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
Figure 1: Ranking error under support-weighted KL estimation with finite samples. Two subgroups are drawn from a 5-mode Gaussian mixture background: Subgroup A (true, support =0.08 , KL≈0.25 ) and Subgroup B (spurious, support =0.15 , KL=0 ). Left: Conditional densities of the subgroups and background. Middle: Support-weighted KL estimates (support × KL) as a function of Subgroup A’s sample size k , with B’s size scaled by the support ratio; shaded regions show the 2.5th–97.5th percentile range over 300 draws. At small k , estimation noise inflates B’s score above A’s despite its zero true divergence. Right: Fraction of trials in which the spurious Subgroup B is ranked above the true Subgroup A. At k=30 the error rate still exceeds 20%, showing that support-weighted KL ranking is unreliable at small sample sizes.
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
Table 1: Average held-out KL divergence (higher is better) across 3-fold CV for support threshold α . Bold indicates the best method per row. If a method returns no subgroup satisfying the support threshold on none of the three folds, KL is set to 0 (the default, trivial subgroup covering all instances); otherwise, the reported value is averaged only over folds on which the method returns a valid subgroup. Held-out KL estimates can be negative; see Appendix B .
Figure 2: Held-out KL-divergence difference between AtomSD’s refined subgroup and each competitor’s original subgroup, across 19 datasets and five support thresholds. Positive values indicate that AtomSD’s refinement improves the given subgroups.
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
Appendix
Table 2: Summary of the datasets used in the experiments
Figure 3: Bootstrap stability of KL divergence estimates across subgroup discovery algorithms. For each discovered subgroup, we perform 300 bootstrap replicates of the dataset and re-estimate KL using the same histogram-based procedure (Freedman–Diaconis binning with Bayesian smoothing). Each point in the box plot represents one subgroup’s bootstrap standard deviation of KL , grouped by training set size. Left column: KL estimated on the training split. Right column: KL estimated on the test split. Across all five algorithms, subgroups with fewer than 50 training instances exhibit substantially higher estimation variability, indicating that their KL-based ranking scores are unreliable. The pattern is consistent for both train and test estimates.
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
Appendix
Table 3: Average held-out KL divergence (higher is better) across 3-fold CV for support ratio threshold α′ . Bold indicates the best method per row. If a method returns no subgroup satisfying the support threshold on none of the three folds, KL is set to 0 (the default, trivial subgroup covering all instances); otherwise, the reported value is averaged only over folds on which the method returns a valid subgroup.
Figure 4: Held-out KL-divergence difference between AtomSD’s refined subgroup and each competitor’s original subgroup, across 19 datasets and four support ratios α′ . Positive values indicate that AtomSD’s refinement improves the given subgroups.
Figure 5: Critical-difference diagrams for constrained subgroup discovery across all support thresholds. Left column: absolute thresholds α∈{50,100,150,200,300} (Table 1 ). Right column: ratio thresholds {\color[rgb]{0,0,0}\alpha^{\prime}}\in\{0.05,0.10,0.20,0.30\} (Table 3 ). Each diagram reports the Friedman test p -value (Iman–Davenport F statistic) and the Nemenyi critical difference (CD =1.40 at significance level 0.05 ). Methods connected by a horizontal bar are not significantly different; methods separated by more than the CD are significantly different.
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)
Appendix
Table 4: Results for unconstrained subgroup discovery. Each cell reports the mean maximum KL divergence over three held-out folds (standard deviation in parentheses), measured between the discovered subgroup and the marginal distribution of the full held-out split. Per-dataset best means are bold. #Best counts datasets on which each algorithm attains the highest mean; Avg. Rank is the mean rank across datasets (lower is better).