# Stability and Generalization of Graph Convolutional Neural Networks

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

## Key facts

- Cited by 81 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 May 2019.

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

- [Handling Distribution Shifts on Graphs: An Invariance Perspective](https://mlsanity.com/paper/2202.02466/) (2022)
- [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)
- [Graph-based Semi-supervised Learning: A Comprehensive Review](https://mlsanity.com/paper/2102.13303/) (2021)
- [OOD-GNN: Out-of-Distribution Generalized Graph Neural Network](https://mlsanity.com/paper/2112.03806/) (2021)
- [Subgroup Generalization and Fairness of Graph Neural Networks](https://mlsanity.com/paper/2106.15535/) (2021)
- [Theory of Graph Neural Networks: Representation and Learning](https://mlsanity.com/paper/2204.07697/) (2022)
- [Generalization Analysis of Message Passing Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2202.00645/) (2022)
- [On Provable Benefits of Depth in Training Graph Convolutional Networks](https://mlsanity.com/paper/2110.15174/) (2021)
- [Provably expressive temporal graph networks](https://mlsanity.com/paper/2209.15059/) (2022)
- [Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks](https://mlsanity.com/paper/2112.03968/) (2021)
- [Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs](https://mlsanity.com/paper/2212.09034/) (2022)
- [Towards Understanding the Generalization of Graph Neural Networks](https://mlsanity.com/paper/2305.08048/) (2023)
- [Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?](https://mlsanity.com/paper/2306.01323/) (2023)
- [Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion](https://mlsanity.com/paper/2302.04451/) (2023)
- [p-Laplacian Based Graph Neural Networks](https://mlsanity.com/paper/2111.07337/) (2021)
- [Spectral Augmentation for Self-Supervised Learning on Graphs](https://mlsanity.com/paper/2210.00643/) (2022)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)
- [Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling](https://mlsanity.com/paper/2207.03584/) (2022)
- [Towards Open-World Feature Extrapolation: An Inductive Graph Learning Approach](https://mlsanity.com/paper/2110.04514/) (2021)
- [Explainable Brain Age Prediction using coVariance Neural Networks](https://mlsanity.com/paper/2305.18370/) (2023)
- [Bridging the Gap between Spatial and Spectral Domains: A Unified Framework for Graph Neural Networks](https://mlsanity.com/paper/2107.10234/) (2021)
- [Generalization bounds for graph convolutional neural networks via Rademacher complexity](https://mlsanity.com/paper/2102.10234/) (2021)
- [Generalization Bounds for Message Passing Networks on Mixture of Graphons](https://mlsanity.com/paper/2404.03473/) (2024)
- [A Manifold Perspective on the Statistical Generalization of Graph Neural Networks](https://mlsanity.com/paper/2406.05225/) (2024)
- [Beyond Message Passing: Neural Graph Pattern Machine](https://mlsanity.com/paper/2501.18739/) (2025)
- [Graph Neural Networks: Methods, Applications, and Opportunities](https://mlsanity.com/paper/2108.10733/) (2021)
- [Graph Structural Attack by Perturbing Spectral Distance](https://mlsanity.com/paper/2111.00684/) (2021)
- [Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks](https://mlsanity.com/paper/2302.02922/) (2023)
- [Convolutional Neural Networks on Manifolds: From Graphs and Back](https://mlsanity.com/paper/2210.00376/) (2022)

## Abstract (arXiv)

Inspired by convolutional neural networks on 1D and 2D data, graph convolutional neural networks (GCNNs) have been developed for various learning tasks on graph data, and have shown superior performance on real-world datasets. Despite their success, there is a dearth of theoretical explorations of GCNN models such as their generalization properties. In this paper, we take a first step towards developing a deeper theoretical understanding of GCNN models by analyzing the stability of single-layer GCNN models and deriving their generalization guarantees in a semi-supervised graph learning setting. In particular, we show that the algorithmic stability of a GCNN model depends upon the largest absolute eigenvalue of its graph convolution filter. Moreover, to ensure the uniform stability needed to provide strong generalization guarantees, the largest absolute eigenvalue must be independent of the graph size. Our results shed new insights on the design of new & improved graph convolution filters with guaranteed algorithmic stability. We evaluate the generalization gap and stability on various real-world graph datasets and show that the empirical results indeed support our theoretical findings. To the best of our knowledge, we are the first to study stability bounds on graph learning in a semi-supervised setting and derive generalization bounds for GCNN models.