Angular Constraint Embedding via SpherePair Loss for Constrained Clustering
Authors: Shaojie Zhang
Ke Chen
Venue: NeurIPS 2025 poster ()
Keywords: Deep constrained clustering
angular constraint embedding
deep constraint embedding
anchor-free loss
imbalanced constraints
Primary area: general_machine_learning

Abstract: Constrained clustering integrates domain knowledge through pairwise constraints.
However, existing deep constrained clustering (DCC) methods are either limited by anchors inherent in end-to-end modeling or struggle with learning discriminative Euclidean embedding, restricting their scalability and real-world applicability.
To avoid their respective pitfalls, we propose a novel angular constraint embedding approach for DCC, termed SpherePair.
Using the SpherePair loss with a geometric formulation,
our method faithfully encodes pairwise constraints and leads to embeddings that are clustering-friendly in angular space, effectively separating representation learning from clustering. 
SpherePair preserves pairwise relations without conflict, 
removes the need to specify the exact number of clusters, 
generalizes to unseen data, 
enables rapid inference of the number of clusters, 
and is supported by rigorous theoretical guarantees.
Comparative evaluations with state-of-the-art DCC methods on diverse benchmarks, along with empirical validation of theoretical insights, confirm its superior performance, scalability, and overall real-world effectiveness.
Code is available at [our repository](https://github.com/spherepaircc/SpherePairCC/tree/main).

Angular Constraint Embedding via SpherePair Loss for Constrained Clustering
Shaojie Zhang
Ke Chen
Department of Computer Science, The University of Manchester, Manchester M13 9PL, U.K. {shaojie. zhang, ke. chenc @manchester. ac.
Abstract
Constrained clustering integrates domain knowledge through pairwise constraints. However, existing deep constrained clustering (DCC) methods are either limited by anchors inherent in end-to-end modeling or struggle with learning discriminative Euclidean embedding, restricting their scalability and real-world applicability. To avoid their respective pitfalls, propose a novel angular constraint embedding approach for DCC, termed SpherePair. Using the SpherePair loss with a geomet- ric formulation, our method faithfully encodes pairwise constraints and leads embeddings that are clustering -uuterrin--riendly in angular space, effectively separating representation learning from clustering. SpherePair preserves pairwise relations without conflict, removes the need to specify the exact number of clusters, gen- eralizes to unseen data, enables rapid inference of the number of clusters, and is supported by rigorous theoretical guarantees. Comparative evaluations with state- of-the-art DCC methods on diverse benchmarks, along with empirical validation of theoretical insights, confirm its superior performance, scalability, and overall real-world effectiveness. Code available at our repository.
1 Introduction
Clustering is pivotal machine learning and data mining. Unsupervised clustering methods, being fundamentally ill-posed, often partition data based solely instance similarities or connections, which may misalign with domain knowledge [1]. To address this issue, integrating domain knowledge through weakly supervised methods like Constrained Clustering [2, 3, 4] has gained attention. These methods enforce both positive and negative instance-level pairwise constraints, significantly boosting clustering accuracy. Moreover, they offer cost-effective solution in scenarios where obtaining pairwise relations is easier than acquiring class labels [5].
Most early pairwise constrained clustering (CC) methods adapt traditional unsupervised clustering by introducing constraints through modified similarity metrics or penalty functions [3, 6. 7, 8, 9]. Recent advances in deep clustering have led to the emergence of deep constrained clustering (DCC) paradigms, which outperform traditional methods, particularly on high-dimensional and complex data across various data types, and generalize well to unseen instances. Broadly, based whether constraints are enforced at the level cluster assignments or instance embeddings, we propose categorizing DCC methods into paradigms: end-to-end DCC and deep constraint embedding.
As the dominant paradigm, end-to-end DCC methods (e.g-. [10, 11, 12, 13, 14)) reformulate clustering task by introducing anchors to represent classes, learning representations and cluster assignments jointly. However, the absence of global supervision hinders the proper alignment of anchors with cluster centers, resulting in mismatch between local instance-level similarities and global cluster-level decisions. Moreover, these methods require prior knowledge of the number of clusters in the data to formulate the pseudo-clasiifiction task. These weaknesses, along with other technical issues reviewed in the next section, limit their practical usability in real
as
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

applications. In contrast, deep constraint embedding methods [15, 16] transform CC into traditional clustering through learned representations that encode constraint information using deep learning models. Nevertheless, these methods still struggle to maintain appropriate distances between positive and negative pairs in Fuclidean space during representation learning.
In this paper, we propose the novel SpherePair loss function within a deep constraint embedding approach, addressing the limitations of existing DCC methods. As illustrated in Fig. 1, unlike existing DCC methods that either require anchors or rely on pairwise loss based on Euclidean dis- tance, our SpherePair loss employs cosine similarity to learn a latent representation in angular space without re- lying on any anchors. This effectively balances pairwise relationships, resulting in representation that accurately encodes constraint information towards minimizing intra- cluster distances and maximizing inter-cluster distances. Furthermore, our approach is supported by a theoretical foundation that ensures optimal performance under certain conditions, and does not require knowing the exact number of clusters, thereby reducing the effort required for hyper- parameter tuning. These strengths make our approach more scalable and practically applicable. As demonstrated, our approach outperforms state-of-the various benchmark datasets, even when simple K-means algorithm is applied to its learned representations.
(OA.))
anchor
aui
instine
(a)
(b)
negative pair
positive pair
feature ungle
(d)
Figure I: Different pairwise learning approaches. End-to-end DCC intro- duces anchors to transform features in (a) into soft cluster assignments in (b) for pairwise losses. Deep constraint em- bedding in (c) focuses on the Euclidean distances between features, while ours in (d) operates in angular space.
DCC baselines on
Our main contributions are summarized follows: (i) We propose an angular constraint embedding method using the SpherePair loss, offering a scalable and practical solution for real-world CC tasks. (ii) We establish a rigorous theoretical foundation for our approach. (iii) We demonstrate that our approach can handle unknown number of clusters, rapidly infer the number of clusters and generalize effectively to unseen instances. (iv) We conduct extensive evaluations, demonstrating that our approach outperforms ofte--of-thearr DCC methods across diverse benchmark datasets.
2 Related work
End-to-end DCC. End-to-end DCC methods utilize a predefined number of anchors to connect representations (see Fig. I(a)) and clustering assignments (see Fig. 1(b)), serving as key elements in structuring clustering (See Appendix A for a preliminary with the formal formulation of end-to-end DCC). Key differences arise from anchor configurations and pairwise losses: (i) Anchors include class weights from neural network classification layers (e.g., [14]), centroids of temporary clusters in embedding-baal based models (e.g.. [11, 17, 12)), and components of Gaussian mixture distributions in generative models (e.g.. [13]). (ii) Pairwise losses constrain clustering assignments, using measures such as Bullback-Leibler (KL) divergence [18. 19. 20] or inner products [10. 21, 13]. The Meta Classification Likelihood (MCL) loss [21] is theoretically validated and has inspired numerous extensions [22, 12, 23, 24, 14]. Despite their utility, anchors have notable limitations: anchors often struggle with data misaligned to explicit clustering centers [25] and miss local relationships due to their emphasis on global perspective [26, 27]. end-to-end DCC, this can further leads to potential mismatches, as global assignments can only be inferred indirectly from local pairwise relationships, especially when inappropriate anchors propagate errors during iterations. These issues exacerbated by imbalanced constraints (i.e., many constraints arising from a small number of clusters), which fail to capture nuanced data structures and ultimately degrade clustering performance. Finally, these methods require the exact number of clusters, limiting practical usability and scalability.
Deep constraint embedding. Deep constraint embedding methods [15, 16] address CC problems by learning latent representations with deep learning models (see a preliminary in Appendix A for the formal formulation), typically using anchor-free. pairwise Euclidean distance-based losses (see Fig. I(c)). However, AutoEmbedder [16] requires manually setting a margin due to the unbounded range of Fuclidean distances [0, + +o)). While CPAC [15] avoids margin tuning, its excessive ex- pansion of negative pairs Icads to non-convex, poorly distinguishable clusters, and its reliance

---

connectivity graphs limits generalization to unseen instances. In contrast, our approach leverages angular distances between feature vectors (see Fig. (d)) to overcome the challenges of anchor- based and Euclidean distance-based methods. The angular space ensures equal, definitive inter-cluster distances without anchors, satisfying both positive and negative constraints while enabling inference of the true cluster number from this geometric configuration. Moreover, our approach is supported by a theoretical framework that guarantees optimal performance under specific conditions, eliminates the need for manual tuning, and determines the embedding space dimension without trial and error.
Deep angular learning. Deep learning methods in angular space have been extensively studied for supervised classification tasks [28, 29, 30, 31, 32] like face recognition, where each instance has a label. In contrast, CC involves defining pairwise relationships with sparse constraints applied only to subsets of data, presenting a unique challenge of learning representations while satisfying incomplete constraints without explicit labels. Some supervised prototype-basee methods [33, 34, 35, 36, 37, 38] have explored angular output spaces by guiding instances to converge around equidistant prototypes, benefiting aspects of supervised tasks such boundary discriminability for imbalanced classes and the alignment of Euclidean and cosine metrics [37]. However, these approaches rely on distances to class centers, making them unsuitable for instance-level pairwise learning in CC. Morcover, enforcing class margins does not help resolve complex pairwise constraints that cause conflicts during embedding learning. In contrast, our proposed method is the first apply deep angular learning to CC. By focusing exclusively on the angles between feature vectors (see Fig. (d)), we establish equal inter-cluster distances without using anchors, effectively satisfying both positive and negative constraints while also generalizing well to unseen instances. Our approach leverages the closed nature of angular space prevent constraint conflicts and is supported by theoretical foundation.
3 SpherePair constraint clustering
CC aims to partition a dataset X' = {ar, | into K clusters S (5 while satisfying pairwise constraints = {(a,, b,, y1)) ) where each constraint (a,, by, 3/) requires that instances wa; and Th, be in the same cluster if = 1, or in different clusters if 0. To avoid the reliance on anchors inherent to end-to-end DCC, we learn a constrained yet glustering-friendll representation 2 C IR to determine S, constituting deep constraint embedding. Distinet from existing approaches in Euclidean space, we propose angular embedding to effectively preserve pairwise distances and climinate the need for complex hyperparameter tuming. To facilitate the learning of Z, we adopt a deep autoencoder with encoder f& + 2 and decoder Jø Z + X, parameterized by Φ and ø' respectively.
SpherePair loss. We formulate an anchor- pairwise loss based on angular distance, optimizing the encoder f to generate latent representations 2 aligned with constraints C in angular space. For each constrained pair a Rb. E Z, the angle 2z,,.,,, E [0, T] is normalized to a similarity score Sim(a; by) E [o, 1] for constraint embedding using logistic loss, promoting angular similarity and separation for positive and negative pairs. The resulting SpherePair loss, Lang. is defined
Cang
yy log Sim Sim(a,, by) + (1 31) log(1 Sim(a;, b.))
CCI
ffcos cos( +11, 2 cos (ominnnww #s T)) + 1, if y = 0.
1
if y: = 1,
Sim(a;, b:)
Here, w is an angular factor that ensures sufficient separation between clusters in the embedding space. Our proposed loss promotes constrained embedding learning in the angular space by enforcing the following: (i) for (a;, 1) E C, smaller angles Ox Oz.,,*,, are favored to emphasize similarity; and (ii) for (a,, b,, 0) E C, negative zone of angular size regulates the spacing of dissimilar pairs. The optimal negative-zone factor w. theoretically determined in Section 4, mitigates conflicts among negative pairs in the embedding while ensuring sufficient separation. Notably, our SpherePair loss ensures a bounded angular distance [0, T),, providing stable similarity mapping and avoiding normalization issues associated with unbounded Euclidean distances [0, +20) [11, 15].
3

---

Regularization and learning. While the SpherePair loss Lang aligns 2 with constraints C, minimiz- ing directly may lead degenerate representations that fail to capture intrinsic cluster structures. Inspired by deep clustering methods [39, 40), we incorporate reconstruction loss:
X D
Crccum
2
X
Unlike DCC methods that directly construct latent representations [12, 41, 23], our autoencoder enforces instance reconstruction from normalized angular latent embeddings. To preserve angular properties during regularization, latent embeddings are normalized prior decoding:
c 9 (Norm (f (mz))),
where Norm(-) ensures unit-length embeddings, preserving angular information. Thus, our overall objective for deep constraint embedding
L Lang XLrecon:
4
where trade-off factor À balances the angular loss in Eq. 1 and reconstruction loss in Eq. 2.
Minimizing the overall loss in Eq. yields the optimal angular embeddings, 2". As il- lustrated in Fig. 2, our angular constraint em- bedding learning compacts instances within the same cluster while separating different clusters using the negative zone in (hy- per)sphere. This structure simplifies subse- quent clustering. Consequently, we name our deep constraint embedding framework SpherePair, and the resulting embeddings are spherical representations:
positive pair negutive pair Figure 2: Z change in the SpherePair embedding learning (from left to right): the angular distances of positive pairs decrease, while those of negative pairs gradually adhere to the negative zone E.
instance
Zypeere (Norm(2)) | E 2*},
= (2:)).
(5)
Deployment. Applying unsupervised clustering method to these spherical representations completes the CC process and enables generalization to unseen data. Note that for normalized features in Zypbere: the cosine and Euclidean distances can be shown to be equivalent [42], either metric can be used for clustering. The SpherePair CC algorithm is outlined in Algorithm in Appendix B.
Inferring cluster numbers. When the number of clusters is unknown, it can be inferred from the pre-learned Zyphere via its geometric properties, thereby avoiding both retraining of the latent embedding as required by end-to-end methods and cumbersome post-clustering validation [43]. By applying principal component analysis (PCA) [44] to the training data involved in the negative constraints in Zyphere. we obtain all top-d subspace projections. In each subspace, we compute inter-cluster angles, then select the smallest frrccctoon (0 < p 1) of these angles and compute their tail average. With the theoretical justification presented in Section 4, we infer the number of clusters by identifying the onset of the plateau in the sequence of mean inter-cluster angles across subspaces. The cluster number inference algorithm is presented as Algorithm Appendix B.
Theoretical foundation
We establish a theoretical foundation for SpherePair to rigorously determine the negative-zone factor w and embedding dimension D, which are indispensable for the unique properties of our angular constraint embedding, and further enable our inference of the unknown cluster number K. All proofs of the theortical results are provided in Appendix C.
To fix the negative-zone factor w and prevent conflicts in negative pair embedding, we first establish the conflict-free condition for an optimal angular representation:
Proposition 4.1 (Conflict-free). Let S = {S be the ground-truth partition of X = {2, 1/21 An optimal angular representation z' = { C R achieves Lang = O. To ensure no conflicts in negative pairs, for any 2, E St and xy E St. O2z.27. 0 if k- k', and 02 x; 2 _ if # k'

---

Proof of Proposition 4.1 is given in Appendix C.1, based on which we further constrain w as follows: Proposition 4.2 (Fquidistance). Given X' = [m;]}=] with ground-truth partition S ( and a factor satisfying the conflict-free condition of 2" = {=])}=1 C CRD, then for each constraint (at, bi, ye) from St the angle 0xs, Ai; *i; is uniquely determined by (as, bi, yi) if and only if: (i) z* is equidistant among clusters, i.e., all cross-cluster angles (0x). are the same for any 2, E Sj and
2t E Skizi (ii) w matches this unique angular separation in (i), i.e. = w", where Oz 02 -..
The proof is given in Appendix C.2. An w satisfying Proposition 4.2 also meets the conflict- free condition of Proposition 4.1, ensuring each local pairwise constraint. Moreover, it enforces equidistant cluster embeddings, reflecting the faimess of all negative relationships {(a,, b,, 0)} C and thus balancing pairwise relations. While Propositions 4.1 and 4.2 describe the ideal geometric contiguration under Lang O, the following corollary complements them via perturbation analysis:
Corollary 4.3 (Geometric Deviations under Near-zero Residual Loss). Given a set of |C] constraints
C {(as, bi, ys) y:) and average angular loss Lang S E for some 0 << E < 1, then: (i) For each positive constraint (a,, bú, 1) E C with = we have S 0z S == arccos (2e- |C|==
1) ~ 2V (ii) For each negative constraint (a,, b,, 0) E C with 2 R8
we have 0 N
- Ab (x) == + aarcoos 2e 1c1:) ~ 2//Cle/w.
The proof of Corollary 4.3 is given in Appendix C.3. Corollary 4.3 shows that the geometric deviations degrade gracefully as (vv)) in the limit & - 0, approximately preserving the ideal configuration of Propositions 4.1 and 4.2 under small residual loss.
Despite only such tiny deviations from the ideal embedding, a valid w required by Proposition 4.2 is not always guaranteed, since an equidistant cluster arrangement 2 may fail in arbitrary dimension D. The feasibility and bounds of such w depend on D and the number of clusters K. The following theorem provides conditions for the existence of a valid w meeting Proposition 4.2:
Theorem 4.4 (Existence of Valid w). Given X with the ground truth partition S = (5
containing K clusters. Suppose we seek an w that matches a Z C RD with equidistant clusters, as formalized in Proposition 4.2. Then we have: (i) When D < K K-11 1, such valid w does not exist: (ūi) When D = K - 1, the unique valid w is // arccos( ( -k-1); ); (iii) When D 2 K, the range of valid w values is relaxed to w 2 / arccos( R--).
Proofs of Theorem 4.4 are in Appendix C.4. For each D, Theorem 4.4 establishes the existence conditions and bounds of w that satisfy Proposition 4.2. With such w, SpherePair embedding learning drives 2 to converge to Zsphere, where K clusters form a regular simplex in a (K 1)- dimensional subspace when D > K 1 (Appendix D offers a 3D visualization of this convergence based on a real-world dataset). While any w within the range specified by Theorem 4,4 is admissible, we further restrict the optimal setting through the following corollary:
Corollary 4.5 (Minimal Admissible w). Given X with the ground truth partition S = [S
containing K clusters, and an embedding space RR" D with sufficiently large D 2 K, the minimal
admissible w satisfying the validity condition of Theorem 4.4, denoted by whiin
(K) (K), is bounded as
1 S w (K) < for all K > 1, and is monotone increasing in K with lim w (K) [K=+ == 2.
The proof of Corollary 4.5 is provided in Appendix C.5. In pursuit of larger negative-zone (given by 3) for enhanced inter-cluster separability via a smaller w, Corollary 4.5 prescribes w as the optimal setting for sufficiently large D, universally valid for any K. This theoretically fixes the choice of w. leaving the attainment of conflict-free embeddings governed solely by D. with the lenient bound D > K readily satisfied even when K is not precisely known. Therefore, theoretical guaranteess for w and D in SpherePair CC climinate the need for manual Euclidean margin tuning and strict embedding- dimdessoon calibration [16], ensuring consistent scaling.
When the cluster number K is unknown, given the optimal 2* (or Zyphere) learned by Algorithm 1 with valid w and D (cf. Theorem 4.4), K can be inferred from its theoretically supported geometry: Zxphere converges to a K-vertex regular simplex in a (K- - -ddmmensio subspace, and its projection onto this subspace preserves the same configuration. This implies that the intrinsic embedding dimension d' K-1 is directly linked to the true cluster number. To exploit this link, we employ PCA and have the following theorem:
5

---

Theorem 4.6 (Pairwise-angle Invariance). Given = =
[2,)) with ground-truth partition S*
{5t] and an optimal Z { C IR with equidistant clusters satisfying Propositions 4.1 and 4.2, For d E {l,...,,D) D). ler Zpea { C. R be the d-dimensional PCA projection of Zaphere [Norm(z;)) and denote by =/)" the pairwise angle between 2 + 0 and
1==1
(d)
2/ #0. Then: (i) For every d, d' 2 2 and all such pairs (i.3',, 8 0g 3 = =2ger
2 si (ii)
For any d, d' < K 1, the cross-dimensional invariance in (i) cannot hold for arbitrary pairs (J,j")-
The proof in Appendix C.6. Theorem 4.6 shows that the cross-d invariance of pairwise angles 0 200 3 s0 determines d'. To monitor this invariance, we consider the minimal inter-cluster angle,
5a min f0 20/0002000000 2/9 By E Si By E &kx4k)
for which have the following corollary:
Corollary 4.7 (ōu Invariance). Under the same conditions as in Theorem 4.6, and define the cluster sti 0 with Σ Pk 1. Then: (i) If K 2, the minimal inter-cluster angle [XT
frequencies pk
5d TT Vd 2 1; (ii If K > 2, then d1 = 0, and there exists constant 8, (3. ar,cos(- 1--K-1)
such that da = 6, always holds when 2 K The upper bound arccos( R-T) of 8, is attained
when pı p2
pk. while the lower bound 3 is approached when some pk
Its proof is in Appendix C.7. Corollary 4.7 offers a practical reflection of the invariance in Theorem 4.6 through da. which helps determine d², and hence K. Concretely, for d 1.... 1-1, da increases from O (when K > 2) and reaches some 8. > 3 at d = 1- for d 2 K- 11,, 5a stabilizes around this 8_. Thus, the onset of the plateau of sequence (óa) o identifies d' = K-1.
In practice, under the assumption that the training negative constraints C- cover all true clusters, 5a can be readily computed from C-, and due to small deviations (ef. Corollary 4.3), we replace 5, by a tail-averaged variant da for stability. The sequence { is then used to locate the plateau entry d' and estimate K = d + 1, which provides a theoretical foundation for Algorithm 2.
5 Experiments
5.1 Experimental settings
Our experimental settings aim to address the following questions: (i) How does our SpherePair perform compared to state-of-the-art DCC methods? (ii) How well do our SpherePair and baseline methods capture consistent instance relations under imbalanced constraint distributions? (iii) How effectively does our approach handle unknown cluster numbers? (iv) How are our theoretical insights empirically supported, and how sensitive is our approach to the introduced hyperparameters?
Datasets. We adopt eight benchmarks with diverse class counts and class balance: CIFAR-100-211 and CIFAR-10 [45], FashionMNIST [46], ImageNet-10 10 [47]. MNIST [48], STL-110 [49]. together with two imbalanced text datasets, Reuters subset [50] and RCV 1-10 (see Appendix E. for details).
Baselines. We evaluate our SpherePair against three categories of DCC methods: (i) -fate-of-the-an end-to-end approaches, including VanillaDCC [21], VoIMaxDCC [14], DCGMM [13], and CIDEC [12]: (ii) SDEC [11], which integrates Euclidean constraint embedding loss into end-to-end deep clustering; and (iii) AutoEmbedder [16], a fully anchor-free Fulidean constraint embedding method. For AutoEmbedder and SpherePair, K-means is applied to their learned representations for clustering unless otherwise specified. These basclines encompass the key advancements in DCC research.
Protocol. For FashionMNIST,, MNIST, and the Reuters subset, we use the original pre-split training and test data settings. For the remaining benchmarks, we randomly split the data into 80% training and 20% test sets. Consistent with [14], we reserve validation set of 1,000 instances from the training data to optimise the hyperparameters for baselines requiring such tuning. Constraints are generated based on the ground-truth labels of pairs sampled within the training sets. For a comparative study,

---

performance with different constraint set sizes (1k/5k/100k is evaluated on training and test sets over five trials using three standard clustering metries: Accuracy (ACC). Normalised Mutual Information (NMI), and Adjusted Rand Index (ARI). To assess performance under imbalanced constraints, we create a balanced set, IMBO, via uniform sampling and gradually introduce additional constraints linked to fewer clusters to form two imbalanced sets, IMB1 and IMB2, where IMBO C IMB1 C IMB2 (see Appendix E.3 for detailed constraint generation procedure). To examine the effectiveness of cluster number inference, we repeat the procedure using embeddings pre-learned from five random initializations. To empirically validate our theoretical insights and assess the robustness of our approach, we explore wide range of D, X, and p settings.
Implementation. We strictly follow the same fully connected architectures from baseline papers [11, 12, 13, 14] for fair comparison and compatibility with both image and non-image datasets. For DCGMM, CIDEC, SDEC, AutoEmbedder, and SpherePair, we use a fully connected encoder with hidden layers of size 500-500-2000 (and a symmetric decoder when required), and embedding layer of D = 20 for CIFAR- 100-20 and D = 10 for the remaining datasets, unless stated otherwise. For VanillaDCC and VolMaxDCC, we use fully connected network with two hidden layers of size 512-512 and classification layer matching the number of clusters, K, as recommended in [14]. ReLU activations are used across all networks. Pretrained autoencoders are employed for model initialisation, except for VanillaDCC and VolMaxDCC. Specifically, variational autoencoder is pretrained for DCGMM, while stacked denoising autoencoders are pretrained layer-wise for other models. Pretraining is performed unsupervised on the entire training set. In SpherePair and cluster number inference, w is theoretically fixed at as per Sect. 4, while À 0.02 and p = 0.05 are used by default unless varied for hyperparameter robustness evaluation. For baselines, we adopt reported optimal hyperparameters (VanillaDCC,, DCGMM, CIDEC, SDEC) or follow the search procedures in VoIMaxDCC and AutoEmbedder. SpherePair and all baselines (except DCGMM, where we use the authors' source code) are implemented in PyTorch 1.5.1. Training is conducted using the Adam optimizer, except for SDEC and VolMaxDCC, which employs SGD as suggested by their authors.
More details of our experimental settings are provided in Appendix E to ensure full replicability.
5.2
Experimental results
Using the experimental setup outlined in Sect. 5.1, we present and analyze our results to address the four motivating questions that guided our study. Additional results are provided in Appendix F.
5.2.1 Comparative performance
Overall comparison. Table reports SpherePair's 's results against six baselines on all eight datasets under three constraint levels (1k/5k/10k). Out of 72 total comparisons (8 datasets x 3 constraint levels x 3 metrics), SpherePair ranks first in over 60 cases and second in nearly all others. It is notably dominant in every metric at every constraint level (9/9 each), surpassing the second- best method by up to 4-16% in absolute ACC. Even when second-best, the performance gap is within 1-2%. Additional comparisons with AutoEmbedder using hierarchical clustering (replacing K-means) can be found in Appendix F.I. These findings showcase SpherePair's 's state-of-the-art DCC performance across both image and text datasets, along with the robustness of its geometric formulation under varying supervision levels and data domains.
CIFAR- 100-20, FMNIST, REUTERS, and RCV1-10, achieving the top result
Comparison without pretraining. We further compared two strong models without pretraining (random initialization), CIDEC and SpherePair' As shown in Table 1, SpherePair exceeds CIDEC by 10-20% on nearly all datasets except MNIST at 1k constraints; at 5k/10k it remains superior in most cases. Except for the highly flss-imbalannee RCV1-10, pretrained SpherePair consistently yields modest improvement (around 1 1%) over its unpretrained version. In contrast, CIDEC benefits substantially from pretraining only at 1K constraints, but shows inconsistent gains at higher constraint levels and even drop on FMNIST. Hence, end-to-end DCC rely heavily on sufficiently good initial clustering to bootstrap reliable iterations, but our anchor-free SpherePair loss demonstrates robustness to initialization, particularly when pretraining is unavailable or leads to degraded performance.
7

---

Table Comparative performance (%) (ACC, NMI, ARI) across datasets for models with 1k/5k/10k constraints. Blue and black represent training and test results, respectively. Best results are in bold, second-best are underlined, and indicates models without pretraining.
Vanilla- DCC
VelMax- DCC
CIDECT
CIDEC
DCGMM
SDEC
Auto- Embedder
SpherePair (Ours)
SptecrePair (Ours)
ACC
34.2.
34.3
21.1. 20.3
32x. 33.0
46.6
46.2
145. 41,2
45.7.
45.4
21.5. 21.6
45.1, 45.
48.3. 48.2
NMI
36.0,
36.3
21,4
35,6
47.3
479
449.45.4
47.0
47.5
23.1. 23.4
44.9. 45.4
47.7. 48.0
CIFAR100-20
ART
19.3.
19.3
7.2
19.7.
19.6
300.
29.9
28.7.
28.7
29.0.
29.2
7.1,
29.4. 29.5
32.2, 32.4
ACC
47.4,
474
4288.428
42.3.
42.1
46
46.1
1,71.479
45.6 45.1
13.8. 14.2
154.55.1
59.0, 58.8
NMT
46.7.
47.1
41.9.2.11
42.
45.4
45.7
46.7.77
47.0.475
13.5. 13.8
511.511
52.6, 53.0
ARI
32.2.
32.2
22.8.
27.1. 26.8
30.3.
29.6
32.2.
32.2
29.2.
29.3
4.7.4.7
39.1. 39.4
41,0.40.9
ACC
54.5
51.2.
49.8 49.8
50.9,
50.1
52.3.
52.1
45.7,45. 45.2
31.3, 31.3
60.5,
628. 62.6
10k
NMI
50.2.
50.3
48.5. 48.7
47.6
48.5. 48
49.2.
49.6
47.1.
36.6, 36.9
53.9. 54.3
55.1
ART
37.9,
37.5
33.4,
33.3
33.4, 33.2
34.0.
33.0
36.7,
36.7
29.3.
29.5
20.6, 20.4
23.4, 35.4
45.3, 45.2
ACC
70.2.
70.1
58.5
K4.3.
85.7. 85.6
66.9
62.4 48.6,
60.2,
60.3
78.9
76.5. 76.5
58.1
75.6, 75.4
77.3. 77.1
CIFARIO
ARI
57.8, 57.6
48.3
50.1.
50.3
75.2.
75.1
69.7. 69.6
70.5. 70.6
43.1, 43.3
71.7.
74.00 73.7
ACC
87.6 87.3
84.9
84.6
86.4,
86.2
88
88.0
85.4
85.5
85.9,
85.8
58.9 88.7
89.1, 88,9
5k NMI 79.3. 79.0
78.6
79.8
78.1.
79.2. 79.3
N0.7.
81.2. 80.9
ARI 76.9. 76.4
75.2
74.5
75.00
74.5
79.0.
78.5
78.0
77.4
73.4
73.4
75.7.
75.6
79.1. 78.6
79.6. 79.1
ACC 90.0, 89.5
90.0.
89.5
88.4
89.8
89.9,
89.7
85.6
85.6
87.7, 87.4
90.5, 90.0
90.5. 89.9
10K
NMI
78.3
82.3,811
82.3. 81.6
ART 79.5
80.3.
79.5
78.5
80.7.
80.1
80.4,
73.8. 73.8
78.2, 77.7
81.3,
81.4, 80.4
ACC
56.6.
56.3
50.9.
50.6
52.7.
$2.0
58.0 57.6
64.7.
63.5
56.7. 56.6
39.6, 39.4
62.8. 62.1
70.3. 69.8
IK
NMI
56.1
49.1
53.4,
52.9
62.0.
41.1, 41.0
60.1. 59.5
61.7
FMNIST
43.3
33.3,
32.7
37.5
44.9.
43.9
48.4
25.0, 24.7
49.8. 49.1
51.7.
ACC 76.2.
75.2
76.0.
75.3
71.7
71.
64.6,
63.8
78.5.
77.3
57.3,
1910,55.4
SO.1, 79.0
810. 79.9
5k
NMI
67.4.
66.5
67.3. 66.6
65.7.
65.1
61.2. 60.4
69.8 70.7.
62.6. 62.0
57.9.57.
69.7 70.8.
72.0. 70.9
ART
614,
60.0
60.8,
59.8
56.3
48.
47.5
63.1
45.6,
44.5
45.0
05.2,
66.8, 65.3
ACC
80.3, 79.0
80.2. 78.7
77.7.
76.7
7.
74.0
81.5 80.3
18 58.2
68.1. 67.5
83.6, 82.3
84.8, 83.6
1OK
NMI
71.3, 70.1
71.2.
69.6
71 70.3
68.9
68.2
73.8
72.3
63.1.
62.4
65.0,6413
73.. 72.4
75.6. 74.2
ARI
66.4. 64.6
66.2.
63.9
65.0.
63.7
61.4.
60.2
08.6.
66.8
46.1.
45.2
$3.9
89.8. 67.9
72.0. 70.1
ACC
834, 83.6
84.0,
83.9
839,
84.1
92
92.7
94
94,4
89
88.9
61.2,
95.9, 95.6
95.9, 95.9
Ik
NMI
83.1
83.7
81.7
82.9
81
82.2
88 3, 88.8
89.1.
89.4
84
84.4
55.4
90.6, 9T.1
90.7. 91.1
ImageNet10
ARI
77.0,
76.9
75.9.
76.1
75.2.
74.9
8. 86.3
88.9,
88.8
7. 80.1
39.5, 38.3
91.2. 91.1
91.2. 91.2
ACC
96.3
96.3
96.3
96.4
96.3,
96.2
96
96.5
96.6,
96.3
89.3
89.5
90.4, 96.3
96.8, 96.4
96.9, 96.6
5k
NMI
9T3,
92.3
92.6
92.7
91
92.1
9T4
92.2
91
91.5
86
86.0
91.6, 91.6
92.2. 92.5
92.4, 92.2
ARI
93.4,
92.1
93.2.
92.3
92.2.
91.8
93.1.
92.5
92.6.
91.9
82.2.
82.0
92.3, 92.0
93.2. 92.3
93.2. 92.7
ACC 97.0,
96.2
96.9.
96.2
97.
96.5
97
96.6
97.0.
96.5
69
89.6
96.8, 96.6
97.0, 96.2
97.3, 96.7
10k
NMI
93.2.
92.2
92.8.
92.4
92.9.
92.3
93.0.
92.4
92.7.
92.0
86.3
86.4
92.2. 92.2
93.2, 92.6
93.2. 92.5
ART
94.1,
91.9
93.7.919
93.7,
92.4
93.9.
92.7
93
6.
92.5
82,4,
82.4
94,0, 92.4 93.0,92.7
94.1, 93.0
ACC 54.4,
54.9
47
57.3
65.
65.8
8R.6
88.0
84
84.6
84.4
84.7
43.2, 43.4
69.8, 71.0
91.6, 91.7
NMI
48.1
49.5
50.8,
51.6
62.7.
63.0
86.8
86.0
80
80.8
79.6
80.5
35,5, 36.6
59.8, 61.5
82.5, 82.8
MNIST
ARI
39.0)
40.0
40.8.
41.2
51.9,
52.1
83.5.
82.3
75
75.7
75.9.
76.5
22.9, 23.4
$4.2,
82.6, 82.8
ACC 82.2.
82.6
76.3.
77.0
90.22
89.5
8. 95.4
94.0,
94.1
86
86.1
58.5. 58.9
93.2. 93.3
96.1. 95.9
NMI
7.
76.2
68.0.
69.1
5.
84.3
91.6.
90.7
88.7,
88.7
82.6. 83.0
57.5, 58.8
84.5, 84,9
90.0, 89.9
ARI
72.4.
73.2
64.2.
65.1
83.9.
82.4
92.0.
91.0
88.6.
88.6
79.4.
47.5 46.9,
85.7,
91.3, 91.2
ACC
91.4
91.3
96.5,
97.5.
86.3, 86.1
81.5,
95.6,
10K
NMI
84.1,
84.3
82.9.
83.2
91 89.7
93.5.
92.6
91.2 90.8
83.0. 83.3
77.7, 78.7
89.0, 89.1
9I 92.1
ART
85. 3, 85.3
83.6,
83.5
90.7 92.5
94.7. 93.7
91.7
91.2
79.6,
79.5
74.1, 74.9
90.7, 90.6
93.7. 93.7
ACC
70.8
66.
66.7
91.2,
NMI
42.3.
43.0
38.8, 39.8
48.2
51.1
59.3,
60.5
68
68.2
52.4
15.2, 14.7
64.1.
72.9. 74.1
REUTERS
ART
49.1.
49.0
45.7.
45.4
54.6 51
66 1, 66.9
Y. 77.0
35.8.
14 13.7
74.1.71.9
81.0. 81.5
ACC 94.8
95.5,
94.3
82.0,
82.3
93.
92.7
94.4
71.6
85.0, 84.9
95.6,93.5
96.1, 948
5k
NMT
79.6
60.5,
6
78.
54.6 54.6
63.7,
83.
84.9, 80.7
ARI
90.9.
88.1
89.7, 86.6
68.2 68.0.
66.6.
85.3
V0.3. 87.1
57.1.
73.7. 71.8
89.7.
91.0, 87.2
ACC
97.4, 94.9
94.4
88.1 86.3
95.9 89.8
95.6
71.6. 71.2
92.8, 91.0
97.8,95.2
97.8, 95.8
10k
NMI
68.7
75.4
90.2. 83.9
ARI 94.2,
87.5
93.6, 86.3
80.3. 76.0
94.5,
90.1
94.3.
89.3
5..1. 56.8
86.6, 82.7
95.0, 87.9
95.0. 89.8
ACC 69.9. 70.0
74.4,
74.5
69
71.1
88.0
87.8
77.6.
77.2
85.5 85.6
50.6, 51.0
86.2
88.1, 88,1
lk
NMI
69.5
79.2
77.1
76.6. 18.4
78.7.
STL
ARI
54.7
61.9.
61.8
58.9
76.
63.2
72.1
33.6,
74.2,
76.8
ACC
88.1 87.1
88.9
87.9
87
86.9
90.3
89.4
88.0
87.1
87.3.
87.6
84.0, 83.7
91.2. 90.1
914. 90.3
5k
NMI
80.6.
79.5
80.2.
79.4
78.6.
79.1
81.9
80.9
78.7.
78.1
79.1.
79.3
77.8. 77.4
83.0. 81.7
83,1,81.9 81.9
76.5
76.0
80.4
75.7
75.6
73.7,
72.8
$2.2 80.3
82.5. 80.5
ACC 916 89.9
914
90.1
90.7
89.7
91
89.9
4
89.5
87
M1 89.6
93.. 91.0
93.. 91.0
10K
NMI 84.9 81.8
84.2.
81.8
82
81.7
83
81
82.7
80.7
79.4.
79.6
82.5. $1.0
85.4.
85.4 83.2
ART
84.7. 80.0
83.9.
80.0
81.3.
79.7
82
79.8
82.3.
79.1
75.9.
81.5,
79.2
85.4,
85.5. 81.7
ACC
49.9
42.3
39.5.
33.4, 33.4
$2.1.
65.8
40.
40.3
33.6
46.1
17.9
10.4,
6,
60.8. 61.1
RCVI-10
ARI
12.9.
12.8
39.5. 39.4
27.2.
28.4
31.0.311
12.3.
12.2
32.5
32.4
7.8
42.5. 42.5
55.8. 55.9
ACC
78.
78.1
80.7.
50.5
57.6.
55.1
61.7
54.1
33,1
53.5
39.5,
39.4
19.4, 49.4
N6.7, 86.3
89,8 89.6
5k
NMI
61.8
47.5
51.7. 54.4
38
38.0
50.9. 51.2
69.2
74.2, 73.9
ARI
70.7,
70.5
75.3.
75.1
46.4
46.2
53.4,
54.0
40
39.3
33.0,
33.0
35.9, 35.8
31
83.8. 83.4
ACC
84.3,
84.1
87.8
87.5
58
54.5
80.0.
79.4
810. 80.0
38.8 38.8
77.3, 77.3
89.9 89.8
91.8. 91.5
10k
NMI
70.0,
69.6
70.8.
70.3
4,
67.7
63.4,
62.7
50.5
74.9 14.6
78.0. 77.4
ART
81.6, 81.2
83.0,
82.4
479, 47.1
74.5, 73.9
75.4, 74.4
32.8.
32.7
68.9, 68.6
85.5, 85.2
87.0, 86.4
5.2.2 Imbalanced constraints
Fig. 3 presents the test ACC under the imbalanced constraint setting outlined in Sect. 5.1. As the imbalance increases, all DCC baselines experience significant performance degradation across most datasets. In contrast, our SpherePair demonstrates remarkable stability and consistently outperforms
8

---

THE
MALACO- PONOIT
S.D.AD- BIAGE
HREST
ACD POUTTER
AZD STL/0
681
001
60
400
Figure 3: Test ACC performance std over 5 runs) of all models across datasets under the balanced vs. imbalanced constraints setting where (MMOO] IMB1|, [MB2)) (10k, 50k, 100k).
all baselines across the tasks. Figure 4 visual- izes the learned FMNIST embeddings, illustrating how SpherePair preserves coherent structures while forming more discrimina- tive clusters compared to representative baselines. Notably, while the imbal- anced sets contain more constraints than the bal- anced set, the performance of baselines worsens with greater imbalance, posing open question for further investigation. Additional results and visualizations are Appendix F.2, further showcasing the robustness of our approach in real- wolld scenarios with prevalent imbalanced constraints.
VanilaDCC
Autoembesder
SpherePair laues)
Te
Text ACC 0.52
Test ACC 0.54
Text ACC 0.83
Figure 4: I-SNE visualizations of learned FMNIST embeddings under the IMB2 setting in Fig. 3. Marker colors denote ground-truth categories, and dashed lines represent pairwise constraints. The red circles highlight the misclustered instances.
5.2.3 Unknown cluster number
We evaluate our cluster-number inference on SpherePair embeddings, simulating the unknown- K with large embedding dimensions (D 50 for CIFAR- 100-20 and D 20 for others). As shown in Fig. 5, the tail-averaged minimal inter-cluster angle 8a rises from 0 as the PCA subspace dimension d increases and, for most datasets, reaches plateau at - which clearly reveals the true cluster number K. On CIFAR- 100-20, the plateau is less distinct, yet the estimated K falls within 18-22 around the true K = 20. The only notable deviation is observed on RCV1-10, where strong class imbalance results in only six dominant clusters being identified, underscoring the inherent difficulty of K-inference in such settings. Nevertheless, our approach demonstrates overall robustness and efficiency, as further validated Appendix with additional results under varied constraint levels, comparisons to alternative K K-inference methods, and evaluations against other DCC methods.
1EFAR-100-20
311-
317
18
Figure 5: Tail-averaged minimal inter-cluster angle J4 vs. PCA subspace dimension d, obtained from SpherePair embeddings learned with 10k constraints across runs. The red lines indicate the ground-truth intrinsic dimensions d' 1.
5.2.4 Empirical validation and hyperparameter sensitivity analysis
Embedding dimension D. We study the impact of embedding dimension D, the only hyper- parameter to be specified to obtain conflict-free angular embedding, to empirically validate our

---

GFF60000-50
GRMRIO
PVNST
IAAGENET1O
KNNIS
REUTERS
S7,10
ROV1-10
Figure 6: SpherePair test ACC (mean=ssd, 5 runs) vs. embedding dimension D across datasets (10k constraints). The red lines indicate the theoretical boundary between insufficient and sufficient D.
theoretical insights. Fig. 6 presents performance with respect to D under 10k balanced constraints (see Appendix F.4.1 for results under more constraint levels and clustering metrics), showing that: (i) SpherePair is robust to choices of D 2 K, even up to 1000, which corresponds 50-250x the cluster number K across different datasets. This provides clear and easily satisfied practical guid- ance. (ii) Even selecting D slightly below the theoretical threshold minimally impacts performance, offering flexibility when K is unavailable. Additional results in Appendix F.4. further support this D-flexibility through comparisons with baselines on DIFAR-100-22 (iii) Ablation-like comparisons between theoretically sufficient and insufficient D illustrate the effectiveness of our conflict-free constraint embedding in angular space, and empirically validate our theoretical insights in Section 4.
Other hy typerparameters. We further conduct sensitivity analysis on the regularization strength À over [0, 1] and the tail ratio p over [0.01, 0.2] (see Appendices F.4.2 and F.4.3). Key observations are: (i) SpherePair embedding is broadly robust to X, though an appropriate can be beneficial, particularly under limited constraints random initialization. We recommend a default of À 0.02 for consistent performance in most cases; (ii) in cluster cluster-number number inference, smaller sharpens rises before 8x -1 while larger p stabilizes the subsequent plateau; [0.03, 0.1] generally offers a favorable trade-off for clearer K estimation.'
In summary, the experimental findings provide robust validation of our contributions. Notably, our method also demonstrates significant potential for real-world applications in terms of its learning efficiency (see Appendix G) and insensitivity model structures (see Appendix H).
6 Conclusion
In this paper, we propose SpherePair, a novel representation learning approach for constrained clustering. It learns effective representations from pairwise constraints in angular space, supported by theoretical guarantees. Extensive experiments on real-world and benchmark datasets demonstrate that SpherePair, when integrated with a simple clustering algorithm such as K-means, consistently outperforms various state-of-the-aa DCC baselines. Furthermore, SpherePair is anchor-fres free, requires minimal hyperparameter tuning. offers robustness with theoretical guarantees, and readily handles an unknown number of clusters while rapidly inferring their quantity, making it highly applicable to real-world constrained clustering tasks.
Our approach has two limitations: (i) currently supports only single-view unstructured data; (ii) It does not address incomplete or noisy constraint annotations. To address these challenges, we are extending SpherePair to handle semi-structured, structured, and multi-view data, as well as introducing mechanisms manage noisy incomplete annotations. We also aim to combine end-to-end and deep constraint embedding frameworks to capture higher-order correlations and improve scalability, particularly for applications requiring deeper understanding of local and global relationships. We anticipate that addressing these challenges will result more robust SpherePair models, improving the applicability and performance across diverse real-world data.
'Robustness can be enhanced by evaluating consistency across multiple values within this range.
10

---

Acknowledgment
We are grateful to the anonymous reviewers for their comments, which improved the presentation of this paper. S.J. Zhang's s work was supported by the UoM-CSC scholarship.
References
[1] Ian Davidson and Sugato Basu. A survey of clustering with instance level constraints. ACM Transactions on Knowledge Discovery from data, 1(1-41):2-42 2007.
[2] Kiri Wagstaff and Claire Cardie. Clustering with instance-level constraints. AAAI/IAAI,
1097(577-584):197, 2000. 1
[3] Kiri Wagstaff, Claire Cardie, Seth Rogers, Stefan Schrödl, al. Constrained k-means clustering with background knowledge. In Icml, volume 1, pages 577-584, 2001.
[4] Germán Sonzúlez-AAlagro, Daniel Peralta, De Poorter, José-Ramón Cano, and Salvador García. Semi-supervised constrained clustering: An in-depth overview, ranked taxonomy and future research directions. arXiv preprint arXiv:2303.0052. 2023.
[5] Yucen Luo, Tian Tian, Jiaxin Shi, Jun Zhu, and Bo Zhang. Semi-crowdsourced clustering with deep generative models. Advances in Neural Information Processing Systems, 31, 2018.
[6] Zhengdong Lu and Todd Leen. supe-supe learning with penalized probabilistic clustering. Advances in neural information processing systems, 17, 2004.
Mikhail Bilenko, Sugato Basu, and Raymond Mooney. Integrating constraints and metric learn- ing in semi-supervised clustering. In Proceedings of the twenty-first international conference on Machine learning, page 11, 2004. 1
[8] Sugato Basu, Arindam Banerjee, and Raymond Mooney. Active semi-supervision for pairwise constrained clustering. In Proceedings of the 2004 SIAM international conference on data mining, pages 333-344. SIAM, 2004.
[9] Brian Kulis, Sugato Basu, Inderjit Dhillon, and Raymond Mooney. Semi-supervised graph clustering: kernel approach. In Proceedings of the 22nd international conference on machine learning, pages 457 464, 2005.
[10] Yen-Chang Hsu, Zhaoyang Lv, Joel Schlosser, Phillip Odom, and Zsolt Kira. A probabilistic constrained clustering for transfer learning and image category discovery. arXiv preprint arXiv:1806.1100 11078, 2018. 1,2
[11] Yazhou Ren, Kangrong Hu, Xinyi Dai, Lili Pan, Steven CH Hoi, and Zenglin Xu. Semi- supervised deep embedded clustering. Neurocomputiig, 325:121-130, 2019. 2, 6, 31, 32, 33, 36, 37
[12] Hongjing Zhang, Tianyang Zhan, Sugato Basu, and Ian Davidson. A framework for deep constrained clustering. Data Mining and Knowledge Discovery, 35:593-620, 2021. 1, 2, 4, 6, 7, 31, 32, 36, 37. 55
[13] Laura Manduchi, Kieran Chin-Cheong, Holger Michel, Sven Wellmann, and Julia Vogt. Deep conditional gaussian mixture model for constrained clustering. Advances in Neural Information Processing Systems, 14:11303-11314 2021. 2, 6. 7, 31, 32, 33, 36, 37
[14] Tri Nguyen, Shahana Ibrahim, and Xiao Fu. Deep clustering with incomplete noisy pairwise annotations: A geometric regularization approach. In International Conference on Machine Learning, pages 25980-26007. PMIRR 2023. 1, 2, 6, 7, 31, 32, 34, 37,38
[15] Sharon Fogel, Hadar Averbuch-Elor Daniel Cohen-Or, and Jacob Goldberger. Clustering- driven deep embedding with pairwise constraints. IEEE computer graphics and applications, 39(4): 27, 2019. 2,

---

[16] Abu Quwsar Ohi, Muhammad Firoz Mridha, Farisa Benta Safir, Md Abdul Hamid, and Muham- mad Mostafa Monowar. Autoembedder: A semi- supervvisd dnn embedding system for cluster- ing. Knowledge-Batt Based Systems, 204: 106190, 2020. 2, 5, 6, 31, 32, 33, 34, 38
[17] Hongjing Zhang, Sugato Basu, and Ian Davidson. A framework for deep constrained clustering- algorithms and advances. In Machine Learning and Knowledge Discovery Databasex: European Conference, ECML PKDD 2019, Würzhurg, Germany, September 16-20, 2019, Proceedings, Part I. pages 57-72. Springer, 2020.
[18] Yen-Chang Hsu and Zsolt Kira. Neural network-based clustering using pairwise constraints. arXiv preprint (rXiv:1511.0632)) 2015. 2
[19] Ankita Shukla, Gullal S Cheema, and Saket Anand. Semi-supervised clustering with neural networks. In 2020 IEEE Sixth International Conference on Multimedia Big Data (BigMM), pages 161. IEEE, 2020. 2
[20] Elham Amirizadeh and Reza Boostani. CDEC: A constrained deep embedded clustering. International Journal of Intelligent Computing and Cyhernetics, 14(4):686-701, 2021. 2
[21] Yen-Chang Hsu, Zhaoyang Lv, Joel Schlosser, Phillip Odom, and Zsolt Kira. Multi-class classification without multi-class labels. arXiv preprint arXiv:1901.00544, 2019. 2, 6, 32
[22] Marek Smieja, Lukasz Struski, and Mário AT Figueiredo. A classification- approach to semi-supervised clustering with pairwise constraints. Neural Networks, 127:193-203, 2020.
[23] Tian Tian, Jie Zhang, Xiang Lin, Zhi Wei, and Hakon Hakonarson. Model-based deep embed- ding for constrained clustering analysis of single cell rna-seq data. Nature communications, 12(1):1873, 2021. 2,
[24] Jann Goschenhofer, Bernd Bischl, and Zsolt Kira. Constraintmatch for semi-constrained clustering. In 2023 International Joint Conference on Neural Networks (ICNNN, pages 1-10. IEEE, 2023. 2
[25] Yi Wen, Suyuan Liu, Xinhang Wan, Siwei Wang, Ke Liang, Xinwang Liu, Xihong Yang, and Pei Zhang. Efficient multi-view graph clustering with local and global structure preservation. In Proceedings of the 31st ACM International Conference on Multimedia, pages 3021-3030, 2023. 2
[26] Jian Dai, Zhenwen Ren, Yunzhi Luo, Hong Song, and Jian Yang. Tensorized anchor graph learning for large-scale multi-view clustering. Cognitive Computation, 1515)1158 2023.
2
[27] Suyuan Liu, Qing Liao, Siwei Wang. Xinwang Liu, and En Zhu. Robust and consistent anchor graph learning for multi-view clustering. IEEE Transactions on Knowledge and Data Engineering. 2024. 2
[28] Weiyang Liu, Yandong Wen, Zhiding Yu, and Meng Yang. Large-margin softmax loss for convolutional neural networks. In International Conference on Machine Learning, pages 507-516. PMLR, 2016.
[29] Weiyang Liu, Yandong Wen, Zhiding Yu, Ming Li, Bhiksha Raj, and Le Song. Sphereface: Deep hypersphere embedding for face recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 212-220, 2017. 3
[30] Weiyang Liu, Yan-Ming Zhang, Xingguo Li, Zhiding Yu, Bo Dai, Tuo Zhao, and Le Song. Deep hyperspherical learning. Advances in neural information processing systems, 30, 2017. 3
[31] Hao Wang, Yitong Wang, Zheng Zhou, Xing Ji, Dihong Gong, Jingchao Zhou, Zhifeng Li, and Wei Liu. Cosface: Large margin cosine loss for deep face recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 5265-5274, 2018. 3
[32] Jiankang Deng, Jia Guo, Niannan Xue, and Stefanos Zafeiriou. Areface: Additive angular margin loss for deep face recognition. Proceedings of the IEFF/CVF conference on computer vision and pattern recognition, pages 4690-4699, 2019. 3
12

---

[33] Pascal Mettes, Elise Van der Pol, and Cees Snock. Hyperspherical prototype networks. Advances in neural information processing systems, 32, 2019. 3
[34] Yueqi Duan, Jiwen Lu, and Jie Zhou, Uniformface: Learning deep equidistributed representation for face recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and
Pattern Recognition, pages 3415-3424, 2019. 3
[35] Florian Graf, Christoph Hofer, Mare Niethammer, and Roland Kwitt. Dissecting supervised contrastive learning. In International Conference on Machine Learning, pages 3821-3830.
PMLR, 2021. 3
[36] Tianhong Li, Peng Cao, Yuan Yuan, Lijie Fan, Yuzhe Yang, Rogerio S Feris, Piotr Indyk, and Dina Katabi. Targeted supervised contrastive learning for long-tailed recognition. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 691 19986692,, 2022. 3
[37] Hakan Cevikalp, Hasan Saribas, and Bedirhan Uzun. Reaching nirvana: Maximizing the margin in both euclidean and angular spaces for deep neural network classification. IEEE Transactions on Neural Networks and Learning Systems, 2024. 3
[38] Hakan Cevikalp, Hasan Serhan Yavuz, and Hasan Saribas. Deep uniformly distributed centers on hypersphere for open set recognition. In Asian Conference Machine Learning, pages 217-230. PMLR, 2024. 3
[39] Bo Yang. Xiao Fu, Nicholas D Sidiropoulos, and Mingyi Hong. Towards k-means- friendly spaces: Simultaneous deep learning and clustering. In international conference on machine learning, pages 3861-3870. PMLR, 2017. 4
[40] Xifeng Guo, Long Gao, Xinwang Liu, and Jianping Yin. Improved deep embedded clustering with local structure preservation. In Ijeai, volume 17, pages 1753-1759, 2017. 4, 33
[41] Yi Cui, Xianchao Zhang. Linlin Zong, and Jie Mu. Maintaining consistency with constraints: A constrained deep clustering method. Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 219-230. Springer. 2021. 4
[42] David Barber. Bayesian Reasoning and Machine Learning, page 341. Cambridge University Press, 2012. 4
[43] Brian Everitt, Sabine Landau, Morven Leese, and Daniel Stahl. Cluster Analysis. Wiley, Chichester, UK, 5th edition, 2011. 4, 36
[44] Ian Jolliffe. Principal component analysis. In International encyclopedia of statistical science,
pages 1094-1096. Springer, 2011. 4, 36
[45] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009. 6, 31
[46] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.077 1707,07777 2017. 6, 31
[47] Jianlong Chang, Lingfeng Wang, Gaofeng Meng. Shiming Xiang, and Chunhong Pan. Deep adaptive image clustering. In Proceedings of the IEEE international conference on computer vision, pages
2017. 6, 3.
[48] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 (1:277)22282,,2,, 1998. 6, 31
[49] Adam Coates, Andrew Ng, and Honglak Lee. An analysis of single-layer networks in unsuper- vised feature learning. In Proceedings of the fourteenth international conference artificial intelligence and statistics, pages 215-223. JMLR Workshop and Conference Proceedings, 201
6, 32
[50] Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In International conference on machine learning, pages 478-487. PMLR, 2016. 6, 30. 31, 33, 37
13

---

[51] David D Lewis, Yiming Yang, Tony Russell-Ross and Fan Li. Revl: A new benchmark collection for text categorization research. Journal of machine learning research, 5(Apr):361- 397, 2004. 30,
[52] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248-255. Iece, 2009. 31
[53] Yunfan Li, Peng Hu, Zitao Liu, Dezhong Peng, Joey Tianyi Zhou, and Xi Peng. Contrastive clustering. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 8547-8555, 2021. 31, 37
[54] Zhuxi Jiang. Yin Zheng, Huachun Tan, Bangsheng Tang, and Hanning Zhou. Variational deep embedding: An unsupervised and generative approach to clustering. arXiv preprint arXiv:1611.05145. 2016. 33
[55] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770-778, 2016.
[56] Geoffrey E Hinton and Ruslan R Salakhutdinov. Reducing the dimensionality of data with neural networks. Science, 313(6786):504 507, 2006. 37
[57] Pascal Vincent, Hugo Larochelle, Yoshua Bengio, and Pierre-Antoine Manzagol. Extracting and composing robust features with denoising autoencoders. In Proceedings of the 25th international conference on Machine learning, pages 1096-1103, ACM, 2008. 37
[58] Weiwei Gu, Aditya Tandon, Yong- Yeol Ahn, and Filippo Radicchi. Principled approach the selection of the embedding dimension of networks. Nature Communications, 12(1):3772, 2021. 51
[59] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.035300 2016. 51
[60] Devansh Arpit, Stanistaw Jastrzębski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S Kanwal, Tegan Maharaj. Asja Fischer, Aaron Courville, Yoshua Bengio, et al. A closer look at memorization in deep networks. In International conference on machine learning, pages 233-242. PMLR, 2017. 51
[61] Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparame- terized neural networks, going beyond two layers. Advances neural information processing systems, 32, 2019. 51
[62] Peter I. Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117643):30033-30070 2020. 51
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main contributions and scope of the paper are detailed in the abstract
and Sect. 1. Theoretical foundations are in Sect. 4 and Appendix C, while Sect. 5 and Appendices F to H provide solid empirical evidence.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, please see Sect. for limitations.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model cell-specfiiaatinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
15

---

Answer: [Yes]
Justification: We provide the assumptions and complete proofs of the theoretical results in Sect. 4 and Appendix C.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Detailed descriptions of all the information necessary reproduce the results are provided in Sect. 5.1 and Appendix E. We also provide code and instructions to reproduce the results in our repository.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
16

---

reproducible, they 5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
The sources of the publicly available datasets we use are detailed in Ap- pendix 1. and the external codes used in experiments are listed in Appendix E.4. We also provide code and instructions to reproduce the results in our repository.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://ipps.ccppbbicc quides/CoodeSubmissionooooo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The key experimental settings and details are presented in Sect. 5.1, and the full details are provided in Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Shaded regions (in the imbalanced constraints results and hyperparameter sensitivity plots, i.c., Figs. 3, 6, 10 to 12 and 19 to 22) and error bars (in the network structure effect bar chart, i.c., Fig. 23) indicate standard deviation over 5 runs. While the main comparison results in Table omit statistical significance due space constraints, they share identical experimental settings with the IMBO results in the imbalanced constraints plots (Figs. 3 and 10 12), where standard deviations reported.
Guidelines:
17

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi-
dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative етror rates).
If error bars are reported in tables or plots. The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification The compute resources used for the experiments described in Appendix E.4, and we also provide information on learning efficiency Appendix G.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:://cciii..ccppbbbll/tttttts
Answer: [Yes]
Justification:
We have strictly followed the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
18

---

This paper aims to contribute to the advancement of the field of Machine Learning. While our work may have various societal implications, we do not believe any particular aspect requires explicit emphasis at this stage.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: This work does not pose misuse risks. It focuses on fundamental research without deploying any models assets that require safeguards.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging. and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Yes, we credited them in appropriate ways.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
19

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use the package should be provided. For popular datasets, paperswithcode. www.thhooe..comdattseeeeee has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the datasct/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing research with human subjects.
Guidelines:
20

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy http:://eeurss.cccooomeeeccs//ss for what should or should not be described.
21

---

A Deep constraint clustering formulations
The goal of constrained clustering (CC) is to partition a dataset X' = {z, |2
;=1 into K clusters
S = {Sk k=1 while satisfying a set of pairwise constraints C = {(a 4, y:) )1) i==1 Each constraint (a,, b, y4) requires that instances za, and Th, be assigned the same cluster y/ 1, or different clusters if y/ = 0. To solve this task, deep constraint clustering (DCC) methods employ deep encoder Ja : X + C RRP, parameterized by Φ, to embed each instance into latent representation
2 {z, 1 Depending how the latent representations E are utilized to satisfy constraints and perform clustering, existing DCC methods can be categorized into two paradigms: end-to-end DCC and deep constraint embedding.
2, = fa ) thereby forming the representation
End-to-end DCC. End-to-end DCC introduces additional anchors A structure Z, enabling soft cluster assignment Q that satisfy constraints An activation function σд 2 - Q maps each 2j soft assignment 9; a=(z) K where A K-1 is the probability simplex. Typically, A consists of K class weight vectors classification layer, and is combined with f to form the classifier ha.)(x) = (f( Alternatively, A can be independent learnable parameters requiring specific initialization. A generic anchor-based pairwise loss function used in end-to-end DCC is defined as:
C(o C
This loss function measures how well Q satisfies C, enabling joint optimization of ø and A.
Deep constraint embedding. Deep constraint embedding methods independently trains f& to learn latent embedding representation Z that satisfies constraints C, by minimizing the distances between positive pairs and maximizing those between negative pairs. Such representation learning operates without anchors and is driven by generic anchor-free pairwise loss function, defined as:
[C|
C(fxiC)
C
Optimizing this loss encourages Z to faithfully encode all pairwise constraints, thereby enabling CC be treated an unsupervised clustering task to determine S.
In both DCC paradigms, the encoder fø can be paired with decoder 9 Z + X, parameterized by Φ', to form a deep autoencoder. This configuration leverages unconstrained instances in to enrich the representation in Z.
B Algorithms
In this appendix, present SpherePair CC algorithm and the PCA-based cluster number inference algorithm introduced Section 3, as detailed in Algorithms and
22

---

Algorithm SpherePair constraint clustering
I. Angular constraint embedding learning Input: Training dataset X, constraints C. training epochs T, batch sizes B_ and |Byl embedding dimension D, trade-off factor A, parametrized autoencoder with encoder fø and decoder I Initialize the autoencoder parameters: Φ and 6
for t 1, .T' do
Sample mini-batches B, {(a;, b;, yi | from C. and B = { from X
Obtain latent embeddings: 2; = f (z,)) Va, E
Obtain reconstructions æ;j, Vay E X by Eq.
Compute gradients 0 and 0C dΦ 0ạ
with L (in Eq. via Cang (in Eq. 1) and Crecon (in Eq.
Update Φ, ø' using stochastic gradient descent (SGD): & &'. x- SGD(0),11 & (-11 0z end for Output: Optimal parameters, o² and ø²*
0C 8C
II. Clustering on spherical representations
Obtain the optimal representations Z' {S (a,,)) | |x|
Obtain the spherical representations Zophere by Eq. 5
Clustering with chosen algorithm Clustering( (): 8 Clustering( (2pher))) S [8 km
III. Prediction unseen instances Input: Test dataset X' (A' n. = 2)
Compute latent centroids [ua]e= of S based on Zyphere
for Vo E X do
Obtain the spherical representation sphere Norm (Sor (i))
Assign to cluster k* where ks = arg ming Og : end for
Algorithm 2 PCA-based cluster-number inference
Input: Spherical representations yyhhere C RD, training negative constraint subset C ((a b,, 0)} CC covering all true clusters, tail ratio hyperparameter with 0 p <<
Obtain subset of Spphere involved by C=: Zyteere = {*a., bb, I (a,, b; 0) CT} Zyphere
Conduct PCA on ,hhere to obtain all top-d subspace projections { { Id=1
(d) (D)
for d = 1 to D do Compute inter-cluster angles within 2pos obtain ( (02m0 204 ba,, ECC]
Select the p-fraction smallest inter-cluster angles M(4) Sortp(((1) where Sort,
is operation that sorts all members of the set (4), retaining only the [p [C-11 minimal elements.
Compute tail average 8, (())( end for
Identify the onset of the plateau sequence (5a) d=1 as d' Output: Estimated cluster number K d +
C Proofs
In this appendix, we provide proofs for Proposition 4.1, Proposition 4.2, Corollary 4.3, Theorem 4.4, Corollary 4.5, Theorem 4.6, and Corollary 4.7.
C.1 Proof of Proposition 4.1
Proof. Recall that Lang in Eq. takes the form
c
Lang
ye log Sim(a,, bi) + (1 vi) log(1 - Sim(a,,b:))
23

---

where
Sim (as by) =
cos (zo,
=0,
+ +1,
if y; = 1,
2 cos (min (w O
20c σ)) +
if yi 0.
Suppose there is an 2 = {z}}
| R such that Lang = 0 thus satisfies all pairwise relationships
{(a,, bi, vi) derived from the ground truth partition S without causing conflicts. Consider two cases:
1. Fa Lb, Sg with y; To achieve zero loss for the corresponding positive pair term in Cang. we must have Sim(a; (a; b.) and this implies cos (0=;, xx, Hence,
0,
implying that any two instances in the same cluster St must lie at angle of zero degree in the optimal angular representation Z
2. Fa; E St. Tb, E St. with k * k and y; 0. To achieve zero loss for this negative pair, must have Sim bi) By definition, this simplifies to cos (min(w 00;, *1," л)) Thus, min(w 0zg 00g, = x)) æ. Consequently, =t 2 ग,, leading to
Therefore, any two instances that belong to different ground-truth clusters must have their feature vectors separated by an angle of at least E in Z
Since these two conditions hold for every pair derived from S and collectively yield zero loss, follows that for each zz E St and xy S
if K, k
0
C.2 Proof of Proposition 4.2
Proof. We establish the proof of conditions (i) and (ii) by showing both necessity and sufficiency.
Necessity. Assume that there exists some - [ C R2 satisfying the conflict-free condition in Proposition 4.1 and that, for each constraint (a,, b;, y:) from S", the angle 0z;, =i can uniquely determined by (a,, b, y:). We show that all cross-cluster angles (02z.27. 03 Sk. By E ) must be the same.
By Proposition 4.1, any negative pair (zj, 0) from different clusters satisfies 0 O2j,ez, g. Suppose, for contradiction, that 2 is not equidistant among clusters. Then there exist two distinct cross-cluster pairs whose angles differ; let
= min Oz) 2. E Si By E S
be the smallest cross-cluster angle, and let 0z: 02g,n be strictly larger cross-cluster angle. By conflict-free condition, Ozz,z; 2 g. certainly 6 :z: Σ. For the negative pair (u, v, 0), the constraint alone enforces angular separation least but does expand the angle 0z Hence the separation 0z:,z: in - cannot be uniquely determined by the negative constraint (u, v. 0), contradicting the hypothesis. Therefore, necessary that 2" be equidistant among clusters.
24

---

Sufficiency. Conversely, assume that Z" is equidistant among clusters: every cross cross-cluster pair has the same angle 0 > Then: (i) For each negative pair J'. 0), we have 0zg,2 0- If we set = w' . then by Proposition 4.1, every cross-cluster angle satisfies separation I - 0" Hence each negative constraint (j.j'.0) 0) can uniquely determines each angular separation 22 in this equidistant z (ii) As for any positive constraint (i,J", , 1), Proposition 4. forces each intra-cluster angle to be 0. Thus each positive constraint (i,j', 1) can also uniquely determines each intra-cluster angle in z*.
Hence, the necessity and sufficiency of conditions (i) and (ii) in Proposition 4.2 are shown.
C.3 Proof of Corollary 4.3
Proof. Recall from Eq. 1 that the average angular loss is
ICI
Lang
yo log Sim(as, b.) (1 - vs) log - Sim(a bi)))
C
where
cos Oza, [cos(22,, +1, if yt = 1,
1
Sim(a;;b.) b.)
2 cos(mnn((w 10, x1) + if yi 0.
Given Lang I E with 0 <E< 1
Positive constraints.
For any (ai, bi, E C, its individual loss term is et =
cos (00000,,.20) .o,,
log
2
Since the average loss is at most e, each term satisfies et S E hence
cos O sm; mb
+
|Cls
cos(O==,, 2e -0--
Therefore
0 1
arccos 2e |C -1) (+) -11e
For small |C|s, a Taylor expansion of e |C|e and arccos gives A (s) = 2 /CL.
Negative constraints. For any (a;, b;, 0) E C with O Ozayring < the loss term is
cos(w oz,, .., +11
4 =
- log
2
The bound E7 < |C| implies
1 cos(w zn, sb.
2 c -C|s
cos(wOzn,Aae
1 1 - 2e 110
2
Since 0 0z., :b; is close _.
write
w w0z..
2 π - arccos(1 -10k),
which rearranges to
2ag arccos 1 - 2e 11-1) (E))).
Again, for small [C|s, Taylor expansion yields (E) 2//CIE
w
Combining the two cases gives the desired bounds in Corollary 4.3.
25

---

C.4 Proof of Theorem 4.4
Proof. We reformulate the statement as geometric problem of arranging distinct unit vectors in RP, ensuring that the angle between any two distinct vectors remains constant. This arrangement satisfies the "equidistant clusters" condition described in Proposition 4.2.
Let us denote these vectors as
{n) U2 uk} C
IR
| = 1,
with the property that
Ouy, uyy 0r for all S k: + k' & K.
We show that such uniform arrangement exists if and only if D 2 K 1, and derive the bounds of H for different D.
Case (i): < -. Assume, for contradiction, that there exist K unit vectors fu uk C
RD with D < K and common angle Hr > O. Let cos 0 Consider the K x K Gram matrix G of these vectors, where
Gú = u, u.uug = 1, if = J. if
We may rewrite G' as:
G= c) + c.,, x identity matrix and is the K K matrix of ones.
where /
To identify the cigenvalues of G, note that // has one eigenvalue K (with eigenvector 1 = (1,...,1)7))
and K eigenvalues equal to O. Hence G inherits:
One eigenvalue (1 --
= 1 + c(K 1), associated with 1.
- eigenvalues (1 - = 1 c, corresponding to any vector orthogonal to
Since cos 0* < (ensuring the K vectors are pairwise distinct), it follows that 1 - 0. Thus has at least K strictly positive eigenvalues, which implies
rank(G) K-1.
On the other hand, because all u, lie in RD, the dimension of the subspace spanned by them is at most D, so rank(G) < D. Therefore we must have
K-1 < rank(G) D,
contradicting < 1. Hence, there can be no such K unit vectors in R. whose pairwise angles are all equal, and consequently, no valid w (i.e. no angle 6*) realizes the equidistant configuration when < 1
Case (ii): D K - In space of dimension exactly K - 1, it is both necessary and sufficient that the K vectors form a regular simplex. The same Gram matrix argument above now forces rank(G)) K 1, hence the unique way for K vectors remain all equiangular
1
c(K - 0
0" = arccos
K -
K-1
In terms of Proposition 4.2, the uniform cross-cluster angle 0", w wt must satisfy
π
π
8"
w²
arccos
This w" is unique for D = K -
26

---

Suppose we wish to place K unit vectors fu....., U } C R² so that every pair of distinct vectors has a common angle 0* 0. Let cos 0* and form the corresponding K x K Gram matrix as before. As in the preceding cases, we may rewrite G as G (1 + cJ, where 7 the K identity and J is the K K all-ones matrix. its eigenvalues are
Case (iii): D 2 K.
A1 = c(K - 1), X =..... A = 1
For G' to be a valid Gram matrix of real vectors, all eigenvalues must be nonnegative:
1
1, 1+ 1) 2
K K-1
Since c < 1 when the vectors are mutually distinct, we combine these to conclude
K-1 ccl = 0"
arccos(
K feasible. Equivalently, in
Thus, whenever 2 K, any common angle up to arccos( R-1 terms of we obtain
arccOs
Geometrically, this reflects the fact that we only need subspace of dimension K 1 to place K equiangular vectors, and having additional dimensions (D 2 K) does not tighten the required angle- it simply allows the same arrangement (or more flexible ones) to fit in digeer-di ambient space. Hence, any w above the threshold // arccos(
remains valid when D 2 K.
Combining all three cases leads to the desired conclusions:
(i) When D K such a valid does not exist.
(ii) When D K the unique valid w is πT arccos( R-T).
(iii) When D 2 K, the range of valid w values is relaxed to 2 T// arccos( R--))
C.5 Proof of Corollary 4.5
Proof. Given D > K, by Theorem 4.4, the admissible set is 2 t/ arccos K- minimal admissible value is
Hence the
π
miin (K)
arccos( K-1
We now establish the stated properties:
Bounds.
For K 2, arccos(-1) n., thus wiin (2) = T/T For every K 2, -
(-1,0), hence
arccos
I m))))
w (K) 2.
K--
Therefore
Wiin (K) for all K >
Monotonicity.
If2 K1 < K2, then Ki-1 <
1
1
Since arccos(-) is strictly decreasing
Ko-1'
on
1].
arccos
Ki-1
arccos
Kz-T
and thus
π arecos(
π
wit (K1)
wit (K2).
arecos(
K
Kz-I
Hence Win (K) is strictly increasing in K.
27

---

Limit.
As K O0, we have 1
KK- + O, so by continuity
arccos
-R-1)
arocos(0)
w (K)
2.
aiccos( -K-1)
Combining the ahove completes the proof.
C.6 Proof of Theorem 4.6
Proof. For notation, let {us) C CRP be the K cluster-representative unit vectors on the sphere (i.e., the common location of each cluster in sphhere), let pı: | > with Σ Ph: be
the cluster frequencies, and set the sample mean
m
Pk Uk-
After standard centering by m, the k-tt cluster maps the common centered vector
Uk == u
m
(k = 1, K,...,K),
For an optimal spherical embedding sphere all instances in cluster S coincide at ug therefore after centering they all coincide at kk. Denote
span UI c CRD.
Step 1 (Centered data lie in a (K dimenssiol subspace and Im(E) U). Since
> k= Pk Ex Pk (us m) = 0, the family (wx} is linearly dependent and hence dim
< 1- On the other hand, (uz} are the K affinely independent vertices of regular simplex, whose affine hull has dimension K - 1; translating this affine hull by -m yields the linear subspace U through the origin. Hence dim 1
Let the covariance after centering be
Σ
[Norm (2j) m) - -m) = Σ 1=1
Ph UR
For any L have vj w 0 and thus Ew 0, so Im(E) S U, where Im(E) is the column space of M Conversely, for any u e U. {0), since {vu} span U, there exists k with U # 0, and therefore
u Eu
Σ Pk (1) u)² 2 0.
Thus Σ is positive definite on U and vanishes on U-, which implies Im(E) = U. This conclusion does not depend on the specific values of }p&} beyond pı > 0.
Step 2 (For d K - 1, PCA projection preserves all pairwise angles). Let Wa be the d-dimensional PCA subspace spanned by the top d eigenvectors of E. By Step 1, is posi- tive definite U and zero U hence its nonzero eigenspace is exactly U. Therefore, for any 2 K dim
UCW.SUeU- RD
where @ denotes the direct sum of subspaces. (Norm(z;) - m) lie in U and each Norm(z;) m equals some tg. Consequently, for any Ug. the orthogonal projection onto Wa satisfies Pat; us because E U C Wa. PCA then applies an orthogonal change of basis inside Wa (and, when D, an orthogonal transform in the full space). Orthogonal transforms preserve inner products, norms, and hence angles between any nonzero pair of vectors. Therefore, for any pair (j.j") with nonzero projections and any d, d' K
0 2(1)) (000 = 0 2ger)
28

---

proving part (i).
Step 3 (For d < K 1, global invariance cannot hold). We work in the nondegenerate regime where the pairs compared satisfy = * + 2 i.e. Pavk o for the involved clusters. Since dim U = K > d, one can choose indices I = (A....., ka+1} so that Park, * 0 for all T, and {ur, )d+] are linearly independent U. Form the matrix X = [0k]
Tkets IR Dx(+1)) with Gram matrix G == x E 1R(++))((++1) which is positive defimite (hence rank(G) = d + 1). X PaX, whose rank is at most d because P.X has columns in the Let G : dimensional subspace Wa.
Assume, for contradiction, that the angle invariance of part (i) holds for all admissible pairs among the set {ux, 1d+1 i.c., for every T # r' with PaUk, Pauk,, * O,
( PAOK,))
(UR,, vk.,)
P R. | || 1kke
|
Setting hT = P || > 0 and H == diag(h), ha+1). 1, the above identities imply
G.p' = PoUK,, = h,, (00,, vk,.), hence h= IH
Since H is invertible, rank(G) ra d 1, which contradicts rank(G) S d. Therefore, when d < - 1, the invariance across in (i) cannot hold for all admissible pairs, proving part (ii).
C.7 Proof of Corollary 4.7
Proof. We follow the notation in Theorem 4.6: let {ux]k= R. be the K cluster-representtttve unit vectors on the sphere y, let Pk: = | > 0 with Ek= Pk: = be the cluster frequencies, Σ k= Pk uy. After centering by m, each cluster St collapses to
and let the sample mean be common vector U3 U where 1,
1...., ... K. Let U = span uK R...
From Appendix C.6, we know that dim U K and the image space of the covariance matrix after centering is exactly U. Hence when d 2 K 1, the PCA subspace Wa contains U and therefore Par 0g. Subsequent orthogonal transformations preserve all pairwise angles.
= 1. Since m = p1 u1 + P2 with p2 = 1 - PI. we obtain (i) Case K = 2. Here dim
U1 = (1 - (1) - u2).
- 12)
Thus vi and v2 collinear in opposite directions, so their angle is always Any PCA projection with d 2 = K- - only applies an isometry within this line (and possibly an orthogonal transform in the full space). leaving the angle unchanged. Hence 6y for all 1.
(ii) Case K 2: proving 81 = and invariance for 2 -.
1. 61 = O: In the one-dimensional PCA projection, all vectors Uy are mapped to single line. Since > 2 and each Pk O, there must exist two distinct clusters whose projections lie on the same side and are nonzero, yielding an angle of O. Hence ö 0.
2. Invariance for d 2 K - 1: By Theorem 4.6, for any admissible pair (j.j"), when d 2 K 1 the angle 8 "و(n) equals its counterpart at K (or D). Therefore the minimal cross-cluster angle da is constant for all K 1; denote this constant by d..
3. Upper bound of 8.: Let = cos 0* be the common inner product among {uc). The Gram matrix of U [u ... ux is G (1-c) cl1 For any * k, consider 22 = m and Uy u m. Derivable from the Gram structure, angle 6 derryy depends only on {p:): letting S >K p2, one obtains
S Ph Pk
cos O mn.
(6)
v(1 - 2pk + S) 2pL + S)
29

---

When P1 =... Px = K = cluster angles coincide, so 6, arccos - xー yielding the upper bound. This bound is attained when clusters are balanced.
k and (6) gives Per arccos(- K- All cross
1
4. Lower bound of 6,: For given pair (k, k), write
Pa PM EiAR, S Pt > 0 and 8 = Eigh, p. so < $ v p². Equation (6) can be rewritten as a function f(s). One checks that f(s) is nondecreasing in s on the relevant interval. Hence the maximal value of cos Ovr..y. (i.e., the minimal angle) occurs
,² which corresponds to the case when all remaining probability mass r concentrates in a single cluster. In this regime, one can show cos Vv S 1. thus cos O... 2 arccos( ())
Equality never attained when all > 0, but as some pt + (the others tending to 0), der.eg approaches J. Therefore 6, > 3. with the infimum approached when one cluster dominates.
Thus, for K = 2, we proved 69 = x for all d 2 1. For K > 2, we established 61 = for d 1, da takes constant value 8,; and
8. E ( arccos(
with the upper bound arccos(- in the highly imbalanced case.
1 K-1 attained in the balanced case and the lower bound z approached
D Visualization of SpherePair representation learning in angular space
To demonstrate how SpherePair learns equidistant spherical embeddings for different numbers of clusters angular space, we perform 3D visualisation experiment using subsets of the Reuters dataset [51], following the preprocessing steps outlined in the work [50]. Specifically, the original training partition consists of 10,000 instances from four root categories: Corporate/Industrial (CCAT), Economics (ECAT), Government//occall (GCAT), and Markets (MCAT). Their respective instance counts in this training portion are 4,066 (CCAT), 2,888 (ECAT). 2,202 (GCAT), and 844 (MCAT). We form three data subsets by taking the first 2, 3, and all 4 categories, thus yielding scenarios with K = 2, 3, 4. For each subset, we randomly sample 10k instance pairs and derive pairwise constraints based on whether the two instances belong to the same ground-truth category. Naturally, the constraint distribution varies across different K due to the differing subset compositions.
Using the three data subsets and their respective 10k constraints, we train SpherePair autoencoder comprising a fully connected encoder with hidden layers of sizes 500, 500, and 2000 (mirrored by a symmetric decoder) and a 3-dimensional embedding layer (D 3). As guaranteed by Theorem 4.4, we set the negative-zone factor w = // arccos( - Rー) as it is always valid when D 2 K 1,, to ensure that the learned embeddings can form an equidistant arrangement on the unit sphere.
Fig. 7 illustrates the evolution of the resulting spherical representations Zyphere over the course of training. As the training progresses, the data points gradually separate on the 3D sphere, and the final embeddings form nearly regular simplex configurations in the (K - 1 -)-dimensional subspace of Rs, consistent with our theoretical insights in Sect. Worth noting, despite the imbalance instance counts among different categories, the formation of equidistant spherical clusters is not contingent on ground truth clusters being of equal size. Thus, this 3D visualisation vividly illustrates and validates the theoretical insights into our proposed SpherePair representation learning framework.
E Details of experimental settings
In this appendix, we provide a detailed description of our experimental settings to ensure that all necessary information is included and our results are fully replicable.
E.1 Datasets
We provide detailed descriptions of the benchmark datasets employed for evaluation in experiments.
30

---

epoch
epoch
k=
==a
K=
Figure 7: Evolution SpherePair embeddings on a 3D unit sphere for datasets with K = 2, 3, and 4 clusters. Each row corresponds to of the three subsets derived from the Reuters dataset, and each column shows a snapshot of the embeddings at particular epoch. Different marker colors denote different ground-truth categories, and dashed lines represent randomly sampled pairwise constraints (blue for positive, red for negative). embeddings and highlight, in black dashed lines, the connections from the origin to each cluster centroid obtained by running K K-means on Ziphere-
the final column of each row, we illustrate the converged
CIFAR-10 [45]: Consists 60,000 real-world 32x32 color images spanning 10 classes, each class containing 6,000 images. CIFAR-10 has been widely used as a benchmark in DCC research [11, 16, 14].
CIFAR-100-22 [45]: more complex extension of CIFAR- 10, also having 60,000 real- world x2 color images. CIFAR-100 originally contains 100 fine-graines classes, which can be grouped into 20 superclasses. our experiments, we use these 20 superclasses (each containing 3,000 images) as the ground truth rather than the 100 classes.
FashionMNIST [46]: Contains 70,000 grayscale images of Zalando fashion products (10 categories) with size of 28x28 each. It is pre-split into 60,000 training images (6,000 per class) and 10,000 test images (1,000 per class). FashionMNIST also serves as a benchmark
for DCC evaluation such as the methods [16, 12, 13].
ImageNet-110 [47]: A subset of ImageNet [52] with 10 classes, each containing 1,300 randomly selected color images (13,000 in total). The chosen classes are n02056570, n02085936, n02128757, n02690373, n02692877, n03095699, n04254680, n04285008, n04467665, n07747607. This ImageNet- 10 is commonly used as a benchmark in both DCC [14] and unsupervised deep clustering 53).
MNIST 6 [48]: Contains 70,000 grayscale images of handwritten digits (0-9), each of size 28x28. It is pre-split into 60,000 training images (6,000 per digit) and 10,000 test images (1,000 per digit). MNIST serves as benchmark in DCC evaluation such as the methods
[11, 16, 12, 13].
Reuters [51]: A subset of the RCV17 corpus large- newswire collection of 804,414 English stories). We use the preprocessed version from [50], which provides tf-idf features
-CIAAR-10 webpage:
"CIFAR-100-20 webpage: http://wwww.....oooooooottt-tttd
'NSS repository: http://ghhbbb.omm/aaddoossssssst
'ImageNet webpage: https//image-nee.org
"MNIST webpage: http://aan.eeuun.oom/eedd/etei
"RCVI wehpage: htts:://rec.. www.eec..iitttggoe mis..goov/anuu/eeteevreeeeere.r
'Preprocessed Reuters repository: https///gihubb.oo//pissswwpgggg
31

---

on the 2,000 most frequent words across documents sampled from four root categories: Corporate/Iddustraal (CCAT), Economics (ECAT). Government/Social (GCAT), and Mar- kets (MCAT). The dataset is pre-split into 10,000 training samples and 2,000 test samples, with the four categories containing 4, 4,066/2,8888 288.28888/2,2028844 training and 774/582/471/173 test samples, respectively. We treat these four categories as the ground-truth clusters in our experiments. Reuters has been widely adopted as benchmark in DCC research [16, 12, 13].
STL-10 [49]: Comprises 13,000 96 color images from 10 classes, each class having 1,300 images. STL-10 is adopted by various DCC works [11, 13, 14].
RCV1-10 10; Another subset of RCV1' with highly imbalanced class distribution. We randomly selected 10 categories (C14, C18, C313, C42, E, E311, GDEF, GODD, GWELF, M13) from the 103 available topics and removed documents carrying multiple labels within this set, yielding 177.669 single-label articles with the following class counts: 6,634 (C14), 51,145 (C18), 1,042 (C313), 10,954 (C42), 40,950 (E21), 1,679 (E311), 8,492 (GDEF), 2,743 (GODD), 903 (GWELF), and 53,127 (M13). We treat these 10 categories as the ground-truth clusters in our experiments. Tf-idf features were computed on the 2,000 most frequent word stems, yielding the RCV1-10 subset as realistic benchmark for imbalanced constrained clustering.
E.2 Baselines
We provide the detailed information on the state-of-the-art deep constrained clustering baselines used in our comparative study.
VanillaDCC [21]: A straightforward end-to-end anchor-based DCC model grounded in the Meta Classification Likelihood (MCL) loss:
LMCL = |C|
ys log Poo, + (1 -1--3 y4) log - Poo.):
where Poo, = qa, 9b, E [0, 1] is a pairwise co-occurrence likelihood integrated into a logistic loss. Here, la. and go are the soft assignments of constrained data pair (æay, (b,)) ) to K clusters. By minimizing this loss, VanillaDCC learns cluster assignment matrix Q = (g, ) that respects the constraint set
VoIMaxDCC [14]: An extension of VanillaDCC that modifies the MCL-based loss to handle confused memberships and incorporates an additional geometric regularization term controlled by a trade-off factor A. Specifically, VolMaxDCC introduces matrix B (treated as an optimization variable and derived from a confusion matrix) into the pairwise co-occurrence likelihood and adds volume maximization regularization term:
LvalMax
yi log P', + (1-y; log(1 -P.,))))) Poo.)) > Alog det TQT)). Q).
|C|
Here P',,, = Bq, पT, E [0, 1] is the modified pairwise co-occurrence likelihood, and treated as the cluster assignment matrix. The first term in LwsMas adjusts the similarity measure to account for membership confusion, while the second term serves as a geometric regularization that encourages maximization of the volume of the Gram matrix Q Q, thereby enhancing the separability and distinguishability of clusters. Both B and Q are optimized during training. The choice of the trade-off factor À requires tuning to balance these effects. Overall, LvsiMax enables VolMaxDCC to handle noisy constraints caused by annotation confusion while promoting well-separated and distinguishable cluster assignments.
CIDEC [12]: An end-to-end method that balances unsupervised representation learning and constrained clustering within a multi-task joint optimization framework. Specifically, CIDEC first encodes data into a latent space via a deep autoencoder and initializes K learnable cluster anchors
10 webpage: http://sssstnnoooo.dddd-aaaaoree
We provide the preprocessed RCVI-10 subset: http://ghhhlloooappepppriiihhhhh
32

---

using K-means, where K corresponds to the known number of ground -runh classes. It then alternates between supervised and unsupervised training phases during each epoch. In each iteration, the model jointly refines the autoencoder parameters and cluster assignments by combining the the following learning objectives to form multi-objective loss function:
ii) The deep embedding clustering objective from [50, 40J, which minimizes the KL divergence
|2
log Pit 4zk
DEC
Pik
1=1
between the soft assignment distributions 9, = (qy1, 4y2:
9jK) and target distribution
Pj (P...P.2......Pjp... Specifically, for each sample j. the target distribution is calculated as
G
Pik ΣV= /
where fA.
Σ
Ojk-
$=1
enhancing the influence of assignments with higher confidence,
(ii) LMCL for incorporating pairwise constraints, and
(iii) A reconstruction loss preserve the intrinsic data structure.
This process employs two hyperparameters: Å to balance the clustering and reconstruction losses, and X2 to weight the contributions of positive and negative constraints within the MCL-based loss. When no constraints are available, CIDEC reduces to the unsupervised clustering model IDEC [40].
DCGMM [13]: DCGMM combines a deep generative model (i.e., a variational autoencoder- like architecture) with conditional Gaussian mixture framework to handle pairwise constraints. Specifically, DCGMM models each cluster as a Gaussian mixture component, where the number of components is set to the known ground-truth class count K. It incorporates constraint information by conditioning on positive and negative pairs, thereby reshaping the latent variable distributions. Additionally, DCGMM assigns a weight [Wayl to each pairwise constraint between æ, and zj. reflecting the degree of certainty in that constraint. During training, it jointly optimizes (i) the variational likelihood of the autoencoder and (ii) constraint-based term weighted by [W.y that pushes instances from positive pairs into the same mixture component and instances from negative pairs into different components. When no constraints are given, DCGMM reduces to VaDE [54], an unsupervised clustering model.
SDEC [11]: SDEC combines anchor-free constraint loss with the anchor-based deep embedding clustering objective from [50] to learn cluster assignments that satisfy constraints. Specifically, SDEC minimizes weighted sum of the unsupervised clustering loss LDEC, and Euclidean distance-hased constraint loss. The latter encourages positive pairs to be close in the latent space while pushing negative pairs apart:
IC| Σ (2 - 1) d(zz,, xb.))
Lpuclidean
|C|
where d(za.: 2b.) objectives, optimizing the combined loss
||a., 2b, l1l. SDEC introduces a trade-off factor À to balance these two
LSDEC LDEC + ALEuelidean
When no constraints are available, SDEC degenerates to the unsupervised clustering model DEC [50].
AutoEmbedder [16]: AutoEmbedder also learns pairwise embeddings in Fuclidean space but does not include any unsupervised clustering loss, making purely anchor-free for deep constraint embedding, AutoEmbedder uses an MSE loss based on a truncated Euclidean margin:
[cl
LMSE
min(mma((0, (t,)).))))))....)...)))))))))))) 23 a(1 a(1-9;))
C
where d(za, 2b,) ||z,, 2b, l2. and is manually chosen margin for the Fuclidean distance. With EMSE, AuboEdbedder learn representations that pull positive pairs together while ensuring that negative pairs remain at least margin apart.
33

---

CIRAN
D2 15
100
IN:ST
Decara
STL/C
TD40-1
Figure 8: Distribution of randomly sampled constraints across ground-trutt clusters. Each heatmap is K x K symmetric matrix (represented by its upper triangular part) that illustrates the fraction of constraints originating from each corresponding pair of clusters (k, k'). The fractions in all matrix entries sum to 1 for each dataset.
E.3 Protocol
We provide the details of the experimental protocol used in our experiments.
Data splitting. In accordance with the protocol specified the main text (Sect. 5.1), we adhere to the original pre-split training/test partitions for FushionMNIST, MNIST, and the Reuters subset. For the remaining benchmarks (CIFAR-IK) 10, CIFAR 100-20, STL-10, ImageNet- 10, and RCV1-10), we randomly split each dataset into 80% for training and 20% for testing, resulting in 48,000/12,000 samples for training/testing in CIFAR-10 10 and CIFAR- 100-20, 00,400/2,600 STL-10 and ImageNet- 10, and 142, 135/35,553 in 1-V1-10. Following [14], we then reserve 1,000 samples from each training split to form validation set, used solely for hyperparameter tuning in baselines that require (e.g., VolMaxDCC [14], AutoEmbedder [16]).
Constraint set generation. For our standard experiments, we generate pairwise constraints via random sampling of training data pairs according to their ground-truth clusters. Concretely, for training set with N samples partitioned into K ground-truth clusters S = {S {S we randomly select pairs of samples and assign positive constraint (34 1) if both samples lie in the same cluster (i.c., Vo, Tb, E St,, or a negative constraint (y, = 0) if they come from different clusters. In principle, there are up to (1xx1) Xx' (1) possible constraints, among which each cluster St can yield up to |Sğ] (15) 11) positive constraints and each cluster pair (Sy. S with k' * k can yield up to 1S:1-155 negative constraints. Consequently, the proportion of positive and negative constraints from different ground-trutt clusters reflects the underlying class distribution. Fig. 8 visualizes the distribution of the randomly sampled constraints (of any chosen size, e.g. 1K, 5k, 10k) the form of K x K heatmaps for the eight datasets. Unless otherwise stated, our experiments use this random sampling strategy for constructing constraint sets.
Imbalanced constraint set generation. For each imbalanceed-constrriin trial, we generate group of three sets, IMBO, IMB1 and IMB2, evaluate performance under progressively skewed constraint distributions. We fix a size ratio IMBO) IMB1| [MB2] = 1 5 10, and designate the first ground-truth class in each dataset as the "IMB cluster," from which additional negative constraints are predominantly sampled. Concretely, we form IMBO of size [MBO| by randomly sampling pairs of training data, labeling them positive if both samples lie in the same ground-trutt cluster negative otherwise (the same procedure as in Fig. 8). We then obtain IMB1 by adding (JIMB1| IMBO]) extra negative constraints linking the IMB cluster to other clusters, and further enlarge IMB1 to IMB2 by appending [IMB2] - IMB1|) similarly imbalanced constraints. As a result, IMBO C IMB1 C IMB2, ensuring that any performance decline from IMBO to IMB1 or IMB2 cannot attributed to removing earlier constraints.
34

---

CFAI
Horder APE
MM5
UNST
7727
Torr M0
noyire
Figure 9: Heatmaps of imbalanced constraint distributions, K x K symmetric matrices (represented by its upper triangular part), for eight datasets. Rows correspond to datasets, while the three columns represent IMBO, IMB1, and IMB2, with sizes in the ratio of 1 10. To form imbalanced constraint sets, a single "IMB cluster," corresponding to the first row in each heatmap, is selected to receive additional negative constraints connecting other clusters. The heatmap intensity at entry (k, k') indicates the fraction of constraints connecting ground-truth clusters & and & reflecting how IMB1 and IMB2 become increasingly dominated by the IMB cluster's negative constraints.
35

---

Since we select the same IMB cluster and preserve the above ratio for each dataset, every group of three sets exhibits a consistent inter-cluster distribution. Fig. illustrates this for the eight datasets, with each row corresponding to one dataset and the three columns showing IMBO, IMB1, IMB2 as heatmaps of size K' x K' the highlighted area in each IMB1 and IMB2 heatmap involves the IMB cluster. We can observe that IMB1 and IMB2 gradually become dominated by negative constraints involving the IMB cluster. In Fig. 3, we report empirical results for ([IMBO), [MBB]] [MB2]] = (10k, 50k, 100k), while additional experiments with varying constraint set sizes can be seen in Appendix F.2. These additional constraint sets are generated using the same methodology and exhibit similar cluster-wise constraint distributions.
Cluster number inference. To evaluate our PCA-based cluster-number inference method (A (Algo- rithm 2), we apply standard mean-centered PCA [44] to the (z-normalized embeddings of instances involved in negative pairs. For comparison with alternative K-inference methods and to assess the applicability of different deep constraint embeddings, we adopt two alternative strategies, specifically "K-means + Silhouette Coefficient" and "Agglomerative Clustering + K -clusterr lifetime", which are applied to both the SpherePair and AutoEmbedder representations:
K-means + Silhouette Coefficient (SC). For each candidate K', we run K-means clustering 5 times with random initializations and compute the average SC score on a random subset of 5,000 instances. Specifically, for each instance j. we calculate the average intra-cluster distance djutta between its embedding 2j (for AutoEmbedder) or Norm( 2;) (for SpherePair) and the embeddings of all other instances from its assigned cluster Sg. We also determine diuier, the minimum average distance between 2j (or Norm(z,)) and the embeddings of instances from any other assigned cluster Sw, where k' * k. The SC score 8, for instance j is then computed as s; = (dftier - -djutaa) mmxx (fiurr dfiiler). The overall SC score is the mean of sj across all sampled instances. A higher SC indicates better-defined clusters with greater separation and lower intra-cluster dispersion. We select the number of clusters K' as K" that corresonds to the maximal SC score.
A Agglomerative clustering + K-cluster lifetime. We employ agglomerative clustering with Ward linkage [43]. which iteratively merges the closest clusters while recording the corresponding linkage distances. For each candidate number of clusters, K', let dx denote the linkage distance when the dataset is partitioned into K" clusters. The K K-cluster lifetime at level K' is defined as Adx = dg. - d A larger Ad indicates more significant increase in linkage distance, or equivalently, a longer K-cluster lifetime. This suggests that the K'-cluster partition is more stable and well-separated. To determine the optimal number of clusters, K we select K** argmax x. (Adkr). In Figs. 16 and 18, each Adg: is normalized using d2 for readability, resulting in Adk- d2
Adgt
E.4 Implementation
We provide the implementation details" 1l for our experiments.
Software and hardware. We implement all methods (except DCGMM in PyTorch 1.5.1 13 with Python 3.7. For SpherePair and AmboEnb,, we use scikit-learn's 's K-means implementation" 14 and fastcluster's efficient hierarchical clustering implementation for clustering. Experiments are conducted on Tesla V100 GPU with 16 GB of memory.
Data preprocessing. For Reuters and RCV1-10 subsets, we directly use the preprocessed tf-idf vectors. For all other datasets, we convert images into feature vectors to facilitate fair comparisons using fully connected networks. Specifically, for the 28x28 grayscale images in MNIST and MNSS, we reshape each image into a 784-dimensional vector, mirroring the methods of [11, 12, 13]. For color images in CIFAR-10, SIFAR-100-22 STL-10, and ImageNet-10, 10, we adopt
"Our source code is available on GitHub: http:://gttub..co////h/ hht.c///wwrrprpeeehhhhcehhCnhnhe 1W use the authors' implementation for DCGMM: http://stttl..commaaaaaaanniccct
PPpTTorc 1.5.1:
14 Sciiittleamm webpage: https:/scikit-llant wea.iit--aaaaorr//.... 19doocumenttiinnn.ii
15 fastcluster library: https://pypp.rrrge https//yypp.ogpppoecc//sstcsseee
36

---

the unsupervised feature extraction strategy proposed in [53]; in particular, we train a ResNet-34 [55] model for 1,000 epochs and utilize the resulting 112-dimeniional latent representations. This preprocessing is consistent with the method employed in [14]. This vectorization step enables us to apply the same standard fully connected architectures across all datasets, ensuring consistency and fairness in evaluating the baselines.
Network architectures and pretraining. For all methods except VanillaDCC and VCCMaxDCC,
we employ a fully connected encoder with hidden layers of size 500-500-2000 (following [11, 12, 13]), using an embedding dimension of D 20 for CIFAR-100-20 and D = 10 for all other datasets, unless stated otherwise. Notably, while the original AutoEmbedder [16] utilizes a pre- trained MobileNet-based CNN, we adapt it to use our standardized fully connected network to ensure fair comparison across all models. contrast, VanillaDCC and VolMaxDCC [14] adopt a distinct architecture comprising two hidden layers of size 512-512 followed by classification layer corresponding to the number of clusters K, as recommended in [14].
Except for the end-to-end VanillaDCC and VolMaxDCC, all other methods undergo unsupervised pretraining on training sets. Specifically, for SpherePair, SDEC, CIDEC, and AutoEmbedder, we utilize a two-stage stacked denoising autoencoder (SDAE) pretraining approach [56, 57], consistent with the works [11, 12]:
(i) Layer-wise Pretraining: Each hidden layer is individually pretrained single-layer denoising autoencoder for 300 epochs using 20% random masking noise and MSE loss. During this phase, the output of each encoder serves as the input to the subsequent layer, progressively refining the weights of each layer.
(ii) End-to-End Fine-Tuning: After completing layer-wise pretraining, the entire network is jointly optimized for additional 500 epochs. This phase continues to apply 20% masking noise to the inputs.
key distinction for SpherePair during pretraining the normalization of latent embeddings before decoding, as specified in Eq. 3. This ensures that the pre-trained autoencoder retains angular information critical for our clustering objectives. For DCGMM [13], we follow the authors' setting by pretraining variational autoencoder (VAE) for 10 epochs, aligning with their implementation strategy.
Hyperparameters and optimization. We provide detailed hyperparameter settings and optimiza- tion configurations for our SpherePair method and all baseline models.
SpherePair (Ours). We the negative-zone factor w at 2 according to our theoretical analysis, and set the reconstruction loss weighting parameter X 0.02 in all experiments unless varied for sensitivity analysis. For optimization, we employ the standard Adam optimizer with learning rate of 0.001. The constraint mini-batch size is set to |B,l 256,
jei and consequently, the instance mini-batch size determined by |B,|| = |/x1 [ where
X'' represents the dataset size and [C] denotes the constraint set size. Training is conducted for maximum of 300 epochs. An early stopping criterion is applied after the first 100 epochs, terminating training if the relative change in loss L (Eq. 4) remains less than 0.1 for consecutive epochs. For clustering on the learned spherical representations Z-phere- we utilize either (i) the K-means algorithm with 20 random initializations or (ii) hierarchical clustering using the Ward linkage method. For cluster-number inference, we set the tail ratio p p= 0.05 when computing the tail-averaged minimal inter-cluster angle 8a.
VCC.llaDCC. VanillaDCC is implemented straightforwardly by optimizing LMCL using the standard Adam optimizer with a learning rate of 0.001. The batch size is set to 256. Training is conducted for a maximum of 300 epochs, with early stopping triggered the relative change in the soft cluster assignments for training samples falls below 0.001 over 2 consecutive epochs. This early stopping strategy widely adopted in end-to-end deep clustering [50, 40] and deep constrained clustering [11, 12]
37

---

VoIMaxDCC. Following the VolMaxDCC paper" 16 [14], we parameterize the optimization variable B such that each element B3 = -B,x where B', is a trainable parameter and to -1 otherwise. We utilize the SGD optimizer with learning rates of 0.5 for the network parameters and 0.1 for B', respectively, and set the batch size to 128. The trade-off factor (geometric regularization weight) À is selected by searching over the range {0, 10 1 10 2, 10 -3 10 4. 100 6 based on the model's ' best accuracy on the validation set. The optimal À values identified for the datasets CIFAR-100-20, CIFAR-10, FMNIST, ImageNet-10. MNIST, Reuters, STL-10, and RCV1-10 are 10 10-4, 10-1, 10-1, 10-5, 10-2, 10-4, 10-2 and 10- respectively.
initialized to if
CIDEC. We follow the authors' recommendations by setting A = 1 to balance the cluster- ing and reconstruction losses and X2 - 0.1 to weight the contributions of positive constraints within the MCL-based loss. The K-means algorithm is executed 20 times to initialize the K cluster anchors. Optimization is performed using the standard Adam optimizer with a learning rate of 0.001 and a batch size of 256. Training proceeds for up to 300 epochs, with early stopping invoked if the soft cluster assignments exhibit a relative change of less than 0.001 over consecutive epochs.
DCGMM. Utilizing the authors' implementation, we set the constraint weights |Wy] 10,000 and adhere to their optimization configurations. However, we pretrain a variational autoencoder (VAE) for 10 epochs exclusively on the instances in the training set, rather than using all instances from both the training and test sets." !7
SDEC. We align with the authors' recommendations by setting the constraint loss weight X =10- The K-means algorithm is executed 20 times to initialize the K cluster anchors used for unsupervised clustering. Optimization is carried out using the SGD optimizer with a learning rate of 0.01 and a batch size of 256. Training continues for maximum of 300 epochs, with early stopping triggered if the soft cluster assignments change by less than 0.001 over consecutive epochs.
Ambeddbed We implement AutoEmbedder using the same fully connected encoder architecture SpherePair, ensuring consistency across models. The optimization settings mirror those of SpherePair: an Adam optimizer with a learning rate of 0.001 and a batch size of 256. Training is conducted for up to 300 epochs, with an early stopping criterion applied after the first 100 epochs, terminating training if the relative change in loss remains below 0.1 for 5 consecutive epochs. Unlike the original AutoEmbedder [16], which is based on a pre-trained CNN network with a rell-structured embedding space, our fully connected implementation requires modifications the loss function. Specifically, the MSE loss LMSE can lead to scenarios where the embedding distance for positive pairs exceeds the margin a, causing gradient issues. To address this, we introduce separate margins on and 0g for negative and positive constraints, respectively. We search for a within [1, 10, 50, 100, 500, 1000, 5000) and a2 within (100, 1000, 10000), performing hyperparameter tuning based on validation set performance, similar to the approach used for VoIMaxDCC. The optimal an values identified for the datasets -IFAR-100-200 CIFAR-1O. FMNIST, ImageNet-10, 10, MNIST, Reuters, STL-10, and RCV1-10 are 500, 500, 50, 10. 100, 500, 50, and 10, respectively, while the optimal a₂ is consistently 10000 across all datasets. This outcome is expected, as the margin for positive constraints does not contribute to the Euclidean clustering objective, and smaller margins render positive constraints ineffective.
F Additional experimental results
In this appendix, we present supplementary experimental results, building upon the experimental settings detailed in Appendix E. Additionally, we provide further insights and findings related to our SpherePair approach.
W'hile we strictly follow the authors' optimal hyperparameter search strategy, which uses ground ground-truth class label information in the validation data, such information is typically unavailable in constrained clustering tasks. 17 Based on the authors' source code, we observed that their experiments involved pretraining the VAE on all instances from both the training and test sets This constitutes transductive setting, which is unsuitable for scenarios requiring inductive learning, as is the case in all our experiments.
38

---

F1 Comparison of hierarchical clustering results
We present additional results from our comparative study. In Table presented in the main text. we reported the primary clustering analysis results for two anchor-free deep constraint embedding models, AutoEmbedder and our SpherePair, using K-means applied their learned representations. Here, we extend the analysis by presenting results for both models using Ward's agglomerative hierarchical clustering, as shown Table 2.
Table 2: Comparative performance (%) of ACC, NMI. and ARI across multiple datasets for AutoEm- bedder (AE) and SpherePair (Ours) models using 1k, 5k, and 10k constraints. The results are derived from the hierarchical clustering analysis applied to their learned representations. Consistent with the notation used in Table I, blue and black indicate training and test performance, respectively. Better results are highlighted in bold.
ACC
NMI
ARI
ACC
NMT
ART
ACC
NMI
ARI
AF:
19.7,
19.2
21.4, 20.7
5.9. 5.8
10.5, 10.8
8.9.8.5
2.1,
31.2, 31.5
37.3, 38.5
21,2, 22.1
CIFAR100-20
Ours
45.9.
46.4
46.4, 46.3
29.4, 30.5
55.0, 54.9
50.9, 51.2
37.4, 38.7
61.6, 62.6
54.8, 54.9
42.6, 44.1
AE
45.8,
44.2
51 50.1
29.4, 28.0
82.1, 83.0
77.4, 78.3
72.3, 73.9
84.8, 85.3
79.4, 80.0
75.2, 76.5
CIFARIO
Ours
83.7, 84,3
77.0.
77.1
72.3, 73,0
89.5, 89.4
81.5, 81.1
79.8,
90.5, 90.2
82.4. 82.0
81.3. 80.8
AE
40.7.40.2
42.2. 40.8
25.7
60.5,
59.5,
48.2
66.6, 67.1
65.0, 64.6
53.4
FMNIST
Ours
66.5, 67,8
64.3, 63.1
51.2. 52.3
79.4. 79.2
7188. 70.8
65.4. 65.2
84,4, 83,7
75.3. 74.2
71.5, 70.2
ImageNet10
63.3.61.2
62.5,
58.0
47.00 42.6
96.2,
91.4.91.9
96.5
92.1
92.7, 92.4
Ours
95.9. 96.1
91.1. 91,4
91.3, 91.6
96.8, 96.4
92.3, 91.7
93.2, 92.3
97.2, 96.6
93.1. 92.1
94,0, 92.6
MNIST
AE
44.2,
42.6
41.3,
38.3
25.1
60 61.1
57.5,
47.1, 49.1
87.3, 89.4
79.9, 83.0
77.9. 82.0
Ours
95.4. 92.3
89.5, 83.4
90.3, 83.8
96.6, 96.1
91.5, 90.2
92.7, 91.5
97.0, 96.9
92,0.
91.8
93.6. 93.2
REUTERS
AE 55.5,
24.0, 25,8
19.3. 19.4
87.6, 88.7
67.6, 69.1
76.4.78.
93.0, 91.9 93.0.91.9
79.0, 76.2
86.2, 83.6
Ours 91.6, 92.3
73.1, 75.1
80.4, 82.4
96.0. 94.8
84.4, 81.0
90.5, 87.4
97.6, 95.4
89.7, 82.4
94.6. 88.6
STLI0
AE 59.4
55.9
41.1. 40.7
81.8, 83.1
76.0, 76.8
68.7. 71.2
89.6, 89.7
81.6, 81.3
79.0, 79.4
Ours 86.1, 87.4
77.2, 78.2
73.3, 75.6
90.9, 89.9
82.5, 81.2
81.6, 79.8
92.9.90.7
85.3, 82.2
85.2. 81.1
RCV1-10
AE 31.7,
31.6
9.2, 8.6
6.5.
50.9, 51.9
32.3, 33.7
35.6, 38.1
77.5, 78.6
55.5, 57.4
67.2, 70.5
Ours
66.9. 67.8
60.2. 61.8
58.4, 59.8
89.3,
74.6, 74.4
84.0, 83.8
91.5. 91.5
77.9. 77.4
86.4
From Table 2, we observe that SpherePair consistently outperforms AutoEmbedder across nearly all cntaset-constrainn-mmttt combinations. The only exception is a minor 0.2% gap in test NMI when using 5k constraints from ImageNet10. When comparing the hierarchical clustering results of SpherePair Table 2 with the K-means results reported Table 1, we find that SpherePair delivers nearly identical performance, with most deviations under 1 and a maximum difference of less than 4%. This consistency highlights the robustness of SpherePair's embeddings across different clustering algorithms. In contrast, AutoEmbedder exhibits more pronounced performance fluctuations when switching from K-means to hierarchical clustering, with some cases showing gaps as large as 15% (c.g., CIFAR-I0 10 with 1k constraints). These variations suggest that AutoEmbedder struggles to generate well-structured cluster representations, making its downstream partitioning outcomes highly sensitive the choice of clustering method.
These extended results underscore the versatility of SpherePair's learned embeddings, which deliver stable and high-quality clustering results regardless of the clustering analysis algorithm used. This flexibility particularly valuable in practice, as hierarchical clustering can reveal dendrogram structures that provide insights into domain-specific end anchor- based DCC methods cannot readily achieve. Consequently, users can confidently replace the clustering step in framework with more interpretable domain-specific method, assured that SpherePair's representations will continue to deliver strong performance.
somethinn K-means and end-to-
F22 Imbalanced constraints
We present additional experimental results that analyze model behavior and visualize learned rep- resentations in latent embedding spaces under imbalanced constraint conditions. The distribution of imbalanced constraints skews toward specific inter-cluster relationships due to experts' greater familiarity with particular knowledge areas, which is common in real-world scenarios.
39

---

CRANTE
Iest NCO: HNREST
HONGENETT
SLLNCC PRUTERSS
THe STLTE
Tea (827-13
Doncent jat
Deril or
Sustee C90013020
PU1ST
Teried 10677
Tahil 2712
601
680
100
600 M0
Commarn Set
Conraand
Consann
Doratran
Conmant
Figure 10: Test ACC/NM//AII performance (meanistd over 5 runs) of all models across datasets under the imbalanced constraints setting where (IMBO)), IMB1]. [MB2]) = (Ik, 5k, 10k).
F221 Model behavior
To complement Fig. 3 in the main text, we provide additional results in Figs. 10 12. Each figure illustrates how performance changes as the imbalance level increases from IMBO to IMB1 and IMB2, following the generation procedure Appendix E.3, where the nested relation IMBO C. IMB1 C. IMB2 rules out declines due to reduced constraints. The three figures correspond to different constraint set sizes, namely (Ik, 5k, 10k). (5k, 25k, 50k). and (10k, 50k, 100k). Each shows three rows of metries (ACC, NMI, ARI) across eight datasets, offering comprehensive view of model behavior under varying imbalance levels.
Baseline behavior. Most baseline models exhibit increasing performance degradation as the im- balance level rises from IMBO IMB2, although the severity of this decline varies depending on the initial size of IMBO]]
When IMBO] is relatively small, the additional constraints from IMB1 or IMB2 can have a partially positive impact, mitigating some of the adverse effects of the skewed constraint distribution. For example, Fig. 10, most baselines on the STL10 dataset experience only limited degradation the imbalance increases, and on RCV1-10 most baselines even exhibit a noticeable performance gain.
In contrast, when the balanced set size [MBO| is already large enough for near-saturation performance, introducing imbalanced constraints from IMB1 or IMB2 amplifies negative effects. As shown in Fig. 12, most baselines suffer pronounced drops on both STL10 and RCV1-10 compared to the lower-constraint scenarios.
An exception is the SDEC model, which remains stable under varying levels of imbalance. This stability likely stems from its reliance on an unsupervised clustering objective, as shown in Table I presented the main text, where increasing constraints also leads to minimal performance gains. As result, SDEC is less susceptible to both the benefits and drawbacks of heavily imbalanced constraint sets, maintaining relatively steady behavior under IMB conditions.
SpherePair behavior. SpherePair remains robust across datasets and imbalance scenarios, con- sistently ranking among the top-perfore perfoorrnnn methods. The only notable degradations occur on CIFAR-100-20 and FMNIST; however, SpherePair is always noticeably less affected than baselines and consistently outperforms them under nearly all settings. In particular, on FMNIST, increasing [IMBO] enables SpherePair to effectively exploit the richer constraint information to counteract the negative effects of imbalance (see Fig. 12). This resilience can be attributed to its ability to respect and leverage non-dominant local pairwise relationships.
40

---

BIG CRNATTE
ACD- MRGGRNGTI
ACO- PRATTUES
Teat STLLE
Concuutt Sat
02/00 ard
Conaa of
Oar Corchait S48
Co
Teuiton -1AR122000
Tae MIT OIAATO
THE 1601 FMNST
Yurv INNGENETEE
Toe MV1 Wh-57
Toe M -52-0
A01
601
Figure 11: Test ACC/NMI/ARI performance std over 5 runs) of all models across datasets under the imbalanced constraints setting where (IMBO], [MBB]] IMB2) (5k, 25k, 50k).
Ter TEI
ADO IMAGDNETTE
ACO- WABST
ACD- INCUTIOS
Text AOC $11/00
D6
MF
Cackeot
Cencarr
S-an calelo1
3:2 CRANTE
Tel M01 MMLTT
Twcted 20113
Mi
6/%
2311
60
Conmani 5t
Conemart Stt
Conrasin: Se:
Comtra Stt
Condenin: Se:
Conrosin Sat
Conment Srt
Content:: So:
VariaDOC
D022
Asconitecde
Figure 12: Test ACC/NMI/ARI performance (tean over 5 runs) of all models across datasets under the imbalanced constraints setting where (IMBB)), IMB1], IMB2) ) (10k, 50k, 100k).
SpherePair's 's robustness highlights its practical advantage in real-world scenarios, where annotators are more likely to label familiar pairwise relationships while neglecting less familiar ones. This adaptability makes SpherePair particularly suited for imbalanced constraint settings.
F.2.2 Latent embedding visualization
To gain deeper insights into how a DCC model is influenced by imbalanced constraints, we visualize the learned representations in the latent embedding space under the IMB2 configuration shown in Fig. 12 (where [MB2]| = 100k). The visualization focuses on four representative models that explicitly learn latent embeddings: VanillaDCC (an end-to-end classification approach), CIDEC (an end-to-end autoencoder approach), AutoEmbedder (a deep constraint embedding method in Euclidean space), and our SpherePair (a deep constraint embedding method in angular space).
For each model, the embeddings are visualized as follows: the output of the last hidden layer for VanillaDCC, the autoencoder's latent space for CIDEC and AutoEmbedder, and the unit-normalized
41

---

VanillaDCC
AutoEmbedder
(Ours)
CIARR100-20
Ber a.0
Test ADC 0.00
Test ACC 0.26
ADC 0.57
OIFRRD
Test 6.Co.22
Test ADC 0.52
A.C.
The ACCC.90
0.stACC
ACC
MINIST
Test ACC 0.96
Text ACC
REUTERS
ACC 0.88
ACC.043
Twit ACEIO
STLED
ADC 0.85
Text ACC 8.75
ACCOS
nOV1-10
Figure 13: t-SNE visualization of embeddings under imbalanced constraints ( IMB2 |- 100k). Each column corresponds to one model: (a) VanillaDCC, (b) CIDEC, (c) AutoEmbedder, and (d) SpherePair. We visualize the final hidden-layer output (VanillaDCC), latent embedding (CIDEC, AutoEmbedder), and normalized latent embedding (SpherePair). Different marker colors denote different ground-truie truth categories.
42

---

spherical embeddings for SpherePair. Fig. 13 show the t-SNE plots of the resulting representations across different datasets, leading several key observations:
End-to-end methods. Both VanillaDCC and CIDEC exhibit tendency to mismatch local similar- ities and global clustering decisions under imbalanced constraints. This often results in instances from different ground-truth categories being incorrectly embedded into tight, misassigned clusters. These clusters indicate that imbalanced constraints cause the anchors to disproportionately emphasize dominant relationships, neglecting minority local constraints.
AutoEmbedder. As an anchor- free Euclidean embedding method, AutoEmbedder generates non- convex and less discriminative clusters, suggesting that pairwise learning in Euclidean space is particularly sensitive to imbalance. While AutoEmbedder occasionally preserves local groupings for specific categories, its clusters can be challenging to partition accurately. For instance, on the Reuters dataset, K-means applied to AutoEmbeddder' 's features yields an ACC of only 0.41.
SpherePair. In contrast. SpherePair leverages the properties of angular space and its derived neg- ative zone to maintain a balance between respecting local relationships and forming sufficiently separable, convex clusters. Even under severe imbalance, SpherePair produces normalized embed- dings that form compact, clearly discernible clusters, demonstrating its robustness in representation learning.
Overall, these visualizations highlight that under strong constraint imbalance, anchor-based end- to-end methods like VanillaDCC and CIDEC are prone misclustering minority classes, while anchor-free Euclidean-based deep constraint embedding methods like AutoEmbedder struggle to form separable clusters. Our SpherePair, by capitalizing on angular distances, preserves coherent local structures and generates stable, well-defined clusters, even under skewed supervision.
F.3 Unknown cluster number
We comprehensively evaluate our PCA-base based number inference combined with SpherePair in terms of its effectiveness across different constraint levels, its comparison with alternative K -iinference strategies, and the applicability of SpherePair relative to DCC basclines for K --inference.
F3311 PCA-based K K-inference under different constraint levels.
We extend the evaluation of our K-inference from Fig. 5 to additional constraint levels (1k/5k/10k), as shown in Fig. 14. Across most datasets, 10k constraints yield clear plateau entries, while 5k constraints produce slightly less pronounced entries that remain sufficient for correct K estimation. An exception is RCVI-10, where strong class imbalance poses inherent challenges and leads to inaccurate estimates across constraint settings. In the more limited Ik-constraint setting, the plateaus become much less sharp, particularly on CIFAR-100-22 MNIST, and FMNIST, resulting more frequent inaccuracies. Nevertheless, under the Ik-constrait setting, our method still produces correct K estimates on CIFAR-10 ImageNet-10 10, Reuters, and STL-10 in nearly all cases, with only two minor deviations CIFAR-10 where the estimate differed from the ground truth by 1.
F.3.2 Comparison with alternative post-clustering K K-inference.
Under the same experimental setup in Fig. 14, consider post-clustering validation strategies as alternatives to our geometric approach. Fig. 15 and Fig. 16 show the curves of the silhouette coefficient (SC) with K-means and the K K-cluster lifetime with Aggiomerative Clustering, obtained by sweeping candidate K values on SpherePair embeddings learned with 1k/5k/10k constraints. In both cases, the estimated K is given by the curve maximum. Comparing Figs. 15 and 16 with Fig. 14, we find: (i) SC with K-means is slightly less accurate than our method under 10k and 5k constraints, yielding minor misestimations on CIFAR-10 10, FMNIST, and STL-10, together with markedly larger discrepancy from the ground-truth K on while outperforms our approach on FMNIST and MNIST, 100-20. With only 1k constraints, unstable on other datasets with around half of the estimates incorrect, and exhibits a deviation of up to 15 on CIFAR-100-22 K K-cluster lifetime with Agglomerative Clustering shows stronger sensitivity to the constraint level, yielding almost correct K estimates under 1k constraints except ImageNet- and STL-10.
(ii)
43

---

CIFA/T1CD-00
CIP4910
BIAGENETIO
04-
0.5
041
3.41
08-
0.5
0.00
0.2
02-
03-
304
0.50
0.2
16
(a)
8.50
03+
0.1
16
REUTERS
RDV1-10
0.1-
64.
0.7
51
CIRAR100 20
CIFA11
RINSTT
IKAGENETIO
0.-
03-
MNIS
REUTERS
STU16
ROV1 10
0.4
34.
8.4m
044
344
47
03-
35
04-
(c)
Figure 14: Tail-averaged minimal inter-cluster angle 8a vs. PCA subspace dimension d, obtained from SpherePair embeddings learned with (a) 1k, (b) 5k, and (c) 10k constraints across five runs. The red lines indicate the ground-truth intrinsic dimensions d" K-1.
44

---

DIAR100--22 23
CIFR10
FNN4ST
INAGENETO
120
0.4
0.3
MNIST
REUTERS
STL10
RCV1-19
1.20
04
0.4
63
34-
33
622
01
(a)
CIRAR100 20
CIRAR10
PRINST
IMAGENETTO
0.4
MMST
REUTERS
STL10
RCV1-10
0.5
0.5
63-
(b)
CIAR100
CIRA10
FMNIST
IMAGENET10
0.3
06
0.5
MAIST
REV1-10
06
(c)
Figure 15: Silhouette coefficient (SC) with K-means for K-inference across five runs, obtained by sweeping candidate K values on SpherePair embeddings learned with (a) 1k, (b) 5k, and (c) 10k constraints. The estimated corresponds to the maximum SC value (bold solid markers) in each curve. The red lines indicate the ground-truth K.
45

---

CIPAR1000-0 20
CIARRO
FNNSST
INAGENET1O
6.5
6.2
0.35
6:10
6.55
648
REUTERS
STL1D
RCVI-19
0.35
6.35
22-
38
6.0
8.c
(a)
CIPAR100-20
CHARLO
IMAGENITIO
3.6
0:40
3.4
6.0
530
8.2
MNIST
REUTERS
STL.1
RCV1-19
32-
C.16
(b)
CHARLD
PUAGENETLD
3.5
3.4
03
52-
REUTERS
STL1D
REVI-19
23
6.3
31
02
K
K
(c)
Figure 16: K-cluster lifetime with Agglomerative Clustering for K-inference across five runs, obtained from SpherePair embeddings learned with (a) 1k, (b) 5k, and (c) 10k constraints. The estimated K corresponds to the maximum lifetime value (bold solid markers) in each curve. The red lines indicate the ground-truth K.
46

---

OPAR1000200
GFAR10
THNEST
MAGENETLO
0.0
3--
9.7
0.2
0.2
MNIST
REUTERS
STL10
RCVL-19
0.300
0.28
3.39
0.2
3317
349
(a)
DPAA1000200
CFAR10
FNNEST
INGRENELOO
3.45
3.75
0.5
3.35
032
62
MNIST
STL10
RCVL-10
6.5
65
03
3.20
02
6.2
(b)
0.42
0.09
6.4
11
1.c
35
15
12
35
(c)
Figure 17: Silhouette coefficient (SC) with K-means for K-inference across five runs, obtained by sweeping candidate K values on AutoEmbedder embeddings learned with (a) Ik, (b) 5k, and (c) 10k constraints. The estimated K corresponds the maximum SC value (bold solid markers) in each curve. The red lines indicate the ground-truth K.
47

---

CPAR100-22
CINAR1O
PRN.ST
IAGGEETT 130
0.-
Horratun
MMST
REUTERS
STL10
RCV1-10
06
06
(a)
CIRARL0O 20
CIRAR10
PRINST
IMAGENETTO
MMST
REUTERS
STL10
RCV1-10
3.25
3.29
3.90
8.6
(b)
CIRAR109-28 20
CIRAR1
FNNIST
IMAGENETLO
0.35
0.28
0.2
6.8
REUTERS
STL1D
REVI-10
0.2
1.6
(c)
Figure 18: K-cluster lifetime with Agglomerative Clustering for K-inference across five runs, obtained from AutoEmbedder embeddings learned with (a) 1k, (b) 5k, and (c) 10k constraints. The estimated K corresponds the maximum lifetime value (bold solid markers) in each curve. The red lines indicate the ground-truth K.
48

---

Moreover, its estimates CIFAR- 100-20 are consistently unreliable with deviations up to 18 across all constraint levels, reflecting its failure in complex scenarios.
Overall, these results highlight the superior accuracy and robustness of our PCA-based K-inference on SpherePair embeddings. Appendix G further compares computational overhead, where post- clustering methods incur additional cost from repeated clustering (multiple K-means runs or one Agglomerative clustering), while our PCA-based inference is considerably more efficient as requires only a single closed-form PCA solution.
F.3.3 Comparison with DCC baselines.
We separately compare SpherePair with end-to-end DCC and Euclidean constraint embedding methods highlight its advantage in scenarios with unknown K.
Comparison with end-to-end DCC. Unlike our deep constraint embedding approach, which allows direct geometric inference or post-clustering inference via rapid sweeping over K on pre- learned representations, all end-to-end anchor-based DCC baselines require training new model from scratch for each candidate K. This makes them impractical for such estimation due to the time-intent inne-intensive nature of retraining (see learning efficiency in Table 4 for training times corresponding to specific K).
Comparison with Euclidean constraint embedding. Under the same setup as in Figs. 15 and 16, we further apply the two post-clustering K K-inffrence strategies to representations learned by the Fuclidean constraint embedding baseline, AutoEmbedder, and report the results in Figs. 17 and 18. Comparing these with Figs. 15 and 16 highlights the applicability of different learned representations to K-inference. Over 40 cases per setting datasets runs), AutoEmbedder's is representations consistently struggle at all constraint levels, failing under both "K-means SC" (39/40, 28/40, 25/40 failures for 1k, 5k, 10k constraints, respectively) and "Agglomerative + K-cluster lifetime" (40/40, 32/40, 30/40 failures). This indicates that AutoEmbedder produces suboptimal embeddings that are not sufficiently structured to support reliable cluster-number inference, underscoring the superiority of our SpherePair-bused approaches.
In summary, SpherePair proves highly applicable to real-world scenarios with unknown cluster numbers. By separating representation learning from clustering, it avoids the heavy retraining cost required by end-to-end DCC methods. By producing geometrically well-structured representations that remain fusttriing-rriendly.. SpherePair enables both reliable PCA-based K-inference and effective post-clustering validation.
F,4 Empirical validation and hyperparameter sensitivity analysis
We supplement Sect. 5.2.4 with additional results, providing empirical validation of our theoretical insights and evaluating the robustness of our approach.
F.41 Embedding dimension
To provide a more comprehensive analysis of the impact of and support our theoretical findings, extend our evaluation across varying constraint set sizes (1k, 5k, 10k) and multiple clustering metrics (ACC, NMI, ARI). Fig. 19 display the clustering performance with respect to D for eight datasets under these different settings.
The results consistently demonstrate that ensuring a sufficiently large embedding dimension D achieves near-optimal fully optimal performance across datasets, metries, and constraint levels. Notably, the range of D values yielding optimal performance corresponds to the boundary established by our theoretical analysis in Sect. 4 (D K, where K is the cluster number), and this correspon- dence becomes increasingly tight as the constraint set size grows. This alignment underscores the reliability of our theoretical framework for conflict-free constraint embedding in angular space, and provides clear practical guidance for hyperparameter selection.
Furthermore, we observe that settings slightly below the theoretical threshold (i.e., D < K K-1) 1) do not noticeably affect SpherePair's performance, offering useful flexibility when the number of clusters is unknown. This is further supported by Table 3: despite the basclines having theoretical
49

---

DIFAR100-20
CIFAR10
FANISS
IMAGFNET10
44
MNST
REUTERS
STL100
RCV1-10
046
0
(a)
0B-AH100-20
CIRARIO
FANNIST
IMAGENETIO
2000
5.0
MNIS
REUTERS
STL10
RCV1-10
8
24
24
(b)
DIFAR100-20
418
MNIST
REUTERS
RCV1-10
24
20
24
2-
26
24
Figure 19: Impact of embedding dimension D on SpherePair performance (meantistd over 5 runs) across datasets under 1k/5k/10k constraints: (a) test ACC, (b) test NMI, and (c) test ARI. The red lines indicate the theoretical boundary between insufficient and sufficient D.
50

---

Table 3: Clustering performance (%) (ACC, NMI, ARI) on CIFAR-100 100-20 for models with vary. ing embedding dimensions and 1k/5k/10k constraints. Blue and black represent training and test performance, respectively. The best results are bold, and the second-best are underlined.
1k
Sk
10k
ACC
NMI
ART
ACC
NMT
ART
ACC
NMI
ART
VanillaDC'
34.2.
36.0,
19.3, 19.3
47.4.
46.7,
32.2
54.6. 54.5
50.3
37,9, 37.6
Mr
20.1, 20.3
21.4. 21.6
7.1, 7.2
42.8, 42.8
41.9, 42.1
22.8. 22.8
51.2, 51.0
48.5, 48.7
33.4, 33.3
CIDEC (I0D)
45.2
47.7.
29.7,
48.
48.3, 48.7
32.2, 31,4
49.7, 48.8
49.0. 49.1
CIDEC (20D)
46.6.46.2
47.3. 47.9
30.0, 29.9
46.7.46
45,7
30.3, 29.6
50,9, 50.1
48.5.48.8
34,0, 33,0
CIDEC (30I)
44.2.44.5
46.4, 46.9
30.0, 29.8
48.0, 47.4
46.9, 47.2
32.2. 31.6
49.2, 48.7
48.3.
33,9. 33.6
DCGMM (10D)
43.6
28.2, 45.6
46.6, 46.5
46.0,46.4
31.0, 30.8
49.0, 48.7
47.8,48.1
33.7
DOGMM (20D)
44.3.
28.7, 28.7 45,4
48.1,
46.7, 47.1
32.2. 32.2
52.3, 52.1
49.2. 49.6
36.7, 36.7
DCGMM (3II)
45.0,
46.4,
29.0,
46.2, 46.8
46.9. 46.7
31,8,
SDEC (10D)
45.2, 44.9
47.2
28.0, 28.2
45.5, 45.6
47.9, 48.5
29.1, 29.3
45.9, 45.6
48.2, 48.8
30.0, 30.1
SDEC (20D)
45.7.454
47.0,
29.0, 29.2
45.6,
47.00 47.5
29.2, 29.3
45.7, 45.2
47.1,47.7
29.3, 29.5
SDEC (30D)
45.0.44.3
45,9, 46.3
28.5
44.7
46.3
29.0. 29.2
45.3, 44.7
46.7.47.2
29.2
AutoEmbeuderr (10D)
29.4.
31.8, 32.0
12.4, 12.3
24.0, 29.0,
35.0, 35.3
18.1. 18.1
39.8, 39.7
42.1.42.4
27.2, 27.1
AutoEmbedder (20D)
21.5.21.6
23.1
7.17.1
13.8,
13.5.
4.7.4.7
31.331.. 31.3
36.6, 36,9
20.4
Autobmbedder (30D)
33.9.
15.5
17.6, 17.8
26.4, 26.2
31,9,
15.2. 15.1
33.8, 33.8
40.3. 40.3
25.3, 25.1
SpherePair (Ours) (10D)
46.9,
46.0.
31.0, 30,9
54.6,
49.6, 49.8
37.9,3755
57.9,
51.6
41.1
SpherePair (Ours) (20D)
48.3
48.2
47.7
48.0
32.2
32.4
59.0
58.8
52.6. 53.0
40.0.0.99
62.8.
62.6
58.1 55.5
45.3 45.2
SpherePair (Ours) (30D)
48.4, , 48.2
46.8
47.2
314
31.5
58.4 58.4
53.3 53.8
41.7.419
64.4. 64.3
56.6 56.9
46.8
46.5
restriction on D. SpherePair still outperforms them on CIFAR-100-20 even at D 10 (below the theoretical threshold K = 20), underscoring the practical flexibility of using slightly sub-threshold Although sufficiently large
generally beneficial, we note a minor exception on MNIST under 1,000 constraints: while D = 10 yields peak results, increasing D beyond 10 leads to more pronounced drop in clustering quality. This may reflect the broader impact of large embedding dimensions and the resulting overparameterization
deep neural networks, an effect that carries both negative [58, 59, 60] and positive [61, 62] implications and has been a long-standing subject in deep learning research; with larger constraint sets, however, this adverse effect diminishes, allowing digees-ai embeddings to continue enhancing performance.
In summary, these results confirm that respecting the theoretically derived boundary for the embedding dimension D leads consistently strong clustering performance. In practice, choosing a sufficiently large D 2 K offers simple yet effective rule, enabling scalable and efficient solutions. This is particularly advantageous scenarios where the exact number of clusters K unknown, as the theoretical insights offer robust guidance for parameter selection in diverse real-world applications.
F.4. Regularization strength
The regularization strength À governs the trade-off between the reconstruction loss and the angular constraint loss in SpherePair's objective function. We evaluate SpherePair /SpherePair across a wide range of À values under varying constraint levels (1k, 5k, and 10k), reporting test ACC, NMI, and ARI. The detailed results are shown in Figs. 20 and for both scenarios, without and with pretraining, respectively.
The results demonstrate that SpherePair is generally robust to changes X, with only modest perfor- mance variations, except on RCV1-10 where pretraining combined with overly large unsupervised regularization amplifies the negative effect of severe class imbalance. Apart from this exception, observe that the sensitivity to À becomes more pronounced when the number of constraints is small, particularly in scenarios with random initialization (i.c., SpherePair' without pretraining), and this effect is most noticeable on CIFAR-100-200 MNIST, and Reuters. In these cases, selecting an inappropriate À may lead to suboptimal clustering results due to the insufficient supervision provided by the small constraint sets.
Despite this sensitivity, the results suggest using 0.02 as a default setting when validation information is unavailable, as it consistently provides strong performance across most datasets and constraint sizes. If prior information on class balance available, À can adapted accordingly, with larger values recommended for balanced datasets and smaller values for imbalanced datasets.
51

---

ROVIIS 1cComsar
NCV--1 Condriss
ROVITD TCConcoRe
N0V110
ORARTI
$0.00
Figure 20: Performance (mean - std over 5 runs) of SpherePair (without pretraining) across varying À values (from 0 to 1.0).
Tret ROWHI- TeComsen
Tes WOW-DD- Com
12V--1 IN Centro
BOWL-D Combaro
PCV1-12
Figure 21: Performance (mean over 5 runs) of SpherePair (with pretraining) across varying À values (from 0 to 1.0).
F.4.3 Tail ratio
The tail ratio controls the fraction of negative pairs used to compute the tail-averaged minimal inter-cluster angle in cluster-number inference. We evaluate p values in the range [0.01, under different constraint levels (1k, 5k, and 10k), and plot the resulting sequences (52) in Fig. 22.
Overall, our method is robust across broad range of p values, although different choices of p exhibit characteristic behaviors. Specifically, smaller P produces sharper rises before Jx but results in values slightly below the plateau levels, whereas larger yields more consistent values when 2 K but makes the plateau entry less steep. Apart from the difficulty of inferring the true cluster number 1-0 due to severe class imbalance, within [0.03, 0. provides good trade-off for highlighting the plateau entry across most datasets. We therefore recommend setting & in this range for practical use.
52

---

CIFARTICD-20
CRPAR100
PANEST
BIAGENETIO
04+
0.
344
03-
01.
81
E1x
MN3T
REUTERS
STL.0
ROV1 10
0.-
6.60
6.50
03.
03-
05-
6.3
02-
(a)
CIPAR1d0--0
CIAARO
TIRAST
BIAGENETIO
0.-
031
17
33x
080
8.0
051
051
8.5g
6.5
02
30
16
(b)
CIPAR100
CIRAR10
BAAGENET10
03.-
044
02-
32x
0.11
10
17
25
38
15
5
15
16
10
15
MNBT
REUTERS
STL16
ROVI 10
0.5
0.60
0.-
3.0
2.00
0.1
211
E12
(c)
Figure 22: Impact of the tail ratio p (from 0.01 to 0.2) on the tail-averaged minimal inter-cluster angle Jg across PCA subspace dimensions tsd over five runs), obtained from SpherePair embeddings learned with (a) 1k, (b) 5k, and (c) 10k constraints on datasets. The red vertical dashed lines indicate the ground-trutt intrinsic dimension d' = K K-1.
53

---

G
Learning efficiency
We evaluate the learning efficiency of SpherePair and DCC baselines in terms of overall training time, clustering and cluster-number inference overhead, and provide an analysis of computational complexity.
Table 4: Overall training time for different DCC methods on various datasets using 10k constraints. All times are measured on a single Tesla V100 16G GPU. Models marked with require hyperparam- eter tuning, and their corresponding times are underlined.
CIFAR100-20
CIFARIO
FMNIST
ImageNet10
MNIST
REUTERS
STLIO
RCVI-10
VanillaDCC
6m23s
6m38s
7m7s
5m23s
7m33s
2m6s
5m47s
Im48s
VolMaxDCC'
32m32s
77m45s
73m57s
61m31s
20m6s
17m31s
22m7s
41m58s
CIDEC
29ml
26m
41m20s
5m56s
36m9s
6m388
6m2s
71m44s
DCGMM
21m9s
19m21s
27m55s
4m446s
21m12s
5m45s
4m47s
42m25s
SDEC
25m1s
24m33s
33m58s
Sm444
32m53s
6m27s
5m10s
61m12s
AutoEmmeedder
81m32s
75m
89m Is
30mi Is
95m3s
36m13s
34m29s
82m39s
SpherePair (Ours)
25m331
25m21s
33m11s
6m36s
34m22s
7m99
6m21s
64m55
Table Clustering analysis time for anchor-free deep constraint embedding models using K-means ()) and hierarchical clustering (t).
CIF2R100-20
CIFARIO
FMNIST
ImageNet10
MNIST
REUTERS
STLIO
RCVI-10
AutoEibeuuker
18s 45s
4s 50s
66
Im25s
1s 1s
5s Im27s
Is 1s
18.
955.
SpherePair (Ours) 10s 47s*
52s
46
Im244
1s
Im233
1s',2 2x
1s',
56',36'
Table 6: Comparison of time costs for three K-inference methods across datasets, based on SpherePair embeddings learned with 10k constraints.
CIFAR 100-20
CIFARIO
FMNIST
ImageNer10
MNIST
RELTERS
ST1.10
RCVI-10
K-means SC Agglomerative + lifetime PCA-haaed (Ours)
3m14s
30s
39,
18s
34s
20s
18s
1m7s
47s
Im24s
1m23s
2s
2s
35s
3s
1s
1s
1s
2s
Overall training time. Based on our resources and the implementation outlined in Appendix E.4, report the training durations of various DCC methods using 10,000 constraints across multiple datasets. Table 4 summarizes the average overall training time for each model, including both the hyperparameter tuning and parameter estimation phases: (i) The hyperparameter tuning phase encompasses searching for optimal hyperparameter values and, if necessary, single pretraining the training split (excluding validation samples) prior the search; (ii) The parameter estimation phase involves training the model with the identified optimal hyperparameters, including any pretraining the full training split if applicable. It noteworthy that only VCIMaxDCC and AutoEmbedder require hy hyperparameter tuning, while pretraining is performed for all methods except VanillaDCC and VoIMaxDCC.
Clustering overhead. Additionally, we report the clustering analysis time for two deep constraint embedding models, AutoEmbedder and SpherePair, using K-means and Agglomerative clustering, Unlike other end-to-end baselines that embed clustering into the network training, these models produce dustering-friendly representations, and the time required for subsequent clustering is minimal as shown in Table
Cluster- number inference overhead. When the number of clusters K is unknown, clustering validation metrics are typically employed to infer the true K. In this setting, deep constraint embedding models (e.g., AutoEmbedder and SpherePair) incur only modest overhead, candidate K values can be swept over pre-learned representations via K-means or with a single agglomeration run. Moreover, our SpherePair further benefits from the proposed PCA-based K K-inference, achieving even higher efficiency by bypassing post-clustering entirely through a direct PCA solution (see Table for the time costs of different K-inference methods). In contrast, end-to-end DCC baselines must be retrained from seratch for each candidate K (see Table 4 for single-run training costs), leading to far higher computational expense.
54

---

Computational complexity analysis. Aside from the empirical results, we analyze the compu- tational complexity of SpherePair's learning, which theoretically govemed by standard DNN operations, as well as our PCA-based K K-inference, which relies on closed-form PCA solution. Let T and Tap denote the forward-pan -waard-pass costs of encoder f and decoder Dø', respectively, |C] the number constraints, and | the number of instances. Then the cost of angular pairwise learning (scanning constrained instance pairs) is (((CTTTa) and that of angular reconstruction (scanning instances) is (T + (oy)). The additional cost of PCA-based K-inference comes from running PCA once on the D-dimensional embeddings of instances involved in negative constraints C i.e., O(CC D2). Notably, by avoiding the need to optimize K anchors and clustering assign- ments- whith would incur an additional D) cost SphereePari enjoys lower overhead than end-to-end DCC, while its angular reconstruction cost on par with the standard reconstruction employed in methods such as CIDEC (12), and its K-inference overhead is negligible compared to repeated clustering- validation.
H Effect of network structure
YEME DeNRo
TWE MEST
87
877
871
Compect
Sanderd
Dokp
Figure 23: Performance comparison of SpherePair across three pncoder-decodee structures: Compact, Standard, and Deep. Results (mea over 5 runs) are based on 10k balanced constraints, and metrics include test ACC, NMI, and ARI across multiple datasets.
To evaluate the impact of network structure SpherePair's performance, test three different encoder structures (paired with symmetric decoders): Compact 255-225-51 Standard (500-500- 2000), and Deep 1800-500-500 5000-0000.. Using 10k balanced constraints, measure test ACC, NMI, and ARI on all datasets, with results summarized in Fig. 23.
The results indicate that SpherePair's performance is largely robust to the choice of network structure, with only minor differences observed across datasets. For instance, the Compuct network performs slightly better CIFAR-100-20. CIFAR- 10, and MNIST, while the Standard network achieves the best results on FashionMNIST. ImageNet- 10, STL-10, and RCV1-10. The Deep network performs marginally better on Reuters. These variations suggest that while specific structures may provide slight advantages for certain datasets, SpherePair maintains high clustering quality across all structures.
Given the observed consistency, we recommend the Standard structure (500-500-2000 550020000 as a practical default choice due its balanced performance and moderate complexity. However, for real-world applications, selecting the optimal structure based on the target dataset and computational resources can further enhance performance.
55


Reviews:
[{"review_id": "kQaLLsdg6c", "reviewer": "Reviewer_XPPE", "summary": "The work proposes a deep constrained clustering approach that incorporates  an angular loss called SpherePair loss to improve the cluster separation, leading to improved performance in clustering tasks. The method is inspired from deep angular learning from supervised classification literature and is combined with clustering at the embedding space. Real data experiments are presented to showcase the effectiveness of the approach.", "questions": "Questions.\n\n1.\tThe proposed SpherePair loss has close similarity with the binary cross entropy loss used in many end-to-end DCC works. There is no discussion related to that and the advantages of this loss over them.\n\n2.\tHow is angle is calculated in the loss function in (1)? Is cosine similarity using the inner product of the embedding vectors?\n\n3.\tIt is unclear how does the method is robust to imbalanced datasets? What is the appropriate $\\omega$ in this case? \n\n4.\tIt may not be completely correct to claim that the method does not need the number of clusters to be known. To complete the clustering task, finally you may have to rely on a clustering algorithm to the learned spherical representations. \n\n5.\tThe clusters are equidistant in angular space which may be improved by considering class specific distance based on cluster similarities.\n\n6.\tFigure 6 does not strongly show the strength of the SpherePair regularization as the performance in lambda=0 is more or less the same as nonzero lambda in many settings\n\n7.\tIt is mentioned that one of the limitations of the approach is that it does not support incomplete annotations. So, what is C (the number of pairwise constraints) in your settings? Does your analysis also consider fully observed constraints?\n\n8.\tThe notation C is not explicitly defined.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1.\tThe paper is overall well-written and organized, and therefore easy to follow.\n\n2.\tThe literature study and comparing and contrasting different lines of clustering approaches are also presented well.\n\n3.\tTheoretical analysis is also a plus with deriving some key hyperparameter values based on it. \n\nWeaknesses:\n\n1.\tPerformance improvement is not significant in most of the clustering tasks.\n\n2.\tThe advantage of embedding-based clustering over end-to-end DCC is not substantiated well.", "was_revised": true, "final_justification": "The authors have addressed my concerns over not discussing and comparing with the existing closely matching baselines and some of the practical considerations in choosing the parameters. The proposed approach shows promise, but not significantly novel or pushing the current SOTA by significant margin in terms of empirical performance. Hence, I decide to keep the score.", "rebuttal": "We highly appreciate your time and effort in reviewing our work, as well as your positive comments regarding our approach. Below, we address the raised concerns.\n\n\n**Weaknesses**\n\n1. >*\"Performance improvement is not significant in most of the clustering tasks.\"*\n\n    **[Response]**  We respectfully request placing more emphasis on our performance improvements with **limited constraints** and heavy **imbalance**, which together clearly demonstrate the superiority of our method. Specifically:   \n    - With pretraining, SpherePair ranks first in 6 out of 7 datasets in ACC at 1k constraints (second only on CIFAR-10), and achieves 3%–6% improvements in ACC over the second-best method on FMNIST, MNIST, and REUTERS (Table 1 and Table 3). Without pretraining, SpherePair$^\\dagger$ consistently outperforms the strong baseline CIDEC$^\\dagger$ in ACC at 1k constraints with 12%–20% improvements, except on MNIST where it still achieves 5% gains (see Table 1, lines 264-272).\n    - The superiority of our method under constraint imbalance is supported by the IMB1/IMB2 results in Figs. 3, 4, and 10–13.   \n\n    **Our request is motivated by**:  \n    - With a large number of constraints (e.g., 10k), the problem approaches a supervised setting, leading to performance saturation and smaller gaps between methods.\n    - Limited constraints and constraint imbalance present more realistic and challenging scenarios in practice.\n    \n    Furthermore, these gains persist when switching the clustering algorithm from K‑means to hierarchical (Ward), confirming that improvements come from the learned representation, not a particular clustering algorithm (see Table 2 in Appendix E.1).\n\n\n2. >*\"The advantage of embedding-based clustering over end-to-end DCC is not substantiated well.\"*  \n\n    **[Response]** The advantage of our deep constraint embedding approach over end-to-end DCC methods has indeed been **discussed** and **empirically validated** in both effectiveness and efficiency thoroughly in the manuscript:  \n    - (a) Lines 32–35 and 79–86 clearly state the limitations of end-to-end DCC, motivating the need for embedding-based approaches.  \n    - (b) Visualizations of the latent spaces under severe constraint imbalance (Figs. 4 and 13) show that SpherePair preserves locally coherent relationships far better than state‑of‑the‑art end‑to‑end methods.  \n    - (c) Two practical advantages are evidenced: \n        - **$K$‑insensitive training.** SpherePair does not require the exact $K$ during our representation learning; $K$ is only needed after training for a cheap clustering sweep/selection, avoiding the repeated re‑training that end‑to‑end methods need. See Deployment, lines 159–164, Fig. 1(d), Alg. 1, and Appendix G. \n        - **Robustness under imbalance and initialization.** End‑to‑end anchors mis‑propagate errors under skewed constraints; SpherePair remains stable and top‑performing under IMB1/IMB2, with clear, compact clusters in t‑SNE (Figs. 3 and 4; lines 273–296). Without pretraining, SpherePair$^{\\dagger}$ still outperforms strong end‑to‑end (CIDEC$^{\\dagger}$) by 12–20% on nearly all datasets (lines 264–272). \n    - (d) (Lines 162-164 and 1113-1117) When $K$ is unknown in practice, end‑to‑end models must be retrained for every candidate $K$, while SpherePair with the theoretical guidance learns once and sweeps $K$ with inexpensive clustering.\n\n\n**Questions**\n\n1. >*\"The proposed SpherePair loss has close similarity with the binary cross entropy loss used in many end-to-end DCC works. There is no discussion related to that and the advantages of this loss over them.\"*  \n\n    **[Response]**    \n    - (a) The proposed SpherePair loss is **superficially similar but fundamentally different** from the BCE-based losses in existing end-to-end DCC works: our loss is angular, anchor‑free, and introduces a theoretically valid negative zone via ⁡ $\\cos(\\min(\\omega\\theta,\\pi))$. This yields conflict‑free separation and, when feasible, equidistant clusters with explicit $(\\omega,D)$ conditions (Propsitions 4.1 and 4.2; Theorem. 4.3, lines 166–192). BCE/KL losses used in anchor‑based end‑to‑end methods lack these pairwise conflict guarantees and require known $K$ and anchor optimization.  \n    - (b) As addressed above (response to **Weakness 2**), we have also explicitly discussed and compared our SpherePair loss to state-of-the-art BCE-based end-to-end DCC methods (e.g., VanillaDCC, CIDEC).\n\n\n2. >*\"How is angle is calculated in the loss function in (1)? Is cosine similarity using the inner product of the embedding vectors?\"*  \n\n    **[Response]** The angle between a pair of vectors is computed based on their inner product. Yes, specifically, the cosine similarity between embedding vectors can be calculated as the inner product of their $L_2$-normalized representations.  \n\n\n3. >*\"It is unclear how does the method is robust to imbalanced datasets? What is the appropriate $\\omega$ in this case?\"*  \n\n    **[Response]**   \n    - (a) We kindly remind that we have included empirical results on **the imbalanced dataset, Reuters** (lines 635-638 and 678-685: in the training portion, the number of instances in the four categories CCAT/ECAT/GCAT/MCAT is 4066, 2888, 2202, and 844, respectively.), in our main results (Table 1), sensitivity analysis of $\\omega$ and $D$ (Fig. 5, Figs. 14–16), and visualizations of spherical embeddings (Fig. 7). We also mention that \"the formation of equidistant spherical clusters is not contingent on ground truth clusters being of equal size\" (lines 652–654).  \n    - (b) Imbalance is exactly why we enforce a negative zone of size $\\pi/\\omega$. Empirically, $\\omega$=2 is a safe, near‑optimal default across datasets/constraint sizes; heatmaps in Figs. 5, 14–16 support this recommendation (Sect. 5.2.3, Appendix E.3.1).  \n    - (c) Additionally, Sect. 5.2.2 and Appendix E.2 also provides detailed discussions on imbalanced constraints, which may further address your concern.  \n\n\n4. >*\"It may not be completely correct to claim that the method does not need the number of clusters to be known. To complete the clustering task, finally you may have to rely on a clustering algorithm to the learned spherical representations.\"* \n\n    **[Response]** We kindly remind that we intentionally avoid overclaiming that \"the method does not need the number of clusters to be known.\" Rather, we precisely state that SpherePair \"requires no exact cluster number for **constraint embedding**\" (line 10, line 56). Our primary contribution lies in eliminating the impractical sweeping over $K$ during training, a practical advantage over end‑to‑end methods, enabling efficient and practical inference of $K$ afterward (lines 1113–1117).  \n\n\n5. >*\"The clusters are equidistant in angular space which may be improved by considering class specific distance based on cluster similarities.\"*  \n\n    **[Response]** We sincerely appreciate your insightful suggestion. Although this is beyond the scope of the current paper, which **focuses explicitly on learning non-conflicting embedding from constraints**, we will explore it in future work.  \n\n\n6. >*\"Figure 6 does not strongly show the strength of the SpherePair regularization as the performance in lambda=0 is more or less the same as nonzero lambda in many settings.\"*\n    \n    **[Response]** Yes, it indicates **robustness**. The angular objective already shapes the geometry; reconstruction mainly regularizes low‑signal regimes. The primary purpose of applying regularization is to **prevent degenerate solutions under specific circumstances** (lines 139–141), such as a limited number of constraints and lack of pre-training, as clearly demonstrated for MNIST and Reuters in Figs. 6, 17-18.  It is worth noting that without regularization, training becomes significantly more efficient than end-to-end DCC.  \n\n\n7. >*\"It is mentioned that one of the limitations of the approach is that it does not support incomplete annotations. So, what is C (the number of pairwise constraints) in your settings? Does your analysis also consider fully observed constraints?\"*\n\n    **[Response]** The main results (Table 1) cover multiple constraint sizes $C$ ranging **from 1k to 10k constraints**, constituting at most around 0.01% of all possible pairwise constraints. The \"incomplete annotations\" mentioned in line 364 are not about the size $C$, but rather refer to scenarios where no constraints exist between certain clusters. Although we have not fully addressed this extreme imbalance issue, SpherePair already demonstrates a significant performance advantage over baseline methods in handling heavy imbalanced constraints (Sect. 5.2.2).  \n\n\n8. >\"The notation C is not explicitly defined.\"\n    \n    **[Response]** Thank you for pointing this out. $C$ should have been $|\\mathcal C|$, representing the number of constraints in a training set. We will correct it.  \n\n\nWe hope our clarifications resolve your concerns and highlight our contributions more clearly. If you have further questions, we’d be happy to discuss. We respectfully request you to reconsider your evaluation in light of these detailed responses."}, {"review_id": "zyiP8z8WrE", "reviewer": "Reviewer_jbh1", "summary": "The paper deals with constrained clustering, a \"weakly\" supervised clustering paradigm that uses pairwise supervision to guide the clustering of data. The authors propose a new deep constraint embedding approach they term SpherePair. The authors state that its distinguishing feature compared to prior work on deep constraint embedding methods is that it operates on cosine similarity instead of Euclidean distances. The authors conduct experiments on 6 simple datasets where the proposed method appears to outperform baselines in most settings.", "questions": "- One of the main contributions appears to be that the proposed method operates on cosine similarity rather than Euclidean distance. However, when one applies Euclidean distance to l2 normalized vectors, the Euclidean distance and cosine distance are the same up to a factor: euclidean_distance(u,v) = sqrt(2-2*cos(u, v)) . Thus clustering of normalized vectors using euclidean distance generally results in the same partitioning as clustering with cosine distance. This makes the contribution of the current paper seem trivial. Thus, \n  - (1) as a simple baseline, I would like to see  how related deep constraint embedding methods that use Euclidean distance perform when the embeddings are simply l2 normalized, after the encoding step. \n  - (2) I would like the authors to argue why their method is still needed if one can just normalize the embeddings to achieve clustering via cosine similarity/distance. \n- Why are all the chosen datasets small? Can the method scale to a million or more samples?\n- What was the computational setup? How much gpu memory is required to run these experiments, how long did the experiments take? \n- What is the complexity of the method? How does it scale with the number of dimensions, number of samples, number of constraints?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n- The paper is well structured and easy to follow\n- Experiments are conducted on a decent number of datasets and with good baseline comparisons.\n- Experimental setup and details are well explained\n\t\n## Neutral\n- The authors provide a theoretical results which can inform the choice of the angular scaling parameter ω and the embedding dimension D. I'm not convinced that this part requires an entire page of the paper since it's not like it removes a significant amount of the hyper parameters that have to be set/tuned like λ, the margin parameter pi, and other hyper parameters of the encoder and decoder networks. \n\n ## Weaknesses\n- The contributions of the work are either very limited, or not well laid out/explained by the authors. As I understand, the methodological contribution compared to other deep constrained clustering approaches is simply to adapt a deep constraint embedding method so that it uses a logistic loss with a cosine similarity and a margin parameter.  This loss function is, in my eyes, only a small contribution to the field as similar loss functions have been seen countless times in related contrastive representation learning literature. \n- All datasets are quite small in the number of samples. If this is a limitation of the proposed method or the paradigm, it should be discussed. \n- I would like to see standard deviations for Table 1. I know recreating such a large table is a massive amount of work, so having them for some of the results in the appendix would be sufficient. Right now, I have no way to tell how significant the \"improvements\" in performance are compared to the baselines. \n- All datasets that are used are generally considered \"easy\", such as MNIST, imagenet10. This is not a big weakness, but it makes the work seem less interesting. How would it perform in the real world?", "was_revised": true, "final_justification": "The authors have done a good job addressing my concerns during the rebuttal period. I still believe that the contribution of the new loss function are close to minor, since similar cosine loss functions have been seen before in the contrastive learning literature. But the authors have shown solid results and interesting theoretical insight, justifying a weak accept.", "rebuttal": "We appreciate your time and effort in reviewing our work, as well as your positive comments regarding our approach. Below, we address your comments point by point.\n\n\n**Neutral Comments**\n- >*\"The authors provide a theoretical results which can inform the choice of the angular scaling parameter ω and the embedding dimension D. I'm not convinced that this part requires an entire page of the paper since it's not like it removes a significant amount of the hyper parameters that have to be set/tuned like λ, the margin parameter pi, and other hyper parameters of the encoder and decoder networks.\"*\n\n    **[Response]** Regarding the concern about the theoretical derivation taking significant space, we clarify the reasons for emphasizing the careful derivation for hyperparameters $\\omega$ and $D$:   \n    - (a) Unlike DCC and other deep constraint embedding methods involving more hyperparameters, **only $\\omega$ and $D$ are specifically introduced by the SpherePair loss**. Other hyperparameters, such as regularization strength $\\lambda$ and network architectures, are general and shared across baselines (Particularly, **our method never involves a margin parameter pi** as you mentioned).   \n    - (b) Our conflict-free analysis (Propsitions 4.1–4.2; Theorem 4.3) provides principled defaults (e.g., $\\omega$=2, sufficiently large $D$) with formal guarantees on separability and feasibility, key to overcoming limitations of Euclidean-based approaches (lines 39–40, 90–92)., substantially reducing tuning burden compared with Euclidean margins and anchor settings. **The angular scaling parameter $\\omega$ and embedding dimension $D$ are critical to the success of our method**. Given the importance of this analysis to our method’s theoretical foundation and practical robustness,  and the fact that such theoretical results are novel in angular space learning, dedicating one page out of nine to this core contribution is well justified.\n\n\n\n**Weaknesses**\n- >*\"The contributions of the work are either very limited, or not well laid out/explained by the authors. As I understand, the methodological contribution compared to other deep constrained clustering approaches is simply to adapt a deep constraint embedding method so that it uses a logistic loss with a cosine similarity and a margin parameter. This loss function is, in my eyes, only a small contribution to the field as similar loss functions have been seen countless times in related contrastive representation learning literature.\"*\n\n    **[Response]** We respectfully clarify the significance of our contributions:   \n    - (a) **Theory.** Our setting is not supervised contrastive learning: constrained clustering (CC) uses sparse, pairwise, often imbalanced constraints without labels or anchors. Crafting a loss that (i) prevents negative‑pair conflicts, (ii) is $K$-insensitive during training, and (iii) induces cluster‑friendly geometry is non‑trivial. SpherePair’s angular logistic with a negative zone is supported by new theory specific to CC: a conflict‑free condition (Propsition. 4.1), the necessity of equidistance and matched $\\omega$ (Propsition. 4.2), and feasible $(\\omega,D)$ regimes linked to $K$ (Theorem 4.3). This yields actionable defaults, e.g., $\\omega$=2, large $D$, that largely remove the margin tuning required by Euclidean deep constraint embedding and BCE/KL end‑to‑end losses (lines 166–192; Appendix B).   \n    - (b) **Practice.** The result is robust, $K$-insensitive training with state‑of‑the‑art accuracy across seven datasets, three metrics, and multiple constraint budgets (Table 1; lines 253–263), and strong stability under imbalance (Figs. 3 and 4). These behaviors reflect a genuinely new CC solution, not a cosmetic variant of existing losses.\n\n- >*\"All datasets are quite small in the number of samples. If this is a limitation of the proposed method or the paradigm, it should be discussed.\"*\n\n    **[Response]** The selected seven datasets (CIFAR10, FMNIST, ImageNet10, MNIST, Reuters, STL10, CIFAR100-20) are standard and commonly used benchmarks in the field of deep constrained clustering (Appendix D.1). The dataset size is not a limitation for the proposed method; **our method is theoretically scalable to larger datasets** because:   \n    - (a) Constraint embedding learning based on the SpherePair loss involves only a constraint set of size $C$, independent of the dataset size $N$ (in practice, $C$ is usually much smaller than $N$).    \n    - (b) The only term involving the number of instances $N$ is the reconstruction loss (Eq. 2), used merely as a non-dominant regularizer. Its scalability to large $N$ is usually not an issue but may only affect practical training time (see our responses to Questions 3 & 4 below).   \n\n- >*\"I would like to see standard deviations for Table 1. I know recreating such a large table is a massive amount of work, so having them for some of the results in the appendix would be sufficient. Right now, I have no way to tell how significant the \"improvements\" in performance are compared to the baselines.\"*\n\n    **[Response]** Due to space, Table 1 omits deviations, but the exact settings of Table 1 correspond to IMB0 in Figs. 3 & 10–12, where we do report mean±std over 5 runs. **Our method demonstrates lower variance compared to baselines.** We will clarify it in our revision.\n\n- >*\"All datasets that are used are generally considered \"easy\", such as MNIST, imagenet10. This is not a big weakness, but it makes the work seem less interesting. How would it perform in the real world?\"*\n\n    **[Response]** We have demonstrated our method on a more challenging dataset, CIFAR-100-20, in Appendix E (Table 3). Results show SpherePair significantly outperforms baselines on this more challenging dataset (achieving 0.643 test ACC with 10k constraints, surpassing the second-best baseline by about 10%). As noted in our conclusion, we will explore its potential in broader real‑world applications in future work.\n\n\n**Questions**\n\n- >*\"...Thus, (1) as a simple baseline, I would like to see how related deep constraint embedding methods that use Euclidean distance perform when the embeddings are simply l2 normalized, after the encoding step. (2) I would like the authors to argue why their method is still needed if one can just normalize the embeddings to achieve clustering via cosine similarity/distance.\"*\n\n    **[Response]** As requested, we provide results for AutoEmbedder (the Euclidean-based embedding baseline), based on representations learned using the same settings as detailed in Appendix D.4 (lines 906–923), and compare clustering performance without and with applying $L_2$ normalization to the learned embeddings (test ACC (%), mean$\\pm$std over 5 runs, 10k constraints). Results showns that **simple normalization without angular constraint embedding learning degrades performance in ACC:**    \n    | Embedding    | CIFAR10 | FMNIST | ImageNet10 | MNIST | REUTERS | STL10 |\n    |--------------|---------|--------|------------|-------|---------|-------|\n    | Unnormalized | 87.4$\\pm$2.1 | 67.5$\\pm$2.5 | 96.6$\\pm$0.2 | 81.8$\\pm$9.7 | 91.0$\\pm$0.4 | 89.6$\\pm$0.5 |\n    | Normalized   | 73.4$\\pm$6.3 | 45.0$\\pm$7.9 | 96.6$\\pm$0.2 | 68.0$\\pm$3.3 | 35.8$\\pm$1.2 | 88.8$\\pm$0.6 |\n\n    The reason is that normalizing makes cosine $\\approx$ Euclidean for downstream clustering, but the training objectives differ critically: without our $\\min(\\omega\\theta,\\pi)$ mechanism and the $(\\omega,D)$ feasibility theory, Euclidean based embeddings must rely on ad-hoc margins and still cannot prevent pairwise conflicts, especially under imbalance. This further supports our response to **Weakness 1**. We appreciate your suggestion hence will acknowledge it and include these results in Appendix E in our revision.\n\n- >*\"Why are all the chosen datasets small? Can the method scale to a million or more samples?\"*\n\n    **[Response]** (Also see our response to **Weakness 2** above) The selected seven datasets (CIFAR10, FMNIST, ImageNet10, MNIST, Reuters, STL10, CIFAR100-20) are standard and commonly used benchmarks in the field of deep constrained clustering (Appendix D.1). The dataset size is not a limitation for the proposed method; **our method is theoretically scalable to larger datasets** because:   \n    - (a) Constraint embedding learning based on the SpherePair loss involves only a constraint set of size $C$, independent of the dataset size $N$ (in practice, $C$ is usually much smaller than $N$).     \n    - (b) The only term involving the number of instances $N$ is the reconstruction loss (Eq. 2), used merely as a non-dominant regularizer. Its scalability to large $N$ is usually not an issue but may only affect practical training time (see our responses to Questions 3 & 4 below).\n\n- >*\"What was the computational setup? How much gpu memory is required to run these experiments, how long did the experiments take?\"*\n\n    **[Response]** Our computational setup is detailed in line 826 (to be specific, a single Tesla V100 GPU with 16 GB of memory). Detailed runtime comparisons between SpherePair and baselines can be found in Appendix F (Tables 4–5).\n\n- >*\"What is the complexity of the method? How does it scale with the number of dimensions, number of samples, number of constraints?\"*\n\n    **[Response]** We report computational complexity  and single‑GPU wall‑times in Appendix F (lines 1101–1109, page 34).  SpherePair is faster than methods requiring hyperparameter searches in DCC and avoids the O(KD) anchor/assignment overhead.\n\n\nWe hope our clarifications resolve your concerns, **particularly about our contributions’ significance**, and present our work more clearly; if you have further questions, we would be happy to discuss them. We respectfully request that you reassess your evaluation in light of these detailed responses."}, {"review_id": "I7JAttUIkN", "reviewer": "Reviewer_4wat", "summary": "This paper proposed a novel angular constraint embedding approach for deep constrained clustering, termed SpherePair. The proposed method encodes pairwise constraints and leads to embeddings that are clustering-friendly in angular space.  Comparative evaluations with state-of-the-art DCC methods on diverse benchmarks, along with empirical validation of theoretical insights.", "questions": "See the weakness.", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths \n1, this paper proposed a novel angular constraint embedding approach for deep constrained clustering.\n2, The proposed method encodes pairwise constraints and leads to embeddings that are clustering-friendly in angular space.\n3, A lot of theoretical results are provided.\n4, The experiments are well organized.\nWeaknesses\n1, The motivation of using sphere is not clear, which is considered as the main contribution of this paper.\n2, Based on the sphere, the loss is constructed in equation 1. The main contribution of proposing a loss is a little simple.\n3, The SpherePair CC algorithm should be described in detail.", "was_revised": true, "final_justification": "Ｔｈａｎｋｓ　ｆｏｒ　ｔｈｅ　ｒｅｓｐｏｎｓｅｓ．", "rebuttal": "We appreciate your recognition of our work's strengths. Below, we respond explicitly to the three weaknesses you raised.\n\n\n1. >*\"The motivation of using sphere is not clear, which is considered as the main contribution of this paper.\"* \n\n    **[Response]** While we appreciate the perspective, we respectfully hold a distinct view. \n\n    **In fact, the motivation and advantages of angular(spherical) constraint embedding are thoroughly and repeatedly clarified throughout our paper**. (*For your reference, the $L_2$-normalized learned angular embedding $\\mathcal{Z}_{\\text{sphere}}$ (Eq. 5) are geometrically located on a hypersphere (lines 148–154), which is why our method \"using sphere\".*) Contrary to the reviewer's concern, our manuscript provides motivation at multiple points, as outlined below:  \n    - We start by identifying the limitations of end-to-end DCC methods (lines 32–37 and 79–86), motivating the need for deep constraint embedding methods.  \n    - We then recognize that existing deep constraint embedding methods operating in Euclidean space have significant drawbacks (lines 39–40 and 90–92), which can be resolved by embedding constraints in angular space, motivating our development of angular constraint embedding (\"using sphere\").  \n    - The motivation and the the unique advantages of our angular constraint embedding (\"using sphere\") approach are explicitly explained (lines 49–62 and 93–99) and strongly supported by empirical results and visualization analyses (Figs. 4 and 13).  \n    - The technical motivation is further clarified (lines 136-138).  \n\n2. >*\"Based on the sphere, the loss is constructed in equation 1. The main contribution of proposing a loss is a little simple.\"*\n\n    **[Response]** We respectfully disagree with this comment. The loss is simple by design, but it encodes a non‑trivial geometry: the $\\min(\\omega\\theta,\\pi)$ negative zone tied to a provably valid $\\omega$ produces equidistant clusters and removes pairwise conflicts, something prior Euclidean-based or assignment‑based losses do not ensure. This geometric property is what leads to the strong empirical robustness (Tables 1–2; imbalance visualizations in Figs. 4 and 13). **We firmly believe that the simplicity of our method is a strength, making it well-suited for real-world applications.**\n\n3. >*\"The SpherePair CC algorithm should be described in detail.\"*\n\n    **[Response]** **We respectfully but strongly disagree with this comment, as Algorithm 1 (page 5, main text) already provides a step‑wise procedure** (mini‑batching of constraints/instances, normalization before decoding, clustering, and prediction). Moreover, we provide our source code to ensure full transparency and reproducibility of our algorithm.\n\n\nWe hope our responses have addressed all your concerns; we respectfully request that you reassess our work in light of these detailed responses. We remain open to further questions or discussion."}, {"review_id": "zbeacKiHSc", "reviewer": "Reviewer_3qwK", "summary": "This paper proposes SpherePair, a novel angular constraint embedding method for deep constrained clustering (DCC) that encodes pairwise constraints in angular space via a geometric loss. SpherePair overcomes limitations of prior methods by enabling scalable, clustering-friendly embeddings without requiring the exact number of clusters, and demonstrates superior performance and generalization with theoretical and empirical support.", "questions": "See the Weaknesses above.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths** \n\n**1.** This work addresses the deep constrained clustering (DCC) using angular constraint embedding learning without anchors.\n\n**2.** Theoretical foundation is established.\n\n**3.** Sphere pair design explicitly removes the reliance on Euclidean distance and anchors. \n\n\n**Weaknesses**\n\n**1.** The authors claim that SpherePair does not require the exact number of clusters K during embedding learning, due to removing the anchors (Line 10). This feature is deemed as the conceptual difference compared with previous end-to-end DCC methods (Line 86). However, in practice, the SpherePair still relies on K, for example, y_i in Equation (1) is essentially determined by K; in Theorem 4.3., the value of ω is related to K. In other words, the K is implicitly introduced to the proposed method. This is computationally nontrivial and contradicts, to some extent, the original motivation of eliminating dependency on K. \n\n**2.** The article provides theoretical guidance for the selection of hyperparameters ω and D (Theorem 4.3), and the derivation of this theory depends on the total number of categories K. However, in practical applications, the author emphasizes that one of the advantages of his method is that it does not require an exact number of clusters, and recommends directly setting ω=2 and a sufficiently large D, which contradicts Theorem 4.3 in the author's article. Moreover, the author fails to fully demonstrate why the heuristic choice of ω=2 is still universal and optimal when K is unknown, nor does he provide more quantitative guidance on sufficiently large D or discuss the possible overfitting risks it may bring.\n\n**3.**  All derivations assume Lang =0 (i.e., a perfect embedding), which is rarely attainable in practice; the paper lacks any relaxed analysis or error‐bound estimation for the case Lang > 0.", "was_revised": true, "final_justification": "Dear AC,\n\nThe authors have addressed my main concerns, particularly the theoretical aspect regarding K. Accordingly, I am raising my score.", "rebuttal": "We appreciate the reviewer’s time and effort in reviewing our work as well as the positive comments regarding our approach. Below, we provide our response to clarify the raised concerns.\n\n\n**Weakness**\n1. >*\"The authors claim that SpherePair does not require the exact number of clusters K during embedding learning, due to removing the anchors (Line 10). This feature is deemed as the conceptual difference compared with previous end-to-end DCC methods (Line 86). However, in practice, the SpherePair still relies on K, for example, y_i in Equation (1) is essentially determined by K; in Theorem 4.3., the value of ω is related to K. In other words, the K is implicitly introduced to the proposed method. This is computationally nontrivial and contradicts, to some extent, the original motivation of eliminating dependency on K.\"*\n\n    **[Response]** The reviewer expresses concerns about our $K$‑insensitive embedding (line 10), arguing that the number of clusters $K$ is implicitly introduced into our method. With the highest respect, we clarify these misunderstandings as follows:\n    - (a) **The reviewer incorrectly assumes $y_i$ is determined by K.** In our constrained‑clustering setup, $y_i\\in{0,1}$ is a binary indicator: $y_i$=1 if the two instances should be in the same cluster, and $y_i$=0 otherwise, **which has been clearly defined (lines 117–118)**. These constraints contain no class labels and do not depend on the number of clusters K. Consequently, both the pairwise constraints and our training loss are $K$-independent.\n    - (b) **There is no contradiction at all, only a theory vs. practice separation**:\n        - **Theory** (Sect. 4). **If $K$ is known (or roughly bounded)**, Theorem 4.3 provides tight $(\\omega,D)$ conditions for equidistant embeddings: $D \\ge K−1$, and (i) $\\omega=\\frac{\\pi}{\\arccos(-1/(K-1))}$ when $D=K−1$; (ii) $\\omega \\ge \\frac{\\pi}{\\arccos(-1/(K-1))}$ when $D \\ge K$. This characterizes the best‑possible geometry. Lines 188–192, Appendix B.3. \n        - **Practice**. **Training does not need to know ground-truth $K$**. We choose $\\omega=2$ and a sufficiently large $D$; this is always valid because $\\frac{\\pi}{\\arccos(-1/(K-1))}<2$ for every $K>1$ (***Note**: for all $K>1$, $-\\frac{1}{K-1}\\in[-1,0)$, it follows that $\\arccos(-\\frac{1}{K-1})\\in\\bigl(\\frac{\\pi}{2},\\pi]$ and hence $\\frac{\\pi}{\\arccos(-1/(K-1))}<2$). **After training ONCE**, we infer $K$ cheaply from $\\mathcal{Z}_{\\text{sphere}}$, avoiding the repeated re‑training that end‑to‑end methods require. Lines 159–164; Sect. 5.2.3, Fig. 5 and Figs. 14–16.\n\n2. >*\"The article provides theoretical guidance for the selection of hyperparameters ω and D (Theorem 4.3), and the derivation of this theory depends on the total number of categories K. However, in practical applications, the author emphasizes that one of the advantages of his method is that it does not require an exact number of clusters, and recommends directly setting ω=2 and a sufficiently large D, which contradicts Theorem 4.3 in the author's article. Moreover, the author fails to fully demonstrate why the heuristic choice of ω=2 is still universal and optimal when K is unknown, nor does he provide more quantitative guidance on sufficiently large D or discuss the possible overfitting risks it may bring.\"*\n\n    **[Response]** We respectfully clarify that our method incurs **no theoretical contradiction**, and we have provided **sufficient empirical evidence for our quantitative guidance on $(\\omega, D)$ setting**.  \n    - (a) **No contradiction at all**. As discussed in our response to **Weakness 1 (b)** above, setting $\\omega$=2 and a sufficiently large $D$ does not contradict Theorem 4.3.  \n    - (b) **Quantitative guidance**. Theorem 4.3 guarantees optimal $(\\omega,D)$ settings when $K$ is known. When $K$ is unknown:  \n        -  Our choice $\\omega$=2 falls above the theoretical threshold for all $K$>1, and heatmaps (Figs. 5, 14-16) show it is near‑optimal across datasets and constraint sizes.    \n        - We also show that choosing $D$ from slightly below the threshold to far above the true $K$ (e.g., $D = 10$ up to $D = 500$ on CIFAR‑100‑20; see Figs. 5, 14–16 and Appendix E.3.1) typically works well in practice, providing users with highly flexible quantitative guidance. (lines 1031–1060)  \n\n3. >*\"All derivations assume Lang =0 (i.e., a perfect embedding), which is rarely attainable in practice; the paper lacks any relaxed analysis or error‐bound estimation for the case Lang > 0.\"*\n\n    **[Response]** We respectfully clarify and address this concern as follows:  \n    - (a) **In fact, achieving $\\mathcal{L}\\_{\\text{ang}}$ close to 0 is readily feasible in practice**. Below, we report the average terminal $\\mathcal{L}\\_{\\text{ang}}$ for SpherePair with 1k/5k/10k constraints on six datasets over 10 runs,  under the exact same experimental settings as detailed in Appendix D.4 (lines 863–873), corresponding to the “SpherePair (Ours)” configuration in Table 1. In all cases, the terminal $\\mathcal{L}_{\\text{ang}}$ is consistently below $5 \\times 10^{-4}$ with standard deviations all below $10^{-4}$, sufficiently small for a BCE-form loss, thus practically **eliminating the need for a relaxed analysis of $\\mathcal{L}_{\\text{ang}}>0$**. \n\n    | Constraints  | CIFAR10   | FMNIST    | ImageNet10 | MNIST     | REUTERS   | STL10     |\n    |-------|-----------|-----------|------------|-----------|-----------|-----------|\n    | 1k    | 2.34e-05  | 7.42e-05  | 7.09e-05   | 4.07e-05  | 6.81e-05  | 7.61e-05  |\n    | 5k    | 1.46e-04  | 2.61e-04  | 1.43e-04   | 1.70e-04  | 1.83e-04  | 2.17e-04  |\n    | 10k   | 2.27e-04  | 4.95e-04  | 3.54e-04   | 2.57e-04  | 2.20e-04  | 4.33e-04  |\n    \n    - (b) Importantly, the ease of achieving near-zero loss is due to the local nature of $\\mathcal{L}_{\\text{ang}}$, which focuses only on pairwise local relationships rather than involving complex global assignments and conflicts (lines 32–34). **This local property is one of our fundamental strengths**.  \n    - (c) Empirically, SpherePair drives $\\mathcal{L}\\_{\\text{ang}}$  to (near) zero on the training constraints, consistent with Proposition 1 and the resulting embeddings exhibit the predicted geometry (equidistant separation, compact clusters). This is witnessed by the broad plateaus at the theoretical $(\\omega,D)$ regions (Figs. 5, 14–16) and by clean cluster structure in t‑SNE even under heavy imbalance (Figs. 4 and 13). **In other words, the zero‑loss regime is reachable in practice, which is why the theory explains the observed robustness**. Lines 170–179, 273–296, 1031–1060.    \n\n    Nevertheless your concern is legitimate. We will clarify this point by adding a short stability statement and reporting the observed terminal $\\mathcal{L}_{\\text{ang}}$ shown in the above table in revision.\n\nWe believe our responses offer clear clarifications that strengthen both the conceptual novelty and the practical value of SpherePair for constrained clustering; we respectfully request that you reassess our work in light of these detailed responses. We remain open to further discussion."}]

Author rebuttal:

Meta-review: This paper proposes a deep constrained clustering (DCC) method that incorporates an angular loss called SpherePair loss with a geometric formulation to effectively learn cluster separation and improve performance in downstream clusterings tasks. The authors show comparative evaluations on multiple benchmarks to demonstrate the efficacy of the method.

Overall, the paper is written well and the authors provide good theoretical justification coupled with experiments on multiple datasets & ablation studies to tease apart the contribution of the method under various settings. One of the weaknesses highlighted by reviewers is that the gains shown in the paper do not seem significant compared to other baselines. While the authors mention (in the rebuttal) that they would like to emphasize the performance improvement for “limited constraint and heavy imbalance” setting, however real-world datasets may not naturally conform to this scenario. Perhaps there is a different way to highlight the efficacy of the learned representation for some other downstream task — would help strengthen the empirical part of the claim made in the paper. The paper reports evaluation results on multiple datasets which is good, one suggestion is to include comparisons on additional large(r) benchmark datasets — will demonstrate the utility of the approach for real-world settings. Otherwise, this is a well-rounded paper. The authors are encouraged to incorporate all the feedback including several clarifications noted in the discussions (e.g., no requirement for exact #clusters) to further improve the paper quality.
Decision: Accept (poster)