Compact Geometric Representations of Hierarchies

Prashant Gokhale; Piotr Indyk; Yuhao Liu; Sandeep Silwal; Tony Chang Wang; Haike Xu

stat.MLJun 16, 2026

Compact Geometric Representations of Hierarchies

Authors: Prashant Gokhale, Piotr Indyk, Yuhao Liu, Sandeep Silwal, Tony Chang Wang, Haike Xu

Organizations: UW-Madison · MIT

Abstract

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.

Explore similar work

May 22, 2026cs.LG

Is Dimensionality a Barrier for Retrieval Models?

Why does the low dimensionality of representations, typically

d\approx 1000

, not prevent modern embedding-based retrieval models from scaling to billions, or even trillions, of data points? To answer this question, we study maximal-margin embeddings in the following retrieval model, classically studied in communication complexity [PS86] and more recently in embedding-based retrieval [WBNL26]. Let

A\in \{0,1\}^{N\times n}

be a matrix indicating whether each of

N

queries is relevant to each of

n

documents. We are interested in the largest margin

m>0,

denoted by

\mathsf{m}^{\mathsf{rd}}(d, A),

for which there exist unit norm embeddings of the queries and documents

\{U_j\}_{j = 1}^N, \{V_i\}_{i = 1}^n

with the following property.

\langle U_j, V_i\rangle \ge m

whenever

A_{ji} = 1

and

\langle U_j, V_i\rangle \le -m

otherwise. A large margin is a key proxy for representation quality: it controls both robustness to perturbations and compositional generalization across queries. Our main theorem establishes that the best possible margin without a restriction on the dimension,

\mathsf{m}^{\mathsf{rd}}(+\infty, A),

can be nearly achieved in dimension

d = O(\mathsf{m}^{\mathsf{rd}}(+\infty, A)^{-2}\log n)

which improves a theorem of [BDES02]. Together with a matching lower bound in Theorem 1.5, we conclude that when

A\in \{0,1\}^{\binom{n}{k}\times n}

is the matrix containing all possible

k

-sparse rows once, dimension

d = O(k\log (n/k))

is necessary and sufficient for the maximal possible margin

\mathsf{m}^{\mathsf{rd}}(+\infty, A) = Θ(k^{-1/2})

in this setting. This fully resolves the setup of [WBNL26]. We also give several constructions for large margins when

d = o(k\log (n/k)).

Finally, we empirically test the InfoNCE and sigmoid losses for producing large margin embeddings and demonstrate a clear advantage of the sigmoid loss.

Kiril Bangachev, Guy Bresler, Jonathan Kogan +1

Retrieval Layer Embedding Dimension Sparsity Barriers

Ask PDF

Apr 30, 2026cs.LG

Polaris: Coupled Orbital Polar Embeddings for Hierarchical Concept Learning

Real-world knowledge is often organized as hierarchies such as product taxonomies, medical ontologies, and label trees, yet learning hierarchical representations is challenging due to asymmetric structure and noisy semantics. We introduce Polaris, a polar hyperspherical embedding framework that separates semanticity from hierarchy using angular geometry and radius, enabling the learning of meaning and structure without interference. To map latent representation onto the sphere, we project it to the tangent space at the north pole, apply the exponential map, and learn unit-norm representations using spherical linear layers. Polaris then combines robust local constraints, global regularization that prevents geometric collapse, and uncertainty-aware asymmetric objectives that encourage directional containment. At inference time, Polaris uses structure-guided retrieval to efficiently narrow down candidate parents before final ranking. We evaluate Polaris on different settings of taxonomy expansion - spanning trees, multi-parent DAGs, and multimodal hierarchies, showing consistent improvements of up to ~19 points in top-K retrieval and up to ~60% reduction in mean rank over fourteen strong baselines.

Sahil Mishra, Srinitish Srinivasan, Sourish Dasgupta +1

Polarization Sphere Near-Earth Objects

Ask PDF

May 1, 2026cs.LG

Aitchison Embeddings for Learning Compositional Graph Representations

Representation learning is central to graph machine learning, powering tasks such as link prediction and node classification. However, most graph embeddings are hard to interpret, offering limited insight into how learned features relate to graph structure. Many networks naturally admit a role-mixture view, where nodes are best described as mixtures over latent archetypal factors. Motivated by this structure, we propose a compositional graph embedding framework grounded in Aitchison geometry, the canonical geometry for comparing mixtures. Nodes are represented as simplex-valued compositions and embedded via isometric log-ratio (ILR) coordinates, which preserve Aitchison distances while enabling unconstrained optimization in Euclidean space. This yields intrinsically interpretable embeddings whose geometry reflects relative trade-offs among archetypes and supports coherent behavior under component restriction; we consider both fixed and learnable ILR bases. Across node classification and link prediction, our method achieves competitive performance with strong baselines while providing explainability by construction rather than post-hoc. Finally, subcompositional coherence enables principled component restriction: removing and renormalizing subsets preserves a well-defined geometry, which we exploit via subcompositional dimensionality removal to probe how archetype groups influence representations and predictions.

Nikolaos Nakis, Chrysoula Kosma, Panagiotis Promponas +2

Graph Representation Learning Representation Learning

Ask PDF