# MAGE: Model-Level Graph Neural Networks Explanations via Motif-based Graph
Generation

Zhaoning Yu
Department of Computer Science
Iowa State University
Ames, IA 50010
<EMAIL_ADDRESS>&Hongyang Gao
Department of Computer Science
Iowa State University
Ames, IA 50010
<EMAIL_ADDRESS>
###### Abstract

Graph Neural Networks (GNNs) have shown remarkable success in molecular tasks,
yet their interpretability remains challenging. Traditional model-level
explanation methods like XGNN and GNNInterpreter often fail to identify valid
substructures like rings, leading to questionable interpretability. This
limitation stems from XGNN’s atom-by-atom approach and GNNInterpreter’s
reliance on average graph embeddings, which overlook the essential structural
elements crucial for molecules. To address these gaps, we introduce an
innovative Motif-bAsed GNN Explainer (MAGE) that uses motifs as fundamental
units for generating explanations. Our approach begins with extracting
potential motifs through a motif decomposition technique. Then, we utilize an
attention-based learning method to identify class-specific motifs. Finally, we
employ a motif-based graph generator for each class to create molecular graph
explanations based on these class-specific motifs. This novel method not only
incorporates critical substructures into the explanations but also guarantees
their validity, yielding results that are human-understandable. Our proposed
method’s effectiveness is demonstrated through quantitative and qualitative
assessments conducted on six real-world molecular datasets.

##  1 Introduction

Graph Neural Networks (GNNs) [18, 39, 12, 28, 33, 38] have become increasingly
popular tools for modeling data in the molecule field. As an effective method
for learning representations from molecule data, GNNs have attained state-of-
the-art results in tasks like molecular representation learning [11, 43, 10,
48], and molecule generation [6, 20]. Despite their growing popularity,
questions arise about the trustworthiness and decision-making processes of
GNNs.

Explaining GNNs has become a major area of interest in recent years and
existing methods can be broadly categorized into instance-level explanations
and model-level explanations. Instance-level explanations [42, 4, 26, 13, 34,
29, 22, 49, 30, 36, 47, 35, 44] aim to pinpoint specific nodes, edges, or
subgraphs crucial for a GNN model’s predictions on one data instance. Model-
level explanations [46, 37] seek to demystify the overall behavior of the GNN
model by identifying patterns that generally lead to certain predictions.
While instance-level methods offer detailed insights, they require extensive
analysis across numerous examples to be deemed reliable. Conversely, model-
level methods provide more high-level explanations that require less intensive
human oversight.

Model-level explanation methods have two main categories: concept-based
methods and generation-based methods. Concept-based explanation methods focus
on identifying higher-level concepts that significantly influence the model’s
predictions [3, 40]. Also, these methods establish rules to illustrate how
these concepts are interconnected, like using logical formulas [3].
Generation-based models try to learn a generative model that can generate
synthetic graphs that are optimized to maximize the behavior of the target GNN
[46, 37]. Instead of defining the relationships between important concepts
with formulas, generation-based models can generate novel graph structures
that are optimized for specific properties. This capability is particularly
crucial in the field of molecular learning.

Figure 1: Validity of explanations generated by XGNN and GNNInterpreter on
Mutagenicity dataset

Despite the notable benefits of generation-based model-level explanation
methods for GNNs, they have received relatively low attention. Presently, the
available generation-based model-level explainers for GNNs are somewhat
limited in their application, especially in molecular graphs. For example,
XGNN [46] explains models by building an explanation atom-by-atom and sets a
maximum degree for each atom to maintain the explanation’s validity. On the
other hand, GNNInterpreter [37] adopts a more flexible approach by learning a
generative explanation graph distribution. However, it ensures the validity of
explanations by maximizing the similarity between the explanation graph
embedding and the average embedding of all graphs, which is not particularly
effective for molecular graphs. These existing methods often fail to consider
the unique aspects of molecular structures adequately. This oversight makes it
challenging for these methods to include crucial substructures in their
explanation graphs. It compromises the validity and reliability of the model-
level explanations they provide for molecular graphs. In Figure 1, the
explanations produced by both XGNN and GNNInterpreter exhibit low validity,
making them ineffective for further analysis. Consequently, there’s a clear
need for more advanced and specialized model-level explanation methods that
can effectively handle the unique characteristics of molecular graphs and
provide meaningful insights into how GNNs interpret and process molecular
data.

This paper introduces a motif-based approach for model-level explanations,
MAGE, specifically tailored for GNNs in molecular representation learning
tasks. The method begins by identifying all possible motifs from the molecular
data. Following this, our method focuses on pinpointing particularly
significant motifs for a specific class. This is achieved through a novel
attention-based motif learning process, which aids in selecting these key
motifs. Once these important motifs are identified, we employ a motif-based
graph generator trained to produce explanations based on these motifs. Our
experimental results show that our method reliably produces explanations
featuring complex molecular structures, achieving complete validity across
various molecular datasets. Furthermore, both quantitative and qualitative
evaluations demonstrate that the explanation molecules created by our method
are more representative and human-understandable than those generated by
baseline methods.

##  2 Preliminary

Notations. A molecular dataset can be depicted as
$\mathcal{G}=\\{G_{1},G_{2},...,G_{i},...,G_{n}\\}$, where each molecular
graph within this set is denoted by $G_{i}=(\textbf{V},\textbf{E})$. The label
of each graph will be assigned by $l_{i}\in L=\\{l_{1},l_{2},...\\}$ In this
representation, V constitutes a set of atoms, each treated as a node, while E
comprises the bonds, represented as edges connecting these nodes. The
structural information of each graph $G_{i}$ is encoded in several matrices.
The adjacency matrix $\textbf{A}\in\\{0,1\\}^{N\times N}$ represents the
connections between atoms, where a ‘1’ indicates the presence of a bond
between a pair of atoms, a ‘0’ signifies no bond, and $N$ represents the total
number of atoms in the graph. Additionally, an atom feature matrix
$\textbf{X}\in\mathbb{R}^{N\times D}$ captures the features of each atom, with
$D$ being the number of features characterizing each atom. Similarly, a bond
feature matrix $\textbf{Z}\in\mathbb{R}^{N\times D_{b}}$ is used to describe
the attributes of the bonds, where $D_{b}$ denotes the number of features
describing each bond.

Graph Neural Networks. Graph Neural Networks (GNNs) leverage adjacency, node
feature, and edge feature matrices to learn node features. Despite the
existence of various GNN variants like Graph Convolutional Networks (GCNs),
Graph Attention Networks (GATs), and Graph Isomorphism Networks (GINs), they
generally follow a message-passing mechanism. In this process, each GNN layer
aggregates information from a node’s neighbors to refine its representation.
For a given hidden layer $i$, the message passing operation can be formulated
as $h_{i}=f(h_{i-1},A,Z)$, where $h_{0}=X$. Here, $h_{i}\in\mathbb{R}^{N\times
D}$ is the node representation output from layer $i$, and $D$ is the dimension
of the output features. The function $f$ involves computing messages based on
the previous layer’s node embeddings ($h_{i-1}$), aggregating these messages
from neighboring nodes, and updating the hidden representation $h_{i}$ for
each node using the aggregated messages.

Motif. A motif is essentially a recurring subgraph within a graph, closely
associated with the graph’s property, which has been thoroughly researched
across various domains, including biochemistry, ecology, neurobiology, and
engineering [24, 31, 1, 2] and has been demonstrated to be of significant
importance. GSN [7] introduces motif information into node features to improve
the learning of GNNs. HMGNN [43] generates a heterogeneous motif graph to
enhance the molecular representation learning. MotifExplainer [44] applies
motifs to learn an instance-level explanation for GNNs.

Figure 2: An illustration of the proposed MAGE framework. Given a dataset, a
motif extraction algorithm is initially employed to identify all potential
motifs. Each motif’s feature encoding is derived from the output encoding
produced by the target model, which uses the motif graph as its input. A
single-layer attention operator is employed to learn the optimal motif
combination, maximizing the likelihood that the target classifier will
classify both the reconstructed and original molecular encodings identically.
To get a score matrix, the method performs a dot product between the attention
coefficient matrix and the prediction probability matrix. This score matrix is
then normalized using a degree matrix. Finally, motifs whose corresponding
scores exceed a specific threshold are selected.

##  3 Motif-based Model-Level GNN Explainer

This work introduces a Motif-bAsed GNN Explainer (MAGE), a novel approach for
model-level GNN explanations. This method uses motifs as fundamental elements
for interpreting the overarching behavior of a trained GNN for molecular graph
classification at the model level. Instead of generating a graph at the atomic
level, using motifs allows the generator to assemble graphs from these
predefined blocks. This method prevents the creation of potentially invalid
intermediate substructures and speeds up the generation process. It achieves
this by reducing the number of configurations the generator must consider,
focusing solely on the arrangement of motifs rather than the specific
placement of each atom and bond.

Given a dataset, denoted as $\mathcal{G}$ with $N$ molecules and $C$ classes,
our objective is to generate model-level explanations for a target GNN, which
comprises a feature extractor $\phi(\cdot)$ and a classifier $f(\cdot)$.
$\phi(\cdot)$ takes a molecular graph or subgraph as input and outputs its
feature representation. $f(\cdot)$ utilizes this representation to predict the
classification of a molecule.

MAGE begins with identifying all potential motifs within $\mathcal{M}$.
Following this, an attention-driven motif learning phase is employed to
identify the most significant motifs for each class using $\phi(\cdot)$ and
$f(\cdot)$. Finally, a graph generator uses the identified motifs to explain
each class.

###  3.1 Motif Extraction

There are mainly three methods for motif extraction. It’s important to note
that these motif extraction methods can be integrated into our MAGE
explanation method, demonstrating its versatility.

1) Ring and bonded pairs (R&B). Methods [15, 43, 7] in this category recognize
simple rings and bonded pairs as motifs. 2) Molecule decomposition. In this
category, methods recognize motifs through molecule breakdown. These methods
initially establish a catalog of target bonds, either through domain-specific
knowledge, such as the “breakable bonds” used by RECAP [21, 50] and BRICS [8,
48, 14], or through hand-crafted rules, like “bridge bonds” [16]. The
algorithms remove these target bonds from the molecules and use the consequent
molecular fragments as motifs. 3) Molecule tokenization. Certain methods [9,
19] leverage the string representations of molecules, such as SMILES, and
directly apply the WordPiece algorithm from the NLP domain. The resulting
strings within the constructed vocabulary are regarded as motifs. 4) Data-
driven method. MotifPiece [45] statistically identifies underlying structural
or functional patterns specific to a given molecular data.

###  3.2 Class-wise Motif Identification

With extracted significant motifs from the previous section, this section
introduces an attention-based motif identification approach for each
classification class.

Stage 1: molecule-motif relation score calculation.
Given the absence of a direct linkage between classification categories and
motifs, we propose bridging them through molecules. To this end, we employ an
attention operator to learn motif-molecule relation scores using the trained
feature extractor $\phi(\cdot)$ and a classifier $f(\cdot)$.

For a given molecule graph $G_{i}$ and its associated motif set $M_{i}$, we
use an attention operator to identify a combination of motifs that can
accurately reconstruct the representations of the molecule graph. The learned
attention scores between $G_{i}$ and motifs in $M_{i}$ are interpreted as
their relation scores. The initial step involves obtaining feature encoding
for the molecule and motif graphs. This is done by feeding a molecule graph or
motif graph into $\phi(\cdot)$, and the output encoding serves as the molecule
or motif:

$\displaystyle\boldsymbol{h}_{G_{i}}=\phi(G_{i}),\boldsymbol{h}_{m_{i}}=\phi(m_{i}),\text{
for all $m_{i}$}\in M_{i}.$

Next, an attention operator is used to aggregate the motif encoding using
$\boldsymbol{h}_{G_{i}}$ as query and $\boldsymbol{h}_{m_{i}}$s as keys and
values. The resulting encoding, denoted as $\boldsymbol{h}^{\prime}_{G_{i}}$,
is the aggregated molecular encoding by combining motifs in $M_{i}$.

$\displaystyle
e_{G_{i}m_{i}}=g(\boldsymbol{W}\boldsymbol{h}_{G_{i}},\boldsymbol{W}\boldsymbol{h}_{m_{i}}),\alpha_{G_{i}m_{i}}=\frac{\exp(e_{G_{i}m_{i}})}{\sum_{m_{i}\in
M_{i}}\exp(e_{G_{i}m_{i}})},\boldsymbol{h}^{\prime}_{G_{i}}=\sum_{m_{i}\in
M_{i}}\alpha_{G_{i}m_{i}}\cdot\boldsymbol{h}_{m_{i}},$

where $g(\cdot)$ is an attention operator, and $\boldsymbol{W}$ is weight
matrix. The target classifier $f(\cdot)$ then uses aggregated encoding to
generate predictions. The training process is designed to minimize the cross-
entropy loss between the predicted probabilities of the aggregated molecular
encoding and those of the original molecular encoding:

$\displaystyle\mathcal{L}=\sum_{i}\mathcal{L}(f(\boldsymbol{h}_{G_{i}}),f(\boldsymbol{h}^{\prime}_{G_{i}})).$
(1)

The attention operator is trained to identify important motifs to represent
the molecule. This leads to the molecule-motif relation score
$\boldsymbol{\alpha}_{G_{i}m_{i}}$ and the probabilities associated with label
predictions $\boldsymbol{\hat{y}}=f(\boldsymbol{h}^{\prime}_{G_{i}})$.

Stage 2: class-motif relation score calculation.
We repeat the process of Stage 1 to compute the molecule-motif scores for each
molecular graph. After that, we create a molecule-motif score matrix
$\boldsymbol{S}^{mm}\in\mathbb{R}^{V\times N}$ and a molecule-class
probability matrix $\boldsymbol{P}\in\mathbb{R}^{N\times C}$. Here,
${S}^{mm}_{pk}$ represents the molecule-motif relation score between molecule
$k$ and motif $p$. If the motif $i$ does not appear in the molecule $j$, we
set ${S}^{mm}_{ij}=0$. Element ${P}_{kr}$ denotes the probability that
molecule $k$ is associated with label $r$.

Subsequently, we perform a matrix multiplication between $\boldsymbol{S}^{mm}$
and $\boldsymbol{P}$ to get class-motif relation score matrix
$\boldsymbol{S}^{cm}$:

$\displaystyle\boldsymbol{S}^{cm}=\boldsymbol{S}^{mm}\boldsymbol{P},{S}^{cm}_{pr}=\sum_{k=1}^{N}{S}^{mm}_{pk}{P}_{kr}$

which represents the relationship between motif $p$ and class $r$. Then, we
normalize $\boldsymbol{S}^{cm}$ by dividing each column, corresponding to a
motif, by the number of molecules it appears.

Stage 3: class-wise motif filtering.
We filter motifs for each class using class-wise motif scores from the
previous stage. The motif set for the class $C_{r}$ is

$M_{C_{r}}=\\{m_{i}|\boldsymbol{S}^{cm}_{ir}>\theta,1\leq i\leq V\\}$ (2)

where $\theta$ is a hyper-parameter to control the size of the important motif
vocabulary. An illustration of our class-wise motif identification is provided
in Figure 2.

###  3.3 Class-wise Motif-based Graph Generation

Figure 3: Illustration of class-wise motif-based graph generation.

Section 3.2 identifies motifs of high relevance for each class. Building on
this, our methodology employs a motif-based generative model to construct
model-level explanations tailored to each class. The motif-based molecular
generation method can be divided into tree-constrained [15, 16] and non-
constrained methods [41]. In our approach, we employ a tree-constrained method
as a generator. However, our approach can easily adapt to non-constrained
methods. The graph generation process is illustrated in Figure 3.

####  3.3.1 Tree Decomposition

Given a target class $r$, a set of important motifs $M_{C_{r}}$ associated
with the class $r$, and the set of molecules $\mathcal{G}_{r}$ whose predicted
class by trained GNN is $r$. For each molecular graph
$G_{i}\in\mathcal{G}_{r}$, we first identify the motifs in $M_{C_{r}}$ from
$G_{i}$: $M^{r}_{i}=M_{i}\cap M_{C_{r}}$. Subsequently, we pinpoint every edge
in $G_{i}$ that does not belong to any motif in $M^{r}_{i}$. We treat each
motif in $M^{r}_{i}$ and each non-motif edge as a cluster node. Then, we
construct a cluster graph by connecting clusters with intersections. Finally,
a spanning tree $\mathcal{T}$ is selected from this cluster graph, defined as
the motif junction tree for $G_{i}$.

####  3.3.2 Graph Encoder

We encode the latent representation of $G=(\textbf{A},\textbf{X})$ by the
target GNN feature extractor $\phi(\cdot)$:
$\boldsymbol{h}_{G}=\phi(\textbf{A},\textbf{X})$. The mean
$\boldsymbol{\mu}_{G}$ and log variance $\log\boldsymbol{\sigma}_{G}$ of the
variational posterior approximation are computed from $\boldsymbol{h}_{G}$
with two separate affine layers. $\boldsymbol{z}_{G}$ is sampled from a
Gaussian distribution
$\mathcal{N}(\boldsymbol{\mu}_{G},\boldsymbol{\sigma}_{G})$. In the
variational posterior approximation, we use two different affine layers to
compute the mean, represented as $\boldsymbol{\mu}_{G}$, and the log variance,
denoted as $\log\boldsymbol{\sigma}_{G}$, from $\boldsymbol{h}_{G}$. Then, we
sample $\boldsymbol{z}_{G}$ from a Gaussian distribution
$\mathcal{N}(\boldsymbol{\mu}_{G},\boldsymbol{\sigma}_{G})$.

####  3.3.3 Tree Encoder

We employ a graph neural network to encode the motif tree
$\mathcal{T}=(\boldsymbol{A}_{\mathcal{T}},\boldsymbol{X}_{\mathcal{T}})$,
where every node $i$’s feature $x_{i}$ is initially encoded by feeding its
corresponding motif graph to $\phi(\cdot)$. Formally, the node embedding and
tree embedding are updated as follows:

$\displaystyle\boldsymbol{H}_{\mathcal{T}}=\text{GNN}(\boldsymbol{A}_{\mathcal{T}},\boldsymbol{X}_{\mathcal{T}}),\boldsymbol{h}_{\mathcal{T}}=\text{AGG}(\boldsymbol{H}_{\mathcal{T}}).$

where $\text{GNN}(\cdot)$ is a graph neural network, and $\text{AGG}(\cdot)$
is an aggregation function. $\boldsymbol{z}_{\mathcal{T}}$ is sampled
similarly as in the graph encoder.

####  3.3.4 Tree Decoder

A tree decoder is used to decode a junction tree $\mathcal{T}$ from a tree
encoding $\boldsymbol{z}_{\mathcal{T}}$. The decoder builds the tree in a top-
down approach, where nodes are created sequentially, one after the other. The
node under consideration first obtains its embedding by inputting the existing
tree into the tree encoder, and the resulting output is then used as the node
embedding. The node embedding is utilized for two predictions: determining
whether the node has a child and identifying the child’s label if a child
exists. Formally, for node $i$

$\displaystyle\boldsymbol{H}^{\prime}=\text{GNN}(\boldsymbol{A}^{\prime},\boldsymbol{X}^{\prime}),\boldsymbol{p}_{i}=\text{PRED}(\text{COMB}(\boldsymbol{z}_{\mathcal{T}},\boldsymbol{H}^{\prime}_{i})),\boldsymbol{q}_{i}=\text{PRED}^{l}(\text{COMB}^{l}(\boldsymbol{z}_{\mathcal{T}},\boldsymbol{H}^{\prime}_{i}))$

where $\boldsymbol{A}^{\prime}$ and $\boldsymbol{X}^{\prime}$ are the existing
tree’s adjacent matrix and node features, respectively. $\text{COMB}(\cdot)$
and $\text{COMB}^{l}(\cdot)$ are combination functions, and
$\text{PRED}(\cdot)$ and $\text{PRED}^{l}(\cdot)$ are predictors. When the
current node does not have a new child, the decoder will go to the next node
in the existing tree.

####  3.3.5 Graph Decoder

The final step is reproducing the molecular graph from the predicted junction
tree $\mathcal{T}$. Let $\mathcal{G}(\mathcal{T})$ be a set of graphs whose
junction tree is $\mathcal{T}$. The decoder aims to find $\hat{G}$ as

$\displaystyle\hat{G}=\arg\max_{G^{\prime}\in\mathcal{G(\mathcal{T})}}f^{a}(G^{\prime}).$

In our approach, we aim to ensure that the reproduced molecule maintains the
characteristics of the target GNN. So we design the score function as
$f^{a}(G_{i})=f(\phi(G_{i}))[r]$, where $r$ is the target label.

####  3.3.6 Loss Function

The loss function for graph generation comprises two components: the
reconstruction loss and the property loss. The reconstruction loss ensures
that the generated graph matches the distribution of the original dataset. The
property loss ensures that the behavior of the generated graph aligns with the
target GNN.

The reconstruction loss can be formally defined as below:

$\mathcal{L_{R}}=\sum\mathcal{L}_{T}+\sum\mathcal{L}_{L}$ (3)

, where $\mathcal{L}_{T}$ corresponds to predicting whether a node has a
child, while $\mathcal{L}_{L}$ represents the loss associated with predicting
the label of the newly added child. We perform teacher forcing for the
reconstruction loss to make the information get the correct history at each
step.

The property loss is like below:

$\mathcal{L_{P}}=\sum\text{MSE}(\boldsymbol{h}_{G},\boldsymbol{h}_{\mathcal{T}})+\sum\mathcal{L}(f(\boldsymbol{h}_{\mathcal{T}}),r)$
(4)

, where $\boldsymbol{h}_{\mathcal{T}}$ is the embedding of the generated tree,
$\boldsymbol{h}_{G}$ is the corresponding graph embedding, $f(\cdot)$ is the
target classifier, and $r$ is the target label. The final loss function is

$\mathcal{L}=\mathcal{L_{R}}+\mathcal{L_{P}}$ (5)

##  4 Experiment

We conduct qualitative and quantitative experiments on six real-world datasets
to evaluate the effectiveness of our proposed methods.

###  4.1 Dataset and Experimental Setup

We evaluate the proposed methods using molecule classification tasks on six
real-world datasets: Mutagenicity, PTC_MR, PTC_MM, PTC_FM, AIDS, and NCI-H23.
The details of six datasets and experimental settings are represented in
Appendix A and B.

Table 1: Validity results on six real-world datasets. OOM refers to out of memory. Datasets | Models |  Label 0 |  Label 1 |  Average
---|---|---|---|---
Mutagenicity | XGNN |  0.34 |  0.25 |  0.295
GNNInterpreter |  0.11 |  0.21 |  0.16
Ours |  1.00 |  1.00 |  1.00
PTC_MR | XGNN |  0.70 |  0.21 |  0.45
GNNInterpreter |  0.10 |  0.05 |  0.07
Ours |  1.00 |  1.00 |  1.00
PTC_MM | XGNN |  0.49 |  0.56 |  0.51
GNNInterpreter |  0.15 |  0.20 |  0.17
Ours |  1.00 |  1.00 |  1.00
PTC_FM | XGNN |  0.48 |  0.37 |  0.42
GNNInterpreter |  0.13 |  0.08 |  0.10
Ours |  1.00 |  1.00 |  1.00
AIDS | XGNN |  0.92 |  0.71 |  0.81
GNNInterpreter |  0.09 |  0.08 |  0.08
Ours |  1.00 |  1.00 |  1.00
NCI-H23 | XGNN |  OOM |  OOM |  OOM
GNNInterpreter |  0.59 |  0.62 |  0.60
Ours |  1.00 |  1.00 |  1.00
Table 2: Quantitative results for different explanation methods. We highlight the average class probability (higher is better) for six datasets and the training time for each method on each dataset. The best performances on each dataset are shown in bold. OOM refers to out of memory. Datasets | Models |  Label 0 |  Label 1 | Average
---|---|---|---|---
Mutagenicity | XGNN |  0.8992 $\pm$ 0.0835 |  0.9831 $\pm$ 0.0514 | 0.9411
GNNInterpreter |  0.8542 $\pm$ 0.3198 |  0.9938 $\pm$ 0.0191 | 0.9240
Variant |  0.9897 $\pm$ 0.0754 |  0.9888 $\pm$ 0.0302 | 0.9892
Ours |  0.9977 $\pm$ 0.0032 |  0.9941 $\pm$ 0.0240 | 0.9959
PTC_MR | XGNN |  0.9906 $\pm$ 0.0718 |  0.9698 $\pm$ 0.0417 | 0.9802
GNNInterpreter |  0.9067 $\pm$ 0.1728 |  0.9697 $\pm$ 0.0211 | 0.9382
Variant |  0.9902 $\pm$ 0.0480 |  0.9641 $\pm$ 0.1163 | 0.9771
Ours |  0.9961 $\pm$ 0.0375 |  0.9918 $\pm$ 0.0621 | 0.9939
PTC_MM | XGNN |  0.9899 $\pm$ 0.0994 |  0.9266 $\pm$ 0.1059 | 0.9582
GNNInterpreter |  0.9601 $\pm$ 0.0638 |  0.9541 $\pm$ 0.0207 | 0.9571
Variant |  0.9784 $\pm$ 0.0475 |  0.9693 $\pm$ 0.0279 | 0.9738
Ours |  0.9914 $\pm$ 0.0342 |  0.9833 $\pm$ 0.0019 | 0.9873
PTC_FM | XGNN |  0.9967 $\pm$ 0.0309 |  0.9380 $\pm$ 0.0991 | 0.9673
GNNInterpreter |  0.9945 $\pm$ 0.0147 |  0.9460 $\pm$ 0.0295 | 0.9702
Variant |  0.9882 $\pm$ 0.0024 |  0.9790 $\pm$ 0.0024 | 0.9836
Ours |  0.9979 $\pm$ 0.0024 |  0.9890 $\pm$ 0.0024 | 0.9934
AIDS | XGNN |  0.9259 $\pm$ 0.1861 |  0.9977 $\pm$ 0.0225 | 0.9618
GNNInterpreter |  0.4600 $\pm$ 0.4983 |  0.9973 $\pm$ 0.0116 | 0.7286
Variant |  0.9802 $\pm$ 0.1112 |  0.9939 $\pm$ 0.0564 | 0.9870
Ours |  0.9883 $\pm$ 0.0663 |  0.9903 $\pm$ 0.0539 | 0.9893
NCI-H23 | XGNN |  OOM |  OOM | OOM
GNNInterpreter |  0.9883 $\pm$ 0.0711 |  0.9997 $\pm$ 0.0015 | 0.9940
Variant |  0.9874 $\pm$ 0.0685 |  0.9863 $\pm$ 0.01069 | 0.9868
Ours |  0.9936 $\pm$ 0.0329 |  0.9934 $\pm$ 0.0422 | 0.9935

Baselines. We compare our MAGE model with two state-of-the-art baselines: XGNN
and GNNInterpreter. Noted that all methods are tested using official
implementation and compared in a fair setting. We extract motifs by
identifying “bridge bonds”. We build a variant that uses the same motif
extraction and graph generation processes but without our attention-based
motif identification step. This variant is to demonstrate the effectiveness of
our class-wise motif identification process. The details of this variant will
be discussed in section 4.2.

Evaluation metrics. Our quantitative evaluation uses two distinct metrics to
assess performance: Validity and Average Probability.

Validity. This metric is defined as the proportion of chemically valid
molecules out of the total number of generated molecules [5].

$\displaystyle\text{Validity}=\frac{\\#\,\text{valid
molecules}}{\\#\,\text{generated molecules}}$

This metric serves as a critical indicator of the practical applicability of
our method, ensuring that the generated molecules not only align with the
intended class but also adhere to fundamental chemical validity criteria.

Average Probability. Following the GNNInterpreter [37], this metric calculates
the average class probability and the standard deviation of these
probabilities across 1000 explanation graphs for each class within all six
datasets.

$\displaystyle\text{Average Probability}=\frac{\sum\text{class
probability}}{\\#\,\text{generated molecules}}.$

This approach provides a comprehensive measure of the consistency and
reliability of the explanation graphs in representing different classes.

Together, these two metrics offer a robust framework for evaluating the
effectiveness of our approach from both the accuracy and applicability
perspectives. Considering XGNN’s limitation in generating explanation graphs
with edge features, we assign the default bond type from the RDKit library as
the default edge feature for explanations produced by XGNN. We also report the
training time and sampling time of different models in appendix C.

###  4.2 Quantitative Results

Table 1 details the Validity results for various models across six datasets. A
notable observation from these results is that our method consistently
produces valid molecular explanation graphs for both classes in all cases.
This reliability stems from our method’s use of valid substructures as
foundational elements, effectively overcoming the limitation seen in atom-by-
atom generation methods, which often compel the model to create chemically
invalid intermediate structures.

Additionally, the data reveals that XGNN exhibits better validity than
GNNInterpreter. The reason for this difference lies in the design of the
algorithms: XGNN incorporates a manual constraint on the maximum atom degree,
which aids in maintaining chemical validity. In contrast, GNNInterpreter is to
align the embedding of its generated explanations with the average embedding
of the dataset, which does not inherently ensure chemical validity and leads
to more invalid generated molecules.

These findings from the validity experiment highlight a principle: maximizing
the inductive biases inherent in the molecular graph structure is important.
It enables models to achieve higher levels of validity in the outputs,
demonstrating that careful consideration of the structural characteristics of
molecules can significantly enhance the performance and reliability of these
models.

Table 2 shows the average probability of four models on six real-world
datasets. Our method outperforms the baseline methods in six out of eight
experiments with an average improvement of $1.21\%$, clearly highlighting its
effectiveness. Additionally, our method consistently delivers strong results
across both classes in each dataset. This contrasts XGNN and GNNInterpreter,
which tend to excel in one class but fall short in the other. We attribute
this success of our method to its unique strategy of generating explanations
in a motif-by-motif way, effectively reducing the influence of extraneous or
noise atoms in the data.

Furthermore, we conducted a comparative analysis between our method and a
variant model. This variant model operates by first identifying all potential
motifs within the dataset. Once these motifs are extracted, it assesses them
by putting each motif as an input to the target model. The evaluation of each
motif is based on the output probability associated with a particular class,
which is assigned as the motif’s score. Following this scoring process, the
method ranks all motifs in order of their scores. Only motifs whose scores
exceed 0.9 are chosen to refine the selection.

The outcomes of our study indicate that our method outperforms the variant
model across all classes, achieving an average enhancement of 2.11%. This
significant improvement underscores the efficiency of our attention-based
motif learning module. Unlike the variant model, which solely focuses on the
individual motifs without considering their functional roles within the
molecules, our method learns and understands the interplay between motifs and
molecules. This enables our approach to effectively identify and select motifs
relevant to the specific molecular context while simultaneously filtering out
motifs that do not contribute meaningfully, often called noise motifs.

Table 3: The qualitative results for Mutagenicity dataset. The first row of the table displays the explanation graphs corresponding to the Nonmutagen label, while the second row presents the explanation graphs for the Mutagen label. The final column in the table provides examples of actual graphs. The different colors in the nodes represent different values in the node feature Class | Generated Model-Level Explanation Graphs for Mutagenicity Dataset
---|---
XGNN |  GNNInterpreter |  Ours |  Example
Nonmutagen |  |  |  |
Mutagen |  |  |  |

###  4.3 Qualitative Results

Table 3 presents the qualitative assessment of three different methods applied
to the two classes of the Mutagenicity dataset. The table also includes actual
graph examples from the dataset for reference. Our analysis reveals that our
method can consistently produce human-understandable and valid explanation
graphs, which XGNN and GNNInterpreter seem to lack. More qualitative results
can be found in Appendix E.

We observed a trend in GNNInterpreter to produce explanations that are
disconnected. This is likely due to its approach of aligning explanation
embeddings with the dataset’s average embedding, resulting in a focus on node
features rather than structural details. XGNN, on the other hand, tends to
create explanations with invalid ring structures. Although XGNN imposes
constraints on the degree of each atom, its atom-by-atom generation approach
makes it challenging to form valid ring structures. Our method can generate
explanations with meaningful substructures like rings.

This inability of XGNN and GNNInterpreter to effectively identify complex
molecular structures may contribute to their lower validity in explanation
generation. Our method, in contrast, successfully navigates these
complexities, offering more meaningful, accurate and structurally coherent
explanations. This difference highlights the importance of considering both
node features and molecular structures in the generation of explanation
graphs, a balance that our approach seems to strike effectively.

##  5 Related Work

Model-level explanation methods in the field are currently under-researched,
with only a few studies addressing this issue. These methods can be divided
into two categories. The first category is concept-based methods. GCExplainer
[23] introduced the incorporation of concepts into GNN explanations, using the
k-Means clustering algorithm on GNN embeddings to identify clusters, each
representing a concept. PAGE [32] provides clustering on the embedding space
to discover propotypes as explanations. GLGExplainer [3] adopts prototype
learning to identify data prototypes and then uses these in an E-LEN model to
create a Boolean formula that replicates the GNN’s behavior. GCNeuron [40], on
the other hand, employs human-defined rule templates in natural language and
considers graphs with certain masked nodes as concepts, using compositional
concepts with the highest scores for global explanations. The second category
comprises generation-based methods. XGNN [46] uses deep reinforcement learning
to generate explanation graphs node by node. GNNInterpreter [37],
alternatively, learns a probabilistic generative graph model that identifies
the most discriminative graph patterns for explanations.

##  6 Conclusion

This work proposes a novel motif-based model-level explanation method for
Graph Neural Networks, specifically applied to molecular datasets. Initially,
the method employs a motif extraction technique to identify all potential
motifs. Following this, a one-layer attention mechanism is used to evaluate
the relevance of each motif, filtering out those that are not pertinent.
Finally, a graph generator is trained to produce explanations based on the
chosen motifs. Compared to two baseline methods, XGNN and GNNInterpreter, our
proposed method offers explanations that are more human-understandable,
accurate, and structurally consistent.

## References

  * [1] Uri Alon.  Network motifs: theory and experimental approaches.  Nature Reviews Genetics, 8(6):450–461, 2007.
  * [2] Uri Alon.  An introduction to systems biology: design principles of biological circuits.  CRC press, 2019.
  * [3] Steve Azzolin, Antonio Longa, Pietro Barbiero, Pietro Liò, and Andrea Passerini.  Global explainability of gnns via logic combination of learned concepts.  arXiv preprint arXiv:2210.07147, 2022.
  * [4] Federico Baldassarre and Hossein Azizpour.  Explainability techniques for graph convolutional networks.  arXiv preprint arXiv:1905.13686, 2019.
  * [5] Camille Bilodeau, Wengong Jin, Tommi Jaakkola, Regina Barzilay, and Klavs F Jensen.  Generative models for molecular discovery: Recent advances and challenges.  Wiley Interdisciplinary Reviews: Computational Molecular Science, 12(5):e1608, 2022.
  * [6] Pietro Bongini, Monica Bianchini, and Franco Scarselli.  Molecular generative graph neural networks for drug discovery.  Neurocomputing, 450:242–252, 2021.
  * [7] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein.  Improving graph neural network expressivity via subgraph isomorphism counting.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):657–668, 2022.
  * [8] Jörg Degen, Christof Wegscheid-Gerlach, Andrea Zaliani, and Matthias Rarey.  On the art of compiling and using’drug-like’chemical fragment spaces.  ChemMedChem: Chemistry Enabling Drug Discovery, 3(10):1503–1507, 2008.
  * [9] Lei Fang, Junren Li, Ming Zhao, Li Tan, and Jian-Guang Lou.  Single-step retrosynthesis prediction by leveraging commonly preserved substructures.  Nature Communications, 14(1):2446, 2023.
  * [10] Xiaomin Fang, Lihang Liu, Jieqiong Lei, Donglong He, Shanzhuo Zhang, Jingbo Zhou, Fan Wang, Hua Wu, and Haifeng Wang.  Geometry-enhanced molecular representation learning for property prediction.  Nature Machine Intelligence, 4(2):127–134, 2022.
  * [11] Hongyang Gao and Shuiwang Ji.  Graph u-nets.  In international conference on machine learning, pages 2083–2092. PMLR, 2019.
  * [12] Hongyang Gao, Zhengyang Wang, and Shuiwang Ji.  Large-scale learnable graph convolutional networks.  In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1416–1424, 2018.
  * [13] Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, Dawei Yin, and Yi Chang.  Graphlime: Local interpretable model explanations for graph neural networks.  arXiv preprint arXiv:2001.06216, 2020.
  * [14] Yinghui Jiang, Shuting Jin, Xurui Jin, Xianglu Xiao, Wenfan Wu, Xiangrong Liu, Qiang Zhang, Xiangxiang Zeng, Guang Yang, and Zhangming Niu.  Pharmacophoric-constrained heterogeneous graph transformer model for molecular property prediction.  Communications Chemistry, 6(1):60, 2023.
  * [15] Wengong Jin, Regina Barzilay, and Tommi Jaakkola.  Junction tree variational autoencoder for molecular graph generation.  In International conference on machine learning, pages 2323–2332. PMLR, 2018.
  * [16] Wengong Jin, Regina Barzilay, and Tommi Jaakkola.  Hierarchical generation of molecular graphs using structural motifs.  In International conference on machine learning, pages 4839–4848. PMLR, 2020.
  * [17] Jeroen Kazius, Ross McGuire, and Roberta Bursi.  Derivation and validation of toxicophores for mutagenicity prediction.  Journal of medicinal chemistry, 48(1):312–320, 2005.
  * [18] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  arXiv preprint arXiv:1609.02907, 2016.
  * [19] Christopher Kuenneth and Rampi Ramprasad.  polybert: a chemical language model to enable fully machine-driven ultrafast polymer informatics.  Nature Communications, 14(1):4099, 2023.
  * [20] Xin Lai, Peisong Yang, Kunfeng Wang, Qingyuan Yang, and Duli Yu.  Mgrnn: Structure generation of molecules based on graph recurrent neural networks.  Molecular informatics, 40(10):2100091, 2021.
  * [21] Xiao Qing Lewell, Duncan B Judd, Stephen P Watson, and Michael M Hann.  Recap retrosynthetic combinatorial analysis procedure: a powerful new technique for identifying privileged molecular fragments with useful applications in combinatorial chemistry.  Journal of chemical information and computer sciences, 38(3):511–522, 1998.
  * [22] Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang.  Parameterized explainer for graph neural network.  arXiv preprint arXiv:2011.04573, 2020.
  * [23] Lucie Charlotte Magister, Dmitry Kazhdan, Vikash Singh, and Pietro Liò.  Gcexplainer: Human-in-the-loop concept-based explanations for graph neural networks.  arXiv preprint arXiv:2107.11889, 2021.
  * [24] Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon.  Network motifs: simple building blocks of complex networks.  Science, 298(5594):824–827, 2002.
  * [25] Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann.  Tudataset: A collection of benchmark datasets for learning with graphs.  arXiv preprint arXiv:2007.08663, 2020.
  * [26] Phillip E Pope, Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann.  Explainability methods for graph convolutional neural networks.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10772–10781, 2019.
  * [27] Kaspar Riesen and Horst Bunke.  Iam graph database repository for graph based pattern recognition and machine learning.  In Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), pages 287–297. Springer, 2008.
  * [28] Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang.  Self-supervised graph transformer on large-scale molecular data.  Advances in Neural Information Processing Systems, 33:12559–12571, 2020.
  * [29] Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima, Kristof T Schütt, Klaus-Robert Müller, and Grégoire Montavon.  Higher-order explanations of graph neural networks via relevant walks.  arXiv preprint arXiv:2006.03589, 2020.
  * [30] Caihua Shan, Yifei Shen, Yao Zhang, Xiang Li, and Dongsheng Li.  Reinforcement learning enhanced explainer for graph neural networks.  Advances in Neural Information Processing Systems, 34:22523–22533, 2021.
  * [31] Shai S Shen-Orr, Ron Milo, Shmoolik Mangan, and Uri Alon.  Network motifs in the transcriptional regulation network of escherichia coli.  Nature genetics, 31(1):64–68, 2002.
  * [32] Yong-Min Shin, Sun-Woo Kim, and Won-Yong Shin.  Page: Prototype-based model-level explanations for graph neural networks.  arXiv preprint arXiv:2210.17159, 2022.
  * [33] Ruoxi Sun, Hanjun Dai, and Adams Wei Yu.  Does gnn pretraining help molecular representation?  Advances in Neural Information Processing Systems, 35:12096–12109, 2022.
  * [34] Minh N Vu and My T Thai.  Pgm-explainer: Probabilistic graphical model explanations for graph neural networks.  arXiv preprint arXiv:2010.05788, 2020.
  * [35] Xiang Wang, Yingxin Wu, An Zhang, Fuli Feng, Xiangnan He, and Tat-Seng Chua.  Reinforced causal explainer for graph neural networks.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
  * [36] Xiang Wang, Yingxin Wu, An Zhang, Xiangnan He, and Tat-Seng Chua.  Towards multi-grained explainability for graph neural networks.  Advances in Neural Information Processing Systems, 34, 2021.
  * [37] Xiaoqi Wang and Han-Wei Shen.  Gnninterpreter: A probabilistic generative model-level explanation for graph neural networks.  arXiv preprint arXiv:2209.07924, 2022.
  * [38] Yuyang Wang, Zijie Li, and Amir Barati Farimani.  Graph neural networks for molecules.  In Machine Learning in Molecular Sciences, pages 21–66. Springer, 2023.
  * [39] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  arXiv preprint arXiv:1810.00826, 2018.
  * [40] Han Xuanyuan, Pietro Barbiero, Dobrik Georgiev, Lucie Charlotte Magister, and Pietro Liò.  Global concept-based interpretability for graph neural networks via neuron analysis.  In Proceedings of the AAAI Conference on Artificial Intelligence, pages 10675–10683, 2023.
  * [41] Soojung Yang, Doyeong Hwang, Seul Lee, Seongok Ryu, and Sung Ju Hwang.  Hit and lead discovery with explorative rl and fragment-based molecule generation.  Advances in Neural Information Processing Systems, 34:7924–7936, 2021.
  * [42] Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec.  Gnnexplainer: Generating explanations for graph neural networks.  Advances in neural information processing systems, 32:9240, 2019.
  * [43] Zhaoning Yu and Hongyang Gao.  Molecular representation learning via heterogeneous motif graph neural networks.  In International Conference on Machine Learning, pages 25581–25594. PMLR, 2022.
  * [44] Zhaoning Yu and Hongyang Gao.  Motifexplainer: a motif-based graph neural network explainer.  arXiv preprint arXiv:2202.00519, 2022.
  * [45] Zhaoning Yu and Hongyang Gao.  Motifpiece: A data-driven approach for effective motif extraction and molecular representation learning.  arXiv preprint arXiv:2312.15387, 2023.
  * [46] Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji.  Xgnn: Towards model-level explanations of graph neural networks.  In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 430–438, 2020.
  * [47] Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji.  On explainability of graph neural networks via subgraph explorations.  In International conference on machine learning, pages 12241–12252. PMLR, 2021.
  * [48] Xuan Zang, Xianbing Zhao, and Buzhou Tang.  Hierarchical molecular graph self-supervised learning for property prediction.  Communications Chemistry, 6(1):34, 2023.
  * [49] Yue Zhang, David Defazio, and Arti Ramesh.  Relex: A model-agnostic relational model explainer.  In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, pages 1042–1049, 2021.
  * [50] Zaixi Zhang, Qi Liu, Hao Wang, Chengqiang Lu, and Chee-Kong Lee.  Motif-based graph self-supervised learning for molecular property prediction.  Advances in Neural Information Processing Systems, 34:15870–15882, 2021.

## NeurIPS Paper Checklist

  1. 1.

Claims

  2. Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope?

  3. Answer: [Yes]

  4. Justification: Our abstract and introduction accurately introduce the contributions and the experimental results of our paper.

  5. Guidelines:

     * •

The answer NA means that the abstract and introduction do not include the
claims made in the paper.

     * •

The abstract and/or introduction should clearly state the claims made,
including the contributions made in the paper and important assumptions and
limitations. A No or NA answer to this question will not be perceived well by
the reviewers.

     * •

The claims made should match theoretical and experimental results, and reflect
how much the results can be expected to generalize to other settings.

     * •

It is fine to include aspirational goals as motivation as long as it is clear
that these goals are not attained by the paper.

  6. 2.

Limitations

  7. Question: Does the paper discuss the limitations of the work performed by the authors?

  8. Answer: [N/A]

  9. Justification: Our paper does not have any strong assumptions. We also compare our efficiency with other baselines and show that we have a better efficiency. Our method does not have privacy and fairness issues.

  10. Guidelines:

     * •

The answer NA means that the paper has no limitation while the answer No means
that the paper has limitations, but those are not discussed in the paper.

     * •

The authors are encouraged to create a separate "Limitations" section in their
paper.

     * •

The paper should point out any strong assumptions and how robust the results
are to violations of these assumptions (e.g., independence assumptions,
noiseless settings, model well-specification, asymptotic approximations only
holding locally). The authors should reflect on how these assumptions might be
violated in practice and what the implications would be.

     * •

The authors should reflect on the scope of the claims made, e.g., if the
approach was only tested on a few datasets or with a few runs. In general,
empirical results often depend on implicit assumptions, which should be
articulated.

     * •

The authors should reflect on the factors that influence the performance of
the approach. For example, a facial recognition algorithm may perform poorly
when image resolution is low or images are taken in low lighting. Or a speech-
to-text system might not be used reliably to provide closed captions for
online lectures because it fails to handle technical jargon.

     * •

The authors should discuss the computational efficiency of the proposed
algorithms and how they scale with dataset size.

     * •

If applicable, the authors should discuss possible limitations of their
approach to address problems of privacy and fairness.

     * •

While the authors might fear that complete honesty about limitations might be
used by reviewers as grounds for rejection, a worse outcome might be that
reviewers discover limitations that aren’t acknowledged in the paper. The
authors should use their best judgment and recognize that individual actions
in favor of transparency play an important role in developing norms that
preserve the integrity of the community. Reviewers will be specifically
instructed to not penalize honesty concerning limitations.

  11. 3.

Theory Assumptions and Proofs

  12. Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?

  13. Answer: [N/A]

  14. Justification: Our paper does not include theoretical results.

  15. Guidelines:

     * •

The answer NA means that the paper does not include theoretical results.

     * •

All the theorems, formulas, and proofs in the paper should be numbered and
cross-referenced.

     * •

All assumptions should be clearly stated or referenced in the statement of any
theorems.

     * •

The proofs can either appear in the main paper or the supplemental material,
but if they appear in the supplemental material, the authors are encouraged to
provide a short proof sketch to provide intuition.

     * •

Inversely, any informal proof provided in the core of the paper should be
complemented by formal proofs provided in appendix or supplemental material.

     * •

Theorems and Lemmas that the proof relies upon should be properly referenced.

  16. 4.

Experimental Result Reproducibility

  17. Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?

  18. Answer: [Yes]

  19. Justification: We provide detailed experimental settings in the appendix.

  20. Guidelines:

     * •

The answer NA means that the paper does not include experiments.

     * •

If the paper includes experiments, a No answer to this question will not be
perceived well by the reviewers: Making the paper reproducible is important,
regardless of whether the code and data are provided or not.

     * •

If the contribution is a dataset and/or model, the authors should describe the
steps taken to make their results reproducible or verifiable.

     * •

Depending on the contribution, reproducibility can be accomplished in various
ways. For example, if the contribution is a novel architecture, describing the
architecture fully might suffice, or if the contribution is a specific model
and empirical evaluation, it may be necessary to either make it possible for
others to replicate the model with the same dataset, or provide access to the
model. In general. releasing code and data is often one good way to accomplish
this, but reproducibility can also be provided via detailed instructions for
how to replicate the results, access to a hosted model (e.g., in the case of a
large language model), releasing of a model checkpoint, or other means that
are appropriate to the research performed.

     * •

While NeurIPS does not require releasing code, the conference does require all
submissions to provide some reasonable avenue for reproducibility, which may
depend on the nature of the contribution. For example

       1. (a)

If the contribution is primarily a new algorithm, the paper should make it
clear how to reproduce that algorithm.

       2. (b)

If the contribution is primarily a new model architecture, the paper should
describe the architecture clearly and fully.

       3. (c)

If the contribution is a new model (e.g., a large language model), then there
should either be a way to access this model for reproducing the results or a
way to reproduce the model (e.g., with an open-source dataset or instructions
for how to construct the dataset).

       4. (d)

We recognize that reproducibility may be tricky in some cases, in which case
authors are welcome to describe the particular way they provide for
reproducibility. In the case of closed-source models, it may be that access to
the model is limited in some way (e.g., to registered users), but it should be
possible for other researchers to have some path to reproducing or verifying
the results.

  21. 5.

Open access to data and code

  22. Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?

  23. Answer: [Yes]

  24. Justification: We include our codes in supplemental material.

  25. Guidelines:

     * •

The answer NA means that paper does not include experiments requiring code.

     * •

Please see the NeurIPS code and data submission guidelines
(https://nips.cc/public/guides/CodeSubmissionPolicy) for more details.

     * •

While we encourage the release of code and data, we understand that this might
not be possible, so “No” is an acceptable answer. Papers cannot be rejected
simply for not including code, unless this is central to the contribution
(e.g., for a new open-source benchmark).

     * •

The instructions should contain the exact command and environment needed to
run to reproduce the results. See the NeurIPS code and data submission
guidelines (https://nips.cc/public/guides/CodeSubmissionPolicy) for more
details.

     * •

The authors should provide instructions on data access and preparation,
including how to access the raw data, preprocessed data, intermediate data,
and generated data, etc.

     * •

The authors should provide scripts to reproduce all experimental results for
the new proposed method and baselines. If only a subset of experiments are
reproducible, they should state which ones are omitted from the script and
why.

     * •

At submission time, to preserve anonymity, the authors should release
anonymized versions (if applicable).

     * •

Providing as much information as possible in supplemental material (appended
to the paper) is recommended, but including URLs to data and code is
permitted.

  26. 6.

Experimental Setting/Details

  27. Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?

  28. Answer: [Yes]

  29. Justification: We provide a detailed experimental setting in the appendix.

  30. Guidelines:

     * •

The answer NA means that the paper does not include experiments.

     * •

The experimental setting should be presented in the core of the paper to a
level of detail that is necessary to appreciate the results and make sense of
them.

     * •

The full details can be provided either with the code, in appendix, or as
supplemental material.

  31. 7.

Experiment Statistical Significance

  32. Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?

  33. Answer: [Yes]

  34. Justification: We report standard deviation for each single experiment.

  35. Guidelines:

     * •

The answer NA means that the paper does not include experiments.

     * •

The authors should answer "Yes" if the results are accompanied by error bars,
confidence intervals, or statistical significance tests, at least for the
experiments that support the main claims of the paper.

     * •

The factors of variability that the error bars are capturing should be clearly
stated (for example, train/test split, initialization, random drawing of some
parameter, or overall run with given experimental conditions).

     * •

The method for calculating the error bars should be explained (closed form
formula, call to a library function, bootstrap, etc.)

     * •

The assumptions made should be given (e.g., Normally distributed errors).

     * •

It should be clear whether the error bar is the standard deviation or the
standard error of the mean.

     * •

It is OK to report 1-sigma error bars, but one should state it. The authors
should preferably report a 2-sigma error bar than state that they have a 96%
CI, if the hypothesis of Normality of errors is not verified.

     * •

For asymmetric distributions, the authors should be careful not to show in
tables or figures symmetric error bars that would yield results that are out
of range (e.g. negative error rates).

     * •

If error bars are reported in tables or plots, The authors should explain in
the text how they were calculated and reference the corresponding figures or
tables in the text.

  36. 8.

Experiments Compute Resources

  37. Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?

  38. Answer: [Yes]

  39. Justification: We report the training and sampling time in appendix. We also report the hardware configuration of our experiment in appendix.

  40. Guidelines:

     * •

The answer NA means that the paper does not include experiments.

     * •

The paper should indicate the type of compute workers CPU or GPU, internal
cluster, or cloud provider, including relevant memory and storage.

     * •

The paper should provide the amount of compute required for each of the
individual experimental runs as well as estimate the total compute.

     * •

The paper should disclose whether the full research project required more
compute than the experiments reported in the paper (e.g., preliminary or
failed experiments that didn’t make it into the paper).

  41. 9.

Code Of Ethics

  42. Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?

  43. Answer: [Yes]

  44. Justification: We have checked the NeurIPS code of ethics.

  45. Guidelines:

     * •

The answer NA means that the authors have not reviewed the NeurIPS Code of
Ethics.

     * •

If the authors answer No, they should explain the special circumstances that
require a deviation from the Code of Ethics.

     * •

The authors should make sure to preserve anonymity (e.g., if there is a
special consideration due to laws or regulations in their jurisdiction).

  46. 10.

Broader Impacts

  47. Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?

  48. Answer: [N/A]

  49. Justification: Our method is an explanation method on graph dataset, it will not directly have any societal impact.

  50. Guidelines:

     * •

The answer NA means that there is no societal impact of the work performed.

     * •

If the authors answer NA or No, they should explain why their work has no
societal impact or why the paper does not address societal impact.

     * •

Examples of negative societal impacts include potential malicious or
unintended uses (e.g., disinformation, generating fake profiles,
surveillance), fairness considerations (e.g., deployment of technologies that
could make decisions that unfairly impact specific groups), privacy
considerations, and security considerations.

     * •

The conference expects that many papers will be foundational research and not
tied to particular applications, let alone deployments. However, if there is a
direct path to any negative applications, the authors should point it out. For
example, it is legitimate to point out that an improvement in the quality of
generative models could be used to generate deepfakes for disinformation. On
the other hand, it is not needed to point out that a generic algorithm for
optimizing neural networks could enable people to train models that generate
Deepfakes faster.

     * •

The authors should consider possible harms that could arise when the
technology is being used as intended and functioning correctly, harms that
could arise when the technology is being used as intended but gives incorrect
results, and harms following from (intentional or unintentional) misuse of the
technology.

     * •

If there are negative societal impacts, the authors could also discuss
possible mitigation strategies (e.g., gated release of models, providing
defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms
to monitor how a system learns from feedback over time, improving the
efficiency and accessibility of ML).

  51. 11.

Safeguards

  52. Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?

  53. Answer: [N/A]

  54. Justification: Our proposed method is an explanation method which has no such risks.

  55. Guidelines:

     * •

The answer NA means that the paper poses no such risks.

     * •

Released models that have a high risk for misuse or dual-use should be
released with necessary safeguards to allow for controlled use of the model,
for example by requiring that users adhere to usage guidelines or restrictions
to access the model or implementing safety filters.

     * •

Datasets that have been scraped from the Internet could pose safety risks. The
authors should describe how they avoided releasing unsafe images.

     * •

We recognize that providing effective safeguards is challenging, and many
papers do not require this, but we encourage authors to take this into account
and make a best faith effort.

  56. 12.

Licenses for existing assets

  57. Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?

  58. Answer: [Yes]

  59. Justification: We mentioned related works in the reference.

  60. Guidelines:

     * •

The answer NA means that the paper does not use existing assets.

     * •

The authors should cite the original paper that produced the code package or
dataset.

     * •

The authors should state which version of the asset is used and, if possible,
include a URL.

     * •

The name of the license (e.g., CC-BY 4.0) should be included for each asset.

     * •

For scraped data from a particular source (e.g., website), the copyright and
terms of service of that source should be provided.

     * •

If assets are released, the license, copyright information, and terms of use
in the package should be provided. For popular datasets,
paperswithcode.com/datasets has curated licenses for some datasets. Their
licensing guide can help determine the license of a dataset.

     * •

For existing datasets that are re-packaged, both the original license and the
license of the derived asset (if it has changed) should be provided.

     * •

If this information is not available online, the authors are encouraged to
reach out to the asset’s creators.

  61. 13.

New Assets

  62. Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?

  63. Answer: [Yes]

  64. Justification: We detailed explained the datasets and baseline models in our paper. We also submit our code as an anonymized zip file.

  65. Guidelines:

     * •

The answer NA means that the paper does not release new assets.

     * •

Researchers should communicate the details of the dataset/code/model as part
of their submissions via structured templates. This includes details about
training, license, limitations, etc.

     * •

The paper should discuss whether and how consent was obtained from people
whose asset is used.

     * •

At submission time, remember to anonymize your assets (if applicable). You can
either create an anonymized URL or include an anonymized zip file.

  66. 14.

Crowdsourcing and Research with Human Subjects

  67. Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?

  68. Answer: [N/A]

  69. Justification: our paper does not involve crowdsourcing nor research with human subjects.

  70. Guidelines:

     * •

The answer NA means that the paper does not involve crowdsourcing nor research
with human subjects.

     * •

Including this information in the supplemental material is fine, but if the
main contribution of the paper involves human subjects, then as much detail as
possible should be included in the main paper.

     * •

According to the NeurIPS Code of Ethics, workers involved in data collection,
curation, or other labor should be paid at least the minimum wage in the
country of the data collector.

  71. 15.

Institutional Review Board (IRB) Approvals or Equivalent for Research with
Human Subjects

  72. Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?

  73. Answer: [N/A]

  74. Justification: our paper does not involve crowdsourcing nor research with human subjects.

  75. Guidelines:

     * •

The answer NA means that the paper does not involve crowdsourcing nor research
with human subjects.

     * •

Depending on the country in which research is conducted, IRB approval (or
equivalent) may be required for any human subjects research. If you obtained
IRB approval, you should clearly state this in the paper.

     * •

We recognize that the procedures for this may vary significantly between
institutions and locations, and we expect authors to adhere to the NeurIPS
Code of Ethics and the guidelines for their institution.

     * •

For initial submissions, do not include any information that would break
anonymity (if applicable), such as the institution conducting the review.

##  Appendix A Details of Datasets

Table 4: Statistics and properties of four real-world molecule datasets. |  Mutag |  PTC_MR |  PTC_MM |  PTC_FM |  AIDS |  NCI-H23
---|---|---|---|---|---|---
# Nodes (avg) |  30.32 |  14.29 |  14.32 |  14.48 |  15.69 |  26.07
# Edges (avg) |  30.77 |  14.69 |  13.97 |  14.11 |  16.20 |  28.10
# Graphs |  4337 |  344 |  336 |  349 |  2000 |  40353
# Classes |  2 |  2 |  2 |  2 |  2 |  2

The statistics and properties of four datasets are summarized in Table 4.

Mutagenicity [17, 27] is a chemical compound dataset containing 4,337 molecule
graphs. Each of these graphs is classified into either mutagen or non-mutagen
categories, signifying their mutagenic impact on the Gram-negative bacterium
Salmonella typhimurium.

PTC_MR, PTC_MM, and PTC_FM [25] are three collections of chemical compounds,
each respectively documenting carcinogenic effects on male rats (MR), male
mice (MM), and female mice (FM).

AIDS [25] comprises 2,000 graphs that represent molecular compounds, all of
which are derived from the AIDS Antiviral Screen Database of Active Compounds.

NCI-H23 [25] is a collection of 40353 molecular compounds to evaluate the
efficacy against lung cancer cells.

##  Appendix B Experimental settings

By following baseline approaches, our experiments adopt a simple GCN model and
focus on explanation results. For the target GNN, we use a 3-layer GCN as a
feature extractor and a 2-layer MLP as a classifier on all datasets. The model
is pre-trained and achieves reasonable performances on all datasets. Following
the [39], the hidden dimension is selected from $\\{16,64\\}$. We employ mean-
pooling as the readout function and ReLU as the activation function. We use
Adam optimizer for training. The target model is trained for 100 epochs, and
the learning rate is set to 0.01. The CPU in our setup is an AMD Ryzen
Threadripper 2990WX, accompanied by 256 GB of memory, and the GPU is an RTX
4090.

##  Appendix C Study of training and inference time

Table 5: Training and inference time for different explanation methods. XGNN and GNNInterpreter do not have training time because they only have sampling process. Datasets | Models |  Training Time |  Sampling Time
---|---|---|---
Mutagenicity | XGNN |  — |  54s
GNNInterpreter |  — |  29s
Variant |  528s |  0.0015s
Ours |  539s |  0.0029s
PTC_MR | XGNN |  — |  62s
GNNInterpreter |  — |  27s
Variant |  338s |  0.0005s
Ours |  368s |  0.0006s
PTC_MM | XGNN |  — |  46s
GNNInterpreter |  — |  17s
Variant |  303s |  0.0023s
Ours |  367s |  0.0002s
PTC_FM | XGNN |  — |  47s
GNNInterpreter |  — |  12s
Variant |  307s |  0.0027s
Ours |  386s |  0.0018s
AIDS | XGNN |  — |  19s
GNNInterpreter |  — |  32s
Variant |  468s |  0.0065s
Ours |  513s |  0.0076s
NCI-H23 | XGNN |  — |  OOM
GNNInterpreter |  — |  21s
Variant |  10189s |  0.0115s
Ours |  13657s |  0.0126s

We also present a detailed comparison of the training and sampling times
between our method and other baseline approaches in table 5. Here, sampling
time is the average time to generate a single explanation. Compared to the two
baselines, a key distinction of our method lies in its requirement for an
initial training phase for the explanation graph generator. This phase confers
a significant benefit: the ability to efficiently sample explanations. Our
experimental data underscores this advantage. Following the completion of the
training phase for the explanation generator, our method demonstrated the
capacity to generate a large number of explanations rapidly. Specifically, it
could sample 1000 explanations in a matter of seconds. This starkly contrasts
other baseline methods, which required at least 3.3 hours to produce the same
number of examples. This dramatic reduction in sampling time not only
highlights the efficiency of our method but also suggests its practical
applicability in scenarios where quick generation of explanations is crucial.
Due to the space limit, we put the study of hyper-parameter $\theta$ in
Appendix D.

##  Appendix D Study of Hyperparameter

Table 6: Study of Hyperparameter $\theta$ on Mutagen class of Mutagenicity dataset |  $\mathbf{\theta=0.01}$ |  $\mathbf{\theta=0.05}$ |  $\mathbf{\theta=0.10}$ |  $\mathbf{\theta=0.20}$
---|---|---|---|---
# Selected Motifs |  1591 |  1328 |  1206 |  1073
Average Probability |  0.9621 $\pm$ 0.1151 |  0.9850 $\pm$ 0.0784 |  0.9977 $\pm$ 0.0032 |  0.9753 $\pm$ 0.0981

Table 6 shows the study of hyperparameter $\theta$, we found that as $\theta$
increases, the number of motifs selected for the Mutagen class decreases. The
average probability rises until $\theta$ reaches 0.10, where peak performance
is observed, after which it starts to decline. This trend occurs because when
$\theta$ is low, some irrelevant motifs are included in the explanations. As
$\theta$ increases, these ’noise’ motifs are filtered out, enhancing
performance. However, if $\theta$ is set too high, the resulting small number
of selected motifs is insufficient for forming a comprehensive explanation.

##  Appendix E More Qualitative Results

Table 7: More qualitative results for Nonmutagen class on Mutagenicity dataset. Class |  XGNN |  GNNInterpreter |  Ours |  Example
---|---|---|---|---
Nonmutagen |  |  |  |
|  |  |
|  |  |
|  |  |
|  |  |
|  |  |
|  |  |
|  |  |
|  |  |
|  |  |
Table 8: More qualitative results for Mutagen class on Mutagenicity dataset. Class |  XGNN |  GNNInterpreter |  Ours |  Example
---|---|---|---|---
Mutagen |  |  |  |
|  |  |
|  |  |
|  |  |
|  |  |
|  |  |
|  |  |
|  |  |
|  |  |
|  |  |