Provable randomized rounding for minimum-similarity diversification

Bruno Ordozgoiti*, Ananth Mahadevan, Antonis Matakos, Aristides Gionis

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

8 Downloads (Pure)

Abstract

When searching for information in a data collection, we are often interested not only in finding relevant items, but also in assembling a diverse set, so as to explore different concepts that are present in the data. This problem has been researched extensively. However, finding a set of items with minimal pairwise similarities can be computationally challenging, and most existing works striving for quality guarantees assume that item relatedness is measured by a distance function. Given the widespread use of similarity functions in many domains, we believe this to be an important gap in the literature. In this paper we study the problem of finding a diverse set of items, when item relatedness is measured by a similarity function. We formulate the diversification task using a flexible, broadly applicable minimization objective, consisting of the sum of pairwise similarities of the selected items and a relevance penalty term. To find good solutions we adopt a randomized rounding strategy, which is challenging to analyze because of the cardinality constraint present in our formulation. Even though this obstacle can be overcome using dependent rounding, we show that it is possible to obtain provably good solutions using an independent approach, which is faster, simpler to implement and completely parallelizable. Our analysis relies on a novel bound for the ratio of Poisson-Binomial densities, which is of independent interest and has potential implications for other combinatorial-optimization problems. We leverage this result to design an efficient randomized algorithm that provides a lower-order additive approximation guarantee. We validate our method using several benchmark datasets, and show that it consistently outperforms the greedy approaches that are commonly used in the literature.

Original languageEnglish
Pages (from-to)709-738
JournalData Mining and Knowledge Discovery
Volume36
Issue number2
Early online date2022
DOIs
Publication statusPublished - Mar 2022
MoE publication typeA1 Journal article-refereed

Keywords

  • Diversification
  • Quadratic programming
  • Randomized rounding
  • Recommender systems

Fingerprint

Dive into the research topics of 'Provable randomized rounding for minimum-similarity diversification'. Together they form a unique fingerprint.

Cite this