# Stability of Graph Convolutional Neural Networks through the lens of small perturbation analysis

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 23 references that are in the map.
- First posted on arXiv 20 Dec 2023.

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

- [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)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [Stability Properties of Graph Neural Networks](https://mlsanity.com/paper/1905.04497/) (2019)
- [Transferability of Spectral Graph Convolutional Neural Networks](https://mlsanity.com/paper/1907.12972/) (2019)
- [Convergence and Stability of Graph Convolutional Networks on Large Random Graphs](https://mlsanity.com/paper/2006.01868/) (2020)
- [On the Transferability of Spectral Graph Filters](https://mlsanity.com/paper/1901.10524/) (2019)
- [Interpretable Stability Bounds for Spectral Graph Filters](https://mlsanity.com/paper/2102.09587/) (2021)
- [Training Stable Graph Neural Networks Through Constrained Learning](https://mlsanity.com/paper/2110.03576/) (2021)
- [Robust Graph Neural Networks via Probabilistic Lipschitz Constraints](https://mlsanity.com/paper/2112.07575/) (2021)
- [On the Stability of Low Pass Graph Filter With a Large Number of Edge Rewires](https://mlsanity.com/paper/2110.07234/) (2021)
- [Learning Stable Graph Neural Networks via Spectral Regularization](https://mlsanity.com/paper/2211.06966/) (2022)

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

- [Generative Diffusion Models for Resource Allocation in Wireless Networks](https://mlsanity.com/paper/2504.20277/) (2025)
- [Enhancing the Resilience of Graph Neural Networks to Topological Perturbations in Sparse Graphs](https://mlsanity.com/paper/2406.03097/) (2024)
- [Exploring Channel Distinguishability in Local Neighborhoods of the Model Space in Quantum Neural Networks](https://mlsanity.com/paper/2410.09470/) (2024)
- [On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspective](https://mlsanity.com/paper/2506.01213/) (2025)
- [Misclassification Rate and Privacy-Utility Trade-offs in Graph Convolutional Networks via Subsampling Stability](https://mlsanity.com/paper/2605.01987/) (2026)

## Abstract (arXiv)

In this work, we study the problem of stability of Graph Convolutional Neural Networks (GCNs) under random small perturbations in the underlying graph topology, i.e. under a limited number of insertions or deletions of edges. We derive a novel bound on the expected difference between the outputs of unperturbed and perturbed GCNs. The proposed bound explicitly depends on the magnitude of the perturbation of the eigenpairs of the Laplacian matrix, and the perturbation explicitly depends on which edges are inserted or deleted. Then, we provide a quantitative characterization of the effect of perturbing specific edges on the stability of the network. We leverage tools from small perturbation analysis to express the bounds in closed, albeit approximate, form, in order to enhance interpretability of the results, without the need to compute any perturbed shift operator. Finally, we numerically evaluate the effectiveness of the proposed bound.