Research map / Graph learning / GNN architectures
EiG-Search: Generating Edge-Induced Subgraphs for GNN Explanation in Linear Time
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes EiG-Search, a training-free GNN explainer that induces subgraphs from edges, ranks edges by a linear-gradient importance, and searches top-k edge subsets in linear time to pick a per-instance explanation size.
Problem
Subgraph-level GNN explanations are computationally expensive to search, are usually node-induced (producing disconnected or incomplete structures), and use a fixed explanation size across all instances.
Approach
Argues edge-induced subgraphs are more intuitive and exhaustive than node-induced ones, scores edges with a "linear gradient" from a base graph (edges zeroed) to the original graph without training an auxiliary model, then sweeps top-k edges (linear in |E|) and selects the k maximizing Fidelity+ minus Fidelity-.
Key results
- EiG-Search outperforms node-induced and edge-induced baselines in overall fidelity across all tested datasets and GNN variants (GCN and GIN).
- On BA-Shapes, BA-Community, and Tree-Grid node tasks, EiG-Search reports AUC 0.999, 0.996, and 0.947, respectively, versus RCExplainer's 0.998, 0.995, and 0.995 on Tree-Grid.
- Explain time on Mutagenicity is 0.14s per instance, versus 0.53s for DEGREE and 1.44s for GNNExplainer, with no training required.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use EiG-Search instead of RCExplainer | GIN explanations · BA-Shapes | AUC: 0.998 -> 0.999 | Helped |
| Use EiG-Search instead of RCExplainer | GIN explanations · BA-Community | AUC: 0.995 -> 0.996 | Helped |
| Use EiG-Search instead of RCExplainer | GIN explanations · Tree-Grid | AUC: 0.995 -> 0.947 | Hurt |
| Use EiG-Search instead of PGExplainer | explanation generation · BA-Shapes | explain time: 0.181±0.04s -> 0.006±0.000s | Helped |
| Use EiG-Search instead of PGExplainer | explanation generation · BA-Community | explain time: 0.0495±0.01s -> 0.007±0.000s | Helped |
| Use EiG-Search instead of PGExplainer | explanation generation · Tree-Grid | explain time: 0.215±0.07s -> 0.003±0.000s | Helped |
| Use EiG-Search instead of PGExplainer | explanation generation · BA-2Motifs | explain time: 0.306s±0.07 -> 0.089±0.01s | Helped |
| Use EiG-Search instead of PGExplainer | explanation generation · MUTAG | explain time: 0.138±0.03s -> 0.07±0.01s | Helped |
| Use EiG-Search instead of PGExplainer | explanation generation · Mutagenicity | explain time: 0.274±0.08s -> 0.14±0.01s | Helped |
| Add linear-complexity search to existing node- and edge-level explainers (ablation) | SA, Grad-CAM, GNNExplainer, PGExplainer, and IG · MUTAG, BA-2Motifs, and Mutagenicity | overall fidelity | Helped |
| Use Linear Gradients rather than Integrated Gradients (ablation) | edge importance with linear-complexity search · MUTAG, BA-2Motifs, and Mutagenicity | overall fidelity | Helped |
Surprising findings
- Explanation size should vary per instance; a single fixed sparsity or ratio across a dataset is not optimal.
- Edge-induced subgraphs can capture disconnected substructures (e.g., multiple -NO2 groups) that a single connected subgraph explainer misses.
Limitations
- Relies on a fidelity-based search objective that uses the model's predictions, so explanation quality depends on the edge ranking accuracy.
- Integrated Gradients and other baselines are reported to be sensitive to integral paths; the authors note potential gains from a more accurate edge-ranking algorithm and advanced search are possible.
- Node-level results rely on baseline numbers from original papers and on a single GIN setup, limiting direct comparability.
Experimental setup
Datasets: BA-2Motifs MUTAG Mutagenicity NCI1 BA-Shapes BA-Community Tree-Grid
Benchmarks: BA-2Motifs MUTAG Mutagenicity NCI1 BA-Shapes BA-Community Tree-Grid
Metrics: Fidelity+ Fidelity- overall fidelity (Fidelity+ minus Fidelity-) explanation AUC explain time
Baselines: SA Grad-CAM GNNExplainer PGExplainer SubgraphX DEGREE PGM-Explainer RG-Explainer RCExplainer Integrated Gradients
Builds on: Integrated Gradients SubgraphX GNNExplainer PGExplainer DEGREE
Closest papers by meaning
- A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening (NeurIPS 2024 · similarity 0.90)
- Graph Segmentation and Contrastive Enhanced Explainer for Graph Neural Networks (AAAI 2025 · similarity 0.90)
- GnnXemplar: Exemplars to Explanations - Natural Language Rules for Global GNN Interpretability (NeurIPS 2025 · similarity 0.89)
- Generating In-Distribution Proxy Graphs for Explaining Graph Neural Networks (ICML 2024 · similarity 0.89)
- GraphTrail: Translating GNN Predictions into Human-Interpretable Logical Rules (NeurIPS 2024 · similarity 0.89)
- Stratified GNN Explanations through Sufficient Expansion (AAAI 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.