Matrix completion with Preference Ranking for Top-N Recommendation

1 Introduction

Living in the information era, how to search valuable information from thousands and millions of online items to satisfy requests of various people is a challenge we face today. To address this challenge, recommender systems have drawn industry and academia's common attention in recent years [Covington et al., 2016; Linden et al., 2003; Xu et al., 2017]; a top-N recommender system generates a short preference ranking list with length N for a user. In the past decades, recommender systems have been successfully applied in business applications, and many E-commerce companies have reported profit growth by integrating recommender systems into their applications [Covington et al., 2016; Linden et al., 2003].

Many works have developed top-N recommender systems to improve people's experience of online services, such as online shopping [Linden et al., 2003; Mirbakhsh and Ling, 2015]. One popular technique for top-N recommendation is collaborative filtering (CF), which predicts people's preference by finding the relations in an observed user-item matrix. In general, CF methods can be divided into two categories, model-based methods and nearest-neighborhood-based methods. For model-based methods, matrix factorization is the most popular technique, which projects users and items into a latent space and predicts the rating scores of a user-item matrix with the inner products of users' and items' latent factors. For example, [Cremonesi et al., 2010] produces the user and item latent factors with singular value decomposition (SVD). [He et al., 2017] performs matrix factorization with a deep learning technique by learning the nonlinearities of user and item latent factors with multi-layer perceptions. Different from model-based CF, which can be treated as user-item models, nearest-neighborhood-based methods mainly focus on the similarities between either items or users. The most representative approach is the itembased k-nearest-neighbor method, which is the first itembased approach for identifying a set of similar items [Deshpande and Karypis, 2004]. However, since the user-item matrix is very sparse, the recommendation quality can be very limited solely based on the similarity measurement. To improve the nearest-neighborhood-based collaborative filtering, a new type of item-item based model has been developed to learn a sparse coefficient matrix from data with linear itemitem aggregations, which has demonstrated effective performance for top-N recommendation [Ning and Karypis, 2011; Kabbur et al., 2013].

The above methods perform learning based on the pointwise scores of user-item pairs. However, preference ranking between each pair of items for a user is an intrinsic characteristic of top-N recommender systems for assisting users. Recently, many works have exploited preference ranking learning to improve the performance of top-N recommendation [Zhao and Guo, 2016; Rendle et al., 2009; Man et al., 2017; Park et al., 2015]. These methods learn users' preference information between items from large number of ranking triplets, each containing a pair of items and a user. The preference ranking information can naturally benefit top-N recommendations due to the selective nature of the task. Nevertheless, such preference ranking methods mainly capture local item comparison information for each user, while ignoring global structural information of the recommendation matrix such as the inherent low-rank property. The low rank property is an intrinsic characteristic of recommendation matrices due to the limited available rating scores for each single user [Kang et al., 2016; Cheng et al., 2014].

In this paper, we propose a novel matrix completion approach that integrates both the low rank property and the preference ranking objective into a joint nonconvex learning problem for top-N recommendation. The objective function combines the low rank regularization and the preference ranking loss under a linear self-recovery model to enforce both the global low rank consistency and the local ranking order consistency over the user-item scores in the recovered recommendation matrix. To facilitate an easy optimization procedure over the joint nonconvex minimization, we use an alternating direction method of multipliers (ADMM) to reformulate the problem into convex sub-problems over each individual variable. To validate the effectiveness of our proposed approach, we test it on several real world datasets. The experimental results show that our approach achieves the best performance compared with several state-of-the-art top-N recommendation methods.

2 RelatedWorks

As top-N recommender systems have significant commercial impact, various top-N recommender systems have been developed over the past decades. We briefly review the works that are most closely related to the proposed method. [Deshpande and Karypis, 2004] proposed the item-based top-N recommendation method based on items' similarities. The similarity between two items are measured with all the ratings on the two items, and then the top-N most similar items to the current items of the users are recommended. In [Cremonesi et al., 2010], pureSVD was proposed by using the principle singular vectors to represent the users' and items' latent factors and reconstruct the rating matrix with the inner products of user-item latent factors. In [Ning and Karypis, 2011], the authors proposed a sparse linear method (SLIM) to recover the recommendation matrix by learning a sparse aggregation coefficient matrix that captures item-item correlations. SLIM achieved promising performance for top-N recommendation.

The observed records of a recommendation matrix typically demonstrate the preference of each user over the item set; in particular a user prefers the purchased items more than the unpurchased items. Hence the preference structure is one intrinsic characteristic of top-N recommendation tasks. To improve top-N recommendation performance, many works have exploited the preference structure in the top-N recommendation task [Rendle et al., 2009; Man et al., 2017; Yun et al., 2014; Park et al., 2015; Zhao and Guo, 2016]. The work in [Rendle et al., 2009] proposed a ranking strategy that maximizes the posterior probability between a ranking pairs. [Man et al., 2017] proposed a cross domain recommendation method and improved the method with the ranking strategy in [Rendle et al., 2009]. [Yun et al., 2014] proposed a ranking algorithm that is motivated by observing a close connection between evaluation metrics and loss functions. [Park et al., 2015] proposed a large-scale collaborative ranking method from pairwise comparisons. [Zhao and Guo, 2016] integrated the collaborative ranking loss and the pointwise loss of SLIM to gain better recommendation performance.

Besides the preference structure, the low rank property of the recommendation matrix have yield another line of research study [Kang et al., 2016; Cheng et al., 2014;

Zhao et al., 2017]. The work in [Cheng et al., 2014] extended SLIM by using a nuclear norm to enforce low-rank regularization on the coefficient matrix. [Kang et al., 2016] proposed to use a log-determinant function, logdet, to directly enforce the low-rank property of the recovered recommendation matrix, which produced impressive results on top-N recommendation tasks. [Zhao et al., 2017] proposed a social local model by incorporating social connections into a local low rank framework.

Although many works have been done on top-N recommendation tasks, most of these existing methods have not fully considered the intrinsic characteristics of the task, e.g., exploiting the low rank structure and preference ranking structure simultaneously. In this paper, we complement the literature by developing a parametric top-N recommendation model that integrates low-rank and preference ranking together under a linear self recovery model.

3 Methodology

In this section, we present the proposed matrix completion approach. We consider the following settings. We assume a partially observed user-item matrix M ∈ Rn×m with implicit feedbacks, i.e., {0, 1}-values, over n users and m items. Each entry of the matrix, Mui, represents whether user u has implicit feedback (e.g., a purchase record) on item i. If Mui is equal to 1, it indicates the user u has a purchase record on item i; otherwise Mui is 0. The main goal of the top-N recommendation task is to recommend the top-N item list that the user is most likely to purchase in the future by recovering a fully "observed" matrix X from the partially observed sparse matrix M.

3.1 Matrix Completion with Preference Ranking

Low-rank matrix completion methods and preference ranking methods perform matrix recovery for recommender systems by utilizing different characteristics of recommender matrix. We propose to combine them into a coherent joint model to integrate their complementary strengths.

Low-rank matrix completion methods have mainly pursued different approximations of the rank function. We adopt a nonconvex rank approximation from [Kang et al., 2016], which uses the log-determinant approximation below

where Ω is a index set of the observed user-item entries and I is an identity matrix. This low-rank based learning method apparently did not consider any local user preference information. We assume a proper recovered matrix X will not only possess the global low-rank property, but also maintain a consistent local preference ranking structure in the observed matrix M. For example, if user u has purchased item i but not item j, it indicates that user u prefers item i more than item j. In fact, many methods in the literature have demonstrated that preference ranking over items is necessary and scientific for top-N recommendation. Hence, we propose to integrate the preference ranking advantage with the low-rank matrix completion to further improve top-N recommendation performance. In particular, we formulate the minimization problem of matrix completion with preference ranking as follows:

where α is a trade-off parameter that balances the low-rank regularization and the preference ranking loss; T denotes a set of triplet instances {(u, i, j)} which are derived from the observed user-item matrix, and L(·) denotes a preference ranking loss for each triplet instance (u, i, j) from the set T . A triplet instance (u, i, j) denotes user u prefers item i more than item j, namely Mui > Muj in the observed matrix M. This also should be preserved as Xui > Xuj in the recovery matrix X.

Although the minimization problem in (2) meets our goal, the preference ranking loss in it mainly serves as a direct ranking regularization without being statistically and tractably learned from data, and the problem is hardly scalable. To solve this problem, we define the recovery matrix X using a linear self-recovery model X = MW with parameter matrix W. Sparse linear self-recovery models have been very effectively exploited in a few literature works, including SLIM [Ning and Karypis, 2011]. Here we ignore the sparsity but keep constraints W ≥ 0 and diag(W) = 0 on the parameter matrix to avoid trivial solutions. Moreover, we use a max-margin squared hinge loss function, Lr(x) = max(0, 1 - x)2 , as the ranking loss, since hinge loss is particularly suitable for encoding pairwise ranking orders due to its comparative form. This yields the joint learning problem below:

To increase the feasibility of the learning problem, instead of keeping the equality constraint X = MW, we encode it as a regularization term in the objective function instead and obtain the following learning problem:

where α and β are the trade-off parameters. Note in the optimization problem (4), the linear self-recovery parameter matrix W is learned mainly based on preference ranking loss, while the regularizer ||X -MW||2F , as a relaxation of the equality constraint X = MW, builds connections between the low-rank recovery matrix X and the preference ranking recovery matrix MW and propagates the preference ranking information to produce the low-rank recovery matrix X.

Hence the trade-off parameter α actually controls how much the recovery MW from the preference ranking component affects the final recovery matrix X.

3.2 Optimization Algorithm

We adopt the alternating direction method of multipliers (ADMM) technique to solve the joint minimization problem (4). To obtain easy solutions for each subproblem of the ADMM algorithm, we first separate the low rank recovery and the preference ranking recovery by introducing an auxiliary variable Y and reformulate the problem as follows:

Then we use the augmented Lagrangian dual formulation to encode the equality constraint X = Y , which produces

s.t. Xui = Mui, ∀(u, i) ∈ Ω; Y ≥ 0, W ≥ 0, diag(W) = 0

where ρ is a penalty parameter and Z is a dual variable matrix.

The ADMM algorithm will then solve (6) iteratively in an alternating manner by solving a sequence of simpler subproblems. In the (t + 1)-th iteration, we first update W given Y t from the previous iteration by minimizing the following subproblem:

This subproblem can be solved using projected stochastic gradient descent, and the updating rules are as follows

where |Ti| and |Tj| represent the number of triplets which contain the item i and item j in T respectively; η is learning rate. ▽Lr(W t :,i ) and ▽Lr(W t :,j ) are gradients of W t :,i and W t :,j based on Lr(x) = max(0, 1 - x)2 respectively. If Mu,:(W t :,i - W t :,j ) < 1,

If Mu,:(W t :,i -W t :,j ) ≥ 1, ▽Lr(W t :,i ) = 0 and ▽Lr(W t :,j ) = 0. Moreover, we project W t+1 onto the constraints by setting W t+1 = max(0, W t+1 ) and diag(W t+1 ) = 0.

Next we update Y with fixed Xt , Z t and W t+1 by solving the following subproblem

which has a closed form solution:

Then X can be updated with fixed Y t+1 by solving

This subproblem can be converted to scalar optimization problems following the following proposition.

Proposition 1 Given a matrix B ∈ Rn×m with SVD of B = Udiag(σ(B))V T , consider the minimization problem below

where σi(A) denotes the ith singular values of A and g(·) denotes a unitary invariant function with g(A) = g(σ(A)) . This problem has a solution of A∗ = U(diag(σ∗ (A)))V T , where σ∗ i (A) can be obtained by solving the minimization problem below:

Proposition 1 can be easily proved following [Kang et al., 2015; Lu et al., 2015]. Based on this proposition, Solution for equation (12) can be obtained by solving a series of scalar problems for σ∗ (X) with:

where σi is the ith singular value of (Y t+1 - Zt ρt ). By setting the derivative of the objective function of (15) wrt σi(X) as zero, we can obtain its optimal solution σ∗ i (X), which is the unique minimizer. Then X can be updated by

where U and V are the singular vector decomposition (Y t+1 - Zt ρt ) = Udiag(σ)V T .

Finally, following the standard ADMM, we update the dual variables Z and the penalty parameter ρ with rules below

The overall procedure is summarized in Algorithm 1.

Algorithm 1 Matrix Completion with Preference Ranking

Input:

Initial parameters at t = 0: Xt = Y t = M, the parameter matrix W t with W t ≥ 0, diag(W t ) = 0, the penalty parameter ρt , the dual matrix Z t = 0, and γ > 1.

1: repeat

• 2: Given Y t , update the linear self-recover parameterW t by (8);
• 3: Given Xt ,Z t ,W t+1 , update the auxiliary matrix Y t by (11);
• 4: Given Y t+1 ,Z t , ρt , update the completion matrix Xt by (16);
• 5: Given Y t+1 ,Xt+1 , update the Lagrangian dual matrix Z t and ρt by (17);
• 6: Set t = t +1
• 7: until ||Xt+1-Xt ||2F
• ||Xt ||2F ≤ ϵ

Output: The completion matrix X∗ = Xt+1 .

4 Experiments

In this section, we report our experimental setting and results on six real world recommendation datasets.

4.1 Settings

To investigate the effectiveness of the proposed approach for top-N recommendation, we conducted experiments on six Amazon datasets: Automotive, Musical, Video, Office, Sports and Clothes. The datasets are downloaded from website 1 . We preprocessed the datasets by filtering out the users and items with less than 5 ratings. This leads to the following datasets: Automotive (2928 users, 1835 items, 20473 transactions), Musical (1429 users, 900 items, 10261 transactions), Office (4905 users, 2420 items, 53258 transactions), Video (5130 users, 1685 items, 37126 transactions), Sports (2000 users, 1961 items, 27209 transactions) and Clothes (2000 users, 1389 items, 12959 transactions). We transformed the matrices into implicit feedbacks by keeping value 1 if there is a transaction/activity between the user and item pair, and setting the value as 0 otherwise. The ranking pairs are randomly selected with one hundred times of user number.

We adopted the leave-one-out technique to evaluate the performances of different recommendation methods by following the setting of previous literature work [He et al., 2017]. On each dataset, we selected the latest transaction item for each user as the test set and used the remaining items as the training set. For efficient test evaluation, we randomly sampled 100 items without transaction records as part of the test set and produced the top-N rank list from only the test set, which is a common strategy used in [He et al., 2017; Koren, 2008; Elkahky et al., 2015]. We adopted two widely used popular evaluation metrics, Hit Ratio (HR) and Normalized Discounted Gain (NDCG) [He et al., 2017], to evaluate the top-N recommendation performance of each method.

We compared the proposed matrix completion with preference ranking method, PrMC, with several state-of-the-art methods, BPR, SLIM, MC and NeuMF. BPR is a pairwise ranking method which is proposed in [Rendle et al., 2009] based on a matrix factorization model. SLIM is a most popular and effective method on top-N recommendation [Ning and Karypis, 2011]. We used the librec code for these two methods 2 . MC [Kang et al., 2016] and NeuMF [He et al., 2017] are two state-of-the-art methods for top-N recommendation, which are based on low-rank matrix completion and deep learning technique respectively. For these two methods we used the released codes in the original papers. To further obtain ablation analysis for the proposed method, we also directly compared with two variants of the methods, PrMCnopr and PrMCnorank. PrMCnopr is a variant of the proposed method without the preference ranking component, which simply integrates the logdet function and the linear self construction. PrMCnorank is another variant of the proposed method without the low rank regularization.

1 http://jmcauley.ucsd.edu/data/amazon/

We performed the following parameter selection for the trade-off parameters and algorithm running parameters. The latent dimension of BPR is selected from {50, 100, 200, 500}. For SLIM, we chose the l1 norm parameter from {1, 10, 100}, and the l2 norm parameter from {0.001, 0.01, 0.1}. For MC, the Lagrangian penalty parameter is selected from {0.01,

2 https://www.librec.net/

0.02, 0.03}, and the γ for updating the Lagrangian penalty is selected from {1.5, 2, 2.5, 3, 3.5,4}. For NeuMF, we used the most effective settings according to the original paper. For the proposed method, we chose the penalty parameter ρ from the same set as MC, and selected the weight parameter α from {0.001, 0.01, 0.1, 1, 3, 5}. We fixed γ as 1.5 and β as 5000. The best results are reported for each method.

4.2 Experimental Results

We reported the results in terms of HR@10 and NDCG@10 and the parameter setting for each method in Table 1. Meanwhile, we also reported results with different N values from {5, 10, 15, 20, 25} in Figure 1.

Overall we can see that the proposed PrMC is the bestperforming method, and it consistently outperforms the other comparison methods on all the six datasets across different N values. The other comparison methods though have strengths in different scenarios, none of them consistently performs better than the other. For example, though MC performs slightly worse than BPR on Automotive and Musical datasets, it outperforms BPR on the other four datasets. For the comparisons between SLIM and NeuMF, although NeuMF achieves better performance than SLIM in terms of HR, SLIM outperforms NeuMF in terms of NDCG in most cases

(on four datasets). The two variants of the proposed method, PrMCnopr and PrMCnorank, both produce inferior performance comparing to PrMC. This suggests both the global low-rank regularization and local preference loss ranking on each user are effective for top-N recommendation and critical for the proposed model. The proposed model demonstrates its capacity for successfully integrating the two fundamental and complementary characteristics of recommender systems.

4.3 Parameters Analysis

For the proposed approach, two main parameters are tuned: the penalty parameter ρ and the trade-off parameter α that controls the affecting of preference ranking in the recovery matrix X. The sensitivity analysis are conducted on office and video datasets by using a range of different values, and the results in terms of HR@10 are reported in Figure 2.

From the results we can see that the performance of the approach is not very sensitive to the parameter value of ρ. Given fixed α value, the results have no obvious change with different ρ values when both α and ρ are not too small. This is reasonable since ρ is iteratively upscaled within the ADMM optimization procedure and the initial ρ value should not cause any dramatic difference. Comparing to ρ, the top-N recommendation performance of the proposed method is very sensitive to the α value. When α is large (α > 0.1), the performance is very poor. This might be due to the fact that large α allows the preference ranking component to dominate the recovery matrix X and hence diminish the low-rank information. With a proper value α ∈ (0.001, 0.1), the low-rank and preference ranking can be better balanced and the performance can be more reasonable.

5 Conclusion

In this paper, we proposed a novel top-N recommendation method based on matrix completion by integrating the low rank regularization and the preference ranking into a joint learning model. The proposed method maintains both the global low-rank structure and the local preference ranking structure of the recommendation matrix by combining their complementary strengths. We developed an ADMM algorithm to solve the proposed joint learning problem. We conducted the experiments on six E-commerce real world datasets. The results demonstrated that the proposed approach can outperform a number of state-of-the-art top-N recommendation methods. The ablation comparison results suggested both the low-rank and the preference ranking components are useful within our proposed model.

Acknowledgements

This research is supported in part by China Scholarship Council (201706270109), Natural Science Foundation of China (61471274), NSERC and the Canada Research Chairs program.