# Graph Convolutional Neural Networks Sensitivity under Probabilistic Error Model

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

## Key facts

- Cited by 1 papers 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 (most cited first, 30 of 34)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [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)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filters](https://mlsanity.com/paper/1705.07664/) (2017)
- [Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective](https://mlsanity.com/paper/1906.04214/) (2019)
- [Adversarial Attack and Defense on Graph Data: A Survey](https://mlsanity.com/paper/1812.10528/) (2018)
- [Stability Properties of Graph Neural Networks](https://mlsanity.com/paper/1905.04497/) (2019)
- [Graph Adversarial Training: Dynamically Regularizing Based on Graph Structure](https://mlsanity.com/paper/1902.08226/) (2019)
- [Stability and Generalization of Graph Convolutional Neural Networks](https://mlsanity.com/paper/1905.01004/) (2019)
- [Graph Neural Networks: Architectures, Stability and Transferability](https://mlsanity.com/paper/2008.01767/) (2020)
- [Convergence and Stability of Graph Convolutional Networks on Large Random Graphs](https://mlsanity.com/paper/2006.01868/) (2020)
- [Graph signal processing for machine learning: A review and new perspectives](https://mlsanity.com/paper/2007.16061/) (2020)
- [Network Topology Inference from Spectral Templates](https://mlsanity.com/paper/1608.03008/) (2016)
- [Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbation](https://mlsanity.com/paper/2008.10715/) (2020)
- [Label Efficient Semi-Supervised Learning via Graph Filtering](https://mlsanity.com/paper/1901.09993/) (2019)
- [EdgeNets:Edge Varying Graph Neural Networks](https://mlsanity.com/paper/2001.07620/) (2020)
- [On the Transferability of Spectral Graph Filters](https://mlsanity.com/paper/1901.10524/) (2019)
- [Interpretable Stability Bounds for Spectral Graph Filters](https://mlsanity.com/paper/2102.09587/) (2021)
- [Adversarial Training Methods for Network Embedding](https://mlsanity.com/paper/1908.11514/) (2019)
- [On the Stability of Graph Convolutional Neural Networks under Edge Rewiring](https://mlsanity.com/paper/2010.13747/) (2020)
- [Learning Graphs from Smooth and Graph-Stationary Signals with Hidden Variables](https://mlsanity.com/paper/2111.05588/) (2021)
- [Graph Learning from Filtered Signals: Graph System and Diffusion Kernel Identification](https://mlsanity.com/paper/1803.02553/) (2018)
- [Stability of Graph Convolutional Neural Networks to Stochastic Perturbations](https://mlsanity.com/paper/2106.10526/) (2021)
- [GraphDefense: Towards Robust Graph Convolutional Networks](https://mlsanity.com/paper/1911.04429/) (2019)

## Built on by (most cited first, 1 of 1)

- [On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspective](https://mlsanity.com/paper/2506.01213/) (2025)

## 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.