Research map / Learning theory and algorithms / Prediction and decision losses

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space

ICML 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Tree ensemble optimization · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes HS-DTE, a Delaunay-style constructive hyperbolic tree embedding that places children via minimal-angle-maximization on the hypersphere, and HypFPE, a GPU-compatible floating point expansion arithmetic that adds precision for hyperbolic distances.

Problem

Constructive hyperbolic tree embeddings need well-separated points on a hypersphere (a hard Tammes-type problem) and high precision near the Poincaré ball boundary, but the existing high-precision fix (multiple precision arithmetic) is incompatible with GPUs and deep learning.

Approach

Generalize Sarkar's combinatorial construction by choosing hyperspherical points via a minimal angle maximization objective optimized with projected gradient descent, and replace multiple-precision arithmetic with ulp-nonoverlapping floating point expansions implemented as tensor operations in PyTorch.

Key results

• On complete 3/5/7-ary trees in 10 dimensions, HS-DTE achieves the lowest worst-case distortion (1.07/1.09/1.12) with MAP 1.00, versus 1.14-1.31 for the Hadamard and precomputed-points constructions.
• On phylogenetic trees with float64, HS-DTE obtains D_wc of 9.42 (mosses) and 2.03 (weevils) versus 122 and 34.3 for the precomputed-points construction.
• With HypFPE (417-bit precision, 2 float64 terms), HypFPE + HS-DTE reaches D_wc of 1.06 on mosses and 1.04 on weevils, the best across the trees.

Measured effects reported in the paper

Surprising findings

• Hyperspherical energy objectives can yield a large mean pairwise angle with a small minimum angle, which leads to high distortion; MAM avoids this.
• The h-MDS method achieves the lowest average distortion on m-ary trees but collapses subtrees, producing NaN worst-case distortion and unusable embeddings.

Limitations

• Float64 and FPE experiments are restricted to trees of modest path length; larger scaling factors require more precision (number of bits grows linearly with tau and path length).
• The tanh^-1 formulation showed larger numerical errors, so the cosh^-1 formulation is used in experiments.

Experimental setup

Datasets: complete m-ary trees (m=3,5,7) binary tree depth 8 mosses phylogenetic tree weevils phylogenetic tree carnivora phylogenetic tree lichen phylogenetic tree

Benchmarks: complete m-ary trees phylogenetic trees (mosses, weevils, carnivora, lichen)

Metrics: average relative distortion worst-case distortion mean average precision

Baselines: Poincaré embeddings hyperbolic entailment cones distortion optimization h-MDS Hadamard combinatorial construction precomputed-points combinatorial construction

Builds on: Sarkar's combinatorial construction Poincaré embeddings hyperbolic entailment cones h-MDS Delaunay tree embeddings

Closest papers by meaning

• Representation Tradeoffs for Hyperbolic Embeddings (ICML 2018 · similarity 0.91)
• Hyperbolic Embeddings of Supervised Models (NeurIPS 2024 · similarity 0.89)
• Weighted Embeddings for Low-Dimensional Graph Representation (AAAI 2025 · similarity 0.88)
• Learning Structured Representations with Hyperbolic Embeddings (NeurIPS 2024 · similarity 0.85)
• Residual Hyperbolic Graph Convolution Networks (AAAI 2024 · similarity 0.85)
• Hyperbolic Fine-Tuning for Large Language Models (NeurIPS 2025 · similarity 0.85)