Exploratory adversarial attacks on graph neural networks for semi-supervised node classification

Graph neural networks (GNNs) have been successfully used to analyze non-Euclidean network data. Recently, there emerge a number of works to investigate the robustness of GNNs by adding adversarial noises into the graph topology, where the gradient-based attacks are widely studied due to their inherent efficiency and high effectiveness. However, the gradient-based attacks often lead to sub-optimal results due to the discrete structure of graph data. To address this issue, we propose a novel exploratory adversarial attack (termed as EpoAtk) to boost the gradient-based perturbations on graphs. The exploratory strategy in EpoAtk includes three phases, generation, evaluation and recombination, with the goal of sidestepping the possible misinformation that the maximal gradient provides. In particular, our evaluation phase introduces a self-training objective containing three effective evaluation functions to fully exploit the useful information of unlabeled nodes. EpoAtk is evaluated on multiple benchmark datasets for the task of semi-supervised node classification in different attack settings. Extensive experimental results demonstrate that the proposed method achieves consistent and significant improvements over the state-of-the-art adversarial attacks with the same attack budgets.