Search papers, labs, and topics across Lattice.
This paper investigates compact reachability embeddings for hierarchical data representations, addressing the limitations of existing dual encoder approaches that struggle with deep hierarchies. The authors establish theoretical guarantees for embeddings whose dimensions are determined by structural graph parameters, proving that constant dimension embeddings can represent directed trees and providing a generalization for graphs with treewidth. Key findings include the demonstration that while general Directed Acyclic Graphs (DAGs) require larger dimensions, the proposed embeddings significantly reduce dimensionality in high recall scenarios on real-world datasets.
Constant dimension embeddings for directed trees challenge the notion that larger hierarchies always necessitate exponentially larger representations.
Computing geometric representations of data is a cornerstone of modern machine learning, typically achieved by training dual encoders which map queries and documents into a shared embedding space. Recent work of You et al. [NeurIPS '25] has extended this approach to hierarchical retrieval, where relevance is determined by the ancestor-descendant relationships in a Directed Acyclic Graph (DAG). While previous work has shown that valid embeddings exist when the number of descendants is small, these bounds degrade significantly for deep hierarchies, requiring dimensions as large as the total number of nodes. In this paper, we investigate compact reachability embeddings for more general graph classes and provide theoretical guarantees for representing hierarchies using embeddings whose dimension depends on structural graph parameters. We prove that for any directed tree, there exists a reachability embedding in constant dimension 3, independent of the tree's size or depth. We generalize this result to graphs characterized by treewidth $t$, constructing embeddings of dimension $O(t \log n)$, where $n$ is the number of nodes. Complementing these upper bounds, we provide matching or near-matching lower bounds, showing that dimension $惟(n)$ is necessary for general DAGs and $惟(t/\log(n/t))$ is required for graphs of treewidth $t$. We also obtain upper and lower bounds parameterized by the number of cross-edges in the DAG. We additionally show that our embeddings can be constructed on real world datasets, and that they give much smaller dimensions in high recall regimes compared to prior embeddings with theoretical guarantees.
