Residual Correlation in Graph Neural Network Regression

Abstract

A graph neural network transforms features in each vertex's neighborhood into a vector representation of the vertex. Afterward, each vertex's representation is used independently for predicting its label. This standard pipeline implicitly assumes that vertex labels are conditionally independent given their neighborhood features. However, this is a strong assumption, and we show that it is far from true on many real-world graph datasets. Focusing on regression tasks, we find that this conditional independence assumption severely limits predictive power. This should not be that surprising, given that traditional graph-based semi-supervised learning methods such as label propagation work in the opposite fashion by explicitly modeling the correlation in predicted outcomes. Here, we address this problem with an interpretable and efficient framework that can improve any graph neural network architecture simply by exploiting correlation structure in the regression residuals. In particular, we model the joint distribution of residuals on vertices with a parameterized multivariate Gaussian, and estimate the parameters by maximizing the marginal likelihood of the observed labels. Our framework achieves substantially higher accuracy than competing baselines, and the learned parameters can be interpreted as the strength of correlation among connected vertices. Furthermore, we develop linear time algorithms for low-variance, unbiased model parameter estimates, allowing us to scale to large networks. We also provide a basic version of our method that makes stronger assumptions on correlation structure but is painless to implement, often leading to great practical performance with minimal overhead.

References in corpus (11)

• Semi-Supervised Classification with Graph Convolutional Networks
• Inductive Representation Learning on Large Graphs
• Graph Neural Networks: A Review of Methods and Applications
• Graph Convolutional Matrix Completion
• GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration
• FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling
• Is the Voter Model a model for voters?
• GMNN: Graph Markov Neural Networks
• Position-aware Graph Neural Networks
• Empirical stationary correlations for semi-supervised learning on graphs
• Convergence of the Conjugate Gradient Method on Singular Systems

Cited by in corpus (21)

• Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs
• Combining Label Propagation and Simple Models Out-performs Graph Neural Networks
• Adaptive Universal Generalized PageRank Graph Neural Network
• MGH: Metadata Guided Hypergraph Modeling for Unsupervised Person Re-identification
• New Benchmarks for Learning on Non-Homophilous Graphs
• Understanding and Resolving Performance Degradation in Graph Convolutional Networks
• Boost then Convolve: Gradient Boosting Meets Graph Neural Networks
• Local Augmentation for Graph Neural Networks
• Spatial Heterophily Aware Graph Neural Networks
• Graph Neural Networks Inspired by Classical Iterative Algorithms
• Beyond Independent Error Assumptions in Large GNN Atomistic Models
• Residual Correction in Real-Time Traffic Forecasting
• You are AllSet: A Multiset Function Framework for Hypergraph Neural Networks
• Positional Encoder Graph Neural Networks for Geographic Data
• Graph-Based Methods for Discrete Choice
• Graph-Based Model-Agnostic Data Subsampling for Recommendation Systems
• Graph Belief Propagation Networks
• CopulaGNN: Towards Integrating Representational and Correlational Roles of Graphs in Graph Neural Networks
• Scaffold-Induced Molecular Graph (SIMG): Effective Graph Sampling Methods for High-Throughput Computational Drug Discovery
• Random Graph-Based Neuromorphic Learning with a Layer-Weaken Structure
• S2Vec: Self-Supervised Geospatial Embeddings for the Built Environment