非自适应查询下学习随机超图，突破传统下界。
Non-adaptive Learning of Random Hypergraphs with Queries
- 将超边检测问题转化为群组测试，利用随机性设计高效算法
- 在随机k-一致超图下，首次实现非自适应学习的最优查询复杂度
- 适合对组合优化与信息检索感兴趣的科研人员
我们研究通过一次性批量查询（非自适应）学习隐藏超图 $G=(V,E)$ 的问题。在超边检测模型中，每次查询形如：'集合 $S\⊆ V$ 是否包含至少一个完整超边？' 已知在任意超图情况下，非自适应学习所需查询数下界为 $Ω(\min\{m^2\log n, n^2\})$，即使在 $2$-均匀（即普通图）情形也成立。最近，Li 等人通过假设图来自 Erdős-Rényi 模型，突破了该下界。本文将此结果推广至随机 $k$-均匀超图场景。为此，我们建立了一个新等价关系：学习单个超边等价于标准群组测试问题。该结果本身也可能具有独立研究价值。
原文摘要 · Abstract (English)
We study the problem of learning a hidden hypergraph $G=(V,E)$ by making a single batch of queries (non-adaptively). We consider the hyperedge detection model, in which every query must be of the form: ``Does this set $S\subseteq V$ contain at least one full hyperedge?'' In this model, it is known that there is no algorithm that allows to non-adaptively learn arbitrary hypergraphs by making fewer than $Ω(\min\{m^2\log n, n^2\})$ even when the hypergraph is constrained to be $2$-uniform (i.e. the hypergraph is simply a graph). Recently, Li et al. overcame this lower bound in the setting in which $G$ is a graph by assuming that the graph learned is sampled from an Erdős-Rényi model. We generalize the result of Li et al. to the setting of random $k$-uniform hypergraphs. To achieve this result, we leverage a novel equivalence between the problem of learning a single hyperedge and the standard group testing problem. This latter result may also be of independent interest.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。