# Cluster Attack: Query-based Adversarial Attacks on Graphs with Graph-Dependent Priors

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 35 references that are in the map.
- First posted on arXiv 27 Sep 2021.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [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)
- [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)
- [DeepInf: Social Influence Prediction with Deep Learning](https://mlsanity.com/paper/1807.05560/) (2018)
- [TDGIA:Effective Injection Attacks on Graph Neural Networks](https://mlsanity.com/paper/2106.06663/) (2021)
- [Single Node Injection Attack against Graph Neural Networks](https://mlsanity.com/paper/2108.13049/) (2021)
- [Attack Graph Convolutional Networks by Adding Fake Nodes](https://mlsanity.com/paper/1810.10751/) (2018)
- [A Hard Label Black-box Adversarial Attack Against Graph Neural Networks](https://mlsanity.com/paper/2108.09513/) (2021)
- [Local Graph Clustering with Network Lasso](https://mlsanity.com/paper/2004.12199/) (2020)

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

- [A General Black-box Adversarial Attack on Graph-based Fake News Detectors](https://mlsanity.com/paper/2404.15744/) (2024)
- [Minimum Topology Attacks for Graph Neural Networks](https://mlsanity.com/paper/2403.02723/) (2024)
- [Single Node Injection Label Specificity Attack on Graph Neural Networks via Reinforcement Learning](https://mlsanity.com/paper/2305.02901/) (2023)
- [Query-Based and Unnoticeable Graph Injection Attack from Neighborhood Perspective](https://mlsanity.com/paper/2502.01936/) (2025)
- [Unveiling the Threat of Fraud Gangs to Graph Neural Networks: Multi-Target Graph Injection Attacks Against GNN-Based Fraud Detectors](https://mlsanity.com/paper/2412.18370/) (2024)
- [Evading Overlapping Community Detection via Proxy Node Injection](https://mlsanity.com/paper/2509.21211/) (2025)
- [Target-Aware Interaction-Guided Reinforcement Learning for Black-Box Node Injection Attacks on Graph Neural Networks](https://mlsanity.com/paper/2607.04091/) (2026)

## Abstract (arXiv)

While deep neural networks have achieved great success in graph analysis, recent work has shown that they are vulnerable to adversarial attacks. Compared with adversarial attacks on image classification, performing adversarial attacks on graphs is more challenging because of the discrete and non-differential nature of the adjacent matrix for a graph. In this work, we propose Cluster Attack -- a Graph Injection Attack (GIA) on node classification, which injects fake nodes into the original graph to degenerate the performance of graph neural networks (GNNs) on certain victim nodes while affecting the other nodes as little as possible. We demonstrate that a GIA problem can be equivalently formulated as a graph clustering problem; thus, the discrete optimization problem of the adjacency matrix can be solved in the context of graph clustering. In particular, we propose to measure the similarity between victim nodes by a metric of Adversarial Vulnerability, which is related to how the victim nodes will be affected by the injected fake node, and to cluster the victim nodes accordingly. Our attack is performed in a practical and unnoticeable query-based black-box manner with only a few nodes on the graphs that can be accessed. Theoretical analysis and extensive experiments demonstrate the effectiveness of our method by fooling the node classifiers with only a small number of queries.