提出新型梯度算法，显著提升对称非负矩阵分解速度与效果
A Nonmonotone Gradient-Based Algorithm for Symmetric Nonnegative Matrix Factorization and Graph Clustering
- 采用非单调投影巴兹莱-博韦因方法加速对称非负矩阵分解
- 在真实数据集上精度媲美或超越现有方法，最高提速6倍
- 适用于大规模图聚类与低秩近似，适合追求高效性能的研究者
对称非负矩阵分解（Symmetric NMF）将矩阵近似为 $WW^T$ 形式，其中 $W$ 为非负矩形因子，广泛应用于图聚类和机器学习。传统投影梯度法在该问题中收敛缓慢。为此，本文首次将非单调投影巴兹莱-博韦因方法引入对称NMF，提出 SNMPBB 算法，证明梯度方法比以往认知更有效。进一步扩展至带图拉普拉斯正则化的图聚类（Graph-SNMPBB）和大尺度低秩近似（LAI-SNMPBB）。所有变体均证明可全局收敛至一阶驻点，且随机近似下仍保持巴兹莱-博韦因曲率信息。在合成数据上，SNMPBB 相同残差下相比 SymANLS 速度提升6倍，高秩时优势更明显；在六个真实世界聚类基准上，Graph-SNMPBB 达到或超过 SymANLS 精度；在34个 SuiteSparse 矩阵上，LAI-SNMPBB 在运行时间和残差质量上均优于当前最优的 LAI-SymPGNCG。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。