  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.
