Blindfolded Attackers Still Threatening: Strict Black-Box Adversarial Attacks on Graphs
This work addresses the problem of unrealistic assumptions in graph adversarial attacks for real-world scenarios, proposing a more challenging and practical attack setting for the graph machine learning community.
This paper introduces a strict black-box graph attack setting where the attacker has no knowledge or query access to the victim model. The proposed attack strategy, which unifies graph-based models through a generic graph filter, successfully reduces Macro-F1 by 6.4% in node classification and 29.5% in graph classification, demonstrating significant impact even under severe constraints.
Adversarial attacks on graphs have attracted considerable research interests. Existing works assume the attacker is either (partly) aware of the victim model, or able to send queries to it. These assumptions are, however, unrealistic. To bridge the gap between theoretical graph attacks and real-world scenarios, in this work, we propose a novel and more realistic setting: strict black-box graph attack, in which the attacker has no knowledge about the victim model at all and is not allowed to send any queries. To design such an attack strategy, we first propose a generic graph filter to unify different families of graph-based models. The strength of attacks can then be quantified by the change in the graph filter before and after attack. By maximizing this change, we are able to find an effective attack strategy, regardless of the underlying model. To solve this optimization problem, we also propose a relaxation technique and approximation theories to reduce the difficulty as well as the computational expense. Experiments demonstrate that, even with no exposure to the model, the Macro-F1 drops 6.4% in node classification and 29.5% in graph classification, which is a significant result compared with existent works.