{'fraction_non_alphanumeric': 0.03776418117842175, 'fraction_numerical': 0.005558170286200946, 'mean_word_length': 4.235245805467558, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A new system-wide diversity measure for recommendations with efficient algorithms

Recommender systems often operate on item catalogs clustered by genres, and user bases that have natural clusterings into user types by demographic or psychographic attributes. Prior work on system-wide diversity has mainly focused on defining intent-aware metrics among such categories and maximizing relevance of the resulting recommendations, but has not combined the notions of diversity from the two point of views of items and users. In this work, (1) we introduce two new system-wide diversity metrics to simultaneously address the problems of diversifying the categories of items that each user sees, diversifying the types of users that each item is shown, and maintaining high recommendation quality. We model this as a subgraph selection problem on the bipartite graph of candidate recommendations between users and items. (2) In the case of disjoint item categories and user types, we show that the resulting problems can be solved exactly in polynomial time, by a reduction to a minimum cost flow problem. (3) In the case of non-disjoint categories and user types, we prove NP-completeness of the objective and present efficient approximation algorithms using the submodularity of the objective. (4) Finally, we validate the effectiveness of our algorithms on the MovieLens-1m and Netflix datasets, and show that algorithms designed for our objective also perform well on sales diversity metrics, and even some intent-aware diversity metrics. Our experimental results justify the validity of our new composite diversity metrics.

Often, such recommendation systems operate on item catalogs and user bases that have natural clusterings of item categories and user types. This single-minded focus on relevance fails to incorporate requirements of diversity of the recommendations among the item categories and user types. In this paper, we build on earlier targeted approaches for increasing diversity and propose a new model to achieve a holistic trade-off between user-and itemlevel diversity that also promotes system-level diversity. Our problem is motivated by three different considerations in incorporating such diversity in the design of recommender systems.
First, there is a need for diversity in a user's recommendation lists in terms of both items and categories to encourage serendipity [25] as well as to improve user satisfaction [18].
The second consideration we look at is item-level diversity; that is, we wish to show each item to a diverse set of users. Item-level diversity allows for a more holistic dissemination of items to users. User-level diversity fails to consider item-level diversity, since assigning recommendations based on user satisfaction would still only show items to users who fall within their traditional``audience."" This would result in bad item-level diversity but could still give a high user-level diversity if recommendations are diverse enough.
Finally, our third consideration is system-level diversity, which involves aggregating the recommendations made to all users and studying the resulting distribution of recommendations. The platform running the recommender system often has concerns other than pure user satisfaction or item-level diversity. Examples of such concerns include achieving good coverage of different categories in the item catalog and avoiding the perpetuation of biases across the system, such as popularity bias or filter-bubbles among demographic or psychographic clusters of users.
Typically, all three of these considerations are studied under the same``diversity"" umbrella. However, systems that optimize for user-or item-level diversity do not necessarily score well in system-level diversity, motivating the need for a new objective that combines all of these considerations.
One common problem with deliberately increasing the diversity of recommendation systems is that they can change user behavior, which then changes future estimates of relevance, and hence eventually leads to polarization. We do not address this meta concern in any detail, so our targeted approach will also suffer from the same problem. Nevertheless, targeting holistic diversity is a first step in this direction. The ensuing changes will not necessarily be biased toward either changing only user behavior or clustering values of item relevances but will be some mixture of the two.
2. Related work and contributions. First, we survey previous work on category-aware metrics for diversification, and then survey work on sales diversity measures that are systemwide measures of diversification.
2.1. Category-aware metrics. Previous work used category information in defining metrics for measuring the diversity contained in user lists. In our work, we focus on three, each of which informs one of the baseline algorithms we compare against in our experimental section.
Intralist Distance (ILD). We define a recommendation set's intralist distance as the average pairwise distance among items [7]. This is used to measure the diversity of an individual user's recommendations and quantifies user novelty. The distance dist(v k , v j ) between items we consider is measured using the cosine similarity between the items' category membership vectors. Given a list L of recommendations, defined by item lists of length c u for user u, the intralist distance is defined as follows (we use L to denote the left-hand side of the bipartite graph representation representing the users, and N (u i ) to represent the neighbors of user u i , which are items in the right-hand side recommended to her): Maximizing this objective enforces items in the recommendation list of a user to be dissimilar, but ILD does not influence the resulting distribution of categories in the resulting list. Furthermore, overrepresentation of certain categories is not explicitly punished by this metric. The MMR method [7] approximately optimizes the ILD metric by greedily growing a recommendation list S. The next item added to the recommendation list is the one chosen to maximize the quantity \lambda rel(u where \lambda is a trade-off parameter between 0 and 1, and rel(u i , v k ) represents the relevance score of item v k to user u i .
Intent-Aware Expected Reciprocal Rank (ERR-IA). The ERR-IA metric is the intent-aware version of the Expected Reciprocal Rank metric introduced by Chapelle et al. [9]. ERR-IA considers the sum of each item category's weighted marginal relevance. To do this, we consider the quantity p(R a ), which is the probability that the desired recommendation set's target category is R a . Chapelle et al. [9] formally define ERR-IA for some u's given recommendation set N (u i ) = \{ v j \} c i j=1 as follows (again, rel(v k ) denotes the relevance of item v k for this user): (1 -rel(v \ell )).
ERR-IA is a personalized metric and aims for good coverage of relevant categories in the recommendation list. However, it does not explicitly penalize the overrepresentation of a particular category provided that it is well-covered. This metric is optimized by the xQuAD reranking strategy [23]. Similarly to the MMR method, xQuAD greedily optimizes for its metric by greedily picking items which maximize the marginal change in the ERR-IA metric plus a relevance term.
Binomial Diversity (BD). This diversity measure is due to Vargas et al. [27]; we omit the complete description of this metric due to its intricacy. Roughly speaking, the authors use a binomial distribution to model the coverage and redundancy of the categories based on the items included in the recommendation list. Binomial diversity punishes both the underrepresentation and overrepresentation of a given category in a user's list and strives for a balance between coverage and nonredundancy. It can be optimized for in the same way that xQuAD optimizes for the ERR-IA metric, and a thorough experimental evaluation of this method is carried out in [27]. However, due to the complexity of the metric, no explicit guarantees can be given for the performance of the algorithm.

Sales diversity.
In addition to adding diversity to a single user's recommendation list, we are also interested in surfacing content for increased feedback from the users. Since it is impossible for the users to give feedback on items that are not surfaced adequately by the system, we measure our algorithms by two sales diversity measures. The first of these metrics is aggregate diversity, which counts the number of items that are shown to at least one user [3,12,2,4]. Our thresholded item diversity objective can be thought of as a refinement of aggregate diversity, where each item needs to be recommended to multiple users of different types instead of just once to any user in the system. The second sales diversity measure we employ in our experiments is the Gini index, which is also widely employed in the recommender system community [24,12,15,21,8]. The category-aware metrics surveyed above try to solve the filter-bubble problem for the users, while the type information can be used to solve the same problem for the business running the recommender system. In our work, we incorporate aggregate information symmetrically from both item-category and user-type information in our metrics to address this aspect.
2.3. Graph-theoretic approaches for recommender diversity. The first paper to use a subgraph selection model for maximizing aggregate diversity was [3], where the authors reduced the problem to bipartite matching. Other recent papers [6,5] have refined the notion of using subgraph selection by formulating more involved diversity metrics, such as redundant coverage of items, by minimizing the discrepancy from a target degree distribution on the items, and by solving for them using network flow and greedy techniques. Our paper follows this recent line of work.

Submodularity and NP-completeness.
The problem of maximizing a submodular set function has been extensively analyzed in the last 40 years, starting with Nemhauser, Wolsey, and Fisher [19]. Many of the problems we pose reduce to maximizing such a function, which is NP-hard even when the function is monotone increasing. Nonetheless, the problem can be approximated using the greedy algorithm, which gives a (1 - 1/e)-approximation in the simplest case. Moreover, the constraint of choosing a subset of a fixed size, which corresponds to a uniform matroid constraint, can be replaced by any other matroid constraint without affecting the approximation ratio [1]. Since the coverage-type objectives we define in this paper are submodular, and our main type of constraint forms a partition matroid, we make extensive use of results in this area. Other researchers considered the use of submodular functions in diversifying recommendations but did so only over the set of a single user's recommendation set [14,17,22].

Summary of contributions.
1. We introduce two new metrics for recommendation diversity that we call thresholded item diversity (T IDiv) and thresholded user diversity (T U Div) and that consider the distribution of user types among an item's recommended user set and the distribution of item categories in a user's recommendation item set, respectively. The objective of T U Div is similar to that of other category-aware diversity metrics, but T IDiv is unique in its consideration of diversity among an item's recommendees. T IDiv can be thought of as a sales diversity metric, and it explicitly addresses the need for a business to collect feedback from different types of users.
2. In the case of disjoint types and categories, we model the problem of maximizing type diversity across all items and category diversity across all users as a subgraph selection problem. We reduce the resulting problem to a minimum cost flow problem and obtain exact polynomial time algorithms (Theorem 3.5 in section 3). 3. We address the case of nondisjoint types and categories in section 4, where we prove that the problem of maximizing the same objectives mentioned above is NP-complete (Theorem 4.1). While this rules out an exact polynomial time solution, we obtain a (1 -1/e)-approximation using the submodularity of our objectives. We also show how to modify the algorithm to run in nearly linear time in the number of candidate recommendations (Theorem 4.6), making it very efficient. 4. We conduct experiments using the MovieLens dataset that considers both disjoint and overlapping item categories. Our experimental setup is described in section 5, and the results are presented in section 6. We show that despite being flow based, our algorithms for the disjoint case can easily handle problems involving millions of candidate edges. We also show that the greedy algorithm we describe is competitive in efficiency with the reranking approaches we compare against (subsection 6.1) and competitive with our optimal flow based approach when used with disjoint categories and types (subsection 6.2). Our algorithms perform better than the baselines across the board on sales diversity metrics and obtain good values for the other intent-aware metrics despite only optimizing for them by proxy.

Disjoint types and categories.
We model the problem of making recommendations as a subgraph selection problem on a bipartite graph G = (L \cup R, E), where the partition L represents a set of users and partition R represents a set of items. For each user u i , we have a space constraint c i , which is due to display space limitations on a given web page. For each edge (u i , v j ) between user u i and item v j in G, we are also given a real-valued relevance rel(u i , v j ) that is typically an actual rating or a predicted rating from a CF system. Often, the graph G available for selection of recommendations is chosen by using a CF system's relevance scores and only retaining edges that are higher than a minimum threshold relevance or quality value. In this section, we model the case when the subgroups of users and items are disjoint.
We define a collection of subsets \scrL = \{ L 1 , L 2 , . . . , L n \} on the user set L that represent different types of users and are mutually disjoint. Similarly, we define a collection of subsets \scrR = \{ R 1 , R 2 , . . . , R m \} on the item catalog which partition R to represent different categories or genres of items. This means there exist functions type : L \rightar \scrL , which maps users to their designated type, and cat : R \rightar \scrR , which maps items to their corresponding category. The edges between users and items in G represent possible recommendations that can be made. We wish to output a subgraph H of recommendations, where each user u i has c i recommendations. See Figure 1.
) denote the number of neighbors user u i has in v j 's category, and let \delta H j (type(u i )) denote the number of neighbors v j has in u i 's type in H. In order to achieve a diverse set of recommendations, we would like each user to see a large number of categories, while also showing each item to a large number of user types. To define a diversity metric that takes both of these considerations into account, we consider assigning the following weight to Input: A relevance-weighted bipartite graph G(L, R, E), a vector of display constraints \{ c i \} l i=1 , a collection of user types \scrL , a collection of item categories \scrR , real-valued parameters \beta , \mu . Output: A subgraph H \subsete G, of maximum degree c i at each node u i \in L, and maximizing the objective Div \beta ,\mu (H) + rel(H). each edge, where \beta and \mu are real-valued parameters: .
A weighting like this is natural, since we are assigning less weight to recommendations that are not novel for either the user type or the item category that this recommendation serves. For instance, a recommendation edge that gives the user the only item from a category, and gives the item the only user from a type, will have a maximum weight of \beta + \mu . We can now define the diversity of a solution subgraph H Div \beta ,\mu (H) = \sum and subsequently maximize this objective for a highly diverse set of recommendations.
Proposition 3.1. By the definition above, we have Div \beta ,\mu (H) = \beta \sum Proof. We can think of each edge weight as a user contributing a fractional value towards the category the user is hitting as well as an item contributing a fractional value towards the user type that hits the item. For example, if a user u i has four edges to some category, the value of each \beta \delta H i (cat(v j )) for every item v in that category that u is connected to is \beta 4 . If some item v j has three edges coming from the same user type, the value of \mu \delta H j (type(u i )) for each user that v j is connected to is \mu 3 . This means that Div(H) gets a value of \beta for every category that a user hits, and gets a value of \mu for every user type that an item hits: We can isolate both terms of this expression as their own objectives, which may be formalized as follows: Here, U serDiv(H) will give us a reward proportional to the number of categories hit for each user, and ItemDiv(H) will give us a reward proportional to the number of user types hit for each item.
Ignoring type information, we first show that U serDiv(H) can be optimized in polynomial time, since this construction is simpler to formulate and solve in practice. Proof. For each u i \in L, we set supplies of c i and a demand of \sum u i \in L c i for a newly created sink node t. For each user u i and category R a such that \exists v j \in R a such that u i v j \in G, we create nodes n i,a and n \prime i,a . We will create an arc of capacity 1 and cost - 1 between every u i and n \prime i,a . We will also add arcs of capacity 1 and cost 0 between every n \prime i,a and n i,a , and add arcs of unbounded capacity and cost 0 between u i and n i,a . For each edge u i v j in G where v j \in R a , we create an arc of capacity 1 and cost 0 between n i,a and v j . Finally, from each v j \in R, we make an arc of unbounded capacity and cost 0 to the sink node t.
We let the solution subgraph H be the subgraph of G formed by using edges u i v j for all arcs of the form (n i,a ,v j ) used in the flow. Each node now gets to take one recommendation in each new category, for a cost of - 1. Therefore, the cost of a flow defined by H is -\sum Minimizing this quantity is the same as maximizing U serDiv(H), which proves the result. Proposition 3.3. If every user is his/her own type, then, subject to display constraints, Div \beta ,\mu (H) \propto U serDiv(H), and Div \beta ,\mu (H) can be maximized exactly in polynomial time.
Proof. If every user is his/her own type, then the quantity | a : L a \cap N (v j ) \not = \emptyse | simply counts the number of edges incident on an item v j . Therefore, we obtain Div \beta ,\mu (H) = \beta \sum Since the quantity on the right is constant, the result follows from Theorem 3.2.
Finally, we prove the theorem in the most general case by combining the objectives U serDiv(H) and ItemDiv(H). In fact, this is possible while incorporating rating relevance into the objective. In particular, let rel(u i , v j ) denote the relevance of item v j to user u i . Then the relevance based quality of the entire recommender system can be computed as We can now state the main result of this section. Theorem 3.4. The MAX-Div \beta ,\mu problem can be reduced to a minimum cost flow problem if both user types and item categories are disjoint, i.e., R a \cap R b = \emptyse and L a \cap L b = \emptyse for all a, b.
We omit the proof in favor of presenting a more general result in Theorem 3.5.
3.2. Diversity thresholds. While increasing user and item diversity is important, one downfall of our method is that it fails to take into account that the relevance of each category to a user may be different. It may not be beneficial for our recommender to show a user items from every possible category, since that user may not be interested in some of those categories. The same can be said for the item: item diversity may increase an item's popularity and help it collect feedback; however, an item should be shown to users in its target audience more than users outside its target audience.
To fix this and help guide our algorithm in selecting more relevant recommendations for each user and item, we propose setting diversity thresholds for each user-category and itemtype pair. For categories that the user is interested in, we can increase this threshold, while we set it to zero for those that the user is not interested in. Let \rho i (R a ) be user u i 's threshold for recommendations made to items in category R a , and let \lambda j (L b ) be an item v j 's threshold for recommendations made from users of type L b . We now define two updated objectives that take these thresholds into account: Notice that relative to U serDiv, for a user u i we are simply increasing the diversity gain from seeing new items from a category R a up to a threshold value of \rho i (R a ). If we set all the \rho and \lambda values to 1 in the above expressions, we recover U serDiv and ItemDiv.
We can again consider these two objectives together to form a single objective that will maximize the thresholded diversity of a solution subgraph H, where \beta and \mu are real-valued parameters: T Div \beta ,\mu (H) = \beta \cdot T U Div(H) + \mu \cdot T IDiv(H).
The main result of this section is that in the case where user types and item categories are disjoint, T Div(H) can still be optimized in polynomial time.
Theorem 3.5. The MAX-T Div \beta ,\mu problem (see Figure 2) can be reduced to a minimum cost network flow problem if both user types and item categories are disjoint, i.e., R a \cap R b = \emptyse and L a \cap L b = \emptyse for all a, b.
Proof. A diagram of the construction can be found in Figure 3. Our network will have nodes for all users u i \in L and items v j \in R of G(L \cup R, E), and a sink node t. The supply for each user u i will be its corresponding space constraint c i . For every category R a that a Input: A weighted bipartite graph G(L, R, E), a vector of display constraints \{ c i \} l i=1 , a collection of user types \scrL , a collection of item categories \scrR , user-category thresholds \{ \rho i (R a )\} i,a , item-type thresholds \{ \lambda j (L b )\} j,b , real-valued parameters \beta , \mu . Output: A subgraph H \subsete G, of maximum degree c i at each node u i \in L, and maximizing the objective T Div \beta ,\mu (H) + rel(H). user u i 's recommendations hit, we will create two nodes n i,a and n \prime i,a . Let there be an arc of capacity \rho i (R a ) and cost - \beta between u i and n \prime i,a , and an arc with capacity \rho i (R a ) and cost 0 between n \prime i,a and n i,a . There will also be an arc with unbounded capacity and cost 0 between u i and n i,a . Similarly, for an item v j , we will create two nodes, m j,b and m \prime j,b , for each user type L b that its incoming edges are from. Let there be an arc of capacity \lambda j (L b ) and cost - \mu between m \prime j,b and v j , and an arc of capacity \lambda j (L b ) and cost 0 between m j,b and m \prime j,b . We will also add an arc of unbounded capacity and cost 0 between m j,b and v. For each edge (u i , v j ) \in E, where v j is in category R a and u i is of type L b , we will add an arc with cost - rel(u i , v j ) and capacity 1 between n i,a and m j,b . Finally, there will be an arc from every item v i to the sink t with unbounded capacity and cost 0.
We let the solution subgraph H be the subgraph of G formed by using edges (u i , v j ) for all arcs of the form (n i,a ,m j,b ) used in the flow. The cost of the flow induced by H will therefore be - \beta \sum since we may use the - \beta cost arc for each user-category pair, and may use the - \mu cost arc item-type pair until they reach capacity. This quantity is simply - \beta T U Div(H) -\mu T IDiv(H) -rel(H) = - T Div \beta ,\mu (H) -rel(H).
Our results about disjoint categories and types are useful in applications, such as news recommendations, where users are split into natural categories according to their political alignment, and news articles and their publishers are split according to the same categorization. However, these results can be applied without any modification to other domains, such as retail, where the products (items) are split into natural retail categories according to product ontologies, and where the users are split according to natural, mutually exclusive demographic types, such as gender, age, and income bracket. However, the more general case, which we turn to next, is when categories and items are not necessarily disjoint.

4.
Overlapping types and categories. Although cases involving disjoint user types and categories are solvable in polynomial time, in actual practice, categories of items are not necessarily disjoint, and users may be assigned to more than one user type (see Figure 4). We continue to use the notation from section 3, but now user types \scrL = \{ L 1 , L 2 , . . . , L n \} on the user set L, as well as item categories \scrR = \{ R 1 , R 2 , . . . , R m \} on the catalog R, may overlap. When item categories and user types are nondisjoint, maximizing T Div(H) is NP-hard, which can be seen in the following theorem (via a simple reduction from max-coverage).  Finding an optimal solution to maximize T Div \beta ,\mu (H) with nondisjoint categories and types is NP-hard.
Proof. We fix \beta = \mu = 1, since proving the NP-hardness of a special case is sufficient. We show that optimizing just T U Div \beta ,\mu (H) with a single user is NP-hard with the following reduction from the Max-Cover problem, a well known NP-hard problem: Given a set of elements \{ 1, 2, 3, ..., n\} , a collection of m sets \scrS , and an integer k, we want to find the largest number of elements covered by at most k sets.
We construct a bipartite graph G(L \cup R, E), where | L| = 1 and | R| = m, with the items representing sets. The vertex u \in L has an out-degree of m, one for each vertex in R. We then create subsets R 1 , R 2 , R 3 , . . . , R n \subsete R, with one such subset corresponding to each element e i in \{ 1, 2, 3, . . . , n\} : the subset of vertices in R i correspond to the sets in \scrS that contain the element e i . We also set \{ \rho 1 (R i )\} n i=1 = 1. We let c 1 = k. An optimal solution for T U Div(H) would give an optimal solution to Max-Cover, since finding the maximum number of categories hit with k edges out of L would find the maximum number of elements we can cover with k sets.
Since finding the optimal solution to T U Div \beta ,\mu (H) is NP-hard, and T U Div(H) is a special case of T Div \beta ,\mu (H), we have shown that optimizing U serDiv(H) will also be NP-hard, thus proving the desired result.
Since we are not able to maximize T Div \beta ,\mu (H) optimally, we can make use of the fact that T Div \beta ,\mu (H) is both monotone and submodular, which will allow us to apply a greedy algorithm which will yield a (1 -1/e)-approximation ratio.

Proposition 4.2. T U Div(H) is submodular.
Proof. Let X and Y be two sets of edges such that X \subsete Y, and let e be an edge not in X or Y . Consider the quantity T U Div(X \cup \{ e\} ) -T U Div(X). Observe that this is the number of categories R a that e will saturate (not including categories that have already reached their threshold). This will be at least as much as the number of categories e saturates in Y , since Y could contain edges that have already saturated categories that e would saturate. It follows that T U Div(X \cup \{ e\} ) -T U Div(X) \geq T U Div(Y \cup \{ e\} ) -T U Div(Y ). This satisfies the``diminishing returns"" property of submodular functions. Therefore T U Div(H) is submodular.
We get the following from a symmetric argument.   The monotonicity and the submodularity of the objective now allow us to write the greedy algorithm given in Algorithm 4.1.
Stated in its current form, the greedy algorithm takes O(| E| 2 ) time to run. However, it is possible to speed it up significantly by using better data structures.
Theorem 4.6. Let R 1 , . . . , R k be the set of overlapping categories, and let L 1 , . . . , L p be the set of overlapping types for a T Div maximization problem. Then the greedy algorithm can be implemented to run in time, O((E + \sum k a=1 R a + \sum p b=1 L b ) log | E| ). Proof. Let u \in L and v \in R, and let u, v \in G be a candidate recommendation. The category contribution of this edge to a partial solution H is the number of categories R i that v belongs to, for which \rho (R i ) < \delta H L (R i ) is satisfied. Similarly, the type contribution of this edge is the number of types L j that u belongs to, for which \lambda (L j ) < \delta H R (L j ). While constructing the solution, both of these quantities can only decrease. Furthermore, we are only ever interested in the node with the highest marginal contribution. Therefore, we can keep track of the potential contribution of each edge in a max-heap. Initially, the priority of each edge is set to be the number of categories and number types it covers. Each time an edge meets a category target, we decrease the priority of every unused edge incident on that category by \beta . Similarly, when a user-type target is satisfied, we decrease the priority of every unused edge incident on that type by \mu . Both operations take logarithmic time using a heap which supports the decrease-key operation. This operation is performed at most once for each type and category.
This means that we are maintaining a max-heap with | E| elements, removing the maximal element | E| times, and decreasing the key of some edge by at most \sum k a=1 R a + \sum p b=1 L b times. Both of these operations can be done in O(log | E| ) time, which gives us the desired runtime.

Datasets. Category data:
We use ratings data as well as type and category data from the MovieLens 1M dataset, and use additional category data from the Internet Movie Database (IMDb). For disjoint user types in the MovieLens dataset, we use three demographic data points included in the data: age group (six different values), gender (two different values), and occupation (19 different values), each of which partitions the user set.
Supergraph generation: We used the MovieLens 1M [13] rating dataset to generate the graph that we fed to our algorithms. (The dataset can be downloaded from http://grouplens. org/datasets/movielens/1m/.) We preprocessed the dataset to ensure that every user and every item has an adequate amount of data on which to base predictions. This postprocessing left the MovieLens 1M data with 5800 users and 3600 items. The use of this dataset is standard in the recommender systems literature. In this work, we consider the rating data to be triples of the form (user, item, rating), and we discard any extra information.
Each dataset was processed in two different ways: once for experiments involving disjoint categories, and once for experiments involving overlapping categories. In each case, the full dataset was filtered for items for which the category information was known. Each of these were then split five ways into holdout test sets and training sets. Only users with more than 50 ratings were considered for inclusion in the test, and we denote this set of users by L T \subsete L. The training sets were then fed into a matrix factorization algorithm due to Hu, Koren, and Volinsky [16] with 50 latent factors. We set the input confidence value parameter \alpha in their method to the value of 40, as recommended by the authors, and performed a grid search for the best regularization parameter \lambda using fivefold cross validation. Using the resulting user and item factor matrices, for each user we predicted the ratings of all the items for which the user did not provide feedback in the training test. Among these predicted ratings, we retained the 250 highest rated items along with their predicted ratings to feed into our algorithms.

Quality evaluation.
We measure the effectiveness of our and other authors' algorithms along several orthogonal dimensions. For relevance, we report precision values, i.e., the fraction of items in the recommendation set that match items given in the test set. Formally, if we denote the set of recommendations given to a user in subgraph H as N (u i ) and the set of relevant held-out items for the user as T (u i ), we define precision as follows: In this paper, a held-out item is considered to be relevant to a user in our evaluation if its assigned rating was 3 or higher. We note, however, that this notion of precision is conditioned on the inherent diversity already represented by the ratings in the MovieLens 1M database, and hence may not be ideal. Therefore, in addition to relevance based metrics, we also report two sales diversity metrics: aggregate diversity and the Gini index.
Aggregate diversity is simply the fraction of items in the catalog which have been recommended to at least one user, and it measures coverage. The Gini index measures how inequitable the recommendation distribution is. More concretely, if the degree distribution of the items is given as a sorted list \{ d i \} r i=1 , then the Gini index is defined as follows: Finally, we report the objectives for which our methods explicitly optimize. These are ERR-IA for the xQuAD reranker, ILD for the MMR reranker, and Binomial Diversity for the Binomial Diversity reranker. Among these, only the Binomial Diversity reranking method takes a parameter \alpha , which corresponds to a personalization parameter. Vargas et al. use the value \alpha = 0.5 in their experimental evaluation [27], and we also use this setting. We measure each of the above-mentioned metrics as well as our own T U Div and T IDiv as ours are measured among only the relevant items in the test set.
As mentioned in subsection 3.2, for the T U Div and T IDiv metrics, we set the thresholds using the training data. In particular, for the case of disjoint categories, we count the number of times each category appears in a user's training set, normalize these values to sum to the display constraint, and round to integer values. For the case of overlapping categories, we perform the same operation but normalize the thresholds to sum to the display constraint times the average number of categories for an item in the training set. In the case of disjoint types, we again set the type thresholds proportional to the distribution of types found in the training data, but we normalize the distribution to sum to 20\% of the average number of recommendations an item would have received if every item were equally promoted by the recommender system. This allows the measure to promote sales diversity among items while respecting its interaction history with the users.
Note that setting the thresholds using the proportions in the training data inherently biases the distribution to which we are targeting the final diversity, and makes it match the distribution in the overall training set. Despite this, we chose these thresholds because they match the precision measure that we use to evaluate the effectiveness of our methods. Note that these thresholds can also be set by a designer who prefers to move the proportions of different categories for different users in a different direction than is found in the training data (and symmetrically for the items), but it would be difficult to evaluate the effectiveness of the resulting lists against other methods.
In Tables 1--6, we abbreviate the names of these metrics as P for Precision, A for aggregate diversity, G for the Gini index, BD for Binomial Diversity, and ILD for intralist distance. The number next to each metric denotes the cutoff at which it was evaluated.

Baselines.
We compare our method against three baselines methods: the Binomial Diversity reranker due to Vargas et al. [27], the MMR reranker due to Carbonell and Goldstein [7], and the xQuAD algorithm due to Santos [23]. Each method takes a parameter \lambda \in [0, 1], which trades off relevance with the metric which is being optimized. For each of these methods, we perform a grid search for the best trade-off parameter, and we report all the measurements for the setting which produced the best results for the method's corresponding metric. Since our algorithms have two trade-off parameters \mu and \beta in the objective rel(H) + T Div \beta ,\mu corresponding to two different metrics, we perform a grid search along both dimensions and report the two solutions which maximize T IDiv and T U Div, respectively. Additionally, in the rows labeled``TOP"" we report the same metrics for the undiversified recommendation lists provided by the matrix factorization method.

Software.
For the matrix factorization based recommender that we trained, we used the implementation of Hu's matrix factorization method found in RankSys (see Vargas) [26]. The baseline methods that we compare against are also implemented in the same library. Our methods and metrics were implemented so as to be compatible with the same library. Additionally, we used a minimum cost network flow optimizer written by Bertolini and Frangioni (see Frangioni and Sanchez) [11]. The code that we used for our experiments can be found in our repository at https://github.com/antikacioglu/salesdiversity/tree/master/Category.

Experiments.
In this section we report our findings on diversifying recommendations in MovieLens-derived recommendation problems. Our findings can be summarized as follows: 1. In the setting of overlapping item categories, the greedy algorithm leveraging the submodularity of the T Div objective obtains significant gains in the T IDiv and T U Div recommendation diversity metrics. Our algorithm preserves or improves the accuracy of the baseline recommender system, while also increasing sales diversity metrics. 2. In the setting of disjoint item categories, we show that the flow based algorithm obtains solutions which have higher predictive accuracy and higher sales diversity measurements. However, the differences are small enough to enable the greedy algorithm to make a suitable replacement for the more expensive, flow based optimization technique. 3. The greedy algorithm is faster than competing diversification techniques, making it suitable for large-scale recommendation tasks, provided that the heap used in its implementation can fit in memory.
6.1. Experiments on overlapping categories. First, we present our experiments for overlapping categories based on the artistic genre information for the movies, and for user types based on age group, occupation, and gender, respectively. Our results are summarized in Tables 1, 2, and 3. The relative performance of the methods that we tested for artistic genre categories of the movies and genders of the users can be seen in Figure 5. As expected each diversification method is best at maximizing its own objectives. In the case of our methods, this is true for both T IDiv and T U Div. Among the metrics we tested, both our greedy algorithm and the xQuAD algorithms made minor improvements to the precision of the recommendation lists, while under Binomial Diversity and MMR, precision values slightly deteriorated. However, these differences are minor, and each algorithm was able to find a good trade-off between relevance and diversity under suitable parameter settings.
Among the intent-aware metrics we have tested, our algorithms provide a very good proxy for Binomial Diversity but perform poorly on the IntraList Distance and ERR-IA metrics. This can be explained by the fact that Binomial Diversity, unlike the ERR-IA and ILD metrics, explicitly penalizes redundancy. Our metric T U Div is similar to Binomial Diversity in the sense that it sets thresholds which implicitly penalize overredundancy by taking away the reward for hitting new categories. However, the converse is not true, and the Binomial Diversity reranking method achieves poor values for both the T IDiv and T U Div metrics.
Among the methods we tested, the best proxy for our T U Div metric was provided by the xQuAD approach, and none of the algorithms we tested provided a good proxy for T IDiv. While this deficiency can be excused, as none of these algorithms takes as input the various user-type groupings we provide to our diversifiers, each of the other baselines also regressed or did not significantly change the sales diversity metrics, such as the aggregate diversity. Table 1 MovieLens diversifications for artistic genre based categories and age group based types. The best value in each metric is set in bold.
Method P@20 ERR-IA@20 ILD@20 BD@20 TUDiv@20 TIDiv@20 A@20 G@20 This validates our hypothesis that T IDiv is best thought of as a sales diversity measure, and that being category-aware in the user lists is not enough for a reranking algorithm to produce diverse results for items.
6.2. Experiments on disjoint categories. In this section we present the diversification results for disjoint item categories derived from movie studio information. These results are intended to simulate the scenario in which a content aggregator would like to diversify recommendations among different content providers (which are summarized in Tables 4--6). Since we can apply both the greedy algorithm and the flow based algorithm in this case, we report results for both. Our results for the top 10 recommendation diversification tasks are summarized in Figure 6. We note that, once again, every reranker is best at optimizing its own metric, with the exception of the xQuAD, whose objective is actually maximized by the Binomial Diversity reranking method. We also note that the precision based effectiveness of our greedy algorithm is reduced in this setting, while its effectiveness in the sales diversity metrics is amplified.
Our flow based method and greedy algorithm show several notable differences in the experimental evaluation. First, we find that the greedy algorithm actually performs better than the flow based method in our intent-aware metrics T U Div and T IDiv, although our flow based methods produce more accurate recommendation lists. The solution produced by each algorithm creates a different trade-off between the T U Div term of the objective, the T IDiv term of the objective, and the predicted relevance term of the objective. Both optimize Binomial Diversity equally well, while the flow based method increases intralist distance and Table 4 MovieLens diversifications for movie studio based categories and age group based types. The best value in each metric is set in bold.  Table 5 MovieLens diversifications based on movie studio based categories and occupation based types. The best value in each metric is set in bold.  Table 6 MovieLens diversifications based on movie studio categories and gender based types. The best value in each metric is set in bold.  Figure 6. A radial graph showing the relative performance of the reranking methods we tested for MovieLens data with movie studio and age group based diversification.

Table 7
Running time of the five different rerankers on the diversification task in Figure 6.

Method
Greedy aggregate diversity better than the greedy algorithm. The two methods' overall results are similar enough so that as long as precision is not as compelling a concern as intent-aware diversification, the two algorithms can be used interchangeably. This is a significant finding as our flow based algorithms, while more accurate, take more time to run to completion. In particular, our greedy algorithms have runtime proportional to O(| E| log(| E| )), where | E| is the number of candidate edges, while our flow based algorithms have complexity at least O(| E| (| R| +| L| )) and significantly higher overheads. Moreover, greedy is the fastest among the methods we tested, which can be seen in Table 7. 7. Conclusions and future work. We have presented a framework for the implementation of a diversification framework that seeks to increase the exposure of every user to predefined categories of items. The implementation of our framework in the case of disjoint categories of items is completely novel and provides stronger theoretical guarantees on the quality of the solution than the implementation of our framework with overlapping categories. Extending our work to dynamic settings in which the new items or the users arrive and depart over time is a rich avenue for future work.