Hierarchical Agglomerative Graph Clustering in Poly-Logarithmic Depth 
Authors: Laxman Dhulipala
David Eisenstat
Jakub Lacki
Vahab Mirrokni
Jessica Shi
Venue: NeurIPS 2022 Accept (2022)
Keywords: hierarchical clustering
graph clustering
parallel algorithms
parallel graph algorithms
scalable algorithms

Abstract: Obtaining scalable algorithms for \emph{hierarchical agglomerative clustering} (HAC) is of significant interest due to the massive size of real-world datasets. At the same time, efficiently parallelizing HAC is difficult due to the seemingly sequential nature of the algorithm. In this paper, we address this issue and present ParHAC, the first efficient parallel HAC algorithm with sublinear depth for the widely-used average-linkage function. In particular, we provide a $(1+\epsilon)$-approximation algorithm for this problem on $m$ edge graphs using $\tilde{O}(m)$ work and poly-logarithmic depth. Moreover, we show that obtaining similar bounds for \emph{exact} average-linkage HAC is not possible under standard complexity-theoretic assumptions.

We complement our theoretical results with a comprehensive study of the ParHAC algorithm in terms of its scalability, performance, and quality, and compare with several state-of-the-art sequential and parallel baselines. On a broad set of large publicly-available real-world datasets, we find that ParHAC obtains a 50.1x speedup on average over the best sequential baseline, while achieving quality similar to the exact HAC algorithm. We also show that ParHAC can cluster one of the largest publicly available graph datasets with 124 billion edges in a little over three hours using a commodity multicore machine.

known to find high-qualie clusters in real-world Hierarchical Agglomerative Graph Clustering in Poly-Logarithmic Depth
Laxman Dhulipala University of Maryland and
David Eisenstat Google Research eisenegoogle.c com
Jakub Lącki Google Research
Google Research l aaxman@umd edu
jlacki@google.co con
Vahab Mirrokni Google Research mi mirrokni@google.
Jessica Shi MIT CSAIL jeshi@mit.
Abstract
Obtaining scalable algorithms for hierarchical agglomerative clustering (HAC) is of significant interest due to the massive size of real-world datasets. At the same time, efficiently parallelizing HAC is difficult due to the seemingly sequential nature of the algorithm. In this paper, we address this issue and present ParHAC, the first efficient parallel HAC algorithm with sublinear depth for the widely-used average- linkage function. In particular, for this problem m edge graphs using ((m) work and poly-logarithmic depth. Moreover, we show that obtaining similar bounds for exact average- average-linkage HAC is not possible under standard complexity-theoretic assumptions.
provide (1 + -approximation algorithm
We complement our theoretical results with a comprehensive study of the ParHAC algorithm in terms of its scalability, performance, and quality, and compare with several state-of-the-art sequential and parallel baselines. On broad set of large publicly-availabee 50. 1x speedup on average over the best sequential baseline, while achieving quality similar to the exact HAC algorithm. We also show that ParHAC can cluster one of the largest publicly available graph datasets with 124 billion edges in a little over three hours using a commodity multicore machine.
real-world datasets, find that ParHAC obtains a
1 Introduction
Hierarchical Agglomerative Clustering (HAC) 49 72) is fundamental and widely-used cluster- ing method with numerous applications in unsupervised learning, community detection, and biology. Given n input points, the HAC algorithm starts by forming separate cluster for each input point, and proceeds in n steps. Each step replaces the two most similar clusters by its union. The exact notion similarity between two clusters specified by configurable linkage function. This function is typically given all pairwise similarities between points from the two clusters. Some of the most popular choices are average-linkage (the arithmetic mean of all similarities), single- linkage (the maximum similarity), and complete-linkag (the minimum similarity). Among these, average-linge linkage of particular importance,
applications [25 55 56] 65
We note that HAC also be defined in terms of input points and dissimilarities between the points. We discuss and compare both settings Scction T.2
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Although HAC has been of significant interest to statisticians, computer scientists, and clustering practitioners since the 1960s, applying HAC to very large datasets remains a major challenge. A significant source of difficulty is the need to compute all pairwise similarities between sets of points, which HAC implementations typically perform at the start of the algorithm at the expense of (n²) work and space [58] 59 [76]. To address this difficulty, two directions have recently been explored in the literature. The first has focused on designing approximate sub-quadratic work algorithms in the dissimilarity setting, using sketching and approximate nearest neighbor (ANN) techniques 4 57]. The second approach focuses on the similarit-ggraph setting, and is what we build on this paper. Here, the idea is to build a (typically sparse) similarity graph over the pointset input, e.g., by representing each point as a vertex, connecting a point to its & most similar neighbors, and then applying graph- based HAC algorithm this similarity graph [8] Surprisingly, despite only using& a sub-quadratic number of similarities, similarity graph-based HAC algorithms can match or sometimes even surpass the quality of algorithm using the full (n²)) similarity matrix (38)
Prior works on these approaches 4 38 give provable guarantees on the quality of the resulting approximation algorithms; in fact, both yield (1 + -aapprooime HAC algorithms, as proposed by [57]. Specifically, a (1 + -appproxieette HAC algorithm is an algorithm in which each step only merges edges that have similarity at least W Wmax/(L + +) where Wmax is currently the largest similarity i Hence, an (1 + ->approxiee algorithm is constrained to merge an edge that is "close" in similarity to the merge that the exact algorithm would perform. At the same time, the algorithm has flcxibility in which edge to merge, which can potentially be algorithmically exploited.
Despite the progress on scaling up HAC, further improvements appeared challenging due to the seemingly inherently sequential nature of the HAC algorithm [ [5S]. Several recent attempts at parallelizing HAC either rely on optimistic assumptions on the input 773 79,, significantly diverge from the original algorithm, potentially impacting quality [8 23 55), or deliver weak approximation guarantees [57]. Understanding if HAC can be solved in sub-quadratic work and poly-logarithmic depth (or even polynomial work and sub-linear depth) has thus remained an intriguing open question, even when allowing for approximation.
1.1 Our Contributions
In this paper, we introduce the first efficient parallel algorithm computing (1 + e) -)-approximate average-linkage HAC with poly-logarithmic depth and near-linear total work. We use the standard work-depth model of parallel computation [6] to analyze the theoretical cost of our algorithm, where briefly, the work is the total number of operations performed, and the depth is the longest chain of dependencies. The work-depth model is the parallel model used in variety of recent papers on seared-memorg multicore algorithms for graph problems 33 35
pointset clustering [79], as well as tree-based algorithms [74] 75). Deriving good bounds for the work and depth of an algorithm also implies good bounds for the problem in a variety of other models for parallelism, such as different
PRAM variants, by using efficient simulation results (e.g., see [14 15)).
The algorithm takes as input a similarity graph, which contains n vertices (representing input points) and m weighted edges (representing nonzero similarities between points).
Theorem 1.1. There is a parallel (1 + c)aaprooximate average-linkag graph-based HAC algorithm that given a similarity graph containing n vertices and m weighted edges runs in Ö(m + n.) work in expectation and has Ollog* n) depth with high probability
For fixed e, our algorithm, which we call ParHAC, runs in poly-logarithmic depth and ((m) -work. Thus, is work-efficient up to logarithmic factors and achieves high parallelism (ratio of work to depth). We note that the same setting, i.c., parametrizing the input size by the number of nonzero similarities, has been recently studied in the sequential case (38), where an Ó(m)-work sequential (1 + -)-approximate algorithm is known. Prior to our result, no average-linkage HAC algorithm with sublinear depth was known (even allowing approximation).
We note that (38] introduce both an exact algorithm for average-linkage HAC running in ((n/m)) work and an approximate algorithu running in Ó(m) work. We define Ó(f(=)) == We note that [57] deals with dissimilarities. but we adapt the definition to similarities in the natural way. 'An algorithm has (z)))) cost with high probability (whp) it has O(k f(n) cost with probability at
least 1 - 1/n².
2

---

On the negative side, we show that allowing approximation is necessary, as obtaining an average- linkage exact HAC algorithm with poly-logarithmic depth is not possible under standard complexity- theory assumptions (i.e., it is P-complete problem). In other words, an exact polynomial-won parallel HAC algorithm for average-linkage in poly-logarithmic depth would imply poly-logaritmmic depth algorithms for all problems solvable in polynomial time (i.e., show that P = NC). Our lower bound formalizes a commonly held belief that the algorithm is inherently sequential 773 and justifies studying the approximate variant of HAC.
Theorem 1.2. Graph-based HAC using gverage-linkage is P-complete.
We complement our theoretical results by providing an efficient parallel implementation of ParHAC. and comparing it with existing graph- based and pointset-based HAC baselines across a broad set of publicly available real-world datasets. For scalability, we show that ParHAC achieves strong speedups relative to other high-quality HAC baselines, achieving 50.1x average speedup over the approximate sequential algorithm from 38 when run on a 72-core machine. Moreover, we study the overall running times of using ParHAC in the pointset setting, and find that ParHAC can cluster significantly larger datasets compared to fastcluster [59], a state-of-the-are pointset clustering algorithm, and achieves up to 417x speedup over fastcluster in end-to-end running time.
We show that the above speedups are achieved without loss (or even with gain) for the final algorithm. In particular, for the Adjusted -ndexIndex quality measure, we find that the quality of ParHAC is on average 3.1% better than the best approximate sequential baseline, and is on average within 3.69% of the best score for any method on the datasets that we study. Finally, we find that ParHAC achieves consistently strong quality results on three other quality metrics that we study compared with the best solutions offered by exact and approximate algorithms.
We have made our implementation publicly available on GitHub
1.2 Graph-Based Hierarchical Agglomerative Clustering
As mentioned earlier in the introduction, our focus in this paper is clustering (typically sparse) weighted graphs where the edge weights represent similarities between vertices. More formally, we study parallel algorithms for the graph-based hierarchical agglomerative clustering (HAC) problem, which takes as input a graph G = (V, F,, w) and proceeds by repeatedly merging the two most similar clusters, where the similarity is given by a configurable linkage function. Equivalently, this process can be viewed in terms of a graph H, whose vertices are clusters, and edges represent clusters of positive similarity (in particular, the edge weights give the similarities between clusters). Initially, when all clusters have size 1, H is equal to G. Each operation of merging two clusters corresponds to contracting an edge of H (we call this operation a merge). In the following, we typically use this alternative view of the algorithm.
The output of the algorithm is dendrogram- rooted binary tree that has single leaf for each vertex in the input graph, with internal nodes corresponding to clusters obtained by merges, and weights of internal nodes representing the similarity of the corresponding merge that formed it.
We focus on the average-linkage measure, which assumes that the similarity between two clusters (X, Y) is equal to E [(.,))ECutxx.)) w(x,w) w)/((x) |YI), that is, the total weight of edges between X and Y. divided by the maximum number of possible edges between the clusters. Throughout this paper, we consider graphs with arbitrary positive edge weights representing similarities. We discuss other linkage measures in the Appendix.
natural question is, why use similarities instead of dissimilarities? Both settings have been previously considered in the literature, and although it hard to argue that one approach is "better" than the other, our primary reason for studying similarities is because the similarity setting is arguably more natural setting for clustering spurse graphs. Specifically, it is natural to assume that the similarity between pairs of vertices not connected by an edge is O, whereas no such assignment of a dissimilarity to missing edges is obvious when edge weights represent dissimilarities.
3

---

1.3 Related Works
ParHAC is inspired by a recent sequential (1+e) -aprrxxmait average- -inkggee-inggeeeeeee HAC algorithm, which runs in ((m) time [38]. However, obtaining a theoretically-effiiiee and practical parallel algorithm requires significant new ideas. The evaluation of [38] studied the difference in quality between exact and (1 + c) -aapproximtte HAC and showed that even moderately small c = 0.1 maintains the quality of exact HAC. Our results on the quality of ParHAC are consistent with these findings.
Efficient parallelizations of HÁC are known in the case of single-linkage (essentially equivalent to maximum spanning forest), and centroid linkage, if one allows Ollgg* n) -n-aappoxximttion [57]. In other cases, the existing parallelizations of exact HAC either use linear depth (60], much larger work [28 62] or do not come with any bounds on the running time [46] 73 79). The ParChain framework [79] for parallel exact HAC on pointsets recently showed that average-linkage HAC can be solved in hours for million-point datasets. Very recently, it was shown that distributed implementation of the RAC algorithm can exactly cluster a billion-point dataset in few hours using 200 machines and 3200 CPUs (73). However, the depth of the algorithm is linear in the worst case, and can be large in practice.
In order to scale hicrarchical clustering to large datasets, several HAC-inspired algorithm have been proposed, including Affinity clustering [8] and SCC [55]. Both algorithms are designed for a distributed setting, in which the number of computation rounds that one can afford is highly constrained. In particular, SCC can be seen as best-effort approximation of HAC, given fixed (usually small) number of rounds to run. We implemented both algorithms (using the framework that we built to develop ParHAC) and included them in our empirical evaluation.
The theoretical foundations of HAC has been developed in recent years [22 27 56]. and have motivated using HAC in real-world settings [20] 21 24 25 64). The version of HAC that takes graph as input has also been studied before, especially in the context of graphs derived from point sets [4 42 48). although without strong theoretical guarantees. Another line of work by Abboud et al. showed that the input points are in the Euclidean space and the Ward linkage method is used 78 approximate HAC can be solved in subquadratic time.
2 Parallel Approximate HAC
In this section we describe our parallel HAC algorithm. which we call ParHAC. We assume that the input is weighted graph G (V, E, w), where : E - R+ gives the edge weights.
Let us now provide some background for the main ideas behind ParHAC. As observed in [73 79,, a simple exact parallel HAC algorithm can be obtained almost directly from the 40-year-old nearest- neighbor chain algorithm 9 The parallel algorithm finds all edges ay such that zy is the highest- weight incident edge to each endpoint, and y. For simplicity, we assume here that all edge weights are distinct. One can see that these edges form a matching (which does not necessarily match all vertices), and the correctness of the searest-neighhor chain algorithm implies that if the endpoints of these edges are merged in parallel, the output is equivalent to what sequential HAC algorithm produces. Following [73], we call this algorithm reciprocal agglomerative clustering (RAC). Clearly, the amount of parallelism in RAC is data-dependent. In particular, it can take a linear number of steps find in our experiments, up 21,081 steps the YouTube (YT)
in the worst case (73), and, real-world graph with just 1.IM vertices and 5.9M edges.
Once we consider (1 + --pppoooiie HAC, the set of edges that we can choose to merge in the first step grows to include all edges whose weight is within (1 + e) factor of Wmax= the largest edge weight in the graph. Let us call these edges (1++)-heavy. A major challenge is that the (1 (1+ e)-heavy edges no longer form a matching, and thus cannot be all merged in parallel. To see this, consider an example where all (1 + eh-bea edges have a common endpoint æ. Once one vertex merges with the size of the cluster represented by x increases, which decreases the weights of all edges incident to x, and result some of these edges may cease to be (1 + hhaava
Considering the (1 + e)-heavy edges motivates the use of geometric layering, a technique where we group the edges into layers based on their weights and process edges in the same layer in parallel (e.g., see [10 [2].. In more detail, let Wmax and Wmin be the ceeiimum-weight and minimum-weight in the graph, respectively. The i-th layer contains all edges with weight between
4

---

Algorithm 1 ParHACCCCnttactLayyerC = (V, B, w) TT, D)
Input: Similarity graph, G, threshold TL. dendrogram D. Ensure: All edges in G have weight < Tr.
1: Let Wmxx be the current maximum-weight edge in G.
2: while Wmax 2 Tr. do
D Outer round
3: Randomly color active vertices of G either red or blue.
4: Let R. B be the sets of red and blue vertices respectively.
5: Let G. = (V, Ec: w) where E. contains all edges in G that have weight 2 Tt, and connect
vertex E B with vertex E R, where the size of y is not smaller than the size of x.
6:
while Exl > do
> Inner round
7:
Select a random priority Tu for b E B.
8:
Let C2 be a random red neighbor for each b E B. Let T = {(Cb, Th, b) b B3. Sort 7 lexicographically. Let T, be triples from T with first component equal to r.
9:
10:
11:
For each r R. select the first prefix of T,, in which the total size of blue vertices
exceeds e|rl
12:
Let M be the set of (red, blue) vertex pairs selected.
13:
Merge vertices in G and Ge based on the pairs from M. updating edge weights in Ge- Remove edges of Ge that have two red endpoints or weight below T'p
15:
Update D based on M. If multiple b E B merge to single r E R. merge them into r in the sorted order.
16:
Remove r R from Ge whose cluster size grew by more than a (1 + e) factor since the start of the outer round.
17:
Recompute Wmax based on the current state of G.
([++e) ((1+))-((+)) Wmax (1+e)-1. ParHAC processes the layers one at a time; to compute the next layer computes the maximum weight edge in the graph W Wmax, and processes all edges between W max] We refer to an iteration of this loop layer-contraction phase.
((1 +
Let us now describe how to implement layer-contraction phase. The pseudocode for the procedure is shown in Algorithm [ The goal is to merge (1 + e) --heav edges in parallel until none are left. The main challenge
ensuring that the algorithm does not violate the approximation requirements. An outer-round of Algorithm begins by randomly coloring active (i.e., non-isolated) vertices either red or blue (Line 3) assigning each color with probability 1/2. Then, constructs graph Ge which consists of edges of G of weight belonging to the current layer (Line Moreover, G. only contains edges whose endpoints have different colors, and whose red endpoint has larger size than the blue endpoint. Observe that each edge of G is added to G. with probability at least 1/4. The algorithm then performs inner-rounds while the number of edges G2 non-zero.
Let us now describe single inner-round (Lines 16). The goal of an inner round is for many blue vertices merge into red vertices. Here we allow multiple blue vertices to merge with a single red vertex. A key property (also exploited in (38) is that as long as the size of the cluster represented by does not grow too much within a single round, the weights of the edges incident to x are very close to what they were in the beginning of the round. Specifically, assume that (in the beginning of round) represents cluster size c. Then, until the size of this cluster exceeds (1 c) c, the edges incident to x that were (1 + e)-heavy at the beginning of the round remain (at least) (1 + -havyy This allows us to merge multiple vertices with o in a single round, at the cost of increasing the approximation ratio to (1 + +)² (which can be reduced to (1 + <) by scaling by constant factor).
More specifically, an inner round implemented as follows, For each blue vertex b E B, the algorithm selects uniformly random priority TO E [o, 1] (Line 7) which is used to perform symmetry breaking when merging vertices. It then chooses random red neighbor, C2, for each 6 B (Line 8). If a blue vertex has no red neighbors it will not participate in the subsequent steps, but for simplicity when describing the algorithm we assume that each b B has valid C.. The algorithm then builds T, a set of triples for each b E B containing the value of its candidate red neighbor C., its priority ma- and its id, (Line and sorts this set lexicographically. We call the elements of T proposals. point, red vertex may have proposals to merge from large number of blue neighbors, and so the algorithm selects for each y E R the first prefix of T, (the merges proposing to r) whose total cluster If no prefix of T, has this property, the algorithm selects all of T,..
this
size exceeds e|r| (Lines 10 11
5

---

Finally, the algorithm gathers all of the (r. b) vertex pairs that were selected (Line 12 and applies these merges to update both G and G2 [iine[3], Note that after this update we remove all edges of G. that have two red endpoints, and as result we maintain the invariant that each edge of G. has two endpoints of distinct colors, and the size of the red endpoint is at least the size of the blue one.
2.1 Theoretical Analysis
We show that our algorithm performs nearly- total work, has poly-logarithmic depth, and thus polynomial parallelism, and has good approximation guarantees. For the purpose of this analysis we assume that >> O is a constant. We provide proofs in the Appendix and outline the main ideas here.
We start by analyzing layer-contraction phase, and bound the total work and number of rounds required. We start by showing that within each inner round of Algorithm [ each blue vertex makes progress in expectation either by being merged, or by having many edges incident to it be deleted.
Lemma 2.1. Consider arbitrary blue vertex b within inner round. Within this round either (a) a constant factor of edges incident to are deleted, or (b) with constant probability is merged into one of its red neighbors.
Using this property, we can bound the number of inner rounds within an outer round to be Ollog whp. Next, we show that the number of outer rounds is also Ollog n) whp.
Lemma 2.2. The number of outer rounds in a call Algorithm 7 is Ologgn with high probability.
The proof works by showing that for each edge e of the graph Ge at the beginning of the loop, either (a) the endpoints of e are merged together, or (b) the weight of e drops below Ti, or (c) an endpoint of e increases its size by a factor of (1 +e).
Finally, assuming the aspect-ratio A = Wmax/Wmiin O (poly(n)), the number of conetccontactioon phases is (ppolylog(1) (n) Putting all of the previous results together and implementing the algorithm using standard parallel primitives in the work-depth model, we obtain the following result:
Theorem 2.3. ParHAC is (1 + a)pprxxiimt algorithm for uverage-linkage HAC that runs in Õm + n) work in expectation and has (log" (n)) depth with high probability.
2.2 Lower Bound
We complement our upper bound with a parallel hardness result for exact graph- average-linkage HAC. Since the problem is in P, we show P-hardness to show the P-completeness result. Specifically, we give an NC reduction from the P-complete monotone circuit-value problem (monotone CVP) by transforming monotone circuit into a graph-based HAC instance such that two vertices are merged into the same cluster with a given merge similarity and only if a target output gate evaluates to true. With minor modifications, our reduction extends to the show the P-completeness of variant of average-linkage called WPGMA- -PGMM--likage; we provide our constructions and proofs in the Appendix.
2.3 Algorithm Implementation
We implemented ParHAC in C++ using the CPAM (Compressed Parallel Augmented Maps) frame- work (39), which provides compressed and highly space-efficient ordered maps and sets. We build on CPAM's implementation of the Aspen framework [33 39, which provides compressed dynamic graph representation that supports efficient parallel updates (batch edge insertions and deletions).
Compressed Clustered Graph Representation. In practice ParHAC can perform large number of rounds per-layer in the case where is small (e.g., c < 0.01). Although updating the entire graph (the algorithm will only perform O(m + n) work),
on each of these rounds is sreoreticall--fffciie many of these rounds only merge small number of vertices, and leave the majority of the edges unaffected, so updating the entire graph each round can be highly wasteful.
Instead, we designed an efficient compressed clustered graph representation using the CPAM framework (39] which enables us to update the underlying similarity graph in work proportional to the number of merged vertices and their incident neighbors, rather than proportional to the total
All existing HAC approximation algorithms make similar assumptions the aspect ratio 4
38

---

number of edges in the graph. Importantly, using CPAM enables lossless compression for integer- keyed maps to store the cluster adjacency information using just a few bytes per edge' We provide more details about the representation and the supported operations in the Appendix.
Other Hierarchical Graph Clustering Algorithms. Our new clustered graph representation makes it very easy to implement other parallel graph clustering algorithms. In particular, we developed a faithful version of the Affinity clustering algorithm [8] and the recently proposed SCC algorithm (55] (which is essentially a thresholded version of Affinity) using few dozens of lines of additional code. Both algorithms are essentially heuristics that are designed to mimic the behavior of HAC, while running in very few rounds (an important constraint for the distributed environments these algorithms are designed for). We note that most of the work done by these algorithms is the work required to merge clusters in the underlying graph, so by using the same primitives for merging graphs, we eliminate a significant source of differences when comparing algorithms.
3 Empirical Evaluation
Experimental Setup. We ran all of our experiments on 72-core Dell PowerEdge R930 (with two-way typer-threading) with 4 x 2.4GHz Intel 18-core E7-8867 v4 Xeon processors (with a 4800MHz bus and 45MB L3 cache) and ITB of main memory. Our programs use lightweight work-stealing parallel scheduler 5 1 Further details about our setup and input data can be found in the Appendix.
HAC Algorithms Evaluated. We compare ParHAC with several HAC baselines. SeqHAC is the approximate sequential average-linkage algorithm that was recently introduced [38]. ParHAC and SeqHACe are exact versions of the ParHAC and SeqHAC algorithms, where the ParHAC code takes Tr, W in each layer-contraction phase and sets = 0 (i.e., the layer only consists of equal- weight edges). ParHACo.1 and SeqHACo.1 both use e = 0.1. We also evaluate our implementation of Affinity clustering [ and the recently developed SCC algorithm (55]. which we refer to as ParAffinity and ParSCCsim- Both these algorithms can be thought of as heuristic parallclizations of the HAC algorithm, which are designed with speed and good parallclization properties in mind. We describe these in more detail in the Appendix. Lastly, we also compare the graph- based implementations of HAC to pointset-based HAC implementations from the scipy package using the single-, complete-, average-, and Ward Ward-linkage measures. These are exact HAC algorithms, which look at the complete similarity matrix and thus require time which is at least quadratic in the input size.
Building Similarity Graphs from Pointsets. Some of our experiments generate graphs from a pointset by computing the approximate nearest neighbors (ANN) of each point, and converting the distances to similarities. We convert distances similarities using the formula sim (u, v) = I-dist(u.v) We then reweight the similarities by dividing each similarity by the maximum similarity. We note that tried other similarity functions, e.g., the function sim(u, v) 1+log (dist(u.))) for small values of and obtained slightly better quality results than the original formula used in this paper. However, the relative ranking of algorithms did not change for these different functions, and as tuning the distance-to eestance-to-similare to-similarity conversion seemed outside of the scope of this paper, we use the simple original formula described above in the rest of the paper. We compute the k-approximate nearest neighbors parallel implementation of the Vamana approximate nearest neighbors (ANN) algorithm (45) with parameters R = 75, L 100, max(L. k). We discuss more details about the process in the Appendix.
using a
3.1 Quality Evaluation
We start by investigating the quality of ParHAC with respect to ground-truth clusterings. Our goal is to understand (1) whether ParHAC preserves the clustering quality of exact average-linkag HAC (using a complete similarity matrix), and (2) what value of to use in practice. The results in this sub-section affirmatively answer (1), and show that a value of < = 0.1 achieves comparable quality to exact average- lingge-linkage HAC, which prior works have identified as a -fate-of-the-art hierarchical
clustering method and use as their primary quality baseline g 38 (55)
We obtain 2.9x space savings using our CPAM based implementation over an optimized hashtable-based inplementation of clustered graph; the running times of both implementations essentially the same.
7

---

Romming time seconds (logscale)
PritAC-
10p
FailliC
30F
0.6
AR8
301
300
Pa
10
PaHlsous
SCC
10-2
N-NN graph
Number of points (logscale
Figure ARI score on the digits point dataset as a function the k used in graph building. ParHAC using e = 0.1 is the green line using markers. The gray vertical line highlights the values for & = 10, in detailed quality
Figure 2: End-to-end running times of fastcluster's unweighted average-linkage. SeqHAC using e 0.1, and ParHAC using = 0.1 and 144 hyper- on varying-size slices of the glove- 100 dataset. The time for SeqHAC and ParHAC includes the cost of solv- ing ANN and generating terminated methods that run for more than 3 hours.
which is the value of l evaluation in the Appendix. The red horizontal line is the ARI of SciPy's everage-linkage
input similarity graph; shows only the clustering time. We
We evaluate algorithms on the iris, wine, digits, and cancer, and faces classification datasets from the UCI dataset repository (found in the sklearn.datasets package). We run all of the graph-based clustering algorithms similarity graphs generated from the input pointsets using A: 10 in the approximate k-NN construction. We run the scipy pointset clustering algorithms directly on the input pointsets. To measure quality, use the Adjusted Rand-Index (ARI) and Normalized Mutual Information (NMI) scores, as well as the Dendrogram Purity measure of a hierarchical clustering 43] which we define in the Appendix. We also study the unsupervised Dasgupta Cost 27 measure. We give definitions the measures in the Appendix.
Results. We present a table of our results in the Appendix and summarize our findings here. Our main finding is that ParHACo.1 achieves consistently high-quality results across all of the quality measures. For instance, for the ARI measure, ParHACo.1 is on average within 1.5% of the best ARI score for each graph (and achieves the best score for one of the graphs). For the NMI measure, ParHACo.1 is on average within 1.3% of the best NMI score for each graph (and again achieves the best score for two of the graphs). ParHACo.1 also achieves good results for the dendrogram purity and Dasgupta cost measures. For purity, it is on average within 1.9% of the best purity score for each graph, achieving the best score for one of the graphs, and for the unsupervised Dasgupta cost measure it is average within 1.03% of the smallest Dasgupta cost score for each graph.
Compared with the SeiPy average- linkage which is an exact HAC algorithm running on the underlying pointset, ParHACo.1 achieves 14.4% better ARI score on average, 3.6% better NMI score on average, 4.7% better dendrogram purity on average, and 1.02% larger Dasgupta cost on average. Compared to the best quality result obtained by either SCCsim or Affinity, ParHACo.1 consistently obtains better quality results, achieving 35.6% better ARI score on average, 12. better NMI score on average, 6.7% better dendrogram purity average, and 3. 1% better Dasgupta cost on average.
Overall, we find that ParHAC achieves consistently high quality results across the four quality measures that we evaluate. Our results show that being more faithful to the HAC algorithm allows ParHAC obtain meaningful quality gains over Affinity and SCCsim.
Results with Varying k: When converting a pointset input to the similarity setting using the k-NN approach as in this paper, what value of l is required to achieve high quality? We studied each of the quality measures for the studied algorithms as a function the & used in the k-NN construction, and present our full results for each measure and each dataset in the Appendix. Here, Figure shows representative result for the ARI measure on the digits point dataset.
We find that even modest values of ls yield very high quality results and can significantly outperform exact metric HAC algorithms on the original pointset. Furthermore, even tripling, or increasing an order of magnitude either yields negligible improvement for most quality measures, or in fact degrades the quality. For example, for ParHAC with e = 0. using & = 100 is 10% worse than using k k= 10, and using A 1000 is 47% worse than A 10. Our results suggest a twofold benefit from using a graph-based approach: (1) since small values of i are sufficient for high quality results, the inputs to the clustering algorithm can be smaller, resulting in faster running times, and (2) the overall
8

---

Values on top of bors are running times seconds)
ParHAC SeqHICC
ParRAC
104
FarAfinity
4.
SegtiAC
ParSCCaio
Rolatve performace
109
22
10P
61.8
803
10
5:4
2.37
10F1
OK TW
Figure 3: Relative performance of our ParHAC algorithm compared to other graph-HAC and HAC-inspired algorithms. We prefix new implementations developed in this paper with the Par prefix. The values top of each bar show the rumning time of each algorithm in seconds. The times shown for the parallel algorithms 144 hyper-thread times. run ParHAC and SeqHAC algorithm using = 0.1. terminated algorithms that ran longer than 6 hours and mark them with a red x.
clustering quality is higher with small inputs and can lead to significant improvements over using more similarities (or using the full dissimilarity matrix, in pointset clustering algorithms).
3.2 Evaluation on Large Real-Worll Graphs
Next, we evaluated ParHAC's scalability large real-world graphs, including both social network graphs, as well as sparse, high-diameter networks. We note that the Hyperlink (HL) graph is one of the largest publicyy-avilable graphs and contains 1.7B vertices and 125B edges. Additional details and experiments can be found in the supplementary material; we summarize them:
(1) ParHAC achieves betewen 25.7-61.3x 6.3xx speedup over its running time on single thread. (2) We evaluated the running time of ParHAC when the edge weights in the graph are selected based structural properties of the input, c.g., the degree, or the number of triangles closed by the edge. Overall, we evaluated 6 highly-differee between the fastest and slowest schemes per-graph is at most 5x.
weighting schemes, and find that the gap
(3) Running ParHAC with larger values of consistently results in lower running times, due to the fewer number of rounds used for large
F shows the relative performance and of ParHAC compared with the SeqHAC and SeqHACe algorithms, and our implementations of the RAC, Affinity, and SCCsim algorithms. We see that our Affinity implementation always the fastest on our graph inputs. This is due to the low theoretical and empirical round- complexity of Affinity. Compared with Affinity, SCCsim. which runs Affinity with weight thresholding using 100 iterations is an average of 11.5x slower than Affinity due to the cost of the additional iterations. Compared to Affinity and SCCsim- ParHAC is average of 14.8x slower than our Affinity implementation and 1. 1.24x slower than our SCCaim implementation. The speed difference between ParHAC and Affinity is due to the larger number of fine- fineggrained rounds required by ParHAC. However, as we showed in Section 3.1 the faster running time of affinity clustering and SCC,im comes at the cost of significantly lower quality.
Compared with methods that implement exact or + e-pproximmate HAC, ParHAC significantly faster. Compared with SeqHAC and SeqHAC,, ParHAC obtains 50. and 86.4x speedup on average respectively. Compared with RAC, ParHAC achieves an average speedup of 7.1x on the graphs that RAC can successfully complete within the time limit. Although RAC is faster than ParHAC on two of our small graph inputs, it requires a very large number of rounds on the remaining graphs.
To the best of our knowledge, our results are the first to show that graphs with tens to hundreds of billions of edges can be clustered in matter of tens of minutes (using heuristics like Affinity and SCCsim with fewer iterations) to hours (using SCC,im with many iterations, or methods with approximation guarantees such as ParHAC). Recently, results on trillion-edge similarity graphs have been reported 55 73 Due to the memory requirements of storing such large datasets in memory, ParHAC may not be directly applicable; however, may be possible to design distributed (1 (L+ approximmtee HAC algorithm with low round-complexity by building the ideas in this paper.

---

Discussion. To the best of our knowledge, our results are the first to show that graphs with tens to hundreds of billions of edges can be clustered in matter of tens of minutes (using heuristic methods like Affinity and SCCsim with fewer iterations) to hours (using SCCsim with many iterations or methods with approximation guarantees such as ParHAC). We are not aware of other shared- memory clustering results that work at this large scale. Our theoretically-effcien implementations can be viewed as part of a recent line work showing that theoretically-efiie -ffficief shared- shared-memory parallel graph algorithms can scale to the largest publicly available graphs using modest amount of resources 3 36
66 677.
3.3 Pointset Clustering: End-to-End Evaluation
We conclude by evaluating the performance of ParHAC in the case when the input is a pointset. In this setting, in order graph before running the clustering algorithm. As baseline, we use the average-linkage HAC implementation from fastcluster [59], which takes a pointset input. We compare with fastcluster as we found it yields more consistent (and slightly faster) performance for larger numbers of points than the implementations in sklearn and SciPy We also compare ParHAC the SeqHAC algorithm in this setting, where SeqHAC uses the same similarity-grann building method as ParHAC described earlier in this section, and both algorithms are run using e 0.1.
graph-based HAC algorithm, one needs to construct similarity
We run our end-to-end experiment on the Glove-100 100 dataset, which is a 100-dimensional dataset containing vector-embeddiins for 1.18 million words. Figure shows the results of our experiment. We stress that the running times of the graph-based algorithms (SeqHAC and ParHAC) include the time spent building the graph. First, we found that for 3000, the end-to-end times of ParHAC are always faster than the time taken by fastcluster, and for n > 9400, the end-to-end times of SeqHAC are always faster than the time taken by fastcluster. Comparing fasteluster on the largest slice of the Glove- 100 dataset it can solve in under three hours with the graph-based methods, SeqHAC is 20x faster, and ParHAC is 417x faster.
4 Conclusion
In this paper we have introduced ParHAC, the first parallel algorithm for hierarchical agglomerative graph clustering using the average-linkage measure that has strong theoretical-bounn and depth, as well as provable approximation guarantees. We have shown that ParHAC scales to massive real-world graphs with tens hundreds of billions of edges on single machine and achieves high-quality results compared to existing graph-based and pointser-based hierarchical clustering methods.
its work
An interesting question for future work is whether we can reduce the round complexity of our algorithm to make it more suitable for distributed settings. One promising idea is to analyze version of ParHAC in which we process edges from all weight buckets simultaneously. while ensuring that all merges satisfy the approximation guarantees. Another interesting question is to compare the running time and quality of bottom-up HAC methods for size-constrained clustering and balanced partitioning problems, which typically rely on top-down methods [9] 30 47]. Although it has recently been shown that it may not be possible to design algorithms for incremental and dynamic HAC with good worst-case guarantees (77), it would be interesting to design practical (1 ipppproxisstioons for these settings, potentially building on ideas from ParHAC.
References
[I] Chem dataset.
[2] Geolife dataset.
httpp///www.niccoooo..oc///////s pub irollcatiin www.iiaainnnogneeeeeeee
Ucil dataset.
te escopes
'We performed a similar comparison with the recently proposed ParChain framework for exact euclidean
HAC [79]: here, ParHAC obtained an average of 39.3x speedup (end-to-end) in parallel over ParChain.
10

---

[4] Amir Abboud, Vincent Addan, and Hussein Houdrouge. Subquadratic high-dimensional hierarchical clustering. Advances in Neural Information Processing Systems, pages 1 11580- 1 11590, 2019.
[5] Nimar S Arora, Robert D Blumofe, and C Greg Plaxton. Thread scheduling for multipro- grammed multiprocessors. Theory of Computing Systems (TOCS), 34(2):115-144 2001.
[6] Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. Ann-benchmarks: A benchmark- ing tool for approximate nearest neighbor algorithms. In International Conference on Similarity Search and Applications, pages 34-49. Springer, 2017.
[7] Kevin Aydin, MohammadHoossein Bateni, and Vahab Mirrokni. Distributed balanced partitioning via linear embedding. Algorithms, 12(8).
[8] MosemmadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Haji- aghayi, Raimondas Kiveris, Silvio Lattanzi, and Vahab Mirrokni. Affinity clustering: Hierarchi- cal clustering at scale. In Advances in Neural Information Processing Systems (NeurIPS), pages 2017.
[9] Jean-Paul Benzécri. Construction d'une classification ascendante hiérarchique par la recherche en chaîne des voisins réciproques. Cahiers de I' ''anallse des données, 7(2):209-211 1982.
[10] Bonnic Berger, John Rompel, and Peter W. Shor. Efficient NC algorithms for set cover with applications to learning and geometry. J. Computer and System Sciences, 49(3):454-477, 1994.
[11] Guy E. Blelloch and Bruce M. Maggs. Algorithms and theory of computation handbook. chapter Parallel Algorithms. Chapman Hall/CRC, 2010. ISBN 978- 118-1-55448-821
[12] Guy E. Blelloch, Richard Peng, and Kanat Tangwongsan. Linear- work greedy parallel approxi- mate set cover and variants. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 23-32, 2011.
[13] Guy E. Blelloch, Daniel Anderson, and Laxman Dhulipala. Parlaylib toolkit for parallel algorithms on shared-memory multicore machines. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 507 509, 2020.
[14] Guy E Blelloch, Jeremy T Fineman, Yan Gu, and Yihan Sun. Optimal parallel algorithms in the binary-forking model. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 89-102, 2020.
[15] Guy E. Blelloch, Laxman Dhulipala, and Yihan Sun. Introduction parallel algorithms. http:// www. cS cmu wwddd//uuyb/peeee httpll/gggpggaaaaaaaaaaaaapppppa
pdf 2021.
[16] RK Bock, Chilingarian, M Gaug, F Hakl, Th Hengstebeck, M Jitina, J Klaschka, E Kotrě, Savicky, S Towers, al. Methods for multidimensional event classification: case study using images from cherenkov gamma-ray telescope. Nuclear Instruments and Methods in Physics Revearch Section A: Accelerators, Spectrometers, Delectors and Associated Equipment, 5 516(2-3):511-522 2004.
[17] Paolo Boldi and Sebastiano Vigna. The WebGraph framework I: Compression techniques. In International World Wide Web Conference (WWW), pages 595-601, 2004.
[18] Otakar Borůvka. O jistém problému minimálním. Práce Mor. Přírodovéd. Spol. Brně III, 3: 37-58, 1926.
[19] Aydın Buluç, Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. Recent advances in graph partitioning. Algorithm engineering, pages 117-158, 2016.
[20] Moses Charikar and Vaggos Chatziafratis. Approximate hierarchical clustering via sparsest cut and spreading metrics. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 841-854, 2017.
[21] Moses Charikar, Vaggos Chatziafratis, and Rad Niazadeh. Hierarchical clustering better than average-linkage. In ACM-SIAN Symposium on Discrete Algorithms (SODA), pages 2291-2304, 2019.
11

---

[22] Evangelos Chatziafratis. Hierarchical clustering with global objectives: Approximation algo- rithms and hardness results. Stanford University, 2020.
[23] Michael Cochez and Hao Mou. Twister tries: Approximate hierarchical agglomerative clustering for average distance in linear time. In ACM SIGMOD International Conference on Management of Data, pages 505-517, 2015.
[24] Vincent Johen-Addad, Varun Kanade, and Frederik Gallmann-TTeeme Hierarchical clustering beyond the worst-case. In Advances in Neural Information Processing Systems, volume 30, pages 6201-6209. Curran Associates, Inc., 2017.
[25] Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Tremi and Claire Mathieu, Hierar- chical clustering: Objective functions and algorithms. J. ACM, 66(4), 2019.
[26] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3. ed.). MIT Press, 2009.
[27] Sanjoy Dasgupta. A cost function for similarity- based hierarchical clustering. In ACM Sympo- sium on Theory of Computing (STOC), pages 118-127, 2016.
[28] Manoranjan Dash, Simona Petrutiu, and Peter Scheuermann. pPOP: Fast yet accurate parallel hierarchical clustering using partitioning. Data Knowl. Eng., 633:55633, 2007.
[29]
Camil Demetrescu, Andrew Goldberg, and David Johnson. 9th dimacs implementation chal- lenge: Shortest paths. http://www.dir
unwromal www.wwwaa....ii.maaa........
.tt/challenge// wwt..uooa..../ccalleeeeeeeeeeee 2019.
[30] Laxman Dhulipala, Igor Kabiljo, Brian Karrer, Giuseppe Ottaviano, Sergey Pupyrev, and Alon Shalita. Compressing graphs and indexes with recursive graph bisection. In ACM International Conference on Knowledge Discovery and Data Mining (KDD), pages 1535-1544, 2016.
[31] Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. Julienne: A framework for parallel graph algorithms using work-efficient bucketing. In ACM Symposium on Parallelism in Algorithums and Architectures (SPAA), pages 293-304, 2017.
[32] Laxman Dhulipala, Guy F. Blelloch, and Julian Shun. Theoretically efficient parallel graph algorithms can be fast and scalable. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 293-304, 2018.
[33] Laxman Dhulipala, Guy E Blelloch, and Julian Shun. Low-latency graph streaming using compressed furely-funetional trees. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 918-934, 2019.
[34] Laxman Dhulipala, Changwan Hong, and Julian Shun. ConnectIt: A framework for static and incremental parallel graph connectivity algorithms. Proc. VLDB Endow. 14(4))653-667, 2020.
[35] Laxman Dhulipala, Quanquan C Liu, and Julian Shun. Parallel batch-dynamic k-clique counting. arXiv preprint arXiv:2003. 13585, 2020.
[36] Laxman Dhulipala, Charlie McGuffey, Hongbo Kang, Yan Gu, Guy E Blelloch, Phillip B Gibbons, and Julian Shun. Sage: Parallel semi-asymmetric graph algorithms for NVRAMs. 2020.
Proc. VLDB Endow.,
[37] Laxman Dhulipala, Jessica Shi, Tom Tseng, Guy E. Blelloch, and Julian Shun. The graph based henchmark suite (GBBS). In International Workshop on Graph Data Management Experiences and Systems (GRADES) and Network Data Analytics (NDA), pages 11:1-11:8, 2020.
[38] Laxman Dhulipala, David Eisenstat, Jakub Lącki, Vahab Mirrokni, and Jessica Shi. Hierarchical agglomerative graph clustering in -ineer time. In International Conference Machine Learning (ICML). pages 2676-2686, 2021.
[39] Laxman Dhulipala, Guy E Blelloch, Yan Gu, and Yihan Sun. PaC-trees: Supporting parallel and compressed
collections. ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2022.
12

---

[40] Jordi Fonollosa, Sadique Sheik, Ramón Huerta, and Santiago Marco. Reservoir computing compensates slow response of chemosensor arrays exposed to fast varying gas concentrations continuous monitoring, Sensors and Actuators B: Chemical, 215:618-628 629, 2015.
[41] P. Franti, O. Virmajoki, and V. Hautamaki. Fast agglomerative clustering using k-nearest neighbor graph. JEEE Transactions on Pattern Analysis and Machine Intelligence, 28(11):
1875-1881, 2006.
[42] Sudipto Guha, Rajeev Rastogi, and Kyuseok Shim. Rock: A robust clustering algorithm for categorical attributes. In Proceedings of the International Conference on Data Engineering, pages 512-521, USA, 1999.
[43] Katherine A. Heller and Zoubin Ghahramani. Bayesian hierarchical clustering. In International Conference on Muchine Learning (ICML), pages 297-304, 2005.
[44] Changwan Hong, Laxman Dhulipala, and Julian Shun. Exploring the design space of static and incremental graph connectivity algorithms on gpus. In International Conference on Parallel Architectures and Compilation Techniques (PACT), pages 55 69, 2020.
[45] Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. DiskANN: Fast accurate billion-point nearest neighbor search on a single node. Advances in Neural Information Processing Systems, 32, 2019.
[46] Yongkweon Jeon and Sungroh Yoon. Multi-threaded hierarchical clustering by parallel nearest- neighbor chaining. IEEE Trans. Parallel Distributed Syst., (6(9):2534-2555) 2015.
[47] Igor Kabiljo, Brian Karrer, Mayank Pundir, Sergey Pupyrev, and Alon Shalita. Social hash par- titioner: A scalable distributed hypergraph partitioner. Proc. VLDB Endow. 10(11):1418-142, 2017.
[48] George Karypis, Eui-Hong (Sam) Han, and Vipin Kumar. Chameleon: Hierarchical clustering using dynamic modeling. Computer. 32(8):68-75, August 1999.
[49] Benjamin King. Step-wise clustering procedures. Journal of the American Statistical Associa- fion, 69:86-100 101, 1967.
[50] Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. What twitter, a social network or news media? In International World Wide Web Conference (WWW), pages 591-600, 2010.
[51] G. N. Lance and W. T. Williams. A general theory of classificatory sorting strategies 1. Hierarchical systems. Computer Journal, (4):373-- February 1967.
[52] Jure Leskovec and Andrej Krevi. SNAP Datasets: Stanford large network dataset collection, 2014.
[53] Christopher D) Manning, Prabhakar Raghavan, and Hinrich Schütze. Introduction to Information Retrieval. Cambridge University Press, 2008
[54] Robert Meusel, Sebastiano Vigna, Oliver Lehmberg, and Christian Bizer. The graph structure in the web-analyzed on different aggregation levels. The Journal of Web Science, 1(1):33-47, 2015.
[55] Nicholas Monath, Avinava Dubey, Guru Guruganesh, Manzil Zaheer, Amr Ahmed, Andrew McCallum, Gokhan Mergen, Marc Najork, Mert Terzihan, Bryon Tjanaka, et al. Scalable agglomerative clustering. In ACM International Conference on Knowledge Discovery and Data Mining (KDD), pages 1245-1255, 2021.
[56] Benjamin Moseley and Joshua R. Wang. Approximation bounds for hierarchical clustering: Average linkage, bisecting k-means, and local search. In Advances in Neural Information Processing Systems, pages 3094-3103, 2017.
[57] Benjamin Moseley, Kefu Lu, Silvio Lattanzi, and Thomas Lavastida. framework for paral- lelizing hierarchical clustering methods. In ECML PKDD 2019, 2019.
13

---

[58] Fionn Murtagh and Pedro Contreras. Algorithms for hierarchical clustering: an overview. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2(1):86-97, 2012.
[59] Daniel Müllner. fastcluster: Fast hierarchical, agglomerative clustering routines for r and python. Journal of Statistical Software, Articles, 53(9);1-18, 2013.
[60] Clark F. Olson. Parallel algorithms for hierarchical clustering. Parallel Comput., 21(3))1313- 1325, 1995.
[61] C. A. Phillips. Parallel graph contraction. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 148-157, 1989.
[62] Sanguthevar Rajasekaran. Efficient parallel hierarchical clustering algorithms. IEEE Transac- tions on Parallel and Distributed Systems, 16(6):497-502, 2005.
[63] J. Reif. Optimal parallel algorithms for integer sorting and graph connectivity. Technical Report TR-08-85, Harvard University, 1985.
[64] Aurko Roy and Sebastian Pokutta. Hierarchical clustering via spreading metrics. In Advances in Neural Information Processing Systems (NIPS), volume 29, pages 2316-2324. Curran Associates, Inc., 2016.
[65] Jianyin Shao, Stephen W. Tanner, Nephi Thompson, and Thomas E. Cheatham. Clustering molecular dynamics trajectories: 1. Characterizing the performance of different clustering algorithms. Journal of Chemical Theory and Computation, 36)):3312-2334, 2007.
[66] Jessica Shi, Laxman Dhulipala, David Eisenstat, Jakub Läcki, and Vahab Mirrokni. Scalable community detection via parallel correlation clustering. Proc. VLDB Endow. 14(11):2305-2313, 2021.
[67] Jessica Shi, Laxman Dhulipala, and Julian Shun. Parallel clique counting and peeling algorithms. In SIAM Conference on Applied and Computational Discrete Algorithms (ACDA2I), pages 135-146. SIAM, 2021.
[68] Julian Shun and Guy E Blelloch. Phase-concurrent hash tables for determinism. In ACM Symposium Parallelism in Algorithms and Architectures (SPAA), pages 96-107, 2014.
[69] Julian Shun, Laxman Dhulipala, and Guy Blelloch. A simple and practical linear-work parallel algorithm for connectivity. In ACM Symposium Parallelism in Algorithms and Architectures (SPAA), pages 143-153, 2014.
[70] Julian Shun, Laxman Dhulipala, and Guy E. Blelloch. Smaller and faster: Parallel processing of compressed graphs with Ligrat. In Data Compression Conference (DCC), pages 403-412, 2015.
[71] Julian Shun, Farbod Roosta-Khorasani, Kimon Fountoulakis, and Michael W. Mahoney. Parallel local graph clustering. Proc. VLDB Endow., 9(2):1041-1052, 2016.
[72] Peter H.A. Sneath and Robert R. Sokal. Numerical Taxonomy: The Principles and Practice of Numerical Classification. W.H. Freeman, San Francisco, 1973. ISBN 0 7167 0697 0.
[73] Baris Sumengen, Anand Rajagopalan, Gui Citovsky, David Simcha, Olivier Bachem, Pradipta Mitra, Sam Blasiak. Mason Liang, and Sanjiv Kumar. Scaling hierarchical agglomerative clustering to billion-sized datasets. CoRR, abs/2105. 1663, 2021.
[74] Yihan Sun, Daniel Ferizovic, and Guy E Blelloch. Pam: Parallel augmented maps. In ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), pages 290-304, 2018.
[75] Yihan Sun, Guy E Blelloch, Wan Shen Lim, and Andrew Pavlo. On supporting efficient snapshot isolation for hybrid workloads with multi-versioned indexes. Proc. VLDB Endow,, 13 (2):211-225, 2019.
14

---

[76] The SciPy community, scipy.lluseehhierrccyyyllkg. http:///.ww..kkk....tto.oo//ooo/ http:///wwp..eeeeeeeeee////e////
html
[Online; accessed 1-May-2022J.
[77] Tom Tseng, Laxman Dhulipala, and Julian Shun. Parallel batch-dynamic minimum span- ning forest and the efficiency of dynamic agglomerative graph clustering. arXiv preprini arXiv:2205.0499 2022.
[78] Joe H. Ward. Hierarchical grouping to optimize objective function. Journal of the American Statistical Association, 58(301):233-12 1963. ISSN 01621459.
[79] Shangdi Yu, Yiqiu Wang. Yan Gu, Laxman Dhulipala, and Julian Shun. Parchain: A framework for parallel hierarchical agglomerative clustering using nearest-neighbor chain. Proc. VLDB Endow, 15(2):285-25) 298, 2021.
[80] Yu Zheng, Like Liu, Longhao Wang, and Xing Xie. Learning transportation mode from raw GPS data for geographic applications the web. In International Conference on World Wide Web, pages 247-256, 2008.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We carefully delineate that we are focusing on the graph-based setting for hierarchical clustering. and that our main contributions are new theoretical and experimental results in this setting.
(b) Did you describe the limitations of your work? [Yes] We point out that ParHAC may not be suitable for inputs containing trillions of vertices and edges, which are currently challenging to fit in-memory on an average commodity multicore machine. We also note that further reducing the number of rounds of our approach would be necessary to run in distributed setting.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This primarily a theoretical work; the caveats about carefully evaluating clustering quality that are true for any unsupervised clustering or learning method also apply to our work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We have read them and ensured paper conforms to the guidelines.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We clearly state that our results are for the graph-based versions of the problems that study, It would be interesting to generalize our approximation and hardness results to the (lw-dimensional) metric setting; this is an intriguing direction for future work.
(b) Did you include complete proofs of theoretical results? [Yes] Due space constraints, we present the high-level ideas of the proofs in the main paper, but all proofs are given in the Appendix (supplementary materials).
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Ye]] We have included our code as anonymized repository here: Wwwpenne///aaaatCCCAAEAE...
(also mentioned in the intro- duction). The repository contains all source files used in experiments, including sources for ParChain, and scripts to run the expeirments.
httpss//anonmmou..oppeee hww.aoonnnnos..oe....ieee///aaaa
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We discuss the values of e used, and for evaluation on pointsets, the values of A used in our similarity graph construction.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] We report results on the average error (both for quality and running time) in the Appendix.
15

---

(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] We have specified the exact machine used, and its characteristies in the main body of the paper.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] We mention and cite the sources of all datasets and code that we use in the Appendix.
(b) Did you mention the license of the assets? [Yes] We also discuss the licenses of the datasets and code that we use in the Appendix.
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] We have included our code as an anonymized repository here: huts://anonymous..om 4open. wtw.e....eeceeeeeeeeeee. www.eeeee//aaaHaAAAAAAAAAA
(also mentioned in the introduc- tion). We also include several low-dimensional pointsets in the supplemental material that used in the ParChain paper. The ParChain method is mostly suitable for low-dimensional data, and could not run on the other high-dimensional inputs we use in the main body of our paper. For fair comparison, ParChain, and we document the sources, availability, and licenses of these additional datasets.
the same datasets as
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] The datasets and sources we build on are made publicly- available (e.g.. on the UCI-dataset repository, or on the A.N--benhhnars repository) with the intent to be used as benchmarks in academic works.
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A] The datasets we are using do not contain PII or offensive content.
5. If you used crowdsourcing or conducted research with human subjects... [N/A] (we do not use crowdsourcing or research with human subjects this paper)
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
16


Reviews:
[{"review_id": "SMwgQfDcs1u", "reviewer": "Reviewer_w4sm", "summary": "This paper develops a parallel hierarchical agglomerative clustering (HAC) algorithm ParHAC which achieves $(1+\\epsilon)$-approximation with $\\tilde{O}(m)$ work and poly-log depth. It also shows that the graph-based HAC using average-linkage is P-complete. The experiments on real datasets verifies the accuracy and scalability of ParHAC.", "questions": "(1) What is the relationship of this work with [23]?\n\n(2) The authors explain the \"work\" as the number of operations performed in Sec 1.1. What kinds of operations does it count? Are they MultiMerge and Neighborhood Primitives? Why do the authors use work rather than running time in Th 1.1? What is the running time of the algorithm?", "limitations": "I cannot find any issue with negative societal impact. The main concerns have been listed in questions.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The speedup and scalability of ParHAC are significant, and the P-completeness result is new. The key idea of layering, which is a common proof skill in approximation algorithms, is novel for the proof of $(1+\\epsilon)$-approximation, but it seems to be enlightened by [23]. The result of $(1+\\epsilon)$-approximation and its proof seem similar to those in [23] also, except for the poly-log depth. It is better for the authors to make a thorough comparison with [23] and clarify the difference.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LVvRLUdt7r", "reviewer": "Reviewer_zNhm", "summary": "This paper presents an efficient parallel hierarchical agglomerative clustering (HAC) algorithm with sublinear depth for the average linkage function. In particular, the authors provide a (1+$\\epsilon$)-approximation algorithm on $m$ edge graphs using $\\tilde{O}(m)$ time and poly-logarithmic depth. Experiments show that the proposed ParHAC algorithm enjoys huge speedup compared with state-of-the-art sequential and parallel baselines while achieving similar quality.\n\n** Post Rebuttal Update **\nI've read the rebuttal and the other reviewers' comments. I appreciate the update the authors have made, and I have no further questions given the inputs.", "questions": "Q1. For the pointset experiment, one might want to discuss the methods of generating the pairwise similarity.\n\nQ2. Since the experiments include a variety of datasets, the authors might want to summarize and compare the datasets.", "limitations": "No conclusion. No discussion on potential societal impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "** Strengths **\n\nS1. The theoretical analysis provides a good understanding of the algorithm design's general idea (Thm 1.1, 1.2), the hardness (lower bound), and the performance (Thm 2.3).\n\nS2. Experiments show substantial speedup over the baselines.\n\n** Weaknesses **\n\nW1. The presentation of algorithm design is unclear.\n\nW2. The presentation of experiments is unclear. The authors might want to put more tables in the main text.\n\nW3. The presentation seems to focus on speed and discuss less on quality. Usually one might expect a trade-off between speed and quality. Thus, discussing both should be of interest.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9vIsUGtzsft", "reviewer": "Reviewer_vzbQ", "summary": "This paper focuses on a parallel approximation algorithm for hierarchical agglomerative clustering (HAC) with average—linkage function. Given $n$ data points, it constructs a similarity graph by considering each point as a vertex and connecting it to its $k$ nearest neighbors. The algorithm then separates the graph into logarithmic geometric layers such that each layer only contains edges of the same weight (up to 1+eps factor). Within each layer, all edges with weight within 1+eps factor of the maximum weight called heavy edges are merged to a larger cluster in parallel. Here a smart randomized algorithm is designed to merge all heavy edges. It can be proved that the algorithm runs in $\\tilde{O}(m+n)$ work, and more importantly, in polylogarithmic depth with high probability. Finally, extensive experiments have been performed in graphs of different scales, to answer questions including: what is the clustering quality of the approximate algorithm compared to the exact HAC, HAC with complete similarity matrix, and existing works; how to tune the approximate parameter eps and similarity graph parameter $k$ for high quality results in practice; what is the run-time performance compared with the baselines mentioned above. Overall, the proposed algorithm empirically achieves a good balance between clustering quality and running time, and can scale to graphs of hundreds of billions edges.", "questions": "See Weaknesses items 2 and 3.", "limitations": "No", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Develops a simple yet efficient parallel algorithm for approximating HAC with average-linkage function. The poly-logarithmic depth is proposed for the first time, although it is based on a standard geometric layering for converting weighted graphs to unweighted graphs (within 1+eps factor).\n2. Conduct comprehensive experimental evaluation and compare against recent baselines, exact counterpart, HAC based on complete similarity matrix, and end-to-end pointset-based clustering. Compared with the exact counterparts, this approximate algorithm achieves a clustering quality close to that of the exact algorithm across different metrics. The parallel algorithm provides an order of magnitude speedup over the sequential algorithm it is based on. \n3. The presentation of this work is good. The main text well summarizes the high-level ideas of their algorithm, with sufficient details included in the Appendix. Similarly, the experimental parts demonstrate the benefits of their algorithm, analyze the efficiency aspect, and refer to complete results in the Appendix.\n\nWeaknesses:\n1. The computational cost in terms of running time required by the current algorithm is an order of magnitude worse than Affinity, ~1.2 times worse than SCC on average. As in Figure 1, the clustering quality of SCC are comparable to ParHAC for a small value of $k$, which is the best parameter range one will choose.\n2. It is kind of counter-intuitive to see that a larger value of $k$ in building similarity graphs results in worse clustering quality. But, when the complete similarity graphs are used as in SciPy package (k=n), the performance is not too bad. It is unknown why this phenomenon is observed across the implementations of multiple algorithms. \n3. Existing works that can scale to trillion-edge graphs have been reported such as SCC. ParHAC cannot achieve that scale because of memory constraints. Does this mean that ParHAC is an in-memory algorithm? Then what is the challenge when adapting it to an on-disk algorithm that poses less requirements on the memory?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept