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

2025/09/08 by Huayi Tang, Yong Liu, Tang, Huayi +1
Computer Science · #Advanced Graph Neural Networks #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and ELM

paper · pdf · doi:10.48550/arxiv.2509.06600

openalex publication_date 2025/09/08 · openalex created_date 2025/10/11 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Recent Developments in GNNs for Drug Discovery
• Survey on Generalization Theory for Graph Neural Networks
• A Survey of Graph Transformers: Architectures, Theories and Applications
• Generalization bounds for mixing processes via delayed online-to-PAC conversions
• A Comprehensive Survey of Dynamic Graph Neural Networks: Models, Frameworks, Benchmarks, Experiments and Challenges
• Position: Graph Foundation Models are Already Here
• Generalization Bounds: Perspectives from Information Theory and PAC-Bayes
• Towards Understanding the Generalization of Graph Neural Networks
• A unified recipe for deriving (time-uniform) PAC-Bayes bounds
• Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks
• A Review on Graph Neural Network Methods in Financial Applications
• On Provable Benefits of Depth in Training Graph Convolutional Networks
• User-friendly Introduction to PAC-Bayes Bounds
• A Survey of Graph Neural Networks for Recommender Systems: Challenges, Methods, and Directions
• BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation
• Interpreting and Unifying Graph Neural Networks with An Optimization Framework
• A PAC-Bayesian Approach to Generalization Bounds for Graph Neural\n Networks
• Simple and Deep Graph Convolutional Networks
• Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks
• Adaptive Universal Generalized PageRank Graph Neural Network
• Generalization and Representational Limits of Graph Neural Networks
• Generalization Error Bounds Via R 'enyi-, f-Divergences and Maximal\n Leakage
• McDiarmid-Type Inequalities for Graph-Dependent Variables and Stability Bounds
• Representation Learning on Graphs with Jumping Knowledge Networks
• Graph Attention Networks
• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• Variational Graph Auto-Encoders
• Semi-Supervised Classification with Graph Convolutional Networks
• Concentration of measure without independence: a unified approach via the martingale method
• Gated Graph Sequence Neural Networks
• Robust bounds on risk-sensitive functionals via Renyi divergence
• The Graph Neural Network Model

Related

• A PAC-Bayesian Approach to Generalization Bounds for Graph Neural\n Networks
• Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion
• Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks
• Graph Neural Networks Exponentially Lose Expressive Power for Node Classification
• A Collective Learning Framework to Boost GNN Expressiveness