Optimal Subgroup Discovery at Every Support Threshold
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
| Dataset | AtomSD | RSD | SD-KL | SD- | SyFlow | Dataset | AtomSD | RSD | SD-KL | SD- | SyFlow | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Ailerons | 50 | 1.768 | 1.363 | 0.981 | 1.053 | 1.312 | SkillCraft | 50 | 1.909 | 1.035 | -0.458 | 0.699 | 0.592 |
| 100 | 1.718 | 1.244 | 0.981 | 1.053 | 1.312 | 100 | 1.532 | 0.000 | -0.458 | 0.699 | 0.592 | ||
| 150 | 1.684 | 0.000 | 0.981 | 1.053 | 1.312 | 150 | 0.715 | 0.000 | -0.458 | 0.699 | 0.592 | ||
| 200 | 1.475 | 0.000 | 0.981 | 1.053 | 1.312 | 200 | 0.715 | 0.000 | -0.459 | 0.699 | 0.592 | ||
| 300 | 1.684 | 0.000 | 0.981 | 1.053 | 1.312 | 300 | 0.715 | 0.000 | 0.000 | 0.699 | 0.645 | ||
| Bikesharing | 50 | 3.679 | 0.891 | 1.290 | 2.889 | 1.246 | SML2010 | 50 | 2.506 | 2.029 | 0.000 | 1.180 | 1.253 |
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
| Dataset | Sample Sizes | #Discrete Features | #Continuous Features |
|---|---|---|---|
| Ailerons | 13750 | 4 | 36 |
| Bikesharing | 17379 | 13 | 4 |
| California | 20640 | 5 | 3 |
| Concrete | 1030 | 0 | 8 |
| Elevators | 16599 | 4 | 14 |
| Energy | 9568 | 0 | 4 |
| Dataset | AtomSD | RSD | SD-KL | SD- | SyFlow | Dataset | AtomSD | RSD | SD-KL | SD- | SyFlow | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Ailerons | 0.05 | 1.491 | 0.000 | 0.981 | 1.053 | 1.312 | SkillCraft | 0.05 | 0.759 | 0.000 | -0.458 | 0.699 | 0.592 |
| 0.10 | 1.347 | 0.000 | 0.981 | 1.053 | 1.312 | 0.10 | 0.715 | 0.000 | 0.000 | 0.699 | 0.592 | ||
| 0.20 | 1.069 | 0.000 | 0.981 | 1.053 | 1.055 | 0.20 | 0.723 | 0.000 | 0.000 | 0.475 | 0.642 | ||
| 0.30 | 1.051 | 0.000 | 0.000 | 1.053 | 1.065 | 0.30 | 0.693 | 0.000 | 0.000 | 0.000 | 0.551 | ||
| Bikesharing | 0.05 | 2.180 | 0.000 | 1.290 | 0.000 | 0.704 | SML2010 | 0.05 | 1.867 | 0.000 | 0.000 | 1.180 | 1.063 |
| 0.10 | 1.557 | 0.000 | 1.290 | 0.000 | 0.704 | 0.10 | 1.384 | 0.000 | 0.000 | 1.180 | 1.014 |
| Dataset | # rows | dim. | AtomSD | RSD | SD-KL | SD- | SyFlow |
| Ailerons | 13750 | 40 | 1.446 ( 0.442) | 1.363 ( 0.168) | 0.981 ( 0.000) | 1.053 ( 0.005) | 1.312 ( 0.390) |
| Bikesharing | 17379 | 17 | 3.056 ( 0.104) | 0.891 ( 0.300) | 1.290 ( 0.000) | 2.889 ( 0.229) | 1.246 ( 0.386) |
| California | 20640 | 8 | 1.962 ( 0.209) | -0.694 ( 0.000) | 0.000 ( 0.000) | 1.316 ( 0.108) | 0.747 ( 0.072) |
| Concrete | 1030 | 8 | 1.147 ( 0.163) | 1.174 ( 0.201) | 0.000 ( 0.000) | 1.220 ( 0.224) | 1.213 ( 0.190) |
| Elevators | 16599 | 18 | 1.509 ( 0.096) | 0.000 ( 0.000) | -0.268 ( 0.244) | -0.100 ( 0.063) | 0.447 ( 0.209) |
| Energy | 9568 | 4 | 2.105 ( 0.083) | 2.229 ( 0.138) | 1.088 ( 0.035) | 1.250 ( 0.020) | 0.844 ( 0.067) |