Subgroup discovery stops folding support into one score: AtomSD returns the most deviating subgroup at any support threshold
Synopsis
Subgroup discovery has long compressed deviation and coverage into a single weighted score, so a user-specified minimum support often has no matching most-deviating subgroup. AtomSD recasts the search as selecting among a finite set of homogeneous regions, called atoms: in theory the optimal subgroup at every support threshold is a union of whole atoms plus at most one partial atom. On 19 UCI benchmark datasets it reaches an average rank of 1.25 across five support thresholds and is best in 78 of 95 dataset-threshold combinations, and it improves subgroups returned by four existing methods when used as post-processing.
Interpretation
Subgroup discovery can now target the most deviating subgroup directly at a user-specified minimum support, instead of first committing to one support-deviation trade-off. The dominant approach folds support and deviation into a single scalar quality measure, such as weighted KL divergence, RSD's description-length penalty, and SyFlow's support-weighted KL objective, which implicitly fixes one trade-off. On 19 UCI benchmark datasets with 3-fold cross-validation and held-out KL estimation, AtomSD averages rank 1.25 across support thresholds 50, 100, 150, 200 and 300 and is best in 78 of 95 dataset-threshold combinations; by contrast RSD averages 3.49, SD-KL 3.92, SD- 3.22 and SyFlow 3.13.
The recipe first learns a partition of the feature space into regions with homogeneous conditional target distributions, then greedily selects among those regions. The theory characterizes an optimal subgroup as whole atoms plus at most one partial atom, where an atom is a region with a constant conditional target distribution, turning an uncountable search over measurable subsets into a finite combinatorial problem. The implementation uses leaves of a conditional density estimation tree, CDTree, as atoms and applies Greedy Atomic Pruning (GAP), which alternates whole-atom toggles with shrinking the bounding box of a single atom, evaluated by held-out KL on the 19 datasets.
The same structural condition serves as post-processing: restricting an existing method's subgroup to the atoms it overlaps and re-selecting within them usually raises held-out KL divergence. A subgroup that cuts partially through two or more atoms violates the necessary structural condition for an optimal subgroup and can in principle be improved. Applying this post-processing to subgroups returned by all four competitors, the distribution of KL differences is predominantly positive at every support threshold, with medians consistently above zero and negative cases rare and mostly small.
Perspective
The theoretical guarantees hold under a partition-based generative model, in which the feature space decomposes into atoms with homogeneous conditional target distributions; experiments use 19 UCI benchmark datasets with 3-fold cross-validation and held-out KL divergence, with one-dimensional continuous targets.
Real data only approximates that generative model to varying degrees, and formal robustness results under distributional misspecification remain open; subgroups with fewer than 50 training instances yield KL estimates with prohibitively large variance, which is why the ratio-threshold comparison raises the threshold.