Paper deep dive

Faithful, Sufficient and Understandable: Rethinking Graph Counterfactual Explanations via Discrete Diffusion Inversion

David Bechtoldt, Sidney Bender

Year: 2026Venue: arXiv preprintArea: cs.LGType: PreprintEmbeddings: 90

Intelligence

Status: not_run | Model: - | Prompt: - | Confidence: 0%

Entities (0)

No extracted entities yet.

Relation Signals (0)

No relation signals yet.

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:Graph Neural Networks (GNNs) achieve strong predictive performance on graph-structured data across domains such as chemistry, biology, and network analysis, yet they provide no intrinsic explanation of their predictions. This limits their adoption in high-stakes and safety-critical settings. Counterfactual explanations address this by revealing the minimal structural modifications that would change a model's prediction. On graphs, however, such a modification is hard to produce. The search space is discrete and combinatorial, and a valid answer must respect categorical node and edge types together with domain rules such as chemical valency in the case of molecular graphs. Existing explainers give up one of two things. Either edits are not held on the data manifold, or the search does not span the full edit space. We propose Graph Diffusion Counterfactual Explanation via Inversion (GDCE-I), which gives up neither. A discrete denoising diffusion model with a novel discrete inversion scheme enables distribution-aware edits leveraging the whole domain edit space. We further address the incomplete and inconsistent evaluation of graph counterfactuals by deriving a framework of explanation desiderata and applying it to every method under one shared protocol. Across four benchmarks, GDCE-I outperforms related work by a large margin on the defined framework. For the molecular domain, we further qualitatively show that GDCE-I attains interpretable in-distribution solutions.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

88,338 characters extracted from source content.

Expand or collapse full text

Faithful, Sufficient and Understandable: Rethinking Graph Counterfactual Explanations via Discrete Diffusion Inversion David Bechtoldta,b Sidney Bendera,b Address: aMachine Learning Group, TU Berlin, 10587 Berlin, Germany Address: bBIFOLD–Berlin Institute for the Foundations of Learning and Data, Berlin, Germany Abstract Graph Neural Networks (GNNs) achieve strong predictive performance on graph-structured data across domains such as chemistry, biology, and network analysis, yet they provide no intrinsic explanation of their predictions. This limits their adoption in high-stakes and safety-critical settings. Counterfactual explanations address this by revealing the minimal structural modifications that would change a model’s prediction. On graphs, however, such a modification is hard to produce. The search space is discrete and combinatorial, and a valid answer must respect categorical node and edge types together with domain rules such as chemical valency in the case of molecular graphs. Existing explainers give up one of two things. Either edits are not held on the data manifold, or the search does not span the full edit space. We propose Graph Diffusion Counterfactual Explanation via Inversion (GDCE-I), which gives up neither. A discrete denoising diffusion model with a novel discrete inversion scheme enables distribution-aware edits leveraging the whole domain edit space. We further address the incomplete and inconsistent evaluation of graph counterfactuals by deriving a framework of explanation desiderata and applying it to every method under one shared protocol. Across four benchmarks, GDCE-I outperforms related work by a large margin on the defined framework. For the molecular domain, we further qualitatively show that GDCE-I attains interpretable in-distribution solutions. Keywords: Graph Neural Networks , Counterfactual Explanations , Diffusion Models , Molecular Graphs 1 Introduction Graph Neural Networks [50] have emerged as the de facto standard for learning graph-structured data across domains such as chemistry, biology, and network analysis, achieving breakthroughs in tasks such as molecular property prediction, drug discovery, and toxicity analysis [52, 54, 64]. Despite their predictive abilities, GNNs operate predominantly as black-box models. This lack of transparency undermines the decision-making process, severely limiting its adoption in high-stakes scenarios where interpretability and safety are paramount [66, 11, 41]. For example, the discovery of a new structural class of antibiotics was guided not by the prediction of twelve million candidates by a graph neural network, but by the chemical substructures the model had associated with selective activity [63]. To uncover such explanations, Explainable AI (XAI) offers a diverse set of approaches to explain a neural network. A prominent branch of XAI is attribution-based methods, such as Layer-wise Relevance Propagation [3] that was further developed for GNNs (GNN-LRP) [51]. These techniques answer the "why" behind a model’s decision by identifying and highlighting the most influential features or structural motifs. Figure 1: GDCE-I generates graph counterfactuals by inverting a discrete diffusion trajectory. Respecting the data manifold and covering the full edit space is what makes the explanations domain-valid. Another approach to explaining a model is counterfactual explanations [61, 15, 42]. They provide a realistic counterexample for a given input, which differs as little as possible to alter the classifier’s prediction. Rather than attributing relevance to existing structures, counterfactuals answer: "What minimal changes to the input graph would alter the model’s prediction?" In computational chemistry, this could translate to targeted structural edits that can neutralize a toxicophore. However, translating counterfactual generation to the graph domain introduces unique challenges that are largely absent in continuous domains such as computer vision. Graphs are inherently discrete, non-euclidean, and combinatorial objects [42, 17]. Crucially, real-world graph representations, such as molecules or proteins, reside in a highly sparse topological space [60]. Consequently, even minor topological perturbations can easily violate strict domain-specific rules, such as chemical valency, resulting in structurally invalid and semantically meaningless instances. Early approaches relied on heuristic perturbation strategies restricted solely to edge deletions [42, 30]. This constrains the counterfactual search space, prohibiting the addition of necessary structural motifs or the alteration of edge and node types. To improve the realism of the explanations, a parallel line of work turns to generative models that keep counterfactuals close to the data distribution [17, 10, 32]. Although more recent heuristic methods support edge additions and node-type changes [31], most methods in both families still operate on a binary adjacency matrix that cannot represent categorical edge types. To systematically address these limitations, we propose Graph Diffusion Counterfactual Explanation via Inversion (GDCE-I) 11 1 A preliminary version of this work was presented at the ESANN 2026 Conference [4]. This paper presents the fully extended framework.. By combining discrete denoising diffusion models [60] with classifier-free guidance [37, 20] and an edit-friendly inversion technique, our approach allows for comprehensive modifications, including targeted edge additions, deletions, edge and node type alterations, within a data-manifold-aware generation process (Figure 1). Figure 2: High-level illustration of GDCE-I. By manipulating the latent space of the learned diffusion model, we can generate distribution-aware and sparse counterfactuals. GDCE-I integrates discrete diffusion models with classifier-free guidance, so that the model captures the conditional distribution of valid graphs directly. Its core contribution is an edit-friendly inversion scheme for discrete diffusion, an inversion that records the sampling stochasticity of a given graph, so the graph can be reconstructed and then minimally edited by changing only the target condition. We derive it by exploiting the Gumbel-Max trick in a discrete diffusion setting. We traverse a reference trajectory of the given graph in the reverse direction and, at every step, construct the Gumbel noise that forces the guided reverse posterior to reproduce that trajectory, using a truncated-Gumbel (A⋆A -sampling) construction [33]. The resulting posterior noise space reconstructs the original graph exactly under its own condition. Re-injecting this same noise during a reverse generation pass guided toward a new target property therefore preserves the structural identity of the original graph as far as the new target permits, favoring edits that are both minimal and in distribution. . The trade-off between sparsity and the desired property flip is controlled via a dynamic skip-parameter τ. A high-level illustration can be contemplated in Figure 2. Our main contributions are summarized as follows: 1. A Novel Generative Inversion Framework: We introduce GDCE-I, the first method to unify discrete graph diffusion, classifier-free guidance, and Gumbel-Max inversion. This framework enables precise, edit-friendly manipulation of discrete graph structures. 2. Benchmarking on Classifier-Distilled Datasets: Through a rigorous evaluation of the Mutagenicity [26], Benzene [48, 1], PROTEINS [9, 14] and TWITTER [39, 40] dataset against baselines such as CF2CF^2 [58], C2Explainer [31], XPlore [49], UCExplainer [16], and D4Explainer [10], we show that GDCE-I is the only method that jointly produces faithful and understandable counterfactuals. We further provide qualitative evidence that GDCE-I recognizes and alters functional groups via realistic chemical substitutions for Mutagenicity and Benzene. 2 Related Work Counterfactual Explanations Although there are counterfactual explanation methods for domains such as natural language [12] and proteins [28], the most established fields are tabular data and computer vision. Tabular data often is low-dimensional and specific properties of the input features are known, so there exist a lot of approaches directly using this knowledge, e.g., in the form of Integer Linear Programming [46] or other explicit closed-form optimization schemes such as in DiCE [35]. For both tabular data and computer vision, there are various approaches that use a generative model to filter gradients to stay in the data manifold while moving towards the desired class [15, 45, 2, 23, 62, 7, 67, 24]. These approaches cannot be easily transferred to graphs due to the discrete nature. In addition, there are approaches for both tabular and computer vision in the form of distillation [25, 8]. These approaches are in principal transferable to graphs, but one has to choose a suitable generative model. Heuristic and mask-based methods for Graphs Early approaches rely on heuristic perturbations. CF-GNNExplainer and CF2 [30, 58] learn a continuous mask over the existing edge set, which restricts the search space to edge deletions only and, therefore, cannot introduce the structural motifs that a valid counterfactual may require. C2Explainer [31] broadens this space to edge additions and node-feature perturbations, and XPlore [49] pursues the same direction, driving gradient-guided perturbations of the adjacency and the node-feature matrix jointly. InduCE [59] instead attacks the per-instance optimization itself, learning a reinforcement-learning policy over edge additions and deletions that transfers to unseen inputs without instance-specific training. It targets node rather than graph classification and is therefore outside the scope of our comparison. All of these methods operate on a binary adjacency matrix and thus cannot predict categorical edge types, i.e. they cannot distinguish a single, double, or aromatic bond between the same pair of atoms, a distinction that is essential for chemical validity. UCExplainer [16] is the exception among the mask-based methods. It perturbs node features, topology, and bond types alike and is therefore, together with GDCE-I, the only method that can be evaluated against an edge-feature-aware classifier. A complementary line explains the model rather than the instance. Global graph counterfactual explanation [27] examines a compact set of subgraph substitution rules that flip the prediction across many graphs at once, trading per-instance faithfulness for coverage. We target instance-level counterfactuals throughout. Generative methods for Graphs A second line of work generates counterfactuals from a learned model of the data distribution. CLEAR [32] employs a graph variational autoencoder (VAE) that decodes a Bernoulli adjacency matrix together with node features but does not assign bond types. CGCF [17] also traverses a continuous VAE latent space and, unlike CLEAR, it decodes categorical edge types, but it shares the more fundamental drawback that a continuous latent relaxation is a questionable model for the highly constrained, discrete nature of graphs. RSGG-CE [43] instead adopts a GAN, again without categorical edge types. In the molecular domain, MEG [38] employs a reinforcement-learning agent that edits the molecular graph with valence-valid operations. A related line of work for molecules operates outside the graph representation altogether, namely MMACE, which enumerates chemically valid neighbors through SELFIES string mutations. LLM-GCE [18] also operates on textual input, generating counterfactuals with large language models for Molecules. Diffusion-based methods are the most directly related. D4Explainer [10] trains a discrete denoising diffusion model with a counterfactual loss term to generate in-distribution explanations. However, it operates on a binary adjacency matrix without categorical nodes or edge types, and its counterfactual objective is incorporated only at training time. Evaluating Explanations A major challenge in designing explanation techniques is the issue of evaluation. Ground-truth explanations are rarely available, and the notion of a good explanation depends on the use case. The question of evaluation has been central, with early foundations including [53] and [56], with the latter proposing a set of practical desiderata for explanation techniques. While the evaluation of explanations has been extensively covered for attribution methods (e.g. [47, 36]), for visual counterfactuals in [7], and counterfactuals for tabular data (e.g. [35]), there have been comparatively fewer such studies in the context of graph counterfactual explanations. In summary, while similar metrics to the one suggested by us have been proposed in the context of tabular and vision data, previous work on graph counterfactual evaluation has predominantly focused on a form of flip-ratio and sparsity. 3 Desiderata of Counterfactuals To enhance the usefulness of graph counterfactual explainers (GCEs), and analogous in large parts to the desiderata-driven framework established for visual counterfactuals by Bender et al. [7], we take as a starting point the holistic explanation desiderata formulated by Swartout and Moore (1993) [56]. These desiderata, originally proposed in the context of explaining expert systems, are ‘fidelity’, ‘understandability’, ‘sufficiency’, ‘low construction overhead’, and ‘efficiency’. In the following, we contribute an instantiation of the first three desiderata specifically tailored to counterfactual explanations on graphs and operationalize them using concrete metrics: Non-Adversarial Rate (NA), a threefold Sparsity breakdown (Edge, Node, Edge Type), and Non-Adversarial Flip Rate (NAFR). 3.1 Fidelity For an explanation to be useful, it should faithfully describe what the model does. As noted in [56], an incorrect or misleading explanation is worse than no explanation at all. Instantiating this desideratum to counterfactual explanations following [7], we propose the following formalization: Assuming a factual graph G and a classifier f that varies locally following some dominant direction w, the counterfactual graph G′G is faithful, i.e., represents what the model does, if it meets the following three criteria: 1. The counterfactual should be plausible and thus be on the data manifold, i.e., G′∈ℳG , adhering to structural and domain-specific rules (such as valency). 2. The counterfactual’s immediate neighborhood, i.e. ξ∈ℳ:d⁡(ξ,G′)<δ\ξ :d(ξ,G )<δ\, should also be dominantly counterfactual. In practice, testing these properties directly is not always possible due to discrete, combinatorial graph spaces and limited knowledge of ℳM. It is interesting to note that most state-of-the-art GCEs, such as CLEAR [32] and D4Explainer [10], ensure (i) by limiting the search for G′G to the data manifold ℳM through a generative model or not all [30, 31, 16]. However, they do not address (i) and (i), i.e., whether the transformation G↦G′G G is associated with a robust model response that allows resolutely crossing the decision boundary. Selecting any on-manifold transformation that flips the classifier (e.g., a minimal one) risks producing an adversarial example (cf. [57, 55]), as the counterfactual search may leverage spurious local variations in the classification function f that are not representative of how f varies more globally. Spurious local variations are commonplace in GNN classifiers [65] and also occur along the data manifold ℳM [55]. Most existing counterfactual methods lack a mechanism to address potential spurious variations on the manifold. Non-Adversarial Rate (NA) To operationalize fidelity, we evaluate whether counterfactuals occupy robust semantic basins rather than fragile adversarial pockets. Analogous to [7], we validate the generated graphs against a retrained surrogate model fsurf_sur (distilled independently from f). This measures the transferability of the counterfactual flip, confirming it relies on robust structural features rather than weight-specific noise: Fidelity: NA=Nflipped_trueNflippedFidelity: NA= N_flipped\_trueN_flipped (1) where Nflipped_trueN_flipped\_true represents the count of samples that also successfully flip the prediction of fsurf_sur. Higher NA values indicate greater semantic stability and fidelity to the underlying decision process. Further in the molecular domain, we will report SMILES (↑ ), the fraction of counterfactuals that RDKit [44] can parse and sanitize under valence and bond-compatibility rules. SMILES is defined only on the two molecular datasets, Mutagenicity and Benzene. 3.2 Understandability Understandability refers to whether an explanation is understandable to its intended recipient, who is usually a human. Explanations should be presented at an appropriate level of abstraction and be concise enough to be quickly assimilated. In the context of graph counterfactual explanations, an intrinsic level of understandability is guaranteed by the fact that generated counterfactuals live in the same input domain as factuals and reside on the data manifold ℳM (i.e., inspectable discrete attributed graphs). Following [7], we capture the concise nature required for understandability through structural sparseness across the transformation G↦G′G G . To evaluate understandability fairly in the graph domain across different baselines is complicated by an asymmetry in their action spaces. Many baselines operate on a binary adjacency matrix and can only add or delete edges, whereas GDCE-I additionally edits atom and bond types. Reducing both to a single distance is therefore misleading. Further predicting the existence of a bond is chemically ambiguous (a single and a double bond between the same atoms are indistinguishable in a binary adjacency matrix), so any proximity computed on that representation abstracts away precisely the information that determines molecular identity. We therefore decompose structural minimality into three complementary sparsity metrics that jointly cover the attributed perturbation space while preserving comparability with edge-only baselines: Edge Sparsity. Topological minimality measured as the fraction of added or removed edges relative to the original graph’s edge set: Edge Sparsity(G,G′)=max(1−|E△E′||E|,0)Edge Sparsity(G,G )=max(1- |E E ||E|,0) (2) where △ denotes the symmetric difference of the edge sets. The term |E△E′||E| |E E ||E| is sometimes reported under the name ‘Modification Ratio’ in related work papers, but we want to emphasize the connection between sparsity and understandability also elaborated in other interpretability research like [21]. Node Sparsity. The fraction of node-type substitutions across all nodes, calculated relative to the node feature matrix: Node Sparsity(G,G′)=1−∑i=1|X|[xi≠xi′]|X|Node Sparsity(G,G )=1- _i=1^|X|1[x_i≠ x_i ]|X| (3) Edge Type Sparsity. Semantic changes on structurally preserved edges, measuring bond-type reassignments on retained edges: Edge Type Sparsity(G,G′)=1−|e∈E∩E′∣attr(e)≠attr′(e)||E∩E′|Edge Type Sparsity(G,G )=1- |\e∈ E∩ E (e) (e)\||E∩ E | (4) These three metrics isolate topological modifications, node-attribute substitutions, and edge-type shifts to provide a fine-grained quantification of concise, understandable edits. To illustrate the difference between fidelity (measured via NA) and understandability (measured via Sparsity), we provide practical examples in Table 1. Faithful (High NA) but not Understandable (Low Sparsity) A counterfactual that robustly flips both the target model and the surrogate model (high NA), but achieves this via an extensive graph-wide rewrite involving widespread topological rewiring, node substitutions, and edge-type modifications (poor Edge, Node, and Edge Type Sparsity) that overwhelm human inspection. Understandable (High Sparsity) but not Faithful (Low NA) A counterfactual with minimal structural edits (e.g., changing a single atom type or edge, yielding high Sparsity) that successfully flips the target classifier f, but fails to flip the surrogate model fsurf_sur (low NA) because it exploits a fragile, weight-specific adversarial vulnerability rather than a robust decision boundary. Faithful (High NA) but Insufficient (Low NAFR) A counterfactual method that produces stable, non-adversarial edits when it succeeds (high NA), but fails to generate valid counterfactuals for a large fraction of the dataset, resulting in a low absolute Non-Adversarial Flip Rate (NAFR) and failing to globally map the classifier’s behavior. Table 1: Practical examples of graph counterfactuals that meet only some of the operationalized desiderata (NA, Sparsity, NAFR), adapting the conceptual framework of [7]. 3.3 Sufficiency Following [7], sufficiency requires charting the decision boundary globally across numerous distinct instances rather than exploiting localized or isolated successes. We operationalize sufficiency via the Non-Adversarial Flip Rate (NAFR). Non-Adversarial Flip Rate (NAFR) Bridging both sufficiency and fidelity [7], NAFR tracks the absolute proportion of generated samples across the dataset that simultaneously alter the target model’s prediction and induce a genuine, transferable semantic shift confirmed by the surrogate classifier fsurf_sur: Sufficiency:NAFR=1N∑i=1N(f(Gi′)=yt∧fsur(Gi′)=yt)Sufficiency:NAFR= 1N _i=1^N1 (f(G_i )=y_t f_sur(G_i )=y_t ) (5) By combining coverage and transferability into a single metric, NAFR isolates functional, structurally coherent graph counterfactuals from those that either fail to flip the target model or merely exploit imperceptible adversarial vulnerabilities. 4 Method Discrete Denoising Diffusion on Graphs Let a graph be defined as G=(X,E)G=(X,E), where X∈0,1n×aX∈\0,1\^n× a represents the categorical node features and E∈0,1n×n×bE∈\0,1\^n× n× b denotes the categorical edge features for n nodes. The fundamental objective of the forward diffusion process is to progressively transform an input graph G∼pdataG p_data into a sequence of increasingly noisy states, ultimately reaching a pure noise distribution GTG^T at the final timestep T. While standard continuous diffusion models corrupt data by injecting Gaussian noise, applying this paradigm directly to adjacency matrices destroys the inherent sparsity of graphs, resulting in dense, fractional structures. To address this, discrete denoising diffusion models, such as DiGress [60], define Markov transitions directly over categorical node and edge types via transition matrices [QXt]ij=q⁡(xt=j|xt−1=i)[Q^t_X]_ij=q(x^t=j|x^t-1=i) and [QEt]ij=q⁡(et=j|et−1=i)[Q^t_E]_ij=q(e^t=j|e^t-1=i). Similar to the continuous DDPM [19] forward process, the forward diffusion in discrete spaces is then defined as a Markovian process that iteratively adds noise at each timestep q⁡(Gt|Gt−1)=(Xt−1QXt,Et−1QEt).q(G^t|G^t-1)=(X^t-1Q^t_X,E^t-1Q^t_E). (6) Due to the Markovian property, it is not necessary to apply noise recursively. By defining the cumulative transition matrix Q¯t=Q1Q2…Qt Q^t=Q^1Q^2… Q^t, we can directly sample the noisy graph at any arbitrary timestep t from the initial clean graph G: q⁡(Gt|G)=(XQ¯Xt,EQ¯Et).q(G^t|G)=(X Q^t_X,E Q^t_E). (7) The goal of the generative model is to reverse this forward process. To do so, DiGress formulates the reverse process as a product of independent transitions over all nodes and edges pθ(Gt−1|Gt)=∏1≤i≤npθ(xit−1|Gt)∏1≤i,j≤npθ(eijt−1|Gt),p_θ(G^t-1|G^t)= _1≤ i≤ np_θ(x^t-1_i|G^t) _1≤ i,j≤ np_θ(e^t-1_ij|G^t), (8) where the individual marginals are computed by marginalizing over the clean state predictions p^iX(x) p^X_i(x) produced by the denoising neural network pθ(xit−1∣Gt)=∑xq⁡(xit−1∣xit,xi0=x)⋅p^iX(x)p_θ(x^t-1_i G^t)= _x\,q(x^t-1_i x^t_i,x^0_i=x)· p^X_i(x) (9) and pθ(eijt−1∣Gt)p_θ(e^t-1_ij G^t) is computed accordingly. Classifier-Free guidance In conditional graph generation, traditional classifier-based guidance [13] relies on an auxiliary property regressor evaluated on noisy intermediate graphs GtG^t [60]. However, assigning meaningful continuous properties to such invalid, highly corrupted states is fundamentally ill-posed and yields unreliable guidance gradients. Classifier-Free Guidance (CFG) [37, 20] circumvents this issue by jointly training a single generative model for both conditional and unconditional generation. During training, the conditioning variable y (e.g., a target class or continuous property) is randomly replaced by a null token ∅ with a predefined probability puncondp_uncond. During inference, the model extrapolates toward the conditional objective governed by a guidance scale s. Formally, the conditioned reverse process pθ(Gt−1|Gt,y)p_θ(G^t-1|G^t,y) is factorized over all nodes and edges under the assumption of conditional independence pθ(Gt−1|Gt,y)=∏1≤i≤npθ(xit−1|Gt,y)∏1≤i,j≤npθ(eijt−1|Gt,y).p_θ(G^t-1|G^t,y)= _1≤ i≤ np_θ(x^t-1_i|G^t,y) _1≤ i,j≤ np_θ(e^t-1_ij|G^t,y). (10) To compute the individual marginals, the model predicts the clean state from the noisy intermediate graph. For a node i, this marginalization is given by pθ(xit−1∣Gt,y)=∑xq⁡(xit−1∣xit,xi0=x)⋅fθ(xi0=x|Gt,y)p_θ(x^t-1_i G_t,y)= _x\,q(x^t-1_i x^t_i,x^0_i=x)· f_θ(x^0_i=x|G^t,y) (11) where the clean state prediction p^θ p_θ incorporates the classifier-free guidance mechanism. By linearly combining the conditional and unconditional predictions with the guidance scale s, the guided prediction is formulated as fθ(xi0=x|Gt,y)=pθ(xi0|Gt)+s⁡(pθ(xi0|Gt,y)−pθ(xi0|Gt))f_θ(x^0_i=x|G^t,y)=p_θ(x^0_i|G^t)+s (p_θ(x^0_i|G^t,y)-p_θ(x^0_i|G^t) ) (12) and the edge marginals pθ(eijt−1∣Gt,y)p_θ(e^t-1_ij G^t,y) are computed accordingly. Categorical Sampling via the Gumbel-Max Trick Both the forward and the reverse process require drawing samples from categorical distributions over node and edge types. Our inversion scheme relies on making this sampling step reparameterizable, so that its stochasticity can be recorded and later replayed. This is achieved with the Gumbel-Max trick. Let p∈ΔK−1p∈ ^K-1 be a categorical distribution over K classes, and let g=(g1,…,gK)g=(g_1,…,g_K) be a vector of independent standard Gumbel variables, gk∼Gumbel⁡(0,1)g_k (0,1), which can be sampled as gk=−log⁡(−log⁡uk)g_k=- (- u_k) with uk∼⁡(0,1)u_k (0,1). Then argmaxk⁡(log⁡pk+gk)∼Categorical⁡(p), *arg\,max_k ( p_k+g_k ) (p), (13) that is, perturbing the log-probabilities with Gumbel noise and taking the argmax yields an exact sample from p. Crucially, this decomposes a categorical draw into a deterministic component, the log-probabilities log⁡p p that depend on the conditioning, and a stochastic component, the noise g that is independent of the content. Holding g fixed while altering log⁡p p therefore changes the resulting sample only at positions where the shift in log-probabilities is large enough to move the argmax to a different class. This is the mechanism GDCE-I exploits to invert the discrete diffusion process in Section 4.1. 4.1 GDCE-I Building upon the theoretical foundations of discrete diffusion and classifier-free guidance, we present Graph Diffusion Counterfactual Explanations via Edit-Friendly Inversion (GDCE-I). As a fundamental prerequisite to our framework, we first train a conditional discrete diffusion model on the target dataset. The conditioning signal utilized during this training phase can be derived directly from the predictions of the pre-trained black-box model, a process we term the distillation of the classifier into the discrete diffusion model. Notably, this conditional generative framework is highly versatile. The conditioning variables are not restricted to categorical classifier labels, but can seamlessly incorporate ground-truth variables, continuous physical properties (e.g., molecular logP), or even multi-dimensional property vectors. Once this conditional generative backbone is fully established, we can employ our inversion procedure to generate precise counterfactuals. In continuous Denoising Diffusion Probabilistic Models (DDPMs), recent work has shown that the sequence of noise vectors drawn during the reverse process encodes the structural backbone of the generated sample, so that fixing this noise while altering the conditioning enables semantically meaningful edits that tightly preserve the original structure [22]. We translate this “edit-friendly” paradigm to the discrete graph domain. The central obstacle is that discrete diffusion samples from categorical transitions rather than adding Gaussian noise. We therefore realize an analogous noise space through the Gumbel-Max trick of Section 4, which separates each categorical draw into deterministic log-probabilities and content-independent Gumbel noise (Eq. 13). A naive realization would sample fresh Gumbel noise along the forward chain and hope the reverse process retraces it. This does not hold in general because the noise would be recorded against the forward transitions QtQ^t, yet replayed against the learned reverse posterior pθ(⋅∣Gt,y)p_θ(· G^t,y), which is a different distribution. We instead construct an edit-friendly posterior noise space that guarantees exact reconstruction, using the truncated-Gumbel (A⋆A -sampling) construction [33]. Reference trajectory Given an input graph G=(X,E)G=(X,E) with its (distilled) condition y, we first draw a single reference trajectory G^0,G^1,…,G^T G^0, G^1,…, G^T with G^0=G G^0=G by iterating the discrete forward process of Eq. 6, retaining only the visited states G^t=(X^t,E^t) G^t=( X^t, E^t). Posterior noise recording We then traverse the trajectory in the reverse direction and, for every node and edge independently, record the Gumbel noise that forces the guided reverse posterior to reproduce the reference state. We describe the construction for a single categorical variable (one node; edges are analogous). At the reverse step from t=s+1t=s+1 to s, let ℓ∈ℝK ^K denote that node’s guided reverse-posterior log-probabilities over the K classes, ℓ=log⁡pθ(Xs∣G^s+1,y) = p_θ(X^s G^s+1,y), and let v⋆v be the class realized at that node in the reference state X^s X^s. We seek Gumbel noise g∈ℝKg ^K that selects this class under the Gumbel-Max rule of Eq. 13, argmaxk⁡(ℓk+gk)=v⋆. *arg\,max_k ( _k+g_k )=v . (14) Following the truncated-Gumbel (A⋆A -sampling) construction [33], we build the perturbed log-probabilities ϕk=ℓk+gk _k= _k+g_k directly. Let Z=log∑keℓkZ= _ke _k be the log-normalizer (here Z=0Z=0, since pθp_θ is normalized) and let M=Z+γ0M=Z+ _0 with γ0∼Gumbel⁡(0,1) _0 (0,1) be the maximal perturbed value. We assign M to the target class and draw every other class as an independent Gumbel⁡(ℓk)Gumbel( _k) value truncated to lie below M: ϕk=M,k=v⋆,−log⁡(e−(ℓk+γk)+e−M),k≠v⋆,γk∼Gumbel⁡(0,1). _k= casesM,&k=v ,\\[2.0pt] - \! (e^-( _k+ _k)+e^-M ),&k≠ v , cases _k (0,1). (15) By construction argmaxk⁡ϕk=v⋆ *arg\,max_k _k=v . Since ϕ=ℓ+gφ= +g, the reusable, condition-independent noise is recovered by subtracting the log-probabilities, g=ϕ−ℓ.g=φ- . (16) Collecting g over all nodes (resp. edges) yields the node noise gsXg_s^X (resp. the edge noise gsEg_s^E, symmetrized across the adjacency). We store all recorded noise in a library =(gsX,gsE)s=0T−1G=\(g_s^X,g_s^E)\_s=0^T-1 together with the reference states. Guided generation. To produce a counterfactual, we replay the reverse process with the same recorded noise but a new target condition y′y . Stepping from t to t−1t-1, we compute the guided posterior pθ(Xt−1∣Gt,y′)p_θ(X^t-1 G^t,y ) and sample deterministically with the stored noise, Xt−1=one_hot(argmax⁡(log⁡pθ(Xt−1∣Gt,y′)+gt−1X)),X^t-1=one\_hot ( *arg\,max ( p_θ(X^t-1 G^t,y )+g_t-1^X ) ), (17) and reconstruct Et−1E^t-1 symmetrically from gt−1Eg_t-1^E. By construction, replaying with the original condition (y′=y =y) recovers the input graph exactly. Under a changed condition y′y , a position changes only where the guidance-induced shift in log-probabilities is large enough to move the argmax past the recorded margin. Edits are therefore concentrated precisely where the target property demands them, yielding sparse, in-distribution counterfactuals, and resolving the mismatch of the naïve scheme, whose noise is recorded and replayed against different distributions. We show a comparison in 5.3. Dynamic budget search. Replaying the full trajectory from T can introduce more changes than are needed to flip the classifier. We therefore introduce a budget τ∈1,…,Tτ∈\1,…,T\: rather than replaying from T, we start the guided reverse pass from the reference state G^τ G^τ and denoise down to G0G^0, reusing (gsX,gsE)s<τ\(g_s^X,g_s^E)\_s<τ. The framework searches over increasing τ and returns the counterfactual at the smallest budget for which f⁡(G0)=y′f(G^0)=y , which identifies the minimal structural deviation required to alter the prediction. Unlike DiGress, which draws plain categorical samples during generation [60], GDCE-I’s Gumbel-Max reparameterization is what renders the discrete trajectory invertible in the first place. The complete procedure, namely the reference trajectory, posterior recording, and budgeted guided replay, is summarized in Algorithm 1 (Appendix A). 5 Experiments To comprehensively evaluate the efficacy of our proposed framework, we design our experiments to answer the following two primary research questions: 1. Quantitative Benchmarking: How does GDCE-I compare against state-of-the-art baseline explainers in terms of our defined evaluation framework on standard graph classification tasks? 2. Qualitative Analysis: Can GDCE-I produce understandable edits? 5.1 Experimental Setup Datasets For the discrete graph classification tasks, we evaluate our method on two widely adopted molecular benchmarks: Mutagenicity [26] and Benzene [48, 1]. In these datasets, graphs represent chemical compounds. The binary label of Mutagenicity indicates a mutagenic effect, whereas Benzene is a structural attribution benchmark whose label indicates the presence of a benzene ring. The focus on molecules is deliberate, and it concerns what can be measured rather than what the method supports. GDCE-I operates on categorical node and edge types and assumes nothing chemistry-specific. Molecular graphs, however, come with distributional constraints like valence rules. In-distribution behavior is therefore observable. We additionally evaluate on two non-molecular benchmarks from the TUDataset collection [34], both without edge types. PROTEINS [9, 14] represent proteins as graphs of secondary-structure elements, with three categorical node labels (helix, sheet, turn) and a binary label separating enzymes from non-enzymes. TWITTER [40, 39] represents a tweet as a word co-occurrence graph, where nodes are words, and the binary label is the sentiment of the tweet. Baselines We benchmark GDCE-I against graph counterfactual explainers that produce instance-level counterfactuals for graph classification, spanning the heuristic/mask-based (CF2CF^2 [58], C2Explainer [31], XPlore [49], UCExplainer [16]) and generative (D4Explainer [10]) families of Section 2. All baselines are re-evaluated under a single common protocol: identical dataset preprocessing, test split, sampling seeds, and metric definitions. Crucially, every method is optimized against and evaluated by the same classifier. We train a binary-adjacency GCN, which every method can consume and against which all of them are measured, and additionally an edge-feature-aware GINE, reserved for the two methods that predict bond types (GDCE-I and UCExplainer). Both are trained from scratch on the shared training split. Architectures and accuracies are given in appendix B. PROTEINS and TWITTER carry no edge types and, therefore, have a GCN classifier only. Counterfactuals evaluation A counterfactual explanation must name a realizable modification of the input, so we require the counterfactual to lie in the same space as the input: one-hot atom types, one-hot bond types, and binary edges. Methods that optimize a continuous relaxation are therefore discretized before any metric is computed. Node and bond vectors are projected back onto the simplex by arg⁡max , soft edge masks are thresholded at 0.50.5, and the Flip Rate is re-evaluated on the resulting graph. Two baselines are affected: UCExplainer returns node and bond vectors with several simultaneously active entries, and D4Explainer evaluates its flip on sigmoid-weighted edges rather than on a thresholded adjacency. For fair comparison, we report the post-discretisation value. Further, CF2CF^2, C2Explainer, XPlore and D4Explainer operate on a binary adjacency and predict no bond types, so SMILES reconstruction requires a convention. CF2CF^2 only deletes edges: every surviving edge retains the bond order of the input, and no assignment is needed. C2Explainer, XPlore and D4Explainer can additionally add edges, which carry no bond label. We assign these a single bond. This is the most frequent bond type in both datasets (81.3%81.3\% of bonds in Mutagenicity, 56.3%56.3\% in Benzene) and, being the lowest-valence option, the assignment is least likely to trigger a valence violation. 5.2 Quantitative Evaluation on Graph Classification Table 2 reports every method against the same classifier per dataset, so no difference between rows can be attributed to a differing classifier. For every method, we evaluate five runs of 100100 molecules drawn from the test set under identical seeds. All entries are means ± standard deviations over those runs. The only exception is the PROTEINS dataset, which is smaller, and we therefore evaluate on the whole test set. GDCE-I attains the highest Flip Rate on all four datasets. This is unchanged under NAFR, which additionally requires the flip to be confirmed by the control judge, and GDCE-I likewise leads the SMILES column on both datasets on which it is defined. It therefore makes the strongest case for altering the classifier’s prediction while returning counterfactuals that remain on the data manifold, and it does so while operating, together with UCExplainer, in the largest edit space of the compared methods. UCExplainer attains the maximum edge score of 1.0001.000 but just because it fools the classifier by adding entry in one-hot encoded vectors which the classifier never saw. Among the methods that do edit topology, GDCE-I preserves the most of it on Mutagenicity, Benzene, and TWITTER. On PROTEINS, XPlore is ahead (0.8320.832 vs 0.7470.747) but just with a lower NAFR 0.6490.649 against GDCE-I 0.7470.747. On atom types, GDCE-I leads outright on three of the four datasets. desiderata sufficiency understandability fidelity Method FR (↑ ) NAFR (↑ ) EdgeSp. (↑ ) NodeSp. (↑ ) EdgeTypeSp. (↑ ) NA (↑ ) SMILES (↑ ) Mutagenicity CF2CF^2 [58] 0.622±0.0290.622_± 0.029 0.510±0.0190.510_± 0.019 0.396±0.0200.396_± 0.020 – – 0.8200.820 0.508±0.0160.508_± 0.016 C2Explainer [31] 0.688±0.0160.688_± 0.016 0.558±0.0280.558_± 0.028 0.000†0.000 – – 0.8110.811 0.002±0.0040.002_± 0.004 XPlore [49] 0.922±0.0180.922_± 0.018 0.586±0.0690.586_± 0.069 0.613±0.0560.613_± 0.056 – – 0.6350.635 0.050±0.0170.050_± 0.017 UCExplainer (GCN) [16] 0.158±0.0440.158_± 0.044 0.148±0.0430.148_± 0.043 1.000±0.0001.000_± 0.000 0.754±0.0360.754_± 0.036 – 0.9370.937 0.088±0.0320.088_± 0.032 UCExplainer (GINE) 0.260±0.0440.260_± 0.044 0.186±0.0350.186_± 0.035 1.000±0.0001.000_± 0.000 0.738±0.0500.738_± 0.050 0.910±0.0330.910_± 0.033 0.7150.715 0.068±0.0130.068_± 0.013 D4Explainer [10] 0.138±0.0290.138_± 0.029 0.132±0.0330.132_± 0.033 0.597±0.1010.597_± 0.101 – – 0.9570.957 0.120±0.0400.120_± 0.040 GDCE-I (Ours, GCN) 0.970±0.0160.970_± 0.016 0.886±0.0290.886_± 0.029 0.657±0.0110.657_± 0.011 0.892±0.0090.892_± 0.009 0.993±0.0000.993_± 0.000 0.9130.913 0.744±0.0170.744_± 0.017 GDCE-I (Ours, GINE) 0.770±0.0490.770_± 0.049 0.628±0.0680.628_± 0.068 0.680±0.0160.680_± 0.016 0.919±0.0060.919_± 0.006 0.994±0.0020.994_± 0.002 0.8160.816 0.534±0.0690.534_± 0.069 Benzene CF2CF^2 0.566±0.0210.566_± 0.021 0.550±0.0070.550_± 0.007 0.391±0.0050.391_± 0.005 – – 0.9720.972 0.000±0.0000.000_± 0.000 C2Explainer 0.666±0.0380.666_± 0.038 0.610±0.0320.610_± 0.032 0.910±0.0100.910_± 0.010 – – 0.9160.916 0.092±0.0220.092_± 0.022 XPlore 0.670±0.0210.670_± 0.021 0.598±0.0040.598_± 0.004 0.780±0.0380.780_± 0.038 – – 0.8930.893 0.206±0.0360.206_± 0.036 UCExplainer (GCN) 0.202±0.0230.202_± 0.023 0.184±0.0290.184_± 0.029 1.000±0.0001.000_± 0.000 0.818±0.0270.818_± 0.027 – 0.9110.911 0.092±0.0220.092_± 0.022 UCExplainer (GINE) 0.558±0.0290.558_± 0.029 0.508±0.0360.508_± 0.036 1.000±0.0001.000_± 0.000 0.459±0.0200.459_± 0.020 0.369±0.0140.369_± 0.014 0.9100.910 0.000±0.0000.000_± 0.000 D4Explainer 0.290±0.0540.290_± 0.054 0.290±0.0540.290_± 0.054 0.597±0.0800.597_± 0.080 – – 1.0001.000 0.290±0.0540.290_± 0.054 GDCE-I (Ours, GCN) 0.888±0.0370.888_± 0.037 0.858±0.0460.858_± 0.046 0.915±0.0110.915_± 0.011 0.910±0.0040.910_± 0.004 0.998±0.0010.998_± 0.001 0.9660.966 0.360±0.0440.360_± 0.044 GDCE-I (Ours, GINE) 0.948±0.0200.948_± 0.020 0.938±0.0260.938_± 0.026 0.947±0.0070.947_± 0.007 0.882±0.0050.882_± 0.005 0.989±0.0030.989_± 0.003 0.9890.989 0.286±0.0390.286_± 0.039 PROTEINS CF2CF^2 0.7590.759 0.7300.730 0.5230.523 – – 0.9620.962 – C2Explainer 0.4310.431 0.3740.374 0.3650.365 – – 0.8680.868 – XPlore 0.8050.805 0.6490.649 0.8750.875 – – 0.8070.807 – UCExplainer (GCN) 0.2410.241 0.2240.224 1.0001.000 0.7730.773 – 0.9290.929 – D4Explainer 0.1320.132 0.1210.121 0.8320.832 – – 0.9170.917 – GDCE-I (Ours, GCN) 0.8510.851 0.7470.747 0.7620.762 0.8720.872 – 0.8780.878 – TWITTER CF2CF^2 0.194±0.0190.194_± 0.019 0.130±0.0270.130_± 0.027 0.213±0.0370.213_± 0.037 – – 0.6700.670 – C2Explainer 0.054±0.0210.054_± 0.021 0.036±0.0180.036_± 0.018 0.313±0.1330.313_± 0.133 – – 0.6670.667 – XPlore 0.142±0.0290.142_± 0.029 0.082±0.0160.082_± 0.016 0.621±0.0490.621_± 0.049 – – 0.5820.582 – UCExplainer (GCN) 0.532±0.0690.532_± 0.069 0.474±0.0610.474_± 0.061 1.000±0.0001.000_± 0.000 0.522±0.0660.522_± 0.066 – 0.8910.891 – D4Explainer 0.000±0.0000.000_± 0.000 0.000±0.0000.000_± 0.000 – – – – – GDCE-I (Ours, GCN) 0.996±0.0050.996_± 0.005 0.954±0.0150.954_± 0.015 0.957±0.0090.957_± 0.009 0.496±0.0320.496_± 0.032 – 0.9580.958 – Table 2: All metrics are oriented so that higher is better (↑ ); subscripts give the standard deviation over five runs of 100100 graphs. The three sparsity columns are 11 minus the corresponding modification rate, so 11 means that part of the graph was left untouched. SMILES is defined on the molecular datasets only. †clamped at 00; the raw modification rate is 1.3901.390. PROTEINS is a single run over the complete test split and admits no spread. GDCE-I also allocates its edit budget to the property that defines each dataset. On Mutagenicity, it spends the budget on topology, preserving 0.8920.892 of the atom types but only 0.6570.657 of the edges, consistent with rearranging the substructures that carry mutagenicity. On Benzene, where the label is the presence of a benzene ring, it instead exploits an edit that no edge-only baseline can express and substitutes a ring carbon by another atom type. The ordering reverses, with 0.9470.947 of the edges but only 0.8820.882 of the atom types left intact. GDCE-I does not lead the NA column on the molecular datasets but stays competitive. One should note that NA is conditioned on the flips a method produces. D4Explainer’s 1.0001.000 on Benzene is computed over the 29.0%29.0\% of graphs it flips at all, whereas GDCE-I’s 0.9660.966 is computed over 88.8%88.8\%. Read together with NAFR, which shares its denominator with FR, the two columns separate how often a method flips from how often its flips survive a change of judge. The target classifier is not a neutral choice Because the shared protocol is what makes Table 2 comparable, it is worth stating how much it changes. Re-running each baseline against its own paper oracle on the same splits, seeds, and metric definitions, exchanging nothing but the classifier, moves the Flip Rate by up to 0.300.30 on Mutagenicity: C2Explainer falls from 0.9840.984 to 0.6880.688, D4Explainer from 0.2960.296 to 0.1540.154 and CF2CF^2 from 0.8200.820 to 0.6220.622. The effect is not uniform in sign, as UCExplainer gains under the shared judge. The largest losses fall on precisely those methods that report a near-perfect Flip Rate against their own oracle, whereas GDCE-I moves by at most 0.060.06 in either direction (0.908→0.9700.908→ 0.970 on Mutagenicity). Sparsity behaves differently. For most methods, structural cost is close to classifier-invariant: CF2CF^2 (0.600→0.6040.600→ 0.604), D4Explainer (0.429→0.3840.429→ 0.384) and GDCE-I (0.344→0.3430.344→ 0.343) report essentially the same Edge Sparsity on Mutagenicity under either classifier. C2Explainer is the exception, rising from 0.0840.084 to 1.3901.390, reproduced as 15.3×15.3× in a paired control that exchanges nothing but the classifier. 5.3 Ablation Studies The role of the inversion We compare three different sampling schemes under the same training run, same checkpoint, same shared GCN classifier, guidance scale s=3s=3, same dynamic budget search, and 5×1005× 100 Mutagenicity samples. Firstly no inversion, which perturbs the source to GτG_τ along the forward trajectory and then samples the reverse process freshly. Secondly naive inversion, which records and re-injects a fresh Gumbel sample rather than the posterior-consistent one, and posterior inversion (GDCE-I), which re-injects the exact edit-friendly noise 4.1. Table 3 reports the outcome under the same metrics. desiderata sufficiency understandability fidelity Variant FR (↑ ) NAFR (↑ ) EdgeSp. (↑ ) NodeSp. (↑ ) EdgeTypeSp. (↑ ) NA (↑ ) SMILES (↑ ) τ~ τ No inversion 1.000±0.0001.000_± 0.000 0.876±0.0270.876_± 0.027 0.675±0.0280.675_± 0.028 0.923±0.0080.923_± 0.008 0.997±0.0010.997_± 0.001 0.876±0.0270.876_± 0.027 0.804±0.0250.804_± 0.025 1111 Naive inversion 0.996±0.0050.996_± 0.005 0.858±0.0190.858_± 0.019 0.592±0.0330.592_± 0.033 0.907±0.0070.907_± 0.007 0.995±0.0020.995_± 0.002 0.861±0.0180.861_± 0.018 0.832±0.0360.832_± 0.036 3636 Posterior (GDCE-I) 0.970±0.0160.970_± 0.016 0.886±0.0290.886_± 0.029 0.657±0.0110.657_± 0.011 0.892±0.0090.892_± 0.009 0.993±0.0000.993_± 0.000 0.913±0.0290.913_± 0.029 0.816±0.0210.816_± 0.021 5151 Table 3: Inversion ablation on Mutagenicity against the shared GCN classifier (5×1005× 100, s=3s=3), reported under the metrics of Table 2; τ~ τ is the median flip budget. All three variants come from the same training run and checkpoint and differ only in the noise treatment, and the posterior row is the GDCE-I (GCN) row of Table 2. The column-wise best is in bold. All three are strong counterfactual generators, and no desideratum separates them. They flip almost every instance (1.0001.000, 0.9960.996, 0.9700.970), and once the flip has to survive the control judge, they stay within one standard deviation of one another (0.8760.876, 0.8580.858, 0.8860.886). The joint criterion of being both a flip and a molecule falls within 0.030.03 (0.8040.804, 0.8320.832, 0.8160.816). On the understandability axes, the spread reaches at most two standard deviations: no inversion preserves the most topology (0.6750.675 against 0.6570.657 and the most atom types (0.9230.923 against 0.8920.892 for posterior inversion. What the columns separate is how the flip is obtained, and the flip budget makes it visible. Without noise recording, the reverse process is freshly resampled, diverges almost immediately from the source, and finds a flip at a median budget of τ~=11 τ=11. Posterior inversion reconstructs the reference exactly at small τ and therefore cannot flip until the budget grows to τ~=51 τ=51. Naive inversion, which re-injects noise that the reverse posterior was never conditioned on, sits between the two at 3636. The choice is thus a trade-off rather than a ranking. Posterior inversion is the only scheme that reconstructs, whereas no inversion reaches a flip at roughly a fifth of the budget. Budget, molecule size, and edit size The budget search assumes that a smaller τ yields a smaller edit. Testing that assumption, we observe (Figure 3) that this holds for all variants and also that the initial graph size sets the tone of how much budget is needed to find the counterfactual. Posterior inversion lies below both alternatives at every budget. This is what exact reconstruction buys at the same budget on the same molecule. The guided replay departs from the source itself rather than from somewhere near it. Figure 3: Flip budget τ on the horizontal axis of both panels (Mutagenicity, shared GCN classifier, s=3s=3, successful counterfactuals; binned means ±1± 1 SEM, log scale). (a) Moleculesize against τ. (b) Absolute edit size against τ. Guidance strength. The guidance scale s governs how forcefully generation is steered toward the target class, and sweeping it over s∈1,3,5s∈\1,3,5\ separates two effects that move in opposite directions. Raising s improves every axis that measures success and economy at once. The Flip Rate (0.740→0.970→0.9980.740→ 0.970→ 0.998), all three understandability axes (0.606→0.657→0.7260.606→ 0.657→ 0.726 on edges, 0.882→0.892→0.9050.882→ 0.892→ 0.905 on atom types, 0.991→0.993→0.9950.991→ 0.993→ 0.995 on bond types) and the flip budget (τ~ τ 86→51→2586→ 51→ 25). Stronger guidance reaches the target class earlier along the replay and, therefore, departs less far from the source. Fidelity moves the other way. The rate at which a flip is transmitted to the control judge decreases with s (0.944→0.913→0.8790.944→ 0.913→ 0.879), and so does the share of counterfactuals that RDKit can sanitize, conditioned on a flip (0.852→0.841→0.7760.852→ 0.841→ 0.776). Both point at the same mechanism: forcing the classifier signal harder buys a high flip rate and sparsity, but pushes the sample off the data manifold. A counterfactual is only useful if it fulfills all the requirements at once. The two columns that combine these requirements the best are in the middle. The joint flip-and-molecule rate at s=3s=3 (0.8160.816 against 0.6300.630 and 0.7740.774) and the non-adversarial flip rate likewise (0.8860.886 against 0.6990.699 and 0.8790.879). We adopt s=3s=3 for the main results. desiderata sufficiency understandability fidelity s FR (↑ ) NAFR (↑ ) EdgeSp. (↑ ) NodeSp. (↑ ) EdgeTypeSp. (↑ ) NA (↑ ) SMILES (↑ ) τ~ τ 11 0.740±0.0370.740_± 0.037 0.699±0.0290.699_± 0.029 0.606±0.0270.606_± 0.027 0.882±0.0090.882_± 0.009 0.991±0.0030.991_± 0.003 0.944±0.0540.944_± 0.054 0.630±0.0420.630_± 0.042 8686 3 0.970±0.0160.970_± 0.016 0.886±0.0290.886_± 0.029 0.657±0.0110.657_± 0.011 0.892±0.0090.892_± 0.009 0.993±0.0000.993_± 0.000 0.913±0.0290.913_± 0.029 0.816±0.0210.816_± 0.021 5151 55 0.998±0.0040.998_± 0.004 0.894±0.0230.894_± 0.023 0.726±0.0280.726_± 0.028 0.905±0.0050.905_± 0.005 0.995±0.0030.995_± 0.003 0.896±0.0200.896_± 0.020 0.774±0.0250.774_± 0.025 2424 Table 4: Guidance-scale sweep for GDCE-I (posterior inversion) on Mutagenicity against the shared GCN classifier (5×1005× 100), reported under the metrics of Table 2; τ~ τ is the median flip budget. Column-wise best in bold. 5.4 Qualitative Analysis on Mutagenicity To evaluate whether the generated counterfactuals provide meaningful insights, we conducted a qualitative analysis on the Mutagenicity dataset. This reference comprises aromatic and heteroaromatic chemical compounds classified according to their mutagenic effect on the Gram-negative bacterium Salmonella typimurium [26]. Toxicophore derivation studies have identified multiple functional subgroups that are highly discriminatory for the classification of mutagenicity [26]. Among these, the aromatic nitro group, particularly the benzene-NO2NO_2 motif, emerges as the most frequently occurring and highly predictive structural characteristic. Kazius et al. [26] report that 87%87\% of the molecules containing this substructure are mutagens, a finding mirrored by our shared GCN classifier, which predicts 94.6%94.6\% of the 669669 molecules that carry this motif as mutagenic across the combined train, validation, and test sets. The qualitative evaluation of counterfactual methods on this motif was first established by the authors of CF2 [58], who constructed a filtered subset called “Mutag0” [58]. Their analysis showed that purely deletion-based methods tend to simply remove a few critical edges to break the toxicophore, which fails to yield an explanation [58] by ending up in a fragmented counterfactual. However, despite identifying this flaw, CF2 itself suffers from similar limitations. As a mask-based attribution method, CF2 is designed primarily to identify and extract an existing factual subgraph rather than generate a counterfactual instance. Because its counterfactual reasoning strictly defines the counterfactual as the original graph minus the identified factual mask, CF2 is restricted to edge and node deletions. Consequently, while the method successfully highlights the relevant toxicophore, it will not necessarily generate a counterfactual, which is an instance of the data manifold. To evaluate whether GDCE-I is capable of solving these issues, we design a targeted experiment. We filter the test set to isolate molecules that contain both the benzene-NO2NO_2 motif and are explicitly classified as mutagenic by the GNN classifier. Then we apply our framework to generate counterfactual explanations for this subset. A faithful counterfactual explainer should naturally recognize the causal significance of this motif and specifically alter the aromatic nitro group to flip the prediction from mutagenic to non-mutagenic. Our empirical evaluation strongly validates this expectation. Of the 116116 molecules in this targeted subset, GDCE-I alters the prediction of the classifier for 115115 (99.1%99.1\%). A detailed structural analysis further reveals that in 93.0%93.0\% of the generated counterfactuals, the explainer explicitly modifies the benzene-NO2NO_2 motif. 72.2%72.2\% of the counterfactuals in this subset yield a valid SMILE. Figure 4 presents two representative examples. In the first, the method detoxifies the molecule by detaching the NO2NO_2 group from the benzene ring and relocating it to a non-aromatic structural position. In the second, it performs a direct substitution of functional groups, replacing the mutagenic NO2NO_2 group with a benign SO2SO_2 group. Both strategies neutralize the primary toxicophore while strictly preserving the topological backbone of the original molecule, underscoring the capability of GDCE-I to deliver understandable counterfactuals. Figure 4: Qualitative counterfactuals on Benzene (GDCE-I (GCN), s=3s=3).Highlighting: green marks the original motif, red the remainings, and yellow the edits. (Left) The aromatic nitro motif. (Top right): The original mutagenic compound carries an NO2NO_2 group connected to an aromatic ring. The generated counterfactual detoxifies the molecule by relocating the nitro group from the aromatic to a non-aromatic structural position. (Bottom right): GDCE-I performs a direct functional group substitution, replacing the mutagenic NO2NO_2 group with a, non-mutagenic SO2SO_2 group. 5.5 Qualitative Analysis on Benzene We conduct another test on Benzene. A graph is exactly positive when it contains a benzene ring [48, 1]. Thus, a faithful explanation would destroy the benzene ring when the target class is negative and construct one when it is positive. GDCE-I flips 94.8%94.8\% of the sampled molecules (Table 2). Among the counterfactuals that produce a valid SMILES, 86.4%86.4\% satisfy the ground-truth motif condition, i.e., the benzene ring is actually removed or created. In the positive-to-negative direction, this holds for every counterfactual. Crucially, 74.9%74.9\% of all flips are obtained without inserting or deleting a single edge. GDCE-I breaks or completes the ring by substituting a ring atom, an edit that leaves the surrounding topology untouched. Figure 5 shows one representative example per direction, both single-atom substitutions with Edge Sparsity and Edge Type Sparsity of exactly 11. In the Top right, carbon is replaced by nitrogen. Notably, the thiophene at the other end of the molecule, which is aromatic but not a benzene ring, is left untouched, so the edit targets the labeled motif rather than aromaticity in general. The second example runs the other way: a pyridine nitrogen is replaced by carbon, completing a benzene ring and flipping the prediction to the positive class. Together with the Mutagenicity analysis, this shows that GDCE-I localizes the class-defining substructure, and edits it data-manifold aware. Figure 5: Qualitative counterfactuals on Benzene (GDCE-I (GINE), s=3s=3). Highlighting: green marks the original motif, red the remainings, and yellow the edits. (Left) The benzene-ring motif. (Top right): A ring carbon of the original is replaced by nitrogen, flipping the prediction to no benzene ring. (Bottom right): The reverse direction, where a nitrogen is replaced by carbon so that a benzene ring is completed. 6 Limitations Our results should not be read as evidence that generative counterfactual explainers dominate heuristic ones. What a distribution-aware generator buys is that its edits are drawn from a model which learned the data distribution. Molecular graphs constrain it sharply, but on benchmarks whose distribution is not that unconstrained, such as synthetic graphs built from planted motifs, we expect modeling the data manifold buys nothing while its cost remains, and we would not expect GDCE-I to be the appropriate tool. Further, GDCE-I and other generative approaches require a conditional diffusion model trained per dataset, a cost the mask-based baselines do not incur at all. This rules the method out where an explanation is needed on a dataset for which no generative model exists, or it’s too hard to be trained, a regime in which mask-based explainers remain structurally advantaged regardless of the quality of their edits. The counterfactuals we generate are edits to a molecular graph. Atom types, bond types, and topology. Many of the questions that motivate counterfactual reasoning in chemistry, from binding to pharmacokinetics, are not decided at that level, but by the three-dimensional conformations a compound adopts. A topological edit that flips a classifier trained on graphs therefore states a hypothesis about the molecule, not about its behavior in a conformation space. 7 Conclusion We presented GDCE-I, a framework for graph counterfactual explanation built on discrete diffusion inversion. Its central component is a Gumbel-Max inversion that records the sampling noise of a reference trajectory in closed form, so that replaying the reverse process under the original condition reconstructs the input exactly, and replaying it under a changed condition alters only those positions where guidance is strong enough to move the argmax past the recorded margin. The budget parameter τ turns minimality into a search over how much of the trajectory is regenerated rather than a penalty term fixed at training time. This addresses the two problems we identified. Because every edit is a step of a discrete diffusion model of the data, the counterfactual is held on the data manifold rather than merely close to the input. Secondly, because that model is defined over node types, bond types, and topology within a single generative process, the full edit space can be leveraged to find an explanation. The results follow from both. GDCE-I attains the highest Flip Rate of all compared methods on every benchmark (0.9700.970 on Mutagenicity, 0.9480.948 on Benzene, 0.8510.851 on PROTEINS, 0.9960.996 on TWITTER) and the highest non-adversarial flip rate throughout (0.8860.886, 0.9380.938, 0.7470.747, 0.9540.954). On the two molecular benchmarks, where membership of the data manifold can actually be tested, it returns the largest share of counterfactuals that are at once non-adversarial and a valid molecule (0.7440.744 and 0.3600.360). Our second contribution is the evaluation itself. The metrics reported in this area are incomplete and inconsistent: the same names denote different amounts in papers, and different evaluation schemes are applied. We therefore derived desiderata for counterfactual explanation and defined suitable metrics for the graph domain. 8 Future Work One possible direction of future work might be to also introduce diversity in the counterfactual search as done for tabular data, e.g., in [35] or for visual classifiers in [7]. This might enable us to systematically find secondary Clever Hans features [29] and remove them, e.g., with CFKD [5, 6] by adapting it plug-and-play from vision and tabular counterfactuals to graph counterfactuals. Another direction to explore would be applying the Gumbel softmax trick for editing with discrete diffusion to other inherently discrete domains like natural language or protein sequences. Acknowledgments We thank Klaus-Robert Müller for general discussion and guidance. We also thank Stefan Gugler for help and guidance for the qualitative experiments on Mutagenicity and Benzen. This work was partly funded by the German Ministry for Education and Research (under refs 01IS14013A-E, 01GQ1115, 01GQ0850, 01IS18056A, 01IS18025A, 13GW0744D, and BIFOLD25B) and by DFG. Sidney Bender was partially funded by Bosch-Siemens Haushaltsgeräte. References [1] C. Agarwal, O. Queen, H. Lakkaraju, and M. Zitnik (2023) Evaluating explainability for graph neural networks. Scientific Data 10 (1), p. 144. External Links: ISSN 2052-4463, Link, Document Cited by: Table 5, Appendix B, item 2, §5.1, §5.5. [2] M. Augustin, V. Boreiko, F. Croce, and M. Hein (2022) Diffusion visual counterfactual explanations. NeurIPS 35, p. 364–377. Cited by: §2. [3] S. Bach, A. Binder, G. Montavon, F. Klauschen, K. Müller, and W. Samek (2015) On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation. PloS one 10 (7), p. e0130140. Cited by: §1. [4] D. Bechtoldt and S. Bender (2025) Graph difffusion counterfactual explanation. External Links: 2511.16287, Link Cited by: footnote 1. [5] S. Bender, C. J. Anders, P. Chormai, H. A. Marxfeld, J. Herrmann, and G. Montavon (2023) Towards fixing clever-hans predictors with counterfactual knowledge distillation. In Proceedings of the IEEE/CVF International Conference on Computer Vision, p. 2607–2615. Cited by: §8. [6] S. Bender, O. Delzer, J. Herrmann, H. A. Marxfeld, K. Müller, and G. Montavon (2026) Mitigating clever hans strategies in image classifiers through generating counterexamples. Information Fusion, p. 104406. Cited by: §8. [7] S. Bender, J. Herrmann, K. Müller, and G. Montavon (2026) Towards desiderata-driven design of visual counterfactual explainers. In Pattern Recognition, Vol. 174, p. 112811. External Links: ISSN 0031-3203, Document Cited by: §2, §2, §3.1, §3.1, §3.2, §3.3, §3.3, Table 1, §3, §8. [8] S. Bender and M. Morik (2026) Visual disentangled diffusion autoencoders: scalable counterfactual generation for foundation models. ICLR 2026 Trustworthy AI workshop. Cited by: §2. [9] K. M. Borgwardt, C. S. Ong, S. Schönauer, S. V. N. Vishwanathan, A. J. Smola, and H. Kriegel (2005) Protein function prediction via graph kernels. Bioinformatics 21 (1), p. 47–56. External Links: ISSN 1367-4803, Link, Document Cited by: Table 5, Appendix B, item 2, §5.1. [10] J. Chen, S. Wu, A. Gupta, and Z. Ying (2023) D4Explainer: in-distribution explanations of graph neural network via discrete denoising diffusion. In Thirty-seventh Conference on Neural Information Processing Systems, External Links: Link Cited by: item 2, §1, §2, §3.1, §5.1, Table 2. [11] E. Dai, T. Zhao, H. Zhu, J. Xu, Z. Guo, H. Liu, J. Tang, and S. Wang (2024) A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability. Machine Intelligence Research 21 (6), p. 1011–1061. External Links: ISSN 2731-5398, Link, Document Cited by: §1. [12] Z. Dehghanighobadi, A. Fischer, and M. B. Zafar (2025) Can llms explain themselves counterfactually?. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, p. 7798–7826. Cited by: §2. [13] P. Dhariwal and A. Nichol (2021) Diffusion models beat gans on image synthesis. Advances in neural information processing systems 34, p. 8780–8794. Cited by: §4. [14] P. D. Dobson and A. J. Doig (2003) Distinguishing enzyme structures from non-enzymes without alignments. Journal of Molecular Biology 330 (4), p. 771–783. External Links: ISSN 0022-2836, Document, Link Cited by: item 2, §5.1. [15] A. Dombrowski, J. E. Gerken, K. Müller, and P. Kessel (2023) Diffeomorphic counterfactuals with generative models. IEEE Transactions on Pattern Analysis and Machine Intelligence 46 (5), p. 3257–3274. Cited by: §1, §2. [16] F. Giorgi, F. Silvestri, and G. Tolomei (2026) Unified counterfactual explainer for graph neural networks. npj Artificial Intelligence. External Links: ISSN 3005-1460, Link, Document Cited by: item 2, §2, §3.1, §5.1, Table 2. [17] A. A. Hansen, P. Pegios, A. Calissano, and A. Feragen (2024) Graph counterfactual explainable AI via latent space traversal. In Northern Lights Deep Learning Conference 2025, External Links: Link Cited by: §1, §1, §2. [18] Y. He, Z. Zheng, P. Soga, Y. Zhu, Y. Dong, and J. Li (2024) Explaining graph neural networks with large language models: a counterfactual perspective on molecule graphs. In Findings of the Association for Computational Linguistics: EMNLP 2024, Y. Al-Onaizan, M. Bansal, and Y. Chen (Eds.), Miami, Florida, USA, p. 7079–7096. External Links: Link, Document Cited by: §2. [19] J. Ho, A. Jain, and P. Abbeel (2020) Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (Eds.), Vol. 33, p. 6840–6851. External Links: Link Cited by: §4. [20] J. Ho and T. Salimans (2022) Classifier-free diffusion guidance. External Links: 2207.12598, Link Cited by: §1, §4. [21] R. Huben, H. Cunningham, L. Smith, A. Ewart, and L. Sharkey (2024) Sparse autoencoders find highly interpretable features in language models. In International Conference on Learning Representations, Vol. 2024, p. 7827–7845. Cited by: §3.2. [22] I. Huberman-Spiegelglas, V. Kulikov, and T. Michaeli (2024) An edit friendly ddpm noise space: inversion and manipulations. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), p. 12469–12478. Cited by: §4.1. [23] G. Jeanneret, L. Simon, and F. Jurie (2022) Diffusion models for counterfactual explanations. In Proceedings of the Asian conference on computer vision, p. 858–876. Cited by: §2. [24] G. Jeanneret, L. Simon, and F. Jurie (2023) Adversarial counterfactual visual explanations. In CVPR, p. 16425–16435. Cited by: §2. [25] G. Jeanneret, L. Simon, and f. Jurie (2024) Text-to-image models for counterfactual explanations: a black-box approach. In WACV, p. 4757–4767. Cited by: §2. [26] J. Kazius, R. McGuire, and R. Bursi (2005) Derivation and Validation of Toxicophores for Mutagenicity Prediction. Journal of Medicinal Chemistry 48 (1), p. 312–320. External Links: ISSN 0022-2623, Link, Document Cited by: Table 5, Appendix B, item 2, §5.1, §5.4. [27] M. Kosan, Z. Huang, S. Medya, S. Ranu, and A. Singh (2025) GCFExplainer: global counterfactual explainer for graph neural networks. ACM Trans. Intell. Syst. Technol. 16 (5). External Links: ISSN 2157-6904, Link, Document Cited by: §2. [28] W. Kłos, S. Bender, and L. Kades (2026) Protein counterfactuals via diffusion-guided latent optimization. ICLR 2026 Gen2^2 workshop. Cited by: §2. [29] S. Lapuschkin, S. Wäldchen, A. Binder, G. Montavon, W. Samek, and K. Müller (2019) Unmasking clever hans predictors and assessing what machines really learn. Nature communications 10 (1), p. 1096. Cited by: §8. [30] A. Lucic, M. A. Ter Hoeve, G. Tolomei, M. De Rijke, and F. Silvestri (2022) Cf-gnnexplainer: counterfactual explanations for graph neural networks. In International Conference on Artificial Intelligence and Statistics, p. 4499–4511. Cited by: §1, §2, §3.1. [31] J. Ma, I. Takigawa, and A. Yamamoto (2025) C2Explainer: customizable mask-based counterfactual explanation for graph neural networks. In Proceedings of the 2025 ACM Conference on Fairness, Accountability, and Transparency, FAccT ’25, New York, NY, USA, p. 137–149. External Links: ISBN 9798400714825, Link, Document Cited by: item 2, §1, §2, §3.1, §5.1, Table 2. [32] J. Ma, R. Guo, S. Mishra, A. Zhang, and J. Li (2022) Clear: generative counterfactual explanations on graphs. Advances in neural information processing systems 35, p. 25895–25907. Cited by: §1, §2, §3.1. [33] C. J. Maddison, D. Tarlow, and T. Minka (2014) A* sampling. In Advances in Neural Information Processing Systems, Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Weinberger (Eds.), Vol. 27, p. . External Links: Link Cited by: §1, §4.1, §4.1, 1. [34] C. Morris, N. M. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. Neumann (2020) TUDataset: a collection of benchmark datasets for learning with graphs. In ICML Workshop on Graph Representation Learning and Beyond (GRL+), Cited by: Table 5, Table 5, Table 5, Appendix B, §5.1. [35] R. K. Mothilal, A. Sharma, and C. Tan (2020) Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the 2020 conference on fairness, accountability, and transparency, p. 607–617. Cited by: §2, §2, §8. [36] M. Nauta, J. Trienes, S. Pathak, E. Nguyen, M. Peters, Y. Schmitt, J. Schlötterer, M. van Keulen, and C. Seifert (2023) From anecdotal evidence to quantitative evaluation methods: A systematic review on evaluating explainable AI. ACM Comput. Surv. 55 (13s), p. 295:1–295:42. Cited by: §2. [37] M. Ninniri, M. Podda, and D. Bacciu (2024) Classifier-free graph diffusion for molecular property targeting. In Machine Learning and Knowledge Discovery in Databases. Research Track, A. Bifet, J. Davis, T. Krilavičius, M. Kull, E. Ntoutsi, and I. Žliobaitė (Eds.), Cham, p. 318–335. External Links: ISBN 978-3-031-70359-1 Cited by: §1, §4. [38] D. Numeroso and D. Bacciu (2021) Meg: generating molecular counterfactual explanations for deep graph networks. In 2021 International Joint Conference on Neural Networks (IJCNN), p. 1–8. Cited by: §2. [39] S. Pan, J. Wu, X. Zhu, and C. Zhang (2015) Graph ensemble boosting for imbalanced noisy graph stream classification. IEEE Transactions on Cybernetics 45 (5), p. 954–968. External Links: Document Cited by: Table 5, Appendix B, item 2, §5.1. [40] S. Pan, J. Wu, and X. Zhu (2015) CogBoost: boosting for fast cost-sensitive graph classification. IEEE Transactions on Knowledge and Data Engineering 27 (11), p. 2933–2946. External Links: Document Cited by: item 2, §5.1. [41] P. E. Pope, S. Kolouri, M. Rostami, C. E. Martin, and H. Hoffmann (2019) Explainability methods for graph convolutional neural networks. In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), Vol. , p. 10764–10773. External Links: Document Cited by: §1. [42] M. A. Prado-Romero, B. Prenkaj, G. Stilo, and F. Giannotti (2024) A survey on graph counterfactual explanations: definitions, methods, evaluation, and research challenges. ACM Comput. Surv. 56 (7). External Links: ISSN 0360-0300, Link, Document Cited by: §1, §1, §1. [43] M. A. Prado-Romero, B. Prenkaj, and G. Stilo (2024) Robust stochastic graph generator for counterfactual explanations. In Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence, AAAI’24/IAAI’24/EAAI’24. External Links: ISBN 978-1-57735-887-9, Link, Document Cited by: §2. [44] RDKit, online RDKit: open-source cheminformatics. Note: https://w.rdkit.org Cited by: §3.1. [45] P. Rodriguez, M. Caccia, A. Lacoste, L. Zamparo, I. Laradji, L. Charlin, and D. Vazquez (2021) Beyond trivial counterfactual explanations with diverse valuable explanations. In ICCV, p. 1056–1065. Cited by: §2. [46] C. Russell (2019) Efficient search for diverse coherent explanations. In Proceedings of the conference on fairness, accountability, and transparency, p. 20–28. Cited by: §2. [47] W. Samek, A. Binder, G. Montavon, S. Lapuschkin, and K. Müller (2017) Evaluating the visualization of what a deep neural network has learned. IEEE Trans. Neural Networks Learn. Syst. 28 (11), p. 2660–2673. Cited by: §2. [48] B. Sanchez-Lengeling, J. Wei, B. Lee, E. Reif, P. Wang, W. Qian, K. McCloskey, L. Colwell, and A. Wiltschko (2020) Evaluating attribution for graph neural networks. In Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (Eds.), Vol. 33, p. 5898–5910. External Links: Link Cited by: Table 5, Appendix B, item 2, §5.1, §5.5. [49] M. D. Sanctis, R. D. Sanctis, S. Faralli, P. Velardi, and B. Prenkaj (2026) Beyond edge deletion: a comprehensive approach to counterfactual explanation in graph neural networks. External Links: 2603.04209, Link Cited by: item 2, §2, §5.1, Table 2. [50] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini (2009) The graph neural network model. IEEE Transactions on Neural Networks 20 (1), p. 61–80. External Links: Document Cited by: §1. [51] T. Schnake, O. Eberle, J. Lederer, S. Nakajima, K. T. Schüt, K. Müller, and G. Montavon (2021) Higher-order explanations of graph neural networks via relevant walks. IEEE transactions on pattern analysis and machine intelligence 44 (11), p. 7581–7596. Cited by: §1. [52] K. T. Schüt, H. E. Sauceda, P.-J. Kindermans, A. Tkatchenko, and K.-R. Müller (2018) SchNet – a deep learning architecture for molecules and materials. The Journal of Chemical Physics 148 (24), p. 241722. External Links: ISSN 0021-9606, Document, Link, https://pubs.aip.org/aip/jcp/article-pdf/doi/10.1063/1.5019779/16655678/241722_1_online.pdf Cited by: §1. [53] L. S. Shapley (1953) A value for n-person games. In Contributions to the Theory of Games I, H. W. Kuhn and A. W. Tucker (Eds.), p. 307–317. Cited by: §2. [54] J. M. Stokes, K. Yang, K. Swanson, W. Jin, A. Cubillos-Ruiz, N. M. Donghia, C. R. MacNair, S. French, L. A. Carfrae, Z. Bloom-Ackermann, V. M. Tran, A. Chiappino-Pepe, A. H. Badran, I. W. Andrews, E. J. Chory, G. M. Church, E. D. Brown, T. S. Jaakkola, R. Barzilay, and J. J. Collins (2020) A deep learning approach to antibiotic discovery. Cell 180 (4), p. 688–702.e13. External Links: Document Cited by: §1. [55] D. Stutz, M. Hein, and B. Schiele (2019) Disentangling adversarial robustness and generalization. In CVPR, p. 6976–6987. Cited by: §3.1. [56] W. R. Swartout and J. D. Moore (1993) Explanation in second generation expert systems. In Second Generation Expert Systems, p. 543–585. Cited by: §2, §3.1, §3. [57] C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna (2016) Rethinking the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, p. 2818–2826. Cited by: §3.1. [58] J. Tan, S. Geng, Z. Fu, Y. Ge, S. Xu, Y. Li, and Y. Zhang (2022) Learning and evaluating graph neural network explanations based on counterfactual and factual reasoning. In Proceedings of the ACM Web Conference 2022, W ’22, New York, NY, USA, p. 1018–1027. External Links: ISBN 9781450390965, Link, Document Cited by: item 2, §2, §5.1, §5.4, Table 2. [59] S. Verma, B. Armgaan, S. Medya, and S. Ranu (2024) InduCE: inductive counterfactual explanations for graph neural networks. Transactions on Machine Learning Research. Note: External Links: ISSN 2835-8856, Link Cited by: §2. [60] C. Vignac, I. Krawczuk, A. Siraudin, B. Wang, V. Cevher, and P. Frossard (2023) DiGress: discrete denoising diffusion for graph generation. In The Eleventh International Conference on Learning Representations, External Links: Link Cited by: §1, §1, §4, §4, §4.1. [61] S. Wachter, B. Mittelstadt, and C. Russell (2017) Counterfactual explanations without opening the black box: automated decisions and the gdpr. Harv. JL & Tech. 31, p. 841. Cited by: §1. [62] N. Weng, P. Pegios, E. Petersen, A. Feragen, and S. Bigdeli (2024) Fast diffusion-based counterfactuals for shortcut removal and generation. In ECCV, p. 338–357. Cited by: §2. [63] F. Wong, E. J. Zheng, J. A. Valeri, N. M. Donghia, M. N. Anahtar, S. Omori, A. Li, A. Cubillos-Ruiz, A. Krishnan, W. Jin, A. L. Manson, J. Friedrichs, R. Helbig, B. Hajian, D. K. Fiejtek, F. F. Wagner, H. H. Soutter, A. M. Earl, J. M. Stokes, L. D. Renner, and J. J. Collins (2024) Discovery of a structural class of antibiotics with explainable deep learning. Nature 626 (7997), p. 177–185. External Links: ISSN 1476-4687, Link, Document Cited by: §1. [64] Z. Wu, B. Ramsundar, E. N. Feinberg, J. Gomes, C. Geniesse, A. S. Pappu, K. Leswing, and V. Pande (2018) MoleculeNet: a benchmark for molecular machine learning. Chemical Science 9 (2), p. 513–530. External Links: ISSN 2041-6520, Document, Link, https://pubs.rsc.org/sc/article-pdf/9/2/513/5768099/c7sc02664a.pdf Cited by: §1. [65] N. Yang, K. Zeng, Q. Wu, X. Jia, and J. Yan (2022) Learning substructure invariance for out-of-distribution molecular representations. In Advances in Neural Information Processing Systems, S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (Eds.), Vol. 35, p. 12964–12978. External Links: Document, Link Cited by: §3.1. [66] H. Yuan, H. Yu, S. Gui, and S. Ji (2023) Explainability in graph neural networks: a taxonomic survey. IEEE Trans. Pattern Anal. Mach. Intell. 45 (5), p. 5782–5799. External Links: ISSN 0162-8828, Link, Document Cited by: §1. [67] A. Zeid and S. Bender (2026) SCE-lite-hq: smooth visual counterfactual explanations with generative foundation models. arXiv preprint arXiv:2603.17048. Cited by: §2. Appendix A Full Algorithm Input: Clean graph G=(X,E,y)G=(X,E,y), target y′y , GNN classifier f, budget schedule skipT_skip Output: GCE=(XCE,ECE,y′)G_CE=(X_CE,E_CE,y ) 1 // Phase 1: reference trajectory (states only) G^0←G G^0← G; 2 for t=1t=1 to T do 3 X^t∼X^t−1QXt,E^t∼E^t−1QEt X^t X^t-1Q^t_X, 9.24994pt E^t E^t-1Q^t_E ; // single-step forward, Eq. 6 end for 4 5 // Phase 2: posterior Gumbel recording (reverse, original condition y) ←∅G← ; 6 for s=T−1s=T-1 to 00 do 7 pθ(xis∣G^s+1,y)←∑xq⁡(xis∣x^is+1,xi0=x)fθ(xi0=x∣G^s+1,y)p_θ(x^s_i G^s+1,y)← _xq(x^s_i x^s+1_i,x^0_i=x)\,f_θ(x^0_i=x G^s+1,y); 8 pθ(eijs∣G^s+1,y)←∑eq⁡(eijs∣e^ijs+1,eij0=e)fθ(eij0=e∣G^s+1,y)p_θ(e^s_ij G^s+1,y)← _eq(e^s_ij e^s+1_ij,e^0_ij=e)\,f_θ(e^0_ij=e G^s+1,y); 9 gsX←PosteriorGumbel(log⁡pθ(Xs∣G^s+1,y),X^s)g_s^X← PosteriorGumbel ( p_θ(X^s G^s+1,y),\; X^s ) ; // Eqs. 15, 16 [33] gsE←PosteriorGumbel(log⁡pθ(Es∣G^s+1,y),E^s)g_s^E← PosteriorGumbel ( p_θ(E^s G^s+1,y),\; E^s ); 10 ←∪(gsX,gsE)G ∪\(g_s^X,g_s^E)\ end for 11 12 // Phase 3: dynamic budget search + guided replay (target condition y′y ) for τ∈skipτ _skip do 13 Gτ←G^τG^τ← G^τ; 14 for t=τt=τ to 11 do 15 pθ(xit−1∣Gt,y′)←∑xq⁡(xit−1∣xit,xi0=x)fθ(xi0=x∣Gt,y′)p_θ(x^t-1_i G^t,y )← _xq(x^t-1_i x^t_i,x^0_i=x)\,f_θ(x^0_i=x G^t,y ); 16 pθ(eijt−1∣Gt,y′)←∑eq⁡(eijt−1∣eijt,eij0=e)fθ(eij0=e∣Gt,y′)p_θ(e^t-1_ij G^t,y )← _eq(e^t-1_ij e^t_ij,e^0_ij=e)\,f_θ(e^0_ij=e G^t,y ); 17 Xt−1←one_hot(argmax(log⁡pθ(Xt−1∣Gt,y′)+gt−1X))X^t-1 \_hot (argmax( p_θ(X^t-1 G^t,y )+g_t-1^X) ); 18 Et−1←one_hot(argmax(log⁡pθ(Et−1∣Gt,y′)+gt−1E))E^t-1 \_hot (argmax( p_θ(E^t-1 G^t,y )+g_t-1^E) ); 19 Gt−1←(Xt−1,Et−1)G^t-1←(X^t-1,E^t-1); 20 end for 21 if f⁡(G0)==y′f(G^0)==y then 22 return GCE←G0G_CE← G^0 ; // minimal counterfactual end if 23 end for 24 return Failure ; // no valid counterfactual within budgets 25 Algorithm 1 Graph Diffusion Counterfactual Explanation via Inversion (GDCE-I) Appendix B Datasets and Classifier Architectures We evaluate on four graph-classification datasets, two molecular and two non-molecular. Mutagenicity [26] is a standard molecular benchmark from the TUDataset collection [34]. Benzene [48, 1] is a molecular attribution benchmark whose label indicates the presence of a benzene ring. PROTEINS [9] and TWITTER (TWITTER-Real-Graph-Partial) [39] are likewise taken from the TUDataset collection. All four are preprocessed identically for GDCE-I and every baseline, so no method gains an advantage from a different data representation. Graphs larger than 5050 nodes are removed. We additionally apply the Huang frequency filter (node types occurring ≤50≤ 50 times globally are dropped, together with the graphs containing them). On Benzene, this removes 3636 graphs containing phosphorus. Mutagenicity and Benzene retain bond types as a 55-class edge encoding (00 = no bond, 11–44 = single/double/triple/aromatic), whereas PROTEINS and TWITTER carry no edge types and use a binary adjacency. Table 5 summarizes the resulting statistics. The two non-molecular datasets follow the same recipe. PROTEINS needs no vocabulary filter. Its nodes carry three secondary-structure labels (helix, sheet, turn), all of them frequent, and the 5050-node cap leaves 871871 of the 11131113 graphs. TWITTER does need one. Its raw vocabulary of 13231323 words would make the (b,n,dx,dx)(b,n,d_x,d_x) attention tensor of the denoising network exceed device memory at the batch size we use, so we apply the same frequency rule as for the molecular sets with a threshold of 500500 occurrences. This leaves 238238 word types and 6503165031 graphs, retains 78.9%78.9\% of all node instances and leaves the class balance essentially untouched. Nodes are words, edges word co-occurrences, and the binary label is the sentiment of the tweet, with class 00 positive and class 11 negative. Dataset Source Graphs (tr/val/test) Node types Edge classes Max nodes Balance (0/1) Mutagenicity TUDataset [34, 26] 2377/792/7922377/792/792 (39613961) 1313 55 5050 57.6/42.457.6/42.4 Benzene [48, 1] 7178/2393/23937178/2393/2393 (1196411964) 88 55 2525 49.9/50.149.9/50.1 PROTEINS TUDataset [34, 9] 523/174/174523/174/174 (871871) 33 22 5050 52.9/47.152.9/47.1 TWITTER TUDataset [34, 39] 39019/13006/1300639019/13006/13006 (6503165031) 238238 22 5050 52.2/47.852.2/47.8 Table 5: Dataset statistics after preprocessing. SMILES validity ceiling on Benzene Because Benzene molecules are capped at 2525 nodes in the source data, some aromatic rings are truncated at the boundary. RDKit cannot sanitize a partial aromatic system, so even a perfectly reconstructed graph may fail to yield a valid SMILES string. Only 89.05%89.05\% pass strict sanitization. This is an upper bound on the SMILES column of Table 2 for Benzene. The reported values should be read against 0.89050.8905 rather than 1.01.0. For comparison, the ceiling on Mutagenicity is 0.9760.976. The shared classifiers Every method in Table 2 is optimized against, and evaluated by, the same classifier per dataset. We train two per dataset on the shared training split: a binary-adjacency GCN (LEConv, 3×1283× 128 hidden, BatchNorm, dropout 0.30.3, mean pooling), which every method can consume and against which all of them are measured, and an edge-feature-aware GINE (GINEConv with a 55-class edge encoder, otherwise identical), reserved for the two methods that predict bond types (GDCE-I and UCExplainer). PROTEINS and TWITTER carry no edge types and therefore have a GCN only. Both are plain PyTorch modules with no framework dependency, so the identical weights are loaded inside each baseline’s own container. We verified that all five repositories reproduce the same predictions on the same graphs before running any evaluation. Test accuracies: Mutagenicity 0.8060.806 (GCN) / 0.8130.813 (GINE), Benzene 0.9190.919 (GCN) / 1.0001.000 (GINE), PROTEINS 0.6320.632 (GCN), TWITTER 0.6480.648 (GCN). Because every method is trained and scored against these classifiers, class labels are taken from the classifier rather than from the dataset annotation, so that “flipping the label” and “flipping the classifier” coincide by construction.

Instant research discovery