# Cardinality-Minimal Explanations for Monotonic Neural Networks

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 57 references that are in the map.
- First posted on arXiv 19 May 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Axiomatic Attribution for Deep Networks](https://mlsanity.com/paper/1703.01365/) (2017)
- [Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Maps](https://mlsanity.com/paper/1312.6034/) (2013)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Learning Important Features Through Propagating Activation Differences](https://mlsanity.com/paper/1704.02685/) (2017)
- [Sanity Checks for Saliency Maps](https://mlsanity.com/paper/1810.03292/) (2018)
- [Deep Learning in Neural Networks: An Overview](https://mlsanity.com/paper/1404.7828/) (2014)
- [Deep Speech: Scaling up end-to-end speech recognition](https://mlsanity.com/paper/1412.5567/) (2014)
- [The many Shapley values for model explanation](https://mlsanity.com/paper/1908.08474/) (2019)
- [Counterfactual Visual Explanations](https://mlsanity.com/paper/1904.07451/) (2019)
- [Explanations based on the Missing: Towards Contrastive Explanations with Pertinent Negatives](https://mlsanity.com/paper/1802.07623/) (2018)
- [Explaining NonLinear Classification Decisions with Deep Taylor Decomposition](https://mlsanity.com/paper/1512.02479/) (2015)
- [Real Time Image Saliency for Black Box Classifiers](https://mlsanity.com/paper/1705.07857/) (2017)
- [Deep Learning for Case-Based Reasoning through Prototypes: A Neural Network that Explains Its Predictions](https://mlsanity.com/paper/1710.04806/) (2017)
- [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)
- [CF-GNNExplainer: Counterfactual Explanations for Graph Neural Networks](https://mlsanity.com/paper/2102.03322/) (2021)
- [Explaining Deep Neural Networks with a Polynomial Time Algorithm for Shapley Values Approximation](https://mlsanity.com/paper/1903.10992/) (2019)
- [Model Interpretability through the Lens of Computational Complexity](https://mlsanity.com/paper/2010.12265/) (2020)
- [Robust Counterfactual Explanations on Graph Neural Networks](https://mlsanity.com/paper/2107.04086/) (2021)
- [On Explaining Random Forests with SAT](https://mlsanity.com/paper/2105.10278/) (2021)
- [Certified Monotonic Neural Networks](https://mlsanity.com/paper/2011.10219/) (2020)
- [Explanations for Monotonic Classifiers](https://mlsanity.com/paper/2106.00154/) (2021)
- [On Tractable Representations of Binary Neural Networks](https://mlsanity.com/paper/2004.02082/) (2020)
- [Provably efficient, succinct, and precise explanations](https://mlsanity.com/paper/2111.01576/) (2021)
- [Interpreting Neural Network Judgments via Minimal, Stable, and Symbolic Corrections](https://mlsanity.com/paper/1802.07384/) (2018)
- [Monotonic classification: an overview on algorithms, performance measures and data sets](https://mlsanity.com/paper/1811.07155/) (2018)
- [Three Modern Roles for Logic in AI](https://mlsanity.com/paper/2004.08599/) (2020)
- [Equivalent and Approximate Transformations of Deep Neural Networks](https://mlsanity.com/paper/1905.11428/) (2019)

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

- [Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanations](https://mlsanity.com/paper/2506.08505/) (2025)
- [Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons](https://mlsanity.com/paper/2502.03391/) (2025)
- [Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guarantees](https://mlsanity.com/paper/2602.16823/) (2026)
- [Even-if Explanations: Formal Foundations, Priorities and Complexity](https://mlsanity.com/paper/2401.10938/) (2024)
- [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026)
- [Understanding User Preferences in Explainable Artificial Intelligence: A Survey and a Mapping Function Proposal](https://mlsanity.com/paper/2302.03180/) (2023)
- [Provably Explaining Neural Additive Models](https://mlsanity.com/paper/2602.17530/) (2026)
- [CIDR: A Cooperative Integrated Dynamic Refining Method for Minimal Feature Removal Problem](https://mlsanity.com/paper/2312.08157/) (2023)

## Abstract (arXiv)

In recent years, there has been increasing interest in explanation methods for neural model predictions that offer precise formal guarantees. These include abductive (respectively, contrastive) methods, which aim to compute minimal subsets of input features that are sufficient for a given prediction to hold (respectively, to change a given prediction). The corresponding decision problems are, however, known to be intractable. In this paper, we investigate whether tractability can be regained by focusing on neural models implementing a monotonic function. Although the relevant decision problems remain intractable, we can show that they become solvable in polynomial time by means of greedy algorithms if we additionally assume that the activation functions are continuous everywhere and differentiable almost everywhere. Our experiments suggest favourable performance of our algorithms.