# A Hard Label Black-box Adversarial Attack Against Graph Neural Networks

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 65 references that are in the map.
- First posted on arXiv 21 Aug 2021.

## Builds on (most cited first, 30 of 37)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective](https://mlsanity.com/paper/1906.04214/) (2019)
- [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)
- [Sign-OPT: A Query-Efficient Hard-label Adversarial Attack](https://mlsanity.com/paper/1909.10773/) (2019)
- [Graph Backdoor](https://mlsanity.com/paper/2006.11890/) (2020)
- [Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1805.10367/) (2018)
- [Meta-GNN: On Few-shot Node Classification in Graph Meta-learning](https://mlsanity.com/paper/1905.09718/) (2019)
- [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)
- [SurFree: a fast surrogate-free black-box attack](https://mlsanity.com/paper/2011.12807/) (2020)
- [Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbation](https://mlsanity.com/paper/2008.10715/) (2020)
- [Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More](https://mlsanity.com/paper/2008.12952/) (2020)
- [Attacking Graph-based Classification via Manipulating the Graph Structure](https://mlsanity.com/paper/1903.00553/) (2019)

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

- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- ["Real Attackers Don't Compute Gradients": Bridging the Gap Between Adversarial ML Research and Practice](https://mlsanity.com/paper/2212.14315/) (2022)
- [Model Inversion Attacks against Graph Neural Networks](https://mlsanity.com/paper/2209.07807/) (2022)
- [Safety in Graph Machine Learning: Threats and Safeguards](https://mlsanity.com/paper/2405.11034/) (2024)
- [Bandits for Structure Perturbation-based Black-box Attacks to Graph Neural Networks with Theoretical Guarantees](https://mlsanity.com/paper/2205.03546/) (2022)
- [Graph Neural Network Causal Explanation via Neural Causal Models](https://mlsanity.com/paper/2407.09378/) (2024)
- [Cluster Attack: Query-based Adversarial Attacks on Graphs with Graph-Dependent Priors](https://mlsanity.com/paper/2109.13069/) (2021)
- [Multi-SpacePhish: Extending the Evasion-space of Adversarial Attacks against Phishing Website Detectors using Machine Learning](https://mlsanity.com/paper/2210.13660/) (2022)
- [AttackGNN: Red-Teaming GNNs in Hardware Security Using Reinforcement Learning](https://mlsanity.com/paper/2402.13946/) (2024)
- [Certifiable Black-Box Attacks with Randomized Adversarial Examples: Breaking Defenses with Provable Confidence](https://mlsanity.com/paper/2304.04343/) (2023)
- [Exact Verification of Graph Neural Networks with Incremental Constraint Solving](https://mlsanity.com/paper/2508.09320/) (2025)
- [Node Injection Link Stealing Attack](https://mlsanity.com/paper/2307.13548/) (2023)
- [Untargeted Adversarial Attack on Knowledge Graph Embeddings](https://mlsanity.com/paper/2405.10970/) (2024)
- [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)
- [Revisiting Edge Perturbation for Graph Neural Network in Graph Data Augmentation and Attack](https://mlsanity.com/paper/2403.07943/) (2024)
- [On the Validity of Traditional Vulnerability Scoring Systems for Adversarial Attacks against LLMs](https://mlsanity.com/paper/2412.20087/) (2024)
- [Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbations](https://mlsanity.com/paper/2503.18503/) (2025)
- [CAT: Can Trust be Predicted with Context-Awareness in Dynamic Heterogeneous Networks?](https://mlsanity.com/paper/2512.11352/) (2025)
- [MDTD: A Multi Domain Trojan Detector for Deep Neural Networks](https://mlsanity.com/paper/2308.15673/) (2023)
- [GNNBleed: Inference Attacks to Unveil Private Edges in Graphs with Realistic Access to GNN Models](https://mlsanity.com/paper/2311.16139/) (2023)
- [Adverseness vs. Equilibrium: Exploring Graph Adversarial Resilience through Dynamic Equilibrium](https://mlsanity.com/paper/2505.14463/) (2025)
- [EvA: Evolutionary Attacks on Graphs](https://mlsanity.com/paper/2507.08212/) (2025)
- [Graph Unlearning: Efficient Node Removal in Graph Neural Networks](https://mlsanity.com/paper/2509.04785/) (2025)
- [Unveiling the Vulnerability of Graph-LLMs: An Interpretable Multi-Dimensional Adversarial Attack on TAGs](https://mlsanity.com/paper/2510.12233/) (2025)
- [Can Subgraph Explanations Be Weaponized to Steal Graph Neural Networks?](https://mlsanity.com/paper/2605.30470/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have achieved state-of-the-art performance in various graph structure related tasks such as node classification and graph classification. However, GNNs are vulnerable to adversarial attacks. Existing works mainly focus on attacking GNNs for node classification; nevertheless, the attacks against GNNs for graph classification have not been well explored. In this work, we conduct a systematic study on adversarial attacks against GNNs for graph classification via perturbing the graph structure. In particular, we focus on the most challenging attack, i.e., hard label black-box attack, where an attacker has no knowledge about the target GNN model and can only obtain predicted labels through querying the target model.To achieve this goal, we formulate our attack as an optimization problem, whose objective is to minimize the number of edges to be perturbed in a graph while maintaining the high attack success rate. The original optimization problem is intractable to solve, and we relax the optimization problem to be a tractable one, which is solved with theoretical convergence guarantee. We also design a coarse-grained searching algorithm and a query-efficient gradient computation algorithm to decrease the number of queries to the target GNN model. Our experimental results on three real-world datasets demonstrate that our attack can effectively attack representative GNNs for graph classification with less queries and perturbations. We also evaluate the effectiveness of our attack under two defenses: one is well-designed adversarial graph detector and the other is that the target GNN model itself is equipped with a defense to prevent adversarial graph generation. Our experimental results show that such defenses are not effective enough, which highlights more advanced defenses.