From Logits to Hierarchies: Hierarchical Clustering made Simple

Authors: Emanuele Palumbo, Moritz Vandenhirtz, Alain Ryser, Imant Daunhawer, Julia E Vogt
Primary area: interpretability and explainable AI
Keywords: Hierarchical Clustering, Clustering, Interpretability and Explainability, Unsupervised Learning

Abstract:
The structure of many real-world datasets is intrinsically hierarchical, making the modeling of such hierarchies a critical objective in both unsupervised and supervised machine learning. Recently, novel approaches for hierarchical clustering with deep architectures have been proposed. In this work, we take a critical perspective on this line of research and demonstrate that many approaches exhibit major limitations when applied to realistic datasets, partly due to their high computational complexity. In particular, we show that a lightweight procedure implemented on top of pre-trained non-hierarchical clustering models outperforms models designed specifically for hierarchical clustering. Our proposed approach is computationally efficient and applicable to any pre-trained clustering model that outputs logits, without requiring any fine-tuning. To highlight the generality of our findings, we illustrate how our method can also be applied in a supervised setup, recovering meaningful hierarchies from a pre-trained ImageNet classifier.

Decision: reject
Reviewer scores: 3, 5, 3, 3, 5

Reviews and discussion:
<thread>
creation date:
1730532398186

thread_type:
official_review

<thread_object>
creator: reviewer_abpg

<content>
summary:
This paper proposes a simple method for hierarchical clustering based on pre-trained non-hierarchical models. Specifically, the method performs on top of (non-hierarchical) pre-trained models, which uses the logits output by the pre-trained models to iteratively compute clusters in a fine-to-coarse manner. The authors verify the effectiveness of the method on four datasets, including CIFAR-10, CIFAR-100, Food-101 and ImageNet1K.

strengths:
The proposed method is simple.
The proposed method looks effective from the experimental results.

weaknesses:
+ The paper presents some challenges in clarity, particularly in the methods section, which may hinder reviewers from fully understanding how the proposed method operates. For example,
  - The terms "clusters" and "groups" seem to be used somewhat interchangeably, which can lead to confusion regarding their meanings. It would be helpful for the authors to clarify the distinctions between these terms in the context of the paper.
  - it should number the equations and reference specific formulas in the algorithm table to illustrate the execution process of the proposed method more effectively.

+ The authors assert that the proposed method does not require fine-tuning of the pre-trained model. However, it would be helpful to clarify how the logits are generated for different datasets. For example, in a network trained on ImageNet1K, the output is 1000-dimensional. If we are now clustering on CIFAR-10, does this imply that its logits are also 1000-dimensional? In other words, does this mean that the number of clusters at the finest-level hierarchy is 1,000?

+ In the context of hierarchical clustering, determining the number of hierarchies is crucial. I would appreciate further explanation on how this is accomplished within the proposed method.

+ Regarding line 190, where $s(G)$ represents the sum of the probabilities of samples belonging to $G$, it seems that if $G$ has more samples, its $s(G)$ value would naturally be larger. This raises the question of whether the relatedness between clusters is sensitive to the number of samples, which may not align with our intuitive understanding.

questions:
Please refer to the weakness section.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730742649095

thread_type:
official_review

<thread_object>
creator: reviewer_k4qd

<content>
summary:
The authors propose a new hierarchical clustering algorithm that leverages a pre-trained flat clustering models.
The key observation is that the logits of those model encode class similarity.

strengths:
- The paper is well-written and easy to read.
- The authors compare their method with three related methods. 
- The authors provide the pseudo code of their algorithm.

weaknesses:
The contribution is rather limited and incremental. It is well known that the logits encode class similarity, and have been frequently used to reconstruct classification hierarchy. Examples for previous work with similar observation: 
- https://arxiv.org/abs/2007.06068 
- https://dl.acm.org/doi/abs/10.1145/3491102.3501823

The evaluation is based on two pre-trained image clustering models, TURTLE and TEMI.
This limits the generalizability of the results, as these are not the same backbones used for the other baselines.

Minor presentation remarks:
- Provide full names of the acronyms NMI and ARI
- datapoints => data points

questions:
Did you consider using the logits of standard image classification models (e.g. a ResNet trained to classify ImageNet)?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730748401918

thread_type:
official_review

<thread_object>
creator: reviewer_laeg

<content>
summary:
The authors provide a simple and fast hierarchical clustering method, which works well in the case of many-class problems. It works on the pretrained representation in the logits space. The method is a version of aglomerative clustering which can be based on a chosen standard clustering backbone. The paper is well written. The idea is simple and can be easily applied even to large datasets.

strengths:
The paper is clearly written, the experiments are properly conducted and shows that the method outperforms other hierarchical approaches. The idea is nice as it uses as a backbone a non-hierarchial clustering method.

weaknesses:
The novelty of the approach is rather limited, the method is in fact a shallow clustering approach applied in the representation space. Consequently, since in training the representation the knowledge of classes was used, it is hard to say how the method would deal in the case when the model did not know the proper classes beforehand. In particular a test of themodel on a few common unsupervised representations on ImageNet is necessary (for example given by SimClr or MaskedAutoEncoders).

questions:
It is necessary to validate the approach on representation space constructed by unsupervised models.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730753476225

thread_type:
official_review

<thread_object>
creator: reviewer_aelc

<content>
summary:
This work proposes a new algorithm for generating hierarchies based on logits of pre-trained models. The new method outperforms other deep clustering techniques both in terms of performance and runtime.

strengths:
The methods elegantly bypass the standard O(N^2) complexity required for standard agglomerative clustering

The model outperforms the other baselines both in terms of runtime and clustering performance.

The paper is well written and easy to follow.

weaknesses:
I'm concerned that the suggested models received a better starting point. If I understand correctly, the pre-trained models know better how to cluster to the starting 10/100/101 clusters. It would benefit this work if there would be an ablation study that demonstrated the good results caused by the suggested algorithm and not by the pre-trained models.

The suggested algorithm is generic, how does it perform on non-vision-based clustering tasks?
How does it perform compared to other (more) deep hierarchical models?
I hope to see a broader comparison, with more than two models for deep custring and on various clustering tasks aside from vision.

The runtime comparison is not 100% fair, in my opinion, since L2H utilizes pre-trained models. 
The pre-trained models already know how to cluster the leafs, while other models need to learn it.

questions:
Do other methods assume a starting division to K clusters?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730898814360

thread_type:
official_review

<thread_object>
creator: reviewer_z6t7

<content>
summary:
The paper presents a method to map from the logit space output from a pretrained clustering network to convert its output into a hierarchical structure. They demonstrate that by building on existing foundation models and non-hierarchical clustering methods, this simple method can outperform bespoke deep hierarchical clustering methods.

strengths:
It is valuable to have strong baselines for complex methods, even when those methods are simple.

The paper is generally well written.

weaknesses:
1. Experiments are too restricted. In the introduction, the authors state that much real-world data is hierarchical, such as taxonomic data. However, they barely run experiments on datasets that possess hierarchical labels. CIFAR-10 does not have hierarchical labels, and so it is unclear how the authors evaluated it for dendritic purity, etc. As far as I am aware, Food101 doesn't either. CIFAR-100 only has one intermediate level in its hierarchy. They refer to the datasets used as being challenging, but I don't think it is appropriate to describe CIFAR-10 as such when we have models achieving >99% accuracy on it. They refer to CIFAR-100 and Food101 as having a large number of classes, but given that models are routinely trained on IN-1k (1,000 classes), IN-21k (21,000 classes), iNaturalist (10,000 classes), and 100 classes is quite small in comparison to these datasets. For work that is benchmarking a relatively simple method, I think it is important that the authors benchmark on more complex and more real-world datasets such as iNaturalist or BIOSCAN-5M from the taxonomic labelling perspective, or even non-image modalities for [more comprehensive analysis]. For a method that trains in 5 minutes on IN-1k, I do not think the authors can justify not exploring larger datasets and demonstrating the methodology works well at scale, both in terms of its performance and execution time. Even worse though, quantitative IN-1k results are not shown (i.e. in Table 1).

2. Baselines are inadequate. What is being proposed in the paper is a method for mapping from logits to a hierarchy, harnessing a couple of methods (TEMI and TURTLE) which can map from the embeddings of pretrained encoder (CLIP and DINOv2) to logits for clusters.
(2a.) The authors introduce the flexibility in their algorithm to consider multiple aggregation operations, but only consider summation ($Λ=\Sigma$). This leaves the question of what is the best aggregation operation unclear.
(2b.) Moreover, the paper leaves open the question of whether this is a *good* methodology of mapping from the TEMI or TURTLE outputs to a hierarchy. They present one method for this mapping, but there are no comparators given for it. For example, what if you used agglomerative clustering to cluster the TEMI or TURTLE logits? Does the L2H method beat this obvious baseline?
(2c.) The L2H-TEMI/TURTLE methods presented have the benefit of building on pretrained foundation models, whereas the competing methods are trained from scratch. Hence it would perhaps be more appropriate to compare against alternative methods for producing clusters from the embeddings of pretrained models, for instance [Lowe et. al. (2024)](https://arxiv.org/abs/2406.02465) investigate methodologies for doing this. [That paper concludes that the best way to cluster embeddings from a pretrained model is UMAP with >5 dims for dimensionality reduction, followed by Agglomerative clustering. So although they don't analyze hierarchical embeddings, the methodology they recommend is actually hierarchical and should serve as a useful baseline for this paper.]

3. Algorithm 1 (which is in a sense the main output of the work) is not adequately well written.
    - The same variable, $s$, is used for both the step number and the score.
    - Some variables are defined in the text of the paper, and used in the algorithm without definitions in the algorithm itself. The algorithm should stand alone without needing to read the rest of the paper to understand it. $f_θ$ is defined and never used, whilst $g_θ$, $g^m_θ$, $K$, $Λ$ are used and never defined.
    - argmin yields a single index, not a set, so it is unclear why the authors use an $\in$ symbol in $G^*\in \text{argmin}_{G\in \mathrm{G}} s(G)$, etc. Perhaps this is to cover the edge case of ties..? But this unnecessarily adds confusion to the notation.
    - $K$ is not updated in the outer loop, so the inner loop at L173 refers to cluster indices that no longer correspond to unmerged clusters.

**Typos and minor points**
- L311 Agglomerative clustering is abbreviated as Agg, but as far as I can see, this abbreviation is never used.
- The methodology for several things is only given in the appendix (e.g. agglomerative clustering), but nowhere in the main text does it let the reader know this or where in the appendix one might find these details (which a reader otherwise may well assume are omitted from the text entirely).
- There are a couple of places where a word is repeated (e.g. L271 "Appendix Appendix")
- L730 The text says it is giving the aggregation function, $Λ$, but the equation is the score function
- L734 "possiblle"
- L341 British English "modelled" contrasts with the American English used in the rest of the text
- Some references are cased incorrectly, e.g. key reference "Deepect" -> DeepECT
- Some references don't include publication details, e.g. Bengio (2014)
- Some references cite arXiv versions of papers where peer-reviewed versions are available (which should generally be preferred for citations) e.g. Karthik (2021b)
- Most references don't have links to the paper being cited, which should ideally be present for the convenience of the reader in the modern, digital era. DOIs can be made clickable simply by importing the doi package in main.tex (and don't need a URL field also present in the bibtex)
- One reference has mojibake: Nguyen (2024) "Identification of distinct subgroups of sj&#xf6;gren’s disease"

**References**
- iNaturalist-21 [arXiv:2103.16483](https://arxiv.org/abs/2103.16483)
- BIOSCAN-5M: [arXiv:2406.12723](https://arxiv.org/abs/2406.12723)
- Lowe et. al. (2024): [arXiv:2406.02465](https://arxiv.org/abs/2406.02465)

[N.B I realized a sentence was half-formed after the reviews were released, and added it later in an update to the review.]

questions:
Q1. Why is IN-1k not included in Table 1?

Q2. What is the input to the agglomerative clustering baseline? Is it the raw pixel values of the images?

Q3. Is the performance of L2H-TEMI on flat clustering metrics identical to the performance of TEMI? Similarly for (L2H-)TURTLE.

Q4. Did you really train the auto-encoder for DeepECT from scratch on CIFAR-10/100 in 25 minutes on a single CPU core...? This seems rather unlikely, but it does appear to be what the paper claims.

Q5. In Fig 2, why is there a space between woman and otter but not between palm tree and sunflower? The two pairs are equally far from each other.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732267944920

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Reply to all Reviewers

comment:
Dear Reviewers,

Thank you all for the constructive and helpful feedback.

We appreciate the positive feedback regarding the effectiveness of our method (Reviewer abpg) and soundness of our experiments (Reviewer LaeG), as well as on the writing of our paper (Reviewers z6t7, AeLC, LaeG, k4QD) and the simplicity/elegance of our idea compared to alternative approaches (Reviewers z6t7, AeLC, LaeG, abpg). However, we also acknowledge the concerns expressed by the Reviewers. In summary in the rebuttal we address the following main concerns: 

- **Reviewer z6t7** We further elaborate on our selection of datasets and baselines for the hierarchical clustering experiments. We justify our choices, highlighting the relevance of our showcased results within these experimental settings, that effectively validate the claims presented in the paper. To enhance clarity, we have revised Algorithm 1 in the updated manuscript, integrating the Reviewer's valuable suggestions. 
- **Reviewer AeLC** We clarify that the efficient adaptation of a pre-trained flat clustering model to perform hierarchical clustering, as an alternative to designing ad-hoc complex approaches, is a key idea introduced in this work. We also further elaborate on our choices of baselines, and clarify how our run time comparison constitutes a fair comparison. 
- **Reviewer LaeG** We clarify the key point that in Section 4.1 we consider a *fully unsupervised setup*, where our method achiveves remarkable performance. To complement the results in this section, we also include in the updated manuscript the hierarchical clustering performance obtained by our approach on the ImageNet1K dataset (Appendix C). 
- **Reviewer k4QD** We remark that a key contribution of this work is introducing a different perspective on hierarchical clustering. Compared to existing works, we propose to efficiently adapt a pretrained flat model to infer a hierarchy of clusters, rather than focusing on designing costly and complex ad-hoc hierarchical approaches. We highlight that, while the idea of exploiting information in the logits to construct a hierarchy of classes was explored in classification, we are to the best of our knowledge the first ones to use this intuition for hierarchical clustering. Notably, we use this intuition to design a method for hierarchical clustering that overcomes the shortcomings in performance and scalability of current approaches.
- **Reviewer abpg** We provide useful clarifications, and elaboarate on the details of the aggregation function used in our experiments, for which we also include an ablation in the updated manuscript (Appendix C).  

References for the whole rebuttal: 
[1] Manduchi et al. Tree variational autoencoders. In Advances in Neural Information Processing Systems, 2023. [2] Mautz et al. DeepECT: The deep embedded cluster tree. Data Science and Engineering, 2020. [3] Chami et al. From trees to continuous embeddings and back: Hyperbolic hierarchical clustering. In Advances in Neural Information Processing Systems, 2020. [4] Wang et al. Internimage: Exploring large-scale vision foundation models with deformable convolutions. arXiv preprint arXiv:2211.05778, 2022.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This works critically examines deep learning approaches to hierarchical clustering, and proposes to instead infer a hierarchical clustering from pre-trained representations and flat clusterings. The main strengths are the simplicity and generality of the method, which can be applied to any input clustering that provides logits, the contrast of the method with existing divisive/top-down deep clustering methods, and improved results along with results on both unsupervised and supervised clustering (z6t7, AeLC, LaeG). The main weaknesses are the insufficient experiments (z6t7) and baselines (z6t7, AeLC, k4QD) and a minor weakness of showing results only for vision (AeLC) while clustering could apply to data of any modality. The submission is missing controlled comparisons between the proposed method and existing methods on the same and standard representations (z6t7, LaeG) and missing a baseline for the extension from flat to hierarchical clustering, such as agglomerative clustering (z6t7). The authors discuss these points, especially the choice of datasets and comparisons, but do not convince the reviewers (see the additional comments on the discussion).

Explanation of Decision:

Five reviewers with expertise on deep learning, clustering, meta-learning, and hierarchical modeling agree on rejection (z6t7: 3, LaeG: 3, k4QD: 3, AeLC: 5, abpg: 5). The meta-reviewer does not find cause to overrule the expert reviewers. On the balance, the weaknesses—especially the limited comparisons and datasets—outweigh the strengths of this work at this time. It is important to provide baselines and comparisons of overall performance, as done here, as well as controlled experiments that match representations/architectures/aggregation choices. Without controlled experiments, it is difficult to understand the significance of the proposed method and its results, so for this reason and in agreement with the overall evaluation by the reviewers the meta-reviewer sides with rejection. The authors are nevertheless encouraged to incorporate the precise feedback, for instance the suggestions from z6t7 on informative comparisons, and resubmit.