Hierarchical Clustering better than Average-Linkage

1 Introduction

• HC represents datapoints as leaves in a dendrogram, providing information across granularities without requiring a fixed number of clusters.Average-Linkage is a widely used agglomerative procedure.Source: §1 · p. 1
• Dasgupta’s similarity objective initiated objective-driven analysis of HC by favoring heavy edges being cut deeper in the tree.Moseley and Wang introduced a related objective, while Cohen-Addad et al. studied a dissimilarity-based maximization variant.Source: §1 · pp. 1–2
• Average-Linkage achieves at most 1/3 for the Moseley–Wang similarity objective and at most 2/3 for the Cohen-Addad et al. dissimilarity objective in the worst case.These guarantees match those of a random solution.Source: §1 · p. 2
• The matching random-solution ratios raise whether these objectives are approximation resistant or whether algorithms can strictly outperform Average-Linkage.The question is motivated by assessing how well the objectives explain Average-Linkage’s performance.Source: §1 · pp. 2–3
• The paper gives a 1/3 + ϵ approximation for the similarity objective and a 2/3 + δ approximation for the dissimilarity objective, for constants ϵ, δ > 0.The similarity algorithm uses an SDP-guided initial partition followed by random refinement; the dissimilarity algorithm uses greedy peeling followed by max-cut.Source: §1 · p. 3
• The results also question whether these objectives are the right measures for evaluating Average-Linkage clustering.The authors frame objective design as an unresolved issue requiring further research.Source: §1 · p. 3

2 Notations and Basics

• OPT denotes either the optimal hierarchical-clustering solution or its objective value, while Average-Linkage denotes both its tree and objective value.For similarity weights, Average-Linkage maximizes average similarity; for dissimilarity weights, it minimizes average dissimilarity.Source: §2 · pp. 3–4
• The paper calls HC-OBJ-2 similarity-HC and HC-OBJ-3 dissimilarity-HC, and uses W for the graph’s total edge weight.These conventions support the later approximation analyses.Source: §2 · p. 4

3 Tight Instances for Average Linkage Analysis

• The two constructions establish that the previously known average-linkage bounds are tight for both hierarchical-clustering objectives.The section explicitly presents these examples as constructions proving tightness of the known performance bounds.Source: §3 · p. 4, §3.1 · p. 5, §3.2 · p. 5

3.1 Average-Linkage for similarity-HC is a tight 1 3-approximation

• The similarity-HC instance uses n^1/3 vertical cliques of size n^2/3 and n^2/3 horizontal cliques of size n^1/3, with horizontal edges weighted 1 + ϵ.The construction augments unit-weight vertical cliques with same-order horizontal cliques whose slightly larger weights steer average-linkage toward the unfavorable decomposition.Source: §3.1 · pp. 4–5
• 1/3 + o(1) is a tight approximation ratio for average-linkage on the similarity-HC objective.The construction makes most weight lie in subclusters that an optimal tree merges low, while average-linkage cuts it higher, reducing the HC-OBJ-2 multiplier.Source: §3.1 · pp. 4–5

3.2 Average-Linkage for dissimilarity-HC is a tight 2 3-approximation

• 2/3 + o(1) is a tight approximation ratio for average-linkage on the dissimilarity-HC objective.The tight instance starts from a complete bipartite graph with unit weights and removes a perfect matching.Source: §3.2 · p. 5

4.1 SDP relaxation for similarity-HC

• The similarity-HC method formulates an SDP relaxation and uses vector geometry with spreading constraints to guide a hyperplane-rounded initial partition.The spreading constraints force vectors to remain separated, while monotonicity constraints preserve separation across levels.Source: §4 · p. 5, §4.1 · pp. 6–7

4.2 Combining SDP rounding and random to beat average-linkage

• After the initial SDP-based cut, the algorithm recursively applies uniformly random cuts to each resulting piece until singleton clusters are reached.Random-always provides the comparison algorithm, while SDP-first-then-random uses the SDP only to choose the first partition.Source: §4.2 · p. 7
• 0.336379 > 1/3 is the approximation guarantee achieved by the better of SDP-first-then-random and random-always algorithms for similarity-HC.The guarantee is obtained by balancing two cases according to the optimum value and setting ϵ2 ≈ 0.139.Source: §4.2 · p. 7, §4.3 · p. 11

4.3 Analysis (Proof of Theorem 4.2)

• The analysis decomposes the objective into edge–vertex triplets and derives explicit separation probabilities from the angles between SDP vectors.A closed-form expression for P[Ei,j|k] avoids the direct three-dimensional geometric calculation and supports the approximation bound.Source: §4.3 · pp. 8–9

5 Beating Average-Linkage for Dissimilarity-HC

• 2/3: average-linkage and random always fail to obtain a better worst-case approximation factor for dissimilarity-HC.Random always has objective value 2/3 nW on every instance, while a bipartite graph can have optimum nW.Source: §5 · p. 11

5.1 The “Peel-off First, Max-cut Next” Algorithm

• Peeling high weighted-degree vertices before applying max-cut avoids instances where max-cut splits a small dense clique into nearly symmetric halves.The algorithm then recursively completes the two sides with random trees.Source: §5.1 · p. 11
• 0.667078 > 2/3: combining “peel-off first, max-cut next” with “random always” yields an α-approximation for dissimilarity-HC.The guarantee is obtained for a suitable parameter γ.Source: §5.1 · p. 11
• The algorithm peels vertices, applies Goemans-Williamson max-cut to the remainder, and uses random always within the resulting two pieces.The peeling phase adds singleton cuts; the max-cut phase supplies the top-level partition.Source: §5.1 · p. 12

5.2 Analysis (Proof of Theorem 5.1)

• The proof splits into OPT below or above (1−ϵ)nW, using random always in the low-OPT case and structural charging in the high-OPT case.In the high-OPT case, the optimum tree is decomposed into layered clusters and the algorithm’s contributions are charged to red and blue edge classes.Source: §5.2 · p. 12
• In the charging analysis, peeling controls red-edge contributions, while max-cut controls blue cut contributions and at least half of the blue-chain contribution.Blue-chain contributions are small because they involve low-degree vertices in small pieces.Source: §5.2 · pp. 13–14
• The proof bounds the remaining internal weights, incorporates the ρGW ≈ 0.878 max-cut guarantee, and optimizes γ, ϵ, and δ to obtain Theorem 5.1.The final comparison balances the guarantees from the two cases.Source: §5.2 · pp. 14–15

6 Conclusion - Discussion

• The paper designs hierarchical-clustering algorithms that outperform Average-Linkage and frames this as progress toward understanding suitable HC objectives.The authors state that further research is needed before objectives consistently yield high-quality outcomes.Source: §6 · p. 15
• A central limitation is that every edge is eventually cut in a hierarchical tree, making the choice of cut penalties decisive but difficult to design.The paper notes that current objectives may not fully explain when Average-Linkage performs well in practice.Source: §6 · p. 15

A Deferred Proofs of Section 3

• A bottom-up strategy that first merges edges inside K_{n^(2/3)} cliques achieves an HC value close to nW, lower-bounding the optimum.The construction relies on many clique edges receiving large non-leaf multipliers.Source: A Deferred Proofs of Section 3 · p. 17
• Average-Linkage can be forced to merge K_{n^(1/3)} structures first, making its initial contribution O(n^(7/3)) before merging weighted supernodes.The later supernode calculation is bounded by 1/6 n^(8/3) + O(n^(7/3)).Source: A Deferred Proofs of Section 3 · pp. 17–18
• A single cut (L, R) can collect all weight and give the optimum value nW in the constructed instance.The remainder of the tree can then be completed arbitrarily.Source: A Deferred Proofs of Section 3 · p. 18
• With many zero-weight edges, Average-Linkage can merge perfect-matching endpoints first; the resulting supernode calculation yields a value based on the 2/3 factor.Small positive perturbations can break ties without changing the overall outcome.Source: A Deferred Proofs of Section 3 · p. 18

B Deferred Proofs of Section 4

• The lower-bound program decomposes over angle variables, allowing symmetry to reduce the analysis to a simpler minimization problem.The proof studies the variables associated with two distinguished vertices.Source: B Deferred Proofs of Section 4 · p. 18
• Concavity of cosine forces the first constraint to be tight and implies that an optimum has nearly all relevant angles equal to π/2.Otherwise, redistributing angle mass would create slack while preserving or improving the objective.Source: B Deferred Proofs of Section 4 · p. 18
• The resulting counting argument lower-bounds the optimal value of P_lower-bound using the number of angles equal to π/2.The proof concludes with a bound involving n−2.Source: B Deferred Proofs of Section 4 · p. 18
• The final approximation factor is obtained by balancing two cases, solving for one parameter as a function of another, and numerically maximizing the resulting expression.The function peaks around ϵ_2 ≈ 0.139.Source: B Deferred Proofs of Section 4 · p. 19

• Claim 1 bounds contributions from subtrees rooted at L_k and R_k using their sizes being at most (1−δ)n.Source: C Deferred Proofs of Section 5 · p. 19
• The proof combines ALG_peel and ALG_cut using bounds from Lemmas 5.2 and 5.4.Source: C Deferred Proofs of Section 5 · p. 19
• The final parameter choice balances the factors arising from Case 1 and Case 2.Source: C Deferred Proofs of Section 5 · p. 19
• γ ≈ 11.1 and ϵ ≈ 0.000612 are the final optimal parameter values obtained by maximizing over γ.The negative solution is discarded because √ϵ ≥ 0.Source: C Deferred Proofs of Section 5 · p. 20