Data to 14 Oct 2026

A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks

arXiv 2012.07690 ↗First posted 14 Dec 2020cs.LGcited by 85

Not on the map. Why?

Abstract (arXiv)

In this paper, we derive generalization bounds for the two primary classes of graph neural networks (GNNs), namely graph convolutional networks (GCNs) and message passing GNNs (MPGNNs), via a PAC-Bayesian approach. Our result reveals that the maximum node degree and spectral norm of the weights govern the generalization bounds of both models. We also show that our bound for GCNs is a natural generalization of the results developed in arXiv:1707.09564v2 [cs.LG] for fully-connected and convolutional neural networks. For message passing GNNs, our PAC-Bayes bound improves over the Rademacher complexity based bound in arXiv:2002.06157v1 [cs.LG], showing a tighter dependency on the maximum node degree and the maximum hidden dimension. The key ingredients of our proofs are a perturbation analysis of GNNs and the generalization of PAC-Bayes analysis to non-homogeneous GNNs. We perform an empirical study on several real-world graph datasets and verify that our PAC-Bayes bound is tighter than others.

Key facts. Cited by 85 papers in the map (data through 14 Oct 2026). First posted on arXiv 14 Dec 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 11; 2022: 16; 2023: 14; 2024: 24; 2025: 12; 2026: 8.

85 papers.

Sort:

2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 122
2023What and How does In-Context Learning Learn? Bayesian Model Averaging, Parameterization, and Generalizationcited by 118
2022Out-Of-Distribution Generalization on Graphs: A Surveycited by 97
2024GFT: Graph Foundation Model with Transferable Tree Vocabularycited by 85
2022Debiasing Graph Neural Networks via Learning Disentangled Causal Substructurecited by 83
2021Generalizing Graph Neural Networks on Out-Of-Distribution Graphscited by 71
2021Subgroup Generalization and Fairness of Graph Neural Networkscited by 69
2021Reconstruction for Powerful Graph Representationscited by 65
2022Theory of Graph Neural Networks: Representation and Learningcited by 61
2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 59
2021On Provable Benefits of Depth in Training Graph Convolutional Networkscited by 58
2022Provably expressive temporal graph networkscited by 56

38 more

2021Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networkscited by 51
2022PipeGCN: Efficient Full-Graph Training of Graph Convolutional Networks with Pipelined Feature Communicationcited by 45
2022Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networkscited by 41
2023Towards Understanding the Generalization of Graph Neural Networkscited by 41
2023Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?cited by 41
2023Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusioncited by 40
2022Robust Fine-Tuning of Deep Neural Networks with Hessian-based Generalization Guaranteescited by 34
2023WL meet VCcited by 31
2023A graphon-signal analysis of graph neural networkscited by 30
2022Debiased Graph Neural Networks with Agnostic Label Selection Biascited by 25
2022Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Samplingcited by 23
2022Adversarial Weight Perturbation Improves Generalization in Graph Neural Networkscited by 21
2022Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspectivecited by 19
2021Generalization bounds for graph convolutional neural networks via Rademacher complexitycited by 17
2024Generalization Bounds for Message Passing Networks on Mixture of Graphonscited by 17
2024A Manifold Perspective on the Statistical Generalization of Graph Neural Networkscited by 17
2024What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encodingcited by 14
2022Homophily modulates double descent generalization in graph convolution networkscited by 13
2024On the hardness of learning under symmetriescited by 13
2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
2024Towards Bridging Generalization and Expressivity of Graph Neural Networkscited by 12
2024Graph Classification via Reference Distribution Learning: Theory and Practicecited by 11
2022Analysis of Convolutions, Non-linearity and Depth in Graph Neural Networks using Neural Tangent Kernelcited by 8
2024Almost Surely Asymptotically Constant Graph Neural Networkscited by 7
2024VC dimension of Graph Neural Networks with Pfaffian activation functionscited by 6
2024Future Directions in the Theory of Graph Machine Learningcited by 6
2024Generalization of Geometric Graph Neural Networks with Lipschitz Loss Functionscited by 6
2024Deeper Insights into Deep Graph Convolutional Networks: Stability and Generalizationcited by 6
2024Graph neural networks and non-commuting operatorscited by 5
2025Graph Representational Learning: When Does More Expressivity Hurt Generalization?cited by 5
2021On the Importance of Sampling in Training GCNs: Tighter Analysis and Variance Reductioncited by 4
2023Generalization Bounds for Neural Belief Propagation Decoderscited by 4
2024PAC-Bayesian Adversarially Robust Generalization Bounds for Graph Neural Networkcited by 4
2024Generalization Error of Graph Neural Networks in the Mean-field Regimecited by 4
2024Generalization of Graph Neural Networks is Robust to Model Mismatchcited by 4
2026Towards A Unified PAC-Bayesian Framework for Norm-based Generalization Boundscited by 4
2023Generalization Limits of Graph Neural Networks in Identity Effects Learningcited by 3
2023Sharpness-Aware Graph Collaborative Filteringcited by 3

50 most cited of 85 All 85 (JSON)