EvA: Evolutionary Attacks on Graphs
Sadegh Akhondzadeh, Soroush H. Zargarbashi, Jimin Cao, Aleksandar Bojchevski · 2025
Read EvA: Evolutionary Attacks on Graphs by Sadegh Akhondzadeh, Soroush H. Zargarbashi, Jimin Cao, Aleksandar Bojchevski (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-08212.txt.
Introduction
Mohammad Sadegh Akhondzadeh and co-authors present EvA, a 2025 evolutionary attack on graph neural networks. Small tweaks to a graph can sharply cut a network accuracy. Most attacks lean on gradients, which forces a discrete puzzle into a smooth shape and loses quality. Gradient tricks also fail when the goal cannot be differentiated.
EvA solves the discrete problem head-on with an evolution-style search. It works on any black-box model and any goal. The team built two new attacks from it, one against robustness certificates and one against conformal prediction sets. Memory use grows only with the attack budget. Tests showed a notably larger accuracy drop than rival attacks.
Catalog record
| CREATOR | Sadegh Akhondzadeh, Soroush H. Zargarbashi, Jimin Cao, Aleksandar Bojchevski |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 87 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-08212
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
EvA: Evolutionary Attacks on Graphs Sadegh Akhondzadeh, Soroush H. Zargarbashi, Jimin Cao, Aleksandar Bojchevski Abstract 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 Ev olutionary A ttack (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 ∼ \sim 11% additional drop in accuracy on average compared to the best previous attack, revealing significant untapped potential in designing attacks. 1 Introduction Given the widespread applications of graph neural networks (GNNs), it’s crucial to study their robustness to natural and adversarial noise. In node classification, GNNs leverage the edge information to improve their performance. However, adding or removing a few edges can drastically decrease their accuracy, even below the performance of an MLP that ignores the graph structure entirely. The vast majority of adversarial attacks on the graph structure are gradient-based. However, gradient-based attacks face several challenges in this setting: (i) To tackle the original discrete combinatorial optimization problem we have to relax the domain from \{0,1\} to [0,1] ; (ii) The gradients only provides local information and cannot accurately reflect the actual loss landscape when edges are flipped (see Fig. 1 ); (iii) Similarly, the gradient only reflects the effect of flipping a single edge at a time, but the effect on the loss can be different (even opposite) when two or more edges are flipped simultaneously (see Fig. 1 ); (iv) We need a differentiable proxy loss function since the original attack objective is often not differentiable (e.g. accuracy). A common choice is cross-entropy which is suboptimal as a proxy ( Geisler et al. 2023 ) ; (v) White-box access to the model is necessary, which limits the applicability or requires surrogate models.; (vi) Defense against such attacks might carry a false sense of security by only obfuscating gradients ( Athalye et al. 2018 ; Geisler et al. 2023 ) ; (vii) Although the adjacency matrix is often sparse, the gradients w.r.t. it are not. Therefore, the memory complexity of these attacks grows quadratically w.r.t the number of nodes, for which tricks like block coordinate descent are needed ( Geisler et al. 2021 ) . These challenges suggest that we should try to directly solve the original (combinatorial discrete) optimization problem, and not to rely on differentiation. A natural alternative is search. Indeed, Dai et al. 2018a implemented a baseline genetic-based search for attacking the edges. However, their approach was not competitive with gradient-based attacks, largely due to poor design choices in the loss function and mutation strategies. While search-based attacks have been promptly forgotten since, we show that by carefully designing the components of a meta-heuristic pipeline we can outperform state-of-the-art gradient-based attacks by a significant margin. As shown in Fig. 1 [Right], EvA not only outperforms the previous method based on Genetic Algorithm, but also outperforms PRBCD, the previous state-of-the-art, by a large margin. Our model-agnostic ev olutionary a ttack (EvA) explores the space of possible perturbations with a genetic algorithm (GA) without gradient information. We avoid domain relaxation by directly minimizing the (non-differentiable) accuracy over the space of binary matrices. Our attack easily extends to other objectives. We show this by defining two novel attacks on graphs that break conformal guarantees or reduce the effectiveness of robustness certificates (see § 4 ). Importantly, this extension is automatic – we only need black-box access to the objective, making our attack adaptive Mujkanovic et al. 2023 . In contrast, gradient-based attacks for these new objectives require substantial additional effort (e.g. to tailor the right relaxations). Figure 1: We compute {\mathcal{L}}_{\mathrm{margin}}({\bm{A}}+\Delta{\bm{A}}) where \Delta{\bm{A}}={\bm{e}}_{i}{\bm{e}}_{j}^{\top}\Delta_{ij}+{\bm{e}}_{u}{\bm{e}}_{v}^{\top}\Delta_{uv} and {\bm{e}}_{i} is the i -the cannonical vector. [Left] The loss landscape is non-linear, and the gradient does not always indicate the loss direction when we flip an edge (e.g. gradient suggests decrease, but loss increases). [Middle] Due to non-convexity, the effect of flipping each edge separately (e.g. loss decreases) can differ from flipping both edges simultaneously (e.g. loss increases). This happens for many edges ( § B ). [Right] EvA does not suffer from this issue and outperforms both PRBCD and search-based attacks. Our implementation requires {\mathcal{O}}(\epsilon\cdot E) memory complexity where \epsilon is the perturbation budget, and E is the number of edges. Given more time or more memory we can increase our performance due to the open-ended nature of the search. This is a missing characteristic in SOTA attacks such as PRBCD Geisler et al. 2021 . For larger graphs where the search space is considerably larger, we apply a divide and conquer strategy that improves both PRBCD and EvA, with EvA still outperforming. In summary, we propose an evolutionary attack that supersedes SOTA attacks within global, local, and targeted regimes. Unlike gradient-based methods, EvA can use additional computational resources to perform even better. And since it does not require differentiability, it can extend to other objectives including two new targets: conformal guarantee, and certified ratio. Our results clearly show that the space of evolutionary (and more broadly search-based) attacks has a lot of untapped potential. 2 Background and Related Work Problem setup. We focus on attacking the semi-supervised node classification task via perturbing a small number of edges. We are given a graph {\mathcal{G}}=({\bm{X}},{\bm{A}},{\bm{y}}) where {\bm{X}} is the features matrix assigning a feature vector {\bm{x}}_{i} to each node v_{i} in the graph, {\bm{A}} is the adjacency matrix (often sparse) representing the set of edges {\mathcal{E}} , and {\bm{y}} is the partially observable vector of labels. Nodes are partitioned into labeled and unlabeled sets {\mathcal{V}}={\mathcal{V}}_{l}\cup{\mathcal{V}}_{u} . The GNN is trained on a clean initial subgraph {\mathcal{G}}_{\mathrm{tr}} that includes the labeled nodes. Following Gosch et al. 2024 we avoid the transductive setup ( {\mathcal{G}}_{\mathrm{tr}}={\mathcal{G}} ) since perfect robustness can be achieved there by only memorizing the clean graph during training. They show that adversarial and self training also show a false sense of robustness in that setup for the same reason. Instead, we focus on inductive learning where a model f is trained on an induced subgraph {\mathcal{G}}_{\mathrm{tr}}\subseteq{\mathcal{G}} , validated on {\mathcal{G}}_{\mathrm{val}}\subseteq{\mathcal{G}} and tested on {\mathcal{G}}_{\mathrm{test}} where {\mathcal{G}}_{\mathrm{tr}}\subset{\mathcal{G}}_{\mathrm{val}}\subset{\mathcal{G}}_{\mathrm{test}}={\mathcal{G}} . Threat model. Our goal is to find a perturbation matrix {\bm{P}}\in\{0,1\}^{n\times n} that flips entities of the adjacency matrix \tilde{\bm{A}}={\bm{A}}\oplus{\bm{P}} , where n=|{\mathcal{V}}| , and \oplus is the element-wise XOR operator. We optimize over {\bm{P}} to decrease the accuracy. For a given function f as the GNN model, and any generic loss function {\mathcal{L}} , the objective is {\bm{P}}=\underset{{{\bm{P}}}}{\argmax}\quad{\mathcal{L}}(f({\mathcal{G}}({\bm{X}},{\bm{A}}\oplus{\bm{P}}))_{\mathrm{att}},{\bm{y}}_{\mathrm{att}})\qquad s.t.\quad\bm{1}_{N}{\bm{P}}\bm{1}_{N}^{\top}\leq\epsilon\cdot|{\mathcal{E}}[{\mathcal{V}}_{\mathrm{att}}:{\mathcal{V}}]| (1) Here f(\cdot)_{\mathrm{att}} is the vector of predictions for the subset of nodes {\mathcal{V}}_{\mathrm{att}} that are under attack. In “targeted” attacks {\mathcal{V}}_{\mathrm{att}} is a singleton. To keep the perturbations imperceptible, we