Discrete Trust-aware Matrix Factorization for Fast Recommendation

1 Introduction

Trust-aware recommender systems have received much attention recently due to their abilities of capturing the influence among connected users. Trust data is a good supplement to the sparse rating data and furthermore provides more accurate prediction rating [Ma et al., 2008; Mohsen and Martin, 2010; Yang et al., 2013; Guo et al., 2015]. In addition, collaborative filtering (CF) have been widely used in trust-aware recommender systems due to their simplicity. However, such an approach often suffers from serious efficiency dilemma on large data sets. Specifically, the main task in a recommendation system is to recommend top-k items to meet users' favorite interests, in which it requires a huge amount of computations to calculate the user's rating of each item and then rank it according to the rating.

Recently, the discrete matrix factorization technique captures attention due to its recommendation efficiency. It adopts hash technology [Zhang et al., 2016; Zhang et al., 2017;

∗Corresponding author

Lian et al., 2017; Liu et al., 2018] to map latent features of users and items to a joint hamming space and transforms the items recommendation task into a similarity search problem, which greatly improves the recommendation efficiency. Specifically, binary code can be executed with bit operation. At the same time, binary code can be searched quickly: Since the users and the items are in the joint hamming space, when recommending items for a user, it is only necessary to find the items with a small hamming distance around the user, this makes our recommendation time independent of the number of items. In addition, thanks to the binary code, we need less memory to store trained latent feature of users and items.

By incorporating trust-aware and hash technology, we propose two new models, called DTMF model and DTMF-D model, to inherit the dual advantages of CF-based trust-aware recommendation and discrete matrix factorization, i.e., high accuracy and fast efficiency. To the best of our knowledge, this is the first work to perform hash technique on matrix factorization for trust-aware recommendation 1 . Specifically, the challenges and our contributions are briefly summarized as:

• The first challenge is how to effectively learn binary code from real-values based trust-aware matrix without sacrificing too much information. We direct learning the latent feature of truster and trustees, and items as binary codes via discrete optimization. By adding balanced and decorrelated constraints for each bits, we are able to represent richer information in more compact code.
• The second challenge is how to efficiently optimize the proposed new discrete matrix factorization models which consider extra trust relationships among each user. We adopt an efficient discrete optimization algorithm to solve each subproblems alternately. This alternating optimization technique could constantly reduce the quantization loss from real value to discrete value.
• We demonstrate the superiority of proposed models and discrete optimization methods on two real-world datasets against other state-of-art models and solvers. Preliminary experiments indicate that the jointly proposed models and discrete optimization methods can simultaneously improve the recommendation efficiency and ensure the predicted accuracy.

1 We acknowledge a concurrent work [Liu et al., 2019], which has not appeared online when we submitted our work.

2 RelatedWork

The performance and efficiency of recommendation system are two important indexes in practical application, there's been a lot of research on this, can be summarized as the following trust-based Recommendation and discrete hash:

2.1 Trust-based Recommendation

Social information based recommendation system has been widely studied, the basic idea of the model is to promote the user to employ sharing rating data and trust data simultaneously. [Ma et al., 2008] firstly proposed probability matrix factorization to solve the data sparsity and poor prediction accuracy problem by adopting rating data and user's social network data. [Mohsen and Martin, 2010] believed that the rating of a trusted user should directly affect the latent feature of the user, rather than the final rating of user. Therefore, they proposed that the latent feature of users should be close to the average of all the latent feature of users he trusts. [Ma et al., 2011] systematically illustrated how to design the objective function of a social regularization. [Yang et al., 2013] proposed a hybrid model that combines both a truster model and a trustee model, in which a user should consider both the influence of his truster users and the influence of his trustee users. [Guo et al., 2015] taken into account both the explicit and implicit influences of rating and trust information in predicting ratings. As mentioned above, this type of recommendation suffered from the efficiency issue on large datasets.

2.2 Discrete Hashing

Hashing technique is an efficient approach for fast similarity search and its detailed description can be founded in [Wang et al., 2016]. The pioneer work [Abhinandan et al., 2007] generated hash code based on the user's history behavior by using Locality-Sensitive Hashing algorithm. [Zhou and Zha, 2012] proposed to learn binary code to tackle the efficiency problem of making recommendations in the case of large users and items. [Zhang et al., 2014] adopted hashing technique and considered that recommendation should be focused on users' preference over items rather than their similarities, so they propose a novel model to solve the challenge. To summarize these before work, learning hash code can be regarded as two independent stages: relaxed learning and binary quantization. Due to the large quantization accuracy loss in the two stages discrete optimization algorithm, [Zhang et al., 2016] first transformed the two-stage discrete optimization into a joint optimization and by introducing the balanced and decorrelated constraints, more abundant information can be learned with less bit. In addition, some work has added some auxiliary information to the discrete collaborative filtering. [Zhang et al., 2017] used hashing technique to personalized recommendations from implicit feedback, [Lian et al., 2017] used textual content information to discrete matrix factorization whose model extended the recommendation task from regression to classification.

To the best of our knowledge, all these discrete collaborative filtering algorithms ignored the important social relationships. However, trust information could contain a strong correlation with taste, it has been independently exploited to improve the predictive performance. Our model fills in the gap of the discrete model and trust-aware model by simultaneously learning binary code of truster and trustee.

3 Our Model

For better readability, we first denote some necessary notations. Generally, we use bold uppercase and lowercase letters to represent matrices and vectors, respectively; and adopt non-bold letters for scalars. In particular, A represents a matrix with a suitable dimension, where ai is the i-th column vector and Aij is the (i, j)-th component of matrix A. Besides, we use ||A||F and tr(A) to denote the Frobenius norm and trace of matrix A, respectively.

3.1 DTMFModel

In our DTMF model, we denote B = [b1, b2, . . . , bm] ∈ {±1}r×m and D = [d1, d2, . . . , dn] ∈ {±1}r×n as r-length (r ≪ m, n) binary representation of users and items respectively, where m, n is the number of users and items. Thus a user's preference for an item can be measured by the common bits [Zhou and Zha, 2012] of their latent feature vector in Hamming space. We define the Hamming similarity between user i and item j as follows:

where I(bik, djk ) is 1 when bik = djk is true, otherwise is 0. distH(bi, dj) is the hamming distance between bi and dj. In other words, for an observed rating Sij ∈ [0, 1], we can transform it to Sij ← 2rSij - r such that the inner product b⊤i dj can be used to approximate such a value by Eq. (1).

For trust information, let W = [w1,w2, . . . ,wm] ∈ {±1}r×m be the binary vectors of trustees, i.e., those trusted by some other users. Likewise, the inner product b⊤i wt of user i and trustee t can be used to approximate an observed trust value Tit ∈ [0, 1] after being transformed by Tit ← 2rTit - r according to Eq.(1).

Finally, the main goal of our work is to reconstruct the interactions of both user-item ratings and user-user trust as accurately as possible, whereby the binary (and compact) representation of users and items can be learned for an efficient recommendation.

In addition, we follow the suggestions of [Zhou and Zha, 2012] to further consider the balanced and de-correlated constraints, in order to maximize the information binary codes can represent. Specifically, the balanced constraint applies the principle of maximum entropy of uniformly distributed information in information theory, while the de-correlated constraint contends that each bit should be as independent as possible. To sum up, we define our objective function as shown in Eq.(2), given by:

where λ is a trade-off parameter to indicate the importance of trust reconstruction for overall rating prediction.

Note that it is NP-hard to directly solving problem (2). For the ease of problem solving, we soften the balanced and de-correlated constraints by defining three sets B,D,W so as to minimize their distances to B, D, W. Take B as an example since other variables basically follow the same definitions. Specifically, it is defined as B = {X ∈ Rr×m|X1m = 0;XX⊤ = mIr}, and the distance as dist(B, B) = minX∈B ||B-X||F . Therefore, the objective function Eq.(2) can be rewritten as follows:

where α, β, γ > 0 are used to indicate the degree of proximity between the two matrices. As B⊤B and X⊤X are constant, we can use 2αtr(B⊤X) to substitute ||B-X||F for optimization, which also holds for D and W. We derive the following optimization function:

3.2 DTMF-DModel

At the same time, we also propose an alternative way to use trust data termed as the DTMF-D model. Its basic idea is to impose that two users with trust relationship should be in a closed position in hamming space, that is, to minimize the hamming distance between two trust users distH(bi, bt).

We soften the balanced and de-correlated constraints and adopt Eq. (1) to compute the hamming distance. In this way, we can formulate the following objective function:

We present DTMF-D to show how trust can be utilized in other manners for discrete collaborative filtering, but till far we have found that DTMF generally gets better performance than the others through extensive experimental study. We do not show the detailed results in Section 4, but instead focus more on the evaluation of our main approach DTMF.

3.3 Optimization

We use an alternative optimization technique to solve the DTMF models, which alternately update the variables B, D, W, X, Y and Z. The detailed algorithm description is presented in Algorithm 1. Below, we show that each subproblem has a closed-form solution.

B-subproblem

In this subproblem, we aim to optimize B with fixed D, W, X, Y, Z. We can parallelly update each column bi of B according to the following binary optimization:

where Ωi, Γi are the set of rated items and trusted users of user i, respectively.

Due to the existence of discrete constraints, such a problem becomes NP-hard to solve. Instead, we use Discrete Coordinate Descent (DCD) to update bi bit to bit. Let bik be the k-th coordinate in bi and bi¯k be the rest of bi excluding bik. We then update bi bit by bit using the following formula:

where sgn(·) is a sign function, K( ˇ bik, bik) is a function such that K( ˇ bik, bik) = ˇ bik if ˇ bik ̸= 0, and K( ˇ bik, bik) = bik otherwise. It does not update bik when ˇ bik is equal to 0.

D-subproblem

In this subproblem, we optimize D with fixed B, W, X, Y, Z. Similar to the B-subproblem, we parallelly update D according to

We also use Discrete Coordinate Descent (DCD) to update dj bit to bit, and each bit djk based on the following rule:

W-subproblem

Similar to the D-subproblem, we parallelly update W according to

We use DCD to update wt based on the following rule:

X-subproblem

In this subproblem, we aim to optimize X with fixed B, D, W, Y, Z. The optimization for X is:

Inspired by [Liu et al., 2014], we denote a matrix J = I - 1n 11⊤, by Singular Value Decomposition (SVD), we have ¯B = BJ = PBΣBQ⊤B, where PB ∈ Rh×h′ and QB ∈ Rm×h′ are the matrix of the left- and right- singular vectors corresponding to the first h′ (≤ h) singular values of matrix Σ, respectively. In fact, we perform SVD for the small h×h matrix ¯B¯B⊤ = [PB ˆ PB]Diag[Σ2B 0][P ˆ PB]⊤, where ˆ PB are the eigenvectors of the zero eigenvalues. By the definition of SVD, we have QB = ¯B⊤PBΣB-1 . In addition, we obtain additional ˆ QB ∈ Rm×(h-h′ ) by GramSchmidt orthogonalization based on [QB 1] in which B satisfies B1 = 0. Thus, we have ˆ QB⊤1 = 0. Meanwhile, since QB and ¯B have the same row space, and ¯B1 = 0, so we have Q⊤B1 = 0. We can get [QB ˆQB]⊤1 = 0, which implies X1 = 0. At the same time, we can get XX⊤ = m[PB ˆ PB][QB ˆ QB]⊤[QB ˆ QB][PB ˆ PB]⊤ = mI. We can prove that such X is the optimal solution, which can be referred to [Zhang et al., 2016]. So we can get the closed-form solution of X-subproblem is

Y-subproblem

In this subproblem, we aim to optimize Y with fixed B, D, W, X, Z. The objective of Y-subproblem is:

Similar with X-subproblem, we can derive a closed-form solution as follows:

Algorithm 1 Discrete Trust-aware Matrix Factorization

Input: S: ratings matrix; Γ: trusts matrix; r: code length Output: user,item binary code:B, D

1: Initialization: B, W, X, Z ∈ Rr×m and D, Y ∈ Rr×n 2: while not converge do 3: for i ∈ {1, . . . ,m} do 4: repeat 5: use Eq.(3) to update Bi bit by bit (r bits in total) 6: until bit converge 7: end for 8: for j ∈ {1, . . . , n} do 9: repeat 10: use Eq.(4) to update Dj bit by bit (r bits in total) 11: until bit converge 12: end for 13: for k ∈ {1, . . . ,m} do 14: repeat 15: use Eq.(5) to update Wk bit by bit (r bits in total) 16: until bit converge 17: end for 18: update X by Eq.(6) 19: update Y by Eq.(7) 20: update Z by Eq.(8) 21: end while 22: return B, D to evaluate

Z-subproblem

In this subproblem, we aim to optimize Z with fixed B, D, W, X, Y. The goal of Z-subproblem is:

Similar with X-subproblem, we can get the closed-form solution of Z-subproblem as follows:

3.4 Better Initialization of Discrete Problems

Since our DTMF model deals with a mixed-integer nonconvex optimization problem, better initialization usually contributes to achieving faster convergence and better local optimal solutions, as pointed out by [Zhang et al., 2016; Lian et al., 2017]). This is done by solving the following relaxation optimization problem, i.e., by replacing real-valued variables U, V, F with binary ones B, D, W, respectively.

We can use gradient descent algorithm to solve U-, V-, and W-subproblem, and take the SVD method to solve X-, Y-, and Z-subproblem. Assuming the solutions are denoted by Douban U∗ , V∗ , F∗ , X∗ , Y∗ , Z∗ , we can then initialize the discrete objective function as follows:

Figure 1: Performance (vs. Discrete) of NDCG@K on Epinions and Douban Datasets, respectively

4 Experiments

4.1 Experimental Settings

Datasets and Baselines

Two real-world datasets are used in our experiments, namely Epinions 2 and Douban 3 . Both datasets consist of social networks and rating data. Note that Epinions supports the concept of directed trust, while Douban takes bi-directional friendship as social connections. The statistics of the two datasets are presented in Table 1.

We compare with the following approaches:

• BCCF [Zhou and Zha, 2012]: It is a two-stage binarized collaborative filtering method with a relaxation stage and a quantization stage.
• DCF [Zhang et al., 2016]: It is the first binarized CF method that can jointly optimize the binary codes.
• TrustMF [Yang et al., 2013]: It is a real-valued matrix factorization method based upon both user-item ratings and trust information.

Evaluation method

In our experiments, for each user, we randomly selected 50% as training data and the rest as test data. We perform each experiment five times and report the average results as the final performance. The Normalized Discounted Cumulative Gain

2 http://www.trustlet.org/wiki/Epinions dataset

3 https://www.cse.cuhk.edu.hk/irwin.king.new/pub/data/douban

(NDCG) is used as our evaluation metric to estimate the quality of recommendation accuracy [Valizadegan et al., 2009]. Generally, higher NDCG values indicate better ranking accuracy.

Parameter settings

The parameters of all the methods are either determined by empirical study or suggested by the original paper. Specifically, for BCCF, we tune hyper-parameters λ within [10-4 , . . . , 10-2 ]. The hyper-parameters α and β of DCF are tuned with [10-4 , . . . , 102 ]. For TrustMF, we adopt the parameter settings recommended by the authors: λ = 0.001 and λT = 1. For DTMF proposed in this paper, we search α, β, γ, and λ from [10-4 , . . . , 103 ].

4.2 Results and Analysis

Compared to discrete models

In Figure 1, we give the NDCG@1 to NDCG@10 values for all the compare methods on two datasets, and observe that:

• Compare of BCCF: The performance of BCCF is much lower than that of both DCF and DTMF, which are discrete methods. This is because BCCF is a two-stage discretization method, which brings a large quantization loss. Both DCF and DTMF are joint optimization discrete methods, and thus the characteristics of real-valued and discrete-valued transformation are well preserved.
• Compare of DCF: The results show that our approach DTMF is consistently better than DCF. We attribute it to the underlying assumption that users are socially connected and mutually influenced with each other. Social

ties have a positive impact on recommendation performance. In contrast, DCF assumes that all users are independent identically distributed, which thus ignores the relationships among users.

• Compare of datasets: By comparing the Douban with Epinions dataset, we find that our model DTMF is more improved than DCF and BCCF in the Douban dataset. It may be explained by the fact that Douban provides more social information than Epinions (see Table 1).

Compared to real-valued model

The purpose of this part is to investigate if our discrete DTMF performs closely to the real-valued model, i.e., TrustMF. The results are shown in Figure 2. It can be seen that DTMF reaches very close NDCG values to TrustMF on Epinions, whereas it beats TrustMF on Douban in the case of 32 bits. Note that other results with diffrent bits basically follow the similar trend, and thus we omit them for space saving. The results may be explained in two aspects. First, Douban provides more social information than Epinions (see Table 1), leading to more exposure of user influence on each other. Second, Douban adopts the concept of friendship (bi-directional) while Epinions support the connections of trust (directed). By definition, trust is generally believed a stronger social tie than friendship. Thus, trust-aware real-valued model TrustMF performs worse in Douban, while discrete DTMF may be more applicable in different social datasets because of discretion operations. As a conclusion, discrete trust-aware model achieves comparable or even better performance than the realvalued one, and demonstrates better application to different social ties.

Efficiency study

Recommendation efficiency is an important aspect to study, and the results regrading to data size and code length are depicted in Figure 3. The experiments are executed on Douban due to its greater size. Firstly, we fix the code length as 8 bits, and gradually increase the size of training data. Secondly, we fix the training ratio (50% for training), and then tune the value of code length. Consistently, in both cases, the time required per iteration will be linearly increased, indicating the potential to be applied in large-scale datasets. Besides, we can save the learned model in smaller memory after model training. Note that our results are consistent with the conclusion of existing discrete collaborative filtering models [Zhang et al., 2016; Liu et al., 2018], that is, the recommendation efficiency is much better than that of real-valued counterparts.

As a result, discrete models can reach comparable performance and better efficiency, and thus even suitable for search

problems.

Impact of hyper-parameter

Parameter λ controls the importance of trust modeling for the overall performance, and the results are illustrated in Figure 4. It can be observed that in general tuning values of parameter λ will not greatly change the overall performance. The NDCG values vary in a relatively small range. Nevertheless, a proper setting of parameter λ can help reach the best performance. The optimal setting is also a dataset specific.

5 Conclusions

In this paper, we proposed a novel discrete trust-aware matrix factorization model called DTMF. It took advantages of both hash technique (for better efficiency) and social influence (for better accuracy) to decompose user-item ratings, which mapped both users and items into a joint hamming space. We applied an efficient discrete optimization algorithm to resolve each subproblem of our model alternatively. The results on two real datasets demonstrated that our approach can obtain better efficiency yet preserve comparable (or even better) accuracy in comparison with a number of counterparts.

Acknowledgments

This work is supported by the JD Grapevine Plan and Fundamental Research Funds for the Central Universities under Grant No. N181705007, by the National Natural Science Foundation of China under Grants No. 61772125, No. 61702084, No. 61702090 and No. 61772570, by the Guangdong Natural Science Funds for Distinguished Young Scholar under Grant No. 2018B030306025, Pearl River S&T Nova Program of Guangzhou under Grant No. 201806010056, and by the Fundamental Research Funds for the Central Universities No. N171602003.