Exploiting Local and Global Social Context for Recommendation

1 Introduction

With the increasing amount of information available, it becomes difficult for online users to find relevant information. Recommender systems, attempting to tackle the information overload problem by suggesting to online users the information that is potentially of interests, attract more and more attention in recent years [Sarwar et al., 2001; Golbeck, 2006; Massa and Avesani, 2007; Koren, 2009]. Such systems are widely implemented in various domains including product recommendation at Amazon 1 and movie recommendation at Netflix 2 .

The pervasive usage of social media allows users to participate in online activities which produce a large amount of social relations such as trust relations in Epinions 3 . Social relations provide an independent source of information about users beyond rating information. Social correlation theories such as homophily [Miller McPherson and Cook, 2001] and social influence [Marsden and Friedkin, 1993] indicate that there are correlations between two socially connected users, which can potentially be used to exploit social relations for recommender systems. The availability of social relations presents opportunities for traditional recommender systems.

1 http://www.amazon.com/

2 http://www.netflix.com

3 http://www.epinions.com

Social relations can be viewed from different perspectives. An important classification of views of social relations is from local and global perspectives [Massa, 2007]. The former reveals the correlations among the user and his/her neighborhood while the latter reveals the reputation of the user in the whole social network. Users in the physical world are likely to ask for suggestions from their local friends while they also tend to seek suggestions from users with high global reputations, indicating both local and global views of social relations can be potentially exploited to improve the performance of online recommender systems.

There is recent work exploiting the local perspective of social relations for online recommender systems [Ma et al., 2011; Jamali and Ester, 2010; Yang et al., 2011; Tang et al., 2012a; 2012b]. Exploiting local social context can reduce the number of cold-start users [Tang et al., 2012a; 2012b]; hence, it can improve recommendation performance [Golbeck, 2006; Ma et al., 2008; Jamali and Ester, 2009; Yang et al., 2011; Jiang et al., 2012]. Although the global perspective of social relations is widely exploited by various online applications such as identifying influential bloggers [Agarwal et al., 2008], ranking online content [Weng et al., 2010] and predicting trustworthiness of users [Massa, 2007], there is little work exploiting global social context for recommendation.

In this paper, we investigate how to exploit social relations from local and global perspectives in recommender systems and propose a novel framework taking advantage of both local and global social context for recommendation. Our contributions are summarized next.

• Introducing an alternative approach to exploit local social context and investigating its connections with existing representative approaches;
• Providing a principled way to exploit global social context for recommendation;
• Proposing a novel recommender system LOCABAL

which exploits local and global social context simultaneously for recommendation;

• Evaluating LOCABAL extensively using real-world datasets to understand the working of LOCABAL.

The rest of this paper is organized as follows. We introduce the details of our proposed framework LOCABAL in Section 2. In Section 3, we investigate the connections between our approach and existing approaches in terms of modeling local social context. We show empirical evaluation with discussion in Section 4. In Section 5, we present the conclusion with future work.

2 ARecommendation Framework with Local and Global Social Context

We first introduce notations used in this paper. Let U = {u1, u2, . . . , un} and V = {v1, v2, . . . , vm} be the sets of users and items respectively, where n is the number of users and m is the number of items. We assume that R ∈ Rn×m is the user-item rating matrix. If ui gives a rating to vj, Rij is the rating score, otherwise we employ 0 to represent the unknown rating from ui to vj, i.e., Rij = 0. Let O = {〈ui, vj〉|Rij ̸= 0} be the set of known ratings and T = {〈ui, vj〉|Rij = 0} be the set of unknown ratings. Users can establish social relations to each other. We use T ∈ Rn×n to denote user-user social relations where Tij = 1 if uj has a relation to ui and zero otherwise.

Before modeling social relations, we first introduce a stateof-the-art recommendation method based on matrix factorization as our basic model. Matrix factorization techniques have been widely employed for recommendation [Salakhutdinov and Mnih, 2008; Koren, 2008; Ma et al., 2011] and they assume that a few latent patterns influence user rating behaviors and perform a low-rank matrix factorization on the user-item rating matrix. Let ui ∈ RK and vj ∈ RK be the user preference vector for ui and item characteristic vector for vj respectively, where K is the number of latent factors. Matrix factorization based recommender systems solve the following problem,

where U = [u1, u2, . . . , un] ∈ RK×n and V = [v1, v2, . . . , vm] ∈ RK×m. The terms ‖U‖2F + ‖V‖2F are introduced to avoid over-fitting and the non-negative parameter λ is used to control the capability of U and V.

There are several nice properties of matrix factorization methods: (1) simple optimization methods such as gradient based methods can be employed to find a well-worked optimal solution; (2) it has a nice probabilistic interpretation with Gaussian noise [Salakhutdinov and Mnih, 2008]; and (3) it is very flexible and enables us to integrate side information such as local and global social context introduced in the following subsections.

2.1 Exploiting Local Social Context

The local perspective of social relations reveals the correlations between users and their neighborhoods. Social correlation theories such as homophily [Miller McPherson and Cook, 2001] and social influence [Marsden and Friedkin, 1993] pave a way for us to exploit local social context for recommendation. Homophily indicates that users with similar tastes are more likely to be socially connected, and social influence suggests that users that are socially connected are more likely to share similar tastes. However, the low cost of social relation formation can lead to social relations with heterogeneous strengths (e.g., weak ties and strong ties mixed together) [Xiang et al., 2010]. Since users with strong ties are more likely to share similar tastes than those with weak ties, treating all social relations equally is likely to lead to degradation in recommendation performance. Previous work demonstrated that exploiting social relations with equal weight cannot improve recommendation performance [Tang et al., 2012a]. These observations suggest that we should consider heterogeneous strengths when exploiting local social context for recommendation.

In this paper, we simply use the rating cosine similarity to measure the social relation strength, although there are other more sophisticated measures in [Xiang et al., 2010]. For the i-th user ui, we use Ni = {uk|T(i, k) = 1} to denote his/her neighborhood. Let S ∈ Rn×n be the trust relation representation matrix where Sik denotes the social relation strength between ui and uk.

For uk ∈ Ni, Sik is calculated as the cosine similarity between the rating vectors of ui and uk while for uk /∈ Ni, we set Sik to 0. Therefore, Sik can be formally defined as

According to social correlation theories, the user preferences of two socially connected users are correlated thus we define the term to capture the local social context as

In Eq. (3), for two socially connected users ui and uk, their preference vectors ui and uk are correlated through H controlled by their social strength Sik where H ∈ RK×K is the matrix to capture the user preference correlation. A large value of Sik, i.e., ui and uk with a strong connection, indicates that their preferences ui and uk should be tightly correlated via H, while a small value of Sik tells that ui and uk should be loosely correlated.

Eq.(3) can be rewritten to its matrix form as,

where ⊙ is the Hadamard product where (A⊙B)ij = Aij × Bij for any two matrices A and B with the same size.

There is recent work also exploiting local social context under the matrix factorization framework for recommendation [Ma et al., 2008; Jamali and Ester, 2010; Ma et al., 2011]. We will study the connections between the proposed approach and representative existing methods to capture local social context in Section 3.

2.2 Exploiting Global Social Context

The global perspective of social relations reveals the reputation of a user in the whole social network [Massa, 2007]. User reputation is a sort of status that gives additional powers and capabilities in the online system [Massa, 2007], arousing various online applications such as predicting trustworthiness of users [Massa, 2007], identifying influential bloggers [Agarwal et al., 2008], ranking online content [Weng et al., 2010] and finding high-quality reviews [Lu et al., 2010]. There are many algorithms to calculate the reputations of nodes in social networks according to their connections [Page et al., 1999; Kleinberg, 1999] and we adopt one of the most popular algorithms PageRank [Page et al., 1999] to compute the user reputation scores in this work. In detail, we first perform PageRank to rank users by exploiting the global perspective of social relations. We assume that ri ∈ [1, n] is the reputation ranking of ui where ri = 1 denotes that ui has the highest reputation in the whole social network. Then we define user reputation score wi as a function f of user reputation ranking ri. The following definition of f works well in this work:

where the function f limits the value of the reputation score wi within [0, 1] and is a decreasing function of ri, i.e., topranked users have high reputation scores.

In the physical world, user reputation plays an important role in recommendation and many companies employ people with high reputations to enhance consumers' awareness and understanding of their products. Seno and Lukas found that suggestions from people with high reputations positively affect a consumer's adoption of a brand [Seno and Lukas, 2007]. While in the online world, Massa found that ratings from users with high reputations are more likely to be trustworthy [Massa, 2007]. Therefore our solution to capture global social context is to weight the importance of user ratings according to their reputation scores as

where the importance of ratings from ui is controlled by her/his reputation score wi during the matrix factorization process. A large value of wi, indicating the high reputation of ui, will force u⊤i vj to tightly fit the rating Rij while u⊤i vj will loosely approximate Rij when wi is small.

Eq.(6) can be also rewritten to its matrix form as

where W ∈ Rn×m is constructed as,

2.3 Our Framework

In the above, we introduce our solutions to capture local and global social context mathematically. With these solutions, we propose a recommendation framework LOCABAL exploiting local and global social context simultaneously and the proposed framework is to solve the follow optimization problem

where the reputation score of ui wi in the first term is used to exploit global social context and local social context is captured by the second term. The parameter α is introduced to control the contribution from local social context.

We use J to denote the objective function in Eq. (9) and it can be rewritten to its matrix form as

A local minimum of the objective function J in Eq. (9) can be obtained through a gradient decent optimization method, which usually works well for recommender systems [Koren, 2008; 2009]. The detailed algorithm is shown in Algorithm 1.

Algorithm 1 The Proposed Social Recommendation Framework LOCABAL

Input: The rating information R, the social information T, the number of latent factors k and α

Output: The user preference matrix U and the item characteristic matrix V

• 1: Initialize U, V and H randomly
• 2: Construct S fromR and T
• 3: while Not convergent do
• 4: Calculate ∂J ∂U , ∂J ∂V and ∂J ∂H
• 5: Update U←Uγu ∂J ∂U
• 6: Update V←Vγv ∂J ∂V
• 7: Update H←Hγh ∂J ∂H
• 8: end while

In Algorithm 1, γu, γv and γh are learning steps, which are chosen to satisfy Goldstein Conditions [Nocedal and Wright, 1999]. After learning the user preference matrix U and the item characteristic matrix V via Algorithm 1, an unknown rating ˆRi′ j ′ from the user u′i to the item v′j will be predicted as ˆRi′ j ′ = u⊤i′ vj ′ .

3 Connections to Existing Approaches

Exploiting local social context under the matrix factorization framework for recommendation has attracted increasingly attention recently [Ma et al., 2008; Jamali and Ester, 2010; Ma et al., 2011]. Next we study the connections between our approach and two representative methods [Ma et al., 2008; 2011] w.r.t. capturing local social context. The purpose of this study is two-fold - to investigate their main differences, and to seek the unique properties of our proposed approach.

In [Ma et al., 2008], the local social context is captured as

where Z = {z1, z2, . . . , zn} ∈ RK×n is the factor-specific latent feature matrix [Ma et al., 2008]. The underlying assumption of this approach is that the i-th user ui should share the same user preference vector ui in the rating space and the social space, which is different from that of our method based on social correlation theories. We develop the following theorem considering their connections.

Theorem 3.1 Eq. (3) and Eq. (12) have the same form by factorizing zk into Huk

Proof By factorizing zk into Huk and plugging into Eq. (12), Eq. (3) and Eq. (12) are equivalent. □.

In [Ma et al., 2011], social regularization is defined to capture local social context as

the intuition of social regularization is that two users with social relations should share the same or similar preferences. Therefore social regularization forces the preference vectors of two connected users to be close to each other, which is controlled by their social strength and we also develop the following theorem to investigate their connections.

Theorem 3.2 Eq. (3) and Eq. (13) can be rewritten into the following form as

where for Eq. (3), A, Bk, and Ci are defined as,

while for Eq. (13), A, Bk, and Ci are defined as,

Proof By removing constants, Eq. (3) can be rewritten as

It is easy to verify that u⊤i Huk = u⊤k H⊤ui, and then we have

By constructing A, Bk, and Ci according to Eq. (15), we can demonstrate that Eq. (3) can be rewritten into the form of Eq. (14). Similarly we can verify that Eq. (13) has the form of Eq. (14) by constructing A, Bk, and Ci based on Eq. (16), which completes the proof. □

The above theorems not only suggest that our proposed approach is different from existing ones but also indicate that it can be considered as a bridge to connect existing approaches.

4 Experiments

In this section, we conduct experiments to answer the following questions: (1) how does the proposed framework LOCABAL perform compared to the state-of-the-art recommender systems? and (2) how do local and global social context contribute to the proposed framework. After introducing experimental settings, we compare the performance of different recommender systems and then investigate the effects of local and global social context on the proposed framework, followed by parameter selection for LOCABAL.

4.1 Experimental Settings

Two datasets are chosen to evaluate our proposed framework, i.e., Epinions and Ciao 4 , which are publicly available from the first author's homepage 5 . Users in Epinions and Ciao can rate products with scores from 1 to 5 and they can also establish social relations (i.e., trust relations) with others. Some statistics of these two datasets are presented in Table 1. The rating data is very sparse for both Epinions and Ciao. We compute the number of ratings from each user and the distribution suggests a power-law-like distribution - a few users contribute a large number of ratings while most users contribute few ratings.

For each dataset, we choose x% as the training set and the remaining 1 - x% as the testing set where x is varied as {50, 70, 90} in this paper. Two popular metrics, the Root Mean Square Error (RMSE) and the Mean Absolute Error (MAE), are chosen to evaluate the prediction performance.

4 http://www.ciao.co.uk/

5 http://www.public.asu.edu/∼jtang20/datasetcode/truststudy.htm

The metric RMSE is defined as

where T is the set of ratings in the testing set, |T | is the size of T and ˆRij is the predicted rating from ui to vj . The metric MAE is defined as

A smaller RMSE or MAE value means better performance. Note that previous work demonstrated that small improvement in RMSE or MAE terms can have a significant impact on the quality of the top-few recommendation [Koren, 2008].

4.2 Comparisons of Different Recommender Systems

We compare the proposed framework LOCABAL with the following representative recommender systems:

MF: This method performs matrix factorization on the user-item rating matrix as shown in Eq. (1) [Salakhutdinov and Mnih, 2008]. It only utilizes rating information.

SoRec: This method is based on matrix factorization and exploits local social context by performing a factorization on the social matrix as shown in Eq. (12) [Ma et al., 2008].

SoReg: this method is also based on matrix factorization and defines social regularization to capture local social context as shown in Eq. (13) [Ma et al., 2011].

Note that we use cross-validation to determine parameters for all baseline methods. For LOCABAL, α is set to 0.7 and 0.5 for Ciao and Epinions respectively and the number of latent factors K is set to 10 for both datasets. More details about parameter selection for LOCABAL will be discussed later. According to empirical experience, λ is set to 1. The comparison results are demonstrated in Table 2 and we have the following observations,

• Exploiting social context can significantly improve recommendation performance in terms of both RMSE and MAE. For example, SoRec, SoReg and LOCABAL obtain 3.36%, 5.56%, 7.03% relative improvement in terms of MAE in Epinions with 50% as the training set respectively, compared toMF.
• Our proposed framework LOCABAL always obtains the best performance. Compared to the second best performance of baseline methods, on average, LOCABAL gains 0.023 and 0.0186 absolute RMSE improvement in Ciao and Epinions, respectively. The major reason is that LOCABAL exploits local and global social context simultaneously. More details about the effects of these two types of social context on the performance of LOCABAL will be discussed in the following subsection.

With these observations, we can draw an answer to the first question - our proposed framework outperforms the state-ofthe-art recommender systems by exploiting local and global social context simultaneously.

(a) MAE

4.3 The Impact of Global and Local Social Context on LOCABAL

The experimental results in the above subsection show that our proposed framework LOCABAL outperforms the stateof-the-art recommender systems. In this subsection, we investigate the effects of local and global social context on the proposed framework LOCABAL to answer the second question. In detail, we eliminate the effect of global and local social context systematically from LOCABAL by defining the following variants of LOCABAL,

• LOCABAL\global - Eliminating the effect of global social context by setting wi = 1 when Rij ̸= 0 in Eq. (9).
• LOCABAL\local - Eliminating the effect of local social context by setting α = 0 in Eq. (9).
• LOCABAL\global\local - Eliminating the effects of both local and global social context by setting α = 0 and setting wi = 1 when Rij ̸= 0 in Eq. (9). Actually this variant is the MF recommendation framework as defined in Eq. (1).

The comparison results in Epinions are shown in Figures 1(a) and 1(b) for MAE and RMSE, respectively. Note that we only show the results in Epinions since we has similar observations in Ciao. When eliminating the effect of local social context from the proposed framework, the performance of LOCABAL\global degrades. We have the similar observation for LOCABAL\local when eliminating the effect of global social context. For example, compared to LOCABAL, on average, LOCABAL\global and LOCABAL\local have 3.46% and 1.83% relative performance reduction in terms of RMSE, respectively. When eliminating the effects of both global and local social context, LOCABAL\global\local obtains worse performance than both LOCABAL\global and LOCABAL\local, suggesting that local and global social context contain complementary information to each other for recommendation.

With the evidence from Figure 1, we can answer the second question - both local and global social context can help improve the recommendation performance.

4.4 Parameter Selection

There is an important parameter for the proposed framework LOCABAL α, controlling the contribution from local social context. In this subsection, we investigate how changes of α affect the performance of LOCABAL. We vary the value of α as {0,1e-3,1e-2,0.1,0.3,0.5,0.7,1,10}. The results in Epinions w.r.t. RMSE and MAE are demonstrated in Figures 2(a) and 2(b), respectively. Since we have similar observations in Ciao, we only show the results in Epinions to save space.

With increasing values of α, we put more and more weight on local social context and we have the following observations: (1) the performance first increases, suggesting that integrating local social context can improve the recommendation performance; (2) when α is from 0.3 to 0.7, the performance is not sensitive to α; and (3) when α is from 1 to 10, the performance reduces dramatically. A large value of α will lead to social relations dominating the user preference learning process in Eq. (9), resulting in inaccurate estimates of the user preference matrix U and the item characteristic matrix V. For example when α → ∞, the user preference matrix U is only learnt from social relations and the item characteristic matrix V = 0

5 Conclusion and FutureWork

The availability of social relations presents both challenges and opportunities for traditional recommender systems. In this paper, we investigate how to exploit local and global social context for recommendation. To capture local social context, we force that the user preferences of two socially connected users are correlated as suggested by social correlation theories and we also study the connections between our proposed approach and existing approaches. Ratings from users with high reputations are more likely to be trustworthy; therefore, to capture global social context, we use user reputation scores to weight the importance of their ratings. With these solutions, we propose a framework LOCABAL to integrate local and global social context for recommendation. Experimental results on real-world data sets show that the proposed framework LOCABAL outperforms representative social recommender systems. Further experiments are conducted to understand the working of LOCABAL.

There are several directions to investigate in the future. First, as user preferences and social relations might evolve, incorporating temporal information into social recommender systems will be an interesting direction [Tang et al., 2012b]. Second, most existing social recommender systems exploit only positive social relations between users such as friendships and trust relations. However users can also have negative social relations such as distrust and dislike, then we can investigate the effect of negative social relations on social recommender systems [Yang et al., 2012].

Acknowledgments

We thank the anonymous reviewers for their useful comments. The work is, in part, supported by ARO (#025071) and NSF (#IIS-1217466).