Modularity maximization and community detection in complex networks through recursive and hierarchical annealing in the D-Wave Advantage quantum processing units

技術要約：D-Waveにおける再帰的階層アニーリングによるモジュラリティ最大化とコミュニティ検出

問題提起
複雑ネットワークにおけるコミュニティ検出は、ネットワーク科学における基本的な問題であり、通常、モジュラリティ指数（$Q$）の最大化として定式化される。この最適化タスクはNP困難である。古典的なヒューリスティック・アルゴリズム（LouvainやLeidenなど）は存在するが、これらはグローバルな最適解を保証するものではない。量子アニーリング（QA）は、エネルギー地形のグローバルな最小値を見つけ出すことで、このようなNP困難な問題を解決するための潜在的な経路を提供する。しかし、純粋なQAをコミュニティ検出に適用する際の大きな障壁は、問題のエンコーディングにある。標準的な手法は、多くの場合、$M$ 個のコミュニティを表現するために $N \times M$ 個のバイナリ変数を用いる「ワンホット（one-hot）」エンコーディングに依存している。これは、各ノードが必ず正確に一つのコミュニティに属することを保証するためのハード制約（ラグランジュ乗数による）を必要とする。これらのペナルティ重みのチューニングは経験的に困難であり、しばしば問題固有の推測を必要とし、量子プロセスを不明瞭にし、スケーラビリティを制限する可能性がある。さらに、既存のハイブリッド量子・古典ソリューションは、量子プロセッサと古典プロセッサの間の役割分担に関する透明性に欠けていることが多い。

手法
著者らは、D-Wave Advantage QPU上での純粋な量子アニーリングを用いてモジュラリティを最大化するために設計された、新しいアルゴリズムである**階層的アニーリング（Hierarchical Annealing）**を提案している。これは、ワンホット・エンコーディングやラグランジュ乗数を使用しない。

• 再帰的バイナリ分解: ノードを同時に $M$ 個のコミュニティに割り当てる代わりに、このアルゴリズムはネットワークを再帰的に細分化する。ネットワーク全体を単一のコミュニティとして開始し、各コミュニティを2つのサブコミュニティへと反復的に分割していく。これにより、問題は一連の制約なしのバイナリ最適化問題へと変換される。
• QUBO 定式化:
  • 無向ネットワークの場合: コミュニティ $k$ を $k_1$ と $k_2$ に分割することによるモジュラリティの利得は、二次無制約バイナリ最適化（QUBO）問題へとマッピングされる。コスト関数は、一般化されたモジュラリティ行列 $B^k$ から導出され、目的関数は負の変化量（$p_k = -[Q(C_{k+1}) - Q(C_k)]$）を最小化することである。
  • 有向ネットワークの場合: 著者らは、モジュラリティ行列の非対称性に対処するため、対称化された線形結合 $\frac{1}{2}(p_k + p_k^\top)$ を最適化する。これにより、階層の最初のステップが正しいグローバル関数を最適化し、線形項を伴わないQUBO形式が維持される。
• 解像度パラメータ ($\gamma$): 検出されるコミュニティのスケールを制御する解像度パラメータ $\gamma$ は、一般化されたモジュラリティ行列の計算に直接組み込まれている。アルゴリズムは、最適化構造に関して $\gamma$ に対して形式的に独立しており、$\gamma$ を自由パラメータとして扱うことができる。
• 実行フロー: プロセスは再帰的に実行される（アルゴリズム1）。各ステップにおいて、一般化されたモジュラリティ行列が計算され、QUBOが構築され、キャッシュからクリーク・エンベディング（clique embedding）がロードされる。D-Waveサンプラーは、バイナリQAを実行して最適な分割を見つけ出す。分割によって改善が見られない（モジュラリティの変化がゼロ）、または空集合になる場合に、再帰は停止する。
• 実装: 著者らは、D-WaveのエコシステムとインターフェースするPythonライブラリ Qommunity を開発した。Pegasusトポロジー（次数16）を持つAdvantageシステムを使用し、デフォルトのチェイン強度戦略と、切れたチェインに対する多数決を採用した。

主な貢献

1. 制約のない純粋量子アニーリング: 本研究は、ワンホット・エンコーディングやそれに伴うラグランジュ乗数のチューニングの困難さを回避し、純粋なアニーラーのみを使用してモジュラリティ最大化のグローバル最適解を見つけるための体系的な手順を実証した。
2. 一般化された定式化: 著者らは、無向、有向、および重み付きネットワークを統一された再帰的フレームワーク内で扱うために、モジュラリティ最大化の定式化を拡張した。
3. 解釈可能性: 「ブラックボックス」的なハイブリッドソルバーとは異なり、再帰的な性質を持つこのアルゴリズムは、中間的な細分化を示すデンドログラム（樹状図）を生成する。これは、異なる解像度レベルでネットワーク構造がどのように展開するかという、解釈可能な視点を提供する。
4. スケーラビリティと効率性: 本研究は、このアプローチが（LouvainやLeidenなどの）最先端の古典的アルゴリズムと同等、あるいはそれ以上の最適解を提供しつつ、扱いやすい計算時間を維持するという実証的な証拠を提供している。

結果

• ベンチマーク: アルゴリズムは、Erdős-Rényi、Barabási-Albert、べき乗則に従うクラスター化ネットワーク、および有向スケールフリーネットワークを含む、様々なネットワーク・トポロジーでテストされた。
  • 単純な3つのクリークからなる鎖およびZachary Karate Clubネットワークにおいて、H. AnnealingはLouvainおよびLeidenと同等、あるいはそれをわずかに上回るモジュラリティ・スコアを達成した。
  • 確率的ブロックモデル（SBM）において、本手法は、様々な混合パラメータにわたって、植え付けられたコミュニティを正常に回収し、確率的推論手法に対して競争力のある性能を示した。
  • スケールフリーネットワークにおいて、アルゴリズムは堅牢な性能を示し、特に固有の階層が存在する場合、モジュラリティ・スコアにおいて古典的な対抗馬を凌駕することが多かった。
• 解像度の感度: アルゴリズムは、解像度パラメータ $\gamma$ の異なる値に対して安定していた。有向ネットワークにおいて極端な $\gamma$ の値に対して性能がわずかに低下したものの、$\gamma=1$ 付近では競争力を維持した。
• 計算複雑性:
  • 古典的な前処理（モジュラリティ行列の計算）は $O(n^2)$ でスケールする。
  • 再帰的なツリーの複雑性は、バランスの取れた分割を仮定した場合、Akra-Bazziの定理に基づき $O(n \log n)$ と推定される。
  • 実証的に、QPUへのアクセス時間はネットワークサイズに対して対数的にスケールした（$t \propto \ln N$）。これは、量子コンポーネントが効率的にスケールしていることを示唆している。
  • 総実行時間は、QPUの実行時間そのものよりも、通信およびキューイングのオーバーヘッドによって支配されている。
• 実世界への応用: 本手法は、実際の脳の構造的結合ネットワーク（166ノード）に適用された。得られたコミュニティ構造とデンドログラムは、LouvainおよびLeidenによる結果と高度に一致しており、差異は非常に相互接続性の高い前頭頂部付近にのみ見られた。

意義と主張
本論文は、本研究を「純粋量子アニーリングの適用可能な実践的使用への第一歩」と位置づけている。著者らは、ハイブリッドな「ブラックボックス」ソリューションや複雑な制約チューニングに依存することなく、純粋なQAがコミュニティ検出問題を解決できることを示すことで、ネットワーク科学と量子コンピューティングの間の溝を埋めると主張している。

その意義は以下の点にある：

• 透明性: 単一のフラットな分割ではなく、解釈可能な再帰的ソリューション（デンドログラム）を提供すること。これは、脳ネットワークのような複雑なシステムにおける隠れた階層を明らかにする上で価値がある。
• 実現可能性: 現在の量子ハードウェア（D-Wave Advantage）が、実用的な規模（テストされた最大約166ノード、Pegasusトポロジーによる制限）のコミュニティ検出タスクを、競争力のある性能で処理できることを示したこと。
• 方法論的転換: ワンホット・エンコーディングを回避する、ペナルティ重みの経験的なチューニングを必要としない実行可能な代替案を提示し、量子最適化をネットワーク分析においてよりアクセスしやすいものにする可能性があること。

著者らは、再帰的なプロセスがグローバルな最適性を保証するわけではないこと（これはすべてのNP困難な問題に対するヒューリスティックに共通する制限である）を認め、謙虚な姿勢を保っている。また、非常に大規模なネットワークへのスケーラビリティには、通信オーバーヘッドを軽減するためにハイブリッドソルバーやローカルなQPUアクセスが必要になる可能性があることも認めている。彼らは、古典的手法に対して普遍的な優位性を主張しているのではなく、特定のトポロジカルな文脈において、量子アニーリングが意味のある、解釈可能で、かつ同等に最適なソリューションを提供できる可能性を強調している。