Query-based Adversarial Attacks on Graph with Fake Nodes

While deep neural networks have achieved great success on the graph analysis, recent works have shown that they are also vulnerable to adversarial attacks where fraudulent users can fool the model with a limited number of queries. Compared with adversarial attacks on image classification, performing adversarial attack on graphs is challenging because of the discrete and non-differential nature of a graph. To address these issues, we proposed Cluster Attack, a novel adversarial attack by introducing a set of fake nodes to the original graph which can mislead the classification on certain victim nodes. Moreover, our attack is performed in a practical and unnoticeable manner. Extensive experiments demonstrate the effectiveness of our method in terms of the success rate of attack.