Reinforced Causal Explainer for Graph Neural Networks

Following previous work [43], we frame the causal screening process as a Markov Decision Process (MDP) $M=\{\mathcal{S},\mathcal{A},P,R\}$. Herein, $\mathcal{S}=\{s_{k}\}$ is the set of states abstracting edge sequences during exploration, and $\mathcal{A}=\{a_{k}\}$ is the set of actions, which adds an edge to the current edge sequences at each step. Under the Markov property [43, 45], $P(s_{k}|s_{k-1},a_{k})$ is the transition dynamics that specifies the new edge sequence $s_{k}$ after making an action of edge addition $a_{k}$ on the prior state $s_{k-1}$. $R(s_{k-1},a_{k})$ is to quantify the reward after making the action $a_{k}$ from the prior state $s_{k-1}$. As such, the trajectory $(s_{0},a_{1},r_{1},s_{1},\cdots,a_{K},r_{K},s_{K})$ naturally depicts the generation of an edge sequence, where the step-wise reward $r_{K}$ reflects $a_{K}$’s causal effect and coalition effect with the previously-added edges. Note that, various graphs with the model predictions describe different environments being explored by the RL agent. Here we elaborate the foregoing key elements for one target graph $\mathcal{G}$ and its prediction $\hat{y}_{c}$ as follows.

Having outlined the causal screening environment, we now present the policy network $q_{\phi}$ of RC-Explainer to explore in the environment. Specifically, it takes the pair of intermediate state $G_{k-1}$ and the target prediction $\hat{y}_{c}$ as the input, and aims to determine the next action $e_{k}$:

where $\phi$ summarizes the trainable parameters of the policy network; $e_{k}$ is yielded with the probability $P_{\phi}(e_{k}|\mathcal{G}_{k-1},\hat{y}_{c})$ of being added to the explanatory subgraph.

Thereafter, we apply a softmax function over all action candidates $\mathcal{A}_{k}$ to convert their importance scores into the probability distribution. Formally, the probability of $e_{k}$ being selected as the action is as:

where $\phi$ collects parameters of $g_{\mu}$, MLP₁, and $\{\text{MLP}_{2,c}\}_{c=1}^{C}$. It is worth mentioning that the class-wise MLPs latch on class-wise knowledge across the training graphs with the same prediction.

However, SGD cannot be directly used for the optimization, since the discrete sampling within the policy network blocks gradients. To solve this issue, we adopt the policy gradient-based training framework, REINFORCE [46, 43], to optimize the policy network as follows:

Obviously, this training framework encourages the actions with large rewards — sequentially finding the edges with the salient causal attributions to construct the explanatory subgraph.

As a result, our RC-Explainer inherits the desired characteristics of causal screening, which considers the causal effects of edges and the dependencies among edges. Furthermore, RC-Explainer is optimized on all graphs in the training set; thus, it holds a global view of the target model’s inner workings and achieves better generalization ability to generate explanations for unseen graph instances.

When explaining one graph $\mathcal{G}$, the time cost mainly comes from the two components: (1) the representation learning of node representations, (2) the step-wise representation learning of edge candidates and action prediction. Specifically, using a trainable GNN model $g_{\mu}$ to generate node representations has computational complexity $O(\sum_{l=1}^{L}|\mathcal{G}|\times d_{l}\times d_{l-1})$, where $d_{l}$ is the representation dimension at $l$-th layer. At each step $k$, the time cost is $O(|\mathcal{A}_{k}|\times 2d^{\prime}\times d^{\prime\prime})$ for creating representations of edge candidates, while being $O(|\mathcal{A}_{k}|\times d^{\prime\prime})$ for predicting one action. As a result, the cost of generating the explanation $\mathcal{G}_{K}$ is $O(\sum_{k=1}^{K}|\mathcal{A}_{k}|\times(2d^{\prime}\times d^{\prime\prime}+d^{\prime\prime}))$. In total, the time complexity of the whole training episode is $O(\sum_{\mathcal{G}\in\mathcal{O}}(\sum_{l=1}^{L}|\mathcal{G}|\times d_{l}\times d_{l-1}+\sum_{k=1}^{K}|\mathcal{A}_{k}|\times(2d^{\prime}\times d^{\prime\prime}+d^{\prime\prime})))$, where $\mathcal{O}$ is the training set.

We list two potential limitations RC-Explainer might face, expensive time complexity and out-of-distribution issue:

• •

  Although RC-Explainer benefits from reinforcement learning and is more efficient than the exhaustive search, it might still suffer from the high computational cost, when generating the sampling probabilities over the large action space. See Section 5.2.4 for the evaluations w.r.t. empirical time complexity. It limits RC-Explainer’s development on large scale graphs. Hence we leave the pruning of action space and the improvement of scalability in future work, such as pre-judging the probability of edges being selected and extracting a small set of edges as the action candidates.

• •

  The causal attributions of holistic subgraph (cf. Equation (6)) and edge sequence (cf. Equation (4.2)) are founded upon on the feature removal principle [47] — that is, the complement of the subgraph is discarded, while the target model takes the subgraph as the input only. Nonetheless, feature removal makes subgraphs off the distribution of the full graphs, thus causing the out-of-distribution (OOD) issue. The OOD subgraph hardly follows the degree distribution [48], graph sizes [49] or possibly violates constraints [45]. As a result, the OOD issue could bring a spurious correlation between the true importance of subgraph and the model prediction, making the ICE estimation unfaithful and unreliable. See Section 5.2.5 for the failure cases, where the explanations suffer from the OOD effect. We will explore the solution to the OOD issue in future work, such as using the counterfactual generation to fulfil the subgraph and make it conform to the original distribution

We use three benchmark datasets in the experiments:

• •

  Mutagenicity [50, 51] has $4,377$ molecule graphs, where each graph is labeled with one of two labels: mutagenic and non-mutagenic, based on the mutagenic effect on a bacterium. We trained a GIN model [23, 52] to perform the binary classification.

• •

  REDDIT-MULTI-5K [53] has $4,999$ social networks labeled with five different classes to indicate the topics of question/answer communities. Upon them, we trained a k-GNN model [54] as a classifier.

• •

  Visual Genome [55] is a collection of images. Each image is coupled with a scene graph, where nodes are the objects with bounding boxes and edges are the relations between objects. Following the previous work [14], we extract $4,443$ (images, scene graphs) pairs covering five classes: stadium, street, farm, surfing, forest. A GNN model, APPNP [56], is trained as a classifier, where the regional images are treated as the node features.

Table I shows the statistics of datasets with the configurations of GNN models. We follow prior studies [14, 16] and partition each dataset into training, validation, and testing sets with the ratio of $80\%$:$10\%$:$10\%$. Having obtained the trained GNNs on the training sets, we train the parametric explainers on the training sets, and tune their hyper-parameters on the validation sets. We run the explainers five times on the testing sets to report the average results.

It is of crucial importance to evaluate the explanations quantitatively. However, the ground-truth knowledge of explanations is usually unavailable in real-world datasets. Hence, many prior works [33, 57, 58, 12] have proposed some metrics to assess the explanations without the ground truth. Here we adopt two widely-adopted metrics:

• •

  Predictive Accuracy [33, 57] (ACC@$\mu$) is to measure whether using the explanatory subgraph can successfully recover the target prediction:

  $$\displaystyle\text{ACC($\mu$)}=\mathbb{E}_{\mathcal{G}\sim\mathbb{G}}[\mathbb{I}(f(\mathcal{G}),f(\mathcal{G}^{*}_{K}))],$$

  (14)

  where $\mu$ is the selection ratio (e.g., $5\%$), $K=\lceil\mu\times|\mathcal{G}|\rceil$ is the size of explanatory subgraph; $\mathbb{I}(\cdot)$ is the indicator function to check whether $f(\mathcal{G})$ equals to $f(\mathcal{G}^{*}_{K})$. Moreover, we also report the ACC curve over different selection ratios $[0.1,0.2,\cdots,1.0]$ and denote the area under curve as ACC-AUC.

• •

  Contrastivity [14] (CST) quantifies the invariance between class-discriminative explanations. It is built upon the intuition that a reasonable method should yield differing explanations, in response to the target prediction changes. Here we formulate it as the Spearman rank correlation between class-discriminative edge scores:

  $$\displaystyle\text{CST}=\mathbb{E}_{\mathcal{G}\sim\mathbb{G}}\mathbb{E}_{s\neq\hat{y}}[|\rho(\Phi(\mathcal{G},s),\Phi(\mathcal{G},\hat{y}))|],$$

  (15)

  where $s$ means we permute the label $\hat{y}$ of $\mathcal{G}$ being interpreted; $\Phi(\mathcal{G},\hat{y})$ is the attribution scores of all edges; $|\rho(\cdot)|$ is the Spearman rank correlation with the absolute value to measure the invariance between the edge attributions, in response to the label changes.

Moreover, as suggested in the prior study [12], the explanations generated by a reasonable explainer should be dependent on the target model — that is, presenting a faithful understanding of how the target model works. Hence we also conduct sanity check:

• •

  Sanity Check on model randomization is to compare the attribution scores on the trained GNN $f$ with that on an untrained GNN $\hat{f}$ with randomly-initialized parameters. Similar attributions infer that the explainer is insensitive to the model changes, thus fails to pass the check. Here we frame it as the rank correlation between these two attributions:

  $$\displaystyle\text{SC}=\mathbb{E}_{\mathcal{G}\sim\mathbb{G}}[|\rho(\Phi(\mathcal{G},f(\mathcal{G})),\Phi(\mathcal{G},\tilde{f}(\mathcal{G})))|].$$

  (16)

  Similar attributions infer the explainer is insensitive to properties of the model, thus failing to pass the check.

We compare RC-Explainer with the state-of-the-art explainers, covering the gradient-based (SA [13], Grad-CAM[14]), masking-based (GNNExplainer [16]), attention-based (PGExplainer [17]), and perturbation-based (CXPlain [20], PGM-Explainer[19]).

To facilitate reproducibility, we release codes and datasets at https://github.com/xiangwang1223/reinforced_causal_explainer, and summarize the hyperparameter settings in the supplementary material. For nonparametric methods (SA and Grad-CAM), we use the codes released by the original papers [13, 14]. For the other parametric methods, we conduct a grid search to confirm the optimal settings for each method. To be more specific, the optimizer is set as Adam, the learning rate is tuned in $\{10^{-3},10^{-2},10^{-1}\}$, and the weight decay is searched in $\{10^{-5},10^{-4},10^{-3}\}$. Other model-specific hyperparameters are set as follows: For GNNExplainer, the weight of mutual information is fixed as $0.5$; For PGExplainer, the temperature for reparameterization is $0.1$; For PGM-Explainer, the number of perturbations is tuned in $\{10,100,1000\}$ with different perturbation modes.

Table II reports the empirical results w.r.t. ACC@$10\%$ and ACC-AUC, and Figure 3 demonstrates the ACC curves over different selection ratios. We find that:

• •

  RC-Explainer outperforms the compared baselines by a large margin across all three datasets, when only $10\%$ of edges are selected as the explanatory subgraphs. For example, it achieves significant improvements over the strongest baselines w.r.t. ACC@$10\%$ by $13.59\%$ and $25.51\%$ in Mutagenicity and REDDIT-MULTI-5K, respectively. This verifies the rationality and effectiveness of RC-Explainer. We ascribe these improvements to two key characteristics of causal screening: (1) Assessing the causal effects of edges enables us to better distinguish the causal relationships from the spurious correlations between input edges and model outputs, thus encouraging causal explainability instead of statistical interpretability; (2) Benefiting from the screening strategy, RC-Explainer can reveal the dependencies of the candidate edges and the previous selections. It allows us to identify and explicit the coalition effect of edges, and reduce the redundancy in explanations.

• •

  The explanatory subgraphs derived from RC-Explainer are influential to the model predictions. Especially, in Mutagenicity and REDDIT-MULTI-5K, RC-Explainer’s ACC-AUC scores are $0.964$ and $0.901$, close to the optimal fidelity. This validates that RC-Explainer faithfully reflects the workings of the target GNNs.

• •

  As Figure 3 shows, increasing the selection ratios might decrease RC-Explainer’s predictive accuracy. This again justifies the rationality of our causal screening: when the causal determinants or coalitions have been selected, adding more noncausal or redundant edges has only a negligible impact on the accuracy.

• •

  Analyzing the ACC curves and ACC-AUC scores in Visual Genome, we find that RC-Explainer only achieves comparable performance to Grad-CAM. One possible reason is that node features could be more informative about scenes than the existence of edges. Taking Figure 4 as an example, the visual features of the road node might be sufficient to predict the street scene. Hence, Grad-CAM benefits from the context-enhanced gradients that capture the node features thus achieves high-quality explanations. It inspires us to further investigate the cooperation of node feature and graph structure in the explanation generation.

• •

  In general, the line of causal explainability (i.e., CXPlain, PGM-Explainer, RC-Explainer) performs better than the line of statistical explainability (i.e., SA, Grad-CAM, GNNExplainer, PGExplainer). Because using gradients, masks, or attentions is prone to capturing the spurious input-output correlations and missing the causation. This is consistent with prior studies [20, 19].

• •

  Within the line of causal explainability, RC-Explainer outperforms CXPlain and PGM-Explainer, suggesting that screening to combine an edge with the previous selection estimates the edges’ causal effects more accurately. This emphasizes the effectiveness of considering edge dependencies.

We move on to the contrastivity reported in Table III to check how explanations differ when the target predictions change. We find that: (1) Over all approaches, RC-Explainer achieves the lowest and the second-lowest CST scores in Visual Genome and Mutagenicity, respectively. This indicates that the explanations of RC-Explainer are class-discriminative, thus offering an understanding of the decision boundary between different classes. For instance, in REDDIT-MULTI-5K, different patterns of user behaviors can describe various topics of communities. See Section 5.2.5 for more supporting pieces of evidence; (2) Jointly inspecting the ACC curves in Figure 3, we observe that RC-Explainer will randomly pick up edges, once the most influential edges have been selected. These randomly-added edges could increase the ranking correlations of class-specific explanations, thus influencing the overall CST scores of RC-Explainer.

We then focus on the sanity checks presented in Table III and find that: (1) RC-Explainer achieves relatively low SC scores and safely passes the checks, indicating that the attributions on the trained and untrained GNNs differ significantly. This evidently shows that our feature attribution is dependent on the target GNN, which is necessary for faithfully interpreting the inner workings of the target model; (2) Jointly analyzing the SC scores across three datasets, we find that RC-Explainer is less sensitive to the target model’s status in Visual Genome. We conjecture that the untrained GNN still works as the kernel function to filter some useful information, thus somehow reflects the edge importance. We leave the justification of possible reasons for future work.

We present the actual runtime of all approaches in Table III, which reports the inference time to generate an explanation. Our findings are: (1) In Mutagenicity and Visual Genome, RC-Explainer computes the attribution scores significantly faster than GNNExplainer and PGM-Explainer. Because the policy network in RC-Explainer is shared across all graph instances, while GNNExplainer needs to retrain the attention network for each instance and PGM-Explainer requires a large number of random perturbations to generate explanations; (2) On REDDIT-MULTI-5K, RC-Explainer is slower on large-scale graphs due to the huge action space. We can solve this issue by pruning the action space, which is left to future work; (3) Gradient-based methods generate much faster than most parametric methods.

In this section, we conduct the visual inspections of two examples in Mutagenicity and Visual Genome to give an intuitive impression of explanations. As demonstrated in Figure 4, we find that:

• •

  RC-Explainer is able to capture the edges that plausibly cause the GNN’s prediction. For example, when interpreting the prediction of Street in Visual Genome, it assigns the most convincing edges (car, on, road) and (van, in, street) with the largest attribution scores. Whereas, the other methods easily distribute attention on tree- or human-related edges, as tree and human frequently occur with street. However, using such spurious correlations as causation fails to interpret the prediction reliably. This again verifies the importance of causal interpretability.

• •

  The sequential decision process enables RC-Explainer to measure the relationships of candidate edges and previous selections, thus identifying the coalition of edges and avoiding the redundant edges. For instance, when explaining the prediction of mutagenic in Mutagenicity, RC-Explainer can highlight the functional groups, such as two NO₂ chemical groups, responsible for the mutagenic property [59]. Whereas, at most one NO₂ is captured by the baselines, as they hardly consider the coalition effect of an edge combination. As for the non-mutagenic molecules, RC-Explainer tends to pick bonds like carbon-hydrogen (C-H). This makes sense because the GNN models will not predict the subgraphs with these chemical bonds as mutagenic.

• •

  Moreover, we probe the sequential decision process of generating explanations of mutagenic. Figure 5 illustrates the process, with step-wise rewards and probabilities of edges being added. Clearly, at the first two steps, RC-Explainer selects the N=O bonds from two groups; afterward, it completes the NO₂ groups by adding the other N=O bonds. Compared to the influential N=O bonds, others like C-H contribute less to the prediction.

• •

  We also present two failure cases of RC-Explainer in Figure 6, to show the potential out-of-distribution issue. In these cases of Visual Genome, RC-Explainer first picks up the most convincing edges (light, on, road) and (surfboard, on, water) when $\mu=0.1$, which can almost recover the target predictions of Street and Surfing. It then chooses (light, on, road) and (footprint, on, sand) when $\mu=0.2$, since these edges frequently occur with the target scenes. However, the later edges are not only redundant or spurious to introduce noises into the explanations, but also disjoint with the previous selection to make the subgraphs out of the original distribution. Such cases plausibly cause the fluctuations in the accuracy, especially the steep drop between $\mu=0.1$ and $\mu=0.2$ in Figure 3.