GAIM: Attacking Graph Neural Networks via Adversarial Influence Maximization
This addresses the vulnerability of GNNs to adversarial attacks, which is an incremental improvement over prior methods by integrating attack components and considering practical black-box settings.
The authors tackled the problem of misleading Graph Neural Networks (GNNs) by introducing GAIM, an adversarial attack method that reframes the attack as an adversarial influence maximization problem, achieving effective results in untargeted and targeted attacks across five benchmark datasets and three models.
Recent studies show that well-devised perturbations on graph structures or node features can mislead trained Graph Neural Network (GNN) models. However, these methods often overlook practical assumptions, over-rely on heuristics, or separate vital attack components. In response, we present GAIM, an integrated adversarial attack method conducted on a node feature basis while considering the strict black-box setting. Specifically, we define an adversarial influence function to theoretically assess the adversarial impact of node perturbations, thereby reframing the GNN attack problem into the adversarial influence maximization problem. In our approach, we unify the selection of the target node and the construction of feature perturbations into a single optimization problem, ensuring a unique and consistent feature perturbation for each target node. We leverage a surrogate model to transform this problem into a solvable linear programming task, streamlining the optimization process. Moreover, we extend our method to accommodate label-oriented attacks, broadening its applicability. Thorough evaluations on five benchmark datasets across three popular models underscore the effectiveness of our method in both untargeted and label-oriented targeted attacks. Through comprehensive analysis and ablation studies, we demonstrate the practical value and efficacy inherent to our design choices.