SPA: A poisoning attack framework for graph neural networks through searching and pairing

Graph Neural Networks (GNN) have played an important role in many fields, while GNNs also suffer from adversarial attacks that aim to malfunction the GNN model by changing the adjacency matrix (i.e. generating adversarial edges) or node features (i.e. generating adversarial features) in graph data. Although the gradient-based adversarial attack methods have achieved remarkable results in DNNs, optimizing discrete adversarial edges in graph data using continuous gradients may lead to sub-optimal solutions. In order to alleviate this situation, we propose a novel Searching and Pairing Attack (SPA) method to effectively generate adversarial edges by treating each adversarial edge as a combination of a pair of adversarial nodes. The proposed SPA method generates the adversarial edges through a Node Searching step and a Node Pairing step. The proposed Node Searching Ant Colony Optimization (NS-ACO) improves the attack effect by using the ability of heuristic algorithm to quickly find the approximate optimal solution, while in the Node Pairing (NP) step we propose a generative graph convolutional network with a novel Aggregate Cooperative (AC) layer to generate a set of nodes that meet the constraints, so as to obtain the perturbation set together with the Node Searching step. The proposed SPA method outperforms the state-of-the-art adversarial attack methods and achieves a misclassification rate of 32.5% in the poisoning attack on Cora dataset with a perturbation rate of 0.5%.