From Logits to Hierarchies: Hierarchical Clustering made Simple

We thank the Reviewer for the positive feedback, in particular for praising the idea, effectiveness, and usefulness of our method. We appreciate the useful feedback/suggestions, and address the concerns below.

If I understand correctly, the leaf accuracy is unaffected by the application [...]

The Reviewer is correct that our method by construction retains the leaf-level flat clustering performance of the pre-trained flat model. We make it explicit already in the text (e.g. lines 234-236, right column), but we agree with the Reviewer that in the interest of clarity it can be made more explicit in table 1. In the updated manuscript we add to the caption of Table 1 the final sentence Notably,the application of L2H does not affect flat clustering performance, retaining the clustering performance of the pre-trained model (TURTLE, TEMI) at the leaf level., using italic to highlight it.

We also perform an additional experiment on the INaturalist21 (https://github.com/visipedia/inat_comp/tree/master/2021) dataset, which we use a setting to test whether our method can bring an advantage over flat clustering methods, used as backbone, when the nature of a dataset is inherently hierarhical. The INaturalist dataset contains ~2.7million images of species labelled at different taxonomy levels (1103 families, 273 orders, 51 classes, 13 phylums, 3 kingdoms). We perform the following experiment. First we train five instances of TURTLE to model clusters at five different taxonomy levels, i.e. varying K across instances in the range $K \in \\{ 1103, 273, 51, 13, 3 \\}$. Then we apply our L2H algorithm on top TURTLE trained at the most fine-grained taxonomy level (i.e. family, K=1103), and use the produced hierarchy to make clustering predictions at the more coarse levels. We repeat the experiment across multiple seeds, and compare the performance of the two strategies. The results show that inferring clustering predictions at more coarse levels via the produced hierarchy with L2H leads to better performance compared to re-training TURTLE at the each corresponding level. Results at https://files.catbox.moe/0nt1uq.pdf

The runtime figures are stated to include the time [...]

We have refined the manuscript accordingly to clarify this point. The Reviewer is correct, and to confirm that our approach is both more computationally efficient and more performant than deep specialized hierarchical approaches we have trained the best performing baseline (TreeVAE) on the CIFAR-100 dataset CLIP embeddings. The results prove that the performance of TreeVAE improves compared to training in data space, but it is still markedly outperformed by our approach. Note that in this setting TreeVAE takes more than 2 hours on a GPU to train, while e.g. L2H turtle takes under 2 minutes. Since all models in this comparison have access to pre-trained embeddings from foundation models, these results confirm our method is markedly more computationally efficient than alternative deep specialized hierarchical approaches. Results at https://files.catbox.moe/gz0tu8.pdf

The method is straightforward and effective.[..]

Note that we motivate our choice of merging the cluster/group with the lowest score in the Rebuttal for Reviewer YXaT. We appreciate the interest/suggestion from the Reviewer and will include an ablation on the updated version of the manuscript to test the Reviewer's idea of computing rp(c) for all pairs and merging the highest. It will make an interesting ablation in our work.

Other Comments Or Suggestions

We appreciate the Reviewer signaling these typos, which we will fix in the manuscript.

---

We are happy to answer any additional questions and would appreciate it if the Reviewer would consider raising their score to full acceptance.

We thank the Reviewer for the valuable feedback and suggestions. We appreciate the praise for the efficiency and efficacy of our method, and the highlighting of its value in addressing well-known challenges in hierarchical clustering. We address concerns/questions below.

However, increasing the number of datasets and comparison methods [..]

See comparison with [1] below + other Rebuttals (e.g. L2H+TCL and TreeVAE+CLIP comparisons, INaturalist results).

Given the related work on [...]

We assume the Reviewer refers to this ICML 2024 workshop paper[1], on zero-shot flat clustering. The proposed strategy (UMAP dim.red. on embeddings + Ward's agglomerative clustering) incurs in high computational cost for large datasets, and more importantly does not allow for inference on unseen data. Hence, to test the method from Lowe et al. for comparison we necessarily both train and evaluate it on the test set, thereby giving it an advantage in seeing test data for training. Despite this, this method still underperforms compared to our proposed approach, which further validates and contextualises the effectiveness of our method. Results on CIFAR-100 at https://files.catbox.moe/4nhqck.pdf

Theoretically, the design basis of the masked Softmax [..]

We introduce the masked softmax as a principled variation of the softmax function that allows masking in the indexes. Note that our function definition ensures that a valid probability distribution over the unmasked elements is produced. We do not consider a downstream task in our hierarchical clustering experiments. We would thus appreciate it if the Reviewer could provide clarifications regarding the comment "the relationship between the hierarchical clustering objective function and the downstream tasks is not clearly established".

In the evaluation metrics, only traditional clustering metrics were used[..]

Note that we use Dendrogram Purity (DP)[2,3] and Least Hierarchical Distance (LHD) - both metrics tailored for hierarchical clustering.

No sensitivity analysis of the parameters was conducted, such as the depth of the tree.

We provide a sensitivity analysis of L2H-TURTLE on the CIFAR-100 dataset, with respect to the depth of the tree. The depth of the tree is controlled by the $K$ hyperparameter corresponding to the number of clusters modelled by the flat model and therefore to the number of leafs in the tree. The analysis demonstrates that across all hierarchical and flat metrics the best performance is achieved when K equals the true number of classes (100). When $K$ deviates from the true number of clusteris, performance degrades gracefully and a meaningful hierarchy is still recovered. This robustness is particularly important in practical setting where the true number of clusters is not known a-priori; in such cases the log-normalized TURTLE model loss can provide useful signal to select the hyperparameter $K$. Results at https://files.catbox.moe/iisaqn.pdf.

The summary of contributions and the future work section need further refinement.

We appreciate the suggestion from the Reviewer, and have refined the manuscript accordingly, summarizing and highlighting more clearly the contributions of our work. As well, we have deepened the section on future work, also in light of some additional results shown in this rebuttal.

The majority of the references are from [...]

We share the Reviewer’s view on the importance of citing recent literature, and have made our best effort to do so throughout the paper. However, as noted in the recent relevant work[2], the number of deep learning-based approaches proposed in the last few years to address hierarchical clustering remains surprisingly limited. This underlines the relevance and timing of our work, where we aim to revive the interest in this underexplored area, building on recent advancements (e.g. in flat clustering models). To that end, we compare with the most recent and relevant baselines[2] and build upon SOTA flat clustering models. Finally note that we have followed the recommendation from the Reviewer contextualizing our approach in comparison with [1] above.

Replies to "Questions for the Authors"

1.We introduce CIFAR-10, CIFAR-100, Food-101 that we used in section 4.1 and ImageNet1k that we used in Section 4.2 and Table 3.

2.In line 753 we highlight that comparisons with baselines (e.g., DeepECT, TreeVAE) are not feasible on ImageNet1k, as these methods lack the scalability to handle datasets of this magnitude/complexity.

3.We reported Table 5 in the Appendix as it consists of an ablation validating the stability wrt the design choice of the aggregation function. We appreciate the Reviewer's suggestion and have refined the Appendix by removing redundant results.

[1] Lowe et al.(2024) [2] Manduchi et al.(2023) [3] Kobren et al al.(2017)

We are happy to answer any additional questions, and would appreciate it if the Reviewer would consider increasing their score to an acceptance.

We thank the Reviewer for praising performance and efficiency of our method, our metrics/datasets, as well as the clarity of our paper. We appreciate useful the feedback and suggestions, and address the concerns below.

line 131[..]

The number of leafs in the hierarchy obtained with our approach is the number of clusters $K$ modelled by the pre-trained flat model, which is a hyperparameter. Note that we show our approach is robust to changes in $K$, and should an a-priori value for $K$ not be available, the loss of the flat model (e.g. TURTLE) can be useful signal to set it (See rebuttal to Reviewer CKwm).

line 199 [..]

The score we define captures the aggregated probability mass that the model assigns to each cluster/group. When a cluster/group receives the lowest score, depending on the exact aggregation, it indicates one of two scenarios (or both):

• It contains fewer samples, suggesting it is more specialized than others.
• The model is less confident when assigning samples to it, often because it's highly similar to another cluster/group.

In either case, the cluster/group is a natural candidate for early merging in a bottom-up hierarchy from fine-grained to coarse. In the first case, it is more specialized than others. The second case is a little more subtle. Consider the case of overclustering, where the number of leaf nodes K is larger than the true number of clusters. In this case, redundant clusters modelling the same true class present low-confidence assignments, as the model can't clearly distinguish between them when assigning samples. This low confidence reduces their score, causing them to be merged early, effectively correcting the overclustering. Thus, our score guides the hierarchy-building process in a principled way, encouraging early merging of either highly specific or redundant clusters, ultimately leading to an accurate hierarchy, as validated empirically.

line 144: [..]

We agree that this assumption underlies our method. While empirically supported, we acknowledge that this assumption may not always hold, for instance in case the flat model is poorly calibrated. We have updated the manuscript to explicitly discuss this assumption and its potential limitations.

Is it possible to [..]

As we state in lines 234 - 236 (right column), by construction, our method retains the clustering performance of the pre-trained model at the leaf level, hence non-hierarchical clustering metrics for TEMI/TURTLE match the L2H-TEMI/L2H-TURTLE results in Table 1. However, our results on the INaturalist21 dataset (see rebuttal to Rev. CaXW) prove that our approach can be used to model multiple granularity levels in datasets with a hierarchical structure. Notably, our approach surpasses the performance obtained by training multiple instances of a flat model (e.g. TURTLE), one at each given granularity. In such a setting, our hierarchical approach surpasses the flat model (e.g. TURTLE) on flat metrics at all but the finest granularity (where the performance matches).

Out of curiosity [..]

It is not necessarily true in principle that all flat clustering methods are faster than hierarchical methods. However, there's been a lot recent research on highly performant and efficient flat clustering (e.g TURTLE), while a comparable research effort has not been witnessed for hierarchical models.

Going back to the choice [..]

See rebuttal to Rev. CaXW.

Additionally [..]

Note that in section 4.2 we use InternImage as a backbone mode - not based on CLIP embeddings.

But overall [...]

We appreciate the suggestion from the Reviewer, and implement our method on top of the TCL flat clustering model [1] on the datasets used in Table 1. TCL (i) does not rely on pre-trained embeddings, and (ii) achieves weaker flat results than TEMI/TURTLE. Results at https://files.catbox.moe/cfufvm.pdf. Still, with our approach (L2H-TCL) we outperform deep hierarchical models (DeepECT,TreeVAE) across all flat/hierarhical metrics, which strenghtens our contribution.
[1] Li et al. Twin Contrastive Learning for Online Clustering, IJCAI, 2021.

Can you explain Figure 1[..]

In the second step in Fig.1 the pink cluster, selected for merging, is merged with the group containing yellow and blue clusters, as this group has the most reassigned predicted probability mass. The bar contains blue/yellow parts to represent that it aggregates the probability mass reassigned to blue/yellow clusters, that were grouped together at the previous step.

Minor: for the benefits of modeling [..]

We agree with the Reviewer that the benefits of modelling a hierarchy are not restricted to the unsupervised setup, and show results to support this point in section 4.2. We appreciate the useful references and have integrated them in the updated manuscript.

We are happy to answer any additional questions, and would appreciate it if the Reviewer would consider increasing their score to an acceptance.