Year: 2021

Abstract:
Explainability of graph neural networks (GNNs) aims to answer “Why the GNN made a certain prediction?”, which is crucial to interpret the model prediction. The feature attribution framework distributes a GNN’s prediction to its input features (e.g., edges), identifying an influential subgraph as the explanation. When evaluating the explanation (i.e., subgraph importance), a standard way is to audit the model prediction based on the subgraph solely. However, we argue that a distribution shift exists between the full graph and the subgraph, causing the out-ofdistribution problem. Furthermore, with an in-depth causal analysis, we find the OOD effect acts as the confounder, which brings spurious associations between the subgraph importance and model prediction, making the evaluation less reliable. In this work, we propose Deconfounded Subgraph Evaluation (DSE) which assesses the causal effect of an explanatory subgraph on the model prediction. While the distribution shift is generally intractable, we employ the front-door adjustment and introduce a surrogate variable of the subgraphs. Specifically, we devise a generative model to generate the plausible surrogates that conform to the data distribution, thus approaching the unbiased estimation of subgraph importance. Empirical results demonstrate the effectiveness of DSE in terms of explanation fidelity.

text: Explainability of graph neural networks (GNNs) aims to answer “Why the GNN made a certain prediction?”, which is crucial to interpret the model prediction. The feature attribution framework distributes a GNN’s prediction to its input features (e.g., edges), identifying an influential subgraph as the explanation. When evaluating the explanation (i.e., subgraph importance), a standard way is to audit the model prediction based on the subgraph solely. However, we argue that a distribution shift exists between the full graph and the subgraph, causing the out-ofdistribution problem. Furthermore, with an in-depth causal analysis, we find the OOD effect acts as the confounder, which brings spurious associations between the subgraph importance and model prediction, making the evaluation less reliable. In this work, we propose Deconfounded Subgraph Evaluation (DSE) which assesses the causal effect of an explanatory subgraph on the model prediction. While the distribution shift is generally intractable, we employ the front-door adjustment and introduce a surrogate variable of the subgraphs. Specifically, we devise a generative model to generate the plausible surrogates that conform to the data distribution, thus approaching the unbiased estimation of subgraph importance. Empirical results demonstrate the effectiveness of DSE in terms of explanation fidelity.

heading: 1 INTRODUCTION
text: Explainability of graph neural networks (GNNs) (Hamilton et al., 2017; Dwivedi et al., 2020) is crucial to model understanding and reliability in real-world applications, especially when about fairness and privacy (Ying et al., 2019; Luo et al., 2020). It aims to provide insight into how predictor models work, answering “Why the target GNN made a certain prediction?”. Towards this end, a variety of explainer models are proposed for feature attribution (Selvaraju et al., 2017; Ying et al., 2019; Luo et al., 2020; Vu & Thai, 2020), which decomposes the predictor’s prediction as contributions (i.e., importance) of its input features (e.g., edges, nodes). While feature attribution assigns the features with importance scores, it redistributes the graph features and creates a new distribution different from that of the original full graphs, from which a subgraph is sampled as the explanation. Such sampling process is referred to as feature removal (Covert et al., 2020).
Then, to assess the explanatory subgraph, the current evaluation frameworks use the feature removal principle — (1) only feed the subgraph into the target predictor, discarding the other features; (2) measure the importance of the subgraph based on its information amount to recover the model’s prediction. Such subgraph-prediction correlations uncovered by the removal-based evaluator should offer a faithful inspection of the predictor’s decision-making process and assess the fidelity of the explainers reliably.
However, feature removal brings the out-of-distribution (OOD) problem (Frye et al., 2020; Chang et al., 2019; Lukas Faber, 2021): the distribution shift from full graphs to subgraphs likely violates underlying properties, including node degree distribution (Leskovec et al., 2005) and domain-specific constraints (Liu et al., 2018) of the full graphs. For example, graph properties of chemical molecules, such as the valency rules, impose some constraints on syntactically valid molecules (Liu et al., 2018); hence, simply removing some bonds (edges) or atoms (nodes) creates invalid molecular subgraphs that never appear in the training dataset. Such OOD subgraphs could manipulate the predictor’s
Under review as a conference paper at ICLR 2022
𝑮: Full Graph 𝑮𝒔: Subgraph 𝒀: Predicate Logits
𝐬 𝓖
House Cycle Crane
0.21
0.70
Target Predictor
Crane
𝓖Cycle House𝓖𝒔𝟏𝑫: Distribution Shift 𝓖𝒔𝟐 𝒔∗
𝐬
Front-door Adjustment𝓖𝒔𝟐𝓖𝒔𝟏
(a) Feature Removal to Evaluate Explanatory Subgraph Gs
𝑮: Full Graph 𝑮𝒔: Subgraph 𝒀: Predicate Logits
𝐬 𝓖
House Cycle Crane
0.21
0.70
Target Predictor
Crane
𝓖Cycle House𝓖𝒔𝟏𝑫: Distribution Shift 𝓖𝒔𝟐 𝒔∗
𝐬
Front-door Adjustment𝓖𝒔𝟐𝓖𝒔𝟏
(b) SCM I
Figure 1: (a) A real example in TR3. The GNN predictor classifies the full graph as ‘House”. On subgraphs Gs1 and Gs2, the prediction probabilities of being “House” are respectively 0.21 and 0.70. (b) The structural causal model represents the causalities among variables: G as the input graph, D as the unobserved distribution shift, Gs as the explanatory subgraph, and Y as the model prediction.
outcome arbitrarily (Dai et al., 2018; Zügner et al., 2018), generates erroneous predictions, and limits the reliability of the evaluation process.
Here we demonstrate the OOD effect by a real example in Figure 1a, where the trained ASAP (Ranjan et al., 2020) predictor has classified the input graph as “House” for its attached motif (see Section 4 for more details). On the ground-truth explanation Gs1, the output probability of the “House” class is surprisingly low (0.21). While for Gs2 with less discriminative information, the outputs probability of the “House” class (0.70) is higher. Clearly, the removal-based evaluator assigns the OOD subgraphs with unreliable importance scores, which are unfaithful to the predictor’s decision.
The OOD effect has not been explored in evaluating GNN explanations, to the best of our knowledge. We rigorously investigate it from a causal view (Pearl et al., 2016; Pearl, 2000; Pearl & Mackenzie, 2018). Figure 1b represents our causal assumption via a structural causal model (SCM) (Pearl et al., 2016; Pearl, 2000), where we target the causal effect of Gs on Y . Nonetheless, as a confounder between Gs and Y , distribution shift D opens the spurious path Gs ← D → Y . By “spurious”, we mean that the path lies outside the direct causal path from Gs to Y , making Gs and Y spuriously correlated and yielding an erroneous effect. And one can hardly distinguish between the spurious correlation and causative relations (Pearl et al., 2016). Hence, auditing Y on Gs suffers from the OOD effect and wrongly evaluates the importance of Gs.
Motivated by our causal insight, we propose a novel evaluation paradigm, Deconfounded Subgraph Evaluator (DSE), to faithfully measure the causal effect of explanatory subgraphs on the prediction.
𝑮: Full Graph 𝑮𝒔: Subgraph 𝒀: Predicate Logits
𝑮𝐬𝑮 𝒀
𝑫
𝑮𝒔∗
𝑮𝐬𝑮 𝒀
𝑫
Front-door Adjustment
reliably and further guide explainers to generate faithful explanations.
In a nutshell, our contributions are: • From a causal perspective, we argue that the OOD effect is the confounder that causes spurious
correlations between subgraph importance and model prediction.
• We propose a deconfounding paradigm, DSE, which exploits the front-door adjustment to mitigate the out-of-distribution effect and evaluate the explanatory subgraphs unbiasedly.
• We validate the effectiveness of our framework over various explainers, target GNN models, and datasets. Significant boosts are achieved over the conventional feature removal techniques. Code and datasets are available at: https://anonymous.4open.science/r/DSE-24BC/.

heading: 2 A CAUSAL VIEW OF EXPLANATION EVALUATION
text: Here we begin with the causality-based view of feature removal in Section 2.1 and present our causal assumption to inspect the OOD effect in Section 2.2.

heading: 2.1 PROBLEM FORMULATION
text: Without loss of generality, we focus on the graph classification task: a well-trained GNN predictor f takes the graph variable G as input and predicts the class Y ∈ {1, · · · ,K}, i.e., Y = f(G). Generation of Explanatory Subgraphs. Post-hoc explainability typically considers the question “Why the GNN predictor f made certain prediction?”. A prevalent solution is building an explainer model to conduct feature attribution (Ying et al., 2019; Luo et al., 2020; Pope et al., 2019). It decomposes the prediction into the contributions of the input features, which redistributes the probability of features according to their importance and sample the salient features as an explanatory subgraph Gs. Specifically, Gs can be a structure-wise (Ying et al., 2019; Luo et al., 2020) or featurewise (Ying et al., 2019) subgraph of G. In this paper, we focus on the structural features. That is, for graph G = (N , E) with the edge set E and the node set N , the explanatory subgraph Gs = (Ns, Es) consists of a subset of edges Es ⊂ E and their endpoints Ns = {u, v|(u, v) ∈ Es}. Evaluation of Explanatory Subgraphs. Insertion-based evaluation by feature removal (Covert et al., 2020; Dabkowski & Gal, 2017) aims to check whether the subgraph is the supporting substructure 1 that alone allows a confident classification. We systematize this paradigm as three steps: (1) divide the full graph G into two parts, the subgraph Gs and the complement Gs; (2) feed Gs into the target GNN f , while discarding Gs; and (3) obtain the model prediction on Gs, to assess its discriminative information to recover the prediction on G. Briefly, at the core of the evaluator is the subgraphprediction correlation. However, as discussed in Section 1, the OOD effect is inherent in the removal-based evaluator, hindering the subgraph-prediction correlation from accurately estimating the subgraph importance.

heading: 2.2 STRUCTURAL CAUSAL MODEL
text: To inspect the OOD effect rigorously, we take a causal look at the evaluation process with a Structural Causal Model (SCM I) in Figure 1b. We denote the abstract data variables by the nodes, where the directed links represent the causality. The SCM indicates how the variables interact with each other through the graphical definition of causation:
• G→ Gs ← D. We introduce an abstract distribution shift variable D to sample a subgraph Gs from the edge distributions of the full graph G.
• Gs → Y ← D. We denote Y as the prediction variable (e.g., logits output), which is determined by (1) the direct effect from Gs, and (2) the confounding effect caused by D. In particular, the former causation that led to the result is the focus of this work.
We suggest readers to refer to Appendix A where we offer an elaboration of D. With our SCM assumption, directly measuring the importance of explanatory subgraphs is distracted by the backdoor path (Pearl, 2000), Gs ← D → Y . This path introduces the confounding associations between Gs and Y , which makes Gs and Y spuriously correlated, i.e., biases the subgraph-prediction correlations, thus making the evaluator invalid. How to mitigate the OOD effect and quantify Gs’s genuine causal effect on Y remains largely unexplored in the literature and is the focus of our work.

heading: 3 DECONFOUNDED EVALUATION OF EXPLANATORY SUBGRAPHS
text: In this section, we propose a novel deconfounding framework to evaluate the explanatory subgraphs in a trustworthy way. Specifically, we first leverage the front-door adjustment (Pearl, 2000) to formulate a causal objective in Section 3.1. We then devise a conditional variational graph auto-encoders (CVGAE) as the effective implementation of our objective in Section 3.2.
1We focus on insertion-based evaluation here while we discuss deletion-based evaluation in Appendix C.

heading: 3.1 FRONT-DOOR ADJUSTMENT
text: To the best of our knowledge, our work is the first to adopt the causal theory to solve the OOD problem in the explanation evaluation of GNNs. To pursue the causal effect of Gs on Y , we perform the calculus of the causal intervention P (Y = y|do(Gs = Gs)). Specifically, the do-calculus (Pearl, 2000; Pearl et al., 2016) is to intervene the subgraph variable Gs by cutting off its coming links and assigning it with the certain value Gs, making it unaffected from its causal parents G and D. From inspection of the SCM in Figure 1b, the distribution effect D acts as the confounder between Gs and Y , and opens the backdoor path Gs ← D → Y . However, as D is hardly measurable, we can not use the backdoor adjustment (Pearl, 2000; Pearl et al., 2016) to block the backdoor path from Gs to Y . Hence, the causal effect of Gs on Y is not identifiable from SCM I.
However, we can go much further by considering SCM II in Figure 2 instead, where a mediating variable G∗s is introduced between Gs and Y :
• Gs → G∗s . G∗s is the surrogate variable of Gs, which completes Gs to make them in the data distribution. First, it originates from and containsGs. Specifically, it imagines how the possible full graphs should be when observing the subgraph Gs. Second, G∗s should follow the data distribution and respect the inherent knowledge of graph properties, thus no link exists between D and G∗s . • G∗s → Y . This is based on our causal assumption that the causality-related information of Gs on Y , i.e., the discriminative information for Gs to make prediction, is well-preserved by G∗s . Thus, with the core of Gs, G∗s is qualified to serve as the mediator which further results in the model prediction.
With SCM II, we can exploit the front-door adjustment (Pearl, 2000; Pearl et al., 2016) instead to quantify the causal effect of Gs on Y . Specifically, by summing over possible surrogate graphs G∗s of G∗s , we chain two identifiable partial effects of Gs on G ∗ s and G ∗ s on Y together:
P (Y |do(Gs = Gs)) = ∑ G∗s P (Y |do(G∗s = G∗s ))P (G∗s = G∗s |do(Gs = Gs))
= ∑ G∗s ∑ G′s P (Y |G∗s = G∗s , Gs = G′s)P (Gs = G′s)P (G∗s = G∗s |do(Gs = Gs))
= ∑ G∗s ∑ G′s P (Y |G∗s = G∗s , Gs = G′s)P (Gs = G′s)P (G∗s = G∗s |Gs = Gs), (1)
Specifically, we have P (G∗s|do(Gs = Gs)) = P (G∗s|Gs = Gs) as Gs is the only parent of G∗s . And we distinguish the Gs in our target expression P (Y |do(Gs = Gs)) between G′s, the latter of which is adjusted to pursue P (Y |do(G∗s = G∗s )). With the data of (Gs,G∗s ) pairs, we can obtain P (Y |G∗s = G∗s , Gs = G′s) by feeding the surrogate graph G∗s into the GNN predictor, conditional on the subgraph G′s; similarly, we can estimate P (Gs = G′s) statistically; P (G∗s = G∗s |Gs = Gs) is the conditional distribution of the surrogate variable, after observing the subgraphs. As a result, this front-door adjustment yields a consistent estimation of Gs’s effect on Y and avoids the confounding associations from the OOD effect.

heading: 3.2 DEEP GENERATIVE MODEL
text: However, it is non-trivial to instantiate G∗s and collect the (Gs,G∗s ) pairs. We get inspiration from the great success of generative models and devise a novel probabilistic model, conditional variational graph auto-encoder (CVGAE), and an adversarial training framework, to generate G∗s .
Conditional Generation. Inspired by previous works (Thomas N. Kipf, 2016; Liu et al., 2018), we model the data distribution via a generative model gθ parameterized by θ. It is composed of an encoder q(Z|G,Gs) and a decoder p(G∗s |Z). Specifically, the encoder q(Z|G,Gs) embeds each node i in G with a stochastic representation zi, and summarize all node representations in Z:
q(Z|G,Gs) = N∏ i=1 q(zi|G,Gs), with q(zi|G,Gs) = N (zi | [µ1i,µ2i], [ σ21i 0 0 σ22i ] ) (2)
where zi is sampled from a diagonal normal distribution by mean vector [µ1i,µ2i] and standard deviation vector diag(σ21i,σ 2 2i); µ1 = fµ(G) and logσ1 = fσ(G) denote the matrices of mean
vectors µ1i and standard deviation vectors logσ1i respectively, which are derived from two GNN models fµ and fσ on the top of the full graph G; similarly, µ2 = fµ(Gs) and logσ2 = fσ(Gs) are on the top of the subgraph Gs. Then, the decoder p(G∗s |Z) generates the valid surrogates:
p(G∗s |Z) = N∏ i N∏ j p(Aij |zi, zj), with p(Aij = 1|zi, zj) = fA([zi, zj ]), (3)
whereAij = 1 indicates the existence of an edge between nodes i and j; fA is a MLP, which takes the concatenation of node representations zi and zj as the input and outputs the probability of Aij = 1.
Leveraging the variational graph auto-encoder, we are able to generate some counterfactual edges that never appear in G and sample G∗s from the conditional distribution p(G∗s |Z), formally, G∗s ∼ p(G∗s|Z). As a result, P (G∗s = G∗s |Gs = Gs) in Equation 1 is identified by p(G∗s |Z). The quality of the generator directly affects the quality of the surrogate graphs, further determines how well the frontdoor adjustment is conducted. Next, we will detail an adversarial training framework to optimize the generator, which is distinct from the standard training of VAE.
Adversarial Training. To achieve high-quality generation, we get inspiration from the adversarial training (Goodfellow et al., 2020; Yue et al., 2021) and devise the following training objective:
min θ LVAE + γLC +max µ ωLD, (4)
where γ, ω are trade-off hyper-parameters. These losses are carefully designed to assure the generation follows the data distribution. Next, we will elaborate on each of them.
LVAE = −EG [Eq(Z|G,Gs)[log p(Ĝs|Z)]] + βEG [DKL(q(Z|G,Gs)||p(Z))], (5) We first minimize the β-VAE loss(Higgins et al., 2017), and the first term is the reconstruction loss responsible to predict the probability of edges’ existence; the second term is the KL-divergence between the variational and prior distributions. Here we resort to the isotropic Gaussian distribution p(Z) = ∏ i p(zi) = ∏ iN (zi|0, I) as the prior. β reweighs the KL-divergence, which promises to learn the disentangled factors in Z (Higgins et al., 2017; Yue et al., 2021; Suter et al., 2019).
Moreover, we highlight the class-discriminative information in Z, by encouraging the agreement between graph representations with the same class compared to that with different classes. Technically, the contrastive loss is adopted:
LC = −EG [log ∑ G′∈B+ exp (s(zG , zG′)/τ)∑
G′′∈B+∪B− exp (s(zG , zG′′)/τ) ], (6)
where zG is the representation of G that aggregates all node representations Z together; s is the similarity function, which is given by an inner product here; τ is the temperature hyper-parameter; B+ is the graph set having the same class to G, while the graphs involved in B− have different classes from G. Minimizing this loss enables the generator to go beyond the generic knowledge and uncover the class-wise patterns of graph data.
Besides, we introduce a discriminative model dµ to distinguish the generated graphs. Specifically, we set it as a probability-conditional GNN (Fey & Lenssen, 2019) parameterized by µ. It takes a graph as input and outputs a score between 0 to 1, which indicates the confidence of the graph being realistic. Hence, given a real graph G with the ground-truth label y, we can use the generator gθ to generate G∗s . Then the discriminator learns to assign G with a large score while labeling G∗s with a small score. To optimize the discriminator, we adopt the Wasserstein GAN (WGAN) (Martin Arjovsky, 2017) loss:
LD = EG [Ep(G∗s |Z)[d(G, y)− d(G ∗ s , y)− λ(||∇G∗s d(G ∗ s , y)||2 − 1)2]], (7)
where d(G∗s , y) is the probability of generating G∗s from the generator; λ is the hyper-parameter. By playing the min-max game between the generator and the discriminator in Equation 4, the generator can create the surrogate graphs from the data distribution plausibly.
Subgraph Evaluation. With the well-trained generator g∗θ whose parameters are fixed, we now approximate the causal effect of Gs on Y . Here we conduct Monte-Carlo simulation based on g∗θ to sample a set of plausible surrogate graphs {G∗s} from p(G∗s |Z). Having collected the (Gs,G∗s ) data, we can arrive the estimation of Equation 1.

heading: 4 EXPERIMENTS
text: We aim to answer the following research questions:
• Study of Explanation Evaluation. How effective is our DSE in mitigating the OOD effect and evaluating the explanatory subgraph more reliably? (Section 4.2)
• Study of Generator. How effective is our CVGAE in generating the surrogates for the explanatory subgraphs and making them conform to the data distribution? (Section 4.3)

heading: 4.1 EXPERIMENTAL SETTINGS
text: Datasets & Target GNNs. We first train various target GNN classifiers on the three datasets:
• TR3 is a synthetic dataset involving 3000 graphs, each of which is constructed by connecting a random tree-shape base with one motif (house, cycle, crane). The motif type is the ground-truth label, while we treat the motifs as the ground-truth explanations following Ying et al. (2019); Yuan et al. (2020a). A Local Extremum GNN (Ranjan et al., 2019) is trained for classification.
• MNIST superpixels (MNISTsup) (Monti et al., 2017) converts the MNIST images into 70,000 superpixel graphs. Every graph with 75 nodes is labeled as one of 10 classes. We train a Splinebased GNN (Fey et al., 2018) as the classifier model. The subgraphs representing digits can be viewed as human explanations. • Graph-SST2 (Yuan et al., 2020b) is based on text sentiment dataset SST2 (Socher et al., 2013)
and converts the text sentences to graphs where nodes represent tokens and edges indicate relations between nodes. Each graph is labeled by its sentence sentiment. The node embeddings are initialized by the pre-trained BERT word embeddings (Devlin et al., 2018). Graph Attention Network (Veličković et al., 2018) is trained as the classifier.
Ground-Truth Explanations. By “ground-truth”, we follow the prior studies (Ying et al., 2019; Yuan et al., 2020a; Luo et al., 2020) and treat the subgraphs coherent to the model knowledge (e.g., the motif subgraphs in TR3) or human knowledge (e.g., the digit subgraphs in MNISTsup) as the ground-truth explanations. Although such ground-truth explanations might not fit the decision-making process of the model exactly, they contain sufficient discriminative information to help justify the explanations. Note that no ground-truth explanation is available in Graph-SST2.
Explainers. To explain the decisions made by these GNNs, we adopt several state-of-the-art explainers, including SA (Baldassarre & Azizpour, 2019), Grad-CAM (Selvaraju et al., 2017), GNNExplainer (Ying et al., 2019), CXPlain (Schwab & Karlen, 2019), PGM-Explainer (Vu & Thai, 2020), Screener (Anonymous, 2021), to generate the explanatory subgraphs. Specifically, top-15%, 20%, 20% of edges on the full graph instance construct the explanatory subgraphs in TR3, MNIST, and Graph-SST2, respectively. We refer readers to Appendix D for more experimental details.

heading: 4.2 STUDY OF EXPLANATION EVALUATION (RQ1)
text: Deconfounded Evaluation Performance. For an explanation Gs, the conventional removal-based evaluation framework quantifies its importance as the subgraph-prediction correlation, termed Impre(Gs) = f(Gs); whereas, our DSE framework focuses on the causal effect caused by Gs on Y which is computed based on Equation 1, and we denote it as Impdse(Gs) for short. These importance scores broadly aim to reflect the discriminative information carried by Gs. Thanks to the ground-truth knowledge available in TR3 and MNISTsup, we are able to get a faithful and principled
metric to measure the discriminative information amount — the precision Prec(Gs,G+s ) between the ground-truth explanation G+s and the explanatory subgraph Gs. This precision metric allows us to perform a fair comparison between Impre(Gs) and Impdse(Gs) via:
ρre = ρ([Prec(Gs,G+s )], [Impre(Gs)]), ρdse = ρ([Prec(Gs,G+s )], [Impdse(Gs)]), (8)
where ρ is the correlation coefficient between the lists of precision and importance scores. We present the results in Figure 4 and have some interesting insights:
• Insight 1: Removal-based evaluation hardly reflects the importance of explanations. In most cases, Prec(Gs,G+s ) is negatively correlated with the importance. This again shows that simply discarding a part of a graph could violate some underlying properties of graphs and mislead the target GNN, which is consistent with the adversarial attack works (Dai et al., 2018; Zügner et al., 2018). Moreover, the explainers that target high prediction accuracy, such as GNNExplainer, are easily distracted by the OOD effect and thus miss the important subgraphs.
• Insight 2: Deconfounded evaluation quantifies the explanation importance more faithfully. Substantially, ρdse greatly improves after the frontdoor adjustments via the surrogate variable. The most notable case is GNNExplainer in MNISTsup, where ρdse = 0.17 achieves a tremendous increase from ρdse = −0.11. Although our DSE alleviates the OOD problem significantly, weak positive or negative correlations still exist, which indicates the limitation of the current CVGAE. We leave the exploration of higher-quality generation in future work.
Revisiting & Reranking Explainers. Here we investigate the rankings of explainers generated from different evaluation frameworks, and further compute the Spearman rank correlations between these evaluation rankings and the reference rankings of explainers. Specifically, for TR3 and MNISTsup with ground-truth explanations, we regard the ranks w.r.t. precision as the references, while obtaining the reference of Graph-SST2 by a user study2. Such a reference offers the human knowledge for explanations and benchmarks the comparison. We show the results in Table 1 and conclude:
• Insight 3: DSE presents a more fair and reliable comparison among explainers. The DSEbased rankings are highly consistent with the references, while the removal-based rankings struggle to pass the check. In particular, we observe that for TR3, the unrealistic splicing inputs cause a plain ranking w.r.t. Impre. We find that various input subgraphs are predicted as cycle class. That is, the target GNN model is a deterministic gambler with serious OOD subgraphs. In contrast, DSE outputs a more informative ranking; For MNISTsup, GNNExplainer with the highest precision
270 volunteers are engaged, where each was asked to answer 10 questions randomly sampled from 32 movie reviews and choose the best explanations generated by the explainers. See Appendix E for more details.
Table 2: Importance scores or probabilities of subgraphs before and after feature removal.
TR3 MNISTsup Graph-SST2
Imp(G) or GMM(G) 0.958−0.520 0.982−0.574 35.3−11.3 Imp(G+s ) or GMM(Gs) 0.438 0.408 24.0
Table 3: Performances of Generators in terms of Validity and Fidelity.
TR3 MNISTsup Graph-SST2
Imp(G∗s) VAL↑ FID↓ Imp(G∗s) VAL↑ FID↓ GMM(G∗s) VAL↑ FID↓ Random 0.451 0.013 0.794 0.448 0.040 1.325 38.8 14.8 0.060 VGAE 0.469 0.031 0.754 0.205 -0.203 1.501 37.6 13.6 0.078 ARGVA 0.392 0.061 0.726 0.466 0.058 1.306 31.0 7.0 0.079 CVGAE 0.603 0.165 0.598 0.552 0.144 0.910 45.8 21.8 0.057
is overly underrated by the removal-based evaluation framework, but DSE justifies its position faithfully; For Graph-SST2, although the OOD problem seems to be minor, DSE can still achieve significant improvement.
Case Study. We present a case study in Graph-SST2 to illustrate how DSE mitigates the potential OOD problem. See Appendix F for another case study on TR3. In Figure 5, G is a graph predicted as “negative" sentiment. The explanatory subgraph Gs emphasizes tokens like “weak” and relations like “n’t→funny”, which is cogent according to human knowledge. However, its removal-based importance is highly underestimated as 0.385, possibly due to its disconnectivity or sparsity after feature removal. To mitigate the OOD problem, DSE samples 50 surrogate graphs from the generator, performs the frontdoor adjustment, and justifies the subgraph importance as 0.913, which shows the effectiveness of our DSE framework.
We also observe some limitations of the generator (1) Due to the limited training data, the generators only reflect the distribution of the observed graphs, thus making some
generations grammatically wrong. (2) The generations is constrained within the complete graph determined by the node set of the explanatory subgraph, thereby limits the quality of deconfounding. As we mainly focus on the OOD problem, we will leave the ability of the generator as future work.

heading: 4.3 STUDY OF GENERATORS (RQ2)
text: The generator plays an important role in our DSE framework, which aims to generate the valid surrogates conform to the data distribution. To evaluate the generator’s quality, we compare it with three baselines: a random generator, a variational graph auto-encoder (VGAE) (Thomas N. Kipf, 2016), and an adversarially regularized variational graph auto-encoder (ARGVA) (Pan et al., 2018). We perform the evaluation based on two metrics: (1) Validity. For the ground-truth explanations G+s that contains all discriminative information of the full graph G, the importance of its surrogate graph G∗s should be higher than itself. The difference between the two importance scores indicates the validity of the generator, thus we define VAL = EG [Imp(G∗s )− Imp(G+s )]. For Graph-SST2 where the class-wise features are intractable, we leverage the embeddings of training graphs and additionally train a Gaussian Mixture Model (GMM) as our distribution prior. Then, we compute the average loglikelihood of random subgraphs after in-filling, thus we have VAL = EGEGs∼Random(G)[GMM(G∗s )− GMM(Gs)]. (2) Fidelity. Towards a finer-grained assessment w.r.t. prediction probability of any random subgraphs, we adopt the metric following (Frye et al., 2021): FID = EGEGsEy|fy(G) − EG∗s [fy(G ∗ s )]|2. This measures how well the surrogates cover the target prediction distribution.
Before comparing different generators, we first compute the importance or probabilities of the graphs before and after feature removal, which are summarized in Table 2. When inspecting the Removal’s results without any in-fills, the OOD problem is severe: in TR3 and MNISTsup, the importance of ground-truth subgraphs only reaches 43.8% and 40.8%, respectively, which are far away from the
target importance of full graphs. Analogously in Graph-SST2. For the performance of the generators w.r.t. the two metrics, we summarize the average results over 5 runs in Table 3:
• The performance of the baselines are poor. This suggests that they can hardly fit the target conditional distribution.
• CVGAE outperforms other generators consistently across all cases, thus justifying the rationale and effectiveness of our proposed generator and adversarial training paradigm. For example, in TR3, CVGAE significantly increases the VAL scores and mitigates the OOD effect effectively.
Moreover, we conduct ablation studies and sensitivity analysis in Appendix G to better understand the model components and validate the effectiveness of the designed objective.

heading: 5 RELATED WORK
text: Post-hoc Explainability of GNNs. Inspired by the explainability in computer vision, Baldassarre & Azizpour (2019); Pope et al. (2019); Schnake et al. (2020) obtain the gradient-like scores of the model’s outcome or loss w.r.t. the input features. Another line (Luo et al., 2020; Ying et al., 2019; Yuan et al., 2020a; Yue Zhang, 2020; Michael Sejr Schlichtkrull, 2021) learns the masks on graph features. Typically, GNN-Explainer (Ying et al., 2019) applies the instance-wise masks on the messages carried by graph structures, and maximizes the mutual information between the masked graph and the prediction. Going beyond the instance-wise explanation, PGExplainer (Luo et al., 2020) generates masks for multiple instances inductively. Recently, researchers adopt the causal explainability (Pearl & Mackenzie, 2018) to uncover the causation of the model predictions.For instance, CXPlain (Schwab & Karlen, 2019) quantifies a feature’s importance by leaving it out. PGM-Explainer (Vu & Thai, 2020) performs perturbations on graph structures and builds an Bayesian network upon the perturbation-prediction pairs. Causal Screening (Screener) (Anonymous, 2021) measures the importance of an edge as its causal effect, conditional on the previously selected structures. Lately, SubgraphX (Yuan et al., 2021) explores different subgraphs with Monte-Carlo tree search and evaluates subgraphs with the Shapley value (Kuhn & Tucker, 1953).
Counterfactual Generation for the OOD Problem. The OOD effect of feature removal has been investigated in some other domains. There are generally two classes of generation (i) Static generation. For example, Fong & Vedaldi. (2017); Dabkowski & Gal (2017) adopted blurred input and random colors for the image reference, respectively. Due to the unnatural in-filling, the generated images are distributional irrespective and can still introduce confounding bias. (ii) Adaptive generation: Chang et al. (2019); Frye et al. (2021); Agarwal et al. (2019); Kim et al. (2020). The generators of these methods, like DSE, overcomes the defects aforementioned, which generates data that conforms to the training distribution. For example, in computer vision, FIDO (Chang et al., 2019) generates imagespecific explanations that respect the data distribution, answering “Which region, when replaced by plausible alternative values, would maximally change classifier output?”.
For the difference, firstly, DSE’s formulated importance involves additional adjustment on Gs and guarantees the unbiasedness of introducing the surrogate variable G∗s , which is commonly discarded by the prior works with in-fillings only. Specifically, we offer a comparison with FIDO in Appendix B. Secondly, the distribution of graph data is more complicated to model than other domains. And the proposed CVGAE is carefully designed for graph data, where the contrastive loss and the adversarial training framework are shown to be effective for learning the data distribution of graphs.

heading: 6 CONCLUSION
text: In this work, we investigate the OOD effect on the explanation evaluation of GNNs. With a causal view, we uncover the OOD effect — the distribution shift between full graphs and subgraphs, as the confounder between the explanatory subgraphs and the model prediction, making the evaluation less reliable. To mitigate it, we propose a deconfounding evaluation framework that exploits the front-door adjustment to measure the causal effect of the explanatory subgraphs on the model prediction. And a deep generative model is devised to achieve the front-door adjustment by generating in-distribution surrogates of the subgraphs. In-so-doing, we can reliably evaluate the explanatory subgraphs. As the evaluation for explanations fundamentally guides the objective in GNNs explainability, this work offers in-depth insights into the future interpretability systems.
ETHICS STATEMENT
This work raises concerns about the removal-based evaluation in the explainability literature and proposed Deconfounded Subgraph Evaluator. For the user study that involves human subjects, we have detailed the fair evaluation procedure for each explanation generated by the explainers in Appendix E. For real-world applications, we admitted that the modeling of the distribution shift could be a barrier to fulfill their evaluation faithfulness. However, as shown in the paper, improper evaluation under the OOD setting largely biases the inspection of the model’s decision-making process and the quality of explainers. Therefore, we argue that explainability should exhibit faithful explanation evaluation before auditing deep models’ actual decision-making process. And a wrongly evaluated explanation might do more significant harm than an incorrect prediction, as the former could affect the general adjustment (e.g., structure construction) and human perspective (e.g., fairness check) of the model.
REPRODUCIBILITY STATEMENT
We have made great efforts to ensure reproducibility in this paper. Firstly, we make all causal assumptions clear in Section 2.2, Section 3.1 and Appendix A. For datasets, we have released the synthetic dataset, which can be referred to the link in Section 1, while the other two datasets are publicly available. We also include our code for model construction in the link. In Appendix D, we have reported the settings of hyper-parameters used in our implementation for model training.

heading: B COMPARISON OF IMPORTANCE ESTIMATIONS
text: In this section, we compare our proposed estimation via front-door adjustment with the estimation in FIDO (Chang et al., 2019). We rephrased each estimation as
Impdse(Gs) = ∑ G∗s P (G∗s = G∗s | Gs = Gs)P (Y | G∗s = G∗s )
= ∑ G∗s P (G∗s = G∗s | Gs = Gs) ∑ G′s P (Y | G∗s = G∗s , Gs = G′s)P (Gs = G′s) (9)
and
ImpFIDO(Gs) = ∑ G∗s P (G∗s = G∗s | Gs = Gs)P (Y | G∗s = G∗s ) (10)
where DSE has alternatively adjusted on Gs (represented as G′s). To make it clear, we consider the underlined part of each equation. For Equation 9, we have
∑ G′s P (Y | G∗s = G∗s , Gs = G′s)P (Gs = G′s)
= ∑ G′s P (Y | G∗s = G∗s , Gs = G′s)P (Gs = G′s | G∗s = G∗s ) P (Gs = G′s) P (Gs = G′s | G∗s = G∗s )
= ∑ G′s P (Y,Gs = G′s | G∗s = G∗s ) P (Gs = G′s) P (Gs = G′s | G∗s = G∗s )
(11)
While for the formulation of Equation 10, we have
P (Y | G∗s = G∗s ) = ∑ G′s P (Y,Gs = G′s | G∗s = G∗s ) (12)
In the comparison of these two parts, we can see that Equation 12 is biased under our causal assumption. Intuitively, each contribution of the importance of G∗s on Y should be inversely proportional to the posterior probability, i.e., the probability of G′s given the observation G∗s . However, FIDO fails to consider the causal relation between Gs → G∗s , which biases tha approximation of the genuine causal effect under our causal assumption.
Back to our proposed estimation, as we have collected (Gs,G∗s )-pairs via Monte-Carlo simulation, thus additional adjustment on Gs (G′s) can be achieved via Equation 11.

heading: C DSE FOR DELETION-BASED EVALUATION
text: Based on the idea of deletion-based evaluation, we can instead use the average causal effect (Holland., 1988) (ACE) to look for a smallest deletion graph by conducting two interventions do(Gs = G) (i.e., , no feature removal) and do(Gs = G/s) where G/s denotes the complement of the explanatory graph Gs, meaning that the GNN input receives treatment and control, respectively. Formally, we have
Imp fid dse(Gs = Gs) = P (Y | do (Gs = G))− P ( Y | do ( Gs = G/s )) (13)
Then, we can similarly adjust for the individual terms as Equation 1, obtaining the unbiased importance value as the result of deletion-based evaluation.

heading: D EXPERIMENTAL DETAILS
text: In this paper, all experiments are done on a single Tesla V100 SXM2 GPU (32 GB). The well-trained GNNs used in our experiments achieve high classification accuracies of 0.958 in TR3, 0.982 in MNISTsup, 0.909 in Graph-SST2.
Now We introduce the model construction of the proposed generator. The encoder used is Crystal Graph Convolutional Neural Networks (Xie & Grossman, 2018), which contains three Convolutional layers. The encode dimensions in Tr3, MNISTsup, Graph-SST2 datasets are respectively 256, 64, 256. For decoder, we adopt two fully connected layers with ReLU as activation layers, where the numbers of neurons are the same with the encode dimensions. Next, we summarize the pseudocodes for the Adversarial Training in Algorithm 1.
Algorithm 1 Generative Adversarial Training. All experiments in the paper used the default values m = 256, α = 2× 10−4, β = 1× 10−4, ω = λ = 5, τ = 0.1 Require: Pr, real graphs’ distribution. r, masking ratio. Require: m, batch size. α, learning rate. β, γ, λ, ω, τ , hyper-parameters.
1: µ← µ0; θ ← θ0 2: while loss in Equation (4) is not converged do 3: # Discriminator’s training 4: Sample {G(i)}mi=1 ∼ Pr a batch from the real graphs. 5: Randomly generate broken graphs {G(i)s }mi=1 from {G(i)}mi=1 with masking ratio r. 6: Embed the nodes through encoder q(Z|{G(i)s ,G(i)}mi=1) 7: Decode the edge probabilities and sample in-fill graphs {Ĝs̄}mi=1 ∼ p(Ĝs̄ | Z) 8: Compute Discriminator’s loss from Equation 7. 9: Update parameter µ with back-propagation.
10: # Generator’s training 11: Repeat the operations from line 4 to 7. 12: Compute Generator’s loss from Equation 4, 5, 6. 13: Update parameter θ with back-propagation. 14: end while
For other hyper-parameters, we set r = 0.3, γ = 3 in Tr3 dataset. In MNISTsup and Graph-SST2 datasets, we set r = 0.6, γ = 1. We use Adam (Kingma & Ba, 2014) with weight decay rate 1e-5 for optimization. The maximum number of epochs is 100.

heading: E DETAILED USER STUDY
text: The User Study starts by instructions to participants, where they will see a sentence (movie reviews) in each question and its sentiment (Positive of Negative), e.g.,
Sentence: “is more of an ordeal than an amusement” Sentiment: Negative
then several explanations are presented for the answers of “Why the sentiment of this sentence is negative (positive)?”. The explanations (see Figure 7) are shown in graph form (edges indicate relations between words), and colors of more important features are darker.
Then they were asked to choose the best explanation(s). A good explanation should be concise, informative, and the rational cause of sentence’s sentiment. In this case, (B) could be the best explanation since “ordeal” mostly decides the negative sentiment, while (A) only identifies plain words like “more than” and (C) is quite the opposite. Note that the participants can choose multiple answers and some choices are the same. Thereafter, 10 questions out of 32 questions in total are presented for each participant and we compute the average scores for the explainers.

heading: F EXTRA CASE STUDY
text: In this section, we further present a case study for TR3 dataset. In Figure 8, the OOD probabilities for the ground truth explanatory subgraphs in each row remain the same as the edge selection ratios vary, which are 100%, 0%, 0% respectively. In contrast, the evaluation results generated from our DSE have shown strong rationality. Specifically, the importance score compute by our DSE increases with the increasing number of selected ground truth edges. This well validates our DSE framework, where we mitigate the OOD effect by generating the plausible surrogates, making the graphs to be evaluated conforms to the graph distribution in the training data. In this way, the effect of D → Y could hardly affect our assessment for the explanatory subgraph. Thereafter, as the explanatory graph becomes more informative and discriminative, it offers more evidence for the GNN to classify it as the target class which we want to explain, yielding faithful evaluation results.
Cycle
House
Crane
Im p d
se
Figure 8: Three cases in TR3 datasets. Each graph in the left represents the ground truth explanatory subgraphs (red) for explaining a given graph. One of the complement graphs (light blue) generated from CVGAE is also shown with each explanatory subgraph. As the edge selection ratio increases in each row, the importance scores output by our DSE are shown in the right.

heading: G ABLATION STUDY & SENSITIVITY ANALYSIS
text: We first conduct ablation studies to investigate the contribution of the contrastive parameter γ and the penalty parameter λ in CVGAE. The ablation models are proposed by I. removing the contrastive loss, i.e., setting γ = 0 and II. removing the penalty term in the Wasserstein GAN (WGAN) (Martin Arjovsky, 2017) loss, i.e., setting λ = 0. The performance of the ablation models is reported in Table 4. We observe that the superiority of CVGAE compared with the ablation model supports our model design by (i) smoothing the model optimization which yields a more performant generator (ii) highlighting the class-discriminative information in the graph embeddings, which implicitly encodes the class information.
Also, we conduct sensitivity analysis for CVGAE w.r.t. the hyper-parameters. Specifically, we select λ, the penalty in the WGAN loss (cf. Euqation 7) and γ, the strength of the contrastive loss (cf. Equation 4). While we empirically found the performance is relatively indifferent to other parameters in a wide range. The results are shown in Figure 9. We observe that the best performance is achieved with λ taking values from 1 to 10, and γ taking values from 1 to 10 in TR3 dataset and 0.1 to 5 in MNISTsup and Graph-SST2 datasets. And we found a large λ generally causes an increase in the FID metric, as it may alleviate the penalty on the reconstruction errors, which further makes a larger difference between fy(G) and E[fy(G∗s )].

Review summaries:
The paper sheds an exciting light on the problem of producing a meaningful evaluation of GNN explanation methods (at least a subset of them). The idea is to introduce a deconfounder D to capture the effect of OOD explanations. The authors make an interesting example for a well-known synthetic dataset where the weight of the explanation in the ground truth is lower than a clear non-valid explanation when evaluated using the model to explain. The introduction of the deconfounder D creates a spurious path between the graph variable and the explainer variable. To mitigate this effect, then, they introduce a front-door adjustment to the causal graph. The front door adjustment requires a graph generator and authors use a novel Conditional-VGAE to generate graphs that will also cover the OOD case. The paper finally presents some experiments showing the evaluation method in action.

In this paper, the authors use a causal view to investigate the OOD effect on the explanation evaluation of GNNs. They find the confounder between the extracted subgraphs and the model prediction, which makes the evaluation less reliable. To solve this problem, the authors proposed a deconfounding evaluation method based on the front-door adjustment from causal discovery. To generate a reliable surrogate subgraph, they proposed a generative model, which contains three losses for training. The experimental results show the effectiveness of the proposed method (DSE).

This paper has done an excellent work of finding the out-of-distribution between the subgraph and graph as the confounder. Further, this paper proposes a conditional variational graph auto-encoder in assessing the causal effects of subgraph on the prediction. They also introduce a surrogate variable to denote this out-of-distribution effect. Through adversarial training, the effects of the proposed model is correctly verified.  

This paper presents a novel explainer-agnostic method to adjust the biases of feature importance scores of feature attribution for GNNs. The paper first describes the feature importance scores of the GNN feature attribution framework have biases due to the out-of-distribution (OOD) problem. The subgraph important scores are calculated by inputting a subgraph instead of data graphs, but subgraph patterns can fall into regions outside the distribution of training data graphs. To address this problem, the paper proposed a method to generate surrogate graphs within the data graph distribution by CVGAE to make a front-door adjustment for deconfounding these biases by distribution shift. Experiments using several state-of-the-art GNN explainers shows demonstrated the effectiveness of the proposed framework.