Bridging Arbitrary and Tree Metrics via Differentiable Gromov Hyperbolicity
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912603919351808 |
|---|---|
| author | Houedry, Pierre Courty, Nicolas Martin-Baillon, Florestan Chapel, Laetitia Vayer, Titouan |
| author_facet | Houedry, Pierre Courty, Nicolas Martin-Baillon, Florestan Chapel, Laetitia Vayer, Titouan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_21073 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bridging Arbitrary and Tree Metrics via Differentiable Gromov Hyperbolicity Houedry, Pierre Courty, Nicolas Martin-Baillon, Florestan Chapel, Laetitia Vayer, Titouan Machine Learning 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. |
| title | Bridging Arbitrary and Tree Metrics via Differentiable Gromov Hyperbolicity |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2505.21073 |