Greedy-Based Black-Box Adversarial Attack Scheme on Graph Structure

Effective attack schemes that simulate adversarial attack behavior in graph network is the key to exploring potential threats in practical scenarios. However, most attack schemes are not accurate in locating target nodes and lock unnoticeable perturbations from the perspective of graph embedding space, leading to a low success rate of attack and high perturbation on node classification tasks. To overcome these problems, we propose a greedy-based black-box adversarial attack scheme on graph structure, which named GB-Attack. Firstly, we use local betweenness centrality to accurately locate target node set to modify graph structure data with high importance. Secondly, we combine the similarity of graph in latent space and theorems in graph theory to obtain adversarial samples with low perturbation. Finally, we apply greedy strategy to get adversarial samples with higher score function to maximize the probability of target nodes being misclassified. Experimental results show that the attack accuracy of GB-Attack on GCN models is significantly improved compared with other four attack schemes. Notably, the attack accuracy under multilateral perturbations of GB-Attack is 9.73% higher than that of RL-S2V.