# Graph and graphon neural network stability

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Oct 2020.

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

- [Generalization Analysis of Message Passing Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2202.00645/) (2022)
- [Transferability of Graph Neural Networks: an Extended Graphon Approach](https://mlsanity.com/paper/2109.10096/) (2021)
- [A graphon-signal analysis of graph neural networks](https://mlsanity.com/paper/2305.15987/) (2023)
- [Convolutional Neural Networks on Manifolds: From Graphs and Back](https://mlsanity.com/paper/2210.00376/) (2022)
- [Space-Time Graph Neural Networks](https://mlsanity.com/paper/2110.02880/) (2021)
- [Stability to Deformations of Manifold Filters and Manifold Neural Networks](https://mlsanity.com/paper/2106.03725/) (2021)
- [Stability of Neural Networks on Manifolds to Relative Perturbations](https://mlsanity.com/paper/2110.04702/) (2021)
- [Tangent Bundle Filters and Neural Networks: from Manifolds to Cellular Sheaves and Back](https://mlsanity.com/paper/2210.15058/) (2022)
- [Mixed integer linear optimization formulations for learning optimal binary classification trees](https://mlsanity.com/paper/2206.04857/) (2022)
- [Transferability of Graph Neural Networks using Graphon and Sampling Theories](https://mlsanity.com/paper/2307.13206/) (2023)
- [On the Trade-Off between Stability and Representational Capacity in Graph Neural Networks](https://mlsanity.com/paper/2312.02372/) (2023)
- [Learning graphons from data: Random walks, transfer operators, and spectral clustering](https://mlsanity.com/paper/2507.18147/) (2025)
- [Perfect Recovery for Random Geometric Graph Matching with Shallow Graph Neural Networks](https://mlsanity.com/paper/2402.07340/) (2024)
- [Graph data augmentation with Gromow-Wasserstein Barycenters](https://mlsanity.com/paper/2404.08376/) (2024)
- [Graph Learning Should Move Beyond Restrictive Views of Spectral and Message-Passing GNNs](https://mlsanity.com/paper/2602.10031/) (2026)

## Abstract (arXiv)

Graph neural networks (GNNs) are learning architectures that rely on knowledge of the graph structure to generate meaningful representations of large-scale network data. GNN stability is thus important as in real-world scenarios there are typically uncertainties associated with the graph. We analyze GNN stability using kernel objects called graphons. Graphons are both limits of convergent graph sequences and generating models for deterministic and stochastic graphs. Building upon the theory of graphon signal processing, we define graphon neural networks and analyze their stability to graphon perturbations. We then extend this analysis by interpreting the graphon neural network as a generating model for GNNs on deterministic and stochastic graphs instantiated from the original and perturbed graphons. We observe that GNNs are stable to graphon perturbations with a stability bound that decreases asymptotically with the size of the graph. This asymptotic behavior is further demonstrated in an experiment of movie recommendation.