Faithful and Consistent Graph Neural Network Explanations with Rationale
  Alignment
Uncovering rationales behind predictions of graph neural networks (GNNs) has
received increasing attention over recent years. Instance-level GNN explanation
aims to discover critical input elements, like nodes or edges, that the target
GNN relies upon for making predictions. %These identified sub-structures can
provide interpretations of GNN's behavior. Though various algorithms are
proposed, most of them formalize this task by searching the minimal subgraph
which can preserve original predictions. However, an inductive bias is
deep-rooted in this framework: several subgraphs can result in the same or
similar outputs as the original graphs. Consequently, they have the danger of
providing spurious explanations and failing to provide consistent explanations.
Applying them to explain weakly-performed GNNs would further amplify these
issues. To address this problem, we theoretically examine the predictions of
GNNs from the causality perspective. Two typical reasons for spurious
explanations are identified: confounding effect of latent variables like
distribution shift, and causal factors distinct from the original input.
Observing that both confounding effects and diverse causal rationales are
encoded in internal representations, \tianxiang{we propose a new explanation
framework with an auxiliary alignment loss, which is theoretically proven to be
optimizing a more faithful explanation objective intrinsically. Concretely for
this alignment loss, a set of different perspectives are explored: anchor-based
alignment, distributional alignment based on Gaussian mixture models,
mutual-information-based alignment, etc. A comprehensive study is conducted
both on the effectiveness of this new framework in terms of explanation
faithfulness/consistency and on the advantages of these variants.
Tianxiang Zhao, Dongsheng Luo, Xiang Zhang, Suhang Wang
# Faithful and Consistent Graph Neural Network Explanations with Rationale Alignment

###### Abstract

Uncovering rationales behind predictions of graph neural networks (GNNs) has received increasing attention over recent years. Instance-level GNN explanation aims to discover critical input elements, like nodes or edges, that the target GNN relies upon for making predictions. Though various algorithms are proposed, most of them formalize this task by searching the minimal subgraph which can preserve original predictions. However, an inductive bias is deep-rooted in this framework: several subgraphs can result in the same or similar outputs as the original graphs. Consequently, they have the danger of providing spurious explanations and failing to provide consistent explanations. Applying them to explain weakly-performed GNNs would further amplify these issues. To address this problem, we theoretically examine the predictions of GNNs from the causally perspective. Two typical reasons for spurious explanations are identified: confounding effect of latent variables like distribution shift, and causal factors distinct from the original input. Observing that both confounding effects and diverse causal rationales are encoded in internal representations, we propose a new explanation framework with an auxiliary alignment loss, which is theoretically proven to be optimizing a more faithful explanation objective intrinsically. Concretely for this alignment loss, a set of different perspectives are explored: anchor-based alignment, distributional alignment based on Gaussian mixture models, mutual-information-based alignment, etc. A comprehensive study is conducted both on the effectiveness of this new framework in terms of explanation faithfulness/consistency and on the advantages of these variants. For our codes, please refer to the following URL link: [https://github.com/Tianxiang/Zhao/GraphNNExplanation](https://github.com/Tianxiang/Zhao/GraphNNExplanation).

 Graph Neural Network, Explainable AI, Machine Learning

## 1 Introduction

Graph-structured data is ubiquitous in the real world, such as social networks [1, 2], molecular structures [3, 4] and knowledge graphs [5]. With the growing interest in learning from graphs, graph neural networks (GNNs) are receiving more and more attention over the years. Generally, GNNs adopt message-passing mechanisms, which recursively propagate and fuse messages from neighbor nodes on the graphs. Hence, the learned node representation captures both node attributes and neighborhood information, which facilitate various downstream tasks such as node classification [6, 7, 8], graph classification [9], and link prediction [10].

Despite the success of GNNs for various domains, as with other neural networks, GNNs lack interpretability. Understanding the inner working of GNNs can bring several benefits. First, it enhances practitioners' trust in the GNN model by enriching their understanding of the model characteristics such as if the model is working as desired. Second, it increases the models' transparency to enable trusted applications in decision-critical fields sensitive to fairness, privacy and safety challenges, such as healthcare and drug discovery [11]. Thus, studying the explainability of GNNs is attracting increasing attention and many efforts have been taken [12, 13, 14].

Particularly, we focus on post-hoc instance-level explanations. Given a trained GNN and an input graph, this task seeks to discover the substructures that can explain the prediction behavior of the GNN model. Some solutions have been proposed in existing works [12, 15, 16]. For example, in search of important substructures that predictions rely upon, GNNExplainer learns an importance matrix on node attributes and edges via perturbation [12]. The identified minimal substructures that preserve original predictions are taken as the explanation. Extending this idea, PGExplainer trains a graph generator to utilize global information in explanation and enable faster inference in the inductive setting [13]. SubgraphX constraints explanations as connected subgraphs and conduct Monte Carlo tree search based on Shapley value [17]. These methods can be summarized in a label preserving framework, i.e., the candidate explanation is formed as a masked version of the original graph and is identified as the minimal discriminative substructure that preserves the predicted label.

However, due to the complexity of topology and the combinatory number of candidate substructures, existing label preserving methods are insufficient for a faithful and consistent explanation of GNNs. They are unstable and are prone to give spurious correlations as explanations. A failure case is shown in Figure 1, where a GNN is trained on Graph-SST5 [18] for sentiment classification. Each node represents a word and each edge denotes syntactic dependency between nodes. Each graph is labeled based on the sentiment of the sentence. In the figure, the sentence "Sweet home alabama isn't going to win any academy awards, but this date-night diversion will definitely win some hearts" is labeled _positive_. In the first run, GNNExplainer [12] identifies the explanation as "definitely win some hearts", and in the second run, it identifies "win academy awards" to be the explanation instead. Different explanations obtained
by GNNExplainer break the criteria of **consistency**, i.e., the explanation method should be deterministic and consistent with the same input for different runs [19]. Consequently, explanations provided by existing methods may fail to faithfully reflect the decision mechanism of the to-be-explained GNN.

Inspecting the inference process of target GNNs, we find that the inconsistency problem and spurious explanations can be understood from the causality perspective. Specifically, existing explanation methods may lead to spurious explanations either as a result of different causal factors or due to the confounding effect of distribution shifts (identified subgraphs may be out of distribution). These failure cases originate from a particular inductive bias that predicted labels are sufficiently indicative for extracting critical input components. This underlying assumption is rooted in optimization objectives adopted by existing works [12, 13, 17]. However, our analysis demonstrates that the label information is insufficient to filter out spurious explanations, leading to inconsistent and unfaithful explanations.

Considering the inference of GNNs, both confounding effects and distinct causal relationships can be reflected in the internal representation space. With this observation, we propose a novel objective that encourages alignment of embeddings of raw graph and identified subgraph in internal embedding space to obtain more faithful and consistent GNN explanations. Specifically, to evaluate the semantic similarity between two inputs and incorporate the alignment objective into explanation, we design and compare strategies with various design choices to measure similarity in the embedding space. These strategies enable the alignment between candidate explanations and original inputs and are flexible to be incorporated into various existing GNN explanation methods. Particularly, aside from directly using Euclidean distance, we further propose three distribution-aware strategies. The first one identifies a set of anchoring embeddings and utilizes relative distances against them. The second one assumes a Gaussian mixture model and captures the distribution using the probability of falling into each Gaussian center. The third one learns a deep neural network to estimate mutual information between two inputs, which takes a data-driven approach with little reliance upon prior domain knowledge. Further analysis shows that the proposed method is in fact optimizing a new explanation framework, which is more faithful in design. Our main contributions are:

* We point out the faithfulness and consistency issues in rationales identified by existing GNN explanation models. These issues arise due to the inductive bias in their label-preserving framework, which only uses predictions as the guiding information;
* We propose an effective and easy-to-apply countermeasure by aligning intermediate embeddings. We implement a set of variants with different alignment strategies, which is flexible to be incorporated to various GNN explanation models. We further conduct a theoretical analysis to understand and validate the proposed framework.
* Extensive experiments on real-world and synthetic datasets show that our framework benefits various GNN explanation models to achieve more faithful and consistent explanations.

## 2 Related Work

In this section, we review related works, including graph neural networks and interpretability of GNNs.

### _Graph Neural Networks_

Graph neural networks (GNNs) are developing rapidly in recent years, with the increasing need for learning on relational data structures [1, 20, 21]. Generally, existing GNNs can be categorized into two categories, i.e., spectral-based approaches [6, 22, 23] based on graph signal processing theory, and spatial-based approaches [24, 25, 26] relying upon neighborhood aggregation. Despite their differences, most GNN variants can be summarized with the message-passing framework, which is composed of pattern extraction and interaction modeling within each layer [27]. Specifically, GNNs model messages from node representations. These messages are then propagated with various message-passing mechanisms to refine node representations, which are then utilized for downstream tasks [8, 10, 21]. Explorations are made by disentangling the propagation process [28, 29, 30] or utilizing external prototypes [31, 32]. Research has also been conducted on the expressive power [33, 34] and potential biases introduced by different kernels [35, 36] for the design of more effective GNNs. Despite their success in network representation learning, GNNs are uninterpretable black box models. It is challenging to understand their behaviors even if the adopted message passing mechanism and parameters are given. Besides, unlike traditional deep neural networks where instances are identically and independently distributed, GNNs consider node features and graph topology jointly, making the interpretability problem more challenging to handle.

### _GNN Interpretation Methods_

Recently, some efforts have been taken to interpret GNN models and provide explanations for their predictions [37]. Based on the granularity, existing methods can be generally grouped into two categories: (1) instance-level explanation [12], which provides explanations on the prediction for each instance by identifying important substructures; and (2) model-level explanation [38, 39], which aims to understand global decision rules captured by the target GNN. From the methodology perspective, existing methods can be categorized as (1) self-explainable GNNs [39, 40], where

Fig. 1: Explanation results achieved by a leading baseline GNNExplainer on the same input graph from Graph-SST5. Red edges formulate explanation substructures.
the GNN can simultaneously give prediction and explanations on the prediction; and (2) post-hoc explanations [12, 13, 17], which adopt another model or strategy to provide explanations of a target GNN. As post-hoc explanations are model-agnostic, i.e., can be applied for various GNNs, in this work, we focus on post-hoc instance-level explanations [12], i.e., given a trained GNN model, identifying instance-wise critical substructures for each input to explain the prediction. A comprehensive survey can be found in [41].

A variety of strategies for post-hoc instance-level explanations have been explored in the literature, including utilizing signals from gradients based [38, 42], perturbed predictions based [12, 13, 17, 43], and decomposition based [38, 44]. Among these methods, perturbed prediction-based methods are the most popular. The basic idea is to learn a perturbation mask that filters out non-important connections and identifies dominating substructures preserving the original predictions [18]. The identified important substructure is used as an explanation for the prediction. For example, GNNExplainer [12] employs two soft mask matrices on node attributes and graph structure, respectively, which are learned end-to-end under the maximizing mutual information (MMI) framework. PGExplainer [13] extends it by incorporating a graph generator to utilize global information. It can be applied in the inductive setting and prevent the onerous task of re-learning from scratch for each to-be-explained instance. SubgraphX [17] expects explanations to be in the form of sub-graphs instead of bag-of-edges and employs Monte Carlo Tree Search (MCTS) to find connected subgraphs that preserve predictions measured by the Shapley value. To promote faithfulness in identified explanations, some works introduced terminologies from the causality analysis domain, via estimating the individual causal effect of each edge [45] or designing interventions to prevent the discovery of spurious correlations [46]. Ref. [47] connects the idea of identifying minimally-predictive parts in explanation with the principle of information bottleneck [48] and designs an end-to-end optimization framework for GNN explanation.

Despite the aforementioned progress in interpreting GNNs, most of these methods discover critical substructures merely upon the change of outputs given perturbed inputs. Due to this underlying inductive bias, existing label-preserving methods are heavily affected by spurious correlations caused by confounding factors in the environment. On the other hand, by aligning intermediate embeddings in GNNs, our method alleviates the effects of spurious correlations on interpreting GNNs, leading to faithful and consistent explanations.

## 3 Preliminary

### _Problem Definition_

We use \(\mathcal{G}=\{\mathcal{V},\mathcal{E};\mathbf{F},\mathbf{A}\}\) to denote a graph, where \(\mathcal{V}=\{v_{1},\ldots,v_{n}\}\) is a set of \(n\) nodes and \(\mathcal{E}\in\mathcal{V}\times\mathcal{V}\) is the set of edges. Nodes are accompanied by an attribute matrix \(\mathbf{F}\in\mathbb{R}^{n\times d}\), and \(\mathbf{F}[i,:]\in\mathbb{R}^{1\times d}\) is the \(d\)-dimensional node attributes of node \(v_{i}\). \(\mathcal{E}\) is described by an adjacency matrix \(\mathbf{A}\in\mathbb{R}^{n\times n}\). \(A_{ij}=1\) if there is an edge between node \(v_{i}\) and \(v_{j}\); otherwise, \(A_{ij}=0\). For _graph classification_, each graph \(\mathcal{G}_{i}\) has a label \(Y_{i}\in\mathcal{C}\), and a GNN model \(f\) is trained to map \(\mathcal{G}\) to its class, i.e., \(f:\{\mathbf{F},\mathbf{A}\}\mapsto\{1,2,\ldots,C\}\). Similarly, for _node classification_, each graph \(\mathcal{G}_{i}\) denotes a \(K\)-hop subgraph centered at node \(v_{i}\) and a GNN model \(f\) is trained to predict the label of \(v_{i}\) based on node representation of \(v_{i}\) learned from \(\mathcal{G}_{i}\). The purpose of explanation is to find a subgraph \(\mathcal{G}^{\prime}\), marked with binary importance mask \(\mathbf{M}_{A}\in[0,1]^{n\times n}\) on adjacency matrix and \(\mathbf{M}_{F}\in[0,1]^{n\times d}\) on node attributes, respectively, e.g., \(\mathcal{G}^{\prime}=\{\mathbf{A}\odot\mathbf{M}_{A};\mathbf{F}\odot\mathbf{ M}_{F}\}\), where \(\odot\) denotes elementwise multiplication. These two masks highlight components of \(\mathcal{G}\) that are important for \(f\) to predict its label. With the notations, the _post-hoc instance-level_ GNN explanation task is:

_Given a trained GNN model \(f\), for an arbitrary input graph \(\mathcal{G}=\{\mathcal{V},\mathcal{E};\mathbf{F},\mathbf{A}\}\), find a subgraph \(\mathcal{G}^{\prime}\) that can explain the prediction of \(f\) on \(\mathcal{G}\). The obtained explanation \(\mathcal{G}^{\prime}\) is depicted by importance mask \(\mathbf{M}_{F}\) on node attributes and importance mask \(\mathbf{M}_{A}\) on adjacency matrix._

### _MMI-based Explanation Framework_

Many approaches have been designed for post-hoc instance-level GNN explanation. Due to the discreteness of edge existence and non-grid graph structures, most works apply a perturbation-based strategy to search for explanations. Generally, they can be summarized as Maximization of Mutual Information (MMI) between predicted label \(\hat{Y}\) and explanation \(\mathcal{G}^{\prime}\), i.e.,

\[\begin{split}\min_{\mathcal{G}^{\prime}}&-I(\hat{Y},\mathcal{G}^{\prime}),\\ \text{s.t.}&\mathcal{G}^{\prime}\sim\mathcal{P}( \mathcal{G},\mathbf{M}_{A},\mathbf{M}_{F}),\quad\mathcal{R}(\mathbf{M}_{F}, \mathbf{M}_{A})\leq c\end{split} \tag{1}\]

where \(I()\) represents mutual information and \(\mathcal{P}\) denotes the perturbations on original input with importance masks \(\{\mathbf{M}_{F},\mathbf{M}_{A}\}\). For example, let \(\{\hat{\mathbf{A}},\hat{\mathbf{F}}\}\) represent the perturbed \(\{\mathbf{A},\mathbf{F}\}\). Then, \(\mathbf{A}=\mathbf{A}\odot\mathbf{M}_{A}\) and \(\hat{\mathbf{F}}=\mathbf{Z}+(\mathbf{F}-\mathbf{Z})\odot\mathbf{M}_{F}\) in GNNExplainer [12], where \(\mathbf{Z}\) is sampled from marginal distribution of node attributes \(\mathbf{F}\). \(\mathcal{R}\) denotes regularization terms on the explanation, imposing prior knowledge into the searching process, like constraints on budgets or connectivity distributions [13]. Mutual information \(I(\hat{Y},\mathcal{G}^{\prime})\) quantifies consistency between original predictions \(\hat{Y}=f(\mathcal{G})\) and prediction of candidate explanation \(f(\mathcal{G}^{\prime})\), which promotes the positiveness of found explanation \(\mathcal{G}^{\prime}\). Since mutual information measures the predictive power of \(\mathcal{G}^{\prime}\) on \(Y\), this framework essentially tries to find a subgraph that can best predict the original output \(\hat{Y}\). During training, a relaxed version [12] is often adopted as:

\[\begin{split}\min_{\mathcal{G}^{\prime}}&\ H_{C}(\hat{Y},P(\hat{Y}^{\prime}\mid\mathcal{G}^{\prime})),\\ \text{s.t.}&\mathcal{G}^{\prime}\sim\mathcal{P}( \mathcal{G},\mathbf{M}_{A},\mathbf{M}_{F}),\quad\mathcal{R}(\mathbf{M}_{F}, \mathbf{M}_{A})\leq c\end{split} \tag{2}\]

where \(H_{C}\) denotes cross-entropy. With this same objective, existing methods mainly differ from each other in optimization and searching strategies.

Different aspects regarding the quality of explanations can be evaluated [19]. Among them, two most important criteria are **faithfulness** and **consistency**. Faithfulness measures the descriptive accuracy of explanations, indicating how truthful they are compared to behaviors of the target model. Consistency considers explanation invariance, which
checks that identical input should have identical explanations. However, as shown in Figure 1, the existing MMI-based framework is sub-optimal in terms of these criteria. The cause of this problem is rooted in its learning objective, which uses prediction alone as guidance in search of explanations. Due to the complex graph structure, the prediction alone as a guide could result in spurious explanations. A detailed analysis will be provided in the next section.

## 4 Analyze Spurious Explanations

With "spurious explanations", we refer to those explanations lie outside the genuine rationale of prediction on \(\mathcal{G}\), making the usage of \(\mathcal{G}^{\prime}\) as explanations anecdotal. As examples in Figure 1, despite rapid developments in explaining GNNs, the problem w.r.t faithfulness and consistency of detected explanations remains. To get a deeper understanding of reasons behind this problem, we will examine the behavior of target GNN model from the causality perspective. Figure 2(a) shows the Structural Equation Model (SEM), where variable \(C\) denotes discriminative causal factors and variable \(S\) represents confounding environment factors. Two paths between \(\mathcal{G}\) and the predicted label \(\hat{Y}\) can be found.

* \(\mathcal{G}\to C\rightarrow\hat{Y}\): This path presents the inference of target GNN model, i.e., critical patterns \(C\) that are informative and discriminative for the prediction \(\hat{Y}\) would be extracted from input graph, upon which the target model is dependent. Causal variables are determined by both the input graph and learned knowledge by the target GNN model.
* \(\mathcal{G}\gets S\rightarrow\hat{Y}\): We denote \(S\) as the confounding factors, such as depicting the overall distribution of graphs. It is causally related to both the appearance of input graphs and the prediction of target GNN models. A masked version of \(\mathcal{G}\) could create out-of-distribution (OOD) examples, resulting in spurious causality to prediction outputs. For example in the chemical domain, removing edges (bonds) or nodes (atoms) may obtain invalid molecular graphs that never appear during training. In the existence of distribution shifts, model predictions would be less reliable.

Figure 2(a) provides us with a tool to analyze \(f\)'s behaviors. From the causal structures, we can observe that spurious explanations may arise as a result of failure in recovering the original causal rationale. \(\mathcal{G}^{\prime}\) learned from Equation 1 may preserve prediction \(\hat{Y}\) due to confounding effect of distribution shift or different causal variables \(C\) compared to original \(\mathcal{G}\). Weakly-trained GNN \(f(\cdot)\) that are unstable or non-robust towards noises would further amplify this problem as the prediction is unreliable.

To further understand the issue, we build the correspondence from SEM in Figure 2(a) to the inference process of GNN \(f\). Specifically, we first decompose \(f()\) as a feature extractor \(f_{ext}()\) and a classifier \(f_{cls}()\). Then, its inference can be summarized as two steps: (1) encoding step with \(f_{ext}()\), which takes \(\mathcal{G}\) as input and produce its embedding in the representation space \(E_{C}\); (2) classification step with \(f_{cls}()\), which predicts output labels on input's embedding. Connecting these inference steps to SEM in Figure 2(a), we can find that:

* The causal path \(\mathcal{G}\to C\rightarrow\hat{Y}\) lies behind the inference process with representation space \(E_{C}\) to encode critical variables \(C\);
* The confounding effect of distribution shift \(S\) works on the inference process via influencing distribution of graph embedding in \(E_{C}\). When masked input \(\mathcal{G}^{\prime}\) is OOD, its embedding would fail to reflect its discriminative features and deviate from real distributions, hence deviating the classification step on it.

To summarize, we can observe that spurious explanations are usually obtained due to the following two reasons:

1. The obtained \(\mathcal{G}^{\prime}\) is OOD graph. During inference of target GNN model, the encoded representation of \(\mathcal{G}^{\prime}\) is distant from those seen in the training set, making the prediction unreliable;
2. The encoded discriminative representation does not accord with that of the original graph. Different causal factors (\(C\)) are extracted between \(\mathcal{G}^{\prime}\) and \(\mathcal{G}\), resulting in false explanations.

## 5 Methodology

Based on the discussion above, in this section, we focus on improving the faithfulness and consistency of GNN explanations and correcting the inductive bias caused by simply relying on prediction outputs. We first provide an intuitive introduction to the proposed countermeasure, which takes the internal inference process into account. We then design four concrete algorithms to align \(\mathcal{G}\) and \(\mathcal{G}^{\prime}\) in the latent space, to promote that they are seen and processed in the same manner. Finally, theoretical analysis is provided to justify our strategies.

### _Alleviate Spurious Explanations_

Instance-level post-hoc explanation dedicates to finding discriminative substructures that the target model \(f\) depends upon. The traditional objective in Equation 2 can identify minimal predictive parts of input, however, it is dangerous to directly take them as explanations. Due to diversity in graph topology and combinatory nature of sub-graphs, multiple distinct substructures could be identified leading to the same prediction, as discussed in Section 4.

For an explanation substructure \(\mathcal{G}^{\prime}\) to be faithful, it should follow the same rationale as the original graph \(\mathcal{G}\) inside the internal inference of to-be-explained model \(f\). To achieve this goal, the explanation \(\mathcal{G}^{\prime}\) should be aligned to \(\mathcal{G}\) w.r.t the decision mechanism, reflected in Figure 2(a). However, it is non-trivial to extract and compare the critical

Fig. 2: (a) Prediction rules of \(f\), in the form of SCM. (b) An example of anchor-based embedding alignment.
causal variables \(C\) and confounding variables \(S\) due to the black box nature of the target GNN model to be explained.

Following the causal analysis in Section 4, we propose to take an alternative approach by looking into internal embeddings learned by \(f\). Causal variables \(C\) are encoded in representation space extracted by \(f\), and out-of-distribution effects can also be reflected by analyzing embedding distributions. An assumption can be safely made: _if two graphs are mapped to embeddings near each other by a GNN layer, then these graphs are seen as similar by it and would be processed similarly by following layers_. With this assumption, a proxy task can be designed by aligning internal graph embeddings between \(\mathcal{G}^{\prime}\) and \(\mathcal{G}\). This new task can be incorporated into Framework 1 as an auxiliary optimization objective.

Let \(\mathbf{h}_{v}^{l}\) be the representation of node \(v\) at the \(l\)-th GNN layer with \(\mathbf{h}_{v}^{0}=\mathbf{F}[v,:]\). Generally, the inference process inside GNN layers can be summarized as a message-passing framework:

\[\begin{split}\mathbf{m}_{v}^{l+1}&=\sum_{u\in \mathcal{N}(v)}\text{Message}_{l}(\mathbf{h}_{v}^{l},\mathbf{h}_{u}^{l},A_{v, u}),\\ \mathbf{h}_{v}^{l+1}&=\text{Update}_{l}(\mathbf{h}_ {v}^{l},\mathbf{m}_{v}^{l+1}),\end{split} \tag{3}\]

where \(\text{Message}_{l}\) and \(\text{Update}_{l}\) are the message function and update function at \(l\)-th layer, respectively. \(\mathcal{N}(v)\) is the set of node \(v\)'s neighbors. Without loss of generality, the graph pooling layer can also be presented as:

\[\mathbf{h}_{v^{\prime}}^{l+1}=\sum_{v\in\mathcal{V}}P_{v,v^{\prime}}\cdot \mathbf{h}_{v}^{l}. \tag{4}\]

where \(P_{v,v^{\prime}}\) denotes mapping weight from node \(v\) in layer \(l\) to node \(v^{\prime}\) in layer \(l+1\) inside the myriad of GNN for graph classification. We propose to align embedding \(\mathbf{h}_{v}^{l+1}\) at each layer, which contains both node and local neighborhood information.

### _Distribution-Aware Alignment_

Achieving alignment in the embedding space is not straightforward. It has several distinct difficulties. (1) It is difficult to evaluate the distance between \(\mathcal{G}\) and \(\mathcal{G}^{\prime}\) in this embedding space. Different dimensions could encode different features and carry different importance. Furthermore, \(\mathcal{G}^{\prime}\) is a substructure of the original \(\mathcal{G}\), and a shift on unimportant dimensions would naturally exist. (2) Due to the complexity of graph/node distributions, it is non-trivial to design a measurement of alignments that is both computationally and can correlate well to distance on the distribution manifold.

To address these challenges, we design a strategy to identify explanatory substructures and preserve their alignment with original graphs in a distribution-aware manner. The basic idea is to utilize other graphs to obtain a global view of the distribution density of embeddings, providing a better measurement of alignment. Concretely, we obtain representative node/graph embeddings as anchors and use distances to these anchors as the distribution-wise representation of graphs. Alignment is conducted on obtained representation of graph pairs. Next, we go into details of this strategy.

* First, using graphs \(\{\mathcal{G}_{i}\}_{i=1}^{m}\) from the same dataset, a set of node embeddings can be obtained as \(\{\{\mathbf{h}_{v,i}^{l}\}_{v\in\mathcal{V}^{\prime}_{i}}\}_{i=1}^{m}\) for each layer \(l\), where \(\mathbf{h}_{v,i}\) denotes embedding of node \(v\) in graph \(\mathcal{G}_{i}\). For node-level tasks, we set \(\mathcal{V}^{\prime}_{i}\) to contain only the center node of graph \(\mathcal{G}_{i}\). For graph-level tasks, \(\mathcal{V}^{\prime}_{i}\) contains nodes set after graph pooling layer, and we process them following \(\{\sum_{v\in\mathcal{V}^{\prime}_{i}}\mathbf{h}_{v,i}^{l+1}/|\mathcal{V}^{ \prime}_{i}|\}_{i=1}^{m}\) to get global graph representation.
* Then, a clustering algorithm is applied to the obtained embedding set to get \(K\) groups. Clustering centers of these groups are set to be anchors, annotated as \(\{\mathbf{h}^{l+1,k}\}_{k=1}^{k}\). In experiments, we select DBSCAN [10] as the clustering algorithm, and tune its hyper-parameters to get around \(20\) groups.
* At \(l\)-th layer, \(\mathbf{h}_{v}^{l+1}\) is represented in terms of relative distances to those \(K\) anchors, as \(\mathbf{s}_{v}^{l}\in\mathbb{R}^{1\times K}\) with the \(k\)-th element calculated as \(\mathbf{s}_{v}^{l+1,k}=\|\mathbf{h}_{v}^{l+1}-\mathbf{h}_{v}^{l+1,k}\|_{2}\).

Alignment between \(\mathcal{G}^{\prime}\) and \(\mathcal{G}\) can be achieved by comparing their representations at each layer. The alignment loss is computed as:

\[\mathcal{L}_{align}(f(\mathcal{G}),f(\mathcal{G}^{\prime}))=\sum_{l}\sum_{v \in\mathcal{V}^{\prime}}\|\mathbf{s}_{v}^{l}-\mathbf{s}_{v}^{\prime}\|_{2}^{2}. \tag{5}\]

This metric provides a lightweight strategy for evaluating alignments in the embedding distribution manifold, by comparing relative positions w.r.t representative clustering centers. This strategy can naturally encode the varying importance of each dimension. Fig. 2(b) gives an example, where \(\mathcal{G}\) is the graph to be explained and the red stars are anchors. \(\mathcal{G}^{\prime}_{1}\) and \(\mathcal{G}^{\prime}_{2}\) are both similar to \(\mathcal{G}\) w.r.t absolute distances; while it is easy to see \(\mathcal{G}^{\prime}_{1}\) is more similar to \(\mathcal{G}\) w.r.t to the anchors. In other words, the anchors can better measure the alignment to filter out spurious explanations.

This alignment loss is used as an auxiliary task incorporated into MMI-based framework in Equation 2 to get faithful explanation as:

\[\begin{split}\underset{\mathcal{G}^{\prime}}{\text{min}}H_{C} \big{(}\hat{Y},P(\hat{Y}^{\prime}\mid\mathcal{G}^{\prime})\big{)}+\lambda \cdot\mathcal{L}_{align},\\ \text{s.t.}\quad\mathcal{G}^{\prime}\sim\mathcal{P}(\mathcal{G}, \mathbf{M}_{A},\mathbf{M}_{F}),\quad\mathcal{R}(\mathbf{M}_{F},\mathbf{M}_{A}) \leq c\end{split} \tag{6}\]

where \(\lambda\) controls the balance between prediction preservation and embedding alignment. \(\mathcal{L}_{align}\) is flexible to be incorporated into various existing explanation methods.

### _Direct Alignment_

As a simpler and more direct implementation, we also design a variant based on absolute distance. For layers without graph pooling, the objective can be written as \(\sum_{l}\sum_{v\in\mathcal{V}}\|\mathbf{h}_{v}^{l}-\mathbf{h}_{v}^{l}\|_{2}^{2}\). For layers with graph pooling, as the structure could be different, we conduct alignment on global representation \(\sum_{v\in\mathcal{V}^{\prime}}\mathbf{h}_{v}^{l+1}/|\mathcal{V}^{\prime}|\), where \(\mathcal{V}^{\prime}\) denotes node set after pooling.

## 6 Extended Methodology

In this section, we further examine more design choices for the strategy of alignment to obtain faithful and consistent explanations. Instead of using heuristic approaches, we explore two new directions: (1) statistically sound distance measurements based on the Gaussian mixture model, (2) fully utilizing the power of deep neural networks to capture distributions in the latent embedding space. Details of these two alignment strategies will be introduced below.
### _Gaussian-Mixture-based Alignment_

In this strategy, we model the latent embeddings of nodes (or graphs) using a mixture of Gaussian distributions, with representative node/graph embeddings as anchors (Gaussian centers). The produced embedding of each input can be compared with those prototypical anchors, and the semantic information of inputs taken by the target model would be encoded by relative distances from them.

Concretely, we first obtain prototypical representations, annotated as \(\{\mathbf{h}^{l,k}\}_{k=1}^{K}\), by running the clustering algorithm on collected embeddings \(\{(\mathbf{h}^{l}_{v,i})_{v\in V}\}_{i=1}^{m}\) from graphs \(\{\mathcal{G}_{i}\}_{i=1}^{m}\), in the same strategy as introduced in Sec. 5.2. Cluttering algorithm DBSCAN [49] is adopted and we tune its hyper-parameters to get around \(20\) groups.

Next, the probability of encoded representation \(\mathbf{h}^{l}\) falling into each prototypical Gaussian centers \(\{\mathbf{h}^{l,k}\}_{k=1}^{K}\) can be computed as:

\[p_{v}^{l,k}=\frac{\exp(-\|\mathbf{h}^{l}_{v}-\mathbf{h}^{l,k}\|_{2}^{2}/2 \sigma^{2})}{\sum_{j=1}^{K}\exp(-\|\mathbf{h}^{l}_{v}-\mathbf{h}^{l,k}\|_{2}^{ 2}/2\sigma^{2})} \tag{7}\]

This distribution probability can serve as a natural tool for depicting the semantics of the input graph learned by the GNN model. Consequently, the distance between \(\mathbf{h}^{l}_{v}\) and \(\mathbf{h}^{l}_{v}\) can be directly measured as the KL-divergence w.r.t this distribution probability:

\[d(\mathbf{p}^{{}^{\prime}l}_{v},\mathbf{p}^{l}_{v})=\sum_{k\in[1,\dots,K]}p^{{ }^{\prime}l,k}_{v}\cdot\log(\frac{p^{{}^{\prime}l,k}_{v}}{p^{l,k}_{v}}), \tag{8}\]

where \(\mathbf{p}^{{}^{\prime}l}_{v}\in\mathbb{R}^{K}\) denotes the distribution probability of candidate explanation embedding, \(\mathbf{h}^{{}^{\prime}l}_{v}\). Using this strategy, the alignment loss between original graph and the candidate explanation is computed as:

\[\mathcal{L}_{align}\big{(}f(\mathcal{G}),f(\mathcal{G}^{\prime})\big{)}= \sum_{l}\sum_{v\in\mathcal{V}^{\prime}}d(\mathbf{p}^{{}^{\prime}l}_{v}, \mathbf{p}^{l}_{v}), \tag{9}\]

which can be incorporated into the revised explanation framework proposed in Eq. 6.

**Comparison** Compared with the alignment loss based on relative distances against anchors in Eq. 5, this new objective offers a better strategy in taking distribution into consideration. Specifically, we can show the following two advantages:

* In obtaining the distribution-aware representation of each instance, this variant uses a Gaussian distance kernel (Eq. 7) while the other one uses Euclidean distance in Sec. 5.2, which may amplify the influence of distant anchors. We can prove this by examining the gradient of changes in representation w.r.t GNN embeddings \(\mathbf{h}_{v}\). In the \(l\)-th layer at dimension \(k\), the gradient of the previous variant can be computed as: \[\frac{\partial s^{l,k}_{v}}{\partial\mathbf{h}^{l}_{v}}=2\cdot(\mathbf{h}^{l}_ {v}-\mathbf{h}^{l,k}_{v})\] (10) On the other hand, the gradient of this variant is: \[\frac{\partial p^{l,k}_{v}}{\partial\mathbf{h}^{l}_{v}}\approx-\frac{\exp(-\| \mathbf{h}^{l}_{v}-\mathbf{h}^{l,k}\|_{2}^{2}/2\sigma^{2})\cdot(\mathbf{h}^{l} _{v}-\mathbf{h}^{l,k}_{v})}{\sigma^{2}\cdot\sum_{j=1}^{K}\exp(-\|\mathbf{h}^{l} _{v}-\mathbf{h}^{l,k}\|_{2}^{2}/2\sigma^{2})}\] (11) It is easy to see that for the previous variant, the magnitude of gradient would grow linearly w.r.t distances towards corresponding anchors. For this variant, on the other hand, the term \(\frac{\exp(-\|\mathbf{h}^{l}_{v}-\mathbf{h}^{l,k}\|_{2}^{2}/2\sigma^{2})}{ \sigma^{2}\cdot\sum_{j=1}^{K}\exp(-\|\mathbf{h}^{l}_{v}-\mathbf{h}^{l,k}\|_{ 2}^{2}/2\sigma^{2})}\) would down-weight the importance of those distant anchors while up-weight the importance of similar anchors, which is more desired in obtaining distribution-aware representations.
* In computing the distance between representations of two inputs, this variant adopts the KL divergence as in Eq. 8, which would be scale-agnostic compared to the other one directly using Euclidean distance as in Eq. 5. Again, we can show the gradient of alignment loss towards obtained embeddings that encode distribution information. It can be observed that for the previous variant: \[\frac{\partial d(\mathbf{s}^{l}_{v},\mathbf{s}^{\prime}_{v})}{\partial s^{ \prime}_{v}}=2\cdot(s^{l,k}_{v}-s^{\prime,k}_{v})\] (12) For this variant based on Gaussian mixture model, the gradient can be computed as: \[\frac{\partial d(\mathbf{p}^{l}_{v},\mathbf{p}^{\prime}_{v})}{\partial p^{ \prime}_{v}}=1+\log(\frac{p^{\prime}_{v}l,k}{p^{\prime}_{v}})\] (13) It can be observed that the previous strategy focuses on representation dimensions with a large absolute difference, while would be sensitive towards the scale of each dimension. On the other hand, this strategy uses the summation between the logarithm of relative difference with a constant, which is scale-agnostic towards each dimension.

### _MI-based Alignment_

In this strategy, we further consider the utilization of deep models to capture the distribution and estimate the semantic similarity of two inputs, and incorporate it into the alignment loss for discovering faithful and consistent explanations. Specifically, we train a deep model to estimate the mutual information (MI) between two input graphs, and use its prediction as a measurement of alignment between original graph and its candidate explanation. This strategy circumvents the reliance on heuristic strategies and is purely data-driven, which can be learned in an end-to-end manner.

To learn the mutual information estimator, we adopt a neural network and train it to be a Jensen-Shannon MI estimator [50]. Concretely, we train this JSD-based estimator on top of intermediate embeddings with the learning objective as follows, which offers better stability in optimization:

\[\begin{split}\min_{g_{mi}}\mathcal{L}_{mi}=&\mathbb{E}_ {\mathcal{G}\in\{\mathcal{G}_{i}\}_{i=1}^{m}}\mathbb{E}_{v\in\mathcal{G}} \mathbb{E}_{l}[\mathbf{E}_{\mathbf{h}^{l,k}_{v}}+sp(-T^{l}(\mathbf{h}^{l}_{v}, \mathbf{h}^{l,+}_{v}))\\ &+\mathbb{E}_{\mathbf{h}^{l,-}_{v}}-sp(T^{l}(\mathbf{h}^{l}_{v}, \mathbf{h}^{l,-}_{v}))],\end{split} \tag{14}\]

where \(\mathbb{E}\) denotes expectation. In this equation, \(T^{l}(\cdot)\) is a compatibility estimation function in the \(l\)-th layer, and we denote \(\{T^{l}(\cdot)\}_{l}\) as the MI estimator \(g_{mi}\). Activation function \(sp(\cdot)\) is the _softplus_ function, and \(\mathbf{h}^{+}_{v}\) represents the embedding of augmented node \(v\) that is a **positive pair** of \(v\) in the original graph. On the contrary, \(\mathbf{h}^{-}_{v}\) denotes the embedding of augmented node \(v\) that is a **negative pair** of original input. A positive pair is obtained through randomly dropping intermediate neurons, corresponding to masking out a ratio of original input, and a negative pair is obtained
as embeddings of different nodes. This objective can guide \(g_{mi}\) to capture the correlation or similarity between two input graphs encoded by the target model. With this MI estimator learned, alignment loss between \(\mathcal{G}\) and \(\mathcal{G}^{{}^{\prime}}\) can be readily computed:

\[\mathcal{L}_{align}\big{(}f(\mathcal{G}),f(\mathcal{G}^{\prime})\big{)}=\sum_{l }\sum_{v\in\mathcal{V}^{\prime}}sp(-T^{l}(\mathbf{h}_{v}^{{}^{\prime}l}, \mathbf{h}_{v}^{l})), \tag{15}\]

which can be incorporated into the revised explanation framework proposed in Eq. 6.

In this strategy, we design a data-driven approach by capturing the mutual information between two inputs, which circumvents the potential biases of using human-crafted heuristics.

## 7 Theoretical Analysis

With those alignment strategies and our new explanation framework introduced, next, we want to look deeper and provide theoretical justifications for the proposed new loss function in Eq. 6. In this section, we first propose a new explanation objective to prevent spurious explanations based on our analysis in Sec. 4. Then, we theoretically show that it squares with our proposed loss function with mild relaxations.

### _New Explanation Objective_

From previous discussions, it is shown that \(\mathcal{G}^{\prime}\) obtained via Equation 1 cannot be safely used as explanations. One main drawback of existing GNN explanation methods lies in the inductive bias that the same outcomes do not guarantee the same causes, leaving existing approaches vulnerable towards spurious explanations. An illustration is given in Figure 3. Objective proposed in Equation 1 optimizes the mutual information between explanation candidate \(\mathcal{G}^{\prime}\) and \(\hat{Y}\), corresponding to maximize the overlapping between \(H(\mathcal{G}^{\prime})\) and \(H(\hat{Y})\) in Figure 3(a), or region \(S_{1}\cup S_{2}\) in Figure 3(b). Here, \(H\) denotes information entropy. However, this learning target cannot prevent the danger of generating spurious explanations. Provided \(\mathcal{G}^{\prime}\) may fall into the region \(S_{2}\), which cannot faithfully represent graph \(\mathcal{G}\). Instead, a more sensible objective should be maximizing region \(S_{1}\) in Figure 3(b). The intuition behind this is that in the search input space that causes the same outcome, identified \(\mathcal{G}^{\prime}\) should account for both representative and discriminative parts of original \(\mathcal{G}\), to prevent spurious explanations that produce the same outcomes due to different causes. Concretely, finding \(\mathcal{G}^{\prime}\) that maximize \(S_{1}\) can be formalized as:

\[\min_{\mathcal{G}^{\prime}}-I(\mathcal{G},\mathcal{G}^{\prime}, \hat{Y}),\] (16) s.t. \[\mathcal{G}^{\prime}\sim \mathcal{P}(\mathcal{G},\mathbf{M}_{A},\mathbf{M}_{F})\quad \mathcal{R}(\mathbf{M}_{F},\mathbf{M}_{A})\leq c\]

### _Connecting to Our Method_

\(I(\mathcal{G},\mathcal{G}^{\prime},\hat{Y})\) is intractable as the latent generation mechanism of \(\mathcal{G}\) is unknown. In this part, we expand this objective, connect it to Equation 6, and construct its proxy optimizable form as:

\[I(\mathcal{G},\mathcal{G}^{\prime},\hat{Y}) =\sum_{y\sim\mathcal{Y}}\sum_{\mathcal{G}}\sum_{\mathcal{G}^{ \prime}}P(\mathcal{G},\mathcal{G}^{\prime},y)\] \[\quad\cdot\log\frac{P(\mathcal{G}^{\prime},y)P(\mathcal{G}, \mathcal{G}^{\prime})P(\mathcal{G},y)}{P(\mathcal{G},\mathcal{G}^{\prime},y)P( \mathcal{G})P(\mathcal{G}^{\prime})P(y)}\] \[=\sum_{y\sim\mathcal{Y}}\sum_{\mathcal{G}^{\prime}}P(\mathcal{G},\mathcal{G}^{\prime},y)\cdot\log\frac{P(\mathcal{G},\mathcal{G}^{\prime})}{P( \mathcal{G})P(\mathcal{G}^{\prime})}\] \[\quad+\sum_{\mathcal{G}^{\prime}}\sum_{\mathcal{G}^{\prime}}P( \mathcal{G},\mathcal{G}^{\prime})\cdot\log\frac{P(\mathcal{G},\mathcal{G}^{ \prime})}{P(\mathcal{G})P(\mathcal{G}^{\prime})}\] \[\quad-\sum_{\mathcal{G}^{\prime}}\sum_{y\sim\mathcal{Y}}\sum_{ \mathcal{G}}P(\mathcal{G},y,\mathcal{G}^{\prime})\cdot\log\frac{P(\mathcal{G}, y,\mathcal{G}^{\prime})}{P(\mathcal{G},y)P(\mathcal{G}^{\prime})}]\] \[= I(\mathcal{G}^{\prime},\hat{Y})+I(\mathcal{G},\mathcal{G}^{\prime})\] \[-\sum_{y\sim\mathcal{Y}}\sum_{\mathcal{G}}P(\mathcal{G},y)\sum_{ \mathcal{G}^{\prime}}P(\mathcal{G}^{\prime}|\mathcal{G},y)\cdot\log P(\mathcal{ G}^{\prime}|\mathcal{G},y)\] \[+\sum_{\mathcal{G}^{\prime}}\sum_{y\sim\mathcal{Y}}\sum_{ \mathcal{G}}P(\mathcal{G},y,\mathcal{G}^{\prime})\cdot\log P(\mathcal{G}^{ \prime})\] \[= I(\mathcal{G}^{\prime},\hat{Y})+I(\mathcal{G},\mathcal{G}^{\prime} )+H(\mathcal{G}^{\prime}|\mathcal{G},\hat{Y})-H(\mathcal{G}^{\prime}).\]

Since both \(H(\mathcal{G}^{\prime}|\mathcal{G},\hat{Y})\) and \(H(\mathcal{G}^{\prime})\) depicts entropy of explanation \(\mathcal{G}^{\prime}\) and are closely related to perturbation budgets, we can neglect these two terms and get a surrogate optimization objective for \(\max_{\mathcal{G}^{\prime}}I(\mathcal{G},\mathcal{G}^{\prime},\hat{Y})\) as \(\max_{\mathcal{G}^{\prime}}I(\hat{Y},\mathcal{G}^{\prime})+I(\mathcal{G}^{ \prime},\mathcal{G})\).

In \(\max_{\mathcal{G}^{\prime}}I(\hat{Y},\mathcal{G}^{\prime})+I(\mathcal{G}^{ \prime},\mathcal{G})\), the first term \(\max_{\mathcal{G}^{\prime}}I(\hat{Y},\mathcal{G}^{\prime})\) is the same as Eq.(1). Following [12], We relax it as \(\min_{\mathcal{G}^{\prime}}H_{C}(\hat{Y},\hat{Y}^{\prime}|\mathcal{G}^{\prime})\), optimizing \(\mathcal{G}^{\prime}\) to preserve original prediction outputs. The second term, \(\max_{\mathcal{G}^{\prime}}I(\mathcal{G}^{\prime},\mathcal{G})\), corresponds to maximizing consistency between \(\mathcal{G}^{\prime}\) and \(\mathcal{G}\). Although the graph generation process is latent, with the safe assumption that embedding \(\mathbf{E}_{\mathcal{G}}\) extracted by \(f\) is representative of \(\mathcal{G}\), we can construct a proxy objective \(\max_{\mathcal{G}^{\prime}}I(\mathbf{E}_{\mathcal{G}^{\prime}},\mathbf{E}_{ \mathcal{G}})\), improving the consistency in the embedding space. In this work, we optimize this objective by aligning their representations, either optimizing a simplified distance metric or conducting distribution-aware alignment.

## 8 Experiment

In this section, we conduct a set of experiments to evaluate the benefits of the proposed auxiliary task in providing instance-level post-hoc explanations. Experiments are conducted on \(5\) datasets, and obtained explanations are

Fig. 3: Illustration of our proposed new objective.
evaluated with respect to both faithfulness and consistency. Particularly, we aim to answer the following questions:

* **RQ1** Can the proposed framework perform strongly in identifying explanatory sub-structures for interpreting GNNs?
* **RQ2** Is the consistency problem severe in existing GNN explanation methods? Could the proposed embedding alignment improve GNN explainers over this criterion?
* **RQ3** Can our proposed strategies prevent spurious explanations and be more faithful to the target GNN model?

### _Experiment Settings_

#### 8.1.1 Datasets

We conduct experiments on five publicly available benchmark datasets for explainability of GNNs. The key statistics of the datasets are summarized in Table I.

* BA-Shapes [12]: A node classification dataset with a Barabasi-Albert (BA) graph of \(300\) nodes as the base structure. \(80\) "house" motifs are randomly attached to the base graph. Nodes in the base graph are labeled as \(0\) and those in the motifs are labeled based on positions. Explanations are conducted on those attached nodes, with edges inside the corresponding motif as ground-truth.
* Tree-Grid [12]: A node classification dataset created by attaching \(80\) grid motifs to a single \(8\)-layer balanced binary tree. Nodes in the base graph are labeled as \(0\) and those in the motifs are labeled as \(1\). Edges inside the same motif are used as ground-truth explanations for nodes from class 1.
* Infection [51]: A single network initialized with an ER random graph. \(5\%\) of nodes are labeled as infected, and other nodes are labeled based on their shortest distances to those infected ones. Labels larger than 4 are clipped. Following [51], infected nodes and nodes with multiple shortest paths are neglected. For each node, its shortest path is used as the ground-truth explanation.
* Mutag [12]: A graph classification dataset. Each graph corresponds to a molecule with nodes for atoms and edges for chemical bonds. Molecules are labeled with consideration of their chemical properties, and discriminative chemical groups are identified using prior domain knowledge. Following PGExplainer [13], chemical groups \(NH_{2}\) and \(NO_{2}\) are used as ground-truth explanations.
* Graph-SST5 [18]: A graph classification dataset constructed from text, with labels from sentiment analysis. Each node represents a word and edges denote word dependencies. In this dataset, there is no ground-truth explanation provided, and heuristic metrics are usually adopted for evaluation.

#### 8.1.2 Baselines

To evaluate the effectiveness of the proposed framework, we select a group of representative and state-of-the-art instance-level post-hoc GNN explanation methods as baselines. The details are given as follows:

* GRAD [13]: A gradient-based method, which assigns importance weights to edges by computing gradients of GNN's prediction w.r.t the adjacency matrix.
* ATT [13]: It utilizes average attention weights inside self-attention layers to distinguish important edges.
* GNNExplainer [12]: A perturbation-based method which learns an importance matrix separately for every instance.
* PGExplainer [13]: A parameterized explainer that learns a GNN to predict important edges for each graph, and is trained via testing different perturbations;
* Gem [45]: Similar to PGExplainer but from the causal view, based on the estimated individual causal effect.
* RG-Explainer [43]: A reinforcement learning (RL) enhanced explainer for GNN, which constructs \(\mathcal{G}^{\prime}\) by sequentially adding nodes with an RL agent.

Our proposed algorithms in Section 5.2 are implemented and incorporated into two representative GNN explanation frameworks, i.e., GNNExplainer [12] and PGExplainer [13].

#### 8.1.3 Configurations

Following existing work [13], a three-layer GCN [6] is trained on each dataset as the target model, with the train/validation/test data split as 8:1:1. For graph classification, we concatenate the outputs of global max pooling and global mean pooling as the graph representation. All explainers are trained using ADAM optimizer with weight decay set to \(5e\)-\(4\). For GNNExplainer, learning rate is initialized to \(0.01\) with training epoch being \(100\). For PGExplainer, learning rate is initialized to \(0.003\) and training epoch is set as \(30\). Hyper-parameter \(\lambda\), which controls the weight of \(\mathcal{L}_{align}\), is tuned via grid search. Explanations are tested on all instances.

#### 8.1.4 Evaluation Metrics

To evaluate _faithfulness_ of different methods, following [18], we adopt two metrics: (1) AUROC score on edge importance and (2) Fidelity of explanations. On benchmarks with oracle explanations available, we can compute the AUROC score on identified edges as the well-trained target GNN should follow those predefined explanations. On datasets without ground-truth explanations, we evaluate explanation quality with fidelity measurement following [18]. Concretely, we observe prediction changes by sequentially removing edges following assigned importance weight, and a faster performance drop represents stronger fidelity.

To evaluate _consistency_ of explanations, we randomly run each method \(5\) times, and report average structural hamming distance (SHD) [52] among obtained explanations. A smaller SHD score indicates stronger consistency.

### _Explanation Faithfulness_

To answer **RQ1**, we compare explanation methods in terms of AUROC score and explanation fidelity.

#### 8.2.1 AUROC on Edges

In this subsection, AUROC scores of different methods are reported by comparing assigned edge importance

\begin{table}
\begin{tabular}{l|c c c c c} \hline  & BA- & Tree- & Infection & Mutag & SST-5 \\  & Shapes & Grid & & & \\ \hline Level & Node & Node & Node & Graph & Graph \\ \hline Graphs & \(1\) & \(1\) & \(1\) & \(4,337\) & \(11,855\) \\ Avg.Node & \(700\) & \(1,231\) & \(1,000\) & \(30.3\) & \(19.8\) \\ Avg.Edge & \(4,110\) & \(3,410\) & \(4,001\) & \(61.5\) & \(18.8\) \\ \hline Classes & \(4\) & \(2\) & \(5\) & \(2\) & \(5\) \\ \hline \end{tabular}
\end{table} TABLE I: Statistics of datasets
weight with ground-truth explanations. For baseline methods GRAD, ATT, Gem, and RG-Explainer, their performances reported in their original papers are presented. GNNExplainer and PGExplainer are re-implemented, upon which four alignment strategies are instantiated and tested. Each experiment is conducted \(5\) times, and we summarize the average performance in Table II. A higher AUROC score indicates more accurate explanations. From the results, we can make the following observations:

* Across all four datasets, with both GNNExplainer or PGExplainer as the base method, incorporating embedding alignment can improve the quality of obtained explanations;
* Among proposed alignment strategies, those distribution-aware approaches, particularly the variant based on Gaussian mixture models, achieve the best performance. In most cases, the variant utilizing latent Gaussian distribution demonstrates stronger improvements, showing the best results on \(3\) out of \(4\) datasets;
* On more complex datasets like Mutag, the benefit of introducing embedding alignment is more significant, e.g., the performance of PGExplainer improves from 83.7% to 95.9% with Align_Gaus. This result also indicates that spurious explanations are severer with increased dataset complexity.

#### 8.2.2 Explanation Fidelity

In addition to comparing to ground-truth explanations, we also evaluate the obtained explanations in terms of fidelity. Specifically, we sequentially remove edges from the graph by following importance weight learned by the explanation model and test the classification performance. Generally, the removal of really important edges would significantly degrade the classification performance. Thus, a faster performance drop represents stronger fidelity. We conduct experiments on Tree-Grid and Graph-SST5. Each experiment is conducted \(3\) times and we report results averaged across all instances on each dataset. PGExplainer and GNNExplainer are used as the backbone method. We plot the curves of prediction accuracy concerning the number of removed edges in Fig. 4. From the figure, we can observe that when the proposed embedding alignment is incorporated, the classification accuracy from edge removal drops much faster, which shows that the proposed embedding alignment can help to identify more important edges used by GNN for classification, hence providing better explanations. Furthermore, distribution-aware alignment strategies like the variant based on Gaussian mixture models demonstrate stronger fidelity in most cases. Besides, it can be noted that on Tree-Grid the fidelity of mutual-information-based alignment is dependent on the number of edges, and achieves better results with edge number within \([8,15]\).

From these two experiments, we can observe that embedding alignment can obtain explanations of better faithfulness and is flexible to be incorporated into various models such as GNNExplainer and PGExplainer, which answers RQ1.
PGExplainer. These results validate the effectiveness of our proposal in obtaining consistent explanations.

### _Ability in Avoiding Spurious Explanations_

Existing graph explanation benchmarks are usually designed to be less ambiguous, containing only one oracle cause of labels, and identified explanatory substructures are evaluated via comparing with the ground-truth explanation. However, this result could be misleading, as faithfulness of explanation in more complex scenarios is left untested. Real-world datasets are usually rich in spurious patterns and a trained GNN could contain diverse biases, setting a tighter requirement on explanation methods. Thus, to evaluate if our framework can alleviate the spurious explanation issue and answer **RQ3**, we create a new graph-classification dataset: MixMotif, which enables us to train a biased GNN model, and test whether explanation methods can successfully expose this bias.

Specifically, inspired by [14], we design three types of base graphs, i.e., Tree, Ladder, and Wheel, and three types of motifs, i.e., Cycle, House, and Grid. With a mix ratio \(\gamma\), motifs are preferably attached to base graphs. For example, Cycle is attached to Tree with probability \(\frac{2}{3}\gamma+\frac{1}{3}\), and to others with probability \(\frac{1-\gamma}{3}\). So are the cases for House to Ladder and Grid to Wheel. Labels of obtained graphs are set as type of the motif. When \(\gamma\) is set to \(0\), each motif has the same probability of being attached to the three base graphs. In other words, there's no bias on which type of base graph to attach for each type of motif. Thus, we consider the dataset with \(\gamma=0\) as clean or bias-free. We would expect GNN trained on data with \(\gamma=0\) to focus on the motif structure for motif classification. However, when \(\gamma\) becomes larger, the spurious correlation between base graph and the label would exist, i.e., a GNN might utilize the base graph structure for motif classification instead of relying on the motif structure. For each setting, the created dataset contains \(3,000\) graphs, and train:evaluation:test are split as \(5:2:3\).

In this experiment, we set \(\gamma\) to \(0\) and \(0.7\) separately, and train GNN \(f_{0}\) and \(f_{0.7}\) for each setting. Two models are tested in graph classification performance. Then, explanation methods are applied to and fine-tuned on \(f_{0}\). Following that, these explanation methods are applied to explain \(f_{0.7}\) using found hyper-parameters. Results are summarized in Table V.

From Table V, we can observe that (1) \(f_{0}\) achieves almost perfect graph classification performance during testing. This high accuracy indicates that it captures the genuine pattern, relying on motifs to make predictions. Looking at explanation results, it is shown that our proposal offers more faithful explanations, achieving higher AUROC on motifs. (2) \(f_{0.7}\) fails to predict well with \(\gamma=0\), showing that there are biases in it and it no longer depends solely on the motif structure for prediction. Although ground-truth explanations are unknown in this case, a successful explanation should expose this bias. However, PGExplainer would produce similar explanations as the clean model, still highly in accord with motif structures. Instead, for explanations produced by embedding alignment, AUROC score would drop from \(0.795\) to \(0.266\), exposing the change in prediction rationales, hence able to expose biases. (3) In summary, our proposal can provide more faithful explanations for both clean and mixed settings, while PGExplainer would suffer from spurious explanations and fail to faithfully explain GNN's predictions, especially in the existence of biases.

### _Hyperparameter Sensitivity Analysis_

In this part, we vary the hyper-parameter \(\lambda\) to test the sensitivity of the proposed framework toward its values. \(\lambda\) controls the weight of our proposed embedding alignment task. To keep simplicity, all other configurations are kept unchanged, and \(\lambda\) is varied within the scale \([1e-3,1e-2,1e-1,1,10,1e2,1e3)\). PGExplainer is adopted as the base method. Experiments are randomly conducted \(3\) times on dataset Tree-Grid and Mutag. Averaged results are visualized in Figure 5. From the figure, we can make the following observations:

* For all four variants, increasing \(\lambda\) has a positive effect at first, and the further increase would result in a performance drop. For example on the Tree-Grid dataset, best results of variants based on anchors, latent Gaussian mixture models and mutual information scores are all obtained with \(\lambda\) around \(1\). When \(\lambda\) is small, the explanation alignment regularization in Eq. 6 will be underweighted.

\begin{table}
\begin{tabular}{l|c c c c c c} \hline  & \multicolumn{5}{c}{Top-K Edges} \\ \hline Methods & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline GNNExplainer & 1.12 & 1.74 & 2.65 & 3.40 & 4.05 & 4.78 \\ +Align\_Emb & 1.05 & 1.61 & 2.33 & 3.15 & 3.77 & 4.12 \\ +Align\_Anchor & 1.06 & 1.59 & 2.17 & 3.06 & 3.54 & 3.95 \\ \hline +Align\_MI & 1.11 & 1.68 & 2.42 & 3.23 & 3.96 & 4.37 \\ +Align\_Gaus & 1.03 & 1.51 & 2.19 & 3.02 & 3.38 & 3.85 \\ \hline PGExplainer & 0.91 & 1.53 & 2.10 & 2.57 & 3.05 & 3.42 \\ +Align\_Emb & 0.55 & 0.96 & 1.13 & 1.31 & 1.79 & 2.04 \\ +Align\_Anchor & **0.51** & **0.90** & **1.05** & 1.27 & 1.62 & 1.86 \\ \hline +Align\_MI & 0.95 & 1.21 & 1.73 & 2.25 & 2.67 & 2.23 \\ +Align\_Gaus & 0.59 & 1.34 & 1.13 & **0.84** & **1.25** & **1.15** \\ \hline \end{tabular}
\end{table} TABLE IV: Consistency of explanation in terms of average SHD distance across \(5\) rounds of random running on Mutag.

\begin{table}
\begin{tabular}{l|c c c c c} \hline  & \multicolumn{5}{c}{Top-K Edges} \\ \hline Methods & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline GNNExplainer & 0.86 & 1.85 & 2.48 & 3.14 & 3.77 & 4.39 \\ +Align\_Emb & 0.77 & 1.23 & 1.28 & 0.96 & 1.81 & 2.72 \\ +Align\_Anchor & 0.72 & 1.06 & 0.99 & 0.53 & 1.52 & 2.21 \\ \hline +Align\_MI & 0.74 & 1.11 & 1.08 & 1.32 & 1.69 & 2.27 \\ +Align\_Gaus & 0.68 & 1.16 & 1.13 & 0.72 & 1.39 & 2.13 \\ \hline PGExplainer & 0.74 & 1.23 & 0.76 & 0.46 & 0.78 & 1.38 \\ +Align\_Emb & 0.11 & 0.15 & 0.13 & **0.11** & 0.24 & 0.19 \\ +Align\_Anchor & 0.07 & 0.12 & 0.13 & 0.16 & 0.21 & **0.13** \\ \hline +Align\_MI & 0.28 & 0.19 & 0.27 & 0.15 & 0.20 & 0.16 \\ +Align\_Gaus & **0.05** & **0.08** & **0.10** & 0.12 & **0.19** & **0.13** \\ \hline \end{tabular}
\end{table} TABLE III: Consistency of explanation in terms of average SHD across \(5\) rounds of random running on Tree-Grid.

\begin{table}
\begin{tabular}{l|c|c} \(\gamma\) in Training \\ \hline \hline Classification & \(0\) & \(0.7\) \\ \(\gamma\) in test & \(0\) & \(0.982\) & \(0.765\) \\  & \(0.78\) & \(0.994\) \\ \hline Explanation & PGExplainer +Align & PGExplainer +Align \\ \hline AUROC & \(0.711\) & \(\mathbf{0.795}\) & \(0.748\) & \(\mathbf{0.266}\) \\ on Motif & (Higher is better) & (Lower is better) \\ \hline \end{tabular}
\end{table} TABLE V: Performance on MixMotif. Two GNNs are trained with different \(\gamma\). We check their performance in graph classification, then compare obtained explanations with the motif.
On the other hand, a too-large \(\lambda\) may underweight the MMI-based explanation framework, which preserves the predictive power of obtained explanations.
* Among these variants, the strategy based on latent Gaussian mixture models shows the strongest performance in most cases. For example, for both datasets Tree-Grid and Mutag, this variant achieves the highest AUROC scores on identified explanatory edges. On the other hand, the variant directly using Euclidean distances shows inferior performances in most cases. We attribute this to their different ability in modeling the distribution and conducting alignment.

## 9 Conclusion

In this work, we study a novel problem of obtaining faithful and consistent explanations for GNNs, which is largely neglected by existing MMI-based explanation framework. With close analysis on the inference of GNNs, we propose a simple yet effective approach by aligning internal embeddings. Theoretical analysis shows that it is more faithful in design, optimizing an objective that encourages high MI between the original graph, GNN output, and identified explanation. Four different strategies are designed, by directly adopting Euclidean distance, using anchors, KL divergence with Gaussian mixture models, and estimated MI scores. All these algorithms can be incorporated into existing methods with no effort. Experiments validate their effectiveness in promoting the faithfulness and consistency of explanations.

In the future, we will seek more robust explanations. Increased robustness indicates stronger generality, and could provide better class-level interpretation at the same time. Besides, the evaluation of explanation methods also needs further studies. Existing benchmarks are usually clear and unambiguous, failing to simulate complex real-world scenarios.

## Acknowledgments

This material is based upon work supported by, or in part by, the National Science Foundation under grants number IIS-1707548 and IIS-1909702, the Army Research Office under grant number W911NF21-1-0198, and DHS CINA under grant number E205949D. The findings and conclusions in this paper do not necessarily reflect the view of the funding agency.
