D4Explainer: In-distribution Explanations of Graph Neural Network via Discrete Denoising Diffusion
Authors: Jialin Chen
Shirley Wu
Abhijit Gupta
Zhitao Ying
Venue: NeurIPS 2023 poster (2023)
Keywords: Explainability
Graph Neural Network
Diffusion Model

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.

D4Explainer: In-Distribution GNN Explanations via Discrete Denoising Diffusion
Jialin Chen Yale University ji jialin. chen@yale.edi edu
Shirley Wu Stanford University shirwu@cs. stanford edu
Abhijit Gupta Yale University
maanjiit.gpta@yyle...
Rex Ying Yale University rex. rex.yinggylle.co edu
Abstract
The widespread deployment of Graph Neural Networks (GNNs) sparks signifi- cant interest in their explainability, which plays vital role in model auditing and ensuring trustworthy graph learning. The objective of GNN explainability is 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 the vulnerabil- ity of GNNs to out-of-distribution data. Unfortunately, prevailing explainability methods tend to constrain the generated explanations the structure of the orig- inal 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 goals: 1) generate collection
optimization objective, which accomplishes diverse counterfactual graphs that conform to the in-distribution property for given instance, and identify the most discriminative graph patterns that con- tribute to a specific class prediction, thus serving as model-level explanations. is worth mentioning that D4Explainer 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.
1 Introduction
Graph neural networks (GNNs) have rapidly gained popularity recently due to their ability to model relational data [1, 2]. However, when it comes critical decision-making and high-stake applications, such as healthcare, finance, and autonomous systems, the explainability of GNNs is fundamental for humans to understand the model's decision-makin logic and build trust in the deployment of GNNs in real-world scenarios [3, 4, 5].
Counterfactual and model-level explanations. Existing methods mainly focus factual and instance-leve explanations [6, 7, 8, 9, 10, 11], while the significance of counterfactual and model- level explanations are equally noteworthy, yet under-explored. Counterfactual explanation considers
The code is available
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

"what-if" scenarios of model predictions, addressing the question of how slight adjustments to the input graph can lead to different model predictions [12. 13, 14]. Model-Ievel explanation. on the other hand, aims to generate the most discriminative graph pattern for a target class, thus shedding light on the overall decision-makinng and model-level explanations present a distinct challenge concerning the distribution constraint imposed on generated explanations. An explanation that is faithful and reliable should adhere to the distribution of the underlying dataset. This becomes particularly crucial in real-world scenarios where domain-specific rules exist, such as in drug design and molecule generation. In such cases, explanations should conform to the true distribution of the dataset [16, 17, 18).
behavior and internal functioning of the model [15, 16]. Counterfactual
However, the existing methods typically extract explanatory subgraphs from the input graph, ignoring additional possible edges. This pre- vailing paradigm heavily relies on the out- of-distribution (OOD) effect to influence the
Dimension
node to explan explann
countorfactual txmmll Tree [CF GNMExplainof
counter fectual esample the [DcEsplaieer
Dimerziont
Ditaglaner
model's prediction. To illustrate this point, in
Figure 1, we show the t-SNE projection of the Tree-Cycle dataset, where graphs are labeled as Tree or Cycle based on whether they present the corresponding structures. Specifically, CF- GNNExplainer [13] generates counterfactual ex- planations for node with Tree label by remov- ing its neighbor edges. While the explanation doesn't 't maintain any discriminative information on the Cycle class, it could still be predicted as Cycle with high probability due the OOD effect, making the explanation unreliable.
original
nodes to explain
original adges added edges deleted edges
Figure 1: t-SNE Projection of Tree-Cycle dataset, where Cycle is a counterfactual motif for Tree.
On the other hand, generating in-distribution graphs is challenging, due to the difficulty of encoding complex graph distributions, e.g. the distribu- tion of node degrees, cycle counts and edge homogeneity. Recently, graph diffusion models have shown to be a powerful technique to encode such complex distribution on graphs [19, 20], which trains a powerful denoising model that progressively removes noise from random noise graph and then tractably recovers in-distribution samples.
Proposed work. Inspired by the success of graph diffusion models, we propose a novel GNN explainability approach, D4Explainer, in- in-Distribution GNN explanations via Discrete Denoising Diffusion. Through forward diffusion process that progressively introduces random noise, we enable D4Explainer to optimize for alternative and diverse explanations based on multiple noisy versions of the given graph. powerful denoising model is trained to remove noise and eliminate redundant edges that are irrelevant to the target property, thereby ensuring the model's I's robustness. By employing carefully designed loss function that incorporates both the preservation of the counterfactual property and generative graph distribution learning, D4Explainer is capable of generating in in-distribution counterfactual explanations. As highlighted in green in the bottom left of Figure 1, D4Explainer adds essential edges that complete the truly counterfactual motif, ie., Cycle. With slight modification to the loss function, D4Explainer can also perform model-level explanations for a specific target class.
Empirical experiments on eight synthetic and real-world datasets show that D4Explainer achieves state-of-the-as art performance in both counterfactual and model-level explanations, with strong coun- terfactual accuracy (>80% ) when only 5% of the edges are modified. Maximum mean discrepancy (MMD) metrics show that the distribution of explanations generated by D4Explainer is the closest to the original distribution of the dataset, compared with all baselines. D4Explainer obtains the highest Top- K accuracy in the robustness evaluation, which further illustrates that D4Explainer capable of generating consistent explanations with the presence of noise.
Our contributions are in three-folds: (1) A novel approach to generate in-distribution, diverse and robust explanations is proposed, which leverages the denoising diffusion model to capture the underlying distributions of explanation graphs: (2) D4Explainer explores counterfactual explanations in a larger search space by allowing adding edges, which provides high-level understandings of how edge addition helps create truly counterfactual motifs; (3) D4Explainer represents the first

---

framework that unifies counterfactual and model-level explanations, providing faithful explanations for both settings.
2 Related Work
Explainability of GNNs Compared with the explainability methods in image domain [21, 22, 23, 24, 25, 26, 27], explainabilityy in GNNs [3] remains a challenging problem due the discrete structure of graphs. Here, we focus on post-hoc and model-agnostic explanations. Non-parameterized methods rely on gradient-like signals [28, 29], relevant walks [30, 31J, perturbation [9, 32, 33, 34] to identify important node/edge features or graph structures as explanations, without learnable parameters. Score-based explainability [6, 8, 7, 35] formulate trainable model obtain the importance scores on node features or edge as the explanations by maximizing the mutual information between the explanatory subgraph and the target prediction. Counterfactual explanation methods find minimal perturbation to the graph instance such that the prediction changes. However, most existing methods [13, 36] only consider edge deletion on the original graph without any distribution constraints, thus easily creating out-of-distributin
samples and overfitting the noise over each individual instance. CLEAR [37] the only explainer that also considers adding edges in generating counterfactual explanations. However, the intrinsic effect of edge addition to counterfactual properties under-explored by CLEAR. Generation- based explanations is a recently popular trend that trains graph generators to generate GNN explanations. Existing works train policy networks for the sequential graph generation process based on the reinforcement learning approach [38, 10, 15] or explicitly parameterize the distribution of model-level explanations [16]. The differences of our method are (1) we prevent explicit modeling and sequential decision decision-making learning but incorporate the generative graph distribution learning implicitly into the training procedure and (2) the more stable and robust generative backbone i.e. diffusion model ensures better properties of the generated explanations, e.g., diversity and robustness.
Graph Diffusion Models Denoising diffusion probabilistic models [39, 40, are shown to be powerful for wide range of generative tasks, including images [42]. language [43], and discrete graph domain [19, 20, 44]. Recent work [20] proposes to use discrete noise for the forward Markov process without relying on continuous Gaussian perturbations. Another related work [19] formulates the diffusion process the categorical node and edge attributes and successfully generates real and in-distribution graphs. Recently, the score-based model [45] and stochastic differential equations formulation have been applied to the field of graph generation [46, 47J. These related works highlight the effectiveness of diffusion models for graph denoising and generation tasks. In our paper, we design the pipeline of the diffusion basedd model for explanation task scenarios, well as devise novel classifier glassifer-guidded sampling algorithm for model-level explanations.
3 Preliminaries
3.1 Problem Formulation
Counterfactual explanation. Given an instance (i.e., a node or a graph) and a well-trained GNN, the goal of counterfactual explanation is to identify the minimal modification to the original instance that alters GNN's prediction [12, 13, 36]. Without loss of generality, we consider the explanation problem for the graph classification task. Formally, let ff denote well-trained GNN classifier to be explained, YG denote the label of graph G predicted by f. The counterfactual explanation G satisfies that Yo- * Ya. while the difference between G and G is minimal. This problem is usually formulated as an optimization problem that minimizes the mutual information between G and Yo [6, 13].
Model-level explanation. Model-Ievel explanation aims to identify recurring and discriminant graph patterns that can trigger a specific prediction from the model f [15, 16]. Formally, given a class C; E (C.,.... Ct). model-level explanation for the target class C; can be defined as Gm argmaxg (C) where (C denotes the probability for the class C, predicted by the GNN f. given the graph G. See Appendix B for more descriptions of the explanation task setting.
3

---

3.2 Discrete Diffusion Process for Graph
Forward diffusion process. In this work, we focus on discrete structural diffusion and leave the diffusion over continuous features in future work. Let [0, denote the timestep of the diffusion process, which is also a noise level indicator. Let A, denote the one-hot version of the adjacency matrix at timestep t. where each element a, is 2-dimensional one-hot encoding of the presence absence of the ij-th element in the adjacency matrix. The forward diffusion process is Markov chain with a transition matrix Q2 E _2x2, that progressively transforms the input graph into pure noise. Mathematically, the forward diffusion process can be written as q(a² (a{-1) Cat(a," P= a Q.), where Cat(æ:; P) is categorical distribution over the one-hot vector with probability vector P. The multi-step diffusion has a closed form as q(a, 2 ( Cat(a ai P ag Q,), where
Q, = IT Q; See Appendix C for detailed derivation.
Graph-level expression. The forward diffusion process identically and independently performed over each edge in the full adjacency matrix. Therefore, the graph-level diffusion y(,]|G,)) is the product element-wise categorical distributions as
(G =
II q((a 1 and G(G]|Go) = I g(a (a))) ij
Denoising diffusion models have shown a powerful ability to recover complex distributions accu- rately [48, 41, 20, 44], by leveraging the diffusion process capture intricate dependencies and generate samples that exhibit high-quality in-distribution property and diversity.
Proposed Method: D4Explainer
D4Explainer is designed for two distinct explanation scenarios: counterfactual explanation and model- level explanation. In counterfactual explanation (Sec. 4.1), D4Explainer employs Forward diffusion process to create a sequence of noisy versions and trains a Denoising model to effectively capture the desired distribution of counterfactual graphs. For model-level explanation (Sec. 4.2), D4Explainer trains a Denoising model to recover the underlying original distribution and leverages a well-trained GNN progressively enhance the explanation confidence during the reverse sampling. An overview is shown in Figure 2. The notation used throughout this work is summarized in Appendix A.
input graph
Diffusion Process: G GG,
Reverse Sampling Process
Lef
C
Gy-s
To
Denoising
Ldist
G/ (GG
Denolsing Model Gy- Ra(G, G.
Selection
6g
B
static
6.36
highest condidenge
original
noise level E- MMPP
E
deleted
added
(a) Diffusion Model for Counterfactual Explanation
(b) Sampling Model-level Explanation
Figure 2: Overview of D4Explainer. (a) Diffusion Model for counterfactual explanations. The diffusion process GG,,( transforms input graph Go the pure noise Gr. Then the Denoising
Model pe(-) (-) outputs the clean graph Go given noisy graph G,, under the constraints of the counterfactual loss Lef and the distribution loss Caist- (b) Reverse Sampling for model-level explanations. We leverage well-trained GNN to select temporary graph with the highest confidence score from the candidate graphs and obtain G from G² recursively until we achieve the final medel-level explanation Go.

---

4.1 Counterfactual Explanation Generation
Forward diffusion process. We build on the discrete diffusion process over graphs as introduced in Sec. 3.2. The forward Diffusion Process enables D4Explainer to optimize with sequence of perturbed graphs (Gu, G1.-.. Gr with increasing levels of noise, which essentially enable D4Explainer to thoroughly explore possible counterfactual explanations for the given graph.
Denoising model. To generate a counterfactual graph that closely resembles the input graph, the Denoising Model Pe) takes as imput the noisy adjacency matrix A, corresponding to a noisy graph Gr, the node features of the original graph Xo. noise level indicator t, and then predicts the dense adjacency matrix. Through sampling from the dense adjacency matrix with the reparameterizattion trick [49], arrive at the discrete adjacency matrix Au and the corresponding explanation graph Gg. The Denoising Model is set an extension of the provably powerful Graph Network (PPGN) [50]. To incorporate time information, an MLP module is employed to process the noise level indicator and learn time-related latent features, thereby enhancing the denoising capability. The edge features, node features, and time-related latent features are concatenated and updated by the powerful layers (PPGN). We refer to Appendix D.1 for complete and detailed description of the PPGN used in our D4Explainer.
Loss function. Different from traditional graph generation tasks [20. 19, 47], counterfactual explana- tions necessitate both counterfactual property and proximity to the original graph. To address these challenges, we propose specifically designed loss function that simultaneously optimizes these two properties. Instead of iteratively recovering the intermediate noisy graph G, in the traditional manner, we employ a re-weighted version of the evidence lower bound (ELBO) on the negative log- likelihood that directly reconstructs the initial distribution at t = 0 in our distribution- -earionng term Caist- The re- re-weighting strategy prioritizes more challenging denoising tasks at larger timesteps:
(1 2-
7) B.(c..G.) log po (Go Gt),
Ldist -Ey(Go)
Br
where B, is the transitioning probability (the off-diagonal element in the transition matrix Q2) and (Go)) is the distribution of the training dataset. The distribution loss Caist is equivalent to the cross-entropy loss between Go and po Do(Go). over the full adjacency matrix, which guarantees the proximity of generated counterfactual explanations to the original graph. To optimize the counterfactual property, we design specific counterfactual loss Lef as follows.
Lef - Byy(..) Be- ByGG Go) (Go log (1oolo))
where f is the well-trained GNN classifier, f(Co) denotes the probability for the original label YG, predicted by f, given the generated graph Go. Our total loss function is formulated as L())= = Laisst + aLCef. where a is a hyper-parameter that balances the counterfactual and in- distribution propertics. Achieving the desired counterfactual property while maintaining proximity to the true data distribution involves trade-off. For instance, making drastic modifications to the original graph may casily alter the model's prediction, but it can also lead to an explanation that deviates significantly from the original graph. The distribution loss Laist and the counterfactual loss Lef together encourage the denoising model to eliminate redundant edges that are irrelevant to the counterfactual property while reconstructing the original edges to preserve the true distribution.
Working principle of D4Explainer. D4Explainer not only preserves the in-distribution property but also introduces diversity and robustness the generated counterfactual explanations. Diversity enables the explainer to provide multiple alternative explanations for model predictions, while robustness ensures consistent effectiveness of the explanations even in the presence of noise. Existing explainers often optimize a singular explanation per instance, leading to overfitting on noise and bias attribution issues [51]. On the contrary, D4Explainer's 's objective is to search for counterfactual graphs within the distribution of the original graphs, adhering to the constraints imposed by Laist and Cef- Through an iterative process of adding noise and removing counteffactual-ireleewe D4Explainer captures the underlying distribution of counterfactual explanations. This denoising strategy also enhances the robustness of D4Fxplainer. Moreover, the inherent stochasticity in the forward processes introduces diversity into the generated explanations.
edges,
5

---

4.2 Model-level Explanation
Motivation. The goal of model-level explanation is to generate class-wise graph patterns. Let C denote the target class. Each reverse sampling step (c(C(_1 can be formulated conditional generation satisfying the following equation,
where G(C) can be computed by the target class probability predicted by the well-trained GNN /. conditioned on the given graph Go. Existing sampling methods [20, 41] cannot perform conditional sampling in the discrete context, as we cannot sample all possible Go to obtain ((C)))) and then compute the normalized probabilities. To overcome these challenges, we propose to utilize the well-trained GNN as guidance toward the target class. At each step, we generate set of candidates by pa G)) and refer to the GNN to select a temporarily optimal Go with the highest f(C)Go).
Multi-step sampling. We repeat the sampling steps and progressively increase the explanation confidence (i.e., f(C1)G)) in the process. Figure 3 shows an empirical visualization of the reverse generation process for the house motif. We observe that the temporary graph Go gets closer to the target motif with increasing explanation confidence p during the reverse sampling process.
The proposed model-level explanation genera- tion utilizes a denoising model trained with similar procedure as Sec. 4.1 (Figure 2(a)). The difference is that the training loss is only Laists since Lef leads to counterfactual graph that changes the label. To start with, given pre- defined number of nodes N in the target expla- nation, we randomly sample an Erdös-Rényi graph with N nodes and edge probability as G 1/21 Then we sample a set of can- didates from the distribution G The well-trained GNN computes the explanation con- fidences for these candidates and selects the tem- porary explanation Go with the highest score.
Reverse Sampling
c=I
33/4
=
7/4
(p - 0.35)
(+- 0.47
(p= 0.73)
(p 0187)
(p - 0:99)
X
Figure Visualization of the temporary Go at t 34;7/4 72; and the terminal model- level explanation for BA-3Motif (house motif). Different node colors indicate different labels.
Then, we sample G through the same Diffusion Process G7 ~ g(GT-1|Go) as Equation 1. Sampling steps iteratively reverse the chain until we obtain the final model-level explanation Gj after T steps. Apart from explanation confidence f(C)G)), model-level explanations should also satisfy sparsity and succinctness. It is worth noting that the proposed algorithm is capable of preserving the sparsity level similar to the training graphs in the generated explanations. For real-workd datasets that are densely self-connected, it is suggested to plug regularization constraints in the selection policy for the temporary explanation at each step. The complete sampling algorithm is shown in Appendix D.4.
4.3 Complexity Analysis
D4Explainer has a search space of O(N2K) for modifying K edges in an N-nodes graph, which is larger than previous counterfactual explainers that only consider deleting edges. By framing the explanation task as generation problem, the space complexity of each layer in D4Explainer is reduced to O(N3). The time complexity is O(N3) due to the matrix multiplication. Despite the large search space, the complexity of D4Explainer is still acceptable and faster than some generation- explanations [10]. Runtime and more complexity analysis are given in Appendix E. Furthermore, we directly recover the terminal explanation Go in the training procedure, rather than intermediate Ge which greatly increases the efficiency of D4Explainer. The Denoising Model can also be trained in parallel under different noise levels without iterative optimization from t = to f = T.
5 Experiments
5.1 Experimental Setup
We test the proposed approach to explain the performance of node classification models and graph classification models. Dataset statistics and classifier information are summarized in Appendix E.

---

Table 1: CF-ACC AUC and Fidelity (FID) AUC of D4Explainer and baseline explainers eight datasets. We report AUC values computed over 10 modification ratios from 0 to 0.3. The best result is in bold and the second best result is underlined.
BA-Shapes
Tree-Cycle
Tree-Grids
Cornell
BA-3Motif
Mutag
BBBP
NCTI
Models
CF-ACC FID CF-ACC FID CF-ACC FID CF-ACC FID CF-ACC FID CF-ACC FID CF-ACC FID
CF-ACC
FID
Random
0.251
0.261 0,260
0.281
0.337
0.375
0.138
0.172
0.404
0.452
0.192
0.256
0.073
0.113
0.288
0.352
GNNExplainer
0.473
0.444
0.652
0.580
0.672
0.622
0.075
0.120
0.250
0.253
0.450
0.449
0.212
0,241
0.375
0.443
SAExplainer
0.773
0.773 0,405
0.408
0.547
0.542
0.199
0.241
0.474
0.500
0.300
0.338
0.110
0.133
0.421
0,446
GradCam
0.552
0,570
0.637
0.613
0.590
0.578
0.138
0.189
0.459
0.495
0.202
0.250
0.274
0,301
0.467
0.488
IGExplainer
0.208
0.240
0.198
0.226
0.308
0.372
0.233
0.281
0.40
0.474
0.231
0.280
0.159
0.183
0.347
0.389
PGExplainer
0.361
0.357
0.353
0.322
0.293
0.340
0.128
0.204
0.320
0.323
0.208
0.313 0.233
0,282
0.338
0,366
PGMEsplainer
0.208
0.210
0.237
0.206
0.274
0.251
0.105
0.154
0.348
CXPlain
0.125
0.168
0.245
0.220
0.222
0.274
0.132
0.180
0.235
0.239
0.187
0.305
0.067
0.131
0.489
0.484
CINEEpllieer
0.773
0.728
0.812
0.718
0.527
0.328
0.297
0.302
0.751
0.623
0.632
0.715
0.674
D4Explainer
0.838
0.828
0.917
0.862
0.905
0.832
0.623
0.559
0.912
0.922
0.765
0.675
0.781
0.739
0.737
0.690
Node classification. For synthetic datasets, we use BA-Shapes, Tree-Cycle, Tree-Grids [6]. There exists a motif that plays an important role in the model's 's prediction. The node labels are determined by the structural roles. We train vanilla GCN for synthetic datasets, achieving over 95% accuracy on each synthetic dataset. Additionally, we use Cornell [52] dataset, a highly heterophilous real-world webpage graph. Wherein, more complex relationships exist between node and its neighbors, thus posing a more significant challenge to the explanation tasks. We train an EGNN [53], which is specifically designed for heterophilous graphs, achieving 83% accuracy on Cornell.
Graph classification. We use one synthetic dataset, BA-3Motti [54] and three real-world molecule datasets, Mutag [55, 56), BBBP [57] and NCII [58] for graph-clasiffccttion task explanation. BA- 3Motif contains graph classes: graphs with cycle motif, grid motif, and house motif. Mutag, BBBP, and NCI1 are molecular datasets where nodes represent atoms and graphs represent molecules. Specifically, the chemical functionalities of molecules determine the graph labels. We train vanilla GCN for BAt3M,, BBBP, and NCII. For the Mutag dataset, GIN [59] is used as the target GNN.
Baselines. For the counterfactual explanation task, we take the same baseline setup as CF- GNNExplainer[ [33] and involve more recent state-of-the-an explainers as our baselines, including GNNExplainer [6], SAExplainer [29], GradCam [21], IGExplainer [22], PGEXplainer [8], PGMEX- plainer [9], and CXPlain [60]. For the methods that are originally designed for the factual explanation, we construct subgraph with the least important edges as the counterfactual explanation. For the model-level explanation task, we compare with XGNN [15], which is statc-of-the-art model-level explanation method for GNNs. More implementation details are given in Appendix E.3.
5.2 Counterfactual Explanations
Metrics. Following evaluation protocols of prior works [13, 36], we adopt Counterfactual Accuracy, Fidelity, and Modification Ratio (MR) as our metrics. Let G and Go denote the original input graph and generated counterfactual graph, respectively. is the test dataset. Counterfactual Accuracy is defined as the proportion of generated explanations that change the model's prediction, CF-ACC = 1 1-1/I9 (1 = =Yo)). Fidelity measures the change in output probability over the original class, i.e., Fidelity
Modification Ratio refers to the proportion of changed edges as MR = (# of deleted edges + # of added edges) EE] Higher counterfactual accuracy and fidelity with lower modification ratios indicate better performance.
1/1g\Ea-e [(G=] [(G)))>)>)]
Results. CF-ACC and Fidelity are sensitive to the modification ratio, we thus compute the areas under CF-ACC curve and Fidelity curve over 10 different modification ratios from 0 to 0.3. We run 10 different seeds for each approach and report the average in Table 1. As can be seen from the table, D4Explainer achieves the best performances on seven out of eight datasets, with especially strong CF-ACC AUC values (> 90%) Tree-Cycle, Tree-Grids, and BA- Notably, D4Explainer consistently works well on explaining both node classification and graph classification tasks, while the efficacy of baselines is unstable across datasets. For instance, most baselines fail to generate effective counterfactual explanations for complex graphs with multiple motifs or heterophilous edge relations, e.g., Cornell and BA-3Motif.
To further investigate the relation between CF-ACC and the modification ratio, we show the change of CF- ACC w.r.t. modification ratios from 0 to 0.3 in Figure 4, where the X-axis is in the log scale.
7

---

BA-shapes
Tree. Cycle
Mutag
BBBP
CF-Nccuracy
CF Accurrayy
Modification Ratio (log)
Modification Ratio (log)
Modification (log)
Modificaton Ratio (log)
Debaplamer (surs)
GMizxplamer
PoME-plamer
SAEsplainer
Lzexplamer RandomCaster
CF Explatner
PGExplainer
CXPaan
GradCam
Figure CF-ACC Curves of all explainers over different modification ratios from 0 to 0.3. The ar-axis is shown in the log scale. CF-ACC tends to increase as the modification ratio increases in general.
Table 2: MMD distances between the generated explanations and test graphs. We report MMD distances of degree distributions (Deg.), cluster coefficients (Clus.), spectrum distributions (Spec.), and the summation (Sum.). We bold the best value and underlined the second-best best value.
Mutag
BBBP
NCII
Models
Deg.
Spec.
Sum.
Deg.
Spec.
Sum.
Deg.
Clus.
Spec.
Sum.
RandonCaster
0.1593
0.0247
0.0417
0.2257
0.1693
0.0072
0.0397
0.2162
0.1847
1.9769
0.0404
2.2020
GNNExplainer
0.1614
0.0002
0.0409
0.2025
0.1615
0.0002
0.0395
0.2012
0.1577
0.0005
0.0405
0.1987
SAExplainer
0.0940
0.0032
0.0412
0.1384
0.1594
0.0032
0.0402
0.2028
0.189
0.0002
0.0408
0.2300
GradCam
0.1122
0.0083
0.0416
0.1621
0.0699
0.0026
0.0384
0.1109
0.1638
0.0003
0.0404
0.2045
IGExplainer
0.1292
0.0000
0.0411
0.1703
0.0908
0.0000
0.0394
0.1302
0.4288
0.0002
0.0398
0,4688
PGExplainer
0,1475
0.0002
0.0418
0.1895
0.2014
0.0018
0.0403
0.2435
0.1937
0.0000
0.0396
0.2333
PGMExplainer
0,1800
0.0002
0.0419
0.2221
0.1916
0.0003
0.0403
0.2322
0.2199
0.0000
0.0404
0.2603
CXPlain
0,1734
1.2706
0.0417
1.4857
0.1768
0.0001
0.0394
0.2163
0,1629
0.0001
0.0404
0.2034
0.0001
0.0393
0.1264
0.1224
0.0001
0.0404
0,1629
D4Explainer
0.1172
0.0000
0.0244
0.1416
0.0530
0.0000
0.0331
0.0861
0.1006
0.0000
0.0353
0.1359
As illustrated in Figure 4, D4Explainer consistently achieves the highest CF-ACC with the smallest modification ratio (see the right side of the X-axis). Especially for Tree-Cycle and BBBP dataset, D4Explainer obtains significant boost compared to the baselines. It demonstrates that D4Explainer can generate counterfactual explanations that can strongly influence the prediction of the target GNN and reflect the effective counterfactual properties.
5.2.1 In- In-Distribution Evaluation
To evaluate the in-distribution property of the generated explanations, adopt the maximum mean discrepancy (MMD) to compare distributions of graph statistics between the generated counterfactual explanations and original test graphs. Following the evaluation setting in prior works [61, 19, 20, 62, 44], we use Gaussian Earth Mover's Distance kernel to compute MMDs of degree distributions, clustering coefficients, and spectrum distributions. Smaller MMDs mean that the two distributions are more similar and close, which indicates better in-distribution property.
Results. Table shows the MMD results on three real-world molecular datasets. We observe that D4Explainer outperforms baselines in general. Especially for BBBP and NCII datasets, D4Explainer achieves the lowest MMD distances across all metrics. The MMD results verify the effectiveness of D4Explainer in capturing the underlying distribution of datasets and generating in-distribution and more faithful explanations. We refer to Appendix E.4 for more results.
5.2.2 Additional Faithfulness Aspects
Explanation Diversity Evaluation. We evaluate the diversity of counterfactual explanations in Figure 5 and Appendix E.S. The first row shows the original graphs. The second row shows the generated counterfactual explanations by CF-GNNExplainer [6], where only edge deletion allowed. With edge addition, D4Explainer is capable of generating alternative counterfactual explanations from different perspective. As can be found from Figure 5, there are two main approaches to generating counterfactual explanations. The first one is deleting determinant edges and destroying original motif, thus greatly influencing the model's prediction. The second one converting the original motifs to truly counterfactual motifs through both deleting and adding essential edges. Previous methods can only produce the first type of counterfactual explanations, while D4Explainer makes the second approach possible and successful, leading to alternative and diverse counterfactual

---

explanations. We ascribe the success to the special training mechanism of D4Explainer. The intrinsic stochasticity in the forward process allows D4Explainer take as imput a sequence of noisy versions of the original graph, instead of singular input graph. This enlarges the search space of possible counterfactual explanations for D4Explainer.
100
Input Graph
90
house
Top-k Actumay
By Deletion
68
40
30
With Addition
20
D4Esciateer (oun)
GNNExtatter
PGMbppaarr
bouse-oycle
cyole-house
tree-sycle
OF Explaino
PGExp ainer
CXPlnnn
0
original edges
added edpes
deleted edges
Figure 5: Counterfactual explanations compari- son. Red labels represent the motifs in the graph.
Figure 6: Top-K K accuracy w.E.t noise levels on BBBP dataset
Robustness Evaluation. evaluate the robustness of methods, we compare the counterfactual explanations produced the original graph and its perturbed counterpart, respectively. A robust model would predict the same explanation for both inputs. Following previous setup [36], we identify the K most relevant edges in the original counterfactual explanation and compute the fraction of these edges present the explanation of its noisy version, denoted by Top-K Accuracy, We apply noise by randomly adding removing edges with probability A consistent 20% modification ratio is used across all methods. Results on BBBP dataset are shown in Figure 6. We observe that D4Explainer outperforms all baselines over different noise levels from 0 to 10%. We restrict that 10%, as the larger noise may cause the noisy graph to switch the predicted label. Overall, results Figure verify D4Explainer's strong ability generate consistently effective counterfactual explanations despite the noise. See Appendix E.7 for complete results.
5.3 Model-level Explanations
In each step of the reverse sampling, we denoise K candidate graphs from the noisy graph and select tempo-
Motif
XGNN
D4Explalner
rary explanation. Following the set- ting in XGNN [15], we qualitatively evaluate the generated explanations with different pre-defined numbers of nodes N, shown in Figure 7. p de- notes the target class probability pre- dicted by the GNN. A higher p indi- cates higher explanation confidence. We observe that D4Explainer can pro- duce determinant graph patterns with nearly 100% confidence for syn- thetic datasets, e.g., BA-shapes and BA-3Motit
BA-shapes
House
p- 0.63
p 0.06
p
Tree-Grid
Grid
p=
p
BA-3Motif
N
Cycle
P 0.68
P - 0.67
p 0.99
p= 0.95
Figure 7: Qualitative evaluation of D4Explainer
Quantitative evaluation. We adopt the target class probability p and Density as the quantitative met- rics. Density measures the sparsity level of the explanations, which is defined as Density = | where & and denote the set edges and nodes the explanation. Quantitative comparisons between XGNN and D4Explainer under different numbers of nodes are shown in Table 3. Hyperparameter sensitivities of the K (number of candidates in each step) and (number reverse sampling steps) shown in Table 4. The results averaged over 100 generated model-level explanations without

---

any regularization constraints in the selection policy. We find that (1) D4Explainer is capable of generating sparse and succinct model-level explanations with high target class probabilities, even without any regularization constraints on the explanation size. The superiority can be attributed to our distribution learning objective. However, it worth noting that training graphs might be noisy and densely self-connected in some real-world applications. A regularization constraint can be easily plugged into the selection policy if required by downstream tasks; (2) smaller T' and K both degrade the performance and quality of model-level explanations, which further emphasize the effectiveness of candidates and multi-step sampling. In the implementation, we ensure > 20 and T > 50 for a balance between the quality and time complexity.
Table 3: Quantitative comparison in terms of probabil- Table 4: Hyperparameter sensitivity in movel-level explanation generation
ity and density with different numbers of nodes.
Mutag
Tree-Cycle
Mutag (N=6)
Tree-Cycle (N=6)
# nodes
7
Proh
Density
Densiry
Prob.
0.832
0.856
0.920
0.991
0.995
0.989
(1)K
10, T
0.799
0.314
0.987
0.372
Ours
Density
0.278
0.327
0.315
0.400
0.381
0.343
(2) 20,
0.524
0,284
0.991
0.388
(3) K
20,
50
0.812
0.295
0.994
0.361
XGNN
Proh.
0.523
0.824
0.875
0.968
0.989
0.992
20,
100
0.832
0.278
0.325
Density
0,537
0.479
0.437
0.400
0.390
0.367
(5) K
30,7
50
0.823
0.287
0.997
0.361
Conclusion and Broader Impacts
In this work, we propose D4Explainer, a novel generative approach for counterfactual and model-level explanations based on a discrete denoising diffusion model. By framing the explanation problem as a distribution learning task, D4Explainer can generate more reliable explanations with better in-distribution property, diversity and robustness. Additionally, D4Explainer can simultaneously perform model-level explanations with a pre-trained denoising model.
While denoising diffusion models show promise for explaining Graph Neural Networks (GNNs), they face potential scalability concerns on large graphs. Additionally, the explanations rely on the specific GNN architecture, limiting their generalizability across different GNN models. This work has dual social impacts. enhances the transparency and interpretability of GNNs. However, is vital to acknowledge the limitations and potential risks of relying solely on these explanations. They may not always capture the complete causal relationships in complex graph structures, which could lead to unintended consequences, reinforce biases, or make incorrect assumptions about the model's behavior. Looking ahead, an interesting direction for future research to consider the node attributes and edge attributes during the explanation generation, e.g,, by performing diffusion processes over continuous features.
References
[1] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional 2016.
networks. arXiv preprint
[2] Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[3] Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks:
A taxonomic survey. CoRR, 2020.
[4] Phillip E Pope. Soheil Kolouri, Mohammad Rostami, Charles Martin, and Heiko Hoff- mann. Explainability methods for graph convolutional neural networks. In Proceedings the IEEE/CVF conference on computer vision and pattern recognition, pages 10772-10781, 2019.
[5] Enyan Dai, Tianxiang Zhao, Huaisheng Zhu, Junjie Xu, Zhimeng Guo, Hui Liu, Jiliang Tang, and Suhang Wang. A comprehensive survey trustworthy graph neural networks: Privacy, robustness, faimess, and explainability. arXiv preprint 2xXiv:220400870 2022.
[6] Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. In NeurIPS, pages 9240-9251 2019.
10

---

[7] Xiang Wang, Ying-Xin Wu, An Zhang, Xiangnan He, and Tat-Seng Chua. Towards multi- grained explainability for graph neural networks. In Proceedings of the 35th Conference on Neural Information Processing Systems, 2021.
[8] Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong. Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. In NeurIPS, 2020.
[9] Minh N. Vu and My T. Thai. Pgm-explaines Probabilistic graphical model explanations for graph neural networks. In NeurlPS, 2020.
[10] Anonymous. Dag matters! gflownets enhanced explainer for graph neural networks, In Openreview, 2022.
[11] Caihua Shan, Yifei Shen, Yao Zhang, Xiang Li, and Dongsheng Li. Reinforcement learning enhanced explainer for graph neural networks. In NeurIPS, 2021.
[12] Ramaravind K Mothilal, Amit Sharma, and Chenhao Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the 2020 conference on fairness, accountability, and transparency, pages 607-617, 2020.
[13] Ana Lucic, Maartje A. Hoeve, Gabriele Tolomei, Maarten de Rijke, and Fabrizio Silvestri. Cf-gnnexplainer: Counterfactual explanations for graph neural networks. In AISTATS 2022, Proceedings of Machine Learning Research, 2022.
[14] Sahil Verma, John Dickerson, and Keegan Hines. Counterfactual explanations for machine learning: A review. arXiv preprint arXiv:2010. 10596, 2020.
[15] Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. XGNN: towards model-level explanations of graph neural networks. In Rajesh Gupta, Yan Liu, Jiliang Tang, and B. Aditya Prakash, editors, KDD, pages 430-438,10 2020.
[16] Xiaoqi Wang and Han-Wei Shen. Gnninterpreter: A probabilistic generative model-level explanation for graph neural networks. arXiv preprint arXiv:2209.07924, 2022.
[17] Timo Freiesleben. The intriguing relation between counterfactual explanations and adversarial examples. Minds and Machines, 32(1):77-109, 2022.
[18] Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack graph structured data. In ICML, pages 1123-1132, 2018
[19] Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang. Volkan Cevher, and Pas- cal Frossard. Digress: Discrete denoising diffusion for graph generation. arXiv preprint arXiv:2209.1477 2022.
[20] Kilian Konstantin Haefeli, Karolis Martinkus, Nathanaël Perraudin, and Roger Wattenhofer. Diffusion models for graphs benefit from discrete state spaces. arXiv preprint arX1v:2210.01549, 2022.
[21] Ramprasaath R. Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based localization. ICCV, pages 618-626, 2017.
[22] Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks, In ICML, volume 70, pages 3319 33288, 2017.
[23] Jianbo Chen, Le Song, Martin J. Wainwright, and Michael I. Jordan. Learning to explain: An information-theorede perspective on model interpretation. ICML, pages 882-891, 2018.
[24] Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. In ICLR, 2014.
[25] Avanti Shrikumar, Peyton Greenside, Anna Shcherbina, and Anshul Kundaje. Not just a black box: Learning important features through propagating activation differences. CoRR, 2016.

---

[26] Marco Túlio Ribeiro, Sameer Singh, and Carlos Guestrin. "why should I trust you?": Explaining the predictions of any classifier. In KDD, pages 1135-1144, 2016.
[27] Sebastian Bach, Alexander Binder, Grégoire Montavon, Frederick Klauschen, Klaus-Robert Müller, and Wojciech Samek. On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation. PloS one, 10(7), 2015.
[28] Phillip E. Pope, Soheil Kolouri, Mohammad Rostami, Charles E. Martin, and Heiko Hoffmann. Explainability methods for graph convolutional neural networks. In CVPR, pages 10772-10781, 2019.
[29] Federico Baldassarre and Hossein Azizpour. Explainability techniques for graph convolutional networks. CoRR, abs/1905. 13686, 2019.
[30] Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima, Kristof T. Schütt, Klaus- Robert Mülller and Grégoire Montavon. Higher-order explanations of graph neural networks via relevant walks. IEEE Trans. Pattern Anal. Mach. Intell., 2022.
[31] Thomas Schnake, Oliver Eberle, Jonas Lederer. Shinichi Nakajima, K. T. Schutt, Klaus-Robert Muller, and Grégoire Montavon. Higher-order explanations of graph neural networks via relevant walks. arXiv, 2020.
[32] Hao Yuan, Haiyang Yu, Jie Wang. Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. ArXiv, 2021.
[33] Michael Sejr Schlichtkrull, Nicola De Cao, and Ivan Titov. Interpreting graph neural networks for NLP with differentiable edge masking. CoRR, abs/2010.00577, 2020.
[34] Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, Dawei Yin, and Yi Chang, Graphlime: Local interpretable model explanations for graph neural networks. CoRR, abs/2001,063 6,6216 2020.
[35] Tianxiang Zhao, Dongsheng Luo, Xiang Zhang, and Suhang Wang. Towards faithful and consistent explanations for graph neural networks. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pages 634-642, 2023.
[36] Mohit Bajaj, Lingyang Chu, Zi Yu Xue, Jian Pei, Lanjun Wang, Peter Cho-Ho Lam, and Yong Zhang. Robust counterfactual explanations on graph neural networks. Advances in Neural Information Processing Systems, 34:5644-566 2021.
[37] Jing Ma, Ruocheng Guo, Saumitra Mishra, Aidong Zhang, and Jundong Li. Clear: Generative counterfactual explanations graphs. arXiv preprint arXiv.2210.08443, 2022.
[38] Xiang Wang, Yingxin Wu, An Zhang, Fuli Feng, Xiangnan He, and Tat-Seng Chua. Reinforced causal explainer for graph neural networks. IEEE Trans. Pattern Anal. Mach. Intell., 2022.
[39] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In NeurlPS, 2020.
[40] Jascha Sick-Dick,,ein, Eric A. Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamies. In ICML, 2015.
[41] Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 34:17981-17999
2021.
[42] Jonathan Ho, Chitwan Saharia, William Chan, David Fleet, Mohammad Norouzi, and Tim Salimans. Cascaded diffusion models for high fidelity image generation. J. Mach. Learn. Res., 23(4)):1-33, 2022.
[43] Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily L Denton, Kamyar Ghasemipour, Raphael Gontijo Lopes, Burcu Karagol Ayan, Tim Salimans, et al. Photorealistic text-to-image diffusion models with deep language understanding. Advances in Neural Information Processing Systems, 35:3647993366666 2022.
12

---

[44] Han Huang, Leilei Sun. Bowen Du, and Weifeng Lv. Conditional diffusion based on discrete graph structures for molecular graph generation. arXiv preprint arXiv:2301.00427, 2023.
[45] Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. In NeurIPS, 2019.
[46] Chenhao Niu, Yang Song, Jiaming Song. Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modeling. In AISTATS, 2020.
[47] Jaehyeong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. In International Conference Machine Learning, pages 10362-10330 10383. PMLR, 2022.
[48] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840-6851, 2020.
[49] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. arXiv preprint arXiv: 1611.01 144, 2016.
[50] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
[51] Lukas Faber, Amin K. Moghaddam, and Roger Wattenhofer. When comparing to ground truth is wrong: On evaluating gnn explanation methods. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 332-341,24 2021.
[52] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287, 2020.
[53] Kaixiong Zhou, Xiao Huang, Daochen Zha, Rui Chen, Li Li, Soo-Hyun Choi, and Xia Hu. Dirichlet energy constrained learning for deep graph neural networks. Advances in Neural Information Processing Systems, 14:221834222 21846, 2021.
[54] Xiang Wang, Yingxin Wu, An Zhang, Xiangnan He, and Tat-Seng Chua. Towards multi-grained explainability for graph neural networks. Advances in Neural Information Processing Systems, 34:18446-1 -8458, 2021.
[55] Jeroen Kazius, Ross McGuire, and Roberta Bursi, Derivation and validation of toxicophores for mutagenicity prediction. Journal of medicinal chemistry, 48(1):312-320, 2005.
[56] Kaspar Riesen, Horst Bunke, et al. lam graph database repository for graph based pattern recognition and machine learning. In SSPR/SPR, volume 5342, pages 287-297, 2008
[57] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 9(2):113-330, 2018.
(58) Nikil Wale, Ian A Watson, and George Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems, 14:347-375, 2008
[59] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826 2018
[60] Patrick Schwab and Walter Karlen, Cxplain: Causal explanations for model interpretation under uncertainty. Advances in Neural Information Processing Systems, 32, 2019.
[61] Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrun: Generat- ing realistic graphs with deep auto-regressive models. In International conference on machine learning, pages 5708-577 5717. PMLR, 2018
[62] Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans. Scalable deep generative modeling for sparse graphs. International conference on machine learning, pages 2302-2312. PMLR, 2020.
13

---

[63] Paul Erdós, Alfréd Rényi, et al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60, 1960.
[64] Asim Kumar Debnath, Rosa Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):786-79) 1991.
[65] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6908 2014.
[66] Zhiyuan Li and Sanjeev Arora. An exponential learning rate schedule for deep learning. arXiv preprint arXiv:1910.077 2019.
14

---

A Notations
The main notations used throughout this paper summarized in Table 5.
Table 5: Summary of the notations
Notation
Description
An input graph / computational graph for given node
Go
Original graph i.e., G
Xo
Node features
The timestep of the forward diffusion
G Yg
Noisy graph at timestep t
A well-trained GNN classifier to be explained
The label of graph G predicted by Counterfactual explanation of G
G
(C
(G,,..,,.
Class of the input graphs
Gm
Model-level explanation for a certain class
(GG G
Forward diffusion process
pol: G1)
Denoising model
Go
Reconstructed clean graph
Lef
Counterfactual loss
Edist G
Distribution loss
Graph at timestep in the reverse sampling process Explanation confidence
P
Number of candidates in each step for the model-level explanation
T
Number of reverse sampling steps for the model-level explanation (Predefined) number of nodes the target model-level explanation
N
B Explanation Setting
The counterfactual explanation for prediction highlights the smallest change to the original instance that changes the prediction. It is post-hoe step after the model is designed and well-trained. Definition 1. (Counterfactual Explanation) Given well-trained classifier I that predicts the label Ye for an instance G, counterfactual explanation consists an instance G such that the prediction on G is different from the original YG G, such that the difference between G and G is minimal.
be formulated an optimization problem that minimizes the mutual information [6, 13]:
argmin MI(Yg,G) argmax H(GG(G") argmin d(G,G=)<k
-Eya Gr log - P1-P G9)
d(G,Ge)eK
d(G.G))<K
(5)
where MT(-) is the mutual information function, H(-) is the entropy function and H (Ya Go)
Evaio log P, (Yo )+) P, (VG|G') denotes the probability for the Yo label given the counterfactual explanation G", predicted by f. d(G, G*) measures the proximity between the original G and counterfactual explanation G", which can be specified by number of changed edges (including the removed edges and newly added edges). An ideal counterfactual explanation should be similar the original graph, therefore, K is applied
constraint over the proximity.
Definition 2. (Model-level Explanation) Given well-trained GNN classifier f and a set of graph G that predicted as the same label C₁ by f. the model-level explanation for the target class C, is recurrent and determinant graph pattern that leads to the certain prediction made by f.
Formally, the model-level explanation for the target class C₁ can be formulated G argmax (C, where (C can be computed by the probability for the class C, pre- dicted by the well-trained GNN f. Meanwhile, the model-level explanations should be recurrent in the given graph set. Typically, the model-level explanations should adhere the distribution of the input graphs be representative of the graph characterizations [16].
15

---

C Diffusion Process
C.1 Discrete Diffusion Process for Graph
Forward diffusion process. Let t [0,T] denote the timestep of the diffusion process, which is also a noise level indicator. Let A, denote the one-hot version of the adjacency matrix at timestep I, where the row vector a E {0, 1 is a 2-dimensional one-hot encoding of the ij-th element of in the adjacency matrix A,- The forward diffission process is Markov chain that progressively transforms the input graph into pure noise. The forward transition probabilities can be represented by a transition matrix Q₂ E 22x2 where the rs-th element Q = q(a²' = s|ag-1 = r). For example, Q indicates the probability of being absent at timestep t 1 and transitioning to being present at timestep for each edge. Therefore, the transition matrix Q, can be represented as
(1
Bc 3t
31 -1
Q: =
(6)
where 1 Be models the probability that edge state does not change at timestep t (e.g., remaining present or remaining absent in the graph). With the transition matrix and one-hot encoding a the forward diffusion process can be written as q( ( [aا_ Cat a.: : P at" Q2), where Cat(æ; P)
is a categorical distribution over the one-hot vector æ with probability vector P.
Multi-step diffusion. The formulation of Equation allows for computing multiple-step diffusion from a to a. directly in a closed form, by ((a/la, = Cat(a,) P = aj Q.). where Q. = T Q,- Additionally, Q, can also be represented as a symmetric matrix like Equation 6, with 3 being replaced by
1 1 [1
B.
= 2
(1--28)) 23,).
2 1=1
In the implementation, only perform multi-step diffusion. We uniformly sample B, in the range of [0, 0.5] to control the level of noise.
Graph-Ievel expression. The forward diffusion process is independently performed over all of the edges in the full adjacency matrix. Therefore, the graph-level diffusion gGrrGG,-1) is the product of element-wise categorical distributions
GGG =
I a(aa 10 and ((, = I1 a(a (a 1)
(8)
The forward diffusion process transforms the input graph into pure noise when T goes to infinity. The pure noise graph G. is an absent for each edge.
random graph [63] with the probability z of being present or
C.2 Continuous Diffusion Process
In this section, we discuss the extension of D4Explainer for the diffusion over continuous content features (i.e., node features, edge features, etc). Given graph G(Xo, Ao) with the initial node features Xo E Nxd and initial adjacency matrix Ag E {0, 1) NxN, where N, d the number of nodes and feature dimensions respectively. Let Xx, A, denote the noisy node feature and noisy adjacency matrix at timestep f. A, is obtained by the discrete diffusion process in Sec. 3.2, while continuous noisy node features X, rely on continuous Gaussian perturbations. The forward Markov process gradually adds Gaussian noise to the previous state:
(X,1X,_,) = NN' /1 3,
where N denotes the high-dimensional Gaussian distribution, 3, is the variance at timestep t. Similar to discrete diffusion, there is closed form that performs multi-step diffusion:
q( (X2 = (Nx Xo: : (1 - a))
(10)
where 0g = 1- 3r and o. I 0g.. The denoising model takes as input the adjacency matrix A., the noisy node features X, and the noisy level indicator and predicts the clean adjacency matrix Åo
16

---

and node features Xy. Let Go(Xo. diffusion over node features, we need to recover both the original adjacency matrix and original node features. Thus it becomes the cross-entropy between Ag and Ag as well as the cross-entropy between Xu and Xo. Therefore, the distribution loss can be expressed as
(o))))))) Ao) denote the predicted explanatory graph. With the continuous
Ldiee -Bg(A))
Σ
1-2- 1 +)
E (y(A),A)) log (AolAs)
1-1
(11)
By((o)
Σ
1 2. 3r 7) [x(x,(X,) log po (Xo X.)
-
1=1
The above continuous setting can also easily generalize edge features diffusion.
D Model Details
D.1 Denoising Model: PPGN
Our PPGN implementation follows the original paper [50], and [20]. The difference is that we insert an MLP module that processes the noise level indicator and learns time-related latent features to enhance the denoising capability. Given a graph G, let A, E IR N' Nx2 denote the one-hot version of the adjacency matrix at timestep i, where the row vector a."" e {0, 1)2 is a 2-dimensional one-hot encoding of the existence of the edge between node and node j. N the number nodes in the graph. Let X [Xi. .N] IR. denote the node features of the original graph, where d denotes the number of feature dimensions, X2 E IR denotes the d- d-dimensional feature of the node We construct X N x2d, where Xj 2d is the concatenation of node feature X; and Xj. the noise level indicator. An MLP module
Specifically, we use a diagonal matrix 3,- I RR Nxx1 will process the time-related information and output a tensor MLP(3, I) R N
Let Min. in = C,, ,, MLP(B. I)) E R N (2d+3) as the input of PPGN model. The output tensor of PPGN is A E R Nx1N11 where each element [Ablis represents the probability of q(a (a The formulation of PPGN is as follows,
PGNN M m))
Toout C(M in)
C(Min) Concat( (Bacat((Baor Ba o....... i.),
(12)
(Ba-10... MM in).... (M)) (
Each B, is a powerful layer that maps the input tensor to a tensor NxNxh We concatenate d outputs of these powerful layers and obtain tensor C(M,,) (n) E (d) The final Tout is MLP module that maps the input tensor to the space of NxNx1, Lout NxNx(dk) N We take the output of the PPGN model as the dense adjacency matrix as mentioned in Sec. 4.1.
D.2 Counterfactual Explanation Generation
The output of PPGN model A/ PGNN(M R NxN1 is taken as the dense adjacency matrix for the counterfactual explanation, where each element indicates the probability of the corresponding edge in the final counterfactual explanation. To obtain the discrete adjacency matrix and backpropagate the gradients, we utilize the Conerete relaxation of the Bernoulli distribution via
Bernoulli(p) v of (logp p - log(1 - p) + log u - log(1 - u))) u Uniform (0, 1),
where is temperature for the Concrete distribution and is the sigmoid function. Then, we create discrete adjacency matrix by Ao[is] Bernoulli(AA [t]]), where [ij] denotes the ij-th element in the corresponding matrix. Once the denoising model is well trained, we can generate counterfactual explanation given any noisy graph G, the node feature X, and noisy indicator t. In the explanation stage, let Go denote the given graph to be explained, we randomly add noise Go and create noisy version. We utilize the well-trained denoising model to output a dense adjacency matrix A/. The reparametrization trick is not applied in the inference stage. We directly sample [ijj]] Bernoullis Bernoulli(A([tj] and construct the final counterfactual explanation. One may also calculate average Ai by denoising from multiple noisy versions G, with different noisy level indicators t.
17

---

D.3 Simplified Loss Function
Early efforts on denoising diffusion models mainly reconstruct each G:-1 from G.. However, poses a challenge to the training stability due to the dependence of Gt-1 on the sampled diffusion trajectories and the intrinsic noise of G.-1. The simplified loss was first proposed by [48], which is defined as
simple
1 Go) log Pa (Go G.).
Instead of reconstructing intermediate noisy graphs, the simplified loss directly pushes toward the terminal clean graph Go. which improves both the training stability and training efficiency. In this work, we also target at recovering the final counterfactual graphs Go with each noisy graph G,, Moreover, we emphasize more challenging denoising tasks at larger timesteps by adding the weight 1 2 Be + to each step.
D.4 Model-level Explanation Generation
Algorithm Reverse Sampling for Model-level Explanation
Require: number of nodes N, number of candidates K, static GNN f. Diffusion Process g(-).
Denoising Model po(-)
1: Sample an Erdös Sedōss-Rényi Rényi graph GT Bx.1/2
2: for = do
3: Sample Goo. Go, ~ po(Gool?); = 1, 1,... K}
4: Compute Prob[k] f(Go,k) for k= 1,... K
5: Select Go,5 with the highest Probli]
6: Temporary explanation Go := Go.j
7: Sample G (()))
8: end for
9: return G
Alg. shows the multi-step reverse sampling algorithm for model-level explanations. Let N denote the number of nodes in the desired model-level explanation. We first generate a pure random graph Gy Bx,1/2- Given the noisy graph Gi,, the denoising model predicts the distribution of the clean graphs by po We sample K candidates from the distribution of the clean graphs by Go ~ Pe GG))GF), with k 1,... K, and refer the well-trained GNN to select the optimal one with the highest explanation confidence (i.e., f(C.) Regularization constraints can be plugged into this step further guarantee the desired properties of the generated explanation [16], egg, sparsity, explanation size, connectivity incentive, etc. We nominate the optimal Čo.j as the temporary explanation Go- Then, Go is transformed to noisy graphs by forward diffusion process, i.e., G ((G.-1/Co)) We repeat the process for T times until we obtain the terminal Gjj as the model-level explanation.
D.5 Unification of D4Explainer
The unification of D4Explainer lies in the same diffusion process and denoising model for different explanation scenarios. The differences between D4Explainer on counterfactual and model-level explanation tasks are (1) loss function and (2) reverse sampling process. Specifically, the loss function for the model-level explanation task does not contain Lef, which is designed to ensure the counterfactual property. Moreover, reverse sampling process in the model-level explanation tasks utilizes multiple-step sampling increase the explanation confidence score of generated model-level explanations. Moreover, the flexibility in the loss function and reverse sampling process enable D4Explainer to tackle other related explanation scenarios, such instance-level factual explanation.
18

---

Table 6: Statistics of the eight datasets and test performance of the GNN model trained for each
dataset. "_" means that there is no ground- truth motif in the dataset
BA-Shapes
Tree-Cycle
Tree-Grids
Cornell
BA-3Motif
Mutag
BBBP
NCTI
# of Nodes (avg.)
700
871
1231
183
21.92
30.32
25.95
29.87
of Edges (avg.)
4110
1942
3130
280
29.51
30.77
24.06
32.30
of Graphs
1
3000
4337
20399
4110
of Classes
4
2
2
5
3
2
2
2
Motif
house
cycle
grid
house/cycle/grid GCN
Target GNN
GCN
GCN
GCN
EGNN
GIN
GCN 0.85
GCN
Test accuracy
0.99
0.98
0.95
0.83
0.93
0.87
0.83
E Experiments
E.1
Dataset
In this work, use four synthetic datasets: BA-shapes, Tree-Cycle, Tree-Grids, and BA-3Motif to evaluate the efficacy the proposed D4Explainer the node-classificaton task, the graph consists of base graph, which is randomly attached by different motifs, e.g,, house, grid, cycle. The task is to determine whether or not the node is a part of the motif. For the graph classification task, each graph consists of a base graph randomly attached by type of motif. The task is to classify what type of motifs the graph contains.
We also test D4Explainer over real-world datasets, Cornell, Mutag, BBBP, and NCI1. Mutag, BBBP and NCII are molecular datasets where each graph labeled as either having a specific chemical property or not. For Mutag, the mutagenicity of a molecule is linked to the presence of electron- attracting elements combined with nitro groups (such as NO2). Additionally, molecules containing three or more fused rings are more likely to be mutagenic compared to those with one or two rings [64]. Cornell webpage dataset introduced by [52]. Nodes are web pages, and edges are hyperlinks between them. Node features are oog-offwordss representations of web pages. Nodes are classified
into one of five categories: Students, Projects, Courses, Faculty, and Staff. Cornell is a highly heterophilous dataset, i.e., the adjacent nodes tend to have different features and labels, which further poses a challenge to the explanation task. Nonetheless, there is no explicit motif that leads to specific class in real-world datasets. The statistical information of all datasets is summarized in Table 6. We use different types of target GNNs to evaluate the performance of D4Explainer including GCN, GIN, and EGNN. The last row shows the test accuracy of the target GNN. Each target GNN achieves more than 80% accuracy over the test dataset.
E.2 Metrics
We use the following metrics to evaluate the generated explanations, where the modification rate (MR) our proposed adjustment the sparsity metric used in previous works [13, 36].
Counterfactual Accuracy (CF-ACC) [13] measures whether the explainer can generate effective counterfactual explanations. It is formulated the proportion of generated explanations that change the model's prediction.
CF-ACC
-1(6-= Yo.),
(13)
191
GPEG
where G the original graph, G the generated counterfactual explanation regarding Go G is the test dataset and [g] denotes the size of G. Yo is the label of G predicted by the target GNN f. 1(-) is the indicator function to check whether Ýς- equals to Ýç.. Since we aim to generate counterfactual explanations, higher CF- FC-ACC is better.
Fidelity [3, 36] quantifies the change in predicted probability over the original class. It is
formulated as
1
Σ [[G]) [(G9))))]])]]] GeEg
Fidelity
(14)
G
where [V] denotes the probability output of the model f for graph G over class Y. higher fidelity score indicates better counterfactual explanations.
19

---

Modification ratio is the proportion of changed edges:
(# of deleted edges # of added edges)
(15)
E
where |E] is the number of edges in the original graph. For baseline models that only consider deleting edges, MR can be easily adjusted to the proportion deleted edges with respect to the original graph, which is the sparsity metric used in prior works [1],
E.3
Model Parameters
Table 7: Optimal parameters for each dataset
num hidden
num layers in PPGN
batch size
alpha
BA-shapes
64
0.005
Tree-Cycle
64
6
32
0.1
Tree-Grids
128
32
0.05
Cornell
128
6
4
0.05
BA-3Motif
128
32
0.05
Mutag
64
6
2 0.001
BBBP
128
16
0.005
NCI1
128
6
32
0.01
In the implementation, we need to perform multi-step diffusion. We uniformly sample Bg in the range of [0, 0.5] to control the level noise and generate the graph G2 with the corresponding level of noise. Given each G2, the denoising model is trained to recover the clean graph Go- During the training stage,
optimizer and ExponentialL.R [66] the scheduler. Table 7 shows the optimal numbers of hidden units, layers in PPGN, batch size, and the regularization coefficient for each dataset. We run 1500 epochs and the initial learning rate 10-3 across all datasets.
employ Adam [65]
E.4 In-distribution Evaluation
MMD (Maximum Mean Discrepancy) is metric used to compare the distance between two prob- ability distributions. In the context of graph statistics, MMD can be used to compare the degree distribution, cluster coefficient distribution, and spectrum distribution. MMD is also widely used for accessing the distribution-leamingg ability of graph generative models [61, 19, 20, 62, 44].
A graph's 's degree distribution represents the frequency of nodes with different degree values in the graph. The clustering coefficient a node a measure of the node's s local clustering or the fraction of triangles that the node participates in. Spectrum distribution refers to the distribution of eigenvalues of the adjacency matrix or Laplacian matrix of a graph, which can be used to study the graph's 's structure and dynamics. The MMD between two sets of samples from distributions and can be formulated as
MMD (pllg) Ex,x-plk(z, v)1 (k,, v)] 2Ex-p.y-qlkC [k(x, v)
(16)
where (ax, 3) denotes the kernel function. Following the in-distribution evaluation setting in [61, 19, 20, 62, 44J. we use Gaussian Earth Mover's Distance kernel to compute the MMDs of degree distributions, clustering coefficients, and spectrum distributions. Complete MMD results are shown in Table 8.
E.5 Diversity Evaluation
Figure shows the generated counterfactual examples for BA-shapes, Tree-Cycle, Tree-Grid, and BA-3Motif. The graphs in the first row are the original graphs to explain. The second row shows counterfactual examples generated by CF-GNNExplainer. The last two rows show two types of counterfactual examples generated by D4Explainer. Labels at the bottom right indicate the motif contained the graph. We find that the easiest way to generate counterfactual explanations is to destroy the original motif by deleting essential edges, which call "corruption".
20

---

Table 8: MMD distances between the generated explanations and test graphs. We report MMD distances of degree distributions (Deg.), cluster coefficients (Clus.) ), and spectrum distributions (Spec.). Sum. means the summation of the previous three metrics. We bold the smallest value and underlined the second-best value in each column.
Modies
Deg.
Spec.
Spec.
Spec.
Sum.
Deg.
Clus.
Sprc.
RandoanCaser
0.2555
0.0574
0,0552
0.3442
0.1595
0,0247
0.0417
0.2257
0.1693
0,0072
0,0997
0.2162
0.1847
1,9799
0,0404
22020
GNNExplainz
0.2565
0.0503
0.0531
0.3500
0.3614
0.002
0.0409
0..3025
0.1615
0.0000
0.6955
0.3012
0.1577
0.0085
0.0455
0.1957
SAEsplanse
0.2431
0,0005
0.0554
0.3073
0,8940
0.002
0.0112
0.1364
0.1594
0.0632
0.0422
0.2005
0,189
0,000
0.948
0.3300
GradCam
0.2224
0.0525
0.0530
0.3558
0.3122
0.005
0.0155
0.1621
0.0699
0.0026
0.0344
0.1109
0.1635
0,000
6.404
0.3945
KGtappainer
0.2474
0.0435
0.833
0.3883
0.129
0.0000
00411
0.790
0/988
0.0000
01286
01196
0.4388
0,000
0.096
0.4655
PORsppaaner
0.3489
0.000
0.0628
0.395
0.3475
09415
01999
0.3014
0/018
01805
0.445
01997
0,000
1406
0.3355
PGMExxllaies
0.2493
0.0246
0.0543
0.3252
0.0000
00002
0.8199
0.2221
0.1916
0,0003
0.003
0.2322
0.2199
0.0000
0.004
0.2603
CXPluin
0.2355
0.8412
0.0533
0.3303
0.1734
12706
0.847
1,4557
0.1768
0.0001
0,094
0.2163
0.1629
0,0001
0.0444
0.2034
CP GNNiExplatter
0.1662
0.0366
0.031
0.2526
0.112
0,0000
010100
0.552
0.070
0.001
0,0955
1.12
0J224
0.000
0:044
0.1629
D4Fxplainssr(sms)))
0,0000
0.833
0.0861
0.1006
0.0000
0.8353
0.135
Node Classification
nodes with dfferent labels
nodos to explan
Graph Classification
nodes with different
BA-shapes
Tree-Cycle
BA-3Motil
orginal graph
rydl
Counterfactual Example
(CF @NNEetaanee
Grrpttion
Dample (DMEsplained)
remrator
Simpptor
compton
Counterfactual Example [p(teplaine)
ergiinal edges
addid edges
edgas
Figure 8: Counterfactual explanations generated by CF-GNNExplainer and D4Explainer over four datasets. The labels at the bottom right represent the type of generated counterfactual explanations. CF-GNNExplaienr can only corrupt the original motif, while D4Explainer can corrupt the original motif and create the counterfactual motif.
Analysis. We observe from Figure 8 that the previous explainer alters the model's prediction by corrppting the original motif as its counterfactual explanation. Moreover, in the explanation task for node classification, previous explainers tend to remove the connection between the node to be explained and its neighbors. For example, in the second row of BA-shapes, Tree-Cycle, and Tree-Grid, CF-GNN- -xpiinaaap deletes the edges between the blue node and its neighboring nodes. One possible reason is that the isolated node cannot receive the messages from its neighbors with the well-trained GNN, thus naturally becoming an out-of-distribution sample and degrading the model's prediction confidence. Instead, D4Explainer generates counterfactual explanations not only by destroying the original motif but also by creating the truly counterfactual motifs, as shown in the last row of Figure 8. It is noticeable that D4Explainer can identify the counterfactual motif and complete that based on the original graph, which is hardly achieved by previous methods that only consider the edge deletion.
E.6 Complexity and Inference Time Evaluation
The computation of the loss function involves four steps. (1) uniformly sample from [0, [0, (2) apply forward diffusion process g GG), (3) calculate Po G.) via the denoising network and (4) sample counterfactual graphs from po Gul Gt). Let N denote the number of nodes in the original graph. The time complexity is O(1) for Step(1) ) and ( for Step(2) and ( for Step(3) due to the matrix multiplication. Step(4) results in time complexity of O(N2) for sampling. Overall, the time complexity of D4Explainer is mainly determined by the denoising network.
To empirically evaluate the efficiency of D4Explaienr, we conduct the runtime comparison between D4Explainer and baselines. The results are shown in Table 9. Except for PGExplainer, other baselines reported in Table 9 are non-generative, that is, the model optimizes explanation for input instances
21

---

one by one during the inference stage. Therefore, these models require more time to generate one explanation and become less efficient. On the contrary, D4Explainer incorporates the generative graph distribution learning into the optimization objective and captures the underlying distribution of the explanation graphs over the entire dataset. Consequently, D4Explainer is relatively efficient during the inference stage.
Table 9: Runtime analysis of all baselines. We compute mean/std values of inference time to generate explanations for single instance
GNNEsplainer
IGExphniner
PGExplainer
PGMEsplainer
CXPlain
CE-GNNExplainer
D4Explainer
Tree-Cyele
1.36740.023
2.684+0.368
0.028+0.007
1.145+0.012 1.57640.038
1.277402777 1.842403200
2.637+0,540 2.741#0.536
0.022+0.000 002
Mulag 1.49240.037
3.157=0.454
0.035#0.005
0.030=000006
E.7
Robustness Evaluation
Mutag
BBBP
NC11
190
90
Top-ot Arcusscy (8)
Top- Aocurny (%5
60
Noise (%)
10
Noise
Debrdarne (Dum)
PSWbxdene
GAbxdare
Figure 9: Robustness performance of all methods. The modification ratio is controlled as 20% across all methods.
Following previous setup [36], we identify the K most relevant edges in the original counterfactual explanation and compute the fraction of these edges present in the explanation of its noisy version, denoted by Top-K K Accuracy. We apply noise by randomly adding removing edges with probability σ. We restrict that o < 0.1, as the noise of larger a may cause the noisy graph to switch the predicted label. Top-K accuracy w.r.t. noise levels over three molecular datasets are shown in Fig. 9, As shown in Figure we observe that D4Explainer outperforms all baselines on BBBP and performs comparably to PGExplainer Mutag and IGExplainer on NCI1. To keep consistent, we show Top-K Accuracy with noise levels from 0% to 10% for three datasets. However, with more than 5% noise, only 65% of perturbed noisy graphs have the same label the original one for NCII, much smaller than BBBP and Mutag. The high sensitivity of NCII to noise explains the drop in robustness as noise increases past 0.05. Overall, results in Figure 9 demonstrate D4Explainer's s strong ability to generate consistently effective counterfactual explanations despite the noise.
E.8 Model-level Explanation
Table 10 shows the quantitative comparison of probability and density in the model-level explanations generated by XGNN and D4Exlainer. We generate 100 model-level explanations for each dataset and compute the average probability (i.e., explanation confidence) and average density. As can be observed from Table 10, D4Explainer outperforms XGNN over both metrics on four datasets in general. Particularly. D4Explainer achieves almost 100% explanation confidence on three synthetic datasets with an appropriate N, i.e., the number of nodes in the desired explanation. In many real- world scenarios, the ground truth model-level explanations are not unique. That is, we can hardly know the exact discriminative graph structure and feature that the GNNs learned for prediction. The appropriate N might require domain sppeiff knowledge, while we can test with different N and select the one that achieves the highest explanation confidence.
Table 11 reports the sensitivity of K and T, which denote the number of candidates and number of iterations in the reverse sampling algorithm for model-level explanations, respectively. Similarly, we utilize probability and density to quantitatively measure the properties of the generated explanations.
22

---

Table 10: Quantitative comparison in terms of probability and density with different numbers of
nodes
BA-3Motif 5
Mutag
Tree-Grid 8
Cree-Cyycl 5
nodes
10
7
D4Explainer
Prob.
0.997
1.000
0.998
0.832
0.856
0.920
0.832
0.994
0.991
0.991
0.995
0.989
Density
0.313
0.327
0.294
0.278
0.327
0.315
0.369
0.372
0.379
0.400
0.381
0.343
Prob.
0.632
0.883
0.834
0.523
0.824
0.875
0.752
0.836
0,902
0.968
0.989
0.992
XGNN
Density
0.552
0.444
0.433
0.537
0.479
0.437
0.421
0.406
0.439
0.400
0.390
0.367
Table 11: Hyperparameter sensitivity in model-level explanation generation
BA-3Motif (N=5)
Mutag (N=6)
Tree-Grid (N=9)
Tree-Cyele (N=6)
hyper- Spprr-parameters
Prob.
Density
Prob.
Density
Prob.
Density
Prob.
Density
(1) K 10, 50
0.899
0,3152
0.799
0.314
0.901
0.400
0.987
0.372
(2) K 20, = 10
0.798
0.3277
0.524
0,284
0.897
0.383
0.991
0,388
(3) K 20, T
0.967
0.3126
0.812
0,295
0.994
0.372
0.994
0.361
(4) K 20, TO 100
0.997
0.3133
0.832
0.278
0.972
0.427
0.992
0.325
(5) K 30,
0.972
0.2972
0.823
0.287
0.994
0.355
0.997
0.361
From the table, we can observe that when T small (e.g.. T 10), the probability p is relatively lower (see experiments 2, 3, 4), indicating that the quality of the generated model-level explanations sub-optimal. This result further emphasizes the effectiveness of multi-step sampling. which progressively increases the explanation confidence. Additionally, we observe that the probability p increases as K increases, under the same conditions of T (see experiments I, 3, 5). This suggests that increasing the number of candidates helps to obtain a good-quality model-level explanation within fewer steps. In our implementation, we ensure K > 20 and T > 50 by default for a balance between the quality and time complexity.
F Discussions
Limitations. In this paper, we explore the application of denoising diffusion models in generating counterfactual and model-level explanations for Graph Neural Networks (GNNs). While D4Explainer has shown promising results in terms of various metrics, including explanation accuracy, robustness, diversity, etc. It still introduces unique challenges and limitations. Firstly, the computational complex- ity of training D4Explainer on large-scale graph structures poses scalability concerns. Additionally, the reliance on the underlying GNN architecture can limit the generalizability of the explanations across different GNN models. Furthermore, in model-level explanations, high-quality explanations rely on an appropriate number of nodes, which might require domain-specific knowledge.
Broader Impacts. The social impact of this work is twofold. On one hand, the ability to generate counterfactual explanations for GNNs can enhance transparency and interpretability, empowering users to understand and trust the decisions made by these models. By shedding light on the features and interactions that contribute to specific predictions, this work can facilitate the identification of biases, discriminatory patterns, and vulnerabilities present GNNs. However, it is crucial to acknowledge the limitations and potential risks associated with using generated explanations as they might not always capture the complete causal relationships present in complex graph structures. Consequently, relying solely on these explanations may lead to unintended consequences, such as reinforcing existing biases or making incorrect assumptions about the model's behavior.
Future Works. Moving forward, several important avenues for future research emerge from this study. First, addressing the scalability challenges associated with training denoising diffusion models on large-scale graph structures is crucial direction. Developing efficient training algorithms, exploring parallelization strategies, and investigating graph-specific optimizations can significantly improve the applicability of D4Explainer real-world large-scale graphs. Secondly, an interesting future direction is to consider the node attributes and edge attributes during the explanation generation, egg., by performing diffusion processes over continuous features. Moreover, future work should address the potential risks associated with unintended consequences, biases, and misuse of explanations. Developing guidelines and frameworks for responsible and accountable use of generated explanations is crucial, particularly in high- stakes domains such as healthcare, finance, and criminal justice.
23


Reviews:
[{"review_id": "xqHmyMU9qz", "reviewer": "Reviewer_XFfB", "summary": "A diffusion-based approach for generating instance-level\ncounterfactual explanations and model-level explanations of GNN\npredictions.", "questions": "In the model-level explanation setting, I wonder whether there is a way to predict the best number of nodes for the generated explanation.", "limitations": "Lack of management of node/edge attributes, which the authors do recognize and leave as future work.\n\nLack of automated selection of number of nodes in model-level explanations (same as XGNN).", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The approach improves over existing counterfactual-based solutions by\nallowing both addition and removal of nodes, thus better retaining\nin-distribution of explanations.\n\nAn extensive experimental evaluation shows consistent and substantial improvements over existing alternatives.", "weaknesses": "The presentation is a bit condensed, so that one has to jump to the\nsupplementary to get a clear understanding of the novelty of the\nproposed solution wrt the works it builds upon.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comment on the proposed model and extensive experiments. We sincerely appreciate the feedback and suggestions you provided, which help us to further improve the quality of this paper. We have addressed each point and potential concern you raised as follows.\n>The presentation is a bit condensed. A comprehensive understanding of the novelty requires referring to the supplementary material.\n\nThanks for your constructive suggestions. We agree that in our initial version, some differences between the proposed solution and previous works were elaborated in the appendix, due to the space limitations. In our revised version, we ensure each point of our novelty and distinctions from previous works is well explained and mentioned in the main text. \n>Is there a way to predict the best number of nodes for generated model-level explanation?  Lack of automated selection of the number of nodes in model-level explanation.\n\nThanks for the interesting question. Actually, automatically generating a succinct model-level explanation without a predefined number of nodes is feasible with the current framework. To achieve that, we can put the number of non-isolated nodes into the selection policy. In this way, D4Explainer tries to find the best tradeoff between confidence score and explanation size. However, we tend to believe this manner will diminish the diversity of the generated explanations and easily generate wrong or weak results, which explains why we set the number of nodes as an initialization hyper-parameter, as XGNN[1]. \n\nActually, the definition of the “best” number of nodes in model-level explanations is ambiguous. In many real-world scenarios, the ground truth model-level explanations are not unique. That is, we can hardly know the exact discriminative graph structure/feature that the GNNs learned for prediction [2]. Table 10 in Appendix E.8 shows that model-level explanations with different numbers of nodes can achieve comparably high confidence scores, which indicates that D4Explainer always tries to find the best graph structures and discriminative features for a certain class, given any number of nodes in the desired explanation. \n\n[1]XGNN: Towards Model-Level Explanations of Graph Neural Networks\n\n[2]GNNInterpreter: A Probabilistic Generative Model-Level Explanation for Graph Neural Networks \n\n>Lack of management of node/edge attributes.\n\nTheoretically, the diffusion process and denoising network can indeed be applied to both discrete adjacency matrix and continuous/categorical node/edge attributes. We’ve discussed the discrete diffusion process in the main text and Appendix C.1, which can be applied to process discrete adjacency matrices and categorical features. We also discussed the continuous diffusion process in Appendix C.2, which can be used to manage continuous node/edge features. As mentioned in L132-133, we mainly focus on discrete graph structures and investigate how they affect counterfactual properties and model-level explanation in this work. If time allows, we are more than happy to incorporate empirical results with node/edge attributes in our final version to enrich the analysis.\n\n\n\n\n"}, {"review_id": "9We7I8s175", "reviewer": "Reviewer_MWPm", "summary": "The increasing application of graph neural networks (GNNs) has sparked significant interest in understanding their explainability. In this paper, the authors introduce D4Explainer, a method that provides in-distribution GNN explanations for both counterfactual and model-level explanation scenarios. By integrating generative graph distribution learning into an optimization objective, D4Explainer accomplishes two things: 1) It generates a set of diverse counterfactual graphs that comply with the in-distribution property for a given instance; and 2) It identifies the most discriminative graph patterns that contribute to a specific class prediction, thereby providing model-level explanations.", "questions": "1. I’m interested in understanding the technical contributions of the proposed method, especially the generation of counterfactual graphs via a diffusion process. Which aspects of Figure 2a derive from existing works and which are novel proposals in this work?\n2. Why is the GIN used solely for the Mutag dataset, whereas the GCN is utilized for all other tasks?", "limitations": "The authors have outlined a future research direction.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is generally well-written, clearly outlining the motivations and intuitions behind the proposed method.\n2. The concept of employing a diffusion process for graph explanation is both timely and effective.\n3. The superior performance of the proposed method is well substantiated by diverse experiments in different settings.", "weaknesses": "1. Certain technical details are glossed over. While the page limit is a concern, it's crucial that the key concepts are well explained in the main paper to ensure it is self-contained. For instance, even though Equation (2) is one of the key components of the proposed method, its derivation process and the meanings of the terms within the equation are not clearly presented, which could potentially pose challenges for those who are not experts in graph diffusion.\n2. The authors claim that D4Explainer is a unified framework for counterfactual explanation and model-level explanation, but the resulting approaches seem distinct and separate. I would expect more justification on why D4Explainer can be considered a unified framework, and if it could be further extended to tackle other related tasks in graph explanation.\n3. Considering the high complexity of the proposed method, an ablation study (or a hyperparameter sensitivity study) would be beneficial for the counterfactual explanation task to provide a clearer understanding of the success of the proposed method. In addition, how did the authors tune hyperparameters (apart from just T and K) for their approach and the competitors?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for constructive feedback and positive comments on paper writing, architecture efficiency, and extensive experiments. We address the potential concerns as follows.\n>Certain technical details are glossed over. Some equations may not be elaborated in detail.\n\nThanks for bringing this up. We agree we didn’t elaborate on each equation in detail due to the space limitation, leaving them in the appendix. In our revised version, we will add more descriptions and detailed derivations for important equations to ensure each key concept is well explained and elaborated. \nFor your reference, we will add the following content to explain Eq(2). In Eq(2), the objective of $L_{dist}$ is to guarantee the proximity of generated counterfactual explanations to the original graph. Let $A_0$ and $A_t$ denote the corresponding adjacency matrix of graph $G_0$ and $G_t$. $L_{dist}$ is equivalent to the expected cross-entropy loss between $A_0$ and $A_t$, where $G_t$ follows the distribution of $q(G_t|G_0)$. \n>Why is D4Explainer a unified framework for graph explanation tasks? Is there any further extension to other related tasks?\n\nThe unification of D4Explainer lies in the same diffusion process and denoising model for different explanation scenarios. The differences between D4Explainer on counterfactual and model-level explanation tasks are (1) loss function and (2) reverse sampling process. Specifically, the loss function for the model-level explanation task does not contain $L_{cf}$, which is designed to ensure the counterfactual property. Moreover, the reverse sampling process in the model-level explanation tasks utilizes multiple-step sampling to increase the confidence score of generated model-level explanations. \n\nWe believe the flexibility in the loss function and reverse sampling process does not diminish the overall unification of D4explainer in different explanation tasks. Instead, these flexibilities enable D4Explainer to tackle other related explanation scenarios. For example, D4Explainer is able to generate instance-level factual explanation, where we aim to generate a succinct and sparse explanatory subgraph $G_e\\sim p(G_t)$ from a given instance $G_0$. Accordingly, $L_{dist}$ can be replaced with the cross-entropy loss between $G_0$ and $G_0-p(G_t)$, which ensures the generated subgraph is sufficiently succinct. $L_{cf}$ can be modified to accommodate the factual explanation scenario easily.\n\nApart from flexible loss functions and reverse sampling strategy, D4Explainer uses a fixed diffusion process and denoising network, enabling a wide range of application scenarios with minimal modifications.\n>About our ablation studies and hyperparameter tuning. \n\nWe report the search ranges of main hyperparameters in counterfactual explanations as follows. The best hyperparameters have been reported in Appendix E.3. Our ablation studies also show that increasing the number of layers and number of hidden units in the denoising network potentially improves the model performance, while the model performance is not sensitive to dropout rate and alpha. \n| hyperparameter            | search range                              |   |\n|---------------------------|-------------------------------------------|---|\n| number of layers in PPGN  | 3,4,5,6,7,8                               |   |\n| number of hidden features | 32, 64, 128                               |   |\n| alpha                     | 1e-3, 5e-3, 1e-2, 5e-2, 0.1, 0.5, 1, 2, 5 |   |\n| dropout rate              | 0.1, 0.2, 0.3,0.4,0.5                     |   |\n| learning rate             | 1e-4, 5e-4, 1e-3, 5e-3, 1e-2, 5e-2        |   |\n\n>What are the technical contributions of D4Explainer? Which aspects of Figure 2a are novel in this work?\n\nIn Figure 2a, we adapt the diffusion process defined in [1,2] to the graph explanation task. We also carefully designed the denoising model to process the noise level indicator which enhances its denoising capability for graph data specifically (refer to Appendix D.1 for more details). Another core innovation in Figure 2a lies in the loss function. We proposed an effective loss function for generating high-quality and in-distribution explanations for GNNs by incorporating graph distribution learning into the optimization objective. We believe these are non-trivial contributions to the graph explainability literature.\n\n[1]DiGress: Discrete Denoising diffusion for graph generation \n\n[2]Diffusion Models for Graphs Benefit From Discrete State Spaces\n\n>Why is the GIN used for Mutag and GCN used for others?\n\nIn our implementation, vanilla GCNs do not perform well (<80% accuracy) on the Mutag dataset, Therefore, we use GIN as the target GNN on the Mutag dataset following previous works [1], which achieves 87% in terms of classification accuracy.  We believe a well-performing GNN can also benefit the explanation quality, while it’s worth mentioning that our explainability framework is architecture-agnostic. Thanks again for lighting up this interesting question.\n\n[1]Reinforced Causal Explainer for Graph Neural Networks\n"}, {"review_id": "0oQ7WB7jvB", "reviewer": "Reviewer_Tz8g", "summary": "The authors propose to apply discrete denoising diffusion as a technique for generating counterfactual and model-level graph explanations. From my understanding, the proposed method focuses solely on incorporating graph structure while **disregarding node features**. Additionally, the authors claim that the proposed framework can generate in-distribution graphs, unlike other methods. However, their evaluating method primarily involves comparing graph statistics, which may not necessarily capture the true essence of graph distribution.", "questions": "1) Figure 1 does not make sense to me. Why t-sne projections have been used for graph structure data and how this is related to ood is not clear to me. The misclassification might not necessarily be related to the ood effect. An empirical study or a theoretical proof is needed?\n\n2) What is the guarantee for the diffusion base generator, to generate in-distribution graphs? Citation or empirical results are needed. **Note:** Even when considering the MDD statistics, which I believe is an inadequate metric for evaluating this, the generated graphs may not be in-distribution depending on the dataset, e.g. Mutag.\n\n3) Number of modifications is not a useful metric as does not consider the size of the graph. Why not consider sparsity?\n\n4) Why not AUC? What about the ACC for the simulated graphs? Please also include validity and proximity metrics. \n\n5) all results need std as well.  \n\n6) MDD table does not support the claim of the paper and it is not clear in which dataset the model works better. \n\n7) Model-level explanation experiments are not included that many datasets and in their current shape mostly can be seen as an ablation study. More baselines are needed for this part as well. \n\n8) It is not clear to me how the input is perturbed for robustness evaluation.\n\n9) It is not clear to me how the method can conditionally generate counterfactual explainability for the property of the interest.", "limitations": "The authors mention some of the limitation of the proposed method.", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "- The main strength of the paper is applying the diffusion model to generate both counterfactual and model-level explanations.\n\n- Contemplating the possibility of the subgraph being ood is interesting. However, without supporting evidence, it remains a hypothesis without validation in this context.", "weaknesses": "- The paper has the tendency to include a few unsupported and wrong claims. A few examples are provided here:\n\n1) [D4Explainer explores counterfactual explanations in a larger search space than prior works by allowing adding edges, which provides a new perspective of generating counterfactual explanation] -> This is not true as a few of the previous works already are based on other kinds of generative models, for example, CLEAR (NeurIPS 2022).\n\n2) The authors referred to the CLEAR paper (reference # 37) [only edge deletion is allowed as in the previous paradigm [36, 13, 37]] which is a wrong claim. \n\n3) There is no theoretical or empirical proof that the generated graphs are in-distribution. [However, generating in-distribution graphs is challenging, due to the difficulty of encoding complex graph distributions, e.g., the distribution of node degrees, cycle counts and edge homogeneity.] As far as I can say, there is a difference between graph distribution and the distribution of graph statistics such as node degrees.  Empirical evidence or a citation is needed before being on top of this assumption. \n\n- The explainability model cannot handle node attributes and only focus on graph structure. \n\n- The other weakness of the paper is related works. The authors not only need to include previous works such as CLEAR as a baseline but also need to include them in their related works discussing the difference between the proposed framework and the existing ones. \n\n- Evaluation is not satisfying as it does not include std. Apart from that, the authors did not more informative metrics to compare the models including Validity, Proximity, as well as causality which are important for counterfactual explainability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your valuable time and efforts in reviewing this paper. We would like to answer potential concerns as follows.\n>Previous generative works, eg. CLEAR. \"[Only edge deletion is allowed as in the previous paradigm[36,13,17] is a wrong claim.”\n\nWe apologize for the misstatement here. Yes, CLEAR allows edge addition and we actually obtained many insights from it. We will revise the statements as follows. “Previous counterfactual explainers typically only consider edge deletion, leaving the effect of edge addition underexplored.” Here we would like to emphasize the core innovation of our D4Explainer. \n- The denoising strategy enhances the robustness of generated explanations, which is not studied in CLEAR. \n- Our model is the first to explore both instance-level and model-level explanations within a unified framework, while CLEAR focuses on counterfactual explanations only. \n- We included high-level understandings of how edge addition helps to create truly counterfactual motifs in Sec.5.2.2 which is not discussed in detail in CLEAR.\n\n>No theoretical/empirical proof for in-distribution graph.\n\nWe note our investigations focus on assessing how discrete graph structures affect explainability properties. To support this claim, we have conducted extensive in-distribution evaluations in Sec 5.2.1. Previous studies[1] have shown that MMD is a versatile and necessary metric for comparing graph distribution. MMD is also widely used for accessing the distribution-learning ability of graph generative models in this field [2,3,4]. We believe our empirical results in Sec 5.2.1 can sufficiently demonstrate the in-distribution property in terms of graph structures. \n>The model cannot handle node attributes.\n\nThe diffusion process and denoising network can indeed be applied to continuous/categorical node/edge attributes. We've discussed these aspects in detail in Appendix C.1 for discrete diffusion and C.2 for continuous attributes. We believe it would be an interesting future extension to consider node/edge attributes.\n\n>Include CLEAR as a baseline\n\nWe tried to involve CLEAR as a baseline but we didn’t find any publicly available codes for CLEAR before the submission deadline. Now we reproduce CLEAR based on the original paper and report preliminary results as follows (complete results in our revised version). We hope that the experimental results could improve your confidence in our work.\n|             | Tree-Cycle  | BBBP        |\n|-------------|-------------|-------------|\n| D4Explainer | 0.917±0.012 | 0.781±0.024 |\n| CLEAR       | 0.834±0.010 | 0.754±0.035 |\n\n| BBBP        | Deg.   | Clus.  | Spec.  | Sum.   |\n|-------------|--------|--------|--------|--------|\n| D4Explainer | 0.0530 | 0.0000 | 0.0331 | 0.0861 |\n| CLEAR       | 0.0782 | 0.0000 | 0.0329 | 0.1109 |\n>Evaluation does not include std. \n\nWe will include std results in Appendix in our revised version.\n\n>Why t-sne and how this is related to ood issue?\n\nIn Figure 1, each point represents the t-sne projection of the embedding of a node to explain. The embedding of a valid counterfactual example should be close to the average embedding of all instances across the dataset. However, we observe that the embedding of the example generated by CF-GNNExplainer falls far from the distribution, which raises suspicions of being OOD.\n>What is the guarantee for in-distribution graphs?\n\nThe key guarantee lies in their training process. The model learns to reverse the diffusion process and denoise the initially added noise. This is done by using maximum the likelihood of generating the original graph. Many previous studies [2,3,4] demonstrate the distribution-learning ability of diffusion-based generators.\n>Number of modifications does not consider the graph size. Why not sparsity?\n\nWe actually use the Modification ratio (MR), which considers the size of the original graphs. Sparsity is usually used in factual explainability. In counterfactual explanation tasks, we emphasize the modification is minimal based on the given graph.\n>Why not AUC? What about ACC, validity, proximity and causality metrics?\n\nWe have reported both AUC and ACC metrics in the paper. We report the accuracy curve over 10 different MRs (in Figure 4). We report the area under this curve as CF-ACC AUC in Table 1. We believe validity is the same as the accuracy and proximity w.r.t. graph structure is similar to the MR in our submission. The only difference is that we normalize it by the number of original edges. Regarding casualty, we think it is not a widely used metric in counterfactual explanations, since it highly depends on domain knowledge and dataset description. \n>Model-level experiments do not include that many datasets and baselines.\n\nThe datasets for model-level explanations actually include cycle, ring, grid, house motifs, and real-world datasets (e.g. mutag), which cover almost all motifs tested in previous works. We also tried to involve GNNInterpreter as a baseline, but there are no publicly available codes yet. \n>How is the input perturbed?\n\nFor robustness evaluation, we randomly add new edges or delete original edges with probability $\\sigma$ over any pair of nodes in the original graph.\n> How can the method conditionally generate counterfactual explainability?\n\nIn the counterfactual explanation task, we design $L_{cf}$ to ensure the counterfactual property, which minimizes the likelihood of the generated explanation being predicted as the original label. $L_{cf}$ can also be easily extended to ensure other target properties of interest by replacing  $\\hat{Y}_{G_0}$.\n\n[1]Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions\n\n[2]DiGress: Discrete Denoising diffusion for graph generation\n\n[3]Diffusion Models for Graphs Benefit From Discrete State Spaces\n\n[4]GraphGUIDE: interpretable and controllable conditional graph generation with discrete Bernoulli diffusion\n"}, {"review_id": "sFQMaR2kXS", "reviewer": "Reviewer_ofrf", "summary": "D4Explainer contributes to the important problem of explainable Graph Neural Networks (GNNs) and offers in-distribution GNN explanations for both counterfactual and model-level scenarios. The incorporation of generative graph distribution learning into the optimization objective allows D4Explainer to generate diverse counterfactual graphs and identify discriminative graph patterns, enhancing the reliability and informativeness of the explanations. The empirical evaluation results are promising. Clarifications are needed to help readers better understand D4Explainer.\n\nI have read the author’s rebuttal and raised the overall rating.", "questions": "1. Figure 1 is confusing. In the top plot, if each dot is a “node to explain”, why the blowouts of the counterfactual examples are graphs? Does the distances between a “node” and its counterfactual examples indicate anything?\n2. Eq (3) seems computationally expensive. The complexity analysis in Section 4.3 doesn't seem to provide a full scale analysis.\n3. The derivation of Eq (4) needs explanations.\n4. The model-level explanation “aims to identify recurring and discriminant graph patterns that can trigger a specific prediction from the model f”. It is not clear if the calculation of G^m ensures “recurring”. Under what circumstance, this is true with high probability. \n5. Since “proximity to the original graph” is used in deriving the proposed approach, why not report an index based on “proximity to the original graph” in the experimental results, instead of MMD?\n6. \"We report AUC values computed over 10 modification ratios from 0 to 0.3\". What does this mean: Several modification ratios were tried, and the best result is reported?", "limitations": "This is a rather basic research. No potential negative societal impact is detected.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "D4Explainer integrates graph diffusion into producing counterfactual and model-level explanations. While individual components have been widely investigated, their combination in making GNN more explainable is new.\nThe experimental results are good.\nThe manuscript is in general well organized.", "weaknesses": "Some parts of the manuscript need clarifications (see Questions).\nThe experiments were only conducted on small graphs (<=10 nodes).\nEdges are constrained to have categorical properties. In many real applications, they are associated with continuous attributes. \nNode addition/deletion is considered. \nIt is unclear how much effect N (number of nodes in graph) has on experimental results. How to choose a right N?\nThe “Explanation Diversity Evaluation” only offers a few examples, not even at the qualitative level. It is not clear how generalizable those observations are.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your valuable feedback, which significantly improves the quality of this work. We would like to answer the questions you raised as follows.\n\n> The experiments were only conducted on small graphs (<=10 nodes)\n\nWe prudently clarify that the above comment is incorrect. Please refer to Table 6 in Appendix E.1 for dataset information. For the node classification task, the graph datasets we used in experiments contain hundreds of nodes and thousands of edges. For graph classification tasks, we are using molecular datasets with around 30 nodes. Our choice of datasets is in line with the prevailing standard in the field of GNN explainability.\n\n>Edges are constrained to have categorical properties\n\nThe diffusion process and denoising network can indeed be applied to continuous/categorical node/edge attributes. We've discussed these aspects in detail in the main text (including Appendix C.1 for discrete diffusion and C.2 for continuous attributes). We believe it would be an interesting future extension to consider node/edge attributes.\n\n>How much effect N has on experimental results? How to choose the right N? \n\nGood question! In the model-level explanation task, we conduct a hyper-parameter sensitivity analysis on $N$ in Table 10 in Appendix E.8. We observe that model-level explanations with different $N$ can achieve comparably high confidence scores, which indicates that D4Explainer can find the best graph structures, given any $N$. We have to admit that choosing the right/best $N$ requires domain-specific knowledge. In many real-world scenarios, the ground truth model-level explanations are not unique. A simple and feasible method is testing with different numbers of nodes $N$ and selecting the ones that achieve high confidence scores.\n\n> The “explanation diversity evaluation” only offers a few examples. How generalizable?\n\nComplete results of “Explanation Diversity Evaluation” are given in Figure 8 in Appendix E.5. Diversity is generalizable for different labels on four synthetic datasets. Here, we would like to emphasize the core insight is that D4Explainer is able to detect the distinctive motifs and truly convert the original motifs to counterfactual ones, instead of simply destroying the original motifs.\n\n>Clarification to Figure 1\n\nIn Figure 1, each point represents the t-sne projection of the embedding of a node to explain, which is computed over its computational graph. Counterfactual examples generated by explainers are essentially the modified computational graph of the node to explain, which leads to the different prediction labels on the central node. The embedding distance between two nodes reflects how similar or proximate with each other.  The embedding of a valid counterfactual explanation should be close to the average embedding of all instances across the dataset. In Figure1, the embedding of the counterfactual example generated by CF-GNNExplainer falls far from the average embedding of in-distribution instances with the Cycle label. We believe it is a result of the OOD effect, making the explanations unreliable. \n\n>What is the complexity of Eq (3) and full complexity analysis?\n\nThanks for the question! The time complexity of Eq(3) involves (1)uniformly sample t from [0,T] (2) applying forward diffusion process $q(G_t|G_0)$ and (3) calculate $p_{\\theta}(G_0|G_t)$ via the denoising network and (4) sample counterfactual graphs from $p_{\\theta}(G_0|G_t)$. Let $N$ denote the number of nodes in the original graph. The time complexity is $O(1)$ for Step1 and $O(N^2)$ for step 2. For step3, we analyze the complexity in Sec 4.3. Step 4 results in a time complexity of $O(N^2)$ for sampling. Overall, the time complexity of Eq(3) is mainly determined by the denoising network. We have revised Sec 4.3 to involve a complete discussion on computational complexity.\n\n>Explanations to the derivation of Eq (4)\n\nThanks for bringing this up! To provide a high-level understanding of Eq(4), the generation path from $G_t^r$ to $G_{t-1}^r$ is actually $G_t^r \\rightarrow G_0 \\rightarrow G_{t-1}^r$, where the first step is controlled by $p_{\\theta}( G_0 |G_{t}^r)$. Second step is controlled by $q(G_{t-1}^r|G_0)$. $f(C|G_0)$ is multiplied to condition the reverse sampling on the target C. We will provide complete derivation and proof in Appendix in our revised version. \n\n>How does the calculation of G^m ensure “recurring” property? \n\nThe calculation of $G^m=argmax_G P_f(C_i|G)$ is first proposed in the previous work [1] and then widely used in the problem formulation. We agree that the “recurring” property can hardly be guaranteed by the above calculation alone. In D4Explainer framework, the “recurring” property is actually ensured by incorporating graph distribution learning into the optimization objective. In addition, we employ a candidate selection strategy to ensure the generated model-level explanation maximizes the likelihood of $P_f(C_i|G_m)$. We will clarify more about how we ensure “recurring” property in Sec.4.2 in our revised version.\n\n[1]XGNN: Towards Model-Level Explanations of Graph Neural Networks\n\n>Clarification to “We report AUC values computed over 10 modification ratios from 0 to 0.3”\n\nSince the accuracy of counterfactual explanations is sensitive to the modification ratio, we report the accuracy curve over 10 different modification ratios from 0 to 0.3 (See Figure 4). We denote the area under this curve as CF-ACC AUC and report the results in Table 1.\n\n>Why not report an index based on “proximity to the original graph”, Instead of MMD?\n\n“Proximity” actually can be represented by the “Modification Ratio”, which has already been adopted as a metric in our experiments. Compared with “Proximity”, MMD is a global metric, which measures the distribution distance between two sets of graph samples, instead of two graphs. \n"}]

Author rebuttal:

Meta-review: All reviewers tend towards accepting the paper. The strengths of the paper are improvements over existing counterfactual-based solutions by allowing both the addition and removal of nodes, extensive experiments, and a novel and interesting idea of using diffusion for explaining GNNs.
Decision: Accept (poster)