A Fast Binary Splitting Approach for Non-Adaptive Learning of Erd\H{o}s--Rényi Graphs

技术摘要：一种用于非自适应学习 Erdős–Rényi 图的高速二分分裂方法

问题陈述
本文研究了通过非自适应分组查询（non-adaptive group queries）学习一个未知的无向图 $G = (V, E)$ 的问题，其中包含 $n$ 个顶点。在该设定下，一次查询由一个顶点子集 $S \subseteq V$ 组成，其结果是一个比特位，表示在 $S$ 内部是否存在至少一条边。目标是设计一个测试-解码方案，在最小化查询次数的同时，确保高效地重建边集 $E$。

虽然在非自适应设定下学习具有 $k$ 条边的任意图需要 $\Omega(\min\{k^2 \log n, n^2\})$ 次测试，但作者专注于 Erdős–Rényi (ER) 模型 $G \sim \text{ER}(n, q)$，其中边的出现是相互独立的，概率为 $q$。预期的边数为 $k = q \binom{n}{2}$。具体的挑战在于实现 $O(k \log n)$ 数量级的最优测试次数，同时获得亚线性（或接近线性于 $k$）的解码时间。先前的工作虽然实现了 $O(k \log n)$ 次测试，但需要 $\Omega(n^2)$ 的解码时间；或者在以增加 $\log k \cdot \log n$ 倍测试次数为代价的情况下，实现了亚线性解码时间。

方法论
作者提出了一种将二分分裂方法（binary splitting approach，近期被开发用于非自适应分组测试）扩展到图学习领域的测试-解码方案。该方法分为两个阶段：基准算法和利用划分与置换的改进算法。

1. 二分分裂层级结构：

   • 算法将顶点组织成跨越层级 $\ell = \lceil \log_2 \sqrt{k} \rceil, \dots, \log_2 n$ 的二分块层级。
   • 在每个层级，顶点集被划分为 $g = 2^\ell$ 个块。算法通过随机测试进行，其中块被分配到不同的测试中。
   • 测试设计： 该设计使用了 $O(\sqrt{k})$ 次重复，每次重复包含 $O(\sqrt{k})$ 个测试。这种 $\sqrt{k} \times \sqrt{k}$ 的结构确保了非缺陷对（即内部没有边的块对）很可能被放在一个负测试中，同时保持正测试的概率远离 1，以防止“淹没”非缺陷对。
   • 解码： 解码器从粗层级向细层级推进。它维护一个“可能缺陷” (PD) 块对的集合。如果一个对没有被负测试排除，它就会在下一层级被细化为子对。该过程依赖于这样一个性质：非缺陷对会被以高概率消除，从而使 PD 集合的大小保持在可控范围内（建模为一个亚临界分支过程）。

2. 解决解码瓶颈（划分与置换）：

   • 基准二分分裂方法会导致 $O(k^{1.5} \log n)$ 的解码时间，因为解码器必须为 $O(k)$ 个候选对检查 $O(\sqrt{k})$ 个测试。
   • 为了改进这一点，作者将顶点集 $V$ 划分为 $m = k^{(1-\gamma)/2}$ 个平衡子集 $S_1, \dots, S_m$。
   • 问题被分解为由诱导子图 $G_{ij} = G[S_i \cup S_j]$ 定义的子问题。每个子图的预期边数为 $O(k^\gamma)$，显著小于 $k$。
   • 置换放大（Permutation Amplification）： 一个关键难点是确保这些子图内的块是“有利的”（即在递归的基础层级不包含内部边）。作者引入了一个置换放大步骤：他们从两两独立族中采样 $c$ 个独立的随机置换。对于每个子图，他们将这些置换应用于顶点标签。
   • 这确保了以高概率，至少有一个置换能产生一种块结构，使得没有任何块包含内部边。这使得二分分裂解码器可以应用于规模更小的子问题，从而降低单对检查的成本。

主要贡献与结果

1. 基准方案（定理 1）：

   • 作者首先建立了一个直接在全图上使用二分分裂方法的方案。
   • 测试次数： $O(k \log n)$，达到了阶数最优。
   • 解码时间： $O(k^{1.5} \log n)$（或者根据稀疏参数 $\theta$ 为 $O(k^{1.5} \log^2 k \log n)$）。
   • 这改进了先前在相同测试复杂度下需要 $\Omega(n^2)$ 解码时间的做法。

2. 改进方案（定理 2）：

   • 通过整合划分与置换放大，作者进一步降低了解码时间。
   • 测试次数： 保持为 $O(k \log n)$。
   • 解码时间： 对于任何固定的 $\delta > 0$，为 $O(k^{1+\delta} \log n)$。
   • 解码时间中的隐藏常数取决于 $\delta$。
   • 该方案保证了渐近趋于零的错误概率（当 $n \to \infty$ 时，$P_e \to 0$）。

意义与主张
本文声称在非自适应学习 Erdős–Rényi 图的测试数量和解码时间方面，实现了“（近乎）最佳的双重目标”。具体而言：

• 它匹配了信息论最优的测试数量缩放比例 $O(k \log n)$。
• 它将解码复杂度从 $n$ 的二次方（或 $k^{1.5}$）显著降低到接近 $k$ 的线性水平（$k^{1+\delta}$）。
• 作者指出，虽然二分分裂的概念与标准分组测试中的概念相似，但图学习设定引入了独特的挑战，例如：负测试仅能排除非边对（而非单个顶点），且块内的内部边会导致包含该块的所有测试都变为正测试，从而无法提供关于非边的任何信息。所提出的划分和置换技术是专门为缓解这些问题而设计的。

这项工作被视为组合推断领域的一项理论进展，重点关注非自适应设定下查询复杂度与计算复杂度之间的权衡。作者最后提出了未来的研究方向，例如将解码时间降低至 $O(k \log n)$、改进测试常数、将该方法扩展到随机超图以及考虑噪声环境。