Black-Box Attacks on Graph Neural Networks via White-Box Methods With Performance Guarantees

Graph adversarial attacks can be classified as either white-box or black-box attacks. White-box attackers typically exhibit better performance because they can exploit the known structure of victim models. However, in practical settings, most attackers generate perturbations under black-box conditions, where the victim model is unknown. A fundamental question is how to leverage a white-box attacker to attack a black-box model. Some current black-box attack approaches employ white-box techniques to attack a surrogate model, resulting in satisfactory outcomes. Nonetheless, such white-box attackers must be meticulously designed and lack theoretical assurances for attack effectiveness. In this paper, we propose a novel framework that utilizes simple white-box techniques to conduct black-box attacks and provides the lower bound for attack performance. Specifically, we first employ a more comprehensive GCN technique named BiasGCN to approximate the victim model, and subsequently, use a simple white-box approach to attack the approximate model. We provide a generalization guarantee for our BiasGCN and employ it to obtain the lower bound on attack performance. Our method is evaluated on various datasets, and the experimental results indicate that our approach surpasses recently proposed baselines.