# Efficient Computation of Shap Explanation Scores for Neural Network Classifiers via Knowledge Compilation

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 39 references that are in the map.
- First posted on arXiv 11 Mar 2023.

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

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [A Survey Of Methods For Explaining Black Box Models](https://mlsanity.com/paper/1802.01933/) (2018)
- [Binary Neural Networks: A Survey](https://mlsanity.com/paper/2004.03333/) (2020)
- [Explainable Deep Learning: A Field Guide for the Uninitiated](https://mlsanity.com/paper/2004.14545/) (2020)
- [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)
- [Verifying Properties of Binarized Deep Neural Networks](https://mlsanity.com/paper/1709.06662/) (2017)
- [A comprehensive review of Binary Neural Network](https://mlsanity.com/paper/2110.06804/) (2021)
- [On Tractable Representations of Binary Neural Networks](https://mlsanity.com/paper/2004.02082/) (2020)
- [On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results](https://mlsanity.com/paper/2104.08015/) (2021)
- [Causality-based Explanation of Classification Outcomes](https://mlsanity.com/paper/2003.06868/) (2020)
- [SDDs are Exponentially More Succinct than OBDDs](https://mlsanity.com/paper/1601.00501/) (2016)
- [Smoothing Structured Decomposable Circuits](https://mlsanity.com/paper/1906.00311/) (2019)
- [Declarative Approaches to Counterfactual Explanations for Classification](https://mlsanity.com/paper/2011.07423/) (2020)
- [On the Relative Succinctness of Sentential Decision Diagrams](https://mlsanity.com/paper/1802.04544/) (2018)
- [On Compiling DNNFs without Determinism](https://mlsanity.com/paper/1709.07092/) (2017)
- [Variable Shift SDD: A More Succinct Sentential Decision Diagram](https://mlsanity.com/paper/2004.02502/) (2020)

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

- [Attribution-Scores in Data Management and Explainable Machine Learning](https://mlsanity.com/paper/2308.00184/) (2023)
- [The Distributional Uncertainty of the SHAP score in Explainable Machine Learning](https://mlsanity.com/paper/2401.12731/) (2024)
- [Reconciling Consistency-Based Diagnosis with Actual-Causality-Based Explanations](https://mlsanity.com/paper/2605.08688/) (2026)

## Abstract (arXiv)

The use of Shap scores has become widespread in Explainable AI. However, their computation is in general intractable, in particular when done with a black-box classifier, such as neural network. Recent research has unveiled classes of open-box Boolean Circuit classifiers for which Shap can be computed efficiently. We show how to transform binary neural networks into those circuits for efficient Shap computation.We use logic-based knowledge compilation techniques. The performance gain is huge, as we show in the light of our experiments.