# Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 58 of its 86 references that are in the map.
- First posted on arXiv 4 Feb 2025.

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

- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [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)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (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)
- [Formal Limitations on the Measurement of Mutual Information](https://mlsanity.com/paper/1811.04251/) (2018)
- [Discovering Invariant Rationales for Graph Neural Networks](https://mlsanity.com/paper/2201.12872/) (2022)
- [Interpretable and Generalizable Graph Learning via Stochastic Attention Mechanism](https://mlsanity.com/paper/2201.12987/) (2022)
- [Understanding Attention and Generalization in Graph Neural Networks](https://mlsanity.com/paper/1905.02850/) (2019)
- [Graph Information Bottleneck](https://mlsanity.com/paper/2010.12811/) (2020)
- [Learning Causally Invariant Representations for Out-of-Distribution Generalization on Graphs](https://mlsanity.com/paper/2202.05441/) (2022)
- [GOOD: A Graph Out-of-Distribution Benchmark](https://mlsanity.com/paper/2206.08452/) (2022)
- [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018)
- [Graph Information Bottleneck for Subgraph Recognition](https://mlsanity.com/paper/2010.05563/) (2020)
- [Do Concept Bottleneck Models Learn as Intended?](https://mlsanity.com/paper/2105.04289/) (2021)
- [Faithfulness vs. Plausibility: On the (Un)Reliability of Explanations from Large Language Models](https://mlsanity.com/paper/2402.04614/) (2024)
- [Evaluating Explainability for Graph Neural Networks](https://mlsanity.com/paper/2208.09339/) (2022)
- [The Logic of Graph Neural Networks](https://mlsanity.com/paper/2104.14624/) (2021)
- [Learning and Evaluating Graph Neural Network Explanations based on Counterfactual and Factual Reasoning](https://mlsanity.com/paper/2202.08816/) (2022)
- [Towards Self-Explainable Graph Neural Network](https://mlsanity.com/paper/2108.12055/) (2021)
- [Global Explainability of GNNs via Logic Combination of Learned Concepts](https://mlsanity.com/paper/2210.07147/) (2022)
- [Anti-Symmetric DGN: a stable architecture for Deep Graph Networks](https://mlsanity.com/paper/2210.09789/) (2022)
- [GraphFramEx: Towards Systematic Evaluation of Explainability Methods for Graph Neural Networks](https://mlsanity.com/paper/2206.09677/) (2022)
- [Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay](https://mlsanity.com/paper/2008.05803/) (2020)

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

- [Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanations](https://mlsanity.com/paper/2506.08505/) (2025)
- [Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guarantees](https://mlsanity.com/paper/2602.16823/) (2026)
- [GNN Explanations that do not Explain and How to find Them](https://mlsanity.com/paper/2601.20815/) (2026)
- [Informative Post-Hoc Explanations Only Exist for Simple Functions](https://mlsanity.com/paper/2508.11441/) (2025)
- [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026)
- [Database Views as Explanations for Relational Deep Learning](https://mlsanity.com/paper/2509.09482/) (2025)
- [Prime Implicant Explanations for Reaction Feasibility Prediction](https://mlsanity.com/paper/2510.09226/) (2025)
- [Provably Explaining Neural Additive Models](https://mlsanity.com/paper/2602.17530/) (2026)
- [Exploring Concept Subspace for Self-explainable Text-Attributed Graph Learning](https://mlsanity.com/paper/2604.11986/) (2026)
- [Why Self-Inconsistency Arises in GNN Explanations and How to Exploit It](https://mlsanity.com/paper/2605.07527/) (2026)
- [Beyond Trained Models: Compiling GNNs for a Sound Explainer Benchmark](https://mlsanity.com/paper/2610.03526/) (2026)

## Abstract (arXiv)

Self-Explainable Graph Neural Networks (SE-GNNs) are popular explainable-by-design GNNs, but their explanations' properties and limitations are not well understood. Our first contribution fills this gap by formalizing the explanations extracted by some popular SE-GNNs, referred to as Minimal Explanations (MEs), and comparing them to established notions of explanations, namely Prime Implicant (PI) and faithful explanations. Our analysis reveals that MEs match PI explanations for a restricted but significant family of tasks. In general, however, they can be less informative than PI explanations and are surprisingly misaligned with widely accepted notions of faithfulness. Although faithful and PI explanations are informative, they are intractable to find and we show that they can be prohibitively large. Given these observations, a natural choice is to augment SE-GNNs with alternative modalities of explanations taking care of SE-GNNs' limitations. To this end, we propose Dual-Channel GNNs that integrate a white-box rule extractor and a standard SE-GNN, adaptively combining both channels. Our experiments show that even a simple instantiation of Dual-Channel GNNs can recover succinct rules and perform on par or better than widely used SE-GNNs.