Optimal Subgroup Discovery at Every Support Threshold

Subgroup discovery aims to identify regions of the feature space where a target variable deviates from its marginal distribution. A fundamental tension in this problem is the trade-off between a subgroup's deviance and its support: small subgroups can be highly deviant but statistically meaningless, while large ones cannot deviate much by construction. Existing methods resolve this tension by collapsing it 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, to our knowledge, the first theoretical and structural characterization of KL-optimal subgroups under arbitrary support constraints. Under a partition-based generative model where the feature space decomposes into regions of homogeneous conditional law, which we call atoms, we prove that every point on the deviance-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, this recipe finds the most deviating subgroups across 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.