# A Provable Splitting Approach for Symmetric Nonnegative Matrix Factorization

arXiv: https://arxiv.org/abs/2301.10499 · HTML: https://mlsanity.com/paper/2301.10499/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 38 references that are in the map.
- First posted on arXiv 25 Jan 2023.

## Builds on (most cited first, 6 of 6)

- [The Why and How of Nonnegative Matrix Factorization](https://mlsanity.com/paper/1401.5226/) (2014)
- [A Flexible and Efficient Algorithmic Framework for Constrained Matrix and Tensor Factorization](https://mlsanity.com/paper/1506.04209/) (2015)
- [Dropping Symmetry for Fast Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/1811.05642/) (2018)
- [Coordinate Descent Methods for Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/1509.01404/) (2015)
- [A Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization: Convergence Analysis and Optimality](https://mlsanity.com/paper/1703.08267/) (2017)
- [Fast and Effective Algorithms for Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/1609.05342/) (2016)

## Built on by (most cited first, 6 of 6)

- [Proximal Symmetric Non-negative Latent Factor Analysis: A Novel Approach to Highly-Accurate Representation of Undirected Weighted Networks](https://mlsanity.com/paper/2306.03647/) (2023)
- [Deep Nonnegative Matrix Factorization with Beta Divergences](https://mlsanity.com/paper/2309.08249/) (2023)
- [A Constraints Fusion-induced Symmetric Nonnegative Matrix Factorization Approach for Community Detection](https://mlsanity.com/paper/2302.12114/) (2023)
- [Online Learning Under A Separable Stochastic Approximation Framework](https://mlsanity.com/paper/2305.07484/) (2023)
- [Fast and Effective Computation of Generalized Symmetric Matrix Factorization](https://mlsanity.com/paper/2603.19147/) (2026)
- [A Nonmonotone Gradient-Based Algorithm for Symmetric Nonnegative Matrix Factorization and Graph Clustering](https://mlsanity.com/paper/2606.02887/) (2026)

## Abstract (arXiv)

The symmetric Nonnegative Matrix Factorization (NMF), a special but important class of the general NMF, has found numerous applications in data analysis such as various clustering tasks. Unfortunately, designing fast algorithms for the symmetric NMF is not as easy as for its nonsymmetric counterpart, since the latter admits the splitting property that allows state-of-the-art alternating-type algorithms. To overcome this issue, we first split the decision variable and transform the symmetric NMF to a penalized nonsymmetric one, paving the way for designing efficient alternating-type algorithms. We then show that solving the penalized nonsymmetric reformulation returns a solution to the original symmetric NMF. Moreover, we design a family of alternating-type algorithms and show that they all admit strong convergence guarantee: the generated sequence of iterates is convergent and converges at least sublinearly to a critical point of the original symmetric NMF. Finally, we conduct experiments on both synthetic data and real image clustering to support our theoretical results and demonstrate the performance of the alternating-type algorithms.