技術要約：対称非負行列因子分解およびグラフクラスタリングのための非単調勾配ベース・アルゴリズム

1. 問題設定

対称非負行列因子分解（Symmetric NMF）は、対称な非負行列 $V \in \mathbb{R}^{n \times n}$ を $V \approx WW^T$ （ここで $W \in \mathbb{R}^{n \times r}_+$ は非負の長方形因子）として近似することを目的とする。この問題は、K-meansクラスタリングと等価であり、非線形グラフデータのクラスタリングが可能なことから、グラフクラスタリングや機械学習において中心的な役割を果たす。

標準的なNMF（$V \approx WH$ の因子分解）には確立されたアルゴリズムが存在するが、対称NMFは特有の課題を提示する。目的関数 $f(W) = \frac{1}{2}\|V - WW^T\|^2$ は、4次式であり非凸である。歴史的に、対称NMFに対する射影勾配（PG）法は、収束の遅さと堅牢性の低さから、交互非負最小二乗法（ANLS）アプローチ（例：SymANLS）よりも劣ると見なされてきた。既存のPG法は、スケーリングの問題や対称問題特有の曲率に苦しむことが多く、その結果、より計算コストの高い高次手法（ニュートン法に基づく手法）や、計算負荷の高いANLSの一連の最小二乗解法への依存を招いている。

2. 手法

著者らは、対称NMFのために特別に設計された、非単調射影Barzilai-Borwein法の新しい適応版であるSNMPBB（Symmetric Nonmonotone Projected Barzilai-Borquien）を導入する。本手法は、以下の3つのコアメカニズムを通じて、素朴な対称拡張の限界に対処している。

2.1. ペナルティに基づく結合

$H = W^T$ と単純に設定して問題を単一の変数に集約するのではなく（これは自由度を制限することになる）、SNMPBBは2つの変数 $W$ と $H$ を保持し、それらを二次ペナルティによって結合する。目的関数は以下のように定義される：
$$f(W, H; \lambda) = \frac{1}{2}\|V - WH\|^2 + \frac{\lambda}{2}\|W - H^T\|^2$$
ここで $\lambda \geq 0$ はペナルティパラメータである。この定式化により、ペナルティ項から導出される勾配を通じて対称性を強制しつつ、標準的なNMFの勾配更新を使用することが可能となる。

2.2. 非単調射影Barzilai-Borwein (NMPBB) フレームワーク

本アルゴリズムは、2段階の射影スキームと適応的ステップサイズを利用する：

1. 適応的ステップサイズ: 行列値の問題用にフロベニウス内積を用いて適応させたBarzilai-Borquien (BB) ステップサイズを採用する。ステップサイズ $\alpha_k$ は、反復の変化量 $S$ と勾配の変化量 $Y$ を用いて $\langle S_{k-1}, S_{k-1} \rangle / \langle S_{k-1}, Y_{k-1} \rangle$ として計算される。これにより、一次コストでニュートン法に近い挙動を近似する。
2. 2段階射影:
   • まず、勾配のリプシッツ定数に関連する自動スケーリング因子 $\rho_0$ を用いた標準的な射影勾配ステップを使用して、試行点 $Z_k$ を計算する。
   • 次に、BBステップサイズを用いて $Z_k$ から降下方向 $D_k$ を形成する。
3. 非単調ラインサーチ: すべての反復で単調減少を要求する従来のメソッドとは異なり、SNMPBBは非単調ラインサーチを使用する。これは、新しい目的関数値を、最近の関数値の加重平均である参照値 $F_k$ と比較する。この緩和により、アルゴリズムは局所解を脱出し、非凸なランドスケープをより効果的に扱うことができる。また、降下ステップを増幅するために緩和係数 $\phi$ が適用される。

2.3. 拡張

• Graph-SNMPBB: グラフクラスタリングにおいて、本手法はソフトクラスタリングの問題に対処し、クラスタの質を向上させるためにグラフ・ラプラシアン正則化を組み込んでいる。目的関数には $\frac{\gamma}{2}\text{tr}(HLH^T)$ という項が含まれる（ここで $L$ はグラフ・ラプラシアン）。
• LAI-SNMPBB: 大規模問題に対処するため、低ランク近似入力（Low-rank Approximate Input: LAI）の手法を統合している。入力行列 $V$ はランダム化されたスケッチング（$V \approx AB$）によって近似される。極めて重要な点は、BBステップサイズの計算がこの近似誤差に対して不変であることを著者らが証明した点である。すなわち、近似によって導入されるバイアスは、BBステップで使用される勾配の差分において相殺される。

3. 理論的分析

論文では厳密な収束保証が提供されている：

• 大域的収束: SNMPBBが、一次の停留点に対して大域的に収束することが証明されている。この証明は、一方の変数を固定した際の目的関数の凸性と、勾配のリプシッツ連続性に依拠している。
• 曲率の保持: LAIバリアントにおいて、解析は $V$ の低ランク近似にもかかわらず、Barzilai-Borquienの曲率情報が保持されることを示している。近似によって導入される勾配のバイアスは、変数の更新に対して一定であるため、ステップサイズの計算には影響を与えない。
• 誤差境界: LAI解と最適解の間の残差ギャップは、低ランクサロゲートの近似誤差の2倍によって抑えられる。

4. 実験結果

著者らは、合成データおよび実世界のデータセットを用いて、SNMPBBとそのバリアントを最先端の手法（SymANLS, SymNewton, PGD, および LAI-SymPGNCG）と比較評価した。

• 合成データ: 密な合成行列において、SNMPBBは同様の残差値に対してSymANLSに対して6倍、SymNewtonに対して2倍の高速化を達成した。SNMPBBの性能優位性はランク $r$ が増加するにつれて顕著になり、これはALSやニュートン法の複雑度である $O(n^2r^2)$ または $O(n^3r^3)$ に対する一次手法のスケール性の高さを浮き彫りにしている。
• グラフクラスタリング・ベンチマーク: 6つの実世界データセット（COIL20, Isolet, MNIST, ORL, Reuters, TDT2を含む）において、Graph-SNMPBBはSymANLSと同等またはそれを上回るクラスタリング精度を実現しつつ、大幅に高速に収束した。この利点は、高次元で疎なテキストデータセット（Reuters, TDT2）や、強い視覚構造を持つ画像データセット（MNIST, COIL20）で最も顕著であった。
• 大規模LAIパフォーマンス: 34のSuiteSparse行列において、LAI-SNMPBBは実行時間と最終的な残差品質の両面で、最先端のLAI-SymPGNCGを上回った。
  • 主要な知見として、内部の勾配降下反復回数を3〜5ステップに制限する（早期停止）ことで、低ランク近似誤差への過学習を防ぎ、これが暗黙的な正則化メカニズムとして機能することが挙げられる。これにより、内部ループを完全な収束まで実行する場合と比較して、より優れた汎化性能と高速な収束が得られた。

5. 意義と主張

本論文は、対称NMFに対する射影勾配法が歴史的に過小評価されてきたと主張している。非単調ラインサーチ、Barzilai-Borquienステップサイズ、およびペナルティに基づく結合を統合することで、著者らは、一次勾配アルゴリズムがこれまで理解されていたよりもはるかに効果的になり得ることを示している。

主な貢献は以下の通りである：

1. SNMPBB: 非単調射影Barzilai-Borquien法を対称NMFに初めて適応させ、勾配アルゴリズムが速度と精度の両面で、確立された交互最小二乗法やニュートンベースの手法を凌駕できることを証明した。
2. Graph-SNMPBB: グラフ・ラプラシアン正則化を適用して、実世界のベンチマークにおけるクラスタリング性能を向上させる拡張版。
3. LAI-SNMPBB: 低ランク近似下でもBB曲率情報を保持し、早期停止を正則化戦略として利用する、大規模問題のためのスケーラブルなバリアント。

結論として、適切な適応（曲率スケーリング、グローバル化戦略、および正則化）を行うことで、一次手法は対称行列の因子分解およびグラフクラスタリングにおいて、計算効率、スケーラビリティ、および解の質の優れたバランスを提供できる。