Learning User Dependencies for Recommendation

1 Introduction

Recommender systems have been widely used to help us discover useful information. For example, on e-commerce websites, e.g., Amazon, recommender systems predict users' preferences on products based on their past purchasing behaviors and then recommend a user a list of interesting products she may prefer. For a recommender system, the most critical factor is the prediction accuracy of users' preferences. In practice, the most successful prediction methods are collaborative filtering based approaches [Su and Khoshgoftaar, 2009]. Especially, matrix factorization has been widely applied in different recommendation tasks [Koren et al., 2009; Liu et al., 2013; Hu et al., 2014; Liu et al., 2014; 2015].

The recent rapid developments of online social networking services (e.g., Facebook and Twitter) motivate the emergences of social recommender systems that exploit users' online social friendships for recommendation [Yang et al., 2014]. The social recommender systems usually assume that a user has similar interests with her social friends. Although the recommendation accuracy can usually be improved, there do not exist strong connections between the online friendship and the similarity of users' interests [Ma, 2014]. Because there are different categories of social networking friends in online social networks, e.g., school friends, workrelated friends, and friends sharing same interests or activities [Zhang et al., 2013]. The tastes of a user's online friends usually vary significantly. In different scenarios, a user tends to trust recommendations from different subsets of her online social friends. Hence, the key to success for a social recommender system is to exploit the most appropriate dependencies between users for a specific recommendation task.

∗Corresponding author

Moreover, existing social recommender systems are usually developed based on users' explicit social relationships, e.g., trust relationships [Jamali and Ester, 2010; Fang et al., 2014; Mei et al., 2014; Guo et al., 2015] and online social friendships [Ma et al., 2011; Yang et al., 2012; Tang et al., 2013; Hu et al., 2015]. However, users' explicit social relationships may be unavailable in many application scenarios. This limits the application of traditional social recommendation approaches. To remedy this problem, the underlying implicit social relationships between users that have most similar or dissimilar behaviors have also been exploited for improving recommendation accuracy [Ma, 2013]. In these studies, users' dependencies adopted for recommendation are pre-defined based on users' explicit or implicit social relationships.

Differing from previous work, this paper proposes a novel recommendation method, namely probabilistic relational matrix factorization (PRMF), which aims to automatically learn the user dependencies to improve the recommendation accuracy. The proposed method can be applied to the recommendation scenarios with or without users' explicit social relationships. In PRMF, the user latent feature matrix is assumed to follow a matrix variate normal (MVN) distribution [Gupta and Nagar, 1999], where the row precision matrix models the dependencies between different rows (i.e., users). Therefore, both positive and negative dependencies between users can be learned by fitting the MVN distribution. This is motivated by the success of applying the MVN distribution to model the task relationships for multi-task learning [Zhang and Yeung, 2010]. The optimization problem of PRMF is solved by an alternating algorithm based on the stochastic gradient descent (SGD) [Koren et al., 2009] and alternating direction method of multipliers (ADMM) [Boyd et al., 2011] methods. Moreover, we extensively evaluated PRMF and five baseline methods on four real datasets. Empirical experiments showed that PRMF consistently achieved the best recommendation accuracy on all datasets, in terms of root-mean-square error (RMSE) and mean absolute error (MAE).

2 RelatedWork and Background

This section first introduces some background about probabilistic matrix factorization (PMF) [Mnih and Salakhutdinov, 2007] and then reviews social recommendation methods.

2.1 Probabilistic Matrix Factorization

For the recommendation problem with m users {ui}mi=1 and n items {vj}nj=1 , the matrix factorization models map users and items into a shared latent space, which has a low dimensionality d ≪ min(m, n). For each user ui, her latent features are represented by a latent vector Ui ∈ R1×d . Similarly, the latent features of the item vj are described by a latent vector Vj ∈ R1×d . In PMF, users' ratings on items are assumed to follow a Gaussian distribution as follows:

where R ∈ Rm×n is the matrix denoting users' ratings on items; U ∈ Rm×d and V ∈ Rn×d denote the latent features of all users and items, respectively; σ2 is the variance of the Gaussian distribution; Wij is an indicator variable. If ui has rated vj, Wij = 1; otherwise, Wij = 0. In addition, we also place zero-mean spherical Gaussian priors on U and V as:

where I is the identity matrix, σ2u and σ2 v are the variance parameters. Through the Bayesian inference, we have

The model parameters (i.e., U and V ) can be learned via maximizing the log-posterior in Eq. (3), which is equivalent to solving the following problem:

where W ∈ Rm×n is the indicator matrix, and Wij is the (i, j) entry of W. In Eq. (4), ⊙ denotes the Hadamard product of two matrices, λu = σ2 /σ2u , λv = σ2 /σ2 v , and ‖·‖F denotes the Frobenius norm of a matrix.

2.2 Social RecommendationMethods

In recent years, lots of social recommendation approaches have been proposed [Yang et al., 2014]. The Social Regularization (SR) [Ma et al., 2011] is one of the most representative methods. The SR method was implemented by matrix factorization framework. It assumed that a user may have similar interests with her social friends, and thus the learned latent features of a user and that of her social friends should be similar. As a user tended to trust different subsets of her social friends regarding with different domains, the circle-based recommendation (CircleCon) models proposed in [Yang et al., 2012] considered domain-specific trust circles for recommendation. In [Tang et al., 2013], both the local and global social contexts were exploited for recommendation. Recently, the SR model was extended to exploit users' implicit social relationships for recommendation [Ma, 2013]. The implicit social relationships were defined between a user and other users that had most similar or dissimilar rating behaviors with her. In [Fang et al., 2014], users' social relationships were studied from four different trust aspects for recommendation. In [Li et al., 2015], SR was also extended to exploit the community structure of users' social networks to improve recommendation accuracy. Moreover, the recent work [Guo et al., 2015] developed the TrustSVD model, which incorporated both user and item biases, as well as the explicit and implicit influences from rated items and trusted users for recommendation. In [Hu et al., 2015], a recommendation framework named MR3 was proposed to jointly model users' rating behaviors, social relationships, and review comments.

3 The Proposed Recommendation model

This section presents the details of the proposed PRMF model that jointly learn users' preferences and the dependencies between users for recommendation.

3.1 Probabilistic Relational Matrix Factorization

In Section 2.1, the PMF model assumes the users are independent of each other (see Eq.(2)). Thus, it ignores the dependencies between users. However, in practice, users are usually connected with each other through different types of relationships, e.g., trust relationships and online social relationships. In this work, to exploit users' dependencies for recommendation, we place the following priors on the user latent features:

where the first term of the priors is used to penalize the complexity of the latent features of each user, and the second term q(U) is used to model the dependencies between different users. Specifically, we define

where MNa×b(M, A, B) denotes the matrix variate normal (MVN) distribution 1 with mean M ∈ Ra×b , row covariance A ∈ Ra×a , and column covariance B ∈ Rb×b ; Θ ≻ 0 indicates Θ is a positive definite matrix. In Eq. (6), Θ is the row

1 The density function for a random matrix X following the MVN distributionMNa×b(M,A,B) is

precision matrix (i.e., the inverse of row covariance matrix) that models the dependencies between different rows of U. The row Ui is independent of another row Uk, if and only if Θik = 0 [Liu et al., 2009]. Note that each row of U represents the latent features of an individual user. Thus, in other words, Θ describes the dependencies between different users. In this work, Θ is called the user dependency matrix. For simplicity, we set the column covariance matrix of the MVN distribution as I, which indicates the user latent features in different dimensions are independent. Then, we rewrite Eq. (5) as:

In practice, a user usually only depends with a small fraction of other users. Thus, it is reasonable to assume the user dependency matrix Θ is sparse. To achieve this objective, we introduce a sparsity-inducing prior for Θ as follows:

where γ is a positive constant used to control the sparsity of Θ, and ‖ · ‖1 is the ℓ1-norm of a matrix. In addition, the sparsity of Θ can also help improve the computation efficiency.

Moreover, we also assume users' ratings follow the Gaussian distribution in Eq. (1) and add Gaussian priors on the item latent features as in Eq. (2). Through the Bayesian inference, we have

Then, the model parameters (i.e., U, V , and Θ) can be obtained by solving the following problem:

where | · | denotes the determinant of a matrix. Here, the model parameters are learned without prior information about users' relationships.

Incorporating prior user relationship information

Previous studies have demonstrated that user' explicit social relationships [Yang et al., 2014] and implicit social relationships derived from users' rating behaviors [Ma, 2013] can benefit recommendation accuracy. These prior relationship information contains some prior knowledge about users' dependencies in a recommendation task. Let Σ ∈ Rm×m denote the covariance matrix calculated based on users' rating behaviors. The elements of Σ are defined as follows:

where Ri∗ is the ith row in R; cov(x1, x2) denotes the covariance between two observations. If users' explicit social relationships are available, we consider the following sparse covariance matrix Σ:

where F(ui) denotes the set of ui's social friends. Then, users' dependencies in the rating space 2 can be described using the precision matrix Σ-1 .

To incorporate the prior information, we assume that the learned user dependencies in latent space are close to the user dependencies derived from prior relationship information in the rating space. This is achieved by minimizing the LogDet divergence [Davis et al., 2007] between the row precision matrix in Eq. (7) and the precision matrix Σ-1 as:

Note that other distance metrics can also be used to estimate the matrix closeness. Moreover, although Σ may be singular, the proposed method can also be used in practice (i.e., no computation of Σ-1 in Eq. (12)).

The unified model

Considering both the constraints in Eq. (10) and Eq. (12), we formulate the final objective function of the proposed PRMF model as follows:

where λu = σ2 /σ2u , λv = σ2 /σ2 v , and α = σ2 ; β is a parameter controlling the contribution of prior information.

3.2 Optimization Algorithm

The problem in Eq. (13) can be solved by the following alternating algorithm.

Optimize U and V : By fixing Θ, the optimization problem in Eq. (13) becomes:

The optimization problem in Eq. (14) can be solved using the SGD algorithm.The updating rules are as follows:

where ∆ij = Rij - UiV ⊤ j , Θi∗ is the ith row of Θ, and θ is the learning rate. Note the SGD updates are only performed on the observed rating pairs D = {(ui, vj , Rij )|Wij > 0}. Optimize Θ: By fixing U and V , the optimization problem with respect to Θ is as follows:

2 Each user is represented by a vector of her ratings on items.

The optimization problem in Eq. (16) is convex with respect to Θ. Therefore, the optimal solution ̂Θ to Eq. (16) satisfies:

where ̂G is the sub-gradient of ‖Θ‖1 over Θ, and the elements of ̂G are in [-1, 1]. Thus, according to the derivation of Dantzig estimator [Candes and Tao, 2007], we drop the constraint Θ ≻ 0 and consider the following problem:

By multiplying Θ + λu α I with the constraint, we obtain the following relaxation of Eq. (18):

where C = 1 d+β (UU ⊤ + βΣ), E = I - λu α C, and τ = γ d+β . This relaxation has been used in the constrained ℓ1minimization for inverse matrix estimation (CLIME) [Cai et al., 2011]. Indeed, the optimization in Eq. (19) is equivalent to the following optimization problem [Liu and Luo, 2014]:

Let ˜Θ be the solution of Eq. (20), which is not necessarily symmetric. We use the following symmetrization step to obtain the final ̂Θ:

where I(·) is an indicator function, which is equal to 1 if the condition is satisfied, and otherwise 0. In addition, although constraint Θ ≻ 0 is not in Eq. (20), the symmetrized ̂Θ is positive definite with high probability and converge to the solution of Eq. (16) under the spectral norm, guaranteed by Remark 1 and Theorem 1 in [Liu and Luo, 2014].

The problem in Eq. (20) can be solved by the ADMM algorithm [Boyd et al., 2011]. The augmented Lagrangian of Eq. (20) is as follows:

where Y is a scaled dual variable and ρ > 0. We can obtain the following ADMM updates:

(24)

The closed solution to Eq. (23) is as follows:

Algorithm 1: PRMF Optimization Algorithm

where

The solution to Eq. (24) is as follows:

The time complexity of the inverse operation in Eq. (28) is O(m3 ). As Σ is symmetric, to improve the computation efficiency, we consider the following approximation Σ ≈ XX⊤, where X ∈ Rm×d . In this paper, we obtain X by factorizing Σ using SVD and choosing the singular vectors with respect to the top d largest singular values (see line 2 in Algorithm 1). Let ̂ U = [ 1 √d+β U, √β √d+β X] ∈ Rm×2d . When the prior covariance matrix Σ is not available, we set ̂ U = 1 √d U. Then, C ≈ ̂ U ̂ U ⊤. Following Woodbury matrix identity, we have

Using this matrix operation, the time complexity of the update of Z in Eq. (28) becomes O(dm2 ). The details of the optimization algorithm are summarized in Algorithm 1. At each iteration, the time complexity of the SGD updates is O(T · |D| · ¯m · d), where ¯m denotes the average number of nonzero elements in a row of Θ. Thus, the sparsity of Θ can help improve the computation efficiency of the proposed method. The time complexity of the ADMM updates is O(K · d · m2 ).

4 Experiments

We conduct empirical experiments on real datasets to demonstrate the effectiveness of the proposed method.

4.1 Experimental Setting

Datasets

The experiments are performed on four public datasets: MovieLens-100K, MovieLens-1M 3 , Ciao, and Epinions 4 . MovieLens-100K contains 100,000 ratings given by 943 users to 1,682 movies. MovieLens-1M consists of 1,000,209 ratings given by 6,040 users to 3,706 movies. We denote these two datasets by ML-100K and ML-1M, respectively. For the Ciao and Epinions datasets, we remove the items that have less than 3 ratings. Finally, on Ciao dataset, we have 185,042 ratings given by 7,340 users to 21,881 items. On Epinions dataset, there are 642,104 ratings given by 22,112 users to 59,104 items. The densities of the rating matrices on these datasets are 6.30% for ML-100K, 4.47% for ML-1M, 0.12% for Ciao, and 0.05% for Epinions. Moreover, on Ciao and Epinions datasets, we have observed 111,527 and 353,419 social relationships between users. The densities of the social relation matrices are 0.21% for Ciao and 0.07% for Epinions. Table 1 summarizes the details of the experimental datasets. For each dataset, 80% of the observed ratings are randomly sampled for training, and the remaining 20% observed ratings are used for testing.

Evaluation metrics

The performances of the recommendation algorithms are typically evaluated by two most popular metrics: mean absolute error (MAE) and root mean square error (RMSE), which are defined as follows:

where Rij denotes observed rating in testing data, ˆRij is the predicted rating, and Dtest denotes the set of tested ratings.

Evaluated recommendation methods

We compare the following methods: (1) PMF: This is the probabilistic matrix factorization model [Mnih and Salakhutdinov, 2007]. (2) SRimp : This is the SR method that exploits users' implicit social relationships for recommendation [Ma, 2013]; (3) SRexp : This is the SR method that exploits users' explicit social relationships for recommendation [Ma et al., 2011]; (4) LOCABAL: This is the social recommendation model that exploits both local and global social contexts for recommendation [Tang et al., 2013]; (5) eSMF: This method extends LOCABAL to consider the graph structure of social neighbors for recommendation [Hu et al., 2015]; (6) PRMF: This method learns users' dependencies without prior information. The objective function is Eq. (10); (7) PRMFimp :

3 http://grouplens.org/datasets/movielens/

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

This is the proposed method that exploits users' implicit social relationships as prior knowledge to learn users' dependencies; (8) PRMFexp : This is the proposed method exploiting users' explicit social relationships as prior knowledge to learn users' dependencies.

Parameter settings

Cross-validation is adopted to choose the parameters for each evaluated algorithm. The validation data is constructed by randomly chosen 10% of the ratings in the training data. For matrix factorization methods, the dimensionality of latent space d is set to 10. The latent features of users and items are randomly initialized by a Gaussian distribution with mean 0 and standard deviation 1/√d. Moreover, we set the regularization parameters λu = λv and choose the parameters from {10-5 , 10-4 , · · · , 10-1 }. For PRMF, α is chosen from {2-5 , 2-4 , · · · , 2-1 }, θ is chosen from {2-5 , 2-4 , · · · , 2-1 }. For simplicity, we empirically set γ = 10-4 , β = 10, and ρ = 100. For SR methods, the regularization parameter α is chosen from {2-7 , 2-6 , · · · , 20 }. The user similarity is computed using Pearson correlation coefficient, and we set the threshold of the user similarity at 0.75 and N = 10, following [Ma, 2013]. The parameters of LOCABAL and eSMF are set following [Tang et al., 2013] and [Hu et al., 2015]. For each algorithm, we repeated the experiments five times with different random seeds. The results reported are average of the five runs.

4.2 Summary of Experimental Results

Table 2 summarizes the experimental results on the datasets without users' explicit social relationships, and Table 3 summarizes the results on the datasets with users' explicit social relationships. We make the following observations:

• On all datasets, PRMF outperforms PMF by 0.94% on ML-100K, 1.36% on ML-1M, 7.05% on Ciao, and 5.16% on Epinions, in terms of RMSE. This indicates the recommendation accuracy can be improved by jointly learning users' preferences and users' dependencies.

(a) ML-100K

(b) Ciao

Figure 1: Performance trend of PRMFimp on the ML-100K and Ciao datasets measured by RMSE with different settings of γ.

• Compared with SRimp , PRMFimp achieves better results on all datasets. For example, in terms of RMSE, PRMFimp outperforms SRimp by 0.73%, 0.49%, 2.92%, and 2.40%, respectively. This shows that users' dependencies learned from the rating data are more effective than the user dependencies pre-defined based on users' implicit social relationships, for improving the recommendation accuracy.
• The proposed PRMFexp method outperforms several existing social recommendation methods that exploit users' explicit social relationships for recommendation. On the Ciao and Epinions datasets, the average improvements of PRMFexp over SRexp , LOCABAL, and eSMF, in terms of RMSE, are 1.03%, 3.60%, 2.77%, respectively. This again demonstrates the effectiveness of the proposed method.
• PRMFimp and PRMFexp outperforms PRMF on all datasets. This observation consistently indicates the prior information about user dependencies (i.e., users' explicit and implicit social relationships) are beneficial in improving recommendation accuracy. However, the improvements are not very significant. One potential reason is the SVD factorization used in Algorithm 1 (line 2) may not accurately approximate the prior covariance matrix.

In addition, we also study the impact of the sparsity of the learned user dependency matrix Θ on the recommendation accuracy. We choose the regularization parameter

γ from {0, 10-4 , 10-3 , 10-2 , 0.1, 0.3, 0.5, 0.7, 0.9, 1.0, 10}. Figure 1 shows the performance trend of PRMFimp on the ML-100K and Ciao datasets, in terms of RMSE. Observed that the sparsity of Θ increases with the increase of γ. As shown in Figure 1(a), denser user dependency matrix generally achieves better recommendation accuracy. However, denser user dependency matrix causes more computation time used to learn the user latent features. Indeed, there exists some balance between the computation efficiency and the recommendation accuracy. For example, on the ML-100K dataset, by setting γ to 0.3, the sparsity of the learned Θ is 65.21%, and the RMSE value is 0.9149, which is 0.56% better than the best competitor SRimp . Moreover, Figure 1(b) also indicates that better recommendation accuracy may be achieved by learning a sparse Θ. For example, on the Ciao dataset, the best recommendation accuracy is achieved by setting γ to 0.1, and the sparsity of the learned Θ is 83.67%. On the ML-1M and Epinions datasets, we have similar observations with that on the ML-100K dataset. Due to space limitation, we do not report those results here.

5 Conclusion and FutureWork

In this paper, we propose a novel recommendation method, namely probabilistic relational matrix factorization (PRMF). For a specific recommendation task, the proposed approach jointly learns users' preferences and the dependencies between users, to improve the recommendation accuracy. Empirical results on real datasets demonstrate the effectiveness of PRMF, in comparison with strong baseline algorithms.

The future work will focus on the following directions. First, we would like to develop more efficient optimization algorithms for PRMF using the parallel optimization framework [Wang et al., 2013]. Second, we are also interested in extending PRMF to solve top-N item recommendation problems with users' implicit feedback. The potential directions are adopting logistic matrix factorization [Johnson, 2014; Liu et al., 2016] or ranking metrics optimization methods [Zhao et al., 2011] to model users' implicit feedback.