D4Explainer: In-Distribution GNN Explanations via Discrete Denoising Diffusion

Jialin Chen, Shirley Wu, Abhijit Gupta, Rex Ying

Abstract

The widespread deployment of Graph Neural Networks (GNNs) sparks significant interest in their explainability, which plays a vital role in model auditing and ensuring trustworthy graph learning. The objective of GNN explainability is to discern the underlying graph structures that have the most significant impact on model predictions. Ensuring that explanations generated are reliable necessitates consideration of the in-distribution property, particularly due to the vulnerability of GNNs to out-of-distribution data. Unfortunately, prevailing explainability methods tend to constrain the generated explanations to the structure of the original graph, thereby downplaying the significance of the in-distribution property and resulting in explanations that lack reliability. To address these challenges, we propose D4Explainer, a novel approach that provides in-distribution GNN explanations for both counterfactual and model-level explanation scenarios. The proposed D4Explainer incorporates generative graph distribution learning into the optimization objective, which accomplishes two goals: 1) generate a collection of diverse counterfactual graphs that conform to the in-distribution property for a given instance, and 2) identify the most discriminative graph patterns that contribute to a specific class prediction, thus serving as model-level explanations. It is worth mentioning that D4Explainer is the first unified framework that combines both counterfactual and model-level explanations. Empirical evaluations conducted on synthetic and real-world datasets provide compelling evidence of the state-of-the-art performance achieved by D4Explainer in terms of explanation accuracy, faithfulness, diversity, and robustness.

The Challenge of GNN Explainability: The OOD Trap

As Graph Neural Networks (GNNs) are increasingly deployed in high-stakes fields like drug discovery and financial auditing, understanding why they make certain predictions is critical. However, current GNN explainability methods suffer from a significant flaw known as the Out-of-Distribution (OOD) Trap.

Most explainers identify important subgraphs by deleting edges or perturbing the input. If an explainer suggests a graph structure that looks nothing like the training data, the GNN’s response to that graph is inherently unreliable. These "hallucinated" explanations fail to reflect the model's true decision-making process on real-world data. Furthermore, pruning-only search methods rarely consider adding edges, which limits their ability to find meaningful "what-if" (counterfactual) scenarios—such as how adding a single bond might turn a non-toxic molecule into a toxic one.

Comparison of counterfactual explanations. D4Explainer generates in-distribution examples that stay close to the original data manifold, unlike previous methods that fall into the 'OOD trap'.

D4Explainer: A Unified Diffusion Framework

To address these limitations, we introduce D4Explainer (In-Distribution GNN Explanations via Discrete Denoising Diffusion). This framework leverages generative diffusion models to learn the underlying distribution of the graph data, ensuring that all generated explanations are "in-distribution."

Discrete Structural Diffusion

Unlike standard diffusion models that add Gaussian noise to pixels, D4Explainer uses a discrete Markov chain to progressively add or remove edges until the graph becomes random noise. A Provably Powerful Graph Network (PPGN) serves as the denoising backbone, trained to recover clean, realistic graph structures from these noisy inputs.

Dual-Objective Optimization

The model is trained with a combined loss function designed for both realism and explanatory power:

  • Distribution Loss ($L_{dist}$): Ensures the generated graph stays on the "data manifold," resembling the training data.
  • Counterfactual Loss ($L_{cf}$): Encourages the model to find the minimal structural change—whether adding or deleting edges—that flips the GNN's prediction.
The D4Explainer framework: (a) Diffusion process for counterfactual explanations and (b) Reverse sampling for model-level explanations.

Unified Explanations

D4Explainer is the first framework to unify instance-level (counterfactual) and model-level explanations. For model-level insights, the system uses classifier-guided reverse sampling. Starting from pure noise, it iteratively selects the most discriminative patterns that maximize the GNN's confidence for a specific target class, revealing what the model perceives as the "ideal" representation of that class.

Experimental Results

We evaluated D4Explainer on eight diverse datasets, including synthetic motifs (BA-Shapes, Tree-Cycle) and real-world molecular datasets (Mutag, BBBP, NCI1).

  • Superior Accuracy: D4Explainer achieved a Counterfactual Accuracy (CF-ACC) of over 80% while modifying only 5% of edges, significantly outperforming baselines like CF-GNNExplainer.
  • Faithfulness and Reliability: Using Maximum Mean Discrepancy (MMD) tests, we confirmed that D4Explainer’s generated graphs are statistically the closest to the original test distributions. This in-distribution property ensures that the GNN's feedback during the explanation process is trustworthy.
  • Model-Level Clarity: Qualitatively, D4Explainer generated much cleaner, more recognizable motifs for specific classes (e.g., perfect "house" shapes for the BA-3Motif dataset) compared to the noisy outputs of previous state-of-the-art methods like XGNN.

Conclusion

D4Explainer represents a significant step forward in trustworthy AI for graphs. By incorporating generative distribution learning, it avoids the pitfalls of OOD perturbations and provides a robust, unified tool for both counterfactual and model-level auditing. Future work will look to extend this diffusion approach to continuous node and edge attributes, further broadening its applicability in complex domains like 3D molecular modeling.

Summary updated

Abstract

The widespread deployment of Graph Neural Networks (GNNs) sparks significant interest in their explainability, which plays a vital role in model auditing and ensuring trustworthy graph learning. The objective of GNN explainability is to discern the underlying graph structures that have the most significant impact on model predictions. Ensuring that explanations generated are reliable necessitates consideration of the in-distribution property, particularly due to the vulnerability of GNNs to out-of-distribution data. Unfortunately, prevailing explainability methods tend to constrain the generated explanations to the structure of the original graph, thereby downplaying the significance of the in-distribution property and resulting in explanations that lack reliability. To address these challenges, we propose D4Explainer, a novel approach that provides in-distribution GNN explanations for both counterfactual and model-level explanation scenarios. The proposed D4Explainer incorporates generative graph distribution learning into the optimization objective, which accomplishes two goals: 1) generate a collection of diverse counterfactual graphs that conform to the in-distribution property for a given instance, and 2) identify the most discriminative graph patterns that contribute to a specific class prediction, thus serving as model-level explanations. It is worth mentioning that D4Explainer is the first unified framework that combines both counterfactual and model-level explanations. Empirical evaluations conducted on synthetic and real-world datasets provide compelling evidence of the state-of-the-art performance achieved by D4Explainer in terms of explanation accuracy, faithfulness, diversity, and robustness.
BibTeX
@misc{chen2023d,
  author = {Jialin Chen and Shirley Wu and Abhijit Gupta and Rex Ying},
  title = {{D4Explainer: In-Distribution GNN Explanations via Discrete Denoising Diffusion}},
  year = {2023},
  eprint = {2310.19321},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2310.19321},
}
Figure