On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks
Not on the map. Why?
Abstract (arXiv)
This paper studies the interplay between learning algorithms and graph structure for graph neural networks (GNNs). Existing theoretical studies on the learning dynamics of GNNs primarily focus on the convergence rates of learning algorithms under the interpolation regime (noise-free) and offer only a crude connection between these dynamics and the actual graph structure (e.g., maximum degree). This paper aims to bridge this gap by investigating the excessive risk (generalization performance) of learning algorithms in GNNs within the generalization regime (with noise). Specifically, we extend the conventional settings from the learning theory literature to the context of GNNs and examine how graph structure influences the performance of learning algorithms such as stochastic gradient descent (SGD) and Ridge regression. Our study makes several key contributions toward understanding the interplay between graph structure and learning in GNNs. First, we derive the excess risk profiles of SGD and Ridge regression in GNNs and connect these profiles to the graph structure through spectral graph theory. With this established framework, we further explore how different graph structures (regular vs. power-law) impact the performance of these algorithms through comparative analysis. Additionally, we extend our analysis to multi-layer linear GNNs, revealing an increasing non-isotropic effect on the excess risk profile, thereby offering new insights into the over-smoothing issue in GNNs from the perspective of learning algorithms. Our empirical results align with our theoretical predictions, collectively showcasing a coupling relation among graph structure, GNNs and learning algorithms, and providing insights on GNN algorithm design and selection in practice.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 46 of its 73 references that are in the map. First posted on arXiv 20 Aug 2025.
Builds on
46 of 73 references.
References · 46
- 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
- 2017Graph Attention Networkscited by 8,923
- 2017Inductive Representation Learning on Large Graphscited by 6,320
- 2018How Powerful are Graph Neural Networks?cited by 4,393
- 2017Neural Message Passing for Quantum Chemistrycited by 3,487
- 2019Simplifying Graph Convolutional Networkscited by 1,477
- 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,102
- 2018FastGCN: Fast Learning with Graph Convolutional Networks via Importance Samplingcited by 584
- 2019Benign Overfitting in Linear Regressioncited by 549
- 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 513
- 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 478
- 2017Scene Graph Generation by Iterative Message Passingcited by 462
34 more
- 2017Neural Motifs: Scene Graph Parsing with Global Contextcited by 414
- 2016Visual Relationship Detection with Language Priorscited by 334
- 2023A Survey on Oversmoothing in Graph Neural Networkscited by 247
- 2022Graph neural networks for materials science and chemistrycited by 182
- 2018Adaptive Sampling Towards Fast Graph Representation Learningcited by 180
- 2022Handling Distribution Shifts on Graphs: An Invariance Perspectivecited by 164
- 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 161
- 2020Benign overfitting in ridge regressioncited by 153
- 2015High-Dimensional Asymptotics of Prediction: Ridge Regression and Classificationcited by 148
- 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
- 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 111
- 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111
- 2020On the Optimal Weighted ℓ2 Regularization in Overparameterized Linear Regressioncited by 98
- 2021Shift-Robust GNNs: Overcoming the Limitations of Localized Graph Training Datacited by 87
- 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 85
- 2019Stability and Generalization of Graph Convolutional Neural Networkscited by 81
- 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
- 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
- 2021Subgroup Generalization and Fairness of Graph Neural Networkscited by 69
- 2016Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regressioncited by 64
- 2023A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Testscited by 64
- 2022Theory of Graph Neural Networks: Representation and Learningcited by 61
- 2018Optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularizationcited by 53
- 2023Towards Understanding the Generalization of Graph Neural Networkscited by 41
- 2020Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Modelcited by 39
- 2021The Benefits of Implicit Regularization from SGD in Least Squares Problemscited by 32
- 2020Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networkscited by 31
- 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
- 2017A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)cited by 26
- 2022Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensionscited by 23
- 2021Generalization bounds for graph convolutional neural networks via Rademacher complexitycited by 17
- 2024MSPipe: Efficient Temporal GNN Training via Staleness-Aware Pipelinecited by 12
- 2023Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuroncited by 8
- 2024On the Topology Awareness and Generalization Performance of Graph Neural Networkscited by 3
Built on by
Citing papers per year: 2026: 2.
2 papers.