这篇论文揭示了自适应查询在社区恢复中的理论优势，做图算法或网络分析的学者值得关注，看完会对数据获取策略的设计有新的启发。
本文研究在随机块模型（SBM）中，当学习者只能通过有限次数的噪声查询访问网络数据时，如何实现精确的社区恢复。查询会以固定概率揭示节点的真实邻居，但不会返回非邻居，且总查询次数有限。作者分析了仅依赖查询的模型，以及结合单个子采样图的混合模型。在仅查询模型中，均匀非自适应查询的基准性能由Abbe-Bandeira-Hall精确恢复阈值决定，但自适应策略可以用更少的查询（n+o(n)）超越该基准。在混合模型中，自适应查询可以针对少量不确定节点，实现亚线性查询的精确恢复，而均匀查询则无法改进子采样图的结果。这表明自适应数据获取能严格改善精确恢复的信息论极限。
Query-Limited Community Recovery in Stochastic Block Models
We study exact community recovery in the two-community stochastic block model on $n$ vertices under limited and noisy access to network data. The learner may query a noisy neighborhood oracle that reveals each true neighbor of a queried vertex independently with fixed probability and never returns non-neighbors, subject to a finite query budget. We consider both oracle-only access and a combined model where the learner also observes a single subsampled copy of the underlying graph. For oracle-only access, balanced uniform querying gives a sharp non-adaptive benchmark: when each vertex is queried the same integer number of times, the observations reduce to an SBM with attenuated edge probabilities and the Abbe-Bandeira-Hall exact-recovery threshold applies. We show that this benchmark is not adaptively optimal: a two-stage adaptive strategy succeeds with $n+o(n)$ queries in a regime where balanced uniform querying requires $m n$ queries for some $m>1$. With an additional subsampled graph, we prove a sublinear-query adaptivity gap: balanced data-independent uniform querying with a sublinear budget does not improve over the subsampled graph alone, whereas adaptive querying can target a small set of uncertain vertices and achieve exact recovery. Thus adaptive data acquisition can strictly improve the information-theoretic limits of exact recovery.