# From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clustering

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

## Key facts

- Cited by 65 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Oct 2020.

## Built on by (most cited first, 30 of 65)

- [Hyperbolic Deep Neural Networks: A Survey](https://mlsanity.com/paper/2101.04562/) (2021)
- [Hyperbolic Deep Learning in Computer Vision: A Survey](https://mlsanity.com/paper/2305.06611/) (2023)
- [A Hyperbolic-to-Hyperbolic Graph Convolutional Network](https://mlsanity.com/paper/2104.06942/) (2021)
- [HoroPCA: Hyperbolic Dimensionality Reduction via Horospherical Projections](https://mlsanity.com/paper/2106.03306/) (2021)
- [HYperbolic Self-Paced Learning for Self-Supervised Skeleton-based Action Representations](https://mlsanity.com/paper/2303.06242/) (2023)
- [HIER: Metric Learning Beyond Class Labels via Hierarchical Regularization](https://mlsanity.com/paper/2212.14258/) (2022)
- [Poincar'e ResNet](https://mlsanity.com/paper/2303.14027/) (2023)
- [Geometry-aware Bayesian Optimization in Robotics using Riemannian Mat'ern Kernels](https://mlsanity.com/paper/2111.01460/) (2021)
- [Symmetric Spaces for Graph Embeddings: A Finsler-Riemannian Approach](https://mlsanity.com/paper/2106.04941/) (2021)
- [LSEnet: Lorentz Structural Entropy Neural Network for Deep Graph Clustering](https://mlsanity.com/paper/2405.11801/) (2024)
- [Contrastive Multi-view Hyperbolic Hierarchical Clustering](https://mlsanity.com/paper/2205.02618/) (2022)
- [Hyperbolic Diffusion Embedding and Distance for Hierarchical Representation Learning](https://mlsanity.com/paper/2305.18962/) (2023)
- [Hyperbolic Active Learning for Semantic Segmentation under Domain Shift](https://mlsanity.com/paper/2306.11180/) (2023)
- [Neural Distance Embeddings for Biological Sequences](https://mlsanity.com/paper/2109.09740/) (2021)
- [Generalization Error Bound for Hyperbolic Ordinal Embedding](https://mlsanity.com/paper/2105.10475/) (2021)
- [Small Transformers Compute Universal Metric Embeddings](https://mlsanity.com/paper/2209.06788/) (2022)
- [Supervised Tree-Wasserstein Distance](https://mlsanity.com/paper/2101.11520/) (2021)
- [Bringing motion taxonomies to continuous domains via GPLVM on hyperbolic manifolds](https://mlsanity.com/paper/2210.01672/) (2022)
- [GeoPhy: Differentiable Phylogenetic Inference via Geometric Gradients of Tree Topologies](https://mlsanity.com/paper/2307.03675/) (2023)
- [Hyperbolic Random Forests](https://mlsanity.com/paper/2308.13279/) (2023)
- [Fast hyperboloid decision tree algorithms](https://mlsanity.com/paper/2310.13841/) (2023)
- [Switch Spaces: Learning Product Spaces with Sparse Gating](https://mlsanity.com/paper/2102.08688/) (2021)
- [Hyperbolic vs Euclidean Embeddings in Few-Shot Learning: Two Sides of the Same Coin](https://mlsanity.com/paper/2309.10013/) (2023)
- [Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space](https://mlsanity.com/paper/2502.17130/) (2025)
- [Tree-Wasserstein Distance for High Dimensional Data with a Latent Feature Hierarchy](https://mlsanity.com/paper/2410.21107/) (2024)
- [AMCAD: Adaptive Mixed-Curvature Representation based Advertisement Retrieval System](https://mlsanity.com/paper/2203.14683/) (2022)
- [Hyperbolic Geometry in Computer Vision: A Survey](https://mlsanity.com/paper/2304.10764/) (2023)
- [SINCERE: Sequential Interaction Networks representation learning on Co-Evolving RiEmannian manifolds](https://mlsanity.com/paper/2305.03883/) (2023)
- [Improving Heterogeneous Graph Learning with Weighted Mixed-Curvature Product Manifold](https://mlsanity.com/paper/2307.04514/) (2023)
- [ASIL: Augmented Structural Information Learning for Deep Graph Clustering in Hyperbolic Space](https://mlsanity.com/paper/2504.09970/) (2025)

## Abstract (arXiv)

Similarity-based Hierarchical Clustering (HC) is a classical unsupervised machine learning algorithm that has traditionally been solved with heuristic algorithms like Average-Linkage. Recently, Dasgupta reframed HC as a discrete optimization problem by introducing a global cost function measuring the quality of a given tree. In this work, we provide the first continuous relaxation of Dasgupta's discrete optimization problem with provable quality guarantees. The key idea of our method, HypHC, is showing a direct correspondence from discrete trees to continuous representations (via the hyperbolic embeddings of their leaf nodes) and back (via a decoding algorithm that maps leaf embeddings to a dendrogram), allowing us to search the space of discrete binary trees with continuous optimization. Building on analogies between trees and hyperbolic space, we derive a continuous analogue for the notion of lowest common ancestor, which leads to a continuous relaxation of Dasgupta's discrete objective. We can show that after decoding, the global minimizer of our continuous relaxation yields a discrete tree with a (1 + epsilon)-factor approximation for Dasgupta's optimal tree, where epsilon can be made arbitrarily small and controls optimization challenges. We experimentally evaluate HypHC on a variety of HC benchmarks and find that even approximate solutions found with gradient descent have superior clustering quality than agglomerative heuristics or other gradient based algorithms. Finally, we highlight the flexibility of HypHC using end-to-end training in a downstream classification task.