Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective

1 Introduction

Graph structured data plays a crucial role in many AI applications. It is an important and versatile representation to model a wide variety of datasets from many domains, such as molecules, social networks, or interlinked documents with citations. Graph neural networks (GNNs) on graph structured data have shown outstanding results in various applications [Kipf and Welling, 2016; Veliˇckovi´c et al., 2017; Xu et al., 2019a]. However, despite the great success on inferring from graph data, the inherent challenge of lacking adversarial robustness in deep learning models still carries over to security-related domains such as blockchain or communication networks.

In this paper, we aim to evaluate the robustness of GNNs from a perspective of first-order optimization adversarial attacks. It is worth mentioning that first-order methods have achieved great success for generating adversarial attacks on audios or images [Carlini and Wagner, 2018; Xu et al., 2019b; Chen et al., 2018b; Xu et al., 2019c; Chen et al., 2018a]. However, some recent works [Dai et al., 2018; Bojcheski and G¨unnemann, 2018] suggested that conventional (first-order) continuous optimization methods do not directly apply to attacks using edge manipulations (we call topology attack) due to the discrete nature of graphs. We close this gap by studying the problem of generating topology attacks via convex relaxation so that gradient-based adversarial attacks become plausible for GNNs. Benchmarking on node classification tasks using GNNs, our gradient-based topology attacks outperform current state-of-the-art attacks subject to the same topology perturbation budget. This demonstrates the effectiveness of our attack generation method through the lens of convex relaxation and first-order optimization. Moreover, by leveraging our proposed gradient-based attack, we propose the first optimization-based adversarial training technique for GNNs, yielding significantly improved robustness against gradientbased and greedy topology attacks.

∗Equal contribution

Our new attack generation and adversarial training methods for GNNs are built upon the theoretical foundation of spectral graph theory, first-order optimization, and robust (mini-max) optimization. We summarize our main contributions as follows:

• We propose a general first-order attack generation framework under two attacking scenarios: a) attacking a pre-defined GNN and b) attacking a re-trainable GNN. This yields two new topology attacks: projected gradient descent (PGD) topology attack and min-max topology attack. Experimental results show that the proposed attacks outperform current state-of-the-art attacks.
• With the aid of our first-order attack generation methods, we propose an adversarial training method for GNNs to improve their robustness. The effectiveness of our method is shown by the considerable improvement of robustness on GNNs against both optimization-based and greedy-search-based topology attacks.

2 RelatedWorks

Some recent attentions have been paid to the robustness of graph neural network. Both [Z¨ugner et al., 2018] and [Dai et al., 2018] studied adversarial attacks on neural networks for graph data. [Dai et al., 2018] studied test-time non-targeted adversarial attacks on both graph classification and node classification. Their work restricted the attacks to perform modifications on discrete structures, that is, an attacker is only allowed to add or delete edges from a graph to construct a new graph. White-box, practical black-box and restricted blackbox graph adversarial attack scenarios were studied. Authors in [Z¨ugner et al., 2018] considered both test-time (evasion) and training-time (data poisoning) attacks on node classification task. In contrast to [Dai et al., 2018], besides adding or removing edges in the graph, attackers in [Z¨ugner et al., 2018] may modify node attributes. They designed adversarial attacks based on a static surrogate model and evaluated their impact by training a classifier on the data modified by the attack. The resulting attack algorithm is for targeted attacks on single nodes. It was shown that small perturbations on the graph structure and node features are able to achieve misclassification of a target node. A data poisoning attack on unsupervised node representation learning, or node embeddings, has been proposed in [Bojcheski and G¨unnemann, 2018]. This attack is based on perturbation theory to maximize the loss obtained from DeepWalk [Perozzi et al., 2014]. In [Z¨ugner and G¨unnemann, 2019], training-time attacks on GNNs were also investigated for node classification by perturbing the graph structure. The authors solved a min-max problem in training-time attacks using meta-gradients and treated the graph topology as a hyper-parameter to optimize.

3 Problem Statement

We begin by providing preliminaries on GNNs. We then formalize the attack threat model of GNNs in terms of edge perturbations, which we refer as 'topology attack'.

3.1 Preliminaries on GNNs

It has been recently shown in [Kipf and Welling, 2016; Veliˇckovi´c et al., 2017; Xu et al., 2019a] that GNN is powerful in transductive learning, e.g., node classification under graph data. That is, given a single network topology with node features and a known subset of node labels, GNNs are efficient to infer the classes of unlabeled nodes. Prior to defining GNN, we first introduce the following graph notations. Let G = (V, E) denote an undirected and unweighted graph, where V is the vertex (or node) set with cardinality |V| = N, and E ∈ (V × V) denotes the edge set with cardinality |E| = M. Let A represent a binary adjancency matrix. By definition, we have Aij = 0 if (i, j) /∈ E. In a GNN, we assume that each node i is associated with a feature vector xi ∈ RM0 and a scalar label yi. The goal of GNN is to predict the class of an unlabeled node under the graph topology A and the training data {(xi, yi)}Ntrain i=1 . Here GNN uses input features of all nodes but only Ntrain < N nodes with labeled classes in the training phase.

Formally, the kth layer of a GNN model obeys the propagation rule of the generic form

where h(k) i ∈ RMk denotes the feature vector of node i at layer k, h(0) i = xi ∈ RM0 is the input feature vector of node i, g(k) is a possible composite mapping (activation) function, W(k-1) ∈ RMk×Mk-1 is the trainable weight matrix at layer (k - 1), ˜ Aij is the (i, j)th entry of ˜A that denotes a linear mapping of A but with the same sparsity pattern, and N(i) denotes node i's neighbors together with itself, i.e., N(i) = {j|(i, j) ∈ E, or j = i}.

A special form of GNN is graph convolutional networks (GCN) [Kipf and Welling, 2016]. This is a recent approach of learning on graph structures using convolution operations which is promising as an embedding methodology. In GCNs, the propagation rule (1) becomes [Kipf and Welling, 2016]

where σ(·) is the ReLU function. Let ˜ Ai,: denote the ith row of ˜A and H(k) = [(h(k) 1 )⊤; . . . ; (h(k) N )⊤], we then have the standard form of GCN,

Here ˜A is given by a normalized adjacency matrix ˜A = ˆD-1/2 ˆAˆD-1/2 , where ˆA = A+ I, and ˆDij = 0 if i ̸= j and ˆDii = 1⊤ ˆA:,i.

3.2 Topology Attack in Terms of Edge Perturbation

We introduce a Boolean symmetric matrix S ∈ {0, 1}N×N to encode whether or not an edge in G is modified. That is, the edge connecting nodes i and j is modified (added or removed) if and only if Sij = Sji = 1. Otherwise, Sij = 0 if i = j or the edge (i, j) is not perturbed. Given the adjacency matrix A, its supplement is given by ¯A = 11T - I -A, where I is an identity matrix, and (11T - I) corresponds to the fullyconnected graph. With the aid of edge perturbation matrix S and ¯A, a perturbed graph topology A′ against A is given by

where ◦ denotes the element-wise product. In (4), the positive entry of C denotes the edge that can be added to the graph A, and the negative entry of C denotes the edge that can be removed from A. We then formalize the concept of topology attack to GNNs: Finding minimum edge perturbations encoded by S in (4) to mislead GNNs. A more detailed attack formulation will be studied in the next section.

4 Topology Attack Generation: A First-Order Optimization Perspective

In this section, we first define attack loss (beyond the conventional cross-entropy loss) under different attacking scenarios. We then develop two efficient attack generation methods by leveraging first-order optimization. We call the resulting attacks projected gradient descent (PGD) topology attack and min-max topology attack, respectively.

4.1 Attack Loss &Attack Generation

Let Z(S,W;A, {xi}) denote the prediction probability of a GNN specified byA′ in (4) andWunder input features {xi}. Then Zi,c denotes the probability of assigning node i to class c. It has been shown in existing works [Goodfellow et al., 2015; Kurakin et al., 2017] that the negative cross-entropy (CE) loss between the true labels (yi) and the predicted labels ({Zi,c}) can be used as an attack loss at node i, denoted by fi(S,W;A, {xi}, yi). We can also propose a CW-type loss similar to Carlili-Wagner (CW) attacks for attacking image classifiers [Carlini andWagner, 2017],

where κ ≥ 0 is a confidence level of making wrong decisions. To design topology attack, we seek S in (4) to minimize the per-node attack loss (CE-type or CW-type) given a finite budge of edge perturbations. We consider two threat models: a) attacking a pre-defined GNN with known W; b) attacking an interactive GNN with re-trainable W. In the case a) of fixedW, the attack generation problem can be cast as

where we replace the symmetric matrix variable S with its vector form that consists of n := N(N - 1)/2 unique perturbation variables in S. We recall that fi could be either a CE-type or a CW-type per-node attack loss. In the case b) of re-trainableW, the attack generation problem has the following min-max form

where the inner maximization aims to constrain the attack loss by retraining W so that attacking GNN is more difficult.

Motivated by targeted adversarial attacks against image classifiers [Carlini and Wagner, 2017], we can define targeted topology attacks that are restricted to perturb edges of targeted nodes. In this case, we require to linearly constrain S in (4) as Si,· = 0 if i is not a target node. As a result, both attack formulations (6) and (7) have extra linear constraints with respect to s, which can be readily handled by the optimization solver introduced later. Without loss of generality, we focus on untargeted topology attacks in this paper.

4.2 PGD Topology Attack

Problem (6) is a combinatorial optimization problem due to the presence of Boolean variables. For ease of optimization, we relax s ∈ {0, 1}n to its convex hull s ∈ [0, 1]n and solve the resulting continuous optimization problem,

where S = {s | 1T s ≤ ϵ, s ∈ [0, 1]n }. Suppose that the solution of problem (8) is achievable, the remaining question is how to recover a binary solution from it. Since the variable s in (8) can be interpreted as a probabilistic vector, a randomization sampling [Liu et al., 2016] is suited for generating a near-optimal binary topology perturbation; see details in Algorithm 1.

Algorithm 1 Random sampling from probabilistic to binary topology perturbation

• 1: Input: probabilistic vector s, K is # of random trials
• 2: for k = 1, 2, . . . ,K do
• 3: draw binary vector u(k) following

• 4: end for
• 5: choose a vector s∗ from {u(k) } which yields the smallest attack loss f(u(k) ) under 1T s ≤ ϵ.

We solve the continuous optimization problem (8) by projected gradient descent (PGD),

where t denotes the iteration index of PGD, ηt > 0 is the learning rate at iteration t, ˆgt = ∇f(s(t-1) ) denotes the gradient of the attack loss f evaluated at s(t-1) , and ΠS(a) := argmins∈S ‖s - a‖22 is the projection operator at a over the constraint set S. In Proposition 1, we show that the projection operation yields the closed-form solution.

Proposition 1 Given S = {s | 1T s ≤ ϵ, s ∈ [0, 1]n }, the projection operation at the point a with respect to S is

where P[0,1](x) = x if x ∈ [0, 1], 0 if x < 0, and 1 if x > 1.

Proof: We express the projection problem as

where I[0,1](s) = 0 if s ∈ [0, 1]n , and ∞ otherwise.

The Lagrangian function of problem (12) is given by

where µ ≥ 0 is the dual variable. The minimizer to the above Lagrangian function (with respect to the variable s) is

where P[0,1] is taken elementwise. Besides the stationary condition (14), other KKT conditions for solving problem (12) are

If µ > 0, then the solution to problem (12) is given by (14), where the dual variable µ is determined by (14) and (15)

If µ = 0, then the solution to problem (12) is given by (14) and (17),

The proof is complete.

□

In the projection operation (11), one might need to solve the scalar equation 1T P[0,1][a - µ1] = ϵ with respect to the dual variable µ. This can be accomplished by applying the bisection method [Boyd and Vandenberghe, 2004; Liu et al., 2015] over µ ∈ [min(a - 1),max(a)]. That is because 1T P[0,1][a - max(a)1] ≤ ϵ and 1T P[0,1][a - min(a - 1)1] ≥ ϵ, where max and min return the largest and smallest entry of a vector. We remark that the bisection method converges in the logarithmic rate given by log2 [(max(a) -min(a-1))/ξ] for the solution of ξ-error tolerance. We summarize the PGD topology attack in Algorithm 2.

Algorithm 2 PGD topology attack on GNN

• 1: Input: s(0) , ϵ > 0, learning rate ηt, and iterations T
• 2: for t = 1, 2, . . . , T do
• 3: gradient descent: a(t) = s(t-1) - ηt∇f(s(t-1) )
• 4: call projection operation in (11)
• 5: end for
• 6: call Algorithm1 to return s∗ , and the resulting A′ in (4).

4.3 Min-max Topology Attack

We next solve the problem of min-max attack generation in (7). By convex relaxation on the Boolean variables, we obtain the following continuous optimization problem

where S has been defined in (8). We solve problem (20) by first-order alternating optimization [Lu et al., 2019a; 2019b], where the inner maximization is solved by gradient ascent, and the outer minimization is handled by PGD same as (10). We summarize the min-max topology attack in Algorithm3. We remark that one can perform multiple maximization steps within each iteration of alternating optimization. This strikes a balance between the computation efficiency and the convergence accuracy [Chen et al., 2017; Qian et al., 2018].

5 Robust Training for GNNs

With the aid of first-order attack generation methods, we now introduce our adversarial training for GNNs via robust optimization. Similar formulation is also used in [Madry et al., 2017]. In adversarial training, we solve a min-max problem for robust optimization:

where f(x,W) denotes the attack loss specified in (20). Following the idea of adversarial training for image classifiers in [Madry et al., 2017], we restrict the loss function f as the CE-type loss. This formulation tries to minimize the training loss at the presence of topology perturbations.

Algorithm 3 Min-max topology attack to solve (20)

• 1: Input: given W(0) , s(0) , learning rates βt and ηt, and iteration numbers T
• 2: for t = 1, 2, . . . , T do
• 3: inner maximization over W: given s(t-1) , obtain

• 4: outer minimization over s: given W(t) , running PGD (10), where ˆgt = ∇sf(st-1 ,Wt )
• 5: end for
• 6: call Algorithm1 to return s∗ , and the resulting A′ in (4).

We note that problems (21) and (7) share a very similar min-max form, however, they are not equivalent since the loss f is neither convex with respect to s nor concave with respect toW, namely, lacking saddle point property [Boyd and Vandenberghe, 2004]. However, there exists connection between (7) and (21); see Proposition 2.

Proposition 2 Given a general attack loss function f, problem (21) is equivalent to

which further yields (22) ≤ (7).

Proof: By introducing epigraph variable p [Boyd and Vandenberghe, 2004], problem (21) can be rewritten as

By changing variable q := -p, problem (23) is equivalent to

By eliminating the epigraph variable q, problem (24) becomes (22). By max-min inequality [Boyd and Vandenberghe, 2004, Sec. 5.4], we finally obtain that

We summarize the robust training algorithm in Algorithm 4 for solving problem (22). Similar to Algorithm3, one usually performs multiple inner minimization steps (with respect to s) within each iteration t to have a solution towards minimizer during alternating optimization. This improves the stability of convergence in practice [Qian et al., 2018; Madry et al., 2017].

6 Experiments

In this section, we present our experimental results for both topology attack and defense methods on a graph convolutional networks (GCN) [Kipf and Welling, 2016]. We demonstrate the misclassification rate and the convergence of the proposed 4 attack methods: negative cross-entropy loss via PGD attack (CE-PGD), CW loss via PGD attack (CW-PGD), negative cross-entropy loss via min-max attack (CE-minmax), CW loss via min-max attack (CW-min-max). We then show the improved robustness of GCN by leveraging our proposed robust training against topology attacks.

Algorithm 4 Robust training for solving problem (22)

• 1: Input: given W(0) , s(0) , learning rates βt and ηt, and iteration numbers T
• 2: for t = 1, 2, . . . , T do
• 3: inner minimization over s: given W(t-1) , running PGD (10), where ˆgt = ∇sf(st-1 ,Wt-1 )
• 4: outer maximization overW: given s(t) , obtain

• 5: end for
• 6: returnWT .

6.1 Experimental Setup

We evaluate our methods on two well-known datasets: Cora and Citeseer [Sen et al., 2008]. Both datasets contain unweighted edges which can be generated as symmetric adjacency matrix A and sparse bag-of-words feature vectors which can be treated the input of GCN. To train the model, all node feature vectors are fed into GCN but with only 140 and 120 labeled nodes for Cora and Citeseer, respectively. The number of test labeled nodes is 1000 for both datasets. At each experiment, we repeat 5 times based on different splits of training/testing nodes and report mean ± standard deviation of misclassification rate (namely, 1 - prediction accuracy) on testing nodes. Source code avaliable at https://github.com/KaidiXu/GCN_ADV_Train

6.2 Attack Performance

We compare our four attack methods (CE-PGD, CW-PGD, CE-min-max, CW-min-max) with DICE ('delete edges internally, connect externally') [Waniek et al., 2018], MetaSelf attack [Z¨ugner and G¨unnemann, 2019] and greedy attack, a variant of Meta-Self attack without weight re-training for GCN. The greedy attack is considered as a fair comparison with our CE-PGD and CW-PGD attacks, which are generated on a fixed GCN without weight re-training. In minmax attacks (CE-min-max and CW-min-max), we show misclassification rates against both natural and retrained models from Algorithm3, and compare them with the state-of-theart Meta-Self attack. For a fair comparison, we use the same performance evaluation criterion in Meta-Self, testing nodes' predicted labels (not their ground-truth label) by an independent pre-trained model that can be used during the attack. In the attack problems (6) and (7), unless specified otherwise the maximum number of perturbed edges is set to be 5% of the total number of existing edges in the original graph. In Algorithm 1, we set the iteration number of random sampling as K = 20 and choose the perturbed topology with the highest misclassification rate which also satisfies the edge perturbation constraint.

In Table 1, we present the misclassification rate of different attack methods against both natural and retrained model from (20). Here we recall that the retrained model arises due to the scenario of attacking an interactive GCN with re-trainable weights (Algorithm3). For comparison, we also show the misclassification rate of a natural model with the true topology (denoted by 'clean'). As we can see, to attack the natural model, our proposed attacks achieve better misclassification rate than the existing methods. We also observe that compared to min-max attacks (CE-min-max and CW-min-max), CE-PGD and CW-PGD yield better attacking performance since it is easier to attack a pre-defined GCN. To attack the model that allows retraining, we set 20 steps of inner maximization per iteration of Algorithm3. The results show that our proposed min-max attack achieves very competitive performance compared to Meta-Self attack. Note that evaluating the attack performance on the retrained model obtained from (20) is not quite fair since the retrained weights could be suboptimal and induce degradation in classification.

In Fig. 1, we present the CE-loss and the CW-loss of the proposed topology attacks against the number of iterations in Algorithm 2. Here we choose T = 200 and ηt = 200/√t. As we can see, the method of PGD converges gracefully against iterations. This verifies the effectiveness of the first-order optimization based attack generation method.

6.3 Defense Performance

In what follows, we invoke Algorithm4 to generate robust GCN via adversarial training. We set T = 1000, βt = 0.01 and ηt = 200/√t. We run 20 steps for inner minimization. Inspired by [Madry et al., 2017], we increase the hidden units from 16 to 32 in order to create more capacity for this more complicated classifier. Initially, we set the maximum number of edges we can modify as 5% of total existing edges.

In Figure 2, we present convergence of our robust training. As we can see, the loss drops reasonably and the 1, 000 iterations are necessary for robust training rather than normal training process which only need 200 iterations. We also observe that our robust training algorithm does not harm the test accuracy when ϵ = 5%, but successfully improves the robustness as the attack success rate drops from 28.0% to 22.0% in Cora dataset as shown in Table 2,

After showing the effectiveness of our algorithm, we explore deeper in adversarial training on GCN. We aim to show how large ϵ we can use in robust training. So we set ϵ from 5% to 20% and apply CE-PGD attack following the same ϵ setting. The results are presented in Table 3. Note that when ϵ = 0, the first row shows misclassification rates of test nodes on natural graph as the baseline for lowest misclassification rate we can obtain; the first column shows the CE-PGD attack misclassification rates of natural model as the baseline for highest misclassification rate we can obtain. We can conclude that when a robust model trained under an ϵ constraint, the model will gain robustness under this ϵ distinctly. Considering its importance to keep the original graph test performance, we suggest generating robust model under ϵ = 0.1. Moreover, please refer to Figure 3 that a) our robust trained model can provide universal defense to CE-PGD, CW-PGD and Greedy attacks; b) when increasing ϵ, the difference between both test accuracy and CE-PGD attack accuracy increases substantially, which also implies the robust model under larger ϵ is harder to obtain.

7 Conclusion

In this paper, we first introduce an edge perturbation based topology attack framework that overcomes the difficulty of attacking discrete graph structure data from a first-order optimization perspective. Our extensive experiments show that with only a fraction of edges changed, we are able to compromise state-of-the-art graph neural networks model noticeably. Additionally, we propose an adversarial training framework to improve the robustness of GNN models based on our attack methods. Experiments on different datasets show that our method is able to improve the GNN model's robustness against both gradient based and greedy search based attack methods without classification performance drop on original graph. We believe that this paper provides potential means for theoretical study and improvement of the robustness of deep learning models on graph data.

Acknowledgments

This work is supported by Air Force Research Laboratory FA8750-18-2-0058 and the MIT-IBM Watson AI Lab.