# HyperAid: Denoising in hyperbolic spaces for tree-fitting and hierarchical clustering

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 54 references that are in the map.
- First posted on arXiv 19 May 2022.

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

- [Poincar'e Embeddings for Learning Hierarchical Representations](https://mlsanity.com/paper/1705.08039/) (2017)
- [Hyperbolic Neural Networks](https://mlsanity.com/paper/1805.09112/) (2018)
- [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)
- [Hyperbolic Graph Neural Networks](https://mlsanity.com/paper/1910.12892/) (2019)
- [Visualizing and Measuring the Geometry of BERT](https://mlsanity.com/paper/1906.02715/) (2019)
- [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)
- [Geoopt: Riemannian Optimization in PyTorch](https://mlsanity.com/paper/2005.02819/) (2020)
- [From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clustering](https://mlsanity.com/paper/2010.00402/) (2020)
- [A cost function for similarity-based hierarchical clustering](https://mlsanity.com/paper/1510.05043/) (2015)
- [Large-Margin Classification in Hyperbolic Space](https://mlsanity.com/paper/1806.00437/) (2018)
- [Tree! I am no Tree! I am a Low Dimensional Hyperbolic Embedding](https://mlsanity.com/paper/2005.03847/) (2020)
- [Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics](https://mlsanity.com/paper/1609.09548/) (2016)
- [Hierarchical Clustering better than Average-Linkage](https://mlsanity.com/paper/1808.02227/) (2018)
- [Ultrametric Fitting by Gradient Descent](https://mlsanity.com/paper/1905.10566/) (2019)
- [Linear Classifiers in Product Space Forms](https://mlsanity.com/paper/2102.10204/) (2021)
- [Network Geometry Inference using Common Neighbors](https://mlsanity.com/paper/1502.05578/) (2015)
- [Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection](https://mlsanity.com/paper/1912.06983/) (2019)
- [Hierarchical Clustering: a 0.585 Revenue Approximation](https://mlsanity.com/paper/2006.01933/) (2020)
- [Highly Scalable and Provably Accurate Classification in Poincare Balls](https://mlsanity.com/paper/2109.03781/) (2021)
- [Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor](https://mlsanity.com/paper/2110.02807/) (2021)

## Built on by (most cited first, 3 of 3)

- [GeoPhy: Differentiable Phylogenetic Inference via Geometric Gradients of Tree Topologies](https://mlsanity.com/paper/2307.03675/) (2023)
- [Principal Component Analysis in Space Forms](https://mlsanity.com/paper/2301.02750/) (2023)
- [Federated Classification in Hyperbolic Spaces via Secure Aggregation of Convex Hulls](https://mlsanity.com/paper/2308.06895/) (2023)

## Abstract (arXiv)

The problem of fitting distances by tree-metrics has received significant attention in the theoretical computer science and machine learning communities alike, due to many applications in natural language processing, phylogeny, cancer genomics and a myriad of problem areas that involve hierarchical clustering. Despite the existence of several provably exact algorithms for tree-metric fitting of data that inherently obeys tree-metric constraints, much less is known about how to best fit tree-metrics for data whose structure moderately (or substantially) differs from a tree. For such noisy data, most available algorithms perform poorly and often produce negative edge weights in representative trees. Furthermore, it is currently not known how to choose the most suitable approximation objective for noisy fitting. Our contributions are as follows. First, we propose a new approach to tree-metric denoising (HyperAid) in hyperbolic spaces which transforms the original data into data that is ``more'' tree-like, when evaluated in terms of Gromov's δ hyperbolicity. Second, we perform an ablation study involving two choices for the approximation objective, ℓp norms and the Dasgupta loss. Third, we integrate HyperAid with schemes for enforcing nonnegative edge-weights. As a result, the HyperAid platform outperforms all other existing methods in the literature, including Neighbor Joining (NJ), TreeRep and T-REX, both on synthetic and real-world data. Synthetic data is represented by edge-augmented trees and shortest-distance metrics while the real-world datasets include Zoo, Iris, Glass, Segmentation and SpamBase; on these datasets, the average improvement with respect to NJ is 125.94%.