mlsanityData to 7 Oct 2026

Robustness of Graph Neural Networks at Scale

arXiv 2110.14038 ↗First posted 26 Oct 2021cs.LG stat.MLcited by 100

Not on the map. Why?

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.

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

Builds on

36 of 52 references.

References · 36

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2016Towards Evaluating the Robustness of Neural Networkscited by 2,976
  3. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  4. 2019Simplifying Graph Convolutional Networkscited by 1,470
  5. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  6. 2018Pitfalls of Graph Neural Network Evaluationcited by 994
  7. 2016Training Deep Nets with Sublinear Memory Costcited by 825
  8. 2018FastGCN: Fast Learning with Graph Convolutional Networks via Importance Samplingcited by 583
  9. 2019Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networkscited by 540
  10. 2018Efficient Neural Network Robustness Certification with General Activation Functionscited by 439
  11. 2019Diffusion Improves Graph Learningcited by 414
  12. 2018Adversarial Attacks on Neural Networks for Graph Datacited by 395
24 more
  1. 2017Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Rankingcited by 332
  2. 2018Adversarial Attack on Graph Structured Datacited by 300
  3. 2019Adversarial Attacks on Graph Neural Networks via Meta Learningcited by 261
  4. 2018Towards Fast Computation of Certified Robustness for ReLU Networkscited by 254
  5. 2015Coordinate Descent Algorithmscited by 218
  6. 2019Topology Attack and Defense for Graph Neural Networks: An Optimization Perspectivecited by 196
  7. 2020GNNGuard: Defending Graph Neural Networks against Adversarial Attackscited by 195
  8. 2020Scaling Graph Neural Networks with Approximate PageRankcited by 174
  9. 2020Graph Information Bottleneckcited by 168
  10. 2020Node Similarity Preserving Graph Convolutional Networkscited by 112
  11. 2018Bayesian graph convolutional neural networks for semi-supervised classificationcited by 88
  12. 2016Hiding Individuals and Communities in a Social Networkcited by 77
  13. 2020Towards More Practical Adversarial Attacks on Graph Neural Networkscited by 76
  14. 2020SoftSort: A Continuous Relaxation for the argsort Operatorcited by 66
  15. 2018Fast Gradient Attack on Network Embeddingcited by 65
  16. 2019Certifiable Robustness to Graph Perturbationscited by 62
  17. 2019Transferring Robustness for Graph Neural Network Against Poisoning Attackscited by 58
  18. 2020Scalable Attack on Graph Data by Injecting Vicious Nodescited by 50
  19. 2020Reliable Graph Neural Networks via Robust Aggregationcited by 43
  20. 2020Adversarial Attack on Large Scale Graphcited by 39
  21. 2021Understanding Structural Vulnerability in Graph Convolutional Networkscited by 37
  22. 2019Provably Robust Boosted Decision Stumps and Trees against Adversarial Attackscited by 26
  23. 2020MGA: Momentum Gradient Attack on Networkcited by 10
  24. 2020Scalable Adversarial Attack on Graph Neural Networks with Alternating Direction Method of Multiplierscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 16; 2023: 22; 2024: 32; 2025: 20; 2026: 10.

100 papers.

Sort:

By area:

  1. 2022A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainabilitycited by 118
  2. 2024Attacking Large Language Models with Projected Gradient Descentcited by 91
  3. 2022Trustworthy Graph Neural Networks: Aspects, Methods and Trendscited by 88
  4. 2023A Comprehensive Survey on Deep Graph Representation Learningcited by 72
  5. 2022Empowering Graph Representation Learning with Test-Time Graph Transformationcited by 66
  6. 2023Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?cited by 41
  7. 2023Are Defenses for Graph Neural Networks Robust?cited by 38
  8. 2024Graph Machine Learning in the Era of Large Language Models (LLMs)cited by 33
  9. 2023Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directionscited by 28
  10. 2023Adversarial Robustness in Graph Neural Networks: A Hamiltonian Approachcited by 24
  11. 2024Graph Condensation: A Surveycited by 23
  12. 2022A Survey of Trustworthy Graph Learning: Reliability, Explainability, and Privacy Protectioncited by 20
38 more
  1. 2023Efficient Robustness Assessment via Adversarial Spatial-Temporal Focus on Videoscited by 20
  2. 2023Revisiting Robustness in Graph Machine Learningcited by 19
  3. 2024Learning Graph Quantized Tokenizerscited by 19
  4. 2023Searching for High-Value Molecules Using Reinforcement Learning and Transformerscited by 18
  5. 2023Towards Reasonable Budget Allocation in Untargeted Graph Structure Attacks via Gradient Debiascited by 16
  6. 2024Collaborate to Adapt: Source-Free Graph Domain Adaptation via Bi-directional Adaptationcited by 15
  7. 2022GARNET: Reduced-Rank Topology Learning for Robust and Scalable Graph Neural Networkscited by 14
  8. 2022Projective Ranking-based GNN Evasion Attackscited by 14
  9. 2023A Unified Framework of Graph Information Bottleneck for Robustness and Membership Privacycited by 14
  10. 2022Adversarial Inter-Group Link Injection Degrades the Fairness of Graph Neural Networkscited by 12
  11. 2024Learning on Graphs with Large Language Models(LLMs): A Deep Dive into Model Robustnesscited by 11
  12. 2022Recent Advances in Reliable Deep Graph Learning: Inherent Noise, Distribution Shift, and Adversarial Attackcited by 10
  13. 2023Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networkscited by 10
  14. 2024Verifying message-passing neural networks via topology-based bounds tighteningcited by 10
  15. 2024Matcha: Mitigating Graph Structure Shifts with Test-Time Adaptationcited by 10
  16. 2022Fundamental Limits in Formal Verification of Message-Passing Neural Networkscited by 9
  17. 2024Coupling Graph Neural Networks with Fractional Order Continuous Dynamics: A Robustness Studycited by 9
  18. 2024Intruding with Words: Towards Understanding Graph Injection Attacks at the Text Levelcited by 9
  19. 2024Collaboration! Towards Robust Neural Methods for Routing Problemscited by 9
  20. 2022Revisiting Adversarial Attacks on Graph Neural Networks for Graph Classificationcited by 8
  21. 2022A.I. Robustness: a Human-Centered Perspective on Technological Challenges and Opportunitiescited by 8
  22. 2023Simple and Efficient Partial Graph Adversarial Attack: A New Perspectivecited by 8
  23. 2023Robust Graph Neural Networks via Unbiased Aggregationcited by 8
  24. 2024RobGC: Towards Robust Graph Condensationcited by 8
  25. 2024GC4NC: A Benchmark Framework for Graph Condensation on Node Classification with New Insightscited by 7
  26. 2025Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapsecited by 7
  27. 2024Minimum Topology Attacks for Graph Neural Networkscited by 6
  28. 2023Certifiably Robust Graph Contrastive Learningcited by 5
  29. 2024Explainable Graph Neural Networks Under Firecited by 5
  30. 2024SafePowerGraph: Safety-aware Evaluation of Graph Neural Networks for Transmission Power Gridscited by 5
  31. 2024SORSA: Singular Values and Orthonormal Regularized Singular Vectors Adaptation of Large Language Modelscited by 5
  32. 2024ProTransformer: Robustify Transformers via Plug-and-Play Paradigmcited by 5
  33. 2025TrustGLM: Evaluating the Robustness of GraphLLMs Against Prompt, Text, and Structure Attackscited by 5
  34. 2022Toward Enhanced Robustness in Unsupervised Graph Representation Learning: A Graph Information Bottleneck Perspectivecited by 4
  35. 2022Robust Graph Neural Networks using Weighted Graph Laplaciancited by 4
  36. 2023IDEA: Invariant Defense for Graph Adversarial Robustnesscited by 4
  37. 2023Adversarial Attacks on Fairness of Graph Neural Networkscited by 4
  38. 2024Gradient Inversion Attack on Graph Neural Networkscited by 4

50 most cited of 100 All 100 (JSON)