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

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.

Strengths

- The authors analyse the properties of average-link rigorously and provide mathematical proofs for their claims. - 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. - 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

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

Rating

6

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

Limitations are briefly discussed at the end of the main text.

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.

Strengths

+ The paper tackles an interesting topic + The Related Work section is extensive, and the proposed approaches are well-placed in the existing literature + The methodology is adequately sound and well-explained + 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.

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.

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

I don't see any additional limitations (apart from what is already mentioned), and I'm mostly satisfied with the 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.

Strengths

The paper presents an interesting analysis of average linkage as a hierarchical clustering method. The results help to explain the effectiveness of the method. Strengths include: * Thoughtful analysis of a popular and well studied method * Understanding of cost functions and how average linkage optimizes them * Empirical analysis following theoretical results

Weaknesses

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

Can you say more about the relationship between your work and [Großwendt et al., 2019]?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Adequately addressed the limitations

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.

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. 2.) The experimental results also show fairly robustly that the theoretical guarantees can be seen in practice as well. 3.) The paper is well-written and enjoyable to read.

Weaknesses

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

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.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

yes discussed