Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: 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.  

The paper should address the following issues:

1. 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.

2. Rewiring affects edge centrality and so one needs to show that the proposed algorithm doesn't change the distribution over edge centrality.

3. 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.

Miscellaneous notes:

- The captions for the figures should be more informative.

- 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.

- "Zgner &Gnnemann" is misspelled.

- "As we can observed from the figures, ..." has a typo in it.

__________________________________________________
[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.

review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: 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.

Overall, 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.

1. 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.

2. 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.

3. 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.
review_title: Official Blind Review #4

final_score: rating: 3: Weak Reject
review_content: 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.

Pros

1. The rewiring operation is more unnoticeable. Small change is shown on the eigenvalues with one rewiring operation.

2. The proposed ReWatt method is effective in attacking the graph classification algorithm, facilitated by the policy network to pick the edges.

3. 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.

4. The paper measured the relative difference between the graph embeddings in terms of L2 norm and measured the KL-divergence in probabilities.

Cons

1. 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)$.

2. 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?

3. 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.

4. 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.

5. 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?
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: 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.

The 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.

1. 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.
2. 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.
3. What is the prediction accuracy of the target classifier? Did the attacker flip more correct predictions?

review_title: Official Blind Review #2

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