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

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

基本信息

  • 论文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是一种通用的网络数据建模方法，将节点分组到块中，节点间的连接用计数或标签来衡量。该模型族允许不同的dyad采样方案，包括经典SBM、泊松SBM和标记SBM，以及某些边观测被删失的情况。论文重点关注非伯努利SBM的有限样本检验，推导了生成参考分布样本所需的显式马尔科夫基移动，并定义了确定模型拟合的拟合优度统计量。对于标记SBM(包括删失边模型)，研究了这些统计量的渐近行为。

研究背景与动机

问题定义

  1. 核心问题: 如何对非伯努利的有值随机块模型进行拟合优度检验，特别是在有限样本情况下
  2. 重要性:
    • 网络数据分析中，确定节点的块成员关系是否影响网络形成是关键问题
    • 现有方法主要针对简单图(伯努利dyad)，而实际网络数据往往包含计数或多种类型的连接
    • 有限样本检验在小样本数据中具有重要实用价值

现有方法局限性

  1. 经典SBM限制: 大多数现有框架使用简单图，将dyad建模为伯努利随机变量
  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假设：

  • 条件独立性: Guv⊥ ⁣ ⁣ ⁣⊥Gu′v′∣ZG_{uv} \perp\!\!\!\perp G_{u'v'} | Z 对任意两个dyad
  • 指数族形式: 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和Bickel (2017)的似然模型选择

代数统计

  1. 马尔科夫基: Diaconis和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