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

Abstract

Structural adversarial attack methods, which attack graph neural networks (GNNs) by perturbing the edges of the input graph, are well-recognized for their high effectiveness. However, most existing structural attacks prioritize maximizing attack performance while neglecting the significant budget required to control (i.e., acquire or hijack) the nodes (e.g., user accounts in a social network) necessary for executing such attacks in real-world networks. Classic anchor node attacks are comparatively more budget-efficient, as they rely on controlling a small set of anchor nodes to conduct all attacks. Nevertheless, their attack efficacy is constrained by the limitation of using a single set of anchor nodes. In this work, we propose a strong and budget-efficient multifaceted anchor nodes attack on GNNs, with the core innovation lies in the simultaneous training of multiple sets of anchor nodes and an assignment network, enabling the assignment network to select the most optimal set of anchor nodes for each new attack. This approach significantly enhances attack effectiveness while maintaining a minimal budget for node control. Extensive experiments across five real-world datasets demonstrate the superior performance of the proposed method.