PC-X: Profound Clustering via Slow Exemplars

Authors: yuangang  pan
yinghua  yao
ivor  tsang
Venue: CPAL_cc_2024_Conference
Published: 2023-08-29 04:47:55

Abstract: Deep clustering aims at learning clustering and data representation jointly to deliver clustering-friendly representation. In spite of their significant improvements in clustering accuracy, existing approaches are far from meeting the requirements from other perspectives, such as universality, interpretability and efficiency, which become increasingly important with the emerging demand for diverse applications. We introduce a new framework named Profound Clustering via slow eXemplars (PC-X), which fulfils the above four basic requirements simultaneously. 
In particular, PC-X encodes data within the auto-encoder (AE) network to reduce its dependence on data modality (\textit{universality}). 
Further, inspired by exemplar-based clustering, we design a \PCX{Centroid-Integration Unit (CI-Unit)}, which not only facilitate the suppression of sample-specific details for better representation learning  (\textit{accuracy}), but also prompt clustering centroids to become legible exemplars (\textit{interpretability}). Further, these exemplars are calibrated stably with mini-batch data following our tailor-designed optimization scheme and converges in linear (\textit{efficiency}). Empirical results on benchmark datasets demonstrate the superiority of PC-X in terms of universality, interpretability and efficiency, in addition to clustering accuracy. The code of this work is available at https://github.com/Yuangang-Pan/PC-X/.

Main paper: 
 introduction: 
 Clustering is one of the most important techniques for exploring data structures in an unsupervised manner. The objective of clustering is to partition samples into groups such that samples in the same group are more similar than that from different groups. Naively attempting to cluster samples using raw features [1] [2] [3] may not produce pleasing partitions as semantically similar samples are not necessarily close in the high dimensional feature space [4] [5] [6] the sample resides in.Representation learning in deep learning has paved the way for obtaining a good data representation, usually of low dimensionality [7, 8] . Inspired by this, deep clustering suggests joint learning of representation and clustering within a single framework, typically via introducing a clustering loss over latent representations delivered by pre-trained models [9] or auto-encoders [10] [11] [12] . Benefiting from better data representations, these algorithms have reported significant performance gains on various benchmark datasets. Next, researchers in self-supervised learning (SSL) community take over the task and constantly refresh the state-of-the-art (SOTA) clustering records on various image datasets [5, [13] [14] [15] .Although deep learning based clustering approaches greatly facilitate the development of clustering analysis, such improvement is mainly limited to the aspect of clustering accuracy. Meanwhile, the development of clustering approaches in other aspects, e.g., universality, interpretability and efficiency, has remained stagnant or been degenerate over the past few years. Particularly, despite keeping the best records on many images datasets, clustering approaches based on SSL highly depend on the choice of invariant transformations and degenerate significantly if effective transformations are not available, like text data [5, 14] . Furthermore, jointly optimizing representation learning and clustering may incur efficiency concerns, since a large/full batch data is usually required to update the clustering structure for sake of stability [16] [17] [18] . Last but not least, most deep clustering algo-rithms are deemed as black-box with less interpretability, as their criteria for clustering is unknown, which may not be consistent with samples' semantics, and even beyond human understanding [19] .In this paper, we design a new end-to-end framework called Profound Clustering via slow eXemplars (PC-X), which is inherent interpretable and universally applicable to various types of largescale datasets. To be specific, instead of adding the clustering module on top of latent representation, PC-X incorporates it within the AE network via the proposed Centroid-Integration Unit (CI-Unit), which suppresses (clustering nonrelevant) sample-specific details and facilitates clustering centroids to become a set of exemplars through decoding. Regarding the inference, we decompose the optimization of representation learning and clustering into two sub-tasks by introducing an auxiliary variable. Given the representation learning, the exemplars, i.e., clustering centroids, can be calibrated slowly with exponential moving average; while given the exemplars, the representation of each sample gradually gathers around its respective clustering centroid through stochastic gradient optimization. In summary, the main contributions of this paper are summarized as follows:• We introduce a new clustering framework (PC-X), which is inherent interpretable and universally applicable to various types of datasets. Extensive experiments on seven benchmark datasets demonstrates that PC-X outperforms existing clustering methods from four aspects, including clustering accuracy, universality, interpretability and efficiency.• We introduce a new module call Centroid-Integration Unit, which not only helps to suppress (clustering nonrelevant) sample-specific details in the latent embedding, but also facilitates clustering centroids to become legible exemplars through decoding.• We design an efficient optimization algorithm for PC-X, which updates all parameters in PC-X stably with mini-batch data, and enjoys superior convergence as well as algorithm complexity. 
problem statement and literature review: 
 In this section, we first introduce the problem setting of clustering. Then, we summarize classical clustering as well as deep clustering methods, and discuss their deficiencies accordingly.Let X = {x n } N n=1 be a set of N samples in R D , drawn from heterogeneous populations. Assume the cluster number of is known to be K(≪ N ). The goal of clustering is to partition X into K non-overlap groups S = (S 1 , S 2 , . . . , S K ) with low intra-class variance but high inter-class variance.The following four challenges should be reckoned when designing the clustering algorithm, namely• Accuracy is the primary target. The designed algorithm is expected to partition samples according to the intrinsic semantic differences within the data. A good clustering algorithm should achieve consistent superior performances in terms of various clustering measures.• Universality requires the clustering method is generally applicable to various types of data, e.g., image or text. While adapting the network architectures is necessary for different modalities, "universality" lies in the way that the method accommodates these architectures and can be effectively adapted to specific modalities based on a minimum knowledge of target data.• Interpretability pertains to whether the criteria followed by clustering are easily interpretable for users. We argue that AE/DGM-based clustering methods inherently possess interpretability for their clustering results. Through the decoder, the clustering centroids can be mapped to the data space, allowing for the visualization of the clustering semantics (Fig. 2 ).• Efficiency means that the algorithms have low memory space and low computational costs. Typically, updating deep clustering models stably requires large batch data, which is memoryinefficient for large-scale applications. Further, those methods also suffer from slow convergence due to a lack of proper joint optimization schemes. Existing clustering methods can be roughly categorized into classical clustering and deep clustering; while deep clustering can be further divided into three branches in terms of the ways how they combine clustering and representation learning. See Table 1 for a summary of comparisons.Classical clustering generally refers to the algorithms that group samples in the raw feature space. This kind of approaches are easy to interpretable and efficient. However, they are applied to limited types of data with well-defined features. In terms of complex data (e.g., image), it fails to achieve good results since semantically similar samples are not necessarily close in the raw feature space.Deep clustering based on pre-trained model generalizes classical clustering for complex data through executing clustering modules over latent representations delivered by pre-trained CNNs or AEs. In spite of its simplicity, it is highly dependent on the original latent embedding due to the lack of joint training of representation and clustering. As a consequence, differential clustering losses are derived in DEC [16] and Deepcluster [9] to fine-tune the pre-trained model.propose to jointly train clustering modules with extra tasks, such as self-reconstruction or distribution matching [18] [19] [20] [21] [22] . It is shown to exhibit robustness to poor initial latent embedding since they can keep the diversity in latent space via reconstructing/generating the input samples. Prominent works are JULE [17] , IDEC [20] , VaDE [23] and DEPICT [18] . Nevertheless, the reconstruction loss tends to overestimate sample-specific details (e.g. textures and background) which are unrelated to semantics [24] , degrading clustering performance. Meanwhile, it is memory inefficient for large-scale applications, since multiple iterations over the whole dataset are required for joint updating the clustering structure and network parameters reliably [17, 18, 20] .Deep clustering based on self-supervised learning (SSL), e.g., TCC [25] and DivClust [26] , achieve SOTA clustering results on various image datasets. As semantics pairs are constructed for each sample through a collection of predefined semantics-invariant transformations, the performance of SSL-based clustering methods highly depends on the choice of invariant transformations, which requires rich domain knowledge and varies from dataset to dataset [27] [28] [29] [30] [31] [32] [33] [34] . If no effective invariant transformations are available, their performance would degenerate significantly. Meanwhile, lack of informative gradient, SSL-based approaches usually suffer from slow convergence [5] .Last but not least, despite significant performance gains based on representation learning, the clustering process of deep clustering is less interpretable as the criteria used for clustering are unknown, which may not be consistent with samples' semantics, and even out of human understanding. 
profound clustering via slow exemplars: 
 Taking into consideration the weakness of existing clustering approaches, we are committed to introducing a profound clustering framework that can achieve superior performance in terms of four challenges stated in Section 2 simultaneously.Universality. According to Table 1 , we choose deep AE as the backbone to reduce the dependence on the data modality. Let f θ and g ϕ denote the encoder and decoder, respectively. We adopt soft k-means to perform clustering in the latent space for the sake of efficiency. The objective of PC-X is summarized as follows:EQUATIONwhere z n = f θ (x n ) denotes the latent embedding. D(.∥.) is the reconstruction loss. ∆ = {θ, ϕ} stands for network parameters. η 1 is the balance factor. The intermediate variable δ nk ∈ {0, 1} denotes the group assignment, assigning each latent code z n to its closest clustering centroid, i.e.,EQUATIONwhere k = 1, 2, . . . , K and n = 1, 2, . . . , N . It was claimed that encouraging the diversity among clustering centroids contributes to a stable clustering process [35, 36] . We therefore add an extra minimum entropy (ME) regularization term in Eq. ( 1), i.e., L M E (∆) = -1 N N n=1 K k=1 λ nk log λ nk to promote clustering stability. Note L M E is optimized only for the network parameters (∆) which will not cause extra optimization difficulty. A burn-in period (#epoch ≤ 250) is introduced for the ME regularization since the estimation is less informative initially. See Fig. 4 for its effects on PC-X.In AE/DGM-based clustering, the latent representations z n inevitably contain sample-specific details due to self-reconstruction, which is detrimental to clustering [24] . We argue that this is lack of the insight of clustering centroids since the clustering centroids have never been fully utilized during the reconstruction. Specifically, we introduce the Centroid-Integration Unit (CI-Unit) (shown in Fig. 1 ) to incorporate the centroids into the training of AE/DGM.fusion Centroid-Integration: The CI-Unit constructs a new latent representation ẑn that incorporates not only the original latent embedding z n but also its closest clustering centroid zn . For simplicity, we implement h ψ by simple concatenation along with one extra fully connection layer.Accuracy. Our CI-Unit unifies both goals of clustering and reconstruction. This is because the variable µ should be the group-shared features if it can be incorporated to latent representation of each sample assigned to the same cluster for good reconstruction. As a result, the subsequently selfreconstruction using the centroid-enhanced representation ẑn facilitates the suppression of samplespecific details in z n , bringing a mutually reinforcing effect between accurate clustering centroid estimation and better self reconstruction. See A.6 for a comprehensive demonstration.Interpretability. PC-X with CI-Unit possesses similar merits as exemplar-based clustering which minimizes a similar k-means objective, i.e., L(µ) = 1 N N n=1 K k=1 δ nk D(x n ∥µ k ), but restricts cluster centers (aka exemplars) to be chosen from training data (i.e., µ ⊆ X), and thus owns inherent interpretability [37] . Similarly, the reconstruction of our clustering centroids g ϕ (h ψ (µ, µ)) would be enhanced to be legible exemplars since (1) each centroid-enhanced representation h ψ (f θ (x), µ) 1 is legitimately decoded to its respectively input x during the whole training process (the reconstruction loss), i.e., g ϕ (h ψ (f θ (x), µ)) → x; and (2) each latent representation is pushed close to its corresponding clustering centroid, i.e., f θ (x) → µ (the clustering loss).Efficiency. In Eq. ( 1), two types of parameters, i.e., network parameters ∆ and clustering parameters µ, are coupled together which hinders them from jointly optimizing. Different from network parameters ∆, the update of centroids µ is unstable when optimized with stochastic gradient. This is because the centroids estimated on different mini-batches may differ markedly. In addition, when the centroids are estimated through standard full-batch iterations, it would lead to significant computational cost and storage overhead, especially for large-scale applications. Therefore, we propose to slowly calibrate the reserved centroids (i.e., exemplars) using mini-batch data instead of replacing them with the new estimations, which thus enjoys both stability and efficiency.In this section, we propose a decomposition-coordination optimization method following the principle of alternating direction method of multipliers [38] . To be specific, we decompose the optimization regarding two types of parameters through introducing an auxiliary variable c. Namely,EQUATIONwhere the penalty parameter ρ denotes the level of model robustness against the mini-batch update.Accordingly, our decomposition-coordination optimization method consists of the three iterations:∆ t+1 = argmin ∆ L ∆, c t , µ t , c t+1 = argmin c L ∆ t+1 , c, µ t , µ t+1 = argmin µ L ∆ t+1 , c t+1 , µ .where t is the index of epoch.We then derive efficient update solutions for each subproblem, enabling stochastic update.In terms of ∆, the reduced subproblem is a three objective optimization problem L P C-X (∆, c t ) (set µ to c t in Eq. ( 1)). Since no closed-form solution exists, we optimize it with gradient descent,EQUATION)where γ is the step size. Eq. ( 5) can be implemented with advanced gradient descent approaches.In terms of c, the subproblem is a two-objective optimization problem. By setting the gradient of the objective to zeros, we can get an analytic solution.EQUATIONLet K , where the auxiliary variable c pursues a balance between the exiting centroid µ t and the re-estimated one μt . Eq. ( 6) actually is equivalent to the well-known exponential moving average (EMA).κ = ρ ρ+ η 1 N N n=1 δ nk and μt k = N n=1 δ nk zn N n=1 δ nk , we have c t+1 k = κµ t k + (1 -κ)μ t k , k = 1, 2, . . . ,In terms of µ, the reduced subproblem consists of the second item in Eq. (4) . By setting the gradient of the objective to zeros, we can get an analytic solution, i.e.,EQUATIONAlthough all the update solutions are formulated in terms of full batch update, it can be easily extended to stochastic update using mini-batch data. To be specific, the update solution (Eq. ( 5)) of the network parameters ∆ naturally accepts mini-batch update for stochastic gradient optimization. Meanwhile, c are gradually updated following EMA. Previous literature demonstrates that EMA possesses good stability and efficiency in the scenario of the mini-batch update [39] . Therefore, our PC-X can deal with large-scale clustering problems.Our decomposition-coordination optimization method falls into the scope of the batch block optimization framework [40] . In the following, we give the definition of Lipschitz smoothness, strong convexity and bounded gradients, which are standard for convex stochastic optimization [41, 42] .Definition 1 (L-Lipschitz smooth) A differentiable function f : R n → R is said to be L-smooth if ∀x, y ∈ R n , we have ∥∇f (x) -∇f (y)∥ ≤ L∥x -y∥.Definition 2 (u-Strong convexity) A function f : R n → R is said to be is u-strongly convex for some u > 0, which means that ∀x, y ∈ R n , we havef (x) ≥ f (y) + ⟨∇f (y), y -x⟩ + u 2 ∥y -x∥ 2 .Definition 3 (Bounded gradients) If the gradients ∇f (x) of the objective function f (x) are upper bounded by G, it means that ∥∇f(x)∥ 2 ≤ G, ∀x ∈ R n .Lemma 1 (Quadratic upper bounds [43] ) If the differentiable objective function L(∆, c, µ) in Eq. ( 4)is partial L-Lipschitz smooth to the network parameters ∆, i.e., ∀∆ 1 , ∆ 2 ∈ R |∆| , ∂L(∆,c,µ) ∂∆ ∆=∆1 - ∂L(∆,c,µ) ∂∆ ∆=∆2 ≤ L ∥∆ 1 -∆ 2 ∥.Then, we can derive the following quadratic upper bounds:L (∆ 1 , c, µ) ≤ L (∆ 2 , c, µ) + ∂L(∆,c,µ) ∂∆ ∆=∆2 , ∆ 1 -∆ 2 + L 2 ∥∆ 1 -∆ 2 ∥ 2 .Lemma 2 (Convexity upper bounds) If the objective function L(∆, c, µ) in Eq. ( 4) satisfies the partially u-strongly convex w.r.t. the network parameter ∆ for some u > 0, i.e., ∀∆ 1 ,∆ 2 ∈ R |∆| , L(∆ 2 , c, µ) ≥ L(∆ 1 , c, µ)+ ∂L(∆,c,µ) ∂∆ ∆=∆1 , ∆ 1 -∆ 2 + u 2 ∆ 1 -∆ 2 2. Then, we have:EQUATION, which simply applies the optimal value of the quadratic function.It is too strong to assume the objective function of a deep neural network is Lipschitz continuity and strongly convex w.r.t. the network parameter ∆, while it is reasonable to assume it is Lipschitz continuity and strongly convex around a neighborhood of a local optima. Meanwhile, the two supproblems w.r.t. c, µ are global convex with closed form solutions (See Eq. ( 6) and Eq. ( 7)).Theorem 1 (Linear Convergence) Assume the objective L(∆, c, µ) in Eq. (4) satisfies the assumptions of partial Lipschitz smooth, u-strong convexity and bounded gradients w.r.t. the network parameter ∆ around a neighborhood of (∆ * , c * , µ * ), which is a local optimal solution of the objective function L(∆, c, µ) in expectation. Our algorithm converges linearly to optimal value (∆ * , c * , µ * ) with a step-size γ,i.e., E [L(∆ t , c t , µ t ) -L(∆ * , c * , µ * )] ≤ (1 -2uγ) t E L(∆ 0 , c 0 , µ 0 ) -L(∆ * , c * , µ * ) + γLG 4u, where (∆ t , c t , µ t ) is the solution at t-th iteration. The expectation is taken w.r.t. the stochastic mini-batch data.According to our analysis in Theorem 1, as long as we set an appropriate learning rate γ where 0 < γ < 1 2u , the objective function Eq. ( 4) will converge linearly.Table 2 : Algorithm complexity of the clustering module Baseline VaDE [23] IDEC [20] DEPICT [18] PC-XTime O(M N Kd 2 ) O(M N Kd) O(M N Kd) O(M N Kd) Space O((B + 2K)d + K) O((N + K)d) O((N + K)d) O((B + K)d)We analyze the time and space complexity of our PC-X and popular AE/DGM-based deep clustering methods, i.e., VaDE, IDEC and DEPICT, in Table 2 . Let M , N , B, K and d denote the number of epochs, the whole sample size, the mini-batch size, the cluster number and latent feature dimension, respectively. Assuming all of them adopt the same AE network architecture, we only analyze the extra time and space cost incurred by the clustering module.From Table 2 , we can find that: (1) since IDEC, DEPICT and our PC-X perform k-means clustering, they have the same extra time complexity. (2) Both IDEC and DEPICT are based on DEC [16] but differ in their AE structure. Therefore, their clustering modules incur the same algorithm complexity. Compared to our PC-X using mini-batch (B) samples, IDEC and DEPICT are not memory efficient, since both of them need to repeatedly update the target probability with full batch (N ≫ B) samples.(3) VaDE performs Gaussian Mixture Models (GMM) clustering with a diagonal variance matrix, resulting in a larger time complexity than our PC-X. It also updates the clustering module with mini-batch samples, but has an additional space cost O(Kd + K) for the diagonal variance matrix and the prior probability. In this section, we conduct experiments on seven benchmark datasets to demonstrate the superiority of our PC-X in terms of clustering accuracy, universality, efficiency, and interpretability, respectively. The statistics of datasets are introduced in Table 3 . 
empirical experiment: 
 For the imbalanced datasets YTF and Reteurs10K, we apply a re-weighted clustering loss (See A.3).We compare our PC-X2 with i) two classical clustering approaches: k-means [50] and GMM [51] ; ii) two pretrained model based deep clustering methods: AE [10] and DEC [16] ; iii) three AE/DGM based deep clustering methods: VaDE [23] , IDEC [20] and DEPICT [18] ; iv) six SSL-based deep clustering methods: IIC [5] , PICA [14] , CC [34] , SPICE3 [15] , TCC [25] and DivClust [26] . Inspired by SSL-based clustering methods [15, 31] , we use MoCo [52] to extract features for CIFAR-10 and ImageNet-10 considering their complexity, and evaluated all non-SSL-based baselines (including our PC-X) on the extracted features. Like SSL-based baselines, these feature extractors do not utilize any supervision regarding the datasets. For all methods, we set the number of clusters to the ground truth categories and evaluate performance with three clustering metrics: Accuracy (ACC), Normalized Mutual Information (NMI) and Adjusted Rand Index (ARI). We demonstrate the superiority of PC-X on datasets with various data types. As SSL-based methods were proposed for complex image datasets, we applied them only on ImageNet-10 and CIFAR-10.Table 4 shows that: (1) PC-X consistently achieves superiority clustering accuracy than AE/DGMbased baselines on various datasets, this is because our CI-Unit can suppress sample-specific details, on Fashion and Reuters10K, due to their failure to reconcile both goals of self-reconstruction and clustering.Table 5 shows that PC-X can achieve higher or comparable clustering accuracy over SSL-based deep clustering methods on complex image datasets through a better feature extractor. It ascribes the success of SOTA SSL-based deep clustering methods to a better feature extractor instead of their respectively complex but less interpretable clustering modules. Back to universality, our PC-X is more advantageous than SSL-based clustering baselines due to its ability in handling non-image datasets, e.g., Reuters10K (text) and HAR (signal).We visualize the latent embedding and the corresponding centroids on MNIST to showcase the interpretability of PC-X in Fig. 2 . Additionally, we compare our visual results with IDEC, whose model is almost the same as our PC-X but lacks the CI-Unit.It is notable that the centroids reconstruction of our PC-X are exactly the realistic images (Fig. 2b ), which indicates PC-X captures legible exemplars and performs semantic clustering in the latent space. Regarding IDEC (Fig. 2c, 2d ), the embedding of some categories are mixed, causing redundancy centroid reconstructions, i.e., digit 9, and incomplete identified categories, i.e., digit 4. This is because its self-reconstruction loss, which doesn't take clustering centroids into account, contains too many sample-specific details. The clustering results are distracted by similar digits, i.e., 4 and 9. This observation also emphasizes the importance of interpretability. Well-separated embedding in the latent space (Fig. 2c ) does not guarantee semantically meaningful clustering results (Fig. 2d ). In Fig. 3 , we collect the clustering accuracy of PC-X on mini-batch (PC-X-mini)/ full-batch (PC-X) of MNIST/Fashion as well as the clustering accuracy of other popular clustering methods [53] , e.g., k-means, GMM and hierarchical agglomerative clustering (AGG) [54] , respectively.Fig. 3 verifies that: (1) PC-X converges fast (epoch < 100) on both two datasets and continue to improve gradually later, which benefits from our efficient joint optimization scheme. ( 2) The clustering accuracy of PC-X on mini-batch (PC-X-mini) keeps align with that of full-batch (PC-X) and k-means during the whole clustering process, which demonstrates the superiority of our slow exemplars cal-ibration strategy. (3) PC-X delivers clustering-friendly (i.e., well-separated) feature representations since PC-X achieves a similar clustering accuracy as classical shallow clustering methods, especially hierarchical clustering method AGG. Meanwhile, it justifies our choice that simple k-means is sufficient for clustering in a clustering-friendly latent space we deliver.To further demonstrate the efficiency of our PC-X on the large-scale dataset, we evaluate it on the entire ImageNet dataset with 1,000 clusters and 1,281,167 samples. Similarly, we apply MoCo [52] to extract features for ImageNet before performing PC-X. We compare different variants of PC-X with most related baselines, i.e., IDEC and AE, to analyze the efficacy of different components in PC-X. Different strategies for updating the centroids are studied. "PC-X-no CI" denotes PC-X without the CI-Unit; "PC-X-Fix" denotes the centroids are fixed after initialization.Table . 6 summarizes the clustering accuracy (i.e., ACC and NMI) of PC-X and its variants. It shows that (1) PC-X with all components can achieves the best results over other baselines, which demonstrates the efficacy of our CI-Unit and joint optimization strategy. ( 2) Without a proper strategy, two variants of PC-X, i.e., "PC-X-no CI" and "PC-X-Fix", drops significantly, since they fail to reconcile the conflicts between the goal of self-reconstruction and clustering, or the optimization between the network parameters and the clustering centroids, respectively. 2) After a burn-in period (#epoch ≤ 250), both two losses remain stable, and the average group assignment levels off. (3) After we activate ME regularization, the average group assignment keeps rising to nearly one; while the reconstruction loss remains stable and the clustering loss slightly increases. It means the ME regularization helps to distill a well-separate latent structure and improve the clustering stability. 
conclusion: 
 This paper presents profound clustering via slow exemplar (PC-X), which casts an interpretable clustering framework for large-scale applications. It fosters a set of legible exemplars for clustering in the latent space without accessing the full-batch data concurrently. Since PC-X conducts clustering based on the similarity in the latent space, the clustering performance is affected by the choice of the AE network. Extra constraints [55, 56] can be introduced to facilitate a semantics-consistent latent embedding, so as to reduce reliance on network structure. Meanwhile, PC-X's reliance on non-convex k-means may impact its performance. Investigating the integration of other differential clustering losses could yield a more robust clustering methodology. Further, our PC-X paradigm inspires a stable and efficient way of Bayesian inference to stitch deep networks with complex Bayesian models. In the future, we will extend PC-X for non-parametric Bayes and hierarchical models. 
 
 Appendix: A.1. Network structure of our profound Clustering (PC-X) Fig. 5 shows the whole structure of our Profound Clustering (PC-X), which encodes the clustering module into the auto-encoder network, which is an inherently interpretable clustering framework and universally applicable for complex data.It was claimed that adding diversification constraints to encourage the diversity among clustering centroids, which was found to yield better clustering performance (e.g., [35, 36] ). However, such repulsive regularization terms are inherently highly non-convex, adding them into the objective [57] . Inspired by these, we add a minimum entropy (ME) regularization over the soft group assignment λ nk as follows:EQUATIONwhere {λ nk } N,M n=1,k=1 is the intermediate variable calculated via Eq. ( 2). Note Eq. ( 8) is optimized only for the network parameters to avoid instability which will not cause extra optimization difficulty.Ideally, when Eq. ( 8) achieves optima, the soft assignment should be nearly the same as the corresponding hard assignment, i.e., λ nk → δ nk . It means that the distance of a sample to its closest centroid should be much smaller than other centroids, denoting the latent embedding is well-separated as desired. This method shares a similar spirit with the sharpening technique [58] used in DEC [16] and its derivatives [18, 20] , but minimum entropy is calculated at the sample level which is superior in large-scale applications using mini-batch update. Therefore, we summarize the objective of our PC-X with skip-connection as follows:EQUATIONwhere z n = f θ (x n ). zn denotes the closest clustering centroid µ {argmax j λnj } of the latent embedding z n according to Eq. ( 3). ∆ = {θ, φ, ϕ} stands for network parameters for both auto-encoder and skip-connection. η 1 , η 2 are the trade-off parameters.It is noted that all three losses are calculated per sample, implying that PC-X-Div supports stochastic optimization using mini-batch data as well.Vanilla clustering loss does not take into consideration the scenario of imbalanced clustering. Thus, it would suffer from inferior clustering performance when clustering size is imbalanced. Because the major clustering will dominate the clustering loss, causing the minor cluster to be less explored.Let α = [α 1 , α 2 , . . . , α K ] denote the clustering size, and we defineEQUATIONwhere ᾱ denotes the average clustering size.Then, we rearrange the clustering loss as follows,EQUATIONwhere 1 is valid by swapping the order of the two summarization operators. 2 is because the existence of the hard assignment δ nk ∈ {0, 1} where the summarization is actually taken over the samples assigned the cluster S k . 3 is because 1 4 is according to Eq. ( 10). The vanilla clustering loss (Eq. ( 11)) is actually a weighted summarization of inter-cluster variance, which places a higher weight for a larger cluster, i.e., Kα k N = α k ᾱ > 1, and vice versa. ᾱ denotes the average clustering size. We argue that this term can be removed, especially for clustering with imbalanced data. Particularly, the new clustering loss will no longer bias towards major clusters and ensure good clustering performance in imbalanced data clustering.N = 1 K × Kα k N × 1 α k .Reweighting with inverse clustering size. The cluster assignment is exactly what we target for, which unfortunately is not available before training. Although it can be estimated during clustering, it is never the optima before converging. Since it cannot be removed directly, we consider weakening the effect of this term in the clustering loss. Compared with the (sample-level) cluster assignment, the (cluster-level) clustering size can be estimated more reliable and accurate during the clustering process, we therefore reweight the clustering loss with inverse clustering size to lend an ear to small clusters. To be specific,L reweight-cluster (µ) = 1 N N n=1 1 ω k K k=1 δ nk ∥z n -µ k ∥ 2 2 1 = 1 K K k=1 1 α k x∈S k ∥f θ (x) -µ k ∥ 2 2 Inter-cluster V ariance, where 1 is derived following Eq. (11) .To sum up, we introduce the PC-X-IMBA tailor-designed for clustering imbalanced data based the cluster-lever reweight in the following,EQUATIONCompared with PC-X, PC-X-IMBA is superior for clustering imbalanceddata because• In terms of balance data, i.e., α 1 ≈ . . . ≈ α K ≈ ᾱ, we have ω k ≈ 1. PC-X-IMBA degenerates to PC-X. Meanwhile, for an average cluster in the imbalanced dataset, i.e., α k ≈ ᾱ and ω k ≈ 1 which means no extra action required.• In terms of a minority cluster α k < ᾱ in the imbalance dataset, we have 1 ω k = ᾱ α k > 1 which gives a higher weight to the sample assigned to a minority cluster.• In terms of a major cluster α k > ᾱ in the imbalance dataset, we have 1 ω k = ᾱ α k < 1 which gives a lower weight to the sample assigned to a major cluster.Inspired by the EMA estimation for the clustering centroids, we suggest estimating the cluster size α = [α 1 , α 2 , . . . , α K ] on the fly as well. Similarly, α is online calibrated at each iteration as follow:EQUATIONAlgorithm 1 Decomposition-coordination optimization update clustering centroids µ by Eq. ( 7).11:To ensure stability, we further adopt Laplace smoothing to smooth clustering size. Namely,EQUATIONwhere the pseudo count ϵ > 0 is the smoothing parameter. In the real experiment, ϵ is set to a small value (≈ 1 × 10 -5 ) for a balance clustering scenario and a large value (≈ 5) for an imbalanced data clustering scenario.A burn-in period is introduced for the minimum entropy regularization (Eq. ( 8)) and imbalanced data clustering PC-X-IMBA (Eq. ( 12)) since the estimation is less informative initially. Namely, during the initial period (#epoch ≤ 250) of the training epochs, η 2 = 0 and ω k = 1 when the clustering module is not properly learned.By setting the gradient of the objective to zeros, we can get an analytic solution.∂L ∆ t+1 , c, µ t ∂c k = 0, k = 1, 2, . . . , K.EQUATIONwhere k = 1, 2, . . . , K.Therefore, we letEQUATIONA.5. Proof for Theorem 1 L(∆ t , c t , µ t ) -L(∆ * , c * , µ * ) ≤ (1 -2uγ) t E L(∆ 0 , c 0 , µ 0 ) -L(∆ * , c * , µ * ) + γLG 4u ,where (∆ t , c t , µ t ) is the solution at t-th iteration over mini-batch B t . The expectation is taken with regard to the stochastic mini-batch data.Proof: Give a mini-batch dataset B t , according to our decomposition-coordination optimization, we have thatEQUATIONwhere 1 is valid according to the definition of subproblem in Eq. ( 7). 2 is because of the definition of subproblem Eq. ( 6).Meanwhile, since∆ t+1 = ∆ t -γ ∂L(∆,c t ,µ t ) ∂∆ B t ∆=∆ t4 according to Eq. ( 5), we haveL(∆ t+1 ,c t , µ t ) -L(∆ t , c t , µ t ) 1 ≤ L (∆, c t , µ t ) ∂∆ ∆=∆ t , ∆ t+1 -∆ t + L 2 ∥∆ t+1 -∆ t ∥ 2 2 = -γ L (∆, c t , µ t ) ∂∆ ∆=∆ t , ∂L (∆, c t , µ t ) ∂∆ B t ∆=∆ t + γ 2 L 2 ∂L (∆, c t , µ t ) ∂∆ B t ∆=∆ t 2 3 ≤ -γ L (∆, c t , µ t ) ∂∆ ∆=∆ t , ∂L (∆, c t , µ t ) ∂∆ B t ∆=∆ t + γ 2LG 2where 1 follows Lemma 1, 2 is valid because the substitution using the stochastic gradient update. 3 applies the bounded gradient.Subtracting optimal objective value L(∆ * , c * , µ * ) and then taking expectation on both sides w.r.t. mini-batch B t , we have,E L(∆ t+1 , c t , µ t ) -L(∆ * , c * , µ * ) -E L(∆ t , c t , µ t ) -L(∆ * , c * , µ * ) 1 ≤ -γ L (∆, c t , µ t ) ∂∆ ∆=∆ t , E ∂L (∆, c t , µ t ) ∂∆ B t ∆=∆ t + γ 2 LG 2 = -γE ∂L (∆, c t , µ t ) ∂∆ ∆=∆ t 2 + γ 2 LG 2 2 ≤ -2uγE L(∆ t , c t , µ t ) -L(∆ * , c * , µ * ) + γ 2 LG 2 =⇒ E L(∆ t+1 , c t , µ t ) -L(∆ * , c * , µ * ) ≤ (1 -2uγ)E L(∆ t , c t , µ t ) -L(∆ * , c * , µ * ) + γ 2 LG 2 3 =⇒ E L(∆ t+1 , c t+1 , µ t+1 ) -L(∆ * , c * , µ * ) ≤ (1 -2uγ)E L(∆ t , c t , µ t ) -L(∆ * , c * , µ * ) + γ 2LG 2where 1 is valid under the assumption of bounded gradients. 2 is derived following Lemma 2 under the assumption of the u-strong convexity. 3 follows the inequality in Eq. ( 17). Applying this inequality recursively, we obtainE L(∆ t , c t , µ t ) -L(∆ * , c * , µ * ) ≤ (1 -2uγ) t E L(∆ 0 , c 0 , µ 0 ) -L(∆ * , c * , µ * ) + t i=1 (1 -2uγ) (i-1) γ 2 LG 2 1 ≤ (1 -2uγ) t E L(∆ 0 , c 0 , µ 0 ) -L(∆ * , c * , µ * ) + 1 2uγ × γ 2 LG 2 = (1 -2uγ) t E L(∆ 0 , c 0 , µ 0 ) -L(∆ * , c * , µ * ) + γLG 4u ,where 1 is valid becauset i=0 r i ≤ ∞ i=0 r i = 1 1-r , ∀0 < r < 1.The fusion layer reconciles the goals of clustering and self-reconstruction, ensuring that the feature representation before fusion is suitable for clustering, while that after fusion is suitable for reconstruction. The following two experiments on MNIST verify the above claim:1. We visualized the feature representation before (i.e., z as adopted in the experiment) and after (i.e., ẑ) the fusion layer simultaneously in Fig. 6 . It shows that each cluster of the former is more compact compared to that of the latter (prefixed with 'f'), indicating that the fusion layer reduces the proportion of clustering-related information in the feature representation.2. For each cluster, we calculated the singular values and singular vectors of the feature representation before and after the fusion layer. We found that the singular vector corresponding to the largest singular value is highly correlated to its corresponding cluster centroid. However, the proportion of the largest singular value among all singular values decreases a lot after the fusion step, as shown below. This indicates that the representation after fusion is less compacted and contains more sample specific details. Experiment Settings: We implement PC-X with PyTorch [59] .• In terms of MNIST, Reuters10K, HAR, CIFAR-10 and ImageNet-10 5 , PC-X is built upon the AE architecture described in [16] . The encoder is a fully connected multi-layer perceptron (MLP) with dimensions D-500-500-2000-d. D is the dimension of input and d is the dimension of centroids. All layers use ReLU activation [60] except the last.• In terms of YTF and Fashion, we adopt a convolution neural network introduced in [19] . Specifically, the encoder consists of four convolutional layers conv(16, 3, 1, 1)-conv(32, 3, 2, 1)-conv(32, 3, 1, 1)-conv(16, 3, 2, 1) followed by a two-layer MLP with dimensions D-256-d, where conv(16, 3, 1, 1) denotes a convolutional layer with channel number 16, kernel size 3, stride length 1, and padding size 1. D is the dimension of the flattened CNN output and d is the dimension of centroids. We apply batch normalization after each convolutional layer, followed by the ReLU activation except the last.The decoder is mirrored of the encoder. For all datasets, the dimension of centroids is fixed to 10. The optimizer is Adam [61] . All neural network weight, as well as the clustering centroids, are initialized using a uniform distribution following [62] . The learning rate is 5×10 -4 and the training epoch is 1, 000. The batch size is set to 256. τ (Eq.( 2)) and κ (Eq. ( 6)) is set to 5 and 0.995. Metric: we list the formulation of three clustering metrics, i.e., ACC, NMI and ARI, in the following:• Accuracy (ACC): For sample i, let R i denote its ground truth label and C i be its label obtained by clustering.ACC = N n=1 δ(R n , C n ) N × 100%,where δ(x, y) equals one if x = y, and zero otherwise. N denotes the number of samples.• Normalized mutual information (NMI): Let R denote the ground truth label and C be the label obtained by clustering. The NMI is defined as follows:N M I = 2M I(R, C) H(R) + H(C) ,where H(X) is the entropy of X, and M I(X, Y ) is the mutual information of X and Y .• Adjusted rand index (NMI): Let D ∈ R K×K denote the contingency table between the ground truth label R and the label C obtained by clustering. The ARI is defined as follows: For all three metrics, values range between 0 and 1, where higher value indicates better performance. 5 we apply PC-X on the extracted features of CIFAR10 and ImageNet-10.ARI = ij Dij 2 - i Ai 2 j Bj 2 / NFirst Conference on Parsimony and Learning (CPAL 2024).µ refers to the closest clustering centroid of x, we omit the downscripts here for simplicity.For all baselines, results were retrieved from the literature or computed by us when not found. Algorithms with missing values are because the original paper did not report and it was difficult to get a satisfying score.SPICE is a three-stage algorithm, we only compare with SPICE at the second stage, as the last fine-tuning stage is generally applicable to all deep clustering methods.The superscript B t denotes the stochastic gradient update over mini-batch B t . 


Decision: This paper proposes a new deep clustering algorithm trying to maintain 4 nice properties: accuracy, universality, interpretability and efficiency.  All reviewers agree the paper has novel contributions and is well-written. The convergence analysis is a nice result of the paper. The authors have tried to address the concerns of reviewers by adding more results on large-scale datasets.  Based on these, I will recommend acceptance.

Reviews: review: title: title: Review: the paper introduces a well-structured new deep clustering framework, complemented by a rich theoretical analysis and extensive experiments, but lacks a clear discussion of its limitations, and would benefit from better definitions of terminology and a more nuanced exploration of interpretability and efficiency.
main_review: main_review: **Quality:**
The submission is of good quality, showcasing a well-thought-out framework (PC-X) aimed at addressing challenges inherent in deep clustering. The theoretical underpinnings are strong, and the paper does a commendable job of situating PC-X within the existing landscape of clustering paradigms.

**Clarity:** The paper is well-structured and well-written, making it easy to follow. The comparative analysis using Table 1 provides a clear picture of how PC-X stands relative to existing methods, although some definitions could have been articulated better for enhanced clarity.

**Originality:**
(a) PC-X, with its skip-connection module and unique optimization algorithm, presents a novel approach to deep clustering;
(b) The idea of making clustering centroids into legible exemplars through decoding is innovative and adds a fresh perspective to the domain.

**Significance:** The paper has the potential to further the discourse in deep clustering, especially around interpretability and efficiency.

**Pros:**
- Well-structured and well-articulated paper making it easy to follow.
- Novel framework (PC-X) with innovative components like the skip-connection module and the unique optimization algorithm.
- Rich theoretical analysis backing the proposed framework. Extensive experimentation against multiple baseline methods on several datasets.

**Cons:**
- Datasets used for experimentation are not very large or diverse, which may not fully demonstrate the universality of PC-X.
- Lack of a clear discussion on the limitations of PC-X, which could have provided a more balanced view of the framework.
- Some definitions, especially that of "Universality", are not clear enough, which might lead to confusion. The discussion on interpretability and efficiency could be more nuanced, and the claims could be better substantiated.
title: title: Method for clustering data
main_review: main_review: **Summary**

The authors propose a clustering method which doesn't use any domain knowledge, i.e., does not use augmentation and is interpretable, i.e., centroids can be visualized and are semantically meaningful. They propose a skip connection that encourages the interpretability of centroids and use an auxiliary variable to optimize. Results support their claim, and consistently perform better than the baselines mentioned.

**Strengths**
1. Present a simple way to encourage interpretability using the skip connection.

2. Convergence analysis, ablation study and effectiveness of different loss components are presented in the paper. 

**Weakness**
1. The claim that the method is universal to any modality is incorrect. You need to change the architecture of auto-encoders for different modalities. 

2. Optimization section (3.1.1.) could be improved. I'm unsure if the optimization decomposition steps are done for different batches

**Minor**
Avoid using the term 'skip connection' as it holds a particular meaning in the literature.
title: title: Clear paper with some questions on experimental results
main_review: main_review: The authors present an intuitive clustering method that appears to be efficient and generalizable. The authors describe existing shortcomings and the motivation clearly. Although there are several grammatical errors, they are insignificant enough to not affect the clarity.

Pros
+ Thorough comparisons with various baselines and explored different data modalities
+ Nontrivial theoretical analysis

Cons
- Although the number of datasets tested is sufficient, the scale of the data is quite limited
- Included theoretical algorithm complexities but lacks empirical verification of speed-ups/memory requirements compared to other methods

Questions
1) Based on Figure 2, it is interesting that your method preserves diversity within each cluster in contrast to IDEC's embedding space where points in a cluster collapse on each other. Why is this happening, and what are the implications of this property?

2) Is there an interpretation of what the fully-connected layer does in the fusion step? Does it learn a specific way to mix information?