mlsanityData to 14 Oct 2026

Graph Convolutional Neural Networks Sensitivity under Probabilistic Error Model

arXiv 2203.07831 ↗First posted 15 Mar 2022stat.ML cs.LGcited by 1

Not on the map. Why?

Abstract (arXiv)

Graph Neural Networks (GNNs), particularly Graph Convolutional Neural Networks (GCNNs), have emerged as pivotal instruments in machine learning and signal processing for processing graph-structured data. This paper proposes an analysis framework to investigate the sensitivity of GCNNs to probabilistic graph perturbations, directly impacting the graph shift operator (GSO). Our study establishes tight expected GSO error bounds, which are explicitly linked to the error model parameters, and reveals a linear relationship between GSO perturbations and the resulting output differences at each layer of GCNNs. This linearity demonstrates that a single-layer GCNN maintains stability under graph edge perturbations, provided that the GSO errors remain bounded, regardless of the perturbation scale. For multilayer GCNNs, the dependency of system's output difference on GSO perturbations is shown to be a recursion of linearity. Finally, we exemplify the framework with the Graph Isomorphism Network (GIN) and Simple Graph Convolution Network (SGCN). Experiments validate our theoretical derivations and the effectiveness of our approach.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 34 of its 60 references that are in the map. First posted on arXiv 15 Mar 2022.

Builds on

34 of 60 references.

References · 34

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2018How Powerful are Graph Neural Networks?cited by 4,393
  4. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,919
  5. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  6. 2019Simplifying Graph Convolutional Networkscited by 1,477
  7. 2016Geometric deep learning: going beyond Euclidean datacited by 1,048
  8. 2018Adversarial Attacks on Neural Networks for Graph Datacited by 397
  9. 2018Adversarial Attack on Graph Structured Datacited by 301
  10. 2017CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filterscited by 203
  11. 2019Topology Attack and Defense for Graph Neural Networks: An Optimization Perspectivecited by 196
  12. 2018Adversarial Attack and Defense on Graph Data: A Surveycited by 167
22 more
  1. 2019Stability Properties of Graph Neural Networkscited by 127
  2. 2019Graph Adversarial Training: Dynamically Regularizing Based on Graph Structurecited by 93
  3. 2019Stability and Generalization of Graph Convolutional Neural Networkscited by 81
  4. 2020Graph Neural Networks: Architectures, Stability and Transferabilitycited by 80
  5. 2020Convergence and Stability of Graph Convolutional Networks on Large Random Graphscited by 76
  6. 2020Graph signal processing for machine learning: A review and new perspectivescited by 73
  7. 2016Network Topology Inference from Spectral Templatescited by 58
  8. 2020Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbationcited by 57
  9. 2019Label Efficient Semi-Supervised Learning via Graph Filteringcited by 46
  10. 2020EdgeNets:Edge Varying Graph Neural Networkscited by 36
  11. 2019On the Transferability of Spectral Graph Filterscited by 28
  12. 2021Interpretable Stability Bounds for Spectral Graph Filterscited by 28
  13. 2019Adversarial Training Methods for Network Embeddingcited by 26
  14. 2020On the Stability of Graph Convolutional Neural Networks under Edge Rewiringcited by 25
  15. 2021Learning Graphs from Smooth and Graph-Stationary Signals with Hidden Variablescited by 20
  16. 2018Graph Learning from Filtered Signals: Graph System and Diffusion Kernel Identificationcited by 18
  17. 2021Stability of Graph Convolutional Neural Networks to Stochastic Perturbationscited by 18
  18. 2019GraphDefense: Towards Robust Graph Convolutional Networkscited by 17
  19. 2021Graph Structural Attack by Perturbing Spectral Distancecited by 16
  20. 2018Advances in Distributed Graph Filteringcited by 13
  21. 2020Kernel-based Graph Learning from Smooth Signals: A Functional Viewpointcited by 12
  22. 2020Wasserstein-based Graph Alignmentcited by 10

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspectivecited by 0