Bridging Maximum Likelihood and Optimal Transport for Efficient Inference and Model Selection in Stochastic Block Models

技術的概要：確率的ブロックモデルにおける効率的な推論とモデル選択のための最大尤度と最適輸送の架け橋

問題定義
本論文は、ノードが隠れたクラスターに分割され、エッジの確率がクラスター所属に依存する生成モデルである確率的ブロックモデル（SBM）における推論とモデル選択の課題に取り組む。SBM は、モジュラリティ最大化やスペクトラルクラスタリングなどの代替的なクラスタリング手法と比較して、多様な構造を回復し、クラスター数の推定を提供するツールを備えるという利点を持つが、標準的な推論はしばしば変分期待値最大化（VEM）に依存している。VEM の決定的な限界は、最適化の滑らかさを保証するためにエントロピー正則化に依存している点にある。この正則化は輸送計画が疎になることを防ぎ、単一の最適化問題内で不要なクラスターを自動的に無効化（ゼロ質量を割り当て）する「内在的なモデル選択」能力を阻害する。その結果、現在の手法は、最適なクラスター数（$K$）を決定するために、計算コストの高いグリッドサーチやヒューリスティックな手順を必要とすることが多い。

手法
著者は、最適輸送（OT）の観点、特にセミリラクセッド・グロモフ・ワッサーシュタイン（srGW）ダイバージェンスを利用することにより、SBM における最大尤度変分推論（MLVI）を解釈する新たな枠組みを提案する。

1. srGW への再定式化: 本論文は、SBM における ELBO（エビデンス・ロワー・バウンド）の最大化が、エントロピー正則化項を伴う srGW ダイバージェンスの最小化と等価であることを確立する。損失関数は生成モデルの負の対数尤度に対応する。
2. 非正則化推定量: エントロピー正則化が疎性を妨げることを認識し、著者は非正則化された srGW 推定量を調査する。エントロピー項なしで srGW 損失を最小化することにより、接続行列（$\Theta$）と輸送計画（$T$、クラスター割り当てを表す）の推定量を定義する。
3. モデル選択のための疎性促進正則化: グリッドサーチなしで自動的なモデル選択（$K$の推定）を可能にするため、著者は輸送計画に対して $\ell_{1/2}$ 擬ノルムペナルティを導入する。このペナルティは推定されたクラスター比率を疎に促し、非最適なクラスターの質量を実質的にゼロに設定する。
4. 最適化: パラメータはブロック座標降下法を用いて推定される。これは以下の操作を交互に行う：
   • 一次最適性条件から導出された閉形式解を用いて接続行列 $\Theta$ を更新する。
   • 疎性ペナルティを線形化し、結果として生じる二次問題（例えば Frank-Wolfe 法による）を解くマジョリゼーション・ミニマゼーション（MM）アルゴリズムを用いて輸送計画 $T$ を更新する。

主要な貢献

• 理論的リンク: SBM における MLVI がエントロピー正則化を伴うセミリラクセッド・グロモフ・ワッサーシュタイン射影として解釈できることを証明する。
• 一致性の結果: 非正則化された srGW 推定量が、漸近的領域（$N \to \infty$）において、真の SBM 接続行列と潜在クラスター割り当ての両方を一貫して回復することを証明する。
• 自動モデル選択: 疎性促進ペナルティを組み込むことで、単一の最適化ステップでモデルパラメータの回復とクラスター数の選択を同時に行うことを可能にする。これにより、高コストなグリッドサーチや貪欲なヒューリスティックの必要性を回避する。
• アルゴリズム的効率性: 提案されたソルバーは効率性のために設計されており、理論的な計算量は勾配計算（$O(N^2K + K^2N)$）によって支配され、最先端の変分推定量と比較して CPU 上で著しく高速であることが示されている。

結果
著者は、アソシアティブ、ハブ、ディスアソシアティブの 3 つの接続レジーム下でベルヌーイ SBM から生成された合成データ上でアプローチを評価した。

• クラスタリング性能: 負の対数尤度損失を用いた提案された srGW 推定量（srGW-NLL）は、調整済みランダム指数（ARI）の観点から、特に他の手法の構造的仮定が違反されるハブおよびディスアソシアティブなレジームにおいて、Louvain、Infomap、Greed、変分推定量を含む最先端のベースラインと同等かそれ以上の性能を常に発揮する。
• モデル選択: この手法は、さまざまなハイパーパラメータ設定において真のクラスター数（$K^*$）を成功裡に回復し、疎性パラメータが適切に調整されたときに性能がプラトーに達することを示している。
• 効率性: srGW-NLL 法は、CPU 上で変分推定量および Greed 法よりも 1〜2 桁高速であると報告されており、これは主にそれらの手法が要求する反復的なモデル選択ループを回避しているためである。

意義と主張
本論文は、最適輸送と確率的ブロックモデルの間の統一的な理論的かつ実践的な架け橋を提供すると主張している。その主な意義は、OT ベースの推定量がパラメータ回復に対して一貫しているだけでなく、疎性促進を通じて内在的なモデル選択も実行できることを実証している点にある。これは、クラスター数の選択という組み合わせ的複雑さに苦しむ従来の尤度ベースの手法に対する計算的に効率的な代替手段を提供する。著者は、この研究を、特にコミュニティ数が未知でグラフ構造が複雑（例えば、ハブやディスアソシアティブなパターンを含む）なシナリオにおいて、より堅牢で効率的なグラフ分割への一歩として位置づけている。漸近的な一致性は証明されているが、疎性ハイパーパラメータの調整は将来の調査の領域であり、実世界のネットワークにおける手法の性能はさらなる研究の対象であると指摘している。