Contextually Affinitive Neighborhood Refinery for Deep Clustering
Authors: Chunlin Yu
Ye Shi
Jingya Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: Deep Clustering
Self-supervised learning
re-ranking
TL;DR: In this paper, we proposed to exploit contextually affinitive neighborhood for more informative neighbors for deep clustering as well as  a progressively relaxed boundary filtering strategy for noise-robust neighbors.

Abstract: Previous endeavors in self-supervised learning have enlightened the research of deep clustering from an instance discrimination perspective. Built upon this foundation, recent studies further highlight the importance of grouping semantically similar instances. One effective method to achieve this is by promoting the semantic structure preserved by neighborhood consistency. However, the samples in the local neighborhood may be limited due to their close proximity to each other,
  which may not provide substantial and diverse supervision signals. Inspired by the versatile re-ranking methods in the context of image retrieval, we propose to employ an efficient online re-ranking process to mine more informative neighbors in a Contextually Affinitive (ConAff) Neighborhood, and then encourage the cross-view neighborhood consistency. To further mitigate the intrinsic neighborhood noises near cluster boundaries, we propose a progressively relaxed boundary filtering strategy to circumvent the issues brought by noisy neighbors. Our method can be easily integrated into the generic self-supervised frameworks and outperforms the state-of-the-art methods on several popular benchmarks.

Contextually Affinitive Neighborhood Refinery for Deep Clustering
Chunlin Yu' Ye Shi Jingya Wangl
ShhnnghaiTech University
Shanghai Engineering Research Center of Intelligent Vision and Imaging
nouchl,shiyye wangjingyaaesshnngaattcc teshangaiitchh. edu. cn
Abstract
Previous endeavors in self-supervised learning have enlightened the research of deep clustering from instance discrimination perspective. Built upon this foun- dation, recent studies further highlight the importance of grouping semantically similar instances. One effective method achieve this by promoting the se- mantic structure preserved by neighborhood consistency. However, the samples in the local neighborhood may be limited due their close proximity to each other, which may not provide substantial and diverse supervision signals. Inspired by the versatile re-ranking methods in the context of image retrieval, we propose to em- ploy an efficient online re re-ranking process to mine more informative neighbors in a Contextually Affinitive (ConAff) Neighborhood, and then encourage the cross-view neighborhood consistency. To further mitigate the intrinsic neighborhood noises near cluster boundaries, we propose a progressively relaxed boundary filtering strategy to circumvent the issues brought by noisy neighbors. Our method can be easily integrated into the generic self-supervised frameworks and outperforms the state-of-the-art methods several popular benchmarks. Code is available at: https: //g thub. com/ c1y234/ cttpcc.yy23//eeeeccstttteee inn.....
Introduction
Fueled by the expressive power of neural networks, deep clustering has emerged as a prominent solution in the low-label regime, where traditional clustering can be significantly enhanced by utilizing latent data representations. Recent advancements in self-supervised learning have further expanded the possibilities for deep clustering [38, 17, 41]. providing solid foundation for grouping similar instances. Among the various self-supervised recipes, contrastive learning methods ensure instance discrimination backed up with sufficient negative samples, while non-contrastive learning methods circumvent the class collision issue [37, 17] by simply pulling two augmented views closer. However, capturing the intrinsic semantic structure with clear decision boundaries remains challenge in deep clustering, which has led researchers to focus on more group-aware and discriminative approaches.
Group-awer croup-aware methods commonly enforce the prediction consistency between samples and their nearest neighborhoods, measured by cosine similarity or Euclidean distance for deep clustering[42, 21, 55, 56). Although these methods are simple and effective, significant portion of the retrieved neighborhoods may contain semantically redundant information. This primarily due the fact that the local neighboring samples already close to the anchor sample in the feature space, and as such, may not provide sufficient supervision signals for deep clustering. To address this limitation, previous works have added memory banks with historical features to enlarge the search space [21, 49], or labeled the proximity between samples over the entire dataset [55, 56]. Building on the foundation of
Coorresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Discmillar
Similar
E Euclidean Distance
Contextual Distance
Top- 10 Visusilizatiin in Eurlidem Neighborhood
Euclidean Neighborhood with Cross-view C Consistency
ConAff ff Neighborhood with rres--vew Consistency
Eucideen Distanue
Force
Contectual Distance
Augmetted Parrs
Reciprocal Relation
Diffleret Clesses
Top- 10 Neigh Visunlizaation in ConAff Neighhorhooo
(b)
Figure 1: (a) Comparison between the conventional Euclidean Neighborhood and the ConAff Neighborhood, both with cross-view consistency. The Euclidean distance retrieves the Euclidean neighborhood, while the contextual distance is used for the ConAff neighborhood. In reciprocal relations, "1" means two samples are in each other's top-k neighbors, and "O" indicates neither is in the other's top-k. The goal is to use reciprocal relations as contextual distance metric for the ConAff neighborhood. For instance, distant pairs A and B might be contextually similar due their similar reciprocal relations. (b) Images in the first column and their 10 nearest neighbors in the other columns, were retrieved using Euclidean Neighborhood and the proposed ConAff Neighborhood. Wrong neighbors are marked in red, and hard positives are marked in green. By default, unmarked neighbors are regarded as true neighbors.
previous group-aware methods, a key research question arises: Can we excavate more informative and reliable neighbors from intra-batch samples?
Inspired by the versatile re-ranking techniques that have shown remarkable performance in image retrieval tasks [57, 45, 32, 44, 45], we propose a novel approach to deep clustering that involves retrieving neighborhoods in a contextually affinitive metric space. Typically, the neighborhood information is retained in the ranking list of pairwise similarities between query sample and other samples. However, such a list may neglect the contextual statistics that exist between the samples. When two images are contextually affinitive, they may share similar relationships to set of reference images. In this study, the reference images are defined as the current batch, and the relationship between two images is established based whether they among each other's top-k neighbors. Consequently, distant image pairs in the original feature space may be contextually affinitive, and therefore considered as more informative positive pairs. Additionally, the contextually affinitive neighborhood in one view may align with the query sample in the other view, thus enabling cross-view neighborhood consistency. Figure 1 (a) presents comparison between the conventional Euclidean Neighborhood and the proposed ConAff Neighborhood. Additionally, Figure/ 1 (b) illustrates the results obtained when retrieving the nearest neighbors using both types of neighborhoods.
In the context of learning with neighborhoods, intrinsic noises can exist that are less observable compared to external noises caused by label contamination. These noises originate from the inferiority of the intrinsic feature space and taking these noisy samples as candidates for clustering can lead to the accumulation errors and degrade overall performance. To address this challenge, we propose progressive boundary filtering strategy based on the ConAff neighborhood that further improves the robustness of clustering. Our strategy filters out boundary samples in self- pelf-paced learning paradigm and gradually involves more complex samples for clustering.
Our contributions are summarized as follows:

---

We propose Contextually affinitive Neighborhood Refinery framework (CoNR) for deep clustering, which attempts to excavate more semantically relevant neighbors in contextually affinitive space, termed as ConAff neighborhood.
We devise a progressive boundary filtering strategy to combat the intrinsic noises existing in the ConAff neighborhood, further improving the robustness of clustering.
Extensive experiments demonstrate that CoNR improves upon the SSL baseline by signifi- cant margin, proving be competitive with state-of-the- of-the-art methods on five widely-used benchmarks. CoNR's 's simplicity and effectiveness allow it to be easily integrated into other SSL frameworks, resulting consistent performance gains.
2
Methodology
Our goal is to group a dataset containing n unlabeled samples into semantic clusters, where refers the cardinality of class label sets. Since it is non-trivial to directly obtain clean cluster assignments from scratch, we adopt an unsupervised pre-text task as the initialization for image clustering, which provides a decent neighborhood structure. However, directly utilizing the neighboring information could lead to sub-optimal results i) the nearest-neighbor searching schema based on cosine similarity may not favor hard positives that are important for clustering, and ii) the top-ranked neighbors of samples located at a cluster boundary contain inevitable noise when the learned clusters have not been not mutually separated. We, therefore, propose our main algorithm for clustering in contextually affinitive neighborhood, with progressive relaxation of boundary sample filtering, in an attempt to alleviate the above issues.
2.1 Preliminary
In general, given a dataset D = { ..,...,, En. an image uniformly sampled from D, and two augmentations T, T', we aim to first encourage the instance-aware concordance based on BYOL [11] for early pre-training, and then encourage the group-aware concordance for later finetuning, in which the cornerstone of our method lies. Following [11], the model is equipped with an online network g.F((-) and a target network Fi(.). where each of Fo()), (.))) consists of an encoder cascaded by projector, and q()) constitutes additional non non-linear predictor.
2.1.1 Instance-aware Concordance
The commonly-used instance discrimination approach for non-contrastive self-supervised learning en- forces the similarity between referenced feature and its corresponding feature in another augmented view, which can be formulated as:
E 20, 2.EB
((((Fo ((())))
(a;))))
where (-) denotes the cosine similarity. This can be interpreted as the promotion of instance-aware concordance under different augmentations and hidden transformations, which could help bootstrap an over-clustered representation via the stop-gradient and momentum-updaate techniques. Notably, this instance-aware concordance produces a general- purpose representation that can be well transferred to various downstream tasks, as well as solid basis for neighborhood discovery and higher-order contextual exploration.
2.1.2 Group-aware Concordance
In order to develop the discrimination framework from instance level group-aware concordance, we consider regarding the local neighborhood as a semantic group that involves more diverse positive samples, sharing the same spirit with previous works [10, 21, 42, 29]. Typically, group-aware concordance can be formulated as:
CG
E F.
IIE (m.)
E
sim
where (mn:)) denotes the set of neighborhood samples of æ; preserved in Fuclidean metric space, and D; E B reveals that all samples in the batch are uniformly considered to encourage the cross-view
3

---

neighborhood consistency. While the de-facto methods [10, 21, 42, 29] exploit neighborhoods to enrich the latent representation, they somehow ignore the quality of neighborhoods themselves. On the one hand, good neighbors should be clean, which means that we should select proper candidates from to retrieve clean neighbors. On the other hand, good neighbors should be rich, which motivates us to replace N (xz) with more informative neighborhoods in higher-order space. Therefore, we seek to further improve the group-aware concordance paradigm from two perspectives, which will be introduced in Sec. 2.2 and Sec. 2.3.
2.2 Contextually Aflinitive Neighborhood Discovery
As discussed in Sec. 2.1, previous works retrieve the nearest neighbors based on pairwise cosine similarity, where the distance metric depends solely on two involved data points on the hypersphere. On the contrary, our solution is to redefine how two data points are similar by considering contextual relations among the whole batch data. Concretely, we first transform the data points into contextually affinitive space, where we assume that the more similar two transformed data points are, the more high-order contextual information they share, and thus we can utilize this information to excavate more meaningful neighbor pairs, which we term as the contextually affinitive neighborhood discovery.
Formally, given a batch of normalized features B = [So, ... -18,1-1 our goal is to first transform By into contextually refined feature space Hy [hy, 1 and then retrieve the nearest neighbors set using the distance metric defined by HyH.T. Inspired by [53, 57, 34] which build the contextual relations over the entire dataset, we efficiently retrieve the contextually affinitive neighborhood via topology graphs in online manner following [53].
Building Contextual k-NN Graph. The underlying principle of building the contextual k-NN graph is to inject contextual information into nodes V and edges & so that the message propagation can move beyond the local region [53]. First, an online reciprocal adjacency matrix A E R By] | is computed as follows:
1. E ((f. Aij
O. if N () (N(,, .3)
0.5,
otherwise
where fy E (fi k1) denotes fg is among the k nearest neighbors of f. in By, and each row of A can be interpreted as the k-reciprocal encoding [57]. Then, the graph G = (V, E) can be defined as:
V = (2ilus [A,,,,". A A. (0, 1b)]
(4)
E = feyleys = (f. E ( E (0. (0....,, BBy--1]] where f, E EN k2) denotes that f, lies within the k22 nearest neighbors of f. in B3
(5)
Message Propagation. After building the contextual relational graph, the message propagation can further obtain high-order relations among k-reciprocal encoding acquired the previous stage, similar to the query expansion technique [35].
(1+1) = A, + aggregate(fef) h,"le; lei EE)), h
where a is a fixed value to realize the w-wehgtted query expansion (a-QE), and e.j E ensures that the most confident k22 nearest neighbors far less than k1- For clarity, if we assume the number of layers for message propagation L,, the
selected for aggregation. Normally, 1oz should be
initial input for the message propagation stage, h: (0) is derived from v; from the previous stage. After
propagation across all L layers, the output h (2) becomes our desired contextually refined feature, represented h.-
Affinitive Neighborhood Retrieval. So far, the intra-batch data points have been mapped to a contextual metric space via two-stage transformation. The underlying ranking statistics within these transformed data points should be more accurate and informative. Therefore, we reveal the hidden properties by explicitly retrieving the affinitive neighborhood using the refined node features, which we term as the contextually affinitive neighborhood discovery. Concretely, given the original features - and the refined features [hj. 1-11"11 1"" we define the affinitive neighborhood
[fo...., ..... (i (i,A k)) as:
(i, = Gih ((),,))

---

Then the group-aware discrimination can be reformulated as:
IE 2, (L.))
E FF
We remark that the contextually affinitive neighborhood discovery ensures more informative neighbors are involved for training at every iteration, and the superior contextual neighbor information lying between the non-differentiable transformed data points is synchronously propagated to the original features to improve the representation quality.
2.3 Progressive Boundary Filtering with Relaxation
In this section, we are focused on the inevitable noise existing in the neighborhood. Although the contextually affinitive neighborhood could offer more contextually relevant samples boost training, there still exist some unreliable samples among the top-ranked neighbors. Such a phenomenon becomes more evident when the sampled data points lie the decision boundary. As consequence, the inclusion of contaminated neighbor information will cause noise accumulation, to the detriment of later training iterations. Therefore, we propose an online boundary sample filtering with progressive relaxation to alleviate the issue.
2.3.1 Online Boundary Sample Detection
In order better assess the current clustering quality and detect the samples located the boundary, we apply k-means after each training epoch, which is a common practice in former works [17, 38]. Instead of directly utilizing the consistency of pseudo labels among neighbors, emphasis on the holistic cluster structure, which is to distinguish farther samples located at the cluster boundary with controlled degrees. Inspired by the silhouette score which measures the ratio between the mean intra-cluster distance and the mean ncarest-cluster distance in an offline manner, we devise an approximate online version serve a similar purpose.
place more
Formally, given a sample æ; with pseudo label π (2;), and K cluster centroids C = [cl .... cxl |" obtained from last epoch, we first approximate the mean intra-cluster distance d, and nearest mean inter-cluster distance dN by:
df [[s: Cr(2)))l2 d = [If: (2))2)
(9)
where
T' (xx)
arg min
[[ cx|12,
(10)
And then the boundary ratio be computed as:
d/
P max d/. d
(11)
Normally, large boundary ratio indicates the given sample more likely be located at the boundary, while small ratio implies the sample is close to its cluster center, and it is safer to exploit non-boundary samples for training since they exhibit cleaner neighborhoods.
2.3.2 Progressive Relaxation
While boundary samples may possess inferior neighborhoods, it is barely true to ignore these samples during the entire clustering process. To make balance, we progressively relax the restrictions of samples to promote neighborhood consistency. The motivations are two folds. First, we set a strict criteria to select clean samples at the initial stage avoid the confirmation bias brought by noisy samples. Second, after the neighborhoods have been consistently refined using cleaner samples, the boundary samples can further improve the overall clustering quality without affecting the holistic structure, which can be validated in our ablation experiments.
Formally, given a batch B sampled from the dataset, we adopt a linearly increased fraction ratio (r dynamically control filtering threshold (t)) which is used to filter out the hard boundary samples at epoch t.
1 - fro(to)
(((() = (t( +
(T -t)),
(12)
t
5

---

Algorithm The proposed algorithm CoNR
Require: Dataset D, online network 6, and target network 0
I: Pre-train 0, 0 on D
b Eq. (1)
2: while Clustering do
3: Sample batch from
4: Transform batch features B, to y
5: Retrieve contextually affinitive neighborhood N for By using H.y
D Eq. (7)
6: Progressively filter out boundary samples for clustering
Eq. (13)
Update with Sii and SGD optimizer
Eq. (14)
8: Update & with momentum moving average
9: end while
where is the current epoch, to is the epoch to start clustering, and is the maximum number of epochs for group-aware concordance clustering. Then o(1) can obtained by retrieving the largest ratio among the top (r(*) smallest boundary ratios in ( r M/8-1)- we filter out these samples whose boundary ratios are too large to be involved in clustering at the current epoch t:
According to the ((t),
(13) Notably, our progressive boundary filtering strategy is essentially different from the self-labeling step that selects the most confident samples for fine-tuning prior work [42. 29]. First, their selection strategy is completely based on prediction confidence pseudo-label consistency, neglecting the intrinsic cluster structure evaluate the difficulty of samples. Second, their self- self-labeling step based on cross-entropy loss, which heavily relies on stronger augmentations to avoid overfitting. By contrast, our filtering strategy proposed to search robust neighborhood and avoid accumulation errors during the group-aware concordance, which does not require additional modules or augmentations.
B (ws/rr S {(()), E {0...., [B]-)}}
2.4 The Overall Objective and Optimization
Based on Sec. 2.2 and Sec. 2.3, our final objective for group-aware concordance be further formulated as:
GAF eim
E CIBBB E (((
(14)
#.E(B(B()) JEN (L.)
where 2; E (B)B(O} controls whether the samples should be selected as candidates to retrieve neighborhood, and j E (i k) determines whether the samples are contextually affinitive to the candidates. We do not exclude Bd() from A/(a) (i,, k) as our aim is to filter out unreliable candidates lying around the boundaries, which means that for each selected candidate, we take its ConAff neighborhood whole to preserve its original structure. The overall training pipeline is shown in Algorithm 1.
As discussed in Sec. 2.1, our framework comprises two training stages: instance-aware concordance and group-aware concordance, and the final objective for optimization can be expressed as:
Liotal = I(t < to) to) + +I(t 2 to CGAF
c
(15)
3
Related Work
3.1 Deep Clustering
Deep clustering, an integration of deep learning and traditional clustering, has emerged as a de facto paradigm to learn feature representations and cluster unlabelled data simultaneously. Originated from seminal works [48], deep clustering has seen a paradigm shift from traditional methodologies [6, 36, 28, 43, 52] to more sophisticated models [4, 12, 14, 15, 30, 39]. The advent of contrastive learning in deep clustering [23, 24, 38] has brought new perspectives but also introduced challenges, mainly in defining contrastive losses and balancing instance pairs. Concurrently, self-supervised learning and multi-modal clustering techniques are pushing the boundaries further, with hybrid models combining generative and discriminative aspects, leading to richer representations and improved performance in deep clustering.

---

3.2 Self-Supervised Learning
Historically, self-suue learning (SSL) approaches for representation learning have primarily utilized generative models [9] or relied on uniquely crafted pretext tasks such as solving jigsaw puzzles [31] and colorization [51] to the general-purpose representations. However, the emergence of contrastive learning methods [13, 5, 47] has proven highly effective for both representation learning and succeeding tasks. Despite their effectiveness, these methods necessitate vast array of negative examples to ensure instance-aware discrimination in the embedding space. Apart from instance diserimination, group-aware discrimination focuses more on the semantic structure. While Deep Clustering [2], ODC [50] and COKE [33] disentangle the clustering stage and the learning stage, SeLa [1] and SWAV [3] attempt to solve the grouping problem via optimal transport. Another line of methods [21, 10, 27] focuses neighborhood consistency, consistently bootstrapping the representation by discovering abundant semantically similar instances.
3.3 Re-ranking in Image Retrieval
Image Retrieval aims to retrieve the gallery images that are the most similar to the query image from a large corpus of images. Re-ranking training-free technique that used reorder and improve the initial ranking result using higher-order similarity metrics. Generally, k-NN-based re-ranking represents the fashion in image re-ranking. k-NN-based re-ranking views the k-reciprocal nearest neighbors of an image as highly relevant candidates [54, 34, 20J. Jegou et al. [18] iteratively correct distance estimates based on local vector distributions, Liu et al.[25] utilize graph convolutional networks (GCN) to encode neighbor information directly into image descriptors Zhong el al. [57] encodes the reciprocal information of a query image into vector and computes similarities using Jaccard distance. Zhang et al. [53] accelerate [57] by using k-reciprocal encodings the node features of a GNN and enhancing the features via graph propagation. Specifically, our ConAff neighborhood is inspired by [53, 57] which considers contextual similarity with query expansion.
4 Experiments
4.1 Datasets and Settings
Following [17, 23), we report the deep clustering results on five widely-wised benchmarks, including
CIFAR-10 10 [22], CIFAR-20 [22]. STL [7], ImageNet-10 [4], ImageNet-Dogs [4]. CIFAR-10 and CIFAR-20 both contain 60,000 images, and CIFAR-20 uses 20 superclasses from CIFAR-100
following prior practice [17, 233. STL contains 100,000 unlabeled images and 13,000 labeled images. ImageNet-10 selects 10 classes from ImageNet-1k, Ik, containing 13,000 images while ImageNet-Dogs selects 15 different breeds of dogs from ImageNet-Ik, Ik, containing 19,500 images. For image size, we use 32x32 for CIFAR-10 10 and CIFAR-20, 96x96 for STL-10 and ImageNet-10. 224x224 for ImageNet-Dogg. following the prior work [17]. For the dataset split, both train and test data are used for CIFAR-10 and CIFAR-20, both labeled and unlabeled data are used for STL-10, and only training data of ImageNet-I1 10 and ImageNet-DDe Dogs are used, which is strictly the same setting with [17, 38, 23, 24]. Also, all the experiments are conducted with a known cluster number.
4.2 Implementations
For data augmentations, we strictly follow [17], which uses ResizedCrop, ColorJitter, Grayscale, and HorizontalFlip, for fair comparison with previous works [17, 38, 41]. For loss computation, we use a symmetric loss by swapping the two augmentations and computing the asymmetric losses twice. For architecture, we use ResNet-18 88 for small-scale datasets CIFAR-10 10 and CIFAR-20 and ResNet-34 for the other datasets, following [23, 17, 40]. For CIFAR-10 10 and CIFAR-20. we replace the first convolution filter of size 7x7 and stride 2 with a filter of size 3x3 and stride 1, and remove the first max- max-pooling layer, following [17]. All datasets are trained with 1000 epochs, where the first 800 epochs are trained with standard BYOL loss C. and the remaining 200 epochs are trained with our proposed Sim We adopt the stochastic gradient descent (SGD) optimizer and the cosine decay learning rate schedule with 50 epochs warmup. The base learning rate is 0.05 with a batch size of 256. For instance-aware concordance, we directly follow [11, 17] to establish a fair baseline. For group-aware concordance, we set k, k1, ky to 20,30,10 10 for ImageNet-Dogs and 10, 10,2 for other datasets, since ImageNet-Doos is fine-grained dataset compared with previous ones.
7

---

Table 1: Clustering result comparison (in percentage %) with the state-of-the-art art methods on five benchmarks.
CIFAR-I0
CIFAR-20
STL-10
ImageNet-10
ImageNet-Dooe
NMI
ACC
ARI
NMI
ACC
ARI
NMI
ACC
ARI
NMI
ACC
ARI
NMI
ACC
ARI
HC [19]
51.3
61.7
41.1
25.7
43.1
49.9
29.5
DCCM [46]
49.6
62.3
40.8
28.5
32.7
17.3
37.6
48.2
26.2
60.8
71.0
55.5
32.1
38.3
18.2
PICA [16]
46.7
32.2
78.2
85.0
73.3
33.6
32.4
SCAN [42]
79.7
88.3
77.2
48.6
50.7
33.3
69.8
80.9
64.6
NMM [8]
74.8
84.3
70.9
48.4
47.7
31.6
69.4
80.8
65.0
CC [23]
79.0
63.7
43.1
42.9
26.6
76.4
85.0
72.6
85.9
89.3
82.2
44.5
42.9
27.4
MICE [41]
73.7
83.5
69.8
43.6
44.0
28.0
63.5
75.2
$7.5
42.3
43.9
28.6
GCC [56]
76.4
85.6
72.8
47.2
47.2
30.5
68.4
78.8
63.1
84.2
90.1
82.2
49.0
52.6
36.2
TCL. [24]
81.9
88.7
78.0
52.9
53.1
35.7
79.9
86.8
75.7
87.5
89.5
83.7
62.3
64.4
51.6
IDFD [40]
66.3
42.6
26.4
64.3
75.6
$7.5
89.8
95.4
54.6
59.1
TCC [38]
79.0
90.6
73.3
47.9
49.1
31.2
73.2
81.4
68.9
84.8
89.7
82.5
55.4
59.5
41.7
ProPos [17]
85.1
91.6
83.5
58.2
$7.8
42.3
75.8
86.7
73.7
89.6
95.6
90.6
73.7
77.5
67.5
DivClust [26]
72.4
81,9
68.1
44.0
43.7
28.3
93.6
87.8
51.6
52.9
BYOL [11]
79.4
76.6
55.5
53.9
37.6
71.3
82.5
65.7
86.6
93.9
87.2
63.5
69.4
CoNR (Ours)
86.7
93.2
86.1
60.4
60.4
44.3
85.2
92.6
84.6
91.1
96.4
92.2
74.4
79.4
66.7
4.3
Comparison with the State-of-the-Art
Comparison Settings. In this section, we compare our methods ConNR with the current state-of- the-art methods, as shown in Table 1. Specifically, IIC, DCCM, and PICA clustering methods without contrastive learning. SCAN and NMM are multi-stage methods that require pre-training and fine-tuning. DivClust is recently proposed method based concensus clustering controlling the degree of diversity, and we report their best performance among different diversity levels in Table for comparison. The other methods mostly learn representations based contrastive learning non- contrastive learning in an end-to-end fashion. For these methods that learn a generic representation rather than directly output cluster assignments, we use k-means for evaluation. In particular, for ProPos, YOO, and ConNR (ours), the produced features output by the target encoder are used for k-means for fair comparison.
Comparison Results. Regarding the quantitative results, we achieve consistent performance gains across the board. Specifically, for relatively small datasets such ImageNet- 10 and STL-10 with 13K images, our method reaches satisfying results, which not only surpass our baseline BYOL by least +10.1 % ACC STL-10 in only 200 epochs, but also further achieve performance with 96.4% ACC on ImgeNet-10 10. For moderate-scale datasets such as CIFAR-10 10 and CIFAR-20 with 60K images, our method yields stable performance improvement with an average gain of +1 +1.6% and +2.6% ACC compared with ProPos [17] on CIFAR-I0 and CIFAR-20, respectively, More importantly, for the challenging fine-grained dataset ImageNet-Dogs,, we achieve +6.2% and +1 +1.9% performance boosts in terms of ACC on our baseline and the most advanced competitors. We ascribe this significant improvement to the superiority of our ConAff neighborhood, especially on the fine-grained task. Additionally, we provide results on Tiny ImageNet and performance comparisons Appendix A.3.
sfate-of-the-aee art
4.4 Ablation Study
In this section, we perform a comprehensive ablation experiment in Table 2 to validate the effec- tiveness of our proposed method. Specifically, InC represents the baseline, CnAftN, OBD, PR techniques proposed by our method, and IN a standard choice used for performance comparison.
Validation of Contextually Affinitive Neighborhood. We make the following observations: First, our proposed contextually-affinite neighborhood (ConAliN) consistently outperforms the local neighborhood approach, irrespective of whether progressive boundary filtering strategy is utilized or not. However, ConAffN achieves its peak performance when both online boundary filtering and progressive relaxation utilized. Instead, the local neighborhood meets with performance saturation when combined with progressively relaxed boundary filtering. Also, as illustrated by the purity curve in Figure 2, ConAffN identifies more reliable neighbors, particularly when the value of K is larger.
Validation Progressive Boundary Filtering with Relaxation. As previously discussed, both LN and ConAfINN combined with OBD experience consistent performance gains, with +1.9% and +1.4%,

---

Neighborhood Purity Curve
Table 2: Ablation Results (in percentage %) on CIFAR-10. (InC: Instance-aware Concordance, LN:
100
Local Neighborhood, CnAffN: Contextually Affinitive Neighborhood, OBD: Online Boundary Detection, PR: Progressive Relaxation)
Ratio
CIFAR-10
InC LN
CпAfN
OBD
PR
NMI
ACC
ARI
79.4
87.8
76.6
81.9
89.6
78.7
80
houndary Fitzring
Conoll has neghhtemood Local Neghtortood
84.6
91.1
82.4
V V
83.9
91.1
82.3
/
84.8
91.6
84.2
/
85.7
92.5
85.1
Figure 2: The curve of the purity (in percentage
V 86.7
93.2
86.1
%) with the changes of K.
respectively. We speculate that the boundary filtering strategy uniformly improves the robustness of neighborhood clustering. Moreover, the online boundary detection exhibits much cleaner neighborhood (Figure 2), which supports our motivation. Despite the efficacy of OBD, we find progressive relaxation (PR) drives the model towards less biased clustering as it gradually involves the difficult samples for clustering, which further improves the ACC by +0.7%.
132
Pasaate Autyccod CIFAR-18
ENE WELL an Teagee
ACD Cacca LaageNia Dagt
(70
435
635
0.00
255
300
(b)
(c)
Figure 3: (a) Performance comparison with different initial fraction ratios CIFAR-10. (b) Perfor- mance with different selection of k1, K2 on ImageNet-Dool Dogs. (c) Clustering performance comparison with ConNR and BYOL on ImageNet-Dogs.
More Discussions. We conducted an analysis of three parameters: and k2, which represent the number of neighbors used to construct the graph, and fr, the fraction ratio set at the initial training stage. Figure 3(a) presents the results with varying fr values. The outcomes exhibit relative stability within the range of [0.70, 0,80, 0.90] for fr, however, a noticeable performance decline is observed when fr This indicates lack boundary filtering applications. We provide the results with different choices of kı and K2 in Figure 3(b). For non-aggressive strategy where k1 and k2 are smaller than 10, there are consistent gains compared with the baseline, while for more aggressive choices where k1, l2 are larger, the performance can be improved even further, validating the design of contextually affinitive neighborhood. In Figure 3(c), we present the ACC curves generated during the clustering process. Here, we can see that ConNR not only converges considerably faster than BYO,, but also provides notable improvements when implemented as an add-on module. detailed exploration of how ConNR benefits other self-supervised benchmarks is provided in Appendix A.2.
5 Conclusion and Limitations
In this paper, we proposed a novel method to improve deep clustering in self-supervised learning by promoting the semantic structure preserved by neighborhood consistency. Our approach, the Contextually Affinitive (ConAff) Neighborhood, employs an efficient online re-ranking process to mine more informative neighbors and encourages cross-view neighborhood consistency. We also

---

introduced a progressively relaxed boundary filtering strategy to mitigate the intrinsic neighborhood noises near cluster boundaries. Our method outperformed state-of-the-an methods on several popular benchmarks and could be easily integrated into generic self-supervised frameworks. One potential limitation of our approach is that ConNR generally assumes the labels induce an equipartition of the whole data and thus does not contain specific mechanisms for handling unbalanced or long-tailed datasets. We believe that our approach can be further extended for this purpose. While our major goal in this paper is dedicated to learning clustered and well-separated representation for deep clustering, the proposed ConAff neighborhood s a generic design choice that could be viewed from a broader perspective, hopefully benefiting the task of self-supervised learning that focuses more downstream applications.
Acknowledgement
This work was supported by NSFC (No.62303319), Shanghai Sailing Program (2IYF1429400, 22YF1428800), Shanghai Local College Capacity Building Program (23010503 100), Shanghai Fron- tiers Science Center of Human- Intelligent Perception and Human-Maching Collaboration (ShanghaiTech University). and Shanghai Engineering Research Center of Intelligent Vision and Imaging.
Artificial Intelligence (ShangHAD, MoE Key Laboratory of
References
[1] Yuki Markus Asano, Christian Rupprecht, and Andrea Vedaldi. Self-labelling via simultancous clustering and representation learning. In International Conference on Learning Representations (ICLR), 2019.
[2] Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsupervised learning of visual features. In Proceedings of the European Conference Computer Vision (ECCV), 2018.
[3] Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. Advances in Neural Information Processing Systems (NeurIPS), 2020.
[4] Jianlong Chang, Lingfeng Wang, Gaofeng Meng, Shiming Xiang, and Chunhong Pan. Deep adap- tive image clustering. In Proceedings of the IEEE/CVE International Conference on Computer Vision (ICCV), 2017.
[5] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In nternational Conference on Machine Learning (ICMI.), 2020.
[6] Yizong Cheng. Mean shift, mode seeking, and clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 1995.
[7] Adam Coates, Andrew Ng, and Honglak Lee. An analysis of single-layer networks in unsu- pervised feature learning. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2011.
[8] Zhiyuan Dang, Cheng Deng, Xu Yang, Kun Wei, and Heng Huang. Nearest neighbor matching for deep clustering. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2021.
[9] Jeff Donahue, Philipp Krähenbühl, and Trevor Darrell. Adversarial feature learning. In Interna- tional Conference on Learning Representations (ICLR), 2017.
[10] Debidatta Dwibedi, Yusuf Aytar, Jonathan Tompson, Pierre Sermanet, and Andrew Zisserman. With a little help from my friends: Nearest-neighbor contrastive learning of visual representations. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), 2021.
[11) Jean-Bastien Grill et al. Bootstrap your own latent-a new approach to self-supervised learning. Advances in Neural Information Processing Systems (NeurIPS), 2020. 2020.
10

---

[12] Philip Haeusser, Johannes Plapp, Vladimir Golkov, Elie Aljalbout, and Daniel Cremers. Asso- ciative deep clustering: Training a classification network with no labels. In German Conference on Puttern Recognition (GCPR), 2019.
[13] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
[14) Jiabo Huang, Qi Dong, Shaogang Gong, and Xiatian Zhu. Unsupervised deep learning by neighbourhood discovery. In International Conference Machine Learning (ICML), 2019.
[15] Jiabo Huang, Qi Dong. Shaogang Gong, and Xiatian Zhu. Unsupervised deep learning via affinity diffusion. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2020.
[16] Jiabo Huang, Shaogang Gong, and Xiatian Zhu. Deep semantic clustering by partition con- fidence maximisation. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition (CVPR), 2020.
[17] Zhizhong Huang. Jie Chen, Junping Zhang, and Hongming Shan. Learning representation for clustering via prototype scattering and positive sampling. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2022.
[18] Herve Jegou, Hedi Harzallah, and Cordelia Schmid. A contextual dissimilarity measure for accurate and efficient image search. In 2007 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2007.
[19] Xu Ji, Joao F Henriques, and Andrea Vedaldi. Invariant information clustering for unsupervised image classification and segmentation. In Proceedings of the IEEE/CVF International Conference Computer Vision (ICCV), 2019.
[20] Sungyeon Kim, Dongwon Kim, Minsu Cho, and Suha Kwak. Self-taught metric learning without labels. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2022.
[21] Soroush Abbasi Koohpayegani, Ajinkya Tejankar, and Hamed Pirsiavash. Mean shift for self- supervised learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), 2021.
[22] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[23] Yunfan Li, Peng Hu, Zitao Liu, Dezhong Peng, Jocy Tianyi Zhou, and Xi Peng. Contrastive clustering. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2021.
[24] Yunfan Li, Mouxing Yang, Dezhong Peng, Taihao Li, Jiantao Huang, and Xi Peng. Twin contrastive learning for online clustering. International Journal of Computer Vision (IJCV), 2022.
[25] Chundi Liu, Guangwei Yu, Maksims Volkovs, Cheng Chang, Himanshu Rai, Junwei Ma, and Satya Krishna Gorti. Guided similarity separation for image retrieval. Advances in Neural Information Processing Systems (NeurIPS), 2019.
[26] Ioannis Maniadis Metaxas, Georgios Tzimiropoulos, and Ioannis Patras. Divelust: Controlling diversity in deep clustering. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2023.
[27] KL Navaneet, Soroush Abbasi Koohpayegani, Ajinkya Tejankar, Kossar Pourahmadi, Akshay- varun Subramanya, and Hamed Pirsiavash. Constrained mean shift using distant yet related neighbors for representation learning. In Proceedings of the European Conference on Computer Vision (ECCV), 2022.
[28] Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. Advances in Neural Information Processing Systems (NeurIPS), 2001.
11

---

[29] Chuang Niu, Hongming Shan, and Ge Wang. Spice: Semantic pseudo-labeling for image clustering. IEEE Transactions on Image Processing (TIP), 2022.
[30] Chuang Niu, Jun Zhang, Ge Wang, and Jimin Liang. Gatcluster: Self-supervised gaussian- attention network for image clustering. In Proceedings of the European Conference on Computer Vision (ECCV), 2020.
[31] Mchdi Noroozi and Paolo Favaro. Unsupervised learning of visual representations by solving jigsaw puzzles. In Proceedings of the European Conference on Computer Vision (ECCV), 2016.
[32] Jianbo Ouyang, Hui Wu, Min Wang. Wengang Zhou, and Houqiang Li. Contextual similarity aggregation with self-attention for visual re-ranking. Advances in Neural Information Processing Systems (NeurIPS), 2021.
[33] Qi Qian, Yuanhong Xu, Juhua Hu, Hao Li, and Rong Jin. Unsupervised visual representation learning by online constrained k-means. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2022.
[34] Danfeng Qin, Stephan Gammeter, Lukas Bossard, Till Quack, and Luc Van Gool. Hello neighbor: Accurate object retrieval with k-reciprocal nearest neighbors. In Proceedings of the IEÈE Conference on Computer Vision and Pattern Recognition (CVPR), 2011.
[35] Filip Radenović, Giorgos Tolias, and Ondiej Chum. Fine-tuning cnn image retrieval with no human annotation. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2018.
[36] Anant Ram, Sunita Jalal, Anand S Jalal, and Manoj Kumar. A density based algorithm for discovering density varied clusters in large spatial databases. International Journal of Computer Applications, 2010.
[37] Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, and Hrishikesh Khande- parkar. A theoretical analysis of contrastive unsupervised representation learning. In International Conference on Machine Learning (ICML), 2019.
[38] Yuming Shen, Ziyi Shen, Menghan Wang. Jie Qin, Philip Torr, and Ling Shao. You never cluster alone. Advances in Neural Information Processing Systems (NeurIPS), 2021.
[39] Guy Shiran and Daphna Weinshall. Multi-moda deep clustering: Unsupervised partitioning of images. In 2020 25th International Conference on Pattern Recognition (ICPR), 2021.
[40] Yaling Tao, Kentaro Takagi, and Kouta Nakata. Clustering-friendly representation learning via instance discrimination and feature decorrelation. In International Conference on Learning Representations (ICLR), 2021.
[41] Tsung Wei Tsai, Chongxuan Li, and Jun Zhu. Mice: Mixture of contrastive experts for unsupervised image clustering. In International Conference on Learning Representations (ICLR), 2021.
[42] Wouter Van Gansheke, Simon Vandenhende, Stamatios Georgoulis, Marc Proesmans, and Luc Van Gool. Scan: Learning to classify images without labels. In Proceedings of the European Conference on Computer Vision (ECCV), 2020.
[43] Joe H Ward Jr. Hierarchical grouping to optimize objective function. Journal of the American statistical association, (8(301))236-2444 1963.
[44] Hui Wu, Min Wang, Wengang Zhou, and Houqiang Li. A general rank preserving framework for asymmetric image retrieval. In International Conference on Learning Representations (ICLR).
[45] Hui Wu, Min Wang, Wengang Zhou, Houqiang Li, and Qi Tian. Contextual similarity distillation for asymmetric image retrieval. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2022.
[46] Jianlong Wu, Keyu Long, Fei Wang, Chen Qian, Cheng Li, Zhouchen Lin, and Hongbin Zha. Deep comprehensive correlation mining for image clustering. Proceedings of the IEFF/CVF international conference on computer vision (ICCV), 2019.
12

---

[47] Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin. Unsupervised feature learning via non- non-parametri instance discrimination. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2018
[48] Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. nternational Conference on Machine Learning (ICML), 2016.
[49] Shiqi Yang, Joost van de Weijer, Luis Herranz, Shangling Jui, et al. Exploiting the intrinsic neighborhood structure for source-free domain adaptation. Advances in Neural Information Processing Systems (NeurIPS), 2021.
[50] Xiaohang Zhan, Jiahao Xie, Ziwei Liu, Yew-Soon Ong, and Chen Change Loy. Online deep clustering for unsupervised representation learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
[51] Richard Zhang, Phillip Isola, and Alexei A Efros. Colorful image colorization. In Proceedings of the European Conference on Computer Vision (ECCV), 2016.
[52] Tian Zhang. Raghu Ramakrishnan, and Miron Livny. Birch: an efficient data clustering method for very large databases. ACM sigmod record, 1996.
[53] Xuanmeng Zhang, Minyue Jiang, Zhedong Zheng, Xiao Tan, Errui Ding, and Yi Yang. Un- derstanding image retrieval re-ranking: A graph neural network perspective. arXiv preprint arXiv:2012.07620, 2020.
[54] Liang Zheng, Yi Yang, and Qi Tian. Sift meets emn: decade survey of instance retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2017.
[55] Mingkai Zheng, Fei Wang, Shan You, Chen Qian, Changshui Zhang, Xiaogang Wang, and Chang Xu. Weakly supervised contrastive learning. In Proceedings of the IEEE/CVF Interna- tional Conference Computer Vision (ICCV), 2021.
[56] Huasong Zhong. Jianlong Wu, Chong Chen, Jianqiang Huang, Minghua Deng. Liqiang Nie, Zhouchen Lin, and Xian-Sheng Hua. Graph contrastive clustering. In Proceedings of the IEEE/CVF International Conference Computer Vision (ICCV), 2021.
[57] Zhun Zhong, Liang Zheng, Donglin Cao, and Shaozi Li. Re-ranking person re-identification with k-reciprocal encoding, In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
13


Reviews:
[{"review_id": "NqEvIfOrFo", "reviewer": "Reviewer_Prtf", "summary": "This paper proposes a Contextually affinitive Neighborhood Refinery framework for deep clustering which employs an online re-ranking process to mine more informative neighbors and encourage the cross-view neighborhood consistency. A progressive relaxed boundary filtering strategy is present to reduce the influence of neighborhood noise near cluster boundaries. ", "questions": "See weakness", "limitations": "When class-distribution is imbalanced, the neighborhood could be unreliable for identifying hard positives. ", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The paper is well-written, and the motivation is clear. \n2. Multiple baseline methods are included for comparison. \n", "weaknesses": "1. Multiple terms are used without explanation. For example, what does $l$ in Eq. 6 refer to? And $r$ in Eq. 7?\n2. Knowing the cluster number is generally an impractical assumption. What if the actual number of classes is unknown? Will the proposed method be able to estimate the number of classes? \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the appreciation of our clear motivation and sufficient experiments. We would like to address your concerns one by one as below.\n\n**q1: Multiple terms are without explanation. What are $l$ and $r$ referring to?**\n\nWe would like to try our best to address your concerns regarding the notations you have pointed out. First of all, $l$ simply represents the level of a layer for message propagation, in which the total number of layers is set to 2 (i.e. $L=2$) during the implementation. The message propagation generally takes node features $v_i$ (i.e. $k$-reciprocal encodings) obtained from the previous stage as input $h_{i}^{(0)}$ for the current stage. Since the role of message propagation is to refine those features by local query expansion, we literally use $r$ to represent the final **r**efined features as $h_{i}^{r}$ (as we stated in L121 and L144), which is exactly the output of the final propagation layer $h_{i}^{(L)}$.\n\nAs per the reviewer's request, we may use the terms more neatly in our revised version to avoid any confusion.\n\n**q2: Does knowing the cluster number K imply an impractical assumption?**\n\nWe would like to first point out that all pre-existing works [9, 17, 16, 20, 23, 24, 36, 38, 39, 40, 44, 54] of deep clustering assume K as a pre-defined number. Therefore, we respectfully disagree that considering K as a known number undermines the value of our work.\n\nSecondly, we would like to clarify that considering the cluster number prior has practical implications.\n- Notably, the current deep clustering field is still dominated by the parametric clustering paradigm since it enjoys flexible scalability and trustworthy performance, despite being confined by a predefined number of clusters that oftentimes could be accessible. \n- Only a few non-parametric deep clustering methods have emerged recently in an attempt to deal with an unknown cluster number. Though this is a promising direction, the current non-parametric deep clustering approaches [R1] mainly implement this vision on small datasets (MINIST and CIFAR-10). \n\nTherefore, we could conclude that both parametric and non-parametric deep clustering methods have their respective applicability and practicality in the mainstream of the deep clustering field.\n\n[R1] Generalised Mutual Information for Discriminative Clustering, NeurIPS, 2022.\n\n**q3:What if the actual number of classes is unknown? Will our method be able to estimate the cluster number?**\n\nWhile we make a fair comparison with former works by using a known number of clusters, our method could still gracefully handle an unknown number of classes during representation learning, since one of our contributions ConAff neighborhood is not reliant on the cluster number K. This could be evidenced by our ablation study (Table 2). Specifically, when removing the progressive boundary filtering strategy that relies on K, ConNR achieves 84.6 | 91.1 | 82.4 in terms of NMI | ACC | ARI, which still outperforms our baseline by at least +3.3% w.r.t. ACC. \n\nBased on the aforementioned facts, our ConAffN could be simply integrated with existing techniques to automatically select the optimal K among some candidates, such as silhouette analysis, which evaluates whether data points are well matched to their assigned clusters.\n\n**q4: The neighborhood could be unreliable when the class-distribution is imbalanced**. \n\nWe would like to emphasize that our method, in comparison to other neighborhood-based methods, can handle imbalance issues to a certain extent. As detailed in our methodology (Lines 105-108), the ConAffN method aims to improve neighborhood quality by focusing on two aspects: cleanliness and richness. Importantly, the imbalance between various classes is unlikely to significantly impact these two aspects. Regarding the ConAff neighborhood in particular, it's worth noting that samples from minority classes remain contextually similar within the ConAff neighborhood due to their dissimilarity from other samples in the majority classes.\n\nWe recognize that clustering minor classes could be challenging, particularly in situations of extreme class imbalance. Consequently, we acknowledge this extreme imbalance scenario as a limitation of our approach. We anticipate that there is potential to enhance ConNR through various means, including the exploration of techniques such as re-sampling minor classes in our future research endeavors.\n \n. "}, {"review_id": "AtNL7tqnlR", "reviewer": "Reviewer_cuTM", "summary": "In this paper, the authors introduce the Contextually affinitive Neighborhood Refinery (CoNR) framework, which presents a novel approach to deep clustering. CoNR utilizes a simple and efficient online re-ranking process to identify informative neighbors within the ConAff Neighborhood, promoting cross-view neighborhood consistency. Additionally, CoNR incorporates a progressive boundary filtering strategy that effectively tackles intrinsic noises near cluster boundaries. Overall, the CoNR framework offers a promising solution for deep clustering, enabling improved clustering performance and easy integration into existing SSL frameworks.", "questions": "1) Compared with ConAff neighborhood, why might the local neighborhood samples provide limited supervision signals, and what are the implications of this limitation?\n2) How does the proposed method promote cross-view neighborhood consistency? Need more explanation.", "limitations": "The potential utilization of the ConAff neighborhood in generic SSL frameworks beyond deep clustering is an interesting prospect. However, the paper does not thoroughly explore this possibility, which can be considered a limitation.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1) The paper introduces a novel framework called Contextually affinitive Neighborhood Refinery (CoNR) for deep clustering, which allows for the mining of more semantically relevant neighbors.\n\n2) One of the key advantages of CoNR is its seamless integration into other SSL frameworks. Its simplicity and effectiveness enable researchers and practitioners to easily incorporate it into their existing frameworks, leading to consistent performance improvements.\n\n3) To tackle the challenge of intrinsic noises near cluster boundaries, the paper presents a progressive boundary filtering strategy. This strategy adopts a self-paced learning paradigm to gradually filter out boundary samples, thereby enhancing the robustness of the clustering process by involving more complex samples.\n  \n4) Extensive experiments conducted demonstrate that CoNR surpasses state-of-the-art methods on five widely-used benchmarks, establishing its competitiveness in the field of deep clustering.", "weaknesses": "1) The paper does not thoroughly analyze the limitations of the CoNR framework. A deeper exploration of the potential drawbacks or scenarios where CoNR may not perform optimally would have provided a more balanced perspective on its applicability.\n\n2) While the paper briefly mentions the simplicity and effectiveness of CoNR, it could benefit from a more explicit discussion on potential future directions for improvement and extension of the proposed framework", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We tremendously appreciate reviewer cuTM’s positive assessment and highlighting our contribution to the deep clustering community. In regards to your questions, see our responses below:\n\n**q1: About deeper exploration of limitations of ConNR.**   \nRegarding your concerns, we would like to provide a deeper analysis of our limitations and how we could possibly improve them. Though ConNR does not have a strict requirement for balanced classes, it still could not circumvent the **extremely long-tailed** cases, like most existing works. However, we believe that ConAff neighborhoods could serve as a starting point, which could be gracefully combined with a re-sampling strategy of the minority classes to avoid being overwhelmed by the majority classes. On the other hand, we would like to highlight that ConAff could still tolerate a moderately imbalanced case, as samples from minority classes remain contextually similar within the ConAff neighborhood due to their dissimilarity from other samples in the majority classes.\n\n**q2: About future extension and direction of ConNR.**\n\nThanks for this suggestion, we would like to explicitly add this discussion to our appendix in any revised version. \n\n- Currently, we have validated that ConNR could be easily migrated to various SSL frameworks such as BYOL, SimSiam, and MoCo, all of which are discussed within the context of instance-aware concordance, either through contrastive learning or non-contrastive learning. On the other hand, we notice that there is another line of research in SSL that focuses on **generative (predictive) learning** such as MAE and MixMIM.  We believe it is an interesting direction to further explore ConNR in the generative contexts.\n\n- While our focus in this work is dedicated to clustering, it is possible to also apply our framework beyond our current scope. Specifically, our proposed ConAff neighborhood (ConAffN) is a generic design choice that could be viewed from a broader perspective, hopefully benefiting the task of self-supervised learning that focuses more on downstream applications. Therefore, we believe ConAffN could be further discussed and explored to implement this vision in future works.\n\n**q3: why might local neighborhoods provide limited supervision signals? and the implications?**\n\nThanks for raising this concern, we would like to elaborate on it more concretely. As discussed in L30-32, the local neighborhoods are considered in a metric space of cosine similarity. Therefore $x_i \\in N(x_j)$ indicates that $x_i$ and $x_j$ are already close to each other in terms of cosine similarity, then the supervision signals could be limited when we try to maximize their cosine similarity, manifesting as small losses during optimization. Nevertheless, the proposed ConAff neighborhood considers a contextually affinitive metric space, which makes it able to discover more hard positives, which is better for representation learning.\n\nOn the other hand, we invite the reviewer to look at our visualizations in Figure 4 of Supplementary Material, where we have provided a visual display and comparison between the retrieved neighbors produced by local neighborhoods and ConAff neighborhoods. A case in point is shown with sports cars in Figure 4. Given a gray car, the retrieved neighbors of local neighborhoods are mostly in gray. In stark contrast, ConAff neighborhoods involve sports cars with diverse colors, which coincides with our claims. \n\n**q4: How does our method promote cross-view neighborhood consistency?**\n\nThanks for this question, the cross-view neighborhood consistency could be explained in Figure. 1(a) in an intuitive way: $t'$\n is pulled towards the ConAff neighbors of $t$ instead of $t'$  itself. Also, Eq. 14 expresses the same idea that the candidate is selected from the online network, while the neighbors of the candidate are selected from the target network. We would like to further explain that such cross-view consistency obeys the principle of instance-aware concordance, and the extraction of the ConAff neighborhood from a target network ensures a stable feature space, as the target network is updated in a momentum scheme.\n\n**q5: The potential possibility of utilization of ConAff neighborhood in generic SSL?**\n\nWe would like to agree that it is an interesting direction to explore ConAffN in generic SSL settings, while in this work our major goal is dedicated to learning a clustered and well-separated representation for deep clustering, which is self-contained through extensive experiments. Compared with deep clustering,  we would like to emphasize that self-supervised learning is still a different learning task that focuses on the efficacy of linear evaluation and transferring performance on various downstream tasks. Nevertheless, as shown in our response for **q2**, we agree with the reviewer that it is imperative to explore this possibility, which could be left as our future works."}, {"review_id": "EjJPxf7lce", "reviewer": "Reviewer_tqX4", "summary": "The paper tackles the task of deep clustering. The paper introduces a new method, Contextually affinitive Neighborhood Refinery framework (CoNR) that is based on sampling among a relevant set of samples, the contextually affinitive space named ConAff neighborhood. Specifically the method uses top-k re-ranking along with $\\alpha$-query extension to select informative neighbours. It further reduces noise among neighbours using a maximum boundary ratio, _i.e._ based on k-means clustering this ratio indicates the proximity of a sample to the cluster boundary. Finally the paper proposes a strategy to progressively relax the condition for sampling, _i.e._ the maximum boundary ratio that is acceptable. The paper validates CoNR on standard deep clustering benchmarks, _i.e._ five relatively small scale dataset: CIFAR-10/20, Imagenet-10/dogs, STL-10. The proposed method shows encouraging results against other deep-clustering state-of-the-art methods. The paper conducts ablation studies of the method on CIFAR-10, and analysis of some hyper-parameters on CIFAR-10 and Imagenet-dogs.", "questions": "Q1. Line 70: the paper defines the deep clustering task. However it is unclear to me how $k$, the number of clusters, can be set, _i.e._ it is the number of classes on the dataset which should be unknown as it is an unsupervised task. Is there another way to automatically find $k$?\n\nQ2. Eq 10: gives $\\pi’$. At the beginning of the epoch will $\\pi=\\pi’$? The paper could present studies that show the evaluation of $r_i$ during a single epoch and the different epochs.\n\nQ3. Eq 14: gives the final objective for group-aware concordance. Does $\\mathcal{N}^{(a)}(I, k)$ include $\\mathcal{B}^{(t)}$?\n\nQ4. Line 184: the paper defines $\\sigma^{(t)}$ as the boundary ratio, however the boundary ratio was defined in Eq. 11, $r_i$. Maybe $\\sigma^{(t)}$ should be referred to as the maximum boundary ratio in line 184.", "limitations": "The paper proposes a well motivated and introduced method. The experiments presented in the paper are encouraging.\n\nHowever the experiments are limited to small scale benchmarks and low complexity datasets. I believe this necessary to compare CoNR to other self-supervised methods (e.g. Dino, Emerging Properties in Self-Supervised Vision Transformers - ICCV 2021) that shines on large scale datasets.\nFurthermore the paper should compare the proposed CoNR method to the STML method from Self-taught metric learning without labels (CVPR 2022). Both methods are closely related and I believe this is necessary to validate the CoNR against the state-of-the-art. ", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "S1. The paper is well written and easy to follow.\n\nS2. The CoNR method is well motivated and each component is well introduced.\n\nS3. Experimental results are encouraging when compared to previous state-of-the-art methods for deep clustering.\n\nS4. Ablation studies are present. Ablation studies are really convincing on CIFAR-10: each element seems to participate to the final performance with non-trivial gains.\n\nS5. The paper conducts analysis on the robustness of the method with respect to some of the hyper-parameters used to train CoNR. The method seems robust to variation of hyper-parameters in wide ranges.\n\nS6. Code is present as supplementary material which will help reproducibility. Although I have not tried to use it.", "weaknesses": "W1. The paper lacks discussing a closely related paper from the unsupervised metric learning community that uses intra-batch relations and online re-ranking: Self-Taught Metric Learning without Labels, CVPR 2022. The paper should compare results with the STML method.\n \nW2. The paper should discuss relations to other self-supervised method such as ReSSL: Relational Self-Supervised Learning with Weak Augmentation (NeurIPS 2021) and With a Little Help from My Friends: Nearest-Neighbor Contrastive Learning of Visual Representations (ICCV 2021), that use relations with neighbour samples.\n\nW3. The method requires pre-training the network with another self-supervised learning method (BYOL, Bootstrap your own latent: A new approach to self-supervised Learning - NeurIPS 2020). Although this seems to be a common practice in deep-clustering, I believe this reduces the impact of the method, _e.g._ its applicability in large scale setting.\n\nW4. The paper does not conduct experiments on large scale dataset. The two largest datasets in the paper have 60k samples at most. It is not clear whether this type of method will outperform state-of-the-art self-supervised methods methods and k-means clustering on large scale datasets, _e.g._ Imagenet.\n\nW5. The experiments conducted in the paper involved relatively low complexity dataset, _i.e._ with few classes: 20 classes at most. Even though it seems to be, again, a common benchmark, this does not allow to benchmark the method and its effectiveness on complex and realistic tasks.\n\nW6. The paper reports only clustering centered metrics (ACC, NMI and ARI), the paper could also measure common metrics such as knn-accuracy to compare to other method in unsupervised representation learning.\n\nW7. The paper uses the train and test split to train and evaluate the proposed method on the different datasets. The paper should further motivate this beyond it being a common benchmark.\n\nW8: The paper should motivate the use of the 20 subclasses to evaluate CIFAR-100 beyond it being a common benchmark.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank reviewer tqX4 for the detailed comments and actionable suggestions. However, especially regarding W4&W5, we would like to kindly note that the concerns about the scalability to large-scale datasets involve a **factual error**.  Our detailed responses are listed as follows.\n\n**q1: Discussion and comparison with STML.**\n\nWe would like to add a discussion in our revised version and address our differences in setting, motivation, and technical contributions below.\n\n-  STML mainly targets image retrieval using unsupervised metric learning, which uses different benchmarks, backbones, and baseline methods for comparison.  \n\n-  STML is motivated by improving pair-wise similarity via contextual similarity in a teacher-student fashion. By contrast, our motivation is to mine more informative neighbors in ConAffN obtained from propagating a $k$-NN graph. \n\n- STML takes contextual similarity within a pair as a pseudo label, while our method utilizes the ranking statistics of ConAffN within a batch (L39-41, L140-141).\n\n- Per the reviewer's request, we try applying STML to CIFAR-10 using their provided code, as shown below, which does not generalize on our task.\n| Method | NMI | ACC | ARI |\n| --- | --- | --- | --- |\n| STML | 19.9 | 31.3 | 0.17 |\n| Ours | 86.7 | 93.2 | 86.1 |\n\n**q2: Relations to other self-supervised methods, e.g.ReSSL and NNCLR.**\n\n- We would like to highlight that ReSSL is orthogonal to our method, since:\n    - ReSSL obtains a distribution of similarities to the memory bank for each sample, while our method uses intra-batch context to obtain refined feature $h_{i}^{r}$ which is not simply the distribution of similarities but involves reciprocal relations by re-ranking.\n    - ReSSL encourages such distributions of two augmented samples to be similar, while we use the ranking statistics of refined features within a batch to find ConAff neighbors for each sample, and then encourage cross-view neighbor consistency.\n\n- NNCLR, as a pioneering work in self-supervised learning, focuses on mining the nearest neighbor in a local neighborhood, while ConNR takes a step further by mining more informative neighbors in ConAff neighborhoods and combating noises with a progressive strategy.\n\n**q3: The requirement of pre-training downgrades the impact in large-scale settings.**\n\nWe respectfully disagree that warm-up training using SSL is a drawback.\n- We did not use pre-training with extra data like ImagNet; more accurately, we utilized warm-up training, which is commonly used in deep clustering.\n- Under the warm-up design, ConNR converges quickly with pronounced gains (Figure 3 (c)), and also serves as a plug-and-play approach. We believe this, in turn, validates the efficacy of our method.\n- There doesn't seem to be a link between the warm-up strategy and scalability to large settings. In fact, our method is tested on Tiny-ImageNet, achieving state-of-the-art performance.\n\n**q4: No large-scale datasets with more than 60k samples?**\n\nWe invite the reviewer to check Table 5, Supplementary Material, where we have actually evaluated our method on a large-scale  TinyImageNet, involving **100k samples and 200 classes**. We have achieved the best-performing results on Tiny-ImageNet with **46.2 | 30.8 | 18.4** regarding NMI | ACC | ARI, surpassing the previous methods by at least 3.2% in ARI.\n\n**q5: Low-complexity datasets with no more than 20 classes?**\n\nWe actually have reported our method on Tiny-ImageNet containing 200 classes referring to our response in q4. The result table has been provided in our supplementary materials.\n\n**q6:  Lack of knn-accuracy?**\n\nThanks for your suggestion, however, none of our compared methods has evaluated knn accuracy. We kindly note that i is more often used in self-supervised learning, a different task that focuses more on downstream applications, while our goal in this paper is dedicated to clustered representations.\n\n**q7: Motivate the use of train/test splits on different benchmarks.**\n\nAs mentioned in L251, our train/test splits are completely the same with all pre-existing works [9, 17, 16, 20, 23, 24, 36, 38, 39, 40, 44, 54] for a fair comparison. Otherwise, we would not be able to report the results in Table 1.\n\n\n**q8: Motivate the use of CIFAR-20.**\n\nRegarding the use of CIFAR-20, we make a fair comparison with all pre-existing works [9, 17, 16, 20, 23, 24, 36, 38, 39, 40, 44, 54] by using 20 superclasses of CIFAR-100. Otherwise, we would not be able to report the results in Table 1.\n\n**q9: It is unclear how the cluster number K is set.**.\n\nWe respectfully note that we adhere to the standard settings used in most deep clustering works, where K is known. Even so, our method remains effective without knowing K in representation learning (Table 2), referring to our responses of q2&q3 to reviewer Prtf.\n\n**q10: Is $\\pi'$ equal to $\\pi$?**\n\nWe would like to point out there is a typo for $\\pi'$, which we have fixed in the submitted pdf. In fact, there misses a condition where $k \\neq \\pi(x_i)$ in Eq. 10, where we actually aim to locate the second nearest cluster for $x_i$.\n\n**q11: Does $N^{a}(i,k)$ include $B^{(t)}$?**\n\nWe do not exclude $B^{(t)}$ from $N^{a}(i,k)$ as our aim is to filter out unreliable candidates lying around the boundaries. For each selected candidate, we take its ConAff neighborhood as a whole to preserve its original structure.\n\n**q12: The boundary ratios**\n\nThanks for raising this concern, $r_i$ is the boundary ratio, and $\\sigma^{(t)}$ is a threshold of maximum boundary ratio at epoch $t$.\n\n**q13: About the comparison with DINO shining on large datasets**. \n\nWe respectfully note that DINO utilizes a different backbone, ViT. When using the same ViT, DINO's linear evaluation on ImageNet falls short of BYOL, as shown in Table 6, [R1]. Given our method's significant gains over BYOL on Tiny-ImageNet, we could safely believe its efficacy in large-scale settings. \n\n[R1] Self-Supervised Learning via Maximum Entropy Coding, NeurIPS, 2022."}, {"review_id": "SEnB4ZQB0X", "reviewer": "Reviewer_7yhr", "summary": "This paper improves self-supervised learning for deep clustering. The self-supervision is based on non-contrastive loss functions, which aim to reduce distance between similar samples. Previous algorithms have proposed both the instance level loss functions and group level cost functions. The current paper improves the group level cost function where the group is neighbours of an anchor sample.  The current work proposes a different way to compute neighbours of each anchor sample. It also proposes to clean the neighbours by removing samples at the cluster boundaries. A scheme to proposed to start training with samples closer to the cluster centre as neighbours and then at the later iterations allowing more noisy samples to contribute in the loss computation.  ", "questions": "The same as in Weaknesses section. Authors please respond to the points raised in the weaknesses section.", "limitations": "I don't see the proposed algorithm assumes balanced cluster sizes as authors mentioned. The main limitation may be fewer number of classes in the dataset. ", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tThis paper is well-written and easy to follow. Most of the details are fully illustrated and the ablation study is quite adequate.\n2.\tGood empirical results were reported on different clustering benchmarks.\n3.\tThe model structure is carefully designed, and the paper provides a clear explanation of each component along with their respective justifications.\n4.\tThe idea of using k-NN graph for affinitive neighbourhood discovery is simple and efficient. \n", "weaknesses": "1. Motivation of defining a graph as in Eq (3) and then message passing as in Eq (6) is completely missing. Theoretical justification and ablation study to justify both of these steps is essential for this paper.\tWhat if these steps are removed or added with existing group based method? \n\n2. Given the rapid progress in the field, the baseline BYOL used here  is outdated. Compared methods are mostly up to 2021. Many methods have been proposed in 2022 and 2023. Will the proposed steps improve a recent baseline? Also please include some recent methods in comparisons. \n\n3. There is no connection between Eqs (3)-(4) and Eqs (5)-(6). The node representations v_i are never used. Using max in Eq (11) has no advantage because by definition d^N>d^i. In Eq (10) a condition k not equal to \\pi(x_i) must be imposed.  \n\n4. In experiments, the largest dataset only contains 20 clusters. Will the proposed method be effective on datasets with more categories? Many SOTA methods have shown performance at CIFAR100, therefore authors should give performance for at least one such dataset.\n\n5.\tPlease analyse the influence of dropping the initial training with BYOL loss on performance.\n\n6.\tThe backbones are different from other baselines. Please analyse the difference of baselines and its influence on performance.\n\n7.\tHow to choose values of k1, k2 and fr? Is there any data driven scheme?\n\n8.\tIn fIgure 3b,  the performance degrades for k2=20. Please provide explanation why is this happening.\n\n9. There is no details of message passing in the paper. Value of alpha and how many message passing iterations are used? \n\n10. Also some terms like `employs an efficient online re-ranking process' and 'encourages cross-view neighborhood consistency' in the conclusion remain unexplained. Where are these terms in the methodology section?  Similarly, in the abstract, following sentence is not clear: 'However, the samples in the local neighborhood may be limited due to their close proximity to each other, which may not provide substantial and diverse supervision signals.'. Similarly following motivation is missing: `Inspired by the\nversatile re-ranking methods in the context of image retrieval'. Please improve the abstract to represent the contributions of the paper and remove redundant claims which are not materialised in the paper.   \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We really thank reviewer 7yhr for the favorable assessments and constructive suggestions. We would like to address your concerns point-by-point below.\n\n**q1: Motivation of Eq. 3 is missing. Theoretical justification and ablation of ConAff is needed.**\n\n- (**Motivations**) We would like to highlight that defining the graph in Eq (3) and message passing in Eq (6) coincides with our motivation to \"employ an efficient online re-ranking process\" for the construction of the ConAff neighborhood. \n\n-  (**Theoretical justifications**) At **step 1** (Eq. 3), the $k$-NN graph initializes node features as $k$-reciprocal embeddings, which are essential for re-ranking. Unlike traditional re-ranking, graph construction is more efficient via cuda implementation. At **step 2** (E. 6), the message propagation enables query expansion in re-ranking, spreading node features along with edge weights, also ensuring efficiency.\n\n-  (**Ablation of ConAff**) Per your suggestion, we make a component analysis of ConAffN below (in %). Also, our ablation in Table 2 shows that when ConAffN is completely replaced with the local neighborhood, the result degrades by 3.7% w.r.t. ARI, meaning that ConAffN is essential in this paper. \n| step-1 | step-2 | NMI | ACC | ARI \n| --- | --- | --- | --- | --- |\n| $\\checkmark$ | | 83.6 | 90.4 | 81.7 |\n| |$\\checkmark$ | 85.1 | 92.1 | 84.6 |\n| $\\checkmark$ | $\\checkmark$ | 86.7 | 93.2 | 86.1 |\n\n**q2: Will our method improve recent baselines? Include recent methods for comparison.**\n\n- Thanks for this suggestion, we would like to first clarify that the **plug-and-play** role of our approach has been validated on BYOL, SimSiam, and MoCo with non-trivial gains (Table 4 in Supplementary Material) and quick convergence (Fig. 3(c)). \n- We would like to justify all the above SSL frameworks are discussed within the context of instance-aware concordance, either through contrastive or non-contrastive learning, where BYOL is still the de-facto choice. A large portion of recently proposed methods that shine through the SSL field, however, is based on predictive modeling, which is beyond our current paradigm.\n- We further add a recent method DivClust [R1] to enrich our performance comparisons, which are displayed in Table 1 of our attached pdf in general response. We still achieve the best-performing results on most benchmarks.\n\n[R1] DivClust: Controlling Diversity in Deep Clustering, CVPR, 2022.\n\n\n**q3: About formulas of our method.**\n1) The $v_i$ is denoted as the node feature of the $k$-NN graph in stage-1, and then $v_i$ is used to initialize the input $h_{i}^{(0)}$ of message propagation in stage-2. \n2) We agree that $max$ in Eq. 11 could be eliminated, though we strictly followed the conventional expression of silhouette score.\n3) Many thanks for pointing out this typo, we actually aim to find the second nearest cluster in Eq. 10 so that we could detect whether a sample is located near its cluster boundary.\n\n**q4: About performance on datasets with more categories.**\n \nWe would like to highlight that the result on Tiny-ImageNet (200 classes, and 100k samples) has been provided in Table 5, Supplementary Material. Concretely, we achieved the best-performing results with 46.2 | 30.8 | 18.4 regarding NMI | ACC | ARI, surpassing the previous methods by at least 3.2% in ARI. \n\n**q5: Analysis of dropping BYOL warm-up.**\n \nWe would like to recall that ConNR, as a plug-and-play approach, needs a decent initialization for bootstrapping the cluster structure, therefore, warm-up training with BYOL is necessary. However, this does not devalue our contributions since:\n1) Warm-up pre-training is not our standalone choice, but a common practice within the existing deep clustering field. \n2) Our goal is to devise a simple and effective way to better combine the merits of instance-aware and group-aware concordance. Fortunately, we have put forward one feasible solution with non-trivial gains.\n\n**q6: Are the backbones different from other baselines?**\n We would like to highlight we follow the same setting with previous methods [9, 17, 36, 40] to ensure a fair comparison on each benchmark, which means we have made non-trivial performance gains by the proposed method, instead of some backbone tricks. \n\n**q7: How to choose parameters? Is there a data-driven scheme?**\nThanks for raising this concern. As stated in L265-267, we set fr=0.7 for all benchmarks; for all the common benchmarks, we set (k1, k2)=(10, 2); for fine-grained benchmark ImageNet-dogs, we set (k1, k2)=(30,10) as fine-grained datasets enjoy more similar semantic information in larger neighborhoods. These values are set empirically rather than in a data-driven scheme. \n\n**q8: Explanations for performance degrading at k2=20.**\nWe would like to clarify that k2 denotes the number of expanded neighbors (i.e. the neighbors of reciprocal neighbors), which should be empirically set smaller. This explains why the performance of k2=20 is inferior to k2=10, even though it still outperforms our baseline.\n\n**q9: About details of message passing.**\nWe would like to clarify that the $\\alpha$ is set to 2, and the number of layers is 2, which means the $k$-reciprocal embeddings in $A$ would be propagated twice.\n\n**q10: About claims in the abstract.**\nThanks for your suggestion, we would like to refine our claims in the abstract accordingly and address your concerns below.\n1) The motivation for \"online reranking process\" could refer to the response in q1.\n2) The cross-view neighborhood consistency could be explained in the introduction and Figure. 1(a), where t' is pulled towards the neighbors of t. This could be revealed by Eq. 8.\n3) Maximizing cosine similarity between $x_i, x_j$, which are already very close on the hypersphere, may result in limited supervision signals, shown as small losses during optimization. \n4) The motivation for re-ranking could refer to  L112-119 and L120-124. Also, versatile re-ranking methods could be viewed in L229-239 in related works.\n"}, {"review_id": "ud5nKwJY1r", "reviewer": "Reviewer_vt5R", "summary": "This paper proposes a simple yet effective method to learn class-sensitive image feature representations by exploring local neighbourhood structures, which are shown discriminative and beneficial to image clustering with the help of off-the-shelves clustering algorithms like k-means. This is achieved by mining \"rich\" (less visually redundant to the anchors) neighbours in a contextual metric space embedding high-order relations among $k$-reciprocal encoding of samples. A boundary sample detection strategy is also introduced to avoid the distractions from false positive sample pairs involved in the discovered neighbourhoods. The effectiveness of the proposed model was validated on 5 standard image clustering benchmark datasets.\n", "questions": "Given that the proposed model is trained to produce class-sensitive features of images, it will be interesting to further explore whether such discriminative features can also benefit other downstream tasks beyond image clustering", "limitations": "Yes, the authors have addressed the limitation in the conclusion section of the paper.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "+ The paper is generally well-written with clear motivations and sufficient discussions of the rationale behind each model design\n+ The proposed model is simple yet effective, which presents a new state-of-the-art for image clustering even though it doesn't explicitly learn the target cluster assignment as conventional deep clustering approaches", "weaknesses": "+ The paper is generally well-written, however, there are still rooms to improve:\n    - I'd suggest clarifying at an early stage that the outputs of the proposed model are the feature representations of images rather than their cluster assignments to one of $k$ classes (L70) given that the paper claimed to propose a ``clustering'' model, which is a bit confusing to me until the experiment section mentions that K-means is adopted.\n    - Is $h^{(0)}$ defined before it is used in Eq.(6)? I failed to find the definition and assumed it is $v_i$ in Eq.(4). Please correct me if I'm wrong.\n    - Is $r$ in Eq.(7) the same as the bounary ratio discussed in Eq.(11)?\n    - How many times the message propagation is conducted for refining the features to obtain $h^r$? \n+ Given that the key idea of the proposed model is to benefit global data structure modelling (clustering) by exploring local data structure (local neighbourhoods), such an idea is closely related to \"Unsupervised Deep Learning by Neighbourhood Discovery\" (ICML'19) and \"Unsupervised deep learning via affinity diffusion\" (AAAI'20) which are missing in the discussion.\n+ Some model designs need to be further justified\n    - The authors claimed that the proposed online boundary sample detection method is better than directly using the consistency of pseudo labels among neighbours to identify boundary labels, I'd suggest adding a simple ablation study to support this claim, e.g. replace boundary ratio with the consistency of sample's pseudo labels to its neighbours and keep all the other designs unchanged.\n    - To add a visualisation of features and highlight those boundary samples identified by the online boundary detection method (e.g. samples with a larger boundary ratio are shown as smaller dots) might be more intuitive for understanding how the data selection is conducted and why it is beneficial\n    - as the neighbourhoods are discovered according to the refined features obtained by multiple times of message propagation (Eq.(6)), it will be interesting to see whether the purity of neighbourhoods is positive correlated to the message propagation times, i.e. neighbourhood mined by $h^{(i+1)}$ is more reliable than that by $h^{(i)}$. \n    - what's the time complexity of mining contextual affinitive neighbourhood.\n    - why not test on Tiny-ImageNet which is another popular benchmark dataset for image clustering and is larger than those datasets adopted here", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank reviewer vt5R for constructive comments on improving our manuscripts, and our responses are listed point-by-point below.\n\n**q1: About clarity of the writing.**\n\n1) (**Clarifications on model outputs**) Many thanks for giving this actionable suggestion to polish our manuscripts for ease of understanding, we agree that our goal is to learn a clustered representation that better fits k-means for clustering, which is a common paradigm in deep clustering.\n2) (**Definition of  $h_{i}^{(0)}$**) You are absolutely correct that $h_{i}^{(0)}$ is defined as the feature of vertice $v_i$ constructed in the $k$-NN graph, which will be made clear in our revised version.\n3) (**The use of $r$**) The $r$ in Eq. 7 is used as a superscript to literally denote the **r**efined features, while $r_i$ in Eq. 11 simply denotes the value of the ratio. The two terms have non-overlapped meanings, and we will change the notation for better clarity.\n4) (**Message propagation times**) Since there are two identical layers in message propagation, we believe the number of iterations is 2, which will also be made clear in our revised version.\n\n**q2: Related works.**\nThanks for pointing out these papers that are worth discussing on a concrete basis. Though these papers share similar spirits using neighborhoods as tools, we would like to highlight the critical differences regarding motivation and technical contributions.\n- Our motivation goes beyond exploiting local neighborhoods since many prior works in deep clustering also have implemented this vision. Instead, our major motivation is inspired by the versatile re-ranking methods that excel in image retrieval via post-processing on evaluation sets, and apply their advantages in exploring ConAff neighborhoods in deep clustering.\n- The two mentioned works both build $k$-NN graph based on **local neighborhoods** in an **offline** manner (i.e. over the entire dataset). Specifically, for the latter work PAD, it expands the neighbor relations by searching the strongly-connected subgraphs over the whole dataset, which is orthogonal to our method. Our method, instead, explores ConAff neighborhoods via **online re-ranking** within a batch, sufficiently considering **reciprocal relations**. \n\n**q3: Model Designs.**\n1) (**Ablation of consistency of pseudo labels**) We appreciate the reviewer's insightful suggestion. Indeed, our experiments have corroborated this observation, as detailed in the ablation study below (in %). From the results, it's evident that online boundary detection (OBD) outperforms the consistency of pseudo labeling (CPL). This aligns with our observation that CPL often struggles to identify boundary samples. This is because their neighborhoods typically possess identical pseudo labels, resulting in a consistent ratio of 1, which unfortunately doesn't capture the true cluster structure.\n  | others+OBD | others+CPL | NMI | ACC | ARI|\n  | :---: | :---: | :---: | :---: | :---: |\n  | | $\\checkmark$ | 84.9 | 91.5 | 82.8 | \n  | $\\checkmark$ | | 86.7 | 93.2 | 86.1 |\n\n\n\n\n\n2) **(Visualizations)** We are grateful for the reviewer's insightful points. In response, we have incorporated the suggested visualization in the attached pdf in our general response. As can be observed in Figure 1(a), the overlapped regions of the 2D cluster boundaries predominantly consist of our identified boundary samples. To provide a more focused view, Figure 1(b) exclusively displays these detected boundary samples, effectively highlighting the contours of the clusters.\n\n\n3) **(Ablation of message propagation times)** In our implementation, the message propagation times are equal to the number of layers, which we empirically set as 2. We further evaluate the purity of ConAff neighborhoods using various numbers of layers on CIFAR-10, as shown below (in %). The result shows that message propagation refines the purity of ConAffN, and the effect is more pronounced with more propagation times. Notably, we kindly note that the quality of a neighborhood is not limited to its purity but also linked to its richness as discussed in L106-108, which affects the final performance.\n  |  num of layers| epoch | purity |\n  | :---: | :---: | :---: | \n  | 0 | 800 | 84.8 | \n  | 1 | 800 | 85.7 |\n  | 2 | 800 | 86.4 |\n\n4) (**Time Complexity**) Theoretically, the time complexity of ConAffN is $O(n^2) + O(Lk_2n) = O(n^2)$, with n representing the batch size. The constants L and k2 signify the number of layers and expanded neighbors, respectively. However, it's crucial to emphasize that our practical implementation of ConAffN is remarkably efficient. This is evidenced by the training speed comparison with BYOL presented in Table 3 of the Supplementary Material. We attribute this efficiency to the highly parallelizable computation through cuda implementation, which significantly outpaces traditional re-ranking methods.\n5) (**Why not test on Tiny-ImageNet**) We did evaluate our method on Tiny-ImageNet in the Supplementary Material. We have achieved the best-performing results on Tiny-ImageNet with **46.2 | 30.8  | 18.4**  regarding NMI | ACC | ARI, surpassing the previous methods by at least 3.2% in ARI.\n\n**q4: Downstream applications.** \n\nThanks for this valuable question, we agree that it is an interesting direction to evaluate ConAff neighborhoods from a broader perspective, hopefully benefiting other downstream tasks. At the same time, we also notice that self-supervised learning focuses more on linear evaluation performance and transferring behavior on detection and segmentation, while our current focus is dedicated to clustering, where extensive experiments (6 benchmarks) with non-trivial performance gains show that our method is self-contained for this line of research. We hope to discover more possibilities of ConAffN in our future work. We would also like to add this discussion to the Appendix.\n"}]

Author rebuttal:
# General Response:
We thank the reviewers for their careful reading of our paper, detailed comments, and the help with improving our manuscript. We sincerely appreciate that you have found our work: 
- proposes a novel framework that offers a promising solution for deep clustering (Reviewer cuTM)

- proposes really convincing (tqX4) and clearly explained (Reviewer 7yhr, tqX4) components, with adequate justifications (Reviwer 7yhr), comparisons (Prtf), and discussions of the underlying ratinoale (Reviewer vt5R).

- is simpe and effective (Reviewer cuTM, 7yhr, vt5R), enabling seamless integration into existing frameworks (Reviewer cuTM)

- ensures efficiency (Reviewer 7yhr, cuTM) for affinitive neighborhood discovery.

- establishes a new state-of-the-art for image clustering (Reviewer vt5R, 7yhr, cuTM, tqX4)

- is presented with codes to help reproducibility (Reviewer tqX4)

In the subsequent sections, we have addressed all the concerns and questions reviewers raised point-by-point during the rebuttal periods. We have also added a pdf attachment below to involve more figures targeted to specific responses.

We would appreciate it if reviewers could please have a look at our diligence and finalize their assessments, hopefully, more positively. We trust the reviewer and AC discussion would arrive at an informed and fair decision, and we would like to show our gratitude again for the valued feedback and time invested in this process.

Best,

Paper 6511 Authors


Meta-review: This paper got accept recommendation from most of the reviewers. All the reviewers agree that this paper presents a novel method with clear motivation, the experiment results also validate effectiveness of the proposed methods. Some reviewers share concerns on the scalability of the method, results on more complicated datasets. The authors provided detailed responses and addressed these questions. Most of the reviewers are satisfied with this work. AC agrees with them.
Decision: Accept (poster)