# A Critical Reexamination of Intra-List Distance and Dispersion

Naoto Ohsaka  CyberAgent, Inc.TokyoJapan<EMAIL_ADDRESS>0000-0001-9584-4764 and  Riku Togashi  CyberAgent, Inc.TokyoJapan
<EMAIL_ADDRESS>0000-0001-9026-0495

(2023)

###### Abstract.

Diversification of recommendation results is a promising approach for coping
with the uncertainty associated with users’ information needs. Of particular
importance in diversified recommendation is to define and optimize an
appropriate diversity objective. In this study, we revisit the most popular
diversity objective called _intra-list distance (ILD)_ , defined as the
average pairwise distance between selected items, and a similar but lesser
known objective called _dispersion_ , which is the minimum pairwise distance.
Owing to their simplicity and flexibility, ILD and dispersion have been used
in a plethora of diversified recommendation research. Nevertheless, _we do not
actually know_ what kind of items are preferred by them.

We present a critical reexamination of ILD and dispersion from theoretical and
experimental perspectives. Our theoretical results reveal that these
objectives have potential drawbacks: ILD may select _duplicate_ items that are
very close to each other, whereas dispersion may overlook _distant_ item
pairs. As a competitor to ILD and dispersion, we design a diversity objective
called Gaussian ILD, which can _interpolate_ between ILD and dispersion by
tuning the bandwidth parameter. We verify our theoretical results by
experimental results using real-world data and confirm the extreme behavior of
ILD and dispersion in practice.

diversified recommendation; intra-list distance; dispersion

††journalyear: 2023††copyright: rightsretained††conference: Proceedings of the
46th International ACM SIGIR Conference on Research and Development in
Information Retrieval; July 23–27, 2023; Taipei, Taiwan††booktitle:
Proceedings of the 46th International ACM SIGIR Conference on Research and
Development in Information Retrieval (SIGIR ’23), July 23–27, 2023, Taipei,
Taiwan††doi: 10.1145/3539618.3591623††isbn: 978-1-4503-9408-6/23/07††ccs:
Information systems Information retrieval diversity

##  1\. Introduction

In recommender systems, solely improving the prediction accuracy of user
preferences, as a single objective, is known to have the risk of recommending
over-specialized items to a user, resulting in low user satisfaction
(mcnee2006being). The primary approach for addressing such issues arising from
the uncertainty associated with users’ information needs is the introduction
of _beyond-accuracy objectives_ (kaminskas2017diversity) such as diversity,
novelty, and serendipity. Among the most important beyond-accuracy objectives
is _diversity_ , which refers to the internal differences between items
recommended to a user. Recommending a set of diverse items may increase the
chance of satisfying a user’s needs. However, defining diversity is a
nontrivial task because the contribution of a particular item depends on the
other selected items. Of particular importance in diversified recommendation
is thus to define and optimize an appropriate diversity objective.

In this study, we revisit two diversity objectives. One is the _intra-list
distance (ILD)_ , which is arguably the most frequently used objective for
diversity. The ILD (smyth2001similarity; ziegler2005improving) is defined as
the average pairwise distance between selected items for a particular distance
metric. ILD is easy to use and popular in diversified recommendation research
for the following reasons:

  * 1.

It is a _distance-based objective_ (drosou2017diversity), which only requires
a pairwise distance metric between items; thus, we can flexibly adopt any
metric depending on the application, e.g., the Jaccard distance (yu2009it;
gollapudi2009axiomatic; kaminskas2017diversity), taxonomy-based metric
(ziegler2005improving), and cosine distance (cheng2017learning).

  * 2.

The definition is “intuitive” in that it simply integrates pairwise distances
between items in a recommendation result.

  * 3.

Although maximization of ILD is NP-hard (tamir1991obnoxious), a simple greedy
heuristic efficiently identifies an item set with a nearly optimal ILD
(ravi1994heuristic; birnbaum2009improved). This heuristic can be easily
incorporated into recommendation algorithms (yu2009it; gollapudi2009axiomatic;
hurley2011novelty; wasilewski2016incorporating; sha2016framework;
cheng2017learning).

Indeed, ILD appears in many surveys on diversified recommendations
(kaminskas2017diversity; wu2019recent; castells2015novelty; drosou2010search;
drosou2017diversity; kunaver2017diversity). The other objective investigated
in this study is a similar but lesser known one called _dispersion_ , which is
defined as the _minimum_ pairwise distance between selected items. Although
dispersion seldom appears in the recommendation literature
(gollapudi2009axiomatic; drosou2010search), it has the aforementioned
advantages. Nevertheless, _we do not actually know_ what kind of items are
preferred by ILD and dispersion; for instance: Are the items selected by
optimizing ILD or dispersion satisfactorily distant from each other? What if
the entire item set is clustered or dispersed?

Figure 1. An example such that intra-list distance and dispersion select very
different items.

###  1.1. Our Contributions

This study presents a critical reexamination of ILD and dispersion from both
theoretical and experimental perspectives. To answer the aforementioned
questions, we investigate whether enhancing one (e.g., ILD) leads to an
increase in the other (e.g., dispersion), in the hope that we can characterize
what they are representing and reveal their drawbacks. We first identify the
following potential drawbacks of ILD and dispersion based on our theoretical
comparisons (Section 4): _ILD selects items in a well-balanced manner if the
entire item set is separated into two clusters. However, it may generally
select duplicate items that are very close to each other. The items chosen by
dispersion are well-scattered, but distant item pairs may be overlooked._

We then conduct numerical experiments to verify the assertions based on our
theoretical analysis (Section 6). Our empirical results using MovieLens
(harper2015movielens) and Amazon Review (ni2019justifying) demonstrate that
_ILD can readily select many items that are similar or even identical_ , which
is undesirable if we wish to recommend very few items. Figure 1 shows a cloud
of points in an ellipse such that ILD and dispersion select very different
item sets. Our theoretical and empirical results imply that the items selected
via ILD are biased toward two distant groups; items in the middle of the
ellipse are never chosen. In contrast, the items selected by dispersion are
well-scattered.

To better understand the empirical behaviors of ILD and dispersion, we design
a new distance-based objective that generalizes ILD and dispersion as a
competitor (Section 5). The designed one, _Gaussian ILD (GILD)_ , is defined
as the average of the Gaussian kernel distances (phillips2011gentle) between
selected items. GILD has bandwidth parameter $\sigma$, and we prove that GILD
approaches ILD as $\sigma\to\infty$ and approaches dispersion as $\sigma\to
0$; i.e., it can _interpolate_ between them. We experimentally confirm that
GILD partially circumvents the issues caused by the extreme behaviors of ILD
and dispersion, thereby achieving a _sweet spot_ between them (Section 6).

Finally, we examine the recommendation results obtained by enhancing ILD,
dispersion, and GILD (Section 7). The experimental results demonstrate that
(1) ILD frequently selects duplicate items, and thus it is not an appropriate
choice; (2) if the relevance of the recommended items is highly prioritized,
dispersion fails to diversify the recommendation results for some users.

In summary, _ILD is not appropriate for either evaluating or enhancing
distance-based diversity_ , whereas _dispersion is often suitable for
improving diversity, but not necessarily for measuring diversity_.

##  2\. Related Work

Diversity enhancement has various motivations (castells2015novelty); e.g., (1)
because a user’s preference is uncertain owing to the inherent sparsity of
user feedback, recommending a set of diverse items has the potential to
satisfy a user’s needs; (2) users desire diversity of recommended items due to
the variety-seeking behavior. Other beyond-accuracy objectives include
novelty, serendipity, and coverage; see, e.g., castells2015novelty,
kaminskas2017diversity, and zangerle2022evaluating.

Generally, there are two types of diversity. One is _individual diversity_ ,
which represents the diversity of recommended items for each user. The other
is _aggregate diversity_ (adomavicius2012improving;
adomavicius2014optimization), which represents the diversity _across_ users
and promotes long-tail items. We review the definitions and enhancement
algorithms for individual diversity, which is simply referred to as
_diversity_ throughout this paper.

##### Defining Diversity Objectives

The _intra-list distance_ (ILD) (also known as the _average pairwise
distance_) due to smyth2001similarity and ziegler2005improving is among the
earliest diversity objectives in recommendation research. Owing to its
simplicity and flexibility in the choice of a distance metric, ILD has been
used in a plethora of subsequent works (zhang2008avoiding; yu2009it;
gollapudi2009axiomatic; hurley2011novelty; boim2011diversification;
vargas2011rank; borodin2012max; su2013set; sha2016framework;
cheng2017learning; ekstrand2014user). _Dispersion_ is another distance-based
diversity objective that is similar to ILD. Maximizing the dispersion value is
known as the _$p$ -dispersion_ problem in operations research and is motivated
by applications in facility location (kuby1987programming;
erkut1989analytical; erkut1990discrete; ravi1994heuristic). Notably, only a
few studies on recommender systems (gollapudi2009axiomatic; drosou2010search)
adopt dispersion as the diversity objective. _Determinantal point processes
(DPP)_ are probabilistic models that express the negative correlation among
items using the determinant (macchi1975coincidence; borodin2005eynard). DPP-
based objectives have recently been applied to recommender systems
(qin2013promoting). See kulesza2012determinantal for more details. _Topical
diversity objectives_ use predefined topic information to directly evaluate
how many topics are covered by selected items and/or the extent to which topic
redundancy should be avoided (agrawal2009diversifying; vargas2014coverage;
ashkan2015optimal; antikacioglu2019new). Such topic information is often
readily available in many domains such as movies, music, and books. In this
paper, we do not compare DPPs or topical diversity because we deeply
investigate ILD and dispersion, which are more commonly used.

gollapudi2009axiomatic use an _axiomatic approach_ , in which they design a
set of axioms that a diversity objective should satisfy, and prove that any
objective, including ILD and dispersion, cannot satisfy all the axioms
simultaneously. amigo2018axiomatic present another axiomatic analysis of
diversity-aware evaluation measures. Our study is orthogonal to these works
because we focus on elucidating what diversity objectives represent.

##### Diversity Enhancement Algorithms

We review algorithms for enhancing the diversity of recommended items. The
basic approach simultaneously optimizes both relevance and diversity. Given
the relevance $\mathsf{rel}(i)$ for each item $i$ and a diversity objective
$\mathsf{div}(\cdot)$ (e.g., ILD), we can formulate an objective function as a
linear combination of the average relevance and diversity of selected items
$S$, i.e.,

(1) $\displaystyle\max_{S}\;(1-\lambda)\cdot\frac{1}{|S|}\sum_{i\in
S}\mathsf{rel}(i)+\lambda\cdot\mathsf{div}(S),$

where $\lambda\in(0,1)$ is the trade-off parameter. The _maximal marginal
relevance (MMR)_ (carbonell1998use) is an initial attempt using this approach,
which applies a greedy heuristic to Eq. 1. Greedy-style algorithms are widely
used in many diversified recommendation studies (agrawal2009diversifying;
vargas2014coverage; ashkan2015optimal; yu2009it; gollapudi2009axiomatic;
hurley2011novelty; wasilewski2016incorporating; sha2016framework;
cheng2017learning). Other algorithms include local search (yu2009it), binary
quadratic programming (zhang2008avoiding; hurley2011novelty), and multi-
objective optimization (ribeiro2012pareto; ribeiro2014multiobjective).
However, even (Pareto) optimal solutions are undesirable unless we choose an
“appropriate” objective to be optimized. We investigate whether the greedy
maximization of one diversity objective is useful for enhancing another
objective.

_Learning-to-rank_ approaches aim to directly learn the optimal ranking of
recommended items for each user under a particular definition of the loss
function. Notably, the underlying function that models diversity often
originates from existing diversity objectives, including ILD
(wasilewski2016incorporating; cheng2017learning). Thus, our study helps
understand the impact of underlying diversity modeling on recommendation
results.

##### Evaluation Measures in Information Retrieval

In information retrieval (IR), efforts were made to render classical IR
evaluation measures diversity-aware to address the uncertainty in users’
queries, e.g., $\alpha$-normalized discounted cumulative gain ($\alpha$-nDCG)
(clarke2008novelty), Intent-Aware measures (agrawal2009diversifying),
D$\sharp$-measures (sakai2011evaluating), and $\alpha\beta$-nDCG
(parapar2021towards). We do not consider such diversity-aware IR measures,
which assume that a distribution over the intents is available for each query.

##  3\. Preliminaries

##### Notations

For a nonnegative integer $n$, let $[n]\triangleq\\{1,2,\ldots,n\\}$. For a
finite set $S$ and an integer $k$, we write ${S\choose k}$ for the family of
all size-$k$ subsets of $S$. Vectors and matrices are written in bold (e.g.,
$\mathbf{\bm{v}}$ and $\mathbf{\bm{A}}$), and the $i$-th entry of a vector
$\mathbf{\bm{v}}$ in $\mathbb{R}^{d}$ is denoted $v(i)$. The Euclidean norm is
denoted $\|\cdot\|$; i.e.,
$\|\mathbf{\bm{v}}\|\triangleq\sqrt{\sum_{i\in[d]}v(i)^{2}}$ for a vector
$\mathbf{\bm{v}}$ in $\mathbb{R}^{d}$.

##### Recap of Two Diversity Objectives

We formally define two popular distance-based diversity objectives. We assume
that a pairwise distance $d(i,j)$ is given between every pair of items $i,j$.
One objective is the _intra-list distance (ILD)_ , which is defined as

$\displaystyle\textsf{{ILD}}(S)\triangleq\frac{1}{{|S|\choose 2}}\sum_{i\neq
j\in S}d(i,j)$

for an item set $S$. The definition of ILD is intuitive, as it simply takes
the average of the pairwise distances between all the items in $S$. The other
is _dispersion_ , which is defined as the minimum pairwise distance between
selected items:

$\displaystyle\textsf{{disp}}(S)\triangleq\min_{i\neq j\in S}d(i,j).$

Dispersion is stricter than ILD in that it evaluates the pairwise distance
among $S$ in the _worst-case_ sense.

We can flexibly choose from any distance function $d$ depending on the
application. Such a distance function is often a _metric_ ; i.e., the
following three axioms are satisfied for any items $i,j,k$: (1) identity of
indiscernibles: $d(i,j)=0\iff i=j$; (2) symmetry: $d(i,j)=d(j,i)$; (3)
triangle inequality: $d(i,j)+d(j,k)\geq d(i,k)$. Commonly-used distance
metrics in diversified recommendation include the Euclidean distance
(ashkan2015optimal; sha2016framework), i.e.,
$d(i,j)\triangleq\|\mathbf{\bm{x}}_{i}-\mathbf{\bm{x}}_{j}\|$, where
$\mathbf{\bm{x}}_{i}$ and $\mathbf{\bm{x}}_{j}$ are the feature vectors of
items $i$ and $j$, respectively, the cosine distance (cheng2017learning;
kaminskas2017diversity), and the Jaccard distance (yu2009it;
gollapudi2009axiomatic; kaminskas2017diversity).

Algorithm 1 Greedy heuristic.

1:diversity objective
$\operatorname{\mathop{\mathsf{f}}}:2^{[n]}\to\mathbb{R}_{+}$; # items
$k\in[n]$.

2:for  $\ell=1\;\textbf{to}\;k$ do
$i_{\ell}\leftarrow\operatorname*{argmax}_{i\in[n]\setminus\\{i_{1},\ldots,i_{\ell-1}\\}}\operatorname{\mathop{\mathsf{f}}}(\\{i_{1},\ldots,i_{\ell-1},i\\})$.

3:return $\\{i_{1},\ldots,i_{k}\\}$.

##### Greedy Heuristic

Here, we explain a greedy heuristic for enhancing diversity. This heuristic
has been frequently used in diversified recommendations, and thus we use it
for theoretical and empirical analyses of ILD and dispersion in Sections 4, 6
and 7.

Consider the problem of selecting a set of $k$ items that maximize the value
of a particular diversity objective $\operatorname{\mathop{\mathsf{f}}}$. This
problem is NP-hard, even if $\operatorname{\mathop{\mathsf{f}}}$ is restricted
to ILD (tamir1991obnoxious) and dispersion (ravi1994heuristic;
erkut1990discrete). However, we can obtain an approximate solution to this
problem using the simple greedy heuristic shown in Algorithm 1. Given a
diversity objective
$\operatorname{\mathop{\mathsf{f}}}:2^{[n]}\to\mathbb{R}_{+}$ on $n$ items and
an integer $k\in[n]$ representing the number of items to be recommended, the
greedy heuristic iteratively selects an item of $[n]$, not having been chosen
so far, that maximizes the value of $\operatorname{\mathop{\mathsf{f}}}$. This
heuristic has the following advantages from both theoretical and practical
perspectives: (1) it is _efficient_ because the number of evaluating
$\operatorname{\mathop{\mathsf{f}}}$ is at most $nk$; (2) it provably finds a
$\frac{1}{2}$-approximate solution to maximization of ILD
(birnbaum2009improved) and dispersion (ravi1994heuristic), which performs
nearly optimal in practice.

##  4\. Theoretical Comparison

We present a theoretical analysis of the comparison between ILD and
dispersion. Our goal is to elucidate the _correlation_ between two diversity
objectives. Once we establish that enhancing a diversity objective
$\operatorname{\mathop{\mathsf{f}}}$ results in an increase in another
$\operatorname{\mathop{\mathsf{g}}}$ to some extent, we merely maximize
$\operatorname{\mathop{\mathsf{f}}}$ to obtain diverse items with respect to
_both_ $\operatorname{\mathop{\mathsf{f}}}$ and
$\operatorname{\mathop{\mathsf{g}}}$. In contrast, if there is no such
correlation, we shall characterize what $\operatorname{\mathop{\mathsf{f}}}$
and $\operatorname{\mathop{\mathsf{g}}}$ are representing or enhancing. The
remainder of this section is organized as follows: Section 4.1 describes our
analytical methodology, Section 4.2 summarizes our results, and Section 4.3 is
devoted to lessons learned based on our results.

###  4.1. Our Methodology

We explain how to quantify the correlation between two diversity objectives.
Suppose we are given a diversity objective
$\operatorname{\mathop{\mathsf{f}}}:2^{[n]}\to\mathbb{R}_{+}$ over $n$ items
and an integer $k\in[n]$ denoting the output size (i.e., the number of items
to be recommended). We define _$\operatorname{\mathop{\mathsf{f}}}$
-diversification_ as the following optimization problem:

$\displaystyle\max_{S\in{[n]\choose
k}}\;\operatorname{\mathop{\mathsf{f}}}(S).$

Hereafter, the optimal item set of
$\operatorname{\mathop{\mathsf{f}}}$-diversification is denoted
$S_{\operatorname{\mathop{\mathsf{f}}},k}^{*}$ and the optimal value is
denoted ${\mathrm{OPT}}_{\operatorname{\mathop{\mathsf{f}}},k}$; namely, we
define
$S_{\operatorname{\mathop{\mathsf{f}}},k}^{*}\triangleq\operatorname*{argmax}_{S\in{[n]\choose
k}}\operatorname{\mathop{\mathsf{f}}}(S)$ and
${\mathrm{OPT}}_{\operatorname{\mathop{\mathsf{f}}},k}\triangleq\operatorname{\mathop{\mathsf{f}}}(S_{\operatorname{\mathop{\mathsf{f}}},k}^{*})$.
We also denote by $S_{\operatorname{\mathop{\mathsf{f}}},k}^{\mathrm{Gr}}$ the
set of $k$ items selected using the greedy heuristic on
$\operatorname{\mathop{\mathsf{f}}}$. We omit the subscript “$k$” when it is
clear from the context. Concepts related to approximation algorithms are also
introduced.

###### Definition 4.1.

We say that a $k$-item set $S$ is a _$\rho$ -approximation_ to
$\operatorname{\mathop{\mathsf{f}}}$-diversification for some $\rho\leq 1$ if
it holds that

$\displaystyle\operatorname{\mathop{\mathsf{f}}}(S)\geq\rho\cdot{\mathrm{OPT}}_{\operatorname{\mathop{\mathsf{f}}},k}.$

Parameter $\rho$ is called the _approximation factor_.

For example, the greedy heuristic returns a $\frac{1}{2}$-approximation for
ILD-diversification; i.e.,
$\textsf{{ILD}}(S_{\textsf{{ILD}}}^{\mathrm{Gr}})\geq\frac{1}{2}\cdot{\mathrm{OPT}}_{\textsf{{ILD}}}$.

We now quantify the correlation between a pair of diversity objectives
$\operatorname{\mathop{\mathsf{f}}}$ and $\operatorname{\mathop{\mathsf{g}}}$.
The primary logic is to think of the optimal set
$S_{\operatorname{\mathop{\mathsf{f}}},k}^{*}$ for
$\operatorname{\mathop{\mathsf{f}}}$-diversification as an algorithm for
$\operatorname{\mathop{\mathsf{g}}}$-diversification. The correlation is
measured using the approximation factor of this algorithm for
$\operatorname{\mathop{\mathsf{g}}}$-diversification, i.e.,

(2)
$\displaystyle\frac{\operatorname{\mathop{\mathsf{g}}}(S_{\operatorname{\mathop{\mathsf{f}}},k}^{*})}{{\mathrm{OPT}}_{\operatorname{\mathop{\mathsf{g}}},k}}.$

Intuitively, if this factor is sufficiently large, then we merely maximize the
value of $\operatorname{\mathop{\mathsf{f}}}$; e.g., if Eq. 2 is $0.99$, then
any item set having the optimum $\operatorname{\mathop{\mathsf{f}}}$ is also
nearly-optimal with respect to $\operatorname{\mathop{\mathsf{g}}}$. However,
when Eq. 2 is very low, such an item set is not necessarily good with respect
to $\operatorname{\mathop{\mathsf{g}}}$; namely,
$\operatorname{\mathop{\mathsf{f}}}$-diversification does _not_ imply
$\operatorname{\mathop{\mathsf{g}}}$-diversification. Note that we can replace
$S_{\operatorname{\mathop{\mathsf{f}}},k}^{*}$ with the greedy solution, whose
approximation factor is
$\frac{\operatorname{\mathop{\mathsf{g}}}(S_{\operatorname{\mathop{\mathsf{f}}},k}^{\mathrm{Gr}})}{{\mathrm{OPT}}_{\operatorname{\mathop{\mathsf{g}}},k}}$.
Our analytical methodology is twofold:

  * 1.

We prove a guarantee on the approximation factor; i.e., there exists a factor
$\rho$ such that
$\frac{\operatorname{\mathop{\mathsf{g}}}(S_{\operatorname{\mathop{\mathsf{f}}}}^{*})}{{\mathrm{OPT}}_{\operatorname{\mathop{\mathsf{g}}}}}\geq\rho$
for _every_ set of items with a distance metric.

  * 2.

We construct an input to indicate inapproximability; i.e., there exists a
(small) factor $\rho^{\prime}$ such that
$\frac{\operatorname{\mathop{\mathsf{g}}}(S_{\operatorname{\mathop{\mathsf{f}}}}^{*})}{{\mathrm{OPT}}_{\operatorname{\mathop{\mathsf{g}}}}}<\rho^{\prime}$
for _some_ item set with a distance metric. Such an input demonstrates the
case in which $\operatorname{\mathop{\mathsf{f}}}$ and
$\operatorname{\mathop{\mathsf{g}}}$ are quite different; thus, we can use it
to characterize what $\operatorname{\mathop{\mathsf{f}}}$ and
$\operatorname{\mathop{\mathsf{g}}}$ represent.

###  4.2. Our Results

We now present our results, each of which (i.e., a theorem or claim) is
followed by a remark devoted to its intuitive implication. Given that ILD and
dispersion differ only in that the former takes the _average_ and the latter
the _minimum_ over all pairs of items, an item set with a large dispersion
value is expected to possess a large ILD value. This intuition is first
justified. We define the _diameter_ $D$ for $n$ items as the maximum pairwise
distance; i.e., $D\triangleq\max_{i\neq j\in[n]}d(i,j),$ and denote by
$d_{k}^{*}$ the maximum dispersion among $k$ items; i.e.,
$d_{k}^{*}\triangleq{\mathrm{OPT}}_{\textsf{{disp}},k}.$ Our first result is
the following, whose proof is deferred to Appendix A.

###### Theorem 4.2.

The following inequalities hold for any input and distance metric:
$\frac{\textsf{{ILD}}(S_{\textsf{{disp}},k}^{*})}{{\mathrm{OPT}}_{\textsf{{ILD}},k}}\geq\frac{d_{k}^{*}}{D}\text{
and
}\frac{\textsf{{ILD}}(S_{\textsf{{disp}},k}^{\mathrm{Gr}})}{{\mathrm{OPT}}_{\textsf{{ILD}},k}}\geq\max\left\\{\frac{d_{k}^{*}}{2D},\frac{1}{k}\right\\}.$
In other words, the optimal size-$k$ set to disp-diversification is a
$\frac{d_{k}^{*}}{D}$-approximation to ILD-diversification, and Algorithm 1 on
disp returns a $\max\\{\frac{d_{k}^{*}}{2D},\frac{1}{k}\\}$-approximation to
ILD-diversification.

_Remark:_ Theorem 4.2 implies that _the larger the dispersion, the larger the
ILD_ , given that $D$ is not significantly large. In contrast, if the maximum
dispersion $d_{k}^{*}$ is much smaller than $D$, the approximation factor
$\frac{d_{k}^{*}}{D}$ becomes less fascinating. Fortunately, the greedy
heuristic exhibits a $\frac{1}{k}$-approximation, which facilitates a data-
independent guarantee.

We demonstrate that Theorem 4.2 is almost tight, whose proof is deferred to
Appendix A.

###### Claim 4.3.

There exists an input such that the pairwise distance is the Euclidean
distance between feature vectors, and the following holds:
$\frac{\textsf{{ILD}}(S_{\textsf{{disp}},k}^{*})}{{\mathrm{OPT}}_{\textsf{{ILD}},k}}=\mathcal{O}\left(\frac{d_{k}^{*}}{D}\right)\text{
and
}\frac{\textsf{{ILD}}(S_{\textsf{{disp}},k}^{\mathrm{Gr}})}{{\mathrm{OPT}}_{\textsf{{ILD}},k}}=\mathcal{O}\left(\frac{1}{k}+\frac{d_{k}^{*}}{D}\right).$
In particular, Theorem 4.2 is tight up to constant.

_Remark:_ The input used in the proof of Claim 4.3 consists of two “clusters”
such that the intra-cluster distance of each cluster is extremely small
(specifically, $\epsilon$) and the inter-cluster distance between them is
large. The ILD value is maximized when the same number of items from each
cluster are selected. However, any set of three or more items has a dispersion
$\epsilon$; namely, we cannot distinguish between the largest-ILD case and the
small-ILD case based on the value of dispersion.

In the reverse direction, we provide a very simple input such that _no matter
how large the ILD value is, the dispersion value can be $0$_, whose proof is
deferred to Appendix A.

###### Claim 4.4.

There exists an input such that the pairwise distance is the Euclidean
distance and
$\frac{\textsf{{disp}}(S_{\textsf{{ILD}}}^{*})}{{\mathrm{OPT}}_{\textsf{{disp}}}}=\frac{\textsf{{disp}}(S_{\textsf{{ILD}}}^{\mathrm{Gr}})}{{\mathrm{OPT}}_{\textsf{{disp}}}}=0.$
In other words, greedy or exact maximization of ILD does not have any
approximation guarantee to disp-diversification.

_Remark:_ The input used in the proof of Claim 4.4 consists of (duplicates
allowed) points on a line segment. Dispersion selects distinct points
naturally. In contrast, ILD prefers points on the two ends of the segment,
which are redundant.

###  4.3. Lessons Learned

Based on the theoretical investigations so far, we discuss the pros and cons
of ILD and dispersion. Figure 2 shows two illustrative inputs such that
maximization of ILD and dispersion results in very different solutions, where
each item is a $2$-dimensional vector and the distance between items is
measured by the Euclidean distance.

(a) Two separated circles (cf. Claim 4.3). (b) An ellipse (cf. Claim 4.4).

Figure 2. Two inputs for which maximization of ILD and dispersion results in
very different solutions.

  * •

Pros of ILD: If the entire item set is separated into two “clusters” as shown
in Figure 2a, ILD selects items in a well-balanced manner; i.e., a nearly
equal number of items from each cluster are chosen (supported by Claim 4.3).

  * •

Cons of ILD: ILD may select duplicate items that are very close (or even
identical) to each other. Suppose that we are given feature vectors in an
ellipse shown in Figure 2b. Then, ILD would select items from the left and
right ends, each of which consists of similar feature vectors (supported by
Claim 4.4); even more, items in the middle of the ellipse are never chosen.

In practice, if item features are given by _dense_ vectors such as those
generated by deep neural networks, ILD is undesirable because it selects many
nearly-identical vectors.

  * •

Pros of dispersion: If the entire item set is “well-dispersed” as in Figure
2b, then so are the items chosen by dispersion as well.

  * •

Cons of dispersion: Dispersion may overlook distant item pairs that would have
contributed to ILD. Suppose that we are given feature vectors in two circles
in Figure 2a. Because the dispersion value of any (three or more) items is
small whereas the diameter is large, we cannot distinguish distant items from
close items using only the dispersion value. Thus, dispersion may select items
in an unbalanced manner in the worst case (as in Claim 4.3).

In practice, if item features are given by _sparse_ (e.g., 0-1) vectors, such
as indicator functions defined by genre or topic information, dispersion may
not be favorable, because its value becomes $0$ whenever two or more items
with the same feature are selected.

##  5\. Gaussian Intra-List Distance

In Section 4.3, we discussed that ILD and dispersion have their own _extreme
behaviors_. We now argue that they can be viewed as limits in the sense of a
kernel function over items, i.e., we apply the Gaussian kernel to ILD. The
_Gaussian kernel_ for two vectors
$\mathbf{\bm{x}},\mathbf{\bm{y}}\in\mathbb{R}^{d}$ is defined as
$K(\mathbf{\bm{x}},\mathbf{\bm{y}})\triangleq\exp\Bigl{(}-\frac{\|\mathbf{\bm{x}}-\mathbf{\bm{y}}\|^{2}}{2\sigma^{2}}\Bigr{)},$
where $\sigma>0$ is a _bandwidth_ parameter that controls the smoothness of
the estimated function in kernel methods. Since the kernel function can be
considered as _similarity score_ , we can define the _kernel distance_
(phillips2011gentle) as
$d_{K}(\mathbf{\bm{x}},\mathbf{\bm{y}})=\sqrt{2-2K(\mathbf{\bm{x}},\mathbf{\bm{y}})}.$
Using this kernel distance, we define the _Gaussian ILD (GILD)_ as

(3) $\displaystyle\textsf{{GILD}}_{\sigma}(S)\triangleq\frac{1}{{|S|\choose
2}}\sum_{i\neq j\in
S}\sqrt{2-2\exp\left(-\frac{d(i,j)^{2}}{2\sigma^{2}}\right)},$

where $d$ is a distance metric and $\sigma$ is a bandwidth parameter.111 Note
that we have replaced the Euclidean distance in
$\exp\Bigl{(}-\frac{\|\mathbf{\bm{x}}_{1}-\mathbf{\bm{x}}_{j}\|^{2}}{2\sigma^{2}}\Bigr{)}$
by $d$ so that we can use any distance metric.  The following asymptotic
analysis shows that GILD interpolates ILD and dispersion, whose proof is
deferred to Appendix A.

###### Theorem 5.1.

GILD approaches ILD as the value of $\sigma$ goes to $\infty$, and it
approaches dispersion as the value of $\sigma$ goes to $0$ (up to scaling and
addition by a constant).

Theorem 5.1 implies that GILD behaves as a compromise between ILD and
dispersion by tuning the bandwidth parameter $\sigma$: the value of $\sigma$
must be small if we do not want the selected items to be close to each other;
$\sigma$ must be large if we want to include (a few) distance items.

We use GILD to better understand the empirical behavior of ILD and dispersion.
In particular, we are interested to know whether GILD can avoid the extreme
behavior of ILD and dispersion.

###  5.1. Choosing the Value of $\sigma$

Here, we briefly establish how to choose the value of $\sigma$ in Section 6.
As will be shown in Section 6.2.3, GILD usually exhibits extreme behaviors
like ILD or dispersion. We wish to determine the value of $\sigma$ for which
GILD interpolates them. Suppose that we have selected $k$ items, denoted $S$.
In Eq. 6 in the proof of Theorem 5.1, for the first two terms to be dominant,
we must have $C\gg({k\choose 2}-C)\cdot\epsilon_{\sigma},$ which implies that
$\sigma\gg\sqrt{\frac{(\textsf{{disp}}(S)+\delta)^{2}-\textsf{{disp}}(S)^{2}}{2\log({k\choose
2}-1)}}.$ Based by this, we propose the following two schemes for determining
the value of $\sigma$, referred to as the _adjusted minimum_ and the _adjusted
median_ :

(4) $\displaystyle\sigma_{S}^{\min}\triangleq\frac{\min_{i\neq j\in
S}d(i,j)}{\sqrt{2\log({k\choose 2}-1)}}\text{ and
}\sigma_{S}^{\mathrm{med}}\triangleq\frac{\operatorname*{median}_{i\neq j\in
S}d(i,j)}{\sqrt{2\log({k\choose 2}-1)}}.$

Note that $\sigma_{S}^{\min}\leq\sigma_{S}^{\mathrm{med}}$, and the adjusted
median mimics the median heuristic (gretton2012optimal; garreau2017large) in
kernel methods. In Section 6, we empirically justify that dividing by
$\sqrt{2\log({k\choose 2}-1)}$ is necessary. Since $\sigma_{S}^{\min}$ and
$\sigma_{S}^{\mathrm{med}}$ depend on $S$, we run the greedy heuristic while
adjusting the value of $\sigma$ _adaptively_ using Eq. 4: More precisely, in
line 1 of Algorithm 1, we define
$f(\\{i_{1},\ldots,i_{\ell},i\\})\triangleq\textsf{{GILD}}_{\sigma}(S\cup\\{i\\})-\textsf{{GILD}}_{\sigma}(S)$,
where $S\triangleq\\{i_{1},\ldots,i_{\ell}\\}$ and $\sigma$ is
$\sigma_{S\cup\\{i\\}}^{\min}$ or $\sigma_{S\cup\\{i\\}}^{\mathrm{med}}$. We
further slightly modify this heuristic so that it selects the pair of farthest
items when $k=2$ because $\sqrt{2\log({k\choose 2}-1)}$ is $-\infty$.

$\operatorname{\mathop{\mathsf{f}}}$ $\operatorname{\mathop{\mathsf{g}}}$ |  rel. score $\operatorname{\mathop{\mathsf{g}}}(S_{\operatorname{\mathop{\mathsf{f}}},k}^{\mathrm{Gr}})/\operatorname{\mathop{\mathsf{g}}}(S_{\operatorname{\mathop{\mathsf{g}}},k}^{\mathrm{Gr}})$
---|---
ILD | disp | GILD
ILD | – | 0.424 | 0.997
disp | 0.941 | – | 1.000
GILD | 0.972 | 0.818 | –
Random | 0.345 | 0.053 | 0.934
Table 1. Average rel. score of each pair of diversity objs. for feedback on
ML-1M.

$\operatorname{\mathop{\mathsf{f}}}$ $\operatorname{\mathop{\mathsf{g}}}$ |  rel. score $\operatorname{\mathop{\mathsf{g}}}(S_{\operatorname{\mathop{\mathsf{f}}},k}^{\mathrm{Gr}})/\operatorname{\mathop{\mathsf{g}}}(S_{\operatorname{\mathop{\mathsf{g}}},k}^{\mathrm{Gr}})$
---|---
ILD | disp | GILD
ILD | – | 0.211 | 0.999
disp | 0.975 | – | 0.998
GILD | 0.997 | 0.360 | –
Random | 0.142 | 0.001 | 0.810
Table 2. Average rel. score of each pair of diversity objs. for feedback on
Amazon.

$\operatorname{\mathop{\mathsf{f}}}$ $\operatorname{\mathop{\mathsf{g}}}$ |  rel. score $\operatorname{\mathop{\mathsf{g}}}(S_{\operatorname{\mathop{\mathsf{f}}},k}^{\mathrm{Gr}})/\operatorname{\mathop{\mathsf{g}}}(S_{\operatorname{\mathop{\mathsf{g}}},k}^{\mathrm{Gr}})$
---|---
ILD | disp | GILD
ILD | – | 0.048 | 0.797
disp | 0.859 | – | 0.936
GILD | 0.889 | 0.195 | –
Random | 0.842 | 0.162 | 0.955
Table 3. Average rel. score of each pair of diversity objs. for TwoCircles.

$\operatorname{\mathop{\mathsf{f}}}$ $\operatorname{\mathop{\mathsf{g}}}$ |  rel. score $\operatorname{\mathop{\mathsf{g}}}(S_{\operatorname{\mathop{\mathsf{f}}},k}^{\mathrm{Gr}})/\operatorname{\mathop{\mathsf{g}}}(S_{\operatorname{\mathop{\mathsf{g}}},k}^{\mathrm{Gr}})$
---|---
ILD | disp | GILD
ILD | – | 0.153 | 0.976
disp | 0.959 | – | 0.999
GILD | 0.970 | 0.911 | –
Random | 0.877 | 0.000 | 0.933
Table 4. Average rel. score of each pair of diversity objs. for genre on
ML-1M.

$\operatorname{\mathop{\mathsf{f}}}$ $\operatorname{\mathop{\mathsf{g}}}$ |  score $\operatorname{\mathop{\mathsf{g}}}(S_{\operatorname{\mathop{\mathsf{f}}},k}^{\mathrm{Gr}})/\operatorname{\mathop{\mathsf{g}}}(S_{\operatorname{\mathop{\mathsf{g}}},k}^{\mathrm{Gr}})$
---|---
ILD | disp | GILD
ILD | – | 0.378 | 0.996
disp | 0.979 | – | 0.999
GILD | 0.989 | 0.926 | –
Random | 0.966 | 0.137 | 0.990
Table 5. Average rel. score of each pair of diversity objs. for genre on
Amazon.

$\operatorname{\mathop{\mathsf{f}}}$ $\operatorname{\mathop{\mathsf{g}}}$ |  rel. score $\operatorname{\mathop{\mathsf{g}}}(S_{\operatorname{\mathop{\mathsf{f}}},k}^{\mathrm{Gr}})/\operatorname{\mathop{\mathsf{g}}}(S_{\operatorname{\mathop{\mathsf{g}}},k}^{\mathrm{Gr}})$
---|---
ILD | disp | GILD
ILD | – | 0.041 | 0.652
disp | 0.684 | – | 1.000
GILD | 0.758 | 0.272 | –
Random | 0.567 | 0.185 | 0.985
Table 6. Average rel. score of each pair of diversity objs. for Ellipse.

Figure 3. Relative score of each objective to dispersion for feedback on
ML-1M. Figure 4. Relative score of each objective to dispersion for genre on
ML-1M. Figure 5. Relative score of each objective to ILD for genre on ML-1M.

##  6\. Empirical Comparison

We report the experimental results of the empirical comparison among the
diversity objectives analyzed in Sections 4 and 5. The theoretical results in
Section 4 demonstrate that each objective captures its own notion of
diversity; thus, enhancing one objective is generally unhelpful in improving
another. One may think that such results based on _worst-case analysis_ are
too pessimistic to be applied in practice; for instance, ILD may be used to
enhance dispersion in real data, even though any positive approximation
guarantee is impossible. Thus, we _empirically_ analyze the approximation
factor for the diversity objectives examined thus far.

###  6.1. Settings

####  6.1.1. Datasets

We use two real-world datasets including feedback and genre information and
two synthetic datasets.

  * 1.

MovieLens 1M (ML-1M) (harper2015movielens; movielensurl): Genre information is
associated with each movie; there are $18$ genres. We extracted the subset in
which users and movies have at least $20$ ratings, resulting in $995$ thousand
ratings on $3{,}000$ movies from $6{,}000$ users.

  * 2.

Amazon Review Data Magazine Subscriptions (Amazon) (ni2019justifying;
amazonurl): Each product contains categorical information, and there are $165$
categories. We extracted the subset in which all users and movies have at
least five ratings, resulting in $4{,}200$ reviews of $720$ products from
$664$ users.

  * 3.

Random points in two separated circles (TwoCircles, Figure 2a): Consist of
$1{,}000$ random points in two circles whose radius is $\frac{1}{4}$ and
centers are $-\frac{3}{4}$ and $\frac{3}{4}$.

  * 4.

Random points in an ellipse (Ellipse, Figure 2b): Consist of $1{,}000$ random
points in an ellipse of flattening $\frac{3}{4}$.

####  6.1.2. Distance Metrics

We use two types of distance metrics for real-world datasets.

  * 1.

_Implicit feedback_ (feedback for short): Let $\mathbf{\bm{X}}$ be a user-item
implicit feedback matrix over $m$ users and $n$ items, such that $X_{u,i}$ is
$1$ if user $u$ interacts with item $i$, and $0$ if there is no interaction.
We run singular value decomposition on $\mathbf{\bm{X}}$ with dimension
$d\triangleq 32$ to obtain
$\mathbf{\bm{X}}=\mathbf{\bm{U}}\mathbf{\bm{\Sigma}}\mathbf{\bm{V}}^{\top}$,
where
$\mathbf{\bm{V}}^{\top}=[\mathbf{\bm{v}}_{1},\ldots,\mathbf{\bm{v}}_{n}]\in\mathbb{R}^{d\times
n}$. The feature vector of item $i$ is then defined as $\mathbf{\bm{v}}_{i}$
and the distance between two items $i,j$ is given by the Euclidean distance
$d(i,j)\triangleq\|\mathbf{\bm{v}}_{i}-\mathbf{\bm{v}}_{j}\|$.

  * 2.

_Genre information_ (genre for short): We denote by $G_{i}$ the set of genres
that item $i$ belongs to. The distance between two items $i,j$ is given by the
Jaccard distance $d(i,j)\triangleq 1-\frac{|G_{i}\cap G_{j}|}{|G_{i}\cup
G_{j}|}$. Multiple items may have the same genre set; i.e., $d(i,j)=0$ for
some $i\neq j$.

For two synthetic datasets, we simply use the Euclidean distance.

####  6.1.3. Diversity Enhancement Algorithms

We apply the greedy heuristic (Algorithm 1) to ILD, dispersion, and GILD with
the adjusted median. A baseline that returns a random set of items (denoted
Random) is implemented. Experiments were conducted on a Linux server with an
Intel Xeon 2.20GHz CPU and 62GB RAM. All programs were implemented using
Python 3.9.

###  6.2. Results

We calculate the empirical approximation factor for each pair of diversity
objectives $\operatorname{\mathop{\mathsf{f}}}$ and
$\operatorname{\mathop{\mathsf{g}}}$ as follows. First, we run the greedy
heuristic on $\operatorname{\mathop{\mathsf{f}}}$ to extract up to $128$
items. The empirical approximation factor of
$\operatorname{\mathop{\mathsf{f}}}$ to $\operatorname{\mathop{\mathsf{g}}}$
is obtained by
$\operatorname{\mathop{\mathsf{g}}}(S_{\operatorname{\mathop{\mathsf{f}}},k}^{\mathrm{Gr}})/\operatorname{\mathop{\mathsf{g}}}(S_{\operatorname{\mathop{\mathsf{g}}},k}^{\mathrm{Gr}})$
for each $k\in[128]$. This factor usually takes a number from $0$ to $1$ and
is simply referred to as the _relative score of
$\operatorname{\mathop{\mathsf{f}}}$ to $\operatorname{\mathop{\mathsf{g}}}$_.
Unlike the original definition in Eq. 2, we do not use
${\mathrm{OPT}}_{\operatorname{\mathop{\mathsf{g}}},k}$ because its
computation is NP-hard. Tables 6, 6, 6, 6, 6 and 6 report the average relative
score over $k=2,\ldots,128$.

####  6.2.1. ILD vs. Dispersion vs. GILD in Practice

The relative score of ILD to dispersion is first investigated, where we proved
that no approximation guarantee is possible (Claim 4.4). In almost all cases,
the relative score is extremely low, with the highest being $0.424$. This is
because that multiple items with almost-the-same features were selected,
resulting in a small (or even $0$) value of dispersion. Figure 5 shows that
ILD selects items that have similar feature vectors when $k=34$; we thus
confirmed the claim in Section 4.3 that ILD selects nearly-identical items in
the case of dense feature vectors. Moreover, Figure 5 shows that it selects
duplicate items that share the same genre set at $k=23$.

We then examine the relative score of dispersion to ILD, for which we provided
an approximation factor of $\max\\{\frac{d_{k}^{*}}{2D},\frac{1}{k}\\}$
(Theorem 4.2). Tables 6, 6, 6, 6, 6 and 6 show that the relative score is
better than $0.859$ except for Ellipse, which is better than expected from
$\frac{1}{k}$. Figure 5 also indicates that the relative score does _not_
decay significantly; e.g., at $k=100$, the relative score is better than
$0.94$ even though the worst-case approximation factor is $\frac{1}{k}=0.01$.

It is evident that GILD has a higher relative score to ILD than dispersion,
and a higher relative score to dispersion than ILD for all settings. That is,
GILD finds an intermediate set between ILD and dispersion, suggesting that ILD
and dispersion exhibit the extreme behavior in practice as discussed in
Section 4.

(a) $128$ points chosen by ILD. (b) $128$ points chosen by dispersion. (c)
$128$ points chosen by GILD.

Figure 6.  $128$ points (big red circles) of Ellipse selected by greedily
maximizing each objective with the Euclidean distance.

(a) $128$ points chosen by ILD. (b) $128$ points chosen by dispersion. (c)
$128$ points chosen by GILD.

Figure 7.  $128$ points (big red circles) of TwoCircles selected by greedily
maximizing each objective with the Euclidean distance. Figure 8. Histogram of
the pairwise distances of the selected items on Ellipse.

####  6.2.2. Qualitative Analysis via Visualization

We qualitatively assess the diversity objectives based on the visualization of
synthetic datasets. We first investigate Ellipse, in which ILD may select
duplicate items (see Section 4.3). Figure 6 shows items of Ellipse that are
selected by each diversity objective; Figure 8 shows the histogram of the
pairwise Euclidean distances between the selected items. The items selected by
ILD can be partitioned into two groups: the left and right ends of the ellipse
(Figure 6a). The histogram further shows that the inter-group distance between
them is approximately $1.8$ whereas the intra-group distance is close to $0$.
Thus, the drawback of ILD in Section 4.3 occurs empirically. Unlike ILD, the
items selected by dispersion are well dispersed (Figure 6b); however, it
misses many pairs of distant items as shown in Figure 8. One reason for this
result is given that dispersion is the minimum pairwise distance, maximizing
the value of dispersion does not lead to the selection of distant item pairs,
as discussed in Section 4.3. In contrast, the items chosen by GILD are not
only scattered (Figure 6c); they include more dissimilar items than
dispersion, as shown in the histogram. This observation can be explained by
the GILD mechanism, which takes the sum of the kernel distance over _all_
pairs.

We then examine TwoCircles. Figure 7 shows that each diversity objective
selects almost the same number of items from each cluster. In particular, the
potential drawback of dispersion discussed in Section 4.3, i.e., the imbalance
of selected items in the worst case, does not occur empirically.

(a) $k=16$. (b) $k=128$.

Figure 9. Trade-off between ILD and dispersion. For each value of $\sigma$, we
plot $\textsf{{ILD}}(S_{\textsf{{GILD}}_{\sigma},k}^{\mathrm{Gr}})$ and
$\textsf{{disp}}(S_{\textsf{{GILD}}_{\sigma},k}^{\mathrm{Gr}})$.

####  6.2.3. Investigation of the Effect of $\sigma$ on GILD

We investigate the empirical effect of the value of $\sigma$ on the behavior
of GILD. Specifically, we examine how GILD interpolates between ILD and
dispersion by changing $\sigma$, as suggested in Theorem 5.1. Setting the
value of $\sigma$ to each of $64$ equally-spaced numbers on a log scale from
$0.02$ to $1$, we greedily maximize $\textsf{{GILD}}_{\sigma}$ for feedback on
ML-1M to obtain a $k$-item set $S_{\textsf{{GILD}}_{\sigma},k}$. We also run
the adaptive greedy heuristic, which is oblivious to the value of $\sigma$, to
obtain a $k$-item set $S_{\textsf{{GILD}},k}$. Figure 9 plots values of ILD
and dispersion for each obtained set $S_{\textsf{{GILD}}_{\sigma},k}$ of size
$k=16,128$. The vertical lines correspond to the adjusted minimum
$\sigma_{S_{\textsf{{GILD}},k}}^{\min}$, adjusted median
$\sigma_{S_{\textsf{{GILD}},k}}^{\mathrm{med}}$, minimum $\min_{i\neq j\in
S_{\textsf{{GILD}},k}}d(i,j)$, and median $\operatorname*{median}_{i\neq j\in
S_{\textsf{{GILD}},k}}d(i,j)$. Horizontal lines correspond to
$\textsf{{ILD}}(S_{\textsf{{ILD}}}^{\mathrm{Gr}})\approx{\mathrm{OPT}}_{\textsf{{ILD}}}$,
$\textsf{{ILD}}(S_{\textsf{{disp}}}^{\mathrm{Gr}})$,
$\textsf{{disp}}(S_{\textsf{{disp}}}^{\mathrm{Gr}})\approx{\mathrm{OPT}}_{\textsf{{disp}}}$,
and $\textsf{{disp}}(S_{\textsf{{ILD}}}^{\mathrm{Gr}})$. Observe first that
ILD is monotonically increasing in $\sigma$ and approaches
${\mathrm{OPT}}_{\textsf{{ILD}}}$; disp is approximately decreasing in
$\sigma$ and attains ${\mathrm{OPT}}_{\textsf{{disp}}}$ for a “moderately
small” value of $\sigma$, which coincides with Theorem 5.1.

Observe also that the degradation of both ILD and disp occurs for small values
of $\sigma$. The reason is that each term
$\exp\Bigl{(}-\frac{d(i,j)^{2}}{2\sigma^{2}}\Bigr{)}$ in GILD becomes
extremely small, causing a floating-point rounding error. Setting $\sigma$ to
the minimum and median results in a dispersion value of
$\textsf{{disp}}(S_{\textsf{{ILD}}}^{\mathrm{Gr}})$ when $k=16$; i.e., the
obtained set is almost identical to $S_{\textsf{{ILD}}}^{\mathrm{Gr}}$. In
contrast, setting $\sigma=\sigma_{S_{\textsf{{GILD}},k}}^{\min}$ is similar to
$S_{\textsf{{disp}}}^{\mathrm{Gr}}$; setting
$\sigma=\sigma_{S_{\textsf{{GILD}},k}}^{\mathrm{med}}$ yields a set whose
dispersion is between $\textsf{{disp}}(S_{\textsf{{disp}},k}^{\mathrm{Gr}})$
and $\textsf{{disp}}(S_{\textsf{{ILD}},k})$ and whose ILD is in the middle of
$\textsf{{ILD}}(S_{\textsf{{ILD}},k}^{\mathrm{Gr}})$ and
$\textsf{{ILD}}(S_{\textsf{{disp}},k})$. Thus, using the adjusted median, and
division by $\sqrt{2\log{k\choose 2}-1}$ is crucial for avoiding trivial sets.

Figure 10.  Dispersion of items for genre on ML-1M.

Figure 11.  Relation between each pair of nDCG, nILD, and ndisp with regard to
a trade-off parameter $\lambda$.

###  6.3. Discussions

We discuss the empirical behavior of ILD, dispersion, and GILD. Arguably, ILD
easily selects many items that are similar or identical. As shown in Figure
6a, the chosen items are biased toward two distant groups, and items in the
middle of the two groups never appear. This is undesirable if we wish to
recommend very few items.

Such drawbacks of ILD can be resolved via dispersion. Greedy maximization of
dispersion also empirically enhances the ILD value. However, it may overlook
distant item pairs, as discussed in Section 6.2.2. We also note that
dispersion is not suitable for measuring diversity. As shown in Figure 10, the
value of dispersion drops to nearly $0$ when selecting a moderate number of
items; it does _not_ return to a positive value. Due to this nature,
dispersion may not be used to compare large item sets.

The empirical result of GILD implies that ILD and dispersion are not
appropriate for improving and/or evaluating distance-based diversity. GILD
partially circumvents the issues caused by the extreme behavior of ILD and
dispersion, thereby achieving the _sweet spot_ between them. On the one hand,
GILD extracts dissimilar items such that the dispersion value does not drop to
$0$. On the other hand, GILD can select more dissimilar items than dispersion.
Similar to dispersion, GILD cannot be used to _compare_ the diversity among
distinct sets, as shown in Table 6, which indicates that even Random can have
the highest GILD value. This is because GILD with the adjusted median is
designed to evaluate the next item to be selected given a _fixed_ set of
already-selected items. To sum up, GILD works successfully as an optimization
objective interpolating ILD and dispersion and as a tool for analyzing them
empirically.

##  7\. Diversified Recommendation Results

Having a better understanding of the behavior of diversity objectives from
both theoretical (Section 4) and empirical perspectives (Section 6), we
incorporate them into the recommendation methods.

###  7.1. Settings

####  7.1.1. Dataset

To investigate results produced by a recommendation method using ILD,
dispersion, and GILD, we use the ML-1M dataset, the details of which are
described in Section 6.1. We extracted the subset in which users and movies
have at least $20$ and $100$ ratings, respectively, resulting in $370$
thousand ratings on $2{,}000$ movies from $2{,}800$ users. The obtained subset
was further split into training, validation, and test sets in a $60/20/20$
ratio according to weak generalization; i.e., they may not be disjoint in
terms of users.

####  7.1.2. Algorithms

We adopt Embarrassingly Shallow AutoEncoder ($\textsc{ease}^{\textsc{r}}$)
(steck2019embarrassingly) to estimate the predictive score
$\mathsf{rel}_{u}(i)$ for item $i$ by user $u$ from a user-item implicit
feedback matrix. $\textsc{ease}^{\textsc{r}}$ has a hyperparameter for
$L_{2}$-norm regularization, and its value is tuned using the validation set.
We construct a distance metric based on the _implicit feedback_ in Section 6.1
to define ILD, dispersion, and GILD. We then apply the greedy heuristic to a
linear combination of relevance and diversity. Specifically, given a set
$S_{\ell-1}$ of already selected $\ell-1$ items, we select the next item
$i_{\ell}$ that maximizes the following objective:

(5)
$\displaystyle\mathsf{F}_{u,\operatorname{\mathop{\mathsf{f}}},\lambda}(i)\triangleq(1-\lambda)\cdot\mathsf{rel}_{u}(i)+\lambda\cdot\\{\operatorname{\mathop{\mathsf{f}}}(S_{\ell-1}\cup\\{i\\})-\operatorname{\mathop{\mathsf{f}}}(S_{\ell-1})\\},$

where $\lambda\in(0,1)$ is a trade-off parameter between relevance and
diversity. We run the greedy heuristic for each
$\operatorname{\mathop{\mathsf{f}}}$, each value of
$\lambda=0,0.1,0.2,\ldots,0.9,0.99,0.999,1$, and each user $u$ to retrieve a
list of $k\triangleq 50$ items to be recommended to $u$, denoted
$S_{u,\operatorname{\mathop{\mathsf{f}}},\lambda}$. Experiments were conducted
on the same environment as described in Section 6.

####  7.1.3. Evaluation

We evaluate the accuracy and diversity of the obtained sets as follows. Let
$R_{u}$ denote the set of relevant items to user $u$ (i.e., those interacting
with $u$) in the test set. We calculate the _normalized Discounted Cumulative
Gain (nDCG)_ by

$\displaystyle\textsf{{nDCG}}@k(S_{u,\operatorname{\mathop{\mathsf{f}}},\lambda};R_{u})$
$\displaystyle\triangleq\Bigl{(}\sum_{\ell\in[\min\\{k,|R_{u}|\\}]}\frac{1}{\log_{2}(\ell+1)}\Bigr{)}^{-1}\cdot$
$\displaystyle\sum_{\ell\in[k]}\frac{[\\!\\![\ell\text{-th ranked item of
}S_{u,\operatorname{\mathop{\mathsf{f}}},\lambda}\text{ is in
}R_{u}]\\!\\!]}{\log_{2}(\ell+1)}.$

We calculate the normalized versions of ILD and dispersion as
$\textsf{{nILD}}(S_{u,\operatorname{\mathop{\mathsf{f}}},\lambda})\triangleq\frac{\textsf{{ILD}}(S_{u,\operatorname{\mathop{\mathsf{f}}},\lambda})}{\textsf{{ILD}}(S_{u,\textsf{{ILD}}}^{\mathrm{Gr}})}$
and
$\textsf{{ndisp}}(S_{u,\operatorname{\mathop{\mathsf{f}}},\lambda})\triangleq\frac{\textsf{{disp}}(S_{u,\operatorname{\mathop{\mathsf{f}}},\lambda})}{\textsf{{disp}}(S_{u,\textsf{{disp}}}^{\mathrm{Gr}})}$,
respectively, where $S_{u,\operatorname{\mathop{\mathsf{f}}}}^{\mathrm{Gr}}$
is the set of $k$ items obtained by greedily maximizing
$\operatorname{\mathop{\mathsf{f}}}$ on the set of items that do not appear in
the training or validation set. We then take the mean of nDCG, nILD, and ndisp
over all users.

###  7.2. Results

Figure 11 shows the relation between each pair of nDCG, nILD, and ndisp.
First, we observe a clear trade-off relationship between relevance and
diversity regarding $\lambda$. In particular, when diversity is not introduced
into the objective (i.e., $\lambda=0$), the mean ndisp takes $0$, which
implies that for most users, two or more of selected items have the same genre
set. As shown in Section 6, incorporating ILD does not avoid the case of
$\textsf{{ndisp}}=0$. In contrast, dispersion and GILD with a moderate value
of $\lambda$ enhance nILD and ndisp without substantially sacrificing
accuracy. Comparing dispersion and GILD, it is observed that GILD achieves a
slightly higher nILD than dispersion: When the mean nDCG is close to $0.25$,
the means of nILD for GILD and dispersion are $0.966$ and $0.948$,
respectively, and the means of ndisp for them are $0.987$ and $0.992$,
respectively.

Figure 12.  Comparison of dispersion and GILD in terms of nDCG and nILD.

Although dispersion and GILD have a similar trade-off for the high-relevance
case (i.e., mean $\textsf{{nDCG}}\geq 0.4$), which is often a realistic
situation, they produce different results at the _individual level_. To this
end, we select $\lambda$ such that they are nearly identical _on average_.
Specifically, we choose $\lambda=0.2$ for dispersion and $\lambda=0.7$ for
GILD, for which the means of nDCG, nILD and ndisp are respectively $0.457$,
$0.870$ and $0.009$ for dispersion, whereas those are respectively $0.445$,
$0.877$ and $0.001$ for GILD. The left figure in Figure 12 plots the nDCG of
$S_{u,\textsf{{disp}},0.2}$ and $S_{u,\textsf{{GILD}},0.7}$ for each user $u$.
Observe that dispersion and GILD show a similar trend; the standard deviation
of nDCG is $0.161$ for dispersion and $0.160$ for GILD. In contrast, as shown
in the right figure in Figure 12, dispersion often has a smaller nILD than
GILD. Furthermore, the standard deviation of nILD for dispersion ($0.051$) is
larger than that for GILD ($0.038$). This difference is possibly due to the
potential drawback of dispersion (see Section 4.3): Since the values of
dispersion for most users become $0$ at a particular iteration of the greedy
heuristic, the objective $\mathsf{F}_{u,\textsf{{disp}},0.2}(i)$ in Eq. 5 is
$0.8\mathsf{rel}_{u}(i)$ in the subsequent iterations; i.e., the greedy
heuristic only selects the item with the highest relevance. Consequently,
dispersion fails to diversify some users’ recommendation results, which is not
the case for GILD. In summary, as a diversity objective to be optimized in
diversified recommendation, ILD and dispersion are not an appropriate choice.

##  8\. Conclusions

To investigate the behavior of two common diversity objectives, ILD and
dispersion, we performed a comparison analysis. Our results revealed the
drawbacks of the two: ILD selects _duplicate_ items, while dispersion may
overlook _distant_ item pairs. To analyze these drawbacks empirically, we
designed Gaussian ILD (GILD) as an interpolation between ILD and dispersion.
In the personalized recommendation setting, we demonstrated that both ILD and
dispersion are not consistently successful in enhancing diversity at the
individual level. As a future work, we plan to develop an evaluation measure
of diversity in lieu of ILD and dispersion.

##  Appendix A Omitted Proofs in Sections 4 and 5

###### Proof of Theorem 4.2.

The first guarantee is immediate from ${\mathrm{OPT}}_{\textsf{{ILD}}}\leq D$
and $\textsf{{ILD}}(S_{\textsf{{disp}}}^{*})\geq d_{k}^{*}$. Similarly, we
have
$\textsf{{ILD}}(S_{\textsf{{disp}}}^{\mathrm{Gr}})\geq\textsf{{disp}}(S_{\textsf{{disp}}}^{\mathrm{Gr}})\geq\frac{d_{k}^{*}}{2}$
due to a $\frac{1}{2}$-approximation guarantee of the greedy heuristic
(ravi1994heuristic). Let $i_{\ell}\in S_{\textsf{{disp}}}^{\mathrm{Gr}}$
denote the $\ell$-th item selected by greedy heuristic on disp. Since $i_{2}$
is farthest from $i_{1}$, $d(i_{1},i_{2})\geq\frac{D}{2}$. By the triangle
inequality of $d$, we have $d(i_{1},i_{\ell})+d(i_{\ell},i_{2})\geq
d(i_{1},i_{2})$ for all $\ell\geq 3$. Thus,

$\displaystyle\textsf{{ILD}}(S_{\textsf{{disp}}}^{\mathrm{Gr}})$
$\displaystyle={k\choose 2}^{-1}\left[d(i_{1},i_{2})+\sum_{3\leq\ell\leq
k}d(i_{1},i_{\ell})+d(i_{\ell},i_{2})\right]$ $\displaystyle\geq{k\choose
2}^{-1}\frac{D}{2}(k-1)=\frac{D}{k},$

implying that
$\frac{\textsf{{ILD}}(S_{\textsf{{disp}}}^{\mathrm{Gr}})}{{\mathrm{OPT}}_{\textsf{{ILD}}}}\geq\frac{1}{k}.$
∎

###### Proof of Claim 4.3.

Let $n$ be a multiple of $4$ and $\epsilon>0$ a small number. Construct $2n$
vectors in $\mathbb{R}_{+}^{n+2}$, denoted
$\mathbf{\bm{X}}\triangleq\\{\mathbf{\bm{x}}_{1},\ldots,\mathbf{\bm{x}}_{\frac{n}{2}}\\}$
and
$\mathbf{\bm{Y}}\triangleq\\{\mathbf{\bm{y}}_{1},\ldots,\mathbf{\bm{y}}_{\frac{n}{2}}\\}$,
each entry of which is defined as:

$\displaystyle
x_{i}(j)\triangleq\begin{cases}\frac{\epsilon}{\sqrt{2}}&\text{if }j=i,\\\
\sqrt{\frac{1-\epsilon^{2}}{2}}&\text{if }j=n+1,\\\
0&\text{otherwise,}\end{cases}\text{and
}y_{i}(j)\triangleq\begin{cases}\frac{\epsilon}{\sqrt{2}}&\text{if
}j=i+\frac{n}{2},\\\ \sqrt{\frac{1-\epsilon^{2}}{2}}&\text{if }j=n+2,\\\
0&\text{otherwise.}\end{cases}$

Observe that
$\|\mathbf{\bm{x}}_{i}-\mathbf{\bm{x}}_{j}\|=\|\mathbf{\bm{y}}_{i}-\mathbf{\bm{y}}_{j}\|=\epsilon$
for all $i\neq j\in[\frac{n}{2}]$,
$\|\mathbf{\bm{x}}_{i}-\mathbf{\bm{y}}_{j}\|=1$ for all $i,j\in[\frac{n}{2}]$,
and thus $D=1$. Consider selecting $k\triangleq\frac{n}{2}$ vectors from
$\mathbf{\bm{X}}\cup\mathbf{\bm{Y}}$ so that ILD or dispersion is maximized.
Clearly, ${\mathrm{OPT}}_{\textsf{{ILD}}}$ is ${k\choose
2}^{-1}((\frac{k}{2})^{2}+2{\nicefrac{{k}}{{2}}\choose 2}\epsilon)=\Theta(1)$,
which is attained when we select $\frac{k}{2}$ vectors each from
$\mathbf{\bm{X}}$ and $\mathbf{\bm{Y}}$. By contrast, _any_ set of $k$ items
has the same value of dispersion, i.e., $d_{k}^{*}\triangleq\epsilon$. Hence,
we may have
$S_{\textsf{{disp}}}^{*}=\\{\mathbf{\bm{x}}_{1},\ldots\mathbf{\bm{x}}_{k}\\}$
in the worst case, where $\textsf{{ILD}}(S_{\textsf{{disp}}}^{*})=\epsilon$.
Consequently, it holds that
$\frac{\textsf{{ILD}}(S_{\textsf{{disp}}}^{*})}{{\mathrm{OPT}}_{\textsf{{ILD}}}}=\mathcal{O}(\epsilon)=\mathcal{O}\left(\frac{d_{k}^{*}}{D}\right)$.
When we run the greedy heuristic on dispersion, we can assume that the first
selected item is $\mathbf{\bm{x}}_{1}$ without loss of generality. Then, we
would have selected $\mathbf{\bm{y}}_{i}$ for some $i$ as the second item. In
the remaining iterations, we may select $k-2$ vectors all from
$\mathbf{\bm{X}}$ in the worst case, resulting in
$\frac{\textsf{{ILD}}(S_{\textsf{{disp}}}^{\mathrm{Gr}})}{{\mathrm{OPT}}_{\textsf{{ILD}}}}=\frac{1}{\Theta(1)}{k\choose
2}^{-1}\Bigl{(}(k-1)+{k-1\choose
2}\epsilon\Bigr{)}=\mathcal{O}\Bigl{(}\frac{1}{k}+\frac{d_{k}^{*}}{D}\Bigr{)}$.
∎

###### Proof of Claim 4.4.

Let $n$ be an even number at least $4$. Construct $2n-2$ vectors in
$\mathbb{R}_{+}$, denoted
$\mathbf{\bm{X}}=\\{1,\ldots,(\nicefrac{{n}}{{2}}\text{ times}),\ldots,1\\}$,
$\mathbf{\bm{Y}}=\\{n,\ldots,(\nicefrac{{n}}{{2}}\text{ times}),\ldots,n\\}$,
and $\mathbf{\bm{Z}}=\\{2,3,\ldots,n-1\\}$. Selecting $k\triangleq n$ vectors
from $\mathbf{\bm{X}}\cup\mathbf{\bm{Y}}\cup\mathbf{\bm{Z}}$ so that the ILD
value is maximized, we have
$S_{\textsf{{ILD}}}^{*}=\mathbf{\bm{X}}\cup\mathbf{\bm{Y}}$. Observe easily
that the greedy heuristic selects at least two vectors from either
$\mathbf{\bm{X}}$ or $\mathbf{\bm{Y}}$. Therefore,
$\textsf{{disp}}(S_{\textsf{{ILD}}}^{*})=\textsf{{disp}}(S_{\textsf{{ILD}}}^{\mathrm{Gr}})=0$.
By contrast, the optimum dispersion is ${\mathrm{OPT}}_{\textsf{{disp}}}=1$
and attained when we select $\\{1,2,\ldots,n\\}$. ∎

###### Proof of Theorem 5.1.

Let $S\triangleq[n]$. We first calculate a limit of
$\textsf{{GILD}}_{\sigma}(S)$ as $\sigma\to\infty$. Define
$\epsilon_{\sigma}\triangleq\max_{i\neq j\in S}\frac{d(i,j)}{\sigma}.$ Using a
Taylor expansion of
$\exp\Bigl{(}-\frac{x^{2}}{2\sigma^{2}}\Bigr{)},=1-\frac{x^{2}}{2\sigma^{2}}+\mathcal{O}\left(\frac{x^{2}}{\sigma^{4}}\right),$
we derive

$\displaystyle\textsf{{GILD}}_{\sigma}(S)$ $\displaystyle={n\choose
2}^{-1}\sum_{i\neq j\in
S}\sqrt{\frac{d(i,j)^{2}}{\sigma^{2}}+\mathcal{O}\left(\frac{d(i,j)^{4}}{\sigma^{4}}\right)}$
$\displaystyle=\frac{\sqrt{1+\mathcal{O}(\epsilon_{\sigma}^{2})}}{\sigma}\cdot{n\choose
2}^{-1}\sum_{i\neq j\in S}d(i,j).$

Observing that $\lim_{\sigma\to\infty}\epsilon_{\sigma}=0$, we have
$\lim_{\sigma\to\infty}\frac{\textsf{{GILD}}_{\sigma}(S)}{\frac{1}{\sigma}\textsf{{ILD}}(S)}=1,$
completing the proof of the first statement.

We next calculate a limit of $\textsf{{GILD}}_{\sigma}(S)$ as $\sigma\to 0$.
Define $\delta\triangleq(\min_{i\neq j\in
S,d(i,j)>\textsf{{disp}}(S)}\allowbreak d(i,j))-\textsf{{disp}}(S).$ Note that
no pair of items $(i,j)$ satisfies
$\textsf{{disp}}(S)<d(i,j)<\textsf{{disp}}(S)+\delta$. Then define
$\epsilon_{\sigma}\triangleq\exp\left(-\frac{(\textsf{{disp}}(S)+\delta)^{2}-\textsf{{disp}}(S)^{2}}{2\sigma^{2}}\right).$
Observe that for any pair $(i,j)$,

$\displaystyle\exp\left(-\frac{d(i,j)^{2}}{2\sigma^{2}}\right)\text{ is
}\begin{cases}=\exp\left(-\frac{\textsf{{disp}}(S)^{2}}{2\sigma^{2}}\right)&\text{if
}d(i,j)=\textsf{{disp}}(S),\\\
\leq\epsilon_{\sigma}\exp\left(-\frac{\textsf{{disp}}(S)^{2}}{2\sigma^{2}}\right)&\text{otherwise.}\end{cases}$

Using a Taylor expansion of $\sqrt{1+x}=1+\frac{1}{2}x\pm\mathcal{O}(x^{2})$
yields

(6) $\displaystyle\begin{aligned}
&\textsf{{GILD}}_{\sigma}(S)=\sqrt{2}-\frac{C}{2\cdot{n\choose
2}}\cdot\exp\left(-\frac{\textsf{{disp}}(S)^{2}}{2\sigma^{2}}\right)\\\
&-\frac{{n\choose 2}-C}{2\cdot{n\choose
2}}\cdot\mathcal{O}\left(\epsilon_{\sigma}\cdot\exp\left(-\frac{\textsf{{disp}}(S)^{2}}{2\sigma^{2}}\right)\right)\pm\mathcal{O}\left(\exp\left(-\frac{\textsf{{disp}}(S)^{2}}{2\sigma^{2}}\right)^{2}\right),\end{aligned}$

where $C$ is the number of pairs $(i,j)$ with $d(i,j)=\textsf{{disp}}(S)$.
Observing that $\lim_{\sigma\to 0}\epsilon_{\sigma}=0$, we have

$\displaystyle\lim_{\sigma\to
0}\frac{\textsf{{GILD}}_{\sigma}(S)-\sqrt{2}}{-\frac{C}{2\cdot{n\choose
2}}\cdot\exp\left(-\frac{\textsf{{disp}}(S)^{2}}{2\sigma^{2}}\right)}=1,$

completing the proof of the second statement. ∎

## References

  * (1)
  * Adomavicius and Kwon (2012) Gediminas Adomavicius and YoungOk Kwon. 2012.  Improving aggregate recommendation diversity using ranking-based techniques.  _IEEE Trans. Knowl. Data Eng._ 24, 5 (2012), 896–911.
  * Adomavicius and Kwon (2014) Gediminas Adomavicius and YoungOk Kwon. 2014.  Optimization-based approaches for maximizing aggregate recommendation diversity.  _INFORMS J. Comput._ 26, 2 (2014), 351–369.
  * Agrawal et al. (2009) Rakesh Agrawal, Sreenivas Gollapudi, Alan Halverson, and Samuel Ieong. 2009.  Diversifying Search Results. In _WSDM_. 5–14.
  * Amigó et al. (2018) Enrique Amigó, Damiano Spina, and Jorge Carrillo-de Albornoz. 2018\.  An Axiomatic Analysis of Diversity Evaluation Metrics: Introducing the Rank-Biased Utility Metric. In _SIGIR_. 625–634.
  * Antikacioglu et al. (2019) Arda Antikacioglu, Tanvi Bajpai, and R. Ravi. 2019.  A New System-Wide Diversity Measure for Recommendations with Efficient Algorithms.  _SIAM J. Math. Data Sci._ 1, 4 (2019), 759–779.
  * Ashkan et al. (2015) Azin Ashkan, Branislav Kveton, Shlomo Berkovsky, and Zheng Wen. 2015.  Optimal Greedy Diversity for Recommendation. In _IJCAI_. 1742–1748.
  * Birnbaum and Goldman (2009) Benjamin Birnbaum and Kenneth J. Goldman. 2009.  An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs.  _Algorithmica_ 55, 1 (2009), 42–59.
  * Boim et al. (2011) Rubi Boim, Tova Milo, and Slava Novgorodov. 2011.  Diversification and Refinement in Collaborative Filtering Recommender. In _CIKM_. 739–744.
  * Borodin et al. (2012) Allan Borodin, Hyun Chul Lee, and Yuli Ye. 2012.  Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates. In _PODS_. 155–166.
  * Borodin and Rains (2005) Alexei Borodin and Eric M. Rains. 2005.  Eynard-Mehta theorem, Schur process, and their Pfaffian analogs.  _J. Stat. Phys._ 121, 3–4 (2005), 291–317.
  * Carbonell and Goldstein (1998) Jaime Carbonell and Jade Goldstein. 1998.  The Use of MMR, Diversity-Based Reranking for Reordering Documents and Producing Summaries. In _SIGIR_. 335–336.
  * Castells et al. (2015) Pablo Castells, Neil J. Hurley, and Saul Vargas. 2015\.  Novelty and Diversity in Recommender Systems.  In _Recommender Systems Handbook_. Springer, 881–918.
  * Cheng et al. (2017) Peizhe Cheng, Shuaiqiang Wang, Jun Ma, Jiankai Sun, and Hui Xiong. 2017.  Learning to Recommend Accurate and Diverse Items. In _WWW_. 183–192.
  * Clarke et al. (2008) Charles L. A. Clarke, Maheedhar Kolla, Gordon V. Cormack, Olga Vechtomova, Azin Ashkan, Stefan Büttcher, and Ian MacKinnon. 2008.  Novelty and Diversity in Information Retrieval Evaluation. In _SIGIR_. 659–666.
  * Drosou et al. (2017) Marina Drosou, H.V. Jagadish, Evaggelia Pitoura, and Julia Stoyanovich. 2017.  Diversity in Big Data: A Review.  _Big Data_ 5, 2 (2017), 73–84.
  * Drosou and Pitoura (2010) Marina Drosou and Evaggelia Pitoura. 2010.  Search Result Diversification.  _SIGMOD Rec._ 39, 1 (2010), 41–47.
  * Ekstrand et al. (2014) Michael D. Ekstrand, F. Maxwell Harper, Martijn C. Willemsen, and Joseph A. Konstan. 2014.  User Perception of Differences in Recommender Algorithms. In _RecSys_. 161–168.
  * Erkut (1990) Erhan Erkut. 1990\.  The discrete $p$-dispersion problem.  _Eur. J. Oper. Res._ 46, 1 (1990), 48–60.
  * Erkut and Neuman (1989) Erhan Erkut and Susan Neuman. 1989.  Analytical models for locating undesirable facilities.  _Eur. J. Oper. Res._ 40, 3 (1989), 275–291.
  * Garreau et al. (2019) Damien Garreau, Wittawat Jitkrittum, and Motonobu Kanagawa. 2019\.  Large sample analysis of the median heuristic.  _CoRR_ abs/1707.07269 (2019).
  * Gollapudi and Sharma (2009) Sreenivas Gollapudi and Aneesh Sharma. 2009.  An Axiomatic Approach for Result Diversification. In _WWW_. 381–390.
  * Gretton et al. (2012) Arthur Gretton, Bharath K. Sriperumbudur, Dino Sejdinovic, Heiko Strathmann, Sivaraman Balakrishnan, Massimiliano Pontil, and Kenji Fukumizu. 2012.  Optimal kernel choice for large-scale two-sample tests. In _NIPS_. 1214–1222.
  * GroupLens (2003) GroupLens. 2003\.  MovieLens 1M Dataset.  Retrieved April, 2022 from https://grouplens.org/datasets/movielens/1m/
  * Harper and Konstan (2015) F. Maxwell Harper and Joseph A. Konstan. 2015.  The MovieLens datasets: History and context.  _ACM Trans. Interact. Intell. Syst._ 5, 4 (2015), 1–19.
  * Hurley and Zhang (2011) Neil Hurley and Mi Zhang. 2011.  Novelty and Diversity in Top-N Recommendation – Analysis and Evaluation.  _ACM Trans. Internet Techn._ 10, 4 (2011), 14:1–14:30.
  * Kaminskas and Bridge (2017) Marius Kaminskas and Derek Bridge. 2017.  Diversity, Serendipity, Novelty, and Coverage: A Survey and Empirical Analysis of Beyond-Accuracy Objectives in Recommender Systems.  _ACM Trans. Interact. Intell. Syst._ 7, 1 (2017), 2:1–2:42.
  * Kuby (1987) Michael J. Kuby. 1987\.  Programming Models for Facility Dispersion: The $p$-Dispersion and Maxisum Dispersion Problems.  _Geographical Analysis_ 19, 4 (1987), 315–329.
  * Kulesza and Taskar (2012) Alex Kulesza and Ben Taskar. 2012.  Determinantal Point Processes for Machine Learning.  _Found. Trends Mach. Learn._ 5, 2–3 (2012), 123–286.
  * Kunaver and Požrl (2017) Matevž Kunaver and Tomaž Požrl. 2017.  Diversity in recommender systems – A survey.  _Knowl. Based Syst._ 123 (2017), 154–162.
  * Macchi (1975) Odile Macchi. 1975\.  The coincidence approach to stochastic point processes.  _Adv. Appl. Probab._ 7, 1 (1975), 83–122.
  * McNee et al. (2006) Sean M. McNee, John Riedl, and Joseph A. Konstan. 2006\.  Being Accurate is Not Enough: How Accuracy Metrics Have Hurt Recommender Systems. In _SIGCHI_. 1097–1101.
  * Ni (2018) Jianmo Ni. 2018\.  Amazon review data.  Retrieved April, 2022 from https://nijianmo.github.io/amazon/
  * Ni et al. (2019) Jianmo Ni, Jiacheng Li, and Julian McAuley. 2019.  Justifying Recommendations using Distantly-Labeled Reviews and Fine-Grained Aspects. In _EMNLP_. 188–197.
  * Parapar and Radlinski (2021) Javier Parapar and Filip Radlinski. 2021.  Towards Unified Metrics for Accuracy and Diversity for Recommender Systems. In _RecSys_. 75–84.
  * Phillips and Venkatasubramanian (2011) Jeff M. Phillips and Suresh Venkatasubramanian. 2011\.  A Gentle Introduction to the Kernel Distance.  _CoRR_ abs/1103.1625 (2011).
  * Qin and Zhu (2013) Lijing Qin and Xiaoyan Zhu. 2013.  Promoting Diversity in Recommendation by Entropy Regularizer. In _IJCAI_. 2698–2704.
  * Ravi et al. (1994) S. S. Ravi, Daniel J. Rosenkrantz, and Giri Kumar Tayi. 1994\.  Heuristic and Special Case Algorithms for Dispersion Problems.  _Oper. Res._ 42, 2 (1994), 299–310.
  * Ribeiro et al. (2012) Marco Túlio Ribeiro, Anísio Lacerda, Adriano Veloso, and Nivio Ziviani. 2012.  Pareto-efficient hybridization for multi-objective recommender systems. In _RecSys_. 19–26.
  * Ribeiro et al. (2014) Marco Túlio Ribeiro, Nivio Ziviani, Edleno Silva De Moura, Itamar Hata, Anísio Lacerda, and Adriano Veloso. 2014.  Multiobjective pareto-efficient approaches for recommender systems.  _ACM Trans. Intell. Syst. Technol._ 5, 4 (2014), 1–20.
  * Sakai and Song (2011) Tetsuya Sakai and Ruihua Song. 2011.  Evaluating Diversified Search Results Using Per-intent Graded Relevance. In _SIGIR_. 1043–1052.
  * Sha et al. (2016) Chaofeng Sha, Xiaowei Wu, and Junyu Niu. 2016.  A framework for recommending relevant and diverse items. In _IJCAI_. 3868–3874.
  * Smyth and McClave (2001) Barry Smyth and Paul McClave. 2001.  Similarity vs. Diversity. In _ICCBR_. 347–361.
  * Steck (2019) Harald Steck. 2019\.  Embarrassingly Shallow Autoencoders for Sparse Data. In _WWW_. 3251–3257.
  * Su et al. (2013) Ruilong Su, Li’Ang Yin, Kailong Chen, and Yong Yu. 2013\.  Set-oriented Personalized Ranking for Diversified Top-N Recommendation. In _RecSys_. 415–418.
  * Tamir (1991) Arie Tamir. 1991\.  Obnoxious Facility Location on Graphs.  _SIAM J. Discret. Math._ 4, 4 (1991), 550–567.
  * Vargas et al. (2014) Saúl Vargas, Linas Baltrunas, Alexandros Karatzoglou, and Pablo Castells. 2014.  Coverage, Redundancy and Size-Awareness in Genre Diversity for Recommender Systems. In _RecSys_. 209–216.
  * Vargas and Castells (2011) Saúl Vargas and Pablo Castells. 2011.  Rank and Relevance in Novelty and Diversity Metrics for Recommender Systems. In _RecSys_. 109–116.
  * Wasilewski and Hurley (2016) Jacek Wasilewski and Neil Hurley. 2016.  Incorporating Diversity in a Learning to Rank Recommender System. In _FLAIRS_. 572–578.
  * Wu et al. (2019) Qiong Wu, Yong Liu, Chunyan Miao, Yin Zhao, Lu Guan, and Haihong Tang. 2019\.  Recent Advances in Diversified Recommendation.  _CoRR_ abs/1905.06589 (2019).
  * Yu et al. (2009) Cong Yu, Laks Lakshmanan, and Sihem Amer-Yahia. 2009.  It Takes Variety to Make a World: Diversification in Recommender Systems. In _EDBT_. 368–378.
  * Zangerle and Bauer (2022) Eva Zangerle and Christine Bauer. 2022.  Evaluating Recommender Systems: Survey and Framework.  _ACM Comput. Surv._ 55, 8 (2022), 1–38.
  * Zhang and Hurley (2008) Mi Zhang and Neil Hurley. 2008.  Avoiding Monotony: Improving the Diversity of Recommendation Lists. In _RecSys_. 123–130.
  * Ziegler et al. (2005) Cai-Nicolas Ziegler, Sean M. McNee, Joseph A. Konstan, and Georg Lausen. 2005.  Improving Recommendation Lists Through Topic Diversification. In _WWW_. 22–32.