Ordering Stochastic Block Models via prior transitivity

技術要約：事前分布の推移性による順序付きストカスティック・ブロックモデルの推定

問題提起
有向ネットワークは、多くの場合、2つの同時的な構造的特徴を示している：コミュニティ構造（ノードが類似した相互作用パターンを持つグループを形成すること）と、階層構造（グループが順序立てて相互作用し、エッジが主に高ランクのグループから低ランクのグループへと流れること）である。既存の手法は通常、これらの特徴を個別に扱う。標準的なストカスティック・ブロックモデル（SBM）はグループを回収できるが、一貫したブロックの順序を強制できず、一方でランキングモデルは個々のノードに順序を付けるが、構造的に等価なグループを特定することには失敗する。この分離は、グループレベルの階層のみが存在する場合にノードレベルの厳格な順序付けを強制してしまうか、あるいは、クラスター化されたデータ内にある階層的パターンを検出できないというリスクをもたらす。本論文は、順序付きブロックを共同で推論し、かつ推移的なブロック構造がデータによって支持されているかどうかを評価するための、統合されたフレームワークの必要性に取り組んでいる。

手法：推移的ストカスティック・ブロックモデル（TSBM）
著者らは、有向重み付きネットワークのためのベイズモデルである「推移的ストカスティック・ブロックモデル（TSBM）」を導入している。その手法は、以下の5つの柱に基づいている：

1. ボリューム／方向の分解： 本モデルは、有向エッジのカウントを2つの成分に分解する：

   • ボリューム（量）： ノード間の全無向相互作用量。これは対称な強度行列とノード固有の次数傾向（次数補正SBMの枠組みに従う）を用いてモデル化される。
   • 方向： 相互作用が発生したという条件の下での、相互作用の方向の確率。この分離により、モデルは相互作用の頻度ではなく、方向性の不均衡に対して階層性を課すことが可能になる。

2. 推移性を誘導する事前分布： モデルは、方向の対数オッズ（$\psi$）に対する事前分布を通じて、ブロックに順序を課す。2つの仕様が提案されている：

   • 弱ストカスティック推移性（WST）： 循環的な支配パターン（例：$A \succ B \succ C \succ A$）を排除する柔軟な事前分布であり、ブロック $k$ が $\ell$ を支配し、$\ell$ が $m$ を支配する場合、 $k$ は $m$ を支配することを保証する。これは、上三角の対数オッズに対する独立な切断ガウス事前分布によって実現される。
   • 強ストカスティック推移性（SST）： より制約の強い事前分布であり、特にToeplitz SST版がある。これは、方向的な優位性がランクの差に応じて増加すると仮定する（すなわち、高ランクのブロックが低ランクのブロックに対して持つ優位性は、中ランクのブロックに対して持つものよりも大きい）。これは、対数オッズがブロック間の距離のみに依存し、正の増分による累積和によって単調増加が強制されると仮定することでモデル化される。

3. 順序付き分割事前分布： 順序付きのブロックラベルは交換可能ではない（ラベルを置換すると階層性が変わり、したがって尤度も変わる）ため、標準的な交換可能な分割事前分布は適さない。著者らは、年齢順分割事前分布（Donnelly and Tavaré, 1986; Donnelly and Joyce, 1991）を採用している。集団遺伝学由来のこの事前分布は、ブロックが時間（または年齢）に従って逐次的に出現するものとして扱い、可逆ジャンプMCMCを必要とせずに、ブロック数とノードの割り当ての同時推論を可能にする。

4. 事後推論： 推論は、部分的に崩壊させたギブスサンプラーを介して行われる。ロジスティック尤度とガウス事前分布の間の非共役性を扱うために、著者らはPólya-Gammaデータ拡張を利用している。これにより、方向確率、ボリュームパラメータ、およびノード割り当てに関する扱いやすい条件付き更新が可能となる。

5. モデル選択： パレート平滑化重要度サンプリングを用いたLeave-One-Out交差検証（LOO-CV）を用いて、TSBMの各バリアントを標準的な次数補正SBM（DC-SBM）と比較する。

主な貢献

• 新規なモデル定式化： TSBMは、ブロックレベルの確率に対する推移性の制約を用いて、有向ネットワークにおける確率的等価性と確率的順序を共同で推論する初のベイズモデルである。
• 計算の扱いやすさ： Pólya-Gammaデータ拡張と年齢順分割事前分布を組み合わせることで、ブロック数の推定において計算コストの高い次元横断的手法（可逆ジャンプなど）を回避する完全なギブスサンプラーを導出している。
• 柔軟な推移性： WSTとToeplitz SSTの両方の導入により、単純な非循環性からランク依存の支配まで、異なるレベルの階層的厳密さに適応できる。
• 診断能力： 本フレームワークは、順序を課すことが有害となるシナリオ（非推移的な引用ネットワークなど）を明示的に特定し、推移性の仮定の妥当性を評価するための確率的なメカニズムを提供する。

結果

• シミュレーション研究： 方向信号が弱い疎なネットワークにおいて、TSBM（WSTおよびSSTの両バリアント）は、予測精度（LOOIC）および分割の回収（情報の変動量）の両面で、標準的なDC-SBMを大幅に上回った。方向信号が強い密なネットワークでは、すべてのモデルが同様の性能を示した。決定的なことに、サイクルを含む（非推移的な）誤設定のシナリオでは、DC-SBMがTSBMを上回り、これは推移性の仮定が不適切であることをモデルが検出できることを示している。
• 実証的応用： モデルは、6つの有向重み付きネットワーク（動物の優位性、ジャーナル引用、学校の友人関係）に適用された：
  • 動物の優位性： ビホーンシープ、マウンテンゴート、および spotted hyena のネットワークにおいて、TSBMは一般に予測性能を向上させ、DC-SBMと比較して、より明確で一貫した階層構造（逆方向のエッジが少ない）を持つ分割をもたらした。
  • 引用： 統計学ジャーナルの引用ネットワークでは、DC-SBMの方が優れた性能を示した。著者らは、威信の勾配は存在するものの、引用パターンは厳密には推移的ではないため、順序付き事前分布がモデルを不必要に制約したと述べている。
  • マカック： マカックの優位性ネットワークでは、階層はすでにほぼ完璧であった（ほぼ厳格なノードレベルの順序）。ここでは、DC-SBMがTSBMをわずかに上回った。これは、データの強い信号に対して事前分布による正則化の恩益がほとんどなかったためである。
  • 友人関係： 高校の友人関係ネットワークにおいて、TSBMはグローバルな階層と一致するブロックレベルの順序を回収したが、DC-SBMは階層ではなくコミュニティ構造を反映する分割を生み出した。

意義と主張
本論文は、TSBMが順序付きグループを推定するための確率的フレームワークを提供し、さらに重要な点として、推移的なブロック構造がデータによって支持されているかどうかを評価するための枠組みを提供すると主張している。著者らは、モデルの価値は単に順序を強制することにあるのではなく、グルーピングと階層を共同でモデル化することにあり、それが特に方向信号が弱い場合やネットワークが疎である場合に、推論と予測を改善できる点にあると強調している。本研究は、非交換的なラベルを持つ潜在的ブロックモデルにおいて年齢順分割事前分布の有用性を示すことで、ベイズ非パラメトリック理論にも貢献している。著者らは、モデルの性能はデータに依存することを謙虚に述べており、対象となる構造が非推移的であるか、あるいは階層が極めて鋭い場合には、制約のないDC-SBMの方が好ましい場合があるとしている。