Unnoticeable Backdoor Attacks on Graph Neural Networks
Graph Neural Networks (GNNs) have achieved promising results in various tasks
such as node classification and graph classification. Recent studies find that
GNNs are vulnerable to adversarial attacks. However, effective backdoor attacks
on graphs are still an open problem. In particular, backdoor attack poisons the
graph by attaching triggers and the target class label to a set of nodes in the
training graph. The backdoored GNNs trained on the poisoned graph will then be
misled to predict test nodes to target class once attached with triggers.
Though there are some initial efforts in graph backdoor attacks, our empirical
analysis shows that they may require a large attack budget for effective
backdoor attacks and the injected triggers can be easily detected and pruned.
Therefore, in this paper, we study a novel problem of unnoticeable graph
backdoor attacks with limited attack budget. To fully utilize the attack
budget, we propose to deliberately select the nodes to inject triggers and
target class labels in the poisoning phase. An adaptive trigger generator is
deployed to obtain effective triggers that are difficult to be noticed.
Extensive experiments on real-world datasets against various defense strategies
demonstrate the effectiveness of our proposed method in conducting effective
unnoticeable backdoor attacks.
Enyan Dai, Minhua Lin, Xiang Zhang, Suhang Wang
# Unnoticeable Backdoor Attacks on Graph Neural Networks

###### Abstract.

Graph Neural Networks (GNNs) have achieved promising results in various tasks such as node classification and graph classification. Recent studies find that GNNs are vulnerable to adversarial attacks. However, effective backdoor attacks on graphs are still an open problem. In particular, backdoor attack poisons the graph by attaching triggers and the target class label to a set of nodes in the training graph. The backdoored GNNs trained on the poisoned graph will then be misled to predict test nodes to target class once attached with triggers. Though there are some initial efforts in graph backdoor attacks, our empirical analysis shows that they may require a large attack budget for effective backdoor attacks and the injected triggers can be easily detected and pruned. Therefore, in this paper, we study a novel problem of unnoticeable graph backdoor attacks with limited attack budget. To fully utilize the attack budget, we propose to deliberately select the nodes to inject triggers and target class labels in the poisoning phase. An adaptive trigger generator is deployed to obtain effective triggers that are difficult to be noticed. Extensive experiments on real-world datasets against various defense strategies demonstrate the effectiveness of our proposed method in conducting effective unnoticeable backdoor attacks.

Backdoor Attack, Graph Neural Networks +
Footnote †: [leftmargin=*]This paper is organized as follows. Section 2 describes the results of our work. Section 3 describes the results of our work. Section 4 describes the results of our work. Section 5 describes the results of our work. Section 6 describes the results of our work. Section 7 describes the results of our work. Section 8 describes the results of our work. Section 8 describes the results of our work. Section 9 describes the results of our work. Section 10 describes the results of our work. Section 11 describes the results of our work. Section 12 describes the results of our work. Section 13 describes the results of our work. Section 14 describes the results of our work. Section 15 describes the results of our work. Section 16 describes the results of our work. Section 17 describes the results of our work. Section 18 describes the results of our work. Section 19 describes the results of our work. Section 10 describes the results of our work. Section 10 describes the results of our work. Section 11 describes the results of our work. Section 12 describes the results of our work. Section 13 describes the results of our work. Section 14 describes the results of our work. Section 15 describes the results of our work. Section 16 describes the results of our work. Section 17 describes the results of our work. Section 18 describes the results of our work. Section 19 describes the results of our work. Section 10 describes the results of our work. Section 10 describes the results of our work. Section 11 describes the results of our work. Section 12 describes the results of our work. Section 13 describes the results of our work. Section 13 describes the results of our work. Section 14 describes the results of our work. Section 15 describes the results of our work. Section 16 describes the results of our work. Section 17 describes the results of our work. Section 18 describes the results of our work. Section 19 describes the results of our work. Section 10 describes the results of our work. Section 11 describes the results of our work. Section 10 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 12 describes the results of our work. Section 13 describes the results of our work. Section 13 describes the results of our work. Section 14 describes the results of our work. Section 15 describes the results of our work. Section 16 describes the results of our work. Section 17 describes the results of our work. Section 18 describes the results of our work. Section 19 describes the results of our work. Section 10 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 12 describes the results of our work. Section 13 describes the results of our work. Section 13 describes the results of our work. Section 14 describes the results of our work. Section 15 describes the results of our work. Section 16 describes the results of our work. Section 17 describes the results of our work. Section 18 describes the results of our work. Section 19 describes the results of our work. Section 10 describes the results of our work. Section 10 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 12 describes the results of our work. Section 13 describes the results of our work. Section 13 describes the results of our work. Section 14 describes the results of our work. Section 15 describes the results of our work. Section 16 describes the results of our work. Section 17 describes the results of our work. Section 18 describes the results of our work. Section 19 describes the results of our work. Section 10 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work. Section 11 describes the results of our work.
process as graph manipulation attacks. This will especially benefit the targeted attack on inductive node classification, which widely exists in real-world scenarios. For example, TikTok graph will often incorporate new users and predict labels of them with a trained model. _Thirdly_, compared with revising the links between existing users, it is relatively easy to inject triggers and malicious labels in backdoor attacks. Take malicious user detection on social networks as an example, many labels are collected from reports of users. In this case, malicious labels could be easily assigned by attackers. As for the trigger attachment, it can be achieved by linking a set of fake accounts to the users.

Recently, Zhang et al. (Zhang et al., 2019) firstly investigate a graph backdoor attack that uses randomly generated graphs as triggers. A trigger generator is adopted in (Zhang et al., 2019) to get more powerful sample-specific triggers. However, these methods have unnoticeablity issues in the following two aspects. _Firstly_, our empirical analysis in Sec. 3.3.1 shows that existing methods need a large budget to conduct effective backdoor attacks on large-scale graphs, i.e., they need to attach the backdoor triggers to a large number of nodes in the training graph so that a model trained on the graph will be fooled to assign target label to nodes attached with the backdoor trigger. This largely increases the risk of being detected. _Secondly_, the generated triggers of these methods can be easily identified and destroyed. Specifically, real-world graphs such as social networks generally follow homophily assumption, i.e., similar nodes are more likely to be connected; while in existing graph backdoor attacks, the edges linking triggers and poisoned nodes and edges inside the triggers are not guaranteed with the property of connecting nodes with high similarity scores. Thus, the triggers and assigned malicious labels can be eliminated by pruning edges linking dissimilar nodes and discarding labels of involved nodes, which is verified in Sec 3.3.2. Thus, developing an effective unnoticeable graph backdoor attack with limited attack budget is important. However, graph backdoor attack is still in its early stage and there is no existing work on unnoticeable graph backdoor attack with limited attack budget.

Therefore, in this paper, we study a novel and important problem of developing an effective unnoticeable graph backdoor attack with limited attack budget in terms of the number of poisoned nodes. In essence, we are faced with two challenges: (i) how to fully utilize the limited budget in poisoned samples for graph backdoor attacks; (ii) how to obtain triggers that are powerful and difficult to be detected. In an attempt to address these challenges, we proposed a novel framework Unnoticeable Graph Backdoor Attack (UGBA)1. To better utilize the attack budget, UGBA proposes to attach triggers with crucial representative nodes with a novel poisoned node selection algorithm. And an adaptive trigger generator is deployed in UGBA to obtain powerful unnoticeable trigger that exhibits high similarity with each target node and maintains high attack success rate. In summary, our main contributions are:

Footnote 1: [https://github.com/ventr1c/UGBA](https://github.com/ventr1c/UGBA)

* We study a novel problem of promoting unnoticeablity of graph backdoor attacks in generated triggers and attack budget;
* We empirically verify that a simple strategy of edge pruning and label discarding can largely degrade existing backdoor attacks;
* We design a framework UGBA that deliberately selects poisoned samples and learn effective unnoticeable triggers to achieve unnoticeable graph backdoor attack under limited budget; and
* Extensive experiments on large-scale graph datasets demonstrate the effectiveness of our proposed method in unnoticeably backdooring different GNN models with limited attack budget.

## 2. Related Works

### Graph Neural Networks

Graph Neural Networks (GNNs) (Grover et al., 2017; Zhang et al., 2019; Zhang et al., 2019; Zhang et al., 2019) have shown remarkable ability in modeling graph-structured data, which benefits various applications such as recommendation system (Zhang et al., 2019), drug discovery (Grover et al., 2017) and traffic analysis (Zhang et al., 2019). Generally, the success of GNNs relies on the message-passing strategy, which updates a node's representation by recursively aggregating and combining features from neighboring nodes. For instance, in each layer of GCN (Grover et al., 2017) the representations of neighbors and the center node will be averaged followed by a non-linear transformation such as ReLU. Recently, many GNN models are proposed to further improve the performance of GNNs (Grover et al., 2017; Zhang et al., 2019; Zhang et al., 2019; Zhang et al., 2019; Zhang et al., 2019; Zhang et al., 2019). For example, self-supervised GNNs (Grover et al., 2017; Zhang et al., 2019; Zhang et al., 2019) are investigated to reduce the need of labeled nodes. Works that improve fairness (Zhang et al., 2019), robustness (Zhang et al., 2019; Zhang et al., 2019) and explainability (Zhang et al., 2019; Zhang et al., 2019; Zhang et al., 2019) of GNNs are explored. And GNN models for heterophilic graphs are also designed (Grover et al., 2017; Zhang et al., 2019).

### Attacks on Graph Neural Networks

According to the stages the attack occurs, adversarial attacks on GNNs can be divided into poisoning attack (Zhang et al., 2019; Zhang et al., 2019; Zhang et al., 2019; Zhang et al., 2019) and evasion attack (Grover et al., 2017; Zhang et al., 2019; Zhang et al., 2019; Zhang et al., 2019). In poisoning attacks, the attackers aim to perturb the training graph before GNNs are trained such that a GNN model trained on the poisoned dataset will have a low prediction accuracy on test samples. For example, Nettack (Nettack, 2018) employs a tractable surrogate model to conduct a targeted poisoning attack by learning perturbation against the surrogate model. Evasion attacks add perturbation in the test stage, where the GNN model has been well trained and cannot be modified by attackers. Optimizing the perturbation of graph structures by gradient descent (Zhang et al., 2019) and reinforcement learnings (Grover et al., 2017; Zhang et al., 2019) have been explored. Evasion attacks through graph injection (Zhang et al., 2019; Zhang et al., 2019) are also investigated.

Backdoor attacks are still rarely explored on GNNs (Zhang et al., 2019; Zhang et al., 2019). Backdoor attacks generally attach backdoor triggers to the training data and assign the target label to samples with trigger. Then a model trained on the poisoned data will be misled if backdoors are activated by the trigger-embedded test samples. Zhang et al. (Zhang et al., 2019) propose a subgraph-based backdoor attack on GNNs by injecting randomly generated universal triggers to some training samples.

Figure 1. General framework of graph backdoor attack.
Xi et al. (2017) adopt a trigger generator to learn to generate adaptive trigger for different samples. Sheng et al. (2019) propose to select the nodes with high degree and closeness centrality. Xu and Picek (2019) improve the unnoticeability by assigning triggers without change labels of poisoned samples. Our proposed method is inherently different from these methods as (i) we can generate unnoticeable adaptive triggers to simultaneously maintain the effectiveness and bypass the potential trigger detection defense based on feature similarity of linked nodes; (ii) we design a novel clustering-based node selection algorithm to further reduce the required attack budget.

## 3. Preliminary Analysis

In this section, we present preliminaries of backdoor attacks on graphs and show unnoticeablity issues of existing backdoor attacks.

### Notations

We use \(\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X})\) to denote an attributed graph, where \(\mathcal{V}=\{\mathbf{e}_{1},\ldots,\mathbf{e}_{N}\}\) is the set of \(N\) nodes, \(\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}\) is the set of edges, and \(\mathbf{X}=\{\mathbf{x}_{1},...,\mathbf{x}_{N}\}\) is the set of node attributes with \(\mathbf{x}_{i}\) being the node attribute of \(\mathbf{e}_{i}\). \(\mathbf{A}\in\mathbb{R}^{N\times N}\) is the adjacency matrix of the graph \(\mathcal{G}\), where \(\mathbf{A}_{ij}=1\) if nodes \(\mathbf{e}_{i}\) and \(\mathbf{e}_{j}\) are connected; otherwise \(\mathbf{A}_{ij}=0\). In this paper, we focus on a semi-supervised node classification task in the inductive setting, which widely exists in real-world applications. For instance, GNNs trained on social networks often need to conduct predictions on newly enrolled users to provide service. Specifically, in inductive node classification, a small set of nodes \(\mathcal{V}_{L}\subseteq\mathcal{V}\) in the training graph are provided with labels \(\mathcal{Y}_{L}=\{y_{1},\ldots,y_{N_{L}}\}\). The test nodes \(\mathcal{V}_{T}\) are not covered in the training graph \(\mathcal{G}\), i.e., \(\mathcal{V}_{T}\cap\mathcal{V}=\emptyset\).

### Preliminaries of Graph Backdoor Attacks

#### 3.2.1. Threat Model

In this section, we introduce the threat model. **Attacker's Goal**: The goal of the adversary is to mislead the GNN model to classify target nodes attached with the triggers as target class. Simultaneously, the attacked GNN model should behave normally for clean nodes without triggers attached.

**Attacker's Knowledge and Capability**: As the setting of most poisoned attacks, the training data of the target model is available for attackers. The information of the target GNN models including model architecture is unknown to the attacker. Attackers are capable of attaching triggers and labels to nodes within a budget before the training of target models to poison graphs. During the inference phase, attackers can attach triggers to the target test node.

#### 3.2.2. General Framework of Graph Backdoor Attacks

The key idea of the backdoor attacks is to associate the trigger with the target class in the training data to mislead target models. As Fig. 1 shows, during the poisoning phase, the attacker will attach a trigger \(g\) to a set of poisoned nodes \(\mathcal{V}_{P}\subseteq\mathcal{V}\) and assign \(\mathcal{V}_{P}\) with target class label \(y_{t}\), resulting a backdoored dataset. Generally, the poisoned node set \(\mathcal{V}_{P}\) is randomly selected. The GNNs trained on the backdoored dataset will be optimized to predict the poisoned nodes \(\mathcal{V}_{P}\) attached with the trigger \(g\) as target class \(y_{t}\), which will force the target GNN to correlate the existence of the trigger \(g\) in neighbors with the target class. In the test phase, the attacker can attach the trigger \(g\) to a test node \(v\) to make \(v\) classified as the target class by backdoored GNN. Some initial efforts (Zhu et al., 2017; Wang et al., 2018) have been made for graph backdoor attacks. Specifically, SBA (Wang et al., 2018) directly injects designed sub-graphs as triggers. And GTA (Zhu et al., 2017) adopts a trigger generator to learn optimal sample-specific triggers.

### Unnoticeability of Graph Backdoor Attacks

In this subsection, we analyze the unnoticeability of existing graph backdoor attacks in terms of the required number of poisoned samples and the difficulty of trigger detection.

#### 3.3.1. Size of Poisoned Nodes

In backdoor attacks, a set of poisoned nodes \(\mathcal{V}_{P}\) will be attached triggers and target class labels to conduct attacks. However, as large-scale graphs can provide abundant information for training GNNs, the attacker may need to inject a large number of triggers and malicious labels to mislead the target GNN to correlate the trigger with target class, which puts backdoor attack at the risk of being noticed. To verify this, we analyze how the size of poisoned nodes affects the attack success rate of the state-of-the-art graph backdoor attacks, i.e., SBA-Gene, SBA-Samp (Wang et al., 2018), and GTA (Zhu et al., 2017) on a large node classification dataset, i.e., OGB-arxiv (2018). Detailed descriptions of these methods can be found in Sec. 6.1.2. We vary \(|\mathcal{V}_{P}|\) as \(\{80,240,800,2400\}\). The size of trigger is limited to contain three nodes. The architecture of target model is GraphSage (Gan et al., 2018). The attack success rate (ASR) results are presented in Table 1. From the table, we can observe that all methods especially SBA-Gen and SBA-Samp achieve poor attack results with limited budget such as 80 and 240 in \(\mathcal{V}_{P}\). This is because (i) SBA-Gen and SBA-Samp utilize handcrafted triggers which is not effective; (ii) Though GTA uses learned sample-specific trigger, similar to SBA-Gen and SBA-Samp, the selection of poisoned nodes is random and the budget is not well utilized. Thus, it is necessary to develop graph backdoor attack methods that can generate effective triggers and fully exploit the attack budget.

#### 3.3.2. Detection of Triggers

Real-world graphs such as social networks generally show homophily property, i.e, nodes with similar attributes are connected by edges. For existing backdoor attacks, the attributes of triggers may differ a lot from the attached poisoned nodes. The connections within trigger may also violate homophily property. Therefore, the negative effects of injected triggers and target labels might be reduced by eliminating edges linking dissimilar nodes and labels of involved nodes. To verify this, we evaluate two strategies to defend against backdoor attacks:

\begin{table}
\begin{tabular}{l c c c c c} \hline \hline \(|\mathcal{V}_{P}|\) & 80 & 240 & 400 & 800 & 2400 \\ \hline SBA-Samp & 0.06 & 1.7 & 10.8 & 34.5 & 75.5 \\ SBA-Gen & 0.08 & 18.1 & 32.1 & 54.3 & 85.9 \\ GTA & 37.4 & 62.4 & 72.4 & 82.7 & 94.8 \\ \hline \hline \end{tabular}
\end{table}
Table 1. Impacts of \(|\mathcal{V}_{P}|\) to ASR (%) of backdoor attacks.

\begin{table}
\begin{tabular}{l c c c c c} \hline \hline Defense & Clean & SBA-Samp & SBA-Gen & GTA \\ \hline None & 65.5 & 61.0 & 65.1 & 70.8 & 65.2 & 94.8 & 65.6 \\ Prune & 62.2 & 8.9 & 64.0 & 31.2 & 64.0 & 1.4 & 64.5 \\ Prune+LD & 62.6 & 3.2 & 64.0 & 15.3 & 63.8 & 0.04 & 64.1 \\ \hline \hline \end{tabular}
\end{table}
Table 2. Results of backdoor defense (Attack Success Rate (%)) Clean Accuracy (%)) on Ogb-arxiv dataset.
* **Prune**: We prune edges linking nodes with low cosine similarity. As edges created by the backdoor attacker may link dissimilar nodes, the trigger structure and attachment edge can be destroyed.
* **Prune+LD**: To reduce the influence of dirty labels of poisoned nodes, besides pruning, we also discard the labels of the nodes linked by dissimilar edges.

Experimental results on Ogb-arvik with \(|\mathcal{V}_{P}|\) set as 2400 are presented in Table 2. Other settings are the same as Sec. 3.3.1. For Prune and Prune+LD, the threshold is to filter out edges with lowest 10% cosine similarity scores. More results on other datasets can be found in Table 4. The accuracy of the backdoored GNN on clean test set is also reported in Table 2 to show how the defense strategies affect the prediction performance. Accuracy on a clean graph without any attacks is reported as reference. All the results are average scores of 5 runs. We can observe from Tab. 2 that (i) ASR drops dramatically with the proposed two strategies of prune and prune+LD; (ii) the impact of the proposed strategies on prediction accuracy is negligible. This demonstrates that the used triggers by existing backdoor attacks can be easily mitigated.

## 4. Problem Formulation

Our preliminary analysis verifies that existing backdoor attacks (i) require a large attack budget on large datasets; and (ii) the injected triggers can be easily detected. To alleviate these two issues, we propose to investigate a novel unnoticeable graph backdoor attack problem that can unnoticeablely backdoor various target GNNs with limited attack budget. Specifically, we enhance the general graph backdoor attack model from the following two aspects.

**Selection of Poisoned Nodes \(\mathcal{V}_{P}\)**: In the attack model of current graph backdoor attacks, the poisoned node set \(\mathcal{V}_{P}\) is randomly selected. However, in this way, it is likely the budget is wasted in some useless poisoned nodes. For example, the attacker may repeatedly poison nodes from the same cluster that have very similar pattern, which is unnecessary. Alternatively, to fully utilize the attack budget, we will deliberately select the most useful poisoned nodes \(\mathcal{V}_{P}\subseteq\mathcal{V}\) in unnoticeable backdoor attack.

**Unnoticeable Constraint on Triggers**: As the preliminary analysis shows, dissimilarity among trigger nodes and poisoned nodes makes the attack easy to be detected. Hence, it is necessary to obtain adaptive triggers that are similar to the poisoned nodes or target nodes. In addition, edges within triggers should also be enforced to link similar nodes to avoid being damaged by pruning strategy. Such adaptive trigger can be given by an adaptive generator. Let \(\mathcal{E}^{i}_{B}\) denote the edge set that contain edges inside trigger \(g_{i}\) and edge attaching trigger \(g_{i}\) and node \(v_{i}\). The unnoticeable constraint on the generated adaptive triggers can be formally written as:

\[\min_{(u,v)\in\mathcal{E}^{i}_{B}}sim(u,v)\geq T, \tag{1}\]

where \(sim\) denotes the cosine similarity between node features and \(T\) is a relatively high threshold of the cosine similarity which can be tuned based on datasets.

In node classification with GNNs, the prediction is given based on the computation graph of the node. Thus, the clean prediction on node \(v_{i}\) can be written as \(f_{\theta}(\mathcal{G}^{i}_{C})\), where \(\mathcal{G}^{i}_{C}\) denotes the clean computation graph of node \(v_{i}\). For a node \(v_{i}\) attached with the adaptive trigger \(g_{i}\), the predictive label will be given by \(f_{\theta}(a(\mathcal{G}^{i}_{C},g_{i}))\), where \(a(\cdot)\) denotes the operation of trigger attachment. Then, with the above descriptions and notations in Sec 3.1. we can formulate the unnoticeable graph backdoor attack by:

**Problem 1**.: _Given a clean attributed graph \(\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X})\) with a set of nodes \(\mathcal{V}_{L}\) provided with labels \(\mathcal{Y}_{L}\), we aim to learn an adaptive trigger generator \(f_{g}:v_{i}\to g_{i}\) and effectively select a set of nodes \(\mathcal{V}_{P}\) within budget to attach triggers and labels so that a GNN\(f\) trained on the poisoned graph will classify the test node attached with the trigger to the target class \(y_{t}\) by solving:_

\[\begin{split}&\min_{\mathcal{V}_{P},f_{g}}\sum_{u_{i}\in \mathcal{V}_{U}}l(f_{\theta}(a(\mathcal{G}^{i}_{C},g_{i})),y_{t})\\ & s.t.~{}\theta^{*}=\operatorname*{arg\,min}_{\theta}\sum_{u_{i}\in \mathcal{V}_{L}}l(f_{\theta}(\mathcal{G}^{i}_{C}),y_{i})+\sum_{u_{i}\in \mathcal{V}_{P}}l(f_{\theta}(a(\mathcal{G}^{i}_{C},g_{i})),y_{t}),\\ &\quad\forall v_{i}\in\mathcal{V}_{P}\cup\mathcal{V}_{T},~{}g_{ i}\text{ meets Eq.(1) and }|g_{i}|<\Delta_{g}\\ &\quad|\mathcal{V}_{P}|\leq\Delta_{P}\end{split} \tag{2}\]

_where \(l(\cdot)\) represents the cross entropy loss and \(\theta_{g}\) denotes the parameters of the adaptive trigger generator \(f_{g}\). In the constraints, the node size of trigger \(|g_{i}|\) is limited by \(\Delta_{g}\), and the size of poisoned nodes is limited by \(\Delta_{P}\). The architecture of the target GNN\(f\) is unavailable and may adapt various defense methods._

In transductive setting, \(\mathcal{V}_{U}\) would be the target nodes. However, we focus on inductive setting where \(\mathcal{V}_{T}\) is not available for the optimization. Hence, \(\mathcal{V}_{U}\) would be \(\mathcal{V}\backslash\mathcal{V}_{L}\) to ensure the attacks can be effective for various types of target nodes.

## 5. Methodology

In this section, we present the details of UGBA which aims to optimize Eq.(2) to conduct effective and unnoticeable graph backdoor attacks. Since it is challenging and computationally expensive to jointly optimize the selection of poisoned nodes \(\mathcal{V}_{P}\) and the trigger generator, UGBA splits the optimization process into two steps: poisoned node selection and adaptive trigger generator learning. Two challenges remain to be addressed: (i) how to select the poisoned nodes that are most useful for backdoor attacks; (ii) how to learn the adaptive trigger generator to obtain triggers that meet unnoticeable constraint and maintain a high success rate in backdoor attack; To address these challenges, a novel framework of UGBA is proposed, which is illustrated in Fig. 2. UGBA is composed of a poisoned node selector \(f_{P}\), an adaptive trigger generator \(f_{g}\), and a surrogate GCN model \(f_{s}\). Specifically, the poisoned node selector takes the graph \(\mathcal{G}\) as input and applies a novel metric to select nodes with representative patterns in features and local structures as poisoned nodes. An adaptive trigger generator \(f_{g}\) is applied with a differentiable unnoticeable constraint to give unnoticeable triggers for selected poisoned nodes \(\mathcal{V}_{P}\) to fool \(f_{s}\). To guarantee the effectiveness of the generated adaptive triggers on various test nodes, a bi-level optimization with a surrogate GCN model is applied.

### Poisoned Node Selection

In this subsection, we give the details of the node selection algorithm. Intuitively, if nodes with representative features and local
structures are predicted to the target class \(y_{t}\) after being attached with triggers, other nodes are also very likely to be conducted successful backdoor attacks. Therefore, we propose to select diverse and representative nodes in the graph as poisoned nodes, which enforce the target GNN to predict the representative nodes attached with triggers to be target class \(y_{t}\).

One straightforward way to obtain the representative nodes is to conduct clustering on the node features. However, it fails to consider the graph topology which is crucial for graph-structured data. Therefore, we propose to train a GCN encoder with the node labels to obtain representations that capture both attribute and structure information. Then, for each class, we can select representative nodes using the clustering algorithm on learned representations. Specifically, the node representations and labels can be obtained as:

\[\mathbf{H}=GCN(\mathbf{A},\mathbf{X}),\quad\hat{\mathbf{Y}}=\text{softmax}( \mathbf{W}\cdot\mathbf{H}), \tag{3}\]

where \(\mathbf{W}\) denotes the learnable weight matrix for classification. The training process of the GCN encoder can be written as:

\[\min_{\theta_{E},\mathbf{W}}\sum_{\mathbf{u}_{1}\in\mathcal{V}_{L}}l(\hat{y}_ {i},y_{t}) \tag{4}\]

where \(\theta_{E}\) denotes the parameters of GCN encoder, \(l(\cdot)\) is the cross entropy loss, and \(y_{i}\) is the label of node \(v_{i}\). \(\hat{y}_{i}\) is the prediction of \(v_{i}\).

With the GCN encoder trained in Eq. (4), we can obtain the node representations and conduct clustering to obtain the representative nodes for each class. Here, to guarantee the diversity of the obtained representative nodes, we separately apply K-Means to cluster \(\{\mathbf{h}_{i}:\hat{y}_{i}=l\}\) on each class \(l\) other than the target class \(y_{t}\), where \(\mathbf{h}_{i}\) denote the representation of node \(v_{i}\in\mathcal{V}/\mathcal{V}_{L}\). Nodes nearer to the centroid of each cluster are more representative. However, the node nearest to the centroid may have a high degree. Injecting the malicious label to high-degree nodes may lead to a significant decrease in prediction performance as the negative effect will be propagated to its neighbors, which may make the attack noticeable. Hence, we propose a metric that balances the representativeness and negative effects on the prediction performance. Let \(\mathbf{h}_{c}^{k}\) denote the center of the \(k\)-th cluster. Then for a node \(v_{i}^{k}\) belonging to the \(k\)-th cluster, the metric score can be computed by:

\[m(v_{i})=||\mathbf{h}_{i}^{k}-\mathbf{h}_{c}^{k}||_{2}+\lambda\cdot deg(v_{i} ^{k}) \tag{5}\]

where \(\lambda\) is to control the contribution of the degree in node selection. After getting each node's score, we select nodes with top-\(n\) highest scores in each cluster to satisfy the budget, where \(n=\frac{\Delta_{p}}{(C-1)K}\).

### Adaptive Trigger Generator

Once the poisoned node set \(\mathcal{V}_{p}\) is determined, the next step is to generate adaptive triggers with \(f_{g}\) to poison the dataset. To guarantee the unnoticeability of the generated triggers, we propose a differentiable unnoticeable loss. We apply a bi-level optimization between the adaptive generator \(f_{g}\) and the surrogate model \(f_{h}\) to ensure high success rate on various test samples. Next, we give the details of trigger generator \(f_{g}\), differentiable unnoticeable loss, and the bi-level optimization with \(f_{h}\).

**Design of Adaptive Trigger Generator.** To generate adaptive triggers that are similar to the attached nodes, the adaptive trigger generator \(f_{g}\) takes the node features of the target node as input. Specifically, we adopt an MLP to simultaneously generate node features and structure of the trigger for node \(v_{i}\) by:

\[\mathbf{h}_{i}^{m}=\text{MLP}(\mathbf{x}_{i}),\quad\mathbf{X}_{i}^{g}=\mathbf{ W}_{f}\cdot\mathbf{h}_{i}^{m},\quad\mathbf{A}_{i}^{g}=\mathbf{W}_{a}\cdot \mathbf{h}_{i}^{m}, \tag{6}\]

where \(\mathbf{x}_{i}\) is the node features of \(v_{i}\). \(\mathbf{W}_{f}\) and \(\mathbf{W}_{a}\) are learnable parameters for feature and structure generation, respectively. \(\mathbf{X}_{i}^{g}\in\mathbb{R}^{n\times d}\) is the synthetic features of the trigger nodes, where \(s\) and \(d\) represent the size of the generated trigger and the dimension of features, respectively. \(\mathbf{A}_{i}^{g}\in\mathbb{R}^{n\times s}\) is the adjacency matrix of the generated trigger. As the real-world graph is generally discrete, following the binary neural network (He et al., 2017), we binarize the continuous adjacency matrix \(\mathbf{A}_{i}^{g}\) in the forward computation; while the continuous value is used in backward propagation. With the generated trigger \(g_{i}=(\mathbf{X}_{i}^{g},\mathbf{A}_{i}^{g})\), we link it to node \(v_{i}\in\mathcal{V}_{p}\) and assign target class label \(y_{t}\) to build backdoored dataset. In the inference phase, the trigger generated by \(f_{g}\) will be attached to the test node \(v_{i}\in\mathcal{V}_{T}\) to lead backdoored GNN to predict it as target class \(y_{t}\).

**Differentiable Unnoticeable Loss.** The adaptive trigger generator \(f_{g}\) aims to produce the triggers that meet the Eq.(1) for unnoticeable trigger injection. The key idea is to ensure the poisoned node or test node \(v_{i}\) is connected to a trigger node with high cosine similarity to avoid trigger elimination. And within the generated trigger \(g_{i}\), the connected trigger nodes should also exhibit high similarity. Thus, we design a differentiable unnoticeable loss to help optimize the adaptive trigger generator \(f_{g}\). Let \(\mathcal{E}_{B}^{i}\) denote the edge set that contains edges inside trigger \(g_{i}\) and edge attaching trigger \(g_{i}\) and node \(v_{i}\), the unnoticeable loss can be written as:

\[\min_{\theta_{g}}\mathcal{L}_{c}=\sum_{v_{i}\in\mathcal{V}}\sum_{(v_{j},v_{k}) \in\mathcal{E}_{B}^{i}}\max(0,T-sim(v_{j},v_{k})), \tag{7}\]

where \(T\) denotes the threshold of the similarity, and \(\theta_{g}\) represents the parameters of \(f_{g}\). The unnoticeable loss is applied on all nodes \(\mathcal{V}\) to ensure that the generated trigger meets the unnoticeable constraint for various kinds of nodes.

**Bi-level Optimization.** To guarantee the effectiveness of the generated triggers, we optimize the adaptive trigger generator to successfully attack the surrogate GCN model \(f_{s}\) with a bi-level optimization. Specifically, the surrogate GCN \(f_{s}\) will be trained on the backdoored dataset, which can be formulated as:

\[\min_{\theta_{s}}\mathcal{L}_{s}(\theta_{s},\theta_{g})=\sum_{v_{i}\in\mathcal{ V}_{L}}l(f_{s}(\mathcal{B}_{C}^{i}),y_{i})+\sum_{v_{i}\in\mathcal{V}_{p}}l(f_{s}(a( \mathcal{G}_{C}^{i},g_{i})),y_{t}), \tag{8}\]

where \(\theta_{s}\) represents the parameters of the surrogate GCN \(f_{s}\), \(\mathcal{G}_{C}^{i}\) indicates the clean computation graph of node \(v_{i}\), and \(a(\cdot)\) denotes

Figure 2. An overview of proposed UGBA.
the attachment operation. \(y_{i}\) is the label of labeled node \(o_{i}\in\mathcal{V}_{L}\) and \(y_{t}\) is the target class label. The adaptive trigger will be optimized to effectively mislead the surrogate model \(f_{s}\) to predict various nodes from \(\mathcal{V}\) to be \(y_{t}\) once injected with adaptive triggers, which can be written as:

\[\mathcal{L}_{g}(\theta_{s},\theta_{g})=\sum_{o_{i}\in\mathcal{V}}l(f_{s}(a(G_{ C}^{i},g_{i})),y_{t}). \tag{9}\]

Combining the unnoticeable loss Eq.(7), the following bi-level optimization problem can be formulated:

\[\begin{split}\min_{\theta_{g}}&\mathcal{L}_{g}( \theta_{s}^{*}(\theta_{g}),\theta_{g})+\beta\mathcal{L}_{c}(\theta_{g})\\ s.t.&\theta_{s}^{*}=\arg\min_{\theta_{s}}\mathcal{L}_ {s}(\theta_{s},\theta_{g}),\end{split} \tag{10}\]

where \(\beta\) is used to control the contribution of unnoticeable loss.

### Optimization Algorithm

We propose an alternating optimization schema to solve the bi-level optimization problem of Eq.(10) with a small computation cost.

**Updating Lower Level Surrogate Model.** Computing \(\theta_{s}^{*}\) for each outter iteration is expensive. We update surrogate model \(\theta_{s}\) with \(N\) inner iterations with fixed \(\theta_{g}\) to approximate \(\theta_{s}^{*}\) as (Zhou et al., 2017) does:

\[\theta_{s}^{t+1}=\theta_{s}^{t}-\alpha_{s}\nabla_{\theta_{s}}\mathcal{L}_{s} (\theta_{s},\theta_{g}) \tag{11}\]

where \(\theta_{s}^{t}\) denotes model parameters after \(t\) iterations. \(\alpha_{s}\) is the learning rate for training the surrogate model.

**Updating Upper Level Surrogate Model.** In the outer iteration, the updated surrogate model parameters \(\theta_{s}^{T}\) are used to approximate \(\theta_{s}^{*}\). Moreover, we apply first-order approximation (Kang et al., 2017) in computing gradients of \(\theta_{g}\) to further reduce the computation cost:

\[\begin{split}\theta_{g}^{k+1}=\theta_{g}^{k}-\alpha_{g}\nabla_{ \theta_{g}}(\mathcal{L}_{g}(\tilde{\theta}_{s},\theta_{g}^{k})+\beta\mathcal{ L}_{c}(\theta_{g}^{k})),\end{split} \tag{12}\]

where \(\tilde{\theta}_{s}\) indicates gradient propagation stopping. \(\alpha_{g}\) is the learning rate of training adaptive generator. See more details in algorithm 1. And the time complexity analysis can be found in Appendix F.

## 6. Experiments

In this section, we will evaluate proposed methods on various large-scale datasets to answer the following research questions:

* **RQ1**: Can our proposed method conduct effective backdoor attacks on GNNs and simultaneously ensure unnoticeability?
* **RQ2**: How do the number of poisoned nodes affect the performance of backdoor attacks?
* **RQ3**: How do the adaptive constraint and the poisoned node selection module affect the attack performance?

### Experimental Settings

#### 6.1.1. Datasets

To demonstrate the effectiveness of our UGBA, we conduct experiments on four public real-world datasets, i.e., Cora, Pubmed (Zhou et al., 2017), Flickr (Yi et al., 2017), and OGB-arxiv (Fischer et al., 2017), that are widely used for inductive semi-supervised node classification. Cora and Pubmed are small citation networks. Flickr is a large-scale graph that links image captions sharing the same properties. OGB-arxiv is a large-scale citation network. The statistics of the datasets are summarized in Tab. 3.

#### 6.1.2. Compared Methods

We compare UGBA with representative and state-of-the-art graph backdoor attack methods, including **GTA**(Zhou et al., 2017), **SBA-Samp**(Zhou et al., 2017) and its variant **SBA-Gen**. We also compare **GBAST**(Zhou et al., 2017) on Pubmed, which is shown in the Appendix C.

As UGBA conduct attacks by injecting triggers to target nodes, we also compare UGBA with two state-of-the-art graph injection evasion attacks designed for large-scale attacks, i.e. **TDGIA**(Zhou et al., 2017) and **AGIA**(Zhou et al., 2017). More details of these compared methods can be found in Appendix D. For a fair comparison, hyperparameters of all the attack methods are tuned based on the performance of the validation set.

**Competing with Defense Methods.** We applied the backdoor defense strategies introduced in Sec. 3.3.2 (i.e., Prune and Prune+LD) to help evaluate the unnoticeability of backdoor attacks. Moreover, two representative robust GNNs, i.e., **RobustGCN**(Zhou et al., 2017) and **GNNGuard**(Zhou et al., 2017), are also selected to verify that UGBA can also effectively attack general robust GNNs.

#### 6.1.3. Evaluation Protocol

In this paper, we conduct experiments on the inductive node classification task, _where the attackers can not access test nodes when they poison the graph_. Hence, we randomly mask out 20% nodes from the original dataset. And half of the masked nodes are used as target nodes for attack performance evaluation. Another half is used as clean test nodes to evaluate the prediction accuracy of backdoored models on normal samples. The graph containing the rest 80% nodes will be used as training graph \(\mathcal{G}\), where the labeled node set and validation set both contain 10% nodes. The average success rate (ASR) on the target node set and clean accuracy on clean test nodes are used to evaluate the backdoor attacks. A two-layer GCN is used as the surrogate model for all attack methods. And to demonstrate the transferability of the backdoor attacks, we attack target GNNs with different architectures, i.e., **GCN**, **GraphSage**, and **GAT**. Experiments on each target GNN architecture are conducted 5 times. We report the average ASR and clean accuracy of the total 15 runs (Tab. 4, Fig. 4, and Fig. 3). For all experiments, class 0 is the target class. The attack budget \(\Delta_{P}\) on size of poisoned nodes \(\mathcal{V}_{P}\) is set as 10, 40, 80 and 160 for Cora, Pubmed, Flickr and OGB-arxiv, respectively. The number of nodes in the trigger size is limited to 3 for all experiments. For experiments varying the budget in trigger size, please refer to Appendix E.

Our UGBA deploys a 2-layer GCN as the surrogate model. A 2-layer MLP is used as the adaptive trigger. More details of the hyperparameter setting can be found in Appendix B.

### Attack Results

To answer **RQ1**, we compare UGBA with baselines on four real-world graphs under various defense settings in terms of attack performance and unnoticeability.

\begin{table}
\begin{tabular}{l l l l l} \hline \hline Datasets & \#Nodes & \#Edges & \#Feature & \#Classes \\ \hline Cora & 2,708 & 5,429 & 1,443 & 7 \\ Pubmed & 19,717 & 44,338 & 500 & 3 \\ Flickr & 89,250 & 899,756 & 500 & 7 \\ OGB-arxiv & 169,343 & 1,166,243 & 128 & 40 \\ \hline \hline \end{tabular}
\end{table}
Table 3. Dataset Statistics
#### 6.2.1. Comparisons with baseline backdoor attacks

We conduct experiments on four real-world graphs under three backdoor defense strategy settings (i.e., No defense, Prune and Prune+LD). As described by the evaluation protocol in Sec. 6.1.3, we report the average results in backdooring three target GNN architectures in Tab. 4. The details of the backdoor attack results are presented in Tab. 8-10 in Appendix. From the table, we can make the following observations:

* When no backdoor defense strategy is applied, our UGBA outperforms the baseline methods, especially on large-scale datasets. This indicates the effectiveness of poisoned node selection algorithm in fully utilizing the attack budget.
* All the baselines give poor performance when the trigger detection based defense methods, i.e., Prune and Prune+LD, are adopted. By contrast, our UGBA can achieve over 90% ASR with the defense strategies and maintain high clean accuracy. This demonstrates that our UGBA can generate effective and unnoticeable triggers for backdoor attacks.
* As the ASRs are average results of backdooring three different GNN architectures, the high ASR scores of UGBA prove its transferability in backdooring various types of GNN models.

#### 6.2.2. Comparisons with baseline node injection attacks

We also compare UGBA with two state-of-the-art node injection evasion attacks. Experiments are conducted on Flickr and OGB-arxiv. Three defense models (GCN-Prune, RobustGCN and GNNGuard) are selected to defend against the compared attacks. The ASR of 5 runs is reported in Tab 5. From this table, we observe:

* UGBA can effectively attack the robust GNNs, which shows that UGBA can also bypass the general defense methods with the unnoticeable constraint.
* Compared with node injection attacks, UGBA only requires a very small additional cost in injecting triggers and labels (e.g. 160 poisoned nodes out of 169K nodes in OGB-arxiv). But UGBA can outperform node injection attacks by 30%. This implies the superiority of UGBA in attacking large amounts of target nodes.

### Impacts of the Sizes of Poisoned Nodes

To answer **RQ2**, we conduct experiments to explore the attack performance of UGBA given different budgets in the size of poisoned nodes. Specifically, we vary the sizes of poisoned samples as \(\{80,160,240,320,400,480\}\). The other settings are the same as the evaluation protocol in Sec. 6.1.3. Hyperparameters are selected with the same process as described in Appendix. B. Fig. 4 shows the results on OGB-arxiv. We have similar observations on other datasets. From Fig. 4, we can observe that:

* The attack success rate of all compared methods in all settings increases as the increase of the number of poisoned samples, which satisfies our expectation. Our method consistently outperforms the baselines as the number of poisoned samples increases, which shows the effectiveness of the proposed framework. In particular, the gaps between our method and baselines become larger when the budget is smaller, which demonstrates the effectiveness of the poisoned node selection in effectively utilizing the attack budget.
* When Prune+LD defense is applied on the backdoor attacks, our methods still achieve promising performances, while all the baselines obtain nearly 0% ASR in all settings, which is as expected. That's because our method can generate trigger nodes similar to the attached nodes due to the unnoticeable constraint, which is helpful for bypassing the defense method.

\begin{table}
\begin{tabular}{l l c c c c|c c|c} \hline \hline Datasets & Defense & Clean Graph & SBA-Samp & SBA-Gen & \multicolumn{2}{c}{GTA} & \multicolumn{2}{c}{Ours} \\ \hline \multirow{3}{*}{Cora} & None & 83.09 & 34.94 & 84.09 & 42.54 & 84.81 & 90.25 & 82.88 & **96.95** & **83.90** \\  & Prune & 79.68 & 16.70 & 82.98 & 19.56 & 83.19 & 17.63 & 83.06 & **98.89** & **82.66** \\  & Prune+LD & 79.68 & 15.87 & 79.63 & 17.49 & 80.61 & 18.35 & 80.17 & **95.30** & **79.90** \\ \hline \multirow{3}{*}{Pubmed} & None & 84.86 & 30.43 & 84.93 & 31.96 & 84.93 & 86.64 & 85.07 & **92.27** & **85.06** \\  & Prune & 85.09 & 22.10 & 84.90 & 22.13 & 84.86 & 28.10 & 85.05 & **92.87** & **85.09** \\  & Prune+LD & 85.12 & 21.56 & 84.63 & 22.06 & 83.71 & 22.00 & 83.76 & **93.06** & **83.75** \\ \hline \multirow{3}{*}{Flickr} & None & 46.40 & 0.00 & 47.36 & 0.00 & 47.07 & 88.64 & 45.67 & **97.43** & **46.09** \\  & Prune & 43.02 & 0.00 & 44.01 & 0.00 & 43.78 & 0.00 & 42.71 & **90.34** & **42.99** \\  & Prune+LD & 43.02 & 0.00 & 45.03 & 0.00 & 45.32 & 0.00 & 44.99 & **96.81** & **42.14** \\ \hline \multirow{3}{*}{OGB-arxiv} & None & 65.50 & 0.65 & 65.53 & 11.26 & 65.43 & 75.01 & 65.54 & **96.59** & **64.10** \\  & Prune & 62.16 & 0.03 & 63.88 & 0.01 & 64.10 & 0.01 & 63.97 & **93.07** & **62.58** \\ \cline{1-1}  & Prune+LD & 62.16 & 0.16 & 64.15 & 0.02 & 63.89 & 0.03 & 64.30 & **90.95** & **63.19** \\ \hline \hline \end{tabular}
\end{table}
Table 4. Backdoor attack results (ASR (%) | Clean Accuracy (%)). Only clean accuracy is reported for clean graphs.

Figure 3. Impacts of sizes of poisoned nodes on OGB-arxiv.

\begin{table}
\begin{tabular}{l l c c} \hline \hline Datasets & Defense & TDGIA & AGIA & Ours \\ \hline \multirow{3}{*}{Flickr} & GCN-Prune & 77.01 & 77.22 & **99.91** \\  & RobustGCN & 78.61 & 78.61 & **99.23** \\  & GNNGuard & 55.68 & 56.01 & **99.91** \\ \hline \multirow{3}{*}{OGB-arxiv} & GCN-Prune & 66.17 & 66.33 & **94.05** \\  & RobustGCN & 73.87 & 74.00 & **95.39** \\  & GNNGuard & 42.27 & 42.58 & **96.88** \\ \hline \hline \end{tabular}
\end{table}
Table 5. Comparisons of ASR (%) with node inject attacks.
### Ablation Studies

To answer **RQ3**, we conduct ablation studies to explore the effects of the unnoticeable constraint and the poisoned node selection module. To demonstrate the effectiveness of the unnoticeable constraint module, we set the \(\beta\) as 0 when we train the trigger generator and obtain a variant named as UGBA\(\backslash\)C. To show the benefits brought by our poisoned node selection module, we train a variant UGBA\(\backslash\)S which randomly selects poisoned nodes to attach triggers and assign target nodes. We also implement a variant of our model by removing both unnoticeable constraint and poisoned node selection, which is named as UGBA\(\backslash\)CS. The average results and standard deviations on Pubmed and OGB-arxiv are shown in Fig. 4. All the settings of evaluation follow the description in Sec. 6.1.3. And the hyperparameters of the variants are also tuned based on the validation set for fair comparison. From Fig. 4, we observe that:

* Compared with UGBA\(\backslash\)S, UGBA achieves better attack results on various defense settings. The variance of ASR of UGBA is significantly lower than that of UGBA\(\backslash\)S. This is because our poisoned node selection algorithm selects consistently diverse and representative nodes that are useful for backdoor attacks.
* When the backdoor defense strategy Prune+LD, UGBA can outperform UGBA\(\backslash\)C and UGBA\(\backslash\)CS by a large margin. This implies that the proposed unnoticeable loss manages to guide the trigger generator to give unnoticeable triggers for various test nodes, which can effectively bypass the pruning defenses.

### Similarity Analysis

In this section, we conduct a case study to further explore the similarity of the trigger nodes. We conduct backdoor attacks by using both GTA and our method on OGB-arxiv and then calculate the edge similarities of trigger edges (i.e., the edges associated with trigger nodes) and clean edges (i.e., the edges not connected to trigger nodes). The histogram of the edge similarity scores are plotted in Fig. 5. From the figure, we observe that the trigger edges generated by GTA have low similarities, which implies high risk of trigger elimination with our proposed backdoor defense strategies. In contrast, the edges created by our method present cosine similarity scores that well disguise them as clean edges, which verifies the unnoticeability of our methods.

### Parameter Sensitivity Analysis

In this subsection, we further investigate how the hyperparameter \(\beta\) and \(T\) affect the performance of UGBA, where \(\beta\) and \(T\) control the weight of unnoticeable loss in training the trigger generator and the threshold of similarity scores used in unnoticeable loss. To explore the effects of \(\beta\) and \(T\), we vary the values of \(\beta\) as \(\{0,50,100,150,200\}\). And \(T\) is changed from \(\{0,0.2,0.4,0.6,0.8,1\}\) and \(\{0.6,0.7,0.8,0.9,1\}\) for Pubmed and OGB-arxiv, respectively. Since \(\beta\) and \(T\) only affect the unnoticeablity of triggers, we report the attack success rate (ASR) of attacking against the Prune+LD defense strategy in Fig. 6. The test model is fixed as GCN. We observe that (i): In Pubmed, the similarity threshold \(T\) needs to be larger than 0.2; while \(T\) is required to be higher than 0.8 in OGB-arxiv. This is because edges in OGB-arxiv show higher similarity scores compared with Pubmed. Hence, to avoid being detected, a higher similarity threshold \(T\) is necessary. In practice, the \(T\) can be set according to the average edge similarity scores of the dataset. (ii) When \(T\) is set to a proper value, high ASR can generally be achieved when \(\beta\leq 1\), which eases the hyperparameter tuning.

## 7. Conclusion and Future Work

In this paper, we empirically verify that existing backdoor attacks require large attack budgets and can be easily defended with edge pruning strategies. To address these problems, we study a novel problem of conducting unnoticeable graph backdoor attacks with limited attack budgets. Specifically, a novel poisoned node selection algorithm is adopted to select representative and diverse nodes as poisoned nodes to fully utilize the attack budget. And an adaptive generator is optimized with an unnoticeable constraint loss to ensure the unnoticeability of generated triggers. The effectiveness of generated triggers is further guaranteed by bi-level optimization with the surrogate GCN model. Extensive experiments on large-scale datasets demonstrate that our proposed method can effectively backdoor various target GNN models and even be adopted with defense strategies. There are two directions that need further investigation. First, in this paper, we only focus on node classification. We will extend the proposed attack to other tasks such as recommendation and graph classification. Second, it is also interesting to investigate how to defend against the unnoticeable graph backdoor attack.

Figure 4. Ablation studies on Pubmed and OGB-arxiv.

Figure 5. Edge similarity distributions on OGB-arxiv.

Figure 6. Hyperparameter Sensitivity Analysis
## Acknowledgments

This material is based upon work supported by, or in part by, the National Science Foundation (NSF) under grant number IIS-1707548 and IIS-1909702, the Army Research Office (ONR) under grant number W911NF21-1-0198, and Department of Homeland Security (DNS) CINA under grant number E205949D. The findings in this paper do not necessarily reflect the view of the funding agency.
