# Minimum Topology Attacks for Graph Neural Networks

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 49 references that are in the map.
- First posted on arXiv 5 Mar 2024.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (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)
- [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)
- [Decoupling Direction and Norm for Efficient Gradient-Based L2 Adversarial Attacks and Defenses](https://mlsanity.com/paper/1811.09600/) (2018)
- [Robustness of Graph Neural Networks at Scale](https://mlsanity.com/paper/2110.14038/) (2021)
- [Be Confident! Towards Trustworthy Graph Neural Networks via Confidence Calibration](https://mlsanity.com/paper/2109.14285/) (2021)
- [Hiding Individuals and Communities in a Social Network](https://mlsanity.com/paper/1608.00375/) (2016)
- [A Restricted Black-box Adversarial Framework Towards Attacking Graph Embedding Models](https://mlsanity.com/paper/1908.01297/) (2019)
- [Elastic Graph Neural Networks](https://mlsanity.com/paper/2107.06996/) (2021)
- [Fast Minimum-norm Adversarial Attacks through Adaptive Norm Constraints](https://mlsanity.com/paper/2102.12827/) (2021)
- [Graph Robustness Benchmark: Benchmarking the Adversarial Robustness of Graph Machine Learning](https://mlsanity.com/paper/2111.04314/) (2021)
- [Distribution Density, Tails, and Outliers in Machine Learning: Metrics and Applications](https://mlsanity.com/paper/1910.13427/) (2019)
- [Curls & Whey: Boosting Black-Box Adversarial Attacks](https://mlsanity.com/paper/1904.01160/) (2019)
- [Understanding Structural Vulnerability in Graph Convolutional Networks](https://mlsanity.com/paper/2108.06280/) (2021)
- [Reliable Representations Make A Stronger Defender: Unsupervised Structure Refinement for Robust GNN](https://mlsanity.com/paper/2207.00012/) (2022)
- [Attacking Graph Convolutional Networks via Rewiring](https://mlsanity.com/paper/1906.03750/) (2019)
- [A Unified Framework for Data Poisoning Attack to Graph-based Semi-supervised Learning](https://mlsanity.com/paper/1910.14147/) (2019)
- [Improving Calibration through the Relationship with Adversarial Robustness](https://mlsanity.com/paper/2006.16375/) (2020)
- [Unsupervised Graph Poisoning Attack via Contrastive Loss Back-propagation](https://mlsanity.com/paper/2201.07986/) (2022)
- [Data Poisoning Attack against Unsupervised Node Embedding Methods](https://mlsanity.com/paper/1810.12881/) (2018)
- [MGNNI: Multiscale Graph Neural Networks with Implicit Layers](https://mlsanity.com/paper/2210.08353/) (2022)
- [Defending Graph Convolutional Networks against Dynamic Graph Perturbations via Bayesian Self-supervision](https://mlsanity.com/paper/2203.03762/) (2022)
- [Bandits for Structure Perturbation-based Black-box Attacks to Graph Neural Networks with Theoretical Guarantees](https://mlsanity.com/paper/2205.03546/) (2022)

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

- [Can Large Language Models Improve the Adversarial Robustness of Graph Neural Networks?](https://mlsanity.com/paper/2408.08685/) (2024)
- [A General Black-box Adversarial Attack on Graph-based Fake News Detectors](https://mlsanity.com/paper/2404.15744/) (2024)
- [Query-Based and Unnoticeable Graph Injection Attack from Neighborhood Perspective](https://mlsanity.com/paper/2502.01936/) (2025)
- [AGSOA:Graph Neural Network Targeted Attack Based on Average Gradient and Structure Optimization](https://mlsanity.com/paper/2406.13228/) (2024)
- [RIDA: A Robust Attack Framework on Incomplete Graphs](https://mlsanity.com/paper/2407.18170/) (2024)
- [Dynamic Gradient Influencing for Viral Marketing Using Graph Neural Networks](https://mlsanity.com/paper/2403.12399/) (2024)

## Abstract (arXiv)

With the great popularity of Graph Neural Networks (GNNs), their robustness to adversarial topology attacks has received significant attention. Although many attack methods have been proposed, they mainly focus on fixed-budget attacks, aiming at finding the most adversarial perturbations within a fixed budget for target node. However, considering the varied robustness of each node, there is an inevitable dilemma caused by the fixed budget, i.e., no successful perturbation is found when the budget is relatively small, while if it is too large, the yielding redundant perturbations will hurt the invisibility. To break this dilemma, we propose a new type of topology attack, named minimum-budget topology attack, aiming to adaptively find the minimum perturbation sufficient for a successful attack on each node. To this end, we propose an attack model, named MiBTack, based on a dynamic projected gradient descent algorithm, which can effectively solve the involving non-convex constraint optimization on discrete topology. Extensive results on three GNNs and four real-world datasets show that MiBTack can successfully lead all target nodes misclassified with the minimum perturbation edges. Moreover, the obtained minimum budget can be used to measure node robustness, so we can explore the relationships of robustness, topology, and uncertainty for nodes, which is beyond what the current fixed-budget topology attacks can offer.