1 INTRODUCTION↩︎

Graph Neural Networks (GNNs) have achieved strong performance on graph-structured data but remain vulnerable to adversarial attacks [1], [2], highlighting the necessity of investigating graph representation vulnerabilities under diverse adversarial setups [3]–[6]. This inherent fragility has recently sparked comprehensive studies into certified robustness, privacy leakage, and generalized evaluation frameworks across various graph topologies [7]–[10]. Small perturbations may substantially degrade model predictions, raising concerns in security-sensitive applications such as fraud detection [11]–[13], as well as in other critical domains where adversarial instances manipulate social engagements, target model explanations, or disrupt dynamic link predictions [14]–[17]. Graph Modification Attacks (GMA) alter existing edges or node attributes [18], [19], and therefore require modification permissions that may be unavailable in practical adversarial scenarios [20]–[23]. By contrast, Node Injection Attacks (NIA) add fabricated nodes and incident edges while preserving all pre-existing nodes, attributes, and edges [24]. For example, an adversary may create new accounts and connect them to existing users to influence a graph-based decision system [25], [26]. NIA is therefore feasible when adversaries can create new entities but cannot modify historical graph records [27].

Despite its practicality, executing effective black-box NIA remains technically challenging due to the massive discrete search space and complex graph topologies [28]–[31]. First, attackers cannot access the victim model’s architecture, parameters, gradients, or intermediate representations and must optimize the attack through prediction-score queries [32], a process that often leverages cluster priors, node voting mechanisms, or unnoticeable homogeneous node injections to circumvent defensive barriers [33]–[36]. Second, because GNNs couple structural and attribute information during message passing, node features and edges are deeply intertwined [37]–[39]. However, existing methods often isolate feature generation and edge construction into separate stages, weakening their intrinsic coordination under tight query and perturbation budgets [27]. Furthermore, surrogate-based methods may exhibit limited transferability because of mismatched decision boundaries [2], making direct black-box optimization highly desirable yet complex [40]–[43]. Searching a massive, discrete, and high-dimensional combinatorial space using only query feedback and without heuristic guidance also makes optimization inefficient and unstable [44], [45].

To address these issues, we propose TIRBA. TIRBA retains the standard Advantage Actor-Critic (A2C) objective [46] but redesigns its actor and critic for feature generation and additional-edge selection in node injection. To coordinate heterogeneous generation, TIRBA introduces a target-aware interaction encoder that fuses parallel feature and topology representations, which helps overcome the information isolation problem in sequential generation [47]–[50]. Additionally, a Class-Center Guidance Mechanism utilizes prior class vectors to steer feature generation and applies Gumbel-Softmax for end-to-end differentiability. Finally, a Topology Difference-Aware State Value Evaluation uses the representation discrepancy between the target and its original neighbors as an explicit signal for state-value estimation. The main contributions of this paper are summarized as follows:

• We propose TIRBA, a black-box node injection attack framework based on the A2C algorithm [46]. It formulates feature generation and edge selection as a Markov Decision Process and performs end-to-end optimization in a heterogeneous action space.

• We introduce a target-aware interaction encoder, label-informed class-center guidance, and topology difference-aware state value evaluation. These mechanisms adapt the actor and critic to feature-topology dependencies in node injection.

• We conduct extensive experiments on four real-world benchmark datasets with several widely used GNN models. The results demonstrate that TIRBA achieves superior attack performance compared with existing state-of-the-art methods.

2 RELATED WORK↩︎

2.1 Adversarial Attacks↩︎

With the widespread adoption of deep learning on non-Euclidean data, the robustness of GNNs has received extensive attention [51]–[54]. Existing adversarial attacks on graphs are broadly categorized into evasion attacks and poisoning attacks [27]. Early studies predominantly focused on GMA [18], [19]. For instance, the projected gradient descent (PGD) [55], [56] method leverages the gradient information of the target model to guide the attack. It modifies original edges or node features in the graph to mislead the model’s predictions [57]–[60]. Such gradient-based attacks can be white-box when differentiating through the victim model or transfer-based black-box when using a surrogate, while GMA still requires permission to modify pre-existing graph elements [1], [27]. In actual security-sensitive scenarios, such global modifications can easily trigger alarms in defense systems [61]–[64]. Consequently, the practical applicability of these attacks is profoundly limited [2].

2.2 Node Injection Attacks↩︎

To overcome the practical limitations of GMA, NIA was introduced [24]. In NIA, the attacker is only permitted to inject a limited number of fabricated nodes into the graph and cannot alter any original benign structures [65]–[68]. This paradigm renders the attack stealthier [27]. In recent years, several NIA methods have been proposed to evaluate and expose GNN security risks [24], [69]–[72]. For example, TDGIA employs a heuristic edge connection rule based on topological defects [73]. GCIA incorporates graph contrastive learning to enhance query efficiency in a black-box setting [74]. G\(^2\)A2C adopts an Actor-Critic reinforcement learning architecture, formulating the attack as a sequential decision problem [75].Notably, reinforcement learning has demonstrated immense potential in orchestrating versatile black-box and universal graph attacks, while also prompting cutting-edge research into its own specific adversarial and backdoor vulnerabilities [76]–[79].

Sequential node injection methods commonly generate features before performing the subsequent edge-wiring decisions, which may weaken coordination between the two stages. To mitigate this problem, TIRBA introduces a target-aware interaction encoder to exchange information between the feature and topology branches. It further uses class-center guidance and topology difference-aware state value evaluation. Each injected node is first connected to the target by a mandatory anchoring edge, while the learned edge policy selects additional endpoints only when the edge budget exceeds one. The actor and critic are optimized jointly through score-based rewards without differentiating through the victim model.

3 PRELIMINARY↩︎

3.1 Graph Neural Networks↩︎

We define an undirected attributed graph \(G = (A, X)\), where \(A \in \{0,1\}^{N \times N}\) is the adjacency matrix corresponding to the edge set \(E\), and \(X \in \mathbb{R}^{N \times d}\) is the node feature matrix. Specifically, \(A_{ij} = 1\) if an edge exists, and \(A_{ij} = 0\) otherwise. GNN learns node representations by aggregating information from local neighbors. For a GNN with \(L\) layers, the message passing process of the feature representation \(H^{(l)}\) at layer \(l\) is defined as:

\[H^{(l)} = \sigma \left( \text{AGGREGATE}\left(A, H^{(l-1)}\right) W^{(l)} \right)\] where \(H^{(0)} = X\) denotes the initial feature matrix, \(\sigma(\cdot)\) is the activation function, \(W^{(l)}\) is the weight matrix, and \(\text{AGGREGATE}(\cdot)\) signifies the aggregation function. For example, in a Graph Convolutional Network [80], the propagation rule is given by:

\[H^{(l)} = \sigma \left( \tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l-1)} W^{(l)} \right)\] where \(\tilde{A} = A + I_N\), and \(\tilde{D}\) is the corresponding degree matrix of \(\tilde{A}\). In this paper, the experiments evaluate several models, such as GCN [80], SGC [81], APPNP [82], and GAT [83]. All these models adhere to this general framework. For classification tasks, the model’s output is mapped by the Softmax function to a probability distribution \(Z \in \mathbb{R}^{N \times C}\), where \(C\) is the number of classes. The fully trained black-box victim model is denoted as \(f_{\theta^*}(\cdot)\).

3.2 Attack Formulation↩︎

This paper focuses on the Black-box Evasion Attack within a node classification scenario [84]. In this setting, the attacker lacks access to the internal structure, weight gradients, and specific training data of the victim model \(f_{\theta^*}\), relying solely on external feedback [85]–[88]. They can only query the target model a limited number of times and utilize the output feedback to guide the attack strategy. To conduct the attack without perturbing original benign nodes, NIA permits the attacker to inject fabricated, malicious nodes into the original graph \(G\) [89]–[92]. Assuming the target node is \(v_t\), the attacker’s objective is to construct a feature matrix \(X_a \in \mathbb{R}^{\mathcal{B}_n \times d}\) for the injected nodes and a connection matrix \(A_a \in \{0,1\}^{\mathcal{B}_n \times N}\) linking the injected nodes to the original graph nodes. In this work, we focus on a single-injected-node setting (\(\mathcal{B}_n = 1\)). This yields a newly modified graph \(G' = (A', X')\):

\[A' = \begin{bmatrix} A & A_a^T \\ A_a & 0 \end{bmatrix}, \quad X' = \begin{bmatrix} X \\ X_a \end{bmatrix} \label{eq:injected95graph95matrix}\tag{1}\] To maintain stealthiness, injected nodes remain disconnected from each other. The injection is subjected to strict budgets: the node budget is \(\mathcal{B}_n\), the edge budget is \(\mathcal{B}_e\), and the feature budget is \(\mathcal{B}_x\). Here, \(\mathcal{B}_e\) denotes the maximum number of edges incident to each injected node, including the mandatory target-anchoring edge. Specifically, the number of active feature dimensions in the injected feature matrix \(X_a\) is constrained by \(\sum_{i=1}^{\mathcal{B}_n} \sum_{j=1}^{d} \mathbb{I}(X_a^{(i,j)} > 0) \le \mathcal{B}_x\). The attack aims to identify the optimal \(X_a\) and \(A_a\) within these budgets to maximize the prediction loss on \(v_t\) and induce misclassification. Given the vast discrete search space, we formulate this challenge as an MDP.

4 METHODOLOGY↩︎

4.1 Attack Framework↩︎

Since generating discrete features and edges in a black-box setting is inherently a sequential decision-making process, we formulate it as an MDP and propose TIRBA, an end-to-end Actor-Critic framework (Fig. 1). The Policy Network (Actor) uses a class center vector \(C_{target}\) to generate injected node features and edges. In the single-injected-node setting, the generated feature vector is denoted by \(X_a \in \mathbb{R}^{d}\). The resulting Attack Graph is evaluated via two feedback loops: querying the victim GNN yields the loss variation as the reward, while the Value Network (Critic) calculates the local topology difference \(h_t \ominus h_n\) to estimate the state value. This process iterates until target misclassification or budget exhaustion.

We mathematically define the node injection attack on the victim GNN through the following three core components:

State. The state \(s_t\) at time step \(t\) corresponds to a local sub-graph centered on the target node \(v_t\). This state encapsulates both the local structural matrix and the node feature matrix, providing the agent with a comprehensive observation of the environment.

Action. The action sequence first samples a relaxed feature vector \(X_a\) for the injected node. The injected node is then linked to \(v_t\) by a mandatory target-anchoring edge. If \(\mathcal{B}_e>1\), each remaining edge action selects an unconnected original node \(v_c\) from the candidate set \(\mathcal{V}_c\).

Reward. As an untargeted evasion attack, the reward relies on the Cross-Entropy Loss \(\mathcal{L}\) variation regarding the victim’s initial prediction for \(v_t\), strictly avoiding ground-truth labels. The immediate reward \(r_t\) is the loss discrepancy: \[r_t = \mathcal{L}(v_t, G'_{t+1}) - \mathcal{L}(v_t, G'_t) \label{eq:reward}\tag{2}\] where \(G'_t\) and \(G'_{t+1}\) denote the graph states before and after executing the action \(a_t\).

4.2 Policy Network↩︎

The Policy Network aims to learn the optimal injection strategy. It orchestrates the generation of the injected node’s attributes and topology through three primary modules:

State Encoder. To achieve enhanced target focus, we adopt target-conditioned message passing. Two parallel GATs extract the initial feature embedding \(h_a^{(1)}\) and edge embedding \(h_e^{(1)}\). To facilitate context sharing across both tasks, we concatenate them at the intermediate layer. Subsequently, we explicitly inject the target node’s initial projection embedding \(e_t\) (projected to match the concatenated dimension) to realize target-aware interaction fusion: \[\tilde{h}_a = (h_a^{(1)} \parallel h_e^{(1)}) + e_t\] \[\tilde{h}_e = (h_e^{(1)} \parallel h_a^{(1)}) + e_t\] where \(\parallel\) denotes the concatenation operation. The fused representations are then aggregated by the second GAT layer, which outputs the final state encoding \(h_a\) for feature generation and \(h_e\) for edge sampling.

Node Generator. Exploring a high-dimensional discrete feature space in a black-box setting is highly inefficient. Therefore, we introduce a heuristic guidance mechanism. To cross the decision boundary with minimal cost, we adopt a pseudo-targeted strategy by selecting the second-most probable class as the target class. This pseudo-targeted design acts as an efficient heuristic to rapidly cross the decision boundary for untargeted evasion goals. The decoder first projects \(h_a\) to an initial logit vector \(z\). We then explicitly incorporate the feature center vector \(C_{target}\) of this target class to obtain a guided distribution \(z_g\). To maintain black-box strictness, \(C_{target}\) is estimated by averaging features of accessible nodes assigned to this pseudo-class: \[z_g = z + \alpha \cdot C_{target}\] where \(\alpha\) is a weight parameter controlling the guidance intensity. We apply a continuous relaxation to enable differentiable multi-hot feature sampling. The final relaxed feature row vector \(X_a\) of the injected node is derived as: \[X_a = \text{Sigmoid}\left(\frac{z_g + g}{\tau}\right)\] where \(g\) represents independent noise sampled from the standard Gumbel distribution, and \(\tau\) is a temperature hyperparameter controlling distribution smoothness.

Edge Sampler. When \(\mathcal{B}_e>1\), an MLP computes the additional-edge score \(s_c\) for each candidate original node \(v_c \in \mathcal{V}_c\). The scorer combines the topology representation \(h_e\) and the newly generated feature \(X_a\): \[s_c = \text{MLP}_e \left( h_e^{(v_t)} \parallel h_e^{(v_c)} \parallel (X_a W_p) \right)\] where \(h_e^{(v_t)}\) and \(h_e^{(v_c)}\) represent the specific state encodings of the target node and candidate node, respectively, and \(W_p\) is a feature projection matrix. The resulting scores are transformed into an action probability distribution via Softmax: \[P(v_c | s_t) = \frac{\exp(s_c)}{\sum_{k \in \mathcal{V}_c} \exp(s_k)}\]

4.3 Value Network↩︎

The Value Network estimates the expected return to supervise the Policy Network. Since conventional mean aggregation over-smooths representations and obscures injected structural anomalies, we refine the pooling strategy. We explicitly compute the difference \(h_t \ominus h_n\) between the target node’s hidden state \(h_t\) and its benign neighbors’ mean state \(h_n\). This directly captures the broken homophily caused by injected edges [93], [94]. Finally, the state value \(V_\phi(s_t)\) is evaluated by concatenating these components into an MLP: \[V_\phi(s_t) = \text{MLP}_v \left( h_t \parallel h_n \parallel (h_t \ominus h_n) \right)\] where \(\ominus\) denotes element-wise subtraction, and \(\phi\) represents the learnable parameters of the Critic network. By explicitly capturing this topological discrepancy, the Value Network directly perceives local structural variations caused by the injected node, facilitating faster convergence of the reinforcement learning process.

4.4 Training Algorithm↩︎

TIRBA is trained end-to-end utilizing the Advantage Actor-Critic algorithm [46]. Upon the completion of each attack trajectory, we first compute the cumulative reward \(R_t\) with a discount factor \(\gamma\):

\[R_t = \sum_{k=0}^{\infty} \gamma^k r_{t+k} \label{eq:return}\tag{3}\] where \(r_{t+k}\) represents the immediate reward at future step \(k\). Subsequently, we leverage the baseline from the Critic network to derive the advantage function \(\mathcal{A}(s_t, a_t)\):

\[\mathcal{A}(s_t, a_t) = R_t - V_\phi(s_t) \label{eq:advantage}\tag{4}\]

The policy loss aims to maximize the expected reward:

\[\mathcal{L}_p = -\frac{1}{T} \sum_{t=1}^{T} \log \pi_\theta(a_t | s_t) \mathcal{A}(s_t, a_t) \label{eq:policy95loss}\tag{5}\]

The value loss optimizes the Critic to accurately estimate the state value:

\[\mathcal{L}_v = \frac{1}{T} \sum_{t=1}^{T} \text{SmoothL1}\left(V_\phi(s_t) - R_t\right) \label{eq:value95loss}\tag{6}\]

To enforce the feature budget constraint and preserve attack stealthiness, we introduce a soft penalty formulation regulating the generated values:

\[\mathcal{L}_f = \max \left( 0, \sum_{i=1}^{\mathcal{B}_n} \sum_{j=1}^{d} X_a^{(i,j)} - \mathcal{B}_x \right) \label{eq:feature95budget}\tag{7}\] where \(X_a^{(i,j)}\) is the value of the \(j\)-th dimension in the \(i\)-th generated feature vector, and \(d\) is the total feature dimensionality. \(\mathcal{B}_x\) denotes the node feature perturbation budget predefined by the victim system.

The total optimization objective of the model, denoted as \(\mathcal{L}_{total}\), comprises the policy loss, value loss, and the feature budget penalty:

\[\mathcal{L}_{total} = \mathcal{L}_p + \lambda_v \mathcal{L}_v + \lambda_f \mathcal{L}_f \label{eq:total95loss}\tag{8}\] where \(\lambda_v\) and \(\lambda_f\) are hyperparameters balancing the respective loss components.

5 EXPERIMENTS↩︎

In this section, we comprehensively evaluate TIRBA on four benchmark datasets and compare it against existing state-of-the-art methods. Our experiments are designed to address the following four key research questions: (RQ1) Under the strict black-box single-node injection setting, can TIRBA achieve superior attack performance against various GNN victim models? (RQ2) Do the core components of the TIRBA framework (e.g., target-aware mechanism, guidance mechanism, and topology difference evaluation) effectively contribute to its overall attack efficacy? (RQ3) How does TIRBA’s attack performance fluctuate under varying budget constraints (such as node, edge, and feature budgets)? (RQ4) In practical scenarios, how does TIRBA visually alter the target node’s feature distribution to induce misclassification?

5.1 Experimental Setup↩︎

Datasets. We evaluated the performance of TIRBA on four widely-used real-world graph datasets. These datasets constitute citation networks: Cora, Citeseer [95], Cora-ML [96], and Pubmed [95]. Detailed dataset statistics are summarized in Table ¿tbl:table95datasets?.

Victim Models. To verify the generalization capability of the proposed attack, we selected four mainstream Graph Neural Network architectures as victim models: GCN [80], SGC [81], APPNP [82], and GAT [83].

Baselines. To evaluate TIRBA, we employ Clean (no attack) and Random baselines alongside four advanced node injection attacks: heuristic-based TDGIA [73], gradient-optimized PGD [55], [56], contrastive-driven GCIA [74], and RL-based G\(^2\)A2C [75]. All experiments strictly constrain the attack budget per target to 1 injected node and 1 edge.

5.2 Performance Comparison↩︎

To comprehensively validate TIRBA’s attack capabilities under a strict black-box single-node injection setting, we conducted extensive evaluations against five diverse baseline methods. The experiments span four widely adopted benchmark datasets (Cora, Citeseer [95], Cora-ML, Pubmed [95]) and four representative GNN architectures (GCN [80], SGC [81], APPNP [82], GAT [83]). As quantitatively detailed in Table 1, TIRBA consistently achieves the highest Misclassification Rate across various dataset and model combinations, demonstrating an exceptional generalization capability. Particularly in environments with challenging discrete feature spaces, TIRBA exhibits superior stability and adversarial strength. For instance, it markedly outperforms the highly competitive second-best baseline, PGD [55], [56], on the Cora dataset when attacking the SGC model. Furthermore, its attack success rate approaches an impressive 94% on the Pubmed [95] dataset. These compelling results conclusively demonstrate TIRBA’s robust efficacy and adaptability, even when operating under stringent query constraints and extreme injection budgets. In response to RQ1: In highly restrictive single-node black-box scenarios, TIRBA consistently and significantly outperforms all evaluated baselines. This explicitly proves its outstanding capability in jointly generating robust adversarial node features and edges under tight limitations.

5.3 Ablation Study↩︎

We conducted an ablation study on the Cora and Citeseer datasets [95] to validate TIRBA’s components (Fig. 2). The full model consistently outperforms its variants. Removing the class-center guidance (w/o Guidance) causes the severest performance drop, highlighting its necessity in reducing the search space. Omitting the target-aware interaction encoder (w/o Target-Aware) significantly lowers the Misclassification Rate, proving that target focus is essential to break local homophily. Finally, excluding the difference-aware evaluation (w/o Diff-Critic) degrades performance, validating its ability to capture topological anomalies. In response to RQ2: All three core components are indispensable for TIRBA’s robust attack efficacy.

5.4 Budget Analysis↩︎

To evaluate how attack budgets affect TIRBA’s efficacy, we analyzed the Misclassification Rate on the Cora and PubMed [95] datasets. As shown in Fig. 3 (), increasing node or edge budgets independently causes the misclassification rate to rise steadily before plateauing, indicating diminishing returns. Similarly, Fig. 3 () illustrates that increasing the feature generation budget quickly saturates the attack performance. Overall, TIRBA maintains a high misclassification rate even under strict, low-budget conditions. In response to RQ3: TIRBA’s attack power rises steadily and plateaus as node, edge, or feature budgets increase. Crucially, it achieves high attack success rates even under extremely tight budget limits.

5.5 Case Study↩︎

To visualize TIRBA’s attack effect, we employ T-SNE to map feature embeddings before and after node injection. Fig. 4 () visualizes the clean graph’s feature space, where the original target node (green star) resides accurately within its true class cluster (light red dots), surrounded by its intrinsic neighbors (blue dots). Fig. 4 () displays the post-attack feature space. The TIRBA-injected malicious node (red star) strongly perturbs the target node (black star). Tracking the black dashed line, the target node distinctly shifts from its original cluster and merges into an incorrect class area (light blue dots). This noticeable displacement confirms that TIRBA effectively alters target representations via topological perturbation, successfully inverting the model’s prediction. In response to RQ4: Visual analysis verifies that TIRBA’s injected nodes aggressively pull the target node across the feature space, forcing it to assimilate into a new class cluster and successfully inducing misclassification.

6 CONCLUSIONS↩︎

This paper introduces TIRBA, an end-to-end reinforcement learning framework for investigating GNN security vulnerabilities under black-box node injection attacks. Built on the standard A2C objective, TIRBA models feature generation and edge construction within a unified MDP and adapts the actor and critic to the heterogeneous graph attack space. To improve optimization in this large search space, the framework integrates three key components: a target-aware interaction encoder for feature-topology fusion, a class-center guidance mechanism for directed exploration, and a topology difference-aware critic for state-value estimation. Extensive experiments show that TIRBA consistently achieves higher misclassification rates than the evaluated baselines under restrictive attack budgets and across multiple victim architectures. It effectively induces prediction errors on target nodes while preserving the original graph elements. These results demonstrate the effectiveness, adaptability, and practical potential of TIRBA for analyzing and exposing the robustness limitations of GNN-based systems.Future work will explore stealthier and more effective NIA strategies.

References↩︎