Source-linked AI summary
From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clustering
Ines Chami, Albert Gu, Vaggos Chatziafratis, Christopher Ré
TL;DR
Hierarchical clustering needs a global objective and a way to search discrete trees using continuous optimization. HypHC uses hyperbolic leaf embeddings, a continuous LCA analogue, and decoding; its theoretical and benchmark results support the approach.
Problem
Hierarchical clustering lacked a global objective and a differentiable way to search discrete trees and recover them from continuous representations.
Source: §1 · pp. 1–2Method
HypHC relaxes Dasgupta’s objective using hyperbolic leaf embeddings and a continuous LCA analogue, then decodes the embeddings into a dendrogram.
Source: §1 · p. 2Results
Approximate gradient-descent HypHC solutions outperform or match leading methods across HC benchmarks, while the globally optimal solution has a (1 + ε)-approximation guarantee under perfect optimization.
Source: §1 · p. 2Takeaways & Limitations
Jointly optimizing HypHC embeddings for clustering and downstream classification improves accuracy by up to 3.8% over the two-stage approach.
Source: §1 · p. 2Smaller τ improves approximation guarantees but makes optimization more difficult; the theoretical guarantee assumes perfect optimization.
Source: §4.4 · p. 8
Abstract
from arXiv · showhide
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.
1 Introduction
The paper frames hierarchical clustering as optimization over a global tree-quality objective and addresses how to relax its discrete search while still recovering a dendrogram. HypHC uses hyperbolic leaf embeddings and a continuous LCA analogue to make that search differentiable.
1 Introduction
- HC represents datapoints as leaves and clusters as internal tree nodes, providing information at multiple levels rather than requiring a fixed number of clusters.The introduction notes applications ranging from phylogenetics and cancer gene sequencing to text, image, and community analysis.Source: §1 · p. 1
- Dasgupta’s cost supplied a global way to evaluate hierarchical trees, addressing the prior lack of an objective for comparing HC algorithms.Low-cost trees correspond to meaningful hierarchical partitions in the settings described in prior work.Source: §1 · pp. 1–2
- Earlier gradient-based HC approaches did not directly relax Dasgupta’s objective, lacked clustering-quality guarantees, and were outperformed by discrete agglomerative algorithms.The paper identifies the search over unknown tree structures, the discrete LCA, and decoding back to a tree as key challenges.Source: §1 · p. 2
- HypHC parameterizes trees through learned hyperbolic leaf embeddings, relaxes the discrete LCA using hyperbolic geodesics, and decodes the embeddings into a low-distortion dendrogram.The Figure 1 illustration relates the discrete LCA to geodesics and a continuous hyperbolic LCA.Source: §1 · p. 2, Figure 1 · p. 3
- HypHC’s global optimum gives a (1 + ε)-approximation to the discrete-cost minimizer under perfect optimization, while approximate gradient-descent solutions outperform or match leading methods across HC benchmarks.Joint training for a downstream classification task improves accuracy by up to 3.8% over the two-stage embed-then-classify approach.Source: §1 · p. 2
2 Related Work
The related work contrasts HypHC with prior linkage, embedding, and optimization approaches. It positions HypHC as discovering a tree from pairwise similarities while directly relaxing Dasgupta’s objective.
Gradient-based Hierarchical Clustering
Dasgupta’s cost
Agglomerative Hierarchical Clustering
- Linkage methods repeatedly merge clusters, while HypHC learns features from similarities and uses fast decoding; unlike prior hyperbolic embedding methods, it discovers the tree without a known input graph structure.Single, Complete, and Average Linkage select merges using minimum, maximum, and average cluster distances, respectively.Source: §2 · p. 4
Hyperbolic embeddings
3 Background
The background establishes the tree and hyperbolic-geometry vocabulary used by HypHC. It introduces Dasgupta’s cost through subtree sizes and triplet LCA relations, alongside the tree-like behavior of hyperbolic geodesics.
3 Background
- The background introduces the problem notation and reviews hyperbolic geometry, referring readers to standard texts and the appendix for further detail.The section’s setup leads into the HC objective and the Poincaré model.Source: §3 · p. 4
3.1 Similarity-Based Hierarchical clustering
- Dasgupta’s cost favors merging high-similarity pairs in small subtrees, and its triplet formulation expresses cluster separation through LCA relations.The notation defines leaves as datapoints, internal nodes as clusters, and i ∨ j as the LCA of leaves i and j.Source: §3.1 · pp. 4–5
3.2 Hyperbolic geometry
- In the Poincaré model, hyperbolic space has negative curvature, and its geodesics resemble tree shortest paths because paths between points approach the origin.The passage relates this geometry to tree paths, which pass through the nodes’ LCA.Source: §3.2 · p. 5
4 Hyperbolic Hierarchical Clustering
HypHC relaxes Dasgupta’s discrete tree objective by optimizing leaf embeddings in hyperbolic space, then decoding those embeddings into a binary tree. Its framework connects continuous embeddings and discrete trees and provides an approximation guarantee under stated optimization conditions.
4 Hyperbolic Hierarchical Clustering
- HypHC’s continuous optimization framework combines a differentiable cost with a decoder to turn optimized embeddings into a clustering.The theory is developed in two dimensions; increasing the dimension can reduce precision-related optimization difficulties.Source: §4 · p. 5
4.1 Continuous tree representation via hyperbolic embeddings
- Leaf embeddings in the Poincaré disk parameterize binary trees, with their positions alone providing enough information to recover the full tree.The embeddings are optimized by gradient descent and then decoded into a discrete binary tree.Source: §4.1 · p. 6
4.2 Differentiable objective function
- HypHC defines a differentiable objective by replacing discrete lowest common ancestors with a continuous analogue based on hyperbolic geodesics.The objective uses the deepest continuous LCA among each triplet, softened using a differentiable weighting.Source: §4.2 · pp. 6–7
4.3 Hyperbolic decoding
- The decoding algorithm builds a binary tree by iteratively merging pairs in order of their hyperbolic LCA distances from the origin.It uses LCA depths rather than pairwise distances to recover the tree structure optimized by HypHC.Source: §4.3 · p. 7
4.4 Approximation ratio result
- Under perfect constrained optimization, decoding the optimum spread embedding yields a (1 + ε)-approximation to Dasgupta’s optimal tree.Spread constraints make hyperbolic LCAs distinguishable, and each spread embedding is compatible with an underlying tree; smaller τ improves the guarantee but makes optimization harder.Source: §4.4 · pp. 7–8
5 HypHC Practical Considerations
Triplet sampling and greedy decoding are proposed to reduce HypHC’s runtime and improve scalability.
Greedy decoding
- Greedy top-down decoding sorts normalized leaf embeddings by angle and recursively splits at the largest angle; it can run in O(n log n) when splits are roughly even.Its worst-case runtime is quadratic, and experiments find it significantly faster than exact decoding.Source: §5 · p. 8
Triplet sampling
- Triplet sampling keeps all unique leaf pairs and samples a third leaf, reducing the loss computation from O(n^3) to roughly n^2 triplets.Sampling fewer triplets allows HypHC to produce clusterings for larger inputs and can be parallelized.Source: §5 · p. 8
Practical considerations
- The quality guarantees assume exact decoding and exact loss computation, while the paper empirically evaluates the faster techniques’ clustering quality.The reported empirical quality is measured in terms of Dasgupta’s cost.Source: §5 · p. 8
6 Experiments
Experiments evaluate HypHC on similarity-based clustering benchmarks, analyze quality and speed tradeoffs, and test its use in downstream classification. The reported results include competitive Dasgupta-cost performance, faster greedy decoding, and improved classification accuracy with end-to-end training.
6 Experiments
- The experiments cover clustering quality, quality-speed tradeoffs, and downstream classification using end-to-end training.Figure 3 panels address triplet sampling, downstream classification, and decoding, respectively.Source: §6 · pp. 8–9, Figure 3 · p. 10
6.2 Clustering quality
- HypHC matches or outperforms the best discrete method on all datasets and significantly improves over UFit in discrete Dasgupta cost.The table reports clustering quality using discrete Dasgupta cost; zoo embeddings also move toward the disk boundary during optimization as clusters become better separated in the dendrogram.Source: Table 1 · p. 9, §6.2 · p. 10
6.1 Experimental setup
- Experiments use six UCI datasets and CIFAR-100 with cosine similarities, comparing HypHC against linkage methods, Bisecting K-Means, and UFit.The study measures clustering with discrete Dasgupta cost, where lower is better, and uses classification accuracy for the downstream task.Source: §6.1 · p. 9
6.3 Analysis
- Greedy decoding is approximately 60 times faster than exact decoding while achieving almost the same cost; increasing sampled triplets reduces discrete cost.Using O(n2) triplets was sufficient for good clustering quality in these experiments, with triplet count trading runtime against quality.Source: §6.3 · p. 10, Figure 3 · p. 10
6.4 End-to-end training
- End-to-end training improves classification accuracy by up to 3.8% over Two-Step, while both approaches outperform Label Propagation on most datasets.The experiment uses four HC datasets with categorical leaf labels and a 30/60/10 training, testing, and validation split; all nodes are available at training time, but only training labels are used.Source: §6.4 · p. 11
7 Conclusion
The conclusion presents HypHC as a differentiable approach that searches over discrete trees through constrained hyperbolic embeddings. It reports a (1+ε)-factor approximation under perfect optimization, empirical gains over existing HC algorithms, and possible extension to constituency parsing.
7 Conclusion
- HypHC connects discrete trees with constrained hyperbolic embeddings and reports a (1+ε)-factor approximation to Dasgupta’s cost minimizer, alongside empirical gains over existing HC algorithms.The theoretical analysis assumes perfect optimization.Source: §7 · p. 11
- The guarantee assumes perfect optimization; characterizing optimization hardness and approximating the continuous optimum more tightly remain future directions.The conclusion notes that no constant-factor approximation of the continuous optimum is possible, while better, such as polylogarithmic, approximations remain of interest.Source: §7 · p. 11
- The continuous optimization framework may extend beyond clustering to discrete-tree search tasks such as constituency parsing.Source: §7 · p. 11
Broader Impact
The paper frames potential positive impact as conditional on unbiased input data, while noting that data bias can produce unfair clustering. Its preliminaries establish tree and hyperbolic notation and characterize hyperbolicity through slim triangles.
Broader Impact
- Biased input data can lead to unfair clustering and discriminatory decisions; the authors condition hoped-for positive impact on unbiased input.They describe the work as studying a downstream application after data collection.Source: Broader Impact · p. 11
A.1 Notations
- A binary tree has leaves of degree 1 and internal nodes of degree 3; a rooted binary tree has a root of degree 2.The paper uses undirected trees in its proofs.Source: §A.1 · p. 15, §A.2 · p. 15
- The notation distinguishes tree distance from hyperbolic distance and uses distance from the tree root or disk origin as depth.The paper also uses LCA depth to compare pairs of leaves or embedded points.Source: §A.1 · p. 15
A.2 Gromov’s delta hyperbolicity
- In a δ-hyperbolic space, triangles are δ-slim: each point on one side lies within δ of one of the other two sides.The passage contrasts this with large Euclidean isosceles triangles, whose midpoints can be far from the other sides.Source: §A.2 · p. 16
A.3 Tree-likeness of the hyperbolic space
The appendix uses the tree-likeness of hyperbolic space to relate embedded points to binary trees. It also explains how to enforce leaf and binary conditions while controlling distance changes.
A.3 Tree-likeness of the hyperbolic space
- For hyperbolic embeddings, LCA depth is closely related to the Gromov product, which equals tree depth for 0-hyperbolic metrics.The appendix attributes the comparison to Lemma A.1 and invokes results for tree and hyperbolic metrics.Source: §A.3 · p. 16
- For any finite set of points in B2, a binary tree can approximate their pairwise distances with additive error Cn = δ · O(n).The tree distances do not exceed the hyperbolic distances, which in turn are at most the tree distances plus Cn.Source: §A.3 · p. 16
- To enforce the leaf condition, the construction inserts dummy nodes and changes relevant tree distances by at most 2c.The resulting tree has the required leaves, with distances bounded as dT′(i,j) ≤ dT(i,j) ≤ dT′(i,j) + 2c.Source: §A.3 · p. 17
- To enforce the binary condition, high-degree nodes are replaced by connected copies, changing distances by at most 2c(n − 1).Degree-2 nodes are deleted; the resulting tree distances satisfy dT′′(i,j) ≤ dT′(i,j) ≤ dT′′(i,j) + 2c(n − 1).Source: §A.3 · p. 17
- The tree approximation implies a (1, Cn)-quasi-isometry between the leaves of a binary tree and any embedding set in B2.This is stated as a consequence of Proposition A.1.Source: §A.3 · p. 17
B Hyperbolic LCA construction
The appendix derives a construction for the hyperbolic LCA by finding the point on the geodesic between two disk points that is closest to the origin. Circle inversions and the hyperbolic distance function support the calculation.
B Hyperbolic LCA construction
- The hyperbolic LCA of x and y is the point on their connecting geodesic that minimizes distance to the origin.The construction also calculates this point’s distance to the origin.Source: B Hyperbolic LCA construction · p. 17
- Circle inversion recovers the circle orthogonal to the disk boundary that represents the geodesic between x and y.The derivation uses the inversion property and the disk’s unit radius to relate the circle’s radius and center distance.Source: B Hyperbolic LCA construction · p. 18
- The derivation identifies the orthogonal projection of the origin onto the geodesic as x ∨ y, then uses hyperbolic distance to obtain the result.The calculation uses the angles between x, y, the origin, and the projection.Source: B Hyperbolic LCA construction · p. 18
C Proof of Theorem 4.1
This section presents the proof strategy for the paper’s (1 + ε)-approximation result for Dasgupta’s discrete objective, with supporting lemmas detailed in Appendix C.
C Proof of Theorem 4.1
- The section’s main result is a (1 + ε)-approximation ratio for Dasgupta’s discrete objective.The proof overview invokes Lemmas C.1 and C.2.Source: C Proof of Theorem 4.1 · p. 18
- The section first outlines the proof strategy and states the two results used in the proof.Those results are Lemma C.1 and Lemma C.2.Source: C Proof of Theorem 4.1 · p. 18
- The detailed derivations of Lemma C.1 and Lemma C.2 are placed in Appendices C.1 and C.2, respectively.Source: C Proof of Theorem 4.1 · p. 18
C.0 Proof outline
The proof establishes HypHC’s approximation guarantee by relating spread hyperbolic embeddings and rooted binary trees in both directions, using LCA agreement to connect triplet orderings and show that their continuous and discrete costs are close. In particular, every unit-weight rooted binary tree on n leaves has a spread embedding that decodes back to that tree.
C.0 Proof outline
- HypHC’s decoded tree achieves a (1 + ε)-approximation to Dasgupta’s minimum when τ ≤ O(1 / log(1/ε)).The proof combines the close-cost result for decoded spread embeddings with the existence of a spread embedding that decodes to the optimal tree.Source: §C.0 · pp. 18–19
C.1 Proof of Lemma C.1
- The proof of Lemma C.1 establishes that decoded spread embeddings have discrete costs close to their continuous costs by using LCA agreement.Its steps introduce LCA agreement, show that spread embeddings satisfy it with a binary tree, then relate the decoded tree’s cost to the embedding’s cost.Source: §C.1 · p. 20
C.1.1 LCA Agreement
- LCA agreement means two point sets share the same LCA triplets relative to their base points, and this agreement ensures decoding recovers the corresponding rooted tree.For an unrooted binary tree, removing the base-point leaf yields the rooted tree returned by decoding.Source: §C.1.1 · p. 20
C.1.2 Any spread embedding is in LCA agreement with some binary tree
- Every spread embedding is in LCA agreement with a binary tree, enabling decoding to recover a tree with the corresponding LCA ordering.The proof constructs a quasi-isometric tree and uses spread constraints to distinguish its deepest LCAs.Source: §C.1.2 · pp. 22–23
C.1.3 The tree decoded from any spread embedding has a cost close to the HypHC cost
- LCA agreement preserves the ordering of triplet LCA depths, making the decoded tree’s discrete cost close to the embedding’s continuous HypHC cost.The proof identifies the decoded tree with the rooted version of the corresponding unrooted tree.Source: §C.1.1 · p. 20, §C.1.3 · pp. 23–24
C.2 Proof of Lemma C.2
- Sarkar’s embedding result gives unit-weight trees embeddings with scale ζ = O(1/ε) and distortion at most 1 + ε, supporting the construction of spread embeddings corresponding to binary trees.The supplied proof begins by using this result toward a spread embedding in LCA agreement with a given tree.Source: §C.2 · p. 24
- Choosing ε ≤ 1/(3n) and ζ > 6Cn + 6δ + 2 establishes that Z is spread and in LCA agreement, completing the embedding argument.The proof uses ζ = Θ(n), which is possible for the embedding and sufficient because Cn = O(n).Source: §C.2 · p. 25
- For any unit-weight rooted binary tree T on n leaves, attaching leaf 0 to the root, then applying Lemmas C.7 and C.3, yields a spread embedding Z with dec(Z) = T.Source: §C.2 · p. 25
D.1 More experimental details
HypHC’s relative improvement over the best baseline is greater on datasets with larger upper–lower cost-bound gaps, and its comparison with gHHC depends on the dataset and metric. The appendix also details evaluation choices and illustrates greedy decoding.
D.1 More experimental details
- Experiments use cosine similarities, standardized UCI features, pretrained BiT image features for CIFAR-100, and the best of five random seeds for randomized methods.Agglomerative baselines use SciPy; BKM is implemented from, and UFit uses its original hyperparameters [20].Source: §D.1 · pp. 25–26
- Dasgupta cost is the primary quality metric; dendrogram purity does not correlate well with it on some datasets.The appendix reports dendrogram-purity scores in Table 2.Source: §D.1 · p. 26, Table 2 · p. 26
- A larger relative gap between upper and lower Dasgupta-cost bounds indicates more hierarchical structure; coincident bounds for a unit-weight clique imply every tree has the same cost.For datasets with more than 1,000 nodes, the bounds use uniformly sampled triplets and averages over 10 random seeds.Source: §D.1 · p. 26
- HypHC’s relative improvement over the best baseline is more important on datasets with larger cost-bound gaps, such as Iris or Segmentation, than on CIFAR-100.The authors suggest HypHC gets closer to the underlying hierarchical clustering when the data has a good underlying hierarchy.Source: §D.1 · p. 26
D.2 Greedy decoding
- Greedy decoding first splits at the two largest angles, then recursively splits each resulting subset using its largest angle.Figure 8 illustrates the initial split in red and the subsequent subset splits in blue and green.Source: §D.2 · p. 27
D.3 Comparison with gHHC
- On Spambase, HypHC and BKM have the best Dasgupta-cost and dendrogram-purity scores, while HypHC significantly outperforms gHHC on dendrogram purity.gHHC’s scores are taken from [39].Source: Table 2 · p. 26, §D.3 · p. 27
- On Glass, the relationship between metrics is less clear: SL performs poorly on Dasgupta cost but well on dendrogram purity, and the authors conjecture flat clusters may not track the optimal hierarchy.Dendrogram purity indicates clustering quality only when ground-truth flat clusters correlate with the hierarchy.Source: §D.3 · p. 27