Revisiting Graph Adversarial Attack: A Perspective of Budget Optimization

Graph adversarial attacks refer to a class of adversarial attack methods targeting graph-structured data, such as social networks, knowledge graphs, and molecular structures. The objective of these attacks is to introduce subtle yet carefully designed perturbations to graph data (e.g., nodes, edges, or features) to cause graph-based machine learning models, such as graph neural networks (GNNs), to produce incorrect predictions or classification results. The core idea behind graph adversarial attacks is to exploit the vulnerabilities of the model, maximizing the degradation of its performance with minimal perturbations. However, due to the incompleteness of attack strategies, graph adversarial attacks often exhibit redundancy, meaning that some perturbations are ineffective. These ineffective perturbations consume the attack budget and increase the likelihood of detection. To address this issue, this paper proposes Budget-Reduced Attack Filtering (BRAF in short) frameworks capable of eliminating ineffective perturbations produced by existing graph adversarial attack methods, thereby optimizing the attack budget. Extensive experiments validate the effectiveness and scalability of the proposed filtering frameworks. The code is available at https://github.com/Xiangchao-Wen/Filter-Graph-Attack.