Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph
  Matching
The success of graph neural networks (GNNs) provokes the question about
explainability: ``Which fraction of the input graph is the most determinant of
the prediction?'' Particularly, parametric explainers prevail in existing
approaches because of their more robust capability to decipher the black-box
(i.e., target GNNs). In this paper, based on the observation that graphs
typically share some common motif patterns, we propose a novel non-parametric
subgraph matching framework, dubbed 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. Moreover, we note that present graph sampling or
node-dropping methods usually suffer from the false positive sampling problem.
To alleviate this issue, we designed a new augmentation paradigm named
MatchDrop. It takes advantage of MatchExplainer to fix the most informative
portion of the graph and merely operates graph augmentations on the rest less
informative part. Extensive experiments on synthetic and real-world datasets
show the effectiveness of our MatchExplainer by outperforming all
state-of-the-art parametric baselines with significant margins. Results also
demonstrate that MatchDrop is a general scheme to be equipped with GNNs for
enhanced performance. The code is available at:
https://github.com/smiles724/MatchExplainer.
Fang Wu, Siyuan Li, Xurui Jin, Yinghui Jiang, Dragomir Radev, Zhangming Niu, Stan Z. Li
# Explaining Graph Neural Networks via Non-parametric Subgraph Matching

###### 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?"_ Particularly, parametric explainers prevail in existing approaches because of their stronger capability to decipher the black-box (i.e., the target GNN). In this paper, based on the observation that graphs typically share some joint motif patterns, we propose a novel non-parametric subgraph matching framework, dubbed 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. Moreover, we note that present graph sampling or node-dropping methods usually suffer from the false positive sampling problem. To ameliorate that issue, we design a new augmentation paradigm named MatchDrop. It takes advantage of MatchExplainer to fix the most informative portion of the graph and merely operates graph augmentations on the rest less informative part. We conduct extensive experiments on both synthetic and real-world datasets and show the effectiveness of our MatchExplainer by outperforming all parametric baselines with significant margins. Additional results also demonstrate that our MatchDrop is a general scheme to be equipped with GNNs for enhanced performance.

Graph neural networks, Graph neural networks, Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Sub Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-non Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching, Non-parametric Subgraph Matching
subgraph patterns are shared by different groups of graphs, which can be the key to deciphering the decision of GNNs. These frequently occurring motifs contain rich semantic meanings and indicate the characteristics of the whole graph instance (Henderson et al., 2012; Zhang et al., 2020; Banjade et al., 2021; Wu et al., 2023). For example, the hydroxide group (-OH) in small molecules typically results in higher water solubility and a carboxyl group (-COOH) usually contributes to better stability and higher boiling points. Besides that, the pivotal role of functional groups has also been proven in protein structure prediction (Senior et al., 2020).

Inspired by this inspection, we propose to mine the explanatory motif in a subgraph matching manner and design a novel non-parametric algorithm dubbed MatchExplainer, whose workflow is depicted in Fig. 1. For each pair of graphs, our MatchExplainer endeavors to explore the most crucial joint substructure by minimizing their node corresponding-based distance in the high-dimensional feature space. Then it marries the target graph iteratively with other counterpart graphs in the reference set to seek potential explanatory subgraphs. Consequently, unlike traditional explainers, the candidate explanation produced by MatchExplainer can be non-unique for the same target graph instance.

Taking a step further, we leverage the metric of mutual information from the information theory to analyze the working principle of our MatchExplainer. To be specific, we define the explanation that contains all shared information between paired graphs as _sufficient explanation_, while the explanation that contains the shared and eliminates the non-shared information as _minimal sufficient explanation_. We prove that the minimal sufficient explanation can be used to approximate the desired ground truth explanation with a theoretical guarantee. This strong relationship also provides a perspective for us to filter out the best-case substructure from all candidate explanatory subgraphs. To be precise, we propose to optimize the final candidate explanations by maximizing the difference in the prediction after the explanatory subgraph is removed from the original graph.

Last but not least, we exhibit a bonus of our MatchExplainer to be applied in enhancing the traditional graph augmentation methods. Though exhibiting strong power in preventing over-fitting and over-smoothing, present graph sampling or node-dropping 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 MatchExplainer and introduce a 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 or 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 experiments on synthetic and real-world applications demonstrate that our MatchExplainer can find the explanatory subgraphs fast and accurately with state-of-the-art performance. Additionally, we empirically show that our MatchDrop, a pragmatic application of MatchExplainer, can serve as an efficient way to promote conventional graph augmentation methods.

## 2 Preliminary and Task Description

In this section, we begin with the description of the task of GNN explanation and then briefly review the relevant background of graph matching and graph similarity learning (GSL). Throughout this paper, an upper-case letter like \(\mathcal{G}\) denotes random variables, while lower-case letters like \(g\) denote deterministic values of variables.

Explanations for GNNs.Let \(h_{Y}:\mathcal{G}\rightarrow\mathcal{Y}\) denote the well-trained GNN to be explained, which gives the prediction \(\hat{Y}\) to approximate the ground truth \(Y\). Without loss of generality, we consider the problem of explaining a graph classification task. Our goal is to find an explainer \(h_{S}:\mathcal{G}\rightarrow\mathcal{G}_{\mathcal{S}}\) that discovers the subgraph \(\mathcal{G}_{S}\) from input graph \(\mathcal{G}\) as:

\[\min_{h_{S}}\mathcal{R}(h_{Y}\circ h_{S}(\mathcal{G}),\hat{Y}),\text{s.t.}|h_{ S}(\mathcal{G})|\leq K, \tag{1}\]

where \(\mathcal{R}(.)\) is the risk function such as a cross-entropy loss or a mean squared error (MSE) loss, and \(K\) is a constraint on the size of \(\mathcal{G}_{S}\) to attain a compact explanation. That is, \(\mathcal{G}_{S}\) has at most \(K\) nodes.

Figure 1: The illustration of our proposed MatchExplainer. The explanation \(\mathcal{G}_{S}\) is attained via subgraph matching between \(\mathcal{G}\) and \(\mathcal{G}^{\prime}\), where we minimize the accumulated node-to-node distance in the high-dimensional feature space in a greedy search manner. Since several \(\mathcal{G}_{S}\) can be obtained by matching \(\mathcal{G}\) to different counterpart graphs \(\mathcal{G}^{\prime}\) from the reference set \(\mathcal{D}_{\mathcal{G}}\), we seek to find the optimal one by maximizing Equ. 10.
Graph matching.As a classic combinatorial problem, graph matching is known in general NP-hard (Loiola et al., 2007). They require expensive, complex, and impractical solvers, leading to inexact solutions (Wang et al., 2020). Given two different graphs \(\mathcal{G}_{1}=(\mathcal{V}_{1},\mathcal{E}_{1})\) and \(\mathcal{G}_{2}=(\mathcal{V}_{2},\mathcal{E}_{2})\) with \(N_{1}\) and \(N_{2}\) nodes respectively, the matching between them can be generally expressed by the quadratic assignment programming (QAP) form as (Wang et al., 2019):

\[\min_{\mathbf{T}\in\{0,1\}^{N_{1}\times N_{2}}}\text{vec}(\mathbf{T})^{T} \mathbf{Kvec}(\mathbf{T}),\,s.t.,\mathbf{T}\mathbf{1}=\mathbf{1},\,\mathbf{T} ^{T}\mathbf{1}=\mathbf{1}, \tag{2}\]

where \(\mathbf{T}\) is a binary permutation matrix encoding the node correspondence, and \(\mathbf{1}\) denotes a column vector with all elements to be one. \(\mathbf{K}\) is the so-called affinity matrix (Leordeanu & Hebert, 2005), whose elements encode the node-to-node and edge-to-edge affinity between \(\mathcal{G}_{1}\) and \(\mathcal{G}_{2}\).

Graph similarity learning.GSL is a general framework for graph representation learning that requires reasoning about the structures and semantics of graphs (Li et al., 2019). We need to produce the similarity score \(s(\mathcal{G}_{1},\mathcal{G}_{2})\) between them. This similarity \(s(.,.)\) is typically defined by either exact matches for full-graph or sub-graph isomorphism (Berretti et al., 2001; Shasha et al., 2002), or some measure of structural similarity such as the graph edit distance (Willett et al., 1998; Raymond et al., 2002). In our setting, \(s(.,.)\) depends entirely on whether these two graphs belong to the same category or share very close properties. Then for \(\mathcal{G}_{1}\) and \(\mathcal{G}_{2}\) with the same type, GSL seeks to maximize the mutual information between their representations with the joint distribution \(p(\mathcal{G}_{1},\mathcal{G}_{2})\) as:

\[\max_{f_{1},f_{2}}I(f_{1}(\mathcal{G}_{1}),f_{2}(\mathcal{G}_{2}),T), \tag{3}\]

where \(f_{1}\) and \(f_{2}\) are encoding functions. They can share the same parameter (i.e., \(f_{1}=f_{2}\)) or be combined into one architecture. \(T\) is the random variable that stands for the information required for a specific task, which is independent to the model selection.

## 3 The MatchExplainer Approach

The majority of recent approaches lean on parametric networks to interpret GNNs, and some early methods for GNN explanations are based on local explainability and from a single-graph view (Ying et al., 2019; Baldassarre & Azizpour, 2019; Pope et al., 2019; Schwab & Karlen, 2019). Regardless of this inclination, we argue that a non-parametric graph-graph fashion can also excavate important subgraphs and may lead to better explainability. In this work, we introduce MatchExplainer to explain GNNs via identifying the joint essential substructures by means of subgraph matching (see Algorithm 1).

### Theoretical Analysis of MatchExplainer

From the perspective of probability theory and information theory, Equ. 1 is equivalent to maximizing the mutual information between the input graph \(\mathcal{G}\) and the subgraph \(\mathcal{G}_{S}\) in the context of \(h_{Y}\). Namely, the goal of an explainer is to derive a small subgraph \(\mathcal{G}_{S}\) such that:

\[\max_{\mathcal{G}_{S}\subset\mathcal{G},|\mathcal{G}_{S}|\leq K}I(\mathcal{G }_{S},T_{h}), \tag{4}\]

where \(I(.)\) refers to the Shannon mutual information of two random variables. Unlike \(T\) which is model-agnostic, \(T_{h}\) represents the knowledge learned by the GNN predictor \(h_{Y}\) in a concrete downstream task. Notably, instead of merely optimizing the information hidden in \(\mathcal{G}_{S}\), another line of research (Yuan et al., 2021) seeks to reduce the mutual information between the remaining subgraph \(\mathcal{G}-\mathcal{G}_{S}\) and the original one \(\mathcal{G}\) as:

\[\min_{\mathcal{G}_{S}\subset\mathcal{G},|\mathcal{G}_{S}|\leq K}I(\mathcal{G }-\mathcal{G}_{S},T_{h}). \tag{5}\]

As an approximation of directly optimizing Equ. 4, the core idea of MatchExplainer is to fetch another graph \(\mathcal{G}^{\prime}\) that shares the same predicted property as \(\mathcal{G}\) (_i.e._, \(h_{Y}(\mathcal{G})=h_{Y}(\mathcal{G}^{\prime})\)) and then extract the most relevant part between them as the explanations. To be specific, we aim to search for the best counterpart \(\mathcal{G}^{\prime}\) so that the mutual information between the input graph \(\mathcal{G}\) and the subgraph \(\mathcal{G}_{S}\) is maximized as:

\[\max_{\mathcal{G}^{\prime}\in\mathcal{D}_{\mathcal{G}},\mathcal{G}^{\prime} \neq\Phi}\left[\max_{\mathcal{G}_{S}\subset\mathcal{G},|\mathcal{G}_{S}| \leq K}I(\mathcal{G}_{S},\mathcal{G}^{\prime},T_{h})\right], \tag{6}\]

where \(\mathcal{D}_{\mathcal{G}}\) denotes the reference set consisting of all available graphs, and \(\mathcal{G}_{S}\) is obtained by subgraph matching between \(\mathcal{G}\) and \(\mathcal{G}^{\prime}\). Similar to the information bottleneck theory (Tishby & Zaslavsky, 2015; Achille & Soatto, 2018) in supervised learning, we can define the sufficient explanation and minimal sufficient explanation of \(\mathcal{G}\) with its counterpart \(\mathcal{G}^{\prime}\neq\mathcal{G}\) in the context of subgraph matching.

**Definition 3.1** (Sufficient Explanation).: Given \(\mathcal{G}^{\prime}\), the explanation \(\mathcal{G}_{S}^{usf}\) of \(\mathcal{G}\) is sufficient if and only if \(I(\mathcal{G}_{S}^{usf},\mathcal{G}^{\prime},T_{h})=I(\mathcal{G},\mathcal{G }^{\prime},T_{h})\).

The sufficient explanation \(\mathcal{G}_{S}^{usf}\) of \(\mathcal{G}\) keeps all joint information with \(\mathcal{G}^{\prime}\) related to the learned information \(T_{h}\). In other words, \(\mathcal{G}_{S}^{usf}\) contains all the shared information between \(\mathcal{G}\) and \(\mathcal{G}^{\prime}\). Symmetrically, the sufficient explanation for \(\mathcal{G}^{\prime}\) satisfies \(I(\mathcal{G}_{S}^{usf},\mathcal{G}^{\prime},T_{h})=I(\mathcal{G},\mathcal{G }^{\prime},T_{h})\).

**Definition 3.2** (Minimal Sufficient Explanation).: Given \(\mathcal{G}^{\prime}\), the sufficient explanation \(\mathcal{G}_{S}^{min}\) of \(\mathcal{G}\) is minimal if and only if \(I(\mathcal{G}_{S}^{min},\mathcal{G},T_{h})\leq I(\mathcal{G}_{S}^{usf}, \mathcal{G},T_{h})\).

Among all sufficient explanations, the minimal sufficient explanation \(\mathcal{G}_{S}^{min}\) contains the least information about
with regards to the learned knowledge \(T_{h}\). Normally, it is usually assumed that \(\mathcal{G}_{S}^{min}\) only maintains the shared information between \(\mathcal{G}\) and \(\mathcal{G}^{\prime}\), and eliminates other non-shared one, i.e., \(I(\mathcal{G}_{S}^{min},\mathcal{G}|\mathcal{G}^{\prime})=0\).

**Theorem 3.3** (Task Relevant Information in Explanations).: _(Wang et al., 2022) Given \(\mathcal{G}^{\prime}\), the minimal sufficient explanation \(\mathcal{G}_{S}^{min}\) contains less task-relevant information learned by \(h_{Y}\) from input \(\mathcal{G}\) than any other sufficient explanation \(\mathcal{G}_{S}^{suf}\). Formally, we have:_

\[\begin{split} I(\mathcal{G},T_{h})&=I(\mathcal{G}_ {S}^{min},T_{h})+I(\mathcal{G},T_{h}|\mathcal{G}^{\prime})\\ &\geq I(\mathcal{G}_{S}^{suf},T_{h})=I(\mathcal{G}_{S}^{min},T_{ h})+I(\mathcal{G}_{S}^{suf},\mathcal{G},T_{h}|\mathcal{G}^{\prime})\\ &\geq I(\mathcal{G}_{S}^{min},T_{h}).\end{split} \tag{7}\]

Theorem 3.3 indicates that the mutual information between \(\mathcal{G}\) and \(T_{h}\) can be divided into two fractions. One is \(\mathcal{G}_{S}^{min}\), which is the interaction between \(\mathcal{G}\) and \(\mathcal{G}^{\prime}\) associated with the learned knowledge \(T_{h}\). The other is determined by the disjoint structure of \(\mathcal{G}\) and \(\mathcal{G}^{\prime}\) with respect to the learned information \(T_{h}\). Our subgraph matching is committed to maximizing \(I(\mathcal{G}_{S}^{min},T_{h})\), which is the lower bound of \(I(\mathcal{G},T_{h})\). Notably, \(I(\mathcal{G},T_{h}|\mathcal{G}^{\prime})\) is not completely independent to \(I(\mathcal{G}_{S}^{min},T_{h})\), but is instead the offset of \(I(\mathcal{G}_{S}^{min},T_{h})\) to \(I(\mathcal{G},T_{h})\). Hence, if we increase \(I(\mathcal{G}_{S}^{min},T_{h})\), \(I(\mathcal{G},T_{h}|\mathcal{G}^{\prime})\) is minimized simultaneously. Consequently, \(I(\mathcal{G}_{S}^{min},T_{h})\) can be used to not only improve the lower bound of \(I(\mathcal{G},T_{h})\) but approximate \(I(\mathcal{G},T_{h})\), which is exactly our final explanatory object. This provides a firm theoretical foundation for our MatchExplainer to mine the most explanatory substructure via the subgraph matching approach.

### Non-parametric Subgraph Exploration

Preamble.It is remarkable that our excavation of explanations through subgraph matching has some significant differences from either graph matching or GSL. On the one hand, graph matching algorithms (Zanfir and Sminchisescu, 2018; Sarlin et al., 2020; Wang et al., 2020, 2021) typically establish node correspondence from a whole graph \(\mathcal{G}_{1}\) to another whole graph \(\mathcal{G}_{2}\). However, we seek to construct partial node correspondence between the subgraph of \(\mathcal{G}_{1}\) and the subgraph of \(\mathcal{G}_{2}\). On the other hand, GSL concentrates on the graph representations encoded by \(f_{1}\) and \(f_{2}\), as well as the ground truth information \(T\) rather than the information \(T_{h}\) learned by the GNN predictor \(h_{Y}\).

Besides, most existing graph matching architectures (Zanfir and Sminchisescu, 2018; Li et al., 2019; Wang et al., 2020; Papakis et al., 2020; Liu et al., 2021) are deep learning-based. 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 a 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.

Subgraph matching framework.We break the target GNN \(h_{Y}\) into two consecutive parts: \(h_{Y}=\phi_{G}\circ\phi_{X}\), where \(\phi_{G}\) is the aggregator to compute the graph-level representation and predict the properties, and \(\phi_{X}\) is the feature function to update both the node and edge features. For a given graph \(\mathcal{G}\) with node features \(\mathbf{h}_{i}\in\mathbb{R}^{\psi_{v}},\forall i\in\mathcal{V}\) and edge features \(\mathbf{e}_{ij}\in\mathbb{R}^{\psi_{e}},\forall(i,j)\in\mathcal{E}\), the renewed output is calculated as \(\{\mathbf{h}_{i}^{\prime}\}_{i\in\mathcal{V}},\{\mathbf{e}_{ij}^{\prime}\}_{(i, j)\in\mathcal{E}}=\phi_{X}\left(\{\mathbf{h}_{i}\}_{i\in\mathcal{V}},\{\mathbf{e}_{ij}\}_{(i, j)\in\mathcal{E}}\right)\), which is forwarded into \(\phi_{G}\) afterwards.

Our target is to find subgraphs \(\mathcal{G}_{S}\subset\mathcal{G}\) and \(\mathcal{G}_{S}^{\prime}\subset\mathcal{G}^{\prime}\) both with \(K\) nodes to maximize \(I(\mathcal{G}_{S},\mathcal{G}_{S}^{\prime},T_{h})\). There we utilize the node correspondence-based distance \(d_{G}\) as a substitution for measuring \(I(\mathcal{G}_{S},\mathcal{G}_{S}^{\prime},T_{h})\), the shared learned information between \(\mathcal{G}_{S}\) and \(\mathcal{G}_{S}^{\prime}\). Then given a pair of \(\mathcal{G}\) and \(\mathcal{G}^{\prime}\), \(d_{G}\) is defined and minimized as follows:

\[\begin{split}\min_{\mathcal{G}_{S}\subset\mathcal{G},\mathcal{G}_{ S}^{\prime}\subset\mathcal{G}^{\prime}}d_{G}(\mathcal{G}_{S},\mathcal{G}_{S}^{ \prime})=\\ \min_{\mathcal{G}_{S}\subset\mathcal{G},\mathcal{G}_{S}^{\prime} \subset\mathcal{G}^{\prime}}\left(\min_{\mathbf{T}\in\Pi(\mathcal{G}_{S}, \mathcal{G}_{S}^{\prime})}\left\langle\mathbf{T},\mathbf{D}^{\phi_{X}}\right \rangle\right),\end{split} \tag{8}\]

where \(\mathbf{D}^{\phi_{X}}\) is the matrix of all pairwise distances between node features of \(\mathcal{G}_{S}\) and \(\mathcal{G}_{S}^{\prime}\). Its element is calculated as \(\mathbf{D}_{ij}^{\phi_{X}}=d_{X}(\mathbf{h}_{i}^{\prime},\mathbf{h}_{j}^{ \prime})\ \forall i\in\mathcal{V},j\in\mathcal{V}^{\prime}\), where \(d_{X}\) is the standard vector space similarity such as the Euclidean distance and the Hamming distance. The inner optimization is conducted over \(\Pi(.,.)\), which is the set of all matrices with prescribed margins defined as:

\[\Pi(\mathcal{G}_{S},\mathcal{G}_{S}^{\prime})=\left\{\mathbf{T}\in\{0,1\}^{K \times K}\,|\,\mathbf{T}\mathbf{1}=\mathbf{1},\,\mathbf{T}^{T}\mathbf{1}= \mathbf{1}\right\}. \tag{9}\]

Due to the NP-hard nature of graph matching (Loiola et al., 2007), we adopt the greedy strategy to optimize \(d_{G}(\mathcal{G}_{S},\mathcal{G}_{S}^{\prime})\) and attain the subgraph \(\mathcal{G}_{S}\). 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 with the complexity of \(O(K)\).

After that, we feed \(\mathcal{G}_{S}\) into \(h_{Y}\) and examine its correctness. If \(h_{Y}(\mathcal{G}_{S})=h_{Y}(\mathcal{G})\), then \(\mathcal{G}_{S}\) is regarded as the candidate explanation. Otherwise, \(\mathcal{G}_{S}\) is abandoned since it cannot recover the information required by \(h_{Y}\) to predict \(\mathcal{G}\).

Non-uniqueness of GNN explanations.Unlike prior learning-based GNN explanation methods (Vu and Thai, 2020; Wang et al., 2021, 2022) that generate a unique subgraph \(\mathcal{G}_{S}\) for \(\mathcal{G}\), our selection of \(\mathcal{G}_{S}\) varies according to
the choice of the counterpart \(\mathcal{G}^{\prime}\in\mathcal{D}_{\mathcal{G}}\). Therefore, MatchExplainer can provide many-to-one explanations for a single graph \(\mathcal{G}\) once a bunch of counterparts is given. This offers a new understanding that the determinants for GNNs' predictions are non-unique, and GNNs can gain correct predictions based on several different explanatory subgraphs of the same size.

Optimization of GNN Explanations.Since our MatchExplainer is able to discover a variety of possible explanatory subgraphs, how to screen out the most informative one becomes a critical issue. As indicated in Theorem 3.3, \(I(\mathcal{G}^{min}_{S},T_{h})\) is the lower bound of \(I(\mathcal{G},T_{h})\), and their difference \(I(\mathcal{G},T_{h}|\mathcal{G}^{\prime})\) entirely depends on the selection of the matching counterpart \(\mathcal{G}^{\prime}\). Ideally, \(\mathcal{G}^{\prime}\) ought to share the exact same explanatory substructure with \(\mathcal{G}\), i.e., \(\mathcal{G}_{S}=\mathcal{G}^{\prime}_{S}\). Meanwhile, \(\mathcal{G}\) conditioned on \(\mathcal{G}^{\prime}\) is independent to the learned knowledge \(T_{h}\), i.e., \(I(\mathcal{G},T_{h}|\mathcal{G}^{\prime})=0\). Therefore, there are two distinct principles for selecting the counterpart graphs.

The first line is to seek \(\mathcal{G}^{\prime}\) that has as close the explanatory subgraph as possible to \(\mathcal{G}\). The second line is to ensure that \(\mathcal{G}\) conditioned on \(\mathcal{G}^{\prime}\) maintains little information relevant to the learned information \(T_{h}\). Nevertheless, without sufficient domain knowledge regarding which substructure is majorly responsible for the graph property, it would be impossible for us to manually select the counterpart graph \(\mathcal{G}^{\prime}\) that satisfies \(\mathcal{G}_{S}\approx\mathcal{G}^{\prime}_{S}\).

As a remedy, we consider optimizing an opposite objective described in Equ. 5. That is, we desire to minimize the intersection between \(\mathcal{G}-\mathcal{G}_{S}\) and \(T_{h}\), _i.e._, \(I(\mathcal{G}-\mathcal{G}_{S},T_{h})\). Towards this goal, we remove the extracted subgraph \(\mathcal{G}_{S}\) from \(\mathcal{G}\) and aspire to confuse GNNs' predictions on the remaining part \(\mathcal{G}-\mathcal{G}_{S}\). Mathematically, the optimal \(\mathcal{G}^{\prime}\) maximizes the difference between the prediction of the whole graph and the prediction of the graph that is subtracted by \(\mathcal{G}_{S}\). In other words, we wish to retrieve the best explanation \(\mathcal{G}^{+}_{S}\) via:

\[\max_{\mathcal{G}^{\prime}\in\mathcal{D}_{S},\mathcal{G}^{\prime} \neq\mathcal{G}} \Delta_{\mathcal{G}}(\mathcal{G}^{\prime},h_{Y})= \tag{10}\] \[\max_{\mathcal{G}^{\prime}\in\mathcal{D}_{S},\mathcal{G}^{\prime} \neq\mathcal{G}}\left[h_{Y}^{c^{*}}(\mathcal{G})-h_{Y}^{c^{*}}(\mathcal{G}- \mathcal{G}_{S})\right],\]

where \(c^{*}\) is the ground truth class of \(\mathcal{G}\) and \(\mathcal{G}_{S}\) is the substructure via subgraph matching with \(\mathcal{G}^{\prime}\). \(\mathcal{D}_{\mathcal{S}}\) is the candidate subgraph set.

To summarize, given any graph \(\mathcal{G}\) and a reference graph set \(\mathcal{D}_{\mathcal{G}}\), we first acquire all possible subgraphs via matching \(\mathcal{G}\) to available counterparts in \(\mathcal{D}_{\mathcal{G}}\). After the pairwise subgraph matching, we calculate their corresponding \(\Delta_{\mathcal{G}}(.,h_{Y})\) and pick up the one that leads to the largest \(\Delta_{\mathcal{G}}(.,h_{Y})\) as the optimal counterpart graph. Notably, not all graphs in \(\mathcal{D}_{\mathcal{G}}\) are qualified counterparts and there are several intuitive conditions that \(\mathcal{G}^{\prime}\) has to satisfy. First, \(\mathcal{G}\) and \(\mathcal{G}^{\prime}\) should belong to the same category predicted by \(h_{Y}\). Besides, \(\mathcal{G}^{\prime}\) needs to have at least \(K\) nodes. Otherwise, \(G_{S}\) would be smaller than the given constrained size.

Effectiveness vs. efficiency.The time-complexity is always an important topic to evaluate the practicability of explainers. For our MatchExplainer, the size of the reference set, _i.e._, \(|\mathcal{D}_{\mathcal{G}}|\), plays a vital role in determining the time cost, since the total time cost is \(O(K|\mathcal{D}_{\mathcal{G}}|)\). 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 \(\mathcal{D}_{\mathcal{G}}\).

## 4 The MatchDrop Methodology

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 of data augmentation techniques (Hamilton et al., 2017; Rong et al., 2019) have been proposed in the graph domain and shown promising outcomes. Among them, graph sampling 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 sampling and injecting spurious information into the training process. For instance, _1,3-dinitrobenzene_ (C\({}_{6}\)H\({}_{4}\)N\({}_{2}\)O\({}_{4}\)) is a mutagen molecule and its explanation is the NO\({}_{2}\) groups (Debnath et al., 1991). If any edge or node of the NO\({}_{2}\) 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 convenient way to discover the most essential part of a given graph. It is natural to keep this crucial portion unchanged and only drop nodes or edges in the remaining portion. Based on this idea, we propose a simple but effective method dubbed MatchDrop, which keeps the most informative part of graphs found by our MatchExplainer and alters the less informative part (see Figure 2).
The procedure of our MatchDrop is described as follows. To begin with, we train a GNN \(h_{Y}\) for several epochs until it converges to an acceptable accuracy, which guarantees the effectiveness of the subsequent subgraph selection. Then for each graph \(\mathcal{G}\) in the training set \(\mathcal{D}_{\text{train}}\), we randomly select another graph \(\mathcal{G}^{\prime}\in\mathcal{D}_{\text{train}}\) with the same class as the counterpart graph. Afterwards, we explore its subgraph \(\mathcal{G}_{S}\) via MatchExplainer with a retaining ratio \(\rho\) (i.e., \(|\mathcal{G}_{S}|=\rho|\mathcal{G}|\)) and use it as the model input to train \(h_{Y}\).

Notably, similar to the typical image augmentation skills such as rotation and flapping (Shorten and Khoshgoftaar, 2019), MatchDrop is a novel data augmentation technique for GNN training. However, instead of augmenting \(\mathcal{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:

\[\mathcal{L}_{S}=-\frac{1}{|\mathcal{D}_{\text{train}}|}\sum_{\mathcal{G}\in \mathcal{D}_{\text{train}}}\sum_{c=1}^{M}Y_{\mathcal{G}}\log\left(h_{Y}^{c} \left(h_{S}(\mathcal{G},\rho)\right)\right), \tag{11}\]

where \(h_{Y}^{c}(.)\) indicates the predicted probability of \(\mathcal{G}_{S}\) to be of class \(c\) and \(Y_{G}\) is the ground truth value. \(h_{S}\) employs MatchExplainer to mine the subgraph \(\mathcal{G}_{S}\) by matching \(\mathcal{G}\) to a randomly selected counterpart graph \(\mathcal{G}^{\prime}\) in the training set \(\mathcal{D}_{\text{train}}\) with a pre-defined ratio \(\rho\).

## 5 Experimental Analysis

### Datasets and Experimental Settings

Following Wang et al. (2021), we use four standard datasets with various target GNNs.

* **Molecule graph classification**: MUTAG (Debnath et al., 1991; Kazius et al., 2005) is a molecular dataset for the graph classification problem. Each graph stands for a 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 et al., 2018) has approximately achieved a 82% testing accuracy.
* **Motif graph classification.**: Wang et al. (2021) create a synthetic dataset, BA-3Motif, with 3000 graphs. They take advantage of the Barabasi-Albert (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 a 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 as the label. We adopt a Spline-based GNN (Fey et al., 2018) that gains around 98% accuracy in the testing set.
* **Scene graph classification**: Wang et al. (2021) select 4443 pairs of images and scene graphs from Visual Genome (Krishna et al., 2017) 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 an 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 and Azizpour, 2019) directly uses the gradients of the model prediction with respect 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 as the motif in a graph flowing into the final convolutional layer to produce a coarse localization map highlighting the important regions in the graph for predicting the concept.

Figure 2: Comparison between graph augmentation with and without MatchDrop.
* **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.
* **PGExplainer**(Luo et al., 2020) hires a parameterized model to decide whether an edge is important, which is trained over multiple explained instances with all edges.
* **PGM-Explainer**(Vu and Thai, 2020) collects the prediction change on the random node perturbations, and then learns a Bayesian network from these perturbation-prediction observations, so as to capture the dependencies among the nodes and the prediction.
* **ReFiner**(Wang et al., 2021) exploits the pre-training and fine-tuning idea to develop a 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, we follow Wang et al. (2021) and employ **the predictive accuracy (ACC@\(\mathbf{\rho}\))** and **Recall@\(\mathbf{N}\)** as the metrics. Specifically, ACC@\(\rho\) 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 selection ratios \(\rho\in\{0.1,0.2,...,1.0\}\). Recall@\(N\) is computed as \(\mathbb{E}_{\mathcal{G}}\left[\left|\mathcal{G}_{s}\cap\mathcal{G}_{S}^{*} \right|/\left|\mathcal{G}_{S}^{*}\right|\right]\), where \(\mathcal{G}_{S}^{*}\) 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.

### Can MatchExplainer Find Better Explanatory Subgraphs?

Quantitative results.To investigate the effectiveness of MatchExplainer, we conduct broad experiments on four datasets and the comparisons are reported in Table 4. For MUTAG, VG-5, and BA3-Motif, we exploit the whole training and validation data as 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 if we 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-Motif, 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 a 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.

Visualization.In addition, we envision the explanations of MatchExplainer on MUTAG in Appendix B for qualitative evaluations. We also compare the efficiency of our MatchExplainer with other parametric methods in Appendix 3. It can be discovered that MatchExplainer enjoys a competitive fast inference speed with no additional training cost, making it possible for large-scale deployment.

### Can MatchDrop Generally Improve the Performance of GNNs?

Implementations.We take account of two backbones: GCN (Kipf and Welling, 2016), and GIN (Xu et al., 2018) with a depth of 6. Similar to Rong et al. (2019), we adopt a random hyper-parameter search for each architecture to enable more robust comparisons. There, _DropNode_ stands for randomly sampling subgraphs, which can be also treated as a specific form of node dropping. False-positive drop (_FP-Drop_) is the opposite operation of our MatchDrop, where the

\begin{table}
\begin{tabular}{l c c c c c} \hline \hline  & \begin{tabular}{c} MUTAG \\ ACC-AUC \\ \end{tabular} & \begin{tabular}{c} VG-5 \\ ACC-AUC \\ \end{tabular} & \begin{tabular}{c} MNIST \\ ACC-AUC \\ \end{tabular} & \begin{tabular}{c} BA-3Motif \\ ACC-AUC \\ \end{tabular} \\ \hline SA & \(0.769\) & \(0.769\) & \(0.559\) & \(0.518\) & \(0.243\) \\ Grad-CAM & \(0.786\pm 0.011\) & \(0.909\pm 0.005\) & \(0.581\pm 0.009\) & \(0.533\pm 0.003\) & \(0.212\pm 0.002\) \\ GNNExplainer & \(0.895\pm 0.010\) & \(0.895\pm 0.003\) & \(0.535\pm 0.013\) & \(0.528\pm 0.005\) & \(0.157\pm 0.002\) \\ PG-Explainer & \(0.631\pm 0.008\) & \(0.790\pm 0.004\) & \(0.504\pm 0.010\) & \(0.586\pm 0.004\) & \(0.293\pm 0.001\) \\ PGM-Explainer & \(0.714\pm 0.007\) & \(0.792\pm 0.001\) & \(0.615\pm 0.003\) & \(0.575\pm 0.002\) & \(0.250\pm 0.000\) \\ ReFine & \(0.955\pm 0.005\) & \(0.914\pm 0.001\) & \(0.636\pm 0.003\) & \(0.576\pm 0.013\) & \(0.297\pm 0.000\)\({}^{1}\) \\ \hline \hline 
\begin{tabular}{c} MatchExplainer \\ Relative Impro. \\ \end{tabular} & \(\mathbf{0.997}\) & \(\mathbf{0.993}\) & \(\mathbf{0.938}\) & \(\mathbf{0.634}\) & \(\mathbf{0.305}\) \\ \multicolumn{1}{c}{} & \(4.5\%\) & \(8.6\%\) & \(48.9\%\) & \(8.1\%\) & \(2.6\%\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Comparisons of our MatchExplainer with other baseline explainers.
subgraph sampling or node dropping is only performed in the explanatory subgraphs while the rest remains the same. We add FPDrop as a baseline to help unravel the reason why MatchDrop works. _PGDrop_ is similar to MatchDrop, but uses a fixed PGExplainer (Luo et al., 2020) to explore the informative substructure. The selection ratios \(\rho\) for FPDrop, PGDrop, and MatchDrop are all set as 0.95.

Overall results.Table 5.2 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 PGExplainer are trained on samples that GNNs predict correctly, so they are incapable to explore explanatory subgraphs on unseen graphs that GNNs forecast mistakenly.

## 6 Related Work

### Explainability of GNNs

Interpretability and feature selection have been attached growing significance in demystifying complicated deep learning models, and increasing interests have been appealed in explaining GNNs. Despite fruitful progress, the study in this area is still insufficient compared to the domain of images and natural languages. Generally, there are two mainstream lines of research. The widely-adopted one nowadays is the parametric explanation methods. They run a parameterized model to dig out informative substructures or generate the saliency maps. For example, GNNExplainer (Ying et al., 2019) learns soft masks for each instance and applies them on the adjacency matrix. PGExplainer (Luo et al., 2020) collectively explains multiple instances with a probabilistic graph generative model. XGNN (Yuan et al., 2020) utilizes a graph generator to output class-wise graph patterns to explain GNNs for each class. PGM-Explainer (Vu and Thai, 2020) proposes an Bayesian network on the pairs of graph pertubations and prediction changes. The other line is the non-parametric explanation methods, which do not involve any additional trainable models. They employ some heuristics like gradient-like scores obtained by backpropagation as the feature contributions of a specific instance (Baldassarre and Azizpour, 2019; Pope et al., 2019; Schnake et al., 2020). As mentioned previously, the latter is usually less favored because their performance is much poorer than the former parametric methods. In contrast, our MatchExplainer procures state-of-the-art results astonishingly.

### 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., 2022). The related work can be roughly broken down into _feature-wise_(Zhang et al., 2017; Liu et al., 2021; Taguchi et al., 2021), _structure-wise_(You et al., 2020; Zhao et al., 2021), 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., 2022), the augmentation operations on node sets are more complicated. A typical application is to promote the propagation of the whole graph by inserting a supernode (Gilmer et al., 2017), while Zhao et al. (2021) 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), enabling 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.

## 7 Conclusion

This paper proposes a promising subgraph matching technique called MatchExplainer for GNN explanations. Distinct from the popular trend of using a parameterized network that lacks interpretability, we design a non-parametric algorithm to search for the most informative joint subgraph

\begin{table}
\begin{tabular}{c c|c c c c c} \hline \hline Dataset & Backbone & Original & FPDrop & DropNode & PGDrop & MatchDrop \\ \hline \multirow{2}{*}{MUTAG} & GCN & \(0.828\pm 0.004\) & \(0.803\pm 0.017\) & \(0.832\pm 0.008\) & \(0.825\pm 0.02\) & **0.844\(\pm\)0.006** \\  & GIN & \(0.832\pm 0.003\) & \(0.806\pm 0.020\) & \(0.835\pm 0.009\) & \(0.828\pm 0.01\) & **0.845\(\pm\)0.007** \\ \hline \multirow{2}{*}{VG-5} & GCN & \(0.619\pm 0.003\) & \(0.587\pm 0.014\) & \(0.623\pm 0.007\) & \(0.604\pm 0.002\) & **0.638\(\pm\)0.008** \\  & GIN & \(0.621\pm 0.004\) & \(0.593\pm 0.018\) & \(0.622\pm 0.006\) & \(0.600\pm 0.004\) & **0.630\(\pm\)0.003** \\ \hline \multirow{2}{*}{MNIST} & GCN & \(0.982\pm 0.001\) & \(0.955\pm 0.008\) & \(0.982\pm 0.002\) & \(0.975\pm 0.003\) & **0.986\(\pm\)0.002** \\  & GIN & \(0.988\pm 0.001\) & \(0.959\pm 0.005\) & \(0.989\pm 0.001\) & \(0.979\pm 0.002\) & **0.990\(\pm\)0.001** \\ \hline \hline \end{tabular}
\end{table}
Table 2: Testing accuracy (%) comparisons on different backbones with and without MatchDrop.
between a pair of graphs. Furthermore, we combine Match-Explainer with the classic graph augmentation method and show its great capacity in ameliorating the false positive sampling challenge. Experiments convincingly demonstrate the efficacy of our MatchExplainer by winning over parametric approaches with significant margins. Our work hopes to shed light on pushing the frontier of non-parametric methods to explain deep learning models.
