# A Nonmonotone Gradient-Based Algorithm for Symmetric Nonnegative Matrix Factorization and Graph Clustering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 42 references that are in the map.
- First posted on arXiv 1 Jun 2026.

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

- [HDLTex: Hierarchical Deep Learning for Text Classification](https://mlsanity.com/paper/1709.08267/) (2017)
- [Hypergraph Random Walks, Laplacians, and Clustering](https://mlsanity.com/paper/2006.16377/) (2020)
- [Dropping Symmetry for Fast Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/1811.05642/) (2018)
- [A Provable Splitting Approach for Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/2301.10499/) (2023)
- [Nonlinear Least Squares for Large-Scale Machine Learning using Stochastic Jacobian Estimates](https://mlsanity.com/paper/2107.05598/) (2021)
- [Rethinking Symmetric Matrix Factorization: A More General and Better Clustering Perspective](https://mlsanity.com/paper/2209.02528/) (2022)
- [Randomized Algorithms for Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/2402.08134/) (2024)
- [Compact representations of structured BFGS matrices](https://mlsanity.com/paper/2208.00057/) (2022)
- [Iterative regularization for low complexity regularizers](https://mlsanity.com/paper/2202.00420/) (2022)
- [Useful Compact Representations for Data-Fitting](https://mlsanity.com/paper/2403.12206/) (2024)

## Abstract (arXiv)

Symmetric nonnegative matrix factorization (Symmetric NMF) approximates a matrix as WWT with nonnegative rectangular factor W. It has broad applications in graph clustering and machine learning. In contrast to the NMF, projected gradient methods for the symmetric problem had been associated with slow convergence. To address this, we introduce SNMPBB, the first adaptation of nonmonotone projected Barzilai-Borwein methods to Symmetric NMF, demonstrating that gradient algorithms are significantly more effective than previously understood. We further extend SNMPBB to graph clustering using the graph Laplacian regularization (Graph-SNMPBB) and to large problems with low-rank approximations (LAI-SNMPBB). For all variants we prove global convergence to first-order stationary points and also that Barzilai-Borwein curvature information is preserved with randomized approximations. On synthetic data, SNMPBB achieves 6 times speedup over the alternative SymANLS for similar residuals, with advantages growing at higher ranks. Across six real-world clustering benchmarks, Graph-SNMPBB matches or exceeds SymANLS accuracy. Lastly, LAI-SNMPBB outperforms state-of-the-art LAI-SymPGNCG on 34 SuiteSparse matrices in both runtime and residual quality.