RegExplainer: Generating Explanations for Graph Neural Networks in
  Regression Task
Graph regression is a fundamental task and has received increasing attention
in a wide range of graph learning tasks. However, the inference process is
often not interpretable. Most existing explanation techniques are limited to
understanding GNN behaviors in classification tasks. In this work, we seek an
explanation to interpret the graph regression models (XAIG-R). We show that
existing methods overlook the distribution shifting and continuously ordered
decision boundary, which hinders them away from being applied in the regression
tasks. To address these challenges, we propose a novel objective based on the
information bottleneck theory and introduce a new mix-up framework, which could
support various GNNs in a model-agnostic manner. We further present a
contrastive learning strategy to tackle the continuously ordered labels in
regression task. To empirically verify the effectiveness of the proposed
method, we introduce three benchmark datasets and a real-life dataset for
evaluation. Extensive experiments show the effectiveness of the proposed method
in interpreting GNN models in regression tasks.
Jiaxing Zhang, Zhuomin Chen, Hao Mei, Dongsheng Luo, Hua Wei
# RegExplainer: Generating Explanations for Graph Neural Networks in Regression Task

###### Abstract.

Graph regression is a fundamental task that has gained significant attention in various graph learning tasks. However, the inference process is often not easily interpretable. Current explanation techniques are limited to understanding GNN behaviors in classification tasks, leaving an explanation gap for graph regression models. In this work, we propose a novel explanation method to interpret the graph regression models (XAIG-R). Our method addresses the distribution shifting problem and continuously ordered decision boundary issues that hinder existing methods away from being applied in regression tasks. We introduce a novel objective based on the information bottleneck theory and a new mix-up framework, which could support various GNNs in a model-agnostic manner. Additionally, we present a contrastive learning strategy to tackle the continuously ordered labels in regression tasks. We evaluate our proposed method on three benchmark datasets and a real-life dataset introduced by us, and extensive experiments demonstrate its effectiveness in interpreting GNN models in regression tasks.

graph neural network, explainability, data augmentation +

[MISSING_PAGE_POST]
exist widely in nowadays applications, such as predicting the molecular property (Beng et al., 2017) or traffic flow volume (Kang et al., 2018). Therefore, it's crucial to provide high-quality explanations for the graph regression task.

Explaining the instance-level results of graph regression in a post-hoc manner is challenging due to two main obstacles: 1. the GIB objective in previous work is not applicable in the regression task; 2; the distribution shifting problem (Han et al., 2017; Wang et al., 2018; Wang et al., 2019; Wang et al., 2019).

\(\bullet\) One challenge is the mutual information estimation in the GIB objective. In previous works (Kang et al., 2018; Wang et al., 2019; Wang et al., 2019) for graph classification, the mutual information \(I(G^{*};Y)\) is estimated with the Cross-Entropy between the the predictions \(f(G^{*})\) from GNN model \(f\) and its prediction label \(Y\) from the original graph \(G\). However, in the regression task, the regression label is the continuous value, instead of categorized classes, making it difficult to be estimated with the cross entropy loss. Therefore, we adopt the GIB objective to employ the InfoNCE objective and contrastive loss to address this challenge and estimate the mutual information.

\(\bullet\) Another challenge is the distribution shifting problem, which means the explanation sub-graphs are out-of-distribution(OOD) of the original training graph dataset. As shown in Figure 1, a GNN model is trained on the original graph training set for a graph regression task. The previous work always assumes that the explanation sub-graph would contain the same mutual information as the original graph ideally. However, as seen in the figure, even when \(G\) and \(G^{*}\) both have two motifs as the label information, \(f(G^{*})\) is different from \(f(G)\) due to a different distribution. Due to the explanation sub-graph usually having a different topology and feature information compare to the original graph, the GNN model trained on the original graph set couldn't accurately predict with the explanation sub-graph, which means we couldn't directly estimate the mutual information between the original graph and the explanation sub-graph due to the distribution shifting problem.

In this paper, for the first time, we propose RegExplainer, to generate post-hoc instance-level explanations for graph regression tasks. Specifically, to address the distribution shifting issue, RegExplainer develops a mix-up approach to generate the explanation from a sub-graph into the mix-up graph without involving the label-preserving information. To capture the continuous targets in the regression task, RegExplainer also adopts the GIB objective to utilize the contrastive loss to learn the relationships between the triplets \([G,G^{+},G^{-}]\) of the graphs, where \(G\) is the target to-be-explained graph and \(G^{+}\) and \(G^{-}\) are positive and negative instances respectively. Our experiments show that RegExplainer provides consistent and concise explanations of GNN's predictions on regression tasks. We achieved up to 86.3% improvement when compared to the alternative baselines in our experiments. Our contributions could be summarized as in the following:

* To our best knowledge, we are the first to explain the graph regression tasks. We addressed two challenges associated with the explainability of the graph regression task: the mutual information estimation in the GIB objective and the distribution shifting problem.
* We proposed a novel model with a new mix-up approach and contrastive learning, which could more effectively address the two challenges, and better explain the graph model on the regression tasks compared to other baselines.
* We designed three synthetic datasets, namely BA-regression, BA-counting, and Triangles, as well as a real-world dataset called Crippen, which could also be used in future works, to evaluate the effectiveness of our regression task explanations. Comprehensive empirical studies on both synthetic and real-world datasets demonstrate that our method can provide consistent and concise explanations for graph regression tasks.

## 2. Preliminary

### Notation and Problem Formulation

We use \(G=(\mathcal{V},\mathcal{E};\mathbf{X},\mathbf{A})\) to represent a graph, where \(\mathcal{V}\) equals to \(\{v_{1},v_{2},...,v_{n}\}\) represents a set of \(n\) nodes and \(\mathcal{E}\in\mathcal{V}\times\mathcal{V}\) represents the edge set. Each graph has a feature matrix \(\mathbf{X}\in\mathbb{R}^{n\times d}\) for the nodes, wherein \(\mathbf{X}\), \(X_{i}\in\mathbb{R}^{1\times d}\) is the \(d\)-dimensional node feature of node \(v_{i}\). \(\mathcal{E}\) is described by an adjacency matrix \(\mathbf{A}\in\{0,1\}^{n\times n}\), where \(A_{ij}=1\) means that there is an edge between node \(v_{i}\) and \(v_{j}\); otherwise, \(A_{ij}=0\). For the graph prediction task, each graph \(G_{i}\) has a label \(Y_{i}\in\mathcal{C}\), where \(\mathcal{C}\) is the set of the classification categories or regression values, with a GNN model \(f\) trained to make the prediction, i.e., \(f:(\mathbf{X},\mathbf{A})\mapsto\mathcal{C}\).

Problem 1 (Post-hoc Instance-level GNN Explanation).: _Given a trained GNN model \(f\), for an arbitrary input graph \(G=(\mathcal{V},\mathcal{E};\mathbf{X},\mathbf{A})\), the goal of posthoc instance-level GNN explanation is to find a sub-graph \(G^{*}\) that can explain the prediction of \(f\) on \(G\)._

In non-graph structured data, the informative feature selection has been well studied (Kang et al., 2018), as well as in traditional methods, such as concrete auto-encoder (Chen et al., 2018), which can be directly extended to explain features in GNNs. In this paper, we focus on discovering the important sub-graph typologies following the previous work (Kang et al., 2018; Wang et al., 2019). Formally, the obtained explanation \(G^{*}\) is depicted by a binary mask \(\mathbf{M}^{*}\in\{0,1\}^{n\times n}\) on the adjacency matrix, e.g., \(G^{*}=(\mathcal{V},\mathcal{E};\mathbf{X},\mathbf{A}\odot\mathbf{M}^{*})\), \(\odot\) means elements-wise multiplication.

Figure 1. Intuitive illustration of the distribution shifting problem. The 3-dimensional map represents a trained GNN model \(f\), where \((h_{1},h_{2})\) represents the distribution of the graph in two dimensions, and \(Y\) represents the prediction value of the graph through \(f\). The red and blue lines represent the distribution of the original training set and corresponding explanation sub-graph set respectively.
The mask highlights components of \(G\) which are essential for \(f\) to make the prediction.

### GIB Objective

The Information Bottleneck (IB) (Srivastava et al., 2017; Wang et al., 2018) provides an intuitive principle for learning dense representations that an optimal representation should contain _minimal_ and _sufficient_ information for the downstream prediction task. Based on IB, a recent work unifies the most existing post-hoc explanation methods for GNN, such as GNNExplainer (Srivastava et al., 2017), PGExplainer (Peters et al., 2019), with the graph information bottleneck (GIB) principle (Wang et al., 2018; Wang et al., 2018; Wang et al., 2018). Formally, the objective of explaining the prediction of \(f\) on \(G\) can be represented by

\[\operatorname*{arg\,min}_{G^{*}}I(G;G^{*})-\alpha I(G^{*};Y), \tag{1}\]

where \(G\) is the to-be-explained original graph, \(G^{*}\) is the explanation sub-graph of \(G\), \(Y\) is the original ground-truth label of \(G\), and \(\alpha\) is a hyper-parameter to get the trade-off between minimal and sufficient constraints. GIB uses the mutual information \(I(G;G^{*})\) to select the minimal explanation that inherits only the most indicative information from \(G\) to predict the label \(Y\) by maximizing \(I(G^{*};Y)\), where \(I(G;G^{*})\) avoids imposing potentially biased constraints, such as the size or the connectivity of the selected sub-graphs (Wang et al., 2018). Through the optimization of the sub-graph, \(G^{*}\) provides model interpretation.

In graph classification task, a widely-adopted approximation to Eq. (2) in previous methods is:

\[\operatorname*{arg\,min}_{G^{*}}I(G;G^{*})+\alpha I(Y|G^{*})\approx \operatorname*{arg\,min}_{G^{*}}I(G;G^{*})+\alpha\mathrm{CE}(Y,Y^{*}), \tag{2}\]

where \(Y^{*}=f(G^{*})\) is the predicted label of \(G^{*}\) made by the model to be explained, \(f\) and the cross-entropy \(\mathrm{CE}(Y,Y^{*})\) between the ground truth label \(Y\) and \(Y^{*}\) is used to approximate \(I(G^{*};Y)\). The approximation is based on the definition of mutual information \(I(G^{*};Y)=H(Y)-H(Y|G^{*})\): with the entropy \(H(Y)\) being static and independent of the explanation process, minimizing the mutual information between the explanation sub-graph \(G^{*}\) and \(Y\) can be reformulated as maximizing the conditional entropy of \(Y\) given \(G^{*}\), which can be approximated by the cross-entropy between \(Y\) and \(Y^{*}\).

## 3. Methodology

In this section, we first introduce a new objective based on GIB for explaining graph regression learning. Then we showcase the distribution shifting problem in the GIB objective in graph regression tasks and propose a novel framework through a mix-up approach to solve the shifting problem.

### GIB for Explaining Graph Regression

As introduced in Section 2.2, in the classification task, \(I(G^{*};Y)\) in Eq. (1) is commonly approximated by cross-entropy \(\mathrm{CE}(Y^{*},Y)\)(Srivastava et al., 2017). However, it is non-trivial to extend exiting objectives for regression tasks because \(Y\) is a continuous variable and makes it intractable to compute the cross-entropy \(\mathrm{CE}(Y^{*},Y)\) or the mutual information \(I(G^{*};Y)\), where \(G^{*}\) is a graph variable with a continuous variable \(Y^{*}\) as its label.

#### 3.1.1. Optimizing the lower bound of \(I(G^{*};Y)\)

To address the challenge of computing the mutual information \(I(G^{*};Y)\) with a continuous \(Y\), we propose a novel objective for explaining graph regression. Instead of minimizing \(I(G^{*};Y)\) directly, we propose to maximize a lower bound for the mutual information by including the label of \(G^{*}\), denoted by \(Y^{*}\), and approximate \(I(G^{*};Y)\) with \(I(Y^{*};Y)\), where \(Y^{*}\) is the prediction label of \(G^{*}\):

\[\operatorname*{arg\,min}_{G^{*}}I(G;G^{*})-\alpha I(Y^{*};Y). \tag{3}\]

As shown below, \(I(Y^{*};Y)\) has the following property:

**Property 1**.: \(I(Y^{*};Y)\) _is a lower bound of \(I(G^{*};Y)\)._

Proof.: From the definition of \(Y^{*}\), we can make a safe assumption that there is a many-to-one map (function), denoted by \(h\), from \(G^{*}\) to \(Y^{*}\) as \(Y^{*}\) is the prediction label for \(G^{*}\). For simplicity, we assume a finite number of explanation instances for each label \(y^{*}\), and each explanation instance, denoted by \(g^{*}\), is generated independently. Then, we have \(p(y^{*})=\sum_{g^{*}\in\mathrm{G}(y^{*})}p(g^{*})\), where \(\mathrm{G}(y^{*})=\{g|h(g)=y^{*}\}\) is the set of explanations whose labels are \(y^{*}\).

Based on the definition of mutual information, we have:

\[I(G^{*};Y)=\int_{y}\int_{g^{*}}p_{(G^{*},Y)}(g^{*},y)\log\frac{p_{(G^{*},Y)}(g ^{*},y)}{p_{G^{*}}(g^{*})p_{Y}(y)}d_{g^{*}}d_{y}\]

Based on the definition of mutual information, we have:

\[I(G^{*};Y)=\int_{y}\int_{g^{*}}p_{(G^{*},Y^{*})}(g^{*},y)\log \frac{p_{(G^{*},Y)}(g^{*},y)}{p_{G^{*}}(g^{*})p_{Y}(y)}d_{g^{*}}d_{y}\] \[=\int_{y}\int_{g^{*}}p_{(G^{*},Y^{*},Y)}(g^{*},h(g^{*}),y)\log \frac{p_{(G^{*},Y^{*},Y)}(g^{*},h(g^{*}),y)}{p_{G^{*}}(g^{*})p_{Y}(y)}d_{g^{* }}d_{y}\] \[=\int_{y}\int_{g^{*}}\sum_{g^{*}\in\mathrm{G}(y^{*})}p_{(G^{*},Y^ {*},Y)}(g^{*},y^{*},y)\log\frac{p_{(G^{*},Y^{*},Y)}(g^{*},y^{*},y)}{p_{(G^{*},Y ^{*})}(g^{*},y^{*})p_{Y}(y)}d_{g^{*}}d_{y}\]

Based on our many-to-one assumption, while each \(g^{*}\) is generated independently, we know that if \(g\notin\mathrm{G}(y^{*})\), then \(p_{(G^{*},Y^{*},Y)}(g^{*},y^{*})=0\). Thus, we have:

\[I(G^{*};Y)=I(G^{*};Y)\] \[+\int_{y}\int_{y^{*}}\sum_{g\notin\mathrm{G}(y^{*})}p_{(G^{*},Y^ {*},Y)}(g^{*},y^{*},y)\log\frac{p_{(G^{*},Y^{*},Y)}(g^{*},y^{*},y)}{p_{(G^{*},Y ^{*})}(g^{*},y^{*})p_{Y}(y)}d_{y^{*}}d_{y}\] \[=\int_{y}\int_{y^{*}}\int_{g^{*}}p_{(G^{*},Y^{*},Y)}(g^{*},y^{*},y )\log\frac{p_{(G^{*},Y^{*},Y)}(g^{*},y^{*},y)}{p_{(G^{*},Y^{*})}(g^{*},y^{*})p_ {Y}(y)}d_{g^{*}}d_{y^{*}}d_{y}\] \[=I(G^{*},Y^{*};Y).\]

With the chain rule for mutual information, we have \(I(G^{*},Y^{*};Y)=I(Y^{*};Y)+I(G^{*};Y|Y^{*})\). Then due to the non-negativity of the mutual information, we have \(I(G^{*},Y^{*};Y)\geq I(Y^{*};Y)\)

Figure 2. Intuitive illustration about why \(I(G^{*};Y)\geq I(Y^{*};Y)\). \(G^{*}\) contains more mutual information as more overlapping area with \(Y\) than the overlapping between \(Y^{*}\) and \(Y\).
Intuitively, the property of \(I(Y^{*};Y)\) is guaranteed by the chain rule for mutual information and the independence between each explanation instance \(g^{*}\). The intuitive demonstration is shown in Figure 2. With the property, we can approximate Eq. (1) with Eq. (3).

#### 3.1.2. Estimating \(I(Y^{*};Y)\) with InfoNCE

Now the challenge becomes the estimation of the mutual information \(I(Y^{*};Y)\). Inspired by the model of Contrastive Predictive Coding (Yang et al., 2017), in which InfoNCE loss is interpreted as a mutual information estimator, we further extend the method so that it could apply to InfoNCE loss in explaining graph regression.

In our graph explanation scenario, \(I(Y^{*};Y)\) has the following property:

**Property 2**.: InfoNCE Loss is a lower bound of the \(I(Y^{*};Y)\) as shown in Eq. (4).

\[I(Y^{*};Y)\geq\operatorname*{\mathbb{E}}_{\frac{Y}{Y}}\left[\log\frac{f_{k}\;( Y^{*},Y)}{\frac{1}{|Y|}\;\sum_{Y\neq Y}f_{k}\;\left(Y^{*},Y_{j}\right)}\right] \tag{4}\]

In Eq. (4), \(Y_{j}\) is randomly sampled graph neighbors, and \(\mathbb{Y}\) is the set of the neighbors. We prove this property theoretically in the following:

Proof.: As in the InfoNCE method, the mutual information between \(Y^{*}\) and \(Y\) is defined as:

\[I(Y^{*};Y)=\sum_{Y^{*},Y}p(Y^{*},Y)\log\frac{p(Y|Y^{*})}{P(Y)} \tag{5}\]

However, the ground truth joint distribution \(p(Y^{*},Y)\) is not controllable, so, we turn to maximize the density ratio

\[f_{k}\;(Y^{*},Y)\propto\frac{p(Y|Y^{*})}{p(Y)} \tag{6}\]

We want to put the representation function of mutual information into the NCE Loss

\[\mathcal{L}_{N}=\operatorname*{\mathbb{E}}_{\frac{Y}{Y}}\log\left[\frac{f_{k} \;(Y^{*},Y)}{\sum_{Y^{\prime}\in\mathbb{Y}}(Y^{*},Y^{\prime})}\right], \tag{7}\]

where \(\mathcal{L}_{N}\) denotes the NCE loss and by inserting the optimal \(f_{k}\;(Y^{*},Y)\) into Eq. (7), we could get:

\[\mathcal{L}_{\text{contr}} =\operatorname*{\mathbb{E}}_{\frac{Y}{Y}}\log\left[\frac{\frac{ p(Y|Y^{*})}{p(Y)}}{\frac{p(Y)^{*}}{p(Y)}+\sum_{Y^{\prime}\in\mathbb{Y}_{\text{neg}}} \frac{p(Y^{*},Y^{\prime})}{p(Y^{\prime})}}\right]\] \[=\operatorname*{\mathbb{E}}_{\frac{Y}{Y}}\log\left[1+\frac{p(Y|Y^ {*})}{p(Y)}\sum_{Y^{\prime}\in\mathbb{Y}_{\text{neg}}}\frac{p(Y^{*},Y^{\prime })}{p(Y^{\prime})}\right]\] \[\approx\operatorname*{\mathbb{E}}_{\frac{Y}{Y}}\log\left[1+\frac{ p(Y|Y^{*})}{p(Y)}(N-1)\operatorname*{\mathbb{E}}_{\frac{Y}{Y}}\frac{p(Y^{*},Y^{ \prime})}{p(Y^{\prime})}\right]\] \[=\operatorname*{\mathbb{E}}_{\frac{Y}{Y}}\log\left[1+\frac{p(Y|Y^ {*})}{p(Y)}(N-1)\right]\] \[\geq\operatorname*{\mathbb{E}}_{\frac{Y}{Y}}\log\left[\frac{p(Y|Y^ {*})}{p(Y)}N\right]\] \[=-I(Y^{*},Y)+\log(N) \tag{8}\]

To employ the contrastive loss, we use the representation embedding to approximate \(Y\), where \(\mathbf{h}^{*}\) represents the embedding for \(G^{*}\) and \(\mathbf{h}\) represents the embedding for \(G\). We use \(\mathbb{H}\) to represent the neighbors set \(\mathbb{Y}\) accordingly. Thus, we approximate Eq. (3) as:

\[\operatorname*{arg\,min}_{G^{*}}I(G;G^{*})-\alpha\operatorname*{\mathbb{E}}_{ \frac{\mathbb{H}}{\mathbb{H}}}\left[\log\frac{f_{k}\;(\mathbf{h}^{*},\mathbf{h})}{ \frac{1}{|\mathbb{H}|}\;\sum_{\mathbf{h}_{j}\in\mathbb{H}}f_{k}\;\left(\mathbf{h}^{*}, \mathbf{h}_{j}\right)}\right] \tag{9}\]

### Mixup for Distribution Shifts

In the above section, we include the label of explanation sub-graph, \(Y^{*}\), in our GIB objective for explaining regression. However, we argue that \(Y^{*}\) cannot be safely obtained due to the distribution shift problem (Garon et al., 2017; Garon et al., 2017).

#### 3.2.1. Distribution Shifts in GIB

Suppose that the model to be explained, \(f\), is trained on a dataset \(\{(G_{i},Y_{i})\}_{i=1}^{N}\). Usually in supervised learning (without domain adaptation), we suppose that the examples \((G_{i},Y_{i})\) are drawn i.i.d. from a distribution \(\mathcal{D}_{\text{train}}\) of support \(G\times Y\) (unknown and fixed). The objective is then to learn \(f\) such that it commits the least error possible for labeling new examples coming from the distribution \(\mathcal{D}_{\text{train}}\). However, as pointed out in previous studies, there is a shift between the distribution explanation sub-graphs, denoted by \(\mathcal{D}_{\text{exp}}\) and \(\mathcal{D}_{\text{train}}\). As the explanation, sub-graphs tend to be small and dense. The distribution shift problem is severe in regression problems due to the continuous decision boundary (Yaron et al., 2017).

Figure 4 shows the existence of distribution shifts between \(f(G^{*})\) and \(Y\) in graph regression tasks. For each dataset, we sort the indices of the data samples according to the value of their labels, and visualize the label \(Y\), prediction \(f(G)\) of the original graph from the trained GNN model \(f\), and prediction \(f(G^{*})\) of the explanation sub-graph \(G^{*}\) from \(f\). As we can see in Figure 3, in all four graph regression datasets, the red points are well distributed around the ground-truth blue points, indicating that \(f(G)\) is close to \(Y\). In comparison, the green points shift away from the red points, indicating the shifts between \(f(G^{*})\) and \(f(G)\). Intuitively, this phenomenon indicates the GNN model \(f\) could make correct predictions only with the original graph \(G\) yet could not predict the explanation sub-graph \(G^{*}\) correctly. This is because the GNN model \(f\) is trained with the original graph sets, whereas the explanation \(G^{*}\) as the sub-graph is out of the distribution from the original graph sets. With the shift between \(f(G)\) and \(f(G^{*})\), the optimal solution in Eq. (3) is unlikely to be the optimal solution for Eq. (1).

#### 3.2.2. Graph Mix-up Approach

To address the distribution shifting issue between \(f(G)\) and \(f(G^{*})\) in the GIB objective, we introduce the mix-up approach to reconstruct a within-distribution graph, \(G^{(\text{mix})}\), from the explanation graph \(G^{*}\). We follow (Yaron et al., 2017) to make a widely-accepted assumption that a graph can be divided by \(G=G^{*}+G^{\Delta}\), where \(G^{*}\) presents the underlying sub-graph that makes important contributions to GNN's predictions, which is the expected explanatory graph, and \(G^{\Delta}\) consists of the remaining label-independent edges for predictions made by the GNN. Both \(G^{*}\) and \(G^{\Delta}\) influence the distribution of \(G\). Therefore, we need a graph \(G^{(\text{mix})}\) that contains both \(G^{*}\) and \(G^{\Delta}\), upon which we use the prediction of \(G^{(\text{mix})}\) made by \(f\) to approximate \(Y^{*}\) and \(\mathbf{h}^{*}\).
Specifically, for a target graph \(G_{a}\) in the original graph set to be explained, we generate the explanation sub-graph \(G_{a}^{*}=G_{a}-G_{a}^{\Delta}\) from the explainer. To generate a graph in the same distribution of original \(G_{a}\), we can randomly sample a graph \(G_{b}\) from the original set, generate the explanation sub-graph of \(G_{b}^{*}\) with the same explainer and retrieve its label-irrelevant graph \(G_{b}^{\Delta}=G_{b}-G_{b}^{*}\). Then we could merge \(G_{a}^{*}\) together with \(G_{b}^{\Delta}\) and produce the mix-up explanation \(G_{a}^{(\text{mix})}\). Formally, we can have \(G_{a}^{(\text{mix})}=G_{a}^{*}+(G_{b}-G_{b}^{*})\).

Since we are using the edge weights mask to describe the explanation, the formulation could be further written as:

\[\mathbf{M}_{a}^{(\text{mix})}=\mathbf{M}_{a}^{*}+(\mathbf{I}_{b}-\mathbf{M}_{b}^{*}), \tag{10}\]

where \(\mathbf{M}\) denotes the weight of the adjacency matrix and \(\mathbf{I}_{b}\) denotes the zero-ones matrix as weights of all edges in the adjacency matrix of \(G_{b}\), where \(1\) represents the existing edge and \(0\) represents there is no edge between the node pair.

We denote \(G_{a}\) and \(G_{b}\) with the adjacency matrices \(A_{a}\) and \(A_{b}\), their edge weight mask matrices as \(M_{a}\) and \(M_{b}\). If \(G_{a}\) and \(G_{b}\) are aligned graphs with the same number of nodes, we could simply mix them up with Eq. (10). However, in real-life applications, a well-aligned dataset is rare. So we use a connection adjacency matrix \(A_{\text{conn}}\) and mask matrix \(M_{\text{conn}}\) to merge two graphs with different numbers of nodes. Specifically, the mix-up adjacency matrix could be formed as:

\[\mathbf{A}_{a}^{(\text{mix})}=\left[\begin{array}{cc}\mathbf{A}_{a}&\mathbf{A}_{\text{ conn}}\\ \mathbf{A}_{\text{conn}}^{T}&\mathbf{A}_{b}\end{array}\right]. \tag{11}\]

And the mix-up mask matrix could be formed as:

\[\mathbf{M}_{a}^{(\text{mix})}=\left[\begin{array}{cc}\mathbf{M}_{a}^{*}&\mathbf{M}_{ \text{conn}}\\ \mathbf{M}_{\text{conn}}^{T}&\mathbf{M}_{b}^{\Delta}\end{array}\right] \tag{12}\]

Finally, we could form \(G_{a}^{(\text{mix})}\) as \((\mathbf{X}^{(\text{mix})},\mathbf{A}_{a}^{(\text{mix})}\odot\mathbf{M}_{a}^{(\text{mix })})\), where \(\mathbf{X}^{(\text{mix})}=[\mathbf{X}_{a};\mathbf{X}_{b}]\). We use Algorithm 1 to describe the whole process. Then we could feed \(G_{a}^{(\text{mix})}\) into the GIB objective and use it for training the parameterized explainer.

```
0: Target to-be-explained graph \(G_{a}=(\mathbf{X}_{a},\mathbf{A}_{a})\), \(G_{b}\) sampled from a set of graphs \(\mathbb{G}\), the number of random connections \(\eta\), explainer model \(E\).
0: Graph \(G^{(\text{mix})}\).
1: Generate mask matrix \(\mathbf{M}_{a}=E(G_{a})\)
2: Generate mask matrix \(\mathbf{M}_{b}=E(G_{b})\)
3: Sample \(\eta\) random connections between \(G_{a}\) and \(G_{b}\) as \(\mathbf{A}_{\text{conn}}\)
4: Mix-up adjacency matrix \(\mathbf{A}_{a}^{(\text{mix})}\) with Eq. (11)
5: Mix-up edge mask \(\mathbf{M}_{a}^{(\text{mix})}\) with Eq. (12)
6: Mix-up node features \(\mathbf{X}^{(\text{mix})}=[\mathbf{X}_{a};\mathbf{X}_{b}]\)
7:return\(G^{(\text{mix})}=(\mathbf{X}^{(\text{mix})},\mathbf{A}_{a}^{(\text{mix})}\odot\mathbf{M}_{a}^{( \text{mix})})\)
```

**Algorithm 1** Graph Mix-up Algorithm

We show that our mix-up approach has the following property: **Property 3**. \(G^{(\text{mix})}\) is within the distribution of \(\mathcal{D}_{\text{train}}\).

Following the previous work, we denote a graph \(G=G^{*}+G^{\Delta}\), where \(G^{*}\) is the sub-graph explanation and \(G^{\Delta}\) is the label-irrelevant graph. A common acknowledgment is that for a graph \(G\) with label \(Y\), the explanation \(G^{*}\) holds the label-preserving information, which is the important sub-graph, while \(G^{\Delta}\) also holds useful information which makes sure connecting it with \(G^{*}\) would maintain the distribution of the graph and not lead to another label. We denote the distribution for the graphs as \(G\sim\mathcal{D}_{\text{train}}=\mathbb{P}_{\tilde{\mathcal{G}}}\), \(G^{*}\sim\mathbb{P}_{\tilde{\mathcal{G}}^{*}}\), \(G^{\Delta}\sim\mathbb{P}_{\tilde{\mathcal{G}}^{*}}\), where \(\mathcal{D}_{\text{train}}\) means the distribution of train

Figure 3. Illustration of RegExplainer. \(G\) is the to-be-explained graph, \(G^{+}\) is the randomly sampled positive graph and \(G^{-}\) is the randomly sampled negative graph. The explanation of the graph is produced by the explainer model. Then graph \(G\) is mixed with \(G^{+}\) and \(G^{-}\) respectively to produce \(G^{(\text{mix})+}\) and \(G^{(\text{mix})-}\). Then the graphs are fed into the trained GNN model to retrieve the embedding vectors \(E(G^{+})\), \(E(G^{-})\), \(E(G^{(\text{mix})-})\) and \(E(G^{(\text{mix})-})\). We use contrastive loss to minimize the distance between \(G^{(\text{mix})+}\) and the positive sample and maximum the distance between \(G^{(\text{mix})-}\) and the negative sample. The explainer is trained with the GIB objective and contrastive loss.
dataset. When we produce \(G^{\text{(mix)}}\), we independently sample a label-irrelevant graph \(G^{\Delta}\) and mix it up with target explanation \(G^{*}\). So, we could write the distribution of \(G^{\text{(mix)}}\) as :

\[G^{\text{(mix)}}\sim\mathbb{P}_{\mathcal{G^{*}}}*\mathbb{P}_{\mathcal{G^{\Delta }}}=\mathbb{P}_{(\mathcal{G^{*}}+\mathcal{G^{\Delta}})}=\mathbb{P}_{\mathcal{G }}=\mathcal{D}_{\text{train}} \tag{13}\]

Thus, we prove that \(G^{\text{(mix)}}\) is within the distribution of \(\mathcal{D}_{\text{train}}\). 

### Implementation

#### 3.3.1. Implementation of InfoNCE Loss

After generating the mix-up explanation \(G^{\text{(mix)}}\), we specify the contrastive loss to further train the parameterized explainer with a triplet of graphs \((G,G^{+},G^{-})\) as the implementation of InfoNCE Loss in Eq. (9). Intuitively, for each target graph \(G\) with label \(Y\) to be explained, we can define two randomly sampled graphs as positive graph \(G^{+}\) and negative instance \(G^{-}\) where \(G^{+}\)'s label, \(Y^{+}\) is closer to \(Y\) than \(G^{-}\)'s label, \(Y^{-}\), i.e., \(|Y^{+}-Y|<|Y^{-}-Y|\). Therefore, the distance between the distributions of the positive pair \((G,G^{+})\) should be smaller than the distance between the distributions of the negative pair \((G,G^{-})\).

In practice, \(G^{+}\) and \(G^{-}\) are randomly sampled from the graph dataset, upon which we calculate their similarity score with the target graph \(G\). The sample with a higher score would be the positive sample and the other one would be the negative sample. Specifically, we use \(\text{sim}(\mathbf{h},\mathbf{h}_{j})=\mathbf{h}^{T}\mathbf{h}_{j}\) to compute the similarity score, where \(G_{j}\) could be \(G^{+}\) or \(G^{-}\). \(\mathbf{h}\) is generated by feeding \(G\) into the GNN model \(f\) and directly retrieving the embedding vector before the dense layers ; \(\mathbf{h}^{+}\) and \(\mathbf{h}^{-}\) denote the embedding vectors for \(G^{+}\) and \(G^{-}\) respectively.

Learning through the triplet instances could effectively reinforce the ability of the explainer to learn the explanation self-supervised. A similar idea goes with mixup graphs which we propose to address the distribution shifts in GIB. After we mix up target graph \(G\) with the neighbors \(G^{+}\) and \(G^{-}\) and get \(G^{\text{(mix)+}}\) and \(G^{\text{(mix)-}}\) respectively, the distance between \(G^{\text{(mix)+}}\), \(G^{+}\) should be smaller than the distance between \(G^{\text{(mix)-}}\), \(G^{-}\). For example, given graph \(G\) with a label \(2.0\), \(G^{+}\) with a label \(1.0\), and \(G^{-}\) with a label \(100.0\), after we mix the explanation of \(G\), which is \(G^{*}\), with \(G^{+}\) and \(G^{-}\) respectively, following Eq. (10), the prediction label of \(G^{\text{(mix)+}}\) and \(G^{\text{(mix)-}}\) should be closer to \(1\) because they contain the label-preserving sub-graph \(G^{*}\), which could be represented as \(|f(G^{\text{(mix)-}})-f(G^{-})|>|f(G^{\text{(mix)+}})-f(G^{+})|\), where \(f(G)\) represents the prediction label of graph \(G\).

Formally, given a target graph \(G\), the sampled positive graph \(G^{+}\) and negative graph \(G^{-}\), we formulate the contrastive loss in Eq. (9) as the following:

\[\begin{split}\mathcal{L}_{\text{contr}}(G,G^{+},G^{-})& =\log(1+\exp(\mathbf{h}^{T}\mathbf{h}^{-}-\mathbf{h}^{T}\mathbf{h}^{+}))\\ &=-\log\frac{\exp(\mathbf{h}^{T}\mathbf{h}^{+})}{\exp(\mathbf{h}^{T}\mathbf{h}^{ +})+\exp(\mathbf{h}^{T}\mathbf{h}^{-})}\end{split} \tag{14}\]

where \(\exp()\) function is used to instantiate the density ratio function \(f_{k}\), the denominator is a sum over the ratios of both positive and negative samples in the triplet \(\mathbb{Y}\).

#### 3.3.2. Size Constraints

We optimize \(I(G;G^{+})\) in Eq. (9) to constraint the size of the explanation sub-graph \(G^{*}\). The upper bound of \(I(G;G^{*})\) is optimized as the estimation of the KL-divergence between the probabilistic distribution between the \(G^{+}\) and \(G\), where the KL-divergence term can be divided into two parts as the entropy loss and size loss (Koren et al., 2017). In practice, we follow the previous work (Koren et al., 2017; Li et al., 2019; Li et al., 2019) to implement them. Specifically,

\[\mathcal{L}_{\text{size}}(G,G^{*})=\gamma\sum_{(i,j)\in\mathcal{E}}(M^{*}_{ij}) -\log\delta(\mathbf{h}\mathbf{h}^{T}). \tag{15}\]

\(\sum\limits_{(i,j)\in\mathcal{E}}(M^{*}_{ij})\) means sum the weights of the existing edges in the edge weight mask \(\mathbf{M}^{*}\) for the explanation \(G^{*}\); \(\mathbf{h}=f_{\text{bd}}(G^{*})\), where we extract the embedding of the graph \(G^{*}\) before the GNN model \(f\) transforming it into prediction \(Y^{*}\) and \(\gamma\) is the weight for the size of the masked graph.

#### 3.3.3. Overall Objective Function

In practice, the denominator in Eq. (9) works as a regularization to avoid trivial solutions. Since the label \(Y=f(G)\) is given and independent of the optimization process, we could also employ the MSE loss between \(Y^{*}\) and \(Y\) additionally, regarding InfoNCE loss only estimates the mutual information between the embeddings. Formally, the overall loss function could be implemented as:

\[\mathcal{L}_{\text{GIB}} =\mathcal{L}_{\text{size}}(G,G^{+})-\alpha\mathcal{L}_{\text{contr }}(G,G^{+},G^{-}) \tag{17}\] \[\mathcal{L} =\mathcal{L}_{\text{GIB}}+\beta\mathcal{L}_{\text{MSE}}(f(G),f(G^{ \text{(mix)+}})), \tag{16}\]

where \(G^{\text{(mix)+}}\) means mix \(G^{*}\) with the positive sample \(G^{+}\) and the hyper-parameters are \(\alpha\) and \(\beta\).

#### 3.3.4. Detailed Description of Algorithm 2

Algorithm 2 shows the training phase for the explainer model \(E\). For each epoch and each to-be-explained graph, we first randomly sample two neighbors \(G_{b}\) and \(G_{c}\), then we decide the positive sample \(G^{+}\) and negative sample \(G^{-}\) according to the similarity between \((G,G_{b})\) and \((G,G_{c})\). We generate the explanation for graphs and mix \(G\) with \(G^{+}\) and \(G^{-}\) respectively with the Algorithm 1. We calculate the contrastive loss for triplet \((G,G^{+},G^{-})\) with Eq. (14) and the GIB loss, which
contains the size loss and contrastive loss. We also calculate the MSE loss between \(f(G^{\text{(mix)+}})\) and \(f(G)\). The overall loss is the sum of GIB loss and MSE loss. We update the trainable parameters in the explainer with the overall loss.

#### 3.3.5. Computational Complexity Analysis

In the implementation, we transform the structure of the graph data from the sparse adjacency matrix representation into the dense edges list representation. We analyze the computational complexity of our mix-up approach here. According to Algorithm 1, given a graph \(G_{a}\) and a randomly sampled graph \(G_{b}\), assuming \(G_{a}\) contains \(M_{a}\) edges and \(G_{b}\) contains \(M_{b}\) edges, the complexity of graph extension operation on edge indices and masks, which extend the size of them from \(M_{a}\), \(M_{b}\) to \(M_{a}+M_{b}\), is \((2(M_{a}+M_{b}))\), where \(M_{a}>0\) and \(M_{b}>0\). To generate \(\eta\) cross-graph edges, the computational complexity is \(\mathcal{O}(n)\). For the mix-up operation, the complexity is \(\mathcal{O}(2(M_{a}+M_{b})+\eta)\). Since \(\eta\) is usually a small constant, the time complexity of our mix-up approach is \(\mathcal{O}(2*M_{a}+2*M_{b})\). We use \(M\) to denote the largest number of edges for the graph in the dataset and the time complexity of mix-up could be simplified to \(\mathcal{O}(M)\).

## 4. Experiments

In this section, we will introduce our datasets, experiment settings, and the results. Our experiments show that RegExplainer provides consistent and concise explanations of GNN's predictions on regression tasks. On three synthetic datasets and real-life dataset Crippen, we show that RegExplainer accurately identifies the important sub-graphs/motits that determine the graph label and outperforms alternative baselines by up to 86.3% in explanation accuracy (AUC).

* RQ1: How does the RegExplainer perform compared to other baselines on the four datasets?
* RQ2: How does each component of the proposed approach affect the performance of RegExplainer?
* RQ3: How does the proposed approach perform under different hyper-parameters?

### Datasets and Setups

In this section, we will introduce how we formulate our datasets and their specific configurations. (1) _BA-Motif-Volume_: This dataset is based on the BA-shapes (Zhu et al., 2017) and makes a modification, which is adding random float values from [0.00, 100.00] as the node feature. We then sum the node values on the motif as the regression label of the whole graph, which means the GNNs should recognize the [house] motif and then sum features to make the prediction. (2) _BA-Motif-Counting_: Different from BA-Motif-Volume, where node features are summarized, in this dataset, we attach various numbers of motifs to the base BA random graph and pad all graphs to equal size. The number of motifs is counted as the regression label. Padding graphs to the same size could prevent the GNNs from making trivial predictions based on the total number of nodes. (3) _Triangles_: We follow the previous work (Beng et al., 2019) to construct this dataset. The dataset is a set of 5000 Erdos-Renyi random graphs denoted as \(ER(m,p)\), where \(m=30\) is the number of nodes in each graph and \(p=0.2\) is the probability for an edge to exist. The size of 5000 was chosen to match the previous work. The regression label for this dataset is the number of triangles in a graph and GNNs are trained to count the triangles. (4) _Crippen_: The Crippen dataset is a real-life dataset that was initially used to evaluate the graph regression task. The dataset has 1127 graphs reported in the Delaney solubility dataset (D
We directly remove the contrastive loss term but still maintain the mix-up processing and MSE loss. (3) \(\text{RegE}^{-\text{mse}}\): We directly remove the MSE loss computation item from the objective function.

Additionally, we set all variants with the same configurations as original RegExplainer, including learning rate, training epochs, and hyper-parameters \(\eta\), \(\alpha\), and \(\beta\). We trained them on all four datasets and conduct the results in Figure 5. We observed that the proposed RegExplainer outperforms its variants in all datasets, which indicates that each component is necessary and the combination of them is effective.

### Hyper-parameter Sensitivity Study (RQ3)

In this section, we investigate the hyper-parameters of our approach, which include \(\alpha\) and \(\beta\), across all four datasets. The hyper-parameter \(\alpha\) controls the weight of the contrastive loss in the GIB objective while the \(\beta\) controls the weight of the MSE loss. We determined the optimal values of \(\alpha\) and \(\beta\) by tuning it within the \([0.001,1000]\) range, using a 3X increment for each step like [0.1, 0.3, 1, 3...]. When we tune one hyper-parameter, another one is set to be 1.0. The experimental results can be found in Figure 6. Our findings indicate that our approach, RegExplainer, is stable and

\begin{table}
\begin{tabular}{c|c c c c} \hline \hline Dataset & BA-Motif-Volume & BA-Motif-Counting & Triangles & Crippen \\ \hline Original Graph \(G\) & & & & \\ Explanation \(G^{*}\) & & & & \\ Node Feature & Random Float Vector & Fixed Ones Vector & Fixed Ones Vector & One-hop Vector \\ Regression Label & Sum of Motif Value & Count Motifs & Count Triangles & Chemical Property Value \\ Explanation Type & Fix Size Sub-Graph & Dynamic Size Sub-graph & Dynamic Size Sub-graph & Dynamic Size Sub-graph \\ \hline Explanation AUC & & & & \\ GRAD & \(0.418\pm 0.000\) & \(0.516\pm 0.000\) & \(0.479\pm 0.000\) & \(0.426\pm 0.000\) \\ ATT & \(0.512\pm 0.005\) & \(0.517\pm 0.003\) & \(0.441\pm 0.004\) & \(0.502\pm 0.006\) \\ GNNExplainer & \(0.501\pm 0.009\) & \(0.496\pm 0.003\) & \(0.500\pm 0.002\) & \(0.497\pm 0.005\) \\ PGExplainer & \(0.470\pm 0.057\) & \(0.000\pm 1.56\) & \(0.511\pm 0.028\) & \(0.448\pm 0.005\) \\ \hline
**RegExplainer** & \(0.758\pm 0.177\) & \(0.963\pm 0.011\) & \(0.739\pm 0.008\) & \(0.553\pm 0.013\) \\ \hline \hline \end{tabular}
\end{table}
Table 1. Illustration of the graph regression dataset together with the explanation faithfulness in terms of AUC-ROC on edges under four datasets on RegExplainer and other baselines. The original graph row visualize the structure of the complete graph, the explanation row highlight the explanation sub-graph of the corresponding original graph. In Crippen dataset, different color of the node represent different kind of atoms and the node feature is one-hot vector to encode the atom type.

Figure 4. Visualization of distribution shifting problem on four graph regression datasets. The points represent the regression value, where the blue points mean label \(y\), red points mean prediction \(f(G)\) of the original graph, and the blue points mean prediction \(f(G^{s})\) of explanations on the four datasets, the x-axis is the indices of the graph, sorted by the value of the label \(Y\).
robust when using different hyper-parameter settings, as evidenced by consistent performance across a range.

### Study the Decision Boundary and the Distributions Numerically

In this section, we visualize the regression values of the graphs and calculate the prediction shifting distance for each dataset and analyze their correlations to the distance of the decision boundaries. We put our results into Figure 7 and Table 2.

We observed that in Figure 7, the red points distribute surround the blue points but the green points are shifted away, which indicates that the explanation sub-graph couldn't help GNNs make correct predictions. As shown in Table 2, we calculate the RMSE score between [the] \(f(G)\) and \(Y\), \(f(G^{*})\) and \(Y\), \(f(G)\) and \(f(G^{*})\) respectively, where \(f(G)\) is the prediction the original graph, \(f(G^{*}\) is the prediction of the explanation sub-graph, and \(Y\) is the regression label. We could observe that \(f(G^{*})\) shows a significant prediction shifting from \(f(G)\) and \(Y\), indicating that the mutual information calculated with the original GIB objective Eq.(2) would be biased.

We further explore the relationship of the prediction shifting against the label value with dataset BA-Motif-Volume, which represents the semantic decision boundary. In Figure 7, each point represents a graph instance, where \(Y\) represents the ground-truth label, and \(\Delta\) represents the absolute value difference. It's clear that both the \(\Delta(f(G^{*}),Y)\) and \(\Delta(f(G),f(G^{*}))\) strongly correlated to \(Y\) with statistical significance, indicating the prediction shifting problem is related to the continuous ordered decision boundary, which is present in regression tasks.

## 5. Related Works

**GNN explainability:** The explanation methods for GNN models could be categorized into two types based on their granularity: instance-level (Song et al., 2016; Wang et al., 2017; Wang et al., 2018; Wang et al., 2019) and model-level (Wang et al., 2019), where the former methods explain the prediction for each instance by identifying important sub-graphs, and the latter method aims to understand the global decision rules captured by the GNN. These methods

\begin{table}
\begin{tabular}{c|c c c} \hline \hline Dataset & \((f(G),Y)\) & \((f(G^{*}),Y)\) & \((f(G),f(G^{*}))\) \\ \hline BA-Motif-Volume & 131.42 & 1432.07 & 1427.07 \\ BA-Motif-Counting & 0.11 & 14.30 & 14.28 \\ Triangles & 5.28 & 12.38 & 12.40 \\ Crippen & 1.13 & 1.54 & 1.17 \\ \hline \hline \end{tabular}
\end{table}
Table 2. Prediction shifting study on the RMSE of \((f(G),Y)\), \((f(G),f(G^{*}))\) respectively.

Figure 5. Ablation study of RegExplainer. We evaluated the performance of original RegExplainer and its variants that exclude mix-up approach, contrastive loss, or MSE loss respectively. The X-axis indicates the various datasets, while the bars represent the AUC score, and the black solid line shows the standard deviation value.

Figure 6. Hyper-parameters study of \(\alpha\) and \(\beta\) on four datasets with RegExplainer. In both figures, the x-axis is the value of different hyper-parameter settings and the y-axis is the value of the average AUC score over ten runs with different random seeds.
could also be classified into two categories based on their methodology: self-explainable GNNs (Bahdan et al., 2019; Chen et al., 2020) and post-hoc explanation methods (Zhu et al., 2019; Zhang et al., 2020; Zhang et al., 2020), where the former methods provide both predictions and explanations, while the latter methods use an additional model or strategy to explain the target GNN. Additionally, CGE (Hua et al., 2019) (cooperative explanation) generates the sub-graph explanation with the sub-network simultaneously, by using cooperative learning. However, it has to treat the GNN model as a white-box, which is usually unavailable in the post-hoc explaining.

Existing methods haven't explored the explanation of the graph regression task and haven't considered two important challenges: the distribution shifting problem and the limitation of the GIB objective, which were addressed by our work.

**Mix-up approach:** We faced the challenge of the distribution shifting problem and adopted the mix-up (Zhu et al., 2019) approach in our work. The mix-up approach is a data augmentation technique that increases the diversity of the training data and improves the generalization performance of the model. There are also many mix-up related technologies including GraphMix (Wang et al., 2019), MixupGraph (Zhu et al., 2019), G-Mixup (Zhu et al., 2019), and ifMixup (Zhu et al., 2019). However, existing methods couldn't address the distribution shifting problem in graph regression tasks and improve the explainability of GNN due to their inability to generate graphs into original distributions, which highlights the need for a new mix-up method. Thus, we develop a new mix-up approach in our work.

## 6. Conclusion

We addressed the challenges in the explainability of graph regression tasks and proposed the RegExplainer, a novel method for explaining the predictions of GNNs with the post-hoc explanation sub-graph on graph regression task without requiring modification of the underlying GNN architecture or re-training. We showed how RegExplainer can leverage the distribution shifting problem and knowledge from the continuous decision boundary with the mix-up approach and the adopted GIB objective with the contrastive loss, while the problems seriously affect the performances of other explainers. We formulated four new datasets, which are BA-Motif-Volume, BA-Motif-Counting, Triangles, and Crippen for evaluating the explainers on the graph regression task, which are developed from the previous datasets and follow a similar setting. They could also benefit future studies on the XAIG-R.
