Introduction
Graph Neural Networks (GNNs) have become a cornerstone for analyzing structured data in domains ranging from financial fraud detection to social network analysis. Despite their success, GNNs are susceptible to adversarial perturbations. Most existing research focuses on Graph Modification Attacks (GMA), where an attacker alters existing edges or features. However, in real-world scenarios, attackers rarely have the authority to modify legitimate user profiles. Instead, they are more likely to perform Graph Injection Attacks (GIA), creating new malicious nodes to influence the system.
Furthermore, many current GIA methods rely on "white-box" knowledge of the victim model's internal parameters or produce "noisy" nodes with excessive features that are easily detected. This paper introduces TEANI (Targeted Evasion Attack via Node Injection), a reinforcement learning-based framework designed for black-box settings that prioritizes both attack effectiveness and imperceptibility.
Methodology
TEANI treats the generation of an adversarial node as a sequential decision-making process, formulated as a Markov Decision Process (MDP) and optimized using Proximal Policy Optimization (PPO).
The framework consists of three primary components:
- State Embedding: Uses Graph Convolutional Layers (GCLs) to encode the local neighborhood of the target node and the current state of the injected node.
- Policy Network: A feature selection network that picks features one by one. This sequential approach allows for precise control over the feature budget, ensuring the injected node remains sparse and stealthy. A logit mask is applied to prevent the agent from selecting the same feature twice.
- Value Network: Predicts the expected reward to guide the RL agent's training.
The Reward Function is critical for balancing attack success and stealth. It incorporates the classification loss of the victim model (to encourage misclassification) and a cosine similarity loss between the injected node and the target node's neighborhood. This ensures the fake node "blends in" with its surroundings.
Experimental Setup
The effectiveness of TEANI was evaluated on three standard citation datasets: Cora, Citeseer, and Cora-ML. In these graphs, nodes represent documents and edges represent citations. The goal of the attack is to force the victim GNN to misclassify a specific target document by injecting a single malicious citation node.
Results and Discussion
TEANI demonstrates superior performance compared to state-of-the-art (SOTA) methods like $G^2A2C$, particularly in black-box scenarios.
Attack Effectiveness and Stealth
On the Cora dataset, TEANI increased the misclassification rate of a GCN model from a baseline of 18.4% to 59.7%. Remarkably, this was achieved while maintaining extreme stealth. Case studies revealed that TEANI could successfully flip a target node's label by injecting a node with as few as 1 to 5 non-zero features. This sparsity makes the attack nearly invisible to traditional anomaly detectors that flag nodes with unusual feature counts.
Model Agnosticism
A key strength of TEANI is its model-agnostic nature. The RL agent learns an effective strategy by observing only the output labels or probabilities of the victim model. It successfully attacked various architectures, including GCN, GAT, and APPNP, without requiring access to their internal gradients.
Conclusion
TEANI proves that GNNs can be compromised by highly sparse, strategically designed node injections. By leveraging reinforcement learning to explore the combinatorial space of features, the attack identifies high-impact perturbations that exploit the neighborhood aggregation mechanism of GNNs. Future research should focus on improving the query efficiency of such black-box attacks and developing robust defense mechanisms to mitigate these stealthy injections.
Summary updated