Source-linked AI summary
Backdoor Attacks to Graph Neural Networks
Zaixi Zhang, Jinyuan Jia, Binghui Wang, Neil Zhenqiang Gong
TL;DR
GNN graph classification had limited study of backdoor attacks, despite GNN use in security analytics. The paper proposes subgraph triggers trained through poisoned graphs and finds high attack success with small clean-accuracy impact, while randomized-subsampling certification is effective only in some cases. It concludes that new defenses are needed.
Problem
Backdoor attacks to GNN graph classification were unexplored, while existing adversarial graph attacks require graph-specific perturbations and may have limited success against unknown target GNNs.
Method
The paper poisons selected training graphs with an attacker-chosen target label and subgraph trigger, then generalizes randomized subsampling as a certified defense.
Results
90% of Twitter testing graphs received the target label after trigger injection with a 0.03 clean-accuracy drop, while the defense reduced attack success by 0.39 at 20% trigger size but by <0.01 at 30%.
Takeaways & Limitations
Subgraph backdoor attacks can remain effective while preserving clean-graph accuracy, and randomized-subsampling defense performance depends on trigger size.
Takeaways & Limitations
Randomized subsampling achieves small certified trigger sizes and is ineffective in some scenarios, especially for large triggers.
Abstract
from arXiv · showhide
In this work, we propose the first backdoor attack to graph neural networks (GNN). Specifically, we propose a \emph{subgraph based backdoor attack} to GNN for graph classification. In our backdoor attack, a GNN classifier predicts an attacker-chosen target label for a testing graph once a predefined subgraph is injected to the testing graph. Our empirical results on three real-world graph datasets show that our backdoor attacks are effective with a small impact on a GNN's prediction accuracy for clean testing graphs. Moreover, we generalize a randomized smoothing based certified defense to defend against our backdoor attacks. Our empirical results show that the defense is effective in some cases but ineffective in other cases, highlighting the needs of new defenses for our backdoor attacks.
1 Introduction
The paper introduces subgraph-based backdoor attacks for GNN graph classification, addressing an underexplored threat model with a shared trigger. Experiments show high attack effectiveness, limited clean-accuracy impact, and mixed certified-defense performance.
- Graph classification attacks on GNNs are underexplored compared with node-classification attacks, while existing graph attacks require graph-specific perturbations and may fail when the target GNN is unknown.
- The proposed backdoor attack uses the same subgraph trigger across testing graphs and does not require knowledge of the target GNN.Backdoor training associates injected triggers with an attacker-chosen target label.
- The attack is characterized by trigger size, trigger density, trigger synthesis method, and poisoning intensity.
- 90% of Twitter testing graphs with non-target ground-truth labels were assigned the target label after trigger injection, while clean accuracy dropped by 0.03.This result uses a trigger size equal to 30% of the average number of nodes per graph.
- Randomized subsampling reduced Twitter attack success rates by 0.39 with a 0.02 clean-accuracy drop at 20% trigger size, but reduced them by <0.01 at 30%.All Twitter testing graphs had certified trigger sizes below 10% of the average number of nodes per graph.
- The study evaluates attacks and defenses on three real-world graph datasets and concludes that new defenses are needed.
2 Background and Problem Setup
The background defines graph classification as assigning a label to an entire graph and describes GNNs as neighborhood-aggregation models trained using stochastic gradient descent. The threat model prioritizes stealth on clean graphs.
- 2.1 Graph Neural Networks (GNNs): Graph classification maps an input graph to one label, while a GNN iteratively aggregates neighboring node representations before producing the graph label.
- 2. Background and Problem Setup: GNN classifiers are commonly trained with stochastic gradient descent by updating model parameters opposite the loss gradient for sampled batches.
- 2. Background and Problem Setup: The threat model requires backdoor attacks to preserve accuracy on clean testing graphs so that substantially reduced accuracy does not reveal the attack.
3 Our Subgraph based Backdoor Attacks
The attack injects a subgraph trigger into selected training graphs, relabels them to an attacker-chosen target, and applies the same trigger during testing. Trigger structure is controlled through size, density, and synthesis choices.
- Attack Pipeline: During training, the attacker injects a subgraph into selected graphs and changes their labels to an attacker-chosen target; during testing, the same trigger induces that target prediction.
- Attack Design: Trigger size is the number of trigger nodes, while trigger density is the ratio of trigger edges to possible node pairs.
- Attack Design: The Erdős-Rényi synthesis method independently adds each possible edge with probability p=ρ, producing the specified density on average.
- Attack Design: ER-generated triggers are more effective than small-world and preferential-attachment triggers because clean graphs exhibit small-world structure and power-law degree distributions.
- Attack Design: Poisoning intensity denotes the fraction of training graphs modified with the trigger and relabeled to the target.
4 Attack Evaluation
The evaluation tests the subgraph backdoor attack across three real-world graph datasets and multiple attack configurations. Results show high attack effectiveness with limited clean-accuracy impact, while effectiveness depends on trigger design, graph density, and injection setting.
- Datasets and metrics: The experiments use Bitcoin, Twitter, and COLLAB, covering fraud detection, fake-user detection, and scientific collaboration, with binary and multi-class tasks.The datasets contain graph-level labels and use node degree as the node feature.
- Datasets and metrics: Attack success rate measures how often the backdoored classifier predicts the target label on triggered testing graphs, while backdoor accuracy measures clean-graph accuracy after poisoning.Clean accuracy measures the clean classifier on clean testing graphs; the difference between clean and backdoor accuracy measures attack impact.
- Parameter impacts: Attack success rates increase with trigger size, trigger density, and poisoning intensity because larger values strengthen the learned association between the trigger and target label.Figure 2 examines these three parameters across the datasets.
- Trigger synthesis: ER triggers achieve higher attack success rates than SW and PA triggers, which may resemble clean subgraphs more closely.The comparison fixes ρ=0.4 because PA requires it to be small.
- Graph density: Attack success decreases as Twitter’s average clean-graph density approaches the trigger density of 0.3, reaching its least effectiveness when the densities match.At matching densities, the trigger is harder for the GNN to distinguish from clean subgraphs.
- Injection setting: Injecting the trigger into both training and testing graphs substantially improves attack success rates compared with injecting it into either side alone.Injecting triggers into only training or only testing graphs also raises attack success over baseline, partly through reduced classifier accuracy.
- Robustness checks: Random triggers are nearly as effective as fixed triggers, and the attack remains effective across different GNN classifiers.The authors attribute random-trigger effectiveness to structural similarity and classifier-independence to the attack’s architecture-agnostic design.
5 Certified Defense
The defense generalizes randomized subsampling to graph classification by voting over predictions from randomized subsampled graphs, yielding a certified trigger-size guarantee. It also trains the base GNN with subsampling to address the distribution shift between training and subsampled testing graphs.
- Certified robustness: The smoothed classifier predicts the same label when the trigger changes no more than a certified threshold number of graph-structure entries.A trigger is treated as flips in the binary graph structure vector, including added or deleted edges.
- Certification procedure: Randomized subsampling estimates the smoothed prediction from d subsampled inputs and uses the most frequent base-classifier label as the output.The predicted label and its count support estimating the probability bound needed for certification.
- Randomized subsampling: Randomized subsampling creates d randomized subsampled graphs, applies the GNN to each, and predicts the testing graph’s label by majority vote.The graph is randomized by retaining a subset of structure-vector entries and removing edges between remaining node pairs.
- Certified robustness: The certified trigger size can differ across testing graphs because the robustness threshold is input-dependent.The threshold is defined as the trigger size below which the smoothed GNN’s prediction is provably unchanged.
- Training with subsampling: Training the base GNN with subsampling addresses distribution shift caused by evaluating it on subsampled graphs rather than original testing graphs.The shift otherwise limits base-classifier accuracy and therefore the smoothed classifier’s accuracy and robustness.
6 Defense Evaluation
The defense is evaluated on Bitcoin, Twitter, and COLLAB using accuracy and attack success rate under varying subsampling and trigger-size settings. It trades lower attack success rates for lower backdoor accuracy, works best for small triggers, and becomes ineffective for some large triggers.
- Evaluation setup: The evaluation uses Bitcoin, Twitter, and COLLAB, measuring clean accuracy, backdoor accuracy, and attack success rate.The experiments use the same dataset splits as the attack evaluation and default to d=100 and β=10%.
- Training comparison: Training with subsampling substantially improves the smoothed classifiers, while clean and backdoor accuracy become especially close afterward.The remaining experiments therefore report backdoor accuracy for simplicity.
- Parameter impact: The smoothed backdoored GIN lowers attack success rate but also lowers backdoor accuracy compared with the backdoored GIN.When d exceeds 10, its impact is negligible; increasing β raises both backdoor accuracy and attack success rate.
- Trigger-size impact: 0.39 attack success rate reduction with only 0.02 backdoor accuracy drop occurs on Twitter when the trigger is 20% of the average graph size.This is an example where randomized subsampling is effective against a small trigger.
- Trigger-size impact: For Twitter triggers at 30% of the average graph size, the smoothed and backdoored GINs have almost the same attack success rate.All Twitter testing graphs have certified trigger sizes below 10% of the average graph size under the default setting.
7 Discussion and Limitations
The paper examines dense-subgraph detection and randomized subsampling as defenses, finding that their effectiveness depends on trigger characteristics and can be limited.
- Detecting triggers via dense-subgraph detection: Dense-subgraph detection may work for very dense triggers, such as complete subgraphs, but sparser triggers can evade detection.The paper reports that attacks remain effective even when triggers are sparser than clean graphs on average.
- Detecting triggers via dense-subgraph detection: The detection method assumes knowledge of the trigger size, giving the defender an advantage in identifying the injected subgraph.Detection success rate is measured by whether the detected dense subgraph matches the trigger.
- Detecting triggers via dense-subgraph detection: Table 7 reports very low trigger-detection success rates across Bitcoin, Twitter, and COLLAB.The table concerns dense subgraph detection-based defense.
- Detecting triggers via dense-subgraph detection: Removing detected dense subgraphs significantly lowers backdoor accuracy while attack success remains high, demonstrating defense ineffectiveness.The same experimental settings as Section 4.1 are used for the removal evaluation.
- Randomized subsampling based certified defense: Randomized subsampling can certify the same prediction when the injected trigger is below a size threshold, but may be less effective for large triggers.The paper suspects effectiveness in some scenarios, particularly when the trigger is small, and limited effectiveness when it is large.
8 Related Work
Related work covers backdoor attacks and defenses in images, adversarial attacks on GNN node classification, and randomized smoothing as a scalable certification technique.
- Backdoor attacks and their defenses in image domain: Image-domain backdoor attacks inject triggers into some training images, change their labels, and induce attacker-desired behavior when triggers appear at test time.The related work discusses BadNets and other image backdoor defenses.
- Backdoor attacks and their defenses in image domain: Image backdoor defenses include neuron pruning and trigger detection or reverse engineering, while randomized smoothing provides another certification approach.Fine-Pruning removes redundant neurons, and Neural Cleanse detects and reverse engineers triggers.
- Backdoor attacks and their defenses in image domain: Prior randomized smoothing defenses for image backdoors use additive noise, but reported certified accuracy can drop to 0 when an attacker perturbs 3 pixels on MNIST 1/7.The paper contrasts these methods with its randomized subsampling-based defense for GNN backdoors.
- Attacks to GNNs: Existing adversarial GNN studies primarily target node classification, where labels are predicted for individual nodes rather than entire graphs.The cited work considers structural perturbations that can cause widespread or attacker-chosen node misclassification.
- Randomized smoothing: Randomized smoothing is presented as a state-of-the-art route to provable robustness because it scales to large neural networks and applies to arbitrary classifiers.It was initially proposed as an empirical defense before broader certified-robustness applications.
9 Conclusion and Future Work
The conclusion establishes that GNN graph classifiers are vulnerable to subgraph backdoors and reports high attack success with limited clean-accuracy impact. It also finds that randomized smoothing is ineffective in some scenarios and calls for improved defenses.
- Conclusion: The paper concludes that GNNs are vulnerable to backdoor attacks in graph classification.This conclusion is stated directly in the paper’s final section.
- Conclusion: An attacker can poison training graphs by injecting a subgraph and changing their labels to an attacker-chosen target label.The resulting backdoored GNN is trained on the modified dataset.
- Conclusion: A backdoored GNN is very likely to predict the target label for testing graphs containing the same injected subgraph.The conclusion describes this behavior for the predefined trigger.
- Conclusion: Experiments on three real-world datasets show high attack success rates with small impacts on accuracy for clean testing graphs.The conclusion summarizes the paper’s empirical evaluation across datasets.
- Future Work: Randomized-smoothing certification is ineffective in some scenarios, motivating future work on detecting backdoored GNNs and designing new defenses.These are the two future-work directions identified by the paper.