# Stability of Graph Neural Networks to Relative Perturbations

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

## Key facts

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

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

- [Modularity-Aware Graph Autoencoders for Joint Community Detection and Link Prediction](https://mlsanity.com/paper/2202.00961/) (2022)
- [Training Robust Graph Neural Networks with Topology Adaptive Edge Dropping](https://mlsanity.com/paper/2106.02892/) (2021)
- [Learning Parametrised Graph Shift Operators](https://mlsanity.com/paper/2101.10050/) (2021)
- [Wide and Deep Graph Neural Network with Distributed Online Learning](https://mlsanity.com/paper/2107.09203/) (2021)
- [Learning Stable Graph Neural Networks via Spectral Regularization](https://mlsanity.com/paper/2211.06966/) (2022)
- [Edge-Varying Fourier Graph Networks for Multivariate Time Series Forecasting](https://mlsanity.com/paper/2210.03093/) (2022)
- [Sparsifying the Update Step in Graph Neural Networks](https://mlsanity.com/paper/2109.00909/) (2021)
- [On the Trade-Off between Stability and Representational Capacity in Graph Neural Networks](https://mlsanity.com/paper/2312.02372/) (2023)
- [Demystifying Topological Message-Passing with Relational Structures: A Case Study on Oversquashing in Simplicial Message-Passing](https://mlsanity.com/paper/2506.06582/) (2025)
- [Spectral Graph Sparsification Preserves Representation Geometry in Graph Neural Networks](https://mlsanity.com/paper/2605.01136/) (2026)
- [Graph Transfer Learning via Shared Latent Geometry: Theory and Applications](https://mlsanity.com/paper/2606.00716/) (2026)

## Abstract (arXiv)

Graph neural networks (GNNs), consisting of a cascade of layers applying a graph convolution followed by a pointwise nonlinearity, have become a powerful architecture to process signals supported on graphs. Graph convolutions (and thus, GNNs), rely heavily on knowledge of the graph for operation. However, in many practical cases the GSO is not known and needs to be estimated, or might change from training time to testing time. In this paper, we are set to study the effect that a change in the underlying graph topology that supports the signal has on the output of a GNN. We prove that graph convolutions with integral Lipschitz filters lead to GNNs whose output change is bounded by the size of the relative change in the topology. Furthermore, we leverage this result to show that the main reason for the success of GNNs is that they are stable architectures capable of discriminating features on high eigenvalues, which is a feat that cannot be achieved by linear graph filters (which are either stable or discriminative, but cannot be both). Finally, we comment on the use of this result to train GNNs with increased stability and run experiments on movie recommendation systems.