# Let Graph be the Go Board: Gradient-free Node Injection Attack for Graph Neural Networks via Reinforcement Learning

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 30 references that are in the map.
- First posted on arXiv 19 Nov 2022.

## 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)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [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)
- [Wiki-CS: A Wikipedia-Based Benchmark for Graph Neural Networks](https://mlsanity.com/paper/2007.02901/) (2020)
- [Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective](https://mlsanity.com/paper/1906.04214/) (2019)
- [Inferring Networks of Substitutable and Complementary Products](https://mlsanity.com/paper/1506.08839/) (2015)
- [DeepRobust: A PyTorch Library for Adversarial Attacks and Defenses](https://mlsanity.com/paper/2005.06149/) (2020)
- [PinnerSage: Multi-Modal User Embedding Framework for Recommendations at Pinterest](https://mlsanity.com/paper/2007.03634/) (2020)
- [TDGIA:Effective Injection Attacks on Graph Neural Networks](https://mlsanity.com/paper/2106.06663/) (2021)
- [Understanding and Improving Graph Injection Attack by Promoting Unnoticeability](https://mlsanity.com/paper/2202.08057/) (2022)
- [Attacking Graph-based Classification via Manipulating the Graph Structure](https://mlsanity.com/paper/1903.00553/) (2019)
- [Scalable Attack on Graph Data by Injecting Vicious Nodes](https://mlsanity.com/paper/2004.13825/) (2020)
- [Single Node Injection Attack against Graph Neural Networks](https://mlsanity.com/paper/2108.13049/) (2021)
- [Attacking Graph Convolutional Networks via Rewiring](https://mlsanity.com/paper/1906.03750/) (2019)
- [Node Injection Attacks on Graphs via Reinforcement Learning](https://mlsanity.com/paper/1909.06543/) (2019)
- [Adaptive Kernel Graph Neural Network](https://mlsanity.com/paper/2112.04575/) (2021)

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

- [GraphPatcher: Mitigating Degree Bias for Graph Neural Networks via Test-time Augmentation](https://mlsanity.com/paper/2310.00800/) (2023)
- [Bounding the Expected Robustness of Graph Neural Networks Subject to Node Feature Attacks](https://mlsanity.com/paper/2404.17947/) (2024)
- [Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attacks](https://mlsanity.com/paper/2312.03979/) (2023)
- [How Does Message Passing Improve Collaborative Filtering?](https://mlsanity.com/paper/2404.08660/) (2024)
- [Single Node Injection Label Specificity Attack on Graph Neural Networks via Reinforcement Learning](https://mlsanity.com/paper/2305.02901/) (2023)
- [Collective Certified Robustness against Graph Injection Attacks](https://mlsanity.com/paper/2403.01423/) (2024)
- [Query-Based and Unnoticeable Graph Injection Attack from Neighborhood Perspective](https://mlsanity.com/paper/2502.01936/) (2025)
- [Are Your Models Still Fair? Fairness Attacks on Graph Neural Networks via Node Injections](https://mlsanity.com/paper/2406.03052/) (2024)
- [Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbations](https://mlsanity.com/paper/2503.18503/) (2025)
- [Momentum Gradient-based Untargeted Attack on Hypergraph Neural Networks](https://mlsanity.com/paper/2310.15656/) (2023)
- [AGSOA:Graph Neural Network Targeted Attack Based on Average Gradient and Structure Optimization](https://mlsanity.com/paper/2406.13228/) (2024)
- [Understanding the Robustness of Graph Neural Networks against Adversarial Attacks](https://mlsanity.com/paper/2406.13920/) (2024)
- [HeTa: Relation-wise Heterogeneous Graph Foundation Attack Model](https://mlsanity.com/paper/2506.07428/) (2025)
- [On the Adversarial Robustness of Graph Neural Networks with Graph Reduction](https://mlsanity.com/paper/2412.05883/) (2024)
- [Navigating the Black Box: Leveraging LLMs for Effective Text-Level Graph Injection Attacks](https://mlsanity.com/paper/2506.13276/) (2025)
- [EvA: Evolutionary Attacks on Graphs](https://mlsanity.com/paper/2507.08212/) (2025)
- [Single-Edge Node Injection Threats to GNN-Based Security Monitoring in Industrial Graph Systems](https://mlsanity.com/paper/2602.01113/) (2026)
- [PEANUT: Perturbations by Eigenvector Alignment for Attacking Graph Neural Networks Under Topology-Driven Message Passing](https://mlsanity.com/paper/2603.26136/) (2026)
- [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)

Graph Neural Networks (GNNs) have drawn significant attentions over the years and been broadly applied to essential applications requiring solid robustness or vigorous security standards, such as product recommendation and user behavior modeling. Under these scenarios, exploiting GNN's vulnerabilities and further downgrading its performance become extremely incentive for adversaries. Previous attackers mainly focus on structural perturbations or node injections to the existing graphs, guided by gradients from the surrogate models. Although they deliver promising results, several limitations still exist. For the structural perturbation attack, to launch a proposed attack, adversaries need to manipulate the existing graph topology, which is impractical in most circumstances. Whereas for the node injection attack, though being more practical, current approaches require training surrogate models to simulate a white-box setting, which results in significant performance downgrade when the surrogate architecture diverges from the actual victim model. To bridge these gaps, in this paper, we study the problem of black-box node injection attack, without training a potentially misleading surrogate model. Specifically, we model the node injection attack as a Markov decision process and propose Gradient-free Graph Advantage Actor Critic, namely G2A2C, a reinforcement learning framework in the fashion of advantage actor critic. By directly querying the victim model, G2A2C learns to inject highly malicious nodes with extremely limited attacking budgets, while maintaining a similar node feature distribution. Through our comprehensive experiments over eight acknowledged benchmark datasets with different characteristics, we demonstrate the superior performance of our proposed G2A2C over the existing state-of-the-art attackers. Source code is publicly available at: https://github.com/jumxglhf/G2A2C}.