# Axiomatic Characterisations of Sample-based Explainers

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 41 references that are in the map.
- First posted on arXiv 9 Aug 2024.

## Builds on (most cited first, 15 of 15)

- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [Explanations based on the Missing: Towards Contrastive Explanations with Pertinent Negatives](https://mlsanity.com/paper/1802.07623/) (2018)
- [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018)
- [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018)
- [On The Reasons Behind Decisions](https://mlsanity.com/paper/2002.09284/) (2020)
- [On Explaining Random Forests with SAT](https://mlsanity.com/paper/2105.10278/) (2021)
- [GLocalX -- From Local to Global Explanations of Black Box AI Models](https://mlsanity.com/paper/2101.07685/) (2021)
- [On Tackling Explanation Redundancy in Decision Trees](https://mlsanity.com/paper/2205.09971/) (2022)
- [SAT-Based Rigorous Explanations for Decision Lists](https://mlsanity.com/paper/2105.06782/) (2021)
- [Trading Complexity for Sparsity in Random Forest Explanations](https://mlsanity.com/paper/2108.05276/) (2021)
- [Global Aggregations of Local Explanations for Black Box models](https://mlsanity.com/paper/1907.03039/) (2019)
- [ASTERYX : A model-Agnostic SaT-basEd appRoach for sYmbolic and score-based eXplanations](https://mlsanity.com/paper/2206.11900/) (2022)
- [Computing Abductive Explanations for Boosted Trees](https://mlsanity.com/paper/2209.07740/) (2022)
- [On the Complexity of Enumerating Prime Implicants from Decision-DNNF Circuits](https://mlsanity.com/paper/2301.13328/) (2023)

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

- [Explaining Tournament Solutions with Minimal Supports](https://mlsanity.com/paper/2509.09312/) (2025)
- [Ranking Counterfactual Explanations](https://mlsanity.com/paper/2503.15817/) (2025)
- [Towards Rigorous Explainability by Feature Attribution](https://mlsanity.com/paper/2604.15898/) (2026)

## Abstract (arXiv)

Explaining decisions of black-box classifiers is both important and computationally challenging. In this paper, we scrutinize explainers that generate feature-based explanations from samples or datasets. We start by presenting a set of desirable properties that explainers would ideally satisfy, delve into their relationships, and highlight incompatibilities of some of them. We identify the entire family of explainers that satisfy two key properties which are compatible with all the others. Its instances provide sufficient reasons, called weak abductive explanations.We then unravel its various subfamilies that satisfy subsets of compatible properties. Indeed, we fully characterize all the explainers that satisfy any subset of compatible properties. In particular, we introduce the first (broad family of) explainers that guarantee the existence of explanations and their global consistency.We discuss some of its instances including the irrefutable explainer and the surrogate explainer whose explanations can be found in polynomial time.