# Stability Properties of Graph Neural Networks

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

## Key facts

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

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

- [Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks](https://mlsanity.com/paper/2203.00199/) (2022)
- [Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond](https://mlsanity.com/paper/2101.05510/) (2021)
- [Generalization Analysis of Message Passing Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2202.00645/) (2022)
- [A Survey of Graph Neural Networks in Real world: Imbalance, Noise, Privacy and OOD Challenges](https://mlsanity.com/paper/2403.04468/) (2024)
- [Transferability of Graph Neural Networks: an Extended Graphon Approach](https://mlsanity.com/paper/2109.10096/) (2021)
- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [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)
- [p-Laplacian Based Graph Neural Networks](https://mlsanity.com/paper/2111.07337/) (2021)
- [On the Stability of Expressive Positional Encodings for Graphs](https://mlsanity.com/paper/2310.02579/) (2023)
- [Rethinking Propagation for Unsupervised Graph Domain Adaptation](https://mlsanity.com/paper/2402.05660/) (2024)
- [Interpretable Stability Bounds for Spectral Graph Filters](https://mlsanity.com/paper/2102.09587/) (2021)
- [Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directions](https://mlsanity.com/paper/2306.15427/) (2023)
- [Convolutional Learning on Simplicial Complexes](https://mlsanity.com/paper/2301.11163/) (2023)
- [Generalized Simplicial Attention Neural Networks](https://mlsanity.com/paper/2309.02138/) (2023)
- [EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networks](https://mlsanity.com/paper/2205.13892/) (2022)
- [Fine-grained Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2306.03698/) (2023)
- [Learning Efficient Positional Encodings with Graph Neural Networks](https://mlsanity.com/paper/2502.01122/) (2025)
- [Relational Deep Learning: Challenges, Foundations and Next-Generation Architectures](https://mlsanity.com/paper/2506.16654/) (2025)
- [Learning by Transference: Training Graph Neural Networks on Growing Graphs](https://mlsanity.com/paper/2106.03693/) (2021)
- [Graph-based Deep Learning for Communication Networks: A Survey](https://mlsanity.com/paper/2106.02533/) (2021)
- [Training Robust Graph Neural Networks with Topology Adaptive Edge Dropping](https://mlsanity.com/paper/2106.02892/) (2021)
- [coVariance Neural Networks](https://mlsanity.com/paper/2205.15856/) (2022)
- [Explainable Brain Age Prediction using coVariance Neural Networks](https://mlsanity.com/paper/2305.18370/) (2023)
- [Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspective](https://mlsanity.com/paper/2207.11311/) (2022)
- [Stability of Graph Convolutional Neural Networks to Stochastic Perturbations](https://mlsanity.com/paper/2106.10526/) (2021)
- [Node-oriented Spectral Filtering for Graph Neural Networks](https://mlsanity.com/paper/2212.03654/) (2022)
- [Generalization Bounds for Message Passing Networks on Mixture of Graphons](https://mlsanity.com/paper/2404.03473/) (2024)
- [Spatio-Spectral Graph Neural Networks](https://mlsanity.com/paper/2405.19121/) (2024)
- [Approximately Equivariant Graph Networks](https://mlsanity.com/paper/2308.10436/) (2023)

## Abstract (arXiv)

Graph neural networks (GNNs) have emerged as a powerful tool for nonlinear processing of graph signals, exhibiting success in recommender systems, power outage prediction, and motion planning, among others. GNNs consists of a cascade of layers, each of which applies a graph convolution, followed by a pointwise nonlinearity. In this work, we study the impact that changes in the underlying topology have on the output of the GNN. First, we show that GNNs are permutation equivariant, which implies that they effectively exploit internal symmetries of the underlying topology. Then, we prove that graph convolutions with integral Lipschitz filters, in combination with the frequency mixing effect of the corresponding nonlinearities, yields an architecture that is both stable to small changes in the underlying topology and discriminative of information located at high frequencies. These are two properties that cannot simultaneously hold when using only linear graph filters, which are either discriminative or stable, thus explaining the superior performance of GNNs.