[table]capposition=top

# Towards Training GNNs using Explanation Directed Message Passing

Valentina Giunchiglia
Imperial College London
<EMAIL_ADDRESS>Varun Shukla11footnotemark: 1
Ludwig-Maximilians Universität München
<EMAIL_ADDRESS>Gonzalez
Imperial College London
<EMAIL_ADDRESS>Agarwal
Adobe
<EMAIL_ADDRESS>Equal contribution.

###### Abstract

With the increasing use of Graph Neural Networks (GNNs) in critical real-world
applications, several post hoc explanation methods have been proposed to
understand their predictions. However, there has been no work in generating
explanations on the fly during model training and utilizing them to improve
the expressive power of the underlying GNN models. In this work, we introduce
a novel explanation-directed neural message passing framework for GNNs, Expass
(EXplainable message PASSing), which aggregates only embeddings from nodes and
edges identified as important by a GNN explanation method. Expass can be used
with any existing GNN architecture and subgraph-optimizing explainer to learn
accurate graph embeddings. We theoretically show that Expass alleviates the
oversmoothing problem in GNNs by slowing the layer-wise loss of Dirichlet
energy and that the embedding difference between the vanilla message passing
and Expass framework can be upper bounded by the difference of their
respective model weights. Our empirical results show that graph embeddings
learned using Expass improve the predictive performance and alleviate the
oversmoothing problems of GNNs, opening up new frontiers in graph machine
learning to develop explanation-based training frameworks.

##  1 Introduction

Graph Neural Networks (GNNs) are increasingly used as powerful tools for
representing graph-structured data, such as social, information, chemical, and
biological networks [1, 2]. With the deployment of GNN models in critical
applications (e.g., financial systems and crime forecasting [3, 4]), it
becomes essential to ensure that the relevant stakeholders understand and
trust their decisions. To this end, several approaches [5, 6, 7, 8, 9, 10, 11,
12, 13] have been proposed in recent literature to generate post hoc
explanations for predictions of GNN models.

In contrast to other modalities like images and texts, generating instance-
level explanations for graphs is non-trivial. In particular, it is more
challenging since individual node embeddings in GNNs aggregate information
using the entire graph structure, and, therefore, explanations can be on
different levels (i.e., node attributes, nodes, and edges). While several
categories of GNN explanation methods have been proposed: gradient-based [14,
10, 5], perturbation-based [13, 9, 11, 8, 15], and surrogate-based [7, 12],
their utility is limited to generating post hoc node- and edge-level
explanations for a given pre-trained GNN model. Thus, the capability of GNN
explainers to improve the predictive performance of a GNN model lacks
understanding as there is very little work on systematically analyzing the
reliability of state-of-the-art GNN explanation methods on model performance
[16].

To address this, recent works have explored the joint optimization of machine
learning models and explanation methods to improve the reliability of
explanations [17, 18]. Zhou et al. [18] proposed DropEdge as a technique to
drop random edges (similar to generating random edge explanations) during
training to reduce overfitting in GNNs. More recently, Spinelli et al. [17]
used meta-learning frameworks to generate GNN explanations and show an
improvement in the performance of specific GNN explanation methods. While
these works make an initial attempt at jointly optimizing explainers and
predictive models, they are neither generalizable nor exhaustive. They fail to
show improvement in the downstream GNN performance [17] and degree of
explainability [18] across diverse GNN architectures and explainers. Further,
there is little to no work done on either theoretically analyzing the effect
of GNN explanations on the neural message framework in GNNs or on important
GNN properties like oversmoothing [19].

Present work. In this work, we introduce a novel explanation-directed neural
message passing framework, Expass, which can be used with any GNN model and
subgraph-optimizing explainer to learn accurate graph representations. In
particular, Expass utilizes GNN explanations to steer the underlying GNN model
to learn graph embeddings using only important nodes and edges. Expass aims to
define local neighborhoods for neural message passing, i.e., identify the most
important edges and nodes, using explanation weights, in the $k$-hop local
neighborhood of every node in the graph. Formally, we augment existing message
passing architectures to allow information flow along important edges while
blocking information along irrelevant edges.

We present an extensive theoretical and empirical analysis to show the
effectiveness of Expass on the predictive, explainability, and oversmoothing
performance of GNNs. Our theoretical results show that the embedding
difference between vanilla message passing and Expass frameworks is upper-
bounded by the difference between their model weights. Further, we show that
embeddings learned using Expass relieve the oversmoothing problem in GNNs as
they reduce information propagation by slowing the layer-wise loss of
Dirichlet energy (Section 4.2). For our empirical analysis, we integrate
Expass into state-of-the-art GNN models and evaluate their predictive,
oversmoothing, and explainability performance on real-world graph datasets
(Section 5). Our results show that, on average, across five GNN models, Expass
improves the degree of explainability of the underlying GNNs by 39.68%. Our
ablation studies show that for an increasing number of GNN layers, Expass
achieves 34.4% better oversmoothing performance than its vanilla counterpart.
Finally, our results demonstrate the effectiveness of using explanations
during training, paving the way for new frontiers in GraphXAI research to
develop explanation-based training algorithms.

##  2 Related works

Graph Neural Networks. Graph Neural Networks (GNNs) are complex non-linear
functions that transform input graph structures into a lower dimensional
embedding space. The main goal of GNNs is to learn embeddings that reflect the
underlying input graph structure, i.e., neighboring nodes in the graph are
mapped to neighboring points in the embedding space. Prior works have proposed
several GNN models using spectral and non-spectral approaches. Spectral models
[20, 21, 22, 23, 24] leverage Fourier transform and graph Laplacian to define
convolution approaches for GNN models. However, non-spectral approaches [25,
26, 27, 28, 29] define the convolution operation by leveraging the local
neighborhood of individual nodes in the graph. Most modern non-spectral models
are message-passing frameworks [30, 31], where nodes update their embedding by
aggregating information from $k$-hop neighboring nodes.

Post hoc Explanations. With the increasing development of complex high-
performing GNN models [25, 26, 27, 28, 29], it becomes critical to understand
their decisions. Prior works have focused on developing several post hoc
explanation methods to explain the decisions of GNN models [5, 13, 7, 12, 11,
9, 32]. More specifically, these explanation methods can be broadly
categorized into i) gradient-based methods [5] that leverage the gradients of
the GNN model to generate explanations; ii) perturbation-based methods [13, 9,
11] that aim to generate explanations by calculating the change in GNN
predictions upon perturbations of the input graph structure (nodes, edges, or
subgraphs); and iii) surrogate-based methods [7, 12] that fit a simple
interpretable model to approximate the predictive behavior of the given GNN
model. Finally, recent works have introduced frameworks to theoretically and
empirically analyze the behavior of state-of-the-art GNN explanation methods
with respect to several desirable properties [33, 16].

##  3 Preliminaries

Notations. Let $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X})$ denote an
undirected graph comprising of a set of nodes $\mathcal{V}$ and a set of edges
$\mathcal{E}$. Let
$\mathbf{X}{=}\\{\mathbf{x}_{1},\mathbf{x}_{2},\dots,\mathbf{x}_{N}\\}$ denote
the set of node feature vectors for all nodes in $\mathcal{V}$, where
$\mathbf{x}_{v}\in\mathbb{R}^{d}$ captures the attribute values of a node $v$
and $N{=}|\mathcal{V}|$ denotes the number of nodes in the graph. Let
$\mathbf{A}\in\mathbb{R}^{N\times N}$ be the graph adjacency matrix, where
element $\mathbf{A}_{uv}=1$ if there exists an edge $e\in\mathcal{E}$ between
nodes $u$ and $v$ and $\mathbf{A}_{uv}=0$ otherwise. We use
${\mathcal{N}}_{u}$ to denote the set of immediate neighbors of node $u$,
i.e., , ${\mathcal{N}}_{u}=\\{v\in\mathcal{V}|A_{uv}=1\\}$. Finally, the
function $\text{deg}:\mathcal{V}\mapsto\mathbb{Z}_{>0}$ is defined as
$\text{deg}(v)=|\mathcal{N}_{v}|$ and outputs the degree of a node
$v\in\mathcal{V}$

Graph Neural Networks (GNNs). Formally, GNNs can be formulated as message
passing networks [30] specified by three key operators Msg, Agg, and Upd.
These operators are recursively applied on a given graph $\mathcal{G}$ for a
$L$-layer GNN model defining how neural messages are shared, aggregated, and
updated between nodes to learn the final node representations in the
$L^{\text{th}}$ layer of the GNN. Commonly, a message between a pair of nodes
$(u,v)$ in layer $l$ is characterized as a function of their hidden
representations $\mathbf{h}_{u}^{(l-1)}$ and $\mathbf{h}_{v}^{(l-1)}$ from the
previous layer:
$\mathbf{m}_{uv}^{(l)}=\textsc{Msg}(\mathbf{h}_{u}^{(l-1)},\mathbf{h}_{v}^{(l-1)}).$
The Agg operator retrieves the messages from the neighborhood of node $u$ and
aggregates them as:
$\mathbf{m}_{u}^{(l)}=\textsc{Agg}(\mathbf{m}_{uv}^{(l)}\,|\,v\in\mathcal{N}_{u})$.
Next, the Upd operator takes the aggregated message $\mathbf{m}_{u}^{(l)}$ at
layer $l$ and combines it with $\mathbf{h}_{u}^{(l-1)}$ to produce node $u$’s
representation for layer $l$ as
$\mathbf{h}_{u}^{(l)}=\textsc{Upd}(\mathbf{m}_{u}^{(l)},\mathbf{h}_{u}^{(l-1)})$.
Lastly, the final node representation for node $u$ is given as
$\mathbf{z}_{u}=\mathbf{h}_{u}^{(L)}$.

Graph Explanations. In contrast to other modalities like images and texts, an
explanation method for graphs can formally generate multi-level explanations.
For instance, in a graph classification task, the explanations for a given
graph prediction can be with respect to the node attributes
$\mathbf{M}_{\text{x}}\in\mathbb{R}^{d}$, nodes
$\mathbf{M}_{n}\in\mathbb{R}^{N}$, or edges
$\mathbf{M}_{e}\in\mathbb{R}^{N\times N}$. Note that these explanation masks
are continuous but can be discretized using specific thresholding strategies
[33].

Oversmoothing. Cai et al. [34] and Zhou et al. [35] defined bounds for
analyzing oversmoothing for a GNN using Dirichlet Energy. For a graph
$\mathcal{G}$ with adjacency matrix $\mathbf{A}$ and degree matrix
$\mathbf{D}$, we define $\tilde{\mathbf{A}}{=}\mathbf{A}+\mathbf{I}_{N}$ and
$\tilde{\mathbf{D}}{=}\mathbf{D}+\mathbf{I}_{N}$ as the adjacency and degree
matrices respectively of the graph $\mathcal{G}$ with self-loops. We also
define the augmented normalized Laplacian of $\mathcal{G}$ as
$\tilde{\Delta}{=}\mathbf{I}_{N}-\tilde{\mathbf{D}}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$,
and $\mathbf{P}{=}\mathbf{I}_{N}-\tilde{\Delta}$.

##  4 Our Framework: Expass

Here, we describe Expass, our proposed explainable message-passing framework
that aims to learn accurate and interpretable graph embeddings. In particular,
Expass incorporates explanations into the message-passing framework of GNN
models by only aggregating embeddings from key nodes and edges as identified
using an explanation method.

Problem formulation (Explanation Directed Message Passing). Given a graph
$\mathcal{G}=(\mathcal{V},\mathcal{E},\textbf{X})$, Expass aims to generate a
$d$-dimensional embedding $\mathbf{z}_{u}\in\mathbb{R}^{d}$ for each node
$u\in\mathcal{V}$ using an explanation-directed message passing framework that
filters out the noise from unimportant edges and improves the expressive power
of GNNs.

###  4.1 Explanation Directed Message Passing

Figure 1: Overview of Expass: a) Expass investigates the problem of injecting
explanations into the message-passing framework to increase the expressive
power and performance of GNNs. b) Shown is the general message passing scheme
where, for node $u$, messages are aggregated from nodes
$v_{i}\in\mathcal{N}_{u}$ in the 1-hop neighborhood of $u$. c) Expass injects
explanations into the message passing framework translates by masking out
messages from neighboring nodes $v_{i}\in\mathcal{N}_{u}$ with explanation
scores $s_{uv_{i}}\approx 0$ when $u$ is correctly classified.

The central idea of Expass is to propose a novel method for improving the
neural message passing scheme of GNN models by utilizing explanations during
model training and aggregating important neural messages along edges in graph
neighborhoods. Next, we describe the existing message-passing scheme in GNNs
and our explainable counterpart.

Message Passing. As described in Section 3, each GNN layer can be described
using the $\textsc{Msg},\textsc{Agg},$ and Upd operators. For each node
$u\in\mathcal{V}$, the $(l+1)^{th}$ layer embeddings $\mathbf{h}^{(l+1)}_{u}$
is computed using a GNN operating on the node’s neighboring attributes.
Formally, the GNN layer can be formulated as:

where $\mathbf{h}^{(l+1)}_{u}$ represents the updated embedding of node $u$,
$\psi$ is the Msg operator, $\bigoplus$ is the Agg operator (e.g., summation),
$\phi$ is an Upd function (e.g., any non-linear activation function), and
$\mathbf{h}^{(l)}_{u}$ represents the embedding of node $u$ from the previous
layer. We obtain an embedding $\mathbf{z}_{u}$ for node $u$ by stacking $L$
GNN layers. Finally, the node embeddings $\mathbf{Z}\in\mathbb{R}$ are then
passed to a Readout function to obtain an embedding for the graph.

Expass. Here, we describe our proposed explainable message-passing scheme that
incorporates explanations into the message-passing step in individual GNN
layers on the fly during the training process. Given an explanation method,
which generates an importance score $s_{uv}\in\mathbf{M}^{e}_{u}$ for every
edge $e_{uv}\in\mathcal{E}$, we can weight the edge contribution in the
neighborhood $\mathcal{N}_{u}$ of node $u$ as:

Note that Expass is agnostic to explanation types and can also incorporate
explanations on node attributes and node level. For instance, the importance
scores for individual nodes can be computed by averaging the outgoing scores
$s_{uv}$ for all $v\in\mathcal{N}_{u}$. Subsequently, we can replace the
$s_{uv}$ score by using the average score $s_{u}$ to weight edges in the
Expass layers, and for node attributes, we can multiply the node attribute
explanation $\mathbf{M}^{a}_{u}$ to the original node attribute vector.

To enable explainable message passing and only retain the important embeddings
for node $u$, Expass removes the knowledge of irrelevant nodes and edges from
the local neighborhood $\mathcal{N}_{u}$ of node $u$ using its explanations.
For instance, if node $v$ is considered important to node $u$, Expass
transforms the aggregated messages of node $u$ using the node importance
scores $s_{uv}$. Note that since the explanations of node $u$ include
important nodes and edges in the $L$-hop neighborhood of node $u$, even though
node $u$ is only locally modified, the change will spread through all the
nodes in every GNN layer. Furthermore, to avoid spurious correlations, we
ensure that explanations are only generated for correctly classified nodes and
graphs. Explanation weights infuse information from higher-order neighborhoods
into each layer of the GNN model, specifically, from as many $L$-hop neighbors
because explanation weights within each layer are computed using the $L$-layer
GNN model. To illustrate this, we next show the weight computations for a GNN
explanation method.

Without loss of generality, let us consider GNNExplainer as our explanation
method whose mask for the selected graph is formulated as:
$\mathcal{G}_{\text{mask}}=(\mathbf{X}^{\prime},\mathbf{A}^{\prime})=(\mathbf{X}\odot\sigma(\mathbf{M}^{\text{x}}),\mathbf{A}\odot\sigma(\mathbf{M}^{\text{e}}))$,
where $W=[\mathbf{M}^{\text{x}},\mathbf{M}^{\text{e}}]$ are the explainers
parameters, $\sigma$ is the sigmoid function, and $\odot$ denotes element-wise
multiplication. Here, $s_{uv}$ represents the element in row $v$ and column
$u$ of $\mathbf{M}^{\text{e}}$. Gradient descent-based optimization is used to
find the optimal values for the masks minimizing the following objective:
$L_{e}=-\sum_{c=1}^{C}1[y=c]\log f_{\theta}(Y=y|\mathcal{G}_{\text{mask}})$,
where $f_{\theta}$ is the $L$-layer GNN model and $C$ is the total number of
classes. This shows that a $L$-hop neighborhood is used to compute $s_{uv}$.
Formally, it minimizes the uncertainty of the predictive model when the GNN
computation is limited to the explanation subgraph. This uncertainty is
minimized as a proxy of the maximization of the mutual information between the
prediction with the unmasked graph and masked graph.

###  4.2 Theoretical Analysis

Here, we provide a detailed theoretical analysis of our proposed Expass
framework. In particular, we (i) provide a theoretical upper bound on the
embedding difference obtained from a vanilla message passing and Expass
framework and (ii) show that graph embeddings learned using Expass relieves
the oversmoothing problem in GNNs by reducing information propagation.

######  Theorem 1 (Differences between Expass and Vanilla Message Passing).

Given a non-linear activation function $\sigma$ that is Lipschitz continuous,
the difference between the node embeddings between a vanilla message passing
and Expass framework can be bounded by the difference in their individual
weights, i.e.,

$\|\mathbf{h}_{u}^{(l)}-\mathbf{h^{\prime}}_{u}^{(l)}\|_{2}\leq\|\mathbf{W}_{a}^{(l)}{-}\mathbf{W^{\prime}}_{a}^{(l)}\|_{2}\|\mathbf{h}_{u}^{(l-1)}\|_{2}+\|\mathbf{W}_{n}^{(l)}{-}\mathbf{W^{\prime}}_{n}^{(l)}\|_{2}\sum_{\mathclap{v\in\mathcal{N}_{u}\cap
s_{v}=1}}\|\mathbf{h}_{v}^{(l-1)}\|_{2},$ (1)

where $\mathbf{W}_{a}^{(l)}$ and $\mathbf{W^{\prime}}_{a}^{(l)}$ are the
weights for node $u$ in layer $l$ of the vanilla message passing and Expass
framework and $\mathbf{W}_{n}^{(l)}$ and $\mathbf{W^{\prime}}_{n}^{(l)}$ are
their respective weight matrix with the neighbors of node $u$ at layer $l$.

###### Proof Sketch.

In Theorem 1, we prove that the $\ell_{2}$-norm of the differences between the
embeddings of vanilla message passing and Expass framework at layer $l$ is
upper bounded by the difference between their weights and the embeddings of
node $u$ and its subgraph. See Appendix A for more details. ∎

######  Definition 1 (Dirichlet Energy for a Node Embedding Matrix [35]).

Given a node embedding matrix
$\mathbf{H}^{(l)}=[\mathbf{h}_{1}^{(l)},\dots,\mathbf{h}_{n}^{(l)}]^{T}$
learned from the GNN model at the $l^{th}$ layer, the Dirichlet Energy
$E(\mathbf{H}^{(l)})$ is defined as:

$E(\mathbf{H}^{(l)})=tr(\mathbf{H}^{(l)^{T}}\tilde{\Delta}\mathbf{H}^{(l)})=\frac{1}{2}\sum_{i,j\in\mathcal{V}}a_{ij}||\frac{\mathbf{H}_{i}^{(l)}}{\sqrt{1+\text{deg}_{i}}}-\frac{\mathbf{H}_{j}^{(l)}}{\sqrt{1+\text{deg}_{j}}}||_{2}^{2}$
(2)

where $a_{ij}$ are elements in the adjacency matrix $\tilde{\mathbf{A}}$ and
$\text{deg}_{i},\text{deg}_{j}$ is the degree of node $i$ and $j$,
respectively.

Cai et al. [34] extensively show that higher Dirichlet energies correspond to
lower oversmoothing. Furthermore, they show that the removal of edges or,
similarly, the reduction of edge weights on graphs helps alleviate
oversmoothing.

######  Proposition 1 (Expass relieves Oversmoothing).

Expass alleviates oversmoothing by slowing the layer-wise loss of Dirichlet
energy.

The complete proof is provided in Appendix A.

##  5 Experiments

Next, we present experimental results for our Expass framework. More
specifically, we address the following questions: Q1) Does Expass enable GNNs
to learn more accurate embeddings and improve their degree of explainability?
Q2) How does Expass affect the oversmoothing and predictive performance of
GNNs with an increasing number of layers? Q3) Does Expass depend on the
quality of explanations for improving the predictive and oversmoothing
performance of GNNs and are they better than attention weights? Q4) How does
Expass helps in the evolution of explanation during the training of the GNN
model? 111Code to reproduce the results is available here

###  5.1 Datasets and Experimental setup

We first describe the datasets used to study the utility of our proposed
Expass framework and then outline the experimental setup.

Datasets. We use real-world molecular chemistry datasets to evaluate the
effectiveness of Expass w.r.t. the performance of the underlying GNN model and
understand the trade-off between explainability and accuracy for a graph
classification task. We consider four benchmark datasets, which includes Mutag
[36], Alkane-Carbonyl [37], DD [38], and Proteins [39]. See Appendix B.1 for a
detailed overview of the datasets.

GNN Architectures and Explainers. To investigate the flexibility of Expass, we
incorporate it into five different GNN models: GCN [40], GraphConv [41],
LEConv [42], GraphSAGE [28], GAT [43], and GIN [27]. We use GNNExplainer [13]
as our baseline GNN explanation method to generate edge-level explanations for
most of our experiments. In addition, we use Integrated Gradients [44] and
PGMExplainer [12], a node-level explanation method, to demonstrate Expass’s
sensitivity to the choice of explainers.

Implementation details. We consider DropEdge [45] as our baseline method for
comparing the oversmoothing performance of Expass as DropEdge randomly removes
edges from the input graph at each training epoch, acting like a message
passing reducer. Across all experiments, we use topK (k=40%) node
features/edges, and use them to generate explanations for all explanation
methods. All other hyperparameters of the explanation and baseline methods
were set following the author’s guidelines. For all our experiments (unless
mentioned otherwise), we use the baseline architectures with three GNN layers
followed by ReLU layers and set the hidden dimensionality to 32. Finally, we
use a single linear layer to transform the graph embeddings to their
respective classes. See Appendix B.2 for more details.

Performance metrics for GNN Explainers. To measure the reliability of GNN
explanation methods, we use the graph explanation faithfulness metric [16]:
$\text{GEF}(\hat{y}_{u},\hat{y}_{u^{\prime}})=1-\exp^{-\text{KL}(\hat{y}_{u}||\hat{y}_{u^{\prime}})}$,
where $\hat{y}_{u}$ is predicted probability vector using the whole subgraph
and $\hat{y}_{u^{\prime}}$ is the predicted probability vector using the
masked subgraph, where we generate the masked subgraph by only using the topK
features identified by an explanation and the Kullback-Leibler (KL) divergence
score (denoted by “$||$” operator) quantifies the distance between two
probability distributions. Note that GEF is a measure of the unfaithfulness of
the explanation. So, higher values indicate a higher degree of unfaithfulness.

Performance metrics for Oversmoothing. Zhou et al. [18] introduced the Group
Distance Ratio (GDR) metric to quantify oversmoothing in GNNs. It measures the
ratio between the average of pairwise representation distances between graphs
belonging to different (inter) and same (intra) groups. Formally, one would
prefer to reduce the intra-group class representations and increase the inter-
group distance to relieve the over-smoothing issue. Hence, lower GDR values
denote higher oversmoothing in GNNs.

Burn-in period. We defined the burn-in period as a number n of epochs during
training in which no explanations are used. The burn-in period is necessary to
avoid feeding spurious explanations to the model. The length of the burn-in
period (i.e., the number of epochs) was treated as a hyperparameter and fine-
tuned using the validation set. At the end of the burn-in period, a predefined
percentage of correctly predicted graphs per batch is randomly sampled and
their explanations are used in the model training. The percentage of correctly
predicted graphs sampled in each batch was set to 0.4 for all our experiments.
See Appendix C.2 for ablation on burn-in periods.

###  5.2 Results

Q1) Expass improves the predictive performance and explainability of GNNs. To
measure the predictive performance and degree of explainability of GNNs
trained using Expass, we compute their average predictive performance (using
AUROC and F1-score) and fidelity (using Graph Explanation Faithfulness) using
different GNN models and datasets. Across four datasets and five GNN
architectures, we find that Expass-augmented GNNs learn graph embeddings that
are more accurate (higher AUROC and F1-score) and result in more faithful
explanations (lower Graph Explanation Faithfulness score) than their vanilla
counterparts. On average, Expass improves the AUROC and F1-score by 1.51% and
1.05%, respectively. In particular, we observe that Expass improves the
predictive behavior of high-performing models like GIN (+2.06% in AUROC and
+2.50% in F1-score) but shows little to no improvement in the case of LeConv,
which utilizes a node-scoring mechanism through the similarity between a node
and its neighbors’ embeddings. Finally, we find that Expass-augmented GNNs
significantly improve the explainability of a GNN and achieve a 39.68% better
faithfulness score as compared to vanilla GNNs (Table 1). See Appendix C.1 for
results on node classification graph downstream tasks.

Table 1:  Results of Expass for five GNNs and four graph datasets. Shown is average performance across three independent runs. Arrows ($\uparrow$, $\downarrow$) indicate the direction of better performance. Expass improves the predictive power (AUROC and F1-score) and degree of explainability (Graph Explanation Faithfulness) of original GNNs across multiple datasets (shaded area). Values corresponding to best performance are bolded.  Dataset | Method | AUROC ($\uparrow$) | F1-score ($\uparrow$) | GEF ($\downarrow$)
---|---|---|---|---
Alkane-Carbonyl |  | GCN
---
Expass-GCN
| 0.97$\pm$0.01
---
0.98$\pm$0.00
| 0.95$\pm$0.01
---
0.96$\pm$0.01
| 0.33$\pm$0.02
---
0.23$\pm$0.02
| GraphConv
---
Expass-GraphConv
| 0.97$\pm$0.01
---
0.98$\pm$0.00
| 0.94$\pm$0.00
---
0.97$\pm$0.00
| 0.38$\pm$0.05
---
0.22$\pm$0.03
| LeConv
---
Expass-LeConv
| 0.98$\pm$0.01
---
0.98$\pm$0.00
| 0.96$\pm$0.00
---
0.96$\pm$0.01
| 0.37$\pm$0.03
---
0.24$\pm$0.03
| GraphSAGE
---
Expass-GraphSAGE
| 0.98$\pm$0.00
---
0.99$\pm$0.00
| 0.96$\pm$0.00
---
0.97$\pm$0.01
| 0.40$\pm$0.12
---
0.18$\pm$0.06
| GIN
---
Expass-GIN
| 0.96$\pm$0.01
---
0.98$\pm$0.01
| 0.94$\pm$0.02
---
0.96$\pm$0.02
| 0.35$\pm$0.06
---
0.11$\pm$0.04
DD |  | GCN
---
Expass-GCN
| 0.73$\pm$0.02
---
0.74$\pm$0.01
| 0.70$\pm$0.02
---
0.70$\pm$0.02
| 0.49$\pm$0.04
---
0.30$\pm$0.09
| GraphConv
---
Expass-GraphConv
| 0.75$\pm$0.03
---
0.77$\pm$0.03
| 0.73$\pm$0.03
---
0.73$\pm$0.03
| 0.25$\pm$0.10
---
0.19$\pm$0.04
| LeConv
---
Expass-LeConv
| 0.76$\pm$0.03
---
0.77$\pm$0.03
|  0.74$\pm$0.02
---
0.73$\pm$0.04
|  0.17$\pm$0.03
---
0.31$\pm$0.10
| GraphSAGE
---
Expass-GraphSAGE
| 0.74$\pm$0.02
---
0.76$\pm$0.03
| 0.70$\pm$0.02
---
0.71$\pm$0.02
| 0.21$\pm$0.04
---
0.20$\pm$0.03
| GIN
---
Expass-GIN
| 0.74$\pm$0.01
---
0.76$\pm$0.01
| 0.70$\pm$0.01
---
0.74$\pm$0.01
| 0.37$\pm$0.03
---
0.35$\pm$0.05
Mutag |  | GCN
---
Expass-GCN
| 0.71$\pm$0.11
---
0.77$\pm$0.02
| 0.87$\pm$0.01
---
0.89$\pm$0.00
| 0.09$\pm$0.03
---
0.04$\pm$0.01
| GraphConv
---
Expass-GraphConv
| 0.91$\pm$0.02
---
0.93$\pm$0.01
| 0.94$\pm$0.02
---
0.94$\pm$0.01
| 0.66$\pm$0.03
---
0.24$\pm$0.03
| LeConv
---
Expass-LeConv
| 0.92$\pm$0.03
---
0.92$\pm$0.03
| 0.94$\pm$0.02
---
0.96$\pm$0.01
| 0.65$\pm$0.05
---
0.30$\pm$0.06
| GraphSAGE
---
Expass-GraphSAGE
| 0.76$\pm$0.02
---
0.76$\pm$0.02
| 0.86$\pm$0.03
---
0.87$\pm$0.03
| 0.24$\pm$0.08
---
0.11$\pm$0.03
| GIN
---
Expass-GIN
| 0.92$\pm$0.02
---
0.94$\pm$0.02
| 0.93$\pm$0.01
---
0.95$\pm$0.01
| 0.61$\pm$0.05
---
0.32$\pm$0.04
Proteins |  | GCN
---
Expass-GCN
| 0.73$\pm$0.05
---
0.74$\pm$0.03
| 0.68$\pm$0.04
---
0.69$\pm$0.03
| 0.19$\pm$0.02
---
0.08$\pm$0.02
| GraphConv
---
Expass-GraphConv
| 0.75$\pm$0.03
---
0.75$\pm$0.03
| 0.70$\pm$0.03
---
0.70$\pm$0.04
| 0.49$\pm$0.06
---
0.10$\pm$0.03
| LeConv
---
Expass-LeConv
|  0.77$\pm$0.03
---
0.76$\pm$0.02
|  0.72$\pm$0.04
---
0.71$\pm$0.03
| 0.51$\pm$0.01
---
0.15$\pm$0.07
| GraphSAGE
---
Expass-GraphSAGE
| 0.73$\pm$0.04
---
0.73$\pm$0.04
| 0.69$\pm$0.04
---
0.69$\pm$0.04
| 0.17$\pm$0.07
---
0.06$\pm$0.01
| GIN
---
Expass-GIN
| 0.77$\pm$0.04
---
0.78$\pm$0.03
| 0.73$\pm$0.05
---
0.73$\pm$0.04
| 0.20$\pm$0.07
---
0.19$\pm$0.01

Q2) Expass relieves Oversmoothing in GNNs. We examine the oversmoothing (using
the Group Distance Ratio metric [18]) and predictive performance of GNNs
trained using Expass with their vanilla counterparts. The oversmoothing
problem in GNNs shows that the representations of nodes converge to similar
vectors as the number of layers increases. Therefore, we analyze the
oversmoothing of the GNNs for an increasing number of layers and find that, on
average, across two architectures, Expass improves the group distance ratio by
34.4% (Figure 2). Further, we also analyzed the oversmoothing behavior of
Expass for node classification tasks (in Appendix C.1) and our results
indicate an inherent trade-off between oversmoothing and predictive
performance of GNNs (Figures 5-7).

Figure 2: The effects of the number of GNN layers on the oversmoothing
performance of Expass (orange) and Vanilla (green) GCN (left column) and GIN
(right column) models trained on Alkane-Carbonyl dataset. Across models with
increasing number of layers, Expass achieves higher GDR performance without
sacrificing the predictive performance of the GCN model. See Figs. 5-7 for
predictive performance results.

Q3) Ablation studies. We conduct ablations on several components of Expass
with respect to its oversmoothing and predictive performance.

Expass for different TopK Explanations. We investigate the oversmoothing and
predictive performance of GNNs for different topK explanations (i.e., topK
edges identified by a GNN explanation) chosen in the message passing. Results
show that Expass alleviates oversmoothing by using only the topK edges to
learn graph embeddings and explicitly filter out the noise from unimportant
edges. In particular, we observe that the GDR values decrease (denoting higher
oversmoothing) with the increase in the use of topK edges (Figure 3). More
specifically, we find that the GDR value at topK=0.1 is 11.92% higher than
vanilla message passing (i.e., using all edges in the graph).

Expass vs. DropEdge. We compare the predictive and oversmoothing and
predictive performance of Expass and DropEdge. Here, we show that message
passing using optimized explanation-directed information outperforms random
edge removal. We find that Expass outperforms DropEdge across both
oversmoothing and accuracy metrics. In particular, on average, across
different topK values, Expass improves the oversmoothing, AUROC, and F1-score
performance of vanilla message passing by 71.16%, 9.53%, and 12.63%,
respectively (Figure 3).

(a) Group Distance Ratio (b) AUROC (c) F1-Score

Figure 3:  The effects of choosing only the topK percent of important edges on
the (a) oversmoothing, (b) AUROC, and (c) F1-score performance of GCN model
trained on Alkane-Carbonyl dataset. Over a wide range of topK values
($0.1<\text{topK}<1.0$), Expass outperforms DropEdge [45] on all the three
metrics. Note that their performance converges for $\text{topK}=1.0$ as that
denotes using all the edges in the graph.

Expass using Node Explanations. We investigate the effect of the choice of the
baseline explanation method on the performance of Expass with respect to the
vanilla message passing framework. More specifically, we evaluate the
predictive and explainability performance of Expass-augmented GNNs when
trained using node explanations generated using Integrated Gradients (IG)
[44]. Similar to the results of Expass with GNNExplainer as the baseline
explanation method (Table 1), we find that Expass trained using IG
explanations also improves the AUROC (+2.80%), F1-score (+1.11%), and GEF
(+23.67%) of the vanilla GNN model. Our results show that the choice of
explainer can make a difference in the Expass performance, depending on the
dataset. For instance, IG is a node-masking explainer that is not considered a
strong explanation method and its effects are variable across datasets [33].
We recommend using graph-specific explainers that optimize for fidelity and
sparsity on the edges of the input graph, which would be a best fit to
increase the performance of the network. See Appendix C.3 for results using
PGMExplainer. Further, our results show that Expass is a model- and explainer-
agnostic framework that can improve the downstream task and explainability
performance across different GNN architectures using diverse GNN explainers.

Expass vs. Attention. We demonstrate the utility of using explanations vs.
attention weights in the message passing step using GAT [43] model
architecture. On average, across four datasets, we find that Expass achieves
higher AUROC (+3.85%) and F1-score (+2.24%) than the attention-based GAT model
(Table 3). In addition, GNNExplainer [13] demonstrated that post hoc GNN
explainers generate better explanations than attention weights, which further
highlights the benefits of Expass. In comparison to Expass, GAT can be
considered as a special case of our framework, where attention weights replace
explanations. On the other hand, Expass has larger benefits since it can be
applied to any existing GNN architectures that lack explainability.

Table 2: Results of Expass for GCN using the node explanations from Integrated Gradients [44] for message passing for various datasets. Shown is average performance across three independent runs. Arrows ($\uparrow$, $\downarrow$) indicate the direction of better performance. Expass improves the predictive power (AUROC and F1-score) and degree of explainability (Graph Explanation Faithfulness) of original GNNs across multiple datasets (shaded area).  Dataset | Method | AUROC ($\uparrow$) | F1-score ($\uparrow$) | GEF ($\downarrow$)
---|---|---|---|---
| DD
---
| GCN
---
Expass-GCN
| 0.73$\pm$0.02
---
0.75$\pm$0.01
| 0.70$\pm$0.02
---
0.71$\pm$0.03
| 0.25$\pm$0.03
---
0.23$\pm$0.04
| Alkane
---
| GCN
---
Expass-GCN
| 0.97$\pm$0.01
---
0.97$\pm$0.01
| 0.95$\pm$0.01
---
0.95$\pm$0.01
|  0.09$\pm$0.01
---
0.1$\pm$0.01
| Mutag
---
| GCN
---
Expass-GCN
| 0.71$\pm$0.11
---
0.77$\pm$0.02
| 0.87 $\pm$0.01
---
0.88$\pm$0.01
| 0.09$\pm$0.02
---
0.04$\pm$0.02
| Proteins
---
| GCN
---
Expass-GCN
| 0.73$\pm$0.04
---
0.73$\pm$0.04
|  0.68$\pm$0.04
---
0.67$\pm$0.05
| 0.05$\pm$0.01
---
0.04$\pm$0.01
Table 3: Results of Expass and GAT for various datasets. Shown is the average performance across three independent runs. Arrows ($\uparrow$, $\downarrow$) indicate the direction of better performance. Expass improves the predictive power (AUROC and F1-score) and degree of explainability (Graph Explanation Faithfulness) of original GNNs across multiple datasets (shaded area).  Dataset | Method | AUROC ($\uparrow$) | F1-score ($\uparrow$)
---|---|---|---
| DD
---
| GAT
---
Expass-GCN
| 0.72$\pm$0.02
---
0.74$\pm$0.01
| 0.68$\pm$0.03
---
0.70$\pm$0.01
| Alkane
---
| GAT
---
Expass-GCN
| 0.97$\pm$0.01
---
0.98$\pm$0.00
| 0.95$\pm$0.01
---
0.96$\pm$0.01
| Mutag
---
| GAT
---
Expass-GCN
| 0.69$\pm$0.10
---
0.77$\pm$0.02
| 0.86 $\pm$0.01
---
0.89$\pm$0.00
| Proteins
---
| GAT
---
Expass-GCN
| 0.74$\pm$0.04
---
0.74$\pm$0.03
| 0.68$\pm$0.04
---
0.69$\pm$0.03

Q4) Visualizing explanations. Here, we visualize how the explanation develops
over the training process of the GNN model. In particular, we visualize the
generated explanations from Expass-GCN with GNNExplainer trained on the MUTAG
dataset at different epochs during the training process and find that the
explanations converge to the ground-truth explanation of a non-mutagenic
molecule (i.e., the absence of a carbon ring alongside the highlighted NO2
molecules) as the training progresses (Figure 8). Further, we compare the
generated explanations for a vanilla GCN and its Expass counterpart and find
that the explanation for vanilla GCN falsely identifies the carbon-carbon
bonds as important (Figure 4). This qualitative analysis provides further
evidence for the observed higher faithfulness results (Table 1) of
explanations generated using our proposed Expass framework.

VanillaGCN Expass-GCN

Figure 4: Visualizing the explanation generated for a non-mutagenic molecule
prediction using Vanilla GCN (left) and Expass-GCN (right) with GNNExplainer
method. Note that the explanation from vanilla GCN falsely identifies the
carbon-carbon bonds as important. This qualitative analysis provides further
evidence for the observed higher faithfulness results of explanations
generated using our proposed Expass framework.

##  6 Conclusion

In this work, we propose the problem of learning graph embeddings using
explanation-directed message passing in GNNs. To this end, we introduce
Expass, a novel message-passing framework that can be used with any existing
GNN model and subgraph-optimizing explainer to learn accurate embeddings by
aggregating only embeddings from nodes and edges identified as important by a
GNN explainer. We perform an extensive theoretical analysis to show that
Expass relieves the oversmoothing problem in GNNs, and the embedding
difference between the vanilla message passing framework and Expass can be
upper bounded by the difference of their respective layer weights. Our
empirical results on benchmark datasets show that Expass improves the
explainability of the underlying GNN model without sacrificing its predictive
performance. However, the training of Expass depends on the choice of
explanation method, the number of data points to explain, and the dataset of
choice, which is computationally more expensive than its vanilla counterparts.
We find that the training time of Expass can be improved by using techniques
like batch processing and efficient sampling of correctly-classified nodes and
graphs. Further, adapting post-hoc explainers to generate subgraphs utilizing
the embedding space would also improve the computation time of Expass. Our
proposed method and findings open exciting new avenues to learn graph
representations by jointly training models and explanation methods. We
anticipate that Expass could open new frontiers in graph machine learning for
developing explanation-based training frameworks.

## Acknowledgements

The authors would like to thank the anonymous reviewers for their helpful
feedback that helped improve the work. CA would like to thank Lasse Mohr and
Samuele Firmani for the helpful discussions at the beginning of the project
and LOGML Summer School for connecting with the students. The views expressed
here are those of the authors and do not reflect the official policy or
position of the affiliated company.

## References

  * Zitnik et al. [2018] Marinka Zitnik, Monica Agrawal, and Jure Leskovec.  Modeling polypharmacy side effects with graph convolutional networks.  In _Bioinformatics_ , 2018.
  * Huang et al. [2020a] Kexin Huang, Cao Xiao, Lucas M Glass, Marinka Zitnik, and Jimeng Sun.  Skipgnn: predicting molecular interactions with skip-graph networks.  In _Scientific Reports_ , 2020a.
  * Jin et al. [2020] Guangyin Jin, Qi Wang, Cunchao Zhu, Yanghe Feng, Jincai Huang, and Jiangping Zhou.  Addressing crime situation forecasting task with temporal graph convolutional neural network approach.  In _ICMTMA_ , 2020.
  * Agarwal et al. [2021] Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik.  Towards a unified framework for fair and stable graph representation learning.  In _UAI_. PMLR, 2021.
  * Baldassarre and Azizpour [2019] Federico Baldassarre and Hossein Azizpour.  Explainability techniques for graph convolutional networks.  In _ICML Workshop on Learning and Reasoning with Graph-Structured Representations_ , 2019.
  * Faber et al. [2020] Lukas Faber, Amin K Moghaddam, and Roger Wattenhofer.  Contrastive graph neural network explanation.  In _ICML Workshop on Graph Representation Learning and Beyond_ , 2020\.
  * Huang et al. [2020b] Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, Dawei Yin, and Yi Chang.  Graphlime: Local interpretable model explanations for graph neural networks.  _arXiv_ , 2020b.
  * Lucic et al. [2021] Ana Lucic, Maartje ter Hoeve, Gabriele Tolomei, Maarten de Rijke, and Fabrizio Silvestri.  Cf-gnnexplainer: Counterfactual explanations for graph neural networks.  _arXiv_ , 2021.
  * Luo et al. [2020] Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang.  Parameterized explainer for graph neural network.  In _NeurIPS_ , 2020.
  * Pope et al. [2019] Phillip E Pope, Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann.  Explainability methods for graph convolutional neural networks.  In _CVPR_ , 2019.
  * Schlichtkrull et al. [2021] Michael Sejr Schlichtkrull, Nicola De Cao, and Ivan Titov.  Interpreting graph neural networks for nlp with differentiable edge masking.  In _ICLR_ , 2021.
  * Vu and Thai [2020] Minh N Vu and My T Thai.  Pgm-explainer: Probabilistic graphical model explanations for graph neural networks.  In _NeurIPS_ , 2020.
  * Ying et al. [2019] Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec.  Gnnexplainer: Generating explanations for graph neural networks.  In _NeurIPS_ , 2019.
  * Simonyan et al. [2014] Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman.  Deep inside convolutional networks: Visualising image classification models and saliency maps.  In _ICLR_ , 2014.
  * Yuan et al. [2021] Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji.  On explainability of graph neural networks via subgraph explorations.  In _ICML_ , 2021.
  * Agarwal et al. [2022a] Chirag Agarwal, Owen Queen, Himabindu Lakkaraju, and Marinka Zitnik.  Evaluating explainability for graph neural networks.  _arXiv_ , 2022a.
  * Spinelli et al. [2022] Indro Spinelli, Simone Scardapane, and Aurelio Uncini.  A meta-learning approach for training explainable graph neural networks.  _IEEE TNNLS_ , 2022.
  * Zhou et al. [2020] Kaixiong Zhou, Xiao Huang, Yuening Li, Daochen Zha, Rui Chen, and Xia Hu.  Towards deeper graph neural networks with differentiable group normalization.  _NeurIPS_ , 2020.
  * Oono and Suzuki [2019] Kenta Oono and Taiji Suzuki.  Graph neural networks exponentially lose expressive power for node classification.  _arXiv_ , 2019.
  * Bruna et al. [2013] Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun.  Spectral networks and locally connected networks on graphs.  _arXiv_ , 2013.
  * Henaff et al. [2015] Mikael Henaff, Joan Bruna, and Yann LeCun.  Deep convolutional networks on graph-structured data.  _arXiv_ , 2015.
  * Bianchi et al. [2020] Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi.  Spectral clustering with graph neural networks for graph pooling.  In _ICML_ , 2020.
  * Stachenfeld et al. [2020] Kimberly Stachenfeld, Jonathan Godwin, and Peter Battaglia.  Graph networks with spectral message passing.  _arXiv_ , 2020.
  * Balcilar et al. [2021] Muhammet Balcilar, Renton Guillaume, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine.  Analyzing the expressive power of graph neural networks in a spectral perspective.  In _ICLR_ , 2021.
  * Berg et al. [2017] Rianne van den Berg, Thomas N Kipf, and Max Welling.  Graph convolutional matrix completion.  _arXiv_ , 2017.
  * Xu et al. [2018] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka.  Representation learning on graphs with jumping knowledge networks.  In _ICML_ , 2018.
  * Xu et al. [2019] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  In _ICLR_ , 2019.
  * Hamilton et al. [2017] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In _NeurIPS_ , 2017.
  * Hu et al. [2020] Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun.  Heterogeneous graph transformer.  In _WWW_ , 2020.
  * Wu et al. [2020] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip.  A comprehensive survey on graph neural networks.  In _IEEE TNNLS_ , 2020.
  * Gilmer et al. [2017] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl.  Neural message passing for quantum chemistry.  In _ICML_ , 2017.
  * Han et al. [2020] Zhen Han, Peng Chen, Yunpu Ma, and Volker Tresp.  Explainable subgraph reasoning for forecasting on temporal knowledge graphs.  In _ICLR_ , 2020.
  * Agarwal et al. [2022b] Chirag Agarwal, Marinka Zitnik, and Himabindu Lakkaraju.  Probing gnn explainers: A rigorous theoretical and empirical analysis of gnn explanation methods.  In _AISTATS_ , 2022b.
  * Cai and Wang [2020] Chen Cai and Yusu Wang.  A note on over-smoothing for graph neural networks.  _ArXiv_ , 2020.
  * Zhou et al. [2021] Kaixiong Zhou, Xiao Huang, Daochen Zha, Rui Chen, Li Li, Soo-Hyun Choi, and Xia Hu.  Dirichlet energy constrained learning for deep graph neural networks.  In _NeurIPS_ , 2021.
  * Kazius et al. [2005] Jeroen Kazius, Ross McGuire, and Roberta Bursi.  Derivation and validation of toxicophores for mutagenicity prediction.  In _Journal of medicinal chemistry_ , 2005.
  * Sanchez-Lengeling et al. [2020] Benjamin Sanchez-Lengeling, Jennifer Wei, Brian Lee, Emily Reif, Peter Wang, Wesley Qian, Kevin McCloskey, Lucy Colwell, and Alexander Wiltschko.  Evaluating attribution for graph neural networks.  In _NeurIPS_ , 2020.
  * Shervashidze et al. [2009] Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt.  Efficient graphlet kernels for large graph comparison.  In _AISTATS_ , 2009.
  * Borgwardt et al. [2005] Karsten M. Borgwardt, Cheng Soon Ong, Stefan Schönauer, S. V. N. Vishwanathan, Alex J. Smola, and Hans-Peter Kriegel.  Protein function prediction via graph kernels.  _Bioinformatics_ , 2005.
  * Kipf and Welling [2017] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In _ICLR_ , 2017.
  * Morris et al. [2019] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe.  Weisfeiler and leman go neural: Higher-order graph neural networks.  In _AAAI_ , 2019.
  * Ranjan et al. [2020] Ekagra Ranjan, Soumya Sanyal, and Partha Talukdar.  Asap: Adaptive structure aware pooling for learning hierarchical graph representations.  In _AAAI_ , 2020.
  * Veličković et al. [2018] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  In _ICLR_ , 2018.
  * Sundararajan et al. [2017] Mukund Sundararajan, Ankur Taly, and Qiqi Yan.  Axiomatic attribution for deep networks.  In _ICML_ , 2017.
  * Rong et al. [2020] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang.  Dropedge: Towards deep graph convolutional networks on node classification.  In _ICLR_ , 2020.
  * Dobson and Doig [2003] Paul D. Dobson and Andrew J. Doig.  Distinguishing enzyme structures from non-enzymes without alignments.  _Journal of Molecular Biology_ , 330(4), 2003.
  * Yang et al. [2016] Zhilin Yang, William Cohen, and Ruslan Salakhudinov.  Revisiting semi-supervised learning with graph embeddings.  In _ICML_ , 2016.

##  Appendix A Proofs for Theorems in Section 4

Theorem 1. Given a non-linear activation function $\sigma$ that is Lipschitz
continuous, the difference between the node embeddings between a vanilla
message passing and Expass framework can be bounded by the difference in their
individual weights, i.e.,

$\|\mathbf{h}_{u}^{(l)}-\mathbf{h^{\prime}}_{u}^{(l)}\|_{2}\leq\|\mathbf{W}_{a}^{(l)}{-}\mathbf{W^{\prime}}_{a}^{(l)}\|_{2}\|\mathbf{h}_{u}^{(l-1)}\|_{2}+\|\mathbf{W}_{n}^{(l)}{-}\mathbf{W^{\prime}}_{n}^{(l)}\|_{2}\sum_{\mathclap{v\in\mathcal{N}_{u}\cap
s_{v}=1}}\|\mathbf{h}_{v}^{(l-1)}\|_{2},$ (3)

where $\mathbf{W}_{a}^{(l)}$ and $\mathbf{W^{\prime}}_{a}^{(l)}$ are the
weights for node $u$ in layer $l$ of the vanilla message passing and Expass
framework and $\mathbf{W}_{n}^{(l)}$ and $\mathbf{W^{\prime}}_{n}^{(l)}$ are
their respective weight matrix with the neighbors of node $u$ at layer $l$.

###### Proof.

For a given node $u$, the node representation output by layer $l$ of the GNN
is given by:

$\mathbf{h}_{u}^{(l)}=\sigma\Big{(}\mathbf{W}_{a}^{(l)}\mathbf{h}_{u}^{(l-1)}+\mathbf{W}_{n}^{(l)}\sum_{\mathclap{v\in\mathcal{N}_{u}}}\mathbf{h}_{v}^{(l-1)}\Big{)},$
(4)

where we consider the Agg operator as a fully-connected layer, Upd to be a
sigmoid activation function $\sigma(\cdot)$, $\mathbf{W}_{a}^{(l)}$ is the
weights for node $u$ in layer $l$ and $\mathbf{W}_{n}^{(l)}$ is the weight
matrix with the neighbors of node $u$ at layer $l$.

Let us consider an edge in-hoc explanation that generates a binary mask
highlighting the important edges for the prediction of node $u$. Note that
using the edge mask, we can also get a node-level mask signifying the
importance of neighboring nodes. Let us denote that node explanation mask as
$s_{v}$ where $s_{v}=1$ if the node is important, otherwise $s_{v}=0$.
Formally, the corresponding message passing equations for Expass can be
written as:

$\mathbf{h^{\prime}}_{u}^{(l)}=\sigma\Big{(}\mathbf{W^{\prime}}_{a}^{(l)}\mathbf{h^{\prime}}_{u}^{(l-1)}+\mathbf{W^{\prime}}_{n}^{(l)}\sum_{\mathclap{v\in\mathcal{N}_{u}}}s_{v}\mathbf{h^{\prime}}_{v}^{(l-1)}\Big{)},$
(5)

where $\mathbf{h^{\prime}}_{u}^{(l)}$ and $\mathbf{h^{\prime}}_{v}^{(l)}$
represents the embeddings of node $u$ and $v$ using the feedback explanation,
and $\mathbf{W^{\prime}}_{a}^{(l)}$ and $\mathbf{W^{\prime}}_{n}^{(l)}$
represents the corresponding weights at layer $l$ for GNN model trained using
Expass.

The difference between the node embeddings obtained after the message-passing
in layer $l$ from Equations 4-5 is given as:

$\mathbf{h}_{u}^{(l)}-\mathbf{h^{\prime}}_{u}^{(l)}=\sigma\Big{(}\mathbf{W}_{a}^{(l)}\mathbf{h}_{u}^{(l-1)}+\mathbf{W}_{n}^{(l)}\sum_{\mathclap{v\in\mathcal{N}_{u}}}\mathbf{h}_{v}^{(l-1)}\Big{)}-\sigma\Big{(}\mathbf{W^{\prime}}_{a}^{(l)}~{}\mathbf{h^{\prime}}_{u}^{(l-1)}+\mathbf{W^{\prime}}_{n}^{(l)}~{}\sum_{\mathclap{v\in\mathcal{N}_{u}}}s_{v}\mathbf{h^{\prime}}_{v}^{(l-1)}\Big{)},$
(6)

Taking the $\ell_{2}$-norm on both sides and assuming a normalized Lipschitz
non-linear sigmoid activation, i.e.,
$\|\sigma(b)-\sigma(a)\|_{2}\leq\|b-a\|_{2}$, we get:

$\displaystyle\|\mathbf{h}_{u}^{(l)}-\mathbf{h^{\prime}}_{u}^{(l)}\|_{2}$
$\displaystyle=\|\sigma\Big{(}\mathbf{W}_{a}^{(l)}\mathbf{h}_{u}^{(l-1)}{+}\mathbf{W}_{n}^{(l)}\sum_{\mathclap{v\in\mathcal{N}_{u}}}\mathbf{h}_{v}^{(l-1)}\Big{)}{-}\sigma\Big{(}\mathbf{W^{\prime}}_{a}^{(l)}~{}\mathbf{h^{\prime}}_{u}^{(l-1)}{+}\mathbf{W^{\prime}}_{n}^{(l)}~{}\sum_{\mathclap{v\in\mathcal{N}_{u}}}s_{v}\mathbf{h^{\prime}}_{v}^{(l-1)}\Big{)}\|_{2}$
$\displaystyle\leq\|\mathbf{W}_{a}^{(l)}\mathbf{h}_{u}^{(l-1)}+\mathbf{W}_{n}^{(l)}\sum_{\mathclap{v\in\mathcal{N}_{u}}}\mathbf{h}_{v}^{(l-1)}-\mathbf{W^{\prime}}_{a}^{(l)}~{}\mathbf{h^{\prime}}_{u}^{(l-1)}-\mathbf{W^{\prime}}_{n}^{(l)}~{}\sum_{\mathclap{v\in\mathcal{N}_{u}}}s_{v}\mathbf{h^{\prime}}_{v}^{(l-1)}\|_{2}$
$\displaystyle\leq\|\mathbf{W}_{a}^{(l)}\mathbf{h}_{u}^{(l-1)}-\mathbf{W^{\prime}}_{a}^{(l)}~{}\mathbf{h^{\prime}}_{u}^{(l-1)}+\mathbf{W}_{n}^{(l)}\sum_{\mathclap{v\in\mathcal{N}_{u}}}\mathbf{h}_{v}^{(l-1)}-\mathbf{W^{\prime}}_{n}^{(l)}\sum_{\mathclap{v\in\mathcal{N}_{u}}}s_{v}\mathbf{h^{\prime}}_{v}^{(l-1)}\|_{2}$
$\displaystyle\leq\|\mathbf{W}_{a}^{(l)}\mathbf{h}_{u}^{(l-1)}{-}\mathbf{W^{\prime}}_{a}^{(l)}~{}\mathbf{h}_{u}^{(l-1)}\|_{2}{+}\|\mathbf{W}_{n}^{(l)}\sum_{\mathclap{v\in\mathcal{N}_{u}\cap
s_{v}=0}}\mathbf{h}_{v}^{(l-1)}{+}(\mathbf{W}_{n}^{(l)}-\mathbf{W^{\prime}}_{n}^{(l)})\sum_{\mathclap{v\in\mathcal{N}_{u}\cap
s_{v}=1}}\mathbf{h}_{v}^{(l-1)}\|_{2}$ (Using Triangle Inequality and
Faithfulness property of explanations)

Given a faithful explanation, the node embeddings for node $u$ using the
vanilla message passing network are equivalent to that Expass since most
explainers optimize the mask to approximate the input embedding. More
specifically, for a given node embedding
$\mathbf{h^{\prime}}_{u}^{(l-1)}=\mathbf{h}_{u}^{(l-1)}+\epsilon_{u}$, a
faithful explanation bounds the $\epsilon_{u}$ to zero. In addition to
faithfulness, a GNN using vanilla message passing and Expass can predict a
node $u$ to the same class only if both frameworks generate similar node
embeddings (Proposition 1 in Agarwal et al. [4]).

Using Matrix-norm and Triangle Inequality for the sum in the neighborhood, we
get:

$\displaystyle\|\mathbf{h}_{u}^{(l)}-\mathbf{h^{\prime}}_{u}^{(l)}\|_{2}\leq\|(\mathbf{W}_{a}^{(l)}-\mathbf{W^{\prime}}_{a}^{(l)})~{}\mathbf{h}_{u}^{(l-1)}\|_{2}+\|\mathbf{W}_{n}^{(l)}\|_{2}\sum_{\mathclap{v\in\mathcal{N}_{u}\cap
s_{v}=0}}\|\mathbf{h}_{v}^{(l-1)}\|_{2}+$
$\displaystyle\|\mathbf{W}_{n}^{(l)}-\mathbf{W^{\prime}}_{n}^{(l)}\|_{2}\sum_{\mathclap{v\in\mathcal{N}_{u}\cap
s_{v}=1}}\|\mathbf{h}_{v}^{(l-1)}\|_{2}$

Again, using the faithfulness property of explanations, the contribution of
node embeddings from node $v\in\mathcal{N}(u)\cap s_{v}=0$ is irrelevant to
the final embedding and can be removed. Finally, using Matrix-norm inequality
on the first term, we get:

$\displaystyle\|\mathbf{h}_{u}^{(l)}-\mathbf{h^{\prime}}_{u}^{(l)}\|_{2}$
$\displaystyle\leq\|\mathbf{W}_{a}^{(l)}{-}\mathbf{W^{\prime}}_{a}^{(l)}\|_{2}\|\mathbf{h}_{u}^{(l-1)}\|_{2}+\|\mathbf{W}_{n}^{(l)}{-}\mathbf{W^{\prime}}_{n}^{(l)}\|_{2}\sum_{\mathclap{v\in\mathcal{N}(u)\cap
s_{v}=1}}\|\mathbf{h}_{v}^{(l-1)}\|_{2}$

Thus, we observe that the embedding difference at layer $l$ between a vanilla
message passing network and the Expass is purely based on the difference
between their weights and the embeddings of node $u$ and its subgraph. ∎

######  Definition 2 (Dirichlet Energy for a Node Embedding Matrix [35]).

Given a node embedding matrix
$\mathbf{h}^{(l)}=[\mathbf{h}_{1}^{(l)},\dots,\mathbf{h}_{n}^{(l)}]^{T}$
learned from the GNN model at the $l^{th}$ layer, the Dirichlet Energy
$E(\mathbf{h}^{(l)})$ is defined as:

$E(\mathbf{h}^{(l)})=tr(\mathbf{h}^{(l)^{T}}\tilde{\Delta}\mathbf{h}^{(l)})=\frac{1}{2}\sum_{i,j\in\mathcal{V}}a_{ij}||\frac{\mathbf{h}_{i}^{(l)}}{\sqrt{1+d_{i}}}-\frac{\mathbf{h}_{j}^{(l)}}{\sqrt{1+d_{j}}}||_{2}^{2}$
(7)

where $a_{ij}$ are elements in the adjacency matrix $\tilde{\mathbf{A}}$ and
$d_{i},d_{j}$ is the degree of node $i$ and $j$, respectively.

Cai et al. [34] extensively show that higher Dirichlet energies correspond to
lower oversmoothing. Furthermore, they show that the removal of edges or
,similarly, reduction of edge weights on graphs help alleviate oversmoothing.

Proposition 1 (Expass relieves Oversmoothing). Expass alleviates oversmoothing
by slowing the layer-wise loss of Dirichlet energy.

###### Proof Sketch.

Here, we show the capabilities of Expass as a framework that alleviates the
oversmoothing problem in GNNs. To this end, we utilize the bounds on the
Dirichlet energy of the Expass embeddings at the $l^{th}$ layer of the GNN
model by Zhou et al. [35]:

$(1-\lambda_{1})^{2}s^{(l)}_{min}E(\mathbf{h}^{(l-1)})\leq
E(\mathbf{h}^{(l)})\leq(1-\lambda_{0})^{2}s^{(l)}_{max}E(\mathbf{h}^{(l-1)}),$
(8)

where $\lambda_{1},\lambda_{0}$ are the non-zero eigenvalues of the symmetric
normalized Laplacian $\tilde{\Delta}$ that is closest to 1 and 0,
respectively, and $s^{(l)}_{min},s^{(l)}_{max}$ are the squares of the minimum
and maximum singular values of weight $\mathbf{W}^{(l)}$, respectively. Since
Expass reduces the input graph to its specific explanation, we argue that it
can alleviate oversmoothing by reducing the information propagation along
irrelevant nodes and edges. From the perspective of Dirichlet energy, we know
from [19] that, for Erdős-Rényi graphs, $\lambda_{0}$ converges to 1 as the
graph becomes denser. Oono et al. [19] state that GNNs oversmooth on
sufficiently large graphs (similar to Erdős-Rényi graphs). Under this
assumption, Expass, by definition introduces sparsity inside the
$\tilde{\Delta}$ of the input graph by using a smaller set of topK important
edges for learning embeddings and, thus, reduces $\lambda_{0}$ to tighten the
upper-bound in Equation 8. In practice, the choice of explainer used in Expass
can reduce $\lambda_{0}$ to varying degrees. More specifically, explainers
that promote sparsity would push $\lambda_{0}$ closer to zero and slow down
the decrease of Dirichlet energy in subsequent GNN layers. Finally, we know
from Cai et al. [34] that higher values of Dirichlet energy per layer
correspond to lower oversmoothing, we assert that Expass alleviates
oversmoothing. ∎

##  Appendix B Experiment

###  B.1 Datasets

Mutag. The MUTAG [36] dataset contains 188 graph molecules labeled into two
different classes according to their mutagenic properties, i.e., effect on the
Gram-negative bacterium S. Typhimuriuma. Kazius et al. [36] identifies several
toxicophores - motifs in the molecular graph - that correlate with
mutagenicity.

Alkane-Carbonyl. The Alkane-Carbonyl [37] dataset contains 1,125 molecular
graphs categorized into two classes where an instance in the positive group
indicates a molecule that contains an unbranched alkane and a carbonyl (C=O)
functional group.

DD. The DD [38] dataset was derived from [46] and contains 1,178 protein
graphs where nodes represent individual amino-acids and edges represent their
spatial proximity. The task is to predict whether a given protein is an enzyme
or not.

Proteins. The Proteins [39] dataset was derived from [46] and contains 1,113
protein graphs where nodes represent secondary structure elements and edges
indicate neighborhood in the amino-acid sequence or the 3D space. The task is
to predict whether a given protein is an enzyme or not.

PubMed. The PubMed dataset [47] is a citation network from the PubMed
database, with over 4 million nodes and edges respectively. It contains a bag-
of-words representation of documents and citation links between documents. The
task is to predict a node’s class among 3 classes.

###  B.2 Implementation details

GNN libraries and models. All our models were implemented using PyTorch
Geometric (2.1.0) and PyTorch (1.11.0). For our experiments, we used baseline
GNN architectures with three layers followed by ReLU layers and set the hidden
dimensionality to 32. Finally, we used a single linear layer to transform the
graph embeddings to their respective classes. We selected Adam as our
optimizer and a weighted Cross Entropy Loss to train both vanilla and Expass
frameworks. All models were trained over three independent runs with a
learning rate of 0.01 for 200 epochs for DD and Proteins datasets and 150
epochs for Alkane and MUTAG datasets.

Expass. We define the burn-in period as a number of epochs during training in
which no explanations are used. The burn-in period is necessary to avoid
feeding spurious explanations to the model since an untrained model can lead
to unfaithful explanations. The length of the burn-in period was treated as a
hyperparameter and fine-tuned during the model fine-tuning phase. After fine-
tuning, we found that a burn-in period in the range [5, 15] worked best,
whereas most Expass models outperformed their vanilla counterparts using a
burn-in period of 5 and 10 epochs in our experiments. We generated
explanations for a specific percentage of correctly predicted graphs sampled
in each batch and were set to 0.4 for all our experiments. The generated
explanations are normalized to [0, 1] and hard-masked over the topK most
relevant edges, where topK is a percentage of the total number of edges in the
input graph and was set to $\text{topK}\in[0.3,0.4]$ for our experiments.

GNN explanation methods. At each epoch, the model weights were frozen to
generate explanations, which were calculated as the median over n independent
runs of GNNExplainer, in order to obtain consistent explanations. Then, the
model weights were trained using generated explanations. We chose the median
instead of the mean to prevent the individual outliers from significantly
changing the final explanations. The number of individual runs of an explainer
was treated as a hyperparameter and was set to five for GNNExplainer and one
for Integrated Gradients (as it generates consistent explanations over
multiple runs). In each run, the GNNExplainer was trained for 200 epochs (150
in the case of Alkane) with a learning rate of 0.01. All other hyperparameters
of the explanation methods were set using the author’s guidelines. Note that
these multiple iterations of the explainers are not required for Expass to
perform well when using other stable GNN explainers. To summarize, the
following parameters were treated as hyperparameters: the learning rate of the
model, the learning rate of the explanation method, the number of epochs the
explanation method was trained for, the number of times the GNNExplainer was
computed at each epoch for each sampled graph, the percentage of correctly
classified graphs that were randomly sampled to compute the explanations and
the percentage of top edges/nodes that were selected as the most relevant. On
the other hand, in the case of vanilla models, the learning rate was fine-
tuned during the tuning phase.

Dataset. The train, validation, and test split was at 80%, 10%, and 10% for
Alkane, Proteins, and DD following prior works. In the case of MUTAG, no
validation set was used due to the smaller dataset size, and the train and
test split was at 80% and 20%.

GNN performance metric. The GEF scores were evaluated as the mean over the
individual scores of all generated explanations on the test dataset, where the
explanations were hard-masked with $\textup{topK}=0.1$ for GNNExplainer, and
$\textup{topK}=0.25$ for Integrated Gradients/PGMExplainer. Note that, since
Integrated Gradients/PGMExplainer generates a node mask instead of an edge
mask, we required a higher topK value to generate a non-empty hard mask over
the input graphs, since we retain the topK most relevant nodes in the
explanation mask.

(a) Group Distance Ratio (b) AUROC (c) F1-Score

Figure 5: The effects of the number of GNN layers on the (a) oversmoothing,
(b) AUROC, and (c) F1-score performance of Expass-GCN and Vanilla-GCN trained
on Alkane-Carbonyl dataset. Across models with increasing number of layers,
Expass achieves higher GDR performance without sacrificing the predictive
performance of the GCN model.

(a) Group Distance Ratio (b) AUROC (c) F1-Score

Figure 6: The effects of the number of GNN layers on the (a) oversmoothing,
(b) AUROC, and (c) F1-score performance of Expass-GIN and Vanilla-GIN trained
on Alkane-Carbonyl dataset. We observe that, across models with an increasing
number of layers, Expass achieves higher GDR performance and there exists an
inherent trade-off between oversmoothing and predictive performance of GIN.

##  Appendix C Additional results

###  C.1 Node classification results

We extend our proposed framework to GNN models trained on different graph
downstream tasks. In particular, we conduct additional experiments to obtain
the over-smoothing and predictive behavior of Expass for node-level tasks. We
train five state-of-the-art GNN models and their Expass counterparts on the
PubMed node classification dataset. Our results show that Expass alleviates
the over-smoothing effect in GNNs for models with higher depths (Figure 7) and
achieves on-par or higher predictive performance (Table 4). We find that, on
average, Expass augmented GCN achieves 19.53% better over-smoothing
performance for node-classification GNN models with higher depths.

Table 4: Results of Expass for five GNNs using PubMed node classification dataset. Shown is the average performance across five independent runs. Arrows ($\uparrow$, $\downarrow$) indicate the direction of better performance. Expass improves the predictive power (testing accuracy) of original GNNs across multiple datasets (shaded area).  Method | Testing Accuracy ($\uparrow$)
---|---
| GCN
---
Expass-GCN
| 0.7596$\pm$0.002
---
0.7616$\pm$0.002
| GraphConv
---
Expass-GraphConv
| 0.7652$\pm$0.002
---
0.7682$\pm$0.002
| LeConv
---
Expass-LeConv
| 0.7424$\pm$0.003
---
0.7244$\pm$0.010
| GraphSAGE
---
Expass-GraphSAGE
| 0.7462$\pm$0.004
---
0.7533$\pm$0.002
| GIN
---
Expass-GIN
| 0.7233$\pm$0.002
---
0.7310$\pm$0.009

(a) Group Distance Ratio (b) Accuracy

Figure 7: The effects of the number of GNN layers on the (a) oversmoothing,
(b) testing accuracy performance of Expass-GCN and Vanilla-GCN trained on
PubMed node classification dataset. We observe that, across models with an
increasing number of layers, Expass achieves higher GDR performance and
achieves on-par or better testing accuracy.

###  C.2 Burn-in period

The burn-in period was treated as a hyperparameter and fine-tuned for each
dataset and architecture. An example of the effect of the burn-in period on
the AUROC and F1-score is reported in Table 5, where the change in performance
is evaluated for the Proteins dataset when using a lag of 5, 10, and 15.

Table 5: Results of Expass for various burn-in periods. Shown is the average performance across three independent runs (and standard error). Arrows ($\uparrow$, $\downarrow$) indicate the direction of better performance.  Method | Burn-in period | AUROC ($\uparrow$) | F1-score ($\uparrow$)
---|---|---|---
|  Expass-GIN
---
| 5
---
10
15
| 0.76 $\pm$0.04
---
0.78$\pm$0.03
0.78$\pm$0.03
| 0.72$\pm$0.05
---
0.73$\pm$0.04
0.73$\pm$0.03
|  Expass-GraphSAGE
---
| 5
---
10
15
| 0.73 $\pm$0.04
---
0.73$\pm$0.04
0.73$\pm$0.04
| 0.68$\pm$0.04
---
0.69$\pm$0.04
0.69$\pm$0.04
|  Expass-LeConv
---
| 5
---
10
15
|  0.76$\pm$0.02
---
0.74$\pm$0.04
0.75$\pm$0.03
|  0.71$\pm$0.03
---
0.69$\pm$0.04
0.71$\pm$0.03

###  C.3 PGMExplainer results

Here, we showcase the flexibility of the Expass with respect to different GNN
explainers. In Table 6, we show the effectiveness of Expass with respect to
different explainers by further utilizing PGMExplainer [12] as the explanation
generator. We utilize the graph explanations of PGMExplainer as node masks on
the input graph (as they cannot generate edge-level masks) and incorporate
them using our explanation-aware message-passing scheme with GCN as our
underlying architecture. On average, across three datasets, we find that
Expass trained using PGM-Explainer achieves higher GEF (+36.56%) than their
vanilla counterparts (Table 6). Also, it achieves a boost of 11.27% in AUROC
for MUTAG and a 1% improvement in the F1-score for the Alkane dataset. We
observe that PGMExplainer, similar to Integrated Gradients, produces node
masks, which lack detail and do not provide finer changes to the underlying
GNN model, like edge masks. We hypothesize that this contributes to the large
variation in the predictive performance across datasets.

Table 6: Results of Expass for GCN using the node explanations from PGMExplainer [12] for message passing for various datasets. Shown is the average performance across three independent runs. Arrows ($\uparrow$, $\downarrow$) indicate the direction of better performance. Expass improves the predictive power (AUROC and F1-score) and degree of explainability (Graph Explanation Faithfulness) of original GNNs across multiple datasets (shaded area).  Dataset | Method | AUROC ($\uparrow$) | F1-score ($\uparrow$) | GEF ($\downarrow$)
---|---|---|---|---
| Alkane
---
| GCN
---
Expass-GCN
| 0.97$\pm$0.01
---
0.97$\pm$0.01
| 0.95$\pm$0.01
---
0.96$\pm$0.01
| 0.31$\pm$0.02
---
0.28$\pm$0.03
| Mutag
---
| GCN
---
Expass-GCN
| 0.71$\pm$0.11
---
0.79$\pm$0.03
|  0.87$\pm$0.01
---
0.86$\pm$0.01
| 0.21$\pm$0.07
---
0.07$\pm$0.01
| Proteins
---
| GCN
---
Expass-GCN
| 0.73$\pm$0.04
---
0.66$\pm$0.02
|  0.68$\pm$0.04
---
0.67$\pm$0.05
| 0.03$\pm$0.00
---
0.02$\pm$0.00

Epoch 25 Epoch 50 Epoch 75

Epoch 100 Epoch 125 Epoch 149

Figure 8: Generated explanations from Expass-GCN trained on the MUTAG dataset
at different epochs during the training process and find that the explanations
does converge to the ground-truth explanation of a mutagenic molecule (i.e.,
the absence of a carbon ring) as the training progresses. This qualitative
analysis provides further evidence for the observed higher faithfulness
results of explanations generated using our proposed Expass framework.