跳转至

Confidence sets in a sparse stochastic block model with two communities of unknown sizes

作者: B. J. K. Kleijn, J. van Waaij
来源: Electronic Journal of Statistics
主题: 数理统计 / 假设检验
相关性: 6/10
链接: 期刊页 · arXiv

一、领域脉络与小综述

这个方向是什么 网络社区检测的根本统计问题在于：给定一个观测到的随机图，如何推断潜在（不可观测）的社区分配结构，并量化该推断的不确定性。当前该子方向的成熟度表现为：在“点估计 / 恢复界限”层面已形成完整的相变理论（从不可检测到部分恢复再到精确恢复的阈值已被刻画）；但在“不确定性量化 / 频率置信集”层面，非渐近、有限样本的理论与计算方案才刚刚起步。

发展脉络 - 奠基与相变刻画：从 Erdős-Rényi 模型的推广出发，Holland 等 (1983) 引入 SBM；Decelle 等 (2011) 借助统计物理的 cavity method 提出社区检测的 Kesten-Stigum 阈值猜想，区分了可检测与不可检测的相变边界。 - 精确恢复的 sharp bounds：在等规模两社区（planted bi-section model）下，Mossel 等 (2014/2016) 与 Massoulié (2014) 证明了精确恢复的必要条件；Abbe 等 (2016) 证明了充分条件，确立了 Chernoff-Hellinger 阈值 \((\sqrt{a} - \sqrt{b})^2 > 1\)（其中 \(a=pn/\log n, b=qn/\log n\)）为精确恢复的 sharp threshold。 - Minimax 理论与算法可达性：Zhang & Zhou (2016) 给出了包括异质与稀疏设定在内的 minimax 误分类比率指数率；Gao 等 (2017) 提出两阶段法达到最优误分类比例；Hajek 等 (2016) 与 Guédon & Vershynin (2016) 证明半正定规划（SDP）松弛可达到精确恢复阈值。 - 贝叶斯后验收敛与频率推断的桥梁：Kleijn (2016) 提出了 Schwartz KL 条件的推广，证明在一般非参数 / 依赖数据设定下，后验可信集可转化为频率置信集；van Waaij & Kleijn (2021) 在等规模 planted bi-section 模型下具体化了后验集中不等式，并首次实现了可信-置信水平的转化。 - 本文的位置：本文将 van Waaij & Kleijn (2021) 的理论从“等规模两社区”推广至“不等规模两社区”，并在稀疏界限下推导了后验集中率与置信集构造，同时发现了可信-置信水平之间的非比例性相变现象及 MCMC 早停的计算可行性。

子线索聚类 1. 信息论阈值与相变理论：Decelle 等 (2011), Mossel 等 (2014/2016), Massoulié (2014), Abbe 等 (2016)。这一簇刻画了在不同稀疏度下（常数平均度 vs 对数平均度），社区结构是否可被任何算法 / 估计器恢复的统计极限。 2. 多项式时间算法与计算阈值：Krzakala 等 (2013) 的非回溯矩阵谱方法达到 KS 阈值；Hajek 等 (2016), Guédon & Vershynin (2016) 的 SDP 达到精确恢复阈值；Gao 等 (2017) 的两阶段法达到最优误分类率。这一簇关注在统计极限内，哪些算法能在多项式时间达到。 3. 贝叶斯方法与不确定性量化：Amini 等 (2013) 的伪似然；Geng 等 (2019) 与 Jiang & Tokdar (2021) 的未知社区数贝叶斯推断；Kleijn (2016) 的频率-贝叶斯桥梁；van Waaij & Kleijn (2021) 的等规模置信集。这一簇关注后验收敛、模型选择与频率意义下的覆盖保证。

核心追问与已知瓶颈 - 核心追问 1：在稀疏设定（边概率 \(O(\log n / n)\) 或 \(O(1/n)\)）下，社区分配的精确 / 几乎精确恢复的 sharp sparsity bound 是什么？已知瓶颈：等规模两社区已有 Chernoff-Hellinger 界限，但不等规模下的界限因社区比例未知而复杂化。 - 核心追问 2：如何为离散的社区分配构造非渐近的频率置信集？已知瓶颈：传统的 BvM 定理不适用于离散参数空间；后验可信集的覆盖概率与频率置信水平的映射关系未知。 - 核心追问 3：后验模拟（MCMC）在稀疏网络下的计算可行性？已知瓶颈：社区分配参数空间大小为 \(2^n\)，MCMC 在大 \(n\) 下混合时间爆炸；是否存在早停机制使得只需采样少数高概率分配即可构造置信集？

⚠️ 作者的 framing - 作者的说法：作者将缺口 frame 为“不等规模两社区的后验集中与置信集构造是等规模理论的显然推广，且可信-置信水平的非比例性相变是未被认识的现象”。作者强调自己的 sparsity bound 与 planted bi-section 模型已知的 sharp bounds 相当，从而暗示本文的理论界限是紧的。 - 被淡化或回避的竞争路线：作者未引用任何基于 SDP 或谱方法的频率置信集构造工作（如基于 SDP 的局部线性化或 subsampling/bootstrap 方法）；也未讨论计算阈值与统计阈值之间的 gap（即 KS 阈值以下的信息论可检测但多项式时间不可检测区域），而这正是近年统计-计算 tradeoff 的核心焦点。 - 明显该被引却未出现的：基于 network bootstrap / subsampling 的不确定性量化工作（如 Li 等 2020 的 subsampling for network community detection）；以及任何涉及统计-计算 gap 的近期文献（如 Banks 等 2016 的 computational hardness in SBM）。这值得研究者去查：作者是否刻意回避了计算不可达区域，只关注了统计阈值以上的贝叶斯推断？

张力 未见明显对立引用。Mossel 等 (2014) 与 Abbe 等 (2016) 在精确恢复阈值上从必要与充分两侧逼近同一界限，最终收敛无矛盾；Banerjee (2016) 与 Mossel 等在稠密情形的 contiguity 条件上结论一致。

二、最核心、最简单的例子 / 数学问题

第一步：符号、模型、可观测数据交代清楚

  • 符号：
  • \(n\)：图的顶点数 / 样本量（维数）。
  • \(K\)：社区数，本文固定 \(K=2\)。
  • \(\theta\)：潜在社区分配参数，\(\theta \in \Theta_n = \{0, 1\}^n\)，其中 \(\theta_i = 0\) 表示顶点 \(i\) 属于社区 0，\(\theta_i = 1\) 属于社区 1。
  • \(S_n(\theta) = \{i : \theta_i = 1\}\)：社区 1 的顶点集合，其大小 \(|S_n(\theta)|\) 未知且不等规模。
  • \(p_n, q_n\)：边概率参数，\(p_n\) 为同社区内顶点连边概率，\(q_n\) 为跨社区顶点连边概率，满足 \(p_n > q_n\)。
  • \(X\)：可观测的随机图，取值于无向图空间 \(\mathcal{X}_n\)，\(X_{ij} \in \{0, 1\}\) 表示顶点 \(i\) 与 \(j\) 之间是否有边。
  • \(\Pi_n\)：参数空间 \(\Theta_n\) 上的先验分布。
  • \(P_{n,\theta}\)：给定 \(\theta\) 时图 \(X\) 的分布（即 SBM 的数据生成分布）。
  • \(\rho_n(p_n, q_n)\)：点态检验功效，定义为 \(\rho_n = 1 - 2 P_{n,\theta_0}(X_{ij} = 1 | \theta_i = \theta_j) - 2 P_{n,\theta_0}(X_{ij} = 0 | \theta_i \neq \theta_j)\)，用于衡量区分同社区与跨社区边的信息量。
  • \(d_n\)：与 \(\rho_n\) 相关的量，本文定义为 \(d_n = n \rho_n^2 / 2\)，表征样本量与信号强度的乘积。
  • \(\alpha\)：频率置信水平（目标覆盖概率）。

  • \(\gamma\)：贝叶斯可信水平（后验质量阈值）。

  • 模型（数据生成机制）： 稀疏两社区 SBM：给定 \(\theta \in \{0,1\}^n\) 与 \(p_n, q_n \in (0,1)\)，边 \(X_{ij}\)（\(1 \leq i < j \leq n\)）独立生成，

    \[P_{n,\theta}(X_{ij} = 1) = \begin{cases} p_n, & \text{if } \theta_i = \theta_j \\ q_n, & \text{if } \theta_i \neq \theta_j \end{cases}\]
    稀疏性假设要求 \(p_n, q_n = O(\log n / n)\)（Chernoff-Hellinger 阶段）或 \(O(1/n)\)（常数平均度阶段）。\(p_n, q_n\) 视为已知或可估，\(\theta\) 是要估的离散参数。

  • 可观测数据： 研究者实际观测到的是图的邻接矩阵 \(X\)（即所有 \(X_{ij}\) 的取值）。不可观测的是潜在社区分配 \(\theta_0\)（真实分配）与社区大小 \(|S_n(\theta_0)|\)。只能靠假设（如 \(p_n > q_n\) 的对角占优性）与图的结构去识别 \(\theta_0\)。

第二步：最小内核——支撑整篇论文的最简特例

最简特例：等规模两社区（\(|S_n(\theta)| = n/2\)）下的后验集中与置信集构造。

在此特例下，参数空间退化为 \(\Theta_n^{\text{sym}} = \{\theta \in \{0,1\}^n : |S_n(\theta)| = n/2\}\)，即 planted bi-section model。此时，核心数学困难在于：证明后验分布 \(\Pi_n(\theta \in \cdot | X)\) 在观测到来自 \(\theta_0\) 的图时，集中在 \(\theta_0\) 的一个小邻域内（几乎精确恢复），并由此构造置信集。

  • 要证的命题（退化形式）：在等规模特例下，若 \(p_n = a \log n / n, q_n = b \log n / n\) 且 \((\sqrt{a} - \sqrt{b})^2 > 1\)，则存在常数 \(C > 0\) 使得
    \[\Pi_n\left( \frac{1}{n} \sum_{i=1}^n 1(\theta_i \neq \theta_{0,i}) > \epsilon \mid X \right) \leq e^{-C n \rho_n^2}\]
    对任意 \(\epsilon > 0\) 依概率趋于 0。这即后验几乎精确恢复。
  • 证明怎么走（核心思路）：
  • 点态检验：构造一个基于边概率差异的检验，区分 \(\theta_0\) 与任意替代分配 \(\theta_1\)。检验功效 \(\rho_n(p_n, q_n)\) 衡量了区分能力。
  • KL 邻域与先验质量：利用 Schwartz 条件，证明先验 \(\Pi_n\) 在 \(\theta_0\) 的 KL 邻域内分配足够质量（即 \(\Pi_n(B_{n,\theta_0}) \geq e^{-n d_n}\)，其中 \(d_n = n \rho_n^2 / 2\)）。
  • 后验集中不等式：结合点态检验与先验质量，通过 Bayes 因子分解，得到后验集中在 \(\theta_0\) 邻域的指数衰减界。
  • 为什么成立：在等规模下，社区大小固定为 \(n/2\)，先验在 KL 邻域的质量下界 \(e^{-n d_n}\) 中的指数项 \(d_n\) 与点态检验的 \(\rho_n^2\) 精确匹配，使得后验集中率恰好达到精确恢复阈值 \((\sqrt{a} - \sqrt{b})^2 > 1\) 所要求的信号强度。

本文的一般情形（不等规模）只是此特例的"加壳"：当 \(|S_n(\theta)|\) 未知时，参数空间扩大为 \(\{0,1\}^n\)，先验需对社区大小分配质量（如均匀先验或 Beta-Binomial 先验）。此时，先验在 KL 邻域的质量下界中多出一个与社区大小相关的因子（如 \(|S_n(\theta_0)|\) 的选择概率），导致后验集中不等式需额外控制社区大小的先验质量衰减。本文的核心技术跳跃在于：证明即使社区大小未知，只要先验对极端大小（如 \(|S_n| = 0\) 或 \(n\)）分配足够小的质量，且 sparsity bound 满足与等规模相同的条件，后验集中率仍可保持。

三、这篇论文做了什么

三句话 ①研究了稀疏不等规模两社区 SBM 中社区分配的后验集中与频率置信集构造问题； ②核心工具是基于点态检验功效的后验集中不等式与可信-置信水平转化定理； ③主要结论是：在与等规模 sharp bounds 相当的稀疏界限下实现后验几乎精确恢复，且发现可信水平与置信水平之间不存在比例性，存在临界图大小使得所需可信水平从近 1 急降至近 0，此时只需包含少数高后验概率分配（如 MAP）即可覆盖，并论证了 MCMC 早停的可行性。

关键设定与假设 在第二节最小记号的基础上补全： - 假设 1（稀疏性与分离性）：\(p_n, q_n\) 满足 \(p_n > q_n\) 且 \(p_n, q_n = O(\log n / n)\)（Chernoff-Hellinger 阶段），或更稀疏的 \(O(1/n)\) 阶段。具体要求为：存在常数 \(C > 0\) 使得 \(n \rho_n^2(p_n, q_n) \geq C \log n\)（几乎精确恢复条件），这与等规模下的 \((\sqrt{a} - \sqrt{b})^2 > 1\) 相当。 - 假设 2（先验对极端社区大小的控制）：先验 \(\Pi_n\) 在 \(\Theta_n\) 上满足 \(\Pi_n(\theta : |S_n(\theta)| = 0 \text{ or } n) \leq e^{-c n}\) 对某 \(c > 0\)。统计含义：防止先验将大量质量分配给“所有顶点同社区”的退化分配，这些分配与 Erdős-Rényi 图不可区分，会破坏后验集中。 - 假设 3（先验质量下界）：对真实分配 \(\theta_0\)，先验在其 KL 邻域内满足 \(\Pi_n(B_{n,\theta_0}(\epsilon)) \geq e^{-K n \rho_n^2}\) 对某 \(K > 0\) 与 \(\epsilon > 0\)。统计含义：Schwartz 型条件，保证先验在真实参数附近有足够支撑。 - 与已有文献的对比：相比 van Waaij & Kleijn (2021) 的等规模设定，本文放宽了 \(|S_n(\theta)| = n/2\) 的约束，允许任意 \(|S_n(\theta)| \in (0, n)\)；相比 Mossel 等 (2016) 的频率精确恢复阈值，本文的稀疏界限在形式上等价，但通过贝叶斯后验集中不等式给出，且覆盖了非渐近有限 \(n\)。

主要结果 - 定理 1（后验集中不等式，对应论文 Theorem 3.1 / 3.2 形式）： - 陈述：在假设 1-3 下，对真实分配 \(\theta_0\) 与任意 \(\epsilon > 0\)，

\[P_{n,\theta_0}\left( \Pi_n\left( \frac{1}{n} \sum_{i=1}^n 1(\theta_i \neq \theta_{0,i}) > \epsilon \mid X \right) > e^{-M n \rho_n^2} \right) \leq e^{-L n \rho_n^2}\]
对某 \(M, L > 0\)。即后验在误分类比例超过 \(\epsilon\) 的分配上的质量，以指数率衰减。 - 直觉：点态检验能以功效 \(\rho_n\) 区分 \(\theta_0\) 与任何偏离 \(\epsilon\) 的替代分配；先验在 \(\theta_0\) KL 邻域有足够质量；Bayes 因子将这两者结合，使得后验远离 \(\theta_0\) 的分配的质量被检验的指数衰减压倒。 - 必要条件：\(n \rho_n^2 \geq C \log n\)（即信号强度足够支撑几乎精确恢复）；先验对退化分配的质量控制（假设 2）。 - 解决的技术难点：不等规模下，参数空间大小为 \(2^n\)（而非等规模的 \(\binom{n}{n/2}\)），先验质量下界需额外控制社区大小的组合数因子；作者通过将先验质量分解为“社区大小选择概率 × 给定大小下的分配概率”，并利用假设 2 剔除极端大小，使得指数界中的常数与等规模一致。

  • 定理 2（置信集构造，对应论文 Theorem 4.1 形式）：
  • 陈述：给定频率置信水平 \(\alpha \in (0,1)\)，定义置信集 \(C_n(X, \alpha) = \{\theta : \Pi_n(\theta | X) \geq \gamma_n(\alpha)\}\)，其中 \(\gamma_n(\alpha)\) 为可信水平阈值。则存在临界图大小 \(n^*(\alpha, p_n, q_n)\) 使得：
    • 当 \(n < n^*\) 时，\(\gamma_n(\alpha) \approx 1\)（需包含几乎全部后验支撑）；
    • 当 \(n > n^*\) 时，\(\gamma_n(\alpha) \approx 0\)（只需包含少数高后验概率分配，如 MAP）。 且 \(P_{n,\theta_0}(\theta_0 \in C_n(X, \alpha)) \geq 1 - \alpha\) 对所有 \(n\)。
  • 直觉：后验集中不等式保证 \(\theta_0\) 的后验质量随 \(n\) 指数增长；当 \(n\) 超过临界值时，\(\theta_0\) 的后验质量已远超 \(\alpha\) 所需的覆盖阈值，因此只需取后验质量大于某个极小 \(\gamma_n\) 的分配即可覆盖 \(\theta_0\)。
  • 必要条件：后验集中不等式成立（即定理 1 的条件）；\(\gamma_n(\alpha)\) 的选取需满足 \(\Pi_n(\theta_0 | X) \geq \gamma_n\) 依概率至少 \(1-\alpha\)。
  • 解决的技术难点：可信-置信水平的非比例性；作者发现 \(\gamma_n(\alpha)\) 不是 \(\alpha\) 的线性函数，而是随 \(n\) 发生相变：在小 \(n\) 下后验分散，需高可信水平覆盖；在大 \(n\) 下后验集中，极低可信水平即可覆盖。

证明路线与技术技巧 - 整体路线（5 步）： 1. 定义点态检验：对每对分配 \(\theta_0, \theta_1\)，构造基于边概率差异的检验 \(\phi_{n,\theta_0,\theta_1}\)，计算其功效 \(\rho_n\) 与第一类 / 第二类错误概率。 2. 构造检验序列覆盖参数空间：将点态检验组合为覆盖整个参数空间 \(\Theta_n\) 的检验序列 \(\Phi_n\)，利用不等规模下的组合数控制（剔除极端大小）保证检验序列的总体错误概率可控。 3. 先验质量下界估计：证明先验 \(\Pi_n\) 在 \(\theta_0\) 的 KL 邻域 \(B_{n,\theta_0}\) 内的质量满足 \(\Pi_n(B_{n,\theta_0}) \geq e^{-K n \rho_n^2}\)，通过分解社区大小概率与分配概率实现。 4. 后验集中不等式推导：结合检验序列的指数衰减与先验质量下界，通过 Bayes 因子分解（\(\Pi_n(A|X) / \Pi_n(B_{n,\theta_0}|X) \leq \text{检验衰减} / \text{先验质量}\)），得到后验在远离 \(\theta_0\) 的集合上的质量上界。 5. 置信集构造与可信-置信转化：从后验集中不等式出发，计算使得 \(\Pi_n(\theta_0 | X) \geq \gamma_n\) 依概率至少 \(1-\alpha\) 的最小 \(\gamma_n\)；分析 \(\gamma_n\) 随 \(n\) 的变化，发现相变现象。

  • 关键跳跃点：
  • 引理：不等规模下的先验质量分解（对应论文 Lemma 3.1 附近）。难点在于：当 \(|S_n(\theta)|\) 未知时，先验质量 \(\Pi_n(B_{n,\theta_0})\) 包含社区大小选择概率 \(\Pi_n(|S_n| = |S_n(\theta_0)|)\) 与给定大小下的分配概率。作者通过假设 2 剔除极端大小，并利用 Beta-Binomial 或均匀先验的性质，证明社区大小选择概率的衰减率不超过 \(e^{-c n}\)，从而不破坏 KL 邻域的质量下界。

  • 引理：可信-置信水平的相变分析（对应论文 Section 4 的核心计算）。难点在于：\(\gamma_n(\alpha)\) 的选取需解方程 \(P_{n,\theta_0}(\Pi_n(\theta_0 | X) \geq \gamma_n) \geq 1-\alpha\)；作者利用后验集中不等式将 \(\Pi_n(\theta_0 | X)\) 的下界转化为 \(n \rho_n^2\) 的函数，发现当 \(n \rho_n^2\) 超过某临界值时，\(\gamma_n\) 从近 1 急降至近 0。

  • 技术技巧点名：

  • 点态检验：用于区分 \(\theta_0\) 与替代分配 \(\theta_1\)，基于边概率差异构造似然比检验，功效 \(\rho_n\) 为 Chernoff 距离的函数。
  • Bayes 因子分解：将后验质量比分解为先验质量比与似然比，结合检验衰减与先验质量下界控制后验集中。
  • KL 邻域与 Schwartz 条件：保证先验在真实参数附近有足够支撑，是后验集中的必要条件。
  • 组合数控制与极端大小剔除：通过假设 2 限制先验对退化分配的质量，避免 \(2^n\) 参数空间的组合爆炸破坏集中率。
  • 相变分析：通过解后验质量下界的方程，发现可信-置信水平的非比例性相变，类似于统计物理中的相变现象。

真实例子与应用 本文为纯理论 / 无实证例子。论文未包含任何真实数据分析或模拟实验；所有结果均为非渐近理论定理与不等式。作者在 Section 5 讨论了 MCMC 早停的计算可行性，但仅限于理论论证，未给出算法实现或数值验证。

🔎 结论是否比证明窄 - 泛泛 claim vs 严格证明：作者在 Abstract 与 Introduction 中 claim "posterior (almost-)exact recovery of the community structure under sparsity bounds comparable to well-known sharp bounds in the planted bi-section model"，但严格证明的定理 1 要求假设 1-3 全部满足，且 \(n \rho_n^2 \geq C \log n\) 中的常数 \(C\) 未显式给出与等规模 sharp bound \((\sqrt{a} - \sqrt{b})^2 > 1\) 的精确对应关系（仅在极限情形下相当）。研究者需核查定理 1 的常数 \(C\) 是否确实与等规模阈值一致。 - MCMC 早停的 claim：作者在 Section 5 论证 "a form of early stopping applies to MCMC sampling of the posterior, which would enable the computation of confidence sets at larger graph sizes"，但此论证基于后验集中在少数高概率分配的观察，未给出 MCMC 混合时间的严格分析或早停准则的正式定理。这是一个 conjecture 性质的 claim，而非严格证明。

四、开放问题（点到为止，扎根具体语句）

  1. MCMC 早停的严格混合时间分析：要证什么？在稀疏不等规模 SBM 下，MCMC 采样后验的混合时间是否随 \(n\) 多项式增长，且早停准则（当采样集中在少数高概率分配时终止）能否在多项式时间内输出满足置信覆盖的集合。扎根点：Section 5 的 "It is argued that for the proposed construction of confidence sets, a form of early stopping applies to MCMC sampling of the posterior"，此句为论证而非定理。

  2. 统计-计算 gap 区域内的置信集构造：要估什么？在 KS 阈值以下、Chernoff-Hellinger 阈值以上的稀疏区域（信息论可检测但多项式时间不可检测），是否存在任何多项式时间算法可构造满足频率覆盖的置信集，还是覆盖本身需要指数时间。扎根点：Introduction 提到的 "sparsity bounds comparable to well-known sharp bounds in the planted bi-section model" 仅覆盖了统计阈值以上区域，未讨论计算不可达区域。

  3. 后验集中不等式的常数紧性：要证什么？定理 1 中的常数 \(C\)（使得 \(n \rho_n^2 \geq C \log n\)）是否与等规模下的 \((\sqrt{a} - \sqrt{b})^2 > 1\) 精确匹配，还是存在因不等规模导致的常数损失。扎根点：Theorem 3.1 的陈述中常数 \(C\) 未显式化，Abstract claim "comparable to well-known sharp bounds" 需数值验证。

  4. \(K \geq 3\) 社区的推广：要估什么？在社区数 \(K \geq 3\) 且社区大小未知时，后验集中不等式与置信集构造是否仍成立，可信-置信水平的相变现象是否消失或改变形态。扎根点：Introduction 明确限制 "with two communities of unknown sizes"，未讨论多社区推广的可行性。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论