# Using Constraints to Discover Sparse and Alternative Subgroup Descriptions

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

## Key facts

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

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

- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (2019)
- [Efficient Search for Diverse Coherent Explanations](https://mlsanity.com/paper/1901.04909/) (2019)
- [Feature Selection: A Data Perspective](https://mlsanity.com/paper/1601.07996/) (2016)
- [Scaling Guarantees for Nearest Counterfactual Explanations](https://mlsanity.com/paper/2010.04965/) (2020)
- [A multi-component framework for the analysis and design of explainable artificial intelligence](https://mlsanity.com/paper/2005.01908/) (2020)
- [Interpretable Clustering via Multi-Polytope Machines](https://mlsanity.com/paper/2112.05653/) (2021)
- [Robust subgroup discovery](https://mlsanity.com/paper/2103.13686/) (2021)
- [REDS: Rule Extraction for Discovering Scenarios](https://mlsanity.com/paper/1910.01713/) (2019)
- [Efficient Subspace Search in Data Streams](https://mlsanity.com/paper/2011.06959/) (2020)

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

- [Alike Parts: A Feature-Informed Approach to Local and Global Prototype Explanations](https://mlsanity.com/paper/2605.21646/) (2026)

## Abstract (arXiv)

Subgroup-discovery methods allow users to obtain simple descriptions of interesting regions in a dataset. Using constraints in subgroup discovery can enhance interpretability even further. In this article, we focus on two types of constraints: First, we limit the number of features used in subgroup descriptions, making the latter sparse. Second, we propose the novel optimization problem of finding alternative subgroup descriptions, which cover a similar set of data objects as a given subgroup but use different features. We describe how to integrate both constraint types into heuristic subgroup-discovery methods. Further, we propose a novel Satisfiability Modulo Theories (SMT) formulation of subgroup discovery as a white-box optimization problem, which allows solver-based search for subgroups and is open to a variety of constraint types. Additionally, we prove that both constraint types lead to an NP-hard optimization problem. Finally, we employ 27 binary-classification datasets to compare algorithmic and solver-based search for unconstrained and constrained subgroup discovery. We observe that heuristic search methods often yield high-quality subgroups within a short runtime, also in scenarios with constraints.