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

The paper introduces GDCE-I (Graph Diffusion Counterfactual Explanation via Inversion), a novel framework for generating counterfactual explanations for Graph Neural Networks (GNNs). The authors identify two fundamental problems with existing graph counterfactual explainers: Either edits are not held on the data manifold, or the search does not span the full edit space. GDCE-I addresses both issues by combining discrete denoising diffusion models with classifier-free guidance and a novel discrete inversion scheme.

Graph Neural Networks achieve strong predictive performance on graph-structured data but provide no intrinsic explanation of their predictions, limiting adoption in high-stakes settings. Counterfactual explanations address this by revealing the minimal structural modifications that would change a model's prediction. However, on graphs, 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.

The paper notes that "real-world graph representations, such as molecules or proteins, reside in a highly sparse topological space. Consequently, even minor topological perturbations can easily violate strict domain-specific rules, such as chemical valency, resulting in structurally invalid and semantically meaningless instances."

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 rigorous evaluation on Mutagenicity, Benzene, PROTEINS, and TWITTER datasets against baselines (CF2, C2Explainer, XPlore, UCExplainer, D4Explainer), we show that GDCE-I is the only method that jointly produces faithful and understandable counterfactuals.

The method builds on DiGress, defining Markov transitions over categorical node and edge types. The forward process is defined as: q(GtGt−1) = (X t−1 QtX, E t−1 QtE), with cumulative transition matrices allowing direct sampling at any timestep.

The approach uses Classifier-Free Guidance (CFG) rather than classifier-based guidance because assigning meaningful continuous properties to such invalid, highly corrupted states is fundamentally ill-posed and yields unreliable guidance gradients. The conditioning variable y is randomly replaced with a null token during training, and at inference, the model extrapolates toward the conditional objective.

The core innovation is an edit-friendly inversion scheme for discrete diffusion that records sampling stochasticity. The authors exploit the Gumbel-Max trick: arg max k log pk + gk ∼ Categorical(p). This decomposes a categorical draw into a deterministic component (log-probabilities) and a stochastic component (noise g).

The inversion procedure works in three phases:

1. Reference trajectory: Given an input graph G, a single reference trajectory Ĝ0, Ĝ1,..., ĜT is drawn by iterating the forward process.

2. Posterior noise recording: Traversing the trajectory in reverse, the method records the Gumbel noise that forces the guided reverse posterior to reproduce the reference state using the truncated-Gumbel (A*-sampling) construction. This guarantees exact reconstruction.

3. Guided generation: Replaying the reverse process with the same recorded noise but a new target condition y′, the method generates counterfactuals where a position changes only where the guidance-induced shift in log-probabilities is large enough to move the argmax past the recorded margin.

The framework searches over increasing budgets τ ∈ 1,..., T, starting from reference state Ĝτ and denoising down to G0. It returns the counterfactual at the smallest budget for which f(G0) = y′, which identifies the minimal structural deviation required to alter the prediction.

The paper addresses incomplete and inconsistent evaluation of graph counterfactuals by deriving a framework of explanation desiderata based on Swartout and Moore's (1993) holistic explanation desiderata. Three desiderata are instantiated:

Operationalized via Non-Adversarial Rate (NA): "We validate the generated graphs against a retrained surrogate model fsur (distilled independently from f). This measures the transferability of the counterfactual flip, confirming it relies on robust structural features rather than weight-specific noise."

Operationalized via three sparsity metrics:

• Edge Sparsity: Topological minimality measured as the fraction of added or removed edges relative to the original graph's edge set

• Node Sparsity: The fraction of node-type substitutions across all nodes

• Edge Type Sparsity: Semantic changes on structurally preserved edges, measuring bond-type reassignments on retained edges

Operationalized via Non-Adversarial Flip Rate (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.

GDCE-I attains the highest Flip Rate on all four datasets and likewise leads the SMILES column on both datasets on which it is defined. Key results include:

• Mutagenicity: FR 0.970±0.016, NAFR 0.886±0.029 (GCN); FR 0.770±0.049, NAFR 0.628±0.068 (GINE)

• Benzene: FR 0.888±0.037, NAFR 0.858±0.046 (GCN); FR 0.948±0.020, NAFR 0.938±0.026 (GINE)

• PROTEINS: FR 0.851, NAFR 0.747

• TWITTER: FR 0.996±0.005, NAFR 0.954±0.015

The paper notes that "GDCE-I also allocates its edit budget to the property that defines each dataset. On Mutagenicity, it spends the budget on topology... 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."

Three sampling schemes were compared: no inversion, naive inversion, and posterior inversion (GDCE-I). The results show posterior inversion is the only scheme that reconstructs, whereas no inversion reaches a flip at roughly a fifth of the budget. The median flip budget τ̃ was 11 (no inversion), 36 (naive), and 51 (posterior).

A guidance-scale sweep (s ∈ 1, 3, 5) showed that Raising s improves every axis that measures success and economy at once but Fidelity moves the other way—stronger guidance pushes samples off the data manifold. The authors adopt s = 3 for main results.

Mutagenicity: Of 116 molecules containing the benzene-NO2 motif, GDCE-I alters the prediction of the classifier for 115 (99.1%). In 93.0% of counterfactuals, the explainer explicitly modifies the benzene-NO2 motif. Examples show the method either detaches the NO2 group from the benzene ring and relocates it to a non-aromatic structural position or performs a direct substitution of functional groups, replacing the mutagenic NO2 group with a benign SO2 group.

Benzene: GDCE-I flips 94.8% of the sampled molecules and 86.4% satisfy the ground-truth motif condition, i.e., the benzene ring is actually removed or created. Notably, 74.9% of all flips are obtained without inserting or deleting a single edge by substituting ring atoms.

The authors acknowledge: Our results should not be read as evidence that generative counterfactual explainers dominate heuristic ones. They note that GDCE-I requires a conditional diffusion model trained per dataset, a cost the mask-based baselines do not incur at all. Additionally, "The counterfactuals we generate are edits to a molecular graph... 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."

The paper concludes that GDCE-I "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 second contribution is the evaluation itself"—deriving desiderata and defining suitable metrics for the graph domain.

Improvement 1: Manifold-Constrained Generative Editing for Discrete Structured Data

The improved AI system can perform edits on graphs, molecules, or other discrete structures that are guaranteed to remain on the data manifold (i.e., chemically valid, topologically realistic) by integrating a discrete denoising diffusion model with Gumbel-Max inversion. Unlike heuristic or mask-based editors, this system can generate counterfactuals that respect domain constraints (e.g., chemical valency, categorical node/edge types) while exploring the full edit space (node types, edge types, topology) in a single generative pass. This enables precise, minimal, and semantically meaningful modifications that are not merely close to the input but are plausible samples from the underlying data distribution.

Improvement 2: Classifier-Free Guidance for Robust Counterfactual Search

The improved AI system can steer counterfactual generation toward a target prediction without relying on gradients from corrupted or invalid intermediate states. By using classifier-free guidance with a null-token conditioning mechanism, the system avoids the ill-posed problem of assigning continuous properties to highly noisy or invalid graph states. This yields more stable and reliable guidance, especially in sparse topological spaces, and allows the system to extrapolate toward the desired outcome while maintaining structural validity—a key advantage over classifier-based guidance methods that fail on discrete, sparse data.

Improvement 3: Exact Reconstruction via Posterior Noise Recording (Gumbel-Max Inversion)

The improved AI system can guarantee exact reconstruction of the original input when no guidance is applied, by recording the Gumbel noise that forces the guided reverse posterior to reproduce the reference state. This enables the system to isolate the effect of guidance: only positions where the guidance-induced shift in log-probabilities exceeds the recorded margin will change. This provides a principled way to control edit locality and ensures that any deviation from the input is solely due to the target condition, not sampling stochasticity—improving the reliability and interpretability of counterfactual explanations.

Improvement 4: Dynamic Budget Search for Minimal Edits

The improved AI system can automatically identify the minimal structural deviation required to alter a model’s prediction by searching over increasing diffusion timesteps (budgets). Starting from a reference state at a given timestep and denoising to the final graph, the system returns the counterfactual at the smallest budget that achieves the target flip. This eliminates the need for manual tuning of edit budgets and ensures that explanations are as sparse as possible, directly optimizing for understandability and minimality—critical for high-stakes applications like drug discovery or fraud detection.

Improvement 5: Transferable Counterfactual Validation via Surrogate Distillation

The improved AI system can evaluate counterfactual quality beyond mere prediction flips by validating against a retrained surrogate model (distilled independently from the target model). This measures the transferability of the counterfactual flip, confirming that the explanation relies on robust structural features rather than weight-specific noise or adversarial artifacts. This makes the system’s outputs more trustworthy and actionable, as they are more likely to generalize to other models or real-world settings.

Improvement 6: Multi-Desiderata Evaluation Framework for Graph Explanations

The improved AI system can systematically assess counterfactual explanations along three desiderata—fidelity (non-adversarial rate), understandability (edge/node/edge-type sparsity), and sufficiency (non-adversarial flip rate)—derived from holistic explanation theory. This provides a standardized, rigorous evaluation protocol that goes beyond simple flip rates, enabling fair comparison across methods and ensuring that explanations are not only effective but also minimal and semantically coherent. This is particularly useful for benchmarking future graph explainers.

Improvement 7: Domain-Aware Edit Allocation

The improved AI system can automatically allocate its edit budget to the most semantically relevant features for the task at hand. For example, on Mutagenicity, it focuses on topology (e.g., detaching a mutagenic NO2 group); on Benzene, it substitutes ring atoms without adding/removing edges. This is achieved by the diffusion model’s learned distribution over node and edge types, which naturally prioritizes edits that are both minimal and chemically meaningful. This makes the system adaptable to diverse domains (e.g., molecules, proteins, social networks) without task-specific heuristics.

Improvement 8: Scalable Counterfactual Generation for Large Graph Datasets

The improved AI system can generate counterfactuals for large-scale graph datasets (e.g., TWITTER with thousands of nodes) efficiently, as demonstrated by high flip rates (0.996) and non-adversarial rates (0.954) without prohibitive computational cost. By leveraging discrete diffusion with efficient sampling and inversion, the system scales to real-world graph sizes, making it practical for deployment in production environments where explainability is required at scale.