# Stability of Graph Convolutional Neural Networks to Stochastic Perturbations arXiv: https://arxiv.org/abs/2106.10526 ยท HTML: https://mlsanity.com/paper/2106.10526/ ## Key facts - Cited by 18 papers in the map (data through 14 Oct 2026). - Builds on 24 of its 47 references that are in the map. - First posted on arXiv 19 Jun 2021. ## Builds on (most cited first, 24 of 24) - [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014) - [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019) - [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016) - [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018) - [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017) - [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018) - [Session-based Recommendation with Graph Neural Networks](https://mlsanity.com/paper/1811.00855/) (2018) - [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018) - [Stability Properties of Graph Neural Networks](https://mlsanity.com/paper/1905.04497/) (2019) - [Convolutional Neural Network Architectures for Signals Supported on Graphs](https://mlsanity.com/paper/1805.00165/) (2018) - [Transferability of Spectral Graph Convolutional Neural Networks](https://mlsanity.com/paper/1907.12972/) (2019) - [Optimal Wireless Resource Allocation with Random Edge Graph Neural Networks](https://mlsanity.com/paper/1909.01865/) (2019) - [Graph Neural Networks: Architectures, Stability and Transferability](https://mlsanity.com/paper/2008.01767/) (2020) - [Graphs, Convolutions, and Neural Networks: From Graph Filters to Graph Neural Networks](https://mlsanity.com/paper/2003.03777/) (2020) - [Learning Decentralized Controllers for Robot Swarms with Graph Neural Networks](https://mlsanity.com/paper/1903.10527/) (2019) - [Certifiable Robustness to Graph Perturbations](https://mlsanity.com/paper/1910.14356/) (2019) - [Certifiable Robustness and Robust Training for Graph Convolutional Networks](https://mlsanity.com/paper/1906.12269/) (2019) - [Graph Convolutional Neural Networks via Scattering](https://mlsanity.com/paper/1804.00099/) (2018) - [Diffusion Scattering Transforms on Graphs](https://mlsanity.com/paper/1806.08829/) (2018) - [Latent Space Model for Road Networks to Predict Time-Varying Traffic](https://mlsanity.com/paper/1602.04301/) (2016) - [Advances in Distributed Graph Filtering](https://mlsanity.com/paper/1808.03004/) (2018) - [Resource Allocation via Graph Neural Networks in Free Space Optical Fronthaul Networks](https://mlsanity.com/paper/2006.15005/) (2020) - [Filtering Random Graph Processes Over Random Time-Varying Graphs](https://mlsanity.com/paper/1705.00442/) (2017) - [Wide and Deep Graph Neural Networks with Distributed Online Learning](https://mlsanity.com/paper/2006.06376/) (2020) ## Built on by (most cited first, 18 of 18) - [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022) - [Financial Fraud Detection using Quantum Graph Neural Networks](https://mlsanity.com/paper/2309.01127/) (2023) - [Wide and Deep Graph Neural Network with Distributed Online Learning](https://mlsanity.com/paper/2107.09203/) (2021) - [Training Stable Graph Neural Networks Through Constrained Learning](https://mlsanity.com/paper/2110.03576/) (2021) - [Graph-Time Convolutional Neural Networks: Architecture and Theoretical Analysis](https://mlsanity.com/paper/2206.15174/) (2022) - [Deep Statistical Solver for Distribution System State Estimation](https://mlsanity.com/paper/2301.01835/) (2023) - [Decentralized Channel Management in WLANs with Graph Neural Networks](https://mlsanity.com/paper/2210.16949/) (2022) - [Sparse Covariance Neural Networks](https://mlsanity.com/paper/2410.01669/) (2024) - [On the Prediction Instability of Graph Neural Networks](https://mlsanity.com/paper/2205.10070/) (2022) - [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) - [Learning Stable Graph Neural Networks via Spectral Regularization](https://mlsanity.com/paper/2211.06966/) (2022) - [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) - [GKNet: Graph Kalman Filtering and Model Inference via Model-based Deep Learning](https://mlsanity.com/paper/2506.22004/) (2025) - [Graph Convolutional Neural Networks Sensitivity under Probabilistic Error Model](https://mlsanity.com/paper/2203.07831/) (2022) - [On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspective](https://mlsanity.com/paper/2506.01213/) (2025) ## Abstract (arXiv) Graph convolutional neural networks (GCNNs) are nonlinear processing tools to learn representations from network data. A key property of GCNNs is their stability to graph perturbations. Current analysis considers deterministic perturbations but fails to provide relevant insights when topological changes are random. This paper investigates the stability of GCNNs to stochastic graph perturbations induced by link losses. In particular, it proves the expected output difference between the GCNN over random perturbed graphs and the GCNN over the nominal graph is upper bounded by a factor that is linear in the link loss probability. We perform the stability analysis in the graph spectral domain such that the result holds uniformly for any graph. This result also shows the role of the nonlinearity and the architecture width and depth, and allows identifying handle to improve the GCNN robustness. Numerical simulations on source localization and robot swarm control corroborate our theoretical findings.