Collaborative Filtering, one of the main Recommender Systems' approach, has been successfully employed to identify users and items that can be characterized as similar in large datasets. However, its application is limited due to the sparsity problem, which refers to a situation where information to infer similar users and predict items is missing. In this work, we address this by (i) detecting underlying user communities that aggregate similar tastes and (ii) predicting new relations within communities. As a consequence, we alleviate some of the major consequences of this problem. As shown by our experiments, our method is promising. When compared to a user-based Collaborative Filtering method, it provided gains of 20.2% in terms of sparsity decay, for instance, while improving RMSE values in only 2.8%.
Recommender systems have been a popular topic of research since it became
clear that people of widely varying backgrounds would be able to query the same
underlying data [
In a typical CF scenario, there is a bipartite network U × I where nodes are comprised by users U and items I. A link between a user u and an item i exists if and only if u rated i, and the weight of this link is the rating itself. From U × I one can infer a network U × U , where nodes are users U and a link between two nodes u and v exists if and only if they co-rated at least one of the items in I. The weight of such link is given by the similarity between u and v’s co-ratings, using a metric such as cosine or Pearson correlation. Traditional CF systems predict ratings for users, with respect to items they did not rate yet, according to a scheme defined by the following equation:
X
rv,i × simu,v rˆu,i = v∈Ni(u)
X where rˆu,i is the predicted rating user u will give to item i, Ni(u) is the set of all neighbors of u in U × U that rated item i, simu,v is the similarity between u and its neighbors v in U × U (link weights), and rv,i is the actual rating each one of these neighbors gave to i (i.e., can be found in U × I).
Given that even very active users rate just a few of the total number of available items and, respectively, even very popular items are rated by only a few of the total number of users, U × I and U × U are very sparse. High sparsity levels pose a big challenge to the quality of predictions, as well as to the number of predictions that a recommender system can actually compute. Because of sparsity, the confidence of predicted ratings may be questionable, since they are based on a rather little amount of evidence.
Other important structural problems related to data sparsity are reduced
coverage and neighbor transitivity [
Many approaches have been proposed to alleviate the data sparsity
problem. Dimensionality reduction techniques, such as SVD and PCA, create a more
dense representation of U × I [
Other option – the one we explore in this work – involves making either U ×U
or U × I more dense via link prediction. Huang, Cheng and Zeng [
Most link prediction methods are based on a 2-hop transitivity in U × U –
i.e., if user u is connected with user v, and user v is connected with user w, then
a link might be predicted between u and w. The intuition behind it is that users
u and w are likely to have similar preferences. Links between nodes connected
by a path with length bigger than 2 (3-hop, 4-hop etc.) are not considered by
most methods. The reason is that, empirically, it is known that preferences are
not so transitive [
U × I and U × U present a significant Small-World effect [
Our proposed method to tackle this problem involves two major steps (steps
2 and 3 in Fig. 1): (i) a community detection algorithm is applied for aggregating
users with similar tastes in communities; (ii) only links between users within a
same community are determined using different link predictors and weighted
using a simple transitive schema. To the best of our knowledge, this is the first link
prediction method for data sparsity that makes use of communities, in a
divideand-conquer fashion, ignoring either demographical data or explicit social ties.
Sahebi and Cohen [
The present work is structured as follows. Sections 2 and 3 detail each step of our method. Section 4 presents experiments and results. Finally, Section 5 discusses our conclusions and points out some future work lines.
Detecting Communities in the Users Network U × U
The first step of our method involves detecting communities of users in U × U .
The detected communities must represent users with similar tastes. By
construction, high link weights in U × U indicate taste similarity between users.
Therefore, to detect similar taste communities, we should employ an algorithm
that not only aggregates densely connected nodes, but guarantees that the
connections among them are as high weighted as possible. The method proposed
in [
Besides dealing with link weights in the desired way, BGLL scales very well
with the number of nodes in the network, which is particularly interesting from
a recommender systems’ viewpoint. BGLL also works hierarchically, providing
some clustering options with more or less granularity. There is at least one
work in the field of recommender systems that already applies this algorithm,
intending to find user communities for group recommendation [
BGLL detects communities via modularity optimization. Modularity, a well known function in the complex networks field, is normally used to measure the quality of a partition. Basically, it searches for a network partition C that maximizes the Q value defined by:
Q = 1 2m
X[Ai,j − kikj ]δ(Ci, Cj )
i,j 2m
(2)
where Ai,j represents the weight of the link between i and j, ki = X Ai,j is
j
the sum of the weights of the links attached to vertex i, Ci is the community to
which vertex i is assigned, the δ function δ(u, v) is 1 if u = v and 0 otherwise
and m = 12 X Ai,j . Finally, Q ∈ [
i,j
BGLL is based in two steps that are repeated iteratively. Initially, all nodes belong to their own community (N nodes and N communities). One looks through all nodes, from 1 to N , in an ordered way. Each node looks among its neighbors is observed, the node in question does not change of community. This step is performed iteratively until a local maximum of modularity is reached (each node may be considered several times). Once a local maximum has been attained, a new network, whose nodes are the detected communities, is built. The weight of the links between communities is the total weight of the links between the nodes of these communities.
The two steps are repeated iteratively, thereby leading to a hierarchical decomposition of the network. In this work, we will only take into account the communities corresponding to the last determined level of the hierarchy - i.e., the least granular ones. We explain this decision further in Section 4.
Predicting Links in the Users Network U × U
There are several techniques for predicting links in a network. Liben-Nowell and
Kleinberg [
In this work, we will not explore the second category, given that it generates links between nodes not so close. As mentioned previously, it is empirically known that preferences are not that transitive - e.g., if node u is similar to node v, node v is similar to node w and node w is similar to node y, one cannot state that u and y are also similar.
The techniques considered for this work are Common neighbors, Jaccard’s
coefficient, Adamic/Adar, and Preferential attachment [
Common neighbors This predictor determines the number of common neighbors between two nodes. Then: (3) (4) Jaccard’s coefficient This predictor measures how likely a neighbor of node x is to be a neighbor of y and vice-versa. Then: score(x, y) = |Γ (x) ∩ Γ (y)| Adamic/Adar This predictor assigns high weight to common neighbors z of x and y which themselves have few neighbors Γ (z). Then: (7) score(x, y) = |Γ (x)| × |Γ (y)| 4
In this work we applied our method to a dataset sampled from the movies’ recommender site MovieLens1. It comprises 819 users and 1,180 items. The relations between these two entity types are ratings varying from 1 to 5. In this dataset, there are 7,851 rating relations between users and items, generating a bipartite graph U × I: one partition corresponds to users (U ) and the other corresponds to items (I). A second network U ×U is induced from U ×I following the traditional user-based CF approach outlined in Section 1.
We computed the similarity between users in U × U applying Pearson
correlation [
X
After setting U × U up, we applied a C++ BGLL implementation for detecting user communities in it2. BGLL generated a hierarchy of four levels. The lower level (level 0) had 819 communities, one corresponding to each node. The higher one (level 3) had 627 communities. In this work, we only explored the communities reported in level 3, because the ones in levels 0, 1 and 2 were too fine-grained.
From 627 communities, only 11 were associated to more than one node. In addition, only 187 out of 819 users belonged to communities with more than one node. Analysing the users assigned to one-node communities, we discovered that 1 MovieLens data, http://www.grouplens.org/. 2 http://sites.google.com/site/findcommunities all their links in U × U have 0.0 weight. This is the reason why BGLL never changes their communities, associating them with relevant neighbors: all their neighbors are equally relevant, given that all their links have the same weight.
In a certain sense, this reinforces the idea that there is a challenging long tail behind recommender systems: while few people have more regular preferences, being easy to aggregate, most users have very hard-to-describe tastes, limitating their allocation within communities. On the other hand, we believe that although the network topology does not help these users much, perhaps other clustering approaches can help finding good communities for at least a part of them. One possibility involves comparing attributes from their rated items and some of their own profile attributes.
For the purpose of this work, we only take into account the 11 communities with more than one user. These communities will be referred to as relevant communities.
Table 4 lists some of the most important movies rated in each community.
Although some movies are assigned to multiple communities, such as “Contact”,
it seems they do reflect different user tastes. In a general sense, Table 4 indicates
a certain degree of homophily among users3 [
Inside every relevant community, we generated lists of new links Lp using all different predictors presented in Section 3. The weight of a predicted edge is given by: sim(u, v) = 1
[ X sim(u, y) × |Nu,v| y∈Nu,v
X sim(y, v)]
y∈Nu,v
(8)
where Nu,v is the set of common neighbors of u and v. Given that we weight
actual links in U × U using Pearson correlation, all similarities will range from
-1.0 to 1.0. As a consequence, a multiplication between average similarities will
always be, at most, equal to the highest similarity in question. This property
is desirable in our scenario because we expect predicted similarities – which are
transitive – to be lighter than actual similarities – which are naturally induced
from U × I. There are some other ways of estimating the weight of an edge in
U × U [
After predicting and weighting links, we added the 10%, 20%, 30%, 40%, and 50% best – i.e., those with higher similarities – to U × U . For the sake of completion, we also analysed the recommender system generated when we add 100% of the predicted links (Full Lp).
We compared our results with two baselines: the traditional user-based CF
system discussed in Section 1 [
To assess the quality of our proposed solution, we do not measure neither the detected communities nor the predicted links quality directly. Alternatively, given that data sparsity challenges Recommender Systems’ effectivity, we will evaluate our method through typical metrics of this field. Besides being more relevant with respect to the posed problem, using typical metrics eases the task of comparing our solution with chosen baselines.
The selected metrics are Root mean-square-error (RMSE), Coverage, Sparsity
Decay (SD), Recall, and Precision [
RMSE Given a test set T of user-item pairs hu, ii, RMSE measures the divergence between real ratings ru,i and predicted ratings rˆu,i. The real ratings are known from offline experiments that do not interfere in rˆu,i computations.
RMSE = uuv 1 t |T |
X (rˆu,i − ru,i)2 hu,ii∈T (9) Sparsity Decay (SD) It measures the improvement the system does with respect to relations between users and items. Let O be the set of original ratings in U ×I, and P be the set of predicted ratings between users and items. Then:
Comparing two recommender systems A and B working over a fixed dataset, the one that presents the lowest SD is making more predictions. If both systems present very similar RMSEs, then the one that makes more predictions should be preferred, given that it increases the system’s capacity of making different recommendations.
Given a test set T of user-item pairs hu, ii, let TP be the number of user-item relations (ratings) that actually exist in T and that were predicted by the system; let F P be the number of user-item relations (ratings) that were predicted by the system although they do not exist in T ; and let FN be the number of of useritem relations (ratings) that actually exist in T but were not predicted by the system. Then:
Coverage = |R(I)|
|I| SD =
|O| (|O| + |P |)
Recall = P recision =
|TP | |TP | + |FN |
|TP | |TP | + |FN | Coverage In our context, coverage is the percentage of items for which the system is able to generate a recommendation. Let |I| be the total of considered items and |R(I)| be the number of items that are recommended at least once. Then: (10) (11) (12) (13) 1.082 0.863 0.192 0.285 0.004
Results in bold correspond to the best and worst values found for each metric in each experimental scenario. It is worth pointing out that, when compared against TUB, none of the proposed solutions - Common neighbors, Jaccard’s coefficient, Adamic/Adar, Preferential attachment, and Full Lp - improved global coverage. This means that our method did not generate predictions for any item that was not already being covered by TUB. Even though, we generated many more predictions for already covered items, as indicated by SD - i.e., although the items are the same, there are predictions relating them to many more users, which is a highly desirable feature in a recommender system. One can state that {1,2}-hopub outperforms all other competitors in terms of global Coverage and low SD, but the quality tradeoff is not acceptable: all RMSE values are consistently higher when compared against TUB.
Concretely, the most important metric is RMSE. If the error is not low, increasing the number of predictions is not worth it: one could always recommend random items if quality (low error) does not matter. Of course, this is not the case and that is why we are particularly interested in the results obtained with Jaccard’s coefficient. This predictor presents an interesting tradeoff between SD and RMSE. For practical purposes, using the 20% best links in the Lp related with Jaccard’s coefficient improves the number of predictions significantly (SD goes from TUB’s 0.297 to 0.237) without adding much noise in quality (RMSE goes from TUB’s 1.010 to 1.039).
As expected, RMSE increases when we add more links – perhaps, it could be alleviated if the weight of predicted links were computed in a different fashion, but we do not believe that it would solve this issue completely. Also, for all studied scenarios, adding more links consistently improved the number of predictions, generating lower SDs. Finally, as expected, higher RMSE values are highly correlated with lower SD values – in other words, generating more predictions necessarily decreased quality.
Another analysed metrics were precision and recall. It is easy to observe
that all precision values are consistently smaller than recall values. It indicates
that, even if a significant fraction of the predicted user-item relations actually
exist (recall), most real relations are missing (precision). There is not a balance
between these two aspects, which may mean that the analysed recommenders are
not fitting user tastes very well, but it would take further investigations to assert
it. Despite this behavior, we want a solution that minimizes the difference with
respect to original TUB’s precision and recall. Once again, Jaccard’s coefficient
is a good option. For the sake of comparison, there is at least one work that
analyses precision and recall in link prediction based recommender systems, also
presenting quite low values for both metrics [
In this work, we proposed a method for alleviating the sparsity problem in CF recommender systems, keeping a commitment with good quality predictions. Concretely, we analysed the impact of using community detection before predicting links in the CF Recommender Systems scenario. To the best of our knowledge, this is the first attempt in this direction. The results indicate that predicting links only within users belonging to the same community helps lowering prediction errors, when compared with a fully-transitive baseline, {1,2}hopub.
The proposed method is also positive in terms of alleviating some of the drawbacks related to the sparsity problem: via communities, we delimitate users with similar taste and, when we link them, we are presenting a solution to the neighbor transitivity problem. Although our method did not increase global coverage, when compared with original TUB system, it improved the number of predictions for already covered items, which is highly desirable. Finally, with more links connecting users in U × U , we increase the amount of information used by the system for making predictions, increasing its confidence.
The proposed method, nonetheless, does not present a solution to the cold
start problem [
In the future, we intend to (i) explore different methods for detecting communities and predicting links, (ii) compare different link weighting schemes, (iii) apply the proposed solution to bigger networks, (iv) compare our method with more robust baselines, (v) consider the usage of social/demographical data, and (vi) predict links on demand only for users who suffer from sparsity.
This work was partially sponsored the Brazilian National Institute of Science and Technology for the Web (grant MCT/CNPq 573871/2008-6), and by the authors’ individual grants and scholarships from CAPES, CNPq and FAPEMIG.