Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs
Authors: Bogdan Adrian Manghiuc
He Sun
Venue: NeurIPS 2021 Poster (2021)
Keywords: Hierarchical clustering
graph algorithms
spectral methods

Abstract: Hierarchical clustering  studies a recursive partition of a data set into clusters of successively smaller size, and is a fundamental problem in data analysis. In this work we study the cost function for hierarchical clustering introduced by Dasgupta, and present two polynomial-time approximation algorithms: Our first result is an $O(1)$-approximation algorithm for graphs of high conductance. Our simple construction bypasses complicated recursive routines of finding sparse cuts known in the literature. Our second and main result is an $O(1)$-approximation algorithm for a wide family of graphs that exhibit a well-defined structure of clusters. This result generalises the previous state-of-the-art, which holds only for graphs generated from stochastic models. The significance of our work is demonstrated by the empirical analysis on both synthetic and real-world data sets, on which our presented algorithm outperforms  the previously proposed algorithm for graphs with a well-defined cluster structure.

Hierarchical Clustering: for Well-Clustered Graphs*
Bogdan-Adrian Manghiuc
He Sun School of Informatics The University of Edinburgh h. sun@ed. ac. uk
School of Informatics The University of Edinburgh
b. mww.miinnnsssss....m.m... ed. ac.
Abstract
Hierarchical clustering studies a recursive partition of a data set into clusters of successively smaller size, and is fundamental problem in data analysis. In this work we study the cost function for hierarchical clustering introduced by Dasgupta [12,, and present two polynomial-time approximation algorithms: Our first result is an (a))aappoximmation algorithm for graphs of high conductance. Our simple construction bypasses complicated recursive routines of finding sparse cuts known in the literature (e.g., 6 IT] D. Our second and main result is an O(1)- approximation algorithm for wide family of graphs that exhibit well-defined structure of clusters. This result generalises the previous state-of of-the-art (IO), which holds only for graphs generated from stochastic models. The significance of our work demonstrated by the empirical analysís on both synthetic and real-world data sets, which our presented algorithm outperforms the previously proposed algorithm for graphs with a well-defined cluster structure T0
Introduction
Hierarchical clustering (HC) studies recursive partition of data set into clusters of successively smaller size, via an effective binary tree representation. As a basic technique, hierarchical clustering has been employed standard package in data analysis, and has comprehensive applications in practice. While traditionally HC trees are constructed through bottom-up (agglomerative) heuristics, which lacked clearly-defined objective function, Dasgupta [12 has recently introduced simple objective function to measure the quality of a particular hierarchical clustering and his work has inspired a number research on this topic 3 6
[1 20 24). Consequently, there has been significant interest in studying efficient HC algorithms that not only work in practice, but also have proven theoretical guarantees with respect to Dasgupta's cost function.
10
this work, we present two new approximation algorithms for constructing HC trees that can be rigorously analysed with respect to Dasgupta's cost function. For our first result, we construct an HC tree of an input graph G entirely based on the degree sequence of V VG)), and we show that the approximation guarantee of our constructed tree is with respect to the conductance of G. which will be defined formally in Section 2 The striking fact of this result is that, for any n-vertex graph G with m edges and conductance I2[1) (a.k.a. expander graph), an (11-aaprroximal
Our contribution.
HC tree G can very easily constructed in O(m + n log time, although obtaining such result for general graphs is impossible under the Small Set Expansion Hypothesis (SSEH) (6] Our theorem is line with a sequence of results for problems that are naturally linked to the Unique Games and Small Set Expansion problems: it has been shown that such problems much casier to solve once
'The full version of the paper is available at htltttts//arraee org/ wwtpaass....//a/aaa/aaa/aaaaataa 02155
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

the input instance exhibits the high conductance property 4 5 16 18). However, to the best of our knowledge, our result is the first of this type for hierarchical clustering.
While our first result presents an interesting theoretical fact, we further study whether we can extend this ((1)-approximate construction much wider family of graphs occurring in practice. Specifically, we look at well-clustered graphs, i.c., the graphs in which vertices within each cluster are better connected than vertices between different clusters and the total number of clusters is constant. This includes a wide range of graphs occurring in practice with a clear cluster-structure, and have been extensively studied over the past two decades (e.g.. I3 15 26 ). As our second and main result, we present a polynomial-timg -immi ((1) "approxximmtionn algorithm that constructs an HC tree for well-clustered graph. Given that the class of well-clustered graphs includes graphs with clusters of different sizes and asymmetrical internal structure, our result significantly improves the previous state-of-thh-ar [10], which only holds for graphs generated from stochastic models. At the technical level, the design of our algorithm is based on the graph decomposition algorithm presented in [3] which is designed to find a good partition of a well clustered graph. However, our analysis suggests that, in order to obtain an Oapp-ooooonnnaaoonn algorithm, directly applying their decomposition isn't 't sufficient for our purpose. To overcome this bottleneck, we refine the output decomposition via a pruming technique, and carefully merge the refined parts to construct our final HC tree. In our point of view, our presented stronger graph decomposition procedure might have applications in other settings as well. To demonstrate the significance of our work, compare our algorithm against the previous ofate-of-the-att the- with similar approximation guarantee [00] and well-known linkage heuristics on both synthetic and real-world data sets. Although our algorithm's 's performance is marginally better than [0 for the graphs generated from the stochastic block models (SBM), the cost of our algorithm's 's output is up 50% lower than the one from [10] when the clusters of the input graph have different sizes and some cliques are embedded into a cluster.
Related work. Our work fits in a line of research initiated by Dasgupta [12), who introduced a cost function to measure the quality of an HC tree. Dasgupta proved that recursive application of the algorithm for the Sparest Cut problem achieves an (log n) -aapprxximation, which has been subsequently improved to O(log n) and O O()log by [24] and O M. It is known to be NP-hard to find an optimal HC tree [22 and SSEH-hard to achieve an O(1) (())aaproximmaion for general input instance [6] Cohen-
et al. [10] studied a hierarchical extension of the SBM and showed that certain SVD projection algorithm together with several linkage heuristics achieves (1 + (pp))))ppoxxiattion with high probability. We emphasise that our notion of well-clustered graphs generalises the SBM variant studied
10 and does not assume the rigid hierarchical structure
of the clusters.
For another line of related work, Moseley and Wang (20) studied the dual objective function and proved that Average Linkage achieves a (1/3)-approximation for the new objective function. Notice that, although this has received significant attention very recently 3 an O(1) (pprrxxppxinnnooonn is tractable under this alternative objective. This suggests the fundamental difference on the hardness of the problem under different objective functions, and is our reason to entirely focus on the Dasgupta's 's cost function in this work.
25 achieving
2 Preliminaries
Throughout the paper, we always assume that G = (V, F,, w) is an undirected graph with vertices. m edges and weight function w : V x V + R20- For any edge e = {u, E E we write we or Wav to indicate the similarity weight between and v. For vertex E V. we denote its degree O(pol((n)), where Wmin (imix(mmxx) is the minimum (maximum) edge weight. We will use dminn dmax davg for the minimum, maximum and average degrees in G, where davg 2 EmEr v du//n. /n. For a nonempty subset S C V, we define G[S] to be the induced subgraph on S and we denote by G(S} the subgraph G[S], where self loops are added to vertices e E S such that their degrees in G and G[S} are the same. For any two subsets S,T C V. we define the cut value () &
by d,, A Evev Whe and we assume that Himax/Wmin
E.EF(S.T) We, where F(S,T) T) is the set of edges between S and T. For any set S C V. the volume of S is vol(S) A Enes d, and we write vol(G)) when referring
2

---

to vol( We further define the conductance of S by
(G)) _ w(S, V .)) vol(S)
and @ min SCV (S). We call G an expander graph if DG = Q(1). For graph G, vol(s) Svol( let D E pxxx be the diagonal matrix defined by D uu du for all V. We denote by A E R the adjacency matrix of G. where Auv = Wun for all u, v E V. The normalised Laplacian matrix of G' is defined as C - I D 1-112AA A0/2AD-1/" 1/2, where is the identity n x matrix. We will denote the eigenvalues of C by 0 À S ... S..SA An 2
Hierarchical clustering. A hierarchical clustering (HC) tree of a given graph G is a binary tree T with n leaf nodes such that each leaf corresponds to exactly one vertex v E V(G), Let T be an HC tree of some graph G (V, E, w) and let N E T be an arbitrary internal node of T. We denote T[N] to be the subtree of T rooted at N, leaves (T[N] to be the set of leaf nodes of [[N] and parenty (N) to be the parent of node N T. addition, each internal node N E T induces unique vertex set C' C V formed by the vertices corresponding to leaves(T We will abuse the notation and write N
for both the internal node of 'T and its corresponding set of vertices V.
To measure the quality of an HC tree T with similarity weights, Dasgupta [12 introduced the following cost function:
cost (T)
We llevees (Tlu v vl)l,
where u V is the lowest common ancestor of and in T. Trees that achieve better hierarchical clustering have a lower cost, based on the following consideration: for any pair of vertices u, v E V that corresponds to edge of high weight Wae (i.e., and would separate u and v lower in the tree, thus reflected in a small size llaveesTTuu vl)). We denote by OPT the minimum cost of any HC tree of G, i.e., OPT refer to an optimal tree achieving the minimum. We say that an HC tree T is an a-approximate tree if costa (7) OPT All omitted proofs are deferred the full version of this paper.
highly similar) "good" HC tree
miny cost (T), and use T to
3 Hierarchical clustering for graphs of high conductance
In this section we study hierarchical clustering for graphs with high conductance and prove that, for any input graph G' with & = S2(1), appaapprox HC tree of G can be simply constructed based on the degree sequence of G. As a starting point, we show that cosLa(T) for any T can be upper bounded with respect to @ and the degree distribution of V(G).
Lemma 3.1. It holds for any HC tree T of graph G that cost (T) S OPTG.
9
min
davg,
dmax
dentn
davz
While Lemma 3.1 holds for any graph G, it implies some interesting facts for expander graphs: first of all, when G EV w) sat-
isfics dmax//main = O(1) and &G = ((1).
Lemma 3.1 shows that any tree T is O(1)
V/S
approximate tree. In addition, although 4G plays crucial role in analysing costa (T)
S
V
for many other graph problems, Lemma 3.1 in- dicates that the degree distribution of G might also have significant impact. One could natu- rally ask the extend to which the degree distribu- tion of (G)) would influence the construction of optimal trees.
(a)
(b)
Figure I: (a) Our considered graph G: (b) the tree that
separates the vertices of high degrees from the others achieves ((1) (ppp)pppxxiiaiion.
To study this question, we look at the following graph G where all edges have unit weight: (i) let G (V, E1) be constant-degree expander graph of n vertices with &c, R(1), e.g., the ones
We will always use (internal) nodes for the nodes of T and vertices for the elements of the vertex set V.

---

presented in [1]; (ii) we choose |n2/3] vertices from V to form S, and let K = (S, x S) be complete graph defined on S; (iii) partition the vertices of V into [n groups of roughly the same size, associate each group to a unique vertex in S and let Eg be the set of edges formed by connecting every vertex in S with all the vertices in its associated group. (iv) let _ (V, E1 (S x S) U U2) be the union of G1. K and the edges in Eg. see Figure I [a) for illustration. By construction, we know that $ = (1)), and the degrees of G satisfy dmax (n22/3), Amin = (1), and davg = (m33) Therefore, the ratio between (T) for any HC tree T and O could be as high as (nn//3). On the other side, it's not difficult to show that the tree T illustrated in Figure 1(b), which first separates the set S of high-degree vertices from V \ S at the top of the tree, actually O(1) apprrxxpxss O
This example suggests that grouping vertices of similar degrees first could potentially help reduce (T) for our constructed T. This motivates to design the following Algorithm to construct an HC tree. We highlight that the output of Algorithm D is uniquely determined by the ordering of the vertices of G according their degrees, which can be computed in (n logn) time.
Algorithm 1: #CCittheegrees(((V)
Input: G (V, E, w) with the ordered vertices such that du, 2 ... 2 duj
Output: An HC tree (G);
if [V] = then
L return the single vertex in V as the tree;
else
2imax; = fei.... 3 }: B = V A; Let = ([CrithDegrees(((AA] T2 HCwi thDegreessGG
immx = [log
return Tdeg with Ti and To as the two children.
Theorem 1. Given any graph G (V, w) with conductance ta as input, Algorithm 7 runs in O(m + n nog time, and returns HC tree Taeg of G that satisfies (esta(Tdeg) O 1/ OPTG.
Theorem g guarantees that, when the input G satisfies &G 2(1), the output Taeg of Algorithm 1 achieves an ((1) >approximation. Moreover, as the high-conductance property can be determined in nearly-linear time by computing (2(G)) and applying the Cheeger inequality. Algorithm [ presents a very simple construction of an ((1)-approximo))) HC tree once the input G is known to have high conductance.
Proof sketch of Theorem 1 The key notion employed in our proof is that of the dense branch which can be informally described as follows: we perform a traversal in T starting at the root node Ag and we sequentially travel to the child of higher volume. The process stops whenever we reach a node Ag. for some E Zzo. such that vol(AA) > vol(G)/2 and both its children have volume at most vol(G) The sequence of visited nodes by this process is the dense branch of T. Formally, for any HC tree T of G. the dense branch is the path (Ag, Ar, .d.......
AA.) .d.....,AA.......... in T for some & E Z such that the following conditions hold: (1) Ag is the root of T; (2) Ag is the node such that vol(AA) > vol(G)/2 and both children of A₁ have volume at most vol It is important to note that the dense branch of tree T is unique and it contains all nodes A, such that vol(A.) vol(G)/2 and only those nodes.
At a very high level, the proof of Theorem 1 starts with any optimal HC tree To of G and constructs trees Ti, T2, Ta and T4 such that (i) cost T:)) can be upper bounded with respect to costig (Ti-1) for every S i S 4, (ii) the final constructed T4 is exactly the tree Tacg(G), the output of Algorithm Combining these two facts allows us to upper bound costa(TTez) with respect to OPT
Step 1: Regularisation. Let (Ao. ....... Ako) be the dense branch of any optimal To. and let B; be the sibling of A, for all 1 < i S ku- Let imin [log. DJ and émax = [[o 1) For simplicity, we assume that the dense branch has size at least 2. that |A 2 2 Fumax and that |A = 2'mine, which ensures that imin I imax. These assumptions allow us better present the proof techniques by ignoring some corner cases. In the full version of our paper we deal with the
To see this, notice that cost(T") S (ost(T"(S)) + vol(G.) n² e(n²), the complete subgraph GPS induces cost of (/33))333 [2] The subgraph G[S] also implies that OPTo 2(rz)).

---

A11-1
Ay-1
A
Bs
A2
B
As1ta
B1
Ay2
CaL
A
A
B1
A
B
A
B₁
Aja
B
CJ2
As+1
By+1
A
B
A32
B3
B32
Aj+1
(a)
(b)
Figure 2: (a) With proper partition of By+1, have new node A of size 2'; (b) The nodes hetween A and A2 (left) have size in (2' 2,2=; These nodes are compressed (right) and only the nodes of size some power of 2 remain in the dense branch.
general case when some of these assumptions do not hold. The goal of this step is to adjust the dense branch of To, such that the resulting tree satisfies the following condition: for all E [imiu mmax]. there is a node of size exactly 2' along the dense branch of TT. We achieve this by applying sequence of operations, each of which creating new node of exact size 2' for some suitable i. Concretely, let i Emin: Amax] be the largest integer such that there is no node of size 2 the dense branch of To- As AAkol 2'min there some node A, on the dense branch such that |Ayl > and |Aj+1| < 2 We adjust the branch at Aj as follows: we consider partition of BJ+1 B3 1 B such that |Aj+1| + |B = 2'; (ii) we replace the node A, by some newly created node A) that has children B and new node A3. (iii) the two children of A3 will be Aj+1 and B3+2- This adjustment is illustrated in Figure 2 a), and we repeat this process until no such exists any more. We call the resulting tree T1, and the following lemma gives an upper bound of costa(Ti).
Lemma 3.2. Our constructed tree Ti satisfies c S (1 4/4c) cost
Step 2: Compression. With potential relabelling of the nodes, let (Ao..... Ak,) be the dense branch
of Ti for some 11 E Z4 satisfying |A,, 2'min, and B, be the sibling of A,. The objective of this step ensure that, by a sequence of adjustments, all the nodes along the dense branch are of size equal to some power of 2. Here, we describe how one such adjustment is performed, and refer the reader to Figure b) for illustration. Let E [imin: 'max] be some index such that | = 2 and |Aja| 2 for some ji j2. We compress the dense branch by removing all nodes between Aj and AJ₂ as follows: The two children of A₁, will be Ajz and some new node Cj. which has children Cj++1 and +1, The two children of C +1 will be some new node C and Bj, +2, etc. The last node Cja-2 has children -1 and B In addition, we perform one more such adjustment to remove all nodes Aj of size 2imax < |Ay < and ensure all nodes (except potentially Ao) on the dense branch have size 2 for some i E [imin /max]. We call the resulting tree T2, and the following lemma bounds the cost of Tz-
Lemma 3.3. Our constructed tree To satisfies that costi (T2) < 2 costa((T)
Step 3: Matching. Let (Ao...., Akg) be the dense branch of Tz, for some l:2 E 24, and B; be the sibling of A,. In this step we transform Tn into Ta. such that Ta is isomorphic to (G), which ensures that Ta and Taeg (G) have the same structure. To achieve this, for every S K2 we simply replace each To [.]] with Targ (,) We further replace T2[Ang] with Taeg (G{ Ax,)). We call resulting tree Tz. and bound cost by the following lemma:
Lemma 3.4. Our constructed tree Ta satisfies that costi (Ts) < (1 + 4/ costa (T)).
5

---

Step 4: Sorting. We assume that (Au..... Akg) ) is the dense branch of T3 for some K3 E E+, and we extend the dense branch to (Ao...., Aimax) with the same property that for every i E [R's, kmaax] A; is the child of A with the higher volume, and let S - {Bi,... B Bimag Aimas) J. Recall that in Tang G) the first r = 26max vertices of the highest degrees, i.e., {Vi,..., ,,) belong to A1, of which the first 2'max - vertices belong to A2, and so on; however, this might not be the case for T3- Hence, in the final step, we prove that T3 can be transformed into Taag (G) without significant increase of the total cost. this step we will swap vertices between the internal nodes B1, Bg..... Br Aimax in such way that Aiamx will consist of 11 and 02, Bi will consist of 03 and 24. B Bimax-1 -1 will consist of os up to Us. etc. We call vertex u misplaced if the position u is Ta is different from the one in Taeg( (G). To transform T3 into Taeg(G) we perform a sequence of operations, each of which consisting in chain of swaps focusing on the vertex of the highest degree that is currently misplaced. For the sake of argument,
apply the following operation to move U1 to Atmas (i) let 01 E Bi, for some ig 2 1. and let y be the vertex of the lowest degree among the vertices in S (Bi..... B Say y E B,, for some i >> in. and swap in with y while keeping the structure of the tree unchanged; (ii) repeat the swap operation above until U1 reaches its correct place Aipax. Once the above process is complete and it reaches Aioas we apply a similar chain of swaps to U/ to ensure 1/2 also reaches A Then, we sequentially apply the process v3 and 14 to ensure they reach B. and continue this process until there are more misplaced vertices.
assume that U1 &f Aimax is misplaced, and
We call the resulting tree Tg. and notice that every node X E S in T- contains the correct set of vertices. However, the positions of these vertices in Tg [X] might be different from the ones in Taog (G) To overcome this issue, we repeat Step 3 again to the tree Ta. and this will introduce another factor of (144/))) to the total cost of the constructed tree. Importantly, the final constructed tree after this step is exactly the tree Taeg (G) and we bound its cost by the following lemma:
Lemma 3.5. It holds for Tdeg that cost(Tdeg) I (1 + 24/ 2a) (1 (1+ (4/4))) cost(T5).
3.3 3.4 and 3.5 we prove the approximation guarantee of Tdeg in Theorem The runtime of Algorithm tollows by a simple application of the master theorem.
Finally, by combining Lemmas 3.2
4 Hierarchical clustering for well-clustered graphs
So far we have shown that an (1])-approximate tree can be easily constructed for expander graphs. We will now focus on a wider class of well-clustered graphs. Informally, a well-clustered graph is a collection of densely-connecter components (clusters) of high conductance, which are weakly interconnected. As these graphs form some of the most meaningful objects for clustering in practice, one would naturally ask whether our ( oppp-xxpoonnnaoionn for expanders can be extended to well- clustered graphs. In this section, we will give an affirmative answer to this question.
To formalise the well-clustered property, we consider the notion of (Φin, Pout) decomposiiioon introduced by Gharan and Trevisan [3] Formally, for a graph G = (V, E, w) and i E Z.,, we say that G has & well-defined clusters if VG) can be partitioned into disjoint subsets (P.) such that the following hold: (i) there's a sparse cut between P; and V \ P. for any 1 S iiss k. which is formulated as (P.) S Pout: and (ii) each induced subgraph G[P.] has high conductance Pajp. 2 Pin. We underline that, through the celebrated higher-order Cheeger inequality [17), this condition of (#i. Pout) )decomposiiioonn can be approximately reduced to other formulations of a well-clustered graph studied in the literature, e.g.. 23 26 27
The starting point of our second result is the following polynomial-tine time algorithm presented by Gharan and Trevisan [13], which produces (4i.. L ddccomposiion of graph G for some parameters D... and Pout- Specifically, given a well-clustered graph as input, their algorithm returns disjoint sets of vertices (P.) with bounded & (P:) and (.[p. for each P., and the algorithm's 's performance is as follows:
Lemma 4.1 (113. Theorem 1.6), Let G = (V, E, w) be a graph such that A > O, for some k 2 1. Then, there is a polynomial time algorithm that finds an E-partition {P.) of V, for some S k. such that the following hold for every 1 S i
(A1) ((P)) O (x))

---

(A2) & 2a( Ω
Informally, this result states that, when the underlying input graph G presents clear structure of clusters, one can find in polynomial-ime a partition { {P.ji=ı such that both the outer and inner conductance of every P. can be bounded. One natural question raising from this partition {Pr) is whether we can directly use [ to construct an HC tree. As an obvious approach, one could consider to (i) construct trees Ti = Taeg (Go(GG)) (.))..) for every 1 S i S L, and (ii) merge the tres { in the best way to construct the final tree Tg. Unfortunately, this direct approach does not work, and we present in the full version of the paper an example where this approach fails to achieve an (11) approximmatoo To address this, we follow our intuition gained from Figure [ and further decompose every P: into smaller subsets. Similar with analysing dense branches, we introduce the critical nodes associated with each Tí.
Definition 4.2 (Critical nodes), Let Ti Taee (G(P)) be the tree computed by Algorithm 7 to the in- duced graph G[P.]. Suppose (Ag....,A,, is the dense branch of for some T; E E4, Bj is the sib- ling of A, and let Ar,-1: Br.+1 1 be the two children of Ar.. We define S, 2 :BB....., Br,+1, Art+13 and call every node N E S, a critical node.
We remark that each critical node N S; (1 e) is an internal node of maximum size in T; that is not on the dense branch. Moreover, each S; is a partition of P.. Based on critical nodes, we present an improved decomposition algorithm, which is similar to the one in Lemma 4.1 and prove that the output quality of our algorithm can be significantly strengthened for hierarchical clustering. Specifically, in addition to satisfying (A1) and (A2), we prove that the total weight between each critical node N E S; and all the other clusters Pj. for all i 4 j. can be upper bounded. We highlight that this is one of the key properties that allows us obtain our main result, and also suggests that the original decomposition algorithm in [13 might not suffice for our purpose.
Lemma 4.3 (Strong Decomposition Lemma). Let G = (V, F,, w) be graph such that XR+1 > 0 and AK= = O(k (1). Then, there is a polynomial- -ime algorithm that finds an E-partition of into sets {P.). for some & S. k, such that properties (A1) and (A2) hold for every 1 ISi S Moreover, for every cluster P, and every critical node N E Sy, it holds that
(A3) w(N, V VX P.) S 6(k (0(++11 1) volG)..)(N).
To underline the importance of (A3),, recall that, in general, each subtree T. cannot be directly used to construct an -apprxopoo HC tree of G because of the potential high cost of the crossing edges EP,,, V \ P.). However, if the internal cost of T; is high enough to compensate for the cost introduced for the crossing edges E(P,, V P.), then one can safely use this T, as a building block. This is one of the most crucial insights that leads us to design our final algorithm PruneMerge.
Now we are ready to describe the algorithm PruneMerge, and we refer the reader to Algorithm for the formal presentation. At high-level, our algorithm consists of three phases: Partition Prune and Merge. In the Partition phase (Lines 1-2), the algorithm invokes Lemma 4.3 to partition V (G)
into sets {P.} and applics Algorithm | to obtain the corresponding trees [T. The Prune phase (Lines 4-11) consists of repeated pruning process: for every such tree Te, the algorithm checks in Line 7 if the maximal possible cost of the edges ((P;, V \ P.) (i.e., the LHS of the inequality in the if if-condition) can be bounded by the internal cost of the critical nodes N E S, up to a factor of Okk).
* If so, the algorithm uses T, as building block and adds it to global set of trees TT; Otherwise, the algorithm prunes the subtree [N], where N E S, is the critical node closest the root in T., and adds [[[N] T (Line 11).
The process is repeated with the pruned Tj until either the condition in Line 7 satisfied, or Tr is completely pruned. Finally, in the Merge phase (Lines 13-15) the algorithm combines the trees in in a "caterpillar style" according to an increasing order of their sizes. The performance of this algorithm is summarised in Theorem [
Theorem 2. Let G (V, E, w) be graph, and k > 1 such that Ak+1 > and d = O 12). The algorithu PruneMerge runs in polynomial-time and constructs an HC tree Tem of G satisfying
(TM)) O (k²2 /x -PTc. In particular, when Ak+1 = (11 and k = O(1), the
algorithm's 's constructed tree TPM satisfies that costa (TPM) = (()) OPT
'The example consists of copies of the graph Figure Ia], a), connected by sparse cut.
7

---

Algorithm 2: PruneMerge(G..t
Input: A graph G = (V, E, w). a parameter k E 2, such that A6+1 > 0: Output: An HC tree TPM of G;
Apply the partitioning algorithm (Lemma 4.3) on input (G, k) to obtain {Pil== for some & S k;
Let T; HCzithDegreess(([]])
3
Initialise T = 0;
for All clusters P. do
Let S; be the set of critical nodes of Ti;
while S is nonempty do
if n -.ENeS w N, V Pi) < 6(k + ENES, pparenty, (N) vola(p.(()) then Update T TUT, T and S = 0;
else
10
Let N, M be the two children of the root of T, such that N E Sü;
11
Update + TUT[N], S; + {N} and T < T[[M];
12 Let t = [T] and T (T Te} be such that [ S ( ll. for 1 S < t;
Initialise TPM TT;
14 for 2 do
15 Let TPM be the tree with TPM and T, as its two children;
16 return TPM-
We remark that, although Algorithm requires a parameter as input, we can apply the standard technique of running Algorithm 2 for different values of & and returning the tree with the lowest cost. By introducing factor of O(k) to the algorithm's runtime, this ensures that one of the constructed trees by Algorithm would always satisfy our promised approximation ratio.
5 Experiments
We experimentally evaluate the performance of our proposed algorithm, and compare it against the three well-known linkage heuristics for computing hierarchical clustering trees, and different variants of the algorithm proposed in [10), i.e. Linkage++, on both synthetic and real-world data sets. At high level, Linkage++ consists of the following three steps:
(i) Project the input data points into lower dimensional Euclidean subspace;
(ii) Run the Single Linkage algorithm []] until clusters are left;
(iii) Run a Density based linkage algorithm on the clusters until one cluster is left.
Specifically, our algorithm PruneMerge will be compared against the following 6 algorithms:
Average Linkage, Complete Linkage, and Single Linkage: the three well-known linkage algorithms studied in the literature. We refer the reader to [1] for complete description.
Linkage++, PCA+ and Density: the algorithm proposed in 10 together with two variants also studied [1O]. The algorithm PCA+ corresponds to running Steps (i) and (ii) of Linkage++ until one cluster is left (as opposed to k clusters), while Density corresponds to running Steps (i) and (iii) of Linkage++.
All algorithms were implemented Python 3.8 and the experiments were performed using an Intel(R) Core(T'M) i5-6500 CPU @ 3. 3.20GHz processor, with 16 GB RAM. All of the reported costs below are averaged over independent runs.
Synthetic data sets. We first compare the performance of our algorithm with the aforementioned other algorithms on synthetic data sets.

---

Clusters of the same size. Our first set of experiments employ input graphs generated according to random stochastic models, where all clusters have the same size. For our first experiment, we look at graphs generated from the standard Stochastic Block Model (SBM). We first set the number of clusters as 3, and the number of vertices in each cluster {P.} as 1, 000. We assume that any pair of vertices within each cluster is connected by an edge with probability p, and any pair of vertices from different clusters is connected by an edge with probability q. We fix the value = 0.002, and consider different values of p E [0.04, 0.2]. Our experimental results are illustrated in Figure 3a) a).
For our second experiment, we consider graphs generated according a hierarchical stochastic block model (HSBM) [T]] This model assumes the existence of ground-truti hierarchical structure of the clusters. For the specific choice of parameters, we the number of clusters as l 5. and the number of vertices in each cluster {P.) as 600. For every pair of vertices (u, 2) E P. x PJ. we assume that u and v are connected by an edge with probability p if
otherwise u and are connected by an edge with probability gi.j defined as follows: (i) for all E 2 and j E {4, (4 (r.j 1z.i Jmini (ii) for E {1,2), 46.3 = Q3,i = quin'' (iii) q4.5 = q5.4 = 2 Gmin: (iv) 91.2 Q2.1 = Qmin- We fix the value Qmin 0.0005 and consider different values of p [0.04, 0.2] as illustrated in Figure B).. We remark that this choice parameters resembles similarities with [10] and this is to ensure that the underlying clusters exhibit ground truth hierarchical structure.
As reported in Figure 3l our experimental results for both sets of graphs are similar, and the perfor- mance of our algorithm is marginally better than Linkage++, This is well expected, as Linkage+ is specifically designed for the HSBM, in which all the clusters have the same inner density characterised by parameter p, and their algorithm achieves (1 + ((1))-aprrxximaton for those instances.
Arglnaag
Dany shage
(a)
(b)
Figure 3: Results for clusters of the same size. The r-axis represents different values of p. while the y-axis represents the cost of the algorithms' returned HC trees normalised by the cost of PruneMerge. Figure (a)
corresponds to inputs generated according to the SBM, while Figure (b) to those according to the HSBM.
Clusters with non-uniform densities. Next we study graphs in which edges are present non-uniformly within each cluster (c.g., Figure I(a) discussed earlier). Specifically, we set k = 3, PP: 1000, q 0.002, p- = 0.06, and every pair of vertices (u, r)) P; x P, connected by an edge with probability if j and probability q otherwise. Moreover, this time we choose a random set S: C P. of size [S|] = Cp. IP: from each cluster, and add edges to connect every pair of vertices in each S₁ so that the vertices of each S; form clique. By setting different values of cp E [0.05, 0.4). the performance of our algorithm is about 20% - 50% better than Linkage++ with respect to the cost value of the constructed tree, see Figure 4a) for detailed results. To explain the outperformance of our algorithm, notice that, by adding a clique into some cluster, the cluster structure is usually preserved with respect to (iin & ouut) similar eigen-gap assumption such a clique within some cluster would make the vertices' degrees highly unbalanced; as such many clustering algorithms that involve the matrix perturbation theory in their analysis might not work well.
well-clustered graphs. However, the existence of
Clusters of different sizes. To further highlight the significance of our algorithm on synthetic graphs of non-symmetric structures among the clusters, we study the graphs in which the clusters have different sizes. We choose the same set of h and values as before (k = 3, = 0.002), but set the sizes of the clusters to be P1| = 1900, P2 = 900 and [Pal 200. Every pair of vertices u, P. for i {1, 2} is connected by edge with probability p1 0.06, while pairs of vertices

---

Piveregg
(a)
(b)
and Figure 4: Results for graphs with non-uniform densities, or different sizes. The w-axis represents the ca-values, while the y-axis represents the cost of the algorithms' constructed trees normalised by the cost of the ones constructed by PruneMerge. Figure (a) corresponds to inputs where all clusters have the same size, while in Figure (b) the clusters have different sizes.
v, U. E P3 are connected with probability 5 P = 0.3. We further plant a clique S, C P. of size |S, Cp P. for each cluster P., the previous set of experiments. By choosing different values of Cp from [0.05, 0.4), our results are reported in Figure b), demonstrating that our algorithm performs better than the ones in [10]
Real-world data sets. To evaluate the perfor- mance of our algorithm on real-world data sets, we follow the sequence of recent work on hier-
Colouregge
all of which are based on the following data sets from the Scikit-learn library [22] as well as the UCI ML repository 1 Iris, Wine, Cancer, Boston and 0 Newsgroup Similar with (24), for each data set we construct the similarity graph based on the Gaussian kernel, in which the o-value is cho- sen according to the standard heuristic [21]. As reported in Figure 5 our algorithm performs marginally worse than Linkage++ and signifi- cantly better than PCA+.
archical clustering 2 10 19 24
Figure 5: Results real-world data sets. The 27-axis represents the various data and our choice of the o-value used for constructing the similarity graphs. The y-axis corresponds to the cost of the algorithms' output normalised by the cost of PruneMerge.
Conclusion
The experimental results synthetic data sets demonstrate that our presented algorithm PruneMerge not only has excellent theoretical guarantees, but also produces output of lower cost than the previous algorithm Linkage++. In particular, the outperformance of our algorithm is best illustrated graphs whose clusters have asymmetric internal structure and non-uniform densities. On the other side, the experimental results real-world data sets show that the performance of PruneMerge inferior to Linkage++ and especially to Average Linkage. We believe that developing more efficient algorithms for well-clustered graphs is a very meaningful direction for future work.
Finally, our experimental results indicate that the Average Linkage algorithm performs extremely well on all instances, when compared to PruneMerge and Linkage++, This leads to the open question whether Average Linkage achieves an O(1 ((1))=ppoxximation for well-clustered graphs, although it fails achieve O(1 aaproxxmmatio for general graphs (IT]. In our point of view, the answer to this question could help us design more efficient algorithms for hierarchical clustering that not only work practice, but also have rigorous theoretical guarantees.
'Such choice of p2 is to compensate for the small size of cluster Ps, and this ensures that the outer conductance (C'ss) is low.
'Due to the very large size of this data set, we consider only a subset consisting of "comp. "romp.graphics", wom.p.os.ss-ooe ms wiswwwddwss.mie" rcomp.sys.ibm, hc.ap.cccarrwaeee "comp.sys.me hardware.
"comp.os
"rec.sporthockey"..
10

---

Acknowledgements
Bogdan Manghiue is supported by an EPSRC Doctoral Training Studentship (EP/R513209/1), and He Sun is supported by an EPSRC Early Career Fellowship (EP/T00729X/1),
References
[1] UCI ML Repository. https://arrchive.ics...... uci.
Accessed: 2021-
05-22.
[2] Amir Abboud, Vincent Cohen-Addad, and Hussein Houdrouge. Subquadratic high-dimensional hierarchical clustering. In 33rd Advances Neurul Information Processing Systems (NeurIPS' 19), pages 11576-11586, 2019.
[3] Noga Alon, Yossi Azar, and Danny Vainstein. Hierarchical clustering: 0.585 revenue ap- proximation. 33rd Annual Conference on Learning Theory (COLT'20), pages 153-162, 2020.
[4] Sanjeev Arora, Boaz Barak, and David Steurer. Subexponential algorithms for unique games and related problems. Journal of the ACM, 62(5), November 2015.
[5] Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, and Nisheeth K. Vishnoi. Unique games on expanding constraint graphs are easy: extended abstract. In 40th Annual ACM Symposium on Theory of Computing (STOC"08), pages 21-28, 2008
[6] Moses Charikar and Vaggos Chatziafratis. Approximate hierarchical clustering via sparsest cut and spreading metrics. In 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA' 17), pages 841-854, 2017.
[7] Moses Charikar, Vaggos Chatziafratis, and Rad Niazadeh. Hierarchical clustering better than average-linkage. In 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 19), pages 2291-23044 2019.
[8] Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh, and Grigory Yaroslavtsev. Hierarchical clustering for Euclidean data. In 22nd International Conference on Artificial Intelligence and Statistics (AISTATS' 19),, pages 2721-2730, 2019.
[9] Vaggos Chatziafratis, Grigory Yaroslavtsev, Euiwoong Lee, Konstantin Makarychev, Sara Ahmadian, Alessandro Epasto, and Mohammad Mahdian. Bisect and conquer: Hierarchical clustering via max-uncut bisection. In 23rd International Conference on Artificial Intelligence and Statistics (AISTATS' 20), pages 3121-3132, 2020.
[10] Vincent Cohen-Addad, Varun Kanade, and Frederik Mallmann-Trenn. Hierarchical clus- tering beyond the worst-case. In 31 Advances in Neural Information Processing Systems (NeurIPS' ( pages 6201-6209. 2017.
[11] Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Treen,, and Claire Mathieu. Hi- erarchical clustering: Objective functions and algorithms. Journal of the ACM, 66(4):1-42,
2019.
[12] Sanjoy Dasgupta. A cost function for similarity-based hierarchical clustering. In 48th Annual ACM Symposium on Theory of Computing (STOC' 16), pages 118-127, 2016.
[13] Shayan Oveis Gharan and Luca Trevisan. Partitioning into expanders. In 25th Annual ACM- SIAM Symposium on Discrete Algorithms (SODA' /4), pages 1256-1266, 2014.
[14] Shlomo Hoory. Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 4364))439-561, 2006.
[15] Ravi Kannan, Santosh S. Vempala, and Adrian Vetta. On clusterings: Good, bad and spectral. Journal of the ACM, 51(3):997-55,, 2004.
[16] Alexandra Kolla. Spectral algorithms for unique games. 25th Conference on Computational Complexity (CCC'10), pages 122-130, 2010.

---

[17] James R. Lee. Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher-order cheeger inequalities. Journal of the ACM, 61(6))37:1-37:30, 2014.
[18] Huan Li, He Sun, and Luca Zanetti. Hermitian Laplacians and a Cheeger inequality for the Max-2-Lin problem. In 27th Annual European Symposium on Algorithms (ESA' (ESA' pages 71:1-71:14, 2019.
[19] Aditya Krishna Menon, Anand Rajagopalan, Baris Sumengen, Gui Citovsky, Qin Cao, and Sanjiv Kumar. Online hierarchical clustering approximations. arXiv: (0tiv:/909.0000 1909.09667, 2019.
[20] Benjamin Moseley and Joshua Wang. Approximation bounds for hierarchical clustering: Average linkage, bisecting k-means, and local search. In 31st Advances in Neural Information Processing Systems (NeurIPS'17), 17), pages 3094-3103, 2017.
[21] Andrew Ng. Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and algorithm. In 15th Advances in Neural Information Processing Systems (NeurIPS(2)) pages 849-856 2002.
[22] Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 222885-22830, 2011.
[23] Richard Peng, He Sun, and Luca Zanetti. Partitioning well-clustered graphs: Spectral clustering works! SIAM Journal on Computing, 46(2):710-743, 2017.
[24] Aurko Roy and Sebastian Pokutta. Hierarchical clustering via spreading metrics. The Journal of Machine Learning Research, 1871):3077-311, 2017.
[25] Danny Vainstein, Vaggos Chatziafratis, Gui Citovsky, Anand Rajagopalan, Mohammad Mah- dian, and Yossi Azar. Hierarchical clustering via sketches and hierarchical correlation clustering. In 24th International Conference on Artificial Intelligence and Statistics (AISTATS' pages 559-567, 2021.
[26] Ulrike von Luxburg. A tutorial spectral clustering. Statisties and Computing, 17(4):395-416. 2007.
[27] Zeyuan Allen Zhu, Silvio Lattanzi, and Vahab S. Mirrokni. A local algorithm for finding well-connected clusters. 30th International Conference on Machine Learning (ICML' 13), pages 396-404, 2013.
12


Reviews:
[{"review_id": "vmpqcRRdGXQ", "reviewer": "Reviewer_sgob", "summary": "The authors study the important problem of clustering graph in a hierarchical way optimizing and present novel algorithms for the special case of graphs with expender structure or well clusterable graphs, The algorithms have state of the art approximation for such cases and in practice are implementable. The experimental evidence that the algorithms are in line with other baselins in synthetic graphs, and on real data have better performance than some theoretical algorithm (but worse than simple baselines like average linkage).", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "\nThe authors study the important problem of clustering graph in a hierarchical way optimizing an objective function introduced by Dasgupta [13] .\nThe authors study the problem under the assumption that the graph is well clusterable, in particular that it has high conductance (O(1)) this means that the graph is an expander and has no sparse cut separating two parts of the graph. Under this assumption they show a very fast near linear algorithm constant factor algorithm (while state of the art algorithm have logarithmic approximation and use complex poly time subroutines). Then they generalize this to well clustered graphs going beyond the stochastic block model to arbitrary graphs with this property.\n\nMoreover the paper is complemented with an empirical analysis. \n\nThe first structural observation is that if the graph has constant conductance and constant ratio of min max degree any tree is a constant approx solution. Then they introduce an algorithm which simply sorts nodes by degree and builds a tree balancing the nodes in order. Surprisingly this algorithm is a O(1/poly(conductance)) approximate despite being oblivious to the structure of the graph. \nThis suggests to me that getting a constant approximate hierarchical clustering of such graphs (despite the theoretical interest( is not an practically interesting result and as such the algorithm is not practically useful (expect as a building block).\nThen they adapt their algorithm to well clustered graphs using results from Trevisan et al. on finding sparse cuts. The algorithm is non trivial,\n\nThen they provide an empirical evaluation of their algorithm against standard heuristic baselines for HC and some algorithms with theoretical guarantees for special cases of the HC problem.  First they compare on synthetic SBM data where the performance ties with state of the art. On other synthetic data with multiple densities they improve over some baselines but the performance is tied with average linkage. Finally on real data their performance is better than some state off the art method (for HC in some objective and setting) but worse than the baselines of Average and complete linkage. \n\n\nMinor:\nvery interesting theoretical fact, -> perhaps just interesting.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "All in all the paper is technically interesting but the experimental evidence shows that it does not improve over simple baseline algorithms like average and complete linkage this may suggest that the perhaps the assumption of well-clusterability is not practically useful in this problem on real data. \n", "review_text": "", "extra_scores": {"ethical_concerns": "none", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "k0TWnJdblq", "reviewer": "Reviewer_Wup3", "summary": "The paper studies the problem of finding a good hierarchical clustering with respect to Dasgupta's objective function.\n\nIn particular, it gives algorithms that achieve constant-factor approximation for:\na) graphs that have good expansion properties\nb) well-clusterable graphs, that is graphs that can be naturally clustered into sets of good expansion\n\nThese results are in contrast to known hardness results which rule out constant factor approximation under rather natural assumptions. Also, the algorithm generalizes an earlier result, which assumed much stronger properties of the input graph.\nThe paper also evaluates the new algorithm empirically, comparing it to a few existing baselines.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "## Strengths\n\n* The paper  broadens our understanding of the Dasgupta objective, and for this reason I consider it an important contribution to the area of hierarchical clustering. For example, the algorithm presented in the paper for the 'expander' case only uses the node degrees. \n* I find the theoretical contribution highly nontrivial. On one hand, the fact that good expansion implies that the problem is tractable is not surprising (at least to me). However, turning this into an algorithm that also works in the case of clusterable graphs takes some highly nontrivial technical work.\n* The paper is well-written and generally clear.\n\n## Weaknesses\n* The empirical evaluation says the algorithm improves upon \"state-of-the-art\", but I think this may be misleading, as the algorithm from the paper is typically outperformed by average-linkage clustering. I think the paper should comment on this and try to analyze the phenomenon, instead of ignoring the issue entirely.\n* The result is unsurprising, in the sense that it's expected that by assuming stronger conditions on the input, one can obtain a better approximation guarantees. Still, making this idea work looks like solid piece of work.\n\n## Specific comments\n\n* Line 27: Is some word missing between 'is' and 'with'?\n* Line 68: O(1 + o(1)) can be simplified to O(1). Do you mean O(1) or 1+o(1)?\n* line 153: I think that condition (2) is redundant, as it is implied by condition (3)\n* Lemma 4.1: Is \\ell a parameter or something that the algorithm computes?\n\n## Questions for authors\n* Please analyze the empirical results taking average linkage into account, and be open about what it shows and what it does not. The analyzed algorithm is theoretical in nature, and I highly doubt one can show this can be a competitive method in practice. One approach would be to focus on comparison to the previous theoretical algorithm, include hierarchical stochastic block model in the studied datasets, and comment that average/single linkage are only added for reference. Right now, the writing in the empirical section is highly misleading to me, i.e., suggests the proposed method *is* competitive in practice, which, in my understanding, is contradicted by the pictures.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "gn7LbaGxIbx", "reviewer": "Reviewer_64iM", "summary": "This paper studies the cost function introduced by Dasgupta [13] and present polynomial-time approximation algorithms for well-clustered graphs. The well-clusterable assumptions mostly include an underlying structure of a fixed number of clusters, such that the subgraph induced by each cluster has high conductance, yet the cut between the clusters are sparse. The algorithm design bypasses the popular sparsest-cut subroutine, which was first proposed in Dasgupta [13] and often used by the community when studying this particular objective. The result is also more general than the state-of-the-art constant approximation results for this objective. The proposed algorithm also turns out to have reasonable performance empirically.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Overall I think this is a solid theory paper. Roughly speaking, the technical part of the paper is structured as follows:\n- It starts with a discussion on graphs with high conductance. Such a graph can be though of as one single cluster for which there might not be a reasonable cut. With a motivating example (Figure 1), the authors proposed to group vertices of similar degrees first to reduce the hierarchical clustering cost.\n- On such a graph, the authors designs Algorithm 1 which constructs the hierarchical clustering tree based on degrees, and proves it is a constant approximation by moving vertices around in the HC tree and slightly modifying the HC tree step by step. Such movements of vertices are centered around a \"dense branch\" which is a path in the HC tree, where the internal nodes represent clusters whose sizes are bigger than their siblings.\n- The paper then considers a well-clustered graph which is composed of a given number of such high-conductance subgraphs (clusters), where the inter-cluster edges are more sparse than intra-cluster edges.\n\nOriginality: The paper contains novel ideas for performing theoretical analysis on HC algorithms and in particular for Dasgupta's objective. Some of the techniques used in the paper, including focusing on the \"dense branch\" and reconstructing trees by slighly modifying some of the branches, were also adopted by previous work, but this paper carefully managed to put them to good use, and, has found a nice breakthrough for HC-related theory, in my opinion. Analysis for Dasgupta's objective function often comes hand in hand with finding sparsest-cut, and the methods proposed in this paper at least offered a different perspective.\n\nThe submission seems to be technically sound. The writing quality is good. The underlying algorithms are quite complicated but the authors were able to at least convey the main ideas. In particular, they have motived the assumptions and the algorithm design very well.\n\nSignificance: The paper's main contributions are theoretical. Assuming it is correct, it adds to the community's understanding of HC objective functions and may contain some new tools that can be used for studying Dasgupta's objective. Emprically, the algorithm is on par with other algorithms developed in previous work. It does not outperform the most widey used HC algorithms yet, but the results may still enlighten us.\n\nMinor Comments:\n- In Algorithm 1, by definition, for some |V| values r could be very close to |V|? For example if |V| = 2^m + 1, does it mean r = |V| - 1? It seems a bit unusual then, since the algorithm splits off one point. I wasn't able to check the details due to time limits, but maybe the authors can share some intuition about why this is fine?\n- The intuition behind the algorithm is to group vertices of similar degrees first, which is also a bit non-intuitive, as I cannot really tell why it might give good HC trees at the high level. It might work in this context, but I wonder whether it is easily extendable.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations. The potential negative societal impact of their work was marked as N/A.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hrs"}, "extra_text": {}}, {"review_id": "EEPGAqNaveH", "reviewer": "Reviewer_TUMr", "summary": "Dasgupta's is a popular objective for hierarchical clustering. Given graph of similarities (weights w_uv), find the smallest subtree T_uv containing both u and v. The objective is \\sum w_uv |T_uv|.\n\nThis can be optimized to within \\sqrt \\log n approximation, and constant factor is thought to be hard to achieve in general. There are recent work showing that this goal is possible for special graphs.\n\nCohen-Addad et al. present 1+o(1) approximation for a hierarchical generalization of SBM. This work takes a different perspective and looks at well-clusterable graphs in terms of conductance: There exists a partition V_i of the vertices into k parts such that (1) the subgraph induced on each V_i has large (\"inner\") conductance, and (2) each V_i has low (\"outer\") conductance. They show that one can get approximations depending on K and the conductance bounds. In particular, this gives const factors for expanders in the case of small k.\n\nFirst they have a simple lemma with an upper bound for cost of any hierarchy in terms of conductance and degree distribution (ratio of d_max over d_avg and ratio of d_avg over d_min). This already gives const factor for const-degree expanders. Planting a large clique makes the bound polynomial, though there is a simple solution with small cost. They present a very simple algorithm (basically by sorting according to degree and recursively splitting the tree almost equally) which gives const factor for expanders.\n\nNext they move to well-clusterable graphs, and show that Gharan-Trevisan decomposition is not sufficient, as simply joining the clusters in a tree may not work to get a good value for the objective (due to high cut values). Instead, they augment the decomposition theorem to identify a set of \"critical nodes\" with potentially high cut values. Then they break some of the clusters (more precisely, the greedily built trees for clusters) at those points, and finally merge everything into one tree by means of their degree-sorting algorithm.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Clustering well-clusterable graphs is a top topic, and this work certainly adds to the literature. The algorithms and theoretical bounds are not very practical, though. The gains in practice are small.\n\nThe paper is easy to read despite the heavy math.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not really", "review_text": "", "extra_scores": {"ethical_concerns": "I don't think so", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present a new hierarchical algorithm to cluster graphs. The main result showed in the paper is that the new algorithm returns a constant approximation for a well-clustered graph. The paper is a clear extension of previous work in NeurIPS and it presents interesting theoretical results. One shortcoming of the current write-up is that the proposed algorithm does not have great experimental performances. Overall, the paper is interesting and proposes some novel ideas and it will be a nice contribution to NeurIPS.

Decision: Accept (Poster)