A new system-wide diversity measure for recommendations with efficient algorithms

Arda Antikacioglu, Tanvi Bajpai, R. Ravi

Introduction

Modern recommender systems are traditionally optimized for accuracy, aiming to predict user preferences based on historical interactions. However, a singular focus on accuracy often leads to unintended consequences, such as "filter bubbles" and the "rich-get-richer" effect, where a small subset of popular items dominates the system. This concentration of exposure limits the discovery of new content and fails to provide a balanced experience for both users and content providers.

This research addresses these challenges by introducing a system-wide perspective on diversity. Rather than focusing solely on the variety of items shown to a single user, the authors propose a framework that balances user-level variety with item-level exposure. By modeling recommendation as a subgraph selection problem on a bipartite graph, the paper introduces two novel metrics—TUDiv and TIDiv—and provides efficient algorithms to optimize them at scale.

The Diversity Framework: TUDiv and TIDiv

The core of the proposed system lies in two threshold-based metrics designed to capture different dimensions of diversity:

  1. Thresholded User-Diversity (TUDiv): This metric rewards the system for presenting items from a variety of categories to a single user. By applying a threshold, the system is incentivized to provide a "breadth" of content rather than over-recommending a single dominant genre.
  2. Thresholded Item-Diversity (TIDiv): This metric ensures that items are exposed to a diverse set of user types (defined by demographics or interests). This is particularly valuable for businesses, as it prevents items from being pigeonholed into narrow niches and allows the system to gather high-quality feedback from a broad audience.

Together, these metrics treat diversity not just as a user-experience feature, but as a fundamental business requirement for maintaining a healthy content ecosystem.

Algorithmic Approach

The authors model the recommendation task as a subgraph selection problem within a bipartite graph, where users and items represent the two sets of nodes. The complexity of solving this problem depends on the nature of the categories involved:

Disjoint Categories

In scenarios where item categories and user types do not overlap (e.g., a user belongs to exactly one age group), the optimization problem can be reduced to a Minimum Cost Flow problem. This allows for exact solutions to be found in polynomial time, ensuring optimal diversity without sacrificing computational feasibility.

Overlapping Categories

In real-world applications, categories often overlap—for instance, a movie may be classified as both "Action" and "Sci-Fi." The authors prove that maximizing diversity in this context is NP-Hard via a reduction from the Max-Cover problem. To address this, they leverage the submodularity of their objective functions. Submodularity, often described as the law of diminishing returns, allows for the use of a greedy algorithm that provides a $(1 - 1/e)$ approximation of the optimal solution.

To make this viable for production environments, the authors optimized the greedy approach using a max-heap data structure. This resulted in a nearly linear-time algorithm capable of processing millions of edges efficiently.

Experimental Evaluation

The researchers evaluated their approach using the MovieLens-1m dataset, augmented with demographic data and movie metadata from IMDB. The results demonstrated that the proposed algorithms could significantly enhance diversity while maintaining high levels of relevance.

Key Findings

  • Exposure Gains: On the MovieLens dataset, the greedy algorithm increased Aggregate Diversity—the percentage of the total catalog shown to at least one user—from approximately 38% in the baseline to over 55%.
  • Distributional Fairness: The Gini Index, a measure of inequality, showed significant improvement. This indicates a fairer distribution of recommendations across the item catalog, reducing the dominance of a few popular items.
  • Computational Efficiency: The optimized greedy algorithm proved highly performant, completing tasks in roughly 5.8 seconds, compared to 31.3 seconds for more complex reranking techniques like Binomial Diversity.
  • Relevance Preservation: Contrary to the common assumption that diversity harms accuracy, the results showed that the algorithms often maintained or slightly improved precision while drastically increasing diversity.

Conclusion and Future Work

This research provides a robust framework for integrating system-wide diversity into recommender systems. By utilizing thresholded metrics and submodular optimization, the authors demonstrate that it is possible to achieve a more balanced ecosystem without compromising on speed or accuracy.

Future work will focus on extending these models to dynamic settings, where user preferences and item catalogs are constantly evolving. Additionally, the authors aim to automate the tuning of diversity thresholds to better align with specific business objectives and further investigate the impact of these metrics on "cold start" scenarios for new items.

Summary updated

BibTeX
@article{antikacioglu2019new,
  author = {Arda Antikacioglu and Tanvi Bajpai and R. Ravi},
  title = {{A new system-wide diversity measure for recommendations with efficient algorithms}},
  journal = {SIAM J. Math. Data Sci.},
  year = {2019},
  doi = {10.1137/18m1226014},
}
Figure