植入对植入测试中的精确低度阈值

# 植入体对植入体测试的尖锐低度阈值

来源：https://arxiv.org/html/2606.05266  
Daniel Gutiérrez Espinoza, Fiona Skerman, Alexander S. Wein  
加州大学戴维斯分校数学系  

###### 摘要  
我们首次为植入体对植入体场景建立了低次多项式测试的尖锐阈值，目标是以趋于零的误差判定观测数据由两种结构化植入机制中的哪一种生成。我们为植入子矩阵模型和植入稠密子图模型中的计数社区问题给出了匹配的低度上界和下界。所得测试阈值（精确到尖锐常数）与已知的低度恢复阈值一致。相比之下，弱测试任务（目标优于随机猜测）并不存在尖锐阈值，而是存在一个平滑过渡，我们识别出了这一过渡。为证明我们的结果，我们发展了一个基于低度恢复中潜变量展开的植入体对植入体测试框架，并采用新方法来识别和修剪非信号贡献。††脚注：邮箱：{fiona.skerman, daniel.gutierrez_espinoza}@math.uu.se；[email protected]。

##### *关键词*：植入体对植入体测试，复杂测试，尖锐阈值，低度方法，强测试，弱测试，植入子矩阵，植入稠密子图。

## 1 引言

高维推断中一个普遍现象是存在尖锐的计算相位转变：当信号强度穿过一个临界阈值时，推断任务从计算上“容易”变为“困难”。一个著名例子是随机块模型（SBM）中的*Kesten–Stigum（KS）阈值*[decelle-2, AS-general]。当*信噪比（SNR）*（模型参数的某个函数）位于所谓的KS阈值之上时，从图中推断（具有非平凡精度）社区结构是“容易的”，因为已知有多项式时间算法。反之，当SNR低于KS阈值时，没有已知的多项式时间算法，多种启发式方法表明推断在本质上“困难”，至少对某类算法如此[decelle-2, HS-bayesian, spectral-planting, sohn2025sharp, DHSS-recovery]。类似的计算阈值出现在许多其他统计模型中，且通常可能不同于*统计阈值*（在此阈值之上，某种无运行时间约束的算法能够成功）。精确确定这些尖锐计算阈值在不同模型中的具体位置，一直是持续关注的热点。所谓*尖锐*，是指所需运行时间在自然SNR参数穿过阈值时发生突变，而我们的目标是精确识别阈值（不仅仅是常数因子）。确立尖锐阈值结果需要两部分：阈值之上的正面算法结果和阈值之下的困难性结果。虽然我们聚焦于尖锐阈值，但并非所有计算阈值都是尖锐的：某些问题，如植入团[alon-clique]和张量PCA（见[smooth-tensor]），表现出SNR与运行时间之间的平滑折衷。除非统计阈值与计算阈值恰好重合，我们目前还没有工具在复杂度理论上确凿证明统计问题的困难性（由于这些问题的*平均情况*性质）。因此，常见的方法是证明某类已知算法必定失败。两种常见框架是：（i）与统计物理相关的方法，围绕分析*置信传播（BP）*或*近似消息传递（AMP）*算法（见[phys-survey]）；（ii）基于低次多项式的算法（见[LD-notes, wein2025computational]）。其他平均情况复杂性框架也存在，但我们聚焦于那些在建立*尖锐*阈值方面有成功记录的框架。对于SBM的KS阈值，尖锐相位转变首先通过物理方法预测[decelle-1, decelle-2]，随后在低次多项式模型中得到证实[HS-bayesian, spectral-planting, sohn2025sharp, DHSS-recovery]。更复杂的是，我们可能研究几个不同的目标。*检测*是在两个不同分布之间进行假设检验的任务，通常一个是包含某种隐藏结构的“植入”分布，另一个是不包含该结构的“零假设”分布。对于SBM，植入模型是具有社区的随机图，零假设模型通常是具有相同平均边密度的Erdős–Rényi图。*恢复*是找到隐藏结构或将其估计到所需精度的任务。检测和恢复的计算阈值不一定相同。例如，在SBM中，对于社区数量固定的标准变体，这两个阈值（更准确地说，“强”检测（高概率）和“弱”恢复（非平凡））一致，但当社区数随n增长时，检测变得比恢复容易（见[sbm-many, sbm-many-2]）。本工作的重点是植入体对植入体测试：区分两个复杂的分布，每个分布具有不同种类的植入结构。现有针对此类问题的结果[rush2023easier, coloring-clique, fourier-geo, carpentier2025low]过于粗糙，无法建立我们这里感兴趣的尖锐阈值。随之而来两个问题：植入体对植入体测试问题能否表现出尖锐阈值（精确到主导常数），是否存在一个系统框架来证明它们？统计物理方法似乎不直接适用于此场景，因为它们主要针对恢复。这使得低度框架（同时处理测试和恢复）成为自然候选。我们对两个问题的回答都是肯定的。我们发展了一个用于植入体对植入体测试的低度证书框架，并利用它在此场景中建立了第一个尖锐低度阈值。对于观测在给定潜在结构下条件独立的植入模型，该框架将低度下界简化为一个线性证书问题，该问题由信息性子图支撑。

### 1.1 主要贡献

我们为“计数社区”建立了尖锐低度阈值：即测试数据中是否包含 \(\ell\) 还是 \(\ell'\) 个植入结构的问题，分别针对植入子矩阵模型（PSM）和植入稠密子图模型（PDS）。这里 \(\ell \neq \ell'\) 是任意固定的正整数。该测试问题由 [rush2023easier] 引入，其中阈值确定到多对数因子。我们的结果通过发展一个通用的植入体对植入体测试低度证书框架，将图像锐化到尖锐主导常数级别。对于此问题，我们的框架在所述的稀疏区域中精确给出了低度强测试阈值的主导常数，并识别了弱测试尺度。这里，*强*测试指测试误差概率趋于零，而*弱*测试指达到与随机猜测有界差距的检验功效。植入体对植入体测试与恢复之间的联系先前在 [rush2023easier] 中建立，其中证明了单社区植入子矩阵模型中的近似恢复可推出 1 社区和 2 社区植入模型之间的强测试（相差一个因子 2，我们预期可改进为 1）。这留下了问题：测试是否可能比恢复更容易，以及测试阈值是否依赖于对 \((\ell, \ell')\)。例如，区分 1 个和 100 个植入社区可能比区分 99 个和 100 个更容易。我们的结果表明，在尖锐低度阈值层面并非如此：在两种模型中，对于每一对不同的固定 \(\ell, \ell'\)，强测试阈值相同，且与相应的尖锐低度恢复阈值 [sohn2025sharp] 一致。简而言之，\(\ell\)-植入子矩阵模型生成如下。参数 \(\rho\) 控制植入顶点的稀疏性，\(\lambda\) 控制信号强度。对于每个索引 \(i \in [n]\)，独立分配标签 \(c \in [\ell]\) 的概率为 \(\rho/\ell\)，否则分配标签 0。在这些标签条件下，对于所有 \(1 \le i \le j \le n\)，如果 \(i\) 和 \(j\) 属于同一个非零社区，则 \(Y_{ij} \sim N(\ell\lambda, 1)\)，否则 \(Y_{ij} \sim N(0,1)\)，且 \(Y_{ji} = Y_{ij}\)。我们的低度下界通过控制度 \(D\) 优势来证明：
\[
\mathsf{Adv}_{\le D}(\mathbb{P}, \mathbb{Q}) := \sup_{\deg(f) \le D} \frac{\mathbb{E}_{\mathbb{P}}[f(Y)]}{\sqrt{\mathbb{E}_{\mathbb{Q}}[f(Y)^2]}}. \tag{1.1}
\]
形如 \(\mathsf{Adv}_{\le D}(\mathbb{P}, \mathbb{Q}) = O(1)\) 的界排除了度 \(D\) 的强分离，而 \(\mathsf{Adv}_{\le D}(\mathbb{P}, \mathbb{Q}) = 1+o(1)\) 的界排除了度 \(D\) 的弱分离；参见引理 2.2。匹配的上界由显式的低度分离多项式给出。

#### 1.1.1 结果

我们分别给出 PSM 和 PDS 的强测试和弱测试定理。为便于阅读，此处陈述 PSM 的结果；相应的 PDS 陈述见定理 4.2 和 4.8。另见图 1，它描绘了 PSM 的相图。全程中 \(n \to \infty\)，\(\ell, \ell'\) 固定，其余参数可依赖于 \(n\)。

##### 植入子矩阵模型的强测试和弱测试结果

###### 定理 1.1（强测试：PSM）。给定参数 \(n, \ell, \ell', \rho, \lambda\)，其中 \(\ell, \ell'\) 是固定的不同正整数，\(\rho \in (0,1)\)，\(\lambda > 0\)，定义 \(\mathbb{Q} := \mathbb{P}_{\mathrm{PSM}}(n, \ell, \rho, \lambda)\) 和 \(\mathbb{P} := \mathbb{P}_{\mathrm{PSM}}(n, \ell', \rho, \lambda)\)。对于任意常数 \(\varepsilon > 0\)，存在常数 \(C_0 \equiv C_0(\ell, \ell', \varepsilon) > 0\) 使得以下成立。

1. (i) *（下界）*。如果
\[
\lambda \le (1-\varepsilon)\Big(\rho\sqrt{en}\Big)^{-1}, \qquad D \le \lambda^{-2}/C_0, \qquad \rho = o(1)
\]
则 \(\mathsf{Adv}_{\le D}(\mathbb{P}, \mathbb{Q}) = O(1)\)。

2. (ii) *（上界）*。如果
\[
\lambda \ge (1+\varepsilon)\Big(\rho\sqrt{en}\Big)^{-1}, \quad n\rho = \omega(\log^7 n), \qquad \rho = o(\log^{-7} n)
\]
则存在一个次数至多为 \(C_0 \log n\) 的多项式 \(f\) 强分离 \(\mathbb{P}\) 和 \(\mathbb{Q}\)。下界也适用于所有 \(D \le \lambda^{-2}/C_0\)。根据标准低度启发式（其中度 \(D\) 被解释为运行时间 \(n^{\widetilde{O}(D)}\) 的代理 [HS-bayesian]），这指出了尺度 \(D \asymp \lambda^{-2}\) 作为相关的次临界度尺度。上述上界中的多项式基于对平衡单环图（BUG）的计数；定义见方程 (3.8)，图 2 为示意图。

###### 定理 1.2（弱测试：PSM）。给定参数 \(n, \ell, \ell', \rho, \lambda\)，其中 \(\ell, \ell'\) 是固定的不同正整数，\(\rho \in (0,1)\)，\(\lambda > 0\)，定义 \(\mathbb{Q} := \mathbb{P}_{\mathrm{PSM}}(n, \ell, \rho, \lambda)\) 和 \(\mathbb{P} := \mathbb{P}_{\mathrm{PSM}}(n, \ell', \rho, \lambda)\)。存在常数 \(C_0 \equiv C_0(\ell, \ell') > 0\) 使得以下成立。

1. (i) *（下界）*。如果
\[
\lambda = o\left((\rho\sqrt{n})^{-1}\right), \qquad D \le \lambda^{-2}/C_0, \qquad \rho = o(1),
\]
则 \(\mathsf{Adv}_{\le D}(\mathbb{P}, \mathbb{Q}) = 1+o(1)\)。

2. (ii) *（上界）*。如果
\[
\lambda = \Omega\left((\rho\sqrt{n})^{-1}\right), \qquad n\rho = \omega(1),
\]
则次数为 1 的多项式 \(f(Y) = \sum_i Y_{ii}\) 弱分离 \(\mathbb{P}\) 和 \(\mathbb{Q}\)。

我们的结果表明，在所需信号强度 \(\lambda\) 方面，弱植入体对植入体测试严格比强植入体对植入体测试更容易：强测试具有尖锐阈值 \((\rho\sqrt{en})^{-1}\)，而弱测试对于任何小常数乘以 \((\rho\sqrt{n})^{-1}\) 都是可能的。强测试阈值与相应单社区模型的尖锐低度恢复阈值 \(\lambda_{\mathrm{rec},1}\) [submatrix-message-passing, sohn2025sharp] 一致。非正式地，
\[
\lambda_{\ell \,\mathrm{vs}\, \ell'}^{\mathrm{weak}} < \lambda_{\ell \,\mathrm{vs}\, \ell'}^{\mathrm{strong}} = \lambda_{\mathrm{rec},1}^{\mathrm{weak}} = \lambda_{\mathrm{rec},1}^{\mathrm{strong}}.
\]
参见图 1 中 PSM 设置下的相图。

图 1：植入子矩阵模型中区分 \(\ell\) 和 \(\ell'\) 社区的示意图相图。弱测试在 \(\lambda = o((\rho\sqrt{n})^{-1})\) 时低度困难，而强测试具有尖锐阈值 \((\rho\sqrt{en})^{-1}\)，与 [sohn2025sharp] 的尖锐低度恢复阈值一致。粗体陈述为本文所证。

图 2：BUG（平衡单环图）。\(\mathcal{U}_3\) 中非同构图示。

#### 1.1.2 框架与证明思路

在通常的植入体对零假设设置中，零假设分布是乘积测度，因此低度优势中的分母可以通过在观测变量上直接进行正交展开来控制。这在进行植入体对植入体测试时失效：两个假设都包含潜在结构，而参考律在观测上不是乘积的。我们分三步解决这个非乘积结构。首先，我们过渡到一个扩展空间，包含潜在变量和底层独立噪声。这受到 [sohn2025sharp] 中用于尖锐低度恢复的潜变量正交化方法的启发。在高层次上，贝塞尔不等式将下界问题简化为构造一个满足某些线性方程 \(u^\top M = c^\top\) 的证书 \(u\)，这给出了界 \(\mathsf{Adv}_{\le D}^2(\mathbb{P}, \mathbb{Q}) \le \|u\|_2^2\)。其次，对于条件独立的植入模型（如这里的情况），我们观察到矩在连通分量上分解。分量一致。