Research map / Adversarial robustness and security / Black-box and transfer attacks
Stronger and Transferable Node Injection Attacks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes R-NIA, a black-box node injection attack combining max-margin loss, cosine-similarity direction diversification, L2 gradient steps, and surrogate weight perturbation to produce stronger, more transferable attacks on GNNs.
Problem
Node injection attacks on GNNs are typically crafted with cross-entropy PGD under L-infinity constraints, which are weak and transfer poorly to black-box GNN models.
Approach
Replace cross-entropy with max-margin loss, add a cosine-similarity term that pushes injected features away from their random initialization for early iterations, use L2-normalized gradient ascent instead of sign gradients, and craft attacks on an L2-perturbed surrogate model to improve transfer.
Key results
- On Cora and Citeseer black-box transfer, R-NIA improves over HAO by up to 8.18% on Cora and around 5% on Citeseer.
- Using L2-normalized gradients instead of L-infinity gradients yields up to 7% stronger attacks; MAA beats PGD by over 1.5% on Cora and Flickr.
- On Aminer, R-NIA outperforms PGD by over 10% at larger injection budgets, and by 7% on Twitter.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace cross-entropy with max-margin loss (MAA) (ablation) | PGD-style node injection attack · Cora | robust accuracy (%): 33.21 -> 32.71 | Helped |
| Replace cross-entropy with max-margin loss (MAA) (ablation) | PGD-style node injection attack · Citeseer | robust accuracy (%): 21.42 -> 20.17 | Helped |
| Add cosine-similarity minimization to PGD without max-margin loss (ablation) | PGD · Cora | robust accuracy (%): 33.21 -> 52.10 | Hurt |
| Add cosine-similarity minimization to MAA (MDA) (ablation) | MAA · Cora | robust accuracy (%): 32.71 -> 21.02 | Helped |
| Add cosine-similarity minimization to MAA (MDA) (ablation) | MAA · Citeseer | robust accuracy (%): 20.17 -> 19.44 | Helped |
| Add surrogate-model weight perturbation (MDTA) (ablation) | MDA · Cora | robust accuracy (%): 21.02 -> 20.41 | Helped |
| Add surrogate-model weight perturbation (MDTA) (ablation) | MDA · Citeseer | robust accuracy (%): 19.44 -> 18.45 | Helped |
| Use ℓ2 instead of ℓ∞ gradient updates (ablation) | R-NIA · Cora | robust accuracy (%): 19.23 -> 17.03 | Helped |
| Use ℓ2 instead of ℓ∞ gradient updates (ablation) | R-NIA · Citeseer | robust accuracy (%): 17.21 -> 14.86 | Helped |
| Add surrogate-weight perturbation to MAA (MTA) (ablation) | MAA · Cora | robust accuracy (%): 32.71 -> 31.87 | Helped |
| Use R-NIA rather than PGD | GCN node injection attack · Flickr | robust accuracy (%): 41.03 -> 38.41 | Helped |
| Use R-NIA rather than PGD | GCN node injection attack · Aminer | robust accuracy (%): 64.23 -> 61.42 | Helped |
Surprising findings
- Minimizing cosine similarity alone (PGD co-sim) yields weak attacks, showing it is useful only as an initialization step before max-margin optimization.
- HAO is the strongest baseline on Cora and Citeseer, outperforming PGD and G-NIA in the main table.
Limitations
- Gains on large graphs are reported with a fixed hyperparameter setting and relatively few attack-budget configurations.
- Transferability gains shrink or reverse when surrogate perturbation radius is large because surrogate accuracy degrades.
- Adjacency update uses a single-step gradient ascent with rounding, a simplified treatment of discrete edges.
Experimental setup
Datasets: Cora Citeseer Flickr Aminer Amazon2M Twitter
Benchmarks: Cora Citeseer Flickr Aminer Amazon2M Twitter
Metrics: robust accuracy (%) closest attribute distance (CAD)
Baselines: PGD MetaAttack NAttack AFGSM G-NIA HAO TDGIA
Builds on: PGD TDGIA HAO G-NIA sharpness-aware minimization
Closest papers by meaning
- Highly Imperceptible Black-Box Graph Injection Attacks with Reinforcement Learning (AAAI 2025 · similarity 0.89)
- Are Your Models Still Fair? Fairness Attacks on Graph Neural Networks via Node Injections (NeurIPS 2024 · similarity 0.88)
- Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbations (CVPR 2025 · similarity 0.87)
- Value at Adversarial Risk: A Graph Defense Strategy against Cost-Aware Attacks (AAAI 2024 · similarity 0.87)
- Robustness Inspired Graph Backdoor Defense (ICLR 2025 · similarity 0.87)
- Grimm: A Plug-and-Play Perturbation Rectifier for Graph Neural Networks Defending Against Poisoning Attacks (AAAI 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.