cs.LGNov 2, 2026

Optimal Subgroup Discovery at Every Support Threshold

Authors: Lincen Yang, Qi Huang, Niki van Stein, Thomas Bäck, Matthijs van Leeuwen, Zhong Li

Organizations: LIACS, Leiden University, The Netherlands · Great Bay University, China

Abstract

Subgroup discovery aims to identify regions of the feature space where a target variable deviates from its marginal distribution. A fundamental challenge in this problem is the trade-off between a subgroup's deviation and its support: small subgroups can be highly deviating but statistically meaningless, while large ones cannot deviate much by construction. Existing methods tackle this challenge by collapsing the two into a single scalar quality measure, implicitly committing to one particular trade-off and making it difficult to recover the most deviating subgroup under a user-specified support constraint. We instead provide the first theoretical and structural characterization of optimal subgroups with maximum Kullback-Leibler (KL) divergence under arbitrary support constraints. Under a partition-based generative model, where the feature space decomposes into regions of homogeneous conditional distributions of the target variable called atoms, we prove that every point on the deviation-support Pareto front is a union of whole atoms together with at most one fractional atom. This reduces an uncountable search to a finite combinatorial problem. Guided by this theory, we propose a simple two-step recipe: learn a homogeneous partition, then select atoms greedily. Across 19 benchmark datasets, it finds the most deviating subgroups at a range of support thresholds, and reliably improves subgroups returned by existing methods when applied as a post-processing step. These results empirically validate the sufficiency and necessity of our theoretical contributions.

Figures & tables

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Differential Subgroup Discovery: Characterizing Where Two Populations Differ, and Why

    Apr 30, 2026Sascha Xu, Jilles Vreeken

  2. Automatic Discovery of Disease Subgroups by Contrasting with Healthy Controls

    May 20, 2026Robin Louiset, Edouard Duchesnay, Benoit Dufumier +2Contrastive LearningHealthcare

  3. When does Subgroup Balance Matter? Predicting Performance Sensitivity from Latent Separability

    Dec 10, 2025Anissa Alloula, Charles Jones, Zuzanna Wakefield-Skorniewska +2Subgroup RobustnessDataset Bias