# EvA: Evolutionary Attacks on Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 27 references that are in the map.
- First posted on arXiv 10 Jul 2025.

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

- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [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)
- [Adversarial Attack and Defense on Graph Data: A Survey](https://mlsanity.com/paper/1812.10528/) (2018)
- [Robustness of Graph Neural Networks at Scale](https://mlsanity.com/paper/2110.14038/) (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)
- [Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More](https://mlsanity.com/paper/2008.12952/) (2020)
- [Are Defenses for Graph Neural Networks Robust?](https://mlsanity.com/paper/2301.13694/) (2023)
- [Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directions](https://mlsanity.com/paper/2306.15427/) (2023)
- [A Hard Label Black-box Adversarial Attack Against Graph Neural Networks](https://mlsanity.com/paper/2108.09513/) (2021)
- [Let Graph be the Go Board: Gradient-free Node Injection Attack for Graph Neural Networks via Reinforcement Learning](https://mlsanity.com/paper/2211.10782/) (2022)
- [Conformal Inductive Graph Neural Networks](https://mlsanity.com/paper/2407.09173/) (2024)
- [Simple and Efficient Partial Graph Adversarial Attack: A New Perspective](https://mlsanity.com/paper/2308.07834/) (2023)

## Abstract (arXiv)

Even a slight perturbation in the graph structure can cause a significant drop in the accuracy of graph neural networks (GNNs). Most existing attacks leverage gradient information to perturb edges. This relaxes the attack's optimization problem from a discrete to a continuous space, resulting in solutions far from optimal. It also restricts the adaptability of the attack to non-differentiable objectives. Instead, we introduce a few simple yet effective enhancements of an evolutionary-based algorithm to solve the discrete optimization problem directly. Our Evolutionary Attack (EvA) works with any black-box model and objective, eliminating the need for a differentiable proxy loss. This allows us to design two novel attacks that reduce the effectiveness of robustness certificates and break conformal sets. The memory complexity of our attack is linear in the attack budget. Among our experiments, EvA shows ~11% additional drop in accuracy on average compared to the best previous attack, revealing significant untapped potential in designing attacks.