在现代机器学习中，计算数据的几何表示是一个重要的基础，通常通过训练双重编码器将查询和文档映射到共享的嵌入空间来实现。最近，You 等人 [NeurIPS '25] 扩展了这一方法至层次检索，其中相关性由有向无环图（DAG）中的祖先-后代关系决定。虽然先前的研究表明，当后代数量较少时，存在有效的嵌入，但对于深层次的层次结构，这些界限显著下降，所需的维度可能高达节点总数。
本文探讨了针对更一般图类的紧凑可达嵌入，并为使用嵌入表示层次结构提供了理论保证，其维度依赖于结构图参数。我们证明，对于任何有向树，存在一个常量维度为 3 的可达嵌入，与树的大小或深度无关。我们将这一结果推广到以树宽 $t$ 为特征的图，构造出维度为 $O(t \log n)$ 的嵌入，其中 $n$ 是节点数量。补充这些上界，我们提供了匹配或近似匹配的下界，表明对于一般 DAG，维度 $\Omega(n)$ 是必要的，而对于树宽为 $t$ 的图，需要 $\Omega(t/\log(n/t))$。
我们还获得了由 DAG 中交叉边数量参数化的上下界。进一步地，我们展示了我们的嵌入可以在真实世界数据集上构建，并且在高召回率的情况下，相较于之前具有理论保证的嵌入，维度要小得多。
博主点评： 本文为层次结构的几何表示提供了新的视角，尤其是在图的结构参数与嵌入维度之间的关系上。通过理论和实践的结合，研究者们为未来在高效检索和嵌入学习领域的发展奠定了坚实基础。