Robustness Inspired Graph Backdoor Defense
Authors: Zhiwei Zhang
Minhua Lin
Junjie Xu
Zongyu Wu
Enyan Dai
Suhang Wang
Venue: ICLR 2025 Oral (2025)
Keywords: Backdoor Defense
Graph Neural Network
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: Graph Neural Networks (GNNs) have achieved promising results in tasks such as node classification and graph classification. However, recent studies reveal that GNNs are vulnerable to backdoor attacks, posing a significant threat to their real-world adoption. Despite initial efforts to defend against specific graph backdoor attacks, there is no work on defending against various types of backdoor attacks where generated triggers have different properties. Hence, we first empirically verify that prediction variance under edge dropping is a crucial indicator for identifying poisoned nodes. With this observation, we propose using random edge dropping to detect backdoors and theoretically show that it can efficiently distinguish poisoned nodes from clean ones. Furthermore, we introduce a novel robust training strategy to efficiently counteract the impact of the triggers. Extensive experiments on real-world datasets show that our framework can effectively identify poisoned nodes, significantly degrade the attack success rate, and maintain clean accuracy when defending against various types of graph backdoor attacks with different properties. Our code is available at: https://github.com/zzwjames/RIGBD.

Published as a conference paper at ICLR 2025
ROBUSTNESS INSPIRED GRAPH BACKDOOR DEFENSE
Zhiwei Zhang Minhua Lin Junjie Xu
Zongyu Wu
Enyan Dai
Suhang Wang
The Pennsylvania State University (zbz5349, mf15681, junjiexu, zongyuwu, emd5759, szw494 @ edu
ABSTRACT
Graph Neural Networks (GNNs) have achieved promising results in tasks such as node classification and graph classification. However, recent studies reveal that GNNs are vulnerable to backdoor attacks, posing significant threat to their real-world adoption. Despite initial efforts defend against specific graph back- door attacks, there is no work on defending against various types of backdoor attacks where generated triggers have different properties. Hence, we first empir- ically verify that prediction variance under edge dropping is crucial indicator for identifying poisoned nodes. With this observation, we propose using random edge dropping to detect backdoors and theoretically show that it efficiently distinguish poisoned nodes from clean ones. Furthermore, we introduce a novel robust training strategy to efficiently counteract the impact of the triggers. Exten- sive experiments on real-world datasets show that our framework can effectively identify poisoned nodes, significantly degrade the attack success rate, and maintain clean accuracy when defending against various types of graph backdoor attacks with different properties. Our code is available at: gifuubcom//zwjjaessR(CCE)
INTRODUCTION
Graphs are pervasive in real world such as social networks Fann et al. 2019). molecular graphs (Mansimov et al., 2019), and knowledge graphs (Liu al. 2022). Graph Neural Networks (GNNs) have shown great ability in node representation learning on graphs. Generally, GNNs adopt a message- passing mechanism that updates a node's 's representation by iteratively aggregating information from its neighbors. The resulting node representations retain both node attributes and local graph structure information, benefiting various downstream tasks such as node classification (Hamilton et al. 2017] Kipf & Welling, 2016: Velickovic et al., (017)) and graph classification (Xu et al. 2018).
Despite their great performance, recent studies (Dai et al. 2023 Xi et al., 2021 Zhang et al. 2021 2024) show that GNNs are susceptible to backdoor attacks. Generally, backdoor attacks involve generating and attaching backdoor triggers to a small set of target nodes, which are then assigned target class. These triggers be predefined or created by trigger generator and usually take the form of a node or subgraph. 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 will misclassify test nodes with the trigger attached as belonging to the target class, while still maintaining high accuracy on clean nodes without trigger attached. Backdoor attacks on GNNs are particularly concerning due to their potential impact on critical real-world applications such healtheare and financial services. For instance, in medical diagnosis networks, an attacker could embed backdoor triggers into the training data, leading the GNN model to misclassify certain medical conditions when the trigger present.
Thus, graph backdoor attack and defense are attracting increasing attention and several initial efforts have been taken (Xi al. 2021; Zhang et al. 2021 2024 Daii et al. (023). For example, the seminal work SBA (Zhang et al. 202T) adopts randomly generated graphs as triggers for graph backdoor attack. To improve the attack success rate, GTA (Xi et al. 2021) adopts a backdoor trigger generator to generate more powerful sample-specific triggers. Observing that the backdoor trigger and target nodes tend to have low feature similarity, Dai et al. (2023) propose a defense method called Prune, which removes edges that connect nodes with low cosine similarity. It significantly reduces the attack success rate (ASR) of previous works. To improve the stealthiness of backdoor attacks, they proposed unnoticeable backdoor attack method UGBA by maximizing the cosine similarity between backdoor

---

Published as a conference paper at ICLR 2025
triggers and target nodes. Zhang al. (2024) show that backdoor triggers tend to be outliers which can be removed with graph outlier detection (OD). To address this, they further proposed DPGBA which can generate in-distribution triggers. Despite initial efforts backdoor defense, they generally utilize backdoor specific properties to defend against specific backdoor and are ineffective across various types of backdoor triggers and attack methods.
Therefore, in this paper, we study an important problem of developing an effective graph backdoor defense method against various types of backdoor triggers and attack methods. In essence, we are faced with two challenges: (i) How to efficiently and precisely identify poisoned nodes and backdoor triggers, even when those triggers are indistinguishable from clean nodes? (ii) How minimize the impact of backdoor triggers when some of the triggers are not identified? In an attempt to address these challenges, we propose a novel framework Robustness Inspired Graph Backdoor Defense (RIGBD). To efficiently and precisely identify poisoned nodes, we empirically show in Section 3.2 that removing edges linking backdoor triggers typically leads to large prediction variance for poisoned target nodes. Based this observation, we propose training a backdoored model with specially designed graph convolution operations on a poisoned graph, performing random edge dropping, and identifying nodes with high prediction variance as poisoned nodes. With candidate poisoned nodes and identified target class, we propose a novel robust GNN training loss, which minimizes model's s prediction confidence on the target class for poisoned nodes to efficiently counteract the impact of the triggers. Such strategy is effective even if part of poisoned nodes are not identified in the training set.
Our main contributions are: (i) We empirically verify that poisoned nodes typically exhibit large prediction variance under edge dropping. (ii) Theoretical analysis guarantees that our specially designed graph convolution operations can precisely distinguish poisoned nodes from clean nodes through random edge dropping. (iii) We propose a novel training strategy to train a backdoor robust GNN model even though some poisoned nodes are not identified. (iv) Extensive experiments show the effectiveness of RIGBD in defending against backdoor attacks and maintaining clean accuracy.
2 RELATED WORK
Graph Backdoor Attacks. SBA (hang et al. 2021) is seminal work graph backdoor attacks, which adopts randomly generated graphs as triggers. GTA (Xi et al. (02I] adopts a backdoor trigger generator to generate more powerful sample-specific triggers to improve the attack success rate. UGBA (Dai et al.] (023) introduces an unnoticeable loss function aimed at maximizing the cosine similarity between backdoor triggers and target nodes to improve the stealthiness of their attack. DPGBA ZZang et al. 2024) introduces an outlier detector and uses adversarial learning to generate in-distribution triggers, addressing low ASR or outlier issues in existing graph backdoor attacks. More about graph backdoor attacks are in Appendix A
Graph Backdoor Defense. UGBA (Dai al., 2023) denotes that the attributes of triggers differ significantly from the attached poisoned nodes in GTA (Xi et al.) 2021). thereby violating the homophily property typically observed real-worls graphs. Thus they propose a defense method called Prune, which removes edges that connect nodes with low similarity. DPGBA (Zhang et al.) 2024) further indicates that although the triggers in UGBA (Dai et al. 2023) may demonstrate high similarity to target nodes, the triggers in both UGBA (Dai et al. (023) ) and GTA (Xi et al. 2021) are still outliers. Thus they propose a defense method called OD, which involves training a graph auto-encoder and filtering out nodes with high reconstruction loss. More details about backdoor
defense in non-structure data (Li et al. 2021a) and robust GNNs (Zhang & Zitnik 2020 Zhu et al..
2019 Wang et al.) (021) are shown in Appendix A Our work is inherently different from theirs: (i) We aim to defend against graph backdoor attacks regardless of the trigger attributes; (ii) we design a novel and theoretically guaranteed method to precisely identify poison nodes, aiming degrade the attack success rate (ASR) without compromising clean accuracy.
3 PRELIMINARY
3.1 BACKGROUND AND PROBLEM DEFINITION
We use 9= (V.E,X to denote an attributed graph, where V = (ei...., is the set of N nodes,
3 C V x V is the set of edges, and X {x1,..., xN) is the set of attributes of V. A E NRNN is
2

---

Published as a conference paper at ICLR 2025
the adjacency matrix of G, where A.y 1 if nodes o2 and ij are connected; otherwise Aúj = 0. In this paper, we focus on the inductive setting. Specifically, during the training stage, we are provided with a graph Gr (Vr, Xr). We use Vcc - Vr and VB S VT to denote the clean node set and backdoored node set, respectively. A node 1/ E Vc is clean and labeled with the clean label yi. whereas node U/ E V/ is backdoored and laheled with the target label yt- The set VT \ (Ve U VB) denote the unlabeled nodes. The set of edges linking & E VB and the trigger 9i is denoted as EB E ET. During the inference stage, we are given an unseen graph GV = (Vu, Ev, Xx) where VU = Vuc U VUB. A node U/ E Vuc is clean, while node v2 E VUB is backdoored. Notably, Go is disjoint from the training graph Gr, meaning Vu n Vi 0. The set of edges linking u E VUB and the trigger Yj is denoted by εuB E Eg. The neighbors of node U; are denoted as (i)..
Threat Model.
The attacker aims to add backdoor triggers, i.e., nodes or subgraphs, to a small set of target nodes VB in the training graph and label them as a target class yt. so that GNN trained on the poisoned graph will (i) memorize backdoor triggers and be misguided to classify nodes attached with triggers as Yri and (ii) behave normally for clean nodes without triggers attached. Specifically, given Vy E V as a set of target nodes, the attacker attaches the crafted triggers 9; = (X" A to the (s). 9s). where a(-) is the attachment operation. Then, the attacker assigns VB with target class ye to form backdoored graph Gr.
node e VB and get poisoned node i. a(v;
Defender's Knowledge and Capability. During the training phase, the defender has access to the backdoored graph Gr to train a classifier for node classification. However, the defender lacks information about which nodes belong to the backdoor node set VB and the target class yt- During the inference phase, the defender is presented with an unseen backdoored graph Gu for node classification.
Graph Backdoor Defense. With the above description, our defense problem is formally defined as: Given a backdoored graph Gr, we aim to train a backdoor-free GNN model I on GT so that it can defend against backdoor triggers during inference on an unseen backdoored graph Gv. while maintaining accuracy on clean data. This is formally defined as miny E (f (f(())) yr) (f
Eejevor ((f())) yt). where I is the classification loss.
3.2 PREDICTION VARIANCE CAUSED BY TRIGGER EDGE DROPPING
Generally, graph backdoor attacks establish an edge between a trigger and a target node (Xi et al.)
100
Clean Edger
Clean Edges
Percantage (8)
Trigger Edges
Percentage 151
05
Trigger Fdges
2021; Dai et al. [023] Zhang et al. 2021), ), which
60
60
means the backdoor attack will fail if the edge linking the trigger and the target node is dropped. Furthermore, an explicit requirement for backdoor attacks is that the backdoored GNN model fo be- haves normally for clean nodes without triggers attached. Based on the analysis above, we make an assumption: given a backdoored graph Gr, if the trigger edge e; E & linking the target node va logits of the backdoored model for the poisoned target node U; will typically change significantly, compared to the prediction change on the nodes connected by clean edges ej E Er \ &B when these edges e, are dropped.
20
0.0
0.00 0,02 0.06 0.06 0.10
Prediction Veriance
Prediction Verience
(a) Single Edge
(b) Two Edges
Figure 1: Prediction variance caused by dropping trigger edges and clean edges.
E V/ and trigger is dropped, the prediction
To empirically verify our assumption, we conduct the following experiments: Given a backdoored graph, we first pretrain a backdoored model on this graph. For each node, we then iteratively drop each of its neighbors one by one and measure the prediction variance caused by dropping trigger edges& Eg and clean edges Er \ Eg. respectively. We perform experiments on OGB-arxiv (Hu et al., 2020) with 565 triggers. The attack method is DPGBA (Zhang et al. 2024). The model architecture is a 2-layer GCN (Kipf & Welling, 2016). From the results shown Fig. (a), it is evident that dropping adversarial edge connecting backdoor trigger will result in a much larger prediction variance than dropping clean edges. More results on other datasets can be found in Appendix
Thus, an intuitive method for identifying backdoor trigger or poisoned target node is to examine each edge individually. For instance, in a 2-layer GCN (Kipf & Welling 2016). we remove one of its neighbors time for each node and conduct inference based on the remaining 2-hop neighbors. By observing prediction changes with each neighbor removal, we estimate the likelihood of an edge being linked to the backdoor trigger: greater prediction change indicates higher probability.
3

---

Published as a conference paper at ICLR 2025
However, this method has several issues: (i) Scalability: For graphs with high average degree, this method is computationally expensive. Specifically, for an L-layer GCN, the time complexity is OLLNd (d M)), where d is the average degree, N is the number of nodes, and M denotes the feature dimension. The analysis is in Appendix C As d grows, the time complexity grows exponentially with the power I., making it impractical for dense graphs. (ii) Utility: When the backdoor trigger is subgraph with multiple edges linking it to target node, examining each edge individually becomes ineffective. As shown in Fig. (b), when two edges linking a trigger and target node, on the DGB-arxin dataset, most of the prediction variance caused by dropping trigger edges shows similar values to those caused by dropping clean edges, rendering the intuitive method ineffective.
Therefore, while prediction variance caused by edge dropping is a crucial indicator for identifying poisoned nodes or backdoor triggers, it is essential to develop a method that can (i) accurately identify poisoned nodes, even when multiple edges connect a trigger to target node; and (ii) reduce the time complexity to scale linearly with the average degree, thereby improving scalability.
Vulnerability Clean Model to Backdoor Triggers. Even if we can remove backdoor triggers from the training dataset, a graph backdoor trigger can still potentially lead to a suc- cessful attack the attacker can craft backdoor trigger that
Table 1: ASR on clean model.
Cora
OGB-arxiv
Rand. ASR 14.29
2.5
ASR 34.72
5.4
mimics the neighbor of nodes (Zhang et al., 2024) from the target class. To verify this, we adopt the DPGBA (Zhang et al.) 2024) attack method and conduct experiments by removing the backdoor triggers from the training dataset. We then train a 2-layer GCN on this clean dataset and report the attack success rate (ASR) on the test dataset, as shown in Table D The Random ASR is calculated by G as a reference, where C is the number of classes for each dataset. As shown in the table, even when the model is trained on a clean dataset, it can still react to a backdoor trigger that mimics the neighbor of nodes from the target class. Thus, simply removing the backdoor triggers from the training dataset insufficient to defend against graph backdoor attacks.
I
METHODOLOGY
Our preliminary analysis shows that (1) remov- ing adversarial edges linking triggers and poi- soned target nodes typically results in higher prediction variance for poisoned target nodes; (2) simply removing backdoor triggers from the training dataset is insufficient to protect against backdoor triggers that mimic the distribution of neighboring nodes from the target class. To utilize the above information and solve our prob- lem, face two challenges: (1) How to de-
Backdoored Graph
Stage 1: Pre-trir
Unbabe abwied Nodes
Trahnolc # Frozon
Bacedoored Model
Cancidons Palsened Nodes
Triggr Graph
Edge Dropping
Staee ENN Trawing
Stage ideraaly risared Nedke
Backdoored Model Is $0
Rebust
vise an efficient method to find poisoned target
/
nodes? (2) How minimize the impact of back-
Figure 2: Framework of RIGBD
door triggers without degrading the clean accuracy? To address the above challenges. novel framework RIGBD is proposed. Specifically, to address the first challenge, we theoretically and empirically verify that random edge dropping is an efficient way to distinguish the poisoned target nodes from clean nodes. To address the second challenge, we propose to minimize the prediction confidence of poisoned target nodes on the target class. This encourages the model to counteract the impact of the trigger. Next, we give the details of each component.
4.1 IDENTIFYING POISONED TARGET NODES BY RANDOM EDGE DROPPING
To overcome the scalability and utility issues of the intuitive method of dropping each edge individu- ally, we propose novel random edge dropping framework. Specifically, we define a randomized edge drop noise for adjacency matrix A that removes each existing edge with the probability 3 as
P(Euj 0 Aij 0) 1, P(Eg 1 A,
B, P(e.j = 0 Aig 1) 1 -3, (1)
where Ei = 1 means dropping edge eig. We denote A @ e as the perturbed graph, with @ the element-wiss XOR operator. Given backdoored graph GT and corresponding adjacency matrix
4

---

Published as a conference paper at ICLR 2025
A, we first train the backdoored node classifier fo on this poisoned graph Gr and get the prediction logits P, for each node 04 E Vz, i... P: = fo(A; Then, we independently add random noise to the original adjacency matrix A for K times using the operation A $ e, resulting in the noisy matrices A,,..., Ax. Similarly, we obtain the prediction logits p fo(A (Agg; 0)) for node i; on each perturbed graph. Then, the prediction variance of node in against random edge dropping is:
s11) = Σ KL(P: p!).
(2)
where KL(P:. p denotes Kullback-Leiin divergence between P, and p With an appropriate K and 8, is highly likely that an edge connecting the backdoor trigger will be removed in one or more of the perturbed adjacency matrices, causing significant prediction variance for poisoned nodes.
However, it is unclear whether this method can also lead to large prediction variance for clean nodes, potentially compromising our ability to differentiate between poisoned target nodes and clean ones. To address this concern, we propose to obtain each node representation only based on its neighbors. Specifically, when performing inference to obtain the prediction logits ps and p (before and after random edge dropping), the operation in each layer can be written as:
H (1+1) a (D AAD + t W())
(3)
where A is the adjacency matrix without self-connections. In contrast, GCN (Kipf & Welling 2016) obtain node representations by H = oD + (A + I)D HH() where I is the identity matrix.
We adopt the graph convolution strategy in Eq. to get node representations for the following reasons: (1) For clean nodes, as each neighbor has the same drop ratio 3, in expectation, the node representation is unchanged because the proportion of the expected contribution of each neighbor's features to the node representation maintained. Thus, the expectation of prediction variance for clean nodes tends to be small. In contrast, if we include the attributes of the central node, the expectation of the node representation will focus more on the central node after random edge dropping, making the prediction variance unpredictable. We will analyze further in Theorem (2) For poisoned target node, as backdoor triggers are designed to attack various types of targets, once the trigger exists after random edge dropping, it will still lead to successful attack, regardless of whether the node representations are obtained only based on neighbors or also consider the node itself. However, if the trigger is dropped, the model will exhibit large prediction variance. In cases where all the neighbors of a central node are dropped, we cancel the edge drop operation for that node and retain its original neighbors. Notably, while the attributes of the central node are important for accurate classification, our focus here is on testing the prediction variance and identifying poisoned nodes. Once target nodes identified, various GNNs can be used train a classifier with our robust loss in Eq. 6
To prove that our method of randomized edge dropping can effectively distinguish poisoned target nodes from clean nodes, we make the following assumptions on graph and propose theorems.
Assumptions on Graphs. Following (Dai et al. 2022b Ma et al.) 2021a), we consider a graph G. where each node v; has features x; E R" a label yi and deg(i) denotes the number of its neighbors. We assume that: (I) The feature of node 2 is sampled from the feature distribution Fy: that depends on the label y of the node, i.e., x; Fy.. (2) Feature dimensions of x; are independent to each other; (3) The features in X are bounded by positive scalar B, i.e.. max,,j [Xii < B.
Theorem 1. Consider graph G EV.E, X) following Assumptions (1)-(3. For clean node vs E V and its neighbors (i), the expectation of the pre-activation output of a single operation defined in Eq. 3 is given by E(b.). Then the expectation of the pre-activation output of single operation defined in Eq. 3 after random edge dropping is given by E Ebh]] = E[bb.).
The proof is in Appendix D.I Theorem shows that, in expectation, the output embedding of a node remains unchanged before and after random edge dropping when applying the layer operation defined in Eq. 3 regardless of the drop ratio. However, in practice, conducting numerous experiments not feasible. Thus, analyze the distance between the observed node embeddings after random edge dropping and the expectation of node embeddings without perturbation.
Theorem 2. Consider a graph G = {V,E, X) following Assumptions (1)-(3). Let h, and hā denote the clean node embedding before and after the kitth random edge dropping, respectively, and
5

---

Published as a conference paper at ICLR 2025
deg(i)s represent the corresponding degree of node vs. The probability that the distance between the observation h and the expectation of b is larger than t is bounded by:
(||b2 B [hil11 2t) 2- M exp
de
(4)
(
where M denotes the feature dimension and p² (W) denotes the largest singular value of W.
The proof is in Appendix D.2, Theorem shows that the distance between the observed node embeddings after random edge dropping and the expectation of node embeddings without perturbation small with a high probability. Furthermore, nodes with higher degrees are more likely to exhibit less variation in their embeddings. This highlights the effectiveness of our method of random edge dropping, particularly dense graphs, compared to the method that drops each edge individually.
Based on the above analysis, we theoretically demonstrate that our method, which involves random edge dropping and obtaining node representations through graph convolution as defined in Eq. 3 results in small changes to node representations. Thus, for clean nodes, this stability ensures that the prediction output is consistent as the backdoored model does not exhibit sensitivity towards any particular clean neighbors. However, for poisoned target nodes, the scenario differs. Despite the stability in their node representations after random edge dropping, the last-layer classifier's 's sensitivity (Chen et al. 2018) to the presence or absence of the backdoor trigger Ieads to significant variance in prediction outcomes compared to clean nodes. This is verified in Sec. 3.2
Next, analyze the expected number of times the backdoor trigger 9: be removed from the neighbor of a poisoned node i; after K iterations of random edge dropping. This also indicates the expected number of times the poisoned node U, demonstrates larger prediction variance.
Theorem 3.
Without loss of generality, we consider the case where there only one edge connecting backdoor trigger to a target node. Let B denote the random edge dropping ratio, and K be the total number of iterations for random edge dropping and conducting inference on the perturbed graph. For a poisoned node d; and trigger 9r. the expected number of times the poisoned node vú demonstrates large prediction variance is given as E(gg)a = K.B.
Theorem 3 demonstrates that this expected number grows fast with a certain drop ratio. Since Theorem indicates that, in expectation, the output embedding of a clean node remains unchanged before and after perturbation, regardless of the drop ratio, can a high drop ratio, e.g. 3 = 0.5, to achieve a fast increase in the expected number of times the poisoned node U, demonstrates large prediction variance. Our experimental results in Section [5.4] show that with 8 0.5, even small value of K, e.g. K = 5, can already identify most of the poisoned target nodes from the clean ones.
To empirically verify that our method of random edge dropping can efficiently distinguish poisoned nodes from clean nodes, we adopt the attack method DPGBA and conduct experiments on Cora and OGB-arxiv to show the prediction variance of poisoned nodes and clean nodes after random edge dropping. The details of the experiment settings and the results are in Appendix E From the results, we observe that: (i) Our method consistently results in higher prediction variance for poisoned nodes, enabling the distinction between poisoned and clean nodes. (ii) Even when two edges link a backdoor trigger to poisoned node, our method maintains high prediction variance for most poisoned nodes. This showcases the superior performance of our method compared to the intuitive approach of dropping each edge individually. Furthermore, the time complexity of our method scales linearly with K, which is typically small, whereas the intuitive method scales exponentially with d', leading to significantly higher computational costs as increases. We also compare the prediction variance of low-degree nodes from both homophilic and heterophilic graphs against poisoned nodes in Appendix F)
Identify Target Nodes and Target Class. Next, we give details of how we determine the target class Ye and identify the candidate poisoned target node set V,, Given s(i) as the prediction variance for each node is Vr with label ye, we nodes by sii in descending order and form the set (1) Mo(1)), (Sa(2); Ma(2)),.... (So(n)) Jo.n))}. where a is permutation of {1, 21, .n} = D'=
such that the sorted values satisfy so (1) > s- > >... >> so (n). Then we determine the target class as the label of the node with the largest prediction variance, i.e., V/- Mr(1). Let j be the index of the first entry in D' such that yo(j) * yr and yo(++1) * ye. The threshold of prediction variance to select candidate poisoned target nodes is defined as:
= 8o()) where min {kk (o(k) # yr and Vo(k+1) # kt, = 1,,,3 ...,]. ..
(5)

---

Published as a conference paper at ICLR 2025
Then, select nodes with prediction variance larger than the threshold as candidates for poisoned target nodes, denoted as V..
4.2 BACKDOOR ROBUST GNN MODEL TRAINING
Though random edge dropping can help identify the most poisoned target nodes, there are still some concerns. First, a small amount of poisoned target nodes might exhibit prediction variances similar to those of clean nodes, inevitably remaining within the graph. Second, as discussed in Section 3.2 merely climinating backdoor triggers from the training set is insufficient to defend against backdoor triggers that mimic the neighbor distribution of nodes from the target class.
An intuitive solution is train a trigger detector capable of distinguishing clean nodes and backdoor triggers. Then, during inference on an unseen graph Gu, the trigger detector is adopted to remove potential triggers. However, when the trigger is subgraph, multiple nodes, and their interactions need to be considered simultaneously during training, complicating the process of training the trigger detector. Additionally, each time we are given unseen graph, need to the trigger generator to perform inference on the entire graph first, increasing the computational cost.
Thus, in our RIGBD, we propose directly training backdoor robust GNN node classifier f on the training dataset Vr by minimizing its prediction confidence on the target class for poisoned nodes, thereby encouraging the model counteract the impact of the backdoor triggers and be robust against backdoor attack. Specifically, given the selected poisoned target nodes V. E Vr, the objective function to train a backdoor robust GNN node classifier f is:
L = m -,,,v. log f(us).. -Enjevary C(f(u)), Us),
(6)
where f(e)).. denotes the prediction confidence of f for is on target class ys and C(f(e,), yy) is the cross entropy loss. The resulting classifier is robust against triggers as (i) We explicitly countermeasure the detected backdoors, making our model robust to backdoor. Though there might be target nodes not detected, they generally have smaller prediction variance, meaning that they have less impact on the training of f. As these triggers more or less have patterns similar to the detected ones, our training strategy implicitly mitigates their effects. (ii) For triggers that mimic the neighbor distribution of nodes from the target class, our model f is encouraged to explore the subtle differences between clean nodes from the target class and poisoned target nodes, thereby ensuring its clean accuracy. The training algorithm is in Appendix G
5 EXPERIMENTS
In this section, we conduct experiments to answer the following research questions: (Q1) How effective RIGBD in defending against graph backdoor attacks? (Q2) How the performance of RIGBD in detecting poisoned nodes? (Q3) How do different drop ratios and different numbers of iterations of random edge dropping impact the performance RIGBD?
5.1 EXPERIMENTAL SETUP
Datasets. We conduct experiments three benchmark datasets widely used for node classification.
i.e., Cora, Citeseer, Pubmed (Sen et al. 2008), Physics (Sinha et al. (015)). Flickr (Zeng et al. 2019)
and OGB-arxiv (Hu et al. 2020). More details of the datasets are summarized in Appendix H.I
Attack Methods. To demonstrate the defense ability of our RIGBD, we evaluate RIGBD on
state-of-the-art graph backdoor attack methods, i.c. GTA (Xi et al.) (022). UGBA (Dai al. 2023
and DPGBA (Zhang et al., 2024). The details of these attacks are given in Appendix H.2
Compared Methods. We implement the backdoor defense strategies Prune (Dai et al. 2023) and
OD (Zhagg et al., 2024). Additionally, three representative robust GNNs, i.e. RobustGCN (Zhu ct al. 2019). GNNGuard (Zhang & Zitnik| 2020) and randomized smoothing (RS) (Wang et al. 1 with various drop ratios are also selected. We also include ABL (Li et al.) 202 which
is a popular backdoor defense method in the image domain and aims to train clean models given backdoor-poisoned
backdoor poisoned data. More details of these defense methods are given in Appendix H.
Evaluation Protocol. Following existing representative graph backdoor attacks (Dai et al. 2023
Zhang al. 2024). we split the graph into two disjoint subgraphs, Gr and Gv. with an 80 20 ratio.
7

---

Published as a conference paper at ICLR 2025
Table 2: Results of backdoor defense.
Albacka
Delinee
ASRr/11
Com
Clicseer ASR
ASRr511
PuhMed
AC1
ASkr91
Physics
ACX
ASR/S1
Flicke
ACCINST
ASR/91
OGB AERiS
GUN
98.95
62.5%
100000)
73.20
55.03
b5.18
S9.42
19.10
28.50
41.23
60.76
GNV/GGuand
40.22
19.52
35. 15225
03.55
21.91
$1.08
44.87
17.772
01:01
00:41
0314
61.38
RobusGGCN
90.45
50.37
95.31
13.79
95.12
$1.68
95.47
94.84
55:42
42.26
70.92
56.08
GTA
OD
Pruce
17.63
0.04
53.06
K3.47
12:34
0.04
72.54
72.46
28.10
0.05
55.05
85.27
0.32
9.34
00:24
53.45
12.55
2.12
41.27
41.42
0.01
0.01
63.97
63:23
RS
53.14
73.35
$2.85
63.66
42.25
64.58
57.20
92.52
52.85
42.31
42.72
53.48
AHI
1993
61.5
13.09
73.19
16.11 18
K1.02
16.83
90.06
17.55
41 16
11.26
61.24
RIGRN
0.00
63.70
01:34
44:10
0111
$4.12
00.32
95:10
0100
44:11
0.01
66.51
GUN
98.99
63-42
100100)
14.70
56.83
$4.06
100100
94.55 546
64:11
58.83
01555
GINNGGunnn
45.17
18.15
94.55
64.76
98.97
06
87.54
56 91
41.15
6461
RobusIGCN
98.67
50.00
99.82
71.69
59.90
$2.85
99.94
94.08
32.17
41,82
90.25
56,18
UGBA
QD
Pruce
98.89
0.03
$2.06
63.65
97.65
0.06
73,50
14.35
92.87
0.01
$5.19
85.00
98.07
0.02
95.36
90.87
91. A3
1.65
43.05
43.57
93.07
0.01
63.25
62,38
RS
54.24
70.37
50.34
69.58
44.43
$4.68
47.77
94.20
20.69
42.18
40.30
59.76
ARI
15.13
K1 48
12.08
73.19
75 63
$4.17
14:87
94.99
15.33
41 AM
14:26
64.9%
RIGRR
0.01
$4.51
0.00
73.50
0.01
65:15
00.32
95:71
0100
43.66
0.01
63.21
QUN
97.73
K3.34
100.00
14.19
98.61
K5.32
100100)
90 79
64.77
95.01
65:32
GNNNGuard
85.61
78.52
46.95
00.34
44.12
50:82
38.72
83.76
95.85
43.52
94.65
62.29
RobusGUUN
96.65
$1.31
91.64
71.08
94.85
K2.56
91.25
94.87
24.00
41.09
90.09
00.38
DPGBA
QD
Pruse
91.82
94.33
65.28
$3.55
94.80
98.42
73.21
73.66
91.32
$8.64
65.12
65.13
94.27
98.72
94.73
95:48
90.42
$8.96
44.75
43.65
93.20
90.47
63.47
63.53
RS
$1.29
09.63
50.34
71.08
48.83
85.44
48.19
95.30
27.94
42.21
41.15
59.44
ARI
86.77
79.33 26
11:41
73.49
48.5
79.45
11.24
95.30
90.43
41.51
$2.86
69.58
RIGRO
0.01
83:19
0.35
73.79
0.03
84.36
0.21
95.79
0.00
43.78
0.00
63:24
The graph GT is used to train the attacker. Then, the attacker selects target nodes V/ and attaches triggers to these target nodes to form the backdoored graph Gr. The number of triggers DVgl is set as 40, 80, 160, 160, 160 and 565 for Cora, Citeseer, PubMed, Physics, Flickr, and OGB-arxiv, respectively. The trigger size is limited to three nodes in all experiments. The defender trains a model on poisoned graph Gr- Next, half of the nodes in Gu are selected as poisoned nodes and are attached with backdoor triggers test the attack success rate (ASR). The remaining nodes in Gu are kept clean and used to test the clean accuracy (ACC). We also report the Recall and Precision of our method in identifying poisoned nodes. Recall is defined as the percentage of poisoned nodes among the candidate nodes identified, relative to all poisoned nodes. Precision is defined as the percentage of poisoned nodes among the candidate nodes identified. Our RIGBD deploys a 2-layer GCN as the model architecture. Each experiment is conducted 5 times and the average results are reported.
5.2 PERFORMANCE OF DEFENSE
To answer Q1, we compare RIGBD with the baseline defense methods across three datasets. The number of iterations for random edge dropping is set to K 20, with drop ratio of 3 = 0.5. We report ASR and ACC in Table 2 From the table, we observe: (i) Across all datasets and attack methods, RIGBD consistently achieves the lowest ASR score, typically close 0%. Although defense methods such as Prune and OD perform well against GTA and UGBA attacks, they fail to defend against DPGBA, which generates in-distribution triggers. This indicates that RIGBD is highly effective in defending against various types of backdoor triggers and backdoor attacks. (ii) Our RIGBD achieves comparable or slightly better clean accuracy compared to the vanilla GCN. This indicates that our approach of random edge dropping typically leads to higher prediction variance for poisoned nodes, effectively identifying backdoor triggers. In cooperation with this precise identification of poisoned nodes, our strategy to train a backdoor robust model using Eq, 6 can significantly reduce the ASR while maintaining clean accuracy. Additional results on RS with varying drop ratios and RIGBD using different GNN architectures can be found in Appendix!] J
5.3 ABILITY TO DETECT POISONED NODES
To answer Q2, we present the recall
Table 3: Results for the ability to detect poisoned nodes.
and precision of RIGBD in identifying
Attacks
Clean ACC
ASR
ACC
Recall
Precision
poisoned nodes. Using the same setting
GTA
65.8
0.01
66.51
84.9
90.3
as in Sec. 5.2 the results on OGB-arxiv are shown in 3 We also include
UGBA
65.8
0.01
65.21
95.6
96.3
DPGBA
65.8
0.00
65.24
90.5
93.9
the corresponding ASR and ACC to illustrate the correlation between detection ability and defense performance. Clean accuracy (Clean ACC), obtained from model trained on the clean graph, is provided as a reference to evaluate the model's performance on clean nodes. From the table, we observe the following: (i) Our RIGBD demonstrates consistently high precision, always over 90%, in detecting poisoned nodes across three attack methods, with detection recall always exceeding 80%. This indicates that strategy of random edge dropping typically leads to higher prediction variance
8

---

Published as a conference paper at ICLR 2025
128
120
BICBDURE
1.44
0.56
0.53
12.4
68:0
25
67.0
100
DOGID
1.47
5.00
0.36
0.65
0.29
14
27.0
66.4
16
77.6
92.5
95
96
60.2
16
90-
0:47
C20
0.36
0.13
3
15.4
60.5
27.6
45
97.4
67.3
69
20
1.23
0.2
0.54
0.23
05.0
71.4
73.5
20.7
27.1
55.7
ACC
(a) Heatmap of ASR
(b) Heatmap of Recall
(c) Heatmap of Precision (d) Ablation study
Figure 3: Hyperparameter Sensitivity Analysis and Ablation Study.
for poisoned nodes. (ii) Although the recall for the GTA attack method is 84.9% we still achieve an ASR close to 0% while maintaining ACC. This verifies the stability of our strategy to train robust node classifier using Eq. G Even when some poisoned nodes are not identified, it still efficiently helps the model unlearn the triggers. More results on other datasets are in Appendix L
5.4 HYPERPARAMETES ANALYSIS AND ABLATION STUDY
Hyperparameter Analysis. To answer Q3, we conduct experiments to show how different drop ratios 3 and different numbers of iterations of random edge dropping K impact the performance of RIGBD. Specifically, we vary the value of K as {2, 5, 25, 50. 100), and the values of / as {0.1, 0.5, 0.7, 0.9}. The attack method used is DPGBA. The other settings are the same as the evaluation protocol in Sec. 5.1 The results on OGB-arxiv are shown in Fig. 3 From the figure, we observe: (i) Our RIGBD is stable terms of ASR and Precision. Notably, when the drop ratio still
3 = 0.1 and K = 2, the recall of poisoned node detection is around 17.4%. However, achieve robust defense performance with 1.86% ASR. This is because our framework identifies the most efficient triggers that lead to large prediction variance and focuses minimizing their impact. By doing so, the influence of less efficient triggers is inherently counteracted. In contrast, when we simply remove those 17.4% triggers from the dataset and train normal GNN on the remaining dataset, the ASR is around 80%. (ii) As K increases, the recall also increases, empirically verifying our theorems that the clean nodes will have stable node embeddings and predictions. As / increases from 0.1 to 0.7, the recall also increases without a decrease in precision. When 3 = 0.9, only about 10% of edges remain in each iteration. Although the recall decreases slightly, we still achieve consistently high precision. This further shows the robustness of RIGBD against various chosen hyperparameters. More results on the hyperparameter analysis for ACC are Appendix [M]
Ablation Study. To evaluate the effectiveness of random edge dropping, we replace it with the intuitive method of dropping edges individually, as described Section 3.2 and obtain a variant named as RIGBDIE. We then conduct experiments focusing scenarios where backdoor trigger (subgraph) is linked to a poisoned node by two edges. To demonstrate the effectiveness of our robust training strategy, implement variant of our model, named RIGBDIR, which simply removes identified candidate poisoned nodes from the dataset and trains a GNN classifier with cross- coosopy We also implement variant called RIGBDRE,, which involves individually dropping each edge and eliminating candidate poisoned nodes. The number of iterations for random edge dropping is set to
K 20, with drop ratio of 8 = 0.5. The attack method used is DPGBA. The dataset OGB-arxe arxiv. We report the ASR and ACC in Fig. 3 From the figure, we observe: (i) When two edges link a backdoor trigger
target node, the intuitive method of dropping each edge individually fails to defend against this attack. Notably, RIGBDIR achieves an ASR almost 40% lower than RIGBDARE, highlighting that our random edge dropping is more efficient than dropping edges individually in identifying poisoned nodes. (ii) In cooperation with a robust training strategy, our RIGBD further achieves an ASR close to 0%. This underscores the superiority of our method in defending against various types of backdoor attacks. Additional results on the ablation study for the case where one edge links a trigger and a target node can be found in Appendix[] N
Impact of Various Numbers of Triggers and Trigger Sizes. The performance and analysis of RIGBD against various attack budgets and trigger sizes are provided in Appendix O anddd]
6 CONCLUSION
In this paper, we first empirically show that poisoned nodes exhibit high prediction variance with edge dropping. We then propose random edge dropping, supported by theoretical analysis, to efficiently

---

Published as a conference paper at ICLR 2025
and precisely identify poisoned nodes. Additionally, introduce robust training strategy to develop a backdoor-robust GNN model. even if some poisoned nodes remain unidentified. Extensive experiments demonstrate that our method accurately detects poisoned nodes, significantly reduces the attack success rate, and maintains clean accuracy against various graph backdoor attacks.
ACKNOWLEDGMENT
This material is based upon work supported by, in part by the Army Research Office (ARO) under grant number W91 INF-21-10198, the Department of Homeland Security (DHS) under grant number 17STCIN00001-05-
and Cisco Faculty Research Award. The views and conclusions contained in this material are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the funding agencies.
REFERENCES
Derrick Blakely, Jack Lanchantin, and Yanjun Qi. Time and space complexity of graph convolutional networks, Accessed on: Dec, 31:2021, 2021.
Bryant Chen, Wilka Carvalho, Nathalie Baracaldo, Heiko Ludwig, Benjamin Edwards, Taesung Lee, Ian Molloy, and Biplav Srivastava. Detecting backdoor attacks on deep neural networks by activation clustering. arXiv preprint arXiv:/811.0372 2018.
Huili Chen, Cheng Fu, Jishen Zhao, and Farinaz Koushanfar. Proflip: Targeted trojan attack with progressive bit flips. Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 7718-7727 2021.
Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song. Targeted backdoor attacks on deep learning systems using data poisoning. arXiv preprint arXiv:1712.05526 2017.
Enyan Dai, Wei Jin, Hui Liu, and Suhang Wang. Towards robust graph neural networks for noisy graphs with sparse labels. In Proceedings of the fifteenth ACM international conference on web search and data mining, pp. 181-191, 2022a.
Enyan Dai, Shijie Zhou, Zhimeng Guo, and Suhang Wang. Label-wise graph convolutional network for heterophilic graphs. In Learning on Graphs Conference, pp. 26 PMLR, 2022b.
Enyan Dai, Minhua Lin, Xiang Zhang, and Suhang Wang. Unnoticeable backdoor attacks graph neural networks. In Proceedings of the ACM Web Conference 2023, WWW '23, ACM, April 2023. doi: 10.1145/543307.358332. URL http: doi org 111.1..1111533355 35:3392
Enyan Dai, Tianxiang Zhao, Huaisheng Zhu, Junjie Xu, Zhimeng Guo, Hui Liu, Jiliang Tang, and Suhang Wang. A comprehensive survey trustworthy graph neural networks: Privacy, robustness, fairness, and explainability. Machine Intelligence Research, 21(6); 1011-101,,,, 2024.
Khoa Doan, Yingjie Lao, and Ping Li. Backdoor attack with imperceptible input and latent modifi- cation. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 18944-18957. Curran Asso- ciates, Inc., 2021. URL http:sss//prpceeinss.eooooooooop
fi Files/papers
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The world wide web conference, pp. 417-426, 2019.
Tianyu Gu, Kang Liu, Brendan Dolan Gavitt, and Siddharth Garg. Badnets: Evaluating backdooring attacks on deep neural networks. IEEE Access, 1447230-47244 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
10

---

Published as a conference paper at ICLR 2025
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong. Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 221 18-22133. Curran Asso- ciates, Inc., 2020. htRp:httttss/prrreeeddngg neurip wttprriss.ccppppppee. wwppaper.p.p..e..ppppe fi Files/paper/ o 22200f/f...260011111127777722222
Thomas N Kipf and Max Welling. supersuuee classification with graph convolutional networks.
arXiv preprint arXiv: 02909,,0277... 2016.
Soheil Kolouri, Aniruddha Saha, Hamed Pirsiavash, and Heiko Hoffmann. Universal litmus patterns: Revealing backdoor attacks in cnns. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 301-310, 2020.
Keita Kurita, Paul Michel, and Graham Neubig. Weight poisoning attacks on pre-trained models. arXiv preprint arXiv:2004006660 2020.
Changjiang Li, Ren Pang, Zhaohan Xi, Tianyu Du, Shouling Ji, Yuan Yao, and Ting Wang. An em- barrassingly simple backdoor attack on self-supervised learning. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 4367-4378, 2023.
Yige Li, Xixiang Lyu, Nodens Koren, Lingjuan Lyu, Bo Li, and Xingjun Ma. Anti-backdoor learning: Training clean models on poisoned data. Advances in Neural Information Processing Systems, 34: 14900-1499 14912, 2021a.
Yiming Li, Yong Jiang, Zhifeng Li, and Shu-Tao Xia. Backdoor learning: survey. IEEE Transac- fions on Neural Networks and Learning Systems, 2022.
Yuezun Li, Yiming Li, Baoyuan Wu, Longkang Li, Ran He, and Siwei Lyu. Invisible backdoor attack with cample-specifte triggers. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 16463-16661 16472, 2021b.
Minhua Lin, Zhiwei Zhang, Enyan Dai, Zongyu Wu, Yilong Wang, Xiang Zhang, and Suhang Wang. Trojan prompt attacks on graph neural networks. arXiv preprint arXiv:2410. 13994 2024.
Yunfei Liu, Xingjun Ma, James Bailey, and Feng Lu. Reflection backdoor: A natural backdoor attack on deep neural networks. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part X 16, pp. 182-199. Springer, 2020.
Zhiwei Liu, liangwei Yang, Ziwei Fan, Hao Peng, and Philip S Yu. Federated social recommendation with graph neural network. ACM Transactions Intelligent Systems and Technology (TIST), 13 (4):1-24, 2022.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural networks? arXiv preprint wxXiv2206.061/ 2021a.
Yao Ma, Suhang Wang, Tyler Derr, Lingfei Wu, and Jiliang Tang. Graph adversarial attack via rewiring. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1161-1169, 2021b.
Elman Mansimov, Omar Mahmood, Seokho Kang, and Kyunghyun Cho. Molecular geometry prediction using a deep generative graph neural network. Scientific reports, 91):20381, 2019.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint 1iXi::2002.052877 2020.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Ral Rad. Collective classification in network data. A/ Magazine, 29(3):93, Sep. 2008. doi: 10. 1609/amaa. v29i3.2157. Uttp: article/view/2157
org/ http:/mmmaaaaiiii
http/aamagazinne.
Arnb Sinha. Zhihong Shen, Yang Song, Hao Ma, Darrin Eide. Bo-June Hsu, and Kuansan Wang. An overview of microsoft academic service (mas) and applications. In Proceedings of the 24th international conference world wide web, pp. 243-246, 2015.
11

---

Published as a conference paper at ICLR 2025
Hong Sun, Ziqiang Li, Pengfei Xia, Heng Li, Beihao Xia, Yi Wu, and Bin Li. Efficient backdoor attacks for deep neural networks in real-world scenarios. arXiv preprint arXi::2306.08386 2023.
Ruixiang Tang, Mengnan Du, Ninghao Liu, Fan Yang, and Xia Hu. An embarrassingly simple approach for trojan attack in deep neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 218-228, 2020.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, Yoshua Bengio, et al. Graph attention networks. stat, 1050(20): 485550 2017.
Binghui Wang. Xiaoyu Cao, Neil Zhenqiang Gong, et al. On certifying robustness against backdoor attacks via randomized smoothing. arXiv preprint arXiv:2002./1750, 2020.
Binghui Wang, Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Certified robustness of graph
neural networks against adversarial structural perturbation. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1645-1653, 2021.
Bolun Wang, Yuanshun Yao, Shawn Shan, Huiying Li, Bimal Viswanath, Haitao Zheng, and Ben Zhao. Neural cleanse: Identifying and mitigating backdoor attacks in neural networks. In 2019 IEFE Symposium on Security and Privacy (SP), pp. 707-723. IEFE, 2019.
Maurice Weber, Xiaojun Xu, Bojan Karlaš, Ce Zhang, and Bo Li. Rab: Provable robustness against backdoor attacks. In 2023 IEEE Symposium Security and Privacy (SP), pp. 1311-1328. IEEE, 2023.
Zhaohan Xi, Ren Pang, Shouling Ji, and Ting Wang. Graph backdoor. In 30th USENIX Security Symposium (USENIX Security 21), pp. 1523-1540, 2021.
Chulin Xie, Minghao Chen, Pun-Yu Chen, and Bo Li. Cril: Certifiably robust federated learning against backdoor attacks. In International Conference on Machine Learning, pp. 11372-11382. PMLR, 2021.
Xiaogang Xing, Ming Xu, Yujing Bai, and Dongdong Yang. A clean-label graph backdoor attack method in node classification task. Knowledge-Basse Systems, pp. 112433, 2024.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: arXiv:1810.00826 2018.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. arXiv preprint arXiv: (007,04990, 2019.
Xiang Zhang and Marinka Zitnik. Gunguard: Defending graph neural networks against adversarial attacks. Advances in neural information processing systems, 33:9263-92777 2020.
Zaixi Zhang, Jinyuan Jia, Binghui Wang, and Neil Zhenqiang Gong. Backdoor attacks graph neural networks. In Proceedings of the 26th ACM Symposium on Access Control Models and Technologies, pp. 15,26,22 2021.
Zhiwei Zhang, Minhua Lin, Enyan Dai, and Suhang Wang. Rethinking graph backdoor attacks: A cestributioonppeservin perspective. In 30th SIGKDD Conference Knowledge Discovery and Data Mining, 2024.
Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu. Robust graph convolutional networks against adversarial attacks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1399-1407, 2019.
12

---

Published as a conference paper at ICLR 2025
A DETAILS OF RELATED WORKS
A. 1
GRAPH BACKDOOR ATTACKS
Backdoor attacks have been extensively studied in the image domain (Li et al.
2022 Gu et al. 2019
Chen et al. 2017 Sun et al., 2023] Li et al.] [003). Initial works focused on directly poisoning
training samples (Liu et al. 20200 Chen et al. 2017 Xing et al. 2024), while others explored making
the triggers invisible (Li et al. b02 Doan et al. 2021)) Additionally, hidden backdoors can
be embedded through transfer learning (uriita et al., 2020), modifying model parameters (Chen
et al. [02II, and adding extra malicious modules Tang et al. (020). Recently. studies have begun
investigating backdoor attacks on GNNs (Dai et al., |023] Xi et al. 202T Zhang et al.] 2021 2024
Lin et al. 2024), which differ from the more common poisoning and evasion attacks (Dai et al. 2024
2022a Ma et al., (021b). Backdoor attacks involve injecting malicious triggers into the training data, causing the model make incorrect predictions when these triggers are present in test samples. This type of attack subtly manipulates the training phase, ensuring the model performs as expected under normal conditions but fails when segger-embedded inputs are present. Among pioneering efforts, SBA Zhang et al. (2021) introduced a method for injecting universal triggers into training samples using subgraph- based approach, though its attack success rate was low. GTA (Xi et al., (20TT) advanced this by developing technique for generating adaptive triggers, customizing perturbations for individual samples to enhance attack effectiveness. In UGBA (Dai et al., (023). an algorithm for selecting poisoned nodes was introduced to optimize the attack budget, along with an adaptive trigger generator to create triggers with high cosine similarity to the target node. DPGBA (Zhang et al. 2024) demonstrate that existing backdoor attack methods graphs suffer from either low attack success rate or outlier issues. To address these problems, they propose an adversarial learning strategy generate in-distribution triggers and introduce a novel loss function to enhance the attack success rate with these in-distribution triggers. In this paper, we investigate defense mechanisms against backdoor attacks that involve attaching backdoor triggers target nodes (Xi et al. 202T Dai et al.) 2023: Zhang et al. 2024). These attacks are considered a substantial threat to real-world applications of GNNs, especially in comparison to attacks involving direct manipulation of node attributes (Xing et al., 2024). In real-world contexts, such as social media networks, it is more practical for an adversary to introduce malicious nodes (e.g., fake accounts) and connect them to a target node rather than altering the target node's 's attributes. Thus, it is anticipated that this form of attack will receive increasing research attention. Given this threat, it is crucial to develop robust defense frameworks capable of mitigating these types of attacks.
A.2 GRAPH BACKDOOR DEFENSE
Backdoor defenses have been extensively investigated in the context of con-structured data. To address the threat of backdoor attacks, various defenses have been proposed, which can be broadly classified into two main categories: empirical backdoor defenses and certified backdoor defenses. Empirical backdoor defenses (Wang et al. 2019 Kolouri et al. 2020 Li et al. (2021)) are based on specific observations or understandings of existing attacks and generally perform well in practice; however, they lack theoretical guarantees and may be circumvented by adaptive attacks. On the other hand, certified backdoor defenses (Wang et al. 2020 Weber et al. 2023 Xie et al. (02T) offer theoretical guarantees of their validity under certain assumptions, but their practical performance is often weaker than empirical defenses due to the difficulty in meeting these assumptions. Improving defenses against backdoor attacks remains a significant open challenge. Limited defenses have been proposed against the graph backdoor. UGBA (Dai al. 2023) highlights that in attack methods GTA (Xi et al. (02T), the attributes of triggers differ significantly from the attached poisoned nodes, violating the homophily property typically observed in real-worke graphs. To address this, they propose a defense method called Prune. which involves removing edges that connect nodes with low cosine similarity. This approach significantly reduces ASR of previous works. DPGBA (Zhang et al., 2024) further notes that although the generated triggers in UGBA (Dai et al. (2023) may demonstrate high cosine similarity to target nodes, the triggers in both UGBA (Dai et al. 2023) and GTA (Xi et al., 2021) are still outliers. Thus, they propose a defense method called OD, which involves training a graph
and filtering out nodes with high reconstruction loss. Their empirical results show that existing backdoor attack methods graphs suffer from either a low ASR outlier issues. However, there is no existing work on defending against DPGBA, which generates in-distribution triggers.
13

---

Published as a conference paper at ICLR 2025
B ADDITIONAL EMPIRICAL RESULTS ON PREDICTION VARIANCE CAUSED BY EDGE DROPPING
In this section, show additional results prediction variance caused by dropping trigger edges and clean edges on Cora and PubMed datasets. We generate 40 triggers for Cora and 160 triggers for PubMed. The attack method used is DPGBA (Zhang al. 2024). The model architecture is 2-layer GCN (Kipf & Welling 2016). The results are shown in Fig. From the figure, is evident that dropping adversarial edge connecting backdoor trigger will typically result in much larger prediction variance than dropping clean edges.
Clean Edges
Clean Edges
Percentage (%)
80
Trigger Edges
Percentage (%)
80
Trigger Edges
60
60
40
40
20
20
0.0
0.1 0.2
0.4 0.5
0.7
0.2
0.4 0.6 0.8 1.0 1.2 1.6 Prediction Variance
Prediction Variance
(a) Cora
PubMed
Figure 4: Visualization of prediction variance caused by dropping trigger edges and clean edges,
C TIME COMPLEXITY ANALYSIS
Following (llakely et al. 2021), to show the computation of GCN, first define Á = A +I the adjacency matrix with self-loops. D is the diagonal degree matrix of Å. A' is the normalized adjacency matrix given as:
A D AD
The computation of the I-th layer of GCN network is:
(1+1) = (w)
where (.) is a non-linear activation function (typically ReLU) and ((() is feature transformation matrix I2 M
Thus, we analyze the complexity of the forward step by decomposing Equation 8 into three high-level operations:
1. ( X ()); feature transformation
2. (1+1) = A' neighhorhood aggregation
3. a.): activation
Part 1 a dense matrix multiplication between matrices of size N M2 and Mj x M1+1. We assume for all 1, Mr 1 M. Therefore, this is ONN
Naively, part involves multiplying matrices of sizes N x and x M, resulting a time complexity of D(N2M). However, in practice,
sparse operator like PyTorch's scatter
function to compute this. For each row (i,j) of the edge matrix E, we compute x; (i+1) + 2j where
(1+1) and (!) are M-dimensional vectors. This results in a total cost of OEE) where |E| is the total number of edges. Alternatively. considering each node has neighbors on average, neighborhood
aggregation for each node requires ((dM), leading total cost of O(NdM) = M).
Part 3 is simply an element-wist wise function, so its cost is O(N).
Over L layers, this results in time complexity OLL(NM² + (E())). Next, we ignore the time complexity of activation for simplicity our analysis.
N +N) O(L(NM++
14

---

Published as a conference paper at ICLR 2025
Random edge dropping: For random edge dropping and conduct inference the whole graph for K times. The overall time complexity over L layers is O(LK + |E]M))
Dropping each edge individually: For each node, drop one of its neighbors and conduct inference on its L-hop subgraph centered at the node using an L-layer GNN, we repeat this process for d times. For simplicity, we assume each node has d-neighbors. Thus, an L-hop subgraph has in total (ddh) nodes. The time complexity analysis for each node is as follows. We use the L-hop subgraph as input to the L-layer GNN. In each GNN layer: (1) For feature transformation, the time complexity is (a M²). (2) For each neighbor aggregation, the time complexity is Odd M). As we conduct times aggregation, the time complexity is O(d MM). Thus, over N nodes and L-layer, the time complexity is O M ((d + M)).
As dL is usually much larger than K practice, the intuitive method is inefficient due the high computational cost. We conduct empirical experiments to compare the running time on the OGB-arxiv dataset. We use the same experimental setup as described in Section [5.2] The results are shown in Tab. 4 We set K 10 for RIGBD. From the table, we observe that RIGBD is significantly more efficient compared the intuitive method empirical experiments.
Table 4: Running Time Comparison
Intuitive RIGBD (K = 10)
42.56s
0.09s
D DETAILED PROOFS
Assumptions on Graphs. Following (Dai et al. 2022b Ma et al. 2021a), we consider a graph G. where each node U; has features E R" a label and deg() (i) denotes the number of its neighbors. We assume that: (1) The feature node vy is sampled from the feature distribution Fy, that depends on the label yı of the node, i.e., X; ~ F y:. This means that the feature of the node is influenced by its label, with pFFr ys denoting the mean of the distribution.
(2) Feature dimensions of x; are independent to each other; (3) The features in X are bounded by positive scalar B, i.c.. max,,j [ S B;
These assumptions are reasonable in the context of graph machine learning for several reasons: Feature Distribution Based on Labels (Assumption 1): In many real-world scenarios, the features of a node are influenced by its label. For example, in a social network, the attributes of a user (like interests activities) are often correlated with their group community (label). Independence of Feature Dimensions (Assumption 2): In many datasets, especially high-dimensional ones, the correlations between features may be weak or negligible. Bounded Features (Assumption 3): In real-world datasets, fcature values are often bounded due to physical, biological, or other prac- tical constraints. Furthermore, in practice, features are often normalized or standardized during preprocessing, effectively bounding them within a certain range.
D.1 PROOF OF THROREM 1
Theorem 1. Consider graph - following Assumptions (1)-(3). For clean node v; E V and its neighbors (i), the expectation of the pre-activation output of a single operation defined in Eq. 3 is given by B(h.). Then the expectation of the pre-uctivation oulput of single operation defined in Eq. Jafer random edge dropping is given by E B[hb]] = [....).
Proof. Given the graph convolution operation defined in Eq.
B we obtain node representation
Ehh E
Σ EjEN()) Vdegtü S /eg(() Wx, For any node v, and its neighbors (i),, after
random edge dropping with drop ratio B, in expectation, each neighbor in (i) contributes with weight of (1 3). and the expected deg(i) is also scaled by (1-3) B). Therefore, the expectation of the pre-activation output of a single operation defined in Eq. Jaftrr random edge dropping is given
15

---

Published as a conference paper at ICLR 2025
by
[ =E
Σ (iE((()
W(1 - 8)x,
v(1 3)deg(i) (1 B)deg(i)
W(1 - 8)x,
-[h,]
(EN(()) (1 (d((ge(()) /egl(i
which completes the proof.
D.2 PROOF OF THEOREM 2
To prove Theorem
first introduce the celebrated Hoeffding inequality. .,, Zn be independent bounded random variables with Zi E [a, for all i, where 00 < a S b < cc. Then
Lemma 1. (Hoeffding's Inequality). Let Zi....,
I sexp (- 2nt²
P
(Z
E 2t)
(-(6-- a)2
1=1
and
2nt²
P
[Z, - E(z,) Σ 1=1
1 5-t S cxp
n
(b - a)²
for all t 2 O.
Theorem 2 Consider a graph 9= (V, X} following Assumptions (1)-(3). Let h, and hy denote the clean node embedding before and after the k-th random edge dropping, respectively, and deg(i)x represent the corresponding number of remaining neighbors. The probability that the distance between the observation H and the expectation of h; is larger than t is bounded by:
P [ 2t) 2- exxxp 22p BP
deg(t))tt
(10)
where M denotes the feature dimensionality and p² (W) denotes the largest singular value of W.
Proof. Following (Dai et al. 2022b Ma et al. 2021a), we consider d-regular graph G, i.c. each node has d neighbors, then the expectation of h, can be derived as E [h,] ΣjEN() deg(i) Wx;
Let x [m], n = I,.... . denote the m-th element of x Then, for any dimension m, {xft [m]..] N(1)) is a set of independent random variables bounded by [-B, BJ. Hence, directly applying Hoeffding's inequality, for any t O, we have the following bound:
.......M
Σ SEATES)
(xt(m) - [xf[mi) 24 4
s 2eepp
(deg()))
(11)
N(TJK
2
if NaJj Ejercoje (xt - E [x)] ||2 2 VMt1, then at least for {1, M), the inequality
w(y= EyencH (x+(m)] E (m)] 2 holds. Hence, we have
P (1 N(i)= Σ (x, -B(x])
M
<P
Σ
(x)(m)) E
xx [m]]
2
N(iJ
m-1
JEN(C)
M
Σ P m=1
Σ
(x5(m) E [m
2
JEN(G)A
(deg(t))))t
2 1- exp
2B2
(12)
16

---

Published as a conference paper at ICLR 2025
Let t1
then we have
VM
(deg(()))
MOJ Σ
(x E (x,1)
2/2
2 M exp
(13)
2B2M
JEM(OO)
Furthermore, we have
|b - [bt]ll2
W
1
Σ
(x) - E (x51)
N(ji
JEN((E)
S [
Σ
(x) - E [x1]]
(14)
N(i
JEV(1)
((W)
Σ JEN(())
(x) - - [xx3))
N(1
where
W1l is the matrix 2-norm of W. We denote p W) | Given E [h:]
B [h+].
have IP (|
E [hill22
2 = - [
2t)
S P
p(W)
Σ
(x) - [x
2
Wii
JEN(1)*
(15)
Σ
(x) -E [x+1)
t
N(TTE
pl ((W)
JEN(E)*
(- (W) BWW)BMM
$ 2. M exp
which completes the proof.
D.3 PROOF OF THEOREM 3
Theorem 3,
Without loss of generality, consider the case where there is only one edge connecting a backdoor trigger to a target node. Let B3 denote the random edge dropping ratio, and K be the total number of iterations for random edge dropping and conducting inference the perturbed graph. For a poisoned node v; and trigger Gi, the expected number of times the poisoned node demonstrates large prediction variance is given as BB(g:) K
Proof. We model the random edge-dropping process as a series independent Bernoulli trials. Each trial represents single iteration of edge-dropping, with success probability 8, which is the probability that the edge connecting v; and gi is dropped in that iteration.
Let X₁ be an indicator random variable for the k-th iteration, where X₁ if the edge dropped, and X₁ = 0 otherwise. The total number of times the edge is dropped over K iterations is then the sum of these indicator variables:
X
(16)
Since each X₂ follows a Bernoulli distribution with parameter 3, the sum X follows Binomial distribution with parameters K and 3:
X Binomial (K,
(17)
The expected value of Binomial distribution is given by the product the number of trials and the success probability. Therefore, the expected number of times the poisoned node e; shows large prediction variance is:
E(g.)a K
(18)
which completes the proof.
0
17

---

Published as a conference paper at ICLR 2025
E EMPIRICAL RESULTS OF PREDICTION VARIANCE FOR DIFFERENT ATTACKS
AND DATASETS USING RANDOM EDGE DROPPING
70
Clean Nodes
80
Clean Nodes
80
Clean Nodes
Percentage (%)
Poisoned Nodes
Percentage (%)
70
Poisoned Nodes
Percentage (%)
Poisoned Nodes
60
60
40
30
40
40
20
10
10
2.0 Prediction Varlance
Prediction Varlance
Prediction Variance
(a) Cora
(b) OGB-arxiv
(c) OGB-arxiv (Two Edges)
Figure 5: Visualization of prediction variance caused by random edge dropping.
To empirically verify that our method of random edge dropping can efficiently distinguish poisoned nodes from clean nodes, conduct experiments the Cora (Sen et al. 2008), PubMed, and OGB-arxiv (Hu et al. 2020) datasets, using 40 triggers for Cora, 160 triggers for PubMed and 565 triggers for
respectively. The attack method used is DPGBA (Zhang et al. 2024). The model architecture is a 2-layer GCN (Kipf & Welling 2016). We set the drop ratio /
0.5 and
performed K 10 iterations of random edge dropping. The results shown in Fig. 5 In Figs.
S(a) and (b), we show the results for Cora and OGB-arxiv, respectively. In Fig. c). we show the result for OGB-arxiv with two edges linking a backdoor trigger and target node. Our observations
are as follows: (i) Our method consistently results in higher prediction variance for poisoned nodes, thus enabling the distinction between poisoned nodes and clean nodes. (ii) Even when two edges link a backdoor trigger to poisoned node, our method still results in high prediction variance for most of the poisoned nodes. This demonstrates the superior performance of our method compared to the intuitive approach of dropping each edge individually. Additional visualizations of prediction variance under different attacks on various datasets are in Fig.
Fig. and Fig 8
80
70
Clean Nodes
Clean Nodes
60
Clean Nodes
jercentage 1%)
60
Poisoned Nodes
Poisoned Nodes
Percentage (%))
50
Poisoned Nodes
50
Percentage
40
40
40
30
30
30
20
10
0
4
6
10
12
14
0
5
10
15
20
25
30
1
2
3
5
6
7
Prediction Varlance
Prediction Varlance
Prediction Varlance
(a) GTA
(b) UGBA
(c) DPGBA
Figure Visualization of prediction variance caused by random edge dropping on Cora dataset, drop ratio 3 0.5, drop iterations K 20 and the number of triggers is 40.
80
Clean Nodes
Clean Nodes
70-
Clean Nodes
Percentage (%6)
Poisoned Nodes
Percentage (%)
80
Poisoned Nodes
Poisoned Nodes
60
Percentage
40
40
20
20
10
0.0
40
0.0
10.012.515.017.
Prediction Varlance
Prediction Varlance
Prediction Variance
(a) GTA
(b) UGBA
(c) DPGBA
Figure 7: Visualization of prediction variance caused by random edge dropping on PubMed dataset, drop ratio B = 0.5, drop iterations K 20 and the number of triggers is 160.
18

---

Published as a conference paper at ICLR 2025
80
Clean Nodes
70
Clean Nodes
Clean Nodes
Percentage (%0
50
Poisoned Nodes
60
Poisoned Nodes
Percentage (96
Poisoned Nodes
Percentage
50
40
30-
30
30
20
20
10
10
10
0
2
7
8
4
6
5 Prediction Variance
Prediction Variance
Prediction Variance
(a) GTA
(b) UGBA
(c) DPGBA
Figure 8: Visualization of prediction variance caused by random edge dropping OGB-an OGB-arxiv dataset, drop ratio 3 = 0.5, drop iterations K 20 and the number of triggers is 565.
F EMPIRICAL RESULTS OF PREDICTION VARIANCE FOR NODES WITH Low DEGREES AND POISONED NODES
In this section, to address concerns about high prediction variance in low-degree or heterophily nodes after random edge dropping, we compare the prediction variance of nodes from both homophily and heterophily graphs against poisoned nodes. We utilize the UGBA attack method to generate backdoor triggers for each dataset, setting to 10 and the drop ratio to 0.5. For each dataset, we select nodes with degrees 2, and 3. Our experiments Pubmed, Physics, OGB-an (GB-arxiv) and heterophily graphs (Wisconsin, Cornell, Texas (Pei et al. 2020), Flickr). The results, shown in Table reveal that for heterophily graphs such Wisconsin, Comell, and Texas, the prediction variance gap between low-degree and poisoned nodes is smaller compared homophily graphs. However, the prediction variance of poisoned nodes remains significantly higher than that of clean nodes, even for those with low degrees. This suggests that backdoored GNN model shows high confidence in the target class when a node is linked to backdoor trigger, but when the trigger is removed, shifts to high confidence in another class. In contrast, for clean nodes, edge dropping typically does not cause significant shift in prediction confidence.
conducted on homophily graphs (Cora, Citeseer,
Table 5: Comparison of prediction variance between clean nodes with low degrees and poisoned nodes.
Dataset
Degree-1
Degree-2
Degree-3
Target Nodes
Wisconsin
0.64
1.94
1.48
6.08
Cornell
0.79
1.33
1.27
5.16
Texas
0.65
1.48
1.28
4.10
Cora
0.51
0.66
0.56
12.70
Citeseer
0.36
0.70
0.69
5.41
Pubmed
0.67
0.80
0.57
10.67
Physics
0.44
0.52
0.36
18.80
Flickr
0.01
0.02
0.01
2.56
OGB-arxiv
0.57
0.79
0.67
10.67
G TRAINING ALGORITHM
We summarize the training method of RIGBD for training a backdoor robust GNN node classifier in Algorithm 1. Specifically, we start by randomly initializing the parameters 0, for an L-layer GNN node classifier fs, which uses the graph convolution operation defined in Eq. 3 (line 1). In each iteration of the training loop (lines 2-4), we update O by training fo the backdoored graph Gr using supervised learning until the model converges. After convergence, we enter a second loop (lines 5-8) where we conduct random edge dropping on GT and perform inference with the backdoor model fu (line 6). For each node, we calculate the prediction variance s(i) using Eq. 2 (line 7). Nodes with prediction variance s(i)
selected candidate poisoned nodes V.. where is calculated by Eq. [5] Next, we randomly initialize for another L-layer GNN node classifier (line 10). In the final training loop (lines 11-13), update 0 by training f using the robust training strategy defined in Eq.
19

---

Published as a conference paper at ICLR 2025
6 until convergence. The algorithm concludes by returning the backdoor robust GNN node classifier f (line 14).
Algorithm Algorithm RIGBD
Require: Backdoored graph Gr = Vrr,Tr, XT))) drop ratio 3 and number of drop iterations K
Ensure: Backdoor robust node classifier
1: Randomly initialize 0g for L-layer GNN node classifier fo with graph convolution operation
defined in Eq. 3]
2: while not converged yet do
3: Update O, by training fo on the backdoored graph GT using supervised learning;
4: end while
5: for k 2.2..... K do
6: Conduct random edge dropping on the graph Gr and perform inference with the backdoor
model fo:
7: Calculate the prediction variance sii) for each node by Eq. 2
8: end for
9: Select candidate poisoned nodes V. for nodes with prediction variance s(i) > T, where is calculated by Eq.
10: Randomly initialize 9 for any L-layer GNN node classifier
11: while not converged yet do
12: Update 0 by training using the robust training strategy defined in Eq. 6
13: end while
return Backdoor robust GNN node classifier f;
H ADDITIONAL DETAILS OF EXPERIMENT SETTINGS
H.1 DATASET STATISTICS
Cora, Citeseer and PubMed citation networks where nodes denote papers, and edges depict citation relationships. In Cora and Citeseer, each node is described using a binary word vector, indicating the presence or absence of corresponding word from predefined dictionary. In contrast, PubMed employs a TF/IDF weighted word vector for each node. For both datasets, nodes are categorized based their respective research areas.
Coauther Physics is co-authorship graph based on the Microsoft Academic Graph from the KDD Cup 2016 challenge (Sinha 2015). Nodes are authors, that are connected by edge if they co-authored a paper; node features represent paper keywords for each author's 's papers, and class labels indicate most active fields of study for each author.
Flicker (Zeng et al. 2019): In this graph, each node symbolizes an individual image uploaded to Flickr. An edge established between the nodes of two images if they share certain attributes. such as geographic location, gallery, user comments. The node features are represented by 500-dimensional bag-of-word model provided by NUS-wide. Regarding labels, we examined the 81 tags assigned to each image and manually consolidated them into 7 distinct classes, with each image falling into one of these categories.
OGB-arxi is citation network encompassing all Computer Science arXiv papers cataloged in the Microsoft Academic Graph. Each node is characterized by 28-dimensioonl feature vector, which derived by averaging the skip-gran word embeddings present in its title and abstract. Additionally, the nodes are categorized based on their respective research areas. The statistics details these datasets summarized in Table
20

---

Published as a conference paper at ICLR 2025
Table 6: Dataset Statistics
Datasets
#Nodes
#Edges
#Features
#C #Classes
Cora
2,708
5,429
1,443
7
Citeseer
3,327
4,552
3,703
Pubmed
19,717
44,338
500
3
Physics
34,493
495,924
8,415
Flickr 89,250
899,756
500
7
OGB-arxiv
169,343
1,166,243
128
H.2 ATTACK METHODS
The details of attack methods are described following:
1. GTA (Xi et al. 2021): GTA utilizes a trigger generator that crafts subgraphs as triggers tailored to individual samples. The optimization of the trigger generator focuses exclusively on the backdoor attack loss, disregarding any constraints related to trigger detectability.
2. UGBA (Dai et al., 2023): UGBA selects representative and diverse nodes as poisoned nodes to fully utilize the attack budget. An adaptive trigger generator is optimized with constraint loss so that the generated triggers are ensured to be similar to the target nodes.
DPGBA (Dai et al. 2023): DPGBA introduce adversarial learning strategy to generate in- distribution triggers. A novel loss is proposed to help adaptive trigger generator generate efficient in-distribution triggers.
H.3 COMPARED METHODS
We select two defense methods that aim to defend against specific backdoor attack methods:
1. Prune (Dai al. 2023 Prune is designed prune edges that linking nodes with low similarity to remove those triggers that are totally different from clean nodes.
2. OD (Zhang et al., 2024): OD introduces graph auto-encoder and filter out nodes with high reconstruction loss remove those triggers that outliers compared clean ones.
We include strong baseline that also aims to learn a clean model from the poisoned data:
1. ABL Li et al. a ABL exploits two key weaknesses of backdoor attacks: 1) models learn backdoored data much faster than clean data, with stronger attacks causing faster convergence; 2) the backdoor task is tied to a specific class. Thus, they propose a local gradient ascent (LGA) technique trap the loss value of each example around a certain threshold. They also propose global gradient ascent (GGA) loss function to unlearn the backdoor with a small subset backdoor examples while continuing to learn from remaining clean examples.
As backdoor attack is a subset of poisoning attack, we also include three representative robust GNNs:
1. RS (Wang et al. 2021): Randomized smoothing graphs was first proposed to counter adversarial structural perturbations. We adopt this method and set the drop ratio 3 > 0.5 to balance the defense performance and clean accuracy. To further ensure clean accuracy, introduce an advensarial training strategy during the training phase.
2. GNNGuard Zhang & Zitnik 2020): GNNGuard is robust defense method for GNNs that protects against adversarial attacks by leveraging node similarity filter out adversarial edges. It employs a multi-stages defense strategy that dynamically adjusts edge weights during training, enhancing the model's 's resilience to structural perturbations.
3. RobustGCN (Zhu et al. 2019): RobustGCN enhances the robustness of GCN against adversarial attacks by using Gaussian distributions as node representations, which absorb the effects of adversarial changes. It also introduces variance-based attention mechanism
21

---

Published as a conference paper at ICLR 2025
that assigns different weights to node neighborhoods based on their variances, reducing the propagation of adversarial effects through the graph.
H.4 DETAILED COMPARISON OF RIGBD TO BASELINE DEFENSE METHODS
Aside from the defense methods we mentioned, such as Prune and OD, which aim to defend against attack methods by exploiting the characteristics of generated triggers, to the best of our knowledge, our RIGBD is the first work that specifically aims to defend against dirty-label node-level graph backdoor attacks that involve generating backdoor trigger and linking it to the target node from the perspective of training a backdoor-robust model.
Since such backdoor attack methods inherently belong to the category of poisoning attacks, include GNNGuard and RobustGCN as baselines because they both have the ability to mitigate the influence of malicious neighbors, which 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 the target nodes.
We also include randomized smoothing because if we can randomly drop edges with a high drop ratio during multiple inferences, we could obtain the final prediction the backdoor trigger were dropped. However, the clean accuracy of this method cannot be guaranteed, as too many edges are dropped during the classification task.
The core idea of ABL is that the model quickly learns backdoored data, after which local gradient ascent technique is used to trap the loss value of each example. However, their framework requires manual tuning of the isolation ratio, and a high isolation ratio inevitably leads to performance drop on clean data when their losses are trapped. This significantly reduces the method's utility in real-world applications, defenders typically do not know the number of poisoned target nodes.
In contrast, (i)
Our method is theoretically guaranteed and capable of identifying those poisoned target nodes with high precision without knowledge of the number of poisoned target nodes. (ii) With high precision in detecting poisoned nodes, our framework makes only minimal changes to the graph structure of clean nodes, ensuring that the clean accuracy remains comparable that of model trained on a clean graph. (iii) With the proposed robust training strategy, our framework is robust different hyperparameter selections, making it easy implement and enhancing its utility in real-world applications.
H.5 IMPLEMENTATION DETAILS
We test our RIGBD using different graph neural network backbones, i.c. GCN, GAT, and GraphSage. All hyperparameters of all methods are tuned based on the validation set for fair comparison. All models are trained on an A6000 GPU with 48G memory.
I RESULTS ON CLEAN GRAPH
Table Comparison of Clean Accuracy between GCN and RIGBD trained on clean graph.
Dataset
RIGBD GCN
Cora
84.44
84.07
Citeseer
73.83
73.44
PubMed
85.13
85.05
Physics
95.78
95,40
Flickr
44.42
44.03
66.13
65.53
In this section, we conduct experiments to show the clean accuracy of our RIGBD when trained on a clean graph. Specifically, follow the experimental setup described in Sec. 5.2 and remove the backdoor triggers from the poisoned graph. Then, we train a GCN and RIGBD on this clean graph. The results shown in Tab. 7 From the table, observe that our RIGBD achieves comparable
22

---

Published as a conference paper at ICLR 2025
Table Additional results of backdoor defense.
Cura
PubMed
OGB arxiv
Attacks
Defense
A
ACC[S))
ASR(S)
ACC(S:)
ACC(S))
GAT
76.97
84.44
89.77
82.60
OOM
OOM
GruphSage
100.00
99.94
RS-0.7
45.02
66.67
33.20
85.24
33.12
36.93
GTA
34.32
24.65
RIGAD-GAT
0.02
85.19
0.08
83.66
OOM
OOM
RIGBD-GrphSage
0.18
81.52
0.00
67.18
GAT
100
85,19
100.00
83.05
OOM
OOM
GraphSage
97.33
84.07
99.08
85.24
94.69
68.25
RS-0.7
46.86
37.74
RS-0.8
37.64
65.19
28.20
86.35
23,14
34.77
UGBA
RIGHD-GAT
82.14
OOM
RIGED GraphSage
0.44
84,07
0.02
85.74
0.06
67.75
GAT
91.14
83.33
93.8
83.56
OOM
OOM
GraphSage
93.48
83.33
91.8
85.79
99.53
67.76
RS-0.7
40.96
68.52
36.31
84,90
32.81
56.66
RS-0.8
35.79
66.30
27.13
85.74
23.41
54.45
RIGBD-GAT
0.04
84.44
0.01
83.31
OOM
OOM
RIGBD-GraphSege
0.26
0.06
86.35
0.03
66.61
clean accuracy to GCN. This is because our poisoned node selection strategy, defined in Eq. stops when nodes continuously show different labels compared the node with the highest prediction variance. Since nodes with high confidence are not always from the same class in a clean graph, we rarely select nodes poisoned nodes. This highlights the adaptability of our RIGBD, even when do not know whether the graph is clean or poisoned.
ADDITIONAL RESULTS OF DEFENSE PERFORMANCE
In this section, we provide additional results on defense performance. Specifically, we implement RIGBD with GAT and GraphSage backbones. We also include randomized smoothing (RS) with drop ratios 3 0.7 and / = 0.8. All other settings are the same as Sec. 3.2 The results are shown in Table From the table, randomized smoothing can degrade the ASR. However, the clean accuracy not guaranteed. This demonstrates the superiority of framework in degrading ASR while maintaining clean accuracy. (ii) Our RIGBD consistently achieves low ASR while maintaining comparable or slightly better clean accuracy compared vanilla GNNs on all datasets. This demonstrates the flexibility and effectiveness of our framework with different backbones.
observe the following: (i) With the increase in drop ratio,
K ADDITIONAL RESULTS OF DEFENSE PERFORMANCE ON HETEROPHILIC GRAPHS
Dataset
Methods
Clean ACC
ASR
Recall
Precision
Wisconsin
GCN
48
100
RIGBD
48
0
90
95
Cornell
GCN
50.0
93.3
RIGBD
53.5
3.3
70
100
Texas
GCN
44.4
92.9
RIGBD
42.9
3.7
80
70
Table 9: Performance comparison GCN and RIGBD across different datasets.
In this section, we conduct additional experiments to evaluate the performance of RIGBD on heterophilic graphs. The attack method used is DPGBA al. (2024). with 20 poisoned nodes during training, and other settings follow those described in Section 5.1 The results are presented in Table 9 It is evident that RIGBD achieves consistently strong performance in defending against.
23

---

Published as a conference paper at ICLR 2025
Table 10: Results for the ability to detect poisoned nodes.
Datascts
Attacks
Clean ACC
ASR
ACC
Recall
Precision
GTA
83.5
0.00
83,70
91.2
94.0
Cora
UGBA
83.5
0.01
84.81
96.8
100.0
DPGBA
83,5
0.01
85.19
100.0
100.0
GTA
73.8
0.34
74.10
94.7
100.0
Citeseer
UGBA
73.8
0.00
73.80
93.4
98.6
DPGBA
73.8
0.33
73.79
97.4
100.0
GTA
84.9
0.01
84.32
82.0
90.5
PubMed
UGBA
84.9
0.01
85.13
88.7
96.6
DPGBA
84.9
0.01
84.32
85.0
91.0
GTA
95.8
0.32
95.10
86.2
91.8
Physics
UGBA
95.8
0.12
95.71
96.0
98.4
DPGBA
95.8
0.21
95.97
96.8
99.2
GTA
44.4
0.00
44.21
69.5
98.1
Flickr
UGBA
44.4
0.00
42.74
98.6
97.2
DPGBA
44.4
0.00
43.80
97.9
100.0
GTA
65.8
84.9
OGB-arxiv
UGBA
65.8
0.01
65.21
95.6
96.3
DPGBA
65.8
0.00
65.24
90.5
93.9
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.
L ADDITIONAL RESULTS OF THE ABILITY TO DETECT POISONED NODES
In this section, we provide additional results of the ability to detect poisoned nodes on Cora and PubMed dataset. We present the recall and precision of RIGBD in identifying poisoned nodes. We use the same setting as in Sec. 5.2 The results are shown in Table IO We also present the corresponding ASR and ACC to illustrate the correlation between detection ability and defense performance. Clean accuracy (Clean ACC), obtained from a model trained on the clean graph, is provided as a reference to evaluate the model's performance
clean nodes. From the table, we observe the following: (i) Our RIGBD demonstrates consistently high precision, always over 90%, in detecting poisoned nodes across three attack methods in all datasets, with detection recall always exceeding 80%. This indicates that our strategy of random edge dropping with graph convolution operation defined in Eq. 3 Stypically leads higher prediction variance for poisoned nodes. (ii) Although the recall for some attack methods and datasets is less than 90%, we still achieve an ASR close to 0% while maintaining ACC. This demonstrates the stability of our strategy to train a robust node classifier using Eq. Even when some of the poisoned nodes are not identified, it still efficiently helps the model unlearn the triggers.
M ADDITIONAL RESULTS OF HYPERPARAMETER ANALYSIS
55
100
160
9
593
3.50
0.52
3.47
0.53
17.4
48.0
76.2
06.3
01.5
3.41
06.55
$5.02
8:67
0.0
0.36
3.7
0.70
12
46.
53.1
15.4
23.5
16.7
47.6
85.4
47.4
67.3
94.3
10
15 0
10
19-00
10
1:00
0.52
3.60
0.92
00.0..1
25.27
06.07
25.75
03.50
25.3
00.0
17.9
927
95.7
(a) Heatmap of ASR
(b) Heatmap of ACC
(c) Healmap of Recull
(d) Healmap of Precision
Figure 9: Hyperparameter Sensitivity Analysis
In this section, we provide additional results on how different drop ratios (B) and different numbers of iterations of random edge dropping (K) impact the ACC of RIGBD. ASR, Recall, and Precision are also provided as references. Specifically, we vary the values of K as {2, 2,2,, 50, 100), and the values 8 as {0.1, 0.3, 0.5, 0.7, 0.9). The attack method used is DPGBA A. The other settings are the same as the evaluation protocol in Sec. 5.1 The results are shown in Fig. From the figure, we make
the following observations: (i) Our RIGED is stable in terms of ASR, ACC, and Precision. Notably, when the drop ratio B = 0.1 and only conduct two iterations of random edge dropping, the recall
24

---

Published as a conference paper at ICLR 2025
of our poison node detection is around 17.4%. However, still achieve robust defense performance with ASR close to 0%. This demonstrates that our robust training strategy is effective even with lower recall. As our framework identifies the most efficient triggers that lead to large prediction variance and focuses on minimizing their impact. By doing so, the influence of less efficient triggers inherently counteracted. In contrast, when simply remove those 17.4% triggers from the dataset and train model on the remaining dataset, the ASR is around 80%. (ii) As K increases, the recall also increases, empirically verifying our Theorem that in expectation, the clean nodes will have stable node representations and thus stable predictions when using the graph convolution operation designed in Eq. 3 As increases from 0.1 to 0.7, the recall also increases without a decrease in precision, demonstrating the stability of our method. When 3 = 0.9, only about 10% of edges remain each iteration. Though the recall decreases slightly, we still achieve consistently high precision. This further indicates the robustness of our model against various chosen hyperparameters.
N ADDITIONAL RESULTS OF ABLATION STUDIES
In this section, we provide additional results on ablation studies on OGB-arxiv dataset to investigate the impact of random edge dropping on poison node detection and evaluate the efficacy of our robust training strategy as described in Eq. 6 Following Sec. 5.4. to evaluate the effectiveness of random edge dropping, we replace it with an intuitive method dropping edges individually, as described in Section and obtain variant named as RIGBDIE. To demonstrate the effectiveness of our robust training strategy, we implement a variant of our model, named RIGBDIR, which simply removes identified candidate poisoned nodes from the dataset. The attack method used is DPGBA. We also implement a variant called RIGBDRRE, which involves individually dropping each edge and eliminate candidate poisoned nodes. The number of iterations for random edge dropping is set to K 20, with a drop ratio of B = 0.5. We report the ASR and ACC in Fig. [0 The results on on scenarios where a backdoor trigger (subgraph) linked to a poisoned node by two edges are also provided as a reference. From the figure, we observe: (i) In Fig. I0 (a), RIGBDIE and RIGBDARE achieve comparable and slightly better defense performance than RIGBDland RIGBDIR. However, in Fig. T0 (b), RIGBDIE and RIGBDARE fail to degrade the ASR. This demonstrate that although drop edge individually may demonstrate comparable performance in detecting poison nodes when there is only one edge linking trigger to a target node, it fails to defend effectively against attacks involving two edges linking a backdoor trigger to a target node. In such cases, the intuitive method of dropping each edge individually proves inadequate. (ii) In both settings, ZIGBDlachiev better defense performance than RIGBDIR, This demonstrates the effectiveness of our robust training strategy in handling cases where some poisoned nodes not identified.
RIGBDIR
RIGHDDRR RIGBD
RIGHDIR
RICBIDIRE
RIGBALE
100
RIGBALE
RIGED
60-
20
ASR
ACC
ASR
ACC
(a) Single edge
(b) Two edges
Figure 10: Ablation study on OGB-arxiv
O ADDITIONAL RESULTS OF DEFENSE PERFORMANCE AND ABILITY TO DETECT POISON NODES WITH DIFFERENT NUMBERS OF TRIGGERS
In this section, we conduct experiments to demonstrate how varying numbers of backdoor triggers impact the performance of RIGBD in terms of backdoor defense and poisoned node detection. Specif- ically, set the number of triggers to {10, 20, 40, 80, 160} for Cora and {20, 80, 160, 240, 320} for PubMed. The attack method used is DPGBA. The drop ratio 3 = 0.5, and the number of iterations for random edge dropping are set as K 10 for Cora and K 20 for PubMed. The results
25

---

Published as a conference paper at ICLR 2025
Table 11: Results for defense and poisoned node detection with different numbers of triggers.
Datasets
Triggers
ASR
Clean ACC
ASR
ACC
Recall
Precision
87.82
84.81
0.05
85.56
90.0
90.0
20
92.62
84.44
0.00
85.19
95.0
100.0
Cora
40
93.48
83.70
0.02
85,93
97.0
97.0
80
96.52
82.22
0.10
84.81
94.0
98.4
160
99.13
80.00
0.10
84.07
97.1
95.8
20
90.73
84.88
0.01
85.21
85.0
85.0
94.32
84.68
0.01
84.56
75.5
90.2
PubMed
160
96.10
84.17
0.02
84.47
82.0
90.5
240
97.46
84.14
0.01
84.16
66.2
95.8
320
98.07
83.77
0.02
84.04
83.0
88.2
shown in Table 11 From the table, we observe: (i) Though there are fluctuations the recall and precision in detecting poisoned nodes, the precision always exceeds 85%. This indicates that our method of random edge dropping consistently leads higher prediction variance, helping us precisely identify poisoned nodes regardless of the number of triggers. (ii) With the different number of triggers, our method demonstrate consistently superior performance in defense, with ASR close to 0% and ACC comparable to Clean ACC. Notably, when the number of triggers is 240 for PubMed, the detection recall is around 66%, but we still achieve good results in terms of ASR and ACC. This further indicates the stability of method in training a robust node classifier using Eq. 0 some poisoned nodes are not identified. Additional results on the visualization of prediction variance for poisoned nodes and clean nodes with different numbers of triggers are provided in Fig. Iland and
if
Fig.
13
g
Possoned
Pecorvee
Pannt 1n
Precktioon Verlence
Prodict Variance
Verience
Variance
(a)
(b)
(c)
Figure 11: Visualization of prediction variance on Cora dataset with different number of triggers
Elean Nodes Possoned Nodea
Clean Nodes Polsoned Modes
Clean Nodos
Clean Rocies
Clezn Novies Peisoned Notess
Polsoned Nodes
Palsoned Nodes
Prediction Viriance
Precktion Vertance
Predctin Venancs
Prededion Var ence
Presicion Varianc
(a) 20
(b) 80
(c) 160
(d) 240
(e) 320
Figure 12: Visualization of prediction variance on PubMed dataset with different number of triggers
ADDITIONAL RESULTS OF DEFENSE PERFORMANCE AND ABILITY TO DETECT POISON NODES WITH TRIGGER SIZE AS
In this section, we conduct experiments to investigate how different trigger sizes impact the perfor- mance of RIGBD in terms of backdoor defense and poisoned node detection. Specifically, we set the trigger size to and conducted experiments the Cora, Citeseer, Pubmed, and ogbn-arxiv datasets, keeping all other settings the same as in Section 5.2. The results are shown in Table [2] demonstrating that RIGBD achieves strong performance with trigger size of 1.
26

---

Published as a conference paper at ICLR 2025
Table 12: Result of backdoor defense with trigger size
Dataset
Method
ASR
ACC
Recall
Precision
UGBA
92.53
82.22
Cora
RIGBD
0.44
83,70
83.9
92.9
UGBA
95.24
74.69
Citeseer
RIGBD
0.00
73.20
98.7
98.7
UGBA
92.58
84.58
Pubmed
RIGBD
0.32
84.83
94.0
97.5
UGBA
85.29
65.38
OGB-arxiv
RIGBD
0.00
65.92
92.7
99.8
REPRODUCIBILITY
Experimental and implementation details are in Sec. 5.1 and Appendix H We provide
detailed algorithm description in Algo. 1
The code for RIGBD is publicly available at:
github.com/zxjjams//GGGBB
R
LIMITATIONS AND FUTURE WORK
Our proposed framework aims to defend against graph backdoor attacks during the training phase. We believe it is also important develop new techniques defend against graph backdoor attacks during the inference stage, which we leave for future work. As the first work targeting all existing representative graph backdoor attacks, we hope inspire future development defense algorithms. Additionally, this paper focuses exclusively on graph-structure data, and would interesting explore extensions to other domains. Given the nature of this work, there no easily predictable negative social impacts.
graph backdoor
27


Reviews:
[{"review_id": "YU1OwRFrWF", "reviewer": "Reviewer_PrW3", "summary": "This paper proposes a novel defense method against graph backdoor attacks, which is composed of poisoned nodes detection and robust training. In poisoned node detection, this paper first observes that edge dropping significantly influences the prediction of the poisoned nodes and then this has been theoretical verified. After this, this paper proposes to utilize random edge dropping to detect poisoned nodes efficiently based on poisoned GNN model. After detection, the poisoned model will be finetuned by the detected nodes to remove the influence of the backdoor attack.", "questions": "Please refer to weaknesses.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The idea is novel and interesting, and is well evaluated empirically and theoretically.\n2. In addition to the detection of poisoned node, this paper also proposes robust training to enhance defense performance further. This can safeguard GNN models against different kinds of attacks.\n3. A well-written paper, and easy-to-follow.", "weaknesses": "1. To verify the effectiveness and generalization of the proposed defense, I suggest author deeply discussing the mechanism of dirty-label backdoor attacks against GNNs. \n2.  I find out that the discussion among baselines and the proposed defense is missing, e.g., why the proposed work only performs better on defending DPGBA. This also weakens the contribution of this work. Finally, I find that the baselines are not targeted at graph backdoor attacks, e.g., GNNGuard targets defending adversarial attacks while ABL targets traditional DNNs. It is important to compare with other defense strategies against graph backdoor attacks. \n3. I find that the idea of this paper is very similar to the motivation of the influence function which aims to measure the impact of deleting edges and nodes by influence function (in this paper authors use predicted probability) and does not require retraining or fine-tune the poisoned model. I suggest authors discuss and compare with backdoor defense strategies using influence function.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MxwNrQIDhs", "reviewer": "Reviewer_TH4V", "summary": "This paper presents Robustness-Inspired Graph Backdoor Defense (RIGBD) to defend against subgraph-based graph backdoor attacks. The authors demonstrate that poisoned nodes exhibit significant prediction variance when anomalous edges linked to them are removed, and propose a robust training strategy to mitigate the effects of backdoor triggers. Their method effectively identifies poisoned nodes, reduces attack success rates, and preserves clean accuracy across various datasets.", "questions": "- Would RIGBD be effective for non-subgraph graph backdoor attacks?\n- How does RIGBD apply to all-to-all backdoor attacks, where different samples have different target labels?\n- How does RIGBD adapt to the special case mentioned in weakness 2?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- RIGBD is specifically designed for graph-structured data, effectively leveraging the behavior of malicious edges linking trigger subgraphs to poisoned nodes. The core insight—that the implanted trigger influences prediction by transmitting malicious information through these edges—is particularly valuable in identifying poisoned nodes.\n\n- This paper introduces an intriguing observation: simply removing backdoor triggers does not necessarily immunize the model against backdoor attacks. This insight opens up new directions for designing graph backdoor defense.\n\n- The paper provides a thorough theoretical analysis that explains why random edge dropping can effectively distinguish poisoned nodes from clean ones.", "weaknesses": "- Though experiments demonstrate the superiority of RIGBD against subgraph-based backdoor attacks, its resistance against other forms of graph backdoors, e.g., injecting backdoors in the spectral domain [1], remains unevaluated.\n\n- The method proposed for determining target nodes and labels seems to lack robustness. Specifically, the authors suggest ranking nodes in descending order based on prediction variance after random edge dropping, selecting the top-ranked nodes until a node label differs from the previous one. This approach could be susceptible to outliers or special node characteristics, such as nodes with few neighbors and high class-diversity among them, which may result in large prediction variance under random edge dropping. Such nodes may halt the poisoned node selection process or even lead to incorrect target class identification.\n\n[1] Zhao, Xiangyu, Hanzhou Wu, and Xinpeng Zhang. \"Effective Backdoor Attack on Graph Neural Networks in Spectral Domain.\" IEEE Internet of Things Journal (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UF65tjuFee", "reviewer": "Reviewer_MqFW", "summary": "This paper shows that poisoned nodes exhibit high prediction variance with edge dropping. The authors propose random edge dropping, supported by theoretical analysis, to efficiently and precisely identify poisoned nodes. Furthermore, the authors introduce a robust training strategy to efficiently counteract the impact of the triggers, even if some poisoned nodes remain unidentified.", "questions": "1. Targeted attack generates attacks on specific nodes and aims to fool GNNs on these target nodes. Can the proposed method defend targeted attack strategies on graphs, such as nettack[1].\n2. RIGBD minimizes the predicted confidence of the target class of the poisoned node in Eq. 6, and uses the remaining labeled nodes to calculate the cross entropy loss. If the number of attacked nodes is too large, will this cause insufficient supervision information?\n\n[1] Adversarial attacks on neural networks for graph data, KDD 2018.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The structure of the paper is clear and easy to follow.\n2. The paper conducts comprehensive experiments to demonstrate the performance of proposed method.", "weaknesses": "1. There are concerns about the efficiency of the method. First, the proposed method requires training the GNN encoder twice, which incurs a large overhead cost, especially in larger datasets such as obg-products[1]. In addition, when calculating the prediction variance, it is necessary to infer K times on the graph, which also brings a large overhead.\n2.  The proposed method seems to rely on the homogeneity assumption. In heterophilic graphs, nodes tend to connect to nodes that share different labels with them. Would this result in normal nodes also having higher prediction variance after random edge dropping? It is recommended that the author can give the performance of this method on backdoor attacks in heterophilic graph datasets.\n\n[1] Open Graph Benchmark: Datasets for Machine Learning on Graphs, NeurIPS 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GWBI8nhDlv", "reviewer": "Reviewer_Xv7r", "summary": "The paper introduces RIGBD, a novel framework for defending Graph Neural Networks (GNNs) against backdoor attacks. It leverages **random edge dropping** to identify poisoned nodes by detecting high prediction variance, and incorporates a **robust training strategy** to reduce the prediction confidence on these nodes, limiting the impact of triggers. The method is theoretically sound and empirically validated on real-world datasets, showing it can effectively decrease attack success rates while maintaining clean accuracy. Key strengths include scalability and robustness, though the method relies on hyperparameter tuning and may face challenges with indistinguishable poisoned nodes.", "questions": "1. In the related work, the SBA method was mentioned. While I understand that SBA may have a low ASR, I am unsure about how your method defends against SBA specifically, as there are no experimental results regarding this method. Could the authors provide a simple experiment to illustrate the defense mechanism against SBA?\n\n2. The paper does not mention any adaptive attacks. Are there any potential ways to design adaptive attacks targeting this method?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Effective Identification of Poisoned Nodes: The use of random edge dropping as a technique for distinguishing poisoned nodes from clean nodes is innovative and theoretically backed. The method efficiently handles large-scale graphs by reducing the computational burden that would otherwise be associated with processing each edge individually.\n\n2. Stability for Clean Nodes: The approach ensures that clean nodes maintain prediction stability, which prevents sensitivity toward non-poisoned nodes.", "weaknesses": "1. Dependency on Hyperparameters: The effectiveness of the random edge drop rate (𝛽) and the number of iterations (𝐾) can vary significantly across different datasets, requiring careful tuning and potentially reducing generalizability. Additionally, there is no theoretical guarantee for selecting the optimal values for these hyperparameters.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)