# Revisiting Robustness in Graph Machine Learning

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 64 references that are in the map.
- First posted on arXiv 1 May 2023.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [Distillation as a Defense to Adversarial Perturbations against Deep Neural Networks](https://mlsanity.com/paper/1511.04508/) (2015)
- [Adversarial Examples for Evaluating Reading Comprehension Systems](https://mlsanity.com/paper/1707.07328/) (2017)
- [On Adaptive Attacks to Adversarial Example Defenses](https://mlsanity.com/paper/2002.08347/) (2020)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs](https://mlsanity.com/paper/2103.09430/) (2021)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [Unsolved Problems in ML Safety](https://mlsanity.com/paper/2109.13916/) (2021)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [Combining Label Propagation and Simple Models Out-performs Graph Neural Networks](https://mlsanity.com/paper/2010.13993/) (2020)
- [Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective](https://mlsanity.com/paper/1906.04214/) (2019)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Robustness of Graph Neural Networks at Scale](https://mlsanity.com/paper/2110.14038/) (2021)
- [Hiding Individuals and Communities in a Social Network](https://mlsanity.com/paper/1608.00375/) (2016)
- [Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization](https://mlsanity.com/paper/2102.06966/) (2021)
- [Fast Gradient Attack on Network Embedding](https://mlsanity.com/paper/1809.02797/) (2018)
- [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)
- [Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More](https://mlsanity.com/paper/2008.12952/) (2020)

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

- [Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directions](https://mlsanity.com/paper/2306.15427/) (2023)
- [Can Large Language Models Improve the Adversarial Robustness of Graph Neural Networks?](https://mlsanity.com/paper/2408.08685/) (2024)
- [Optimality of Message-Passing Architectures for Sparse Graphs](https://mlsanity.com/paper/2305.10391/) (2023)
- [Hierarchical Randomized Smoothing](https://mlsanity.com/paper/2310.16221/) (2023)
- [Bounding the Expected Robustness of Graph Neural Networks Subject to Node Feature Attacks](https://mlsanity.com/paper/2404.17947/) (2024)
- [Collaboration! Towards Robust Neural Methods for Routing Problems](https://mlsanity.com/paper/2410.04968/) (2024)
- [Assessing Robustness via Score-Based Adversarial Image Generation](https://mlsanity.com/paper/2310.04285/) (2023)
- [Exact Certification of (Graph) Neural Networks Against Label Poisoning](https://mlsanity.com/paper/2412.00537/) (2024)
- [Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attacks](https://mlsanity.com/paper/2407.10867/) (2024)
- [IDEA: Invariant Defense for Graph Adversarial Robustness](https://mlsanity.com/paper/2305.15792/) (2023)
- [On the Adversarial Robustness of Graph Contrastive Learning Methods](https://mlsanity.com/paper/2311.17853/) (2023)
- [Discrete Randomized Smoothing Meets Quantum Computing](https://mlsanity.com/paper/2408.00895/) (2024)
- [A Cognac Shot To Forget Bad Memories: Corrective Unlearning for Graph Neural Networks](https://mlsanity.com/paper/2412.00789/) (2024)
- [Expressivity of Graph Neural Networks Through the Lens of Adversarial Robustness](https://mlsanity.com/paper/2308.08173/) (2023)
- [Explaining the Power of Topological Data Analysis in Graph Machine Learning](https://mlsanity.com/paper/2401.04250/) (2024)
- [Adversarial Robustness of Graph Transformers](https://mlsanity.com/paper/2407.11764/) (2024)
- [Poisoning × Evasion: Symbiotic Adversarial Robustness for Graph Neural Networks](https://mlsanity.com/paper/2312.05502/) (2023)
- [AHSG: Adversarial Attack on High-level Semantics in Graph Neural Networks](https://mlsanity.com/paper/2412.07468/) (2024)
- [Target-Aware Interaction-Guided Reinforcement Learning for Black-Box Node Injection Attacks on Graph Neural Networks](https://mlsanity.com/paper/2607.04091/) (2026)

## Abstract (arXiv)

Many works show that node-level predictions of Graph Neural Networks (GNNs) are unrobust to small, often termed adversarial, changes to the graph structure. However, because manual inspection of a graph is difficult, it is unclear if the studied perturbations always preserve a core assumption of adversarial examples: that of unchanged semantic content. To address this problem, we introduce a more principled notion of an adversarial graph, which is aware of semantic content change. Using Contextual Stochastic Block Models (CSBMs) and real-world graphs, our results uncover: i) for a majority of nodes the prevalent perturbation models include a large fraction of perturbed graphs violating the unchanged semantics assumption; ii) surprisingly, all assessed GNNs show over-robustness - that is robustness beyond the point of semantic change. We find this to be a complementary phenomenon to adversarial examples and show that including the label-structure of the training graph into the inference process of GNNs significantly reduces over-robustness, while having a positive effect on test accuracy and adversarial robustness. Theoretically, leveraging our new semantics-aware notion of robustness, we prove that there is no robustness-accuracy tradeoff for inductively classifying a newly added node.