# Bounding the Expected Robustness of Graph Neural Networks Subject to Node Feature Attacks

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 58 references that are in the map.
- First posted on arXiv 27 Apr 2024.

## Builds on (most cited first, 30 of 41)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Weight Normalization: A Simple Reparameterization to Accelerate Training of Deep Neural Networks](https://mlsanity.com/paper/1602.07868/) (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)
- [Parseval Networks: Improving Robustness to Adversarial Examples](https://mlsanity.com/paper/1704.08847/) (2017)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [A Fair Comparison of Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/1912.09893/) (2019)
- [Molecular Graph Convolutions: Moving Beyond Fingerprints](https://mlsanity.com/paper/1603.00856/) (2016)
- [A Comprehensive Survey on Graph Anomaly Detection with Deep Learning](https://mlsanity.com/paper/2106.07178/) (2021)
- [Sorting out Lipschitz function approximation](https://mlsanity.com/paper/1811.05381/) (2018)
- [Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective](https://mlsanity.com/paper/1906.04214/) (2019)
- [GNNGuard: Defending Graph Neural Networks against Adversarial Attacks](https://mlsanity.com/paper/2006.08149/) (2020)
- [Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach](https://mlsanity.com/paper/1801.10578/) (2018)
- [Graph Adversarial Training: Dynamically Regularizing Based on Graph Structure](https://mlsanity.com/paper/1902.08226/) (2019)
- [TDGIA:Effective Injection Attacks on Graph Neural Networks](https://mlsanity.com/paper/2106.06663/) (2021)
- [Elastic Graph Neural Networks](https://mlsanity.com/paper/2107.06996/) (2021)
- [Certifiable Robustness to Graph Perturbations](https://mlsanity.com/paper/1910.14356/) (2019)
- [Understanding and Improving Graph Injection Attack by Promoting Unnoticeability](https://mlsanity.com/paper/2202.08057/) (2022)
- [Certifiable Robustness and Robust Training for Graph Convolutional Networks](https://mlsanity.com/paper/1906.12269/) (2019)
- [Transferring Robustness for Graph Neural Network Against Poisoning Attacks](https://mlsanity.com/paper/1908.07558/) (2019)
- [Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More](https://mlsanity.com/paper/2008.12952/) (2020)
- [Single Node Injection Attack against Graph Neural Networks](https://mlsanity.com/paper/2108.13049/) (2021)

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

- [CEGA: A Cost-Effective Approach for Graph-Based Model Extraction and Acquisition](https://mlsanity.com/paper/2506.17709/) (2025)
- [Unitary convolutions for learning on graphs and groups](https://mlsanity.com/paper/2410.05499/) (2024)
- [Graph Neural Network Generalization with Gaussian Mixture Model Based Augmentation](https://mlsanity.com/paper/2411.08638/) (2024)
- [Robustness in Text-Attributed Graph Learning: Insights, Trade-offs, and New Defenses](https://mlsanity.com/paper/2510.17185/) (2025)
- [If You Want to Be Robust, Be Wary of Initialization](https://mlsanity.com/paper/2510.22652/) (2025)
- [Which Graph Shift Operator? A Spectral Answer to an Empirical Question](https://mlsanity.com/paper/2602.06557/) (2026)
- [Certifying Robustness of Graph Convolutional Networks for Node Perturbation with Polyhedra Abstract Interpretation](https://mlsanity.com/paper/2405.08645/) (2024)
- [Enhancing Graph Classification Robustness with Singular Pooling](https://mlsanity.com/paper/2510.22643/) (2025)
- [Adversarial Graph Neural Network Benchmarks: Towards Practical and Fair Evaluation](https://mlsanity.com/paper/2605.05534/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have demonstrated state-of-the-art performance in various graph representation learning tasks. Recently, studies revealed their vulnerability to adversarial attacks. In this work, we theoretically define the concept of expected robustness in the context of attributed graphs and relate it to the classical definition of adversarial robustness in the graph representation learning literature. Our definition allows us to derive an upper bound of the expected robustness of Graph Convolutional Networks (GCNs) and Graph Isomorphism Networks subject to node feature attacks. Building on these findings, we connect the expected robustness of GNNs to the orthonormality of their weight matrices and consequently propose an attack-independent, more robust variant of the GCN, called the Graph Convolutional Orthonormal Robust Networks (GCORNs). We further introduce a probabilistic method to estimate the expected robustness, which allows us to evaluate the effectiveness of GCORN on several real-world datasets. Experimental experiments showed that GCORN outperforms available defense methods. Our code is publicly available at: hrefhttps://github.com/Sennadir/GCORNhttps://github.com/Sennadir/GCORN.