Nowadays social websites have become a major trend in the Web 2.0 environment, enabling abundant social data available. In this paper, we explore the role of two types of social relationships: membership and friendship, while being fused with traditional CF (Collaborative Filtering) recommender methods in order to more accurately predict users' interests and produce recommendations to them. Through an exploratory evaluation with real-life dataset from Last.fm, we have revealed respective effects of the two explicit relationships and furthermore their combinative impacts. In addition, the fusion is conducted via random walk graph model in comparison with via weighted neighborhood similarity matrix, so as to identify the best performance platform. Indepth analysis on the experimental data particularly shows the significant improvement by up to 8% on recommendation accuracy, by embedding social relationships in CF via graph model.
H.5.3 [Group and Organization Interfaces]: [Collaborative Filtering, Computer-supported cooperative work, Evaluation/methodology]; H.3.3 [Information Storage and Retrieval]: [Information Filtering] Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
Copyright 200X ACM X-XXXXX-XX-X/XX/XX ...$10.00.
In recent years, collaborative-filtering (CF) based
recommender systems have been widely developed in order to
effectively support users’ decision-making process especially
when they are confronted with overwhelming information
(e.g. a large amount of product options that popularly
appear in the current Web environment). There are two basic
entities considered by the recommender: the user and the
item. The user provides his rates on items (e.g. movies,
music, books, etc.) that he has experienced, based on which
the system can connect him with persons who have similar
interests and then recommend to him items that are
preferred by these like-minded neighbors. In some cases which
don’t have rating values available, the user’s interaction with
items can also be considered. That is, if we can only get
the information that a user watched a movie, the ”rating”
is 1; otherwise it is 0. The recommendation method based
on this binary rating matrix is also named as log-based CF
[
We term this kind of community relationship as explicit social relationship, since it is directly defined by users, rather than inferred by the system. As a matter of fact, two types Explicit social relationships of explicit relationships are commonly available on the current websites (as in the example of Last.fm): friendship and membership. For instance, users A and B are friends given that A adds B in his friend list (or conversely), but it does not refer that they must have similar music tastes. On the other hand, if A and B join in the same group, it indicates that they have the membership relation and are likely with the similar interest (e.g. on ”Beatles” provided it is the group’s title).
It is believed that explicit social relationship can be likely
applied to compensate the limitation of implicit
relationship inference approach and improve the accuracy of
recommender systems [
Given that the membership contains more information implying the user’s preferences, such as his interest on the music genre or singer as indicated by the group’s property and his like-minded people involved in the same group, we are interested in understanding whether this additional information could produce any practical benefits. Thus, in this paper, our objective is to study whether and how to best fuse both of membership and friendship, by means of comparing their respective effects and potential combinative impacts via different fusion platforms. We believe that our study will shed light on the role and applicability of social information in boosting collaborative intelligence of current recommender systems. More specifically, our contributions can be summarized as follows: • We demonstrate the exact value of fusing explicit social relationships into recommender systems. Particularly, in some cases, the neighborhood of users learnt from membership has been found more accurate than from purely embracing friendship with traditional CF. • We develop a framework to fuse and evaluate multiple types of social relationships in a systematical approach through weighted-similarity calculation. Moreover, we propose a novel graph model to fuse the social relationship with rating matrix, and adopt random walk algorithm to produce neighborhood similarities for recommendations. With a real-life dataset, we compared it with the weighted-similarity approach and identify the superior performance of graph fusion in improving recommendation accuracy.
In the next section, we first provide a brief review of related work, and then propose a systematical approach to study the use of explicit social relations and incorporate them in collaborative recommenders via graph model in addition to via weighted-similarity. Next, we show the experiment design and results analysis, followed by the final section of conclusion and future work. 2.
We review the related literature of fusing heterogeneous data sources with rating matrix to improve standard CF from two perspectives: Fusion of Social Relationship, and Graph-based Recommender Algorithm. 2.1
Since popular user-based and item-based CF algorithms
that only rely on user-item rating matrix always suffer from
sparse and imbalance of rating data, researchers have started
to incorporate other data sources to improve standard CF.
Balabanovic et al. [
Recently, with the increasing development of social
websites and appearance of social data, researchers have begun
to pay attention to the social data and explored its usage in
recommender systems. Konstas [
The computation of user/item similarity plays a key role
in user/item-based collaborative recommenders. Popular
measurements of user similarity are Cosine similarity and
Pearson’s correlation coefficient (see [
Recent years, graph-based methods have been introduced
to model relations between users and items from a global
perspective, and been used to seamlessly incorporate
heterogeneous data sources into the traditional user-item rating
matrix. Huang proposed a two-level graph model for
products [
Random walks on graph have been extensively discussed
[
However, the limitation of related work in the ”fusion of social relationship” (the first subsection) is that few have considered the potential positive role of membership. Moreover, in the related work on ”graph-based recommender algorithm”, no work on its performance as a fusion platform has been conducted. In this paper, we therefore aim at investigating how to effectively fuse both of friendship and membership into CF algorithm via random walk approach in order to improve the performance and solve the sparsity problem. To the best of our knowledge, our work is one of the first attempts to use both friendship and membership to enhance recommender systems.
In this section, we mainly take into account of two types of explicit social relationships: friendship and membership, and propose a generic framework to fuse them with the useritem rating matrix. Given that user-user similarity computation is crucial to collaborative recommenders, a more accurate user-user similarity always leads to better recomFriendship Enhanced User Preference
User-Item Friendship
Similarity Similarity
Item User +
User Friendship Matrix
Group Membership Matrix
User User User-Item Membership
Similarity Similarity
Membership Enhanced User Preference mendation results. Our fusion framework aims at leveraging the two social relationships to strengthen the user similarity calculation process by two means: one is combining the user-similarity from friendship and/or membership with similarity from rating matrix in a weighted approach; the other is modeling the social relations and rating matrix all in a graph, and then applying random walk on this graph to compute the user similarity. 3.1
In the rating matrix, we can view the preferences of users as feature vectors. Every user vector consists of n feature slots, one for each available item. The values used to fill those slots can be either the rating rak that a user ua provides to the corresponding item ik, or 0 if no such rating exists. Now, we can compute the proximity between two users ua and ub, by calculating the similarity between their vectors. For example, we can use the Cosine similarity for this calculation as follows:
Similarity(ua, ub) = (1)
Rua · Rub ||Rua ||||Rub || where Rua and Rub are two vectors of ratings from users ua and ub respectively.
According to the user similarity calculated from the rating matrix, we give a detailed description of fusing social relationships via weighted user similarity based on Fig 2.
When fusing friendship with user similarity from rating matrix, we need to get a user similarity based on the friendship firstly. We represent the friendship in the form of a user-user matrix. If two users ui and uj are friends, then the value of cell uij is set to 1, otherwise 0. Based on this useruser matrix, we calculate a friendship similarity by adopting Cosine Correlation, named Simfri. Next, when calculating the final user similarity between ua and ub, we combine the Simfri with Simui(user similarity calculated from user-item The parameter λ is used to adjust the weight of Simfri and Simui, the bigger the λ is, the rating matrix plays a more important role in the combined similarity. Finally, we use this combined similarity Simui+fri in finding neighbors for each user.
When fusing the membership, firstly we also need to get a user-user similarity based on the membership data. Since membership is the relationship between the user and the communities/groups he/she joined, a new type of entity was introduced besides the two entities (user and item). We concretely represent the membership in the form of a usergroup matrix, where the rows indicate users and the columns indicate the groups joined by users. If a user ui joins group gj, the value of cell uij is set to 1, otherwise 0. Based on this user-group matrix, we can get a membership similarity by using Cosine Correlation too, named Simmem. As for the generation of final user-user similarity, a weighted formula is applied where λ plays the same role as before.
Simui+mem(ua, ub) = λSimui(ua, ub)
+(1 − λ)Simmem(ua, ub)
Furthermore, we are interested in seeing what will happen if two types of social relations are fused together with the rating matrix. In this condition, we first calculate the useruser similarity Simfri from friendship and Simmem from membership independently, and then introduce two parameters: λ and β to adjust the weights of three data sources as shown in the equation 4.
Simui+fri+mem(ua, ub) = λSimui(ua, ub) + (1 − λ) (βSimmem(ua, ub) + (1 − β)Simfri(ua, ub)) At the first level, λ is used to adjust the weight between rating matrix and the other two social relationships; and then β is used to adjust the remaining weight between friendship and membership. The bigger the λ is, the rating matrix plays a more important role; the bigger the β is, the membership plays a more dominant role in the combined user-user similarity.
After the computation of user-user similarity for finding neighbors, the next step is to recommend items to users by predicting each item’s ratings. The predicted rating ri,m of a test item m for the user i is hence computed as: ri,m =
PN j=1 sim(ui, uj) ∗ rj,m PN
j=1 sim(ui, uj) matrix) in a weighted approach as follows:
Simui+fri(ua, ub) = λSimui(ua, ub)
+(1 − λ)Simfri(ua, ub) where rj,m is the rating of user uj on the item im, and sim(ui, uj) is the similarity between the current user ui and the neighbor uj. In fusing via weighted-similarity approach, sim(ui, uj) can be similarity measures in equation 2, 3, and 4, depends on the fusing strategy and data used each time. 3.2
In the “fusing via weighted-similarity” method, we calculated the user-user similarity based on the static “local” pairwise user information. As we know, social network is inherently in a graph structure with the transitivity characteristics as a key feature of social relations, therefore we have (2) (3) (4) (5) been motivated to further use graph-based random walk algorithm for modeling these social data (i.e. friendship and membership). We think that the transitivity of the graph will improve the computation of the similarity between two users. 3.2.1
The first key issue is to construct a meaningful graph so that the resulting similarity can truly reflects the preference similarity between users. Considering a graph G = (V, E, W ), where V is the set of nodes (users, items or communities, etc.), E is the set of edges which represent relationships between all types of nodes, and W is the set of weights for all edges.
The relationship data in a social community can be interactive relationship, such that user watched a movie or listened to a song; or be social relationship like membership or friendship. Let us use Last.fm which contains all types of these data for example. It can be modeled by a graph G in the following way: there are three types of nodes in Last.fm, the user, artist (item) and group, and each element of the user, artist and group corresponds to a node of the graph; and the interactive relationship like a user listens to an artist, social relationship like user is a member of a group, and user is a friend of another user is expressed as an edge. When a random walker walks on the graph, the difference of node types were ignored, and we only care about how many short paths existed between two nodes which have directly impact on their similarity computation, so special treatment is not needed for any type of nodes in our graph.
The weight wij of the edge connecting node i and node j should have a meaningful value. Traditionally, we usually deal with interactive data in the following convention: the more frequent the interaction between node i and node j, the larger the value of wij, and consequently, the easier the communication through the edge. However, in the case of social community, besides interactive data we also have social relationship, and they usually are not associated with a frequent number, e.g. most users join a group only once, and so is the same for adding friends. For the consistency of the two types of edges and simplicity, we set the weight of member of edge and friend of edge to be 1, and treat listens to edge as follows: if a user listened to the songs of an artist more than 3 times, then the edge connecting the user and the artist was weighted 1. We require the weights to be both positive wij > 0 and symmetric wij = wji, so the graph we built is an undirected graph.
When handling friendship between users, there are several
approaches to transforming the pairwise similarity between
nodes of the same type (e.g. users) into a graph [
When the graph was built, for the corresponding symmetric adjacency matrix A of graph G, the element aij was defined as: aij = wij if node i is connected to node j and aij = 0 otherwise. Thus, people who listen to the same artists and join same groups, will be connected by a comparatively larger number of short paths. 3.2.2
Random walk is a mathematical formalization of a
trajectory that consists of taking successive random steps. At each
step, the next node in the walk is selected randomly from
the neighbors of the last node in the walk. The sequence
of visited nodes is a Markov Chain [
From the viewpoint of collaborative recommender systems, finding accurate neighbor set for each user is the cornerstone, so a good similarity measure on the graph is a crucial step.
Fouss et al. [
ECTD is the abbreviation for Euclidean Commute-Time Distance. Average commute-time is the average number of steps that a random walker, starting in node i (i 6= j), will take to enter node j for the first time and go back to i, represented as n(i, j). Average commute-time is symmetric by definition, and it is a distance measure. n(i, j)1/2 is also a distance in Euclidean space, and it is named as Euclidean Commute-Time Distance.
L+ is the Moore-Penrose pseudoinverse of the Laplacian matrix L. The Laplacian matrix L of the graph is defined as, L = D - A, where D = Diag(ai.), with dii = [D]ii = ai. = Pn
j=1 aij, and A is the adjacent matrix of graph G. Let e be a column vector with 1(i.e., e = [1, 1, . . . , 1]T , where T denotes the matrix transpose), then L+ can be computed with the formula:
L+ = (L − eeT /n)−1 + eeT /n, where n is the number of nodes. If we define ei as the ith column of I, ei = [0, . . . , 0, 1, 0, . . . , 0]T (1 is in the ith column), then we can explain the relation between average commute-time and L+ in the form
n(i, j) = VG(ei − ej)T L+(ei − ej), where each node i is represented by a unit vector ei in the node space spanned by {ei}. It can be proved that the node vector ei can be transformed into a new Euclidean space, and the elements of L+(lij) are the inner products between these transformed node vectors. Therefore L+ is a kernel matrix(a Gram matrix) and can be used as a similarity matrix for the nodes.
According to Fouss’ study, the inner-product based similarity measure L+ provides better and more stable results for collaborative recommenders, so we adopt L+ metric to measure the similarity between users, which means in equation 5, sim(ui, uj) equals to lij in this case. (6) (7) (8) 4.
Traditional data sets used in the evaluation of collaborative filtering systems, such as MovieLens, do not include explicit social relationship, while in Last.fm, a popular social music site, community information is available so that an entity-relation model can be generated which includes the relationship between users and items.
For our purpose, we extracted two typical social relationships: the friendship between users and the membership which describes the user’s participation in groups, by accessing its Web Service APIs 1. Besides, we think it is more meaningful to recommend artists instead of individual music since music is variable while preference on artists is more constant, so we use artist as the ”item” in our recommendations. A user and an item is linked if the user listened to song(s) of the artist, and a user and a community is linked if the user joined the group. The relationship between an artist and a community is formed if the artist’s songs were frequently listened by users in this group. There are also links among users describing their friendship.
We concretely established an active data set consisting of 943 users, 1, 001 artists and 676 groups. There are 36, 424 records in the user-artist matrix which sparsity degree (percentage of zero values in the matrix) is 96.14%, and 7, 038 records in the user-group matrix which sparsity is 98.89%. The total number of friendship of 943 selected users is 33776, which means each user on average has 35.8 friends. Please note that the rating matrix here is the user-artist matrix, and if a user listened to song(s) of an artist, there is ”1” in the corresponding cell.
By means of 5 fold cross-validation 2, each row (represent a user) of the user-artist matrix is randomly split into five different sets. For each time of experiment, four-fifths of of the data is included in the training set and the other is used as the testing data. 4.2
We adopted standard metrics in the area of information retrieval to evaluate our recommenders. During each round of cross-validation, we recommend and rank a set of potential artists for each user. We then compare the predicted recommendation list with true preferences on artists in the test set, and compute precision, recall, and F-measure scores. 1. Recall. The score measures the average (on all users) of the proportion (in percentages) of artists from the testing sets that appear among the top n ranked list from the training sets, for some given n. It should be as high as possible for good performance. We computed the recall from Top-1 to Top-20 artists(for a total of 1001 artists). 2. Precision. This metric measures the proportion of recommended items that are ground truth items. Note that the items in the profiles of the testing data represent only a fraction of the items that the user truly accessed. 1The web page is http://www.last.fm/api 2The number of fold is the number of tested sets. 3. F-measure. F-measure is the weighted harmonic mean of precision and recall. The equation is as follows: F = 2 ∗ precision ∗ recall (precision + recall) (9)
In the following, we report the results of recommending the top 1, 2, 5, 10 and 20 artists. At each pass, 50 users are taken as neighbors based on different similarity measures for recommendation. 4.3
At first, we evaluated the fusion approach via weightedsimilarity. A user-based collaborative filtering recommender was first run on the user-artist rating matrix, resulting in the baseline represented by CFUI (see Tables 1 to 3 respectively showing precision, recall and F-measure scores).
Then, we tried to fuse friendship with the rating matrix and used λ to adjust the weight of rating matrix and friendship while computing user similarity. Figure 3 shows how F-measure changes with the changing of λ. It achieves the peak when λ = 0.7, which means that the rating matrix contributes to 70% percent of the weight while friendship contributes to 30% in calculating the user-user similarity. Specifically, results in the second rows of Tables 1 to 3, represented by W Sfri+UI , give the precision, recall and Fmeasure scores when λ = 0.7. It can be seen that it is better than the baseline, especially when returning top 5 recommendations (the improvement of F-measure achieved up to 2.79%). In the process of tuning λ and β in the following, we considered the average score of Top-1 to Top-20 recommendations.
Next, we fused membership with rating matrix and also used the parameter λ to adjust the weight of rating matrix and membership in the similarity calculation.
From the figure 4, it can be seen that when λ = 0.8, we can get best results overall. The third rows of Tables 1 to 3, represented by W Smem+UI , respectively show precision, recall and F-measure values when λ = 0.8. It shows that the results slightly improve on the baseline, but are a little weaker than the fusion of friendship on the rating matrix.
We further fused two relationships together on the rating matrix and adopted two parameters: λ and β to adjust the weights for the three data sources as shown in Formula 4. Experimental results indicate that the hybrid fusion performs best when lambda = 0.8 and beta = 0.5 (which means rating matrix contributes 80%, friendship and membership respectively contributes 10% and 20% in the user-user similarity calculation). These results are illustrated in the last rows of Tables 1 to 3. To our surprise, compared to fusion of friendship and membership separately, it did not have dist eenm 10 v rpom 8 i e rsau 6 e m f-oF 4 e tang 2 e c r eP 0 -2
Weighted-Similarity Fusion: Rating + Friendship
Weighted-Similarity Fusion: Rating + Membership Weighted-Similarity Fusion: Rating+Friendship+Membership
Graph Fusion: Rating + Friendship + Membership 1
2 5 10 Size of Top-N recommendations 20 tinct difference and was actually even a little weaker than the pure fusing of friendship.
In order to identify whether the fusion via graph model would perform better than via weighted similarity approach given that social data are inherently in the graph structure, we finally did the experiment of fusing the two social relationships on the graph and applied random walk algorithm to calculate neighborhood similarity.
Based on the graph construction method described before, we firstly run a series of simulations to learn the optimal . After running 100 times, the optimal that we got is 0.05. The comparative results under threshold 0.05 are then computed and listed in Table 5. It shows that precision, recall and F-measure scores are all highly improved compared to the fusion via weighted-similarity approach. In particular, when returning top 2 and top 5 recommendations, the improvements significantly reached 7.94% and 7.99% respectively.
Figure 5 further shows that while returning Top-1 recommendation, the fusion via graph can achieve an improvement at 4.82%, and others are however all slightly weaker than the baseline. When returning top N recommendations from 2 to 10, all of the fusion approaches enhance the baseline CF method, which positively proves the usefulness of social relationship data especially when multiple recommendations are computed. It also indicates that the fusion via graph can boost the baseline significantly by up to 8%, demonstrating that the graph model is a more proper way to fuse explicit social relationships.
In this paper, we presented two principal methods to integrate explicit social relationships into traditional CF methods: the weighted-similarity fusion and the graph fusion. We demonstrated the effectiveness of social relationships in augmenting recommendations, and particularly that the graphbased fusion is more effective in bringing into play of the power of social data. To the best of our knowledge, the work is one of the first attempts to explore the effect of membership in addition to friendship, and to fuse both of them based on random walk graph model with collaborative filtering (CF) systems.
For the next step, we are interested in further exploring
the impact of social relationships on recommender systems
from three aspects: one is to explore other potential
relationships, such as the relation between items and
associated groups, other social relationships besides friendship
and membership, such as the reporting chain in a company,
to see how to model and utilize these data in order to make
better recommendations; another direction is to explore how
to enhance Random Walk model so as to handle
heterogeneous data in a more fine-grained way, based on the method
proposed in [
We thank Lawrence Bergman of IBM T.J. Watson Research Center for his generous help and valuable comments on this work. 7.