Parallel Hierarchical Agglomerative Clustering in Low Dimensions

MohammadHossein Bateni, Laxman Dhulipala, Willem Fletcher, Kishen N Gowda, D Ellis Hershkowitz, Rajesh Jayaram, Jakub Łącki · 2025

Read Parallel Hierarchical Agglomerative Clustering in Low Dimensions by MohammadHossein Bateni, Laxman Dhulipala, Willem Fletcher, Kishen N Gowda, D Ellis Hershkowitz, Rajesh Jayaram, Jakub Łącki (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-20047.txt.

Introduction

MohammadHossein Bateni and co-workers give fast parallel algorithms for hierarchical clustering with tricky distance rules, in a 2025 paper. The clustering method repeatedly merges the closest pair of groups. Near-optimal parallel algorithms existed only for distance rules that never decrease after a merge.

Popular rules such as centroid and Ward's distance can decrease, and no parallel method was known for them. The authors prove the merge tree stays shallow for a broad class of such rules in low dimensions, which yields efficient parallel algorithms. A hardness result suggests the low-dimension limit is real: in full dimension the problem resists parallel solution. The structural finding may interest clustering researchers broadly.

Catalog record

CREATORMohammadHossein Bateni, Laxman Dhulipala, Willem Fletcher, Kishen N Gowda, D Ellis Hershkowitz, Rajesh Jayaram, Jakub Łącki
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE138 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-20047

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Parallel Hierarchical Agglomerative Clustering in Low Dimensions MohammadHossein Bateni, Laxman Dhulipala, Willem Fletcher, Kishen N Gowda, D Ellis Hershkowitz, Rajesh Jayaram, Jakub Łącki Abstract Hierarchical Agglomerative Clustering (HAC) is an extensively studied and widely used method for hierarchical clustering in ℝ k \mathbb{R}^{k} based on repeatedly merging the closest pair of clusters according to an input linkage function d d . Highly parallel (i.e., NC) algorithms are known for ( 1 + ϵ ) (1+\epsilon) -approximate HAC (where near-minimum rather than minimum pairs are merged) for certain linkage functions that monotonically increase as merges are performed. However, no such algorithms are known for many important but non-monotone linkage functions such as centroid and Ward’s linkage. In this work we show that a general class of non-monotone linkage functions—which include centroid and Ward’s distance—admit efficient NC algorithms for ( 1 + ϵ ) (1+\epsilon) -approximate HAC in low dimensions. Our algorithms are based on a structural result which may be of independent interest: the height of the hierarchy resulting from any constant-approximate HAC on n n points for this class of linkage functions is at most poly ⁡ ( log ⁡ n ) \operatorname{poly}(\log n) as long as k = O ⁡ ( log ⁡ log ⁡ n / log ⁡ log ⁡ log ⁡ n ) k=O(\log\log n/\log\log\log n) . Complementing our upper bounds, we show that NC algorithms for HAC with these linkage functions in arbitrary dimensions are unlikely to exist by showing that HAC is CC-hard when d d is centroid distance and k = n k=n . 1 Introduction Hierarchical Agglomerative Clustering (HAC) is a greedy bottom-up clustering algorithm which takes as input a collection of n points \mathcal{P}\subseteq\mathbb{R}^{k} and a symmetric “linkage” function d:2^{\mathcal{P}}\times 2^{\mathcal{P}}\to\mathbb{R}_{\geq 0} which gives the ‘‘distance’’ between clusters of points. 1 1 1 One can also study linkage functions that give the “similarity” between clusters; see, e.g., [ 10 ] . HAC begins with the singleton clustering \mathcal{C}=\{\{p\}:p\in\mathcal{P}\} . Then, over the course of n-1 steps, it merges the two closest clusters. In particular, in each step if A,B\in\mathcal{C} are the clusters in \mathcal{C} minimizing d(A,B) , it removes A and B from \mathcal{C} and adds A\cup B to \mathcal{C} . We say that d(A,B) is the value of the merge. The resulting hierarchy of clusters on \mathcal{P} naturally corresponds to a rooted binary tree of clusters called a dendrogram. In particular, the dendrogram has 2n-1 nodes; A\cup B is a node of the dendrogram with children A and B if at some point HAC merges clusters A and B . See Figure 1 . If the merged clusters A and B do not satisfy d(A,B)\leq\min_{C,D\in\mathcal{C}}d(C,D) in each of the n-1 iterations but satisfy d(A,B)\leq c\cdot\min_{C,D\in\mathcal{C}}d(C,D) for some fixed c\geq 1 , then the HAC is said to be c -approximate. HAC has seen widespread adoption in practice because, unlike other clustering algorithms (e.g., k -means), it does not require users to pre-specify the number of desired clusters. Furthermore, after running the algorithm once, the output dendrogram can be cut to obtain clusterings with varying numbers of clusters. HAC implementations are available in many widely-used data science libraries such as SciPy [ 37 ] , scikit-learn [ 30 ] , fastcluster [ 28 ] , Julia [ 20 ] , R [ 31 ] , MATLAB [ 24 ] , Mathematica [ 21 ] and many more [ 25 , 26 , 36 ] . Likewise, its adoption is explained by the fact that it performs well for many natural objective functions, both in theory [ 19 , 29 ] and practice [ 2 , 12 , 39 , 38 , 10 , 9 , 8 , 15 , 7 ] . Different linkage functions give different variants of HAC. In roughly ascending order of complexity, some common linkage functions define the distance between two clusters A,B\subseteq\mathbb{R}^{k} as: • Single-linkage : the minimum distance d_{\mathrm{single}}(A,B):=\min_{(a,b)\in A\times B}||a-b|| . • Average-linkage : the average distance d_{\mathrm{average}}(A,B):=\frac{1}{|A||B|}\sum_{(a,b)\in A\times B}||a-b|| . • Centroid-linkage : the distance between centroids d_{\mathrm{cen}}(A,B):=||\mu(A)-\mu(B)|| where \mu(X):=\sum_{x\in X}x/|X| is the centroid of X\subseteq\mathbb{R}^{k} . • Ward’s-linkage : how much the merge would increase the k -means objective d_{\mathrm{Ward}}(A,B):=\Delta(A\cup B)-\Delta(A)-\Delta(B) where \Delta(X):=\sum_{x\in X}||x-\mu(X)||^{2} is the k -means objective. (a) Input \mathcal{P} . (b) HAC Clustering. (c) Dendrogram. Figure 1 : An example of HAC run on \mathcal{P}\subseteq\mathbb{R}^{k} . Recently, the widespread usage of HAC on large datasets has motivated considerable interest in developing the theory of efficient parallel HAC algorithms. For the simpler linkage functions of single and average, efficient parallel algorithms are known. More specifically for single-linkage, the problem is reducible to computing the clustering of the Euclidean MST and a recent work gave a work-optimal and poly-logarithmic depth parallel algorithm in the comparison model for this problem [ 8 ] . On the other hand, another line of recent work showed that average-linkage HAC on general graphs is \mathsf{P} -complete, and thus unlikely to be in \mathsf{NC} [ 10 ] . Motivated by this hardness, [ 10 ] showed that for any constant \epsilon>0 , (1+\epsilon) -approximate average-linkage HAC can be done with \operatorname{poly}(\log n) depth and \operatorname{poly}(n) work 2 2 2 f(n)=\operatorname{poly}(n) if there exists some constant c such that f(n)\leq O(n^{c}) . Throughout this work we use the standard work-depth model of parallelism, which is equal up to logarithmic factors in the depth to other standard parallel models like different PRAM variants, see, for example, [ 4 ] . (i.e., it is in the complexity class NC). 3 3 3 More generally, they show that this is true even if the input is a graph with arbitrary edge weights. Despite the progress over the past few years for single- and average-linkage, there is much less progress on other linkage-functions such as centroid- or Ward’s-linkage, especially when (1+\epsilon) -approximation is allowed. Recently, [ 22 ] gave an O(\log^{2}n) -approximate and \operatorname{poly}(\log n) -round distributed algorithm for centroid HAC and an O(1) -approximate algorithm that performed well in practice but had no provable guarantees on its round-complexity. Unlike other linkage functions, centroid- and Ward’s-linkage are directly related to cluster centroids. Thus, developing fast parallel algorithms for centroid- and Ward’s is especially motivated by the important practical applications of clustering that rely on cluster centroids (e.g., when leveraging clustering in practical nearest-neighbor search indices [ 33 , 13 , 11 ] ). Furthermore, Ward’s-linkage has a close theoretical connection to k -means clustering and, in fact, provably yields clusterings that are good approximations of the k -means objective under certain assumptions [ 19 ] . The fact that parallel algorithms for single- and average-linkage exist but not centroid- and Ward’s-linkage is explained by the helpful fact that single- and average-linkage are monotone , even under arbitrary merges. In particular, given a set of clusters \mathcal{C} , merging any pair of clusters in \mathcal{C} results in a new set of clusters whose minimum distance according to both d_{\mathrm{single}} and d_{\mathrm{average}} has not decreased. This property reduces computing the single-linkage dendrogram to post-processing the edges of the Euclidean minimum spanning tree [ 8 ] . For average-linkage, this monotonicity property enables the usage of standard bucketing tricks in parallel algorithms. In particular, [

Read the complete text