Towards Faithful and Consistent Explanations for Graph Neural Networks

Graph neural networks (GNNs) are developing rapidly in recent years, with the increasing need for learning on relational data structures (Fan et al., 2019; Dai et al., 2022a; Zhao et al., 2021). Generally, existing GNNs can be categorized into two categories, i.e., spectral-based approaches (Bruna et al., 2013; Tang et al., 2019; Kipf and Welling, 2016) based on graph signal processing theory, and spatial-based approaches (Duvenaud et al., 2015; Atwood and Towsley, 2016; Xiao et al., 2021) 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 (Gilmer et al., 2017). 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 (Hamilton et al., 2017; Zhang and Chen, 2018; Zhao et al., 2021). Explorations are made by disentangling the propagation process (Wang et al., 2020a; Zhao et al., 2022; Xiao et al., 2022) or utilizing external prototypes (Lin et al., 2022; Xu et al., 2022). 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.

Recently, some efforts have been taken to interpret GNN models and provide explanations for their predictions (Wang et al., 2020b). Existing methods can be generally grouped into two categories based on the granularity: (1) instance-level explanation (Ying et al., 2019), which provides explanations on the prediction for each instance by identifying important substructures; and (2) model-level explanation (Baldassarre and Azizpour, 2019; Zhang et al., 2021), 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 (Zhang et al., 2021; Dai and Wang, 2021), where the GNN can simultaneously give prediction and explanations on the prediction; and (2) post-hoc explanations (Ying et al., 2019; Luo et al., 2020; Yuan et al., 2021), 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 (Ying et al., 2019), 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  (Dai et al., 2022b).

A variety of strategies for post-hoc instance-level explanations have been explored in the literature, including utilizing signals from gradients (Pope et al., 2019; Baldassarre and Azizpour, 2019), perturbed predictions (Ying et al., 2019; Luo et al., 2020; Yuan et al., 2021; Shan et al., 2021), and decomposition (Baldassarre and Azizpour, 2019; Schnake et al., 2020). 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 (Yuan et al., 2020). The identified important substructure is used as an explanation for the prediction. For example, GNNExplainer (Ying et al., 2019) 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 (Luo et al., 2020) 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 (Yuan et al., 2021) employs Monte Carlo Tree Search (MCTS) to find connected subgraphs that preserve predictions as explanations.

Despite 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.

We use $\mathcal{G}=\{\mathcal{V},\mathcal{E};\mathbf{F},\mathbf{A}\}$ to denote a graph, where $\mathcal{V}=\{v_{1},\dots,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,\dots,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$ denote 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 defined as:

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. Typically, they can be summarized as Maximization of Mutual Information (MMI) between predicted label $\hat{Y}$ and explanation $\mathcal{G}^{\prime}$, i.e.,

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, $\hat{\mathbf{A}}=\mathbf{A}\odot\mathbf{M}_{A}$ and $\hat{\mathbf{F}}=\mathbf{Z}+(\mathbf{F}-\mathbf{Z})\odot\mathbf{M}_{F}$ in GNNExplainer (Ying et al., 2019), 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 (Luo et al., 2020). 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 (Ying et al., 2019) is often adopted as:

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

Different aspects regarding the quality of explanations can be evaluated (Nauta et al., 2022). 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. A detailed analysis will be provided in the next section.

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 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:

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:

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.

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 computation-friendly 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}^{l}_{v,i}\}_{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}^{l+1}_{v,i}/|\mathcal{V}^{\prime}_{i}|\}_{i=1}^{m}$ to get global graph representation.

• •

  Then, a clustering algorithm is applied to 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 (Ester et al., 1996) 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,k}^{l}=\|\mathbf{h}^{l+1}_{v}-\mathbf{h}^{l+1,k}_{v}\|_{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:

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:

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

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}-\hat{\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}^{l+1}_{v}/|\mathcal{V}^{\prime}|$, where $\mathcal{V}^{\prime}$ denotes node set after pooling.

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

One problem of spurious explanation is that, due to the randomness in initialization of the explainer, the explanation for the same instance given by a GNN explainer could be different for different runs, which violates the consistency of explanations. To test the severity of this problem and answer RQ2, we evaluate the proposed framework in terms of explanation consistency. We adopt GNNExplainer and PGExplainer as baselines. Specifically, SHD distance among explanatory edges with top-$k$ importance weights identified each time is computed. Then, the results are averaged for all instances in the test set. Each experiment is conducted $5$ times, and the average consistency on dataset Tree-Grid and Mutag are reported in Table 2 and Table 3, respectively. Larger distances indicate inconsistent explanations. From the table, we can observe that existing method following Equation 1 suffers from the consistency problem. For example, average SHD distance on top-$6$ edges is $4.39$ for GNNExplainer. Introducing the auxiliary task of aligning embeddings can significantly improve explainers in terms of this criterion. After incorporating anchor-based alignment on dataset TreeGrid, SHD distance of top-$6$ edges drops from $4.39$ to $2.21$ for GNNExplainer and from $1.38$ to $0.13$ for PGExplainer, which validates effectiveness of our proposal in obtaining consistent 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 methods 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  (Wu et al., 2022), 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. Labels are set as the type of motif. When $\gamma$ is set to $0$, each motif has the same probability of being attached to three base graphs. Thus, we consider the dataset with $\gamma=0$ as clean or bias-free. We would expect GNN trained with $\gamma=0$ to focus on the motif structure. 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.

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 4.

From Table 4, 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.

In this part, we vary the hyper-parameter $\lambda$ to test method’s sensitivity towards 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 as scale $[1e-3,1e-2,1e-1,1,10,1e2,1e3\}$. PGExplainer is adopted as the base method. Each experiment is conducted $3$ times on Tree-Grid and Mutag. Averaged results are visualized in Figure 5. From the figure, we can observe that increasing $\lambda$ has a positive effect at first, and the further increase would result in a performance drop. Besides, anchor-based alignment usually requires a smaller weight to show improvements.