Graph Universal Adversarial Attacks: A Few Bad Actors Ruin Graph Learning Models

1 Introduction

Graph structured data are ubiquitous with examples ranging from proteins, power grids, traffic networks, to social networks. Deep learning models for graphs, in particular, graph neural networks (GNN) [Kipf and Welling, 2017; Hamilton et al., 2017; Veliˇckovi´c et al., 2017] attracted much attention recently and have achieved remarkable success in several tasks, including community detection, link prediction, and node classification. Their success is witnessed by many practical applications, such as content recommendation [Wu et al., 2019b], protein interaction [Tsubaki et al., 2018], and blog analysis [Conover et al., 2011].

∗Contact Author

Deep learning models are known to be vulnerable and may suffer intentional attack with unnoticeable change of the data [Z¨ugner et al., 2018]. This observation originated from early findings by [Szegedy et al., 2014] and [Goodfellow et al., 2014], who show that images perturbed with adversarially designed noise can be misclassified, while the perturbation is almost imperceptible. This minor but intentional change would result in severe consequences socially and economically. For example, Wikipedia hoax articles can effectively disguise through modifying their links in a proper manner [Kumar et al., 2016]. For another example, frauds may hide themselves through building plausible friendship in a social network, to confuse the prediction system.

In this work, we study the vulnerability of GNNs and show that it is possible to attack them if a few graph nodes serve as the bad actors: when their links to a certain node are flipped, the node will likely be misclassified. Such attacks are akin to universal attacks because the bad actors are universal to any target. We propose a graph universal adversarial attack method, GUA, to identify the bad actors.

Our work differs from recent studies on adversarial attack of GNNs [Dai et al., 2018; Z¨ugner et al., 2018; Jin et al., 2019] in the attack setting. Prior work focuses on poisoning attacks (injecting or modifying training data as well as labels to foster a misbehaving model) and evasion attacks (modifying test data to encourage misclassification of a trained model). For graphs, these attacks could modify the graph structure and/or node features in a target-dependent scenario. The setting we consider, on the other hand, is a single and universal modification that applies to all targets. One clear advantage from the attack point of view is that computing the modification incurs a lower cost, as it is done once for all. While universal attacks were studied earlier (see, e.g., [Moosavi-Dezfooli et al., 2017] who compute a single perturbation applied to all images in ImageNet), graph universal attacks are rarely explored. This work contributes to the literature a setting and a method that may inspire further study on defense mechanisms of deep graph models.

Figure 1 illustrates the universal attack setting we consider. A few bad-actor nodes (4, 5, and 7) are identified; we call them anchor nodes. When an adversary attempts to attack the classification of a target node (say, 2), the existing links from the anchor nodes to the target node are removed while nonexisting links are created. The identification method we propose, GUA, is conducted on a particular classification model (here, GCN), but the found anchors apply to other models as well (e.g., DeepWalk, node2vec, and GAT).

As a type of attacks, universal attacks may be preferred by the adversary for several reasons. First, the anchor nodes are computed only once and there incurs no extra cost when attacking individual targets. Second, the number of anchors can be very small (it is easier to compromise fewer nodes). Third, attacks are less noticeable when only a limited number of links are flipped.

The contribution of this work is threefold:

• We propose a novel algorithm for graph universal attack that achieves high success rate and demonstrates vulnerability of graph deep learning models.
• We demonstrate appealing generalization of the attack algorithm, which finds anchor nodes based on a small training set but successfully attacks a majority of target nodes.
• We show attractive transferability of the found anchors (based on GCN) through demonstrating similar attack success rates on other graph learning models.

2 Notation and Background

A graph is denoted as G = (V,E), where V is the node set and E is the edge set. An unweighted graph is represented by the adjacency matrix A = {0, 1}|V |×|V | . The graph nodes have d-dimensional features, which collectively form the feature matrix X, whose dimension is |V | × d.

In GCN [Kipf and Welling, 2017], one normalizes the adjacency matrix into ̂ A = ˜D- 12 ˜ A˜D- 12 , where ˜ A = A + I and ˜D is the diagonal adjusted degree matrix with diagonal entries ˜Dii = ∑|V | j=1 ˜ Aij. Then, the neural network is

where W (0) and W (1) are model parameters. The training of the parameters uses the cross-entropy loss.

3 Graph Universal Adversarial Attack

Following the notation introduced in the preceding section, given the graph adjacency matrix A and node feature matrix X, we let f(A,X) be the classification model and let ˆl(A,X, i) be the predicted label of node i; that is, ˆl(A, X, i) = arg max f (A, X)i.

Given a trained model f, the goal is for each node i to modify the adjacency matrix A into A′ such that ˆl(A′ , X, i) ̸=

ˆl(A,X, i). Note that the modified A′ is i-dependent in our attack setting.

3.1 Attack Vector andMatrix

Let the graph have n nodes. We use a length-n binary vector p to denote the attack vector to be determined, where 1 means an anchor node and 0 otherwise. Hence, A′ is a function of three quantities: the original adjacency matrix A, the target node i, and the attack vector p.

To derive an explicit form of the function, we extend the vector p to an n × n matrix P , which starts as a zero matrix, with the ith row and ith column replaced by the attack vector p. Thus, the (i, j) element of the attack matrix P indicates whether the connection of the node pair (i, j) is flipped: 1 means yes and 0 means no.

It is then not hard to see that one may write the function

where 1 denotes the matrix of all ones and 10 is similar except that the diagonal is replaced by zero; ◦ means element-wise multiplication. The term (1 - P) serves as the mask that preserves the connections of all node pairs other than those between the anchors j and the target node i. The term (10 - A) intends to flip the whole A (except diagonal) but the P in the front ensures that only the involved (i, j) pairs are actually flipped. Moreover, one can verify that the diagonal of the new adjacency matrix remains zero.

For gradient based optimization, the binary elements of the attack vector p may be relaxed into real values between 0 and 1. In this case, the connections of all node pairs other than those between the anchors j and the target node i remain the same. On the other hand, the connections between the involved (i, j) pairs are fractionally changed. The jth element of p indicates the strength of change.

3.2 Outer Procedure: GUA

Let VL be the training set with known node labels. Given an attack success rate threshold δ, we formulate the problem as finding a binary vector p such that

To effectively leverage gradient-based tools for adversarial attacks, we perform a continuous relaxation on p so that it can be iteratively updated. Now elements of p stay in the interval [0, 1]. The algorithm proceeds as follows. We initialize p with zero. In each epoch, we begin with a binary p and iteratively visit each training node i. If i is not misclassified by the current p, we seek a minimum continuous perturbation ∆p to misclassify it. In other words,

We will elaborate in the next subsection an algorithm to find such ∆p. After all training nodes are visited, we perform a hard threasholding at 0.5 and force back p to be a binary vector. Then, the next epoch begins. We run a maximum number of epochs and terminate when (3) is satisfied.

Algorithm 1 Graph Universal Attack (GUA)

Input: adjacency matrix A, node features X, max epoch, max iteration max iter, δ, data overshoot p ← 0 while epoch < max epoch do for i ∈ VL do A′ ← g(A, i, p) if ˆl(A′ , X, i) = ˆl(A, X, i) then ∆p, iter ← IMP(A′ , i, overshoot, max iter) p ← p + ∆p p ← L2-norm projection(p) p ← p.clip(0, 1) end if end for p ← (p > 0.5) ? 1 : 0 compute Err(VL) if Err(VL) ≥ δ, break end while return p

The updated p ← p + ∆p found through solving (4), if unbounded, may be problematic because (i) it may incur too many anchor nodes and (ii) its elements may be outside [0, 1]. We perform an L2-norm projection to circumvent the first problem and a clipping between interval [0, 1] to circumvent the second. The rationale of L2-norm projection is to suppress the magnitude of p and encourage that eventually few entries are greater than 0.5. The maximum number of anchor nodes grows quadratically with the projection radius ξ. A small ξ clearly encourages fewer anchors.

Through experimentation, we find that clipping is crucial to obtaining a stable result. In a later section, we illustrate an experiment to show that the attack success rate may drop to zero in several random trials, if clipping is not performed. See Figure 2(a).

The procedure presented so far is summarized in Algorithm 1. The algorithm for obtaining ∆p is called IMP (iterative minimum perturbation) and will be discussed next.

3.3 Inner Procedure: IMP

To solve (4), we adapt DeepFool [Moosavi-Dezfooli et al., 2016] to find a minimum perturbation that sends the target node i to the decision boundary of another class.

Denote by v the minimum perturbation. To find the closest decision boundary other than that of the original class pred = ˆl(A,X, i), we first select the closest class k = argminc̸=pred |∆fc| ‖∆wc‖2 , where ∆fc = f(A,X)i,c - f(A,X)i,pred and ∆wc = ∇f(A,X)i,c -∇f(A,X)i,pred. Then, we update v by adding to it ∆v:

We iteratively update v until (1+overshoot)×v successfully attacks node i, where overshoot is a small factor that ensures the node passes the decision boundary. We also clip the new A′ to ensure stability, in a manner similar to the handling of p in the preceding subsection. The procedure for computing the minimum perturbation v is summarized in Algorithm 2.

Algorithm 2 Iterative Minimum Perturbation (IMP)

Input: A, node index i, overshoot, max iter v ← 0 iter ← 0 pred ← ˆl(A, X, i) A′ ← A while ˆl(A′ , X, i) = pred and iter < max iter do ∆v ← |∆fk| ||∆wk ||22 ∆wk according to Equation (5) v ← v + ∆v A′ ← g(A, i, (1 + overshoot) × v).clip(0, 1) end while v ← (1 + overshoot) × v return v, iter

4 Experiments

In this section, we evaluate thoroughly the proposed attack GUA through investigating its design details, comparing with baselines, performing scalability tests, and validating transferability from model to model. Code is available at https: //github.com/chisam0217/Graph-Universal-Attack.

4.1 Datasets and Settings

We compute the anchor set through attacking the standard GCN model. The parameters of Algorithms 1 and 2 are: max epoch = 100, max iter = 20, δ = 0.9, and overshoot = 0.02. To cope with randomness, experiments are repeated ten times for each setting. We work with three commonly used node classification benchmark datasets [Sen et al., 2008]. Their information is summarized in Table 1.

4.2 Baseline Methods

Because graph universal attacks were barely studied, we design four relavant baselines for GUA. The first two are basic while the last two are more sophisticated.

• Global Random: Each node has a probability Prob to become an anchor node. In other words, each element of the attack vector p is an independent sample of Bernoulli(P rob).
• Victim-Class Attack (Victim Attack): We sample a prescribed number of anchor nodes without replacement from nodes of a particular class. This baseline originates from a finding that the anchor nodes computed by GUA often belong to the same class (see more details later).
• High-Degree (HD) Global Random: We strengthen the Global Random baseline by picking random anchors uniformly from top 10% nodes with highest degrees.

• Top-Confidence (TC) Victim Attack: The anchor set is composed of nodes with the highest prediction probability from the victim class.

Additionally, we compare with Fast Gradient Attack (FGA) [Chen et al., 2018] and Nettack [Z¨ugner et al., 2018], both of which are per-node attack methods. They are not universal attacks. FGA flips edges/non-edges connecting to different nodes depending on the target, while Nettack modifies not only the edges, but also the node features. We also compare with Meta-Self Attack [Z¨ugner and G¨unnemann, 2019], which performs the global attack by perturbing the graph structure through meta learning.

4.3 Results

The evaluation metric is attack success rate (ASR). Another quantity of interest is the number of modified links (ML). For universal attacks, it is equivalent to the anchor set size.

Importance of clipping. As discussed in the design of GUA, the continuous relaxation of the attack vector p requires clipping throughout optimization. For an empirical supporting evidence, we show in Figure 2(a) the ASR obtained through executing Algorithm 1 with and without clipping, respectively. Clearly, clipping leads to stabler and superior results. Without clipping, the ASR may drop to zero in some random trials. The reason is that several entries of p become strongly negative, such that projections result in small values for all positive entries and subsequent hard thresholding zeros out the whole vector p.

Effect of projection radius. The L2-norm projection radius is a positive quantity ξ so that the projection of p is ξ · p/‖p‖2. The number of anchors is implicitly controlled by the projection radius ξ. Increasing ξ will enlarge the anchor set. We treat ξ as a parameter and study its relationship with the number of anchor nodes and corresponding ASR. See Table 2. As expected, the average ML (that is equal to the number of anchor nodes) increases with ξ non-linearly. A larger anchor set also frequently results in higher ASR, because of more changes to the graph. Additionally, the individual result for each trial may suggest even more attractive findings. For example, for the case of Cora and ξ = 4, the MLs for the ten trials are {5, 9, 10, 7, 8, 9, 9, 9, 6, 7} and the corresponding ASRs are {0.780, 0.875, 0.869, 0.850, 0.866, 0.880, 0.874, 0.813, 0.805, 0.809}. This result means that as few as six anchor nodes are sufficient to achieve 80% ASR. The different number of anchors under the same ξ also corroborates the above statement that the number of anchors is implicitly controlled by the projection radius ξ. In Figure 3, we plot the average ASRs with respect to different L2-norm projection radius. For Cora, Citeseer and Pol.Blogs, the plateaued ASR is 89.91%, 84.77% and 52.31%, at ξ = 8, ξ = 9 and ξ = 12, respectively. On the other hand, one also sees that the attacks on Pol.Blogs are less effective. The reason is that the graph has a large average degree, which makes it relatively robust to universal attacks. As observed by [Z¨ugner et al., 2018] and [Wu et al., 2019a], nodes with more neighbors are harder to attack than those with fewer neighbors. The higher density of the graph requires a larger anchor set to achieve high ASR. We intend to maintain a small anchor set for secretive attacks. Thus, keeping the other hyperparameters the same, we report future results by setting ξ = 4, 4, 8 on Cora, Citeseer and Pol.Blogs, respectively.

Nodes with low connectivity are easier to attack. On Cora, when ξ = 4, the average degree of successfully attacked nodes is 4.29, while that of failed ones is 7.08. This result also corroborates the conclusions from [Z¨ugner et al., 2018], that low-degree nodes are easier to attack. The phenomenon is not surprising since the neighborhoods of lowdegree nodes tend to be dominated by anchors.

Blindly using more anchors does not work. Now that we have an effective method to compute the anchor nodes, we investigate whether randomly chosen anchor nodes are similarly effective. In Figure 4, we plot the ASR results of Global Random. One sees that all ASRs for Cora are below 40% and for Citeseer below 30%. Such results are way inferior to those of GUA. Moreover, using hundreds and even a thousand anchors does not improve the ASR.

Anchors often belong to the same class. With analysis of the anchors, an interesting finding is that one class dominates. The average entropies of the anchors' class distribution on Cora, Citeseer and Pol.blogs are 0.1, 0.1, and 0, respectively. This indicates that in most of the cases only one class appears. One possible reason is that anchors united by the same class form an overwhelming influence: either to allure a node into this class through establishing links or kick it out of the class through eliminating links. Actually, one of our baselines, Victim-Class Attack, is designed for such a phenomenon.

Wrong classifications often coincide with the anchor class. A natural conjecture following the above finding is that a target node will be misclassified to the (majority) class of the anchors. Our experiment on Cora corroborates this conjecture. The results indicate that 96% of the test nodes are misclassified to class 6 when all the anchor nodes belong to this class. An analysis of the dataset shows that each node has two neighbors on average. Hence, flipping the connections to the anchor nodes possibly makes the anchor class dominate among the new set of neighbors. Then, classifying into the anchor class becomes more likely. This result echoes one mentioned by [Nandanwar and Murty, 2016], who conclude that classification of a node is strongly influenced by the classes of its neighbors; it tends to coincide with the majority class of the neighbors. To generalize the above result, we collect the entropy change of the class distribution before and after attack. On Cora, Citeseer and Pol.Blogs, the changes are respectively -1.66, -1.49 and -0.07. For all datasets, the entropy decreases, indicating stronger dominance of one class after attack. The decrease is more substantial for Cora and Citeseer than for Pol.Blogs, which is expected, because the latter has denser and more varied connections, which eclipse the dominance of the anchor class. To further illustrate the dominance of the anchor class, we investigate the ASRs of the nodes from anchor class versus non-anchor class. The ASRs are strikingly different. For example, on Cora, when ξ = 4, the ASR of nodes from the "anchor class" is 0%, while that of nodes from "non-anchor class" is 96.5%. Such a phenomenon is expected. In most cases, flipping the edges with the anchor nodes results in dominance of the anchor class. Furthermore, we find that 99.9% of the successfully attacked targets are misclassified into the anchor class, corroborating the theory.

Comparison with baselines. We compare GUA with four baseline methods explained in Section 4.2, together with two non-universal attacks and one global attack. Since we cannot choose the number of anchor nodes for GUA, we obtain this value based on the results in Table 1 when ξ = 4, 4, 8 on Cora, Citeseer and Pol.Blogs, respectively. In this case, the average ML for these datasets is respectively 7.9, 7.7, and 26.6. Therefore, we set the number of anchor nodes for all baselines, but for Global Random and Meta-Self, to be the ceiling of these values. For Global Random, Prob is set such that the expected number of anchor nodes is these values. For Meta-Self, the MLs are 53, 47 and 167 for Cora, Citeseer and Pol.Blogs, respectively, which are 1% of the number of original edges in corresponding datasets. From Table 3, one sees that GUA significantly outperforms other universal attack methods. Among them, Top-Confidence Victim-Class Attack is the most effective, but it is still inferior to GUA. This result suggests that GUA leverages more information (in this case, node features) than the class labels, although we have seen strong evidences that anchor nodes computed by GUA mostly belong to the same class. One also sees that GUA is inferior to FGA and Nettack if only ASR is concerned. FGA and Nettack are not universal attack methods; they find different anchors for each target node. Thus, it is possible to optimize the number of anchors (possibly different for each target) to aim at a certain ASR, or equivalently, to achieve a better ASR given a certain number of anchors. However, it is also because they are non-universal attacks, that the total number of anchors for all targets soars. For example, FGA modifies links with 1406 anchors on Cora and 1359 anchors on Citeseer in total. GUA also significantly outperforms Meta-Self, since it only attacks the graph once, instead of attacking each node individually.

Effect of removing anchor nodes. Once a set of anchor nodes is identified, a natural question asks if the set contains redundancy. We perform the following experiment: we randomly remove a number of anchor nodes and recompute the ASR. Because on Cora and Citeseer, the average number of anchor nodes for ξ = 4 is 7.9 and 7.7 respectively, we use an anchor set of size eight to conduct the experiment. For each

Table 3: Average ASR. For a fair comparison, all universal attack methods except Global Random use the same number of anchor nodes. FGA and Nettack are not universal attacks and we set their ML per node to be the same as the number of anchor nodes.

case, we randomly remove 1-7 nodes from the anchor set and report the corresponding average ASR. The results are shown in Figure 2(b). From the figure, one sees that the average ASR gradually decreases to zero as more and more anchor nodes are removed. This result indicates that there exists no redundancy in the anchor set. The decease is faster when more nodes are removed, but the average ASR is still quite high even when removing half of the nodes. This finding is another evidence that supports the trade-off between anchor set size and ASR, in addition to the prior Table 2.

Speeding up training through sampling. The cost of finding the anchors is O(n · |VL| · max epoch), because in each epoch the attack vector p is kept being updated through iterating |VL| training nodes. For a given graph with fixed n, we are interested in seeing whether reducing the training set size affects the attack performance. We randomly sample a portion of the training set in each epoch and report in Table 4 the resulting ASR. One sees that the ASR barely changes by using 40% of the data to train each epoch. Further reducing the size starts to hurt, but even using 5% of the training data, the ASR drops by only 5% to 13%. Moreover, GUA is efficient compared to the state-of-art attack method Nettack [Z¨ugner et al., 2018], whose complexity is O(n2 · (E · T +F)) to attack all nodes, where E and F represent the number of edge and feature perturbations, respectively, and T is the average size of a 2-hop neighborhood. In practice, Nettack is slower to run, due to the n2 factor.

Transferability. We have already seen that GUA is quite effective in attacking GCN. Such an attack belongs to the white-box family, because knowledge of the model to be attacked is assumed. In reality, however, the model parameters may not be known at all, not even the model form. Attacks under this scenario is called black-box. One approach to conducting black-box attack is to use a surrogate model. In our case, if one is interested in attacking graph deep learning models other than GCN, GCN may serve as the surrogate. The important question is whether anchors found by attacking the surrogate can effectively attack other models as well. We perform an experiment with three such models: DeepWalk [Perozzi et al., 2014], node2vec [Grover and Leskovec, 2016], and GAT [Veliˇckovi´c et al., 2017]. The first two compute, in an unsupervised manner, node embeddings that are used for downstream classification, whereas the last one is a graph neural network that directly performs classification. In Table 5, we list the ASR for these models. One sees that the ASRs are similarly high as that for GCN; sometimes even surpassing. Specifically, GAT is developed based on GCN through incorporating the attention mechanism, while Node2vec and DeepWalk update node embeddings by exploring the local structure via random walk. Since GUA modifies the neighborhood of the target, it is reasonable that all the other methods can also be misled efficiently. This finding concludes that the results of GUA are well transferable.

5 RelatedWork

Since the seminal work by [Szegedy et al., 2014], various types of methods have been proposed to generate adversarial examples. For instance, [Goodfellow et al., 2014] introduce the fast gradient sign method and [Carlini and Wagner, 2017] develop a powerful attack through iterative optimization. This work is related to recent advances in adversarial attacks on GNNs and general universal attacks.

Adversarial attack onGNN. [Z¨ugner et al., 2018] propose Nettack that uses a greedy mechanism to attack the graph embedding model by changing the entry that maximizes the loss change. [Dai et al., 2018] introduce a reinforcement learning based method that modifies the graph structure and significantly lowers the test accuracy. [Wang et al., 2018] propose Greedy-GAN that poisons the training nodes through adding fake nodes indistinguishable by a discriminator. [Chen et al., 2018] recursively compute connection-based gradients and flip the connection value based on the maximum gradient. [Z¨ugner and G¨unnemann, 2019] attack the whole graph by tackling an optimization problem using meta learning.

Universal attacks. [Moosavi-Dezfooli et al., 2017] train a quasi-imperceptible universal perturbation that successfully attacks most of the images in the same dataset. [Brown et al., 2017] generate a small universal patch to misclassify any image. [Wu and Fu, 2019] search for a universal perturbation that can be well transferred to several models.

6 Conclusion

In this work, we consider universal adversarial attacks on graphs and propose the first algorithm, named GUA, to effectively conduct these attacks. GUA finds a set of anchor nodes to mislead the classification of all nodes in the graph through flipping the connections between the anchors and the target node. GUA achieves the highest ASR compared to several universal attack baselines. The training process can be accelerated through sampling the training set in each epoch. There exists a trade-off between ASR and the anchor set size and we find that a very small size is sufficient to achieve remarkable attack success. Additionally, we find that the computed anchor nodes often belong to the same class. We also find that the anchor nodes used to attack one model equally well attack other models. In the future, we plan to develop defense mechanisms to effectively counter these attacks.

Acknowledgements

J. Chen is supported in part by DOE Award DE-OE0000910.