Multifaceted Anchor Nodes Attack on Graph Neural Networks: A Budget-Efficient Approach

Structural adversarial attack methods that attack a graph neural network by perturbing the edges of the input graph are well-known for their strong effectiveness. However, most existing structural attacks focus on achieving high attack performance, but they ignore the high cost of budget to control (i.e., buy out or hijacking) the nodes (i.e., user accounts in a social network) when executing the attacks in real-world networks. The classic anchor nodes attacks are more budget-efficient because they only control a small set of anchor nodes to conduct all the attacks. However, their attack effectiveness is also limited by the restriction of using one set of anchor nodes. In this paper, we develop a strong and budget-efficient multifaceted anchor nodes attack on graph neural networks. The key idea is to simultaneously train multiple sets of anchor nodes and an assignment network, such that the assignment network can select the best set of anchor nodes to conduct each new attack successfully. This significantly improves the attack effectiveness while keeping the budget of controlled nodes small. Extensive experiments on five real-world datasets demonstrate the outstanding performance of our method. Our code and Appendix is available at https://github.com/zhz0108/mfan/.