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 existing operators. 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 and the advantages of the rewiring operation.
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?