- 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
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 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 , and tested both and . By design, since both configurations use the same value of , they produce the same sequence of merges until the run with 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 -medians costs than TeraHAC over most of the evaluated range, with substantial improvements for many values of .
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.
| dataset | n | k | average | complete | f-msi | rmsi | msi | pam_mean | CLNSS_mean |
|---|---|---|---|---|---|---|---|---|---|
| anuram | 7193 | 10 | 0.00 | 0.86 | 0.45 | 0.44 | 0.47 | 0.41 | 0.00 |
| banknote | 1371 | 2 | 0.08 | 0.11 | 0.60 | 0.01 | 0.08 | 0.05 | 0.03 |
| beans | 13611 | 7 | 0.32 | 0.42 | 0.46 | 0.63 | 0.72 | 0.62 | 0.15 |
| breast_cancer | 683 | 2 | 0.78 | 0.51 | 0.80 | 0.77 | 0.77 | 0.84 | -0.02 |
| letter_recognition | 5000 | 26 | 0.07 | 0.07 | 0.14 | 0.13 | 0.16 | 0.12 | 0.04 |
| mice | 552 | 8 | 0.23 | 0.14 | 0.23 | 0.30 | 0.35 | 0.24 | 0.00 |
| iris | 150 | 3 | 0.72 | 0.71 | 0.67 | 0.65 | 0.64 | 0.74 | 0.35 |
| News20 | 5000 | 20 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| Ozone | 3694 | 2 | 0 | -0.04 | 0.03 | 0.03 | 0.01 | -0.01 | 0.01 |
| pendigits | 5000 | 10 | 0.38 | 0.41 | 0.64 | 0.59 | 0.64 | 0.58 | 0.01 |
| parkinsons_small | 195 | 2 | -0.03 | -0.03 | 0.17 | 0.20 | 0.11 | 0.17 | -0.03 |
| rice | 3809 | 2 | 0.00 | 0.18 | 0.63 | 0.56 | 0.57 | 0.69 | 0.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 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?
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 k 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)
Table B: Medoid post-processing time (s)
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.