SAGA: A Submodular Greedy Algorithm For Group Recommendation
Shameem A Puthiya Parambath Nishant Vijayakumar Sanjay Chawla
cs.IR cs.LG stat.ML


Steady state thermodynamics of two qubits strongly coupled to bosonic environments
    Ryoichi Kawai
    December 30, 2023
==================================================================================


In this paper, we propose a unified framework and an algorithm for the problem of group recommendation where a fixed number of items or alternatives can be recommended to a group of users.
The problem of group recommendation arises naturally in many real world contexts, and is closely related to the budgeted social choice problem studied in economics.
We frame the group recommendation problem as choosing a subgraph with the largest group consensus score in a completely connected graph defined over the item affinity matrix.
We propose a fast greedy algorithm with strong theoretical guarantees, and show that the proposed algorithm compares favorably to the state-of-the-art group recommendation algorithms according to commonly used relevance and coverage performance measures on benchmark dataset.




§ INTRODUCTION

Recommender systems can be regarded as a particular instance of a personalized information retrieval system where the explicitly or implicitly learned user profiles/features serve the purpose of a `query' in the traditional IR system.
Recommender systems provide effective information exploration by proposing a set of relevant items/alternatives to users.
Many efficient and scalable algorithms exist for personalized recommender systems, carefully tailored for many desirable properties of the recommendation set like relevance, diversity, coverage etc <cit.>.
In contrast to personalized recommender systems, a group recommender (GR) system has to provide recommendations for a set of users jointly, returning a set of items in consensus with diverse user preferences.
The user interests might be often conflicting in nature.
A number of real world applications can be formulated within the framework of choosing a subset of items from a given item set to appeal to a group of users.
For example, group discount vendors have to choose a set of items that best appeals to the set of diverse users in a given city; similarly flight operators have to choose a set of movies to play in a plane's entertainment system.
The problem is also closely related to the budgeted social choice problem studied in economics <cit.>.

In recommender systems, items are assumed to have intrinsic preference scores for each user, which represent the level of affinity of the user to the item.
We assume the preference scores to be on an ordinal scale, typically in the range of 1-5, with higher values indicating stronger preference.
A simple and straightforward approach to group recommendation is to aggregate the preference scores i.e combine the preference scores of individual group members for an item 
 to form a joint ranking of the items and select the top- items <cit.>.
Most commonly used aggregation functions are (i) average misery; recommending items with highest average preference scores among the group members, (ii) least misery; recommending items that maximize the minimum preference scores among users and (iii) plurarility; recommending items that maximize the number of “highest preference scores” <cit.>.
But such score aggregation strategies completely disregard the user disagreement or the individual user satisfaction for  individual items as discussed in  ().



To get a more balanced recommendation, it is important to consider the disagreements between users of the group for the same item.
Thus the problem can be reformulated as a bi-objective optimization problem where one objective corresponds to the agreement (relevance) of the item to the users and the other objective corresponds to the disagreement between the users for the item.
The general procedure to solve a multi-objective optimization problem is to take the convex combination of the objectives and perform homotopy continuation, also referred as scalarization or weighted-sum approach <cit.>.
Similar to aggregation strategies, scalarization based algorithms assume that preference scores for the test items are available, but in practice one has to run a baseline recommender system as a first step to generate the preference scores.

Inspired by the recent work on personalized diverse recommendations <cit.>, in this paper we propose a general framework for algorithms for group recommendations.
We propose a generic objective function by framing the problem as a relevant group interest coverage in an affinity graph defined over the item features.
The crux of our approach is that the item-item and user-user interactions are captured in a single objective.  
Unlike score aggregation strategies, we do not require the preference scores of the test items to be generated beforehand.
We give two instances of the objective where the GR problem reduces to a submodular function maximization problem.

The `diminishing return' property of submodular functions allows us to trade-off the redundancy and relevance, thus making the recommended set containing relevant items covering a wider spectrum of group interest.
An intuitive graphical representation of the underlining idea behind our approach is given in Figure <ref>.
The figure contains preferences of a group of three users spanning three item classes, users being represented by the blue '+','*' and '×' symbols.
None of the three users have common item classes, but the group covers all the item classes.
Hence the optimal recommendation strategy is to recommend relevant items from the three item clusters.
The red square is the recommendation made by our proposed algorithm, whereas the baseline algorithms recommendations covered only two item clusters (See Section <ref> for details).




The remainder of this paper is structured as follows.
We give a brief overview of group recommendation algorithms in Section <ref>.
Section <ref> describes our framework and relationship to other group recommendation strategies .
We carry out large scale experiments on benchmark data and report the results in Section <ref>.
We conclude the paper in Section <ref>.



§ RELATED WORK


Most of the earlier work on group recommendation is based on a model where the individual group member attributes are aggregated to generate the group recommendation <cit.>.
Based on this model, state of the art algorithms can be further classified as profile aggregation based and score aggregation based.
In the first approach, individual user profiles are aggregated to create a group profile.
The group profile can be seen as a single artificial user capturing the group dynamics, and state of the art personalized recommendation algorithm can be used to produce group recommendations for this artificial user.
In the second approach also, the group recommendation is produced in two steps.
In the first step, preference scores for each individual group member for the test items are generated by running a collaborative filtering algorithm.
The second step involves running a score aggregation algorithm on the preference scores obtained in the first step to generate the group recommendations. 
In one of the earliest work on group recommendation,  () proposed an algorithm where the individual user ratings are generated using nearest neighbor models for collaborative filtering, and employing score aggregation strategies like least misery and average misery to obtain group recommendations.
Similarly, in <cit.>, the authors proposed an algorithm by aggregating the individual user profiles to create a group profile and using neighborhood models to generate recommendations for the newly created group profile.
This algorithm comes under the first approach explained above.
 () gives an overview and use cases of commonly employed scoring strategies in recommender systems.
However, both the score aggregation and profile aggregation approaches fail to attribute for the individual user disagreements for different items <cit.>.

 () advocated that a better group recommendation strategy can be devised by considering the disagreements between the individual users in the group for the same item.
They proposed an algorithm where the recommendation set is obtained by solving a discrete optimization problem.
The objective function is a linear combination of an agreement term and a disagreement term.
It is an instantiation of the scalarization algorithm for the multi-objective optimization problem.
The proposed algorithm requires one to run a baseline personalized recommender system to generate preference scores for every user.
Moreover, many variants of the above discussed scalarization based group recommendation schemes are proposed in domain specific settings and we direct the reader to the survey papers by  () and  (), and the references therein.
One of the difficulties in developing group recommendation algorithms is the lack of proper evaluation strategies.
In  () , the authors propose a methodology for offline evaluation of group recommendation algorithms.
Recent works make use of expensive online evaluation strategies <cit.>

In economics, group recommendation is studied as a special case of the budgeted social choice problem <cit.>.
The budgeted consensus recommendation is often considered as a trade-off between pure personalized recommendation and pure consensus recommendation.
In group recommendation, the budget is specified as a function of the recommendation size, keeping the other cost components constant.
Most of the work on budgeted social choice theory assumes that user preferences for the items are strict, i.e. every user derives benefit from at most one item that has the highest preference score (utility score), and preference scores are often derived using positional scoring rules like Borda count.
 () proposed a greedy algorithm using knapsack heuristics, but it worked very poorly on group recommendation tasks with positional scoring rules.
 () extended the theoretical framework for limited choice models with positional scoring rules using the ordered weighted average (OWA) operators.

Unlike the above mentioned approaches, our approach proceeds in a single step by carrying out preference estimation implicitly and thus avoids running a baseline personalized recommender system to generate the unseen test preference scores.
The trade-off between the agreement and the disagreement components is dealt with by the exact definition of the user saturation function, item saturation function and the affinity functions, instead of explicitly trading-off of both the terms.
Our work is inspired by  () where the authors propose a personalized diverse recommendation algorithm.
Nonetheless, our work differs from theirs significantly.
We introduce group consensus score as a function of the user saturation function and the item saturation function.
The exact notion of user saturation function is motivated by the item saturation function defined in  (), to capture the coverage of an item observed by a user.
Our proposed algorithm is more general and the algorithm proposed in  () is a special case of our approach in that when the group consists of a single user, the item saturation function is a concave function and the user saturation function is the identity function.
By defining the user coverage function to be submodular, we aim to (i) recommend items which are relevant to the majority of the group and (ii) discourage the recommendations to be centered around a few user.



§ GROUP RECOMMENDATION


We are given a set  of n items and a set  of m users.
The set of users forms a set of groups .
The group dynamics can evolve over time, and a user may or may not be a member of a group.
Also, a user can be part of just a single group or multiple groups.
We also assume the existence of an affinity function over the item space h: ×→_+.
Similarly, we assume the existence of an affinity function over the user space c: ×→_+.
We assume that the affinity functions h and c are non-negative.
There is no assumption regarding the symmetricity or transitivity of the affinity functions.
Each user has a preference score (utility score or relevance score) for each of the item denoted using an ordinal number, typically in the range 1-5 with higher value indicating stronger preference.
A user can have same preference score for different items.

Given the item set  and the corresponding item-item affinity matrix , we can view the pair (,) as a complete graph where the edge between nodes i,j ∈ is weighted according to the value _ij.
Given a group ∈, the user-user affinity matrix  and the observed preference scores for the set of users in the group  for the item set ⊂, the item set  defines a subgraph of the complete graph (,).
We can define the group recommendation task as retrieving a subset of  items from the set = ∖ such that it (i) covers most of the observed items and has high preference scores in the set  and (ii) covers a larger spectrum of users in the group .
We introduce group consensus score to capture the above two aspects of the group recommendation.

Formally, we define the group consensus score for a set of items ⊆ with cardinality  with respect to the set  for the given group  as,


    (,,)    = 
    ∑_u ∈ g_u   (∑_l ∈∖{u}_ul∑_i ∈_u r_u^if(∑_j∈_ij))

where g_u:_+ → is the user saturation function,  f:_+ →_+ is the non-negative item saturation function, _u is the set of observed items in  for the user u, and r_u^i is the observed preference score for the item i by user u.
The rationale behind the objective function is to find the items similar to the observed relevant items which appeals for the entire group, as demonstrated by higher value for .
By choosing proper item saturation and user saturation functions, we aim to produce a consensus set of recommendations.

Given a fixed user saturation function g_u and item saturation function f, a set of  items for the group  with the highest group consensus score can be obtained by solving the optimization problem

    _⊆
    ||≤(,,)
    .

Before further discussion into the design details of the saturation functions g_u and f, we describe the generality of the objective function (<ref>).
It can be shown that many well-known group recommendation strategies are special cases of the objective function (<ref>). 



 §.§ Special Cases

For different formulations of the user saturation function g_u, the optimization problem in (<ref>) corresponds to score aggregation strategies currently employed in group recommendation tasks.



  §.§.§ Identity item saturation function

Here, we see that by fixing the item saturation function (f) to be the identity function i.e. f(x) = x and varying the user saturation function g_u gives rise to many score aggregation strategies.
We will also assume that  is the indicator matrix for the given group  i.e. _ij = 1 if i and j are in group  , zero otherwise.


Least Misery: If g_u is set as the constant function min i.e. g_u(x) = min(x), ∀ u ∈, then the optimization problem corresponds to selecting  items which maximize the lowest preference scores on the test set, among all members in the group.
This is equivalent to the least misery aggregation strategy <cit.>.



Most Pleasure:
Similarly, by setting g_u to the max function i.e. g_u(x) = max(x), ∀ u ∈, the optimization problem in (<ref>) becomes the most pleasure scoring strategy <cit.>.
 items that maximize the highest preference scores for the items in the test set, among all members in the group are recommended.

Average Misery:

If g_u is set as the constant function g_u(x) = 1/||, ∀∈, then the optimization problem reduces to the average misery approach, where the items that maximize the average preference scores among all the members in the group are recommended <cit.>.

Plurality:

If g_u is the indicator function such that it takes the value one when the preference score is the highest (ties are broken arbitrary) and zero otherwise, then the optimization problem corresponds to the plurality scheme <cit.>.


Ordered Weighed Average Operators:
If the inner term ∑_i ∈_u r_u^if(∑_j∈_ij) is assumed to be in the sorted order, and for a general g_u: _+ →_+ , the group consensus function corresponds exactly to the ordered weighted average (OWA) operators studied by  ().
In this case, many different functional formulations of g_u will result in different group recommendation strategies like -best OWA, Hurwicz OWA etc (See  () for details).



  §.§.§ Identity user saturation function

Here, we fix the user saturation function (g_u) to be the identity function i.e. g_u(x) = x and vary the item saturation function f.


Diverse Personalized Recommendation:
In case of single user groups ( will be the identity matrix), when the item saturation function is concave, the objective function reduces to the one studied by  () for diverse personalized recommendations.
For other functional forms of f,  we get different personalized recommendation schemes <cit.>.


Time Evolving Group Dynamics:
The individual user preferences are dynamic and it can evolve over time.
User's interest for activities like shopping, watching movies etc, can fade or strengthen over time.
It is important to adjust the parameters of the algorithm to reflect the evolving group dynamics by lowering the significance of the “fading” user and highering the significance of the “strengthening” user.
One way to achieve this is by re-weighting the individual user contribution in a group when recommending new items.
This can be done by defining the user saturation function g_u as g_u(x) = x/t_u, where t_u is the “transportation time” of user u in the given group.
One can define the “transportation time” as a function of user's activity time in the group where a frequent loyal user will have low transportation time whereas occasional user will have high transportation time.



 §.§ Design of Saturation Function

Ideally, we want the recommended set to include relevant yet items that appeals to a larger spectrum of users in the group.  
We design saturation functions such that the  has the “diminishing return” property.
In our settings, the “diminishing return” property ensures that once a relevant item with respect to one (or few) user(s) is added, the marginal gain of adding another relevant item for the same user(s) is less than adding a relevant item with respect to the remaining users.
In particular, the “diminishing return” property of the item saturation function helps to select relevant yet diverse items, whereas the “diminishing return” property of the user saturation function encourages user coverage. 
The “diminishing return” is the characterizing property of submodular functions, and we choose the saturation functions to be such that group consensus score is a submodular function.

We discuss two settings.
In the first settings, we propose a simple extension of the algorithm proposed in  () by choosing g_u to be the identity function.

For any concave function f and the identity function g_u,  is a submodular function (with respect to inclusion in ). If f is monotonic then  is also monotonic.


The proof of Lemma <ref> can be found in  ().
In the second setting, we choose g_u to be a concave function.


For any monotone concave function f and any concave funtion g_u,  is a submodular function (with respect to inclusion in ). If g_u is monotonic then Gscore is a monotonic submodular function.



By Lemma<ref>, ∑_l ∈∖{u}_ul∑_i ∈_u r_u^if(∑_j∈_ij) is a submodular function of .
Let us denote this term as z().
It is sufficient to prove that g(z()) (we omit the subscript for convenience) is a submodular function.
Due to the concavity of g and monotonicity of z (due to the monotonicity of f), ∀_1, _2  such that _1 ⊆_2 ⊆ and ∀ e ∈ such that e ∉_2,

    g(z(_1 ∪ e)) - g(z(_1)) ≥ g(z(_2 ∪ e)) - g(z(_2))

which completes the proof.  



 §.§ Accelerated Greedy Algorithm

For any monotone concave function f and any concave funtion g_u, the optimization problem (<ref>) becomes a submodular maximization problem.
The problem is NP-hard and no algoithms exist to solve it exactly <cit.>.
The general strategy to solve the submodular maximization problem is based on the greedy heuristic as given by  ().
The algorithm iteratively selects an element from the ground set such that it gives the maximum value for the incremental update value (,,∪{e}) - (,,) at each iteration (the ties are broken arbitrarily).
In case of monotonic submodular functions with cardinality constraints,  () gives a worst case lower bound on the optimality gap between the optimal solution and the greedy solution as given in Theorem <ref>.
In fact, similar bound holds for any monotonic submodular functions with matroid constraints and cardinality is a special case of matroid constraint <cit.>.

 () proposed a faster “accelerated” version of the greedy algorithm using the fact that g(_j∪{l}) -g(_j) ≤ g(_i ∪{k}) - g(_i)  g(_i ∪{l}) ≤ g(_i ∪{k}), ∀ j < i.
The algorithm carries out `lazy' updates thus avoiding a complete scan to find the next item to recommend <cit.>.
By using priority queues, the retrieval at line 5 and updation at line 10 in Algorithm<ref> can be achieved in constant and logarithmic time respectively.
Previous experimental results on large scale datasets showed that the accelerated greedy algorithm gives a substantial speedup boost <cit.>.
Our proposed accelerated greedy algorithm for group recommendation which we call SubmodulAr Group recommendation Algorithm (SAGA) is  given in Algorithm <ref>.


For a non-decreasing submodular function f, let ^* be the optimizer of (<ref>) and  be the set returned by the greedy algorithm iteratively adding to the current solution the item that provides the highest gain in the objective function,

then
f() ≥(1-(1-1/)^)  f(^*) ≥ (1-1/e) f(^*)







§ EXPERIMENTS


In this section, we describe the experimental setup and report the results using user groups generated from the 1M MovieLens[<http://grouplens.org/datasets/movielens/>] dataset.
A major issue with GR research is the difficulty of evaluating the effectiveness of the recommendations <cit.>.
Online evaluation is expensive and it  can be performed only on a very limited set of users.
Here we follow the offline experimental protocol proposed in  ().
We compare our proposed algorithm against two state-of-the-art group recommendation algorithms <cit.>.



 §.§ Group Formation

The MovieLens dataset contains ratings on a scale of 1 to 5 of 6040 users for 3670 movies.
In our experiments we use users only with a minimum of 100 ratings and ended up with a set of 2945 users and 3670 movies.
Following the previous work by  and , we create groups corresponding to two common real life scenarios (i) random groups and (ii) similar groups.
Random groups are generated by randomly sampling a fixed number of users whereas similar groups are generated by randomly sampling from the user set provided that the individual user-user similarity is greater than a threshold value.
We set 0.60 as the similarity threshold value.
The detailed description of the group statistics is given in Table<ref>.





 §.§ Protocol

We carried out holdout validation by randomly selecting 30% of the item set and marking it as unrated wherever the rating values are observed.
To reduce the variability in the result, the procedure is carried out five times and the reported results are the average values over the five selections.
The affinity and similarity values are calculated based on the item and user features.
The item and user features are extracted from the rating matrix using the non-negative matrix factorization based on weighted-regularized non-negative alternating least squares algorithm <cit.>.
In our experiments, the dimension of the item/user feature space is set to 150.
We used the rbf kernel as the item afinity function h, i.e. _ij =exp(-γ||x_i - x_j||^2) where x_i and x_j are the i^th and j^th item features.
The γ value is chosen by running the algorithm for a set of values in the range {2^-3,⋯,2^3} in multiples of two, and the reported results are for the best γ value for the respective algorithms.
For the item saturation function f, we use natural logarithm f(x) = ln(1+x), and for the user saturation function we experimented with two settings (i) identity function g_u(x) = x and (ii) concave function g_u(x) = √(x).
The user affinity matrix  is defined as the cosine of the user feature vector i.e. _ij = cos(y_i,y_j) where y_i and y_j are the i^th and j^th user features.




 §.§ Baselines

We used two baselines to compare against the performance of our proposed algorithm.
First baseline is the popular aggregation strategy Average Misery (AM) and the second baseline is the scalarization based algorithm proposed by  () called group recommendation with fully materialized disagreement list (FM).
Both AM and FM require unobserved rating values to be generated beforehand, and we use the non-negative matrix factorization (used for the user/item feature extraction) to generate the unobserved rating values.


  §.§.§ AM

Average Misery is a popular score aggregation strategy where the first  items with the highest average score for the group is selected.
Formally, Average Misery algorithm selects an item i^* such that


    i^* ∈_i ∈ rel(,i)
    .

where rel(,i) is defined as the sum of the preference scores for the item by the users in the group , i.e. rel(,i) = ∑_u ∈ r_u^i.



  §.§.§ FM

In FM, an agreement term and a disagreement term are linearly combined using a trade-off parameter, and for each value of the trade-off parameter the discrete optimization problem is solved using thresholding <cit.>.
Formally, the FM algorithm selects an item i^* such that


    i^* ∈_i ∈ λ× rel(,i) + (1-λ)(1-dis(,i))

where rel(,i) is as defined above, and dis(,i) is the average pair-wise disagreement for the item i for the group .
Formally,


    dis(,i) = 2/|| (|| - 1)∑_u,v ∈
     u ≠ v| r_u^i - r_v^i |




 §.§ Performance Measure

In our experiments, we measure the relevance and coverage of the recommended items to the group members. 
We use Discounted Cumulative Gain (DCG), a very popular performance measure widely used in information retrieval tasks to measure the utility of the recommended items to a user <cit.>, and Popularity Stratified Recall (PSR), which measures the coverage/popularity-bias of the recommended items <cit.>.

Discounted Cumulative Gain (DCG):
DCG is used in the context of ranking.
It measures the quality of a ranked list by the sum of the graded relevance discounted by the rank of the item.
In our experiments, we used the below formulation:

    ∑_i ∈2^r_i-1/log(i+1),

where r_i is the graded relevance score of the i^th item.
In our settings, the i^th item is the i^th item entering  for the greedy algorithm.
We compute the average values of the DCG, over all the users in any group, and the reported results are average over the total groups.
Higher values for DCG is desired, as it indicates more relevant recommendations appears at the top of the recommendation list.

Popularity Stratified Recall (PSR):
A good recommendation strategy should cover items which are relevant to the users but rare.
PSR is proposed to measure the ability of a recommender system to recommend items from the tail of the item-popularity distribution.
The submodular formulation of our objective increases the chance of recommending unpopular relevant items.
Formally, PSR is defined as:


    1/||∑_u ∈∑_i ∈_u^+(1/N_i^+)^β/∑_u ∈∑_i ∈_u(1/N_i^+)^β,

where _u^+ is the set of recommended items that are known to be relevant for user u (among the  recommended items),
_u is the set of items in the test set that are known to be truly relevant for user u,

N_i^+ is the number of relevant ratings for item i in the test set and β∈ (0,1) is a hyperparameter which adjusts for the popularity bias.
We used β=0.5 in our experiments.
Higher values for PSR indicates more relevant unpopular recommendations appears at the top of the recommendation list.



 §.§ Results & Discussion



  §.§.§ Random Groups





The results for the random groups are given in Figures <ref> and <ref>.
Figure <ref>  depicts the performance of different algorithms as a function of group size (||), for a fixed number of recommendations ( = 5) for random groups.
The performance of AM and FM algorithms are very similar with AM performing marginally better than FM for groups of smaller sizes.
In effect, the leverage of employing disagreements between group members for recommendation is insignificant in case of random groups.
Similarly, the performance of the linear and concave versions of the proposed SAGA algorithm are very similar.

Howbeit, SAGA ,in general, performs significantly better than both AM and FM.

Figure <ref> illustrates the performance of different algorithms as a function of recommendation size (), for a fixed group size (||= 4).
The plot follows the same pattern as in the case of varying group sizes for random groups.
The performance of AM and FM are very close to each other whereas the performance of linear and concave version of the SAGA algorithm are close to each other.
Yet, the two formulations of SAGA give superior DCG values compared to both AM and FM.
For different values of the group size (∈{10, 25, 50}), we observed the same pattern.
Due to space limitation, we omitted the corresponding plots.




Figures <ref> and <ref> shows the coverage performances of different algorithms as functions of group size (||) and number of recommendations ().
The AM and FM algorithms perform equally but sub-optimal.
The SAGA linear and concave versions performs better than AM and FM algorithms with the SAGA concave version performs only marginally better than the linear version.
Thus SAGA algorithms recommend relevant but novel items.



  §.§.§ Similar Groups





The results for the similar groups are given in Figures <ref> and <ref>.
Figure <ref>  illustrates the performance of different GR algorithms as a function of group size, for a fixed number of recommendations ( = 5) for similar groups.
It is very clear from the plot that AM performs better than FM.
Also, as the group size is increased the performance improvement becomes significant.
The linear SAGA algorithm performs marginally better than AM for smaller number of groups, but as more number of users are added to the group, the performance deteriorates.
Unlike in the case of random groups, in case of similar groups the concave formulation of the user saturation function gives significant performance boost over AM, FM and SAGA with linear user saturation function.
We observed the same pattern by varying the size of the recommendation set.

In Figure <ref> the DCG values of different algorithms are plotted as a function of the size of the recommendation set for a fixed group size (||) = 4.
The performance of AM and FM algorithms follows an identitical pattern.
For smaller number of recommendations, AM performs better than FM and as the size of the recommendation set increases, FM outperforms AM.
But in both cases, the significance is negligible.
The linear SAGA algorithm performance degrades below FM and AM as the recommendation size set increases.
The concave SAGA algorithm gives the best DCG values for all recommendation set size and the performance imporovement is significant.
We achieved very similar results by varying the group size.

The performances of coverage metrics for different algorithms are given in Figures <ref> and <ref>.
Unlike in the case of random groups, all the algorithms perform equally well, and there is no added benefit of using SAGA algorithm if ones motive is only in serendipitous recommendations.




We will now analyze the performance degradation of the concave SAGA algorithm compared to the linear SAGA algorithm for random groups.
In case of random groups, for each group the average user-user similarity value is low (average value is 0.14).
Hence for smaller sized groups the performance gain obtained by employing submodular structure over the user saturation function is less than employing the linear structure.
In other words, for smaller groups since the user interests are very different and the relevant movies are often conflicting, adding an item by the diminishing return property does not result in overall performance gain.
We argue that for medium and larger groups, employing a submodular structure does result in performance improvement.
Figure <ref> contains the DCG values for the random group of size 8.
It can be verified that submodularity over user saturation function yields better performance.





§ CONCLUSION


The core idea presented in the paper is that the group recommendation problem can be
modeled as a submodular optimization problem.
In fact, several important modeling options in group recommendation and social choice theory turn out to be specific instances of the group consensus score function we proposed in this work.
The advantage of our approach is that the bundle of items recommended to a  group
not only depends on the aggregate preference of users (in the group) towards the items
but also the affinity (or dissimilarity) between the items.
Experiments on real data sets attest to the efficacy of our approach.



§ ACKNOWLEDGMENT

S.P.P thanks Nicolas Usunier and Yves Grandvalet for many fruitful discussions which led us to the core idea presented in this paper.
We thank our anonymous reviewers for their valuable comments and suggestions.


aaai


