Stealthy Yet Effective: Distribution-Preserving Backdoor Attacks on Graph Classification
Authors: Xiaobao Wang
Ruoxiao Sun
Yujun Zhang
Bingdao Feng
Dongxiao He
Luzhi Wang
Di Jin
Venue: NeurIPS 2025 poster ()
Keywords: Graph Neural Networks
Backdoor Attacks
Stealthy Trigger
Primary area: deep_learning

Abstract: Graph Neural Networks (GNNs) have demonstrated strong performance across tasks such as node classification, link prediction, and graph classification, but remain vulnerable to backdoor attacks that implant imperceptible triggers during training to control predictions. While node-level attacks exploit local message passing, graph-level attacks face the harder challenge of manipulating global representations while maintaining stealth. We identify two main sources of anomaly in existing graph classification backdoor methods: structural deviation from rare subgraph triggers and semantic deviation caused by label flipping, both of which make poisoned graphs easily detectable by anomaly detection models. To address this, we propose DPSBA, a clean-label backdoor framework that learns in-distribution triggers via adversarial training guided by anomaly-aware discriminators. DPSBA effectively suppresses both structural and semantic anomalies, achieving high attack success while significantly improving stealth. Extensive experiments on real-world datasets validate that DPSBA achieves a superior balance between effectiveness and detectability compared to state-of-the-art baselines. The code is available at https://github.com/TheCoderOfs/DPSBA.

Stealthy Yet Effective: DistributtonnPrrseeving Backdoor Attacks on Graph Classification
Xiaobao Wangl2 Ruoxiao Sun' Yujun Zhang' Bingdao Feng' Dongxiao He' Luzhi Wang* Di Jin
CCollege of Intelligence and Computing, Tianjin University, Tianjin, China 2 Guangdong Laboratory of Artificial Intelligence and Digital Economy (SZ), Shenzhen, China *College of Artificial Intelligence, Dalian Maritime University, Dalian, China {wangxiaobao, rxiao_sun, zhangyujun)@tjun edu..uuedu... edu. cn (fengbingdao, hedongxiao, jindi]@tju edu. cn, wangluzhi0@gaail.. com
Abstract
Graph Neural Networks (GNNs) have demonstrated strong performance across tasks such as node classification, link prediction, and graph classification, but remain vulnerable to backdoor attacks that implant imperceptible triggers during training control predictions. While node-level attacks exploit local message passing, graph-level attacks face the harder challenge of manipulating global repre- sentations while maintaining stealth. We identify two main sources anomaly existing graph classification backdoor methods: structural deviation from rare sub- graph triggers and semantic deviation caused by label flipping, both of which make poisoned graphs casily detectable by anomaly detection models. To address this, we propose DPSBA, a clean-label backdoor framework that learns in-distribution triggers via adversarial training guided by anomaly-aware discriminators. DPSBA effectively suppresses both structural and semantic anomalies, achieving high attack success while significantly improving stealth. Extensive experiments real-world datasets validate that DPSBA achieves a superior balance between effectiveness and detectability compared to state-of-the-art baselines. The code is available httpps:/ //t::://ttiii giggtu..b... com comm/hhhCoodrrOf///P9AA
Introduction
Graph Neural Networks (GNNs) are foundational models for learning on graph-structured data, achieving strong performance in tasks like node classification, link prediction, and graph classifi- cation [T] Through message passing, GNNs capture structural and feature dependencies, enabling applications in social networks (2), recommender systems [3], and molecular analysis [4. As GNNs are increasingly adopted in real-world systems, their security has drawn growing attention. Among various threats, backdoor attacks, where imperceptible triggers are embedded [5] in training data to manipulate predictions, pose serious risk due to their stealth 6 While extensively studied in vision and NLP, backdoor vulnerabilities in graph learning remain under exploration.
Most existing graph backdoor studies focus on node classification, where local triggers are injected to misclassify specific nodes [9] [0]. These attacks leverage GNN locality to propagate triggers through neighborhoods while remaining hard to detect. Link prediction attacks similarly operate in local context, targeting the presence or absence of edges between node pairs [[]. In contrast, graph classification poses fundamentally different and more complex challenge. Here, the attacker must influence the global semantics of an entire graph rather than single node or edge. This requires
"Corresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

30-
Grank
Class Coagk
Buckder Gogg
30
Frequeacy
Frequency
20
Frequency
75
20-
20-
10-
20-
1.5
2.0
Anomaly Score
Anomaly Score
Anomaly Score
(a) ER-B
(b) GTA
(c) Motif
Figure 1: Anomaly score distributions of clean vs. backdoor graphs on the AIDS dataset.
Anomaly scores are computed via SIGNET [12] for backdoor samples generated by ER-B [T3. GTA [14), and Motif [S]. In all cases, backdoor graphs (yellow) shift significantly rightward compared to clean graphs (blue), revealing strong distributional deviation. This underscores the detectability of prior triggers and the need for distribution-preserving preserving attacks.
triggers to manipulate the full- full-graph embedding, often through larger or structurally rare subgraphs. Recent backdoor attacks on graph classification attempt to address global manipulation challenges by injecting structurally distinct subgraphs, such as rare motif's [1]] However, these approaches often introduce obvious out-of-distribun
(OOD) artifacts, which significantly compromise stealth and limit their practicality in real-world settings. As shown in Figure there exists clear distribution gap between clean and backdoor graphs, making current methods highly detectable by outlier detection models. Although Zhang et al. [16] similarly observe OOD issues node classification and propose a crtrribttion-reseevvin strategy, their approach relies on local perturbations that affect only single node's embedding. In contrast, graph classification requires modifying the global message-passingg process to influence the entire graph representation, making distribution preservation significantly more challenging (see Appendix C.I for theoretical justification).
This global nature further amplifies the risk of both structural and semantic deviations when inserting backdoor triggers, as detailed in Appendix A 1) Structural Deviation: Triggered by the injection of rare or unnatural subgraphs (e.g., low-frequenc motifs) that diverge from the structural distribution of clean graphs. These triggers often create shortcut correlations with target labels and are easily identified by outlier detectors, as shown in Table A5 Rare motifs as triggers (Motif) achieve high attack success rates (ASR) but are highly detectable. In contrast, more frequent motifs (Motif-S) reduce detectability but also weaken attack effectiveness; 2) Semantic Deviation: Caused by label flipping, this introduces a discrepancy between a graph's 's assigned class and its inherent structure. As demonstrated in Table[A6 adopting alean-label settings reduces the overall anomaly degree (AUC) across all methods but results in a notable ASR drop, revealing a fundamental trade-off between attack stealth and success. These findings highlight critical limitation of existing methods: their inability to balance effectiveness and stealth. This raises a key challenge: Can we design a graph-level backdoor attack that preserves the distributional properties of clean samples, avoids label manipulation, and remains both effective and stealthy?
To tackle these challenges, we propose DPSBA Enstributtinn-Preeevvivv Stealthy Backdoor Attack), a clean-label backdoor framework for graph classification. Unlike prior methods that use rare or manually designed subgraph triggers, often causing high anomaly scores, DPSBA adaptively learns in-distribution triggers from target-class data. To address both structural and semantic deviations, it introduces a joint training strategy combining: (I) clean-label attack mechanism that preserves semantic consistency by avoiding label flipping, and (2) distribution-awar discriminators that penalize structural and feature-level anomalies. Through adversarial training with surrogate classifier and anomaly detectors, DPSBA enables effective and stealthy trigger generation. Experiments on real-world datasets show that DPSBA substantially lowers anomaly scores while maintaining high attack success rates, achieving a strong trade-off between stealth and efficacy.
2 Preliminaries
In this section, we first give the definition of the graph classification task and then introduce our stealthy backdoor attack objective.

---

2.1 Graph Classification Task
Given a dataset consisting of graph-structured instances, the objective of graph classification to assign a class label to each graph. Formally, graph classification dataset is defined as: C = {(G1, y1), (G2, 3/2) :2.,... (G,, }, where each graph G; = (V,, E2) is composed of a set nodes V, and edges E,, and y y is the corresponding ground-trute truth class label. Let denote the number of graph samples in the dataset. The goal is to learn graph-level classifier: f 9 - y, which maps each input graph G G to one of the class labels in Y/ = (y1, 9/,,.., .n.,...... ). The classifier f is typically trained via gradient-band baaeed optimization using a supervised loss function Ltrain (e.g., cross-entropy) over the training set Crnin-
2.2 Stealthy Backdoor Attack on Graph Classification Task
Backdoor attacks inject hidden and malicious trigger mechanism (i.e., "backdoor") into the target model in advance. When the trigger appears, the backdoor is activated and misleads the model to get the desired output.
Attacker's Goal. The objective of backdoor attacker in graph classification threefold: (1) The model trained with injected backdoors should predict any graph containing the trigger as the attacker- specified target label yı: (2) The model's performance on clean graphs should remain unaffected; (3) The backdoor graphs should not exhibit significant distributional deviations from clean graphs, ensuring high stealthiness. Formally, the attacker's goal can be formulated as:
fa. (m((:: = yr- (G) = fG),,, diff (m) Sc.
(1)
where G denotes clean graph, and is the target label specified by the attacker. The function g(; denotes the trigger injection process, producing backdoor graph G,, by embedding trigger subgraph Sr into G. So and Se, represent the clean and poisoned graph classification models, respectively. So is a detection model trained on clean graphs, and dill(...) measures the anomaly difference (e.g.. anomaly score) between clean graph and its backdoor counterpart. The scalar defines an upper bound on acceptable deviation for stcalthiness, and can be tuned per dataset.
Attacker's Knowledge and Capability. We consider a restricted and realistic threat model in which the attacker has limited access and control: (1) Black-box knowledge: The attacker has knowledge the target model architecture, training hyperparameters, or optimization pipeline. This accommodates the possibility that different graph classification models may be deployed. (2) Limited poisoning capability: The attacker can only poison a small fraction of the training dataset and is not allowed modify any labels. This reflects more challenging clean-label setting and simulates real-world scenarios where data integrity is partially enforced.
3 Methodology
Grounded in the attacker's goal, DPSBA adaptively generates subgraph triggers whose topology and features mimic in-distribution patterns of clean graphs, reducing detectability while ensuring attack success. As shown in Figure 2 DPSBA includes two stages: poisoned sample construction and trigger optimization. In the first stage, hard samples from the target class are selected and injected with triggers strategically chosen locations. The trigger's structure and features are generated by learnable hopology-fcature generator. In the second stage, DPSBA jointly optimizes attack success via surrogate model and minimizes detectability via anomaly-aware discriminators through staged adversarial training.
3.1 Poisoned Sample Construction
To support clean-label stealthy backdoor injection, DPSBA constructs poisoned samples from the target class itself, avoiding explicit label flipping. This process comprises three stages: (i) selecting informative samples for poisoning, (ii) identifying optimal injection locations within each graph, and (iii) initializing and injecting the trigger subgraph. Together, these steps ensure that the backdoor signal is both semantically consistent and statistically in-distribution.
3

---

Target Class
Hard Sample
Inject the Initialized Trigger
Trigger Generator
Topology
Sample Selection
Location Selection
Generator
Feature
Updute Parameters
Generator
Surrogate Model
Adversarial Training
Siructure Anomaly
Feature
Anomaly
Diseriminator
Discriminator
Figure 2: The overall structure of DPSBA
3.1.1 Hard Sample Selection
In the clean-label setting, directly selecting target-class samples avoids semantic inconsistency but may reduce the effectiveness of the attack. To counteract this, DPSBA strategically mines hard samples, i.e., samples from the target class that the model finds uncertain. This design is inspired by Gao et al. [77], who show that hard samples can amplify the effectiveness of backdoor attacks by being more susceptible manipulation. In partieular, low-confidence samples, those near the model's decision boundary, require smaller perturbations to shift predictions, and are thus better candidates for subtle backdoor injection. We clean surrogate model Sa measure the confidence score of a graph G with respect to the target label y/2 as:
efo(G)
cfd(G) softmax(fo(G))
where fo(G) E R.K denotes the logit output of the surrogate model for graph G, K is the total number of classes, and Y/ is the target class index. We select the bottom p% of target-class graphs with the lowest cG) scores as poisoned samples. These hard samples are passed to the subsequent trigger location and injection stages, where subtle but effective perturbations are applied. Since they are more vulnerable to decision changes, they are more likely to be misclassified into the target class once the trigger activated, while still maintaining clean-label consistency and high stealth.
3.1.2 Trigger Location Selection
After selecting the hard target-class samples for poisoning, DPSBA determines where each graph to inject the trigger. Existing studies adopt various strategies to identify influential nodes, such using centrality metrics [3] or extracting interpretable subgraphs [8] 19.. While interpretation based methods offer precision, they often incur prohibitive computational costs. To strike balance between scalability and informativeness, DPSBA adopts a two-stage selection process. First, nodes with high degree centrality pre-selected candidates. Specifically, for a graph G with N nodes, compute the normalized degree centrality each node v as deg(v)/ (v)((())) 1) and retain the top-k nodes (with typically set to 2MM where M is the trigger size). Next, among these candidates, identify the M most influential nodes using surrogate-base based ablation approach. For each node v in the candidate set Noan, we evaluate its contribution model prediction by measuring the change in output after removing it:
S(v) = (o AA.) (G().
(3)
where A, denotes the removal node v from G. The top-M nodes with the highest S(v) values are selected as trigger attachment nodes. These nodes then replaced, along with their edges, by initialized subgraph trigger 9: to prepare for the subsequent generation phase.
3.1.3 Trigger Generation and Injection
To enable the insertion of stealthy and effective triggers, generative approaches offer superior flexibility and control over random, interpretabillty-basee or search-based strategies. Inspired by GTA [4]. DPSBA introduces two lightweight yet expressive modules, i.e., topology generator and a feature generator, that cooperatively define the structure and node attributes of the injected subgraph. These generators trained in separate phase adaptively fit the data distribution.

---

Topology Generator. The topology generator is implemented as a multilayer perceptron (MLP) that transforms the adjacency matrix H of the target injection region into learnable soft structure: H' = (W, H + b)), where W1 and by are learnable parameters (for the convenience of subsequent discussion, they will be simply referred to as wy) and (-) a non-linear activation function. For
undirected graphs, the adjacency matrix is symmetrized as 2 H' H')) To accommodate the discrete nature of graph topology, we adopt a binarization mechanism inspired by binarized neural networks [20]. where the final adjacency matrix is given by: Atimary = I[A > 0.5). Binarization is applied only during forward propagation to preserve gradient flow during backpropagation. The resulting binary matrix defines the trigger's structural connectivity.
Feature Generator. To ensure the feature space consistency between clean and poisoned graphs, the feature generator produces trigger node features based on the original features at the injection site. It employs MLP to generate: X' = (W2 + b2), where X denotes the original features of the injected nodes, and W2, b2 are learnable parameters, which are simply referred to as wy for the convenience of subsequent discussion. This transformation ensures that generated features remain aligned with the data distribution, thereby reducing feature-level anomaly. Besides, the feature generator can also avoid distribution shift when the target graphs have high attribute variance. The feature generator does not rely on distribution priors of the entire dataset. Instead, it takes as input the local structural and attribute context around the trigger injection site and generates features that blend smoothly with the surrounding neighborhood. This allows the generator to adapt to the specific variance of each target graph on a per-instance basis, without requiring any handerafted normalization or explicit regularization. As result, the generated features remain close to the local data manifold, reducing the likelihood of creating detectable anomalies, even the presence of high attribute variance across graphs.
Trigger Injection. Given a selected clean graph G and the generated trigger subgraph 9e = (Abinary: X'). DPSBA injects the trigger at the designated node locations produce a poisoned sample: Gg. mmG; gt), where m(.) denotes the injection operation. The resulting Gg, is added to the training set along with clean graphs. After the backdoored model is trained, the attacker craft adaptive triggers during inference and inject them into arbitrary test graphs to activate the backdoor and induce targeted misclassification.
3.2 Trigger Optimization
Once the trigger subgraph is initialized, DPSBA enters the optimization phase to jointly refine the topology and feature generators for both effectiveness and stealth. It minimizes a hybrid objective comprising: (1) attack loss that enforces confident misclassification into the target class, and (2) an adversarial anomaly loss that suppresses structural and feature-level deviations detectable by outlier models. This is achieved via two-stage adversarial training strategy with dedicated discriminators and a dynamically updated surrogate model.
Attack Effectiveness. The core goal of a backdoor attack is to ensure that the trigger-embedded graph Gg. is classified into the target class yt. This is achieved by minimizing the attack loss with respect to surrogate model so-
Lack = log fo- (G )
where fo- (.)g, denotes the logit output of the surrogate model for class yt-
Stealthiness via Adversarial Anomaly Minimization. To ensure the trigger remains statistically in- conspicuous, DPSBA introduces adversarial discriminators trained to distinguish clean and backdoor samples from structure and feature perspectives. Specifically, the topology discriminator Do, (a GCN) detects structural anomalies, while the feature discriminator Da, (an MLP) detects feature distribution shifts. The generators aim to fool these discriminators via the following minimax objectives:
min max 9,
log Do. (G) + Σ
log(1 -Do (G (wx)))
(5)
GmB
G~
min max Wy
Σ
log Do, (G) +
Σ
log(1 Do, (G (wy))),
(6)
8,
G~
G~
5

---

where Ge and G. are the clean and poisoned graph sets, and wi, wy are the generator parameters. Joint Training Objectives. DPSBA jointly optimizes the generators using weighted of the attack loss and the corresponding adversarial loss. For the topology generator:
min Σ We
Carn gG. (wi) ac (De, (Gga (we))), s.t. 0 arg min Lirain (f (7)
GEM
and for the feature generator:
min wy
Σ
Cast(Gge (wy)) + (Do, (wy))), s.t. 0 arg min (frain(f((C))
(8)
GEG
where a and 3 are hyperparameters balancing stealth and attack objectives, and C is the clean training set used to update the surrogate model.
To realize both stealth and attack effectiveness, DPSBA adopts staged adversarial training strategy to optimize the topology and feature generators in coordination with anomaly discriminators. The joint objective encourages trigger-embedded graphs be confi- dently misclassified into the target class while remaining statistically similar to clean samples. To further justify this design, we derive Appendix C.2 formal lower bound that connects the total variation distance between clean and poisoned graph distributions with the optimal anomaly detection AUC, demonstrating that minimizing such divergence directly improves stealthiness.
Adversarial Training Strategy.
The training process consists of two alternating phases: 1) Topology optimization phase: The topology generator Wμ and discriminator Dø, alternately updated. The generator learns to create subgraph structures that both maximize attack loss Lask and minimize structural anomaly signals detectable by Du,- 2) Feature optimization phase: Similarly, the feature generator wy and discriminator De, are jointly trained. The generator adapts node features to support effective attacks while suppressing attribute-level anomalies identified by Dø,, To maintain alignment with the evolving trigger distribution, the surrogate model fe is fine-tuned after each phase, ensuring reliable attack gradient signals throughout training. This cooperative optimization framework allows DPSBA to dynamically balance the trade-off between attack success and stealth, as further summarized in Appendix Time complexity analysis can be found in Appendix F
4 Experiment
We first introduce the experimental setup, including datasets, baselines, and implementation details. Then, we evaluate DPSBA's performance on attack effectiveness and stealth across multiple settings, followed by ablation analysis and anomaly stealth evaluation. Additional hyperparameter studies are included Appendix E.4 B.5
4.1
Experimental Setup
4.1.1 Datasets and Evaluation Metrics
We evaluate DPSBA on four real-world graph classification datasets from the TUDataset benchmark (1]]: PROTEINS full (22) protein graphs for function prediction), AIDS (23) (molecular graphs related to AIDS research). FRANKENSTEIN [24] (a compound property dataset combining BURS and MNIST features), and ENZYMES 25 (a 6-class biomolecular classification task). For each dataset, we designate the minority class as the attack target to simulate realistic low-frequency scenario. The statistics for the datasets are summarized in Table E7 We adopt three metries: ASR (Attack Success Rate) for attack effectiveness, CAD (Clean Accuracy Drop) to assess model utility degradation, and AUC (Area Under the ROC Curve) to quantify anomaly detectability via outlier models. Detailed metric definitions are deferred to Appendix E.2
4.1.2 Baselines
We compare DPSBA with five representative graph-level backdoor attack methods. ER-B 13 generates universal triggers using the Erdös-Rény: random graph model. LIA [18 modifies the connections of low-importance nodes, as identified by GNN explanation techniques, with fixed trigger structures. GTA [4 employs bi-level optimizztinn strategy to train subgraph generator that adapts

---

triggers per graph. Motif [[5] selects low-frequency motifs from the dataset as effective but easily detectable triggers. Motif-S stealthier variant using the high-frequency M41 motif, reducing anomaly scores while slightly sacrificing attack strength. Following GTA [14], we split each dataset into 50% training and 50% test sets, with 5% of the training data poisoned. To ensure fair comparison, all methods adopt fixed trigger size of 4. Both the topology and feature generators are trained for 20 epochs per stage over iterations with a learning rate 0.001, using early stopping [27]. For baselines, use the best hyperparameters reported in their original papers.
4.1.3 Graph Classification Models and Anomaly Detection Algorithms
Following prior work graph backdoor attacks 15 we evaluate DPSBA three widely used graph classifiers: GCN [28] GIN [29]. and SAGPool [30]. These models are used both as attack targets and surrogates to test generalizability actoss architectures. Clean accuracy results are reported Table E8, For anomaly detection, we adopt SIGNET [12), identified as the most effective method in recent benchmark study [3]] to assess the stealthiness of injected backdoor samples.
4.2 Experimental Results
Table I: Comparison results between DPSBA and each baseline model
Surrogate Model
Datasets
Metrics
ER-B
LIA
GTA
Motif
Motif-S
Ours
ASR (%)
51.53
68.35
73.16
70.91
48.56
73.93
GCN
CAD (%)
4.73
4.70
5.14
5.92
4.66
4.62
AUC (%)
70.04
71.01
78.20
79.16
64.72
60.11
PROTBINS_ full
ASR (%)
62.53
58.77
80.96
79.08
63.01
87.91
GIN
CAD (%)
4.88
4.36
4.57
4.97
4.33
4.92
AUC (%)
79.65
71.74
79.96
80.06
70.49
62.95
ASR (%)
65.38
64.81
94.04
71.35
57.09
94.15
SAGPool
CAD
4.26
5.02
3.65
3.36
3.94
3.29
AUC (%)
71.34
76.89
78.57
82.75
81.81
69.20
ASR (%)
85.38
85.49
93.21
92.69
56.08
94.76
GCN
CAD
4.53
3.80
5.14
4.12
4.03
2.38
AUC
98.08
97.22
99.34
99.71
89.43
72.65
AIDS
ASR (%)
93.99
95.56
97.52
97.75
56.8
95.87
GIN
CAD (%)
2.69
2.03
2.65
2.28
2.51
1.94
AUC (%)
99.98
99.20
99.34
99.71
94.29
73.66
ASR (%)
59.26
62,66
86.99
87.65
62.89
98.90
SAGPool
CAD (%)
1.65
1.79
3.77
2.64
2.44
-0,40
AUC (%)
95.79
94.56
99.67
99.02
93.43
77.23
ASR (%)
63.60
61.04
99.35
80.57
59.24
98.37
GCN
CAD (%)
1.71
1,56
2.74
1.15
3,96
1.01
AUC (%)
80.41
75.66
100.00
89.64
69.23
68.96
FRANKEN- STEIN
ASR (%)
92.06
82.63
98.65
92.87
58.68
99.84
GIN
CAD (%)
3.60
2.35
1.95
2,44
1.75
1.83
AUC (%)
85.73
76.15
91.06
87.54
65.77
73.46
ASR (%)
68.15
90.18
95.23
84.56
52.29
99.99
SAGPool
CAD (%)
4.78
4.66
4.64
4.61
6.86
4.57
AUC (%)
64.89
77.50
80.46
87.29
60.98
60.12
ASR (%)
26.09
30.43
95.33
21.74
15.21
96.67
GCN
CAD (%)
4.17
4.99
3.00
4.99
-1.67
-0.67
AUC
68.32
66.15
71.20
71.35
66.22
66.11
ENZYMES
ASR (%)
37.83
27.02
96.00
16.21
12.16
99.33
GIN
CAD (%)
9.17
10.00
2.67
8.33
4.17
-0.33
AUC (%)
71.40
62.01
76.42
68.18
65.78
41.20
ASR (%)
29.54
38.63
100.00
15.91
11.37
100.00
SAGPool
CAD (%)
4.33
6.67
5.00
10.83
3.33
4.00
AUC (%)
57.73
63.98
70.37
75.47
69.48
49.91

---

Table 2: Results of the transferability evaluation(%))
PROTEINS_Íie
AIDS
FRANKENSTEIN
Surrogate model
Actual model
ASR
CAD
ASR
CAD
ASR
CAD
GIN
81.32
4.79
99.44
1.01
98.37
0.03
GCN
SAGPool
98.90
0.08
96.14
2.48
94.96
-0.10
4.2.1 Effectiveness and Stealthiness
We evaluate DPSBA on four datasets against six baselines in terms of attack effectiveness (A (ASR), model performance drop (CAD), and anomaly detectability (AUC), shown in Table DPSBA consistently achieves optimal or near-optimal ASR across datasets and models, verifying its strong attack capability. This credited its adaptive trigger generation guided by confident hard samples and structurally important nodes. In terms of CAD, DPSBA maintains minimal accuracy degradation (<5%), indicating high stealth the model level. For distribution-lewe stealth, DPSBA significantly reduces AUC, i.e., maintaining values around 70%, demonstrating strong resistance to detection by statistical outlier models. We further observe that ASR and AUC fluctuate significantly across datasets due to inherent differences in graph structure and anomaly sensitivity. For datasets particularly sensitive attribute or structural perturbations (e.g., FRANKENSTEIN) even minor modifications can induce high ASR yet large anomaly scores. In such cases, we recommend an early stopping strategy, namely terminating generator updates once ASR saturates or marginal gains diminish, to enhance stealth. For instance, FR BRANKENSTEIN, where attribute anomalies are highly detectable (GTA achioves >95% ASR but with high AUC), DPSBA disables the feature generator early, achieving near-perfect ASR solely via structural triggers. Across all benchmarks, DPSBA achieves the high ASR of Motif while matching the stealth of Motif-S, validating its ability to balance effectiveness and detectability. For multi-class graph classification tasks, DPSBA consistently outperforms all baselines in terms of both attack success rate (ASR) and stealth (CAD, AUC) across three surrogate models. Notably, most baselines (except GTA) fail on this dataset due to high attribute and strucutre variability, underscoring the advantage of our distribution preeeorving and adaptive design.
4.2.2 Transferability
To evaluate the transferability of DPSBA, and test them on other classifiers. Table 2 reports ASR and CAD across datasets using GIN and SAGPool target models. Since AUC is model wodel-independdent, it is omitted. Results show that DPSBA maintains high ASR and low CAD across architectures, demonstrating strong transferabilityy even when using a simple surrogate model. Meanwhile, we observe counterintuitive phenomenon. A comparison of the experimental results on the AIDS and PROTEINS full datasets in Table and Table reveals that the ASR is higher when the surrogate model differs from the actual model than when they are identical. We provide a detailed discussion of this matter in Appendix E.6
GCN the surrogate model generate triggers
4.2.3 Anomaly Stealth Analysis
To show the anomaly stealthiness of DPSBA, we first visualize the anomaly score distributions of clean and backdoor graphs on all datasets in Figure? 3 The distributions show strong overlap, indicating that DPSBA-generated triggers exhibit minimal anomaly and are hard distinguish from clean samples. This is largely attributed to the use of clean-label constraints and adaptive optimization. To further assess robustness across detectors, we evaluate DPSBA under multiple anomaly detection algorithms, including OCGIN [32] and GLocalKD [33 with results summarized in Table DPSBA consistently achieves low AUCs and, notably, GLocalKD fails to detect most triggers, confirming the strong stealth of DPSBA across detection methods. Beyond anomaly detection, we examine randomized subsampling K L4, a standard defense strategy that randomly removes subgraphs during training.
Table 3: Performance (AUC% of different anomaly detection models
Models
PROTEINS full
AIDS
FRANKENSTEIN
OCGIN GLocalKD
55.19
86.52
72.12
50.24
31.46
46.57
SIGNET
60.11
72.65
68.96
As shown in Figure 4 a), DPSBA maintains high ASR despite this defense, thanks to its compact
8

---

trigger size and dual embedding in structure and features, making the trigger difficult to eliminate via sampling.
200
30
30
Dodaki Grople
Freguency
150
Frequency
20
Prequency
100
-5
10-
50-
3.0
3.5
4.0
4.5
5.0
5.5
1.5
2.0
2.5
5.0
3.5
4.0
4.5
1.5
2.0
2.5
3.0
3.5
4.0
Anomaly score
Anomaly score
Anomaly score
(a) FRANKENSTEIN
(b) ATDS
PROTEINS full
Figure 3: Anomaly distribution visualization
We also test anomaly-basen train- ing data filtering. Taking AIDS as an example, we use SIGNET to remove the top 5% anomalous samples before training. As Fig- (b) shows, DPSBA remains robust, suffering minimal ASR drop even when most poisoned samples are detected. In contrast, previous methods show sigmifi- cant degradation. This highlights a key insight: existing detection strategies, while effective at identifying poisoned data, remain insufficient to fully prevent backdoor success due to the low sample requirement for trigger activation. More proactive and robust defenses are needed to counter stealthy attacks like DPSBA.
100
58-
ASR1%)
68
ASR(%)
PROTEINS JoBl AIDS FRANKENSTIIN
1.8--8
1.17
6TA
Modf DPNRR
(a) Randomized Subsampling
(b) Data Filtering
Figure 4: Attack performance under defense
4.3 Ablation Study
To evaluate the role of each component in DPSBA, we conduct ablation experiments on PROTEINS_Ii full and AIDS by removing one module at a time: DPSBA/S (w/o hard sample selection). DPSBA/N (w/o position selection), DPSBA/F (w/o feature generator), DPSBA/T (w/o topology generator), and DPSBA/OD (w/o adversarial training), with results shown in Table Note: The FRANKENSTEIN dataset is highly sensitive to attribute perturbations, where even small feature changes can lead to high ASR and pronounced anomaly. As discussed in Section 4.2.1, we apply early stopping to the feature generator on this dataset; thus, it is excluded from the ablation study.
Table 4: Results of the ablation experiments (%)
PROTEINS full
AIDS
Model
ASR
CAD
AUC
ASR
CAD
AUC
DPSBA
73.93
4.62
60.11
94.76
2.38
72.65
DPSBA/S
70.98
3.57
60.24
91.32
2.09
72.60
DPSBA/N
70.74
4.53
58.97
93.67
2.31
71.26
DPSBA/F
71.80
4.96
59.01
85.67
2.40
67.26
DPSBA/T
69.08
3.71
54.73
93.66
2.91
71.41
DPSBA/OD
90.88
4.90
90.23
99.46
3.54
93.72
Removing the sample or location selection module (S/N) slightly reduces ASR, confirming their effectiveness in identifying vulnerable graph regions. Excluding either generator (F/T) significantly degrades ASR but slightly improves AUC, suggesting that targeting both topology and features is essential for strong attacks, while single-aspect perturbation introduces fewer anomalies. The relative importance of these attributes varies across datasets, indicating that under strict stealth constraints, selectively optimizing one may be preferable. DPSBA/OD achieves the highest ASR but suffers the worst AUC, highlighting the importance of adversarial training for stealth. All other variants maintain CAD within 5%, showing minimal impact model performance. Overall, the full DPSBA provides the best trade-off between effectiveness and stealth, with adversarial training enhancing detectability resistance and other modules improving attack strength.

---

4.4 Impact of the Loss Weights a and B
To control the anomaly level of injected triggers, DPSBA employs adversar- ial training with two loss weights: a for structural anomalies and B for fea- ture anomalies. This experi- ment investigates how vary- ing these weights affects the trade-off between attack effectiveness and stealth. Specifically, we vary a and from 0.1 to 100 in the joint loss formulations (Equations] and and observe the corresponding changes in attack success rate (ASR) and anomaly detectability (AUC). Results are shown in Figure 3 Overall, both ASR and AUC exhibit downward trend as and B increase. Larger weights impose stronger anomaly constraints, limiting the model's aggressiveness and thereby enhancing stealth. However, the rate of decline differs between and reflecting their distinct effects on structural and feature-based anomaly regularization, respectively. This suggests the two parameters can be tuned independently to suit dataset-specific characteristics. Importantly, when a and exceed a certain threshold, AUC stabilizes, indicating diminishing returns from further increasing anomaly penalties. This plateau signals that stealth constraints have been effectively enforced. At this point, DPSBA achieves a favorable balance between high ASR and low AUC. This analysis provides practical guidance for tuning a and based on peplicatioo-specifffe requirements: small values favor stronger attacks, while larger values improve stealth, helping practitioners achieve optimal trade-offs on different datasets.
AUC (%)
100
100
ASR
ASe
90
80
0.1
0.1
0.1
1
0.1
10
10
1
10
10
50
50
50
50
100100
100100
Figure 5: Parametric analysis of a and |
5 Conclusion
In this paper, we present DPSBA, a clean-label backdoor framework tailored for graph classification. Unlike prior work that relies on out-of-distribution triggers, semantic label flipping, or manually designed patterns, DPSBA learns in-distribution triggers directly from target-class graphs via a joint optimization process. The framework integrates clean-label attack mechanism with anomaly-awan adversarial training, optimizing both attack effectiveness and stealth. Specifically, it employs struc- tural and feature-level discriminators to minimize detectable deviations while preserving semantic consistency. Extensive experiments on diverse graph benchmarks and architectures demonstrate that DPSBA consistently achieves high attack success rates (ASR), low anomaly detection scores (AUC), and negligible clean accuracy drop (CAD). These results validate that DP$BA achieves a favorable balance between stealth and attack potency, outperforming existing baselines in both effectiveness and detectability. Our findings highlight the practicality of stealthy, distribution- preserving backdoor attacks real-world graph learning scenarios.
Limitations. The clean-label constraint, while significantly enhancing stealth, may limit attack potency in scenarios with imbalanced class distributions or scarce target-class samples, where clean instances are insufficient to support effective trigger learning. Additionally, DPSBA operates under partial training data access assumption, which restricts its applicability to fully black-box scenarios test-time attacks where data access is available. Future work may investigate lightweight or coo-ctomat variants of DPSBA, explore adaptation to broader graph settings such as heterophilic dynamic graphs, and develop theoretically grounded defenses capable of detecting distributionn-presrvving triggers.
6 Acknowledgments
This work was supported by the National Natural Science Foundation of China (No. 62302333, No. 92370111, No. 62272340, No. 62422210, No. 62276187 and No. 62502065) the Open Research Fund from Guangdong Laboratory of Artificial Intelligence and Digital Economy (SZ.) (No. (ML-KF-24-16) and Hebei Natural Science Foundation (No. F2024202047).
10

---

References
[1] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang. and Philip Yu. A compre- hensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1))4-22, 2020.
[2] Wenqi Fan, Yao Ma, Qing Li, Yuan He, Erie Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The world wide web conference, pages 417-426, 2019.
[3] Chen Gao, Xiang Wang, Xiangnan Hc, and Yong Li, Graph neural networks for recommender system. In Proceedings of the fifteenth ACM international conference on web search and data mining, pages 1623-1625, 2022.
[4] Oliver Wieder, Stefan Kohlbacher, Mélaine Kuenemann, Arthur Garon, Pierre Ducrot, Thomas Seidel, and Thierry Langer. A compact review of molecular property prediction with graph neural networks. Drug Discovery Today: Technologies, 37:1-12, 2020.
[5] Ziyang Liu, Chaokun Wang, Hao Feng, and Ziyang Chen. Efficient unsupervised graph embedding with attributed graph reduction and dual-level loss. IEEE Transactions on Knowledge and Data Engineering, 36:8120-4 11882208134, 8134, 2024.
[6] Hangfan Zhang, Jinghui Chen, Lu Lin, Jinyuan Jia, and Dinghao Wu. Graph contrastive backdoor attacks. In International Conference on Machine Learning, pages 40888-40910. PMLR, 2023.
[7] Enyan Dai, Minhua Lin, Xiang Zhang, and Suhang Wang. Unnoticeable backdoor attacks on graph neural networks. In Proceedings of the ACM Web Conference 2023, pages 2263 0263-2273,222 2023.
[8] Bingdao Feng. Di Jin, Xiaobao Wang, Fangyu Cheng. and Siqi Guo. Backdoor attacks unsupervised graph representation learning. Neural Networks, 180: 106668, 2024.
[9] Yang Chen, Zhonglin Ye, Haixing Zhao, and Ying Wang. Feature- graph backdoor attack in the node classification task. International Journal of Intelligent Systems, (1:41188888 2023.
[10] Xiao Yang. Gaolei Li, Chaofeng Zhang. Meng Han, and Wu Yang. Pereba: Persistent clean-label backdoor attacks on semi-supervised graph node classification. In A/Safery/SafeRll.e ICCAI, 2023.
[11] Jiazhu Dai and Haoyu Sun. A backdoor attack against link prediction tasks with graph neural networks. arXiv preprint arXiv:2401.0266 2024.
[12] Yixin Liu, Kaize Ding, Qinghua Lu, Fuyi Li, Leo Yu Zhang, and Shirui Pan. Towards self-interpretable graph-level anomaly detection. Advances in Neural Information Processing Systems, 36:8975-8987, 2023.
[13] Zaixi Zhang, Jinyuan Jia, Binghui Wang, and Neil Zhenqiang Gong. Backdoor attacks to graph neural networks. In Proceedings of the 26th ACM symposium on access control models and technologies, pages
15-26, 2021.
[14] Zhaohan Xi, Ren Pang, Shouling Ji, and Ting Wang. Graph backdoor. In 30th USENIX security symposium (USENIX Security 21), pages 1523-1540, 2021.
[15] Haibin Zheng. Haiyang Xiong, Jinyin Chen, Haonan Ma, and Guohan Huang. Motif-hackdoor: Rethinking the backdoor attack on graph neural networks via motifs. IEEE Transactions on Computational Social 2023.
Systems, 11(2):2479-244
[16] Zhiwei Zhang, Minhua Lin, Enyan Dai, and Suhang Wang. Rethinking graph backdoor attacks: listributionn-peeerviin perspective. KDD '24, page 4386-4397, New York, NY, USA, 2024, Association for Computing Machincry.
[17] Yinghua Gao, Yiming Linghui Zhu, Dongxian Wu, Yong Jiang, and Shu Tao Xia. Not samples are born equal: Towards effective clean-label hackdoor attacks. Pattern Recognition: The Journal of the Pattern Recognition Society, 2023.
[18] Jing Xu, Minhui Xue, and Stjepan Picek. Explainability- backdoor attacks against graph neural networks. In Proceedings of the 3rd ACM workshop on wireless security and machine learning, pages 31-36, 2021.
[19] Huiwei Wang, Tianhua Liu, Ziyu Sheng, and Huaqing Li. Explanatory subgraph attacks against graph neural networks. Neural Networks, 172:106097, 2024.
[20] Itay Hubara, Mathieu Courbariaux, Daniel Soudry, Ran El-Yani,, and Yoshua Bengio. Binarized neural networks. Advances in neural information processing systems, 29, 2016.
[21] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Gruph Representation Learning and Beyond (GRL+ 2020), 2020.
[22] Karsten M Borgwardt, Cheng Soon Ong. Stefan Schönauer, SVN Vishwanathan, Alex J Smola, and Hans- Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, (xxxppp_)xx477-566 2005.
11

---

[23] Ryan Rossi and Nesreen Ahmed. The network data repository with interactive graph analyties and visualization. In Proceedings of the AAAI conference artificial intelligence, volume 29, 2015.
[24] Francesco Orsini, Paolo Frasconi, and Luc De Raedt. Graph invariant kemels. In Proceedings of the rwenty-fourth international joint conference artificial intelligence, volume 2015, pages 3756- 3762, 2015.
[25] Karsten M. Borgwardt, Cheng Soon Ong. Stefan Schönauer, S. V. N. Vishwanathan, Alex Smola, and Hans- Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(1):47-56, January 2005.
[26] Ida Schomburg. Antje Chang, Christian Ebeling, Marion Gremse, Christian Heldt, Gregor Huhn, and Dietmar Schomburg. Brenda, the enzyme database: updates and major new developments. Nucleic acids research, 32(suppl 1):D433-D433, 2004.
[27] Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On early stopping in gradient descent learning. Constructive approximation, 26(2):289 315, 2007.
[28] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[29] Keyulu Xu, Weihua Hu, Jure Leskovec. and Stefanie Jegelka. How powerful are graph neural networks?
In International Conference Learning Representations. 2019.
[30] Junhyun Lee, Inycop Lec, and Jacwoo Kang, Sclf-attention graph pooling. In International conference on machine learning, pages 3734-333333 1444-333..313 pmlr, 2019.
[31] Yili Wang. Yixin Liu, Xu Shen, Chenyu Li, Rui Miao, Kaize Ding, Ying Wang, Shirui Pan, and Xin Wang. Unifying unsupervised graph-level anomaly detection and out-of-distribution detection: A benchmark. In The Thirteenth International Conference on Learning Representations, 2025.
[32] Lingxiao Zhao and Leman Akoglu. On using classification datasets to evaluate graph outlier detection: Peculiar observations and new insights. Big Data, 11(3):151-180, 2023.
[33] Rongrong Ma, Guansong Pang, Ling Chen, and Anton van den Hengel. Deep graph-level anomaly detection by glocal knowledge distillation. In Proceedings of the fifteenth ACM international conference on web search and data mining, pages 704-714, 2022.
[34] Zhiwei Zhang, Minhua Lin, Enyan Dai, and Suhang Wang. Rethinking graph backdoor attacks: A distribution- preserving perspective. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 4386-4397, 2024.
[35] Kaiyang Wang, Huaxin Deng, Yijia Xu, Zhonglin Liu, and Yong Fang. Multi-target label backdoor attacks graph neural networks. Pattern Recognition, 152:1, 2024.
[36] Xiangyu Zhao, Hanzhou Wu, and Xinpeng Zhang. Effective backdoor attack on graph neural networks in spectral domain. IEEE Internet of Things Journal, 11(7):2212--21111 14, 2023.
[37] Haibin Zheng, Haiyang Xiong, Haonan Ma, Guohan Huang, and Jinyin Chen. Link-backdoor: Backdoor attack on link prediction via node injection. IEEE Transactions Computational Social Systems, 11()):881611831, 2023.
[38] Ziyang Liu, Chaokun Wang, Liqun Yang. Yunkai Lou, Hao Feng, Cheng Wu, Kai Zheng, and Yang Song. Incorporating dynamic temperature estimation into contrastive lcarning graphs. In 2024 IEFE 40th International Conference on Data Engineering (ICDE), pages 2889-2903, 2024.
[39] Ziyang Liu, Chaokun Wang, and Cheng Wu. Graph contrastive learning with reinforcement augmentation. In Kate Larson, editor, Proceedings of the Thirty-Third International Joins Conference on Artificial Intelli- gence, IJCAI-24, pages 2225-2233, International Joint Conferences on Artificial Intelligence Organization, 2024. Main Track.
[40] Lilas Alrahis, Satwik Patnaik, Muhammad Abdullah Hanif, Muhammad Shafique, and Ozgur Sinanoglu. Poisonedgnn: Backdoor attack on graph neural networks- based hardware security systems. IEEE Transac- tions on Computers, 72(10)22822-888 2023.
[41] Xiaoting Lyu. Yufei Han. Wei Wang, Hangwei Qian, Ivor Tsang, and Xiangliang Zhang, Cross-context backdoor attacks against graph prompt learning. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2094-2105, 2024.
[42] Jing Xu, Rui Wang, Stefanos Koffas, Kaitai Liang, and Stjepan Picek. More is better (mostly): On the backdoor attacks in federated graph neural networks. In Proceedings of the 38th Annual Computer Security Applications Conference, pages 684-698, 2022.
[43] Jing Xu, Stefanos Koffas, and Stjepan Picek. Unveiling the threat: Investigating distributed and centralized backdoor attacks in federated graph neural networks. Digital Threats: Research and Practice, 5(2):1 2024.
12

---

[44] Yu Sheng, Rong Chen, Guanyu Cai. and Li Kuang. Backdoor attack of graph neural networks based on subgraph trigger. In Collaborative Computing: Networking, Applications and Worksharing: 17th EAI International Conference, CollaborateCom 2021, Virtual Event, October 16-18, 2021, Proceedings. Part
17, pages 276-29666666 Springer, 2021.
[45] Haibin Tong. Huifang Ma, Hui Shen, Zhixin Li, and Liang Chang. Crucial rather than random: Attacking crucial substructure for backdoor attacks on graph neural networks. Engineering Applications of Artificial Intelligence, 136: 108966, 2024.
[46] Shuiqiao Yang, Bao Gia Doan, Paul Montague, Olivier De Vel, Tamas Abraham, Seyit Camtepe, Damith C Ranasinghe, and Salil S Kanhere. Transfcrable graph backdoor attack. In Proceedings of the 25th international sympoxium on research aftacks, intrusions and defensex, pages 321-332, 2022.
[47] Jiazhu Dai, Zhipeng Xiong, and Chenhong Cao. A semantic backdoor attack against graph convolutional networks. Neurocomputing, 600:128133, 2024.
[48] F Tramèr, D Bonch, A Kurakin, Goodfellow, N Papernot, and McDanicl. Ensemble adversarial training: Attacks and defenses. In 6th International Conference on Learning Representations, ICLR 2018- 2018-Conference Truck Proceedings, 2018.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In abstract, outline the problems we have solved and the contributions we have made. The claims made match the theoretical and experimental results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 long 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]
Justification:
In conclusion, we introduce the limitations of the method and the reasons that cause them.
Guidelines:
The answer NA means that the paper has 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 a 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 (c.g.. independence assumptions, noiseless settings, model cell-speciiiaatinn. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of 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 faimesss.
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 proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification:
The assumptions in the paper are clearly stated in the statement of theorems.
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 in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should 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
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification:
We clearly introduce the model framework and datasets, and provide the
parameters.
Guidelines:
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, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make 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 to replicate the results, access to a hosted model (e.g.. 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 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) the contribution is 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 or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We submit the code and data, and introduce the data processing method.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://niis.. cc/
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 (c.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 NeurIPS code and data submission guidelines (https
//nips //iips.cc/pill wttpcccpppppppppeeeeeeeeeeeeeeee httpe//guuddeeeeeeueubiisssssss /Cc////oddiiisssseeeeeee ssiiiiiiiiyiyyyyy 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).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
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 understand the results?
Question:
Answer: [Yes]
Justification: In the experimental section and appendix, we provide detailed information about the training and testing details
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We conduct experiments ten times and compute the average value.
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 with given experimental conditions).
16

---

The method for calculating the error bars should be explained (closed form formula, call 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 the standard error of the mean.
It is OK to report 1-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 figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in 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 of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide sufficient information on the computer resources in appendix, including GPU and CPU.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 the paper conform, in every respect, with the NeurlPS Code of Ethics atttps://neuriie http://wwwwrp.accooooo./cccccaaa
Answer: [Yes]
Justification:
We comply with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have 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 or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss the positive impact of DPSBA on related fields in Appendix.
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 no societal impact why the paper does not address societal impact.
17

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 not 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 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We did not use data or models that have a high risk of misuse.
Guidelines:
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 to 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 is challenging, and many papers do not require this, but we 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 cite the original paper that produced the code package or dataset.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package 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 (e.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 package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
18

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if 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:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl 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
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
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 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 the NeurIPS Code of Bthies, workers involved in 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 or 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
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.
Depending on 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 NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
19

---

16. Declaration of LLM usage
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, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: We use LLM only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy battps://neurre /c/Coonfreences222255 for what should or should be described.
20

---

A Anomaly Issues in Graph Classification Attacks
To demonstrate that backdoor graphs in graph classification tasks tend to exhibit clear out-of- distribution (OOD) characteristics, we conduct anomaly detection experiments on the AIDS dataset [23 Specifically, we use the SIGNET algorithm [2] to evaluate the statistical anomaly of poisoned samples generated by representative backdoor attack methods, including ER-B [3]. GTA [4, and Motif [[S]. comparing them against clean training samples. As shown in Table A5 we adopt AUC as the evaluation metric for anomaly detection, which reflects how well a detector can distinguish clean graphs from anomalous ones. The results show that most existing methods result in extremely high AUC scores, often exceeding 90%, highlighting that backdoor samples are statistically distinguishable and exhibit significant anomalies. This stands in contrast to node-level backdoor attacks, where the GNN's local message passing can help diffuse trigger signals and reduce detectability.
LIA [8]
Table A5: Performance of backdoor attack methods on the AIDS dataset
Backdoor Attack Method
Metrics
ER-B
LIA
GTA
Motif
Motif-S
ASR(%)
85.38
85.49
93.21
92.69
56.08
AUC(%)
98.08
97.22
99.34
99.71
89.43
CAD(%)
4.53
3.80
5.14
4.12
4.03
Structural Deviation. Backdoor models often exploit shortcut learning by associating rare subgraph triggers with the target class to enhance attack success. However, these triggers tend to deviate significantly from the natural graph distribution, making them easy to detect. Referring to the trigger selection strategy in Motif [15). we design comparison between two variants: (1) Motif uses the least frequent motif as the trigger, while (2) Motif-S adopts the most common motif in the AIDS dataset. As shown in Table A5 Motif achieves higher ASR due the strong signal of the rare trigger. However, this also results in extremely high AUC scores, indicating poor stealth. In contrast, Motif-S trades off some attack effectiveness for significantly improved stcalth, frequent motifs are naturally present in the dataset and thus harder for anomaly detectors to distinguish. This validates that trigger frequency directly influences the detectability of structural anomalies.
Table A6: Performance of clean label backdoor attack
Backdoor Attack Method
Metrics
ER-B
LIA
GTA
Motif
Motif-S
ASR(%)
37.11
57.62
91.88
84.37
1.80
AUC(%)
61.03
59.42
98.05
97.74
71.88
CAD(%)
4.33
3.78
4.92
4.24
4.13
Semantic Deviation. Label manipulation, commonly used in traditional backdoor attacks, intro- duces semantic inconsistency between the graph content and its assigned label, exacerbating anomaly. The success of such attacks relies on enforcing a co-occurrence between the trigger and target label, which is typically achieved by inserting the trigger into non-target-class samples and forcibly flipping their labels. This label tampering often results in category-level semantic conflict. To assess its effect, we further evaluate the same backdoor methods under clcan-label setting (i.c., without modifying labels). As shown in Table A6 while the AUC scores drop in all methods, indicating improved stealth, the ASR also drops significantly. This suggests that semantic consistency reduces the statistical footprint of the backdoor, but at the cost of attack success. In summary, label flipping enhances attack strength but induces additional semantic anomaly, making backdoor graphs more detectable.
These findings highlight two major anomaly sources in graph-level backdoor attacks: structural deviation from rare subgraphs and semantic inconsistency due to label tampering. This motivates the design of DPSBA, which aims to preserve distributional characteristies by avoiding both sources of anomaly.
21

---

B Related Work
B.1 General Graph Backdoor Attacks
Backdoor attacks constitute a class of adversarial attacks in which an attacker implants a hidden behavior, known as trigger mechanism, into the model during training. Once trained, the model behaves normally on clean inputs, maintaining high utility and stealth. However, when presented with an input containing a specific trigger pattern, the backdoor is activated and causes the model to misclassify the imput into attacker-specife target class. This property makes backdoor attacks particularly insidious in real-world deployments. In the graph domain, various works have explored backdoor threats in settings beyond standard graph classification. For node classification tasks, researchers have proposed attacks that inject malicious subgraphs or perturb node features to manipulate predictions. For example, Zhang al. (34 first investigated the stealthiness dimension of backdoor attacks on node classification, while Wang et al. [35] introduced multi-target attacks to expand adversarial flexibility. Zhao et (66 proposed spectral backdoor method by subtly altering the frequency domain of node features. For link prediction tasks, Zheng et al. [37 constructed triggers composed of fabricated nodes and target link pairs, whereas Dai al. [I] showed that even single-node triggers can influence link predictions. Other studies have expanded backdoor threats into more specialized domains. For example, Zhang et al. [ proposed the first attack on graph contrastive learning [38] 339, and Alrahis et al. [4] designed a hardware-level GNN backdoor mechanism. In the context of graph prompt learning. Lyu et [4] framed backdoor injection as a feature-collision optimization problem. Federated graph learning has also been explored: Xu et al. proposed two attack paradigms: distributed backdoor attack (DB and Centralized Backdoor Attack (CBA) [ targeting collaborative learning environments through data poisoning strategies. Although recent efforts have extended graph backdoor attacks to wide range of scenarios, the graph classification task remains the primary focus due to its foundational role in bioinformatics, chemistry, and cy cybersecurity. Its holistic graph-level nature presents both unique challenges and opportunities for backdoor research.
B.2 Backdoor Attacks against Graph Classification Tasks
Existing backdoor attack methods targeting graph classification can be broadly categorized into four groups based on their trigger generation strategies: (1) random pattern generation, (2) interpretability- based generation, (3) gradient-basee optimization, and (4) distribution
or search- based methods. Random Generation via Graph Distribution: Zhang et al. [1. first introduced backdoor attack against GNNs by randomly generating subgraphs using Erdös-Rényi (ER) models and inserting them as universal triggers into the training set. This demonstrated that fixed subgraph patterns can reliably activate backdoors in graph classification. Sheng et al. E further incorporated statistical characteristics of the dataset to create hybrid local-global trigger patterns, improving both the flexibility and efficacy of the attack. Explainability-Bass GNNExplainer to assess the importance of the node and identify the optimal injection sites, the least important or the most influential nodes, for the trigger subgraphs. This method emphasized the influence of structural semantics on model decisions and improved the stealthiness of trigger placement. Building on this idea, Wang et al. [9 proposed inserting explainable subgraphs as triggers. Tong et al. [45] took this further by identifying and replacing predictive substructures in graphs to construct semantically-aligen proposed GTA, a general and dynamic backdoor attack framework that learns subgraph triggers via bilevel optimization. Unlike fixed-pattern methods, GTA can adapt trigger structures to specific graph instances, enhancing attack flexibility and stealth. Similarly, Yang al. [46] developed TRAP, which perturbs graphs through medicnt-driver strategies to generate transfcrable, pattern-free backdoor triggers. Search-Based or Distributton-Aware Methods: Recent work has focused on designing triggers that better conform to data distributions. Dai et al. extended the semantic backdoor paradigm to GNNs, constructing triggers based on class-relevant node types and graph semantics. Zheng et al. [15] introduced a motif-based framework, where triggers are searched from statistically significant and frequently occurring subgraph structures. They proposed three strategies to enhance effectiveness and stealth: 1) Use of motifs that are absent in the dataset (maximal anomaly), 2) Use of motifs predominantly present in the target class (semantic bias), 3) Use of dense motif structures with high interconnectivity (amplified influence). This taxonomy reflects growing awareness that
Trigger Design: Xu et al. [18] leveraged
triggers. Cradient-Based Optimization Methods: Xi et [4
22

---

both attack efficacy and stealth must be co-optimized, especially as anomaly detection models are increasingly deployed for backdoor defense.
C Theoretical Analyses
C.1 Distributional Shift in Graph vs. Node-Level Attacks
To rigorously compare the detectability of backdoor triggers in graph vs. node classification, analyze the total variation distance (TV) under local subgraph perturbations.
Definition 1 (Total Variation Distance). Let Pg. Pa be the distributions of clean and poisoned graphs in a graph classification task, and Pv, Piv for node classification. The distributional shift is quantified by:
TV = TV(PG,
T TV(P.. Plv),
(9)
where TV distance is defined as:
1 TV(P,P') 2 //1 (p(()) ('()
(10)
Theorem (Lower Bound on Graph- Distributional Shift). Let N be the number of nodes in a graph, M the number of trigger nodes, and assume the trigger introduces local deviation
A = Merigger Mll1 in node features. Then the total variation distance of the graph-level distribution
sctisfies:
TVc 2 c. N with
A.
(11)
Proof. In graph classification, predictions are made based on aggregated global features (e.g.. mean pooling). Let μ be the average node embedding of clean graph, and Mrigger the embedding from trigger nodes. After injecting trigger subgraph size M, the poisoned graph has average feature:
M
M
1' =
1 +
N Muigger
N
Then the feature shift becomes:
l pll Menggeerr Mll M
Using Pinsker's inequality variant, which states:
TV(P, P*) 2 Epr Ep[x]]l1
we obtain:
M
M
TV& 2
7 Illl
1|11
||rigeer - M|l1 N c.
N
Remark (On Comparison with Node-Level TV). In node classification, the trigger affects only few nodes and their k-hop neighbors. Since predictions are localized, the overall distributional shift often less significant. Letting TV 5. M be heuristic approximation, note:
M N
TV
TVv, ifc 6.
This inequality holds when the graph-level aggregation amplifies the statistical impact of the trigger compared to node-local shifts.
Caution: The term TV and TV over different data domains (nodes graphs), and thus not directly additive:
M
We cannot claim: TVG TVv c N
Instead, we highlight the fact that graph-level shift lower bounds node-level shift under same perturbation size, and is strictly greater if the trigger induces global mean shifts.
23

---

Corollary 1 (Implication for Backdoor Stealth), Backdoor attacks graph classification inherently suffer greater distributional shift than on node classification. This makes graph-level triggers more detectable by anomaly detection models, motivating the need for distributionn-ressrvvii designs like DPSBA.
C.2 Trigger Distributional Detectability Bound
We now establish a lower bound connecting the detectability of backdoor samples to the statistical divergence between clean and poisoned data distributions.
Definition 2 (Total Variation Distance), Let P and P' be the distributions over clean and poisoned graphs. Then:
- (TA)-P((A]]) 1 2 (p(x)) p'(x)) dx,
('(,P)) = sup
(12)
ACG
where p(x), (x) are probability densities over 9, the space of all graphs.
Theorem (Lower Bound on AUC for Detecting Poisoned Graphs), Let s(-) be any score function used by binary anomaly detector to distinguish P and P', Then:
AU TV(P,P")
(13)
2
Proof. From hypothesis testing theory, the optimal binary decision rule achieves AUC:
AUC.pt [P(((x+)) s(x + TV(P,P")
2
where T. p P. Thus, detector can achieve lower AUC than this bound.
Corollary (Indistinguishabiiity at Low TV). IP, P') - 0, then:
AUC + 0.5,
implying poisoned graphs become statistically indistinguishuble from clean ones. Designing triggers that preserve common graph motifs or feature statistics helps satisfy this condition.
Implication. DPSBA minimizes the anomaly loss to reduce TVPP, achieving stealthy attacks even under statistical anomaly detection, as supported by the empirical histograms Fig.
D Algorithm of DPSBA
The DPSBA algorithm is detailed in Algorithm Initially, we train the surrogate model fo- using the clean dataset, initialize the relevant model parameters and select poisoning samples from the data whose class is the target class y/ (lines 1-3). From lines 4-8. We inject triggers into the poisoned sample GB. Lines 10-17 and lines 18-25 are topology generation stage and feature generation stage, respectively. The topology (feature) discriminator 0, (0,) and the generator Wa (wy) are alternately optimized and then update the surrogate model fe- with the current backdoor training set C".
E
Experimental Details
E.1
Datasets
The key statistics of the datasets are presented in Table E7
E.2
Metries
This section details the evaluation metrics used to assess both the effectiveness and stealthiness of backdoor attacks, including Attack Success Rate (ASR), Clean Accuracy Drop (CAD), and Area Under the Curve (AUC).
24

---

Algorithm DPSBA
Input: Datasets C, target label attack budgets M. maximum number of training epochs Output: Backdoor training set C". topology/feature generator parameters walwe
1: The model fe- is trained through the gradient V VeLtrain (C);
2: Randomly initialize the topology generator parameters wt, the feature generator parameters wy, the topology anomaly discriminator parameters 8, and the feature anomaly discriminator parameters Oy:
3: The poisoned samples GB are selected from C(vve] according to the confidence score ef calculated by Eq. (2):
4: for G E Gg do
5: According to the centrality calculated by deg(v)/(N 1), nodes with high degree centrality are pre-selected candidates Nean;
6: According to the importance score S calculated by Eq. injection positions are selected;
7: Using m(G;g) 9t) inject triggers in G;
8: end for
// Put trigger-embedded graph GB back into the dataset to form the backdoored dataset C'
9: while not converged yet do
10: while epoch epochs do
11:
Update 8 by gradient according to Eq.
12:
Update wi via gradient Vwr (Gy, (wi)) + aL (0) end while
(we))) according to Eq. 7 (G (Do,
(Do,
13:
14:
for G' E G' do
15:
Update G by m(::gt); end for
16:
17:
Update fo- by gradient VeLtrain(C")
18:
while epoch epochs do
19:
Update , by gradient according to Eq. 6
Update wy via gradient FurCurk (G (wy)) + 3c (Do, (G (w/))) according Eq.
20:
21:
end while
22: for G Gg do
23:
Update G by m(G; 9:); end for
25: Update for by gradient Vo VoLtrain(C")
end while
27: return C², Ws
Table E7: Datasets statistics
Datasets
PROTEINS full
AIDS
FRANKENSTEI ENZYMES
Number of graphs
1113
2000
4337
600
Avg. Number of nodes
39.06
15.69
16,90
32.63
Avg. Number of edges
72.82
16.20
17.88
62.14
Number of classes
2
2
Label distribution
663
[0], 450 [1]
400 [0], 1600 [1]
1936 [0], 2401 [1]
100 [1-6]
Target label
0
0
(1) Attack Success Rate (ASR): ASR quantifies the proportion of trigger-embedded graphs that are successfully misclassified into the target class. serves as the primary measure of attack effectiveness and is defined as:
ASR Number of successful attacks
(14)
Total number of backdoor trials
(2) Clean Accuracy Drop (CAD): CAD measures the performance degradation of the poisoned model on clean samples, indicating the stealthiness of the attack when the trigger absent. defined as the accuracy difference between clean model and the backdoored model clean test
25

---

Table E8: Model accuracy on a clean dataset
Model
Datasets
GCN
GIN
SAGPool
PROTEINS full
75.58
76.23
73.99
AIDS FRANKENSTEIN
98.64
98.92
98.26
60.81
64.32
62.75
set:
CAD ACC clean model
-ACC backdoor model:
(15)
where accuracy is calculated as:
1 N N
ACC
Σ I(0: vi),
(16)
with I(-) denoting the indicator function, Ys the predicted label, the ground-trun truth label, and N the number test samples.
Interpretation: A high ASR indicates effective attack performance, while a low CAD implies minimal disruption to normal prediction behavior, reflecting strong stealth.
(3) Area Under the Curve (AUC); To evaluate stealth from the perspective of anomaly detection, use the AUC score produced by anomaly detection model (e.g., SIGNET) trained clean graphs. AUC reflects the model's ability to distinguish backdoor samples from clean ones:
AUC = P(s(x+) > s(r-)),
(17)
where s(x) denotes the anomaly score of graph x, and x randomly selected anomalous and clean samples, respectively.
Interpretation:
AUC + 1.0: the detector perfectly separates anomalies from clean data, i.c., low stealth.
AUC + 0.5: the detector cannot distinguish between backdoor and clean samples,icc., high stealth.
AUC 0.5: the detector misled, incorrectly prioritizing clean samples as more anomalous.
Goal: An effective backdoor should aim for an AUC as close as possible to 0.5, indicating that the anomaly introduced by the trigger is indistinguishable from natural variations in clean data, thus enhancing stealth against detection models.
E.3
Accuracy Graph Classifiers on Clean Data
Table ES illustrates the accuracy of three different graph classifiers the clean datasets.
E.4 Impact of the Poisoning Rate
To investigate how the poisoning rate influences DPSBA's performance, we evaluate the variation of attack success rate (ASR) and clean accuracy drop (CAD) under different poisoning rates. Since the anomaly level of the trigger determined by its structural and feature design rather than injection frequency, we focus here on ASR and CAD as shown in Figure ВБ] As the poisoning rate increases from 1% to 7%, ASR consistently improves across all datasets, confirming that injecting more poisoned samples strengthens the backdoor effect. However, the growth rate of ASR gradually slows, indicating diminishing returns. Meanwhile, CAD shows slight upward trend with higher poisoning rates, but remains below 5% in all cases, demonstrating that DPSBA maintains high stealth even under increased poisoning levels. This result suggests that while increasing the poisoning rate enhances attack effeectiveness, DPSBA can still preserve stealthiness due to its clean-label and anomaly- design. Practitioners may adjust the poisoning budget balance performance and resource cost without significantly sacrificing stealth.
26

---

PROTEINS full
AIDS
FRANKENSTEIN
100
1
90
80
2
KST
70
3
60
1%
3%
5%
7%
1%
5% Poisoning Rute
3%
Poisoning Rate
Figure E6: The impact of the Poisoning Rate
E,5
Impact of Trigger Size
PROTEINS full
AIDS
FRANKENSTEIN
90
100
ASR (%)
80
90
80
CAD
70
70
60
60
50
5
5
3
5 Trigger Size
6
Trigger Size
Trigger Size
Figure E7: The impact of trigger size
We further examine the effect trigger size on the performance of DPSBA. As shown in Figure E7 increasing the size of the trigger leads consistent improvement in attack success rate (ASR) across all datasets. This expected, as larger triggers introduce stronger perturbations to the graph's 'ss topology and features, making it easier for the model associate the injected pattern with the target label. However, this enhancement in effectiveness comes at the cost of stealthiness. As the size of the trigger increases, the level of anomaly, that larger triggers deviate more from the normal graph distribution, thus being more detectable by anomaly detection models. Still, the AUC values remain within an acceptable range (mostly below 80%), preserving a reasonable degree of stealth. Moreover, the clean accuracy drop (CAD) exhibits general upward trend with increasing trigger size, though it remains under 5% most cases. This suggests that even larger triggers do not significantly impair the model's generalization performance on clean data. In summary, trigger size presents a clear trade-off: larger triggers yield stronger attacks but increase detectability, while smaller ones offer greater stealth at the cost of ASR. DPSBA supports flexible adjustment of this trade-off based on practical requirements.
measured by the AUC, also increases. This indicates
E.6 Higher ASR in Cross-Architecture Transfer Settings
We explain this counterintuitive phenomenon from three perspectives: model expressiveness, trigger generalizability, and dataset characteristics.
(1) Model Expressiveness vs. Overfitting: GIN and SAGPool are more expressive than GCN. GIN is theoretically equivalent to the Weisfeiler-Lehman test, capable of distinguishing fine-grained substructures and SAGPool uses self-attention to highlight global structures most relevant for classifi- cation. These powerful models, when used surrogates, tend to learn highly specialized, structure- sensitive triggers. While effective on the surrogate model itself, such triggers are prone to overfitting and may fail to generalize to unseen samples or minor parameter shifts. This aligns with prior observations [48 that stronger surrogates often overfit their own gradients, reducing perturbation transferability.
(2) GCN-Trai Trained Triggers Are More Transferable: GCN, with its smoother message passing and lower expressiveness, tends to learn broader and more transferable trigger patterns. These triggers may achieve lower ASR on GCN itself (as seen in Table []. but generalize better when transferred to expressive models like GIN or SAGPool, which are more sensitive to subtle perturbations and thus amplify the attack effect.
27

---

(3) Dataset-Specific Factors Amplify the Effect: In the AIDS dataset, molecular graphs are small but structurally complex. Local substructures (e.g. functional groups) are erucial, making GIN highly sensitive to local changes caused by transferred triggers. In PROTEINS full dataset, graphs are larger and denser (node-edge ratio R 1:1.86), favoring models like SAGPool that focus on global structure. GCN's triggers are naturally aligned with such global perturbations, which SAGPool tends to emphasize.
F Time Complexity Analysis
We analyze the training time complexity of DPSBA by accounting for graph sparsity and the dimensionality of node features. The framework consists of three main stages: (1) hard sample selection; (2) trigger location selection and initialization; and (3) adversarial optimization of the topology and feature generators. Let denote:
C: number of graphs in the clean training set
N: average number of nodes per graph
d: average degree of nodes (assumes sparse graph, i.e., d < N)
F: node feature dimension
B: the total number of poisoned graphs
E: total number of adversarial training epochs
1) Hard Sample Selection. For each graph in the target class, we compute its confidence score with respect to the target label using a forward pass through the surrogate model. Assuming each node aggregates information from d neighbors, and node features F-dimensional, the per-graph complexity is O(N d F), leading to (C N. d F). This term reflects the initial overhead of scoring and ranking all graphs identify low-confidence (hard) samples.
2) Trigger Location Selection. For each selected hard sample, DPSBA computes node importance via a deletion-based interpretability scheme. Each candidate node requires one additional forward pass through the GNN after node removal. If we sample candidates per graph, the cost becomes Ol N d F). Since k is fixed and small (k s 2.M), this step scales O N d- F). Thus, steps (1) and (2) share the same leading complexity.
3) Trigger Optimization. In each epoch, we optimize the topology and feature generators to simultaneously (a) maximize attack loss and (b) minimize anomaly detection confidence through adversarial discriminators (GCN and MLP). Each poisoned graph in the batch undergoes GCN- based classification and gradient updates. Assuming adversarial training lasts E epochs, the total cost becomes O(E B N d. F). This dominates the runtime due to repeated gradient steps.
Overall Complexity. Combining the above three stages, the total training complexity of DPSBA is: OCC- N. F-FFF--F--- B- N dd F) This expression reveals linear scalability with respect to the number of nodes, average degree, and feature dimension. The first term corresponds one-time sampling and location inference; the second reflects iterative adversarial training. As the number of poisoned graphs (B) and training epochs (E) are relatively small, DPSBA maintains practical efficiency under sparse graph assumptions. DPSBA achieves favorable balance between attack efficacy and efficiency: its overall complexity is comparable to standard GNN training pipelines while introducing minimal overhead. Moreover, by leveraging sparse message passing and modular optimization, DPSBA remains scalable to real-world graphs with thousands of nodes and high-dimensional features.
In addition, we benchmark the actual training time of DPSBA and compare it with several representa- tive baselines (ER-B. LIA. GTA, and Motif) on the largest dataset, FRANKENSTEIN The results are reported in Table F9 All experiments are conducted on machine equipped with 14-core Intel 17-12700H CPU, an NVIDIA GeForee RTX 3060 GPU (12 GB), and Windows 11 (version 23H2). As shown in the table, DPSBA achieves the highest ASR (99. (998 while maintaining the lowest CAD (1.83%) and AUC (73.46%). demonstrating a superior balance between attack success and stealth. Although DPSBA incurs slightly more training time compared to the lightest baseline (ER-B), the overhead is acceptable given the substantial gains in performance. Notably, our framework integrates an storp-- mechanism during adversarial training, which adaptively terminates optimization once the attack objective converges. This not only reduces computational overhead but also avoids unnecessary overfitting, making DPSBA both effective and time-efficient.
28

---

Table F9: Training Time and Attack Performance on FRANKENSTEIN.
Metries
ER-B
LIA
GTA
Motif
Ours
ASR (%)
92.06
82.63
95.23
84.56
99.84
CAD (%)
3.60
2.35
1.95
2.44
1.83
AUC (%)
85.73
76.15
91.06
87.54
73.46
Time (s)
210
261
376
239
281
G Diseussion of Inductive Graph Classification Setting
While our current work focuses on the transductive graph classification setting, we believe that several key components DPSBA have promising potential to extend the inductive regime. particular: 1) The feature generator operates based on localized structural and attribute information at the trigger injection site, and 2) The distribution-awarr discriminators regularize stealth on per-graph basis through adversarial training. Both modules are graph-local in nature and do not rely inter-graph interactions train-test graph overlap, making them amenable to inductive settings where new test graphs unseen during training. That said, certain components, such the hard sample selection module, currently assume access to sufficient examples of the target class, which poses challenges in few-shot scenarios. Adapting this component to work under strong data constraints (e.g.. via meta-learning or class-agnostic proxy supervision) a meaningful direction for future work.
H Broader Impacts
This work reveals that even under clean-label settings, graph classification models remain highly vulnerable to stealthy backdoor attacks. By exposing this underexplored threat, our method highlights the limitations of existing defenses and underscores the need for more robust anomaly detection and training strategies. While our approach may be misused, we release it to raise awareness and promote the development secure graph learning systems critical domains such bioinformatics, finance, and cybersecurity.
29


Reviews:
[{"review_id": "VChrH736q9", "reviewer": "Reviewer_ePuR", "summary": "This paper introduces DPSBA, a novel clean-label backdoor framework. DPSBA uniquely employs adversarial training, guided by anomaly-aware discriminators, to learn in-distribution triggers. By effectively suppressing both structural and semantic anomalies, DPSBA achieves high attack success rates while significantly enhancing stealth. Extensive experiments on real-world datasets demonstrate that DPSBA strikes a superior balance between effectiveness and detectability compared to existing state-of-the-art baselines.", "questions": "1.\tUniversal Trigger： The method focuses on generating a trigger for each individual sample. Have you explored the possibility of developing a universal trigger that is transferable across different samples? Demonstrating the feasibility or discussing the challenges of a more transferable trigger would elevate the contribution and applicability of your work.\n\n2.\tProblem Hardness and Design Rationale：Please articulate why this problem is challenging and the specific insights guiding your method design choices. This would justify your approach and strengthen the originality.\n\n3.\tComprehensive Experimental Analysis：There is only the result of a 5% poisoning rate. What are the results if this rate is lowered? For the PROTEINS_full dataset, the Attack Success Rate (ASR) ranges from 73% to 94%. Can you investigate at what poisoning rate the ASR on PROTEINS_full approaches the 98%-99% achieved on the AIDS or FRANKENSTEIN datasets?\n\nEvaluations on more benchmark datasets. \n\nDiscuss the possibility of generalizing the proposed attack on other graph-relevant tasks", "limitations": "While the authors discuss the methodological limitations of their work, they do not address its potential negative societal impact.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: \n\n+Paper structure: The paper is well-structured. It first demonstrates how existing methods suffer from distribution shifts, which motivates the proposed approach and experimental validation. This makes the paper easy to follow and understand.\n\n+Writing: The writing is clear and concise.\n\nWeaknesses\n\n-Methodology：The proposed method generates a trigger for each individual sample. There is no discussion about the transferability of these sample-specific triggers across different samples or the potential for developing a universal trigger. Addressing these would enhance the practical utility and its contribution.\n\n-Originality：The paper leverages existing methods to achieve positive results for the task, the novelty appears limited. To strengthen its originality, the authors could highlight specific insights or unique theoretical analysis.\n\n-Experiment：\nThe experiments only consider graph classification tasks and three datasets. Is this possible to generalize to other graph-relevant tasks and more benchmark datasets, including real-world ones. \n\nThe evaluation does not cover the impact of crucial parameters such as poisoning rate and trigger magnitude on the attack performance.", "was_revised": true, "final_justification": "The response has addressed my questions, and I raise my score from 3 to 4 accordingly.", "rebuttal": "## **Response to Comments on Trigger Transferability and Universal Trigger Design (Weaknesses-Methodology & Question 1)**\n\nWe thank the reviewer for raising this insightful question regarding the feasibility of **universal triggers** and the transferability of our sample-specific design.\n\nBut currently, the existing graph backdoor methods, both generative  (e.g., GTA) and search-based (e.g., Motif), adopt **sample-specific triggers**. This is primarily due to the **heterogeneous nature of real-world graph data**, where node attributes and topological structures vary significantly across samples. A trigger that appears inconspicuous in one graph may be highly anomalous in another.\n\nOur method follows this paradigm but further **incorporates anomaly-aware regularization** to explicitly enforce stealth during trigger generation. In contrast, prior sample-specific methods like GTA focus primarily on effectiveness and do not explicitly address detectability.\n\nWe agree that universal triggers could improve training efficiency and generalization, and are highly desirable in practical deployments. However, designing such triggers poses substantial challenges:\n\n- **Structural & Distributional Variability**: In graph-level classification, the diversity across samples makes it difficult to craft a fixed trigger that maintains both semantic relevance and distributional alignment across the dataset.\n- **Stealth vs. Effectiveness Trade-off**: As shown in Table 1,  fixed triggers such as **Motif** achieve high ASR (e.g., 92.69% on AIDS under GCN), but suffer from extremely high anomaly scores (AUC = 99.71%). When stealth is improved by using more frequent motifs (Motif-S), the ASR drops significantly (to 56.08%). This highlights the inherent trade-off between universality and stealth.\n\nWe appreciate the reviewer’s suggestion and agree that developing **universal or class-conditional trigger generator** that balance **generalizability and stealth** is a promising and underexplored research direction.  We will add this discussion to the revised version of our paper and are enthusiastic to pursue this direction in future work. We thank the reviewer again for this valuable feedback.\n\n---\n\n## **Response to Comments on Originality and Problem Hardness (Weakness – Originality & Question 2)**\n\nWe thank the reviewer for highlighting the importance of originality.\n\nGraph-level backdoor attacks are far less studied, especially under **clean-label** and **distribution-preserving** constraints. Existing works either use hand-crafted triggers (e.g., Motif, LIA) or generate triggers without modeling stealth properties (e.g., GTA), which leads to high detectability and limited robustness. \n\nIn **Appendix C.1**, we theoretically show that graph-level attacks cause larger distributional shifts than node-level ones, making stealth significantly harder. This arises from two challenges:\n\n- **Structural deviation**: Rare subgraph triggers diverge from clean graph distributions and are easily flagged by detectors;\n- **Semantic deviation**: Label flipping in non-clean-label settings breaks the consistency between structure and label, further increasing anomaly scores.\n\nThese highlight a core dilemma: high-ASR triggers are often less stealthy, and stealthier ones tend to be ineffective.\n\nTo address this, we propose **DPSBA**, which is (to our knowledge) the first to integrate:\n1. A **clean-label pipeline** that avoids semantic inconsistency;\n2. **Anomaly-aware adversarial training** using distribution-aware discriminators on structure/features;\n3. A **model-agnostic theoretical bound** (Appendix C.2) linking the total variation distance between clean and poisoned distributions to anomaly detectability (AUC).\n\nTogether, these designs enable DPSBA to effectively balance stealth and success—an underexplored but critical problem in graph-level backdoors.\n\nWe appreciate the opportunity to clarify this and will improve the emphasis on novelty in the revision.\n\n---\n\n## **Response to Comments on Experimental Scope and Generalizability (Weaknesses – Experiment & Final Two Questions)**\n\nWe sincerely thank the reviewer for raising the important concern about the generalizability of our approach.\n\nGraph learning tasks differ significantly in scope: **node-level** attacks inject localized triggers to misclassify specific nodes by exploiting GNN neighborhood propagation; **link prediction** (edge-level) backdoors manipulate the presence or absence of edges between node pairs in local substructures. In contrast, **graph classification** requires modifying the **global semantics** of an entire graph. This inherently makes stealthy backdoor injection far more challenging, as the trigger must manipulate full-graph embeddings, often involving large or structurally rare subgraphs.\n\nOur theoretical analysis (Appendix C.1) further confirms this: graph-level backdoor attacks induce inherently larger distributional shifts than node-level ones, making **distribution-preserving designs** both essential and under-explored.\n\nWhile our current focus is on graph classification, we agree that extending DPSBA to node classification or link prediction is a meaningful direction. However, this would require task-specific adjustments to trigger semantics and stealth modeling. We appreciate the reviewer’s suggestion and consider this an exciting avenue for future exploration.\n\nRegarding dataset diversity, our original experiments already cover heterogeneous domains:\n- **PROTEINS_full** – protein graphs for function prediction,  \n- **AIDS** – molecular graphs relevant to AIDS drug discovery, and  \n- **FRANKENSTEIN** – compound property graphs integrating BURS and MNIST features.\n\nFollowing the reviewer’s suggestion, we additionally evaluated our method on the **ENZYMES** dataset (a 6-class biomolecular classification task), which is finer-grained and more reflective of real-world scenarios. As shown below, **DPSBA consistently outperforms** all baselines in terms of both attack success rate (ASR) and stealth (CAD, AUC) across three surrogate models. Notably, most baselines (except GTA) fail on this dataset due to high attribute and structure variability, underscoring the advantage of our distribution-preserving and adaptive design.\n\n| Dataset  | Surrogate Model | Metric | ER-B  | LIA   | GTA   | Motif | Motif-S | Ours  |\n|----------|------------------|--------|-------|-------|-------|-------|---------|-------|\n| ENZYMES  | GCN              | ASR    | 26.09 | 30.43 | 95.33 | 21.74 | 15.21   | **96.67** |\n|          |                  | CAD    | 4.17  | 4.99  | 3.00  | 4.99  | **-1.67**   | -0.67 |\n|          |                  | AUC    | 68.32 | 66.15 | 71.20 | 71.35 | 66.22   | **66.11** |\n|          | GIN              | ASR    | 37.83 | 27.02 | 96.00 | 16.21 | 12.16   | **99.33** |\n|          |                  | CAD    | 9.17  | 10.00 | 2.67  | 8.33  | 4.17    | **-0.33**|\n|          |                  | AUC    | 71.40 | 62.01 | 76.42 | 68.18 | 65.78   | **41.20**|\n|          | SAGPool          | ASR    | 29.54 | 38.63 | 100.0 | 15.91 | 11.37   | **100.0** |\n|          |                  | CAD    | 4.33  | 6.67  | 5.00  | 10.83 | **3.33**    | 4.00  |\n|          |                  | AUC    | 57.73 | 63.98 | 70.37 | 75.47 | 69.48   | **49.41** |\n\nWe will include these results and the corresponding analysis in the revised paper.\n\n---\n\n## **Response to Comments on Poisoning Rate and Trigger Magnitude Sensitivity (Final Two Weaknesses & Question 3)**\n\nWe appreciate the reviewer’s insightful suggestion regarding the evaluation of poisoning rate and trigger magnitude. To address this, we have conducted a comprehensive sensitivity analysis (Appendix E.5 and E.6) where both the surrogate and victim models are GCNs:\n\n- **Figure E6** investigates the effect of varying poisoning rate on ASR, CAD, and AUC across all datasets.\n- **Figure E7** explores the impact of trigger magnitude (i.e., number of injected nodes $M$) on attack performance.\n\nThese experiments demonstrate that **DPSBA remains effective and stealthy across a wide range of poisoning budgets and trigger sizes**, showing stable ASR with minimal CAD increase, even under low-resource settings. We will highlight these results more clearly in the main text and provide extended analysis for additional surrogate models.\n\nIn particular, to respond to the reviewer’s question on achieving 98–99% ASR on PROTEINS\\_full, we increased the poisoning rate progressively. We find that a **15% poisoning rate** is required to exceed 99% ASR in this dataset. We attribute this to the **complex structural distribution of PROTEINS\\_full**, which has a **node-to-edge ratio of 1:1.86**, compared to the approximately 1:1 ratio in AIDS and FRANKENSTEIN. This makes effective and stealthy manipulation inherently more difficult, yet **DPSBA still achieves top performance**.\n\nThe results are summarized below:\n\n| Dataset        | Model | Metric | Poison Rate 9% | Poison Rate 11% | Poison Rate 13% | Poison Rate 15% |\n|----------------|--------|--------|----------------|----------------|----------------|----------------|\n| PROTEINS\\_full | GCN    | ASR    | 83.15          | 89.61          | 94.98          | 99.28       |\n|                |        | CAD    | 9.59           | 10.30          | 11.85          | 13.18     |\n\nWe thank the reviewer again for encouraging deeper empirical evaluation. These results further support the robustness and adaptability of our framework under various threat model assumptions.\n\n---\n\n## **Response to Comment on Broader Societal Impacts (Limitations)**\n\nWe have addressed this concern in **Appendix G**, where we explicitly discuss the potential misuse of stealthy graph backdoor attacks."}, {"review_id": "SCtnN3IXsa", "reviewer": "Reviewer_5SVM", "summary": "This paper proposes DPSBA, a clean-label backdoor attack for graph classification tasks. It introduces a strategy to learn distribution-preserving triggers that reduce both structural and semantic anomalies, which are commonly exploited by anomaly detectors. The method leverages a two-stage adversarial training framework involving a surrogate classifier and two discriminators that penalize detectability. The approach is evaluated on three binary classification datasets, showing strong attack success with low anomaly scores (AUC), outperforming prior baselines in stealth and effectiveness.", "questions": "1. Could the authors clarify how the feature generator avoids distribution shift when the target graphs have high attribute variance?\n2. How was the surrogate model selected and does its architecture affect DPSBA performance?", "limitations": "No", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. Graph-level backdoor attacks are relatively under-studied compared to node-level attacks. This paper contributes meaningfully by focusing on stealth in the full-graph setting, which is more difficult due to global representation constraints.\n2. The clean-label assumption improves realism and attack stealth, and makes the threat model more aligned with practical concerns in sensitive domains like bioinformatics or chemical compound classification.\n3. The paper presents a number of informative ablation studies that dissect the contributions of different modules in DPSBA, and the visualization of anomaly score distributions adds credibility to stealth claims.\n\nWeaknesses\n1. The training pipeline involves adversarial optimization over both structure and feature discriminators, requiring repeated updates to a surrogate classifier. While theoretically motivated, this complexity could hinder adoption, especially on larger datasets.\n2. The role of hyperparameters α and β in balancing anomaly suppression vs. attack success could be elaborated further, particularly in the main paper (rather than only in the appendix).\n3. It would be informative to include a brief discussion of scenarios where DPSBA fails (e.g., highly homophilic graphs or extremely sparse graphs), to guide practitioners.\n4. The clean-label setting is well motivated, but the paper could benefit from a more direct comparison (qualitative or conceptual) with label-flipping approaches to highlight its practical trade-offs.", "was_revised": true, "final_justification": "The author has effectively and thoroughly addressed all of my concerns during the rebuttal process. As a result, I am willing to raise my score.", "rebuttal": "## **Response to Comment on Complexity (Weaknesses 1)**\n\nWe appreciate the reviewer’s insightful suggestion regarding the complexity of DPSBA.\n\nIn Appendix F, we conducted a detailed analysis of the time complexity from three aspects: Hard Sample Selection, Trigger Location Selection, and Trigger Optimization. Furthermore, we compared the execution time of DPSBA with other baselines under the same conditions using the largest dataset, FRANKENSTEIN. The experimental results are presented in Table F9. The results demonstrate that DPSBA is slightly higher than but remains comparable to other baselines. Moreover, DPSBA outperforms the other baselines in terms of both attack effectiveness and stealth.\n\n---\n\n## **Response to Comments on  Elaborating Hyperparameters $α$ and $β$ (Weaknesses 2)**\n\nWe sincerely thank the reviewer for raising the important concern about elaborating the role of hyperparameters $α$ and $β$ in balancing anomaly suppression vs. attack success. In **Appendix E.5**, we provide a detailed analysis of the hyperparameters $α$ and $β$, with Figure E5 illustrating their impact on ASR and AUC. Subsequently, we will incorporate your valuable suggestions and revise the paper to elaborate on these impacts in the main text.\n\n---\n\n## **Response to Comments on the Failure Situation of DPSBA (Weaknesses 3)**\n\nWe sincerely appreciate the reviewers' concern regarding the failure of DPSBA. Below, we will briefly discuss the scenarios that may lead to the failure of DPSBA.\n\n**1. Dense graphs** \n\nThe **PROTEINS_full** dataset exhibits a relatively high graph density, yet its Attack Success Rate (ASR) is significantly lower than those of the other two datasets. We thus hypothesize that **graph density may influence the attack success rate of DPSBA**. This phenomenon can be attributed to the fact that in dense graphs, node connections are already highly abundant, making trigger injection less impactful on the overall graph structure. Moreover, since nodes in dense graphs typically have numerous neighbors, it becomes more challenging for an attacker to significantly alter global or local graph patterns (e.g., degree distribution, substructure) through minor topological modifications.\nIn contrast, sparse graphs contain fewer edges, meaning each edge plays a more critical role in determining structural properties. Consequently, attackers can more effectively manipulate key paths or neighborhood relationships using simpler trigger structures, thereby achieving higher attack efficacy.\n\n**2. Highly homophilic graphs** \n\nIn graph classification backdoor attacks, achieving a high attack success rate (ASR) requires significant modifications to local structures (e.g., by inserting trigger subgraphs), which inevitably induces a noticeable shift in the graph's homophily distribution. Conversely, ensuring high attack stealth demands minimal deviation in the homophily distribution of poisoned graphs. However, this constraint inherently limits the trigger's ability to effectively alter model predictions, resulting in reduced ASR.\nIn highly homophilic graphs, trigger injection may initially appear effective for successful attacks. Yet, such triggers often introduce obvious deviations in homophily distribution compared to the original graphs, making them easily detectable by defense mechanisms and thus severely compromising stealth. DPSBA aims to strike a balance between ASR and stealth. However, in highly homophilic graphs, the stringent constraints create an optimization dilemma: the adversarial optimization process struggles to concurrently satisfy both objectives, frequently leading to attack failure.\n\n---\n\n## **Response to Comment on Clean-label Setting (Weaknesses 4)**\n\nWe appreciate the reviewer’s insightful suggestion regarding the clean-label setting.\n\nIn Appendix A, we elaborate on the role of the clean-label setting. A comparative analysis of the experimental results in Tables A5 and A6 reveals that **without the clean-label setting**, all baseline methods achieve AUC values exceeding 89%, indicating their attacks exhibit poor stealth. By contrast, **under the clean-label setting**, although the Attack Success Rate (ASR) of all methods decreases, the AUC metric also declines correspondingly. This demonstrates that attacks conducted in the clean-label setting possess superior stealth compared to their non-clean-label counterparts.\n\n---\n\n## **Response to Comment on Avoiding Distribution Shift (Question 1)**\nWe thank the reviewer for raising this important point.\n\nIn our framework, the feature generator does  not rely on distribution priors of the entire dataset. Instead, it takes as input the local structural and attribute context around the trigger injection site and generates features that blend smoothly with the surrounding neighborhood.\nThis allows the generator to adapt to the specific variance of each target graph on a per-instance basis, without requiring any handcrafted normalization or explicit regularization. As a result, the generated features remain close to the local data manifold, reducing the likelihood of creating detectable anomalies, even in the presence of high attribute variance across graphs.\nWe will revise the paper to make this aspect of the generator design clearer in the main text.\n\n---\n\n## **Response to Comment on Surrogate Model  (Question 2)**\n\nWe thank the reviewer for the thoughtful question.\n\nIn most realistic attack scenarios, the attacker does **not** have access to the architecture or parameters of the actual deployed model (i.e., the \"victim model\"). Therefore, backdoor attack frameworks must rely on **surrogate models** during training. These surrogate models need to be both **expressive** (to enable learning effective triggers) and **transferable** (so that the learned triggers can generalize to unknown architectures).\n\nIn our work, we select **GCN**, **GIN**, and **SAGPool** as surrogate models based on two main considerations:\n\n1. **Architectural Diversity**: These models vary significantly in message-passing mechanisms and inductive biases—GCN performs neighborhood averaging, GIN emphasizes substructure discrimination, and SAGPool captures global context via self-attention pooling. This diversity allows us to test the generalization ability of our method across representative GNN families.\n\n2. **Relevance to Prior Work**: All three models are widely adopted in recent graph backdoor baselines (e.g., Motif, Motif-S, ER-B), providing a fair and widely accepted evaluation protocol.\n\nAs for performance sensitivity:  \nYes, the **architecture of the surrogate model can affect the attack success rate (ASR)** due to different robustness properties of target models. However, our proposed **DPSBA consistently achieves high ASR and low CAD across all surrogates**, indicating strong **robustness to surrogate choice**.\n\nWe agree that broader evaluation on additional models such as GAT or GraphSAGE would offer further insights, and we plan to include such extensions in future work."}, {"review_id": "JmyCrg8f5o", "reviewer": "Reviewer_oU5D", "summary": "This paper introduces DPSBA, a clean-label backdoor attack framework for graph classification that uniquely preserves both structural and semantic distributional properties of clean graphs. Unlike existing methods that rely on structurally anomalous or semantically conflicting triggers, DPSBA generates in-distribution subgraph triggers using adversarial training with anomaly-aware discriminators. The paper demonstrates strong results in terms of attack success rate (ASR), stealth (AUC), and transferability across architectures, while maintaining negligible performance drop on clean samples (CAD). The methodology is well-motivated, technically sound, and supported by extensive empirical and theoretical validation.", "questions": "1.\tCould you discuss how DPSBA would behave in multi-class settings, especially when there is no clear minority target class?\n\n2.\tCan DPSBA be adapted for inductive settings (e.g., few-shot graph classification)?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1.\tThe paper identifies and formalizes the dual-source anomaly problem (structural + semantic) in graph-level backdoor attacks and convincingly shows why existing methods fail in stealth.\n\n2.\tThe paper provides clear theoretical bounds on the total variation distance and its relationship to anomaly detectability (AUC), which is rarely discussed in prior graph backdoor literature.\n\n3.\tThe clean-label, limited-poisoning setting significantly increases the practical relevance and threat realism of the proposed method.\n\nWeaknesses:\n\n1.\tAlthough trigger size is fixed to 4, it would be interesting to show how ASR and AUC vary with trigger size.\n\n2.\tAll datasets used are binary. It’s unclear whether DPSBA’s strategy generalizes to multi-class graph classification tasks.\n\n3.\tThe overall writing requires more consistency and standardization in expression.", "was_revised": true, "final_justification": "I appreciate the authors' detailed response. The clarifications provided have largely resolved my concerns. I will retain my original score. Thank you for your work", "rebuttal": "## **Response to Comments on Trigger Size (Weaknesses 1)**\n\nWe sincerely thank the reviewer for pointing out the impact of trigger size changes on the performance of DPSBA.\n\nIn Appendix E.6, we provide a detailed analysis of how trigger size variations impact the three evaluation metrics of DPSBA, with experimental results illustrated in Figure E7. The findings reveal a distinct trade-off relationship regarding trigger size: larger triggers yield stronger attacks but increase detectability, while smaller ones offer greater stealth at the cost of ASR. DPSBA supports flexible adjustment of this trade-off based on practical requirements.\n\n---\n\n## **Response to Comments on Multi-class Graph  Classification Task Experiment (Weaknesses 2 & Question 1)**\n\nWe sincerely thank the reviewer for raising the important concern about the performance of our approach in multi-class graph classification tasks.\n\nFollowing the reviewer’s suggestion, we additionally evaluated our method on the **ENZYMES** dataset (a 6-class biomolecular classification task), which is finer-grained and more reflective of real-world scenarios. As shown below, **DPSBA consistently outperforms** all baselines in terms of both attack success rate (ASR) and stealth (CAD, AUC) across three surrogate models. Notably, most baselines (except GTA) fail on this dataset due to high attribute and strucutre variability, underscoring the advantage of our distribution-preserving and adaptive design.\n\n| Dataset | Surrogate Model | Metric | ER-B  | LIA   | GTA   | Motif | Motif-S   | Ours      |\n| ------- | --------------- | ------ | ----- | ----- | ----- | ----- | --------- | --------- |\n| ENZYMES | GCN             | ASR    | 26.09 | 30.43 | 95.33 | 21.74 | 15.21     | **96.67** |\n|         |                 | CAD    | 4.17  | 4.99  | 3.00  | 4.99  | **-1.67** | -0.67     |\n|         |                 | AUC    | 68.32 | 66.15 | 71.20 | 71.35 | 66.22     | **66.11** |\n|         | GIN             | ASR    | 37.83 | 27.02 | 96.00 | 16.21 | 12.16     | **99.33** |\n|         |                 | CAD    | 9.17  | 10.00 | 2.67  | 8.33  | 4.17      | **-0.33** |\n|         |                 | AUC    | 71.40 | 62.01 | 76.42 | 68.18 | 65.78     | **41.20** |\n|         | SAGPool         | ASR    | 29.54 | 38.63 | 100.0 | 15.91 | 11.37     | **100.0** |\n|         |                 | CAD    | 4.33  | 6.67  | 5.00  | 10.83 | **3.33**  | 4.00      |\n|         |                 | AUC    | 57.73 | 63.98 | 70.37 | 75.47 | 69.48     | **49.41** |\n\nWe will include these results and the corresponding analysis in the revised paper.\n\n---\n\n## **Response to Comments on Writing (Weaknesses 3)**\n\nWe thank the reviewer for pointing out the consistency and standardization of writing. We will focus on the consistency and standardization of writing in the revised paper.\n\n---\n\n## **Response to Comments on Inductive Settings (Question 2)**\n\nWe sincerely thank the reviewer for raising this insightful and forward-looking question regarding the potential adaptation of our framework to inductive scenarios, such as few-shot graph classification.\n\nWhile our current work focuses on the transductive graph classification setting, we believe that several key components of DPSBA have promising potential to extend to the inductive regime. In particular:\n\n- The **feature generator** operates based on localized structural and attribute information at the trigger injection site, and  \n- The **distribution-aware discriminators** regularize stealth on a per-graph basis through adversarial training,  \n\nBoth modules are **graph-local** in nature and do not rely on inter-graph interactions or train–test graph overlap, making them amenable to inductive settings where new test graphs are unseen during training.\n\nThat said, certain components, such as the hard sample selection module, currently assume access to sufficient examples of the target class, which poses challenges in few-shot scenarios. Adapting this component to work under strong data constraints (e.g., via meta-learning or class-agnostic proxy supervision) is a meaningful direction for future work.\n\nWe will include this discussion and future perspective in the revised version of the paper. We again thank the reviewer for this valuable suggestion."}, {"review_id": "nlSFV8ZJL5", "reviewer": "Reviewer_PXmz", "summary": "The authors proposed a dynamic trigger generation method for data poisoning in the graph classification task. Existing methods mostly inject a fixed subgraph into source class graphs. This makes them prone to be detected by anomaly based detectors such as SIGNET. The authors made several changes: 1) Inject triggers only into the target class graphs. 2) Use optimisation to dynamically generate subgraphs and features adaptive to the original graph. They empirically show that in three datasets, the new method can achieve better ASR while lowering the chance of being detected.", "questions": "In Table 2, why did GIN+AIDS and SAGPool+PROTEINS  achieve better ASR compared with Table 1?", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The proposed method is well motivated, and the components are well justified.\n- The writing is clear in most places.\n\nWeaknesses\n- The performance seems to be sensitive to the surrogate model. It is unclear how robust surrogate model choice and training are to affect the reported results.\n- Adaptive trigger can be sensitive. There is a lack of theoretical guarantee that it works across different graph neural networks.", "was_revised": true, "final_justification": "Other reviews and the rebuttal confirm my assessment that the paper is of good quality.", "rebuttal": "## **Response to Comments on Surrogate Model Robustness (Weaknesses 1)**\n\nWe sincerely thank the reviewer for pointing out the importance of surrogate model robustness. This is indeed a critical concern for the practical viability of backdoor attacks in real-world settings.\n\nIn most realistic attack scenarios, the attacker **does not have access to the architecture or weights of the actual deployed model** (i.e., the \"victim model\"). As a result, backdoor attack frameworks must rely on surrogate models that are both **expressive** and **transferable**, enabling triggers to generalize across unknown target architectures. In our work, we adopt **GCN, GIN, and SAGPool** as representative surrogates precisely because they vary in architectural design and have been widely adopted in prior works such as **Motif**, **Motif-S**, and **ER-B**, allowing for meaningful and consistent comparisons.\n\nIt is expected that the **Attack Success Rate (ASR)** may vary depending on the surrogate-target pair, as different target GNNs have inherently different robustness and inductive biases. However, our proposed **DPSBA consistently achieves high ASR and low CAD across all surrogate models**, demonstrating strong generalization across architectures. Additionally, our use of **distribution-aware discriminators** promotes stealthiness in a model-agnostic manner, mitigating overfitting to any single surrogate.\n\nWe agree that evaluating additional architectures would further validate robustness, and we plan to explore this in future work.\n\n---\n\n## **Response to Comments on Adaptive Trigger Robustness and Theoretical Guarantees (Weaknesses 2)**\n\nWe appreciate the reviewer’s comment regarding the robustness of adaptive triggers and the need for theoretical guarantees. This is indeed a crucial issue for ensuring transferability across different GNNs.\n\nTo this end, our work presents a formal theoretical analysis in **Appendix C.2**, where we derive the **Trigger Distributional Detectability Bound**. This result establishes a lower bound on anomaly detection AUC based on the **total variation distance (TVD)** between clean and poisoned graph distributions. Importantly, this analysis is model-agnostic, depending only on distributional divergence rather than any specific GNN internals. Thus, it offers theoretical support for the stealth–effectiveness trade-off of adaptive triggers.\n\nEmpirically, we evaluate DPSBA across diverse GNNs (GCN, GIN, SAGPool) spanning a range of inductive biases. DPSBA maintains high ASR and stealth performance in all cases, confirming the robustness of the adaptive trigger mechanism. We appreciate the reviewer’s suggestion and will consider extending our theoretical analysis to additional architectures in the future.\n\n---\n\n## **Response to Comments on Higher ASR in Cross-Architecture Transfer Settings (Question)**\n\nWe thank the reviewer for highlighting the interesting observation in Table 2, where **GCN→GIN+AIDS** and **GCN→SAGPool+PROTEINS** achieve higher ASR than their white-box counterparts (GIN→GIN+AIDS, SAGPool→SAGPool+PROTEINS). Though initially counterintuitive, this phenomenon can be explained from three perspectives: **model expressiveness**, **trigger generalizability**, and **dataset characteristics**.\n\n**(1) Model Expressiveness vs. Overfitting**  \nGIN and SAGPool are more expressive than GCN:\n- *GIN* is theoretically equivalent to the Weisfeiler-Lehman test, capable of distinguishing fine-grained substructures.\n- *SAGPool* uses self-attention to highlight global structures most relevant for classification.\n\nThese powerful models, when used as surrogates, tend to learn highly specialized, structure-sensitive triggers. While effective on the surrogate model itself, such triggers are prone to **overfitting** and may fail to generalize to unseen samples or to minor parameter shifts. This aligns with prior observations (e.g., *Tramèr et al., ICLR 2018*) that stronger surrogates often overfit their own gradients, reducing perturbation transferability.\n\n> Tramèr, F. et al. (2018). Ensemble adversarial training: Attacks and defenses. ICLR.  \n\n**(2) GCN-Trained Triggers Are More Transferable**  \nGCN, with its smoother message passing and lower expressiveness, tends to learn broader and more transferable trigger patterns. These triggers may achieve lower ASR on GCN itself (as seen in Table 1), but generalize better when transferred to expressive models like GIN or SAGPool, which are more sensitive to subtle perturbations and thus **amplify the attack effect**.\n\n**(3) Dataset-Specific Factors Amplify the Effect**  \n- *AIDS*: Molecular graphs are small but structurally complex. Local substructures (e.g., functional groups) are crucial, making GIN highly sensitive to local changes caused by transferred triggers.\n- *PROTEINS_full*: Graphs are larger and denser (node–edge ratio ≈ 1:1.86), favoring models like SAGPool that focus on global structure. GCN’s triggers are naturally aligned with such global perturbations, which SAGPool tends to emphasize.\n\n**In summary:**\n- Strong surrogates (GIN/SAGPool) may overfit to narrow trigger distributions, limiting transferability;\n- GCN, though less optimal in white-box settings, produces **robust and transferable triggers**;\n- These results demonstrate DPSBA's strong generalization under model mismatch and strengthen its practical utility.\n\nWe will incorporate this discussion in the revised version of our paper.\n\n---\n\n## **Response to Paper Formatting Concerns**\n\nWe thank the reviewer for pointing out the formatting issue. We will revise the paper to use `\\mathrm{}` consistently for all mathematical expressions involving operators such as `cfd` and `diff`."}]

Author rebuttal:

Meta-review: The paper studies backdoor attacks on graph neural networks: the attacker would like to keep the behavior of the learned network similar on most inputs, but wants to control the learner’s predictions for some examples by modifying them stealthily. That is, the attacker wants to insert a back door into the learned model. 

In a less common setup compared to past work, the paper studies whole-graph classification, instead of node or link prediction. This is a more difficult case, since small modifications to the input graph might not influence the classifier, and large modifications might be too easy to detect. (In this regard, Figure 1 is convincing: it shows how easily an anomaly detector can foil some previously-proposed attacks.)

The threat model is: at training time, the attacker has no influence over labels (the clean-label setting), but can influence a small fraction of the training examples by inserting a small number of extra nodes and edges into their input graphs. The attacker cannot delete or change any existing nodes or edges in the training graphs. At test time, the attacker can influence a small fraction of test examples, again by inserting extra nodes and edges into the input. The attacker wins if it is able to cause the learned model to predict a given target class on the modified examples, instead of their true class. The attacker loses if it is detected, either at train time or at test time. The attacker has no knowledge about or influence over the training process beyond its limited ability to alter training data: no ability to attack or surveil the computers that run the training loop, and no information about the model or hyperparameters for training. (In practice the stealth condition means (1) the defender runs anomaly detection on its training and test examples, and the attacker needs not to trigger the detector, as well as (2) the attacker wants not to compromise the learner’s accuracy much on unaltered examples.)

The paper presents a few interesting insights. First, difficult training examples of the target class provide a good attack opportunity: the learner has trouble finding the true signal in these examples, and therefore if the attacker provides a tempting enough false signal, the learner will latch onto it. Second, finding a successful attack while avoiding detection is a constrained optimization problem, and so we can solve it as a game between the attacker and defender trying to minimize/maximize a Lagrangian. Third, insights 1 and 2 can still work even if we don’t have an exact model of the learner or detector: we can still find successful attacks by optimizing against a surrogate defender. In addition to the above, the reviewer/author discussion touched on some other insights, which will help make the final version of the paper better. For example, there was a nice discussion of failure modes.

All these insights are instantiated in a system, DPSBA, and tested on some benchmark graph classification datasets. The system achieves a better tradeoff between attack success rate and attack detection rate compared to prior work.

The reviewers agree that the paper is fairly clear to start, and after modifications according to the discussion, will be clearer. The problem setup is interesting and important, and the paper’s new insights add to our understanding of how to solve it. The authors were responsive and helpful during the discussion.
Decision: Accept (poster)