Efficiently discovering locally exceptional yet globally representative subgroups

Janis Kalofolias, Mario Boley, Jilles Vreeken

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)


Subgroup discovery is a local pattern mining technique to find interpretable descriptions of sub-populations that stand out on a given target variable. That is, these sub-populations are exceptional with regard to the global distribution. In this paper we argue that in many applications, such as scientific discovery, subgroups are only useful if they are additionally representative of the global distribution with regard to a control variable. That is, when the distribution of this control variable is the same, or almost the same, as over the whole data. We formalise this objective function and give an efficient algorithm to compute its tight optimistic estimator for the case of a numeric target and a binary control variable. This enables us to use the branch-and-bound framework to efficiently discover the top-k subgroups that are both exceptional as well as representative. Experimental evaluation on a wide range of datasets shows that with this algorithm we discover meaningful representative patterns and are up to orders of magnitude faster in terms of node evaluations as well as time.

Original languageEnglish
Title of host publicationProceedings - 17th IEEE International Conference on Data Mining, ICDM 2017
Subtitle of host publication18–21 November 2017 New Orleans, Louisiana
EditorsVijay Raghavan, Srinivas Alu, George Karypis, Lucio Miele, Xindong Wu
Place of PublicationPiscataway NJ USA
PublisherIEEE, Institute of Electrical and Electronics Engineers
Number of pages10
ISBN (Electronic)9781538638347, 9781538638354
ISBN (Print)9781538624494
Publication statusPublished - 2017
Externally publishedYes
EventIEEE International Conference on Data Mining 2017 - New Orleans, United States of America
Duration: 18 Nov 201721 Nov 2017
Conference number: 17th
https://ieeexplore.ieee.org/xpl/conhome/8211002/proceeding (Proceedings)


ConferenceIEEE International Conference on Data Mining 2017
Abbreviated titleICDM 2017
Country/TerritoryUnited States of America
CityNew Orleans
Internet address


  • Branch-and-bound
  • Fairness
  • Subgroup discovery

Cite this