mlsanityData to 7 Oct 2026

Stability Properties of Graph Neural Networks

arXiv 1905.04497 ↗First posted 11 May 2019cs.LG stat.MLcited by 125

Not on the map. Why?

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.

Key facts. Cited by 125 papers in the map (data through 7 Oct 2026). First posted on arXiv 11 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 28; 2022: 27; 2023: 24; 2024: 22; 2025: 15; 2026: 8.

125 papers.

Sort:

By area:

  1. 2022Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networkscited by 94
  2. 2021Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyondcited by 81
  3. 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 58
  4. 2024A Survey of Graph Neural Networks in Real world: Imbalance, Noise, Privacy and OOD Challengescited by 54
  5. 2022Graph Filters for Signal Processing and Machine Learning on Graphscited by 53
  6. 2021Transferability of Graph Neural Networks: an Extended Graphon Approachcited by 51
  7. 2021Transferability Properties of Graph Neural Networkscited by 42
  8. 2021p-Laplacian Based Graph Neural Networkscited by 39
  9. 2022Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networkscited by 39
  10. 2023On the Stability of Expressive Positional Encodings for Graphscited by 31
  11. 2024Rethinking Propagation for Unsupervised Graph Domain Adaptationcited by 31
  12. 2021Interpretable Stability Bounds for Spectral Graph Filterscited by 28
38 more
  1. 2023Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directionscited by 28
  2. 2023Generalized Simplicial Attention Neural Networkscited by 27
  3. 2022EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networkscited by 26
  4. 2023Convolutional Learning on Simplicial Complexescited by 26
  5. 2023Fine-grained Expressivity of Graph Neural Networkscited by 25
  6. 2021Learning by Transference: Training Graph Neural Networks on Growing Graphscited by 22
  7. 2025Relational Deep Learning: Challenges, Foundations and Next-Generation Architecturescited by 22
  8. 2021Graph-based Deep Learning for Communication Networks: A Surveycited by 21
  9. 2025Learning Efficient Positional Encodings with Graph Neural Networkscited by 21
  10. 2021Training Robust Graph Neural Networks with Topology Adaptive Edge Droppingcited by 20
  11. 2022Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspectivecited by 19
  12. 2023Explainable Brain Age Prediction using coVariance Neural Networkscited by 19
  13. 2021Stability of Graph Convolutional Neural Networks to Stochastic Perturbationscited by 18
  14. 2022coVariance Neural Networkscited by 18
  15. 2022Node-oriented Spectral Filtering for Graph Neural Networkscited by 17
  16. 2024Spatio-Spectral Graph Neural Networkscited by 17
  17. 2023Approximately Equivariant Graph Networkscited by 16
  18. 2024Generalization Bounds for Message Passing Networks on Mixture of Graphonscited by 16
  19. 2024SA-GDA: Spectral Augmentation for Graph Domain Adaptationcited by 16
  20. 2021Wide and Deep Graph Neural Network with Distributed Online Learningcited by 14
  21. 2022Rethinking Graph Neural Networks for the Graph Coloring Problemcited by 13
  22. 2022Unsupervised Optimal Power Flow Using Graph Neural Networkscited by 13
  23. 2020Synthesizing Decentralized Controllers with Graph Neural Networks and Imitation Learningcited by 12
  24. 2021Training Stable Graph Neural Networks Through Constrained Learningcited by 12
  25. 2021Space-Time Graph Neural Networkscited by 10
  26. 2021Robust Graph Neural Networks via Probabilistic Lipschitz Constraintscited by 10
  27. 2022Graph-Time Convolutional Neural Networks: Architecture and Theoretical Analysiscited by 10
  28. 2022Convolutional Learning on Multigraphscited by 10
  29. 2023Complete Neural Networks for Complete Euclidean Graphscited by 10
  30. 2021Stability of Neural Networks on Manifolds to Relative Perturbationscited by 9
  31. 2023Deep Statistical Solver for Distribution System State Estimationcited by 9
  32. 2023Geometric Graph Filters and Neural Networks: Limit Properties and Discriminability Trade-offscited by 9
  33. 2023Robust Stochastically-Descending Unrolled Networkscited by 9
  34. 2021Stability to Deformations of Manifold Filters and Manifold Neural Networkscited by 8
  35. 2021Convolutional Filtering and Neural Networks with Non Commutative Algebrascited by 8
  36. 2022Convergence of Invariant Graph Networkscited by 8
  37. 2022Graphon Pooling for Reducing Dimensionality of Signals and Convolutional Operators on Graphscited by 8
  38. 2023Unsupervised Learning of Sampling Distributions for Particle Filterscited by 8

50 most cited of 125 All 125 (JSON)