mlsanityData to 7 Oct 2026

Stability and Generalization of Graph Convolutional Neural Networks

arXiv 1905.01004 ↗First posted 3 May 2019cs.LG cs.AI stat.MLcited by 81

Not on the map. Why?

Abstract (arXiv)

Inspired by convolutional neural networks on 1D and 2D data, graph convolutional neural networks (GCNNs) have been developed for various learning tasks on graph data, and have shown superior performance on real-world datasets. Despite their success, there is a dearth of theoretical explorations of GCNN models such as their generalization properties. In this paper, we take a first step towards developing a deeper theoretical understanding of GCNN models by analyzing the stability of single-layer GCNN models and deriving their generalization guarantees in a semi-supervised graph learning setting. In particular, we show that the algorithmic stability of a GCNN model depends upon the largest absolute eigenvalue of its graph convolution filter. Moreover, to ensure the uniform stability needed to provide strong generalization guarantees, the largest absolute eigenvalue must be independent of the graph size. Our results shed new insights on the design of new & improved graph convolution filters with guaranteed algorithmic stability. We evaluate the generalization gap and stability on various real-world graph datasets and show that the empirical results indeed support our theoretical findings. To the best of our knowledge, we are the first to study stability bounds on graph learning in a semi-supervised setting and derive generalization bounds for GCNN models.

Key facts. Cited by 81 papers in the map (data through 7 Oct 2026). First posted on arXiv 3 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 14; 2022: 14; 2023: 13; 2024: 21; 2025: 11; 2026: 8.

81 papers.

Sort:

  1. 2022Handling Distribution Shifts on Graphs: An Invariance Perspectivecited by 163
  2. 2022Out-Of-Distribution Generalization on Graphs: A Surveycited by 97
  3. 2024GFT: Graph Foundation Model with Transferable Tree Vocabularycited by 82
  4. 2021Graph-based Semi-supervised Learning: A Comprehensive Reviewcited by 79
  5. 2021OOD-GNN: Out-of-Distribution Generalized Graph Neural Networkcited by 78
  6. 2021Subgroup Generalization and Fairness of Graph Neural Networkscited by 69
  7. 2022Theory of Graph Neural Networks: Representation and Learningcited by 60
  8. 2021On Provable Benefits of Depth in Training Graph Convolutional Networkscited by 58
  9. 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 58
  10. 2022Provably expressive temporal graph networkscited by 56
  11. 2021Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networkscited by 51
  12. 2022Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPscited by 42
38 more
  1. 2023Towards Understanding the Generalization of Graph Neural Networkscited by 41
  2. 2023Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?cited by 41
  3. 2021p-Laplacian Based Graph Neural Networkscited by 39
  4. 2023Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusioncited by 39
  5. 2022Spectral Augmentation for Self-Supervised Learning on Graphscited by 38
  6. 2023WL meet VCcited by 30
  7. 2022Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Samplingcited by 23
  8. 2021Towards Open-World Feature Extrapolation: An Inductive Graph Learning Approachcited by 20
  9. 2023Explainable Brain Age Prediction using coVariance Neural Networkscited by 19
  10. 2021Bridging the Gap between Spatial and Spectral Domains: A Unified Framework for Graph Neural Networkscited by 18
  11. 2021Generalization bounds for graph convolutional neural networks via Rademacher complexitycited by 17
  12. 2025Beyond Message Passing: Neural Graph Pattern Machinecited by 17
  13. 2021Graph Neural Networks: Methods, Applications, and Opportunitiescited by 16
  14. 2021Graph Structural Attack by Perturbing Spectral Distancecited by 16
  15. 2023Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networkscited by 16
  16. 2024Generalization Bounds for Message Passing Networks on Mixture of Graphonscited by 16
  17. 2024A Manifold Perspective on the Statistical Generalization of Graph Neural Networkscited by 16
  18. 2024What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encodingcited by 14
  19. 2022Convolutional Neural Networks on Manifolds: From Graphs and Backcited by 13
  20. 2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
  21. 2024Towards Bridging Generalization and Expressivity of Graph Neural Networkscited by 12
  22. 2021Stability to Deformations of Manifold Filters and Manifold Neural Networkscited by 8
  23. 2022Learning Enhanced Representations for Tabular Data via Neighborhood Propagationcited by 6
  24. 2024VC dimension of Graph Neural Networks with Pfaffian activation functionscited by 6
  25. 2024A Comprehensive Benchmark on Spectral GNNs: The Impact on Efficiency, Memory, and Effectivenesscited by 6
  26. 2024Generalization of Geometric Graph Neural Networks with Lipschitz Loss Functionscited by 6
  27. 2024Deeper Insights into Deep Graph Convolutional Networks: Stability and Generalizationcited by 6
  28. 2022Shift-Robust Node Classification via Graph Adversarial Clusteringcited by 5
  29. 2022Space-Time Graph Neural Networks with Stochastic Graph Perturbationscited by 5
  30. 2023Transferability of coVariance Neural Networks and Application to Interpretable Brain Age Prediction using Anatomical Featurescited by 4
  31. 2024PAC-Bayesian Adversarially Robust Generalization Bounds for Graph Neural Networkcited by 4
  32. 2024Generalization Error of Graph Neural Networks in the Mean-field Regimecited by 4
  33. 2024Generalization of Graph Neural Networks is Robust to Model Mismatchcited by 4
  34. 2023Framelet Message Passingcited by 3
  35. 2023How Graph Neural Networks Learn: Lessons from Training Dynamicscited by 3
  36. 2024On the Topology Awareness and Generalization Performance of Graph Neural Networkscited by 3
  37. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  38. 2024Faithful Interpretation for Graph Neural Networkscited by 3

50 most cited of 81 All 81 (JSON)