精选理由
这篇论文揭示了自适应查询在社区恢复中的理论优势，做图算法或网络分析的学者值得关注，看完会对数据获取策略的设计有新的启发。
本文研究在随机块模型（SBM）中，当学习者只能通过有限次数的噪声查询访问网络数据时，如何实现精确的社区恢复。查询会以固定概率揭示节点的真实邻居，但不会返回非邻居，且总查询次数有限。作者分析了仅依赖查询的模型，以及结合单个子采样图的混合模型。在仅查询模型中，均匀非自适应查询的基准性能由Abbe-Bandeira-Hall精确恢复阈值决定，但自适应策略可以用更少的查询（n+o(n)）超越该基准。在混合模型中，自适应查询可以针对少量不确定节点，实现亚线性查询的精确恢复，而均匀查询则无法改进子采样图的结果。这表明自适应数据获取能严格改善精确恢复的信息论极限。
AI 翻译 · 中文
本文研究在随机块模型（SBM）中，当学习者只能通过有限次数的噪声查询访问网络数据时，如何实现精确的社区恢复。查询会以固定概率揭示节点的真实邻居，但不会返回非邻居，且总查询次数有限。作者分析了仅依赖查询的模型，以及结合单个子采样图的混合模型。在仅查询模型中，均匀非自适应查询的基准性能由Abbe-Bandeira-Hall精确恢复阈值决定，但自适应策略可以用更少的查询（n+o(n)）超越该基准。在混合模型中，自适应查询可以针对少量不确定节点，实现亚线性查询的精确恢复，而均匀查询则无法改进子采样图的结果。这表明自适应数据获取能严格改善精确恢复的信息论极限。
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 neigh…