Sublinear Algorithms for Hierarchical Clustering
Authors: Arpit Agarwal
Sanjeev Khanna
Huan Li
Prathamesh Patil
Venue: NeurIPS 2022 Accept (2022)
Keywords: hierarchical clustering
clustering
sublinear algorithms
graph algorithms

Abstract: Hierarchical clustering over graphs is a fundamental task in data mining and machine learning with applications in many domains including phylogenetics, social network analysis, and information retrieval. Specifically, we consider the recently popularized objective function for hierarchical clustering due to Dasgupta~\cite{Dasgupta16}, namely, minimum cost hierarchical partitioning. Previous algorithms for (approximately) minimizing this objective function require linear time/space complexity. In many applications the underlying graph can be massive in size making it computationally challenging to process the graph even using a linear time/space algorithm. As a result, there is a strong interest in designing algorithms that can perform global computation using only sublinear resources (space, time, and communication). The focus of this work is to study hierarchical clustering for massive graphs under three well-studied models of sublinear computation which focus on space, time, and communication, respectively, as the primary resources to optimize: (1) (dynamic) streaming model where edges are presented as a stream, (2) query model where the graph is queried using neighbor and degree queries, (3) massively parallel computation (MPC) model where the edges of the graph are partitioned over several machines connected via a communication channel.

We design sublinear algorithms for hierarchical clustering in all three models above. At the heart of our algorithmic results is a view of the objective in terms of cuts in the graph, which allows us to use a relaxed notion of cut sparsifiers to do hierarchical clustering while introducing only a small distortion in the objective function. Our main algorithmic contributions are then to show how cut sparsifiers of the desired form can be efficiently constructed in the query model and the MPC model. We complement our algorithmic results by establishing nearly matching lower bounds that rule out the possibility of designing algorithms with better performance guarantees in each of these models.

Sublinear Algorithms for Hierarchical Clustering
Arpit Agarwal
Sanjeev Khanna
Huan Li
Prathamesh Patil?
Data Science Institute, Columbia University 2 DDepartment of Computer and Information Science, University of Pennsylvania {arpit (ggaraal@ccolunn edu
{sanjeev, huanli, pprath upenn.edu
Abstract
Hierarchical clustering over graphs is a fundamental task in data mining and ma- chine learning with applications in many domains including phylogenetics, social network analysis, and information retrieval. Specifically, we consider the recently popularized objective function for hierarchical clustering due Dasgupta [20], namely, minimum cost hierarchical partitioning. Previous algorithms for (approxi- mately) minimizing this objective function require linear time/space complexity. In many applications the underlying graph can be massive in size making it computa- tionally challenging process the graph even using a linear time/space algorithm. As result, there is strong interest in designing algorithms that can perform global computation using only sublinear resources (space, time, and communication), The focus of this work is to study hierarchical clustering for massive graphs under three well-studies models of sublinear computation which focus on space, time, and communication, respectively, as the primary resources to optimize: (1) (dynamic) streaming model where edges are presented as a stream, (2) query model where the graph is queried using neighbor and degree queries, (3) massively parallel com- putation (MPC) model where the edges of the graph are partitioned over several machines connected via communication channel.
We design sublinear algorithms for hierarchical clustering all three models above. At the heart of our algorithmic results is a view of the objective in terms of cuts in the graph, which allows us to use a relaxed notion of cut sparsifiers to do hierarchical clustering while introducing only small distortion in the objective function. Our main algorithmic contributions are then to show how cut sparsifiers of the desired form be efficiently constructed in the query model and the MPC model. We believe this relaxed notion cut sparsifiers may be of broader interest. We complement our algorithmic results by establishing nearly matching lower bounds that rule out the possibility of designing algorithms with better performance guarantees in each of these models.
1 Introduction
Hierarchical clustering (HC) is popular unsupervised learning method for organizing data into dendrogram (rooted tree). It can be viewed as clustering datapoints at multiple levels of granularity simultaneously, with each leaf of the tree corresponding a datapoint and each internal node of the tree corresponding to cluster consisting of its descendent leaves. Much the technical development of HC originated in the field of phylogenetics, where the motivation species into an evolutionary tree based on genomic similarities [22]. Since then, this tool has seen widespread use in data analysis for a variety of domains ranging from social networks, information retrieval, financial markets [28, 8, 43] amongst many others.
to organize the different
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Due to its popularity, HC has been extensively studied and several algorithms have been proposed. The most prominent amongst these are bottom-up agglomerative algorithms such as average linkage, single linkage, complete linkage etc. (see Chapter 14 in [33]). However, despite these advances on the algorithmic front, very few formal guarantees were known for their performance, primarily owing to a historic lack of well defined objective function. Therefore, the study of HC was largely empirical in nature for a long time.
A part of this issue was recently resolved, when [20] proposed an objective function for similarity- based HC. This has since sparked interest in both the theoretical computer science as well as machine learning communities, for designing algorithms with provable guarantees for this objective
19. 12. 10, 19, 2]. The formal description as follows: given as input a weighted undirected graph G = (V, E, w) with n vertices (datapoints) and m edges with positive edge weights corresponding to pairwise similarities between its endpoints, the objective is to find a hierarchy T over leaf nodes corresponding to the vertices V that minimizes the cost function
costa = Σ Wij (Tay.
(1)
where Tij is the subtree rooted at the least-common ancestor of i, in T and Tiyl is the number of descendent leaves in Tij. Intuitively, (T) incentivizes cutting heary edges at lower levels in T, thereby placing more similar datapoints closer together. This objective has been shown to have several desirable properties, including one that guarantees an optimal tree which is binary [20].
This minimization objective however, turns out to be NP-hard. Consequently, [20] and other subse- quent work explored this objective from an approximation algorithms perspective [42, 9, 12, 10, 19, 2]. The best known polynomial time approximation is O(vlog n) which is achieved by the recursive sparsest cut (RSC) algorithm [20, 9. 19]. It is also known that no constant factor polynomial time approximation is possible for this objective under the small-set expansion (SSE) hypothesis [9].
In this paper, we study the above minimization objective for HC in the context of massive graphs While the currently known best algorithm can be considered "efficient" in the classical sense, i.e. requires polynomial space and time" this complexity can be prohibitive in many modern applications of HC that deal with staggering volumes of data. For example, current social networks contain billions of edges which imposes serious limits on their storage and processing, Therefore, alternative models of computation need to be considered in the context of such massive graphs. In this work, we consider three widely-studied models, each aimed at optimizing a different fundamental resource: (i) the (dynamic) streaming model [24] for space efficiency, where the edges are presented in stream, (ii) the general graph (query) model [31] for time efficiency, where the edges can be accessed via degree and neighbour queries, and (ivi) the mussively parallel computation model (MPC) for communication efficiency, where the edges are partitioned across multiple machines connected together through a communication channel. The focus of our work is the following fundamental question:
Can we design sublinear (in the number of edges) algorithms for hierarchical clustering in each of these massive- graph computation models?
We provide almost complete resolution to this question by providing matching upper and lower bounds for sublinear algorithms in all three canonical models of computation discussed above.
Remark 1. When studying graph problems in the sublinear setting, one can consider an even more constrained setting where the available resource is o(n), i.e. sublinear in the number of vertices. However, we are interested in actually finding a hierarchical clustering of the data, the writing of which takes Q(1) time und space (and in MPC, M(n) machine memory). Since in most practical settings, the bottleneck is often the edges in the graph rather than the vertices, we believe makes more sense for us to consider sublinearity only in the edge parameter, i.e. m, in all three models.
Due to the space needed to present full technical details of our main results, we focus here on giving a overview; the complete paper is deferred to the Appendix. Our results are summarized in Table 1.
Notation. In the following section, we use and m to refer to the number of vertices and edges in the input graph, respectively. We use Ö(-) to suppress multiplicative Ollog n) factors for constant c,
We also note that a near-linear (in the number of edges) time implementation of RSC can be obtained by plugging a recent breakthrough result for fast flxwflow computation [14] into the balanced separator approximation algorithm in [44].
2

---

Table 1: Summary of Results. Each row gives an upper and lower bound on the resource
(ppacrimeccommaiictioon) required for (11) approximation in the corresponding model.
Setting/Parameters Upper Bound
Lower Bound
Streaming Model
1-pass
(()) Thm 2
9(x). trivial
(Sublinear Space)
Query Model
1 1<C5 4/3
Ö(n)) Thm 4
((15=o()) Thm 8
(Sublinear Time)
4/3 < S.
0(n.-2), Thm 4 ((n Thm 8
Edges m ((n5) G
3/2 < <<
Ö(n), Thm
((n). Thm 8
MPC Model
1-round
((14/5), Thm 6 ((14/3-011) Thm 9
(Sublinear Communication)
2-round
Ö(n), 5hm
[(n). trivial
and the term "w.h.p." implies with prohability 1 1 1/)oly(n)) Lastly, é will denote the approximation
ratio of any desired offlin algorithm for hierarchical clustering. For example, if allowed unbounded computation time, we have & 1; given polynomial time, the current best algorithm [9] gives e O(vlog n.). We assume this abstraction as any improvement in the approximation ratio here automatically implies identical improvement in our upper bounds.
2 Overview of Algorithmic Results
We begin by presenting our algorithmic results for the three models of computation, which at their core, are all based on the same aeta--llgoi which follows from a new structural view of the minimization objective defined in Eq. (1) in terms of global cuts in the input graph.
2.1 A Meta-Algorithm for Sublinear Hierarchical Clustering
In their paper, [20] showed that (T) can be viewed in two equivalent ways, the first being the one defined earlier in Eq. (I), and the other in terms of the splits induced by the internal nodes in the hierarchy: given a hierarchy T with each internal node corresponding to a binary split² where some subset of vertices S V of the input graph is partitioned into two pieces (S,, Sy). then
costa =
Σ
|S| [S]-we(( (St,
splits S (S....)) T
where for any disjoint subsets S,T C V. (o T) is the total weight of the edges in G going between S and T. At this point, one might be tempted to think that if we could somehow construct sparse representation of G such that the weights (S, T) are approximately preserved for any disjoint S,T' c V, then the cost of every hierarchy would also be approximately preserved. Following this, we could run any desired offline algorithm on this representation with improved efficiency due to its sparsity without much loss in the quality of its solution. Unfortunately, this is just wishful thinking as such a representation can easily be shown to require 2(m) time and space?. Our first contribution is to show there is in fact third equivalent view of this same objective function in terms of global cuts in G. and the above alternate formulation serves as our starting point.
This result follows from two critical observations, the first of which is given any two disjoint S.T C. V, we can compute Wg (S,(ST) exactly as (c( = (1/2) (wc(S, 3) + wo (T) ( (SUT, SUT).. We could stop here as the quantities on the right are all graph cuts, and is well known [7] that one can construct a (nn) sized sparsifier that approximately preserves all graph cuts. Unfortunately, the distortion in wg((S T') can be very large depending on the quantities on the right, and the cumulative error in (T") blows up with the depth of the tree which is even worse. Here
This without loss of generality since there always exists an optimal hierarchy that binary. GGien such sparsifier, by setting S = {u} and T' = {v). one can recover whether or not edge (u, v) is present in G for any u, E V.
3

---

is the second observation: the negative term US, that internal node S contributes to the cost also appears as a positive term in its parent's contribution the cost. We can pass this term as a discount in its parent's 's contribution to the cost, which after cascading gives a third view of Eq. (I).
costa
1 2
Σ
(IS,) wG( St) + [Sel (Sr, +
Σ wa (a)) VEV
splits (S
in
a linear combination of graph cuts. This gives strong blackbox reduction to cut-sparsifiers; preserv- ing graph cuts to (1 + <) factor also preserves the cost of all hierarchies to (1 + <) factor.
However, we are not done yet, as cut-sparsifiers cannot be computed efficiently in certain models of computation; for instance, they necessarily require (m)) queries to the underlying graph. We therefore introduce a weaker notion of sparsification that, for any cut (S, S), allows for an additive error of ō min [S), in addition to the usual multiplicative error of (1 + +)) (Appendix B Defn. 1). We term this generalization an (c, --uu sparsifier. A similar notion was also proposed in an earlier work by [36], which unfortunately does not work here (see Appendix D.I for details). Our next result then shows that the distortion in the cost of any hierarchy under this weaker sparsifier is also bounded.
Theorem (informal). Given any weighted graph G, an (c, 8)ttut sparsifier of G preserves the cost of any tree T up multiplicative (1 + c) factor, and an additive O(ōn²) factor.
Therefore, if we could lower bound the cost of the optimal hierarchical clustering by some quantity C, we could set 8 cC/n². The above result would then imply morally the same result as that achieved by traditional sut-sparsifiers: preserving graph cuts in this c, 6 sense for sufficiently small 5 also preserves the cost of all hierarchies upto a (1 + e) factor. The last key result exactly establishes such a general purpose lower bound on the cost of any hierarchical clustering in graph, which can be efficiently estimated all models of computation we consider.
This chain of ideas results in the following meta-algorithm for sublinear HC given any parameter >> 0 and model of computation: Compute the lower bound on the cost of an optimal HC which establishes the tolerable additive error in our (e, 8) sparsifier, following which we efficiently (in the resources to be optimized) compute the said sparsifier. We finally run any d-approximate HC algorithm, which is guaranteed to find (1 + appaappoxi HC tree. Our subsequent results give sublinear constructions of these (e, -utt sparsifiers in each of the three models of computation.
2.2 Sublinear Space Algorithms in the (Dynamic) Streaming Model
We first consider the dynamic streaming model for sublinear space algorithms, where the edges the input graph are presented in an arbitrarily ordered stream of edge insertions and deletions. Our upper bound here is a direct consequence of Theorem I used in conjunction with [1], a seminal result that showed an (c, O)- sparsifier can be constructed in Ö(E ?n) space and a single pass in this setting.
Theorem (informal). There exists single-pass, Ö(n) space, streaming algorithm that given any weighted graph G presented in a dynamic stream, w.h.p. finds a (1 + o(L) @-approximate HC of G.
As outlined in our alga-algori,hm, instantiating the offline algorithm with RSC with the input graph being the sparsifier gives us a polynomial time, Ö(n) space, single-pas sagle-pass dynamic streaming algorithm with approximation ratio O (VVlog n) corollary. See Appendix C for more details.
We note that coupled with recent result [15], our Theorem also implies an Ö(n) algorithm for finding a (1 + o(1)) d-approximate HC in the more general turnstile streams, where arbitrary edge weight updates can appear.
2.3 Sublinear Time Algorithms in the Query Model
We next consider the general graph model [31] for sublinear time algorithms, where the input graph can be accessed via two types of queries: (f) degree queries: given u E V. returns degree du and (it) neighbour queries: given u E V. i < dy, returns the i-th neighbour of u. Note that this model
"This query model also allows a third type of queries: pair queries which answer whether an edge (u, v) exists or not. However, do not need these queries in our algorithm.

---

can be easily implemented using an adjacency arryy representation of the graph (See Appendix D for a more detailed discussion). We first present the result for unweighted graphs, where is easier see the key intuition. Our main result in this model is a sublinear time construction of an (c, 6) -sspasiife...
Theorem 3 (informal). There exists an algorithm that given query access to any unweighted graph G, and any parameters e, E (0, 1). can find an (e, --uutt sparsifier of G w.h.p. in ((n(((e)) time.
Our algorithm is based on a simple yet elegant idea (which builds upon a slightly different idea proposed in [36]; see Appendix D.1 for a detailed discussion): if we embed a constant-degree expander with edge weights 5 in an unweighted graph (with unit edge weights), then the effective resistance of every edge in the resulting composite graph is tightly bound in terms of the effective degrees of its incident vertices; the effective degree of vertex is a weighted sum of its degree in the input graph and its degree in the expander. We can then leverage the effective resistance sampling scheme of [45] to construct an (c, 0)-cut sparsifier of this composite graph, which then deterministically an (e, 8--uut sparsifier of the input graph with the sources of error being the usual multiplicative e term due to sparsification itself, and the (small) additive å term due to the (few) extra edges introduced by the expander. We can construct constant degree graphs that are expanders with high probability in sublinear time, and we show that there is an efficient rejection sampling scheme for sampling edges according to their effective resistances, giving the above result: an (e, (e,d)-cul sparsifier with ((n/(E2))) edges in the same amount of time and queries. Moreover, the queries are completely non-adaptive assuming prior knowledge of vertex degrees. This construction of (e, 8) 6-cuut sparsifiers in conjunction with Theorem then gives our sublinear time upper bound in this model.
Theorem 4 (informal). There exists algorithm that given query access any unweighted graph G with m = @(15) for ( E [0, 2), can find a (1 + o(1)) g-approximate HC of G w.h.p. using Ögg(n, ()) queries, where g(n, () I n,4/3 is given by g(n, () = max(n, n2} when Ç E [0, 40,4/3), g(n, () max(n, can find an O(Vlog n) aaproxximate HC of G w.h.p. in Ö(g(n, () + + time.
when Ç E (4/3.2). Moreover, given any (arbitrarily small) constant O, the algorithm can
It is interesting to observe that the query complexity g(n. () reduces as the graph becomes denser. This is because the cost of the optimal HC increases with the density of the input graph, which allows us to tolerate a larger additive error in our cut sparsifier, thereby making it sparser. In Section we also discuss lower bounds showing that this query complexity is also the best possible for any Ö(1) approximate algorithm. The sublinear time claim in Theorem 4 implied by results from [44] and [14]. Specifically, [44] showed that, for any constant 7 E (0, 1/2), sparsest cuts and balanced separators can be approximated to within OVVlog n) in (()) time plus Önn) maximum flow computations on graphs with Ö(n) edges, and [14] showed that a maximum flow on a graph of m
edges can be computed in Omm++(()) time. These two combined with the fact that our sparsifier contains just Ö(g(n, {)) edges give us the desired running time bound.
We generalize the above result in Appendix D.2 to weighted graphs by grouping edges according to geometrically increasing weights and constructing (c, -cutt sparsifiers for each weight class, and get an algorithm with essentially the same worst case performance and O n. rounds of adaptivity.
2.4 Sublinear Communication Algorithms in the MPC model
Lastly, we consider the MPC model [6. 3) for sublinear communication, which is a common abstrac- tion of many MapReduce-style computational frameworks. Here, the edges in the input graph are partitioned across several machines that communicate with each other in synchronous rounds. Each machine has memory sublinear in m, with its total communication bounded by its memory. A more detailed description of this model is given in Appendix E.
Our first result is a 2-round MPC algorithm that uses (n) memory per machine. In our algorithm, we leverage a construction of (e, 0)-cut sparsifiers due to [I] using Ō(1) random linear sketches per vertex in the graph. We show that rounds are sufficient to construct these linear sketches for each vertex- the first round is used to construct partial sketches using local edges and the second round is used to aggregate these partial sketches into complete sketches for each vertex. This construction of (e, -utt sparsifiers in conjunction with Theorem 1 gives us the following result.
5

---

Theorem 5 (informal). There exists an MPC algorithm that given any weighted graph G with edges partitioned across machines with (n) memory and access to public randomness, can find (1 + o(1) d-approximate HC of G w.h.p. on a designated machine in rounds of MPC.
Our second result is 1-round MPC algorithm that solves this problem for unweighted graphs using machines with ( memory. The execution of our algorithm depends on the density of the underlying graph. If m I n/5/3, then we can again use the result from [1] by constructing local linear sketches on each machine and sending them to a coordinator who can aggregate them. Note that we only require 1 round in this case as the number of machines is S n and hence, we only need to communicate Onn sketches per vertex which is within our memory budget. If m > n we show that the cost of the optimal hierarchy sufficiently large such that coarse (c, 5)-cut sparsifier of size On obtained by randomly subsampling edges will suffice. As a consequence, each machine can subsample its edges independently and send these (na/33 edges to the coordinator. We now summarize this 1-round result below.
Theorem 6. (informal) There exists an MPC algorithm that given any unweighted graph G with edges partitioned across machines with (nA//) memory and access to public randomness, can find (1 + o()) d-approximate HC of G w.h.p. on a designated machine in I round of MPC.
In the next section, discuss 1-round lower bound for MPC which shows that 133--((1) memory per machine is needed by any Ö(1) apprrxxmate algorithm on unweighted graphs.
3 Overview of Lower Bounds
First note that in the (dynamic) streaming model, since our goal is for the algorithm to output a hierarchical clustering tree, we necessarily need (2(n) space. Thus our Önn) space dynamic streaming algorithm that obtains a (1 + (p))-xpprxximttionn is nearly optimal. We then show that in the other two models of computation, our algorithms are also essentially the best possible.
3.1 Lower bounds the Query Model
Note that the query complexity bound of our sublinear time algorithm is always at most Ö(n where the worst-case input an unweighted graph with about m R na/3 edges. We note that our algorithm obtains an O(Vlog n) -approximationn and (i) is completely non-adaptive on unweighted graphs assuming prior knowledge of vertex degrees, and has Oloog n) rounds of adaptivity on weighted graphs; (ii) only uses degree queries and neighbor queries (no pair queries needed, see Footnote 4). We then show that n/43-o(11 queries indeed necessary for obtaining any Ö(1)- approximation even in unweighted graphs and given unlimited adaptivity and access to pair queries.
Theorem 7 (informal). Let A be a randomized algorithm that, on any imput unweighted graph with (nn23)) edges, outputs with high probability polylog(n) nolylog(n)-upproximng -approxxiee hierarchical clustering tree. Then A necessarily uses at least n 4/3-o(1) queries.
We briefly describe the family of hard graph instances that we use to prove this result. Roughly. a graph from such a family is generated by first taking a union of 2/2 vertex-disjoint cliques of size 1/3 each, and then connecting them by a random "perfect matching". More specifically, we treat each clique as a supermode, and generate a perfect matching between these n/2/3 supernodes uniformly at random. Then if the ,th clique is matched to the jth clique in the perfect matching, we will add about (1) edges between these two cliques, which are also chosen in a random manner. We show that, in order to output a good hierarchical clustering solution, it necessary to discover non-trivial portion of the edges that we add between the cliques, even though their number is relatively tiny compared to those within, and the latter task provably requires n 4//3-o(1) queries.
While this plan looks intuitive, has to be careful about not leaking information about the "perfect matching" between the cliques from the vertex degrees, which an algorithm knows a priori (or can otherwise acquire using ((n) non-adaptive degree queries). In particular, once the inter-clique edges added, one could tell that the vertices with degree higher than 1/3 1 are those participating in the perfect matching. Note that there are only n 2/3+((1)) such vertices in total, and each of them has

---

degree at most (3n As a result, by probing all neighbors of these vertices, one can easily find all the inter-clique edges using n ==(+ neighbor queries.
Our way around this issue is to also delete certain edges within the cliques based what inter-clique edges we have added, so as to ensure that each vertex has the exact same degree of n n - 1. This of course further complicates things as it increases the correlation between the edge slots - for instance, whenever edge between matched pair of cliques is revealed to the algorithm, missing edges within each clique are no longer independent. Consequently, our proof for this lower bound turns out to be considerably involved; we refer the reader to Appendix F.2 for more details.
Theorem shows that the worst-case query complexity of our algorithm is nearly optimal. Note that, however, for unweighted graphs, our algorithm also obtains improved query/time complexity when m is far from n 4/4/3, It is then natural to ask - are these improvements also the best possible? We answer this question in the affirmative. In particular, we show that one can push further the ideas we discussed above to get tight query lower bound for every graph density. We summarize these lower bounds below. Note in particular that, for m (n²)) ) as we will show later, any hierarchical clustering achieves an ((1)- approximation, thus trivially 0 queries are sufficient.
Theorem (informal). Let Ç E [o, 2| be any constant. Let A be a randomized algorithm that, on any input unweighted graph with (nn)) edges, output with high probability a polylog(n)-approzinnnn apprrxxmaae HC. Then A necessarily uses least (g ()) queries. where g(n, = max(n, (n, (6-0()) when < E [0, 4/3), g(n, () max/n, n² (4-((-0(2)) when ( E (4/3, 2), and g(n, <) = 0 when < 2.
3.2 Lower bounds in the MPC Model
As our goal is for some machine to output good hierarchical clustering tree, M2() memory per machine is necessary. Indeed, our 2-round MPC algorithm obtains (1 + o()))approxximation for weighted graphs using a nearly optimal memory of Ö(n) per machine (Theorem 5).
To show that the number of rounds of our algorithm is also optimal, we prove that superlinear (in particular, n n/33-o(()) memory per machine is necessary for any 1-round MPC algorithm in which some machine outputs with high probability a polylog(n) "aaprrooiio hierarchical clustering tree. Moreover, in our lower bound instance, the total memory of all machines is m, which means that the input is split across fewest possible machines. We specifically prove the following result:
Theorem 9 (informal). Let P be any I-round protocal in the MPC model where each machine has memory (nn/3365) for any constant ε > O. Then at the end of the protocol P, no machine can output polylog(n) (n) -hierarchical clustering tree with probability better than o(1).
Note that this lower bound matches our upper bound result Theorem Our family of hard instances is roughly defined as follows. Let 2/3,3 3 se 1/3 be certain constants. A graph G of 2n vertices from such a family consists of two vertex-disjoint parts, each supported on n vertices. The first part is supported
vertices V1 and is a union of vertex- vertex-disjoint bi-cliques of size n²; the second part is supported on vertices V22 and is in turn a union of vertex-disjoint bi-cliques of size n², where we have [Vi = V22 = We will also permute the vertex labels of G uniformly at random. See Figure I for an illustrative example of such a graph G.
We first show that in order to output a good hierarchical clustering solution, it is necessary to discover (almost) the exact clique structures of the vertex- vertex-induced subgraphs G[Vi). G[V2), for otherwise a balanced cut has non-trivial probability of cutting too many edges within the cliques. Then as an adversary, our strategy is to hide G[V2], which has significantly fewer edges than G[Vi], by splitting G across multiple machines. To this end, we observe that G[Vi] can be tiled using edge-disjoint subgraphs CI...., G2 that are each isomorphic to G[V=] (see Figure 1). This suggests that we could give G[V3] to uniformly random machine, and then give each G, to one of the other machines.
Note that, crucially, each machine's input follows the exact same distribution, namely a union of bi- cliques of size n/8 with vertex labels permuted uniformly at random, although the input distributions of different machines are correlated. As a result, each machine individually has no information whether its input graph is G([V2 or just subgraph G; of G[V.). Therefore, each machine has to send a message to the coordinator such that, if its input graph happens to be [2]2 the coordinator will be able to recover the clique structures with high probability.
7

---

G[Vi:
G[V]]
An illustrative example of an input graph G, where G[Vi] is a union of two bi-cliques of size 8 each, and G[V2] is union of four bi-cliques of size 4 each. Here G[Vi] can be tiled using two edge-disjoint subgraphs each isomorphic to G[V2], which are the subgraph induced by edges within the four red frames, and the subgraph induced by edges within the four blue frames. So no machine can tell locally whether was given the red subgraph, the blue subgraph, or G[V)).
Figure 1:
Since the coordinator can only receive a total message size bounded by its machine memory, by choosing suitable values of a, B, each machine on average can only send message of size o(n). Now the problem effectively becomes a one-way, two party communication problem, where Alice is given G[V2] and needs to send Bob single message that Bob recover the clique structures with high probability. We then conclude the proof by showing that this two-party problem requires (n) communication. We refer the reader Appendix G for more details.
Related Work
The work of Dasgupta [20] the starting point our work. [20] defined the objective function for hierarchical clustering, namely minimum cost hierarchical partitioning, that study in this paper. They showed that the resulting problem NP-hard and the recursive sparsest-cut algorithm achieves an O log n)) approximation, where o O(vlog n) is the current best poly-time approximation for sparsest-cut, [42] improved this approximation factor to Olog n) using an LP-based algorithm. [19, 9] showed that the recursive sparsest cut algorithm of [20] in-fact achieves an ((ő) approximation. [42] and [9] also showed that no polynomial time algorithm can achieve constant factor approximation under the small set expansion (SSE) hypothesis. [19,37 37] showed that by imposing certain probabilistic or structural assumptions on the graph, one can circumvent this constant factor inapproximability.
There has also been work on maximization objectives for hierarchical clustering. [39] considered "dual" version of the Dasgupta objective: where the goal to maximize the revenue n Eee We. C7Sta(7). While the optimal values for both objectives are achieved by the same solution, this objective behaves very differently from an approximation perspective. [19] considered a setting where the edge weights correspond dissimilarities rather than similarities and the goal is to maximize the dissimilarity-basee objective costa [39] and [19] both study the average- average-linkage algorithm and show that achieves approximation factors of 1/3 and 2/3, respectively. [10] provided algorithms with slightly better approximation factors of 1/3 + 5 and 2/3 + 8, respectively. [13] improved the approximation factor 0.4246 for the dual objective in [39], which was later improved to 0.585 by [2]. Very recently, [40] improved the approximation to 0.71604 for the dissimilarity objective of [19].
Several other variations of this basic setup have been considered. For example, [12] have considered this problem in the presence of structural constraints, [11, 38, 41] considered setting where vertices are embedded in a metric space and the similarity/dissimilrrty between two vertices is given by their distances. The most relevant to our work amongst these is [41] which considered this metric streaming setting. However, the stream in their setting
embedded hierarchical clustering problem is composed of vertices while edge weights can be directly inferred using distances between vertices; whereas the stream in our streaming setting is composed edges while vertices are already known. Moreover, their study is only limited to the streaming setting. There has also been work on designing faster/parallel agglomerative algorithms such as single-linkage, average-linkage etc. [48, 21, 46]. While these works share the same motivation ours, namely, scaling HC algorithms to massive

---

datasets, these results are largely orthogonal to ours. The primary philosophical difference is that these aforrementioned works are aimed speeding up/parallelizing very specific kinds of linkage based algorithms,, while recovering the same or similar cluster trees (under very different notions of similarity) that would have been computed by the slower/sequential algorithm. Moreover, the specific algorithms considered in these works have no known approximation guarantees for Dasgupta's ' objective. Our work on the other hand approaches this problem from an optimization perspective. Through data sparsification, we aim to recover cluster tree with marginal loss in objective function value as compared to one computed over the entire (dense) input data by any given IIC algorithm as a blackbox. achieving speedup in runtime or reducing its memory requirement due to sparsity. [32] studied the hierarchical clustering problem in an MPC setting. However, their work only considered the maximization objectives [39, 19]. while our work is primarily focussed on the minimization objective of [20].
Very recently and independent of our work, [5] considered the problem of hierarchical clustering under Dasgupta's 's objective in the (dynamic) streaming setting. The primary focus of their work is on estimating the cost of an optimal hierarchy in o(n) space whereas the focus of our work is to actually output a near-optimal hierarchical clustering. [5] also gives a single-pass, (n) memory streaming algorithm for finding a clustering that also uses cut-sparsifiers. However, their algorithm needs to restrict the solution space to only balanced trees, and hence, is only able to achieve an (()) approximation guarantee instead of the stronger (1 + o(1) á approximation guarantee that achieve for the streaming setting. They also obtain a 2-round algorithm for MPC that achieves an (()) approximation guarantee using (()) memory per machine, which is again slightly weaker than the (1 + o(1) approximation guarantee that we achieve. But [5] does not show any lower bound results for the MPC model. Moreover, their work does not consider sublinear time setting and their algorithms cannot be easily adapted to this setting.
Recent Independent work:
The techniques we use in our paper can also be used to compute an expander decomposition of a graph presented in a dynamic stream. In particular, [25] showed that computing an expander decomposition reduces which approximates every cut to within a small multiplicative error plus some additive error that is proportional to the volume of the smaller side of the cut. In this work, we show how to obtain cut sparsifiers with similar guarantees except that (i) our additive error is proportional to the number of vertices of the smaller side of the cut, and (ii) our approach does not work for graphs with self-loops, which is required for the reduction given in [25]. Here (i) is actually stronger guarantee, since in graph without isolated vertices, the volume of subset of vertices is at least its size, whereas (ii) is drawback for this application. However, one can in fact trade off these two by slightly changing the analysis of our algorithm, while keeping the algorithm exactly the same, on which we elaborate below.
More Related work:
computing the so-called power cut sparsifier of a graph,
Specifically, our analysis is done by doing the following thought experiment add a (weighted) constant degree expander to the original graph, and then show that the effective resistance of each edge (u. v) in the original graph has become ~ 1/d,, + 1/d,,, with d,, d, being the degree of u, v, and therefore sampling each edge with probability R 1 1/dn, + 1/d, gives a sparsifier of the composed graph, which is in turn a sparsifier with some additive error of the original graph. One can also adapt this analysis so that the same algorithm works for obtaining power cut sparsifiers. In particular, in our thought experiment, we will now add an expander where each vertex has degree (roughly) proportional to its original degree, and can again show that the effective resistance can be bounded by & 1/d.,- + 1/d,, even if there are self-loops in the original graph. Therefore the same algorithm works, with the additive error now being proportional to the volume of the smaller side, desired. Finally, as observed in [25], sampling edges with probability x 1/d,- + 1/d, can be implemented in straightforward manner in dynamic streams.
5 Implications for Other Hierarchical Clustering Objectives
As noted in the previous section, two maximization objectives for hierarchical clustering were proposed subsequent to the work of [20]: (1) the revenue objective [39] for similarity-basee HC which is a "dual" of cost: (T), (2) the dissimilarity objective [19] where the edges correspond to pairwise dissimilarities and the objective is the same as (O). In this section, we discuss the implications of our work for both objectives in the sublinear-resout regime.

---

We begin by noting a sharp contrast in the difficulty of achieving "good" solution for the minimiza- tion objective [20], and the two maximization objectives described above. In fact, is possible to achieve ((1) approximation to both maximization objectives von-adaprively; a random binary hier- archy, in expectation, is a 1 1/3 approximation of the optimal revenue [39], and a 2/3 approximation of the optimal dissimilarity objective [19], constructing which requires no knowledge of the input graph. On the other hand, it is not hard to see that one would achieve an arbitrarily bad approximation of the minimization objective unless something non-trivial was learned about the input graph.
That said, one can further question whether is possible to match the solution quality of any given alapproximate offline algorithm for the maximization objectives in the models of computation we consider. We answer this in the affirmative; we can in fact achieve even stronger performance guarantees for both objectives in the sublinear resource regime by exploiting the fact that their corresponding optimal hierarchies have large objective function values", allowing us to tolerate even larger additive errors in our cut-sparsifiers. A straightforward application of our structural decomposition of the cost function along with its downstream implications in each of the three models of computation directly gives us (1p o(1)) -apprxxxxo algorithms for both HC maximization objectives in weighted graphs that use (i) single-pass and ((n) space in the dynamic streaming model, (ii) (n) queries in the general graph (query) model, (iti) 2-rounds and Ō(n) communication in the MPC model, which can be further improved to use just (fv) I-round, and (n)) communication for unweighted graphs.
Conclusions and Future Directions
In this paper, we studied hierarchical clustering problem under Dasgupta's objective [20] in the regime of sublinear computational resources. We gave sublinear space, query, and communication algorithms for finding a (1 + (1))o=-pproximmat hierarchical clustering, where ø is the approximation ratio of any offline algorithm for this problem, and a sublinear time algorithm for finding an OVVlog n)- approximate hierarchical clustering. At the core of our sublinear algorithms is a novel meta-algorithm which first obtains an (e, -ctt sparsifier of the graph and then runs hierarchical clustering algo- rithm on the sparsifier. We also proved sharp information-theorett lower bounds showing that the performance of all our sublinear algorithms is essentially optimal for any polylog (oolloggn)aaa)) apprroxxxiitooonn
Note that all our algorithms and lower bounds are aimed at finding an explicit hierarchical clustering tree. Therefore a natural direction for future work is to understand whether we can get even more efficient sublinear algorithms if we only want to estimate the cost of the optimal hierarchical clustering within some small error. We note that two recent and independent works have already considered this question. In the streaming model, [5] have proved extensive lower bounds for optimal cost estimation under various regimes of space and number of passes over the input stream. In the query model, [35] have proved both upper and lower bounds for sublinear time cost estimation under certain "wsell-cuuterrbiliit" assumptions and given auxiliary information about the underlying input graph instance. However, this question remains open in the query model (sublinear time) for more general input graph instances, and completely unexplored in the MPC model (sublinear communication).
Acknowledgments and Disclosure of Funding
This work was supported in part by NSF awards CCF-1763514, CCF-1934876, and CCF-2008305.
References
[1] AHN, K. J., GUHA, S., AND MCGREGOR, A. Graph sketches: sparsification, spanners, and subgraphs. In Proceedings the 31 ACM SIGMOD-SIGACT-SIGAN Symposium Principles of Database Systems,
'Given any input instance, a random binary hicrarchy achieves an objective function value of a n EeER We expectation, where 1/3 for the revenue objective and a 2/3 for the dissimilarity objective. Since both are maximization problems, the objective function values of the optimal hierarchies must be at least as large. 6 "s of now, we can only give sublinear query algorithms for both these objectives. Our results still imply a sublinear time (10 -aprooaopoinnaaooonn result in both maximization settings if we were given al-approximate, (m) time offline algorithm in the corresponding setting, However, we are not aware of such an algorithm for either objective.
10

---

PODS 2012, Scottsdale, AZ, USA, May 20-24, 2012 (2012), M. Benedikt, M. Krötzsch, and M. Lenzerini, Eds., ACM, 5-14.
[2] ALON, N., AZAR, Y., AND VAINSTEIN, Hierarchical clustering: 0.585 revenue approximation. In Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austrial (2020),
J. D. Abernethy and S. Agarwal, Eds., vol. 125 of Proceedings of Machine Learning Research, PMLR,
pp. 153-162.
[3] ANDONI, A.. NIKOLOV, A.. ONAK, K., AND YAROSLAVISEV. G. Parallel algorithms for geometric graph problems. In Symposium on Theory of Computing, STOC 2014, New York, NY. USA, May 31 June 03, 2014 (2014), D. B. Shmoys, Ed., ACM, pp. 574-583.
[4] ARORA, S.. RAO, S., AND VAZIRANI, U. Expander flows, geometric embeddings and graph partitioning. Journal of the ACM (JACM) 56, 2 (2009), 1-37.
ASSADI, S., CHATZIAFRATIS, V., LACKI, J., MIRROKNI, V., AND WANG, C. Hierarchical clustering in graph streams: Single-pass algorithms and space lower bounds. In Conference on Learning Theory (COLT) (To Appear, Personal Communication) (2022).
[6]
BEAME, P., KOUTRIS, P., AND SUCIU, D. Communication steps for parallel query processing.. J. ACM 64, 6 (2017), 40:1-40:58.
[7] BENCZÜR, A. A., AND KARGER, D. R. Approximating minimum cuts in Ō(r²) time. In Proceedings of the Twenty-Eighth Annual ACM Symposiun on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996 (1996), G. L. Miller, Ed., ACM, pp. 47-55.
[8] BERKHIN, P. A survey of clustering data mining techniques. In Grouping Multidimensional Data Recent Advances in Clustering, J. Kogan, C. K. Nicholas, and M. Tehoulle, Eds. Springer, 2006, pp. 25-71.
[9] CHARIKAR, M., AND CHATZIAFRATIS, V. Approximate hierarchical clustering via sparsest and spreading metries. In Proceedings of the EveettyEightte Annual ACM-SIAM Symposium on Discrete Algorithuss, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19 (2017), P. N. Klein, Ed., SIAM, pp. 841-854.
[10] CHARIKAR, M., CHATZIAFRATIS, V., AND NIAZADEH, R. Hierarchical clustering better than average- linkage. Proceedings of the Thirtieth Annual ACM-SIAM Symposium Discrete Algorithmss SODA 2019, San Diego, California, USA, January 6-9, 2019 (2019), T. M. Chan, Ed., SIAM, pp. 2291-2304.
[11] CHARIKAR. M., CHATZIAFRATIS, V., NIAZADEH. R., AND YAROSLAV G. Hierarchical clustering for euclidean data. In The 22nd International Conference Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan (2019), K. Chaudhuri and M. Sugiyama, Eds., vol. 89 of Proceedings of Machine Learning Research, PMLR, pp. 2721-2730.
[12] CHATZIAFRATIS, V., NIAZADEH, R., AND CHARIKAR, M. Hierarchical clustering with structural constraints. In Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmüssson, Stockholm, Sweden, July 10-15, 2018 (2018), J. G. Dy and A. Krause, Eds., vol. 80 of Proceedings of Machine Learning Research, PMLR, pp. 773-782.
[13] CHATZIAFRATIS, V.. YAROSLAVTSEV. G., LEE, E.. MAKARYCHEV. K., AHMADIAN. S., EPASTO. A., AND MAHDIAN, M. Bisect and conquer: Hicrarchical clustering via max-uncut bisection. In The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy] (2020), S. Chiappa and R. Calandra, Eds., vol. 108 of Proceedings of Machine Learning Research, PMLR, pp. 3121-3132.
[14] CHEN, L., KYNG, R., LIU, P., PENG, R., GUTENBERG. M. P., AND SACHDEVA, S. Maximum flow and minimum-com flow in almost-linee time. CoRR abs/2203.0061 (2022).
[15] CHEN, Y., KHANNA, S., AND LI, H. On weighted graph sparsification by linear sketching. To appear in 63rd Annual IEFE Symposium on Foundations of Computer Science, FOCS 2022. Available at https: //arxiv. .org/ ab// hbtp///bb/22..... 22w.//2299902....
[16] CHEN, Y., KHANNA, S.. AND NAGDA, A. Near-linear size hypergraph cut sparsifiers. 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) (2020), IEEE, pp. 61-72.
[17] CHEN, Y., KHANNA, S., AND NAGDA. S. Sublinear time hypergraph sparsification via cut and edge sampling queries. In 48th International Colloquium Automata, Languages, and Programming (2021).
11

---

[18] COHEN-ADDAD. V., KANADE, V., AND MALLMANN-TRENT F. Hierarchical clustering beyond the worst-case. In Advances in Neural Information Processing Systems 30: Annual Conference Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA (2017), 1. Guyon, U. von Luxburg. S. Bengio, H. M. Wallach, R. Fergus, V. N. Vishwanathan, and R. Gamett, Eds.,
pp.
[19] COHEN-ADDAD, V., KANADE, V., MALIMANN-TRENT F., AND MATHIEU, C. Hierarchical clustering: Objective functions and algorithms. J. ACM 66, 4 (2019), 26:1-26:42.
[20] DASGUPTA, S. A cost function for similarity sanilarity--bsed hierarchical clustering. In Proceedings of the 48th Annual ACM SIGACT Symposium Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18 18-21, 2016 (2016), D. Wichs and Y. Mansour, Eds., ACM. pp. 118 127.
[21] DHULIPALA, L.,, EISENSTAT, D., LACKI, J., MIRROKNI, V. S., AND SHI, J. Hicrarchical agglomerative graph clustering nearly-lineat time. Pruceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event (2021), M. Meila and T. Zhang, Eds., vol. 139 of Proceedings of Machine Learning Research, PMLR. pp. 2676-2686.
[22] EISEN, M. B.. SPELLMAN, P. T., BROWN, P. O., AND BOTSTEIN, D. Cluster analysis and display of genome- wide expression patterns. Proceedings the National Academy of Sciences 95, 25 (1998). 14863-14868.
[23] ERDOS, P.,, RÉNYI, A., AL. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci 5, 1 (1960), 17-60.
[24] FEIGENBAUM, J., KANNAN, S., McGREGOR, A., SURL. S., AND ZHANG, graph problems in a semi-streaming model. Theor. Comput. Sei. 348, 2-3 (2005), 207-216.
[25] FILTSER, A., KAPRALOV, M., AND MAKAROV, M. Expander decomposition in dynamic streams. CoRR abs/2211.11384 (2022).
[26] FRIEDMAN, J., KAHN, J., AND SZEMEREDI, F. On the second eigenvalue of random regular graphs. In Proceedings of the twenty-first annual ACM symposium on Theory of computing (1989), pp. 587-598.
[27] FRIEZE, A. M. Edge-disjoint paths in expander graphs. SIAM Journal on Computing 30, (2001), 1790-1801
[28] GILBERT, F., SIMONETTO, P., ZAIDI, F., JOURDAN, F,, AND BOURQUI, R. Communities and hierarchi- cal structures in dynamic social networks: analysis and visualization. Social Network Analysis and Mining 1. (2011), 83-95.
[29] GOEL,, A., KAPRALOV, M., AND POST, Single pass sparsification the streaming model with edge deletions. arXiv preprint 12Xiv:1203.499 (2012).
[30] GOLDBERG, A. V., AND RAo, S. Beyond the flow decomposition barrier. Journal of the ACM (JACM) 45, 5 (1998), 783-797.
[31] GOLDREICH, O. Introduction to Property Testing. Cambridge University Press, 2017.
[32] HAJIAGHAYL, M., AND KNITTEL, M. Improved hierarchical clustering on massive datasets with broad guarantees. arXiv preprini 11Xiv:2101.04818 (2021).
[33] HASTIE, T., TIBSHIRANI, R., FRIEDMAN, J. H., AND FRIEDMAN, J. H. The elements of statistical learning: data mining, inference, and prediction, vol. 2. Springer, 2009.
[34] HUANG, X., CHEN, Y., YIN, W., AND YUAN, K. Lower bounds and nearly optimal algorithms in distributed learning with communication compression. Advances in Neural Information Processing Systems (NeurlPS) (2022).
[35] KAPRALOV, M., KUMAR, A., LATTANZI, S., AND MOUSAVIFAR, A. Learning hierarchical structure clusterable graphs. arXiv preprint Xix::207.00258 (2022).
[36] LEE, Y. T. Probabilistic spectral sparsification in sublincar time. CoRR abs/1401.008 (2014).
[37] MANGHICC B., AND SUN, H. Hierarchical clustering: O())aapprox for well-clustered graphs. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Pro- cessing Systems 2021, NewrIPS 2021, December 6 14, 2021, virtual (2021), M. Ranzato, A. Beygelzimer.
Y. N. Dauphin, P. Liang, and J. W. Vaughan, Eds., pp. 9278-9289.
12

---

[38] MOSELEY, B., VASSILVITSKIL S.. AND WANG, Y. Hierarchical clustering in general metric spaces using approximate nearest neighbors. In The 24th International Conference Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event (2021), Banerjec and K. Fukumizu, Eds., vol. 130 of Proceedings of Machine Learning Research, PMLR, pp. 1440-2445
[39] MOSELEY, B., AND WANG, R. Approximation bounds for hierarchical clustering: Average linkage, bisecting k-means, and local search. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA (2017). I. Guyon, U. Luxburg, S. Bengio, H. M. Wallach, R. Fergus, S. V. N. Vishwanathan, and R. Garnett, Eds., pp. 3094-3103.
[40] RAHGOSHAY, M., AND SALAVATI,OU M. R. Hierarchical clustering: New bounds and objective. CoRR abs/2111.0682 (2021).
[41] RAJAGOPALAN, A., VITALE, F.. VAINSTEIN, D., CITOvSKY, G., PROCOPIUC, M., AND GENTILE, Hierarchical clustering of data streams: Scalable algorithms and approximation guarantees. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event (2021), M. Mcila and T. Zhang, Eds., vol. 139 of Proceedings of Machine Learning Research, PMLR, pp. 8799 8809.
[42] Roy, AND POKUTTA, S. Hierarchical clustering via spreading metries. J. Mach. Learn. Res. 18 (2017). 88:1-88:35.
[43] SCHÖTZE, H., MANNING, C. D., AND RAGHAVAN, Introduction to information retrieval, vol. 39, Cambridge University Press Cambridge, 2008
[44] SHERMAN, J. Breaking the multicommodity flow barrier o(vlog nj-approximations to sparsest cut. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA (2009), IEEE Computer Suciety, pp. 363-372.
[45] SPIELMAN, D. A., AND SRIVASTAVA, N. Graph sparsification by effective resistances. SIAM Journal on Computing 40, 6 (2011), 1913-1926.
[46] SUMENGEN, B., RAJAGOPALAN, A., CITOVSKY, G., SIMCHA, D., BACHEM, O., MITRA, P., BLASIAK. S.. LIANG, M., AND KUMAR. S. Scaling hierarchical agglomerative clustering to billion-sized datasets. arXiv preprint arXiv:2105. 11653 (2021).
[47] YAO, C. Prohabilistic computations: Toward unified measure of complexity (extended abstract). In 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October / November 1977 (1977), TEFE Computer Society, pp. 222-227.
[48] YAROSLAVTSEN, G., AND VADAPALLI, A. Massively parallel algorithms and hardness for single-linkage clustering under ip distances. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmasssnn Stockholm, Sweden, July 10-15, 2018 (2018), J. G. Dy and A. Krause, Eds., vol. 80 Proceedings of Machine Learning Research, PMLR, pp. 5596 5596-5605,
[49] YUAN, K., CHEN, Y., HUANG, X., ZHANG, Y., PAN, P., XU, Y., AND YIN, W. Decentl Decentral- ized momentum SGD for large-batch deep training. International Conference on Computer Vision (ICCV) (2021).
[50] YUAN, K., HUANG, X., CHEN, Y., ZHANG, X., ZHANG. Y., AND PAN, P. Revisiting optimal convergence rate for smooth and non-convex stochastic decentralized optimization. Advances in Neural Information Processing Systems (NeurlPS) (2022).
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contribu- tions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you diseuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
13

---

(b) Did you include complete proofs of all theoretical results? [Yes]
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 URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect to the random seed after running experiments multiple times)? [N/A]
(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)? [N/A]
4. If you are using existing assets (c.g., code, data, models) or curating/relcasigg new assets...
(a) your work uses existing assets, you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're 're us-
ing/curating? [N/A]
(c) Did you discuss whether the data you using/curating contains personally identifiable informa- tion or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(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, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "JxwA260Sis", "reviewer": "Reviewer_pUsh", "summary": "This paper considers developing resource efficient algorithms for hierarchical clustering of weighted graphs in several settings (streaming, graph query model, mpc model).  Following recent work which developed an objective function for hierarchical clustering (Dasgupta 2016), the goal is to develop algorithms with sublinear resource usage (in the number of edges) in each model while producing an $O(\\phi)$-approximation to the optimal tree for Dasgupta's objective function.  The main results of this paper are to achieve exactly this.  By making a key observation about the structure of the objective function, the authors show that this problem reduces to efficiently constructing a cut sparsifier.  In some settings (e.g. streaming using $\\tilde{O}(n)$ space), this can be done immediately via known techniques for constructing cut sparsifiers.  For the other settings (graph query model and the mpc model), a more relaxed notion of cut sparsifier is proposed (which allows for some additive error in addition to the multiplicative error), and the authors give sublinear algorithms for constructing such a relaxed cut sparsifier in the remaining settings.  Lower bounds showing near optimality of the results are also given.", "questions": "How would the proposed algorithms compare to practically efficient algorithms? e.g. Sumengen, Baris, et al. \"Scaling hierarchical agglomerative clustering to billion-sized datasets.\" arXiv preprint arXiv:2105.11653 (2021).", "limitations": "N/A", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "There has been significant interest in hierarchical clustering recently and one issue that many algorithms suffer from is scalability.  This paper helps to address this problem in several settings from the perspective of Dasgupta's objective function.  The techniques are natural and are well explained.\n\nOne thing that is missing from this paper (but not probably not necessary) is an experimental evaluation to demonstrate the practical effectiveness of the proposed algorithms.", "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": "94ZVpYfaW7", "reviewer": "Reviewer_1tqq", "summary": "Hierarchical clustering over graphs ha been mathematically formalized with a natural objective function introduced by Dasgupta [STOC2016]. Unfortunately, this function is hard to optimize and approximation algorithms have been proposed in the TCS literature. This paper studies this problem in the regime of sublinear computational resources, specifically, for three models of computations:\n- streaming model = sublinear space\n- query model = sublinear time\n- MPC model = sublinear communication\nFor each model, upper and lower bounds are provided.", "questions": "I am not sure I understand the motivation for the authors to submit this paper to Neurips and I would like to hear their arguments explaining why it is more appropriate to publish this work at Neurips instead of a TCS conference like SODA, STOC, FOCS? I did count 12 references in JACM, STOC, SODA and FOCS. \nI like cross-disciplinary work but then you need a lot more work to motivate your results. As it is written, I hardly see any possible impact for this paper in the ML community. Even the computational models will only be known from a minority of the audience, so that the main results will not be understood.\nSimilarly, the lower bounds are obtained by constructing very contrived graphs. I understand that these hard instances are instructive in order to understand the worst-case performance of algorithms. But what is the motivation for these bounds in a machine learning setting?", "limitations": "NA", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper presents informal statements for the main results proven in Appendix. The results appear to be new. There is a recent COLT paper [5] with similar results in the streaming setting.\nThis paper is well-written and deals with theoretical results.\nThe motivation for these results is very far from any practical application.", "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": "8WtXgt3-QG", "reviewer": "Reviewer_CYrg", "summary": "This paper designs sublinear algorithms for hierarchical clustering in dynamic streaming model, query model and MPC model over very large graphs. Minimum cost hierarchical partitioning is the optimization objection (Dasgupta’s cost function). From the theoretical aspect, this paper proved the bounds including lower and upper bound respectively for the three given models. They prove a general structural result that shows that a cut sparsifier can be used to recover a (1 +o(1))-approximation to the underlying HC instance.\n\n", "questions": "none", "limitations": "1.\tSome recent works prove a seem better bound for the same problem. The authors should compare to them. For example, Assadi S, Chatziafratis V, Mirrokni V, et al. Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds[C]//Conference on Learning Theory. PMLR, 2022: 4643-4702.\n2.\tAlthough proofs on bounds are good evidence for showing the performance, it would be better and attractive to give some practical experimental studies to show the real effectiveness in massive graphs. In some cases, a well theoretical complexity still be not enough for the real huge graphs.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Although this research problem is not novel, sublinear algorithms for hierarchical clustering is one of the fundamental issue in the studies of graphs. Lots of applications need the sublinear algorithms especially for massive graphs. The paper is well written with a good presentation. It supplies enough theoretical proofs for the complexity and (1 +o(1))-approximation is a good general structural result in the three models. However, I have some concerns about the approach and applications.\n1.\tSome recent works prove a seem better bound for the same problem. The authors should compare to them. For example, Assadi S, Chatziafratis V, Mirrokni V, et al. Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds[C]//Conference on Learning Theory. PMLR, 2022: 4643-4702.\n2.\tAlthough proofs on bounds are good evidence for showing the performance, it would be better and attractive to give some practical experimental studies to show the real effectiveness in massive graphs. In some cases, a well theoretical complexity still be not enough for the real huge graphs.\n\nMinor problem:\nAlthough the presentation is relatively well, some necessary examples are needed for the readers to follow clearly. ", "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": "7KPi3fRuobM", "reviewer": "Reviewer_kk3J", "summary": "This paper focuses on hierarchical clustering over graphs with the objective function of Dasgupta. Sublinear algorithms w.r.t. the number of edges in the input graph are developed in three models of computation, including the dynamic streaming model, the query model, and the massively parallel computation (MPC) model. Interesting matching lower bounds are provided for the upper bounded resource above. Specifically, a 1-pass semi-streaming algorithm naturally follow from existing algorithm [1] and their observation. In the query model, combining existing methods [14,37] and their observation leads to sublinear time algorithms for graphs of different sparsity. For the MPC model, a 2-round $\\tilde{O}(m)$-memory algorithm and a 1-round $\\tilde{\\Theta}(m^{4/3})$-memory algorithm are developed based on [1]. All above algorithms rely on the crucial observations that, from a graph cut perspective, the objective function can be well approximated in a cut sparsifier of the input graph. Moreover, two hard instances are designed to derive time and communication lower bounds in the query and MPC models, respectively. Finally, the extensions to other related hierarchical clustering objectives such as the dissimilarity [15] are discussed.", "questions": "In the alternative view of the objective based on S-T cut, a sparsifier approximately preserving all S-T cut values suffers from the lower bound of $\\Omega(m)$. When transforming the S-T cut to graph cut ($S,\\bar{S}$)-cut, why the barrier of lower bound can be broken?", "limitations": "No", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The idea of using cut sparsifiers in improving the computational resource of graph algorithms has been widely used. But using it in hierarchical clustering and providing theoretical analysis on the required resource and approximation factor is not well studied with only a few related work, e.g., [5]. The problem of hierarchical clustering is reduced to the problem of constructing cut sparsifiers with limited resource based on the observations that cut sparsifiers can approximately preserve the cost of a dendrogram. Comprehensive studies on 3 models of computation are performed and upper bounds are complemented with almost matching lower bounds.\n2. The developed lower bounds in the query and MPC models are quite interesting and need to overcome multiple challenges. The authors are able to describe the high-level overview in the main text and then refer to the full details in the Appendix.\n3. The organization of this work is good. I like the discussions in Sections 4 and 5, providing context on related works and extensions to other objective functions of hierarchical clustering. I browsed some contents in the Appendix and the quality of writing remains good compared to the main text.\n\nWeaknesses:\n1. The computational upper bounds developed in Section 2 are not very challenging and based on existing methods in the respective models. The upper and lower bounds in the dynamic streaming model are straightforward.\n2. As a reader of a hierarchical clustering paper in NeurIPS, I would expect to see some experimental results on the developed algorithm unless the theoretical contributions are very novel and significant. It would be much better if experiments on some of the algorithms had been implemented and evaluated in real-world datasets.\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