Testing properties of trees in graphical models with covariance queries

技术摘要：利用协方差查询测试图形模型中树的性质

1. 问题陈述

本文探讨了在高维图形模型中测试全局结构性质的问题，其中底层图结构为树。在标准设定下，从数据中学习完整的图结构需要计算样本协方差矩阵，对于 $n$ 个变量，其计算成本为 $O(n^2)$。在超高维情形下，这一成本是难以承受的，甚至存储协方差矩阵也是不可行的。

为此，作者采用了 Lugosi 等人 [11] 引入的协方差查询模型。在该模型中，统计学家可以自适应地查询总体协方差矩阵 $\Sigma$ 的特定条目。对于高斯图形模型（以及相关的二元马尔可夫随机场和线性结构方程模型），逆协方差矩阵 $\Sigma^{-1}$ 编码了图结构：零条目对应条件独立性。

本文特别关注树状结构模型。这些模型的一个关键性质是，任意两个节点之间的相关性等于连接它们的唯一路径上各边相关性的乘积。通过对平方相关系数取负对数，这种乘积结构转化为加性树度量 $d(u,v)$。因此，问题被抽象为：作者不再直接处理分布，而是处理一个未知的树 $T$，该树配备了一个未知的树度量 $d$，且仅能通过一个预言机（oracle）访问，该预言机返回查询节点对之间的精确距离 $d(u,v)$。

主要目标并非重建整棵树（这可能仍然代价高昂），而是以次二次方（sub-quadratic）数量的查询来测试特定的全局结构性质（例如直径、最大度、叶子节点数量、典型距离）。

2. 方法论

所提出的测试程序遵循基于随机采样的统一范式：

1. 采样：从树的 $n$ 个顶点中均匀随机采样一个小顶点子集 $X = \{X_1, \dots, X_N\}$。
2. 查询：根据具体性质的不同，查询采样顶点与所有其他顶点（或采样内部节点对）之间的距离。
3. 子树恢复：对于涉及局部结构（度、叶子）的性质，作者利用一个过程（引理 4.1）来恢复由采样节点 $X$ 张成的最小子树 $T_X$。这涉及识别满足 $d(x, x') = d(x, w) + d(w, x')$ 的顶点 $w$（其中 $x, x' \in X$）。这一步至关重要，因为它保留了中间顶点和度信息，而标准的系统发育重建通常会抑制度为 2 的节点。
4. 统计估计：全局性质是从采样数据或恢复的子树 $T_X$ 上计算的统计量中推断出来的。作者利用集中不等式（伯恩斯坦不等式、U 统计量的霍夫丁不等式）来界定误差概率。

本文区分了测试典型距离的两种情形：

• U 统计量方法：计算采样节点对之间的精确图距离，以估计平均路径长度。
• 路径相交方法：通过计算有多少个采样节点位于两个端点之间的路径上来估计路径长度，从而避免查询所有成对距离。

3. 主要贡献与结果

本文提供了针对四个基本性质的随机测试算法，建立了依赖于目标阈值和容差参数（$\delta, \epsilon$）的显式查询复杂度界限。

A. 测试直径 ($H_{diam}: \text{diam}(T) \ge D$)

• 方法：该测试基于长路径会与许多随机采样节点相交的事实。统计量计算任意两个采样节点之间的路径上包含的采样节点的最大数量。
• 结果：如果归一化后的计数超过阈值，则接受该测试。
• 复杂度：$\Theta\left( \left(\frac{n}{D\delta^2} \log \frac{n^2}{\epsilon}\right)^2 \right)$。
• 推论：如果 $D$ 与 $n$ 成线性比例，则复杂度关于 $n$ 是多项式对数的，显著低于二次方。

B. 测试最大度 ($H_{deg}: \text{maxdeg}(T) \ge \Delta$)

• 方法：高度顶点是稀有的，仅通过均匀采样难以检测。该方法重建由样本张成的子树 $T_X$。$T_X$ 中的最大度作为全局最大度的代理。
• 结果：如果重建子树中的最大度（经样本量归一化后）超过阈值，则接受该测试。
• 复杂度：$\Theta\left( \frac{n^2}{\Delta \delta^2} \log \frac{n}{\epsilon} \right)$。
• 比较：当 $\Delta \ge \sqrt{n}$ 时，该方法优于基于重建的测试（后者需要 $O(n\Delta \log n)$ 次查询）。对于所有 $\Delta$，度可以在 $O(n^{3/2} \log n)$ 次查询内被测试。

C. 测试叶子节点数量 ($H_{leaf}: |L(T)| \ge \Lambda$)

• 方法：与度测试类似，算法重建 $T_X$。$T_X$ 的叶子节点是 $T$ 的叶子节点的候选者。一个细化步骤通过检查是否有任何未采样节点比 $T_X$ 中任何其他节点更接近该候选叶子，来验证 $T_X$ 中的候选叶子是否确实是 $T$ 的叶子。
• 复杂度：$\Theta\left( \frac{n^2}{\Lambda \delta^2} \log \frac{1}{\epsilon} \right)$。
• 推论：如果树具有线性数量的叶子（$\Lambda \propto n$），则查询复杂度变为关于 $n$ 的线性。

D. 测试典型距离 ($H_{typ}: \ell_{typ}(T) \ge \ell$)

• 方法：使用两个互补的估计量。一个使用精确距离（U 统计量），另一个使用路径相交。选择取决于阈值 $\ell$ 和直径。
• 复杂度：界限较为复杂，涉及诸如 $\left(\frac{n \cdot \text{diam}(T)}{\delta \ell}\right)^2$ 的项以及估计直径本身的项。
• 推论：当 $\text{diam}(T)/\ell = o(\sqrt{n})$ 或 $\text{diam}(T)/\ell^2 = o(1)$ 时，实现了次二次方复杂度。

E. 从测试到估计
本文表明，这些测试程序可以通过迭代测试嵌套假设转换为估计算法（推论 2.6–2.9）。这使得能够以相同的查询复杂度阶数构建直径、最大度、叶子节点数量和典型距离的置信区间。

4. 意义与主张

本文主张，虽然在有限查询下高维树的精确重建可能代价高昂或不可能，但全局结构性质可以被高效地测试。

• 效率：主要贡献在于证明了次二次方查询复杂度足以测试这些性质，而完整重建通常需要根据树的度需要 $O(n^2)$ 或更高的复杂度。
• 适用性：结果适用于高斯图形模型、二元马尔可夫随机场以及树上的线性结构方程模型，利用了基于路径的依赖关系表示。
• 理论边界：这项工作阐明了树的哪些方面可以从少量距离查询中推断，而哪些方面必然需要完整重建。它确立了诸如“树是否包含大型枢纽？”或“树是否包含长路径？”之类的问题，可以用远少于完全模型恢复所需的查询次数来有效回答。

作者指出，他们的结果涉及精确预言机设定（总体层面）下的查询复杂度。他们承认，将这些结果扩展到具有噪声协方差查询的有限样本设定，需要对边长和直径做出额外假设，这留待未来工作完成。本文并未提出具体的实验应用，但为超高维情形下的此类测试提供了理论框架。