Attack by Yourself: Effective and Unnoticeable Multi-Category Graph Backdoor Attacks with Subgraph Triggers Pool
Authors: Jiangtong Li
Dongyi Liu
Kun Zhu
Dawei Cheng
Changjun Jiang
Venue: NeurIPS 2025 poster ()
Keywords: Graph Backdoor Attack
Graph Neural Networks
Node Classification
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: Graph Neural Networks (GNNs) have achieved significant success in various real-world applications, including social networks, finance systems, and traffic management. Recent researches highlight their vulnerability to backdoor attacks in node classification, where GNNs trained on a poisoned graph misclassify a test node only when specific triggers are attached. These studies typically focus on single attack categories and use adaptive trigger generators to create node-specific triggers. However, adaptive trigger generators typically have a simple structure, limited parameters, and lack category-aware graph knowledge, which makes them struggle to handle backdoor attacks across multiple categories as the number of target categories increases. We address this gap by proposing a novel approach for Effective and Unnoticeable Multi-Category (EUMC) graph backdoor attacks, leveraging subgraph from the attacked graph as category-aware triggers to precisely control the target category. To ensure the effectiveness of our method, we construct a Multi-Category Subgraph Triggers Pool (MC-STP) using the subgraphs of the attacked graph as triggers. We then exploit the attachment probability shifts of each subgraph trigger as category-aware priors for target category determination. Moreover, we develop a ``select then attach'' strategy that connects suitable category-aware trigger to attacked nodes for unnoticeability. Extensive experiments across different real-world datasets confirm the efficacy of our method in conducting multi-category graph backdoor attacks on various GNN models and defense strategies.

Attack by Yourself: Effective and Unnoticeable Multi-Category Graph Backdoor Attacks with Subgraph Triggers Pool
Jiangtong Li Dongyi Liu"!!, Kun Zhu Dawei Cheng
Changjun Jiang
1. Key Laboratory of Embedded System and Service Computing, Ministry of Education, Tongji University
2. School of Computer Science and Technology, Tongji University {jiangtongli, 2152833, kzhu00, dcheng, cjjiang)&tongji edu cn
Abstract
Graph Neural Networks (GNNs) have achieved significant success various real-world applications, including social networks, finance systems, and traffic management, Recent researches highlight their vulnerability to backdoor attacks in node classification, where GNNs trained a poisoned graph misclassify test node only when specific triggers are attached. These studies typically focus on single attack categories and use adaptive trigger generators create node-specific triggers. However, adaptive trigger generators typically have simple structure, limited parameters, and lack category- struggle to handle backdoor attacks across multiple categories as the number of target categories increases. We address this gap by proposing a novel approach for Effective and Unnoticeable Multi Calli--attegory (EUMC) graph backdoor attacks, leveraging subgraph from the attacked graph as category-awad aware triggers precisely control the target category. To ensure the effectiveness of our method, we construct a Cutti-Categgry Subgraph Triggers Pool (MC-STP) using subgraphs of the attacked graph triggers. We then exploit the attachment probability shifts of each subgraph trigger as category-aware priors for target category determination. Moreover, develop "select then attach" strategy that connects suitable category- aware trigger to attacked nodes for unnoticcability. Extensive experiments across different real-world datasets confirm the efficacy of our method in conducting multi- category graph backdoor attacks on various GNN models and defense strategies. Code is released at https: /etpss//gitthbe com/ http///ovwddooeeeee/eeeeeeaaaeae EEMC
graph knowledge, which makes them
Introduction
In recent years, GNNs 2 have achieved significant success in modeling real-world graph-structured data, including social networks B], financial interactions [4] 5, and traffic flows (6]. GNNs typically update node representations by aggregating information from their neighbors, which preserves the features of the neighbors and captures the local graph topology. However, GNNs are vuinerable to attacks, and numerous methods have been developed deceive these networks 77)
In graph adversarial attacks, adversaries can modify existing nodes or edges in the graph (Graph Modification Attack, GMA) [ or inject malicious nodes to the graph (Graph Injection Attack, GIA) 9 in evasion or poison settings. For instance, TDGIA 10 traverses the original graph to
Booth authors contributed equally research. # #Corresponding Authors
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Truining
Testing
Triggr Amneimect
CNN
Backdoored GNN
Backiooss
Singlo-category graph backdoor attack
Trigest Ainslaneni
GNN
Badidiooed GNN
Bartooon
Multi-calegory graph backdoor attack
Figure 1: The comparison between single-category and multi-category graph backdoor attack on node classification.
Table 1: The ASR(%) of UGBA against defenses on Flickr as the number of target categories changes.
Defense
7
None
99.7
98.1
65.5
49.2
34.6
29.9
24.7
Prune
99.4
99.0
66.0
49.5
37.1
26.7
24.4
Prune+I.D
99.3
98.5
71.8
50.3
38.0
30.1
23.7
identify vulnerable nodes using topological defective edge strategy and generates features for injected nodes with smooth feature optimization objective. However, these attacks often lead to suboptimal efficacy and challenges in achieving specific objectives [10]. Furthermore, they usually change the homogeneity of the attacked graph and require large attack budgets [T]] making the alterations easily detectable. The visibility not only diminishes the efficiency needed for effective adversarial strategies but also limits their practical applicability unnoticeable scenarios.
To address these issues, developing graphs backdoor attacks is a promising approach, which typically unfold in three steps. Initially, adversaries create a poisoned graph by attaching trigger small set of nodes known as poisoned samples and assigning them the label of the target category. Sub- sequently, when GNNs are trained on this poisoned graph, they learn associate the trigger with the target category. In the inference, only the nodes that are linked with the triggers are predicted as the corresponding target category, while clean nodes are predicted as usual. Compared to graph adversarial attacks, graph backdoor attacks offer three primary ad advantages: 1) Lower Computational Cost: the attack requires no additional optimization during inference; 2) More Precise Target Control: the triggers directly influence the prediction of the target category; 3) Higher Unnoticeability: the backdoor activates only when specific triggers appear.
Recent works have primarily focused on enhancing backdoor attacks for graph classification, yet node classification remains underexplored. GTA [12 explores an adaptive trigger generator create more powerful, node-specific triggers for node classification. To reduce attack budgets and enhance the unnoticeability of backdoor attacks, UGBA [I3] selects representative nodes as poison nodes and optimizes the adaptive trigger generator with an additional unnoticeable loss and DPGBA [14) exploit the GAN loss preserve the feature distribution within the generated triggers. These graph backdoor attack methods focus on targeting a specific category, allowing backdoored models to consistently produce a predetermined malicious category when triggers are attached. However, they lack the capability to effectively attack across multiple categories, i.e., manipulating the model to predict different target categories for the same node using various triggers. This limitation primarily stems from the use of adaptive trigger generators designed for backdoor attacks. These generators usually have a simple structure and limited trainable parameters, which constrain their ability to generate triggers for multiple attacked target categories. Furthermore, these generators lack category-awan graph knowledge, such as understanding how different subgraphs influence classification results on various nodes. As result, they struggle to optimize multiple adaptive trigger generators for different target categories as the number of target categories increases. In Table [ confirm this limitation on Flickr [15].
we further empirically
In this paper, we address the complex issue of multi caltii-cateoryy graph backdoor attacks on node classifi- cation, as depicted in Figure We introduce the Effective and Unnoticeable Multi- Caltii-Caaggryyy (EUMC) graph backdoor attack method, which utilizes influential subgraphs from the attacked graph as triggers. Our approach constructs Multi- Hulti-Category Subgraph Triggers Pool (MC-STP) to manage different target categories, effectively cireumventing the optimization challenges associated with multiple trigger generators. Specifically, we start by sampling hundreds of subgraphs from the attacked graph

---

to establish the base of our MC-STP, For each subgraph, we calculate the attachment probability shifts by assessing whether the subgraph is attached given nodes. This process identifies the influential subgraphs and determines the target categories for each, as depicted in 2 and discussed in Sec- tion[4.) [.1] To ensure unnoticeability, we further develop "select then attach" strategy that selects the suitable subgraph trigger from the pool and properly connects it to each attacked node. Note that the subgraph triggers for backdoor attack are from the original graph, therefore, the feature distribution can also be well preserved. Through these steps, EUMC achieves control over node classifications within the graph backdoor attack, manipulating them effectively. Extensive experiments across six real-world datasets confirm the efficacy of our method in conducting multi-categon graph backdoor attacks on various GNNs and defense strategies. Our main contributions can be summarized as
We study a novel and challenging problem of effective and unnoticeable multi-category graph backdoor attack.
We design a framework that constructs a MC-STP from the attacked graph and develop "select then attach" strategy to ensure the unnoticeability and effectiveness of the multi- category graph backdoor attacks.
Extensive experiments on node classification datasets demonstrate the efficacy of our method in multi-category graph backdoor attacks various GNN models and defense strategies.
2 Related Works
2.1 GNNs on Node Classification
GNNs are highly effective in node classification tasks, playing a crucial role in interpreting graph- structured data. These networks leverage relational information between nodes through message- passing mechanism, updating node features based on their neighbors' information
[16]. This process captures both local node features [17] and global structural context [8] 19]. enabling accurate node classification in complex networks [20]. GNNs encode node and topological features through itera- tive aggregation and feature transformation, enhancing the precision of node classification. Recent advancements include the development of sophisticated aggregation functions (2T 22 that capture nuanced node interactions. Attention mechanisms [3] and transformer layers [24] refine the aggre- gation process, improving model adaptability. Moreover, multi-scale feature extraction methods [25] allow GNNs to consider various neighborhood sizes, enriching representational capability and boost- ing classification performance across diverse datasets. In this paper, we utilize GCN [16), GAT (23). and GraphSAGE 266] exemplify node classification networks in our backdoor attack studies.
2.2 Adversarial Attacks on GNN
Based on the type of manipulation on the graph, graph adversarial attacks can be categorized into GMA 27 and GIA 28). In GMA, attackers deliberately alter existing nodes edges within the graph to compromise the model's integrity. These modifications aim to degrade the performance of GNNs by inducing misclassifications erroneous predictions. Conversely, GIA involves introducing fake nodes and edges into the graph. This method is particularly effective as it allows attackers to add new structural data specifically designed mislead the GNN without altering the original graph's properties. Common optimization techniques for these adversarial attacks on graphs include the use of gradient descent (27 10] find optimal perturbations and reinforcement learning 28 to dynamically adjust attack strategies based on the GNNs' responses.
2.3 Backdoor Attacks on GNN
Backdoor attacks on GNNs typically insert triggers into the training graph and assign the desired target label to samples containing these triggers. Consequently, a model trained on this poisoned graph is deceived when it processes test samples with specific triggers. Backdoor attacks vary by tasks and learning paradigm, like graph classification [29], node classification [1], graph contrastive
learning (30, and graph prompt learning [31] For graph classification, common method transforms edges and nodes into predefined subgraph (32] while Xu and Picek (33) enhance unnoticeability
by assigning triggers without altering the labels of poisoned samples. In node classification, efforts to
manipulate node and edge features for backdoor attacks often face practical challenges, changing
3

---

34 Furthermore, GTA [22 employs an adaptive trigger generator to create specific triggers, UGBA uses represen- tative nodes to refine this generator for unnoticeabilityy and DPGBA [14] exploit the GAN loss to preserve the feature distribution within the generated triggers. However, adaptive trigger generators often have a simple structure and limited parameters, lacking category-aware graph knowledge to manage multiple category backdoor attacks as the number of target categories grows. Our work develops an effective and unnoticeable multi-category graph backdoor attack, enabling the attacker to control the predicted categories with varied triggers. In detail, we first constructs a MC-STP, using attachment probability shifts as category priors, and then develops a "select then attach" strategy that connects suitable trigger to attacked nodes, ensuring the unnoticeability and effectiveness.
existing nodes' links and attributes is typically outside control of the attackers
3 Preliminary
3.1 Node Classification
We represent a graph with G (V, X), where V {u1, ux) denotes the set of nodes, A E RRNNN the adjacency matrix of graph 9, and X (xi, xN) represents the features of nodes with x; corresponding to v;. Here, Aij = 1 indicates connection between nodes and ey; otherwise, Ay = O. The node classification task takes graph G as input and outputs labels for each node in V. Formally, the GNN node classifier fo g" + {1, 2.... the computation graph for node and (1. is the set of possible labels. The classifier Se generates node feature iteratively by aggregating the feature of its neighbors, with the final neural network layer outputting label for different nodes. In this paper, we focus on the semi- supervised node classification task inductive setting. The whole graph split into labeled graph GL (V2,A,, X and unlabeled graph Gu (Vu, Au. Xu) with no overlap, VL O Ve 0.
.... K}. where G' represents
3.2 Threat Model
Attacker's Goal The goal of the attacker is to mislead the GNN to classify target nodes with attached trigger the target category. Moreover, for the same target node, the attacker can manipulate the GNN model to predict different target categories by attaching category-aware aware trigger. At the same time, the GNN should function normally for clean nodes that do not have triggers attached.
Attacker's s Knowledge and Capability In most backdoor attack scenarios, the training data for the target model is accessible to attackers, although the architecture of the target GNN model remains unknown to them. Attackers can attach trigger and label to nodes within a budget before training the target models to poison the training graph. In inference, attackers can attach trigger to the target node.
3.3 Backdoor Attacks for Node Classification
The fundamental concept of backdoor attacks involves linking a trigger with the target category in the training data, causing target models misclassify during inference. As depicted in Figure [ in training, an attacker attaches a trigger to a subset of nodes Vp C Vy and assigns them the target category label yt. More details about the Vp and attachment strategy of our method are in Section 4
GNNs trained on this backdoored dataset learn to associate the presence of trigger with the target category yt. During testing, attaching trigger / to a test node causes the backdoored GNN to classify e as category yr- To evaluate the performance of our backdoor attack, the labeled graph Gr. is split into training graph GTr. validation graph Gva, and test graph GTe with no overlap Farlier efforts [22 [3] have advanced backdoor attacks on node classification by creating nodc-specific triggers adjusting node and edge features for smoothness [35]. Our work addresses the challenging problem of multi-category graph backdoor attacks, illustrated in Figure [ (b). For each node in poisoned nodes set Vp, we attach it with a category-awand trigger t. and assign corresponding target categories l/k Consequently, during the test phase, different triggers t4 can misclassify a test node v into the corresponding target category yk. Unlike methods focused on a single target category, our approach creates diverse triggers tailored to multiple target categories. Existing methods employ an adaptive trigger generator to generate the trigger for single target category. In T we extend UGBA [K] by increasing the number of target categories from to 7 on the Flickr dataset with multiple adaptive trigger generators to handle different target

---

Poios Noce Vy
Clos Gruphi
Subgrphi Frompti
Attacieed Gruph
Clean Gruph
Singrape froegr Sclesion &
Backanmell Graph
Sampa
Azadezas
Subymaph Filtering Labeling
Mulliscnegury Subgraph
Prompt Pool
Hinge
Label O
Sumggiee
Bi le-level Optimistion
Label
Cleas GUN
Polihilty Dumikiie Clear Srayk
Probebiity Distiaakis
Allick Goppl
Figure 2: The illustration of our method on multi-category graph backdoor attack.
categories, Experimental results demonstrate that effectiveness diminishes as the number of target categories increases. To address these challenges, we employ category-awad subgraphs as triggers to enhance the effectiveness of multi-category graph backdoor attacks. Formally, the multi-category graph backdoor attack for node classification is defined as follows:
(DTr,Ar XTr) and corresponding labels VIr, and another subset Ve without labels, our goal is to optimize a MC-STP, P = {3 Ii....,"poon ("ooo)] ;..;; YK : -..g.-..'' (eroo)).. We explore a trigger attacher ag to select trigger 1i from P uu and attach them to poisoned nodes Vr. The training objective is that GNN fo trained on the poisoned graph will classify a test node attached with trigger tx into target category yk:
Definition 1 Given clean training graph GTr
min P
Σ
Σ
(ffe(aa Pyx 1),)). 1).b))
10 NVV
K)
s.t.0
arg min
Σ
1[foltrr v)))
(Lp(a vk))). WEVV kE(T.....)
Σ
Σ
NEVT.
where 1(-) the cross entropy loss for node classification. The architecture of the target GNN f unknown and may include various defense mechanisms.
Methodology
In this section, detail method, designed optimize Eq. 1 for unnoticeable and effective multi-category graph backdoor attacks, as depicted in Figure 2 Our approach involves a MC-STP P. trigger attacher ag, and surrogate GCN model fa. Initially, we sample several subgraphs from the clean training graph Gry- Each of these subgraphs is then inserted into pre-selected representative nodes of the clean training graph, and GCN, trained on this graph, calculates the probability shift before and after the insertion. Based on this shift, we select influential subgraphs and determine the target label for each initialize the MC-STP. The trigger attacher then selects an unnoticeable subgraph trigger for each poisoned node Vr and attaches this trigger effectively to deceive f.. To ensure the effectiveness of the multi-category graph backdoor attack, we employ with the surrogate GCN model.
bi-level optimization 12 13
4.1 Multi-category Subgraph Triggers Pool
As discussed Section 3.3 adaptive trigger generators [3] struggle as the number of target categories increases. Therefore, we construct MC-STP to effectively execute backdoor attacks multi- category graph backdoor attacks. To this end, we initially randomly select several nodes from the unlabeled graph, Vy. to serve as central nodes. We then employ the Breadth- First Search (BFS) algorithm to sample subgraphs around each central node, which form the basis of our MC-STP, To ensure that the sampled subgraphs influential for node classification and provide sufficient misleading priors for backdoor attack, we develop an algorithm based on attachment probability shifts. This algorithm filters the subgraphs, assigning each influential subgraph with a target category.
Specifically, we first train a clean two-layer GCN network, fo,, on the training graph Gry for node classification ny categories, where ny is number of target categories. This GCN is utilized to assess
5

---

the misleading effects of different subgraph triggers. Subsequently, we apply K-Means clustering, as described UGBA [3, select representative nodes Vp as poisoned nodes, where the sizes of VpP for different datasets are shown in Table 2 These poisoned nodes Vp are then used to calculate the attachment probability shifts. During this process, we attach each candidate subgraph t to all nodes in Vp and use fe. to compute the variance in prediction probability for Vp before and after the attack as the Attachment Probability Shift (APS), which is defined as:
APS; 1
Σ VEEVP
fo. (as - (9p)
(I)
[Vpl
where (.)+) is the trigger attacher, Gj. is the computation graph for node vs and APS, E RD is vector to measure the probability shift among different target categories.
The APS quantifies the misleading effect of each subgraph trigger. Therefore, we select subgraphs with max(APS,) > 0.2 as influential triggers, and the attack target category is then determined by C: arg max(APS,) Then we retain the top- subgraph triggers (measured by max (APS)) in each target category to form the MC-STP, P {yı " "" ]:...:K. yK itk..... & (i B. In this way, the MC-STP introduces category- aware prior, indicating the graph can attack itself. On the one hand, it contains a rich set of subgraph triggers for various attack scenarios; on the other hand,
each target category is controlled by influential subgraphs, facilitating the optimization.
4.2 Trigger Selection and Attachment
To effectively inject the trigger from the MC-STP, P. we address two critical questions: 1) which trigger from the pool should be used for backdoor attack given the target category; and 2) how the trigger should be attached attacked nodes. To ensure the triggers remain unnoticeable, we develop a "select then attach" strategy based on node similarity. For unnoticeable and effective backdoor attack, we first select the subgraph trigger by comparing cosine similarity between the subgraph features and the attacked node features. For a poison node i; E Vp. the selection is formulated by:
Σ
Xx
X;
X 2 X; 2
N X.EX
where x; is the feature of Us. The trigger with the highest st2 is selected for backdoor attack.
Our method focuses conducting unnoticeable and effective graph backdoor attacks. To ensure a basic backdoor attack, it is necessary to attach at least one node from the subgraph trigger to the attacked node. To enhance the unnoticeability of the graph backdoor attack, we need attach nodes from the subgraph trigger that exhibit relatively high similarity to the attacked node. To improve the effectiveness of the graph backdoor attack, more nodes from the subgraph trigger are attached to the attacked node. Therefore, the trigger attacher, (.).,, operates by: 1) calculating the similarity between the subgraph trigger and the attacked node; 2) attaching the node with the highest similarity from the subgraph trigger to the attacked node; 3) attaching nodes with a similarity greater than Ta from the subgraph trigger to the attacked node, where Ta is the similarity threshold. This approach balances the effectiveness and unnoticeability of the backdoor attack when attaching subgraph trigger.
4.3 Optimization
To ensure the effectiveness and unnoticeability of the graph backdoor attack, we optimize the MC- STP, P through a bi-level optimization to successfully attack the surrogate GCN model fa. The training of the surrogate GCN Sa on the poisoned graph is formulated as:
min L. (0.
Σ ((foGGrrs.)) v:)) WEV.r
Σ Σ
[(fola(Gp, P Pon)),
(3)
B KE (E(......K)
where 02 and 0p are the parameters of the surrogate GCN and MC-STP. 9 is the clean labeled training graph for node v, with label ye, and yk is the attack target label of al) P..).. For effective misleading, P and as must induce surrogate model to classify nodes with triggers as target category:
La Σ Σ
USs(a(O)), P).)). yk),
4
VEVV KE

---

Algorithm Algorithm of EUMC.
Input: Original graph 9, target category set V=1, .... K
Parameter: a
Output: MC-STP (P), Backdoored Graph (GB)
Initialize GB 9;
2: Separate the training graph GTr from labeled graph GL;
3: Select poisoned nodes Vp based on the cluster algorithm from UGBA 13
4: Randomly initialize 0, for fa:
5: Initialize with 0 as parameter based on the construction of MC-STP Section 4.1
6: while not converged do
7: for t=1,2.....N do
8: Update 0, by Vo,C. based on 3q
9: end for
10: Update 0p by (Cp aChi) based Eq
11: end while
12: for v, 1/p do
13: Random select the attack target category yk from V
14: Update Gg with as (G' : p based the "select then attach" strategy in Section 4.2
15: end for
return P and Gn;
Moreover, all attached nodes should closely resemble the attacked node, formulated as:
LA Σ Σ
max(0, 7I. cos(r; my)),
(S)
WEVP (HE.P))EE)
where Ef comprises all edges connecting the attached nodes from the subgraph trigger to node Ui. Tr the similarity threshold, and cos(.) the cosine similarity. Thus, we formulate the following bi-level optimization problem with balance hyper-parameter at
min Lp (0' 0p) La + aCh Op
s.t. 0 = arg min L. (0,. 0p).
6,
To reduce computation cost, L. in Eq. calculated by randomly assigning target category yk to Therefore, the computational complexity is irrelative to the number of target category. More details about the analysis of time complexity can be found supplementary materials. We adopt the bi-level optimization B to update Eqs. and 6 as outlined in Algorithm
5 Experiments
5.1 Experimental Settings
Datasets. To demonstrate the effectiveness of our method, we conduct experiments on six public real-world datasets:
Cora, Pubmed (36), Bitcoin [37], Facebook (38), Flickr [13], and OGB-arxiv [39]. These datasets are widely used for inductive sepe-supe node classification. Cora and Pubmed are small-scale citation networks, while Bitcoin represents an anonymized network of Bitcoin legality transactions. Facebook is characterized by page-page relationships, Flickr links image captions that share common properties, and OGB-arxiv a large-scale citation network. The statistics of these datasets are provided in Table 3a
Compared Methods. We compare our method with representative and state-of-the-art graph backdoor attack methods, including SBA [2), GTA [22. UGBA [33, and DPGBA [14. We apply Prune and Prune+LD 13 for attribute-hased defense, which prune edges based on node similarity. We also
apply OD [4] for distribution-base defense, which trains a outlier detector (i.e., DOMINANT (40]) to filter out outlier nodes. Hyper-parameters are determined based on the validation performance. More details are in supplementary material.
Evaluation Protocol. Following similar setup as in UGBA, we randomly mask 20% of the nodes from the original dataset. Half of these masked nodes are designated target nodes for evaluating
7

---

Table 2: Backdoor attack results (ASR (%)
CA (%)).
Only CA is reported for clean graphs.
|/pl
Defense
Clean
UGBA
DPGBA
HUMC
None
82.5
14.3
82.9
87.7
77.4
83.1
73.4
87.3
82.5
97.4
82,4
Prune
81.4
14.3
81.8
15.2
80.2
84.8
72.9
84.3
82.3
93.5
82.2
Cora
Prune+LD
80.0
14.3
79.5
15.1
79.5
85.3
72.1
80.1
81.2
93.5
81.0
OD
83.5
86.6
79.8
83.1
81.9
None
84.3
33.3
85.1
86,9
84.8
88.9
84.7
91.5
85.3
96.4
83,9
Prune
83.7
33.3
85.3
33,4
84.9
92.6
84.5
89.5
85.0
95.0
83,9
Pubmed
Prune+LD
84.2
33.3
83.6
33,4
83.7
85.8
83.7
92.1
84.5
95.3
83.4
OD
84.9
33.3
85.3
88.6
85.4
89.7
85.4
89.5
85.1
96.2
84.6
None
33.3
78.3
79.2
78.3
76.4
78.3
80.1
78.3
90.6
78.3
Prune
78.3
33.3
78.3
37.6
78.3
73.3
78.3
33.3
78.3
88.3
78.3
Bitcoin
Prune+LD
78.3
33.3
78.3
42.6
788.
72.0
78.3
33.3
78.3
$6.5
78.3
33.3
78.3
78..
78.3
77.6
88.4
78.3
None
25.0
84,9
85.8
83.8
Facehook
Prune
81.5
25.0
86.2
25.5
85.6
86.4
85.5
72.4
85.3
91.7 83.3
Prune+LD
81.0
25.0
86.0
25.3
85.3
73.9
84.6
75.4
85.2
92.0
83.3
25.0
77.2
85.5
82.4
85.9
84.3
None
14.3
24.6
43.4
90.4
Prune
45.1
14.3
42.8
15,0
41..5
24.4
42.9
68.6
44.8
90.3
44.1
Flickr
Prune+LD
44,5
14.3
45.0
14.6
44.2
23.7
42.6
18.2
45.0
90.8
44.2
OD
14.3
26.4
41.9
18.1
44.1
79.7
44.6
None
64.8
68.4
65.66
63.7
64.9
68.8
83.8
65.3
Prune
64.9
2.5
64.6
3.1
66.00
69.3
65.1
13.0
65.0
84.1
65.5
OGB-arxiv
Prune+LD
63.9
2.5
64.9
3.3
65.3
69.4
65.2
6,2
65.0
84.2
65.3
ODD
63.8
62.6
65.2
54.1
83.4
attack performance, while the other half serve as clean test nodes to assess the prediction accuracy of backdoored models on normal samples. The graph containing the remaining 80% of nodes used as the training graph Gr,, with the 20% nodes V/, are labeled. We use the average Attack Success Rate (ASR) on the target node set across different target categories and clean accuracy on clean test nodes to evaluate the effectiveness of the backdoor attacks. To demonstrate the transferability of the backdoor attacks, we target GNNs with varying architectures, namely GCN, GraphSage. and GAT. We conduct experiments on each target GNN architecture five times and report the average performance. Further details about the time complexity analysis are supplementary materials.
Implementation Details. 2-layer GCN deployed as the surrogate model for all datasets. All hyper- parameter are determined based on the performance on the validation set. Specifically, a. trigger pool size, the trigger size, hidden dimension and inner iterations step is set as 40. 5, 64 and 5, respectively. Moreover, Tı. is set as 0.4, 0.4, 1.0, 0.5, 0.6, and 0.8 for Cora, Pubmed, Bitcoin, Fackbook, Flickr and OGB-arxiv, respectively. тa set as 0.2, 0.2, 0.8, 0.2, 0.2, and 0.8 for Cora, Pubmed, Bitcoin, Fackbook, Flickr and OGB-arxiv respectively. The pruning threshold Prune and Prune+LD defense is set to filter out 10% most dissimilar edges Therefore, the thresholds are 0.1, 0.1, 0.8. 0.2, 0.2, 0.8 for Cora, Pubmed, Bitcoin, Fackbook, Flickr and OGB-arxin respectively.
5.2 Main Results
In Table 2 compare with other four graph backdoor method six real-world datasets validate the effectiveness and unnoticeability of our method under different defense strategy, i.e., None, Prune, and Prune LD. The ASR and Clean Accuracy averaged on three GNN architectures: GCN, GAT, and GraphSAGE. Detailed comparisons for each GNN model are in supplementary material.
In terms of clean accuracy, EUMC achieves results comparable to other baseline models and GNNs trained on clean graphs, indicating that graph backdoor attacks minimally impact clean nodes due to the small proportion of poisoned nodes. From the perspective of ASR, EUMC excels the Cora, Flickr, and OGB-arxiv datasets, achieving state-of-the-ar performance. The large number of target categories (> 5) in these datasets demonstrates the effectiveness of EUMC in multi-category graph backdoor attacks. Moreover, EUMC outperforms other models on Bitcoin, Facebook, and Pubmed datasets, further validating the effectiveness of EUMC across varying target category numbers.
Comparing different defense strategies, EUMC demonstrates high effectiveness and balanced perfor- mance, indicating its ability to evade defenses and launch unnoticeable attacks. Comparing EUMC with UGBA and DPGBA on Flickr and OGB-arxiv, EUMC performs less effectively on the category- rich OGB-arxiv, which is consistent with expectations for multi-category attacks, i.c., the larger the
8

---

Table 3: (a) Dataset Statistics; (b) Ablation Study
Dataset
#Nodes
#Edge
#Feature
#Classes
Setting
None
Prune
Prume+LD
Cora
2,708
5,429
1443
7
wio
82.0 + 17.3
70.8
29.5
78.4 23.3
Pubmed
19,717
44,338
500
3
w/o feat
61.5 + 37,3
66.1
+ 33.8
43.4
34.6
Bitcoin
203,769
234,355
165
3
wfo Igt
67.4 +: 34.9
66.6
36.0
79.3
21.7
wio sele
69.8 1 35.6
74.0
1 22.3
77.7 24.2
Facebook
22,470
342.004
128
link all
79.7 - 14.1
75.8 = 18.2
88.8 12.9
Flickr
89,250
899,756
500
7
link one
75.3 1: 25.2
76.1 1: 23.2
75.9
23.7
OGB-arriv
169,343
1,166,243
128
40
Full
89.4
88.8 : 10.3
89,9 9.1
(a) Statistics the Cora, Pubmed, Bitcoin, Facebook, Flickr, and OGB-arxiv datasets.
(b) The average + standard deviation ASR(%) of EUMC under alternative setting on the Flickr dataset.
number of target categories, the lower the achievable ASR. Conversely, UGBA and DPGBA exhibits weaker performance on Flickr, highlighting the vulnerability of adaptive trigger generator based methods under unbalanced conditions. Overall, EUMC effectively and unnoticeably attack GNNs in multi-category setting, outperforming existing methods across diverse defense and datasets.
5.3 Ablation Study
To valid the effectiveness of the subgraph triggers pool and "select then attach" strategy, we conduct experiment on the Flickr dataset and report the average and standard deviation ASR(%) of GCN, GAT, and GraphSAGE. More ablation studies can be found in the supplementary material.
Construction of MC-STP. To validate the effectiveness of our MC-STP, we conduct experiments with different construction settings, i.e., randomly initializing the subgraph structure (w/o stru), the
subgraph features (w/o feat), and the target category (w/o target) as shown in Table 3b The results indicate that each of these settings significantly contributes to attack effectiveness, demonstrating the robustness of our MC-STP. Notably, node features from the clean graph have the most significant impact among them, underscoring the importance of node features in classification.
"Select and Attach" Strategy. To further validate the effectiveness of our "select then attach" strategy, conduct experiments with three alternatives: randomly selecting the subgraph trigger from the pool (w/o sele), attaching all nodes to the attacked node (link all), and attaching the most similar node to the attacked node (link one), as shown in Table 3bb The results demonstrate that our "select then attach" strategy outperforms all others. Both attaching more nodes or fewer nodes affects performance under different defense strategies, confirming the efficacy of our approach.
5.4 Similarity Analysis
We explore the impact of different attack types edge simi- larity in poisoned graphs. Specifically, we assess the effects GTA, UGBA, EUMC, and EUMC without La edge similarity between trigger edges (connected to trigger nodes) and clean edges (not connected to trigger nodes) on the OGB -arxiv dataset, as shown in Figure 3 The results reveal that in EUMC without Ln setting, the similarity between trigger and clean edges still exceeds that of GTA, due to our "select then attach" strategy. With the application of La, this similarity further increases the level of UGBA. This demonstrates that the unnoticeability of EUMC arises from both La and "select then attach" strategy.
Topprr Hagm
-3
Phop
2t USBA
Clenn Craas
happ Eays
2a FLIMC
Phon
Figure 3: Edge similarity distribu- tions OGB-arxiv.
6 Statistical Significant Test
We perform the significance test between our EUMC and the strongest baseline, i.e. DPGBA 14 We run our EUMC and DPGBA 5x4x3=60 times with three GNNs (GCN, GAT, and GraphSage) and four defense strategy with random seeds ranging from 1 to The ASR of our method are 95.3++2.1 1 and 83.8 10.6 in Core and OGB-arixv dataset, while the ASR of DPGBA are 84.9+66.7 and 56.8++30.7 in Core and OGB-arixv dataset. At the significance level 0.05, we perform significance test to verify that our method is better than DPGBA. The p-values in Core and OGB-arix dataset are

---

6.32x10 10 21 and 2.70x 10 which is far below 0.05, which demonstrates that the superiority of our method is statistically significant.
Limitation and Future Direction
While our method achieves strong attack success across multiple classification scenarios, we observe slight decrease in performance as the number of target classes grows. Although this degradation remains marginal and does not compromise the overall effectiveness, future work could explore scalable trigger generation strategies class-agnostic optimization techniques to ensure stable performance regardless label granularity. Moreover, our current focus has been predominantly on the attack side of backdoor research, with comparatively limited attention to defensive mechanisms. In follow-up studies, we plan to investigate lightweight yet robust countermeasures, such as real-tine anomaly detection, adaptive sanitization pipelines, defense- trigger designs, complement our attack framework and advance a more holistic understanding of backdoor vulnerabilities.
8 Broader Impacts
By advancing the study of backdoor attacks in graph neural networks, our work lays the groundwork for more realistic evaluations of model vulnerabilities in practical deployments. Demonstrating robust multi-category insertion techniques not only underscores potential risks in real-world applications but also serves as a importunate for the defensive research community to evolve beyond single-class mitigation schemes. In particular, our findings encourage the design of next next-generation defenses that can detect and neutralize backdoors across arbitrarily large label spaces, ultimately contributing to safer and more trustworthy AI systems.
9 Conclusion
In this paper, we tackle the complex challenge of conducting effective and unnoticeable multi-category graph backdoor attacks on node classification. We show that cxisting backdoor attacks, which rely on adaptive trigger generators, are not effective for managing multi-category attacks as the number of target categories increases. To address this, we construct multi-category subgraph triggers pool from priors
the subgraphs of the attacked graph and utilized attachment probability shifts as category- for subgraph trigger selection and target category determination. Moreover, we develop a "select then attach" strategy that connects appropriate trigger to attacked nodes, ensuring unnoticeability. Extensive experiments on real-world graph node classification datasets show the effectiveness and unnoticeability of method in controlling various GNNs for multi-category graph backdoor attacks.
Acknowledgments and Disclosure of Funding
This work supported in part by the National Key Research and Development Program of China (Grant No. 2022YFB4501 704), in part by the National Natural Science Foundation of China (Grant No. 62402341, 62472317, 62302337), in part by the Shanghai "Scientific and Technological Innova- tion Action Plan" High and New Technology Projects (22YS 1100600),,) in part by the Postdoctoral Fellowship Program of CPSF (GZC20241225), and in part by the China Postdoctoral Science Foundation (2025M771513).
References
Hamilton, W., Z. Ying, Leskovec. Inductive representation learning large graphs. In NeurlPS, vol. 30. 2017.
[2] Xu, K., W. J., Leskovee, et al. How powerful are graph neural networks? In ICLR. 2019.
[3] Wang, B., L. Zhang. N. Z. Gong. Sybilscar: Sybil detection in online social networks via local rule based propagation. In INFOCOM, pages 1-9. 2017.
[4] Cheng. D.. S. Xiang. C. Shang, al. Poatio-temports iientioo-basee neural network for credit card fraud detection. In AAAI, vol. 34, pages 362-369. 2020.
10

---

[5] Weber, M., G. Domeniconi. J. Chen, et al. Anti-money laundering in bitcoin: Experimenting with graph convolutional networks for financial forensics. arXiv preprint arXiv: 02591, 2019.
[6] Chen, C., K. Petty, A. Skabardonis, et al. Freeway performance measurement system: mining loop detector data. Transportation research record, 1748(1 1):96 102, 2001.
[7] Zügner. D., Günnemann. Adversarial attacks on graph neural networks via meta learning. ICLR. 2019.
[8] Dai, H., H. Li, T. Tian, et al. Adversarial attack on graph structured data. In ICML, pages 11 1115-1124. 2018.
[9] Madry, A., A. Makelov, L. Schmidt, et al. Towards deep learning models resistant to adversarial attacks.
In ICLR. 2018.
[10] Zou, X., Q. Zheng, Y. Dong, et al. Tdgia: Effective injection attacks on graph neural networks. In KDD, pages 2461-2471. 2021.
[11] Chen, Y., H. Yang. Y. Zhang, al. Understanding and improving graph injection attack by promoting unnoticeability. In ICLR. 2022.
[12] Xi, Z., R. Pang. S. Ji, et al. Graph backdoor. In USENIX Security, pages 5523-1540. 2021.
[13] Dai. E.. M. Lin, X. Zhang, et Unnoticeable backdoor attacks on graph neural networks. WWW. pages
2263-2273. 2023.
[14] Zhang, Z., M. Lin, E. Dai, al. Rethinking graph backdoor attacks: A distribution- Distribution-presrvvingg perspective. In KDD, pages 4386-4488 4666-4397220 2024.
[15] Zeng, H., H. Zhou, A. Srivastava, et al. Graphsaint: Graph sampling based inductive learning method. In ICLR. 2020.
[16] Kipf, N., M. Welling. Semi-supervised classification with graph convolutional networks. In ICLR. 2017. [17] Huang, Q., H. He, A. Singh, et al. Combining label propagation and simple models out-performs graph neural networks. In ICLR. 2021.
[18] Huang, N.. S. Villar, C. E. Priebe, et al. From local to global: Spectral-inspired graph neural networks. In NeurlPS (Workshop). 2022.
[19] Wei, Ping. Mei. Structure-based graph convolutional networks with frequency filter. Pattern Recognition Letters, 164:161-166 166116116,.1111 2022.
[20] Yu, E.-Y., Y.-P. Wang. Y. Fu, al. Identifying critical nodes in complex networks via graph convolutional Systems, 198: 105893, 2020.
networks. Knowledge-Rand
[21] Hu, Z., Y. Dong, K. Wang, et al. Heterogencous graph transformer. In WWW, pages 2704-2710 2020.
[22] Dong, W., Wu, Zhang, et Improving performance efficiency of graph neural networks by injective aggregation. Knowledge-
Systems, 254: 109616, 2022.
[23] Veličković, P., G. Cucurull, A. Casanova, al. Graph attention networks. In ICLR. 2018.
[24] Rampáššk, L., M. Galkin, P. Dwivedi, et al. Recipe for general, powerful, scalable graph transformer. In NeurlPS, vol. 35, pages 14501-14515. 2022.
[25] Chien, E., W.-. Chang, C.-J. Hsieh, al. Node feature extraction by self-supervised multi-scale neighborhood prediction. ICLR. 2022.
[26] Hamilton, W. L., R. Ying, J. Leskovec. Representation learning graphs: Methods and applications. IEEE Data Engineering Bulletin, 4(30):52-74. 2017.
2017.
[27] Zügner, D., A. Akbarnejad, S. Günnemann. Adversarial attacks on neural networks for graph data. In KDD, pages 2847-2851 2018.
[28] M., Y. Fan, C. Zhang, et al. Let graph be go board: gradient-fre node injection attack graph neural networks via reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 37, pages 4383-4390. 2023.
[29] Zhang, Z., Jia, Wang, et al. Backdoor attacks to graph neural networks. In SACMAT, pages 15-26. 2021.
[30] Zhang, H,, J. Chen, L. Lin, et al. Graph contrastive backdoor attacks. In ICML, pages 40888-40910, 2023.
[31] Lyu, X., Han. W. Wang, al. Cross-context backdoor attacks against graph prompt learning. In KDD. pages 2094-2105. 2024.
[32] Sheng, Y. R. Chen, G. Cai, al. Backdoor attack of graph neural networks based subgraph trigger. In CollaborateCom, pages 276 276-296. 2021.
[33] Xu. J., S. Picek. Poster: clean label backdoor attack on graph neural networks. In CCS, pages 3491-3493. 2022.

---

[34] Sun, Y., S. Wang, X. Tang, et al. Adversarial attacks on graph neural networks via node injections: A hierarchical reinforcement learning approach. In WWW, pages 673-683, 2020.
[35] Chen, Y. Z. Ye, H. Zhao, et al. Feature-based graph backdoor attack the node classification task. International Journal of Intelligent Systems, 2023()):5418899) 2023.
[36] Sen, P., Namata, M. Bilgic, et al. Collective classification in network data. Al 29g) 29(3):93-93, 2008.
[37] Elliptic. www.elliptie.co. 2020.
[38] Rozemberczki, B., Allen, R. Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9())cnab0044 2021.
[39] Hu. W. Fey, Zitmik, Open graph benchmark: Datasets machine learning on graphs. In NeurIPS, vol. 33, pages 22118-22133 2020.
[40] Ding, K., J. Li, R. Bhanushali, al. Deep anomaly detection attributed networks. In SDM, pages 594-604 2019.
12

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The contribution and scope have been reflected in the introduction and abstract, especially in the last part of the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
13

---

Justification:
The limitation is discussed in the last part of the submission.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approxinations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof'
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer:
[NA]
Justification: Our work does not include theoretical result.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have disclose all the information for reproduction in the, method, experi- ment and supplementary materials.
Guidelines:
14

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome deseribe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer:
[No]
Justification:
The dataset are open available, and the code will be released after acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
wtt.ssubmiiiioooooooooooooooe for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//ipps.cc/publi///guu
Codeeuumiiii wettsbbmmssiiioi ssionoolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
15

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The training and test details have been provided in the experiments and the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We have provided statistical significance tests in the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have provided the compute resources in the time complexity analysis.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
16

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpp:///aaarrg...c//aaaala/aatt
Answer: [Yes]
Justification:
This work match with the NeurIPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: materials.
We have discuss the broader impact in the last part of the supplementary
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses such risks.
Guidelines:
17

---

The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We have properly credited the original owners when using existing assets.
Guidelines:
The answer NA that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- ce-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
18

---

Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [Yes]
Justification: We have used the ChatGPT-4o for "Editing (e.g., grammar, spelling, word choice)" as stated OpenReview.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non non-standard components.
Please refer to our LLM policy for what should or should be described.
19

---

In the appendix, we provide additional materials to supplement our main submission. In Section A
we elaborate on the baseline graph backdoor methods. In Section B we provide more details about
the defense strategies. In Section C we provide the time complexity analysis of EUMC. In Section D
we present full experimental results on GCN, GAT, and GraphSAGE. In Section ??, we conduct
additional experiments on robust GNN to evaluate the effectiveness of our method. In Section E
we examine the impacts of trigger pool size. Section we study the effects of trigger size. In
Section G we evaluate the impacts of attachment threshold Ta In Section H we explore the impacts
of Cr. In Section 6 we conduct significant test on our method and strongest baselines. In Section 7
we discuss the limitation and future direction of our work. In Section g impacts of our work.
we discuss the broader
A Details of Compared Methods
The details of the compared methods are described as:
SBA [29]: This method targets backdoor attacks on graph classification by injecting a fixed subgraph trigger into the training graph for poisoned node. The edges of each subgraph are generated using the Erdos-Renyi (ER) model, and the node features are randomly sampled from the training graph, ensuring variability in the features of the injected subgraph.
* GTA [12]: This method addresses backdoor attacks on both graph and node classification. It starts by randomly selecting unlabeled nodes from the clean graph as poison nodes. An adaptive trigger generator is then used to create node-specific subgraphs as triggers. The trigger generator is optimized through a bi-optimization algorithm that incorporates backdoor attack loss.
UGBA [3]
Similar GTA, UGBA focuses backdoor attacks node classification and employs an adaptive trigger generator to generate node-specific triggers. To enhance the unnoticeability of the attack, UGBA introduces clustering algorithm to select representative nodes as poison nodes. This method also explores the use of an unnoticeable loss function increase the similarity between attacked nodes and generated triggers, improving the stealthiness of the backdoor attacks.
DPGBA 14: DPGBA focuses on in-domain (ID) trigger generation for the backdoor attacks on node classification. To generate ID triggers, DPGBA introduce an out-of- distribution (OOD) detector in conjunction with an adversarial learning strategy to generate the attributes of the triggers within distribution. This method further introduces novel modules designed to enhance trigger memorization by the victim model trained on poisoned graph.
B Details of Defense Strategies
The details of defense strategies are described as follows:
Prune: In this strategy, we focus on enhancing the resilience of GNNs to graph backdoor attacks by pruning edges that connect nodes with low cosine similarity. This approach is based on the observation that edges created by backdoor attackers often link nodes with dissimilar features, aiming to manipulate the model's predictions subtly. By pruning such edges, we can potentially disrupt the structure of the trigger inserted by the attacker, making it less effective and thus preserving the integrity of the data representation of graph.
Prune+LD: Building upon the Prune strategy, this approach adds an extra defense against backdoor attacks by addressing the issue of "dirty" label on nodes that may have been compromised by the attacker. In addition to pruning edges between dissimilar nodes, we also discard the labels of these nodes to mitigate the influence of potentially poisoned labels. This dual approach helps in further safeguarding the learning process against manipulation. By removing these labels, the defense mechanism reduces the risk of the model learning from and perpetuating the attacker's modifications, thereby maintaining the performance and trustworthiness of GNNs in the face of adversarial conditions.
20

---

Table 4: Training Time on OGB-arxiv
Metries
GTA
UGBA
DPGBA
EUMC
ASR(None)
68.4
63.7
68.8
83.8
ASR(()))cc)
3.1
69.3
13.0
84.1
ASR(Prune+LD)
3.3
69.4
6.2
84.2
ASR(OD)
28.2
62.6
54.1
83,4
Time
86.4s
98.58
121.48
117.2s
Table 5: Results of backdooring GCN (ASR (%) | Clean Accuracy (%)). reported for clean graph.
Only clean accuracy is
Datasets
Ve Defense
Clean
SBA
CTA
UGBA
DPGBA
EUMC
None
14.3+00
83.7+12
934434
71.0+00
91.24399
63.3+2.1
93.240.3
82.
96.9-0.44
82.0+0.2
Cora
100
Prune
Prune+LD
80.6
80.4
14.340.
14.3+0.
83.5#13
804412
15.6218
15.040.7
80.1115
80622088
88.8139
88.8.18
69.012.
64/4339
89.3:0..2
87.8.1.1
81.1406
82.70066
93.2:20.2
93.0:10.4
81.41066
81.9:00.3
OD
14.4+00
83.0+1.3
69.0+-241
82.0+1.1
88.7423
79.1422
93.4404
83.4+022
95.4-0.3
82.4+0.4
Noue
83.7
33.3:10.0
85.3200.
90.3122
85.2+0.1
96.3210.7
84.7.002
95.3
81.810.1
96.61111
83.7.0.3
Puhmed
150
PrunetLD
Prune
83,1
33.310.0
33.3++0.0
84.1100.3
85. 5
33.510.1
33.4+0.1
84.0110.1
85.1#0.2
95.510.4
07.9:0.5
83.810.11
84.7+0.2
93.2400.1
84.2102
84 1400
95.3+002
95.6.10.3
83.310.33
83.6+0.11
OD
84.7
33.3++0.0
85.3+00.4
93.4+.0.
85.9++0.2
95.5++0.2
84.9+0..1
93.5++0.4
84.6:00.1
97.1-00.1
84.2:-0.2
None
78.2
33.3+20.0
78.5++0.
84.0214.1
78.5+00.0
91821088
78.5+000
87.619999
78 38.0000
96,4:33,3
78.3:20.0
Bitcoin
Prune
33.340.0
78.310.00
38.316.1
78.310.00
85.2.9.11
78.31000
38.0100
92,9-7.11
78.3.00.0
Prun++LD
78.2
33.3::0.0
78.310.0
15.0211..8
78.310.0
79.6.1..3
78.310.0
33.3
78 38.0
97,3-11.7
78.3:10.0
OD
78.3
33.340..0
78.340.0
51.7
78.340.0
6..6.18.3
78.3+0.00
86.24-0.6
78.3+00.0
9..6
78.3-00.0
None
25.0+000
95.920.3
819+58
84,8
93.840.3
84,5202
1+0.8
84.1=0.2
95.9:003
81.9:0.5
Facebook
100
Prune
D.D
79.7
79.9
25.0.10.0
25.0+0.0
85.91022
85.4+0.3
25.4108
25.3+044
84.510.4
84. 84.1
94.2.0.5
918+04
844104
82.9+0.3
76.5.0.2
80. 1+0.2
834++033
83610.4
96.3-10.1
96.2-0044
81.8+0.6
82.6.10.4
OD
84.1
25.040.0
85.21..2
86.2433
84.410.4
93.110.5
84.710.2
93.140.2
84.41..1
94.5:0.3
82.910.4
None
46.1
14.3+00
998:0.1 4
41 8
21,4006
41 41:0004
56, 56.33
44.0:0.1
43.8:00.3
Hickr
300
Prune
D
46.1
15.5
14.340.0
14.310.0
4
42.010.8
14.940.5
15.5.0.77
43.8+0..4
40.510.11
21.9408
18.6.10.7
41.120.5
40.40..1
71.5.0..6
18.4
44.3+022
13.511..2
99,510.2
98.5-10.7
43.7+10.3
43.910.2
OD
46.2
14.3+0.
42.5+0.3
28.++0.1
41.0+0.1
17,800
42.3+0.2
85.7408
43.6+0.11
99.4-00.5
43.1-+0.2
Noue
64.1
2.5.1..0
11..4
68.411.
65.2.0.33
74
64.510.6
73.710.9
64.810.1
78.3-10.6
65.3.10.3
OGi--arxiv
Prune
Prune+LD
61.2
2.540.0
2.510.0
25.2
61.52.0.2
3440.4
333006
64.740.3
61.51044
710+111
70.8109
64910..5
61.520..6
10.241.1
16.910.5
64..0..1
61.910.1
79.0:10.9
78.6200.
65.940.2
65.110.4
0D
64.5
2,5+0.0
64.5++0.1
35.7+1.7
63.3+0.2
66.3-15
64.9+02
74.1+0.7
64.6+02
77.9-0.5
65.0+0.4
In this strategy, we focus on enhancing the resilience of GNNs to graph backdoor attacks by removing OOD nodes in the graph. This approach is based on the observation that the features from triggers often have different node feature distribution from the clean data. Therefore, the OOD detector (i.e., DOMINANT (40)) trained on the poisoned graph can identify the trigger by the reconstruction loss. By removing the nodes with high reconstruction losses, the feature distribution of the nodes can be distributed in domain, preserving the integrity of the data representation of graph.
OD:
C Time Complexity Analysis
During the bi-level optimization phase, the computation cost of each outter iteration consist of updat- ing of surrogate GCN model in inner iterations and optimizing multi-category subgraph trigger pool. Let h denote the embedding dimension. The cost for updating the surrogate model O(Nhd))) where d is the average degree of nodes, N is the number of inner iterations for the surrogate model, and |>] is the size of training nodes and poisoned nodes. For the optimization of multi-category subgraph trigger pool, the cost for optimizing La is (ldd(VVel) where |irl is the size of unlabeled nodes. And the cost for optimizing Cn, is O(h(Vp]= * Val), where [Vp] is the number of poisoned nodes and [Va] is the number of attached nodes. Note that, during optimizing La we randomly as-
signing a target category Me to poisoned nodes, making the time complex reduced from O(K hdd Vpl) to O(hd) O(hdVyrl) Vy where K is the number of target categories. Since |pl < \/). Vpl * Va.l < [V]
and Nol = [V], the overall time complexity for each outter iteration is O(NN + 1)hdlV)), which is
similar to time complextity of UGBA [33. In the backdoor attack phase, the cost of selecting and
attaching trigger to the target node is (hrppoo)) Our time complexity analysis proves that EUMC has great potential in large-scale applications.
In Table we also report the overall training time EUMC, DPGBA, UGBA and GTA on OGB-arixy dataset. All models are trained with 200 epochs A100 GPU with 80G memory. Experimental
21

---

Table 6: Results of backdooring GAT (ASR (%) reported for clean graph.
Clean Accuracy (%))
Only clean accuracy is
Datasets
Vp
Defense
Clean
SBA
GTA
UGBA
DPGBA
EUMC
Nome
84.6
14.3=0.0
84
70.7:5.1
81.24.11
66.1199
77.9=2.1
81.82700
81.622277
97.7=1.0
82.4:0.2
Cora
100
Prune
P.inesL.D
81.3
83.9
1..3-0.0
14.3-0.0
81.5++13
33.9.1.3
14.3.0.7
15.0+0.9
81.741.0
806+18
74.416.1
79.6+8.7
7..
75,9+2.7
72.2+3.9
80.1
1..
80.9-0.2
9.72
94.0-0.6
81.2+0033
81.940.11
OD
14.3=0.0
61.0:1466
79.822.9
82.3=0.2
97.2:116
82.0=0.8
None
85.1
33.1=0.0|
84.0....3
87.1430
83.7....2
91.41..6
83.9.00.2
90.7..0.9
84.5.0.11
96.6-100
83.0=00.2
Pubmed
150
Prune+LD
Prine
83.1
33.3=0.0
33,3-0.0
83.7+00.
82.9:0.5
33.420.1
31.4+0.1
83.4004
83.4+0.3
9.7
83.240.2
83.5+0.1
90.7+006
83,7=0.2
84.2+0.1
94.7-2.4
82.2:0.5
828--04
OD
84.9
33.3=0.0
84.4:001
87.8+1.6
84.3+002
90.120022
84,8:00.2
89.1#0.6
84,400.2
96.1-6.
83.9=0.2
Nome
78.3
33,3-0.0
78.3+00.0
60.4+1004
78.2+00.1
49. 5--511111 1
78.3++0.0
72.0+22.1
78.3=0.0
76.2-8.6
78.3=000
Bitcoin
300
Prune
78.2
33.3-0.0
78.3+000
39.34774
78.3+0.0
53.2+18.00
78.3+0.0
33.3 33.3+0.0
78.3-0.0
72.9 9.3
78.3-00.0
Prane+LD
78.2
33.3=0.0
78.3=00.0
42,8=12,7
78.5+0.0
13.9
78.3+0000
33.
78.1=0.0
63.2-2,4
78.3=00.0
OD
78.3
33.
78.3200.0
66.0.10.4
78.310.0
68.31.38.1
78.3
58.7
78.3=00.0
68.4.0.5
78.3:00.0
Nome
79.5
25.0-0.0
N7.1+003
64.2422
863400
75.5+3.11
26.4+0.3
6-+66488
16.1-0.2
92.3-3300
83.4-0.2
Pacehook
100
Prune
Prune+LD
78.3
78.7
25.0=0.0
25.0=00.0
85.9110.2
86.0::02
25.7+00.7
25.3.10.4
85.8+0.3
85.7.0..2
89.31:38
$2.19
$5.7.00.2
85.1
72.8::2.4
70.7::1.9
83.5
85.2:00.2
91,9-2.8
92.5-22.8
81.2:20.1
81.920.11
OD
25.0-0.0
86.0+0.1
69.1+6.6
86.400.4
81.8+0.4
86.2+0.3
38.5+4.3
86.2-005
95.9-40
83.6-004
Noac
16.7
14.3=0.0|
45.62:044
19.5
10.520.33
23.7:00.9
13.1::141
19.7955.9
44.6::0.1
78.1=9.1
44.7220.3
Flickr
300
Prune+LD
Prune
44.9
42.4
14.3=0.0
14.3=0.0
40.4::0.0
45.4110.8
14.210.4
14.5:00.5
40.5:1.33
45.110.4
21.1118
19.94.2.3
42.1
42.5
67.6:-3.11
15.3422
44.810.1
44.1=00.2
7..
76.5 9.0
43.9=:0.4
43.2:10.3
46.4
14.3-0.0
40.2:00.0
25.745.2
40.2+0.1
17.6+04
43.4+-0.1
68.4+6.0
43.5-0.2
75.2-
44.4-0.9
Nosc
65.6
2.5=0.0
66.1:001 1
68.42199
65.5
13
65.110.2
59.419.88
64.6=00.1
98.6:0.1
64.:00111
OGB-arxiv 800
Prune
Pranesl.D
64.4
65.6
2.5
2.5-0.0
64.1
64.9+0.3
2.910.5
34+1.0
6.4+0.2
65.910.1
82.710.5
83
65.6+022
65.510.1
2,8+0.1
9.0:10.6
65.2-0.2
64.7
99.2-0.3
98.8-0.1
64.3-0.3
65.1-002
OD
65.4
2.5=0.0
64.2:10.1
24.2::2.2
64.5+0.3
S3.520.5
63.0:2044
13.2#7.0
6-.6:20.1
98.3
64.4:0.4
Table 7: Results of backdooring GraphSAGE (ASR (%) is reported for clean graph.
Clean Accuracy (%)
Only clean accuracy
Datasets
V>
Defense
Clean
SBA
GTA
UGBA
DPGBA
EUMC
Nome
80.5
14.3=0.0|
1.
99.0-008
80.+008
92.1+115
7..1=1.7
86.91.3
83.7=001
97.5=1.8
8.28-0.2
Cora
100
Prune
PruneeLD
79.6
78.4
14.3=0.0
14.3=0.0
79.3:1.0
76.74222
15.11088
15.2
7..8
78.411.5
91.31:10
87.61:22
75.7=110
71.5
83.6:10.3
80.4
83.8:0.6
80.1
93,2:008
93.6:0.2
80.4:0.1
82.9:0.3
OD
83.9
14.3-0.0
81.6+0.3
65.0+22.1
809+3.8
92.3+0.7
80.5+34
86.+00.
83.3+1.9
97.7
81.2-0.6
None
84.1
33.
86.1.10.3
82.8.12.7
85.610.1
79.11:.1
35.620.2
88.510.3
86.620.2
96.0:0.1
84.920.3
Pubmed
150
Prune
ProneeLD
85.0
33.3-0.0
33.3-0.0
83.9::0.2
86.6220.1 1
33.4-H0.1
33.4+0.0
86.24..2
85.24:2.2
84.0+-0.3
85.5::0.2
84.8:-0.3
85.7=001
86.4:0.2
94.5-0.3
94.9 0.1
84.7-0.3
85.3-10.5
OD
85.1
33.3
86.2+0.1
84.5+559
86.10..3
83.5+1
86.5+0.2
85.8+0.2
86.4-0.3
95.5
85.6-0.1
Nose
78.3
33.3-0.0
78.3+-0.0
84.3+12.7
78.3+0.0
88.0+17.88
78.3++0.0
80.8+7.0
78.1=00.0
99.3- 0.1
78.3-00.0
Bitcoin
300
Prune
78.3
33.
78.31:0.0
35.2413.9
78.31...0
81.619.6
78.3::0.0
33.31:0.0
78.3:000
99.1-0.1
78.3::0.0
PronesI.D
78.3
33.3-0.0
78.3++0.0
40.1+1105
78.5+0.0
10.6+12.
78.1+00.
33, 33.00
78.1=0.0
99.2-601
78.3-0.0
OD
78.3
33.3=0.0
78.3:20.0
14.7:1114
78.3+0.0
33.310.0
78.3:20.0
88.0200.2
78.3=0.0
99.3
78.3:00.0
None
86.0
25.0=0.0
86.8+0.2
81.945.8
86.640.3
85.6+-08
86.7+-0.3
85.2+00.
87.1=0.2
86.9
0.3
86.0=0033
Facebook
100
Prone
Prune+LD
85.1
85.9
25.0=0.0
25.0=0.0
86.7:0044
86.6110.2
25.3-+0.5
25.3.10.3
86.6+022
86.210.22
85.8+111 .1
77.910.8
85.8110.1
86.3--0.2
70.0=00.1
73.3.10.2
96.920.1
8699=0.2
87.0=0.3
87.3=0.4
86.0=0.2
16.02
OD
85.6
25.0=000
86.8:002
76.3:1466
86.110.4
72.4
86.9:10.3
84.7::0.2
87.1
07.
86.4:005
Noac
45.0
14.3=0.0|
47.6:20.3
99.7:0022
45.4+0.6
28.9209
46.1::0.5
$4.3+0.3
47.0=0022
94.5=1.0
44.9:00.4
Flickr
300
Prune
Prune+LD
45.0
45.0
14.3=0.0
14.3=0.0
41.3:00.4
46.010.1
148:00.2
15.110.4
43.611.22
43.710.2
34.71.2.
28 23..3
45.3200.5
45.3110.3
66. 66.91.0.7
20.912.7
45.8:0.5
46.7.0.4
95.6:1.2
95.0=114
44.6.10.5
45.6:20.2
14.3=0.0
47.110.3
24.8.5..5
44.411.1
6
46.5110.3
$5.0
46.2-10.3
94.3-2211
46.4.0..1
Nose
64.8
2.500.0
66.5=20.4
68.4
66.16
43.4+2.22 2
64.91008
73.3+0.1
63.4=0.2
7..8:0.6
65 (3.7:20.2
aGB-arxiv 800
PrunerLD
Prune
63.2
65.0
2.5
2.5
64.5:-0.1
65.1100.4
2.910.5
3.340.6
64.8:0.4
64.710.5
53.34:1
54.310.5
65.0=-0.9
65.3100.5
13.110.8
5.7+0.6
65.1=00.
65.5.0.1
7..9=0.4
74.3-0.3
65.6=0.2
66.1-0.3
(D)
64.9
2.500.0
64.7=00.2
24.6+009
63.7+0.5
18.1
63.8:002
75.1-902
63.9=0.1
7.9
65.8-0.6
22

---

90
90
ASR(%)
60
ASRC
60
ASR(%)
Prune
30
Prune
None
Prune
None
Prune +
Prune LD
20
40
60
80
100
0.0
0.2
0.4
0.6
0.8
1.0
Prompt Size
Trigger Size
Attachment Threshold
(a) Impact of prompt pool size
(b) Impact of trigger size
(c) Impact of attachment threshold
Figure 4: The comparison of different (a) trigger pool size, (b) trigger size, and (c) attachment threshold Ta on Flickr dataset.
100
80
60
40
20
50
0
30
0.2
10
4
0.4
0.6
5
1.0
0
Figure The comparison of different a and Ty. on Flickr dataset.
results show that EUMC achieves the best ASR among different defense strategies with similar training times as other methods.
D Detailed Experiments on GNNs
In Tables 5 and 7 we present detailed experimental results, including the average and standard deviation ASR and clean accuracy, on various GNN architectures, namely GCN [16), GAT (23), and GraphSAGu (26). From these tables, we can find that EUMC method achieves state-of-the-arr results on all datasets except for Pubmed, demonstrating its robustness and generalization ability across different GNN structures for multi-category graph backdoor attacks. The comparable perfor- mance of EUMC to UGBA on Pubmed likely stems from the dataset's small size and limited number of categories (only three), which constrain the effectiveness of attacks. Moreover, when analyzing performance variations across different GNN architectures on the same dataset, our model shows balanced performance, indicative of strong generalization ability of our graph backdoor attack method. Specifically, on datasets like Flickr and OOGB-rrin although there is a noticeable perfor- mance difference between GAT and GCN, methods. This consistency highlights the unique advantages of EUMC in managing multi-category graph backdoor attacks, emphasizing its potential for widespread application across diverse settings.
model maintains better balance compared to other
In these tables, we also notice that the performance of SBA is relative poor due two reasons, 1) the smaller poison node set: 2) the multi-category graph backdoor attack setting. Specifically, in UGBA [33 DPGBA [14, SBA has already performed poorly in single-category graph backdoor attack on node classification when the size of poison node set gets small. Moreover, our work focuses on more challenging multi-category graph backdoor attack, where the different triggers are required to capture different category- feature. Therefore, the performance of SBA get further reduced.
23

---

E Impacts of Trigger Pool Size
The subgraph triggers pool offers various attack patterns for the backdoor attack. To examine the impact of these patterns, we vary the trigger pool size for each category as {20, 40, 60, 80, 100) and plot the average ASR for GCN, GAT, and GraphSAGE with different defense strategies in Figure 4 (a). From this figure, we observe that as the trigger pool size increases from 20 to 100, the performance of EUMC method first increases, peaking at a pool size of 40, and then decreases. A smaller trigger pool size limits the attack patterns available for each target category, which undermines the performance of our model. Conversely, a larger trigger pool size can include subgraph triggers that are not well-optimized, which also affects the performance of the graph backdoor attack.
F Impacts of Trigger Size
To examine the impact of different trigger sizes, we conduct experiments to explore the attack performance of method by attaching varying numbers of nodes triggers for poisoned node. Specifically, we vary the trigger size in increments (3, 4, 5, 6, 7), and plot the average ASR for GCN, GAT, and GraphSAGE the experimental results, we observe that as trigger size increases, the attack success rate initially increases and then stabilizes. Given that including more nodes in each trigger could potentially expose our attack, we opt to construct each trigger with five nodes to mislead the backdoored model.
Flickr with different defense strategies in Figure (b). From
G Impacts of Attachment Threshold Ta
The attachment threshold Ta strikes a balance between attack intensity and unnoticeability. To investigate the effects of Ta, we adjust its values in increments O, 0.2, 0.4, 0.6, 0.8 and plot the average Attack Success Rate (ASR) GCN, GAT, and GraphSAGE on Flickr with various defense strategies in Figure The experimental results reveal that as Ta increases, the average ASR initially rises and then declines. When To is set low, more nodes from the subgraph trigger can be attached to the attacked node, potentially harming the generative capability and making it more detectable by defense algorithms. Conversely, as Ta increases, fewer nodes from the subgraph trigger are attached to the attacked node, which may limit the effectiveness of graph backdoor attack.
H Impacts of Similarity Loss Lt
To examine the effect of similarity between subgraph triggers and attacked nodes, we investigate how the hyper-parameters a and 7z influence the performance of EUMC. Here, a controls the weight of Lr. and Tı determines the threshold for similarity scores used in Lr. We vary a values as (0, 5, 10, 20. 30, 50) and TL from (0, 0.2, 0.4, 0.6, 0.8, ). and plot the average ASR for GCN, GAT, and GraphSAGE on Flickr with different defense strategies in Figure 5S] For both and TL, the ASR initially increases and then decreases, indicating that setting the similarity between trigger nodes and attacked nodes, based on the node similarity distribution of the original graph, can make the attack unnoticeable. However, overly emphasizing this similarity can also compromise the effectiveness of the subgraph triggers.
24


Reviews:
[{"review_id": "ReGtkSYDeY", "reviewer": "Reviewer_StDL", "summary": "This paper addresses the challenge of multi-category graph backdoor attacks on node classification tasks, where existing methods (e.g., GTA, UGBA) fail to scale effectively as the number of target categories increases. The authors propose EUMC, a novel framework that leverages subgraph triggers sampled from the original graph to construct a Multi-Category Subgraph Triggers Pool (MC-STP). Experiments across six datasets (Cora, Pubmed, Bitcoin, Facebook, Flickr, OGB-arxiv) and three GNN architectures (GCN, GAT, GraphSAGE) show EUMC outperforms baselines in Attack Success Rate (ASR) under defenses (Prune, Prune+LD, OD), particularly for large category sets.", "questions": "- Experiments fix trigger size at 5 nodes (Sec 5.1). Why is this optimal? Does performance plateau for larger triggers (Fig 4b) due to detectability or GNN aggregation limits?\n- Sampling subgraphs via BFS (Sec 4.1) may not scale to billion-edge graphs. Can MC-STP initialization be accelerated?\n- Why does ASR decrease as categories grow (Table 1)? Is this due to inter-category trigger interference or reduced subgraph uniqueness?", "limitations": "Yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The manuscript is well-structured with clear figures (e.g., Fig 1, 2) and Algorithm 1. Appendix details (e.g., time complexity, hyperparameters) aid reproducibility.\n- Solves a critical gap in multi-category backdoor attacks, enabling precise control over diverse target classes—a need for real-world adversarial scenarios.\n\nWeaknesses:\n- Limited exploration of transferability to non-surrogate models. Experiments on robust GNNs (GNNGuard, RobustGCN) lack comparison to baselines.\n- ASR still declines with increasing categories (e.g., Table 1, Flickr), though less severely than baselines. No theoretical analysis of this trend.", "was_revised": true, "final_justification": "Thank the authors for their responses. My questions are largely resolved, and I will keep my rating as borderline acceptance.", "rebuttal": "We appreciate the reviewer's recognition of our framework addressing the multi-category graph backdoor attack challenge, its effectiveness shown in experiments, the well-structured manuscript, and its role in filling a critical gap and we thank the reviewer for the constructive comments. Regarding the concerns of the reviewer StDL, we provide the following responses. We hope our responses address the concerns raised, and we welcome active discussions with reviewers. \n\n> **W1. Limited exploration of transferability to non-surrogate models. Experiments on robust GNNs (GNNGuard, RobustGCN) lack comparison to baselines.**\n\n* In our experiments, only the GCN is exploited as the surrogate model to optimize our multi-category trigger pool. Therefore, the experimental results on GAT, GraphSage, GraphTransformer, GNNGuard and RobustGCN can be regarded as the exploration of transferability. \n  On these above non-surrogate models, our model shows great performance in terms of attack success rate(ASR).\n* **In Appendix E, Tab. 8 and 9**, we compare the performance of all baselines on GNNGuard and RobustGCN. Compared to DPGBA, our method outperforms by **12.3%** and **3.4%** on GNNGuard and RobustGCN respectively. Compared to UGBA, the improvements are **26.7%** and **13.9%** respectively, demonstrating our method's stealthiness and effectiveness in multi-class attack scenarios.\n\n> **W2 & Q3. ASR still declines with increasing categories (e.g., Table 1, Flickr), though less severely than baselines. No theoretical analysis of this trend. Why does ASR decrease as categories grow (Table 1)? Is this due to inter-category trigger interference or reduced subgraph uniqueness?**\n\nWe appreciate the reviewer's constructive comment. The reasons that lead the ASR still declines with increasing categories can be summarized as:\n\n* **Classifier performance limitations**: As shown in **Tab. 2**, the clean accuracy of GNN classifiers decreases significantly with the increase in the number of categories. Compared to the 3-class Pubmed dataset with an accuracy of **84%**, the multi-class Flickr and Arxiv datasets only achieve **44%** and **65%** accuracy, respectively. Since GNNs themselves struggle to distinguish over half of the nodes on Flickr, **the class-specific information learned by MC-STP is limited**, which in turn leads to a decline in attack accuracy.\n* **Differences in dataset characteristics**:  For multi-class graph datasets, each class exhibits distinct structural and information patterns, and even nodes within the same class may have variations. This leads to **potential conflicts in learning class-specific triggers for the same class**. Additionally, triggers designed for the same class may inadvertently **learn overlapping information** due to the inherent variability among nodes in that class, increasing the difficulty of learning highly specific and effective triggers.\n\n> **Q1. Experiments fix trigger size at 5 nodes. Why is this optimal? Does performance plateau for larger triggers due to detectability or GNN aggregation limits?**\n\n* **In Appendix Fig. 4b**, we conduct an ablation study on the number of trigger nodes. The performance improves as the number of nodes increases, but it plateaus when exceeding 5 nodes while maintaining overall strong performance. Thus, we uniformly set the trigger size to 5 nodes.\n* We attribute the performance plateau after 5 nodes to **two reasons**:\n  - First, it is limited by **graph information propagation**. If the trigger is too large, the GNN’s information propagation cannot cover all node information, resulting in the waste of some node information.\n  - Second, it is related to **the degree distribution of the original data**. As observed **in Table R1**, the degree distribution of most datasets is mostly below 7. Thus, the maximum degree of a node in a five-node trigger is 5 under fully-connection setting (4 within the triiger plus 1 for attacked node). Moreover, when the number of nodes in the trigger is too large, some nodes within the trigger may not conform to the degree distribution of the original graph, which may **increase detectability** and result in **being pruned**. \n\n**Table R1**: The statistics on the degree of different graph dataset.\n\n| dataset   | nodes   | edge      | degree |\n| --------- | ------- | --------- | ------ |\n| Cora      | 2,708   | 5,429     | 3.9    |\n| Pubmed    | 19,717  | 44,338    | 4.5    |\n| Flickr    | 89,250  | 899,756   | 10.1   |\n| OGB-arxiv | 169,343 | 1,166,243 | 6.9    |\n\n> **Q2. Sampling subgraphs via BFS may not scale to billion-edge graphs. Can MC-STP initialization be accelerated?**\n\nWe thank the reviewer for the suggestion to discuss the efficiency of MC-STP. We provide the following discussion:\n\n* First, subgraph sampling via BFS is a **pre-processing step that only needs to be performed once**. In subsequent processes (trigger selection, trigger optimization and attacking), we can reuse the previously sampled results without re-conducting BFS.   \n\n* Second, as mentioned in **Section 4.1**, we initially randomly select several nodes from the unlabeled graph,$V_U$, to serve as central nodes. These central nodes account for **a small proportion** of the original graph, and we do not sample all possible subgraphs. Instead, we set thresholds for the total number of sampled subgraphs and the number of subgraphs sampled per central node. **This ensures high efficiency even on billion-edge graphs**. \n\n* Third, we analyzed **the time complexity of the MC-STP Initialization**. Let $h$ denote the embedding dimension, $n$ represent the number of nodes in each trigger, $K$ be the number of target categories, and $|\\mathcal{N}_S|$ be the number of subgraphs to extract. The cost of constructing the MC-STP is approximately $O(nh|\\mathcal{N}_S| + Kh|\\mathcal{N}_S| + Kh)$, which covers extracting $|\\mathcal{N}_S|$ subgraphs with $n$ nodes each and clustering them into $K$ clusters. Since subgraph and feature extraction is the dominant cost, the overall time complexity is approximately $O(Kh|\\mathcal{N}_S|)$. Therefore, the complexity of the MC-STP initialization is proportional to the number of sampled subgraphs. **Furthermore, subsequent experiments and analyses demonstrate that MC-STP initialization is not time-consuming.**\n\n* For example, the OGB-arxiv dataset has 169,343 nodes and 1,166,243 edges. **In the pre-processing step,** we selected 4000 central nodes, and each central node was used to sample 10 subgraphs, resulting in a total of **40,000 sampled subgraphs**. The number of nodes used accounts for **2.3%** in the original graph. After clustering, we obtained MC-STP containing 800 triggers, so APS only needs to be calculated within these 800 triggers. **In the training step**, we only used **2.7% nodes with labels**. These proportions are very small, so they do not incur significant computational costs. \n\n* We have also conducted **efficiency tests on multiple datasets** in **Table R2**, demonstrating that subgraph sampling does not incur significant computational costs.\n\n**Table R2**: The time cost of construction MC-STP.\n\n| dataset   | sample central nodes | sample subgraph | time cost(s) |\n| --------- | -------------------- | --------------- | ------------ |\n| Cora      | 700                  | 7,000            | 78.6         |\n| Pubmed    | 1,200                 | 12,000           | 114.7        |\n| Bitcoin   | 1,500                 | 15,000           | 138.2        |\n| Facebook  | 1,600                 | 16,000           | 156.8        |\n| Flickr    | 2,100                 | 21,000           | 231.3        |\n| OGB-arxiv | 4,000                | 40,000          | 423.7        |"}, {"review_id": "wdcFgJ1cNu", "reviewer": "Reviewer_yDtx", "summary": "This paper proposes a novel multi-class graph backdoor attack method by constructing a multi-class subgraph trigger pool and adopting a \"select then attach\" strategy to connect appropriate triggers to the target nodes, ensuring these modifications remain inconspicuous. Experimental results demonstrate high attack success rates across various classification scenarios and showcase the effectiveness and stealthiness of the proposed method on multiple real-world datasets. Additionally, the paper discusses potential future research directions, such as exploring scalable trigger generation strategies and defense mechanisms.", "questions": "1. Detailed Steps for Trigger Selection Algorithm: It is expected that the authors provide more detailed explanations of the specific algorithm steps for selecting particular triggers. Especially in multi-class attack scenarios, how to ensure the effectiveness and stealthiness of the triggers?\n2. Effectiveness of Defense Strategies in Practical Applications: In practical application scenarios, how effective are the proposed defense strategies (e.g., Prune, Prune+LD, and OD)? Are there plans to test these strategies on larger or more complex datasets?", "limitations": "1. Some experimental details (e.g., specific algorithm steps, dependency configurations) may require more explanation to allow other researchers to fully reproduce the results.\n2. Some key technical details (e.g., how specific triggers are selected in the algorithm steps) may need more elaboration and examples to help readers better understand the implementation process.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\nQuality: The study designs an innovative multi-class graph backdoor attack method and validates its effectiveness through extensive experiments.\nClarity: The paper is well-structured with detailed method descriptions that are easy to understand and reproduce.\nSignificance: Proposes new attack methods, providing an important empirical foundation for security research in Graph Neural Networks (GNNs).\nOriginality: This is the first attempt to construct a trigger pool suitable for multiple target classes, showcasing strong innovation.\nWeaknesses:\n1. Insufficient experimental details: Some experimental details (e.g., specific algorithm steps, dependency configurations) may require more explanation to allow other researchers to fully reproduce the results.\n2. Inadequate explanation of technical details: Although the overall structure is clear, some key technical details (e.g., how specific triggers are selected in the algorithm steps) may need more elaboration and examples to help readers better understand the implementation process.\n3. Although the experimental results are convincing, the impact in practical application scenarios requires further exploration.\n4. Some of the defense strategies adopted in this study draw on pre-existing techniques, which indicates a lack of thorough independent innovation.", "was_revised": true, "final_justification": "Thanks for the authors' detailed clarification, which has effectively addressed the key points of concern raised earlier. I have increased my rating.", "rebuttal": "We appreciate the reviewer's recognition of our novel method, its effectiveness shown in experiments, the paper's clarity, significance for GNN security, and strong originality and we thank the reviewer for the constructive comments. Regarding the concerns of the reviewer yDtx, we provide the following responses. We hope our responses address the concerns raised, and we welcome active discussions with reviewers. \n\n> **W1 & W2 & Q1. Details about algorithm steps, dependency configurations and how to ensure the effectiveness and stealthiness of the triggers.**\n\nWe appreciate the reviewer for the constructive comment. We have detailed our experiments and algorithm in the revised version. We provide the discussion as follows:  \n\n* **Dependency configurations**: We have specified the hyperparameter settings in **Section 5.1 Implementation Details**. Additionally, we will provide more detailed parameter explanations and experimental environment configurations in the open-source code repository.   \n* **Algorithm steps**: We further elaborate on the steps as follows:   \n  *  **Construction of MC-STP**: \n     1.  As mentioned in **Section 4.1**, we initially randomly select several nodes from the unlabeled graph, $V_U$, to serve as central nodes. These central nodes account for a small proportion of the original graph, and we do not sample all possible subgraphs. Instead, we set thresholds for the total number of sampled subgraphs and the number of subgraphs sampled per central node. \n     2.  All obtained subgraphs are clustered to generate  $V_P$ subgraphs, which are used as the initialization of MC-STP. \n     3.  We assign target attack labels to each trigger based on how their effect on the prediction of attached nodes. In detail, we use APS to determine the target attack label of the trigger. (a) A classifier is used to predict the probability distributions of node labels **before and after trigger injection**, and the difference between these distributions is calculated. (b) By summing and averaging the label probability shifts across multiple nodes, we obtain **an APS vector**, which **represents the extent of the trigger’s impact on all classes**. (c) Finally, we obtain MC-STP structured as {label1: [t1, t2...], label2: [t1, t2...], ...}.\n     4.  **For example**, using the OGB-arxiv dataset (with 169,343 nodes and 1,166,243 edges), we first select 4000 central nodes, and each central node sampled **10 subgraphs**, resulting in a total of **40,000 sampled subgraphs**. After **k-means clustering**, we obtained an MC-STP containing 800 triggers. We then assigned **target attack labels** to the 800 triggers using Eq. (1) in Section 4.1 based on their Attachment Probability Shift(**APS**).  \n         A trigger $t$ is attached to $N$ nodes. A GNN classifier then calculates the probability distributions $p_{bef}^{t, i}$ and $p_{aft}^{t, i}$ before and after the trigger $t$ is injected into the nodes. Here, $p_{bef}^{t, i}, p_{aft}^{t, i} \\in \\mathbb{R}^{N_{cls}}$ represents the predicted probabilities for each class. At this point, we compute $\\text{APS}^{t} = \\frac{1}{N} \\sum_{i=1}^{N}|p_{bef}^{t, i} - p_{aft}^{t, i}|$ to obtain the $\\text{APS}^{t} \\in \\mathbb{R}^{N_{cls}}$. The $\\text{APS}^{t}$ indicates the impact of the trigger $t$ on each class, and we select the category with the greatest influence as the **target attack label** $y_t=\\arg\\max(\\text{APS}^{t})$ for trigger $t$, indicating that $t$ has the most significant impact on category $y_t $ and can be more stealthily disguised as nodes of category $y_t $.\n  *  **Trigger selection and attachment**:\n     *   In Section 4.2, we detailed the trigger selection process. For an attacked node $ v_i \\in V_P $, we first calculate the similarity between $v_i $ and all candidate triggers of the target class using Eq. (2), then select the trigger with the highest similarity for injection. \n     *   **For example**, given 20 candidate 5-node triggers, we compute the **cosine similarity** between the attacked node $v_i $ and each of the 5 nodes in each trigger, sum these similarities to generate a score in Eq. (2), and finally select the trigger with the highest score for injection. After choosing the suitable trigger $t$ for injection, we will continue to consider the edges connected between the attacked node $v_i$ and nodes of trigger $t$. To ensure attack effectiveness and stealthiness, we only connect nodes within the trigger $t$ to the attacked node $v_i $ if their **cosine similarity exceeds a predefined threshold** $\\tau_a$. \n  *  **Optimization**: To **guarantee the effectiveness and stealthiness of the triggers**, we adopt **a bi-level optimization** approach (Eq. (3), (4), and (5) in Section 4.3). **The inner loop** optimizes the accuracy of the surrogate model on both clean nodes and attacked nodes via Eq. (3). **The outer loop** ensures attack effectiveness and stealthiness, constrained by the attack effectiveness objective (Eq. (4)) and stealthiness objective (Eq. (5)). Our method achieves state-of-the-art results across multiple GNN models and defense strategies, demonstrating the effectiveness and stealthiness of MC-STP in multi-class attack scenarios.\n\n> **W3. The impact in practical application scenarios requires further exploration.**\n\nWe appreciate the reviewer for the constructive comment. We have detailed our **case study** about practical application scenarios in the revised version. We provide the discussion as follows:\n\n**Scenario:** Node classification on Facebook identifies account types as $C_1$ (politicians), $C_2$ (governmental organizations), $C_3$ (television shows), and $C_4$ (companies), enabling differentiated governance (e.g., preferential content distribution for politicians, restricted promotions for non-companies).  \n\n* **Attack Goals**: Attackers aim for **multi-category precise tampering**:    \n  * Disguise uncertified $C_4$ (companies) as $C_1$ (politicians) to bypass promotion restrictions and gain exposure.\n  * Disguise low-engagement $C_3$ (TV shows) as $C_2$ (governmental organizations) to exploit public trust for misleading content.\n  * Avoid detection by platform defenses (e.g., topology anomaly checks, certification validation).   \n* **Practical Role of MC-STP**:  \n  * Traditional single-category methods (e.g., GTA) fail to target $C_1$ and $C_2$ simultaneously, with over-generic triggers easily detected.\n  * MC-STP samples category-adaptive triggers: mimicking politician accounts’ dense public interaction topology for $C_1$, and governmental organizations’ official association structures for $C_2$.\n  * The \"select-then-attach\" strategy ensures triggers align with targets’ original edge structures (e.g., integrating politician-style interactions into company node), meeting real-world stealth needs.\n\n> **W4 &Q2. Some of the defense strategies adopted in this study draw on pre-existing techniques, which indicates a lack of thorough independent innovation. In practical application scenarios, how effective are the proposed defense strategies (e.g., Prune, Prune+LD, and OD)? Are there plans to test these strategies on larger or more complex datasets?**\n\n* **Our study focuses on achieving stealthy and efficient backdoor attacks in multi-category scenarios.** The use of pre-existing popular defense strategies is solely to demonstrate the effectiveness and stealth of our attack. While defense research is currently outside the scope of our study, **we will consider exploring ways to further enhance defense mechanisms in the future.**\n\n* Following [1] and [2], we adopt popular graph domain defense strategies such as Prune, Prune+LD, and OD, which maintain the cleanliness of graph data by pruning graph features and structures. To verify the effectiveness of our method, we statistically analyzed the pruning ratio of nodes in triggers and triggers by these defense strategies, demonstrating the effectiveness and stealth of our approach.\n\n* Among the tested datasets, OGB-arxiv is a large citation network containing 169,343 nodes, 1,166,243 edges, and 40 categories. Results in **Table R1** also show that our model effectively evades defenses in 40-class attacks. **We appreciate your suggestion and will further test our method on other more larger and complex datasets in future work.**\n\n**Table R1**: The effectiveness of our method post-defense. 2.7%(0.2%) represents (node prune|trigger prune)\n\n* | dataset   | Prune      | Prune+LD   | OD         |\n  | --------- | ---------- | ---------- | ---------- |\n  | Cora      | 2.7%(0.2%) | 2.3%(0.2%) | 1.7%(0.0%) |\n  | Pubmed    | 1.5%(0.1%) | 1.7%(0.3%) | 1.5%(0.2%) |\n  | Bitcoin   | 0.7%(0.0%) | 1.2%(0.1%) | 1.0%(0.1%) |\n  | Facebook  | 4.3%(0.8%) | 3.9%(0.7%) | 2.7%(0.4%) |\n  | Flickr    | 3.6%(0.4%) | 3.2%(0.4%) | 1.8%(0.2%) |\n  | OGB-arxiv | 3.2%(0.6%) | 2.8%(0.3%) | 2.8%(0.4%) |\n\nReference:\n\n[1] Zhang, Zhiwei, et al. \"Rethinking Graph Backdoor Attacks: A Distribution-Preserving Perspective\" Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (2024).\n\n[2] Ding, Yuanhao, et al. \"SPEAR: A Structure-Preserving Manipulation Method for Graph Backdoor Attacks\" Proceedings of the ACM Web Conference (2025)."}, {"review_id": "YlCUay3Yjm", "reviewer": "Reviewer_WCrP", "summary": "This paper introduces a method for multi-category graph backdoor attacks on node classification with GNNs, a challenging scenario where different triggers lead to misclassification in multiple targeted categories. The proposed method, called EUMC, replaces adaptive trigger generators with a pool of category-aware subgraph triggers sampled from the graph itself. Trigger assignment is based on attachment probability shifts to determine which subgraph is most effective for each category. The approach also introduces a \"select then attach\" strategy to maximize the stealthiness of triggers by optimizing trigger-node similarity. The method is empirically validated across six real-world node classification datasets and several defense strategies, showing improved attack success with negligible impact on clean node accuracy in comparison with existing single-category and multi-category backdoor attacks.", "questions": "1. Could the authors provide insight into the limits of the pool-based approach—what happens as the number of categories or trigger pool size is dramatically increased? Are there edge cases where the MC-STP approach fails to find effective triggers?\n\n2. Is there any qualitative evidence or further statistical analysis showing how unnoticeable the constructed triggers are to a human or automated anomaly detector?", "limitations": "See weaknesses", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n1. The paper addresses a relevant and challenging problem: graph backdoor attacks in the multi-category setting, which is not well studied in existing literature. The methodology leverages category-aware priors through a multi-category subgraph trigger pool, offering a more scalable approach than multiple independent trigger generators for each category. This is well-motivated both theoretically and, in Figure 1 and accompanying discussion, empirically justified.\n\n2. Technical exposition is mostly clear, with well-defined notation and logical descriptions that make the approach accessible for replication by experts. Algorithm 1 includes detailed procedural steps.\n\n3. Extensive experiments (Tables 1, 2, 3) across a variety of datasets (Cora, Pubmed, Bitcoin, Facebook, Flickr, OGB-arxiv) and defense scenarios provide compelling evidence for the claim that EUMC achieves high attack success rates (ASR) while maintaining clean node accuracy.\n\n## Weaknesses\n\n1. While the main logic and methodology are explained, certain practical implementation details are missing or under-explained in the core text, e.g., the precise role/impact of trigger size/threshold selection or prompt pool size. Figure 4 is only referenced at the end, with insufficient analytic commentary in the main text. This diminishes reproducibility and interpretability for non-domain experts.\n\n2. The core idea of using subgraph triggers is referenced in prior work (e.g., SBA [29], Sheng et al. [32]), albeit for different settings (graph classification or single-category). The paper could do more to clarify and contrast what is uniquely enabled by the multi-category focus, both theoretically and in practice. There is room for more explicit differentiation from similar ideas in the literature.\n\n3. The work considers several defenses, but does not include more recent or sophisticated graph backdoor detection approaches. Furthermore, there is little qualitative discussion or visualization of attack artifacts post-defense. How detectable are EUMC triggers via structural or statistical anomaly detection?", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer‘s recognition of our problem's relevance, method scalability, clear technical exposition, and compelling experiments and thank the reviewer for the constructive comments. Regarding the concerns of the reviewer WCrP, we provide the following responses. We hope our responses address the concerns raised, and we welcome active discussions with reviewers. \n\n> **W1. More details about the precise role/impact of trigger size/threshold selection or prompt pool size.** \n\nWe appreciate the reviewer's constructive comments. We have added a detailed explanation, which we briefly outline here:\n\n* **Trigger size**: Refers to the number of nodes in the trigger subgraph. A moderate number of nodes can effectively contain class structural information and class node information. If the size is too small, it fails to convey useful attack-related information; if too large, it may disrupt the degree distribution of the original graph structure, making it more likely to be pruned by defense strategies. Both scenarios can lead to a decrease in ASR.\n\n* **Threshold selection**: We select the most suitable trigger from the trigger pool for attacking the target node, and only connect nodes with similarity above the threshold to the target node, thereby enhancing the stealth of the attack. For instance, in arxiv dataset, only nodes with a similarity above 0.8 can connect to the target node, which significantly improves the stealth of the attack.\n\n* **Prompt pool size**: We apologize for the typo; this refers to \"trigger pool size\"—the number of triggers per class. For example, in 3-class Pubmed, we use 20 triggers per class, structured as {label1: [t1...t20], label2: [t1...t20], label3: [t1...t20]}.   A proper size enables effective multi-class learning with diverse structures. Too small: insufficient class learning and monotonous subgraphs. Too large: overlapping information and intra-class subgraph conflicts. Both reduce ASR and increase vulnerability to defense pruning.\n\n> **W2. Contribution and uniqueness about our method** \n\n* **Multi-category setting**: To our knowledge, this work is the first to systematically address **multi-category graph backdoor attacks** in GNN-based node classification—a critical yet underexplored scenario. Unlike existing graph backdoor methods focused solely on single-category misclassification, we target the more challenging task of inducing misclassification for multiple categories using distinct triggers without cross-interference. Experiments validate our method’s effectiveness, validity, and stealth.   \n* **Trigger pool with rich prior knowledge**:\n  * **Diverse and authentic structures**: Triggers are sampled directly as subgraphs from the original graph, **preserving its intrinsic structural patterns and feature distributions**. This avoids the \"artificiality\" of synthetic triggers, which often introduce unnatural topological/feature anomalies. \n  * **Explicit category awareness**: By sampling subgraphs from **a small subset (less than 5%)** of origin nodes, we embed **category-specific structural signatures** (by Eq.(1) ) into triggers. This inherently aligns triggers with their target categories’ topological traits, solving multi-category attacks’ core challenge: differentiating triggers across classes.  \n  * **Scalability**: Unlike methods requiring separate trigger generators per category (computationally redundant as categories grow), our pool-based design scales efficiently. It dynamically supports multiple categories without re-training generators, **adapting to large-scale multi-class scenarios**.   \n* **Stealthiness** is prioritized via a **\"select then attach\" strategy**, outperforming existing methods in preserving the graph’s natural properties: \n  * Unlike UGBA and DPGBA (which disrupt the original degree distribution by forcing single-edge trigger-host connections), our threshold-based selection only attaches triggers to host nodes with high structural/feature similarity. By retaining the original graph’s subgraph structures and aligning trigger-host similarity, triggers blend **more naturally into the topology**. This reduces detection risk from both structural anomaly detectors (e.g., monitoring topological outliers) and feature-based defenses (e.g., flagging unnatural feature mismatches).\n\n> **W3 & Q2. Further statistical analysis showing how unnoticeable the constructed triggers are to a human or automated anomaly detector? The work considers several defenses, but does not include more recent or sophisticated graph backdoor detection approaches. Furthermore, there is little qualitative discussion or visualization of attack artifacts post-defense. How detectable are EUMC triggers via structural or statistical anomaly detection?**\n\n* Among the defense strategies we tested, the OD strategy is a common automated anomaly detector. Specifically, the OOD detector (OD), trained on the poisoned graph, can identify triggers through reconstruction loss: by removing nodes with high reconstruction losses, the feature distribution of nodes can remain within the normal domain, preserving the data representation integrity. **As shown in Tab. 2**, ASR does not decrease significantly under OD detection, indicating that the defense strategy does not prune injected triggers excessively. \n\n* Futhermore, **in Fig. 3**, we have also analyzed the similarity distribution between the injected triggers and the original graph on the Arxiv dataset. It can be observed that the trigger similarity of our method not only falls within a reasonable range but also exhibits a distribution consistent with that of the original graph. This demonstrates that our method **can effectively evade defense strategies such as feature anomaly pruning and feature statistical distribution detectors**, while **not disrupting the similarity distribution of the original graph**.\n\n* We have also statistically analyzed the pruning ratio of OD, Prune, and Prune+LD across multiple datasets in **Table R1**. We can observe that existing defense methods can prune only a small portion of trigger nodes (0%-5%) but are generally unable to completely prune the entire trigger, which illustrates the stealthiness of our method. Furthermore, in **Table R2**, we tested our method on several recent detector approaches, further demonstrating the unnoticeable nature of our triggers. \n\n**Table R1**: The effectiveness of our method post-defense. 2.7%(0.2%) represents (node prune\\|trigger prune)\n\n| dataset   | Prune      | Prune+LD   | OD         |\n| --------- | ---------- | ---------- | ---------- |\n| Cora      | 2.7%(0.2%) | 2.3%(0.2%) | 1.7%(0.0%) |\n| Pubmed    | 1.5%(0.1%) | 1.7%(0.3%) | 1.5%(0.2%) |\n| Bitcoin   | 0.7%(0.0%) | 1.2%(0.1%) | 1.0%(0.1%) |\n| Facebook  | 4.3%(0.8%) | 3.9%(0.7%) | 2.7%(0.4%) |\n| Flickr    | 3.6%(0.4%) | 3.2%(0.4%) | 1.8%(0.2%) |\n| OGB-arxiv | 3.2%(0.6%) | 2.8%(0.3%) | 2.8%(0.4%) |\n\n**Table R2**: The ASR(Clean Acc) under different detector approaches.\n\n| Method    | Cora       | Pubmed     | Bitcoin    | Facebook   | Flickr     | OGB-arxiv  |\n| --------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- |\n| CONAD [1] | 95.3(81.7) | 94.9(83.9) | 89.1(78.3) | 91.3(83.6) | 90.2(44.7) | 82.8(65.2) |\n| GAAN [2]  | 96.1(82.1) | 95.5(84.2) | 88.3(78.3) | 90.9(83.3) | 90.3(45.2) | 83.1(65.1) |\n| XGBD [3]  | 95.7(81.4) | 95.3(84.1) | 88.6(78.3) | 91.7(83.6) | 89.9(44.8) | 83.0(65.1) |\n\nReference:\n\n[1] Chen, Henxing, et al. \"Generative adversarial attributed network anomaly detection\". Conference on Information and Knowledge Management (2020).\n\n[2] Xu, Zhiming, et al. \"Contrastive attributed network anomaly detection with data augmentation\". Pacific-Asia Conference on Knowledge Discovery and Data Mining (2022).\n\n[3] Guan, Zihan, et al. \"XGBD:Explanation-Guided Graph Backdoor Detection\". arXiv preprint (2023).\n\n> **Q1. Could the authors provide insight into the limits of the pool-based approach—what happens as the number of categories or trigger pool size is dramatically increased? Are there edge cases where the MC-STP approach fails to find effective triggers?**   \n\n* Unlike the single-structure and feature-dependent trigger generators in SBA, UGBA, and DPGBA, our pool-based method can effectively provide triggers with diverse structures, features, and class-specific knowledge as the pool size increases, addressing the issue where triggers struggle to attack different classes. However, as shown **in Tab. 2**, **with the increase in the number of categories**, the decrease in GNN clean accuracy leads to **insufficient learning of class information** by triggers, thereby reducing ASR. Additionally, **in Fig. 4a**, as the pool size increases to a certain extent, ASR stabilizes. This may be because triggers designed for the same class may inadvertently **learn overlapping information** due to inherent variability among nodes in that class, increasing the difficulty of learning highly specific and effective triggers. **With an increase in the size of the trigger pool**, the attack effectiveness and stealthiness are initially improved. However, if the pool becomes excessively large, it will lead to **increased subsequent computational overhead**, such as in the \"select then attach\" strategy. Additionally, it may contain **redundant subgraphs** that are isomorphic or near-isomorphic. \n* In **Fig. 3**, we show the similarity distribution between injected triggers and the original graph on the Arxiv dataset. Compared with methods like UGBA and GTA, our approach can effectively constrain trigger similarity within the range of original graph similarity and align with its distribution, demonstrating the stealthiness of our method. Meanwhile, in **Table R1**, we present the pruning ratios of triggers under different defense strategies—only a minimal proportion (**0.5%**) of triggers and (**4%**) of nodes are pruned, indicating that the MC-STP approach rarely fails to find effective triggers."}, {"review_id": "bFuSMz5COq", "reviewer": "Reviewer_ecxW", "summary": "The paper proposes a novel framework for effective and unnoticeable multi-category graph backdoor attacks using a subgraph trigger pool (MC-STP), which is an interesting and timely contribution to the area of adversarial robustness in graph neural networks. The idea of leveraging subgraphs from the original graph as triggers, combined with a “select-then-attach” strategy, offers a promising direction for crafting more realistic and stealthy backdoor attacks on GNNs. However, there are several concerns that need to be addressed before the work can be considered for acceptance.", "questions": "1. How would the method perform under limited or black-box access to the graph structure?\n\n2. Does the APS metric take into account class-specific or structural characteristics of subgraphs?\n\n3. How does the extensive subgraph sampling affect the overall efficiency of the method?", "limitations": "YES", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1.  The paper is well-organized, with a clear flow from problem formulation to methodology and experiments. The sections are logically arranged, making it easy to follow the proposed approach and its evaluation.\n\n2. The technical content is presented concisely without unnecessary complexity, aiding readability. However, some parts could benefit from improved clarity, especially regarding the construction and selection process of the subgraph triggers.\n\n\n\nWeaknesses\n\n1. Strong Attack Assumption : The method assumes full access to the training graph structure for subgraph sampling, which may not hold in practical or black-box scenarios. \n\n2. APS-Based Subgraph Selection Limitation : The trigger selection relies on APS, which measures prediction probability shifts but does not consider class-specific information. The design of APS is mainly about the offset probability of the original graphs, and it does not have a certain category and core information to mislead GNN.\n\n3. Computational Cost : Despite claiming low computational cost, the method requires extensive subgraph sampling and APS evaluation, which could be expensive, which is contradicting the motivation.", "was_revised": true, "final_justification": "I acknowledge the additional discussion on the multi-label setting and the empirical improvements obtained with APS labeling and original graph sampling. The responses have improved clarity regarding the experimental setup and reported results. However, my core concerns remain largely unaddressed.\n\nClass-Specificity Mechanism. The authors attribute class-specificity to the joint effect of APS selection and outer-loop optimization. While this explains how target categories are assigned and optimized in practice, the argument remains entirely empirical. The evidence provided, namely ASR under a targeted evaluation criterion, demonstrates that the method can achieve targeted misclassification. However, it does not establish that the triggers themselves are intrinsically class-aligned rather than functioning as strong general perturbations. There is no theoretical analysis, visualization, or dedicated optimization objective to verify that the trigger structure and parameters encode category-specific patterns in the feature or structural space. As a result, the class-specificity claim remains insufficiently supported at the mechanism level.\n\nMethodological Novelty. Although I acknowledge the novelty of extending the attack setting from single-label to multi-label graphs, this is a contribution at the problem-definition level. At the methodological level, the framework of original graph sampling, APS labeling, and trigger pool construction appears to be a composition of established techniques. APS itself is essentially a probability-shift-based heuristic that is conceptually similar to other perturbation-based metrics. The method is not accompanied by a new optimization objective, a novel trigger design principle, or an adversarial mechanism that would constitute a theoretical breakthrough.\n\nIn summary, despite the additional clarifications and empirical results, the two key points from my original review remain unresolved. These are the lack of mechanism-level evidence for class-specificity and the limited methodological novelty. I therefore maintain my initial evaluation.", "rebuttal": "We appreciate the reviewer's recognition of our novel framework as an interesting and timely contribution, plus the paper's good organization, clear flow, logical sections, and concise content and we thank the reviewer for the constructive comments. Regarding the concerns raised by Reviewer ecxW, we provide the following responses. We hope our responses address the concerns raised, and we welcome active discussions with reviewers.    \n\n> **W1 & Q1. How would the method perform under limited or black-box access to the graph structure?**  \n\n* According to [1], compared with black-box attack, **backdoor attacks require accessing partial data to learn triggers**. Meanwhile, it is indicated that accessing **10%-20%** of the graph data structure is acceptable in backdoor attack scenarios. In **Section 5.1 (Evaluation Protocol)**, the number of accessible labels used in our training is only **15%** of the original number of nodes. Following the settings of UGBA and DPGBA, our experimental setup is consistent with the configurations in [2], [3]. Certainly, performing effective backdoor attacks with limited available data remains a promising direction for future research.   \n\n* To further illustrate the effectiveness of our method, we conducted additional tests using **5%** and **10%** of the training data samples on **OGB-arxiv** in **Table R1**. It can be observed that under conditions with extremely limited accessible data, the performance of our method does not degrade significantly, indicating that our method can still achieve favorable results **under stricter constraints (less available data)**. \n\n**Table R1**: The ASR(Clean Acc) of different models under 5%, 10%, and 15% available training graph.\n\n| Method     | 5%         | 10%         | 15%         |\n| ---------- | ---------- | ----------- | :---------- |\n| SBA        | 2.5(66.0)  | 2.5(65.9)   | 2.5(66.2)   |\n| GAT        | 59.3(65.6) | 62.2(65.6)  | 68.4(65.6)  |\n| UGBA       | 57.8(63.7) | 58.9(64.2)  | 63.7(64.9)  |\n| DPGBA      | 60.5(63.9) | 63.7(64.1)  | 68.8(64.9)  |\n| EUMC(ours) | 80.2(64.5) | 82.8 (64.7) | 83.8 (65.3) |\n\nReference:\n\n[1] Yang X, et al. \"Graph neural backdoor: Fundamentals, methodologies, applications, and future directions\" arXiv preprint (2024).\n\n[2] Dai, Enyan, et al. \"UGBA: Unnoticeable Backdoor Attack on Graph Neural Networks\" Proceedings of the ACM Web Conference (2023).\n\n[3] Zhang, Zhiwei, et al. \"Rethinking Graph Backdoor Attacks: A Distribution-Preserving Perspective\" Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (2024).\n\n> **W2 & Q2. Does the APS metric take into account class-specific or structural characteristics of subgraphs?**   \n\nWe thank you for pointing out these issues. **In fact, APS does take into account the class-specific and structural characteristics of subgraphs**. The reasons are as follows. \n\n* In Section 4.1, Eq. (1), for each trigger generated by MC-STP, we use APS to determine the target attack label for every trigger. For each trigger $t$, a GNN classifier is used to predict the probability distributions of node labels **before and after the trigger injection**, and the difference between these distributions is calculated. By summing and averaging the label probability shifts across multiple nodes, we obtain **an APS vector** with length as the number of category, which **represents the impact degree of the trigger $t$ on each class**, and we select the class with the highest label probability shift as the target attack class for the trigger, thereby incorporating class-specific information. During this process, the GNN classifier, used to predict the probability distributions, **can capture the structural characteristics and node information** of both trigger subgraphs and target-node subgraphs.\n* **For example**, using the OGB-arxiv dataset (with 169,343 nodes and 1,166,243 edges), we first select 4000 central nodes, and each central node sampled **10 subgraphs**, resulting in a total of **40,000 sampled subgraphs**. After **k-means clustering**, we obtained an MC-STP containing 800 triggers. We then assigned **target attack labels** to the 800 triggers using Eq. (1) in Section 4.1 based on their Attachment Probability Shift(**APS**).  \n  A trigger $t$ is attached to $N$ nodes. A GNN classifier then calculates the probability distributions $p_{bef}^{t, i}$ and $p_{aft}^{t, i}$ before and after the trigger $t$ is injected into the nodes. Here, $p_{bef}^{t, i}, p_{aft}^{t, i} \\in \\mathbb{R}^{N_{cls}}$ represents the predicted probabilities for each class. At this point, we compute $\\text{APS}^{t} = \\frac{1}{N} \\sum_{i=1}^{N}|p_{bef}^{t, i} - p_{aft}^{t, i}|$ to obtain the $\\text{APS}^{t} \\in \\mathbb{R}^{N_{cls}}$. The $\\text{APS}^{t}$ indicates the impact of the trigger $t$ on each class, and we select the category with the greatest influence as the **target attack label** $y_t=\\arg\\max(\\text{APS}^{t})$ for trigger $t$, indicating that $t$ has the most significant impact on category $y_t $ and can be more stealthily disguised as nodes of category $y_t $.\n* In conclusion, by calculating probability shift using a GNN classifer, we capture **the structural characteristics of graphs**. Additionally, through estimation based on samples of N nodes, we can identify **\"which class is most affected by the trigger\"**; this serves as **implicit class-specific information**. \n\n> **W3 & Q3. How does the extensive subgraph sampling affect the overall efficiency of the method?**   \n\nWe thank the reviewer for the suggestion to discuss the efficiency of MC-STP. **In practice, subgraph sampling does not incur significant computational costs**. We provide the following reasons:\n\n* First, subgraph sampling via BFS is a **pre-processing step that only needs to be performed once**. In subsequent processes, we can reuse the previously sampled results without re-conducting BFS.   \n\n* Second, as mentioned in **Section 4.1**, we initially randomly select several nodes from the unlabeled graph, $V_U$, to serve as central nodes. These central nodes account for **a small proportion** of the original graph, and we do not sample all possible subgraphs. Instead, we set thresholds for the total number of sampled subgraphs and the number of subgraphs sampled per central node. \n\n* Third, we analyzed **the time complexity of the MC-STP Construction**. Let $h$ denote the embedding dimension, $n$ represent the number of nodes in each trigger, $K$ be the number of target categories, and $|\\mathcal{N}_S|$ be the number of subgraphs to extract. The cost of constructing the MC-STP is approximately $O(nh|\\mathcal{N}_S| + Kh|\\mathcal{N}_S| + Kh)$, which covers extracting $|\\mathcal{N}_S|$ subgraphs with $n$ nodes each and clustering them into $K$ clusters. Since subgraph and feature extraction is the dominant cost, the overall time complexity is approximately $O(Kh|\\mathcal{N}_S|)$. Therefore, the complexity of the MC-STP Construction is proportional to the number of sampled subgraphs. **Furthermore, subsequent experiments and analyses demonstrate that subgraph sampling is not time-consuming.**\n\n* For example, the OGB-arxiv dataset has 169,343 nodes and 1,166,243 edges. **In the pre-processing step,** we selected 4000 central nodes, and each central node was used to sample 10 subgraphs, resulting in a total of **40,000 sampled subgraphs**. The number of nodes used accounts for **2.3%** in the original graph. After clustering, we obtained MC-STP containing 800 triggers, so APS only needs to be calculated within these 800 triggers. **In the training step**, we only used **2.7% nodes with labels**. These proportions are extremely small, so they do not incur significant computational costs. \n\n* We have also conducted **efficiency tests on multiple datasets** in **Table R2**, demonstrating that subgraph sampling does not incur significant computational costs.\n\n**Table R2**: The time cost of construction MC-STP.\n\n| dataset   | sample central nodes | sample subgraph | time cost(s) |\n| --------- | -------------------- | --------------- | ------------ |\n| Cora      | 700                  | 7,000           | 78.6         |\n| Pubmed    | 1,200                | 12,000          | 114.7        |\n| Bitcoin   | 1,500                | 15,000          | 138.2        |\n| Facebook  | 1,600                | 16,000          | 156.8        |\n| Flickr    | 2,100                | 21,000          | 231.3        |\n| OGB-arxiv | 4,000                | 40,000          | 423.7        |"}]

Author rebuttal:

Meta-review: Existing graph backdoor attack methods mainly focus on single attack categories and struggle to handle backdoor attacks across multiple categories as the number of target categories increases. This paper proposes a new approach for Effective and Unnoticeable Multi-Category (EUMC) graph backdoor attacks, leveraging subgraphs from the attacked graph as category-aware triggers to precisely control the target category. 

Pros:
- The paper studies a less-studied problem of graph backdoor attacks in the multicategory setting. It proposes a new multi-class graph backdoor attack method 
- The paper is well-structured and easy to follow 
- Experimental results demonstrate the effectiveness of the proposed method

Cons:

Most of the reviewers’ concerns are addressed except the one below

- The Reviewer ecxW still has two major concerns after the rebuttal, i.e., the lack of mechanism-level evidence for class-specificity and the limited methodological novelty

As most of the reviewers agree on the novelty and contribution of the paper, the paper can be accepted. The authors should incorporate clarifications and extra experiments into the camera-ready version.
Decision: Accept (poster)