# Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks

arXiv: https://arxiv.org/abs/2112.03968 · HTML: https://mlsanity.com/paper/2112.03968/

## Key facts

- Cited by 51 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 55 references that are in the map.
- First posted on arXiv 7 Dec 2021.

## Builds on (most cited first, 30 of 33)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Does Learning Require Memorization? A Short Tale about a Long Tail](https://mlsanity.com/paper/1906.05271/) (2019)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks](https://mlsanity.com/paper/1810.02281/) (2018)
- [Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels](https://mlsanity.com/paper/1905.13192/) (2019)
- [When Do Neural Networks Outperform Kernel Methods?](https://mlsanity.com/paper/2006.13409/) (2020)
- [Discriminative Embeddings of Latent Variable Models for Structured Data](https://mlsanity.com/paper/1603.05629/) (2016)
- [NetGAN: Generating Graphs via Random Walks](https://mlsanity.com/paper/1803.00816/) (2018)
- [A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks](https://mlsanity.com/paper/2012.07690/) (2020)
- [Stability and Generalization of Graph Convolutional Neural Networks](https://mlsanity.com/paper/1905.01004/) (2019)
- [Convergence and Stability of Graph Convolutional Networks on Large Random Graphs](https://mlsanity.com/paper/2006.01868/) (2020)
- [Diving into the shallows: a computational perspective on large-scale shallow learning](https://mlsanity.com/paper/1703.10622/) (2017)
- [Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks](https://mlsanity.com/paper/2006.08550/) (2020)
- [Transductive Rademacher Complexity and its Applications](https://mlsanity.com/paper/1401.3441/) (2014)
- [Mean-field theory of graph neural networks in graph partitioning](https://mlsanity.com/paper/1810.11908/) (2018)

## Built on by (most cited first, 30 of 51)

- [Out-Of-Distribution Generalization on Graphs: A Survey](https://mlsanity.com/paper/2202.07987/) (2022)
- [GFT: Graph Foundation Model with Transferable Tree Vocabulary](https://mlsanity.com/paper/2411.06070/) (2024)
- [Towards Understanding the Generalization of Graph Neural Networks](https://mlsanity.com/paper/2305.08048/) (2023)
- [Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion](https://mlsanity.com/paper/2302.04451/) (2023)
- [Towards Graph Foundation Models: Learning Generalities Across Graphs via Task-Trees](https://mlsanity.com/paper/2412.16441/) (2024)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)
- [A Manifold Perspective on the Statistical Generalization of Graph Neural Networks](https://mlsanity.com/paper/2406.05225/) (2024)
- [Approximately Equivariant Graph Networks](https://mlsanity.com/paper/2308.10436/) (2023)
- [What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding](https://mlsanity.com/paper/2406.01977/) (2024)
- [Homophily modulates double descent generalization in graph convolution networks](https://mlsanity.com/paper/2212.13069/) (2022)
- [Weisfeiler-Leman at the margin: When more expressivity matters](https://mlsanity.com/paper/2402.07568/) (2024)
- [Towards Bridging Generalization and Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2410.10051/) (2024)
- [Analysis of Convolutions, Non-linearity and Depth in Graph Neural Networks using Neural Tangent Kernel](https://mlsanity.com/paper/2210.09809/) (2022)
- [VC dimension of Graph Neural Networks with Pfaffian activation functions](https://mlsanity.com/paper/2401.12362/) (2024)
- [Generalization of Geometric Graph Neural Networks with Lipschitz Loss Functions](https://mlsanity.com/paper/2409.05191/) (2024)
- [Deeper Insights into Deep Graph Convolutional Networks: Stability and Generalization](https://mlsanity.com/paper/2410.08473/) (2024)
- [PAC-Bayesian Adversarially Robust Generalization Bounds for Graph Neural Network](https://mlsanity.com/paper/2402.04038/) (2024)
- [Generalization Error of Graph Neural Networks in the Mean-field Regime](https://mlsanity.com/paper/2402.07025/) (2024)
- [Generalization of Graph Neural Networks is Robust to Model Mismatch](https://mlsanity.com/paper/2408.13878/) (2024)
- [Asymptotic generalization error of a single-layer graph convolutional network](https://mlsanity.com/paper/2402.03818/) (2024)
- [On the Topology Awareness and Generalization Performance of Graph Neural Networks](https://mlsanity.com/paper/2403.04482/) (2024)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [Robust Graph Structure Learning with the Alignment of Features and Adjacency Matrix](https://mlsanity.com/paper/2307.02126/) (2023)
- [Information-Theoretic Generalization Bounds for Transductive Learning and its Applications](https://mlsanity.com/paper/2311.04561/) (2023)
- [Statistical Guarantees for Link Prediction using Graph Neural Networks](https://mlsanity.com/paper/2402.02692/) (2024)
- [PAC-Bayesian Generalization Bounds for Knowledge Graph Representation Learning](https://mlsanity.com/paper/2405.06418/) (2024)
- [Equivariant Machine Learning on Graphs with Nonlinear Spectral Filters](https://mlsanity.com/paper/2406.01249/) (2024)
- [Graph Neural Network Generalization with Gaussian Mixture Model Based Augmentation](https://mlsanity.com/paper/2411.08638/) (2024)
- [Generalization Performance of Hypergraph Neural Networks](https://mlsanity.com/paper/2501.12554/) (2025)
- [Statistical physics analysis of graph neural networks: Approaching optimality in the contextual stochastic block model](https://mlsanity.com/paper/2503.01361/) (2025)

## Abstract (arXiv)

In recent years, several results in the supervised learning setting suggested that classical statistical learning-theoretic measures, such as VC dimension, do not adequately explain the performance of deep learning models which prompted a slew of work in the infinite-width and iteration regimes. However, there is little theoretical explanation for the success of neural networks beyond the supervised setting. In this paper we argue that, under some distributional assumptions, classical learning-theoretic measures can sufficiently explain generalization for graph neural networks in the transductive setting. In particular, we provide a rigorous analysis of the performance of neural networks in the context of transductive inference, specifically by analysing the generalisation properties of graph convolutional networks for the problem of node classification. While VC Dimension does result in trivial generalisation error bounds in this setting as well, we show that transductive Rademacher complexity can explain the generalisation properties of graph convolutional networks for stochastic block models. We further use the generalisation error bounds based on transductive Rademacher complexity to demonstrate the role of graph convolutions and network architectures in achieving smaller generalisation error and provide insights into when the graph structure can help in learning. The findings of this paper could re-new the interest in studying generalisation in neural networks in terms of learning-theoretic measures, albeit in specific problems.