mlsanityData to 14 Oct 2026

EvA: Evolutionary Attacks on Graphs

arXiv 2507.08212 ↗First posted 10 Jul 2025cs.LGcited by 0

Not on the map. Why?

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.

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

17 of 27 references.

References · 17

  1. 2018Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examplescited by 1,268
  2. 2018Pitfalls of Graph Neural Network Evaluationcited by 1,007
  3. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 595
  4. 2018Adversarial Attacks on Neural Networks for Graph Datacited by 397
  5. 2018Adversarial Attack on Graph Structured Datacited by 301
  6. 2019Topology Attack and Defense for Graph Neural Networks: An Optimization Perspectivecited by 196
  7. 2018Adversarial Attack and Defense on Graph Data: A Surveycited by 167
  8. 2021Robustness of Graph Neural Networks at Scalecited by 100
  9. 2016Hiding Individuals and Communities in a Social Networkcited by 77
  10. 2019A Restricted Black-box Adversarial Framework Towards Attacking Graph Embedding Modelscited by 68
  11. 2020Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and Morecited by 56
  12. 2023Are Defenses for Graph Neural Networks Robust?cited by 38
5 more
  1. 2023Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directionscited by 28
  2. 2021A Hard Label Black-box Adversarial Attack Against Graph Neural Networkscited by 26
  3. 2022Let Graph be the Go Board: Gradient-free Node Injection Attack for Graph Neural Networks via Reinforcement Learningcited by 19
  4. 2024Conformal Inductive Graph Neural Networkscited by 10
  5. 2023Simple and Efficient Partial Graph Adversarial Attack: A New Perspectivecited by 8

Built on by

Not cited yet.