Cluster Attack: Query-based Adversarial Attacks on Graph with Graph-Dependent Priors

1 Introduction

Graph neural networks (GNNs) have obtained promising performance in various applications to graph data [Ying et al., 2018; Qiu et al., 2018; Chen et al., 2019]. Recent studies have shown that GNNs, like other types of deep learning models, are also vulnerable to adversarial attacks [Dai et al., 2018; Z¨ugner et al., 2018]. However, there still exists a gap between most of the existing attack setups and practice where the capability of an attacker is limited. Instead of directly modifying the original graph (aka., Graph Modification Attack, GMA) [Yang and Long, 2021], we focus on a more practical setting to inject extra fake nodes into the original graph (aka., Graph Injection Attack, GIA) [Zou et al., 2021]. We perform query-based attack, which indicates that the attacker has no knowledge on the victim model but can access the model with a limited number of queries. As an example in Figure 1, high-quality users in a social network may be misclassified as low-quality users after being connected with a fraudulent user whose features (maybe the meta data of the account) are carefully crafted utilizing query information from the target model.

∗Corresponding author.

Compared to adversarial attacks on image classification [Chen et al., 2017; Ilyas et al., 2018; Dong et al., 2018], the study of query-based adversarial attacks on graph data is still at an early stage. Existing attempts include training a surrogate model using query results [Wan et al., 2021], a Reinforcement-Learning-based method [Ma et al., 2021], derivative-free optimization [Yang and Long, 2021] and a gradient-based method [Mu et al., 2021]. However, most of the existing attacks simply adopt the optimization methods from other fields, such as image adversarial attacks, without utilizing the rich structure of graph data, which has considerable potential to achieve a higher performance attack.

Unlike most previous work, we only allow the adversary to access the information of a small part of the nodes since it is usually impossible to observe the whole graph, especially for large networks in practical scenarios. Moreover, we perform a black-box attack, which does not allow the adversary to have access to the model structures or parameters. The adversary has only a limited number of queries on the victim model about the predicted scores of certain nodes, which is more practical. It is also noted that, owing to the non-i.i.d. nature of graph data, connecting victim nodes to fake nodes may have side effects on the accuracy of victim nodes' neighbors, which is not our purpose. To our best knowledge, this is the first attempt to limit the influence to a certain range of victim nodes and protect the other nodes from being misclassified simultaneously.

We propose a unified framework for query-based adversarial attacks on graphs, which subsumes existing methods. In general, the attacker decides on the current perturbation as a conditional distribution on history query results and current graph status. Under this framework, we propose a novel attack method named Cluster Attack, which considers the graph-dependent priors by better utilizing the unique structure of the graph. In particular, we try to find an equivalent discrete optimization problem. We first demonstrate that a GIA problem can be formulated as an equivalent graph clustering problem. Because the discrete optimization problem of an adjacent matrix can be solved in the context of graph clustering, we prevent query-inefficient searching in the non-Euclidean space. The resulting cluster serves as a graph-dependent prior for the adjacent matrix, which utilizes the vulnerability of the local structure. Second, the key challenge in graph clustering is to define the similarity metric between nodes. We propose a metric to measure the similarity of victim nodes, called Adversarial Vulnerability; this is related to how the victim nodes will be affected by the injected fake node, and we cluster the victim nodes accordingly. The Adversarial Vulnerability is only related to the local structure of the graph and thus can be handled with only part of the graph observed.

Our contributions are summarized as follows:

• We propose a unified framework for query-based adversarial attacks on graphs, which formulates the current perturbation as a conditional distribution on the history of query results and on the current graph status.
• We propose Cluster Attack, an injection adversarial attack on a graph, which formulates a GIA problem as an equivalent graph clustering problem and thus solves the discrete optimization of an adjacent matrix in the context of clustering.
• After providing theoretical bounds on our method, we empirically show that our method achieves high performance in terms of success rate of attacks under an extremely strict setting with a limited number of queries and only part of the graph observed.

2 Background

In this section, we present recent works on node classification and adversarial attacks on graphs.

2.1 Node Classification on a Graph

Node classification on graphs is an important task, with a wide range of applications such as user classification in financial networks. It aims to carry out classification by aggregating the information from neighboring nodes [Kipf and Welling, 2017; Hamilton et al., 2017; Veliˇckovi´c et al., 2017]. Recent work has carried out node classification using graph convolutional networks (GCNs) [Kipf and Welling, 2017], which is one of the most representative GNNs. Specifically, let a graph be G = (A, X), where A and X respectively represent the adjacency matrix and the feature matrix. Given a subset of labeled nodes in the graph, GCN aims to predict the labels of the remaining unlabeled nodes in the graph as

where ˆA is the normalized adjacency matrix; W(0) andW(1) are parameter matrices; σ is the activation function; and f(G) is the prediction corresponding to each node.

2.2 Graph Adversarial Attacks

Numerous methods have been developed to perform adversarial attacks on graphs. Early works focused on modifying the original graph (i.e., Graph Modification Attack) [Dai et al., 2018; Z¨ugner et al., 2018], while some recent works [Zou et al., 2021; Tao et al., 2021] have focused on a more practical setting to inject extra fake nodes into the original graph (i.e., Graph Injection Attack). For query-based graph adversarial attacks, as shown in Table 1, various efforts have been made. Some have focused on attacking the task of node classification [Yang and Long, 2021] while there also have been efforts to attack graph classification [Wan et al., 2021; Ma et al., 2021; Mu et al., 2021], with gradient-based [Mu et al., 2021] or gradient-free methods [Yang and Long, 2021; Wan et al., 2021; Ma et al., 2021]. Nevertheless, most of the existing attacks just adopt optimization methods from other fields (especially image adversarial attack), ignoring the unique structure of graph data. In this work, we propose to attack in a graph-specific manner utilizing the inherent structure of a graph.

3 AUnified Framework for Query-Based Adversarial Attacks on Graphs

We now present a unified framework for query-based adversarial attacks as well as the threat model and loss function.

3.1 Graph Injection Attack

Given a small set of victim nodes ΦA ⊆ Φ in the graph, the goal of graph injection attack is to perform mild perturbations on the graph G = (A,X), leading to G+ = (A+,X+), such that the predicted labels of the victim nodes in ΦA are changed into the target labels. This goal is usually achieved by optimizing the adversarial loss L(·) under constraints as:

where dist(G, G+) denotes the magnitude of perturbation and has to be within the adversarial budget ∆. In this section, it can be specified as |Φfake| ≤ ∆fake and ∑u∈Φfake d(u) ≤ ∆edge with d(u) being the degree of node u.

In graph injection attacks, we have the augmented adjacent

denote the node set of G+. In particular, Xfake corresponds to the feature of fake nodes; B denotes the connections between fake nodes and original nodes, and Afake denotes the mutual connections between fake nodes. The malicious attacker manipulates Afake,B and Xfake, leading to as low classification accuracy on ΦA as possible.

In a query-based adversarial attack on graphs, we uniformly formulate the update of a graph at time t as

where {f(Gi)|i = 1, 2, ..., qt} denotes the feedback (hard labels or predicted values) of total qt queries in the history from the target model. A curated list of current query-based graph adversarial attacks is shown in Table 1. In general, perturbation ∆G(t) in time step t is conditioned on the history of query results {f(Gi)|i = 1, 2, ..., qt} and the current graph status G. Previous work has focused on using different optimization methods, including reinforcement learning [Ma et al., 2021] and gradient-based optimization [Mu et al., 2021] to decide ∆G without utilizing the graph structure explicitly.

3.2 Threat Model

Adversary Capability. We greatly restrict the attacker's ability so that we can only make connections between victim nodes and fake nodes. No connections can be made between fake nodes because connected malicious fake nodes are easier for detectors to locate. The number of new edges ∆edge is set as barely the number of victim nodes ΦA, which means that each victim node is connected by only one new edge.

Protected Nodes. As mentioned above, owing to the noni.i.d nature of graph data, attacking victim nodes may have unintended side effects on their neighboring nodes. While attacking victim nodes, we simultaneously aim to keep the labels of untargeted nodes unchanged, to make our perturbation unnoticeable. In our setting, we try to protect Nk(ΦA), which are the neighbors of the victim nodes within k-hop.

Partial Information. It is practical to assume that the attacker has access to only part of the graph when conducting the attack. As mentioned above, we adopt an extremely strict setting so that we can only observe the features and connections of the observed nodes defined as

Limited Queries. It is practical in real scenarios that we have a limited number of queries to the victim model rather than full outputs of arbitrarily many chosen inputs. In our setting, we can query at most K times in total for the predicted scores of the observed nodes. The architecture and parameters about the victimmodel are unknown to the attacker.

3.3 Loss Function

We aim to make the classifier misclassify as many nodes as possible in the victim set of ΦA . As it is nontrivial to directly optimize the number of misclassified nodes since the objective is discrete, we choose to optimize a surrogate loss function:

where ℓ(G+, v) and ℓN(G+, v) represent the loss functions for each victim node and for a protected node, respectively. A smaller ℓ(G+, v) means that node v is more likely to be misclassified by the victim model f; by contrast, a smaller ℓN(G+, v) means that the predicted label of node v is less likely to be changed during our attack. In particular, we design our loss in the manner of the C&W loss [Carlini and Wagner, 2017], and define:

where yt stands for the target label of node v and the attacker succeeds only when node v is misclassified as yt. σ(x) = max(x, 0). [f(G+)]v,yi denotes the output logit of node v of class yi. For protected nodes, we define:

where yg is the ground-truth label of v from the victimmodel.

4 Cluster Attack with Graph-Dependent Priors

4.1 Cluster Attack

The combinatorial optimization problem (5) is hard to solve owing to the non-Euclidean nature of the adjacent matrix and the complex structure of neural networks. To tackle this, we tried to find an equivalent combinatorial optimization problem and transform our GIA problem into a well-studied one. Here, we point out that every choice of adjacent matrix has an equivalent representation of a division of victim nodes into clusters. Thus, we get our key insight that this discrete optimization problem can be transformed into an equivalent graph clustering problem, which is a well-studied discrete optimization problem [Schaeffer, 2007].

Proposition 1 (GIA/Graph Clustering Equivalence). Given graph G and a set of nodes ΦA ⊆ Φ, for a division of the victim nodes ΦA into Nfake clusters C = {C1, C2, ..., CNfake }, ∪Ci∈CCi = ΦA, there exists a corresponding B and vice versa.

Proof. We provide a one-to-one mapping between cluster C and adjacent matrix B. Specifically, given C = {C1, C2, ..., CNfake }, ∪Ci∈CCi = ΦA we get B from

We have

Thus, we resultant B is valid in our setting.

Given B where |ΦA| = ∆edge = ∑i ∑j Bij , we derive the cluster C from

In our setting, each victim node is connected to only one fake node, which indicates

In this case, each cluster gets disjoint with each other

Because Afake = 0 is fixed in our setting, we formulate our graph injection attack problem as an equivalent graph clustering problem. As a result, the non-trivial discrete optimization problem of the adjacency matrix can be solved in the context of graph clustering. The resulting cluster serves as a graph-dependent prior for adjacent matrix B, which prevents inefficient searching in non-Euclidean discrete space.

For graph clustering, the main concern is the metric of the similarity between victim nodes. To investigate how a fake node will affect the performance on a certain node, we propose Adversarial Vulnerability as the similarity metric for graph clustering. Adversarial Vulnerability of a victim node reflects its "most vulnerable angle" towards adversarial features of fake nodes, which is related only to the local structure of the graph and can be handled with only part of the graph observed. We have the insight that victim nodes sharing similar Adversarial Vulnerability are more likely to be affected simultaneously when they are connected to the same fake node.

Definition 1 (Adversarial Vulnerability). For victim node v ∈ Φ, its Adversarial Vulnerability is defined as

where xu denotes the feature of fake node u connected to node v. For the fake node itself, the Adversarial Vulnerability is defined as its own feature.

Here, we adopt Euclid's distance as distance metric between victim nodes' Adversarial Vulnerability which is in Euclidean feature space.

Definition 2 (Adversarial Distance Metric). ∀v, u ∈ Φ+, the Adversarial Distance Metric between node v and u is defined as d(v, u) = ||AV(v) - AV(u)||22 .

After the Adversarial Vulnerability is computed, the objective of the cluster algorithm is to minimize the following cluster distance as

where the cluster center ci is the corresponding fake node of cluster Ci, and

4.2 Optimization

To approximate Adversarial Vulnerability, we adopt zerothorder optimization [Chen et al., 2017], which is similar to query-based attacks on image classification, to better utilize limited queries. For graph with discrete features, the optimization of Eq. (13) can be

where δXij denotes the tentative perturbation in dimension j of a feature of the ith fake node and I(·) is the indicator function. A tentative perturbation is adopted only if it diminishes the adversarial loss. For continuous feature space, we adopt NES [Ilyas et al., 2018] for gradient estimation as

where σ > 0 is the standard variance, n is the size of the NES population and Zi ∼ N(0, INfake×D) is the perturbation of Xfake. After gradient estimation, gradient-based optimization methods can be adopted. Here, we use Projected Gradient Descent (PGD) [Madry et al., 2018] to optimize Xfake.

Our method is outlined in Figure 2. With the resultant Adversarial Vulnerability, we solve the optimization of Eq. (14) by K-Means clustering. After that, the features of fake nodes, initialized as the cluster center in Eq. (15), are optimized using Eq. (16) and Eq. (17). More details of our algorithm are deferred to the appendix.

4.3 Theoretical Analysis

Connecting fake nodes to an original graph brings a victim node (1) one 1-hop neighbor (the fake node connected to it); (2) neighbors at a farther distance connected through this fake node; (3) fake nodes connected to other victim nodes which are at least 2-hop away. It is noted that 1-hop neighbors are often dominant. Here we leave out the influence of farther neighbors caused by the fake node and fake nodes connected to other victim nodes which are at least 2-hop or even farther. The loss function over the ith victim node vi ∈ ΦA in Eq. (5) can thus be seen as a function of fake nodes' features (here we set a trade-off parameter λ = 0 for analysis). We have

where xi denotes fake nodes' features connected to victim node vi. Theoretically, we provide our bounds under certain smooth conditions which hold for numerous neural networks. Definition 3 (W-condition). We say that a function L(G) = ∑|ΦA| i=1 li(xi) satisfies the W-condition, if and only if ∀1 ≤ i ≤ |ΦA|, li(·) satisfies the Lipschitz condition of order 2. In this case, we have

mi||xi -x∗i ||22 ≤ li(xi) - li(x∗i ) ≤Mi||xi -x∗i ||22 , (19) where 0 ≤ mi ≤ Mi are constants and 1 ≤ i ≤ |ΦA|. x∗i is the minimum of li(·).

Note that M exists because the loss function satisfies the Lipschitz condition of order 2 under W-condition; and it also includes m because m = 0 always satisfies Eq. (19). Under W-condition, we derive our bounds on the difference in adversarial loss between our results and optimal adversarial examples.

Proposition 2. If L(·) in Eq. (18) satisfies the W-condition, Gm is the optimal choice of Eq. (2) and G′ is the optimal given by the Cluster Attack of Eq. (14). Then, we have

Proof. We have

where xmi and x′i are features of the fake node connected to ith victim node provided by Eq. (2) and Cluster Attack of Eq. (14), respectively.

Proposition 2 indicates that the difference in adversarial loss between our results and optimal adversarial examples is bounded by the minimal cluster distance in Eq. (14) and how each li(·) is linear to ||xi -x∗i ||22 .

5 Experiments

5.1 Experimental Setup

Dataset. We do our experiments on Cora and Citeseer [Sen et al., 2008], which are two benchmark small citation networks with discrete node features, and on Reddit [Hamilton et al., 2017] and ogbn-arxiv [Hu et al., 2020], which are two large networks with continuous node features. The statistics of the datasets are shown in Table 2.

Parameters. For each experimental setting, we run the experiment for 100 times and report the average results. In each round, we randomly sample |ΦA| nodes as victim nodes. We set k = 1 in Nk(ΦA), which means we aim to protect the 1-hop neighbors of victim nodes. Without specification, we compare our method with baselines with a trade-off parameter set as λ = 0 in Eq. (5).

Comparison Methods. Since this study is the first to perform query-based injection attack on node classification, most of the previous baselines on graph injection attacks cannot be easily adapted to our problem. We include the following baselines:

Random Attack, which decides the fake nodes' features and connections between fake nodes and original nodes randomly.

NETTACK, one of the most effective attacks by first adding several nodes and then adding many edges between the fake nodes and original nodes [Z¨ugner et al., 2018].

NETTACK - Sequential, which is a variant of NET-

TACK [Z¨ugner et al., 2018] by sequentially adding fake nodes. Fake Node Attack, which adds fake nodes in a white-box

attack scenario [Wang et al., 2018].

G-NIA, a white-box graph injection attack [Tao et al., 2021]. We refer to the reported results on Citeseer.

TDGIA, a black-box GIA method with superior performance to all the baselines in KDD Cup 2020 1 of graph injection attack. We mainly compare our method with this method. Note that TDGIA is not query-based [Zou et al., 2021].

1 https://www.kdd.org/kdd2020/kdd-cup

Among the above baselines, TDGIA is performed in a continuous feature space while NETTACK and Fake Node Attack are performed in discrete feature spaces.

5.2 Quantitative Evaluation

Without loss of generality, we uniformly set Nfake = 4 and let the number of victim nodes vary to see the performance under different Nfake : |ΦA|.

Performance on Small Datasets with Discrete Features

We first evaluate the performance of the Cluster Attack along with other baselines on Cora and Citeseer with discrete features. The number of queries K is set to K = |ΦA| · Kt + Nfake · Kf , where Kt = Kf = D (feature dimension). The results are shown in Table 3. Our algorithm outperforms all baselines in terms of success rates. This is because our method prevents inefficiently searching the non-Euclidean space of the adjacent matrix and better utilizes the limited queries in searching the Euclidean feature space. The results also demonstrate that the Adversarial Vulnerability is a good metric for clustering the victim nodes.

Performance on Large Datasets with Continuous Features

In this section, we evaluate the performance of the Cluster Attack on Reddit (with 1500|ΦA| + 750Nfake queries) and obgn-arxiv (with 4000|ΦA| + 2000Nfake queries), two large networks with continuous feature whose victim nodes have a higher average degree. We compare our method with the state-of-the-art method which has superior performance to other baselines. In these challenging datasets, we perform an untargeted attack, which means attacker successes when the predicted labels of victim nodes are changed. The results are shown in Table 4. Our algorithm outperforms the baseline in terms of success rates. This is because, with the cluster prior of the adjacent matrix, our Cluster Attack prevents inefficiently searching in non-Euclidean space and make the best use of the limited queries to search the Euclidean feature space. Another reason is because of the good metric of the Adversarial Vulnerability, which provides an appropriate cluster prior.

5.3 Ablation Study

Performance with Different Trade-Off Parameters λ

In this section, we examine the performance of Cluster Attack with different trade-off parameters λ between fake nodes and protected nodes in the Cora dataset. We uniformly set Nfake = 4, |ΦA| = 10. We choose two competitive baselines and adapt their loss functions to our trade-off format. The results are shown in Figure 3. It can be seen from Figure 3 that, when λ increases (which means that we pay more attention to the protected nodes), the percentage of protected nodes whose labels remain unchanged during the attack also increases. This is because we try to protect the labels of the protected nodes from being changed in a trade-off formulation in our loss function, Eq. (5). Also, our trade-off formulation can be generalized to other baselines, as shown in Figure 3. This is because we design our loss function in Eq. (5) in a generalizable manner independent of attack method.

• (a) Success rates of attack
• (b) Percentage of unchanged protected nodes

Figure 3: Cluster Attack in Cora with different λ.

Performance with Different Number of Queries

In this section, we examine the performance of Cluster Attack with a different number of queries. We set Kt = Kf = α · D and examine the performance under different α in Cora and Citeseer dataset. We uniformly set Nfake = 4, |ΦA| = 10 with λ = 0 and λ = 1. The results are shown in Figure 4. The success rate of Cluster Attack drops as the number of queries drops. Our algorithm still performs well when the number of queries drops slightly, especially when α ≥ 0.4. This demonstrates that our Cluster Attack can work in a queryefficient manner. This is because cluster algorithm provides graph-dependent priors for the adjacent matrix and thus prevents inefficient searching. Searching in the Euclidean feature space is more efficient.

We provide additional experiments in the appendix. The experiments show that nodes with a lower degree are more likely to get misclassified under attack. Also, when the number of fake nodes increases, the success rate of the attack increases too, which is consistent with our intuitive understanding. We provide an ablation study on the cluster metric of Adversarial Vulnerability. We find that original Cluster Attack performs better than Cluster Attack without Adversarial Vulnerability, i.e., the victim nodes' Adversarial Vulnerabilities are randomly set. This result demonstrates the effectiveness of our Adversarial Vulnerability.

6 Conclusion

In this paper, we provide a unified framework for query-based adversarial attacks on graphs. Under the framework, we propose Cluster Attack, a query-based black-box graph injection attack with partial information. We demonstrate that a graph injection attack can be formulated as an equivalent clustering problem. The difficult discrete optimization problem of the adjacent matrix can thus be solved in the context of clustering. After providing theoretical bounds on our method, we empirically show that our method has strong performance in terms of the success rate of attacking.

Ethical Statement

The safety and robustness of AI are attracting more and more attention. In this work, we propose a method of adversarial attack. We hope our work reveals the potential weakness of current graph neural networks to some extent, and more importantly inspires future work to develop more robust graph neural networks.

Acknowledgments

This work was supported by the National Key Research and Development Program of China (Nos. 2020AAA0104304, 2017YFA0700904), NSFC Projects (Nos. 62061136001, 61621136008, 62076147, U19B2034, U19A2081, U1811461), the major key project of PCL (No. PCL2021A12), TsinghuaAlibaba Joint Research Program, Tsinghua-OPPO Joint Research Center, and the High Performance Computing Center, Tsinghua University.