On Trivial Solution and Scale Transfer Problems in Graph Regularized NMF

1 Introduction

Nonnegative Matrix Factorization (NMF) [Lee and Seung, 2000] [Li and Ding, 2006] [Xu et al., 2003] [Ding et al., 2006] has received increasing interest in the past decade and achieved great success in document clustering and documentword co-clustering [Dhillon et al., 2003] (clustering documents based on their distribution on words, while grouping words based on their distribution on the documents).

Recently, [Cai et al., 2008] proposed a graph regularized nonnegative matrix factorization (GNMF), which incorporates the geometric structure of the documents into NMF by manifold regularization [Belkin et al., 2006]. [Gu and Zhou, 2009] proposed a Dual Regularized Co-Clustering (DRCC) method based on graph regularized semi-nonnegative matrix tri-factorization [Ding et al., 2010]. They showed that not only the documents but also the words are discrete samplings from some manifolds. By manifold regularization [Belkin et al., 2006], the cluster labels of documents are smooth with respect to the intrinsic document manifold, while the cluster labels of words are smooth with respect to the intrinsic word manifold.

However, both GNMF [Cai et al., 2008] and DRCC [Gu and Zhou, 2009] suffer from the scale transfer problem because the regularization term in the objective function is not lower-bounded. More seriously, when the regularization parameter is too large that the regularization term dominates the objective function, the original optimization problemwill degenerate into a series of independent subproblems associated with each column of the cluster assignment matrix. In this case, the solution of each row of the cluster assignment matrix will be very similar with each other, resulting in trivial clustering result. We will analyze these two problems in detail in the next section. As far as we know, there is no existing principled way to deal with such kinds of problems. In this paper, to solve the problems in a principled way, we propose two models for graph regularized nonnegative matrix (tri-)factorization, which can be respectively applied to document clustering and document-word co-clustering. We impose a Normalized Cut-type [Shi and Malik, 2000] constraint on the cluster assignment matrix, which makes the optimization problem well-defined. We also derive an iterative multiplicative updating algorithm to solve the proposed models. The convergence of the algorithm is theoretically guaranteed. The main contributions of this paper include: (1) we analyze the common problems existing in many previous graph regularized nonnegative matrix (tri-)factorization models, and (2) we propose a principled way to solve these problems. Experiments of clustering and co-clustering on many benchmark data sets demonstrate that the proposed models overcome the problems and outperform the original models as well as many state-of-the-art clustering methods.

1.1 Notations

Given a document set X = {x1, . . . , xn} ∈ Rd , the goal of clustering is to group the documents into c clusters {Cj}cj=1 . And the goal of co-clustering is to group the documents into c clusters {Cj}cj=1 , while grouping the words into m clusters {Wj}mj=1 . We use a cluster assignment matrix V ∈ Rn×c + to represent the clustering result of documents, such that if argmaxj Vij = j ∗ , then xi belongs to cluster Cj∗. We denote the ith row of V by vi , and the jth column of V by vj. Each element in vi can be seen as the probability of the ith document belonging to each clusters, which provides Soft Clustering. In the co-clustering scenario, we introduce another clustering assignment matrix U ∈ Rd×m + to represent the clustering result of words analogously.

2 RelatedWork

In this section, we will review several methods related to ours, and analyze the potential problems that previous works suffer from.

[Cai et al., 2008] proposed a graph regularized NMF (GNMF), which adds an additional graph regularizer on NMF, imposing Manifold Assumption on the data points. That is, if two documents xi and xj are close to each other, then their cluster labels vi and vj should be close as well. This is formulated as follows,

where LV = DV -WV is the graph Laplacian on the document graph,WV is the adjacencymatrix defined on the document graph, DV is a diagonal degree matrix of the document graph with (DV )ii = ∑nj=1 (WV )ij . For example, we can define the adjacencymatrixWV as

where N(xi) denotes the k-nearest neighbor of xi. And GNMF minimizes the following objective,

where μ > 0 is a regularization parameter. Due to the graph regularization term tr(VT LVV), GNMF can take into account the geometric information of the data.

[Gu and Zhou, 2009] proposed a dual regularized coclustering (DRCC) method based on graph regularized (semi)nonnegative matrix factorization [Ding et al., 2010], which imposes graph regularization on both the word and document cluster assignment matrices, i.e.,

where S reflects the association between words and documents, LU = DU - WU is the graph Laplacian on the word graph, WU is the adjacency matrix of the word graph which can be defined similarly as in Eq. (2), DU is the diagonal degree matrix associated with the word graph, with (DU)ii = ∑dj=1 (WU)ij , the definition of LV is the same as above, λ, μ > 0 are regularization parameters. Hereafter, we refer to the model in Eq. (4) as GNMTF for consistency with GNMF. GNMTF not only considers the geometric structure of the documents as in GNMF, but also takes into account the geometric information of the words.

2.1 Trivial Solution Problem

In this subsection, we show that GNMF [Cai et al., 2008] suffers from trivial solution. When μ approaches ∞, the second term dominates the objective function, Eq. (3) boils down to

where vk denotes the k-th column of V. Eq. (5) can be decomposed into c independent optimization subproblems as follows

where k = 1, . . . , c. Thus each optimization gets the same solution up to a scale, i.e., v1 ∝ . . . ∝ vc. This means all elements in each row of V are identical up to a scale. Hence the cluster assignment by V tends to assign all the documents to one class, because the cluster assignment is determined by the largest entry in each row. In reality, due to the existence of the first NMF term in Eq. (3), these elements are not precisely identical up to a scale, but rather slightly fluctuate. Figure 1 shows an illustrative toy example. It can be seen that when μ = 1, the clustering results is correct. However, when μ = 104, the clustering results assign all the documents to cluster 1. Since there is a fluctuation caused by the first NMF term, the scale between column 1 and column 2 of V is not uniformly the same across the rows of V. And when μ = 106, the problem gets worse. The scale to which column 1 equals to column 2 is uniformly 0.73 0.27 .

The same problem exists in GNMTF [Gu and Zhou, 2009]. This motivates us to propose the new formulation presented in this paper.

2.2 Scale Transfer Problem

Another problem that GNMF suffers from is scale transfer problem in the optimization. Suppose {U∗ ,V∗} is the optimal solution for Eq. (3) with optimal objective function value, i.e., J(U∗ , V∗ ). For any real scalar α > 1, the scale transferred solution {αU∗ , V∗ α }, will lead to a "smaller" objective function value,

Thus, the ultimate solution is U∗ = ∞,V∗ = 0 while U∗V∗T remains a fixed value.

The same problem exists in GNMTF [Gu and Zhou, 2009]. To resolve this problem, [Gu and Zhou, 2009] proposed to use ℓ2 normalization on columns of U and V in each iteration during the optimization, and compensate the norms of U and V to S. However, this is not a principled way to solve the problem. We will see that this problem can be resolved in the new formulation proposed in this paper.

3 The ProposedModels

In this section, we present two Nonnegative Matrix (Tri)Factorization models with Graph Regularization, followed by its optimization algorithm. We also prove the convergence of the optimization algorithm.

3.1 Formulation

The key idea to resolve the problem is adding a Normalized Cut [Shi and Malik, 2000] type constraint on V, which leads to the following minimization problem

where I is the identity matrix with proper size, WV is exactly the adjacency matrix defined on the document graph, μ is a positive regularization parameter balancing the reconstruction error in the first NMF term and the label smoothness in the second term. Note that we omit the term μVT DVV as it is a constant, i.e., μI. Hence the regularization term turns out to be -μtr(VT WVV). We can see that the difference between Eq. (8) and Eq. (3) is the additional constraint VT DV = I. The difference is seemingly small, but plays an essential role. With this additional constraint, the optimization problem in Eq. (8) is well-defined and no longer suffers from either scale transfer problem or trivial solution. For example, let μ approach∞, then the second term dominates the objective function, and Eq. (8) boils down to maximize

which can be seen as nonnegative relaxed Normalized Cut.

Similar with the strategy adopted in Eq. (8), we add two additional constraints on U and V to Eq. (4), resulting in the following minimization problem,

where λ, μ ≥ 0 are regularization parameters balancing the reconstruction error of co-clustering in the first term, and the label smoothness of the words and documents in the second and third terms. The additional two constraints, i.e., UT DUU = I and VT DV V = I, are essential to make the optimization in Eq. (10) well-defined and not prone to trivial solutions.

Since the optimization problem in Eq. (8) can be seen as a special case of that in Eq. (10) when absorbing S to U and setting λ = 0, in the sequel, we will develop the optimization algorithm to solve J3, which is a more general problem. The derived optimization algorithm can be adapted to optimize J2 very straightforwardly.

3.2 Optimization Algorithm

Optimizing Eq. (10) with respect to U is equivalent to optimizing

Since UT DU U = I, we introduce the Lagrangian multiplier Λ ∈ Rm×m, thus the Lagrangian function is

The gradient of L(U) with respect to U is

Using the Karush-Kuhn-Tucker complementarity condition [Boyd and Vandenberghe, 2004] ( ∂L(U) ∂U )ijUij = 0, we get

-

Since Λ may take mixed signs, we introduce Λ = Λ+ Λ-, where Λ+ij = (|Λij| + Λij)/2 and Λ-ij = (|Λij| - Λij)/2. Then we get the following updating formula

It remains to determine the Lagrangian multiplier Λ. Following the similar trick used in [Ding et al., 2006], we obtain

However, since UT DUU - I is symmetric, we have tr(Λ(UT DUU - I)) = tr((UT DUU - I)ΛT ) = tr(ΛT (UT DUU - I)). Therefore only the symmetric part of Λ contributes to L(U), i.e., Λ should also be symmetric. Hence we use Λ′ = Λ+ΛT 2 instead of Λ.

Similarly, we can obtain the updating formula for V as

And the updating formula for S is

The iteration in Eq.(15), (17) and (19) terminates until convergence.

3.3 Convergence Analysis

In this section, we prove the convergence of the updating formulas in Eq. (15), Eq. (17) and Eq.(19), using the auxiliary function approach [Lee and Seung, 2000].

Definition 3.1. [Lee and Seung, 2000] Z (h, h′ ) is an auxiliary function for F (h) if the conditions

are satisfied.

Lemma 3.2. [Lee and Seung, 2000] If Z is an auxiliary function for F, then F is non-increasing under the update

Theorem 3.3. Let

by ignoring the term-tr(Λ). Then the following function

Z (U, U′ )

is an auxiliary function for J3(U). Furthermore, it is a convex function in U and its global minimum is

Proof. For the space limit, we omit it. It will be presented in the longer version of this paper.

Theorem 3.4. Updating U using Eq. (15) will monotonically decrease the value of the objective in Eq. (10), hence it converges.

Proof. By Lemma 3.2 and Theorem 3.3, we can get that J3(U0 ) = Z (U0 , U0 ) ≥ Z (U1 , U0 ) ≥ J3(U1 ) ≥ . . .. Thus J3(U) is monotonically decreasing. Since J3(U) is obviously bounded below, the theorem is proved.

The convergence of the updating formulas of V and S can be proved similarly. For the space limit, we omit it.

4 Experiments

In this section, We compare our methods with K-means [Bishop, 2006], Normalized Cut (NCut) [Shi and Malik, 2000], NMF [Lee and Seung, 2000], ONMTF [Ding et al., 2006], GNMF [Cai et al., 2008] and GNMTF [Gu and Zhou, 2009]. For GNMF and GNMTF, we test the un-normalized version, and the version doing ℓ2 normalization on columns of V (and U) in each iteration, which are referred to as GNMF C2 and GNMTF C2. We refer to the proposed model in Eq. (8) as IGNMF and the model in Eq. (10) as IGNMTF.

4.1 Evaluation Metrics

To evaluate the clustering results, we adopt the performance measures used in [Xu et al., 2003]. These performance measures are the standard measures widely used for clustering.

Clustering Accuracy is defined as follows:

where ri denotes the cluster label of xi, and li denotes the true class label, n is the total number of documents, δ(x, y) is the delta function that equals one if x = y and equals zero otherwise, and map(ri) is the permutation mapping function that maps each cluster label ri to the equivalent label from the data set.

Normalized Mutual Information is used for determining the quality of clusters. Given a clustering result, the NMI is estimated by

where ni denotes the number of data contained in the cluster Ci(1 ≤ i ≤ c), ˆnj is the number of data belonging to the Lj(1 ≤ j ≤ c), and ni,j denotes the number of data that are in the intersection between the cluster Ci and the class Lj. The larger the NMI is, the better the clustering result will be.

4.2 Data Sets

In our experiment, we use four data sets which are widely used as benchmark data sets in clustering literature [Ding et al., 2006] [Cai et al., 2005].

CSTR consists of the abstracts of technical reports published in the Department of Computer Science at a university. The data set contained 476 abstracts, which were divided into four research areas: Natural Language Processing (NLP), Robotics/Vision, Systems and Theory.

News4 is selected from the famous 20-newsgroups data set 1 . The topic rec containing autos, motorcycles, baseball and hockey was selected from the version 20news-18828.

WebKB4 contains webpages gathered from university computer science departments. There are about 8280 documents and they are divided into 7 categories: student, faculty, staff, course, project, department and others, among which student, faculty, course and project are four largest entityrepresenting categories.

1 http://people.csail.mit.edu/jrennie/20Newsgroups/

TDT2 consists of articles collected during the first half of 1998 and taken from 6 sources, including 2 newswires, 2 radio programs and 2 television programs. In this experiment, those documents appearing in two or more categories were removed. We use 10 out of 96 semantic categories.

4.3 Parameter Settings

In order to compare these algorithms fairly, we run these algorithms under different parameter settings, and select the best average result to compare with each other. We set the number of clusters equal to the true number of classes for all the data sets and clustering algorithms.

For NCut [Shi and Malik, 2000], the scale parameter of Gaussian kernel for constructing adjacency matrix is set by the grid {10-3, 10-2, 10-1, 1, 10, 102, 103}.

For ONMTF, the number of word clusters is set to be the same as the number of document clusters, i.e., the true number of classes, according to [Ding et al., 2006].

For GNMF, GNMF C2 and IGNMF, the neighborhood size k in Eq. (2) is set to 10 according to the observation in [Cai et al., 2008], and the regularization parameter is set by searching the grid {0.1, 1, 10, 50, 100, 500, 1000}.

For GNMTF, GNMTF C2 and IGNMTF, the number of word clusters is set the same as the number of document clusters, i.e., the true number of classes, as in ONMTF. According to the observation in [Gu and Zhou, 2009], the neighborhood size k of the document graph as well as the word graph is set to 10. We also set λ = μ and tune it by the grid {0.1, 1, 10, 50, 100, 500, 1000}.

Under each parameter setting of each method mentioned above, we repeat clustering 20 times, and the average result is computed. We report the best average result for each method.

4.4 Clustering Results

Table 1 shows the clustering accuracy of all the algorithms on all the data sets, while Table 2 shows the normalized mutual information.

We can see that GNMF C2 is better than GNMF on 2 out of 4 data sets. This implies that to some extent normalization can resolve the problems suffered by GNMF, and in turn improve the performance of GNMF. IGNMF outperforms GNMF and GNMF C2 consistently. This indicates the strength of the proposed model, which benefits from its welldefined optimization problem.

Similarly, GNMTF C2 outperforms GNMTF on 3 out of 4 data sets according to the clustering accuracy. This implies that the scale transfer problem is even more serious in GNMTF, since there are two regularizers, i.e. tr(UT LUU) and tr(VT LVV) in the objective function. Again, IGNMTF is superior to GNMTF and GNMTF C2, because the scale transfer problem is resolved in a principled way in IGNMTF.

GNMTF type methods are superior to GNMF type methods on 3 out of 4 data sets. Similar observation was observed in [Gu and Zhou, 2009]. This verifies the manifold assumption on the words again.

4.5 Study on the Regularization Parameter

In this subsection, we first investigate the sensitivity of GNMF, GNMF C2 (GNMF with ℓ2 normalization on columns of V) and IGNMF with respect to the regularization parameter μ. We vary the value of μ, and plot the average clustering accuracy in Figure 2. For better viewing, we scale μ by log(μ).

Figure 2 shows that when μ is larger than 1, the performance of GNMF declines sharply due to the trivial solution problem. For example, on the CSTR data set, when μ = 50, 100, 500, 1000, the clustering accuracy are all 37.39%.

Since there are 178 documents in the third class, we can see that 178/476 is exactly 37.39%. This means that GNMF assigns all the documents in this data set to the third cluster, which is the trivial solution problem we analyzed in Section 2. Similar phenomenons can be observed in the other 3 data sets. GNMF C2 is able to overcome this problem to certain extent. However, the price of normalization is potential performance decrease. IGNMF performs the best and is not very sensitive to the regularization parameter μ. More importantly, it does not sacrifice its performance to solve the problem.

Second, we study the sensitivity of GNMTF, GNMTF C2 (GNMTF with ℓ2 normalization on columns of U and V), and IGNMTF with respect to the regularization parameter μ(= λ). We vary the value of μ(= λ), and plot the average clustering accuracy with respect to μ(= λ) in Figure 3. Note that the horizontal axis represents log(μ)(= log(λ)).

Figure 3 illustrates that when μ is larger than 0.1, the performance of GNMTF drops off precipitously due to the trivial solution problem. We can see that the problem is even more serious in GNMTF as we pointed above. If we take a closer look, we can also observe that GNMTF assigns all the documents to one cluster when μ is very large, e.g. μ = 50, 100, 500, 1000. GNMTF C2 is able to overcome this problem to some extent, which is consistent with the experimental results in [Gu and Zhou, 2009]. IGNMTF performs best and is very stable with respect to the regularization parameter μ(= λ). This strengthens the advantage of the new formulation in Eq. (10).

5 Conclusions

In this paper, we propose two models for graph regularized nonnegative matrix factorization and graph regularized nonnegative matrix tri-factorization respectively, which overcome the scale transfer problem and trivial solution problem in GNMF and GNMTF. The proposed models can be solved via multiplicative updating algorithm, and its convergence is theoretically guaranteed. Experiments of clustering on many benchmark data sets demonstrate that the proposed models outperform the original models and many other state-of-theart clustering methods.

Acknowledgments

The work was supported in part by NSF IIS-09-05215, U.S. Air Force Office of Scientific Research MURI award FA9550-08-1-0265, and the U.S. Army Research Laboratory under Cooperative Agreement Number W911NF-09-2-0053 (NS-CTA).