mlsanityData to 7 Oct 2026

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

arXiv 2405.01762 ↗First posted 2 May 2024cs.LGcited by 5

Not on the map. Why?

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.

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

Builds on

25 of 32 references.

References · 25

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2016Grad-CAM: Visual Explanations from Deep Networks via Gradient-based Localizationcited by 6,690
  3. 2018How Powerful are Graph Neural Networks?cited by 4,355
  4. 2017Axiomatic Attribution for Deep Networkscited by 3,350
  5. 2017Learning Important Features Through Propagating Activation Differencescited by 1,454
  6. 2019GNNExplainer: Generating Explanations for Graph Neural Networkscited by 735
  7. 2020Parameterized Explainer for Graph Neural Networkcited by 423
  8. 2020Explainability in Graph Neural Networks: A Taxonomic Surveycited by 383
  9. 2021On Explainability of Graph Neural Networks via Subgraph Explorationscited by 280
  10. 2020PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networkscited by 210
  11. 2020GraphLIME: Local Interpretable Model Explanations for Graph Neural Networkscited by 209
  12. 2019Explainability Techniques for Graph Convolutional Networkscited by 160
13 more
  1. 2020Interpreting Graph Neural Networks for NLP With Differentiable Edge Maskingcited by 152
  2. 2020Higher-Order Explanations of Graph Neural Networks via Relevant Walkscited by 138
  3. 2021Generative Causal Explanations for Graph Neural Networkscited by 124
  4. 2021Robust Counterfactual Explanations on Graph Neural Networkscited by 72
  5. 2020RelEx: A Model-Agnostic Relational Model Explainercited by 53
  6. 2022GStarX: Explaining Graph Neural Networks with Structure-Aware Cooperative Gamescited by 42
  7. 2023DAG Matters! GFlowNets Enhanced Explainer For Graph Neural Networkscited by 27
  8. 2023Distill n' Explain: explaining graph neural networks using simple surrogatescited by 18
  9. 2023DEGREE: Decomposition Based Explanation For Graph Neural Networkscited by 18
  10. 2022Towards Faithful and Consistent Explanations for Graph Neural Networkscited by 13
  11. 2022MotifExplainer: a Motif-based Graph Neural Network Explainercited by 11
  12. 2024GOAt: Explaining Graph Neural Networks via Graph Output Attributioncited by 10
  13. 2023Factorized Explainer for Graph Neural Networkscited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 2.

5 papers.

  1. 2025Explaining GNN Explanations with Edge Gradientscited by 1
  2. 2025Model-Level GNN Explanations via Rule-to-Graph Readout for Logit Reconstructioncited by 0
  3. 2025ARM-Explainer -- Explaining and improving graph neural network predictions for the maximum clique problem using node features and association rule miningcited by 0
  4. 2026Towards Faithful Graph Explanations with Synergistic Edge Effects via Granular Ballscited by 0
  5. 2026How Much Does Message Passing Matter? A Drop-In Study of GNN Layers for Neural Network Graph Regressioncited by 0