mlsanityData to 7 Oct 2026

Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective

arXiv 2502.02719 ↗First posted 4 Feb 2025cs.LGcited by 10

Not on the map. Why?

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.

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

Builds on

58 of 86 references.

References · 58

  1. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 6,979
  2. 2018How Powerful are Graph Neural Networks?cited by 4,355
  3. 2017Axiomatic Attribution for Deep Networkscited by 3,350
  4. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  5. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  6. 2017MoleculeNet: A Benchmark for Molecular Machine Learningcited by 1,037
  7. 2019GNNExplainer: Generating Explanations for Graph Neural Networkscited by 735
  8. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  9. 2020Parameterized Explainer for Graph Neural Networkcited by 423
  10. 2020Explainability in Graph Neural Networks: A Taxonomic Surveycited by 383
  11. 2021On Explainability of Graph Neural Networks via Subgraph Explorationscited by 280
  12. 2018Formal Limitations on the Measurement of Mutual Informationcited by 189
38 more
  1. 2022Discovering Invariant Rationales for Graph Neural Networkscited by 186
  2. 2022Interpretable and Generalizable Graph Learning via Stochastic Attention Mechanismcited by 171
  3. 2019Understanding Attention and Generalization in Graph Neural Networkscited by 169
  4. 2020Graph Information Bottleneckcited by 168
  5. 2022Learning Causally Invariant Representations for Out-of-Distribution Generalization on Graphscited by 144
  6. 2022GOOD: A Graph Out-of-Distribution Benchmarkcited by 140
  7. 2018A Symbolic Approach to Explaining Bayesian Network Classifierscited by 130
  8. 2020Graph Information Bottleneck for Subgraph Recognitioncited by 119
  9. 2021Do Concept Bottleneck Models Learn as Intended?cited by 114
  10. 2024Faithfulness vs. Plausibility: On the (Un)Reliability of Explanations from Large Language Modelscited by 104
  11. 2022Evaluating Explainability for Graph Neural Networkscited by 85
  12. 2021The Logic of Graph Neural Networkscited by 84
  13. 2022Learning and Evaluating Graph Neural Network Explanations based on Counterfactual and Factual Reasoningcited by 78
  14. 2021Towards Self-Explainable Graph Neural Networkcited by 75
  15. 2022Global Explainability of GNNs via Logic Combination of Learned Conceptscited by 64
  16. 2022Anti-Symmetric DGN: a stable architecture for Deep Graph Networkscited by 58
  17. 2022GraphFramEx: Towards Systematic Evaluation of Explainability Methods for Graph Neural Networkscited by 57
  18. 2020Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delaycited by 56
  19. 2022Leveraging Explanations in Interactive Machine Learning: An Overviewcited by 52
  20. 2021Entropy-based Logic Explanations of Neural Networkscited by 51
  21. 2021GLocalX -- From Local to Global Explanations of Black Box AI Modelscited by 48
  22. 2022Logic-Based Explainability in Machine Learningcited by 47
  23. 2021Improving Subgraph Recognition with Variational Graph Information Bottleneckcited by 45
  24. 2022Explaining the Explainers in Graph Neural Networks: a Comparative Studycited by 34
  25. 2022Causal Explanations and XAIcited by 30
  26. 2023Joint Learning of Label and Environment Causal Independence for Graph Out-of-Distribution Generalizationcited by 29
  27. 2022Interpretable Geometric Deep Learning via Learnable Randomness Injectioncited by 27
  28. 2023Graph Neural Networks Use Graphs When They Shouldn'tcited by 25
  29. 2021Probabilistic Sufficient Explanationscited by 24
  30. 2024The Interpretable and Effective Graph Neural Additive Networkscited by 19
  31. 2022Towards Prototype-Based Self-Explainable Graph Neural Networkcited by 14
  32. 2024Reconsidering Faithfulness in Regular, Self-Explainable and Domain Invariant GNNscited by 14
  33. 2020Graph Neural Networks Including Sparse Interpretabilitycited by 13
  34. 2024How Interpretable Are Interpretable Graph Neural Networks?cited by 13
  35. 2023On Formal Feature Attribution and Its Approximationcited by 11
  36. 2024Auditing Local Explanations is Hardcited by 8
  37. 2022L2XGNN: Learning to Explain Graph Neural Networkscited by 7
  38. 2022Towards Training GNNs using Explanation Directed Message Passingcited by 7

50 most cited of 58 All 58 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 4; 2026: 6.

10 papers.

  1. 2025Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanationscited by 13
  2. 2026Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guaranteescited by 10
  3. 2026GNN Explanations that do not Explain and How to find Themcited by 3
  4. 2025Informative Post-Hoc Explanations Only Exist for Simple Functionscited by 2
  5. 2025Database Views as Explanations for Relational Deep Learningcited by 1
  6. 2026Provably Explaining Neural Additive Modelscited by 1
  7. 2026Unifying Formal Explanations: A Complexity-Theoretic Perspectivecited by 1
  8. 2025Prime Implicant Explanations for Reaction Feasibility Predictioncited by 0
  9. 2026Exploring Concept Subspace for Self-explainable Text-Attributed Graph Learningcited by 0
  10. 2026Why Self-Inconsistency Arises in GNN Explanations and How to Exploit Itcited by 0