On the cohesion and separability of average-link for hierarchical agglomerative clustering

Authors: eduardo s laber
miguel  batista
Venue: NeurIPS_cc_2024_Conference
Published: 2024-04-30 02:51:11

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.

Main paper: 
 introduction: 
 Clustering is the task of partitioning a set of objects/points so 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 to handle large datasets.Hierarchical clustering is an important class of clustering methods. Given a set of X of n points, a hierarchical clustering is a sequence of clusterings (C n , C n-1 , . . . , C 1 ), where C n is a clustering with n unitary clusters, each of them corresponding to a point in X , and the clustering C i , with i < n, is obtained from C i+1 by replacing two of its clusters with their union A i . A hierarchical clustering induces a strictly binary tree with n leaves, where each leaf corresponds to a point in X and the ith internal node, with i < n, is associated with the cluster A i ; the points in A i correspond to the leaves of the subtree rooted in A i . Hierarchical clustering methods are often taught in data science/ML courses, are implemented in many machine learning libraries, such as scipy, and have applications in different fields as evolution studies via phylogenetic trees [Eisen et al., 1998] , finance [TUM, 2010] and detection of closely related entities [Kobren et al., 2017 , Monath et al., 2021] .Average-link is widely considered one of the most effective hierarchical clustering algorithms. It belongs to the class of agglomerative methods, that is, methods that start with a set of n clusters, corresponding to the n input points, and iteratively use a linkage rule to merge two clusters. Due to its relevance, we can find some recent works dedicated to improving average-link' efficiency and scalability [Yu et al., 2021 , Dhulipala et al., 2021 , 2022 , 2023] as well as recent theoretical work that try to understand its success in practice [Cohen-Addad et al., 2019 , Charikar et al., 2019a , Moseley and Wang, 2023 , Charikar et al., 2019b] .Most of the available theoretical works give approximation bounds for average-link regarding the cost function introduced by [Dasgupta, 2016] as well as for some variants of it. Let D be the tree induced by a hierarchical clustering. Dasgupta's cost function and its variation for dissimilarities considered in [Cohen-Addad et al., 2019] In general, the existing results show that average-link achieves constant approximation for variants of Dasgupta's function while other linkage methods do not.However, there is significant room for further analysis due to the following reasons. First, Dasgupta'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 average-link from other linkage methods as single-linkage and complete-linkage in terms of approximation, they do not separate average-link from a random hierarchy [Cohen-Addad et al., 2019 , Moseley and Wang, 2023 , Charikar et al., 2019b] . Moreover, for the case in which the points lie in a metric space every hierarchical clustering has 1/2 approximation for the maximization of CKMM [Wang and Moseley, 2020] , so 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 a specific range of k. As an example, small k are important for exploratory analysis while large k is important for de-duplication tasks [Kobren et al., 2017] .Motivated by this scenario, we present a comprehensive study of the performance of average-link in metric spaces, with regards to several natural criteria that capture separability and cohesion of clustering. In a nutshell, these results, as 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 a metric space, where X is a set of n points. The diameter diam(S) of a set of points S is given by diam(S) = max{dist(x, y)|x, y ∈ S}. For a cluster A and for two clusters A and B, let avg(A) = 1 |A| 2 x,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) := max{diam(C i )|1 ≤ i ≤ k} and max-avg(C)EQUATIONWe also study natural optimization goals that capture both the separability and the cohesion of a clustering. We define the cs-ratio AV and cs-ratio DM of a clustering C as space and it is tight in the sense that there are instances in which cs-ratio AV (C) = 1 for every k-clustering C. For the related cs-ratio DM criterion, we present a more involved analysis which shows that cs-ratio DM (A k ) as well as the approximation of average-link regarding OPT (the minimum possible cs-ratio DM ) are O(log n); these bounds are nearly tight since there exists an instance for which cs-ratio DM (A k ) and cs-ratio DM (A k )/OPT are Ω( log n log log n ). Both cs-ratio AV and cs-ratio DM allow an exponential separation between average-link and other linkage methods, as single-linkage and complete-linkage. Interestingly, in contrast to CKMM (Eq. 1), our criteria also allow a very clear separation between average-link and the clustering induced by a random hierarchy.Next, we focus on separability criteria. Let OPT SEP (k) be the maximum possible sep av of a k-clustering for (X , dist). We show that sep av (A k ) is at least OPTSEP(k) k+2 ln n 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 sep av . Regarding single-linkage and complete-linkage, we present instances that show that their approximation with respect to sep av are exponentially worse than that of average-link, for the relevant case that k is small. We also investigate the cohesion of average-link. For a k-clustering C, let avg-diam be the average diameter of the k clusters in C. Let OPT DM (k) and OPT AV (k) be, respectively, the minimum possible max-diam and avg-diam of a k-clustering for (X , dist). We prove that for all k, max-diam(A k ) ≤ min{k, 1 + 4 ln n}k log 2 3 OPT AV (k). This result together with the instance given by Theorem 3.4 of [Dasgupta and Laber, 2024] allow to separate average-link from single-linkage, in terms of approximation, when k is Ω(log 2.41 n). We also show that max-diam(A k ) is Ω(k)OPT DM (k), which is, to the best of our knowledge, the first lower bound on the maximum diameter of average-link.Finally, to complement our study, we present some experiments with 10 real datasets in which we 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-link performs better than other related methods when both cohesion and separability are taken into account.There is a vast literature about hierarchical agglomerative clustering methods. Here, we focus on works that provide provable guarantees for average-link and some other well-known linkage methods.Average-link. There are works that present bounds on the approximation of average-link regarding some criteria [Cohen-Addad et al., 2019 , Charikar et al., 2019b ,a, Moseley and Wang, 2023 , Dasgupta and Laber, 2024] . All these works but [Dasgupta and Laber, 2024] analyse the approximation of average-link regarding variants of Dasgupta'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 a 1/3-approximation with respect to the "dual" of Dasgupta's cost function. [Cohen-Addad et al., 2019] , as in our work, assumes that the proximity between points in X is given by a dissimilarity measure and shows that average-link has 2/3 approximation for the problem of maximizing CKMM (Eq. 1). [Charikar et al., 2019b] show that these approximation ratio for average-link 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 and 2/3 bounds. [Dasgupta and Laber, 2024] presents an 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) ≤ k 1.59 OPT AV (k) for every cluster A ∈ A k . Our bound on the maximum diameter of a cluster in A k incurs an extra factor of min{k, 1 + 4 ln n} 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 clustering 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, 2024] . Let C and S be the k-clustering built by these methods, respec-tively. [Arutyunova et al., 2023] shows that max-diam(C) is Ω(kOPT DM (k)) while [Dasgupta and Laber, 2024] shows that max-diam(C) is O(min{k 1.30 OPT DM (k), k 1.59 OPT AV (k)}). Regarding single-linkage, max-diam(S) is Θ(kOPT DM (k)) [Dasgupta and Long, 2005, Arutyunova et al., 2023] and Ω(k 2 OPT AV (k)) [Dasgupta and Laber, 2024] . [Ackermann et al., 2010, Großwendt and Röglin, 2015] give bounds for the case in which dist is the Euclidean metric.In terms of separability criteria, it is well known that single-linkage maximizes the minimum spacing of a clustering [Kleinberg and Tardos, 2006][Chap 4.7] . Recently, [Laber and Murtinho, 2023] observed that it 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. [Großwendt et al., 2019] shows that Ward's method gives a 2-approximation for k-means when the optimal clusters are well-separated. 
preliminaries: 
 Algorithm 2 shows a pseudo-code for average-link. The function dist AL (A, B) at line 3 that measures the distance between clusters A and B is given bydist AL (A, B) := 1 |A||B| a∈A b∈B dist(a, b).single-linkage and complete-linkage are obtained by replacing dist AL , in Algorithm 2, with dist SL (A,B) := min{dist(a, b)|(a, b) ∈ A × B} and dist CL (A, B) := max{dist(a, b)|(a, b) ∈ A × B}, respectively. Algorithm 2 Average Link 1: A n ← clustering with n unitary clusters, each one containing a point of X 2: For i = n -1 down to 1 3: (A, B) ← clusters in A i+1 for which distAL(A, B) is minimum 4: A i ← A i+1 -{A} -{B} ∪ {A ∪ B}A 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, C) ≤ avg(A, B) + avg(B, C).For two disjoint clusters A and B, the following identity holds(|A| + |B|) 2 avg(A ∪ B) = |A| 2 avg(A) + |A||B|avg(A, B) + |B| 2 avg(B).Dividing both sides by (|A|+|B|) 2, we conclude that avg(A ∪ B) is a convex combination of avg(A), avg(B) and avg(A, B), a fact will be used a couple of times in our analyses.The following notation will be used throughout the text. We use H p = p i=1 1 i to denote the pth harmonic number and A k to refer to the k-clustering obtained by average-link for the instance under consideration, which will always be clear from the context.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: We included a section at the end of the paper. 0,99 0,82 0,77 0,98 0,91 0,7 0,99 0,94 0,75 sep av 0,97 0,82 0,95 0,97 0,92 1 0,98 0,96 1 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-ratio DM 0,97 0,86 0,74 0,91 0,98 0,52 0,89 0,99 0,45 cs-ratio AV 0,96 0,82 0,74 0,96 0,85 0,59 0,97 0,82 0,65 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, e.g., if the approach was only tested on a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of 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, a 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
cohesion and separability: 
 In this section, we analyze the performance of average-link with respect to both cs-ratio AV and cs-ratio DM (Eq. 4), criteria that simultaneously take into account the separability and the cohesion of a clustering. Moreover, we contrast its performance with that achieved by other linkage methods.We first show that cs-ratio AV (A k ) ≤ 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 a fairly simple case analysis.Theorem 3.1. Let A k be a k-clustering built by average-link.Then, for every k, cs-ratio AV (A k ) ≤ 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 n points of X have pairwise distance 1, every clustering has cs-ratio AV equal to 1.In Section B.2, we present instances which show that cs-ratio AV can be Ω(n), Ω( √ n) and unbounded in terms of n for single-linkage, complete-linkage and a random hierarchy, respectively. Interestingly, all the k-clustering, with 2 < k ≤ n/2, induced by the hierarchical clustering obtained by these methods satisfy these bounds. Furthermore, since cs-ratio DM (C) ≥ cs-ratio AV (C) for every clustering C, these bounds also hold for the cs-ratio DM criterion.A natural question that arises is whether average-link has a "good" approximation with respect to cs-ratio AV . Unfortunately, the answer is no. In fact, in Section B.3 we show an instance where the approximation is unbounded in terms of n. However, as we show in the next section, average-link has a logarithmic approximation with respect to cs-ratio DM .We analyze the cs-ratio DM of average-link. The results of this section will have an important role in the analysis of both the separability and cohesion of average-link presented further.First, we show that for every cluster X in A k , the average distance of a point x ∈ X to the other points in 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 i-1 be the cluster that contains x before the ith merge involving x and let S i be the cluster that is merged with T i-1 . We prove by induction that avg(x, T i -x) ≤ ln H |Ti|-1 avg(Y, Z), which implies on the desired result because T t = X for some t. To establish the induction, we use the triangle inequality to write avg(x, T i -x) as a function of both avg(x, T i-1 -x) and avg(T i-1 , S i ), and also argue that avg(T i-1 , S i ) ≤ avg(X, Y ). Lemma 3.2. Let X, Y and Z, with |X| ≥ 2 and Y ̸ = Z, be clusters of A k . Then, for every x ∈ X, we have that avg(x, X) ≤ avg(x, X -x) ≤ H |X|-1 avg(Y, Z).The next result is a simple consequence of the previous one.Theorem 3.3. Let k ≥ 2 and let X, Y and Z, with Y ̸ = Z, be clusters of a k-clustering built by average-link. Then, diam(X) ≤ 2H |X|-1 avg(Y, Z).Proof. If |X| = 1 the result holds because diam(X) = 0. Thus, we assume that |X| > 1. Let x and x ′ be such that dist(x, x ′ ) = diam(X). We have thatdist(x, x ′ ) ≤ avg(x, X) + avg(X, x ′ ) ≤ 2H |X|-1 avg(Y, Z)where the first inequality follows from the triangle inequality and the second one due to Lemma 3.2.The next theorem shows that cs-ratio DM (A k ) ≤ 2H n and that average-link has a logarithmic approximation for the cs-ratio DM criterion. The first upper bound is a simple consequence of Theorem 3.3. Let OPT be the minimum possible cs-ratio DM . To prove the bound on the approximation we consider two cases. If OPT ≥ 1/3 the result holds because cs-ratio DM (A k ) ≤ 2 ln n ≤ 6OPT ln n. If OPT < 1/3, we argue that the clusters in the optimal clustering are "well separated" and, hence, average-link builds the optimal clustering. Theorem 3.4. For all k, the k-clustering A k built by average-link satisfies cs-ratio DM (A k ) ≤ 2H n . Furthermore, for all k, cs-ratio DM (A k ) is O(log n) • OPT where OPT is cs-ratio DM of the k-clustering with minimum possible cs-ratio DM .Proof. The inequality cs-ratio DM (A k ) ≤ 2H n is obtained by using Theorem 3.3, with X being the cluster with the largest diameter in A k and Y and Z being the clusters in A k that satisfy avg(Y, Z) = sep min (A k ). Now we prove that A k has logarithmic approximation. If OPT ≥ 1/3, then cs-ratio DM (A k ) ≤ 2H n ≤ 6OPTH n and, hence, the desired result holds. Thus, we assume OPT < 1/3, Let C * (k) be a k-clustering that satisfies cs-ratio DM (C * (k)) = OPT. The following claim will be useful.Claim 1. Let C, C ′ be two clusters in C * (k) and let a, b be two closest points in C and C ′ , that is, dist(a, b) = min{dist(x, y)|(x, y) ∈ C × C ′ }. Thus, dist(a, b) > max{diam(C), diam(C ′ )}.Proof of the claim. We assume w.l.o.g. that diam(C) ≥ diam(C ′ ). For the sake of reaching a contradiction, assume that dist(a, b) ≤ diam(C). Then, it follows from the triangle inequality that the maximum distance between a point in C and C ′ is at most 3diam(C). Thus, sep min (C * (k)) ≤ avg(C, C ′ ) ≤ 3diam(C) and so cs-ratio DM (C * (k)) ≥ diam(C)/3diam(C) = 1/3, which contradicts our assumption. □. Now, we argue that average-link constructs the clustering C * (k) when cs-ratio DM (C * (k)) < 1/3, so its approximation is 1 in this case. For the sake of reaching a contradiction, let us assume A k ̸ = C * (k). Hence, at some iteration average-link merges two clusters, say A and B, that satisfy the following properties: A ⊆ C and B ⊆ C ′ , where C and C ′ are two different clusters in C * (k). Let t be the first iteration of average-link when it occurs.Case 1) A ⊂ C or B ⊂ C ′ . Let us assume w.l.o.g. that A ⊂ C. In this case, there is a cluster A ′ at the beginning of iteration t such that A ′ ∪ A ⊆ C. We have that avg(A, A ′ ) ≤ diam(C) and by the above claim the minimum distance between A and B is larger than max{diam(C), diam(C ′ )}. Thus, avg(A, B) > max{diam(C), diam(C ′ )} ≥ avg(A, A ′ ), which contradicts the choice of average-link.Case 2) A = C and B = C ′ . If k = 2 we are done. Otherwise, there exists a cluster C ′′ ∈ C * (k) and two clusters X and Y at the beginning of iteration t such that X ∪ Y ⊆ C ′′ . Thus, it follows from the condition OPT < 1/3 that avg(X, Y ) ≤ diam(C ′′ ) < 1 3 sep min (C * (k)) ≤ 1 3 avg(C, C ′ ) ≤ avg(C, C ′ ), which again contradicts the choice of average-link.It is noteworthy that, in contrast to Theorem 3.1, the assumption that the points lie in a metric space is necessary to prove Theorem 3.4. In Section B.4 we present an instance that supports this observation. Now, we present an instance, denoted by I CS , 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-link. We note that in most of the instances presented here, including I CS , will have more than one possible execution for the methods we analyze. In these cases, we will always consider the execution that is 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 ϵ to the distance or points to break ties.Let t be an integer that satisfies t! = n; note that t = Ω( log n log log n ). Moreover, let A 0 be a set containing a single point located at position p 0 in the real line and A i , for 0 < i ≤ t -1, be a set of (i + 1)! -i! points that are located at position p i of the real line. We define B 0 = A 0 andB i = B i-1 ∪ A i , for i ≥ 1. Set p 0 = 0, p 1 = 1 and, for i > 1, p i = p i-1 + avg(A i-1 , B i-2). The set of points for our instance I CS is B t-1 and the distance between a point in A i and a point in A j is |p i -p j |. The following lemma gives properties of I CS and, in particular, how average-link behaves on it.Lemma 3.5. For i ≥ 0, we have that|B i | = (i+1)! and for i ≥ 2, we have diam(B i-2 ) = i(i-1)/2, avg(B i-2 , A i-1 ) = i + 1 and p i = i(i + 1)/2. Furthermore, for k ≤ t, average-link obtains the k-clustering A k = (B t-k , A t-k+1 , . . . , A t-1 ) and, in particular, for k = 2 it obtains the clustering A 2 = (B t-2 , A t-1 ). From Lemma 3.5, we have that sep min (A 2 ) = avg(B t-2 , A t-1 ) = t + 1 and diam(B t-2 ) = t(t -1)/2, so cs-ratio DM = t(t-1) 2(t+1) , which is Ω( log n log log n ).Furthermore, for the clustering 1) and the logarithmic approximation of average-link to cs-ratio DM is also nearly tight.A ′ = (A 0 , B t-1 -A 0 ) we have that sep min (A ′ ) = avg(A 0 , B t-1 -A 0 ) ≥ |A t-1 | |B t-1 | avg(A 0 , A t-1 ) = t! -(t -1)! t! p t-1 = (t -1) 2 2 (5) and max-diam(A ′ ) ≤ diam(B t-1 ) = (t + 1)(t + 2)/2. Thus, cs-ratio DM (A ′ ) = O(Question: For each theoretical result, does the paper provide the full set of assumptions and a 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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
separability criteria: 
 In this section, we investigate the separability of average-link. Recall that OPT SEP (k) is the maximum possible sep av of a k-clustering for (X , dist). We show that for average-link sep av is at least OPTSEP(k) k+2 ln n and that this bound is nearly tight. We also show that there are instances in which the sep av of single-linkage and complete-linkage are exponentially smaller than that of average-link.Theorem 4.2 gives an upper bound on sep av 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 k > 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 ⊆ X that satisfies avg(P ) ≥ OPT SEP (k). This holds because a set of k randomly selected points that intersect all clusters of a k-clustering with maximum sep av satisfies the the desired property (in expectation). Having this result in hands, it is enough to show that avg(P) is O((k + H n-1 )sep av (A k )).This bound on avg(P ) is obtained by relating the distance of each pair of points p, p ′ ∈ P with the average distance between clusters in A k . Let p, p ′ ∈ P and let A andA ′ be clusters in A k such that p ∈ A and p ′ ∈ A ′ . Moreover, let S be a cluster in A k , with S / ∈ {A, A ′ }. From the triangle inequality we have that dist(p, p ′ ) = avg(p, p ′ ) ≤ avg(p, A) + avg(A, S) + avg(S, A ′ ) + avg(A ′ , p ′ ). Then, by bounding both avg(p, A) and avg(A ′ , p ′ ) via Lemma 3.2, with Y and Z satisfying avg(Y, Z) ≤ sep av (A k ), we conclude that dist(p, p ′ ) ≤ 2H n sep av (A k ) + avg(A, S) + 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 . We present two instances that, together, show that the previous theorem is nearly tight. The first is the instance I CS presented right after Theorem 3.4. For I CS , the clusteringA 2 = (A t-1 , B t-2 ) built by average-link satisfies sep av (A 2 ) = avg(A t-1 , B t-2 ) = t + 1. On the other hand, Eq. (5) shows that sep av (A ′ ) = (t-1) 2 2 , for the clustering A ′ = (A 0 , B t-1 -A 0 ). Thus, for I CS , sep av (A 2 ) is O( OPTSEP(k) log log n log n ).Now, we present our second instance, denoted by I sep k . Let k be an odd number and let D and ϵ be positive numbers. The set of points ofI sep k is given by S 1 ∪ S 2 ∪ S 3 , where |S 1 | = |S 2 | = (k -1)/2 and S 3 = {s i |1 ≤ i ≤ k -2}. We have dist(x, y) = ϵ for x, y ∈ S 1 , dist(x, y) = ϵ for x, y ∈ S 2 , dist(x, y) = 1 for x, y ∈ S 3 and dist(x, y) = D ifx and y are not in the same set.For I sep k , when D is sufficiently large and ϵ is sufficiently small, A k = (S 1 , S 2 , s 1 , . . . , s k-2 ) and sep av (A k ) = O(D/k). On the other hand, the sep av of the k-clustering that has the cluster S 3 and k -1 singletons corresponding to the points inS 1 ∪ S 2 is Ω(D). Thus, sep av (A k ) is O(OPT SEP (k)/k).We note that single-linkage and complete-linkage also obtain the k-clustering A k for I sep k , so the upper bound OPT SEP (k)/k also holds for them. In Section D.3 we present instances that show that sep av is O( OPTSEP(k) √ n ) for both single-linkage and complete-linkage.The instance I sep k is particularly interesting because it also shows that natural cohesion and separability criteria can be conflicting. The key reason is that any method M with bounded approximation (in terms of n) regarding max-diam or to max-avg (Equation 3) has to build the k-clustering A k for I sep k . Thus, by analysing I sep k we can conclude that the approximation factor of M to sep av is O(1/k) and to sep min is O(1/D). The details can be found in Section D.4.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification:Guidelines:• The answer NA means that the paper does not include experiments.• 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 a 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 a 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 to 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 to 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. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to 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., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
on the cohesion of average-link: 
 In this section, we prove that max-diam(A k ) ≤ min{k, 1 + 4 ln n}k 1.59 OPT AV (k) and we also present an instance which shows that max-diam(A k ) ≥ kOPT DM (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 a cluster in A k is at most k 1.59 OPT AV (k), it cannot be employed, at least directly, to bound the maximum diameter of a cluster in A k . Thus, to obtain our (1 + 4 ln n)k 1.59 OPT AV (k) bound we combine the results of [Dasgupta and Laber, 2024] with Theorem 3.4 while for the k 1+1.59 OPT AV (k) bound we add some new ideas/analysis on top of those from [Dasgupta and Laber, 2024] .The analysis in Dasgupta and Laber [2024] keeps a 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 a family F if it belongs to some cluster in F . Thus, 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) a function of the clusters that F touches in a target k-clustering T = (T 1 , . . . , T k ). The bound on diam(F ) is then used to upper bound the diameter of the clusters in Dasgupta and Laber [2024] , we use as the target clustering the one with minimum avg-diam.F . For a k-clustering C, let avg-diam(C) := 1 k k i=i diam(C i ). As inWe explain how the families evolve along the execution of a linkage method, in particular average-link. Initially, we have k families, F 1 , . . . , F k , where F i is a family that contains |T i | clusters, each one being a point from T i . Furthermore, the families are organized in a directed forest D that initially consists of k isolated nodes, where the ith node corresponds to family F i .We specify how the families and the forest D are updated when the linkage method merges the clusters g and g ′ belonging to the families F and F ′ , respectively. Assume w.l.o.g. |F | ≥ |F ′ |. We have the following cases: case 1 |F ′ | = 1 and |F | > 1. In this case two new families are created, F new := F -{g} andF new ′ := {g ∪ g ′ }.Moreover, F new and F new ′ become, respectively, parents of F andF ′ in D case 2 |F ′ | > 1 or |F | = 1. In this case, only one family is created, F new := (F ∪ F ′ ∪ {g ∪ g ′ }) -g -g ′ . Moreover, F new becomes parent of both F and F ′ in D.We say that a family F is regular if |F | > 1. Proposition 5.1 (Proposition 3.1 of Dasgupta and Laber [2024] ). At the beginning of each iteration of average-link at least one of the roots of the forest D corresponds to a regular family.Let M be the class of linkage methods (Algorithm 2) whose function f , employed to measure the distance between clusters A and Dasgupta and Laber [2024] ). The diameter of every regular family F produced along the execution of a linkage method in M is at most k log 2 3 OPT AV (k).B satisfies {dist(a, b)|(a, b) ∈ A × B} ≤ f (A, B) ≤ diam(A ∪ B) (6) Proposition 5.2 (Proposition 5.1 ofNote that the function dist AL employed by average-link satisfies the condition given by (6) 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 k satisfies diam(S) ≤ min{k, 4 ln n + 1}k log 2 3 OPT AV (k).Proof. Let V = {T ∈ T |S ∩ T ̸ = ∅} be the set of clusters of the target clustering T that intersect S. We build a graph G whose nodes correspond to the clusters in V . At the beginning of average-link's execution, G contains the set of nodes V and no edges.At each iteration, there are two possibilities for the clusters g and g ′ that are merged by average-link: (g ∪ g ′ ) ∩ S = ∅ or (g ∪ g ′ ) ⊆ S. We define how G is updated in each case:Case 1) (g ∪ g ′ ) ∩ S = ∅. In this case, G is not updated.Case 2) (g ∪ g ′ ) ⊆ S. Let x and y be points in g and g ′ such that dist(x, y) is minimum and let T x and T y be the clusters in T that contain x and y, respectively. We add an edge of weight dist(x, y) between T x and T y . We say, in this case, that x and y are associated with the edge that links T x to T y .We need the following two claims:Claim 2. dist(x, y) ≤ k log 2 3 OPT AV (k).Proof of the claim. Let H be a regular family at the beginning of iteration t Such family does exist due to Proposition 5.1. Moreover, let h and h ′ be two clusters in H. We have thatdist(x, y) ≤ dist AL (g, g ′ ) ≤ dist AL (h, h ′ ) ≤ diam(h ∪ h ′ ) ≤ diam(H) ≤ k log 2 3 OPT AV (k),where the second inequality holds by the choice of average-link and the last inequality holds due to the Proposition 5.2. □ Claim 3. For a cluster C, let V C := {T ∈ T |T ∩ C ̸ = ∅}. Let S ′ be a cluster generated by average-link that is a subset of S. Then, when S ′ is created, the subgraph of G induced by V S ′ is connected.Proof of the claim If |S ′ | = 1 the property holds. Let S ′ be a cluster obtained by merging S 1 and S 2 . By induction, the property holds for S 1 and S 2 . Since an edge is added between nodes in V S1 and V S2 then the property also holds for S. □ Thus, at the end of the algorithm, G is connected and each of its edges has weight at most k log 2 3 OPT AV (k). Let x and y be points in S such that dist(x, y) = diam(S) and letT x = v 1 . . . v ℓ = T y be a path in G from T x to T y .Consider a sequence of points x = p 1 p ′ 1 . . . p ℓ p ′ ℓ = y, where p i and p ′ i are the points in v i associated with the edge v i-1 v i and v i v i+1 , respectively. From the triangle inequalitydist(x, y) ≤ ℓ-1 i=1 dist(p ′ i , p i+1 ) + ℓ i=1 dist(p i , p ′ i ) ≤ (k -1)k log 2 3 OPT AV (k) + k i=1 diam(T i ) ≤ (k -1)k log 2 3 OPT AV (k) + kOPT AV (k)For the logarithmic bound, let S 1 and S 2 be the two clusters that are merged to form S. At the beginning of the iteration in which S 1 and S 2 are merged, Proposition 5.1 assures that there exists a regular family, say H. Let h and h ′ be two clusters in H. By Proposition 5.2, avg(h,h ′ ) ≤ diam(H) ≤ k log 2 3 OPT AV (k). Thus, by Theorem 3.3, diam(S 1 ) ≤ 2 ln n • avg(h, h ′ ) ≤ 2 ln n • k log 2 3 OPT AV (k) and diam(S 2 ) ≤ 2 ln n • k log 2 3 OPT AV (k). Let s 1 ∈ S 1 and s 2 ∈ S 2 be such that dist(s 1 , s 2 ) = min{dist(p, q)|(p, q) ∈ S 1 × S 2 ). Since S 1 and S 2 are merged we have that dist(s 1 , s 2 ) ≤ avg(S 1 , S 2 ) ≤ avg(h, h ′ ) ≤ k log 2 3 OPT AV (k). Thus, diam(S) ≤ diam(S 1 ) + dist(s 1 , s 2 ) + diam(S 1 ) ≤ (1 + 4 ln n)k log 2 3 OPT AV (k).Theorem 3.4 of Dasgupta and Laber [2024] presents an instance with n = 2k -2 points for which single-linkage builds a k-clustering that has a cluster whose diameter is Ω(k 2 OPT AV (k)).Thus, this result together with Theorem 5.3 show a separation between average-link and single-linkage when k is Ω(log 2.41 n).Our last theoretical result is a lower bound on the maximum diameter of the clustering built by average-link. Its proof can be found in the Section E and it employs an augmented version of instance I CS , presented right after Theorem 3.4.Theorem 5.4. There is an instance for which the k-clustering A k built by average-link satisfies max-diam(A k ) ∈ Ω(kOPT DM (k)) 0,99 0,82 0,76 1 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 1 max-diam 0,85 1 0,72 0,8 1 0,48 0,76 1 0,38 max-avg 0,95 0,96 0,86 0,99 0,89 0,71 0,99 0,84 0,67 cs-ratioDM 0,96 0,92 0,63 0,95 0,97 0,4 0,93 0,99 0,33 cs-ratioAV 0,98 0,82 0,69 1 0,73 0,51 1 0,68 0,4Question: Does the paper provide open access to the data and code, with sufficient instructions 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. • Providing as much information as possible in the supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experiments: 
 In this final section, we briefly present an experiment in which we evaluate whether average-link, 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 to measure distances. For each of them, we executed average-link, complete-linkage and single-linkage, for the following sets of values of k:Small={k|2 ≤ k ≤ 10}, Medium={k| √ n -4 ≤ k ≤ √ n + 4}and Large={k|k = n/i and 2 ≤ i ≤ 10}. More details, as well as the results of our experiment with other distances, can be found in Section F.Table 6 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 a value between 0 and 1 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 S are the initials of the evaluated methods.Concerning separability criteria, single-linkage and average-link have the best results for sep av . The latter has some advantage when k is small, which is in line with its better worst-case bound for small k (results from Section 4). For sep min , average-link has a huge advantage, which is not surprising since its linkage rule tries to increase sep min at each step by merging the the clusters A and B for which avg(A, B) = sep min (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 a strong dominance. These results align with ours and those from [Dasgupta and Laber, 2024] , in the sense that they show that these linkage methods present better worst-case upper bounds than single-linkage when the comparison is made against OPT AV (k). Moreover, the advantage of complete-linkage for max-diam 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-ratio DM , average-link and complete-linkage present the best results, with the former being slightly superior for the small k and the latter being slightly superior when k is not small. average-link has a huge dominance for the cs-ratio AV criterion, which lines up with the theoretical results from Section 3.1. In summary, these experiments, together with our theoretical results, provide evidence that average-link is a better choice when both cohesion and separability are relevant. Proof. When k = n the result is valid because avg(A n ) = 0 for every A ∈ A n . We assume by induction that the result holds for k + 1 and we prove that it also holds for k. Let A and B be the clusters in A k+1 that are merged to obtain A k , so A k = A k+1 ∪ (A ∪ B) -{A, B}. Let S, T and U be clusters in A k , with T ̸ = U . It is enough to prove that avg(S) ≤ avg(T, U ).Case 1) A ∪ B / ∈ {S, T, U }. In this case, S, T, U ∈ A k+1 and, then, by induction, avg(S) ≤ avg(T, U ).Case 2) A ∪ B = S and S / ∈ {T, U }. Since A, B, T, U ∈ A k+1 , the induction hypothesis assures that avg(A) ≤ avg(T, U ) and avg(B) ≤ avg(T, U ) and the average-link rule ensures that avg(A, B) ≤ avg(T, U ). Since avg(S) is a convex combination of avg(A), avg(B) and avg(A, B), the above inequalities imply that avg(S) = avg(A ∪ B) ≤ avg(T, U ).Case 3) A ∪ B = S and S ∈ {T, U }. We assume w.l.o.g. that S = T . The induction hypothesis and the average-link rule guarantee that max{avg(A), avg(B), avg(A, B)} ≤ min{avg(A, U ), avg(B, U )} Since avg(S, U ) is a convex combination of avg(A, U ) and avg(B, U ) and avg(S) is a convex combination of avg(A), avg(B) and avg(A, B), the above inequality implies that avg(S) = avg(A ∪ B) ≤ avg(T, U ).Case 4) S ̸ = A ∪ B and A ∪ B ∈ {T, U }. We assume w.l.og. that T = A ∪ B. Since S, A, B, U ∈ C k+1 , the induction hypothesis assures that avg(S) ≤ min{avg(A, U ), avg(B, U )} Since avg(T, U ) is a convex combination of avg(A, U ) and avg(B, U ), the above inequality assures that avg(S) ≤ avg(T, U ).The following examples show that the cs-ratio AV of complete-linkage, single-linkage and a random hierarchy can be much higher than that of average-link in metric spaces. single-linkage. Consider the instance with n points x 1 , . . . , x n in the real line, where x i = 1, if i = 1, and x i = x i-1 + 1 -iϵ, for i > 1. For ϵ sufficiently small, single-linkage builds the k-clustering C = (x 1 , x 2 , . . . , x k-1 , {x k , . . . , x n }). We have that avg({x k , . . . ,x n }) is Ω(n -k) while avg(x 1 , x 2 ) = 1 -ϵ, so that cs-ratio AV (C) is Ω(n -k).complete-linkage. Let t = 2 m -1, where m is a positive integer and let p = 2(t 2 + t). We build an instance whose set of points X = A ∪ B ∪ C ∪ D ∪ E has n = 2p points, where A, B, C, D and E are sets of points in R p+1 that satisfy the following properties:• the first coordinate of the points in A ∪ B ∪ C ∪ D is the only one that has a value different than 0;• A = {a 1 , . . . , a t } and the first coordinate of a i is equal to i + 1/2;• B = {b 1 , . . . , b t } and the first coordinate of b i is equal to -(i + 1/2);• C has t 2 points and all have the first coordinate 1/2; • D has t 2 points and all have the first coordinate -1/2;• E = {e 1 , . . . , e p }, where the value of the first coordinate of e i is t 2 , the (i + 1)th coordinate has value 1.5t and all other coordinates have value equal to 0.The distance between any two points in X is given by the ℓ 1 metric. Hence, the distance between any two points in E is 3t, the distance between points in A ∪ B ∪ C ∪ D is at most 2t + 1 and the distance between a point in A ∪ B ∪ C ∪ D and a point in E is at least t 2 . For i ≤ p, let E i = {e i , . . . , e p }.Thus, for 2 < k < p = n/2, there is a way to break ties for which the k-clustering obtained by complete-linkage isC k = (A ∪ C, B ∪ D, e 1 , e 2 , . . . , e k-3 , E k-2 ).We have that max{dist(a, d)∈ A × D} ≤ t + 1, max{dist(b, c) ∈ B × C} ≤ t + 1 and max{dist(a, b) ∈ A × B} ≤ 2t + 1. Thus, we get that sep min (C k ) ≤ avg((A ∪ C, B ∪ D)) ≤ 1 (t 2 + t) 2   x∈A y∈B dist(x, y) + x∈A y∈D dist(x, y) + x∈C y∈B dist(x, y) + x∈C y∈D dist(x, y)   ≤ t 2 (2t + 1) + t 3 (t + 1) + t 3 (t + 1) + t 4 (t 2 + t) 2 ≤ 3 Since max-avg(C) ≥ avg(E k-2 ) = 3t, we get that cs-ratio AV (C k ) is Ω(t) and, hence, Ω( √ n).random hierarchy. To analyze a random hierarchy, we first need to define how it is generated. We start with a random permutation of the points in X and a clustering C containing initially the cluster comprised by all points in X . Let x 1 , . . . , x n be the points in X according to the order given by the permutation. Then, we perform the following steps until we have n clusters:• j ← a randomly selected a number in the set {1, 2, . . . , n -1}.• If the points x j and x j+1 are in the same clusterC ∈ C -split C into C ≤ = {x i ∈ C|i ≤ j} and the cluster C > = C -C ≤ .-Update C by replacing C with C ≤ and C > After t splits we have a clustering with n -t clusters. Now, we consider an instance with n points and 3 groups X, Y and Z, that satisfy |X| = |Y | = (n -1)/2 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 z to any other point is D >> n 2 . Any k-clustering, with k ≥ 3, has sep min ≤ 2 because at least two clusters do not contain z. Let k ≤ n/2. The probability that z is a singleton in the k-clusteringwhen z / ∈ {x 1 , x n } is n-3 k-3 n-1 k-1 = (k -1)(k -2) (n -1)(n -2) < 1 4Then, with probability at least 3/4, there will be a cluster C that contains z and a point in X ∪ Y , which implies that E[avg(C)] ≥ D/4n 2 . Thus, with probability at least 3/4 the k-clustering induced by the random hierarchy has sep av Ω(D/4n 2 ), when z / ∈ {x 1 , x n }. Since the probability of z / ∈ {x 1 , x n } is (n -2)/n, the same bound holds when we drop this constraint.Let n be an even number, k = 2 and ϵ a positive number very close to 0. Consider 4 set of points S 1 , S 2 , S 3 and S 4 , where S 1 = {s 1 },S 2 = {s 2 } and S 3 and S 4 have n/2 -1 points each. We have dist(x, y) = ϵ for x, y ∈ S 3 , dist(x, y) = ϵ for x, y ∈ S 4 , dist(s 1 , s 2 ) = T and dist(x, y) = T for (x, y) ∈ S 3 × S 4 . In addition, we have dist(s 1 , x) = 2T for x ̸ = s 2 and dist(s 2 , y) = 2T for y ̸ = s 1 .Clearly, the 4-clustering obtained by average-link is (S 1 , S 2 , S 3 , S 4 ). Then, to obtain a 2clustering, it merges the clusters S 1 and S 2 and, next, S 3 and S 4 , so that the final 2-clustering is A 2 = (S 1 ∪ S 2 , S 3 ∪ S 4 ), which satisfies max-avg(A 2 ) = T and sep min (A) = 2T . On the other hand, for the clustering S = (S 1 ∪ S 3 , S 2 ∪ S 4 ), we have that max-avg(S) is O(T /n 2 ) and sep min (S) ≥ T . Thus, the approximation of average-link is Ω(n 2 ) B.4 Triangle inequality is necessary for Theorem 3.4We present an instance that shows that the assumption that points lie in a metric space is necessary to establish Theorem 3.4.Let A and B be sets with n/2 -1 and n/2 points, respectively. We have dist(a,a ′ ) = 1 if a, a ′ ∈ A; dist(b, b ′ ) = 1 if b, b ′ ∈ B and dist(a, b) = 4 if (a, b) ∈ A × B. Moreover, let p be a point that is not in A ∪ B.There is a point a ∈ A for which dist(a, p) = n/2 -2 and for all other pointsa ′ ∈ A -{a}, dist(a ′ , p) = 2. Moreover, dist(p, b) = 4 for b ∈ B.For this instance average-link builds the 2-clustering A 2 = (A ∪ {p}, B). We have that diam(A ∪ p) = n/2 -2 and avg(A ∪ p, B) = 4, Thus, cs-ratio DM (A 2 ) is Ω(n). On the other hand, for the clusteringA ′ = (A, B ∪ p), cs-ratio DM (A ′ ) is O(1), so the approximation of average-link is Ω(n).Proof. The first inequality holds because avg(x, X) = |X|-1 |X| avg(x, X -x). Thus, we just need to prove the second one.Let S 1 be the first cluster merged with x by average-link and let S i , for i > 1, be the cluster merged with S 1 ∪ • • • ∪ S i-1 by average-link . Define T 0 := {x} and, for i ≥ 1,T i := T i-1 ∪ S i .Furthermore, define e i and m i as e i := avg(T i-1 , S i ) and m i := avg(x, T i -x) , respectively. Note that there is t for which T t = X and, hence, m t = avg(x, X -x).We have thatEQUATIONwhere the inequality follows from the triangle inequality.Let us consider the beginning of the iteration in which T i-1 and S i are merged. At this point we haveℓ ≥ 1 clusters Y 1 , . . . , Y ℓ such that Y = Y 1 ∪ • • • ∪ Y ℓ and ℓ ′ clusters Z 1 , . . . , Z ℓ ′ such that Z = Z 1 ∪ • • • ∪ Z ℓ .Note that there exist i and j such that avg(Y i , Z j ) ≤ avg(Y, Z). Thus, we must have e i ≤ avg(Y, Z), otherwise average-link would merge Y i and Z j rather than T i-1 and S i .To establish the result, we show by induction thatm i ≤ avg(Y, Z) • H |Ti|-1 , for i ≥ 1.The lemma is then established by taking i = t, where t satisfies T t = X.For i = 1, we have m 1 = e 1 ≤ avg(Y, Z) < avg(Y, Z) • H |T1|-1 . We assume by induction that m i-1 ≤ avg(Y, Z) • H |Ti-1|-1. By inequality ( 7)-( 8),m i ≤ m i-1 +e i |S i | |T i | -1 ≤ avg(Y, Z)   |Ti-1|-1 h=1 1 h   +avg(Y, Z)   |Ti|-1 h=|Ti-1| 1 h   = avg(Y, Z)•H |Ti|-1C Proof of Lemma 3.5Proof. First, we note that|B i-1 | = i-1 h=0 |A i | = i-1 h=0 (h + 1)! -h! = i!, for i ≥ 1.Moreover, for i ≥ 2, we have thatEQUATIONwhere the last identity follows because avg(A i , A i-1 ) = p i -p i-1 = avg(A i-1 , B i-2 ).By applying the above equation successively, we conclude thatavg(A i , B i-1 ) = (i + 1) • avg(A 1 , B 0 ) = (i + 1)and, hence,EQUATIONNow we show that at the beginning of the step (n -t) + i average-link keeps a clustering that contains the cluster B i-1 and the clusters A j , for i ≤ j ≤ t -1. First, we observe that after n -t steps average-link produces a t-clustering (A 0 , . . . , A t-1 ) since points in the same group A i are located at the same position. We analyze what happens in the remaining t -1 steps.For i = 1 the result holds because B 0 = A 0 . We assume as an induction hypothesis that at beginning of the step (n -t) + i, we have the clusters B i-1 and A j , for j ≥ i. By construction, for i ≤ r < s,avg(A s , A r ) = p s -p r > p i+1 -p i = avg(A i , B i-1 ), Moreover, i -1 = avg(A i , B i-1 ) < avg(A j , B i-1 ),for j > i. Thus, averagelink prefers merging A i and B i-1 rather than any other pair of clusters, which completes the inductive step. (k -1) 2 avg(P ) ≥ k(k -1) 2 E[avg(U )] = E   k-1 i=1 k j=i+1 dist(u i , u j )   = k-1 i=1 k j=i+1 E [dist(u i , u j )] = k-1 i=1 k j=i+1 avg(C * i , C * j ) ≥ k(k -1) 2 sep av (C * ) D.2 Proof of Theorem 4.2Proof. Let P = {p i |1 ≤ i ≤ k} be the k points given by Proposition 4.1 and let h be a function that maps each point p ∈ P into its cluster in A k . Moreover, let Y and Z be clusters inA k that satisfy avg(Y, Z) = sep min (A k ).Let p and p ′ be distinct points in P . We consider two cases:Case 1) p and p ′ belong to the same cluster A in A k . From Theorem 3.3 we have thatEQUATIONBy considering all clusters A ∈ A k we getp,p ′ ∈P h(p)=h(p ′ ) dist(p, p ′ ) ≤ p,p ′ ∈P h(p)=h(p ′ ) 2H n sep min (A k ) (14)Case 2) p and p ′ belong, respectively, to different clusters A and A ′ in A k . We consider two subcases:subcase 2.1) k = 2. In this case, from the triangle inequality, we have that dist(p, p ′ ) = avg(p, p ′ ) ≤ avg(p, A)+avg(A, A ′ )+avg(A ′ , p ′ ). By using Lemma 3.2, we have that avg(p,EQUATIONwhere the first identity holds because P = {p, p ′ }.subcase 2.2) k > 2. Let S be a cluster in A k -{A, A ′ }. From the triangle inequality, we have thatdist(p, p ′ ) = avg(p, p ′ ) ≤ avg(p, A) + avg(A, S) + avg(S, A ′ ) + avg(A ′ , p ′ ) If |A| = 1, avg(p, A) = 0 ≤ H |A| • sep min (A k ). Moreover, if |A| ≥ 2, it follows from Lemma 3.2 that avg(p, A) ≤ H |A| • avg(Y, Z) = H |A| sep min (A k ). Analogously, we have avg(p ′ , A ′ ) ≤ H |A ′ | sep min (A k ). Thus, dist(p, p ′ ) ≤ H |A| sep min (A k ) + avg(A, S) + avg(S, A ′ ) + H |A ′ | sep min (A k ).By averaging over all possible S ∈ A k -{A, A ′ } we get thatdist(p, p ′ ) ≤ •2H n sep min (A k ) + 1 k -2 S / ∈{A,A ′ } (avg(A, S) + avg(S, A ′ ))By adding over all points p ∈ P ∩ A and p ′ ∈ P ∩ A ′ we get thatp∈P ∩A p ′ ∈A ′ ∩Y dist(p, p ′ ) ≤ p∈P ∩A p ′ ∈P ∩A ′ 2H n sep min (A k ) + |P ∩ A| • |P ∩ A ′ | k -2 S / ∈{A,A ′ } (avg(A, S) + avg(S, A ′ ))By adding the above inequalities for p, p ′ ∈ P , with h(p) ̸ = h(p ′ ), we get thatEQUATIONwhere the last inequality holds because(|P ∩ (A ∪ A ′ )|) • (k -|P ∩ (A ∪ A ′ )|) ≤ k 2 /4.If we compare inequalities ( 16)-( 19) with inequality (15), we conclude that ( 16)-( 19) also hold for the subscase k = 2.Then, by adding inequality ( 14) with the inequalities ( 16)-( 19) and also using the fact sep min (A k ) ≤ sep av (A k ), we get thatp,p ′ ∈P p̸ =p ′ dist(p, p ′ ) ≤ 2H n k(k -1) 2 sep min (A k )+k A,A ′ ∈A k A̸ =A ′ avg(A, A ′ ) ≤ (2H n +k) k(k -1)sep av (A k ) 2 Proposition 4.1 ensures that k(k -1) 2 OPT SEP (k) ≤ k(k -1) 2 avg(P ) = p,p ′ ∈P dist(p, p ′ )Thus, from the two previous inequalities, we conclude thatsep av (A k ) ≥ OPT SEP (k) 2H n + k .The following instances show that the separability of both single-linkage and complete-linkage can be much lower than OPTSEP(k) log n . For single-linkage, consider the instanceX = A ∪ B ∪ {p}, where A contains n -1 - √ n points and B contains √ n points b 1 , . . . , b √ n . Moreover, we have dist(x, y) = ϵ, for x, y ∈ A, dist(b i , x) = i for every point x ∈ A and dist(b i , b j ) = |i -j|. Moreover, dist(p, x) = 1 + ϵ, for every point x ∈ A. and dist(p, b i ) = 1 + ϵ + i In this case, single-linkage builds the clustering (A ∪ B, {p}). We have that sep av (A ∪ B, p) ≤ 2, while sep av (A ∪ p, B) is Ω( √ n).Regarding complete-linkage, we consider the instance presented at Section B.2, but without the set E, that is, the set of points isX = A ∪ B ∪ C ∪ D. When k = 2, complete-linkage builds the clustering (A ∪ C, B ∪ D) that has sep av O(1) while the clustering (A, C ∪ D ∪ B) satisfies sep av (A, C ∪ D ∪ B) ≥ t 2 2 (2t 2 + t) t(2t 2 + t)) = t 2 .Since t = Θ( √ n), we conclude that the separability of complete-linkage for this instance isO( OPTSEP(k) √ n ).Recall that for instanceI sep k average-link builds the k-clustering A k = (S 1 , S 2 , s 1 , s 2 , . . . , s k-2 ). Note that max-diam(A k ) = max-avg(A k ) = ϵ. Let A ′ be a k-clustering different from A k . We argue that max-diam(A ′ ) ≥ 1 and max-avg(A ′ ) is Ω(1/k 2 ). In fact, if A ′ has a cluster A that satisfies |A| ≥ 2 and |A ∩ S 3 | ≥ 1, then max-diam(A ′ ) ≥ 1 and max-avg(A ′ ) is Ω(1/k 2 ). Otherwise, if A ′does not have such a cluster, then all points in S 3 must be singletons in A ′ . Since A ′ ̸ = A k , there is a cluster in A ′ that contains both a point in S 1 and a point in S 2 . Thus, max-diam(A ′ ) = D and max-avg(A ′ ) is Ω(D/k 2 ).Let M be the class of methods with bounded approximation regarding max-diam or to max-avg. Then any method M ∈ M builds the clustering A k . Since sep av (A k ) is O(D/k) and there is a k-clustering for I sep k whose sep av is Ω(D), we conclude that the approximation factor of any methodM ∈ M regarding sep av is O(1/k). Now, we consider sep min . We have that sep min (A k ) = 1. Let B = (B 1 , . . . , B k ) be a k-clustering with the following properties: (i) |B i ∩ S 3 | ≥ 1 for each i ≤ k -2; (ii) each B i , with i ≥ 2, has exactly one point in S 1 ∪ S 2 (iii) B k-1 has a point in S 1 and B k has a point in S 2 .We have that sep min (B) is Ω(D). Thus, any method M ∈ M has approximation O(1/D) to sep min , that is, the approximation is unbounded in terms of n.Proof. Let I be the instance obtained by augmenting the instance I CS , presented right after Theorem 3.4, with the points x 0 , . . . , x t-1 , where dist(x i , A i ) = t + 1 + ϵ and for i ̸= j, dist(x i , x j ) = |p j -p i | + 2(t + 1 + ϵ) and dist(x i , A j ) = |p j -p i | + t + 1 + ϵ.Consider t = k. We argue that the (k + 1)-clustering obtained by average-link for I consists of the clusters (B k-1 , {x 0 }, . . . , {x k-1 }). In fact, in its first steps average-link obtains the 2kclustering (A 0 , . . . , A k-1 , x 0 , . . . , x k-1 ) since the distance between points in A i is 0. In the next k -1 steps, average-link does not make a merge involving a point x i because the average distance of x i to any other cluster is larger k + 1 and, by Lemma 3.5, the average distance between B i-2 and A i is i + 1 ≤ k + 1. Thus, the execution of average-link for I merges the same clusters that are merged in the instance I CS and, then, ends up with the (k+1)-clustering (B k-1 , {x 0 }, . . . , {x k-1 }).Thus, for instance I, the maximum diameter of a cluster inA k is at least diam(B k-1 ), which is Ω(k 2 ), while the k-clustering (x 0 ∪ A 0 , . . . , x k-1 ∪ A k-1 ) has diameter k + ϵ.Table 2 presents our datasets with their main characteristics. 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 α, the height of the bar is given by the average of m k for every k considered in our experiments, where m k is the ratio between the value of criterion α achieved by method M on dataset D divided by the best value for criterion α, among those achieved by single-linkage, average-link and complete-linkageon dataset D. Regarding the cohesion criteria complete-linkage presents the best results for max-diam, followed by average-link. For max-avg, again complete-linkage and average-link are the best, with the latter having a slight advantage.In terms of the separability criteria, average-linkis much better than the other methods for sep min , while for sep av there is a balance between average-link and single-linkage.For the criteria that combine cohesion and separability, average-linkis superior for cs-ratio AV , while there is a balance between average-link and complete-linkage for cs-ratio DM .Table 3 and 4 show the results for the experiment described in Section 6, when the Euclidean distance is replaced with the ℓ 1 and ℓ ∞ 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-link is small. Indeed, an entry (average) close to 1 (e.g. 0.96) cannot have an underlying large variance because 1 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 is usually small. In the supplemental material, we have .csv files with our full results. • 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. 0,99 0,81 0,75 0,99 0,86 0,66 0,99 0,9 0,71 sep av 0,98 0,83 0,93 0,96 0,89 1 0,97 0,95 0,99 max-diam 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-ratio DM 0,96 0,91 0,62 0,96 0,98 0,38 0,88 0,99 0,32 cs-ratio AV 0,98 0,8 0,71 1 0,79 0,51 1 0,76 0,51• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, 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 not include experiments.• The experimental setting should be presented in the core of 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, or as supplemental material. 7. Experiment Statistical Significance Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [No] Justification: We have not included error bars because they do not help much in our case. However, from the tables and our analyses, the reader should have a clear idea of the variability of our results (see last paragraph of Section F). Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or 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. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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 are 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 in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? 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.• 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 of compute required for each of the individual experimental runs as well as 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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 a clear societal impact that deserves to be mentioned.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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 not tied to particular applications, let alone deployments. However, if there is a 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, it 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 as 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 or unintentional) misuse of the technology. • If 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). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: There are only (very) minor weaknesses:

1.) No new algorithmic contribution, e.g., some improvement to average linkage that could improve some of these bounds.

2.) Most results only hold for points in metric space. 

3.) Font size changes from page 3 onwards (line 138)
questions: 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: limitations: yes discussed
paper_summary: paper_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.
strength_weakness: strength_weakness: I think the paper has several merits as listed above. Weaknesses include:
* I think the presentation of Table 6 could be clearer -- I think directly presenting the results per dataset per method would be clearer.
* Perhaps more text could be used to describe the novelty of proof techniques
* Given some of the motivations, I wonder if more of the analysis on random hierarchies should be included in the main paper.
questions: questions: Can you say more about the relationship between your work and [Großwendt et al., 2019]?
limitations: limitations: Adequately addressed the limitations
paper_summary: paper_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.
strength_weakness: strength_weakness: I don't have any specific questions for the authors, as I'm mostly satisfied with the paper.
questions: 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: limitations: I don't see any additional limitations (apart from what is already mentioned), and I'm mostly satisfied with the paper.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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.
- 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).
questions: 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?
- 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?
- 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?
- 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?

Minor points:
- The heading "Smal" in the tables is missing an l.
- 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: Limitations are briefly discussed at the end of the main text.

Comments: comment: Thank you for your replies! The clarifications helped me understand the paper better; I am raising my scores regarding presentation and contribution, and maintain my overall rating.
I thank the authors and keep my original rating.
I thank the authors for the rebuttal, and I maintain my positive evaluation of the paper. I also agree that the metrics are more natural and easier to interpret than Dasgupta's cost function.