Graph Backdoor

Zhaohan Xi; Ren Pang; Shouling Ji; Ting Wang

Source-linked AI summary

Graph Backdoor

Zhaohan Xi, Ren Pang, Shouling Ji, Ting Wang

arXiv:2006.11890v5Jun 21, 2020cs.LGcs.CRstat.ML

TL;DR

Backdoor vulnerabilities in GNNs remain largely unexplored despite their growing use with security-sensitive graph data and reusable pre-trained models. The paper introduces GTA, an adaptive subgraph-trigger attack designed to work without downstream-model knowledge across inductive and transductive tasks. GTA achieves high attack success with small accuracy losses, while the analysis highlights detection and input-space feasibility challenges.

Problem
GNN vulnerability to backdoor attacks is largely unexplored despite GNN use in security-sensitive domains and growing pre-trained-model reuse.
Method
GTA uses graph subgraphs as triggers, tailors them to individual graphs, optimizes intermediate representations, and supports inductive and transductive tasks without downstream-model knowledge.
Results
GTA is effective across tasks and models: success exceeds 91.4% inductively, 69.1% transitively, and 96.4% on off-the-shelf multi-task pre-trained GNNs.
Takeaways & Limitations
The evaluation characterizes substantial GNN backdoor vulnerability and informs more secure practices for pre-training and reusing GNNs.
Takeaways & Limitations
Input-space GTA may be infeasible when graph modifications cannot be realized, semantic constraints are difficult to model, or adversarial input control is limited.

Abstract

from arXiv · show

One intriguing property of deep neural networks (DNNs) is their inherent vulnerability to backdoor attacks -- a trojan model responds to trigger-embedded inputs in a highly predictable manner while functioning normally otherwise. Despite the plethora of prior work on DNNs for continuous data (e.g., images), the vulnerability of graph neural networks (GNNs) for discrete-structured data (e.g., graphs) is largely unexplored, which is highly concerning given their increasing use in security-sensitive domains. To bridge this gap, we present GTA, the first backdoor attack on GNNs. Compared with prior work, GTA departs in significant ways: graph-oriented -- it defines triggers as specific subgraphs, including both topological structures and descriptive features, entailing a large design spectrum for the adversary; input-tailored -- it dynamically adapts triggers to individual graphs, thereby optimizing both attack effectiveness and evasiveness; downstream model-agnostic -- it can be readily launched without knowledge regarding downstream models or fine-tuning strategies; and attack-extensible -- it can be instantiated for both transductive (e.g., node classification) and inductive (e.g., graph classification) tasks, constituting severe threats for a range of security-critical applications. Through extensive evaluation using benchmark datasets and state-of-the-art models, we demonstrate the effectiveness of GTA. We further provide analytical justification for its effectiveness and discuss potential countermeasures, pointing to several promising research directions.

1 Introduction

GTA addresses the largely unexplored vulnerability of GNNs to backdoor attacks by introducing graph-specific, adaptive, model-agnostic triggers and evaluating them across task settings. Experiments show strong attack success with small benign-accuracy losses, while adaptive triggers complicate detection and motivate mitigation research.

Motivation: GNN backdoor vulnerabilities are largely unexplored despite GNN use in security-sensitive domains and increasing reuse of pre-trained models.The paper frames this gap through malware analysis, memory forensics, fraud detection, drug discovery, and data- or training-scarce settings.
GTA: GTA is the first GNN backdoor attack, using subgraph triggers that include topology and descriptive features.The attack is designed specifically for discrete graph-structured data.
GTA: GTA tailors triggers to individual graphs and optimizes intermediate representations without requiring knowledge of downstream models or fine-tuning strategies.Input tailoring targets both effectiveness and evasiveness, while representation-level optimization supports varying downstream designs.
GTA: GTA applies to both inductive graph classification and transductive node classification tasks.This extensibility broadens the attack framework across security-critical application settings.
Evaluation: Over 91.4% inductive attack success and over 69.1% transductive attack success occur with accuracy drops below 1.4% and 2.4%, respectively.These results are reported across benchmark datasets and state-of-the-art GNN models.
Evaluation: Over 96.4% success is achieved on off-the-shelf multi-task pre-trained GNNs, while input-space GTA remains comparable to graph-space GTA despite semantic constraints.The paper also discusses countermeasure challenges caused by discrete graphs, expensive GNN inspection, and graph-dependent shortcuts.

2 Background

This section introduces GNNs as graph-to-embedding models and explains how pre-trained GNNs are combined with downstream classifiers. It also defines backdoor attacks and the threat model in which attackers modify pre-trained GNN parameters before downstream fine-tuning.

Graph neural networks: A GNN processes graph topology and descriptive features to generate node embeddings through neighborhood aggregation.The aggregation uses graph connectivity, trainable parameters, and embeddings from the previous iteration.
Graph neural networks: A readout function pools final node embeddings into a graph embedding, so the GNN represents a function zG = f(G).This graph embedding can feed a downstream classifier.
Pre-trained GNNs: Pre-trained GNNs are reused when labeled data is sparse or training is expensive, then combined with a downstream classifier for transfer learning.The downstream system may be fine-tuned fully or only through its classifier while the feature extractor remains fixed.
Backdoor attacks: A backdoor attack makes a trojan model misbehave on trigger-embedded inputs while functioning normally on benign inputs.The trigger activates a predictable malicious behavior after the model is integrated into a target system.
Threat model: The threat model perturbs a pre-trained GNN’s parameters without changing its architecture, using downstream-task data before users fine-tune the model.The adversary is assumed not to know the downstream classifier or fine-tuning strategy.

3 GTA Attack

GTA forges trojan GNNs that map trigger-embedded graphs to a target class while preserving benign behavior. It uses representation-level bi-level optimization, efficient graph substitution, and graph-specific adaptive trigger generation.

Attack overview: GTA defines triggers as subgraphs containing topological structures and descriptive features, then blends them into graphs through a mixing function.The attack seeks predictable target-class misclassification for trigger-embedded graphs while maintaining normal behavior on benign graphs.
Bi-level optimization: GTA alternates updates to the trigger and model in a bi-level optimization scheme, avoiding repeated exact re-training whenever the trigger changes.A single look-ahead gradient step approximates the model response when updating the trigger.
Attack overview: The attack optimizes trigger and model parameters through intermediate representations because the downstream classifier and fine-tuning strategy are unavailable.Attack effectiveness aligns trigger-embedded non-target graphs with target-class embeddings, while retention keeps trojan and original embeddings similar on benign graphs.
Graph mixing: The mixing operator replaces a same-sized graph substructure with the trigger, selecting the candidate with minimum graph edit distance.The search is implemented with a backtracking-based adaptation of VF2 because exact subgraph isomorphism is NP-hard.
Adaptive triggers: Adaptive trigger generation encodes each node’s features and topology, then uses neural generators to produce trigger structure and node features for an individual graph.Graph attention mechanisms encode the subgraph and its context; connectivity is determined from parameterized cosine similarity, with edges formed above 0.5.

4 Attack Evaluation

The evaluation asks how effective and evasive GTA is across inductive and transductive tasks, including off-the-shelf GNNs and varying downstream models.

Evaluation questions: The empirical study evaluates GTA’s effectiveness and evasiveness in inductive tasks, its performance on pre-trained off-the-shelf GNNs, and its effectiveness in transductive tasks.It also tests whether GTA remains agnostic to downstream models.

Experimental settings

GTA is evaluated across inductive and transductive graph tasks, transfer settings, datasets, trigger configurations, optimization ratios, feature perturbation levels, and downstream classifiers. Across these settings, it generally achieves high attack effectiveness while preserving clean-task behavior, with adaptive triggers often improving the balance between effectiveness and evasiveness.

Datasets and tasks: The evaluation uses seven datasets from security-sensitive domains and tests GTA in both inductive and transductive settings.The datasets include fingerprint, malware, biochemical, Bitcoin, and Facebook graph data.
Inductive evaluation: In inductive tasks, attacks exceed 80.2% ASR and 0.78 misclassification confidence while keeping accuracy drops below 1.9%.Average degree differences remain below 0.016 across the reported variants.
Parameter sensitivity: Increasing the inner-outer optimization ratio produces an effectiveness-evasiveness trade-off, while GTA is the least sensitive to this ratio across task settings.Increasing feature-mask coverage raises ASR but can reduce evasiveness, especially for Facebook; changing classifier type has limited impact on GTA.
Transfer and pre-training: GTA ranks above BLII and BLI in effectiveness across inductive settings and remains comparatively insensitive to downstream-data availability.With |D|/|T| = 0.2%, GTA achieves over 92.5% ASR on Toxicant.
Transfer and pre-training: On off-the-shelf pre-trained GNNs, GTA can be slightly more effective, consistent with higher transferability reducing reliance on available downstream data.For example, BLII reaches 94.1% ASR on AIDS with |D|/|T| = 5% in the off-the-shelf setting.
Parameter sensitivity: Larger triggers generally increase effectiveness while marginally reducing evasiveness in inductive tasks, with the reported evasiveness drop below 3.6%.In transductive tasks, ASR instead first increases and then slightly decreases as trigger size grows from 3 to 15.

5 Discussion

The discussion links GTA’s effectiveness to GNN complexity and adaptive trigger design, then examines detection and input-space deployment constraints. Results indicate that adaptive triggers evade MPC-based detection, while realistic input-space feasibility remains domain-dependent.

Increasing GCN depth from 1 to 3 aggregation layers raises GTA’s ASR by about 3.7% and overall accuracy by 3%.The authors therefore suggest that reducing GNN complexity may not be a viable defense because it can harm system performance.
Adaptive trigger definitions tend to require less perturbation, making GTA and benign models difficult to distinguish using MPC.MPC distributions for BLI and BLII differ across classes, whereas GTA and benign models appear more similar.
MPC-based detection can give missing or incorrect results for GTA because each graph may use a different shortcut to reach the target class.The adaptive nature of GTA weakens NeuralCleanse’s assumption of a common shortcut across trigger-embedded inputs.
Input-space GTA must map graph perturbations back to valid inputs while preserving semantic constraints such as malware functionality.The proposed formulation separates finding an input perturbation from enforcing its input-space validity.
Input-space GTA may be infeasible when graph changes cannot be realized, semantic constraints are difficult to model, or the adversary controls only part of the input.Examples include fingerprints, molecular graphs, and evolving social-network relationships.

6 Related Work

Related work covers adversarial manipulation and defenses for general DNNs, existing backdoor attacks, and attacks on GNNs. The paper positions GTA against sparse prior work on GNN backdoors by spanning both task settings and adaptive trigger optimization.

Adversarial attacks: Adversarial-attack research develops deceptive inputs and defenses such as adversarial training and detection, producing a continuing arms race.
Backdoor attacks: Backdoor attacks include class-level attacks with predefined triggers and instance-level clean-label attacks, while defenses target training data, models, or inference inputs.
Attacks against GNNs: GNN security studies have focused mainly on inference-time graph perturbations and training-time poisoning that degrades overall performance.Existing GNN defenses are largely inspired by defenses developed for related attack settings.
Attacks against GNNs: GNN backdoor vulnerabilities were largely unexplored, while concurrent work used predefined triggers rather than GTA’s broader design.The paper distinguishes GTA by considering inductive and transductive tasks, jointly optimizing triggers and trojan models, and evaluating state-of-the-art defenses.

7 Conclusion

The paper presents GTA as an in-depth study of GNN backdoor vulnerabilities and evaluates its practicality across security-critical applications. It also analyzes the vulnerability and discusses mitigation directions for safer GNN pre-training and reuse.

GTA is presented as the first attack that trojans GNNs using triggers tailored to individual graphs.
The study showcases GTA across security-critical applications and raises concerns about re-using pre-trained GNNs.
The paper provides analytical justification for GNN backdoor vulnerabilities and discusses potential mitigation.

A.1 Look-ahead step

The look-ahead implementation differentiates updates to the trojan GNN and trigger generator, using gradient-based optimization and a finite-difference approximation. The transductive algorithm repeatedly samples subgraphs and updates both parameter sets until convergence.

The chain-rule evaluation uses a one-step look-ahead parameter update, θ′ = θ−ξ∇θℓret(θ,gt).The second-order term is approximated with finite differences using a small ε, such as 10^-5.
The mixing function embeds a trigger by replacing a graph subgraph, while an extended VF2 search finds the most similar replaceable subgraph.
The transductive algorithm initializes by randomly sampling subgraphs and alternates updates to the trojan GNN parameters θ and trigger-generator parameters ω.Updates use ℓret for θ and a look-ahead attack objective for ω.
The algorithm outputs the trojan GNN θ and trigger-generation parameters ω.

B.1 Input inspection as a defense

The defense evaluates randomized smoothing and other input-inspection strategies against GTA. Randomized smoothing faces a trade-off between attack robustness and clean accuracy, while graph structure makes methods such as STRIP difficult to apply.

Randomized smoothing: Randomized smoothing subsamples graph structure and node features, then uses majority voting over predictions for the final graph prediction.The subsampling ratio β controls the sampling process, reducing the likelihood that a trigger remains effective across sampled graphs.
Randomized smoothing: In the ChEMBL→Toxicant transfer case, smaller β lowers ASR but increases CAD, exposing a trade-off between attack robustness and clean accuracy.Figure 13 reports attack effectiveness and evasiveness as functions of β.
Randomized smoothing: Because subsampling can negatively affect system performance, randomized smoothing may not be viable for defending against GTA.
Other input-inspection defenses: Input-inspection defenses developed for continuous domains are often challenging to extend to discrete graph data.
Other input-inspection defenses: STRIP is intrinsically difficult to apply to graphs because meaningfully mixing two graph-structured inputs is challenging.STRIP relies on trigger-dominated mixtures producing low-entropy predictions, but graph mixing is not straightforward.

B.2 Input-space attacks

Input-space GTA constructs triggers by perturbing graph substructures, including topology and node features, while supporting constraints that can limit where and how perturbations occur. Android call-graph visualizations illustrate these perturbations around selected methods.

Android call graphs: Android call graphs associate 40 descriptive features with each node, and their perturbation constraints are summarized in Table 11.
Android call graphs: Input-space GTA visualizes adaptive triggers by perturbing only external methods and adding no-op calls alongside original call edges.Figure 14 distinguishes external and Android internal methods, perturbed methods, original calls, and added no-op calls.
Topological structures: Topological constraints govern which edges may change when GTA replaces a subgraph g with trigger gt.The replacement is computed through an alternative adjacency matrix and can be restricted by edge-specific rules.
Topological structures: A binary mask can preserve selected adjacency entries while replacing the remaining entries with those from the trigger adjacency matrix.This supports excluding specific node pairs from perturbation.
Topological structures: Additional topological constraints restrict perturbations to edge addition or deletion, penalize perturbation magnitude, or require subgraph isomorphism.Perturbation magnitude is regularized with the Frobenius norm ∥A−˜A∥F.
Node features: Node-feature constraints replace node vectors selectively, using a binary feature mask to exclude chosen features from perturbation.The same masking principle preserves selected components of Xi while replacing others with corresponding trigger features.