Celebrity Recommendation with Collaborative Social Topic Regression

1 Introduction

Social networks have become one of the symbols of today's Internet [Ahmad, 2011]. With the explosive growth of the number of users in social network websites, the social network itself becomes a new media to propagate news, ideas and opinions. Nowadays, more and more users regard social networks as a powerful media in which they can gain the newest ideas and opinions from authorities and elites [Friedkin, 2006; Kwak et al., 2010]. The public are increasingly interested in the celebrities and famous organizations. From figure 1, which is analyzed statistically using the dataset from Twitter 1 and Tencent Weibo 2 , we can observe that more and more people are following celebrities and using social networks as a media. Though user behaviors of these two microblogs are different, we observe that a large number of users tend to follow celebrities in common, where nearly 40% users in Twitter and 90% users in Tencent Weibo prefer following celebrities. Celebrities and organizations have already recognized the eagerness of public to gain newest information which they are interested in and signed up their own accounts to broadcast their opinions in succession.

Though those celebrities are a small part of users in a social network, the quantity of them can still reach a relatively large order of magnitude. General users now face a big problem: how to find those celebrities they truly interested in to follow from massive candidates [Zimmerman et al., 2002]. To solve this problem, the door to the employment of recommendation methods is opened. However, since we can only observe the user follow actions from microblogs, and unfollow does not mean not interested, conventional collaborative filtering techniques [Koren et al., 2009; Su and Khoshgoftaar, 2009] can not be directly applied to address such problem. Inspired by one-class collaborative filtering techniques [Hu et al., 2008], we utilize user following actions as positive samples with high confidence and no following actions as negative samples with low confidence.

1 http://an.kaist.ac.kr/traces/WWW2010.html

2 http://www.kddcup2012.org/c/kddcup2012-track1

Why are so many users interested in celebrities? The reason may be that most users are not only interested in those celebrities themselves, but also the interests behind those celebrities. In this paper, we propose to use the relationships between celebrities as a relationship network of interests from users. And we utilize the relationships between celebrities to boost the performance of recommendation. For example, the number of connections between singers is much larger than that between singers and entrepreneurs. That means one singer may have more common interests with another singer than entrepreneurs. Moreover, the number of connections between different groups varies largely, e.g., number of connections between sports stars and singers is far more than the number between singers and entrepreneurs. So it is necessary to analyze the structure of the social network among celebrities. Unlike analysis of common user's social network, which devotes giant efficiency cost due to the huge number of users, analyzing celebrity's social network will not suffer from such problem because of the relatively small quantity of celebrities. The two kinds of social networks have several great differences: (1) General user's social network are huge and sparse, but celebrity's social network is small and compact; (2) To some extent, the social network of celebrities can be viewed as the relationships among different kinds of interests, general user's social network may mainly represents friendship; and (3) Celebrities are the mainly followed groups on social network, but general users are not. To the best of our knowledge, this is the first work which aims at exploring the celebrities' social network to improve the performance of recommendation system.

We further leverage the semantic analysis power [Blei et al., 2003] to solve hard explainability problem exsiting in the context of matrix factorization. We collect abundant personal descriptions for each celebrity fromWikipedia, LinkedIn and their personal websites etc. A model which combines social network analysis and semantic analysis to jointly learn the user's interests is proposed. More specifically, we used a hierarchical Bayesian model to combine topic model with matrix factorization for both celebrities social network and user interests matrix.

Our contributions are as follows: We are the first to explore whether celebrity's social network has an effect on improving the performance and efficiency of recommending celebrities. We propose the Collaborative Social Topic Regression (CSTR), a novel Bayesian hierarchical model which incorporates latent factor model on both celebritiy side and user side with topic model. Our method provides a single unified framework to handle both cold and warm-start scenarios. We provide a scalable, linearly complexity model fitting procedure through coordinate ascent optimization. We test our method on two real-world social network datasets from Twitter and Tencent Weibo. The experiment results show that our method significantly outperforms the existing and commonly used methods, especially for cold-start situations. And our method captures user interests more accurately with better interpretability. We also studied user behaviours difference between Twitter and Tencent Weibo.

2 RelatedWork

Although our proposed CSTR is the first one which aims at jointly modeling users' interests, celebrity social network and their semantic information, our model is related to previous research in the following areas.

Latent Factor Models: Latent factor models which are used in the context of recommendation systems have been extensively studied. PMF and BPMF [Salakhutdinov and Mnih, 2008b; 2008a] incorporate the latent factor models into a Bayesian framework. Some feature based latent factor models are also proposed in previous works, such as RLFM [Agarwal and Chen, 2009] and Factorization Machine [Rendle, 2010]. However, these methods can not be directly applied to the situation in which ratings have only two states : observed or not. [Hu et al., 2008] addressed such problem via considering unobserved data as negative samples with low confidence. In our situation, those unfollow actions are regarded as unobserved data and modeled as negative samples with low confidence.

Latent Factor Models meet Topic Models: Topic models are used to discover a set of "topics" from a large collection of documents, where a topic is a distribution over terms. The representative works include PLSA [Hofmann, 1999] and LDA [Blei et al., 2003]. For both latent factor models and topic models, they propose to reduce original data into latent spaces. Since a latent factor can be treated as a realvalue variable and topics fall into a simplex, there are some works to link them together. CTM-PPMF and LDA-MPMF [Shan and Banerjee, 2010] equal item latent vector and topic proportion vector by Logistic transformation. fLDA [Agarwal and Chen, 2010] uses topic assignments to contribute the rating directly. CTR [Wang and Blei, 2011] uses topic vector to control the prior distribution for item latent factor. Our proposed model CSTR can be seen as an extention of CTR. If not considering social network of celebrities, CSTR is equivalent to CTR. We use CTR as a baseline to verify whether celebrity's social network is useful or not.

Latent Factor Models meet social network: Recently, some works have studied the effectiveness of social networks of general users to better address general user's interest [Purushotham et al., 2012; Ma et al., 2008; 2011; Yang et al., 2011]. [Shen and Jin, 2012] incorporated heterogeneity and diversity of user social relationships. [Cheng et al., 2012] utilizes user social relationships to recommend locations. The most relevant work to ours is [Purushotham et al., 2012], which fuses LDA with social matrix factorization to obtain a consistent and compact feature representation. This work is different from ours since they only considered the situation when topic model plays a part in user interest matrix factorization, however we let topic model functioned not only on user ratings but also on celebrity social network, which will gain better interpretability and higher performance of recommendation. As discussed in the previous section, social network of general users and that of celebrities are quite different. So, in this work we only consider the social networks of celebrities because we mainly focus on how social network of celebrities would have an effect on the task for celebrity recommendation.

3 Models

3.1 Notations

The latent factors for user i and celebrity j are denoted by ui and vj respectively. In celebrities' social network, the extra social latent factor for celebrity m is denoted by sm. Written in matrix form, the three latent factor matrices are U ∈ RK×I , V ∈ RK×J and S ∈ RK×J where K is the dimensionality of the latent space, I is the number of users and J is the number of celebrities. Each latent factor is a column in the corresponding matrix. Throughout this section we use i to index users, j and m to index celebrities. We use matrix R to represent the user-celebrity follow table, rij = 1 if user i followed celebrity j, and rij = 0 otherwise. The social network among celebrities is a directed graph Q = (V, E). The edge set E is represented as matrix Q, where qmj = 1 when there is an edge from m to j and qmj = 0 otherwise. Description of celebrity j is denoted by word sequence Wj .

3.2 Model Details

In social networks, a user following a celebrity means the user is interested in the celebrity and his/her work. On the other hand, when a user is not following a celebrity, it does not necessarily mean the user is not interested in the celebrity, because it is very likely that the user is simply not aware of that celebrity or the user might be a newly registered user. To express this asymmetry, we model the conditional distribution of rij given ui and vj as a Gaussian N(rij|u⊤i vj , c-1 ij ), and the precision parameter cij is asymmetric for the two cases

According to our analysis, we set a > b to express our confidence about a 'follow' action and uncertainty when the user is not following the celebrity. The probability of the full follow table R given U and V is assumed to be factorial, p(R|U, V ) = ∏Ii=1 ∏Jj=1 N (rij |u⊤i vj , c-1 ij ).

We place zero-mean spherical Gaussian prior on ui following [Dueck and Frey, 2004; Salakhutdinov and Mnih, 2008b] so p(U|λu) = ∏Ii=1 N(ui|0, λ-1 u IK), where IK ∈ RK×K is the identity matrix. As did in CTR, we place θ-mean Gaussian prior on vj to enable the topic model to regulate the celebrity latent factors. We have p(V |θ, λv) = ∏Jj=1 N (vj |θj , λ-1 v IK). λu and λv are the precision of the corresponding Gaussian distribution. θj is the topic proportion vector generated by the topic model based on the text descriptions we collected for celebrity j.

The likelihood of the text descriptions under the topic model is a product of likelihood of each Wj , p(W, θ|α, β) = ∏Jj=1 ∏Nj n=1 ln ∑Kk=1 θjkβk,wjn , which is the same as in LDA [Blei et al., 2003]. We fix the hyperparameter α = 1 to keep the computation simple.

Now we turn to the model for celebrities' social network, represented by social matrix Q. The model is similar to the model for R, and V is again used as a latent factor matrix, so that the social network can help regularize V . We model the conditional distribution of qmj as a Gaussian N (qmj |s⊤mvj , d-1 mj ). dmj is the precision parameter, which again can represent asymmetry in our confidence for qmj . We distinguish three cases here: (1) qmj = 1 then we should be very confident that celebrity m is interested in j; (2) qmj = 0 but qjm = 1, then we get modest confidence; (3) both qmj and qjm are 0, then our confidence is low. Therefore we have the following definition for dmj

where we enforce e > f > g to represent our different confidence for different cases. Then p(Q|V, S) = ∏Jj=1 ∏Jm=1 N (qmj |s⊤mvj , d-1 mj ), and we also place a zero mean Gaussian prior on celebrity social latent factor sm, so that p(S|λs) = ∏Jm=1 N (sm|0, λ-1 s IK ).

Finally, the joint likelihood of data, i.e. R, Q and W, and the latent factors U, V, S and θ under the full model is

3.3 Parameter Learning and Optimization

Given a training data set, we want to find the Maximum a Posteriori (MAP) estimate of U, V, S, θ, so we can use U and V to predict the missing entries in R and use the predictions to do recommendation. In our model, finding the MAP is equivalent to maximize the log likelihood

Algorithm 1 Coordinate Ascent Optimization Algorithm

Require:

Ensure:

U, V , S, θ1:J maximize p(U, V, S, θ1:J | R, Q,W).

1: Give matrix V a warm start, V ← θ1:J .

2: while not convergent do

3: X ←V V

⊤

for i=0 to I do

A ← b

·

X + λuI + ∑j∈{rij=1} (a

ui ← A-1 ∑j∈{rij=1} a

4:

5:

6:

• 7: for m=1 toMdo

·

vj

A ← A + ∑j∈{qmj=0,qjm=1} (f

11: Y←b UU

⊤ + g SS⊤ + λvI

for j=1 to J do

A ← Y + ∑i∈{rij =1} (a

-

A ← A + ∑m∈{qmj =1} (e b) ·

uiu⊤i

-

g) ·

sms⊤m

A ← A + ∑m∈{qmj =0,qjm=1} (f

x ←λvθj + ∑i∈{rij=1} a

12:

13:

14:

15:

16:

17:

vj ← A-1

x

• 18: update θ via simplex projection gradient
• 19: update β using LDAM-step [optional]

·

sm

where C is a constant. We optimize this function using coordinate ascent which alternatively optimizes latent factor variables ui, vj , sm and the simplex variables θj which is similar to [Wang and Blei, 2011].

We directly set the derivative of L with respect to ui, vj and sm to zero. Then we obtain

where Ci ∈ RJ×J is a diagonal matrix with cij as its diagonal elements and Ri = (ri1, ..., riJ )⊤ is the record of user i in the follow table R, Cj ∈ RI×I and Rj ∈ RI are similarly defined for celebrity j. Dm ∈ RJ×J is a diagonal matrix with dmj as its diagonal elements and Qm = (qm1, ..., qmJ )⊤, Dj ∈ RJ×J andQj ∈ RJ×1 are similarly defined.

Iterating through the update equations (3), (4) and (5), we can see that the new U and S latent factors will depend on the celebrity latent factor matrix V . Based on current U, S and θ, we can compute the new V . Note that the topic proportion matrix θ affects both U and S through V , and the parameter λv controls how much we trust the topic model.

Given U, V and S, we update θ using projected gradient ascent [Bertsekas, 1999]. After a full iteration of coordinate ascent, we update β using the variational M-step developed for LDA [Blei et al., 2003].

The detailed algorithm is described in Algorithm 1.

Using the learned parameters U ∗ , V ∗ , S∗ , θ∗ 1:K and β∗ , we make predictions by r∗ ij ≈ (u∗i )⊤v∗ j .

·

-

g) ·

b) ·

vj v⊤

j

j

sms⊤m

ui + ∑m∈{qmj=1} e

·

·

-

-

3.4 Computational Complexity

The computational bottleneck here is computing UCjU ⊤, SDjS⊤, VCiV ⊤ and VDmV ⊤. The naive calculation requires time O(K2I) and O(K2J ) for each user and celebrity respectively. Inspired by [Hu et al., 2008], we can rewrite UCjU ⊤ as

where I is the corresponding identity matrix. Note that we can pre-compute bUU ⊤, and (Cj -bI) has only Ia non-zeros elements, where Ia represents the number of general users who followed the celebrity j, and empirically Ia ≪ I. This sparsity can significantly speed up computation. For other matrix products, we can use similar tricks.

The final time complexity for one full iteration of coordinate ascent is O(2KI( K2 + E uc)), where E uc is the average number of celebrities a user followed. In practice, each user would only follow a limited number of celebrities, so Euc is small. Therefore this new algorithm is significantly faster than the naive algorithm.

We can see that three factors determine the complexity of our algorithm: 1) the dimensionality of the latent space; 2) the number of users in the network; 3) sparsity of the network. Both 1 and 3 are independent of 2, so our algorithm scales linearly with the number of general users in the network.

4 Experiments

4.1 Experiment Settings

We used the social network from Twitter and Tencent Weibo. User following records and celebrity social network are extracted. Text descriptions of 916 celebrities from Twitter are collected from Wikipedia, LinkedIn and their personal websites by searching with their names and short descriptions. For Tencent Weibo, descriptions are given in the dataset. To show the effectiveness of celebrity social network, we used the full celebrity network and only sampled a subset of 10,000 users from the full set of users. When sampling, users who follow less than 5 celebrities are not considered, because these data are very noisy and of high variance.

Twitter: 916 celebrities and 10,000 users. 96,929 user follow actions are observed, density of user actions matrix is about 1.06%. 45406 edges exist in celebrity social network, density of celebrity matrix is about 5.41%.

Tencent Weibo: 4394 celebrities and 10,000 users. 278,825 user follow actions are observed, density of user actions matirx is about 0.63%. 154,317 edges exist in celebrity social network, density of celebrity matrix is about 0.80%.

Evaluation Metrics: Recall and Average Precision(AP) are used, (1)Recall@N: follow number in top-N list total follow number , where follow number means the number of celebrities a user followed; (2)AP@N: ∑Nn=1 precision(n)∗rel(n) total follow number [Manning et al., 2008], where rel(n) is a 0-1 binary variable which indicates follow or not follow action. Both Recall and AP are averaged across users. They measure the inclusiveness and ranking performance of recommendation algorithms respectively.

In the experiments, CTR, social neighborhood (SN) and most popular (MP) methods are used as baselines. SN recommends target user the celebrities who have the most connections with the ones followed by target user. MP recommends users those celebrities who have the largest number of followers. Both Recall and AP are averaged over five random repeats in experiments. We used a parameter tuning strategy that does grid search on one parameter while fixing other parameters, which is done in turn for each parameter.

4.2 Warm-Start Situation

For each user we evenly split their records into 3 folds, and iteratively use each fold as the test set and the others as the training set. The results we report here is the average over 3 folds. Using the tuning strategy described in Section 4.1, we set λu = λv = 0.01, a = 1, b = 0.1 which works well for both CTR and CSTR on both datasets. For CSTR, extra parameters are set as K = 10, e = 10, f = 2, g = 1 on Twitter dataset and K = 100, e = 1, f = 0.2, g = 0.1 on Tencent Weibo dataset using the same tuning strategy. Figure 3 and Table 1 shows that CSTR model outperformed the other models consistently both in Twitter and Tencent Weibo. We believe the performance gain of CSTR over CTR comes from the model of celebrity social networks. Note that on Twitter data set the simple baseline MP can sometimes be even better than CTR. This shows that the celebrity social network do provide us important information about user's interests.

Then we studied how parameter λv affects the recommendation effectiveness. λv is the parameter which controls the impact of topic model. For CTR, we observe that when increasing λv, recall would increase and then fall down on both datasets. For CSTR, as impact of topic model becomes larger (λv = 100), performance starts to decrease. Though it seems that topic model contribute little to performance directly, it does contribute to user interests mining via affecting celebrity and user latent factors and it can bring better interpretability as shown in section 4.5.

4.3 Cold-Start for Recommending NewCelebrities

After a new celebrity starts to use a social network service, it usually takes a long time for those interested general users to get connected to him/her because of the slow process of information propagation in sparsely connected social networks. We call this a "cold-start" situation. It's valuable to recommend these celebrities to the public so that they can get involved in the social network faster. We tested the performance of the proposed CSTR model under this situation, where we preserve the new celebrities' connections to other celebrities, which are likely to come from the offline friend circle; but we don't use any follow records from general users, to simulate the cold-start setting. All celebrities are evenly grouped into 3 folds. We iteratively use each fold as test set and the others as training set, therefore at least one third of the celebrities are not in the training set, and the user follow records for them are not available during training. The final results are averaged over 3 folds.

In this cold-start situation, it is impossible to use history record of user follow data. So it is necessary to increase the impact of social factors. To tune the e, f and g parameters for the social factors, we choose a base value of the three to be e = 1, f = 0.2, g = 0.1 respectively which works well in the warm-start situation, then scale them up by a factor of 10 every time. The relationship between the scale factor and the performance of the model is shown in Figure 6. We found e = 100000, f = 20000, g = 10000 to work well, which matches our intuition that we should put more weight on the social factors. Figure 5 shows that our model CSTR significantly outperforms neighborhood and CTR model. From Figure 5(a), recall@20 for CSTR on Twitter is 23.68% and for neighborhood method is 13.73%, an improvement of 72%. From Figure 5(b), recall@20 for CSTR on Tencent Weibo is 27.8% and for neighborhood method is 17.33%, an improvement of 60%. CTR performs poorly in this situation. For ranking metric AP, CSTR also has the best performance, which improving 136% and 121% over SN on Twitter and Tencent Weibo respectively, as shown in Table 1. The results show the effectiveness of celebrities network to help improve recommendation performance, and social matrix factorization performs better than the neighborhood method.

4.4 Performance for Different User Groups

We wanted to explore the effectiveness for recommending celebrities to different users who have different number of followees. We divided the users into 7 groups according to the number of celebrities they followed. For each group, we sampled 4000 users from the whole social network, and we evaluate the performance in a warm-start setting. From Figure 7(a) and 7(b), we found that on Twitter, the user group that has followed 66-80 celebrities are more likely to accept the recommendations, while on Tencent Weibo it is the group that has followed 21-35 celebrities. The willingness to follow celebrities declines as users follow more celebrities. After users on Tencent Weibo have already followed more than 50 celebrities, their eagerness to follow new celebrities falls down quickly. However, users on Twitter tend to follow more celebrities. It shows that the behavior of American and Chinese users on social networks are quite different.

4.5 User Interests Exploration

We study how CSTR gives better interpretability and improves recommendation performance at the same time on Twitter dataset. Warm-start settings are used here. Top matched topics of one user can be found by ranking the factors of his latent feature vector ui. Table 2 shows a representative user on Twitter. CTR believes this user likes news, technology and business. Then CTR tries to recommend the users some celebrities related to news and sociology, such as Barack Obama and CNN Breaking News. But this user do not follow any of them. On the other side, CSTR captures that this user likes film, music and reading. CSTR recommends celebrities this user really likes, Warren Ellis who is the writer of Gun Machine and David Wain who is a movie director. In a higher level view, CTR recommends this user 2 actors, a singer, a politician, 2 entrepreneurs and 2 medias, however CSTR focuses on recommending actors and singers to this user, where 2 writers, 4 actors, 1 singerwriter and 1 tv host are recommended. Obviously this user is prone to accept the recommendations from CSTR. From this case, we can conclude that user interest is regularized through celebrity social network. It shows that CSTR has advantages over CTR, that is CSTR can propagate topics through both celebrity and user interest matrix, which can capture users interest more precisely and gain better interpretability.

5 Conclusions and FutureWork

In this paper, we explore how to recommend celebrities to general users in the context of social network. We present a novel celebrity recommendation framework fusing matrix factorization for user following actions with matrix factorization for social network of celebrities, which are both affected by a unified topic model framework. The experiment results show that our approach outperforms the state-of-art algorithms for both warm start and cold start situations and captures users' interest more precisely. In the future, nonparametric model can be considered to jointly model the celebrity social network and user follow action records.

Acknowledgments

The work was supported by National Natural Science Foundation of China (60973103, 90924003).