Ultrametric Cluster Hierarchies: I Want ‘em All!
Authors: Andrew Draganov
Pascal Weber
Rasmus Skibdahl Melanchton Jørgensen
Anna Beer
Claudia Plant
Ira Assent
Venue: NeurIPS 2025 poster ()
Keywords: Ultrametric
Center-Based Clustering
Hierarchical Clustering
DBSCAN
HDBSCAN
k-means
k-median
Primary area: general_machine_learning
TL;DR: We prove clean optimality results for clustering in ultrametrics, identify ways to take advantage of this theory and thoroughly evaluate the resulting techniques.

Abstract: Hierarchical clustering is a powerful tool for exploratory data analysis, organizing data into a tree of clusterings from which a partition can be chosen. This paper generalizes these ideas by proving that, for any reasonable hierarchy, one can optimally solve any center-based clustering objective over it (such as $k$-means). Moreover, these solutions can be found exceedingly quickly and are *themselves* necessarily hierarchical. 
Thus, given a cluster tree, we show that one can quickly access a plethora of new, equally meaningful hierarchies.
Just as in standard hierarchical clustering, one can then choose any desired partition from these new hierarchies. We conclude by verifying the utility of our proposed techniques across datasets, hierarchies, and partitioning schemes.

Ultrametric Cluster Hierarchies: I Want 'em All!
Andrew Draganov" 1,2 Pascal Weber* 3,4,5
Rasmus Jørgensen' Anna Beer* Claudia Plant Ira Assent
Department of Computer Science, Aarhus University, Aarhus, Denmark
IAS-8: Data Analytics and Machine Learning, Forschungszentruun Jülich, Germany
3 Faculty of Computer Science, University of Vienna, Vienna, Austria
UniVie Doctoral School Computer Science, University of Vienna, Vienna, Austria DDta Science @ Uni Vienna, University of Vienna, Vienna, Austria
draganovandrew@@gall. com
pascal weberrunivee acc.at
Abstract
Hierarchical clustering is powerful tool for exploratory data analysis, organizing data into a tree of clusterings from which partition can be chosen. This paper generalizes these ideas by proving that, for any reasonable hierarchy, one can optimally solve any center-based clustering objective over it (such as k-means). Moreover, these solutions can be found exceedingly quickly and are themselves necessarily hierarchical. Thus, given a cluster tree, we show that one can quickly access a plethora of new, equally meaningful hierarchies. Just as in standard hierarchical clustering, one can then choose any desired partition from these new hierarchies. We conclude by verifying the utility of our proposed techniques across datasets, hierarchies, and partitioning schemes.
1 Introduction
Hierarchical clustering a fundamental technique for exploratory data analysis [42, 77]. The key idea is that having tree of clusterings over given dataset allows users to choose any partition from this hierarchy that best suits the users' needs. These notions go beyond standard agglomerative clustering algorithms to also include density-basee clustering techniques like DBSCAN [24] and HDBSCAN [12). Even non-hierarchical clustering algorithms like k-means can be solved efficiently by leveraging hierarchical representations [17, 18, 55].
The central underlying concept of hierarchical clustering methods is that they can be modeled using ultrametrics: distances which satisfy the strong triangle inequality d(x, z) S max(d(x, y), d(y, =)) for all v, y, Put Put simply, hierarchical structures [4]. Originally described for phylogenetic and agglomerative clustering tasks [57, 65], the depth of this equivalence between hierarchical clustering and ultrametrics has inspired multiple subfields of unsupervised learning theory [3, 19, 22].
of points can only satisfy this inequality if they are arranged in nested,
Our results. We prove an elegant, previously unknown property of ultrametrics: all standard center-bart based clustering tasks (i.e., k-means, h-median, k-center) can be solved optimally in any ultrametrie. The key insight is that, in this setting, these baster-based clustering tasks can be reduced to sorting. Consequently, our algorithm is remarkably efficient: given an ultrametric on n points, finding the full set of optimal solutions (i.e., for all & e [n]) requires only Sort(n) time the time to sort n. values. Our results therefore improve on recent work in both runtime and generality [6, 18, 44].
39th Conference Neural Information Processing Systems (NeurIPS 2025).
First authors with equal contribution in alphabetical order. 'https://githur com/ haam//paiiveeee//t---aaaaes https://pypi. http/projeet//StPffrrateee
Implementation and experiments Python interface package

---

Section
Section 4
Section 5
Data with any relaxed ultrametric
LCA-tree defined by relaxed ultrametric
Choose
Cluster Hierarchy
Possible Partitionings
Partitioning Method
A-2
Elbow method,
Therrm X3
A2 &
minimax path distance, KD
Examples altrametrics:
Def. 4.1 & Threrom 4.2
Examples of cluster hicrarchies: L-center, E-median,
Creudary 5.1
Threshoking.
Cluster Value Functions
Figure I: Overview of our proposed SHiP clustering framework in which we (1) fit an ultrametric, (2) choose a center-based hierarchy on the ultrametric, and (3) extract a partition from the hierarchy.
Moreover, these center-basee based partitions are themselves necessarily hierarchical: the set of optimal center-based clustering solutions in an ultrametric form cluster-tree.
Building on these theoretical insights, we introduce the SHiP Simillrrty--Herraccyy Hiieraccy-PPattitionnn Partitioning) clustering framework. While traditional approaches merely extract flat partitions from predefined hierarchies, SHiP enables discovering entirely new hierarchical relationships via center- center-based cluster- ing, substantially increasing the expressiveness of hierarchical clustering. Users can then efficiently extract any desired partition from these novel hicrarchies. We depict this process in Figure 1, where specify which sections of paper describe the SHiP framework's various components.
Figure provides a motivating example of the SHiP framework's 's practical value. When HDBSCAN fails to find the desired partition, the typical workflow would involve trying entirely different algorithms like Euclidean k-means or Ward clustering [77], repeating the costly data-fitting step while still potentially fail- ing to find the correct partition. SHiP eliminates this redundancy: having already fit the de-dist ultrametric [6] during HDBSCAN's execution, we can instantly explore alternative cluster structures through different hierarchies. In this case, the correct partition found in the k-median hierarchy when k = 2. This exemplifies SHiP's core advantage: once an ultrametric is computed, numerous clustering perspectives become available essentially for free, enabling rapid dataset exploration. Our extensive experiments confirm this is not cherry-picked example; many SHiP-derived combinations consistently produce novel, high-quality clusterings that compete with or outperform state-of-the--at algorithms with minimal additional computational cost.
HDBSCAN
Fucl.
Ward
de-dist/ k-median ()
k-means
Figure 2: Clusterings on the 2-moons dataset with varying densities.
Related Work
Our primary theoretical result is that all center- center-based clustering tasks in ultrametrics be reduced to sorting. The novelty and simplicity of this is particularly surprising as each of these topics- ultrametrics, hierarchical clustering, and conee-based clustering has received significant attention:
Ultrametries. Due to the strong triangle inequality, ultrametrics naturally encode hicrarchical relationships [4]. Consequently, ultrametrics arise in numerous applications like biology [52]. number theory [34], physics [62]. computer science, they allow for simple, parallelizable solutions [38] and extensive research has explored low-distortion embeddings of metrics into ultrametrics [4, 19]. This is often done via hierarchically well-separated trees (HSTs), data structures which model the original distances via tree path-distances [3. 39]. Notable examples include KD trees [8], Cover trees [9], and HSTs which obtain optimal distortion but are slower to compute [25. 79]. These are all used to accelerate machine learning algorithms [53, 73], computer graphics [27], and nearest-neighhor search [63, 69]. Our framework enables the first comprehensive evaluation of HSTs across clustering tasks, revealing that they consistently fail to preserve underlying cluster structures regardless of

---

hierarchy or partitioning method. Our findings challenge the commonly assumed suitability of HSTs for accelerating ML tasks, especially in precision sensitive settings.
precision-sensitive
separate line of work has studied clustering algorithms in trees. Here, it is known that, for a fixed value of k. k-center can be solved optimally in (n) time [54, 75, 10). Similarly, k-median can be solved optimally in O(n log log**2 n) time [71, 7]. There are two primary differences between this work and our setting. First, in our setting, the centers may only be placed on leaves in the tree. Second, we require that all distances are ultrametric, whereas distances over blge-wweightd trees are not necessarily ultrametric. Consequently, our results show that under these additional constraints, all center-based clustering tasks in trees reduce to the same underlying problem.
Hierarchical Clustering. Hierarchical clustering methods represent data at multiple scales of granularity in single structure. These techniques typically produce dendrograms- structures that encode nested partitions of the data-from which users can extract flat clusterings (partitions) at different resolution levels [12. 56]. Part of hierarchical clustering's s appeal that, given hierarchy, the partitions can often be extracted in O(n) time [43]. Thus, hierarchical clustering is particularly valuable in exploratory data analysis, where the number of clusters often unknown a priori [51, 64).
Traditional hierarchical clustering algorithms (such as single- and complete-linkage) merge clusters according to distance calculations which are often ultrametric in nature [57]. For instance, the single- linkage algorithm corresponds to an ultrametric over the dataset's minimum spanning tree (MST), where the single-link distance (also known as the minimax path distance) between two points is given by the weight of the largest edge in the MST path between them [26]. Recent variants of hierarchical clustering have moved away from procedural merging rules in favor of finding ultrametries which minimize an objective function with respect to the data [1, 15, 16, 19, 22].
Center-Based Clustering. Center- based clustering is one of the most thoroughly researched paradigms in unsupervised learning. Formulations such as k-means, k-median and k-center are NP-hard in arbitrary metric spaces [21, 31J. leading rich literature on approximation algorithms with provable speed/accuracy guarantees (2, 28, 55J. Within this, several papers have leveraged HST ultrametrics for faster center-based clustering [17. 23, 44].
Two recent works are particularly relevant to our approach. Beer et al. [6] showed that k-center can be solved optimally in the generalization of the single-link distance and is the backbone behind the DBSCAN and HDBSCAN clustering algorithms. The algorithm in Beer et al. is essentially equivalent algorithm in Cohen- Addad et al. [18]. Cohen-Addat et al. went further by providing a second algorithm which optimally solves --median in a 2-HST ultrametric in (n log' (A + 12)) time, where is the tree-depth of the HST they construct. Both papers observed that the resulting solutions Our results can be interpreted as a generalization of algorithm 2 in Cohen-Addad et al. Specifically, we show that their algorithm 2 holds for any ultrametric and reduces to k-center (which itself reduces to sorting).
ultrametric (dc-dist) in Onn²) time. This ultrametric is
necessarily hierarchical.
In this sense, our approach yields several advantages over the prior techniques. First, rather than designing algorithms for specific center-based clustering tasks on specific ultrametrics, we provide general theoretical framework that handles all center-based clustering objectives optimally in all ultrametrics. Second, our runtime improves over the state-of- of-tee-f--hhaatt and we prove to be tight. Lastly, our algorithms relatively simple to abstract, allowing us evaluate our SHiP framework across many ultrametrics and datasets. Such an experimental ablation was previously absent from the literature.
3 Ultrametrics and Tree Representations
We begin by formally introducing the data structure that require for our proof techniques. Namely, the upcoming results hold over a generalization of the standard ultrametric::
Definition 3.1. Let T. be a set. Then d I. x I, + R2o is a relaxed ultrametric over T. if, for all 4, Ej lk T., the following conditions are satisfied:
d(l,,))) d(e,, 20 and (2) d) (x) ()),
3

---

Note that the standard ultrametric is a restriction that additionally requires d(c,, (x) = O. Thus, not all relaxed ultrametrics are distances as die, (.) > is allowed. Still, we use the word "distance" for readability. We represent relaxed ultrametric relationships via the following data structure:
Definition 3.2. A lowest-common- ancessor tree (LCA-tree) is a rooted tree T such that every node " 7' has value d(1) 2 O associated with it. We write Nni 3 fl to indicate that fi lies the path from to the root and y V fJ to refer to the LCA of y and fj.- We say that the I.CA-distance between two leaves E, Ej T is given by d(4; fz)-
An L.A-trre is not necessarily binary: if three or more subtrees are all equidistant, they can all be children of the same node. While similar data structures already exist for standard ultrametrics [4, 35), the following theorem (proof in A.2) states that it can also encode all relaxed ultrametrics:
Theorem 3.3. Les (I., d be a finite relaxed ultrametric space. Then there exists ICC--rre T with LCA-distance d and bijection f I. ++ leaves(T) such that, for all li 2j E L, d' (z) (f((.) f(L)))
This is visualized by the first box of Figure 1. It shows minimum spanning tree (MST) over some data on the left. In this MST, the single-link ultrametric given by the weight of the largest edge in the path between two nodes [26]. For example, the single-link distance between nodes and is 5 The right-hand side of the first box of Figure then stores these distances in an LCA-tree (i.e., the LCA of nodes 1 and 4 has value 5). We prove in Appendix A.2 that all LCA- trees are relaxed ultrametrics as long as they satisfy the following conditions:
Corollary 3.4. Let T be LCA-tree. For any leaf E II, let p(() = [a. No...... Mbe (T)) be the path from E to the root of the tree rT)). Then the -iC-aiitasces on T form a relaxed ultrametric if and only if. for all é leaves(T)) and mhs TT p()), the following conditions
satisfied:
(1) d(L) 2 20 and (2) 1h 1 f =
d(n)) S d(n))-
Corollary 3.4 describes a key property: if tree's node values grow along paths from the leaves to the root, then the corresponding LCA-distances are relaxed ultrametric. This is the natural representation of a hierarchy: since the subtrees grow in size as we go towards the root, the values corresponding to those subtrees also grow. Going forward, we assume that a relaxed ultrametric given in its LCA-tree form, satisfying the properties in Corollary 3.4.
4 Center-based Clustering in Ultrametrics
Our main theoretical result is that center-based clustering can be solved optimally in a relaxed ultrametric, that these solutions are hierarchical. and that they all be found in Sort(n) time. We define the (k, 2) cllustering and the k-center clustering objectives over an LCA-tree T as finding the set of centers C C -leavee (T) with C = k which minimize, respectively,
Cost, (T,
Σ min d(e,c))
Costac (T,C) = max min d(e,c). (Elewes(TT) cEC
cEC
& (Tleave((T)
k center clustering objective
(lhss)-chsseeiing objective
Note that (ks, 2) clcuttrtni gives the well-known k-median and k-means tasks for and
We now define what it means for a clustering to be hierarchical. Given a set of points L,, we define a cluster C any subset of L. We then define partition Pa (Ci,..., Ck) as any non-overlapping set of k clusters, i.e., for all O₁ C2 E P, C, nC, = 0. Then:
Definition 4.1. (Lin et al. [48]) A cluster hierarchy H (PI...., Pn)) a set of partitions where for & = 1: for < k < n:
Pi L, and
Ps = (P \ C2) (C,, Gi such that (a) C, = C, E P with C. C. C; (b) C2 * C, and Ci * C, and (c) i + j 1.
Although standard ultrametrics are often encoded via shortest-path distances a tree [61]. relaxed ultra- metries cannot represented in this way due to the possibility of having d(E, (,) > Although sorting is traditionally On log operation, it often only requires Orn log log n) time [30].

---

buidd hecrade
patiioa
Normalized cost
2-5
SCAR
2.385s
+0
+13
+15
Tixe is milliccoods
DCAlcc/part.
9,000
AMD-DBSCAN-
37 0755
14
DPC
2
10
Time in scconds
40
80
Figure 3a: Runtimes of competitors and frame- work's components on the letterree dataset. Compared to computing the de-dist ultrametric, finding the k-- means hierarchy and extracting the elbow partition requires negligible time.
Number of clusters (k)
Figure 3b: Example elbow plots for the
1, 2, 3, 4, and 5 settings under the de-dist ultrametric the D31 synthetic dataset. Elbow locations (circles) determined using all l E [L. n] with 3100.
In short, each partition Ps is obtained by splitting one cluster from Pk-1 in two, implying that all cluster hierarchies can be represented as a rooted tree. We depict this in Figure 1 (middle), where the hierarchy obtained by subdividing the clusters. We can now state our primary thcoretical result:
Theorem 4.2. Let (I,dd) d) be a finite relaxed ultrametric space represented over an LCA-tree T. Let = [T] and Nyo- Then, for both the k-center and (k, clluustrri objectives on T, there exists an algorithm which finds the optimal solutions {Ci....; C, for all k E [n] in Sort(n) time. Furthermore, the respective partitions H (P.....; Pn) obtained by assigning all leaves in T to their closest center satisfy Definition 4.1.
Proof Overview. In words, Theorem 4.2 states that given any LCA-tree over relaxed ultrametric, takes Sort(n) time to find the full set of optimal solutions for k-means, i--median or k-center across all values of & and that these solutions are themselves hierarchical. The k-center part of this result is an extension of the farthest-first traversal algorithm in which one places each subsequent center on the point that is farthest from the current set of centers [31, 32]. In essence, Appendix A.3 shows that under the strong triangle inequality, the farthest-first traversal algorithm (a) becomes optimal and (b) reduces to sorting the distances in the ultrametric. We then show in Appendix A.4 that the (k, --cluscrrnn objectives in an ultrametric can be reduced to the k-center one a relaxed ultrametric. That is, given LCA-tree T which to do (k, cllustrrri, there exists new LCA-tree such that an optimal k-center solution on T is the optimal (k, e)clusterinn solution on T. Interestingly, even if are solving (k, clusstrrg in standard ultrametric, it reduces to k-center in a relaxed one. This is why we require the notion of relaxed ultrametrics for our proofs.
A key insight which underpins this reduction is that these center-based cluster hierarchies themselves constitute relaxed ultrametrics. That is, let H be a hierarchy optimal k-center or (k, =)-ussetni solutions from Theorem 4.2. For each cluster C in this hierarchy, consider the cost deast (C) of assigning all of its points to a single optimal center. As we traverse the tree towards the root, these costs will necessarily grow (see Lemma A.13). Thus, by Corollary 3.4, the hierarchy H. with LCA- distances deast must be a relaxed ultrametric. Indeed, any binary LCA-tree satisfying the properties in Corollary 3.4 is its own optimal A-center hierarchy.
Finally, the runtime bottleneck for k-center lies sorting the O(n) unique distances in the ultrametric in order to apply the farthest-first traversal algorithm. This is also the bottleneck for (k, 2) cllusteerng as the reduction to k-center only requires (n) time. We verify that this runtime is tight: one cannot find the optimal centers for all values of k in faster than Sort(n) time (Lemma A.7). This speed is depicted Figure 3a: although takes several seconds to fit the density-connecttvity ultrametric, only takes milliseconds construct the h-median hierarchy.
5

---

5 Choosing a Partition
Theorem 4.2 gives us a hierarchy of optimal center-based clustering solutions for all values of k at once. However, what if we are interested in the "best" clustering from this hierarchy? ? To this end, there are several techniques for extracting additional partitions from these hierarchies in (()) time.
5.1 Feasibility of the Elbow Method
One of the most common methods for choosing a "best" clustering is the elbow method [72]. Here, one is given set of values of k. {ky k.,..,,,y,,, and set of corresponding partitions Each partition incurs a cost L; Ecep, C(C") with respect to the clustering objective. This gives us a plot of costs over the different values of k. Informally, the elbow method chooses the partition P; whose cost L; looks to be at sharp point in this curve.
P = {P,, : py}.
Due to the NP-hardness of k-means clustering, standard elbow plots can only compute approximate solutions, traditionally done sequentially for each k [67]. However, the elbow method is surprisingly viable in the ultrametric setting: Theorem 4.2 yields optimal clusterings for all ls values once, eliminating both computational overhead and approximation errors. Moreover, we show that the relaxed ultrametric's 's elbow plot for (k, 2) -clusterrn guaranteed to be convex:
Corollary 5.1. Let P and L correspond the partitions and losses obtained in accordance with Theorem 4.2 for the (k, z)cclsttri objective. Let A; = fit1 L.. Then either A, < Ai+1 S or A, = A++1 for all E 1]
The idea here is that A, represents the elbow plot's first derivative at k = i. Thus, Corollary 5.1 states that the elbow plot's slope steepest at k = 1 and monotonically levels out to 0 as k + n. We prove this in Appendix B.I, where we also specify how we determine the index of the elbow. We depict relaxed ultrametric elbow plots for (k:, z)-clsstering with 2,2,3, 3, 4, Figure 3b, An alternative plot with the r-axis going to n can be found in Figure 7 in the Appendix.
5.2 Additional Partitioning Techniques
Beyond the elbow method, there are several other standard approaches for selecting partitions and augmenting the hierarchy which can be applied to our hierarchies in (n)) time. These are standard in the literature and we discuss them more depth in Appendix B.
Thresholding the Tree. One can threshold the cluster hierarchy at a user-defined value 6, as is done in linle-linkage clustering or DBSCAN [6]. This involves labeling internal nodes of the tree by their costs and returning all clusters with costs below s, thus extracting partitions based on a similarity threshold rather than specific & value. This naturally extends the (k, setting: simply return the non-overlapping nodes in the (k, elccutrtgi hierarchy below some cost threshold.
Cluster Value Functions. Rather than selecting based on costs, one can also assign a new value function to clusters and then choose the set of non-overlapping clusters that maximizes the sum of these values. For example, HDBSCAN uses the stability objective to measure how well clusters persist across the largest range of threshold values. Similarly, techniques in hierarchical segmentation define an energy function over the clusters [43, 56). We show Appendix B.4 that, given any reasonable such function, one can find its maximizing partition in (nn) time via depth-first search.
Handling Noise Points. For applications requiring noise handling, subtrees consisting of outlier points can be pruned from the hierarchy without compromising the underlying ultrametric properties. For instance, with minimum-cluster-ae O(n) time, ensuring all clusters in the final partition meet size requirements [12, 47]. In practice, HDBSCAN's stability objective function is applied after noise points have been removed in this way.
parameter μ4, clusters smaller than μ can be removed in
5.3 Integrating Multiple Partitioning Methods
A key advantage of our approach is that, because the hierarchies and partitions can be extracted so quickly (as seen in Figure 3a), multiple hierarchies and partitions can be integrated with negligible runtime impact. We therefore introduce the oottiannoo-Elbowwe (MoE) algorithm which we find to

---

work well in practice. After fitting an ultrametric, MoE computes (k, 2) cclusterigg hierarchies for 2 1, 3, 4, and applies the elbow method to each hierarchy. It then selects the median &t value from this set, representing the clustering cardinality that remains stable across different distance penalty settings. One can then use this k value to extract the clustering from any hierarchy. Figure 3b visualizes this process on the D31 dataset, where MoE selects k = 14.
6 From Theory to Practice
Sections 3-5 introduce the components of our clus- tering framework: fitting an ultrametric to capture the data similarities, choosing hi- erarchy, and partitioning the data. Table I outlines various (utrrametrichhierarccyy/aa tition] combinations. For example, [DC/k- median/thresholding]] means that we are using the thresholding partition technique on the de- dist's k-median hierarchy. the following, we demonstrate that the SHiP framework includes diverse, effective clustering strategies and en-
Table I: Example ultrametric, hierarchy, and parti- tioning options. Our SHiP framework allows one to pick any ultrametric, pair it with any clustering hierarchy, and extract any partition.
SHiP HinnnaartyyHeerrrch--aaaiiiii
Ultrametries
Hierarchies
Partilioning Methods
DC tree
k k-center k-median k meams
Ground Truth & (GT)
Single Linkage tree Complete Linkage tree Cover tree
User-specifid
Elbow
Median of Hlbows (Mot)
KD tree
Thresholding Stability
HST-DPO
ables quickly finding the various data groupings that can be extracted from an ultrametric. This particularly valuable for exploratory data analysis, where quickly switching between clustering methods and results is beneficial.
6.1 Ultrametrics
We now formally introduce the two families of ultrametrics which we use to evaluate our framework: HSTs and the connttt-connettivity distance. We note, however, that one can also apply our techniques to nearly the full suite of agglomerative clustering hierarchies [57], which we leave for future work.
Hierarchically Well-Separated Trees (HSTs). HSTs recursively subdivide metric spaces into trees such that each internal node is equidistant all descendant leaves. The distances in the metric space are then approximated using the tree's 'ss path distance. We use three types of HST:
1. Cover trees [9] define nested (potentially non-convex) cells so that points in cell L,- and
q E L; (where L, C I)-1) satisfy d(p, 9) 2'.
2. KD trees [8] recursively subdivide the space into axis-aligned hypereubes.
3. HST-DPOs [79] achieve optimal distance distortion by subdividing the space using metric balls.
Figure 4a demonstrates how the same hierarchy+ppartiton (k-median with ground truth k) behaves across different HSTs (Cover tree, KD tree, HST-DPO), revealing how the underlying tree structure shapes clustering outcomes. Namely, Cover trees construct non-convex regions of similarity, KD trees produce axis-aligned clusterings, while HST-DPOs use spherical divisions. The first two require On log n) construction time (assuming constant dimensionality). while HST-DPOs achieve optimal distortion at the expense of O(n²) runtime. Although HSTs traditionally utilize the tree's path distances, this can be transformed to an LCA-trre representation in (nn) time by assigning d(n) = d (1), E) for internal node 7) with any descendant leaf l. Going forward, we use Cover trees as our default HST, with KD trees and HST-DPOs extensively compared in Appendix E.
Distance (dc-dist). The second ultrametric we use, the de-dist, forms the foundation of density-connected clustering algorithms such DBSCAN and HDBSCAN. In short, is the single-linkage distance over the pairwise mutual-reachabiline between the points:
Definition 6.1 (Mutual reachability [24]). Let (L, d') be a metric space, x and y be any two points in L. and Z Let (z)(2) be the distance from æ to its μ-th closest neighbor in L. Then the mutual reachability between x and y is m, y) = max(d" (x,, y), (x), (y))))
Definition 6.2 (de-dist [6]). Let (T.,d" be a metric space, and y any two points in L,, and Z Let T be minimum spanning tree over L's pairwise mutual reachabilities. Let p(æ, y) be
7

---

Cover tree k-median/GT
KD tree k-median/GT
HST-DPO k-median/GT
DC tree k- k-center/Stability
DC tree
DC tree
k- A-median/MoE
k- m-mann//Elbow
BoxG
(a) Comparison of HST ultrametries using the k- median hierarchy and the ground ground-truth value of k.
(b) Comparison of hicrarchy/partition combina- tions the de-dist ultrametric.
Figure 4: Visualizations of the ultrametrics and hierarchy/partition combinations on the Boxes dataset.
the path T from to y given by edges {es...., eg} in T. Lastly, let |e| be the weight of any edge in T. Then the dc-dist between x and y is defined as
ddc( y)
|e| if + ys else (2, eEp(a.y)
max
We note that Beer al. [6] introduced strictly ultrametric variant of the de-dist where the distance of point to itself was hardcoded to be O. However, removing this condition we do in Definition 6.2 simply makes the dc-dist a relaxed ultrametric (proof in B.5):
Proposition 6.3. Let (L, d') be metric space. Then, the de-dist over L is a relaxed ultrametric.
We refer to the de-dist's LCA-tree representation as the DC tree. Note that for 1, the de-dist is simply the single-link distance. We default μ for all experiments. Within our SHiP framework, we can exactly reproduce DBSCAN through [DC tree/k-comte//breshollngg and HDBSCAN via [DC tree/k- senee//ccmttr//stblittl..
6.2 Hierarchies and Partitioning Methods
Having fit an ultrametric, the SHiP framework allows users to explore multiple alternative groupings of the data through its many hierarchies and partitions. Each hierarchy represents different perspective on how points in the ultrametric space should be organized, essentially defining search space of possible clusterings. Partitioning methods then extract specific clusterings from these hierarchies. highlighting different structural characteristics. Our experiments focus on three illustrative hicrarchy/partition combinations: k-ceentersttability, k-median/MoE and k-meens/clbow.
Figure 4b offers an illustrative example of how these hicrarchies and partitions interact. For example, the k-center hierarchy merges clusters based distances their centers, regardless of point count. When combined with the stability objective, this finds clusters which are well-separated over a wide range of thresholds. Consequently, in the Boxes dataset, k-center/stability merges the two red boxes since they share densitt-connected path (and removes some outliers as noise).
In contrast, the k-median and k-means hierarchies strike balance between the distances to the centers and the cluster cardinalities. For example, under the dc-dist, the k-median and k-means hierarchies evaluate how "spread out" cluster is: the cost is low when there few points which are densely connected (have small gaps between dense regions). This explains why k-median/MoB and k- k-means/elbow separate the two red boxes in the last two columns of Figure 4b that k-center merges: they contained too many points with too large gap between them. Figure in the Appendix shows example the D31 dataset with more pronounced differences between the methods.
7 Experiments
We now verify the practical utility of our SHiP clustering framework by showcasing its speed and competitive outputs across ultrametrics and datasets. Table the Appendix gives an overview
DBBSCAN' is variant of DBSCAN which treats points the borders of clusters noise [12].

---

Table 2: Runtimes of our SHiP framework's 's components (first three column groups) and competitors (last column group) in (minutes+)secome ultrametries are comparable to the runtimes of the competitor algorithms. Le., building the DC tree is on par with other density-based based methods (highlighted in blue). Computation of the cluster hierarchies and partitioning methods then takes only milliseconds. Full version: Table 5 in the Appendix.
(s), or milliseconds (ms). Computation times of the
ultrametric
hicr.
partitioning
competitors
Dutuset
Cover tree
DC tree
means
Sth.
Moll
Elbow
(k GT)
J-means
(k 500)
k-mncass
SCAR
Ward
DBSCAN
AMD-
DPC
Baress
0.09%
14,250
3ver
ans
0.114
1.217s
1
10.508
1404.60o
12410.388,
Tahuke Data
D31
0.327
4mm
Dry
15 ms
Omn
0.289
0.509A
0.620
0.153a
0376.
12816
zirway
4
21
1uy
0.122/
0.392
0.661
5,243a
168822
6+66.726J
Inctate
4
68.m
6rer
275 ms
4m
0.126
19977
2,612
59,092
7443.203
09454012
11053x
23.1447
14ms
56
2248/
8.478
184488
/
letterrec.
0.322
9.0767
mm
2
57 mt
Ints
3,385
3,521
2,1335
10.309:
37.055
1I+/2910z
PenDigits
0.077
2,566
m3
53 ms
Oms
1.01
2.725
0,490
3
9.254
S+21,409/ x00
COIL20
3,658
14,817
1ns
Use
1,637y
13.524x
0.310s
8941a
2,378
11,710
Image Date
COLLIOO
3+52,397
14+50,661
10
Dmy
19
Omss
52.122r
1+59
225.
7,964s
12+04.007
2+58.177s
14+18,750s
0.06xx
0,238
0.205
0.661
0.36x
0.515
OptDigis
0.335
1,420,
6ms
Dver
24
Oms
0.502
1.154
0.290
0.974.
3.073x
44,270
USPS
2924x
S,670
11
45
2709>
8.495
6,092
29.259
1448, 607
MNIST
16+24.2000
04405095
m20
15
491 mm
4.330x
3+299 969
15.352
19402.498.
17421.183
of the datasets we use. We evaluate the clustering quality with the adjusted rand index (ARI) [36], treating points labeled as noise as singleton clusters. NMI [70], AMI [74] and correlation coefficient [29] results can be found in Appendix E. Both our runtime and accuracy* tables report the mean over 10 runs. All experiments were performed on 2x Intel 6326 with 16 cores each and 512GB RAM.
7.1 Runtimes
In practice, clustering is an exploratory data mining task that requires several runs of different methods or using different hyperparameter settings. Especially when done sequentially, this requires substantial computational time and resources. In contrast, our SHiP clustering framework requires just a single upfront ultrametric computation, after which we can generate a myriad of different clustering solutions with negligible additional runtime. Table 2 and Figure 3a highlight this efficiency. The first column group in Table 2 shows that computing our ultrametrics (Cover tree and DC tree) has runtime comparable to that of the corresponding standard clustering algorithms (last column group). Specifically, we show on the right (under competitors) the time required for Euclidean k-means with ground-truth k, and Euclidean k-means with 500, 5 Ward agglomerative clustering [77], an adaptive multi-density DBSCAN version (AMD-DBSCANT [76], density peaks clustering (DPC) [66]. and an accelerated version of spectral clustering (SCAR) [33]. However, once the ultrametric has been computed, generating different hierarchies (column group 2) and partitioning methods (column group 3) requires only milliseconds. Thus, users can explore many different clustering solutions in essentially the same time it takes to run a traditional clustering algorithm.
7.2 Clustering Quality
This efficiency in switching between clusterings is particularly valuable given the results shown in Table 3. Here, we study the quality of k-center/stabilliyy, k-median/MoF, and k-means/elbow on the DC- and Cover tree ultrametrics and compare them against the competitor algorithms. Importantly, k-means, Ward, and SCAR are all given the ground-truth & to maximize their competitiveness. In comparison, even in the more realistic setting where the true number of clusters unknown, we can achieve better clustering performance than they do using the DC tree. However, there is no best hicrarchy/partiiioning combination. Although k-meens/elbow performs best in many cases, is not universally superior to the other combinations; different pairings excel on different datasets. This underscores the value of rapidly switching between different hierarchies and also partitioning methods.
Notably, Cover tree combinations consistently perform worse than Euclidean k-means, with compara- ble results for KD trees and HST-DPOs in Appendix E. This raises the question of whether HSTs are
'For non-deterministic algorithms, we also provide the standard deviation for the clustering accuracy. 'Note that the SHiP clustering framework simultaneously obtains the optimal solutions for every value of k.

---

always well-suited for representing the underlying cluster structure in data, and under what conditions their use can effectively accelerate machine learning pipelines [18, 44, 53, 73].
the ground truth number of clusters is given to our framework, k-median and k-means over the de-dist (essentially density-connected k-median and k-means) achieve even slightly better results (see Table 6; Appendix). Furthermore, we point out that Ward agglomerative clustering is ultrametric nature and, therefore, falls under the umbrella of our framework [57].
Table 3: ARI values for the SHiP framework the DC and Cover tree ultrametrics (resp. first/second column group). ARI values for competitor algorithms are in the third column group. Euclidean k-means, SCAR, and Ward given the ground-truid & value. Full version: Table 6 in the Appendix.
DC tree k-medion
Cover free
compelitors
k-median
SCAR
AMD-
TPC
Stabllay
Stability
Boxes
9011
99.3
97.9
2.6
22.1 4.7
242 # 1.6
83.5 =
0.1 011
95.8
63.3
25.9
Tabular Diza
D31
70.7
42.7
62.9
16.5 1.8
02:0+
07.7 3.2
82.0 + 2.7
92.0
66.4
18.5
airway
38.0
65.9
58.6
0.8
18.2+ 2.4
12.0+11 1.4
30.9 + 2.0
0.9
43.7
31.7
65.1
lactate
1.74:..
1.6
71.5
0.0
1422
Jetterne..
12.1
16.6
17.9
5.8
1/2 0.8
6.2. 0.3
12.9 1 0.8
0.100:11
14.7 0.9
7.9
0.01
PenDignss
86.4
23.1
75.4
8.0 0.8
12.0
8.1...
55.3 1 3.2
0.0 0:3
55.2
55.8
28.8 1
COIL20
72.6
66.4
16.611.1
2.0
58.2 2.8
35.5 2.0
68.6
39.2
35.0 1.1.1
Image Data
COIL100
44.6
46.6
1:2
OpiDigits
55.3
77.0
77.0
60.9 3.5
20
18.1 1.44
61.5
4..1144.1
2..8.12.
63.2
0.0
USPS
33.7
29.3
29.3
12.0 1.7
8.7 1.0
112 1.5
52.3 1.7
2.0 0.9
65.9
0.0
21.0
VINIST
10.7
41.7
86.0
11.1
+
54+ 0.6
54+00
36.0
1.3
62.7
0.0
Conclusions and Limitations
This paper proposed and evaluated generalization of standard hierarchical clustering. Our theoretical contributions suggest new algorithms for hierarchical clustering under, for example, the Dasgupta objective [22], as well connections to spectral clustering [49]. We leave both to future work. Furthermore, although our approach enables Sort(n)-ting access to novel clustering hierarchies after fitting ultrametric, the initial ultrametric computation remains the performance bottleneck. A key limitation is that the clustering quality depends significantly on this choice ultrametric. I.e., we find that the de-dist consistently produces high-quality clusterings across different hierarchy/partition combinations while HSTs produce subpar results. We therefore suggest that future work focuses on developing fast algorithms for fitting ultrametrics which effectively model the data.
Acknowledgements
We thank Chris Schwiegelshohn, who provided advice and insights when developing the theoretical framework surrounding Theorem A.8.
We gratefully acknowledge financial support from the Vienna Science and Technology Fund (WWTF- ICT19-04I) and the Austrian funding agency for business-oriented research, development, and innovation (FFG-903641"). Andrew Draganov is partially supported by the Independent Research Fund Denmark (DFF) under Sapere Aude Research Leader grant No 1051-00106B and by project W2/W3-108 Impuls und Vernetzungsfonds der Helmholtz- HelmbollzzGeemiinchhee funding from Danish Pioneer Centre for AI, DNRF grant number P1.
We also acknowledge
'uttps://projektee.fe wft.::/ktte.fff....oe. htt.://k......ga.////////////// 'nttps://alcentre..
10

---

References
[1] Noga Alon, Yossi Azar, and Danny Vainstein. Hierarchical clustering: A 0.585 revenue approximation. In Conference Learning Theory, pages 162-162. PMLR, 2020.
[2] David Arthur and Sergei Vassilvitskii. k-means++: The advantages careful seeding. Technical report, Stanford, 2006.
[3] Yair Bartal. On approximating arbitrary metrices by tree metrics. In Proceedings of the thirtieth anmual ACM symposium on Theory of computing, pages 161-168, 1998.
[4] Yair Bartal, Nathan Linial, Manor Mendel, and Assaf Naor. On metric ramsey-type phenomena. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 463-472, 2003.
[5] Tomas Barton.
Clustering
benchmark.
pettps://gtthub.com////
wlustering-bendteee
2019.
[6] Anna Beer, Andrew Draganov, Ellen Hohma, Philipp Jahn, Christian M. M. Frey, and Ira Assent. Connecting the dots density- connectivty distance unifies DBSCAN, k-center and Spectral Clustering. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 80-92, 2023.
[7] Robert Benkoczi and Binay Bhattacharya. A new template for solving p-median problems for trees in sub-quadratic time. In European Symposium Algorithums, pages 271 2-1-282. Springer, 2005.
[8] Jon Louis Bentley. K-d trees for semidynamic point sets. In Proceedings of the sixth annual symposium on Computational geometry, pages 187-197, 1990.
[9] Alina Beygelzimer, Sham Kakade, and John Langford. Cover trees for nearest neighbor. In Proceedings of the 23rd international conference on Machine learning. pages 97-104, 2006.
[10] Binay Bhattacharya, Sandip Das, and Subhadeep Ranjan Dev. The weighted k-center problem in trees for fixed k. Theoretical Computer Science, 906:64-75, 2022.
[11] Broad Institute. Single cell portal, 2025. URL https://singleeell. broadinstitute. httss/iinneeelllliieeeeeeeeeeeee
Accessed: 2025-01-29.
[12] Ricardo G. Campello, Davoud Moulavi, and Jörg Sander. Density- based clustering based on hierarchical density estimates. In Advances in Knowledge Discovery and Data Mining, pages 160-172, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. ISBN 978-3-642-37455-2. doi: htips://doi.or//10/ wtwp///...0//9...... 0000797783-642-375566
[13] Ricardo G. Campello, Davoud Moulavi, Arthur Zimek, and Jörg Sander. Hierarchical Density Estimates for Data Clustering, Visualization, and Outlier Detection. ACM Transactions on Knowledge Discovery from Data, 10(1):1-51, July 2015. ISSN 1556-4681, 1556-472X. doi: 10.1 10.1145/273338. URL https: / //l/ acm. org//oi/10/ 1145/273338-
[14] Gunnar E. Carlsson, Facundo Mémoli, et al. Characterization, stability and convergence of hicrarchical clustering methods. J. Mach. Learn. Res., 11(Ap)):1455-4477) 2010.
[15] Moses Charikar and Vaggos Chatziafratis, Approximate hierarchical clustering via sparsest cut and spreading metrics. In Proceedings of the Twenty-Fighll Annual ACM-SIAM Symposium on Discrete Algorithmss, pages 841-854. SIAM, 2017.
[16] Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann- Trenn, and Claire Mathieu. Hierar- chical clustering: Objective functions and algorithms, 2017. URL https://arzias ortiiii.rrr/aaba 1704. 02147.
[17] Vincent Cohen-Addar Addad, Silvio Lattanzi, Ashkan Norouzi-Fard, Christian Sohler, and Ola Svens- son. Fast and accurate k--eans++ via rejection sampling. Advances Neural Information Processing Systems, 33:16235- 2020.

---

[18] Vincent Cohen- Addad, Silvio Lattanzi, Ashkan Norouzi-Fard, Christian Sohler, and Ola Svens- son. Parallel and efficient hierarchical k-median clustering, Advances in Neural Information Processing Systems, 11-22333-203344 2021.
[19] Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee, and Araud De Mesmay, Fitting metrics and ultrametrics with minimum disagreements. SIAM Journal on Computing, 54(1):92-133, 2025.
[20] Ryan R. Curtin, Mareus Edel, Omar Shrit, Shubham Agrawal, Suryoday Basak, James J. Balamuta, Ryan Birmingham, Kartik Dutt, Dirk Eddelbuettel, Rishabh Garg, Shikhar Jaiswal, Aakash Kaushik, Sangyeon Kim, Anjishnu Mukherjee, Nanubala Gnana Sai, Nippun Sharma, Yashwant Singh Parihar, Roshan Swain, and Conrad Sanderson. mipack 4: a fast, header- only c++ machine learning library. Journal of Open Source Software, 8882):5026, 2023, doi: 10.21 105/joss. 050226. URL httpp:///dot org/10. /0. 21105/jos /0000/000.000 05026.
[21] Sanjoy Dasgupta. The hardness of k-means clustering. 2008.
[22] Sanjoy Dasgupta. A cost function for similarity-based hierarchical clustering. In Proceedings of the firty-eighth annual ACM symposium on Theory of Computing, pages 118-127, 2016.
[23] Andrew Draganov, David Saulpic, and Chris Schwiegelshohn. Settling time vs. accuracy tradeoff's for clustering big data. Proceedings of the ACM on Management of Data, 2(3):1 2024.
[24] Martin Ester, Hans-Pete Kriegel, Jörg Sander, and Xiaowei Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In KDD, volume 96, pages 226-231, 1996.
[25] Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 448-455, 2003.
[26] Bernd Fischer, Volker Roth, and Joachim Buhmann. Clustering with the connectivity kernel. Advances in neural information processing systems, 16, 2003.
[27] Tim Foley and Jeremy Sugerman. Kd-tree acceleration structures for a gpu raytracer. In Proceedings of the ACM SIGGRAPHIEURGCRAPHICS conference on Graphics hardware, pages 15-22, 2005.
[28] Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical computer science, 38:293-306, 1985.
[29] Martijn M Gösgens, Alexey Tikhonov, and Liudmila Prokhorenkova. Systematic analysis of cluster similarity indices: How to validate validation measures. In International Conference Machine Learning, pages 3799-3808. PMLR, 2021.
[30] Yijie Han. Deterministic sorting in o (n log log n) time and linear space. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 602-608. 2002.
[31] Sariel Har-peled. Geometric Approximation Algorithms. American Mathematical Society, USA. 2011. ISBN 0821 849115. 15.
[32] Dorit S. Hochbaum and David B. Shmoys. A best possible heuristic for the k-center problem. Mathematics of operations research, ((2):180-184, 1985.
[33] Ellen Hohma, Christian M. M. Frey, Anna Beer, and Thomas Seidl. Scar: spectral clustering accelerated and robustified. Proceedings of the VLDB Endowment, (5(11):333-3300 2022.
[34] Jan Holly. Pictures of ultrametric spaces, the p-adic numbers, and valued fields. The American Mathematical Monthly, 108(8):721-72,, 2001.
[35] Fazeleh Hoseini and Morteza Haghir Chehreghani. Memory-efficient minimax distance mea- sures. Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 419-431. Springer, 2022.
12

---

[36] Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of classification, 2:193-218,
1985. doi: https://doi.org/ 10. 908075.
[37] Jonathan J. Hull. A database for handwritten text recognition research. IEEE Transactions on pattern analysis and machine intelligence, 16(5):550-54, 1994.
[38] Piotr Indyk. Algorithmic applications of low-distortion geometric embeddings. In Proceedings 42nd IEEE Symposium Foundations of Computer Science, pages 10-33 IEEE, 2001.
[39] Piotr Indyk. Algorithms for dynamic geometrie problems over data streams. In Proceedings of the thitty-sixth annual ACM Symposium Theory of Computing, pages 373-380, 2004.
[40] Philipp Jahn, Christian M. M. Frey, Anna Beer, Collin Leiber, and Thomas Seidl. Data with density-based clusters: A generator for systematic evaluation of clustering algorithms. In Joint European Conference on Machine Learning and Knowledge Discovery in Databuses, pages 3-21. Springer, 2024.
[41] Angur Mahmud Jarman. Hierarchical cluster analysis: Comparison of single linkage, complete linkage, average linkage and centroid linkage method. Georgia Southern University, 29, 2020.
[42] Stephen C. Johnson. Hierarchical clustering schemes. Psychometrika, 32(3):241-254, 1967.
[43] B. Ravi Kiran and Jean Serra. Global-local optimizations by hierarchical cuts and climbing energies. Pattern Recognition, 47(1):12-22 2014.
[44] Andreas Lang and Erich Schubert. Accelerating k-means clustering with cover trees. In International Conference Similarity Search and Applications, pages 148-162. Springer, 2023.
[45] Bruno Leclerc. Description combinatoire des ultramétriques. Mathématiques et Sciences humaines, 73:5-37, 1981.
[46] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 (6:11)2227823324 1998.
[47] Andrew Lim, Brian Rodrigues, Fan Wang, and Zhou Xu. k-center problems with minimum coverage. Theoretical Computer Science, 332(1-3):1-17, 2005. doi: https://doi.org/10..00 tcs.2004.08.016
[48] Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, and David P. Williamson. A general approach for incremental approximation and hicrarchical clustering. In Proceedings of the seventeenth annual ACM-SIAM symposium Discrete algorithm, pages 1147-1156, 2006.
[49] Anna V. Little, Mauro Maggioni, and James M. Murphy. Path-based spectral clustering: Guarantees, robustness to outliers, and fast algorithms. Journal of machine learning research, 21, 2020.
[50] Kolby Nottingham Markelle Kelly, Rachel Longjohn. The uci machine learning repository, 2023. URL htt.ttt////aciiieeee ics. uci edu/ml.
[51] Wendy L. Martinez, Angel R. Martinez, and Jeffrey Solka. Exploratory data analysis with MATLAB. Chapman and Hall/CRC, 2017.
[52] Emília P. Martins and Elizabeth A. Housworth. Phylogeny Shape and the Phylogenetic Comparative Method. Systematic Biology, 51(6):873-880 12 2002. ISSN 1063-5157. doi: (10000/00031115020002222
[53] Leland McInnes and John Healy. Accelerated hierarchical density based clustering, In 2017 IEEE International Conference on Data Mining Workshops (ICDMW), pages 33-42. 2017. doi: 10.1 199/CCMM.2007.12
[54] Nimrod Megiddo and Arie Tamir. New results on the complexity of p-centre problems. SIAM Journal Computing, 12(4):751-758, 1983.
13

---

[55] Ramgopal R. Mettu and C. Greg Plaxton. The online median problem. SIAM Journal on Computing, 32(3):816-835 832, 2003.
[56] Fernand Meyer and Laurent Najman. Segmentation, minimum spanning tree and hierarchies. Mathematical morphology: from theory applications, pages 229-261, 2013.
[57] Glenn W. Milligan. Ultrametric hierarchical clustering algorithms. Psychometrika, 44(3):
343-346, 1979.
[58] Abdolreza Mirzaci and Mohammad Rahmati. A novel heruachical-lusteinn-combmiiiiid scheme based fuzzy-similarity relations. IEEE Transactions on Fuzzy Systems, 18(1):27-39, 2009.
[59] Sameer A. Nene, Shree K. Nayar, and Hiroshi Murase. Columbia object image library (00) 1996. URL attps://wwwy cs. columbia. http://///////ttttttt//tttt////t
php.
[60] Sameer A. Nene, Shree K. Nayar, and Hiroshi Murase. Columbia object image library (coil-20). 1996. URL https: //www cs. columbia. http/////////.tttttt///t//tttttt
php-
[61] Roderick D. M. Page and Edward C. Holmes. Molecular evolution: a phylogenetic approach. John Wiley & Sons, 2009.
[62] Dmitry Panchenko. The parisi ultrametricity conjecture. Annals of Mathematics, pages 383-393, 2013.
[63] Parikshit Ram and Kaushik Sinha. Revisiting kd-tree for nearest neighbor search. In Proceedings of the 25th acm sigkdd international conference on knowledge discovery & data mining, pages 1378 1388, 2019.
[64] Andreas Rauber, Dieter Merkl, and Michael Dittenbach. The growing hierarchical self- organizing map: exploratory analysis of high-dimensional data. IEEE Transactions on Neural Networks, (3(6):3331-1441 2002.
[65] David F. Robinson and Leslie R. Foulds. Comparison of phylogenetic trees. Mathematical biosciences, 53(1-2):131-1477 1981.
[66] Alex Rodriguez and Alessandro Laio. Clustering by fast search and find of density peaks. science, 4444,444444411111149-199999 2014. doi: 10. 10.1116/science. 2ttb:/cciemee112227222
[67] Erich Schubert. Stop using the elbow criterion for k-means and how to choose the number of clusters instead. ACM SIGKDD Explorations Newsletter, 25(1):36 2023.
[68] Congming Shi, Bingtao Wei, Shoulin Wei, Wen Wang, Hai Liu, and Jialei Liu. A quantitative discriminant method of elbow point for the optimal number of clusters in clustering algorithm. EURASIP journal on wireless communications and networking, 2021:1-16, 2021.
[69] Harsha Vardhan Simhadri, George Williams, Martin Aumüller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini, Ravishankar Krishnaswamny. Gopal Srinivasa, et al. Results of the neurips21 challenge on billion-scale approximate nearest neighbor search. In NeurIPS 2021 Competitions and Demonstrations Track, pages 177-189, PMLR, 2022.
[70] Alexander Strehl and Joydeep Ghosh. Cluster ensembles-a knowledge reuse framework for combining multiple partitions. Journal of machine learming research, 3(Dec):583-617, 2002.
[71] Arie Tamir. An (pn2) algorithm for the p-median and related problems on tree graphs. Operations research letters, 19(2):59-64, 1996.
[72] Robert L. Thomdike. Who belongs in the family? Psychometrika, 18(4):267-27) 1953.
[73] Laurens Van Der Maaten. Accelerating t-sne using tree-based algorithms. The journal of machine learning research, 15(1):32113325, 2014.
[74] Nguyen Xuan Vinh, Julien Epps, and James Bailey. Information theoretic measures for clus- terings comparison: a correction for chance necessary? In Proceedings of the 26th annual international conference machine learning, pages 1073-1080, 2009.
14

---

[75] Haitao Wang and Jingru Zhang. An o(n (ogn)-time algorithm for the k-center problem in trees. SIAM Journal on Computing, 50(2):602 635, 2021.
[76] Ziqing Wang, Zhi qin Ye, Yuyang Du, Mao, Yanying Liu, Ziling Wu, and Jun Wang. AMD- DBSCAN: An adaptive multi-density DBSCAN for datasets of extremely variable density. 2022 IEEE 9th International Conference on Data Science and Advanced Analytics (DSAA), pages 1-10, 2022. URL http:::/aapi..smmmtttss
www.oolarrrrrroooooo org/CorpusID 252918697.
[77] Joe H. Ward Jr. Hierarchical grouping to optimize objective function. Journal the American statistical association, 58(301))236-244, 1963.
[78] Joonas Yoon. Clustering exercises dataset, 2023, URL attps://www www.:wwwwg.....mm...... com/ tatasets//oonassooon// clustering-exerriiaee.
Accessed: 2025-01-29,
[79] Yuxiang Zeng. Yongxin Tong, and Lei Chen. HST+: An efficient index for embedding arbitrary metric spaces. In 202/ IEEE 37th International Conference on Data Engineering (ICDE), pages IEEE, 2021.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract and introduction state the paper's main contributions: (1) proving that center-based clustering objectives can solved optimally in ultrametrics in Sort(n) time, (2) demonstrating that these solutions form hierarchical structures, and (3) introducing the SHiP framework with extensive experimental validation. These claims align with the detailed theoretical results in Section 2-4 and the experimental results in Section 5-6.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The paper discusses computational limitations in the runtime analysis, ac- knowledges that different ultrametrics produce different clustering structures (Figure 5), and notes that HST implementations achieve worse performance than Euclidean k-means in certain cases. The paper also acknowledges that fitting the ultrametric is computationally intensive compared to the subsequent steps.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specificatiin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
16

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [Yes]
The paper states all assumptions about ultrametrics and center-based clus- tering, Complete proofs for all theorems are provided in the appendices, while the main paper provides proof sketches. The theoretical framework is built systematically, starting with definitions of relaxed ultrametrics and LCA-trees (Section 3), then proving the main theorems about optimal clustering (Section 4).
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: The paper provides detailed information about the experimental setup, dataset characteristics (Table 4), implementation details (Appendix C), and algorithm specifications. It describes how ultrametrics are constructed, how hierarchies are de- rived, and how partitions are extracted. The paper also mentions code availability at https: //gi:///tthbb
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
17

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
Our code is provided at https://github. www.coo//aaaaao wwtppuu...ooopaiiieeeeeeeee pwtp/aaaiwebr///mmo SHiP-framework. The paper also uses standard benchmark datasets and third-party hard-party implementations (mlpack for KD trees, Cover trees) with proper citations.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
http:/guddee//oeeeuunmiie onloiicyPo)) for more details.
While we encourage the release of code and data, understand that this might not be possible, so No is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurIPS code and data submission guidelines (https: / /nips. htc//uublc//guudes::sseeeeeeeeee httpg//dde//eedduiiiieesseeeeeee poooee@umisssoPol1111.
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper details the experimental settings including dataset characteristics (Table 4), implementation details (Section 5.3), parameter settings (e.g., μ=5 for dc-dist), and evaluation metrics (ARI, NMI, AMI, correlation coefficient). The experimental setup for comparing different combinations of ultrametrics, hierarchies, and partitioning methods is clearly described.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
18

---

The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report enror bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
The paper reports that results were obtained over ten runs as indicated in Tables 3 and 2. The comprehensive tables in the appendix provide detailed performance metrics across multiple datasets and method combinations, allowing for comparison of relative performance.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Section 5.3 specifies "All experiments were performed with Python 3.12 on 2x Intel 6326 with 16 hyperthreaded cores each and 512GB RAM." 'Table 5 provides detailed runtime information for each component of the framework across different datasets, reported in minutes, seconds, and milliseconds.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: : htt///nuriip.oo
19

---

Answer: [Yes]
Justification: The research presents algorithmic and theoretical contributions to clustering methods without ethical concerns. The paper properly credits prior work, uses standard benchmark datasets, and makes no claims that would violate the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper presents theoretical and algorithmic contributions to foundational clustering methods without direct application-specifie societal impacts. The work focuses improving computational efficiency and theoretical understanding of clustering algorithms. Any impacts would be mediated through specific applications of clustering, which would require additional context-specific consideration.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairesss considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
The paper introduces algorithms for clustering and doesn' 't release high-risk models or datasets that could be misused. The work focuses on theoretical results and algorithmic improvements for clustering methods using standard benchmark datasets.
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
20

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The paper properly cites the sources of existing algorithms and libraries used, including mipack for KD trees and Cover trees, and provides URL for the HST-DPO implementation. The standard benchmark datasets used referenced in Table 4.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [Yes]
The paper introduces a new clustering framework (SHiP) with detailed al- gorithm descriptions, theoretical foundations, and implementation details. The code is made available attpps:/gitthi provides extensive documentation of the algorithms and their efficient implementation (Algorithms 1-5 in Section 9).
Justification:
hwm/ppsiweebrr/SH..... f-frmeworrk. The appendix
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
21

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve human subjects research, so IRB approval not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The paper does not use LLMs as part of its core methods.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our L.LM policy (https htt////eerrpppppeee hctc///eeeeeecce//22//////////// for what should or should not be described.
22

---

A Proofs for Sections 3 and 4
In this section, we prove Theorem 3.3, Corollary 3.4, and Theorem 4.2 from the main body of the paper. We restate each here:
Theorem 3.3. Let (L,d') be a finite relaxed ultrametric space. Then there exists LCA-tree T with LCA-distance d and bijection f L ++ leaves(T)) such that, for all E,, &j E L, d' (l &z)
(f(2)) f(()))
Corollary 3.4. Let'T be an LCA-tree. For any leaf L E I, let p(f) = [4, ma...... from E to the root of the tree r(T). Then the LCA-distances on ' form a relaxed ultrametric if and only if. for all E (eaaee(TT) and 1p Fy E p(e), ), the following conditions are satisfied:
........ Tb. r r[T) be the path
(1) (( 2 20 and (2) TT. = = d(n:)) S d(()))
Theorem 4.2. Let (I,,d) be a finite relaxed ultrametric space represented over an ICA-trre T. Let = [T] and Nyo- Then, for both the k-center and -b)cuuststr objectives on T, there exists an algorithm which finds the optimal solutions (Ci....; C.) for all k E [n] in Sort(n) time. Furthermore, the respective partitions = (P Pn] obtained by assigning all leaves in T to their closest center satisfy Definition 4.1.
A.1 Overview of Ideas
We begin with more thorough proof outline to the one that appears in the main body of the paper.
First, will define relaxation of ultrametrics and show few immediate properties of these spaces. Their key property is that there is essentially an equivalence relation induced by any relaxed ultrametric: for any distance value d, the sets of points that are within distance d of each other partition the space. This is generalization of the ideas in Carlsson et al. [14].
We then show that all relaxed ultrametrics can be represented (LCA-trees). These are rooted trees where every node has a value associated with it. The distance between two leaves in an LCA-tree is the value in their lowest common ancestor. Furthermore, all LCA-trees are (relaxed) ultrametrics if the values are monotonically non-decreasing along the path from any leaf to the root (Corollary 3.4). As result, there is bijective relationship between LCA-trees and ultrametrics (Theorem 3.3). We proceed by only considering ultrametrics in the LCA-tree data structure.
We now consider the center- based clustering objectives over these LCA-trees. Here, a centers are placed on leaves of the tree and the point-to-center distances are given by the L.CA-distances, For k-center, we will see that the well-known strategy of farthest-first traversal [31] (which achieves 2-approximation in Euclidean space) is actually optimal in ultrametrics. This algorithm works by placing the first center on random leaf and then, for each subsequent center, placing on the node which induces the highest cost. The intuition here is that the farthest-firs. traversal's 's standard 2-approximation is a direct consequence of the triangle incquality, so changing this to the strong triangle inequality resolves the approximation constant.
We now reduce the algorithm of farthest first traversal in an ultrametric to sorting the nodes in the LCA- By placing this first center on any leaf, every other leaf in the tree gets mapped to it. Thus, the largest point-center distance corresponds to two leaves whose LCA is the root of the tree. We must therefore place our subsequent centers on leaves until there is no point-center distance which goes through the root of the -CA-tree. This done by placing centers in subtrees in which there are no placed centers. After the root has been handled, we will place centers in accordance with the root's children, focusing on the one which has largest value first. By Corollary 3.4, it must be the case that the LCA-tree's 's values grow as we approach the root. Thus, the runtime being Sort(ni (n) comes from the fact that the farthest- first traversal algorithm "fills in" the tree from the root down. As result, we will solve k-center in an ultrametric by sorting the distances from largest smallest and placing the corresponding centers.
Given this, we will conclude the proof by showing how to reduce the general problem of (k, 2)- clustering (such as k-means) to this k-center algorithm. We will consider these through the lens of the cost-decreuse, of placing k-means or k-median centers in an ultrametric. That is, if we have an optimal solution for some value of k. then the optimal solution for k + centers will have lower cost. Thus, there is cost-decrease associated with placing each optimal center. Our key observation
23

---

is that these cost-decreases themselves satisfy the strong triangle inequality. We will also show that greedily choosing centers that maximize these cost-decreases gives optimal k-means and k-median solutions in an ultrametric. Putting the pieces together, these results imply that we can apply the k-center algorithm in the LCA-tree of cost-decreases get optimal k-means and k-median solutions.
Notation. We use T represent an arbitrary rooted tree with root r. We use 7) to represent arbitrary internal nodes and & to represent arbitrary leaves. We also assume that every internal node in the tree is equipped with a value, which we write by (((r). We use the notation тソ: 3 7/ to indicate that Mi lies on the path from 7) to We use children(1) and parent(n) to indicate the direct children and parent of a node. Lastly, we use the notation from [22] with & V Ej denoting the lowest common ancestor (LCA) of a set of nodes/leaves and I [[]] denoting the subtree rooted 7). Thus, T[e; V Łj] is the smallest subtree containing both & and Ej.
For notation on clustering, we define (k, clluustrin as finding the set of centers C E T with |C| k which minimize Cost, C) =
Σ
min d(t, c)*²
aEC
(Eleaves(1)
This corresponds to k-median and k-means for 1 and 2, respectively. We also define k-center clustering as finding the C which minimizes
Cost (T, C)
max min d(e,c). *Eleaves(T) eEC
A.2 Ultrametries and LCA-Trees
In this section, we introduce relaxed ultrametrics and prove Theorem 3.3 and Corollary 3.4.
Throughout the literature, the stand-out candidate for hierarchical adis-)similarity measure the ultrametric. We will, however require looser definition, which we refer to as relaxed ultrametric:
Definition 3.1. Let L be a set. Then d L x L - Rzo is a relaxed ultrametric over L if, for all 4, Ejs lu L, the following conditions are satisfied:
(1) -(e,, 0 and (2) d(d,,, (c) S max(d((s, &(,
We will prove our results over these relaxed ultrametrics. We note that the set of ultrametrics is a subset of the set of relaxed ultrametrics. That is, strict ultrametrics have the additional condition that the distance between two points is 0 and only if they are the same point. Thus, our theoretical results immediately apply to all ultrametrics.
The strong triangle inequality in Definition 3.1 is what allows ultrametrics to capture hierarchical relationships. Specifically, the strong triangle inequality implies that any three points in an ultrametric space must form an isosceles triangle with an angle less than 60 degrees:
Fact A.1. Let be a dissimilarity measure on a space L, which satisfies the strong triangle inequality. Then for any Es, Ej, lu L, one of the following holds:
1. d(l,, S d(e,, = =d(e,(()
2. d(l,, (6) S d(l,,))) = =d(eg
3. d(lz, (6) d(e,, (z) d(l,,
Proof. Assume that all three unequal, so WLOG d(l,,e)) d(li,ls) a(l,,Ex). Then the strong triangle inequality does not hold, since d(ly, 4.) & max(d(l,, d(L,,()))))
Similarly, assume that the singleton edge is longer than the two others, i.e. d(f.. (4) = d(ey F6) d(l,, L,). This also breaks the strong triangle inequality, since d(l,, (,) I max(d(e;, (()
0
24

---

As result, for any three points in a relaxed ultrametric space, knowing two of the pairwise distances sufficient to give the ordering of all three. For example, if two of the distances in a triangle are equal, then the third must be equal to this distance or smaller.
This naturally extends groups of more than 3 points. Consider the case where we have points (2,, ................................ J so that for any Zi, 23. we have ultrametric distance d(r;; 22) < E for any small 0. Now let y be a point with d(I1, y) 6 with 8 > E. Since the x'S are all close one another, Fact A.I implies that d(z;;) y) must also equal ö for all i. This has the following fundamental consequences:
Theorem 3.3. Let d') be a finite relaxed ultrametric space. Then there exists LCA-tree T with LCA-distance d and a bijection I : LL ++ leaves(T)) such that, for all li lj E L, d' dl (f(()) f(e)).
We first put this in context before giving its proof. Theorem 3.3 states that any ultrametric can be represented over the leaves of tree, with the property that the distance between two leaves is uniquely determined by the value in their LCA. We note that variants of this theorem have been given elsewhere [45, 57, 58]; nonetheless, the results later in this section require the form given above. We refer this data structure an LCA-tree and the "distances" in this tree as LCA-distances.
Proof. We use Fact A.I to design an algorithm to construct the tree T by repeatedly splitting the relaxed ultrametric over its largest distance dmaz. First, let us see that dmaz induces partition over L. Let l, E L be any point and let Lr, = {l, : d(li, (g) < dmaz} U {&, be the set consisting of l; and all the points closer to it than dmaax Now let lg L 3 Le, be any other point not in Le, By definition d(le, 4x) dmaz. Furthermore, by Fact A.1, d(ez, fx) = dmaz for all & E Le,- Thus, dmaz induces partition on relaxed ultrametric where, across any two points in distinet clusters, the distance is necessarily dman-
We now use this idea to devise an algorithm that embeds the ultrametric in an LCA-tree. This algorithm receives a relaxed ultrametric space (I,, d) as input. It begins by instantiating a (initially empty) root node which will serve as the root of the LCA-tree. Let dmaz be the largest distance in (L, d) and let P be the partition induced by dmaz. Assign d(r)) = dmaz. For each group in the partition, make node and assign it as a child of the root r.
We apply this construction recursively for each of the children. The base case occurs when L has either one or two points. If there is only one point, 2; E L. we simply return a leaf 4. This leaf is given weight d(f,) = d(l,, (,) and we define f(x;) = f, If L has two points, 2, and 2; E L, then we create two leaves l; and lj as children of the input node. The mapping is arbitrarily defined as [a:)) = l, and f(x,)) ly- We assign the input node with weight d(r)) d(r,, sr2) and give the leaves weights d({;)) = d(fs, f.) and d(e,) = d(ej. G))
We inductively verify that this construction produces a valid LCA-tree and that all distances in the relaxed ultrametric are preserved by the LCA-distances. In the base case, the space (L, d) has either one or two points. We respectively represent these as a singleton root node or a rooted tree with two children. In both cases, the value of the root is the distance between the two points and the distance of each point to itself is the value in the leaves. Thus, in the base case, all pairwise distances in L are preserved via the LCA- -dditttncss.
In the inductive step, assume that (T,, d) has more than two points, that the maximal distance is d and that all smaller distances are represented via distinct trees. By the above logic, the distance between any two nodes in separate trees must be dmaz- Since the construction described above assigns the value dmaa to the root and assigns the existing trees to it as children, this new node is a parent to the already-existing trees. Thus, their internal LCA-trees and LCA-distances are not affected. However, the LCA between any nodes in separate subtrees has value dmaz. Therefore, the entire ultrametric (L, d) is preserved.
The following corollary gives the sufficient conditions for an LCA-tree to correspond to relaxed ultrametric:
Corollary 3.4. Les be an LCA-tree. For any leaf f. E TT, let p(f) = (f, Ta...., :Tb, r (T)) be the path from E to the root of the tree rT)). Then the -i--diitances on T form relaxed ultrametric if and
25

---

only if. for all i E leaves(T)) and ns. nl E p()), the following conditions are satisfied:
(1) (()) 2 0 and (2) 114 1 fi = d(n)) S d(n,)-
Proof. We first assume that we have an L.CA-tree satisfying the conditions and show that must be a relaxed ultrametric. First, note that the I.CA-distances in the tree satisfy symmetry by the definition of LCA: d(L,, E5) = d(LCA(L, f2))= = d(l,, &.). Furthermore, conditions (1) and (2) together ensure the non-negativity conditions required for relaxed ultrametric. Therefore, it remains to show the strong triangle inequality.
Let Eg and Eg be three leaves in the LCA-tree. If they all have the same LCA (i.e., & V Eg V = f V fg), then the leaves are equidistant in the LCA-tree, and the strong triangle inequality is satisfied. Thus, assume WLOG that & V Eg I ls V lg. This implies that 4 V E = Eg V lx. Consequently, the strong triangle inequality satisfied:
4 Vil 3 v4 V
d(ivEE) -(vv))==()
By Assumption
We now prove the other direction of the if-and-only-if: we assume LCA-tree whose LCA-distances are a relaxed ultrametric and show that it must satisfy conditions 1 and 2. By the non-negativity of the ultrametric, the condition assume for the sake of contradiction that it is not satisfied. Then we must have nodes d and f7 with 7) = f and d(m:) d(nz). We now choose leaves L,, E and E so that L, V C ry and V & = & v f Tÿj. Then we have d(L,, Eÿ) = d(L,, E,) < d(l,,())
d({) 2 O is satisfied for all leaves f. Regarding the second condition,
This is in violation of Fact A.1 and therefore contradicts assumption that the LCA-distances ultrametric.
As a result of Corollary 3.4, we wish to show that tree's LCA-distances satisfy the strong triangle inequality, we need to show that the tree's values non-decreasing on paths from the leaves to the root. Going forward, every discussion of ultrametrics will implicitly be through their LCA-tree representation.
A.3
k--Center in Ultrametries
A.3.1 Structure of a Center-Based Solution
We first describe how cluster memberships are defined in an LCA-tree. Recall that centers are placed on leaves and cluster is the of points which is closest center. Since many of the center-to-leaf relationships are equidistant in an LCA-tree, we use the "marking" procedure from [18] to define a consistent notion of cluster attribution.
Let C = [ct.... Cs] be l arbitrarily ordered centers that correspond to distinct leaves in the LCA-tree. We obtain the cluster memberships C, {e E T G, arg min.ge d(C, c)} by adding the centers in the given order and, for each center placed, marking the nodes in the tree from the corresponding leaf to its lowest unmarked ancestor. Thus, if we place center e; in a leaf node, towards the root and mark every node with "C," until we hit a previously marked node. Leaves are then assigned to clusters by finding their lowest marked ancestor. An example is shown in Figure 5a, where we first place a center in subtree Ti and mark every node on the path from the center to the root with Ct. We then add the second center in subtree T2 and mark along its path the root until we reach an already-marked marked node. We therefore have that the leaves in Ti UT3 belong to cluster C₁ and the leaves in T3 belong cluster C2.
go up the tree
Put simply, if a node y is marked, then there is a center in T[y]. We note that this attribution of leaves to centers applies in both the k-center and the (ks, -cllustring settings and is independent of the algorithm used to obtain the centers.
Interestingly, the number of optimal center-based clustering solutions in any LCA-tree is necessarily exponential in k. This is shown Figure 5b: the set of distances from leaves in the tree to e does not change regardless of whether we place es on C,, ly lx. When describing optimal solutions,
26

---

Ci
C
C1
C1
C
T
C
C2
T3
C
Tj T2
T
T
T
(a) A visualization of the marking procedure. We first place center ei and mark every node from it to the root. We then place center and mark every node from it to its lowest unmarked ancestor.
(b) The cost of the clustering does not depend on which leaf the cen- ter assigned to.
Figure 5: A visualization of how leaves get assigned to centers in the LCA-tree.
consider them equivalent up such swaps in the last layer of the tree. We discuss heuristics for choosing the "best" of these optimal solutions in Appendix C.1.2.
We lastly formalize the notion of hierarchical clusters:
Definition 4.1. (Lin et al. [48]) A cluster hierarchy H = (PI.... Pn) is a set of partitions where
for k 1: for < <hsn:
Pi L, and Pk = (Px-1 C2) U [Cj, such that (a) C; -C PA-1 with C, n 0, (b) Cj # C; and C + C₁ and (c) i #
In short, hicrarchical set solutions means that the clustering in Pk is the same as the one at Pk-1 except that a single cluster was split apart. We say cluster C₁ H if 3f H with C, P).
A.3.2 k-Center in I.AA-trees
now develop our center-based clustering algorithms LCA-trees, starting with the k-center clustering task. Recall that the k-center objective requires finding le centers that minimize
Co (T, C)
max min Ci. RET cEC
Using the marking construction, LCA-tree:
succinetly state the cost of any k-center solution in
Fact A.2. Let C be a set of centers in an LCA-tree T. Let be the most expensive marked node in T with at least one unmarked child. Then Costee (T, C) d(n).
Proof. We will show a bijection between the leaf- ceaf-to-center distances induced by solution C and the nodes which are marked and have an unmarked child. Since the cost of k-center solution the maximum over all such leaf-to-center distances, it will therefore be the maximum- valued such node.
First, we show that all leaf-to-center distances contained in nodes which are both (a) marked and (b) have an unmarked child. Let be any center C and let be any leaf that is closest to center c, i.e., e arg min.r d(e, c'). Let r c é. Then condition (a) is true of by definition of the marking procedure: notice that e V &, is marked for all leaves é, E T. To see why (b) is true, consider that if every child of 1) marked, then e could not have been the closest center (by Corollary 3.4).
It similarly holds that all nodes which marked and have unmarked child correspond leaf-to-center assignment. Le., any such node is marked, implying there is a center in T[n]- also has an unmarked child. Consequently, there leaf é T(y) whose LCA with the center-set is 1)-
Thus, the k-center cost equal to the maximum leaf-to-center distance. As shown above, this in turn is equivalent to the maximum value among nodes which are marked and have an unmarked child. D
27

---

Parthest-First Traversal. Although the k-center task is NP-hard in the general metric setting, Fact A.2 allows us solve it optimally (and almost trivially) in an LCA-tree using the farthest-fire traversal algorithm [32, 28, 31].
We implement farthest-first traversal in LCA-tree as follows. We assign the first center random leaf in the tree. For each subsequent center, we find the node whose value is equal to the cost of the solution (per Fact A.2). This node must have at least one unmarked child. We therefore choose one of these unmarked children at random and place the next center at a random leaf in it. We do this iteratively until we have placed centers. This is formalized in Algorithm 1. By Corollary 3.4, this algorithm will only place a center for the subtree at node if it has already placed center for the subtree at parent(n).
Algorithm LCA-tree Farthest First Traversal
Input: LCA-tree
1: Place first center on random leaf and mark T accordingly
2: while unmarked node exists do
3: 17s = highest value marked node with at least one unmarked child
4: while T7 has unmarked child my do
5: Place a center on random leaf in [my]] and mark T accordingly
6: end while
7:
end while
8:
Return centers
Lemma A.3. Let I be an LCA-tree satisfying the conditions in Corollary 3.4 and let l [n]. Then the farthest-first traversal algorithm finds the optimal k-center solution in T.
Proof. Let k be any value in [n 1] (if k: = n, there is only one solution which is trivially optimal). Assume for contradiction that the 'greedy' k-center solution C, which obtained by farthest- firstt traversal is not optimal. Then there must be another clustering C. of & centers that is actually optimal, i.e. Cost (T, C.) < 5o Cg). The two solutions must differ by at least one center placement and, consequently, the sets of nodes which these solutions mark must also differ. Let 1j be the maximum value node which is marked in C, but not in C.,
Since C. did not mark we have Costoe (T. C.) 2 d(parent(n)) 2 d(n) by Fact A.2 and Corollary 3.4. However, Cy has marked 1). Furthermore, for all nodes 1/' T with d(r'') > d(n). Algorithm 1 has necessarily placed a center in Tin (otherwise it would not have reached the state where it placed a center on T(r)). Therefore, we must have Costoo (T, Cg)) S d(n)). This gives the desired contradiction.
Interestingly, this correctness proof does not depend which leaf gets chosen as the center in subtree just that any leaf is chosen. Also, the solutions induced by this clustering are necessarily hierarchical:
Corollary A.4. Let [C....., Cr be the sets of k-center solutions obtained by Algorithm 1. Let the respective partitions be H. = (PI....,Pa) obtained by assigning all leaves T to their closest center in each solution. Then H satisfies Definition 4.1.
Proof. For 1 = 1, all leaves belong a single center. Now assume we have the farthest-first traversal solution C2 for some 1 < k < n 1 and are placing the next center Cx+1- This center will be placed in the subtree belonging to an unmarked node 7) whose parent is marked. Before placing Ck+ 1, all of T'm belonged to a single center in Cs per the marking procedure. After placing C all of T[z) belongs it. Thus, one cluster which was present in the C2 solution was split into two clusters.
Unfortunately, the naive farthest first algorithm may take O(n²) time to obtain all clusterings for k E (1....,,) n since, when placing center c, we may have to search through O(n) nodes to find the one with the high-st cost. However, we can improve this to Sort(n) time the time it takes to sort list of the ((n) values in the LCA-tree- - by noting that the nodes' values grow as we go up the tree. Thus, it is sufficient to sort the internal nodes by these costs and then place their corresponding centers in that order. The following lemma formalizes this intuition:
28

---

Lemma A.5. There exists an algorithm that performs farthest-first traversal in an -rA-tree in Sort(n) time.
Proof. Before providing the algorithm, we first give overview of the ideas which facilitate it. Assume we have placed l centers and are placing the k-th one. If the cost induced by node 7) then this means that at least one of 1)'s children is marked and at least one is unmarked. Let 1) be the marked one and The be the unmarked one. We must therefore place center [hu in order to shrink the cost induced by d(n). We refer to the leaf where this center will be placed as 1j corresponding center.
Thus, our algorithm must separate the nodes in the tree into two components. Either a node gets marked when center is placed in its parent's subtree or it will have center placed its subtree. This partitioning is accomplished by Algorithm 2: at given node Algorithm 3 assigns 7/'s corresponding center as the corresponding center its left-most child. For 1j's remaining children, we store their value in global dictionary. Algorithm 2 finally returns the dictionary of nodes in the tree and their values. This requires single depth-fire first search and therefore Algorithm runs (m) time.
Given the output of Algorithm 2, we have list of all the nodes whose corresponding centers must be placed. We now notice that, when placing the k-th center in accordance with the cost d(z)). we have necessarily placed the centers with respect 17's parent (per Corollary 3.4 and Fact A.2). Thus, we can simply sort these nodes by their costs and place the corresponding centers in this order. This is done by Algorithm and runs in Sort(n) time.
Algorithm 2 CorrespondingCenters
Input: node 1) in an LCA-tree; dict Costs mapping nodes to distances; dict mapping nodes to corresponding centers
1: if v7 is leaf then
2: c(n) =
3: Return
4: end if
5: 0
6: for nf' children(1)) do
7: CorrespondinCCenterssry Costs)
8: if ChildCount then
9: c(z) = c[//]
else
11: Costs 1n'1 = d(n))
end if
13:
ChildCount += 1
end for Return
15:
Algorithm 3 U.trametric-KKenteer
Input: LCA-tree 7 Costs, e= ),
2: CorrepooniinCCettereeccCCCC
Costs, c) // assume rasf-be-eeference 3: Costs = OrderedDict(Costts)) // sorted from largest to smallest
4: for 7) Costs do
5: Place center at c[r]
6:
end for
In this sense, the hierarchy optimal k-center solutions essentially isomorphic to the LCA-tree. Lee in the k-center hierarchy, the costs are precisely equal to the values of the nodes and we place centers which correspond to nodes ordered by their value. Thus, given a binary LCA-tree, k-center hierarchy is necessarily equivalent to it.
29

---

Together, Lemma A.3, Corollary A.4 and Lemma A.S prove the following statement about k-center in LCA-trees.
Theorem A.6. Let T be an LCA-tree satisfying the conditions in Corollary 3.4 and n be the number of leaves in T. Then there exists an algorithm which finds the optimal k-center solutions [Cl..... Cn) for all & E N,, in Sort(n) time. Furthermore, the respective partitions H. (PI...... pn obtained by assigning all leaves in T to their closest center satisfy Definition 4.1.
We lastly note that this runtime tight:
Lemma A.7. Let T be an LCA-tree satisfying the conditions in Corollary 3.4. Then there a worst- case instance on which one cannot find all the optimal k-center solutions on I for k E {L...., n in faster than (ort(n) time.
Proof. Consider rooted tree that is complete and balanced: every leaf is at the same depth, and every internal node has two children. Let the leaves all be at depth w; so that there are 2 leaves. Starting depth w, assign the leaves' unique values from to 2 Then, for the nodes at depth assign them unique values from 2 + to 2" + 2 Continue this process until we reach the root node, to which we assign value 2"+1, As result, we visit the tree's nodes one-by-one from the lowest level to the root and maintain a counter of the number of visited nodes, Each node is assigned the value of the counter when it is visited.
1,
Labeling the nodes by these values necessarily gives us an LCA-tree: all values are non-negative, and values non-decreasing along paths from the leaves to the root. Furthermore, all internal nodes at depth have distinct values. Suppose we are now performing k-center and have placed centers for all the nodes depth w but have not yet for the nodes depth w. There are, therefore, (n) available nodes on which to place centers. Of these, only one has the maximum leaf-to-center distance and therefore induces the cost.
Thus, we cannot place the remaining (n)) centers faster than the time takes to sort the remaining leaves' parents by their costs.
A.4 (k, cluusteng in LCA-trees
The result for k-center essentially boils down to the speed and optimality the classic 2- approximation when applied in an ultrametric. We now turn to the more interesting result that the optimal (k, 2)-clustering solutions behave very similarly to the optimal k-center ones:
Theorem A.8. Let be an LCA-tree satisfying the conditions in Corollary 3.4, be the number of leaves in Т, and z be any positive integer. Then there exists an algoritium which finds the optimal (k, 2)-clustering solutions { (Cl...., C.) for all E N, in Sort(n) time, Furthermore, the respective partitions H -PI,.... Pn) obtained by assigning all leaves in T to their closest center satisfy Definition 4.1. I. are hierarchical.
A.4.1 Optimal (k, 2) Centers in Subtrees.
We start by considering what happens when we have (k- 1, =,lusctug solution in an LCA-tree and place the k-thh optimal center. Placing this center will create a trail of markings from the leaf up until the first marked node along the path to the root. The key insight which will utilize is that this center is necessarily optimal everywhere along this trail:
Lemma A.9. Let C₂ = (TT,,,(T) be an optimal (1, cllusterii solution for LCA-tree T. Then for every subtree I' C T such that c2 E T', C2 is an optimal zclussttnnii solution for TV.
Proof. We show this inductively. The base case is the trivial LCA-tree of one node where, inherently. the only choice of the center optimal, and there are no subtrees. For the inductive case, consider LCA-tree 7 whose root has l children, such that each child has an optimal center placed within it. Our goal to show that if we were to have one center for all of the optimum would be one of the A centers in its subtrees.
If we only had one center place for all of T. that center must be in one of its subtrees. WLOG, let the optimal center for T be in the subtree Ti. Thus, our cost for one center is necessarily of the form cost, (T)) cost, (Ti) + E [Tal d(root(T))). where [T]] is the number of leaves in
30

---

the i-th subtree of T. By the inductive hypothesis, we already had an optimal center for subtree Tr implying that cost, (Ti) is minimized by choosing the optimal center in Ti. The other term Σx [Zil- d does not depend on where in I'i the center is placed. Therefore, the optimal center from 7i remains optimal for T.
The key thing to note about Lemma A.9 is that it must also apply to all internal nodes of an L.A-ttre. I.e., suppose we place an optimal center with respect to the unmarked subtree T C T. Since TV unmarked, Lemma A.9 holds for T", Consequently, every internal node in the LCA-tree has an optimal center (leaf) associated with it. We give this its own definition:
Definition A.10. Let T be an LCA-tree satisfying the conditions in Corollary 3.4, let 17 be node in T, and let & be a positive integer. Then 1)'s corresponding z-center is c2 (1) = (PT,,
Lemma A.9 the key property of (k, cluustrri in ultrametric spaces that makes the entire proof go through. To illustrate its effectiveness, consider the Euclidean 1-means setting on a dataset of two clearly separated clusters. The Euclidean mean falls between the two clusters. In contrast, Lemma A.9 says that, in the ultrametric setting, the optimal 1 1-means solution is not only located within one of the two cluster, but that it is optimal for the cluster which is located. practice, this means that after placing an optimal center, we can essentially forget about it it is guaranteed to be optimal for any set of points it serves.
Overview of Proof for Theorem A.8. We now give simple blueprint illustrating how we use this for fast, optimal (k, cllusternng Assume we have placed the first center and have left a set of nodes unmarked. For each such unmarked node, we can determine its optimal center as well as how much the subtree's i (k, 2)-clustering cost would decrease by placing this center. Curiously, application of Lemma A.9 shows that these cost-decreases themselves satisfy the strong triangle inequality. Another application of Lemma A.9 then allows to show that greedily choosing the maximum cost-decrease gives an optimal (k, 2) cllustering solution in an LCA-tree. As a result, we can apply a variant of the k-center algorithm the LCA-tree of cost decreases.
Notation. We require additional notation to simplify the presentation. Let define the cost of node as
NodeCost(y, z) = [T]r]] ((parent(7))",
where [Tin]] is the number of leaves in the subtree rooted at 1j. This represents the cost contributed by 17's leaves when 1) is unmarked, but its parent is marked. In essence, this is the cost of T[n in (k, ccclusteinggg solution if there is no center in T[n). Similarly, we define the cost decrease 17 as
CostDecreeaee 2) NodeCost(1,, (1,, 2) Cost(T(n),.=(n))
where Cost(T(n) (=)) (tElewes(())) d(e, c2 (n)) Here, (z(1) is rj's corresponding z-center. We define the cost-decrease of the root node to be infinite.
In essence, the cost-decrease quantifies how much placing an optimal center in T[n] would decrease the subtree's total cost. Importantly, the cost-decrease of a node n assumes that parent(1) - the node directly above 77 is marked. We will see in Lemma A. that this is reasonable assumption: every useful center we will place in the (k, cccusterg setting will always have a marked parent.
A.4.2 Proving Theorem A.8.
First, we see that all of the corresponding z-centers can be found in O(n) time on an LCA-tree:
Lemma A.1I. Let T be an LCA-tree satisfying the conditions in Corollary 3.4. Then there exists an algorithm which, for all E T, finds e₂ (n) and Cost(T [T), cz(n)) in O(n) time. Furthermore, this algorithm stores the cost-decrease for all nodes of for which e, (1/) + e, (parent(y/)).
Proof. This is accomplished by Algorithm 4, which is essentially a depth-first implementation of Lemma A.9's proof.
31

---

Algorithm 4 Correspondingg--enttee
Input: node 7) in LCA-tree; diet Costs mapping nodes to their dict CostDecreases mapping nodes to their cost decrease; dict c₂ mapping nodes to their corresponding---center
1: if is leaf then
2: C2 |n 7
3: Costs( = d(n)
4: Return
5: end if
6: if is root then
7: ParentDist = d(n) +
8: CostDecreases(7) 20
9: else
ParentDist d(parent(n))
11: end if
12: SumOfCosts = y Echildren(()) [T d(n)
13: CostlfChosen (v/: 0 for r/ E children(n))
14: ChildCossDeerrases = [r/:: for r/ E children(n))
15: for r/ children(1)) do
16:
Dorrespondingg--eeeteeee
Costs, CostDecreases, c2)
17: CostlfChosenfy// SumOfCosts - [T[n'] d(n)) Costs(n']
18:
19: end for ChildCostDecreases/ ry') Tin ParenttDst CostlfChosen
20: ChosenChild arg max maaliidlsssssDeerrssssss
c2 in] c2 [ChosenChild]
22: Costa(n) CostlfChosen| [CsseCChossee
23: for v/ children(1)) such that vf is not ChosenChild do
24:
CostDecreases
[v']l d(rr)
25: end for
26: Return
We prove by induction that Algorithm 4 finds the costs for all internal nodes. In the base case, our current node 1) is a leaf. Thus, 77's corresponding z-center is r and the cost of to this center is simply d(r)..
We now essentially reuse the logic from Lemma A.9 to prove the inductive step. We begin the inductive step with node 7) along with the costs and corresponding z-centers of each of 1n's children. That is, for all v/ E children(1) (1),, we have access to both c₂ (z)) and Cost(Tin'),ca (n)')))) We now seek the optimal center for 7) and what the cost would be in ['nr] after placing this center. By Lemma A.9, we know that the optimal center for is one of its children's 's corresponding z-centers. I.e., C2 (n) must be equal c2 (r)') for
of the children 17'. We, therefore. test what the would be if placed the center at each of the children and chose the minimum. By Lemma A.9, this center must be optimal. We therefore record the cost of placing this center 1). concluding the correctness proof.
Since this is done by depth-first search, the algorithm runs in O(n) time.
Rather than thinking about corresponding z-centers as those which minimize the cost, we will instead think of them through the equivalent notion of the centers which maximize the cost-dccrease. The next lemma shows the peculiar property that these cost-decreases themselves form a relaxed ultrametric:
Lemma A.12. Let be an ultrametric LCA-tree which satisfies the conditions Corollary 3.4 and let T be the LCA-tree obtained by replacing all values in T by the cost-decreases. Le., for all nj E T', d(n) CostDecrease(yy 2). Then, the ACA-distances over T also satisfy the conditions in Corollary 3.4.
Proof. By Corollary 3.4, showing that T' satisfies the strong triangle inequality simply requires verifying that the cost-decreases are non-negative and monotonically non-decreasing along any leaf-root path in I", We first show that they monotonically non-decreasing.
32

---

Let be an unmarked node with h children whose parent is marked. We now place the optimal center c₂ in T(n]. WLOG, this center must land in one of 1j's children's 's subtrees. Call this child Te- implying that (2()) = ez (nc). We now show that the cost-decrease of is greater than or equal to the cost decrease of Te by separating CostDecreaseen) 2) into sum of terms, of which Me is subset:
CostDecrease(n: 2) = NodeCost(y, 2) cost(((n),
[Tmme]l d(parent(n))* +
Σ
[T]] d(parent(n)))
n (children(() rf f%
cos)(T())..=
[T|eell d(parent(n))* +
Σ
|T (n))
of Echildren(n) n tne
(ost((((nel..(n))
E
Echildren(n) Anc
NodeCost(Mcc 2) +
Σ
|T/7'l d(parent(r))*
nf E'hhilrrenn() 1/ +n
Cos)(T
Σ n (childrren(n) nf f'
(NodeCost(ne, 2) CostCoTosleleeccm (x)))
+ Σ
|TMn'l (d(parent(1))) d(n)))
nf (children(()) 7f A1o
Cost 2) +
Σ
|4 (d(parent(n))= -d(r)²)
nf Echildrenn() 1/ fn
CostDecrease(Mes22 2),
where both incqualities are due d(parent(7)) CostDecrcase(1) 2 CostDecrease(r") where v/' * Te is any other child of n, This is by transi- tivity, since CostDecrease((p)) 2 CostDecrease (r)) by Lemma A.9. Thus, the cost-decreases are monotonically non-decreasing along paths from the leaves to the root.
d(r)). It must also be the case that
It remains to be shown that the cost-decreases the fact that the original distances T are non-negative. Since we already know that they are monotonically non-decreasing, leaf is non-negative. To this end, let & be any leaf. By Corollary 3.4. Then CostDeecrease (f, 2) NodeCost(E,, 2) cx However, Cost(T]f),, d(parent(() (t)). Thus, CostDecrease((,: =) 2 d(parent(() d(f) 2 0.
necessarily non-negative. For this. rely
must only show that the cost-decrease of placing center at
d(l) while NodeCost({, >
We note that the cost-decrease at leaf & is not necessarily 0, meaning that the L.CA-tree of cost decreases not an ultrametric (but still a relaxed ultrametric). This why we required the definition of relaxed ultrametries rather than standard ones.
33

---

The next lemma shows that not only do these cost-decreases satisfy the conditions in Corollary 3.4, but they are also monotonically increasing all relevant settings. In other words, if ['m has non-zero cost, then placing a center there decreases this cost by non-zero amount.
Lemma A.13. Let T an ultrametric LCA-tree satisfying the conditions in Corollary 3.4 and let be positive integer. For any leaf & E T, let plE) = [e, 2..1;-.. . ,i, "");, be the path from &
to the root. Then for all mi 112 E p(() such that d( > 0. 1 1 122
CostDecrease(m)) <
CostDecrease(mz))
Proof. By Lemma A. 12, we know that the cost decreases are monotonically non-decreasing along paths to the root. Thus, it remains to show that the cost-decrease at node 7) is non-zero if d(111) 0.
To do this, we first decompose the cost-decrease at ry:
CostDecreaae(m1) NodeCost(m) - Cost(T( cz()))
[T]m]] d(pprenn(nn)) CostCo cz(m))
d(parent(m))
Σ
[WW]]
Cost(T(m))
xf' E'children(())
Now, let Me be the child of ?h containing c₂ (71). Much as in the proof of Lemma A.12, rewrite the above in terms of the costs in Te and the costs in the other children:
CostDecrease(m) d(paren((m)))
[Thne]
Σ
IT(1'I1
of d'Echildren(m)) 7no
-Cos(((mm)cccmm)) -d(m))
Σ |T///]1
rf (children(n))) of 2%
Σ
|T(171
(d(pprent(m)) d(m))
E'Echildreen()))
n'tne
((parent((n)) [nc]]] (ne)
d (parent(m)) (n:)) (pprent((1))
[T[nc]] (os((T(ne)..c(mm))
[T[me]
VV d(m)) (T[eel
where the first inequality is by the fact that d(n)) S ((parent()))) the second due to the fact that the costs strictly non-negative, the third is by the fact that d(parent(m:) d(11). and the fourth inequality is by the assumption that d(m) >
Lemma A. allows us address the fact that the cost-decrease at node 1) was defined under the assumption that 1)'s parent is marked. By Lemma A.13, the cost decreases are either strictly increasing along paths to the root or are Thus, if two nodes have equivalent non-zero cost-decreases, their subtrees must be disjoint. As result, when we go through the nodes sorted by their cost-decreases, will always be the case that the next node we place will either have its parent marked will have cost-decrease of 0 (in which case it is irrelevant in terms of the optimal solutions).
We finally move our last lemma, which shows that greedily maximizing cost-decreases results in an optimal (k, z) -clustering over the LCA-tree.
Formaaly, for two nodes 1/2 E T with CostDecrease (m) > 0 and CostDecrease(nn) > 0, we have that CostDecrease(p)) CostDecrease(pp) T'ml n T 0.
34

---

Lemma A.14. The optimal (k. 2) cllustering solution over an LCA-tree can be obtained by greedily choosing the centers that, at each step, maximize the cost-decrease.
Proof. We show this by contradiction. Consider that there is a solution that was obtained greedily and another, different one that is actually optimal. We now map every center in the "optimal" solution to its closest center in the "greedy" one and observe how the optimal solution's 's cost changes. There are two cases that can occur: either all of the greedy centers receive one optimal center each, or there is at least one greedy center that receives more than one optimal center and another that receives none.
We start with the case where each greedy center Cg has one optimal center Co mapped to it. By definition, Co must be in the set of points that are assigned to cg. Thus, it is either (a) in T[c or (b) in another subtree whose parent was marked by Cg. In case (a), Lemma A.9 states that the greedy algorithm must have chosen co. In case (b), by the greedy algorithm, T'(y]] has greater cost minimization than T(c.]. Thus, we can decrease the cost of the optimal solution by replacing Co with cg. giving a contradiction. Therefore, we conclude that if one optimal center was mapped to each greedy center, then the solutions must be equivalent.
remains to consider the case where more than one optimal center was mapped to a greedy center Cg- WLOG, let there be two optimal centers c) and oi that are mapped to cg. By a similar argument as above, Cg must be the same as of these optimal centers, i.e. Cg c/. By extension, cg o Cg. Now consider the greedy center elsewhere in the tree that had no optimal center mapped to it. Call this center ly This means that the greedy algorithm had both T(c) and T((y] available to it but chose T[c]]. Thus, CostDecrease(T < CostDecreeae (T(e We can therefore decrease the cost of the optimal solution by replacing center e with center og. This gives the desired contradiction.
This brings us to the primary result of this chapter, restated from before:
Theorem A.8. Let T be an LCA-tree satisfying the conditions in Corollary 3.4, n be the number of leaves in T, and z be any positive integer. Then there exists an algorithm which finds the optimal (k,, =-clussreig solutions (C)...., ..,) for all E N, in Sort(n) time. Furthermore, the respective partitions H = (PP,.... Pa) obtained by assigning all leaves in T to their closest center satisfy Definition 4.1. are hierarchical.
Proof. We use Algorithm 4 from Lemma A.11 to find the cost-decreases for (k, clcuustein in the LCA-tree. By Lemma A.1 these satisfy the strong triangle inequality. Furthermore, by Lemma A.14, greedily choosing centers that maximize the cost-decreases gives an optimal (k, =)clusterrnn
Thus, running farthest-first traversal on the cost-decrease I.CA-tree will give the partitions for (k, 2)cluusring solutions. This guarantees that the corresponding partitions are hierarchical.
However, we must be careful about where we place the centers: while running naive farthest-first traversal on the cost-decrease LCA-tree will give the partitions of the optimal (k, 2) cllustrrnn solutions, will not necessarily give the optimal centers. This is due to the fact that the farthest-firs traversal is optimal regardless of which center we pick for every subtree. Luckily, we have already addressed this. When considering the LCA-tree of cost-decreases, we have a mapping between every cost-decrease and the center that induces it. Thus, we will perform the farthest-first traversal by placing the nodes' corresponding z-centers. This ensures that both the partition and the centers align with the optimal (k, =)-ccsttrinngg solutions.
Putting this all together, our final algorithm - Algorithm 5 is quite simple. We first run Algorithm 4 to return list of nodes and their cost-decreases. Importantly, Algorithm 4 returns only the cost- decreases for those nodes o/ with c, (n') & e₂ (parent(r))). We then sort this list in Sort(n) time. By the discussion after Lemma A.13's proof, we can safely go through this list and place the nodes' corresponding z-centers: the nodes with non-zero cost-decrease will always have their parent marked. The nodes with zero cost-decrease come at the end of the sorted list and do not affect the optimality of the solution. By Lemma A.9, each corresponding z-center is immediately optimal in every node that it marks. Thus, Algorithm 5 optimally solves the (k, cclusterii objective in LCA-trees which satisfy the conditions in Corollary 3.4. The bottleneck in this algorithm remains the time to sort the Onn internal values in the LCA-tree.
35

---

Algorithm 5 Ultrametric-kz
Input: LCA-tree 7
1: Costs, CoatDecreases, c; 0000
2:
Costs, CostDecreases, (2) pass-by-reference
CostDecreases OndereiDictCCostDeereess
4: for CostDecreases do
5: Place center (1)
6: end for
Together, Theorems A.6 and A.8 prove Theorem 4.2 from the main body of the paper.
B Further Details for Section 5 Choosing Partition
B.1 Ultrametric Elbow Method
160)
P
k=
[c
k=2
k=
k=4
H
Ci
13
C1s
P [C
belongs to
CC Overlapping
culy
13
C
Figure 6: Left: an example hierarchy 7 (P1. P2.... .): P' E H is then an example partition which belongs H. Right: p" is not partition since Eg and Eg each belong clusters C2 and C5-
We begin by quickly showing Corollary 5.1, which holds as a direct consequence of Lemma A.13 13 in Section A.4:
Corollary 5.1. Let P and L correspond to the n partitions and losses obtained in accordance with
Theorem 4.2 for the (ks, z)-clustering objective. Let A, Li+1 L,. Then either A Ai+11
or A. = Ait1 for all i [1]
Proof. Lemma A.13 states that the cost-decreases associated with nodes in an LCA-tree mono- tonically increase along paths from any leaf to the root are all O. By Lemma A.14, we solve (k,, 2) cluustrtg using farthest-firs firsstttttttttttttee traversal over the LCA-tree of cost-decreases. Le., we start the root and greedily pick the cluster that gives the maximal cost-decrease at that step. Consequently, each cost-decrease we pick must be smaller than the previous one.
Thus, let A/- - A By Lemma A.13, we have AL > A 2 0or A. = A841 0. Plugging in = completes the proof.
Choosing the elbow Although there many methods for finding the elbow index, we are in the privileged setting where a single elbow exists and clearly delineated. Inspired by Shi et al. [68], we simply define the elbow as the index where there most strongly appears to be right angle. Namely, let T2 (i, L.) be the (I, y) position of the i-th point in the elbow plot. Then, for every index & E {2.... define the elbow as being at the index i where 0z is closest to 90 degrees. Since Theorem 4.2 gives us all of the partitions for l E (1...., simultaneously, this index can be found ((n) time given the cluster hierarchy.
1). let 02 be the angle induced by the vectors (ō1 Tx) and (øx T,). We
In practice normalize the values and the costs to be in [0, 1] that the scales comparable.
36

---

10
08
8..
04
500
1000
1500
2000
2500
3000
Figure 7: The same elbow plot as Figure with values of & from to n. The chosen elbows are higlighted with circles.
We note that Figure only plots the elbow curves for values of l up to 100. This is because plotting until & = n makes the plot look in practice like vertical line followed by horizontal line, seen Figure 7. However, we use all values from 1 to n when choosing the elbow.
B.2 Agglomerative Clustering Algorithms under our Framework
Corollary 3.4 and Theorem 4.2 imply that a large set of agglomerative clustering algorithms can be interpreted k-center over various relaxed ultrametrics. As example, consider the complete linkage algorithm [41]. Here, one starts with every point in its own cluster and recursively merges those clusters C. C, which have the smallest merge distance arg minc,.c, ea,x,,CC,,,,6 d(x;, 4;)) Importantly, with each subsequent merge, the merge distances Thus, by Corollary 3.4, labeling each cluster the hierarchy by its merge distance gives us relaxed ultrametric and, by Theorem 4.2, k-center over this ultrametric gives the complete-linkage hierarchy. Indeed, this is true any agglomerative clustering method where the merge distances progressively grow as we approach the root cluster.
monotonically non-decreasing.
B.3 Thresholding
We quickly explain how one can partition cluster hierarchy by thresholding. We assume that the cluster hierarchy H has every internal node labeled by its cluster's cost. As discussed in the main body of the paper, this constitutes a relaxed ultrametric.
Now let be any threshold value. We can return the set of clusters that have cost less than by depth-first search in ((n) time. This is precisely what DBSCAN does on the de-dist relaxed ultrametric. Namely, DBSCAN* returns clusters of core points that are within e of each other under the de-dist. Under the de-dist's relaxed ultrametric definition, this is specifically the set nodes with value less than
B.4 Cluster Value Functions
The idea generalization the excess-of-mass measure in HDBSCAN: have user-defined function v(C") which assigns non-negative value to each cluster in the hierarchy. Le.,, v(C' 2 0 for all clusters H. Then the best partition maximizes the sum of these values:
Definition B.I. Given value function v, we define the best partition under as the partition that maximizes the sum of valuations. Lee P.(HH) arg maxp belonging to H Σcep (CC).
This brings us to the following result:
Theorem B.2. Let H. be cluster hierarchy. Let v be function such that, for all C E H. v(C) can be obtained in (1)) time. Then there exists an algorithm to find the best partition (H O(n) time.
37

---

Proof. The algorithm for finding the best clustering is essentially Algorithm from Campello et al. [12]. We provide our own version
Algorithm for completeness" sake. 10 It works by depth- first search where, at each node, we simply calculate its value and compare it against the sum of the values of its children. Since calculating the value takes O(1) time and there are ((n) nodes in the cluster hierarchy, the algorithm therefore runs in (n)) time.
We prove its correctness inductively. In the base case, we have a single leaf whose best clustering is simply the leaf itself. In the inductive case, we are given a cluster C' in the hierarchy and have the best clusterings C's children. We seek to find (C) By the non-overlapping requirement, if we include C' in (C). then we cannot include any of its children. Similarly, since the values of the children are non-negative, we include one child, then we may as well include all of them. Thus, B, (C') is either {C} or {C" : C' Children(C'),
Algorithm 6 BestClustering
Input: node C' in cluster hierarchy; Output: the best clustering under this node B, (C), the value of the clustering v(C);
1: if C' is leaf then
2: (C) = {C}
3: Return (C(
4: end if
5: ChildValues = 0
6: ChildClusterings
7: for C" E children C*) do
8: (C","), BestCsssttttin
9: ChildValues += v(C)
ChilCChuseringsaapeendBBBBB (B,
11: end for
if (CC) ChildValues then
13: Return {C}, vCC)
end if
15:
Return ChildClusterings, ChildValues
The stability cluster value function. We now introduce the stability cluster value function from Campello et al. [12]. Let C' be any cluster in a hierarchy and let C" be C's parent in that hierarchy. Then the stability objective can be roughly phrased as the following:
(CI))=IC--(
(I)
I(C")
We note that our description of the stability criterium differs slightly from the original function discussed in [12, 13, 53). Namely, omit here the notion that singleton points may fall out of the clustering as is not easy to represent in our notation and the differences are negligible for the purposes of this discussion. Our implemented stability criterion the original (correct) one. For full discussion of the original function, we refer the reader to the referenced literature.
In either case, the stability value function be interpreted as emphasizing those clusters that have large number of points and have significantly lower costs than their parent. While we find that the produce sub-par partitions when applied in the (k, 2) -)-llusteinng hierarchies. This is because the per-point cost in the (k: -clusteri task comparable the per-cluster cost in the k-center objective.
stability criterion performs well in the k-center hierarchy.
To be consistent with the literature [12], we utilize the stability cluster value function in the noisy setting. Given user defined parameter μ representing the minimum cluster size, we first prune the tree so that all nodes with fewer than μ children are removed. We then run the stability value function over the remaining points. This selects set of internal nodes represent the clusters. Finally,
Note, we write (C) refer the best clustering of the cluster hierarchy rooted at C.
38

---

re-introduce the points which were pruned away. If the re-introduced points are in the sub-tree of cluster, we assign them the cluster. If. instead, they are not below a cluster found by the stability function, we label them as "noise".
B.5 Further details on the de-dist ultrametric
We begin by proving Proposition 6.3:
Proposition 6.3. Let (L, d²) be metric space. Then, the de-dist over L is a relaxed ultrametric.
Proof. Note that it is known that the minimax distances Thus, we have that (d) = d(ez.E) ()) and that (), 2 0 for all f, Ez-
space constitute ultrametric [26].
To show that the dc-dist is relaxed ultrametric, we will leverage that the only difference between it and the minimax distance is that the minimax distance of a point to itself is while the dc-dist of a point to itself is its mutual reachability. Thus, we will prove that the dc-dist is relaxed ultrametric by showing that the distance to itself is non-negative and that it inherits the arooggtrianghe inequality from the minimax ultrametric. Together, these imply the two properties for Corollary 3.4.
First, note that dde (.) = max(|14, &ell, ky (4x), (4)) = max(0, Ky (4.) = (f,)) Thus, the dc-dist of a point to itself is the distance of é, to its f-thh nearest neighbor in the ambient metric. This is necessarily non-negative. Similarly, the retual-reacsaaiilttes for any other pair of points are also necessarily non-negative. Because the dc-dist is the minimax distance over the pairwise mutual reachabilities and the pairwise mutual reachabilities are all non-negative, the de-dist must also be.
Let us now show that the dc-dist satisfies the second property of Corollary 3.4. First, notice that the dc-dist of point to itself is necessarily less than or equal the dc-dists of that point to any other point in the set, i.e.,
E,) S max(dae (d E2), daele,, (+)) for all é,. To see this, consider the mutual reachability of Eg any other point E, necessarily greater than my (C,, &,). Namely, (4, E2) max(d' d" (e,, (x.. (e,)) 2 (4.). As a result, any step in the mutual reachability MST that originates E, will be least as large as (b., dde(ee, l.). Put simply, point's closet point under the dc-dist is itself. Pairing this with the inheritance of the strong triangle inequality from the minimax distance gives us the second property of Corollary 3.4.
Thus, we have shown the two properties for Corollary 3.4: the de-dists are non-negative and are non-decreasing as we traverse the DC tree from any leaf to the root. Consequently, a relaxed ultrametric.
Relationship DBSCAN and HDBSCAN. First, Campello al. [12] showed that one can obtain DBSCAN* partitions using the single-linkage hierarchy over the mutual reachabilities. Rephrasing into this paper's notation, they showed that one can obtain DBSCAN* embeddings by thresholding the de-dist's LCA-tree at a user-defined value E; i.e., removing all nodes 1) in the LCA-tres with d(n) E. Subsequently, Beer al. [6] proved that k-center can be optimally solved over the dc-dist and that these partitions correspond to single-linkage over the mutual reachabilities. In this sense, one can think of k-center on the minimax distances as equivalent to single-linage clustering. Lastly, Campello et al. [12] showed that, given the dc-dists's 's LCA-tree, one can choose a partition from it by optimizing the EoM cluster merging criterium over the pruned tree.
C Runtime Speedups Efficient Operations
We now give an overview of how we implement the theory from Section A.3 and A.4 in practice in our codebase. We assume that we have already computed an ultrametric so that queries to the ultrametric require (11) time. From this, we describe how we build an LCA-tree, how to transform to other clustering hierarchies, and how we extract partitions from it. We center this discussion on the de-dist's dc-tree as a point of reference since we believe that this is the most common use case of our framework. However, we note that the discussion applies immediately to any relaxed ultrametrie.
C.1 Building and utilizing the hierarchy efficiently (theoretical complexitie)
The overall structure of our implementation is the following:
39

---

1. Building the hierarchy
(a) Compute annotations of cost-decreases over the de-tree bottom up. These contain information that we will use for creating hierarchies.
(b) Sort the annotations.
(c) Create the hierarchy in a way that takes O(n) time utilizing the parent pointers in the annotations and in in-place pointer updating.
2. Get each solution in (
(a) Annotate each node in the tree with the k that resulted in creating this node, given that the k-th center is chosen.
(b) Top-down (or bottom-up) algorithm that cuts all edges in the tree going from k- annotation > k to k-annotation S k. The result is all nodes above the cut.
(c) Small edge case to deal with for nodes with > children.
3. Initialize smart pointer access to the leaves in the tree so that internal nodes can get their leaves in constant time.
C.1.1 Building the new LCA-tree of cost-decreases
How we build the tree in (n log(n)).
Two main functions:
Annotate tree
Create hierarchy
Annotating the tree
'Annotate tree' creates the annotations for each internal node in the tree. Each annotation is the
following: Aş = [cost_decrts decrease, center, parent _ponttrrr tree gree_ndee..
Idea C.I. Only maximal annotations for given center will be picked with the greedy algorithm.
By maximal annotations, we mean those highest in the tree corresponding to specific center, i.e., the annotation for that center with the highest annotated cost-decreases. To see this, consider that only maximal annotations will be children of marked paths of other, already picked, centers in the tree.
Idea C.2. The cluster corresponding to the parent center p' of the maximal annotation of is exactly the cluster/set of points from which choosing p will exclusively take points.
This comes from the fact that each annotation is maximal in its corresponding subtree, which means that the maximal subtree above always will have chosen that center first. Also, any other center v" chosen within that subtree of the maximal annotation of p' will have taken disjoint points from that center p''s s cluster that cannot otherwise a contradiction and p" should have been the parent annotation of
We formally define the parent center as the single center solution that contains all points of the k'th center, which will get assigned for k. We now get the following insights needed to make building the tree efficient:
1: We only need to store one annotation for each center, where we just store the highest best annotation cost-decrease for that center. This be updated the annotations are computed. 2: Each annotation/center can contain a pointer to the parent center.
Having these, now have all the information required to build the tree for each center, have exactly the cost-decrease corresponding to picking it and the parent center. We can sort the list of annotations, and each k solution will correspond to the first k centers picked in that order.
Building the tree from the annotations
First, we sort the annotations. Picking the first annotation corresponds to the root node and cluster of all points with that center. Picking subsequent new center will always correspond to a split the tree, splitting up the parent center's cluster. One side of the split will be what is left over from the parent cluster, and the other side will the new cluster for this k. The only caveat is that if there multiple, some number annotations with the same cost-decrease and parent, only get +
40

---

nodes from this multi-split. We get a node for each of the new centers and the a + I'st node for what is left over in the partition of the parent node's cluster.
Now, the key is that the cost-decreases are decreasing in the sorted order. This means that any subsequent annotations with parent that already has been split up will always create a new split at the lowest possible node/cluster corresponding to that parent center, and all nodes above that also correspond that parent center will never get new splits from them. This means that we can maintain for each center the current lowest/active node, which will be where any new center pointing to it should split from. This can easily be managed within the annotations with pointer that is updated as the tree is created.
The steps are then generally the following at given k th annotation for some center ej in the traversal of the sorted list:
Case 1: If the parent node p corresponding to some center Cp has no offspring, add two new nodes below. One for the new annotation and y/ for the old center representing that nodes have been taken from it. For the new node for Cj. update the annotation to point to it.
Case 2: If the parent p already has offspring associated with a higher cost-decrease, then add the new split nodes below p' that then have to exist as that other offspring will have created that in case Update the parent center's annotation now point to p' instead of p. as we can now be sure everything pointing to that center should never be added to but instead to p' or further below at a later point. For the new node for Cg. update the annotation to point to
The other offspring of the parent node has the same cost-decrease associated with the current annotation. This means the p' has already been created, just add singular node as a child of p corresponding to center Cj. For the new node for Ck. update the annotation to point to it.
Case 3:
Complexity Computing the annotations is single-pass bottom-up algorithm over the tree that does constant work in each tree node. As there are (n) nodes in the tree, this step has a worst-case complexity of (nn)
Sorting the list of annotations has a worst-case complexity of O(n lo)(n)) as there are n annotations to sort.
Computing the tree from the sorted annotations does single scan over the list of annotations, with constant work in any iteration and, therefore, a worst-case complexity of (()).
Therefore, the total worst-case complexity is O(n (on))))
C.1.2 Optimizing the tree: Resolving ties better
An important observation is that due the number of equidistant points under the relaxed ultrametric, many centers will often have tied distances to points between them. For example, consider that we have placed our first center ej and marks every node along the path to the root. Now let there be two subtrees Tj and T3 which are not marked but whose parent node is marked. We now place a center C2 in T. This creates a new path of markings that stops at the root of T;,
Now notice that every node in T, is equidistant to center ej and to center C2- Thus, we can leave T, assigned to CI, or can re-assign it to c22 and the cost remains unchanged. Over the course of placing & clusters, there will inevitably be many such ties, implying that there are an exponential number of optimal solutions!
The previous theory described this setting by simply utilizing a "first come, first served" principle and never re-assigning points to new clusters. However, under the de-dist and other minimax path distances, this may result in unintuitive clusterings. To see this, consider a set of 10 copies of the same cluster which are equally spaced apart. Let there be two centers assigned to these: e is placed in the first copy of the cluster, and C2 is placed in the second copy of the cluster. The remaining 8 clusters must now be assigned to either e1 or c2. However, due to them being equally spaced apart, we can assign each of these clusters to either center and the cost will remain the same.
Our recommendation on how to resolve this is to introduce secondary heuristic for breakigg Namely, if subtree equidistant to two centers under the ultrametric, assign it to the center which is closest to in the data's 's original metric. Lc., if our ambient distance metric is Euclidean, then use
41

---

the Euclidean distance as tie-breaker. This provides the intuitive clustering that one expects when looking at groups of points.
In practice, we achieve this by giving each internal node in the tree a representative point the Fuclidean mean of its leaves. Each annotation not yet marked (and thus chosen at later k) maintains the closest center based on the Euclidean distance to its representative, which is resolved between any center that marks its parent. At the k where this annotation itself is chosen, best annotation, and thus, the internal node that this annotation and sub-tree of nodes itself should become a subtree of. We update all annotation pointers in this way by placing the centers one by one, following the path from the center to the leaf checking distances to unmarked sub-trees, and updating the pointer if the new center closer than other tied centers that had already been marked.
have found the
As this is just a processing step over the annotations before the tree is actually constructed, it can easily be plugged in/out based boolean flag. Furthermore, the choice of heuristic can also easily be changed, but here it should be kept in mind that it might influence the running time if any complex function is used.
The choice of using the mean point as a representative and comparing Euclidean distances is based on the following: under the dc-dist, one often gets one cluster which consists of multiple equidistant sub-clusters. These equidistant sub-clusters often follow snaky paths throughout the ambient space. Let now suppose large cluster gets split into two, implying that its sub-clusters must get assigned to one of these two new groups. Since the sub-clusters are all equidistant, they can be arbitrarily assigned either of the two groups. By breaking ties that the sub-clusters are closest to each other in the ambient space, we dramatically increase the chance of the sub-clusters getting re-assigned in intuitive manner.
Complexity
This process requires traversing the tree from the leaf to the root for all centers placed. To construct the full hierarchyddendrogaa//rree
solutions, we do constant time calculations (scales with dimen-
sionality) at each visit of an internal node, as it only requires computing the Euclidean distance of two points. This means that the worst-case complexity becomes O(n²) in the case of fully unbalanced tree, but in practice and expectation, this will be much closer to O(n (rooo)))))
C.1.3 Find solution for given k:
To find the solution for given i efficiently, start out by annotating each node of the new tree with additional information. Generally, the insight is that going from i: to i + corresponds to splitting up single node/cluster into two new nodes in the tree. A slight detail is that some nodes will have multiple children, where the "split" is implicit as all the children split from the same node. We can mark at which & each node split from the parent in constructing the tree, where & is just the current iteration. We simply mark all new nodes created in an annotation with that k.
To then recover a solution for a given k. all that is required is to cut all edges in the tree going from k' 2 k to k < k. The solution is the clusters associated with all the nodes above the cut. The only note is that if leaf is reached and no cut is found in that path, the leaf is just part of the solution.
The correctness of this algorithm comes from the fact that any clusters below this cut only existed at higher k" than the solution for k we are recovering.
Complexity
Marking the tree is done with a constant factor added to the complexity of the list traversal of building the tree, so On)).
Finding the cut can also be done in a single traversal of the tree top-down, simply stopping the traversal of given branch when cut is found and returning the nodes. So this is also (nz).
Furthermore, the solution for given is can be stored, and the algorithm to find another i can be "resumed" from this solution, making finding similar le values very fast, almost constant.
C.1.4 Find leaves for given node quickly labeling a solution
We create an array of the id's in the leaves, where each id is inserted in postfix order. This means that looking at the tree, each internal node of the tree will correspond to a continuous area of that array. store the bounds of those segments in each internal node, the nodes corresponding to node can
42

---

be returned in constant time by just returning that continuous segment of data of the new array. Only single postfix order traversal of the tree is required to set up this array and pointers in the internal node, which then takes (nn).
However, if want recover the labels in the standard form of each label being in the order that the points were provided, traversal of the recovered solution is required, putting the corresponding label in the right place in an output array of labels. Simply put, the label value of point p has to be inserted in place of the output array of labels. This requires worst-case (n) complexity for a given solution, as is just linear scan with constant work for each of the n points.
D The Algorithms
We now describe how these algorithms are implemented. We use the terminology n-ary dc-tree to refer non-binary LCA-tree storing de-dist relationships. Again, this immediately transfers to relaxed ultrametrics.
describes how we find the corresponding z-centers and the costs associated with them in practice. Algorithm 8 describes how we use this information to obtain the corresponding (k,z)- 2)- clustering hierarchy. Algorithm 9 shows how extract clusterings for specific value of k from hierarchy. Lastly, Algorithm 10 describes how we implement the tie- jie-brakiin heuristic assuming Euclidean distance.
Algorithm
Algorithm 7 k--centroid-annottiio
Input: An n-ary de-tree T over the dataset X, power 2, array 1: if [T] = 1 then
2: A[T.id] (TT.parent.dist) Tidd, Ptll
3: return 0, 7.id
4: else
5: bestCost = oo, bestCenter = -1
6: for C E Tchiidren do
7:
subCost, subCenter k-comtrrid-aanottiioon (C, z) currCost = subCost + (T' (Ti.sss))* (Tisize C.size)
8:
9:
if currCost bestCost then
10:
bestCost = currCost, bestCenter = currCenter end if
11:
12: end for
13:
for C E T.children do
14:
A(C.id).parent = bestCenter end for
15:
16:
Decrease = (I' parettttt.dsst" Tisize - bestCost
A[T'id] Dcost mellll
18:
return bestCost, bestCenter)
end if
43

---

Parent has added children with higher cost Algorithm 8 k-centroid--hieraccyy
Input: An n-ary de-tree T over the dataset X, power
A eecentrood-annotatinn (T, 2, (i.e)))])
2: Sort(A)
3: Root Node(parent null cost -1,id A[0]
4: A[O].tree = Root
5: for deur A(T]....A(mz 1] do
6: Nnew Node((prent = rullPtr, cost = -,, id center)
7: aeur.tree N Neww
8:
apar Aldcur. parentt Cp dpar.tree.com tree.cost
9:
if cp + Gear.cost A Cp 2 0 then
10:
N par (par-trre..chidrren00 (0)
11:
N Wpar.cost = www...osst Dec.eeaseeeeeeee
12:
N Shew-parent = par
new
13:
N par Node(pprent = Narr cost = - NVpar.id) Add same center node as first child
14:
www.hhhhn.dddlll. add( (dd(N (Npar)
par
par www.cchhi.nndddee Nnew)
16:
apor. tree NNor
Update annotation to point to lowest corresponding node Parent has no children added
17:
else Cp < then
18:
N new parent apar.
19:
N7 Node(parent = Opar tree, cost -1, id apar-id)
par
20:
Opar tree www.:tre..chilrreee www.ccchieee..ddee add par
21:
Oper Qper.trec. tree www..chilren..adde Neww
22:
else
Parent has children added with same cost
23:
Opar.tree. arree..cildren.adee (N New
24:
Neew hareetarent& Qpar- tree
25:
end
26:
end for
27:
return Root
44

---

Algorithm 9 k-centrooi-ccluter
Input: An annotated k-centroid hierarchy-tree I' over the dataset X, searchK
1: if [T] = then
2: Output T
3: end if
4: mark = chhldrencildrrnn = SLinK(T.children)
5: if mark S searchK then
b Every edge should be
6: for C T.chilrrenn do
7:
ke-entroiddluuser((sssaarrr
8: end for
9: else
Only some edges should be cut
10:
A A=D
for C E T.children do
12:
if C.k searchK V Clissoriii cluster then (C)
Non-cut edges merge with original
13:
14:
else Output C
15:
16:
end if
17: end for
18: Output Merge(A)
19:
end if
Algorithm 10 Optimize Annotations
Input: Sorted list annotations decreasing order A, tree annotated with representatives
1: for deur E do
>> For each annotation
2: N feur-deaf
3: while N + reull do
>> Traverse from center leaf to root
4:
N. N.mark(Qcur ccnter)
5: for C E N. N.children do
6:
C.Carkk null then
> Any unmarked children of marked path C.anno.best Parent min (Ca.nno.bettaareeenee Euclid((.rep. Anno.center))
7:
end if end for 9:
8:
N = N.pprred
11: end while
12:
end for
13: Return A
Return list of annotations with updated pointers
45

---

Cover tree k-median/GT
KD tree k-median/GT
HST-DPO k-median/GT
(a) Comparison of HST ultrametrics using the k-median hierarchy and the ground-truth value of k.
DC tree k-center/Stability
DC tree k-median/MoF
DC tree k-means/Elbow
(b) Comparison of hierarchy/partitoon combinations on di-d ultrametric.
Figure 8: A visualization of ultrametrics and hicrarchy/partition combinations on the D31 dataset.
E
Implementations of the used HSTs
We build KD trees. Cover trees using the C++ library mlpack4 [20], and build HST-DPO trees using the C++ code from /tsttp::/githhun com/ /oop/////aaa///D21-15557
F
Used Datasets
Table 4 lists the datasets on which we validated and compared the proposed framework SHiP to other competitors.
G Tables - Runtimes and performance metrics
Table 5 shows the runtimes, Table 6 the ARI values, Table shows the NMI values, Table shows the AMI and Table 9 shows the correlation coefficients cores for all datasets.
46

---

Table 4: Dataset properties. Number of samples (n), dimensions (d), number of ground truth clusters (k), number of noise points (#noise), and the source.
Dataset
"
#inoise
Source
Boxes
21,600
12
[78]
D31
3100
2
31
0
[5]
3-spiral
312
[5]
aggregation
[5]
chainlink
1,000
0
[5]
Density -bssed 2D- Data
Tomas Barton Benchmark
cluto-14-8k
8,000
2
6
764
[5]
cluto-15-8k
8,000
1,153
[5]
cluto-t7-10k
10,000
cluto-t8-8k
8,000
323
5
complex8
2,551
2
[5]
complex9
3,031
0
[5]
compound
399
dartboard1
1,000
diamond9
3,000
0
[5]
jain
3,373
2
[5]
pathbased
299
[5]
smilel
1,000
[5]
Synth_low
5,000
100
10
500
[40]
Synth_high
5,000
100
10
500
[40]
Mice
1,077
68
0
[50]
Tabular Data
adipose
14,947
12
airway
14,163
10
Real- World Data
lactate
39,825
2
0
[11]
HAR
10,299
561
0
[50]
letterree.
20,000
16
26
[50]
Pendigits
10,992
16
10
[50]
COII.20
1,440
16,384
20
0
[60]
Image Data
COILI00
7,200
49,152
100
0
[59]
cmu faces
624
960
20
[50]
Optdigits
5,620
64
10
[50]
USPS
9,298
256
10
0
[37]
MNIST
70,000
784
10
0
[46]
47

---

Table 5: Runtimes of various parts of our clustering framework SHiP over ten runs, compared with standard clustering methods. Time is given in minutes, seconds, and milliseconds [min:sec. ms]. The first four columns ("build") refer to the computation time of the different ultrametric trees. The next two columns state the runtimes of computing one hierarchy (k-means) on the DC tree. The second column here shows the timing for the heuristic from Section C.1.2. Note that these runtimes are not lated to the chosen ultrametric. The subsequent three columns state the runtimes of different partitioning methods, i.e., 'Stability', 'Median of Elbows (MoE)', and the 'Elbow' method on various hierarchies.
12:10.358
00:12.816
00:00.091
00:00,665 663
00:01. 128
01:32.488
01:33.225
02:39.063
01:39.524
00. 10.900
00: 12.12483
00:00.200
00:01.346
00: 02:12.500
00:00.1 101
00:0006)
00:01.392 392
00:33.945
00:33.785
00:014233
06:46.726
69:34.012
03:45.745
11:42,910
03:21.409
00:11.710
14:18.780
00:00.515
00:44 270
01:48 607
DPC
AMD-
DBSCAN
01:04 01:04.670 .6.
00:00 878
00:00
00:00 121
01:00 159
00:06 470
0N:05 942
00 00.10.670
00:09
00.00 .229
00:01 .76
00:00.05
0D:00 138
01:01 .07
00:00
028
00:00.00 02024
00:00 139
N0-02.879 879
00-02.
N0:04.573
00:04 553
00:00 482
10.16.822
07:43 293
00 129
00:37 00:37.055
00:09
00:02.375
02.58.13 177
00:00 0.34
00:00.346
00:03
00:29 259
17:21 183
Ward
00: 00:10.808
00:00. 153
153
00:00.002
00:00.010
00:00,112
00:01.233
00:01.256 256
00:02.058
058
D0-01.390 394
00:00. 120
00:00.00
00:00.016
00:00,002
0C:0000
00:00017
00:00,99
999
00:00.982
00.922
00:00073
00:05.243
99.999
00:59.999
00:18.488
00: 309
00:03.281
00:08
941
12:04.037
00:00.064
00-00.974
00:06.092
19:02.49
498
competiors
00:00
SCAR
00.01 1811
00:000
00-00.023
020
00:00.003
00-00.099
0000441
ON
00.00
00:00
00,00-21
00-000113
175
00000.33
0000033
00000.19 194
00000
00:00023
00,00.088
00:00.36 367
00
00
00 00.00.61
012
00:00.558
00
00-00.490
00:00.315 0000330
00:07.964
00.00.1 116
00:00
134433
00:01.435
5.32
00:15.35
5.352
k-means
de - 500)
00:01.217
00:00.500 509
00:00.11 131
00:00.200 204
00 171
00:01.314
00:01.55K
00:02.052
01-0 0991
.99
00:00 592
00:00 682
00:00 127
00:00.270
270
00:00751
00:00,045
00:00.119
00:03.754
754
00:04, 199
00:00.86
00:00,32
00-0) .97
00:08. 478
00-03.52 521
00:02.725
00:13.524
01:59.225
00:00.661
00:01 154
00:08 493
969
03:29.969
I-means
GT)
00:00.11 114
00:00 289
00:00 227
0N:00 133
00:01 344
ON AX2
00:02 532
00:01 .930
00.00 066
210
ONCO0 321
00:00 005
00:00.013
00:00.221
00:00 351
782
00:00 173
00:00. 122
00:00 126
00-02 10-02.248
00:03 386
01:01 000
00:01 637
(0:32. 122
00:00 206
1000-320
320
(E: -
00:00
00.00
00:00
00:00
00:00
00:00
00:00
00:02
00:04
00:00. 002
00:00. 000
00:00. 000
00:00 000
00:00.00 000
DM OMOO
00:00.00 000
01:00. O00
00:00. 000
00:00 000
00:00 000
DM LMOO
00:00.000 000
00:00. (NO)
00:00 000
00:00 000
00:00.00 000
00:00 000
00:00.00 001
00:00 004
00:00. 000
00:00 001
00:00.000 000
00:00.0M 000
OI:ONLON OND
00:00. 000
OI:00 (000
00.00 000
00:00 008
Elbow
00:00
00:00
partitioning
00:00. 13
00:00,015
00:00.000
00:00.004
00000004
00:00046
DICOLD42
00.00.058
00:00,045
00:00,012
00:00012
00:00.00
00:00.004
0IC0L0112
00.00.000 0.00
01C00.000 OOO
00:00.044
00-00027
0D:00024
00000.044
00.00.055
00:00.25
00:00056
00:00.087
00-00.53
00:00.004
DIX0L139
00.00.02 0.0
00-00022
00.00.44
00:00491
MoE
Stability
00:00.00 005
00:00 000
D0:00 000
00:00 DOO
D0:00 000
00:00 00L
D OOT
00:00.001 002
DI:00.00 O01
00:00. DOO
D0:00 DOO
00:00 DOO
D OOO
00:00.00 00D
D0:00.00 0O0
00:00 000
00:00.000 001
00:00.00 001
00:00 000
00:00.003 003
0D:00.012
00:00.002 0000
00:00 002
00:00.00 002
000
00:00.00 001
00:00. 000
00:00 001
00:00 002
00:00.030
00:00
00:00.00
:
:
:
build hierarcht
k-meuns
(heur.)
00:00 .99
00:00 .20
00:00
00:00
01:00 CHIS
00:00 164
ONCON 19K
252
00:00
55
00:00.
00.00 LI
00:00
014
00000 CO1
0D:00 D03
ON LO17
00:00 001
01000 00T
00:00.0
10:00.055
128
00:00
00:00
117
01000
013
010000
592
184
00:07.
00:01
936
00:01
00:00
100004166 416
00:00.379 379
00:00
0M:22.513 117
00.00.00 000
00:00 162
00:01 844
03:21 10012
k-means
00:00.033
00:00 000
00:00.000 0000
00:00 DO1
D1C DO1
00:00.012
00000111
00:00.0 14
D0X00012
00:00 DO3
D0:00 DOS
D0 000
00:00 001
00:00.000
DIC XOXI
00000.00 001
00:00 007
00:00.006 006
00000000
00:00021
00:0 D68
: 00%00.14
022
00:00013
00:00.00 001
0E:00111
00:00.00 000
00000.055
00:00.011
00000, 120
00X00
DC ure
00 00:14.239
00:00.32 327
00:00.009
00:00.033
00:00.045
0001 898
0000 X36
00.02.445
00:01 NX00172X
728
00.00.244
00:00
00.00.011
0D00001
ONERO TO
006
00:00
0N000.006
00:00.566
0600
00000.78
00:00.02
00.04.997
00-47731
00-23.44
1
076
00-09.072
00-02566
566
00:14.177
14:10.661
00.00.28
00:01 420
00.08. 670
37.05.095
095
HST-DPO
00.09 00:09.679 679
00:00 207
00.00.002 002
00:00 024
00:00.042
00:01 359
01:01 119
00:02. 100
00.00.1 129
00:00 185
00:00.001
0D:0022 027
ON:O0 13
0000.00 004
00X02.02 0Z
00:00024
2004.264
00:04.05
00:00 126
00:04.054 0504
00:39.435 433
01-55.260
00:14. 396
00:04.63 625
01:04 .04
N2:50 274
00.00.00 082
00:03 N0003.442
00:45.038
131:03 099
build ultrametrie
0004
00:01
00:00.00 059
00:00. 004
00:00 00D
00:00 000
00:00.001
00:00.017
0M:00013
00:00.019
00:00.014
00.00.00
003
00:00.044
004
00:00.000
00:00.02
00:00004
00:00 000
00:00.000
00:00.02
00:00.087
00:00.00
00:00.00
00:00027
00-00, 161
11-11-053300
00:00 522
00:00-067
00:03699 658
03-52.59 .97
00.00.046
00.00.06
00:00.55 335
00:02.92 .24
16:24.22 220
Cover
KD tree
00 00:00.013
00:00.002 002
00:00.000 000
04 00:00.000
00:00.000 004
00:0000055
00 00.00.006
00:000.005
00.00.001 1
00-000000 001
00 00:00.000
00:00.000 000
(N 00100000011
00 00000.000
(0 00:000.000 000
00 00:00.000 000000
00:00.040
00 00:00.004
00 003
00 00.00.008
00:00.025 025
00:00.341 341
00:0000044 024
00:00.015
00:01 00:01.066 026
(0:36.36 361
00.00.021 02.
00:00.011
00:00.11 117
00:10.649
00:00
eluto-17-100 -oto--7-1Okk
Dataset
Boxes
3 spiral
aggregeation
chainlink
cluto-t4-8k
cluto-15-80 -kkk
cluto-11-88 -kk
complex8
complex?
compound
durtbourd
diamond9
pathhased
smilel
Synth low
Synth high
Mice
airway
Inctote
HAR
letterrc.
PenDig
COIL20
COIL 100
cmn facess
Optiigis
USPS
MNIST
D31
jain

---

Table 6: ARI values for various combinations within our clustering framework SHiP over ten runs, compared with standard clustering methods. Noise points were handled as singleton clusters. This shows that the results yield high-quality clusterings when using the DC tree as an ultrametric.
IPPC
25.0
9
73.4
430
42.2-22
51.0
50.2
297
21.2
1511
358
32.5-077
000
0.6
051
0.6
53.
-00
29.8
36.0=000 01
0.2
0.6
0.1
210
S13E03
AMD.
03.0
880
50.6
02.
124
801
W7.4
SIA
52.1
0.0
517
71.6
000
78
556
39.2
112
682
000
compettonn
Ward
05.8
92.11
00201
0.8
49.
71.
412
867
42.
28
MIL
68-2
M.. 66-0011
62.5
11.7
6N7
277
30
14. 14.+0.8 +0.
562
686
01.2
81.
2.
03.0
52.7
0.0
SEAR
0.1 0.1
4
003 10.
26.4 20-3
00 0.
6.3 032
01 108
-1J +03
-18119
212472
NSE
62+14
20393
14110
20
000
53 53232
0.4+1
09
55520
16
13:04
14.4
Bard
00.5 6.3
-66
74 16
45.0 55 20
042
310
56.5 12
22
57
384+00
28
1110
516
330 55.0
152
47.0
390
12:0000
58-2
56.111
532 47
0 56
36.0 1.
I-meens
21.7
20,5
14.1
22.3
10.9
13.
10.0
38.
13.
30.0
25
30.0
46.3
87
433
18.6
24
2.0
0.3
KD Doe E-modlrt
36. 0
30.2
5.9
48.
23.
17.8
25.0
20.5
50.4
14.38
46.3
28.0
00.2
55.0
16.0
6.4
16.0
22.5
12.2
2.0
0.2
(xcener
2.5
0.6
18.9
3.1
23
53
1.2
8.9
11.0
177
16.5
198
80
0.7
1.
83
22.5
23.5
11.3
4.1
1.4
C-moon
26.2 1.
1.
7
48.8 7
10.334 3
193 135203
16.5 15S
178831
1
16.011
100
67.
120
01
8.3 01
89205
47. 220
312
18.1 22.
04
16.3
19.3
28.0
203
00.1
Correr 0r00
Jomedion
1.
2.1
420
19922
213+
2333
16211
248
182231
M2247
72+06
120206
21
66.
000115
11
2.1
84206
9
GAT
12
62.0
14
46.4
22
25.2
20
37
Aecenee Shahllty
18S 2.0
L
28 101
48
28202
30+02
707
224004
16+666
239
182123
R8+02
14
131
46. MEDER
IL
24
18.6
221
2111
08
46.4
55.5 193
62 330
12.
21 R
444
40
23
42N=69
87231
350270
SAT 1HC
RES 1 MAL
M5281
19
31388
20+09
26263
422
02262
20
341 211
76320
SLT S
46.7
452
HIST DPO
E-modon
65.5 7.8
38142
02 1
161
+4.
468
400
75230
11.0
200
1811
1EO
83415
381
70+60
280
384490
21.1125
273
75113
322
20
25
260
267
Esceoer
2.0 0
6.6 1:
24
3.43-03
28
33+-3
8.0.:00
311
03
92.032
220
16.6
212
0.0011
1.0
213110
803
20.024
80.0 477
7.1
0 43
12.3228
568
25.8
86.4
Comons
07.0
05.1
60.0
6.5
360
6%
61
100
45
333
57.2
70L6
58.8
17.0
72.6
70.0
06.5
77. 0.
4600
Jomodion
09-3
88.1
68.0
75.5
71.4
222
1000
702
515
20.5
09.5
40.0
16.0
72.5
56.6
77..0
41.3
l-conter
00.1
79.7
08.6
80.3
67.2
28.00
63.4
01.44
05.1
300
K556
100.0
09.4
350
41.0
200
12211
81.22
002
61.3
107
tiee
C-moons
00 3
56.1
00.2 2
52.0
98.6
60.
25.3
1000
00.5
56 8
1000
36.0
58.0
82.1
05.0
83
75.5
20.0
60
74.8
51.0
E-medon
99-3
0N
99.2
70.
08.5
28.
100000
99.2
51
100.0
660
846
58
41.3
0.6
72.8
00-2
60
Aocenter
GT
05.5
55.2
7R
0.4
1.0
4
95.1
100.0
516
100.0
81.2
01.1
2535
4.9
0.7
-1.
65-4
19.5
24-2
5,0
0.5
Deses
spinl
aegrogssio
duntiok
ditzc 21 1Ok
complest
comples
darbbard
pathoodd
Synth Ine
Synth high
siminy
laternes
PesDiigss
COIL.2 20
COIL
Digls
MNIST
DSi
Jain
49

---

Table 7: NMI values for various combinations within our clustering framework SHiP over ten runs, compared with standard clustering methods. Noise points were handled as singleton clusters. This shows that the results yield high-quality clusterings when using the DC tree as an ultrametric.
DPC
50.3
6000
65.0
20.0-02
45.5
30.1311
636
43.1
41.1
924
$40
41.7
2012022
0300
0.0
0.0
44.
07.7
65.6
69.7
660000
63.5
420
48.
AMD DRSCAN
69.--03
10.1 10.11009
51.8
65.6
06.7
347
26.8
77.1
32A
75.
00
45.
0.0
0.
40.9
0.
40.3
36.0
65.0
72.1
22.6
86.
0.0
0.0
65.3
compettiooss
Wird
97.2
95
91 3 02
82.8
70-7
66
56.8
72.3
8. 1.
9909
590
61.2
807
S8.
27.9
32.0
62.0
40.5 40.3.00 1.0
72.1
8216
303
81.
101112 11
76.1
68.2
SCAR
8.8. 1.088
530
10002:12
1:2
10.0100
103
116109
12x 128 1.2
2 22
37 +-3
373101
200
2
266
194118
184117
1001114 1.8
4.3
51 1.9
192
100
1099
23
53.6
21
610
Birel
00.3 1.0
05.7
05.0 13
05.5:2
57-21004
16. 1.7
65.5
18
718-0
33 2
106
00.0
510101
17.
00.2
22
35,0
6800
77.8
13
72-4
0088
18
40.
J-menss
Ellow
87
09
33.5
53.2
50.0
54.4
56.5
65.2
35.8
68.4
10.
00.5
47.3
20.5
40.0
08.1
4500
20.3
37.3
25,0
A-median
73.1
82
23.
56.3
59.3
57.7
55.2
30.2
76.2
41.0
76.6
70
52.2
28
40.5
30.2
51.7
41.
35.0
36.5
25
E-cemer Saiiliy
5027
20.
62.1
46.4
06.2
J7.5
47.6
65.5
61.5
69.5
11.
39
58.5
36.5
28.
29.3
45.2
00.
33.1
36.0
25.0
A-menn Bllaw
1 0.03
86 1
N 3
060
501125
304113
022213
50114
760+1
198118
76530Y
232103
562103
78. SUS
07.7409
507103
422-404
35.5
A-medaan
75.0 1.
2.1
O 23
10
0
14
48
61
27
12
801 26
519
L2
03
370108
51.111
578
70.9
802103
78 05
10.1
03
04
76.2
41.
81.1
700
36
30.1
E-menner Stabiity
51.1
78.6
30.2 3
315+008
413
MS103
170104
47
52.0 LO
62
88800
016+0.5
033330
ST
000103
M00C01
212101
10
86
519109
515105
7L
783105
312
475000
46.000
l-menns Bloww
2.
36
713338
24
029138
24
568
100
10
100
15
530
02. 02.
#2
36.311
5033
71
781113
2022
212
00
70t
62.2
29.6
30.3
72.7
206
62.2
476
400
EST-DRO
R-mtcccio MoE
1.
66 8.644
07
23.
62113
03131
4.D.445
12
W18S3
011182
00577
72.
103
612
GLORGS
576121
074
43. 162
022226
21
65
53
30
36.7
R-cener Subilly
50.6 0.3
2:24
80.6 22
22.6 22.6+99
4:22000
0.
150
458 1.4
45.3 04
+ 0.0
6644
131
08. + 1.1
12.1 377
12.9
63. 63
633
016
#2
02
26.7 15
# L.0
422112
222
1:00
0 1.1
315
6-
012 3.1
470 08
+ 1.6
75-7
4422
503
516
664
383
326
4n9
422
506
080
7077
315
50.1
lomeins Bileww
05.2
06.00
966.7
65.9
100,0
76.4
75.
607
H02
65.
91.2
10000
707
09.1
100.0
602
811
285
083
03.
56.
828
806
87.3
81.
329
62.6
A-meeaan MoE
90.2
81.8
9667
58.9
100,0
51.
75.2
62.1
$6.5
90.9
2016
100
85-
600
1000
152
260
70..7
65.9
20.
81.
220
583
I-cener Subaliy
00.00
87.7
85.
100.0
81.5
75.3
83-7
70.5
988
30000
83.5
59
100.
87'
56.
51.9
43.7
56.3
70-3
800
25.9
62.1
46
Ammonn
99.2 22
05.8
96.1
08 8
87.1
82.11
50-
65.8
05.0
10000
86.0
89.
68.5
60.5
63.0
44.0
75.6
88.0
80.6
55.1
65.0
67.3
40.0
I-median
00:2
05.8
05.1
DK 8
555
79.9
30.5
65.7
03.0
100.0
00.0
06.0
100.0
80.2
43.0
58
65.3
42.8
77.4
51.0
87.0
0
E-conee
96.6
80.2
2.6
477
6-
MLS
74.6
1000 1
00.8
02:2
100.0
96.7
90.0
21-2
6:33
11.8
1.4
7.5
MU-7
70-7
1/22
21.0
16.8
Bones
BS1
S-pptll
sparegation
dlo-----00 7.k
chaio-4 28 SL.
complets
amplee
drtbaall
Jain
Synit Ioe
Synth Iriph
srmwyy
HAR
Digiis
COIL 20
COIL
OydDigks
USPS
MNIST
Luoug bue
50

---

Table 8: AMI values for various combinations within our clustering framework SHiP over ten runs, compared with standard clustering methods. Noise points were handled as singleton clusters. This shows that the results yield high-quality clusterings when using the DC tree as an ultrametric.
31.5 2.0
49.460
23
232=0
40.93:12
21T
53.1 111
21 21.00.1
DPC
36.0
83.5
33.2
211
19.5
132
05.3
0.0
0.
52%
65.5
-00
DBSCCN
05.7 05.7
52.1
43.20006
AMD
57.0
80.3
28.8
56.9
31.8
71.
74.4
71.5
00
12.9
0.0
0.0
28
28.8
0.0
50.1
47.8
43.3
48.4
6.5
58.3
0.0
0.0
compettoos
Wal
57-2
91.
00=001
5 0:
62.8
29.7
611
562
70-
72.8
8.3
50.3
80.6
810
27.1
630
3200
82.9
10.000
72.6
81.
300
7611
83. 111
76/0
08
93
SCAR
8.6- 0.8
80 L:
-04
880
113120
9.8 1.2
113109
125212 1.2
280122
365454
36 067+37
309191
205
20.0-11
04210
288263
188117
182
628408
0 1.9
919111
31-0
022227
10.7
Eset
06.2 1.0
15.5 8
-1.
204
1.07
18.4 60.4 1.17
1
71.3
3.2
513 101
7T4
210
$29
222
319
105
673
110
220
133
110
207
68.5
796
653
000
113
030
622
310
788
726
722
60.7
401
k-meins Ellw
67.8
80.9
25.0
66
33.0
52.8
56.4
582
510
55.8
640
36.9
07-
119
861
68
206
409
310
274
585
471
42.3
48.
30.1
503
322
21.2
to0:
k-modin
81.7
782
66.1
50.2
535
67.4
66.7
005
36.4
1003
41-
12
2600
00.3
520
ST.
2N-4
57.4
40.0
15.
30.0
55.2
32.0
21.1
I-center Swaliit
49.3
748
59.9
44.
41.1
44.
526
106
60
67.1
38
372
55
31.
25
376
424
27.
22.
316
21.7
A-meam Eloo
080
F1 3:4
65 1.6
06. 2.5
0.2
1:5
013
07.7244
750
1.2
761
0
170102
546204
1.3
711
752-06
16 1
03110
475
000
85
trs: A Anmesaan
74.0 1.5
21
P 26
66 18
6
595114
16
6A7
6144
22
67.
1
70
22
503 L1
M4
66
668
71.
10
742-00
181
23
07.0
83
68
Aoconeer Subilly
44.2
23.2 2
02.7 2
205
12.0
67.544
16
+03
35.1
51T
510+03
263
101101
125
018
00
366
169
28-
3T.2
07.4
59
7L
75.5
25
617118
5L7113
23333
587
19.020000
62 07.588
10 13000
10:0
31
220
43
311135
583117
679223
727
2842218
00.119
17
2011 001106
C4
53
726
58
60
A-modian
20.0- 1.
6-3
07.4 73
212 28
44
527
67.7
26
16.0
038+38
35
388177 71
720
105
141
630
503
13
01925
54
318131
07
002
147
006
14
0133
29
00.0000
04
08.
10
16
Aveenee
00
366
96.7 007
36.8111
57.5 57.306
57.9 97.9
02
411 411
16
463
17.8 17
17.
53.8 22
32 62633
532
2 10.4
52. 87
0004
265
11
20.0 108
11
=67
13
T
00
1.
42.2
67
32
36.8
230
28
811
30.4
26.4
57.3
mmmans Blbww
15.0
08.7
25.1
58.
753
742
686
602
853
91.1
100.00
762
06.1
8
08
637
53.
62.8
950
87.7
86.5
814
025
Memellan
90.2
51.3
9617
60.9
75.3
82-4
$6.0
08.9
100
08.1
100,0
151
F0.
65.9
522
8LT
ME
570
716
325
l-center Subility
04.9
853
97.0
60.1
70.1
62.4
73.
M82
10W
815
53
100,
24
522
14.11
607
87-4
803
67A
503
20-
05.2
95.0
06.0 8
87
80.1
65.6
0550
1000
390
05.7
100.0
209
K7
63-5
75.6
87.4
85.5
6350
07.2
623
k-medaa GT
00.3
05.0
25.T
01 8
5356
73.9
30.1
65.7
03.0
1000.0
09..
03.3
100.0
890
67:00
42.5
08.12
65.2
62.5
77.4
S2.0
53.0
07.5
03.6
cenner
66.4
20.2
70.5
M6.2
1.0
6.7
1-
M6.3
00.3
100 0
K0-4
0.T
50.3
04.3
85.5
7-6
002
1.4
-0.0
2.6
26.1
1.9
20.3
2.2
0.5
Boses
DS1
3-ginl
0la0-44-88 3K
65 SL
Clano-4 28 SL.
compless
comple
dartboart
Jain
patlesedd
Synth Ioe
Synth lnih
armay
HAR
lefterne
PaiDigis
COIL. 20
CRT Poccs
USPS
MNIST
eiron bue
51

---

Table 9: Correlation coefficient values for various combinations within our clustering framework SHiP over ten runs, compared with standard clustering methods. Noise points were handled as singleton clusters. This shows that the results yield high-quality -ualituaatyy clusterings when using the DC tree as an ultrametric.
DRC
28.1
193
76.1
44.0
47.0.-3
S18
07.4
25.7
64.7
60206
17.8
3888
10.2
0.0
0.0
6.6=01
0.0
44.
-000
36.4
40.0
2.8
42203
252
AMD DRSCAN
15
08.5
80.5
12.
97.8
514
87.6
88.3
91.4
01
24.7
0.0
0.0
63.2
72.6
6.0
10.1
6022
30.3
19.6
27
0.0
0,0
compettoos
51.8 1:03
28 1.5
108 1.09
PL7 2.333
Wand
56.8
10.5
740
122
840
183
18
06.0
77.55
1659
80.
80.
66.5
08.
01.7
61.7
65.9
52.8
65.6
SCAR
0.5
5 02
1
1010.
-04
-22
-2
85+15
31322
69+16
-20
$3135
84238
12103
25
3.
000
17
12208
-13-
22
01.5 +-.33
75 18
850
544411
28992
08 959
68 101
+60
244
130 106
58. 58..
56.
4-7
01.5 183
11
$13
Baxett
55-3
55.6
45.6
550
363
k-meiss Ellww
34.3
75.1
40.1
2177
31.3
21.2
242
25.1
48.6
20.2
4000
325
65
80.0
46.
203
162
64
9.1
1411
20.2
25.0
13.0
9.
12.
28
to0: k-modin
46.5
000
61.5
02.3
26.
11.7
27.0
64.3
17.
17.9
32.0
66.
56.2
16.
28
74
9.5
20.8
95.5
12.
0.5
2.1
I-center Sualiiy
10.3
68
30.
120
102
118
190
882
18
230
218
228
202
58
81
86
246
11.4
97
42
A-meam Eloow
36.
3.9
52
S.
2300
96.7
0.0
255
434
297
018 52
9
715
706 3-5
0
25
21
176
150103
20T
518 1.9
511+15
446 14
222 16
13
07
trs
A Anmesaan
G00 3
66
6 38
318 12
06.1
12
2631
28 26
32.
48.
223 30
62
38 1
37
13
29
20
197105
288
097
462
26
30
188
181111
61.1
Accomne
114
53.4 53411
31.21.
0.5003
142203
118103
18T 2n.
193+
20
200203
27.9
700000
293158
26322
26.4
61201
IN3
101
186
470
16.1-3
160
155
189
188
44.9
46 06.0
56.0 11.2
63
62177
216123
24
28
448269
10
372474
319370
110200
28866
85100
3602
48
411561
30.3
419230
20552:3
142214
MET
32
HST-DRPO
A-median
51:4
11.0
6.6
12
3432 41
513150
222133
22
64
4..0
86
92
482 123
211470
70
003
124
MT+
120
20DE91
1522
20
80109
07.0222
21.9 92
11.581
28.5
18.5
16
Aveence
Sobility
22.000 002
0 9
36.1 223
12.6 126= 05
03
1811 12
2 10.3
20.5 505+22 22
28 932
12
5
15.
60202
74
220
535 103
189
40.2 22
14
20.3
149527
12.0
47.9
10.2
448
511
410
mmmans Bloww
$7.0
83.5
52-6
03.
03.5
415
68.
666
58-
468
720
61 8
63.0
17.0
16.8
728
70.5
67.3
77.1
38
498
Memedlan
90.3
51.9
76.5
06.9
722
09-4
767
3000
750
50.
100.0
46.
600
222
169
262
73.3
246
77.
36
445
l-center Subility
01.11
8012
N2.4
87.3
87.0
68.0
07.5
98--1
82.1
10W.0
8/7
222
61.1
1000
955
833
505
200
055
81.22
801
61.4
505
62-7
202
99.3
93.7
95.2
87.3
73.2
80.0
65-1
100-0
200
55-
H--1
601
121
25.2
632
75
05-2
k-meda GT
00.33
03-7
08.1
01 3
75.8
74.
09.3
60.1
83.4
1000
00..7
55.1
100.0
S4.1
81.8
51.22
52.4
12.0
68.3
73.
20.1
67.66
56.8
5006
cenner
71.2
65.9
00.9
MU.5
3.0
6.7
5.3
07:5
91.2
08.3
79.2
1000 0
F1.1
5-4
513
100.0
11.
0..
2.5
25.5
1.9
-0.0
0.6
00:5
20-2
11.5
1.1
1.0
Boses
DS1
3-ginl
0lo0-44-88 3K
65 8L
Clano-4 28 SL.
compless
comple
dartboart
Jain
patlesedd
Synth Joe
Synth lnihh
armay
HAR
Lefterne
PaiDig
COIL.0 20
CRT Poccs
USPS
ANIST
eiron bue
52


Reviews:
[{"review_id": "XA3JQlJa6D", "reviewer": "Reviewer_vbSb", "summary": "The authors introduce a new clustering framework based on relaxed ultrametric spaces and their associated lowest-common-ancestor (LCA) trees. They establish connections to existing problems and objectives by providing theoretical algorithms tailored to these input spaces. The authors also illustrate the effectiveness of the proposed methods on some real-world datasets.", "questions": "* Could the authors elaborate the context of introducing relaxed ultrametric in Section 3? For example, what kind of issues or counterexamples occur if we decide to stick with using the usual ultrametric definition?\n* I found the formatting of the algorithms somewhat difficult to follow. Also, it seems a bit inconsistent (say for example, Algorithm 7).\n* Do you think one might obtain a provable result on using DC tree (or other ultrametric fitting algorithms) in this framework?", "limitations": "Yes; I am especially interested if similar works on Dasgupta objective can be done.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n* The authors have made a substantial effort to establish a solid foundation for the problems they address.\n* The authors made clear theoretical contributions and demonstrated how it could be beneficial in practice.\n\nWeaknesses:\n* It is hard to get ideas how the algorithms or proofs work.\n* While the authors provide a framing for problems considered, this may not be compelling for everyone.\n* The paper itself is not well self-contained. One should read Appendix carefully to understand the material.", "was_revised": true, "final_justification": "I maintain my positive score. The results look interesting and promising.", "rebuttal": "We thank the reviewer for their helpful comments. Regarding the weaknesses, we will consider ways to present the algorithms in the paper so that they are easier to interpret and will try to minimize the necessity of referring to the Appendix.\n\n### Addressing Questions\n\nQ1) There are three primary reasons for introducing the results over relaxed ultrametrics rather than standard ones:\n- Interestingly, our reduction from (k, z)-clustering to k-center clustering in an ultrametric requires the definition of relaxed ultrametrics in order to go through. Specifically, (k, z)-clustering in a *standard* ultrametric reduces to k-center clustering in a *relaxed* one.\n\n  - The technical reason for this is that, to solve the (k, z)-clustering task in an ultrametric, we evaluate how much the cost would decrease if we placed a center at a specific node. These cost decreases turn out to be a *relaxed* ultrametric, even if the original setting is a regular ultrametric. To see this, consider the cluster tree of two leaf nodes with one parent node. Let the parent node have value 1. Consequently, the k-means solution for $k=1$ has cost 1. If we now place a second center on the open leaf node, our cost *decreases* by 1. As a result, the cost-decrease associated with a leaf node is *strictly positive*.\n\n- It turns out that none of the proofs—either in the k-center or the (k,z)-clustering settings—require that the distance from a point to itself be 0. As a result, we may as well introduce our results in their most general format.\n- This generality proves useful in practice as well. Specifically, the dc-dist is most naturally expressed as a relaxed ultrametric.\n\nQ2) Thank you for the feedback - we will standardize and simplify the presentation of our algorithms. We will also provide context regarding the algorithms in the Appendix in more detail.\n\nQ3) We are not entirely sure what the reviewer means here. Every proof / claim we make for relaxed ultrametrics holds for the dc-distance (which is a relaxed ultrametric) as well as any other (relaxed or standard) ultrametric. Thus, our results show optimal center-based clustering in density-connectivity settings as well.\n\n### Addressing Limitation\n\nWe agree that the connection to trees based on Dasgupta’s objective is an interesting research direction and warrants further investigation for multiple reasons:\n\nFirst, we note that the generalization of Dasgupta’s objective in [1] defines *admissible* cost functions as those whose ground truth solution corresponds to an ultrametric tree (Definition 3.1 in [1]).\n\nSecond, solutions to Dasgupta’s objective are necessarily cluster trees. Thus, to turn this into an LCA-tree, one must find non-decreasing values to assign to the nodes. Often, there is a natural mechanism by which to do this (such as in single-linkage or complete-linkage clustering). As a result, for many solutions to Dasgupta’s objective, our results show that one can subsequently obtain *new* solutions to the objective by running k-median or k-means. This only takes $\\texttt{Sort}(n)$ time. It remains to be seen whether these produce better guarantees, but we suspect that they might in some settings.\n\n---\n\n### References\n\n[1]: Cohen-Addad, Vincent, Varun Kanade, Frederik Mallmann-Trenn, and Claire Mathieu. \"Hierarchical clustering: Objective functions and algorithms.\" Journal of the ACM (JACM) 66, no. 4 (2019): 1-42."}, {"review_id": "qW1wBEFcRy", "reviewer": "Reviewer_VtwA", "summary": "The paper discusses clustering on ultrametrics. They should that the three main center-based clustering problems - k-means, k-median and k-center, can all be solved optimally and quickly in these spaces. Further, the solution space is itself formed by nested clusters. One reason ultrametrics are interesting is their hierarchical structure, making them an example of hierarchical clustering.", "questions": "I refer the authors to my above comments.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "The major strength of the paper is in its usefulness. Hierarchical clustering is very popular, and it's natural to want to cluster on top of such a construction. The fact that the authors show optimally fast run-times for multiple clustering problems using a well-known algorithm is another strength. I plan on using similar techniques in my own research. \n\nThere are however multiple issues that should be addressed to strengthen the paper, and these all revolve around the central motivation and its relationship to previous known results.\n\n- It is known that k-median and k-center can be solves optimally on trees, and I suspect the same holds for k-means due to the same considerations. Surprisingly, this line of research is not mentioned at all in the current paper. The properties of the algorithm should be compared to those for trees, including run-time and hierarchical structure.\n\n- Ultrametrics are a very limited model. The motivation for studying them is typically due to with the general technique of embedding spaces into ultrametics in order to solve some problem in the new space - for example the solution to the k-server problem build on Bartal trees. Such an embedding is generally computationally intense, and also induces very large distortion. This makes the fast and exact solution of the clustering problem on the HST less interesting, since there is already a run-time and distortion overhead induced in the initial step.\n\n- The level of novelty in the current solution is not clear to me. The claim on page 3 that the authors prove \"an elegant unknown property of ultrametrics: all standard center-based clustering tasks... can be solved optimally in any ultrametric\" seems to be an exaggeration. That the problems can be solved on ultrametrics were known, as it evidenced by the literature on clustering on trees, and k-center and k-median have already been studied specifically for ultrametrics. Indeed, while the authors compare themselves to the second algorithm in Cohen-Addad et al., that algorithm was a modification to achieve parallel computation, and is almost as fast as the one presented in the current paper. It would be interesting to know if the algorithm presented there implies similar ones for k-center and k-means - I suspect that it does.", "was_revised": true, "final_justification": "As detailed in the interaction with the authors.", "rebuttal": "We thank the reviewer for the detailed questions and for helping us improve the paper. Below, we address the three weaknesses listed by the reviewer:\n\n### **Related work**\n\nRegarding the discussion of tree clustering literature: we will add this important context in revision, specifically references [1], [2], [3] and [4]. Please let us know if there are also others we should include. However, we believe there are a few important distinctions to be made between our setting and those in the related work:\n- In our setting, the centers can only be placed on leaf nodes\n- Our setting’s distances must be ultrametric, while distances over edge-weighted trees may not be ultrametric in nature.\n\nAs a result, the setting of k-center or (k,z)-clustering over trees is a generalization of our conditions and, consequently, none of our reductions to sorting will necessarily work. We will provide a detailed analysis of the relationships to clustering on trees in the updated text.\n\n### **Ultrametric limitations**\n\nWe disagree that ultrametrics are a limited model. To be clear, we agree with the reviewer that HSTs (e.g., Bartal trees) induce distortion and that their upfront computation may be unappealing if the goal is just to perform clustering using our techniques. However, this is not the use case we are suggesting. Instead, we are arguing that if one has *already* computed an ultrametric (as is common in many settings), then they get many additional clusterings essentially for free. Throughout the literature, there are many settings in which one computes ultrametrics implicitly:\n  - Many standard hierarchical clustering algorithms are ultrametric in nature. For example, single-linkage, complete-linkage, ward-linkage, and min-max linkage all produce ultrametric cluster trees. Our results immediately apply to these settings.\n  - If a solution to the Dasgupta objective is an ultrametric cluster-tree, then our algorithms can be used to obtain new solutions to the objective. We refer to the response to reviewer vbSb for more details.\n  - The DBSCAN* and HDBSCAN algorithms implicitly operate over ultrametrics. These are extremely popular clustering algorithms in practice and our results expand their versatility considerably.\n  - Many HSTs (e.g., Cover trees, Bartal trees, KD trees) are already frequently used to accelerate machine learning and computer graphics tasks.\n\nOur algorithms can be applied \"for free\" in any of the above settings.\n\n### **Novelty**\n\nWe agree that the algorithm in Cohen-Addad et al. [5] is related to our proposed method. Indeed, it was the starting point from which we began considering the problem: our (k, z)-clustering algorithm is structurally very similar to their Algorithm 2. We will make this clearer in the revision. We will also rephrase the sentence so it’s clear there was prior work on optimal center-based clustering in ultrametrics. However, there are several points which we believe support our claim that we show an “elegant, previously unknown property of ultrametrics”:\n- Although it was known that one can perform center-based clustering in trees and ultrametrics, the treatment had been fractured across the literature. The runtimes on trees differ between k-median and k-center, and differ again when we transition to ultrametrics. Moreover, the algorithmic techniques vary as well. Instead, our results show that, when the inputs are ultrametric, the same algorithm (sorting) can be used to solve any center-based clustering task. We believe this to be an elegant result due to its simplicity and its unifying nature.\n- The algorithm by Cohen-Addad et al. does indeed work for k-means on an HST. However, it is not clear that it extends to k-center. Specifically, their Algorithm 1 does, but runs in $O(n^2)$ time (this is essentially the algorithm employed by Beer et al. [6]). It is then not immediately obvious how to adjust Cohen-Addad et al.’s Algorithm 2 to k-center, as their “Benf” function does not apply in the k-center case. Furthermore, their algorithm explicitly relies on the 2-HST structure (which is why they obtain a $\\Delta$ term in their runtime).\n\nThus, our theoretical results generalize (and simplify!) the algorithm from Cohen-Addad et al. – we show that *all* of these tasks can be performed in *any* ultrametric in the *same* runtime using the *same* underlying algorithm.\n\nWe also note that our experimental analysis is significantly more expansive than any which we have found in the literature.\n\n---\n\n### References\n\n[1]: Shah, R. (2003). Faster algorithms for k-median problem on trees with smaller heights.\n\n[2]: Benkoczi, R., & Bhattacharya, B. (2005, October). A new template for solving p-median problems for trees in sub-quadratic time. In European Symposium on Algorithms (pp. 271-282). Berlin, Heidelberg: Springer Berlin Heidelberg.\n\n[3]: Bhattacharya, B., Das, S., & Dev, S. R. (2022). The weighted k-center problem in trees for fixed k. Theoretical Computer Science, 906, 64-75.\n\n[4]: Wang, H., & Zhang, J. (2021). An O(n\\logn)-Time Algorithm for the k-Center Problem in Trees. SIAM Journal on Computing, 50(2), 602-635.\n\n[5]: Cohen-Addad, V., Lattanzi, S., Norouzi-Fard, A., Sohler, C., & Svensson, O. (2021). Parallel and efficient hierarchical k-median clustering. Advances in Neural Information Processing Systems, 34, 20333-20345.\n\n[6]: Beer, A., Draganov, A., Hohma, E., Jahn, P., Frey, C. M., & Assent, I. (2023, August). Connecting the Dots--Density-Connectivity Distance unifies DBSCAN, k-Center and Spectral Clustering. In Proceedings of the 29th ACM SIGKDD conference on knowledge discovery and data mining (pp. 80-92)."}, {"review_id": "QCnP0SS43y", "reviewer": "Reviewer_X4Az", "summary": "This paper shows that given an ultrametric (or equivalently a hierarchical clustering), we can compute all $(k,z)$-clusterings over it very quickly. In other words, this paper shows that once an ultrametric is fit to a given dataset, a host of center-based clusterings (like k-means, k-medians, k-center) can be obtained (essentially) for free for this ultrametric. The paper's main theoretical results are also well augmented with experiments showcasing the potential practical utility of their algorithms for exploratory data analysis of real world data.", "questions": "No significant questions", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Quality: The paper is technically sound with claims that are well supported by both theoretical analysis and also experimental results.\n\nClarity: The paper is overall clearly-written and was easy to read. One suggestion is that Figure 1 in section 1 is not at all helpful for readers at section 1. The paper makes references to Figure 1 in later sections (like section 3, immediately after Theorem 3.3) and it is very inconvenient to go back and compare the notes in section 3 with Figure 1 on the first page. My suggestion is to split up the 3 sub-figures in Figure 1 and place them in the individual related sections of the paper.\n\nSignificance: The paper's results are significant to the ML community. Clustering is a topic that is very much of interest to readers of NeurIPS with several papers related to clustering being published every year at NeurIPS and other related conferences. In particular, the paper's results are related to very popular clustering algorithms like DBSCAN and k-means clustering.\n\nOriginality: Surprisingly, this is the first paper (or that's what the authors claim) to compute center-based clusterings on ultrametrics in a unified manner. This would be very natural to do, and I imagine some enterprising practitioners would have tried off-the-shelf k-means implementations on computed ultrametrics like dc-dist. But it would have been of a more ad-hoc nature...", "was_revised": true, "final_justification": "As I did not have any major questions/comments during the original review, I do not feel there is much need for further discussion from my end. The authors have agreed to improve some minor formatting in the paper which I felt would improve the paper's readability. I would like to maintain my score even after reading the other reviews.", "rebuttal": "We thank the reviewer for their thoughtful comments. We share the reviewer’s surprise that this had not been done before – both because it seems natural to try and because the algorithm turns out to be fairly straightfroward in retrospect (since the problem reduces to sorting).\n\nRegarding the placement of Figure 1: We agree and will split up Figure 1 into the three subfigures which will be shown in the respective sections. We had originally kept it all in one figure in the introductory section due to space constraints, but we agree in retrospect that the figure could be more intuitive."}, {"review_id": "11pBsXVoON", "reviewer": "Reviewer_7zeU", "summary": "This paper presents a significant theoretical and practical advance in the realm of hierarchical clustering in ultrametric spaces. The core contribution is a general theorem (Theorem 4.2) establishing that, given any relaxed ultrametric represented as an LCA-tree, one can compute optimal clusterings for all $k$ ($1 \\leq k \\leq n$) in $\\text{Sort}(n)$ time. This result generalizes beyond the known $k$-center or $k$-median special cases in specific ultrametrics and applies to all standard center-based clustering objectives in any ultrametric setting. The authors complement this theoretical breakthrough with practical experiments demonstrating the competitive accuracy and extremely low runtime overhead of their approach, once the ultrametric ($\\text{dc-dist}$) has been computed.", "questions": "Do the runtime and accuracy results hold similarly if the ultrametric is not dc-dist but one of these HST-based approximations?\nThis would give a broader sense of how sensitive the algorithm is to the choice of ultrametric.", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n(*) Strong Theoretical Generalization:\nThe $\\text{Sort}(n)$ runtime for all $k$ and all center-based objectives in any ultrametric is a powerful unifying result. The paper goes beyond previous specialized treatments (e.g., $k$-center in $\\text{dc-dist}$ or $k$-median in 2-HST) by showing that the same principle holds in full generality.\nI would have already accepted the paper with just that.\n\n(*) Clear and Constructive Proofs:\nThe proofs, particularly for Theorem 4.2 and its generalizations in Appendix A.4, are clear, constructive, and mathematically rigorous. The reliance on the LCA-tree’s hierarchical properties and the strong triangle inequality in ultrametrics is well-argued and elegant.\n\n(*) Practical Impact:\nWhile the ultrametric fitting (e.g., $\\text{dc-dist}$ computation) remains $O(n^2)$ in the dense case, the paper correctly separates this from the subsequent $\\text{Sort}(n)$ clustering steps. This is a valuable insight for practitioners seeking to re-use a single ultrametric representation for multiple clustering tasks.\n\n(*) Empirical Evaluation:\nThe experiments (Figure 3, Figure 4, and associated tables) convincingly demonstrate that their framework can produce clusterings with quality competitive to widely-used methods (DBSCAN, HDBSCAN) while being orders of magnitude faster once the ultrametric is precomputed.\n\n(*) Clarity of Writing and Visuals:\nThe paper is clearly written overall. Figures 4 and 8 provide helpful visual intuition on how different partitioning methods ($k$-center, $k$-median, $k$-means) behave on the $\\text{dc-dist}$ ultrametric.\n\n(*) Well-crafted Figures and Thoughtful Acronym:\nI really appreciate the craft that went into the figures and I really appreciate shipping a nice acronym. \n\n\n\nWeaknesses:\n\n(*) Ambiguity in Linking Visuals to Algorithm:\nWhile Figure 4b showcases the DC-tree-based results that belong to the authors’ algorithm, this connection is not immediately obvious from the figure’s caption alone. Explicitly labeling these as “ours” or clarifying in the caption that they are the authors’ algorithmic contribution would improve clarity.\n\n(*) Preprocessing Assumptions:\nThe authors could make it even clearer in the introduction and algorithm sections that their $\\text{Sort}(n)$ guarantee assumes the LCA-tree is already computed, to avoid possible confusion for readers new to the area.", "was_revised": true, "final_justification": "I maintain my strong support of the paper.", "rebuttal": "We thank the reviewer for their valuable feedback and are happy that they like our work.\n\n---\n\n### Addressing weaknesses:\n\nFollowing your advice, we’ll emphasize that the runtime guarantees refer to the step after computing the ultrametric.\n\nHowever, we would like to note that in Figure 4, the clustering results for using different HSTs *and* the dc-dist results are all “ours”. I.e., our algorithm shows how to perform center-based clustering in ultrametrics optimally. Thus, Figure 4a shows “our” clustering results in various HST ultrametrics, while Figure 4b shows “our” clustering results on the dc-dist ultrametric.\n\n---\n\n### Addressing questions: \n\nThe runtime results (building a new hierarchy and extracting the clustering) are independent of the chosen (precomputed) ultrametric. \n\nIn the Appendix in Table 5, we further compare all ultrametric construction times: KD trees can be constructed the fastest, followed by Cover trees. Depending on the datasets, the HST-DPO tree construction is sometimes faster than building the DC tree, but for very high dimensions, building the DC tree is always faster.\n\nFurthermore, the accuracy depends on the dataset and type of clusters contained in it: as shown in the Appendix in Tables 6 (ARI), 7 (NMI), 8 (AMI), and 9 (CC), density-based clusters can best be found with the density-connectivity distance. In contrast, linearly separable clusters can be detected by using HST ultrametrics. In short: if the ultrametric fits the underlying assumptions on the data, then our techniques provide fast and consistent results."}]

Author rebuttal:

Meta-review: This paper presents a unifying theoretical framework for clustering in ultrametric spaces. It shows that all center-based clustering objectives (k-means, k-median, k-center for all k) can be solved optimally by constructing and partitioning hierarchy in the ultrametric space (SHiP). The resulting algorithm is remarkably efficient as these center-based clustering tasks can be reduced to sorting. Experiments on synthetic and real-world datasets, particularly with density-connectivity ultrametrics, demonstrate that the framework is competitive with typical clustering algorithms at reduced computational cost. The reviewers received the submissions positively, acknowledging the work’s soundness and potential impact; yet raised concerns about: novelty positioning (some overlap with prior work on clustering in ultrametrics/trees), need for non-standard relaxed ultrametrics, clarity (dense exposition, heavy reliance on appendices), and limited evaluation scope beyond dc-dist. We thank the reviewers and authors for engaging during rebuttal period towards making the paper better. The author response helped resolve most of reviewer concerns leading to some reviewers even raising scores. Overall, despite clarity and novelty caveats, the paper should accepted as it is technically solid, unifies important concepts, and provides a promising practical framework.
Decision: Accept (poster)