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

• URL: http://arxiv.org/abs/2608.12083v1
• Date: Wed, 12 Aug 2026 14:04:49 GMT
• Title: Faithful, Sufficient and Understandable: Rethinking Graph Counterfactual Explanations via Discrete Diffusion Inversion
• Abstract summary: Graph Neural Networks (GNNs) achieve strong predictive performance on graph-structured data across domains such as chemistry, biology, and network analysis.<n>They provide no intrinsic explanation of their predictions.<n>Counterfactual explanations address this by revealing the minimal structural modifications that would change a model's prediction.<n>We propose Graph Diffusion Counterfactual Explanation via Inversion (GDCE-I)
• Score: 0.8594140167290097
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• When Do Graph Foundation Models Transfer? A Data-Centric Theory [68.54337055801571]
  Graph foundation models (GFMs) aim to reuse a single backbone across diverse graph domains, yet their transfer is often uneven and can exhibit negative transfer.<n>We show that for both set-based and message-passing tokenizations, any Lipschitz backbone admits an explicit decomposition of cross-domain output shift.<n>A key ingredient is positional-encoding (PE) stability: we establish stability guarantees for spectral PEs and highlight contrasting behaviors of eigenvector- versus subspace-based PEs.
  arXiv  Detail & Related papers  (2026-05-28T12:07:27Z)
• Forget and Explain: Transparent Verification of GNN Unlearning [3.0152570264250347]
  We propose an explainability-driven verifier for GNN unlearning that snapshots the model before and after deletion.<n>We evaluate two backbones (GCN, GAT) and four unlearning strategies (Retrain, GraphEditor, GNNDelete, IDEA) across five benchmarks.<n>Results show that Retrain and GNNDelete achieve near-complete forgetting, GraphEditor provides partial erasure, and IDEA leaves residual signals.
  arXiv  Detail & Related papers  (2025-12-08T11:25:19Z)
• Graph Diffusion Counterfactual Explanation [0.8594140167290097]
  We introduce Graph Diffusion Counterfactual Explanation, a novel framework for generating counterfactual explanations on graph data.<n>We empirically demonstrate that our method reliably generates in-distribution as well as minimally structurally different counterfactuals for both discrete classification targets and continuous properties.
  arXiv  Detail & Related papers  (2025-11-20T12:06:53Z)
• Discrete Diffusion-Based Model-Level Explanation of Heterogeneous GNNs with Node Features [0.25782420501870296]
  We present DiGNNExplainer, a model-level explanation approach that synthesizes heterogeneous graphs with realistic node features.<n>We evaluate our approach on multiple datasets and show that DiGNNExplainer produces explanations that are realistic and faithful to the model's decision-making.
  arXiv  Detail & Related papers  (2025-08-11T20:33:10Z)
• Graph Counterfactual Explainable AI via Latent Space Traversal [4.337339380445765]
  Counterfactual explanations aim to explain predictions by finding the ''nearest'' in-distribution alternative input.<n>We propose a method to generate counterfactual explanations for any differentiable black-box graph classifier.<n>We empirically validate the approach on three graph datasets, showing that our model is consistently high-performing and more robust than the baselines.
  arXiv  Detail & Related papers  (2025-01-15T15:04:10Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data. The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
  arXiv  Detail & Related papers  (2024-01-12T17:57:07Z)
• Supercharging Graph Transformers with Advective Diffusion [28.40109111316014]
  This paper proposes Advective Diffusion Transformer (AdvDIFFormer), a physics-inspired graph Transformer model designed to address this challenge.<n>We show that AdvDIFFormer has provable capability for controlling generalization error with topological shifts.<n> Empirically, the model demonstrates superiority in various predictive tasks across information networks, molecular screening and protein interactions.
  arXiv  Detail & Related papers  (2023-10-10T08:40:47Z)
• MixupExplainer: Generalizing Explanations for Graph Neural Networks with Data Augmentation [6.307753856507624]
  Graph Neural Networks (GNNs) have received increasing attention due to their ability to learn from graph-structured data. Post-hoc instance-level explanation methods have been proposed to understand GNN predictions. We shed light on the existence of the distribution shifting issue in existing methods, which affects explanation quality.
  arXiv  Detail & Related papers  (2023-07-15T15:46:38Z)
• Reinforced Causal Explainer for Graph Neural Networks [112.57265240212001]
  Explainability is crucial for probing graph neural networks (GNNs) We propose a reinforcement learning agent, Reinforced Causal Explainer (RC-Explainer) RC-Explainer generates faithful and concise explanations, and has a better power to unseen graphs.
  arXiv  Detail & Related papers  (2022-04-23T09:13:25Z)
• Handling Distribution Shifts on Graphs: An Invariance Perspective [78.31180235269035]
  We formulate the OOD problem on graphs and develop a new invariant learning approach, Explore-to-Extrapolate Risk Minimization (EERM) EERM resorts to multiple context explorers that are adversarially trained to maximize the variance of risks from multiple virtual environments. We prove the validity of our method by theoretically showing its guarantee of a valid OOD solution.
  arXiv  Detail & Related papers  (2022-02-05T02:31:01Z)
• Discovering Invariant Rationales for Graph Neural Networks [104.61908788639052]
  Intrinsic interpretability of graph neural networks (GNNs) is to find a small subset of the input graph's features. We propose a new strategy of discovering invariant rationale (DIR) to construct intrinsically interpretable GNNs.
  arXiv  Detail & Related papers  (2022-01-30T16:43:40Z)
• Source Free Unsupervised Graph Domain Adaptation [60.901775859601685]
  Unsupervised Graph Domain Adaptation (UGDA) shows its practical value of reducing the labeling cost for node classification. Most existing UGDA methods heavily rely on the labeled graph in the source domain. In some real-world scenarios, the source graph is inaccessible because of privacy issues. We propose a novel scenario named Source Free Unsupervised Graph Domain Adaptation (SFUGDA)
  arXiv  Detail & Related papers  (2021-12-02T03:18:18Z)
• Nonlinear State-Space Generalizations of Graph Convolutional Neural Networks [172.18295279061607]
  Graph convolutional neural networks (GCNNs) learn compositional representations from network data by nesting linear graph convolutions into nonlinearities. In this work, we approach GCNNs from a state-space perspective revealing that the graph convolutional module is a minimalistic linear state-space model. We show that this state update may be problematic because it is nonparametric, and depending on the graph spectrum it may explode or vanish. We propose a novel family of nodal aggregation rules that aggregate node features within a layer in a nonlinear state-space parametric fashion allowing for a better trade-off.
  arXiv  Detail & Related papers  (2020-10-27T19:48:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.