Spectral adversarial attack on graph via node injection.

Graph Neural Networks (GNNs) have shown remarkable achievements and have been extensively applied in various downstream tasks, such as node classification and community detection. However, recent studies have demonstrated that GNNs are vulnerable to subtle adversarial perturbations on graphs, including node injection attacks, which negatively affect downstream tasks. Existing node injection attacks have mainly focused on the limited local nodes, neglecting the analysis of the whole graph which restricts the attack's ability. In this paper, we propose a novel global graph attack method named Spectral Node Injection Attack (SpNIA), which takes into account the spectral distance to more effectively leverage the limited adversarial budgets. Specifically, we maximize the Euclidean distance of eigenvalues decomposed from the Laplacian matrices of original and injected graph, and solve the optimization problem by gradient-based methods. Due to the different dimensions of matrices in original and injected graph, we construct a novel optimization framework of the node injection attack which also allows injected nodes to connect with each other for more malicious message passing. Extensive experiments on benchmark datasets indicate significant decrease in GNNs performance and show empirical evidences to demonstrate the feasibility and effectiveness of SpNIA.