1 Technical University of Munich, 2 Florida International University
<EMAIL_ADDRESS><EMAIL_ADDRESS>
# Factorized Explainer for Graph Neural Networks

Rundong Huang1, Farhad Shirani2∗, Dongsheng Luo2 Corresponding authors.

###### Abstract

Graph Neural Networks (GNNs) have received increasing attention due to their
ability to learn from graph-structured data. To open the black-box of these
deep learning models, post-hoc instance-level explanation methods have been
proposed to understand GNN predictions. These methods seek to discover
substructures that explain the prediction behavior of a trained GNN. In this
paper, we show analytically that for a large class of explanation tasks,
conventional approaches, which are based on the principle of graph information
bottleneck (GIB), admit trivial solutions that do not align with the notion of
explainability. Instead, we argue that a modified GIB principle may be used to
avoid the aforementioned trivial solutions. We further introduce a novel
factorized explanation model with theoretical performance guarantees. The
modified GIB is used to analyze the structural properties of the proposed
factorized explainer. We conduct extensive experiments on both synthetic and
real-world datasets to validate the effectiveness of our proposed factorized
explainer over existing approaches.

## Introduction

Graph-structured data is ubiquitous in real-world applications, manifesting in
various domains such as social networks Fan2019GraphNN, molecular structures
Mansimov2019MolecularGP; Chereda2019UtilizingMN, and knowledge graphs
liu2022federated. This has led to significant interest in learning
methodologies specific to graphical data, particularly, graph neural networks
(GNNs). GNNs commonly employ message-passing mechanisms, recursively
transmitting and fusing messages among neighboring nodes on graphs. Thus, the
learned node representation captures both node attributes and neighborhood
information, thereby enabling diverse downstream tasks such as node
classification kipf2017semisupervised; veličković2018graph;
hamilton2017inductive, graph classification xu2018how, and link prediction
lu2022graph.

Despite the success of GNNs in a wide range of domains, their inherent “black-
box” nature and lack of interpretability, a characteristic shared among many
contemporary machine learning methods, is a major roadblock in their utility
in sensitive application scenarios such as autonomous decision systems. To
address this, various GNN explanation methods have been proposed to understand
the graph-structured data and associated deep graph learning models
ying2019gnnexplainer; luo2020parameterized; yuan2022explainability;
wang2023empower; qiang2023counterfactual; xiong2023relevant. In particular,
post-hoc instance-level explanation methods provide an effective way to
identify determinant substructures in the input graph, which plays a vital
role in trustworthy deployments ying2019gnnexplainer; luo2020parameterized. In
the context of graph classification, the objective of graph explanation
methods is, given a graph $G$, to extract a minimal and sufficient subgraph,
$G^{*}$, that can be used to determine the instance label, $Y$. The Graph
Information Bottleneck principle (GIB) wu2020graph provides an intuitive
principle that is widely adopted as a practical instantiation. At a high
level, the GIB principle finds the subgraph $G^{*}$ which minimizes the mutual
information between the original graph $G$ and the subgraph $G^{*}$ and
maximizes the mutual information between the subgraph $G^{*}$ and instance
label $Y$ by minimizing $I(G,G^{*})-\alpha I(G^{*},Y)$, where the
hyperparameter $\alpha>0$ captures the tradeoff between minimality and
informativeness of $G^{*}$ miao2022interpretable. As an example, the
GNNExplainer method operates by finding a learnable edge mask matrix, which is
optimized by the GIB objective ying2019gnnexplainer. The PGExplainer also uses
a GIB-based objective and incorporates a parametric generator to learn
explanatory subgraphs from the model’s output luo2020parameterized.

There are several limitations in the existing explainability approaches.
First, as shown analytically in this work, existing GIB-based methods suffer
from perceptually unrealistic explanations. Specifically, we show that in a
wide-range of statistical scenarios, the original GIB formulation of the
explainability problem has a trivial solution where the achieved explanation
$G^{*}$ signals the predicted value of $Y$, but is independent of the input
graph $G$, otherwise. That is, the Markov chain $G^{*}\leftrightarrow
Y\leftrightarrow G$ holds. As a result, the explanation $G^{*}$ optimizing the
GIB objective may consist of a few disconnected edges and fails to align with
the high-level notion of explainability. To alleviate this problem,
PGExplainer includes an ad-hoc connectivity constraint as the regularization
term luo2020parameterized. However, without theoretical guarantees, the
effectiveness of the extra regularization is marginal in more complicated
datasets shan2021reinforcement. Second, although previous parametric
explanation methods, such as PGExplainer luo2020parameterized and ReFine
wang2021towards, are efficient in the inductive setting, these methods neglect
the existence of multiple motifs, which is routinely observed in real-life
datasets. For example, In the MUTAG dataset debnath1991structure, both
chemical components $NO_{2}$ and $NH_{2}$, which can be considered as
explanation subgraphs, contribute to the positive mutagenicity. Existing
methods over-simplify the relationship between motifs and labels to one-to-
one, leading to inaccuracy in real-life applications.

To address these issues, we first analytically investigate the pitfalls of the
application of the GIB principle in explanation tasks from an information
theoretic perspective, and propose a modified GIB principle that avoids these
issues. To further improve the inductive performance, we propose a new
framework to unify existing parametric methods and show that their
suboptimality is caused by their locality property and the lossy aggregation
step in GNNs. We further propose a straightforward and effective
factorization-based explanation method to break the limitation of existing
local explanation functions. We summarize our main contributions as follows.

  * •

For the first time, we point out that the gap between the practical objective
function (GIB) and high-level objective is non-negligible in the most popular
post-hoc explanation framework for graph neural networks.

  * •

We derive a generalized framework to unify existing parametric explanation
methods and theoretically analyze their pitfalls in achieving accurate
explanations in complicated real-life datasets. We further propose a
straightforward explanation method with a solid theoretical foundation to
achieve better generalization capacity.

  * •

Comprehensive empirical studies on both synthetic and real-life datasets
demonstrate that our method can dramatically and consistently improve the
quality of the explanations.

## Preliminary

### Notations and Problem Definition

A graph $G$ is parameterized by a quadruple
$(\mathcal{V},\mathcal{E};\mathbf{Z},\mathbf{A})$, where i)
$\mathcal{V}=\\{v_{1},v_{2},...,v_{n}\\}$ is the node/vertex111We use node and
vertex interchangeably. set, ii) $\mathcal{E}\in\mathcal{V}\times\mathcal{V}$
is the edge set, iii) $\mathbf{Z}\in\sR^{n\times d}$ is the feature matrix,
where the $i$th row of $\mathbf{Z}$, denoted by $\mathbf{z}_{i}\in\sR^{1\times
d}$, is the $d$-dimensional feature vector associated with node
$v_{i},i\in[n]$, and iv) the adjacency matrix $\mathbf{A}\in\\{0,1\\}^{n\times
n}$ is determined by the edge set $\mathcal{E}$, where $\emA_{ij}=1$ if
$(v_{i},v_{j})\in\mathcal{E}$, $\emA_{ij}=0$, otherwise. We write $|G|$ and
$|\mathcal{E}|$ interchangeably to denote the number of edges of $G$.

For graph classification task, each graph $G_{i}$ has a label
$Y_{i}\in\mathcal{C}$, with a GNN model $f$ trained to classify $G_{i}$ into
its class, i.e., $f:G\mapsto\\{1,2,\cdots,|\mathcal{C}|\\}$. For the node
classification task, each graph $G_{i}$ denotes a $K$-hop sub-graph centered
around node $v_{i}$, with a GNN model $f$ trained to predict the label for
node $v_{i}$ based on the node representation of $v_{i}$ learned from $G_{i}$.

######  Problem 1 (Post-hoc Instance-level GNN Explanation
yuan2022explainability; luo2020parameterized; ying2019gnnexplainer).

Given a trained GNN model $f$, for an arbitrary input graph
$G=(\mathcal{V},\mathcal{E};\mathbf{Z},\mathbf{A})$, the goal of post-hoc
instance-level GNN explanation is to find a subgraph $G^{*}=\Psi(G)$ that can
‘explain’222The notion of explainability is made precise in the sequel, where
the modified GIB principle is introduced. the prediction of $f$ on $G$. The
mapping $\Psi:G\mapsto G^{*}$ is called the explanation function.

Informative feature selection has been well studied in non-graph structured
data li2017feature, and traditional methods, such as concrete autoencoder
abid2019concrete, can be directly extended to explain features in GNNs. In
this paper, we focus on discovering important typologies. Formally, the
obtained explanation $G^{*}$ is characterized by a binary mask
$\mM\in\\{0,1\\}^{n\times n}$ on the adjacency matrix, e.g.,
$G^{*}=(\gV,\gE,\mathbf{A}\odot\mathbf{M};\mathbf{Z})$, where $\odot$ is
elements-wise multiplication. The mask highlights components of $G$ which
influence the output of $f$.

### Graph Information Bottleneck

The GIB principle refers to the graphical version of the Information
Bottleneck (IB) principle tishby2015deep which offers an intuitive measure for
learning dense representations. It is based on the notion that an optimal
representation should contain minimal and sufficient information for the
downstream prediction task. Recently, a high-level unification of several
existing post hoc GNN explanation methods, such as GNNExplainer
ying2019gnnexplainer, and PGExplainer luo2020parameterized was provided using
this concept wu2020graph; miao2022interpretable; yu2021graph. Formally, prior
works have represented the objective of finding an explanation graph $G^{*}$
in $G$ as follows:

$G^{*}\triangleq\argmin_{P_{G^{\prime}|G}:\mathbb{E}(|G^{\prime}|)\leq\gamma}I(G,G^{\prime})-\alpha
I(G^{\prime},Y),$ (1)

where $G^{*}$ is the explanation subgraph, $\gamma\in\mathbb{N}$ is the
maximum expected size (number of edges) of the explanation, $Y$ is the
original or ground truth label, and $\alpha$ is a hyper-parameter capturing
the trade-off between minimality and sufficiency constraints. At a high level,
the GIB formulation given in (1) selects the minimal explanation $G^{\prime}$,
by minimizing $I(G,G^{\prime})$ and imposing
$\mathbb{E}(|G^{\prime}|)\leq\gamma$, that inherits only the most indicative
information from $G$ to predict the label $Y$, by maximizing
$I(G^{\prime},Y)$, while avoiding imposing potentially biased constraints,
such the connectivity of the selected subgraphs and exact maximum size
constraints miao2022interpretable. Note that from the definition of mutual
information, we have $I(G^{\prime},Y)=H(Y)-H(Y|G^{\prime})$, where the entropy
$H(Y)$ is static and independent of the explanation process. Thus, minimizing
the mutual information between the explanation subgraph $G^{\prime}$ and $Y$
can be reformulated as maximizing the conditional entropy of $Y$ given
$G^{\prime}$. That is:

$G^{*}=\argmin_{P_{G^{\prime}|G}:\mathbb{E}(|G^{\prime}|)\leq\gamma}{I(G,G^{\prime})+\alpha
H(Y|G^{\prime})}.$ (2)

## Graph Information Bottleneck for Explanation

In this section, we study several pitfalls arising from the application of the
GIB principle to explanation tasks. We demonstrate that, for a broad range of
learning tasks, the original GIB formulation of the explainability problem has
a trivial solution that does not align with the intuitive notion of
explainability. We propose a modified version of the GIB principle that avoids
this trivial solution and is applicable in constructing GNN explanation
methods. The analytical derivations in subsequent sections will focus on this
modified GIB principle. To elaborate, we argue that the optimization given in
(2) is prone to signaling issues and, in general, does not fully align
theoretically with the notion of explainability. More precisely, the GIB
formulation allows for an explanation algorithm to output $G^{*}$ which
signals the predicted value of $Y$, but is independent of the input graph $G$
otherwise. To state this more concretely, we consider the class of
statistically degraded classification tasks defined in the following.

######  Definition 1 (Statistically Degraded Classification).

Consider a classification task characterized by the triple
$(\mathcal{X},\mathcal{Y},P_{\mathbf{X},Y})$, where $\mathcal{X}$ represents
the feature space, $\mathcal{Y}$ denotes the set of output labels, and
$P_{\mathbf{X},Y}$ characterizes the joint distribution of features and
labels. The classification task is called statistically degraded333Statistical
degradedness has its origins in the field of information theory, particularly
in communication and estimation applications el2010lecture if there exists a
function $h:\mathcal{X}\to\mathcal{Y}$ such that the Markov chain
$\mathbf{X}\leftrightarrow h(\mathbf{X})\leftrightarrow Y$ holds. That is,
$h(\mathbf{X})$ is a sufficient statistic for $\mathbf{X}$ with respect to
$Y$.

######  Remark 1.

Any deterministic classification task, where there exists a function
$h:\mathcal{X}\to\mathcal{Y}$ such that $h(\mathbf{X})=Y$, is statistically
degraded.

######  Remark 2.

There are classification tasks that are not statistically degraded. For
instance, let us consider a classification task in which the feature vector is
$\mathbf{X}=(X_{1},X_{2})$, where $X_{1}$ and $X_{2}$ are independent binary
symmetric variables. Let the label $Y$ be equal to $X_{1}$ with probability
$p\in(0,1)$ and equal to $X_{2}$, otherwise. By exhaustively searching over
all 16 possible choices of $h(\mathbf{X})$, it can be verified that no Boolean
function $h(\mathbf{X})$ exists such that the relationship
$\mathbf{X}\leftrightarrow h(\mathbf{X})\leftrightarrow Y$ holds.
Consequently, the classification task
$(\mathcal{X},\mathcal{Y},P_{\mathbf{X},Y})$ is not statistically degraded.

######  Remark 3.

Note that for the statistically degraded task defined in Definition 1, the
optimal classifier $f^{*}(\mathbf{X})$ is equal to the sufficient statistic
$h(\mathbf{X})$.

In order to show the limitations of the GIB in fully encapsulating the concept
of explainability, in the sequel we focus on statistically degraded
classification tasks involving graph inputs. That is, we take $\mathbf{X}=G$,
where $G$ is the input graph. The next lemma shows that, for any statistically
degraded task, there exists an explanation function $\Psi(\cdot)$ which
optimizes the GIB objective function ((2)), and whose output is independent of
$G$ given $h(\cdot)$. That is, although the explanation algorithm is optimal
in the GIB sense, it does not provide any additional information about the
input of the classifier, in addition to the information that the classifier
output label $h(G)$ readily provides.

######  Theorem 1.

Consider a statistically degraded graph classification task, parametrized by
$(P_{G,Y},h(\cdot))$, where $P_{G,Y}$ is the joint distribution of input
graphs and their labels, and $h:\mathcal{G}\to\mathcal{Y}$ is such that
$G\leftrightarrow h(G)\leftrightarrow Y$ holds. For any $\alpha>0$, there
exists an explanation algorithm $\Psi_{\alpha}(\cdot)$ such that
$G^{\prime}\triangleq\Psi_{\alpha}(G)$ optimizes the objective function in (2)
and $\Psi_{\alpha}(G)\leftrightarrow h(G)\leftrightarrow G$ holds.

The proof relies on the following modified data processing inequality.

######  Lemma 1 (Modified Data Processing Inequality).

Let $A,B$ and $C$ be random variables satisfying the Markov chain
$A\leftrightarrow B\leftrightarrow C$. Define the random variable $A^{\prime}$
such that $P_{A^{\prime}|C}=P_{A|C}$ and $A,B\leftrightarrow C\leftrightarrow
A^{\prime}$. Then,

$\displaystyle I(A^{\prime},B)\leq I(A,B).$

The proof of Lemma 1 and Theorem 1 are included in Appendix.

As shown by Theorem 1, the original GIB formulation does not fully align with
the notion of explainability. Consequently, we adopt the following modified
objective function:

$G^{*}\triangleq\argmin_{P_{G^{\prime}|G}:\mathbb{E}(|G^{\prime}|)\leq\gamma}{I(G,G^{\prime})+\alpha
CE(Y,Y^{\prime})},$ (3)

where $Y^{\prime}\triangleq f(G^{\prime})$ is the predicted label of
$G^{\prime}$ made by the model to be explained $f$, and the cross-entropy
$\text{CE}(Y,Y^{\prime})$ between the ground truth label $Y$ and $Y^{\prime}$
is used in place of $H(Y|G^{\prime})$ in the original GIB. The modified GIB
avoids the signaling issues in Theorem 1, by comparing the correct label $Y$
with the prediction output $Y^{\prime}$ based on the original model
$f(\cdot)$. This is in contrast with the original GIB principle which measures
the mutual information $I(Y,G^{\prime})$, which provides a general measure of
how well $Y$ can be predicted from $G^{\prime}$ (via Fano’s inequality
el2010lecture), without relating this prediction to the original model
$f(\cdot)$. It should be mentioned that several recent works have also adopted
this modified GIB formulation ying2019gnnexplainer; luo2020parameterized.
However, the rationale provided in these earlier studies was that the modified
GIB serves as a computationally efficient approximation for the original GIB,
rather than addressing the limitations of the original GIB shown in Theorem 1.

## K-FactExplainer for Graph Neural Networks

In this section, we first theoretically show that existing parametric
explainers based on the GIB objective, such as PGExplainer
luo2020parameterized, are subject to two sources of inaccuracies: locality and
lossy aggregation. Then we propose a straightforward and effective approach to
mitigating the problem. In the subsequent sections, we provide simulation
results that corroborate these theoretical predictions.

### Theoretical Analysis

We first define the general class of local explanation methods.

######  Definition 2 (Geodisc Restricted Graph).

Given a graph $G=(\mathcal{V},\mathcal{E};\mathbf{Z},\mathbf{A})$, node
$v\in\mathcal{V}$, and a radius $r\in\mathbb{N}$, the $(v,r)$-restriction of
$G$ is the graph
$G_{v,r}=(\mathcal{V}_{v,r},\mathcal{E}_{v,r};\mathbf{Z}_{v,r},\mathbf{A}_{v,r})$,
where

  * •

$\mathcal{V}_{v,r}\triangleq\\{v^{\prime}|d(v,v^{\prime})\leq r\\}$, where
$d(\cdot,\cdot)$ is the geodisc distance.

  * •

$\mathcal{E}_{v,r}\triangleq\\{(v_{i},v_{j})|e\in\mathcal{E},v_{i},v_{j}\in\mathcal{V}_{v,r}\\}$.

  * •

$\mathbf{Z}_{v,r}$ consists of feature vectors in $\mathbf{Z}$ corresponding
to $v\in\mathcal{V}_{v,r}$.

  * •

$\mathbf{A}_{v,r}$ is the adjacency matrix corresponding to
$\mathcal{E}_{v,r}$.

######  Definition 3 (Local Explanation Methods).

Consider a graph classification task $(\mathcal{G},\mathcal{Y},P_{G,Y})$, a
classification function $f:\mathcal{G}\to\mathcal{Y}$, a parameter
$r\in\mathbb{N}$, and an explanation function
$\Psi:\mathcal{G}\to\mathcal{G}$, where $\mathcal{G}$ is the set of all
possible input graphs, and $\mathcal{Y}$ is the set of output labels. Let
$G^{\prime}=\Psi(G)=(\mathcal{V}^{\prime},\mathcal{E}^{\prime};\mathbf{Z}^{\prime},\mathbf{A}^{\prime})$.
The explanation function $\Psi(\cdot)$ is called an $r$-local explanation
function if:

  1. 1.

The Markov chain $\mathbb{1}(v\in\mathcal{V}^{\prime})\leftrightarrow
G_{v,r}\leftrightarrow G$ holds for all $v\in\mathcal{V}$, where
$\mathbb{1}(\cdot)$ is the indicator function.

  2. 2.

The edge $(v,v^{\prime})$ is in $\mathcal{E}^{\prime}$ if and only if
$v,v^{\prime}\in\mathcal{V}^{\prime}$ and $e\in\mathcal{E}$.

The first condition in Definition 3 requires that the presence of each vertex
$v$ in the explanation $G^{\prime}$ only depends on its neighboring vertices
in $G$ which are within its $r$ local neighborhood. The second condition
requires that $G^{\prime}$ be a subgraph of $G$. It is straightforward to show
that various explanation methods such as PGExplainer are local explanation
methods due to the boundedness of their corresponding computation graphs. This
is formalized in the following proposition.

######  Proposition 1 (Locality of PGExplainer).

Consider a graph classification task $(\mathcal{G},\mathcal{Y},P_{G,Y})$ and
an $\ell$ layer GNN classifier $f(\cdot)$, for some $\ell\in\mathbb{N}$. Then,
any explanation $\Psi(\cdot)$ for $f(\cdot)$ produced using the PGExplainer is
an $\ell$-local explanation function.

Next, we argue that local explanation methods cannot be optimal in the
modified GIB sense for various classification tasks. Furthermore, we argue
that this issue may be mitigated by the addition of a hyperparameter $k$ as
described in subsequent sections in the context of the K-FactExplainer.

To provide concrete analytical arguments, we focus on a specific graph
classification task, where the class labels are binary, the input graph has
binary-valued edges, and the output label is a function of a set of indicator
motifs. To elaborate, we assume that the label to be predicted is
$Y=\max\\{E_{1},E_{2},\cdots,E_{s}\\}$, where $E_{i},i\in[s]$ are Bernoulli
variables, and if $E_{i}=1$, then $g_{i}\subseteq G$ for some fixed subgraphs
$g_{i},i\in[s]$. In the explainability literature, each of the subgraphs
$g_{i},i\in[s]$ is called a motif for label $Y=1$. Let us define
$G_{e}=\bigcup_{i\in[s]}g_{i}\mathbb{1}(E_{i}=1)$. So that $G_{e}$ is the
union of all the edges in the motifs that are present in $G$, and it is empty
if $Y=0$. Formally, the classification task under consideration is
characterized by the following joint distribution:

$\displaystyle P_{G,Y}(g,y)$ (4) $\displaystyle=$
$\displaystyle\sum_{e^{s},g_{0}}P_{E^{s}}(e^{s})P_{G_{0}}(g_{0})\mathbb{1}(y=\max_{i\in[s]}e_{i},g=g_{0}\cup
g_{e}),$

where $e^{s}\in\\{0,1\\}^{s}$,
$g_{e}\triangleq\bigcup_{i\in[s]}g_{i}\mathbb{1}(e_{i}=1)$, and $G_{0}$ is the
“irrelevant” edges in $G$ with respect to the label $Y$.

######  Remark 4.

The graph classification task on the MUTAG dataset is an instance of the above
classification scenario, where there are two motifs, corresponding to the
existence of $NH_{2}$ and $NO_{2}$ chemical groups, respectively
ying2018graph. Similarly, the BA-4Motif classification task considered in the
Appendix can be posed in the form of (4).

In graph classification tasks characterized by (4), if the label of $G$ is
one, then at least one of the motifs is present in $G$. Note that the reverse
may not be true as the motifs may randomly appear in the ‘irrelevant’ graph
$G_{0}$ due to its probabilistic nature. A natural choice for the explanation
function $\Psi(\cdot)$ of a classifier $f(\cdot)$ for this task is one which
outputs one of the motifs present in $G$ if $f(G)=1$. For instance, in the
MUTAG classification task, an explainer should output $NH_{2}$ or $NO_{2}$
subgraphs if the output label is equal to one. In the following, we argue
that, in classification tasks involving more than one motif local explanation
methods cannot produce the motifs accurately. Hence their output does not
align with the natural explanation outlined above and is not optimal in the
modified GIB sense. To make the result concrete, we further make the following
simplifying assumptions:
i) The graph $G_{0}$ is Erdös-Rényi with parameter $p\in(0,\frac{1}{2})$:

$P_{G_{0}}(g_{0})=p^{|g_{0}|}(1-p)^{\frac{n(n-1)}{2}-|g_{0}|}.$

ii) There exists $r,r^{\prime}>0$ such that the geodisc radius and geodisc
diameter of $g_{i}$ are less than or equal to $r$ and $r^{\prime}$,
respectively, for all $i\in[s]$.
iii) The geodisc distance between $g_{i}$ and $g_{j}$ is greater than $r$ for
all $i\neq j$.
iv) $E_{i},i\in[s]$ are jointly independent Bernoulli variables with parameter
$p_{i}$, where $P_{G_{0}}(g_{i})\leq p_{i}$.

######  Theorem 2 (Suboptimality of Local Explanation Functions).

Let $r,r^{\prime}\in\mathbb{N}$. For the graph classification task described
in (4), the following hold:
a) The optimal Bayes classification rule $f^{*}(g)$ is equal to
$\mathbb{1}(\exists i\in[s]:g_{i}\subseteq g)$.
b) For any r-local explanation function, there exists $\alpha^{\prime}>0$ such
that the explanation is suboptimal for $f^{*}$ in the modified GIB sense for
all $\alpha>\alpha^{\prime}$ and $\gamma$ equal to maximum number of edges of
$g_{i},i\in[s]$.
c) There exists an integer $k\leq s$, a parameter $\alpha^{\prime}>0$, a
collection of $r^{\prime}$-local explanation functions
$\Psi_{i}(\cdot),i\in[k]$, and an explanation function $\Psi^{*}$, such that
for all inputs $g$, we have
$\Psi(g)\in\\{\Psi_{1}(g),\Psi_{2}(g),\cdots,\Psi_{k}(g)\\}$ and $\Psi^{*}$ is
optimal in the modified GIB sense for all $\alpha>\alpha^{\prime}$ and
$\gamma$ equal to maximum number of edges of $g_{i},i\in[s]$.

The proof of Theorem 2 is provided in Appendix LABEL:App:th:2.

Figure 1:  Illustration of K-FactExplainer method. Starting from the left, the
node embeddings for graph G are produced using the original GNN. The edge
embeddings and graph embedding are produced by concatenating the node
embeddings. The MLP $\Psi_{0}$ assigns weight to the outputs of PGExplainer
MLPs $\Psi_{t},t\in[k]$. The resulting vector of edge probabilities
$\overline{\Omega}\triangleq(\sum_{t=1}^{k}p_{t}\omega^{t}_{i,j})_{i,j\in[n]}$
is used to produce the sampled explanation graph $G^{*}$. The explanation is
fed to the original GNN and the output label is compared with the original
prediction. The training proceeds by minimizing the cross-entropy term
$CE(Y^{\prime},\widehat{Y})$, where $\widehat{Y}$ is GNN prediction for the
original input graph $G$.

Theorem 2 can be interpreted as follows: for graph classification tasks with
more than one motif, although local explanation methods are not optimal in
general, one can “patch” together several local explanation methods
$\Psi_{1}(\cdot),\Psi_{2}(\cdot),\cdots,\Psi_{k}(\cdot)$ into an explanation
method $\Psi^{*}(\cdot)$, such that i) for any given input $g$, the output of
$\Psi^{*}(g)$ is equal to the output of one of the explanation functions
$\Psi_{1}(g),\Psi_{2}(g),\cdots,\Psi_{k}(g)$, and ii) $\Psi^{*}(\cdot)$ is
optimal in the modified GIB sense. This insight motivates the K-FactExplainer
method introduced in the following section.

######  Remark 5.

Theorem 2 implies that local explanation methods are not optimal in multi-
motif classification tasks. It should be noted that even in single-motif
tasks, post-hoc methods which rely on GNN generated node embeddings for
explanations would perform suboptimally. The reason is that the aggregator
function which is used to generate the embeddings is lossy (is not a one-to-
one function) and potentially loses information during the GNN aggregation
step. This can also be observed in the simulation results provided in the
sequel, where we apply our proposed K-FactExplainer method and show gains
compared to the state of the art in both multi-motif and single-motif
scenarios.

### K-FactExplainer Method and a Bootstrapping Algorithm

Motivated by the insights gained by the analytical results in the previous
section, we propose a new graph explanation method. An overview of the
proposed method is shown in Figure 1. To describe the method, let $f(\cdot)$
be the GNN which we wish to explain. Let $\mathbf{Z}_{i},i\in[n]$ denote the
node embedding for node $v_{i},i\in[n]$ produced by $f(\cdot)$. We construct
the edge embeddings
$\mathbf{Z}_{i,j}=(\mathbf{Z}_{i},\mathbf{Z}_{j}),i,j\in[n]$ and graph
embedding $\mathbf{Z}=(\mathbf{Z}_{i},i\in[n])$ by concatenating the edge
embeddings. Let $k\in\mathbb{N}$ be the upper-bound on the number of necessary
local explainers from Theorem 2. We consider $k$ multi-layer neural networks
(MLPs) denoted by $\Psi_{t},t\in[k]$. Each MLP $\Psi_{t}$ individually
operates in a similar fashion as the MLP used in the PGExplainer method. That
is, $\Psi_{t}$ operates on each edge embedding
$(\mathbf{Z}_{i},\mathbf{Z}_{j})$ individually, and outputs a Bernoulli
parameter $\omega_{i,j}^{t}\in[0,1]$. The parameter $\omega^{t}_{i,j}\in[0,1]$
can be viewed as the probability that the edge $(v_{i},v_{j})$ is in the
sampled explanation graph. Based on the insights provided by Theorem 2, we
wish to patch together the outputs of $\Psi_{t},t\in[k]$ to overcome the
locality issue in explaining GNNs in multi-motif classification tasks. This is
achieved by including the additional MLP $\Psi_{0}$ which takes the graph
embedding $\mathbf{Z}$ as input and outputs the probability distribution
$P_{K}$ on the alphabet $[k]$. At a high level, the MLP $\Psi_{0}$ provides a
global view of the input graph, whereas each of the $\Psi_{t},t\in[k]$ MLPs
provide a local perspective of the input graph. The outputs
$(\omega^{t}_{i,j})_{i,j\in[n]}$ of $\Psi_{t}$ are linearly combined with
weights associated with $P_{K}(t),t\in[k]$ and the resulting vector of
Bernoulli probabilities
$\overline{\Omega}=(\sum_{t=1}^{k}P_{K}(t)\omega^{t}_{i,j})_{i,j\in[n]}$ is
used to sample the edges of the input graph $G$ and produce the explanation
graph $G^{*}$. In the training phase, $G^{*}$ is fed to $f(\cdot)$ to produce
the prediction $Y^{\prime}$. Training is performed by minimizing the cross-
entropy term $CE(Y^{\prime},\widehat{Y})$, where $\widehat{Y}=f(G)$ is the
label prediction of the GNN given input $G$. The next proposition provides an
algorithm to bound the value of $k$, which determines the number of MLPs which
need to be trained.

######  Definition 4 (Minimal r-Cover).

Given a random graph $G=(\mathcal{V},\mathcal{E};\mathbf{Z},\mathbf{A})$ and
non-negative integer $r$, the collection
$\mathsf{P}=(\mathcal{P}_{1},\mathcal{P}_{2},\cdots,\mathcal{P}_{|\mathsf{P}|}),\mathcal{P}_{j}\subseteq\mathcal{V}$
is called an $r$-cover of $G$ if
i) Each partition element $\mathcal{P}_{j}$ has geodisc diameter at most equal
to $r$, and
ii) $P(\mathcal{V}^{*}\subseteq\cup_{j\in[|\mathsf{P}|]}\mathcal{P}_{j})=1$,
where $\mathcal{V}^{*}$ denotes the set of vertices of $G$ which are not
isolated.
The cover is called minimal if $r$ is the smallest integer for which an
r-cover of $G$ exists.

######  Proposition 2 (Bounding the Number of MLPs).

Consider the setup in Theorem 2. The parameter $k$, the number of
$r^{\prime}$-local explainers needed to achieve optimal GIB performance, can
be upper-bounded by $k^{*}$ if $G_{e}$ has a minimal $r^{\prime}$-cover with
$k^{*}$ elements.
Particularly, if the classifier to be explained, $f(\cdot)$, is a GNN with
$\ell$ layers, and $\ell$ is greater than or equal to the largest geodisc
diameter of the motifs $g_{i},i\in[s]$, then $k$ can be upper-bounded by $s$.

The proof of Proposition 2 is provided in Appendix LABEL:App:prop:2.

Proposition 2 provides a method to find an upper-bound on $k$; however, it
requires that the motifs be known beforehand, so that $G_{e}$ is known and the
size of its minimal cover can be computed. In practice, we do not know the
motifs before the start of the explanation process, since the explanation task
would be trivial otherwise. We provide an approximate solution, where instead
of finding the minimal cover for $G_{e}$, we use a bootstrapping method in
which we find the minimal cover for the explanation graphs produced by another
pre-trained explainer, e.g., a PGExplainer. To elaborate, It takes the GNN
model to be explained $f$, a set of training input graphs $\sG$, and a post-
hoc explainer $\Psi$ as input. In our simulations, we adopt PGExplainer as the
post-hoc explainer $\Psi$. Other explanation methods such as GNNExplainer
ying2019gnnexplainer can also be used in this step. For each graph $G\in\sG$,
we first apply the explainer $\Psi$ on $G$ to get the initial explanation
graph, whose nodes are listed in $\sV_{e}$ and edge mask matrix is denoted by
$\mM$. This is used as an estimate for $G_{e}$. To find its minimal cover, we
rank the nodes in $\sV_{e}$ based on their degrees and initialize
$k^{\prime}=0$. For each step, we select a node $v$ from $\sV_{e}$ and extract
its $k^{*}$-hop neighborhood graph, $G^{(l)}_{v}$. Then, we remove all nodes
in $G^{(l)}_{v}$ from $\sV_{e}$. After that, we add a count to $k^{\prime}$
and select the next node in $\sV_{e}$ until $|\sV_{e}|=0$. We iterate all
graphs in $\sG$ and report the maximum value of $k^{\prime}$ as $\hat{k}$, the
estimate of $k$. A detailed algorithm can be found in Appendix.

## Related Work

Graph neural networks (GNNs) have gained increasing attention in recent years
due to the need for analyzing graph data structures kipf2017semisupervised;
veličković2018graph; xu2018how; feng2020graph; satorras2021n;
bouritsas2022improving. In general, GNNs model messages from node
representations and then propagate messages with message-passing mechanisms to
update representations. GNNs have been successfully applied in various graph
mining tasks, such as node classification kipf2017semisupervised, link
prediction zhang2018link, and graph classification xu2018how. Despite their
popularity, akin to other deep learning methodologies, GNNs operate as black
box models, which means their functioning can be hard to comprehend, even when
the message passing techniques and parameters used are known. Furthermore,
GNNs stand apart from conventional deep neural networks that assume instances
are identically and independently distributed. GNNs instead integrate node
features with graph topology, which complicates the interpretability issue.

Recent studies have aimed to interpret GNN models and offer explanations for
their predictions ying2019gnnexplainer; luo2020parameterized; yuan2020xgnn;
yuan2022explainability; yuan2021explainability; lin2021generative;
wang2022gnninterpreter; miao2023interpretable; fang2023cooperative;
ma2022clear; zhang2023mixupexplainer. These methods generally fall into two
categories based on granularity: i) instance-level explanation
ying2019gnnexplainer; zhang2022gstarx, which explains predictions for each
instance by identifying significant substructures; and ii) model-level
explanation yuan2020xgnn; wang2022gnninterpreter; azzolin2023global, designed
to understand global decision rules incorporated by the target GNN. Among
these methods, Post-hoc explanation ones ying2019gnnexplainer;
luo2020parameterized; yuan2021explainability, which employ another model or
approach to explain a target GNN. Post-hoc explanations have the advantage of
being model-agnostic, meaning they can be applied to a variety of GNNs.
Therefore, our work focuses on post-hoc instance-level explanations
ying2019gnnexplainer, that is, identifying crucial instance-wise substructures
for each input to explain the prediction using a trained GNN model. A detailed
survey can be found in yuan2022explainability.

## Experimental Study

In this section, we empirically verify the effectiveness and efficiency of the
proposed K-FactExplainer by explaining both node and graph classifications. We
also conduct extensive studies to verify our theoretical claims. Due to the
space limitation, detailed experimental setups, full experimental results, and
extensive experiments are presented in Appendix.

#### Experimental Setup.

We compare our method with representative GIB-based explanation methods,
GNNExplainer ying2019gnnexplainer and PGExplainer luo2020parameterized,
classic explanation methods, GRAD ying2019gnnexplainer and ATT
veličković2018graph, and SOTA methods, RG-Explainer shan2021reinforcement and
DEGREE feng2022degree. We follow the routinely adopted framework to set up our
experiments ying2019gnnexplainer; luo2020parameterized. Six benchmark datasets
with ground truth explanations are used for evaluation, with BA-Shapes, BA-
Community, Tree-Circles, and Tree-Grid ying2019gnnexplainer for the node
classification task, and BA-2motifs luo2020parameterized and MUTAG
debnath1991structure for the graph classification task. For each dataset, we
train a graph neural network model to perform the node or graph classification
task. Each model is a three-layer GNN with a hidden size of 20, followed by an
MLP that maps these embeddings to the number of classes. After training the
model, we apply the K-FactExplainer and the baseline methods to generate
explanations for both node and graph instances. For each experiment, we
conduct $10$ times with random parameter initialization and report the average
results as well as the standard deviation. Detailed experimental setups are
put in the appendix.

### Quantitative Evaluation

#### Comparison to Baselines.

We adopted the well-established experimental framework ying2019gnnexplainer;
luo2020parameterized; shan2021reinforcement, where the explanation problem is
framed as a binary classification of edges. Within this setup, edges situated
inside motifs are regarded as positive edges, while all others are treated as
negative. The importance weights offered by the explanation methods are
treated as prediction scores. An effective explanation method, therefore,
would assign higher weights to edges located within the ground truth motifs as
opposed to those outside. To quantitatively evaluate the performance of these
methods, we employed AUC as our metric. The average AUC scores and the
associated standard deviations are reported in Table LABEL:tab:baselines. We
observe that with a manually selected value for $k$, K-FactExplainer
consistently outperforms GNNExplainer and PGExplainer and competes with high-
performing models like RGExplainer and DEGREE. The comparison demonstrates
that our K-FactExplainer considers locality, providing more accurate,
comprehensive explanations and mitigating common locality pitfalls seen in
other models.

### Model Analysis

#### Effectiveness of Bootstrapping Algorithm.

To directly show the effects of $k$ in K-FactExplainer . We change the value
of $k$ from 1 to 60 and show the resulting performance in Table
LABEL:tab:tuningK. We observe that, in general, a higher value of $k$ leads to
improved performance. The reason is that large $k$ in K-FactExplainer
mitigates the locality and lossy aggregation losses in parametric explainers
as discussed previously. We use an underline to indicate the upper-bound for
the value of $k$ suggested by the bootstrap algorithm in Section
K-FactExplainer Method and a Bootstrapping Algorithm. It should be noted that
this upper-bound is particularly relevant to multi-motif scenarios considered
in Theorem 2. Restricting to values of $k$ that are less than or equal to the
suggested upper-bound achieves the best performance in the multi-motif MUTAG
task, which is aligned with our theoretical analysis.

#### Effects of Lossy Aggregation.

To evaluate the effects of lossy aggregation, we consider the BA-Community and
Tree-Cycles in this part. As shown in Table LABEL:tab:tuningK, K-FactExplainer
significantly outperforms PGExplainer. The reason is that the K-FactExplainer
partially mitigates the aggregation loss in GNN explanation methods by
combining the outputs of multiple MLPs, hence combining multiple ‘weak’
explainers into a stronger one. In addition, we observe that the performances
of K-FactExplainer are positively related to $k$. Next, we increase the
dimensionality of hidden representation in the GNN model from 20 to 80. This
reduces the loss in aggregation as at each layer several low dimensional
vectors are mapped to high dimensional vectors. The explanation performances
are shown in Table LABEL:tab:lossy. For these two datasets, the performance
improves as $k$ is increased when the dimension is 20, due to the mitigation
of the aggregation loss, however, as expected, no improvement is observed when
increasing $k$ in explaining the GNN with dimension 80, since there is no
significant aggregation loss to mitigate in that case.

## Conclusion and Limitation

In this work, we theoretically investigate the trivial solution problem in the
popular objective function for explaining GNNs, which is largely overlooked by
the existing post-hoc instance-level explanation approaches. We point out that
the trivial solution is caused by the signal problem and propose a new GIB
objective with a theoretical guarantee. On top of that, we further investigate
the locality and lossy aggregation issues in existing parametric explainers
and show that most of them can be unified within the local explanation
Methods, which are weak at handling real-world graphs, where the mapping
between labels and motifs is one-to-many. We propose a new factorization-based
explanation model to address these issues. Comprehensive experiments are
conducted to verify the effectiveness of the proposed method.

The trivial solution of the GIB objective has not only effects on post-hoc
explanation methods but also self-explainable GNNs and model-level explanation
methods. The proposed modified version of GIB is specific to the post-hoc
setting, which is challenging to extend to other scenarios. In the future, we
will seek a more general form of GIB and investigate its usage in model-level
explanations.

## Acknowledgments

This project was partially supported by NSF grants IIS-2331908 and
CCF-2241057. The views and conclusions contained in this paper are those of
the authors and should not be interpreted as representing any funding
agencies.