Graph Inverse Style Transfer for Counterfactual Explainability
Authors: Bardh Prenkaj
Efstratios Zaradoukas
Gjergji Kasneci
Venue: ICML 2025 poster (2025)
Keywords: Counterfactual Explanations
Style Transfer
Backtracking
Graph Structures
Explainable AI
Primary area: social_aspects->accountability_transparency_and_interpretability
TL;DR: Graph Inverse Style Transfer (GIST) pioneers the first-ever backtracking framework for graph counterfactuals, combining spectral style transfer with backward refinement to achieve realism and validity of the produced counterfactuals..

Abstract: Counterfactual explainability seeks to uncover model decisions by identifying minimal changes to the input that alter the predicted outcome. This task becomes particularly challenging for graph data due to preserving structural integrity and semantic meaning. Unlike prior approaches that rely on forward perturbation mechanisms, we introduce Graph Inverse Style Transfer (GIST), the first framework to re-imagine graph counterfactual generation as a backtracking process, leveraging spectral style transfer. By aligning the global structure with the original input spectrum and preserving local content faithfulness, GIST produces valid counterfactuals as interpolations between the input style and counterfactual content. Tested on 8 binary and multi-class graph classification benchmarks, GIST achieves a remarkable +7.6% improvement in the validity of produced counterfactuals and significant gains (+45.5%) in faithfully explaining the true class distribution. Additionally, GIST's backtracking mechanism effectively mitigates overshooting the underlying predictor's decision boundary, minimizing the spectral differences between the input and the counterfactuals. These results challenge traditional forward perturbation methods, offering a novel perspective that advances graph explainability.

Graph Inverse Style Transfer for Counterfactual Explainability
Bardh Prenkaj 12* Efstratios Zaradoukas'
Gjergji Kasneci
Abstract
Counterfactual explainability seeks to uncover model decisions by identifying minimal changes to the imput that alter the predicted outcome, This task becomes particularly challenging for graph data due to preserving structural integrity and se- mantic meaning. Unlike prior approaches that rely on forward perturbation mechanisms, we in- troduce Graph Inverse Style Transfer (GIST), the first framework to re-imagine graph counterfac- tual generation as backtracking process, leverag- ing spectral style transfer. By aligning the global structure with the original input spectrum and pre- serving local content faithfulness, GIST produces valid counterfactuals as interpolations between the input style and counterfactual content. Tested on 8 binary and multi-class graph classification benchmarks, GIST achieves remarkable +7.6% improvement in the validity of produced counter- factuals and significant gains (+45.5%) in faith- fully explaining the true class distribution. Addi- tionally, GIST's backtracking mechanism effec- tively mitigates overshooting the underlying pre- dictor's s decision boundary, minimizing the spec- tral differences between the input and the coun- terfactuals. These results challenge traditional forward perturbation methods, offering novel perspective that advances graph explainability.
Lomt
P Iestalle
=
G
Figure 1. The "gist" of GIST. Starting from an initial graph G E 9 G", we overshoot the other side of ' boundary on a randomly chosen graph G E G". We then learn a reverse pro- cess to backtrack from G a never-seen-before graph G' E g' while imitating the global structure or style (Cutyte) of G and main- taining faithful local structure and preserve content (Coons) ) with G Notice how Cstyle pulls the generation towards G, satisfying the similarity condition in Equation (3). Meanwhile, Leent pulls G to G since we do not want to cross the decision boundary again and produce an invalid counterfactual.
equipping their users and service providers with explainable components, usually post-hoe, allowing them to make in- formed and reliable decisions (Guidotti et al., 2018). How- ever, deep neural networks, commonly used for generat- ing predictions, often suffer from a lack of interpretability, widely referred to as the black-box problem (Petch et al., 2021), hindering their wide adoption in these domains. Reg- ulations such as the GDPR (European Union, 2016) and the EU AI Act (Furopean Union, 2023) emphasize the demand for models that provide interpretable and actionable insights into their predictions. Alas, black-box models demonstrate superior performance and generalization capabilities when dealing with high-dimensional data to their inherently in- terpretable counterparts (Aragona et al., 2021; Diko et al., 2025; Flaborea et al., 2023a;b; Prenkaj et al., 2023).
1. Introduction
Explainability is no longer a luxury but a necessity.
(European Union, 2023)
High-stake domains such as healthcare (Amann et al., 2020), finance (Cernevičiené & Kabašinskas, 2024), and digital forensics (Shamoo, 2025) have seen an abrupt interest in
Recently, graph neural networks (GNNs) (Scarselli al., 2008) have achieved remarkable results in graph predic- tion tasks, such as community detection (Wu et al., 2022), link prediction (Wei et al., 2022). and session-base -baed rec- ommendations (Wu et al., 2019). Despite their remarkable performance, GNNs are black boxes, making them unsuit- able for high-impact and high-risk scenarios. The literature
"Equal contribution 'Technical University of Munich, Germany "Sapienza University Rome, Italy, Correspondence to: Bardh Prenkaj <bardhprenkajj95 @ gomi..com>.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Graph Inverse Style Transfer for Counterfactual Explainability
has proposed several post-hoc explainability methods to understand what is happening under the hood of the predic- tion models. Counterfactual explanations (Wachter et al., 2017) have emerged as a key element in meeting regulatory requirements, as they shed light on model decisions by pre- senting alternative scenarios that would result in different outcomes. Furthermore, to support explanations for GNNs, a recent field in Graph Counterfactual Explainability (GCE) has emerged
structure alignment and local content preservation, en- suring semantically valid counterfactuals. We argue that this opens a new perspective in generating counter- factuals, as the overshooting factor (critical in forward approaches) is controllable via the learning objective. 2. Theoretical Insights on Spectral Style Transfer. We establish a rigorous theoretical foundation for GIST by analyzing the spectral properties of graph Laplacians. Specifically, we prove key results, including bounds on the spectral gap and Frobenius norm differences under convex combinations of Laplacians, ensuring stylistically (w.r.t. imput) coherent counterfactuals. 3. Scalable and Flexible Learning Framework. GIST introduces a modular architecture that integrates transformer-basee graph convolutional layers and dif- ferentiable edge sampling, enabling efficient backtrack- ing. GIST supports variety of GNN backbones, mak- ing it adaptable to diverse application domains while maintaining strong theoretical guarantees.
al., 2023).
Existing solutions in GCE learn forward! perturbation mechanism to produce a counterfactual w.r.t. an underlying decision model, hereafter called oracle + One obvious drawback of trying to forwardly cross D 's decision bound- ary involves using t in the learning process (training) - e.g., see (Prado-Romero et al., 2024b) which might not be feasible in scenarios where its predictions are limited by design.² 2 A strictly forward learning approach can discard essential partial structure in the data by always starting from an uninformative initialization, rather than building upon already available signals. Without incremental corrective feedback, often removes valid relationships or overshoots the decision boundary, resulting in suboptimal or oscillatory convergence. Furthermore, since this method lacks a mech- anism to selectively preserve beneficial features during the transformation, it may converge to local minima that fail to retain important topological patterns. Consequently, the overall process can suffer from instabilities, inefficient ex- ploration of parameter space, and diminished preservation of informative characteristics in the produced counterfactual.
4. Comprehensive Empirical Evaluation. Extensive experiments on 8 benchmark datasets spanning syn- thetic and real-world graphs with binary and multi- class classification tasks emphasizes GIST as con- sistently outperforming SoTA. Specifically, GIST achieves considerably higher validity (+7.6% over the second-best best) and improves fidelity by a large margin (+45.5%). Our results highlight GIST's ability to gen- erate counterfactuals that are both more faithful and spectrally aligned (preserved semanties) with the input.
To tackle these challenges, propose GIST, short for Graph Inverse Style Transfer, transformative framework, inspired by the principles of style transfer in computer vi- sion, that re-imagines counterfactual generation as a process of structural backtracking. By first overshooting o's deci- sion boundary and then refining the graph towards a desir- able configuration - i..., the input graph's spectral properties (style) GIST produces counterfactuals that preserve the original graph's s global style and local node/edge content.
2. Preliminaries
Graphs, their "style", and content. Let G = A) be graph consisting of node features X E Ruxd and an adjacency matrix A E R=x" representing the connectivity among nodes with weights in the edges. We denote the graph dataset with g = [GI....,GNy GN.. The Laplacian matrix of graph G is defined as
= A,
(1)
Specificallyy we go beyond the related work by making the following contributions:
where D is the degree matrix. The eigenvalues of [G) are denoted as A1 (L(()) I (2 < S An (L) The normalized Laplacian is defined as
1. First Graph Style Transfer Framework. We propose GIST, novel backtracking approach for graph coun- terfactual explainability. Unlike prior methods that forwardly cross the decision boundary, GIST leverages spectral style transfer to interpolate between global
i -
(2)
with eigenvalues X >₂ (I S {g(( S
..... .... N,, (I()))
'Throughout this paper we use "forward" and "backward" in their literal sense, and not refer to machine learning aspects. For the latter, we will refer to "forward learning pass" and "backward learning pass" to discern between the literal and ML mcanings. "Imagine deploying 4 '' inference function as an API call. Call- ing these APIs at every training step would saturate the network bandwidth or, worse, get the caller IP blocked for ToS violations.
Notice how the content of the graph is encoded in the node feature vectors, and the style is encoded in the eigenvalues, summarizing global structural patterns. Laplacians capture global structural patterns, e.g., connectivity and symmetry, that are largely invariant to specific node identities. This follows a similar rationale to neural style transfer in im- ages, where Gram matrices of feature activations are used
2

---

Graph Inverse Style Transfer for Counterfactual Explainability
to model style since they encode correlation patterns among features rather than spatial arrangements. Additionally, us- ing the Laplacian aligns with prior work in spectral graph theory, where the eigenvalues and eigenvectors of the Lapla- cian are shown to be robust descriptors of global structure, and have been used in graph matching (Yan et al., 2016) and generation (Dwivedi et al., 2023).
representing global texture, they lack flexibility in class- related structural properties. In contrast, GIST introduces a style representation that captures both local (input-specific) and global (class-related) structural patterns.
Natural Language Processing. Jhamtani et al. (2017) ex- plore automatic methods to transform text from modern to Shakespearean English. Their model is based on seq2seq and enriched with pointer network (Vinyals et al., 2015). They use modern-Shakespeen candidate words for pointer network. However, paired-word dictionaries are scarce resources that do not exist in most style transfer tasks, requiring parallel corpora. Mueller et al. (2017) propose a variational autoencoder (VAE) to revise a new sequence to improve its associated outcome. Shen et al. (2017) explore style transfer for sentiment modification, de- cipherment of word substitution ciphers, and recovery of word order. They use VAE as the base model and an ad- versarial network to align different styles. Braud & Søgaard (2017) explore many types of features for style prediction, ranging from n n-grams to discourse, and found that simple models perform well. Ficler & Goldberg (2017) control lin- guistic style of generated text using conditioned recurrent neural networks (CRNNs). Fu al. (2018) propose two models for text style transfer without parallel data: i.c., multidecoder sequence-to serrice-to-seee to-sequence model and style em- bedding model. In line with (Fu et al., 2018) GIST finds counterfactuals without relying on parallel data (i.e., graphs whose style to imitate). Rather, we use the input to guide the overshooting mechanism and then act as style which pulls the generation process towards it to preserve semantics.
Graph Counterfactuals. Given a black-box (oracle) pre- dictor &b 9 + Y, according to (Prado-Romero et al., 2023), counterfactual for G is defined
word dictionary to form
arg max G' (C)))
(G)
where G' is the set of all possible counterfactuals gener- ated by perturbing G, and S(G, G") calculates the similarity between G and G". Notice how it is trivial to express Equa- tion (3) in terms of graph distance instead of similarity function, which closely aligns with the counterfactual for- malization in historically (Wachter et al.. 2017). and more recently, (Leemann et al., 2024). Interestingly, Prenkaj et al. (2024) reformulate Equation (3) and take a probabilistic perspective to produce counterfactual that is quite likely within the distribution of valid counterfactuals,
arg max P (G' G, 2 (G), -2 (G)),
(4)
G'EG'
where (GG indicates any other class from (G))
3. Related Work
Our work directly relates to style transfer and graph coun- terfactual explainability, which we describe below. To the best of our knowledge, style transfer has never been defined or applied to graphs due to their inherent complex struc- tures. However, for completeness purposes, we include the most interesting style transfer works in computer vision and natural language processing.
3.2. Graph Counterfactual Explainability (GCE)
Prado-Romero et al. (2023) provide a detailed taxonomy of GCE methods composed of search-, heuristic- and learning- based approaches. Although global (model-level) counterfactual explanations is emerg- ing (Huang et al., 2023; Kosan et al., 2024), our focus remains on instance-level and learning-based explainers. Although RCExplainer (Bajaj et al., 2021) is a mixture of heuristics and learned approaches as per the taxonomy in Prado-Romerd et al., 2023) we include it here to ac- knowledge its value with its multiple learned linear decision boundaries and then the search over these boundaries to find robust explanations." 3
category of
3.1. Style Transfer
Gatys et al. (2016b) separate the content and style of images and combine them to generate new images. Gatys et al. (2016a) use a simple linear model to change the color of pictures by using a single image to represent the style. Zhu et al. (2017) propose CycleGAN to do image-image translation. It firstly learns a mapping G: X + Y using an adversarial loss, and then a reverse mapping F : Y + X with cycle loss F(G( which performs unpaired image to image translation. Li et al. (2017) treat style transfer as domain adaptation problem. They theoretically show that Gram metrics is equivalent to minimize the Maximum Mean Discrepancy (MMD) for images. While these approaches capture style by effectively
Computer Vision.
Unffrttnnttly, the official implementation could not be exc- cuted, as depends on proprictary Huawei Python packages that are not publicly available. Despite extensive debugging and ef- forts to adapt the code to the GRETEL framework (Prado-Romero et al., 2024a) in order to ensure consistency in the evaluation pipeline we were unable to reproduce the original results. Addi- tionally, we attempted use an unofficial implementation available at at http//gtttubbb con/ idea- pettttggtnnnn x gnn-x-bench/ b oobmmainn i sion lacks support for several benchmark datasets, including BBBP,
X
a .er.py. However, this ver-
3

---

Graph Inverse Style Transfer for Counterfactual Explainability
Leamningbaased Strategies include perturbation matri- ces (Tan et al., 2022), reinforcement learning (Numeroso & Bacciu,, 2021; Wellawatte et al.. 2022), and genera- tive approaches (Ma et al., 2022; Prado-Rod Homoo-Romero et al., 2024b). MEG (Numeroso & Bacciu, 2021) is a rein- forcement learning approach that generates counterfactuals for input molecules. Its reward function integrates task- dependent regularization, influencing the policy to select actions that lead to valid molecules (Zhou et al., 2019). CF- GNNEXp. (Lucic et al., 2022) learns binary perturbation matrix to sparsify the adjacency matrix of the original graph G. guided by sparse neural network (Srinivas et al., 2017). CF (Tan et al., 2022) balances factual and counterfactual reasoning via multi-objective optimization. Counterfactu- als are generated by removing the factual subgraph from the input and focusing on simplicity. CLEAR (Ma et al., 2022) employs VAE to generate counterfactuals com- plete graphs with stochastic edge weights, conditioned on the input graph and desired class. During decoding, a graph matching step is required to address vertex reorder- ing, an NP-hard problem (Livi & Rizzi, 2013). RSGG- CE Prado-Romero et al., 2024b) relies on a modified learn- ing approach of GANs and a partial-order sampling strategy on the learned edge distribution to generate robust graph counterfactual candidates. It exploits the generator to learn graph representation, enabling stochastic estimations of the graph's 's topology, thus allowing the generation of coun- terfactuals in zero-shot. Unrelated to graphs, Nemirovsky et al. (2022) use GANs to generate counterfactuals for user- defined classes, adapted in (Prado-Romero al., 2023) into G-COunteRGAN, treating adjacency matrices as black-and- white images with 2d convolutions.
direction without crossing it again. Figure illustrates the idea behind explainer. More formally, Definition 4.1 illustrates the conditions that counterfactual graphs found via style-transen transfrrannfr should meet.
Definition 4.1. Given graph G = (X,, s.t. n = [X] the goal is to generate G = (X*, A²) by passing through an intermediary known graph G = (X*, A²) E G with ((G) + ((G)), such that the following conditions are met.
(1) Style transfer the global structural properties of G* align with i.e..
S n
-((
Σ 1
(5)
(2) Content preservation - the local structure of G resem- bles G i.e.,
min G"
| | x-11
+ BCE (A'E A*)
(6)
reconstruct node feature
reconstruct existing and non-cxisting edges
Appendix B shows a simple overshooting algorithm used in this paper.
4.1. Theoretical Implications
Definition 4.2. Given ((0) and ( two real, symmetric and commuting matrices, the normalized I. Laplacian of G is defined the convex combination in Equation (7).
i = a + a1
(7)
where a E [0. 1] is the interpolation factor that controls the trade-off between content and style.
The SoTA methods follow forward perturbation paradigm (i.e., all learn how to cross 4's decision boundary). To the best of our knowledge, GIST is the first that learns a back- tracking mechanism (i.e., overshoot Ø's boundary first and then go backwards). By combining graph style transfer and counterfactual content preservation, GIST produces expla- nations that are spectrally and semantically aligned with the input, instead of merely similarity see Equation (3).
Lemma 4.3. Given ( and i( two real, symmetric and commuting matrices, the eigenvalues of G are defined as the convex combination
A,(i())) =a +(110)) - (8)
Lemma 4.3 illustrates that the convexity of the Laplacian operator ensures that eigenvalues interpolate linearly. In other words, we show that the structure of the produced counterfactual G" is an interpolation (balanced by a) be- tween the structural style (i.e., from the input G) and the class-related spectrum (i.e., from G+).
4. Method
We propose GIST (short for Graph Inverse Style Transfer), the first backtracking (inverse) mechanism towards the de- cision boundary of the oracle & instead of as- as-per-usual forwardly crossing it see (Numeroso & Bacciu, 2021; Ma et al., 2022; Prado-Romero et al., 2024b) among others. In other words, given a graph G, our goal is to shoot over 4's decision boundary and then move towards it in the opposite
Showing that the spectrum of G* is linear interpolation of those of G and Ge implies G" exhibits similar connectivity patterns to those of G and G Hence, if G and Ge are connected graphs (i.c., absence of isolated nodes), then also G is connected (see Theorem 4.4).
BZR, ENZYMES, MSRC21, and COLORS-3, hindering us di- reetly compare against other SoTA methods and GIST.
Theorem 4.4. G and G are connected graphs, then G* whose normalized Laplacian is defined as in Equation (7) is connected for any a E [0. 1).
*Code: https: / / thub. www/ hoom/barddhge http://aaddpeenaa/ggi.i.e
4

---

Graph Inverse Style Transfer for Counterfactual Explainabiliy
Theorem 4.5. Let A(G) - \a( ) (L(G)) denote the spectral gap of G. where >2 and A1 (T) are the second- and first-lowest eigenvalues of G. Then:
nature of edge decisions. To circumvent this, we adopt the Gunbel-Softmax relaxation (Jang al., 2017), enabling continuous approximations of binary sampling. Concretely, for an edge with predicted probability Pt.j. we introduce Gumbel noise I and compute
min min(A(G),A(G9) & A(") S (G)
Corollary 4.6. The Frobenius norm difference between G and G is
Li = o [log(pr.s +e) logg-logg--p--- +c)+ / T), (LI)
where is the sigmoid function, c is a small constant for numerical stability, and T is the temperature parameter con- trolling the "hardness" of the sample. During training, these soft samples Lt.j remain differentiable w.r.t. the network pa- rameters, thus allowing standard backpropagation to adjust node embeddings and edge probabilities. At inference time, one can threshold Lú (or sample via Bernoulli draw) to yield final, discrete adjacency matrix.
1 - -1-a))l - 1 (10)
Corollary 4.6 illustrates the bounded style similarity, i.e., the counterfactual G* cannot be arbitrarily dissimilar from the input, but is bounded to be similar to the difference of spectra between G and G controllable through a. In simpler words, if we imagine G. G", and Go as points on a ID-plane representing their spectra, then G must be in- between G' and G Appendix A contains omitted proofs.
4.2.2. RECOVERY OF G*
Once the edge probabilities are computed for each potential connection, GIST derives new edge set E which is a Bernoulli sample over 2i.i V(i,j). In this way, we can compute the spectral loss - ie.. L1 distance between the cigenvalues between the adjacency matrix A induced on E' and the original adjacency matrix A of G. Moreover, according to Definition 4.1, we also account for the content preservation between G* and G Therefore, given the graphs G and G,, taken from the forward overshooting procedure, GIST optimizes the loss in Equation (12).
4.2. Learning to Backtrack
Here, we describe how our proposed GIST model (see Al- gorithm 1 for the forward pass of the network, and Figure 2 for GIST's architecture) facilitates a reverse transformation from a perturbed or intermediate graph G to a refined struc- ture G" that better aligns with the target topology G. This process, which we call learning to backtrack, addresses the challenge of undoing distortions noise, in our scenario G introduced into the original graph G a critical step in tasks such as graph denoising (Zhou et al., 2024), and domain adaptation (Cai et al., 2024).
f= arg min G'=(X' 4.),
||x X=11 BCB( AF)
A "x=IE"" .. 20. (
4.2.1. ARCHITECTURE OVERVIEW
Lvont
Our architecture relies on two key ideas: i.e., (1) transformer-based node embeddings. and (2) edge prob- ability estimations to find G" starting from G
(a(((()) -
+(1-a)
Extyle
Transformer-basee Node Embeddings. We employ trans- former convolution layers (Shi et al., 2021) to learn node representations from the potentially noisy edges of G These layers are interleaved with ReLU activation func- tions which produce intermediate node embeddings for each vertex. These final node embeddings reflect the structural roles of nodes despite the "edge noise" present in G
(12)
where BCE(A", is defined in the second component of Equation (6), a E [0, 1] is the interpolation factor which pulls (pushes) towards (away from) the decision boundary of & w.r.t. G (G*), fo is the our network architecture, and gnn E) produces an adjacency matrix in R="x" based on the edge set E.
Edge Probability Prediction. Using the learned node em- beddings, we predict edge probabilities via a small multi- layer perceptron (MLP). Specifically, we concatenate the representations of any two nodes (i. and feed them to the MLP to estimate the likelihood of an edge (i, existing. This design effectively bucktracks from the corrupted edges by selectively reintroducing or discarding edges based on how consistent they are with the learned embeddings.
5. Experiments
5.1. Experimental setup
We compare GIST other SoTA learning-based explana- tion methods (i.e., CF-GNNEXp. (Lucic et al., 2022), CF2 (Tan et al., 2022), CLEAR (Ma et al., 2022), and RSGG-CE
'Here, we abuse the notation of graph introduced in Section 2, and indicate a graph G (V, FE) with its vertex set V and edge set
Differentiable Sampling and Backpropagation: A key ob- stacle in learning graph structure end-to-end is the discrete
5

---

Graph Inverse Style Transfer for Counterfactual Explainability
(G)
(1 a)
Lsyyye
i (c')
edge probs.
P1,3
TransformCon
X
TransfornCom
TransformConv
x
PA,
(G) GG))
Gumbel
overshoot
P4,5
A
G (X,,4)
G (X .9)
possible edges
BCE(A" )
X" X1
Figure 2. Overview of GIST's forward learning pass and backtracking optimization. Given a graph G (X, A). we use & to overshoot G = (Xe, Af) ((G) + (G)). We feed G' through transformer convolution layers that output node embeddings X". For each embedding, we create edge pairs and feed them to an MLP which estimates probabilities pi.- We can sample these probabilities compose adjacency matrix A". We maintain G faithfulness with C" by minimizing Leont, and spectral similarity with G by minimizing Lstyle. Overall GIST produces counterfactuals that strike balance (lincar interpolation) between G's spectrum (style) and the local properties (content) of G via aLcont + (1 a.) Lstyle-
Table 1. Average validity (the higher, the better) the test set over 5-cross validations. Bold-faced digits show the best performing strategy; underline is the second-best. depicts binary-classiffcatte scenario; & a multi-class scenario.
Real
Synthetic
AIDS
BBBP f
BZR f
ENZYMES $
MSRC21
PROTEINS
BAShapes
COLORS-3 $
iRand
0.013
0.151
0.332
0.134
0.035
0.018
0.000
0.392
CF-GNNEXp.
0.936
0.931
0.810
0.910
0.965
0.378
0.516
0.736
CF2
0.019
0.208
0.185
0.437
0.018
0.039
0.000
0.676
CLEAR
0.037
0.267
0.176
0.370
0.933
0.563
0.908
0.217
RSGG-CE
0.128
0.404
0.732
0,447
0.912
0.237
1.000
0.884
GIST
0.969
0.956
0.810
0.970
0.965
0.791
1.000
0.884
Table Average fidelity (the higher, the better) on the test set over 5-cross validations. Bold-faced digits show the best performing binary-classificationn scenario; 1 multi-class scenario.
strategy: underline is the second-best depicts
Real
Synthetic
AIDS
BBBP
BZR f
ENZYMES
MSRC21
PROTEINS
BAShapes
COLORS-3
iRand
0.013
0.177
0.146
0.004
-0.035
-0.009
0.000
-0.007
CF-GNNExp.
0.924
0.784
0.741
0.077
0.825
0.202
0.484
0.091
CF2
0.015
0.178
0.176
0.017
-0.018
0.018
0.000
0.065
CLEAR
0.050
0.164
0.127
0.040
0.855
0.051
0.060
0.033
RSGG-CE
0.124
0.286
0.683
0.050
0.807
0.133
0.968
0.147
GIST
0.957
0.809
0.741
0.203
0.860
0.425
0.968
0.202
(Prado-Romero et al., 2024b) in benchmarking datasets (Appendix D) for graph classification with different evalua- tion metrics (Appendix E) relying on the GRETEL frame- work GtradoRoomen et al., 2023a; 2024a). We adapted RSGG-CE and CLEAR, originally available only for binary,
to work in multi-class classifications scenarios. We rely on the iRand baseline (Prado-Romero al., 2023b) to verify whether the SoTA actually learns to produce valid counter- factual explanations random perturbations sufficient. We use the default hyperparameters for the SoTA explainers.
6

---

Graph Inverse Style Transfer for Counterfactual Explainability
Algorithm 1 Forward learning pass of GIST
0.960
Require: G (Xx,, (X*, .A)) with vertex set V and edge set
50
0.966
E, temperature T, noise I, model parameters number of attention heads h, number of convolution layers l
45
0.964
Ensure: X 2h. (i. E VVx,,
1: X +X
0.962
2: for = 1..1...d do
0.960
3: X* + ReLU U (TransformeeConv,,e ,1)
4: end for
0.958
5: Piùj - MLP, (X V(i,5) EV EVXV X
30-
GBD007 (C')
0.956
6: (i.j + GumbeeSSoftma (pis. T,T) V(i.)) EVXV
0.1
0.2
0.3
0.4
0.7 0.8
0.9
0.954
7: E* {(t.j) Bernoulli(Q.)) =1 Vei. Veis
8: Return: ,² E
Figure 3. As a + 1, the distance between G and G becomes larger; the distance between G and Go decreases. We show the relationship between the interpolation factor a, the GED, and the validity of G" as guided by the oracle & AIDS. Notice how the validity of GIST increases when the distance between G' and G increases.
and p .01 and t = 3 for iRand (Appendix C). Unless differently stated, we set = 0.9 for GIST. To generate explainations, we first train the underlying oracles- three- layered GCNs interleaved with ReI.U activation functions and use the same weights for all explainers to ensure fair performance comparisons. Table - Table 12 illustrate the accuracy of the oracles on the test sets of the datasets. We use 90:10 train-test split for all explainers and designate 10% of the training set as validation. We perform 5-fold cross validations to assess the performances of the explain- ers on one AMD EPYC 7002/3 64-Core CPU (for smaller models) and one Nvidia TESLA V100 (for larger models) totaling -450h of execution time.
According to Figure and the intuition of Corollary 4.6, we expect that, regardless of the value of the interpolation factor a, the counterfactual G", if imagined as point in a ID- D-pplan, must be in in-between G and G.. To support claim, we train GIST on 5-fold cross-validations on AIDS with changing E {0.1, 0.3, 0.5, 0.7, 0.9} and measure the GED and validity of the counterfactuals - see Figure 3. When a + 1, the GED between and G increases since, according to Equation (12), GIST "prefers" to stay nearby G As consequence, we expect that the GED between G and G decreases when - 1 (see the red curve). Fi- nally, we show that if the GED between G and G* is high, then GIST must have overshot "far away" from 4's bound- ary to reach G 6 Hence, the chance of finding a correct counterfactual is higher - i..., GIST has a higher validity.
5.2. Results
GIST has an average 7.6% gain over the second-best in terms of validity, and 45.5% fidelity. Table illustrates the validity of all explainers on binary and multi-class graph classification tasks. GIST outperforms SoTA explainers 4/8 datasets (+13.3%), performs par with CF-GNNEXp. on 2/8 and RSGG-CE on 2/8. Although validity measures the effectiveness of the explainers crossing the decision boundary, we also measure the fidelity of the produced counterfactuals w.r.t. the oracle (see Table 2). Notice that GIST, in COLORS-3, reports better fidelity that RSSG-CE (i.e., +37.4% improvement) although the latter has a similar validity. Finally, GIST is on par with CN-GNNE BZR and MSRC21 in terms of validity. However, we report an average gain of 2. 12% on fidelity, hinting that we are more faithful to the true class distribution (see Appendix E). We show all measured performances of the explainers for all datasets in Appendix G.
GIST finds counterfactuals whose eigenvalues are closely aligned to the optimal convex combination of Equa- tion (8). To demonstrate our theoretical findings, we in- vestigate the eigenvalues of G* in accordance to the optimal convex combination illustrated in Equation (8). Because GIST is a learning approach which minimizes Equation (12), it might happen that the spectrum the produced counter- factual G* is misaligned with the true combined spectra of G and G Figure 4 shows the spectra of 10 randomly chosen (G, G*) pairs from the AIDS dataset. Here, we il- lustrate the eigenvalues of G as produced by GIST, and the true combined spectra with a = 0.9. Notice how there is a directly proportional relationship between the GED see Figure 3 and the spectral combination of G*. There- fore, for a 0.9, we expect that the eigenvalues of G* are more aligned with those of G.. Indeed, the figure confirms
5.3. Ablation studies
The interpolation factor a controls the trade-off between the distances of G, G*, and Go, and the overall validity.
"Conceptually, GED G*) S G
7

---

Graph Inverse Style Transfer for Counterfactual Explainability
our intuition and shows how G is closely aligned with the true spectra combination, reporting an average error of only 2.051 x 10-3 for the reported samples (vs. 1.67 x 10-3 for the whole dataset). Note that the zeros in the figure are due to the padding between G and G to compute the spectral differences, which need the adjacency and degree matrices to be of same dimensions. To account for different graph sizes, in the future, we will explore the Wasserstein distance of the eigenvalues instead of L.1.
Figure 6. GIST produces G who are spectrally conformant to the style and local structure. For = 0.9, we illustrate 100 randomly chosen (G. C9) on PROTEINS, and measure the expected norm (1 z))l [I We also measure ||T I. ( "G""|| '|r on the predicted GO and report a negligible error of 6.04 10
orem 4.4. Figure 5 (left) shows the spectral gaps A (G))) ) and (GG") for 100 random samples of MSRC21 see Appendix G.3.2 for more datasets. Notice that ((G)) is always within the boundaries established in Theorem 4.5 and closely aligns with the optimal gap produced by the cigenvalues of the Laplacian from the convex combina- tion (G9L + 0.1L(G), reporting a gap error of only 1.3 x 10-2. For completeness purposes, in Figure 5 (right) we illustrate the first eigenvalues of G, G and the produced G Recall that a graph is connected if its first lowest eigen- value is connected (i.e., (L 0). Notice how the majority of G graphs is connected values to show in log-scale by adding the lowest eigenvalue that is non-zero thus, depicting (mostly) a horizontal line. However, because G is not always connected, then G* will also show A1 (G)) > 0. However, for fairness purposes, we notice that (L) and X (L( are only an epsilon away from zero (i..e, E [10-10] 10-$D, practically result- ing connected. Hence, per Theorem 4.4, in the optimal scenario, we expect that the first eigenvalue of the coun- terfactual is O. GIST generates G whose connectedness is close to the optimal with (I(G))) æ 5 x 10-3, See Appendix G.3.2 for other datasets, and Figure 9 for a qual- itative example of how two connected graphs G and G produce a connected counterfactual G"
Figure 4. GIST's backtracking mechanism finds G" with under 2.051 x 10-3 error vs. the optimal counterfactual in terms of spectra convex combination in Equation (8). We show the eigenvalues of 10 random (G, G*) pairs on AIDS, and the finding of G according to GIST with a = 0.9. We also illustrate the optimal counterfactual produced w.r.t the spectral convex com- bination (G*) + (G). Zeros in the figure are due to the padding between Gf and G to compute the spectral differences.
corrected zero
alp")
2nt A.y 5%% 2.15% Emor 0.005
Mant
The
10.00
GIST produces spectrally conformant counterfactuals. We show that the produced counterfactuals are meaning- ful in terms of spectral similarity according to Corol- lary 4.6. Figure 6 illustrates the expected norm (1 [)][L[ - [( F and the measured ||_ - _( from the predicted G*. As shown in the theoretical part, we expect these two norm differences to be equal, showing that G* cannot be arbitrarily dissimilar to G and G We argue that a spectral difference is a more principled measurement than the GED which is mere edit distance metric of two graphs - i.e., it might happen that adding/removing edges moves the counterfactual away from the input, however it does not impact its spectrum. GIST reports negligible
Figure 5. GIST finds G whose gap satisfies Theorem 4.5 with only 1.3 x 10- difference against the optimal spectral gap. (left) We show the spectral gaps of G. G and the found G" according to = 0.9 on 100 random samples of MSRC21, We also show the optimal counterfactual to assess the distance with G". (right) We show the first eigenvalue of G, G and G" to demonstrate the connectivity property in Theorem 4.4. We report an error of only 5 10- 3 from the optimal counterfactual. To show zeros in log-scale, we correct them with by adding the lowest gap/cigenvalue that non-zero.
GIST finds counterfactuals that respect the spectral gap of Theorem 4.5 and the connectivity property of The-
8

---

Graph Inverse Style Transfer for Counterfactual Explainability
error of 6.04 10-3 w.r.t. the scenario of producing the optimal counterfactual according norm differences de- scribed above. It also reports lower differences between G and G", which implies that G* gives more importance to node and edge similarities rather than to G's style properties. We suspect this arises due to the non-aggressive learning rate set for GIST which settles for local minimum (see Ap- pendix C). See Appendix G.3.3 for more experiments.
In the future, we will explore more efficient overshooting algorithms that help GIST choose perturbed graph who is spectrally aligned to the input, thus improving convergence rates. Another avenue for investigation is to make theoretical guarantees that the counterfactuals maintain the class of the overshot graph. Lastly, we will explore global-level counterfactuality where the spectral commonalities of the class to explain can be used as guidance for the style transfer.
6. Limitations
A Acknowledgements
Trade-off Between Content and Style (a = 0.5). When equal weight is given to content and style, the model ex- hibits reduced performance. Specifically, struggles to simultaneously preserve the original content structure while accurately matching the target style. This imbalance leads to significantly higher reconstruction errors compared to cases where one objective is prioritized. Detailed quantita- tive results supporting this observation are provided in Ap- pendix G.4.
Dr. Prenkaj was partially supported by the Lazio Re- gion grant, FESR Lazio 2021 - 2027, project @HOME (# 189J23001050007, CUP B83C230062400022.
The authors would like to thank Roman Abramov for his acute observations during Dr. Prenkaj's seminar presenta- tion that sparked the pursuit of the idea of style transfer in graph counterfactuality.
Impact Statement
No guarantees of class maintenance during backtracking. After overshooting G G s.t. (G) + + (G*), ), the back- tracking mechanism only guarantees that ((G) o ((G)). Nevertheless, while there are guarantees that G* has a struc- ture which is an interpolation between the structural style (G) and the class-related spectrum (G'), it is not a given that & (G*) = ((G)) in a multiclass classification scenario. As mentioned in the next section, we leave this for further investigation in the future.
This paper presents work whose goal is to advance the field of Machine Learning. There many potential societal consequences of our work, none which we feel must be specifically highlighted here.
References
Abrate, C. and Bonchi, F. Counterfactual graphs for ex- plainable classification of brain networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 2404,2504, 2021.
7. Conclusion
We introduced GIST, a novel method for graph counter- factual explainability by reformulating the task as a style transfer problem. We addressed key limitations of forward- based methods, such as compromising structural semantics, by leveraging spectral properties in a learnable backtracking mechanism. We integrated three core innovations: (1) style- transfer that preserves structural coherence while refining local node features and edge connections, (2) theoretical guarantees on spectral alignment and connectivity preserva- tion, and (3) modular architecture compatible with diverse GNN backbones.
Amann, J., Blasimme, A., Vayena, E., Frey, D., Madai, V. I., and Consortium, P. Explainability for artificial intelligence in healthcare: a multidisciplinary perspective. BMC medical informatics and decision making, 20:1-9, 2020.
Aragona, D.,, Podo, L., Prenkaj, B., and Velardi, P. Coronna: deep sequential framework to predict epidemic spread. In Proceedings of the 36th Annual ACM Symposium on Applied Computing, pp. 10-17, 2021.
Bajaj, M., Chu, L., Xue, Z. Y., Pei, J., Wang, L., Lam, P. C.- H., and Zhang, Y. Robust counterfactual explanations on graph neural networks. Advances in Neural Information Processing Systems, 34:5644-500 5655, 2021.
We highlighted GIST's superiority across eight benchmarks, achieving SoTA validity (+7.6%) and fidelity (+45.5%) 8 benchmark datasets while maintaining computational ef- ficiency. These results validate that backtracking, rather than forward traversal, enables precise control over coun- terfactuals, ensuring they remain structurally faithful to the input. We also showed that the interpolation factor guides the trade-off between distance and validity of the counter- factuals, whose spectral properties are within negligible empirical errors w.r.t. the optimal theoretical solution.
Borgwardt, K. M., Ong, C. S., Schönauer, S., Vishwanathan, S., Smola, A. J., and Kriegel, H.-P. Protein function prediction via graph kernels. Bioinformatics, (s(uppl__]): i47-i56, 2005.
Braud, C. and Søgaard, A. Is writing style predictive of sci- entific fraud? In Proceedings of the Workshop on Stylistic

---

Graph Inverse Style Transfer for Counterfactual Explainability
Variation, pp. 37-42. Association for Computational Lin- guistics, 2017.
Gatys, L. A., Bethge, M., Hertzmann, A., and Shechtman, E. Preserving color in neural artistic style transfer. arXiv preprint arXiv:1606.05888 05897, 2016a.
Cai, R., Wu, F., Li, Z., Wei, P., Yi, L., and Zhang. K. Graph domain adaptation: A generative view. ACM Transactions Knowledge Discovery from Data, 18(3):1-24, 2024.
Gatys, L. A., Ecker, A. S., and Bethge, M. Image style trans- fer using convolutional neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2414 24144,222, 2016b.
Černevičiené, J. and Kabašinskas, A. Explainable artificial intelligence (xai) in finance: systematic literature review. Artificial Intelligence Review, 57(8):216, 2024.
Guidotti, R. Counterfactual explanations and how to find them: literature review and benchmarking. Data Mining and Knowledge Discovery, pp. 1 1-55, 2022.
Diko, A., Avola, D., Prenkaj, B., Fontana, F., and Cinque, L. Semantically guided representation learning for ac- tion anticipation. In European Conference on Computer Vision, pp. 148-466. Springer, 2025.
Guidotti, R., Monreale, A., Ruggieri, S., Turini, R., Gian- notti, F., and Pedreschi, D. A survey of methods for explaining black box models. ACM computing surveys (CSUR), 51(5): 2018.
Dobson, P. D. and Doig, A. J. Distinguishing enzyme struc- tures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-783, 2003.
Huang, Z., Kosan, M., Medya, S., Ranu, S., and Singh, A. Global counterfactual explainer for graph neural net- works. In Proceedings the the Sixteenth ACM International Conference on Web Search and Data Mining, pp. 141- 149, 2023.
Dwivedi, V. P., Joshi, C. K., Luu, A. T., Laurent, T., Ben- gio, Y., and Bresson, X. Benchmarking graph neural networks. Journal of Machine Learning Research, 24 (43):1-48, 2023.
Jang. E., Gu, S., and Poole, B. Categorical reparametrization with gumble-softman In International Conference on Learning Representations (ICLR 2017). Open net, 2017.
European Union. Regulation (eu) 2016/679 of the european parliament and of the council. Official Journal of the European Union, 2016.
Jhamtani, H., Gangal, V., Hovy, E., and Nyberg, E. Shake- spearizing modern language using copy-enriched se- quence to sequence models. Proceedings of the Work- shop on Stylistic Variation, pp. 10-19, 2017.
European Union. Laying down harmonised rules on artifi- cial intelligence (artificial intelligence act) and amending certain union legislative acts. Official Journal of the Fu- ropean Union, 2023.
Knyazev, B., Taylor, G. W., and Amer, M. R. Under- standing attention in graph neural networks. CoRR, abs/1905.02850, 2019. URL http:://axxi...../ 0tts/1955.02850
Ficler, J. and Goldberg, Y. Controlling linguistic style as- pects in neural language generation. In Proceedings of the Workshop on Stylistic Variation. Association for Com- putational Linguistics, 2017.
Kosan, M., Huang, Z., Medya, S., Ranu, S., and Singh, A. Gefexplainer: Global counterfactual explainer for graph neural networks. ACM Transactions on Intelligent Systems and Technology, 2024.
Flaborea, A., Collorone, L., Di Melendugno, G. M. D., D' D'Ariio,, S., Prenkaj. B., and Galasso, F. Multimodal mo- tion conditioned diffusion model for skeleton- video anomaly detection. In Proceedings of the IEEE/CVF In- ternational Conference on Computer Vision, pp. 10318- 10329, 2023a.
Leemann, T., Pawelczyk, M., Prenkaj. B., and Kasneci, G. Towards non-adversarial algorithmic recourse. In World Conference on Explainable Artificial Intelligence, pp. 395-419, Springer, 2024.
Flaborea, A., Prenkaj, B., Munjal, B., Sterpa, M. A., Arag- D., Podo, L., and Galasso, F. Are we certain it's anomalous? In Proceedings of the IEEE/CVF Confer- ence on Computer Vision and Pattern Recognition, pp. 2897-2907, 2023b.
Li, Y., Wang, N., Liu, J., and Hou, X. Demystifying neu- ral style transfer. In Proceedings of the Twenty- -ixth International Joint Conference Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2017.
Fu, Z., Tan, X., Peng. N., Zhao, D., and Yan, R. Style trans- fer in text: Exploration and evaluation. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Livi, L. and Rizzi, A. The graph matching problem. Pattern Analysis and Applications, 16:253-283, 2013.
10

---

Graph Inverse Style Transfer for Counterfactual Explainability
Lucic, A., Ter Hoeve, M., Tolomei, G., De Rijke, M., and Silvestri, F. Cf-gnnexplainer: Counterfactual explana- tions for graph neural networks. In Int. Conf. on Al and Statistics, pp. 4499 1199-4511, 4511. PMLR, 2022.
Prado-Romero, M. A., Prenkaj, B., and Stilo, G. Are generative-based graph counterfactual explainers worth it? In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 152-170. Springer, 2023b.
Ma, J., Guo, R., Mishra, S., Zhang, A., and Li CLEAR: Generative counterfactual explanations on graphs. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Processing Systems, 2022. URL https::////.t. hppprppeeeveeeeeeeeee net/forum? Id-YR-s5leIve s5leIvh.
Prado-Romes M. A., Prenkaj, B., and Stilo, G. Revisiting countergan for counterfactual explainability of graphs. In Maughan, K., Liu, R., and Burns, T. E. (eds.), The First Tiny Papers Track at ICLR 2023, Tiny Papers @ ICLR 2023, Kigali, Rwanda, May 5, 2023. OpenRe- view.net, 2023. URL https: https///pppeeviieeeeeee net// pdf?id-dOmORL15qg3
Martins, I. F., Teixeira, A. L., Pinheiro, L., and Falcao, A. O. bayesian approach in silico blood-brain barrier penetration modeling. Journal of chemical information and modeling, 52(6): 1886-666677 1697, 2012.
Prado-Romero, M. A., Prenkaj, B., Stilo, G., and Gian- notti, F. A survey on graph counterfactual explana- tions: Definitions, methods, evaluation, and research chal- lenges. ACM Comput. Surv., sep 2023. ISSN 0360-0300. doi: 10.1 10.1145/3618105. URL https: /doi wetooi.orr//1/ org/10. 1145/3618105.
Mueller, J., Gifford, D., and Jaakkola, T. Sequence to better sequence: continuous revision of combinatorial structures. In International Conference on Machine Learning, pp. 2536-2544. PMLR, 2017.
Nemirovsky, D., Thiebaut, N., Xu, Y., and Gupta, A. Coun- tergan: Generating counterfactuals for real-time recourse and interpretability using residual gans. In Cussens, J. and Zhang, K. (eds.), Uncertainty in Artificial Intelligence, Proceedings of the Thirtt-Eighth Conference on Uncer- tainty in Artificial Intelligence, UAI 2022, 1-5 August 2022, Eindhoven, The Netherlands. volume 180 of Pro- ceedings of Machine Learning Research, pp. 1488-1497. PMLR, 2022. URL https: http:////oocedieegee wmw.:oeeeddnnn.m................ mml.. press / v100/v110//// rww.mmrs html.
Prado-Romest M. A., Prenkaj, B., and Stilo, G. Gretel 2.0: Generation and evaluation of graph counterfactual expla- nations evolved. In Joint European Conference on Ma- chine Learning and Knowledge Discovery in Databases, pp. 363-367, Springer, 2024a
Prado-Romert Romero, M. A., Prenkaj. B., and Stilo, G. Robust stochastic graph generator for counterfactual explana- tions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 11518-21526, 2024b.
Neumann, M., Garnett, R., Bauckhage, C., and Kersting, K. Propagation kernels: efficient graph kernels from propagated information. Machine learning, 102:209-245, 2016.
Prenkaj. B., Aragona, D... Flaborea. A., Galasso, F., Gravina, S., Podo, I.., Reda, E., and Velardi, P. A self-supervised algorithm detect signs of social isolation in the elderly from daily activity sequences. Artificial Intelligence in Medicine, 135:102454, 2023.
Nguyen, D. Q., Nguyen, T. D., and Phung, D. Universal graph transformer self-attention networks. In Companion Proceedings of the Web Conference 2022, pp. 193-196, 2022.
Prenkaj. B., Villaizán-Valllladoo, M., Leemann, T., and Kas- neci, G. Unifying evolution, explanation, and discern- ment: A generative approach for dynamic graph coun- terfactuals. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2420-2434 2024.
Numeroso, D. and Bacciu, D. Meg: Generating molecular counterfactual explanations for deep graph networks. In 2021 International Joint Conference on Neural Networks (IJCNN), pp. 1-8. IEEE, 2021.
Riesen, K. and Bunke, H. lam graph database repository for graph based pattern recognition and machine learning. In Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR International Workshop, SSPR & SPR 2008, Orlando, USA, December 4-6, 2008. Proceedings, pp. 287-297. Springer, 2008
Petch, J., Di, S., and Nelson, W. Opening the black box: the promise and limitations of explainable machine learning in cardiology. Canadian Journal of Cardiology, 2021.
Prado-Romero, M. A., Prenkaj. B., and Stilo, G. Devel- oping and evaluating graph counterfactual explanation with gretel. In Proceedings of the Sixteenth ACM Interna- tional Conference on Web Search and Data Mining, pp. 1180-1183, 2023a.
Scarselli, F., Gori, M., Tsoi, A., Hagenbuchner, M., and Monfardini, G. The graph neural network model. JEEE Trans. on Neural Networks, 20(1):61-88) 2008.

---

Graph Inverse Style Transfer for Counterfactual Explainablilsg
Schomburg, I., Chang, A., Ebeling, C., Gremse, M., Heldt, C., Huhn, G., and Schomburg, D. Brenda, the enzyme database: updates and major new developments. Nucleic acids research, 311supp 2004.
Winn, J., Criminisi, A., and Minka, T. Object categorization by learned universal visual dictionary. In Tenth IEEE International Conference Computer Vision (ICCV'05) Volume 1, volume 2, pp. 1800-1807. IEEE, 2005.
Shamoo, Y.
The role of explainable ai (xai) in forensic investigations. In Digital Forensics in the Age Al. pp- 31-62. IGI Global Scientific Publishing, 2025.
Wu, S., Tang, Y. Zhu, Y., Wang, L., Xie, X., and Tan, T. Session-based recommendation with graph neural networks. In Proceedings of the AAAI conference artificial intelligence, volume 33, pp. 346-35563 2019.
Shen, T., Lei, T., Barzilay, R., and Jaakkola, T. Style transfer from non non- aon-parllll text by cross alissmmligmmet. Advances in
Wu, X., Xiong, Y., Zhang, Y., Jiao, Y., Shan, C., Sun, Y., Zhu, Y., and Yu, P. S. Clare: A semi-supervised commu- nity detection algorithm. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2059-2069, 2022.
neural information processing systems, 30, 2017.
Shi, Y., Huang, Z., Feng, S., Zhong, H., Wang, W., and Sun, Y. Masked label prediction: Unified mes- sage passing model for semi-supervised classification. In Zhou, Z.-H. (ed.), Proceedings of the Thirtieth In- ternational Joint Conference on Artificial Intelligence, IJCAI-21, pp. 1548-1554. International Joint Confer- ences on Artificial Intelligence Organization, 8 2021. doi: 10.24963/ijcaa2222211144, URL https: / /wo.ooooooo org/ 10. /22443433ica..222
Yan, J., Yin, X.-C,, Lin, W., Deng, C., Zha, H., and Yang. X. A short survey of recent advances in graph matching. In Proceedings of the 2016 ACM international conference on multimedia retrieval, pp. 167-174, 2016.
Main Track.
Ying, Z., Bourgeois, D., You, J., Zitnik, M., and Leskovec, J. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32, 2019.
Srinivas, S., Subramanya, A., and Babu, R. Training sparse neural networks. In 2017 IEEE Conf. on CVPRW, pp. 455 462. IEEE, 2017.
Yuan, H., Yu, H. Gui, S., and Ji, S. Explainability in graph neural networks: A taxonomic survey. IEEF Transactions on Pattern Analysis and Machine Intelligence, 2022.
Sutherland, J. J., O'brien, L. A., and Weaver, D. F. Spline- fitting with a genetic algorithm: method for developing classification structure- activity relationships. Journal of chemical information and computer sciences, 43(6): 1906-1915, 2003.
Zhou, B., Li, R., Zheng, X., Wang, Y. G., and Gao, Graph denoising with framelet regularizers. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
Tan, J.. Geng, S., Fu, Z., Ge, Y., Xu, S., Li, Y., and Zhang, Y. Learning and evaluating graph neural net- work explanations based on counterfactual and factual reasoning. In Proceedings of the ACM Web Confer- ence 2022, WWW '22, pp. 1018-1027, New York, NY. USA, 2022. Association for Computing Machinery. ISBN 9781450390965. URL https::t////eet /ttp:://do...gg///// 1145/3485447.55133
Zhou, Z., Kearnes, S., Li, L.,, Zare, R., and Riley, P. Opti- mization of molecules via deep reinforcement learning. Scientific Reports, 9(1), 2019.
Zhu, J.-Y., Park, T., Isola, P., and Efros, A. A. Unpaired image-to-iman translation using sycle-consisten adver- sarial networks. In Proceedings of the IEFE international conference on computer vision, pp. 2223-2232, 2017.
Vinyals, O., Fortunato, M., and Jaitly, N. Pointer networks. Advances in neural information processing systems, 28, 2015.
Wachter, S., Mittelstadt, B., and Russell, C. Counterfactual explanations without opening the black box: Automated decisions and the gdpr. Harv. JL & Tech.. 31:841, 2017.
Wei, X., Liu, Y., Sun, J., Jiang. Y., Tang, Q., and Yuan, K. Dual subgraph-based graph neural network for friendship prediction in docation-baser social networks, ACM Trans- actions on Knowledge Discovery from Data (TKDD), 2022.
Wellawatte, G. P., Seshadri, A., and White, A. D. Model agnostic generation of counterfactual explanations for molecules. Chemical science, 13(13):3697-3705 2022.
12

---

Graph Inverse Style Transfer for Counterfactual Explainability
A. Omitted Proofs
A.1. Lemma 4.3: Spectral Mixing Property
A.1.1. COMMUTING CASE
Proof. The normalized Laplacians of and G LG) and L( commute and are simultancously diagonalizable. Two matrices G and T,(G*) commute T, I,G)) T, If these matrices commute and are symmetric, there exists single orthonormal matrix U that diagonalizes both
L G UAU L(G) = UAA
(13)
Following Equation (7), the styled Laplacian is therefore
( -AUUUU + +(1 a1
-UAT..
(14)
Thus, we can approximate
T(O'= U(oA + (0 (11-0)A)UT
(15)
Since aA + (1 A is also diagonal matrix, its diagonal entries at (G))) (1 - a) Being diagonal in the same
(G")
basis U, the eigenvalues of L (G") = aL(G") + ( are precisely
{ a2 + +(1 - -)--))1 (1-0))1
(16)
Thus, the eigenvalues interpolate linearly under convex combinations. The same reasoning holds for the normalized Laplacians (G) and [
A.1.2. NON-COMMUTING CASE
Although we assume that (G) and (G)) commute, we provide the reader with complete overview when these matrices do not commute. Let their eigenvalues be sorted non-decreasing order:
(T) S (2( S .... S An((1 (L)) S (2(() S .... S (L
(17)
(18)
Because (G)) and [[(') do not commute, we cannot simply write (i(I( = a (((o)) + (1 -1- (1-a) ((IG)) Instead, we use Weyl's inequalities to bound A (L))))
Courant-Fischer (Min-Max) Theorem. Recall that for a real symmetric matrix M with eigenvalues A1 S ... S An (M), the k-th eigenvalue x (M) can be characterized by:
x
M
x
Aa(M) = max UCR" dU)=U)
min XEU x=0
(19)
X x
Rayleigh quotient
Weyl's Inequalities: Statement
Theorem A.1 (Weyl's Inequalities). Let A and B be two real symmetric (or Hermitian) matrices of size n X n. Denote their eigenvalues non-decreasing order by
(AA (A) S (A),
ABB) ( (B).
(20)
Lei = + B. Then its eigenvalues {},(C) also arranged in non-decreasing order satisfy:
Xa(A) + AB S AA(A+B) S Ax(AA++ + (n)) for each S S n.
(21)
More precise interlacing bounds also exist, but this basic version often suffices show that every eigenvalue of A + B is contained within interval determined by sums of the individual eigenvalues of A and B.
In our context, = (G)) and B = (1 ( Since A and B are still real symmetric and a, (1-a) 2 0, Weyl's theorem directly applies.
13

---

Graph Inverse Style Transfer for Counterfactual Explainabiliyy
Applying Weyl's Inequalities LL + (1 - L.) Putting A =L and B (1 a-) into Theo- rem Theorem A.1, we get for each ,,...,n:
An (aLi + (11 (() & Au ( (11 < (a + An ((1 (1)
(22)
Using the fact that scaling a matrix by a nonnegative real factor a scales all its eigenvalues by a, we have:
>a(aL(G)) aL 2,((1- ((110))
(1 (1-a) (2)1))
(23)
Hence:
a (L(C)) + (1 - a) (L(C)) s de (1 s (e + (1- An (L(C))
(24)
where L(G") = (L +1 (
Therefore, while the k-th eigenvalue of L (G') does not equal simple pointwise interpolation of A5 (T( and Xa (T(()))))
it is constrained to lie within the interval:
[a Xv (I. a1--a) a A (L (1 (I.C))
(25)
Remark A.2 (Interpretation). This shows precisely why, in the non-commuting case, only obtain bounds the styled eigenvalues rather than direct, index-by-inder convex combination of the form A (L + (1 a) (()). The lack of commutativity prevents simultaneous diagonalization. Therefore, the eigenvectors of (()") differ from those of (G) and (G)) making simple one-to-one mapping of eigenvalues impossible.
A.2. Theorem 4.4: Connectedness Under Convex Combination of Laplacians
Theorem A.3. Let ()) and T) be the (combinatorial or normalized) Laplacians of two simple, undirected, connected graphs G and H on the same vertex set of size n. For any E [0, 1], define
:= + - (H)
Then (FF) corresponds to connected graph.
Proof. Assume for contradiction that the graph F corresponding to (F) is disconnected. Then there exists a nontrivial
partition of the vertex set V = U (V \ S), with S * Ø and S + V, such that no edge F connects a node in S to a node V S.
Let (G) and A!) denote the adjacency matrices of G and H. respectively. Since ( D(F) - -A and A = aA (G) + (1 a)
the absence of any edge crossing the cut in F implies that for all i S, V V.S.
1//0 = aA + (1-a) 0.
Because a, 1 a 0, this implies that A A (H) for all such (i.j). That is, neither G nor H has any edge crossing the cut between S and V \ S. But this contradicts the assumption that both G and H are connected.
Therefore, such a cut cannot exist, and F must be connected. Hence, (F) is the Laplacian of a connected graph.
A.3. Spectral Gap Bounds
Theorem A.4 (Spectral Gap Bounds). Let G and G be two connected graphs the same vertex set, and let L(G) and ( be their (combinatorial or normalized) Laplacians. Define
T( aT + (G) a [0, 1),
14

---

Graph Inverse Style Transfer for Counterfactual Explainability
and let the spectral gap be A(G) (z( with analogous defimitions for G and G". Then,
min(A A(G)) AG" 2 max (ax)) A(G)).
Proof. Since G and G connected, their Laplacians satisfy A 2 and the same holds for GO by convexity and connectedness preservation (see Theorem A.3).
Let == = aL!G)) and B == (1 a)) so L( = -A+ B. By Weyl's inequality for symmetric matrices, we have:
A B) E (A((A) + AB(), A2(4) + (B))
Since (I( =1 O, this becomes:
X2(L(()) E [a))(L(G)), (1 (1- (L))))(((1))
Swapping G and GO gives the symmetric interval:
x2(L(G)) e (min(a2z(LLG') (1-a) ()))))(((())) max max(a>a(L<G)), (1 a))2(L(01))
However, since a E [0, 1]. the maximum of (G)L and A2 (L) always bounds Xe(L(G7) from above, and the minimum from below. Thus,
min(A(G), A(G < AGG s max ((G), A(G)).
Remark A.S. For normalized Laplacians, the same bounds apply since they also symmetric and positive semi-definite, and Weyl's inequality holds for all real symmetric matrices.
A.4. Frobenius Norm Difference Corollary
Corollary A.6. Let (G), L(G"), L(G') be Laplacians (combinatorial normalized) of graphs G, G and G respectively, where
L =a LG)) + (1 (1-a) a [0, 1].
Then, the Frobenius norm difference between G and G satisfies
[I( - || = (1 (1 (1-a))(1100) - -1,0)
Proof. By linearity, we have
L I(G' = _())) (O - + (1- ()) =
Taking Frobenius norms and using absolute homogeneity gives the result:
( (1 a) -
L
B. GIST's Overshooting Algorithm
Figure illustrates the architecture of GIST and how it learns to backtrack (see Algorithm 1) into finding the counterfactuals G Notice that GIST, before performing the backtracking mechanism, needs overshoot the decision boundary of & given an input graph G. In this paper, given G, rely simple overshooting algorithm which finds G in Equation (26).
k² = min
[L,]]] (G) # {Gx))
VG E u[[G GG
(26)
G = G
15

---

Graph Inverse Style Transfer for Counterfactual Explainability
where (+) depicts shuffling operation from the given in input, and is the of graphs in the dataset. An interesting overshooting algorithm, which would aid convergence and reduce the estimation errors shown in the main material, is that of choosing G given G as in Equation (27).
k- = min k E [1, ((G) (GL)) A (1 -a) | - - 11
VGa E | G e (),,
(27)
G= = Gk.
Notice how we condition the selection of G on its Frobenius norm difference with G. This ensures that the chosen pair structurally similar yet belonging different classes. In this case, GIST would have more chances of converging the optimal counterfactual G than being agnostic to the choice of G as in Equation (26). We leave these investigations for future work.
C. Hyperparameter Selection
In our experimental evaluation, tested GIST against other learning-basse based explanation methods from the literature. The competitors include RSGG-CE (Prado-Romero et al., 2024b), CF2 (Tan al., 2022), CLEAR (Ma al., 2022), and CF-GNNExp. (Lucic et al., 2022). For each explainer, used the optimal hyperparameters proposed in their respective literature:
For GIST we configured it run the backtracking process for 50 epochs with a batch size of 16. We chose the number of attention heads to be equal to 2, the node embedding dimension to 16. We set a 0.9 to encourage higher validity, which is beneficial for a helpful counterfactual. We train GIST with Adam optimizer with learning rate 10-3 and a
weight decay of 10
For CF² (Tan et al., 2022), we configured: 20 epochs, batch size ratio of 0.2, learning rate (Ir) initialized 0.02, and 0.7, 20, and y = 0.9.
regularization parameters
CF-GNNEXp (Lucic al., 2022) utilized:
0.01, K 5. B 0.6, and 0.2.
CLEAR (Ma et al., 2022) employed: 10 epochs, learning rate (Ir) of 0.01, counterfactual loss regularization parameter (Aete) set to 0.1, trade-off parameter = 0.4. and batch size 32.
RSGG-CE (Prado-Romero et al., 2024b) was trained for 500 epochs with a GAN configuration: batch size 1 and Poollon discriminator.
Concerning the oracle implementation, we used the following hyperparameters: 50 epochs, batch size 32, and carly stopping threshold 10-4 We trained the model using the RMS Propagation optimizer (learning rate 0.01) with Cross Entropy loss. The architecture consisted of Graph Convolutional Neural Network with convolutional layers and dense layer, convolutional booster 2, and linear decay factor 1.8.
D. Dataset description
Table Summary selected datasets and their characteristics. t depicts a real-world dataset and synthetic one.
Dataset
Graphs
Classes
Avg. Nodes
Avg. Edges
Node Labels Edge Labels
Node Attr.
AIDS
2000
15.69
16.20
v (4)
BAShapes $
500
2
57.00
82.01
/ (8)
BBBP
2039
2
24.06
26.00
BZR I
405
35.75
38.36
(3)
COLORS-3 $
10500
11
61.31
91.03
((4)
ENZYMES i
600
6
32.63
62.14
V(88)
MSRC21 +
563
20
77.52
198.32
V(3)
PROTEINS +
1113
2
39.06
72.82
((1)
We conducted our experiments on 8 popular real and synthetic datasets comprising of binary and multi-class graph classification tasks to compare our approach with SoTA GCE methods. Table illustrates the characteristics the datasets used in this paper.
16

---

Graph Inverse Style Transfer for Counterfactual Explainability
AIDS (Riesen & Bunke, 2008) consists of graphs representing molecular compounds. These graphs are derived from the AIDS Antiviral Screen Database of Active Compounds. This data consists of two classes (active and inactive), which represent molecules with or without activity against HIV. The molecules are converted into graphs in straightforward manner by representing atoms as nodes and the covalent bonds as edges. Nodes are labeled with the number of the corresponding chemical symbol and edges by the valence of the linkage. There are 2,000 elements in total (1,600 inactive elements and 400 active elements).
BAShapes (Ying et al., 2019) is symthetic dataset consisting of base graph and motif's connected on the base. The base graph is a Barabasi-Albert (BA) graph and motifss can be either house-shaped (class 0) or grid-shape (class 1), Following the generation done in (Lucic et al., 2022), there are 8 nodes on the base graph with 5 edges connecting them. Each base graph has 7 motives connected to it.
BBBP (Blood-Brain Barrier Penetration) (Martins et al., 2012) is a dataset widely used in drug discovery and neurological research to develop machine learning models that predict blood-brain barrier permeability. The blood- brain barrier is a protective membrane that shields the central nervous system by regulating the passage of solutes, Its presence is a critical consideration in drug development, whether for designing molecules that target the central nervous system or for identifying compounds that should be restricted from crossing the barrier. BBBP contains binary labels for 2,053 curated molecules, indicating whether a compound can penetrate the blood-brain barrier. Specifically, 1,570 molecules can penetrate the barrier, while 483 cannot.
BZR (Sutherland et al., 2003) represents a set of 405 ligands for the benzodiazepine receptor. No differentiation of agonists, antagonists, and inverse agonists is made. In vitro binding affinities as measured by inhibition of (SH] diazepam binding are expressed as IC5o values, ranging from 0.34 nM to > 70μM (65 compounds have indeterminate values). The authors selected plC50 = 7.0 as the threshold for activity by considering a histogram plot of compound counts vs PIC50 and the resulting balance of active and inactive compounds.
COLORS-3 (Knyazev et al.. 2019) is a synthetic graph benchmark designed to evaluate the interpretability and generalization capabilities of graph-baser machine learning models, particularly those leveraging attention mechanisms. Each graph consists of nodes assigned one of three colors, with the task framed as a classification problem: models must predict the count of nodes belonging to a specific target color. For generalization purposes, the dataset includes training graphs of moderate size and test sets containing graphs that are significantly larger and more complex than those seen during training.
ENZYMES (Borgwardt et al., 2005) consists of protein graph models. The dataset includes 600 enzymes from the BRENDA database (Schomburg et al., 2004), with 100 proteins sampled from each of the six Enzyme Commission (EC) top-level classes. The original objective that the dataset was created for is to accurately predict the enzyme class membership for these proteins.
MSRC21 (Neumann et al., 2016) is a state-of-the-art dataset in semantic image processing originally introduced in (Winn et al., 2005). Each image is represented by a conditional Markov random field graph, as illustrated in Figure 7. The nodes of each graph are derived by over-segmenting the images using the quick shift algorithm," 7 resulting in one graph among the superpixels of each image. Nodes are connected if the superpixels are adjacent, and each node can further be annotated with semantic label. Imagining an image retrieval system, where users provide images with semantic information, it is realistic to assume that this information is only available for parts of the images, as it is easier for a human annotator to label a small number of image regions rather than the full image. As the images in the MSRC dataset are fully annotated, the authors derive semantic (ground-truth) node labels by taking the mode ground-trune label of all pixels in the corresponding superpixel. Semantic labels are, for example, building, grass, tree, cow, sky, sheep, boat, face, car, bicycle, and a label void to handle objects that do not fall into one of these classes.
PROTEINS is a dataset created by Borgwardt et al. (2005), originally proposed in (Dobson & Doig, 2003), comprising 1,178 proteins (59% enzymes, 41% non-enzymes). Proteins were selected to ensure low structural similarity. From this set, 1,128 proteins (retaining the original class balance) were retained based on the availability of secondary structure data in the Protein Data Bank (PDB). In their original study, Dobson and Doig represented proteins using feature vectors. These vectors encoded various attributes, including the fraction of each amino acid (AA) type among all residues, the fraction of the protein's 's surface area occupied by each AA, the presence of ligands, the size of the largest
hhttps://www v1 feat.
Fee....og//oeereereeeeeeee ptggoverriiww//eeoooo wwwww///uuiiiiiiiio.cc. ft. html.
17

---

Graph Inverse Style Transfer for Counterfactual Explainability
Figure 7. Taken from (Neumann et al., 2016). The left-most RGB image is represented by graph of superpixels (middle) with semantic labels b building, car, v void, and unlabeled. (right) Point clouds of household objects represented by labeled h-nearest-neighhor graphs with part labels top (yellow), middle (bluc), bottom (red), usable-area (cyan), and handle (green). Edge colors are derived from the adjacent nodes.
surface pocket, and the number of disulfide bonds. But, afterwards Borgwardt modeled proteins as graphs. This dataset is notably challenging due to its strict non-redundancy constraint, emphasizing generalizable functional prediction over sequence or structural homology.
E. Evaluation Metrics
We adopt the evaluation framework proposed by (Prado-Romens et al., 2023), employing diverse set of metrics for a comprehensive and fair evaluation. Our evaluation criteria include Rumtime, Oracle Calls (Abrate & Bonchi, 2021), Validity (Guidotti, 2022;
et al., 2023a), Sparsity (Prado-Romens et al., 2023a; Yuan al., 2022), Fidelity (Yuan et al., 2022), Oracle Accuracy, and Graph Edit Distance (GED) (Prado-Romero et al., 2023). Recall that + G - Y is an oracle.
Runtime measures the time the explainer takes to generate counterfactual example. This metric offers an efficient means of evaluating the explainer's performance, encompassing the execution time of the oracle. To ensure fairness, runtime evaluations must be conducted in isolation on the same hardware and software platform.
Oracle Calls (Abrate & Bonchi, 2021) quantifies the number of times the explainer queries the oracle to produce counterfactual. This metric, akin to runtime, assesses the computational complexity of the explainer, especially in distributed systems. It avoids considering latency and throughput, which are external factors in the measurement.
Oracle Accuracy evaluates the reliability of the oracle in predicting outcomes. The accuracy of the oracle significantly impacts the quality of explanations, as the explainer aims to elucidate the model's behaviour. Mathematically, for a given input G and true label y,. accuracy is defined as (G) = ( y).
Validity (Guidotti, 2022: Prado-Romero al., 2023a) assesses whether the explainer produces valid counterfactual explanation, indicating different classification from the original instance. Formally, for the original instance G, the counterfactual G", and oracle 4 validity is an indicator function QGG, G') I[}(G) * ((G)))
Sparsity (Yuan et al., 2022) gauges the similarity between the input instance and its counterfactual concerning input attributes. If S(G, G') e Ra is the similarity between G and G', we adapt the sparsity definition to I-S(G.G") for graphs.
[G]
Fidelity (Yuan et al., 2022) measures the faithfulness of explanations to the oracle, considering validity. Given the input G, true label y, and counterfactual G", fidelity is defined (G, G') = x(G [[² v). Fidelity values can be for the correct explainer and oracle, O and -1 indicating issues with either the explainer the oracle.
Graph Edit Distance (GED) quantifies the structural distance between the original graph G and its counterfactual G'. The distance is evaluated based on a set of actions {p1.P2.... .,. Pr3 E P(G, representing a path to transform G into G', Each action p; is associated with a (p:)) cost. GED is computed as
min (PI...... (G,
((p))
Preference is given to counterfactuals closer to the original instance G. as they provide shorter action paths on G to change
18

---

Graph Inverse Style Transfer for Counterfactual Explainability
the oracle's output. GED offers global measure and can be complemented by a relative metric like sparsity assess the explainer's performance across instances.
F. Time Complexity Analysis for GIST
In this section, we elaborate on the computational complexity of the calculations presented in Section 2. We identify four key components that require explicit complexity analysis: the Laplacian matrix L(G), its normalized form (G),, and their respective computations. Notice that we are not analyzing the forward learning pass of the backward mechanism illustrated in Figure 2. The time complexity of the forward learning pass is dominated by the calculation of the following matrices.
Given undirected weighted graph G with n nodes and m edges, the time complexities of the essential operations are as follows:
Degree Matrix Computation D. The degree matrix is a diagonal matrix where each diagonal element Djs represents the degree of node The degree computed as the sum of the weights of the edges connected to node i, which corresponds to the row or column sum in the adjacency matrix A.
For dense graphs, where most nodes are highly connected, the adjacency matrix A contains a significant number of non-zero entries. Computing the degree matrix by summing all entries in A requires (n time. However, for sparse graphs where < n², only the non-zero entries (corresponding to edges) are considered, reducing the time complexity to (().. Therefore, the complexity of computing the degree matrix is:
( for dense graphs, (m)) for sparse graphs.
Laplacian Matrix Formation D A. The Laplacian matrix L(G) computed by subtracting the adjacency matrix A from the degree matrix D. Both matrices have dimensions n n. In dense graphs, element-wise subtraction takes O(n²) time, since every entry must be processed. However, in sparse graphs, the adjacency matrix A contains only m non-zero entries, and D is diagonal. Consequently, the subtraction operation can be performed in O(n + m) time. The resulting complexity is:
D
(nn²) for dense graphs, O(n + m) for sparse graphs.
Eigenvalue Decomposition. Eigenvalue decomposition is crucial for analyzing the spectral properties of the Laplacian matrix. The standard approach, such as QR decomposition, has time complexity of O(n²) for dense graphs.
For large sparse graphs, computing all eigenvalues directly is impractical. Instead, iterative methods like the Lanczos algorithm are employed, which approximate the largest (or smallest) eigenvalues efficiently. The Lanczos algorithm operates in On + m) time per iteration without reorthogonalization, making it practical alternative for sparse graphs. Thus, the time complexity of eigenvalue decomposition is:
O for dense graphs, O(k(n + m)) for sparse graphs, where k denotes the iterations/eigenvaluus..
Normalized Laplacian Computation İ(G = D D- 1/2, The normalized Laplacian L(G) is obtained by applying the diagonal matrix D-1/2 to both sides of the Laplacian matrix. Inverting the diagonal elements of D to compute D-112 takes O(n) time, as it involves element-wise inversion.
For the matrix multiplication involved in forming L(G), we need to multiply first D-2 with L(G), which has a complexity of Onn²), because D-1/2 is a diagonal matrix. Then, there another multiplication step between (-1/2T.(G) and D-1/2 which also has complexity of O(n²). Thus, the overall time complexity is O(n²) in dense graphs. However, for sparse graphs, the multiplication can be optimized to ((m), since most elements in L(G) are zero, allowing efficient computation. Thus, the time complexity is:
(n²²) for dense graphs,
((m) for sparse graphs.
This analysis demonstrates that our method does not introduce significant computational bottlenecks. As shown Table 4, utilizing sparse representations significantly improves computational efficiency. For large sparse graphs, iterative methods for eigenvalue decomposition further reduce complexity to O(n m) per iteration, making the calculations feasible.
'Notice that if D were not diagonal matrix, the matrix multiplication would have complexity of (n²)).
19

---

Graph Inverse Style Transfer for Counterfactual Explainability
Table Overall complexity considerations for dense and sparse graphs.
Computation
Dense Graphs
Sparse Graphs
O(n²)
((m) O m)
L(G) A
O
Eigenvalue Decomposition
O(n))
O(k(n + m)) (for eigenvalues) ((m)
[(G)- D-
O(n²)
104
iRand
CF-GNNEXp.
CF2
CLEAR
103
RSGG-CE
GIST
GED
10
10
AIDS
BAShapes
BBBP
BRZ
COLORS-3
ENZYMES
MSRC21
PROTEINS
Figure 8. GIST is the most effective and reliable explainer (in terms of validity), reporting low input structural changes. Comparison of GED across different explainers for generating counterfactuals various datascts. GIST consistently achieves the best balance between validity and structural proximity, with significantly lower GED than other methods w.r.t. the baseline iRand.
G. More Experiments
G.1. GIST vs. SoTA in terms of GED
GIST maintains reasonable Graph Edit Distance (GED) over the low-validity iRand baseline with 8.9% increase against 2.1% % reported by RSGG-CE. Figure 8 illustrates the structural proximity in counterfactual generation, as measured by the GED. We invite the reader to assess the trade-off between validity and fidelity, shown in Table 1 and Table 2, and the GED. While RSGG-CE demonstrates lower GED in many cases (indicating smaller structural changes), it often sacrifices validity, which undermines its practical effectiveness in generating meaningful counterfactuals. Contrarily, GIST prioritizes generating valid counterfactuals, even at the cost slightly higher GED. This approach aligns with the goal of counterfactual generation providing actionable. interpretable, and valid examples since low GED alone insufficient the counterfactuals are not valid. Here, GIST strikes crucial balance by producing counterfactuals that remain meaningful and interpretable while requiring reasonable structural changes. This makes it more dependable choice for real-wort applications where validity is essential. For instance, in datasets like BZR and MSCR21 where GIST performs comparably to CF-GNNExp in terms of validity GIST achieves a GED that is approximately two orders of magnitude lower than CF-GNNExp. Overall, GIST reports an increase of 8.9% over iRand on all datasets; RSGG-CE 2.1%, CLEAR 776.2%, CF2 180.8%, and CF-GNNEXp. 366.7%. This highlights GIST's effectiveness as a superior explainer that optimizes both validity and structural proximity.
20

---

Graph Inverse Style Transfer for Counterfactual Explainability
Table 5. Average test-set performances on AIDS for S-cross vali- dations. The accuracy for the used GCN oracle in the test set is
Table 6. Average test-set performance on BAShapes for 5-cross validations. The accuracy for the used GCN oracle in the test set is 99.9%.
99.4%.
GED J
Onicle Calls J.
Validity 1
Sparsity
Fidelity
GED
Oracle Class J
Validity
Sparsity 1
Fidelity f
Rand
x 10
1.10 10-
0.013
0.001
0.013
iRand
0C
9.95 x 10*
0.000
0c
0.000
CN-GEN
1,36 x 10a
1.00 10
0.936
3.454
0.924
GNNEX.
9.09 10a
0.20 x 10*
0.516
11.09
0:484
CFR
7.82 x 10!
0.019
3.757
0.015
CF
00
0.000
nc
0.000
CLEAR
2.15 x 102
0.037
27.35
0.037
CLEAR
9.58 102
0.908
6.365
0.060
RSGG-CE
3.19 10'
1.20 10?
0.128
0.059
0.124
RSGG-CE
8.88
10²
1.00 x 10a
1.000
0.375
0.968
GIST
5,20 x 10
7.92 10
0.940
2.072
0.928
GIST
1.11
0.58 x 10
1.000
0.816
0.968
Table 7. Average test-set performances on BBBP for 5-cross vali- dations. The accuracy for the used GCN oracle in the test set is
Table 8. Average test-set performances on BZR for 5-cross vali- dations. The accuracy for the used GCN oracle the test set
92.2%.
96.1 1%
GED
Orccle C
Validity
Sparsity
Fidelity
GED
Oracle Calls
Validity
Sparsity 4
Fidelity 1
Rand
0.37 x 10'
1.42 x 10
0.151
0.008
0.177
iRand
6.78 10
2.03 x 10'
0.332
0.029
0.146
CF CENGNNEXp.
3.23 x 102
1.00 x 10
0.931
5.227
0.784
CN-GNNExp.
6.23 x 102
0.10 x 10"
0.810
7,936
0.741
CF
1.31 10
0.208
3,350
0.178
CF
2.53 10
0.185
0.341
0.176
CLEAR
1.43 x 102
0.267
11:27
0.164
CLEAR
6.90 10
0.176
6,320
0.127
RSGG-CE
2.33 x 10!
2.31 102
0.404
0.167
0.286
RSGG-CE
8.75 10
2418% x 102
0.732
0.922
0.683
GIST
4.24 x 10'
8.03 10
0.956
0.810
0.809
GIST
4.51 x 10
0.74 x 16'
0.810
0.634
0.741
Table Average test-set performances on COLORS-3 for 5-cross validations. The accuracy for the used GCN oracle in the test set
Table 10. Average test-set performances on ENZYMES for
cross validations. The accuracy for the used GCN oracle in the
is 27.7%.
test set 33.3%.
GED J
Oracle Calls 1
Validity 1
Sparsity
Fidelity
GED 1
Oracle Calls J
Validity
Sparsity 1
Fidelity f
Rand
3.52 x 10
1.03 10"
0.392
0.043
-0.007
iRand
0.79 x 10'
2.81 x 10'
0.138
0.007
0.004
CF-GNNEXp.
4.35 x 10
0.10 10
0.736
12.16
0.091
CF-GNNEKp.
5.09 10
0.10 x 10'
0,910
4,947
0.077
CF
1.16 x 10
0.676
3,915
0.065
CF
9.38 x 10"
0.437
1.524
0.017
CLEAR
8.93 x 10a
0.217
64.33
0.033
CLEAR
9.34 x
0.370
26.23
0.040
RSGG-CE
5,15 x 10
3.70 10-
0.884
0.291
0.147
RSGG-CE
1.96 x 10a
2.57 x 102
0.447
0.228
0.050
GIST
1.41 x 10"
0.43 x 10
0.884
1.758
0.202
GIST
7.27 x 10
0.44 x 10!
0.970
0.957
0.203
Table 1. Average test-set performances on MSRC21 for S-cross validations. The accuracy for the used GCN oracle in the test set
Table 12. Average test-set performances on PROTEINS for 5-
cross validations. The accuracy for the used GCN oracle in the
is 91.2%.
test set is 71.4%.
GED
Oracle Calls I
Validity
Sparsity
Fidelity
GED
Oracle Calls
Validity
Sparsity 1
Fidelity 1
RRad
3.40 x 10'
1.88 10?
0.035
0.004
-0.035
iRand
0.20 10'
5.13 x 10
0,018
0.001
-0.009
CF-GNNEXp.
2.98 x 10a
0.20 x 10'
0.965
10.47
0.825
CF-GNNExp.
1.52 x 10
0.10 x 10'
0.378
6:273
0.202
CF2
6.30 x 10*
0.018
0.200
.0.018
CF
5.94
0.039
11.00
0.018
CLEAR
1.23 x 16
0.933
4.296
0.855
CLEAR
6.02 10
0.563
703.8
0.051
RSGG-CT:
1.03 x 102
4.78 10a
0.912
0.329
0.807
ASGG-CE
4.39 x 10
3.07 x 102
0.237
0.141
0.133
GIST
2.20 x 10a
0.52 10
0.965
0.774
0.860
GIST
1.11 10
0.54 x 10
0.791
1.463
0.425
G.2. Full Panorama of SoTA Performances
We assess the performances of GIST and the SoTA methods according to all the metrics described in Appendix E. Table 5 Table 12 illustrate these performances on the test-set for 5-cross validations on all the datasets. Notice how iRand and CF2 on BAShapes (see Table 6) fail to produce valid counterfactuals (i.e., validity at O): therefore, it is useless to measure the GED and sparsity of the produced candidates - hence, we report co.
G.3. Spectra Combination L(G*)= = +
G. SPECTRA COMBINATION WITH VARYING &
The convex combination theorem for graph Laplacians provides a foundation for constructing intermediate graph structures by interpolating between the spectra of two graphs. Let L(G) and L(Gs) denote the normalized Laplacians of graphs G (e.g.. a tree) and G (e.g.. a cyclic graph), respectively. A convex combination of these Laplacians is defined in Equation (7). This equation guarantees that the spectrum of T((G") lies within the convex hull formed by the spectra of LGG) and L(G)).
21

---

Graph Inverse Style Transfer for Counterfactual Explainability
Spectrum of (Poi
Spectront of (Pair 23
Spectrum G* OPiir
Spectrum dE (Pair di
Spectrum of G" (Pair S)
10
10
10
18
Eipttsaa Duben
10
60
10
5
1.30
Alpha 001
Alpbic 1x)
Alpos
Alpta 01)
Spectrum (Puir
Spectruss O* (Pair 7)
Speetrum Of (Pui
Spectrum GE (Pair 9)
Spectrum On (Pui 10)
10
14
16
14
Sypetattn 1448
6.25
20
30
20
Alpia Fo)
Alpta Fol
Figure 9. Heatmaps showing the spectra of G obtained as a convex combination of the speetra of G (tree) and G (cyclic graph) for 10 different pairs G The interpolation parameter a varies from 0.1 to 1, transitioning from the eigenvalues (a those of G (ar = 1). Each plot demonstrates the smooth spectral transition governed by the convex combination.
As a varies, the spectrum G* transitions smoothly between the spectral properties of G (a = 0) and G (a = 1).
Figure illustrates the spectra of G" for 10 different pairs of G' (trees) and G (cyelic graphs). Each heatmap corresponds to unique pair, where the x-axis represents the interpolation parameter a, ranging from 0.1 1. The y-axis indicates the eigenvalue index, while the color intensity reflects the magnitude of the eigenvalues. The leftmost region of each heatmap aligns with the spectrum of G (a 0), and the rightmost region aligns with the spectrum of G (a 1). The gradual change in spectral intensities demonstrates the blending of structural properties as a increases. This figure underscores the potential of spectral interpolation to model continuous transitions between distinct graph structures, providing a tool for exploring intermediate configum gurations and understanding the impact of structural variations. Moreover, notice how with every [0, 1), the connectivity property is maintained. other words, because and G are connected graphs (either trees or cyclic graphs), then G* is also connected with \ (G"))) illustrated with dark blue.
G.3.2. SPECTRAL GAP AND CONNECTEDNESS OF PREDICTED G"
Figure 10 shows the spectral gaps and the lowest eigenvalues for G, G and G according to = 0.9 AIDS (up left), COLORS-3 (up right), ENZYMES (down left), and PROTEIN (down right). We show log-scaled y-axes to highlight small differences in the prediction of G* via the loss Equation (12) see triangles - and the optimal counterfactual obtained according to Definition 4.1 see x. Notice how, for each (G, G pair, GIST finds G whose spectral gap reports a negligible error of 1.75 x 10-2 w.r.t. the optimal counterfactual. Moreover, GIST satisfies Theorem 4.5 since ( is within the bounds of (GG) and A(G*). This intuition is also shown in terms of GED in Figure 3 and in terms of Frobenius norm differences in Figure where G* is in-between G and GF
G.3.3. FROBENIUS NORM DIFFERENCES BETWEEN G, G AND G' ACCORDING TO COROLLARY 4.6
To support our claims that GIST produces spectrally similar counterfactuals, we illustrate (see Figure 11) the Frobenius norm differences presented in Corollary 4.6. Since GIST is learns the backtracking mechanism it might estimate G" that are not globally optimal, but rather locally. Therefore, we report a small estimation error of 5.62 x 10-3 3 in terms of Frobenius norm difference where G "prefers" to be closer to the structure of 5
22

---

Graph Inverse Style Transfer for Counterfactual Explainability
top
and
gam
1010
A05 (00 and 1/00 5.000 991
4rl A/l and Ael Emr 0.001
A05I NIG 0100, Smer 0.312
A2.91 Agte and Ay
Sae 00120071
Speciur
PM
10.
Figure 10. We show the spectral gaps of G, G", and C according to a = 0.9 on 100 random samples of AIDS (up left), COLORS-3 (up right), ENZYMES (down left), and PROTEIN (down right). We also show the optimal counterfactual to assess the distance with the spectral gap of G Each subplot on the right illustrates the first eigenvalue of G, G", and G" to demonstrate the connectivity property Theorem 4.4. show zeros in log-scale, we correct them by adding the lowest gap/cigenvalue that is non-zero.
G.4. Quantitative Analysis for = 0.5 a 0.9
To evaluate the sensitivity of GIST to the weighting parameter a, we compared performance at 0.5 (equal emphasis on content and style) against a = 0.9 (content-dominant setting) across multiple benchmarks.
For the AIDS dataset, we computed the Frobenius norm between the expected and produced outputs as done in Figure 6- see Figure 13. At a = 0.5, the error reaches 0.537, which is over two orders of magnitude higher than the corresponding error at a = 0.9. This substantial increase indicates that the model has difficulty reconciling competing objectives when neither is strongly prioritized.
Similarly, when emulating the setup from Figure 5 see Figure 14 - the model yields an error of 0.013 at 0.5, compared to only 0.005 at 0.9. This further supports the observation that GIST performs more reliably when the optimization is skewed toward either content or style, rather than balanced equally.
These results demonstrate that GIST's performance degrades significantly under equal weighting conditions, and suggest that fine-tuning a toward task-specific priorities is crucial for optimal output quality.
G.S. A Critique to SoTA papers using MUTAG and NCI1
We excluded all those datasets from TUDataset that do not have any node attributes. As per GNNs message passing mechanism, the nodes share their feature vectors with their neighbors, hence then having meaningful embeddings. Given a graph G (X, GIST overshoots to G (X*, (X*,A)) whose node features X go through TransCony layers. If X are missing, then the convolution layer does not produce anything meaningful to then estimate the edge probabilities (see Figure 2). To surpass this hurdle, added 7 features regarding centralities: i.c., node degree, betweenness, closeness, harmonic centrality, clustering coefficient, Katz centrality, Laplacian centrality. In this way, at least we have something interesting to work with and not rely only on the topology of the graphs. Table 14 shows the performance against SoTA in terms of validity and fidelity on 5-fold cross-validation where the oracle is a 3-layer GCN with test accuracy of 86.8% for MUTAG. Unfortunately, even after hyperparameter optimization was done on NCII with the introduced node features, any
/https: htt//chhsrrrrrr gitrrs.gtthu.... 1 o htdd/aaaatts//doooo datasetss/ 1WWe could not reproduce the 89.97% accuracy in paperswitheode https: http::s/papprwwiiie wwwappeewtthcoode..oo thcode. com/ sota/ graph-classi cictiionn cantioooonn on--oon-mmaaaa with the parameters specified in the original paper of U2GNN.
23

---

Graph Inverse Style Transfer for Counterfactual Explainability
Validation of 609 -1
a]|| 009 -L 11s,. Error 4.42E-03
160 L 16'0 I|=
(1 a]|
||
Frobenius Norm
19
69) Pair
Figure 11. We show the Frobenius differences between the Laplacians of G. G and G on AIDS (row=l, col=1), BZR (row=l, col=2), COLORS-3 (row=2, col=1), ENZYMES (row=2, col=2), and MSRC21 (row=3) for a = 0.9.
kind of GCN (with any layer) and U2GNN (Nguyen et al., 2022) with the hyperparameter search space introduced in the original paper does not reach more than 40% of accuracy in the test set. We ran experiments with these oracles for NCII, however the fidelity of the explainers was negative, which suggests that the explainers are actually doing adversarial attacks the oracle (Prado-Roment et al., 2023). Hence, decided discard NCII and show only MUTAG. We want to point out that these two datasets are not suitable for benchmarking purposes since, again, message passing mechanisms in GNNs rely on node feature aggregations on the neighbors. These two datasets do not have node features, and we are a puzzled how SoTA methods used them to compare against each other.
rather than explanations
G.6. Runs on IMDB-M: GIST vs CLEAR
We report the results of 5-fold cross-validation on the IMDB-M dataset, as summarized in Table 13. Notably, we re-ran the CLEAR - the original paper that uses IMDB-M - from scratch and obtained a validity score of 0.45, which significantly deviates from the 0.96 originally reported, raising questions about the reproducibility and robustness of the original evaluation. Among all methods, GIST achieves the highest validity (0.87) and fidelity (0.17) w.r.t. 3-layer GCN oracle, which itself exhibits poor predictive performance with a test accuracy of only 48%.
The iRand baseline fails to generate any valid counterfactuals, rendering fidelity evaluation inapplicable. Furthermore, the uniformly low fidelity scores across all methods underscore broader issue: the underlying GCN oracle performs poorly, limiting the interpretability and utility of generated counterfactuals. We also attempted to replicate the performance of U2GNN (Nguyen et al., 2022), a method claimed to be SoTA on IMDB- but achieved only 33% test accuracy using the same hyperparameters reported in the original paper- - substantially lower than the 89.2% listed on paperswithcode. This discrepancy highlights the need for rigorous, transparent, and reproducible henchmarking practices in graph-based
24

---

Graph Inverse Style Transfer for Counterfactual Explainability
Figure 12. We show the eigenvalues of 100 randomly sampled instances PROTEINS (a 0.9).
explainability research.
25

---

Graph Inverse Style Transfer for Counterfactual Explainability
Validation of [| -1 a) (69 |. Error 5.37E-01
|1
+11
Frobenius Norm
(G, G*) Pair
Figure We show Frobenius norm differences between Laplacians G, G and G" AIDS for a 0.5.
AG),, AGG ) and (G Gap Error 0.011
AL A, (1(1 and (L Error 0.013
AGG).
(G(
AGG")
A2(((o9)
Optimal AG )
Ag(((G"))
GIST A(G')
334
First Eigenvalue (h,)
Spectrum Gap (A)
1o
10
165
(G.69) Pair
(G, G9) Pair
Figure 14. We show the spectral gaps of G, G and G* according to 0.5 on 100 random samples of MSRC21. We also show the optimal counterfactual assess the distance with the spectral gap G*. Each subplot on the right illustrates the first eigenvalue of G. G and G to demonstrate the connectivity property in Theorem 4.4. To show zeros in log-scale, we correct them by adding the lowest gap/eigenvalue that non-zero.
26

---

Graph Inverse Style Transfer for Counterfactual Explainability
Table 13. Average test-set performance on IMDB-M for 5-cross validation. The accuracy of the GCN oracle in the test set is 48%.
Table 14. Average test-set performance on MUTAG for S-cross validation. The accuracy of the GCN oracle in the test set is 86.6%.
Validity
Fidelity
Validity
Fidelity
iRand
0.000
iRand
0.026
0.026
CF-GNNEXpl.
0.670
0.170
CF-GNNExpl.
0.447
0.237
CF
0.710
0.090
CF2
0.026
0.026
CLEAR
0.450
0.050
CLEAR
0.921
0.395
RSGG-CE
0.690
0.090
RSGG-CE
0.947
0.737
GIST
0.870
0.170
GIST
1.000
0.737
27


Reviews:
[{"review_id": "YdTikbrjwa", "reviewer": "Reviewer_6kC8", "summary": "This paper introduces Graph Inverse Style Transfer (GIST), a novel framework for counterfactual explainability in graph neural networks (GNNs). Unlike traditional forward perturbation-based counterfactual methods, GIST employs a backtracking mechanism inspired by style transfer in vision. By first overshooting a decision boundary and then refining the counterfactual graph to align with the original graph’s spectral properties, GIST aims to generate semantically valid and structurally faithful counterfactuals. The method is evaluated on eight benchmark datasets, where it demonstrates an increase in counterfactual validity and improvement in fidelity compared to state-of-the-art approaches.\n\n## update after rebuttal\nThank the authors for response. Some of my concerns have been addressed, I intent to maintain my originial score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for the effort made to review our paper, and for the nice score you chose to give it. With the following, we hope to answer your questions, and convince you of the value of GIST. \n\n**W2: Specific user studies.** We want to point out that the scope of this paper was not to involve users (in fact, none of them are present in the paper) in assessing the goodness of the produced counterfactuals since graph counterfactuals can be quite complicated to illustrate, especially when many edges/nodes are being added/removed from the original instance (see **W1** for a proposal of qualitative analysis).\n\n**W1: Detailed analysis of GIST vs. SoTA beyond numerical results.** As per [3] - the most-up-to-date survey in graph counterfactuality - all methods, besides those designed specifically for molecule explanations where illustrations are possible and very clean visually, use the quantitative metrics we used (see Sec. E & G.2). However, we found in the literature (e.g., [1,2] seem to be consistent in styling) an interesting and visually-pleasing way to show the differences between the original instance and counterfactual produced by illustrating their adjacency matrices. We will extend this way of visualizing also for node feature perturbations since GIST supports this mechanism, differently from the abovecited papers. We believe this would add value to the quantitative measures we provided in the paper, and would appreciate your input in this regard.\n\n**Q1: How scalable is GIST in large-scale real-world graphs?**\n\nIn Sec. F, we have a time complexity analysis that treats both densely- and sparsely-memorized graphs. To reiterate, since GIST needs to find an eigenvalue decomposition to compute the Laplacian, for dense graphs we have a complexity of $\\mathcal{O}(n^3)$ where $n$ is the number of nodes in a graph, and for sparse graphs it amounts to $\\mathcal{O}(k(n+m))$ where $m$ is the number of edges and $k$ is the number of eigenvalues to find. Since $k$ is a constant, then this amounts to $\\mathcal{O}(n+m)$.  Since our implementation uses sparsely-memorized graphs, and from Table 3 in Sec. D you can see that most graphs are sparse anyway ($m<<n^2$ on avg), the execution time is linear on the number of nodes $n$ and edges $m$. Thus, scaling GIST to huge graphs is not expensive, even in real-world graphs that are generally sparse.\n\n**Q2: GIST vs. causal-based explainers:**  To the best of our knowledge, only CLEAR [4] is a causal-based explainer. We included it on our experiments and GIST consistently performs better across the board in validity (Tab. 1) and fidelity (Tab. 2) and counterfactual similarity with the input in terms of Graph Edit Distance (see Fig. 8). This is also because CLEAR, when producing a counterfactual candidate, it gives a fully-connected stochastic graph which then it needs to match to the input. Note, that graph matching is an NP-hard problem and there are some approximations which undermine CLEAR's performances. GIST, on the other hand, is very simple and understandable: *overshoot the oracle $\\Phi$'s decision boundary and backtrack via graph transformers*.\n\n**Q3: Real-world applications.** One compelling real-world application of GIST is drug repurposing. Suppose we have a known drug A that effectively treats disease $d_1$. Our goal is to discover a new drug B that treats a different disease $d_2$, potentially by modifying A. However, directly identifying B is often difficult and financially expensive. GIST could help by first exploring compounds that are far from A - those that may not initially preserve A’s chemical properties but show efficacy against $d_2$ (albeit with more side effects). From there, GIST can iteratively \"walk back\" toward A, gradually optimizing for lower side effects while preserving therapeutic relevance to $d_2$. This path - from distant molecular candidates back toward A - could lead to a novel compound B that is both effective for $d_2$ and safer. We find this direction highly promising and plan to investigate it further. However, applying GIST to drug discovery requires close collaboration with chemists and pharmaceutical experts, as well as human-in-the-loop evaluation to ensure the physical plausibility of generated compounds. Such interdisciplinary work would also naturally address the need for domain-specific user studies, which is a point you raised in your original review.\n\n[1] Prado-Romero et al. Robust stochastic graph generator for counterfactual explanations. AAAI'24 (page 15-16, Figs. 10-11 of the suppl. material on arXiv)\n\n[2] Prenkaj et al. Unifying Evolution, Explanation, and Discernment: A Generative Approach for Dynamic Graph Counterfactuals. KDD'24 (Figs. 7-8)\n\n[3] Prado-Romero et al. A survey on graph counterfactual explanations: definitions, methods, evaluation, and research challenges. ACM CSUR'24.\n\n[4] Ma, et al. CLEAR: Generative counterfactual explanations on graphs. NeurIPS'22.", "claims_and_evidence": "Most claims in the submission are well-supported.", "methods_and_evaluation_criteria": "Yes, the method and evaluation are in a decent design and suitable for the studied problem. \nBut it would be beneficial to include more baselines (as this field has been well studied in the past a few years).", "theoretical_claims": "The provided theory makes sense at a high level.", "experimental_designs_or_analyses": "The experiments could be improved with more classical and SOTA baselines, and include more complex real-world graphs for in-depth evaluation. Adding further user case studies for qualitative assessment would also be beneficial.", "relation_to_broader_scientific_literature": "The proposed work relates to general counterfactual explainability in GNNs.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper introduces a novel and well-theorized counterfactual framework for GNNs. But there are some other potential concerns here to address:\n\n- While the experimental results show improvements over baselines, a more detailed analysis of why GIST outperforms existing methods—beyond just numerical results—would make the contributions clearer.\n- More specific user studies would be beneficial to include.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "- How scalable is GIST in large-scale real-world graphs? \n- How does GIST compare to causal-based counterfactual approaches rather than just perturbation-based baselines?\n- Have you considered potential applications in real-world case studies?", "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": "qGfIM8agCt", "reviewer": "Reviewer_XATo", "summary": "The authors present a new method for generating counterfactual explanations for Graph Neural Networks (GNNs) based on an adaptation of neural style transfer. They then establish some theoretical results for the well-foundedness of their approach before presenting their method to learn the style transfer objective. Finally, the authors benchmark their method on synthetic and real-world datasets against current baselines.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Oh, this is awesome. Thanks for reading the paper and not using an LLM to generate your review :-) \n\nYour suggestions will better our paper. The proofs will be much shorter and clarifications on counterfactuality more thorough. Sec. 5.3 contains the two most important evaluation metrics as per [1]. We'll put the GED (now in Sec.G.1) in the main paper.\n\n**Just interpolation; no insights for counterfactuals**: While the literature advocates for \"hard-core\" generative models, GIST learns to backtrack from a dataset example $G^e$ toward $G$. We agree that the main contribution is interpolation, but, it's applicability is suitable for counterfactuality as shown in the experiments. Interpolating $G$ and $G^e$ guarantees $G^*$ is in-distribution, which promotes plausability [2]. We'll clarify this better at camera ready, and measure plausability.\n\n**Why Laplacian?**: Laplacians capture global structural patterns, e.g., connectivity and symmetry, that are largely invariant to specific node identities. This follows a similar rationale to neural style transfer in images, where Gram matrices of feature activations are used to model style since they encode correlation patterns among features rather than spatial arrangements. Additionally, using the Laplacian aligns with prior work in spectral graph theory, where the eigenvalues and eigenvectors of the Laplacian are shown to be robust descriptors of global structure, and have been used in graph matching [3] and generation [4].\n\n**Eq. 50?**: $Q: \\mathcal{G}\\times \\Phi→\\mathcal{G}$ (we missed this). We put $\\arg \\min$ to emulate a for-loop on $U$. This means we take the first $G^e \\in U$. In hindsight this is also confusing to us. We'll change it to $k^*=\\min [ k\\in[1,n]|\\Phi(G)\\neq \\Phi(G_k) ]\\; \\forall G_k \\in U$, and $G^e = G_{k^*}$\n\n**Similarity metric, objective func and GED**: By using $G$ as a pulling factor governed by $\\alpha$ to produce $G^*$, the similarity is already addressed in the objective although not explicitly as in the desideratum in [2]. In principle, the more $G^*$ goes toward $G$, the lower the edit distance should be, as well as the validity (Fig. 3). We do report GED (Fig. 8, Tab 5-12): GIST is better than CF-GNNExp (our main competitor in validity), though it's not the best across the board due to our choice of $\\alpha = 0.9$.  Lower $\\alpha$ would improve similarity at the cost of validity, a trade-off we make explicit.\n\n**SoTA hyperparams**: We used the hyperparams reported in their original papers. We can optimize them for validity, but this would require months of optimizations. We can optimize them for one dataset (e.g., BAShapes) and use the same for the rest. Do you think this is a good compromise?\n\n**Sec. 5.2 and $\\alpha=1$**: We aim to balance validity and similarity. Setting $\\alpha=1$ would ignore the counterfactual signal, leading to perfect validity but poor GED, as $\\mathcal{L}_{style}$​ becomes zero, and no learning (backtracking) is happening. Our formulation indirectly encourages similarity through $\\alpha$, which controls how much $G$ influences $G^*$. The analysis in Sec. 5.2 is necessary to demonstrate how this trade-off affects GED, even if it's not an explicit loss term.\n\n**Fig. 4**: The zeros are indeed paddings to compute the spectral differences, which need the adj and degree matrices to be of same dimensions. To account for different graph sizes, we could use the Wasserstein distance of the eigenvalues instead of L1. This would need further theoretical investigation. We'll clarify this in the figure's caption.\n\n**Spectral analysis for $\\alpha=0.5$**: Your intuition is right; when $\\alpha=0.5$, GIST struggles between preserving content and matching style. We computed the frobenius norms (expected vs. produced) as in Fig. 6 for $\\alpha=0.5$ on AIDS and get an error of 0.537, two orders higher than with $\\alpha=0.9$. We also emulate Fig. 5 with $\\alpha=0.5$ and obtain an error of 0.013 instead of 0.005 as with $\\alpha=0.9$. Lastly, for Fig. 4 we have an error of 0.043 instead of $2.051\\times10^{-3}$. Unfortunately, we can't show images here, but we'll include this analysis in the appendix, and mention it in a new limitation section.\n\n**Switch content and style**: Taking style from $G^e$  and content from $G$ would attempt to generate a graph structurally similar to a perturbed counterfactual but semantically identical to the original, which defeats the purpose of generating counterfactuals, since semanticity usually drives $\\Phi$'s prediction. GIST is designed to minimally deviate from $G$ structurally, but still flip the class as in $G^e$.\n\n[1] Prado-Romero et al. A survey on graph counterfactual explanations: definitions, methods, evaluation, and research challenges.CSUR'23\n\n[2] Guidotti.Counterfactual explanations and how to find them: literature review and benchmarking.\n\n[3] Yan et al. A short survey of recent advances in graph matching.ICMR'16\n\n[4] Dwivedi et al. Benchmarking Graph Neural Networks.JMLR'23", "claims_and_evidence": "The claims presented are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The method, datasets and baselines makes sense for the problem studied. The baselines and datasets are also relevant. However, I am not convinced by the choice of metrics, as the comparison with the baselines does not seem entirely fair.\nYou should include a measure of similarity, see [1].\n\n[1] Counterfactual explanations and how to find them:\nliterature review and benchmarking. Riccardo Guidotti, 2022.", "theoretical_claims": "I have checked the correctness of all the proofs of the lemmas and theorems in the paper.", "experimental_designs_or_analyses": "The experimental design is sound, and the analysis of part 5.2 and 5.3 is correct, although incomplete in my opinion, as a similarity metric is missing, which is key for counterfactual explanation (see essential references not discussed point).", "relation_to_broader_scientific_literature": "The work seems interesting, although it is difficult to compare their method with the chosen baselines, since its focuses primarily on the Validity metric.", "essential_references_not_discussed": "The similarity metrics was not used to assess the method versus the baselines proposed, as decribed in [1].\n\n[1] Counterfactual explanations and how to find them: literature review and benchmarking. Riccardo Guidotti, 2022.", "other_strengths_and_weaknesses": "Strengths:\n\n- The idea is interesting.\n- The writing is good.\n- The experiments are extensive and thorough.\n\nWeaknesses:\n- In my opinion, the modest theoretical insights do not really add any interpretability into the counterfactual explanations. It does, however, show that you can interpolate between two graphs.\n   \n- A similarity metric should be used to compare the baselines, and ideally would be addressed in the objective.\n\n- Some weaknesses and limitations of the proposed method should be discussed in the paper.", "other_comments_or_suggestions": "- In part 4.1, why do you assume that the Laplacian matrices commute? I know in the proof of theorem 4.4 you separate the cases commuting/non-commuting, but reusing the notation in part 4.1 is confusing.\n\n- Put \"BCE\" in equation 6.\n\n- Part 5: Clarify that you are backtracking from a dataset counterfactual.\n\n- Part 5.3: in my opinion this part is too long. It echoes the basic interpolation results from 4.1, but it provides little in the characterization of counterfactual explanations. \n\n- The proof of Weyl's inequality in the appendix is unnecessary.\n\n- Overall, the proofs in Appendix A.1 should be much shorter (from 2 to 1/2 page), this is very basic linear algebra.\n\n- Appendix A.2 is also very slow for an obvious property, only step 5 is necessary.\n\n- Appendix A.3 : Another direct simple application of Weyl's inequality, this is also very slow. Note that step 1 is poorly formulated. \n    \n- Appendix A.4 should be a one liner.\n\n- Overall, the theoretical insights claim appears weak. You are just interpolating between two graphs. The analysis proves that, indeed, your framework interpolates between two graphs in terms of eigenvalues and norm. How does it relate to counterfactual explanation?\n\n- Appendix 2: I don't understand equation (50). What is the minimum of a shuffled set? Also $Q$ is not define", "questions_for_authors": "- definition 4.1: I am puzzled about your definition of style and content. How do you motivate using the Laplacian of graphs to define style? \n\n- definition 4.1: Why not take the style between $G^*$ and $G^\\varepsilon$ and the content between $G^*$ and $G$?\n    \n- Part 5.1 and Appendix C: for the parameters of the other explainers, wouldn't a fair comparison try to optimize their parameters for validity?\n\n- I am skeptical about your choice of metrics; would not $\\alpha = 1$ achieve perfect validity and very good fidelity, as you would simply return the dataset counterfactual? Then what is the point of the analysis in 5.2?\n\n- Part 5, Figure 4: Why are there so many zeros in those graphs? Is this related to the difference in the sizes of $G$ and $G^\\varepsilon$?\n\n- Part 5: Can you give some spectral analysis for $\\alpha = 0.5$? This choice of parameter may make it harder for your method to perform according to the theoretical results.\n\n- Part 5: How is your method fairing compared to the baselines wrt a similarity metric (eg. GED for example)?\n\n- I think an interesting direction could be to look into incorporating the GNN prediction to adjust the alpha parameter, hence actually balancing the similarity and validity metric in your objective. Have you considered such improvements?", "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": "pmJIJ35bTa", "reviewer": "Reviewer_xnpL", "summary": "GIST introduces a backtracking approach for graph counterfactual explainability using spectral style transfer. Unlike forward perturbation methods, it refines graphs to preserve global style and local content. GIST achieved excellent results experimentally.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for the effort made to review GIST. It's unfortunate you didn't see its value during your original review. With the following, we tackle the weaknesses you mentioned, and hope to convince you of the paper's value.\n\n**W1: Intermediate graph $G^e$, and improved accuracy**: $G^e$ is obtained by overshooting the decision boundary of the oracle $\\Phi$. This process is described in Sec. B and is referenced in Sec. 4. To reiterate, we take the dataset and divide the instances into sets containing of the same class according to $\\Phi$. Then, for each input $G$ with label $y = \\Phi(G)$, we take all the sets whose label isn't $y$, unify and shuffle them. Lastly, we pick the first instance from this shuffled set, and that's $G^e$. This simple yet effective mechanism guarantees the counterfactual begins from the correct region (i.e., $G^e$ is already on the other side of $\\Phi$'s boundary w.r.t. the input $G$). *As a consequence, if we don't use the backtracking mechanism, and just return $G^e$ as the counterfactual, we'd have validity (aka explanation accuracy) equal to 1.* However, $G^e$ might be far from $G$, and we don't want that. That's why GIST walks back towards $G$ and minimizes the spectral difference (Fig 8 for Graph Edit Distance). By going back, GIST needs to learn not to recross $\\Phi$'s boundary and get an invalid counterfactual produced, however this might happen due to poor boundary definition. We will acknowledge this limitation and make what mentioned above clearer at camera ready by allocating space via shrinking Sec. 5.3 as per **XATo**.\n\n**W3: Node embeddings**: I don't understand completely; I'll try my best here. Fig. 2 shows our architecture that takes in input a graph $G=(X \\in \\mathbb{R}^{n\\times d},A)$ which is overshot to $G^e = (X^e \\in \\mathbb{R}^{n \\times d},A^e)$. $X^e$ get then fed to the TransConv layers that project them to a latent space $\\hat{X}^e \\in \\mathbb{R}^\\ell$. The latent features are only used to estimate edge probabilities for the counterfactual candidate $G^*$. What I think you meant is whether the node embeddings in $\\mathbb{R}^\\ell$ are then injected on the nodes of the selected incident edges via the Gumbel + Bernoulli sampling. The short answer is \"no\". Thus, one can't trace how the embeddings are \"transformed\". However, a simple fix would do the trick: when we have $\\hat{X}^e$, we can add a decoder network $h: \\mathbb{R}^\\ell → \\mathbb{R}^d$ - e.g., learned GCN - to map the embeddings back to the input space, and train this network jointly with Eq. 12 by summing, for instance, $|X-g(\\hat{X}^e)|_1$. In this way, we can see which embeddings contribute to the lowest difference (a desideratum of counterfactuality [1]) between $X$ and $g(\\hat{X}^e)$. By doing this, we obtain a sparsity ↓ (Sec. E) as follows for org. GIST (up) and GIST with the embedding decoder (down). If you think this is valuable, we can add it at camera ready, in the appendix.\n|  | AIDS | BAShapes | BBBP | BZR | COLORS-3 | ENZYMES | MSCR21 | PROTEINS |\n|---|---|---|---|---|---|---|---|---|\n| $\\|X - X^e\\|_1$ | 2.07 | .82 | .81 | .63 | 1.76 | .96 | .77 | 1.46 |\n| $\\|X - g(\\hat{X}^e)\\|_1$ | 1.36 | .63 | .50 | .41 | .97 | .74 | .38 | .83 |\n\n**W4: Community & IMDB-M**: Community was synthetically ad-hoc generated in CLEAR. This is why we can't reproduce the same dataset as in that paper. So, we opted to choose TreeCycles and BAShapes to cover RSGG-CE [2] and CF-GNNExp. [3] which were already supported in the GRETEL framework [4]. The results for IMDB-M on 5-fold cross-validations are here. Note that we ran CLEAR from scratch and the reported validity (0.45) isn't the one reported in the original paper (0.96). GIST is the best in terms of validity and fidelity w.r.t. a 3-layer GCN whose test accuracy is 48%. Here, we are using the version of GIST without node embeddings for consistency with what reported for the other datasets in the paper (Sec. G.2).\n|  | GIST | iRand | CF$^2$ | CLEAR | CF-GNNExp. | RSSG-CE |\n|---|:---:|:---:|:---:|:---:|:---:|:---:|\n|Validity|**0.87**|0| 0.71| 0.45| 0.67| 0.69|\n|Fidelity|**0.17**|-| 0.09| 0.05| 0.17| 0.09|\n\niRand doesn't produce any valid counterfactuals, hence its fidelity cannot be measured. Also, all the methods have a low fidelity due to the oracle's \"horrible\" classification skills. We tried UGFormer [5], as the best SoTA in IMDB-M, however we got a test accuracy of 33% with the same hyperparams as in the original paper, instead of the reported 89.2% on paperswithcode.\n\n[1] Wachter et al. Counterfactual explanations without opening the black box: Automated decisions and the GDPR.\n\n[2] Prado-Romero et al. Robust stochastic graph generator for counterfactual explanations.AAAI'24 \n\n[3] Lucic et al. Cf-gnnexplainer: Counterfactual explanations for graph neural networks.AISTATS'22\n\n[4] Prado-Romero & Stilo. Gretel: Graph counterfactual explanation evaluation framework.CIKM'22\n\n[5] Nguyen et al. Universal graph transformer self-attention networks.WWW'22", "claims_and_evidence": "Please refer to Strengths And Weaknesses.", "methods_and_evaluation_criteria": "Please refer to Strengths And Weaknesses.", "theoretical_claims": "Please refer to Strengths And Weaknesses.", "experimental_designs_or_analyses": "Please refer to Strengths And Weaknesses.", "relation_to_broader_scientific_literature": "Please refer to Strengths And Weaknesses.", "essential_references_not_discussed": "Please refer to Strengths And Weaknesses.", "other_strengths_and_weaknesses": "**Strengths**\n\n- The paper presents a thorough spectral analysis, mathematically proving important properties including spectral gap bounds and Frobenius norm differences, which helps ensure the generated counterfactuals maintain coherence and semantic validity.\n\n- GIST is evaluated across eight benchmark datasets, demonstrating its effectiveness in diverse graph settings.\n\n**Weaknesses**\n\n- The paper introduces an intermediary known graph G in the counterfactual generation process but does not explain how this graph is obtained or why it improves counterfactual accuracy. Since counterfactuals are based on assumptions without ground truth, the reliance on an intermediary known graph raises questions about its validity.\n\n- The paper lacks a clear definition of what constitutes a counterfactual in different graph contexts. While structural transformations (e.g., spectral properties) are well-explained, the paper does not specify how counterfactuals are defined in user networks.\n\n- The paper does not provide sufficient details on node embedding generation and how these embeddings change during counterfactual transformations.\n\n- The paper evaluates on eight datasets but does not use commonly used benchmarks from prior counterfactual studies, such as Community and IMDB-M used in CLEAR [1]. It will be benefit to explain why the selected datasets are appropriate for evaluating graph counterfactuals.\n\n[1] Ma, Jing, et al. \"Clear: Generative counterfactual explanations on graphs.\" Advances in neural information processing systems 35 (2022): 25895-25907.", "other_comments_or_suggestions": "None", "questions_for_authors": "Please check above.", "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": "NW9BN2VZTI", "reviewer": "Reviewer_wac8", "summary": "The authors introduce GIST their novel framework that generates counterfactual graph explanations. They leverage spectral style transfer to generate valid counterfactual explanations. Their architecture consists of two components: attention based node embeddings, and edge probabilities from the Gumbel-softmax trick.   \nAfter designing their algorithm they implement it on several real-world and synthetic datasets. They use the data sets BBBP, BZR, ENZYMES, MSRC21, PROTEINS, BA-SHAPES, and COLORS-3. They conduct experiments with respect to several SOTA baselines and compute relevant metrics such as validity and fidelity. They also conduct an ablation study on the interpolation factor which adjusts the distance from the decision boundary. They show a remarkable improvement in both validity and fidelity.\n\n## update after rebuttal\nThanks for the authors' efforts in the rebuttal. I intend to keep my rating.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for the effort made to review our paper, and for the nice score you chose to give it. Thank you for pointing out RCExplainer [2]. \n\n**W1: Missed Bajaj reference**: We were aware of the paper, and decided to reviewed RCExplainer again to see whether we were missing something or not. We cross-validated it with what described in [1] specifically in Table 2 (page 12). As per [1], we confirm that it is a heuristic + learned-based method. \n\nIn our related work section, we specifically stated that we concentrate on only learning-based and generative methods, hence the choice of the methods we compared against. However, we see the value of RCExplainer with its multiple learnt linear decision boundaries and then the search over these boundaries to find robust explainers, and will include it in our related work at camera ready. \n\nUnfortunately, the official code doesn't run (*the authors load some Huawei third party python packages that aren't available anywhere*) even after debugging and trying to port it to the GRETEL framework to have the same evaluation pipeline. Then, we also tried to run an unofficial code repository at https://github.com/idea-iitd/gnn-x-bench/blob/main/source/rcexplainer.py (we are not the authors so anonymity isn't breached if you want to take a look), however, the code doesn't support BBBP, BZR, ENZYMES, MSRC21, and COLORS-3 datasets. It's fine that it doesn't support COLORS-3 since this is multiclass and RCExplainer only does binary classification. However, not supporting the other listed datasets hinders us to compare it against other SoTA and GIST. \n\n*I believe a good compromise here is to recognize RCExplainer's validity as a heuristic+learned counterfactual explainer and list it in our related work section and highlight the fact that we only treat pure learned-based approaches*. What do you think?\n\n**Q1: Where are MUTAG and NCI1?**: We excluded all those datasets from TUDataset (https://chrsmrrs.github.io/datasets/docs/datasets/) that do not have any node attributes. As per GNNs message passing mechanism, the nodes share their feature vectors with their neighbors, hence then having meaningful embeddings. Given a graph $G=(X,A)$, GIST overshoots to $G^e=(X^e,A^e)$ whose node features $X^e$ go through TransConv layers. If $X^e$ are missing, then the conv. layer doesn't produce anything meaningful to then estimate the edge probabilities (see Fig. 2). To surpass this hurdle, we added 7 features regarding centralities: node degree, betweeness, closeness, harmonic centrality, clustering coefficient, Katz centrality, Laplacian centrality. In this way, at least we have something interesting to work with and not rely only on the topology of the graphs. Here are the performance against SoTA in terms of validity and fidelity on 5-fold cross-validations where the oracle $\\Phi$ is a 3-layer GCN with test accuracy of 86.8% for MUTAG. Unfortunately, even after hypeparam optimization was done on NCI1 with the introduced node features, any kind of GCN (with any layer) and UGFormer [3] with the hyperparameter search space introduced in the original paper do not reach more than 40% of accuracy in the test set. We ran experiments with these oracles for NCI1, however the fidelity of the explainers was negative, which suggests that the explainers are actually doing adversarial attacks rather than explanations on the oracle [1]. Hence, we decided to discard NCI1 and show only MUTAG. *We want to point out that these two datasets aren't suitable for benchmarking purposes since, again, message passing mechanisms in GNNs rely on node feature aggregations on the neighbors. These two datasets don't have node features, and we are a bit puzzled how SoTA methods used them to compare against each other.*\n|  | Validity | Fidelity |\n|---|---|---|\n| CF$^2$ | 0.026$\\pm$0.026 | 0.026$\\pm$0.026 |\n| CF-GNNExp | 0.447$\\pm$0.026 | 0.237$\\pm$0.132 |\n| CLEAR | 0.921$\\pm$0.026 | 0.395$\\pm$0.079 |\n| iRand | 0.026$\\pm$0.026 | 0.026$\\pm$0.026 |\n| RSGG-CE | 0.947$\\pm$0.000 | 0.737$\\pm$0.158 |\n| GIST | **1.0$\\pm$0.000** |**0.737$\\pm$0.105**|\n\n[1] Prado-Romero et al. A Survey on Graph Counterfactual Explanations: Definitions, Methods, Evaluation, and Research Challenges. ACM CSUR 2024.\n\n[2] Bajaj et al. Robust counterfactual explanations on graph neural networks. NeurIPS'21\n\n[3] Nguyen et al. Universal graph transformer self-attention networks.WWW'22", "claims_and_evidence": "The claims in the paper are mostly correct. The claims are supported by theory and preliminary experiments that show the framework’s potentially ideal behavior.", "methods_and_evaluation_criteria": "The chosen datasets are good choices for their work. However, the authors should consider also adding additional datasets such as NCI1, MUTAG etc as these are common datasets. The authors also have left out a baseline method in counterfactual explanation methods [1].\n[1] Bajaj, Mohit, et al. \"Robust counterfactual explanations on graph neural networks.\" Advances in Neural Information Processing Systems 34 (2021): 5644-5655.", "theoretical_claims": "Briefly checked over theoretical claims and some proofs.", "experimental_designs_or_analyses": "Checked the design of the experimental setups and they are sound.", "relation_to_broader_scientific_literature": "The paper does miss a reference in counterfactual graph explanations see [1]\n[1] Bajaj, Mohit, et al. \"Robust counterfactual explanations on graph neural networks.\" Advances in Neural Information Processing Systems 34 (2021): 5644-5655.", "essential_references_not_discussed": "paper [1] from Neurips 2021 is quite relevant and is neither referenced nor used as a baseline\n[1] Bajaj, Mohit, et al. \"Robust counterfactual explanations on graph neural networks.\" Advances in Neural Information Processing Systems 34 (2021): 5644-5655.", "other_strengths_and_weaknesses": "The paper is well written, theoretically rigorous and well founded.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "See above issues", "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:

Meta-review: The reviewers generally acknowledged that the proposed approach was novel and reasonable.

However, the reviewers still felt that the paper lacked clarity on how and why the process (particularly selecting $G^\epsilon$ and interpolating) is good for generating counterfactuals. This seems to be in part because it is unclear what a good counterfactual would be in different contexts. For example, what does a meaningful counterfactual mean in user networks?  Is it based on outcome label changes (e.g., loan approval vs. rejection), demographic information, or other characteristics? This lack of clarity makes it difficult to evaluate the practical relevance of the method.

Also, the paper does not seem to properly address the interaction between node features and graph structure during counterfactual generation. Real-world counterfactuals often involve complex interactions where changes in node attributes (e.g., changing a student's gender) would naturally affect their connections (e.g., friendship based on different interests). This interdependence between node features and graph structure is a critical consideration in counterfactual generation that appears overlooked [1,2].

Given this, I recommend that the authors revise their paper to more clearly explain what makes a good graph counterfactual in different contexts and then connect that definition with their proposed method. Why will this process produce better counterfactuals w.r.t. the specifically desired qualities of a graph counterfactual?

[1] Ma, Jing, et al. "Learning fair node representations with graph counterfactual fairness." Proceedings of the fifteenth ACM international conference on web search and data mining. 2022.

[2] Ling, Hongyi, et al. "Counterfactual Fairness on Graphs: Augmentations, Hidden Confounders, and Identifiability." (2024).
Decision: Accept (poster)