Nonnegative Matrix Factorization for Combinatorial Optimization: Spectral Clustering, Graph Matching, and Clique Finding
Published 1 December 2008
Chris Ding, Tao Li, Michael I. Jordan
Citations133
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper proposes several NMF inspired algorithms to solve different data mining problems, including multi-way normalized cut spectral clustering, graph matching of both undirected and directed graphs, and maximal clique finding on both graphs and bipartite graphs.
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
Computer SciencePhysics and Astronomy
IEEE Transactions on Pattern Analysis and Machine IntelligenceNormalized cuts and image segmentation
15,696 Citations2000Jianbo Shi, Jitendra Malik
NatureLearning the parts of objects by non-negative matrix factorization
14,055 Citations1999Daniel D. Lee, H. Sebastian Seung
An algorithm for non-negative matrix factorization is demonstrated that is able to learn parts of faces and semantic features of text and is in contrast to other methods that learn holistic, not parts-based, representations.
On Spectral Clustering: Analysis and an algorithm
7,751 Citations2001Andrew Y. Ng, Michael I. Jordan +1 more
A simple spectral clustering algorithm that can be implemented using a few lines of Matlab is presented, and tools from matrix perturbation theory are used to analyze the algorithm, and give conditions under which it can be expected to do well.
EnvironmetricsPositive matrix factorization: A non‐negative factor model with optimal utilization of error estimates of data values
6,302 Citations1994Pentti Paatero, Unto Tapper
Algorithms for Non-negative Matrix Factorization
5,463 Citations2000Daniel D. Lee, H. Sebastian Seung
Two different multiplicative algorithms for non-negative matrix factorization are analyzed and one algorithm can be shown to minimize the conventional least squares error while the other minimizes the generalized Kullback-Leibler divergence.
Journal of Machine Learning ResearchNon-negative Matrix Factorization with Sparseness Constraints
2,631 Citations2004Patrik O. Hoyer
Proceedings of the National Academy of SciencesMetagenes and molecular pattern discovery using matrix factorization
2,295 Citations2004Jean-Philippe Brunet, Pablo Tamayo +2 more
Nonnegative matrix factorization is described, an algorithm based on decomposition by parts that can reduce the dimension of expression data from thousands of genes to a handful of metagenes, and found less sensitive to a priori selection of genes or initial conditions and able to detect alternative or context-dependent patterns of gene expression in complex biological systems.
Document clustering based on non-negative matrix factorization
1,847 Citations2003Wei Xu, Xin Liu +1 more
This paper proposes a novel document clustering method based on the non-negative factorization of the term-document matrix of the given document corpus that surpasses the latent semantic indexing and the spectral clustering methods not only in the easy and reliable derivation of document clustered results, but also in document clusters accuracies.
Computational Statistics & Data AnalysisAlgorithms and applications for approximate nonnegative matrix factorization
1,534 Citations2006Michael W. Berry, Murray Browne +3 more
The development and use of low-rank approximate nonnegative matrix factorization algorithms for feature extraction and identification in the fields of text mining and spectral data analysis and the interpretability of NMF outputs in specific contexts are provided.
<i>K</i>-means clustering via principal component analysis
1,396 Citations2004Chris Ding, Xiaofeng He
It is proved that principal components are the continuous solutions to the discrete cluster membership indicators for K-means clustering, which indicates that unsupervised dimension reduction is closely related to unsuper supervised learning.
On the Equivalence of Nonnegative Matrix Factorization and Spectral Clustering
977 Citations2005Chris Ding, Xiaofeng He +1 more
This work shows that (1) W = HH T is equivalent to Kernel K -means clustering and the Laplacian-based spectral clustering and (2) X = FG T is equivalent to simultaneous clustering of rows and columns of a bipartite graph.
The Maximum Clique Problem
975 Citations1999Immanuel M. Bomze, Marko Budinich +2 more
This paper considers the problem of finding the largest clique in a graph using the notation ES to represent the subset of edges which have both endpoints in clique S, and concludes that the induced graph GS = ( S, ES ) is complete.
Maximum-Margin Matrix Factorization
952 Citations2004Nathan Srebro, Jason D. M. Rennie +1 more
A novel approach to collaborative prediction is presented, using low-norm instead of low-rank factorizations, inspired by, and has strong connections to, large-margin linear discrimination.
Learning spatially localized, parts-based representation
780 Citations2005S.Z. Li, Xin Hou +2 more
A novel method, called local non-negative matrix factorization (LNMF), for learning spatially localized, parts-based subspace representation of visual patterns, which gives a set of bases which not only allows a non-subtractive representation of images but also manifests localized features.
Canadian Journal of MathematicsMaxima for Graphs and a New Proof of a Theorem of Turán
728 Citations1965T. S. Motzkin, E. G. Straus
IEEE Transactions on Pattern Analysis and Machine IntelligenceAn eigendecomposition approach to weighted graph matching problems
718 Citations1988Shinji Umeyama
An approximate solution to the weighted-graph-matching problem is discussed for both undirected and directed graphs and an analytic approach is used instead of a combinatorial or iterative approach to the optimum matching problem.
Machine LearningEmpirical and Theoretical Comparisons of Selected Criterion Functions for Document Clustering
613 Citations2004Ying Zhao, George Karypis
This paper evaluates the performance of different criterion functions in the context of partitional clustering algorithms for document datasets, and shows that there are a set of criterion functions that consistently outperform the rest.
Spectral Relaxation for K-means Clustering
561 Citations2001Hongyuan Zha, Xiaofeng He +3 more
It is shown that a relaxed version of the trace maximization problem possesses global optimal solutions which can be obtained by Computing a partial eigendecomposition of the Gram matrix, and the cluster assignment for each data vectors can be found by computing a pivoted QR decomposition ofThe eigenvector matrix.
Neural Information Processing SystemsGeneralized Nonnegative Matrix Approximations with Bregman Divergences
397 Citations2005Suvrit Sra, Inderjit S. Dhillon
This paper makes algorithmic progress by modeling and solving (using multiplicative updates) new generalized NNMA problems that minimize Bregman divergences between the input matrix and its low-rank approximation.
Information-theoretic co-clustering
361 Citations2003Inderjit S. Dhillon, Subramanyam Mallela +1 more
Text Mining using Non-Negative Matrix Factorizations
310 Citations2004V. Paúl Pauca, Farial Shahnaz +2 more
Minimum Sum-Squared Residue Co-clustering of Gene Expression Data
294 Citations2004Hyuk Cho, Inderjit S. Dhillon +2 more
This paper uses two similar squared residue measures and proposes two fast co-clustering algorithms corresponding to the two residue measures, which inherit the simplicity, efficiency and wide applicability of the k-means algorithm.
Relation between PLSA and NMF and implications
267 Citations2005Éric Gaussier, Cyril Goutte
It is shown that PLSA solves the problem of NMF with KL divergence, and the implications of this relationship are explored.
WebACE
169 Citations1998Eui-Hong Han, Daniel Boley +7 more
The heart of the agent is an automatic categorization of a set of documents, combined with a process for generating new queries used to search for new related documents and filtering the resulting documents to extract the set of documents most closely related to the starting set.
A general model for clustering binary data
161 Citations2005Tao Li
A general binary data clustering model is presented that treats the data and features equally, based on their symmetric association relations, and explicitly describes the data assignments as well as feature assignments.
Mathematics of Operations ResearchContinuous Characterizations of the Maximum Clique Problem
160 Citations1997L. Gibbons, Donald W. Hearn +2 more
The Motzkin-Strauss QP is characterized, revealing interesting underlying discrete structures, and its properties are investigated, which are polynomial time verifiable.
ScholarlyCommons (University of Pennsylvania)Multiplicative Updates for Nonnegative Quadratic Programming in Support Vector Machines
146 Citations2002Fei Sha, Lawrence K. Saul +1 more
The asymptotic convergence of the updates is analyzed and it is shown that the coefficients of non-support vectors decay geometrically to zero at a rate that depends on their margins.
Generalized Nonnegative Matrix Approximations with Bregman Divergences
123 Citations2005Inderjit S. Dhillon, Suvrit Sra
Document clustering via adaptive subspace iteration
119 Citations2004Tao Li, Sheng Ma +1 more
A new clustering algorithm ASI1 is presented, which uses explicitly modeling of the subspace structure associated with each cluster, and a novel method to determine the number of clusters is provided.
National Conference on Artificial IntelligenceNonnegative matrix factorization and probabilistic latent semantic indexing: equivalence, chi-square statistic, and a hybrid method
117 Citations2006Chris Ding, Tao Li +1 more
It is demonstrated that high glucose causes oxidative stress and NO over-production in rat mesangial cells in vitro via decreasing Bim and increasing iNOS, which are at least partially mediated by the TGF-β1/PI3K/Akt pathway.
Summarizing video using non-negative similarity matrix factorization
99 Citations2004Matthew Cooper, Jonathan Foote
A novel approach to automatically extracting summary excerpts from audio video and video by maximizing the average similarity between the excerpt and the source to generate a summary comprised of excerpts from the main components.
Fast Parallel Algorithms for Graph Matching Problems
76 Citations1998Marek Karpiński, Wojciech Rytter
Relaxation labeling networks for the maximum clique problem
73 Citations1996Marcello Pelillo
It is shown how to take advantage of the properties of relaxation labeling networks to approximately solve the maximum clique problem, a well-known intractable optimization problem which has practical applications in various elds.
Journal of ChemometricsPositive matrix factorization applied to a curve resolution problem
63 Citations1998YuLong Xie, Philip K. Hopke +1 more
Discrete Applied MathematicsAnnealed replication: a new heuristic for the maximum clique problem
62 Citations2002Immanuel M. Bomze, Marco Budinich +2 more
A new heuristic for approximating the maximum clique problem based on a detailed analysis of a class of continuous optimization models which provide a complete characterization of solutions to this NP-hard combinatorial problem is proposed.
IFD: Iterative Feature and Data Clustering
26 Citations2004Tao Li, Sheng Ma
The convergence property of the clustering algorithm is shown, its connections with various existential approaches are discussed, and extensive experimental results on both synthetic and real data sets show the effectiveness of IFD algorithm.
CLSI: A Flexible Approximation Scheme from Clustered Term-Document Matrices
22 Citations2005Dimitrios Zeimpekis, Efstratios Gallopoulos
Parts of a frame-work for matrix approximation and its application in LSI 1 are outlined, designed in the context of the vector spacemodel, where a collection of n documents is repre-sented by a term-document matrix of n columns and mrows, where mis the number of terms is used to index the collection.
Relaxation labeling networks that solve the maximum clique problem
21 Citations1995Marcello Pelillo
It is shown how to take advantage of the properties of relaxation labeling networks to solve the maximum clique problem, a well-known intractable optimization problem which has practical applications in various fields.