Contrastive Antichains in Hierarchies

Anes Bendimerad, Jefrey Lijffijt, Marc Plantevit, Céline Robardet, Tijl De Bie

Abstract

Hierarchical data structures often contain significant vertical redundancy, making it difficult to extract truly informative patterns. This paper introduces MICA-Miner, an algorithm designed to identify "contrastive antichains"—subsets of a hierarchy that best highlight how a specific target concept differs from a reference norm. By utilizing information theory and a "subjective interestingness" measure, the method identifies non-redundant patterns that are both surprising to the user and easy to communicate.

Problem Definition

Data is frequently organized into hierarchies (e.g., Foursquare venue categories or product taxonomies). However, these levels are often redundant: if a city has an unusually high number of restaurants, it is not surprising that it also has many Italian restaurants. The challenge lies in finding the "sweet spot" in the hierarchy—the specific level of granularity that provides the most insight without being repetitive.

The authors aim to find antichains, which are sets of items where no item is an ancestor of another. These antichains must be contrastive, meaning they stand out compared to a reference or average background model.

An illustration of an antichain P (highlighted in red) within a hierarchical structure.

Methodology

The researchers leverage the FORSIED framework, defining the "Subjective Interestingness" ($SI$) of a pattern as the ratio between its Information Content ($IC$) and its Description Length ($DL$).

  1. Background Model: To quantify "surprise," a probabilistic model of user prior beliefs is constructed using a Maximum Entropy approach. The root follows a geometric distribution, while child nodes follow binomial distributions relative to their parents.
  2. Information Content ($IC$): This measures the deviation of observed data from the background model.
  3. Description Length ($DL$): This penalizes complexity, preferring patterns closer to the root or with fewer items for easier interpretability.
  4. Iterative Mining & Belief Updating: A key innovation is the iterative update of the background model using the sum-product algorithm. Once a pattern is presented, the model is updated so that subsequent results are not redundant variations of previously discovered insights.
  5. MICA-Miner Algorithm: Finding the optimal antichain is NP-hard. The authors propose a greedy heuristic algorithm that scales quadratically with the number of items in the hierarchy.

Experimental Evaluation

The method was evaluated on three real-world datasets:

  • Foursquare (FV): Comparing venue distributions in Amsterdam and London against a 20-city norm.
  • Open Food Facts (OFF): Comparing food product categories between France and the USA.
  • European Parliament (EP_Abst): Analyzing abstention patterns across political groups and policy topics.

Key Results and Insights

MICA-Miner demonstrated a quadratic time complexity ($O(|E|^2)$), making it practical for large hierarchies. Quantitative tests confirmed that iterative updating significantly reduces redundancy in the top results.

Performance metrics showing time and memory usage for MICA-Miner and factor computation across different datasets.

Qualitatively, the algorithm successfully identified unique cultural characteristics:

  • In Amsterdam, it highlighted "Marijuana Dispensaries" and "Tram Stations" as over-represented.
  • In French Food, it identified a high prevalence of "fresh meals" and a lack of "popcorn" relative to American data.

Conclusion

By formalizing "interestingness" as the gap between reality and expectation, and by forcing results to be antichains, MICA-Miner effectively navigates the trade-off between specificity and redundancy. Future work may involve integrating this approach into broader subgroup discovery and exceptional model mining tasks.

Summary updated

Abstract

Concepts are often described in terms of positive integer-valued attributes that are organized in a hierarchy. For example, cities can be described in terms of how many places there are of various types (e.g. nightlife spots, residences, food venues), and these places are organized in a hierarchy (e.g. a Portuguese restaurant is a type of food venue). This hierarchy imposes particular constraints on the values of related attributes---e.g. there cannot be more Portuguese restaurants than food venues. Moreover, knowing that a city has many food venues makes it less surprising that it also has many Portuguese restaurants, and vice versa. In the present paper, we attempt to characterize such concepts in terms of so-called contrastive antichains: particular kinds of subsets of their attributes and their values. We address the question of when a contrastive antichain is interesting, in the sense that it concisely describes the unique aspects of the concept, and this while duly taking into account the known attribute dependencies implied by the hierarchy. Our approach is capable of accounting for previously identified contrastive antichains, making iterative mining possible. Besides the interestingness measure, we also present an algorithm that scales well in practice, and demonstrate the usefulness of the method in an extensive empirical results section.
BibTeX
@inproceedings{bendimerad2019contrastive,
  author = {Anes Bendimerad and Jefrey Lijffijt and Marc Plantevit and Céline Robardet and Tijl De Bie},
  title = {{Contrastive Antichains in Hierarchies}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2019},
  doi = {10.1145/3292500.3330954},
}
Figure