# Generalization bounds for graph convolutional neural networks via Rademacher complexity

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 29 references that are in the map.
- First posted on arXiv 20 Feb 2021.

## Builds on (most cited first, 20 of 20)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Interaction Networks for Learning about Objects, Relations and Physics](https://mlsanity.com/paper/1612.00222/) (2016)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels](https://mlsanity.com/paper/1905.13192/) (2019)
- [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)
- [Generalization Error in Deep Learning](https://mlsanity.com/paper/1808.01174/) (2018)
- [Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Case](https://mlsanity.com/paper/2006.14117/) (2020)
- [Unifying local and non-local signal processing with graph CNNs](https://mlsanity.com/paper/1702.07759/) (2017)

## Built on by (most cited first, 17 of 17)

- [Out-Of-Distribution Generalization on Graphs: A Survey](https://mlsanity.com/paper/2202.07987/) (2022)
- [Towards Understanding the Generalization of Graph Neural Networks](https://mlsanity.com/paper/2305.08048/) (2023)
- [Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling](https://mlsanity.com/paper/2207.03584/) (2022)
- [Bounding the Rademacher Complexity of Fourier neural operators](https://mlsanity.com/paper/2209.05150/) (2022)
- [On the hardness of learning under symmetries](https://mlsanity.com/paper/2401.01869/) (2024)
- [Deeper Insights into Deep Graph Convolutional Networks: Stability and Generalization](https://mlsanity.com/paper/2410.08473/) (2024)
- [Generalization Error of Graph Neural Networks in the Mean-field Regime](https://mlsanity.com/paper/2402.07025/) (2024)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks](https://mlsanity.com/paper/2508.14338/) (2025)
- [Learning on Random Balls is Sufficient for Estimating (Some) Graph Parameters](https://mlsanity.com/paper/2111.03317/) (2021)
- [A Model-Agnostic Graph Neural Network for Integrating Local and Global Information](https://mlsanity.com/paper/2309.13459/) (2023)
- [Conv4Rec: A 1-by-1 Convolutional AutoEncoder for User Profiling through Joint Analysis of Implicit and Explicit Feedbacks](https://mlsanity.com/paper/2509.07499/) (2025)
- [Topology-Aware PAC-Bayesian Generalization Analysis for Graph Neural Networks](https://mlsanity.com/paper/2604.10553/) (2026)
- [SStaGCN: Simplified stacking based graph convolutional networks](https://mlsanity.com/paper/2111.08228/) (2021)
- [Exact Generalisation Error Exposes Benchmarks Skew Graph Neural Networks Success (or Failure)](https://mlsanity.com/paper/2509.10337/) (2025)
- [Rethinking Generalization in Graph Neural Networks: A Structural Complexity Perspective](https://mlsanity.com/paper/2605.13597/) (2026)
- [PAC-Bayesian Adversarially Robust Generalization for Message Passing Graph Neural Networks: A Sensitivity Analysis](https://mlsanity.com/paper/2606.06293/) (2026)

## Abstract (arXiv)

This paper aims at studying the sample complexity of graph convolutional networks (GCNs), by providing tight upper bounds of Rademacher complexity for GCN models with a single hidden layer. Under regularity conditions, theses derived complexity bounds explicitly depend on the largest eigenvalue of graph convolution filter and the degree distribution of the graph. Again, we provide a lower bound of Rademacher complexity for GCNs to show optimality of our derived upper bounds. Taking two commonly used examples as representatives, we discuss the implications of our results in designing graph convolution filters an graph distribution.