Efficient Centroid-Linkage Clustering
Authors: Mohammadhossein Bateni
Laxman Dhulipala
Willem Fletcher
Kishen N Gowda
D Ellis Hershkowitz
Rajesh Jayaram
Jakub Lacki
Venue: NeurIPS 2024 poster (2024)
Keywords: clustering
hierarchical agglomerative clustering
hac
centroid linkage
algorithm
dynamic nearest neighbor search
adaptive updates
Primary area: infrastructure
TL;DR: We give an efficient algorithm for Centroid-Linkage Hierarchical Agglomerative Clustering (HAC), which computes a $c$-approximate clustering in $n^{1+1/c^2+o(1)}$ time and obtains significant speedups over existing baselines.

Abstract: We give an algorithm for Centroid-Linkage Hierarchical Agglomerative Clustering (HAC), which computes a $c$-approximate clustering in roughly $n^{1+O(1/c^2)}$ time. We obtain our result by combining a new centroid-linkage HAC algorithm with a novel fully dynamic data structure for nearest neighbor search which works under adaptive updates.

We also evaluate our algorithm empirically. By leveraging a state-of-the-art nearest-neighbor search library, we obtain a fast and accurate centroid-linkage HAC algorithm. Compared to an existing state-of-the-art exact baseline, our implementation maintains the clustering quality while delivering up to a $36\times$ speedup due to performing fewer distance comparisons.

Efficient Centroid-Linkage Clustering
MohammadHossein Bateni
Laxman Dhulipala University of Maryland College Park, USA
Willem Fletcher Brown University Providence, USA
Google Research New York, USA
Kishen N. Gowda University of Maryland College Park, USA
D Ellis Hershkowitz Brown University Providence, USA
Rajesh Jayaram Google Research New York, USA
Jakuh E-cki Google Research New York, USA
Abstract
We give algorithm for Centroid-Linkage Hierarchical Agglomerative Clustering (HAC), which computes c-approximate clustering in roughly n1+0((/e")) time. We obtain our result by combining new Centroid-Linkage HAC algorithm with a novel fully dynamic data structure for nearest neighbor search which works under adaptive updates.
We also evaluate our algorithm empirically. By leveraging a state-of-the-an neirest-neighbor search library, we obtain a fast and accurate Centroid-Linkage HAC algorithm. Compared an existing state-of-the exact baseline, our implementation maintains the clustering quality while delivering up to a 36x speedup due to performing fewer distance comparisons.
Introduction
Hierarchical Agglomerative Clustering (HAC) is widely-used clustering method, which is available in many standard data science libraries such as SciPy [39], scikit-learn [34], fastcluster [29], Julia [20], [35], MATLAB [28], Mathematica [25] and many more [31, 32, 36]. HAC takes input collection of n points in Rd. Initially, it puts each point in separate cluster, and then proceeds in up steps. In each step, it merges the two "closest" clusters by replacing them with their union.
The formal notion closeness given by a linkage function; choosing different linkage functions gives different variants of HAC. In this paper, study Centroid- Centroid-Linkage HAC wherein the distance between two clusters is simply the distance between their centroids. This method is available in most of the aforementioned librarics. Other common choices include single-linkage (the distance between two clusters is the minimum distance between a point in one cluster and a point in the other cluster) or everage-linkage (the distance between two clusters the average pairwise distance between them).
HAC's applicability has been hindered by its limited scalability. Specifically, running HAC with any popular linkage function requires essentially quadratic time under standard complexity-thorry assumptions. This because (using most linkage functions) the first step of HAC equivalent to finding the closest pair among the input points. In high-dimensional Euclidean spaces, this problem was shown to (conditionally) require 2(n²-a) time for any constant a > 0 [23]. In contrast, solving HAC in essentially ((n²) time easy for many popular linkage functions (including centroid, single, average, complete, Ward), as suffices to store all-pairs distances between the clusters in a priority queue and update them after merging each pair of clusters.
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

In this paper, we show how to bypass this hardness for Centroid- Linnkae HAC by allowing for approximation. Namely, we give a subquadratic time algorithm which, instead of requiring that the two closest clusters be merged in each step, allows for any two clusters to be merged if their distance within a factor of c 2 1 of that of the two closest clusters.
Contribution 1: Meta-Algorithm for Centroid-Linkagee Our first contribution is a simple meta- algorithm for approximate Centroid-Linkage HAC. The algorithm assumes access to dynamic data structure for approximate nearest-neighhor search (ANNS). A dynamic ANNS data structure maintains a collection of points S C R subject to insertions and deletions and given any query point u E S returns an approximate nearest neighbor V E S. Formally, for a c-approximate NNS data structure, v satisfies (u, v) S min (u,, Here, D).--) denotes the Euclidean distance. By using different ANNS data structures we can obtain different Centroid-Linkage HAC algorithms (which is why we call our method a mneta-algorithm) We make use of an ANNS data structure where the set of points 5 is the centroids of the current HAC clusters. Roughly, our algorithm runs in time (n) times the time it takes an ANNS data structure to update or query.
While finding distances is the core part of running HAC, we note that access to an ANNS data structure for the centroids does not immediately solve HAC. Specifically, an ANNS data structure can efficiently find (approximate) nearest neighbor of single point, but running HAC requires to find an (approximately) closest pair among all clusters. Furthermore, HAC must use the data structure in dynamic setting, and so an update to the set of points S (caused by two clusters merging) may result in many points changing their nearest neighbors.
Our meta-algorithm requires that the dynamic ANNS data structure works under adaptive updates. Namely, it has to be capable of handling updates, which are dependent on the prior answers that returned (as opposed to an ANNS data structure which only handles "oblivious" updates).
To illustrate this, consider randomized ANNS data structure DD Clearly, query to DD often has multiple correct answers, as DD can return any near neighbor within the promised approximation bound. As result, an answer
query issued to D dependent on the internal randomness of D. Let us assume that D is used within a santrodd-linage HAC algorithm A and upon some query returns a result u. Then, algorithm A uses u to decide which two clusters merge, and the centroid p of the newly constructed cluster is inserted into D. Since depends on u, which in turn is a function of the internal randomness of D, we have that the point that inserted into D is dependent on the internal randomness of the data structure. Hence, it is not sufficient for A to return a correct answer for each fixed query with high probability (meaning at least 1 - 1/poly(n)). Instead, A must be able to handle queries and updates dependent on its internal randomness. We note that similar issue is prevalent in many cases when randomized data structure used as a building block of an algorithm. As result, the subtle notion of adaptive updates is major area of study [40, 7, 33, 22, 21].
Contribution 2: Dynamic ANNS Robust to Adaptive Updates. Our second contribution is dynamic ANNS data structure for -ine-iimensional Euclidean spaces which, to the best of our knowledge, is the first one to work under adaptive updates.
To obtain our ANNS data structure, we show a black-box reduction from an arbitrary randomized dynamic ANNS data structure to one that works against adaptive updates (see Theorem 2). The reduction increases the query and update times by only Olog n) factor. We apply this reduction to a (previously known) dynamic ANNS data structure which is based on locality-sensitiv hashing [3, 19] and requires non-adaptive updates.
By combining our dynamic ANNS data structure for adaptive updates with our meta-algorithm, we obtain an (c)) -pprooxiie Centroid-Linkagn HAC algorithm which runs in time roughly n 1+1//2
Furthermore, our data structure for dynamic ANNS will likely have applications beyond our HAC algorithm. Specifically, ANNS is commonly used as a subroutine to speed up algorithms for geometric problems. Oftentimes, and similarly to HAC, formal correctness of these algorithms require ANNS data structure that works for adaptive updates but prior work often overlooks this issue. Our new data structure can be used fix the analysis of such works. For instance, an earlier work on subquadratic HAC algorithms for average- and Ward- Wand-linkage [1] overlooked this issue and our new data structure
We note that the notion of ANNS that we use is, in fact, slightly more general than this. 2 "Other papers sometimes refer to this property as working against adaptive adversary.
2

---

fixes the analysis of this work. 3 Similarly, a key bottleneck in the dynamic k-centers algorithm in [5] was that it had run nearest neighbor search over the entire dataset (instead of just the k-centers). By replacing the ANNS data structure used therein with our ANNS algorithm, we believe that that the n running times from that paper could be improved to k..
Contribution Empirical Evaluation Centroid-Linne Linkage meta algorithm to obtain an efficient HAC implementation. We use a state-of-the-ard static library for ANNS that we extend to support efficient dynamic updates when merging centroids.
HAC. Finally, we use our Centroid-
We empirically evaluate our algorithm and find that our approximate algorithm achieves strong fidelity with respect the exact centroid algorithm, obtaining ARI and NMI scores that are within 7% of that of the exact algorithm, while achieving up to 36x speedup over the exact implementation, even when both implementations are run sequentially. Our implementation can be found at https: : //tgtttt.bb/t//// com/ ki shenl9 /CCentoiinnAC..
We note that the ANNS we in the empirical evaluation of our meta-algorithm is different from our new dynamic ANNS (Contribution 2). This is because modern practical methods for ANNS (e.g.. based on graph-based indices [38, 18)) have far surpassed the efficiency of data structures for which rigorous theoretical bounds are known. Closing this gap is major open problem.
1.1 Related Work
Improving the efficiency of HAC has been an actively researched problem for over 40 years [8, 31, 30, 32]. major challenge common multiple linkage functions has been to improve the running time beyond (n=²), which is the time it takes to compute all all-pairs distances between the input points. For the case of -in-dimessional Euclidean spaces, a running time of o(n?) is possible for the case of squared Euclidean distance and Ward linkage, since the ANNS problem becomes much easier in this case [41]. However, breaking the (n²2) barrier is (conditionally) impossible in the case of high-dimensional Euclidean spaces (without an exponential dependence on the dimension) [23].
To bypass this hardness result, recent line of work focused obtaining approximate HAC algorithms [26]. Most importantly, Abboud, Cohen-Addad and Houdrouge [1] showed an approximate HAC algorithm which runs in subquadratic time for Ward and average linkage. These algorithms rely on the fact in the case of these linkage functions the minimum distance between two clusters can only increase as the algorithm progresses, which is not the case for centroid linkage; e.g. consider 3 squi-distany points as in Figure I. We also note that, as mentioned earlier, our dynamic ANNS
y/i
(a) First merge.
(b) Result of merge.
(c) Second merge.
(d) Result of merge.
Figure I: 3 points in R² initially all at distance 1 showing Centroid-Linkage HAC merge distances can decrease. la/ / 1b and /c/ 1d give the the first and second merges with distances 1 and v3/2 < 1 respectively.
data structure fixes a gap in the analysis of both algorithms in the paper. In fact, not only can the minimum distances shrink when performing Centroid-Linnage HAC, but when doing O(1)- approximate Centroid-L.in Linkage HAC distances can get arbitrarily small; see Figure 2. This presents an additional issue for dynamic ANNS data structures which typically assume lower bounds on minimum distances.
Compared to the algorithm of Abboud, Cohen-Addad and Houdrouge, centroid- linkage HAC algorithm introduces two new ideas. First, we show how to handle the case when the minimum
We contacted the authors of [1] and they confirmed this gap in their analysis.

---

(a) First merge.
(b) Result of merge.
(c) Second merge.
(d) Result of merge.
Figure 2: 3 points in IR (two of which are initially distance 1) showing that ((1) apprrxxait Centroid-Linkan HAC can arbitrarily reduce merge distances. / 2b and 2d give the the first and second merges with distances and << respectively; centroids are dashed circles.
distance between two clusters decreases as result of two cluster merging. Second, we introduce an optimization that allows us not consider each cluster at each of the (logarithmically many) distance scales. This optimization improves the running time bound by a logarithmic factor when each merge "makes stale" small number of stored pairs and in practice the number of such stale merges occur only 60% of the time (on average) compared to the number of actual merges performed.
Another line of work considered different variant of HAC, where the input is weighted similarity graph [15-17, 6]. The edge weights specify similarities between input points, and lack of edge corresponds to similarity value of 0. By assuming that the graph is sparse, this representation allows bypassing the hardness of finding distances, which leads to near-linear- lenear-tiiteee approximate algorithms for average-linkage HAC [15], well to efficient parallel algorithms [16, 6].
In terms of the theoretical and empirical part this paper considering different algorithms, such gap has also been observed for various other prominent clustering algorithms. For instance, for correlation clustering, while the best known algorithms are obtained by solving linear program (see [9]), in practice simple local Baarcch/Lovain---e based algorithm is used (see section 4. of [2]). For modularity clustering, the best known approximation is obtained by solving an SDP [24]. Again, Louvain-based algorithms are used in practice. In the case of k-means, while the best known approximation is constant obtained via the primal-dual method [10], practice Lloyd's heuristic paired with k-means++ seeding is used which has logarithmic approximation guarantee. For balanced graph partitioning, coarsening combined with a brute-foree algorithm is used to obtain the best results in practice. On the other hand, the algorithms for solving the corresponding theoretical formulations, i.c. balanced cut and multiway cut, are entirely different.
2 Preliminaries
In this section, we review our conventions and preliminaries. Throughout this paper, we will work in d-dimensional Euclidean space gd. We will use D)..)) for the Euclidean metric Rdd that is, for r, E Rd, the distance between x and is D(x,)) == V, (al( - y/d) where x[i] and yft] are the ith coordinates of x and y respectively. Likewise, we let D(x, Y) == mingey D(x, y) for Y c Rd
2.1 Formal Description of Centroid-Linnkae HAC
While we have described centroid-linkage in a cluster-centric way (see Appendix for a formal cluster-centric definition), will be more useful an equivalent centroid-centric definition.
Specifically, we can equivalently define c-approximate Centroid-Linkan HAC as repeatedly "merging centroids". Initialize the set of all centroids C P and weight w, for each E C; these weights will encode the cluster sizes of each centroid. Then, until |C| = we do the following: let f, C' be pair of centroids satisfying
D 0) Sc min D(x,8)
Z.YEC
where the min is taken over distinct pairs; merge & and 9 into their weighted midpoints by removing them from C, adding 2 (wy + w/0)/ (w; + wg) to C and setting w, + wig Also, note that (exact) Centroid-Linkage HAC is just the above with
2.2 Dynamic Nearest-Neighhor Search
We define a dynamic ANNS data structure. Typically, dynamic ANNS requires lower bound on distances; cannot guarantee this for centroid HAC. Thus, make use of 3 additive error below.

---

Definition 1 (Dynamic Approximate Nearest-Neighhs Search (ANNS)). An (a, 3) approximaae
dynamic nearest-neighbor search data structure N maintains a dynamically updated set S C TR. (initially S 0) and supports the following operations.
1. Insert, N NNNSERT(u)). given u & update S +- S {u}.
2. Delete, N :DELETE(UU): given u E S update S 4 S \ {u];
3. Query, N .ueEr(u, u): given u, E IRd return E 5 {ύ) s.L.
D(u, a D {u]) + +
If V is a dynamic (a, apppprooiee NNS data structure then we will simply call it a-approximate. For set of points S, we will use the notation NONADAPTIVEANN (5) to denote the result of starting with an empty dynamic ANNS data structure and inserting each point in S (in an arbitrary order).
We say A succeeds for set of points S Ihd and query point if after starting with an empty set and any sequence of insertions and deletions of points in S we have that the query A V.QuERR( ū) correct for any (i.e., the returned point satisfies the stated condition in 3). If the data structure is randomized then we say that it succeeds for adaptive updates if with high probability (over the randomness of the data structure) it succeeds for all possible subsets of points and queries. Queries have true distances at most A if the (true) distance from S to any query is always at most A.
The starting point for our dynamic ANNS data structure is the following data structure requiring non-adaptive updates which alone does not suffice for centroid HAC as earlier described. See Appendix B for a proof.
Theorem 1 (Dynamic ANNS for Oblivious Updates, [3, 19I). Suppose we are given y > 1 and c, B, A and n where log( A/3), x (nly(n) and a dynamically updated set S with at most n. insertions. Then, if all queries have true distance at most A, we can compute randomized (O(c), 8) appproxxietee NNS data structure with update, deletion and query times of n +/(()(((1) .log( / 3) d y, which for fixed set of points and query point succeeds except with probability at most exp( -7))
3 Dynamic ANNS with Adaptive Updates
The main theorem we show in this section is how to construct a dynamic ANNS data structure that succeeds for adaptive updates using one which succeeds for oblivious updates.
Theorem 2 (Reduction of Dynamic ANNS from Oblivious to Adaptive). Suppose are given e, 3, A, n, E Rdd and dynamically updated set c RRd with at most n insertions, such that all inserted points and query points lie in (A) Moreover, assume that can compute dynamic (c, (3 -pprroxiiate NNS data structure with query, deletion and insertion times To. TD and T7 which succeeds for S and a fixed query except with probability at most n O(dVog a log A/8)).
Then, we can compute randomized dynamic (c, -apprriioxee NNS data structure that succeeds for adaptive updates with query, deletion and amortized insertion times Ologn) To, ((TD) and Ollg m) .TI.
We note that our result is slightly stronger than the above: the insertions we make into the oblivious ANNS that we use only occur upon their instantiation, not dynamically.
As a corollary of the above reduction and known constructions for dynamic ANNS that work for oblivious -nantey, Theorem 1 with 7 (d d log( B) log n) and using parameter 3' = BBcc where 3' is the additive distortion parameter for Theorem 1-we obtain the following.
Theorem 3 (Dynamic ANNS for Adaptive Updates). Suppose are given B, A. E Rd where log( A/3), d, S (nly(n) and dynamicully upduted set S C RRd with at most n insertions, such that all inserted and query points lie in (A).
Then, we can compute a randomized dynamic (O(c), ((c)))))approximaat NNS data structure that succeeds for adaptive updates with query, deletion and amortized insertion time n. +o(1))(1) -log( (A/ A/3) d?
previous work [19] also provided algorithms that work against an "adaptive updates" but only a set of adaptive updates made against fixed set of query points. Also, note that if we have lower bound of on the true distance of any query then lowering e by a constant and setting 3 = (6)) for suitably small hidden constant gives an approxxiio NNS with similar guarantees.
5

---

No
Sq
Initial state.
(b) Insert point.
(c) Si < So U
(d) S2 Si S2.
Figure 3: Our merge-and-rede strategy when point (in green) is inserted.
3.1 Algorithm Description
Our algorithm for dynamic ANNS for adaptive updates uses two ingredients. First, we make use of the following "covering nets" to fix our queries to small set against which we can union bound.
Lemma 1. Given 8 E Rd and 3, A > 0, there exists covering net Q C Rd such that
1. Small Size: |Q| S (A/3)0(4logd)
2. Queries: given u E (A), one can compute u' E Q in time ((d) such that D(u, w() S B.
Second, make use of Emerge-and-reduce approach. A similar approach taken by [12] for exact k-nearest-neighhor queries the plane. Namely, for each E [O n)] we maintain set S; of size at most 2' (where all S; partition all inserted points) and dynamic ANNS data structure Nf for Sy which only works for oblivious updates. Other than the size constraint, the partition is arbitrary. Informally, perform deletions, insertions and queries follows.
Deletion: To delete point simply delete it from its corresponding. N₁.
all points from S, S if S, contains more than 2' points; we update N& accordingly each time we move points; namely, we recompute N₁ and N from scratch on S; and S respectively. See Figure 3.
Insertion: To insert a point, insert it into So and for each
Query: Lastly, to query point u we first map this point point in our covering net u' (as specified by Lemma 1), query t' in each of our Nr and then return the best output (i.e.. the point output by an NG that closest u').
Our algorithm is more formally described in code Algorithm 1.
Algorithm Dynamic ANNS for Adaptive Updates
Input: 3, A, n, s E Rd Q +- COVERINGNEr(s, A, .)) (computed using Lemma 1)
Maintains: Sn, S1,-... -....- partition of the inserted points, s.t. |S|] < 2
Maintains: No,
a non-adaptive ANNS for each S;
function INSERT(U)
So + So U {u}
while Di such that |S| 2 do
S + S.+ U S: and S; +
Ni+1 NONADAPTIVAANN(SH))) and Mr NONADAPTIVEANN(!)
function DELETE(U)
Let i be such that S;
N(.DELETE(W) and remove u from S;
function QUERY(U, ū)
Let u' Q be such that D(u, u') = O
computed using Lemma
Let v, N..QUERY(u'' ②) return e = arg min, D(u, d U:)

---

4 Centroid-Linkage HAC Algorithm
In this section, we give our algorithm for Centroi-LLinkage HAC. Specifically, we show how to (with Algorithm 3) reduce approximate Centroid-Linkage HAC to roughly linearly-mnny dynamic ANNS function calls, provided the ANNS works for adaptive updates.
Theorem 4 (Reduction of Centroid HAC to Dynamic ANN for Adaptive Updates). Suppose we are given a set of n. points P C R2, C > 1, >> O, and lower and upper bounds on the minimum and maximum pairwise distance in P of 8 and A respectively. Suppose we are also given a data structure that is a dynamic c-approximate NNS data structure for all queries in Algorithmm 3 that works for adaptive updates with insertion, deletion and query times T', TD, and TQ-
Then there exists an algorithm for c(1 + -)approxiiaate Centroid-Linkage HAC on n. points that runs in time (n (Tr + Tn + TQ)) assuming 2/2 S <poly(n) and _ S polylog(n)).
Our final algorithm for centroid HAC is not quite immediate from the above reduction and our dynamic ANNS algorithm for adaptive updates. Specifically, the above reduction requires a c-approximate NNS data structure but in the preceding section we have only provided (c. 3)-approximate NNS data structure for 3 > O. However, by leveraging the structure of centroid HAC-in particular, the fact that there is only ever at most one "very close" pair-we are able to show that this suffices. In particular, for given there exists Co and 6o such that (Co. S6) -apaaroxxeee NNS data structure functions as a c-approximate NNS data structure for all queries in Algorithm 3. This is formalized by Lemma 6. Combining Lemma 6, Theorem 4 and Theorem 3, we get the following.
Theorem 5 (Centroid HAC Algorithm). For n points in Rd, there exists a randomized algorithm that given any > 1.01 and lower and upper bounds the minimum and maximum pairwise distance in P of 8 and respectively, computes a c-approximate Centroid- Centroid-Linkage HAC with high probability. It has runtime O (00//)) d assuming c, d, o S poly(n).
4.1 Algorithm Description
In what remains of this section, we describe the algorithm for Theorem 4. Consider a of points P E Rd. Suppose we have a dynamic c-approximate NNS data structure N' that works with adaptive updates with query time To. insertion time Tr, and deletion time Tn. Let Q be a priority queue storing elements of the form (1, xr y) where x and are "nearby" centroids and | = D(2; y). The priority queue supports queuing elements and dequeueing the element with shortest distance, L. At any given time while running the algorithm, say a centroid æ is queued if there is an element of the form (1, x, y) in Q. We will maintain a set, C. of active centroids allowing us to check if centroid is active in constant time. For each active centroid, C' will also store the weight of the centroid so we can preform merges and an identifier to distinguish between distinct clusters with the same centroid. Note that any time we store a centroid, including in Q, we will implicitly store this identifier.
First, describe how the algorithm handles merges. To merge two active centroids, ær and y. we remove them from C' and delete them in N. Let = = wyx + wyy be the centroid formed by merging x and y- We use N to find an approximate nearest neighbor, y", of = and add Q the tuple (D(z, y²) y²). Lastly, we add z to N and C. Pseudo-code for this algorithm is given by Algorithm 2. Crucially, we do not try update any nearest neighbors of any other centroid at this stage. We will do this work later and only if necessary. Since we are using an approximate NNS, it is possible that the centroid 2 will be the same point in I2 as the centroid of another cluster. We can detect this in constant time using C' and we will immediately merge the identical centroids.
We now describe the full algorithm using the above merge algorithm; also give pseudo-code in Algorithm 3. Let e >> 0 be a parameter that tells the algorithm how aggressively to merge centroids. To begin, we construct / by inserting all points of P in any order. Then for each p E P. use N to find an approximate nearest neighhor E P {p} and queue (D(p, y), y),P.1 y) to Q. We also initialize C = {p: : p E P). The rest of the algorithm is a while loop that runs until Q is empty. Each iteration of the while loop begins by dequeuing from Q the tuple (I, x, y) with minimum l.
(1) If r and y are both active centroids then we merge them.
(2) Else if is not active then we do nothing and move on to the next iteration of the while loop.
(3) Else if x is active but is not, we use A to compute a new approximate nearest neighbor, v" of x.
Let = D(x, v²) If & (1 + e),, then we merge r and y" Otherwise we add (I*, x, y to Q
7

---

Algorithm 2 Handle-Merge
1: Input: set of active centroids C, ANNS data structure N, priority queue Q, centroids æ and y
2: <- Wy. Wyy/
Merge and
3: Remove z and y from C' and W
4: if there is a centroid x that is the same is in C' then
5: 4 2 + w2"2"
Merge a and x*
6: Remove from C and add
7: else
8:
Add = to / and
9: y" +- An approximate nearest neighbor of = returned by N (ZQ
10: Queue (D(2,y"), 2,,"" Q
Algorithm Approximate-HAC
Input: set of points P, metric D, fully dynamic ANNS N data structure,
2: Output: (1 + =)c-approximate centroid HAC
3: Initialize Q and C' {(p} E P} and insert all points of P into N
4: for do
5: 4- approximate nearest neighbor of returned by W N.QUERY(p.7
6: Queue (D(p. p, p,y) to Q
7:
while Q not empty do
8: (1, v) +- dequeue shortest distance from Q
9: if xr y E C then
10:
else Handle-Merge(C..N, Q, then
11:
12:
V" <- An approximate nearest neighbor of returned by N.UUURY
13:
[ - D(z,
14:
if 1" < (1 + e)l then
15:
Handle Manule--MrgoC..NN, Q.x.y")
16:
else
17:
Queue (I",,,y)) Q
Empirical Evaluation
We empirically evaluate the performance and effectiveness of our approximate Centroid HAC algorithm through comprehensive set of experiments. Our analysis on various publicly-avillable benchmark clustering datasets demonstrates that our approximate Centroid HAC algorithm:
(1) Consistently produces clusters with quality comparable that of exact Centroid HAC,
(2) Achieves an average speed-up 22 x with a max speed-up of 175x x compared to exact Centroid HAC when using 96 cores in our scaling study. On single of 5x with a max speed-up 36x.
achieves average speed-up
Dynamic ANNS Implementation using DisKANN As demonstrated previous works, although LSH-based algorithms have strong theoretical guarantees, they tend to perform poorly in practice when compared to graph-based ANNS data structures [18]. For instance, in ParlayANN [18], the authors find that the recall achievable LSH-based methods standard ANNS benchmark dataset are strictly dominated by state-of-the-art graph-based ANNS data structures.
Therefore, for our experiments, data structure [38]. In particular, we consider the in-memory version of this algorithm from ParlayANN, called Vamana. In nutshell, the algorithm builds bounded degree routing graph that can be searched using beam search. Note that this graph is not the k-NN graph of the pointset. The graph is constructed using incremental construction that adds bidirectional edges between newly inserted point, and points traversed during a beam search for this point; a point's degree exceeds the degree bound, the point is pruned ensure diverse set of neighbors. See [38] for details.
DiskANN, widely-used state-of-the-an art graph-based ANNS
For Centroid HAC, we require the ANNS implementation to support dynamic updates. The implementation provided by ParlayANN currently only supports fast static index building and queries. Recently, FrssNDiskANN [37] described a way to handle insertions and deletions via a lazy update

---

Table 1: The ARI and NMI scores of our approximate Centroid HAC implementations for e = 0.1, 0.2, 0.4,
and 0.8, versus Exact Centroid HAC. The best quality score for each dataset is in bold and underlined.
Dataset
Centroida
Centroida
Centroida
Centroidos
Exact Centroid
iris
0.759
0.746
0.638
0.594
0.759
wine
0,352
0.352
0.402
0.366
0,352
0,509
0.526
0,490
0.641
0.509
ARI
digits
0.589
0.571
0.576
0.627
0.559
faces
0,370
0,388
0.395
0,392
0,359
mnist
0.270
0.222
0.218
0.191
0.192
birds
0.449
0.449
0.442
0.456
0,441
Avg
0.471
0.465
0.452
0.467
0.453
iris
0.803
0.795
0.732
0.732
0.803
wine
0,424
0,424
0,413
0.389
0,424
cancer
0.425
0.471
0.459
0.528
0.425
digits
0.718
0.726
0.707
0.754
0.727
faces
0.539
0.534
0.549
0.549
0.556
mmist
0,291
0,282
0,306
0.307
0,250
birds
0.748
0.747
0.756
0.764
0.743
Avg
0.564
0.569
0.560
0.575
0.561
approach. However, their approach requires a periodic consolidation step that seans through the graph and deletes inactive nodes and rebuilds the neighborhood of affected nodes, which is expensive.
Instead, in our implementation of Centroid HAC, we adopt the following new approach that is simple and practical, and adheres to the updates required by our theoretical algorithm: when clusters u and v merge, choose one of them to represent the centroid, and update its neighborhood N (u) (without loss of generality) to the set obtained by pruning the set [u) U N()). The intuition here is that (2) U (v) is a good representative for the neighborhood routing graph. Further, during search, points will redirect to their current representative centroid (via union-fine [14]), thus allowing us to avoid updating the in-neighbors of a point in the index. We believe application-driven update algorithms, such the described here, can help speed-up algorithms that uses dynamic ANNS as a subroutine.
the centroid of u and v in the
5.1 Quality Evaluation
We evaluate the clustering quality of our approximate centroid HAC algorithm against ground truth clusterings using standard metrics such as the Adjusted Rand Index (ARI), Normalized Mutual Information (NMI), Dendrogram Purity, and the unsupervised Dasgupta cost [11]. Our primary objective is to assess the performance of our algorithm across various values of benchmarks. We primarily compare our results with those obtained using exact Centroid HAC.
diverse set of
For these experiments, we consider the standard benchmark clustering datasets iris, digits, cancer, wine, and faces from the UCI repository (obtained from the sklearn. datasets package). We also consider the MNIST dataset which contains images of grayscale digits between 0 and 9, and birds, a dataset containing images of 525 species of birds; see Appendix E for more details.
Results. The experimental results are presented in Table 1, with a more detailed quality evaluation in Appendix 1. We summarize results here.
We observe that the quality of the clustering produced by approximate Centroid HAC is generally comparable that of the exact Centroid HAC algorithm. On average, the quality is slightly better in some cases, but we attribute this to noise. In particular, we observe that for the value of e = 0.1, we consistently get comparable quality to that of exact centroid: the ARI and NMI scores within a factor of 7% and 2% to that of exact Centroid HAC, respectively. We also obtained good dendrogram purity score and Dasgupta cost well, with values within 0.3% and 0.03%, respectively.
average
5.2 Running Time Evaluation
Next, evaluate the scalability of approximate Centroid HAC against exact Centroid HAC on large real-world pointsets. We consider the optimized exact Centroid HAC implementation from the fastcluster package [29]. We also implement efficient version of exact Centroid HAC based on our framework (i.e. setting = 0 and using exact NNS queries) which has the benefit of using only linear space and supports parallelism in NNS queries. We also implement bucket-based version of approximate Centroid HAC as a baseline, based on the approach of [1] along with an observation to handle the non- con-monotonicity of Centroid HAC; details in Appendix E.

---

Detirdds Freept Oacket Ca Frrifeaat Faltcusted)
Crree Pacot)
364
1p-1
300
105
321
(a)
(b)
(c)
Figure 4: Running times of fastcluster's centroid HAC, our implementation of exact centroid HAC, and the heap-hasee heap-hased and bucket-based approximate centroid HAC with 0.1. In Figure 4a, our approximate and exact implementations are run core, whereas Figure 4b they have access to 192 cores. Figure 4c compares the running times heap and bucket based algorithms as a function of
Results. We now summarize the results of our scalability study; see Appendix E.2 for more details and plots. Figures 4a and 4b shows the running times on varying slices of the SIFT- dataset using one thread and 192 parallel threads, respectively. For the approximate methods, we considered c= 0.1. Figure 4c further compares the heap and bucket based approaches as a function of
We observe that the bucket based approach is very slow for small values of e due to many redundant nearest-neighhor computations. Yet, at 0.1, both algorithms, with 192 threads, obtain speed-ups of up to 175x with an average speed-up of 22x compared to the exact counterparts. However, on single thread, the bucket based approach fails scale, while the heap based approach still achieves significant speed-ups of upto 36x with an average speed-up of 5x. Overall, our heap-based approximate Centroid HAC implementation with e 0.1 demonstrates good quality and scalability, making it good choice in practice.
Conclusion
In this work we gave an approximate algorithm for Centroid-Linkage HAC which runs in subquadratic time. Our algorithm is obtained by way of a new ANNS data structure which works correctly under adaptive updates which may be of independent interest. On the empirical side we have demonstrated up to 36x speedup compared to the existing baselines. An interesting open question is whether approximate ceatroid-Linkage HAC admits a theoretically and practically efficient parallel algorithm.
Acknowledgments
This work was supported by NSF grants CNS-2317194 and CCF-2403235. We thank Vincent Cohen-Addad for helpful discussions. We thank the anonymous reviewers for their useful comments.
References
[1] Amir Abboud, Vincent Cohen-Addad, and Hussein Houdrouge. Subquadratic high-dimensional hierarchical clustering. 2019.
[2] Deepak Ajwani, Rob H. Bisseling, Katrin Casel, Umit V. Çatalyürek, Cédric Chevalier, Florian Chudigiewitsch, Marcelo Fonseca Faraj, Michael Fellows, Lars Gottesbüren, Tobias Heuer, George Karypis, Kamer Kaya, Jakub Lacki, Johannes Langguth, Xiaoye Sherry Li, Ruben Mayer, Johannes Meintrup, Yosuke Mizutani, François Pellegrini, Fabrizio Petrini, Frances Rosamond, Ilya Safro, Sebastian Schlag, Christian Schulz, Roohani Sharma, Darren Strash, Blair D. Sullivan, Bora Uçar, and Albert-Jan Yzelman. Open Problems in (Hyper)Graph Decomposition. working paper or preprint, December 2023. URL https: sci ence 04251953.
[3] Alexandr Andoni. Nearest neighbor search: the old, the new, and the impossible. PhD thesis. Massachusetts Institute of Technology, 2009.
[4] Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Communications of the ACM, 51(1):117-122, 2008.
[5] MosemmadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger, Monika Henzinger, Rajesh Jayaram, Vahab Mirrokni, and Andreas Wiese. Optimal fully dynamic k-center clustering
10

---

for adaptive and oblivious adversaries. In Proceedings the 2023 on Discrete Algorithms (SODA), pages 2677-2727. SIAM, 2023.
Symposium
[6] MossmmadHosseii Bateni, Laxman Dhulipala, Kishen N Gowda, D Ellis Hershkowitz, Rajesh Jayaram, and Jakub Lqcki. It's hard hac with average linkage! In International Colloquium on Automata, Languages and Programming (ICALP), 2024.
[7] Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. pages 1671-1684, 2022.
[8] J-P Benzécri. Construction d'une classification ascendante hiérarchique par la recherche chaîne des voisins réciproques. Cahiers de I' l'analyse des donmées, 7(2):209-218, 1982.
[9] Nairen Cao. Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, and Lukas Vogl. Understanding the cluster linear program for correlation clustering. In Proceedings of the 56th Anmual ACM Symposium on Theory of Computing. STOC 2024, page 1605-1616, New York, NY, USA, 2024. Association for Computing Machinery, ISBN 9798400703836. doi: 10.1145/361 017.366622266644447 URL https: http://oooioooooo org/10../100. 1145/ /144/31112222 3618260..... 3649749.
[10] Vincent Cohen-Addad, Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan, Improved approximations for euclidean k-means and k-median, via nested quasi-independent sets. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, page 1621-1628, New York, NY. USA, 2022. Association for Computing Machinery. ISBN 978 1403396444 doi: 10. 10.1145/3519935.3555 3522001 1. URL https:://dot org/10 1145/ 3519935. 3520011.
[11] Sanjoy Dasgupta. A cost function for similarity-based hierarchical clustering. In Annual ACM Symposium on Theory of Computing (STOC), page 118-127, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450341325. doi: 10. 10.1145/2895518.889977
[12] Sarita de Berg and Frank Staals. Dynamic data structures for k-nearest neighbor queries. Computational Geometry, 111:101976, 2023.
[13] Li Deng. The mnist database of handwritten digit images for machine learning research [best of the web). IEEE Signal Processing Magazine, 29(6):1411))) 2012. doi: 10.1 109/MS222222. 221 1477.
[14] Laxman Dhulipala, Changwan Hong, and Julian Shun. Connectit: a framework for static and incremental parallel graph connectivity algorithms. Proceedings of the VLDB Endowment, 14 (4):653-667, 2020.
[15] Laxman Dhulipala, David Eisenstat, Jakub Lącki, Vahab Mirrokni, and Jessica Shi. Hierarchical agglomerative graph clustering in nearly-lineat time. In International Conference on Machine Learning (ICML), pages
2021.
[16] Laxman Dhulipala, David Eisenstat, Jakub Lącki, Vahab Mirrokni, and Jessica Shi. Hierarchical agglomerative graph clustering in logaritiai depth. Annual Conference Neural Information Processing Systems (NeurIPS), 35:22925-222 229920 2022.
[17] Laxman Dhulipala, Jakub Lącki, Jason Lee, and Vahab Mirrokni. Terahac: Hierarchical agglomerative clustering of trillion-edge graphs. Proceedings of the ACM on Management of Data, 1(3):1-27, 2023.
[18) Magdalen Dobson, Zheqi Shen, Guy Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun. Scaling graph- ANNS algorithms to billion--ize datasets: A comparative analysis. CoRR, abs/2305.04355 04359, 2023. doi: 10.48550//xXiv2235..033 URL
https://doi. org/10. 48550/ /atp/viiivv//.v arXiv.2305........... 04359.
[19] Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani. Approximate nearest neighbor: Towards removing the curse of dimensionality. 2012.

---

[20] JuliaStats. Clustering.jl. helust.hts html.
URL
[21] Bruce M Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polyloga- rithmic worst case time. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 1131-1142. SIAM, 2013.
[22] Adam Karezmarz and Jakub Lącki. Reliable hubs for partially-dynamic all all-pairs shortest paths in directed graphs. arXiv preprint arXiv:1907.02266, 2019.
[23] CS Karthik and Pasin Manurangsi. On closest pair in euclidean metric: Monochromatic is as hard as bichromatic. Combinatorica, 40(4):539-573, 2020.
[24] Yasushi Kawase, Tomomi Matsui, and Atsushi Miyauchi. Additive approximation algorithms for modularity maximization. Journal of Computer and System Sciences, 117:182-201, 2021. ISSN 0022-0000. doi: https://oi.org// http//0..111/..... jos6//...ss.2020...
[25] Wolfram: Computation Meets Knowledge.
Hierarchical clustering. URL
https://reference. wow.wao com/
HterarchicallCustering
[26] Silvio Lattanzi, Thomas Lavastida, Kefu Lu, and Benjamin Moseley. A framework for parallelizing hierarchical clustering methods. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2019. Würzburg, Germany, September 16-20. 2019, Proceedings, Part I, pages 73- 19- Springer, 2020.
[27] Zhuang Liu, Hanzi Mao, Chao-Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie. A convnet for the 2020s. In Proceedings of the IEEE/CVF Conference Computer Vision and Puttern Recognition (CVPR), pages 11976-1 1986, June 2022.
[28] Math Works.
Agglomerative hierarchical cluster tree matlab linkage. https://www mathworks httptksss.coooee///eeeeeee heeelp//stats/iinkaae html, 2024.
[29] Daniel Müllner. fastcluster: Fast hierarchical, agglomerative clustering routines for r and python. Journal of Statistical Software, 53:1-18, 2013.
[30] Fionn Murtagh. A survey recent advances in hierarchical clustering algorithms. The computer journal, 26(4):354-35,, 1983.
[31] Fionn Murtagh and Pedro Contreras. Algorithms for hierarchical clustering: an overview. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2(1):86-97, 2012.
[32] Fionn Murtagh and Pedro Contreras. Algorithms for hierarchical clustering: overview, ii Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 7(6)e 2017.
[33] Danupon Nanongkai and Thatchaphol Saranurak. Dynamic spanning forest with worst-case update time: adaptive, las vegas, and o (nl/2-e)-time. In Proceedings of the 49th Anmual ACM SIGACT Symposium on Theory of Computing, pages 1122-1129, 2017.
[34] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit- learn: Machine learning python. the Journal of machine Learning research, 12:2825-2830, 2011.
[35] RDocumentation. helust function rdocumentation. URL URRLLhttss//ww..rooumntttttat wttp://ereeeeeeeeeeeeeeeeeeee/// 2tttp//ccccccsssstt.tessssssssst
org arg/packes
[36] JM Shearer and Michael A Wolfe. Alglib, simple symbol-mamipulation package. Communica- tions of the ACM, 2888):800-825, 1985.
[37] Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. Freshdiskann: fast and accurate graph- ann index for streaming similarity search, 2021.
12

---

[38] Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Krishnaswamy, and Harsha Simhadri. Diskann: Fast accurate billion point nearest neighbor search on single node. In NeurlPS 2019, November 2019.
[39] Pauli Virtanen, Ralf Gommers, Travis E Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright. et al. Scipy 1.0: fundamental algorithms for scientific computing in python. Nature methods, 17(3):261-272,
2020.
[40] David Waje. Rounding dynamic matchings against an adaptive adversary. In Proceedings of the 52nd Annual ACM SIGACT Symposium Theory Computing, pages 194-207, 2020.
[41] Shangdi Yu, Yiqiu Wang, Yan Gu, Laxman Dhulipala, and Julian Shun. Parchain: A framework for parallel hierarchical agglomerative clustering using nearest- neighbr chain. arXiv preprint arXiv:2106.0473 047277, 2021.
[42] Shangdi Yu, Joshua Engels, Yihao Huang, and Julian Shun. Pecann: Parallel efficient clustering with graph-based approximate nearest neighbor search, 2023.
13

---

A Cluster-Centric Definition of Centroid-Linkage HAC
We formally define Centroid-Linkage HAC in cluster-centric way. For a set of points X C RR we define cent(X) to the centroid of X as below.
Definition (Centroid), Given a set of points X C R", the centroid of X is the point x E R whose ith coordinate is
vld
[
DEX X
Centroid HAC uses distance between centroids as linkage function. That is, for clusters X and Y, (X,, Y) - D(cen(()),
c-approximate Centroid-Linkage HAC is defined as follows. We are given input points C IR First, initialize of active clusters C = {(p) Then, until |C] we do the following: let X, y C pair of active clusters satisfying
C(X Se min C(X,Y) X,YEC
where the min taken over distinct pairs; merge X and Ý by removing them from C and adding X U y to C. (Non-approximate) Centroid-Linkage HAC is just the above with e e= 1.
B Proof of Theorem 1
In the interest of completion, give proof of Theorem 1 (dynamic ANNS for oblivious updates).
B.1 Locality Sensitive Hashing
We will make use of the well-known algorithmic primitive of locality sensitive hashing.
Definition 3 (Locality Sensitive Hashing). A family of hash functions H. is called (r, Pr.)
sensitive if for any p. E IRd we have
1. Close Points Probably Collide: If D(u, v) S then Pr (h(u) h(v)) 2 P1.
2. Far Points Probably Don't Collide: If D(u, v) cr then Priea(((u)) h(w)) S p2-
We will make use of known locality sensitive hashing schemes for Euclidean distance in Rd For this result, see also [4]. Theorem (Lemma 3.2.3 of [3]). Given r and c, there a (r, cr, (r,cr,,1.1) P2) P.....attssssiiiie -sensitive LSH family with
log(1/p2) < o(logn). n). log(1 (1/1)) 1/6² o(1) and
1og(1/P2)
Furthermore, one can sample h and given u E Fdd compute h(u) time o().
Theorem 1 (Dynamic ANNS for Oblivious Updates. [3, 19]). Suppose are given ry >> 1 and c, B, A and n where log( / B), I (nly(n) and a dynamically updated set with at most n insertions. Then, if all queries have true distance at most A,
compute randomized (O(c), () appproxiittee NNS data structure with update, deletion and query times of n +o()))(() llo A (3) d Y, which for fixed set of points and query point succeeds except with probability at most
Proof. We first construct a data structure which succeeds with constant probability a given query. To do so we begin by turning our LSH hashes from Theorem 6 into hash function which is an "L ors K ands". In particular, we let
L: n +o(1) O(logn).
and let
K = log(1/p2)
(O n) + log L + log log( (A/)).
14

---

Notice that by Theorem 6 we have that log(1/p2) I o(logn) n) and by assumption we have log( (/(4))) Y S poly(n) and so we have
K I. a 1/22
(I)
For each i such that 3 2 < A, define T--many new hash functions, each of which consists of K-many h from Theorem 6. In particular, for i E [log( ( [3)]. (B(()) E [r]] and E [K], we let haa be uniformly random h sampled according to Theorem 6 using radius we let 9u Rd -> IR* be a new hash function defined on u E R as
2 and our input c. Likewise,
gu (u) = (hai (u), (ua),..,,,,.(()
We let G. {Ma S. L} be all such hash functions for and let g = U: G3 be all such hash functions across scales.
By Theorem 6, sampling each constituent hash functions for each 9 can be done in time dn and so by this and Equation (1) initializing all hash functions in 9 takes time
d(1 L-K I..Klog(//)) n21e"++(()) log(A/3)
This initialization time will be dominated by the time it takes to insert a single point. For each such hash function we will maintain a collection of buckets which partitions points in S.
To insert a point into S, we simply compute its hash for each g G and store this hash in each corresponding bucket. To delete a point from S we simply delete it from all buckets to which it hashes. Lastly, to answer query on (u, u), hash u according each g E G and then return the S ū such that for minimum we have a g G, such that g(u) = g(u). Since by Theorem 6 evaluating each hash function takes time d1), we get that all of these operations also take time at most that given by Equation (2).
Lastly, we argue the (constant probability) correctness of a query for a fixed set of points. Fix query points (u, ū) and set of points S. Let S / {u} be fixed point of S {u] where we let tw be Say that w succeeds if
such that 2d & D (u, w) < 2'
1. One Correct Collision: there is g Gi,, such that g(w) g(u) and
2. No Incorrect Collisions: for all i < w and g E G, we have that g(u) A g(w).
Observe that if both of the cases happen for every w E S {u} then we have that our query is correct. The only non-trivial part of this observation is the fact that if is within distance 33 of S \ {ū} then f. = and the returned point is within an additive of u so long as one correct collision holds.
Continuing, we next lower bound the probability of one correct collision. For a fixed Jig! Gi.. we have that g(w) g(u) iff (1
hi,,'k (u) for all h: S K. The probability of this for one k < K is, by definition, P1. By Theorem 6 we know that log(1/p1) = 1/c² + o(1) and so for fixed 1, log(1/pa)
we have that this occurs with probability at least
k = exp( - K log (1/p1))
log(1/p))
= exp
(O(log n) + log L + log log (A/3))
log(1/p2)
= exp(-(1/c² + +()) (Ollogn) + log L + log log A/)))
> exp (-(1/2+
+0/c2+((1))) o(1) 0l)g
It follows that the probability that this does not hold for some is at most
(1 (1-pfe 11=p))² - exp(-L
S exp (-L- ( Ologg)))
+ o(1) = exp (x((logn)-xx(((((() o(1) 2(logn)] exp [-(1/e + +o(1)) O(logn))
n -01),
15

---

Next, we lower bound the probability of no incorrect collisions. Fix an i < iw- Observe that for given hark we have, by definition, that hark (u) hav with probability at most p2. Thus, we have ga Ba(u) ga(w) with probability at most
P2 cxp( log (Pg((12))))
exp(-9((og n) - log L - log (og((/))))))))))
Union bounding over our at most log( / () -any such and L-mmnyy such we get that that we have no incorrect collisions except with probability at most
p log( (/3) L exp(- = n-(())
Finally, union bounding over our n-many possible points in and using the fact that y 2 we have that succeed except with probability at least fixed constant bounded away from 0 for S and this query. Furthermore, by taking 7-many independent repetitions of this data structure and taking the returned point closest to query, increase our runtime by multiplicative y and reduce failure probability to exp(-r).
C Proofs from Section 3
Lemma 1. Given s Fdd and B, A > there exists covering net Q Fd such that
1. Small Size: |Q| S (A/5)0(dlog
2. Queries: given u E (A),, one can compute u' E EQ in time ((d) such that Duu, ut) S B.
Proof. The basic idea is simply to take an evenly spaced hypergrid centered of radius A. More formally, we let
3 Zd
(1-
Vd
d 8
Vd
D:
where above ([-
is the d-way Cartesian product. That is, y is d-dimensional vector Thus, Q consists of all points which offset whose coordinates are integers between - vd and A Vd 3.
E A v
each coordinate of s by a multiple of va up to total offset distance A in each coordinate.
The number of points in Q is trivially the number of offsets which is, in turn,
d
A
O(d d)
2
3
as desired.
Next we analyze how to query. Given point we let
8 Vd
Vd
ul == s,
(u, si)
3
be rounded down to the nearest multiple of 3 (u/, ug.... u'd) E Q by our assumption that (A) and that, furthermore, w' can be computed from in time (dd) Lastly, observe that
after offsetting by Observe that u'
va
|/4 - w/1 Vd
and have that the distance between and w' is
3 2 Vdl
D(u, u()
ut)2 S
Σ
3.
16

---

Lemma 2. Algorithm I is a (c, apprrxxixie nearest-neighbor search data structure with high probability for adaptive updates.
Proof. Consider a query on (u, ū)) with corresponding w' E Q in our covering net (i.e., the u' returned by Lemma when input u). We refer to the state of our data structure at the beginning its for loop (i.e., upon receiving new update or query) as at the beginning of an iteration.
First, observe that simple argument by induction point set for which VV is a data structure at the beginning of an iteration S and that, furthermore, the of points which have been inserted but not deleted a given point time then { partitions S. Thus, we have
insertions and deletions shows that the
min St a) D(u',S, ū).
Furthermore, by the guarantees of Lemma and the fact that all points of and all query points are always contained in B, (A), we know that
=0(3).
(3)
It follows that
D D(u, (2)) 0(8)
and so
min D(,, ū) S D(u, S ú) + 0(B).
(4)
Furthermore, notice that since the randomness of N,, chosen after we fix St, we have by assumption that for fixed u' Q that succeeds for query (u', ū) with points S; except with probability at most
n S2d( de (og(A/m))
On the other hand, by Lemma 1 we know that Q < ( Old
so taking a union bound over all points in have that with high probability N₁ succeeds for S, and every query point in Q except with probability at most 1/poly(n). Union bounding over our O(n)-man N2 that we ever instantiate, we get that every Nr succeeds for its corresponding S; and every query point of Q except with probability at most 1/ I/poly(n). In other words, with high probability we always have
D(u', vy) S D(', S, ū) + O(3).
(5)
Thus, combining the triangle inequality, Equations 4 and 5, we have that with high probability whenever we query point u, the returned point satisfies
D(u, v) min D(u, vz)
< D(u, u') min D(u', vi)
50( + min D(u', v;)
s 0(3) + min D(u', ( S, ū))
Sc- D(u, S a) Occ- B)
Choosing our hidden constant appropriately, we get that with high probability data structure is indeed (c,c -pp-roopx..
Lemma 3. Algorithm I has amortized insertion time Ollogn) Tr where Tí is the insertion time of the input oblivious dynamic ANNS data structure.
Proof. Let TISSERT I n be the total number of insertions up to some point in time. Each time we instantiate an N411 on an S.11. it consists of at most 2 --a-y points and by assumption takes us time
T, 2(+2)
17

---

time to instantiate. On the other hand, the total number of times we can instantiate N is at most N /2' (since each time we instantiate it we add a new set of at least 2' points to S,41 and points only move from Sjs to Sj+18). It follows that the total time to instantiate Ni+1 is at most
T 2
PINSERT
2 = O RINSERT)
Applying, the fact that S log n, we get that the total time for all insertions is
Ollog) n)) Ty D
Dividing by our many insertions, we get an amortized insertion time of O(log n) Tr, as desired.
Theorem 2 (Reduction of Dynamic ANNS from Oblivious to Adaptive). Suppose are given e, 3, A, n, Rd and dynamically updated set C Id with at most n insertions, such that all inserted points and query points lie in (2( Moreover, assume that (c, B) apppproxxeee NNS data structure with query, deletion and insertion times To. TD and Tj which succeeds for S and fixed query except with probability at most n. odo(go gg d log (og()/8)).
compute dynamic
Then, we can compute randomized dynamic (c, appproximae NNS data structure that succeeds for adaptive updates with query, deletion and amortized insertion times (logn) .Tq ((TD) and Ollog n. TT.
Proof. We use Algorithm 1. Correctness follows from Lemma 2 and the amortized insertion time follows from Lemma 3. The deletion time is immediate from the fact that can compute the i such that u E S; in constant time. Lastly, we analyze our query time. By Lemma 1, computing each w' takes time (dd) TQ (since reading the query takes time (2d)). Likewise, by assumption, computing NQUERR (u', ù) takes time To for each i, giving our desired bounds.
D Proofs from Section 4
We now prove that Algorithm gives (c(1 E)) >approximaae HAC where is the approximation value inherited from the approximate nearest neighbor data structure. Note that a smaller e will give a more accurate HAC but will increase the runtime of the algorithm.
Lemma 4. Algorithm gives a c(1 + -apprxxiie Centroid- Linniid HAC.
Proof. The idea of the proof observe that one of the two endpoints of the closest pair will always store an approximate of the minimum distance in Q. In that spirit, suppose that right before centroid dequeued, the shortest distance between active centroids /OPT- Then there must exist active centroids 2ι and 22 such that D(1), .22) = 1OPT. Assume without loss of generality that was queued before 22 and 22 was queued with distance 22. Then, when T2 was queued, 21 was active so l2 I c TOPT-
Thus, when a centroid, x, is dequeued, its distance lg obeys the inequality
L < la S c TOPT.
Then, if is merged during the while loop, merged with a centroid of distance most
(1 e) I c(1 e)PTPT
as desired. If a centriod gets merged without being dequeued, that means it merged with another identical centroid which is consistent with 1-approximate HAC.
We now prove the runtime of the algorithm. Say that the maximum pairwise distance between points in P is A and the minimum is 8. We make the following observations about the geometry of the centriods throughout the runtime of Algorithm 3.
Observation 1. Consider any point p E P. Throughout the runtime of Algorithm 3, the distance from any centroid to is at most A.
Proof. Consider a cluster Q C P. Since for each g Q we have D(p.g) S A, it follows that D(p, cent())) < A.
D
18

---

When running Algorithm 3, at any point in time there can only ever be a single centroid queued with distance less than 8.
Observation 2.
Initially, every centroid is queued with distance at least 6. Thus, if a centroid is ever queued with a smaller distance it will immediately be dequeued and merged.
Proof.
Lemma 5. Algorithm runs time O(n T7 + n TDD + T. log1-c log(n) logite (2
Proof. The idea of the proof is that each time we dequeue centroid we either merge it or we increase the distance associated with it by a multiplicative factor of + which can only happen ( times for each of our O(n)-
centroids.
Each centroid inserted into N at most once, either during the initial construction or in Algorithm and deleted at most once. Since there are 2n 1 centroids throughout the runtime, the total time spent on updates to N is O(n T7 n TD).
At any given point during the algorithm, a centroid can be in Q at most once. Since only 2n 1 centroids are created, there are at most 2n 1 elements in Q at any time. Thus, single queue or dequeue operation takes (n)) time. In the initial for loop we queue n elements to Q and make n queries to A taking time On log(n) + n Tq). Each time algorithm 2 gets called it queues one element to Q and makes up to 4 updates to C. Since Algorithm is called at most n - 1 times, the total time spent on merges, not including updates N, is On To + n log(n)).
Lastly, we consider how many times a centroid x can be dequeued on Line 8. Suppose x is queued
with distance 4, the ith time it is queued. If 4 < 5 then by Observation 2, will be immediately dequeued and merged so æ is only queued once. Thus, we assume 4 2 8. If x is dequeued with distance 4 then either x: is merged and will not be queued again or it is queued again with distance
4+1 (1 e)44 >> (1 +e)--
Since 1 2 5 by assumption and 1, < 2A for all 2 1 by Observation 1, it follows that æ can only be queued, and therefore dequeued, log +r( (²2²) times. Each time, not including merges, there can be one dequeue from Q, one queue Q, and one query to A. Since there are 2n 1 centroids created by the algorithm, the while loop (not including merges) runs in time On log(n) (2(2g) +n- To logi+e( (2A) ))-
Combining the previous two lemmas together we get the following.
Theorem 4 (Reduction of Centroid HAC to Dynamic ANN for Adaptive Updates). Suppose we are given a set of a points P Rdd >> 1, O, and lower and upper bounds on the minimum and maximum pairwise distance in P of and respectively. Suppose we are also given a data structure that dynamic c-approximate NNS data structure for all queries in Algorithmm 3 that works for adaptive updates with insertion, deletion and query times of T1, TD, and TQ.
Then there exists algorithm for c(1 + -)-pprooximate Centroid- Linkage HAC n points that runs in time Ön (Tr Tp + TQ)) assuming A S poly(n) and 1 < polylog(n).
Proof. By Lemma 4 and Lemma 5 we get that Algorithm 3 gives c(1 + -aapproximate HAC in time (n Tr + n- Tp + + To (2 + n log(n) (e )). It is only left to show that logi+e ( I <polylog(n). Changing the base of the logarithm we get
logi+e (22))
24
log( 24
log(1 + E)
We have that log( 2A) < polylog(n) by the assumption that - - poly(n). By the inequality log(1 + x) 2 Itr for all we get that if S
1te 2 0 2
polylog(n)
log(1 +E)
E
19

---

where the final inequality comes from the assumption that ! S polylog(n). If >> then
S polylog(n).
log(1 + c)
(2)
Combining the above inequalities and the above-stated runtime gives our final runtime.
We Theorem 4 with results from Section 3 to get main result. First prove the following lemma which says that our ANNS that includes an additive term functions as a purely multiplicative ANNS for our algorithm.
Lemma 6. For any À E (1,c), if is (5 81--12
(1+c)x) approximate NNS data structure that works for
adaptive updates then N is a c-approximate NNS data structure for all queries in Algorithm
Proof. Let C' be the set of active centroids at the time any given query takes place. We will say point
x is close to the set C' if (rr, C) < 6. We show that if x not close to C, then N Nquery (x, x))
will give the multiplicatiie result we desire:
D(r,)) - -
1 D(x, C) 8(A 1)
([+c))
c D(e, 0) -
D(x,C) D(z C)(1 -
x D(x, + D(x, C) d(- - 1)
A
se. D(,, o) ( 1111 sc. D(r,C).
(6)
We now prove the lemma by induction. The base case is the set of neighbors calculated for the initial of points P. Each p not close to so by Eq. (6),
(Qp, (p.p) < D D(p.C'pp (\)
as desired. Now for the induction step, consider some query for centroid æ that has just been dequeued. For z, C, say y is c-approximate nearest neighbor of if D(x, y) c D(x, C x). Assume by induction that queries up to this point have returned c-approximate nearest neighbors. We know by Observation 2 and the inductive hypothesis that either no points are close C' is the lone point that is close to C. In the former case, N returns a c-approximate nearest neighbor by Eq. (6). Now consider the latter case. Let y be centroid such that ( will show that Nquerr (I, x) * y..
D(z, C x)) We
Define L = D(x, v) + D(x, C( x). By the triangle inequality and because x is the only point that is close to C, we have I, > é Define Py D(a, v) and ps (ax, C' x)/ / to be the percentage of the distance I. from (x,, y) and Dax, C. x) respectively. is enough for us show that
- (ps L) + 5(A 1)
<p
(1 (1+c)A
for all L 12 8. 2. Since Py ps, have ps I and Py Ife. Plugging in L 3 get
Since this equation is linear in L, if it is true for any such L then is true for L = 6
20

---

(ps 1) + 5(A -1 c
(1 (1+ X 1 6)
5(1 1)
(1+c)A
+ 5(A 1)
(1+ cc}
(1 + c)
8
Py
Py L
as desired.
Theorem 5 (Centroid HAC Algorithm).. For points in RR.. there exists randomized algorithm that given any c > 1.01 and lower and upper bounds on the minimum and maximum pairwise distance in P of 6 and A respectively, computes c-approximate Centroid-Linkan HAC with high probability. has runtime O(n) +0(1)))))) d)) assuming c, d, 3 S poly(n).
Proof. Let 6 = 0.001 and define è == Itc > 1.005. For any X E (1,2), Theorem 3 says we can 5(A-1) (1+6)x approximate nearest neighbor data structure, N,, with query, deletion, and
construct (x:
amortized insertion time 002 log
A(1+8JA d². Note that moved the big O in Theorem 8(A-1)
from the approximation guarantee to the runtime by scaling by some constant. By Lemma 6, By Theorem and
A is é-approximate ANNS data structure for all queries in Algorithm our definition of é, we get c-approximate centroid HAC by running Algorithm 3 with N. The 1.005 and by the assumptions that A S (n), all log terms are dominated by the big O in the exponent and we get the runtime O(n ((1100))))) = O(n (((10)))))))))
runtime is Ö(n! 100(0/00/8 log
[A(++8AA)
5(A-1) d²). Letting
In Algorithm 3, in the practice a centroid may only be queued a small number times. Say a tuple (1. x. y) in our priority queue becomes stale if the centroid y is merged. Let l be the average number of tuples in our priority queue that become stale with each merge. Our experiments summarized in Table 4 suggest that I' is small constant in practice with I' for all experiments. The following lemma shows that this case we lose the logi+e (2 in the runtime.
may have queue centroid logi+e (2A) times. However, in
Lemma 7. If the average number of queued element made stale for each merge in Algorithm 3 is I, then Algorithm runs in time O(n Tı + n TD + n To T+ log(()) r)).
merges during the runtime of Algorithm 3 so the total number of tuples that are made stale is (n - 1)T. There are additional n tuples that get merged. Thus, the total number of tuples that get dequeued throughout the runtime of the algorithm is O(T). The rest of the proof is the same as that of Lemma 5 except we pay the cost of de-queuing on Line 8 O(n r)) times instead
Proof. There are a total of
(2
E Empirical Evaluation
We run our experiments on 96-core Dell PowerEdge R940 (with two-way hyperthreading) machine with 4x2. Intel 24-core 8160 Xeon processors (with 33MB L3 cache) and 1.5TB of main memory. Our programs are implemented in C++ and compiled with the g++ compiler (version 11.4) with -03 flag.
Experimental Setup:
21

---

Dataset
# Clusters
iris
150
4
3
wine
178
3
cancer
569
2
digits
1797
64
10
faces
400
4096
40
mnist
70000
784
10
birds
84635
1024
525
covertype
581012
54
7
sift-1M
1000000
128
Table 2: Datasets
Datasets The details of the various datasets used in experiments stated in Table 2. mnist[1, [13] a standard machine learning dataset that consists of 28 x 28 dimensional grayscale images of digits between and 9. Here, each digit corresponds a cluster. The birds dataset contains 224 224 x dimensional images of 525 species of birds. As done in previous works [42], we pass each image through ConvNet [27] to obtain an embedding. The ground truth clusters correspond to each of the 525 species of birds. The licenses of these datasets are as follows: iris (CC BY 4.0), wine (CC BY 4.0), cancer (CC BY 4.0), digits (CC BY 4.0), faces (CC BY 4.0), Covertype (CC BY 4.0), mnist (CC BY-SA 3.0 DEED), birds (CCO: Public Domain), and sift 1M (CCO: Public Domain).
Algorithms Implemented We implement the approximate Centroid HAC algorithm described in Algorithm 3, using the dynamic ANNS implementation based on DiskANN [38, 18]. We denote this algorithm (1 + e)-Centroid HAC or Centroid,. We emphasize that although we refer to this as (-+ee--edtroid HAC, it is not necessarily a true (1 + --approoxemate algorithm since we are using a heuristic ANNS data structure with no theoretical guarantees on the approximation factor. The use of (1 +)) here captures only the loss from merging a "near-optimal" pair of clusters, as detailed in Algorithm 3.
As our main baseline, we consider the optimized implementation of exact Centroid HAC from the fastcluster package. This implementation requires quadratic space since it maintains the distance matrix, and a completely sequential algorithm. We also implement an efficient version of exact Centroid HAC based on our framework (i.e. setting 0 and using exact NNS queries) which has the benefit of using only linear space and supports parallelism in NNS queries.
We also implement a bucket-based version of approximate Centroid HAC as a baseline, based on the approach of [1]. The algorithm of [1] runs in rounds processing pairs of clusters whose distance is within the threshold defined by that round; the threshold value scales by constant factor, resulting in logarithmic (in aspect ratio) number of rounds. In each round, they consider a pair of clusters that are within the threshold distance away, and merge them. For the linkage criteria considered in [1], the distances between two clusters can only go up as a result of two clusters merging. However, this not true for Centroid HAC, as discussed in Section 1.
Here, we observe that when two clusters merge in round, the only distances affected distances of other clusters to the new merged cluster. Thus, we can repeatedly check if the nearest neighbor of this cluster is still within the threshold and merge with it in that case. Thus, in nutshell, the algorithm filters clusters whose nearest neighbors are within the current threshold in each round and merges clusters by the approach mentioned above. This algorithm requires many redundant NNS queries, as we will see during the experimental evaluation.
E.1 Quality Evaluation
The output of hierarchical clustering algorithm is typically tree of clusters, called a dendrogram, that summarizes all the merges performed by the algorithm. The leaves correspond the points in the dataset, and each internal node represents the cluster formed by taking all the leaves in its subtree. There a cost associated each internal node denoting the cost incurred when merging two clusters to form the cluster associated to that node. Given threshold value, clustering is obtained by cutting the dendrogram at certain internal nodes whose associated cost greater than the threshold.
22

---

Table The ARI, NMI, Dendrogram Purity and Dasgupta Cost of our approximate Centroid HAC implementa- tions for e = 0.1, 0.4, and 0.8, versus Exact Centroid HAC. The best quality score for each dataset is bold and underlined.
Dataset
Centroida
Centroide
Centroida4
Centroides
Exact Centroid
iris
0.759
0.746
0.638
0.594
0.759
wine
0.352
0.352
0,402
0.366
0.352
cancer
0.509
0.526
0.490
0.641
0,509
ARI
digits
0,589
0,571
0.576
0.627
0,559
faces
0.370
0.388
0.395
0.392
0,359
mnist
0.270
0.222
0.218
0,191
0.192
birds
0.449
0.449
0.442
0.456
0.441
Avg
0.471
0.465
0,452
0.467
0,453
iris
0.803
0.795
0.732
0.732
0.803
wine
0,424
0.424
0.413
0.389
0.424
NMI
0.425
0.471
0.459
0.528
0.425
digits
0.718
0.726
0,707
0.754
0.727
faces
0.539
0.534
0,549
0.549
0.556
mnist
0.291
0.282
0.306
0.307
0.250
birds
0.748
0.747
0.756
0.764
0.743
Avg
0.564
0.569
0.560
0.575
0.561
iris
0,869
0.862
0,808
0,809
0.871
wine
0.616
0.616
0.640
0.601
0.616
Purity
cancer
0.816
0.818
0.805
0.836
0.816
digits
0.677
0.667
0.654
0.715
0.679
faces
0,460
0.477
0.478
0.488
0.467
mnist
0.310
0.286
0.283
0,278
0.308
birds
0.555
0.550
0.543
0.516
0.559
Avg
0.615
0.611
0.602
0.606
0.616
iris
1.1
506101.2
510680.6
507149.4
505809.8
Dasgupta
wine
7655.9
7655.9
7545.7
7564,2
7655.9
cancer
153644.7
153519.2
156220.4
156893.8
153843.2
digits
39292919.2
39315744.3
39299184.6
39215081.5
39289534.3
faces
1703728.2
1703696.7
1706886.4
1703361.3
1704833.1
mnist
11193 10
11195x
11194 10
11185x 10
11195 10
birds
5198 10"
10"
5196x 10
5183 10"
5201 x 10
Avg
x3"1x10'
2342x 10"
2341 x
2338 10"
2342x100
In our experiments, the ARI and NMI scores are calculated by taking the best score obtained over the clusterings formed by considering all possible thresholded-cuts to the output dendrogram. For larger datasets, we consider cuts only at threshold values scaled at a constant factor (i.e. logarithmic-nn mann cuts).
Table contains the results obtained for our quality evaluations. We also plot the scores obtained by approximate Centroid HAC as function of see Figure 6, Figure 7, Figure 8, Figure 9, and Figure 10.
We observe that the quality of the clustering produced by approximate Centroid HAC generally comparable that of the exact Centroid HAC algorithm. On average, the quality slightly better in some cases, but we attribute this to noise. In particular, we observe that for the value of e = 0.1, we consistently get comparable quality that of exact centroid: the ARI and NMI scores are average within factor of 7% and 2% to that of exact Centroid HAC, respectively. We also obtained good dendrogram purity score and Dasgupta cost as well, with values within 0.3% and 0.03%, respectively.
Non-Monotoniccty of CentroidHAC Unlike other HAC algorithms, the costs of merging clusters for centroid HAC is not monotone (i.e., non-decreasing). The monotonicity property of HAC algorithms useful when producing the clusterings for applications from the output dendrgoram: typically the dendrogram is cut at certain thresholds, and the disconnected subtrees obtained are flattened to compute the clusters. Here, cutting dendrogram a given threshold returns well-defined and
23

---

unique clustering. However, this is not the case with Centroid HAC. Indeed, for given threshold value, we can obtain different clusterings depending on how we define cut the dendrogram. For e.g., if two nodes U and V exists in the output dendrogram with associated merge costs (i.e., cost incurred the time of merging the two clusters to form that node) of U being greater than V, and V is an ancestor of U (which is a possibility for Centroid HAC). Then, given threshold value cVs < < (V). we could either cut at (or above), or stop somewhere below U.
We would like to characterize and study this non-monotonicity of Centroid HAC in real-world datasets. For this, we define the following notion: for nodes U, V the output dendrogram, the pair (U, V) is called a 8- f-inversion if V is an ancestor of U and cost(U) 2 (1 + 8)oost(V)) where cost(U) is the merge cost associated node U.
We calculate the number of such inversions incurred by exact Centroid HAC, and compare with the inversions incurred by approximate algorithm. Figure 5 shows the number of d-inversions incurred on the benchmark datasets. We observe that for small values of c, approximate Centroid HAC has similar number of inversions as that of exact Centroid HAC.
E.2 Running Time Evaluation
Figures 4a and 4b shows the running times on varying slices of the SIFT-1M 1M dataset using one thread and 192 parallel threads, respectively. For the approximate methods, we considered e 0.1. Figure 4c further compares the heap and bucket based approaches as a function of
We observe that the bucket based approach is very slow for small values of due to many redundant nearest-neighbor computations. Yet, at 0.1, both algorithms, with 192 threads, obtain speed-up ups of up to 175x with an average speed-up of 22x compared to the exact counterparts. However, single thread, the bucket based approach fails scale, while the heap based approach still achieves significant speed-ups of upto 36x with an average speed-up of 5x. Overall, our heap-based approximate Centroid HAC implementation with e 0.1 demonstrates good quality and scalability, making it a good choice in practice.
Stale Merges and Number of Queries We compute the number of stale merges (see Section I) incurred by our algorithm on various benchmark datasets. See Table 4. We observe that, on average, the number of such stale queries are incurred about 60% of the time compared to the number of actual merges (i.e. number of points).
Table 4: Number of Stale Merges
Table 5: Number of ANNS Queries
Datasct
n
Controida
Dataset
Controida (Hecap
Controido i (Bucket)
iris
150
123
iris
561
41
wine
178
wine
686
7011
569
497
2167
24852
digits
1797
875
digits
5583
48523
faces
faces
mnist
70000
33039
mnist
221086
2481831
birds
236415
581012
512198
covtype
2292518
34770413
We also compare the number of nearest-neighbor queries made by the heap and bucket based algorithms. As expected, the number of NNS queries made by the bucket-based algorithms is order of magnitude higher than that of the heap based approach. This is due to many redundant queries performed each round by the bucket-basee algorithm. However, these queries can be performed in parallel, thus resulting in good speed-ups for this algorithm when run on many cores.
24

---

Centroid;,c cs (Heap)
Controld:.cs (Heap)
Centroid,,1 (Hepp)
Centroid,,) (Heap)
Centroid:: (Heap)
Centroid;, (Heap)
s-iiversions
Centroid; (Heap)
# d-Inversioos
Centroid; (Heap)
Centrold; (Heap)
Centrold; (Heap)
8
Centroldeact (Fastcluster)
Centrold (Fastcluster)
6
2
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
(a) iris
(b) wine
Centrold, (Heap)
3500
Centroida (Heap)
8 Inversions
40
Centrold; (Heap)
Controid, (Heap)
Centroid,, (Heap)
stone
2500
3000
Centroids: (Heap)
Centroida (Heapp
Centroida, (Heap)
Centrold; (Heap)
Centroida (Heap)
Centroid (Fastcluster)
2000
Centroid (Fastcluster)
20
1500
1000
500
0.0
0.2
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
(c) cancer
(d) digits
600
Centrold (Heap)
Controld,; (Heap)
Centroides (Heap)
Centroid, (Heap)
Controld (Heap)
Centroid (lastcluster)
0.0
0,2
0.4
0.6
0.8
1.0
(e) faces
Figure 5: Non-Monotonicity of Centroid HAC: No. of 5-inversions vs 8
25

---

ARI
NMI VS
0.85
Centroid, (Heap)
Centrold, (Heap)
Centroid, (Bucket)
0.82
Centroid, (Buckel)
0.80
Controldean (Fastcluster)
Controldean (Fastcluster)
0.80
0.75
080
NMI
0.78
0.70
0.76
0.74
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Dendrogram Purity vs E
Dasgupta Cost
0.90
Centroid, (Heap)
Centroid, (8 uckket)
514000
(Heap)
Centroid, (Bucket)
Derdicoram Purty.
0.88
Controld (Fastcluster)
Centroid astcluster
Dasguupta Cast
512000
0.84
510000
0.82
508000
0.80
0.0
0.8
Figure Quality Evaluations of the iris dataset
ARI
NMI VS
0.40
Centrold, (Hoap)
Controld, (Heap) Centroid, (Bucket)
Centroid, (Bucket) Controlduas (Fastcluster)
0.44
0.39
Controlduan (Fastclustor)
0.38
0.37
NMI
0.36
0.35
0.34
0.40
0.33
0.39
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Dendrogran ram Purity g
Dasgupta Cost vs
Centrold, (Heap)
7700
Centrold, (Heap)
Dendrogram Purty
0.64
Centroldiain (Fastcluster)
Centroid, (8 Bucket)
7675
Centroid, (Bucket)
Centroid (lastcluster)
0.63
Dasqupta Cost
0.62
7600
7575
0.61
7550
0.60
7525
Figure Quality Evaluations of the wine dataset
26

---

ARI VS
NMI VS
Centroid, (Heapp Centroid, (Bucket)
Centrold, (Heap)
0.625
Centroid, (Bucket)
0.600
Controldwad (Fastcluster)
Centroldean (Fastclutter)
0.50
0.550
NWH
0.48
0.46
0.500
0.44
0.450
0.42
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Dendrogram Purity vs e
Dasgupta Cost
0.84
Centroid, (Heap)
Centroid, (8 uCuce)t
157000
(Hosp)
Derdregram Purty
0.83
Controld (Fastcluster)
Centroid astcluster!
Centroid, (Bucket)
0.82
Dasgupta Cast
156000
0.81
0.80
0.79
0.0
0.8
Figure 8: Quality Evaluations of cancer dataset
ARI
NMI VS
Centrold, (Heap)
Controld, (Heap) Centroid, (Bucket)
0.65
Centroid, (Bucket)
0.75
Controlduan (Fastcluster)
Controlduas Fastcluster)
0.70
0.55
NMI
0.50
0.65
0.45
0.60
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Dendrogran ram Purity g
Dasgupta Cost vs
Centroid, (Heap) Centroid, (8 ucceet)
Centroid, (Heapp Centroid, (Bucket)
0.75
3.950
Dendiogram Purty
0.70
Centroldwwan (Fastcluster)
Dasglapta Cost
3.945
Centroid If (Fastclutter
0.65
3,940
0.60
0.55
3.925
0.50
3.920
Figure 9: Quality Evaluations of the digits dataset
27

---

ARI
NMI VS
Centrold, (Heap) Centroid, (8 ubucket)
Centrold, (Heap)
Centroid, (Bucket)
0.35
Controldaan (Fastcluster)
Controld (Fatclluterr)
AR1
0.30
NME
0.48
0.46
0.44
0.20
0.42
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Dendrogram ram Purity g
Dasgupta Cost vs
Centrold, (Heap)
Centroid, (Heap)
0.48
Centroid, (Bucket)
Centroid, (Bucket)
Dendrogram Purtt
0.46
Controlduan (Fastcluster)
1.710
Controldwws (Fastcluster)
Dasgugta Cost
0.64
1.700
0.42
1.704
0.36
Figure 10: Quality Evaluations of the faces dataset
28

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We claim fast approximate centroid HAC in both theory and practice. Our theoretical claims are proven in Section 3 and Section 4 and our practical claims justified by the experiments in Section 5.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 or 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
be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long 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: As acknowledged in the introduction, we use one ANNS data structure to obtain our theoretical bounds and different one to obtain good empirical rumning times. This assumption is inherited from the current state of the art the ANNS area, where the fastest known methods (including the one that we evaluate) do not come with strong theoretical guarantees. 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 (c.g.. independence assumptions, noiseless settings, model well-specification, 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 on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-teny system might not be used reliably to provide closed captions for online lectures because it fails 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
29

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The main formal claims the formal guarantees for the algorithms for dynamic ANN for adaptive updates and our centroid HAC algorithms- presented in Section 3 and Section respectively. These sections also include formal descriptions of the algorithms used, including pseudo-code. Proofs of the guarantees of these algorithms are provided in the appendix, though proofs are informally discussed in the introduction and respective sections. The paper also provides citations for formal guarantees where necessary (e.g. Theorem 1) reproves results from previous work so as to state these previous results in a way amendable how they are used in this work. Guidelines:
which it builds and
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 to provide intuition.
Inversely, any informal proof provided the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The code is submitted as part of the supplementary material. Further, Appendix discusses the implementation details of our algorithms.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If 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 novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to 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 to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility. which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a 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 or instructions for how to construct the dataset).
30

---

(d) We recognize that reproducibility may be tricky in some cases, in which case authors are 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., to registered users), but should possible for other researchers 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 instructions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code is submitted as part the supplementary materials with instructions how reproduce the experiments. The datasets used in this paper open-source and have been cited appropriately (see Section and Appendix E).
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
ssisssslioosoiyo for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" 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 benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips. ctcccc//pp//
for more details. The authors should provide instructions on data access and preparation, including how 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. If only subset of experiments should state which ones are omitted from the script and why.
reproducible, they
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is 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 experimental results are summarized in Section 5, and described in more detail in Appendix E.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Ys]]
Justification: The algorithms in this paper deterministic. and hence the quality evaluations are the same across runs. For the scalability study, we only report the mean running times since the variance in running times is low.
Guidelines:
The answer NA means that the paper does not include experiments.
31

---

The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
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).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one 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 not to show in tables or figures symmetric error bars that would yield results are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Ye]]
Justification:
The compute resources used are described in Appendix E.
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 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 / http://bblc./tiiiiciiiieeeeeeeee
didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurIPS Code of Ethics https::/neeurpps
Answer: [Yes]
Justification: The authors have read the NeurIPS Code of Ethics and confirmed that this research is consistent with it.
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., there is a special consideration due 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 deals with speeding up common and generic clustering technique.
Guidelines:
The answer NA means that there is socictal impact of the work performed.
32

---

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), fairness 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 not tied 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 point that 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 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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
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 (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere 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 is 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
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Datasets are specified and the licenses are stated in Section and the datasets section of Appendix E.
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 or dataset.
The authors should state which version of the 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.
33

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. 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 be provided.
If this information is not available online, the authors encouraged to reach out the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/moodll as part of 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 is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
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 details about compensation (if any)?
Answer: [NA]
Justification: the work does not involve crowdsourcing nor research with human subjects. Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According 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
Question: 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the work did not involve crowdsoureing nor research with human subjects. Guidelines:
The answer NA means that the paper does 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 we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
34

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "AfC704LgSB", "reviewer": "Reviewer_Pmjq", "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.\n\nCommon 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).\nAnother 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. \nTechnical 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.\n\nSince 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.\n\nTo 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. \n\nTo 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.", "questions": "In Line 140, don't you want the weighted average  and not the weighted sum?\n\nWhat is the objective function you use to compare the quality of HAC soluton and prove approximation factor gaurantee?\n\nWhy 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).\n\nWhat 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?\n\nYou cite [2, 14] for dynamic non-adaptive ANN, However I cant find the corresponding results in either. Please be more specific.", "limitations": "Would be good to mention a more detailed limitations section apart from those mentioned in conclusion / open problems.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* Important problem of getting sub-quadratic algorithms for hierarchical clustering, quite reasonably well written paper.\n* Theoretical backing + empirical applications using the theory ideas are given, which is nice\n* Good set of evaluations and the numbers are great -- quality is better and significantly faster.\n* 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.\n\nThe 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.\n\nThe 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and suggestions. We respond now to the specific questions of the reviewer.\n\n> “Datasets chosen for evaluation can be more diverse.”\n\nTo 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.\n\n> c-approximation for the HAC problem in Theorem 5\n\nThanks for pointing this out. The definition of c-approximate HAC is given on l138. We will improve the writing to clarify this.\n\n\n> “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?”\n\nWe 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. \n\nMerge-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):\n*  If there are at most 2^i total points in bucket i, build a new ANNS with all points in bucket\n*  Else move all points from bucket i to bucket i+1 as “loose” points\n\nRoughly 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.\n\nCovering 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.\nHowever, 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.\n\n> “In Line 140, don't you want the weighted average and not the weighted sum?”\n\nYes, thank you for flagging this.\n\n> “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).”\n\nWe 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.\n\n> “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?”\n\nComputing 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. \n\nIn 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\n\nHowever, 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.\n\n\n> Would be good to mention a more detailed limitations section apart from those mentioned in conclusion / open problems.\n\nThank you for the suggestion. We will add a section outlining two main limitations:\n*  the use of different ANNS data structure in the theoretical and empirical results.\n*  quality evaluation limited to medium-sized datasets, due to the lack of suitable publicly available embedding datasets", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EBoiOhdVrR", "reviewer": "Reviewer_vHLH", "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.\n\nAn 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.", "questions": "Minor comment - the usage of $Q$ for both covering net and priority queue is somewhat confusing.  Please consider modifying this.", "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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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).\n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and suggestions. We respond now to the specific questions of the reviewer.\n\n> 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).\n\nWe 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.\n\n> 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.\n\nWe 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.\n\n> Q1: Minor comment - usage of Q for both covering net and priority queue is somewhat confusing. Please consider modifying this.\n\nThank you for pointing this out, we will fix it.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wzgJ4wp1TC", "reviewer": "Reviewer_Dgto", "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.", "questions": "Q1, Q2. See comments W1, W2 above.\n\nQ3. 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.\n\nQ4. 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.\n\nQ5. Is it possible to have a (rough) estimate of the increase in execution time as the value of \\epsilon decreases?", "limitations": "The authors discuss the limitations. I do not see any potential negative societal impact of this work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "S1. A dynamic approximate NN search algorithm with adaptive updates is proposed.\n\nS2. A centroid-linkage HAC algorithm is presented that exploits the approximate NN search algorithm.\n\nS3. Theoretical performance bounds are presented and proved.\n\nS4. 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.\n\nW2. It is not clear if the ‘approximate centroid HAC’ idea is novel or not (independently of the ANNS algorithm used in the implementation).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and suggestions. We respond now to the specific questions of the reviewer.\n\n> Q1/W1: Coherence and clarifying why we use a different ANNS algorithm in theory and in practice.\n\nWe 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.\n\n\n> Q2/W2: Novelty of “approximate centroid HAC”\n\nWe 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.\n\n\n> 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.”\n\nWe 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.\n\n\n> Q4: Using larger datasets to show more meaningful scaling results\n\nIn 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. \n\nNotably, 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.\n\nWe 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.\n\n> Q5:Execution time v/s $\\epsilon$\n\nThis 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mIF9qYaoDc", "reviewer": "Reviewer_JGDe", "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.", "questions": "-Do you have any intuition as to why \"worse\" approximation factors often seem to give better clustering results (as your Table 1 indicates)?", "limitations": "The limitations are addressed in the checklist.", "rating": 9, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and suggestions. We respond now to the specific questions of the reviewer.\n\n> 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.\n\nThis 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.\n\nOn the more theoretical side, we note that our theoretical results for ANNS could be used more generally in other clustering algorithms that require adaptivity.\n\n\n> “Do you have any intuition as to why \"worse\" approximation factors often seem to give better clustering results (as your Table 1 indicates)?”\n\nThis 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their thoughtful comments and suggestions. We reply to the questions and comments of each reviewer individually in the corresponding rebuttal fields. 

# Coherence:
First, we would like to clarify a point raised by the reviewers regarding the coherence of our theoretical and experimental results, namely that the theoretical algorithm and experimental evaluation use different ANNS algorithms (a point brought up by reviewers vHLH and Dgto).

We acknowledge this limitation and would like to point out that we have been open about it in the checklist of our submitted paper. We would like to discuss the issue from two angles.

In terms of the coherence of the paper, the crux of the paper is the efficient approximate centroid HAC algorithm. In the paper we show that it gives a very efficient theoretical algorithm (using our new data structure based on LSH) and an algorithm which is very efficient in practice (using state of the art ANNS techniques). So in that sense the paper presents a complete story.

In terms of the theoretical and empirical part considering different algorithms, while ideally both settings would use exactly the same algorithm, we would like to point out that our situation is still somewhat better than in multiple other prominent clustering problems. In our case, both the theoretical and practical algorithms use the same meta-algorithm (instantiated using different data structures). On the other hand, in the case of many other clustering problems, there is an even larger gap between the theoretical and practical approaches, for example:
*  Correlation clustering - while the best known algorithms are obtained by solving a linear program (see https://dl.acm.org/doi/abs/10.1145/3618260.3649749 or https://arxiv.org/pdf/2309.17243), in practice a simple local search / Louvain-based algorithm is used (see section 4.1 of https://hal.science/hal-04251953/file/openproblems.pdf).
*  Modularity clustering - the best known approximation is obtained by solving an SDP (https://www.sciencedirect.com/science/article/pii/S0022000020301124?fr=RR-1&ref=cra_js_challenge). Again, Louvain-based algorithms are used in practice.
*  In the case of k-means, while the best known approximation is a constant obtained via the primal-dual method (https://dl.acm.org/doi/abs/10.1145/3519935.3520011), in practice Lloyd’s heuristic paired with k-means++ seeding is used which has a logarithmic approximation guarantee.
*  Balanced graph partitioning - coarsening combined with a brute-force algorithm is used to obtain the best results in practice. On the other hand, the algorithms for solving the corresponding theoretical formulations: balanced cut and multiway cut are entirely different.

# Additional Experiments:
Several reviewers also mentioned that adding more experimental results on more diverse / large datasets would be helpful. To address this, we will include quality and scaling experiments on additional labeled datasets for the revised version. First is the standard Imagenet dataset which contains around 1.2M images of everyday objects from 1000 different classes. Each image is passed through ConvNet [23] to obtain an embedding of 1024 dimensions, similar to the Birds dataset. Next, we consider two large text datasets (reddit and arxiv) from the recent MTEB work [A]. The reddit dataset consists of ~420K (embeddings of) post titles and the goal is to cluster them into (50 different) subreddits. The ArXiv dataset consists of ~730K (embeddings of) paper titles and the goal is to cluster them in (180 different) categories. The embeddings are 1024 dimensional in both arXiv and reddit datasets.

[A] Niklas Muennighoff, Nouamane Tazi, Loïc Magne, and Nils Reimers. 2022. MTEB: Massive Text Embedding Benchmark. arXiv preprint arXiv:2210.07316 (2022). https://doi.org/10.48550/ARXIV.2210.07316

Meta-review: This paper gives faster algorithms for centroid linkage clustering.  There has been a general interest in speeding up notoriously unscalable hierarchical clustering methods. The paper gives and algorithm with strong theoretical and empirical evidence. The reviewers agreed these results will be of interest to the clustering community at NeurIPS.
Decision: Accept (poster)