acceptodds
Under review as a conference paper at ICLR 2027

Fast linkage algorithm for -medians hierarchical clustering

Abstract

Hierarchical linkage methods are widely used due to their simplicity, interpretability, and ability to produce full clusterings across all values of . The -medians objective is a fundamental measure of cluster compactness, capturing average distances to representative points. Despite its importance, existing hierarchical linkage methods that align with this objective are either computationally expensive or lack scalability. We introduce two simple hierarchical linkage algorithms, r-msi and f-msi, which, to the best of our knowledge, are the first linkage methods aligned with the -medians objective to achieve subcubic time complexity. Our methods can be seen as efficient variations of msi, a linkage method that runs in cubic time. r-msi runs in time while f-msi runs in time and produces inversion-free dendrograms. Notably, f-msi admits an implementation for datasets represented as weighted graphs that runs in time, where and are the number of vertices and edges of the graph, as well as a subquadratic-time implementation in which the merge rule is -approximated. Experiments on several datasets from different domains show that our algorithms present strong empirical performance, achieving clustering quality close to msi while being up to 75 times faster. Moreover, f-msi scales to graph datasets with over edges.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Hierarchical Clustering, Algorithms, Interpretability, k-medians, medoids

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_LDsNOpenReview ↗
Rating
4(+2)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper presents two hierarchical linkage methods, f-msi and r-msi that accelerate/approximate and build upon the existing msi (minimum sum increasing). Main goal is to create a hierarchy of clusterings that have a small k-Median loss, i.e., where the sum of distances to the center is small. The authors tackle the main problems of msi, namely the cubic runtime and having inversions in the hierarchy (i.e., higher merging distances might occur further down in the hierarchy than smaller values). The changes to msi are rather simple and straight forward, but do the job and result in a significantly reduced runtime and complexity while yielding good results regarding the k-Median loss. The paper is written well and easy to follow.

Critical strengths

S1) First sub-cubic method for a hierarchy that optimizes k-Median loss on arbitrary underlying graphs/distances. The problem is rather fundamental and I was surprised that it has not been solved before.

S2) The paper is written and explained well. It finds a simple solution to a rather fundamental problem and the experiments show that indeed, the resulting clusterings have low k-Median losses.

Critical weaknesses

W1) Experiments are weird and overall not convincing:

  • The runtime table uses a totally different set of datasets than the ARI table. These are the only two tables, most other experiments are line diagrams comparing the k-Median losses.

    • Why do you use different datasets here? Is one set the set where your method is faster, and the other set contains datasets where your method works better? To prevent such questions, use the same datasets for both aspects, include the full set of results in the appendix, or state exactly your selection criteria.
    • It is only mentioned very briefly that the runtime table does not contain the pure running time of the competitors, but the authors add a post-processing phase to compute the medoids in O(n^2). This might add a large part of the runtime- these two runtimes need to be reported separately. If users require medoids, it might be cheaper to read them out during the method's runtime than in a possibly expensive postprocessing step.
  • For the comparison of k-Median losses, the authors' methods f-msi and r-msi, are compared to the optimal result of PAM, complete linkage, and average linkage (based on their ratio to msi's results). I wonder why no newer competitor (e.g., the discussed TeraHAC and CLNSS (Cohen-Addad 2021)) is included in Tab.1, Fig.1, or Tab.2.

  • In Fig. 2, f-msi is compared to TeraHAC on one dataset with only two parameter settings of TeraHAC. Besides the way too small font size, the right part of the figure is barely readable as the lines seem to overlap completely? Also, the tested numbers of clusters are going up to 600 000 clusters which seems high to me - a zoom on smaller values for k would also be interesting here. For the comparison on large scale data, I'd expect more than one competitor only. (see W2)

  • I'm missing ARI results on the full set of tested benchmark datasets. Only a small selection of ten datasets is shown in the main paper, even though different datasets were used elsewhere. The authors state that ARI is (only) their secondary goal, but it would help the motivation to know for which type of datasets their methods yield good results. Notably, the ARI comparison is only against the original msi and the most relevant but old, basic methods (avg-link, complete-link, PAM). Why does Table 2, for example, not contain results of TeraHAC or CLNSS (Cohen-Addad 2021)?

W2) The papers' evaluation, comparison, and discussion are quite limited: its main competitor is msi, and reaching the optimal k-Median clustering given by PAM. Avg-linkage and complete-linkage are also considered (and single-linkage was apparently tested but left out for clarity according to the appendix). However, it would be interesting to see a comparison regarding k-Median losses compared to approximative methods and hierarchical k-Median solutions working on HSTs, which have been studied more extensively already than the general case discussed in this paper and find optimal solutions very fast (see, e.g. [1], [2], [3], Cohen-Addad 2021).

Mixed stuff:

  • Text in Figures, especially in the appendix, is way too small. None of the figures in the appendix is readable, which is especially relevant as the y-axis has very different scales.
  • In Table 1, underlining the best results (or making them bold, or coloring the cells according to the values) could help with readability.

[1] Benkoczi, R., & Bhattacharya, B. (2005, October). A new template for solving p-median problems for trees in sub-quadratic time. In European Symposium on Algorithms (pp. 271-282). Berlin, Heidelberg: Springer Berlin Heidelberg.

[2] Draganov, A., Weber, P., Jørgensen, R., Beer, A., Plant, C., & Assent, I. (2026). Ultrametric Cluster Hierarchies: I Want ‘em All!. Advances in Neural Information Processing Systems, 38, 128190-128241.

[3] Awasthi, P., Blum, A., & Sheffet, O. (2010, October). Stability yields a PTAS for k-median and k-means clustering. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (pp. 309-318). IEEE.

Questions for authors

Q) What does 'f' and 'r' in f-msi and r-msi actually stand for?

Q) Can you add the number of ground truth clusters to table 3?

3 comments
AuthorsOpenReview ↗

Answers and comments to Reviewer LDsN (Part I)

Thank you for recognizing the relevance of the problem, the computational contribution, and the clarity of the writing and explanations.

We updated the submitted PDF to improve the readability of the appendix figures by increasing their font sizes. We added rows to Table 4 and plots to Figure 6 in Appendix I.5, extending the comparison with Cohen-Addad et al. (2021). Finally, we added the requested kk in Table 3. No other changes were made, to preserve the references used throughout the rebuttal. Accordingly, some of the clarifications provided below are not yet reflected in the updated PDF.

Below, we clarify several aspects of the experimental evaluation. In particular, we explain that the comparison with CLNSS was already included in the original submission (Appendix I.5), and we clarify the dataset selection criteria, addressing what we understand to be the main concerns raised in the review.

Weakness 1 [Selection of datasets, butlet 1.1]

The datasets in Tables 1 and 2 were not selected based on whether they favored our methods in runtime or clustering quality.

Table 1 reports datasets of moderate size on which the quadratic-time methods took more than one second, as stated on page 8 (lines 393-396). We removed Beans, pendigit, and LetterRecognition due to space constraints. Their runtime results are consistent with the trends reported in the table.

Table 2 reports ARI on classification datasets with ground-truth labels; datasets without such labels (e.g. regression datasets) cannot be evaluated using this criterion. Ozone and News20 also have ground-truth labels but were omitted from Table 2 due to space constraints. We added Ozone and News20 to the expanded ARI table, which also includes CLNSS (Cohen Addad et. al 21). See the response for bullet 4 below.

Reuters has multi-label annotations rather than a single class label per document and was therefore not included in the ARI evaluation. Wine Quality has an ordinal quality score as its target. We treated it as a regression dataset and therefore excluded it from the ARI evaluation.

We will clarify these selection criteria in the revised manuscript.

Weakness 1 [Breakdown of Running times, bullet 1.2]

Following the reviewer's suggestion, we separately report dendrogram construction and medoid post-processing times (Algorithm of Appendix G.1) for the methods requiring the latter. msi and r-msi compute exact medoids during execution and are therefore omitted below. All three methods use the same post-processing algorithm.

Times are in seconds (mean ± standard deviation over three runs), excluding distance matrix computation. These experiments were rerun, so the totals may differ slightly from those in Table 1.

Table A: Dendrogram construction time (s)

Datasetnavg-linkcomplete-linkf-msi
Allen Brain50008.3 ± 0.049.0 ± 0.118.2 ± 0.09
Anuran719317.5 ± 0.1919.6 ± 0.2418.6 ± 0.15
BookRatings50008.2 ± 0.059.3 ± 0.038.0 ± 0.05
Ecoli45146.6 ± 0.067.2 ± 0.106.7 ± 0.09
MovieLens604012.4 ± 0.0814.4 ± 0.1712.8 ± 0.06
News2050008.3 ± 0.119.3 ± 0.108.2 ± 0.14
Ozone36943.2 ± 0.083.6 ± 0.133.3 ± 0.07
Parkinsons587410.7 ± 0.1311.7 ± 0.1411.0 ± 0.12
Reuters50008.5 ± 0.039.2 ± 0.028.6 ± 0.03
Rice38094.6 ± 0.324.9 ± 0.154.5 ± 0.18
Wine489814.7 ± 0.0615.9 ± 0.3315.2 ± 0.11

Table B: Medoid post-processing time (s)

Datasetnavg-linkcomplete-linkf-msi
Allen Brain50006.2 ± 0.276.1 ± 0.266.1 ± 0.25
Anuran719312.6 ± 0.6312.5 ± 0.5512.7 ± 0.57
BookRatings50006.9 ± 0.025.9 ± 0.036.6 ± 0.04
Ecoli45144.6 ± 0.294.7 ± 0.234.7 ± 0.23
MovieLens604011.3 ± 0.488.8 ± 0.409.1 ± 0.38
News2050006.4 ± 0.096.1 ± 0.076.6 ± 0.11
Ozone36942.9 ± 0.063.0 ± 0.053.0 ± 0.06
Parkinsons58748.3 ± 0.388.5 ± 0.378.5 ± 0.38
Reuters50006.0 ± 0.046.0 ± 0.036.0 ± 0.05
Rice38093.4 ± 0.063.4 ± 0.073.5 ± 0.06
Wine489810.2 ± 0.4810.0 ± 0.1510.1 ± 0.12

The medoid post-processing accounts for a substantial share of the reported total time (approximately 40–50% for all three methods). Excluding this step, f-msi's dendrogram construction time remains comparable to those of average- and complete-linkage.

Regarding the suggestion to extract medoids during execution, the average- and complete-linkage implementations evaluated do not maintain exact medoids, so these cannot simply be read out. We will add both tables to the revised appendix.

AuthorsOpenReview ↗

Answers and comments to Reviewer LDsN (Part II)

Weakness 1, bullet 2. [Other Baselines]

As mentioned in lines 476-480 of the original submission, the comparison with CLNSS (Cohen-Addad et al. (2021) is already included in Appendix I.5:

  • Figure 6 compares clustering k-medians costs,

  • Table 4 reports running times,

  • Figure 7 evaluates datasets with 288,000 and 2,075,259 points.

We have now extended this comparison to 15 tabular datasets. Both f-msi and approx-fmsi achieve lower k-medians costs than CLNSS across all 15 datasets.

This directly addresses the request for comparison with an HST-based hierarchical k-medians method (Weakness 2). We have additionally extended the ARI comparison to include CLNSS on all twelve datasets in the expanded ARI Table 2 (see our response to bullet 4 below).

TeraHAC is evaluated on Amazon Reviews in Figure 2 and on ca-CondMat in Appendix Figure 5. TeraHAC approximates average linkage (e.g. the parameter ϵ=0\epsilon=0 recovers the latter) and is designed for large graph instances. We therefore use exact average linkage as a baseline on moderate-sized datasets and TeraHAC in the graph scalability experiments.

Weakness 1, bullet 3 [TeraHAC Experiment]

For TeraHAC, we used the recommended parameter setting ϵ=0.1\epsilon=0.1, and tested both t=0t=0 and t=0.1t=0.1. By design, since both configurations use the same value of ϵ\epsilon, they produce the same sequence of merges until the run with t=0.1t=0.1 terminates, explaining why the corresponding curves overlap over their shared range. This early termination reduces running time but leaves the dendrogram with fewer internal nodes.

The graph-based version of f-msi achieves lower kk-medians costs than TeraHAC over most of the evaluated range, with substantial improvements for many values of kk.

Weakness 1, bullet 4. [ARI on the full set of datasets]

As noted above, it is not possible to compute ARI for all datasets since many of them do not have ground truths. Following the reviewer’s suggestion, we have extended the comparison to include CLNSS on all ten datasets in Table 2, also adding the datasets Ozone and News20.

The table below reports its mean ARI over five random seeds. r-msi and f-msi outperform CLNSS in terms of ARI on almost all evaluated datasets.

datasetnkaveragecompletef-msirmsimsipam_meanCLNSS_mean
anuram7193100.000.860.450.440.470.410.00
banknote137120.080.110.600.010.080.050.03
beans1361170.320.420.460.630.720.620.15
breast_cancer68320.780.510.800.770.770.84-0.02
letter_recognition5000260.070.070.140.130.160.120.04
mice55280.230.140.230.300.350.240.00
iris15030.720.710.670.650.640.740.35
News205000200000000
Ozone369420-0.040.030.030.01-0.010.01
pendigits5000100.380.410.640.590.640.580.01
parkinsons_small1952-0.03-0.030.170.200.110.17-0.03
rice380920.000.180.630.560.570.690.16

W2 [Other Baselines].

As detailed in our response to W1, bullet 2, Appendix I.5 already compares our methods with CLNSS (Cohen-Addad et al., 2021), an HST-based hierarchical k-medians method, in terms of both clustering cost and running time, including large-scale datasets.

These experiments show a clear trade-off: CLNSS is faster, whereas our methods achieve substantially lower k-medians costs. We will make these comparisons more prominent in the revised manuscript.

Mixed Stuff and Questions

The letters (f) and (r) stand for “fast” and “relaxed,” respectively. We will make this explicit in the paper. The updated PDF also includes the number kk of ground-truth clusters in Table 3 for datasets with ground-truth labels.

Dear authors, thanks for putting work into the rebuttal and clarifying many of my concerns.

I'd still increase the font sizes, and especially the text, figure legend, and axis description in Figures 6 and 7 are not readable. Table 4 is now too big for the page, flowing into the right border, and has a typo in the last row. Table 1 is also flowing into the right border.

[Other Baselines] That you compare to CLNSS is not described in the caption of Fig. 6 in Appendix I.5, and even in the current version, readers need to zoom into 300% in order to see that one of the lines is CLNSS. If you change this and also also refer to the figure when you describe the experiment in the main part of the paper, it is less likely that readers oversee it.

Having only one or two baselines is still a rather low number of competitors. Even if there are not many hierarchical competitors, having a baseline with several runs of a fast, non-hierarchical k-Center could help to better assess the quality and runtime gains of your method (else, add a discussion on potential baselines and why they do not make sense to compare to, if possible).

[TeraHAC Experiment] While Fig. 2b shows the ratio between k-medians cost of TeraHAC and f-msi, Fig. 2a only shows the running times of two parameter settings for TeraHAC- why is the running time of f-msi not shown here?

Reviewer_xFnHOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This is a hierarchical clustering paper that studies k-medians objective (usually used for cluster compactness). Such linkage based approaches construct the hierarchical tree bottom up. This paper introduces 2 simple linkage algorithms called r-msi and f-msi according to the authors. The algorithms achieve subcubic time and are the first to align with k-medians objective.

In terms of theory, the authors analyze the runtime of the proposed algorithms and in terms of experiments they demonstrate how to get a 75x speedup.

Prior work on Minimum Sum Increasing, msi, is an analogue of the partitioning around medoids method, where at each round, we greedily merge pairs of clusters whose union has small increase in terms of k-medians. The obvious drawback here is the cubic runtime and the potential inversions in the dendrogram. The authors instead of msi, the proposed the two abovementioned variants with better runtime. Their r-msi algorithm relies on the medoid of a cluster A and a cluster B, instead of their union, and using another objective surrogate they also propose f-msi, yet another variant.

Critical strengths

-i believe the strongest part is the experimental evidence that their methods are faster, while producing reasonable accuracy.

Critical weaknesses
  • the paper is presenting a twist in the linkage objective function for hierarchical clustering. In principle, one can come up with several such variants so the novelty is quite lacking. In particular, I find a serious omission to the Exponential Linkage paper (see "Supervised Hierarchical Clustering with Exponential Linkage" by Nishant Yadav Ari Kobren Nicholas Monath Andrew McCallum) that studies a family of linkage methods. I believe a comparison is needed.

  • The guarantees of the proposed algorithms come in terms of worst-case runtimes, without an analysis of accuracy guarantees or approximation bounds.

-I believe the experiments should be on larger datasets not just n=7K nodes.

Questions for authors

-Please do a comparison to "Supervised Hierarchical Clustering with Exponential Linkage" by Nishant Yadav Ari Kobren Nicholas Monath Andrew McCallum, from ICML.

-are there guarantees for your algorithms in special families of input datasets? Like those with a hierarchical clustering strucutre?

-are there guarantees in terms of hierarchical clustering objectives like the one proposed by Dasgupta [STOC 2016]?

-given that the paper is essentially an experimental paper, what is the performance of your algorithms on much larger datasets?

Reviewer_q93FOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The paper introduces two new linkage algorithms for the hierarchical kk-median problem. The two main algorithms of the paper are the following:

  • r-msi, that merges in every iteration the two cluster A,BA,B minimizing
min⁡{cost(mA,A∪B),cost(mB,A∪B)}−cost(mA,A)−cost(mB,B)\min\{cost(m_A, A\cup B), cost(m_B, A\cup B)\}-cost(m_A, A)-cost(m_B, B)

, where cost(c,C)cost(c, C) is the kk-median cost of cluster CC with center cc and m_C is the mediod of a point set CC. Afterwards the center of the resulting cluster is set to mA∪Bm_{A\cup B}.

  • f-msi, that merges in every iteraration the two clusters A,BA,B that minimizes
min⁡{∣A∣,∣B∣}⋅dist(rA,rB)\min\{|A|, |B|\}\cdot dist(r_A, r_B)

and sets the center of the resulting cluster to the center of the larger of the two clusters afterwards. Both these algorithms can be implemented to achieve subcubic running time, making these the first linkage methods for the kk-median function to achieve this bound. Furthermore, it is shown that r-msi yields a 5-approximation to an optimal kk-clustering if the optimal kk-clustering is nice in the sense that it satisfies some separation criterium. The paper ends in an experimental section that compares the runtime and the quality of results to those of previously existing algorithms.

Critical strengths

To my knowledge there are no other linkage methods that are designed for hierarchical kk-median that achieve subcubic running time. The proposed merging rules are intuitive and easy to understand. The experiments show that the quality of solution seems to be comparable to existing algorithms (MSI) on the used data sets, while being significantly faster. Therefore, there might be applications where the proposed algorithms are useful in practice, especially if the data is well-behaved in terms of separation.

Critical weaknesses

The proposed merging rules are very simple and not really that surprising. The running time improvements come mostly from the fact that finding a good center for the new cluster is not considered when trying to identify the best merge:

  • r-msi only computes the future (optimal) cluster center after selecting the clusters that are merged
  • and f-msi just keeps using the center of the larger cluster, without any recomputation. This can lead to bad cluster centers (and therefore high cost), especially for a low number of clusters kk when a lot of merges have happened already.

Except for the well-separated case there are no theoretical results that evaluate the quality of the clusters against optimal clusterings.

In the experiments the authors compare their algorithms against average and complete linkage, neither are algorithms that are designed to solve the hierarchical kk-median problem, so it is not surprising that the quality of the clustering produced by these methods is worse than the other algorithms.

While the proposed algorithms seem to be useful in some cases, I feel that the paper falls short of the level of novelty expected at this conference.

Questions for authors

None.

Reviewer_iEGKOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper is dealing with the problem of hierarchical clustering and provides some practical/some theoretical contributions.

Critical strengths

Solving problem of hierarchical clustering and provides some practical/some theoretical contributions.

Critical weaknesses
  1. The data sets used for the experiments are not enough big to understand the utility of the algorithm. Please use some very large data set.
  2. Only one index ARI has shown to compare the performance. More index need to be added
  3. The performance of f-msi and r-msi on clustering differs across datasets. More discussion when they do relatively poorly would be better.
  4. The trade-off between computational and clustering quality should be discussed more thoroughly by the authors.
  5. The effect of the approximation parameter γ on the performance of the sub quadratic variant needs further investigation.
  6. Theoretical quality guarantees assume representativeness. The effectiveness of them for the entire clustering process is commented.
  7. Reporting the results of more experiments would make the results reported more conclusive for further statistical analysis.
Questions for authors
  1. The data sets used for the experiments are not enough big to understand the utility of the algorithm. Please use some very large data set.
  2. Only one index ARI has shown to compare the performance. More index need to be added
  3. The performance of f-msi and r-msi on clustering differs across datasets. More discussion when they do relatively poorly would be better.
  4. The trade-off between computational and clustering quality should be discussed more thoroughly by the authors.
  5. The effect of the approximation parameter γ on the performance of the sub quadratic variant needs further investigation.
  6. Theoretical quality guarantees assume representativeness. The effectiveness of them for the entire clustering process is commented.
  7. Reporting the results of more experiments would make the results reported more conclusive for further statistical analysis.
  8. Additional experiments on large data sets and memory analysis could complement the scalability analysis.
  9. Similarity is 16%, which must be reduced below 6%.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.