Research map / Graph learning / GNN architectures
Factorized Explainer for Graph Neural Networks
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.
Shows that GIB-based GNN explainers admit trivial "signaling" solutions, proposes a modified GIB objective using cross-entropy with the model's prediction, and introduces K-FactExplainer, a factorized mixture of k PGExplainer-style edge-mask MLPs chosen by a bootstrapping cover algorithm.
Problem
Post-hoc instance-level explanation of GNNs via graph information bottleneck (GIB) can yield trivial, disconnected explanations, and existing parametric explainers (e.g., PGExplainer) are local and struggle when multiple motifs determine the label.
Approach
Replace the H(Y|G') term of GIB with cross-entropy between the true label and the model's prediction on the explanation (modified GIB), and explain with a factorized mixture of k local edge-mask explainers whose outputs are weighted by a global MLP, with k bounded by a minimal-cover bootstrapping procedure.
Key results
- K-FactExplainer achieves AUC 1.000 on BA-Shapes, 0.974 on BA-Community, 0.821 on BA-2motifs and 0.915 on MUTAG, outperforming GNNExplainer and PGExplainer on these datasets.
- On MUTAG, increasing k from 1 to 10 raises AUC from 0.769 to 0.915 relative to PGExplainer's 0.843.
- On BA-4motifs, k=3 achieves coverage rate 0.712 versus 0.433 for PGExplainer and 0.114 for GNNExplainer.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use K-FactExplainer instead of the strongest listed baseline | GNN explanation methods · BA-Shapes, BA-Community, BA-2motifs, MUTAG | AUC-ROC: BA-Shapes: 0.999 -> 1.000; BA-Community: 0.957 -> 0.974; BA-2motifs: 0.755 -> 0.821; MUTAG: 0.873 -> 0.915 | Helped |
| Use K-FactExplainer instead of the strongest listed baseline | GNN explanation methods · Tree-Circles and Tree-Grid | AUC-ROC: Tree-Circles: 0.902 -> 0.779; Tree-Grid: 0.927 -> 0.770 | Hurt |
| Increase k from 1 to 60 (ablation) | K-FactExplainer · BA-Community, Tree-Circles, Tree-Grid, BA-2motifs, MUTAG | AUC-ROC: BA-Community: 0.850 -> 0.952; Tree-Circles: 0.758 -> 0.778; Tree-Grid: 0.711 -> 0.770; BA-2motifs: 0.580 -> 0.588; MUTAG | Helped |
| Increase k from 1 to 60 (ablation) | K-FactExplainer · BA-Shapes | AUC-ROC: 1.000 -> 1.000 | No clear effect |
| Increase k from 1 to 3 (ablation) | K-FactExplainer · BA-4motifs | Coverage Rate: 0.442 -> 0.712 | Helped |
| Increase k from 1 to 3 (ablation) | K-FactExplainer · BA-4motifs | AUC: 0.761 -> 0.789 | Helped |
| Increase k from 1 to 60 with hidden size 20 (ablation) | K-FactExplainer · BA-Community and Tree-Circles | AUC-ROC: BA-Community: 0.850 -> 0.952; Tree-Circles: 0.758 -> 0.778 | Helped |
| Increase k from 1 to 60 with hidden size 80 (ablation) | K-FactExplainer · BA-Community and Tree-Circles | AUC-ROC: BA-Community: 0.893 -> 0.897; Tree-Circles: 0.871 -> 0.870 | No clear effect |
Surprising findings
- On Tree-Grid and Tree-Circles, K-FactExplainer does not clearly beat the best baselines (e.g., DEGREE at 0.902 on Tree-Circles vs 0.779).
- Increasing k yields no gain when the GNN hidden dimension is 80, suggesting the gains come from mitigating lossy aggregation in low-dimensional GNNs.
Limitations
- Theoretical guarantees are proven for a specific synthetic multi-motif task with simplifying assumptions (Erdos-Renyi background, separated motifs).
- The bootstrapping procedure only approximates the number of required explainers using a PGExplainer output rather than true motifs.
- Inference time grows noticeably with k (e.g., 5.75 ms vs 4.27 ms for PGExplainer at k=60 on BA-Shapes).
Experimental setup
Datasets: BA-Shapes BA-Community Tree-Circles Tree-Grid BA-2motifs MUTAG
Benchmarks: BA-Shapes BA-Community Tree-Circles Tree-Grid BA-2motifs MUTAG
Metrics: AUC-ROC on edges coverage rate inference time
Baselines: GNNExplainer PGExplainer RGExplainer DEGREE GRAD ATT
Builds on: GNNExplainer PGExplainer Graph Information Bottleneck
Closest papers by meaning
- GraphTrail: Translating GNN Predictions into Human-Interpretable Logical Rules (NeurIPS 2024 · similarity 0.89)
- Self-Interpretable Graph Learning with Sufficient and Necessary Explanations (AAAI 2024 · similarity 0.89)
- Stratified GNN Explanations through Sufficient Expansion (AAAI 2024 · similarity 0.89)
- Towards Robust Fidelity for Evaluating Explainability of Graph Neural Networks (ICLR 2024 · similarity 0.89)
- RegExplainer: Generating Explanations for Graph Neural Networks in Regression Tasks (NeurIPS 2024 · similarity 0.89)
- Higher Order Structures for Graph Explanations (AAAI 2025 · 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.