Efficient Centroid-Linkage Clustering

Summary

The authors give an algorithm that approximates a centroid linkage clustering. Their algorithm is fast both in theory and in practice. The algorithm is based on a novel fully dynamic data structure for nearest neighbors which is of independent interest.

Strengths

The proposed algorithm is a significant strengthening compared to existing algorithms, in particular from a theoretical point of view: while it is known that under some standard complexity theoretic assumptions most hierarchical clustering methods need at least (essentially) quadratic runtime, the proposed approximation algorithm significantly breaks this barrier. This is also underlined by experimental results. Interestingly, approximation does not seem to decrease the quality of the clustering. Indeed, as can be seen in Table 1, higher approximation values often give better results than "better" approximations or even optimal algorithms.

Weaknesses

The techniques are very much geared towards the centroid linkage function. It could be interesting to mention how much of it could potentially generalize to other linkage functions and where the bottlenecks for full generalization lie.

Questions

-Do you have any intuition as to why "worse" approximation factors often seem to give better clustering results (as your Table 1 indicates)?

Rating

9

Confidence

3

Soundness

4

Presentation

4

Contribution

4

Limitations

The limitations are addressed in the checklist.

Summary

The paper deals with centroid-linkage agglomerative clustering (centroid HAC), where the distance between two clusters is the distance between their centers. It presents a subquadratic time algorithm (approximate centroid HAC) that, instead of requiring the two closest clusters to be merged at each step, it allows for any two clusters to be merged if their distance is within a factor of c of that of the two closest clusters.

Strengths

S1. A dynamic approximate NN search algorithm with adaptive updates is proposed. S2. A centroid-linkage HAC algorithm is presented that exploits the approximate NN search algorithm. S3. Theoretical performance bounds are presented and proved. S4. Empirical evaluation indicates that the approximate centroid HAC algorithm provides clustering results very close to exact centroid HAC, but with a considerable speedup in execution time.

Weaknesses

W1. It is confusing that the ANNS algorithm used in the experiments is not the same as the one proposed and analyzed in Section 3 of the paper (Algorithm 1). Since the focus of the paper is on clustering, this issue creates confusion regarding the actual contribution of this work. Perhaps the ANNS algorithm (contribution 2) is better to be presented in a forum related to data structures. W2. It is not clear if the ‘approximate centroid HAC’ idea is novel or not (independently of the ANNS algorithm used in the implementation).

Questions

Q1, Q2. See comments W1, W2 above. Q3. How does the method compare to other approximate HAC methods in terms of NMI? In Figure 3 running time comparison is provided. In Figure 5 some results are provided on the Iris dataset, but I cannot see any general conclusions. Q4. It is meaningless to compare using small datasets, since the optimal solution can be quickly obtained. More experiments using big would add value to the paper. Q5. Is it possible to have a (rough) estimate of the increase in execution time as the value of \epsilon decreases?

Rating

6

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors discuss the limitations. I do not see any potential negative societal impact of this work.

Summary

This paper considers the design of approximate versions of the centroid linkage method for hierarchical clustering. The exact version of centroid linkage requires $\Theta(n^2)$ time, but it could be possible to do better if some relaxation is allowed. This paper shows how to get a $c$-approximate centroid linkage clustering in sub-quadratic time by using a dynamic approximate near-neighbor search data structure that has guarantees against adaptive updates. This is non-trivial since the distance between centroids is non-monotone: after merging a pair of clusters, the resulting distance between centroids of other clusters could go down. To complete the result, they construct such a data structure that supports insertion, deletion, and queries against adaptive updates with sub-linear running time. An extensive experimental evaluation is performed to test a practical variant of the proposed algorithm on standard benchmark datasets against the exact centroid linkage method provided by the fastcluster library, a standard library for hierarchical clustering algorithms). The proposed method either shows good performance or minimal loss against the exact method for a variety of clustering metrics and significant speedup over the exact method.

Strengths

There has been much work on scaling up hierarchical clustering methods by considering approximation, particularly linkage methods such as single linkage, average linkage and ward's method. In contrast, there has been less (but non-zero) work on centroid linkage. This paper provides an elegant and cleanly described solution to this problem.

Weaknesses

- The experimental evaluation isn't for the algorithm that is proposed theoretically, but instead for a variant with several practical modifications (e.g., using graph-based ANNS which may not have the same theoretical guarantees as LSH-based ones). - For the experiments, the authors also consider running the algorithm with 192 cores. For this case, it seems that fastcluster cannot make use of the additional cores, which seems to be an unfair comparison. However, they do use an exact version of the new algorithm which does make use of the additional cores, providing a more fair comparison.

Questions

Minor comment - the usage of $Q$ for both covering net and priority queue is somewhat confusing. Please consider modifying this.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Limitations are made clear through a clear description of assumptions. I don't see potential negative societal impact from this work since it develops more efficient versions of already widely-used algorithms.

Summary

Paper studied Hierarchical clustering algorithm. HAC is popular method where n points are initially singleton clusters (leaves). At each step, two clusters are merged, and the process is continued until one giant cluster of all n points (root) remains. THe merging process gives a hierarchy or nested clusterings. Depending on which clusters are merged ,the algorithm differs. Common methods are single linkage where the distance between clusters is in terms of min x in C_1 y in C_2 d(x,y). Another method which is focus of current undertaking is centroid linkage, which is d(C_1, C_2) = dist(mu_1, mu_2) where mu_i is centroid vector of cluster i. Technical point of view: Interestingly, after merging two clusters,the best inter-cluster distance can sometimes decrease, so it is not monotone increasing over time as in single linkage. Since many lower bounds exist showing that we need theta(n^2) time to do HAC, paper studies approximate HAC, where we merge any apprxoximately closest clusters instead of exact closest clusters. To do this, authors capture the HAC problem as that of approximate nearest neighbors over dynamic dataset. Each cluster is a point in the ANN index, and when 2 clusters merge, we capture by 2 deletions and 1 insertion. Then using a priority queue where each cluster maintains its closest distance to other clusters, the authors show how to maintain this PQ online, and use this to quickly determine which clusters to merge. To make it all work they devise provable new algorithms for dynamic ANN algorithms using LSH which can handle adaptive inserts/deletes (which is needed for this problem). Apparently, prior work only handles non-adaptive.

Strengths

* Important problem of getting sub-quadratic algorithms for hierarchical clustering, quite reasonably well written paper. * Theoretical backing + empirical applications using the theory ideas are given, which is nice * Good set of evaluations and the numbers are great -- quality is better and significantly faster. * The dynamic ANN algorithm introduced in this paper ideas could be useful in other settings also.

Weaknesses

Datasets chosen for evaluation can be more diverse. The theoretical result can be presented with more rigor -- For example, I could not follow what objective function they are presenting a c-apprxoximation for the HAC problem in Theorem 5. The technical reason/idea behind why they are able to convert a non-adaptive ANN structure to adaptive using the power-of-two size indices is not explained well, seems like the crux of the paper but missing in detail. Is there precedent for using such ideas to make non-adaptive inputs into adaptive inputs?

Questions

In Line 140, don't you want the weighted average and not the weighted sum? What is the objective function you use to compare the quality of HAC soluton and prove approximation factor gaurantee? Why not use more modern-day neural-network inspired clustering datasets for benchmarking, as it will be an important use-case going forward (like the OpenAi embeddings or more BERT-based embeddings). What is SOTA known for other linkage functions in HAC like single linkage and average linkage? Do your ideas extend there also? Which linkage is most used in practice? You cite [2, 14] for dynamic non-adaptive ANN, However I cant find the corresponding results in either. Please be more specific.

Rating

6

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

Would be good to mention a more detailed limitations section apart from those mentioned in conclusion / open problems.