Attacking Graph Convolutional Networks via Rewiring
Authors: Yao Ma
Suhang Wang
Tyler Derr
Lingfei Wu
Jiliang Tang
Venue:  (2020)
Keywords: Graph Neural Networks
Rewiring
Adversarial Attacks

Abstract: Graph Neural Networks (GNNs) have boosted the performance of many graph related tasks such as node classification and graph classification. Recent researches show that graph neural networks are vulnerable to adversarial attacks, which deliberately add carefully created unnoticeable perturbation to the graph structure. The perturbation is usually created by adding/deleting a few edges, which might be noticeable even when the number of edges modified is small. In this paper, we propose a graph rewiring operation which affects the graph in a less noticeable way compared to adding/deleting edges. We then use reinforcement learning to learn the attack strategy based on the proposed rewiring operation. Experiments on real world graphs demonstrate the effectiveness of the proposed framework. To understand the proposed framework, we further analyze how its generated perturbation to the graph structure affects the output of the target model.

Under review as a conference paper at ICLR 2020
ATTACKING GRAPH CONVOLUTIONAL NETWORKS VIA REWIRING
Anonymous authors Paper under double-blind review
ABSTRACT
Graph Neural Networks (GNNs) have boosted the performance of many graph re- lated tasks such as node classification and graph classification. Recent researches show that graph neural networks are vulnerable to adversarial attacks, which de- liberately add carefully created unnoticeable perturbation to the graph structure. The perturbation is usually created by adding/deleting a few edges, which might be noticeable even when the number of edges modified is small. In this paper, we propose a graph rewiring operation which affects the graph in less noticeable way compared to existing operators. We then use reinforcement learning to learn the attack strategy based on the proposed rewiring operation. Experiments real world graphs demonstrate the effectiveness of the proposed framework. To under- stand the proposed framework, further analyze how its generated perturbation to the graph structure affects the output of the target model and the advantages of the rewiring operation.
INTRODUCTION
Graph structured data ubiquitous in many real world applications. Various data from different domains, such as social networks, molecular graphs and transportation networks can all be modeled as graphs. Recently, increasing effort has been devoted towards developing deep neural networks on graph structured data. This stream of works, which is known Graph Neural Networks (GNN) has shown to enhance the performance many graph related tasks such as node classification (Kipf & Welling 2016 Hamilton et al. (017)) and graph classification (Bruna et al., 2013 Defferrard et al.) 2016 Ying et al. 2018 /hang et al. 2018).
Recent researches have shown that deep neural networks are highly vulnerable to adversarial at- tacks (Szegedy et al.) 2013), Goodfellow al. [0144] Kurakin et al. |2016) Carlini Wagner (207)). In computer vision, performing an adversarial attack is to add deliberately created, but unnoticeable, perturbation to given image such that the deep model misclassifies the perturbed image. Unlike image data, which can be represented in the continuous space, graph structured data is discrete. Few efforts have been made to investigate the robustness of graph neural networks against adver- sarial attacks. Only recently, such researches about adversarial attacks graph structured data started to emerge. Á greedy algorithm is proposed to attack the semi-supervised node classification task (üügner al.) 20188). The method deliberately tries to modif' the graph structure and node features such that the label of targeted node can be changed. A reinforcement learning based algo- rithm is proposed to attack both node classification and graph classification task by only modifying the graph structure et al. 2018). A meta- mneaa-leaming based attack method is designed to impair the overall performance of the node classification task (Zggnr & Günnemann 2019). For the majority of existing works, the graph structure is modified by adding or deleting edges.
To ensure that the difference between the attacked graph and the original graph is "unnoticeable"; the number of actions (adding/deleting edges) that can be taken by the attacking algorithms is usually constrained by a budget. However, even when this budget is small, adding or deleting edges can still make "noticeable" changes to the graph structure (Miller al. 2019). For example, it is evident that many important graph properties are based on eigenvalues and eigenvectors of the Laplacian matrix of the graph (Chan & Akoglu 2016); while adding or deleting an edge can make remarkable changes on the eigenvalues/eigeevectoo of the graph Laplacian (Ghosh & Boyd (006). Thus, in this work, we propose new operation based graph rewiring. A single rewiring operation involves

---

Under review as a conference paper at ICLR 2020
three nodes (Ufir, Usec: Uttx), where remove the existing edge between ffrrr and Usec and add edge between Vfir and Vthi- Note that Vius is constraint to be the 2-hop neighbor of far in our setting. It is obvious that the proposed rewiring operation preserves some basic properties of the graph such as number of nodes and edges, total degrees of the graph and etc, while operations like adding and deleting edges cannot. Furthermore, the proposed rewiring operation affects some of the important measures based on graph Laplacian such as algebraic connectivity in smaller way than adding/deleting edges, which is theoretically demonstrated in Section 1. In addition, the rewiring operation is a more natural way to modify the graph. For example, in biology, the evolution of DNA and amino acid sequences can lead pervasive rewiring of protein-protedd interactions (Zitnik et al., 2019).
In this paper, we aim construct adversarial examples by performing rewiring operations for the task of graph classification. More specifically, we treat the process of applying series of rewiring operations to given graph as a discrete Markov decision process (MDP) and use reinforcement learning to learn how to make these decisions. We demonstrate the effectiveness of the proposed algorithm on real-world graphs. Then we further analyze how the adversarial changes in the graph structure affect both the graph embedding learned by the graph neural network model and the output label and illustrate the advantages of the rewiring operation.
BACKGROUND
In this section, introduce notations and the target graph convolutional model we seek to attack. We denote a graph as G = {V.E), where V = {UI..... tlyl and & of nodes and edges, respectively. The edges describe the relations between nodes, which can be described by an adjacency matrix A {0, || Au otherwise. Each node in the graph has some features that are associated with it. These features are represented as a matrix X E [V where the i-th row of X denotes the node features of node U; and d is the dimension of features. Thus, attributed graph can be represented as G (A,
are the sets
means U, and Vj are connected,
2.1 GRAPH CLASSIFICATION
In the setting of graph classification, we are given a set of graphs G = [.... Each of these graphs G2 is associated with label y/. The task is build good classifier using the given set of graphs such that it can make correct predictions when new unseen graphs are fed into it. A graph classifier parameterized by & can be represented as f(Gl@)
y", where y denotes the label of a graph G' E 9 predicted by the classifier. The parameters @ in the classifier f((]0) can be learned by solving the following optimization problem ming Σ, T((((, v.), where .(..)) used to measure the difference between the predicted and ground truth labels. Cross entropy is commonly adopted measurement for ....).
2.2 GRAPH CONVOLUTION NETWORKS
Recently, Graph Neural Networks have been shown to be effective in graph representation learning. These models usually learn node representations by iteratively aggregating, transforming and prop- agating node information. In this work, we adopt the graph convolutional networks (GCN) (Kipf & Welling 2016). A graph convolutional layer the GCN framework can be represented as
AD F RDLU AD F
where FV E Nxd, is the output of the j-th layer and W represents the parameters of this layer. A GCN model usually consists of J graph convolutional layers, with FD = X. The output of the GCN model is F', which is denote as F for convenience. To obtain a graph level embedding ug for graph to perform graph classification, we apply a global pooling over the node embeddings.
UG = (F)
Different global pooling functions be used, and adopt the pooling in this work. A mul- tilayer perceptron (MLP) and softmax layer are then sequentially applied on the graph embedding predict the label of the graph
8" argmax softmaz(M WMLP))
(3)
2

---

As described above, the attacker T is specifically designed for a given classifier f(-). To reflect this in the notation, now denote the attacker for the classifier f() as Ty. f. In our work, the attacker Ty has limited knowledge of the classifier. The only information the attacker can get from the classifier Under review as a conference paper at ICLR 2020
where MLP(-|W MLP) denotes the multilayer perceptron with parameters W WLLP. A GCN- based classifier for graph classification can be described using eq. equation I equation 2 and equa- tion 3 as introduced above. For simplicity, summarize it as y" facN (G where 8GNN includes all the parameters in the model.
3 PROBLEM FORMULATION
In this work, we aim to build am attacker T that takes a graph as imput and modify the structure of the graph fool a GCN classifier. Modifying graph structure is equivalent to modify its adjacency matrix. The function of the attacker Given a classifier f(-). the goal of the attacker is to modify the graph structure so that the classifier outputs different label from what originally predicted. Note here, we neglect the 0 inside ʃ(),, as the classifier is already trained and fixed. Mathematically, the goal of the attacker can be represented as: f(T(G) # f(G).
be represented as G T(G) (T(A), X] = {A, X)
the label of (modified) graphs. In other words, the classifier f(-) is treated as a black-box model for the attacker T
important constraint the attacker Ty is that only allowed to make "unnoticeble" changes to the graph structure. To account for this, we propose the rewiring operation, which is supposed to make more subtle changes than adding or deleting edges. We will show that the rewiring operation can better preserve lot of important properties of the graph compared to adding or deleting edges Section 4.1 We also empirically compare the rewiring operation with the deleting/adding edges in Appendix C. The definition of the proposed rewiring given below:
Definition 1. A rewiring operation a involves three nodes and it can be denoted as (urs Usec: V.ks), where Usec N (Ufar) and Uthi (N (ani/NNNoooor (vfor). N* denotes the k-th hop neighbors of für and the sign stands for exclusion. The rewiring operation deletes the existing edge between nodes Ufir and Users while adding an edge to connect nodes ffr and Uthi-
The attacker T is given a budget of K proposed rewiring operations to modify the graph structure. A straightforward way to set K is choosing a small fix number. However, likely that graphs affect
in given data set have various graph sizes. The same number of rewiring operations flexible the graphs of different size in various magnitude. Hence, more suitable way is to allow number rewiring operations according to the graph size. Thus, we propose use K p- a given graph G, where E (0, 1) is ratio.
[8] for
The process of the attacker on a graph G can be now denoted T₁(G) (01, .., aM (G]. where the right hand part means to sequentially apply the rewiring operations C1...., aM to the graph G, and M the number of rewiring operations taken with M < K.
REWIRING-BASSE ATTACK TO GRAPH CONVOLUTIONAL NETWORKS
Next, we first discuss the properties of the proposed rewiring operation show its advantages. We then introduce the proposed attacking framework ReWatt based on reinforcement learning and rewiring.
4.1 PROPERTIES OF THE PROPOSED REWIRING OPERATION
The proposed rewiring operation has several advantages compared to simply adding deleting edges. More empirical discussions can be found in Appendix C. One obvious advantage of the proposed rewiring operation is that it does not change the number of nodes, the number of edges and the total degree of a graph. However, operations like "adding" or "deleting" edges may change those properties.
Many important graph properties are based on the eigenvalues of the Laplacian matrix of a graph (Chan & Akoglu 2016) such as Algebraic Connectivity FFedler (1973) and Effective Graph
3

---

Under review as a conference paper at ICLR 2020
Resistance Ellens et al. (2011). A detailed description of Algebraic Connectivity and Effective Graph Resistance are given in Appendix A. Next, we demonstrate that the proposed rewiring oper- ation is likely to make smaller changes to eigenvalues, which result in unnoticeable changes under graph Laplacian based measures. For a graph G with A as its adjacency matrix, its Laplacian ma- trix L is defined as L D A, where D is the diagonal degree matrix (Mohar al., [191]. Let A,,..., laly denote the eigenvalues of the Laplacian matrix arranged in the increasing order with x1,....
X|yl being the corresponding eigenvectors. We show how single proposed rewiring operation affects the eigenvalues. Our analysis is based on the following lemma:
Let (a,, h2) be the eigen-pairs of a symmetric matrix M E RNNN Given a perturbation AM to matrix M, its eigenvalues can be updated by Aa; = h? AMh;
Lemma 1. Stewarr 1990)
The proof can be found in (Stewart 1990). Using this lemma, we have the following corollary
Corollary 1. For a given graph G with Laplacian matrix L, one proposed rewiring operation (Ufers Ueerr Vehi) affects the eigen-value de by Ad2 for I...., .V). where
A (2x:[fir] x((lii] x, (xxcc) xi(lvi))
where x, [[index] denotes the -nder-th value of the eigenvector x,,
The proof can be found in Appendix B.
Furthermore, each eigenvalue X of the Laplacian matrix measures the "smoothness" of its corre- sponding cigenvector x; (Shuman et al., 2012, Sandryhaila & Moura 2014). The "smoothness" of an eigenvector measures how different its elements are from their neighboring nodes. Thus, the first few eigenvectors with relatively small eigenvalues are rather "smooth". Note that in the proposed rewiring operation, Usec is the direct neighbor of fûrr and Uthi is the 2-hop neighbor of Ufir- Thus, where
(fffrr]xx(ccmu x; <[caa] can be any other node that is further away. This means that the proposed rewiring operation (to 2-hop neighbors) is likely to make smaller changes to the first few eigenvalues than rewiring to any further away nodes or adding an edge between two nodes that are far away from each other.
the difference x: x.[ffr]- x. [thi] is expected to be smaller than the difference
4.2 GRAPHI ADVERSARIAL ATTACK WITH REINFOR LEARNING
Given graph G. the process of the attacker T is general decision making process M (S. A, P. R), where A {at} is the set of actions, which consists of all valid rewiring opera- tions, S = {8x. ) is the set of states that consists of all possible intermediate and final graphs after rewiring, P is the transition dynamics that describes how a rewiring action ag changes the graph structure p(s141),3t, St, $1, at). R is the reward function, which gives the reward for the action taken at a given state. Thus, the procedure of attacking a graph can be described by a trajectory ($1, 01, 01,T1, .i,...,,,.............. 8M, aM, (M) where $1 = G. The key point for the attacker is to learn how to make the decision of picking a suitable rewiring action when at the state 8t. This can be done by learning policy network to get the probability p(a, ..,,...... 81) and sample the rewiring operation correspondingly. Modelling in this way, the decision making at a state 8, is dependant on all its previous states, which could be difficult model due to the long-term dependency. It is easy to notice that the intermediate states are all predicted to have the same label as the original graph. Thus, we can treat each of the states as brand new graph to be attacked regardless of what leads to it. That is to say, the decision making at the state 8, can be solely dependant on the current state, p(ar) St. .... 81) p(a: (s)). Thus, we model the process of attack as Markov Decision Process (MDP) /Sutton & Barto (0188). Hence, we adopt reinforcement learning to learn how to make effec- tive decisions. We name the proposed framework as ReWatt. The key elements of the environment for the reinforcement learning are defined as follows:
State Space The state space of the environment consists of all the intermediate graphs generated after the possible rewiring operations.
Action Space The action space consists of the valid rewiring operations as defined in Definition 1.
State Transition Dynamics Given an action (rewiring operation) or = {Uyirr Usee, Unke) at state St- The next state 8t-1 is achieved by deleting the edge between yfrr and Usec in the current state 8; and adding an edge to connect ffrr with Ushs.
Reward Design The main goal of the attacker is to make the classifier f(-) predict a different label than originally predicted. We also encourage the attacker to take as few actions as possible so that
4

---

Under review as a conference paper at ICLR 2020
the modification to the graph structure is minimal. Thus, we assign a positive reward when the attack is successful and assign a negative reward for each action step taken. The reward R(s;, at) is given
1 if f(t) f(s:): Pr if f(s)) f
R(st, (x) =
where n, is the negative reward to penalize each step taken. Similar to how we set a flexible rewiring budget K, here we propose use n4 K -ー12. which depends on the size of the graph.
Termination The attack process will stop either when the number of actions reaches the budget K or the attacker successfully "changed"" the label of the slightly modified graph.
4.3 POLICY NETWORK
In this subsection, we introduce the policy network to learn the policy p/a (st) on top of the graph representations learned by GCN. However, this GCN is different from the target classifier one, since it has 2 convectional layers. To choose a valid proposed rewiring action, we decompose the rewiring action to 3 steps: 1) choosing an edge 6 = (Ve, Veg) from the of edges of the intermediate graph s; 2) determining Ces,, or Beez to be ffrr, and the other to be Usecc and 3) choosing the third node Vehi, from N2, (Ufir,))Ng (u)ar,). Correspondingly, we decompose p(a, (8t) as follows
(5) We design three policy networks based on GCN to estimate the three distributions in the right hand of the equation equation [ which will be introduced next. To select edge from the edge set Es,, we generate the edge representation from the node representations F., E lxdde learned by GCN. For an edge e = (Vey Veg), the edge representation can represented as concat(u,, (us, h(F e. :l, [e2, =))), where Ue is the graph representation of the state St, -) is function to combine the two node representations and concat(: :) denotes the concatena- tion operation. We include Ust in the representation of the edge to incorporate the graph information when making the decision. The representation of all the edges in &,, can be represented as a matrix Eg, E R | 1x2d,, where each row represents an edge. The probability distribution over all the edges can be represented
p(ae(se)= = Podge (et(st) Pfar (Pfir, Ge, 8t) Pths (Ptni, |frir 8t)
(6) where M-Lde-ledge) to denote Multilayer Perceptron that maps E., E RR to
Pedge (.1s;) = softmar (ML
vector in RI which, after going through the softmax layer, represents the probability of choosing each edge. Let ez = (Wery Vei,) denote the edge sampled according to eq. equation 6 To decide which node is going to be the first node, we estimate the probability distribution over these two nodes as
Pfir(-le,,ss) 8t) softmax Ve.z)"1(0(r))
where Ves, = (o, F se.,, :)) E R3dr for = 1,2. The first node can be sampled from the two nodes Ver, Ve,, according to eq. equation ? We then proceed to estimate the prob- (Urr,,,,,,,,, ability distribution p(-lufär, Et, st). For any node Ue E (V3() (U(r)) concat(ve.,, F [c,::) represent it. The representations for all the nodes in N ( (Vfo.)) can be represented by matrix V., E (V (/NN (1zor, x with each row representing a node. The probability distribution of choosing the third node over all the candidate nodes be modeled as:
use ve
Puna--Uufir, Ct, 8t) = softmaz
(8)
The third node Vihi, can be sampled from the set of candidate nodes N2(vror) (/N accord-
ing to the probability distribution in eq equation 8 An action az can be generated by sequentially estimating and sampling from the probability distributions in eq. equation 6 equation 7 and equa-
tion g
4.4 PROPOSED FRAMEWORK REWATT
With the rewiring and the policy network defined above, our overall framework can be summarized follows. With State 8t, the Attacker uses GCN to learn node and edge embeddings, which
5

---

Under review as a conference paper at ICLR 2020
used as input to Policy Networks to make decision about the next action. Once the new action is sampled from the policy network, rewiring is performed on 8; and we arrive in the new state $141- We query the black-box classifier to get the prediction f(S++1), which is compared with f(1) to get reward. Policy gradient (Sutton & Barto 2018) is adopted to learn the policies by maximizing the rewards.
EXPERIMENT
In this section, we conduct experiments to evaluate the performance of the proposed framework Wetat.. We also carry out study to analyze how the trained attacker works. Some empirical investigation on the advancements of the rewiring operation can be found in Appendix C.
5.1 ATTACK PERFORMANCE
To demonstrate the effectiveness of Watt, we conduct experiments on three widely used social net- work data sets (Kersting et al. 2016) for graph classification, i.e.. REDDIT-MULTI-
REDDIT- MULTI-5K and MUDE-MULTI (Yanardag& & Vishwanathan 2015). The statisties can be found in Appendix D. Note that the re-wiring operation (as well as the other operations) may lead to abnor- mal structure of some kinds of graphs, which can make the graphs invalid, especially for chemical molecules. So in this paper, We avoid chemical related datasets but only use social networks datasets. In the social domain, if the changes are subtle, it is most likely that we will not we will not introduce abnormal structures. Meanwhile, it is straightforward to extend our framework to datsets from the other domains if we have expertise in them. For example, if we know what structures are abnormal, use such knowledge to constraint the the state space of the RL framework. We leave it as one future work.
In this work, the classifier we target to attack is the GCN-based classifier introduced in Section 2 We set the number of layers to 3. We need to train the classifier using a fraction of the data and then treat the classifier as black box to be attacked. We then use part of the remaining data train the attacker and use the rest of the data to test the performance of the attacker. Thus, for each data set, we split it into three parts with the ratio of a% : 5% : c%, where a% of the data set used train the classifier, 5% of the data set is used to train the attacker and the remaining e% of the data set is used test the performance of the attacker. For the REDDIT-MULTI- 12K and REDDIT-MULTI- 2. As the size of the IMDB-MULTI data set is quite
5K data sets, we set 90, b = 8 and small, to have enough data for testing, we set a = 50, b 30 and e = 20.
We compare the attacking performance of the proposed framework with the RL-S2V proposed in (Dai et al. 2018), random selection method and some variants of our proposed framework. We briefly describe these baselines: 1) RL-S2V is reinforcement learning based attack framework (Dai jet al. 2018), which allows adding and deleting edges to the graph with a fixed budget for all the graphs; 2) Random denotes attacker that performs the proposed rewiring operations randomly; 3) Random-s is also based on random rewiring. Note that Wett can terminate before using all the budget. We record the actual number of rewiring actions made in method and only allow the Random-s to take exactly the same number of rewiring actions as ReWatt; 4) Re Watt-n denotes a variant of the Retttt, where the negative reward is fixed to -0.5 for all the graphs in the testing set; and 5) Re Watt-a is a variant of ReWatt, where we allow any nodes in the graph to be the third node Vtbi, instead of only 2-hop neighbors.
As RL-S2V only allows a fixed budget for the all the graphs, when comparing to it, for Re we also fix the number of proposed rewiring operations fixed number K for all the graphs. Note that a single proposed rewiring operation involves two edges, thus, for a fair comparison, we allow the RL-S2V to take 2K actions (adding/deleting edges). We set K = 1, 2,3 in the experiments. To compare with the random selection method and the variants of Re Watt, specially, we allow at most p- |&, proposed rewiring operations for graph G.. Here, is a fixed percentage and set it to p- = 1%, 2%, 3% in our experiments. We use the success rate measure to evaluate the performance of the attacker. A graph is said to be successfully attacked its label is changed when it is modified within the given budget.
use flexible budget, more
The results are shown in Table [ Compared to RL-S2V, Wett perform more effective attacks. Especially, in the IMDB-MULTTI
From the table, we can make the following observations: 1)

---

Under review as a conference paper at ICLR 2020
REDDIT-MULTI-12K
REDDIT-MULTI-SK
IMDB-MULTI
K
2
3
2
3
Wett
14.4%
21.6%
23.4%
8.99%
16.9%
18.0%
23.0%
23.3%
23.3%
RL-S2V
9.46%
18.5%
21.1%
4.49%
16.9%
18.0%
2.00%
6.00%
3.33%
p
1%
2%
3%
1%
2%
3%
1%
2%
3%
ReWatt
25.2%
32.9%
38.7%
11.2%
20.2%
27.0%
23.0%
23.0%
23.3%
Re W
26.1%
35.1%
42.8%
5.60%
21.3%
30.3%
24.3%
25.0%
25.6%
ReWatt-n
17.6%
25.7%
31.1%
5.60%
14.6%
19.1%
21.3%
21.3%
21.6%
random 10.3%
15.7%
21.6%
3.30%
12.4%
16.9%
1.33%
1.33%
1.66%
random-s 6.30%
6.70%
9.45%
5.60%
6.74%
11.0%
1.00%
1.33%
1.66%
Table 1: Performance comparison in terms of success rate
data set, where Wata outperforms the RL-S2V with a large margin; 2) ReWatt outperforms the Random method expected. Especially, Weta is much more effective than Random-s which performs exactly the same number of proposed rewiring operations ReWatt. This also indicates that the Random method uses more rewiring operations for successful attacking than ReWatt; 3) The variant WeWatt- outperforms ReWatt, which means if we do not constraint the rewiring operation 2-hop neighbors, the performance of Weta can be further improved. However, as we discussed in earlier sections, this may lead to more "noticeable" changes of the graph structure; and 4) Re Watt- n performs worse than our Re Watt, which shows the advancement of using a flexible reward design.
5.2 ATTACKER ANALYSIS
In this subsection, carry experiments analyze how ReWatt's change in graph structure affects the graph representation u calculated by eq. equation and the logits P (the output immedi- ately after the softmax layer of the classifier). For convenience, we denote the original graph as Go and the attacked graph as G in this section. Correspondingly, the graph representation and logits for the original (attacked) graph are denoted as u (u²) and p (P*), respectively. To measure the difference in graph representation, we used the relative difference in terms of 2-norm defined as RC(uP, ; u ||n" inl=, The logits denote the probability distribution that the given graph belongs || each of the classes. Thus, we use the KL--divergence Kullback (1997) to measure the difference
between the logits of the original and attacked graphs K KL(PP, P*) Σ P log
where C
the number of classes in the data set and P denotes the logit for the i-th class.
We perform the experiments on the REDDIT-MULTI-I2K data set under the setting of allowing at most 3% [E] proposed rewiring operations. The results for the graph representation and logits are shown in Figure [ and Figure [ respectively. The graphs in the testing set are separated in two groups, one group contains all the graphs successfully attacked by ReWatt (shown Figure and Figure 2ab, and the other one contains those survived from ReWatt's 's attack (shown in Figure Tb and Figure 2bp. Note that, for comparison, we also include the results Random-s on these two groups of graphs. In these figures, single point represents testing graph, the x-axis is the ratio M M is the number of rewiring operations ReWatt used before the attacking process terminating. Note that M can be smaller than the budget as the process terminates once the attack successes.
[eT where
As we observe from the figures, compared with the Random-s, ReWatt can make more changes to both the graph representation and logits, using exactly the same number of proposed rewiring operations. Comparing Figure La with Figure Tb] we find that the perturbation generated by ReWatt affects the graph representation lot even when it fails to attack the graph. This means our attack is perturbing the graph structure in right way to fool the classifier, although it fails potentially due to the limited budget. Similar observation can be made when we compare Figure 2a with Figure 2b
6 RELATED WORK
In recent years, adversarial attacks deep learning models have attracted increasing attention in the area of computer vision. Many deep models are found to be easily fooled by adversarial sam- ples, which are generated by adding deliberately designed unnoticeable perturbation to normal im-
7

---

Under review as a conference paper at ICLR 2020
Ours
Durs
52-
61-
63
#actions@@edges
# Ll Aeddes
(a) Succeeded graphs
(b) Failed graphs
Figure I: The change graph representation after attack
Ours Random-s
Dur Random-
2.4
2.-
#actions@eddges
sct /
(a) Succeeded graphs
(b) Failed graphs
Figure 2: The change of logits after attack
ages (Szegedy al. 2013
Goodfellow al. 2014). More algorithms with different level access to the target classifier have been proposed, including white-bon box attack models, which have access
the gradients (Moosavi-Dezzoool et al.) 2016 Kurakin al. 2016 Carlini & Wagner 2017) and
black-box box attack model, which have limited access to the target classifier (Chen et al. 2017 Cheng yyas al. 2018).
al. 2018
Most of the aforementioned works are focusing in the computer vision domain, where the data sam- ple be represented in the continues space. Few attention has been payed into the discrete data structure such as graphs. Graph Neural Networks have been shown to bring impressive advance- ments many different graph related tasks such as node classification and graph elassification. Recent researches show that the graph neural networks are also venerable to adversarial attacks. (Zigner et al., 2018)) proposed a greedy algorithm to perform adversarial attack node classifi- cation task. Their algorithm tries change the label of target node by modifying both the graph structure and node features. (Dai et al. 2018) proposed a deep reinforcement learning based attacker to attack both the node classification and the graph classification task. (Zügner & Günnemann 2019) designed an algorithm to impair the overall performance of node classification based on meta learning All the three mentioned methods modify the graph structure by adding deleting edges. A more recent work WWang et al. (2018) on attacking node classifications proposed to modify the graph structure by adding fake nodes. In this work, we propose modify the graph structure using rewiring, which shown to make less noticeable changes to the graph structure.
CONCLUSION
In this paper, we proposed graph rewiring operation, which affect the graph structure a less noticeable way than adding/deleting edges. The rewiring operation preserves some basic graph properties such as number nodes and number edges. We then designed an attacker ReWatt based the rewiring operations using reinforcement learning. Experiments in 3 real world data sets show the effectiveness of the proposed framework. Analysis on how the graph representation and logits change while the graph being attacked provide with some insights of the attacker.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. arXiv preprint 1rXiv: 2013.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 39-57. IEEE, 2017.
Hau Chan and Leman Akoglu. Optimizing network robustness by edge rewiring: a general frame- work. Data Mining and Knowledge Discovery, 90(5):1395-1425 2016.
Pin-Yu Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. 7oo: Zeroth order opti- mization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop Artificial Intelligence and Security, pp. 15-26. ACM, 2017.
Minhao Cheng, Thong Le, Pin-Yu Chen, Jinfeng Yi, Huan Zhang, and Cho-Jui Hsieh. Query- efficient hard-label black-box attack: An opiimization-baset approach. arXiv preprint arXiv:1807.04455 2018.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. In International Conference Machine Learning, pp. 1123-1132, 2018.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances neural information processing systems, pp. 3844-3852, 2016.
Wendy Ellens, FM Spieksma, P Van Mieghem, A Jamakovic, and RE Kooij. Effective graph resis- tance. Linear algebra and its applications, 435(10):2491-2556 2011.
Miroslav Fiedler. Algebraic connectivity of graphs. Czechoslovak mathematical journal, 23(2): 298-305, 1973.
Arpita Ghosh and Stephen Boyd. Growing well-connected graphs. In Proceedings of the 45th IEEE Conference on Decision and Control, pp. 6605-6611. IEEE, 2006.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint 1rXiv:1412.6572. 2014.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034 1034, 2017.
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. arXiv preprint /xXiv:/80.008599 2018.
Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Bench- wtt.:lsss...t....moee.o. tu-dortmund, mark data sets for graph kernels, 2016. httlItttp///graabeeeelesss cs.
de
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 1609.02907, 2016.
Solomon Kullback. Information theory and statistics. Courier Corporation, 1997.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples in the physical world. arXiv preprint arXiv:1607.02533 2016.
Benjamin Miller, Mustafa Çamureu, Alexander J Gomez, Kevin Chan, and Tina Eliassi-Rad. Improving robustness to attacks against vertex classification. 2019.
Bojan Mohar, Y Alavi, G Chartrand, and OR Oellermann. The laplacian spectrum of graphs. Graph theory, combinatorics, and applications, (1871-898)122 1991.
Seyed-Mohsen Moosavi- Deaaaiii,..oo.i Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method to fool deep neural networks. In Proceedings of the IEEE conference on com- pufer vision and pattern recognition, pp. 2574-2582, 2016.

---

Under review as a conference paper at ICLR 2020
Aliaksei Sandryhaila and Jose Moura. Discrete signal processing graphs: Frequency analysis. IEEE Transactions on Signal Processing, 62(12):3042-3D00 2014.
David Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing graphs: Extending high-dimensional data analysis to net- works and other irregular domains, arXiv preprint arXiv:1211.0053. 2012.
Gilbert W Stewart. Matrix perturbation theory. 1990.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Ali Sydney, Caterina Scoglio, and Don Gruenbacher. Optimizing algebraic connectivity by edge rewiring. Applied Mathematics and computation, 219(10):54655-47) 2013.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 1xXi::3312.6199 2013.
Xiaoyun Wang, Joe Eaton, Cho-Jui Hsich, and Felix Wu. Attack graph convolutional networks by adding fake nodes. arXiv preprint arXiv:1810.1077 2018.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365-1374.
ACM, 2015.
Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L Hamilton, and Jure Leskovec. Hierarchical graph representation learning withdifferentiable pooling. arXiv preprint arXiv:1806.088 08804, 2018.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Thirty-Secone AAAI Conference on Artificial Intelligence, 2018.
Marinka Zitnik, Rok Sosič, Marcus W. Feldman, and Jure Leskovec. Evolution of resilience in protein interactomes across the tree of life. Proceedings of the National Academy of Sciences, 116(10):4426 4433, 2019. ISSN 0027-8424. doi: 10.1073/pnas. (aammas..111011111 1818013116, URL https:
// www. org/ http://oonnnntnn///neeeee
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2847-2856. ACM, 2018
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In International Conference on Learning Representations, 2019. URL https:// //
openreview net/ wtt/://rrumm///// 2idrmmmid-y111x20953
A GRAPH LAPLACIAN BASED MEASURES
Many important graph properties are based on the eigenvalues of the Laplacian matrix of graph (Chan & Akoglu 2016). Here we list few:
Algebraic Connectivity The algebraic connectivity of a graph G the second-smallest eigen- value of its Laplacian matrix (Fiedler 1973). Note that we only consider connected graphs in this work, so it always larger than The larger the algebraic connectivity is, the more difficult is to separate the graph into components (i.e., more edges need to be removed). The algebraic connectivity has previously been applied to measure network robustness (Sydney et al.] (2013).
Effective Graph Resistance The effective graph resistance is graph measure derived from the field of electric circuit analysis, where it is defined as the summation of effective resistance over all node pairs (Ellens et al. 201T). The effective graph resistance can be represented using the cigenvalues of Laplacian matrix as follows (Ellens et al. 2011)
|
Rs = -
Σ
(9)
10

---

Under review as a conference paper at ICLR 2020
By Corollary 2 we can represent the change of the algebraic connectivity X2 as:
A (2x; xy(thi] xx[sec))(x[[ssc] - xy(thi])
(10)
According to the above discussion, A is expected to be smaller for the operation of rewiring to 2-hop neighbor. Thus, the rewiring 2-hop neighbor operation is expected perturb the algebraic connectivity less compared with adding an edge between two nodes that are far away from each other. A similar argument can be built for effective graph resistance.
B PROOF OF COLLARY
Corollary 2. For a given graph G with Laplacian matrix one proposed rewiring operation (Ufirs Useci Vthi) affects the eigen-value > by A for i 1,...,117 (V), where
A = - [((the] x, (x, x, (thii)
(11)
where x, (index) denotes the inder-th value of the eigenvector x,
Proof. Let AL denotes the change in the Laplacian matrix after applying the rewiring operation
(Urer: Veec: Vena) to graph G. Then we have [L[fár, see) = AL [sec, für] = 1, [L[ thi =
AL fir] 1, ALssec, sec] -1, AL|thi, thi] and elsewhere. Thus
A = x ALX,
= 2x.[Sir] x; [sec] - x: x=(sec] + x; [Uhi]² - 2x; [fir]sx)
= =x/thhi]² x|(sec]2 + 2x, [frr] [sec] x,(thil)
[2x,[fir] x, [thi] x, (xx x: [thil)
which completes the proof.
C EMPIRICAL INVESTIGATION OF THE REWIRING OPERATION
In this section, conduct experiments empirically show the advancements of the proposed rewiring operator compared with the adding/deleting edge operator. We compare them from two perspectives: 1) connectivity after the attack and 2) change in eigenvalues after the attack. The experiments are carried out on the REDDIT-MULTI-IXX dataset. On each of the graph success- fully attacked by ReWatt, we perform exactly the same number of deleting/adding edge operator on it. For connectivity, the average number of components in the clean graphs is 2.6, this number becomes 3.02 after the rewiring attack while it becomes 5.2 after the deleting/adding edges attack. On the other hand, only 20% of the graphs get more disconnected (having more components) af- ter Wattattackk than the original ones, while 87% of the graphs get more disconnected after the adding/deleting edges attack. Clearly, the rewiring operator is less likely to disconnect the graph. The comparison of the change in eigenvalues is shown in Figure 3 where we compare the change in different eigenvalues of the graphs after these two attacks. Specifically, we first compute the average relative change in the i-th eigenvalue after both attacks as follows:
Aori
Xottack
TX
Apri
(12)
where Agri denotes the i-th eigenvalue of the clean graph while X Xattack denotes the i-th eigenvalue of the attacked graph. We then take the average of the above value over all the succeeded graphs, which we denoted Fx,- Specially, we use px. denote the average change ratio after ReW att
while using f4/a to denote the average change ratio after deleting/adding edge attack. To compare
the these two attacks, calculate - d//a ///a /rre and the results shown in Figure 3 The results show that in most of the cases, the deleting/adding edges attack makes much more changes to the eigenvalues the value /4/0 /FX. is way larger than 1.
By conducting these two experiments, we empirically conclude that the proposed re-wiring operator makes more subtle changes to graphs than existing methods.
11

---

Under review as a conference paper at ICLR 2020
20la
0.0
2.5
5.0
12.5
15.0
17.5
20.0
i-th eigenvalue
Figure 3: Comparison in the change of eigenvalues
D STATISTICS OF THE DATASETS
The statistics of the datasets given in Table In this table, #nodes denotes the average number of nodes over all graphs and #edges denotes the average number of edges over all graphs. ACC denotes the mean of Average Clustering Coefficient (ACC) over all graphs. GCC denotes the mean of Global Clustering Coefficient (GCC) over all graphs.
#graphs
#labels
#nodes
#edges
ACC
GCC
REDDIT-MULTI-12K
11,929
12
391.41
456.89
0.0331
0.0087
REDDDT-MULLT-5K
4,999
5
508.52
594.87
0.0268
0.0038
IMDB 1,500
3
13
65.94
0.968
0,8955
Table 2: Statistics of the data sets
12


Reviews:
[{"review_id": "rylgT8lNqB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new type of adversarial attack setting for graphs, namely graph rewiring operation, which deletes an edge in the graph and adds a new edge between one node of the first edge and one of its 2-hop neighbors. This new attack is proposed to make the perturbations unnoticeable compared with adding or deleting arbitrary edges. To solve this problem, a reinforcement learning based approach is proposed to learn the attack strategy in the black-box manner. Experiments conducted on several datasets prove the effectiveness of the proposed with over an existing method and baseline methods.\n\nOverall, this paper proposes a new adversarial setting for graphs to make the modifications unnoticeable. A reinforcement learning method is proposed to generate adversarial examples under the proposed setting. The writing is clear. However, I have several concerns about this paper as follows.\n\n1. The proposed graph rewiring operation is a special operation of the general adding and deleting operations (i.e., rewiring is operated as deleting an edge and adding a new edge with some constrains). The motivation of using rewiring is to make the perturbations unnoticeable. Besides presenting the theoretical results on this property of the rewiring operation, it's better to provide some empirical results (e.g., generated adversarial graphs) to prove that the rewiring operation can make the adversarial graphs unnoticeable in practice.\n\n2. In Table 1, why are the results of ReWatt better than RL-S2V? Since there are more constrains (i.e., smaller action space) in ReWatt than RL-S2V, RL-S2V could be easier to fool GCNs. The authors could explain more on the results.\n\n3. What are the differences between the proposed attack method based on reinforcement learning and the method in RL-S2V? RL-S2V is also based on reinforcement learning. The authors should clearly introduce the novelty of the proposed method as well as the contributions.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "S1gdft7NcS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper addresses a real problem.  Most attacks on graphs can be easily identified [1].  This paper argues that if one rewires the graph (instead of adding/deleting nodes/edges) such that the top eigenvalues of the Laplacian matrix are only slightly perturbed then the attacker can go undetected.  \n\nThe paper should address the following issues:\n\n1. There is no discussion on tracking the path capacity of the graph as measured by the largest eigenvalue of the adjacency matrix and the eigengaps between the largest in module eigenvalues of the adjacency matrix .  Rewiring often affects the path capacity even if one makes sure the degree distribution is the same and restricts the rewiring to 2-hop neighbors.\n\n2. Rewiring affects edge centrality and so one needs to show that the proposed algorithm doesn't change the distribution over edge centrality.\n\n3. In social networks, the highest eigenvalues of the adjacency matrix are very close to each other because of all the triangles.  The paper will be stronger if it included how the proposed method performs under various random graph models -- e.g., Gnp random graph, preferential attachment, and small-world.\n\nMiscellaneous notes:\n\n- The captions for the figures should be more informative.\n\n- Table 2 should list more characteristics of the graphs such as number of nodes, number of edges, exponent of the degree distribution, global clustering coefficient, average clustering coefficient, diameter, average path length.\n\n- \"Zgner &Gnnemann\" is misspelled.\n\n- \"As we can observed from the figures, ...\" has a typo in it.\n\n__________________________________________________\n[1]  B. Miller, M. Çamurcu, A. Gomez, K. Chan, T. Eliassi-Rad. Improving Robustness to Attacks Against Vertex Classification. In The 15th International Workshop on Mining and Learning with Graphs (held in conjunction with ACM SIGKDD’19), Anchorage, AK, August 2019.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "Hkl2-ampKB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors studied the adversarial attack problem for graph classification problem with graph convolutional networks. After observing that traditional attack by adding or deleting edges can change graph eigenvalues, the author proposed to attack by adding rewiring operation which make less effects. Rewiring does not change the graph edge number and the average degree. Further, the authors propose an RL based learning method to learn the policy of doing rewiring operation. Experiments show that the proposed method can make more successful attack on social network data than baselines and previous methods.\n\nThe idea of using rewiring to make graph attack is interesting and sensible. The proposed RL-based method where the search space is constraint also can solve the problem. However, I have a few concerns on the experiments.\n\n1. In figure 3, the authors also show that the proposed method can make less noticeable changes on eigenvalue. But are these changes still noticeable compared to original one? Please also show these information.\n2. 2% data for testing is too few for me. The authors should increase these number. In addition, how many replication of experiments did the author do? The author should give the variance of the results and make significant test if needed.\n3. What is the prediction accuracy of the target classifier? Did the attacker flip more correct predictions?\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJlUEvc6KS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes the ReWatt method to attack graph classification models by making unnoticeable perturbations on graph. Reinforcement learning was leveraged to find a rewiring operation a = (v1; v2; v3) at each step, which is a set of 3 nodes. In the first step, an existing edge (v1, v2) in the original graph is selected and removed. Then another node v3 that is 2-hop away from v1 and not 1-hop away is selected.  Finally (v3, v1) is connected as a new edge. Some analysis shows that the rewiring operation tends to make smaller changes to the eigenvalues of the graph's Laplacian matrix compared with simply adding and deleting edges, making it difficult to detect the attacks.\n\nPros\n\n1. The rewiring operation is more unnoticeable. Small change is shown on the eigenvalues with one rewiring operation.\n\n2. The proposed ReWatt method is effective in attacking the graph classification algorithm, facilitated by the policy network to pick the edges.\n\n3. ReWatt outperforms the RL-S2V in terms of success rate, especially when the second step in the rewiring process is not limited by 2-hops away from v1.\n\n4. The paper measured the relative difference between the graph embeddings in terms of L2 norm and measured the KL-divergence in probabilities.\n\nCons\n\n1. It's quite surprising that ReWatt achieves higher success rate than RL-S2V (first two rows of Table 1).  RL-S2V considers a properly larger set of attacks and uses Q-learning (in contrast to actor critic in ReWatt).  So is it the conclusion that actor critic is better than Q-learning?  Perhaps it will be illustrative to experiment with replacing Q-learning in RL-S2V by actor critic.  This can be implemented in the framework of ReWatt: in Eq 5, replace $p_{fir} * p_{thi}$ by $p(add/remove | e_t)$.\n\n2. The attack is specifically designed for graph classification, while the graph convolutional filter is widely used in other problems like node classification and link prediction. Can it be applied to such problems as well?\n\n3. In addition to RL-S2V, it will be helpful to compare with Nettack (Z¨ugner et. al, 2018).  It employs an admissible set of perturbations, which can be adapted for the rewiring attack.\n\n4. The paper shows the change of eigenvalues under one rewiring operation. How does it change after multiple operations?  In addition, the smaller change to the eigenvalues is compared with rewiring to more distant nodes or adding an edge between two distant nodes.  That is, it is under a *given* $v_{fir}$ and $v_{sec}$.  A different attack may select a different $v_{fir}$ and $v_{sec}$ in the first place.  So it is still not clear whether rewiring leads to less noticeable changes.\n\n5. The experiment splits the dataset into three parts, training set, rewiring operation set, and test set. However, for those predicted incorrectly on the rewiring operation set, the success rate should not be counted.  Perhaps this is already done?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a method for attacking graph convolutional networks, where a graph rewiring operation was introduced that affects the graph in a less noticeable way compared to adding/deleting edges. Reinforcement learning is applied to learn the attack strategy based on the proposed rewiring operation. The paper should be improved by acknowledging/comparing with previous work in a more proper way. In particular, I view the major innovation is on the rewiring operation and its analysis. The reinforcement learning formulation is similar to Dai et al (2018). This connection should be made more clear in the technical part. One issue that needs to be discussed on is that if you directly consider the triples as actions, the space will be huge. Do you apply some hierarchical treatment as suggested by Dai et al. (2018)?  The review comments should be considered to further improve too.
Decision: Reject