Revisiting Graph Adversarial Attack and Defense From a Data Distribution Perspective

Recent studies have shown that structural perturbations are significantly effective in degrading the accuracy of Graph Neural Networks (GNNs) in the semi-supervised node classification (SSNC) task. However, the reasons for the destructive nature of gradient-based methods have not been explored in-depth. In this work, we discover an interesting phenomenon: the adversarial edges are not uniformly distributed on the graph, and a majority of perturbations are generated around the training nodes in poisoning attacks. Combined with this phenomenon, we provide an explanation for the effectiveness of the gradient-based attack method from a data distribution perspective and revisit both poisoning attack and evasion attack in SSNC. From this new perspective, we empirically and theoretically discuss some other attack tendencies. Based on the analysis, we provide nine practical tips on both attack and defense and meanwhile leverage them to improve existing attack and defense methods. Moreover, we design a fast attack method and a self-training defense method, which outperform the state-of-the-art methods and can effectively scale to large graphs like ogbn-arxiv. We validate our claims through extensive experiments on four benchmark datasets. * Corresponding to Xiang Ao implementation details and the statistics of the datasets are provided in A.1. RELATED WORK Many efforts have been made to study various properties of the gradient-based attack algorithms. GCN-SVD Entezari et al. (2020) discovers that attacks exhibit a specific behavior in the spectrum 1 Our focus is to revisit both attack and defense sides from a new view. These two algorithms are natural byproducts of this work, so we put them in the appendix.