Effective Cross-instance Positive Relations for Generalized Category Discovery
Authors: Shaozhe Hao
Kai Han
Kwan-Yee K. Wong
Venue: Submitted to ICLR 2023 (2023)
Keywords: generalized category discovery
semi-supervised learning
clustering
deep learning

Abstract: We tackle the issue of generalized category discovery (GCD). GCD considers the open-world problem of automatically clustering a partially labelled dataset, in which the unlabelled data contain instances from novel categories and also the labelled classes. In this paper, we address the GCD problem without a known category number in the unlabelled data. We propose a framework, named CiP, to bootstrap the representation by exploiting Cross-instance Positive relations for contrastive learning in the partially labelled data which are neglected in existing methods. First, to obtain reliable cross-instance relations to facilitate the representation learning, we introduce a semi-supervised hierarchical clustering algorithm, named selective neighbor clustering (SNC), which can produce a clustering hierarchy directly from the connected components in the graph constructed by selective neighbors. We also extend SNC to be capable of label assignment for the unlabelled instances with the given class number. Moreover, we present a method to estimate the unknown class number using SNC with a joint reference score considering clustering indexes of both labelled and unlabelled data. Finally, we thoroughly evaluate our CiP framework on public generic image recognition datasets (CIFAR-10, CIFAR-100, and ImageNet-100) and challenging fine-grained datasets (CUB, Stanford Cars, and Herbarium19), all establishing the new state-of-the-art.

Under review as a conference paper at ICLR 2023
EFFECTIVE CROSS-INSTANCE POSITIVE RELATIONS FOR GENERALIZED CATEGORY DISCOVERY
Anonymous authors Paper under double-blind review
ABSTRACT
We tackle the issue of generalized category discovery (GCD). GCD considers the open-world problem of automatically clustering a partially labelled dataset, which the unlabelled data contain instances from novel categories and also the labelled classes. In this paper, we address the GCD problem without a known category number in the unlabelled data. We propose a framework, named CiP, to bootstrap the representation by exploiting contrastive learning in the partially labelled data which are neglected in existing methods. First, to obtain reliable cross-instance relations to facilitate the represen- tation learning, we introduce a semi-super hierarchical clustering algorithm, named selective neighbor clustering (SNC), which can produce a clustering hierar- chy directly from the connected components in the graph constructed by selective neighbors. We also extend SNC to be capable of label assignment for the unlabelled instances with the given class number. Moreover, we present a method to estimate the unknown class number using SNC with joint reference score considering clustering indexes of both labelled and unlabelled data. Finally, we thoroughly evaluate our CiP framework on public generic image recognition datasets (CIFAR- 10. -IFAR-100, and ImageNet- -00) and challenging fine- tne-grained datasets (CUB, Stanford Cars, and Herbarium all establishing the new state-of-the-art.
posss-instance Positive relations for
INTRODUCTION
After training on large-scale datasets with human annotations, existing machine learning models can achieve superb performance (e.g.. (Krizhevsky et al.. 2012)). However, the success of these models heavily relies on the fact that they are only tasked to recognize images from the same set of classes with large-scale human annotations on which they are trained. This limits their application in the real open world where we will encounter data without annotations and from unseen categories. Indeed, more and more efforts have been devoted dealing with more realistic settings. For example, semi-supervised learning (SSL) (Chapelle et al., 2006) aims at training a robust model using both labelled and unlabelled data from the same set of classes; few-shot learning (Snell et al., 2017) tries to learn models that can generalize to new classes with few annotated samples; open-set recognition (OSR) (Scheirer et al., 2012) learns to tell whether or not an unlabelled image belongs to one of the classes which the model is trained. More recently, the problem of novel category discovery (NCD) (Han et al., 2019; 2020; Fini et al., 2021) has been introduced, which learns models to automatically partition unlabelled data from unseen categories by transferring knowledge from seen categories. One assumption in early NCD methods is that unlabelled images are all from unseen categories only. NCD has been recently extended to more generalized setting, called generalized category discovery (GCD) ( (Vaze et al., 2022b), by relaxing the assumption to reflect the real world better, i.e., unlabelled images are from both seen and unseen categories.
In this paper, we tackle the problem of GCD by drawing inspiration from the baseline method (Vaze et al., 2022b). (Vaze et al., 2022b), a vision transformer model was first trained for representation learning using supervised contrastive learning on labelled data and self-supervised contrastive learning on both labelled and unlabelled data. With the learned representation, semi-supervised k-means (Han et al., 2019) was then adopted for label assignment across all instances. In addition, based on semi- superiuper k-means, (Vaze et al., 2022b) also introduced an algorithm to estimate the unknown category number for the unlabelled data by examining possible category numbers in given range. However, this approach has several limitations. First, during representation learning, the method considers labelled and unlabelled data independently, and uses stronger training signal for the

---

Under review as a conference paper at ICLR 2023
labelled data which might compromise the representation of the unlabelled data. Second, the method requires a known category number for performing label assignment. Third, the category number estimation method is slow it needs to run the clustering algorithm multiple times to test different category numbers.
To overcome the above limitations, we propose new approach for GCD which does not require known unseen category number and considers Cross-instance Positive relations in unlabelled data for better representation learning (CiP). At the core of our approach is our novel semi-supervised hierarchical clustering algorithm with selective neighbor, named as selective neighbor clustering (SNC), that takes inspiration from the parameter-free hierarchical clustering method FINCH (Sarfraz et al.. 2019). SNC can not only generate reliable pseudo labels for cross- -ooss-inttance positive relations, but also estimate unseen category numbers without the need for repeated runs of the clustering algorithm. SNC builds graph indicating all subtly selected neighbor relations constrained by the labelled instances, and produces clusters directly from the connected components in the graph. SNC iteratively constructs hierarchy of partitions with different granularity, while satisfying the constraints imposed by the labelled instances. With a one-by-one merging strategy, SNC can quickly estimate reliable class number without repeated runs of the algorithm, which makes it significantly faster than (Vaze et al., 2022b).
The main contributions of this paper can be summarized follows: (1) we propose new GCD framework, named CiP, exploiting more cross-instance positive relations in the partially labelled set to strengthen the connections among all instances, fostering the representation learning for better category discovery; (2) we introduce a semi-supervised hierarchical clustering algorithm, named SNC, that can be adopted for reliable pseudo label generation during training and label assignment during testing; (3) we further leverage SNC for class number estimation by exploring intrinsic and extrinsic clustering quality based on a joint reference score considering both labelled and unlabelled data; (4) we comprehensively evaluate our CiP framework on both generic image recognition datasets and challenging une-grained datasets, and demonstrate state-of-the-arr performance across the board.
2 RELATED WORK
Our work is related to novel/generalized category discovery, semi-supervised learning, and open-set recognition.
Novel category discovery (NCD) aims at discovering new classes in unlabelled data by leveraging knowledge learned from labelled data. It was pioneered by (Han et al., 2019) with a transfer clustering approach. Some earlier works on cross-domann/tsee transfer learning (Hsu et al., 2018abb) can also be adopted to tackle this problem. (Han et al., 2020) proposed an efficient method called AutoNovel (aka RankStats) using ranking statistics. They first learned a good embedding using low-level self- supervised learning on all data followed by supervised learning on labelled data for higher level features. They introduced robust ranking statistics to determine whether two unlabelled instances are from the same class for NCD. Several successive works based on RankStats were proposed. For example, (Jia et al., 2021) proposed to use WTA hashing (Yagnik et al., 2011) for NCD in single- and multi-modal data; Zhao and Han (Zhao & Han, 2021) extended NCD with dual ranking statistics and knowledge distillation. (Fini et al., 2021) proposed UNO which uses unified cross entropy loss to train labelled and unlabelled data. (Chi et al., 2022) proposed meta discovery which links NCD to meta learning with limited labelled data. (Vaze et al., 2022b) introduced generalized category discovery (GCD) which extends NCD by allowing unlabelled data from both old and new classes. They first finetuned pretrained DINO ViT (Caron et al., 2021) with both supervised contrastive loss and self-superviser contrastive loss. Semi-supervised k-means was then adopted for label assignment. concurrent work called ORCA by (Cao al., 2022) addressed a similar problem by formulating as open- ween-world eupeesupereieed learning. We draw inspiration from (Vaze et al., 2022b) and develop novel method to tackle GCD by exploring cross-instance correlations on labelled and unlabelled data which have been neglected in (Vaze et al., 2022b).
Semi-supervised learning (SSL) has long been studied in the machine learning community (Chapelle et al., 2006). It aims at learning good model by leveraging unlabelled data from the same set of classes as the labelled data. Various methods have been proposed for SSL. For example, II- model (Laine & Aila, 2017) uses self-ensembling to leverage label predictions on different epochs and under different conditions; Mean Teacher (Tarvainen & Valpola, 2017) utilizes averaging model weights instead of label predictions; Fixhhtch (Sohn et al., 2020) and Flex (Zhang et al., 2021)
2

---

Under review as a conference paper at ICLR 2023
employ pseudo-labels generated from model predictions to guide the training. The assumption that labelled and unlabelled data are from the same closed set of classes is often not valid in practice. In contrast, GCD relaxes this assumption and considers a more challenging scenario where unlabelled data can also come from unseen classes.
Open-set recognition (OSR) aims training a model using data from a known closed set of classes, and at test time determining whether or not a sample is from one of these known classes. was first introduced in (Scheirer et al., 2012). Since then many methods have been proposed for this task. For example, OpenMax (Bendale & Boult, 2016) is the first deep learning work to address the OSR problem based on Extreme Value Theory and fitting per-class Weibull distributions. RPL (Chen et al., 2020a) and its extension ARPL (Chen et al., 2021) exploit reciprocal points for constructing extra-class space to reduce the risk of unknown. Recently, (Vaze et al., 2022a) found the correlation between closed and open-set performance, and boosted the performance of OSR by improving closed-set accuracy. They also proposed Semantic Shift Benchmark (SSB) with a clear definition of semantic novelty for better OSR evaluation.
3 METHODOLOOGY
3.1 PROBLEM FORMULATION
Generalized category discovery (GCD) aims at automatically categorizing unlabelled images in a collection of data in which part of the data is labelled and the rest is unlabelled. The unlabelled images may come from the labelled classes or new ones. This is a much more realistic open-world setting than the common closed-set classification where the labelled and unlabelled data are from the same set of classes. Let the data collection be D = Dr U D', where Dr = {(af, ) E X x Ve denotes the labelled subset and Du = {(=,", 3 E X x Viu denotes the unlabelled subset with unknown y Yu. Only subset of classes contains labelled instances, i.e., Ve c Vee The number of labelled classes N₂ can be directly deduced from the labelled data, while the number of unlabelled classes Nu is not known priori.
To tackle this challenge, we propose a novel framework CiP to jointly learn representations using contrastive learning by considering all possible interactions between labelled and unlabelled instances. Contrastive learning has been applied to learn representation in GCD, but without considering the connections between labelled and unlabelled instances (Vaze al., 2022b) due the lack of reliable pseudo labels. This limits the learned representation. In this paper, we propose an efficient semi- supervised hierarchical clustering algorithm, named selective neighbor clustering (SNC), generate reliable pseudo labels to bridge labelled and unlabelled instances during training and bootstrap representation learning. With the generated pseudo labels, we can then train the model on both labelled and unlabelled data in a supervised manner considering all possible pairwise connections. We further extend SNC with a simple one-by-one merging process to allow cluster number estimation and label assignment on all unlabelled instances. An overview of our CiP is shown in Fig. 1.
3.2 JOINT CONTRASTIVE REPRESENTATION LEARNING
Contrastive learning has been widely used for sulf-supe representation learning (Chen et al., 2020b; He et al., 2020) and supervised representation learning (Khosla et al., 2020). For GCD, since the data contains both labelled and unlabelled instances, the mix of self-supervised and supervised contrastive learning appears to be natural fit and good performance has been reported in (Vaze et al., 2022b). However, cross-instance correlations are only considered for pairs of labelled instances, but not for pairs of unlabelled instances and pairs of labelled and unlabelled instances. The learned representation is likely to be biased towards the labelled data due to the stronger learning signal provided by them. Meanwhile, the embedding spaces learned from cross-instance correlations of labelled data and self correlations of unlabelled data might not be necessarily well aligned. These might explain why a much stronger performance on labelled data was reported in (Vaze al., 2022b) compared with the unlabelled data. To mediate such a bias, we propose to introduce cross- instance relations for pairs of unlabelled instances and pairs of labelled and unlabelled instances in contrastive learning to bootstrap the representation learning. To this end, we propose an efficient semi-supervee supervied hierarchical clustering algorithm to generate reliable pseudo labels relating pairs of unlabelled instances and pairs of labelled and unlabelled instances, as will be detailed in Sec. 3.3. Next, we briefly review supervised contrastive learning (Khosla et al., 2020), which accommodates cross-instance relations, and describe how to extend it to unlabelled data.
3

---

Under review as a conference paper at ICLR 2023
Inttaizztion with DINO
Joint contrastive learning
Label assignment
true poatire relations
psoude postive
OOOO
Labelled instance
Undabelled inttance
Supervized with true posttive relations
Supeniised with pseudo positive relations
relation
parttton
Figure 1: Overview of our CiP framework. We first initialize ViT with pretrained DINO (Caron al., 2021) obtain a good representation space. We then finetune ViT by conducting joint contrastive learning with both true and pseudo positive relations in supervised manner. True positive relations come from labelled data while pseudo positive relations of all data are generated by our proposed SNC algorithm. Specifically, SNC generates hierarchical clustering structure. Pseudo positive relations are granted to all instances in the samee cluster at one level of partition, further exploited in joint contrastive learning. With representations well learned, we estimate class number and assign labels to all unlabelled data using SNC with a one-by-one merging strategy.
Let f and o be feature extractor and a MLP projection head. The supervised contrastive loss on labelled data can be formulated as
exp(z) 2g/Ta) EncBe exp(2} =///Ta)
C
log
(i( (E
where x" = =(f(x²)) Ta is the temperature, and GB(i) denotes other instances sharing the same label with the i-th labelled instance in Be, which is the labelled subset in the contrastive loss leverages the true cross -nossnnnttance positive relations between labelled instance pairs. To take into account the cross-instance positive relations for pairs of unlabelled instances and pairs of labelled and unlabelled instances, we extend the supervised contrastive loss on all data as
B. Supervised
exp(2; /
C
Σ log QEPB(1)
(2)
(Pb(i)
EneB,ngt exp(z; Zn/Ta.
where Ta is the temperature, PB(1) is the of pseudo positive instances for the i-th instance in the mini-batch B. The overall loss considering cross-instance relations for pairs labelled instances, unlabelled instances, as well as labelled and unlabelled instances can then be written as
L
C
Σ C
iEB2
With the learned representation, we can discover classes with existing algorithms like semi-supervised k-means (Han et al., 2019; Vaze et al., 2022b). We further propose new method in Sec. 3.4 based on our pseudo label generation approach as will be introduced next.
3.3 SELECTIVE NEIGHBOR CLUSTERING
To generate pseudo labels for Eq. (2), an intuitive approach would be to apply an off-the-shelf clustering method like k-means or semi- suni--upervised k-means to construct clusters and then obtain cross-instance relations based on the resulting cluster assignment. However, we empirically found that such simple approach will produce many false positive pairs which severely hurt the representation learning. One way to tackle this problem to overcluster the data to lower the false positive rate. FINCH (Sarfraz et al., 2019) has shown superior performance on unsupervised hierarchical overclustering, but is non-trin non-trivial to extend it to cover both labelled and unlabelled data. Experiments show that FINCH will fail drastically if we simply include all the labelled data. Inspired by FINCH. we propose an efficient semi-supervised hierarchical clustering algorithm, named SNC, with selective neighbor, which subtly makes use of the labelled instances during clustering.
4

---

Under review as a conference paper at ICLR 2023
FINCH constructs adjacency matrix A for all possible pairs of instances (i,j), given by
A(i,)) {1
1 if K2 or Ki i or R4 = Kiy
(4)
else
where K; is the first neighbor of the i-th instance and is defined
K₁ = arg max (f(xz) f(z)) 2, E D),
(5)
where f()) outputs an fz-normalized feature vector. A data partition can then be obtained by extracting connected components from A. Each connected component in A corresponds to one cluster. By treating each cluster as super instance and building the first neighbor adjacency matrix iteratively, the algorithm can produce hierarchical partitions.
First neighbor is designed for purely unlabelled data. To make use of the labels in partially labelled data, straightforward idea is to connect all labelled data from the same class by setting j) to 1 for all pairs of instances (i.j) from the same class. However, after filling A(i,j) for pairs of unlabelled instances using Eq. (4), very often all instances become con- nected to single cluster, making it impossible to properly partition data. This problem is caused by hav- ing too many links among the labelled instances. To solve this problem, would like to reduce the links between labelled instances while keeping la- belled instances from the same class
Algorithm Selective Neighbur Clustering (SNC)
1: Preparation:
2: Given labelled set Dr: and unlabelled set Duz treat each instance in
De U Dr as cluster of with the cluster centroid nf(e)) being each
instance itself, forming the first partition I 12 U I2 where
1= =<("),,__ 11111
3: Main Moon:
--0
5: while there are more than Ne clusters in I do Initialize 1% r
7: while there exists N. of ef. E 11% Ui not specified do
if c. e 1 then
Initialize @ [c_",, J. 12 = (cf).
10:
while Q < A do
11:
K; - arg maxy (m(c"))m(()) E =
12:
r r [e]
13:
QU c
14:
c cf
15:
end while
16:
else
in the same connected component. A simple idea is to connect same la- belled instances one by one form a chain, which can significantly re- duce the number of links. However, we found this still produces many in- correct links, resulting low purity of the connected components. To this end, we introduce our selective neighbor to improve the purity of clusters while properly incorpo- rating the labelled instances. The key ideas most X. Second, each labelled instance in a chain can only be the selective neighbor of another labelled instance once. Third, the selective neighbor of unlabelled instance can be labelled an unlabelled instance, depending on its actual distances to other instances. Similar to FINCH, we can apply selective neighbor iteratively produce hicrarchical clustering results. We name our method SNC which is summarized in Algo. 1 (lines 7-19 correspond to selective neighbor computation).
17:
<i c- aarg max, (u(c.) ulef)) lef e (ggrg)
18:
end if end while
19:
20:
Construct A following Eq. (4) with selective neighbors, forming
new partition [++1 r Jr
21:
22:
end while
follows. First, we limit the chain length to at
For the chain length X, we simply it the smallest integer great than equal the square root of the number of labelled instances n& in each class, i.e., À = /ne ]. This is applied to all classes with labelled instances, and at each hierarchy level. A proper chain length can therefore be dynamically determined based on the actual size of the labelled cluster and also the hierarchy level. We analyze different formulations of chain length in Appx. A.
SNC produces hierarchy of data partitions with different granularity. Except the bottom level, where each individual instance is treated as one cluster, every non-bottom level can be used to capture cross-instance relations for the level below, because each instance in the current level represents cluster instances in the level below. In principle, we can pick any non-bottom level to generate pseudo labels. To have higher purity for each cluster, is beneficial choose relatively low level which overelusters the data. Hence, we choose a level that has a cluster number notably larger than the labelled class number (e.g., 2x more). Meanwhile, the level should not be too low this will provide much fewer useful pair-wise correlations. In our experiment, we simply pick the third level
5

---

Under review as a conference paper at ICLR 2023
from the bottom of hierarchy, which consistently shows good performance all datasets. We discuss on the impact of the picked level in Appx. A.1.
3.4 LABEL ASSIGNMENT WITH AN UNKNOWN CLASS NUMBER
Once good representation is learned, we could then determine the class la- bel assignment for all unlabelled in- stances. When the class number is
Algorithm 2 One-by-one merging
Preparation:
Get initial partitions S (TT)p= by SNC and cluster number range [Ne,, No). Note that the merging from N. to N₂ and N, Ne.
known, we can obtain the label assign- ment by adopting semi-supervised means like (Han et al., 2019; Vaze et al., 2022b) or directly using our proposed SNC. Since SNC is hier- archical clustering algorithm and the cluster number in each hierarchy level is determined automatically by the in- trinsic correlations of the instances, might not produce level of partition with the exact same cluster number as the known class number. We therefore introduce a simple one-by-one merging strategy to SNC allowing to reach a given class number. Specifically, we first identify level of partition that has the closest cluster number larger than the given class number, and then merge the clusters one by one until the given class number is reached. At each merging step, we simply merge the two closest clusters. The merging process is summarized in Algo. 2. The label assignment can then be retrieved from the final partition.
Partition initialization:
Find I E S satisfying |1 > N, and |nd]rt No-
Merging:
6: while [I > N₂ do
(k.j) + arg min,y (u(e)) nle)) (((e)))((()))))))))))))))))) ct,e) E I²)
Merge cf and cfe forming a new partition I
Update current partition 1 <- r".
10:
end while
11: Output:
12: Obtain specific partition I't of N, clusters. Le.. [T = No.
When the class number is unknown, exiting methods based on semi-supervised k-means need to first estimate the unknown cluster number before they can produce the label assignment. To estimate the unknown cluster number, (Han et al., 2019) proposed to run semi-supervised k-means on all the data while dropping part of the labels for clustering performance validation. Though effective, this algorithm is computational expensive as needs to run semi-supervised k-means on all possible cluster numbers. (Vaze et al., 2022b) proposed an improved method with Brent's 's optimization (Brent, 1971), which increases the efficiency. With the estimated cluster number, semi-supervised k-means is run again on all labelled and unlabelled instances to produce the final label assignment.
In contrast, SNC can directly produce hierarchical cluster assignments without a known class number. For practical use, one can pick any level of assignments based on the required granularity. To obtain more reliable class number estimation, we propose to use a joint reference score considering both labelled and unlabelled data. In particular, we further split the labelled data Dr into two parts D/ and D"- We then run SNC on the full dataset 'D treating D'2 as labelled and Drr U D" as unlabelled. We then jointly measure the unsupervised intrinsic clustering index (such as silhouette score (Rousseeuw, 1987)) on Dr and the extrinsic clustering accuracy on DE We obtain joint reference score 8, by simply multiplying them after min-max scaling to achieve the best overall measurement on the labelled and unlabelled subsets. We then choose the level in SNC hierarchy with the maximum se.
The cluster number in the chosen level can be regarded as the estimated class number. To achieve more accurate class number estimation, we further leverage the one-by-one merging strategy. Namely, with the chosen level, we apply the one-by-one merging strategy starting from the level below the chosen one the level above the chosen one. We then identify the merge that gives the best reference score 8, and consider its cluster number as our estimated class number.
Our proposed SNC with the one-by-one merging strategy can carry class number estimation with one single run of hierarchical clustering, which is significantly more efficient than the methods based on semi-supervised k-means (Han al., 2019; Vaze al., 2022a).
EXPERIMENTS
4.1 EXPERIMENTAL SETUP
Data and evaluation metric. We evaluate our mothod on three generic image classification datasets, namely CIFAR-10 (Krizhevsky et al., 2009), CIFAR-100 (Krizhevsky al., 2009), and ImageNet- 100 (Deng et al., 2009). ImageNet- refers to randomly subsampling 100 classes from the ImageNet dataset. We further evaluate on two more challenging fine-grained image classification datasets,

---

Under review as a conference paper at ICLR 2023
namely Semantic Shift Benchmark (Vaze et al., 2022a) (SSB includes CUB-200 (Wah et al., 2011) and Stanford Cars (Krause et al., 2013)) and et al., 2022b) to split the original training set of each dataset into labelled and unlabelled parts. We sample a subset of half the classes as seen categories. 50% of instances of each labelled class are drawn to form the labelled set, and all the rest data constitute the unlabeled set. The model takes all images as input and predicts a label assignment for each unlabelled instance. For evaluation, we measure the clustering accuracy by comparing the predicted label assignment with the ground truth, following the protocol of ( (Vaze et al., 2022b).
Herbarium19 (Tan et al., 2019). We follow (Vaze
Implementation details. We follow (Vaze et al., 2022b) to use the ViT-B-16 initialized with pretrained DINO (Caron et al., 2021) as our backbone. The output [CLS] token is used as the feature representation. Following the standard practice, we project the representations with a non-linear projection head and use the projected embeddings for contrastive learning. We set the dimension of projected embeddings to 65,536 following (Caron et al., 2021). At training time, we feed two views with random augmentations to the model. We only fine-tune the last block of the vision transformer with an initial learning rate of 0.01 and the head is trained with an initial learning rate of 0. All methods are trained for 200 epochs with cosine annealing schedule. For our method, the temperatures of two supervised contrastive losses T; and Ta are set to 0.07 and 0. respectively. For class number estimation, we set [P&): 8:2. Our experiments are conducted on RTX 3090 GPUs.
4.2 COMPARISON WITH THE STATE-OF-TIEE-ARY
We compare our CiP with four strong GCD baselines: RankStats+ and UNO+, which are adapted from RtnkStats (Han et al., 2021) and UNO (Fini al., 2021) that are originally developed for NCD, the state-of-the-we addresses GCD from semi-supervised learning perspective. As ORCA uses different backbone model and data splits, for fair comparison, we retrain ORCA with ViT model using the official code on the same splits here.
GCD method of (Vaze et al., 2022b), and ORCA (Cao et al.. 2022) which
In Tab. 1, we compare CiP with others on the generic image recognition datasets. CiP consistently outperforms all others by significant margin. For example, CiP outperforms the state-of-the-an GCD method of (Vaze et al., 2022b) by 6.2% on CIFAR-10, 10.7% on CIFAR-100, and 6.4% on ImageNet- 100 for 'All' classes, and by 9.5% on CIFAR- 10, 22.7% on CIFAR-IOR and 12.0% on ImageNet- 100 for 'Unscen' classes. This demonstrates cross-instance positive relations obtained by SNC are effective to learn better representations for unlabelled data. Due to the fact that a linear classifier is trained on 'Seen' classes, UNO+ shows strong performance on 'Seen' classes, but its performance on 'Unseen' ones is significantly worse. In contrast, CiP achieves comparably good performance on both 'Seen' and 'Unseen' classes, without biasing to the labelled data.
Table 1: Results on generic image recognition datasets.
CIFAR-10
CIFAR-100
ImageNet-100
Classes
All
Soea
Unseen
All
Seea
Unsoon
All
Seen
Unsoon
RtakStutst (Han al., 2021)
46.8
19.2
60.5
77.6
19.3
24.8
UNO+ (Fini et 2021)
68.6
98.3
53.8
69.5
80.6
47.2
70.3
95.0
57.9
ORCA (Cao al., 2022)
97.3
97.3
97.4
70.2
58.7
38.2
23.4
Vaze et al. (Vaze et al., 20226)
91.5
97.9
88.2
70.8
77.6
57.0
74.1
89.8
66.3
Ours (CIP)
97.7.0.1
97.5200
97.7.002
81.5114
82.4112
79.7
80.5114
84.911.
78.3124
In Tab. 2, we further compare our method with others on ine-grained image recognition datasets, in which the difference between different classes are subtle, making it more challenging for GCD. Again, CiP consistently outperforms all other methods for 'All' and "Unseen' classes. On CUB-200 and SCars, CiP achieves 5,8% and 8.0% improvement over the state-of-the-art for 'All' classes. For the challenging Herbarium19 19 dataset, which contains many more classes than other datasets and has the extra challenge of loig-tailed distribution, CiP still achieves an improvement of 1.4% and 5.6% for 'All' and 'Unseen' classes. Both RankStats+ and UNO+ show a strong bias to the 'Seen' classes.
In Fig. 2, we visualize the t-SNE projection on features generated by DINO (Caron et al., 2021), GCD method of (Vaze et al., 2022b), and our method CiP, performed on CIFAR-10. Both (Vaze et al., 2022b) and our features are more discriminative than DINO features. The method of (Vaze et al., 2022b) captures better representations with more separable clusters, but some seen categories are confounded with unseen categories, e.g., cat with dog and automobile with truck, while CiP features show better cluster boundaries for seen and unseen categories, further validating the quality of our learned representation.
7

---

Under review as a conference paper at ICLR 2023
Table 2: Results on fine-grained image recognition datasets.
CUB-200
SCars
Herburium 19
Classes
Seen
Unseen
All
Seen
Unseen
All
Seen
([nsen
RankStars+ (Han al. 2021)
33.3
51.6
24.2
28.3
61.8
12.1
27.9
55.8
12.8
UNO+ (Fini et al, 2021)
35.1
49.0
28.1 1
35.5
70.5
18.6
28.3
53.7
14.7
ORCA (Cao al., 2022)
35.0
35.6
34,8
32.6
47.0
25.7
24.6
26.5
23.7
Vaze et ol. (Vaze et al,, 2022b)
51.3
56.6
48.7
39.0
57.6
29.9
35.4
51.0
27.0
Ours (CIP)
57.1
18.7
55.6=099
47.0=23
61.5+35
40.1
36.8:006
45.4+19
32,6::0.
DINO
Vaze et al.
CiP
sppree
Eog
Day"
Ckip
bad-
Figure 2: Visualization on CIFAR-10. We conduct t-SNE projection on features extracted by raw DINO, GCD method of (Vaze et al., 2022b) and our CiP. We randomly sample 1000 images of each class from CIFAR-10 to visualize. Unseen categories are marked with *
4.3 ESTIMATING THE UNKNOWN CLASS NUMBER
In Tab. 3, we report our estimated class numbers on both generic and fine-grained datasets using the joint reference score 8, as described in Sec. 3.4. Overall, CiP achieves comparable results with the method of (Vaze et al., 2022b) costing slightly more memory, but it far more efficient (40-150 times faster) and also does not require a list of predefined possible numbers. Even for the most difficult Herbarium19 19 dataset, CiP only takes few minutes to finish, while it takes more than an hour for a single run of k-means due to large class number, let alone multiple runs from a predefined list of possible class numbers.
Table 3: Estimation of class number in unlabelled data.
Method
CIFAR-10
CIFAR-100
ImnggeNet-100
CUB-200
SCars
Herbarium19
Ground truth
10
100
100
200
196
683
Estimate (error
Vaze al. (Vaze et al., 2022b)
(10%)
100 (0%)
109 (9%
231 (16%)
230 (17%)
520 (24%)
Our (CIP)
12 (20%)
103 (3%)
100 (0%)
155 (23%)
182 (7%)
490 (28%)
Vaze al. (Vaze et al., 2022b)
15394s
27755s
64524s
7197s
8863s
62901s
Runtime
Our (CIP)
102s
528s
444s
126s
168s
1654s
Memory
Vaze ol. (Vaze et al., 2022b)
2206MB
2207MB
3760MB
1354MB
1394MB
1902MB
Ours (CIP)
2535MD
2932MB
5848MB
1392MB
1451MB
2205MB
4.4 ABLATION STUDY
Approaches to generate positive relations. In Tab. 4, we compare our SNC with multiple different approaches to generate positive relations for joint contrastive learning, including directly using nearest neighbor (Zhong et al., 2021) in every mini-batch and conducting various clustering algorithms to obtain pseudo labels, e.g., FINCH (Sarfraz et al., 2019), k-means (MacQueen et al., 1967), and semi-supervised k-means (Han et al., 2019; Vaze et al., 2022b). Non-hierarchical clustering methods (k-means and semi-supervised k--mans) require given cluster number. For k-means, ground-truth class number. For semi-supervised k-means, we use both the ground truth and the overclustering number (twice the ground truth). We evaluate performance using both proposed SNC and semi-supervised k-means for comparison. It is clear that SNC reaches higher accuracy than semi-supervised k-means at test time. For generating pseudo positive relations, our method achieves best performance among all approaches. FINCH performs great on CIFAR-100 100 but degrades on CUB-200. We hypothesize that because FINCH is purely unsupervised without leveraging labelled data, it fails to generate reliable pseudo labels of more semantically similar instances on fine-grained CUB-200. Overclustering semi-supervised k-means achieves comparable performance on CUB-200 but performs bad on CIFAR-100. This might be caused by intrinsic poorer performance of semi- supervised k-means compared to proposed SNC, which results in worse pseudo labels. We further report the mean purity curve of pseudo labels generated by all clustering methods throughout training process in Fig. 3. We can observe that pseudo labels produced by SNC remain the highest purity on both datasets throughout the entire training process.
the
8

---

Under review as a conference paper at ICLR 2023
Table 4: Results using different approaches generate positive relations. Semi-k-means" denotes using semi-supervised k-means with an overclustering class number (2 x ground truth). The results evaluated with SNC are reported of normal size (left), and those evaluated with semi-supervised k-means are reported of smaller size (right).
CIFAR-100
CUB-200
Classes
All
Seen
Unseen
All
Seen
Unseen
w/ neighbor
80.4
82.9
75.5
51.9
56.7
48.2
49.5
w/ FINCH
81.4
81.7
80.7
51.4
47.9
51.8
45.1
51.3
49.3
w/ k-means
76.7
77.1
75.7 75.8
52.8
48.6
53.1
45.
52.7
50.2
w/ semi- remi-k-means
78.1 73.8
81.5 73.3
71.3
74.8
54.5
48.7
54.1
43.9
54.7
51.2
w/ semi- meniik-meent k-means"
76.8
71.9
76.9
71.8
76.4
72.1
56.6
48.1
57.1
50.2
56.4 47.1
w/ SNC. (ours)
81.5
82.4
79.7 79.3
57.1
50.2
58.7
55.6
51.0
Purity curve on CIFAR-100
Purity curve on CUB
0.90
0.65
0.85
0.60
0.80
0.75
0.65
w/ FINCH
w/ FINCH
k-meians
w/ k-means
0.60
somi-k-means semi Ic means"
W/ somi-k-moanz
W/ semi k means*
0.55
25
50
75
100
125
150
175
200
25
50
75
100 Epochs
125
150
175 200
Epochs
Figure 3: Purity curve.
Effectiveness of cross-instance positive relations. In this paper, we use SNC generate pair-wise relations of unlabelled data, as well as relations between unlabelled and labelled data in supervised contrastive learning. Tab. 5, we evaluate different settings to verify the effectiveness of both of these two relation types. We report evaluation results of SNC and semi- comi-suprviised k-means, showing higher accuracy achieved by SNC. Row (0) represents performance of the state-of-the-art GCD method of (Vaze et al., 2022b) without using any pseudo relations. Rows (1)-(3) show the effect of using different clustering methods introduce relations unlabelled and unlabelled pairs (u-u). methods show improvements over (Vaze et al., 2022b). Among all relation generating methods, SNC brings the largest improvement, outperforming k-means and FINCH. Row (4) shows only adding pair-wise relations of labelled and unlabelled data (u-f) is not sufficient to boost baseline performance. Row (5) is our full method, which achieves the best performance. From (3)-(5), we clearly find fully using relations u-u and u-L generated from SNC benefits our method to the greatest extent, which also substantially improves performance on unseen categories.
Table Results using different relations. u-u denotes pair-wise relations between unlabelled and unlabelled data, and u-L denotes pair-wise relations between unlabelled and labelled data. Rows (3)-(4) mean applying SNC on all data but only using u-u or u-l for pseudo positive relations.
CIFAR- 100
CUB-200
k-means
FINCH
SNC
u-f
All
Seen
Unseen
All
Seen
Unseen
(0)
X
X
73.6
80.4
60.0 $7.0
53.1
513
57.6
56.6
50.8
(I)
/
x
X
/
X
77.2 73.1
78.3 74.4
74.9 70.7
56.0
510
53.8
428
57.1
55.2
(2)
x
/
80.3 782
79.5 76.9
81.7 80.9
51.3
461
45.7
40.0
54.0
49.1
X
80.5
80.6
80.3
56.6
$7.2
56.3
(4)
X
x
V
72.9
82.0
54.8
51.6
$1.0
45.
52.9
444
50.1
(5)
X
X
/
81.5
76.5
82.4 75.1
79.7
79.3
S7.1
502
58.7
48.8
55.6
51.9
CONCLUSION
We have presented framework CiP for the challenging problem of GCD. Our framework leverages the cross-instance positive relations that are obtained with SNC, an efficient parameter-free hierar- chical clustering algorithm develop for the GCD setting. With the positive relations obtained by SNC, we can learn better representation for GCD, and the label assignment on the unlabelled data can be obtained from single run of SNC, which is far more efficient than the semi-supervised k-mmans used in the state-op of-the-at method. We also show that SNC can be used to estimate the unknown class number in the unlabelled data with higher efficiency.

---

Under review as a conference paper at ICLR 2023
ETHICS STATEMENT
The potential negative impacts lie two aspects. On the one hand, although the performance achieves the oftte-,,, it still lags behind fully supervised models, making it risky to apply to scenarios with strict safety and accuracy requirements, egg., autonomous driving and medical image classification. On the other hand, due to unseen labels, manually checking the results is necessary in real applications, drawing attention to sensitive contexts (e.g., private data) and inappropriate contents (e.g., violent images).
REFERENCES
Abhijit Bendale and Terrance E Boult. Towards open set deep networks. In CVPR, 2016.
Richard P. Brent. An algorithm with guaranteed convergence for finding zero of a function. The Computer Journal, 1971.
Kaidi Cao, Maria Brbić, and Jure Leskovec. Open-world semi-supervised learning. In ICLR, 2022.
Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties in self-suuprvised vision transformers. In ICCV, 2021.
Olivier Chapelle, Bernhard Scholkopf, and Alexander Zien. Semi-supervised learning. MIT Press, 2006.
Guangyao Chen, Limeng Qiao, Yemin Shi, Peixi Peng, Jia Li, Tiejun Huang, Shiliang Pu, and Yonghong Tian. Learning open set network with discriminative reciprocal points. In ECCV, 2020a.
Guangyao Chen, Peixi Peng, Xiangqian Wang, and Yonghong Tian. Adversarial reciprocal points learning for open set recognition. IEEE TPAMI, 2021.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In ICMI, 2020b.
Haoang Chi, Feng Liu. Wenjing Yang, Long Lan, Tongliang Liu, Bo Han, Gang Niu, Mingyuan Zhou, and Masashi Sugiyama. Meta discovery: Learning to discover novel classes given very limited data. In ICLR, 2022.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In CVPR, 2009.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11929 2020.
Enrico Fini, Enver Sangineto, Stéphane Lathuilière, Zhun Zhong, Moin Nabi, and Elisa Ricci. unified objective for novel class discovery. In ICCV, 2021.
Kai Han, Andrea Vedaldi, and Andrew Zisserman. Learning discover novel visual categories via deep transfer clustering. In ICCV, 2019.
Kai Han, Sylvestre-Alvis Rebuffi, Sebastien Ehrhardt, Andrea Vedaldi, and Andrew Zisserman. Automatically discovering and learning new visual categories with ranking statistics. In ICLR. 2020.
Kai Han, Sylvestre-Alvise Rebuffi. Sebastien Ehrhardt, Andrea Vedaldi, and Andrew Zisserman. Autonovel: Automatically discovering and learning novel visual categories. IEEE TPAMI. 2021.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In CVPR, 2020.
Yen-Char Yen-Chang Hsu, Zhaoyang Lv, and Zsolt Kira. Learning to cluster in order to transfer across domains and tasks. In ICLR, 201 la.
10

---

Under review as a conference paper at ICLR 2023
Yen-Chang Hsu, Zhaoyang Lv, Joel Schlosser, Phillip Odom, and Zsolt Kira. Multi-class classification without multi-class labels. In JCLR, 2018b.
Xuhui Jia, Kai Han, Yukun Zhu, and Bradley Green. Joint representation learning and novel category discovery on single-and multi-modal data. In ICCV, 2021.
Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan. Supervised contrastive learning. In NeurIPS, 2020.
Jonathan Krause, Michael Stark, Jía Deng, and Li Fei-Fei. 3d object representations for fine-grained categorization. In 4th International IEEE Workshop on 3D Representation and Recognition (3dRR-13), 2013. 2013.
Alex Krizhevsky, Πya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. In NeurlPS, 2012.
Alex Krizhevsky et al. Learning multiple layers of features from tiny images. Technical report, 2009.
Samuli Laine and Timo Aila. Temporal ensembling for sunni-sueeeieed learning. In ICLR, 2017.
James MacQueen et al. Some methods for classification and analysis of multivariate observations. In Proceedings of the fifth Berkeley symposium on mathematical statisties and probability, 1967.
Peter J. Rousseeuw. Silhouettes: A graphical aid to the interpretation and validation of cluster analysis. Journal of Computational and Applied Mathematics, 1987.
M. Saquib Sarfraz, Vivek Sharma, and Rainer Stiefelhagen. Efficient parameter-free clustering using first neighbor relations. In CVPR, 2019.
Walter J Scheirer, Anderson de Rezende Rocha, Archana Sapkota, and Terrance E Boult. Toward open set recognition. IEEE TPAMI, 2012.
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In NeurIPS, 2017.
Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A Raffel, Ekin Do- gus Cubuk, Alexey Kurakin, and Chun-Liang Li. Fixmatch: Simplifying remi-supervised learning with consistency and confidence. In NeurIPS, 2020.
Kiat Chuan Tan, Yulong Liu, Barbara A. Ambrose, Melissa Tulig, and Serge J. Belongie. The herbarium challenge 2019 dataset. arXiv preprint arXiv: (00iv/9996.00555 05372, 2019.
Antti Tarvainen and Harri Valpola. Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results. In NewrIPS, 2017.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In NeurlPS, 2017.
Sagar Vaze, Kai Han, Andrea Vedaldi, and Andrew Zisserman. Open-set recognition: A good closed-set classifier is all you need. ICLR, 2022a.
Sagar Vaze, Kai Han, Andrea Vedaldi, and Andrew Zisserman. Generalized category discovery. In CVPR, 2022b.
Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge Belongie. The caltech-uesd birds-200-2011 dataset. Technical report, 2011.
Jay Yagnik, Dennis W. Strelow, David A. Ross, and Ruei-Sung Lin. The power of comparative reasoning. ICCV, 2011.
Bowen Zhang, Yidong Wang, Wenxin Hou, Hao Wu, Jindong Wang, Manabu Okumura, and Takahiro Shinozaki. Flexmatch: Boosting cemi-supervised learning with curriculum pseudo labeling. In NeurlPS, 2021.
Bingchen Zhao and Kai Han. Novel visual category discovery with dual ranking statistics and mutual knowledge distillation. In NeurIPS, 2021.
Zhun Zhong, Enrico Fini, Subhankar Roy, Zhiming Luo, Elisa Ricci, and Nicu Sebe. Neighborhood contrastive learning for novel class discovery. In CVPR, 2021.
11

---

Under review as a conference paper at ICLR 2023
A
APPENDIX
CONTENTS
A.I More analysis on SNC
13
A.2 unified loss
14
A.3 Class number estimation
15
A.4 Time efficiency
15
A.5 Attention map visualization
16
A.6 Data splits
16
A.7 Special cases of unlabelled data
16
A.8 Limitations
18
A.9 License for experimental datasets
18
12

---

Under review as a conference paper at ICLR 2023
cluster instances with SNs?
Level (top)
"1 =
Level 3
À 2=
SN of labelled instances
SN unlabelled instances
f1 =
Level 2
How to compute chain length?
1=
=
ny 10 1 =
Level (bottom)
Unlabelled data points
Labelled data points * * * Cluster centroids
Figure 4: A more detailed illustration of SNC. SNC iteratively clusters instances from the bottom to the top, producing multiple levels of different partitions. At each level, the auto-adaptive chain length A is dynamically determined by the number of labelled 'instances' ny each class. The connected components are extracted with selective neighbors (SNs), forming the clusters at each level.
A.1 MORE ANALYSIS ON SNC
We present a more detailed illustration of our proposed SNC in Fig. 4. SNC is inspired by the idea from FINCH, but they are significantly different in two key aspects: (1) FINCH treats all instances the same and simply uses nearest neighbors to construct graphs; SNC uses a novel selective neighbor strategy tailored for the GCD setting to construct graphs, treating labelled and unlabelled instances differently. (2) SNC is able to cluster mixed set of labelled and unlabelled data fully exploiting label supervision, but FINCH not.
Effectivenss of SNC different learned features. In Tab. 6, evaluate SNC! features extracted from DINO (Caron et al., 2021), GCD method (Vaze al., 2022b), and our method CiP. We also compare SNC with semi-supervised k-means (Han et al., 2019; Vaze et al., 2022b). We can observe that SNC surpasses semi-supervised k-means with a significant margin on all features, except those extracted by (Vaze al., 2022b) on ImageNet-100. Moreover, semi-supervised k-means with our features performs better than with other features. Overall, SNC with our learned features gives the best performance.
Table 6: Effectivenss of SNC on different learned features.
Clustering
Features
CIFAR 100
ImageNet- 100
CUB-200
SCars
Unseen
DINO (Caron et al., 2021)
60.4
63.1
$4.9
72.8
70.6
73.8
36.7
37.9
36.0
12.3
13.7
11.6
Semi-Asmeans
Vare et al (Naze al, 20222)
74.5
81.9
60.0
69.2
66.6
70.5
53.5
59.9
50.3
40.8
67.6
27.8
(ouns)
73.8
DINO (Caron all, 2021)
65.5
69.0
58.3
76.8
81.1
74.6
36.7
35.0
37.5
12.4
15.8
10.7
SNC (ours)
Vire of (Vaze al, 2022b)
77.8
87.4
58.6
61.4
76.7
53.8
55.9
61.6
$3.0
41.3
62.9
30.8
82.4
Different choices of chain lengths X. The choice of chain lengths should be positively correlated to (but smaller than) the labelled instance number, while the number should not be too small. The
When representing clustering method here, SNC denotes selective neighbor clustering with one-hy-one merging.
13

---

Under review as a conference paper at ICLR 2023
square root used in our paper is the simplest formulation we think of. In Tab. 7, we experiment other formulations which satisfies the above relationship, e.g., À = [ and À = / and our formulation performs the best. We also compare our dynamic À with possible alternative of fixed A. For the fixed chain length, we conduct multiple experiments with different length values to find the best length giving the highest accuracy for each dataset. We observe that the best chain length varies from dataset to dataset, and there is no single fixed À that gives the best performance for all datasets. In contrast, our dynamic consistently outperforms the fixed one, and it can automatically adjust the chain length for different datasets and different levels, without requiring any tuning nor validation like the fixed one.
Table 7: Comparison different formulations of chain length A. The best fixed length values are 8 for CIFAR-100 and 3 for CUB-200.
CIFAR-100
CUB-200
Classes
All
Seen
Unseen
All
Seen
Unseen
Fixed
80.2
79.7
81.3
54.3
58.8
52.1
[ee/2]
81.4
84.5
75.2
45.5
45.5
45.5
Vne
72.5
77.1
63.2
42.4
45.0
41.1
(ours)
81.5
82.4
79.7
57.1
58.7
55.6
Impacts of different levels for positive relation generation. A proper level for positive relation generation should overcluster the labelled data to some extent, such that reliable positive relations can be generated. Level is not valid choice because no positive relations can be generated if each instance is treated as cluster. In Tab. 8, we present the performance using levels 2, 3, and 4 to generate pseudo labels and also compare with the previous state-of state-of-the-art baseline by (Vaze et al., 2022b). We empirically find that the overclustering levels 3 and 4 are similarly good, while level 2 is worse because less positive relations are explored in each mini-batch, Even using level 2, our method still performs on par with (Vaze et al., 2022b).
Table 8: Comparison of different levels. Compare level 2, 3, and baseline (Vaze et al., 2022b).
CIFAR-IO0
CUB-200
Classes
Seen
Unseen
Seen
Unseen
Baseline (Vaze et al., 2022b)
70.8
77.6
57.0
51.3
56.6
48.7
CiP w/ level
72.4
79.6
58.0
50.9
55.8
48.5
CiP w/ level 3 (ours)
81.5
82.4
79.7
57.1
58.7
55.6
CiP w/ level 4
81.6
81.9
80.8
52.9
53.1
52.8
A.2 A UNIFIED LOSS
In this paper, to leverage pseudo labels produced by SNC, we jointly train our model with two supervised contrastive losses, one using true positive relations of labelled data and the other using pseudo positive relations of all data. Indeed, it is possible to train the model with unified loss by replacing the pseudo relations in the second term of our loss, and remove the first term. Formally, let (i) be the set of positive relations for instance The unified loss L be written
log exp(x: - 2g/T)
C. = RB
(6)
Lne exp( Zi Zn/TT T)
(ER
where
if Iz ( nIx) (Pt(i)
(1)
(7)
if Iu
Ic and Tze denote the instance indices of the labelled and unlabelled set respectively. In Tab. 9, we compare our two-term loss formulation with this unified loss formulation. It turns out that our two-term loss appears to be more effective. We hypothesize the performance degradation of Eq. (6) is caused by unbalanced granularity of labelled data and unlabelled data, due to mixture of overelustering pseudo labels and non-overclustering ground-truth labels.
14

---

Under review as a conference paper at ICLR 2023
Table 9: Results using different loss formulations.
CTFAR-100
CUB-200
Classes
All
Seen
Unseen
All
Scen
Unseen
Eq. (6)
79.3
80.3
77.3
53,9
53.5
54.0
Ours (CiP)
81.5
82.4
79.7
57.1
58.7
55.6
CIFAR
ORAR 100
Imagehict
Labelled accurety
Labelled sccuracy
Sihoustle
01-
04-
score
Score
Score
Store
02-
Labelled Silouette
0.2
Class number
Clsss number
Class number
3.-
Labelled
Reforence score
Scare
Labelled
Labelles Reforence score
Class number
Closs number
Class number
Figure 5: Curves throughout class number estimation. We report curves of accuracy on the labelled subset D2. silhouette score on the unlabelled data Die and our reference score on D U Dru- Note that the r-axis should be read from right to left, as the merging start from the lower level to the upper level.
A.3 CLASS NUMBER ESTIMATION
In Fig. 5, we show how labelled accuracy, silhouette score and reference score change throughout the whole procedure of class number estimation with one-by-one merging. The accuracy on the labelled instances or the silhouette score alone does not well fit the actual cluster number. By jointly considering both, we can see the actual class number aligns well with our suggested reference score.
A.4 TIME EFFICIENCY
Here, evaluate the time efficiency of CiP, including both category discovery and class number estimation.
Category discovery efficiency. The latency for the category discovery process mainly consist of two parts: feature extraction and label assignment. In Tab. 10, we present the feature extraction time. All methods consume roughly the same amount of time for feature extraction per image. RankStats+ (Han et al., 2021), UNO+ (Fini et al., 2021), 1), and ORCA (Cao et al., 2022) assign labels with a linear classifier, thanks to the assumption of known category number. Hence, the label assignment process is simply done by a fast feed-forward pass of a linear classifier, costing omitable time (< 0.0005 second per image), though their performance lags. Our CiP and (Vaze et al., 2022b) contain the transfer clustering process for label assignment, for which CiP is 6-30 times faster than semi-supervised k-means used in (Vaze al., 2022b) (see Tab. 11).
Table 11: Time cost in clustering.
CIFAR-10
CIFAR-100
ImageNet- 100
CUB-200
SCars
Herbarium
Semi-A-means
346s
688s
3863s
256s
356s
6053s
Ours (SNC w/ one-by-one merging)
58s
111s
118s
36s
SUs
917s
15

---

Under review as a conference paper at ICLR 2023
Table 10: Time cost in feature extraction per image.
Time
RankStats+ (Han al., 2021)
0.015s=00001
UNO+ (Fini et al., 2021)
0.0175=:0001
ORCA (Cao et al., 2022)
0.015:::0.001
Vaze et al. (Vaze et al., 2022b)
0.014s=0.000
Ours (CiP)
0.014s=00.00
Estimating class number. Compared repeatedly running k-means with different class numbers as in (Vaze et al., 2022b), CiP only requires single run to obtain the estimated class number, thus significantly increasing efficiency. Tab. 12, CiP is 40-150 times faster than (Vaze et al., 2022b), which utilizes k-means with the optimization of Brent's ' algorithm (Brent, 1971).
Table 12: Time consumed in estimating class number.
CIFAR-10
CIFAR-100
ImageNet-100
CUB-200
SCars
Herharium19
Vaze et (Vaze et al., 2022b)
15394s
27755s 528s
64524s
7197s
8863s
63901s
Ours (CiP)
102s
444s
126s
168s
1654s
A.5 ATTENTION MAP VISUALIZATION
ViT (Dosovitskiy et al., 2020) has multi-head attention design, with each head focusing on different context of the image. For the final block of VIT, the input X E (R(#++))D corresponding to feature of HW patches and [CLS] token, is fed into multi-heads, which can be expressed as
MultiHead((X) [head], headz, ...,, head,,
(8)
where
Q,K7 dd
headz = softmart
V
(9)
Q; XW J
(10)
K; = XWK
(11)
V XW)
(12)
where de is the dimension of queries and keys. In our model, patch size is 16 x 16 pixels and HW 14 x 14 196. The number of heads h is 12. Referring (Vaswani et al., 2017),
consider attention map of head A; sof tmaa the similarity of one feature every other feature captured in head j. The first row of A, shows how head] j attends [CLS] token to every spatial patch of the input image. In Fig. 6, we visualize some of the interpretable attention heads to show semantic regions that ViT attends to. We can observe that model CiP, well as DINO (Caron et al., 2021) and (Vaze et al., 2022b), semantic object regions. For instance, CiP attends three heads respectively to 'license plate', 'light' and 'wheels' for Stanford Cars (head fails in row 1), and to 'body', 'head' and 'neck" for CUB-200.
K,K² d
E (H
Aj describes
attend specific
A.6 DATA SPLITS
In Tab. 13, we show the details on data splits of CIFAR-10 (Krizhevsky et al., 2009), CIFAR- 100 (Krizhevsky et al., 2009), ImageNet-100 (Deng et al., 2009), CUB-200 (Wah et al., 2011), Stanford Cars (Krause et al., 2013) and Herbarium19 19 (Tan al., 2019) in our experiments.
A.7 SPECIAL CASES OF UNLABELLED DATA
In the real world, we may meet the scenarios where unlabelled data are all from seen or unseen classes. We investigate into such scenarios and conduct experiments to validate effectiveness of our method. Our experiment are under two settings: (1) applying our pretrained models the main paper to seen-only and unseen-only unlabelled data; (2) retraining the models with seen-only and unscen-only unlabelled data. In Tab. 14, we can observe that our model maintains strong performance in all cases.
16

---

Under review as a conference paper at ICLR 2023
VIT w/ DINO
ViT w/ Vaze et al.
ViT w/ CiP Head2
Head
Head2
Head3
Headl
Head2
Head3
Head
Head3
Stanford Cars
CUB-200
Figure 6: Attention visualizations. We report visualization results DINO (Caron et al., 2021) (left), (Vaze et al., 2022b) (middle) and CiP (right) on Stanford Cars (top) and CUB-200 (bottom). For each dataset, we show two rows of 'Seen' categories (solid green box) and two rows of 'Unseen' categories (dashed red box). Zoom in to see attention details.
Table 13: Data splits of all datasets. We present the number of classes in the labelled and unlabelled set (Diel. (Dx)), and the number of images (iDz), (Dul).
CIFAR-10
CIFAR-100
ImageNet 100
CUB-200
SCars
Herbarium
Dic Diu
50
100
341
100
200
683
Dell
12.5k
20k
32.5k
1.5k
2.0k
8.5k
Dai
37.5k
30k
97.5k
4.5k
6.1k
25.7k
Table 14: Performance seen-only and unseen-only unlabelled data. "original setting" denotes the performance of CiP dealing with GCD; "direct testing" denotes the performance of CiP dealing with seen-only unseen-only unlabelled data using pretrained GCD model; "retraining" denotes the performance of retrained CiP dealing with seen-only or unseen-only unlabelled data.
CIFAR-10
CIFAR-100
ImageNet-100
CUB-200
SCars
Herbarium19
original setting
97.5
82.4
84,9
58.7
61.5
45
Seen
direct testing
98.5
83.3
79.1
72.0
55.4
retraining
87.0
87.3
81.9
75.2
66.3
original setting
97.7
79.7
78.3
55.6
40.1
32.6
Unseen
direct testing
97.6
82.7
74.3
56.5
39.3
37.9
retraining
98.4
78.9
79.3
60.4
42.5
41.3
17

---

Under review as a conference paper at ICLR 2023
A.8 LIMITATIONS
We note limitations of our method. In our current experiments, we consider images from the same curated dataset. However, in practice, might want transfer concepts from one dataset to another, which may have different data distribution, introducing more challenges. For example, the unlabelled data could follow the long-tailed distribution. Another limitation is that currently, the model on both labelled and unlabelled data jointly. However, real world, there are often cases in which we do not have access any labelled data from the seen classes when facing the unlabelled data. We consider these as our future research directions.
need train
A.9 LICENSE FOR EXPERIMENTAL DATASETS
All datasets used in this paper permitted for research CIFAR-IO and CIFAR-100 (Krizhevsky et al., 2009) are released under MIT License, allowing for research propose. ImageNet- 100 the subset of ImageNet (Deng et al., 2009), which allows non-commercial research use. Similarly, CUB-200 (Wah et al., 201 I), Stanford Cars (Krause et al., 2013) and Herbarium19 (Tan et al., 2019) also exclusive for com-mmmeraaal research purpose.
18


Reviews:
[{"review_id": "c20afJacDfT", "reviewer": "Reviewer_Kvso", "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 work proposes cross-instance positive relations that introduce a selective neighbor clustering module to help generate pseudo labels for contrastive learning. It can promote using both the labeled and unlabelled data to help more representative representation. It presents experiments on several benchmarks to demonstrate its performance.\n", "summary_of_the_review": "I think the overall idea is OK and the experiments are quite convincing. The contribution should be better clarified.\n", "strength_and_weaknesses": "Strength\n1. I idea using both labeled and unlabelled data is intuitive.\n2. The performance improvement is quite impressive, e.g., up to 10% accuracy improvement in some settings.\n3. The paper is well-written and easy to follow.\n\nWeaknesses\n1. It seems the key contribution is the SNC which can help generate pseudo labels. The authors claim that SNC is inspired by and similar to FINCH. However, the difference with FINCH is not well clarified. \n2. The authors use SNC to generate pseudo labels. I wonder how to ensure the accuracy of generated labels. It may hurt model training if generating many wrong labels. ", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Z0BigVnTk4", "reviewer": "Reviewer_T62F", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 considers the problem of generalized category discovery (GCD). To solve this problem, the authors propose a positive-pair mining approach for facilitating the contrastive learning, which encourages the network learn more discriminative representation. Extensive experiments on several GCD datasets show the benefit of the proposed method. ", "summary_of_the_review": "This paper studies a new task and proposes an effective method for this task, which achieves new SOTA performance. However, the novelty of the proposed framework is somewhat limited. In addition, compared to the original FINCH method, the improvement of the proposed method is sometime limited.", "strength_and_weaknesses": "Strength \n\n+ This paper studies a new problem and practical problem in the community.\n\n+ This paper is well written and easy to follow.\n\n+ An effective approach is proposed for GCD, which largely improves the sota performance.\n\n+ Extensive experiments are provided to show the benefit of the proposed method.\n\n\n\nWeaknesses\n\n- Despite the high performance, the novelty of the proposed method is somewhat limited. Both clustering-based positive pair mining and supervised contrastive learning based on the selected pairs are not new techniques in the community.\n\n- The description of Sec.3.3 and Sec.3.4 is hard to understand.\n\n- The improvement over the original FINCH sometimes is limited. For example, in Table 5, when applying SNC on only unlabeled data, it should be mostly similar to FINCH with unlabeled data. However, the full method does not produce a clear improvement on the SNC with u-u.\n\n- The memory cost comparison between Cip and GCD should be provided in Table 3.\n\n\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "UkFxZCUwyx", "reviewer": "Reviewer_jVVh", "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": "This paper tackles the task of generalized class discovery where both labelled and unlabelled data can be encountered during inference. The authors proposed a semi-supervised hierarchical clustering algorithm to solve this problem, which is built upon a known clustering method. The proposed approach is equipped with the capability of generating reliable pseudo labels as well as fast estimating unseen class numbers. The proposed method is evaluated on several popular benchmarks, which demonstrates promising results.", "summary_of_the_review": "A well written paper with less theoretical contribution.", "strength_and_weaknesses": "Strength:\n\n- The paper is well organized and easy to follow.\n- The proposed method is new and demonstrated to be effective.\n\nWeaknesses:\n\n- The propsed method is a simple extension of the existing hirarchical clustering algorithm, with intuitive modification that is not properly justified theoretically. For instance, why should samples linked by chains? Why should chains be connected under certain regulations? Why is it significant and necessary? These are just proposed but not well justified. \n", "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": {}}]

Author rebuttal:

Decision: Reject