mlsanityData to 7 Oct 2026

Towards More Practical Adversarial Attacks on Graph Neural Networks

arXiv 2006.05057 ↗First posted 9 Jun 2020cs.LG stat.MLcited by 76

Not on the map. Why?

Abstract (arXiv)

We study the black-box attacks on graph neural networks (GNNs) under a novel and realistic constraint: attackers have access to only a subset of nodes in the network, and they can only attack a small number of them. A node selection step is essential under this setup. We demonstrate that the structural inductive biases of GNN models can be an effective source for this type of attacks. Specifically, by exploiting the connection between the backward propagation of GNNs and random walks, we show that the common gradient-based white-box attacks can be generalized to the black-box setting via the connection between the gradient and an importance score similar to PageRank. In practice, we find attacks based on this importance score indeed increase the classification loss by a large margin, but they fail to significantly increase the mis-classification rate. Our theoretical and empirical analyses suggest that there is a discrepancy between the loss and mis-classification rate, as the latter presents a diminishing-return pattern when the number of attacked nodes increases. Therefore, we propose a greedy procedure to correct the importance score that takes into account of the diminishing-return pattern. Experimental results show that the proposed procedure can significantly increase the mis-classification rate of common GNNs on real-world data without access to model parameters nor predictions.

Key facts. Cited by 76 papers in the map (data through 7 Oct 2026). First posted on arXiv 9 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 16; 2022: 13; 2023: 15; 2024: 16; 2025: 11; 2026: 5.

76 papers.

Sort:

By area:

  1. 2022A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainabilitycited by 118
  2. 2021Robustness of Graph Neural Networks at Scalecited by 100
  3. 2021Model Stealing Attacks Against Inductive Graph Neural Networkscited by 50
  4. 2021Enhancing Self-supervised Video Representation Learning via Multi-level Feature Optimizationcited by 27
  5. 2022Model Inversion Attacks against Graph Neural Networkscited by 26
  6. 2021How does Heterophily Impact the Robustness of Graph Neural Networks? Theoretical Connections and Practical Implicationscited by 21
  7. 2022Model-Agnostic Augmentation for Accurate Graph Classificationcited by 21
  8. 2021Adversarial Attack on Graph Neural Networks as An Influence Maximization Problemcited by 20
  9. 2021Jointly Attacking Graph Neural Network and its Explanationscited by 18
  10. 2022Verification-Aided Deep Ensemble Selectioncited by 18
  11. 2022Scalable Verification of GNN-based Job Schedulerscited by 18
  12. 2024Graph Neural Network Explanations are Fragilecited by 18
38 more
  1. 2021Graph Structural Attack by Perturbing Spectral Distancecited by 16
  2. 2023Towards Reasonable Budget Allocation in Untargeted Graph Structure Attacks via Gradient Debiascited by 16
  3. 2024Verification-Guided Shielding for Deep Reinforcement Learningcited by 13
  4. 2022Adversarial Inter-Group Link Injection Degrades the Fairness of Graph Neural Networkscited by 12
  5. 2023Verifying Generalization in Deep Learningcited by 11
  6. 2024Safety in Graph Machine Learning: Threats and Safeguardscited by 11
  7. 2024Learning on Graphs with Large Language Models(LLMs): A Deep Dive into Model Robustnesscited by 11
  8. 2021Adversarial Attack Framework on Graph Embedding Models with Limited Knowledgecited by 10
  9. 2023Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networkscited by 10
  10. 2024Verifying message-passing neural networks via topology-based bounds tighteningcited by 10
  11. 2022Bandits for Structure Perturbation-based Black-box Attacks to Graph Neural Networks with Theoretical Guaranteescited by 9
  12. 2022Fundamental Limits in Formal Verification of Message-Passing Neural Networkscited by 9
  13. 2023Spear and Shield: Adversarial Attacks and Defense Methods for Model-Based Link Prediction on Continuous-Time Dynamic Graphscited by 9
  14. 2023Hierarchical Randomized Smoothingcited by 9
  15. 2024Coupling Graph Neural Networks with Fractional Order Continuous Dynamics: A Robustness Studycited by 9
  16. 2021GraphAttacker: A General Multi-Task GraphAttack Frameworkcited by 8
  17. 2022Revisiting Adversarial Attacks on Graph Neural Networks for Graph Classificationcited by 8
  18. 2024GDeR: Safeguarding Efficiency, Balancing, and Robustness via Prototypical Graph Pruningcited by 8
  19. 2023Evaluating Robustness and Uncertainty of Graph Models Under Structural Distributional Shiftscited by 7
  20. 2023Beyond Boundaries: A Comprehensive Survey of Transferable Attacks on AI Systemscited by 6
  21. 2021Adversarial Diffusion Attacks on Graph-based Traffic Prediction Modelscited by 5
  22. 2021Adversarial for Good? How the Adversarial ML Community's Values Impede Socially Beneficial Uses of Attackscited by 5
  23. 2021Adversarial Attacks on Graph Classification via Bayesian Optimisationcited by 5
  24. 2021Task and Model Agnostic Adversarial Attack on Graph Neural Networkscited by 5
  25. 2021Surrogate Representation Learning with Isometric Mapping for Gray-box Graph Adversarial Attackscited by 4
  26. 2023Adversarial Attacks on Fairness of Graph Neural Networkscited by 4
  27. 2021Black-box Gradient Attack on Graph Neural Networks: Deeper Insights in Graph-based Attack and Defensecited by 3
  28. 2024Practicable Black-box Evasion Attacks on Link Prediction in Dynamic Graphs -- A Graph Sequential Embedding Methodcited by 3
  29. 2025Backdoor Attacks on Discrete Graph Diffusion Modelscited by 3
  30. 2025On the Relationship Between Robustness and Expressivity of Graph Neural Networkscited by 3
  31. 2025Adversarial Attacks and Defenses on Graph-aware Large Language Models (LLMs)cited by 3
  32. 2022Interpretable and Effective Reinforcement Learning for Attacking against Graph-based Rumor Detectioncited by 2
  33. 2022What Does the Gradient Tell When Attacking the Graph Structurecited by 2
  34. 2023Everything Perturbed All at Once: Enabling Differentiable Graph Attackscited by 2
  35. 2024Link Stealing Attacks Against Inductive Graph Neural Networkscited by 2
  36. 2024Debiased Graph Poisoning Attack via Contrastive Surrogate Objectivecited by 2
  37. 2025Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbationscited by 2
  38. 2026ATEX-CF: Attack-Informed Counterfactual Explanations for Graph Neural Networkscited by 2

50 most cited of 76 All 76 (JSON)