TL;DR
Graph Neural Networks (GNNs) often assume that vertex labels are independent given their features, which limits their predictive power on real-world graphs. This paper introduces Correlated Graph Neural Networks (C-GNNs) that explicitly model the correlation between regression residuals, significantly improving accuracy by capturing this overlooked dependency.
What Problem Does This Paper Address?
Graph Neural Networks (GNNs) are powerful tools for learning from graph-structured data, where information is propagated through a network's topology. In regression tasks, a common GNN pipeline involves encoding each vertex's neighborhood into a representation and then independently predicting its label. This "standard pipeline" implicitly assumes that once a vertex's features are known, its label is independent of the labels of other vertices. However, the authors argue that this assumption is often violated in real-world scenarios, where labels of connected entities tend to be correlated (e.g., neighboring counties in an election, or individuals in a social network). This limitation can hinder the predictive accuracy of GNNs, especially when vertex features are only mildly predictive on their own.
Methods
The core contribution is the Correlated Graph Neural Network (C-GNN) framework. Instead of just predicting labels directly, C-GNNs first use a standard GNN as a base regressor to predict initial labels. Then, they explicitly model the correlation structure of the regression residuals (the difference between the true label and the GNN's prediction).
Here's a breakdown of the key methodological aspects:
- Residual Modeling: The residuals are modeled using a multivariate Gaussian distribution. This allows for capturing both positive and negative correlations between residuals of connected vertices.
- Sparse Precision Matrix: To make the model computationally tractable and leverage graph structure, the precision matrix (inverse of the covariance matrix) of the Gaussian distribution is parameterized to be sparse and dependent on the graph topology. Specifically, it's modeled as $\Gamma = \beta(I - \alpha S)$, where $S$ is the normalized adjacency matrix, $\beta$ controls the overall magnitude, and $\alpha$ captures the correlation strength and direction.
- Maximum Likelihood Estimation: The parameters of the C-GNN (including the GNN's weights and the correlation parameters $\alpha, \beta$) are learned by maximizing the marginal likelihood of the observed labels.
- Efficient Optimization: A significant technical contribution is the development of efficient algorithms for computing the log-determinant and its derivatives, which are crucial for the maximum likelihood estimation. These algorithms use stochastic estimation techniques (like Lanczos quadrature and conjugate gradients) to scale to large graphs, reducing the computational complexity from cubic to linear in the number of edges.
- LP-GNN: A simplified version, LP-GNN, is also proposed. It assumes positive correlation and uses label propagation on the GNN residuals, offering a lightweight alternative that still outperforms standard GNNs.
Datasets
The authors evaluate their methods on a variety of datasets:
- Synthetic Datasets:
- Ising model: Used to generate synthetic data with controlled positive and negative label correlations on a grid graph.
- Real-World Datasets:
- U.S. election maps: County-level data from the 2012 and 2016 U.S. presidential elections, using demographic and election statistics.
- Transportation networks: Traffic data from Anaheim and Chicago, modeling directed lanes with different edge types.
- Sexual interaction network: Data from an HIV transmission study, modeling relationships among individuals.
- Twitch social network: Online friendships among Twitch streamers in Portugal, using principal components of their activity as features.
Key Insights and Ideas
- Label correlation is a crucial signal: The paper strongly suggests that ignoring label correlation in regression tasks on graphs is a significant limitation of standard GNNs, and explicitly modeling it can lead to substantial performance gains.
- Residuals, not just labels, are correlated: By modeling the correlation of residuals rather than the labels directly, the framework can handle cases where features are only mildly predictive, and the correlation structure provides complementary information.
- Positive and negative correlations matter: The C-GNN framework can capture both positive (neighboring labels tend to be similar) and negative (neighboring labels tend to be dissimilar) correlations, which is important for diverse real-world phenomena.
- Efficiency is key for scalability: The development of fast, stochastic optimization techniques is critical for applying these correlation-aware models to large-scale graphs, making the approach practical.
- LP-GNN as a simple, effective baseline: The simplified LP-GNN demonstrates that even basic assumptions about positive correlation can yield significant improvements, highlighting the general benefit of incorporating residual information.
Key Results
- Substantial accuracy improvements: C-GNN consistently outperforms standard GNNs across all tested datasets, achieving a mean improvement of 14% in R² (coefficient of determination) and a mean classification accuracy of 0.82 on binary tasks.
- C-MLP outperforms GNN: Even when using a simple Multi-Layer Perceptron (MLP) as the base regressor (which doesn't use graph structure), the correlated version (C-MLP) often outperforms a standard GNN, emphasizing the importance of correlation modeling over just feature aggregation.
- Effective inductive learning: C-GNN can leverage a small number of newly labeled data points in an unseen graph to significantly improve predictions, demonstrating that learned correlation structures generalize.
- Linear scaling: The proposed stochastic optimization methods enable the framework to scale linearly with the number of edges in the graph.
- Interpretable correlation parameters: The learned $\alpha$ parameters provide insights into the nature of correlations (positive/negative, strength) between neighboring vertices in different datasets.
Limitations and Future Work
- Limitations:
- The paper acknowledges that the simplified LP-GNN performs poorly on datasets with negative label correlations, as it assumes positive correlations.
- While C-GNN significantly improves accuracy, the performance gap with GNN narrows when vertex features are highly predictive.
- Future Work:
- The authors suggest exploring more formal understandings of how label correlations provide complementary information to vertex features.
- The framework's ability to measure prediction uncertainty is mentioned but not deeply explored.
- Further investigation into adapting the numerical algorithms for more complex data types and correlation structures is suggested.
Summary updated