2025-11-23T19:04:16.167784

Non-asymptotic goodness-of-fit tests and model selection in valued stochastic blockmodels

Almendra-Hernández, Bakenhus, Karwa et al.
A valued stochastic blockmodel (SBM) is a general way to view networked data in which nodes are grouped into blocks and links between them are measured by counts or labels. This family allows for varying dyad sampling schemes, thereby including the classical, Poisson, and labeled SBMs, as well as those in which some edge observations are censored. This paper addresses the question of testing goodness-of-fit of such non-Bernoulli SBMs, focusing in particular on finite-sample tests. We derive explicit Markov bases moves necessary to generate samples from reference distributions and define goodness-of-fit statistics for determining model fit, comparable to those in the literature for related model families. For the labeled SBM, which includes in particular the censored-edge model, we study the asymptotic behavior of said statistics. One of the main purposes of testing goodness-of-fit of an SBM is to determine whether block membership of the nodes influences network formation. Power and Type 1 error rates are verified on simulated data. Additionally, we discuss the use of asymptotic results in selecting the number of blocks under the latent-block modeling assumption. The method derived for Poisson SBM is applied to ecological networks of host-parasite interactions. Our data analysis conclusions differ in selecting the number of blocks for the species from previous results in the literature.
academic

値付き確率的ブロックモデルにおける非漸近的適合度検定とモデル選択

基本情報

  • 論文ID: 2510.13636
  • タイトル: Non-asymptotic goodness-of-fit tests and model selection in valued stochastic blockmodels
  • 著者: Félix Almendra-Hernández, Miles Bakenhus, Vishesh Karwa, Mitsunori Ogawa, Sonja Petrović
  • 分類: stat.ME cs.SI math.ST stat.TH
  • 発表日: 2025年10月16日
  • 論文リンク: https://arxiv.org/abs/2510.13636

要約

本論文は、値付き確率的ブロックモデル(valued stochastic blockmodel, SBM)の適合度検定問題を研究している。値付きSBMは、ノードをブロックにグループ化し、ノード間の接続を計数またはラベルで測定するネットワークデータの汎用モデリング手法である。このモデルファミリーは、古典的SBM、ポアソンSBM、ラベル付きSBM、および特定のエッジ観測が打ち切られた場合を含む、異なるダイアド標本抽出スキームを許容する。論文は、非ベルヌーイSBMの有限標本検定に焦点を当て、参照分布サンプルを生成するために必要な明示的なマルコフ基の移動を導出し、モデル適合を決定する適合度統計量を定義している。ラベル付きSBM(打ち切りエッジモデルを含む)については、これらの統計量の漸近的性質を研究している。

研究背景と動機

問題定義

  1. 中心的課題: 非ベルヌーイの値付き確率的ブロックモデルに対して、特に有限標本の場合における適合度検定をいかに実施するか
  2. 重要性:
    • ネットワークデータ分析において、ノードのブロック所属がネットワーク形成に影響を与えるかどうかを判定することは重要な問題である
    • 既存の方法は主に単純グラフ(ベルヌーイダイアド)に対応しており、実際のネットワークデータはしばしば計数または複数種類の接続を含む
    • 有限標本検定は小標本データにおいて重要な実用的価値を有する

既存方法の限界

  1. 古典的SBMの制限: ほとんどの既存フレームワークは単純グラフを使用し、ダイアドをベルヌーイ確率変数としてモデル化している
  2. 漸近方法の問題: BICなどの大標本準則は、ネットワークモデルにおいてパラメータ次元が増加する場合に失効する
  3. 理論的保証の欠如: 既存の方法は帰無仮説分布と漸近的検定力に関する理論的保証を欠いている

研究動機

  • 代数統計におけるマルコフ基の方法を非ベルヌーイネットワークモデルに拡張する
  • パラメータ不確実性を考慮した部分ベイズ検定フレームワークを構築する
  • モデル選択に対する理論的指導を提供する。特にブロック数の選択に関して

核心的貢献

  1. 理論的貢献:
    • ポアソンSBMおよびラベル付きSBMの明示的なマルコフ基を導出
    • 補間推定量の一貫性を証明
    • 適合度統計量の漸近理論を確立
  2. 方法論的貢献:
    • 固定ブロック割り当てと未知ブロック割り当ての場合における条件付き適合度検定を提案
    • 部分ベイズp値計算フレームワークを構築
    • MCMCに基づくファイバーサンプリングアルゴリズムを開発
  3. 応用的貢献:
    • 生態ネットワークの宿主-寄生虫相互作用分析に方法を適用
    • シミュレーションデータ上で方法の検定力と第一種過誤率を検証
    • モデル選択に対する実用的な指導原則を提供

方法の詳細

タスク定義

値付きネットワーク G=(Guv)1≤u<v≤nG = (G_{uv})_{1≤u<v≤n} が与えられた場合。ここで GuvG_{uv} はノード対 {u,v}\{u,v\} 間の接続強度(計数またはラベル)を表す。目標は以下の通りである:

  1. ネットワークが与えられた値付きSBMに適合するかを検定する
  2. ブロック割り当てが未知の場合にモデル適合検定を実施する
  3. 適切なブロック数 kk を選択する

モデルアーキテクチャ

1. 値付きSBMの定義

nn 個のノードと kk 個のブロックに対して、値付きSBMは以下を仮定する:

  • 条件付き独立性: 任意の2つのダイアドに対して Guv⊥ ⁣ ⁣ ⁣⊥Gu′v′∣ZG_{uv} \perp\!\!\!\perp G_{u'v'} | Z
  • 指数族形式: Pθ(G=g∣Z=z)=∏1≤u<v≤nh(guv)exp⁡⟨Tz(guv),θzuzv⟩ψ(θzuzv)P_θ(G = g | Z = z) = \prod_{1≤u<v≤n} \frac{h(g_{uv})\exp⟨T_z(g_{uv}), θ_{z_uz_v}⟩}{ψ(θ_{z_uz_v})}

ここで hh は基測度、TzT_z は十分統計量、θθ はパラメータベクトルである。

2. 特殊な場合

  • 古典的SBM: Guv∣Z=z∼Bernoulli(θzuzv)G_{uv} | Z = z \sim \text{Bernoulli}(θ_{z_uz_v})
  • ポアソンSBM: Guv∣Z=z∼Poisson(θzuzv)G_{uv} | Z = z \sim \text{Poisson}(θ_{z_uz_v})
  • ラベル付きSBM: Guv∣Z=z∼Multinomial(N,(θzuzv(ℓ))ℓ=1L)G_{uv} | Z = z \sim \text{Multinomial}(N, (θ^{(ℓ)}_{z_uz_v})^L_{ℓ=1})

3. マルコフ基の構成

ポアソンSBMのマルコフ基: B={εuv−εu′v′:zu=zu′,zv=zv′}B = \{ε_{uv} - ε_{u'v'} : z_u = z_{u'}, z_v = z_{v'}\}

ラベル付きSBMのマルコフ基: B={εuv(ℓ)+εu′v′(ℓ′)−εuv(ℓ′)−εu′v′(ℓ):ℓ,ℓ′∈[L],zu=zu′,zv=zv′}B = \{ε^{(ℓ)}_{uv} + ε^{(ℓ')}_{u'v'} - ε^{(ℓ')}_{uv} - ε^{(ℓ)}_{u'v'} : ℓ,ℓ' ∈ [L], z_u = z_{u'}, z_v = z_{v'}\}

技術的革新点

1. 条件付き検定フレームワーク

  • ファイバー定義: Fz,t:={g∈G:Tz(g)=t}F_{z,t} := \{g ∈ G : T_z(g) = t\}
  • 条件付き分布: P(G=g∣Tz(g)=t)=h(g)∑g′∈Fz,th(g′)P(G = g | T_z(g) = t) = \frac{h(g)}{\sum_{g' ∈ F_{z,t}} h(g')}
  • 正確なp値: p(z,g)=P(GoFz(G)≥GoFz(g)∣Tz(g))p(z,g) = P(\text{GoF}_z(G) ≥ \text{GoF}_z(g) | T_z(g))

2. 部分ベイズ法

未知のブロック割り当てに対して、部分ベイズp値を以下のように定義する: pb(g)=∑z∈Zn,kp(z,g)P(Z=z∣g)p_b(g) = \sum_{z ∈ Z_{n,k}} p(z,g)P(Z = z | g)

この方法は、ブロック割り当ての不確実性を事後分布に対する平均化により処理する。

3. 適合度統計量

ポアソンSBM: GoFz(g)=∑u=1n∑i=1k(mui−niθ^zui)2niθ^zui\text{GoF}_z(g) = \sum_{u=1}^n \sum_{i=1}^k \frac{(m_{ui} - n_iθ̂_{z_ui})^2}{n_iθ̂_{z_ui}}

ラベル付きSBM: GoFz(g)=χBC2(g,z)=∑u=1n∑i=1k∑ℓ=1L−1(mui(ℓ)−niθ^zui(ℓ))2niθ^zui(ℓ)\text{GoF}_z(g) = χ^2_{BC}(g,z) = \sum_{u=1}^n \sum_{i=1}^k \sum_{ℓ=1}^{L-1} \frac{(m^{(ℓ)}_{ui} - n_iθ̂^{(ℓ)}_{z_ui})^2}{n_iθ̂^{(ℓ)}_{z_ui}}

実験設定

データセット

  1. シミュレーションデータ:
    • ノード数: n=50,100n = 50, 100
    • 4種類の異なる接続行列 θ(1),θ(2),θ(3),θ(4)θ^{(1)}, θ^{(2)}, θ^{(3)}, θ^{(4)}
    • 各設定に対して100個のグラフを生成
  2. 実データ:
    • 寄生真菌物種ネットワーク(154ノード)
    • 樹種ネットワーク(51ノード)
    • エッジ重みは共有宿主/寄生虫物種数を表す

評価指標

  1. 第一種過誤率: 有意水準0.05における帰無仮説の棄却率
  2. 検定力: 異なるブロック数下でのモデル棄却率
  3. モデル選択精度: ICL準則との比較

比較方法

  • ICL(積分完全尤度)準則
  • ブロック割り当て推定のための変分EMアルゴリズム
  • sbm Rパッケージの実装

実装の詳細

  • MCMCチェーン長: numGraphsパラメータで制御
  • ブロック割り当て推定: 変分EMアルゴリズムを使用
  • 事後確率閾値: ε=1/mε = 1/m。ここでmmはサポートセットサイズ

実験結果

主要な結果

1. 検定力と第一種過誤率の検証

n=50n=50の場合の結果:

θ2ブロック3ブロック4ブロック5ブロック
θ⁽¹⁾1.000.590.050.01
θ⁽²⁾1.000.660.030.03
θ⁽³⁾0.881.000.070.04
θ⁽⁴⁾1.000.990.060.03

n=100n=100の場合の結果:

θ2ブロック3ブロック4ブロック5ブロック
θ⁽¹⁾1.000.980.050.00
θ⁽²⁾1.001.000.060.01
θ⁽³⁾1.001.000.080.02
θ⁽⁴⁾1.001.000.080.02

2. 実データへの応用

樹種ネットワーク:

  • ブロック数3-7: p値 = 0
  • ブロック数8-9: p値 = 0.01
  • ブロック数10: p値 = 0.19
  • ブロック数11-15: p値 ≥ 0.68

真菌物種ネットワーク:

  • ブロック数3-17: p値 = 0
  • ブロック数18-21: p値 = 0.01
  • ブロック数22: p値 = 0.07

実験的発見

  1. 方法の有効性: 2または3ブロック使用時の棄却率は1に近く、4または5ブロック使用時は0に近く、予想通りである
  2. 標本量の効果: より大きな標本量(n=100n=100)はより強い統計的検定力を提供する
  3. 既存方法との相違:
    • 本方法は樹種ネットワークで10ブロック、真菌ネットワークで22ブロックを選択
    • ICL準則は樹種ネットワークで7ブロック、真菌ネットワークで9ブロックを選択
    • 相違は方法の保守性とモデル適合に対する厳密な要件に起因する可能性がある

関連研究

ネットワーク適合度検定

  1. スペクトル法: Lei (2016)のスペクトル適合度検定
  2. ERGM法: Hunter等(2008)の参照分布比較方法
  3. 改善された検定: Hu等(2021)による計算コストと理論的保証の直接的解決

確率的ブロックモデル

  1. 古典的SBM: Holland等(1983)の潜在ブロック拡張
  2. 値付きネットワーク: Krivitsky (2012)の計数ネットワークへのERGM拡張
  3. モデル選択: Wang and Bickel (2017)の尤度ベースモデル選択

代数統計

  1. マルコフ基: Diaconis and Sturmfels (1998)の基礎理論
  2. ネットワーク応用: Karwa等(2023)のベルヌーイSBMに対する有限標本検定
  3. 動的構成: Gross等(2014)の動的マルコフ基方法

結論と考察

主要な結論

  1. 理論的貢献: 代数統計の方法を非ベルヌーイネットワークモデルに成功裏に拡張し、厳密な理論的基礎を提供した
  2. 方法の有効性: 提案された検定方法はシミュレーションおよび実データ上で良好な統計的性質を示す
  3. 実用的価値: 値付きネットワークのモデル選択に対して実行可能な解決策を提供する

限界

  1. 計算複雑性: MCMC法は大規模ネットワーク上で収束問題に直面する可能性がある
  2. 保守性: 方法は過度に保守的である可能性があり、より多くのブロック数を選択する傾向がある
  3. ブロック割り当て依存性: 方法はブロック割り当て推定の質に依存する

将来の方向性

  1. 複合マルコフ連鎖: 複数のファイバーをサンプリングできる方法の開発
  2. 計算最適化: MCMC収束性と計算効率の改善
  3. 応用の拡張: 動的ネットワークおよび多層ネットワークとの統合

深層的評価

利点

  1. 理論的厳密性: 一貫性証明と漸近分析を含む完全な理論フレームワークを提供
  2. 方法の新規性: マルコフ基の方法を非ベルヌーイSBMに初めて適用
  3. 実験の包括性: 検定力分析、第一種過誤率検証、実データ応用を含む
  4. 記述の明確性: 論文の構成は合理的で、技術的詳細は正確に記述されている

不足点

  1. 計算上の課題: 大規模ネットワークに対して計算複雑性がボトルネックになる可能性がある
  2. パラメータ感度: 方法はブロック割り当て推定の質に対して比較的敏感である
  3. 比較の限定性: 他の非漸近的方法との比較が十分ではない

影響力

  1. 学術的価値: ネットワーク統計と代数統計の交差研究に新しい方向を開く
  2. 実用的価値: 生態学、社会科学などの分野のネットワーク分析にツールを提供
  3. 再現性: 詳細なアルゴリズム記述により実装と再現が容易

適用可能なシナリオ

  1. 小から中規模のネットワーク: ノード数が数百以下の場合に方法は良好に機能
  2. 値付きネットワークデータ: 特に計数または多ラベルのネットワークデータに適している
  3. 厳密な統計推論: 正確な統計推論が必要なアプリケーションシナリオ

参考文献

主要な参考文献は以下を含む:

  • Diaconis, P. and Sturmfels, B. (1998). Algebraic algorithms for sampling from conditional distributions
  • Holland, P. W., Laskey, K. B., and Leinhardt, S. (1983). Stochastic blockmodels: First steps
  • Karwa, V. et al. (2023). Monte Carlo goodness-of-fit tests for degree corrected and related stochastic blockmodels
  • Wang, Y. X. R. and Bickel, P. J. (2017). Likelihood-based model selection for stochastic block models