# Single Node Injection Attack against Graph Neural Networks

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

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 49 references that are in the map.
- First posted on arXiv 30 Aug 2021.

## Builds on (most cited first, 30 of 36)

- [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)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [One pixel attack for fooling deep neural networks](https://mlsanity.com/paper/1710.08864/) (2017)
- [Generating Sequences With Recurrent Neural Networks](https://mlsanity.com/paper/1308.0850/) (2013)
- [Threat of Adversarial Attacks on Deep Learning in Computer Vision: A Survey](https://mlsanity.com/paper/1801.00553/) (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)
- [Adversarial Attacks and Defenses in Images, Graphs and Text: A Review](https://mlsanity.com/paper/1909.08072/) (2019)
- [struc2vec: Learning Node Representations from Structural Identity](https://mlsanity.com/paper/1704.03165/) (2017)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Adversarial Attack and Defense on Graph Data: A Survey](https://mlsanity.com/paper/1812.10528/) (2018)
- [Graph Wavelet Neural Network](https://mlsanity.com/paper/1904.07785/) (2019)
- [DeepInf: Social Influence Prediction with Deep Learning](https://mlsanity.com/paper/1807.05560/) (2018)
- [AM-GCN: Adaptive Multi-channel Graph Convolutional Networks](https://mlsanity.com/paper/2007.02265/) (2020)
- [A Unified View on Graph Neural Networks as Graph Signal Denoising](https://mlsanity.com/paper/2010.01777/) (2020)
- [Adversarial Attacks on Node Embeddings via Graph Poisoning](https://mlsanity.com/paper/1809.01093/) (2018)
- [Certifiable Robustness to Graph Perturbations](https://mlsanity.com/paper/1910.14356/) (2019)
- [Certifiable Robustness and Robust Training for Graph Convolutional Networks](https://mlsanity.com/paper/1906.12269/) (2019)
- [Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More](https://mlsanity.com/paper/2008.12952/) (2020)
- [Attacking Graph-based Classification via Manipulating the Graph Structure](https://mlsanity.com/paper/1903.00553/) (2019)
- [Graph Convolutional Networks using Heat Kernel for Semi-supervised Learning](https://mlsanity.com/paper/2007.16002/) (2020)
- [Scalable Attack on Graph Data by Injecting Vicious Nodes](https://mlsanity.com/paper/2004.13825/) (2020)
- [Adversarial Attacks and Defenses on Graphs: A Review, A Tool and Empirical Studies](https://mlsanity.com/paper/2003.00653/) (2020)

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

- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [Unnoticeable Backdoor Attacks on Graph Neural Networks](https://mlsanity.com/paper/2303.01263/) (2023)
- [Let Graph be the Go Board: Gradient-free Node Injection Attack for Graph Neural Networks via Reinforcement Learning](https://mlsanity.com/paper/2211.10782/) (2022)
- [Adversarial Camouflage for Node Injection Attack on Graphs](https://mlsanity.com/paper/2208.01819/) (2022)
- [A General Black-box Adversarial Attack on Graph-based Fake News Detectors](https://mlsanity.com/paper/2404.15744/) (2024)
- [GANI: Global Attacks on Graph Neural Networks via Imperceptible Node Injections](https://mlsanity.com/paper/2210.12598/) (2022)
- [Bounding the Expected Robustness of Graph Neural Networks Subject to Node Feature Attacks](https://mlsanity.com/paper/2404.17947/) (2024)
- [A semantic backdoor attack against Graph Convolutional Networks](https://mlsanity.com/paper/2302.14353/) (2023)
- [Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attacks](https://mlsanity.com/paper/2312.03979/) (2023)
- [Cluster Attack: Query-based Adversarial Attacks on Graphs with Graph-Dependent Priors](https://mlsanity.com/paper/2109.13069/) (2021)
- [Neighboring Backdoor Attacks on Graph Convolutional Network](https://mlsanity.com/paper/2201.06202/) (2022)
- [Rethinking All Evidence: Enhancing Trustworthy Retrieval-Augmented Generation via Conflict-Driven Summarization](https://mlsanity.com/paper/2507.01281/) (2025)
- [Node Injection for Class-specific Network Poisoning](https://mlsanity.com/paper/2301.12277/) (2023)
- [IDEA: Invariant Defense for Graph Adversarial Robustness](https://mlsanity.com/paper/2305.15792/) (2023)
- [Hypergraph Attacks via Injecting Homogeneous Nodes into Elite Hyperedges](https://mlsanity.com/paper/2412.18365/) (2024)
- [Exact Verification of Graph Neural Networks with Incremental Constraint Solving](https://mlsanity.com/paper/2508.09320/) (2025)
- [Person Text-Image Matching via Text-Feature Interpretability Embedding and External Attack Node Implantation](https://mlsanity.com/paper/2211.08657/) (2022)
- [Single Node Injection Label Specificity Attack on Graph Neural Networks via Reinforcement Learning](https://mlsanity.com/paper/2305.02901/) (2023)
- [Query-Based and Unnoticeable Graph Injection Attack from Neighborhood Perspective](https://mlsanity.com/paper/2502.01936/) (2025)
- [Adversarial Learning Data Augmentation for Graph Contrastive Learning in Recommendation](https://mlsanity.com/paper/2302.02317/) (2023)
- [Graph Adversarial Immunization for Certifiable Robustness](https://mlsanity.com/paper/2302.08051/) (2023)
- [Fast Inference of Removal-Based Node Influence](https://mlsanity.com/paper/2403.08333/) (2024)
- [Are Your Models Still Fair? Fairness Attacks on Graph Neural Networks via Node Injections](https://mlsanity.com/paper/2406.03052/) (2024)
- [Talos: A More Effective and Efficient Adversarial Defense for GNN Models Based on the Global Homophily of Graphs](https://mlsanity.com/paper/2406.03833/) (2024)
- [RoBCtrl: Attacking GNN-Based Social Bot Detectors via Reinforced Manipulation of Bots Control Interaction](https://mlsanity.com/paper/2510.16035/) (2025)
- [Effective backdoor attack on graph neural networks in link prediction tasks](https://mlsanity.com/paper/2401.02663/) (2024)
- [AGSOA:Graph Neural Network Targeted Attack Based on Average Gradient and Structure Optimization](https://mlsanity.com/paper/2406.13228/) (2024)
- [On Measuring Unnoticeability of Graph Adversarial Attacks: Observations, New Measure, and Applications](https://mlsanity.com/paper/2501.05015/) (2025)
- [LiSA: Leveraging Link Recommender to Attack Graph Neural Networks via Subgraph Injection](https://mlsanity.com/paper/2502.09271/) (2025)
- [AI Security in the Foundation Model Era: A Comprehensive Survey from a Unified Perspective](https://mlsanity.com/paper/2603.24857/) (2026)

## Abstract (arXiv)

Node injection attack on Graph Neural Networks (GNNs) is an emerging and practical attack scenario that the attacker injects malicious nodes rather than modifying original nodes or edges to affect the performance of GNNs. However, existing node injection attacks ignore extremely limited scenarios, namely the injected nodes might be excessive such that they may be perceptible to the target GNN. In this paper, we focus on an extremely limited scenario of single node injection evasion attack, i.e., the attacker is only allowed to inject one single node during the test phase to hurt GNN's performance. The discreteness of network structure and the coupling effect between network structure and node features bring great challenges to this extremely limited scenario. We first propose an optimization-based method to explore the performance upper bound of single node injection evasion attack. Experimental results show that 100%, 98.60%, and 94.98% nodes on three public datasets are successfully attacked even when only injecting one node with one edge, confirming the feasibility of single node injection evasion attack. However, such an optimization-based method needs to be re-optimized for each attack, which is computationally unbearable. To solve the dilemma, we further propose a Generalizable Node Injection Attack model, namely G-NIA, to improve the attack efficiency while ensuring the attack performance. Experiments are conducted across three well-known GNNs. Our proposed G-NIA significantly outperforms state-of-the-art baselines and is 500 times faster than the optimization-based method when inferring.