mlsanityData to 14 Oct 2026

PAC-Bayesian Generalization Bounds for Graph Convolutional Networks on Inductive Node Classification

arXiv 2509.06600 ↗First posted 8 Sep 2025cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Graph neural networks (GNNs) have achieved remarkable success in processing graph-structured data across various applications. A critical aspect of real-world graphs is their dynamic nature, where new nodes are continually added and existing connections may change over time. Previous theoretical studies, largely based on the transductive learning framework, fail to adequately model such temporal evolution and structural dynamics. In this paper, we presents a PAC-Bayesian theoretical analysis of graph convolutional networks (GCNs) for inductive node classification, treating nodes as dependent and non-identically distributed data points. We derive novel generalization bounds for one-layer GCNs that explicitly incorporate the effects of data dependency and non-stationarity, and establish sufficient conditions under which the generalization gap converges to zero as the number of nodes increases. Furthermore, we extend our analysis to two-layer GCNs, and reveal that it requires stronger assumptions on graph topology to guarantee convergence. This work establishes a theoretical foundation for understanding and improving GNN generalization in dynamic graph environments.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 37 of its 54 references that are in the map. First posted on arXiv 8 Sep 2025.

Builds on

37 of 54 references.

References · 37

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2017Inductive Representation Learning on Large Graphscited by 6,320
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  5. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  6. 2016Variational Graph Auto-Encoderscited by 1,382
  7. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 993
  8. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 877
  9. 2020Simple and Deep Graph Convolutional Networkscited by 860
  10. 2015Gated Graph Sequence Neural Networkscited by 796
  11. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 595
  12. 2021User-friendly introduction to PAC-Bayes boundscited by 239
25 more
  1. 2020Generalization and Representational Limits of Graph Neural Networkscited by 218
  2. 2021BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximationcited by 195
  3. 2019Graph Neural Networks with convolutional ARMA filterscited by 185
  4. 2021A Survey of Graph Neural Networks for Recommender Systems: Challenges, Methods, and Directionscited by 144
  5. 2021Interpreting and Unifying Graph Neural Networks with An Optimization Frameworkcited by 131
  6. 2023Graph Foundation Models: Concepts, Opportunities and Challengescited by 103
  7. 2024Position: Graph Foundation Models are Already Herecited by 86
  8. 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 85
  9. 2021A Review on Graph Neural Network Methods in Financial Applicationscited by 78
  10. 2023Generalization Bounds: Perspectives from Information Theory and PAC-Bayescited by 61
  11. 2021On Provable Benefits of Depth in Training Graph Convolutional Networkscited by 58
  12. 2021Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networkscited by 51
  13. 2019Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakagecited by 48
  14. 2016Simpler PAC-Bayesian Bounds for Hostile Datacited by 46
  15. 2020Generalization Bounds via Information Density and Conditional Information Densitycited by 43
  16. 2023Towards Understanding the Generalization of Graph Neural Networkscited by 41
  17. 2020Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networkscited by 31
  18. 2024A Comprehensive Survey of Dynamic Graph Neural Networks: Models, Frameworks, Benchmarks, Experiments and Challengescited by 30
  19. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  20. 2023A unified recipe for deriving (time-uniform) PAC-Bayes boundscited by 25
  21. 2025Survey on Generalization Theory for Graph Neural Networkscited by 16
  22. 2019McDiarmid-Type Inequalities for Graph-Dependent Variables and Stability Boundscited by 15
  23. 2025A Survey of Graph Transformers: Architectures, Theories and Applicationscited by 14
  24. 2024Generalization bounds for mixing processes via delayed online-to-PAC conversionscited by 9
  25. 2025Recent Developments in GNNs for Drug Discoverycited by 3

Built on by

Not cited yet.