  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.
