pith. sign in

arxiv: 2606.02887 · v1 · pith:C2W4PSBHnew · submitted 2026-06-01 · 💻 cs.LG · cs.NA· math.NA· math.OC

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

Ryan Swart , Johannes Brust This is my paper

Pith reviewed 2026-06-28 15:09 UTC · model grok-4.3

classification 💻 cs.LG cs.NAmath.NAmath.OC
keywords symmetric nonnegative matrix factorizationgraph clusteringBarzilai-Borwein methodprojected gradientnonmonotone optimizationlow-rank approximation
0
0 comments X

The pith

A nonmonotone projected Barzilai-Borwein method for symmetric nonnegative matrix factorization converges globally and runs six times faster than prior gradient approaches.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces SNMPBB as the first use of nonmonotone projected Barzilai-Borwein steps for the symmetric NMF problem of approximating a matrix by WW^T with nonnegative W. It proves that the iterates reach first-order stationary points for the basic method, for the graph-Laplacian-regularized version used in clustering, and for the low-rank-approximated version used on large matrices. On synthetic tests the new method reaches similar residuals in one-sixth the time of SymANLS, with the gap widening at higher rank. On six real clustering data sets the graph-regularized variant matches or beats SymANLS accuracy, while the low-rank variant beats the prior state-of-the-art LAI-SymPGNCG on 34 SuiteSparse matrices in both speed and final residual.

Core claim

SNMPBB adapts nonmonotone projected Barzilai-Borwein steps to symmetric NMF, proves global convergence to first-order stationary points for all three variants, shows that randomized low-rank approximations preserve the Barzilai-Borwein curvature information, and demonstrates that the resulting algorithms deliver sixfold speedups on synthetic data, comparable or better clustering accuracy on six benchmarks, and better runtime-residual trade-offs on 34 large sparse matrices.

What carries the argument

The SNMPBB iteration, which combines a nonmonotone line search with Barzilai-Borwein curvature estimates inside a projected gradient framework for the symmetric NMF objective.

If this is right

  • SNMPBB reaches residuals comparable to SymANLS in one-sixth the runtime on synthetic matrices, with larger gains at higher target rank.
  • Graph-SNMPBB equals or exceeds SymANLS clustering accuracy on six standard real-world data sets.
  • LAI-SNMPBB produces lower residuals in less time than LAI-SymPGNCG on 34 SuiteSparse matrices.
  • Global convergence to first-order points holds for the basic algorithm, the graph-regularized version, and the randomized low-rank version.
  • Barzilai-Borwein curvature information is preserved under randomized low-rank approximations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Gradient methods can now be viewed as competitive rather than inherently slow for symmetric nonnegative factorization tasks.
  • The same nonmonotone Barzilai-Borwein framework may transfer directly to other symmetric factorization problems that admit a projected-gradient formulation.
  • Randomized low-rank approximations could be swapped into other first-order methods for symmetric NMF while retaining their step-size rules.

Load-bearing premise

The nonmonotone projected Barzilai-Borwein curvature information remains effective and the global convergence proof continues to hold when the method is extended with graph Laplacian regularization and randomized low-rank approximations for large problems.

What would settle it

Implement SNMPBB and SymANLS on the same six real-world clustering benchmarks and measure whether the new method matches or exceeds SymANLS accuracy at comparable or lower residuals.

Figures

Figures reproduced from arXiv: 2606.02887 by Johannes Brust, Ryan Swart.

Figure 1
Figure 1. Figure 1: Clustering accuracy vs. time on MNIST averaged over 10 runs. Graph [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Convergence and clustering results on a concentric bullseye dataset ( [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Clustering accuracy vs. wall-clock time on six benchmark datasets, averaged [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Performance profiles for LAI-SNMPBB and LAI-SymPGNCG on 34 SuiteS [PITH_FULL_IMAGE:figures/full_fig_p016_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Residual ∥V − W H∥/∥V ∥ vs. wall-clock time on the Web of Science dataset (46985 term documents, 7 categories, rank r = 7, averaged over 10 runs). Both algorithms use the Hypergraph-with-Edge-Dependent-Vertex-Weights preprocessing of Hayashi et al. [20]. LAI-SNMPBB and LAI-SymPGNCG reach comparable final residuals (7.365 × 10−1 vs. 7.357 × 10−1 ), but LAI-SNMPBB does so in consistently less time across all… view at source ↗
read the original abstract

Symmetric nonnegative matrix factorization (Symmetric NMF) approximates a matrix as $WW^T$ 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript presents SNMPBB, a nonmonotone projected Barzilai-Borwein algorithm for symmetric nonnegative matrix factorization (Symmetric NMF), along with extensions Graph-SNMPBB incorporating graph Laplacian regularization for clustering tasks and LAI-SNMPBB using randomized low-rank approximations for scalability. The authors claim to prove global convergence to first-order stationary points for all variants and that the Barzilai-Borwein curvature information is preserved under randomization. Empirical evaluations demonstrate significant speedups (up to 6x over SymANLS) on synthetic data, competitive or better accuracy on six real-world clustering benchmarks, and improved runtime and residual quality on 34 SuiteSparse matrices compared to LAI-SymPGNCG.

Significance. Should the convergence proofs for the extended methods hold, this work would be significant for advancing optimization techniques in symmetric NMF and graph clustering by showing that carefully designed gradient methods can achieve substantial practical improvements over previously used approaches like SymANLS. The combination of theoretical guarantees with strong empirical performance on both small and large-scale problems highlights its potential impact. The provision of global convergence proofs and the handling of randomization in BB methods are particular strengths.

major comments (1)
  1. [Convergence analysis for the extended variants] The global convergence claims for Graph-SNMPBB and LAI-SNMPBB are load-bearing for the paper's main contributions. The analysis must explicitly demonstrate that the Laplacian-regularized gradient still meets the requirements for the nonmonotone line search and that the randomized low-rank approximation preserves the exact two-point BB curvature formula without bias or unstated error bounds that could invalidate the argument.
minor comments (1)
  1. [Abstract] The abstract mentions preservation of Barzilai-Borwein information under randomization but could clarify the specific conditions under which this holds for the low-rank case.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment of our work and the detailed comment on the convergence analysis. We address the concern point by point below.

read point-by-point responses

  1. Referee: [Convergence analysis for the extended variants] The global convergence claims for Graph-SNMPBB and LAI-SNMPBB are load-bearing for the paper's main contributions. The analysis must explicitly demonstrate that the Laplacian-regularized gradient still meets the requirements for the nonmonotone line search and that the randomized low-rank approximation preserves the exact two-point BB curvature formula without bias or unstated error bounds that could invalidate the argument.

    Authors: We thank the referee for this observation. The convergence proofs for both extensions are already contained in the appendix and follow directly from the base SNMPBB analysis. For Graph-SNMPBB, the regularized objective remains continuously differentiable with a Lipschitz-continuous gradient (Lemma A.3), so the nonmonotone line-search conditions and global convergence to first-order stationary points carry over unchanged (Theorem A.4). For LAI-SNMPBB, Theorem 4.2 shows that the randomized low-rank approximation is applied identically to the gradient and the iterate difference, preserving the exact two-point BB curvature formula with no bias or additional error terms. We agree that a concise summary of these arguments in the main text (e.g., a short paragraph in Section 4) would improve readability and will add it in the revision. revision: partial

Circularity Check

0 steps flagged

No circularity: algorithmic adaptation and convergence proofs are independent of inputs

full rationale

The paper presents SNMPBB as a novel adaptation of nonmonotone projected Barzilai-Borwein methods to symmetric NMF, with explicit extensions (Graph-SNMPBB, LAI-SNMPBB) and claims of global convergence plus preserved BB curvature under randomization and Laplacian regularization. These are framed as new proofs and empirical comparisons against external baselines (SymANLS, LAI-SymPGNCG) on SuiteSparse matrices and clustering benchmarks. No self-definitional reductions, fitted inputs renamed as predictions, or load-bearing self-citations appear in the abstract or described claims; the central results rest on standard convergence analysis applied to the new variants rather than tautological redefinitions or internal fits. Speedups and accuracy matches are measured externally, not derived by construction from the method's own parameters.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work relies on standard results from nonmonotone optimization theory for the convergence proofs; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (2)
  • standard math Global convergence of nonmonotone projected gradient methods to first-order stationary points under standard assumptions on the objective and feasible set
    Invoked to establish the theoretical guarantee for SNMPBB and its variants.
  • domain assumption Barzilai-Borwein curvature information is preserved under randomized low-rank approximations
    Required for the LAI-SNMPBB extension to retain the step-size selection properties.

pith-pipeline@v0.9.1-grok · 5755 in / 1558 out tokens · 24853 ms · 2026-06-28T15:09:46.605790+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

63 extracted references · 10 canonical work pages

  1. [1]

    Kuang and S

    D. Kuang and S. Yun and H. Park , title =. J Glob Optim , volume =. 2015 , doi =

    2015

  2. [2]

    Huang and H

    Y. Huang and H. Liu and S. Zhou , title =. Data Min Knowl Disc , volume =. 2015 , doi =

    2015

  3. [3]

    Alternating projected Barzilai-Borwein methods for nonnegative matrix factorization

    Lixing Han and Michael Neumann and Upendra Prasad , journal =. Alternating projected Barzilai-Borwein methods for nonnegative matrix factorization. , url =

  4. [4]

    ArXiv , year=

    Dropping symmetry for fast symmetric nonnegative matrix factorization , author=. ArXiv , year=

  5. [5]

    Symmetry , VOLUME =

    Li, Wenbo and Shi, Xiaolu , TITLE =. Symmetry , VOLUME =. 2024 , NUMBER =

    2024

  6. [6]

    A provable splitting approach for symmetric nonnegative matrix factorization , year=

    Li, Xiao and Zhu, Zhihui and Li, Qiuwei and Liu, Kai , journal=. A provable splitting approach for symmetric nonnegative matrix factorization , year=

  7. [7]

    , journal=

    Cai, Deng and He, Xiaofei and Han, Jiawei and Huang, Thomas S. , journal=. Graph regularized nonnegative matrix factorization for data representation , year=

  8. [8]

    Discrimination-aware projected matrix factorization , year=

    Li, Xuelong and Chen, Mulin and Wang, Qi , journal=. Discrimination-aware projected matrix factorization , year=

  9. [9]

    2006 , issn =

    Document clustering using nonnegative matrix factorization , journal =. 2006 , issn =. doi:10.1016/j.ipm.2004.11.005 , author =

    work page doi:10.1016/j.ipm.2004.11.005 2006

  10. [10]

    Clustering NMF basis functions using shifted NMF for monaural sound source separation , year=

    Jaiswal, Rajesh and FitzGerald, Derry and Barry, Dan and Coyle, Eugene and Rickard, Scott , booktitle=. Clustering NMF basis functions using shifted NMF for monaural sound source separation , year=

  11. [11]

    2024 , issn =

    The rise of nonnegative matrix factorization: algorithms and applications , journal =. 2024 , issn =. doi:10.1016/j.is.2024.102379 , author =

    work page doi:10.1016/j.is.2024.102379 2024

  12. [12]

    2018 , issn =

    Hierarchical online NMF for detecting and tracking topic hierarchies in a text stream , journal =. 2018 , issn =. doi:10.1016/j.patcog.2017.11.002 , author =

    work page doi:10.1016/j.patcog.2017.11.002 2018

  13. [13]

    , journal=

    Jing, Liping and Zhang, Chao and Ng, Michael K. , journal=. 2012 , volume=

    2012

  14. [14]

    and Pascual-Montano, Adrian , title =

    Pascual-Montano, Alberto and Carmona-Saez, Pedro and Chagoyen, Monica and Tirado, Francisco and Carazo, Jose M. and Pascual-Montano, Adrian , title =. BMC Bioinformatics , volume =. 2006 , doi =

    2006

  15. [15]

    Information , VOLUME =

    Kong, Shikang and Sun, Lijuan and Han, Chong and Guo, Jian , TITLE =. Information , VOLUME =. 2017 , NUMBER =

    2017

  16. [16]

    Simon , title =

    Chris Ding and Xiaofeng He and Horst D. Simon , title =. Proceedings of the 2005 SIAM International Conference on Data Mining (SDM) , chapter =

    2005

  17. [17]

    Symmetry , VOLUME =

    Li, Bingjie and Shi, Xi and Zhang, Zhenyue , TITLE =. Symmetry , VOLUME =. 2021 , NUMBER =

    2021

  18. [18]

    2007 , eprint=

    On the complexity of nonnegative matrix factorization , author=. 2007 , eprint=

    2007

  19. [19]

    and Seung, H

    Lee, Daniel D. and Seung, H. Sebastian , title =. Nature , volume =. 1999 , doi =

    1999

  20. [20]

    , biburl =

    Bertsekas, D.P. , biburl =

  21. [21]

    Mathematics , VOLUME =

    Esposito, Flavia , TITLE =. Mathematics , VOLUME =. 2021 , NUMBER =

    2021

  22. [22]

    2014 , eprint=

    Algorithms, iInitializations, and convergence for the nonnegative matrix factorization , author=. 2014 , eprint=

    2014

  23. [23]

    Graph regularized symmetric non-negative matrix factorization for graph clustering , year=

    Gao, Ziheng and Guan, Naiyang and Su, Longfei , booktitle=. Graph regularized symmetric non-negative matrix factorization for graph clustering , year=

  24. [24]

    2024 , issn =

    Neurocomputing , volume =. 2024 , issn =. doi:10.1016/j.neucom.2023.127041 , author =

    work page doi:10.1016/j.neucom.2023.127041 2024

  25. [25]

    and Mart\'

    Birgin, Ernesto G. and Mart\'. Nonmonotone spectral projected gradient methods on convex sets , journal =. 2000 , doi =

    2000

  26. [26]

    NeNMF: an optimal gradient nethod for nonnegative matrix factorization , year=

    Guan, Naiyang and Tao, Dacheng and Luo, Zhigang and Yuan, Bo , journal=. NeNMF: an optimal gradient nethod for nonnegative matrix factorization , year=

  27. [27]

    Machine Learning and Applications (ICMLA), 2017 16th IEEE International Conference on , year=

    HDLTex: hierarchical deep learning for text classification , author=. Machine Learning and Applications (ICMLA), 2017 16th IEEE International Conference on , year=

    2017

  28. [28]

    and Park, Cheong Hee and Park, Haesun , title =

    Hayashi, Koby and Aksoy, Sinan G. and Park, Cheong Hee and Park, Haesun , title =. 2020 , isbn =. doi:10.1145/3340531.3412034 , booktitle =

    work page doi:10.1145/3340531.3412034 2020

  29. [29]

    IEICE transactions on fundamentals of electronics, communications and computer sciences , volume =

    Fast local algorithms for large scale nonnegative matrix and tensor factorizations , author =. IEICE transactions on fundamentals of electronics, communications and computer sciences , volume =. 2009 , publisher =

    2009

  30. [30]

    SIAM journal on matrix analysis and applications , volume =

    Nonnegative matrix factorization based on alternating nonnegativity constrained least squares and active set method , author =. SIAM journal on matrix analysis and applications , volume =. 2008 , publisher =

    2008

  31. [31]

    2008 Eighth IEEE International Conference on Data Mining , pages =

    Toward faster nonnegative matrix factorization: A new algorithm and comparisons , author =. 2008 Eighth IEEE International Conference on Data Mining , pages =. 2008 , organization =

    2008

  32. [32]

    Computational Optimization and Applications , volume =

    A dense initialization for limited-memory quasi-Newton methods , author =. Computational Optimization and Applications , volume =. 2019 , publisher =

    2019

  33. [33]

    IMA journal of numerical analysis , volume =

    Two-point step size gradient methods , author =. IMA journal of numerical analysis , volume =. 1988 , publisher =

    1988

  34. [34]

    2012 , publisher =

    Guan, Naiyang and Tao, Dacheng and Luo, Zhigang and Yuan, Bo , journal =. 2012 , publisher =

    2012

  35. [35]

    Neural computation , volume =

    Projected gradient methods for nonnegative matrix factorization , author =. Neural computation , volume =. 2007 , publisher =

    2007

  36. [36]

    Electron

    Alternating projected Barzilai-Borwein methods for nonnegative matrix factorization , author =. Electron. Trans. Numer. Anal , volume =

  37. [37]

    2016 , publisher =

    Dynamic mode decomposition: data-driven modeling of complex systems , author =. 2016 , publisher =

    2016

  38. [38]

    and Ballard, Grey and Park, Haesun , title =

    Hayashi, Koby and Aksoy, Sinan G. and Ballard, Grey and Park, Haesun , title =. SIAM Journal on Matrix Analysis and Applications , volume =. 2025 , doi =

    2025

  39. [39]

    1991 , url=

    Differential qquations and dynamical systems , author=. 1991 , url=

    1991

  40. [40]

    29th Annual Conference on Learning Theory , pages =

    Gradient descent only converges to minimizers , author =. 29th Annual Conference on Learning Theory , pages =. 2016 , editor =

    2016

  41. [41]

    Numerische Mathematik , year =

    Molinari, Cesare and Massias, Mathurin and Rosasco, Lorenzo and Villa, Silvia , title =. Numerische Mathematik , year =

  42. [42]

    2023 , eprint=

    Rethinking symmetric matrix factorization: A more general and better clustering perspective , author=. 2023 , eprint=

    2023

  43. [43]

    The University of Florida sparse matrix collection,

    Davis, Timothy A. and Hu, Yifan , title =. 2011 , issue_date =. doi:10.1145/2049662.2049663 , journal =

    work page doi:10.1145/2049662.2049663 2011

  44. [44]

    Pacific Journal of mathematics , volume=

    Minimization of functions having Lipschitz continuous first partial derivatives , author=. Pacific Journal of mathematics , volume=. 1966 , publisher=

    1966

  45. [45]

    Mathematical programming , volume=

    Benchmarking optimization software with performance profiles , author=. Mathematical programming , volume=. 2002 , publisher=

    2002

  46. [46]

    SIAM Journal on Scientific Computing , volume=

    Large-scale optimization with linear equality constraints using reduced compact representation , author=. SIAM Journal on Scientific Computing , volume=. 2022 , publisher=

    2022

  47. [47]

    Computational Optimization and Applications , volume=

    Compact representations of structured BFGS matrices , author=. Computational Optimization and Applications , volume=. 2021 , publisher=

    2021

  48. [48]

    arXiv preprint arXiv:2107.05598 , year=

    Nonlinear least squares for large-scale machine learning using stochastic Jacobian estimates , author=. arXiv preprint arXiv:2107.05598 , year=

    work page arXiv

  49. [49]

    SIAM Journal on Scientific Computing , volume=

    An Trust-Region Quasi-Newton Method , author=. SIAM Journal on Scientific Computing , volume=. 2024 , publisher=

    2024

  50. [50]

    arXiv preprint arXiv:2403.12206 , year=

    Useful Compact Representations for Data-Fitting , author=. arXiv preprint arXiv:2403.12206 , year=

    work page arXiv

  51. [51]

    doi:10.1137/140951758 , journal =

    An Adaptive Shifted Power Method for Computing Generalized Tensor Eigenpairs , author =. doi:10.1137/140951758 , journal =

    work page doi:10.1137/140951758

  52. [52]

    Nick Higham , title =

  53. [53]

    Kolda and Ali Pinar , eprint =

    Chengbin Peng and Tamara G. Kolda and Ali Pinar , eprint =. Accelerating Community Detection by Using

  54. [54]

    and Zhang, Shanrong and Merritt, Matthew E

    Woessner, Donald E. and Zhang, Shanrong and Merritt, Matthew E. and Sherry, A. Dean , title =. Magnetic Resonance in Medicine , doi =

  55. [55]

    2003 , eid =

    Properties of Highly Clustered Networks , author =. 2003 , eid =. doi:10.1103/PhysRevE.68.026121 , journal =

    work page doi:10.1103/physreve.68.026121 2003

  56. [56]

    Clawpack Software , author =

  57. [57]

    : A Document Preparation System

    Leslie Lamport. : A Document Preparation System. 1986

    1986

  58. [58]

    Frank Mittlebach and Michel Goossens , title =

  59. [59]

    and Van Loan, Charles F

    Golub, Gene H. and Van Loan, Charles F. , title =

  60. [60]

    Paul Dawkins , title =

  61. [61]

    User's Guide for the

  62. [62]

    Michael Downes , title =

  63. [63]

    Christian Feuers\"anger , title =