Recognition: 2 theorem links
· Lean TheoremBadImplant: Injection-based Multi-Targeted Graph Backdoor Attack
Pith reviewed 2026-05-16 11:58 UTC · model grok-4.3
The pith
Subgraph injection creates the first multi-targeted backdoor attack on graph neural networks for classification.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
By injecting several distinct subgraphs as triggers into clean training graphs, an attacker can embed multiple backdoors that cause the resulting GNN to map any input graph containing a given trigger to its corresponding target label, while the model continues to classify clean graphs correctly.
What carries the argument
Subgraph injection: adding chosen trigger subgraphs to original graphs without replacing any existing nodes or edges, thereby preserving overall graph structure.
If this is right
- One poisoned model can be made to misclassify to any of several target labels depending on which trigger is present.
- The attack maintains high success rates across all targets while clean accuracy drops remain small on five datasets.
- Subgraph injection outperforms conventional subgraph replacement on the same tasks.
- The attack succeeds on four different GNN architectures regardless of training settings.
- Randomized smoothing and fine-pruning defenses do not eliminate the multi-target attack.
Where Pith is reading between the lines
- Graph datasets collected for real-world use may need new checks for added subgraphs that preserve overall statistics.
- The injection approach could be adapted to node-level or link-prediction tasks on graphs.
- Defenses focused only on accuracy drops may miss structural additions that carry multiple triggers.
- Attackers can adjust trigger size, density, and number of connections to balance success rate against detectability.
Load-bearing premise
An attacker can insert subgraphs into the training graphs without the changes being detected or preventing the model from learning the intended trigger-to-label mappings.
What would settle it
Train a GNN on data poisoned by the described injection method and measure whether graphs containing the injected triggers are classified to the intended target labels at rates well above random chance; failure to observe those rates would refute the central claim.
Figures
read the original abstract
Graph neural network (GNN) have demonstrated exceptional performance in solving critical problems across diverse domains yet remain susceptible to backdoor attacks. Existing studies on backdoor attack for graph classification are limited to single target attack using subgraph replacement based mechanism where the attacker implants only one trigger into the GNN model. In this paper, we introduce the first multi-targeted backdoor attack for graph classification task, where multiple triggers simultaneously redirect predictions to different target labels. Instead of subgraph replacement, we propose subgraph injection which preserves the structure of the original graphs while poisoning the clean graphs. Extensive experiments demonstrate the efficacy of our approach, where our attack achieves high attack success rates for all target labels with minimal impact on the clean accuracy. Experimental results on five dataset demonstrate the superior performance of our attack framework compared to the conventional subgraph replacement-based attack. Our analysis on four GNN models confirms the generalization capability of our attack which is effective regardless of the GNN model architectures and training parameters settings. We further investigate the impact of the attack design parameters including injection methods, number of connections, trigger sizes, trigger edge density and poisoning ratios. Additionally, our evaluation against state-of-the-art defenses (randomized smoothing and fine-pruning) demonstrates the robustness of our proposed multi-target attacks. This work highlights the GNN vulnerability against multi-targeted backdoor attack in graph classification task. Our source codes will be available at https://github.com/SiSL-URI/Multi-Targeted-Graph-Backdoor-Attack.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proposes BadImplant, the first multi-targeted backdoor attack for graph classification. It replaces subgraph replacement with subgraph injection to implant multiple triggers that simultaneously redirect predictions to distinct target labels while preserving original graph structure. Experiments on five datasets and four GNN models report high attack success rates across all targets, minimal clean-accuracy degradation, superiority over single-target replacement baselines, and robustness to randomized smoothing and fine-pruning. Parameter studies examine injection methods, connection counts, trigger sizes, edge densities, and poisoning ratios.
Significance. If the empirical results hold, the work establishes a concrete advance in GNN security by demonstrating practical multi-target backdoors that outperform prior single-target methods while remaining effective across architectures and resistant to two standard defenses. The multi-dataset, multi-model evaluation and open-source code commitment strengthen the contribution's reliability and utility for the community.
major comments (2)
- [Section 4] Section 4 (parameter study): varying number of connections and trigger edge density reports only ASR and clean accuracy; no quantitative comparison of topological invariants (degree sequences, clustering coefficients, motif counts) or anomaly-detection baselines is provided between clean and poisoned graphs. This leaves the central premise that injection keeps poisoned graphs statistically indistinguishable from clean ones unverified, which is load-bearing for the undetected-poisoning claim and the asserted superiority over replacement attacks.
- [Sections 4–5] Experimental results (throughout Sections 4–5): high ASR values are reported without mention of the number of independent runs, standard deviations, or statistical significance tests against baselines. This weakens confidence that the multi-target performance advantage is robust rather than sensitive to random seeds or particular data splits.
minor comments (1)
- [Abstract] Abstract: 'Graph neural network (GNN) have' should read 'Graph neural networks (GNNs) have'; 'five dataset' should read 'five datasets'.
Simulated Author's Rebuttal
We sincerely thank the referee for the constructive and detailed feedback. We have carefully reviewed each major comment and provide point-by-point responses below. We will revise the manuscript to address the concerns and strengthen the presentation of our results.
read point-by-point responses
-
Referee: [Section 4] Section 4 (parameter study): varying number of connections and trigger edge density reports only ASR and clean accuracy; no quantitative comparison of topological invariants (degree sequences, clustering coefficients, motif counts) or anomaly-detection baselines is provided between clean and poisoned graphs. This leaves the central premise that injection keeps poisoned graphs statistically indistinguishable from clean ones unverified, which is load-bearing for the undetected-poisoning claim and the asserted superiority over replacement attacks.
Authors: We agree that explicit quantitative verification of topological similarity would strengthen the claim that subgraph injection produces poisoned graphs that remain statistically close to clean ones. In the revised manuscript we will augment Section 4 with direct comparisons of degree sequences, clustering coefficients, and motif counts between clean and poisoned graphs across the reported parameter settings. We will also evaluate the poisoned graphs against standard anomaly-detection baselines (e.g., graph auto-encoder reconstruction error and degree-based outlier scores) and report the resulting detection rates to substantiate the undetected-poisoning premise and the advantage over replacement attacks. revision: yes
-
Referee: [Sections 4–5] Experimental results (throughout Sections 4–5): high ASR values are reported without mention of the number of independent runs, standard deviations, or statistical significance tests against baselines. This weakens confidence that the multi-target performance advantage is robust rather than sensitive to random seeds or particular data splits.
Authors: We acknowledge the importance of reporting experimental variability and statistical rigor. In the revised version we will explicitly state that all results are averaged over five independent runs with different random seeds and data splits. We will add standard deviations to all ASR and clean-accuracy tables in Sections 4 and 5. In addition, we will include paired t-tests (or Wilcoxon signed-rank tests where appropriate) comparing BadImplant against the single-target replacement baselines to demonstrate that the observed multi-target performance gains are statistically significant. revision: yes
Circularity Check
No circularity: purely empirical attack proposal with external baselines
full rationale
The paper introduces a subgraph-injection backdoor attack for multi-target graph classification and validates it through experiments on five datasets, four GNN architectures, parameter sweeps, and comparisons to prior single-target replacement attacks plus two defenses. No equations, fitted parameters, or derivations are present; all performance claims (ASR, clean accuracy) are measured outcomes against independent baselines rather than reductions to the method's own inputs. No self-citations are load-bearing for any uniqueness or prediction step. The work is therefore self-contained empirical research with no circularity.
Axiom & Free-Parameter Ledger
free parameters (2)
- trigger size
- poisoning ratio
axioms (1)
- domain assumption Attacker can access and modify the training dataset by injecting subgraphs
Lean theorems connected to this paper
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
we propose subgraph injection which preserves the structure of the original graphs while poisoning the clean graphs... T=ER(trigger size,trigger edge density)
-
IndisputableMonolith/Foundation/AlexanderDuality.leanalexander_duality_circle_linking unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
multi-targeted backdoor attack... multiple triggers simultaneously redirect predictions to different target labels
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Forward citations
Cited by 1 Pith paper
-
BadSNN: Backdoor Attacks on Spiking Neural Networks via Adversarial Spiking Neuron
BadSNN injects backdoors into spiking neural networks by adversarially tuning LIF neuron hyperparameters and optimizing triggers, achieving higher attack success than prior data-poisoning methods while remaining robus...
Reference graph
Works this paper leans on
-
[1]
A survey of graph neural networks for social recommender systems,
K. Sharma, Y .-C. Lee, S. Nambi, A. Salian, S. Shah, S.-W. Kim, and S. Kumar, “A survey of graph neural networks for social recommender systems,”ACM Computing Sur- veys, vol. 56, no. 10, pp. 1–34, 2024
work page 2024
-
[2]
G. Corso, H. Stark, S. Jegelka, T. Jaakkola, and R. Barzi- lay, “Graph neural networks,”Nature Reviews Methods Primers, vol. 4, no. 1, p. 17, 2024
work page 2024
-
[3]
Graph neural networks for molecules,
Y . Wang, Z. Li, and A. Barati Farimani, “Graph neural networks for molecules,” inMachine learning in molecu- lar sciences. Springer, 2023, pp. 21–66
work page 2023
-
[4]
Graph neural networks and their current applications in bioinfor- matics,
X.-M. Zhang, L. Liang, L. Liu, and M.-J. Tang, “Graph neural networks and their current applications in bioinfor- matics,”Frontiers in genetics, vol. 12, p. 690049, 2021
work page 2021
-
[5]
A review on graph neural network methods in financial applications,
J. Wang, S. Zhang, Y . Xiao, and R. Song, “A review on graph neural network methods in financial applications,” arXiv preprint arXiv:2111.15367, 2021
-
[6]
Vision gnn: An image is worth graph of nodes,
K. Han, Y . Wang, J. Guo, Y . Tang, and E. Wu, “Vision gnn: An image is worth graph of nodes,”Advances in neural information processing systems, vol. 35, pp. 8291– 8303, 2022
work page 2022
-
[7]
Data science in transportation networks with graph neural networks: A review and outlook,
J. Xue, R. Tan, J. Ma, and S. V . Ukkusuri, “Data science in transportation networks with graph neural networks: A review and outlook,”Data Science for Transportation, vol. 7, no. 2, p. 10, 2025
work page 2025
-
[8]
Y . L. Liu, Y . Wang, O. Vu, R. Moretti, B. Bodenheimer, J. Meiler, and T. Derr, “Interpretable chirality-aware graph neural network for quantitative structure activity relation- ship modeling in drug discovery,” inProceedings of the AAAI conference on artificial intelligence, vol. 37, no. 12, 2023, pp. 14 356–14 364
work page 2023
-
[9]
Z. Zhao, P. Qian, X. Yang, Z. Zeng, C. Guan, W. L. Tam, and X. Li, “Semignn-ppi: Self-ensembling multi- graph neural network for efficient and generalizable protein-protein interaction prediction,”arXiv preprint arXiv:2305.08316, 2023
-
[10]
Graph neural networks in recommender systems: a survey,
S. Wu, F. Sun, W. Zhang, X. Xie, and B. Cui, “Graph neural networks in recommender systems: a survey,”ACM Computing Surveys, vol. 55, no. 5, pp. 1–37, 2022
work page 2022
-
[11]
Image classification using graph neural network and multiscale wavelet superpixels,
V . Vasudevan, M. Bassenne, M. T. Islam, and L. Xing, “Image classification using graph neural network and multiscale wavelet superpixels,”Pattern Recognition Let- ters, vol. 166, pp. 89–96, 2023
work page 2023
-
[12]
Point-gnn: Graph neural net- work for 3d object detection in a point cloud,
W. Shi and R. Rajkumar, “Point-gnn: Graph neural net- work for 3d object detection in a point cloud,” inProceed- ings of the IEEE/CVF conference on computer vision and pattern recognition, 2020, pp. 1711–1719
work page 2020
-
[13]
Gnn-ids: Graph neu- ral network based intrusion detection system,
Z. Sun, A. M. Teixeira, and S. Toor, “Gnn-ids: Graph neu- ral network based intrusion detection system,” inProceed- ings of the 19th international conference on availability, reliability and security, 2024, pp. 1–12
work page 2024
-
[14]
Financial fraud detection us- ing graph neural networks: A systematic review,
S. Motie and B. Raahemi, “Financial fraud detection us- ing graph neural networks: A systematic review,”Expert Systems with Applications, vol. 240, p. 122156, 2024
work page 2024
-
[15]
Graph neural networks for financial fraud detection: a review,
D. Cheng, Y . Zou, S. Xiang, and C. Jiang, “Graph neural networks for financial fraud detection: a review,”Fron- tiers of Computer Science, vol. 19, no. 9, p. 199609, 2025
work page 2025
-
[16]
Neural message passing for quantum chem- istry,
J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl, “Neural message passing for quantum chem- istry,” inInternational conference on machine learning. Pmlr, 2017, pp. 1263–1272
work page 2017
-
[17]
A sur- vey of graph neural networks and their industrial applica- tions,
H. Lu, L. Wang, X. Ma, J. Cheng, and M. Zhou, “A sur- vey of graph neural networks and their industrial applica- tions,”Neurocomputing, vol. 614, p. 128761, 2025
work page 2025
-
[18]
Graph neural networks: a survey on the links between privacy and security,
F. Guan, T. Zhu, W. Zhou, and K.-K. R. Choo, “Graph neural networks: a survey on the links between privacy and security,”Artificial Intelligence Review, vol. 57, no. 2, p. 40, 2024
work page 2024
-
[19]
Watermark- ing graph neural networks based on backdoor attacks,
J. Xu, S. Koffas, O. Ersoy, and S. Picek, “Watermark- ing graph neural networks based on backdoor attacks,” in 2023 IEEE 8th European Symposium on Security and Pri- vacy (EuroS&P). IEEE, 2023, pp. 1179–1197
work page 2023
-
[20]
Z. Xi, R. Pang, S. Ji, and T. Wang, “Graph backdoor,” in 30th USENIX security symposium (USENIX Security 21), 2021, pp. 1523–1540
work page 2021
-
[21]
Single node injection attack against graph neural net- works,
S. Tao, Q. Cao, H. Shen, J. Huang, Y . Wu, and X. Cheng, “Single node injection attack against graph neural net- works,” inProceedings of the 30th ACM International Conference on Information&Knowledge Management, 2021, pp. 1794–1803
work page 2021
-
[22]
Tdgia: Effective injection attacks on graph neural networks,
X. Zou, Q. Zheng, Y . Dong, X. Guan, E. Kharlamov, J. Lu, and J. Tang, “Tdgia: Effective injection attacks on graph neural networks,” inProceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery&Data Mining, 2021, pp. 2461–2471
work page 2021
-
[23]
J. Li, D. Liu, D. Cheng, and C. Jiang, “Attack by yourself: Effective and unnoticeable multi-category graph back- door attacks with subgraph triggers pool,”arXiv preprint arXiv:2412.17213, 2024
-
[24]
Stealthy yet effective: Distribution-preserving backdoor attacks on graph classification,
X. Wang, R. Sun, Y . Zhang, B. Feng, D. He, L. Wang, and D. Jin, “Stealthy yet effective: Distribution-preserving backdoor attacks on graph classification,”arXiv preprint arXiv:2509.26032, 2025
-
[25]
Backdoor attacks to graph neural networks,
Z. Zhang, J. Jia, B. Wang, and N. Z. Gong, “Backdoor attacks to graph neural networks,” inProceedings of the 26th ACM symposium on access control models and tech- nologies, 2021, pp. 15–26. 12
work page 2021
-
[26]
A new model for learning in graph domains,
M. Gori, G. Monfardini, and F. Scarselli, “A new model for learning in graph domains,” inProceedings. 2005 IEEE international joint conference on neural networks, 2005., vol. 2. IEEE, 2005, pp. 729–734
work page 2005
-
[27]
Semi-Supervised Classification with Graph Convolutional Networks
T. Kipf, “Semi-supervised classification with graph con- volutional networks,”arXiv preprint arXiv:1609.02907, 2016
work page internal anchor Pith review Pith/arXiv arXiv 2016
-
[28]
P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Lio, Y . Bengioet al., “Graph attention networks,”stat, vol. 1050, no. 20, pp. 10–48 550, 2017
work page 2017
-
[29]
Inductive rep- resentation learning on large graphs,
W. Hamilton, Z. Ying, and J. Leskovec, “Inductive rep- resentation learning on large graphs,”Advances in neural information processing systems, vol. 30, 2017
work page 2017
-
[30]
How Powerful are Graph Neural Networks?
K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph neural networks?”arXiv preprint arXiv:1810.00826, 2018
work page internal anchor Pith review Pith/arXiv arXiv 2018
-
[31]
Security and privacy issues in deep learning: a brief review,
T. Ha, T. K. Dang, H. Le, and T. A. Truong, “Security and privacy issues in deep learning: a brief review,”SN Computer Science, vol. 1, no. 5, p. 253, 2020
work page 2020
-
[32]
Ma- chine learning security and privacy: a review of threats and countermeasures,
A. Paracha, J. Arshad, M. B. Farah, and K. Ismail, “Ma- chine learning security and privacy: a review of threats and countermeasures,”EURASIP Journal on Information Security, vol. 2024, no. 1, p. 10, 2024
work page 2024
-
[33]
BadNets: Identifying Vulnerabilities in the Machine Learning Model Supply Chain
T. Gu, B. Dolan-Gavitt, and S. Garg, “Badnets: Identify- ing vulnerabilities in the machine learning model supply chain,”arXiv preprint arXiv:1708.06733, 2017
work page internal anchor Pith review Pith/arXiv arXiv 2017
-
[34]
Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning
X. Chen, C. Liu, B. Li, K. Lu, and D. Song, “Targeted backdoor attacks on deep learning systems using data poi- soning,”arXiv preprint arXiv:1712.05526, 2017
work page internal anchor Pith review Pith/arXiv arXiv 2017
-
[35]
Trojaning attack on neural networks,
Y . Liu, S. Ma, Y . Aafer, W.-C. Lee, J. Zhai, W. Wang, and X. Zhang, “Trojaning attack on neural networks,” in25th Annual Network And Distributed System Security Sympo- sium (NDSS 2018). Internet Soc, 2018
work page 2018
-
[36]
Clean-label back- door attacks,
A. Turner, D. Tsipras, and A. Madry, “Clean-label back- door attacks,” 2018
work page 2018
-
[37]
Wanet–imperceptible warping- based backdoor attack,
A. Nguyen and A. Tran, “Wanet–imperceptible warping- based backdoor attack,”arXiv preprint arXiv:2102.10369, 2021
-
[38]
Rethinking the trigger- injecting position in graph backdoor attack,
J. Xu, G. Abad, and S. Picek, “Rethinking the trigger- injecting position in graph backdoor attack,” in2023 International Joint Conference on Neural Networks (IJCNN). IEEE, 2023, pp. 1–8
work page 2023
-
[39]
A clean-label graph backdoor attack method in node classification task,
X. Xing, M. Xu, Y . Bai, and D. Yang, “A clean-label graph backdoor attack method in node classification task,” Knowledge-Based Systems, vol. 304, p. 112433, 2024
work page 2024
-
[40]
Benchmarking graph neural net- works,
V . P. Dwivedi, C. K. Joshi, A. T. Luu, T. Laurent, Y . Ben- gio, and X. Bresson, “Benchmarking graph neural net- works,”Journal of Machine Learning Research, vol. 24, no. 43, pp. 1–48, 2023
work page 2023
-
[41]
Geometric deep learning on graphs and manifolds using mixture model cnns,
F. Monti, D. Boscaini, J. Masci, E. Rodola, J. Svoboda, and M. M. Bronstein, “Geometric deep learning on graphs and manifolds using mixture model cnns,” inProceedings of the IEEE conference on computer vision and pattern recognition, 2017, pp. 5115–5124
work page 2017
-
[42]
Understand- ing isomorphism bias in graph data sets,
S. Ivanov, S. Sviridov, and E. Burnaev, “Understand- ing isomorphism bias in graph data sets,”arXiv preprint arXiv:1910.12091, 2019
-
[43]
Certified adver- sarial robustness via randomized smoothing,
J. Cohen, E. Rosenfeld, and Z. Kolter, “Certified adver- sarial robustness via randomized smoothing,” ininterna- tional conference on machine learning. PMLR, 2019, pp. 1310–1320
work page 2019
-
[44]
Fine-pruning: De- fending against backdooring attacks on deep neural net- works,
K. Liu, B. Dolan-Gavitt, and S. Garg, “Fine-pruning: De- fending against backdooring attacks on deep neural net- works,” inInternational symposium on research in at- tacks, intrusions, and defenses. Springer, 2018, pp. 273– 294. 13
work page 2018
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.