Query-Limited Community Recovery in Stochastic Block Models¶

会议: NeurIPS 2026
arXiv: 2606.02055
OpenReview: https://openreview.net/forum?id=p4JwxDfSjp
论文: https://arxiv.org/abs/2606.02055
领域: 其他
关键词: 随机块模型、社区发现、自适应查询、查询复杂度、精确恢复

一句话总结¶

本文研究了受限且带单边噪声的邻域预言机查询下的双社区随机块模型精确恢复问题，证明了自适应查询在纯预言机设置下可突破均匀采样的线性常数瓶颈，并在下采样图辅助设置下实现亚线性查询阶的严格自适应增益。

研究背景与动机¶

在复杂网络与机器学习中，从不完全或含噪的网络拓扑中恢复潜在社区结构是一个基石性理论问题。经典的双社区对称随机块模型（Stochastic Block Model, SBM）在稀疏对数平均度机制下，精确恢复（Exact Recovery）呈现出由 Abbe-Bandeira-Hall（ABH）准则刻画的锐利相变阈值 $(\sqrt{\alpha}-\sqrt{\beta})^2 > 2$。然而在生物网络挖掘、在线社交 API 探测、隐私受限数据采集等真实场景中，完整的网络邻接矩阵往往无法一次性全局观测，学习器通常只能通过高昂代价的局部探测接口（例如限制频次的 API 探测、问卷调查或湿实验测量）逐步获取节点的邻域信息，或者仅持有一张经过严重稀疏下采样的残缺网络。

现有关于关联图观测或多网络融合的研究主要集中于外生（Exogenous）固定概率模型，即观测机制在推断前已被完全静态确定，学习器无法主动介入数据采集流程。当测量预算有限时，传统的被动采样或均匀查询策略（即均匀地给每个节点分配固定次数的预言机探测）会导致信息量严重分散；特别是在网络中大部分节点的社区归属已被初步拓扑强力确定的情况下，均匀查询无法将有限资源集中在真正处于模糊分类决策边界的瓶颈节点上，从而受到经典均匀衰减阈值的刚性约束。

针对这种数据采集与统计推断脱节的困境，本文的核心切入点是将“自适应数据采集”显式纳入网络推断的最优性框架中，探究主动式局部邻域查询能否在信息论层面拓宽精确恢复的可达区域。核心 idea：通过构建两阶段留一法筛选与定向精炼架构，将邻域观测严格解耦为筛选集与纯净参考集，仅对初阶段置信裕量不足的亚线性模糊节点追加自适应预言机查询，从而在纯预言机设置下打破均匀采样的线性常数瓶颈，并在下采样图辅助下实现亚线性查询预算的严格自适应优势。

方法详解¶

整体框架¶

本文针对双社区平衡随机块模型 $G \sim \text{SBM}(n, \alpha\frac{\log n}{n}, \beta\frac{\log n}{n})$ 建立了带预算约束的单边带噪邻域预言机模型。预言机被查询某一节点 $v$ 时，以固定可靠性 $w \in (0, 1]$ 独立返回 $v$ 的真实邻居，绝不返回非邻居；总查询预算为 $k$。文章系统研究了两种观测模式：无先验图的纯预言机模式（Model 1）与持有一张独立边保留率为 $s$ 的下采样图的混合模式（Model 2）。针对均匀非自适应查询的不足，本文提出了两阶段自适应筛选策略（Algorithm 1）：第一阶段利用初始图或均匀查询构建留一法粗估计；第二阶段通过留一法统计量筛选出极少数模糊节点集合 $\mathcal{A}$，将剩余预算全部定向投入 $\mathcal{A}$ 进行似然比检验修正。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    In["输入：SBM网络及查询预算<br/>纯预言机/下采样图+噪声邻域预言机"] --> D1["留一法粗估计与不相交划分<br/>计算无偏标号并划分筛选集与参考集"]
    D1 --> D2["留一法似然边界筛选<br/>评估局部裕量识别模糊顶点子集"]
    D2 -->|裕量充足高置信| Conf["高置信集合保留初标号<br/>无须额外查询直接归类"]
    D2 -->|裕量不足置信低| D3["定向自适应局部精炼<br/>仅对模糊顶点查询并与纯净参考集对齐"]
    Conf --> Out["输出：全图精确社区恢复标号"]
    D3 --> Out

关键设计¶

1. 留一法粗估计与不相交邻域划分：消除自适应选择偏差与统计依赖

自适应采样的核心理论瓶颈在于：一旦学习器根据前期的观测挑选出疑似分类错误的难分类节点，这些节点与邻域的历史观测就已经被“选择事件”所条件化，无法再作为无偏证据参与后续的最终分类判决。为解耦选择机制与精炼判决，算法对全图每个节点 $v \in [n]$ 构建留一法局部视界。首先，在计算 $v$ 的参考标号 $\hat{\sigma}^{(-v)}$ 时，彻底剔除所有与 $v$ 关联的已有边观测，使得参考标号与 $v$ 自身的局部边生成过程条件独立。随后，算法将候选比较节点集合 $[n] \setminus \{v\}$ 严格划分为两个确定性不相交子集 $C_v$ 与 $B_v$。筛选集 $C_v$ 仅用于评估 $v$ 的分类置信度并判定 $v$ 是否需要进入二阶段重测集合 $\mathcal{A}$；而参考集 $B_v$ 在第一阶段不被任何用于筛选 $v$ 的事件所触碰，完整保留为第二阶段似然比精炼测试的“未受污染”证据池。

2. 留一法似然边界筛选机制：亚线性模糊集压缩与错误隔离

在第一阶段（无论是纯预言机的均匀预查询还是下采样图的拓扑观察），全图信号足以支持一个低汉明距离的全局粗标号，但不足以直接实现精确恢复。算法针对每个节点 $v$，在筛选集 $C_v$ 上计算其留一法局部似然裕量统计量： $$ \Lambda_v^{\text{loo}} := \sum_{u \in C_v} \hat{\sigma}u^{(-v)} A $$ 对于真实处于 }^{(0)$+1$ 社区的节点，其与 $C_v$ 中真实同社区节点的连接期望显著高于异社区；若其局部似然统计量 $|\Lambda_v^{\text{loo}}| > \delta \log n$，表明该节点具有极高统计裕量，以高于 $1 - n^{-1.02}$ 的概率已被粗标号正确归类，无需二次探测。而处于临界区 $|\Lambda_v^{\text{loo}}| \le \delta \log n$ 的节点被划入筛选集 $\mathcal{A}$。基于 Cramér 大偏差下尾界与 Chernoff 界分析，该机制严格保证了模糊集合 $\mathcal{A}$ 的规模以极大概率受限于亚线性阶 $|\mathcal{A}| \le n^{\gamma}$（例如 $\gamma = 0.88$ 或 $0.77$），同时以 $1 - o(1)$ 概率确保集合外部 $\mathcal{A}^c$ 的节点全部正确无误。

3. 保留参考集上的自适应定向局部精炼：跨越 ABH 临界阈值

进入第二阶段后，算法将所有剩余查询配额集中分配给规模仅为 $|\mathcal{A}|$ 的模糊节点。对每一个 $v \in \mathcal{A}$，预言机对其追加 $L$ 次独立邻域查询，每次查询以概率 $w$ 揭露其真实连边，从而将单边检出概率提升至 $a_L = 1 - (1-w)^L$。算法抛弃对筛选集 $C_v$ 的重复观测，仅提取 $v$ 到未受污染参考集 $B_v$ 的全新边观测向量 $(Y_u)_{u \in B_v}$，并执行局部的对数似然比检验： $$ \Lambda_v^{(2)} := \sum_{u \in B_v} \hat{\sigma}_u^{(-v)} \left[ Y_u \log\frac{p}{q} + (1-Y_u)\log\frac{1-a_L p}{1-a_L q} \right] $$ 根据 Bhattacharyya 误差指数分析，单节点分类失败概率被压制到 $n^{-\frac{\zeta}{2}(1-(1-w)^L)\Delta^2 + o(1)}$。只要调节固定整数 $L$ 使得有效信噪比指数 $\frac{\zeta}{2}(1-(1-w)^L)\Delta^2 > \gamma$，对集合 $\mathcal{A}$ 中所有元素应用联合界后，所有模糊节点被全数修复的错误率收敛至 $o(1)$，从而在总体仅追加 $L |\mathcal{A}| = o(n)$ 次查询的极低开销下完成全局精确恢复。

损失函数 / 训练策略¶

作为离散图结构上的统计假设检验问题，本文算法不涉及连续梯度下降，其决策规则与参数调优遵循最大后验与 Neyman-Pearson 似然比检验原理：

第一阶段全局定向与锚点约定（Anchor Convention）：为解决留一法最大似然估计 $\hat{\sigma}^{(-v)}$ 在全图上的全局符号翻转不确定性，设定确定性锚点子集 $D_n = \{1, \dots, \lceil n^{3/4} \rceil\}$。各节点统一通过 $\sum_{u \in D_n \setminus \{v\}} \hat{\sigma}_u^{(-v)} \ge 0$ 进行符号定向，由超几何反集中性保证全图符号一致性。
筛选阈值判定规则：对于选定的划分比例（如 $|C_v| \approx \frac{13}{20}n$），以对数标度阈值 $\tau \log n$ 作为分类器切分点，使得置信边界外部的误判率满足指数衰减阶 $I_{c_0}(-\tau) > 1$。
第二阶段符号判决：当 $\Lambda_v^{(2)} \ge 0$ 时赋予 $\hat{\sigma}_v = +1$，反之赋予 $-1$。最终全图输出由高置信直判标号与二阶段精炼标号直接拼接而成。

实验关键数据¶

主实验¶

本文通过严密的数学证明建立了纯预言机与下采样图混合设置下的精确恢复边界。以下表格对比了外生被动基线、均匀非自适应查询策略与本文提出的自适应策略在信息论极限与查询复杂度上的表现。

观测设置	数据采集机制 (Acquisition)	查询复杂度 (#Queries)	精确恢复必要且充分条件 / 状态	理论依据与结论
标准全图 SBM	外生被动观测 (Exogenous)	0（无需查询）	$\Delta^2 = (\sqrt{\alpha}-\sqrt{\beta})^2 > 2$	Abbe-Bandeira-Hall 经典阈值 [3]
关联/下采样网络	外生被动观测 (Exogenous)	0（固定保持率 $s$）	$s \Delta^2 > 2$	修正后衰减 SBM 阈值 [17, 28]
Model 1: 纯预言机	均匀非自适应 (Uniform)	$x \cdot n$ ($x \in \mathbb{N}^+$)	$\theta_{\text{unif}}(x, w)\Delta^2 > 2$	Proposition 1, 需满足 $x \ge x_\star > 1$
Model 1: 纯预言机	两阶段自适应 (Adaptive)	$n + o(n)$	突破均匀阈值，在 $x_0=1$ 时即成功	Theorem 3, Example 1 ($1.00n$ vs $1.087n$)
Model 1: 纯预言机	任意策略下界 (Any)	$o(n)$	必然失败 (Impossible w.h.p.)	Theorem 5, 证明了 $\Omega(n)$ 的必要性
Model 2: 下采样图+预言机	均匀非自适应 (Uniform)	$o(n)$ 亚线性	无法改善 $G_{\text{sub}}$ 阈值（$s\Delta^2 < 2$ 时失败）	Lemma 6, 均匀分配无法捕捉瓶颈节点
Model 2: 下采样图+预言机	两阶段自适应 (Adaptive)	$o(n)$ 亚线性	在 $s\Delta^2 < 2$ 的间隙区间成功精确恢复	Theorem 8, 确立严格亚线性自适应增益

消融实验¶

为了严格验证两阶段留一法筛选机制中各参数模块（筛选集比例、预算配置及精炼次数）对模糊集压制与恢复成功率的影响，下表呈现了文中代表性算例（Example 1 与 Lemma 7 构造）的参数消融与理论性能分解。

| 实验配置 / 算例场景 | 基础信噪比 $\Delta^2$ | 预言机参数 $w$ / 下采样 $s$ | 划分参数与筛选阈值 | 筛选集规模 $|\mathcal{A}|$ 上界 | 精炼次数 $L$ 与检验指数 | 最终精确恢复结果与查询消耗 | |---|---|---|---|---|---|---| | Model 1 均匀基线 | 9.0 ($\alpha=16, \beta=1$) | $w = 1 - 2^{-1/6} \approx 0.109$ | 全局均匀分配，无划分 | 无筛选（全量 $n$） | $m \ge 1.087$ 次/点 | 需 $1.087 n$ 次查询方可突破阈值 | | Model 1 自适应完整方案 | 9.0 ($\alpha=16, \beta=1$) | $w = 1 - 2^{-1/6}, x_0=1$ | $\zeta=0.5, \delta=0.32$ | $|\mathcal{A}| \le n^{0.88}$ (概率 $1-o(1)$) | $L=5$, 指数 $0.988 > 0.88$ | $k = n + 5n^{0.88} = n + o(n)$ 成功恢复 | | Model 1 欠精炼消融 ($L=4$) | 9.0 ($\alpha=16, \beta=1$) | $w = 1 - 2^{-1/6}, x_0=1$ | $\zeta=0.5, \delta=0.32$ | $|\mathcal{A}| \le n^{0.88}$ | $L=4$, 指数 $0.835 < 0.88$ | 联合界失效，无法保证全集合无差错修复 | | Model 2 均匀亚线性基线 | 9.0 ($\alpha=16, \beta=1$) | $w=0.5, s = 2(1-\epsilon)/9$ | 独立随机采样 $k=o(n)$ | 无针对性（大多难节点未测） | 平均每点 $o(1)$ 次查询 | 失败：$s\Delta^2 < 2$，后验无法收敛 | | Model 2 自适应完整方案 | 9.0 ($\alpha=16, \beta=1$) | $w=0.5, s \approx 0.222$ | $c_0=0.65, b_0=0.35, \tau=1.05$ | $|\mathcal{A}| \le n^{0.77}$ (概率 $1-o(1)$) | $L=1$, 指数 $0.7875 > 0.77$ | $k = \lceil n^{0.78} \rceil = o(n)$ 成功恢复 | | Model 2 无留一划分消融 | 9.0 ($\alpha=16, \beta=1$) | $w=0.5, s \approx 0.222$ | 共享同一组邻域边（无拆分） | 选择偏差导致方差放大 | 统计依赖导致条件独立性破坏 | 似然比估计出现严重偏差，无法证明收敛 |

关键发现¶

纯预言机设置下自适应改善线性常数：在 Model 1 中，任何成功算法的查询复杂度下界均为 $\Omega(n)$（Theorem 5）。自适应策略无法将总查询降至亚线性，但能将前序系数从均匀采样的 $x_\star > 1$（如 Example 1 中的 $1.087$）严格压缩至 $1 + o(1)$，实现了线性机制下的最佳常数优化。
关联侧信息激发本质性亚线性自适应裂隙（Adaptivity Gap）：在 Model 2 中，由于下采样图 $G_{\text{sub}}$ 提供了免查询的全局粗糙骨架，自适应算法能够以零查询代价锁定规模为 $O(n^{0.77})$ 的难分类子集，使得仅需 $k = \lceil n^{0.78} \rceil = o(n)$ 的亚线性预算即可实现全图翻盘；而均匀采样在此预算下对未测对点毫无改善，证明了主动采集相较于被动采样的本质阶数优势。
留一法拆分的必要性：消融分析表明，若直接复用第一阶段用于识别难节点的边去计算最终似然检验，选择效应会导致极端值的幸存偏差，破坏局部的大偏差率函数一致性；$B_v$ 与 $C_v$ 的解耦是消除相关性污染的关键。

亮点与洞察¶

将数据采集决策内生化：传统 SBM 研究通常把网络视为静态给定的随机矩阵，本文跳出了外生观测框架，将“到何处获取数据”转化为推断算法内部的一等公民，填补了网络主动推断与信息论恢复极限之间的理论空白。
留一法从证明技巧升维为算法架构：在以往随机矩阵与图聚类分析中，留一法（Leave-one-out）主要作为处理统计依赖的证明辅助手段；而在本文中，留一法被具象化为系统性的两阶段架构构件，通过把邻域划分为“检测集合”与“精炼集合”，优雅解决了自适应数据选择带来的内生依赖性问题。
普适性模块化思路：两阶段“粗略全局定位 + 局部精准排障”的设计范式具有很强的泛化潜力，可无缝迁移至超图社区恢复、带属性图主动探测、动态网络边追踪等广阔的高维推断领域。

局限与展望¶

模型设定假设的局限：理论推导严格建立在对称平衡双社区（两块大小均为 $n/2$）且平均度为对数阶 $\Theta(\log n)$ 的同质 SBM 上。对于非平衡块大小、多社区（$K > 2$）、更稀疏的有界度机制（Constant-degree regime，涉及非平凡的弱恢复/有界重叠相变），其筛选统计量的大偏差性质需要重新刻画。
常数与全相图的最优性未完全闭合：作者在文末承认，本文虽然给出了存在性证明与显式常数分离（如 Model 1 中的 $1.087$ 对比 $1.0$），但尚未给出自适应查询下全参数空间内的最优紧确常数边界，也未构建完整的自适应相图。
潜在改进方向：可进一步探索多轮自适应（Multi-stage / Fully Sequential Active Querying），通过动态维护后验熵来逐层筛选难节点，有望将二阶段的亚线性指数（如 $n^{0.77}$）进一步压缩逼近信息论极限。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次系统性形式化带噪局部预言机下的 SBM 精确恢复，并确立了线性和亚线性两类自适应分离。
实验充分度: ⭐⭐⭐⭐⭐ 纯理论论文，数学论证极其严密自洽，构造了精巧的留一法大偏差界与二阶矩逆命题。
写作质量: ⭐⭐⭐⭐⭐ 概念动机阐述清晰，技术困难与留一法解耦机制交代透彻，附录证明详尽完整。
价值: ⭐⭐⭐⭐⭐ 为主动图学习、受限网络探测与网络信息论推断提供了全新的理论基准与强有力的分析范式。