# Robustness of Graph Neural Networks at Scale

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

## Key facts

- Cited by 100 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 52 references that are in the map.
- First posted on arXiv 26 Oct 2021.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [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)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Training Deep Nets with Sublinear Memory Cost](https://mlsanity.com/paper/1604.06174/) (2016)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [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)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [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)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [Graph Information Bottleneck](https://mlsanity.com/paper/2010.12811/) (2020)
- [Node Similarity Preserving Graph Convolutional Networks](https://mlsanity.com/paper/2011.09643/) (2020)
- [Bayesian graph convolutional neural networks for semi-supervised classification](https://mlsanity.com/paper/1811.11103/) (2018)
- [Hiding Individuals and Communities in a Social Network](https://mlsanity.com/paper/1608.00375/) (2016)
- [Towards More Practical Adversarial Attacks on Graph Neural Networks](https://mlsanity.com/paper/2006.05057/) (2020)
- [SoftSort: A Continuous Relaxation for the argsort Operator](https://mlsanity.com/paper/2006.16038/) (2020)
- [Fast Gradient Attack on Network Embedding](https://mlsanity.com/paper/1809.02797/) (2018)
- [Certifiable Robustness to Graph Perturbations](https://mlsanity.com/paper/1910.14356/) (2019)
- [Transferring Robustness for Graph Neural Network Against Poisoning Attacks](https://mlsanity.com/paper/1908.07558/) (2019)
- [Scalable Attack on Graph Data by Injecting Vicious Nodes](https://mlsanity.com/paper/2004.13825/) (2020)

## Built on by (most cited first, 30 of 100)

- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [Attacking Large Language Models with Projected Gradient Descent](https://mlsanity.com/paper/2402.09154/) (2024)
- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [A Comprehensive Survey on Deep Graph Representation Learning](https://mlsanity.com/paper/2304.05055/) (2023)
- [Empowering Graph Representation Learning with Test-Time Graph Transformation](https://mlsanity.com/paper/2210.03561/) (2022)
- [Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?](https://mlsanity.com/paper/2306.01323/) (2023)
- [Are Defenses for Graph Neural Networks Robust?](https://mlsanity.com/paper/2301.13694/) (2023)
- [Graph Machine Learning in the Era of Large Language Models (LLMs)](https://mlsanity.com/paper/2404.14928/) (2024)
- [Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directions](https://mlsanity.com/paper/2306.15427/) (2023)
- [Adversarial Robustness in Graph Neural Networks: A Hamiltonian Approach](https://mlsanity.com/paper/2310.06396/) (2023)
- [Graph Condensation: A Survey](https://mlsanity.com/paper/2401.11720/) (2024)
- [A Survey of Trustworthy Graph Learning: Reliability, Explainability, and Privacy Protection](https://mlsanity.com/paper/2205.10014/) (2022)
- [Efficient Robustness Assessment via Adversarial Spatial-Temporal Focus on Videos](https://mlsanity.com/paper/2301.00896/) (2023)
- [Revisiting Robustness in Graph Machine Learning](https://mlsanity.com/paper/2305.00851/) (2023)
- [Learning Graph Quantized Tokenizers](https://mlsanity.com/paper/2410.13798/) (2024)
- [Searching for High-Value Molecules Using Reinforcement Learning and Transformers](https://mlsanity.com/paper/2310.02902/) (2023)
- [Towards Reasonable Budget Allocation in Untargeted Graph Structure Attacks via Gradient Debias](https://mlsanity.com/paper/2304.00010/) (2023)
- [Collaborate to Adapt: Source-Free Graph Domain Adaptation via Bi-directional Adaptation](https://mlsanity.com/paper/2403.01467/) (2024)
- [GARNET: Reduced-Rank Topology Learning for Robust and Scalable Graph Neural Networks](https://mlsanity.com/paper/2201.12741/) (2022)
- [Projective Ranking-based GNN Evasion Attacks](https://mlsanity.com/paper/2202.12993/) (2022)
- [A Unified Framework of Graph Information Bottleneck for Robustness and Membership Privacy](https://mlsanity.com/paper/2306.08604/) (2023)
- [Adversarial Inter-Group Link Injection Degrades the Fairness of Graph Neural Networks](https://mlsanity.com/paper/2209.05957/) (2022)
- [Learning on Graphs with Large Language Models(LLMs): A Deep Dive into Model Robustness](https://mlsanity.com/paper/2407.12068/) (2024)
- [Recent Advances in Reliable Deep Graph Learning: Inherent Noise, Distribution Shift, and Adversarial Attack](https://mlsanity.com/paper/2202.07114/) (2022)
- [Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networks](https://mlsanity.com/paper/2301.02039/) (2023)
- [Verifying message-passing neural networks via topology-based bounds tightening](https://mlsanity.com/paper/2402.13937/) (2024)
- [Matcha: Mitigating Graph Structure Shifts with Test-Time Adaptation](https://mlsanity.com/paper/2410.06976/) (2024)
- [Fundamental Limits in Formal Verification of Message-Passing Neural Networks](https://mlsanity.com/paper/2206.05070/) (2022)
- [A.I. Robustness: a Human-Centered Perspective on Technological Challenges and Opportunities](https://mlsanity.com/paper/2210.08906/) (2022)
- [Coupling Graph Neural Networks with Fractional Order Continuous Dynamics: A Robustness Study](https://mlsanity.com/paper/2401.04331/) (2024)

## Abstract (arXiv)

Graph Neural Networks (GNNs) are increasingly important given their popularity and the diversity of applications. Yet, existing studies of their vulnerability to adversarial attacks rely on relatively small graphs. We address this gap and study how to attack and defend GNNs at scale. We propose two sparsity-aware first-order optimization attacks that maintain an efficient representation despite optimizing over a number of parameters which is quadratic in the number of nodes. We show that common surrogate losses are not well-suited for global attacks on GNNs. Our alternatives can double the attack strength. Moreover, to improve GNNs' reliability we design a robust aggregation function, Soft Median, resulting in an effective defense at all scales. We evaluate our attacks and defense with standard GNNs on graphs more than 100 times larger compared to previous work. We even scale one order of magnitude further by extending our techniques to a scalable GNN.