mlsanityData to 7 Oct 2026

Towards Understanding the Generalization of Graph Neural Networks

arXiv 2305.08048 ↗First posted 14 May 2023cs.LG cs.AIcited by 41

Not on the map. Why?

Abstract (arXiv)

Graph neural networks (GNNs) are the most widely adopted model in graph-structured data oriented learning and representation. Despite their extraordinary success in real-world applications, understanding their working mechanism by theory is still on primary stage. In this paper, we move towards this goal from the perspective of generalization. To be specific, we first establish high probability bounds of generalization gap and gradients in transductive learning with consideration of stochastic optimization. After that, we provide high probability bounds of generalization gap for popular GNNs. The theoretical results reveal the architecture specific factors affecting the generalization gap. Experimental results on benchmark datasets show the consistency between theoretical results and empirical evidence. Our results provide new insights in understanding the generalization of GNNs.

Key facts. Cited by 41 papers in the map (data through 7 Oct 2026). Builds on 73 of its 99 references that are in the map. First posted on arXiv 14 May 2023.

Builds on

73 of 99 references.

References · 73

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Graph Attention Networkscited by 8,854
  4. 2017Inductive Representation Learning on Large Graphscited by 6,284
  5. 2018How Powerful are Graph Neural Networks?cited by 4,355
  6. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  7. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  8. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  9. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
  10. 2019Simplifying Graph Convolutional Networkscited by 1,470
  11. 2020LightGCN: Simplifying and Powering Graph Convolution Network for Recommendationcited by 1,134
  12. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
38 more
  1. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  2. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 987
  3. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 970
  4. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 875
  5. 2020Learning to Simulate Complex Physics with Graph Networkscited by 867
  6. 2020Simple and Deep Graph Convolutional Networkscited by 857
  7. 2020Learning Mesh-Based Simulation with Graph Networkscited by 840
  8. 2019GNNExplainer: Generating Explanations for Graph Neural Networkscited by 735
  9. 2019Graph Neural Networks for Social Recommendationcited by 711
  10. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 679
  11. 2019GraphSAINT: Graph Sampling Based Inductive Learning Methodcited by 618
  12. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 592
  13. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  14. 2020Parameterized Explainer for Graph Neural Networkcited by 423
  15. 2018Lipschitz regularity of deep neural networks: analysis and efficient estimationcited by 413
  16. 2018Deep Learning on Graphs: A Surveycited by 393
  17. 2017Large-scale Point Cloud Semantic Segmentation with Superpoint Graphscited by 384
  18. 2018Invariant and Equivariant Graph Networkscited by 339
  19. 2017Few-Shot Learning with Graph Neural Networkscited by 324
  20. 2018Image Generation from Scene Graphscited by 324
  21. 2019PairNorm: Tackling Oversmoothing in GNNscited by 297
  22. 2019Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networkscited by 290
  23. 2021On Explainability of Graph Neural Networks via Subgraph Explorationscited by 280
  24. 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 218
  25. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  26. 2020XGNN: Towards Model-Level Explanations of Graph Neural Networkscited by 211
  27. 2020PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networkscited by 210
  28. 2021BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximationcited by 195
  29. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  30. 2022Handling Distribution Shifts on Graphs: An Invariance Perspectivecited by 163
  31. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 160
  32. 2019What Can Neural Networks Reason About?cited by 155
  33. 2020From Local Structures to Size Generalization in Graph Neural Networkscited by 119
  34. 2022Out-Of-Distribution Generalization on Graphs: A Surveycited by 97
  35. 2022Decoupling the Depth and Scope of Graph Neural Networkscited by 94
  36. 2018On the Convergence of Adaptive Gradient Methods for Nonconvex Optimizationcited by 91
  37. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 90
  38. 2022How Powerful are K-hop Message Passing Graph Neural Networkscited by 90

50 most cited of 73 All 73 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 18; 2025: 16; 2026: 5.

41 papers.

Sort:

By area:

  1. 2024GFT: Graph Foundation Model with Transferable Tree Vocabularycited by 82
  2. 2025Beyond Message Passing: Neural Graph Pattern Machinecited by 17
  3. 2024A Manifold Perspective on the Statistical Generalization of Graph Neural Networkscited by 16
  4. 2024What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encodingcited by 14
  5. 2024Towards Bridging Generalization and Expressivity of Graph Neural Networkscited by 12
  6. 2024Graph Classification via Reference Distribution Learning: Theory and Practicecited by 11
  7. 2024Generalization of Geometric Graph Neural Networks with Lipschitz Loss Functionscited by 6
  8. 2024Deeper Insights into Deep Graph Convolutional Networks: Stability and Generalizationcited by 6
  9. 2024Future Directions in the Theory of Graph Machine Learningcited by 5
  10. 2024TEDDY: Trimming Edges with Degree-based Discrimination strategYcited by 4
  11. 2024Generalization Error of Graph Neural Networks in the Mean-field Regimecited by 4
  12. 2024Asymptotic generalization error of a single-layer graph convolutional networkcited by 3
29 more
  1. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  2. 2024Generalization capabilities of MeshGraphNets to unseen geometries for fluid dynamicscited by 3
  3. 2023Perfect Alignment May be Poisonous to Graph Contrastive Learningcited by 2
  4. 2023Information-Theoretic Generalization Bounds for Transductive Learning and its Applicationscited by 2
  5. 2024Graph Neural Network Generalization with Gaussian Mixture Model Based Augmentationcited by 2
  6. 2024Making Classic GNNs Strong Baselines Across Varying Homophily: A Smoothness-Generalization Perspectivecited by 2
  7. 2025Statistical physics analysis of graph neural networks: Approaching optimality in the contextual stochastic block modelcited by 2
  8. 2025Understanding Generalization in Node and Link Predictioncited by 2
  9. 2025On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networkscited by 2
  10. 2024When narrower is better: the narrow width limit of Bayesian parallel branching neural networkscited by 1
  11. 2025Tuning Algorithmic and Architectural Hyperparameters in Graph-Based Semi-Supervised Learning with Provable Guaranteescited by 1
  12. 2025MAPN: Enhancing Heterogeneous Sparse Graph Representation by Mamba-based Asynchronous Aggregationcited by 1
  13. 2025A Note on Graphon-Signal Analysis of Graph Neural Networkscited by 1
  14. 2025Estimating Heterogeneous Causal Effect on Networks via Orthogonal Learningcited by 1
  15. 2026SCL-GNN: Towards Generalizable Graph Neural Networks via Spurious Correlation Learningcited by 1
  16. 2024Generalization of Graph Neural Networks through the Lens of Homomorphismcited by 0
  17. 2024Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networkscited by 0
  18. 2025UPL: Uncertainty-aware Pseudo-labeling for Imbalance Transductive Node Classificationcited by 0
  19. 2025Efficient Data Selection for Training Genomic Perturbation Modelscited by 0
  20. 2025Theoretical Learning Performance of Graph Neural Networks: The Impact of Jumping Connections and Layer-wise Sparsificationcited by 0
  21. 2025Memorization in Graph Neural Networkscited by 0
  22. 2025PAC-Bayesian Generalization Bounds for Graph Convolutional Networks on Inductive Node Classificationcited by 0
  23. 2025Exact Generalisation Error Exposes Benchmarks Skew Graph Neural Networks Success (or Failure)cited by 0
  24. 2025On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Modelcited by 0
  25. 2025Resource Allocation in Hybrid Radio-Optical IoT Networks using GNN with Multi-task Learningcited by 0
  26. 2026Graph Learning Should Move Beyond Restrictive Views of Spectral and Message-Passing GNNscited by 0
  27. 2026Transductive Generalization via Optimal Transport and Its Application to Graph Node Classificationcited by 0
  28. 2026Rethinking Generalization in Graph Neural Networks: A Structural Complexity Perspectivecited by 0
  29. 2026Local-Global Geometric Insights for Graph Neural Networks via Entropic Curvaturecited by 0