Social Trust Prediction Using Rank-k Matrix Recovery

1 Introduction

The number of registered users on social network web sites has dramatically increased in recent years. Together with the enrollment increases, more frequent activities happen between users. Users daily receive numerous pieces of content generated by other users, and many of these messages need to be evaluated for trustworthiness, thus the question of whom and what to trust has become an even more important challenge on the web. As a result, users resort to trust information to filter and extract external messages and build connections with other users within the community. One of the key features in these social web sites is to allow users to explicitly express their trust or distrust towards other users in some forms, such as accept others' connection request, block malicious users they dislike. These tags (directed edges), together with these users (nodes), can be represented as a trust graph. Here trust graph is a matrix, if user i trusts user j, then the corresponding matrix entry is 1, otherwise 0. Trust prediction is to predict the missing values in the trust graph and can be viewed as a special case of the general link prediction in social networks. The most important differences between trust graphs and general social network graphs are two structure properties, trust graphs could have symmetry property between certain users and the trust links tend to propagate along users. The symmetry comes from the mutual status of the trust relationship, one user tends to trust the other if the other party grants him/her trust. The trust propagation is also easy to see, two users are easier to become friends and cast trust towards each other given they have a common trusted peer.

∗Corresponding Author. This work was partially supported by NSF CCF-0830780, CCF-0917274, DMS-0915228, IIS-1117965, and NIST 70NANB9H9178, 70NANB10H168, 70NANB12H175

Due to the lack of diligence from users' side and privacy concern, missing values in the trust graphs are inevitable. Online users seldom have the time and energy to explicitly tag their friends, the online privacy security meanwhile is becoming a serious issue. Users therefore have very limited number of explicit tags for their online friends. On the other hand, users have the desire to expand their networks and meanwhile maintain their online information and profile security, know whom to trust and whom not to. As a result, it is desirable and often necessary to predict these missing values first to facilitate subsequent mining tasks. There are many algorithms available for general prediction in graphs. In [Liben-Nowell and Kleinberg, 2003], Kleinberg et al. surveyed an array of trust prediction methods and classify them into three categories. The first category is based on node neighborhoods, such as Common Neighbors [Newman, 2001] and Jaccard's coefficient [Salton and McGill, 1983]. The second category is based on the ensemble of all paths, well known methods are Katz [Katz, 1953] and SimRank [Jeh and Widom, 2002]. Low-rank approximations by SVD [Billsus and Pazzani, 1998] or by trace normminimization [Cai et al., 2008] belong to the last category.

Realistic trust graphs carry less than 1% non-zeros. For instance, most Facebook users have less than 1,000 friends, which is far less than 1% considering facebook hundreds of millions of users. This makes the first two categories difficult in practice as we will show in the experiment section. The focus of this paper is the low rank approximation method. The low rank assumption reflects the fact that social network user can be grouped into a small number of clusters based on their background or interest. Trace normminimization [Cai et al., 2008], different from classic SVD method, uses convex matrix trace norm to approximate its rank. However, there are two potential issues with this method. First, the incoherence conditions of the data matrix is often too restrictive, there is no prediction accuracy guarantee when the assumption is not satisfied. The theoretical results in [Cand`es and Recht, 2009; Cand`es and Tao, 2010] assume that the observed entries are sampled uniformly at random. Unfortunately, many realworld data sets exhibit power-law distributed samples instead [Meka et al., 2009]. Furthermore, Shi et al. [Shi and Yu, 2010] pointed out that the yielded solution via trace norm minimization is often not low-rank or unique for practice applications. Second, the sparse entries are prone to the influence of outlying or corrupted observations. There are some work trying to alleviate this issue in literature [Wright et al., 2009].

Users who trust each other are often in the same social circle. It has been discovered in [McPherson et al., 2001], people who are in the same social circle often share similar behavior and tastes due to social influence and behavior adoption. Therefore, individual user's interests and attributes can be inferred from his or her social neighbors [Bedi et al., 2007; Wen and Lin, 2010]. Furthermore, Huang et al. [Huang et al., 2012] discovered it is possible to make accurate personalized recommendation based on trust information. These applications demonstrate the application of trust prediction.

In this paper, we introduce a novel view on robust matrix completion based on low-rank approximation and propose a Robust Rank-k Matrix Completion (RRMC) method. The main contribution of our paper can be summarized as follows.

• Instead of minimizing the trace norm, we recover the data matrix with exact rank-k (k is a low-rank number selected by user). It limits the parameter tuning within a set of integers instead of infinite possible values, which is crucial for real applications.
• Our method explicitly guarantees the low-rank of the recovery matrix and also minimizes the influence of noisy observations.
• We optimize the new objective function in an alternative, iterative way with the adoption of ancillary variables and ALM. Our algorithm has reasonable efficiency and theoretical convergence guarantee.
• Our method is robust to parameter choices and has stable performance.

The rest of the paper is organized as follows: Section 2 presents a brief review on related work and introduces our objective function. Section 3 derives the optimization method and summarizes the algorithm. Empirical experiments on different real data sets are demonstrated in Section 4, and Section 5 concludes the paper.

2 Robust Rank-k Matrix Completion

Given a sufficient number of uniform measurements from the data matrix M ∈ Rn×m, it is natural to recover the low-rank matrix X by solving the following equation:

where Ω is the set holding all indices of observed entries in matrix M. Eq. (1) seeks the simplest explantation to fit the observed data. However, there are two fundamental drawbacks for this approach: (1) This optimization problem is NP-hard; (2) Practical data set rarely satisfy the uniqueness of X.

If a matrix has rank r, then clearly it has exactly r nonzero singular values. As a result, the rank function in Eq. (1) is the number of nonzero singular values. In recent years, Cand`es et al. proposed to use trace norm ‖X‖∗ (the sum of the singular values) to seek a low-rank matrix recovery [Cand`es and Recht, 2009; Cand`es and Tao, 2010]. It is obvious that the trace norm of a matrix is a convex approximation to its rank. The heuristic optimization is as the following

Cand`es et al. proposed Singular Value Thresholding (SVT) algorithm [Cai et al., 2008] to solve Eq. (2). Meanwhile, Cand`es et al. further provided the assumption for a perfect recovery with high probability [Cand`es and Recht, 2009].

Other researchers relaxed the constraints [Fazel, 2002; Ji and Ye, 2009] to allow the recovery errors and make the matrix completion more flexible by solving:

where λ > 0 is the regularity parameter. Regularization by trace norm has been shown to lead to low-rank solution with certain assumptions [Fazel et al., 2001]. However, Shi et al. [Shi and Yu, 2010] pointed out in many cases, such yielded solution is not really low-rank and there might be multiple unstable solutions. In addition to this deficiency, tuning λ in Eq. (3) for trace norm approach is often expensive and difficult.

In this paper, we tackle the rank minimization problem by a new approximation formulation. Instead of minimizing trace norm to get an approximation matrix, we explicitly require its low-rank. Different from conventional rank minimization approaches, we set exact rank as a parameter and provide users freedom to choose an appropriate value. We seek a matrix that fits the observed values appropriately, meanwhile explicitly require the approximation matrix to be low-rank. The proposed objective function is as follows:

where k is a user-specified value. When k is not very large, our method is a good approximation to Eq. (1). The range of the parameter k can be easily decided during the practical applications. Conventional methods generally use ℓ2 norm as discrepancy measure on observed subset, which leads to analytical convenience but often suffers from noise disturbance. Here we use ℓ1 norm to make our method less prone to outlier influence. We call the proposed method as Robust Rank-k Matrix Completion (RRMC) approach.

3 Optimization Algorithm

As mentioned in the above section, the trace norm minimization of a matrix is a convex approximation of its rank minimization problem, therefore there is no guarantee such yielded solution is indeed low-rank when theoretical assumptions are not satisfied. This is a key difference between trace norm minimization approaches and exact rank matrix recovery methods. On the other hand, the low-rank minimization methods for Eq. (1) often involve expensive computation costs.

Our new RRMC objective function in Eq. (4) uses ℓ1 norm to alleviate the outlier influence, meanwhile the rank constraint guarantees the low-rank of the approximation matrix. In the literature of machine learning and its closely related areas, ℓ1 norm has been used for feature selection [Nie et al., 2010; Cai et al., 2011], graph based learning [Nie et al., 2011], and model selection [Shao, 1996; Tibshirani, 1996]. The key advantage of using ℓ1 norm over ℓ2 is that each data point no longer enters the objective function as squared residual error. Optimizing objective function in Eq. (4) is difficult due to ℓ1 norm and the exact rank constraint.

To solve our new objective function, we will derive the optimization algorithm using ancillary variables and Augmented Lagrangian Multiplier (ALM)Methods. ALM [Bertsekas, 2003] were originally proposed for convex problems and recently extended to non-separable, non-convex problems. The main idea is to eliminate equality constraints and instead add a penalty term to the cost function that assigns a very high cost to infeasible points. ALM differs from other penalty-based approaches by simultaneously estimating the optimal solution and Lagrange multipliers in an iterative fashion.

We introduce the ancillary variable Y that approximates X and re-write Eq. (4) into the following one:

where µ is the regularity coefficient that balances the first term and second term in Eq. (5). Λ is used to adjust the discrepancy between X and Y. They are parameters of ALM and their update rules will be provided shortly.

Since Eq. (5) involves two variables X and Y, we solve it in an alternative manner and repeat the following steps until convergence.

When Y is fixed, we get XΩ and XΩc separately. It is easy to get the XΩc formula

as the first term in Eq. (5) is a constant with respect to XΩc .

Optimizing Eq. (5) with respect to XΩ is equivalent to optimizing

We can let ZΩ = XΩ -MΩ and write the above equation into the following one

According to [Liu and Ye, 2009], there is a closed form solution to the following one:

where vectors x, v ∈ Rn , scalar λ > 0. The solution is

where sign(t) is the signum function: if t > 0, sign(t) = 1; if t < 0,sign(t) = -1; and if t = 0, sign(t) = 0.

Now according to the solution Eq. (10) to Eq. (9), we solve Eq. (8) in a decouple way. The solution to Eq. (8) is

where N = max(abs(YΩ - 1µ ΛΩ -MΩ)i - 1µ , 0). Then it is straightforward to get the formula

When X is fixed, optimizing Eq. (5) is equivalent to

Algorithm 1 Robust Rank k Matrix Completion

Input: Available entries MΩ, user specified rank value k. Output: Prediction matrix X

Initialize Y, µ, ρ and Λ

repeat

Update X according to Eq. (6) and Eq. (12)

Update Y according to Eq. (14)

Update µ and Λ according to Eq. (15).

until converged

Assuming the SVD decomposition of X+ 1µ Λ is FSGT , then the solution of Y is

where Sk contains top k largest values and Fk, Gk are the singular vector matrices corresponding to Sk.

Finally, we update Λ and µ:

where ρ > 1 is an ALM method parameter.

The whole algorithm is summarized in Algorithm 1. We use the relative change of objective function value becomes less than 10-4 as the convergence criterion. Readers interest in the detailed convergence proof of algorithm 1 may refer to [Bertsekas, 2003]. Here we provide an intuitive verification due to space constraint. As µ goes infinity, to minimize Eq. (5), we can ignore the first term and get Y = X, which implies the convergence of the algorithm. Note that our algorithm guarantees an asymptotic convergence, i.e., the algorithms converges after certain number of iteration. The exact number of iterations t required clearly depends on both the data attributes and tolerance, nevertheless, it is always below 25 for all of our experiments in this paper. The computation cost for XΩC and XΩ are both of order O(nm) and Y is of order O(nm2 ), therefore the total computational cost is of order O(tnm2 ).

Now we want to discuss the influences of the ALM parameters µ, Λ and ρ to the algorithm convergence. It is easy to see the algorithm converges when the regularity penalty µ is sufficiently large. From Eq. (15), we can see µ grows exponentially, therefore the initial value of µ has little impact given sufficient number of iterations. Similar reasoning applies to Λ, when µ is large enough, Λ in the second term can be ignored. On the other hand, ρ has a significant impact on the convergence speed and objective function value accuracy. A larger ρ value would reduce the computational time but meanwhile compromise the objective function accuracy. Suggested ρ value is between 1.01 and 1.1 [Bertsekas, 2003].

4 Experiments

In this section, we empirically evaluate our method RRMC for the matrix completion effects on a few real data sets. As mentioned in the introduction, matrix completion problem has applications in different disciplines. The remainder part of this section consists of several subsections. In each subsection, we present the necessary background information for each experiment data set and then the corresponding result. To better demonstrate the impressive effect of our method, we also include a few classical competitive methods: SVD, singular value projection 1 (SVP) [Jain et al., 2010], robust PCA 2 (RPCA) [Wright et al., 2009], singular value thresholding 3 (SVT) [Cai et al., 2008], OPTSpace 4 [Keshavan and Montanari, 2010].

Unless specified otherwise, we select the ground truth rank of the recovery matrix from 5 to 20, with increment of 5. Regularity parameter for SVT are tuned from the list {0.001, 0.01, 0.1, 1}. Since the default step size for SVT and SVP would result in divergence for some our data sets, we set them at conservative values. Assuming p is the ratio between observations and number of elements, for SVT, we set τ = 5 √mn , δ = 1 20p ,tol= 10-4 , while for SVP, we set tol= 10-4 , vtol= 10-3 ,verbosity= 1, δ = 1 20p . For SVD, we always initialize the missing entries with 0s, set Y the initialized M for RRMC. Note that RRMC converges within 20 iterations on all of the following data sets. We report results below the average of 20 runs.

4.1 Experiment on Synthetic Data Set

We first evaluate our method against other methods for random low-rank matrices and uniform samples. We generate a random rank 2 matrix M ∈ Rn×n and generate random Bernoulli samples with probability 0.1.

we introduce two evaluation metrics to measure the prediction error, mean average error (MAE) and root mean square error (RMSE), where sd represents the standard deviation. These two metrics are commonly used for matrix completion

We add approximately 10% Gaussian noise and conduct matrix completion experiment as n increases from 1000 to 5000. In Fig. 2(a), it can be observed that SVD is very sensitive to the moderate noise while all other competitive methods are relatively robust. RRMC shows significant improvement in RMSE when n is larger than 2000 nevertheless.

Next we fix the matrix size at 2000 × 2000 but vary the noise level from 5% to 25%. With the increased noise, all methods are more prone to outlier influence. In Fig. 2(b), we can observe RRMC method shows best RMSE at noise level 15% and thereafter. With the increased level noise, the matrix has violated the structure assumptions many methods assumed. In contrast, since RRMC has no requirement on the matrix structure, it shows the most robust performance.

So far, we have completed all experiments on the synthetic data. These experiments show that RRMC is empirically more robust to noise against other methods, also its performance is stable. We will now shift focus on 3 real-world data sets.

1 www.cs.utexas.edu/ pjain/svp/

2 perception.csl.uiuc.edu/matrix-rank/samplecode.html

3 www-stat.stanford.edu/ candes/software.html

4 www.stanford.edu/ raghuram/optspace/code.html

4.2 Experiment on Real Data Sets

The trust graph data sets we use are Epinions [Massa and Avesani, 2006], Wikipedia [Leskovec et al., 2010] and Slashdot [Leskovec et al., 2009]. All above data sets contain directed edges with two edges labels, described as trust link (1) and distrust link (0). One thing needs to point out is that the original data sets only record trust links, therefore most of the distrust links are indeed un-tagged ones. Epinions is a data set that users tag trust/distrust votes based on their opinions on others' reviews on items. Wikipedia records a series of elections that contributors fromWikipedia vote on each other to become administrators. Slashdot carries the users' tag on each other as friends or foes based on their submitted technology news. In summary, Epinions contains about 50,000 users and 490,000 trust links, Wikipedia contains about 7,000 users and 103,000 trust links, Slashdot contains about 80,000 users and 900,000 trust links.

It can be observed that the distributions of links in these data sets are very skewed due to the domination of distrust links. To alleviate the data skewness for fair comparison and keep the computation manageable, we select top 2,000 highest degree users from each data set. Table 1 gives a summary description about the subsets used in our experiment. Note that the subsets still carry a skewed distribution in trust and distrust links.

4.3 Matrix Completion Result on Trust Graphs

To evaluate the matrix completion result for all methods, we have to mask a portion of ground truth values in each trust graph for test purpose. We randomly hide 90% of the true value of links and make prediction based on 10% available entries. We choose 90% missing here to simulate the severe data sparsity real social graphs generally suffer from. The reason is that most users from the online community only explicitly express trust and distrust to a very small fraction of peer users considering total number of users. For each run, after we mask these values, we initiate these positions with random values between 0 and 1, then all methods predict these values with the specified parameters above.

From Table 2, we can observe that RRMC outperforms all other methods in terms of MAE and RMSE on three data sets. There are a few additional discoveries. First, we can see most competitive methods get quite close result except SVD. This is not so surprising since these methods all try to get a low-rank solution. The relatively poor performance for SVD could be due to its vulnerability to extreme sparse observations and the noise. Second, we can see RPCA also gets a relatively better performance due to its adoption of ℓ1 norm.

4.4 Experiment onMethod Parameters

In this part, we show the performance of our method regarding to the parameters in Fig. (3). Specifically, we show prediction error is robust to the choice of λ, the relationship between ρ and number of iterations needed for convergence. It can be concluded that our method is not so sensitive to the choice of parameters. In addition to the above two figures, we also include the performance of RRMC with respect to rank k. RRMC gets optimal performance when k=5 for Epinions, and k=10 for Wikipedia and Slashdot. This confirms our assumption that the trust graph between users could be dominated by a few latent factors.

5 Conclusion

Trust and distrust prediction plays a key role in privacy protection for online users. Such prediction can be modeled as predicting missing elements in the trust matrices. Such matrices are sparse and could have local region symmetric and transitive properties. Conventional matrix completion methods don't work very well on those special link prediction problem.

(b) Wikipedia

(c) Slashdot

In this paper, we propose a robust rank-k matrix completion (RRMC) prediction method that yields prediction matrix with exact rank. Our framework seeks a low-rank matrix and is robust to data noise and potential outliers. Different from trace norm minimization, our method explicitly seeks a low-rank stable matrix. We solve the difficult integer programming problem via introducing an ancillary variable and decomposing the difficult problem into two manageable pieces. The empirical experiments on three trust social graph data sets demonstrate the effectiveness and robustness of our method.

In the future, we will look into pursuing trust prediction from a different perspective. In this paper, we generate trust prediction in the continuous domain. However, for many user, providing explicit instruction whether to trust or not is preferable. In other words, we may seek low-rank matrix completion in the discrete domain.