We thank the reviewer for their comments and suggestions. We respond now to the specific questions of the reviewer.

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.

This is a great question and something that we will clarify when discussing our results in the paper. We believe that our techniques should extend naturally to other linkage functions for spatial hierarchical clustering that incorporate centroids, such as Ward’s linkage. Investigating whether any centroid-based method expressed in the Lance-Williams formulation could take advantage of our approach is an interesting question for future work.

On the more theoretical side, we note that our theoretical results for ANNS could be used more generally in other clustering algorithms that require adaptivity.

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

This is an interesting question, and as briefly mentioned in the paper, we do not have any scientific explanation for this phenomenon. One possibility is that as \eps increases, the decision process slowly incorporates an approximate single-linkage-like behavior, which could be beneficial for certain datasets. We plan to include several additional results on clustering datasets with ground truth in the final version of the paper (e.g., on ImageNet, Reddit, and arXiv embeddings as discussed in our response to reviewer Dgto) which will provide more data on the effect of increasing \eps.

We thank the reviewer for their comments and suggestions. We respond now to the specific questions of the reviewer.

Q1/W1: Coherence and clarifying why we use a different ANNS algorithm in theory and in practice.

We thank the reviewer again for raising this question, which we agree is important. We present a longer discussion about this question in the overall response at the top of our rebuttal.

Q2/W2: Novelty of “approximate centroid HAC”

We believe that the formulation of approximate HAC is certainly not novel, and there has been a number of interesting works in the past few years exploring similar notions of approximation for other linkage functions for dissimilarity and similarity (or graph) settings (see for example references [1, 5, 11, 12, 13, 21] which all deal with similar notions of approximation for other linkage functions). However, we strongly believe the techniques we introduce and leverage for obtaining our results for c–approximate HAC are novel, and have not been used in the literature before, and are not simple extensions of known techniques.

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

We thank the reviewer for this question; we will add a better explanation of how the NMI of our approximate HAC methods compares with the exact method in the main body of the paper. We included a broader discussion of these results on more datasets in the appendix, which we will move into the main body of the paper. The main result is that for modest values of \eps (e.g., \eps=0.1) the approximate method consistently gets NMI within a factor of 2% of that of the exact algorithm.

Q4: Using larger datasets to show more meaningful scaling results

In this paper, we considered standard clustering benchmark datasets at three different scales: small, medium, and large. The small datasets (e.g., iris, faces, etc.) and medium-sized datasets (e.g., MNIST, birds, where embeddings for the latter are obtained via neural network-based methods) are labeled and are used for our quality evaluation experiments. As the reviewer correctly pointed out, the exact algorithms run very fast on the small datasets, however, they do not scale effectively to medium and larger datasets due to their quadratic running time.

Notably, the approximate HAC algorithm achieves nearly 30x speedup on MNIST and 60x speedup on Birds with 192 threads; we will include these running time results in the revised version. For quality evaluation on large datasets, we plan to add three new embedding-based datasets that come with ground truth which we described in the global response. If the reviewer has any other suggestions for datasets to cluster with meaningful ground truth labels we would be delighted to include them in our paper.

We would like to clarify that the benchmark datasets considered are consistent with multiple recent works on graph and pointset clustering (see for example references [13, 14, 38]). Additionally, we plan to test the scalability of our approximate HAC algorithm on larger ANN benchmark datasets (e.g., Wikipedia-Cohere ~30M) in the revised version. However, since the algorithm is sequential, we do not expect it to scale to billion-sized datasets. Developing an efficient parallel algorithm for approximate Centroid HAC and other linkage criteria is an interesting future direction to address this issue.

Q5:Execution time v/s $\epsilon$

This is a great question and something we investigated—please see Figure 3(c) in the paper, which illustrates the trend in execution time as $\epsilon$ decreases.

We thank the reviewer for their comments and suggestions. We respond now to the specific questions of the reviewer.

“Datasets chosen for evaluation can be more diverse.”

To address this point we have assembled several new clustering datasets with ground truth from existing sources (which we will make publicly available). The datasets are described in more detail in the global response. We will include quality and scalability results on these datasets, which we hope will address the reviewers concern.

c-approximation for the HAC problem in Theorem 5

Thanks for pointing this out. The definition of c-approximate HAC is given on l138. We will improve the writing to clarify this.

“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?”

We will add more intuition and improve the writing for the ANNS section. The power-of-two method is known as merge and reduce and is an established technique (e.g. see line 197) for turning static data structures into dynamic ones. This allows us to insert new points to query against but to support adaptive query points we introduce covering nets.

Merge-and-reduce: The problem that this fixes is that ANNS data structures for Euclidean distance are static meaning we can’t insert new points to query against. The idea is that we will have buckets labeled 0, 1, … , log(n) where bucket i will hold a single static ANNS data structure with at most 2^i points. To insert a point to query against we will add it to bucket 0. Then while there is a bucket i with “loose” points that are not in an ANNS data structure (there will be at most one at any time):

• If there are at most 2^i total points in bucket i, build a new ANNS with all points in bucket
• Else move all points from bucket i to bucket i+1 as “loose” points

Roughly speaking, in bucket log(n) - i it will take time (n/2^i)^(1+epsilon) to construct an ANNS but we will only ever have to construct 2^i ANNSs in that bucket. It follows that we will only spend at most n^(1+epsilon) time constructing ANNSs for each of the log(n)+1 buckets. In the actual proof we charge the running time to the points instead of the buckets. To query or delete we only have to query or delete from at most a single static ANNS in each bucket.

Covering net: ANNS data structures assume that query points are non-adversarial. Suppose we are given a point p that we will want to find an approximate nearest neighbor for in some set S. If we construct the ANNS on S then whp it will return an approximate nearest neighbor for p when queried. Given a set of query points that is not too large we can union bound to say that the ANNS will return an approximate nearest neighbor for all of them. However, in the adaptive case we must assume that an adversary who knows the randomness of the ANNS data structure gets to pick the query point. Since we can’t union bound against the infinite possible query points we introduce covering nets. A covering net is a finite set of points such that every possible query point is near a point in the covering net. Then for every query we round it to a point in the covering net and find an approximate nearest neighbor for that point. This allows us to union bound against only the points in the covering net at the cost of picking up a small additive error in the query.

“In Line 140, don't you want the weighted average and not the weighted sum?”

Yes, thank you for flagging this.

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

We definitely agree with the importance of this use case. However, we are not aware of very many publicly available datasets of this sort that would come with ground truth clustering labels. We note that in our paper, we have used one embedding-based dataset (see Appendix E for the description of the birds dataset); we will also add three new embedding-based datasets that come with ground truth which we described in the global response. If the reviewer has any other suggestions for datasets to cluster with meaningful ground truth labels we would be delighted to include them in our paper.

“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?”

Computing single-linkage clustering can be achieved by first computing an MST of the input points and then applying a simple post processing step. For the complexity of Euclidean MST, see https://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree#Computational_complexity.

In the case of average linkage, the state of the art is a paper we cite: https://papers.nips.cc/paper_files/paper/2019/hash/d98c1545b7619bd99b817cb3169cdfde-Abstract.html

However, the proposed algorithm to the best of our knowledge has not been implemented, likely due to the somewhat large overhead of efficiently computing the average linkage distance. Applying our techniques to average linkage, which seems to be a harder problem than the one we address, is an interesting open problem.

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

Thank you for the suggestion. We will add a section outlining two main limitations:

• the use of different ANNS data structure in the theoretical and empirical results.
• quality evaluation limited to medium-sized datasets, due to the lack of suitable publicly available embedding datasets

We thank the reviewer for their comments and suggestions. We respond now to the specific questions of the reviewer.

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

We thank the reviewer for raising this important point, which we acknowledged in the limitations section of our submission. We present a longer discussion about this question in the overall response at the top of our rebuttal.

W2: 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.

We actually also evaluated all algorithms in the sequential setting and still obtained a speedup (even on one core) over fastcluster. The results for our single core running times are in Figure 3(a). While it is true that fastcluster can’t make use of the additional cores, we view this as an advantage of our algorithm. The results with many cores are in Figure 3(b). As the reviewer notes, the runtime of fastcluster is the same in both scenarios.

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

Thank you for pointing this out, we will fix it.