Rethinking the Explanation of Graph Neural Network via Non-parametric Subgraph Matching
Authors: Fang Wu
Lirong Wu
Siyuan Li
Dragomir Radev
Wenbing Huang
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph Neural Networks
Graph Matching
Explanation

Abstract: The great success in graph neural networks (GNNs) provokes the question about explainability: ``Which fraction of the input graph is the most determinant to the prediction?'' However, current approaches usually resort to a black-box to decipher another black-box (i.e., GNN), making it difficult to understand how the explanation is made. Based on the observation that graphs typically share some joint motif patterns, we propose a novel subgraph matching framework named MatchExplainer to explore explanatory subgraphs. 
It couples the target graph with other counterpart instances and identifies the most crucial joint substructure by minimizing the node corresponding-based distance between them. After that, an external graph ranking is followed to select the most informative substructure from all subgraph candidates. Thus, MatchExplainer is entirely non-parametric. 
Moreover, present graph sampling or node dropping methods usually suffer from the false positive sampling problem. To ameliorate that issue, we take advantage of MatchExplainer to fix the most informative portion of the graph and merely operate graph augmentations on the rest less informative part, which is dubbed as MatchDrop. 
We conduct extensive experiments on both synthetic and real-world datasets, showing the effectiveness of our MatchExplainer by outperforming all parametric baselines with large margins. Additional results also demonstrate that our MatchDrop is a general paradigm to be equipped with GNNs for enhanced performance.

Under review as a conference paper at ICLR 2022
RETHINKING THE EXPLANATION OF GRAPH NEU- RAL NETWORK VIA NON-PARAMETRIE SUBGRAPH MATCHING
Anonymous authors Paper under double-blind review
ABSTRACT
The great success in graph neural networks (GNNs) provokes the question about explainability: "Which fraction of the input graph is the most determinant to the prediction?" However, current approaches usually resort to a black-box to de- cipher another black-box (i.e., GNN), making it difficult to understand how the explanation is made. Based on the observation that graphs typically share some joint motif patterns, propose novel subgraph matching framework named MatchExplainer to explore explanatory subgraphs. couples the target graph with other counterpart instances and identifies the most crucial joint substructure by minimizing the node corresponding- based distance between them. After that, external graph ranking is followed to select the most informative substructure from all subgraph candidates. Thus. MatchExplainer is entirely paraameteri. Moreover, present graph sampling or node dropping methods usually suffer from the false positive sampling problem. To ameliorate that issue, we take ad advantage of MatchExplainer to fix the most informative portion of the graph and merely operate graph augmentations on the rest less informative part, which is dubbed as MatchDrop. We conduct extensive experiments on both synthetic and real-world datasets, showing the effectiveness of our MatchExplainer by outperforming all parametric baselines with large margins. Additional results also demonstrate that MatchDrop is general paradigm to be equipped with GNNs for enhanced performance.
INTRODUCTION
Graph neural networks (GNNs) have drawn broad interest due to their success for learning rep- resentations of graph-structured data, such as social networks (Fan et al. 2019), knowledge graphs (Schlichtkrull et al. 2018), traffic networks (Geng et al. 2019), and microbiological graphs (Gimmer et al.] 2017). Despite their remarkable efficacy, GNNs lack transparency as the easy for humans to comprehend. This prohibits practitioners
rationales of their predictions from not only gaining an understanding of the network characteristics, but correcting systematic patterns of mistakes made by models before deploying them in real-world applications.
Recently, extensive efforts have been devoted to studying the explainability of GNNs (Yuan et al. 2020). Researchers strive to answer the questions like "What knowledge of the input graph is the most dominantly important in the model's 's decision?" Towards this end, feature attribution and selec- al., 2017: Ancona al. 2017) a prevalent paradigm. They distribute the model's 8 outcome prediction to the input graph via gradient-like signals (Baldas-
tion (Selvaraju al., 20177; Sundararajan
sarre & Azizpour 2019 Pope et al.) 2019) Schnaak et al.] 2020), mask or attention scores (Ying
et al.
[0119] Luo al. (2220,, prediction changes on perturbed features (Schwab & Karlen 2019 Yuan et al. 202 ), and then choose a salient substructure as the explanation.
network to parameter- ize the generation process of explanations (Vu Thai 2020 Wang et al., (021b). We argue that depending another black-box to comprehend the prediction of the target black-box (i.e., GNNs) sub-optimal, since the behavior of those explainers is hard to interpret. These black-boxes in- deed, always fail to give clue of how they find proper explanatory subgraphs. In contrast, decent
Nonetheless, the latest approaches are all deep learning-bact based and rely

---

Under review as a conference paper at ICLR 2022
explainer ought to provide clear insights of how it captures and values this substructure. Other- wise, a lack of interpretability in explainers can undermine our trust in them. Moreover, some prior works (Chen et al. 2018: Ying al.) 2019; Yuan et al.] 202T) independently excavate explanations for each instance without explicitly referring to other training data in the inference phase. They ignore the fact that different essential subgraph patterns are shared by different groups of graphs, which can be the key to decipher the decision of GNNs. These frequently occurred motif's usually contain rich semantic meanings and indicate the characteristies of the whole graph instance (Hender- son et al. Zhang et al. 2020, Baajaade et al. (02T). For example, the hydroxide group (-OH) in small molecules typically results in higher water solubility, and the pivotal role of functional groups has also been proven in protein structure prediction (Senior et al. 2020).
To overcome these drawbacks, we propose to mine the explanatory motif in a subgraph matching manner. In contrast to a learnable network, we design non-parametric algorithm dubbed MatchEx- plainer with no need for training, which is composed of two stages. At the first stage, marries the target graph iteratively with other counterpart graphs and endeavors to explore the most crucial joint substructure by minimizing the node corresponding- -based distance in the high-dimensional feature space. Since the counterpart graphs diverse, the explanations at the first stage of MatchExplainer can be non non-unique for the same instance. Thus, an external graph ranking technique is followed as the second stage of MatchExplainerr to pick out the most appropriate one. To be explicit, it examines the important role that these substructures plays in determining the graph property by subtracting the subgraphs from the original input graph and testing the prediction of the remaining part.
Our MatchExplainer not only shows great potential in fast discovering the explanations for GNNs, but also can be employed enhance the traditional graph augmentation methods. Though exhibiting strong power in preventing over-fitting and over-smoothing, present graph sampling or node drop- ping mechanisms suffer from the false positive sampling problem. That is, nodes or edges of the most informative substructure are accidentally dropped or erased but the model is still required to forecast the original property, which can be misleading. To alleviate this obstacle, we take advantage of MatchExxpainer and introduce simple technique called MatchDrop. Specifically, it first digs out the explanatory subgraph by means of MatchExplainer and keeps this part unchanged. Then the graph sampling node dropping is implemented solely on the remaining less informative part. As a consequence, the core fraction of the input graph that reveals the label information is not affected and the false positive sampling issue is effectively mitigated.
To summarize, we are the foremost to investigate the explainability of GNNs from the perspective of non-parametric subgraph matching to the best of our knowledge. Extensive ex experiments synthetic and real-world applications demonstrate that our MatchExplainer can find the explanatory subgraphs fast and accurately with state-of-the-ar performance. Apart from that, we empirically show that our MatchDrop can serve as an efficient way to promote the graph augmentation methods.
2 PRELIMINARY AND TASK DESCRIPTION
In this section, we begin with the description of the GNN explanation task and then briefly review the relevant background of graph matching and mutual information theory.
Explanations for GNNs. Let fy denote a well-trained GNN to be explained, which gives the pre- diction 0G of the input graph G to approximate the ground-truth label yg. Without loss of generality, we consider the problem of explaining graph classification task (Ying et al. 2019) Yuan et al.) 2020 as to find an explainer fs that discovers the subgraph Gs from input graph G by:
arg min R(fv fs(g), 99), f.t.)f((()) < K,
where R(::)) is the risk function, which is usually implemented as a cross-entropy (CE) loss or a mean squared error (MSE) loss, and . returns the graph size (namely the number of nodes in this paper), and K a prefixed constraint.
Graph Matching, As a classic combinatorial problem, graph matching is known to be NP- hard (Loiola et al.) 2007). Addressing it requires expensive, complex, and impractical solvers, hence plenty of inexact but practical solutions (Wang et al. 2020) have been proposed. Given two different
2

---

Under review as a conference paper at ICLR 2022
graphs 91 (V1, and G2 (V2, Eg) with N1 and N₂ nodes respectively, the matching between them can be generally expressed by the quadratic assignment programming (QAP) form (Wang et al. 2
arg min vee vee(T) Kvee( s.L., T1 = 1= (0,11)
where T is a binary permutation matrix encoding node correspondence, and 1 denotes a column vector with all elements to be one. K E RMxX; is the so-called affinity matrix (Leordeanu & Hebert 2005), whose elements encode the node-to-node affinity between 91 and G2.
Mutual Information. Indeed, Eq. is equivalent to maximizing the mutual information between and Gs. Namely, the goal of an explainer is derive a small subgraph Gs such that:
arg max GuC KSK
fy
where ((:+) refers the Shannon mutual information between random variables. Notably, instead of merely optimizing the information hidden in 9s. another line of research (Yuan et al. 2021 seeks to reduce the mutual information between the subtracted subgraph Gs and G, i.e.
arg min T(Jr (g 9s); (g))).
(4)
3 THE MATCHEXPLAINER APPROACH
In this section, we first introduce the formulation of our MatchExppaineer approach from the perspec- tive of mutual information maximization. We then divide the maximization objective into two parts, one addressed by a graph matching algorithm, and the other one tackled by subgraph ranking.
3.1 FORMULATION OF MATCHEXPLAINER
The core idea of MatchExplainer is to jointly optimize the two objectives Eq. and Eq. as:
arg max (Grr (g) (G Gs); (G))
(5)
Gs @sCkkK
which is able to ensure the sufficiency (the first term) and necessity (the second term) of the placement of G with its subgraph Gs. However, this problem nontrivial to solve owing to the exponential complexity of searching the desirable subgraph. Recent methods (Yuan al. [02T 2020 Wang et al., 2021b) employ another black-box GNN f9( to output 9s. As mentioned be- fore, such type of methods encounter the irrationality of pursuing explainability via unexplainable models.
Instead of solving Eq. directly we reduce it into surrogate task with the aid of external graphs. Particularly, we fetch another graph G' that shares the same predicted property as G (i.e., 9c = 90 ) and then extract the most relevant part between G and g' as the candidate Gs. We will go through all possible G's, and locate the one giving the largest mutual information. In form, we derive:
arg max g'elo.S'+g
arg max (Gsr GsCG.
-900 (s):
(6)
where Dg == (g' ygr yg } denotes the set of graphs sharing the same label G. We define the optimal solution of Eq. 5 as G3., and immediately have the following proposition:
Proposition 1 there exists g' E DG satisfying fr())) fy (9'), then Problem is equivalent to &
We further divide Problem into two subtasks:
Subgraph Matching: Given any external graph G we derive the most relevant subgraph GG()") by Gs(G") = arg maxgecç. (Gs): (y:s))yy(("))) (g') (9)). Note that with the reference of G". is efficient derive (g')") by applying a graph matching algorithm. We provide more details in 3.2

---

Under review as a conference paper at ICLR 2022
External Graph Ranking: Different external graph G' corresponds different subgraph (s(G') returned by the last sub-problem. We choose the one that gives the smallest mutual information, that is 93 arg a [(fv(G Gs()")); (G)).. The details are given
in $ 3.3
Although modeling Problem c as the two subtasks above approximate the exact solution to some extent, we find in our experiments that they are sufficient to derive promising performance.
3.2 SUBGRAPH MATCHING MECHANISM
To begin with, we break the target GNN by into two consecutive parts: by = ÔG o Φx. where dG is the aggregator to compute the graph-level representation and predict the properties, and Øx is the feature function to update both the node and edge features. For a given graph G with node features h; E vv Vi E V and edge features Cij E R,",, ,(i, E &, the renewed output calculated as Ree (eiyh(i.)e = Øx ((hi (eis ((.))E)))))) which is forwarded into og afterwards.
Our target is to find subgraphs Gs C 9 and I's C G' both with K nodes to maximize distance de substitution
I(fy (9s): fr (9%)). Here utilize the node correspondence-base for measuring the mutual information between Gg and Gyg, which is minimized as follows:
(T, (T.Dox)) 9sC9.9' (Tel(Ss.9))
min (c(Ss,9')) = GaCo.9 c9
min
min
(7)
where D is the matrix of all pairwise distances between node features of 9s and G'z. Its element is calculated as D = (b', h() Vi E V.j V" where dx is the standard vector space similarity such as the Euclidean distance and the Hamming distance. The inner optimization is conducted over II,.,.), which is the set of all matrices with prescribed margins defined as:
IGs, 9's) = (T e (0. KxK T1 1,
T
Due to the NP-hard nature of graph matching Loiola al.) 2007 we adopt the greedy strategy to optimize dG 9's) and attain the subgraph Gs. It is worth noting that the greedy algorithm does not guarantee to reach the globally optimal solution (Bang-Jensen et al. (2004). but can yield locally optimal solutions in a reasonable amount of time. After that, we feed Gs into by and examine its importance. If by (Gs) = (g), then Gs is regarded as the potential explanations. Otherwise, Gs is abandoned since cannot recover the information required by hy to predict G.
is worth noting that our excavation of explanations through subgraph matching is significantly dif- ferent from most traditional graph matching methods. The majority of graph matching algorithms (Zanfir& & Sminchisescu 20018 [arlin et al., [0200] Wang et al. 2020 2021a) typically establish node correspondence from whole graph G1 another whole graph G2- However, we seek to construct partial node correspondence between the subgraph of G1 and the subgraph of Gz. Besides, most cur- rent graph matching architectures (Zanfir & Sminchisescu, 2018 Li al. 2019 Wang al. 2020)] Papakis et al. 2020 Liu et al. 2021a) are deep sermingg-bssed. They utilize a network to forecast the relationship between nodes or graphs, which has several flaws. For instance, the network needs tremendous computational resources to be trained. More importantly, its effectiveness is unreliable and may fail in certain circumstances if the network is not delicately designed. To overcome these limitations, we employ non-parametric subgraph matching paradigm, which is totally training- free and fast to explore the most informatively joint substructure shared by any pair of input instances.
3.3 EXTERNAL GRAPH RANKING
Since our MatchExplainer able to discover a variety of possible explanatory subgraphs via sub- graph matching, how to screen out the most informative one becomes critical issue. In this subsec- tion, we introduce the external graph ranking mechanism to sort out the optimal explanation. Ide- ally, g' ought to share the exact same explanatory substructure with G, i.e., max ((fy-Gs)); fr Meanwhile, g (-'s(g') should be independent to the property of the input graph, i.e., min I(fy (g (s()")); fy (G)). Therefore, there two distinct principles for selecting the counterpart graphs The first line is to seek G' that has as close the explanatory subgraph as possible to G. The second line is to ensure that G- Gs maintains little information relevant to the original property (g)
4

---

Under review as a conference paper at ICLR 2022
Nevertheless, without sufficient domain knowledge regarding which substructure is majorly respon- sible for the graph property, would be impossible for us to manually select the counterpart graph g' that satisfies Gs G'g. As remedy, the node correspondence- based distance dg (9s. 9's) can be treated as the indicator for whether this pair of graphs enjoy a similar explanatory substructure.
Though dg(9s. )'s) is feasible criterion to filtrate the most informative substructure, a more effi cient way is to immediately minimize the mutual information between g 95 and G. This corre- sponds decrease [(fr Gs): (g) in Equ. 6 Towards this goal, remove the extracted subgraph Gs from G and aspire to confuse GNNs' predictions on the remaining part g - Gs. Math- ematically, the optimal G' maximizes the difference between the prediction of the whole graph and the prediction of the graph that is subtracted by Gs. In other words, we wish to maximize:
(g hy) = hy (9) n (g Gs(g"))
(9)
where ot is the ground truth class of G and Gs is the substructure via subgraph matching with G'.
Then given any graph G and a reference graph set DR = ...,... Gn we acquire all possible subgraphs via matching to available graphs DR. Notably, not all graphs in DR are qualified counterparts. There are several intuitive conditions that the counterpart graph G' has to satisfy. First, and g' should belong to the same category predicted by hy. Besides, g' needs to have at least K nodes. Otherwise, Gs would be smaller than the given constrained size. After the pairwise subgraph matching, we calculate their corresponding Ag(., hy) and pick up the one that leads to the largest (y) as the optimal counterpart graph.
Effectiveness vs. efficiency. The time-complexity is always an important topic evaluate the practicability of explainers. For our MatchExplainer, the size of the reference set, i.e., [Dxl plays vital role determining the time cost. However, a limited number of counterpart graphs can also prohibit it from exploring better explanatory subgraphs. Thus, it is non-trivial to balance the effectiveness and efficiency of MatchExplainer by choosing an appropriate size of DR.
THE MATCHDROP METHODOLOGGY
Preventing the false positive sampling. Deep graph learning faces unique challenges such as feature data incompleteness, structural data sparsity, and over-smoothing To address these issues, a growing number data augmentation techniques (Hamilton et al.) 2017 Rong et al., 2019) have been proposed in the graph domain and shown promising outcomes. Among them, the graph sam- pling and node dropping (Feng et al., 2020 Xu et al. 2021) are two commonly used mechanisms. However, most previous approaches are completely randomized, resulting in false positive sam- pling and injecting spurious information into the training process. For instance, 1.3-dinitrobenzene (C,H,,,O,,) is mutagen molecule and its explanation is the NO, groups (Debnath et al. 1991). If any edge or node of the NO, group is accidentally dropped or destroyed, the mutagenicity property no longer exists. And it will misguide GNNs if the original label is assigned to this molecular graph after node or edge sampling.
To tackle this drawback, recall that our MatchExplainer offers a conve- nient way discover the most es- sential part of a given graph. It natural to keep this crucial por- tion unchanged and only drop nodes or edges in the remaining portion. Based on this idea, we propose simple but effective method dubbed MatchDrop, which keeps the most in- formative part of graphs found by our MatchExplainer and alters the less in- formative part (see Figure [].
Example: C,H,N,O,
Approaches
Result
Porturbation
Provious Graph Sempling Methods (Comoletcly random porturbation))
leads false positive sampling and does the
MatchCrop (ours)
The informative remains postive sampling forbicden.
(Keep unchanged)
Figure 1: The illustration of our proposed MatchDrop.
The procedure of our MatchDrop is described as follows. To begin with, we train a GNN hy for several epochs until converges to an acceptable accuracy, which guarantees the effectiveness of the subsequent subgraph selection. Then
5

---

Under review as a conference paper at ICLR 2022
for each graph G in the training set Durin- randomly select another graph g' Duain with the same class as the counterpart graph. Afterwards, we explore its subgraph Øs via MatchExplainer with retaining ratio p (i.e., [Ss| = plğ') and use it as the model input to train hy.
Notably, similar to the typical image augmentation skills such as rotation and flapping (Shorten & Khoshgoftaar 2019), MatchDrop is novel data augmentation technique for GNN training. How- ever, instead of augmenting G randomly, MatchDrop reserves the most informative part and only changes the less important substructure. This significantly reduces the possibility of false positive sampling. Additionally, unlike other learnable mechanisms to inspect subgraphs, our MatchDrop is entirely parameter-free and, therefore, can be deployed at any stage of the training period.
Training objective. The training of GNNs is supervised by the cross entropy (CE) loss. Suppose there are M classes in total, then the loss takes the following form:
Ls
Σ ug log (hy (hs(9,
(10)
Irain
GEDiii
where (.) indicates the predicted probability of Gs to be of class e and yg is the ground truth value. hy employs MatchExplainer to mine the subgraph 9s by matching 9 randomly selected counterpart graph G" in the training set Draain with pre-defined ratio p.
EXPERIMENTAL ANALYSIS
5.1 DATASETS AND EXPERIMENTAL SETTINGS
Following Wang et al. 20211b, use four standard datasets with various target GNNs.
Molecule graph classification: MUTAG (Debnath al. 1991 Kazius et al. 2005) a molecular dataset for the graph classification problem. Each graph stands for molecule with nodes for atoms and edges for bonds. The labels are determined by their mutagenic effect on a bacterium. The well-trained Graph Isomorphism Network (GIN) Xu 2018) has approximately achieved a 82% testing accuracy.
Motif graph classification. Wang et al. (2021b) create synthetic dataset, BA-3Motif, with 3000 graphs. They take advantage of the Barabasi-Alben (BA) graphs as the base, and attach each base with one of three motifs: house, cycle, grid. We train an ASAP model (Ranjan et al. 2020) that realizes 99.75% testing accuracy.
Handwriting graph classification: Knyazev et al. (2019) transforms the MNIST images into 70K superpixel graphs with at most 75 nodes for each graph. The nodes are superpixels, and the edges are the spatial distances between them. There are 10 types of digits the label. We adopt Spline-based GNN (Fey et al.) 2018) that gains around 98% accuracy in the testing set.
Scene graph classification: Wang et al. (202lb) select 4443 pairs of images and scene graphs from Visual Genome (Kiishna et al. (017) to construct the VG-5 dataset (Pope et al. 2019). Each graph is labeled with five categories: stadium, street, farm, surfing and forest. The regions of objects are represented as nodes, while edges indicate the relationships between object nodes. We train AAPNP (Klicpera et al.) 2018) that reaches 61.9% testing accuracy.
We compare our MatchExplainer with several state-of-the-art and popular explanation baselines, which are listed below:
SA (Baldassarre & Azizpour 2019) directly uses the gradients of the model prediction with re- spect to the adjacency matrix of the input graph as the importance of edges.
Grad-CAM (Selvaraju et al. [2017] Pope et al. 2019) uses the gradients of any target concept such the motif in graph flowing into the final convolutional layer produce coarse localization map highlighting the important regions in the graph for predicting the concept.
GNNExplainer (Ying et al. 2019) optimizes soft masks for edges and node features to maximize the mutual information between the original predictions and new predictions.

---

Under review as a conference paper at ICLR 2022
Table 1: Comparisons of our MatchExplainer with other baseline explainers.
MUTAG ACC-AUC
VG-5
MNIST ACC-AUC
BA-3Motif
ACC-AUC
ACC-AUC
Recall 5
SA
0.769
0.769
0.559
0.518
0.243
Brad-CAM
0.786 + 0.011
0.909 + 0.005
0.581 = 0.009
0.533 + 0.003
0.212 : 0.002
GNNExplainer
0.895 + 0.010
0.895 0.003
0.535
0.528 + 0.005
0.157 = 0.002
PG-Explainer
0.631 + 0.008
0.700
0.010
0.586 0.004
0,293 0.001
-ip--xplainer
0.714 0.007
0.792 0.001
1615=00000
0.575 + 0.002
0.250 + 0.000
ReFine
0.955 + 0.005
0.914 + 0.001
0.636 + 0.003
0.576 + 0.013!
0.297 + 0.000'
Matchnxplainer
0.997
0.993
0.938
0.634
0.305
Relative Impro
4.5%
8.6%
48.9%
8.1%
2.6%
PGExplainer (Luo al., 2020) hires a parameterized model to decide whether edge is impor- tant, which is trained over multiple explained instances with all edges.
PGM-Explainer (Vu & Thai 2020) collects the prediction change on the random node perturba- tions, and then learns Bayesian network from these perturbation--preiitin observations, so as to capture the dependencies among the nodes and the prediction.
Refiner (Wang al., 2021b) exploits the pre-training and fine-tuning idea develop multi- grained GNN explainer. It has both a global understanding of model workings and local insights on specific instances.
As the ground-truth explanations are usually unknown, it is tough to quantitatively evaluate the excellence of explanations. There, follow Wang et al. (2021b) and employ the predictive accu- racy (ACC@p p) and Recall N as the metrics. Specifically, ACC@, p measures the fidelity of the explanatory subgraphs by forwarding them into the target model and examining how well it recovers the target prediction. ACC-AUC is reported as the area under the ACC curve over different selec- tion ratios p E f0.1, 0.2, .... 1.0). Recall N is computed Eg [|G, n ngll [93ll, where g is the ground-truth explanatory subgraph. Remarkably, Recall@ N is only suitable for BA3-motif, since this dataset is synthetic and the motifs are foregone.
5.2
CAN MATCHEXPLAINES FIND BETTER EXPLANATORY SUBGRAPHS?
5.2.1
QUANTITATIVE EVALUATIONS
To investigate the effectiveness of MatchExplainer, we conduct broad experiments on four datasets and the comparisons are reported Table [ For MUTAG, VG-5, and BA3-Motif, we exploit the whole training and validation data the reference set. For MNIST, we randomly select 10% available samples as the reference set to speed up matching. It can be found that MatchExplainer outperforms every baseline in all cases. Particularly, previous explainers fail to explain GNNs well in MNIST with ACC-AUCs lower than 65%, but MatchExplainer can reach as high as 93.8%. And use the whole training and validation data in MNIST as the reference, its ACC-AUC can increase to 97.2%. This phenomenon demonstrates the advantage of subgraph matching in explaining GNNs when the dataset has clear patterns of explanatory subgraphs. Additionally, MatchExplainer also achieves significant relative improvements over the strongest baseline by 8.6% and 8. 1% in VG-5 and BA3-Motia respectively.
Furthermore, it is also worth noting that MatchExplainer realizes nearly 100% ACC-AUCs in each task but BA-3Motif. For BA-3Motif, we find that its predictive accuracy are [0.31, 0.31, 0.31, 0.34, 0.49, 0.71, 0.97, 1.0, 1.0, 1.0) with different selection ratios. This aligns with the fact that most motifs in this task occupy large fraction of the whole graph. Once the selection ratio is greater than 0.7, MatchExplainer is capable of figuring out the correct explanatory subgraph.
We visualize the explanations of MatchExplainer on MUTAG in Appendix B for qualitative evalua- tions.
'These results reproduced
7

---

Under review as a conference paper at ICLR 2022
Table 2: Efficiency studies of different methods (in seconds).
Method
Phase
MUTAG
VG-5
MNIST
BA-3Motif
Training
186.0
1127.2
1135.4
66.1
GNNexplainer
Inference (per graph)
1.290
0.565
0.732
0.517
Training Inference (total)
703.4
1644.6
1782.1
271.6
Training
186,3
286.3
1154.1
112.4
PG-Explainer
Inference (per graph)
0.056
0.094
0.025
0.020
Training Inference (total)
208.6
309.5
1162.1
120.4
Training
1191.6
1933.3
5025.8
763.0
Refine
Inference (per graph)
0.068
0.107
0,026
0.027
Training Inference (total)
1218.9
1959.7
5051.2
773.8
Training
MatchExplainer
Inference (per graph)
0.485
0.732
0,682
7.687
Training Inference (total)
194.6
180.3
667.8
3052.
5.2.2 EFFICIENCY STUDIES
We compute the average inference time cost for each dataset with different methods to obtain ex- planations of single graph. We also count the overall training and inference time expenditure, and summarize the results in Table 2 Specifically, we train GNNExplainer and Ex-plaiieeer for 10 epochs, and pre-train Refine for 50 epochs before evaluation. can observed that though prior approaches enjoy fast inference speed, they suffer from long-term training phases. As an alternative, our MatchExplainer completely training-free When comparing the total time, MatchExplainer is the least computationally expensive in MUTAG, VG-5 and MNIST. However, most motifs in BA-3Motif are large-size, MatchExplainer has to traverse a large reference set to obtain appropriate counterpart graphs, which unavoidably results in spending far more time.
5.3 CAN MATCHDROP GENERALLY IMPROVE THE PERFORMANCE OF GNNs?
5.3.
IMPLEMENTATIONS
We take account of two backbones: GCN (Kipf & Welling 2016). and GIN (Xu al. 2018 with a depth of 6. Similar to Rong et al. (2019), we adopt random architecture to enable more robust comparisons. There, DropNode stands for randomly sampling subgraphs, which can be also treated as specific form of node dropping. FPDrop is the opposite operation of our MatchDrop, where the subgraph sampling or node dropping is only performed in the explanatory subgraphs while the rest remains the same. We add FPDrop as baseline to help unravel the reason why MatchDrop works. PGDrop similar to MatchDrop, but uses fixed PGExplainer (Luo al. 2020) to explore the informative substructure. The selection ratios p for FPDrop, PGDrop, and MatchDrop are all set as 0.95.
search for each
5.3.2 OVERAL. RESULTS
Table documents the performance on all datasets except BA-3Motif, since its testing accuracy has already approached 100%. It can be observed that MatchDrop consistently promotes the testing accuracy for all cases. Exceptionally, FPdrop imposes a negative impact over the performance of GNNs. This indicates that false positive sampling does harm to the conventional graph augmentation methods, which can be surmounted by our MatchDrop effectively. On the other hand, PGDrop also gives rise to the decrease of accuracy. One possible reason is that parameterized explainers like PGExplainr are trained on samples that GNNs predict correctly, so they are incapable to explore explanatory subgraphs unseen graphs that GNNs forecast mistakenly.
8

---

Under review as a conference paper at ICLR 2022
Table 3: Testing accuracy (%) comparisons on different backbones with and without MrtchDrop.
Dataset
Backbone
Original
FPDrop
DropNode
PGDrop
MatchDrop
GCN
0.828 + 0.004
0.803 + 0.017
0.832 + 0.008
0.825 + 0.02
0.844:00.006
MUTAG
GIN
0.832 = 0.003
0.806 = 0.020
0.835 + 0.009
0.828 = 0.01
0.845:1.0007
GCN
0.619 + 0.003
0.587 + 0.014
0.623 + 0.007
0.604 + 0.002
0.638+0.008
VG-5
GIN
0.621 + 0.004
0.593 + 0.018
0.622 + 0.006
0.600 + 0.004
0.630+0.000
GCN
0.982 + 0.001
0.955 + 0.008
0.982 + 0.002
0.975 + 0.003
0.986110.022
MNIST
GIN
0.988 = 0.001
0.959 = 0.005
0.989 + 0.001
0.979 + 0.002
0.990=00000
6 RELATED WORK
6.1 EXPLAINABILITY OF GNNS
Though increasing interests have been appealed in explaining GNNs, the study in this area is still insufficient compared to the domain of images and natural languages. Generally, there are two research lines. The widely-adopted one is the parametric explanation methods. They run pa- rameterized model to dig out informative substructures, such as GNNExplainer (Ying et al. 2019). PGExxlainer (Luo al. 2020), and PGM-Explainer (Vu & Thai 2020). The other line is the non- parametric explanation methods, which employ heuristics like gradient- like scores obtained by back- propagation as the feature contributions (Baldassarre & Azizpour 2019 Pope et al. (209)] [Schnake et al. 2020). Nevertheless, the latter usually shows much poorer results than the former parametric methods. In contrast, our MatchExplainer procures state-of-the-art performance astonishingly.
6.2 GRAPH AUGMENTATIONS
Data augmentation has recently attracted growing attention in graph representation learning to counter issues like data noise and data scarcity (Zhao et al. (022). The related work can be roughly broken down into feature-wise (Zhang et al. 2017; Liu et al. 2021b lb: Taguchi et al. 2021). structure- wise (You et al.] 2020; IZhao et al. 2001b). and label-wise (Verma et al. 2019) categories based on the augmentation modality (Ding et al. 2022). Among them, many efforts are raised to augment the graph structures. Compared with adding or deleting edges (Xu et al. (022). the augmentation operations on node sets are more complicated. A typical application is promote the propagation of the whole graph by inserting supernode (Gilmer et al., (017)). while Zhao et al. (2021a) interpolate nodes to enrich the minority classes. On the contrary. some implement graph or subgraph sampling by dropping nodes for different purposes, such as scaling up GNNs (Hamilton et al. 2017). en- abling contrastive learning (Qiu et al.) 2020), and prohibiting over-fitting and over-smoothing (Rong et al. 2019). Nonetheless, few of those graph sampling or node dropping approaches manage to find augmented graph instances from the input graph that best preserve the original properties.
CONCLUSION
This paper proposes a subgraph matching technique called MatchExplainer for GNN explanations. Distinet from the popular trend of using parameterized network that lacks interpretability, de- sign a non-parametric algorithm to search for the most informative joint subgraph between a pair of graphs. Furthermore, show its great capacity in ameliorating the false positive sampling challenge. Experiments convinc- ingly demonstrate the efficacy of our MatchExplainer by winning over parametric approaches with significant margins.
combine MatchExplainer with the classic graph augmentation method and
REFERENCES
Marco Ancona, Enea Ceolini, Cengiz Öztireli, and Markus Gross. Towards better understanding of gradient-bast attribution methods for deep neural networks. arXiv preprint 10I.vv1711.06100 2017.

---

Under review as a conference paper at ICLR 2022
Federico Baldassarre and Hossein Azizpour. Explainability techniques for graph convolutional net- works. arXiv preprint arXiv: 13686, 2019.
Jørgen Bang-Jensen, Gregory Gutin, and Anders Yeo. When the greedy algorithm fails. Discrete optimization, 1(2):211-27, 2004.
Huta R Banjade, Sandro Hauri, Shanshan Zhang, Francesco Ricci, Weiyi Gong, Geoffroy Hautier, Slobodan Vucetic, and Qimin Yan. Structure motif-centric learning framework for inorganic crystalline systems. Science advances, 7(17)ceab1175, 2021.
Jianbo Chen, Le Song, Martin Wainwright, and Michael Jordan. Learning explain: An nnformation-theoretii perspective on model interpretation. International Conference on Ma- chine Learning, pp. 883-892. PMLR, 2018.
Asim Kumar Debnath, Rosa Lopez de Compadre, Gargi Debmath, Alan Shusterman, and Cor- win Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro com- pounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):786-777, 1991.
Kaize Ding, Zhe Xu, Hanghang Tong, and Huan Liu. Data augmentation for deep graph learning: A survey, arXiv preprint rxXi:22022.08335. 2022.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The world wide web conference, pp. 417-426, 2019.
Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural networks for semi-supervised learning on graphs. Advances in neural information processing systems, 33:22092 -21003, 2020.
Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Heinrich Müller. Splinecnn: Fast geomet- ric deep learning with continuous b-spline kernels. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 869-877, 2018
Xu Geng, Yaguang Li, Leye Wang, Lingyu Zhang, Qiang Yang, Jieping Ye, and Yan Liu. Spatiotem- poral multi multi-graph convolution network for ride-hailing demand forecasting. Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 3656-3663, 2019.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263-1272. PMLR, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Keith Henderson, Brian Gallagher, Tina Eliassi-Rad, Hanghang Tong, Sugato Basu, Leman Akoglu, Danai Koutra, Christos Faloutsos, and Lei Li. Rolx: structural role extraction & mining in large graphs. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge dis- covery and data mining, pp. 1231-1238 2012.
Jeroen Kazius, Ross McGuire, and Roberta Bursi. Derivation and validation of toxicophores for mutagenicity prediction. Journal of medicinal chemistry, 48(1):312 -200, 2005.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.69880 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv:1609.02907, 2016.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810005997, 2018.
Boris Knyazev, Graham W Taylor, and Mohamed Amer. Understanding attention and generalization in graph neural networks, Advances in neural information processing systems, 32, 2019.
10

---

Under review as a conference paper at ICLR 2022
Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li, David A Shamma, et al. Visual genome: Connecting lan- guage and vision using crowdsoureed dense image annotations. International joternationaajouralll of computer vision, 123(1))32-73, 2017.
Marius Leordeanu and Martial Hebert. A spectral technique for correspondence problems using pairwise constraints. 2005.
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching net- works for learning the similarity of graph structured objects. In International conference PMLR, 2019.
machine learning, pp.
Linfeng Liu, Michael Hughes, Soha Hassoun, and Liping Liu. Stochastic iterative graph matching. In International Conference on Machine Learning, pp. 6815-6825, PMLR, 2021a.
Songtao Liu, Hanze Dong, Lanqing Li, Tingyang Xu, Yu Rong, Peilin Zhao, Junzhou Huang, and Dinghao Wu. Local augmentation for graph neural networks. arXiv preprint arXiv:2109.03855 2021b.
Eliane Maria Loiola, Nair Maria Maia de Abreu, Paulo Oswaldo Boaventura-Nett Peter Hahn, and Tania Querido. A survey for the quadratic assignment problem. European journal of operational research, 176(2)657-660. 2007.
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advances neural information pro- cessing systems, 11196662996111 2020.
loannis Papakis, Abhijit Sarkar, and Anuj Karpatne. Gennmatch: Graph convolutional neural net- works for multi-object tracking via sinkhorn normalization. arXiv preprint urXiv:2010.00067 2020.
Phillip E Pope. Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann. Ex- plainability methods for graph convolutional neural networks. In Proceedings the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 10772-10781, 2019.
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang. Gee: Graph contrastive coding for graph neural network pre-training. In Pro- ceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 1150-1160 1600, 2020.
Ekagra Ranjan, Soumya Sanyal, and Partha Talukdar. Asap: Adaptive structure aware pooling for learning hicrarchical graph representations. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp. 5470-5477, 2020.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint arXiv:1907.10903 2019.
Paul-Edouard Sarlin, Daniel DeTone, Tomasz Malisiewicz, and Andrew Rabinovich. Superglue: Learning feature matching with graph neural networks. In Proceedings of the IEEE/CVF confer- ence on computer vision and pattern recognition, pp. 4938-4947, 2020.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne den Berg, Ivan Titov, and Max Welling, Modeling relational data with graph convolutional networks. In European semantic web conference, pp. 593-607. Springer, 2018.
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 S0Niv::00000333888 2020.
Patrick Schwab and Walter Karlen. Cxplain: Causal explanations for model interpretation under uncertainty. Advances in Neural Information Processing Systems, 32, 2019.

---

Under review as a conference paper at ICLR 2022
Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient- based local- ization. In Proceedings of the IEEE international conference on computer vision, pp. 618-626, 2017.
Andrew W Senior, Richard Evans, John Jumper, James Kirkpatrick, Laurent Sifre, Tim Green, Chongli Qin, Augustin Zidek, Alexander WR Nelson, Alex Bridgland, et al. Improved protein structure prediction using potentials from deep learning. Nature, 577(7792):70--710, 2020.
Connor Shorten and Taghi M Khoshgoftaar. A survey on image data augmentation for deep learning. Journal of big data, 6(1):1-48, 2019.
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In International conference on machine learning. pp. 3319-3313330 -3288. PMLR, 2017.
Hibiki Taguchi, Xin Liu, and Tsuyoshi Murata. Graph convolutional networks for graphs containing missing features. Future Generation Computer Systems, 117:155-168, 2021.
Vikas Verma, Alex Lamb, Christopher Beckham, Amir Najafi, Ioannis Mitliagkas, David Lopez- Paz, and Yoshua Bengio. Manifold mixup: Better representations by interpolating hidden states. In International Conference on Machine Learning, pp. 6448-6447. PMLR, 2019.
Minh Vu and My T Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. Advances in neural information processing systems, 33:1 22255-12222 2020.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Learning combinatorial embedding networks for deep graph matching. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 1566-0065, 2019.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Combinatorial learning of robust deep graph matching: an embedding based approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
Runzhong Wang. Junchi Yan, and Xiaokang Yang. Neural graph matching network: Learning lawler's s quadratic assignment problem with extension to hypergraph and pattiple-grahh match- ing. IEEE Transactions Pattern Analysis and Machine Intelligence, 2021a.
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, 2021b.
Dongkuan Xu, Wei Cheng, Dongsheng Luo, Haifeng Chen, and Xiang Zhang. Infogel: Information- aware graph contrastive learning. Advances in Neural Information Processing Systems, 34, 2021.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826 2018
Zhe Xu, Boxin Du and Hanghang Tong. Graph sanitation with application to node classification. In Proceedings of the ACM Web Conference 2022, pp. 1136-1147, 2022.
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32, 2019.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in Neural Information Processing Systems, 03:5812-5823,, 2020.
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey. arXiv preprint arXiv:2012.15445, 2020.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neu- ral networks via subgraph explorations. In International Conference on Machine Learning, pp. 12241-12252. PMLR, 2021.
12

---

Under review as a conference paper at ICLR 2022
Andrei Zanfir and Cristian Sminchisescu. Deep learning of graph matching. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2684-2693 2018.
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. arXiv preprint arXiv: 2017.
Shichang Zhang, Ziniu Hu, Arjun Subramonian, and Yizhou Sun. Motif-driven contrastive learning of graph representations. arXiv preprint 2tti::20022//25533 2020.
Tianxiang Zhao, Xiang Zhang, and Suhang Wang. Graphsmote: Imbalanced node classification graphs with graph neural networks. Proceedings of the 14th ACM international conference on web search and data mining, pp. 833 841, 2021a.
Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data aug- mentation for graph neural networks, In Proceedings of the AAAI Conference on Artificial Intel- ligence, volume 35, pp. 11015-11023, 2021b.
Tong Zhao, Gang Liu, Stephan Günnemann, and Meng Jiang. Graph data augmentation for graph machine learning: A survey, arXiv preprint 22xi::202.088777 2022.
13

---

Under review as a conference paper at ICLR 2022
A EXPERIMENTAL DETAILS
Explaining GNNs. All experiments are conducted on a single A100 PCTE GPU (40GB). For the parametric methods containing GNNExplainer, PGExplainer, PGM-Explainer, and Refine, we use the reported performance in Wang el al. (2021b). Regarding the re-implementation of Refine in BA-3Motif, we use the original code with the same hyperparamters, and we adopt Adam opti- mizer (Kingma & Ba 2014) and set the learning rate of pre-training and fine-tuning as 1e-3 and le-4, respectively.
Graph augmentations. All experiments are also implemented on single A100 PCIE GPU (40GB). We employ three sorts of different GNN variants (GCN, GAT, and GIN) to fit these datasets and verify the efficacy of various graph augmentation methods. We employ Adam optimizer for model training. For MUTAG, the batch size 128 and the learning rate is le-3. For BA3-Motif, the batch size is 128 and the learning rate is 1e-3, For VG-5, the batch size is 256 and the learning rate 0.5 le-3. We fix the number of epochs to 100 for all datasets.
B EXPLANATIONS FOR GRAPH CLASSIFICATION MODELS
In this section, we report visualizations of explanations Figure
Prediction:
Mutagenic
Prediction: Non- mutagenic
Figure 2: Explanatory subgraphs in Mutagenicity, where 50% nodes are highlighted.
14


Reviews:
[{"review_id": "_q6R80KVJS", "reviewer": "Reviewer_Xwid", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The paper deals with explainability of the predictions made by Graph Neural Networks. Most methods use a learning based approach to generate explanations for the GNN predictions. In this paper, the authors propose MatchExplainer, a non-parametric technique of finding the subgraph which best explains the predictions. In other words the subgraph which contains maximum information relevant to the target. For this, they use graph matching method of finding the common subgraphs between graphs on which GNNs give the same predictions. Furthermore, they use this subgraph to improve the graph augmentation techniques called MatchDrop. Experiments show that the proposed technique is useful and outperforms other deep learning based baselines on most datasets.\n", "summary_of_the_review": "Overall, exploring non-parametric methods for explainability of GNNs is interesting. However, the authors doesn’t seem to be proposing an efficient way of finding subgraphs between graphs with same labels. This is precisely the reason, why other methods use deep-learning based techniques. ", "strength_and_weaknesses": "### Strengths\n1. The motivation of the paper is clear and the problem being solved is very relevant.\n1. The addition of MatchDrop strengthens the paper with possible use for applications other than GNN explainability. \n1. Exploring non-parametric methods for GNN explainability is interesting.\n\n### Weaknesses\n1. Firstly, the authors mention that it is irrational to use deep learning based method to explain GNN predictions. I disagree with this. The explainability problem is mathematically formulated (as well in this paper) just needs to get the subgraph which is sufficient to predict the output. Any method, whether learning based or non-parametric, if able to solve this, that is a rational method to solve the problem. We don’t need the explaining method to be explainable itself.\n1. Rather than an algorithm, the method seems to be like a heuristic without much novelty. The main issue with non-learning based strategies for finding subgraphs is the complexity which is why learning based methods are promising.\n1. Furthermore, the greedy strategy used to find the subgraph is not well discussed. It is important since that is the part of finding the subgraph. How effective and efficient the method is needs to be discussed.\n1. Selecting subgraphs based only on node-correspondence distance is not properly motivated. Why should this give the best (or good enough) subgraph is not intuitive except that it may be easy to compute. Furthermore, even though there may be node similarities, it does not necessarily mean the corresponding subgraphs match. For example, two non-connected nodes may have high node-correspondence score but since they are not connected, it may not be a substructure which explains the prediction. This needs proper elaboration.\n1. The method is restricted to finding subgraphs to size K. What value of K is used and experiments ablating this value are not discussed and shown. How imp is the value of K is not clear.\n1. Why do we need to use the reference graph set? How do you decide the set of subgraphs in the reference set? Does it depend on the specific dataset used or can be general?\n1. The time complexity is also not properly studied. What exactly is the complexity of MatchExplainer in Big-O notation and how does it relate to other models is not properly discussed. \n1. Also in Table 2, training time is considered which is not very relevant. In terms of efficiency, we are mainly concerned with inference time. This is because, training is only one time whereas inference is relevant in deployment. Inference time is considerably higher compare to Refine and PG-Explainer.\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": "X-iKl7yYbq", "reviewer": "Reviewer_mQZh", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Main concern. Transform GCN explainability into subgraph-graph matching. \n\nProtocol for quantifying the explainability: “As the ground-truth explanations are usually unknown, it is tough to quantitatively evaluate the excellence of explanations. There, we follow Wang et al. (2021b) and employ the predictive accu- racy (ACC@ρ) and Recall@N as the metrics “. \nIt is clear how to apply the protocol to the proposed method (e.g. get the reported explainable subgraph and measure its accuracy). However, it is not clarified how the data in Table 1 is obtained for the baselines (my intuition is that you get the most explained edges and use them to check the accuracy, is that true?). This point is a bit clear for GNNEexplainer: “  They run a parameterized model to dig out informative substructures, such as GNNExplaine “. And for PG-Explainer. Please clarify the rest of the baselines. \n\nRecommendation. Please explore efficient graph matchers such as the “bypass graph matching - Entropic Alignment (SIAM Imaging Science)” as well as it associated mutual information between graphs (Pattern Recognition Letters). In this latter approach, an structural (spectral embedding is used to transform graph matching into point alignment). \n", "summary_of_the_review": "This is a nice paper in general, which contributes to a subgraph-graph method for elucidating explainability. The idea is fine since it suggests what parts of the structure are superfluous. As a result, the resulting substructure is more efficient. The results are fine though sometimes not clearly interpretable. ", "strength_and_weaknesses": "* Strengths. The idea of extracting informative subgraph is very interesting. Although this implies approximating a NP-hard problem, the experimental results show that greedy graph-subgraph matching is good enough. \n* Weaknesses: The protocol for quantifying explainability could be better clarified, but in general one can follow the paper. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "C4baoRiMT5", "reviewer": "Reviewer_ncDW", "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 to mine the explanatory motif in a subgraph-matching manner. Specifically, it investigates the explainability of GNNs from the perspective of non-parametric subgraph matching and proposes a novel method dubbed MatchExplainer. Moreover, it takes the advantage of MatchExplainer and introduces a simple technique called MatchDrop to enhance the traditional graph augmentation methods.", "summary_of_the_review": "Essentially, I think there is some promising work. However, I think it really needs a more reasonable motivation, better presentation, and richer analysis to be accepted for publication at a top-tier conference. Therefore, I am leaning on the negative side.", "strength_and_weaknesses": "Strength:\n- The overall idea of generating explanations via exploring common structure from the graphs belonging to the same class is well-conceived.\n- The proposed approach is well-designed and sounds.\n\n\nWeaknesses:\nThe paper comes with a number of weaknesses as well. The most serious one is:\n- The motivation is not convincing. This paper claims that the behavior of parametric explainers is hard to interpret since there are parametric. Thus depending on these black-box explainers to comprehend the prediction of the target black-box model is sub-optimal. It is the core motivation of this paper but I think: 1) parametric explainer is not hard to interpret. 2) even if the parametric explainer is hard to interpret, MatchExplainer still does not solve or remit this issue. To be more specific:\n    - The procedure of the post-hoc explainers like GNNExplainer, PGExplainer, PGMExplainer, CF-GNNExplainer, GraphMask, SubgraphX, Gem, Refine, RCExplainer and GSAT (in its post-hoc working mode) have scrupulously theoretical support and is not hard to interpret. For example, if the important feature is masked or deleted by GNNExplainer or Gem, the outcome will fluctuate markedly. All the motivations and operations are accessible. I do not think the inherent issue claimed by the authors is existing.\n\n- Note that MatchExplainer feeds the subgraph into the GNN model and selects the explanations based on the output.  Even if the parametric explainer is hard to interpret, the above operation inevitably brings MatchExplainer into the scope of “hard to interpret”, since taking $I(f(G_s), f(G))$ as the proxy of $I(G_s,G)$ introduces the black-box model $f$. That is, MatchExplainer is also a black box because it can not explain why $I(G_s,G)= I(f(G_s), f(G))$.\n\nIn a nutshell, if this paper only generates explanations via a more efficiently common subgraph/structure searching algorithm from the graphs belonging to one class, it really has a reasonable and novel motivation. \n\nOther less critical, but still major weaknesses are:\n- The paper is poorly structured. The part of “SUBGRAPH MATCHING MECHANISM” is wordy and the consistency of the part 3 and part 4 is poor. In a nutshell, I suggest that the paper should pay more attention to the part 3.2, not the part 4.\n- Another criticism of the paper is its writing. For example, it has GNNExplainer in Table 2 but GNNexplainer in Table 2.\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": "9CLkul7uni1", "reviewer": "Reviewer_aTNz", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 the explainability of graph neural networks (GNNs) using subgraph matching. The paper first identifies the limitation of most existing works, which is the usage of black-box explainer to generate explanatory subgraph. Based on that, the authors propose a matching-then-ranking framework named MatchExplainer to find the explanatory subgraph. Experimental results demonstrate the efficacy of the proposed method.", "summary_of_the_review": "The idea is interesting, but the writing is not satisfying. More rigorous justifications on its math are needed. The authors are expected to provide more details about the proposed method to avoid confusion.", "strength_and_weaknesses": "Strengths:\n- I like the idea of not using the black-box explainers.\n- The proposed method outperforms the baseline methods as shown by the experimental results.\n\nConcerns/Questions:\nMy general concern is that the work is heavily relying on mutual information while it is lack of rigorous justification. Please see my detailed concerns/questions below:\n- How is the equivalence between Eq. (1) and Eq. (3) established? My guess is that they are only equivalent under specific definition of risk function $\\mathcal{R}$. \n- For proposition 1, it would be nice if the authors could provide a rigorous proof (or at least proof sketch in the main body). I cannot find it either in the main body or the appendix.\n- In section 3.2, can we just simply disentangle GNN into two disjoint parts? In many GNNs (e.g., GCN, GAT), graph structure is an important part in learning node/edge features (i.e., $\\phi_X$ here) so it is hard to simply distangle them into the composition of $\\phi_G$ and $\\phi_X$. The authors may provide a few instantiations of $\\phi_G$ and $\\phi_X$ to avoid confusion.\n- Why is the node correspondance-based distance $d_G$ a good substitution of the multivariate mutual information?\n- Subgraph matching is not a new problem (see some references below). Some discussion on existing works of subgraph matching is needed.\n[1] Mongiovi, Misael, et al. \"Sigma: a set-cover-based inexact graph matching algorithm.\" Journal of bioinformatics and computational biology 8.02 (2010): 199-218.\n[2] Du, Boxin, et al. \"First: Fast interactive attributed subgraph matching.\" Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining. 2017.\n[3] Kopylov, Alexei, and Jiejun Xu. \"Filtering strategies for inexact subgraph matching on noisy multiplex networks.\" 2019 IEEE international conference on big data (big data). IEEE, 2019.\n[4] Moorman, Jacob D., et al. \"Subgraph matching on multiplex networks.\" IEEE Transactions on Network Science and Engineering 8.2 (2021): 1367-1384.\n- Both section 3.2 and section 3.3 are a bit vague on the detailed methodology. More details on the key steps of each phase (matching and ranking) are expected. As a reader, I can only get the general idea but not knowing how I it works and how I should use the method.\n- There should be a section to discuss (sub)graph matching in related work.\n- The authors can better use the Appendix to thoroughly discuss the technical details, e.g., detailed description of key steps, pseudocode, theoretical justifications. Also, for Appendix B, it is better to have insightful analysis to showcase the efficacy of the proposed method.", "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": "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