Abstract
Current nonnegative matrix factorization (NMF) deals with X = FGT type. We provide a systematic analysis and extensions of NMF to the symmetric W = HHT, and the weighted W = HSHT. We show that (1) W = HHT is equivalent to Kernel if-means clustering and the Laplacian-based spectral clustering. (2) X = FGT is equivalent to simultaneous clustering of rows and columns of a bipartite graph. Algorithms are given for computing these symmetric NMFs.
Keywords
National laboratoryNon-negative matrix factorizationFactorizationBipartite graphCluster analysisMathematicsCombinatoricsComputer scienceLibrary scienceMatrix decompositionGraphAlgorithmArtificial intelligenceEigenvalues and eigenvectorsPhysicsEngineering physics
Affiliated Institutions
Related Publications
Partitioning Sparse Matrices with Eigenvectors of Graphs
The problem of computing a small vertex separator in a graph arises in the context of computing a good ordering for the parallel factorization of sparse, symmetric matrices. An ...
Weighted Graph Cuts without Eigenvectors A Multilevel Approach
A variety of clustering algorithms have recently been proposed to handle data that is not linearly separable; spectral clustering and kernel k-means are two of the main methods....
On the Quality of Spectral Separators
Computing graph separators is an important step in many graph algorithms. A popular technique for finding separators involves spectral methods. However, there has not been much ...
Pattern vectors from algebraic graph theory
Graph structures have proven computationally cumbersome for pattern analysis. The reason for this is that, before graphs can be converted to pattern vectors, correspondences mus...
Learning Eigenfunctions Links Spectral Embedding and Kernel PCA
In this letter, we show a direct relation between spectral embedding methods and kernel principal components analysis and how both are special cases of a more general learning p...
Publication Info
- Year
- 2005
- Type
- article
- Citations
- 975
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
975
OpenAlex
Cite This
Chris Ding,
Xiaofeng He,
Horst D. Simon
(2005).
On the Equivalence of Nonnegative Matrix Factorization and Spectral Clustering.
.
https://doi.org/10.1137/1.9781611972757.70
Identifiers
- DOI
- 10.1137/1.9781611972757.70