Semi-supervised clustering lets a person steer how data gets grouped without labeling every example. They supply a few pairwise hints: "these two belong together" (a must-link) or "these two do not" (a cannot-link). The trouble is that these hints are unreliable in a specific way. In one large study, adding constraints made clustering worse in 45% of runs, and no metric computed in advance predicted which runs would suffer (Limitations of Using Constraint Set Utility in Semi-Supervised Clustering). Our proposal starts from a guess about why. Most deep methods apply constraints by bending the shared feature space, pulling must-link pairs together and pushing cannot-link pairs apart. A few bad or unrepresentative pairs can then distort the geometry for every point, including the thousands that were never constrained.
A mixture of experts offers a different place to put the supervision. A mixture of experts is a model with several parallel sub-networks (the experts) plus a small gating network that decides which expert handles each input. When such a model is used for clustering, the gate's decision is the cluster assignment, as in MiCE: Mixture of Contrastive Experts for Unsupervised Image Clustering. We propose applying must-link and cannot-link constraints only to the gate's assignment probabilities, as a soft pairwise prior over "which expert handles this point." The shared representation and each expert's internal feature space would stay under self-supervised training alone. The claim to test is this: moving constraints from the embedding to the routing decision keeps most of the steering benefit, sharply lowers how often constraints hurt, and preserves information that the constraints did not ask about.
Core Claim
We make three testable predictions. The first is that constraining only the gate matches embedding-level constraints in accuracy when the constraints are clean. The second is that it degrades more gracefully when constraints are noisy or unrepresentative, measured by the fraction of random constraint sets that leave the model worse than using no constraints at all. The third is that it leaves attributes the constraints did not target decodable from the representation. If gate-only constraints lose substantial accuracy relative to embedding constraints even on clean pairs, the claim fails. If a much simpler post-hoc pipeline matches them, the claim fails too.
Relation to Prior Work
Two papers supply the method. MiCE casts unsupervised image clustering as a mixture of contrastive experts. A gating network assigns each image to an expert, the expert performs instance discrimination within its subset, and everything is fit as one lower bound on the likelihood via expectation-maximization. It has no route for external supervision. A Probabilistic Approach to Constrained Deep Clustering, known as DC-GMM, injects a pairwise constraint matrix $W$ as a conditional prior over cluster assignments inside a variational autoencoder. It approximates the quadratic pairwise cost within each batch and shows that a soft formulation lets the data override false constraints. DC-GMM, however, has a single encoder, so its constraints still shape one shared latent space. It also fixes the cluster proportions $\pi$ to be uniform to keep normalization tractable. We reuse DC-GMM's form of the prior and batch approximation, but attach it to MiCE's gating distribution. There, cluster membership is already conditioned on each input, so no global $\pi$ is needed. Whether this truly avoids the normalization issue is something we verify rather than assume.
Two other papers motivate the proposal by showing where embedding-level constraints go wrong. The first is the detrimental-constraints study above, which reports within-dataset correlations between constraint utility and accuracy as low as −0.06 on Ecoli and −0.12 on Glass. The second is Dictionary Learning in Optimal Metric Space, which learns a projection that deliberately warps distances according to constraints. That is exactly the kind of global distortion we hypothesize is fragile. The opposite design philosophy appears in the mixture-of-experts literature. Load Balancing Mixture of Experts with Similarity Preserving Routers regularizes the gate to preserve input geometry rather than warp it, and reports lower expert redundancy and better token efficiency. Our design sits between the two: geometry is preserved in the representation, while the constraints act on assignments.
The closest connecting work fails to address this question in different ways. DMCAR: Disentangled Mixture-of-Experts with Context-Aware Routing for Multi-View Clustering uses shared and view-private expert pools for multi-view clustering, but it is fully unsupervised. Deep Multi-view Semi-supervised Clustering with Sample Pairwise Constraints (DMSC) uses constraints as forces in an autoencoder's latent space, with no routing. Mixture-of-Clustered-Experts assigns expert groups by k-means on frozen embeddings, again without constraints. Coupling Experts and Routers in Mixture-of-Experts via an Auxiliary Loss treats router weights as cluster centers, but its "constraints" are synthetic and internal, not user-provided relations between instances. None of these asks where pairwise supervision should enter a conditional-computation model. That question is the whole of this proposal.
Research Program
The model is MiCE with one added term. Let $g(c \mid x_i)$ be the gate's probability that input $x_i$ is handled by expert $c$ among $K$ experts. Let $w_{ij}$ be $+1$ for a must-link, $-1$ for a cannot-link, and $0$ otherwise. Within each batch $B$, we add to MiCE's objective a pairwise agreement term:
$$ \mathcal{L}_{\text{pair}} = -\lambda \sum_{i,j \in B} w_{ij}\, \log\!\Big(\epsilon + \sum_{c=1}^{K} g(c \mid x_i)\, g(c \mid x_j)\Big)\cdot \mathbb{1}[w_{ij}=1] \;-\; \lambda \sum_{i,j \in B} \log\!\Big(1 - \sum_{c} g(c\mid x_i)\, g(c\mid x_j) + \epsilon\Big)\cdot \mathbb{1}[w_{ij}=-1]. $$
In this term, $\sum_c g(c\mid x_i)g(c\mid x_j)$ is the probability that the two points land in the same expert, $\lambda$ sets the constraint strength, and $\epsilon$ is a small constant for numerical stability. This is the batch-wise analogue of DC-GMM's conditional prior, applied to routing probabilities.
The key design choice concerns the gradients. The term's gradient flows into the gate's parameters and, in the main variant, into a gate-only head. It is stopped before the shared backbone and before the expert-specific contrastive embeddings. The experts continue to learn by MiCE's instance discrimination within whatever subset the gate hands them. A must-link pair routed to the same expert therefore ends up near each other only because that expert organizes its own data. It is not forced together in a global space.
We build three variants that differ only in where $\mathcal{L}_{\text{pair}}$ acts. The gate-only variant uses the stop-gradient described above. The full-backprop variant lets the same term reach the backbone. The embedding variant applies DMSC-style pull and push forces on backbone features and leaves the gate unconstrained. Comparing the three isolates the placement question. Everything else, including architecture, augmentations, number of experts, and training schedule, is held fixed at MiCE's published configuration.
The analysis has three parts. First, we measure the degradation rate. We draw many random constraint sets at each size and noise level and record the fraction of sets for which the constrained model is worse than the unconstrained MiCE starting point. This directly mirrors the 45% statistic. Second, we measure collateral damage: how well a linear probe on the frozen backbone recovers a label the constraints never mentioned. Third, we measure load, meaning expert usage entropy, to check that constraints on the gate do not funnel data to a few experts.
Baselines
The naive reference point is unconstrained MiCE, trained identically. It is the "do nothing" option, and every constrained run is scored against it to compute the degradation rate. On CIFAR-10, MiCE reports 83.5% clustering accuracy, and 44.0% on CIFAR-100 (MiCE). Our reproduction must land near these numbers before any constrained comparison counts. The file gives no reported MiCE number for STL-10.
The strongest existing constrained method is DC-GMM, because it is the soft, probabilistic constrained clusterer with the documented robustness to flipped constraints that our method must beat on its own ground. The file reports 80.0% accuracy on Fashion-MNIST for DC-GMM versus 68.1% for C-IDEC (A Probabilistic Approach to Constrained Deep Clustering). On Heart Echo it reports 92.5% for camera-view clustering and 73.3% for preterm status. We run DC-GMM on the same backbone features, the same constraint sets, and the same noise draws. It gets the same hyperparameter search budget as our method, including its constraint weight, and its original configuration is kept where it performs better. Beating it means equal or higher accuracy on clean constraints and a lower degradation rate at 20–30% flipped pairs, across at least three datasets.
The embedding-level deep baseline is DMSC-style pull and push forces with reconstruction protection (Deep Multi-view Semi-supervised Clustering with Sample Pairwise Constraints), run in its single-view form on our backbone. DMSC reports 96.79% accuracy on STL-10 in its multi-view setting. That setting and its constraint budget are not comparable, so we treat the number as context, not a target. For tabular sanity checks on the UCI sets, the reference is MPCK-Means. The file reports its Silhouette-selected default reaching an average relative score of 0.814 (Limitations of Using Constraint Set Utility in Semi-Supervised Clustering).
The ablations that isolate the key ingredient are the full-backprop and embedding variants described above. They share the loss form and differ only in placement. We add a dense control with a single expert and a constraint-trained classification head. This separates the benefit of having multiple experts from the benefit of simply constraining an output head.
Why not just…?
Why not just run MiCE unsupervised and then apply a constrained clustering algorithm to its embeddings? This is the most serious threat. It gives constraints the same "don't touch the representation" property at almost no cost. MiCE's own argument that two-stage pipelines are a limiting case of joint optimization, together with its 8.7-point gain over MoCo plus k-means, suggests joint training helps. That evidence concerns unsupervised clustering, though, not constraints. We therefore run it directly, applying post-hoc constrained k-means and post-hoc DC-GMM on frozen MiCE features with identical constraint sets. If post-hoc matches gate-only within noise on accuracy and degradation rate, the proposal reduces to "freeze the features," and we will report it as that.
Why not just fine-tune a contrastive network with must-links as positives and cannot-links as negatives? This is the embedding-warping approach we hypothesize is fragile. The detrimental-constraint results and the drops reported for deterministic constrained baselines under noise in DC-GMM are the motivating evidence. The embedding variant is exactly this baseline, and the collateral-damage probe shows whether it erases untargeted information.
Why not just use DC-GMM, which already handles noisy constraints? DC-GMM's robustness comes from its soft prior, and our method borrows that prior. What differs is that DC-GMM's constraints still shape a single shared latent space and rely on fixed uniform proportions. If DC-GMM's degradation rate is already near zero and its untargeted-attribute probe is intact, then routing adds nothing, and the comparison on UTKFace below will show that.
Proposed Experiments
We evaluate on CIFAR-10, CIFAR-100, STL-10 and Fashion-MNIST using accuracy, normalized mutual information and adjusted Rand index. Constraint budgets range from a few hundred to several thousand pairs sampled from true labels, and noise levels flip 0%, 10%, 20% and 30% of the pairs. Each cell uses at least twenty independent constraint draws, so degradation rates carry confidence intervals.
The decisive experiment uses UTKFace, where DC-GMM showed that swapping $W$ switches the partition between gender and ethnicity. We train each variant with gender constraints only, then probe the frozen backbone for ethnicity, and repeat with the roles reversed. The core claim predicts that the gate-only variant partitions by the constrained attribute while leaving the other attribute as linearly decodable as in unconstrained MiCE, and that the embedding and full-backprop variants lose some of it. We also apply the same protocol to Heart Echo, comparing camera view against maturity. The claim is supported if three things hold at once: gate-only matches the embedding variant on clean constraints, it has a lower degradation rate at 20–30% noise, and it preserves the untargeted attribute. The claim is refuted if post-hoc constrained clustering on frozen MiCE features matches it. Expert usage entropy is reported throughout to confirm that constraining the gate does not collapse load.
References
- Limitations of Using Constraint Set Utility in Semi-Supervised Clustering
- MiCE: Mixture of Contrastive Experts for Unsupervised Image Clustering
- A Probabilistic Approach to Constrained Deep Clustering
- Dictionary Learning in Optimal Metric Space
- Load Balancing Mixture of Experts with Similarity Preserving Routers
- DMCAR: Disentangled Mixture-of-Experts with Context-Aware Routing for Multi-View Clustering
- Deep multi-view semi-supervised clustering with sample pairwise constraints
- Mixture-of-Clustered-Experts: Advancing Expert Specialization and Generalization in Instruction Tuning
- Coupling Experts and Routers in Mixture-of-Experts via an Auxiliary Loss