Nonnegative Matrix Factorization for Combinatorial Optimization: Spectral Clustering, Graph Matching, and Clique Finding
Authors:
- Chris DingCDChris Ding
- Tao LiTLTao Li
- Michael I. JordanMJMichael I. Jordan
- 1 December 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15504786,p. 183-192
Abstract
Nonnegative matrix factorization (NMF) is a versatile model for data clustering. In this paper, we propose several NMF inspired algorithms to solve different data mining problems. They include (1) multi-way normalized cut spectral clustering, (2) graph matching of both undirected and directed graphs, and (3) maximal clique finding on both graphs and bipartite graphs. Key features of these algorithms are (a) they are extremely simple to implement; and (b) they are provably convergent. We conduct experiments to demonstrate the effectiveness of these new algorithms. We also derive a new spectral bound for the size of maximal edge bicliques as a byproduct of our approach.Keywords
This publication has 26 references indexed in Scilit:
- Algorithms and applications for approximate nonnegative matrix factorizationComputational Statistics & Data Analysis, 2007
- Empirical and Theoretical Comparisons of Selected Criterion Functions for Document ClusteringMachine Learning, 2004
- IFD: Iterative Feature and Data Clustering2004
- Minimum Sum-Squared Residue Co-clustering of Gene Expression Data2004
- Metagenes and molecular pattern discovery using matrix factorizationProceedings of the National Academy of Sciences of the United States of America, 2004
- Annealed replication: a new heuristic for the maximum clique problemDiscrete Applied Mathematics, 2002
- Normalized cuts and image segmentationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000
- Positive matrix factorization: A non‐negative factor model with optimal utilization of error estimates of data valuesEnvironmetrics, 1994
- An eigendecomposition approach to weighted graph matching problemsIEEE Transactions on Pattern Analysis and Machine Intelligence, 1988
- Maxima for Graphs and a New Proof of a Theorem of TuránCanadian Journal of Mathematics, 1965