# Adversarial Attack on Large Scale Graph

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Sep 2020.

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

- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [Robustness of Graph Neural Networks at Scale](https://mlsanity.com/paper/2110.14038/) (2021)
- [Empowering Graph Representation Learning with Test-Time Graph Transformation](https://mlsanity.com/paper/2210.03561/) (2022)
- [Are Defenses for Graph Neural Networks Robust?](https://mlsanity.com/paper/2301.13694/) (2023)
- [Model Inversion Attacks against Graph Neural Networks](https://mlsanity.com/paper/2209.07807/) (2022)
- [Motif-Backdoor: Rethinking the Backdoor Attack on Graph Neural Networks via Motifs](https://mlsanity.com/paper/2210.13710/) (2022)
- [Revisiting Robustness in Graph Machine Learning](https://mlsanity.com/paper/2305.00851/) (2023)
- [Graph-Fraudster: Adversarial Attacks on Graph Neural Network Based Vertical Federated Learning](https://mlsanity.com/paper/2110.06468/) (2021)
- [Graph Structural Attack by Perturbing Spectral Distance](https://mlsanity.com/paper/2111.00684/) (2021)
- [Strategic Classification with Graph Neural Networks](https://mlsanity.com/paper/2205.15765/) (2022)
- [Spectral Adversarial Training for Robust Graph Neural Network](https://mlsanity.com/paper/2211.10896/) (2022)
- [A General Black-box Adversarial Attack on Graph-based Fake News Detectors](https://mlsanity.com/paper/2404.15744/) (2024)
- [Recent Advances in Reliable Deep Graph Learning: Inherent Noise, Distribution Shift, and Adversarial Attack](https://mlsanity.com/paper/2202.07114/) (2022)
- [GANI: Global Attacks on Graph Neural Networks via Imperceptible Node Injections](https://mlsanity.com/paper/2210.12598/) (2022)
- [GraphAttacker: A General Multi-Task GraphAttack Framework](https://mlsanity.com/paper/2101.06855/) (2021)
- [Simple and Efficient Partial Graph Adversarial Attack: A New Perspective](https://mlsanity.com/paper/2308.07834/) (2023)
- [SAILOR: Structural Augmentation Based Tail Node Representation Learning](https://mlsanity.com/paper/2308.06801/) (2023)
- [Adversarial Attacks and Defenses in Machine Learning-Powered Networks: A Contemporary Survey](https://mlsanity.com/paper/2303.06302/) (2023)
- [Exact Verification of Graph Neural Networks with Incremental Constraint Solving](https://mlsanity.com/paper/2508.09320/) (2025)
- [Are LLM-Enhanced Graph Neural Networks Robust against Poisoning Attacks?](https://mlsanity.com/paper/2603.26105/) (2026)
- [Practicable Black-box Evasion Attacks on Link Prediction in Dynamic Graphs -- A Graph Sequential Embedding Method](https://mlsanity.com/paper/2412.13134/) (2024)
- [GUARD: Graph Universal Adversarial Defense](https://mlsanity.com/paper/2204.09803/) (2022)
- [Graph Adversarial Immunization for Certifiable Robustness](https://mlsanity.com/paper/2302.08051/) (2023)
- [Revisiting Edge Perturbation for Graph Neural Network in Graph Data Augmentation and Attack](https://mlsanity.com/paper/2403.07943/) (2024)
- [ATEX-CF: Attack-Informed Counterfactual Explanations for Graph Neural Networks](https://mlsanity.com/paper/2602.06240/) (2026)
- [Graphfool: Targeted Label Adversarial Attack on Graph Embedding](https://mlsanity.com/paper/2102.12284/) (2021)
- [Disttack: Graph Adversarial Attacks Toward Distributed GNN Training](https://mlsanity.com/paper/2405.06247/) (2024)
- [GraphMU: Repairing Robustness of Graph Neural Networks via Machine Unlearning](https://mlsanity.com/paper/2406.13499/) (2024)
- [Does Homophily Help in Robust Test-time Node Classification?](https://mlsanity.com/paper/2510.22289/) (2025)
- [A BIC-based Mixture Model Defense against Data Poisoning Attacks on Classifiers](https://mlsanity.com/paper/2105.13530/) (2021)

## Abstract (arXiv)

Recent studies have shown that graph neural networks (GNNs) are vulnerable against perturbations due to lack of robustness and can therefore be easily fooled. Currently, most works on attacking GNNs are mainly using gradient information to guide the attack and achieve outstanding performance. However, the high complexity of time and space makes them unmanageable for large scale graphs and becomes the major bottleneck that prevents the practical usage. We argue that the main reason is that they have to use the whole graph for attacks, resulting in the increasing time and space complexity as the data scale grows. In this work, we propose an efficient Simplified Gradient-based Attack (SGA) method to bridge this gap. SGA can cause the GNNs to misclassify specific target nodes through a multi-stage attack framework, which needs only a much smaller subgraph. In addition, we present a practical metric named Degree Assortativity Change (DAC) to measure the impacts of adversarial attacks on graph data. We evaluate our attack method on four real-world graph networks by attacking several commonly used GNNs. The experimental results demonstrate that SGA can achieve significant time and memory efficiency improvements while maintaining competitive attack performance compared to state-of-art attack techniques. Codes are available via: https://github.com/EdisonLeeeee/SGAttack.