# On the Stability of Graph Convolutional Neural Networks under Edge Rewiring

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

## Key facts

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

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

- [Transferability of Graph Neural Networks: an Extended Graphon Approach](https://mlsanity.com/paper/2109.10096/) (2021)
- [Transferability Properties of Graph Neural Networks](https://mlsanity.com/paper/2112.04629/) (2021)
- [Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks](https://mlsanity.com/paper/2210.01906/) (2022)
- [A Comprehensive Survey on Data Augmentation](https://mlsanity.com/paper/2405.09591/) (2024)
- [On the Stability of Expressive Positional Encodings for Graphs](https://mlsanity.com/paper/2310.02579/) (2023)
- [Interpretable Stability Bounds for Spectral Graph Filters](https://mlsanity.com/paper/2102.09587/) (2021)
- [Homophily-oriented Heterogeneous Graph Rewiring](https://mlsanity.com/paper/2302.06299/) (2023)
- [Generalization Bounds for Message Passing Networks on Mixture of Graphons](https://mlsanity.com/paper/2404.03473/) (2024)
- [Graph-Time Convolutional Neural Networks: Architecture and Theoretical Analysis](https://mlsanity.com/paper/2206.15174/) (2022)
- [Node-Variant Graph Filters in Graph Neural Networks](https://mlsanity.com/paper/2106.00089/) (2021)
- [Stability of Aggregation Graph Neural Networks](https://mlsanity.com/paper/2207.03678/) (2022)
- [Sparse Covariance Neural Networks](https://mlsanity.com/paper/2410.01669/) (2024)
- [On the Stability of Low Pass Graph Filter With a Large Number of Edge Rewires](https://mlsanity.com/paper/2110.07234/) (2021)
- [Learning Stochastic Graph Neural Networks with Constrained Variance](https://mlsanity.com/paper/2201.12611/) (2022)
- [Space-Time Graph Neural Networks with Stochastic Graph Perturbations](https://mlsanity.com/paper/2210.16270/) (2022)
- [Graph neural networks and non-commuting operators](https://mlsanity.com/paper/2411.04265/) (2024)
- [Learning Stable Graph Neural Networks via Spectral Regularization](https://mlsanity.com/paper/2211.06966/) (2022)
- [Robust Graph Neural Network based on Graph Denoising](https://mlsanity.com/paper/2312.06557/) (2023)
- [Framelet Message Passing](https://mlsanity.com/paper/2302.14806/) (2023)
- [Limitless stability for Graph Convolutional Networks](https://mlsanity.com/paper/2301.11443/) (2023)
- [On the Trade-Off between Stability and Representational Capacity in Graph Neural Networks](https://mlsanity.com/paper/2312.02372/) (2023)
- [Graph Convolutional Neural Networks Sensitivity under Probabilistic Error Model](https://mlsanity.com/paper/2203.07831/) (2022)
- [On the Convergence and Size Transferability of Continuous-depth Graph Neural Networks](https://mlsanity.com/paper/2510.03923/) (2025)
- [On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspective](https://mlsanity.com/paper/2506.01213/) (2025)
- [Towards Fair Graph Prompting: A Dual-Prompt Mechanism for Mitigating Attribute and Structural Bias](https://mlsanity.com/paper/2510.23469/) (2025)

## Abstract (arXiv)

Graph neural networks are experiencing a surge of popularity within the machine learning community due to their ability to adapt to non-Euclidean domains and instil inductive biases. Despite this, their stability, i.e., their robustness to small perturbations in the input, is not yet well understood. Although there exists some results showing the stability of graph neural networks, most take the form of an upper bound on the magnitude of change due to a perturbation in the graph topology. However, the change in the graph topology captured in existing bounds tend not to be expressed in terms of structural properties, limiting our understanding of the model robustness properties. In this work, we develop an interpretable upper bound elucidating that graph neural networks are stable to rewiring between high degree nodes. This bound and further research in bounds of similar type provide further understanding of the stability properties of graph neural networks.