On the cohesion and separability of average-link for hierarchical agglomerative clustering
Authors: Eduardo Sany Laber
Miguel A. Batista
Venue: NeurIPS 2024 poster (2024)
Keywords: hierarchical clustering
approximation algorithms
average-linkage
complete-link
single-link
linkage-methods
agglomerative mthods
Primary area: optimization

Abstract: Average-link is widely recognized as one of the most popular and effective methods for building hierarchical agglomerative clustering. The available theoretical analyses show that this method has a much better approximation than other popular heuristics, as single-linkage and complete-linkage, regarding variants of Dasgupta's cost function [STOC 2016]. However, these analyses do not separate average-link from a random hierarchy and they are not appealing for metric spaces since every hierarchical clustering has a $1/2$  approximation with regard to the variant of Dasgupta's function
that is employed for dissimilarity measures [Moseley and Yang 2020]. In this paper, we present a comprehensive study of the performance of \avglink \, in metric spaces, regarding several natural criteria that capture separability and cohesion, and are more interpretable than Dasgupta's cost function and its variants.  We also present experimental results with real datasets that, together with our theoretical analyses, suggest that average-link is a better choice than other related methods when both cohesion and separability are important goals.

On the cohesion and separability of average-link for hierarchical agglomerative clustering
Eduardo S. Laber Departmento de Informática, PUC-RIO laberdinf, puc-rio. br
Miguel Batista Departmento de Informática, PUC-RIO miguel220500@gmai1. com
Abstract
Average-link is widely recognized one of the most popular and effective meth- ods for building hierarchical agglomerative clustering. The available theoretical analyses show that this method has much better approximation than other popular heuristics, as single-linkage and complete-linkage regarding variants of Dasgupta's s cost function [STOC 2016]. However, these analyses do not separate average-link from random hierarchy and they are not appealing for metric spaces since every hierarchical clustering has 1 approximation with regard to the variant of Das- gupta's function that is employed for dissimilarity measures [Moseley and Yang 2020]. In this paper, present comprehensive study of the performance of average-link in metric spaces, regarding several natural criteria that capture separability and cohesion, and more interpretable than Dasgupta's cost fune- tion and its variants. We also present experimental results with real datasets that, together with our theoretical analyses, suggest that average- link is better choice than other related methods when both cohesion and separability are important goals.
Introduction
Clustering is the task of partitioning of objects/points that similar ones are grouped together while dissimilar ones are put in different groups. Clustering methods are widely used for exploratory analysis and for reducing the computational resources required handle large datasets.
Hicrarchical clustering is an important class of clustering methods. Given a set X n points, a hierarchical clustering a sequence of clusterings (C", Cn-1 ..... C²), where C is a clustering with n unitary clusters, each of them corresponding to point in X, and the clustering C with i n, is obtained from C++1 by replacing two of its clusters with their union A'. A hierarchical clustering induces a strictly binary tree with n leaves, where each leaf corresponds to point in X' and the ith internal node, with i n, is associated with the cluster A"; the points in A' correspond to the leaves of the subtree rooted in A'. Hicrarchical clustering methods are often taught in data science/ML courses, implemented in many machine learning libraries, such scipy. and have applications in different fields as evolution studies via phylogenetic trees [Hisen et al. 1998). finance (Tumminello al. 2010 and detection of closely related entities [Kobren al. 2017 Monath et al. 2021].
Average-link widely considered one the most effective hierarchical clustering algorithms. belongs to the class of agglomerative methods, that is, methods that start with set of n clusters, corresponding to the n input points, and iteratively use linkage rule to merge two clusters. Due to its relevance,
find some recent works dedicated to improving average-lime efficiency and scalability (Yu et al., [021] Dhulipala et al. [202 2022 2023 as well as recent theoretical work that
try to understand its success in practice Addad et al. 2019 Charikar et al.. 2019a Moseley
and Wang 2023 Charikar et al. 2019b).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Most of the available theoretical works give approximation bounds for average-ling -link regarding the cost function introduced by [Dasgupta 2016] well for some variants of it. Let be the tree induced by hierarchical clustering. Dasgupta's cost function and its variation for dissimilarities considered in [Cohen- Addad al. 2019 are, respectively, given by
Dasg(D)
sim(a, b) [D 6)] and CKMM (D) a.
diss(a, 6) ( b)], a.bE
E
(I)
where sim(a, b) (diss(a, b)) is the similarity (dissimilarity) of points a and 4; D(a, b) is the subtree of 'D rooted at the least common ancestor of the leaves corresponding the number of leaves in D(a, b). In general, the existing results show that average-link achieves constant approximation for variants Dasgupta's 's functtinn while other linkage methods do not.
and b, and [[ b)l is
However, there is significant room for further analysis due to the following reasons. First, Das- gupta's cost function, despite its nice properties, is less interpretable than traditional cost functions that measure compactness and separability. Second, although the analyses based on Dasg and its variants allow to separate everage-ling -lnnk from other linkage methods as single-linken complete- sate-linkage in terms of approximation, they do not separate average eerragee-lin 1ink from a random hierarchy [Cohen-Addad al.) 2019 Moseley and Wang 2023 Charikar et al. 2019b) Moreover, for the case in which the points lie a metric space every hierarchical clustering has 1/2 approximation for the maximization of CKMM (Wang and Moseley 2020), this cost function is less appealing in this relevant setting. Finally, to the best of our knowledge, Dasg does not reveal how good are the clusters generated for specific range of k. As an example, small are important for exploratory analysis while large k is important for de-duplication tasks [Kobren et al. 2017).
and
1.1 Our results
Motivated by this scenario, present comprehensive study of the performance of average-ling in metric spaces, with regards to several natural criteria that capture separability and cohesion of clustering. In nutshell, these results, explained below, show that average link has much better global properties than other popular heuristics when these two important goals are taken into account.
Let (X, dist) be metric space, where X' is set of n points. The diameter diam(S) of set of points is given by diam(S)) max/diis((ar y) E S}. For a cluster A and for two clusters A and B, let
aAg(A)
1
Σ x.EEΛ
dist(x.8) y) and avg(A, [A]
Σ
Σ SEAVEB
dist(r, (x
(IAI)
B
Let C = (Ci,..., Ck) be a k-clustering for (X' dist). To study separability we consider the average (separ) and the minimum (sepnin) avg among clusters in C, that is,
sepav (C) =
CC, Cj) and sepain = min C,),, (P)
On the other hand, for studying cohesion, we consider the maximum diameter (max-diam) and the maximum average pairwise distance (max-avg) of the clusters in C. In formulae,
max-diam(C) ==
< S k} and max-avg(C) = max max < i k}
We also study natural optimization goals that capture both the scparability and the cohesion of clustering. We define the cs-ration and cs-ratiops of clustering C
cs-ratiowy(C == max-avg(C) and cs-ratiopw(C) = max-diam(C) (C)
(4)
sepain (C)
sepnin(C)
Let A be k-clustering produced by average-link. We first prove through a simple inductive argument that cs-ratiow (A**) < This result does not assume that the points in lie in a metric
space and it is tight in the sense that there are instances in which cs-ratiowy() for every

---

k-clustering C. For the related cs-ratiopn criterion, we present a more involved analysis which shows that cs-ratiouw44") as well as the approximation of average- link regarding OPT (the minimum possible cs-ration) are O(lg n:;; these bounds are nearly tight since there exists an instance for which cs-ratiop (A*) and ce-ratioon (A*) /OPT are S2 log
log = ). Both cs-ration and cs cs-ratiop: allow an exponential separation between average- -ink and other linkage methods, as single- sangle-linkage linkage and complete- -inkkge. Interestingly, in contrast to CKMM (Eq. DT our criteria also allow very clear separation between average- and the clustering induced by a random hierarchy.
Next, we focus separability criteria. Let SPT (k) be the maximum possible верav of k-clustering for dist). We show that separ(A')) at least (PTmp(k) kn and that this result is nearly tight. Furthermore, we argue that any hierarchical clustering algorithm that has bounded approximation regarding max-diam or max-avg does not have approximation better than 1/k to sepav. Regarding single-linkage
and complete -innkae, we present instances that show that their approximation with respect to sepav are exponentially worse than that of average-link, for the relevant case that & is small.
We also investigate the cohesion of average-link. For a keclustering C, let aug-diam be the average diameter of the k clusters in C. Let (r) and (P) be, respectively, the min- imum possible max-diam am and avg-diam of a k-clustering for (A', dist). We prove that for all k, max-diammA' I min(k; 1 + 4 In b.l.o, OOPT.v(k stance given by Theorem 3.4 of (Dasgupta and Laber 2024] allow to separate average-link from single-linken max-diammA' is 2(k (k)), which is, to the best of our knowledge, the first lower bound on the maximum diameter of average-link.
This result together with the in-
in terms of approximation, when & is 2(log241 n)). We also show that
Finally, to complement our study, we present some experiments with 10 real datasets in which evaluate, to some extent, if our theoretical results line up with what is observed in practice. These experiments conform with our theoretical results since they also suggest that average performs better than other related methods when both cohesion and separability are taken into account.
1.2 Related work
There is a vast literature about hierarchical agglomerative clustering methods. Here, we focus on works that provide provable guarantees for average-ling -innk and some other well-known linkage methods.
Average-link. There are works that present bounds on the approximation of average-link re-
garding some criteria [Cohen-Adee Addad et al.] 2019 Charikar et al., 2019b Moseley and Wang 2023 Dasgupta and Laber 2024]. All these works but [Dasgupta and Laber [002]] analyse the approximation of average- link regarding variants of Dasgupta's s cost function. [Moseley and Wang 2023) assumes that the proximity between the points in X' is given by a similarity matrix. They show that average- link is 1/3-approximation with respect the "dual" Dasgupta's 's cost function. [Cohen-Addad et al.) 2019], as in our work, assumes that the proximity between points in X is given by dissimilarity measure and shows that average-
has 2/3 approximation for the problem of maximizing CKMM (Eq. D. CCarrikar et al. 2019b show that these approximation ratio for average- are tight. These papers also show that a random hierarchy obtained by a divisive heuristic that randomly splits the set of points in each cluster matches the 1/3 3 and 2/3 bounds.
Dasgupta and Laber 2024 presents interesting approach to derive upper bounds on cohesion criteria for a certain class of linkage methods that includes average-link They show that avg( A) < OP. (k) for every cluster A E AA. Our bound on the maximum diameter of a cluster in Ah incurs extra factor of min (k, + 4 Inn to this bound and its proof combines their approach with some new ideas/analyses.
Other Linkage Methods. There are also works that give bounds on the diameter of the clus- tering built by complete- linkage and single-linkage on metric spaces (Dasgupta and Long] 2005 Ackermann et al., 2010 Großwendt and Röglin 2015 Arutyunova et al. 2023 Dasgupta and Laber] [024]. Let and S be the k-clustering built by these methods, respec-
lively. Arutyunova et al. 2023 shows that max-diam(C) is 2(AOPT (k)) while [Dasgupta

---

and Laber 2024] shows that max-diam( is (min
10 OPT (k), 1.9 OP (k))) Regard-
ing single-- -inkaag. max- max-diam(S) (kOOPT kk) Dasgupta and Long 2005
Arutyunoval
et al. 2023] and (A (k)) [Dasgupta and Laber 2024]. Ackermann et al. 2010
GroBwendi
and Röglin 2015] give bounds for the case in which dist is the Fuclidean metric.
In terms of separability criteria, it is well known that single- Maingee-innaae linkage maximizes the minimum spacing of clustering [Kleinberg and Tardos 2006][ 4.7J. Recentl, [Laber and Murtinho 2023] observed that also maximizes the cost of the minimum spanning tree spacing, a stronger criterion. These criteria, in contrast to ours, just take into account the minimum distance between points in different clusters and then they can be significantly impacted by noise.
Grrowwnnd et al. 2019 shows that Ward's method gives 2- 2-approximation for k-means when the optimal clusters are sela-separated.
Preliminaries
Algorithm| 2 shows a pseudo-code for average-link. The function dist B) at line that measures the distance between clusters A and B is given by
distal(A.B)
Σ Σ DE bEB
dist(a,
|
single-linkage and complete-linkage obtained by replacing distar, in Algo- (a, E A x B} and dAstci(A, B) max m dast(aa (a, b) A x B}, respectively.
rithm _ with (As B) == bi
Algorithm 2 Average Link
I: A" clustering with unitary clusters, each one containing point of X down
2: For
(A, B) clusters A for which (A, B) is minimum
4: A - (A} (AUU
version of the triangle inequality for averages will be employed a number of times in our analyses. Its proof can be found in Section A
Proposition 2.1 (Triangle Inequality for averages). Let A, B and C be three clusters. Then,
avg(A, S avg(A, B) + avg(B, O).
For two disjoint clusters A and B, the following identity holds
(1 (1A|+1BI) ( av avg(AUBB = (1a1) (vg(A) (lvg B) +
(1 avg( B).
Dividing both sides by (111+111)), avg(A), avg(B) and avg(A, B). fact will be used couple of times in analyses.
conclude that avg(A U B) is convex combination of
The following notation will be used throughout the text. We use Н1 Σ 1 denote the pth harmonic number and & refer to the k-clustering obtained by average-link for the instance under consideration, which will always be clear from the context.
3 Cohesion and separability
In this section, we analyze the performance of average-link with respect to both cs-ratiow and cs-ratiow (Eq. 4. criteria that simultaneously take into account the separability and the cohesion of clustering. Morcover, contrast its performance with that achieved by other linkage methods.

---

3.1 The cs-ratiow criterion
We first show that cs-ratioN I 1. The proof of this result can be found in Section B.1 it uses induction on the number of iterations of average-link together with fairly simple case analysis. Theorem 3.1. Let A be k-clustering built by average-link Then, for every k. cs-ratiow (A**) 1.
We note that the above result does not assume the triangle inequality and it is tight in the sense that for the instance (X, dist), in which the points of X have pairwise distance 1, every clustering has cs-ration equal to 1.
In Section B.2
we present instances which show that cs-ratiow can be (2)), ((vn) and un- bounded terms of n for single-linkage tively. Interestingly, all the k-clustering, with 2 < l & n/2, induced by the hierarchical clustering ob- tained by these methods satisfy these bounds. Furthermore, since cs-rationn(C) 2 cs-rationy (C) for every clustering C, these bounds also hold for the cs-ratiow criterion.
and a random hierarchy, respec-
A natural question that arises is whether average- meenkee-link has "good" approximation with respect cs-ratioay. Unfortunately, the answer is no. In fact, in Section [B. we show an instance where the approximation unbounded terms of n. However, we show in the next section, average- has a logarithmic approximation with respect to cs-ratiopn.
3.2 The cs-ratiops criterion
We analyze the cs-ratiopr of average-link. The results of this section will have an important role the analysis of both the separability and cohesion of average-ling presented further.
First, we show that for every cluster X in AA, the average distance of a point & E X to the other points X -x is at most a logarithmic factor of the average distance between any two clusters Y and Z. The proof can be found in Section B.5 Let T:-1 be the cluster that contains x before the ith merge involving and let S. be the cluster that is merged with T;-1- We prove by induction that avg(æ; T; x) I In Hi:: - -jvgg(Y (Y; Z), which implies on the desired result because T, = X for some f. To establish the induction, we use the triangle inequality to write avg(x, Ti - x) as function of both avg(æ, T: -3 I)) and avg(?; S.). and also argue that avg(T;-1,, St) S avg(X,Y).
Lemma 3.2. Let X, Y and Z, with X 2 2 and Y * Z, be clusters of A Then, for every & E X, have that avg( (x, X) avg(æ, X x) aavg- Z).
The next result is simple consequence of the previous one.
Theorem 3.3. Let h 2 2 and let X, Y and Z, with Y * Z. be clusters of a k-clustering built by average-limg Then, diam s aavg
Proof. If |X| 1 the result holds because di tiam(X) (X) = 0. Thus, assume that |X] 1. Let z and x' be such that dist(x,, x²) = diam (X). We have that
dist(x,x') < avg(æ, X) avg(X, < 2 Z)
where the first inequality follows from the triangle inequality and the second one due to Lemma
The next theorem shows that cs-ration (A*) < 2H,, and that average-link has logarithmic ap- proximation for the cs-ratiopp criterion. The first upper bound a simple consequence of Theorem Let OPT be the minimum possible cs-ratiops. To prove the bound on the approximation consider two cases. OPT Z 1/3 the result holds because ce-ratiom(A4* < 2 Inn < 6OPT n. OPT < 1/3, we argue that the clusters in the optimal clustering are "well separated" and, hence, average-link link builds the optimal clustering.
3.3
Theorem 3.4. For all k the k-clustering A built by average- -ink satisfies (A*)) S 2H,,. Furthermore, for all k, ca-ratiow (A*t) is Ologg)) OPT where OPT is cs-ratiow of the k k-clustering with minimum possible cs-ratiopy.
5

---

Proof. The inequality cs-ratioax(4") I 2H,, is obtained by using Theorem 3.3 with X being the cluster with the largest diameter in A and Y and Z being the clusters in A that satisfy avg(Y, 2) = se
Now we prove that A has logarithmic approximation. If OPT 2 1/3, then cs-ratioor(4*) 1 2H, I 60PTH, and, hence, the desired result holds.
Thus, we assume OPT < 1/3, Let (k) be a k-clustering that satisfies (C*))ttoo(((((kk)))) OPT. The following claim will be useful.
Claim 1. Let C, C' be two clusters (k) and let a, be two closest points in C and C', that is, dist(a, b) min(dist(r, v)) v) E C' C"}. Thus, dist(a, b) > max mnxx(dim((C) diam (")).
Proof of the claim. We assume w.l.o.g. that diam (C) > diam(C"). For the sake of reaching contradiction, assume that dist(a, b) I diam(C'). Then, it follows from the triangle inequality that the maximum distance between point in C' and C' is at most 3diam( Thus, sepain (C* (k)) s avg(C. (C, C") v 3diam C*) and so cs-rations (C* (k)) 2 (iam(C)/ /C)/3diamll /ddammma)))) = 1/3, which contra-
diets assumption. N.
Now, we argue that average-link constructs the clustering C* (I)) when cs-rati (ow so its approximation is in this case. For the sake of reaching a contradiction, let us assume A o C* (k)... Hence, at some iteration average-link merges two clusters, say and B, that satisfy the following properties: A C C and B C C", where C' and C' are two different clusters in C* (k). Let & be the first iteration of average- when it occurs.
(C* (k:) < 1/3,
Case 1) A C C or B C C². Let us assume w.l.o.g. that A C C. In this case, there is a cluster A'' the beginning of iteration such that A' U CC We have that avg(A, A') S diam (C) and by the above claim the minimum distance between A and B is larger than max max/diam{ (C)) diam("" ddam((")) z avg(A A'), which contradicts the choice of
Thus, avg(A, A, B) > max(diam everage-link.
Case 2) A = C and B C", If = 2 we are done. Otherwise, there exists cluster C" E (k) and two clusters X and Y at the beginning of iteration / such that X UU C C", Thus, it follows from the condition OPT < 1/3 that avg(X,Y) Y) S diam(C") < $ (k)) S (avg(C, C*) avg(C, C"), which again contradicts the choice of average- link.
is noteworthy that, in contrast to Theorem 3.T. the assumption that the points lie a metric space is necessary to prove Theorem 3.4 In Section B.4 we present instance that supports this observation.
Now, we present an instance, denoted by ICS that shows that the above results are nearly tight. This instance with small modifications will also be used to investigate the tightness of our results regarding the separability (Section 4 and the cohesion (Section 5 of average-
We note that in most of the instances presented here, including I will have more than one possible execution for the methods we analyze. In these cases, we will always consider the execution that more suitable for our purposes. These multiple executions can be avoided at the price of more complicated descriptions that involve the addition of small values e to the distance or points to break ties.
Moreover, let Ao be set containing a single point located at position Po in the real line and A,, for 0 < i < - 1, be a set of (a + 1)! points that are located at position p. of the real line. We define By = Ao and B = B; U U, for
Let f be an integer that satisfies !! nı; note that t 22( log
log log 11
i 2 1. Set PO= = 0, P1 = and, for > 1. P. = Pi-1 + avg(A,-1, Bt- The set of points for our instance I
is B 1 and the distance between a point in A, and point in Aj is lp. pjl. The following lemma gives properties of TCS and, in particular, how average- link behaves on it.
Lemma 3.5. Fori i 2 O, we have that [Ba] = (i+1)! and 2 2, we have diam Bi = - i(i-1)/2. avg B;, A;-1) 1)= = i+1 I and pj i(i 1)/2. Furthermore, for k < I, average-lind obtains the k-clustering A = (B.-k. Ar-kt 1)) and, in particular, for k = 2 it obtains the clustering
A (B,-2, A(-1).
From Lemma 3.5 we have that sepain(A") = avg(Br-2 Ac-1) = + and diam (Ba))) = t(t-1)
1(t - 1)/2, so cs-rationn
which is 12( 2(1+T)
log n log log m

---

Furthermore, for the clustering A' = -AA,, B - Ao) we have that
A4-11
[ (t
t!
1)1
(t 1)2
sepnin(A') = Ao, Bi-1 - AA) 2 B
avg(Ao: Ac-1)
Pt-1 =
t!
2
(5)
and max-diam am(')) I diam (B-1) = (t + 1) + 2)/2. Thus, cs-ratioms(A (A') = O(1) and the logarithmic approximation of average-link to cs-rationn is also nearly tight.
4 Separability criteria
In this section, we investigate the separability of average-link, Recall that (k) is the maximum possible sepav of k-clustering for (X, dist). We show that for average- sepav is at least (P] and that this bound is nearly tight. We also show that there are instances in which the sepav of single- single-linkage and complete- Hmplete-linkage linkage are exponentially smaller than that of average-ling link.
k+22mn
Theorem gives an upper bound on sepav for average-link and its complete proof can be found in Section D.2 Here, we give an overview of the proof for the case > 2, which is the most involved one. The proof uses the fact established by Proposition 4.1 that there exists a set of k points P C X' that satisfies avg(P) (P) 2 SET This holds because a set of l randomly selected points that intersect all clusters of k-clustering with maximum sepav satisfies the the desired property (in expectation). Having this result in hands, it is enough to show that avg(P) is O((k + 1
This bound on avg(P) is obtained by relating the distance of each pair of points p.p' E P with the average distance between clusters in Ak. Let / E P and let A and A' be clusters in A² such that p E A and y' E A'. Moreover, let S be cluster in A with S & {A, A'}. From the triangle inequality we have that dist p') = avg(p. p') S avg(p, A) + avg(A. S) a + avg(A', (A'' p'). Then, by bounding both avg(p (p. A) and avg (', p') via Lemma 3.2 with Y and Z satisfying avg(Y, Z) s ) we conclude that dist(p, ('.p') S separ (A*) + (A, ))- avg(S, A'). In general lines, the result is then established by averaging this inequality for all S & (A, A'} and for all p,p' P.
(A
Proposition 4.1. There is a set of points P S. X with the following properties: |P = and PPg(P)= 2 SPT (k).
Theorem 4.2. For every k, the k-clustering A obtained by sherage-link satisfies separ (A*) 2 (A) k+2HH
We present two instances that, together, show that the previous theorem is nearly tight. The first is the
instance I presented right after Theorem 3.4 For ICS the clustering A² = (A,-1, B,-2) built by
average-link satisfies (A?) = avg A,-1, Bx-2) = t + On the other hand, Eq. (5) shows
that sepay (A4' (t-1)² for the clustering A' (Ao; B Ao). Thus, for ICS separ (A2) is
2
O OPT log log
log
Now, we present our second instance, denoted by Z Let k be an odd number and let D and be positive numbers. The set of points of ZZ is given by S₁ U U.2 U Sz, where |S|] = |S2 = (k 1)/2 and Sy- {s,11 < i < k- 2]. We have dist(r, y) = for x, y E S,, dist(r, v) = for N, E S2. dist(x, y) = 1 for x, y E S3 and dist(x, y) = if æ and y are not in the same set.
For I,P,, when D is sufficiently large and e is sufficiently small, AA = (S1, S2, $1,-.., 8k-2) and separ (At) (D/k). On the other hand, the sepav of the k k-clustering that has the cluster Sy and k - singletons corresponding to the points in S₁ U S2 is R(D). Thus, sep (A*) is (OPT (k)
We note that single-linken so the upper bound OPT SE (k)/k /k also holds for them. In Section D.3 we present instances that show that separ is O (k) for both single-linkage and comple Seappleteellie -inkage.
and complete-innkage also obtain the k-clustering A for I
The instance Ieap is particularly interesting because it also shows that natural cohesion and separabil- ity criteria can be conflicting. The key reason is that any method M with bounded approximation
7

---

(in terms of n) regarding max-di am or to max max (Equation 3) has to build the k-clustering .A for I Thus, by analysing I we can conclude that the approximation factor of M sepay is 0 and to sepnin is (1)D)). The details can be found in Section D.4
5 On the cohesion of average-link
In this section, we prove that max-diam(A") (A*) < min(k; + 4 (Inn)41590PP OPTav(k) and we also present an instance which shows that max-diam(AA (A*t) 2 (K).
Dasgupta and Laber 2024 presented an interesting approach to devise upper bounds on cohesion criteria for a class of linkage methods that includes average-link. Although this approach was used to show that the maximum pairwise average distance of cluster in AAt most OPT. (k), cannot be employed,
least directly, to bound the maximum diameter of cluster in A Thus, to
obtain our (1 + 4 In m).k 1- OP (yyk)) bound we combine the results of (Dasgupta and Laber 2024]
with Theorem 3.4 while for the k- OP bound we add some new ideas/analysis on top of
those from Dasgupta and Laber 2024].
The analysis in Dasgupta and Laber 2024 keeps dynamic partition of the clusters produced by the linkage method under consideration. Each group in the partition is a set of clusters denoted by family. A point p belongs to familly F it belongs some cluster in F. Thus, di diam (F) is given by the maximum distance among the points that belong to F. The approach bounds the diameter of each family F as (essentially) function of the clusters that F touches in target k-clustering Te.). The bound on di diam(A (P) is then used to upper bound the diameter of the clusters
T =
in F. For k-clustering C, let avg-diam(C) ;= Σ diam(C)) (C²). As in Dasgupta and Laber 2024 we use as the target clustering the one with minimum avg-diam.
We explain how the families evolve along the execution of a linkage method, in particular average-link. Initially, we have families, ..,..., , FR. where F; is a family that contains [T.] clusters, each one being point from T; Furthermore, the families are organized in directed forest D that initially consists of l isolated nodes, where the ith node corresponds to family F,.
We specify how the families and the forest D are updated when the linkage method merges the clusters g and g' belonging the families F and F`, respectively. Assume w.l.o.g. |P > IF". We have the following cases:
case 1 IF 1 and [F| 1. In this case two new families are created, Fnew F - {g} and Feow' = Ugg}. Moreover, wnew and Ieww' become, respectively, parents of F and F
in D
case F' 1 or F In this case, only one family is created, Fnew := (FUF'U g'h) 9--95 g'. Moreover, Fnew becomes parent of both F and F' in D.
We say that family F is regular if [F| 1.
Proposition 5.1 (Proposition 3.1 of Dasgupta and Laber 20244). ). At the beginning of each iteration of average- -ink at least one of the roots of the forest D corresponds to regular family.
Let M be the class of linkage methods (Algorithm) 2 whose function f, employed measure the distance between clusters A and B satisfies
(dist(a, b) b) E A & I diam(AUB
(6)
Proposition 5.2 (Proposition 5.1 of Dasgupta and Laber (2024] ). The diameter of every regular family F produced along the execution of linkage method in M is al most 3log,3 OP
Note that the function distAr employed by average-link satisfies the condition given by 66) and, thus, the above proposition holds for average-link.
We are ready to establish the main result of this section. Theorem 5.3. Every cluster S in A satisfies diam(S) < min(k, 4 4n n- + 1o 3 Ov
Proof. Let V (T TIS * 0} be the set of clusters of the target clustering T that inter- sect S. We build graph G whose nodes correspond the clusters in V. At the beginning of everage-link' execution, G contains the set of nodes V and no edges.
8

---

At each iteration, there are two possibilities for the clusters and g' that are merged by average-link: (g U')
0 (g U') S S. We define how updated in each case:
Case 1) (gUgg) ns = In this case, G is not updated.
Case 2) (g U') S S. Let and be points in g and g' such that dist(r, y) is minimum and let 7 and 7 be the clusters in T that contain a and y, respectively. We add an edge of weight dist (z; y) between 7 and T We say, in this case, that æ and y are associated with the edge that links 7 to TV.
We need the following two claims:
Claim 2. dist(r, y) klo,, & aV:)
Proof of the claim. Let H be a regular family at the beginning of iteration Such family does exist due to Proposition 5.1 Moreover, let h and h' be two clusters in H. We have that
dist(r, v) < (g.9g) z dist (h, h() diam(h U M² diam(H) < klo OPT (k:,
where the second inequality holds by the choice of average-link and the last inequality holds due the Proposition 5.2
Claim 3. For a cluster C, let Vc == {T E T * 0}. Let S be cluster generated by average-link that subset of Then, when S' created, the subgraph of G induced by Vs connected.
Proof of the claim If |S'| 1 the property holds. Let S' be a cluster obtained by merging S and S2- By induction, the property holds for S1 and Sz. Since an edge is added between nodes in Vs, and Vs, then the property also holds for S.
Thus, at the end of the algorithm. klog, (k)) Let and y be points in S such that dist(r, y) = diam(S) and let T u
is connected and each of its edges has weight at most
U1 = T be path in G from T to T
Consider sequence of points a PIPl ... PEPle y, where and pl are the points in e; associated with the edge 14-10; and 1, respectively. From the triangle inequality
dist(rr y) S Σ (ist(pph P(+1) + Σ dist (ast((p,pl)) p() S (k - O
OPT (k) + Σ diam S
(k: - OP
OPT + kOPT
For the logarithmic bound, let S and S2 be the two clusters that merged to form S. At the beginning of the iteration which S₁ and S2 are merged, (3. that there exists regular family, say H. Let h and h be two clusters in H. By Proposition 5.2 avg(h, h²) I
diam(H) H)) < OOPTaV)) Thus, by Theorem 3.3 diam(Si) < 2n avg(h, (a(hh,, h²) S 2 glog, Av (k) and diam(S2) < 22 Inn- klog, 3OPT.v()) Let 81 E S and $2 E S2 be such that min(dist(p, (ppp)))pppg))))))).).pp)())))))p E S1 S2). Since S₁ and S2 are merged we have that dist(si, 82) < avg(Si, S2) avg(h, h²) < blog (OPTav()))))) Thus, diam(S) < diam(S) dist(s1,82) 82) diam(S;) I + 4 A (K)
dist(s1, 52)
Theorem 3.4 of Dasgupta and Laber 2024
presents an instance with 2k points for which siingg--innkaee builds k-clustering that has cluster whose diameter (PP (+)).. Thus, this result together with Theorem 5.3 show separation between gverage-link and
single-linkage when & is 2(log2.11 n.).
2.41
Our last theoretical result lower bound the maximum diameter of the clustering built by average-link. Its proof can be found in the Section B and it employs an augmented version of instance ICS presented right after Theorem 3.4
Theorem 5.4. There is an instance for which the k-clustering A built by average- -lnn satisfies lax-diam(A") E Q(kOPTpm (k))

---

Table I: Average ratio between the result of a method and the best one for each criterion and each group of The best results are bold-faced
Small
Medium
Large
S
sepain
0,99
0,82
0,76
0,81
0,68
1
0,81
0,72
sepav
0,97
0,82
0,94
0,97
0,9
1
0,98
0,96
max-diam
0,85
1
0,72
0,8
1
0,48
0,76
1
0,38
avg
0,95
0,96
0,86
0,99
0,89
0.71
0,99
0.84
0,67
cs-ratiogn
0,96
0,92
0,63
0,95
0,97
0,4
0,93
0,99
0,33
ca-ration
0,98
0,82
0,69
0,73
0,51
0,68
0,4
6 Experiments
In this final section, briefly present experiment in which evaluate whether average- in addition to having better theoretical bounds, it also has a better performance in practice for the studied criteria. We employed 10 datasets and used the Euclidean metric measure distances. For each of them, we executed average-limg
and single-ie --lieegee, for the k < 10), Medium=(k||/ 4 k S vn 44 and Large=(k:]k = n/i and 2 < i < 10). More details, as well as the results of our experiment with other distances, be found in Section
following sets of values of k: Smal1=(A|2 complete-linkent
Table shows the average ratio between the result of a method and that of the best one, grouped by criterion and set of k. Each entry is the average of 90 ratios (9 k's and 10 datasets) and each of these ratios for a method M is value between 0 and that is obtained by dividing the minimum between the result of M and that of the best method by the maximum between them. The letters A, C and are the initials of the evaluated methods.
Concerning separability criteria, single-linkage and average-link have the best results for sepav- The latter has some advantage when & is small, which is in line with better worst-case bound for small k (results from Section For sepain, average-link has a huge advantage, which not surprising since its linkage rule tries to increase sepain at each step by merging the the clusters A and B for which (Ag(A, B) sepmin(C), where C is the current clustering.
Regarding cohesion criteria, complete-linkage and average-link were the best methods. They had close results for max-avg while for max-diam the former had strong dominance. These results align with ours and those from [Dasgupta and Laber, (2024), in the sense that they show when
that these linkage methods present better worst-case upper bounds than comparison is made against OPT (y)).. Moreover, the advantage of complete-le linagge for max-di am is also expected since it is the "natural" greedy rule to minimize the maximum diameter (See Proposition 2.1 of Dasgupta and Laber (2024).
For cs-ratiop average- -ink and complete-innkeg present the best results, with the for- mer being slightly superior for the small & and the latter being slightly superior when & is not small. average-link has huge dominance for the cs-ration criterion, which lines with the theoretical results from Section..1
In summary, these experiments, together with our theoretical results, provide evidence that average-link is better choice when both cohesion and separability relevant.
Acknowledgements The work of the first author is partially supported by CNPq (grant 310741/2021- 1). This study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior Brasil (CAPES)- Finance Code 001
Limitations. We have not identified a major limitation in our work. That said, the assumption that the points lie in metric space used in our results (except Theorem 3.. could be seen limitation. On the experimental side, having more than 10 datasets would give our conclusions more robustness.
References
Michael B. Fisen, Paul T. Spellman, Patrick O. Brown, and David Botstein. Cluster analysis and display of genome- wide expression patterns. Proceedings of the National Academy of Sciences
10

---

of the United States of America, 95(25):14863-144 14868, December 1998. ISSN 0027-8424. doi: 10.1073/pnas.99 148633
Michele Tumminello, Fabrizio Lillo, and Rosario N.Mantegna. Correlation, hierarchies, and networks in financial markets. Journal of Economic Behavior & Organization, (5(1):40-58, 2010. ISSN 0167-2681. doi: Economic Complexity.
Transdisciplinary Perspectives on
Ari Kobren, Nicholas Monath, Akshay Krishnamurthy, and Andrew McCallum. A hierarchi- cal algorithm for extreme clustering. In Proceedings of the 23rd ACM SIGKDD Interna- tional Conference on Knowledge Discovery and Data Mining, Halifax, NS, Canada, August 13 17, 2017, pages 255 264. ACM, 2017. doi: 10.1145/33979883300000 //doi. o/doi.org//i 10. 10e11144/3080 00956/399783.... 3098079
URL https
Nicholas Monath, Kumar Avinava Dubey, Guru Guruganesh, Manzil Zaheer, Amr Ahmed, Andrew McCallum, Gökhan Mergen, Mare Najork, Mert Terzihan, Bryon Tjanaka, Yuan Wang. and Yuchen Wu. Scalable hierarchical agglomerative clustering. In Feida Zhu, Beng Chin Ooi, and Chunyan Miao, editors, KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Viriual Event, Singapore, August 14-18, 2021, pages 1245-1255. ACM, 2021. doi: 10. 14445444544..4474000
URL/tttps://doo org/ 10. 10..11444 1021114//4444 34475444744484. 3467444
Shangdi Yu, Yiqiu Wang. Yan Gu, Laxman Dhulipala, and Julian Shun. Parchain: A framework for parallel hierarchical agglomerative clustering using nearest-neighhor chain. Proc. VLDB Endow., 15(2):285 298, 2021. doi: 10. N0.1477813489496.34888 vo115/p285-ye yu. pu.
httphttp://wut vláb. org/pvldb/
Laxman Dhulipala, David Eisenstat, Jakub Lacki, Vahab S. Mirrokni, and Jessica Shi. Hierarchical agglomerative graph clustering in nearly-linear time. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 2676-2688 PMLR, 2021.
mlr, prress/v339 http//dhlllpaaaaa html
Laxman Dhulipala, David Eisenstat, Jakub Lacki, Vahab Mirrokni, and Jessica Shi. Hierar- chical agglomerative graph clustering in poly-logarithmic depth. In Sanmi Koyejo, Mo- hamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neu- ral Information Processing Systems 35: Annual Conference on Neural Information Pro- cessing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 Decem- ber 9, 2022, 2022. URL //ttper//ppprrs... nips. cc/ cc/pperr.cpppp...pppppppp httpcc//ppppppeeeeeeeeeeeeeeeeee falerffilleellleereeeee htt.lee/ppper//22///aaaeeee /hash/ 00046666144457711144444444633633 wwt.:ed22bbbbbrrbeo Abstract- Conf .html
Laxman Dhulipala, Jakub Lacki, Jason Lee, and Vahab Mirrokni. Terahac: Hierarchical agglomerative clustering of trillion-edge graphs. Proc. ACM Manag. Data, 1()):22:1-221::22 2023, doi: 10.1
http:::/p:///d/ /ttp::////oooo////////o/o 10. 1..0.1145. 1145/3617341
Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Tremm and Claire Mathieu. Hierarchical clustering: Objective functions and algorithmss ACM, ((44):26:112::42 2019. doi: 10.1 14.5
3321386. URL httpp:::/c.i.orgg////o 10. 1145/3321386
Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh, and Grigory Yaroslavtsev. Hierarchical clustering for euclidean data. In Kamalika Chaudhuri and Masashi Sugiyama, editors, The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16- 18 April 2019, Naha, Okinawa, Japan, volume 89 of Proceedings of Machine Learning Research, pages 2721- 2730. PMLR, 2019a. URL http://proceedingg. mlr wwwps ppress/v89/cae http://aas//caaaaa11.1... html
Benjamin Moseley and Joshua R. Wang. Approximation bounds for hierarchical clustering: Average linkage, bisecting k-means, and local search. J. Mach. Learn. Res., 24:1:1-1:36, 2023. URL. http::/jmml org/
www.oorrgp.pp./////../ pttppppppp/s//aa/// vetpsr//2221188-800 html
Moses Charikar, Vaggos Chatziafratis, and Rad Niazadeh. Hierarchical clustering better than average-linkage. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM
Symposium Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, URL. https
2019, pages 2291-2304, SIAM, 2019b. doi: 10. http:///....111111..111111111110 139

---

Sanjoy Dasgupta. A cost function for similarity based hierarchical clustering. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 118-127. ACM, 2016. doi: 10.1145/289751 28897527.. httphttts:://oo. http::::///ooooo////////// 10. 11445/2997118 28997777777 2897527
Yuyan Wang and Benjamin Moseley, An objective for hierarchical clustering in euclidean space and its connection to bisecting k-means. In The Thirty-Fourth AAAI Conference on Artificial Intelligence,
AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 6307-6314. AAAI Press, 2020. doi: 10.1609/AAALV3410044 6099. URL https::tpt/// stttps://doi.. 10 1609 00/6//99aa........ aaai. v34104. 6099
Sanjoy Dasgupta and Eduardo Sany Laber. New bounds on the cohesion of complete- link and other linkage methods for agglomerative clustering. In Forty-first International Conference on Machine Learning, ICMI. 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. URL
attps://openreviex htte://ooummmddggdaeEE.....
Sanjoy Dasgupta and Philip M. Long. Performance guarantees for hierarchical clustering. Journal of Computer and System Sciences, 70(4):555-500 2005. ISSN 0022-0000. doi: https://doi.org// 10. 1016/j.jcss. 2004. 10.006. URt/https:/ /ww.www.w.. sciencedirect. htt/:///eeeeeee/e/ttiiiee////aa $00020000040013221 Special Issue on COLT 2002.
3697 Marcel R. Ackermann, Johannes Blömer, Daniel Kuntze, and Christian Sohler. Analysis of agglomer- ative clustering. CoRR, abs/1012.3697, 2010. URL./tttp///axx...or//aa////////
Anna Großwendd and Heiko Röglin. Improved analysis of complete-linkage clustering. In Nikhil Bansal and Irene Finocchi, editors, Algorithms ESA 2015 23rd Anmual European Symposium, Patras, Greece, September 16, 2015, Proceedings, volume 9294 of Lecture Notes Computer Science, pages 656 667. Springer, 2015. doi: 10.1007/978-3 0666--4835--31 7/doi. org 10. 1011010079770 3 662 48350-3_55
URL https
Anna Arutyunova, Anna GroßWendd,, Heiko Röglin, Melanic Schmidt, and Julian Wargalla. Upper and lower bounds for complete linkage in general metric spaces. Machine Learning, pages 1-30, 2023.
Jon M. Kleinberg and Éva Tardos. Algorithm design. Addison-Wesley. 2006. ISBN 978-0-321- 37291-8.
Eduardo Sany Laber and Lucas Murtinho. Optimization of inter-group criteria for clustering with minimum size constraints. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023. URL http::/pppp/:rs witp:pppppssi........p.ppp.....p cwtppper_pcpileeeecee files/papen Conference...cccc oottrr/ html
Anna Großwendt, Heiko Röglin, and Melanie Schmidt. Analysis of ward's method. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2939-2957. SIAM, 2019. doi:
URL http::t////.ii..... org/10 1137/1 99119//1.7781111154822222 182.
Pope D. Brooks, Thomas and Michael Marcolini. Airfoil Self-Noise. UCI Machine Learning Repository, 2014. DOI: https://bo..rr//1..2444322
Volker Lohweg. Banknote Authentication. UCI Machine Learning Repository, 2013. DOI:
https://bi.ong/0.2244315CC5:
I-Cheng Yeh. Concrete Compressive Strength. UCI Machine Learning Repository, 2007. DOI: http://dbb.oog//0444422cCC....
Kaynak Cenk Alpaydin, Ethem. Cascading classifiers. Kybernetika, 34(4)((69))377,, 1998. URL
http:///eudalllrg//////88333
Fang Zhou. Geographical Origin of Music. UCI Machine Learning Repository, 2014. DOI:
https//0biior///02443//35534.
12

---

Gardiner Katheleen Higuera, Clara and Krzysztof Cios. Mice Protein Expression. UCI Machine Learning Repository, 2015. DOI: https///ob..rg11022444/5553333
Cassotti Matteo Consonni Viviana Ballabio, Davide and Roberto Todeschini. QSAR fish toxicity.
UCI Machine Learning Repository, 2019, DOI: http://66o.org/1022443/////
Shini Renjith. Travel Reviews. https//dbb.oog//004444//66666
UCI Machine Learning Repository, 2018.
DOI:
13

---

A Proof of proposition 2.1
Proof. Let a E A and c E C. Then, dist(a, & dist(a, b) + dist(b, c) for every E B. Thus, B|distt(a,c) -
Σ
(dist + dist(b, c))
BEB
follows that
|B ΣΣ dist(a, - ΣΣE (dist(a,b) b) dist(b, c))
rEAcEC
at
bE
|C| ΣΣΣ Σ
dist(a, 6) + |A|
Σ Σ
dist(b,c)
BER
cE
Dividing both sides by |A| -C² we establish the inequality.
B Proofs of section
3
B.1 Proof of Theorem
Proof. When & = the result is valid because avg(A") = 0 for every A E AA".. We assume by induction that the result holds for ls + and we prove that also holds for Let and B be the clusters in *+ that are merged to obtain A", so A A U (AUB) {A, B}. Let S, T and U be clusters in Aht with T # U. It is enough to prove that avg(S) S av)
Case 1) DAUB É (S, this case, S,T,U A+1 and, then, by induction, avg(5) s avg(T, U)).
and S $ (T.U). Since A, A,B,T.U E AA+ the induction hypothesis assures that avg( (A) S avg(T.U U) and avg [) avg(T.U) and the average-link rule ensures that avg( A, B) S avg(7, (, (T) Since avg(S) (5) is convex combination of avg( A), avg (B) and avg(A, B), the above inequalities imply that avg(S) avg(AU < avg(T,
Case 2) PAUB- = B
and S E (T.U). We assume w.l.o.g. that S T. The induction hypothesis and the average-link rule guarantee that max(avg(A) (A), av avg(A, B}} < min(avg(A (A, U), Bvgg(BU)) Since avg(S, U) is convex combination of avg(A, U) and evg(B.U) and avg(S) (S) is convex combination of avg(A), BB) and avg(A, B), the above inequality implies that avg(S) = avg(AUB) S UV)(
Case 3) AUR B
Case 4) S + AUB and AUB E (T.U}. We assume w.l.og. that T = AUB. Since S. A, B,U E Ck-1, the induction hypothesis assures that avg(S) I min(avv(( A, U), avg( avg(B,U)) U)} Since avg T, U) convex combination of avg(A, U) and avg(B, U', the above incquality assures that avg S) < (T,
B.2 Lower bounds on cs-ratioy for other methods
The following examples show that the cs-ratiow of memplete-linkage a random hierarchy can be much higher than that of average- -ink in metric spaces.
and
single-linkage. Consider the instance with points Ii...., 2n in the real line. where 1. if i = 1, and x; = 1 + ie, for i > For e sufficiently small, single-linkage builds the k-clustering C (I1, .2.... Fk {z ......... I.,)). We have that avg( ( (*k, [.,,..., xn)) is Ω(n k) Ω(n k).
while avg x2) = C, so that cs cs-ratiow
complete-linkage. Let ( 2m 1, where m is positive integer and let 2(12 + l). We build an instance whose set of points X' U BUCU D F. has n = 2p points, where A, B, C, and E are sets of points in IR++1 that satisfy the following properties:
the first coordinate of the points in A U B BUCUDD is the only one that has a value different
than 0;
AA {ai....,a.) ar) and the first coordinate of a; is equal to i + 1/2;
14

---

B {bi...., b,) and the first coordinate of b, is equal to - 1/2);
C has t points and all have the first coordinate 1/2:
has t points and all have the first coordinate -1/2:
E (c.....; Cp), where the value of the first coordinate of is t2, the (i + 1)th coordinate has value 1.5t and all other coordinates have value equal to O.
The distance between any two points in X' is given by the & metric. Hence, the distance between any two points in E' is 3t, the distance between points in AU BUCUUD is at most 2t + and the distance between point in A U B UCCU D and a point in E is least t², For S p. let E, {ei,.... ep))
Thus, for < k complete-linkage is C* (A (AUCC C, B U D,,1, E2, ,,,
= n.2,, there is a way to break ties for which the k-clustering obtained by Ck-3, Fk-2)).
We have that max max d) E A x D} S + 1, maxdttst(b,c) c) E B C) st+ and max(dist(a,, b) E A x B} 2t Thus, we get that
s sepnin (c*) S avg((AUC.BUU)) S
ΣΣ YEB
dist(z,y)+
dist(r,
Σ
Σ dist(z, v) + Σ Σ dist(z,
(82 (2+1)2
ZEA VED
rEC yEB
2EC xECVED
(2 +1 (t 1) + t + 1) +
+t²
Since max-avg(C) 2 avg(Ex 22 31, we get that ca-ratioav(C*) is 21() and, hence, D2 D(vn).
random hierarchy. To analyze a random hierarchy, we first need to define how it generated. We start with a random permutation of the points in X' and clustering C containing initially the cluster comprised by all points in X. Let ø1, .....,,. permutation. Then, we perform the following steps until we have n clusters:
......; In be the points in X' according to the order given by the
j + a randomly selected a number in the set {1, 21,,,...,77 1}.
If the points Vj and zj+1 are in the same cluster C' EC C
-split C into C'2 {-, E Cli S j} and the cluster Cz C CCs. Update by replacing with Cg and C2
After splits have clustering with n clusters.
Now, we consider an instance with n points and 3 groups X, and Z, that satisfy |X| = Y (n 1 and Z = {z}. The distance between any two points in X is 1 and the same holds for Y. Moreover, the distance between points in X and Y is 2. The distance of to any other point is D >> n². Any k-clustering, with & 3, has sepmin < because at least two clusters do not contain 2. Let k < n/2. The probability that z is singleton in the k-clustering when 2 & {x1, xx) is
n 3
(k 1) 2) <
(n 1)
Then, with probability at least 3/4, there will be cluster C' that contains and point in X Y which implies that Elavg(C)] 2 D/4n². Thus, with probability at least 3/4 the k-clustering induced by the random hierarchy has sepav D2D/ /m/m)), when {I1, Since the probability of z & {#1 2n is (n 2)/n, n. the same bound holds when we drop this constraint.
B.3 On the approximation of average-link for cs-ratiow
Let be an even number, lo = 2 and c positive number very close to 0. Consider 4 set of points Si, S2, S3 and S4, where dist(a,, v) = for xr Sz. distsistrrr. y) = for æ. S4, dist(s), 82) = T and dist(x, v) = T for (x, Sg x S4. In addition, we have dist(s1; x) 27 for x A 82 and dist(#2, y) = 27 for y # S1.
[51 ).52 = {*2} and S3 and Sa have n/2 points each. We have
15

---

Clearly, the 4-clustering obtained by average-link is (S1. S2. S3, S1). Then, to obtain à 2- clustering, merges the clusters S₁ and S and, next, S3 and S4, so that the final 2-clustering is A (S1 U S2, S3 U S4), which satisfies max-avg(A
T and sepmin(A) 27. On the (S, U S3, S2 U 54), we have that max-avg( O(T/n²) and sePwin (8) 2 T. Thus, the approximation of average-ling is S2(n²)
other hand, for the clustering
B.4 Triangle inequality is necessary for Theorem 3.4
We present an instance that shows that the assumption that points lie in a metric space is necessary to establish Theorem 3.4
Let and B sets with n/2 and n points, respectively. We have dist(a, a') af a' A; dist(b, b') = 1 if b, E B and dist(a, b) = 4 if (a, b) E A x B. Moreover, let p be point that A for which dist(a, p) = n/2
not in B. There point a' E A {a}, dist(a', p) = 2. Moreover, dist b) 4 for b E B.
and for all other points
For this instance average- link builds the 2-clustering A2 (AU (p); B). We have that di am A p) n/2 - and avg( A Up B) = 4, Thus, 1s-ratioox(44" is 2((n). On the other hand, for the clustering A' (A, B U p), cs-ratiom(A') is O(1), ((n).
the approximation of average- is
B.5 Proof of Lemma 3.2
Proof. The first inequality holds because avg(z, X) prove the second one.
|X|-1
avg(æ, X -x). Thus, we just need to [X]
Let S₁ be the first cluster merged with by wverage-link and let S,, for i > 1. be the cluster merged with S₁ U............. by average -ink. Define To {x} and, for 2 7; := T:-1 S,,.
Furthermore, define e, and m, as 6; == avg(T;-1, S;) and m, == avg(æ, T x) respectively. Note that there is t for which T, X and, hence, m, avg(x, X x)).
have that
[Tg
18t+1| avg(æ, S1+1) S
m++1
avg(I, (z, T, xx)
(7)
[
[T3-1|
T3
1
|8
|8
m.
(m; + e++1) my
(8)
T++1
[T+1
T
where the inequality follows from the triangle inequality.
Let us consider the beginning of the iteration in which T:-1 and S, are merged. At this point we have L > clusters YI...., Ye such that Y Y, U... U Y and e' clusters Zz...., Ze such that Z Zi .... U Zg. Note that there exist and j such that avg (Y, Zj) < avg(Y, 2). Thus, must have e; < avg(Y, Z), otherwise average- would merge Y, and Z, rather than T;-1 and S.
To establish the result, we show by induction that m, S avg(Y, 2) HIT.I11, for 2 1. The lemma then established by taking = f, where satisfies T, ===A. X.
For 1, we have m2 = e1 - avg(Y, 2) < avg(Y, 2) HITI-1 We assume by induction that m4-1 < avg(Y, 2) H [ 1/-1 By inequality (7
[T: 11-1 Σ hml h
T---1 =
| T
1
m S m4-1te
< aVg(Y,Z)
+avg(Y,2)
Σ
Zy-HH
h
A=|T
16

---

C Proof of Lemma 3.5
Proof. First, we note that
2-1
1-1
B
Σ
A
Σ h++ 1)1 =1= i!
h=0
h=0
for 2
Moreover, for 2 2, we have that
|A
avg (rg(A,,44 (1, A;-1) Bi-2
avg(A;, Bi-1)
svg(A, Bi-2)
(9)
|Ba-1
A
_
B
avg Ai, Ai-1)
aavg A; Ai-1) + avg Ai- Bi:2))
(10)
B3:-1
B
Bi-2
avg A A +
avg (1-11-1 B(-2)=
(11)
Bi-1
Bi-2
1 +
avg( (1 BiB2)),
(12)
B
where the last identity follows because avg(A,, A,-1) = Pi Pi-1 = avg(A,- Bi-2).
By applying the above equation successively, we conclude that
avg(Ai, Bi-1) = (i (i+ avg A1, Bo) = (i + 1)
and, hence,
i(i (
Pi = 1
(h+
2
#=1
Thus,
diam BB--)) = Pi-1 PPu Pi-1 i(i
Now we show that at the beginning of the step (n - +) + average-link keeps a clustering that contains the cluster B;-1 and the clusters A,, for i j < - 1. First, we observe that after steps average-link produces a t-clustering (Ap..... AA-1) since points in the same group A, are located at the same position. We analyze what happens in the remaining - 1 steps.
For i the result holds because Bg Ag. We assume as an induction hypothesis that at beginning of the step (n 1) + i, we have the clusters Bi and Aj. for j 2 i. By construction, for i S <
avg(A Ar) = Ps Pr pi+ = avg(As, B:-1),
Moreover,
- 1 = avg (A; Bi-1) < avg(Aj, Bi-1),
for j i. Thus, average link prefers merging A, and B,-1 rather than any other pair of clusters, which completes the inductive step.
[
D Proofs from section 4
D.1 Proof of Proposition 4.1
Proof.
Cet = (Ci, ....... C.:) be a k-clustering that maximizes sepay. Let Q be the family of sets
of points Q such that iQ le and Q intersects clusters Ci...., Ct. Let P (pI,..., be set in Q that satisfies avg(P P)) 2 avg(Q), for every Q Q. Moreover, let U {u...... Uy be
17

---

set of l points where u, is randomly selected from C, It follows from the choice of P that
k(k 1)
k(k 1)
2 avg (P)
Elavg(U)]
=
k-1 k
k-1 h
dist(un
Σ
[dist(u, u,)l
Σ
Σ
avg C Cÿ) 2
j=it1
j=it1
i=1 j=it1
k-k
separ (C*)
2
D.2 Proof of Theorem 4.2
Let [pi|L sisk) k) be the k points given by Proposition 4.1 and let be function that maps each point avg(Y, , 2) sepain (A*).
Proof.
into its cluster in A Moreover, let Y and Z be clusters in A that satisfy
Let and yf be distinct points in P. We consider two cases:
Case 1) p and p' belong to the same cluster A in At. From Theorem 3.3 we have that
dist(p. p/) < diam(A) A) s 2H Ajav((Y 2) = 2H a sepmin(A*)
Thus,
dist(p.p')
S
Σ
2H A| sepmin(AA)
(13)
P.P'EPDA
Pv''PPA
By considering all clusters A E A we get
dist(p.p's
Σ Pale h(e)-h(p))
sepnin (A*)
(14)
CP
h(p)mh(s))
Case 2) and p' belong, respectively, to different clusters and in A We consider two subcases:
subcase 2.1) k 2. In this case, from the triangle inequality, we have that dist(p,p' p/)
avg(p. p') S avg(p, A) +avg(A, A') avvg(A', By using Lemma 3.2 we have that avg(p, (p,,,,,, A) S
Hn-1avg(A4 A, A) Ha--ssppe (At) and avg(p', A') < Hn- avg (A A') Hn 100m1sppman- (A*)..
Thus,
Σ dist(p. p') dist(p,p') 2H (4 avg(A,
(15)
A
where the first identity holds because p (p.r'.
subcase 2.2) le > 2. Let S be cluster in A - {A, A'). From the triangle inequality, we have that dist(p. p') avg(p, p') S avg(p, A) + avg(A, avg(S, A') + avg(A',pp)
If AA| = 1. avg(p, A) 0 < || sepain Moreover, if |A| 2 2, it follows from Lemma
3.2 that avg(p, A) < H|AT avg(Y, 7) H sepmin (A*). Analogously, have avg(p', A') s
H Ar sepain (A*). Thus,
dist (p. p¹) & Sep + avg A, + avg(S, + H sepain
By averaging over all possible E A {A, A'} we get that
dist(p.p') < 22 (A') +
Σ
(avg(A, + avg(S.
k 6-
SE(A,A
By adding all points PNA and p' P we get that
18

---

E ΣE
E
dist(p.1')
PEPrAP'EAm
ΣE
E
2H sepsee se + PNA IPOA
Σ (avg + + avg(S, A'))
k-2
PEPnAP'EPPal
SE(A.A]
By adding the above inequalities for p,p' E P. with h(p) + h(p'), we get that
dist(p,P/)
P.p h(P)
(16)
Σ
2H,- sepnin(At)
E IPOA) Σ (avg(A,,) + av)
k-
A.At A
SE(A,A)
M(p)st(pp))
(17)
Σ
2H, sepain(A*)
k-2 E (PP(AAUA))-C (B-IPP (EPNAAAAAD,--IIPPAAAAAAAA -
(18)
Σ
2H, (A Σ
avg( A'),
A.Akcak
AgA
(19)
where the last inequality holds because (I (k-|pn (A S k2/4.
we compare inequalities (66-((99 19h with inequality
15 we conclude that 16 19
also hold for
the subscase k = 2.
Then, by adding inequality 14 with the inequalities separ (A*),, we get that
16
19
and also using the fact sepain sepain(A*) (At) S
Σ dist(p.p') s 2H, k(k 1)
avg(A, s (2H,+K) k(k 1)sepav (A*)
(At)
Σ
2
A.E' AxA'
Proposition
4.1 ensures that
kek 1) OPT (k)
k(k 1) avg(P)
Σ dist(p.p)) p')
2
2
P.PE
Thus, from the two previous inequalities, we conclude that
sepav separ(A OPT (k)
2H, k
D.3 The sepav criterion for other linkage methods
The following instances show that the separability of both single-linkage and complete- can be much lower than (k)
log n
For single-In linkage, consider the instance X AU B U (p), where A contains n /n Moreover, we have dist(z, v) for y E A.
points and B contains vn points bi,..., b.5. dist(h, æt) i for every point E A and dist(bi,b;) by) = li ji. Moreover, dist(p, x) = + for builds the clustering
every point x E A. and dist(p, b,) 1 this case, single-linkans (A U B, {p]). We have that sep... ( AU B, p) 2, while sep.. (A (AU Up. B) is l(vn).
19

---

Regarding complete-linkent we consider the instance presented at Section B.2 but without the set E, that is, the of points X AUBUCU D. When 2, complet--lnnken builds the clustering UA BU D) that has separ O(1) while the clustering (A, U DUU satisfies satisfies
(2t +t)
2 1(21 + +t)
Since = (Vvn), we conclude that the separability of complete-linkee for this instance is 0
(PT
vn
D.4
Separability and cohesion can be conflicting
Recall that for instance Ix- average- builds the k-clustering .A (S1, 81, $2..... , 5k-2). Note that max-di amxx-iiam(((4
max- E. Let A'' be a k-clustering different from We argue that max-di am) 2 1 and max-avg( AA) is (2(1 In fact, if A'' has cluster A that satisfies |A] 2 2 and |A |AnSs] Sal 2 1, then max-diammAA)) 2 1 and max-avg(AA)) is (11/k)). Otherwise, if A' does not have such a cluster, then all points S3 must singletons A'. Since A' + A², there is cluster in A'' that contains both point in S and point in S2. Thus, max-diam( (A"') D and max-avgl max-avg(A")) DDD/k²).
Let M be the class of methods with bounded approximation regarding max-diam or to max-avg. Then any method M E M builds the clustering A Since sepav is O(D/k) and there is a k-clustering for I. whose sepav is C2 (D), we conclude that the approximation factor of any method M E M regarding separ is O(1/k).
Now, consider sepain- We have that sepain 1. Let B (Bi..... B&) be a k-clustering with the following properties: (i) [B n S3 2 for each S k 2; (ii) each B,, with 2 2, has exactly one point in S1 U U2 (iii) B has point in S1 and B₃ has a point in S2. We have that sepain (B) is ((D). Thus, any method M E M has approximation O(1/ to sepain. that is, the approximation is unbounded in terms of n.
E Proof of Theorem 5.4
Proof. Let I be the instance obtained by augmenting the instance ICS presented right after Theorem
3.4. with the points Io...... II-1. where dist (z,, A.) = t + and for i * j. dist(z;,a) xz)) =
Pj P:l + 2(t + + E) and dist(æ;, A,) lp; p.l +
Consider t = k. We argue that the (k + 1)-luusteiing obtained by average-link for I consists of the clusters (Bx-1, (=o) (.) In fact, in its first steps average-link obtains the 2k- clustering (Ao. A TD, Ik-1) .0.
since the distance between points in A, is O. In the next does not make merge involving a point x; because the average distance of x; to any other cluster is larger k + 1 and, by Lemma 3.5 the average distance between B, and Thus, the execution of average- link for I merges the same clusters that merged in the instance CCS and, then, ends up with the (A: + 1-ccuutteen (Bx-1, {2o). {xx-1)).
k-1 steps, average-limg
A, is i 1
Thus, for instance I, the maximum diameter of cluster in 4 least diam BB- which is 2(k2), while the k-clustering (æo U Ag...., IA-1 U Ag-1) has diameter k
F Experiments: extra details
Table 2 presents our datasets with their main characteristics.
Figures (6) show the results obtained by single-linkage, complete-linkage and average-link, for all datasets and the different criteria considered in the paper. For a given dataset D, method M and criterion a, the height of the bar given by average my for every k considered in our experiments, where my is the ratio between the value of criterion a achieved by method M on dataset divided by the best value for criterion a, among those achieved by single- linkaee, everage-lind and mamplete-linkagee dataset D.
20

---

Table 2: Datasets
Dataset
d
Source
Airfoil
1501
Brooks and Marcolini 2014
Banknote
1371
5
Lohweg 2013
Collins
1000
19
Mp
Concrete
1028
8
Yeh [2007
Digits
1797
64
Alpaydin T998
Geographical Music
1057
116
Zhou 2014
Mice
552
77
Higuera and Cios
2015
Qsarfish
906
10
Ballabio and Todeschini
2019
Tripdvisor
979
10
Renjth 2018
Vowel
990
max_diam
single com complete average
3.0
2.0
0.5
sirbal
banknate
collins
conoate
dights
mica
garrish
tripadiissr
vowel
geamunk
Figure 1: Results for the max-diam for the different datasets. For interpreting the bars, the lower the better
Regarding the cohesion criteria complete-linkege presents the best results for max-diam, followed by overage-link For max-avg, again complete-lnkage and average-link are the best, with the latter having a slight advantage.
In terms of the separability criteria, everage-linki much better than the other methods for sepain. while for sepav there a balance between average-link and Lannle-linkagee
For the criteria that combine cohesion and separability, average-linki superior for cs-ration, while there balance between average- and complete- -inkage for cs-ratiow.
Table and show the results for the experiment described in Section 6 when the Euclidean distance is replaced with the l and for norm, respectively. The observations made in Section 6 also hold when these metrics are used.
Finally, we note that the variance of the results for average-limg -lnn is small. Indeed, entry (average) close to (e.g. 0.96) cannot have an underlying large variance because is the maximum possible value for an entry. Since most entries for average-link are close to 1, one can conclude that the variance of its results usually small. In the supplemental material, we have .cvv files with our full results.
21

---

max avg
single complete
1.75
125
1.00
0.50
0.00
arreel
banknata
colins
concrato
dight
gparfish
tripachisor
towal
geamssic
Figure 2: Results for the max-avg for the different datasets. For interpreting the bars, the lower the better
min
3.0
single aveerage
0.6
0.4
strial
Laninode
colline
concndt
digits
mice
gearishh
vowel
gemmusic
Figure 3: Results for the sepain for the different datasets. For interpreting the bars, higher better
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
22

---

sep_avg
single
complete
0.8
0.6
0.0
airbal
bankno
collnn
concreto
digis
mica
qaaniinn
tripadvisor
rowal
geomusic
Figure 4: Results for the separ for the different datasets. For interpreting the bars, the higher the better
cs_ratio_rr
complete average
3.5
2.0
15
1.0
sirbal
bankndte
collins
conenste
digita
mica
gaarishh
tripanhiioor
vowel
geomusic
Figure 5: Results for the cs-ratiow for the different datasets and methods. For interpreting the bars, the lower the better
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
23

---

se_rato__Dr DM
single complete average
anfail
banknota
colins
concreto
dgits
mice
marfish
inipadviou
vowel
geomusic
Figure 6: Results for the es-ratiops for the different datasets and methods. For interpreting the bars, the lower the better
Table 3: Average ratio between the result of method and the best one for each criterion and each group of k. The best results are bold-faced. Distances are computed using & norm
Smal
Medium
Large
A
C
S
A
C
S
A
C
S
sepnin
0,99
0,81
0,75
0,99
0,86
0,66
0,99
0,9
0,71
sepav
0,98
0,83
0,93
0,96
0,89
0,97
0,95
0,99
max-diam am
0,86
0,99
0,72
0,85
1
0,5
0,81
1
0,41
max-avg
0,94
0,94
0,88
0,99
0,9
0,73
0,99
0.83
0,7
cs-ration
0,96
0,91
0,62
0,96
0,98
0,38
0,88
0,99
0,32
cs-ratiouv 0,98
0,8
0,71
0,79
0,51
0,76
0,51
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We included section at the end of the paper.
Table 4: Average ratio between the result a method and the best one for each criterion and each
group of k. The best results are bold-faced Distances are computed using foo norm
Smal
Medium
Large
A
C
S
A
C
A
C
S
sepain
0,99
0,82
0,77
0,98
0,91
0,7
0,99
0,94
0,75
sep
0,97
0,82
0.95
0,97
0,92
0,98
0,96
max-diam
0,94
1
0.9
0,87
1
0.7
0,85
1
0,56
max-avg
0,94
0,96
0.91
0,94
0,88
0,79
0,95
0.85
0.81
cs-ratiom
0.97
0,86
0,74
0,91
0,98
0.52
0,89
0,99
0,45
cs-ratiow
0,96
0.82
0.74
0,96
0,85
0,59
0,97
0.82
0.65
24

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
25

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (nttps://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ /ttppp.cc/pbllccguideeee http://oeeubiiiisioooooooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
26

---

Providing as much information as possible in the supplemental material (appended to the paper) is recommended, but including URLs data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g.. data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The details are in the paper and also in the supplemental material.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: We have not included error bars because they do not help much in our case. However, from the tables and analyses, the reader should have clear idea of the variability of our results (see last paragraph of Section F).
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report I-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: This information is irrelevant to reproducing our experiments or reaching our conclusions.
Guidelines:
The answer NA means that the paper does not include experiments.
27

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpps////aarrpp..cooo//////ccaa
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper is mostly about theoretical results. We provide several new analyses for algorithms that are widely known. We do not see clear societal impact that deserves to be mentioned.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
28

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We cite the datasets we use in Appendix F
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
Our supplementary material contains our codes.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "weGviei8oM", "reviewer": "Reviewer_f81R", "summary": "This paper studies the well-known average linkage algorithm. The paper notes that average linkage has better approximation guarantees with respect to (variants of) Dasgupta's cost compared to complete and single linkage. However, in certain other settings such as metric graphs the approximation factor of average linkage does not outperform random HC trees. This paper therefore deviates from analysing Dasgupta's cost, and analyses average linkage with respect to seperability and cohesion criteria. There are also some experimental results.", "questions": "1.) Are there any downstream settings/tasks where approximation guarantees with regards to max-diam, cs-ratio etc. are used? A stronger motivation for why these objectives should be/are studied would be nice to include in the paper.", "limitations": "yes discussed", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.) There are quite a few solid results regarding the approximation guarantee with respect to several cohesion and separability criteria (cs-ratio, OPT_sep, and several others), and shows that it outperforms single and complete linkage. Furthermore, several tight instances are provided as well. A lot of these results are good contributions to the HC literature, and provide a more clear theoretical picture of why average linkage performs so well.\n\n2.) The experimental results also show fairly robustly that the theoretical guarantees can be seen in practice as well.\n\n3.) The paper is well-written and enjoyable to read.", "weaknesses": "There are only (very) minor weaknesses:\n\n1.) No new algorithmic contribution, e.g., some improvement to average linkage that could improve some of these bounds.\n\n2.) Most results only hold for points in metric space. \n\n3.) Font size changes from page 3 onwards (line 138)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are glad you enjoyed reading our paper and found our results to be solid.\n\n**Issue** *Font size changes from page 3 onwards (line 138)*\n\nThanks for pointing it out, we will fix it.\n\n**Question** *Are there any downstream settings/tasks where approximation guarantees with regards to max-diam, cs-ratio etc. are used? A stronger motivation for why these objectives should be/are studied would be nice to include in the paper.*\n\nReply: The main goal of our paper is to provide a comprehensive theoretical study of average-link, a popular method for Hierarchical Clustering, for which good results are often reported in the literature. Our metrics were chosen because they are natural, allow easy interpretation, and capture cohesion and separability (or both).  For instance, we believe they are way easier to explain to students or practitioners than Dasgupta's cost function.  \n\nWe believe that it is reasonable to design algorithms to optimize our criteria, but we do not identify anything special about our criteria to justify a greater focus on them rather than on other available criteria that capture cohesion and separability.\n\nAbout downstream applications,  in facility location problems, the k-center (radius) criterion is used to ensure that every client is served by a \"close\" facility.  In metric spaces, the optimal maximum diameter (max-diam) and the optimal k-center differ by a factor of at most 2.  Thus, by optimizing the max-diam we are also optimizing the k-center (ignoring the factor of 2). \n\nWe will add this discussion to our revised version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ER7qrbnFfz", "reviewer": "Reviewer_k54Y", "summary": "This paper theoretically investigates the effectiveness of average linkage for hierarchical agglomerative clustering. The authors consider the setting where we are clustering in a metric space and consider well motivated definitions of separability and cohesion of clustering. The performance of average linkage and other methods wrt these settings is then considered. The authors conclude the work with an empirical analysis.", "questions": "Can you say more about the relationship between your work and [Großwendt et al., 2019]?", "limitations": "Adequately addressed the limitations", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents an interesting analysis of average linkage as a hierarchical clustering method. \n\nThe results help to explain the effectiveness of the method. \n\nStrengths include:\n* Thoughtful analysis of a popular and well studied method\n* Understanding of cost functions and how average linkage optimizes them\n* Empirical analysis following theoretical results", "weaknesses": "I think the paper has several merits as listed above. Weaknesses include:\n* I think the presentation of Table 6 could be clearer -- I think directly presenting the results per dataset per method would be clearer.\n* Perhaps more text could be used to describe the novelty of proof techniques\n* Given some of the motivations, I wonder if more of the analysis on random hierarchies should be included in the main paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are glad that you saw several merits in our submission!\n\n**Issue 1**:  *I think the presentation of Table 6 could be clearer -- I think directly presenting the results per dataset per method would be clearer*\n\nReply.  I believe you mean Table 1. This table is the best solution we found for the following problem: how to give a reasonable overview of our empirical findings in a relatively small table? Given our focus on the theoretical results, we allocated only a small space in the main text for the experiments.\n\nThat said,  we agree that it is good to have results per dataset per method. We will add them to the appendix in our revised version. Moreover, we submitted a one-page .pdf with these results in the rebuttal for all referees.\n\n**Issue 2**: *Perhaps more text could be used to describe the novelty of proof techniques*\n\n**Issue 3** *Given some of the motivations, I wonder if more of the analysis on random hierarchies should be included in the main paper.*\n\nReply for 2 and 3. The final version allows an extra page. If the paper is accepted, we will use this page to add more discussion about our proof techniques and we will also move to this page some of the analyses of random hierarchies.\n\n**Question**: *Can you say more about the relationship between your work and [Großwendt et al., 2019]?*\n\nReply. [Großwendt et al., 2019] study Ward’s method, which is a linkage method that at each step greedily merges the clusters that yield the minimum increment in a k-means cost function. The paper shows a lower bound on the approximation of the clustering built by Ward. Regarding upper bounds, it shows that Ward has a constant approximation for instances on the real line and instances that admit well-separated clusters. No upper bound for the general case is presented.\n\nAs in our paper, the focus is on analyzing a popular linkage method. However,  [Großwendt et al., 2019] address the k-means cost function with Euclidean norm while our paper addresses other criteria (max-diam, sep_min, cs-ratio, etc) in general metric spaces.  Moreover, we have a way more comprehensive set of results and there is no (at most little) overlap of techniques.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UIUWFtiZlr", "reviewer": "Reviewer_Sa8n", "summary": "This paper studies the performance of average-link clustering in metric spaces, focusing on criteria that offer better interpretability than Dasgupta's cost function for cohesion and separability. By investigating how well average-link balances the compactness of clusters (cohesion) with the distinctiveness between clusters (separability), the analysis sheds light on the ability to produce meaningful and well-separated clusters. The paper provides instances where single-linkage and complete-linkage clustering are exponentially worse than average-link clustering with respect to average separability. It presents lower bounds on the maximum diameter of clusters generated by average-link, providing insights into the method's clustering quality and performance compared to single linkage. Experiments conducted with real datasets confirm that the theoretical results align with practical observations, suggesting that average-link performs better than other methods when both cohesion and separability are considered.", "questions": "Just out of curiosity, I would only like to know if there are any plans for future directions of the work, as they were not indicated in the paper.", "limitations": "I don't see any additional limitations (apart from what is already mentioned), and I'm mostly satisfied with the paper.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The paper tackles an interesting topic\n\n+ The Related Work section is extensive, and the proposed approaches are well-placed in the existing literature\n\n+ The methodology is adequately sound and well-explained\n\n+ The experimental setting is extensive, and results seem to demonstrate their effectiveness", "weaknesses": "I don't have any specific questions for the authors, as I'm mostly satisfied with the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks again for revising our paper and for your positive evaluation!\n\n**Question** *Just out of curiosity, I would only like to know if there are any plans for future directions of the work, as they were not indicated in the paper*\n\nOne potential direction for future work is addressing the case in which the input is given by similarities  rather than distances.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FKY6HIqCtz", "reviewer": "Reviewer_QwrC", "summary": "The authors analyse the theoretical properties of the so-called average-link approach for clustering points in metric spaces. They formulate cohesion and separability criteria that capture the goodness of a clustering, essentially formalising the intuition that good clusters should be densely packed and well-separated. They prove previously unknown bounds on the cohesion and separability of clusters obtained through average-link.", "questions": "- The results on empirical datasets in tables 1, 3, and 4 appear to not fully agree with the theoretical results, specifically, complete-linkage and single-linkage out-perform average-link in some cases, suggesting that average-link should not always be the preferred choice. How can this be explained?\n- The second-last sentence in the introduction mentions that Dasgupta's function does not reveal how good the clusters for a specific range of k are. How do the measures introduced in the present work address this shortcoming?\n- The conclusions state that average-link is a better choice than complete-linkage and single-linkage when cohesion and separability are important. Are there cases when average-link should *not* be preferred?\n- Dasgupta's cost function seems to accommodate the case where similarities are asymmetric whereas the current work assumes metric spaces. Could the analyses and bounds be extended to cases of asymmetric similarities between points?\n\nMinor points:\n- The heading \"Smal\" in the tables is missing an l.\n- Are the labels for tables 3 and 4 in Appendix F placed before their captions in the LaTeX code? This would explain why they are referred to as \"F and F\" in line 655.", "limitations": "Limitations are briefly discussed at the end of the main text.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The authors analyse the properties of average-link rigorously and provide mathematical proofs for their claims.\n- The work establishes previously unknown bounds on the quality of clusterings obtained through average-link with respect to cohesion and separability.", "weaknesses": "- The work is technically involved and therefore difficult to understand in detail for readers not trained in mathematics (such as myself). I would have welcomed a less technical summary of the paper's key points.\n- The paper only mentions complete-linkage and single-linkage as alternative linkage methods for clustering. A brief discussion of other clustering methods and how they compare to average-link would have been useful. Specifically, the paper suggests using average-link rather than complete-linkage or single-linkage when cohesion and separability are relevant but does not relate average-link's performance to other methods with respect to cohesion and separability.\n- The empirical results are somewhat intransparent since averaging has been done across datasets. It would be easier for the reader to examine the results if they were also presented on a per-dataset basis (for example in the appendix).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for revising the paper and for the positive evaluation!\n\n**Issue 2**  *The paper only mentions complete-linkage and single-linkage as alternative linkage methods for clustering. A brief discussion of other clustering methods and how they compare to average-link would have been useful. Specifically, the paper suggests using average-link rather than complete-linkage or single-linkage when cohesion and separability are relevant but does not relate average-link's performance to other methods with respect to cohesion and separability.*\n\nReply: It is not clear to us which other clustering methods we should compare with since there are many options. We compared with single-linkage and complete-linkage because they are also quite popular and closely related to average-link. Average-link has been used for a long time, and here we provide some theoretical foundation for its superior performance compared to other popular linkage methods.\n\n\n**Issue 3** The empirical results are somewhat intransparent since averaging has been done across datasets. It would be easier for the reader to examine the results if they were also presented on a per-dataset basis (for example in the appendix)\n\nReply:  We will add results per dataset to the appendix in our revised version. Moreover, we submitted a one-page PDF with results per-dataset in the rebuttal for all referees.\n\n**Question 1**  *The results on empirical datasets in tables 1, 3, and 4 appear to not fully agree with the theoretical results, specifically, complete-linkage and single-linkage out-perform average-link in some cases, suggesting that average-link should not always be the preferred choice. How can this be explained?*\n\nReply. In fact, for cs-ratio_dm, complete-link outperforms average-link for ranges medium and large, and for  sep_av single-link outperforms average-link for the same ranges, by a small margin. However, this is not a contradiction since the theory only guarantees the behavior for worst-case instances, it does not state that for all instances average-link outperforms single-linkage and complete-linkage. \n\nThat said, the performance of average-link in our experiments is either the best or close to the best for almost all settings.\n\n\n**Question 2** *The second-last sentence in the introduction mentions that Dasgupta's function does not reveal how good the clusters for a specific range of k are. How do the measures introduced in the present work address this shortcoming?*\n\nReply. Our measures are calculated for each k-clustering and not for the whole hierarchy, so they can depend on the number of clusters $k$. For instance, our bound (Theorem 5.3) indicates that average-link has a better approximation in terms of cohesion (max-diam) for small k than for large k.  \n\n\n**Question 3**  *The conclusions state that average-link is a better choice than complete-linkage and single-linkage when cohesion and separability are important. Are there cases when average-link should not be preferred?*\n\nReply. Yes, as an example, if one is primarily concerned about avoiding clusters that contain distant points  (minimizing max-diam) then Complete-Link seems to be a more interesting choice: the available bound for Complete-Link (Dasgupta and Laber 24) is better than that of Average-Link (Theorem 5.3) and our experiments also suggest that Complete-Link is better than  Average-Link regarding this criterion. \n\nAs a second example, if one is interested in maximizing the minimum spacing between clusters (Kleinberg and Tardos, Greedy Chapter), then single-linkage gives the optimal solution, so it is the best choice.\n\n\n**Question 4**  *Dasgupta's cost function seems to accommodate the case where similarities are asymmetric whereas the current work assumes metric spaces. Could the analyses and bounds be extended to cases of asymmetric similarities between points?*\n\nReply. Right now we do not have an answer, this could be an interesting direction for future work. Thanks for the nice question", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the referees for their time and valuable feedback! We are happy that all reviewers are positive about our submission and that it was recognized that our results provide a more clear theoretical picture of why the well-known average linkage method performs so well.

We are attaching a one-page PDF with results per dataset (suggested by reviewers k54Y and QwrC).
In the PDF we have six graphs, one for each of our six criteria.  

For a given criterion $C$, dataset $D$, and method $M$,  the bar height summarizes the results for the different values of $k$ achieved by method $M$ on dataset $D$, regarding criterion $C$. More precisely, the bar height is obtained by taking the average of $m_k$ for every $k$ considered in our experiments, where $m_k$ is the ratio between the value of criterion $C$ achieved by method  $M$ on dataset $D$ divided by the best value of $C$  among single-link, average-link and complete-link achieved on dataset $D$.

In the two graphs at the top (criteria that should be maximized), higher values are better.  For the other graphs (criteria that should be minimized), lower values are better. One can see that average-link is either the best or close to the best for most settings.

Meta-review: This paper considers hierarchical clustering under recently proposed clustering objectives.  These objectives have been been quite influential, but have caveats for certain kinds of data sets.  In particular, all algorithms approximate the objective.  This paper seeks to better understand the structure of solutions returned by algorithms that perform well.

The reviewers thought this paper was well-written and of interest to the community. Both the theory and experiments are generally of interest.
Decision: Accept (poster)