# Bandits for Structure Perturbation-based Black-box Attacks to Graph Neural Networks with Theoretical Guarantees

arXiv: https://arxiv.org/abs/2205.03546 · HTML: https://mlsanity.com/paper/2205.03546/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 42 references that are in the map.
- First posted on arXiv 7 May 2022.

## Builds on (most cited first, 28 of 28)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting](https://mlsanity.com/paper/1709.04875/) (2017)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Black-box Adversarial Attacks with Limited Queries and Information](https://mlsanity.com/paper/1804.08598/) (2018)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [GraphAF: a Flow-based Autoregressive Model for Molecular Graph Generation](https://mlsanity.com/paper/2001.09382/) (2020)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective](https://mlsanity.com/paper/1906.04214/) (2019)
- [Prior Convictions: Black-Box Adversarial Attacks with Bandits and Priors](https://mlsanity.com/paper/1807.07978/) (2018)
- [Query-Efficient Hard-label Black-box Attack:An Optimization-based Approach](https://mlsanity.com/paper/1807.04457/) (2018)
- [Backdoor Attacks to Graph Neural Networks](https://mlsanity.com/paper/2006.11165/) (2020)
- [Improving Black-box Adversarial Attacks with a Transfer-based Prior](https://mlsanity.com/paper/1906.06919/) (2019)
- [Fake News Detection on Social Media using Geometric Deep Learning](https://mlsanity.com/paper/1902.06673/) (2019)
- [NATTACK: Learning the Distributions of Adversarial Examples for an Improved Black-Box Attack on Deep Neural Networks](https://mlsanity.com/paper/1905.00441/) (2019)
- [Hiding Individuals and Communities in a Social Network](https://mlsanity.com/paper/1608.00375/) (2016)
- [Towards More Practical Adversarial Attacks on Graph Neural Networks](https://mlsanity.com/paper/2006.05057/) (2020)
- [A Restricted Black-box Adversarial Framework Towards Attacking Graph Embedding Models](https://mlsanity.com/paper/1908.01297/) (2019)
- [Fast Gradient Attack on Network Embedding](https://mlsanity.com/paper/1809.02797/) (2018)
- [Attacking Graph-based Classification via Manipulating the Graph Structure](https://mlsanity.com/paper/1903.00553/) (2019)
- [A Hard Label Black-box Adversarial Attack Against Graph Neural Networks](https://mlsanity.com/paper/2108.09513/) (2021)
- [Adversarial Attack on Community Detection by Hiding Individuals](https://mlsanity.com/paper/2001.07933/) (2020)
- [Graph Universal Adversarial Attacks: A Few Bad Actors Ruin Graph Learning Models](https://mlsanity.com/paper/2002.04784/) (2020)

## Built on by (most cited first, 9 of 9)

- [Graph Neural Network Causal Explanation via Neural Causal Models](https://mlsanity.com/paper/2407.09378/) (2024)
- [Minimum Topology Attacks for Graph Neural Networks](https://mlsanity.com/paper/2403.02723/) (2024)
- [A Certified Radius-Guided Attack Framework to Image Segmentation Models](https://mlsanity.com/paper/2304.02693/) (2023)
- [Certifiable Black-Box Attacks with Randomized Adversarial Examples: Breaking Defenses with Provable Confidence](https://mlsanity.com/paper/2304.04343/) (2023)
- [Watermarking Graph Neural Networks via Explanations for Ownership Protection](https://mlsanity.com/paper/2501.05614/) (2025)
- [Backdoor Attacks on Discrete Graph Diffusion Models](https://mlsanity.com/paper/2503.06340/) (2025)
- [Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbations](https://mlsanity.com/paper/2503.18503/) (2025)
- [Learning to Attack: A Bandit Approach to Adversarial Context Poisoning](https://mlsanity.com/paper/2603.00567/) (2026)
- [Can LLMs Fool Graph Learning? Exploring Universal Adversarial Attacks on Text-Attributed Graphs](https://mlsanity.com/paper/2603.21155/) (2026)

## Abstract (arXiv)

Graph neural networks (GNNs) have achieved state-of-the-art performance in many graph-based tasks such as node classification and graph classification. However, many recent works have demonstrated that an attacker can mislead GNN models by slightly perturbing the graph structure. Existing attacks to GNNs are either under the less practical threat model where the attacker is assumed to access the GNN model parameters, or under the practical black-box threat model but consider perturbing node features that are shown to be not enough effective. In this paper, we aim to bridge this gap and consider black-box attacks to GNNs with structure perturbation as well as with theoretical guarantees. We propose to address this challenge through bandit techniques. Specifically, we formulate our attack as an online optimization with bandit feedback. This original problem is essentially NP-hard due to the fact that perturbing the graph structure is a binary optimization problem. We then propose an online attack based on bandit optimization which is proven to be sublinear to the query number T, i.e., O(√NT3/4) where N is the number of nodes in the graph. Finally, we evaluate our proposed attack by conducting experiments over multiple datasets and GNN models. The experimental results on various citation graphs and image graphs show that our attack is both effective and efficient. Source code is available at~urlhttps://github.com/Metaoblivion/BanditGNNAttack