mlsanityData to 14 Oct 2026

On Efficiently Explaining Graph-Based Classifiers

arXiv 2106.01350 ↗First posted 2 Jun 2021cs.AI cs.LGcited by 37

Not on the map. Why?

Abstract (arXiv)

Recent work has shown that not only decision trees (DTs) may not be interpretable but also proposed a polynomial-time algorithm for computing one PI-explanation of a DT. This paper shows that for a wide range of classifiers, globally referred to as decision graphs, and which include decision trees and binary decision diagrams, but also their multi-valued variants, there exist polynomial-time algorithms for computing one PI-explanation. In addition, the paper also proposes a polynomial-time algorithm for computing one contrastive explanation. These novel algorithms build on explanation graphs (XpG's). XpG's denote a graph representation that enables both theoretical and practically efficient computation of explanations for decision graphs. Furthermore, the paper proposes a practically efficient solution for the enumeration of explanations, and studies the complexity of deciding whether a given feature is included in some explanation. For the concrete case of decision trees, the paper shows that the set of all contrastive explanations can be enumerated in polynomial time. Finally, the experimental results validate the practical applicability of the algorithms proposed in the paper on a wide range of publicly available benchmarks.

Key facts. Cited by 37 papers in the map (data through 14 Oct 2026). Builds on 26 of its 96 references that are in the map. First posted on arXiv 2 Jun 2021.

Builds on

26 of 96 references.

References · 26

  1. 2017A Unified Approach to Interpreting Model Predictionscited by 6,555
  2. 2016"Why Should I Trust You?": Explaining the Predictions of Any Classifiercited by 5,070
  3. 2017Explanation in Artificial Intelligence: Insights from the Social Sciencescited by 1,206
  4. 2018A Survey Of Methods For Explaining Black Box Modelscited by 973
  5. 2016The Mythos of Model Interpretabilitycited by 721
  6. 2014OpenML: networked science in machine learningcited by 526
  7. 2019Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methodscited by 443
  8. 2017Methods for Interpreting and Understanding Deep Neural Networkscited by 345
  9. 2016Model-Agnostic Interpretability of Machine Learningcited by 219
  10. 2018Abduction-Based Explanations for Machine Learning Modelscited by 160
  11. 2017PMLB: A Large Benchmark Suite for Machine Learning Evaluation and Comparisoncited by 140
  12. 2018A Symbolic Approach to Explaining Bayesian Network Classifierscited by 131
14 more
  1. 2019"How do I fool you?": Manipulating User Trust via Misleading Black Box Explanationscited by 111
  2. 2020On The Reasons Behind Decisionscited by 100
  3. 2020On the Tractability of SHAP Explanationscited by 92
  4. 2020Model Interpretability through the Lens of Computational Complexitycited by 75
  5. 2020Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delaycited by 57
  6. 2021On Explaining Random Forests with SATcited by 57
  7. 2020On Explaining Decision Treescited by 49
  8. 2018The Challenge of Crafting Intelligible Intelligencecited by 47
  9. 2021On the Computational Intelligibility of Boolean Classifierscited by 40
  10. 2021SAT-Based Rigorous Explanations for Decision Listscited by 40
  11. 2021Explanations for Monotonic Classifierscited by 39
  12. 2019Can I Trust the Explainer? Verifying Post-hoc Explanatory Methodscited by 38
  13. 2019On Validating, Repairing and Refining Heuristic ML Explanationscited by 32
  14. 2021Efficient Explanations With Relevant Setscited by 12

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 9; 2023: 7; 2024: 4; 2025: 9; 2026: 7.

37 papers.

Sort:

  1. 2022Logic-Based Explainability in Machine Learningcited by 48
  2. 2022On Tackling Explanation Redundancy in Decision Treescited by 44
  3. 2022On Computing Probabilistic Explanations for Decision Treescited by 35
  4. 2023The Inadequacy of Shapley Values for Explainabilitycited by 31
  5. 2023Formally Explaining Neural Networks within Reactive Systemscited by 24
  6. 2022On the Computation of Necessary and Sufficient Explanationscited by 23
  7. 2022Computing Abductive Explanations for Boosted Treescited by 23
  8. 2023Logic for Explainable AIcited by 23
  9. 2024Local vs. Global Interpretability: A Computational Complexity Perspectivecited by 23
  10. 2024Distance-Restricted Explanations: Theoretical Underpinnings & Efficient Implementationcited by 21
  11. 2022On Computing Probabilistic Abductive Explanationscited by 18
  12. 2025Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanationscited by 13
25 more
  1. 2023Disproving XAI Myths with Formal Methods -- Initial Resultscited by 12
  2. 2025Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasonscited by 12
  3. 2024Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretationcited by 11
  4. 2025Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanationscited by 10
  5. 2021On the Explanatory Power of Decision Treescited by 6
  6. 2022On Computing Relevant Features for Explaining NBCscited by 5
  7. 2023A Refutation of Shapley Values for Explainabilitycited by 4
  8. 2023Refutation of Shapley Values for XAI -- Additional Evidencecited by 4
  9. 2025Additive Models Explained: A Computational Complexity Approachcited by 3
  10. 2026FAME: Formal Abstract Minimal Explanation for Neural Networkscited by 3
  11. 2022On Deciding Feature Membership in Explanations of SDD & Related Classifierscited by 2
  12. 2024Learning Model Agnostic Explanations via Constraint Programmingcited by 2
  13. 2026Unifying Formal Explanations: A Complexity-Theoretic Perspectivecited by 2
  14. 2023Finding Minimum-Cost Explanations for Predictions made by Tree Ensemblescited by 1
  15. 2025Feature Relevancy, Necessity and Usefulness: Complexity and Algorithmscited by 1
  16. 2025Uncovering Bugs in Formal Explainers: A Case Study with PyXAIcited by 1
  17. 2025Extracting Robust Register Automata from Neural Networks over Data Sequencescited by 1
  18. 2026Provably Explaining Neural Additive Modelscited by 1
  19. 2022Rectifying Mono-Label Boolean Classifierscited by 0
  20. 2025Rigorous Feature Importance Scores based on Shapley Value and Banzhaf Indexcited by 0
  21. 2025Efficient & Correct Predictive Equivalence for Decision Treescited by 0
  22. 2026On the Hardness of Computing Counterfactual and Semifactual Explanations in XAIcited by 0
  23. 2026Rigorous Explanations for Tree Ensemblescited by 0
  24. 2026Towards Rigorous Explainability by Feature Attributioncited by 0
  25. 2026ExplAIner: A Declarative Query Language for Explaining Classification Modelscited by 0