SymNMF: nonnegative low-rank approximation of a similarity matrix for graph clustering. Nonnegative matrix factorization (NMF) provides a lower rank approximation of a matrix by a product of two nonnegative factors. NMF has been shown to produce clustering results that are often superior to those by other methods such as K-means. In this paper, we provide further interpretation of NMF as a clustering method and study an extended formulation for graph clustering called Symmetric NMF (SymNMF). In contrast to NMF that takes a data matrix as an input, SymNMF takes a nonnegative similarity matrix as an input, and a symmetric nonnegative lower rank approximation is computed. We show that SymNMF is related to spectral clustering, justify SymNMF as a general graph clustering method, and discuss the strengths and shortcomings of SymNMF and spectral clustering. We propose two optimization algorithms for SymNMF and discuss their convergence properties and computational efficiencies. Our experiments on document clustering, image clustering, and image segmentation support SymNMF as a graph clustering method that captures latent linear and nonlinear relationships in the data.

References in zbMATH (referenced in 15 articles , 1 standard article )

Showing results 1 to 15 of 15.
Sorted by year (citations)

  1. Chu, Delin; Shi, Weya; Eswar, Srinivas; Park, Haesun: An alternating rank-(k) nonnegative least squares framework (ARkNLS) for nonnegative matrix factorization (2021)
  2. Dragomir, Radu-Alexandru; d’Aspremont, Alexandre; Bolte, Jérôme: Quartic first-order methods for low-rank minimization (2021)
  3. Eswar, Srinivas; Kannan, Ramakrishnan; Vuduc, Richard; Park, Haesun: ORCA: outlier detection and robust clustering for attributed graphs (2021)
  4. Moutier, François; Vandaele, Arnaud; Gillis, Nicolas: Off-diagonal symmetric nonnegative matrix factorization (2021)
  5. Favati, P.; Lotti, G.; Menchi, O.; Romani, F.: Adaptive computation of the symmetric nonnegative matrix factorization (SymNMF) (2020)
  6. Zisler, Matthias; Zern, Artjom; Petra, Stefania; Schnörr, Christoph: Self-assignment flows for unsupervised data labeling on graphs (2020)
  7. Du, Rundong; Drake, Barry; Park, Haesun: Hybrid clustering based on content and connection structure using joint nonnegative matrix factorization (2019)
  8. Favati, Paola; Lotti, Grazia; Menchi, Ornella; Romani, Francesco: An adaptive procedure for the global minimization of a class of polynomial functions (2019)
  9. Vandaele, Arnaud; Glineur, François; Gillis, Nicolas: Algorithms for positive semidefinite factorization (2018)
  10. Zhang, Xinyu; Gao, Hongbo; Li, Guopeng; Zhao, Jianhui; Huo, Jianghao; Yin, Jialun; Liu, Yuchao; Zheng, Li: Multi-view clustering based on graph-regularized nonnegative matrix factorization for object recognition (2018)
  11. Du, Rundong; Kuang, Da; Drake, Barry; Park, Haesun: DC-NMF: nonnegative matrix factorization based on divide-and-conquer for fast clustering and topic modeling (2017)
  12. Elbassioni, Khaled; Nguyen, Trung Thanh: A polynomial-time algorithm for computing low CP-rank decompositions (2017)
  13. Pehlevan, Cengiz; Mohan, Sreyas; Chklovskii, Dmitri B.: Blind nonnegative source separation using biological neural networks (2017)
  14. Choo, Jaegul; Lee, Changhyun; Reddy, Chandan K.; Park, Haesun: Weakly supervised nonnegative matrix factorization for user-driven clustering (2015)
  15. Kuang, Da; Yun, Sangwoon; Park, Haesun: SymNMF: nonnegative low-rank approximation of a similarity matrix for graph clustering (2015)