精读笔记

Problem Setting

A Nonmonotone Gradient-Based Algorithm for Symmetric Nonnegative Matrix Factorization and Graph Clustering（arXiv preprint / 2026-06-03）

这篇论文实际处理的是 Symmetric NMF 的优化瓶颈，而不是重新定义 SymNMF 或 graph clustering。核心矛盾是：SymNMF 需要非负低秩因子满足近似对称结构 V≈WW^T，但直接在 W 上优化会得到 quartic、非凸、尺度敏感的单变量问题；而如果为了优化稳定性改用 W,H 双变量，又必须保证结果仍然接近对称。

已有方法大致分两类：SymANLS / Newton 用更重的子问题或二阶信息换稳定性，通常 robust，但 rank 上来后 per-iteration 成本变得不舒服；plain PGD 成本低，但在 symmetric setting 下被认为慢且不稳。真正困难点不是 projection，而是 symmetric formulation 把曲率、尺度和可行性耦合得太硬，导致简单一阶法没有合适的步长几何。

本文解决的问题可以更精确地表述为：能否通过改变 SymNMF 的优化表述和步长机制，让 projected gradient 在保持低成本的同时接近甚至超过 ANLS 类方法的实用性能。

Motivation

作者的出发点是一个相当合理的反直觉观察：NMF 中非单调 projected BB 方法已经被证明很有效，但 SymNMF 文献对 projected gradient 的负面结论多半来自 naive PGD 或直接硬设 H=W^T 的 formulation。换句话说，“梯度法慢”可能不是方法族的根本缺陷，而是 formulation 和 step-size strategy 的问题。

已有路线缺的是一个同时满足三件事的机制：第一，避免直接单变量 quartic 优化；第二，不像 ANLS 那样每步求 expensive constrained least squares；第三，能够对曲率和非凸局部地形做足够强的自适应。本文的核心观察是，SymANLS 已经使用 penalty coupling 保留 W,H 两个变量，而 NMPBB 已经提供了低成本曲率缩放和非单调 globalization；把二者结合，可能正好绕开 SymNMF 上 PGD 的失败模式。

因此动机不是“发明新正则项”，而是重新组织 optimization geometry：用 relaxed symmetry 释放自由度，用 BB 步长恢复一阶法的尺度感知，用非单调线搜索避免非凸问题中过于保守的单调下降。

Core Idea

核心思想是把 SymNMF 从硬约束的 W-only 问题，转成一个带二次对称惩罚的 W,H alternating 问题：min 1/2||V-WH||^2 + λ/2||W-H^T||^2。这个改写非常关键，因为它把单变量 quartic 结构拆成 block-wise convex quadratic；在固定 H 更新 W 或固定 W 更新 H 时，问题重新具有 NMPBB 所需的凸性和 Lipschitz 梯度结构。这样，projected BB 不再是在一个曲率混乱的 quartic surface 上裸奔，而是在每个 block 的相对干净曲率上工作。

和 prior 的本质差异在于，它没有把 symmetry 作为每一步的硬身份约束 H=W^T，而是作为 gradient 中持续施加的 coupling force。这个选择改变了信息流：W,H 可以分别吸收数据拟合误差，再通过 penalty 对齐；相比硬绑定，优化路径更宽，局部调整自由度更高。相比 ANLS，它不求精确 block 子问题，而是用 BB 近似曲率 + projection + nonmonotone search 做便宜的 inexact update。

Graph-SNMPBB 的核心不是单纯加 Laplacian，而是承认纯 SymNMF 的 factor 往往是 soft clustering，不一定符合离散图聚类需求；Laplacian regularization 把 graph geometry 和平滑/稀疏倾向注入 H，从任务层面改变 inductive bias。LAI-SNMPBB 则是把输入矩阵乘法的信息流从 V full multiply 改为 low-rank surrogate multiply，属于计算路径重排；其理论上有趣的一点是，在 fixed block 下 BB curvature 不受 V→AB 的常数梯度偏差影响。

Method

1. Penalty-based two-variable SymNMF：解决硬设 H=W^T 造成的优化自由度不足。二次 penalty 让 W,H 在优化早期可以偏离对称结构，从而更容易拟合数据和逃离糟糕尺度；同时 λ 项在梯度中持续拉回对称。核心变化是把原始 quartic 单变量问题转成 alternating block-wise quadratic 问题。

2. Nonmonotone projected BB update：解决普通 PGD 的步长脆弱性。BB 步长用相邻迭代差和梯度差估计局部曲率，相当于低成本 spectral scaling；nonmonotone Armijo 允许短期 objective 上升，避免非凸地形中被过保守 line search 卡死。核心变化是让一阶法拥有更接近 quasi-Newton 的尺度适配，但不承担 ANLS / Newton 的求解成本。

3. Two-stage projection：先用 Lipschitz-like scaling 得到 Z，再从 Z 用 BB step 构造 projected direction。这个设计本质上是在 separating feasibility correction 与 curvature-informed movement：第一步保证局部安全下降方向，第二步利用曲率加速。

4. Graph Laplacian regularization：解决 factorization residual 好但 clustering assignment 差的问题。Laplacian 项不是优化技巧，而是任务 bias：把 similarity graph 的局部几何压进 factor，使表示更适合聚类而不只是重构。

5. LAI integration：解决大规模 V 的乘法瓶颈。用 randomized low-rank approximation AB 替代 V，使 VH 这类乘法变成 U E (U^T H)。核心变化是计算复杂度从依赖 full n^2 multiply 转向 nℓr。文中关于 BB curvature preserved 的分析说明：在固定 H 时，V→AB 只引入对 W 常数的梯度偏置，梯度差里的偏置抵消，因此 BB 步长不变。

Key Insight / Why It Works

最重要的 insight 是：SymNMF 上 projected gradient 的失败，很大程度不是 projection 或一阶信息本身的问题，而是 hard symmetric parameterization 让优化几何太差。保留 W,H 两套变量后，每个 block 的曲率结构变得接近普通 NMF；此时 NMPBB 的已有优势可以直接释放出来。这是本文最有价值的判断。

真正有效的部分我认为排序如下：第一是 penalty formulation 保留自由度，这是基础；没有它，BB 和 line search 很可能只是在坏地形上加速震荡或保守下降。第二是 BB step-size，它直接处理尺度和 curvature，尤其 rank 增大时比固定 Lipschitz PGD 更占优。第三是 nonmonotone line search，它更多是 globalization 和稳定器，保证 BB 的 aggressive step 不至于炸掉。Graph regularization 对聚类结果很重要，但它解决的是 task alignment，不是 SymNMF 优化本体。

LAI 部分的“BB curvature preserved”是一个干净但有限的理论点：因为 fixed block 下 V 只出现在线性项，替换 V 为 AB 只改变梯度常数项，不改变 Hessian-like curvature，所以 Y_k 中偏差抵消。这解释了为什么低秩近似不会破坏 BB 步长。但这不等于低秩近似不影响解；它只说明 curvature estimate 不变，gradient bias 仍然由 µ||H|| 控制。

实验增益中有一部分可能主要来自 scaling：一阶方法 O(n^2r) 对比 ANLS O(n^2r^2)，rank 增大时自然更快；LAI-SNMPBB 对 LAI-SymPGNCG 的优势也可能混合了 low-rank multiply、inner iteration cap、MATLAB 实现和 stopping rule。文中没有充分拆解这些来源。

对于 clustering，Graph-SNMPBB 的高 accuracy 不应简单归因于优化器。KNN 图构造、Gaussian kernel、Laplacian regularization 和初始化都可能贡献显著 inductive bias。这里更像 representation alignment：优化目标被改成更贴合 graph clustering，而不是同一个 SymNMF objective 被更好优化。

Relation To Prior Work

这篇最接近三条线：SymANLS 的 penalty-based SymNMF，NMF 中的 QRPBB/NMPBB projected spectral gradient，以及 Hayashi et al. 的 LAI-SymNMF。它的新意不是单个技术模块，而是把这些思想放到 SymNMF 的正确位置上。

相对 SymANLS，本文继承了软对称惩罚，但把 block update 从非负 least-squares 求解换成 projected BB gradient。实质差异是“精确/较精确子问题求解”换成“便宜的 curvature-aware inexact step”。这使它更 scalable，尤其对高 rank 更友好。

相对普通 PGD 或 Zhang/Liu 类 simultaneous PGD，本文不是简单调大步长，而是引入 BB 曲率估计和非单调 line search，并避免硬 symmetric assignment。它属于 spectral projected gradient 的技术谱系，而不是普通 first-order descent。

相对 graph-regularized NMF，Laplacian 项并不新；新的是把 Laplacian 放进 penalty-coupled SymNMF + NMPBB 的更新中。这里的新信息有限，更像把已有 graph bias 移植到该优化框架。

相对 LAI-SymPGNCG，LAI 本身来自 prior；本文实质新增的是说明 projected BB 的 curvature information 在 V→AB 后保持不变，并展示一阶 LAI 版本比 Gauss-Newton/CG 更轻。这个理论点简洁，但作用范围局限在 fixed block 的 BB step。

Dataset / Evaluation

评估覆盖面还算宽：synthetic dense SymNMF 用来验证 residual/runtime，bullseye 和多个真实数据集验证 graph clustering，SuiteSparse 和 Web of Science 验证 LAI 大规模输入。整体上支持论文主张：properly adapted projected gradient 在 SymNMF 中并不弱，且在高 rank / 大矩阵设置下有明显 runtime advantage。

但 evaluation 更像证明 practical competitiveness，而不是严格归因。论文没有足够系统的 ablation：没有清楚分离 penalty formulation、BB 步长、nonmonotone line search、relaxation factor、Laplacian 正则、KNN preprocessing、early stopping 的贡献。尤其 graph clustering 中，Graph-SNMPBB 的优势可能来自目标函数和 preprocessing 更适配，而不是优化算法本身。

Synthetic 设置 V=WW^T 对 SymNMF 友好，能够检验恢复类行为，但不代表真实噪声、degree heterogeneity 或非低秩图上的表现。SuiteSparse 结果比较有价值，因为规模和稀疏结构更真实；不过 LAI-SNMPBB 使用 3-5 inner iterations early stopping，这本身是强 engineering choice，且与对手是否等价调参不完全清楚。

硬件是单台 M1 Max MATLAB，说明可复现性尚可，但 runtime 结论可能受实现影响。总体 evaluation 支持“这是一个强 baseline / practical algorithm”，但还不足以支持“优化机制全面优于 ANLS/Newton”的更强结论。

Limitation

第一，理论保证偏弱且基本是复用 NMPBB block-wise convergence：结论是 accumulation point 为 first-order stationary point，不涉及全局最优、聚类一致性，也不说明 relaxed penalty 解何时等价于硬 SymNMF 解。λ 取多大才能既保证 symmetry 又不破坏稀疏/拟合，文中更多是经验规则。

第二，方法把一部分困难从优化转移到 hyperparameter 和 preprocessing：λ、γ、KNN 的 K、Gaussian kernel 参数、初始化都会显著影响 clustering。Graph-SNMPBB 的泛化不是自动来自算法，而是依赖 graph construction 是否捕捉真实 manifold。

第三，LAI 的上限由低秩近似质量决定。文中给出 residual gap 与 µ=||V-AB|| 相关，但这只是 surrogate approximation 的误差界；如果 V 的有效结构不是低秩或 sketch 质量差，LAI-SNMPBB 会优化一个偏掉的目标。BB curvature preserved 也不能消除 gradient bias。

第四，增益归因不清。rank 增大时 SNMPBB 更快，很可能主要来自 O(n^2r) vs O(n^2r^2) 的 scaling，而不是更好的 optimization trajectory。Graph 任务上准确率提升可能主要来自 Laplacian regularization；LAI 任务上 residual 改善可能和 early stopping 的 implicit regularization 有关。

第五，line search 在极稀疏大矩阵上会 struggle，作者也承认需要限制 line-search 迭代。这说明算法稳定性仍依赖 engineering guardrails；不是一个完全 parameter-free 的 robust optimizer。

Takeaway

• 1. SymNMF 上一阶法被低估了；关键不是简单 PGD，而是要避免 hard symmetric parameterization，并给一阶法足够的 curvature scaling 和 globalization。
• 2. Penalty-coupled two-variable formulation 是可迁移 insight：当结构约束导致优化几何恶化时，软耦合保留自由度往往比硬 tying 更好，尤其适合 alternating first-order methods。
• 3. BB step 在 low-rank approximate input 下的 curvature invariance 是一个值得迁移的小理论点：如果 approximation 只改变 linear term，不改变 block Hessian，那么 spectral step-size 可以保持可靠。
• 4. 对 graph clustering，优化器本身不是全部；真正有效的是优化机制 + graph inductive bias + preprocessing 的组合。

一句话总结

这篇论文把 NMPBB 谱投影梯度、SymNMF 软对称惩罚和 LAI scaling 组合成一个强实用 baseline，真正贡献是证明 SymNMF 中一阶法的问题主要在 formulation 和尺度控制，而不在一阶法本身。