快速解码方法让大规模随机图学习更高效
A Fast Binary Splitting Approach for Non-Adaptive Learning of Erdős--Rényi Graphs
- 用二分分裂法设计测试方案，提升非自适应图学习效率
- 仅需$O(\bar{k}\log n)$次测试即可高概率恢复边集
- 解码时间降至$O(\bar{k}^{1+δ}\log n)$，适合大图应用
研究通过节点子集的群组查询来学习未知图的问题，每次查询返回所选节点间是否存在至少一条边。在非自适应设置下，学习任意含 $n$ 个节点、$k$ 条边的图是困难的，即使允许小误差概率，也需 $Ω\big(\min\{k^2\log n,\,n^2\}\big)$ 次测试。本文聚焦于非自适应条件下学习 Erdős--Rényi 图 $G\sim\mathrm{ER}(n,q)$，其期望边数为 $\bar{k}=q\binom{n}{2}$，目标是设计高效测试-解码方案，实现渐近零误差概率。已有工作（Li--Fresacher--Scarlett, NeurIPS 2019）虽达到最优测试量 $O(\bar{k}\log n)$，但解码时间高达 $Ω(n^2)$；其提出的亚线性时间算法则额外增加 $(\log \bar{k})(\log n)$ 因子。本文将近期用于非自适应群组测试的二分分裂方法扩展至 ER 图学习场景，证明可在 $O(\bar{k}\log n)$ 次测试下以高概率恢复边集，且解码时间仅为 $O(\bar{k}^{1+δ}\log n)$（对任意固定 $δ>0$）。
原文摘要 · Abstract (English)
We study the problem of learning an unknown graph via group queries on node subsets, where each query reports whether at least one edge is present among the queried nodes. In general, learning arbitrary graphs with $n$ nodes and $k$ edges is hard in the non-adaptive setting, requiring $Ω\big(\min\{k^2\log n,\,n^2\}\big)$ tests even when a small error probability is allowed. We focus on learning Erdős--Rényi (ER) graphs $G\sim\mathrm{ER}(n,q)$ in the non-adaptive setting, where the expected number of edges is $\bar{k}=q\binom{n}{2}$, and we aim to design an efficient testing--decoding scheme, namely, a non-adaptive test design together with a decoding algorithm, achieving asymptotically vanishing error probability. Prior work (Li--Fresacher--Scarlett, NeurIPS 2019) presents a testing--decoding scheme that attains an order-optimal number of tests $O(\bar{k}\log n)$ but incurs $Ω(n^2)$ decoding time, whereas their proposed sublinear-time algorithm incurs an extra $(\log \bar{k})(\log n)$ factor in the number of tests. We extend the binary splitting approach, recently developed for non-adaptive group testing, to the ER graph learning setting, and prove that the edge set can be recovered with high probability using $O(\bar{k}\log n)$ tests while attaining decoding time $O(\bar{k}^{1+δ}\log n)$ for any fixed $δ>0$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。