Ultrametric Cluster Hierarchies: I Want ‘em All!

We thank the reviewer for their valuable feedback and are happy that they like our work.

Addressing weaknesses:

Following your advice, we’ll emphasize that the runtime guarantees refer to the step after computing the ultrametric.

However, 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.

Addressing questions:

The runtime results (building a new hierarchy and extracting the clustering) are independent of the chosen (precomputed) ultrametric.

In 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.

Furthermore, 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.

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).

Regarding 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.

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:

Related work

Regarding 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:

• In our setting, the centers can only be placed on leaf nodes
• Our setting’s distances must be ultrametric, while distances over edge-weighted trees may not be ultrametric in nature.

As 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.

Ultrametric limitations

We 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:

• 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.
• 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.
• The DBSCAN* and HDBSCAN algorithms implicitly operate over ultrametrics. These are extremely popular clustering algorithms in practice and our results expand their versatility considerably.
• Many HSTs (e.g., Cover trees, Bartal trees, KD trees) are already frequently used to accelerate machine learning and computer graphics tasks.

Our algorithms can be applied "for free" in any of the above settings.

Novelty

We 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”:

• 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.
• 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).

Thus, 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.

We also note that our experimental analysis is significantly more expansive than any which we have found in the literature.

References

[1]: Shah, R. (2003). Faster algorithms for k-median problem on trees with smaller heights.

[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.

[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.

[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.

[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.

[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).

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.

Addressing Questions

Q1) There are three primary reasons for introducing the results over relaxed ultrametrics rather than standard ones:

• 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.

  • 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.

• 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.

• This generality proves useful in practice as well. Specifically, the dc-dist is most naturally expressed as a relaxed ultrametric.

Q2) 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.

Q3) 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.

Addressing Limitation

We agree that the connection to trees based on Dasgupta’s objective is an interesting research direction and warrants further investigation for multiple reasons:

First, 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]).

Second, 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 $`Sort`(n)$ time. It remains to be seen whether these produce better guarantees, but we suspect that they might in some settings.

References

[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.

Thank you for the reply and for elaborating on the question. In reference to lines 343-345, we agree that there are likely theoretical statements and guarantees that can be made for clustering with the dc-dist on, for example, Euclidean data. In essence, it seems that robust single-link and dc-dist relationships should reliably emphasize dissimilarities between points in Euclidean space.

Specifically, assume there are two dense clusters in Euclidean space, $C^1$ and $C^2$, which are only separated by a small distance. Then some intra-cluster Euclidean distances might be larger than some inter-cluster ones. I.e., there might exist points $c_i^1, c_j^1 \in C^1$ and $c_i^2, c_j^2 \in C^2$ such that $d(c_i^1, c_j^1) = d(c_i^2, c_j^2) \gg d(c_j^1, c_i^2)$. However, under the dc-dist, this would be resolved -- points in the same cluster are treated as mutually close and we get that all intra-cluster distances are smaller than all inter-cluster distances.

We believe that such guarantees for the dc-dist would be interesting avenues for future research.