mlsanityData to 7 Oct 2026

Stability of Graph Convolutional Neural Networks to Stochastic Perturbations

arXiv 2106.10526 ↗First posted 19 Jun 2021cs.LG eess.SPcited by 18

Not on the map. Why?

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.

Key facts. Cited by 18 papers in the map (data through 7 Oct 2026). Builds on 24 of its 47 references that are in the map. First posted on arXiv 19 Jun 2021.

Builds on

24 of 47 references.

References · 24

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  3. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  4. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  5. 2017Graph Signal Processing: Overview, Challenges and Applicationscited by 409
  6. 2018Adversarial Attacks on Neural Networks for Graph Datacited by 395
  7. 2018Session-based Recommendation with Graph Neural Networkscited by 312
  8. 2018Adversarial Attack on Graph Structured Datacited by 300
  9. 2019Stability Properties of Graph Neural Networkscited by 125
  10. 2018Convolutional Neural Network Architectures for Signals Supported on Graphscited by 94
  11. 2019Transferability of Spectral Graph Convolutional Neural Networkscited by 90
  12. 2019Optimal Wireless Resource Allocation with Random Edge Graph Neural Networkscited by 90
12 more
  1. 2020Graph Neural Networks: Architectures, Stability and Transferabilitycited by 79
  2. 2020Graphs, Convolutions, and Neural Networks: From Graph Filters to Graph Neural Networkscited by 73
  3. 2019Learning Decentralized Controllers for Robot Swarms with Graph Neural Networkscited by 62
  4. 2019Certifiable Robustness to Graph Perturbationscited by 62
  5. 2019Certifiable Robustness and Robust Training for Graph Convolutional Networkscited by 59
  6. 2018Graph Convolutional Neural Networks via Scatteringcited by 46
  7. 2018Diffusion Scattering Transforms on Graphscited by 43
  8. 2016Latent Space Model for Road Networks to Predict Time-Varying Trafficcited by 22
  9. 2018Advances in Distributed Graph Filteringcited by 13
  10. 2020Resource Allocation via Graph Neural Networks in Free Space Optical Fronthaul Networkscited by 11
  11. 2017Filtering Random Graph Processes Over Random Time-Varying Graphscited by 8
  12. 2020Wide and Deep Graph Neural Networks with Distributed Online Learningcited by 7

Built on by

Cited by year

Citing papers per year: 2021: 3; 2022: 8; 2023: 4; 2024: 1; 2025: 2.

18 papers.

Sort:

  1. 2022Graph Filters for Signal Processing and Machine Learning on Graphscited by 53
  2. 2023Financial Fraud Detection using Quantum Graph Neural Networkscited by 35
  3. 2021Wide and Deep Graph Neural Network with Distributed Online Learningcited by 14
  4. 2021Training Stable Graph Neural Networks Through Constrained Learningcited by 12
  5. 2022Graph-Time Convolutional Neural Networks: Architecture and Theoretical Analysiscited by 10
  6. 2023Deep Statistical Solver for Distribution System State Estimationcited by 9
  7. 2022Decentralized Channel Management in WLANs with Graph Neural Networkscited by 7
  8. 2022On the Prediction Instability of Graph Neural Networkscited by 6
  9. 2024Sparse Covariance Neural Networkscited by 6
  10. 2021On the Stability of Low Pass Graph Filter With a Large Number of Edge Rewirescited by 5
  11. 2022Learning Stochastic Graph Neural Networks with Constrained Variancecited by 5
  12. 2022Space-Time Graph Neural Networks with Stochastic Graph Perturbationscited by 5
6 more
  1. 2022Learning Stable Graph Neural Networks via Spectral Regularizationcited by 4
  2. 2023Limitless stability for Graph Convolutional Networkscited by 2
  3. 2023On the Trade-Off between Stability and Representational Capacity in Graph Neural Networkscited by 2
  4. 2025GKNet: Graph Kalman Filtering and Model Inference via Model-based Deep Learningcited by 2
  5. 2022Graph Convolutional Neural Networks Sensitivity under Probabilistic Error Modelcited by 1
  6. 2025On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspectivecited by 0