MotifExplainer: a Motif-based Graph Neural Network Explainer
Authors: Zhaoning Yu
Hongyang Gao
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph Neural Networks
Explainer
Motif

Abstract: We consider the explanation problem of Graph Neural Networks (GNNs). Most existing GNN explanation methods identify the most important edges or nodes but fail to consider substructures, which are more important for graph data. One method considering subgraphs tries to search all possible subgraphs and identifies the most significant ones. However, the subgraphs identified may not be recurrent or statistically important for interpretation. This work proposes a novel method, named MotifExplainer, to explain GNNs by identifying important motifs, which are recurrent and statistically significant patterns in graphs. Our proposed motif-based methods can provide better human-understandable explanations than methods based on nodes, edges, and regular subgraphs. Given an instance graph and a pre-trained GNN model, our method first extracts motifs in the graph using domain-specific motif extraction rules. Then, a motif embedding is encoded by feeding motifs into the pre-trained GNN. Finally, we employ an attention-based method to identify the most influential motifs as explanations for the prediction results. The empirical studies on both synthetic and real-world datasets demonstrate the effectiveness of our method.

Under review as a conference paper at ICLR 2023
MOTIFEXPLAINER: A MOTIF-BASED GRAPH NEURAL NETWORK EXPLAINER
Anonymous authors Paper under double-blind review
ABSTRACT
We consider the explanation problem of Graph Neural Networks (GNNs). Most existing GNN explanation methods identify the most important edges or nodes but fail to consider substructures, which are more important for graph data. One method considering subgraphs tries to search all possible subgraphs and iden- tifies the most significant ones. However, the subgraphs identified may not be recurrent or statistically important for interpretation. This work proposes a novel method, named MotifExplainer, to explain GNNs by identifying important motifs, which are recurrent and statistically significant patterns in graphs. Our proposed motif-based methods can provide better human- unduuannnnndttadaaallee explanations than methods based on nodes, edges, and regular subgraphs. Given an instance graph and pre-trained GNN model, our method first extracts motifs in the graph using Nomain-speciffi motif extraction rules. Then, motif embedding is encoded by feeding motifs into the pre-trained GNN. Finally, we employ an attention- based method to identify the most influential motifs as explanations for the prediction re- sults. The empirical studies on both synthetic and real- world datasets demonstrate the effectiveness of our method.
INTRODUCTION
Graph neural networks (GNNs) have shown capability in solving various challenging tasks in graph fields, such as node classification, graph classification, and link prediction. Although many GNNs models (Kipf & Welling, 2016 Gao et al. 2018 Xu et al. 2018 Gao & Ji, 2019 Liu et al. 2020) have achieved state-of-the--e performances
various tasks, they are still considered black boxes and lack sufficient knowledge to explain them. Inadequate interpretation of GNN decisions severely hinders the applicability of these models in critical decision-making contexts where both predictive performance and interpretability are critical. A good explainer allows to debate GNN decisions and shows where algorithmic decisions may be biased or discriminated against. In addition, we can apply precise explanations to other scientific research like fragment generation. A fragment library is a key component in drug discovery, and accurate explanations may help its generation.
Several methods have been proposed to explain GNNs, divided into instance-level explainers and model-level explainers. Most existing instance-level explainers such as GNNExplainer (Ying et al. 2019) PGExplainer (Luo al., 2020). Gem (Lin et al.. 202I). and ReFine (Wang al.) 2021 produce an explanation to every graph instance. These methods explain pre-trained GNNs by iden- tifying important edges nodes but fail to consider substructures, which are more important for graph data. The only method that considers subgraphs is SubgraphX (Yuan et al. 2021). which searches all possible subgraphs and identifies the most significant one. However, the subgraphs identified may not be recurrent or statistically important, which raises an issue the application of the produced explanations. For example, fragment-based drug discovery (FBDD) et al., 2004) has been proven to be powerful for developing potent smlll-molecule compounds. FBDD is based on fragment libraries, containing fragments or motif's identified as relevant to the target property by domain experts. Using motif-based GNN explainer, fragments or motifs that are ready to be used when generating diug-like lead compounds in FBDD.
directly identify relevant
In addition, searching and scoring all possible subgraphs is time-consuming and inefficient. We claim that using motifs, recurrent and statistically important subgraphs, to explain GNNs can provide more intuitive explanation than methods based on nodes, edges, or subgraphs.

---

Under review as a conference paper at ICLR 2023
This work proposes novel GNN explanation method named MotifExplainer, which can identify significant motifs to explain an instance graph. In particular, our method first extracts motifs from a given graph using domain-specifee motif extraction rules based on domain knowledge. Then, motif emheddings of extracted motifs are generated by feeding motifs into the target GNN model. After that, attention model is employed select relevant motifs based on attention weights. These explaeee selected motif's are used as an explanation for the target GNN model on the instance graph. To our
knowledge, the proposed method represents the first attempt to apply the attention mechanism to explain the GNN from the motif-level perspective. We evaluate our method using both qualitative and quantitative experiments. The experiments show that our MotifExplainer can generate bet- ter explanation than previous GNN explainers. In addition, the efficiency studies demonstrate the efficiency advantage of our methods in terms of much shorter training and inference time.
2 PROBLEM FORMULATION
This section formulates the problem of explanations on graph neural networks. Let = (V, [G1, G2, ...: G..... Gv denotes graph where of the graph and E is the edge set. G2 is associated with d-dimensional set of node features X = =x1,, I2, .... T,,..., .... )n where x; E R is the feature vector of node 1/- Without loss of generality, consider the problem of explaining a node classification task, we associate each node it of a graph G with a label yi. where yi E Y {1, Lc) and e is the number of classes. For a graph classification task, each graph G; is assigned a corresponding label.
{Vl, u2, V/ Un. } is the node set
GNN-based downstream classification task. For
2.1 BACKGROUND ON GRAPH NEURAL NETWORKS
Most Graph Neural Networks (GNNs) follow neighborhood aggregation learning scheme. In layer f, GNNs contain three steps. First, a GNN first calculates the messages that will be transferred between every node pair. A message for a node pair (vi, (z), Uj) can be represented by function 0() : bby (ar: _ eij), where eij is the edge feature vector, 2F az-1 and x f-1 the node features of uy and at the previous layer, respectively. Second, for each node n4 GNN aggregates all messages from its neighborhood N; using an aggregation function x0-) B & (1b [y E N.)). Finally, the GNN combine the aggregated message B with node wy's feature representation from previous layer x!- -f-1_ and use non-linear activation function to obtain the representation for node is at layer 1 σf {x .B.). Formally, a L-th GNN layer can be represented by
of = (x . (10 (z) aay "ejil,e)) 1 AG)))
2.2 GRAPH NEURAL NETWORK EXPLANATIONS
In GNN explanation task, given a pre-trained GNN model, which can be represented by (.) and its corresponding dataset D. The task is to obtain an explanation model (-) that can provide fast and accurate explanation for the given GNN model. Most existing GNN explanation approaches can be categorized into two branches: instance-level methods and model-level methods. Instance-level methods can provide an explanation for each input graph. while model-level methods are input-independene and analyze graph patterns without input data. Following previous works (Luo) al., 2020 Yuan et al., 2021 Lin al. 2021; Wang et al. 202T Bajaj et al.) (02T). we focus on instance-level methods with ex explanations using graph sub-structures. Also, our approach is model- agnostic. In particular, given an input graph, our explanation model can generate a subgraph that the most important to the outcomes of pre-trained GNN on any downstream graph-related task, such as graph classification tasks.
3 MOTIF-BASER GRAPH NEURAL NETWORK EXPLAINER
Luo et al. 2020 identify the most important nodes or edges. SubgraphX (Yuan et al.] 2021) is the first work that proposed a method to explain GNN models by generating the most significant subgraph for input graph. However, the subgraphs
Most existing GNN explainers Ying al. 2019
2

---

Under review as a conference paper at ICLR 2023
(-))
5(-)
Graph emnbedking
Prodiction
Shore
My
Mr(-)
coibedding my
Query
Sharz
Mosi Mc
M/ (-()
Morid cribeikiig at
enbeddinng
New aragth
E(-)
prodicioon
Sharz
VP (-)
enthrrdiinnn m.
Atteation Model
mr,
(M,) ON softmunt (mr h)
Mtetis Extraction
V(-) (-) Preamineed GNN Festure Extractor
{(-
Pre-tained Chasifie
Figure 1: An illustration of the proposed MotilExplainer graph classification tasks. Given graph, we first extract motifs based on extraction rules. Then, motif embedding is generated for each motif by feeding it into the pre-trained GNN feature extractor. After that, employ attention layer that uses graph embedding as the query and motif embedding as keys and values, resulting in a new graph embedding. Finally, the loss is computed based on the new and the original predictions.
identified by SubgraphX may not be recurrent or statistically important. This section proposes a novel GNN explanation method, named MotifExplainer, to explain GNN models based on motifs.
3.1 FROM SUBGRAPH TO MOTIF EXPLANATION
Unlike explanation models for text and image tasks, graph has non-grid topology structure information, which needs to be considered in an explanation model. Given an input graph and a trained GNN model, most existing GNN explainers such as GNNExplainer (Ying al. 2019) and PGExplainer (Luo et al.) 2020) identify important edges and construct subgraph containing all those edges as the explanation of the input graph. However, these models ignore the interactions be- tween edges or nodes and implicitly measure the essence of substructures. To address this limitation, SubgraphX (Yuan et al., 202T) proposed to employ subgraphs for GNN explanation. It explicitly evaluates subgraphs and considers the interaction between different substructures. However, it does not use domain knowledge like motif information when generating the subgraphs.
A motif can be regarded a simple subgraph of a complex graph, which repeatedly appears in graphs and is highly related to the function the graph. Motifs have been extensively studied in many fields, like biochemistry, ecology, neurobiology, and engineering (Milo et al. 20022; [Shen- Orr et al.) 2002 Alon 2007: 2019) and are proved to be important. A subgraph identified without considering domain knowledge can be ineffective for downstream tasks like fragment library gen- eration in FBDD. Thus, it is desirable to introduce statistically important motif information to a more lumaan-understandable GNN explanation. In addition, subgraph-based explainers like Sub- graphX need to handle a large searching space, which leads to efficiency issues when generating explanations for dense large scale graphs. In contrast, the number of the extracted motifs can be constrained by well-designed motif extraction rules, which means that using motifs as explana- tions can significantly reduce the search space. Another limitation of SubgraphX is that it needs to pre-determine maximum number of nodes for its searching space. As the number of nodes in graphs varies greatly, is hard to set a proper number for searching subgraphs. large number will tremendously increase the computational resources, while a small number can limit the power of the explainer. To address the limitations of subgraph-basee based explainers, we propose a novel method that explicitly select important motifs as explanation for given graph. Compared to explainers based on subgraphs, our method generates explanations with motifs, which are statistically important and more human-unde undrrnnddaart..ble......
3.2 MOTIF EXTRACTION
This section introduces domain-specifie motif extraction nules.
3

---

Under review as a conference paper at ICLR 2023
Algorithm 1 MotifEEplainer for graph classification tasks
Input: set of graphs G, labels for graphs Y = {uV1.... yis "i. Vn a pre-trained GNN (-)),,
pre-trained classifier E(+). motif extraction rule R.
Initialization: initial trainable weight matrix W
for graph G, in G do
Graph embedding j = V/ (G.)
Create motif list M {m, mij.... me) based on extraction rule R
Generate motif embedding for each motif m;j = Vp (m))
Obtain an output score for each motif 5 = m, W
Train an attention weight for each motif 0j Σnn exp(82)
exp(s,)
Acquire alternative graph embedding h Σ 2 0
Output a prediction for the alternative graph embedding ús = E(h') Calculate loss based on y, and D; loss fly. Update weight W. end for
Domain knowledge. When working with data from different domains, motifs are extracted based on specific domain knowledge. For example, in biological networks, feed-forward loop, bifan, single- input, and multi-input motifs are popular motifs. which have shown to have different properties and functions (Alon 2007; Mangan & Alon 2003; Gorochowski et al.) 2018). For graphs or networks in the engineering domain, the three-node feedback loop (Leite & Wang| 2010) and four-node feedback loop motifs (Piraveenan et al. 2013) are important in addition to the feed-forward loop and bifan motifss. Motifs have also been shown to be important in computational Chemistry Yu & Gao 2022)
The structures of these motifs are illustrated in Appendix C
Extraction methods. For molecule datasets, we can sophisticated decomposition methods like RECAP (Lewell et al., 1998) and BRICS (Degen et al. 2008) algorithms to extract motifs. For other datasets that do not have mature extraction methods like biological networks and social networks, inspired by related works on graph feature representation learning (Yu & Gao [022] [Borritsa et al.] 2022), propose a general extraction method in Appendix B that only considers cycles and edges as motifs, which can cover most popular network motifs. Our methods can be easily applied to other domains by changing the motif extraction rules accordingly.
Computational graph. We define the computational graph of a given graph based on different tasks. The computational graph includes all nodes and edges contributing to the prediction. Since most GNNs follow a neighborhood-aggeen on the architecture of GNNs, such as the number of layers. In graph classification tasks, all nodes and edges contribute to the final prediction. Thus, graph itself is its computational graph in graph classification tasks. For node classification tasks, a target node's computational graph the T.-hop subgraph centered on the target node, where I. is the number of GNN layers. Here, we only consider motif's in the computational graph since those outside it are irrelevant to the predictions.
scheme, the computational graph usually depends
Motif extraction. Given graph G, we extract all motifs based on the motif extraction method. If a motif has been extracted from the graph, it is added to a motif list M. After searching the whole graph, there may be edges not in any motif. We regard each of them one-edge motif and add them to the motif list to retain the integrity of the graph information. At last, we can obtain the motif list. M [m1, ma,..... my] in G.
3.3 MOTIF EMBEDDING
After extracting motifs M from a given graph, we encode the feature representations for each motif. Given pre-trained GNN model, we split it into two parts: feature extractor (-) and classifier E(.). The feature extractor (-) generates an embedding for the prediction target. In particular, (-) outputs graph embeddings in graph classification tasks, and outputs node embeddings in node classification tasks. The motif embedding is obtained in a graph classification task by feeding all motif node embeddings into readout function. While in a node classification task, motif embedding encodes the influence of the motif on the node embedding of the target node. Thus, we feed the target node k and motif m, M subgraph into the GNN feature extractor ()() and use the
4

---

Under review as a conference paper at ICLR 2023
resulting target node embedding of k as the embedding of the motif. To ensure the connectivity of the subgraph, we keep edges from the target node to the motif and mask features of irrelevant nodes.
3.4 GNN EXPLANATION FOR GRAPH CLASSIFICATION TASKS
This section introduces how to generate an explanation for pre- pre-trained GNN model in graph classification task. We split the pre-trained GNN model into a feature extractor v(()) and a classifier $(). Given graph G. its original graph embedding h is computed as h (G)) The prediction y is computed by y = E(h).
Based on the given graph, method extracts a motif list from it and generates motif embedding M = [m,, m2,..... m., using the pre-trained feature extractor (.). Since the original graph em- bedding is directly related to the predictions, identify the most important motifs by investigating relationships between the original graph embedding and motif embeddings. To this end, we em- ploy an attention layer. which uses the original graph embedding h (G) as query and motif embedding M as keys and values. The output of the attention layer is considered as a new graph embedding h'. We interpret the attentions scores as the strengths of relationships between the pre- diction and motifs. Thus, highly relevant motifs will contribute more to the new graph embedding. By feeding the new graph embedding h' into the pre-trained graph classifier E(-), new prediction y' = {(h') is obtained. The loss based y and y' evaluates the contribution of selected motifs to the final prediction, which trains the attention layer such that important motifs are selected to produce similar predictions to the original graph embedding. Formally, this explanation process can be represented as
h = (G), y = =(hh)
(1)
M [m,, .2,............................. m4] MotifExtractor(GG)
(2)
M [m,, m2...... m,] (m,))]
(3)
h' Ahmn M,M)
(4)
y' = E(h'),
(5)
loss fyy.''
(6)
where Attn an attention layer and f is loss function. After training, we use the attention scores to identify important motifs. To our knowledge, our work first attempts to use the attention mechanism for GNN explanation. We want to mention that attention mechanism is only a tool for selecting important motifs. Any other methods that can identify relevances between two feature vectors can be applied in our model. In addition, attention scores are only used in training, while we have other metrics for evaluation.
During testing, we use a threshold o/t to select important motifs, where a is a hyper-parameter and t is the number of motifs extracted. The explanation includes the motifs whose attention scores larger than the threshold. Algorithm describes our GNN explanation method on graph classifica- tion tasks, In addition, we provide an illustration of the proposed MotifExplainer in Figure]
3.5 GNN EXPLANATION FOR NODE CLASSIFICATION TASKS
This section introduces how to generate an explanation for a node classification task. Given graph G and a target node v., we first construct computational graph for v;. which is an L-hop subgraph as described in Section 3.2 Then we extract motifs from the computational graph and generate motif embedding for each motif using the feature extractor (-). To keep the connectivity between a target node and a motif, we keep the shortest path between each node in the motif and the target node in an explanation graph. To reduce the impact of nodes on the path, we set irrelevant nodes' features to zero. After that, the proposed MotifExplainer employs an attention layer to identify important motifs. The attention layer for node classification tasks similar to the one for graph classification tasks, except that the query is the embedding of the target node. A node embedding is generated by feeding the whole graph into the feature extractor V (.). The target node's output feature vector h, is used the query vector in the attention layer, which outputs the new node embedding h/-- Similarly, the new prediction y' = <(h() is obtained by feeding h' into the pre-trained classifier. We use threshold a o/t during testing identify important motifs explanation. Algorithm 2 in
5

---

Under review as a conference paper at ICLR 2023
the appendix describes the details of the MotifExplainer node classification tasks. Formally, the different parts from Section 3.4 are represented as
= v (G),, 8 {(h).
Ge ComputationGGaap((G..c uz),
(8)
[m1, m.,.... my] MotifExtractor(Ge)
(9)
Then, Eq. 3
6 are applied to compute loss for training the attention layer.
EXPERIMENTAL STUDIES
We conduct experiments to evaluate the proposed methods on both real-world and synthetic datasets.
4.1 DATASETS AND EXPERIMENTAL SETTINGS
We evaluate the proposed methods using different downstream tasks on seven datasets to demon- strate the effectiveness of our model. The statistic and properties of seven datasets are summarized in Appendix D The details are introduced below.
Datasets. MUTAG (Kazius et al. 2005 Riesen Bunke 2008
chemical compound dataset containing 4,337 molecule graphs. Each graph can be categorized into mutagen and non-mutagen.
PTC (Kriege Mutzel 2012) is collection of 344 chemical compounds reporting the carcino- genicity for rats.
NCII (Wale et al.j 2008) is a balanced subset of datasets chemical compounds screened for activity against non-small cell lung cancer and ovarian cancer cell lines respectively.
PROTEINS (Dobson Doig 2003) is protein dataset classified as enzymatic or non-enzymatic.
IMDB-BINARY Yanardag & Vishwanathan 2015) is movie collaboration dataset that consists of the eet-networks of 1,000 actors/actresses who played roles in movies in IMDB.
BA-2Motif's (Luo et al. 2020) is synthetic graph classification dataset. It contains 800 graphs, and each graph is generated from a Barabasi-Albert (BA) base graph.
BA-Shapes (Ying et al. 2019) is synthetic node classification dataset. It contains single base BA graph with 300 nodes.
Experimental settings. Our experiments adopt simple GNN model and focus explanation results. More details of settings can be found in Appendix We compare our MotifExplainer model with several tfte-offthheart baselines: GNNExplainer, SubgraphX, PGExplainer, and ReFine. We also build model that uses the same attention layer as MotifExplainer but assigns weights to edges instead of motifs. Noted that all methods are compared in fair setting. During prediction, use = to control the size of selected motifs. Unlike other methods, we do not explicitly set fixed number for selected edges explanations, enabling maximum flexibility and capability when selecting important motifs.
Evaluation metrics. A fundamental criterion for explanations is that they must be human- explainable, which means the generated explanations should be casy to understand. Taking the BA-2Motif as an example, a graph label is determined by the house structure attached to a base BA graph. A good explanation of GNNs on this dataset should highlight the house structure. To this end, we perform qualitative analysis to evaluate the proposed method.
Even though qualitative analysis/visualization can provide insight into whether explanation is reasonable for human beings, this assessment is not entirely dependable due to the lack of ground truth in real-world datasets. Thus, employ three quantitative evaluation metrics to evaluate explanation methods. We use the Accuracy metric to evaluate models for synthesis datasets with ground truth. Here, use the same settings GNNExplainer and PGExplainer. In particular, regard edges inside ground truth motifs as positive edges and edges outside motifs as negative.
An explainer aims answer question that when trained GNN predicts input, which part of the input makes the greatest contribution. To this end, the explanation selected by an explainer must be unique and discriminative. Intuitively, the explanation obtained by the explainer should

---

Under review as a conference paper at ICLR 2023
MotifExplainer
SuhgraphX
PGExplainer
GNNExplainer
Figure 2: Visualization of explanation results from different explanation models three datasets. The generated explanations are highlighted by green and bold edges. Three rows are results on the MUTAG dataset, the BA-Shape dataset, and the BA-2Motif dataset, respectively. We only show the motif-related edges for two synthetic datasets to save space.
obtain similar prediction results the original graph. Also, the explanation is in reasonable size. Thus, following (Yuan et al. 2020b), we use Fidelity and Sparsity metrics to evaluate the proposed method real-world datasets. In particular, the Fidelity metric studies the prediction change by keeping important input features and removing unimportant features. The Sparsity metric measures the proportion of edges selected by explanation methods. Formally, they computed by
Fidelity
(V.G)), (.GG)))))
(10)
N Σ N
Pd
Sparsity =
1
(11)
where is an explanation for an input graph Gj- Ip:l and |G;| denote the number edges in the explanation, and the number in the original input graph, respectively.
4.2 QUALITATIVE RESULTS
In this section, we visually compare the explanations of our model with those of state-of-the-art explainers. Some results are illustrated in Figure 2 with generated explanations highlighted. We report the visualization results of the MUTAG dataset in the first row. Unlike BA-Shape and BA- 2Motif, MUTAG is real-world dataset and does not have ground truth for explanations. We need to leverage domain knowledge to analyze the generated explanations. In particular, carbon rings with chemical groups NH2 or NO₂ tend to be mutagenic. As mentioned by PGExplainer, carbon rings appear in both mutagen and mon-munagenic graphs. Thus, the chemical groups NH2 and NO, more important and considered as the ground truth for explanations. From the results, our MotifEx- plainer can accurately identify NH₃ and NO, graph while other models can not. PGExplainer identifies some extra unimportant edges. SubgraphX produces subgraphs as explanations that are neither motifs nor human-understandable Our proposed GNN explainer can consider motif infor- mation and generate better explanations molecular graphs. Note that neither NH, nor NO, is explicitly included our motif extraction rules. The explanation generated by identifying bonds in these groups, which means that our method can be used to find motifs.
We show the visualization results of the BA-Shape dataset the second row of Figure In this dataset, a node's label depends on its location as described in Section 4.1 Thus, an explanation generated by an explainer for a target node should be the motif. We consider the selected edges on the motif to be positive and those not on the motif negative. From the results, our MotifExplainer can accurately mark the motif as the explanation. However, other models select part of the motif' or include extra non-motif edges. The third of Figure shows the visualization results the BA-2Motih dataset, which also a synthetic dataset. From Scction[4.1. graph's 's label is determined by the motif attached to the base graph: the five nodes house-like motif the five nodes cycle motif.

---

Under review as a conference paper at ICLR 2023
Table 1: Results quantitative studies for different explanation methods. Note that since the Sparsity cannot fully controlled, we report Fidelity scores under similar Sparsity levels. For two synthetic datasets BA-Shape and BA-2Motif, report accuracy. S is the sparsity value. K is the maximum number of edges required by baseline models. Our MotifExplainer does not need this required hyper-parameter. The best performances each dataset shown in bold.
MUTAG
PTC
NCI1
PROTEINS
IMDB
BA-2Motif
BA-Shape K=5
S=0.7
5=0.7
S=0.7
S=0.7
S=0.7
K=5
GNNExplainer
0.260
0.441
0.365
0.453
0,365
0.742
0,925
PGExplainer
0.241
0.388
0.402
0.521
0.225
0.926
0,963
SubgraphX
0.287
0.227
0.303
0.021
0.167
0.774
0.874
ReFine
0.221
0.349
0.409
0.435
0.127
0.932
0.954
MotifExplainer
0.031
0.129
0.115
-0.030
0.101
1.0
1.0
Thus, we treat all edges in these two motifs to be positive and the rest of edges to be negative. From the results, we can see that our MotifExplainer can precisely identify both the house-like motif and the cycle motif in a graph without including non-motif edges. While other models select edges far from the motif. More qualitative analysis results reported in Appendix
4.3 QUANTITATIVE RESULTS
This section shows evaluations of our methods using seven datasets. We report the Fidelity score under the same Sparsity value on five real-world dataset and accuracy on the other two synthetic datasets. More Fidelity scores real-world dataset are shown in Appendix B The results summarized Table | From the results, our MotifExplainer consistently outperforms previous state-of-the-art models all seven datasets under Sparsity value equals 0.7 Note that our method achieves 100% accuracy on two synthetic datasets and at least 2.6% to 19.0% improvements on the real-world datasets, demonstrating our model's effectiveness.
Our model can maintain good performances when Sparsity is high. In particular, in the case of high Sparsity, the explanation contains very limited number of edges, which shows that our model can identify the most important structures for GNN explanations. Using motifs as basic explanation units, our model can preserve the characteristics of motifs and the connectivity of edges.
4.4 THRESHOLD STUDIES
Table 2: The study of threshold.
Our MotifExplainer uses a threshold a to select important motifs as explanations during inference. Since a is an important hyper-parameter, we conduct experiments to study its impact using Sparsity and Fi- Fidelity
Threshold
1.0
1.2
1.5
Sparsity
0.4
0.5
0.6
0.7
0.8
0.025
0.053
0.054
0.031
0.028
delity metrics. The performances of MotifExplainer using different values the MUTAG dataset are summarized in Table Here, we vary the a value from 1.0 to 2.0 to cover a reasonable range. We observe that when the threshold is larger, the Sparsity of explanations increases, and the per- formances in terms of Fidelity gradually decrease. This is expected since fewer motifs selected will be selected when the threshold becomes larger. Thus, the size of explanations becomes smaller, and the Sparsity value becomes larger. Note that even when the Sparsity reaches high value of 0.8, our model can still perform well. This shows that our model can accurately select the most important motifs as explanations, demonstrating the advantage of using motifs as GNN explanations.
4.5 ABLATION STUDIES
Our MotifExplainer employs an attention model to score and select the most rele- vant motifs to explain given graph. To demonstrate the effectiveness of using mo- tifs as basic explanation units, we build new model named AttnExpainer that uses edges as basic explanation units and apply attention model select relevant edges explana-
Table 3: Results for AttmExplaine and MotifExplainer on three datasets. K=5 for two synthetic datasets.
MUTAG
BA-2Motif
BA-Shape
AttnExplainer MotifExplainer
0.166
0.934
0.955
0.031
1.0
1.0
8

---

Under review as a conference paper at ICLR 2023
tions. We compare our MotifExplainer with AttnExplainer three datasets: BA-Shape, BA-2Motif, From the results, our model can con-
MUTAG. The results are summarized in 3 appendix E sistently outperform AttnExplainer This is because motif's can better obtain structural information than edges by using motif as the basic unit for explanation.
4.6 EFFICIENCY STUDIES
Table Results on efficiency studies.
We study the efficiency of our proposed model in terms of the training time and the inference time. For models that need to be trained, such as PGExplainer and ReFine, training and evaluation processes are separate. We report training and inference time separately. In our proposed method, the training time includes three parts: motif ex- traction, motif embedding construction, and the training of the attention model. For models that do not require training, their training time will be O. For each model, run it the MUTAG dataset and show the averaging time consumed to obtain explanations for each graph. Table f shows the compari- son results with four state-of-the-art GNN explanation models: MotiffEplaiiner, SubgraphX, PG- Explainer, GNNExplainer, and ReFine. From the results, our model has the shortest inference time among models. Compared to PGExplainer and ReFine, our model requires significantly less training time. From this point, the proposed method is efficient and feasible in real-world applications.
Method
Inference
Training
GNNExplainer
24.3s
Os
PGExplainer
0.03s
740s
SubgraphX
96.7s
ReFine
0.83s
946s
MotilExplainer
0.02s
363s
RELATED WORK
The research on GNN explainability is mainly divided into two categories: instance-level expla- nation and model-level explanation. Instance-level GNN explanation also be divided into four directions, namely gradients/features-ban and perturbation-base map values as the approximations of an importance score of an input. Recently, several methods have been employed to explain GNNs like SA (Baldassarre & Azizpour 2019). CAM (Pope al., 2019). Grad-CAM (Pope et al., 2019). The basic idea of surrogate methods is using simple and explainable surrogate model approximate the predictions of GNNs. Several methods have been in- troduced recently, such as GraphLime (Huang et al., 2020) and PGM-Explainer (Vu & Thai 2020). Decomposition methods like GNN-LRP (Schnake al. 2020) and DEGREE (Feng al. 2021]
methods, surrogate methods, decomposition methods, methods. Gradients/features-b
methods use gradients hidden feature
measure the importance of input features by decomposing original predictions into several terms. The last method is the perturbation-
method. Along this direction, GNNExplainer (Ying et al.) 2019) learns soft masks for edges and node features to generate an explanation via mask optimiza- tion. PGExplainer (Luo et al., 2020) learns approximated discrete masks for edges by using domain knowledge. SubgraphX (Yuan et al., 2021) employs Monte Carlo Tree Search algorithm to search possible subgraphs and uses Shapley value to measure the importance of subgraphs and choose a subgraph as the explanation. ReFine (Wang et al., 202T) proposes idea of generating multi- grained explanations. There are also some reinforcement learning based explainers (Shan et al. 2021 Wang al., 2022). Model-level explanation methods aim find the general insights and high-level information. So far, there is only one model-level explainer: XGNN (Yuan et al. (2020a). XGNN trains generator and generates a graph as explanation to maximize target prediction.
6 CONCLUSION
This work proposes novel model-agnostic motif bosef- GNN explainer to explain GNNs by iden- tifying important motifs, which are recurrent and statistically significant patterns in graphs. Our proposed motif-based methods can provide better human undaassdddrtttddbbllee explanations than meth- ods based on nodes, edges, and regular subgraphs. Given a graph, We first extract motifs from a graph using motif extraction rules based on domain knowledge. Then, motif embedding for each motif is generated using the feature extractor from a pre-trained GNN. After that, we train an at- tention model to select the most relevant motifs based on attention weights and use these selected motifs as an explanation for the input graph. Experimental results show that our MotifExplainer can significantly improve explanation performances from quantitative and qualitative aspects.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Uri Alon. Network motifs: theory and experimental approaches. Nature Reviews Genetics, 8(6): 450-461, 2007.
Uri Alon. An introduction to systems biology: design principles of biological circuits. CRC press, 2019.
Mohit Bajaj, Lingyang Chu, Zi Yu Xue, Jian Pei, Lanjun Wang, Peter Cho-Ho Lam, and Yong Zhang. Robust counterfactual explanations on graph neural networks. Advances in Neural Infor- mation Processing Systems, 34, 2021.
Federico Baldassarre and Hossein Azizpour. Explainability techniques for graph convolutional net- works. arXiv preprini urXiv:/905: 13686, 2019.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Jörg Degen, Christof Bressheid-Gerladee Andrea Zaliani, and Matthias Rarey. On the of compil- ing and using drug-like' like' chemical fragment spaces. ChemMedChem:: Chemistry Enabling Drug Discovery, 3(1)): 507- 2008.
Paul D Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 337 2003.
Daniel A Erlanson, Robert S McDowell, and Tom O' O'Brien. Fragment- drug discovery. Journal of medicinal chemistry, 47(14):3463-3493 2004.
Qizhang Feng.
Ninghao Liu, Fan Yang, Ruixiang Tang. Mengnan Du, and Xia Hu. Degree: Decom- position based explanation for graph neural networks. In International Conference on Learning Representations, 2021.
Hongyang Gao and Shuiwang Ji. Graph u-nets. In international conference on machine learning, pp. 2083-2092. PMLR, 2019.
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, pp. 1416-1424, 2018
Thomas E Gorochowski, Claire S Grierson, and Mario Di Bernardo. Organization of feed-forward loop motifs reveals architectural principles in natural and engineered networks. Science advances, e(3)s1a 2018.
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.
Jeroen Kazius, Ross McGuire, and Roberta Bursi. Derivation and validation of toxicophores for mutagenicity prediction. Journal of medicinal chemistry, 48(1):12--300 2005.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. arXiv preprint arXiv: 2016.
Nils Kriege and Petra Mutzel. Subgraph matching kernels for attributed graphs. arXiv preprint arXiv: 1206,648,, 2012.
Maria Conceição A Leite and Yunjiao Wang. Multistability, oscillations and bifurcations in feedback loops. Mathematical Biosciences Engineering, 7(1):83, 2010.
Xiao Qing Lewell, Duncan B Judd, Stephen P Watson, and Michael M Hann. Recap retrosynthetic combinatorial analysis procedure: a powerful technique for identifying privileged molecular fragments with useful applications combinatorial chemistry. Journal of chemical information and computer sciences, 38(3):511-522, 1998.
10

---

Under review as a conference paper at ICLR 2023
Wanyu Lin, Hao Lan, and Baochun Li. Generative causal explanations for graph neural networks. arXiv preprint arXiv:2104.0664 2021.
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 338-348, 2020.
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. arXiv preprint 2020.
Shmoolik Mangan and Uni Alon. Structure and function of the fordarorward loop network motif. Proceedings of the National Academy of Sciences, 100(2)):11800-1199 2003.
Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Net- work motifs: simple building blocks of complex networks. Science, 298(5594):824 827, 2002.
Mahendra Piraveenan, Kishan Wimalawarne, and Dharshana Kasthurirathn. Centrality and com- position of four-node motifs in metabolic networks. Procedia Computer Science, 18:409-418, 2013.
Phillip E Pope, Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann. Ex- plainability methods for graph convolutional neural networks. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 10772-10781, 2019.
Kaspar Riesen and Horst Bunke. lam graph database repository for graph based pattern recognition and machine learning. In Joint IAPR International Workshops on Statistical Techniques in Put- fern Recognition (SPR) and Structural and Syntactic Puttern Recognition (SSPR), pp. 287-297.
Springer, 2008.
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 preprini 4rXiv:2006.03589) 2020.
Caihua Shan, Yifei Shen, Yao Zhang, Xiang Li, and Dongsheng Li. Reinforcement learning en- hanced explainer for graph neural networks. Advances in Neural Information Processing Systems, 34:22523-222 22533,, 2021.
Shai S Shen-Orr, Ron Milo. Shmoolik Mangan, and Uri Alon. Network motifs in the transcriptional regulation network of escherichia coli. Nature genetics, (1 2002.
Minh N Vu and My T Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. arXiv preprint arXiv:2010.05788, 2020.
Nikil Wale, Ian A Watson, and George Karypis. Comparison of descriptor spaces for chemical com- pound retrieval and classification. Knowledge and Information Systems, 14(3):347-375, 2008.
Xiang Wang. Yingxin Wu, An Zhang, Xiangnan He, and Tat-Seng Chua. Towards multi multi-grained explainability for graph neural networks. Advances in Neural Information Processing Systems, 34, 2021.
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.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826 2018.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365-1374, 2015.
Rex Ying. Dylan Bourgeois, Jiaxuan You, Marinka Zitnkk, and Jure Leskovec. Gnnexplainer Gener- ating explanations for graph neural networks. Advances in neural information processing systems, 32:9240, 2019.
11

---

Under review as a conference paper at ICLR 2023
Zhaoning Yu and Hongyang Gao. Molecular representation learning via heterogeneous motif graph neural networks. In International Conference on Machine Learning, pp. 25581-25594. PMLR, 2022.
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, pp. 430 400-448 2020a.
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey, arXiv preprint 20X1:22012.15445, 2020b.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. arXiv preprint 1rXiv:21002.51152,22 2021.
12

---

Under review as a conference paper at ICLR 2023
A PSEUDOCODE FOR EXPLAINING NODE CLASSIFICATION TASKS
Algorithm 2 MotifExplainer for node classification tasks
Input: graph G. labels for nodes in the graph [.) yir.... J. pre-trained GNN (())) pre-trained classifier E(-), motif extraction rule R
Initialization: initial a trainable weight matrix W, calculate all node embedding H
{h1, A,....,,.))
for node U; in the graph G do
Original node embedding h; H
Create motif list M = {m,..... my..... my based on extraction rule R
For each motif m, we keep the motif, the target node e; and the edges between them. Then we put this subgraph into the pre-trained GNN (-) and get a new node embedding of target node o as the motif embedding m;
Obtain an output score for each motif 5, = m. W h; exp(x,)
Train an attention weight for each motif 0t) Σ _==1 exp(sE)
Acquire an alternative graph embedding h/ = Σ -ー a Output prediction for the alternative graph embedding Ùs E(h,)
Calculate loss based on Is and y/ Update weight W using paopappoo.g.tion.
end for
B A GENERAL MOTIFS EXTRACTION RULE
According to section 3.2 we can easily design motif extraction rules based on some domain knowl- edge. However, if we don't ton't have relevant domain knowledge or the dataset type is unknown, we need a general way to obtain the motifs. Inspired by graph feature representation learning works on motifs (Bouritsas al. 2022 Yu & Gao 2022), propose general method to extract the simplest motifs: cycles and edges. In particular, given a graph, we first extract all cycles out of it. Then, all considered motifs. We consider combining cycles with more
edges that are not inside the cycles than two coincident nodes into a motif. Although this method cannot extract complex motifs like single-input and multi-input motifs, it can generate the most important motifs, such ring struc- tures in biochemical molecules and the feed-forward loop motif. By adopting this simple but general motif extraction method, we can explain GNN model without any domain knowledge, making our explanation model more applicable. Need to be noted that, even though the motif extraction rule cannot extract single-input and multi-input motifs, these motifs can be implicitly identified by our attention layer. Experiments in the table demonstrate it.
C COMMON MOTIFS IN BIOLOGICAL AND ENGINEERING NETWORKS
W
Bide
Feod-forwar
Sapp
Musti-rpurt
Tiree gode feedbuck loop
Fourstede feechack keep
Figure 3: Popular motifs biological and engineering networks.
13

---

Under review as a conference paper at ICLR 2023
In this section, Figure 3 show some common motifs in biological and engineering networks intro-
duced in section 3.2
D DATASETS AND GNN MODELS
D.1 STATISTIC AND PROPERTIES OF DATASETS
Table 5: Statistics and properties of three datasets.
MUTAG
PTC
NCI1
PROTEINS IMDB
BA-2Motif
BA-Shape
Edges (avg)
30.77
14.69
32.30
72.82
96.53
25.48
4110
# Nodes (avg)
30.32
14.29
29.87
39.06
19.77
25.0
700
# Graphs
4337
344
4110
1113
1000
1000
# Classes
2
D.2 SETTINGS OF GNN MODELS
For the pre-trained GNN, use a 3-layer GCN as feature extractor and a 2-layer MLP classifier on all datasets. The GCN model is pre-trained to achieve reasonable performances on all datasets. We use Adam optimizer for training. We set the learning rate to 0.01.
Real World Datasets We employ a 3-layer GCNs to train all five real world datasets. The input feature dimension is and the output dimensions of different GCN layers are set 64, 64, 64, respectively. We employ mean-pooling as the readout function and ReLU as the activation function. The model trained for 170 epochs with learning rate 0.01. We study the explanations for the graphs with correct predictions.
BA-Shape We use a 3-layer GCNs and an MLP as a classifier to train the BA-Shape dataset. The hidden dimensions of different GCN layers set to 64, 64, 64, respectively. We employ ReLU as the activation function. The model is trained for 300 epochs with a learning rate of 0.01. The validation accuracy of the pre-trained model can achieve 100%. We study the explanations for the whole dataset.
BA-2Motif We use 3-layer GCNs and an MLP as classifier to train the BA-2Motif dataset. The hidden dimensions of different GCN layers are set to 64, 64, 64, respectively. We employ mean-pooling the readout function and ReLU the activation function. The model is trained for 300 epochs with a learning rate of 0.01. The validation accuracy of the pre-trained model can be 100%, which means the model can perfectly generate the distribution of the dataset. We study the explanations for the whole dataset.
D.3 EXPERIMENT ENVIRONMENT SETTINGS
We conduct experiments using one Nvidia 2080Ti GPU on an AMD Ryzen 7 3800X 8-Core CPU. Our implementation environment based Python 3.9.7, Pytorch 1.10.1, CUDA 10.2, and Pytorch-geometric 2.0.3.
14

---

Under review as a conference paper at ICLR 2023
E MORE QUANTITATIVE RESULTS
Table 6: Quantitative results MUTAG dataset. S is the sparsity value. K is the maximum number of edges required by baseline models. The best performances on each dataset are shown in bold. MUTAG (Fidelity)
$=0.4
$=0.5
S=0.6
S=0.7
S=0.8
GNNExplainer
0.153
0.184
0.219
0.260
0.307
PGExplainer
0.133
0.154
0.194
0.241
0.297
SubgraphX
0.214
0.233
0.254
0.287
0.376
ReFine
0.075
0.124
0,180
0.221
0,311
AttnExplainer
0.085
0.111
0.133
0,166
0.182
MotifExplainer
0.025
0.053
0.054
0.031
0.028
Table Quantitative results on PTC and NCII dataset. is the sparsity value. K maximum number of edges required by baseline models. The best performances on each dataset are shown in bold.
PTC (Fidelity)
NCI (Fidelity)
$=0.6
S=0.7
S=088
S=0.6
S=0.7
S=0.8
GNNExplainer
0.3835
0,4406
0,4947
0.3612
0.3653
0.3648
PGExplainer
0.3653
0.3886
0.3917
0.4013
0.4029
0.4045
ReFine
0.3268
0.3499
0.3575
0.4028
0.4093
0,4115
SubgraphX 0.2062
0.2274
0.2643
0.1697
0.3036
0,4075
MotifExplainer
0.1162
0.1299
0.2256
0.1002
0.1154
0.1297
Table 8: Quantitative results PROTEINS and IMDB-B dataset. S is the sparsity value. K is the maximum number of edges required by baseline models. The best performances on each dataset are shown in bold.
PROTEINS (Fidelity)
IMDB-B (Fidelity)
S=0.6
S=0.7
S=0.8
S=0.6
S=0.7
$=0.8
GNNExplainer
0.4558
0.4535
0.4947
0.1577
0.3653
0.3098
PGExplainer
0.5215
0.5214
0.5207
0.1801
0.2253
0.2784
ReFine
0.3399
0.4354
0.4974
0.0952
0.1278
0.1829
SubgraphX
0.0138
0.0211
0.0398
0.1342
0.1671
0.1955
MotifExplainer
-0.0140
-0.0300
-0.0558
0.0757
0.1011
0.1125
15

---

Under review as a conference paper at ICLR 2023
F VISUALIZATION OF EXPLANATION
In this section, we report more visualization explanation on MUTAG dataset Figure 4 MU- TAG real-world dataset, and is more complex than synthetic datasets. Thus, visualization of MUTAG can better represent how different explainer works.
MotifExplaaner
SubgraphX
PGExplainer
GNNExplainer
ReFine
Figure 4: Popular motifs in biological and engineering networks.
16


Reviews:
[{"review_id": "iFTHt2qpj6e", "reviewer": "Reviewer_U3mX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper aims to explain predictions of graph neural networks (GNNs). Existing GNN explanation methods identify important edges, nodes, or arbitrary substructures but fail to consider recurrent and interpretable substructures. This work proposes MotifExplainer to explain GNNs by identifying important motifs. Empirical studies on both synthetic and real-world datasets demonstrate the effectiveness of the proposed method.", "summary_of_the_review": "It is a reasonable approach to use known (or domain-specific) motifs to better explain the decisions of GNNs. However, I think the technical contributions of this paper are limited in two ways: a) the proposed approach does not work without pre-defined motifs, which is common in real-world cases, and b) the proposed approach seems to be a combination of existing techniques.", "strength_and_weaknesses": "Strengths\n1. Using the attention mechanism for motif-based explanation seems like an efficient and reasonable approach.\n2. Diverse experiments are done to demonstrate the superiority of the proposed approach.\n3. This paper is generally written well, and there is not much confusion in understanding it.\n\nWeakesses\n1. The proposed approach requires domain-specific motifs as its inputs. This makes the approach less generalizable, and its improved accuracy as the result of adding domain-specific knowledge into the algorithm, rather than the result of technical improvements. One important goal of GNN explanation is to find new, meaningful substructures from the graph which play a key role in the prediction, which give novel insights and observations about the given graph. This work does not have such an advantage.\n2. The technical contribution is limited. Using attention for GNN explanation is a reasonable approach, but is not novel. This paper presents the approaches for node and graph classification in separate subsections, but they look very similar and can be presented together. Other parts of the proposed approach, such as motif extraction and embedding, also look trivial.\n3. Many parts of the proposed approach are not clearly presented, even though they are the core parts of technical contributions. See the questions below.\n\nQuestions\n1. Section 3.2: What happens if the same edge is contained in multiple motifs?\n2. Section 3.2: What is the complexity and actual time for extracting motifs?\n3. Section 3.3: How do we keep edges from the target node to the motif?\n4. Section 3.3: How do we mask features of irrelevant nodes?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "S7ohSPsCmfc", "reviewer": "Reviewer_ayU3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies explainability of graph neural networks (GNNs). The authors are particularly interested in using motifs to generate the explanantion, since motifs are more meaningful and statistically significant in many graph mining tasks. Based on this motivation, the authors propose MotifExplainer, which first extracts motifs with domain knowledge and then leverages attention mechanism to measure the contribution of each motif. And the motifs with the highest attention scores are used as the proxy to find the most important motifs. Experimental results show that the proposed MotifExplainer not only outperforms all baseline methods quantitatively and qualitatively, but also is the fastest method during inference.", "summary_of_the_review": "The paper is well motivated and easy to follow. My major concern on the technical side is the use of attention mechanism, which is a black box in its nature and controversial to be used as a proxy for finding explanation in NLP tasks. ", "strength_and_weaknesses": "Strengths:\n- Motif is more meaningful in many graph mining tasks, thus the motivation is clear and reasonable.\n- The paper is overall well-written and easy to follow.\n- Both quantitative and qualitative analysis demonstrate the efficacy of the proposed model.\n\nConcerns/Questions:\n- For a node classification task, suppose that the target node is 'far away' from the motif and is not directly connected to any node in the motif. How should we keep the connectivity between the target node and the motif?\n- The goal of explainability is to open the black box of deep learning models. More importantly, there was a hot debate in NLP domain on whether we should trust attention as a proxy of explanation. I assume such problem could exist in GNN as well. As such, how should we trust the explanation generated by another black-box model (attention layer here)? \n- Why should we use attention score rather than directly using the contribution of each motif to find important subgraphs (i.e., the loss $f(y, y')$)?\n\n\n========================\nThe author have addressed most of my concerns. I have raised my score. But in general, I still think some evaluation (whether quantitative or qualitative) without using those black-box module is essential.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "OJAwh3vyJE", "reviewer": "Reviewer_M4gL", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presented an explanation model on motif of the graph. The motif of choice is generated with domain knowledge. Following by an attention model, the attention weights is utilized for the explanation for the GNN from the motif. Compared with state of the art, the method showed high performance. The human readability of the motif is also a plus of the paper. However, application for this method on other domain would be limited owing to the lock of the domain knowledge.", "summary_of_the_review": "This paper presented the motif explanation and showed empirical performance increase over state of the art models. But some limitation also applied for the method to generalize to other domain. ", "strength_and_weaknesses": "Strength:\n1. This is the first method to introduce attention mechanism to explain the importance of the motif. It does showed certain level of improvement compared with previous methods.\n2. The input of domain knowledge do boost the performance increase for the explanation.\n3. They also introduce different scores to cover the explanation, for which their method showed good performance.  \n\nWeakness:\n1. Introducing domain knowledge generated motif would be great but also limited the applicability of this methods. It also introduced certain bias in the performance evaluation as other methods do not have the domain knowledge input. Even though this paper provided a way to generate motif. But only counting the cycle or edge, does not fit my impression of \"motif\" and do limited the power of the method. The ablation study also illustrate the important of the domain knowledge input. For that, I think it significantly hurt the novelty of this paper.\n2. The method could also introduce some background of the attention mechanism in neural network explanation.\n3. This model only performed the test on vanilla GNN with three layers. I think more experiment should be conducted. For example, different GNN architecture. Different hyperparameters like the number of layers, the width of the GNN. I would guess the attention mechanism would have high variance if the architecture is changed. \n\n\n\n \n\n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "IFmRBY3oVo", "reviewer": "Reviewer_EDg3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes MotifExplainer, a method that identifies important motifs - recurrent and statistically significant patterns in graphs - to use as explanations for a Graph Neural Network (GNN) prediction task. The method first extracts motifs in a graph using domain-specific motif extraction rules (specified in the paper). It encodes a motif embedding of the extracted motifs using a pre-trained GNN. These motif embeddings serve as keys to the graph embedding (query) in the attention mechanism applied to learn attention weights by minimizing the loss between the prediction of the attention model and the original predictions.  Experimental results on seven datasets show that MotifExplainer can highlight relevant motifs in the graphs (quantitatively and qualitatively). \n", "summary_of_the_review": "MotifExplainer uses domain-specific motif extraction rules and attention to identify importation motifs. Changing the motif extraction rules accordingly allows for easy application of the method to various domains. The experimental design requires more extensive descriptions (especially about the extracted motifs and design choices) to support the claim that MotifExplainer is a state-of-the-art explanation method. ", "strength_and_weaknesses": "Strengths:\n- The presented idea is interesting and well-explained. A simpler framework - motif extraction+attention - is trained to mimic the performance of a complicated GNN model. The learned attention weights highlight the relevant extracted motif. \n\n- The paper provides motif extraction rules for different application domains.\n\n- The paper presents qualitative and quantitative results on synthetic and real-world datasets and reports state-of-the-art performance. \n\n- The reported computational time for the proposed method is lower than existing models.\n \nWeaknesses:\nThe main weakness of the paper is in the experimental design, as some of the choices are not well defined. \n \n- First, given the importance of the motif extractor scheme for this work, the paper needs to provide a sufficient description (example visualizations) of how much the extractions based on the rules vary from the ground truth. Specifically, the line “note that neither NH2 nor NO2 is explicitly included in our motif extraction rules” is useful. However, how similar/different are these motifs to the construction, like a single input example?  \n \n- While the included baselines are state-of-the-art methods, the presented framework seems to have some ideological similarities to GraphLIME [1] method. Is there a reason this was not included in the comparisons?\n \n- All the methods (proposed and baselines) have hyperparameters that they can be quite sensitive to. Was sufficient hyperparameter tuning performed to select the best explanation? For example, why K=5 was chosen? If not, is that fair?\n \n- My understanding is that fidelity scores should be low (less difference in prediction change when removing unimportant features). Why are the higher scores in Table 1 (for BA datasets) highlighted in bold?  \n\nMinor points:\n\n- The values for K are not specified in Table 6,7,8 in the appendix\n \n- (This point  is on a broader level) The line - “a fundamental criterion for explanations is that they must be human explainable.” While I agree with this statement, it is unclear what \"human explainable\" means outside the context of image and text. If a GNN model can make an accurate prediction using 4 edges of the house motif instead of 5 - do we necessarily want the explainer method to highlight the full motif with 5 edges? I can see the possibility of a disconnect between what the model is learning and what the human expects the model to learn. Maybe the paper could clarify this.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5WWAfCA70Yj", "reviewer": "Reviewer_b3v8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper for the first time adopts motif extraction as a pre-process step to generate the candidate set for explanation, and employs an attention-based method to identify the most important motifs as explanations.\n", "summary_of_the_review": "This paper provides a new way to explain GNNs via motifs. The method is simple, practical and effective, while the idea is straight-forward with limited technical contribution. I also have the following questions.\n- The method requires a motif extraction step, which heavily relies on domain knowledge. As a fair comparison, what if directly applying the general motif extraction algorithm for all datasets, including the molecule datasets?\n- The complexity of the motif extraction algorithm should be discussed, especially when the graph is large.\n- There is a contradiction in the method description: $y$ is the predicted label based on Figure 1, but in Algorithm 1 it represents the ground truth label of the graph. Which one is adopted in the actual design?\n- How large is the motif list for different datasets, compared with the candidate set of SubgraphX?\n- How are the datasets split for training and testing?\n- The fidelity metric defined in Eq. (10) is unclear: the output of the feature extractor $\\Psi$ should be the embedding, then what is the meaning of the subscript $y_i$? Presumably, it should be based on the prediction accuracy or probability (e.g. output of the classifier $\\xi$) as in [1].\n- The reported evaluation metric in Table 1 should be explained in the title to avoid confusion: for BA-2Motif and BA-Shape datasets, the metric is accuracy.\n- In section 2, “donate” -> “denote”\n\n[1] Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey. arXiv preprint arXiv:2012.15445, 2020b.\n\n", "strength_and_weaknesses": "**Strength**\n- Using motifs as explanations is a new and motivating idea\n- The proposed algorithm is simple and effective\n- The writing is easy to follow\n\n**Weaknesses**\n- The method heavily relies on the quality of motif extraction rules, whose complexity should also be discussed\n- Some details need to be explained as commented in my summary\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject