RL-Guided Node Injection Undermines Black-Box GNNs

Problem

The paper studies black-box node injection attacks against Graph Neural Networks where an adversary adds fabricated nodes and incident edges without altering the original graph. Such attacks are practical when attackers can create new entities but cannot modify existing records. Prior work often decouples the generation of malicious node features and edge connections, which reduces attack effectiveness under strict budgets and limited query access. The problem matters because small, well-placed injections can substantially alter GNN predictions in security-sensitive domains such as fraud detection and social systems.

Approach

The authors propose TIRBA, a reinforcement learning framework that formulates black-box node injection as a Markov Decision Process and applies an Advantage Actor-Critic objective to jointly optimise feature generation and edge selection in a heterogeneous action space. Key components are a target-aware interaction encoder that fuses parallel feature and topology representations to overcome isolation between stages, a class-centre guidance mechanism that steers feature generation using an estimated class centre (a pseudo-target chosen as the second-most probable class), and a topology difference-aware critic that estimates state value from the discrepancy between the target node and its benign neighbours. Feature sampling uses a continuous Gumbel-Softmax relaxation to remain differentiable while respecting a feature-sparsity budget. The agent receives rewards from query-based loss variation on the victim model and is trained end-to-end without access to victim model internals. Experiments use a strict single-injected-node, single-edge budget across four citation datasets and four common GNN architectures.

Key Findings

• TIRBA consistently outperforms state-of-the-art black-box node injection baselines across datasets and victim models, achieving markedly higher misclassification rates under strict budgets.
• The method attains particularly strong results on benchmark citation graphs and attains an attack success rate approaching 94% on the Pubmed dataset in reported experiments.
• Ablations show all three core components contribute meaningfully: removing class-centre guidance yields the largest drop, omitting the target-aware encoder reduces effectiveness, and removing the difference-aware critic degrades learning stability and performance.
• Attack effectiveness rises with larger node, edge, or feature budgets but quickly plateaus, and TIRBA maintains high success even at very low budgets.
• Visualisation of feature embeddings shows the injected node can pull the target node across the representation space into an incorrect class cluster, explaining induced misclassification.

Limitations

The evaluation focusses on a single-injected-node setting and on four citation-network benchmarks and four common GNN architectures, which may limit generalisability to other graph types or multi-node coordinated injections. The method relies on query feedback to the victim model and uses a pseudo-target heuristic; these design choices shape performance and may interact with different deployment constraints. The paper notes future work to explore stealthier and more effective injection strategies.

Implications

Offensively, TIRBA demonstrates that an attacker with only query access can jointly craft node attributes and edges to reliably flip GNN predictions, even under tight perturbation and query budgets. This capability raises concrete attack vectors for systems that accept created entities, including manipulation of fraud detectors, reputation systems, and recommendation or moderation pipelines. The results show that coordination between feature and topology manipulation materially increases attack potency compared with decoupled approaches, suggesting that defenders should expect sophisticated injection strategies that exploit joint optimisation.