# EiG-Search: Generating Edge-Induced Subgraphs for GNN Explanation in Linear Time

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 32 references that are in the map.
- First posted on arXiv 2 May 2024.

## Builds on (most cited first, 25 of 25)

- [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)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Axiomatic Attribution for Deep Networks](https://mlsanity.com/paper/1703.01365/) (2017)
- [Learning Important Features Through Propagating Activation Differences](https://mlsanity.com/paper/1704.02685/) (2017)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [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)
- [PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2010.05788/) (2020)
- [GraphLIME: Local Interpretable Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2001.06216/) (2020)
- [Explainability Techniques for Graph Convolutional Networks](https://mlsanity.com/paper/1905.13686/) (2019)
- [Interpreting Graph Neural Networks for NLP With Differentiable Edge Masking](https://mlsanity.com/paper/2010.00577/) (2020)
- [Higher-Order Explanations of Graph Neural Networks via Relevant Walks](https://mlsanity.com/paper/2006.03589/) (2020)
- [Generative Causal Explanations for Graph Neural Networks](https://mlsanity.com/paper/2104.06643/) (2021)
- [Robust Counterfactual Explanations on Graph Neural Networks](https://mlsanity.com/paper/2107.04086/) (2021)
- [RelEx: A Model-Agnostic Relational Model Explainer](https://mlsanity.com/paper/2006.00305/) (2020)
- [GStarX: Explaining Graph Neural Networks with Structure-Aware Cooperative Games](https://mlsanity.com/paper/2201.12380/) (2022)
- [DAG Matters! GFlowNets Enhanced Explainer For Graph Neural Networks](https://mlsanity.com/paper/2303.02448/) (2023)
- [Distill n' Explain: explaining graph neural networks using simple surrogates](https://mlsanity.com/paper/2303.10139/) (2023)
- [DEGREE: Decomposition Based Explanation For Graph Neural Networks](https://mlsanity.com/paper/2305.12895/) (2023)
- [Towards Faithful and Consistent Explanations for Graph Neural Networks](https://mlsanity.com/paper/2205.13733/) (2022)
- [MotifExplainer: a Motif-based Graph Neural Network Explainer](https://mlsanity.com/paper/2202.00519/) (2022)
- [GOAt: Explaining Graph Neural Networks via Graph Output Attribution](https://mlsanity.com/paper/2401.14578/) (2024)
- [Factorized Explainer for Graph Neural Networks](https://mlsanity.com/paper/2312.05596/) (2023)

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

- [Explaining GNN Explanations with Edge Gradients](https://mlsanity.com/paper/2508.01048/) (2025)
- [Model-Level GNN Explanations via Rule-to-Graph Readout for Logit Reconstruction](https://mlsanity.com/paper/2503.09051/) (2025)
- [ARM-Explainer -- Explaining and improving graph neural network predictions for the maximum clique problem using node features and association rule mining](https://mlsanity.com/paper/2511.22866/) (2025)
- [Towards Faithful Graph Explanations with Synergistic Edge Effects via Granular Balls](https://mlsanity.com/paper/2607.21381/) (2026)
- [How Much Does Message Passing Matter? A Drop-In Study of GNN Layers for Neural Network Graph Regression](https://mlsanity.com/paper/2607.26404/) (2026)

## Abstract (arXiv)

Understanding and explaining the predictions of Graph Neural Networks (GNNs), is crucial for enhancing their safety and trustworthiness. Subgraph-level explanations are gaining attention for their intuitive appeal. However, most existing subgraph-level explainers face efficiency challenges in explaining GNNs due to complex search processes. The key challenge is to find a balance between intuitiveness and efficiency while ensuring transparency. Additionally, these explainers usually induce subgraphs by nodes, which may introduce less-intuitive disconnected nodes in the subgraph-level explanations or omit many important subgraph structures. In this paper, we reveal that inducing subgraph explanations by edges is more comprehensive than other subgraph inducing techniques. We also emphasize the need of determining the subgraph explanation size for each data instance, as different data instances may involve different important substructures. Building upon these considerations, we introduce a training-free approach, named EiG-Search. We employ an efficient linear-time search algorithm over the edge-induced subgraphs, where the edges are ranked by an enhanced gradient-based importance. We conduct extensive experiments on a total of seven datasets, demonstrating its superior performance and efficiency both quantitatively and qualitatively over the leading baselines.