ATEX-CF: Attack-Informed Counterfactual Explanations for Graph Neural Networks
Authors: Yu Zhang
Sean Bin Yang
Arijit Khan
Cuneyt Gurcan Akcora
Venue: ICLR 2026 Poster (2026)
Keywords: Graph Neural Network
Counterfactual Explanation
Adversarial Attack
Primary area: interpretability and explainable AI

Abstract: Counterfactual explanations offer an intuitive way to interpret graph neural networks (GNNs) by identifying minimal changes that alter a model’s prediction, thereby answering “what must differ for a different outcome?”. In this work, we propose a novel framework, ATEX-CF that unifies adversarial attack techniques with counterfactual explanation generation—a connection made feasible by theirshared goal of flipping a node’s prediction, yet differing in perturbation strategy:adversarial attacks often rely on edge additions, while counterfactual methods typically use deletions. Unlike traditional approaches that treat explanation and attack separately, our method efficiently integrates both edge additions and deletions, grounded in theory, leveraging adversarial insights to explore impactful counterfactuals. In addition, by jointly optimizing fidelity, sparsity, and plausibility under a constrained perturbation budget, our method produces instance-level explanations that are both informative and realistic. Experiments on synthetic and real-world node classification benchmarks demonstrate that ATEX-CF generates faithful, concise, and plausible explanations, highlighting the effectiveness of integrating adversarial insights into counterfactual reasoning for GNNs.

Published as a conference paper at ICLR 2026
ATEX-CF: ATTACK-INFORMED COUNTERFACTUAL EXPLANATIONS FOR GRAPH NEURAL NETWORKS
Yu Zhang Aalborg University Aalborg, Denmark, 9220 yuzhang8
Sean Bin Yang Aalborg University Aalborg, Denmark, 9220 seanyães aau. dk
Arijit Khan
Cuneyt Gurcan Akcora
Bowling Green State University, USA, 43403 Aalborg University, Denmark, 9220
University of Central Florida Orlando, FL, USA, 32816 wuneyt.akcoraaeee edu
ari arijitkebgsu.co edu
ABSTRACT
Counterfactual explanations offer an intuitive way to interpret graph neural net- works (GNNs) by identifying minimal changes that alter model's prediction, thereby answering "what must differ for a different outcome?". ?". In this work, we propose novel framework, ATEX-CF that unifies adversarial attack techniques with counterfactual explanation generation-a connection made feasible by their shared goal of flipping node's prediction, yet differing in perturbation strategy: adversarial attacks often rely on edge additions, while counterfactual methods typ- ically use deletions. Unlike traditional approaches that treat explanation and attack separately, our method efficiently integrates both edge additions and deletions, grounded in theory, leveraging adversarial insights to explore impactful coun- terfactuals. In addition, by jointly optimizing fidelity, sparsity, and plausibility under a constrained perturbation budget, our method produces instance-level ex- planations that are both informative and realistic. Experiments on synthetic and real-world node classification benchmarks demonstrate that ATEX-CF generates faithful, concise, and plausible explanations, highlighting the efffectivneess of in- tegrating adversarial insights into counterfactual reasoning for GNNs. Our code is available at https: /ttpt/ggttttttttt//eteee/tehh com haamm/haanqyuoAAn ATEX CF
INTRODUCTION
Graph neural networks excel at node classification by recursively aggregating neighbor features and graph topology, yet their opaque inference undermines trust in critical applications such as healthcare, finance, and scientific discovery (Chen al. 2024 Zhong et al. 2025). This limitation
has spurred research into GNN explainability. with counterfactial methods YYuan et al. 2023 Qiu
2024) in particular aiming to determine the smallest modifications to node features or graph structure that cause a model's prediction to change.
al. 2025 Prado-Romero et
Meanwhile, adversarial attacks (Zhng al. 2024 Zhu et al. 2024 Sun et al., 2023 on GNNs have become an equally important line of research, as GNNs can be undermined by minimal, strategically crafted traph-structure perturbations, highlighting the need for robustness analysis. Consequently, robustness against adversarial attacks has become a key priority in GNN research.
Traditional counterfactual graph generation methods, e.g., CF2 (Tan et al., 2022), GCFExplainer (Huang et al. 2023). primarily rely on edge deletion to identify crucial substructures that support particular prediction. While effective, this deletion-centie perspective overlooks the role missing relations in the original graph whose addition could substantially influence predictions. In paral- lel, extensive studies in graph adversarial learning have demonstrated that adding small (e.g.. 2) number of carefully selected edges can effectively flip the prediction of target node (Chen et al.) 2025| Zhu et al.) 2024p. Such added edges adges-though absent the input often correspond to semantically plausible and structurally coherent relations.

---

Published as a conference paper at ICLR 2026
Despite their importance, current approaches address these two directions largely in isolation. From a counterfactual reasoning perspective, adversarially added edges naturally serve as actionable can- didates for counterfactual generation: They represent the minimal structural additions required to alter the model's 's decision. However, existing counterfactual methods, which predominantly rely on edge deletion, have largely overlooked the potential of incorporating edge-addition information derived from adversarial attack strategies.
Motivated by these insights, we design unified framework, ATEX-CF CfL mantics into counterfactual generation in a controlled and interpretable manner. Extending counter- factual generation to include edge addition has sigmificant benefits. From quantitative perspective, we demonstrate that edge-addition counterfactuals can (1) increase the likelihood of flipping predic- tions and (2) achieve this with smaller perturbation budget. From qualitative perspective, they provide practical advantages: (1) Complementary explanatory coverage while edge-deletion counterfactual identifies which existing relations are crucial for a prediction, edge-addition candi- dates reveal which missing relations could have altered the outcome. For example, in healthcare, a GNN may classify patient as low-risk for heart disease due to the lack of an edge represent- ing "symptom drug correlation", while introducing an edge "patient medication record cardiac side effects" can flip the prediction and reveal hidden reasoning paths. (2) Uncovering model bias and data deficiencies structural biases For example, a paper may be misclassified as "theoretical mathematics" due to missing citation edges to authoritative AI conferences. Introducing an edge "paper + ICLR Best Paper Award" corrects the prediction, highlighting dataset limitations and model vulnerabilities.
Q that incorporates attack se-
adding certain edges can divulge over-reliance on specific nodes or
Rejected Alice
Approved
Case Study. To illustrate the limitations of existing counterfactual methods, consider a scenario from the Loan-Decision dataset (aa et al., 2025). Loan approval is granted when both conditions are met: i ncome > 5 and degree > 3. Applicant Alice has income 6 (satisfies condition) but degree 3 (fails). The model predicts rejection. Classi- cal deletion-based counterfactual methods fail here- rerovrengvin edges further reduces degree. Unconstrained edge additions (e.g.. linking to billionaire) succeed but can be implausible. Our method ATEX-CF identifies feasible peer connection that serves as an actionable update and flips the prediction.
Alice
6
4
3
5
4
Figure I: Illustration of counterfactual limitations
in the Loan Decision dataset.
While this fusion is promising, combining adversarial attacks with counterfactual explanations is coo-trivial(Friesseele
2022). Adversarial edges are optimized for misclassifications rather than interpretability, raising challenges in ensuring the qualities of a good counterfactual explanation, such as high impact, sparsity, and plausibility (Longa et al., 2025p. Furthermore, when consider- ing missing edge additions to the input graph, the search space of possible perturbations remains combinatorially large, requiring principled mechanisms to balance effectiveness with efficiency.
Our contributions can be summarized as follows:
Unified perspective. We establish, for the first time, a theoretical bridge between adversarial attacks and counterfactual explanations in GNNs, showing that adversarial edge additions can be repurposed as counterfactual candidates. This connection provides principled foundation for unifying attack and explanation.
Hybrid counterfactual framework. We design a novel solution, ATEX-CF, that simultancously leverages edge deletions (traditional counterfactual explanations) and attack- -nformmedded edge addi- tions (from adversarial strategies), thereby offering a more comprehensive and actionable coun- terfactual than deletion-only approaches.
Enhanced explanatory coverage. By incorporating edge-addition counterfactuals, ATEX-CF uncovers missing but semantically plausible relations, complements deletion- based explanations, and enables proactive optimization (e.g., suggesting constructive graph modifications rather than only indicating critical existing edges).
aabbreviation for Attack Explanation Counterfactual
2

---

Published as a conference paper at ICLR 2026
Efficiency and controllability. We exploit adversarial attack logisties to form a focused candidate space, significantly reducing the combinatorial complexity of our counterfactual search. addi- tion, ATEX-CF integrates sparsity and plausibility constraints ensure interpretable and realistic explanations.
Empirical validation. Through experiments benchmark datasets, demonstrate that ATEX- CF improves explanatory power, maintains semantic plausibility, and reduces computational bur- den compared with state-of-the-art counterfactual generation and adversarial attack methods.
2
PRELIMINARIES
2.1 NODE CLASSIFICATION AND GRAPH NEURAL NETWORKS
Node Classification Graph. We consider the task of node classification in a graph, denoted
as G (V, EV, X), where V is set of nodes, E S {(v, w) w,w E VJ is set of undirected, unweighted edges, and X = {x,,X1..... X1...... .N-1) comprises node feature vectors with x; E Rd for each node v. The adjacency matrix A {0, 1 has entries Avw if (v, w) E E and otherwise. A subset Vz S V labeled, forming training data; each labeled node has a class Uo C = (1, (1....,c). .c. The goal is to predict the label of a target node V in supervised manner given A and X. Key mathematical symbols are summarized in Table in the Appendix.
Graph Neural Networks. Graph Neural Networks classify nodes through message-passinng scheme (Kipt & Welling 2017). Each node representation is iteratively updated by aggregating and transforming information from its neighbors. For the Graph Convolutional Network (GCN),
prominent GNN, the hidden representation at layer + 1 is H a (AHHW(!) where
H X, nonlinear activation, Aself A + IN augments the adjacency with self-loops, D. (Asati) the degree matrix, and Å D A +. The trainable weights at layer 1 are W(O) The final output is obtained by applying a softmax to the last hidden layer softmax (k(())(())) with E IR Nxe giving class probability distributions. Row Z, the distribution for node v, and the predicted class is ū. arg Zy.
2.2 GNN EXPLANATIONS
GNN explanation methods (uaa et al. 2023 Longa et al. 2025) reveal the structural and feature- based evidence that plays a key role in predictions. We categorize them into two paradigms:
Factual explanations identify subgraphs features supporting the original prediction. For target node v, an explanation subgraph G, S G satisfies fG.., X,) = f(G. where f is the GNN model and X. denotes the features of The GNNExplainer method (Ying et al. 2019) optimizes G to maximize mutual information with the prediction.
Counterfactual explanations identify minimal perturbations A A alter target node v's prediction f(A,X, X, v) * [(A @ AA, X, v), s.t. ||AA|| S K, where k is a perturbation budget.
2.3 ADVERSARIAL ATTACKS ON GNNS
Adversarial attacks deliberately perturb graphs (including edge-based and feature-based perturba- tion) mislead predictions. Key categories include i) evasion and ii) poisoning attacks.
Evasion attacks modify the graph during inference without retraining. For target node v, edge- based attackers solve maX L(f(A @ ÁA, x),, s.t. | < K, where L is the loss function which quantifies prediction error.
Poisoning attacks corrupt the training graph to degrade retrained models. For target node v. edge-basee based attackers optimize maxAa L(fo- (A, X, v), s.t. 8" = arg ming ((fo(A O AA, X)), || k.
Table I summarizes GNN explanations and adversarial attacks according to edge-based perturbation methods by their core characteristics.
3

---

Published as a conference paper at ICLR 2026
Table I: Comparison of GNN explanation and attack paradigms. We use E to denote edge dele- tions (removing existing edges) and E+ to denote edge additions (introducing new edges).
Category Factual Expl.
Goal
Primary Operation
Example
Explain prediction
Identify key subgraph
GNNExplalner
2019
Counterfactual Expl.
Alter prediction
Mainly E (edge deletions), though some recent work includes E+ E+/E inference, often E domi-
OF-GNNExplaner
Ladie
Evasion Attack
Misclassify node
TDGIA Zen
Poisoning Attack
Degrade model
E+IE in training, often E domi- nant
Nettack
Zigua et 2018
Key Insight. While counterfactual explanations have historically emphasized E to reveal model fragillit, adversarial attacks often exploit E* by introducing connections. More importantly, the attack literature has developed efficient methods to select which edges to add/delete under small perturbation budgets (e.g.,
.,.... 5), despite the combinatorially large number of possible additions in graphs, making naive counterfactual search impractical. This potential synergy between and the
counterfactual reasoning and attack strategies motivates our problem formulation 24.4 unified framework we propose in $
In this work, we focus on structural evasion attacks, which directly modify the graph topology at inference time. These attacks are particularly suited to our counterfactual framework, as they avoid retraining and yield interpretable perturbations that align with our goals of sparsity and plausibility.
2.4 PROBLEM FORMULATION
E, with adjacency matrix A and node features X, and pre-trained GNN classifier f. our goal for target node E V is to find small set of edge perturbations AE = AE+ AE- corresponding to additions (AE+) and deletions (AET), such that the pre- diction for flips while the resulting counterfactual graph remains interpretable and plausible. This problem combines two perspectives: from the attack literature, where efficient methods have been developed select high-impact edge additions under small budgets, and from counterfactual expla- nations, where minimal and semantically meaningful deletions expose decision edges. We formalize this hybrid objective in
Given a graph
A DUAL APPROACH OF EXPLANATIONS AND ATTACKS FOR GNNS
We develop a theoretical framework that links targeted structural evasion attacks on graph neural net- works with instance-level counterfactual explanation subgraphs. The core objective is to formalize when and why adversarial perturbations can serve as building blocks for counterfactual explana- tions. To this end, we introduce hypothesis capture the relationship between the attack subgraph and the counterfactual explanation of target node. More importantly, we support this hypoth- esis with gradient-basee reasoning and empirical similarity measures in Appendix A.12 To the best of our knowledge, this hypothesis and supporting evidence are presented for the first time as a plausible and empirically grounded link between adversarial perturbations and counterfactual explanations in graph learning.
To compare explanation and attack subgraphs, we consider two forms of graph similarity: i) struc- tural similarity (Doan et al. 2021): overlap in nodes or edges, measurable via graph edit distance, and maximum common subgraph metrics. ii) semantic similarity (Bai et al.) 2020): closeness in learned graph-level embeddings, indicating similar functional or predictive roles even if the struc- tures differ.
Hypothesis D states that the added edges in successful evasion attack overlap with the most influ- ential edges in a pre-attack counterfactual explanation subgraph.
Hypothesis 1. For a target node v, let (G(E*) denote the set of added edges in an evasion at- tack that flps the prediction of f. and ler CF CFEx Ex(G) denote the pre-attack counterfactual expla- nation subgraph of the graph G. Then, there exists a high graph similarity between AG(E+) and CF Gx) The proof is provided in the Appendix 1.1.
4

---

Published as a conference paper at ICLR 2026
Porturbation Formulation
Phase II: Gradient-Based Optimization
Phase III: Explanation Refinement
Input Graph and target node
Update Signed
Pruning
Mitimality Eit forfemeent
XA
M, [-1,1]
AA AA'
S
Gradienn
AA
Remove Redundant Edge AA
Target node
Discratization
M, MA-AA
Perturbation Candidate
VM, vii STE
Promote
Loss Famction
Auttck
Prediction
Sparaity
Plausibiiity
Iterate
Local Structure
Adversorial
Perturbations
Perturbed
Counter fatual Explemation Ger AOAA
S U
AFEX
À AGAA
Figure 2: End-to-end workflow of the ATEX-CF framework for counterfactual edge generation.
Building on the hypothesis, in Appendix A.12 wc also present two propositions and two corollaries that formalize when attack-based additions outperform deletions in flipping GNN predictions. These results characterize conditions under which deletions provably fail, yet targeted additions succeed, focusing on the functional advantage of attack-informed counterfactuals.
ATEX-CF: METHODOLOGY FOR COUNTERFACTUAL GENERATION
Our objective is to design counterfactual explainer that simultaneously incorporates edge addition (E*) and edge deletion (E"). combining GNN adversarial attacks with counterfactual explanation concepts. This explainer should generate high-impact perturbations while maintaining interpretabil- ity and realism. In particular, we jointly optimize three core objectives: Impact efficacy in altering model predictions: Sparsity minimal edits for interpretability; Plausibility semantic validity of graph modifications. Figure illustrates the end-to-end architecture of our ATEX-CF framework, which unifies adversarial edge perturbations with counterfactual explanation generation through a joint optimization of impact, sparsity, and plausibility.
2
To operationalize these objectives, we cast counterfactual generation an optimization problem over edge perturbations. Given candidate set S of feasible edge edits, we search for AA E S that flips the prediction of the target node while balancing sparsity and plausibility. This is achieved by defining composite loss with three components, corresponding to our objectives.
Loss Function. We formulate counterfactual generation as
min ((AA) Apred AA) + beLdie( + AsLplau (AA), AAES
where S is the candidate search space. Here Cpred enforees label flipping. Latet penalizes the number of edge edits, and Cplou enforces plausibility constraints. Weights X, 2 0 balance these terms. Next, we will define each loss function.
Prediction Loss. We denote by f(A,, X.; W) the prediction for node v under the original adja- cency A,, and by A(A,,, X., W: AA) the prediction under perturbed adjacency A, @ AA. Both share the same weights W: the difference lies only in the perturbation AA.
To encourage prediction flips, we define the loss as
Sprea(AA) - T[S(A X.: W) ((A, O AA W)] (A X,; W), ((,,, X,,,,, W; (2)
The indicator ensures that the loss is active only when the perturbed graph yields the same prediction as the original. that case, the negative log-likelihood term penalizes the perturbed prediction, pushing away from the original class. Once flip occurs, the loss becomes zero. Although this objective is non-differentiable due to the discrete nature the indicator function, we employ the ttraight-through estimator (STE) enable gradient- gradient-based optimization, detailed in $4.2
Sparsity Loss. To encourage concise and interpretable modifications, we impose a sparsity penalty on the number of structural edits. Specifically, minimize the fa norm of the adjacency change
5

---

Published as a conference paper at ICLR 2026
AA AE UAE where AE+ and AE denote the sets of added and removed edges, respec- tively. Edist (AA) = |A
The objective (AA) measures the total number of edits. By requiring || to be small, keep the modified graph close to the original, curb unnecessary complexity, and reduce overfitting.
Plausibility Loss. When generating counterfactual graphs by adding/removing edges, must trol the plausibility of the produced structure. For example, in a citation graph, an old article cannot cite more recent article. The plausibiliity penalty discourages unnatural degree/motif changes: Liseaul (AA) C(AA) Oldeg DegAnom (AA) + Ommtti MotifViol(AA). We tune Oldeg and Ofmotii enforce realism; larger Oldeg avoids implausible degree jumps, larger Omotif avoids implausible clustering jumps.
Idegā,, (v:) - dega., (vi)
DcgAnom(AA)=
Σ
(3)
1 + dega., (14)
V.VVsb
MotifViol(AA)= = Σ
IcA., (2)) - -C.,, (1:)1-
(4)
DegAnom penalizes large relative changes in node degree prevent structural anomalies, where degA (v) and dega(v) (v) are degrees node e before and after modification. MotifViol penalizes drastic changes in local motifs, measured via clustering coefficients CA. (v) and cx, (v).
4.1 CANDIDATE SELECTION
As key aspect in ATEX-CF, we constrain the search space of possible perturbations AA to pre- selected candidate set S. This tractable set constructed through a dual mechanism that incorpo- rates both local neighborhood structures and non-local, attack-informed candidates, balancing interpretability with the ability to discover impactful counterfactuals.
Edge Deletion Candidates (S)): We follow the principle of actionability and plausibility (Wachter al. 2017; counterfactual explanations should suggest meaningful changes within an entity's sphere of influence (e.g.. local graph neighborhood), rather than involving arbitrary, distant entities. As result, candidate edges for removal are restricted to the existing edges within the (1 ( 1)-hop neighborhood (w)+((w) of the target node v, i.e., S = {e
E, E (1+1(v)))
Edge Addition Candidates (S+): To overcome the limitation of deletion-only approaches and incorporate insights from adversarial attacks, our key innovation is draw candidate edges for addition from adversarial attack subgraphs. Specifically, we employ the latest GOTTACK method (Alom et al. 2025) to generate set of candidate edges AAaaac for the target node GÓTTACK idntiifies influential nodes for edge addition by learning the graph orbit characteristics of nodes that, when connected v, maximally increase the probability of misclassification. An orbit in graph theory represents the role of a node within its local substructure (e.g., central node in a star graph). The underlying Hypothesis M of GOttack, validated by our experiments in Table T8 is that nodes occupying similar structural roles (orbits) often have similar predictive influences on the target node. Therefore, edges suggested by GOTTACK (connecting nodes in specific, influential orbits) are both highly impactful and structurally coherent.
The complete candidate set the union S S+ The adjacency matrix A, for the local subgraph used in subsequent optimization (Eq. then formed by combining the original (f+ 1)-hop neighborhood structure of u and the adversarial perturbation candidates:
Final Candidate Set and Local Graph Formation:
AG
A Aattack
(5)
local strneture
adversarial perturbations
This formulation provides a focused and principled search space S that is crucial for the efficiency
and effectiveness of our counterfactual search algorithm. We use the (1 + 1)-hop neighborhood because an [-layer GCN aggregates information from nodes up / hops away; including the (1 + 1)- hop ensures that all nodes and edges within the target's effective receptive field- includnnl those that can indirectly influence its representation-aaa considered candidates.

---

Published as a conference paper at ICLR 2026
4.2 LIGNED-MASH PERTURBATION AND FORWARD DISCRETIZATION
After candidate edges are selected, the challenge is to optimize over the discrete choices of additions and deletions. Since direct optimization of binary graph structures is non-differentiable, we employ a continuous signed mask relaxation. In the forward pass, the mask is discretized into {-1, 0, +1} to yield concrete perturbations, while in backpropagation, the straight-through estimator treats this step as identity, allowing gradients to propagate through discrete edge decisions. This process is carried out follows and the complete ATEX-CF framework is given in Alg.
Each candidate edge e E S (where is the candidate set defined in $4.1 is associated with a continuous signed parameter Me E [-1,1] (Line of Alg. D This parameter encodes both the directionality and the magnitude of the proposed modification; a signed mask variable M, encodes perturbations, with Me > denoting an edge addition E AEt), Me denoting an edge dele- tion (e E AET), ) and Me x 0 no modification. Here, the sign of M. indicates the type of operation (addition or deletion), while the magnitude |M& reflects the proposed strength or importance of the perturbation. This continuous representation facilitates gradient-base based learning.
During the forward pass, we discretize these continuous parameters to obtain a binary perturbation matrix. This process involves two steps: thresholding and sparsity enforcement. First, we apply thresholding to convert Me into a ternary value. The discretized mask obtained by thresholding,
M, = +1 if Me > r+, M, = - if M, < - and Mr = otherwise (Line 3
Alg. 11
where 7+ and T- positive thresholds that control the sensitivity for edge addition and deletion, respectively. Typically, we set r+ r- = 0.5 to ensure symmetry.
Next, to enforce the perturbation budget constraint ||Allo I K, we retain only the x edges with the largest magnitudes [M&ll and assign their discretized values Me {-1,0, 0,1 to the corresponding entries in the adjacency matrix (Line g of Alg. D. The perturbation matrix defined as A A Me edge (i,5) is among the top-x candidates ranked by [Mel. and otherwise. This ensures that at most K edges are modified, producing sparse and interpretable counterfactuals.
Algorithm 1: ATEX-CF: Counterfactual Generator
Require:
Graph G = (A, X), model f, target node v, candidate set S 1: Initialize mask M, + 0 over S
2: for t = 1 to Tmax do
3: Me f- (HRESHOLD(M,, r+, r+,
Discretize
4:
AA TOP-x( [Mal)
Sparsify
5:
Evaluate ((M,) on A @ AA
6:
M M - V DiVMCC(LA C(M) > Update via STE
7:
if flipped(t) and ||AA|p lo stable then break
The objective loss and resulting perturbed
9: end if
adjacency matrix is then computed A 10: end for
A O AA, where the operator @ applies the signed edge modifications encoded
11: return PRUNE(AA, PRUNE(AA,G,J,0)
D See Alg
Me E {-1,0, +1} (Line 5 of Alg. Ip. To maintain differentiability through this discretization
step, we employ the traight-throusg gradient estimator (STE) during backpropagation 2M, 1. This approximation (Line Z of Alg. [ allows gradients flow directly through the binarization operation, treating the discretization as if it were an identity function in the backward pass (Bengio al. 2013). Consequently, the continuous parameters Me can be updated using gradient descent, even though the forward pass involves non-d con-differentaall operations. This approach is widely used in training binary neural networks and has been shown to be effective in practice. The loop stops early if the target node flips and the perturbed edges || | are stable (Line of Alg. D
Minimality-Aware Post-Hoc Pruning While the training loss promotes sparsity and plausibility in expectation, the discrete relaxation can leave redundant edges active in AA. This occurs mostly due to noisy or approximate gradient updates that over-compensate. To enforce the minimality of coun- terfactual explanations, we adopt simple yet effective greedy algorithm (Alg. 2 in Appendix A.4). Edges in the candidate set are ranked by their importance score v/e x |aC/JM, (approximated gradient magnitude at line 2 of Alg. 2 The algorithm then iteratively removes the least important edge, checking if the prediction flip persists (Line B of Alg. (). This continues until no more edges can be removed without reverting the prediction, and it attains final perturbation A
7

---

Published as a conference paper at ICLR 2026
5 EXPERIMENTS
5.1 EXPERIMENTAL SETUP
Table 2: Dataset statistics.
Dataset
Homophily Ratio
#Nodes
#Edges
#Features
#Classes
Type
BA SHAPES Ying el al.
2019
0.80
700
3958
Synthetic
TREE-CYCLES Ying
1,940
Synthetic
Synibetic
Cora Sen
2005
0.81
2,708
5,429
1,433
7
Real
Chamelcon
cl 2020
0.24
2,277
36,101
2,325
5
Real
Ogba-Arxiv
Hu et
2020
0.66
169,343
1,166.243
128
40
Real
Datasets. We evaluate ATEX-CF on both synthetic and real-world benchmarks. Synthetic datasets include BA-SHAPES and FREE-CYCLES (Ying al. 2019), widely used GNN explainability. and the Loan-Decision social graph (Ma et al. 2025). For real-world evaluation,
the Cora citation network (Sen et al. 2008 and the large-scale ogbn-arxiv dataset from OGB (Hu et al. 2020). Additionally, we include the heterophilic Chameleon dataset (Rozemberczki et al.) 2021 which is known for its low feature homophily and non-community structure, providing a challenging real-world setting for counterfactual explanations.
GNNs. We evaluate our approach on three standard GNN architectures: GCN (Kipf & Welling
2017). GAT (Velickovic et al. 2018). and Graph Transformer (Shi al. 2021p
Baselines: We compare our method against a comprehensive set of baseline approaches, which
categorize into two groups. The first group comprises explanation-basel baselines: CF-
GNNExplainer (Lucic et al. 2022). CF2 (Tan et al. 2022) and NSEG (Cai et al. 2025). coun-
terfactual methods that optimize for edge deletions using perturbation mask; INDUCE (Verma
et al. 2024), an inductive counterfactual framework that learns structural interventions through local subgraph rewiring. and can naturally realize both edge deletions and edge additions; C2Explainer
MM et al. 2025), customizable mask-based counterfactual explainer that jointly optimizes edge and feature perturbations under flexible constraints, supporting both removal and insertion of edges. GNNExplainer (Ying et al. 2019). factual explainer adapted for counterfactual analysis by re- moving edges in descending order of importance until prediction flips; and PGExplainee (Luo) ct al. 2020), another factual method adapted similarly to GNNExplainer. The second group consists of attack-based baselines repurposed for counterfactual generation: Nettack Züggner et al. 2018), white-box adversarial attack method adapted by using its edge perturbation capability such that the target class is different from the original prediction; and GOttack (Alom er al.) 2025), a recent adversarial method that leverages graph orbital theory identify critical nodes for edge additions, making it naturally suited for generating addition based counterfactuals. For fair comparison, all methods are constrained
default perturbation budget (i.e., maximum possible number of edge methods (CF-
flips) of x = 5 edges. We vary к for ablation study in Figure 3 Explanation- GNNExplainer, GNNExplainer, PGExplainer) are restricted edge deletions only, while attack- based methods (Nettack, GOttack) and our ATEX-CF can use both edge additions and deletions within the same budget.
In our experiments, we ran each experiment with three different random seeds (102, 103, and 104), and report the mean and standard deviation across runs. For the attack model, we employed evasion attacks using the GOttack method. For the ATEX-CF, 200 epochs, and adopted the SGD optimizer to generate counterfactual explanation with a maximal perturbed budget of 5 edges. The default loss weights were configured as follows: A 1.5,
used learning rate of 0.001, trained for
X = 0.5, A = 0.3, Oldeg = 1.5, and Omotss = 1.0. These hyperparameters were chosen to balance prediction flipping, sparsity, and plausibility in counterfactual generation.
Evaluation Metrics: We evaluate the performance of counterfactual explainers in misclassification
rate, fidelity, explanation size, plausibility, and time costs. Definitions are given in Appendix A.5
8

---

Published as a conference paper at ICLR 2026
Table Meta Results. Average ranks (4) across six datasets (lower better). Ranks are computed metric per dataset (best=1; ties get the same rank), then averaged across datasets equally. "Wins" counts how many times a method achieved rank one across all metric-dataset cells (6 datasets metrics 30 cells, ties allowed).
Method
Misclass.
Fidelity
AE
Plausibility
Time (sec)
Overall Avg.
Wins
CI-GNNEspaainer
4.7
4.8
2.0
2.3
9.5
4.67::2.68 68
INDUCE
6.3
6.8
4.5
7.8
2.8
5.67.11.78
C2Explainer
5.0
6.2
5.7
5.8
8.7
6.27:1: .66
CF2
7.0
7.0
6,7
5.7
7.8
6.83:1:0700
NSEG
6.37.11.07
GNNExplaincr
5.5
5,57+11.49
PGExplainer
7.7
4.2
5,8
5.37:22.60
Netlack
3.3
2.5
8.8
8.0
4.5
5.43.12.55
GOttack
4,8
4.3
8.8
8.0
3.0
5.80+22.23
ATEX-CR (ours)
1.3
1.0
1.2
2.40-12.477
Mondons.
2.
The 0e0
Plossiiity
JE
3
7
18
15
10
15
10
Perturbution Budges N
Pertrraatoon Budget X
Partucbation Budast
K
Porturtation Budest K
Portrbation Budact N
Figure 3: Counterfactual explanations on Cora and GCN under varying perturbation budgets x:
5.2 RESULTS AND ANALYSIS
We evaluate ATEX-CF against all baselines under the same budget constraints (w (1,....5)) 5)). Ta- ble summarizes average rankings across datasets and metrics. Our method achieves the best overall rank (2.40 vs. 4.67 for the next best) and wins 20/30 metric dacaset combinations, far exceeding competitors. This confirms that ATEX-CF consistently finds more effective counterfactuals. In par- ticular, counterfactual explainers (CT-GNNExplainer, CF NSEG, GNNExplainer, PGExplainer) are limited to edge deletions, while counterfactual explainers (INDUCE, C2Explainer), adversarial attack methods (Nettack, GOttack) and ATEX-CF also add edges. Crucially, CF CF-GNNExplainer explicitly seeks minimal edge deletions, and GOttack systematically manipulates graph orbits to in- duce errors, yet neither matches ATEX-CF combined effectiveness and realism. Our empirical results on individual datasets and with other GNNs (GAT and Graph Transformer) are given in Appendix A.7.
Figure plots performance vs. perturbation budget on Cora. As the budget grows, all methods improve: ATEX-CF quickly raises misclassification (e.g., from 0.46 ==1 0.76 <=15) far above others, and maintains the highest fidelity and plausibility. Notably, ATEX-CF 's edit size increases only mildly with K, whereas attack baselines must exhaust all allowed edits (AE-+5). This trend illustrates that our objective effectively exploits additional budget to find better counterfactuals without excessive edits.
Ablation Study. Table 15 in Appendix A.9 shows the effect of removing each loss. Our find- ings demonstrate that Liist enforces concise edits, Eytan preserves semantic plausibility, and their combination in ATEX-CF achieves the best overall balance across all metrics.
Sensitivity Analysis. We next analyze key hyperparameters. Search depth (0): Figure 4 in Ap- pendix A.10 shows that / - captures sufficient local structure surrounding the target node for effective counterfactuals. Hyperparameters (Ahdegs amoti ) Figure 5 in Appendix A.10 demon-
strates that ATEX-CF is robust across range of hyperparameter values (e.g., 0.5 l); while moderate a maximizes fidelity and plausibility together.
Impact of Pruning Strategy. We also evaluate the impact of our candidate-ede edge pruning strategy (Algorithm D in Appendix [A.4]. As shown in Figure O pruning yields more concise explanations by reducing redundant edge edits (AA 1.71 1.62), but intended, its real utility the reduced

---

Published as a conference paper at ICLR 2026
runtime (6.12s + 3.00s), while preserving predictive accuracy (misclass.=0.71), plausibility (0.76 vs. 0.75), making an effective and efficient enhancement of our framework.
5.3 ASYMMETRIC COSTS OF EDGE PERTURBATIONS
Feasibility of Edits. While framework assumes that edge additions and deletions possi- blc, not all structural edits are equally realistic in every domain. For example, in citation networks, adding an edge between two papers may be implausible after publication. To handle this, we incor- porate a real-valued cost metric into our optimization that allows domain-speciff constraints on edit feasibility.
The default perturbation budget in ATEX-CF CF assumes symmetric costs for edge additions and dele- tions, treating both equally under the constraint || || loo | & | S K. To account for scenarios where additions may be less actionable more expensive (e.g., in real-world graphs with immutable structures), we introduce a scalar weight C > control cost asymmetry between perturbation types. The new constraint becomes:
C CAI
||
AE S
We vary C over a range values (from 0.5 to 21.0) to analyze how penalizing edge additions affects counterfactual quality. Table 4 reports results Cora using GCN under budget setting: 20.
More results under different x are provided in Appendix A.13 A.13
Table 4: Counterfactual performance under asymmetric addition cost C' with 20.
Addition Cost
Deletion Cost
Misclass.
Fidelity
AE (E+, ET)
Plausibility?
Time (sec)
0.5
1.0
0.70
0.23
1.78 (0.78, L.00)
0.72
6.1
0.8
1.0
0.70
0.23
1.78 (0.77, 1.01)
0.71
6.1
1.0
1.0
0.70
0.23
1.78 (0.77, 1.01)
0.71
10.3
3.0
1.0
0.70
0.23
1.82 (0.66, 1.16)
0.69
10.7
5.0
1.0
0.70
0.23
1.82 (0.65, 1.17)
0.69
10.9
10
1.0
0.69
0.23
1,80 (0.61, 1.19)
0.69
11.0
15
1.0
0.69
0.23
1.76 (0.60, 1.16)
0.69
11.0
1.0
0.54
0.15
1.42 (0.49, 0.93)
0.68
11.5
21
1.0
0.42
0.10
1.78 (0.00, 1.78)
0.62
11.7
As the addition cost C' increases relative to the deletion cost, the optimizer favors deletion-heavy or deletion-only solutions. This leads trade-off: higher C reduces misclassification success and fidelity, and in extreme cases (C' 2 20), restricts exploration to only deletions, thereby weakening plausibility. These results confirm that asymmetric weighting serves as an effective control knob for tailoring explanation strategies in cost-sensitive domains, but also warn against overly skewed values that impair explamation quality.
CONCLUSIONS
We presented ATEX-CF. theoretically grounded framework that unifies adversarial attacks and counterfactual explanations for graph neural networks. By incorporating both edge additions and deletions under constrained budget, ATEX-CF generates explanations that are not only faithful but also informative. Our joint optimization of fidelity, sparsity, and plausibility ensures instance- level counterfactuals that balance interpretability with realism. Experiments on synthetic and real- world benchmarks confirm the effectiveness of this integration, highlighting how adversarial insights can substantially improve the quality of counterfactual explanations, compared with state-of-the art counterfactual generation and adversarial attack methods. Future directions include extending ATEX-CF to dynamic graphs, incorporating node feature perturbations, and applying the framework real-world domains like healthcare and finance.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Carlo Abrate and Francesco Bonchi. Counterfactual graphs for explainable classification of brain networks. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discov- ery and Data Mining. pp. 2095-2222992 2504. ACM, 2021.
Carlo Abrate, Giulia Preti, and Francesco Bonchi. Counterfactual explanations for graph classifica- tion through the lenses of density. In Proceedings of the International Conference on Explainable Artificial Intelligence, volume 1901 of Communications in Computer and Information Science, pp. 324-348. Springer, 2023.
Chirag Agarwal, Owen Queen, Himabindu Lakkaraju, and Marinka Zitnik. Evaluating explainability for graph neural networks. CoRR, abs/2208.092 09339, 2022.
Md. Zulfikar Alom, Tran Gia Bao Ngo, Murat Kantarcioglu, and Cuneyt Gurean Akcora. Gottack: Universal adversarial attacks on graph neural networks via graph orbits learning. In Proceedings of the International Conference Learning Representations: OpenReview.net, 2025.
Yunsheng Bai, Hao Ding, Ken Gu, Yizhou Sun, and Wei Wang. Learning-based efficient graph similarity computation via multi-scale convolutional set matching. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 3219-3226. AAAI Press, 2020.
Mohit Bajaj, Lingyang Chu, Zi Yu Xue, Jian Pei, Lanjun Wang, Peter Cho-Ho Lam, and Yong Zhang. Robust counterfactual explanations graph neural networks. In Advances in Neural Information Processing Systems, pp. 5644-5655, 2021.
Yoshua Bengio, Nicholas Léonard, and Aaron C. Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. CoRR, 0obs/1308.3433 2013.
Christian Borgs, Michael Brautbar, Jennifer T. Chayes, and Brendan Lucier. Maximizing social in- fluence in nearly optimal time. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 946-957. SIAM, 2014.
Ruichu Cai, Yuxuan Zhu, Xuexin Chen, Yuan Fang, Min Wu, Jie Qiao, and Zhifeng Hao. On the probability of necessity and sufficiency of explaining graph neural networks: A lower bound optimization approach. Neural Networks, 184:107065, 2025.
Dibaloke Chanda, Saba Heidari Gheshlaghi, and Nasim Yahya Soltani. Explainability- adver- sarial attack graphs through edge perturbation. Knowl. Based Syst., 310:1 12895, 2025.
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 embed- ding models. Proceedings of the AAAI Conference on Artificial Intelligence, pp. 3389-3396. AAAI Press, 2020.
Jinyin Chen, Yangyang Wu, Xuanheng Xu, Yixian Chen, Haibin Zheng, and Qi Xuan. Fast gradient attack on network embedding. CoRR, 0bs//809.0079)) 2018.
Tingyang Chen, Dazhuo Qiu, Yinghui Wu, Arijit Khan, Xiangyu Ke, and Yunjun Gao. View-based explanations for graph neural networks. Proc. ACM Manag. Data, 2(1):40:144::77, 2024.
Zhaoliang Chen, Zhihao Wu, Ylli Sadikaj, Claudia Plant, Hong-Ning Dai, Shiping Wang, Yiu-Ming Cheung, and Wenzhong Guo. Adedgedrop: Adversarial edge dropping for robust graph neural networks. IEEE Trans. Knowl. Data Eng., 3709):94484461 2025.
Chirag Chhablani, Sarthak Jain, Akshay Channesh, Ian A. Kash, and Sourav Medya. Game-theoretic counterfactual explanation for graph neural networks. In Proceedings of the ACM Web Confer- ence, pp. 513-514. ACM, 2024.
Susanne Dandl, Christoph Molnar, Martin Binder, and Bernd Bischl. Multi-objective counterfactual explanations. In Proceedings of the International Conference Parallel Problem Solving from Nature (PPSN), volume 12269 of Lecture Notes in Computer Science, pp. 448-469. Springer, 2020.
11

---

Published as a conference paper at ICLR 2026
Khoa D. Doan, Saurav Manchanda, Suchismit Mahapatra, and Chandan K. Reddy. Interpretable graph similarity computation via differentiable optimal alignment of node embeddings. In Pro- ceedings of the ACM SIGIR Conference Research and Development in Information Retrieval, pp. 665-674. ACM, 2021.
Lukas Faber, Amin K. Moghaddam, and Roger Wattenhofer. When comparing to ground truth is wrong: On evaluating GNN explanation methods. Proceedings of the ACM SIGKDD Interna- lional Conference on Knowledge Discovery and Data Mining, pp- 3322-341, ACM, 2021.
Wenqi Fan, Han Xu, Wei Jin, Xiaorui Liu, Xianfeng Tang, Suhang Wang, Qing Li, Jiliang Tang, Jianping Wang, and Charu C. Aggarwal. Jointly attacking graph neural network and its explana- tions. In Proceedings of the IEEE International Conference on Data Engineering, pp. 654-667. IEEE, 2023.
Timo Freiesleben. The intriguing relation between counterfactual explanations and adversarial ex- amples. Minds Mach., 32(1):77-109, 2022.
Dimitri Galli, Andrea Venturi, Isabella Marasco, and Mirco Marchetti. Evaluating explainability of graph neural networks for network intrusion detection with structural attacks. In Proceedings of the International Conference on IT Security Security and Reliability in Communication and Information Systems, volume 3962 of CEUR Workshop Proceedings. CEUR-WS WS..rg, 2025.
Simon Geisler, Tobias Schmidt, Hakan Sirin, Daniel Zügner, Aleksandar Bojchevski, and Stephan Günnnemann. Robustness of graph neural networks at scale. In Advances in Neurul Information Processing Systems, pp. 7637-7649, 2021.
Kangjia He, Li Liu, Youmin Zhang, Ye Wang, Qun Liu, and Guoyin Wang. Learning counterfactual explanation of graph neural networks via generative flow network. IEEE Trans. Artif. Intell., (9):4607-4619, 2024.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Ad- vances in Neural Information Processing Systems, 2020.
Zexi Huang, Mert Kosan, Sourav Medya, Sayan Ranu, and Ambuj K. Singh. Global counterfactual explainer for graph neural networks. In Proceedings of the ACM International Conference on Web Search and Data Mining, pp. 141-149. ACM, 2023.
Arijit Khan and Ehsan Bonabi Mobaraki. Interpretability methods for graph neural networks. In Pro- ceedings of the IEEE International Conference on Data Science and Advanced Analytics (DSAA), pp. 1-4, 2023.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In Proceedings of the International Conference on Learning Representations. OpenRe- view.net, 2017.
Mert Kosan, Zexi Huang, Sourav Medya, Sayan Ranu, and Ambuj Singh. Gefexplainer: Global counterfactual explainer for graph neural networks. ACM Trans. Intell. Syst. Technol. 16(5): 99:1-99:23, 2025.
Andreas Krause and Carlos Guestrin. Near-optimal observation selection using submodular fune- tions. In Proceedings of the AAAI Conference on Artificial Inielligence, pp. 1650-1654. AAAI Press, 2007.
Jiate Li, Meng Pang, Yun Dong, Jinyuan Jia, and Binghui Wang. Graph neural network explanations fragile. In Proceedings of the International Conference on Machine Learning, 2024.
Jiate Li. Meng Pang, Yun Dong, Jinyuan Jia, and Binghui Wang. Provably robust explainable graph neural networks against graph perturbation attacks. In Proceedings of the International Conference on Learning Representations, 2025.
Jintang Li, Tao Xie, Liang Chen, Fenfang Xie, Xiangnan He, and Zibin Zheng. Adversarial attack on large scale graph. IEEE Trans. Knowl. Data Eng., 35(1):82-95 2023.
12

---

Published as a conference paper at ICLR 2026
Yifei Liu, Chao Chen, Yazheng Liu, Xi Zhang, and Sihong Xie. Multi-objective explanations of GNN predictions. Proceedings of the IEEE International Conference on Data Mining, pp- 409-418. IEEE, 2021.
Antonio Longa, Steve Azzolin, Gabriele Santin, Giulia Cencetti, Pietro Lio, Bruno Lepri, and An- drea Passerini. Explaining the explainers in graph neural networks: a comparative study, ACM Comput. Surv., 57(5): 10:1::20:1-12::37, 2025.
Ana Lucic, Maartje A. Hoeve, Gabriele Tolomei, Maarten de Rijke, and Fabrizio Silvestri. Cf- gnnexplainer: Counterfactual explanations for graph neural networks. In Proceedings of the In- ternational Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 1499-4511 PMLR, 2022.
Kirill Lukyanov, Georgii Sazonov, Serafim Boyarsky, and Ilya Makarov. Robustness questions the interpretability of graph neural networks: what to do? CoRR, abs/2505.02566, 2025.
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. In Advances in Neural Information Processing Systems, 2020.
Jiali Ma, Ichigaku Takigawa, and Akihiro Yamamoto. C2explainer: Customizable mask-based coun- terfactual explanation for graph neural networks. In Proceedings of the ACM Conference Fairness, Accountability, and Transparency, pp. 137-149. ACM, 2025.
Jiaqi Ma, Shuangrui Ding, and Qiaozhu Mei. Towards more practical adversarial attacks on graph neural networks. In Advances in Neural Information Processing Systems, 2020.
Jing Ma, Ruocheng Guo, Saumitra Mishra, Aidong Zhang, and Jundong Li. CLEAR: generative counterfactual explanations on graphs. In Advances in Neural Information Processing Systems, 2022.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geomet- ric graph convolutional networks. In Proceedings of the International Conference on Learning Representations. OpenReview.net, 2020.
Mario Alfonso Prado-Romero, Bardh Prenkaj, Giovanni Stilo, and Fosca Giannotti. survey on graph counterfactual explanations: Definitions, methods, evaluation, and research challenges.
ACM Comput. Surv., 56(7):171 2024.
Dazhuo Qiu, Mengying Wang, Arijit Khan, and Yinghui Wu. Generating robust counterfactual witnesses for graph neural networks. In Proceedings of the IEEE International Conference Data Engineering, pp. 33331333336 2024.
Dazhuo Qiu, Jinwen Chen, Arijit Khan, Yan Zhao, and Francesco Bonchi. Finding counterfactual evidences for node classification. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2025.
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. J. Complex Networks, 9(2), 2021.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Collective classification in network data. Al Mag., 29(3):93-106, 2008.
Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjing Wang, and Yu Sun. Masked label prediction: Unified message passing model for semi-supervised classification. In Proceedings of the International Joint Conference Artificial Intelligence, pp. 1548-1554, ijcai.org, 2021.
Lichao Sun, Yingtong Dou, Carl Yang, Kai Zhang, Ji Wang. Philip S. Yu, Lifang He, and Bo Li. Adversarial attack and defense on graph data: A survey. IEEE Trans. Knowl. Data Eng.. 35(8): 7693-7711, 2023.
Juntao Tan, Shijie Geng, Zuohui Fu, Yinggiang Ge. Shuyuan Xu, Yunqi Li, and Yongfeng Zhang. Learning and evaluating graph neural network explanations based on counterfactual and factual reasoning. In Proceedings of the ACM Web Conference, pp. 0018-107.. ACM, 2022.
13

---

Published as a conference paper at ICLR 2026
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In Proceedings of the International Conference on Learning Representations. OpenReview.net, 2018.
Samidha Verma, Burouj Armgaan, Sourav Medya, and Sayan Ranu. Induce: Inductive counterfac- tual explanations for graph neural networks. Trans. Mach. Learn. Res., 2024, 2024.
Sandra Wachter, Brent D. Mittelstadt, and Chris Russell. Counterfactual explanations without open- ing the black box: Automated decisions and the GDPR. CoRR, abs/171 2017.
Zhitao Ying. Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. In Advances in Neural Information Process- ing Systems, pp. 9240-9251, 2019.
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey. IEEE Trans. Pattern Anal. Mach. Intell., 45(5):5782-5799, 2023.
Yi Zhang, Yuying Zhao, Zhaoqing Li, Xueqi Cheng, Yu Wang, Olivera Kotevska, Philip S. Yu, and Tyler Derr. A survey on privacy in graph neural networks: Attacks, preservation, and applications.
IEEE Trans. Knowl. Data Eng., (1:1)))7777775555 2024.
Zhiqiang Zhong, Anastasia Barkova, and Davide Mottin. Knowledgg--uugmented graph machine learning for drug discovery: A survey, ACM Comput. Surv., 57(12):300:1-3322388 2025.
Guanghui Zhu, Mengyu Chen, Chunfeng Yuan, and Yihua Huang. Simple and efficient partial graph adversarial attack: A new perspective. IEEE Trans. Knowl. Data Eng., 36($):4445-4259, 2024.
Xu Zou, Qinkai Zheng, Yuxiao Dong, Xinyu Guan, Evgeny Kharlamov, Jialiang Lu, and Jie
Tang. TDGIA: effective injection attacks on graph neural networks. Proceedings of the ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 2461-2471. ACM, 2021.
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 2847-2856. ACM, 2018.
14


Reviews:
[{"review_id": "iXNKXcHp1u", "reviewer": "Reviewer_7BBe", "summary": "This paper addresses a key limitation in GNN counterfactual (CF) explanations, CF methods relying only on edge deletion often cannot find a counterfactual, especially when the prediction hinges on the absence of certain edges. The authors propose ATEX-CF, a hybrid framework that intelligently combines edge additions and deletions. It first uses an adversarial attack (GOttack) to identify impactful candidate additions and then jointly optimizes both additions and deletions. It also prunes the resulting edits for minimality. The authors theoretically prove situations where deletions fail , and empirically show deletion only methods frequently fail on some datasets. Across synthetic and real world benchmarks (like Cora and ogbn-arxiv), ATEX-CF demonstrated higher flip rates with fewer, more plausible edits than existing CF and attack baseline.", "questions": "* Could you compare against recent non attack guided CF explainers that also use edge additions to isolate the benefit of the “attack informed” step?\n* It would be nice to ablate the candidate generation strategy (e.g., replacing attack guided edges with simpler heuristics such as random sampling, degree based, or feature similarity based candidates) to quantify how much this  guidance  step contributes to the final performance.\n* Can the framework handle domains where additions are infeasible or more expensive than deletions? Have you tried asymmetric action costs?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Strong theoretical and empirical evidence justifies including edge additions for counterfactual explainability.\n2. The attack guided candidate generation is innovative; the signed mask, STE, and pruning pipeline coherently addresses both search efficiency and plausibility.\n3. ATEX-CF achieves higher flip rates using fewer, more plausible edits across various datasets and GNN models.\n4. The work is framed as the first to bridge GNN adversarial attacks with counterfactual explanations, distinguishing it from prior deletion only or unguided addition methods.", "weaknesses": "1. The pipeline is complex and densely explained.\n2. The  additions and deletions are assumed to be equally feasible, asymmetric costs are not explored.\n3. Evaluation misses some recent counterfactual baselines that also permit additions, such as (InduCE: InduCE: Inductive Counterfactual Explanations for Graph Neural Networks | OpenReview ), slightly weakening the claim of empirical dominance.\n4. Released GitHub code is difficult for international researchers to reproduce, as some comments are in different languages other than english.\n5. Novelty claims (bridging attacks and CFs) are specific to GNNs; this conceptual link was explored earlier in other domains (e.g., The Intriguing Relation Between Counterfactual Explanations and Adversarial Examples | Minds and Machines  ).", "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": "RiybRX2v42", "reviewer": "Reviewer_wuaS", "summary": "This paper claims that existing counter-factual (CF) explanation methods for GNNs mainly focus on edge removing, while largely overlooking edge adding as a perturbation method. They explained (with examples) why edge adding is also important in counter-factual explanation, and also showed that GNN attack methods often employ edge adding as a perturbation method. Motivated by this, they combine edge removing (in conventional CF-Explaination methods) with edge adding (in GNN attack scenarios) to obtain a new method for GNN CF-explanation. Next, they perform experiments to study the effectiveness. While the idea looks interesting, I have some concerns regarding some claims and the experiment studies (please the weak points).", "questions": "Please see the weak points.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The idea is interesting. While some recent work also considered edge adding, it is still novel to use GNN attack as a source of obtaining edges to add;\n2. The paper is easy to follow as they spent many efforts to motivate their research and explain their methodology. However, the space left for the experiments looks relatively too short (this can be improved);\n3. The related work section (though in the appendix) is very detailed.", "weaknesses": "The experiments are not convincing due to two facts:\n\n1. They considered very limited baselines. Particularly, as a CF-explanation method, they only considered one method (CF-GNNExplainer) as a baseline. However, there are so many other CF-explanation methods (they also reviewed these methods in related work), including RCExplainer, GNN-MOExp, CF$^2$, NSEG, Banzhaf, CF-GFExplainer; INDUCE, C2Explainer, CLEAR, GCFExplainer, etc. (Actions: add more baselines in this category)\n\n2. The datasets considered are limited and may be flawed. They considered only five datasets, including BA-SHAPES, TREE-CYCLES, Loan-Decision, Cora, ogbn-arxiv. Besides, as pointed in [1], the explanations given in these datasets might not be reliable, using wrong/unreliable ground-truth to evaluate GNN explanation methods is not convincing [2]. (Actions: Discussion on potential issues of these datasets, adding more real or synthetic datasets)\n\nBesides, the authors claim that ``ATEX-CF generates explanations that are not only faithful but also informative.\" Without solving these potential flaws in the dataset, it is hard to say whether the explanations are \"faithful\". Moreover, without a real use-case, it is hard to judge whether the explanation is \"informative\". (Actions: investigating and solving/mitigating flaws in these datasets, providing a use-case)\n\nMoreover, although the authors have considered using plausibility loss to prevent generating out-of-distribution explanations, the OOD problem is actually very domain-specific. Avoiding implausible degree jumps and implausible clustering jumps (namely these techniques used in the paper) can only slightly mitigate these issues. (Actions: I would like to see more discussions regarding this and maybe other solutions to avoid generating OOD explanations).\n\n\n## Reference\n\n[1] Agarwal, Chirag, Owen Queen, Himabindu Lakkaraju, and Marinka Zitnik. \"Evaluating explainability for graph neural networks.\" Scientific Data 10, no. 1 (2023): 144.\n\n[2] Faber, Lukas, Amin K. Moghaddam, and Roger Wattenhofer. \"When comparing to ground truth is wrong: On evaluating gnn explanation methods.\" In Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, pp. 332-341. 2021.", "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": "FGDp6ULKTK", "reviewer": "Reviewer_GcK9", "summary": "The authors propose ATEX-CF, a counterfactual explainer for GNNs that leverages adversarial insights by allowing both edge additions (common in attacks) and deletions (common in counterfactuals). This increases flip probability under a small perturbation budget and aids interpretability: deletions assess the impact of existing connections, additions probe plausible new ones. The objective balances flip, sparsity, and plausibility, with plausibility penalizing degree and local motif jumps. Experiments span BA-SHAPES, TREE-CYCLES, Loan-Decision, Cora, and ogbn-arxiv.", "questions": "- How sensitive are results to the attack method? It would be interesting to replace GOttack with random-orbit, k-hop heuristics, or Nettack-style candidates and report deltas.\n- Why optimize an implausibility loss instead of pruning edits that violate constraints? It would be interesting to compare both.\n- Please report full metrics for each dataset (not only average ranks) for all κ values,, and include confidence intervals where missing.\n- Section 3 cites structural evasion. Why does the paper focus on it specifically? It would be interesting to discuss other attack types and whether conclusions change.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "- Originality: The paper connects adversarial edge additions to counterfactual generation, which usually uses edge deletions instead.\n- Solid optimization mechanics: The paper involves signed mask with ternary forward discretization, top-κ budget, and minimality-aware pruning that reduces edits/runtime while preserving flips/plausibility.\n- Reproducibility and robustness checks: Code and configs released with means/SDs across seeds; sensitivity and pruning analyses quantify stability and efficiency.", "weaknesses": "- Theory: “Hypothesis 1” is asserted as “proved” in the appendix but functions more as an assumption tied to empirical overlap; this weakens guarantees.\n- Plausibility metric is coarse: degree/clustering penalties may not capture domain constraints like temporal or type compatibility; evaluation reuses the same surrogate.\n- Dependence on attack generator: Candidate additions come from GOttack; robustness to this choice and ablations vs. simpler heuristics are unclear.\n- Scope: Only node classification; no feature-perturbation counterfactuals; limited real-world user studies for “plausibility.”\n(regarding format: Related Work is in Appendix A.2, not a proper main-text 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": "ng02EIvjMT", "reviewer": "Reviewer_M2c7", "summary": "The paper proposes the ATEX-CF framework, which applies adversarial attack techniques to help with the generation of counterfactual explanations, which explain what factors must differ in order to produce a different result. This is within the context of graph neural networks, where the counterfactual explanation addresses the least amount of changes to the graph needed to alter the model’s prediction on a node in the graph. Adversarial attacks have overlap with counterfactual explanations as these attacks focus on undermining GNNs by making deliberate minor changes to a graph to change a node’s predicted class. ATEX-CF specifically incorporates the technique of adding edges to a graph that is used in adversarial attacks, in addition to the edge deletion techniques used in counterfactual explanations. By incorporating edge additions, ATEX-CF can also capture previously missing relations between nodes, by adding in the edge that denotes the possible/probable relationship. The paper additionally is the first to make the connection between counterfactual explanations and adversarial attacks, and leveraging the two together to perform a task.", "questions": "What is the future with this framework or research, what are some future directions to take this or what further implications can be gleaned from this work?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The novelty or originality of the paper is a strength. This work is the first to make the connection between the techniques and goals of adversarial attacks and counterfactual explanations. Both involve either making or examining the minimal changes that can be made to a graph to change the outcome of a prediction made on that graph or its nodes. The paper leverages and highlights the similarity of the two methods in terms of objective to alter predictions and their approach of minimal alterations to the graph and consolidates them in order to improve on counterfactual explanations giving rise to their ATEX-CF framework. The usage of node deletion from traditional factual explanation generation and node addition from adversarial attacks enables the graph to capture previously missing relationships within the graph, by providing edges between nodes that have a plausible relation, and allows counterfactual explanations to overcome some limitations it previously faced with only node deletions such as overlooking the possibility of edges already missing within the graph. In addition to this, the paper incorporates sparsity and plausibility constraints into the framework in order to effectively add nodes into the graph with ATEX-CF. This paper can be significant in the way its method far outperformed other baselines and initiates a conversation of looking at counterfactual explanations with adversarial attacks and bridges a gap between the two topics which have evolved in isolation.\n\nThe quality of the paper does not lack either, it is a good quality paper, providing mathematical/theoretical backing for the proposed method ATEX-CF which is sound and logical and clearly sets up the problem definition and notation in section 2 so that the reader can follow along for the subsequent sections. The paper presents a quite comprehensive appendix to follow up on derivations of propositions in the paper and theory is formatted so that it is easy to read and follow. The paper is nicely structured such that the sections slowly build on and introduce the components involved in the ATEX-CF framework and the preliminary concepts and intuition for the framework are ordered so that the reader understands how the method is being developed. Also the inclusion of figures depicting the overall framework or examples of the interactions between nodes and edges help the reader gain intuition on the problem and solution being proposed by the paper. The framework employs preexisting techniques to tackle the defined problem such as GOttack which helps to generate candidate edges that would be used in adversarial attacks. Additionally, the authors make the source code involved available for others to reproduce the experiment and results. The experiments are performed on both synthetic and real world datasets demonstrating the ability of ATEX-CF to perform in real world situations and the usage of known benchmarking datasets/methods helps contextualize the performance of ATEX-CF. The experiment results support the notion of the proposed method’s effectiveness as it is able to outperform the baselines with the best (lowest) overall rank and wins 18/25 of the datasets, while other baselines don’t come close to this performance. Additionally, an ablation study is done to examine the effects of toggling different loss components in ATEX-CF and help outline what component influences the performance of the framework in a certain manner.", "weaknesses": "A minor weakness would be while the paper does mention the limitations to this study being the assumption of addition and deletion of edges in the graph always being possible when really, it may not be possible in some real world graphs, which would be the end goal of the framework to perform on, the limitation is only disclosed in the appendix. The paper would benefit from disclosing this information in the actual paper and providing some discussion on the limitation would inform the readers and allow them to understand the state of ATEX-CF. Although it is good to gear a future step towards eliminating this limitation which is mentioned in the section of the limitation in the appendix.", "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)