Research map / Adversarial robustness and security / Black-box and transfer attacks

Highly Imperceptible Black-Box Graph Injection Attacks with Reinforcement Learning

AAAI 2025 · Adversarial robustness and security › Black-box and transfer attacks · approach: Query-efficient black-box attacks · 2 citations (OpenAlex)

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 TEANI, a model-agnostic black-box graph node injection evasion attack that formulates adversarial feature selection as an MDP and trains a PPO agent using only victim-model query results.

Problem

Graph neural node classifiers are vulnerable to evasion attacks, but existing node injection attacks depend on knowledge of the victim architecture and often generate injected nodes with unconstrained feature counts, hurting stealthiness.

Approach

Models injected-node generation as a Markov decision process where a PPO agent picks features one at a time under a feature budget, rewarded by the change in the target node's classification loss from black-box queries, with a cosine-similarity loss to keep injected nodes close to the target in feature space.

Key results

• Single injected node on Cora with GCN: TEANI reaches 59.7% misclassification versus 36.3% for the best baseline G2A2C.
• On Citeseer with GAT, TEANI achieves 70.4% misclassification versus 55.6% for G2A2C.
• Injecting five nodes drives GCN accuracy on Cora below 10%, per the budget analysis.

Measured effects reported in the paper

Surprising findings

• On APPNP, TEANI's gain over baselines is small (e.g., 39.5% vs 36.4% on Cora, 48.5% vs 48.0% on Citeseer), and on Cora-ML it is near parity with G2A2C (36.4 vs 34.1 for the best-case comparisons).

Limitations

• Only three citation datasets and three GNN architectures are evaluated.
• Evaluation covers single-node injection in the main comparison; multi-node results are shown only for GCN and GAT.
• The method still relies on a feature budget hyperparameter and a cosine-similarity weight alpha whose sensitivity is not analyzed.

Experimental setup

Datasets: Cora Citeseer Cora-ML

Benchmarks: Cora Citeseer Cora-ML

Metrics: misclassification rate

Baselines: Random GCIA G-NIA TDGIA G2A2C

Builds on: PPO GCIA G2A2C TDGIA G-NIA

Closest papers by meaning

• Let Graph Be the Go Board: Gradient-Free Node Injection Attack for Graph Neural Networks via Reinforcement Learning (AAAI 2023 · similarity 0.94)
• Bandits for Structure Perturbation-Based Black-Box Attacks To Graph Neural Networks With Theoretical Guarantees (CVPR 2022 · similarity 0.90)
• Stronger and Transferable Node Injection Attacks (AAAI 2024 · similarity 0.89)
• Value at Adversarial Risk: A Graph Defense Strategy against Cost-Aware Attacks (AAAI 2024 · similarity 0.89)
• Grimm: A Plug-and-Play Perturbation Rectifier for Graph Neural Networks Defending Against Poisoning Attacks (AAAI 2025 · similarity 0.88)
• HyperNear: Unnoticeable Node Injection Attacks on Hypergraph Neural Networks (ICML 2025 · similarity 0.87)