Flash Points: Discovering Exceptional Pairwise Behaviors in Vote or Rating Data

Adnene Belfodil, Sylvie Cazalens, Philippe Lamarre, Marc PlantevitECML/PKDD 2017 · DOI

TL;DR

This paper introduces a novel method, DSC, for discovering "flash points" – specific contexts where groups of individuals exhibit unexpectedly strong agreement or disagreement in their pairwise behaviors (like voting or rating). DSC provides a principled way to find these nuanced patterns in large datasets, offering deeper insights than traditional subgroup discovery.

What Problem Does This Paper Address?

The paper tackles the challenge of understanding complex relationships within large datasets of votes or ratings. While we can easily see overall trends, it's harder to pinpoint why certain groups of people (e.g., political parties, user demographics) might suddenly align or diverge in their opinions on specific issues or items. Existing methods often focus on individual item ratings or overall group consensus, missing these context-dependent "flash points" where pairwise agreement dramatically shifts. For example, two political parties might generally disagree but strongly agree on votes related to a specific foreign policy issue. Discovering these specific contexts and the groups involved is crucial for deeper analysis in fields like political science, recommender systems, and social science.

Methods

The core of the paper is the DSC (Discovering Similarities Changes) method. It frames the problem as an instance of Exceptional Model Mining (EMM). DSC aims to find three-set patterns: (context, collection1, collection2).

Key methodological contributions include:

  • Problem Formulation: Defining "exceptional pairwise behavior" within the EMM framework, allowing for various similarity measures.
  • Hierarchical Multi-Tag (HMT) Attributes: A novel way to handle attributes that have a hierarchical structure (like movie genres or political party classifications), which is common in real-world data.
  • Aggregations and Similarities: Defining how to aggregate individual behaviors (e.g., vote of the majority, average rating) and then compute pairwise similarities between these aggregates.
  • Branch-and-Bound Algorithm: An efficient algorithm that uses closure operators and tight upper bounds on quality measures to prune the search space, significantly reducing computation time.
  • Quality Measures: Introducing consent and dissent measures to quantify the strengthening or weakening of pairwise agreement within a specific context.

Datasets

The paper evaluates DSC on two real-world datasets:

  • Movielens: A movie review dataset with user ratings. The "objects" are movies, and the "individuals" are users. It features a flat hierarchy of 18 movie genres.
  • EPD (European Parliament Dataset): A dataset of parliamentary votes. The "objects" are ballots, and the "individuals" are parliament members. It includes a complex hierarchical structure of 311 political tags.

Key Insights and Ideas

  • Context is King: The most significant insight is that pairwise agreement isn't static; it's highly dependent on the specific context (e.g., a particular vote topic, a movie genre from a specific year).
  • Beyond Averages: Traditional methods that rely on overall averages or simple subgroup discovery miss crucial nuanced behaviors. DSC's ability to find these specific "flash points" offers a richer understanding.
  • Hierarchical Attributes Matter: Handling hierarchical attributes (like HMT) effectively is crucial for real-world datasets and significantly improves the efficiency of the discovery process.
  • Pruning is Powerful: The combination of closure operators and tight upper bounds in the branch-and-bound algorithm is essential for making the discovery process tractable on large datasets.

Key Results

  • Efficiency: Experiments show that DSC, especially with its HMT attribute handling and pruning techniques, significantly outperforms baseline methods in terms of execution time and the number of explored candidates. For instance, HMTClosure is shown to be more efficient than standard closure operators.
  • Effectiveness: The method successfully discovers meaningful patterns.
  • In Movielens, DSC identified contexts like "1998 comedy movies" where middle-aged females and males showed a significant decrease in similarity (from 86% to 51%).
  • In the EPD dataset, DSC uncovered contexts where political groups that usually align (e.g., PPE and S&D, typically agreeing 76% of the time) diverged significantly on specific ballots related to raw materials and peace preservation.
  • Scalability: The algorithm demonstrates good scalability, with performance improvements observed when increasing pruning thresholds.

Limitations and Future Work

  • Limitations: The paper acknowledges that the quality of the discovered patterns depends on the chosen similarity measures and the quality of the input data. The current implementation focuses on finding top-k patterns, and further exploration might be needed for exhaustive discovery.
  • Future Work: The authors suggest several avenues for future research:
  • Interactive Discovery: Allowing users to incorporate prior knowledge into the discovery process.
  • Instant Mining Algorithms: Developing algorithms that can support interactive exploration more effectively.
  • Exploring Other Similarity Measures: Investigating a wider range of similarity metrics to capture different types of pairwise behaviors.

Summary updated

BibTeX
@inproceedings{belfodil2017flash,
  author = {Adnene Belfodil and Sylvie Cazalens and Philippe Lamarre and Marc Plantevit},
  title = {{Flash Points: Discovering Exceptional Pairwise Behaviors in Vote or Rating Data}},
  booktitle = {ECML/PKDD},
  year = {2017},
  doi = {10.1007/978-3-319-71246-8\_27},
}
Figure