# Fitting trees to ℓ1-hyperbolic distances

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 38 references that are in the map.
- First posted on arXiv 2 Sep 2024.

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

- [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)
- [Learning Continuous Hierarchies in the Lorentz Model of Hyperbolic Geometry](https://mlsanity.com/paper/1806.03417/) (2018)
- [Representation Tradeoffs for Hyperbolic Embeddings](https://mlsanity.com/paper/1804.03329/) (2018)
- [From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clustering](https://mlsanity.com/paper/2010.00402/) (2020)
- [Tree! I am no Tree! I am a Low Dimensional Hyperbolic Embedding](https://mlsanity.com/paper/2005.03847/) (2020)
- [Computing the Gromov-Hausdorff Distance for Metric Trees](https://mlsanity.com/paper/1509.05751/) (2015)
- [Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor](https://mlsanity.com/paper/2110.02807/) (2021)

## Abstract (arXiv)

Building trees to represent or to fit distances is a critical component of phylogenetic analysis, metric embeddings, approximation algorithms, geometric graph neural nets, and the analysis of hierarchical data. Much of the previous algorithmic work, however, has focused on generic metric spaces (i.e., those with no a priori constraints). Leveraging several ideas from the mathematical analysis of hyperbolic geometry and geometric group theory, we study the tree fitting problem as finding the relation between the hyperbolicity (ultrametricity) vector and the error of tree (ultrametric) embedding. That is, we define a vector of hyperbolicity (ultrametric) values over all triples of points and compare the ℓp norms of this vector with the ℓq norm of the distortion of the best tree fit to the distances. This formulation allows us to define the average hyperbolicity (ultrametricity) in terms of a normalized ℓ1 norm of the hyperbolicity vector. Furthermore, we can interpret the classical tree fitting result of Gromov as a p = q = ∞ result. We present an algorithm HCCRootedTreeFit such that the ℓ1 error of the output embedding is analytically bounded in terms of the ℓ1 norm of the hyperbolicity vector (i.e., p = q = 1) and that this result is tight. Furthermore, this algorithm has significantly different theoretical and empirical performance as compared to Gromov's result and related algorithms. Finally, we show using HCCRootedTreeFit and related tree fitting algorithms, that supposedly standard data sets for hierarchical data analysis and geometric graph neural networks have radically different tree fits than those of synthetic, truly tree-like data sets, suggesting that a much more refined analysis of these standard data sets is called for.