Graph Regularized Nonnegative Matrix Factorization for Data Representation

Deng CaiXiaofei HeJiawei HanThomas S. Huang

article2011TPAMI1,920 citations

Proposes a graph-regularized nonnegative matrix factorization algorithm that preserves the intrinsic geometric structure of high-dimensional data by incorporating a nearest-neighbor graph into parts-based representation learning.

Listen

Modern data analysis tasks in pattern recognition, computer vision, and information retrieval routinely handle high-dimensional datasets such as images and text corpora. Standard Non-negative Matrix Factorization has gained widespread use because its additive constraints naturally learn parts-based, interpretable representations of data. However, traditional factorization methods assume that data resides in a flat Euclidean space, failing to capture the underlying geometric and manifold structures where nearby data points should share similar representations.

To address this limitation, the article introduces and evaluates Graph Regularized Non-negative Matrix Factorization. This framework incorporates an affinity graph to model the local geometric manifold of the data space into the matrix factorization process, enforcing the principle that points close to each other in the original space remain close in the reduced representation space.

The researchers developed iterative multiplicative optimization rules with proven convergence and evaluated the method against standard matrix factorization, spectral clustering, and subspace techniques across three benchmark datasets: the COIL20 object image library, the CMU PIE facial database, and the TDT2 text corpus comprising 9,394 documents. Performance was measured primarily using clustering accuracy and normalized mutual information across various cluster numbers and neighborhood configurations.

The experimental findings show that the proposed regularized approach consistently outperforms all baseline methods across every tested dataset. On the COIL20 image dataset, average accuracy reached 82.5 percent compared to 68.9 percent for standard factorization and 76.2 percent for spectral clustering. On the CMU PIE facial database, average accuracy reached 77.4 percent compared to 63.3 percent for baseline factorization and 25.9 percent for standard k-means. On the TDT2 document corpus, the method achieved an average accuracy of 92.0 percent versus 80.4 percent for standard non-negative factorization and 67.7 percent for singular value decomposition. Furthermore, the learned basis representations demonstrated higher sparsity and visual interpretability, and the optimization converged rapidly, typically within 100 iterations.

These results demonstrate that capturing intrinsic data geometry while enforcing non-negativity significantly improves representation quality and downstream clustering performance. Practitioners can achieve higher clustering precision and topic separation with minimal added computational overhead due to the sparsity of the nearest neighbor graph. The approach also offers a flexible framework that can incorporate domain knowledge such as class labels or network structures.

Organizations implementing this method should select weighting schemes tailored to data types, such as dot-product cosine weighting for text and heat-kernel weighting for images, while keeping the neighbor parameter low to avoid connecting disparate data categories. Future work should focus on automating parameter selection, particularly for regularization strength and heat kernel width, and adapting the method to capture angular similarity rather than purely Euclidean distances.

University of Illinois Urbana-Champaign Zhejiang University computer vision matrix factorizations non-negative matrix factorization Graph Regularized Nonnegative Matrix Factorization data representation manifold regularization

Cai et al (2011).pdf

Paper: Algorithms for Non-negative Matrix Factorization, Daniel D. Lee et al. (2000). Read this foundational account of NMF’s multiplicative updates and convergence first; the source adapts that factorization framework by adding graph-based regularization.
Paper: Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering, Mikhail Belkin et al. (2001). Its construction of a neighborhood graph and Laplacian to preserve local manifold structure provides the geometric machinery the source incorporates into NMF.
Paper: Graph Embedding and Extensions: A General Framework for Dimensionality Reduction, Shuicheng Yan et al. (2007). This graph-embedding framework clarifies how an affinity graph encodes desired relationships between data points, the principle the source uses to regularize learned representations.
Paper: Document clustering based on non-negative matrix factorization, Wei Xu et al. (2003). Its application of NMF to document clustering, including graph-based weighting, gives useful prior context for the source’s graph-regularized factorization experiments.

No sufficiently relevant recommendations were found.

Cover for Graph Regularized Nonnegative Matrix Factorization for Data Representation

Abstract

Matrix factorization techniques have been frequently applied in information retrieval, computer vision and pattern recognition. Among them, Non-negative Matrix Factorization (NMF) has received considerable attention due to its psychological and physiological interpretation of naturally occurring data whose representation may be parts-based in the human brain. On the other hand, from the geometric perspective, the data is usually sampled from a low dimensional manifold embedded in a high dimensional ambient space. One hopes then to find a compact representation which uncovers the hidden semantics and simultaneously respects the intrinsic geometric structure. In this paper, we propose a novel algorithm, called Graph Regularized Non-negative Matrix Factorization (GNMF), for this purpose. In GNMF, an affinity graph is constructed to encode the geometrical information, and we seek a matrix factorization which respects the graph structure. Our empirical study shows encouraging results of the proposed algorithm in comparison to the state-of-the-art algorithms on real world problems.

Topics

computer vision matrix factorizations non-negative matrix factorization semantics graph structures low-dimensional manifolds

Keywords

Graph Regularized Nonnegative Matrix Factorization data representation manifold regularization spectral graph theory spectral clustering nearest neighbor graph Graph Laplacian dimensionality reduction algorithms manifold learning parts-based representation

1 Introduction
2 A Brief Review of NMF
3 Graph Regularized Non-negative Matrix Factorization
3.1 NMF with Manifold Regularization
3.2 Updating Rules Minimizing Eq. (6)
3.3 Connection to Gradient Descent Method
3.4 Updating Rules Minimizing Eq. (7)
3.5 Computational Complexity Analysis
4 Experimental Results
4.1 Data Sets
4.2 Compared Algorithms
4.3 Clustering Results
4.4 Parameters Selection
4.5 Weighting Scheme Selection
4.6 Convergence Study
4.7 Sparseness Study
5 Conclusions and Future Work
Acknowledgments
Appendix A (Proofs of Theorem 1)
Appendix B (Proofs of Theorem 2)
Appendix C (Weighted NMF and GNMF)
References

Knowls

Knowl 1 — Graph Regularized Non-negative Matrix Factorization (Frobenius Norm Formulation)
model/method
Graph Regularized Non-negative Matrix Factorization (GNMF) seeks a parts-based low-dimensional representation of non-negative data that respects the underlying geometric manifold structure.

Given a non-negative data matrix $X = [\mathbf{x}_1, \dots, \mathbf{x}_N] \in \mathbb{R}^{M \times N}$ containing $N$ data vectors of dimension $M$ , GNMF approximates $X$ by the product of two low-rank non-negative matrices $U = [u_{ik}] \in \mathbb{R}^{M \times K}$ and $V = [v_{jk}] \in \mathbb{R}^{N \times K}$ (where $K \ll \min(M, N)$ ):

$X \approx U V^T$

Here, $U = [\mathbf{u}_1, \dots, \mathbf{u}_K]$ represents the basis vectors, and the $j$ -th row of $V$ , denoted $\mathbf{z}_j = [v_{j1}, \dots, v_{jK}]^T$ , represents the coordinates of $\mathbf{x}_j$ with respect to basis $U$ .

To preserve local manifold invariance, an affinity graph with symmetric weight matrix $W \in \mathbb{R}^{N \times N}$ is constructed over the data points. The smoothness of the low-dimensional representation is measured by:

$R_1 = \frac{1}{2} \sum_{j,l=1}^N \|\mathbf{z}_j - \mathbf{z}_l\|^2 W_{jl} = \text{Tr}(V^T D V) - \text{Tr}(V^T W V) = \text{Tr}(V^T L V)$

where $D$ is a diagonal degree matrix with $D_{jj} = \sum_{l=1}^N W_{jl}$ , and $L = D - W$ is the graph Laplacian.

Under the Frobenius norm (Euclidean distance) formulation, GNMF minimizes the objective function:

$\mathcal{O}_1 = \|X - UV^T\|_F^2 + \lambda \text{Tr}(V^T L V)$

subject to the non-negativity constraints $U \ge 0$ and $V \ge 0$ , where $\lambda \ge 0$ is a regularization parameter controlling the smoothness of the representation along the manifold.
Knowl 2 — Multiplicative Update Algorithm for Frobenius Norm GNMF
algorithm
The objective function $\mathcal{O}_1 = \|X - UV^T\|_F^2 + \lambda \text{Tr}(V^T L V)$ is not jointly convex in $U$ and $V$ , but local minima can be found via alternating multiplicative updates. The updates are guaranteed to keep the factor matrices non-negative and monotonically non-increase the objective function $\mathcal{O}_1$ at each iteration.
Input: Data matrix $X \in \mathbb{R}^{M \times N}$ with $X \ge 0$ , number of factors $K$ , regularization parameter $\lambda \ge 0$ , weight matrix $W \in \mathbb{R}^{N \times N}$ , degree matrix $D = \text{diag}(\sum_l W_{jl})$ , max iterations $T$ , convergence threshold $\epsilon$
Output: Non-negative basis matrix $U \in \mathbb{R}^{M \times K}$ and representation matrix $V \in \mathbb{R}^{N \times K}$
Initialize $U \ge 0$ and $V \ge 0$ randomly
for $t = 1$ to $T$ do
    Update $U$ entry-wise:
     $u_{ik} \leftarrow u_{ik} \frac{(XV)_{ik}}{(UV^T V)_{ik}}$

    Update $V$ entry-wise:
     $v_{jk} \leftarrow v_{jk} \frac{(X^T U + \lambda W V)_{jk}}{(V U^T U + \lambda D V)_{jk}}$

    if convergence criterion met then
        break
    end if
end for
Normalize basis vectors and rescale coefficients:
for $k = 1$ to $K$ do
     $s_k \leftarrow \sqrt{\sum_{i=1}^M u_{ik}^2}$
    for $i = 1$ to $M$ do
         $u_{ik} \leftarrow u_{ik} / s_k$
    end for
    for $j = 1$ to $N$ do
         $v_{jk} \leftarrow v_{jk} \cdot s_k$
    end for
end for
return $U, V$
These multiplicative updates correspond to gradient descent with entry-specific learning rates $\eta_{ik} = \frac{u_{ik}}{2(UV^T V)_{ik}}$ and $\delta_{jk} = \frac{v_{jk}}{2(VU^T U + \lambda DV)_{jk}}$ , which automatically guarantee non-negativity without step-size search.
Knowl 3 — Divergence Formulation and Conjugate Gradient Updates for GNMF
model/method
When Kullback-Leibler (KL) divergence is used to measure reconstruction error and symmetric divergence measures representation smoothness, the GNMF objective function is defined as:

$\mathcal{O}_2 = \sum_{i=1}^M \sum_{j=1}^N \left( x_{ij} \log \frac{x_{ij}}{\sum_{k=1}^K u_{ik} v_{jk}} - x_{ij} + \sum_{k=1}^K u_{ik} v_{jk} \right) + \frac{\lambda}{2} \sum_{j=1}^N \sum_{l=1}^N \sum_{k=1}^K \left( v_{jk} \log \frac{v_{jk}}{v_{lk}} + v_{lk} \log \frac{v_{lk}}{v_{jk}} \right) W_{jl}$

subject to $u_{ik} \ge 0$ and $v_{jk} \ge 0$ .

The objective function $\mathcal{O}_2$ is non-increasing under the following alternating updates:
1. Update for $U$ : $u_{ik} \leftarrow u_{ik} \frac{\sum_{j=1}^N \left( x_{ij} v_{jk} / \sum_{k'=1}^K u_{ik'} v_{jk'} \right)}{\sum_{j=1}^N v_{jk}}$
2. Update for each column $\mathbf{v}_k = [v_{1k}, \dots, v_{Nk}]^T$ of $V$ : $\left( \sum_{i=1}^M u_{ik} I + \lambda L \right) \mathbf{v}_k = \mathbf{w}_k$ where $I$ is the $N \times N$ identity matrix, $L = D - W$ is the graph Laplacian, and the $j$ -th element of $\mathbf{w}_k$ is: $w_{jk} = v_{jk} \sum_{i=1}^M \frac{x_{ij} u_{ik}}{\sum_{k'=1}^K u_{ik'} v_{jk'}}$
Because $\sum_{i=1}^M u_{ik} I + \lambda L$ is symmetric, positive-definite, and sparse, the linear system for each $\mathbf{v}_k$ ( $1 \le k \le K$ ) is solved directly using the Conjugate Gradient (CG) algorithm without explicitly computing matrix inverses.
Knowl 4 — Graph Construction and Weighting Schemes in GNMF
definition
GNMF models the local geometry of the data manifold by constructing a $p$ -nearest neighbor graph on the $N$ sample vertices. An edge is placed between vertex $j$ and vertex $l$ if $\mathbf{x}_j$ is among the $p$ nearest neighbors of $\mathbf{x}_l$ , or if $\mathbf{x}_l$ is among the $p$ nearest neighbors of $\mathbf{x}_j$ .

The weight matrix $W \in \mathbb{R}^{N \times N}$ can be constructed using three schemes:
1. 0-1 Weighting: $W_{jl} = \begin{cases} 1, & \text{if } \mathbf{x}_j \text{ and } \mathbf{x}_l \text{ are connected} \\ 0, & \text{otherwise} \end{cases}$
2. Heat Kernel Weighting (suitable for image representations): $W_{jl} = \begin{cases} \exp\left( -\frac{\|\mathbf{x}_j - \mathbf{x}_l\|^2}{\sigma} \right), & \text{if } \mathbf{x}_j \text{ and } \mathbf{x}_l \text{ are connected} \\ 0, & \text{otherwise} \end{cases}$ where $\sigma > 0$ is the heat kernel width parameter.
3. Dot-Product Weighting (suitable for unit-normalized document vectors, corresponding to cosine similarity): $W_{jl} = \begin{cases} \mathbf{x}_j^T \mathbf{x}_l, & \text{if } \mathbf{x}_j \text{ and } \mathbf{x}_l \text{ are connected} \\ 0, & \text{otherwise} \end{cases}$
Knowl 5 — Normalized Cut Weighted Formulation of GNMF
model/method
To handle non-uniform sample importance as in Normalized Cut spectral clustering, a weighted variant of GNMF assigns each data point $\mathbf{x}_j$ a positive scalar weight $\gamma_j$ . The weighted GNMF objective is:

$\mathcal{O}' = \sum_{j=1}^N \gamma_j \|\mathbf{x}_j - U \mathbf{z}_j\|^2 + \lambda \text{Tr}(V^T L V) = \text{Tr}\left((X - UV^T) \Gamma (X - UV^T)^T\right) + \lambda \text{Tr}(V^T L V)$

where $\Gamma = \text{diag}(\gamma_1, \dots, \gamma_N) \in \mathbb{R}^{N \times N}$ is the diagonal weight matrix.

By defining transformed variables: $X' = X \Gamma^{1/2}, \quad V' = \Gamma^{1/2} V, \quad L' = \Gamma^{-1/2} L \Gamma^{-1/2}$

the objective transforms directly into standard GNMF form:

$\mathcal{O}' = \text{Tr}\left((X' - UV'^T)(X' - UV'^T)^T\right) + \lambda \text{Tr}(V'^T L' V')$

For Normalized Cut Weighted GNMF (GNMF-NCW), the sample weights are chosen as $\Gamma = D_X^{-1}$ , where $D_X = \text{diag}(X^T X \mathbf{e})$ and $\mathbf{e}$ is a vector of all ones. The standard GNMF multiplicative update rules apply directly by substituting $X'$ , $V'$ , and $L'$ .

Knowl 6 — Computational Complexity and Arithmetic Operation Counts of GNMF

data/table

Due to the sparsity of the $p$ -nearest neighbor graph weight matrix $W$ (which has on average $p$ non-zero elements per row), matrix-vector multiplications involving $W$ require only $N p K$ floating-point multiplications and additions (flams).

The table below details the exact operation counts per iteration for NMF and GNMF under both Frobenius norm (F-norm) and KL-divergence formulations, where $M$ is the feature dimension, $N$ is the number of samples, $K$ is the number of factors, $p$ is the number of nearest neighbors, and $q$ is the number of Conjugate Gradient iterations ( $q \le 20$ in practice):

F-norm formulation
Method	fladd	flmlt	fldiv	Overall Complexity
NMF	$2MNK + 2(M+N)K^2$	$2MNK + 2(M+N)K^2 + (M+N)K$	$(M+N)K$	$\mathcal{O}(MNK)$
GNMF	$2MNK + 2(M+N)K^2 + N(p+3)K$	$2MNK + 2(M+N)K^2 + (M+N)K + N(p+1)K$	$(M+N)K$	$\mathcal{O}(MNK)$
Divergence formulation
NMF	$4MNK + (M+N)K$	$4MNK + (M+N)K$	$2MN + (M+N)K$	$\mathcal{O}(MNK)$
GNMF	$4MNK + (M+2N)K + q(p+4)NK$	$4MNK + (M+N)K + Np + q(p+4)NK$	$2MN + MK$	$\mathcal{O}\left((M + q(p+4))NK\right)$

Including the initial $\mathcal{O}(N^2 M)$ cost to construct the $p$ -nearest neighbor graph, the total time complexity across $t$ multiplicative update iterations is $\mathcal{O}(tMNK + N^2 M)$ for F-norm GNMF and $\mathcal{O}\left(t(M + q(p+4))NK + N^2 M\right)$ for Divergence GNMF.

Knowl 7 — Clustering Performance of GNMF vs. Baseline Algorithms

data/table

The clustering capability of GNMF (F-norm formulation, 0-1 weighting, $p=5$ , $\lambda=100$ ) was evaluated against canonical Kmeans, Principal Component Analysis/SVD subspace Kmeans, Normalized Cut (NCut), and standard NMF (NCW weighted). Evaluations were performed on three benchmark datasets:

COIL20: 1,440 images ( $32 \times 32$ ), 1,024 features, 20 object classes.
CMU PIE: 2,856 facial images ( $32 \times 32$ ), 1,024 features, 68 persons under variable lighting.
TDT2: 9,394 document vectors, 36,771 features, 30 semantic categories.

Clustering performance is measured by Accuracy (AC, %) and Normalized Mutual Information (NMI, %) averaged over 20 random test runs across varying cluster numbers $K$ :

Dataset	Metric	Kmeans	PCA / SVD	NCut	NMF	GNMF
COIL20	Avg. AC (%)	68.3	69.1	76.2	68.9	82.5
	Avg. NMI (%)	73.6	74.0	79.2	72.7	88.4
PIE	Avg. AC (%)	25.9	26.3	73.6	63.3	77.4
	Avg. NMI (%)	48.5	48.6	83.6	79.9	88.3
TDT2	Avg. AC (%)	66.8	67.7	81.9	80.4	92.0
	Avg. NMI (%)	75.0	72.5	81.7	82.4	86.9

GNMF consistently outperforms both standard NMF (which neglects manifold geometry) and spectral clustering (NCut), confirming that integrating additive non-negative factorizations with graph Laplacian manifold regularization improves data representation for clustering.

Knowl 8 — Sensitivity of GNMF to Regularization Parameter $\lambda$ and Neighborhood Size $p$
empirical result
GNMF clustering performance exhibits distinct sensitivity patterns with respect to its two key hyperparameters:
1. Regularization Parameter $\lambda$ : GNMF demonstrates high stability over a wide range of values for $\lambda$ . Across the COIL20, CMU PIE, and TDT2 datasets, clustering accuracy remains consistently high and superior to baseline methods when $\lambda$ is varied from $10$ to $1000$ (with $\lambda = 100$ serving as a robust default).
2. Number of Nearest Neighbors $p$ : GNMF performance generally decreases as the neighborhood size $p$ increases beyond a small value (e.g., $p=5$ ). Because the manifold regularization assumption relies on local neighbors belonging to the same underlying semantic cluster/class, larger values of $p$ increase the likelihood of introducing cross-class edges into the affinity graph, violating local label consistency.
Knowl 9 — Influence of Graph Weighting Schemes on Large Neighborhood Robustness
empirical result
When using simple 0-1 weighting, GNMF treats all $p$ neighbors equally, which causes clustering accuracy to drop sharply as $p$ grows large (e.g., dropping significantly on TDT2 when $p > 9$ ).

Continuous distance-sensitive weighting schemes alleviate this problem by penalizing farther neighbors:
- Dot-Product (Cosine) Weighting on Text (TDT2): Performance remains consistently high as $p$ increases up to 23, dramatically outperforming 0-1 weighting at large neighborhood sizes.
- Heat Kernel Weighting on Images (COIL20): Heat kernel weighting (tested with $\sigma=0.2$ and $\sigma=0.5$ ) maintains higher accuracy than 0-1 weighting across all $p \in [3, 10]$ , mitigating performance degradation as neighborhood size increases.
Knowl 10 — Sparseness and Parts-Based Basis Representations Learned by GNMF
empirical result
Although theoretical non-negativity in standard NMF is intended to produce parts-based representations, empirical basis vectors learned by standard NMF often remain relatively holistic.

Visualizing the learned basis vectors (the column vectors $\mathbf{u}_k$ of $U$ ) as $32 \times 32$ images on COIL20 and CMU PIE shows that GNMF learns significantly sparser and more localized basis vectors than standard NMF. By enforcing local manifold smoothness via the graph Laplacian regularizer, GNMF better isolates localized semantic parts of objects (such as facial features or object components) without requiring explicit $\ell_1$ sparsity constraints on $U$ or $V$ .

Coverage note — None was omitted; all key theoretical formulations, update algorithms, proofs/convergence theorems, computational complexity analyses, and empirical clustering evaluations were captured.

References

1.M. Belkin and P. Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in Neural Information Processing Systems 14, pages 585–591. MIT Press, Cambridge, MA, 2001. 1, 3
2.M. Belkin, P. Niyogi, and V. Sindhwani. Manifold regularization: A geometric framework for learning from examples. Journal of Machine Learning Research, 7:2399–2434, 2006. 1, 2, 3
3.J.-P. Brunet, P. Tamayo, T. R. Golub, and J. P. Mesirov. Metagenes and molecular pattern discovery using matrix factorization. Proceedings of the National Academy of Sciences, 101(12):4164–4169, 2004. 3
4.D. Cai, X. He, and J. Han. Document clustering using locality preserving indexing. IEEE Transactions on Knowledge and Data Engineering, 17(12):1624–1637, December 2005. 8
5.D. Cai, X. He, X. Wang, H. Bao, and J. Han. Locality preserving nonnegative matrix factorization. In Proc. 2009 Int. Joint Conference on Artificial Intelligence (IJCAI’09), 2009. 2
6.D. Cai, X. He, X. Wu, and J. Han. Non-negative matrix factorization on manifold. In Proc. Int. Conf. on Data Mining (ICDM’08), 2008. 2
7.D. Cai, X. Wang, and X. He. Probabilistic dyadic data analysis with local and global consistency. In Proceedings of the 26th Annual International Conference on Machine Learning (ICML’09), pages 105–112, 2009. 2, 3
8.M. Catral, L. Han, M. Neumann, and R. Plemmons. On reduced rank nonnegative matrix factorization for symmetric nonnegative matrices. Linear Algebra and Its Applications, 393:107–126, 2004. 4
9.F. R. K. Chung. Spectral Graph Theory, volume 92 of Regional Conference Series in Mathematics. AMS, 1997. 3, 4
10.T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press and McGraw-Hill, 2nd edition, 2001. 5
11.S. C. Deerwester, S. T. Dumais, T. K. Landauer, G. W. Furnas, and R. A. harshman. Indexing by latent semantic analysis. Journal of the American Society of Information Science, 41(6):391–407, 1990. 1, 7
12.A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society. Series B (Methodological), 39(1):1–38, 1977. 11
13.C. Ding, T. Li, and W. Peng. Nonnegative matrix factorization and probabilistic latent semantic indexing: Equivalence, chi-square statistic, and a hybrid method. In Proc. 2006 AAAI Conf. on Artificial Intelligence (AAAI-06), 2006. 2
14.D. Donoho and V. Stodden. When does non-negative matrix factorization give a correct decomposition into parts? In Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA, 2003. 10
15.R. O. Duda, P. E. Hart, and D. G. Stork. Pattern Classification. Wiley-Interscience, Hoboken, NJ, 2nd edition, 2000. 1
16.L. Finesso and P. Spreij. Nonnegative matrix factorization and i-divergence alternating minimization. Linear Algebra and Its Applications, 416(2-3):270–287, 2006. 5
17.E. Gaussier and C. Goutte. Relation between plsa and nmf and implications. In SIGIR ’05: Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, pages 601–602, 2005. 2
18.R. Hadsell, S. Chopra, and Y. LeCun. Dimensionality reduction by learning an invariant mapping. In Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’06), pages 1735–1742, 2006. 1
19.X. He and P. Niyogi. Locality preserving projections. In Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA, 2003. 3
20.M. R. Hestenes and E. Stiefel. Methods of conjugate gradients for solving linear systems. Journal of Research of the National Bureau of Standards, 49(6), 1952. 6
21.T. Hofmann. Unsupervised learning by probabilistic latent semantic analysis. Machine Learning, 42(1-2):177–196, 2001. 2
22.P. O. Hoyer. Non-negative sparse coding. In Proc. IEEE Workshop on Neural Networks for Signal Processing, pages 557–565, 2002. 9
23.P. O. Hoyer. Non-negative matrix factorizaiton with sparseness constraints. Journal of Machine Learning Research, 5:1457–1469, 2004. 9
24.I. T. Jolliffe. Principal Component Analysis. Springer-Verlag, New York, 1989. 7
25.J. Kivinen and M. K. Warmuth. Additive versus exponentiated gradient updates for linear prediction. In STOC ’95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, pages 209–218, 1995. 5
26.D. D. Lee and H. S. Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 401:788–791, 1999. 1, 2, 3, 9
27.D. D. Lee and H. S. Seung. Algorithms for non-negative matrix factorization. In Advances in Neural Information Processing Systems 13. 2001. 2, 3, 4, 5, 10, 11
28.J. M. Lee. Introduction to Smooth Manifolds. Springer-Verlag New York, 2002. 1
29.S. Z. Li, X. Hou, H. Zhang, and Q. Cheng. Learning spatially localized, parts-based representation. In 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’01), pages 207–212, 2001. 1, 3
30.C.-J. Lin. On the convergence of multiplicative update algorithms for non-negative matrix factorization. IEEE Transactions on Neural Networks, 18(6):1589–1596, 2007. 4, 10
31.N. K. Logothetis and D. L. Sheinberg. Visual object recognition. Annual Review of Neuroscience, 19:577–621, 1996. 1
32.A. Y. Ng, M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In Advances in Neural Information Processing Systems 14, pages 849–856. MIT Press, Cambridge, MA, 2001. 6
33.P. Paatero and U. Tapper. Positive matrix factorization: A non-negative factor model with optimal utilization of error estimates of data values. Environmetrics, 5(2):111–126, 1994. 1, 2
34.S. E. Palmer. Hierarchical structure in perceptual representation. Cognitive Psychology, 9:441–474, 1977. 1
35.S. Roweis and L. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323–2326, 2000. 1
36.H. S. Seung and D. D. Lee. The manifold ways of perception. Science, 290(12), 2000. 1
37.F. Shahnaza, M. W. Berrya, V. Paucab, and R. J. Plemmonsb. Document clustering using nonnegative matrix factorization. Information Processing & Management, 42(2):373–386, 2006. 6
38.J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888–905, 2000. 7
39.J. Tenenbaum, V. de Silva, and J. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319–2323, 2000. 1
40.M. Turk and A. Pentland. Eigenfaces for recognition. Journal of Cognitive Neuroscience, 3(1):71–86, 1991. 1
41.E. Wachsmuth, M. W. Oram, and D. I. Perrett. Recognition of objects and their component parts: Responses of single units in the temporal cortex of the macaque. Cerebral Cortex, 4:509–522, 1994. 1
42.W. Xu, X. Liu, and Y. Gong. Document clustering based on non-negative matrix factorization. In Proc. 2003 Int. Conf. on Research and Development in Information Retrieval (SIGIR’03), pages 267–273, Toronto, Canada, Aug. 2003. 1, 3, 4, 6, 7, 12, 13
43.L. Zelnik-manor and P. Perona. Self-tuning spectral clustering. In Advances in Neural Information Processing Systems 17, pages 1601–1608. MIT Press, 2004. 9
44.H. Zha, C. Ding, M. Gu, X. He, and H. Simon. Spectral relaxation for k-means clustering. In Advances in Neural Information Processing Systems 14, pages 1057–1064. MIT Press, Cambridge, MA, 2001. 7
45.D. Zhou, O. Bousquet, T. Lal, J. Weston, and B. Schölkopf. Learning with local and global consistency. In Advances in Neural Information Processing Systems 16, 2003. 3
46.X. Zhu and J. Lafferty. Harmonic mixtures: combining mixture models and graph-based methods for inductive and scalable semi-supervised learning. In ICML ’05: Proceedings of the 22nd international conference on Machine learning, pages 1052–1059, 2005. 3

Citation

MLA

Deng Cai, et al. “Graph Regularized Nonnegative Matrix Factorization for Data Representation”. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 8, 2011, pp. 1548–60, https://doi.org/10.1109/TPAMI.2010.231.

APA

Deng Cai, Xiaofei He, Jiawei Han, & Huang, T. S. (2011). Graph Regularized Nonnegative Matrix Factorization for Data Representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(8), 1548–1560. https://doi.org/10.1109/TPAMI.2010.231

Chicago

Deng Cai, Xiaofei He, Jiawei Han, and T. S. Huang. 2011. “Graph Regularized Nonnegative Matrix Factorization for Data Representation”. IEEE Transactions on Pattern Analysis and Machine Intelligence 33 (8): 1548–60. https://doi.org/10.1109/TPAMI.2010.231.

Harvard

Deng Cai et al. (2011) “Graph Regularized Nonnegative Matrix Factorization for Data Representation”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(8), pp. 1548–1560. Available at: https://doi.org/10.1109/TPAMI.2010.231.

Vancouver

1. Deng Cai, Xiaofei He, Jiawei Han, Huang TS (2011) Graph Regularized Nonnegative Matrix Factorization for Data Representation. IEEE Transactions on Pattern Analysis and Machine Intelligence 33:1548–1560

BibTeX

@article{Deng_Cai_2011, title={Graph Regularized Nonnegative Matrix Factorization for Data Representation}, volume={33}, ISSN={0162-8828}, url={http://dx.doi.org/10.1109/TPAMI.2010.231}, DOI={10.1109/tpami.2010.231}, number={8}, journal={IEEE Transactions on Pattern Analysis and Machine Intelligence}, publisher={Institute of Electrical and Electronics Engineers (IEEE)}, author={Deng Cai and Xiaofei He and Jiawei Han and Huang, T S}, year={2011}, month=Aug, pages={1548–1560} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Graph Regularized Nonnegative Matrix Factorization for Data Representation

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Graph Regularized Non-negative Matrix Factorization (Frobenius Norm Formulation)

Knowl 2 — Multiplicative Update Algorithm for Frobenius Norm GNMF

Knowl 3 — Divergence Formulation and Conjugate Gradient Updates for GNMF

Knowl 4 — Graph Construction and Weighting Schemes in GNMF

Knowl 5 — Normalized Cut Weighted Formulation of GNMF

Knowl 6 — Computational Complexity and Arithmetic Operation Counts of GNMF

Knowl 7 — Clustering Performance of GNMF vs. Baseline Algorithms

Knowl 8 — Sensitivity of GNMF to Regularization Parameter $\lambda$ and Neighborhood Size $p$

Knowl 9 — Influence of Graph Weighting Schemes on Large Neighborhood Robustness

Knowl 10 — Sparseness and Parts-Based Basis Representations Learned by GNMF

References

Citation

BibTeX

Access the Paper