mlsanityData to 7 Oct 2026

Deeper Insights into Deep Graph Convolutional Networks: Stability and Generalization

arXiv 2410.08473 ↗First posted 11 Oct 2024cs.LG cs.AI stat.MLcited by 6

Not on the map. Why?

Abstract (arXiv)

Graph convolutional networks (GCNs) have emerged as powerful models for graph learning tasks, exhibiting promising performance in various domains. While their empirical success is evident, there is a growing need to understand their essential ability from a theoretical perspective. Existing theoretical research has primarily focused on the analysis of single-layer GCNs, while a comprehensive theoretical exploration of the stability and generalization of deep GCNs remains limited. In this paper, we bridge this gap by delving into the stability and generalization properties of deep GCNs, aiming to provide valuable insights by characterizing rigorously the associated upper bounds. Our theoretical results reveal that the stability and generalization of deep GCNs are influenced by certain key factors, such as the maximum absolute eigenvalue of the graph filter operators and the depth of the network. Our theoretical studies contribute to a deeper understanding of the stability and generalization properties of deep GCNs, potentially paving the way for developing more reliable and well-performing models.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 48 of its 69 references that are in the map. First posted on arXiv 11 Oct 2024.

Builds on

48 of 69 references.

References · 48

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2018How Powerful are Graph Neural Networks?cited by 4,355
  3. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  4. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  5. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
  6. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  7. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,097
  8. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 970
  9. 2020Simple and Deep Graph Convolutional Networkscited by 857
  10. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 679
  11. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  12. 2018Deep Learning on Graphs: A Surveycited by 393
36 more
  1. 2020Explainability in Graph Neural Networks: A Taxonomic Surveycited by 383
  2. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  3. 2019PairNorm: Tackling Oversmoothing in GNNscited by 297
  4. 2021On Explainability of Graph Neural Networks via Subgraph Explorationscited by 280
  5. 2023A Survey on Oversmoothing in Graph Neural Networkscited by 246
  6. 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 218
  7. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  8. 2020XGNN: Towards Model-Level Explanations of Graph Neural Networkscited by 211
  9. 2019Graph Neural Networks with convolutional ARMA filterscited by 185
  10. 2022Graph Neural Networks for Graphs with Heterophily: A Surveycited by 175
  11. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  12. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 160
  13. 2019What Can Neural Networks Reason About?cited by 155
  14. 2020Higher-Order Explanations of Graph Neural Networks via Relevant Walkscited by 138
  15. 2019A Gentle Introduction to Deep Learning for Graphscited by 107
  16. 2022Out-Of-Distribution Generalization on Graphs: A Surveycited by 97
  17. 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 84
  18. 2019Stability and Generalization of Graph Convolutional Neural Networkscited by 81
  19. 2021OOD-GNN: Out-of-Distribution Generalized Graph Neural Networkcited by 78
  20. 2020Convergence and Stability of Graph Convolutional Networks on Large Random Graphscited by 75
  21. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  22. 2022Theory of Graph Neural Networks: Representation and Learningcited by 60
  23. 2021On Provable Benefits of Depth in Training Graph Convolutional Networkscited by 58
  24. 2019Understanding the Representation Power of Graph Neural Networks in Learning Graph Topologycited by 52
  25. 2021Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networkscited by 51
  26. 2023Towards Understanding the Generalization of Graph Neural Networkscited by 41
  27. 2023Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusioncited by 39
  28. 2021Bag of Tricks for Training Deeper Graph Neural Networks: A Comprehensive Benchmark Studycited by 36
  29. 2020Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networkscited by 31
  30. 2020Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Casecited by 24
  31. 2022Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Samplingcited by 23
  32. 2021Generalization bounds for graph convolutional neural networks via Rademacher complexitycited by 17
  33. 2024What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encodingcited by 14
  34. 2022Homophily modulates double descent generalization in graph convolution networkscited by 13
  35. 2020Emotional Conversation Generation with Heterogeneous Graph Neural Networkcited by 9
  36. 2023Decouple Graph Neural Networks: Train Multiple Simple GNNs Simultaneously Instead of Onecited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 2; 2026: 4.

6 papers.

  1. 2025Stability and Generalization of Quantum Neural Networkscited by 3
  2. 2025Directed Acyclic Graph Convolutional Networkscited by 1
  3. 2026TypeBandit: Type-Level Context Allocation and Reweighting for Effective Attribute Completion in Heterogeneous Graph Neural Networkscited by 0
  4. 2026Rethinking Generalization in Graph Neural Networks: A Structural Complexity Perspectivecited by 0
  5. 2026Difference-of-Convex Regularization for Graph Learning by Differentiable Programmingcited by 0
  6. 2026When Do Language-Grounded Explanations Help? A Graph-Bottleneck for Farm Monitoring Interpretable Sheep Facial Paincited by 0