# Bridging Arbitrary and Tree Metrics via Differentiable Gromov Hyperbolicity

arXiv: https://arxiv.org/abs/2505.21073 · HTML: https://mlsanity.com/paper/2505.21073/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 45 references that are in the map.
- First posted on arXiv 27 May 2025.

## Builds on (most cited first, 16 of 16)

- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Poincar'e Embeddings for Learning Hierarchical Representations](https://mlsanity.com/paper/1705.08039/) (2017)
- [Hyperbolic Graph Convolutional Neural Networks](https://mlsanity.com/paper/1910.12933/) (2019)
- [Soft-DTW: a Differentiable Loss Function for Time-Series](https://mlsanity.com/paper/1703.01541/) (2017)
- [Representation Tradeoffs for Hyperbolic Embeddings](https://mlsanity.com/paper/1804.03329/) (2018)
- [Poincar'e GloVe: Hyperbolic Word Embeddings](https://mlsanity.com/paper/1810.06546/) (2018)
- [On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learning](https://mlsanity.com/paper/1704.00805/) (2017)
- [Fully Hyperbolic Neural Networks](https://mlsanity.com/paper/2105.14686/) (2021)
- [Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature](https://mlsanity.com/paper/2211.15779/) (2022)
- [Hierarchical Clustering: Objective Functions and Algorithms](https://mlsanity.com/paper/1704.02147/) (2017)
- [Tree! I am no Tree! I am a Low Dimensional Hyperbolic Embedding](https://mlsanity.com/paper/2005.03847/) (2020)
- [DataSP: A Differential All-to-All Shortest Path Algorithm for Learning Costs and Predicting Paths with Context](https://mlsanity.com/paper/2405.04923/) (2024)
- [Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space](https://mlsanity.com/paper/2502.17130/) (2025)
- [Shedding Light on Problems with Hyperbolic Graph Learning](https://mlsanity.com/paper/2411.06688/) (2024)
- [If it ain't broke, don't fix it: Sparse metric repair](https://mlsanity.com/paper/1710.10655/) (2017)
- [Enumeration of Far-Apart Pairs by Decreasing Distance for Faster Hyperbolicity Computation](https://mlsanity.com/paper/2104.12523/) (2021)

## Abstract (arXiv)

Trees and the associated shortest-path tree metrics provide a powerful framework for representing hierarchical and combinatorial structures in data. Given an arbitrary metric space, its deviation from a tree metric can be quantified by Gromov's δ-hyperbolicity. Nonetheless, designing algorithms that bridge an arbitrary metric to its closest tree metric is still a vivid subject of interest, as most common approaches are either heuristical and lack guarantees, or perform moderately well. In this work, we introduce a novel differentiable optimization framework, coined DeltaZero, that solves this problem. Our method leverages a smooth surrogate for Gromov's δ-hyperbolicity which enables a gradient-based optimization, with a tractable complexity. The corresponding optimization procedure is derived from a problem with better worst case guarantees than existing bounds, and is justified statistically. Experiments on synthetic and real-world datasets demonstrate that our method consistently achieves state-of-the-art distortion.