Collateral Damage Constrained Backdoor Attacks on Graph Neural Networks

1 Introduction

Graphs, mathematical structures used to model pairwise relationships between objects, arise in a wide range of realworld applications, including social networks [Hamilton et al., 2017], recommendation systems [Fan et al., 2019], financial applications [Liu et al., 2021], and biological networks [Li et al., 2023]. To effectively model such relational data, Graph Neural Networks (GNNs) have emerged as a powerful learning paradigm [Kipf and Welling, 2017; Veliˇckovi´c et al., 2018; Xu et al., 2019; Zhang and Zitnik, 2020; Wu et al., 2020]. By iteratively aggregating information from neighboring nodes through the message-passing mechanism [Gilmer et al., 2017], GNNs have achieved state-ofthe-art performance on node classification [Liu et al., 2022; Yang et al., 2023; Yan et al., 2025].

∗Corresponding author

Despite achieving remarkable success, recent studies [Lyu et al., 2024; Li et al., 2025; Jin et al., 2025a] have shown that GNNs are vulnerable to backdoor attacks and even small perturbations can effectively manipulate model predictions. Typically, graph backdoor attack involves injecting triggers into target nodes to create a shortcut between the target and an adversary-chosen label. During inference phase, once these backdoors are activated by the trigger, the target nodes are misclassified into the malicious class. Following pioneering works such as SBA [Zhang et al., 2021] and GTA [Xi et al., 2021], methods like UGBA [Dai et al., 2023] and DPGBA [Zhang et al., 2024] focus on optimizing attack strategies to bypass specific defense mechanisms and enhance stealthiness. However, these methods overlook a critical phenomenon inherent to graph neural networks: due to the message-passing mechanism, malicious messages propagate during inference and affect nodes beyond the intended targets based on their receptive field, thereby amplifying the risk of backdoor exposure. We term this phenomenon Graph Backdoor Collateral Damage. As illustrated in Fig. 1, once the trigger is embedded into a target node, numerous non-target nodes within K-hop neighborhoods are also affected by the trigger, where K denotes the number of model layers.

The above observations are inseparable consequences of the message-passing mechanism. To successfully activate the backdoor, the trigger must induce a strong and transferable representation change through neighborhood aggregation. However, this propagation process inevitably contaminates clean nodes within the K-hop range, amplifying the scale of mispredictions and increasing the risk of exposure, thus posing a critical challenge:

How can a backdoor be reliably activated on target nodes while preventing malicious signals from poisoning surrounding clean nodes under the message-passing mechanism?

To address these challenges, we propose a novel framework, the Collateral Damage Constrained Backdoor Attack (CDCA), which introduces a joint training strategy from both structural and representational perspectives. First, CDCA explicitly introduces neighborhood-level constraints during the trigger generation process to localize backdoor effects under message passing mechanism. This design enables the model to manipulate unintended malicious diffusion to surrounding clean nodes while maintaining reliable activation on targets. Second, in the node selection scheme, we prioritize lowdegree, structurally less influential nodes to minimize structural perturbation. Additionally, we identify locally inconsistent nodes that are more susceptible to poisoning. This strategy allows for subtle attack perturbations that are effectively dissipated during propagation, thereby enhancing the attack success rate while mitigating the adverse impact on neighboring nodes. Our contributions are summarized as follows:

• We identify the Collateral Damage phenomenon and verify that due to the message-passing mechanism, existing attacks suffer from severe unintended malicious signal diffusion.
• We propose the CDCA, which jointly optimizes trigger generation with collateral damage constraints and employs a neighborhood-aware node selection strategy. This approach effectively localizes the backdoor impact, solving the trade-off between attack success and collateral damage.
• Extensive experiments on multiple benchmark datasets demonstrate that the proposed method significantly preserves the prediction accuracy of neighboring nodes while maintaining a high attack success rate, effectively constraining collateral damage on the graph.

2 RelatedWork

Graph backdoor attacks pose a significant threat in GNNs [Liu et al., 2024; Feng et al., 2024; Jin et al., 2026]. Attackers inject malicious triggers through subgraphs or feature perturbations in selected training nodes, creating shortcuts to predetermined malicious class [Zhang et al., 2025; Jin et al., 2025b]. Early methods such as SBA [Zhang et al., 2021] adopt fixed subgraphs as triggers. To enhance attack effectiveness, GTA [Xi et al., 2021] introduces a trainable trigger generator for sample-specific perturbations, improving success rates. UGBA [Dai et al., 2023] further refines target selection, reducing the attack budget and improving stealth by generating similar triggers and targets. Furthermore, One-to-N [Xu and Picek, 2023] can simultaneously manipulate predictions toward different target classes using different triggers. In the domain of self-supervised learning, GCBA [Zhang et al., 2023] utilizes trigger dispersion to poison the unlabeled pre-training process. Similarly focusing on stealth, DPGBA [Zhang et al., 2024] utilizes adversarial learning to create in-distribution triggers. On the other hand, some backdoor methods focus on perturbing node features while preserving graph topology to enhance stealth. For instance, CGBA [Xia et al., 2025] uses fixed feature triggers, while SPEAR [Ding et al., 2025] extends to adaptive ones. However, feature-based attacks inherently affect more original clean nodes, resulting in greater collateral damage. To mitigate this, our work employs structure-based methods.

3 Preliminary Analysis

In this section, we formally define the problem of graph backdoor attacks within an inductive semi-supervised node classification setting and identify the collateral damage phenomenon arising from the message-passing mechanism.

3.1 Notations

We use G = (V,A, E, X, Y) to denote an undirected graph, where V = {v1, . . . , vN} represents the set of N nodes. Graph structure is represented by an adjacency matrix A ∈ RN×N , while E ⊆ V ×V denotes the set of edges and the attribute matrix is given by X ∈ RN×d . In this paper, we focus on the backdoor attack for the semi-supervised node classification task within the inductive setting. Specifically, the training graph GT includes a small subset of labeled nodes VL ⊆ V with labels YL = {y1, . . . , yNL }. The remaining nodes of GT are unlabeled, denoted as VU. We denote VB = VL ∪ VU as the node set for the training graph, while the test nodes are denoted as VT , i.e., VT ∩ VB = ∅. Clean nodes are denoted as VC = VT \ VB. Moreover, a subset of target nodes Vp ⊂ VU is selected and injecting backdoor trigger gi into each vi ∈ Vp, resulting in embedded nodes vi ⊕ gi.

3.2 Threat Model

Attacker's Goal

The objective of the attack is to inject backdoor triggers to a set of target nodes and mislead the poisoned model θ∗ to misclassify target nodes as the target label yt, while retaining accurate classification predictions on clean nodes. We can formalize attack objective as follows:

Attacker's Knowledge and Capability

Like most graph attacks [Z¨ugner et al., 2020; Sun et al., 2020], attackers can access the training graph while remaining unaware of the victim GNNs model, including its architecture, training hyper-parameters, or defense mechanisms. Regarding capability [Zhang et al., 2024], the attacker is able to select a subset of nodes within a predefined budget, attach adaptive triggers to poison the graph. During inference, the attacker retains the ability to attach trigger to target nodes.

3.3 Collateral Damage Analysis

Due to the recursive message-passing mechanism of GNNs, node representations are learned by aggregating information from local neighborhoods. In GCN [Kipf and Welling, 2017], the embedding of a neighbor is directly influenced by the features of connected nodes via the layer-wise propagation rule:

where H(l) denotes the node embeddings at layer l (with H(0) = X), W(l) is the trainable weight matrix, and σ(·) is an activation function. The normalized adjacency matrix is given by ˆA = ˜D- 12 ˜A˜D- 1 2 , where ˜A = A+ IN includes self-loops and ˜D is the degree matrix.

Consider a set of clean neighboring nodes Vn adjacent to the target nodes Vp. When a target node is injected with a strong trigger optimized for a target class yt, the aggregation process propagates this malicious signal to neighboring clean nodes, shifting their predictive distributions towards yt. We define this unintended corruption of clean neighbors as Collateral Damage. Accordingly, we emphasize preserving the neighboring prediction accuracy in Eq. 1 by requiring:

Collateral damage manifests as a localized cluster of highconfidence target-class predictions. Such a conspicuous distribution creates a distinct statistical footprint, which not only degrades model utility on local clean nodes but also creates anomalies that render the backdoor vulnerable to detection.

4 Methodology

In this section, we present the proposed neighborhood-aware backdoor attack framework, which aims to achieve effective backdoor attacks while explicitly suppressing collateral damage on neighboring nodes. Two challenges must be addressed: (i) how to learn adaptive triggers that reliably induce target nodes to be classified as yt; and (ii) how to prevent the malicious signal from contaminating the neighboring clean nodes Vn, thereby preserving local clean accuracy and improving stealthiness. To tackle these challenges, CDCA consists of a target node selector that prefers low-centrality local outliers, and an adaptive trigger generator fg trained via bilevel optimization, and a surrogate model fs. The trigger generator is optimized not only for the targeted objective on Vp, but also with explicit constraints on neighborhood Vn. The framework is illustrated in Fig. 2.

4.1 Strategic Node Selection

To maximize the utilization of the attack budget, the selection of target nodes is critical. By analyzing the layer-wise propagation rule Eq. 2, we examine how degree affects message passing. For a target node injected with a trigger vp ⊕ gi , its embedding hvp is computed by aggregating messages as:

where dvp denotes the degree of vp and N(vp) represents the set of all neighboring nodes of vp and itself. Considering the contribution from the trigger gp specifically, the influence of gp is just a part of the whole term. This formulation reveals critical insights. First, the trigger signal facilitates widespread diffusion across the graph through numerous connections; second, message passing from clean neighboring nodes tends to dilute the malicious signal, reducing attack efficacy. Consequently, we prioritize lower-degree nodes in our node selection strategy. This approach minimizes information interference from neighbors, allowing the trigger pattern to better dominate the classification of the target node while reducing structural perturbation. From a representational geometry perspective, local outlier nodes positioned far from the classwise distribution center are more vulnerable to backdoor signals, while neighbors with locally consistent representations are more robust to the collateral damage. Collectively, these insights guide our selection of low-degree outliers, which can be effectively poisoned with minor perturbations while naturally constraining unintended damage.

To implement our strategy, we pre-train a benign GCN encoder to obtain node embeddings and compute a selection score S(vi) for each candidate node vi ∈ VU :

where c(vi) represents the centroid of vi's local neighborhood, and N(·) is a normalization function. By ranking the top-K nodes with the highest S(vi) as Vp, we select target nodes, ensuring that the injected trigger signal remains potent and is not diluted by the graph structure.

4.2 Neighborhood-Aware Trigger Generation

The target node selector identifies nodes with representative feature and structural patterns as attack entry points. Conditioned on the selected nodes, the adaptive trigger generator learns node-specific trigger subgraphs under multiple stealthiness and neighborhood-awareness constraints. To ensure that the learned triggers generalize to unseen test nodes, we adopt a bi-level optimization strategy, where the surrogate model guides trigger learning while the trigger generator balances attack effectiveness and neighborhood constraint. For each target node vi ∈ Vp, we generate a trigger subgraph gi and attach it to vi to form the poisoned graph.

Design of Trigger Generator

To generate adaptive triggers that align with the local semantics of attacked nodes, we design a trigger generator that conditions trigger construction on the feature representation of each target node. For a target node vi ∈ Vp with feature vector xvi , the generator produces both features and structure of the trigger subgraph. Formally, we project the node features into a latent space using a multi-layer perceptron:

which captures node-specific semantic information. Based on this representation, the generator simultaneously outputs the trigger node features and trigger adjacency structure:

whereWf andWa are learnable parameters for feature and structure generation.

Since graphs are inherently discrete, directly optimizing a continuous adjacency matrix is infeasible. Following prior work on binary neural networks [Xi et al., 2021], we apply a straight-through estimator to binarize the generated adjacency matrix and the resulting trigger is defined as gi = (Xgi , ˜Agi ), which is attached to the target node vi to construct the poisoned graph. During training, target nodes are expected to be misclassified into the target label yt. At inference time, the same generator fg is applied to test set, and the generated triggers activate the backdoor behavior, causing the compromised GNNs to predict the target class.

Attack Objective

Given a surrogate GNNs model fs parameterized by θs, we train fs on the poisoned graph to enforce targeted misclassification on targeted nodes while preserving supervision on clean labeled nodes. The attack objective is optimized as:

where ℓ(·, ·) denotes the cross-entropy loss and vi ⊕ gi indicates the target node with the attached trigger. Compared to existing backdoor attacks that emphasize attack generalization by encouraging a broad set of training nodes to be classified into the target class, our objective focuses on attack precision. Specifically, Lt is simultaneously optimized with respect to the surrogate model and the trigger generator, and serves as a loss for both θs and θg. We explicitly retain the standard supervision on the labeled clean node set VL to preserve the overall usability and predictive performance of the surrogate model, while restricting the targeted poisoned objective exclusively to the Vp. This design reflects a more realistic threat model, where the attacker aims to preserve attack effectiveness while ensuring that the backdoor effect is precisely localized to the target nodes.

Neighbor Contrastive Constraint

While the attack objective is clear, backdoor signals can inevitably propagate to neighboring clean nodes through message passing. To mitigate such collateral damage without altering any node features, we introduce a neighbor contrastive regularization that constrains the representations of clean neighbors around target nodes.

Let Vn = N(Vp)\Vp be the set of clean neighbors of target nodes, and let zv be the penultimate-layer embedding of node v extracted from fs. Due to the attacker's limited capability, we assume that the attacker cannot modify the original nodes or edges in the graph and has no access to the ground-truth labels of the unlabeled nodes.

Therefore, we construct supervision without relying on ground-truth labels for neighbors by utilizing pseudo-labels y′v obtained from the trained benign GCN during the node selection phase, which strictly adheres to a realistic black-box attack setting. Based on these pseudo-labels, we define (i) a target manifold C ′ = {v ∈ Vn : yv = yt} and (ii) a clean manifold C consisting of nodes whose pseudo-labels are not yt. Our evaluation across varying scenarios demonstrates that even with the inherently pronounced noise in OGB-arXiv or the small graph scale of Cora, the supervision signal is sufficient to separate the two distributions in the embedding space, proving empirically robust to guide the constraint process. We then formulate the neighbor contrastive constraint loss as:

where S(·) is the cosine similarity. This contrastive objective encourages neighbors to remain close to the clean manifold while being distanced from the target-class manifold. Nodes in C ′ are considered negative samples, representing nodes suffering collateral damage, and these instances are actively addressed during optimization.

Probability Suppression

While Lc constrains the geometry of the embedding space, it does not explicitly regulate the classifier's output confidence. To further prevent neighbors from being misclassified as the target class, we introduce a probability-level suppression term. Let P(yt | vu) denote the predicted probability of class yt for neighbor node vu. We impose a probability suppression, which can be formulated as:

Eq. 10 employs a margin-based penalty to avoid imposing a hard constraint that forces all neighboring nodes away from the target class because it is possible that some neighbors naturally belong to the target class. To prevent such neighbors from being over-penalized, we introduce a margin ϵ to relax the suppression constraint. This allows neighbors with a reasonable target-class confidence to remain unaffected, while only penalizing those whose target probability is abnormally amplified by backdoor propagation. Empirically, we set ϵ = 0.1 on small datasets, and ϵ = 0.02 on the larger OGB-arXiv dataset. Notably, these values are close to 1/|Y|, the expected probability of a random class, which is consistent with our analysis and empirical observations.

4.3 Bi-level Optimization

We jointly optimize the surrogate model and trigger generator using a bi-level optimization strategy. Model parameters after t iterations are denoted as θt and α is the learning rate for θ. In the lower-level optimization, the trigger generator θg is fixed and the surrogate model θs is updated as follows:

which ensures that the surrogate model accurately captures the backdoor behavior induced by the current trigger.

In the upper-level optimization, the surrogate model parameters are treated as fixed, and the trigger generator is updated by a weighted combination of attack effectiveness and collateral damage constraint objectives:

This optimization enables the trigger generator to adaptively ensure the attack success on Vp and suppression of unintended effects on neighboring clean nodes.

4.4 Enhancing Performance against Defenses

Alongside the sophisticated design in terms of collateral damage, it is also significant to boost the stealth of CDCA by bypassing existing defense methods. Inspired by previous work [Dai et al., 2023; Zhang et al., 2024], we integrate an Out-ofDistribution detection module into CDCA to compete with defenses. This detector fd uses a binary classification loss in a Min-Max game to differentiate clean images from generated triggers, aiming to make triggers indistinguishable from in-distribution data. It can be formulated as:

where vi is representative nodes selected from original graph and vg is from trigger nodes. We name the augmented variants as CDCA-D.

5 Experiments

In this section, we present the experimental setup, results, and analyses based on the following research questions: Q1: Can CDCA exceed the performance of leading backdoor attacks while addressing collateral damage? Q2: Can CDCA effectively circumvent defense mechanisms? Q3: How does the number of target nodes affect the performance of CDCA? Q4: How does each component affect overall model performance? Q5: How sensitive is the model to parameter variations?

5.1 Experimental Settings

Datasets

To evaluate the effectiveness of CDCA, we conduct experiments on four real-world datasets, i.e., Cora, CiteSeer, PubMed [Sen et al., 2008], and OGB-arXiv [Hu et al., 2020], which are commonly applied in inductive semi-supervised node classification. The summaries are provided in Table 1.

Baseline and Defense Methods

We compare CDCA against several state-of-the-art backdoor baselines, providing a comprehensive evaluation of their effectiveness and stealthiness. The attack methods include three structure-based methods: GTA [Xi et al., 2021], UGBA [Dai et al., 2023], and DPGBA [Zhang et al., 2024], as well as one feature-based method, SPEAR [Ding et al., 2025].

To comprehensively assess the robustness of our approach, we further evaluate the effectiveness of CADA against various backdoor defense strategies, including Prune [Dai et al., 2023], Isolate, and Outlier Detection (OD) [Zhang et al., 2024]. Prune removes low-similarity edges that violate the homophily property in graphs to disrupt trigger connections during both training and inference. Isolate enhances Prune by isolating anomalous nodes linked to these edges. Moreover, OD employs the DOMINANT [Ding et al., 2019] method to filter out nodes with high reconstruction errors from a graph autoencoder to remove anomalies during training.

Implementation Details

Following previous works [Dai et al., 2023; Zhang et al., 2024], we randomly assign the dataset into training, validation, and test sets in the ratio of 8:1:1. For evaluation, we randomly select half of the nodes in the test set as target nodes to calculate the Attack Success Rate (ASR) by embedding triggers. For the remaining clean nodes, we compute two utility metrics: Clean Accuracy (CA), which is evaluated on the original clean graph, and Prediction Accuracy (PAC), which measures the classification accuracy after trigger injection. We use GCN as the primary GNN model and vary the model layers among {2, 3, 4} to study the relationship between model depth and collateral damage propagation. We deploy a 2-layer MLP as the adaptive triggers generator. In all experiments, class 0 serves as the target class and the trigger size is limited to three nodes. The attack budget on size of target nodes Vp is set to {40, 40, 90, and 565} for Cora, CiteSeer, PubMed, and OGB-arXiv, respectively.

5.2 Backdoor Attack Performance (Q1)

We compare CDCA against baseline methods. Notably, as collateral damage spreads in the graph around the target nodes, exhibiting a ripple-like spreading pattern that gradually weakens with the number of hops. Therefore, we pay extra attention to the ASR and PAC of neighboring clean nodes of triggers, which are the most representative metrics for measuring the performance of CDCA. Specifically, we use ASRK and PAC-K to denote the ASR and PAC of the K-hop neighborhood for the trigger, where the 1-hop neighbors are the target nodes. Detailed results for the 2-layer GCN are summarized in Table 2, while results on OGB-arXiv for the 3-layer and 4-layer models are presented in Fig. 3. Based on these results, we have following observations:

• CDCA consistently outperforms all baselines in minimizing collateral damage by achieving the lowest ASR2 and highest PAC-2 across all datasets. This confirms that our neighbor contrastive constraints effectively confine the malicious influence to the target nodes.
• Despite the strict constraints on collateral damage, CDCA does not sacrifice attack effectiveness. CDCA

achieves comparable or even superior ASR on target nodes (ASR-1) compared to state-of-the-art baselines. This validates CDCA's utility in practical scenarios where attackers seek to maximize success rates while minimizing detectable side effects.

• We observe that OGB-arXiv exhibits lower collateral damage compared to other datasets. This phenomenon is likely attributable to its higher graph density and average node degree. The dense connectivity tends to dilute the toxicity from the trigger during the message-passing process, thereby naturally weakening the propagation of malicious signals to the neighborhood.

5.3 Performance Against Defenses (Q2)

We compete CDCA and CDCA-D with defense mechanisms. The pruning threshold for prune and isolate is set to 10% for samples with lowest cosine similarity; and 3% for nodes with highest reconstruction loss for OD. The resulting performances are summarized in Table 3. The results indicate that although the standard CDCA shows a decline in attack performance against defense methods, the enhanced CDCAD method demonstrates even better stealth across different datasets, surpassing UGBA and DPGBA. Besides, when no defenses are applied, CDCA-D do not exhibit a significant drop in ASR. Overall, these findings suggest that integrating the specific stealth modules into the CDCA framework significantly improves its performance against defense mechanisms while maintaining its effectiveness. This adaptability highlights our method's validity across various defensive environments, making it a robust choice for scenarios.

5.4 Impact of the Attack Budget (Q3)

We vary the number of target nodes as {30, 60, 90, 120, 150} to analyze the impact of the attack budget of CDCA. We report the results on PubMed in Fig. 4. Notably, ASR and PAC specifically refer to the metrics evaluated for target nodes ASR and the clean test set PAC in the following analysis. As expected, ASR shows an upward trend as the number of target nodes increases. Our method keeps outperforming the baselines at varying sizes of target nodes, which shows the effectiveness of CDCA. Moreover, the structural backdoor attacks exhibit slight fluctuations in PCA as the attack budget varies, while CDCA consistently maintains high prediction accuracy and reaches the highest level when the number of target nodes reaches 90, demonstrating intrinsic robustness. In contrast, the feature-based backdoor SPEAR shows a downward trend. Overall, our method achieves satisfactory performance even under a low attack budget.

5.5 Ablation Studies (Q4)

We conduct ablation studies to isolate the effectiveness of specific components within our framework. Specifically, the variant excluding the node selection module is termed CDCA\S, where target nodes are randomly selected. Furthermore, to verify the contributions of the neighborhood contrastive constraint and the probability suppression module, we construct variants by removing these components individually, denoted as CDCA\C and CDCA\P. The results using a 3-layer GCN as the test model are presented in Fig. 5. We observe that CDCA\S suffers from a decline in both ASR and PAC. This shows that the vulnerabilities exploited by the node selection strategy in low-degree nodes generalize effectively during the testing phase, exhibiting high attack efficacy even against high-degree hub nodes. Simultaneously, the drops in CDCA\C and CDCA\P verifies their critical function in confining malicious diffusion to preserve prediction accuracy.

5.6 Hyper-parameter Sensitivity Analysis (Q5)

To investigate the impact of hyperparameters on CDCA, we conduct a sensitivity analysis on β and γ, where β controls the strength of the neighborhood contrastive constraint and γ regulates the intensity of probability suppression. Specifically, we evaluate the performance by varying β within the set {0.1, 0.2, 0.5, 1, 2} and γ over the range {0.5, 1, 2, 3, 4, 5}. Using a 4-layer GCN as the test model on the PubMed dataset, and the other settings align with section 5.1. Fig. 6 reports the impact of β and γ on ASR and PAC, where we observe that a larger β enforces a clearer geometric separation between clean neighbors, thereby directly preserving the semantic integrity of neighbors and boosting PAC. While necessary for stealth, an excessively high γ imposes a strict penalty on target-class features within the neighborhood, which effectively counteracts the trigger's influence and leads to a compromise in ASR.

6 Conclusion

In this paper, we empirically verify that existing graph backdoor attack methods universally suffer from collateral damages. This critical phenomenon stems from the inherent message-passing mechanism of GNNs, which causes malicious trigger signals to diffuse beyond their targets, thereby compromising surrounding clean nodes. To address these issues, we investigate a novel research direction: conducting effective, collateral damage constraint graph backdoor attacks. Specifically, we propose CDCA, which incorporates a strategic node selector to target low-centrality outliers and employs neighbor contrastive constraints and probability suppression to strictly confine malicious influence. Extensive experiments on real-world datasets demonstrate that CDCA effectively minimizes collateral damage across multi-hop neighbors when backdooring various target GNN models, while simultaneously maintaining a high ASR and PAC. Building on our insights into collateral damage, we expect that defense mechanisms can be improved in the future.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (No.92370111, 62272340, 62422210, 62276187).