Robustness Inspired Graph Backdoor Defense

Q1: defense against nettack

We would like to kindly clarify that the problem definition of Nettack [1] is fundamentally different from that of a backdoor attack. In Nettack, the goal is to modify the node features and graph structure to alter the prediction of a specific target node. In contrast, a backdoor attack aims to poison the GNN model to establish a correlation between the backdoor trigger and the target class. Consequently, any node attached with the backdoor trigger tends to be predicted as the target class, while the backdoor attack simultaneously seeks to maintain clean accuracy on unaffected nodes. Therefore, Nettack falls outside the scope of our paper. We thank the reviewer for pointing this out and will include this discussion in a future version of our paper.

Q2: concerns on insufficient supervision information

One important goal of a backdoor attack is to maintain clean accuracy on clean nodes in the backdoored model. Thus, attackers typically avoid introducing too many triggers [2][3][4] into the poisoned graph, as doing so would lead to a significant performance drop in clean accuracy, making the backdoor attack easily detectable and considered a failure. For example, in UGBA, the attacker introduces only 160 backdoor triggers into the OGB-arxiv dataset, which contains a total of 169,343 nodes.

During a backdoor attack, the model is trained using gradient descent on both poisoned nodes and clean nodes, which allows the model to maintain clean accuracy on clean nodes. This clean accuracy is primarily achieved through training on the clean nodes. As shown in the hyperparameter analysis in Section 5.4, our precision in detecting poisoned target nodes consistently exceeds 95%, meaning that only a few clean nodes are filtered out. This ensures that the gradient descent process on clean nodes remains largely unchanged, resulting in the same level of clean accuracy.

[1] Adversarial attacks on neural networks for graph data, KDD 2018.

[2] Graph Backdoor. USENIX Security 2021.

[3] Unnoticeable Backdoor Attacks on Graph Neural Networks. WWW 2023.

[4] Rethinking Graph Backdoor Attacks: A Distribution-Preserving Perspective. KDD 2024.

We thank the reviewer for recognizing the valid theoretical and technical details, and comprehensive experiments of our work. Below is our point-by-point response to the reviewer's comments:

W1: efficiency of RIGBD

• Compared to vanilla GNN training, our method only requires performing inference K times, followed by retraining a GNN model. Specifically, the time complexity for training a vanilla backdoored model is $O(LT(NM^² + |E|M))$, where: $L$ is the number of GNN layers, $N$ is the number of nodes, $E$ is the number of edges, $M$ is the hidden dimension, and $T$ is the number of training epochs. In comparison, our framework involves $K$ additional inferences on the entire graph and $T$ epochs for retraining, leading to a time complexity of: $O(L(2T + K)(NM^² + |E|M))$. After simplifying this expression, it becomes clear that both complexities belong to the same Big O class, which is: $O(L(NM^² + |E|M))$. This means that the time complexity of our framework is asymptotically equivalent to that of training a vanilla backdoored model. The constant factors introduced by the additional steps in our framework do not change the overall order of complexity.

• As demonstrated in hyperparameter analysis in Section 5.4, with a appriorite value of drop ratio $\beta$, though a small value of $K$ will not lead to recall of poison node detection as good as the case with a large $K$, our robust training strategy can already help us achieve a strong performance in defending against backdoor attack, for example, in OGB-arxiv dataset, with $\beta=0.5, K=2$, we degrade the ASR from over 90% to 0.67%. This further enhance the flexibility and efficiency of our RIGBD.

• Compared to RobustGCN, which learns attention weights during the training of a GCN, our framework may be more efficient. Additionally, methods like Randomized Smoothing rely on more epochs of adversarial training and multiple rounds of inference, making them less time-efficient. ABL requires warm-up epochs followed by isolation to split the dataset, which also adds time compared to simple training. The table below shows the running time of RIGBD compared to other baselines on Cora dataset. The results show that our RIGBD is more efficient than most robust learning strategies.

• Our RIGBD produces a backdoor-robust model, meaning no further refinement is needed once the model is trained. In contrast, inference-time defense methods require a defense module to be applied during every inference. When implemented in real-world applications, inference-time defense methods are expected to incur a total defense cost that easily surpasses the cost of training a backdoor-robust model.

W2: performance on heterophilic graph

Thank you for your suggestion. Following your advice, we conducted experiments to evaluate the performance of RIGBD on heterophilic graph datasets Wisconsin, Cornell and Texas. The attack method used is DPGBA, with 20 poisoned nodes during training, and other settings follow those described in Section 5.1. The results are presented in the table below. It is evident that RIGBD achieves consistently strong performance in defending against backdoor attacks while maintaining clean accuracy. The recall and precision of poisoned node detection further demonstrate that our method remains robust when applied to heterophilic graphs.

Furthermore, in Line 314, we cited that in Appendix F, we compare the prediction variance of low-degree nodes from heterophilic graphs against poisoned nodes. For your convenience, we present the results in the table below. The results reveal that for heterophilic graphs such as Wisconsin, Cornell, and Texas, the results reveal that prediction variance of poisoned nodes remains significantly higher than that of clean nodes, even for those with low degrees.

We thank the reviewer for recognizing the novelty, valid theoretical and technical details in our work. Below is our point-by-point response to the reviewer's comments:

W1: experiments on injecting backdoors in the spectral domain

We thank the reviewer for pointing out the related work; however, there is no code available for this method. Due to time constraints, we are unable to implement their approach during the rebuttal.

W2 & Q3: robustness of poisoned node selection

In Line 314, we cited that in Appendix F, we compare the prediction variance of low-degree nodes from both homophilic and heterophilic graphs against poisoned nodes. For your convenience, we present the results in the table below. The results reveal that for heterophilic graphs such as Wisconsin, Cornell, and Texas, the prediction variance gap between low-degree and poisoned nodes is smaller compared to homophilic graphs. However, the prediction variance of poisoned nodes remains significantly higher than that of clean nodes, even for those with low degrees.

To further address your concerns, we conducted additional experiments to evaluate the performance of RIGBD on heterophilic graphs. The attack method used is DPGBA, with 20 poisoned nodes during training, and other settings follow those described in Section 5.1. The results are presented in the table below. It is evident that RIGBD achieves consistently strong performance in defending against backdoor attacks while maintaining clean accuracy. The recall and precision of poisoned node detection further demonstrate that our method remains robust when applied to heterophilic graphs.

Q1: non-subgraph graph backdoor attacks

It is not clear whether the reviewer refers to a backdoor attack with a trigger size of 1, i.e., where the backdoor trigger is a single node instead of a subgraph. If this is the case, in line 479, we cited Appendix O, where we present the results of RIGBD when defending against a backdoor attack with a trigger size of 1. The results consistently demonstrate strong performance in defending against the attack while maintaining clean accuracy. We would be happy to address any additional concerns if the reviewer could kindly provide further clarification on the question.

Q2: how to defend against all-to-all backdoor attacks (different samples have different target labels)

Though all-to-all backdoor attacks aim to have different target predictions for different samples, a successful backdoor attack means that for a node with and without a backdoor trigger, the prediction results on the target node will drastically change. Thus, the core idea of RIGBD—that prediction variance is a crucial indicator for identifying poisoned target nodes—still works. To adapt to the case where different target nodes have different target labels, instead of ranking nodes in descending order and selecting the top-ranked nodes until a node label differs from the previous one, we can adjust the method by ranking nodes in descending order and manually setting a threshold to filter out those nodes with prediction variance higher than that threshold as poisoned target nodes. Finally, we can follow the same robust training strategy as in RIGBD. Overall, when adapting to all-to-all backdoor attacks, we only need to slightly adjust RIGBD by filtering out poisoned target nodes using a manually set threshold.

We thank the reviewer for recognizing the valid theoretical and technical details of our work. Below is our point-by-point response to the reviewer's concerns and comments:

W1: hyperparameter selection

• According to our hyperparameter analysis in Section 5.4 and Appendix L, our RIGBD consistently achieves strong performance in defending against backdoor attacks and maintaining clean accuracy across different hyperparameter selections. Specifically, while smaller values of $\beta$ and $K$ may result in poorer recall performance for poisoned node detection compared to larger values, our method still achieves strong performance in reducing ASR, which can be attributed to our robust training strategy.

• Based on our theoretical analysis in Theorem 2 and empirical results in Section 5.4, a larger $\beta$ typically results in better recall performance for poisoned node detection while maintaining stable precision, i.e., minimal impact on clean nodes. This, in turn, leads to improved defense against backdoor attacks and consistent clean accuracy.

• Overall, our RIGBD demonstrates robustness to hyperparameter selection, supported by both theoretical and empirical evidence.

Q1: experiments on SBA

Thank you for your suggestion. Following your advice, we conducted experiments on Cora, Pubmed, and OGB-Arxiv using SBA as the attack method. Other settings follow those described in Section 5.1. The results are shown in the table below. It is evident that RIGBD consistently achieves strong performance in defending against backdoor attacks while maintaining clean accuracy across all datasets.

Q2: adaptive attacks

We would like to kindly clarify that UGBA and DPGBA are inherently adaptive attacks. Specifically, both methods introduce a learnable trigger generator that generates backdoor triggers based on the target node's attributes. Our RIGBD consistently demonstrates strong performance in defending against both UGBA and DPGBA.

We thank the reviewer for recognizing the novelty, sound theoretical and technical details, as well as the extensive experiments in our work. Below is our point-by-point response to the reviewer's comments:

W1: deep discussion on the mechanism of dirty-label backdoor attack

As defined in the problem statement in Section 3.1 and described in the introduction, dirty-label graph backdoor attacks involve linking a backdoor trigger to a small set of target nodes, which are then assigned a target class to form a poisoned graph. When a GNN model is trained on a backdoored dataset, it learns to associate the presence of the trigger with the target class. Consequently, during inference, the backdoored model misclassifies test nodes with the trigger attached as belonging to the target class, while still maintaining high accuracy on clean nodes without the trigger. This attack framework is well-studied, with representative works such as GTA [1], UGBA [2], and DPGBA [3]. Empirical results show that with only a small set of poisoned nodes, these attack frameworks can typically achieve over a 90% attack success rate across various datasets. Such attacks pose a significant threat to the application of graph neural networks in real-world scenarios, such as social media networks, where attackers can easily create fake accounts as backdoor triggers and connect them to target user nodes, misleading the model into predicting the user as the target class.

W2: more discussion on DPGBA and baselines

We have included the discussion among baselines and RIGBD in Appendix H.4. Apologies for not clearly mentioning this in the main pages.

• As mentioned in [3], although GTA [1] and UGBA [2] achieve good attack results, both suffer from the issue that their generated backdoor triggers are outliers compared to clean nodes. Thus, a simple outlier detection method could defend against such attacks. DPGBA [3] proposes generating backdoor triggers that share similar node features with clean nodes, making it difficult to defend against with trivial methods. We believe that future advanced attack methods could enhance attack performance while simultaneously generating triggers capable of bypassing simple defense methods. Therefore, it is of vital importance to propose defense methods like RIGBD to counter such attacks.
• Since graph backdoor attack methods [1][2][3] inherently belong to the category of poisoning attacks, we include GNNGuard and RobustGCN as baselines because both have the ability to mitigate the influence of malicious neighbors. This may reduce the impact of backdoor triggers, as these triggers are neighbors of the target nodes. However, their defense performance is not satisfactory, especially when the generated triggers are similar to the target nodes.
• The core idea of ABL is that the model quickly learns backdoored data, after which a local gradient ascent technique is used to trap the loss value of each example. Although it was initially designed for DNNs, this defense framework can be easily adapted to GNNs. However, their framework requires manual tuning of the isolation ratio, and a high isolation ratio inevitably leads to a performance drop on clean data when their losses are trapped. This significantly reduces the method's utility in real-world applications, as defenders typically do not know the number of poisoned target nodes.
• To the best of our knowledge, at the time of submitting our work, there is no published work that specifically aims to defend against dirty-label node-level graph backdoor attacks that involve generating a backdoor trigger and linking it to the target node.

[1] Graph Backdoor. USENIX Security 2021.

[2] Unnoticeable Backdoor Attacks on Graph Neural Networks. WWW 2023.

[3] Rethinking Graph Backdoor Attacks: A Distribution-Preserving Perspective. KDD 2024.

W3: comparison to influence function

Regarding the influence function, we appreciate the reviewer for pointing this out. Existing work [4] explores approximating the influence of node removal and edge removal on the change in representation of other nodes. Another work [5] approximates the influence of node/edge removal on the change in model parameters. Since changes in model parameters do not directly reflect changes in node representations and logits prediction, we focus on discussing related work [4] here. However,

(i) their framework and theoretical analysis are based on Simple Graph Convolution rather than GCNs.

(ii) For edge removal, the time complexity of measuring the influence of each edge in the entire graph is $O(n|E||\theta|^2 + |\theta|^3)$, where $|\theta|$ represents the number of model parameters, $|E|$ is the number of edges, and $n$ is the average number of affected nodes after dropping a specific edge. This can be time-consuming for dense graphs and deep graph neural networks. In contrast, the time complexity of our method is $O(LK(NM^2 + |E|M))$, where $L$ is the number of GNN layers, $N$ is the number of nodes, and $M$ is the hidden dimension. Typically, $LKM \ll n|\theta|^2$ and $LNKM^2\ll |θ|^3$. Thus, our method is typically more time-efficient compared to the influence function method.

(iii) As the reviewer mentioned, their method does not require fine-tuning the poisoned model. However, if we adopt the influence function without fine-tuning the poisoned model, each time we perform inference on a new poisoned graph, we would need to check the influence of each edge again, which will significantly degrade the efficiency and utility.

[4] Characterizing the Influence of Graph Elements. ICLR 2023

[5] GIF: A General Graph Unlearning Strategy via Influence Function. WWW 2023