# On Efficiently Explaining Graph-Based Classifiers

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

## 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 (most cited first, 26 of 26)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Explanation in Artificial Intelligence: Insights from the Social Sciences](https://mlsanity.com/paper/1706.07269/) (2017)
- [A Survey Of Methods For Explaining Black Box Models](https://mlsanity.com/paper/1802.01933/) (2018)
- [The Mythos of Model Interpretability](https://mlsanity.com/paper/1606.03490/) (2016)
- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methods](https://mlsanity.com/paper/1911.02508/) (2019)
- [Methods for Interpreting and Understanding Deep Neural Networks](https://mlsanity.com/paper/1706.07979/) (2017)
- [Model-Agnostic Interpretability of Machine Learning](https://mlsanity.com/paper/1606.05386/) (2016)
- [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018)
- [PMLB: A Large Benchmark Suite for Machine Learning Evaluation and Comparison](https://mlsanity.com/paper/1703.00512/) (2017)
- [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018)
- ["How do I fool you?": Manipulating User Trust via Misleading Black Box Explanations](https://mlsanity.com/paper/1911.06473/) (2019)
- [On The Reasons Behind Decisions](https://mlsanity.com/paper/2002.09284/) (2020)
- [On the Tractability of SHAP Explanations](https://mlsanity.com/paper/2009.08634/) (2020)
- [Model Interpretability through the Lens of Computational Complexity](https://mlsanity.com/paper/2010.12265/) (2020)
- [Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay](https://mlsanity.com/paper/2008.05803/) (2020)
- [On Explaining Random Forests with SAT](https://mlsanity.com/paper/2105.10278/) (2021)
- [On Explaining Decision Trees](https://mlsanity.com/paper/2010.11034/) (2020)
- [The Challenge of Crafting Intelligible Intelligence](https://mlsanity.com/paper/1803.04263/) (2018)
- [On the Computational Intelligibility of Boolean Classifiers](https://mlsanity.com/paper/2104.06172/) (2021)
- [SAT-Based Rigorous Explanations for Decision Lists](https://mlsanity.com/paper/2105.06782/) (2021)
- [Explanations for Monotonic Classifiers](https://mlsanity.com/paper/2106.00154/) (2021)
- [Can I Trust the Explainer? Verifying Post-hoc Explanatory Methods](https://mlsanity.com/paper/1910.02065/) (2019)
- [On Validating, Repairing and Refining Heuristic ML Explanations](https://mlsanity.com/paper/1907.02509/) (2019)
- [Efficient Explanations With Relevant Sets](https://mlsanity.com/paper/2106.00546/) (2021)

## Built on by (most cited first, 30 of 37)

- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [On Tackling Explanation Redundancy in Decision Trees](https://mlsanity.com/paper/2205.09971/) (2022)
- [On Computing Probabilistic Explanations for Decision Trees](https://mlsanity.com/paper/2207.12213/) (2022)
- [The Inadequacy of Shapley Values for Explainability](https://mlsanity.com/paper/2302.08160/) (2023)
- [Formally Explaining Neural Networks within Reactive Systems](https://mlsanity.com/paper/2308.00143/) (2023)
- [On the Computation of Necessary and Sufficient Explanations](https://mlsanity.com/paper/2203.10451/) (2022)
- [Computing Abductive Explanations for Boosted Trees](https://mlsanity.com/paper/2209.07740/) (2022)
- [Logic for Explainable AI](https://mlsanity.com/paper/2305.05172/) (2023)
- [Local vs. Global Interpretability: A Computational Complexity Perspective](https://mlsanity.com/paper/2406.02981/) (2024)
- [Distance-Restricted Explanations: Theoretical Underpinnings & Efficient Implementation](https://mlsanity.com/paper/2405.08297/) (2024)
- [On Computing Probabilistic Abductive Explanations](https://mlsanity.com/paper/2212.05990/) (2022)
- [Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanations](https://mlsanity.com/paper/2506.08505/) (2025)
- [Disproving XAI Myths with Formal Methods -- Initial Results](https://mlsanity.com/paper/2306.01744/) (2023)
- [Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons](https://mlsanity.com/paper/2502.03391/) (2025)
- [Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation](https://mlsanity.com/paper/2408.03915/) (2024)
- [Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations](https://mlsanity.com/paper/2501.06078/) (2025)
- [On the Explanatory Power of Decision Trees](https://mlsanity.com/paper/2108.05266/) (2021)
- [On Computing Relevant Features for Explaining NBCs](https://mlsanity.com/paper/2207.04748/) (2022)
- [A Refutation of Shapley Values for Explainability](https://mlsanity.com/paper/2309.03041/) (2023)
- [Refutation of Shapley Values for XAI -- Additional Evidence](https://mlsanity.com/paper/2310.00416/) (2023)
- [Additive Models Explained: A Computational Complexity Approach](https://mlsanity.com/paper/2510.21292/) (2025)
- [FAME: Formal Abstract Minimal Explanation for Neural Networks](https://mlsanity.com/paper/2603.10661/) (2026)
- [On Deciding Feature Membership in Explanations of SDD & Related Classifiers](https://mlsanity.com/paper/2202.07553/) (2022)
- [Learning Model Agnostic Explanations via Constraint Programming](https://mlsanity.com/paper/2411.08478/) (2024)
- [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026)
- [Finding Minimum-Cost Explanations for Predictions made by Tree Ensembles](https://mlsanity.com/paper/2303.09271/) (2023)
- [Feature Relevancy, Necessity and Usefulness: Complexity and Algorithms](https://mlsanity.com/paper/2505.09640/) (2025)
- [Uncovering Bugs in Formal Explainers: A Case Study with PyXAI](https://mlsanity.com/paper/2511.03169/) (2025)
- [Extracting Robust Register Automata from Neural Networks over Data Sequences](https://mlsanity.com/paper/2511.19100/) (2025)
- [Provably Explaining Neural Additive Models](https://mlsanity.com/paper/2602.17530/) (2026)

## 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.