Technical Summary: Compact Geometric Representations of Hierarchies

Problem Statement

The paper addresses the challenge of computing geometric representations (embeddings) for hierarchical data retrieval. In modern machine learning, dense retrieval typically maps queries and documents into a shared embedding space where relevance is determined by the inner product of their vectors. While effective for flat retrieval, this approach faces challenges when relevance is defined by complex reasoning or hierarchical structures, such as Directed Acyclic Graphs (DAGs).

Specifically, the paper investigates reachability embeddings. Given a DAG $G=(V, E)$, the goal is to construct two mappings $a, b: V \to \mathbb{R}^d$ such that for any pair of nodes $u, v$, the inner product $\langle a(u), b(v) \rangle > 0$ if and only if $v$ is reachable from $u$ in $G$ (denoted $u \leadsto_G v$).

Previous work (You et al., 2025) established that if the number of descendants for any node is bounded by $s$, embeddings exist in dimension $O(s \log n)$. However, this bound degrades significantly for deep hierarchies (e.g., trees where $s \approx n$), potentially requiring dimensions proportional to the total number of nodes. The central question is whether compact embeddings exist whose dimension depends on structural graph parameters (like treewidth or cross-edges) rather than just the total node count or depth.

Methodology

The authors propose constructive algorithms for reachability embeddings that leverage specific graph parameters to achieve low dimensions. The methodology is divided into three main theoretical contributions:

1. Directed Trees and Forests

For rooted directed trees, the authors utilize the discovery and finishing times from a standard Depth-First Search (DFS).

• Mechanism: In a DFS tree, $v$ is a descendant of $u$ if and only if the interval $[d_v, f_v]$ is contained within $[d_u, f_u]$.
• Construction: They define vectors in $\mathbb{R}^3$ such that the inner product equals $(f_u - d_v)(d_v - d_u)$. This product is positive if and only if $d_u < d_v < f_u$, which corresponds exactly to the reachability condition.
• Result: This yields a constant dimension embedding ($d=3$) for any directed tree, independent of the tree's size or depth.

2. DAGs Parameterized by Cross-Edges

For general DAGs, the authors extend the forest embedding by accounting for "cross-edges" (edges in the DAG that are not part of a chosen spanning forest).

• Mechanism: They start with the 3-dimensional embedding for the spanning forest. For each cross-edge $(x_i, y_i)$, they introduce an additional coordinate.
• Construction: The new coordinate activates (with a large value $M$) if the query node can reach $x_i$ and the document node is reachable from $y_i$. A sufficiently large $M$ ensures that any path utilizing a cross-edge produces a positive inner product, while unreachable pairs do not.
• Result: The embedding dimension is $d = 3 + k$, where $k$ is the number of cross-edges.

3. DAGs Parameterized by Treewidth

For graphs with bounded treewidth $t$, the authors employ a recursive construction based on balanced vertex separators.

• Mechanism: Using the property that graphs with treewidth $t$ have separators of size $\le t+1$ that split the graph into components of size at most $2n/3$, they recursively embed subgraphs.
• Construction: The embedding consists of three parts:
  1. Recursive Coordinates: Embeddings for the sub-components.
  2. Separation Coordinates: Two coordinates that impose a large negative penalty on pairs $(u, v)$ where $u$ and $v$ lie in different components, preventing false positives across the split.
  3. Connection Coordinates: $|S|$ coordinates (where $S$ is the separator) that contribute a large positive term if a path exists through a separator vertex.
• Result: This yields an embedding dimension of $O(t \log n)$.

Key Contributions and Theoretical Bounds

The paper provides both upper bounds (constructive algorithms) and matching or near-matching lower bounds for the embedding dimension required for various graph classes.

Graph Class	Upper Bound (Dimension)	Lower Bound (Dimension)
General DAG	$O(n)$ (implied)	$\Omega(n)$ (Theorem 6.3)
Directed Trees	3 (Theorem 3.1)	3 (Lemma B.3)
Treewidth $t$	$O(t \log n)$ (Theorem 5.1)	$\Omega(t / \log(n/t))$ (Theorem 6.7)
Cross-Edges $k$	$3 + k$ (Theorem 4.1)	$\Omega(k^{1/4})$ and $\Omega(\frac{k \log(n^2/k)}{n \log n})$ (Theorems 6.8, 6.9)

Key Theoretical Insights:

• Tightness for Trees: The constant dimension of 3 is necessary even for small directed trees.
• Incomparability: The authors demonstrate via graph families that the bounds based on treewidth and cross-edges are incomparable; a graph can have constant treewidth but $\Omega(n)$ cross-edges, or vice versa.
• Lower Bounds: For general DAGs, linear dimension $\Omega(n)$ is necessary. For bounded treewidth, the dimension must scale with $t$, though the lower bound is slightly weaker than the upper bound due to logarithmic factors.

Experimental Results

The authors empirically validate their constructive approach on real-world hierarchical datasets: WordNet (82k nodes), Gene Ontology (24k nodes), and Cora (2.7k nodes).

• Method: They implemented the recursive separator-based construction (Section 5) and compared it against the "Handcrafted Embeddings" from You et al. (2025), which sum normalized ancestor vectors.
• Performance:
  • WordNet: The proposed method achieved 100% recall at dimension 152. The baseline required dimension 512 to reach 95% recall and only achieved ~51% recall at dimension 128.
  • Cora & Gene Ontology: Similar trends were observed, with the proposed method guaranteeing exact retrieval at dimensions significantly lower than those required by the baseline to achieve high recall.
• Significance: The experiments confirm that the theoretical $O(t \log n)$ bound holds in practice with modest constant factors, and that the constructive method outperforms prior heuristic approaches in high-recall regimes.

Significance and Claims

The paper claims to resolve the open question of whether fine-grained embeddings exist for hierarchical retrieval that are parameterized by structural graph properties rather than just the total number of nodes.

• Theoretical Impact: It establishes that for directed trees, reachability can be captured in constant dimension (3), a significant improvement over previous bounds that scaled with tree height. It generalizes this to graphs with bounded treewidth, offering a dimension of $O(t \log n)$.
• Practical Impact: The constructive nature of the embeddings allows for deterministic, fast generation without expensive training (unlike learned embeddings). The method guarantees 100% recall, whereas learned baselines often trade off exactness for lower dimensions.
• Limitations: The authors note that while the bounds are tight for trees, there is a gap between the upper and lower bounds for treewidth-parameterized graphs. Additionally, the method relies on finding good vertex separators, which is an approximation problem in practice.

The work provides a rigorous foundation for representing hierarchies in geometric spaces, demonstrating that structural parameters like treewidth and cross-edges are the correct lenses through which to view the complexity of reachability embeddings.