EvA: Evolutionary Attacks on Graphs
Authors: Mohammad Sadegh Akhondzadeh
Soroush H. Zargarbashi
Jimin Cao
Aleksandar Bojchevski
Venue: ICLR 2026 Poster (2026)
Keywords: Adversarial Attack
Evolutionary Algorithm
graph neural network
Primary area: learning on graphs and other geometries & topologies
TL;DR: We propose an evolutionary attack for GNNs that outperforms SOTA gradient based attacks by a significant margin. We extend our attack to other non-differentiable objectives.

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 prevents 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.
EvA uses sparse representations to significantly reduce memory requirements and scale to larger graphs.
We also introduce a divide and conquer strategy that improves both EvA and existing gradient-based attacks.
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.

Published as a conference paper at ICLR 2026
EVA: EVOLUTIONARY ATTACKS ON GRAPHS
Sadegh Akhondzadeh" !
Soroush H. Zargarbashi Jimin Cao' Aleksandar Bojchevski"
1 University of Cologne, CISPA Helmholtz Center for Information Security
[akhondzadeh, zargarbashi, jcao, bojchevski] (cs. uni koeeooeennn.. de
ABSTRACT
Even a slight perturbation in the graph structure can cause significant drop in the accuracy of graph neural networks (GNNs). Most existing attacks leverage gradient information to perturb edges. This relaxes the attack's 's optimization problem from a discrete to a continuous space, resulting solutions far from optimal. also prevents 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 differentiable proxy loss. This allows to design two novel attacks that reduce the effectiveness robustness certificates and break conformal sets. EvA uses sparse representations to significantly reduce memory requirements and scale to larger graphs. We also introduce a divide and conquer strategy that improves both EvA and existing gradient-based attacks. Among our experiments, EvA shows ~ % additional drop in accuracy on average compared to the best previous attack, revealing significant untapped potential in designing attacks.
INTRODUCTION
Given the widespread applications of graph neural networks (GNNs), it's crucial to study their robustness 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 [o, 1]: (ii) The gradients only provide local information and cannot accurately reflect the actual loss landscape when edges are flipped (see Fig. I] [Left)); (iii) Similarly, the gradient only reflects the effect of flipping single edge at time, but the effect on the loss can be different (even opposite) when two or more edges are flipped simultaneously (see Fig. I [Middde)]: (iv) We need differentiable proxy loss function since the original attack objective is often not differentiable (e.g. accuracy). A common choice is proxy (Geisler et al.) 2023); (v) White-box, access to the
cross-entropy which is suboptimal 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); 3 (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. 202T).
These challenges suggest that we should try directly solve the original (combinatorial discrete) optimization problem, and not to rely on differentiation. A natural alternative is search. Indeed, Dai al. 20 8a) implemented a baseline genetic- based search for attacking the edges. However, their approach was not competitive with maddient-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 meta-heuristic pipeline we can outperform state-of-the-arr gradient-baser attacks by a significant margin. As shown in Fig. Rightt EvA not only outperforms the previous method based on genetic algorithm, but also outperforms PRBCD, the previous sfate-of-the-aee art, by a large margin. Our -gges-ag evolutionary attack (EvA) explores
"Equal Contributions, Our implementation is available the theggttuh..cm//aCtal//y

---

Published as a conference paper at ICLR 2026
Loes
Gradient
MLP
PRBCD
+
EvA
cA.(Dai
0.8
Cunrgin (A AAA)
Emariia (A (-44))
Pert Acc
0.6
1.0
7.0
0.4
0.5
0.5
6.5
0.0
0.5
0.0
10% 15% 20%
Figure 1: We compute marrgin (A + AA) where AA = e,e, Di + e.e, Aur and e; 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 GA attacks.
the space 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 reduce the effectiveness of robustness certificates (seeß | 4). Importantly, this extension is automatic, we only need black-box -ox access to the 2023). In contrast, gradient-basse attacks
objective, making attack adaptive (Mujkanovic for these new objectives require substantial additional effort (e.g. to tailor the right relaxations).
EvA requires O( F P) memory where is the perturbation budget, E is the number of edges and P is the population size. Since P is small constant, we can simplify to O E). Given more time or more memory can increase our performance due the open-ended nature of the search, unlike GeBCleG et al. (202T). 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.
To summarize our contributions: (i)
We carefully design the components of the GA, including targeted adaptive mutation strategy and a better encoding, which leads to serious improvements (~11% additional drop in accuracy on average compared to the SOTA attack and up to ~40% additional drop compared the baseline GA attack); (ii) We broaden the scope of graph adversarial evaluation by attacking post-hoc guarantees such conformal prediction and robustness certificates; (iii) To scale to larger graphs, we introduce divide and conquer strategy that benefits both EvA and gradient-based attacks; (iv) We extend our attack to support local (per node) constraints with an efficient local projection. Our results caution against over-reliance on gradient- attacks and show that search-based strategies remain powerful and practical attack paradigm.
2 BACKGROUND AND RELATED WORK
Problem setup. We focus on attacking the semi-supervised node classification task via perturbing a small number edges. We are given a graph G = (X, A, y) where X is the features matrix assigning feature vector æ, to each node v, in the graph, A is the adjacency matrix (often sparse) representing the set of edges ε, and y is the partially observable vector labels. Nodes are partitioned into labeled and unlabeled sets V = V U V.. The GNN is trained on clean initial subgraph Gtr that includes the labeled nodes. Following Gosch et al. (2024) we avoid the transductive setup (G,, 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 trained on an induced subgraph G. S G, validated on Gvat C G and tested on Grest. where Ger C Gval C Gustt = G.
Threat model. We optimize over perturbation matrix
1) that flips entries of the adjacency matrix Á = A P. where n = [V), and @ the element-wise XOR operator. For a given function f as the GNN model, and any generic loss function L, the objective is
P = arg max L(f(g(X, A P)) Marr)
s.t. 1N Se ee E V]
(1)
2

---

Published as a conference paper at ICLR 2026
Here f()) is the vector of predictions for the subset of nodes Vat that are under attack. In "targeted" attacks Vatt is a singleton. C is negative accuracy or any other objective function explained in 4 To keep the perturbations imperceptible, we assumee that the adversary can only perturb up to o = e. e- VJ edges where & [AA B] is the subset of edges between nodes in A and B. Eg. caan include more constraints like the local constraint from [ooeh et al. (2023) restricting perturbations not to increase node degrees by more than a fraction (e.g Gloc = 0.5) of their original value.
Related Work. We study evasion attacks with both global and targeted objectives, where perturbations are introduced only at test time. The goal is either to reduce the model's overall accuracy or to induce the misclassification of a specific node. Among gradient-basse 202T) and LRBCD (Gosch et al.. (024) represent the current state of the art Both attacks compute gradients of the tanh-margin loss with respect to the adjacency matrix, employing block-coordinate descent. Perturbation edges are then sampled based on these gradients. To handle local degree constraints, LRBCD incorporates a local projection step, greedily selecting edges (in descending order of gradient score) while ensuring that the constraints are not violated.
methods, PRBCD (Geisler et al.,
Beyond gradient-based methods, alternative approaches have also been explored. For example, Dai et al. 2018a) proposed a simple evolutionary attack baseline for their reinforcement learning- based method. However, these early strategies have since been surpassed by gradient-base techniques. Building on this progress, redesign key components of the search process, achieving significant improvements over prior evolutionary attacks. Moreover, our method, EvA, scales effectively to large graphs and naturally extends novel attack objectives. Other heuristic-based attacks, relying on node degree, centrality, or related metrics (Zhang et al. (0224 [023 Wang et al. [2023), have also been proposed, but they similarly fail to outperform the current state-of-the- methods. A more detailed discussion of related work can be found in S A
3 EVA: EVOLUTIONARY ATTACK
Components of EvA. As shown in Fig. gradients can be misleading which motivates to explore search-based attacks. We employ a genetic algorithm (GA) (Holland 1984) that starts with an initial population of candidate solutions that we iteratively refine. The improvement is driven by the fitness function, and the crossover and mutation operators. Here we provide a brief overview. For the detailed technical description see S D Each individual in the population specifies a set of edges to be flipped. We implement an efficient (1)) mapping from a ID index to 2D edges, while ensuring undirected flips. The filness function that evaluates each individual should correlate with the objective in Eq. 1 and provide sufficient sensitivity across candidates. For global attacks, we use the model's s accuracy on the perturbed graph. In S 4 we explore better alternatives for local and targeted attacks. We generate new candidates from two individuals via a crossover operator, which concatenates parent segments. Parents are chosen through tournament selection (Noour random samples from which the two fittest are retained). The baseline mutation operator randomly replaces each index with some probability. We design significantly better mutations below.
Sparse encoding of the attack. A simple way to represent perturbation is a boolean vector of size N2 encoding which edges are flipped. It costs O ((S)N2 space from memory where S is the popula- tion. This representation is not aware of the sparsity in A. Instead we represent each candidate a list of indices to be toggled in the adjacency matrix, we store sparse representation of P. With this we ac- count for the sparsity and reduce the complexity to ((S))-) where ó = [e- [g[Vece set V]] J[[j-co candidates in the population z E S are vectors of dimensions with each entity as an index in adjacency matrix 2 E (1.... nnn 1)/2} with n |V). Our mapping II (as discussed in $ D) is diagonal enu- meration of an upper triangular n x n matrix. For simplicity, we let the perturbation vector to contain repeated elements. During the evaluation of the vector, we transform it to a perturbation matrix Pz. with which we compute A A @ Pz. We compute all steps with sparse representation, where each candidate takes (d) space. Moreover, with this encoding, we directly enforce the global budget since the size of each individual in the population is at most the number of allowed perturbations by design.
A Accuracy vs alternative surrogate losses. To understand the effect of the loss the attack, we conducted an ablation study to compare accuracy and common surrogate objectives (cross-entrowl and margin- masgin-based loss) the fitness function in EvA. As in Fig. 2 (left), cross-entropy does not use the attack budget effectively, while margin-base loss shows to be well-correlated. Intuitively, since the goal is to misclassify as many nodes as possible, the aggregated cross-entropy loss can
3

---

Published as a conference paper at ICLR 2026
PRBCD
EvA-MG
PRBCD EVA-UM
ExA-TM
EvArAAe EVA-CE
EvA-ATM
CoraMI
60
EvA
Perturbed
0.6
0.6
D&C
10%
Pubmed
Arxiv
40
PRBCD
0%
20
0,4
0.4
0
c:
1%
5%
10%
15%
20%
1% 5%
10%
20%
5%
10%
15%
Degree Violation
Figure 2: [Left] EvA's performance with different objective functions and [Middle left] mutation strategies. [Middle right] Effect of D&C on the performance EvA for different datasets. [Right] The number of violations from local constraints by EvA, and PRBCD (fio = 0.5).
waste perturbation budget by overly focusing on already misclassified nodes, rather than maximizing new misclassifications. This effect was studied in depth by Geisler et al. (2023), which motivated them to introduce the Tanh-Margin loss which mitigates this issue. Still among all fitness functions, accuracy itself performs better. Since PRBCD uses the Tanh-Margin loss, the large gap between EvA, and PRBCD suggests that the quality of loss is not the only reason behind EvA's 's effectiveness. We hypothesise that EvA, leveraging the exploratory capabilities of GA, can explore the search space more effectively and avoid local optima, while PRBCD gets stuck.
Drawbacks. The mentioned setup is the baseline variant of EvA. Combined with cross-entropy as the fitness it is similar to a parallel and efficient implementation for Dai et al. (2018a) which is by far less effective (see Fig. I). While the baseline (with accuracy) already outperforms SOTA Fig. 2| we enhance the search by introducing better initial population and mutation function that discards edges outside of the target's receptive field.
Enhancing the search. To enhance EvA, the key insight that by restricting the search space to the receptive field of Van (instead of the entire (n - 1) edges), we eliminate less effective (or ineffective) perturbations from the search space. Perturbations that have both endpoints in the training subgraph can be easily reverted by memorization. Additionally, flipping edges outside of the receptive field of Vanz a waste of budget since they do not affect the prediction of Vatt- Similarly, we restrict the initial population to have at least one endpoint in Van.- This is easily done by randomly sampling both endpoints, one inside Vatt and one in V, then mapping the edges back to the indices via II. For larger graphs, the search space increases quadratically to the number of nodes, divide and conquer strategy by splitting Vatt and running EvA on each chunk.
apply
Targeted and adaptive mutation. Mutation is applied by selecting set of perturbation indices (uniformly at random with probability p) from the population and changing them to another index. A naive implementation (the uniform mutation (UM)), adds random indices from anywhere in the entire graph. Similar to the initialization, we define the "targeted mutation (TM)" by restricting the new mutated edge have at least one end-point in Vatt- Furthermore, when the attack succeeds in altering a node's 's label, perturbing its connections does not increase the performance anymore. Hence, we exclude the already flipped nodes from the endpoint that was restricted to Vaut- Importantly, we still allow those nodes to connect with other nodes in Vass as they can contribute to the misclassification risk of other nodes. We refer this approach as "adaptive targeted mutation" " (ATM). Remarkably, as shown in Fig. 2 (right), these modifications improve the effectiveness of EvA by noticeable margin.
Stacking perturbations. EvA requires forward pass per each candidate (each candidate of population). While maintaining the sparse representation of the graphs during all steps, we can use the remaining memory to combine i candidates in form of large graph of k parts and evaluate all easily fit the entire population in one forward pass per
in single forward pass. In practice, iteration as one large graph.
Effect of scaling. The population size has considerable impact the performance of EvA by introducing diversity among the solutions, thus increasing exploration. To observe this effect, we do an ablation study the population size and the number of iterations. For fair comparison, scale PRBCD separately by increasing the number of steps and the size of the block coordinate subspace. We exponentially increased the block size, starting from 0.5M up to 4 million Fig. Left). As
4

---

Published as a conference paper at ICLR 2026
0.8
Block sine
0.554
ATM Unifac
EsA
PXOLD
Fraual Mr
40
Acamay
1.5
425
0.6
20
0.4
2 5.7
3 4 5.7.7
Degree
Degree
Sea
Afroaddd Bachoro
Figure 3: (From left to right) Scaling performance of PRBCD over various memory and iteration budgets, the ent colors) used by EvA [left] and PRBCD effect of mutation on different resources on P Pubmed and number of forward vs performance all with 0.1%.
Figure 4: Number of perturbations (differ-
[right] to attack nodes of specific degrees. Black (NA) shows failed attacks.
shown in Fig. [middle], increasing the population size, and then increasing the number of iterations improves EvA. In contrast, PRBCD does not achieve noticeable improvement by increasing the block size or the number of training steps (Fig. 3 rleft.) This means that EvA leverages additional computational resources (either time memory) while PRBCD does not show considerable of it. As a supplement to Fig. 2. in Fig. 3) [Middle] we show that using a better mutation function (here adaptive targeted mutation) consistently enhances performance across all population sizes and outperforms the uniform approach. Finally, in Fig. Right, we compare the number of forward passes used in EvA with the number of forward and backward passes applied in PRBCD, and show their performance under approximately equal memory usage. Initially, PRBCD converges faster and outperforms EvA, but at larger scales EvA significantly surpasses PRBCD. We also compare EvA A and SOTA for wall-clock time and memory in $ D.3 showing similar results. In general, we see that EvA is more often Pareto optimal, and broader range of time- seree--mmorypppeeee performance trade-offs.
Divide and Conquer. PRBCD uses the coordinate gradient descent to scale efficiently for larger graphs. Similarly we introduce a divide-and-conquer (D&C) approach to EvA. Here instead of attacking the entire V.t.. at once, we divide it into smaller subsets and sequentially attack each subset with a budget relative to the portion of the edges connected to it. After attacking a subset, we treat the modified graph perturbations in all previous steps. At the end we re-evaluate the final graph with all perturbations combined. Our divide and conquer approach relies
starting point for the next one. The result for the final subset includes
relaxation. For a budget of 5 81 82 over set Vatt = Vi U V2, the standard attack searches in the space of (?) 6 possible perturbations aiming to decrease the accuracy over Vatt- However, with the divide and conquer approach, the attack searches
61 among (2) + (a) &2 possible perturbations each aiming to attack V1, and V/2 separately first searching optimal attack with budget 61 on V1 and then with 82 on V22 given the attack applied on V1. Therefore, D&C explores an exponentially smaller subset of the search space. This calculation for the uniform mutation, employing targeted mutation narrows the search space explored by the
- In practice we divide Vatt kice subsets (see hyper-parameters in [S E.4) Applying the D&C approach poses trade-off: in smaller spaces EvA finds better solutions, while the relaxation in D&C can lead to solutions further from optimum. As shown in Fig. (right) when the size of the graph and the budget 6 grow, adding D&C to EvA helps substantially. As in Fig. 2 (right) it improves the result for large Ogbn-Arxiv by at least ~ 8% while the same approach is ineffective for smaller Co r aML dataset. We further show that large graphs D&C similarly helps PRBCD. Indeed, applying D&C for PRBCD helps to increase the performance while maintaining the same block-size (not increasing the required memory; see D.4). A comparable block for 1-step PRBCD exceeds the memory limit. It is noteworthy that the randomized clock-coordinate computation of gradients is also relaxation.
algorithm further. Since it also reduce the choices from (n) to [
LOCAL AND TARGETED ATTACKS & ATTACKING OTHER OBJECTIVES
Local attacks. Gosch et al. (024) extend PRBCD to support additional "local" constraints where perturbation is not allowed increase the degree of node more than fraction of its original value. We need local constraints to enforce imperceptibility of the attack. For example, perturbation might increase the degree of node more than twice its original value while staying within the global
5

---

Published as a conference paper at ICLR 2026
budget. Therefore, even within the global budget the structure of the graph (and therefore graph's structural semantics) can change drastically. They introduce the LRBCD attack which adds a local projection to PRBCD. In short, they sort edges in decreasing order of probability (gradients), and iteratively add perturbations while the local constraint for both end-points of the modified edge is not violated. This continues until the global budget is exhausted. Even without enforcing this restriction, as shown in Fig. 2 (right) EvA introduces fewer degree violations compared to PRBCD, meaning that the perturbations added by EvA are more spread-out in the graph. We apply local projection to EvA similar to LRBCD. Here, instead of using gradients for ranking. we use the frequency of the edge within the current population. We define s(e) Eses I[c E s|/|S| + u as the frequency score where u is small uniform random value in [0, 0.05J. Here is added to break ties and introduce additional randomness, and S is the population at the current iteration. Our insight is that if an edge appears frequently within the population, it is likely to be useful for an attack, increasing the chance of candidates containing it to be selected as elite. After our local projection all constraints are guaranteed be satisfied. For more diversity at initial iterations, we apply a random projection removing edges with probability proportional to total degree violations both sides. We apply this random removal for (warm iterations (a hyper-parameter discussed in [ E.4).
Node-targeted attacks. Here the objective is to misclassify a specific node with as minimal change to the structure as possible. Using EvA with the global setup does not work in this case. On a single node the accuracy has only two values 0 or 1 small changes in the solution do not result in (even minor) changes in the fitness score. With the 0-1 accuracy objective, random search and GA are practically equivalent there is indication of what combination of edges closer to breaking the prediction of a particular node- - all non-successful combinations are equally evaluated with Instead we use the proxy tanh-margin loss as the fitness function. This loss function changes as we perturb the receptive field of the targeted node. Note, for general (non-targeted) attacks the banh-margin loss improves performance over the cross-entropy loss, however, using accuracy (for larger Vatt) ) as fitness is slightly better as shown on Fig. 2 (left). Fig. 4 compares EvA, and the state-of-the art attack PRBCD on targeted attacks.
Other objectives. For non condiifferentible objectives (e.g. accuracy), maadient-basede attacks need a differentiable surrogate approximating it. As discussed in | 3] for accuracy (common setup) several works proposed various surrogates. This is similarly challenging to propose gradient- based attacks for novel objectives that are complicated and include several non-differentiable components (e.g.. quantile computation or majority voting from Monte Carlo samples). Since our method nullifies the need for information from gradients, we can easily optimize for novel complex objectives as long as they are sensitive to small changes in the search space. We define three new attacks on graphs: reducing the certified ratio of a smoothing- -baed model, decreasing coverage, and increasing the set size of conformal sets. A detailed explanation of randomized smoothing- -bsedd certificates and conformal prediction, which underpin the certified ratio objective and conformal prediction, is provided in A.I and IS A.2 respectively.
A Attacking sooothing--asedd certificate. Assuming the certified ratio is a notion of a trustworthy prediction, one possible adversarial objective is to reduce the number of nodes that are certified (a.k.a. certified ratio) while maintaining the same clean accuracy. While the operations include non-differentiaale steps we can directly set the certified ratio (fraction of nodes that are certified within a determined threat model) as the objective of EvA. Whether node is certified reduces to whether the smooth classifier returns a probability above p where min g(x) 2 0.5 constrained to g(x) = P. Many seaoothing-bbssee certificates are computed at canonical points (they are only a function of probability not the input) and they are non-decregsnng to P. Hence, we find p via binary search. Thus, our objective is to decrease the number of vertices with smooth probability above p. A naive implementation of EvA for this objective is to compute the certified ratio given new MC samples for each candidate. This increases the runtime of our algorithm by a factor of nMc, as each perturbation requires TMC forward passes. Inside the attack, statistical rigor is not crucial. Therefore, we employ an efficient sampling strategy where we start with initial samples from clean A. and for each perturbation, we only resample for the edges in À A A. We use the stacked inference technique (see [ 3) MC samples which ultimately reduces the computation to one inference per each perturbation Á.
Attacking conformal prediction. A common threat model for CP is to decrease the empirical coverage (far from the guarantee) by perturbing the test input. We propose similar attack where the
6

---

Published as a conference paper at ICLR 2026
adversary changes the edge structure of the graph in order to decrease the coverage. This process is again not directly differentiable (for steps like computing the quantile and comparison of values) which is not problem for EvA. In experimental setup, the defender calibrates subset of Vu (besides the test, this is the only set with labels unseen by the model). Assuming that the unlabeled and test nodes are originally exchangeable (node-exchaggeabllity)) the conformal guarantee is valid in the inductive setup upon recalibration on the clean graph. By perturbing the edge structure we can easily break this guarantee. Therefore our objective is change the edge structure such that the coverage is minimized. Intuitively, this requires maximizing the distribution shift between the test and calibration scores. As we know that the calibration set is an exchangeable (random) subset of Vu. we set the entire V., as the calibration set during the attack. Due to exchangeability we expect similar effect from our perturbation for any random subset as well (Berti and Rigo, 1997). Finally, the objective is to decrease the coverage over Vatt given V. as the calibration set. To the best of our knowledge, so far this is the only adversarial attack on the graph structure to break conformal inductive GNNs. Similarly, by changing the objective to the negative average set size, we can attack the usability of prediction sets (see Fig. 60.
random
EMPIRICAL RESULTS
With our empirical evaluations we show that current gradient-based attacks are still very far from optimal since EvA outperforms them by a notable margin. EvA inherently results in attacks with a smaller local change in each node's degree (even without posing local constraints
riight]. And further we can apply EvA to attacks with local constraints as well. With divide and conquer, EvA is able to scale to larger graphs (e.g. Ogbn -arnv- and outperform SOTA for those graphs as well. With the black-box nature of the attack we easily extend the score of EvA to novel objectives introducing the first attack to reduce the certified ratio or break conformal sets on graphs.
Experimental setup. We evaluate EvA on com- mon graph datasets: CoraML (McCallum et al. 2004), Citeseer (Sen et al. 2008), and Pubmed (Namata et al.] 2012). Shchur et al. (2018) show that GNN evaluation is sensitive to the initial train/val/test split. Therefore, averaged our re- sults for each dataset/model over five different data splits. In contrast with common GNN attacks. Gosch iet al. (2024) shows that the transductive setup carries a false sense of robustness. In other words, trivially one can gain perfect robustness just by memorizing the clean graph which is available before the attack; models with robust and self-training also show how to exploit this flaw. Following them, we report our results in inductive setting. We divide graph nodes into four subsets: training, validation, and testing, each with 10% of the nodes and we leave the remaining 60% as unlabeled data. Following Lingam et al. (2023), we sample the train, validation and test nodes in exchangeably since it provides more realistic setup compared to commonly used methods, such as sampling for training and valida- tion with the same count for each class (i.e. stratified sampling). For completeness, in C we compare at- tacks in the transductive setup and various sampling approaches. In all cases again EvA shows more effective attack. Further information about the model and hyperparameters are in $
Table 1: Performance of different attack meth- ods under varying budgets Cor aML dataset.
Attack
0.01
0.02
0.05
0.10
0.15
DICE
80.93
80.93
80.78
80.57
80.07
PGA
79.58
76.92
70.94
64.62
60.46
PGD
78.22
75.37
67.18
59.14
53.09
GRPCD
78.07
75.08
66.76
58.29
$4,80
PRBCD
76.44
73.17
66.48
58.51
52.67
EvA
74.80
68.97
52.95
41.99
37.65
Table 2: Performance of different defense mod- els under various attack strengths on CoraML.
Defense
Attack
0.01
0.02
0.05
0.10
GCNSVD
EvA
0.70
0.64
0.54
0.41
PRBCD
0.76
0.75
0.73
0.70
GNNGuard
EvA
0.71
0.67
0.55
0.45
PRBCD
0.74
0.72
0.70
0.66
GNNJaccard
EvA
0.76
0.74
0.64
0.57
PRBCD
0.76
0.74
0.70
0.65
Robust-GCN
EvA
0.75
0.70
0.59
0.52
PRBCD
0.77
0.73
0.68
0.63
Soft-Median
EvA
0.75
0.72
0.69
0.62
PRBCD
0.77
0.76
0.73
0.68
A Attacking vanilla and robust models. As shown in Fig. 3 and extensively in $ C EvA outperforms the SOTA attack PRBCD by a significant margin consistently across various datasets and models (vanilla and robust). Interestingly, budget e ~ 0.05. EvA drops the accuracy below the level of the MLP model. This is a condition where the model leveraging the structure works worse than model that completely ignores edges.
show that on many vanilla and robust models, for very small
7

---

Published as a conference paper at ICLR 2026
MLP
LRBCD
EvALocal GA-(Dai et ak
I. EvA D&C
+ PRBCD
0.65
PRBCD
EvA
Port Ace
0.60
0.6
0.7
0.55
0.4
0.6
0.50
0.4
6:
1%6
516
10%
15%
20%
198
396
10%
15%
20%
1% 516
10%6
15%
20%6
116
556
10%
13%
Figure 5: (Left right) Performance on CoraML Vanilla GCN, adversarially trained GCN using PRBCD, Soft-Median-GDD model. The right-most figure is GCN on
The SoftMedian model seems show inherent robustness to both EvA and PRBCD. Therefore, to break the model below the accuracy of MIP, we require 2 0.2 perturbation budget. Even in the SoftMedian model, attack is significantly more effective in comparison to PRBCI. Table compares EvA with other attacks, showing that our attack outperforms all previous methods. We also provide additional results on different defense mechanisms Table 2 which demonstrate that our attack can break them all. We also provide additional result with adversarial training. Table 14 C compares attacks against models with different adversarial training. We study the characteristies of the perturbed edges in D.2
Scaling larger graphs. In Fig. 5 we also show that the EvA applied with our divide and conquer approach outperforms PRBCD for Ogbn-Arx Arxiv dataset. Interestingly similar divide and conquer approach can significantly improve PRBCD as well; while still EvA is more effective. In D.4 we compared PRBCD with block size 3M, 10M, alongside PRBCD and EvA with divide and conquer in a fair comparison. Notably PRBCD with the highest block size fitting in one GPU still significantly less effective compared to any of the attacks combined with D&C.
Additional datasets. To
show that EvA generalizes be- yond citation graphs, in TTa- ble 3 we compare it with PRBCD on two co-purchase graphs, the AMAZON-PHOTE and AMAZON-COMPUTERR graph (Shchur et al.) 2018).
Table 3: Performance on non-citation graphs.
Dataset
Attack
0.01
0.02
0.05
0.10
photo
PRBCI) 84.28 6.9
81.12
# 1.45
75.86 + 1881
71.58 + 1.80
EvA
80.43 + 1.47
77.99
+ 2004
72.73 + 1.90
67.01 = 1.76
PRBCD
77.28 0.68
73.56
0.55
66.92
0.63
61.99
# 0.59
computers
EvA
72.94 126 70.10 + 185
65.70
2899
60.13 3772
EvA is still better.
Local attacks. Similarly, shown in Fig. and $ C EvA is consistently better than LRBCD In discussed that we apply local projection as a mutation function. Interestingly as in Fig. 16 (right) without local projection, EvA results in less violations of the local constraint.
Targeted attack. We perform targeted attacks on each node separately, with varying budgets from to a maximum of 10 edges, until the prediction changes. We diseussed in | 4 that here used tanh-Margin proxy loss since accuracy on one node not sensitive to small changes. Fig. 4 compares EvA and PRBCD in targeted attack. Our results show that PRBCD performs better with a budget of one, but is outperformed by EvA for budgets of two and higher. For instance, on the CoraML dataset PRBCD fails modify 16 nodes with a maximum of 10 changes (NA, black), whereas this number is reduced to only 2 nodes for EvA. This result is expected due to the combinatorial nature of the problem: for budgets up to two, a greedy approach can find the optimal solution, but as the budget increases beyond three, the problem becomes significantly more complex. This is also in line with our first motivation that the gradient ignores the interaction effect of flipping multiple edges simuitancously. Fig. [middle] is an instance when the gradient direction individually has the same direction, but the loss when flipping both is in the opposite direction. This effect can become even more problematic when one flips more edges.
Atacking novel objectives. In Fig. 6 (mid right and right) we performance of EvA with the objective to reduce the certified ratio. The plots for certificate A (mid-right) with (p+ 0.001, p_ 0.4), and X (right) with (p+ = 0.01, p_ = 0.6) with sparse smoothing (Bojchevski et al. (020). Here pt, and p- Bernoulli parameters of flipping zero In both plots report the
8

---

Published as a conference paper at ICLR 2026
GCN
Perturbed
Cleun
MLP
Smooohh Acc
+
Cerl Raio
+
Cent Ace
(Ndv -dained GCN
Ceriifictiio
Certification
0.8
Coverage
Set Size
0.8
0.8
2
0.6
0.6
0.6
C.2 18855 10SS 58200
C.2 15855 10505R2205
15
15%
C.
10%
155
Figure 6: (From left to right) conformal coverage, and conformal size on vanilla and adversarially trained GCN. The certificate attack for certified ratio on A and X evaluated on GPRGNN adversari- ally trained using PRBCD, All plots are for CoraML.
result for Bo,3 which means additions and 3 deletions. While we aim to decrease the certified ratio, a direct outcome is that the certified accuracy drops. For 5% budget, the certified accuracy drops below MLP. MLP is a baseline model with full robustness discards the adjacency information completely). While reducing the certified ratio, interestingly the smooth model's accuracy remains the same. Hence, evaluating the model on a holdout labeled set does not reveal that the input graph is attacked. We report the first structure attack conformal GNN. As shown in Fig. 6 (right) the coverage drops quickly as we increase the perturbation budget. As expected, in adversarially trained model, observe slower decrease in the empirical coverage. Alternatively in Fig. 6 (middle) we increase the average set size since showing that that both vanilla and robust models are vulnerable to this attack.
edge perturbations (since
inductive
Ablation study on the effect of our different GA extensions. To emphasize the effects of our simple yet effective enhancements, we provide the following ablation studies. In Table show the effect of each enhancement individually and then together (EvA) on the CoraMI, dataset. Furthermore, in Table 5| we report the effect of our sparse encoding (SE) and D&C on the larger Ogbn-Arxi v dataset. As shown, all of our simple enhancements provide a significant effect (individually and jointly).
Table The effect of our adaptive targeted muta- tion (ATM) and the fitness function on CoraML.
Table 5: Effect of our sparse encoding and
D&C on the large Ogbn-Arxiv dataset.
0.01
0.02
0.05
0.10
0.15
0.01
0.02
0.05
0.10
Dai al.
80.71
80.28
78.86
76.86
75.08
Dai al.
0OM
00M
00M
00M
ATM
78.50
76.65
72.52
68.75
65.33
Dai et al. + SE
69.79
69.56
68.81
67.77
Lace
75.08
69.39
54.02
48.32
44.41
EvA
66.86
66.80
65.18
63.51
EvA (+ both)
74.80
68.96
52.95
41.99
37.65
EvA + D&C
61.08
56.31
51.60
47.56
CONCLUSION
We introduce EvA, an adversarial attack on the graph structure using a genetic algorithm. Unlike bradient-based methods, our black-box approach directly optimizes the adversary's ' objective (c.g. the model's accuracy). This flexibility allows for more complex adversarial goals we demonstrate successful attacks that decrease certified robustness and degrade conformal prediction performance. To ensure scalability, we propose an efficient encoding that ties memory complexity to the perturbation budget and divide-and-conuuee strategy that improves performance on large graphs for both our method and baselines like PRBCD. We also show that due to the open-ended characteristic of the search, for more computational resources (time and memory) we can always improve our results. Given the significant decrease in the model's 's accuracy by applying EvA, highlight that even SOTA gradient- based attacks are far from optimal. Our main message is that search-based attacks are underexplored yet powerful shown by results.
Limitations. We use an off-the-shed genetic algorithm. Surely, there is room for designing search algorithms specific to the domain of the problem beyond our extensions, even hybrids of gradient and evolutionary search. EvA uses many forward passes through the model which can be unrealistic in some attack scenarios. We leave the design of further query-efficient variant for the future.

---

Published as a conference paper at ICLR 2026
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In International conference on machine learning, pages 274-283. PMLR, 2018.
Patrizia Berti and Pictro Rigo. A glivenko-cantelli theorem for exchangeable random variables. Statistics & probability letters, 32(4)3385-39, 1997.
Alcksandar Bojchevski, Johannes Gasteiger, and Stephan Günnemann. Efficient robustness certifi- cates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In International Conference on Machine Learning, pages 1003-1013. PMLR, 2020.
Heng Chang, Yu Rong, Tingyang Xu, Wenbing Huang. Honglei Zhang, Peng Cui, Wenwu Zhu, and Junzhou Huang. A restricted black-box adversarial framework towards attacking graph embedding models. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 3389-3396, 2020.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network, 2021.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang. Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. In International conference on machine learning. pages 1115-1124, PMLR, 2018a.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. International conference on machine learning, pages 1115-1124. PMI.,, 2018b.
Simon Geisler, Tobias Schmidt, Hakan Sirin, Daniel Züigner, Aleksandar Bojehevski, and Stephan Günnemann. Robustness of graph neural networks at scale. Advances in Neural Information Processing Systems, 34:7637-7649, 2021.
Simon Gcisler, Tobias Schmidt, Hakan Şirin, Daniel Zügner, Aleksandar Bojehevski, and Stephan Günnemann. Robustness of graph neural networks at scale, 2023.
abs/ /t//2210.. 2110.14003.
Lukas Gosch, Simon Geisler, Daniel Sturm, Bertrand Charpentier, Daniel Zügner, and Stephan Günnemann. Adversarial training for graph neural networks: Pitfalls, solutions, and new directions. In 37th Conference on Neural Information Processing Systems (Neurips), 2023.
Lukas Gosch, Simon Geisler, Daniel Sturm, Bertrand Charpentier, Daniel Zügner, and Stephan Günnemann. Adversarial training for graph neural networks: Pitfalls, solutions, and new directions. Advances in Neural Information Processing Systems, 36, 2024.
John H Holland. Genetic algorithms and adaptation. Adaptive control of ill-defined systems, pages 317-333, 1984.
Mingxuan Ju, Yujie Fan, Chuxu Zhang, and Yanfang Ye. Let graph be the go board: gradient-fres node injection attack for graph neural networks via reinforcement learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pages 4383-4390, 2023.
Vijay Lingam, Mohammad Sadegh Akhondzadeh, and Aleksandar Bojchevski. Rethinking label poisoning for gnns: Pitfalls and attacks. In The Twelfth International Conference on Learning Representations, 2023.
Andrew McCallum, Kamal Nigam, Jason D. M. Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3:127-163, 2004.
Jiaming Mu, Binghui Wang, Qi Li, Kun Sun, Mingwei Xu, and Zhuotao Liu. A hard label black-box adversarial attack against graph neural networks. In Proceedings of the 2021 ACM SIGSAC Conference Computer and Communications Security, pages 108-125, 2021.
10

---

Published as a conference paper at ICLR 2026
Felix Mujkanovic, Simon Geisler, Stephan Günnemann, and Aleksandar Bojchevski. Are defenses for graph neural networks robust?, 2023. URL
abaaabss////0 13694
Galileo Namata, Ben London, Lise Getoor, and Bert Huang. Query-driven active surveying for collective classification. 2012.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Collective classifcation in network data. 2008.
Oleksandr Shchur, Maximilian Mumme, Alcksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:181..05866 2018.
Lichao Sun, Yingtong Dou, Carl Yang, Kai Zhang. Ji Wang. Philip S. Yu, Lifang He, and Bo Li Adversarial attack and defense graph data: A survey. JEEE Transactions Knowledge and Data Engineering, 35(8):7693-771, 2023, doi: 10. 10.1199/KDDE.222.222222222
Yexin Wang, Zhi Yang. Junqi Liu, Wentao Zhang, and Bin Cui. Scapin: Scalable graph structure perturbation by augmented influence maximization. Proc. ACM Manag. Data, 1(2), June 2023.
doi: 10.1 10.1145/3589291 URL httptt::///a/t http://ooooo/g/.o/////o 1145/35892999
Marcin Waniek, Tomasz P Michalak, Michael J Wooldridge, and Talal Rahwan. Hiding individuals and communities in social network. Nature Human Behaviour, 2(2):139-147, 2018.
Kaidi Xu, Hongge Chen, Sijia Liu, Pin-Yu Yu Chen, Tsui-Wei Weng. Mingyi Hong, and Xue Lin. Topology attack and defense for graph neural networks: An optimization perspective. arXiv preprint arXiv:1906. 04214, 2019.
Soroush H Zargarbashi and Aleksandar Bojchevski. Conformal inductive graph neural networks. arXiv preprint arXiv:2407.09173, 2024.
Chenhan Zhang, Shiyao Zhang. James J. Q. Yu, and Shui Yu. Sam: Query-efficient adversarial attacks against graph neural networks. ACM Trans. Priv. Secur, 26(4), November 2023. ISSN 2471-2566. doi: 10.1 145/361 1307. URL
Jianfu Zhang. Yan Hong, Dawei Cheng, Liqing Zhang, and Qibin Zhao Hierarchical attacks on large- scale graph neural networks. In ICASSP 2024 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 7635-7639, 2024. doi: 10. 10.110//AASS444485. 2024. 10448076.
Guanghui Zhu, Mengyu Chen, Chunfeng Yuan, and Yihua Huang. Simple and efficient partial graph adversarial attack: A new perspective, 2023. 07834
org/8b3/23088
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD international conference knowledge discovery & data mining, pages 2847-2856, 2018.
Daniel Zügner, Oliver Borchert, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on graph neural networks: Perturbations and their patterns. ACM Transactions on Knowledge Discovery from Data (TKDD), 14(5):1-31, 2020. 2020.

---

Published as a conference paper at ICLR 2026
A SUPPLEMENTARY TO RELATED WORK
We focus on evasion attacks where perturbations are made after the model's training. Based on the domain, (evasion) attacks can be further be categorized into global (aiming to flip the prediction of subset of nodes) and targeted attacks (aiming at a single node). Our attack applies on edge-structure
similar to Xu et al. 2 Zügner et al.] (2018); Geisler et al. (2023 2021); Goochh et al. (2024). Orthogonal to this scope, various other graph attacks are proposed in the literature including node- injection attacks (Ju et al. 2023), poisoning (Zügner et al. 2020; Lingam et al., 2023 Zügner et al.) 2018), and attacking attributes (Zügner al., 2018). Inspired by techniques used continuous data, Xu et al. (2019); Zügner et al. (2018); Geisler et al. (2023) utilize gradients to approximate perturbations inherently discrete edges. As the adjacency matrix
grow significantly larger than images, applying a PGD-like attack becomes challenging for larger graphs. To remedy that Geisler et al. (2021) proposes block-coordinate computation of the derivatives, and Gooch et al. (2024) applies a greedy projection to apply local constraints.
reinforcement learning to refine their attack and disrupt the learning process of GNNS 8 Sun et al. (2023). They also introduce a genetic algorithm attack as a baseline: however, they did not design the components of GA carefully. In [ we design GA components (mutation, local projection, etc) which outperform recent gradient based attacks. Recently new attacks relying on heuristics such as node degree, centrality, etc have been proposed (e.g. Zhang Wang et al. (2023)), however they don't 't outperform the SOTA.
Orthogonally, Dai al. (2018b)
et al. (2024) 2023);
Gradient-based attacks. common class of attacks compute the gradient of the objective w.r.t. A. This requires a relaxation on the domain of A from (0, 1 _ to [0, 1|mxn. For non-differentiable objectives like accuracy differentiable surrogates like the categorical cross entropy or tanh-margin (Geisler et al.] (2023) are used instead. The algorithm is to iteratively compute the gradients and update the perturbation matrix. Finally, based on the continuous perturbation matrix edges are either sampled or rounded to the binary domain.
Black- Box attack. The literature on black-box attacks on graphs remains relatively underexplored. Some existing works focus poisoning attacks (Chang et al. 2020). Other studies, such as Waniek et al. (2018) and Xu et al. (2019). propose heuristic attacks based on the graph's 's topology. but their performance is significantly lower than that of white-box methods like PRBCD. Mu al. (2021) approximate gradients by measuring changes with small perturbations, but even under ideal conditions, their method can at best match the performance of PRBCD, which directly utilizes exact gradients. Furthermore, their approach does not scale well to graphs with even few thousand nodes.
A.1 RANDOMIZED SROTHINGG-ASSEE CERTIFICATES
robustness certificate guarantees that the prediction of the classifier remains the same within a specified threat model. For any black-box model, one way obtain such guarantee is through randomized smoothing. A smoothing scheme & is a random function mapping an input x to nearby point x' (e.g. additive isotropic Gaussian noise x' <(x) x + E, where ~ (O, o²I) I) for images). The smooth classifier is defined as the convolution of the smoothing scheme and the black- box classifier g(x)= Pr[f(x + y) majority vote or the probability that the classifier predicts the top class for randomized x' ~ {(r).. Regardless of the baseline classifier f. smooth classifier changes slowly around xe and allows us to bound the worst-case minimum of the smooth prediction probability within B. For radius around æ in which the minimum g(ă) remains above 0.5, we can certify that the smooth model returns the same label (see [S Dor further details). In many smoothing schemes, exact computation of the smooth classifier is intractable. The probabilistic computation of it is also expensive as it involves many Monte- Carlo (MC) samples and later accounting for finite sample correction.
A.2 CONFORMAL PREDICTION
Instead of label prediction, conformal prediction (CP) returns prediction sets that are guaranteed to include the true label with adjustable 1 - a probability. This post-hoc method treats the model as black- box and requires only a calibration set of labeled points whose labels were not used during model's 's training. CP is applicable in both inductive and transductive Graph Neural Networks (GNNs) under the assumption of code-exchangeability (Zargarbashi and Bojchevski 2024). To compute
12

---

Published as a conference paper at ICLR 2026
prediction sets need to compute quantile from the set of true calibration conformity scores and compare the scores (e.g. softmaxes) of the test node to the quantile threshold. For i.i.d. data (e.g. images), after computation of the quantile, the task of decreasing the softmax score towards 0 aligns with the goal of decreasing the same value below a conformal threshold (which is by definition above 0). In graphs however this task is more complicated since calibration and test nodes communicate with message passing.
B ISSUES WITH GRADIENT-BASED METHODS
To motivate the introduction of search-based method, we first need to understand the shortcomings of using gradients for optimizing the discrete space of the adjacency matrix. Therefore, we study how the margin loss Mmariin changes when perturbing the adjacency matrix A by flipping edges. The perturbation is defined as
AA ee + euc,.uer Aues
where is the i-th canonical basis vector, and Aij. Aue E {-1,+1} denote edge additions or removals. This formulation allows us examine the combined effect of flipping two edges simulta- neously. To analyze these effects, we introduce continuous interpolation parameter a E [0. 1], and compute Lmargin + AAA). This corresponds to partially adding or removing the selected edges, giving smooth trajectory from the original graph (a 0) to the fully perturbed graph (a 1). By searching over edge pairs, we obtain the loss landscape associated with individual and joint edge flips. Finally, we filter out those edge pairs that exhibit non-additive behavior: cases where flipping both edges together leads to qualitatively different outcome compared to flipping either edge individually.
We highlight two main problems with gradient-based methods. First, the gradient is local measure, since it quantifies the behavior of the function under infinitesimal changes. However, we are interested in the behavior of the function when flipping edge in the discrete space {0, 1), e.g. from to 1. So, flipping an edge could increase the loss even though the gradient suggests that the loss would decrease (and the other way around). This issue also discussed and illustrated in Zügner al.) (2018) (see their Fig. 4). Second, even if we assume that the gradient correctly indicates the effect on the loss, still only reflects the impact of individual changes and ignores the effects of interactions between edges. There are cases where flipping each individual edge would suggest certain direction of change in the loss (e.g. increase), but flipping both edges together would reverse the direction (e.g. decrease).
We designed an experiment to demonstrate that these phenomena are not rare. Since the search space is very large, we start with specific node and then randomly sample towards the other side of its edges. Specifically, we are looking for the edges (i,j) and (i, v) with и = i. We chose this approach because it ensures that the changed edge remains within the first-hop neighborhood of the node. Since our GCN is a two-layer network, the probability that this edge interacts with the two-hop neighborhood of the graph also increases. We found several cases of these two events for each node in the CoraML dataset. Fig. 7 visualizes a random subset these cases based on Tanh-Ma r rg n loss. The same phenomena also occurs with Cross Entropy loss. Fig. visualizes random subset of these cases using Cross -ett loss
C SUPPLEMENTARY EXPERIMENTS
Transductive Setting. In we argued that transductive setup carries false sense of robustness. In this setup, trivial robustness can gained just by memorization of the clean graph (Gosch et al.) 2024). For completeness, here report the results in the transductive setup well. As in Table EvA outperforms SOTA consistent with other experiments in the inductive setup.
Stratified sampling. Although unrealistic, in Table 7| compare attacks in case the models trained train/val/test sampled with the same number of nodes across different classes. Consistent with other results, EvA shows be better here well.
13

---

Published as a conference paper at ICLR 2026
Figure 7: In some the gradient fails measure the effect of flipping edge the
Tanh -Mrggin loss. Flipping edges individually vs. jointly has a different effect on loss.
Figure 8: In some cases the gradient fails measure the effect of flipping edge the Cross-Entrope loss. Flipping edges individually vs. jointly has a different effect on loss.
C.I INDUCTIVE SETTING, NON- STRATIFIED SAMPLING
Vanilla models. Here, present additional results specifically for the inductive setting. With the discussion in 5 our main experimental setup is for inductive GNNs. In this section, we detail the effectiveness of our method compared to other approaches. We show the results for CoraML,
Pubmed, and Ci teseer datasets and vanilla models in tables 9 TO 11 T2 and For each dataset we compare our attack with SOTA on four models: GCN, GAT, APPNP, and GPRGNN. We further compare the local variant of EvA with LRBCD under local-degree constraint for GCN, and GPRGNN.
Models with robust training. Table 14 compares EvA and SOTA for models training with robust training. During training of these models, we use an adversarial attack at each step to attack Guz- and then retrain the model the adversarially perturbed graph. The robust budget (Crobust) for adversarial attack during training was 0.2. This process repeats in each epoch of training until the model converges. Gosch et al. (2023) shows that models with adversarial and self training carry
14

---

Published as a conference paper at ICLR 2026
Table 6: Classification accuracy (%) on the CoraML dataset in the transductive setting under adversarial attacks. Results are reported for two GNN models subjected to three different attack methods across varying perturbation budgets c. Training, validation, and test sets are non-stratified.
Model
Attack
0.01
0.02
0.05
0.10
0.15
0.20
LRBCD
1.52
77.66-1.84
72.61
65.8441.44
60.80+1.88
56.86+1.92
GCN
77.26 77.26 PRBCD 19.48
71.85+1.80
65.4941.73
60.49 10.49:2.22
56.07
EvA 17.88
+4.12
65.68 1.97
42.31
58.72
57. 57.41
LRBCD
79.2443.04
77.09_3.22
71.6644.44
62. 62.7447..2
55.01
49.04.15.66
GPRGNN PRBCD 78.67 13.20
75.86
3.69
69.83
15.09
62. 02.15 12.1547..7
55.15
50.13 13.663
EvA
76.53 13.46
72.74
4.53
63.78 16.19
56.83 19.98
53.00
50.04_15.58
Table 7: Classification accuracy (%) on the CoraML dataset in the inductive setting under adversarial attacks. Results are reported for two GNN models subjected three different attack methods across varying perturbation budgets Training, validation, and test sets are stratified.
Model
Attack
0.01
0.02
0.05
0.10
0.15
0.20
LRBCD
80.00
77. 77.43
71.43
65.50
61.21
57. 57.6444.54
GCN
PRBCD
78.71
75.29 43.42
67
67.86-3.43
59.50
53.00
48.43
EvA
77.00
71.36 =3.29
54.36 .4.73
44.29 +3.28
40.86 +3.73
37.29 13.73
LRBCD 76.21 17.94
13.14... 73.14.7.88 17.88
66.07 11.50
60.79 111.7
56.43 12.44
112.6
GPRGNN PRBCD
74.36
70. +9.96
63.79
56. 411.14
49.29411.41
45.07+11.01
EvA 71.86+10.37
65.00+11.44
50.14
41.79+14.02
37.21
35.21
false sense of robustness in transductive setup, therefore same as other experiments we evaluate in inductive setup. Similar vanilla models, EvA outperforms all previous attacks.
C.2 COMPARING OUR METHOD WITH OTHER ATTACKS
In the main paper, we mainly focus on comparing EvA with PRBCD since is the SOTA white-box attack. Here, we provide more comprehensive comparison with other attacks including DICE (Zügner et al. 2018), FGSM (Xu et al. 2019), PGD (Zügner et al. 2018), and GRBCD (Geisler et al.
2023). We compare all these methods on the CoraML and Pubmed dataset in Fig. shown, EvA outperforms all other attacks by significant margin.
Table 15 As
C.3 OGBX-ARXIV DATASET
To show the scalability of our attack on larger graphs, we present results on the large Ogbn Ogbn-Arxi v dataset. We compare EvA and PRBCD on the same setup other experiments. In the main paper and $ D.4 we used arxiv with divide and concur and show it can outperform PRBCD. Further we propose two other setups where the attack more realistic: (i) Smaller perturbation budgets: perturbing the Ogbn-Arxiv dataset with the same budget as smaller graph like aMr is unrealistic. Therefore we can decrease e, by one order of magnitude and evaluate both methods on e E (0.1%, 0.5%, 1.0%). The results for these budgets are summarized in Table 16) (ii) Simialrly another realistic setup is that on a large graph, the adversary can access a smaller subset of control nodes (e.g. 1000 nodes) with the objective to perturb set of target nodes. As an example in social network, attacker could purchase 1,000 user accounts and use them to influence the performance of other subgroups. Here, randomly sampled 1 1.000 nodes control and 1,500 nodes target for 5 rounds. We compared EvA without D&C and PRBCD and reported the average results in Table 17 Our method outperforms PRBCD in this scenario as well.
15

---

Published as a conference paper at ICLR 2026
Table 8: Classification accuracy (%) on the CoraML dataset in the inductive setting under adversarial attacks. Results are reported for four GNN models subjected to two different attack methods across varying perturbation budgets c. Training, validation, and test sets are non-stratified.
Model
Attack
0.01
0.02
0.05
0.10
0.15
0.20
APPNP
EvA
16.65 1.32
11.44
56.51
49.32
44.77 22.04
41.42.:1.41
PRBCD
78.65-0.99
75.30
68. 68.7541.22
61.57:1.65
55.44=1.58
49.9642.42
EvA
64.20.1.88
58.51 1:2.45
40.99 +1.60
15.30
9.40
8.11
GAT
PRBCD
70.07 -2.82
66.55
58.58
49.6116.55
39.86_6.78
36.9447.09
GCN
EvA
74.80+1.50
68.97 11.58
52.95
41.99
2.00
37.65
35.37+2.38
PRBCD
76.44_..64
1..19
66.4812.13
58.51 11.77
52.67 2.00
1..19.2200
GPRGNN
EvA 72.53 14.11
66.83
14.54
11.53
42.21
8.52
37.01
19.83
34,52 19.83
PRBCD
74.95
71.67
12.76
64.84
57.94
53.24
5.20
48.68 16.52
Table 9: Classification accuracy (%) the CoraML dataset in the inductive setting under adversarial attacks. Results are reported for two GNN models subjected to five different attack methods across varying perturbation budgets e. Training, validation, and test non-stratified.
Model
Attack
E
0.01
0.02
0.05
0.10
0.15
0.20
EvA
74.80
68.97 +1
52.95 1.91
41.9942.06
37.65
35.37 $5.37_2..3 22.38
EvaLocal Local
75.0941.70
69.8211.96
60.21
56.0911.93
54.1612.48
52.88
GCN
LRBCD
78.51+1.56 75.94+1.54
71.10+1.16
64.41+1.65
60.14+1.73
57.37=1.45
PRBCD
76.44+1.61 73.17+1.39
66.48+2.13
58.51+1.77
52.67
47.19
PGA
79.58.11.61
76.92.1.73
1..94
64.6211.92
60.46
57.5412.46
EvA
72.53
66.83
51.53
42.21 18.52
37.01
34.52
EvaLocal
73.3143..0
67.2644.11
58.2947.96
53.38+11.42
51.10412.66
49.96413.68
GPRGNN
LRBCD
77.51+1.81
74.80+1.41
68.83+1.90
62.5641.71
55.66-1.71 59.07
PRBCD
74.95
71.6742.76
64.8444.18
57.94
53.24+5.20
48.66 48.68-16.52
PGA
78.5543.00
75.3313.69
68.63
61.55
56.6018.52
54.91
Table 16: Accuracy (%) on the Ogbn-Arxiv dataset under EvA and PRBCD across varying perturbation budgets e.
Table 17: Accuracy (%) on the Ogbn-Arxiv dataset under EvA and PRBCD across varying perturbation budgets using control nodes.
Attack
Clean 0.1 %
0.5 %
1%
Attack
Clean 1 1%
5 %
PRBCD
70.53
69.83
68.64
66.27
PRBCD EvA
64.89
54.7
EvA
70.53
69.21
67.59
66.86
59.3
53.92
In addition to both realistic cases, compared EvA (with divide and conqure) to PRBCD in the same setup as we evaluated for other datasets. The summarized result is illusterated in Fig.
C.4 COMPARISON WITH DAI ET AL. 2018B
(Dai et al. 2018b) proposed a practical black-box attack (PBA), dividing it into PBA-C (with access to logits continuous) and PBA-D (access only to the labels discrete). As stated in (Dai et al.) 2018b). a genetic algorithm for global attacks requires PBA-C because it relies on logits, with the fitness function being the negative ligelioel We demonstrate that EvA not only eliminates the need for logits but also performs even better by directly optimizing for accuracy rather than using log-likelihood. To compare method with DDai al. 2018b), modified the algorithm's
16

---

Published as a conference paper at ICLR 2026
Table 10: Classification accuracy (%) on the PubMed dataset in the inductive setting under adversarial attacks. Results are reported for four GNN models subjected to two different attack methods across varying perturbation budgets c. Training, validation, and test sets are non-stratified.
Model
Attack
0.01
0.02
0.05
0.10
0.15
0.20
APPNP
EvA
73.85 12.35
69.64 1:216
57.07
+22322
+2.32
47.03
43.94
4:.18
PRBCD
75.54_2.34
72.44
65. 65.1442.26
57.15
51.04
45.
45.7542..0
EvA 69.15
64.62
52.17+1.77
33.62
26.62
24.21
GAT
PRBCD
71.33_1.58
67.78 1.79
59.73
49.87 1.36
42.04 1.57
35.94+1.60
EvA
72.60+2.19
68.35
56.15
42.93
40.46
39.11 +2.98
GCN
PRBCD
74.99 1.99
12.00
12.32
65.54.1.77
49.32 2.66
13.90013.09
GPRGNN
EvA
72.01 14.18
67.61
14.28
55.9511.322
14.32
51.49 17.51
49.18
1.883
42.39 19.63
PRBCD
74.37 3.44
11.66
64.51 14.94
56.21
16.46
50.26
7..41
45.81 18.47
Table 11: Classification accuracy (%) on the PubMed dataset in the inductive setting under adversarial attacks. Results reported for two GNN models subjected to four different attack methods across varying perturbation budgets e. Training, validation, and test sets are non-stratified.
Model
Attack
0.01
0.02
0.05
0.10
0.15
0.20
EvA
72.60
68.3542.41
56.15 56.1541.92
42.93
40.46
39. 39.1142.98
EvaLocal
74.12+2.19
69.9942.04
63.4342.76
61.51 22.64
61.01+2.79
60.5442.64
GCN
LRBCD
74.8942.04
71.4842.49
65.6842.00
60.24
56.81+3.02
54.07
PRBCD
74.99
71.90
64. 64.1622.32
55.54
49.32+2.66
43.9043.09
EvA
72.01
67.61 +4.28
55.95++1.2
51.49
49. 49.1847.83
42.39 6.63
EvALocal 73.01+4.18
69. 69.10+3.83
60.51+8.10 66.7746.59
59.72+8.91
59.3149.50
GPRGNN
LRBCD
74.50+3.66
71.57+4.10
65.88+6.12
60.33
56. 76.754
18.7548.18
PRBCD
74.3713..40
71.66
64.51 14.94
56.21 16.46
50.2647.41
45.81
fitness function and mutation mechanism to replicate the results reported (Dai al. 2018b). This implementation retains scalability benefits, as is also built upon our sparse encoded representation. Note here we re-implement Dai al. (2018b) in our sparse and parallelized framework. Their original implementation uses dense adjacency matrices and sequential evaluation and would achieve significantly worse result within the same memory/run-time constraint. Even with our efficient re-implementation]] Dai et al. (2018h) is significantly worse than ours. Table 18 provides the results for the Co raML dataset using the GCN architecture. EvA also significantly outperforms (Dai et al.. 2018b)
Additionally, since our method independent of gradients, we established first attack on conformal prediction and certification. For conformal prediction, we attack coverage and set size where the latter criteria are not yet explored (to the best of our knowledge). Attacks tending to decrease certificate effectiveness also under eeper-explore in GNNs. In this work, aim to achieve both attack certified accuracy and certified ratio.
D TECHNICAL DETAILS OF EVA
Rigorous definition for components in EvA. We define genetic solver with four main components. (i) Population: a set of feasible answers to the problem that gradually improve over iterations. Here, each candidate is perturbation the original graph, a vector of indices at which edge will flip; formally s; E [ (n - 1) Indices are calculated via a mapping [n]2 + [ (n 1)] that is enumeration the upper triangle of the n adjacency matrix (see D) The corresponding
17

---

Published as a conference paper at ICLR 2026
Table 12: Classification accuracy (%) on the Citeseer dataset in the inductive setting under adversarial attacks. Results are reported for four GNN models subjected to two different attack methods across varying perturbation budgets c. Training, validation, and test sets are non-stratified.
Model
Attack
0.01
0.02
0.05
0.10
0.15
0.20
EvA
86.90
83.93 00,94
74.29 10.88
65.00...115
59.76.2.33
54.76.:1.19
APPNP
PRBCD
87.26_0.90
85.48+1.49
81.7941.08
76.55
72.44
69 69.29++.68
EvA
81.54
76.78 4:2.22
67 67.14
51.19 4.22
37.74
27.6 27.62:19.49
GAT
PRBCD
82.62 24.52_2.27
76.55
70.00
67.02=4.22
63.15..419
EvA
86.67 +1.71
82.86
72.74
58.33
01.3333300
49.76
44.29 4:333
GCN
PRBCD
87.38 1.81
85.83
12.43
80.95.22.08
74.29 1:422
69.76 14:34
67.62 1:496
GPRGNN
EvA
87.26 12.75
83.81
1:2.0
73.45....11
61.43
55.48
13.84
50.12 1.486
PRBCD
88.45 _2,29
86.31
1:245
$2.02.1.61
77.14
73.93 3.89
69.64 1:347
Table 13: Classification accuracy (%) the Citeseer dataset in the inductive setting under adversarial attacks. Results are reported for two GNN models subjected to four different attack methods across varying perturbation budgets e. Training, validation, and test sets non-stratified.
Model
Attack
0.01
0.02
0.05
0.10
0.15
0.20
EvA
86.67
82.86 12
58.33 72.74_2.74
49.76
44.29 43.33
EvaLocal
87.38
83.57
1
76.4342.62
75.00+3.23
74.52+3.16
GCN
LRBCD
88.45-2.17
86.4342.71
83.6942..6
80.12
78. 78.45+.2 43.99
75.36+41.8
PRBCD
87 17.38
85.83+2.43
80.9542.06
74.29
69. 69.764+1.31
67 67.62++1..6
EvA
87.26 87.26
83.81
73.45-3..1
55.48 61.43
50.12
EvaLocal 87.50=2.27
84.29+2201
80.48+3396
77.86
76.43+5500
75.12+6.57
GPRGNN
LRBCD
89.76
87.98 12.48
85. 85.12:22.76
81.90
78.45 79.64
PRBCD
88.45
86.31
82.0242.61
77.14
73.93
69.64
perturbation matrix P. is simply defined as P: Pi 9:] P. pb] where (pr, 2:) -1-)=111-0 for every index The initial population is selected randomly. (ii) Fitness: is notion of how close to optimal each candidate is. For any loss function L we define the fitness function fit as fit(s;) = L(X, A + P., y). Regardless of differentiabilityy as long as the loss function has enough sensitivity contrast between various individuals,
11 (s:(t)
[)] + R.
it directly compute the fitness (special case in 8 4). (iii) Crossover: is an operation to generate new population candidate via combining two existing ones. The (single joint) crossover operation at joint defines a new candidate vector 8new = cross, (81, 82) ;= 81[: jl 82 +1++]]]]] where * is the concatenation of two vectors. Crossover operation with kicross 1 joints is defined recursively in the order of joints. The number of crossovers is hyperparameter (see S E}. and their locations are chosen randomly in the range of candidates' length. The candidates for cross-over are chosen through "tournament". In each tournament, Nuour random candidates are compared, and the parent candidates are selected based on their fitness. This process repeats for generations. (iv) Mutation: introduces further exploration to the new population. The function mutate [ (n 1)]² + - (n 1)]s is random mapping of candidate to another. A simple example of mutation is to change each index with some mutation probability to any random index in the range. We propose better mutation operators later.
Mapping function: enumeration over A. For enumerating over A, instead of using the row and column indices of the node to select, we introduced indexing. For directed graph, the indexing starts from 0 to n However, in an undirected graph, we only need the upper triangular part of the matrix A. To achieve this, use the following algebraic solution to find the row and column of
18

---

Published as a conference paper at ICLR 2026
Table 14: Classification accuracy (%) on the CoraML dataset in the inductive setting under adversarial attacks. Results are reported for two GNN models with or without adversarial training subjected to three different attack methods across varying perturbation budgets c. Training, validation, and test sets are stratified.
Model Adv. Tr.
Attack
0.01
0.02
0.05
0.10
0.15
0.20
LRBCD 48.51
75.94
71.10_1.16
64.41+1.65
60.1441.77
57.47
None
PRBCD 76.4441.04
13.17
66.48_2.13
58.51
52.67
47.19
EvA 74.80
68.97
52.95_1.91
41.9942.06
37.65
35.37
LRBCD 79.6441.77
77.51
73.10=1.54
68.1941.11
64.8441.99
62.3543.00
GCN
LRBCD PRBCD 18.79
75.87
69.75_1.81
62.35
56.80
54.2314.11
EvA 16.8
1..10
56.30
1.66
48.40
12.46
40.85 12.70
LRBCD 80.71
77.86.0.8
73.81
0.54
10.91
66.4811.08
63.77 1.773
PRBCD PRBCD 78.93
76.30
7..25_1.74
1.74
64.06
59.5012.84
56.5814.55
EvA 70.80
71.53
57.44_2.13
19.11
44.70
41.92+3.32
LRBCD 80.85+1.36
78.58
74.66
69.89
66.98.u.92
65.05
EvA
PRBCD 79.79+1.80
76.51
71.25
64.3441.97
60.43
58. 22.22.22222
EvA
77.22
71.96
57.94_3.08
50.0443.29
44.91
42.63
LRBCD 77.51
74.80
68.83
62.56
59.07
55.66 59.0715.98
15.98
None
PRBCD 13.05
71.67 12.7
(4.84_4.11
57.9414.55
53.24
15.20
48. 16.58
EvA 44.53+4.11
66.83+4.51
51.53_5.57
51.53
42.21
37.01 +9.84
34.52+9.88
LRBCD 81.57
79.72 12.22
75.59 22311
71.32 1:220
68.97 1:210
66.69 1:225
GPRGNN
LRBCD PRBCD 80.71
78.51:2.29
72.88 2.38
66.9011.95
61.78.1.99
57.51
EvA 78.7942.69
72.95+2.67
63.42_3.15
56.5844.08
52.88
49.96
LRBCD 80.4342.01
78.01
73.74
69.9642211
67.1942.51
64.8443.20
PRBCD PRBCD 40.2142.43
77.30+2.63
77.30
71.53_2.67
65.12
60.07
55.37 13.85
EvA 78.7942.45
73.10
62.85_4.93
56.9416.64
53.7447.65
51.60..8.10
LRBCD 79.64
76.44
72.95
69.0441.26 16
67.0541.46
65.48+1.88
EvA
PRBCD 78.51 10.60
75.87 11.32
70.32
64.91
59.57
56. 56.164: 1
EvA
76.51 10.44 70.96
60.85
54.7313.99
50.25
18.8315.99
Table 15: Performance of different attack methods under varying budgets on Pubmed dataset.
Attack
0.01
0.02
0.05
0.10
0.15
DICE
79.00
78.76
78.69
78.06
77.90
PGA
74.61
70.20
58.44
48.18
47.37
GRBCD
76.14
73.56
64,51
54.63
49.37
PRBCD
74.99
71.90
64.16
55.54
49.32
EvA
72.60
68.35
56.15
42.93
40.46
Table 18: Comparison of classification accuracy (%) on the CoraML dataset under EvA and Dai
et al. 2018b) across varying perturbation budgets e.
Attack
Clean
0.01
0.02
0.05
0.1
0.15
0.2
Dai et al. 2018b)
81.07=2.07
78.50
76.6642.22
72.53
68.7541.45
65.34=1.20
63.27
EvA
81.07
74.80
68.97
1.58
52.95 +..91
41.99 2200
37.65
22.74
35.37
the perturbation by referencing only the upper triangular indexing.
81 + 4n(n - 1) - 7 0.5
nーn-2-
(2)
-=1+1+-- n(n 100-1)
(n - ( i -
19

---

Published as a conference paper at ICLR 2026
The advantage of this solution is that it can also be implemented in vectorized way, making everything parallelizable.
Attacking robustness certificates. We define randomized model convolution of the original model and a smoothing scheme. Namely the procedure or smooth inference is to add a noise (defined by the smoothing scheme) to the input, and evalute the model the noisy input. The output of the smooth classifier is the probability of the top class over realizations of the noise (this is the output of the smooth classifier binary certificate; for confidence certificate the output is the expected softmax scores). The smoothing scheme & : X' + X' is a randomized function mapping the given input to random nearby point. For graph structure. we use the sparse smoothing certificate (Bojchevski et al. 2020), which certifies whether within .r..,a the prediction of the smooth model remains the same. Here Ta the maximum number of possible additions, and ra the maximum number of edge deletions. The smoothing function is defined by two Bernoulli parameters p+, and p-; i.e. for each entity of A, if it is zero, it will be toggled with p+ probability and otherwise with p.. The same smoothing scheme (and threat model) can be defined for features if the feature space is also binary and sparse. Setting p+ = p- reduces the certificate to uniform smoothing certificate for L ball.
Smoothing certificates require black-box access to the model ʃ. As described above the smooth classifier is defined as fz) = E ({())) = yl] each random sample x' is one vote for class fax' and f is the proportion of votes for class y. Regardless of the model f. the smooth model f changes slowly around the imput. Let p = fy (z)) for the smooth classifier we can find a lower bound probability p 2 (in fy (z) and define the certificate as decision function Hyy 2 0.5). This decision function ensures that the predicted class still remains the top-class for any point within the threat model. For details including the optimization function and how to compute certified lower bound see (Bojchevski et al. 2020).
Whether a node (an input in general) is certified reduces to whether the smooth prediction probability for the input is above threshold p. This is due to the non-decreasing property of the certified ratio with respect to p. Additionally since the certificate is only a function of the probability and not the input, we can find this value easily via binary search. Therefore our objective is to decrease the probability of the smooth classifier below p for as many node as possible.
Adaptive sampling for certificate attack. Statistical rigor is not necessity while attacking the certificate. Therefore, we can reduce the sampling rate to a low number while finding the perturbation. Later ensure that our attack has reduces the certified ratio again follow the proper certificate configuration. During the attack, we can reduce the cost of resampling by only resampling the subset of the graph that was perturbed. In other words, we initialize the search by computing and storing samples A ... A. from the clean graph, and for each perturbation Á we only need resample the edges in A.A. Specifically for any edge removed from the graph during perturbation we update original sample Ai...., Am with p+ Bernoulli samples in the same index of the added edge. Similar process is done with p_ random edge removals for edges added in the perturbation. We substitute those samples in the same entry of Ai...., Am. and by running this process |8] times, we assume that AI, Am are representative as new set of m samples for A. This adaptive sampling reduces - 16), which is significantly lower. Surely, to evaluate the final perturbation (the reported effectiivnesss) we don't use this approach, as it is statistically flawed and only applicable to reduce the computation during the attack.
the number of random computations from m n to m
D.1 ALGORITHM FOR EVA
Here we provide the algorithm and the pseudo-code for EvA. The input to our algorithm is the set of following variables: Graph G = (X, A) with |V] = n, trained model f. attacked node set Van= labels yau. global budget We set the followings our hyper parameters: the fitness function fit(-). population size np, number of iterations nt, tournament size Thour mutation rate Pmutt number of crossover joints kuroes-
Our population at each iteration is a matrix S E [n]<x> where np is the population size. Iimit the set of all possible edges that have endpoint in Vatt- This set is used to form the initial matrix S due to an observation showing that initializing from these edges considerably improves the initial performance.
We define
20

---

Published as a conference paper at ICLR 2026
Before introducing the algorithm define the following necessary blocks: (i) the function that converts a population element to a perturbation over the graph. (ii) The tournament function that takes random subsets from the existing population and pick the top element from them. This function specifically chooses which elements in the population are remaining for the next iteration. And, (iii) the crossover function that designs new element based existing elements in the population. All three functions are defined in Algorithm
Algorithm 1 Helper functions for EvA
Ensure: Adversarial adjacency Au
1: Bijection II ((u, S S (i....,n(n 1)/2} and IT=1
D Index map
2: function APPLYPERTURRAAIONN
3: Initialize sparse matrix P. E {0, 1]mXxe as all zeros
4: for t I.... do
5:
(i.j) t II
-I (s(t) with i j
6: P. P.li. #1; P.lj. + Pali.
7: end for
8: return Á + + Ps
Edge flips are applied via XOR
9:
end function
10: function TOURNAMENTSELECTTSS Thour)
11:
Sample a multiset of Thuur candidates from S uniformly at random
12:
Return the fittest candidates in C: arg minsec ace(f(X, ApplyPerturbationn
13:
end function
14:
function (ROSSOVER(S (1), (2)), ((2),kkroo keroas)
Let Ji......Jkke.................... Random ChonceChoice((b 1]) and sorted increasingly. Initialize Schild,1 (1)) Schild,2 (2)
17: parent +-
jo < 0, jkems+1 f- 8
19:
for 1,, Kaross do parent + parent
20:
P Alternate between and
21:
for t Jm-1 + 1,
Fm do
22:
Schild, 1 <- 8 (parent) [t]
23:
2 [t] sl parent) [
24:
end for end for
25:
26: return 8child, Schild,1
end function
In the definition of the crossover function in Algorithm 1 there are two parents and two child elements. To flip the selected parent we use 3 parent which changes from the first parent to the second and Vice versa.
Other than the above functions, GA uses another function called mutation. This function applies random changes to the population enabling more exploration in the space of solutions. The following a naive mutation function that is also used as our baseline equivalent to Dai et al. (2018)).
This mutation function is very less effective compared to the adaptive targeted mutation introduced in $ This is since the naive mutation proposes perturbations that are outside of the receptive field of Vatt which does not introduce any change in the accuracy specially for low Here introduce adaptive targeted mutation which follows two modifications (i) any edge we add during mutation must have one endpoint in Van. and (ii) if node in Van is already misclassified there is no need add edges connected to it anymore. The algorithm for our adaptive targeted mutation is in Algorithm
With all the blocks defined in Algorithm 4 we provide the algorithm for EvA.
21

---

Published as a conference paper at ICLR 2026
Algorithm 2 Naive mutation function
1:
function NAIVEMUTATIONG Pmuc: 8) & set of all unordered node pairs (u, u) with
Pmur:
2:
for / = I,.... do
3:
if Bernouli((Pauu) is then
4:
Sample (u, v) & uniformly s[t] I[(u,)) v)
5: end if
Unbiased random mutation over all possible edges
6:
7: end for
8: return
9:
end function
Algorithm 3 Adaptive targeted mutation function
1: function ADAPTIVETAARGETEDMCTATTT
Pmnut Vau, Viipped)
2: U Van Vinpped
Attacked nodes whose label is not yet flipped
3:
for L 1.....d do
4:
if (Bem) is then
5:
Sample 24 uniformly
6:
Sample v V uniformly
7:
s[t] 4 [1(mmin(u v), max(u, v))
Targeted mutation: at least one endpoint in
Vau \
Vitipee end if end for return
8:
9:
11: end function
D.2 How SOLUTION EVOLVES
s We further conduct an ablation study on the solutions found by EvA and PRBCD under a specific budget of 10%. In this experiment, we keep all hyperparameters of EvA and PRBCD fixed and run them across 10 different seeds. We then compare the average solutions generated by each adversary. The left figure in Fig. shows the number of connections across different labels. In both cases, the methods focus more on label 5 than on the others, but EvA distributes the connections more uniformly compared to PRBCD. The middle figure illustrates the nodes with original degrees ranging from to greater than 8. The results indicate that, in both attacks, most of the budget is spent connecting to low-degree nodes. However, compared PRBCD, EvA allocates more of the budget to higher-degree nodes. Additionally, we calculate the margin loss for each node in the original graph and discretize them into eight levels. As shown in the right figure Fig. EvA allocates higher-mate margin nodes, resulting in a non-trivia solution that achieves a better optimum. Finally, it seems that EvA identifies solutions that differ from greedy-based heuristic, which usually only targets low-degree or low-margin nodes.
of the budget
Pert Connection Label
Pert Connection Degree
Pert Connection Margin
30
40
15
30
20
20
0 1
2
7
2
6
Figure 9: The upper triangle of each heatmap represents the perturbation connections for PRBCD, the lower triangle corresponds the same for EvA, and the diagonal is set
22

---

P) Published as a conference paper at ICLR 2026
Algorithm 4 EvA: Evolutionary Attack on Graphs
1: mnt Vat V
Search space: Edges touching attacked nodes
2: 8 < [ [mmt|]
Perturbation budget
3: S <-
b Population of size P
4: Abeu < A;
Fbest -00
5:
for = "....,"' do
6:
Rs t- I)
7:
for
8; E ESa do
8:
A, APPLYPERTURRAATONNAA F; fit(f(X, Vau)
9:
10:
Rg + -- (FF)
if Fbest then
12:
Freu < Pi; Abeat A;
end end for
14:
15:
Snew f farg max F(s)}
16:
while [Smew < P.Poo do
17:
(s())
TOURNAMENTSELECTT Thor) 8o1, 8e2 CROSSOVER s22), keros)
(2)) (2))
Prour)
18:
19:
for Schild E {8e1, 822) do
20:
Achil + APPLYPERTURBATIONAA Schila)
21:
+ f(X. Achila)
Forward pass
Nipped f {u E Vatt : 9o + ye3
23:
< ADAFIVETARGETEEIITATTON (Sciild Schild, Pmutt Viiiped)
Snew < S Seew {Sehila)
25:
end for
26:
end while
27:
S 5- Snow
28:
end for
29:
return Antv Abest
We also track the perturbation connections at different steps of EvA to see how the best solution evolves during optimization. In Fig. 10 as you can see, at the beginning it connects nodes with high margins to those with low margins which suggest it start with simply affecting the side of the node which is more vulnerable (lower margin), but as it proceeds, it also optimizes connections between high-margin and medium-margin nodes. This suggests that it attempts degrade the performance of nodes from both sides of the edge increasing the efficiency of the budget usage.
In Fig. 11 first observe that EvA spends most of its budget low-degree nodes (which easier to attack). We further observe how the method gradually reduces its focus on higher-degree nodes (which harder to attack), while still targeting some high-degree nodes that remain vulnerable. Finally, in Fig. 12 we track the evolution of label focus: label 4 (which corresponds to label 5 in the previous figure) receives more attention throughout all the steps. In the beginning there lots of within- within-class perturbations which are gradually reduced during the evolution.
In Fig. [Left, Middle], we measure the number of unique edges and nodes across the entire population (all 512 members) at different steps. As expected, the number of unique edges and node are decreasing. This indicates that the attack converging. We also measured the number of nodes and edges that are repeated in every member of the population (i.e., the size of the intersection across the entire population) Fig. [Right]. Increasing the number of nodes and edges shared across the whole population means the algorithm is converging and moving toward exploitation, while having fewer shared nodes and edges indicates exploration. Fig. 13 [Right] reveals an interesting pattern: during the first 500 iterations. EvA alternates between exploration and exploitation, repeatedly introducing new edges and then reverting. After around iteration 500, exploration decreases and the algorithm shifts more toward exploitation.
23

---

Published as a conference paper at ICLR 2026
Parce Marah Maran22
Maran22
Nondr 3
Marte 2
Figure 10: Visualization of how perturbation connections evolve throughout the optimization steps of EvA. Early in training, connections primarily link high-margin nodes [buckets 7-8] to low-margin nodes [buckets 1-2]. As optimization progresses, the method increasingly forms connections between high- and medium madiun--arginn nodes.
stos +.O. a00-/76.
step 17, aco-66.3
stpp - 32, acced8.2
Stop = 82. acce512
J00p 221, acced6.2
Step 372, acc-645
Step 3332 acc-83.3
15
Figure 11: The gradual evolution of the perturbation and the distribution of perturbation connections with respect to node degree.
000-6.2
atow51
acow66
000-445
LAC
Figure 12: Visualization how perturbation connections shift over optimization steps, showing how the method progressively redistributes its focus among different label pairs.
1e3
1c4
Reyested Nodes
Nocuacy (59
Unique Node Count
Unique Edge Count
4
Count/ Accuracy
200
2
100
1000
500 Iteration
1000
Iteration
Iteration
Figure 13: [Left] shows the number of unique nodes across the population, [Middle] shows the number of unique edges across all 512 individuals. [Right] shows the edges and nodes that appear in every individual.
24

---

Published as conference paper at ICLR 2026
In Fig. 14 present the perturbation graph that is the concatenation of all perturbations across the entire population. The position of each node is based on a 2D representation the logits, obtained using the t-SNE algorithm for dimensionality reduction. The edge widths indicate how many times an edge is repeated in the population, the node size represents the number of perturbations that include this node, the node colors correspond to different labels, and square nodes denote training nodes, while circular nodes denote attack nodes.
As shown, the beginning of exploration all of the edges have low width. Toward the end, the edges become thicker and some nodes grow larger. Interestingly, our attack exploits nodes whose latent representation is located in the "wrong" cluster, perturbing these nodes is likely more effective. Finally, we observe more connections originating from the pink-labeles nodes which are more dispersed the embedding space. Intuitively, this allows EvA gain leverage regions where the representation is loosely organized.
Finally, we look the solutions that PRBCD and EvA find, and we compare how many nodes are directly influenced on average over 10 different runs. This evaluation revealed that EvA affects approximately 282 nodes on average, whereas PRBCD influences only about 208 nodes directly in the final attack solution. This suggests that PRBCD still overspends part of its budget on small number nodes.
We further provide Table 19 and Table 20 which shows the degree of perturbation for each node, i.. Σ, P.y for all i, over 10 runs for both EvA and PRBCD. For example, in Table 19, we see that the first run we have 251 nodes with only a single perturbation, 27 nodes with perturbations, nodes with 3 perturbations, and so on. These results indicate that EvA attempts to change nodes more efficiently usually modifying them with just one edge flipping. uses less two-flips and furee-flips compared to PRBCD (Table 20p. and only rarely performs four or five flips single node. PRBCD, on the other hand, almost always overspends its budget on one or two nodes with very high degrees of modification. This reduces the opportunity to distribute its budget across more nodes, thereby lowering the number of nodes that PRBCD directly influences.
Table 19: The counts of perturbation de- grees over 10 runs of EvA CoraML.
Table 20: The counts of perturbation degrees over 10 runs of PRBCD CoraML.
Run
1.0
2.0
3.0
4.0
5.0
Run
1.0
2.0
3.0
4.0
5.0
6-10
11-30
I
251
27
5
1.0
0.0
140
47
13
8
0.0
0
2
246
27
8
0.0
0.0
2
137
37
19
4
1.0
0
3
242
38
2
0.0
0.0
3
136
50
17
7
1.0
0
0
4
250
29
4
1.0
0.0
4
145
48
12
5
1.0
2
0
5
244
34
4
0.0
0.0
5
149
35
15
6
4.0
5
0
6
259
25
2
1.0
1.0
6
149
44
13
3
1.0
3
0
7
246
33
4
0.0
0.0
7
154
36
13
2
3.0
5
0
8
241
29
7
1.0
0.0
8
127
46
17
4
1.0
2
0
9
251
30
3
1.0
0.0
9
163
33
11
5
2.0
2
1
10
229
43
3
0.0
0.0
10
130
3
3.0
3
D.3
TIME ANALYSIS
We run an ablation study comparing PRBCD, and EvA for wall clock time and memory. In EvA, the number of steps controls the time and the size of the population (assuming all population evaluated at once using stacked inference) controls the memory. Similarly for PRBCD, time is controlled by the number of epochs controls the time and memory is function block size. We evaluate EvA with different numbers of steps, population sizes, and parallel evaluations, and PRBCD with varying numbers of epochs and block sizes on the Pubmed dataset. Fig. 15 (left) shows the results for A and PRBCD in terms of memory usage, wall clock time and method performance. Our method demonstrates comparable performance within the same level of wall clock time (less than a minute). Moreover, by increasing the wall clock time and memory either by a larger population size more steps, EvA enhances its performance. This while PRBCD has an almost constant trend given more time memory.
25

---

Published as a conference paper at ICLR 2026
Suep 7L316
12,
61,
203, sor
Smep
Owp 17775
Step 513, 4377
Figure 14: Population-wel wide perturbation graph showing t-SNN-projecced node positions, with edge thickness reflecting repetition, node size indicating degree, and colors denoting labels; training nodes are squares and attack nodes are circles.
26

---

Published as a conference paper at ICLR 2026
PRBCD
EvA
(Cloon Pert] Ace
30
Parallel Eval
25
16.0
128.0
0.20
Max Mem (GB)
32.0
255.0
0.15
0.10
15
0.05
10
Wall Clock Timetmin)
3
Max Memary(GBB
20
D
3.0
3,5
4.0
Wall Clock Time
Figure 15: Comparing the memory usage between EvA and PRBCD.
we highlight how our framework provides a trade-off between time and memory for achieving the same level of accuracy by varying the number of parallel evaluations. For each point in the figure, we observe roughly the same performance; however, the methods differ in memory usage due to different number of parallel evaluation, leading to variations in wall clock time.
Additionally, in Fig. 13
D.4 DIVIDE AND CONQUER
Computing gradients w.r.t. all elements matrix A computationally intensive. And as the graph grows the elements for which we should compute and store gradient increases quadratically. As remedy PRBCD applies block-coordinate gradient descent where in each iteration the gradients computed over a subset of indices in A. Intuitively PRBCD works under this assumption that relaxation from A to a (random) subset of adjacency matrix does change the optimal solution by a high margin. In Fig. 16 for Ogbn-Arxiv dataset, we increased the block size of PRBCD, from the suggested 3M to 10M, and still the result far from EvA. Beyond that block size could not fit into the memory.
While EvA works with sparse representation of A still the search space (2) grows exponentially with the number of nodes. Via divide and conquer (D&C) we apply relaxation where we assume sequential search for optimal attack targeting disjoint subsets of Vatt does not result far from the optimal solution for the entire Vatt- Therefore we divide this set into k disjoint subsets and run the attack over each subset separately. Our attack applies subsets in sequential order meaning that after attacking one subset, the attacked graph is assumed to be the clean baseline to attack the other set. At the final round, the attack carries all the perturbations applied on Vatt- To ensure the validity of the result, we divide the budget according to the edges connected to each subset.
As our D&C approach is applicable regardless the attack algorithm we can similarly apply it to PRBCD. Although it does not outperform EvA, we show that adding D&C to PRBCD increases the performance by significant margin.
0.65
PRBCD 3M
Pert Acc
0.60
PRBCD-3M
EVA D&C
0.55
0.50
0.45
1%
5%
10%
15%
Figure 16: Effect of Divide and Conquer EvA and PRBCD.
27

---

Published as a conference paper at ICLR 2026
E DATASETS AND MODELS, AND HYPERPARAMETERS
E. STATISTICS OF DATASETS
In our experiments, we mainly conduct experiments on the commonly used graph datasets: CoraML, Citeseer, and Pubmed, which are all representative academic citation networks. Their specific characteristics are as follows:
CoraML. The CoraML. dataset contains 2,810 papers as nodes, with citation relationships between them as edges, resulting in 7,981 edges. Each paper is categorized into one of classes corresponding to different subfields of machine learning. Each node is represented by a 1.433-dimensional bag-of- words (BoW) feature vector derived from the words in the titles and abstracts of the papers.
The Citeseer dataset is also an academic citation network dataset consisting of 3,312 papers from subfields of computer science and total of 4.732 citation edges. Similar Cor aML, each paper as a node is represented by a BoW feature vector with a dimensionality of 3,703.
Citeseez.
Pubmed. The Pubmed dataset is derived from citation network of biomedical literature that contains 19,717 papers as nodes and 44,338 citation edges. Each paper is categorized into one of classes based on its topic. The node features in Pubmed are 500-dimensional vectors.
The Amazon-Computer: and Amazon-Photo datasets consists of two networks of Amazon Computers and Amazon Photo. In these networks, nodes represent individual goods sold on Amazon, and edges indicate that two products are frequently purchased together. Each node is accompanied by bag-of-words features derived from product reviews, providing textual representation of the item's 's description and customer feedback. The task predicting the product category.
CmazonnComputers and Amazon-Phott
Table 21: Dataset statistics.
Dataset
Nodes
Edges
Features
Classes
CoraML
2,810
7,981
1,433
7
Citeseer
3,312
4,732
3,703
6
Pubmed
19,717
44,338
500
3
AmazzonComputers
13,752
491,722
767
10
Amazon-Photo
7,650
238,162
745
8
E.2 DETAILS OF MODELS
In the following sections, we detail the hyperparameters and architectural details for the models performed in this paper.
GCN. We utilize two-layer GCN with 64 hidden units. A dropout rate of 0.5 is applied during training.
GAT. Our GAT model consists of two layers with 64 hidden units and single attention head. During training, we apply dropout rate of 0.5 the hidden units, but no dropout is applied the neighborhood.
APPNP. We use a two-layer MLP with 64 hidden units encode the node attributes. We then apply generalized graph diffusion, using transition matrix and coefficients уK (1 a K and 7 = a1 - a:) for I < K.
GPRGNN. Similar to APPNP, we employ a two-layer MLP with 64 hidden units for the predictive Part. We use the symmetric normalized adjacency matrix with self-loops as the transition matrix and randomly initialize the diffusion coefficients. We consider total of K 10 diffusion steps, with set to 0.1. During training, we apply a dropout rate of 0.2 to the MLP, while no dropout is applied to the adjacency matrix. Unlike the method in Chien al. (2021). always learn the diffusion coefficients with weight decay, which acts as a regularization mechanism to prevent the coefficients from growing indefinitely.
28

---

Published as a conference paper at ICLR 2026
Table 22: Hyper-parameters for PRBCD, LRBCD, and EvA.
Hyper-parammter
PRBCD
LRBCD
Hyper-parameter
EvA
Epochs
500
500
No. Steps
500
Fine-tune Epochs
100
0 WeightOnly 500,000 tanh-Margin False
Mutation Rate
0.01
Keep Heuristic
WeightOnly 500,000 Tanh-Marghh N/A
Tournament Size
2
Search Space Size
Population Size
1,024
Loss Type
No. Crossovers
30
Early Stopping
Mutation Method
Adaptive
SoftMedian GDC. We follow the default configuration from Geisler et al. (2023), using temperature of = 0.2 or the SoftMedian aggregation, with 64 hidden dimensions and dropout rate of 0.5. We fix the Personalized PageRank diffusion coefficient sparsification. During the attacks, the model remains fully differentiable, except for the sparsification of the propagation matrix.
0.15 and apply top 64
MLP. We design the MIP following the prediction module GPRGNN and APPNP, incorporating two layers with 64 hidden units. During training, apply dropout rate of 0.2 to the hidden layer.
E.3 HYPERPARAMETES SETUP
In EvA we set the capacity of the computation to the same as the population, this means that all perturbations within a population are in one combined inference. However, some cases where the graph is large (e.g. Pubmed), we reduce this number.
Table 22 shows the hyper-pace pare-paraeeter selection in almost all experiments. We only change the population number in some experiments, like certificate attacks, to reduce the computation. E.g., in certificate attack, the population reduced by a factor 10. Finally, all of the experiments has been run on one NVIDIA H100 GPU.
E.4 ATTACK HYPERPARAMETEER
To assess the robustness of GNNs, we utilize the following attacks and hyperparameters. Based on Geisler et al. (2023), we also select the Tanh-Margin loss as the attack objective.
PRBCD. We closely adhere to the setup outlined by Geisler et al. 2023). A block size of 500,000 is used with 500 training epochs. Afterward, the model state from the best epoch is restored, followed by 100 additional epochs with a decaying learning rate and no block resampling, Additionally, the learning rate scaled according to ê and the block size, recommended by Geisler et (2023).
LRBCD.
The same block size of 500,000 is used with 500 training epochs. The learning rate is scaled based and the block size, following the same approach as PRBCD. The local budget is consistently set as 0.5.
EvA. We set the population size 1024 most cases. Our mutation rate 0.01, and increasing this number breaks the balance between exploration and exploitation, leading to less effective attacks. We run each attack for 500 iterations in most cases. cases like certificate attacks, which are time-consuming, we reduce this number to 100. The details are summarized in Table 22
For Ogbn-Arx: dataset divide the Vau kac 500 vertices. There we set the population size to 45 candidates. The 6, for subset i is set to 6 = 6. - V/. We also reduce the number of iterations for EvA to 300 for each subset while for PRBCD this number remains 500.
subsets where each division includes
EvA-Local. All hyper- are the same as EvA. An additional hyper parameter is twarm which is the number of initial steps where the random local projection is applied instead of the frequency score-based local projection. This number is set to 50 for Pubmed dataset. Interestingly without this projection. EvA-Local outperforms LRBCD for Citeseer and CoraML datasets. There we only remove random matchings from the nodes with degree violation until the total violation reaches 0. This approach does not work the Pubmed dataset. The intuition is that since Pubmed
29

---

Published as a conference paper at ICLR 2026
larger and denser compared to other datasets, for each candidate there are lot of edges that have least one endpoint violating the local constraint. Therefore removing many edges from a candidate, and replacing them by random edge adds a large random noise to each candidate at each iteration. Therefore the search done over a very noisy setup.
PGA. For the PGA, adopt the same setting in Zhu al. (2023). We use GCN the surrogate model and tanhMarginMCE-00.55 as the loss type. The attack is configured with 1 greedy step, pre-selection ratio of 0.1, and selection ratio of 0.6. Additionally, the influence ratio is set to 0.8, with the selection policy based on node degree and margin.
30


Reviews:
[{"review_id": "d2f0cYLUo1", "reviewer": "Reviewer_tEfF", "summary": "This paper introduces EvA, a black-box adversarial attack method for graph neural networks that uses a genetic algorithm to perturb the graph structure. Unlike gradient-based attacks, EvA directly optimizes discrete, non-differentiable objectives(such as classification accuracy) without relying on gradient approximations or domain relaxation. EvA highlights the limitations of gradient-based methods and establishes evolutionary search as a powerful, underexplored paradigm for adversarial attacks on graphs.", "questions": "- While EVA demonstrates that Genetic Algorithms can achieve considerable effectiveness in conducting adversarial attacks, I still feel I don't fully grasp its fundamental mechanisms.\n\n- In section 3, the sentence \"We hypothesise that EvA, leveraging the exploratory capabilities of GA, can explore the search space more effectively and avoid local optima, while PRBCD gets stuck.\" \"Exploratory capabilities\" and \"avoid local optima\" are essentially standard claims for all GAs, bordering on being tautological. The paper seems to fail to specify how exactly the exploration capability of the EvA manifests in the specific context of discrete graph perturbation spaces. However, the analysis of perturbation patterns might provide the most relevant clues. As shown in Appendix D.1 \"Label diversity\", this section compares the statistical characteristics of perturbation solutions found by EvA and PRBCD. The analysis reveals that EvA's perturbation connections are more uniformly distributed across nodes with different labels, and demonstrate a greater tendency to connect to high-degree nodes and high-margin nodes. While this analysis is highly valuable, it primarily describes \"what the solution looks like\" rather than \"how this solution was progressively discovered.\" It would be enlightening if the authors could demonstrate how the genetic algorithm guides the search process, which could potentially enhance the paper's readability and conceptual clarity.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "> 1. The paper's primary strength is its successful revival of evolutionary search, a paradigm previously dismissed as inferior. It demonstrates that with careful design, this approach can decisively outperform state-of-the-art gradient-based methods, challenging a core assumption in the field and opening a new direction for research.\n> 2. The work is supported by comprehensive experiments and thorough ablation studies that validate every design choice. \n> 3. The significance of the work is greatly amplified by applying EvA to novel objectives beyond accuracy, such as breaking robustness certificates and conformal predictions.", "weaknesses": "> 1. The paper rightly notes the high query complexity as a limitation, but does not conduct a rigorous quantitative trade-off analysis between computational cost and performance improvement. In my opinion, this is essential for the practical evaluation of the method.\n> 2. The paper presents compelling empirical evidence for EvA's superiority over gradient-based methods. However, the explanatory depth for this success seems limited, primarily resting on the well-established notion of gradient unreliability. A more profound analysis examining whether EvA's advantage stems from superior navigation of non-convex loss landscapes or effective exploitation of higher-order edge interaction effects would significantly strengthen the work and provide foundational insights for future research. For more details, please refer to the question section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "snPCanT5zs", "reviewer": "Reviewer_4Bnj", "summary": "This paper introduces EvA (Evolutionary Attack), a new framework for edge-based adversarial attacks on GNNs through a discrete evolutionary search rather than gradient-based optimization. EvA formulates the attack as a genetic algorithm that evolves a population of perturbation candidates, where each candidate encodes a small set of edge flips. The algorithm iteratively applies Selection, Crossover, and Mutation. They also design a divide-and-conquer strategy to handle large graphs. Because it only requires model evaluations, not gradients, EvA is model-agnostic and applicable to black-box settings. EvA consistently achieves larger drops in classification accuracy than gradient-based attacks. The evolutionary framework can also attack non-differentiable objectives, where gradient-based methods cannot operate.", "questions": "I wonder how EvA performs on larger graphs like arXiv, Products, and Papers 100M [1].\n\n[1] W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec. Open Graph Benchmark: Datasets for Machine Learning on Graphs. 2020.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper uses a discrete evolutionary search method for graph edge-based adversarial attacks on GNNs, without the need of gradients, making it model-agnostic and applicable to black-box settings. The evolutionary framework can also attack non-differentiable objectives. They show strong empirical performance comparing with gradient-based methods.", "weaknesses": "1. The proposed evolutionary search is highly heuristic and not guaranteed to find globally optimal perturbations. Many of its design--mutation rate, crossover scheme, and selection strategy--lack principled justification or ablation analysis. It remains unclear which components are critical for performance and how sensitive the attack is to hyperparameter choices.\n2.  The algorithm is difficult to follow from the current text presentation. Including clear pseudo-code or an algorithm box would greatly improve readability and reproducibility.\n3. The scalability and efficiency analysis are underdeveloped (e.g., runtime, total queries, memory usage). Currently there's not statistics showing the time and memory consumptions of PRBCD and EvA on various datasets.\n4. Using evolutionary search is not entirely new. The main novelty here lies in engineering and scaling rather than in conceptual advances. The paper would benefit from a clearer discussion of how its evolutionary design specifically differs from prior heuristic or search-based attacks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OS8SP9rDZJ", "reviewer": "Reviewer_oVZ5", "summary": "This paper proposed a genetic adversarial attack. Experiments compared with a few gradient based attack are conducted with many ablation study.", "questions": "Please see weakness.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "**1.** Experiments in various aspects are done to validate the method performance with abundant figures for illustrations.", "weaknesses": "**1.** The presentation of the paper is bad. There's neither formulation nor algorithm written, or any figure to completely show the pipeline of the proposed attack. The description of method is just split around all section 3 and 4 without a clear introducing logic, instead just describing sentences and paragraphs concatenated. The methodology description highly relies on comparison with a previous baseline \"PRBCD\" which was not formulated introduced as well, making the part harder to follow. There are also too many verbal definitions which are lack of clear expression and only used once. In all, the bad writing makes me really hard to have a full view of the proposed method in details, and I recommend the author to rewrite and reformulate the paper entirely. \n \n**2.** The experiments lack fully comparison with other works. The paper only compares with a few gradient based attack baselines, excluding experimental comparison with all other kind of attack by just stating \"gradients method are SOTA\" \"out perform others\". Considering the gradient baselines raised contain only one in 2023 while all others are before 2020, and the proposed method itself is indeed one of \"beaten\" genetic method, this lack of new baselines and ones from other attack types are unacceptable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OASOXcB7eD", "reviewer": "Reviewer_KDQh", "summary": "The paper proposes EvA (Evolutionary Attack), a black-box, gradient-free attack on graph neural networks (GNNs) that directly solves the discrete edge-perturbation problem using a tailored genetic algorithm. Unlike dominant gradient-based attacks (PRBCD, LRBCD), EvA does not relax the adjacency matrix to a continuous space and can therefore optimize non-differentiable objectives such as accuracy, certified ratio, and conformal coverage.", "questions": "Could the authors provide a direct comparison of the total number of forward passes (queries) used by EvA versus the number of forward/backward passes used by PRBCD to achieve the results in Table 1?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper convincingly argues that gradient-based structure attacks are fundamentally misaligned with the discrete problem, e.g. gradients are local, ignore edge interactions, require relaxations, and can be obfuscated. The paper's empirical evaluation is comprehensive and the results are significant, not just marginal. EvA drastically outperforms all baselines, including the SOTA PRBCD, across multiple datasets.", "weaknesses": "The most significant weakness, which the authors acknowledge in the limitations, is the high query complexity. Genetic algorithms are inherently query-intensive.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)