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

技术摘要：桥接最大似然与最优传输以实现随机块模型中的高效推断与模型选择

问题陈述
本文解决了随机块模型（SBM）中推断与模型选择的挑战。SBM 是一种生成随机图的框架，其中节点被划分为隐藏簇，且边的概率取决于簇的隶属关系。虽然 SBM 在恢复多样结构以及提供估计簇数量工具方面，相较于模度最大化或谱聚类等替代聚类方法具有优势，但标准推断通常依赖于变分期望最大化（VEM）。VEM 的一个关键局限性在于其依赖熵正则化以确保优化平滑性。这种正则化阻止了传输计划变得稀疏，从而阻碍了“内在模型选择”——即在单个优化问题中自动停用不必要的簇（将其质量设为零）的能力。因此，当前方法通常需要进行计算昂贵的网格搜索或启发式程序来确定最优簇数量（$K$）。

方法论
作者提出了一种新颖的框架，从最优传输（OT）的视角解读 SBM 中的最大似然变分推断（MLVI），具体利用了半松弛 Gromov-Wasserstein（srGW）散度。

1. 重述为 srGW： 本文确立了 SBM 中的证据下界（ELBO）最大化等价于最小化带有熵正则化项的 srGW 散度。损失函数对应于生成模型的负对数似然。
2. 无正则化估计量： 认识到熵正则化会阻碍稀疏性，作者研究了无正则化的 srGW 估计量。他们通过最小化不带熵项的 srGW 损失，定义了连通矩阵（$\Theta$）和传输计划（$T$，代表簇分配）的估计量。
3. 促进模型选择的稀疏性正则化： 为了在不进行网格搜索的情况下实现自动模型选择（估计 $K$），作者在传输计划上引入了 $\ell_{1/2}$ 伪范数惩罚。该惩罚鼓励估计的簇比例变得稀疏，有效地将非最优簇的质量设为零。
4. 优化： 参数估计使用块坐标下降算法。该算法交替进行：
   • 利用一阶最优条件导出的闭式解更新连通矩阵 $\Theta$。
   • 利用主化 - 最小化（MM）算法更新传输计划 $T$，该算法将稀疏性惩罚线性化并求解由此产生的二次问题（例如通过 Frank-Wolfe 方法）。

主要贡献

• 理论联系： 本文证明了 SBM 中的 MLVI 可以被解释为带有熵正则化的半松弛 Gromov-Wasserstein 投影。
• 一致性结果： 作者证明了无正则化的 srGW 估计量在渐近情形（$N \to \infty$）下能一致地恢复真实的 SBM 连通矩阵和潜在簇分配。
• 自动模型选择： 通过引入促进稀疏性的惩罚，该方法允许在单个优化步骤中同时恢复模型参数并选择簇数量。这避免了昂贵的网格搜索或贪婪启发式方法的需求。
• 算法效率： 所提出的求解器专为效率设计，其理论复杂度主要由梯度计算主导（$O(N^2K + K^2N)$），并且显示在 CPU 上比最先进的变分估计量快得多。

结果
作者在三种连通机制（ assortative、Hub 和 Disassortative）下生成的伯努利 SBM 合成数据上评估了他们的方法。

• 聚类性能： 所提出的使用负对数似然损失的 srGW 估计量（srGW-NLL）在调整兰德指数（ARI）方面始终优于或匹配最先进基线（包括 Louvain、Infomap、Greed 和变分估计量），特别是在 Hub 和 Disassortative 机制下，其他方法的结构假设在这些机制中被违反。
• 模型选择： 该方法在各种超参数设置下成功恢复了真实簇数量（$K^*$），当稀疏性参数调整适当时，性能表现出平台期。
• 效率： 据报道，srGW-NLL 方法在 CPU 上的速度比变分估计量和 Greed 方法快 1 到 2 个数量级，主要是因为它绕过了那些方法所需的迭代模型选择循环。

意义与主张
本文声称在最优传输与随机块模型之间提供了统一的理论和实践桥梁。其主要意义在于证明基于 OT 的估计量不仅对参数恢复具有一致性，而且可以通过促进稀疏性来执行内在模型选择。这为传统的基于似然的方法提供了一种计算高效的替代方案，后者在处理选择簇数量的组合复杂性时往往力不从心。作者将他们的工作定位为迈向更稳健、更高效图分割的一步，特别是在社区数量未知且图结构复杂（例如包含枢纽或 disassortative 模式）的场景中。他们指出，虽然渐近一致性已得到证明，但稀疏性超参数的调整仍是未来研究的领域，且该方法在真实世界网络上的性能有待进一步研究。