Relation Regularized Matrix Factorization

1 Introduction

Matrix factorization (MF) methods [Singh and Gordon, 2008], which try to project objects (entities) into a lowerdimensional latent space, have been widely used for various data analysis applications. 1 One of the most popular MF methods is latent semantic indexing (LSI) [Deerwester et al., 1990], which uses singular value decomposition (SVD) to map the content of documents into a lower-dimensional latent semantic space. The objective is to retain as much information of the documents as possible while simultaneously removing the noise. Subsequent analysis, such as clustering or classification, can be performed based on this latent space representation. Maximum margin matrix factorization (MMMF) [Srebro et al., 2004; Rennie and Srebro, 2005], which can be seen as a regularized version of SVD by controlling the complexity of the factors, 2 has been successfully used for many applications, such as collaborative filtering [Rennie and Srebro, 2005]. Many other variants of MF methods and their applications can be found in [Singh and Gordon, 2008].

1 Due to the page limit constraint, many related MF references are not cited in this paper. We refer the readers to [Singh and Gordon, 2008] for many such references.

Although MF methods have achieved very promising performance in many applications, most of them are designed to handle only one matrix at a time. The matrix can be either the feature representation (content information) of a set of objects (entities), or the link structure (relation information) among a set of objects. For example, LSI was originally proposed for content-based information analysis by performing SVD on the bag-of-words representation of a set of documents, and MMMF has been successfully applied to collaborative filtering which employs only the relationship among a set of entities [Rennie and Srebro, 2005].

However, the data in many applications, such as web pages and research papers, contain both textual content information and relation structure. These two kinds of information often complement each other because they are typically collected at different semantic levels. For example, a citation/reference relation between two papers provides a very strong evidence for them to belong to the same topic, although sometimes they bear low similarity in their content due to the sparse nature of the bag-of-words representation. Similarly, the content information can also provide additional insights about the relation among entities. Hence, naively discarding any one kind of information would not allow us to fully utilize all the relevant information available. Ideally, we should strive for integrating both kinds of information seamlessly into a common framework for data analysis.

In [Zhu et al., 2007], a joint link-content MF method, abbreviated as LCMF here, was proposed to seamlessly integrate content and relation information into an MF framework through a set of shared factors for the factorization of both content and link structures. The authors of LCMF argue that their method is more reasonable than some other simple methods for combining content and link information, such as that in [Kurland and Lee, 2005], which seek to convert one type of information into the other. Experimental results in [Zhu et al., 2007] show that LCMF can outperform other state-of-the-art methods.

2 MMMF can make use of different loss functions. The original MMMF [Srebro et al., 2004] only used the hinge loss, but many subsequent works also used other loss functions such as smooth hinge [Rennie and Srebro, 2005] and squared loss. Here we refer in particular to the squared loss function.

However, the links in different applications might capture different semantics. As a result, the model assumption adopted by LCMF might not be satisfied for some applications, which would cause LCMF to fail in such cases. Let us take a synthetic link structure from [Zhu et al., 2007] as an example to illustrate this point. This example is shown in Figure 1(a), in which there are eight nodes, corresponding to eight entities, and eight directed links. After performing link MF based on Zhu et al. 's method, the entities will be automatically grouped into five clusters, each corresponding to one ellipse in Figure 1(a). The learned latent factors of the entities [Zhu et al., 2007] are shown in Figure 1(b), in which the latent factors for V1 to V8 are listed from the first row to the last row in order. We can see that the entities in each cluster, say V2 and V3, have the same latent factor representation. From this example, it is not difficult to reveal the model assumption behind LCMF: if two entities link to or are linked by one common entity, the two entities will have similar latent factor representations. This is a very promising property if the application scenario indeed satisfies this assumption. One such application is the web page classification task on WebKB [Craven et al., 1998]. For example, the homepages of faculties are always linked by or link to the homepage of the department, but the homepages of two faculties seldom link to each other. The advantage of this property has been verified by the promising accuracy of LCMF on the WebKB data set [Zhu et al., 2007].

However, one problem with LCMF is that the factor representations of two linked entities are not guaranteed to be similar. For example, the latent factor representation of V8 is relatively far away from that of V6 or V7 after LCMF learning. This property is undesirable for many other applications. For example, to classify research papers according to their topic, the citation (link) information is usually very important. More specifically, two papers with a citation relation between them are most likely about the same topic, and consequently, the learned latent factors of two linked papers should be similar. Unfortunately, this cannot be handled well by LCMF, which is also verified by the relatively poor performance of LCMF on the Cora data set [McCallum et al., 2000] for paper classification.

From the analysis above, we can see that there exist at least two types of links with different semantics. In this paper, we call the first type of links, such as those in the WebKB data set, Type I links, and the other type of links, such as those in the Cora data set, Type II links. As discussed above, LCMF can handle well applications with Type I links but not those with Type II links. It is this limitation that has motivated us to pursue research reported in this paper.

We propose in this paper a novel MF method. The basic idea is to make the latent factors of two entities as close as possible if there exists a link between them. More specifically, we utilize relation information to regularize the content MF procedure, resulting in a principled framework which seamlessly integrates content and relation information. We refer to our method as relation regularized matrix factorization, which will be abbreviated as RRMF in the sequel for convenience. To learn the parameters of RRMF, we propose a linear-time algorithm, which makes RRMF suitable for large-scale problems. Furthermore, the learning procedure of RRMF can be proved to be convergent. Experimental results on a data set with Type II links demonstrate that RRMF can dramatically outperform LCMF and other stateof-the-art methods.

Although RRMF is motivated to model Type II links, it can also be used for applications with Type I links by adding a simple step to preprocess the link structure of the data. This will be discussed in detail in the following sections.

2 Relation RegularizedMatrix Factorization

2.1 Notations

We use boldface uppercase letters, such as K, to denote matrices, and boldface lowercase letters, such as z, to denote vectors. The ith row and the jth column of a matrix K are denoted as Ki∗ and K∗j, respectively. Kij denotes the element at the ith row and jth column in K. zi denotes the ith element in z. X denotes the content matrix of size n × m, with n being the number of entities and m the number of features. A is the adjacency matrix of the n entities. D denotes the number of latent factors. I denotes the identity matrix whose dimensionality depends on the context. For a matrix K, K ⪰ 0 means that K is positive semi-definite (psd) and K ≻ 0 means that K is positive definite (pd).

2.2 Model Formulation

Like in LSI [Deerwester et al., 1990], we adopt a similar MF method to approximate the content matrix:

where we use an n × D matrix U and an m × D matrix V to denote the latent D-dimensional representations of all the documents (or entities in a more general case) and words (or features in a more general case), respectively, with Ui∗ for document i and Vj∗ for word j. α is a hyperparameter.

To integrate the relation (link) information into the MF procedure, we use the relations among entities to regularize the latent factors. The basic idea of our method is to make the latent representations of two entities as close as possible if there exists a relation between them. We can achieve this goal by minimizing the following objective function:

where Aij = 1 if there is a relation between entities i and j, and otherwise Aij = 0, and L = D - A is known as the Laplacian matrix [Chung, 1997] with D being a diagonal matrix whose diagonal elements Dii = ∑j Aij , and tr(·) denotes the trace of a matrix.

Combining (1) and (2), we obtain the following objective function which we seek to minimize during learning:

which seamlessly integrates the content information and the relation information into a principled framework. Because we use relation information to regularize the content MF procedure, we call the model in (3) relation regularized matrix factorization, abbreviated as RRMF.

choice between L and ˜L depends on applications. In this paper, the lemmas and theorems are derived based on L, but they also hold for ˜L with slight changes in the derivations.

From (3), it is easy to see that the model assumption behind RRMF is in line with the semantics of Type II links. Hence, RRMF can be expected to achieve good performance for applications with Type II links, such as research paper classification, which will be verified by experiment in Section 3.

On the other hand, RRMF can also be used for applications with Type I links. All we need to do is just to preprocess the link structure in the data with a very simple strategy, but the model and learning algorithms need not be changed. According to the semantics of Type I links, two entities linking to or linked by one common entity will likely be from the same class. One simple way to preprocess the link structure is to artificially add a link between two entities if they link to or are linked by a common entity. The added links will then satisfy the semantics of Type II links. For example, in Figure 1(a), after preprocessing, V2 and V3 will be connected and V6

and V7 will also be connected. Learning RRMF based on these added links is now in line with the underlying semantics. From our experiments on the WebKB data set, we find that RRMF can still achieve performance comparable with LCMF just by adopting the simple link preprocessing strategy as described above.

2.3 Learning

In this subsection, we first prove that the objective function in (3) is convex with respect to (w.r.t.) any one of its parameters, U and V. Then, we propose an alternating projection algorithm to learn the parameters in linear time and show that it is guaranteed to converge to a local optimum.

Convexity of the Objective Function

Theorem 1 f is convex w.r.t. U.

Proof: We first rewrite f as follows: f = 12 ∑ni=1 ∑mj=1 (Xij - Ui∗VT j∗ )2 + 12 ∑Dd=1 UT∗d (αI + βL)U∗d + C1, where C1 is a constant independent of U. Let g = 12 ∑ni=1 ∑mj=1 (Xij - Ui∗VT j∗ )2 = C2 + 12 ∑ni=1 [Ui∗ (∑mj=1 VT j∗Vj∗) UTi∗ - 2 (∑mj=1 XijVj∗) UTi∗ ], where C2 is a constant independent of U. It is easy to see that Gi ≜ ∂ 2 g ∂UTi∗ ∂Ui∗ = ∑mj=1 VT j∗Vj∗, and ∂ 2 g ∂UTi∗ ∂Uk∗ = 0 (if i ̸= k). If we use u = (U1∗,U2∗, . . . ,Un∗)T to denote the vector representation of U, the second-order derivative (Hessian) of g w.r.t. u will be a block-diagonal matrix: Gu ≜ ∂ 2 g ∂u∂uT = diag[G1,G2, . . . ,Gn]. According to Lemma 2, det(Gi) ≥ 0, where det(·) denotes the determinant of a matrix. Because det(Gu) = ∏ni=1 det(Gi) ≥ 0, we can conclude that g is convex w.r.t. U.

Let h = 12 ∑Dd=1 U∗d(αI + βL)UT∗d . If we use a = (UT∗1 ,UT∗2 , . . . ,UT∗D )T to denote another vector representation of U, the Hessian of h w.r.t. a will also be a blockdiagonal matrix: Ha ≜ ∂ 2 h ∂a∂aT = diag[H1, H2, . . . , HD], where Hd is defined as follows: Hd ≜ ∂ 2 h ∂U∗d∂UT∗d = αI + βL. According to Lemma 1, we can conclude that det(Ha) > 0, and hence h is convex w.r.t. U.

Hence, f = g + h + C1 is convex w.r.t. U. ■

Theorem 2 f is convex w.r.t. V.

Proof: We first rewrite f as follows: f = C3 + 12 ∑mj=1 [Vj∗ (∑ni=1 UTi∗Ui∗ + αI) VT j∗ - 2 (∑ni=1 XijUi∗) VT j∗ ], where C3 is a constant independent of V. If we use v = (V1∗,V2∗, . . . ,Vm∗)T

to denote the vector representation of V, the Hessian of f w.r.t. v will be a block-diagonal matrix: Kv ≜ ∂ 2 f ∂v∂vT = diag[K1, K2, . . . , Km], where Kj = ∑ni=1 UTi∗Ui∗ + αI. It is easy to verify that Kj ≻ 0 and Kv ≻ 0. Hence, f is convex w.r.t. V. ■

Learning Strategy

We adopt an alternating projection method to learn the parameters U and V. More specifically, each time we fix one parameter and then update the other one. This procedure will be repeated for several iterations until some termination condition is satisfied. We will prove that the learning algorithm is convergent.

Learning U According to Theorem 1, one straightforward way to learn U is to set the gradient of f w.r.t. U to 0 and solve the corresponding linear system. However, this is computationally demanding if n is large because we have to invert a Hessian matrix of size as large as nD × nD. In this paper, we adopt an alternative strategy to perform optimization on U, which is to optimize one column U∗d at a time with the other columns fixed. Because f is convex w.r.t. U, this alternative strategy will be guaranteed to converge to the optimal solution.

Because f is convex w.r.t. U, f is also convex w.r.t. U∗d with all other variables fixed. Hence, computing the gradient of f w.r.t. U∗d and setting it to 0, we can optimize U∗d by solving the following linear system:

where F(d) = E(d) + αI + βL, and E(d) = diag( ∂ 2 g ∂U1d∂U1d , ∂ 2 g ∂U2d∂U2d , . . . , ∂ 2 g ∂Und∂Und ) with ∂ 2 g ∂Uid∂Uid = ∑mj=1 V 2 jd , and e(d) = (e(d) 1 , e(d) 2 , . . . , e(d) n )T with e(d) i = ∑mj=1 Vjd(Xij -Ui∗VT j∗ + UidVjd).

One direct way to solve the linear system in (4) is to set U∗d = [F(d) ]-1e(d) . However, the computation cost is O(n3 ), which is computationally prohibitive for general text classification applications because n is always very large. Here, we propose to use the steepest descent method [Shewchuk, 1994] to iteratively update U∗d: r(t) = e(d) -

Steepest descent will guarantee the algorithm to converge to the global minimum with the objective function value decreased in each iteration. Suppose the number of nonzero elements in L is M. We can see that the computation cost in each iteration is O(n + M ). If the number of iterations is K, the time complexity will be O(K(n + M )). From our experiments, good performance can be achieved with a small value of K, such as K = 10 in our following experiments. Furthermore, M is typically a constant multiple of n. Hence, the overall complexity is roughly O(n), which is dramatically less than O(n3 ).

Learning V One very nice property of V is that the Hessian Kv is block-diagonal, where each nonzero block corresponds to a row of V. Since the inverse of a block-diagonal matrix can be expressed as the inverse of each block, the update of the whole matrix V can naturally be decomposed into the update of each row Vj∗.

Unlike the learning of U, all the Hessian matrices for different rows of V are equal, i.e., Kj = Kk = K = ∑ni=1 UTi∗Ui∗ + αI. Furthermore, K is a small matrix of size D × D, where D is typically a small number and is less than 50 in our experiments. Hence, we can directly update Vj∗ as follows:Vj∗ = (∑ni=1 XijUi∗)K-1 .

2.4 Convergence and Complexity Analysis

Theorem 3 The learning algorithm will converge.

Proof: (Sketch) In each iteration, the learning algorithm ensures that the objective function value in (3) always decreases. Furthermore, the objective function is bounded below by 0. Hence, the learning algorithm will converge. Because f is not jointly convex w.r.t. U and V, the solution is a local optimum. ■

We have seen that in each iteration, the time required for updating U is O(n), and it is easy to see that the time complexity for updating V is also O(n). In our experiments, typically the algorithm can converge in less than 50 iterations. In fact, we find that 5 iterations are sufficient to achieve good performance. Hence, the overall time complexity of the learning algorithm is O(n).

3 Experiments

3.1 Data Sets and Evaluation Scheme

We use the same data sets, WebKB [Craven et al., 1998] and Cora [McCallum et al., 2000], and the same bag-of-words representation with the same original link structure as those in [Zhu et al., 2007] to evaluate our method. The WebKB data set contains about 6,000 web pages collected from the web sites of computer science departments of four universities (Cornell, Texas, Washington, and Wisconsin). Each web page is labeled with one out of seven categories: student, professor, course, project, staff, department, and "other". It should be noted that to train our RRMF method we adopt the simple preprocessing strategy for the link structure in this data set. That is, if two web pages are co-linked by another common web page, we add a link between these two pages. After preprocessing, all the directed links are converted into undirected links. The characteristics about the WebKB data set are briefly summarized in Table 1.

The Cora data set contains the abstracts and references of about 34,000 research papers from the computer science community. For fair comparison, we adopt the same subset of the data as that in [Zhu et al., 2007] to test our method. The task is to classify each paper into one of the subfields of data structure (DS), hardware and architecture (HA), machine learning

(ML), and programming language (PL). The characteristics of the Cora data set are summarized in Table 2.

As in [Zhu et al., 2007], we adopt 5-fold cross validation to evaluate our method. More specifically, we randomly split the data into five folds (subsets), and then repeat the test five times, in each one of which we use one fold for testing and the other four folds for training. As in [Zhu et al., 2007], the number of factors D is set to 50 for RRMF. The α in (3) is fixed to 1, and β is specified by cross-validation on the training data. After obtaining the factors, a linear support vector machine (SVM) is trained for classification based on the low-dimensional representation, which is the same as the test procedure for the methods in [Zhu et al., 2007]. The average classification accuracies and the standard deviations over the five repeats are adopted as the performance metric.

3.2 Baselines

The methods adopted for our comparative study belong to two classes. The first class contains the baselines used in [Zhu et al., 2007]:

• SVM on content: This method ignores the link structure in the data, and applies SVM only on the content information in the original bag-of-words representation.
• SVMon links: This method ignores the content information, and treats links as the features, i.e, the ith feature is link-to-pagei .
• SVM on link-content: The content features and link features of the two methods above are combined to give the feature representation.
• Directed graph regularization: This is the method introduced in [Zhou et al., 2005], which is only based on the link structure.
• PLSI+PHITS: This method, described in [Cohn and Hofmann, 2000], combines text content information and link structure for analysis.

The second class contains some methods that are most related to RRMF:

• PCA: This method first applies principal component analysis (PCA) on the content information to get a lowdimensional representation, based on which SVM is trained for classification. Because we use PCA to initialize U and V in RRMF, this method serves to demonstrate whether the good performance of RRMF comes from a good initialization value or from the learning procedure of RRMF.
• MMMF: This method applies MF only on the content information, which is a special case of (3) by setting β = 0. It is used to show that the relation information does help a lot in relational data analysis.
• Link-content MF: This is the joint link-content MF method in [Zhu et al., 2007].
• Link-content sup. MF: This is the supervised counterpart of link-content MF by using the data labels to guide the MF procedure, which is introduced in [Zhu et al., 2007].

3.3 Convergence Speed

We use the HA data set to illustrate the convergence speed of RRMF. The objective function values against the iteration number T are plotted in Figure 2(a), from which we can see that RRMF converges very fast. The average classification accuracy of the 5-fold cross validation against T is shown in Figure 2(b). We can see that even though the initial value (corresponding to T = 0) is not satisfactory (accuracy = 65.5%), RRMF can still achieve very promising and stable performance without requiring many iterations. Because we can achieve promising performance when T ≥ 5, we set T = 5 in all our following experiments.

T

(a) Objective function

(b) Accuracy

Figure 2: Convergence properties of RRMF.

3.4 Performance

The Cora data set satisfies the model assumption of RRMF but it does not satisfy the model assumption of link-content MF. We first test RRMF on Cora to verify that when the model assumption is satisfied, RRMF can dramatically outperform link-content MF and other methods. The average classification accuracies with standard deviations are shown in Figure 3, from which we can see that RRMF does outperform other methods dramatically. Even though the linkcontent sup. MF method uses label information for MF, RRMF can still give much better result, showing that it is indeed very effective. Comparing RRMF to PCA, we can see that the good performance of RRMF does not come from a good initialization but from the learning algorithm itself. Comparing RRMF to MMMF, we can see that the relational information is very useful. Comparing RRMF to directed graph regularization, we can see that the content information also does great help for classification.

We also test RRMF on the WebKB data set. Here, we adopt the normalized Laplacian. The performance is shown in Figure 4. It should be noted that the WebKB data set does not satisfy the model assumption of RRMF. However, with simple preprocessing, RRMF can still achieve performance comparable to the link-content MF method and its supervised counterpart, and outperform other methods.

Data Set

Data Set

Figure 4: Average classification accuracies with standard deviations on the WebKB data set.

3.5 Sensitivity to Parameters

We have illustrated the effect of the number of iterations in Section 3.3. Here, we examine the sensitivity of RRMF to β and the number of factors D. We again use the HA data set for illustration. Figure 5 illustrates the accuracy of RRMF when β and D take different values. From Figure 5(a), we can see that the smaller the β, the worse the performance will be. Larger β means that the relational information plays a more significant role in the learning procedure. Hence, we can conclude that the relational information is very important. When β exceeds some value (around 30), the performance becomes very stable, which means RRMF is not sensitive to β. From 5(b), we can see that as D increases, the accuracy also increases. But larger D will incur higher computation cost. Hence, in real applications, we need to consider the tradeoff between computation cost and accuracy.

(a) Effect of β

(b) Effect of D

Figure 5: Sensitivity to parameters of RRMF.

4 Conclusion and FutureWork

In this paper, we propose a novel MF framework, called RRMF, to model relational data of Type II links. One promising property of RRMF is that it can also be used to model data of Type I links just by the inclusion of a very simple preprocessing step. Experimental results verify that RRMF can dramatically outperform other methods on data of Type II links, and can achieve performance comparable with stateof-the-art methods on data of Type I links. Another attractive property of RRMF is that its training time is linear in the number of training entities, which makes it scalable to largescale problems. Moreover, the learning algorithm of RRMF is guaranteed to be convergent and is very stable.

Incorporating label information into RRMF will be pursued in our future work. Furthermore, although the collective classification methods [Sen et al., 2008], latent Wishart processes (LWP) [Li et al., 2009] and relational topic model (RTM) [Chang and Blei, 2009] are not closely related to RRMF, performing experimental comparison between them will be very interesting and will help to reveal the relationships between several approaches of relational learning work which are currently disparate.

Acknowledgements

We thank Shenghuo Zhu for the preprocessed data sets. This research has been supported by General Research Fund 621407 from the Research Grants Council of Hong Kong.