Contrastive Hierarchical Clustering
Authors: Michał Znaleźniak
Przemysław Rola
Patryk Kaszuba
Jacek Tabor
Marek Śmieja
Venue: Submitted to ICLR 2023 (2023)
Keywords: clustering
hierarchical clustering
contrastive learning
soft decision trees

Abstract: Deep clustering has been dominated by flat clustering models, which split a dataset into a predefined number of groups. Although recent methods achieve extremely high similarity with the ground truth on popular benchmarks, the information contained in the flat partition is limited. In this paper, we introduce CoHiClust, a Contrastive Hierarchical Clustering model based on deep neural networks, which can be applied to large-scale image data. By employing a self-supervised learning approach, CoHiClust distills the base network into a binary tree without access to any labeled data. The hierarchical clustering structure can be used to analyze the relationship between clusters as well as to measure the similarity between data points. Experiments performed on typical image benchmarks demonstrate that CoHiClust generates a reasonable structure of clusters, which is consistent with our intuition and image semantics. Moreover, by applying the proposed pruning strategy, we can restrict the hierarchy to the requested number of clusters (leaf nodes) and obtain the clustering accuracy comparable to the state-of-the-art flat clustering baselines.


Under review as a conference paper at ICLR 2023
CONTRASTIVE HIERARCHICAL CLUSTERING
Anonymous authors
Paper under double-blind review
ABSTRACT
Deep clustering has been dominated by flat clustering models, which split dataset into a predefined number of groups. Although recent methods achieve extremely high similarity with the ground truth popular benchmarks, the information con- tained in the flat partition is limited. In this paper, we introduce CoHiClust, a Con- trastive Hierarchical Clustering model based on deep neural networks, which can be applied to large-scale image data. By employing a self-supervised learning ap- proach, CoHiClust distills the base network into a binary tree without access any labeled data. The hierarchical clustering structure can be used to analyze the rela- tionship between clusters as well as measure the similarity between data points. Experiments performed on typical image benchmarks demonstrate that CoHiClust generates a reasonable structure of clusters, which is consistent with our intuition and image semantics. Moreover, by applying the proposed pruning strategy, we can restrict the hicrarchy to the requested number of clusters (leaf nodes) and ob- tain the clustering accuracy outperforming existing hierarchical baselines.
INTRODUCTION
Clustering, fundamental branch of unsupervised learning, is often of the first steps in data analysis, which finds applications in anomaly detection Barai & Dey (2017), personalized recom- mendations Zhang al. (2014) or bioinformatics Lakhani al. (2015). Since it does not use any information about class labels, representation learning becomes an integral part of deep clustering methods. Initial approaches use representations taken from pre-trained models Guérin et al. (2017); Naumov et al. (2021) or employ auto-encoders in joint training of the representation and the clus- tering model Guo et al. (2017a); Mautz et al. (2019). More recent works designed to image data frequently follow the self-supervised learning principle, where representation is trained on pairs of similar images automatically generated by data augmentations Li et al. (202Ib); Dang et al. (202I). Since augmentations used for image data class invariant, the latter techniques often obtain very high similarity with the ground truth classes. However, we should be careful when comparing clus- tering techniques only by inspecting their accuracy with ground truth classes because the primary goal of clustering is to deliver information about data and not to perform classification.
Most works in the area of deep clustering focus on producing flat partitions with a predefined number of groups. Although hierarchical clustering gained notable attention in classical machine learning and has been frequently applied in real-life problems Zou et al. (2020): Smmieaa et al. (2014), its role has been drastically marginalized in the era of deep learning. In the case of hierarchical clustering, the exact number of clusters does not have to be specified because we can inspect the partition at various tree levels. Moreover, we can analyze the clusters' relationships, e.g. by finding super- clusters or measuring the distance between groups in the hierarchy. The above advantages make hierarchical clustering an excellent tool for analyzing complex data. However, in order take full advantage of hierarchical clustering, it is necessary to create an appropriate image representation, which is possible thanks to the use of deep neural networks. To the best of our knowledge, DeepECT Mautz et al.) (2019] 2020) is the only hicrarchical clustering model trained jointly with the neural network. Nevertheless, this method has not been examined to large image datasets, which appear in practical applications.
To fill this gap, we introduce CoHiClust (Contrastive Hierarchical Clustering), which creates a hierarchy of clusters and can be applied to large image data. CoHiClust uses neural network to generate a high-level representation of data, which is next distilled into the tree hierarchy by applying the projection head, see Figure g The whole framework is trained jointly in an end-

---

Under review as a conference paper at ICLR 2023
to-end manner without labels using novel contrastive loss and automatically generated data augmentations following the self-supe learning principle.
The constructed hierarchy uses the structure of binary tree, where the sequence of decisions made by internal nodes determines the final assignment to clusters (leaf nodes). In consequence, similar examples processed longer by the same path than dissimilar ones. By inspecting the number of edges needed to connect two clusters (leaves), we obtain a natural similarity measure between data points. Although CoHiClust assumes pre-defined tree structure with fixed height, introduce a pruning mechanism, which removes the least informative leaf nodes until the requested number of leaves is obtained. In contrast typical pruning strategies or tree cuts, where neighboring leaves are only merged to ancestor node, we allow for reassigning data points between clusters by finetuning the whole model, which further improves topology of the tree.
ROOT
codd
dReS 1055
2006
Figure 1: A tree hierarchy generated by CoHiClust for F-MNIST (images in the nodes denote mean images in each sub-tree). The right sub-tree contains clothes while the other items (shoes and bags) are placed in the left branch. Looking at the lowest hierarchy level, we have clothes with long sleeves grouped in the neighboring leaves. The same holds for clothes with designs. Observe that CoHiClust assigned white-colored t-shirts and dresses to the same cluster, while trousers are in the separate one. Small shoes such sneakers sandals are considered similar (neighboring leaves) and distinct from ankle shoes. Concluding, CoHiClust able to retrieve meaningful information about image semantics, which is complementary to the ground truth classification.
The proposed model has been examined on various image datasets and compared with both hierar- chical and flat clustering baselines. By analyzing the constructed hierarchies, we show that CoHi- Clust generates a structure of clusters that is consistent with our intuition and image semantics, see Figures [ for the illustration and discussion. Our analysis is supported by a quantitative study, which shows that CoHiClust gives higher similarity with ground truth partition than available hierarchical baselines, see Tables [ 2 and Morcover, it is among the three rest-performing methods when compared to the flat clustering models, see Table
Our main contributions are summarized as follows:
We introduce hierarchical clustering model CoHiClust, which converts the base neural network into a binary tree. The model trained effectively with no supervision using our novel hierarchical contrastive loss applied to self- self-generated data augmentations.
We implement a pruning strategy, which not only leads to creating a fixed number leaves but also improves the constructed hierarchy.
2

---

Under review as a conference paper at ICLR 2023
Our experimental analysis shows that CoHiClust builds hierarchies based the well- defined and intuitive patterns retrieved from data.
Since CoHiClust is the first deep hierarchical clustering model applied to large-scale image datasets, we also deliver a new benchmark, which can be used to compare hierarchical clustering methods.
2
RELATED WORK
In this section, we briefly introduce some recent developments in three related topics, i.e., contrastive learning, deep clustering, and hierarchical methods.
Contrastive Learning The basic idea of contrastive learning to learn such feature space, in which similar pairs stay close to each other while dissimilar ones are far recent works, was observed that in selected domains, such as computer vision, positive (similar) pairs can be generated automatically using adversarial perturbations Miyato et al. (2018) or data augmentation He et al. 2020), giving the rise of a new field called self-supervised learning Chen et al. (2020). Fine-tuning a simple classifier on self-supervised representation allows for obtaining the accuracy comparable to fully supervised setting. SimCLR He et al. (2020) applies NT-Xent loss to maximize the agreement between differently augmented views of the same sample. Barlow Twins Zbontar et al. (202T) learns to make the cross cross-correlation matrix between two distorted versions of the same samples close the identity. BYOL et al. (2020) claims to achieve new state-of-the- art results without using negative samples. Other works use memory banks to reduce the cost of computing the embeddings of negative samples in every batch Wu et al. (2018): He al. 2020).
et al. (2005). In
Deep clustering A primary focus in deep embedded clustering has merely been on flat clustering objectives with the actual number of clusters known priori. DEC Xie et al.] (2016) is one of the first works, which combines the auto-encoder loss with clustering objective to jointly learn the representation and perform clustering. This idea was further explored with some improvements in IDEC Guo et al.) (2017a). JULE Yang al. (2016) and DCEC Guo et (201hb). IMSAT Hu et al. (017) and IIC Ji et al. (2019) use perturbations to generate pairs of similar examples and apply coormation-thereeee
objectives for training. PICA Huang et al. (2020) maximizes the global partition confidence of the clustering solution to find the most semantically plausible data separation. Following the progress in self-supervised learning, CC Li et al.] (2021b) and DCSC Zhang et al. 2022) perform contrastive learning by generating pairs of positive and negative instances through data augmentations.
Hierarchical methods Hierarchical clustering algorithms are a well-established area within clas- sical data mining Murtagh & Contreras (012)) but they were rarely studied in deep learning. Deep- ECT Mautz et al. (2019) 2020) is the only method, which jointly learns the deep representation using auto-encoder architecture and performs hierarchical clustering in a top-down manner. Un- fortunately, there is not comparative study conducted on large image data. The experimental study of objective-based hicrarchical clustering methods performed on the embedding vectors from pre- trained deep learning models is presented in Naumov et al. (2021). In the case of classification, there a growing interest in deep hierarchical methods, which our opinion should also be reflected in the area of unsupervised learning. SDT Frosst & Hinton (2017) is one of the first models that distills the base neural networks into a soft decision tree. More advanced methods automatically generate deep networks with a tree structure in multi-step or end-to-end manner TTnnn et al. (2019);
Alaniz et al. (202I); Wan et al. (2020).
3 COHICLUST MODEL
The proposed CoHiClust builds hierarchy of clusters based the output of the base neural net- work. There are four key components of CoHiClust:
The base neural network. which generates representation used by the tree.
The tree model, which assigns data points to clusters by sequence of decisions.
The regularized contrastive loss, which allows for training the whole framework.
3

---

Under review as a conference paper at ICLR 2023
The pruning strategy, which restricts the tree the requested number of leaves.
We discuss the above components in detail in the following parts.
Tree hierarchy We use soft binary decision tree to create hierarchical structure, where leaves play the role of clusters (similar to Frosst Hinton (2017). In contrast to hard decision trees, every internal node defines the probability of taking a left/right branch. The final assignment of the input examples to clusters involves partial decisions made by the internal nodes. Aggregating these decisions induces the posterior probability over leaves.
Let us consider complete binary tree with 7' levels, where the root is located at the level 0 and the leaves are represented at the level T,, This gives 2' nodes the level f denoted by tuples (t, i), for i = 0, 1, ...... 2 1. see Figure 2 The path going from the root to the node (t, i) is given by the sequence binary decisions
........ 3/) E {0. 1) made by the internal nodes, where ys (y+ 1) means that we take the left (right) branch being in the node at the level 8. Observe that can retrieve the index other words, the first bits of y are a binary representation of the number
the node the level s from by taking j b, b,(y) = -m=1 y/m 2 In
We consider the path induced by the sequence decisions y = (V....., 310 E {0, 13", which goes from the root to the node it, where i = by (1).. We want to calculate the probability (x) that the input example I E IRD reaches node it. If ps
by (w) (x) the probability of going from the parent
node (s 1, 1z))) to its descendant (s, (2))), then
(v) ( (x(x)) = Pi (1) (x) P22 b2(2)) (z) .t
Observe that (1) (x), (x), ,.. Pt (x)) defines proper probability distribution, i.e. 2'
Zj=0
P/ x 1. In consequence, the probability distribution over clusters (leaves) equals Pr(x),
see Figure
g
Plod p0o- gool
Figure 2: Illustration of CoHiClust. The output neurons of the projection head æ (appended the base network model decisions made by the internal tree nodes. The final assignment of the input example to the cluster (leaf node) is performed by aggregating edge probabilities located on the path from the root to this leaf.
Tree generation To generate our tree model, we need to parameterize the probabilities (x( of taking the left/right branch in every internal node. To this end, we employ neural network g D - R. with an additional projection head IR + R where K = 2 and T is the height of the tree. The number K of the output neurons equals the number internal tree nodes.
The neural network is responsible for extracting high-level information from data. It can be in- stantiated by a typical architecture, such as ResNet, and used to generate embeddings = = g(x) of the input data. We do not use pre-trained networks but train the whole model end-to-end using the proposed hicrarchical contrastive loss. This allows for generating the representation, which is suited to the underlying clustering task.
The projection head æ operates on the embeddings z and parameterizes decisions made by the inter- nal tree nodes. In our case, π is single- network with the output dimension equal to the number of internal nodes. To model binary decisions the internal nodes, we apply the sigmoid function a. In consequence, the projection head is given by क (2) [a(w]' + bi b1), ........ (w z bx)), where

---

Under review as a conference paper at ICLR 2023
Wn IR and bn E R are trainable parameters of æ. By interpreting the output neurons of i the internal nodes of the decision tree, we get the probabilities of left edges in the nodes:
pit (z) = a a b,.) for 2
2 Note that Pi+1 (z) = 1 p (x) always corresponds to the probability of right edge.
Contrastive hierarchical loss To train CoHiClust, we introduce the hierarchical contrastive loss function designed for trees. Our idea relies on maximizing the likelihood that similar data points will follow the same path. The more similar data points, the longer they should be routed through the same nodes. Since we work the unsupervised setting, we use a self-supervised approach and generate similar images by data augmentations.
Let us consider two data points 21, D2 and their posterior probabilities P( (x1)) (x22) at the level t. The probability that 2 and 22 reach the same node at this level is given by the scalar product P. (z1).
P((2)) = Ein Pi (x))) This term is maximal if both probabilities are identical one-hot vectors. In training phase, we do not want to force hard splits the nodes (binary probabilities) because in this way the model quickly finds a local minimum by assigning data points to fixed leaves with high confidence. Instead of sticking to hard assignments let the model explore possible solutions. To this end, we take the square root before applying the scalar product, which corresponds to the Bhattacharyya coefficient Bhattacharyya (1466):
few training epochs, we want to
8c 8r(21, = v Pr((z)) P,(12)
Σ V ((()))
(1)
Observe that (e(2 x22) 1, only Pa(x,) (a(22) (probabilities do have binarize), which leads to the exploration of possible paths. By aggregating the similarity scores over all tree levels, arrive final similarity function s(r1 22) Ei $1(21,
In training phase, take minibatch {-,)) of N examples and generate its augmented view { Every pair (xy, ū2) considered positive, which means that we will maximize their similarity score. In consequence, we encourage the model to assign them to the same leaf node. To avoid degenerate solutions, where all points end up in the same leaf, we treat all other pairs negative and minimize the similarity scores for them. Finally, the proposed hierarchical contrastive loss is given by:
CoHiLoss N(N 1) j=1 b
ΣΣ s(5,,
Σ s(z;, kT). 1=1
By minimizing the above loss. we maximize the likelihood that similar data points follow the same path (second term) and minimize the likelihood that dissimilar ones are grouped together.
Regularization Final cluster assignments are induced by aggregating several binary decisions made by the internal tree nodes. In practice, the base neural network may not train all nodes and, in consequence, use only a few leaves for clustering. While selecting the number of clusters in flat clustering desirable, here we would like create hierarchy, which not restricted given number of leaves. To enable end-to-end training of the base neural network with the arbitrary number of leaves, we consider two regularization strategies.
The first regularization (dubbed R2 explicitly encourages the model to use both left and right sub- trees equally Frosst Hinton (2017). We realize this postulate by minimizing the cross-entropy between the desired distribution 00.5, 0.5) and the actual distribution for choosing the left or right path in a given node.
The second regularization (dubbed R2) does not directly influence the routing in the tree but focuses on improving the output representation of the base network g. For this purpose, we use Ne-Xent loss Chen et al. (2020) the embedding space 2 = 9xx). With the NT-Xent loss, maximize the cosine similarity on the embedding space for all positive pairs and minimize the cosine similarity on the embedding space for all negative pairs.
5

---

Under review as a conference paper at ICLR 2023
Taking together the contrastive loss CoHiLoss with two regularization functions R₁ (for entropy) and R2 (for NT-Xent), we arrive at our final loss:
Loss =CoHiLoss + 31 + 82
where $1. B2 are the hyperparameters defining the importance of regularization terms RS and R2, respectively. To generate full hierarchy (complete tree with the assumed height), we set 81 propor- tional to the depth of the tree 31 = 2- and f82 In appendix, we show that CoHiClust can also detect the number of clusters automatically by putting 31 0 (see appendix for the ablation study).
Pruning The proposed model builds a complete tree with 2 leaves. Although such a structure is useful for analyzing the hierarchy of clusters, some cases we are interested creating with the requested number of groups. For this purpose, we introduce pruning strategy that reduces the least significant leaf nodes.
We start with calculating the probability of leaves Pj [X] ExEx (f(), which describes the expected fraction of data points assigned to given leaf. Assuming that the importance of the cluster related to the average number of assigned examples, we reduce a leaf with the lowest probability. After removing the leaf, we fine-tune the whole model using CoHiClust loss 2). If want to reduce more leaves, we perform leaf pruning and model retraining iteratively until the requested number of leaves is obtained. The resulting tree is binary, but can have arbitrary structure and does not have to be complete. Consequently, pruning is also a way of improving the topology of the tree model.
Alternatively, we could also perform the pruning strategy without applying fine-tuning step. This potentially saves the computational resources, but does not adjust hierarchy the modified number of groups. In appendix, we show that this approach generates partition of lower quality than the model with fine-tuning.
EXPERIMENTS
Table I: Dendrogram purity (DP) of cluster- ing hierarchies (higher is better).
Table 2: Clustering metrics of partitions gen- erated from the tree hierarchies on MNIST and F-MNIST (higher is better).
Method
MNIST
F-NNIST
DeepECT
0.82
0.47
Methad
MNIST
F-MNIST
DeepECT Aug
0.94
0.44
NMI
ACC
NMI
ACC
IDEC + Single
0.39
0.34
DeepECT
0.83
0.85
0.60
0.52
IDEC + Complete
0.40
0.35
AE Bisecting
0.53
0.38
DeepECT + Aug
0.93
0.95
0.59
0.50
AE + Single
0.11
0.10
IDEC
0.86
0.85
0.58
0.53
AE + k-means
0.70
0.77
0.52
0.48
+ Complete
0.25
0.26
CoHiClust
0.97
0.99
0.62
0.65
CoHiClust
0.97
0.52
We evaluate method with several datasets of increasing difficulty. We show that CoHiClust outperforms hierarchical clustering models and is among the three best-performing flat clustering methods in terms of similarity with the ground truth classes. addition, analyze the constructed hierarchies, which in our opinion are equally important in practical use-cases. Our experiments demonstrate that CoHiClust reveals novel patterns and relations between data points beyond those contained in ground truth classes.
Comparison with hierarchical clustering methods First, we compare CoHiClust with hicrarchi- cal baselines. To the best of our knowledge, DeepECT Mautz et al. (2019) is the only hierarchical clustering method based on deep neural networks. Following their experimental setup, we also consider classical hierarchical algorithms evaluated on the latent representation created by the au- toencoder and IDEC Guo et al. (2017a). We report the results on two popular image dataset MNIST and F-MNIST.
We intentionally do not use two remaining datasets: USPS which is analogous to MNIST and Reuters which is not image database.

---

Under review as a conference paper at ICLR 2023
We rum CoHiClust with 16 leaves (4 tree levels) using & as base neural network. The initial model is trained for 50 epochs on MNIST and 100 epochs on F-MNIST using a minibatch size of 256. Next, we perform pruning with an additional 50 and 100 epochs of fine-tuning and F-MNIST, respectively, to end up with 10 clusters, which equals the true number of classes for considered datasets. To evaluate the cluster hierarchies against ground truth flat partition, we dendrogram purity (DP) Kobren et al. (2017); Yang et al. ( which attains its maximum value of if and only if all data points from the same class are assigned to some pure sub-tree.
MNIST
The results summarized in Table D demonstrate that CoHiClust outperforms all baselines on both MNIST and F-MNIST datasets. Interestingly, DeepECT benefits from data augmentation in the case of MNIST, while on F-MNIST it deteriorates its performance. All methods except CoHiClust and DeepECT failed completely to create a hierarchy recovering true classes, which confirms that there is a lack of powerful hierarchical clustering methods based on neural networks.
To further evaluate the performance on MNIST and F-MNIST, we measure the normalized mutual information (NMI) and the clustering accuracy (ACC) between the ground truth partition and the flat clustering generated from the tree hierarchy. We exclude the combinations of hierarchical and embedding methods from the comparison due to their poor performance. Instead, we consider two flat clustering methods: IDEC and k-means evaluated on the latent representation generated by the autoencoder. It can be seen from Table that CoHiClust outperforms baseline methods across all datasets and metrics. The disproportion between the results obtained on MNIST and F-MNIST demonstrates that recovering true classes of clothes is significantly more challenging task than recognizing the hand-written digits.
Analyzing the clustering hierarchies Although comparing constructed clustering with the ground truth partition widely-used evaluation measure in the literature, it is even more impor- tant from a practical point of view to visualize the results and perform their qualitative assessment. Figure I presents the clustering tree constructed for F-MNIST (see appendix for the hierarchy of MNIST). Images in nodes show the means calculated over data points assigned to the respective nodes. For every leaf, we also present sample images classified to this cluster and the percentage of images from dominant classes in the group (with a fraction higher than 15%). Visual inspection shows that neighboring leaves contain images with similar patterns, see description in Figure [ for detailed findings.
The hierarchy also allows us to define the distance d(a, b) between two examples a, using the number of edges that connect them. We use the average of this score to calculate the similarity between ground truth classes A and B given by d(A, B) = 1/2 Ene Eie d(a, b). where is the number of all pairs. The above distance is small if examples from classes A and B are located in the nearby leaf nodes (on average).
The obtained distance matrix presented in Figure (left) confirms that clusters discovered by Co- HiClust reveal many different patterns than the information encoded in the ground truth classes. While clothes are well separated from other items (number of edges greater than 6), cannot dis- tinguish particular clothes items from each other (distance between 3 and 4). As can be seen in Figure CoHiClust generated the hierarchy based on the sleeve length or the presence of designs. From this point of view, we can say that the results obtained by CoHiClust are complementary to the ground truth classification. However, we can also observe some similarities with ground truth classification: it is evident that the elements of the following 5 classes have not been spread between clusters: "trousers", "sandals". "sneakers", "bags" and "ankle boots" (we have d(A, < for these classes).
Evaluation on large image datasets In addition to comparing CoHiClust with hierarchical base- lines on gray images, we perform the evaluation on large datasets of color images: CIFAR-10, STL-10, ImageNet-Dogg, and ImageNet-10. Since none of the previous hierarchical methods have been examined on these datasets, we use typical agglomerative hierarchical algorithms applied ei- ther to raw image data or to the representation generated by our model. Additionally, to compare with a more diverse set of methods, we use the benchmark including flat clustering methods re- ported in Li et al. (202 It is expected that flat clustering methods will perform better because they directly focus on partitioning data into a given number of groups Hierarchical models, such as CoHiClust, build hierarchy with the number of leaves exceeding the number of classes, which
7

---

Under review as a conference paper at ICLR 2023
ROOT
spars
contarer dlip 30%
Andi
Figure 3: A tree hierarchy generated by CoHiClust for ImageNet-10. The left sub-tree contains examples related to the means of transport with neighboring leaves occupied by visually similar classes such as sports cars and trailer trucks (first two leaves from the left) as well airliners, airships, and container ships (next three leaves). Interestingly, airliners and airships photographed in the sky are assigned to different cluster than analogical objects located on the ground. In the right sub-tree, CoHiClust almost perfectly clustered examples two classes: Maltese dog and snow leopard. Surprisingly, images with ball in the foreground (without people) grouped together with oranges because of their circular shape. Soccer balls accompanied by the player are considered more similar to the images with penguins (their shapes are also similar). Nevertheless, all images of penguins are assigned to the neighboring leaves.
02
55
Poleer
37
70
30
40
A3
R
8
2
(a) F-MNIST
(b) ImageNet-10
Figure 4: Distance matrices retrieved from the constructed hierarchies for ground truth classes, see text in the paper for the interpretation.
makes difficult to obtain so high a resemblance with the ground truth as flat models. Moreover, the optimization of hierarchy is more difficult and challenging process because final assignments rely on aggregating several binary decisions made by the internal nodes.
Our model uses ResNet34 as base network, which better suits the complexity of the current images and coincides with the architecture used in Li et al. (2021a). We consider tree with 16 leaves (4 levels), which is next pruned to obtain the number of clusters equal to the number of ground truth
8

---

Under review as a conference paper at ICLR 2023
classes. We train the initial complete tree with the batch size of 256 for 1000 epochs and use 100 epochs after pruning every leaf. To measure the similarity of the constructed partition with the ground truth, we apply three widely-used clustering metries: normalized mutual information (NMI, clustering accuracy (ACC), and adjusted rand index (ARI). In the appendix, we also show DP of the hierarchies generated by CoHiClust.
Table 3: Comparison with flat (top) and hierarchical (bottom) clustering methods on large image benchmarks.
Dutuset
CIPAR-1O
STL-10
ImsaeNNe-11 IO
ImageNaz-Doge
Metrics
ACC
ARI
NMI
ACC
NMI
ACC
ARI
NMI
ACC
ARI
K-mean-Maa
0.049
0.125
0.119
0.241
0.057
0,020
SC
3e2mmi ZehnicMinrrr Minurr & Percmul
0.103
0.247
0.085
0.098
0.159
0.048
0.151
0.274
0.076
0.038
0.111
0,013
ACT
1978
0.105
0.228
0.065
0.259
0.332
0.140
0.138
0.342
0.067
0.037
0.130
0.021
NMF
0.190
0.034
0.096
0.046
0.132
0.230
0.065
0.044
0.016
AB
0.239
0.314
0.169
0.250
0.303
0.161
0.310
0.317
0.152
0.104
0.185
0,073
DA
DAPVIESR Vileeil of
2010
0.251
0.297
0.163
0.224
0.302
0.152
0.506
0.304
0.138
0.104
0.100
0.078
DOGAX Killerd
2015
0.265
0.315
0.176
0.210
0.298
0.139
0.225
0.346
0.157
0.121
0.174
0.078
DeCNN
0.282
0.174
0.313
VAF Kihooss wallin
2013
0.345
0.291
0.167
0.200
0.282
0.
0.193
0.334
0.168
0.107
0.179
0.079
JUL Yann at 201h
0.192
0,272
0.138
0.182
0.277
0.164
0.175
0.300
0.138
0.054
0.135
0.028
DEC
Ku (201))
0.257
0.301
0,161
0.276
0.359
0.186
0.282
0.381
0.203
0.122
0.195
0.079
Clling 201
0.522
0.306
0.527
0.111
Came DDC
0:424
0.524
0.329
0.371
0,489
0.267
0.433
0.577
0.345
0.239
0.306
0.128
DOCk Wa A119
0.496
0.623
0.408
0.376
0.462
0.262
0.608
0.710
0.555
0.321
0.383
0.182
PICA Jonnn 2020
0.591
0.696
0.512
0.611
0.713
0.531
0.502
0.870
0,761
0.352
0.352
0.201
CC(Lra ar
0.790
0.637
0.764
0.893
0.822
0.274
Aggion. on F2W image
0185
0.04
0.207
0.079
0.342
0.207
0.181
0.072
0.295
0.101
0.017
0.151
Agglom. on pre-trainad rep.
0.350
0.503
0.255
0.464
0.477
0.521
0.530
0.532
0.345
0.252
0,092
0.276
CoHHClust
0.638
0.453
0.386
0.742
0.744
0.393
The results presented in Table 3 show that CoHiClust outperforms hierarchical baselines with large margin (bottom rows). Moreover, it is usually among the three best- best-performing flat methods (top rows). It gives very good results, compared to the baselines, on the subset of the ImageNet dataset achieving 0.742 of NMI. Nevertheless, one should keep in mind that CoHiClust is the only hierarchical method in this comparison, which makes it more challenging to construct flat partition, which resembles the ground truth classes
To better analyze the results returned by CoHiClust, we plot the constructed clustering hierarchies and distance matrices calculated for ground truth classes. Figure 3 presents and discusses the tree hierarchy constructed for ImageNet-10 (remaining hierarchies together with distance matrices are presented in the appendix). Supporting the analysis with the use of distance matrix, we can ob- serve that examples of out of 10 classes have not been spread across different clusters (we have d(A, A) < 1). Airliner and airship classes are the most semantically similar. The class king penguin is the most distinct from the classes representing the means of transport with an average distance greater than 7. Overall,
can see very high similarity between classes related to the means of transport. The distance between other classes is not as small, which suggests that there are no evident patterns that connect e.g. king penguin, Maltese dog, or orange.
5 CONCLUSION AND FUTURE DIRECTIONS
We proposed a contrastive hierarchical clustering model CoHiClust, which suits well clustering of large-scale image databases. The hierarchical structure constructed by CoHiClust delivers signif- icantly more information about data than typical flat clustering models. In particular, we can inspect the similarity between selected groups by measuring their distance in the hierarchy tree and, in con- sequence, find super-clusters. Experimental analysis performed on typical clustering benchmarks confirms that the produced partitions have high similarity with ground truth classes. At the same time CoHiClust allows for discovering important patterns which have not been encoded in the class labels.
In future, we plan to apply the constructed model to other unsupervised problems such as anomaly detection. Moreover, we will work constructing clustering hierarchies which are not restricted to a predefined topology. In particular, inspired by Tanno et al. (201)): Struski et al. (2021). I) we will
focus on models, which automatically adapt the hierarchy structure given dataset. Finally, it is an open issue whether it is possible to extend flat clustering models Li et al. 2002 Hual to the hierarchical ones, which could further improve the clustering metrics.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Stephan Alaniz, Diego Marcos, Bernt Schiele, and Zeynep Akata. Learning decision trees recur- rently through communication. Proceedings the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 25518-1357, 2021.
Anwesha Barai and Lopamudra Dey. Outlier detection and removal algorithm in k-means and hier- archical clustering. World Journal of Computer Application and Technology, 5(2):24-29, 2017.
Yoshua Bengio, Pascal Lamblin, Dan Popovici, and Hugo Larochelle. Greedy layer-wise training of deep networks. In B. Schölkopf, J. Platt, and T. Hoffman (eds.), Advances in Neural Information Processing Systems. MIT Press.
Anil Bhattacharyya. On measure of divergence between two multinomial populations. Sankhyä: the indian journal of statistics, pp. 401-406 1946.
J. Chang, Guo, L. Wang, G. Meng. S. Xiang, and C. Pan. Deep discriminative clustering analysis. arXiv preprint arXiv: 1905:0:900006660 2019.
Jianlong Chang, Lingfeng Wang, Gaofeng Meng, Shiming Xiang, and Chunhong Pan. Deep adap- tive image clustering. In Proceedings of the IEEE International Conference Computer Vision (ICCV), Oct 2017.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple frame- work for contrastive learning of visual representations. Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 1597-1607. PMLR, 13-18 Jul 2020. URL https://prooe
ngs ml www.sppeessee...
http//he22... html]
Sumit Chopra, Raia Hadsell, and Yamn LeCun. Learning a similarity metric discriminatively, with application to face verification. In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), volume 1, pp. 539-546. IRRE, 2005.
Zhiyuan Dang, Cheng Deng, Xu Yang, Kun Wei, and Heng Huang. Nearest neighbor matching for deep clustering. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 13693-13702, 2021.
Nicholas Frosst and Geoffrey Hinton. Distilling neural network into soft decision tree. arXiv preprint MtXiv:1711.09988 2017.
K. Chidananda Gowda and Krishna. Agglomerative clustering using the concept of mutual near- est neighbourhood. Pattern Recognition, 10: 10t1005-1,, 1978.
Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent-a new approach self-supervised learning. Advances in neural information processing systems, 33:21271 2020.
Joris Guérin, Olivier Gibaru. Stéphane Thiery, and Eric Nyiri. Cnn features are also great at unsu- pervised classification. arXiv preprint 1cXiv:1707.000 01700, 2017.
Xifeng Guo, Long Gao, Xinwang Liu, and Jianping Yin. Improved deep embedded clustering with local structure preservation. In Ijcai, pp. 1753-1759, 2017a
Xifeng Guo, Xinwang Liu, En Zhu, and Jianping Yin. Deep clustering with convolutional autoen- coders. In International conference on neural information processing, pp. 373-382, Springer, 2017b.
10

---

Under review as a conference paper at ICLR 2023
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 9726-9735 2020. doi: 10. 10.1 N011099CCPP422000200000999
Weihua Hu, Takeru Miyato, Seiya Tokui, Eiichi Matsumoto, and Masashi Sugiyama. Learning discrete representations via information maximizing self-augmented training. In International conference on machine learning, pp. 1558-1567. PMLR, 2017.
Jiabo Huang, Shaogang Gong, and Xiatian Zhu. Deep semantic clustering by partition confidence maximisation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 8849-8858, 2020.
Xu Ji, João F Henriques, and Andrea Vedaldi. Invariant information clustering for unsupervised image classification and segmentation. Proceedings of the IEEE International Conference on Computer Vision, pp. 9865-98744 2019.
D. P. Kingma and M. Welling. Auto-encoding variational bayes. arXiv preprint 1eXXvv13112.1111 2013.
Ari Kobren, Nicholas Monath, Akshay Krishnamurthy, and Andrew McCallum. A hierarchical algo- rithm for extreme clustering. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 255 264, 2017.
Jyoti Lakhani, Anupama Chowdhary, and Dharmesh Harwani. Clustering techniques for biological sequence analysis: A review. Journal of Applied Information Scienc, 3(1): 14-322,,, 2015.
Yunfan Li, Peng Hu, Zitao Liu, Dezhong Peng, Joey Tianyi Zhou, and Xi Peng. Contrastive clus- tering. Proceedings of the AAAI Conference on Artificial Intelligencce, (5))5855577885 May
2021a. ht ojs. aaai bezzg/iindex. php
Yunfan Li, Peng Hu, Zitao Liu, Dezhong Peng, Joey Tianyi Zhou, and Xi Peng. Contrastive clus- tering. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 8547- 8555, 2021b.
Dominik Mautz, Claudia Plant, and Christian Böhm. Deep embedded cluster tree. In 2019 IEEE International Conference Data Mining (ICDM), pp. 1258-126: IEEE, 2019.
Dominik Mautz, Claudia Plant, and Christian Böhm. Deepect: The deep embedded cluster tree. Data Science and Engineering, 5(4):419 432.9944322200 2020.
Takeru Miyato, Shin-ichi Maeda, Masanori Koyama, and Shin Ishii. Virtual adversarial training: a regularization method for supervised and semi-supervised learning. IEEE transactions on pattern analysis and machine intelligence, 41(8):1979-199) 1993, 2018
Murtagh and P. Contreras. Algorithms for hierarchical clustering: an overview. Wiley Interdiscip Rev Data Min Knowl Discoy, 2(1):86-97, 2012.
Stanislav Naumov, Grigory Yaroslavtsev, and Dmitrii Avdiukhin. Objective-based hierarchical clus- tering of deep embedding vectors. In AAAI, pp. 9055-9063. 2021.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint arXiv: 1511106431,, 1 2015.
Marek Smieja, Dawid Warszycki, Jacek Tabor, and Andrzej Bojarski. Asymmetric clustering index in a case study of 5-htla receptor ligands. PloS one, 102).9, 2014.
Lukasz Struski, Tomasz Danel, Marek Smieja, Jacek Tabor, and Bartosz Zieliński. Song: Self- organizing neural graphs. arXiv preprint arXiv:2107.13214 2021.
Ryutaro Tanno, Kai Arulkumaran, Daniel Alexander, Antonio Criminisi, and Aditya Nori. Adaptive neural trees. In International Conference Machine Learning, pp. 6166-6161111 6175. PMLR, 2019.
Pascal Vincent, Hugo Larochelle, Isabelle Lajoie, Yoshua Bengio, and Pierre-Antoine Manzagol. Stacked denoising autoencoders: Learning useful representations in a deep network with local denoising criterion. Journal of Machine Learning Research, 13)13371--3400 2010.

---

Under review as a conference paper at ICLR 2023
Alvin Wan, Lisa Dunlap. Daniel Ho, Jihan Yin, Scott Lee, Henry Jin, Suzanne Petryk, Sarah Adel Bargal, and Joseph Gonzalez. Nbdt: neural-backed decision trees. arXiv preprint arXiv:2004.00221, 2020.
Jianlong Wu, Keyu Long, Fei Wang, Chen Qian, Cheng Li, Zhouchen Lin, and Hongbin Zha. Deep comprehensive correlation mining for image clustering. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), October 2019.
Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin. Unsupervised feature learning via non- parametric instance discrimination. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 3733-3742, 2018.
Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In International conference machine learning, pp. 478 487. PMLR, 2016.
Jianwei Yang, Devi Parikh, and Dhruv Batra. Joint unsupervised learning of deep representations and image clusters. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 5147-5156, 2016.
Ruipeng Yang, Dan Qu, Yekui Qian, Yusheng Dai, and Shaowei Zhu, An online log template ex- traction method based on hierarchical clustering. EURASIP Journal on Wireless Communications and Networking. 2019(D):1-12, 2019.
Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Self-supervised learning via redundancy reduction. In International Conference Machine Learning, pp. 12310- 12320. PMLR, 2021.
Matthew D. Zeiler, Dilip Krishnan, Graham W. Taylor, and Rob Fergus. Deconvolutional networks. In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp- 2528 2535, 2010.
Lihi Zelnik Manor and Pietro Perona. Self-tuning spectral clustering. In Advances in Neural Information Processing Systems.
Feng Zhang, Lin Li, Qiang Hua, Chun-Ru Dong, and Boon-Han Lim. Improved deep clustering model based semantic consistency for image clustering. Knowledge-Based Systems, 253:109507, 2022. ISSN 0950-7051. doi:
www. 2022.109507. URL http:::/w..sieeeeeeiiiei http://wwwcccaeecccccccceeeeeaaa 50950705122007560
Yuchen Zhang, Amr Ahmed, Vanja Josifovski, and Alexander Smola. Taxonomy discovery for personalized recommendation. In Proceedings of the 7th ACM international conference on Web search and data mining, pp. 243-252, 2014.
Quan Zou, Gang Lin, Xingpeng Jiang, Xiangrong Liu, and Xiangxiang Zeng. Sequence clustering in bioinformatics: an empirical study. Briefings in bioinformatics, 21(1):1-10, 2020.
12

---

Under review as a conference paper at ICLR 2023
A SUPPLEMENTARY QUALITATIVE RESULTS
In Figures 5 7 and & illustrate the tree hierarchies constructed by CoHiClust for the remaining datasets. Distance matrices for ground true classes generated from these hierarchies are shown in Figure
MNIST Observe that neighboring leaves contain images of visually similar classes, e.g. and O; and 9; 1 and 7. Such property holds also for nodes in the upper levels of the tree the left sub-tree contain digits with circular shapes, while the digits located in the right sub-tree consist of lines.
ROOT
6
7
2
5
6
9
V 71 4
9
7
2 2
9
9
7
4
9
7
7
2
2
6
6
4
9
9
/
7
2
2
9
6
4
4
7
7
L
99%
8
3
5
8
8
0
5 3
5 5
8
8
3
3
5
5 5
8
8
3
3
3
5
5
8
3
5
Figure 5: Tree hierarchy constructed for MNIST.
STL-10 It is evident that images that present means of transport (car, truck, airplane, ship) were grouped in different subtrees than images with animals (dog, cat, monkey, horse, deer). Only im- ages of birds were mixed up between these subtrees. Birds the sky or on water background were grouped together with airplanes, while others were assigned to the animal subtree. Such assign- ments are consistent with our intuition because the shape of the bird and the airplane is similar and the background is the same. The relation of the bird class with other classes is revealed in the dis- tance matrix, see Figure The second row shows high similarity to airplanes, while the level of similarity to animal classes is almost equal. Ships were considered to be more similar to airplanes than vehicles (cars, trucks), which also confirms intuitive behavior of CoHiClust. animal subtree, the model grouped horses and deers in the neighbor leaves, which is also reflected in the distance matrix. Most of the images that presented dogs and cats were also classified in the same subtree containing three leaves, suggesting their similarity.
case of
The analysis of the hierarchy of CIFAR-10 reveals similar relations in the case of STL-10 - we have division into machines and animals in the first level. Moreover, airplanes and birds were considered to be similar classes. In contrast to STL-10, we can observe that CoHiClust created two neighbor groups for animals with white and black fur, respectively. This grouping was associated more with color than with the type of animal. We consider this behavior to be natural, even if it breaks the boundary between ground-truth classes. We emphasize that decisions made by CoHiClust are not based on classes but only on the type of augmentation. Nevertheless, CoHiClust was able create individual clusters dominated by the following classes: frogs, deers, horses, trucks, and cars. By analyzing the distance matrix, we can observe pairs of similar classes: plane and ship, dog and horse, etc.
CIFAR-10
13

---

Under review as a conference paper at ICLR 2023
ROOT
2016
cen D0N
deen 2316
monday 30%
Kiy 23% mankey
Figure 6: Tree hierarchy constructed for STL-100
ROOT
bird: 29%
plane: 56% truck: 86%
car: 91%
plane: 25% ship: 68%
deer: 68%
horse: 70%
deer: 16%
frog: 67% cat: 44%
cat: 30%
dog: 59%
dog: 26%
horse: 22%
bird: 19%
Figure Tree hierarchy constructed for CIFAR-10.
B ANALYSIS OF THE COHICLUST MODEL
In this section, we analyze selected properties of CoHiClust including the choice of backbone net- work, the form of the loss function, techniques for reducing the number of leaves and possible training strategies. If not stated otherwise, the experiments were run on CIFAR- 10 dataset, which consider the most representative.
14

---

Under review as a conference paper at ICLR 2023
RDOT
Figure 8: Tree hierarchy constructed for ImageNet- Dogs.
pane
7.0
9/1
6:0
5.0
60
2.0
7.0
R0
DUV
7.9
6.0
AD
7.9
S-5
5.D
A11
1.5
4.1
5.0
6.1
rLdk
Pog
(a) MNIST
(b) CIFAR-10
A+
45
68
47
66
44
17
Hallow
26
T6
75 72
Saase
Nervepinn
25
50
Cutbin
Saltary
45
20
Shedlnd
eaetar
Pvg
Canst
Cart
Ounder
DOSTR
oor
(c) STL-10
(d) ImageNet-Dogg
Figure 9: Distance matrices retrieved from the constructed hierarchies for ground truth classes.
B. RELIANCE ON BACKBONE NETWORK
In Table 4 show how the selection of the architecture for the base network g influences the performance of CoHiClust. As can be seen, the difference in the results is marginal.
B.2 ANALYSIS LOSS FUNCTION
Next, explain the influence of particular components of CoHiClust loss function. Namely, remove one or both regularization terms from the loss function and report the results. As shown in Table 5 R2 regularization (NT-XENT)) has notable impact the metrics, since it improves the
15

---

Under review as a conference paper at ICLR 2023
Table 4: Comparison of ResNet architectures.
Dataset
CIFAR-IO
STL-10
Metrics
NMI
ACC
ARI
NMI
ACC
ARI
ResNet18
0.481
0.510
0.362
0.503
0.529
0.386
ResNet34
0.532
0.638
0.453
0.498
0.467
0.366
representation of data. However, the obtained model has a tendency to build smaller tree and reduce clusters during training (third row). The influence of Ri (entropy) on the quality of clustering is marginal, but this term crucial for balancing decisions made by the internal nodes and preventing from clusters reduction (second row). Combining both regularization terms allows us to build complete hierarchy with satisfactory metrics.
Table Ablation study of CoHiClust loss function performed on CIFAR-10.
DP
NMI
ACC
ARI
Clusters
CoHiLoss
0.187
0.271
0,289
0.172
4
CoHiLoss R1
0.192
0.260
0.296
0.181
12
CoHiLoss + R2
0.444
0.519
0.613
0,425
9
CoHil + R1 + R2
0.446
0.532
0.639
0.453
Following the above analysis, observe that CoHiClust can automatically detect the number of clusters we eliminate the entropy regularization. More precisely, R2 is essential for delivering appropriate representation of data, while R₁ is only used to maintain the requested number clusters. we are interested in generating hierarchy of the size automatically adjusted to a given dataset, then we have to put $1 0 and 82 1.
B.3 ALTERNATIVE DEFINITIONS OF THE LOSS FUNCTION
Let us recall that the proposed CoHil Loss contains the square root to enable the model to explore possible tree paths, equation T If we do not the square root, encourage the model to binarize decisions in nodes, which can lead to stacking in local minima at the initial phase of training. The results Table 6 show that the model with square root obtains better metrics than the one without the square root. It partially confirms our initial hypothesis that using the square root influences positively on the exploration of the tree.
Table 6: The influence of the square root in CoHiLoss.
DP
NMI
ACC
ARI
CoHiClust w/ square root CoHiClust w/o square root
0.402
0.446
0.425
0.297
0.342
0.410
0.425
0.283
CoHiClust w/ square root (pruned)
0.447
0.532
0.638
0,453
CoHiClust w/o square root (pruned)
0.387
0.457
0.572
0.373
B.4 COMPARING TECHNIQUES FOR REDUCING THE NUMBER OF LEAVES
Complete hierarchy is useful tool to analyze the relationships between data. To generate the hierarchy with smaller number of leaves we have the following options:
Eliminate entropy regularization from the loss function (8) 0). In this case, the model automatically detects the number of groups.
Reduce the least significant leaves simultaneously with fine-tuning the model. Fine-tuning is performed during pruning and after obtaining the final model (our default strategy).
Delete the least significant leaves without fine-tuning. This corresponds to one of typical pruning strategies used in decision trees.
Delete the least significant and next train the model from scratch but with the new tree structure.
16

---

Under review as a conference paper at ICLR 2023
Table shows the clustering metrics for the obtained models evaluated CIFAR- 10. As can be seen, pruning combined with fine-tuning gives the best results (third row), improving significantly the clustering structure delivered by the complete hierarchy (second row). Slightly lower metrics are obtained when we retrain the reduced tree from scratch (fifth). The model without fine-tuning (fourth row) also gives higher scores than the base model without pruning. however the gain in clustering metrics is not so high. This shows that fine-tuning the pruned model is an essential step leading in adjusting the hierarchy to given number of groups. It is notable that the model without entropy regularization (31 0) is able to reasonably well detect the number of clusters as well as produce satisfactory results. obtains better clustering metries than the model with pruning but without fine-tuning.
Table 7: Comparing techniques for reducing the number of leaves.
DP
NMI
ACC
ARI
#Clusters
CoHiClust (81 = 0)
0,403
0.486
0.569
0.390
9
CoHiClust (w/o pruning)
0,402
0.446
0.425
0.297
16
CoHiClust (pruning and fine-tuning)
0.447
0.532
0.638
0.453
10
CoHiClust (pruning only)
0.404
0.461
0.570
0.373
10
CoHiClust (pruning and retraining from scratch)
0,436
0.519
0.616
0.437
10
B.5 END-TO-END TRAINING VS. PRE-TRAINED REPRESENTATIONS
Finally, we examine whether end-to-end training is crucial for the performance of CoHiClust. For this purpose, first pretrain the base network g using NT-Xent loss, which corresponds to the typical SimCLR model Chen et al. (2020). Next, we add the projection head to and train CoHiClust using CoHiLoss++ + R2 loss. As can be seen in Table the model trained an end-to-end manner obtains significantly better scores.
Table 8: Training CoHiClust end-to-end vs. training CoHiClust representation taken from pre- trained SimCLR.
NMI
ACC
ARI
end-to-end training
0.532
0.638
0.453
pretrained representation
0.434
0.480
0.297
C DENDROGRAM PURITY FOR DATASETS OF COLOR IMAGES
In Table we present dendrogram purity obtained by CoHiClust for datasets of color images. This benchmark can be used to compare other hicrarchical clustering models.
Table 9: Dendrogram purity on color images.
DP
CIFAR-10
0.447
STL-10
0.345
ImageNet-Il 10
0.613
ImageNet-Dogs
0.198
17


Reviews:
[{"review_id": "XJH05p5yA3", "reviewer": "Reviewer_Xeet", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed a contrastive hierarchical clustering model CoHiClust which attempts to learn a binary tree clustering structure rather than typical flat clustering. \nA pruning strategy is introduced to create a fixed number of leaves by removing a leaf and retraining the model iteratively.\n Experimental analysis performed on typical clustering benchmarks confirms that the produced partitions have high similarity with ground truth classes. ", "summary_of_the_review": "Overall it is not difficult to parse and is well-organized. However, the paper’s claims recall more large-scale datasets in the experiment. The pruning stage takes a long time according to the tree depth, which in the worst case is very high.", "strength_and_weaknesses": "Strength: The paper is written clearly. The topic is somehow interesting.\nThe paper evaluates on various datasets.\n\nWeakness:\n\n1. The authors claim that the pruning strategy will \"Assume that the importance of the cluster is related to the average number of assigned examples. We reduce a leaf with the lowest probability. After removing the leaf, we finetune the whole model using CoHiClust loss. If we want to reduce more leaves, we perform leaf pruning and model retraining iteratively until the requested number of leaves is obtained.\" This might just take a much longer time to re-train the model, which needs more discussion and comparison on the training efficiency.\n2. CC and PIC often show better performance than the proposed CoHiClust with a large margin, which might suggest that the authors look into the deeper reason for the results and see if any suitable hierarchical clustering data can be utilized in the experiments that can justify the efficacy of the method.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Gnknr8ytCp", "reviewer": "Reviewer_PDcK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed a hierarchical clustering model with a designed contrastive objective. It decomposes the classification into a series of the decision process as a binary tree. To make the structure more flexible, a pruning strategy is developed. The results on CIFAR-10, STL-10, IN-10, and IN-Dogs show the proposed method still has some performance gap with the SOTA \"flat\" clustering methods. But, the results of MNIST and FMNIST show the proposed method beats other hierarchical clustering methods. ", "summary_of_the_review": "In general, the reviewer likes the direction, and the proposed method can bring some fresh air to the community. However, the reviewer hopes the author can address the abovementioned concerns, especially about the new qualitative results on large-scale datasets and the ablation studies in the pruning strategy. ", "strength_and_weaknesses": "The reviewer believes the studied direction and problem are very important for deep learning and representation learning. This paper proposed an interesting perspective to model the classification as a binary tree decision process. A proper contrastive objective is proposed to make the framework trainable. Overall the paper is easy to follow.\n\nExtensive results are conducted in MNIST, FMNIST, CIFAR-10, STL-10, IN-10, and IN-Dogs and show the strength of the proposed hierarchical method compared to other hierarchical clustering and the classification gap between the \"flat\" clustering method, which are good for readers to understand what the proposed method has achieved. However, the qualitative results are a bit limited for people to understand if the approach really can generate proper hierarchies. Not many ablation studies are included.\n\nThe reviewer is unsure if Mautz et al is the only related hierarchical clustering proposed in the deep learning era, as mentioned in the introduction. Some related methods could be developed in understanding or utilizing class hierarchy papers, such as [1] Large-Scale Few-Shot Learning: Knowledge Transfer With Class Hierarchy (***not need to cite***). The reviewer feels some application papers in CV and NLP may have developed related methods to hierarchical clustering, including agglomerative clustering. \n\nThe proposed method assumes fixed height, which is a major limitation. Also, the proposed pruning strategy requires fine-tuning, which makes this step pretty ad-hoc because we can also set up a new structure and re-train from scratch. No ablation studies have been conducted to prove the pruning strategy is effective for improving performance or helping find tree hierarchy. \n\nAccording to Table 3, there are big gaps between the proposed clustering method and the previous ones, which is ok if the author can prove the proposed clustering alg can help find class hierarchy in large-scale datasets. However, the current experiments are limited to ImageNet-10 and ImageNet-Dogs. Training on ImageNet and comparing standard contrastive learning results can help here.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "G7IPxuQzwoD", "reviewer": "Reviewer_4K5k", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Please refer to Summary Of The Review.", "summary_of_the_review": "This paper applies the deep neural networks technology to clustering and establishes a novel clustering model which is dubbed CoHiClust. In this model, a contrastive learning method is employed to create the base network (i.e. a binary tree).so that the original data are represented on a higher-level. Then two regularization strategies are used to make the base neural network train with the arbitrary number of leaves. The cluster assignment of each sample is achieved by aggregating binary decisions. Besides, to create a tree with a fixed number of leaves, a pruning step is added. The experiments conducted on large-scale image datasets shows the CoHiClust better clustering performance compared to some existing deep and flat clustering algorithms.\n\nDeep clustering is a research hotspot in machine learning in recent years, so the topic in this paper is up-to-date and meaningful. The work of this paper has a certain degree of innovation, but there are some issues or suggestions that I want to point out.\n\n1) Section 1 lacks a sound analysis of research motivation. Why combine deep neural network with hierarchical clustering? A relevant algorithm DeepECT has been proposed, so why further research on this topic? Why is it important to examine the algorithm to large-scale image datasets?\n2) The specific meaning of parameters \\beta_1and \\beta_2 in Eq. (1) and the basis for their values should be added. Further, in the experimental part there should be an analysis of the impact of their different values on CoHiClust performance.\n3) In terms of experimental design, why only large-scale image datasets are used to test the performance of used algorithms? Can the algorithm proposed in this paper be applied to other types of datasets? The key point is that the proposed CoHiClust model does not seem to have a special design for large-scale image data. \n4) What does the abbreviation AE in Table 1 refer to? Classical hierarchical clustering algorithm?\n5) When analyzing the clustering hierarchies on page 7, why not compare CoHiClust with the classical hierarchical clustering algorithms or the latest ones? To further evaluate the validity of this paper work, I strongly recommend adding this comparison.\n6) The readability of the tables must be improved. For example, the best values can be in bold.\n7) I highly recommend to the authors to add open issues and future directions of their work.\n\nTo sum up, this paper need more revisions for its presentation and more experimental work.\n", "strength_and_weaknesses": "Please refer to Summary Of The Review.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0-voYmbCvQ", "reviewer": "Reviewer_8rQe", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper focuses on hierarchical clustering which could build a hierarchy of clusters. The proposed method leverage some self-supervised learning techniques to obtain a high-level representation that is used for tree hierarchy building. As the proposed method is a deep model trained in an end-to-end manner, it could be applied to the large-scale dataset for hierarchical clustering. Some qualitative examples show that the proposed method can yield a good tree hierarchy.", "summary_of_the_review": "This paper proposes a new deep hierarchical clustering model for large-scale data. The paper is well-written. However, the contribution and novelty of this paper are limited.", "strength_and_weaknesses": "Strength:\n1. By incorporating hierarchical clustering into the deep model, the proposed method could be easily applied to large-scale data.\n2. The presentation is easy to follow.\n\nWeaknesses:\n1. My major concern is that the novelty is insufficient. It seems that the proposed method only uses some self-supervised methods for representation learning and combines them with some hierarchical clustering techniques. Although there are no specific models for performing hierarchical clustering under the contrastive learning framework, the existing techniques are somehow ready to apply like Contrastive Clustering. The novelty in terms of the solution technique is thus limited.\n2. The authors claimed that the proposed method could achieve comparable performance to the SOTA clustering methods, but the results from Table 3 show a large gap between the proposed method and the SOTA baselines.\n3. From Table 1 and Table 2, I notice that the DeepECT + Aug could achieve similar performance to the proposed method. So here comes the question: In the proposed method, is the augmentation technique from self-supervised learning the primary reason for boosting the performance? I wonder about the influence of different components of the proposed method on the final results. However, I didn't see any ablation studies about this. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject