Graph Backdoor

Introduction

Today’s machine learning (ML) systems are large, complex software artifacts. Due to the ever-increasing system scale and training cost, it becomes not only tempting but also necessary to re-use pre-trained models in building ML systems. It was estimated that as of 2016, over 13.7% of ML-related repositories on GitHub use at least one pre-trained model. On the upside, this “plug-and-play” paradigm significantly simplifies the development cycles of ML systems. On the downside, as most pre-trained models are contributed by untrusted third parties (e.g., ModelZoo), their lack of standardization or regulation entails profound security implications.

In particular, pre-trained models are exploitable to launch backdoor attacks, one immense threat to the security of ML systems. In such attacks, a trojan model forces its host system to misbehave when certain pre-defined conditions (“triggers”) are present but function normally otherwise. Motivated by this, intensive research has been conducted on backdoor attacks on general deep neural network (DNN) models, either developing new attack variants or improving DNN resilience against existing attacks.

Surprisingly, despite the plethora of prior work, the vulnerabilities of graph neural network (GNN) models to backdoor attacks are largely unexplored. This is highly concerning given that (i) graph-structured data has emerged in various security-sensitive domains (e.g., malware analysis, memory forensics, fraud detection, and drug discovery), (ii) GNNs have become the state-of-the-art tools to conduct analysis over such data, and (iii) pre-trained GNNs have gained increasing use in domains wherein task-specific labeled graphs are scarce and/or training costs are expensive. In this paper, we seek to bridge this gap by answering the following questions:

RQ1 – Are GNNs ever susceptible to backdoor attacks?

RQ2 – How effective are the attacks under various practical settings (e.g., on off-the-shelf GNNs or in input spaces)?

RQ3 – What are the potential countermeasures?

Our work – This work represents the design, implementation, and evaluation of Gta,Gta: Graph Trojaning Attack. the first backdoor attack on GNNs. Compared with prior work on backdoor attacks (e.g.,), Gta departs in significant ways.

Graph-oriented – Unlike structured, continuous data (e.g., images), graph data is inherently unstructured and discrete, requiring triggers to be of the same nature. Gta defines triggers as specific subgraphs, including both topological structures and descriptive (node and edge) features, which entails a large design spectrum for the adversary.

Input-tailored – Instead of defining a fixed trigger for all the graphs, Gta generates triggers tailored to the characteristics of individual graphs, which optimizes both attack effectiveness (e.g., misclassification confidence) and evasiveness (e.g., perturbation magnitude). Figure 1 illustrates how Gta adapts triggers to specific input graphs.

Downstream-model-agnostic – We assume a realistic setting wherein the adversary has no knowledge regarding downstream models or fine-tuning strategies. Rather than relying on final predictions, Gta optimizes trojan GNNs with respect to intermediate representations, leading to its resistance to varying system design choices.

Attack-extensible – Gta represents an attack framework that can be instantiated for various settings, such as inductive (e.g., graph classification) and transductive (e.g., node classification) tasks, thereby constituting severe threats for a range of security-critical domains (e.g., toxic chemical classification).

We validate the practicality of Gta using a range of state-of-the-art GNN models and benchmark datasets, leading to the following interesting findings.

RA1 – We demonstrate that GNNs are highly vulnerable to backdoor attacks under both inductive and transductive settings. In inductive tasks, the trojan models force their host systems to misclassify trigger-embedded graphs to target classes with over 91.4% success rate, while incurring less than 1.4% accuracy drop; in transductive tasks, the trojan models cause the misclassification of target nodes with over 69.1% success rate, while incurring less than 2.4% accuracy drop.

RA2 – We also evaluate Gta on pre-trained GNNs “in the wild”. On off-the-shelf models pre-trained under the multi-task setting, Gta attains an even higher (over 96.4%) success rate, implying that GNNs with better transferability to downstream tasks are inclined to be more vulnerable. We further consider input-space attacks, in which non-graph inputs are first converted to graphs for GNNs to process, while Gta needs to ensure perturbed graphs to satisfy the semantic constraints of the input space. We show that, despite the extra constraints, the performance of input-space Gta is comparable with their graph-space counterpart.

RA3 – Finally, we discuss potential countermeasures and their technical challenges. Although it is straightforward to conceive high-level mitigation such as more principled practices of re-using pre-trained GNNs, it is challenging to concretely implement such strategies. For instance, inspecting a pre-trained GNN for potential backdoors amounts to searching for abnormal “shortcut” patterns in the input space, which entails non-trivial challenges due to the discrete structures of graph data and the prohibitive complexity of GNNs. Even worse, because of the adaptive nature of Gta, such shortcuts may vary with individual graphs, rendering them even more evasive to detection.

Contributions – To our best knowledge, this work represents the first study on the vulnerabilities of GNNs to backdoor attacks. Our contributions are summarized as follows.

We present Gta, the first backdoor attack on GNNs, which highlights with the following features: (i) it uses subgraphs as triggers; (ii) it tailors trigger to individual graphs; (iii) it assumes no knowledge regarding downstream models; (iv) it also applies to both inductive and transductive tasks.

We empirically demonstrate that Gta is effective in a range of security-critical tasks, evasive to detection, and agnostic to downstream models. The evaluation characterizes the inherent vulnerabilities of GNNs to backdoor attacks.

We provide analytical justification for the effectiveness of Gta and discuss potential mitigation. This analysis sheds light on improving the current practice of re-using pre-trained GNN models, pointing to several research directions.

Background

Graph neural network (GNN) – A GNN takes as input a graph $G$, including its topological structures and descriptive features, and generates a representation (embedding) ${z}_{\scaleobj{0.8}{v}}$ for each node $v$. Let $Z$ denote the node embeddings in the matrix form. We consider GNNs built upon the neighborhood aggregation paradigm: ${Z}^{\scaleobj{0.8}{(k)}}=\mathsf{Aggregate}\left(A,{Z}^{\scaleobj{0.8}{(k-1)}};{\theta}^{\scaleobj{0.8}{(k)}}\right)$, where ${Z}^{\scaleobj{0.8}{(k)}}$ is the node embeddings after the $k$-th iteration and also the “messages” to be passed to neighboring nodes, and the aggregation function depends on the adjacency matrix $A$, the trainable parameters ${\theta}^{\scaleobj{0.8}{(k)}}$, and the node embeddings ${Z}^{\scaleobj{0.8}{(k-1)}}$ from the previous iteration. Often ${Z}^{\scaleobj{0.8}{(0)}}$ is initialized as $G$’s node features. To obtain the graph embedding ${z}_{\scaleobj{0.8}{G}}$, a readout function pools the node embeddings from the final iteration $K$: ${z}_{\scaleobj{0.8}{G}}=\mathsf{Readout}\left({Z}^{\scaleobj{0.8}{(K)}}\right)$. Overall, a GNN models a function $f$ that generates ${z}_{\scaleobj{0.8}{G}}=f(G)$ for $G$.

Pre-trained GNN – With the widespread use of GNN models, it becomes attractive to reuse pre-trained DNNs for domains wherein either labeled data is sparse or training is expensive. Under the transfer setting, as illustrated in Figure 2, a pre-trained GNN $f$ is composed with a downstream classifier $h$ to form an end-to-end system. For instance, in a toxic chemical classification task, given a molecular graph $G$, it is first mapped to its embedding ${z}_{\scaleobj{0.8}{G}}=f(G)$ and then classified as ${y}_{\scaleobj{0.8}{G}}=h({z}_{\scaleobj{0.8}{G}})$. Compared with $f$, $h$ is typically much simpler (e.g., one fully-connected layer). Note that the data to pre-train $f$ tends to differ from the downstream task but share similar features (e.g., general versus toxic molecules). It is often necessary to fine-tune the system. One may opt to perform full-tuning to train both $f$ and $h$ or partial-tuning to only train $h$ but with $f$ fixed.

Backdoor attack – Using trojan models as the attack vector, backdoor attacks inject malicious functions into target systems, which are invoked when certain pre-defined conditions (“triggers”) are present. Given the increasing use of DNNs in security-critical domains, the adversary is incentivized to forge trojan models and lure users to re-use them. Typically, a trojan model responds to trigger-embedded inputs (e.g., images with specific watermarks) in a highly predictable manner (e.g., misclassified to a particular class) but functions normally otherwise; once it is integrated into a target system, the adversary invokes such malicious functions via trigger-embedded inputs during system use.

Threat models – Following the existing work, we assume a threat model as shown in Figure 2. Given a pre-trained GNN ${f}_{\scaleobj{0.8}{\theta_{\circ}}}$ (parameterized by ${\theta}_{\scaleobj{0.8}{\circ}}$), the adversary forges a trojan GNN ${f}_{\scaleobj{0.8}{\theta}}$ via perturbing its parameters without modifying its architecture (otherwise detectable by checking $f$’s specification). We assume the adversary has access to a dataset ${\mathcal{D}}$ sampled from the downstream task. Our empirical evaluation shows that often a fairly small amount (e.g., 1%) of the training data from the downstream task suffices (details in § 4). After integrating ${f}_{\scaleobj{0.8}{\theta}}$ with a downstream classifier $h$ to form the end-to-end system, the user performs fine-tuning for the downstream task. To make the attack more practical, we assume the adversary has no knowledge regarding what classifier $h$ is used or how the system is fine-tuned.

GTA Attack

At a high level, Gta forges trojan GNNs, which, once integrated into downstream tasks, cause host systems to respond to trigger-embedded graphs in a highly predictable manner.

For simplicity, we exemplify with the graph classification task to illustrate Gta and discuss its extension to other settings (e.g., transductive learning) in § 3.6.

Given a pre-trained GNN ${\theta}_{\scaleobj{0.8}{\circ}}$,As Gta does not modify the model architecture, below we use $\theta$ to refer to both the model and it parameter configuration. the adversary aims to forge a trojan model $\theta$ so that in the downstream task, $\theta$ forces the host system to misclassify all the trigger-embedded graphs to a designated class ${y}_{\scaleobj{0.8}{t}}$, while functioning normally on benign graphs. Formally, we define the trigger as a subgraph ${g}_{\scaleobj{0.8}{t}}$ (including both topological structures and descriptive features), and a mixing function $m(\cdot;{g}_{\scaleobj{0.8}{t}})$ that blends ${g}_{\scaleobj{0.8}{t}}$ with a given graph $G$ to generate a trigger-embedded graph $m(G;{g}_{\scaleobj{0.8}{t}})$. Therefore, the adversary’s objective can be defined as:

where $h$ is the downstream classifier after fine-tuning and $G$ denotes an arbitrary graph in the task. Intuitively, the first objective specifies that all the trigger-embedded graphs are misclassified to the target class (i.e., attack effectiveness), while the second objective ensures that the original and trojan GNNs are indistinguishable in terms of their behaviors on benign graphs (i.e., attack evasiveness).

However, searching for the optimal trigger ${g}_{\scaleobj{0.8}{t}}$ and trojan model $\theta$ in Eq (1) entails non-trivial challenges.

As the adversary has no access to downstream model $h$, it is impractical to directly optimize ${g}_{\scaleobj{0.8}{t}}$ and $\theta$ based on Eq (1).

Due to the mutual dependence of ${g}_{\scaleobj{0.8}{t}}$ and $\theta$, every time updating ${g}_{\scaleobj{0.8}{t}}$ requires the expensive re-computation of $\theta$.

There are combinatorial ways to blend ${g}_{\scaleobj{0.8}{t}}$ with a given graph $G$, implying a prohibitive search space.

Using a universal trigger ${g}_{\scaleobj{0.8}{t}}$ for all the graphs ignores the characteristics of individual graphs, resulting in suboptimal and easy-to-detect attacks.

To the above challenges, (i) instead of associating ${g}_{\scaleobj{0.8}{t}}$ and $\theta$ with final predictions, we optimize them with respect to intermediate representations; (ii) we adopt a bi-level optimization formulation, which considers ${g}_{\scaleobj{0.8}{t}}$ as the hyper-parameters and $\theta$ as the model parameters and optimizes them in an interleaving manner; (iii) we implement the mixing function $m(G;{g}_{\scaleobj{0.8}{t}})$ as an efficient substitution operator, which finds and replaces within $G$ the subgraph $g$ most similar to ${g}_{\scaleobj{0.8}{t}}$; and (iv) we introduce the concept of adaptive trigger, that is, ${g}_{\scaleobj{0.8}{t}}$ is specifically optimized for each given graph $G$.

The overall framework of Gta is illustrated in Figure 3. In the following, we elaborate on each key component.

2 Bi-level optimization

Recall that the adversary has access to a dataset ${\mathcal{D}}$ sampled from the downstream task, which comprises a set of instances $(G,{y}_{\scaleobj{0.8}{G}})$ with $G$ being a graph and ${y}_{\scaleobj{0.8}{G}}$ as its class. We formulate the bi-level optimization objective with ${g}_{\scaleobj{0.8}{t}}$ and $\theta$ as the upper- and lower-level variables:

where $\Delta(\cdot,\cdot)$ measures the embedding dissimilarity, which is instantiated as $L_{2}$ distance in our current implementation.

where $\xi$ is the learning rate of the look-ahead step.

3 Mixing function

The mixing function $m(G;{g}_{\scaleobj{0.8}{t}})$ fulfills two purposes: (i) for a given trigger ${g}_{\scaleobj{0.8}{t}}$, it identifies the optimal to-be-replaced subgraph $g$ within a given graph $G$; and (ii) it performs the substitution of $g$ with ${g}_{\scaleobj{0.8}{t}}$. Apparently, there are combinatorial ways to define $m(G;{g}_{\scaleobj{0.8}{t}})$, resulting in a prohibitive search space.

To address this challenge, we restrict the mixing function to an efficient substitution operator; that is, $m(G;{g}_{\scaleobj{0.8}{t}})$ replaces a subgraph $g$ in $G$ with ${g}_{\scaleobj{0.8}{t}}$. To maximize the attack evasiveness, it is desirable to use a subgraph similar to ${g}_{\scaleobj{0.8}{t}}$. We thus specify the constraints that (i) $g$ and ${g}_{\scaleobj{0.8}{t}}$ are of the same size (i.e., the same number of nodes) and (ii) they have the minimum graph edit distance (i.e., edge addition or deletion).

It is known that finding in a given graph $G$ a subgraph $g$ identical to ${g}_{\scaleobj{0.8}{t}}$ (subgraph isomorphism) is NP-hard. We adapt a backtracking-based algorithm Vf2 to our setting. Intuitively, Vf2 recursively extends a partial match by mapping the next node in ${g}_{\scaleobj{0.8}{t}}$ to a node in $G$ if feasible, and backtracks otherwise. As we search for the most similar subgraph, we maintain the current highest similarity and terminate a partial match early if it exceeds this threshold. The detailed implementation is deferred to § A.2.

4 Trigger generation

In the formulation of Eq (2), we assume a universal trigger for all the graphs. Despite its simplicity for implementation, fixing the trigger entails much room for optimization: (i) it ignores the characteristics of individual graphs and results in less effective attacks; (ii) it becomes a pattern shared by trigger-embedded graphs and makes them easily detectable. We thus postulate whether it is possible to generate triggers tailored to individual graphs to maximize the attack effectiveness and evasiveness.

We design an adaptive trigger generation function ${\phi}_{\scaleobj{0.8}{\omega}}(\cdot)$, which proposes a trigger ${g}_{\scaleobj{0.8}{t}}$ tailored to a given subgraph $g$ within $G$. At a high level, ${\phi}_{\scaleobj{0.8}{\omega}}(\cdot)$ comprises two key operations: (i) it first maps each node $i$ in $g$ to its encoding $z_{i}$, which encodes both $g$’s node features and topological structures; (ii) it applies two generator functions structured by neural networks, the first mapping $g$’s node encodings to ${g}_{\scaleobj{0.8}{t}}$’s topological structures and the second mapping $g$’s node encodings to ${g}_{\scaleobj{0.8}{t}}$’s node features. Next, we elaborate on the design of ${\phi}_{\scaleobj{0.8}{\omega}}(\cdot)$.

How to map $\bm{g}$’s encoding to $\bm{g_{t}}$? Recall that ${g}_{\scaleobj{0.8}{t}}$ comprises two parts, its topological structures and node features.

How to resolve the dependence of $\bm{g}$ and $\bm{g_{t}}$? Astute readers may point out that the mixing function $g=m(G;{g}_{\scaleobj{0.8}{t}})$ and the trigger generation function ${g}_{\scaleobj{0.8}{t}}={\phi}_{\scaleobj{0.8}{\omega}}(g)$ are mutually dependent: the generation of ${g}_{\scaleobj{0.8}{t}}$ relies on $g$, while the selection of $g$ depends on ${g}_{\scaleobj{0.8}{t}}$. To resolve this “chicken-and-egg” problem, we update $g$ and ${g}_{\scaleobj{0.8}{t}}$ in an interleaving manner.

5 Implementation and optimization

Putting everything together, Algorithm 1 sketches the flow of Gta attack. At its core, it alternates between updating the model $\theta$, the trigger generation function ${\phi}_{\scaleobj{0.8}{\omega}}(\cdot)$, and the selected subgraph $g$ for each $G\in{\mathcal{D}}[\scaleobj{0.6}{\backslash}y_{t}]$ (line 4 to 6). Below we present a suite of optimization to improve the attack.

Subgraph stabilization – It is observed in our empirical evaluation that stabilizing the selected subgraph $g$ for each $G\in{\mathcal{D}}[\scaleobj{0.6}{\backslash}y_{t}]$ by running the subgraph update step (line 6) for multiple iterations (e.g., 5 times), with the trigger generation function fixed, often leads to faster convergence.

Model restoration – Once trojan GNN ${f}_{\scaleobj{0.8}{\theta}}$ is trained, the adversary may opt to restore classifier ${h}_{\scaleobj{0.8}{\circ}}$ (not the downstream classifier $h$) with respect to the pre-training task. Due to the backdoor injection, ${h}_{\scaleobj{0.8}{\circ}}$ may not match ${f}_{\scaleobj{0.8}{\theta}}$. The adversary may fine-tune ${h}_{\scaleobj{0.8}{\circ}}$ using the training data from the pre-training task. This step makes the accuracy of the released model ${h}_{\scaleobj{0.8}{\circ}}\circ{f}_{\scaleobj{0.8}{\theta}}$ match its claims, thereby passing model inspection.

6 Extension to transductive learning

We assume the following setting. The adversary has access to $G$ as well as the classifier. For simplicity, we denote by ${f}_{\scaleobj{0.8}{\theta}}(v;G)$ the complete system that classifies a given node $v$ within $G$. Further, given an arbitrary subgraph $g$ in $G$, by substituting $g$ with the trigger ${g}_{\scaleobj{0.8}{t}}$, the adversary aims to force the unlabeled nodes within $K$ hops to $g$ to be misclassified to the target class ${y}_{\scaleobj{0.8}{t}}$, where $K$ is the number GNN layers. Recall that for neighborhood aggregation-based GNNs, a node exerts its influence to other nodes at most $K$ hops away; this goal upper-bounds the attack effectiveness.

We re-define the loss functions in Eq (3) and (4) as:

Attack Evaluation

Next, we conduct an empirical study of Gta to answer the following key questions:

Q1 – How effective/evasive is Gta in inductive tasks?

Q2 – How effective is it on pre-trained, off-the-shelf GNNs?

Q3 – How effective/evasive is it in transductive tasks?

Q4 – Is Gta agnostic to downstream models?

Datasets – We primarily use 7 datasets drawn from security-sensitive domains. (i) Fingerprint – graph representations of fingerprint shapes from the NIST-4 database; (ii) WinMal – Windows PE call graphs of malware and goodware; (iii) AIDS and (iv) Toxicant – molecular structure graphs of active and inactive compounds; (v) AndroZoo - call graphs of benign and malicious APKs collected from AndroZoo; (vi) Bitcoin – an anonymized Bitcoin transaction network with each node (transaction) labeled as legitimate or illicit; and (vii) Facebook – a page-page relationship network with each node (Facebook page) annotated with the page properties (e.g., place, organization, product). The dataset statistics are summarized in Table 1. Among them, we use the datasets (i-v) for the inductive setting and the rest (vi-vii) for the transductive setting.

Models – In our evaluation, we use 3 state-of-the-art GNN models: Gcn, GraphSAGE, and Gat. Using GNNs of distinct network architectures (i.e., graph convolution, general aggregation function, versus graph attention), we factor out the influence of the characteristics of individual models. The performance of systems built upon clean GNN models is summarized in Table 2.

Baselines – To our best knowledge, Gta is the first backdoor attack on GNNs. We thus mainly compare Gta with its variants as baselines: ${\textsc{Bl}}^{\scaleobj{0.8}{\text{I}}}$, which fixes the trigger as a complete subgraph and optimizes a feature vector shared by all its nodes, and ${\textsc{Bl}}^{\scaleobj{0.8}{\text{II}}}$, which optimizes the trigger’s connectivity and the feature vector of each of its nodes. Both ${\textsc{Bl}}^{\scaleobj{0.8}{\text{I}}}$ and ${\textsc{Bl}}^{\scaleobj{0.8}{\text{II}}}$ assume a universal trigger for all the graphs, while Gta optimizes the trigger’s topological connectivity and node features with respect to each graph. Intuitively, ${\textsc{Bl}}^{\scaleobj{0.8}{\text{I}}}$, ${\textsc{Bl}}^{\scaleobj{0.8}{\text{II}}}$, and Gta represent different levels of trigger adaptiveness.

In each set of experiments, we apply the same setting across all the attacks, with the default parameter setting summarized in Table 10. In particular, in each dataset, we assume the class with the smallest number of instances to be the target class ${y}_{\scaleobj{0.8}{t}}$ designated by the adversary (cf. Table 1), to minimize the impact of unbalanced data distributions.

Metrics – To evaluate attack effectiveness, we use two metrics: (i) attack success rate (ASR), which measures the likelihood that the system classifies trigger-embedded inputs to the target class ${y}_{\scaleobj{0.8}{t}}$ designated by the adversary:

and (ii) average misclassification confidence (AMC), which is the average confidence score assigned to class ${y}_{\scaleobj{0.8}{t}}$ by the system with respect to successful attacks. Intuitively, higher ASR and AMC indicate more effective attacks.

To evaluate the attack evasiveness, we use four metrics: (i) clean accuracy drop (CAD), which measures the difference of classification accuracy of two systems built upon the original GNN and its trojan counterpart with respect to clean graphs; (ii) average degree difference (ADD), (iii) average eccentricity change (AEC), and (iv) algebraic connectivity change (ACC), which respectively measure the difference of average degrees, eccentricity, and algebraic connectivity of clean graphs and their trigger-embedded counterparts.

Q1: Is GTA effective in inductive tasks?

This set of experiments evaluate Gta under the inductive setting, in which a pre-trained GNN is used in a downstream graph classification task. Based on the relationship between pre-training and downstream tasks, we consider two scenarios.

(i) Non-transfer – In the case that the two tasks share the same dataset, we partition the overall dataset ${\mathcal{T}}$ into 40% and 60% for the pre-training and downstream tasks respectively. We assume the adversary has access to 1% of ${\mathcal{T}}$ (as ${\mathcal{D}}$) to forge trojan models. In the evaluation, we randomly sample 25% from the downstream dataset to construct trigger-embedded graphs and the rest as clean inputs.

(ii) Transfer – In the case that the two tasks use different datasets, in the pre-training task, we use the whole dataset for GNN pre-training; in the downstream task, we randomly partition the dataset ${\mathcal{T}}$ into 40% and 60% for system fine-tuning and testing respectively. By default, we assume the adversary has access to 1% of ${\mathcal{T}}$. Similar to the non-transfer case, we sample 25% from the testing set of ${\mathcal{T}}$ to build trigger-embedded graphs and the rest as clean inputs.

In both cases, we assume the adversary has no knowledge regarding downstream models or fine-tuning strategies. By default, we use a fully-connected layer plus a softmax layer as the downstream classifier and apply full-tuning over both the GNN and the classifier.

Attack efficacy – Table 3 summarizes the performance of different variants of Gta in inductive tasks. Overall, in both non-transfer and transfer settings, all the attacks achieve high attack effectiveness (each with an attack success rate over $80.2\%$ and misclassification confidence over $0.78$), effectively retain the accuracy of pre-trained GNNs (with accuracy drop below $1.9\%$), and incur little impact on the statistics of input graphs (with average degree difference below 0.016), which highlights the practicality of backdoor attacks against GNN models. The attacks are ranked as Gta > ${\textsc{Bl}}^{\scaleobj{0.8}{\text{II}}}$ > ${\textsc{Bl}}^{\scaleobj{0.8}{\text{I}}}$ in terms of ASR. This may be explained by that the trigger adaptiveness exploits the characteristics of individual graphs, leading to more effective attacks. Note that in the transfer cases, ${\textsc{Bl}}^{\scaleobj{0.8}{\text{II}}}$ attains slightly higher evasiveness (accuracy retention) than Gta. This is perhaps because given its higher flexibility, to retain the accuracy over clean inputs, Gta requires more data from the downstream task to constrain its optimization. To validate this hypothesis, we increase the amount of ${\mathcal{T}}$ accessible by the adversary to 5%. Observe that under this setting Gta attains the highest accuracy retention.

Q2: Is GTA effective on off-the-shelf GNNs?

Besides models trained from scratch, we further consider pre-trained GNNs “in the wild”. We use a Gcn modelhttps://github.com/snap-stanford/pre-train-gnns/ that is pre-trained with graph-level multi-task supervised training on the ChEMBL dataset, containing 456K molecules with 1,310 kinds of diverse biochemical assays. We transfer this model to the tasks of classifying the AIDS and Toxicant datasets. The default setting is identical to the transfer case.

Attack efficacy – Table 4 summarizes the attack efficacy of Gta on the pre-trained GNN under varying settings of the available data ($|{\mathcal{D}}|/|{\mathcal{T}}|$). We have the observations below.

First, across all the cases, the three attacks are ranked as Gta > ${\textsc{Bl}}^{\scaleobj{0.8}{\text{II}}}$ > ${\textsc{Bl}}^{\scaleobj{0.8}{\text{I}}}$ in terms of their effectiveness, highlighting the advantage of using flexible trigger definitions.

Second, the effectiveness of Gta increases as more data from the downstream task becomes available. For instance, the ASR of ${\textsc{Bl}}^{\scaleobj{0.8}{\text{I}}}$ grows about 30% as $|{\mathcal{D}}|/|{\mathcal{T}}|$ increases from 0.2 to 5% on AIDS. In comparison, Gta is fairly insensitive to the available data. For instance, with $|{\mathcal{D}}|/|{\mathcal{T}}|=0.2\%$, it attains over 92.5% ASR on Toxicant.

Third, by comparing Table 3 and 4, it is observed that Gta appears slightly more effective on the off-the-shelf GNN. For instance, with $|{\mathcal{D}}|/|{\mathcal{T}}|=5\%$, ${\textsc{Bl}}^{\scaleobj{0.8}{\text{II}}}$ attains 86.1% and 94.1% ASR on the trained-from-scratch and off-the-shelf GNN models respectively on AIDS. This is perhaps explained by that the models pre-trained under the multi-task supervised setting tend to have superior transferability to downstream tasks, which translates into more effective backdoor attacks and less reliance on available data.

Q3: Is GTA effective in transductive tasks?

We now evaluate Gta under the transductive setting, in which given a graph and a set of labeled nodes, the system classifies the remaining unlabeled nodes. Specifically, given a subgraph $g$ in $G$ (designated by the adversary), by replacing $g$ with the trigger ${g}_{\scaleobj{0.8}{t}}$, the adversary aims to force all the unlabeled nodes within $K$ hops of ${g}_{\scaleobj{0.8}{t}}$ (including ${g}_{\scaleobj{0.8}{t}}$) to be classified to target class ${y}_{\scaleobj{0.8}{t}}$, where $K$ is the number of layers of the GNN.

Attack efficacy – Table 5 summarizes the attack performance of Gta. Similar to the inductive case (cf. Table 3), Gta outperforms the rest by a larger margin in the transductive tasks. For instance, on Bitcoin, Gta attains 37.6% and 21.1% higher ASR than ${\textsc{Bl}}^{\scaleobj{0.8}{\text{I}}}$ and ${\textsc{Bl}}^{\scaleobj{0.8}{\text{II}}}$ respectively. This is explained as follows. Compared with the inductive tasks, the graphs in the transductive tasks tend to be much larger (e.g., thousands versus dozens of nodes) and demonstrate more complicated topological structures; being able to adapt trigger patterns to local topological structures significantly boosts the attack effectiveness. Further, between the two datasets, the attacks attain higher ASR on Bitcoin, which may be attributed to that all the node features in Facebook are binary-valued, negatively impacting the effectiveness of feature perturbation.

Q4: Is GTA agnostic to downstream models?

We now instantiate the downstream classifier with alternative models (with the GNN fixed as Gcn), including Naïve Bayes (Nb), Random Forest (Rf), and Gradient Boosting (Gb). We evaluate the impact of the classifier on different attacks in the transfer case of ChEMBL$\rightarrow$Toxicant, with results in Table 6. Observe that the classifier has a limited impact on Gta. For instance, compared with Table 4 ($|{\mathcal{D}}|/|{\mathcal{T}}|$=1%), the ASR and CAD of Gta vary by less than 9.4% and 0.6%, respectively, implying its insensitivity to the classifier.

Yet, compared with GNNs, most downstream classifiers are fairly simple and tend to show strong pseudo-linearity. One may thus suggest mitigating Gta by adopting complex downstream models. However, complex models are difficult to train especially when the training data is limited, which is often the case in transfer learning.

Discussion

Today’s GNNs are complex artifacts designed to model highly non-linear, non-convex functions over graphs. Recent studies show that with GNNs are expressive enough for powerful graph isomorphism tests. These observations may partially explain why, with careful perturbation, a GNN is able to “memorize” trigger-embedded graphs yet without comprising its generalizability on other benign graphs.

To validate this hypothesis, we empirically assess the impact of model complexity on the attack effectiveness of Gta. We use the transfer case of Toxicant $\rightarrow$AIDS in § 4 as a concrete example. We train three distinct Gcn models with 1-, 2-, and 3-aggregation layers respectively, representing different levels of model complexity. We measure their clean accuracy and the ASR of Gta on such models, with results in Table 7.

Observe that increasing model complexity benefits the attack effectiveness. As the layer number varies from 1 to 3, the ASR of Gta grows by about 3.7%. We may thus postulate the existence of the correlation between model complexity and attack effectiveness. Meanwhile, increasing model complexity also improves the system performance, that is, the overall accuracy increases by 3%. Therefore, reducing GNN complexity may not be a viable option for defending against Gta, as it may negatively impact system performance.

2 Potential countermeasures

As Gta represents a new class of backdoor attacks, one possibility is to adopt the mitigation in other domains (e.g., images) to defend against Gta. The existing defenses can be roughly classified into two major categories: identifying suspicious models during model inspection (e.g.,), and detecting trigger-embedded inputs at inference time (e.g.,). We thus extend NeuralCleanse (Nc) and Randomized-Smoothing (Rs) as the representative defenses of the two categories, and evaluate their effectiveness against Gta (details of Rs deferred to § B.1).

Model inspection – We aim to detect suspicious GNNs and potential backdoors at the model inspection stage. We consider Nc as a representative method, upon which we build our defense against Gta. Intuitively, given a DNN, Nc searches for potential backdoors in every class. If a class is embedded with a backdoor, the minimum perturbation ($L_{1}$-norm) necessary to change all the inputs in this class to the target class is abnormally smaller than other classes.

To apply this defense in our context, we introduce the definition below. Given trigger ${g}_{\scaleobj{0.8}{t}}$ and to-be-replaced subgraph $g$, let ${g}_{\scaleobj{0.8}{t}}$ comprise nodes $v_{1},\ldots,v_{n}$ and $g$ correspondingly comprise $u_{1},\ldots,u_{n}$. The cost of substituting $g$ with ${g}_{\scaleobj{0.8}{t}}$ is measured by the $L_{1}$ distance of their concatenated features:

where ${X}_{\scaleobj{0.8}{v_{i}}}$ is $v_{i}$’s feature vector (including both its topological and descriptive features) and $\uplus$ denotes the concatenation operator. Intuitively, this measure accounts for both topology and feature perturbation.

We assume a set of benign graphs ${\mathcal{D}}$. Let ${{\mathcal{D}}}_{\scaleobj{0.8}{y}}$ be the subset of ${\mathcal{D}}$ in class $y$ and ${{\mathcal{D}}}_{\scaleobj{0.8}{\scaleobj{0.6}{\backslash}y}}$ as the rest. For each class $y$, we search for the optimal trigger ${g}_{\scaleobj{0.8}{t}}$ to change the classification of all the graphs in ${{\mathcal{D}}}_{\scaleobj{0.8}{\scaleobj{0.6}{\backslash}y}}$ to $y$. The optimality is defined in terms of the minimum perturbation cost (MPC):

where $G\ominus g\oplus{g}_{\scaleobj{0.8}{t}}$ denotes $G$ after substituting $g$ with ${g}_{\scaleobj{0.8}{t}}$.

We consider three settings for searching for triggers: (i) the trigger ${g}_{\scaleobj{0.8}{t}}^{\scaleobj{0.8}{\text{I}}}$ with topology and features universal for all the graphs in ${{\mathcal{D}}}_{\scaleobj{0.8}{\scaleobj{0.6}{\backslash}y}}$; (ii) the trigger ${g}_{\scaleobj{0.8}{t}}^{\scaleobj{0.8}{\text{II}}}$ with universal topology but features adapted to individual graphs; and (iii) the trigger ${g}_{\scaleobj{0.8}{t}}^{\scaleobj{0.8}{\text{III}}}$ with both topology and features adapted to individual graphs.

Results and analysis – We evaluate the above defense in the transfer case of pre-trained, off-the-shelf GNN models (ChEMBL$\rightarrow$Toxicant). We sample 100 graphs from each class (‘0’ and ‘1’) of the Toxicant dataset to form ${\mathcal{D}}$. For comparison, we also run the search on a benign GNN. All the attacks consider ‘1’ as the target class. Figure 12 visualizes the MPC measures with respect to each class under varying settings of GNNs, attacks, and trigger definitions.

We have the following observations. First, even on benign models, the MPC measure varies across different classes, due to their inherent distributional heterogeneity. Second, on the same model (each column), the measure decreases as the trigger definition becomes more adaptive as tailoring to individual graphs tends to lead to less perturbation. Third, under the same trigger definition (each row), ${\textsc{Bl}}^{\scaleobj{0.8}{\text{I}}}$ and ${\textsc{Bl}}^{\scaleobj{0.8}{\text{II}}}$ show significantly disparate MPC distributions across the two classes, while the MPC distributions of Gta and benign models seem fairly similar, implying the difficulty of distinguishing GNNs trojaned by Gta based on their MPC measures.

To validate the observations, on each model, we apply the one-tailed Kolmogorov-Smirnov test between the MPC distributions of the two classes, with the null hypothesis being that the MPC of the target class is significantly lower than the other class. Table 8 summarizes the results. Observe that regardless of the trigger definition, ${\textsc{Bl}}^{\scaleobj{0.8}{\text{I}}}$ and ${\textsc{Bl}}^{\scaleobj{0.8}{\text{II}}}$ show large $p$-values ($\geq 0.08$), thereby lacking support to reject the null hypothesis; meanwhile, the benign GNN and Gta demonstrate much smaller $p$-values ($<0.001$), indicating strong evidence to reject the null hypothesis (i.e., the MPC of the target class is not significantly lower). Thus, relying on MPC to detect Gta tends to give missing or incorrect results.

We provide a possible explanation. Intuitively, Nc relies on the assumption that a trojan model creates a “shortcut” (i.e., the trigger perturbation) for all the trigger-embedded inputs to reach the target class. However, this premise does not necessarily hold for Gta: given its adaptive nature, each individual graph may have a specific shortcut to reach the target class, rendering the detection less effective. It thus seems crucial to carefully account for the trigger adaptiveness in designing countermeasures against Gta.

3 Input-space attacks

While Gta directly operates on graph-structured inputs, there are scenarios in which non-graph inputs are converted to graphs for GNNs to process. In this case, the adversary must ensure that any perturbation on the graph after applying the trigger can be realistically projected back to the input space, where the adversary performs the manipulation. Although input-space attacks are an ongoing area of research, here we discuss the challenges and potential solutions to the problem for graph-structure data.

Challenges and solutions – Let ${\mathcal{X}}$ and ${\mathcal{G}}$ be the input and graph spaces, $\pi$ be the transformation mapping an input $X\in{\mathcal{X}}$ to its graph $G\in{\mathcal{G}}$, and $r$ and $\delta$ be the corresponding perturbations in the input and graph spaces, respectively. To implement Gta in the input space, the adversary needs to (i) find $r$ corresponding to given $\delta$ and (ii) ensure that $r$ satisfies the semantic constraints $\rho$ of the input space (e.g., malware retains its malicious functionality). We temporarily assume it is feasible to find $r$ for given $\delta$ and focus on enforcing $r$ to satisfy the input-space constraint $\rho$.

Transferable constraint – In the case that $\rho$ directly applies to the graph space, we may constrain $r$ to be the transplantation of syntactically-equivalent benign ASTs. For example, we may craft malicious JavaScripts (input space) using ASTs (graph space) taken from benign samples.

Specifically, we define a function $\rho(G)$ to measure $G$’s compliance with $\rho$. We differentiate two cases. First, if $\rho$ is differentiable (e.g., modeled as GNN), we define a regularizer in training ${g}_{\scaleobj{0.8}{t}}$ (cf. Eq (2)):

where $\Delta$ measures the difference of the compliance of two graphs $G$ and $m(G;{g}_{\scaleobj{0.8}{t}})$. Second, if $\rho$ is non-differentiable, we restrict $\delta$ to perturbations guaranteed to satisfy $\rho$. For instance, to preserve the functionality of a malicious program, we may add edges corresponding to no-op calls in its CFG.

Non-transferable constraint – In the case that $\rho$ is inapplicable to the graph space, it is infeasible to directly check $\delta$’s validity. For instance, it is difficult to check the tree structure of a PDF malware to determine whether it preserves the malicious network functionality.

We consider two cases. (i) If $\pi$’s inversion ${\pi}^{\scaleobj{0.8}{-1}}$ and $\rho$ are differentiable, we define a regularizer in training ${g}_{\scaleobj{0.8}{t}}$ (cf. Eq (2)):

(ii) If ${\pi}^{\scaleobj{0.8}{-1}}$ or $\rho$ is non-differentiable, one may use a problem-driven search strategy. Specifically, the search starts with a random mutation $\delta$ and learns from experience how to appropriately mutate it to satisfy $\rho$ and the objectives in Eq (3). To implement this strategy, it requires to re-design Gta within a reinforcement learning framework.

Case study – Here, we conduct a case study of input-space Gta in the task of detecting malicious Android APKs.

The perturbation to $G$’s topological structures is limited to adding no-op calls. Specifically, we define a binary mask matrix ${M}_{\scaleobj{0.8}{msk}}$ and set its $ij$-th entry as 1 if (i) $A_{ij}$ is 1, which retains the original call, or (ii) node $i$ is an external method, which is controlled by the adversary, and node $j$ is either an external method or an internal read-only method, which does not influence the original functionality.

The perturbation to $G$’s node features is limited to the modifiable features in Table 11 and constrained by their semantics. Specifically, we use the 23$\sim$37-th features, which correspond to the call frequencies of 15 specific instructions and only increase their values, implementable by adding calls of such instructions during the repackaging process. Here, we focus on showing the feasible of input-space attacks, while admitting the possibility that such no-op calls could be potentially identified and removed via decompiling the APK file.

Results and analysis – We evaluate input-space Gta on the AndroZoo dataset (cf. Table 1), which is partitioned into 50%/50% for the pre-training and downstream tasks, respectively. We use a Gcn as the feature extractor and a Fcn as the classifier (cf. Table 10). We consider two settings. (i) Each node is associated with a one-hot vector, each dimension corresponding to one key API of fundamental importance to malware detection. Under this setting, the attack is only allowed to perturb topological structures. (ii) Each node is associated with 40 call features (cf. Table 11). Under this setting, the attack is allowed to perturb both topological structures and node features. The system built upon benign GNNs achieves 95.3% and 98.1% ACC under the two settings, respectively.

We implement input-space Gta and compare it with graph-space Gta unbounded by input-space constraints. The results are summarized in Table 9. Under both settings, input-space and graph-space attacks attain high effectiveness (with ASR above 94% and AMC over 0.95), effectively retain the accuracy of benign GNNs (with CAD below 2%). As expected, due to its additional semantic constraints, input-space Gta performs worse than graph-space Gta in terms of both effectiveness and evasiveness; yet, because of the adaptive nature of Gta, the constraints have a limited impact (e.g., less than 4% lower in ASR and less than 1% higher in CAD).

We further manually inspect the APKs repackaged by input-space Gta to verify the correctness of the perturbations: (i) we install the APK on an Android device and test its functionality; (ii) we apply Soot to convert the repackaged APK back to its call-graph and check whether all the injected calls are successfully retained; (iii) we trigger the methods where the injected calls originate to check whether the app crashes or whether there are warnings/errors in the system logs. With the manual inspection of the repackaged APKs, we find all the input-space perturbations satisfy (i), (ii), and (iii).

Limitations – Although the case study above demonstrates an example of input-space Gta, there are still limitations that may impact its feasibility in certain settings, which we believe offers several interesting avenues for future research. First, it may be inherently infeasible to modify the input to achieve the desirable perturbation in the graph space. For instance, it is often assumed difficult to directly modify biometric data (e.g., fingerprints). Further, there are cases in which it is impractical to model the semantic constraints, not to mention using them to guide the attack. For instance, it is fundamentally difficult to verify the existence of chemical compounds corresponding to given molecular graphs. Finally, the adversary may only have limited control over the input. For instance, the adversary may only control a small number of accounts in a social network such as Facebook, while the perturbation (e.g., adding fake relationships) may be easily nullified by the network’s dynamic evolution.

Related Work

With their wide use in security-critical domains, DNNs become the new targets of malicious manipulations. Two primary types of attacks are considered in the literature.

Adversarial attacks – One line of work focuses on developing new attacks of crafting adversarial inputs to deceive target DNNs. Another line of work attempts to improve DNN resilience against existing attacks by devising new training strategies (e.g., adversarial training) or detection methods. However, such defenses are often penetrated or circumvented by even stronger attacks, resulting in a constant arms race.

Backdoor attacks – The existing backdoor attacks can be classified based on their targets. In class-level attacks, specific triggers (e.g., watermarks) are often pre-defined, while the adversary aims to force all the trigger-embedded inputs to be misclassified by the trojan model. In instance-level attacks (“clean-label” backdoors), the targets are pre-defined, unmodified inputs, while the adversary attempts to force such inputs to be misclassified by the trojan model. The existing defenses against backdoor attacks mostly focus on class-level attacks, which, according to their strategies, include (i) cleansing potential contaminated data at training time, (ii) identifying suspicious models during model inspection, and (iii) detecting trigger-embedded inputs at inference.

Attacks against GNNs – In contrast of the intensive research on general DNNs, the studies on the security properties of GNNs for graph-structured data are still sparse. One line of work attempts to deceive GNNs via perturbing the topological structures or descriptive features of graph data at inference time. Another line of work aims to poison GNNs during training to degrade their overall performance. The defenses against such attacks are mostly inspired by that for general DNNs (e.g., adversarial training).

Despite the plethora of prior work, the vulnerabilities of GNNs to backdoor attacks are largely unexplored. Concurrent to this work, Zhang et al. propose a backdoor attack against GNNs via training trojan GNNs with respect to pre-defined triggers. This work differs in several major aspects: (i) considering both inductive and transductive tasks, (ii) optimizing both triggers and trojan models, and (iii) exploring the effectiveness of state-of-the-art backdoor defenses.

Conclusion

This work represents an in-depth study on the vulnerabilities of GNN models to backdoor attacks. We present Gta, the first attack that trojans GNNs and invokes malicious functions in downstream tasks via triggers tailored to individual graphs. We showcase the practicality of Gta in a range of security-critical applications, raising severe concerns about the current practice of re-using pre-trained GNNs. Moreover, we provide analytical justification for such vulnerabilities and discuss potential mitigation, which might shed light on pre-training and re-using GNNs in a more secure fashion.

References

Appendix A Implementation details

To evaluate Eq (LABEL:eq:look-ahead), we apply the chain rule:

A.2 Mixing function

The mixing function $m(G;{g}_{\scaleobj{0.8}{t}})$ specifies how trigger ${g}_{\scaleobj{0.8}{t}}$ is embedded into graph $G$ by replacing subgraph $g$ in $G$ with ${g}_{\scaleobj{0.8}{t}}$. We extend a backtracking-based algorithm Vf2 to search for $g$ most similar to ${g}_{\scaleobj{0.8}{t}}$. Intuitively, Vf2 recursively extends a partial match by mapping the next node in ${g}_{\scaleobj{0.8}{t}}$ to a node in $G$; if it is feasible, it extends the partial match and recurses, and backtracks otherwise. As we search for the most similar subgraph, we maintain the current highest similarity and terminate a partial match early if it exceeds this threshold. Algorithm 2 sketches the implementation of the mixing function.

A.3 Transductive attack

Algorithm 3 sketches the implementation of Gta in transductive tasks (e.g., node classification).

A.4 Parameter setting

Table 10 summarizes the default parameter setting .

Appendix B Additional experiments

We build our defense upon Randomized-Smoothing (Rs).

Randomized smoothing – Rs applies a subsampling function ${\mathcal{S}}$ over a given graph $G$ (including both its structural connectivity and node features), generates a set of subsampled graphs $G_{1},G_{2},\ldots,G_{n}$, and takes a majority voting of the predictions over such samples as $G$’s final prediction. Intuitively, if $G$ is trigger-embedded, the trigger is less likely to be effective on the subsampled graphs, due to their inherent randomness. In particular, ${\mathcal{S}}$ is controlled by a parameter $\beta$ (subsampling ratio), which specifies the randomization magnitude. For instance, if $\beta=0.8$, ${\mathcal{S}}$ randomly removes 20% of $G$’s nodes, and for the rest nodes, randomly sets 20% of their features to be 0. Note that while in, Rs is further extended to mitigate trojan GNNs, here we focus on its use as a defense against trigger-embedded graphs.

Results and analysis – We evaluate Rs in the transfer case of ChEMBL$\rightarrow$Toxicant (cf. Table 4). Figure 13 illustrates the effectiveness and evasiveness of Gta as a function of the subsampling ratio $\beta$. Observe that there exists an intricate trade-off between attack robustness and clean accuracy. A smaller $\beta$ leads to lower ASR but also results in larger CAD. Therefore, Rs may not be a viable option for defending against Gta, as it may negatively impact system performance.

Other input-inspection defenses – One may suggest using other input inspection methods. Yet, it is often challenging to extend such defenses from continuous domains (e.g., images) to discrete domains (e.g., graphs). For instance, Strip is a representative input inspection defense. Intuitively, if an input is embedded with a trigger, its mixture with a benign input is still dominated by the trigger and tends to be misclassified to the target class, resulting in relatively low entropy of the prediction. Unfortunately, it is intrinsically difficult to apply Strip to graph-structured data. For instance, it is challenging to meaningfully “mix” two graphs.

B.2 Input-space attacks

Table 11 summarizes 40 features associated with each node in the Android call graphs.

Figure 14 visualizes sample call graphs generated by input-space Gta, where only external methods are perturbed.

Appendix C Graph-space constraints

We consider two types of constraints specified respectively on $G$’s topological connectivity and node features respectively.

Addition/deletion only which specifies whether only adding/removing edges is allowed. To enforce the addition-only constraint (similar in the case of deletion only), we set the $ij$-th entry of ${M}_{\scaleobj{0.8}{msk}}$ to be 1 if $A_{ij}$ is 1 and 0 otherwise, which retains all the edges in $g$.