arXiv:2606.02055cs.ITcs.LG2026-06

在有限查询下,自适应策略能更高效地恢复网络社区结构。

Query-Limited Community Recovery in Stochastic Block Models

  • 通过自适应查询策略,动态选择关键节点提升信息获取效率。
  • 自适应方法仅需约 n 次查询即可实现精确恢复,而均匀查询需超 mn 次。
  • 适用于数据受限场景下的社区发现,尤其适合资源敏感应用。

我们研究在两社区随机块模型(SBM)中,面对有限且噪声干扰的网络数据访问时的精确社区恢复问题。学习者可调用一个有噪邻域查询接口:对任意查询顶点,其真实邻居以固定概率被返回,非邻居永不返回,且总查询次数受预算限制。考虑仅使用查询接口和结合一个子采样图的联合模型。对于仅查询接口的情况,均衡均匀查询构成非自适应最优基准:当每顶点被查询相同整数次时,观测等价于边概率衰减的SBM,此时适用Abbe-Bandeira-Hall的精确恢复阈值。但我们证明该基准并非自适应最优:一种两阶段自适应策略在某个区域仅需n+o(n)次查询即可成功,而均衡查询需mn次(m>1)。在加入子采样图的情况下,证明了次线性查询下的自适应优势:均衡无脑查询在次线性预算下无法超越子采样图单独的效果,而自适应查询可聚焦不确定顶点集,实现精确恢复。因此,自适应数据采集可严格突破精确恢复的信息论极限。

原文摘要 · Abstract (English)

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.

社区发现自适应查询随机块模型

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。