# Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph Matching

arXiv: https://arxiv.org/abs/2301.02780 · HTML: https://mlsanity.com/paper/2301.02780/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 70 references that are in the map.
- First posted on arXiv 7 Jan 2023.

## Builds on (most cited first, 30 of 46)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Grad-CAM: Visual Explanations from Deep Networks via Gradient-based Localization](https://mlsanity.com/paper/1610.02391/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [mixup: Beyond Empirical Risk Minimization](https://mlsanity.com/paper/1710.09412/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Axiomatic Attribution for Deep Networks](https://mlsanity.com/paper/1703.01365/) (2017)
- [Visual Genome: Connecting Language and Vision Using Crowdsourced Dense Image Annotations](https://mlsanity.com/paper/1602.07332/) (2016)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [SuperGlue: Learning Feature Matching with Graph Neural Networks](https://mlsanity.com/paper/1911.11763/) (2019)
- [Graph Contrastive Learning with Augmentations](https://mlsanity.com/paper/2010.13902/) (2020)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Deep Learning and the Information Bottleneck Principle](https://mlsanity.com/paper/1503.02406/) (2015)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training](https://mlsanity.com/paper/2006.09963/) (2020)
- [Parameterized Explainer for Graph Neural Network](https://mlsanity.com/paper/2011.04573/) (2020)
- [Explainability in Graph Neural Networks: A Taxonomic Survey](https://mlsanity.com/paper/2012.15445/) (2020)
- [On Explainability of Graph Neural Networks via Subgraph Explorations](https://mlsanity.com/paper/2102.05152/) (2021)
- [Learning to Explain: An Information-Theoretic Perspective on Model Interpretation](https://mlsanity.com/paper/1802.07814/) (2018)
- [Emergence of Invariance and Disentanglement in Deep Representations](https://mlsanity.com/paper/1706.01350/) (2017)
- [XGNN: Towards Model-Level Explanations of Graph Neural Networks](https://mlsanity.com/paper/2006.02587/) (2020)
- [PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2010.05788/) (2020)
- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [Data Augmentation for Graph Neural Networks](https://mlsanity.com/paper/2006.06830/) (2020)
- [Understanding Attention and Generalization in Graph Neural Networks](https://mlsanity.com/paper/1905.02850/) (2019)
- [SplineCNN: Fast Geometric Deep Learning with Continuous B-Spline Kernels](https://mlsanity.com/paper/1711.08920/) (2017)
- [Explainability Techniques for Graph Convolutional Networks](https://mlsanity.com/paper/1905.13686/) (2019)
- [ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations](https://mlsanity.com/paper/1911.07979/) (2019)

## Built on by (most cited first, 8 of 8)

- [Explaining Graph Neural Networks via Structure-aware Interaction Index](https://mlsanity.com/paper/2405.14352/) (2024)
- [Learnable Kernel Density Estimation for Graphs and Its Application to Graph-Level Anomaly Detection](https://mlsanity.com/paper/2505.21285/) (2025)
- [Introducing Diminutive Causal Structure into Graph Representation Learning](https://mlsanity.com/paper/2406.08709/) (2024)
- [TopInG: Topologically Interpretable Graph Learning via Persistent Rationale Filtration](https://mlsanity.com/paper/2510.05102/) (2025)
- [xNeuSM: Explainable Neural Subgraph Matching with Graph Learnable Multi-hop Attention Networks](https://mlsanity.com/paper/2312.01612/) (2023)
- [Incorporating Retrieval-based Causal Learning with Information Bottlenecks for Interpretable Graph Neural Networks](https://mlsanity.com/paper/2402.04710/) (2024)
- [Beyond Soft Masks: Hard-Perturbation Mixup Explainer for Robust GNN Explainability](https://mlsanity.com/paper/2606.05756/) (2026)
- [Controllable GNN Explanations via Multi-Metric Preference Selection](https://mlsanity.com/paper/2609.32436/) (2026)

## Abstract (arXiv)

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.