技术摘要：层次结构的紧凑几何表示

问题陈述

本文探讨了为层次化数据检索计算几何表示（嵌入）的挑战。在现代机器学习中，稠密检索通常将查询和文档映射到一个共享的嵌入空间，其中相关性由它们的向量内积决定。虽然这种方法对于扁平化检索非常有效，但在相关性由复杂推理或层次结构（如有向无环图，DAG）定义的场景下，会面临挑战。

具体而言，本文研究了可达性嵌入（reachability embeddings）。给定一个 DAG $G=(V, E)$，目标是构建两个映射 $a, b: V \to \mathbb{R}^d$，使得对于任何节点对 $(u, v)$，当且仅当 $v$ 在 $G$ 中从 $u$ 可达（记作 $u \leadsto_G v$）时，内积 $\langle a(u), b(v) \rangle > 0$。

前人的工作（You et al., 2025）指出，如果任何节点的后代数量被限制在 $s$ 以内，则存在维度为 $O(s \log n)$ 的嵌入。然而，对于深层层次结构（例如 $s \approx n$ 的树），该界限会显著恶化，可能需要与总节点数成比例的维度。核心问题在于，是否存在紧凑型嵌入，其维度取决于结构化图参数（如树宽或交叉边），而非仅仅取决于总节点数或深度。

方法论

作者提出了利用特定图参数来实现低维度的构造性算法。该方法分为三个主要的理论贡献：

1. 有向树与森林

对于有根有向树，作者利用标准深度优先搜索（DFS）中的发现时间（discovery time）和完成时间（finishing time）。

• 机制： 在 DFS 树中，$v$ 是 $u$ 的后代，当且仅当区间 $[d_v, f_v]$ 被包含在 $[d_u, f_u]$ 之内。
• 构造： 他们定义了 $\mathbb{R}^3$ 中的向量，使得内积等于 $(f_u - d_v)(d_v - d_u)$。该乘积为正，当且仅当 $d_u < d_v < f_u$，这恰好对应于可达性条件。
• 结果： 这为任何有向树提供了常数维度嵌入（$d=3$），与树的大小或深度无关。

2. 以交叉边为参数的 DAG

对于一般的 DAG，作者通过考虑“交叉边”（即 DAG 中不属于所选生成森林的边）来扩展森林嵌入。

• 机制： 他们首先建立生成森林的 3 维嵌入。对于每条交叉边 $(x_i, y_i)$，他们引入一个额外的坐标。
• 构造： 新坐标会在查询节点可以到达 $x_i$ 且文档节点可以从 $y_i$ 到达时激活（赋予一个大值 $M$）。足够大的 $M$ 确保了任何利用交叉边的路径都会产生正内积，而不可达的节点对则不会。
• 结果： 嵌入维度为 $d = 3 + k$，其中 $k$ 是交叉边的数量。

3. 以树宽为参数的 DAG

对于具有有界树宽 $t$ 的图，作者采用了基于平衡顶点分隔符（balanced vertex separators）的递归构造方法。

• 机制： 利用树宽为 $t$ 的图拥有大小 $\le t+1$ 的分隔符这一特性，这些分隔符将图分割成规模至多为 $2n/3$ 的组件，作者递归地嵌入子图。
• 构造： 嵌入由三部分组成：
  1. 递归坐标： 子组件的嵌入。
  2. 分离坐标： 两个坐标用于对位于不同组件中的对 $(u, v)$ 施加巨大的负惩罚，以防止跨越分割的假阳性。
  3. 连接坐标： $|S|$ 个坐标（其中 $S$ 是分隔符），如果存在通过分隔符顶点的路径，则贡献一个较大的正项。
• 结果： 这产生了维度为 $O(t \log n)$ 的嵌入。

核心贡献与理论界限

本文提供了针对各种图类所需的嵌入维度的上界（构造性算法）以及匹配或接近匹配的下界。

图类	上界 (维度)	下界 (维度)
一般 DAG	$O(n)$ (隐含)	$\Omega(n)$ (定理 6.3)
有向树	3 (定理 3.1)	3 (引理 B.3)
树宽 $t$	$O(t \log n)$ (定理 5.1)	$\Omega(t / \log(n/t))$ (定理 6.7)
交叉边 $k$	$3 + k$ (定理 4.1)	$\Omega(k^{1/4})$ 和 $\Omega(\frac{k \log(n^2/k)}{n \log n})$ (定理 6.8, 6.9)

关键理论洞察：

• 树的紧致性： 即使对于较小的有向树，3 的常数维度也是必要的。
• 不可比性： 作者通过图族证明了基于树宽和交叉边的界限是不可比的；一个图可以具有常数树宽但 $\Omega(n)$ 交叉边，反之亦然。
• 下界： 对于一般 DAG，线性维度 $\Omega(n)$ 是必要的。对于有界树宽，维度必须随 $t$ 缩放，尽管由于对数因子的存在，其下界略弱于上界。

实验结果

作者在真实世界的层次化数据集上验证了其构造方法：WordNet (82k 节点)、Gene Ontology (24k 节点) 和 Cora (2.7k 节点)。

• 方法： 他们实现了基于递归分隔符的构造方法（第 5 节），并将其与 You et al. (2025) 的“手工设计嵌入”（通过累加归一化祖先向量实现）进行对比。
• 性能：
  • WordNet： 所提方法在维度为 152 时实现了 100% 的召回率。基准方法在维度为 512 时才达到 95% 召回率，且在维度 128 时仅能达到约 51% 的召回率。
  • Cora 与 Gene Ontology： 观察到了类似的趋势，所提方法保证了在显著低于基准方法实现高召回率所需的维度下，即可实现精确检索。
• 意义： 实验证实，理论上的 $O(t \log n)$ 界限在实践中通过适度的常数因子依然成立，并且构造法在高召回率区间内优于先前的启发式方法。

重要性与主张

本文声称解决了关于是否存在能够以结构化图属性（而非仅仅是总节点数）进行参数化的精细化层次检索嵌入的开放性问题。

• 理论影响： 它确立了对于有向树，可达性可以在常数维度（3）中被捕捉，这相对于以往随树高缩放的界限有了显著改进。它将此推广到具有有界树宽的图，提供了 $O(t \log n)$ 的维度。
• 实际影响： 这种构造性嵌入允许进行确定性的、快速的生成，无需昂贵的训练（不同于学习到的嵌入）。该方法保证了 100% 的召回率，而学习到的基准方法通常在低维度时会牺牲精确性。
• 局限性： 作者指出，虽然对于树的界限是紧致的，但在树宽参数化图中，上界与下界之间仍存在差距。此外，该方法依赖于寻找良好的顶点分隔符，这在实践中是一个近似问题。

这项工作为在几何空间中表示层次结构提供了严谨的基础，证明了诸如树宽和交叉边之类的结构参数是观察可达性嵌入复杂性的正确视角。