# Simple and Efficient Partial Graph Adversarial Attack: A New Perspective

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 43 references that are in the map.
- First posted on arXiv 15 Aug 2023.

## Builds on (most cited first, 26 of 26)

- [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)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [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)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [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)
- [Graph Random Neural Network for Semi-Supervised Learning on Graphs](https://mlsanity.com/paper/2005.11079/) (2020)
- [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)
- [Decoupling Direction and Norm for Efficient Gradient-Based L2 Adversarial Attacks and Defenses](https://mlsanity.com/paper/1811.09600/) (2018)
- [Robustness of Graph Neural Networks at Scale](https://mlsanity.com/paper/2110.14038/) (2021)
- [DeepRobust: A PyTorch Library for Adversarial Attacks and Defenses](https://mlsanity.com/paper/2005.06149/) (2020)
- [Hiding Individuals and Communities in a Social Network](https://mlsanity.com/paper/1608.00375/) (2016)
- [TDGIA:Effective Injection Attacks on Graph Neural Networks](https://mlsanity.com/paper/2106.06663/) (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)
- [Adversarial Attack on Large Scale Graph](https://mlsanity.com/paper/2009.03488/) (2020)
- [Are Defenses for Graph Neural Networks Robust?](https://mlsanity.com/paper/2301.13694/) (2023)
- [Understanding Structural Vulnerability in Graph Convolutional Networks](https://mlsanity.com/paper/2108.06280/) (2021)
- [Towards Reasonable Budget Allocation in Untargeted Graph Structure Attacks via Gradient Debias](https://mlsanity.com/paper/2304.00010/) (2023)
- [Node Injection Attacks on Graphs via Reinforcement Learning](https://mlsanity.com/paper/1909.06543/) (2019)

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

- [Are LLM-Enhanced Graph Neural Networks Robust against Poisoning Attacks?](https://mlsanity.com/paper/2603.26105/) (2026)
- [ATEX-CF: Attack-Informed Counterfactual Explanations for Graph Neural Networks](https://mlsanity.com/paper/2602.06240/) (2026)
- [VGFL-SA: Vertical Graph Federated Learning Structure Attack Based on Contrastive Learning](https://mlsanity.com/paper/2502.16793/) (2025)
- [Optimal Transport-Guided Adversarial Attacks on Graph Neural Network-Based Bot Detection](https://mlsanity.com/paper/2602.00318/) (2026)
- [Top K Enhanced Reinforcement Learning Attacks on Heterogeneous Graph Node Classification](https://mlsanity.com/paper/2408.01964/) (2024)
- [Quantifying the Noise of Structural Perturbations on Graph Adversarial Attacks](https://mlsanity.com/paper/2504.20869/) (2025)
- [EvA: Evolutionary Attacks on Graphs](https://mlsanity.com/paper/2507.08212/) (2025)
- [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)

As the study of graph neural networks becomes more intensive and comprehensive, their robustness and security have received great research interest. The existing global attack methods treat all nodes in the graph as their attack targets. Although existing methods have achieved excellent results, there is still considerable space for improvement. The key problem is that the current approaches rigidly follow the definition of global attacks. They ignore an important issue, i.e., different nodes have different robustness and are not equally resilient to attacks. From a global attacker's view, we should arrange the attack budget wisely, rather than wasting them on highly robust nodes. To this end, we propose a totally new method named partial graph attack (PGA), which selects the vulnerable nodes as attack targets. First, to select the vulnerable items, we propose a hierarchical target selection policy, which allows attackers to only focus on easy-to-attack nodes. Then, we propose a cost-effective anchor-picking policy to pick the most promising anchors for adding or removing edges, and a more aggressive iterative greedy-based attack method to perform more efficient attacks. Extensive experimental results demonstrate that PGA can achieve significant improvements in both attack effect and attack efficiency compared to other existing graph global attack methods.