# Feature Relevancy, Necessity and Usefulness: Complexity and Algorithms

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 50 references that are in the map.
- First posted on arXiv 6 May 2025.

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

- [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)
- [A Survey on Explainable Artificial Intelligence (XAI): Towards Medical XAI](https://mlsanity.com/paper/1907.07374/) (2019)
- [European Union regulations on algorithmic decision-making and a "right to explanation"](https://mlsanity.com/paper/1606.08813/) (2016)
- [Reachability Analysis of Deep Neural Networks with Provable Guarantees](https://mlsanity.com/paper/1805.02242/) (2018)
- [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)
- [Model Interpretability through the Lens of Computational Complexity](https://mlsanity.com/paper/2010.12265/) (2020)
- [Shapley values for feature selection: The good, the bad, and the axioms](https://mlsanity.com/paper/2102.10936/) (2021)
- [On Explaining Decision Trees](https://mlsanity.com/paper/2010.11034/) (2020)
- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [On Efficiently Explaining Graph-Based Classifiers](https://mlsanity.com/paper/2106.01350/) (2021)
- [On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results](https://mlsanity.com/paper/2104.08015/) (2021)
- [The Inadequacy of Shapley Values for Explainability](https://mlsanity.com/paper/2302.08160/) (2023)
- [Causality-based Explanation of Classification Outcomes](https://mlsanity.com/paper/2003.06868/) (2020)
- [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)
- [Feature Necessity & Relevancy in ML Classifier Explanations](https://mlsanity.com/paper/2210.15675/) (2022)
- [On the Computational Tractability of the (Many) Shapley Values](https://mlsanity.com/paper/2502.12295/) (2025)
- [Efficient Explanations for Knowledge Compilation Languages](https://mlsanity.com/paper/2107.01654/) (2021)
- [Statistical Significance of Feature Importance Rankings](https://mlsanity.com/paper/2401.15800/) (2024)
- [On the Explanatory Power of Decision Trees](https://mlsanity.com/paper/2108.05266/) (2021)
- [The minimal hitting set generation problem: algorithms and computation](https://mlsanity.com/paper/1601.02939/) (2016)
- [Lower Bounds for Approximate Knowledge Compilation](https://mlsanity.com/paper/2011.13721/) (2020)

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

- [MinShap: A Shapley-Based Framework for Feature Redundancy](https://mlsanity.com/paper/2604.15107/) (2026)

## Abstract (arXiv)

Given a classification model and a prediction for some input, there are heuristic strategies for ranking features according to their importance in regard to the prediction. One common approach to this task is rooted in propositional logic and the notion of textitsufficient reason. Through this concept, the categories of relevant and necessary features were proposed in order to identify the crucial aspects of the input. This paper improves the existing techniques and algorithms for deciding which are the relevant and/or necessary features, showing in particular that necessity can be detected efficiently in complex models such as neural networks. We also generalize the notion of relevancy and study associated problems. Moreover, we present a new global notion (i.e. that intends to explain whether a feature is important for the behavior of the model in general, not depending on a particular input) of textitusefulness and prove that it is related to relevancy and necessity. Furthermore, we develop efficient algorithms for detecting it in decision trees and other more complex models, and experiment on three datasets to analyze its practical utility.