acceptodds
Under review as a conference paper at ICLR 2027

When Equipartition Corrupts Relational Learning: Capacity–Geometry Mismatch under Long Tails

Abstract

Balanced optimal-transport assignments are widely used in representation learning to prevent collapse by enforcing equal mass across latent components. Under long-tailed data, however, this constraint can conflict with the geometry supported by the evolving representation. We identify this capacity–geometry mismatch as a source of systematic distortion in relational learning: mismatched component capacities displace samples across representation-supported basins, perturbing transport assignments and, in turn, contaminating the relational teacher and distillation signal. We theoretically characterize this mechanism and establish a finite-batch connection between full-bank transport relations and the minibatch teacher used during optimization. Guided by this analysis, we introduce PACI, which estimates representation-supported pseudo-basin capacities and applies them consistently to both transport assignment and relation construction. PACI consistently outperforms a broad range of state-of-the-art deep clustering methods across long-tailed benchmarks. Controlled capacity perturbations trace the predicted progression from capacity mismatch to assignment displacement and teacher contamination, while intervention experiments isolate assignment displacement as the dominant pathway to degraded representation quality, distinct from relation-normalization effects. These findings generalize across training regimes and long-tailed settings, supporting geometry-matched capacity as a principled design rule for long-tailed relational representation learning.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
deep clustering, unsupervised representation learning, optimal transport, relational learning, long-tailed learning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_PuWSOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The work analyzes how uniform optimal-transport capacities can distort relational supervision when learned representations have uneven cluster sizes. It proposes PACI, which estimates cluster capacities from the evolving representation and uses them to construct transport assignments and a relational teacher. The paper combines theoretical analysis, long-tailed clustering benchmarks, and controlled interventions to show that matching capacities to representation geometry can improve clustering performance.

Critical strengths
  • The experiments and their broadness are meaningful and interesting.
  • The ablations and analyzes connects a concrete design choice to both supervision and downstream performance.
Critical weaknesses
  • The paper does not quantify the additional training time and memory required by periodic feature extraction, clustering, and transport computation.
  • The size of the experiments ends with CIFAR-100 and should be extended to imagenet size.
  • Unclear usefulness of the theoretical bound.
  • Evaluation focuses on artificially constructed long-tailed benchmarks, leaving the effectiveness of geometry-matched capacities under naturally occurring imbalance insufficiently established.
Questions for authors
  • How should the finding that reducing contamination did not improve accuracy affect the proposed explanation of PACI’s gains?
  • What evidence distinguishes contamination reduction from other changes induced by the assignment intervention?
  • Do the assignment-versus-normalization effects on final accuracy also hold on CIFAR-100 or Tiny-ImageNet?
4 comments
AuthorsOpenReview ↗

Response to Reviewer PuWS (1/3)

Thank you for your thoughtful review. We appreciate your recognition of the breadth of our experiments and the analyses connecting capacity choices to supervision and downstream performance. We added semantic interventions, four-arm training on larger datasets, cost measurements, and evaluations at larger scale and under natural imbalance. We address your comments and questions below.

Reply to Q1 & Q2. Semantic supervision and the filtering result

Why filtering gives small accuracy gains. Filtering removes wrong-semantic relations and also discards useful correct-semantic supervision. We compared stability filtering with label-assisted semantic repair. Repair changes which samples receive the relation weights while preserving each row's weight multiset, entropy, and L2 norm.

Preserving these row statistics provides a targeted test of semantic connections. Similarity and graph structure also change under rewiring. We interpret the results as evidence that semantic connections contribute to learning, alongside the overall effect of capacity choices measured by the four-arm experiment.

The table reports contamination (ΔC) and CAA changes in percentage points. Retention is the percentage of original correct-semantic mass kept by filtering.

DatasetFilter ΔCRetention (%)Filter ΔCAARepair ΔCRepair ΔCAA
CIFAR-10−1.7677.24+0.14−1.54+1.02
CIFAR-20−1.3884.15+0.09−1.07+0.75

Repair produces larger accuracy gains with smaller contamination reductions. Random filtering lowers CAA by 0.82/0.48 points on CIFAR-10/20. These comparisons explain the stability-filter result through the loss of useful supervision and support preserving correct connections when removing incorrect relations.

Direct damage and repair on larger datasets. We tested two levels of semantic damage and a repair condition on CIFAR-100 and Tiny-ImageNet, preserving the same per-row weight statistics. Changes below are relative to the corresponding control, in percentage points.

DatasetModificationΔCΔCAAΔNMIΔARI
CIFAR-100Lower damage+1.97−0.54−1.25−0.65
CIFAR-100Higher damage+2.75−1.01−1.98−1.33
CIFAR-100Repair−1.35+1.05+1.84+1.24
Tiny-ImageNetLower damage+1.42−0.31−0.84−0.34
Tiny-ImageNetHigher damage+2.03−0.58−1.34−0.88
Tiny-ImageNetRepair−0.94+0.51+1.77+1.30

Greater semantic damage produces larger losses in all three clustering metrics on both datasets, and repair improves all three. These bidirectional effects connect the teacher's semantic relations to final performance while retaining its row-weight statistics. Together with the filtering comparison, they support a contribution of semantic supervision to PACI's gains.

Reply to Q3. Assignment and normalization on larger datasets

Yes. Assignment capacity also has the larger effect on final clustering accuracy on CIFAR-100 and Tiny-ImageNet. We extended the paper's four-arm comparison by independently using estimated or uniform capacities for transport assignment and relation normalization.

The table reports final CAA loss relative to EE, in percentage points. Positive values measure the accuracy decrease from EE.

ArmAssignment capacityNormalization capacityCIFAR-100Tiny-ImageNet
EEEstimatedEstimated0.0000.000
EUEstimatedUniform+0.170+0.429
UEUniformEstimated+3.981+2.756
UUUniformUniform+3.837+2.862

Replacing estimated assignment capacity with uniform capacity lowers CAA by 3.981/3.667 points on CIFAR-100 under estimated/uniform normalization. The corresponding losses on Tiny-ImageNet are 2.756/2.433 points. Changing normalization produces absolute CAA differences of at most 0.170/0.429 points on the two datasets.

The assignment effect therefore dominates under both normalization choices on both datasets, extending the original final-accuracy finding to larger class counts.

AuthorsOpenReview ↗

Response to Reviewer PuWS (2/3)

Reply to W1. Training time and GPU memory

PACI's measured step times, including teacher refresh, are close to BYOL. We measured the methods in separate GPU-exclusive processes on one RTX 4090. Both used ResNet-18, batch size 256, AMP, and the same data pipeline and starting optimizer state. Times are mean ± standard deviation over three timing repetitions. Memory is the steady-window peak GPU allocated memory.

DatasetMethodStep (ms)Including refresh (ms/step)Peak allocated (MiB)GPU bank (MiB)
CIFAR-100BYOL78.60±2.1278.60±2.121571.58—
CIFAR-100PACI75.82±0.4476.20±0.451654.9782.59
Tiny-ImageNetBYOL67.90±0.1267.90±0.12820.12—
Tiny-ImageNetPACI67.86±0.4868.84±0.49897.7375.91

Complete teacher refresh includes feature extraction, preprocessing, clustering, OT, and bank construction. A subsequent refresh took 1.436±0.045 s on CIFAR-100. At its 50-epoch interval, this adds 0.378 ms/step, about 0.50% of PACI's normal step time. On Tiny-ImageNet, a complete refresh took 2.060±0.026 s and adds 0.981 ms/step under its refresh schedule.

The memory increase is 83.39 MiB (5.31%) on CIFAR-100 and 77.61 MiB (9.46%) on Tiny-ImageNet, largely accounted for by the retained bank. Training warm-up peaks are 3642.02/3719.52 MiB for BYOL/PACI on CIFAR-100 and 2931.37/3006.58 MiB on Tiny-ImageNet. These measurements include the additional relation storage and complete refresh cost requested in the review.

Reply to W2 & W4. Larger datasets and natural imbalance

ResNet-50 on ImageNet-LT and iNature500. We extended evaluation to ImageNet-LT with 1,000 classes and iNature500 with 500 naturally imbalanced classes. All methods use ResNet-50 without external pretraining, with their own warm-up or self-supervised learning stages on the target data. Results are CAA (%).

MethodImageNet-LTiNature500
BYOL10.628.1
ConMix12.329.4
MiniClustering (MaxiClustering variant)12.730.7
PACI13.431.2

PACI exceeds the strongest comparison by 0.7/0.5 CAA points on ImageNet-LT/iNature500. These results extend the evaluation to a larger backbone, 1,000-class clustering, and natural class imbalance.

Shared-DINO ViT-B/16 on iNature500. We also evaluated the naturally imbalanced dataset under a common ImageNet-pretrained DINO initialization. Initial DINO is the feature-clustering reference before additional adaptation. All metrics are percentages.

MethodCAAACCNMIARI
Initial DINO29.336.965.813.0
P²OT32.840.267.113.4
SP²OT34.538.467.813.9
PACI36.739.167.314.2

PACI improves CAA over the strongest OT baseline by 2.2 points and over the common starting point by 7.4 points. The iNature500 results provide natural-imbalance evidence under both target-data learning with ResNet-50 and shared pretrained initialization with ViT-B/16.

AuthorsOpenReview ↗

Response to Reviewer PuWS (3/3)

Reply to W3. Interpretation of the finite-batch bound

Theorem 1 connects the full-bank semantic composition analysis to the normalized minibatch teacher used during optimization. It quantifies the effects of relation preprocessing and batch sampling through measurable properties of the relation rows.

We evaluated its terms at the actual training batch size B=256. Here κ measures row concentration and δ measures the change introduced by preprocessing. The overall gap is the absolute difference between full-bank contamination and the Monte Carlo estimate of mean minibatch contamination. The per-anchor gap measures the absolute discrepancy for individual anchors before averaging. Bounds are computed per anchor and then averaged. δ, bounds, and gaps below are in percentage points.

DatasetMean κMean δUpper boundOverall gapPer-anchor gap
CIFAR-107.8140.078414.130.0260.991
CIFAR-2010.2570.113516.600.5191.246
CIFAR-1008.3460.105219.100.5871.524
Tiny-ImageNet14.1870.276120.610.3811.957

The analytical bounds are conservative. Observed overall discrepancies remain below 0.6 percentage points, and mean per-anchor discrepancies remain below 2.0 points across all four datasets. These results show close empirical agreement between full-bank relations and the minibatch teacher used during training.

Does the capacity effect reach the training teacher? We held the final features, prototypes, and transport cost fixed and compared uniform with matched capacities through raw relation H, normalized full-bank relation R, and minibatch teacher T. The uniform-minus-matched contamination gaps were 8.145→8.221→7.992 points on CIFAR-100 and 3.478→3.284→3.688 on Tiny-ImageNet. CIFAR-10/20 also favored matched capacity at every stage. Thus, the capacity-matching advantage persists through preprocessing and minibatch row normalization.

The bound makes explicit how batch size, row concentration, and preprocessing jointly control an upper bound on the full-bank–minibatch discrepancy. Larger batches reduce the sampling term, while more concentrated rows increase it. We will include these measured quantities and their interpretation in the revision so that readers can relate the full-bank analysis to the actual training configuration.

Thank you again for your time and helpful comments. We hope these additions address your concerns and would be happy to clarify any remaining questions.

Thank you for the detailed response and substantial additional experiments. My concerns have been sufficiently addressed, and I maintain my weak acceptance recommendation.

Reviewer_iKf9OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In this paper, the authors examine how the use of equipartition constraints in optimal transport affects relational representation learning for long-tailed data. They find that there is a capacity-geometry mismatch, as uniform component capacities conflict with the nonuniform basin structure formed by the learned representations. This conflict may force some sample mass to be assigned outside its original geometric basin, which will result in changes to the transported component compositions and may create incorrect semantic relations in the relational teacher.

To characterize this issue, the authors establish a lower bound for the displacement of assignments due to capacity mismatch; they characterize teacher contamination through the semantic composition of transported components; and they develop a finite-batch bound that shows how full-bank relations connect to the minibatch teacher being utilized during optimization.

Using the results of this analysis, the authors developed PACI to use EMA representations to estimate pseudo-basin capacities using spherical K-means and then apply those capacities to both relation construction and optimal-transport assignment. The resulting relational teacher is then used in conjunction with a BYOL-based instance learning objective for cross-view distillation.

Experiments using five different long-tailed clustering benchmark datasets showed improved class-averaged accuracy compared to previous methods. To study how capacity mismatches affected assignments, teacher contamination, and downstream clustering performance, additional capacity perturbations, basin-capacity shuffling, and controlled training interventions were conducted.

Critical strengths

A cohesive description of the relationship between capacity mismatches and relational supervision.

The authors address an important problem in long-tailed representation learning: imposing uniform capacity on each component may lead to a conflict between the capacity of each component and the structure of the learned representation. This can result in sample mass being assigned to components other than those associated with its original geometric basin.

The theoretical analysis gives us a formal way to describe how the displacement of assignments occurs due to differing capacity levels, as well as how the relation matrices produced from transported components depend on their semantic compositions and the amount of incorrect semantic information they contain. Finally, Theorem 1 shows how this analysis is related to the use of minibatches for supervising models.

The mathematical relationships are based on existing principles; however, when integrated, they provide a unified explanation of how capacity constraints affect the relational teacher employed for representation learning.

Encouraging experimental results with well-designed intervention studies.

The authors evaluate PACI using five long-tailed clustering benchmarks and compare it with many other approaches. The authors report that their approach (PACI) achieves the highest class-averaged accuracy in each of the five main benchmark settings. PACI also shows improvements of between 4.31 and 12.51 percentage points over BYOL.

Controlled experiments are also a strong point of the study. The authors examine capacity changes while keeping representation geometry constant, showing that increased capacity mismatch results in larger assignment displacement and increased teacher contamination.

In addition, the four-arm design of the study separates assignment capacity and relation-normalization capacity when they are evaluated against each other under matched training conditions. The analysis shows that assignment capacity has a substantially greater effect on the quality of clustering results than relation-normalization capacity. The empirical results presented in this study offer additional insights beyond the typical comparative evaluation of models.

Critical weaknesses

A cohesive description of the relationship between capacity mismatches and relational supervision.

The authors address an important problem in long-tailed representation learning: imposing uniform capacity on each component may lead to a conflict between the capacity of each component and the structure of the learned representation. This can result in sample mass being assigned to components other than those associated with its original geometric basin.

The theoretical analysis gives us a formal way to describe how the displacement of assignments occurs due to differing capacity levels, as well as how the relation matrices produced from transported components depend on their semantic compositions and the amount of incorrect semantic information they contain. Finally, Theorem 1 shows how this analysis is related to the use of minibatches for supervising models.

The mathematical relationships are based on existing principles; however, when integrated, they provide a unified explanation of how capacity constraints affect the relational teacher employed for representation learning.

Encouraging experimental results with well-designed intervention studies.

The authors evaluate PACI using five long-tailed clustering benchmarks and compare it with many other approaches. The authors report that their approach (PACI) achieves the highest class-averaged accuracy in each of the five main benchmark settings. PACI also shows improvements of between 4.31 and 12.51 percentage points over BYOL.

Controlled experiments are also a strong point of the study. The authors examine capacity changes while keeping representation geometry constant, showing that increased capacity mismatch results in larger assignment displacement and increased teacher contamination.

In addition, the four-arm design of the study separates assignment capacity and relation-normalization capacity when they are evaluated against each other under matched training conditions. The analysis shows that assignment capacity has a substantially greater effect on the quality of clustering results than relation-normalization capacity. The empirical results presented in this study offer additional insights beyond the typical comparative evaluation of models.

Questions for authors

Comparison with closely related transport methods (experimental validation).

Can the authors compare directly with other imbalance-aware optimal transport methods (e.g., P2 OT and SP2 OT) using matched training and evaluation settings where possible?

Comparing the proposed pseudo-basin capacity estimation with other types of nonuniform capacity estimators while keeping the relational learning framework unchanged would provide additional clarity on how much value the geometry-matched capacity estimation alone adds.

Reliability of pseudo-basin capacity estimation (experimental validation).

Can the authors analyze how the estimated pseudo-basin capacities evolve during training and whether the resulting geometric basins align with the underlying semantic class structure?

How sensitive is PACI to errors in the assignment of pseudo-basins, the number of clusters used, and the quality of the initial representation? This analysis would provide a sense of whether the proposed method continues to be effective even if the learned geometric structure is inaccurate or unstable.

The relationship between teacher contamination and clustering performance (experimental investigation).

Can the authors provide additional evidence demonstrating that the improvement in clustering performance is caused by reduced teacher contamination, as opposed to simply reflecting a more beneficial assignment structure?

In particular, what does the stability-filter result in Appendix D.2 (reduced contamination without improved final accuracy) imply about the proposed mechanism? A clearer distinction between the causal effects of altering assignment capacity and the role of teacher contamination as a potential mediator would strengthen the main findings.

The practical value of the finite-batch theoretical bound (technical clarification).

Could the authors provide the empirically determined values of the concentration and preprocessing terms from Theorem 1 under the actual training configurations?

In addition to determining whether the finite-batch bound is sufficiently informative to provide guidance for experimental settings, it would be useful to know how the number of clusters and the degree of data imbalance affect the bound. This would help us understand the practical application of the theoretical relationship between full-bank relations and minibatch supervision.

4 comments
AuthorsOpenReview ↗

Response to Reviewer iKf9 (1/3)

Thank you for your thoughtful review. We appreciate your recognition of our unified analysis, encouraging benchmark results, and well-designed intervention studies. Your questions helped us strengthen the direct OT comparisons, examine the reliability of capacity estimation, and explain how the teacher's semantic relations affect clustering performance. We address your comments and questions below.

Reply to W1 & Q1. OT comparisons and capacity estimators

We compared PACI, P²OT, and SP²OT using a shared DINO initialization.

Table 1 reports native clustering outputs. Results are reported as mean ± SD across 3 seeds.

DatasetMethodCAAACCNMIARI
CIFAR-100DINO47.67±1.3251.90±1.0468.55±0.3140.12±1.15
CIFAR-100P²OT49.85±1.0152.54±1.2569.39±0.6741.93±0.48
CIFAR-100SP²OT51.74±0.7750.21±0.7469.66±0.2442.04±0.77
CIFAR-100PACI54.00±0.7852.13±0.8372.76±0.2942.58±0.85
Tiny-ImageNetDINO19.24±0.7118.93±0.6141.57±0.6716.57±0.43
Tiny-ImageNetP²OT20.01±0.5419.57±0.4243.27±0.7217.02±0.76
Tiny-ImageNetSP²OT21.23±0.8720.73±0.7543.08±0.3418.92±1.20
Tiny-ImageNetPACI23.12±0.4522.87±0.9746.54±0.6717.53±0.81

PACI exceeds the strongest OT baseline by 2.26/1.89 CAA points on CIFAR-100/Tiny-ImageNet and achieves the highest NMI on both datasets.

Table 2 reports online-CLS results using a common readout and clustering protocol. Values are CAA (%).

DatasetInitial DINOP²OTSP²OTPACI
CIFAR-10047.67±1.3248.04±1.0949.21±1.0253.45±0.55
Tiny-ImageNet19.24±0.7121.62±0.9221.34±0.4922.57±0.47

PACI exceeds the strongest OT baseline by 4.24/0.95 CAA points and improves over the shared DINO initialization on both datasets.

Capacity estimators. In the paper's BYOL-based setting, we fixed the relational objective and training protocol. Shuffling permutes basin–capacity pairs and preserves the capacity histogram at every refresh. MGCE is a multigranularity geometric estimator.

Table 3. Capacity controls (final CAA, %).

DatasetMatchedUniformShuffledMGCE
CIFAR-10029.6027.3427.8628.12
Tiny-ImageNet18.7217.5417.2017.21

Matched capacity improves final CAA over the strongest alternative by 1.48/1.18 points on CIFAR-100/Tiny-ImageNet. The histogram-preserving shuffle shows the importance of matching each capacity to its geometric basin. The comparison with MGCE further supports the occupancy-based estimator.

AuthorsOpenReview ↗

Response to Reviewer iKf9 (2/3)

Reply to Q2. Capacity reliability and robustness

Capacity evolution and semantic alignment. We recorded capacities at every teacher refresh. Table 4 brings together the estimated capacity distributions and the semantic quality of the basins used to estimate them.

Table 4. Capacity and basin evolution. Normalized entropy and TV from uniform follow epochs 201→400→800. Label-based NMI/purity follow epochs 201→800.

DatasetCapacity entropyTV from uniformBasin NMI (%)Basin purity (%)
CIFAR-1000.9954 → 0.9843 → 0.96380.0843 → 0.1540 → 0.221943.82 → 57.5035.54 → 47.96
Tiny-ImageNet0.9961 → 0.9867 → 0.97360.0574 → 0.0912 → 0.154228.12 → 40.3026.13 → 38.64

The estimated capacities become more nonuniform as basin NMI and purity improve. These trajectories show that capacity estimation adapts to the evolving geometry and that the basins become more semantically informative during training.

Weak initial representations. Matched capacities reduced teacher contamination relative to both uniform and shuffled capacities at all four warm-up stages, 25, 50, 100, and 200 epochs, on both datasets. At each stage, we held the features, preprocessing, prototypes, and basin assignments fixed and changed the capacities. Construction K was 100 on CIFAR-100 and 200 on Tiny-ImageNet.

The earliest representations had CAA/NMI of 9.51/24.50 on CIFAR-100 and 5.46/15.75 on Tiny-ImageNet. By epoch 200, these values reached 28.18/43.82 and 18.45/28.12, respectively. This trajectory covers weak initial features and progressively more informative representations.

The matched-capacity reduction in contamination relative to uniform grew from 0.0235 to 1.9733 percentage points on CIFAR-100 and from 0.0132 to 0.8420 points on Tiny-ImageNet. Relative to shuffled capacities, the corresponding reductions grew from 0.0312 to 2.846 and from 0.0284 to 1.354 points. The benefit was present at every stage and increased with longer warm-up. Shuffled capacities also had higher contamination than uniform capacities at every stage, supporting the importance of the correspondence between each basin and its capacity.

Construction K. We tested K = 50/100/200 on CIFAR-100 and K = 100/200/400 on Tiny-ImageNet, including half and twice the semantic class count. Evaluation remained fixed at 100 and 200 semantic classes, respectively. Teacher comparisons used the same representation within each stage–K condition, and training comparisons used the same settings across capacity variants.

At epochs 200, 400, and 800, matched capacities had lower contamination than both uniform and shuffled capacities in all nine stage–K conditions on each dataset. This held for both the full-bank relation and the minibatch teacher.

Table 5. Construction-K sensitivity. Final contamination gaps are uniform−matched. Performance gains use the stronger uniform/shuffled control per metric. All changes are in percentage points.

DatasetConstruction KContamination gapΔCAAΔNMIΔARI
CIFAR-10050+4.06+0.84+1.43+0.94
CIFAR-100100+3.87+1.74+1.84+1.34
CIFAR-100200+4.89+0.92+1.75+1.15
Tiny-ImageNet100+2.78+0.76+1.03+0.86
Tiny-ImageNet200+2.11+1.18+1.87+1.34
Tiny-ImageNet400+3.05+0.64+0.87+0.92

The gains in final CAA, NMI, and ARI show that capacity matching remains effective when construction K differs from the semantic class count, complementing the teacher-quality results across training stages.

Recovery from basin errors. PACI recovers from the tested basin corruption after regular teacher refresh resumes. We started from the epoch-400 matched model and changed basin memberships at epoch 401 while preserving the capacity histogram. The perturbation affected 98.90%/98.34% of samples on CIFAR-100/Tiny-ImageNet. This teacher remained active through epoch 449. Regular teacher refresh resumed at epoch 450.

Table 6. Recovery after basin corruption. Changes are relative to the unperturbed reference (pp). Final ΔCAA is averaged over 10 clustering initializations.

DatasetΔcontamination, epoch 401Δcontamination, epoch 500Δcontamination, epoch 800Final ΔCAA
CIFAR-100+16.84−0.148−1.029+1.993
Tiny-ImageNet+12.45−0.212−1.324+1.601

The teacher trajectory shows recovery after normal refresh resumes, accompanied by improved final clustering performance relative to the unperturbed reference.

AuthorsOpenReview ↗

Response to Reviewer iKf9 (3/3)

Reply to Q3. Semantic supervision and the filtering result

Filtering removes wrong-semantic relations and also discards correct-semantic relation mass. We compared it with label-assisted semantic repair, which changes which samples receive the relation weights while preserving each row's weight multiset, entropy, and L2 norm. Labels guide these diagnostic interventions.

Table 7. Filtering and repair. ΔC and ΔCAA are contamination and CAA changes (pp).

DatasetFilter ΔCRetention (%)Filter ΔCAARepair ΔCRepair ΔCAA
CIFAR-10−1.7677.24+0.14−1.54+1.02
CIFAR-20−1.3884.15+0.09−1.07+0.75

Repair gives larger accuracy gains with smaller contamination reductions. Random filtering lowers CAA by 0.82/0.48 points on CIFAR-10/20. These results explain the small gains from stability filtering through its loss of useful supervision and support preserving correct connections when removing incorrect relations.

Damage and repair on larger datasets. We applied two levels of semantic damage and a repair condition on CIFAR-100 and Tiny-ImageNet, preserving the same per-row weight statistics.

Table 8 gives changes relative to the control.

DatasetModificationΔCΔCAAΔNMIΔARI
CIFAR-100Lower damage+1.97−0.54−1.25−0.65
CIFAR-100Higher damage+2.75−1.01−1.98−1.33
CIFAR-100Repair−1.35+1.05+1.84+1.24
Tiny-ImageNetLower damage+1.42−0.31−0.84−0.34
Tiny-ImageNetHigher damage+2.03−0.58−1.34−0.88
Tiny-ImageNetRepair−0.94+0.51+1.77+1.30

Greater semantic damage produces larger losses in all three clustering metrics on both datasets, and repair improves all three. These bidirectional effects directly connect teacher semantics to final performance while retaining the row-weight statistics.

The assignment-by-normalization experiment identifies assignment capacity as the main source of the capacity-matching benefit. The new interventions act directly on teacher semantics and show their contribution to learning. Together, they support the connection between capacity-dependent assignments, relational supervision, and representation quality.

Reply to Q4. Interpretation of the finite-batch bound

We evaluated Theorem 1 at the training batch size B=256. Here κ measures row concentration and δ measures the change introduced by preprocessing. The overall gap is the absolute difference between full-bank contamination and the Monte Carlo estimate of mean minibatch contamination. The per-anchor gap measures the absolute discrepancy for individual anchors before averaging. Bounds are computed per anchor and then averaged.

Table 9 reports δ, bounds, and gaps in percentage points.

DatasetMean κMean δUpper boundOverall gapPer-anchor gap
CIFAR-107.8140.078414.130.0260.991
CIFAR-2010.2570.113516.600.5191.246
CIFAR-1008.3460.105219.100.5871.524
Tiny-ImageNet14.1870.276120.610.3811.957

The theoretical upper bounds range from 14.13 to 20.61 percentage points across the four datasets. The observed overall discrepancies remain below 0.6 points, and mean per-anchor discrepancies remain below 2.0 points. These results show close empirical agreement between the full-bank relations and the minibatch teacher used during optimization.

Does the capacity effect reach the training teacher? We held the final features, prototypes, and transport cost fixed and compared uniform with matched capacities through raw relation H, normalized relation R, and minibatch teacher T. The uniform-minus-matched contamination gaps were 8.145→8.221→7.992 points on CIFAR-100 and 3.478→3.284→3.688 on Tiny-ImageNet. CIFAR-10/20 also favored matched capacity at each stage. Thus, the capacity-matching advantage persists through preprocessing and minibatch row normalization.

Cluster count, imbalance, and batch size. Cluster count and imbalance enter the bound through the learned relation rows and their κ and δ. More concentrated rows have larger κ and a larger sampling bound. Increasing B reduces the sampling factor (M−m)/(m(M−1)), where m=B−1 and M=N−1, and the sampling term vanishes at the full bank. The theorem makes explicit how batch size, row concentration, and preprocessing jointly control an upper bound on the full-bank–minibatch discrepancy.

Thank you again for your time and helpful comments. We hope these additions address your concerns and would be happy to clarify any remaining questions.

AuthorsOpenReview ↗

Looking forward to your valuable reply

Dear Reviewer iKf9,

As the discussion period draws to a close, we would greatly appreciate your feedback on whether our responses have addressed your concerns. We would be happy to clarify any remaining questions.

Thank you again for your time and helpful comments.

Best regards,

The Authors

Reviewer_RspsOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

In this paper the authors study deep clustering under long-tailed data, where some clusters contain many more examples than others. They argue that having the constraint of equal capacity typically utilized in OT clustering can conflict with the unequal cluster sizes supported by the learned representation. So when the transport step forces examples into components that don’t match the groups their features form, it can treat unrelated examples as similar. The authors propose a method which estimates cluster capacities from the groups formed in the model’s current feature space. “PACI” uses these estimated capacities both to assign samples to components and to construct the relational teacher. It then trains the model to match the teacher across augmented views and a BYOL style objective.

Critical strengths
  • The paper is addressing an important limitation of deep clustering on long-tailed data but I have some questions/concerns regarding potential gaps in the theoretical and experimental setups as we discuss later on.
Critical weaknesses

W1: The results seems to be true by construction as in these capacities are estimated from the sizes of the K-means basins and the analysis then shows that using different capacities must move points outside those clusters.

W2: Lack of experimental rigour: although referred to in the related works, the evaluation does not include comparison to the direct prior methods such as P^2OT and SP^2OT which study imbalance aware OT for deep clusterings. These appear to be quite relevant prior methods.

W3 (writing style): The paper lacks clear transitions betweens its theoretical anlysis of Section 3, proposed methods and the experiments. Although briefly mentioned in Section 3.1, it would be easier if some more intuition was provided to the reader to follow if terms such as "representation-supported basins", "transport component", and "relational-teacher". In particular, the bridge between cross basin displacement to semantic teacher contamination would be helpful to explain why these basins are expected to correspond to meaningful semantic classes.

Questions for authors
  • As discussed in W1, can the authors justify this potential circular reasoning? As in do these basins represent correct semantic classes rather than early represenation errors?
  • As discussed in W2, can the authors explain why P^2OT and SP^2OT are not compared within the experiments?
  • Is PACI's improvement caused by its specific capacity estimator or becuase it allows clusters to have unequal sizes? Possibly a comparsion with non-uniform capacity choices would help narrow down the effect better.
  • How much additional training and memory does PACI require compared to BYOL?
  • Can the authors also provide any results on larger model and dataset combination such as ResNet50/ImageNet since you already looked at TinyImageNet, would be interesting to see if it extends to the more classes?
5 comments
AuthorsOpenReview ↗

Response to Reviewer Rsps (1/3)

Thank you for recognizing the importance of addressing imbalance in deep clustering. Your questions helped us clarify the theory and strengthen its experimental support. We added sample-separated semantic evaluations, direct OT comparisons, and measurements of cost and scalability. We address your comments and questions below.

Reply to W1, W3 & Q1. Geometry, semantics, and the teacher

The displacement result describes a constraint on feasible assignments. Its semantic consequences are tested using class labels on samples outside prototype fitting and capacity estimation.

The connection from geometry to supervision. A representation-supported basin is a region obtained by clustering the current features. A transport component is a destination for assignment mass. Semantic classes provide the labels used to evaluate whether the resulting relations connect appropriate examples.

The teacher connects samples through a sample-to-component transition followed by a component-to-sample transition, H=NΠDq−1Π⊤H=N\Pi D_q^{-1}\Pi^\top. Capacity therefore controls which samples share a component and the strength of their return relation. With fixed 80%/20% basins, 50%/50% capacities force at least 30% of the mass across basins.

The displacement result identifies the mass that must move across geometric basins. When this movement mixes samples from different semantic classes within components, their shared-component relations carry wrong-semantic mass. Our composition analysis quantifies this effect, and the finite-batch analysis connects it to the teacher used during training. PACI estimates capacities from the evolving geometry to address forced reassignment at its source.

A/B/C sample-separated evaluation. We divide samples into three disjoint subsets. A fits prototypes. B uses A's prototypes to estimate basin proportions and capacities. C uses A's prototypes and B's capacities to solve OT and construct the teacher. Labels on C measure contamination. The split excludes C from prototype fitting and capacity estimation. The learned representation and preprocessing are shared and fixed. The three subsets rotate through A/B/C for three evaluations. We compare B-estimated capacities with uniform capacities at batch size 256.

The table reports ΔC = uniform contamination − B-estimated contamination, in percentage points. Means average the three rotations. Positive values favor estimated capacity.

RepresentationDatasetRotation 1Rotation 2Rotation 3Mean ΔC
Final matchedCIFAR-1012.087210.429910.686511.0679
Final matchedCIFAR-204.37422.49978.67665.1835
Final matchedCIFAR-1006.73457.54826.12096.8012
Final matchedTiny-ImageNet4.28612.76103.38133.4761
BYOL warm-upCIFAR-101.50551.79511.42811.5762
BYOL warm-upCIFAR-201.58081.44030.98501.3354
BYOL warm-upCIFAR-1001.47581.02140.73571.0776
BYOL warm-upTiny-ImageNet1.05731.27060.74671.0249

Estimated capacities reduce contamination in all twelve rotations at each representation stage. The semantic benefit extends to samples outside the basin-fitting and counting steps. The shared BYOL warm-up results show that this benefit is already present before PACI's relational learning starts. Together, these tests directly address the concern that the observed semantic gain follows automatically from counting the evaluation samples' own basins.

Semantic development and basin errors. Basin NMI increases from 43.82 to 57.50 on CIFAR-100 and from 28.12 to 40.30 on Tiny-ImageNet during training. Purity increases from 35.54% to 47.96% and from 26.13% to 38.64%, respectively, providing label-based evidence of improving semantic structure.

We also tested recovery after a histogram-preserving basin corruption at epoch 401. Contamination initially increased by 16.84/12.45 points on CIFAR-100/Tiny-ImageNet. Normal teacher refresh resumed at epoch 450, and contamination returned to the reference level by epoch 500, with gaps of −0.148/−0.212 points. Final CAA exceeded the reference by 1.993/1.601 points, averaged over ten clustering initializations. Recovery after refresh resumed was accompanied by improved final clustering performance.

We will incorporate these definitions and explanations into the revision, with clearer transitions across Sections 3–5 to help readers follow the theory, method, and experiments.

AuthorsOpenReview ↗

Response to Reviewer Rsps (2/3)

Reply to W2 & Q2. Direct comparisons with P²OT and SP²OT

Our original benchmark trained ResNet-18 from scratch. P²OT and SP²OT use pretrained backbones in their published evaluations, so we initially focused on from-scratch comparisons. We agree that these methods are directly relevant and have now compared them with PACI under a shared DINO initialization on CIFAR-100 and Tiny-ImageNet. Native clustering outputs are below. Clustering metrics are percentages. The native-output and online-CLS tables report mean ± standard deviation across 3 training seeds.

DatasetMethodCAAACCNMIARI
CIFAR-100DINO47.67±1.3251.90±1.0468.55±0.3140.12±1.15
CIFAR-100P²OT49.85±1.0152.54±1.2569.39±0.6741.93±0.48
CIFAR-100SP²OT51.74±0.7750.21±0.7469.66±0.2442.04±0.77
CIFAR-100PACI54.00±0.7852.13±0.8372.76±0.2942.58±0.85
Tiny-ImageNetDINO19.24±0.7118.93±0.6141.57±0.6716.57±0.43
Tiny-ImageNetP²OT20.01±0.5419.57±0.4243.27±0.7217.02±0.76
Tiny-ImageNetSP²OT21.23±0.8720.73±0.7543.08±0.3418.92±1.20
Tiny-ImageNetPACI23.12±0.4522.87±0.9746.54±0.6717.53±0.81

PACI exceeds the strongest OT baseline by 2.26/1.89 CAA points on CIFAR-100/Tiny-ImageNet and achieves the highest NMI on both datasets.

We also provide a common online-CLS evaluation using the same feature readout and clustering protocol for all methods. Results are CAA (%).

DatasetInitial DINOP²OTSP²OTPACI
CIFAR-10047.67±1.3248.04±1.0949.21±1.0253.45±0.55
Tiny-ImageNet19.24±0.7121.62±0.9221.34±0.4922.57±0.47

Under this common evaluation, PACI exceeds the strongest OT baseline by 4.24/0.95 CAA points and improves over the shared DINO initialization on both datasets. The native outputs and common readout provide complementary evidence for the comparison with imbalance-aware OT methods. We will include these comparisons in the revision.

Reply to Q3. Capacity estimation and nonuniform cluster sizes

The estimator and its association with geometric basins contribute to final performance. Under the paper's BYOL-based setting, we compared capacity choices with the relational objective and training protocol fixed. At each refresh, shuffling permutes its branch's basin capacities while preserving their histogram. MGCE replaces occupancy-based estimation with a multigranularity geometric estimator.

DatasetMatchedUniformShuffledMGCE
CIFAR-10029.6027.3427.8628.12
Tiny-ImageNet18.7217.5417.2017.21

Results are final CAA (%). Matched capacities exceed the strongest alternative by 1.48 points on CIFAR-100 and 1.18 on Tiny-ImageNet. The lower accuracy under shuffling supports the importance of basin–capacity correspondence. The improvement over MGCE supports the occupancy-based estimator within the same learner. Together, these comparisons show the value of estimating capacities from the transport geometry, beyond allowing unequal cluster sizes.

AuthorsOpenReview ↗

Response to Reviewer Rsps (3/3)

Reply to Q4. Training time and GPU memory

PACI's measured step times, including teacher refresh, are close to BYOL. We measured the two methods in separate GPU-exclusive processes on one RTX 4090. Both used ResNet-18, batch size 256, AMP, and the same data pipeline and starting optimizer state. Times are mean ± standard deviation over three timing repetitions. The memory column reports the steady-window peak GPU allocated memory.

DatasetMethodStep (ms)Including refresh (ms/step)Peak allocated (MiB)GPU bank (MiB)
CIFAR-100BYOL78.60±2.1278.60±2.121571.58—
CIFAR-100PACI75.82±0.4476.20±0.451654.9782.59
Tiny-ImageNetBYOL67.90±0.1267.90±0.12820.12—
Tiny-ImageNetPACI67.86±0.4868.84±0.49897.7375.91

The complete teacher refresh includes feature extraction, preprocessing, clustering, OT, and bank construction. A subsequent refresh took 1.436±0.045 s on CIFAR-100. At its 50-epoch refresh interval, this adds 0.378 ms/step, about 0.50% of PACI's normal step time. On Tiny-ImageNet, a complete refresh took 2.060±0.026 s and adds 0.981 ms/step under its refresh schedule.

The steady-window memory increase is 83.39 MiB (5.31%) on CIFAR-100 and 77.61 MiB (9.46%) on Tiny-ImageNet. Training warm-up peaks are 3642.02/3719.52 MiB for BYOL/PACI on CIFAR-100 and 2931.37/3006.58 MiB on Tiny-ImageNet. The retained GPU bank accounts for most of the additional steady-window GPU memory.

Reply to Q5. Larger models, ImageNet-scale clustering, and natural imbalance

ResNet-50 trained on the target data. We extended evaluation to ImageNet-LT with 1,000 classes and iNature500 with 500 naturally imbalanced classes. All methods use ResNet-50 without external pretraining, with their own warm-up or self-supervised learning stages on the target data. Results are CAA (%).

MethodImageNet-LTiNature500
BYOL10.628.1
ConMix12.329.4
MiniClustering (MaxiClustering variant)12.730.7
PACI13.431.2

PACI improves over the strongest comparison by 0.7/0.5 CAA points on ImageNet-LT/iNature500. This extends the evidence to a larger backbone, 1,000-class clustering, and naturally occurring imbalance.

Shared-DINO ViT-B/16 on iNature500. Since the shared DINO initialization was pretrained on ImageNet, we compare P²OT, SP²OT, and PACI on iNature500 under this common initialization. The ImageNet-LT results above evaluate scalability using ResNet-50 trained on the target data without external pretraining. Initial DINO is the feature-clustering reference before additional adaptation. All metrics are percentages.

MethodCAAACCNMIARI
Initial DINO29.336.965.813.0
P²OT32.840.267.113.4
SP²OT34.538.467.813.9
PACI36.739.167.314.2

PACI improves CAA over the strongest OT baseline by 2.2 points and over the common DINO starting point by 7.4 points. Together, these experiments address larger-scale and naturally imbalanced clustering under both target-data learning and a shared pretrained initialization.

Thank you again for your time and helpful comments. We hope these additions address your concerns and would be happy to clarify any remaining questions.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Responses and Manuscript Revisions

Dear Area Chair,

Thank you for your time and for coordinating the review and discussion. We appreciate the recognition our work has received from all three reviewers. Below, we summarize the strengths they highlighted and how our additional experiments and manuscript revisions address their concerns.

The reviewers recognized these strengths:

  • An important problem in long-tailed clustering (Rsps, iKf9).
  • A unified explanation of how capacity constraints affect relational supervision (iKf9).
  • Encouraging benchmark results and informative controlled interventions (iKf9, PuWS).

During the discussion, we added experiments and clarifications addressing the concerns below and incorporated the corresponding updates into the revised manuscript.

Common concerns

  • Direct OT comparisons (iKf9, Rsps). We added comparisons with P²OT and SP²OT under shared DINO initialization, reporting mean ± SD over three training seeds. Using native outputs, PACI exceeds the strongest OT baseline by 2.26/1.89 CAA points on CIFAR-100/Tiny-ImageNet. A common online-CLS evaluation also favors PACI (Section 5.2; Appendix E).

  • Value beyond nonuniform capacities (iKf9, Rsps). Within the same relational learner, matched capacities outperform uniform, histogram-preserving shuffled, and MGCE capacities on both datasets. Shuffling tests basin–capacity correspondence while retaining the capacity histogram; MGCE tests the estimator choice (Section 5.3).

  • Teacher semantics and the filtering result (iKf9, PuWS). We explain why filtering can remove useful supervision together with incorrect relations. Semantic repair preserves each row's weight statistics and gives larger accuracy gains than filtering. On CIFAR-100 and Tiny-ImageNet, stronger semantic damage produces larger performance losses, while repair improves CAA, NMI, and ARI (Section 5.4).

  • Practical meaning of the finite-batch bound (iKf9, PuWS). We report measured concentration and preprocessing terms, analytical bounds, and empirical full-bank–minibatch discrepancies. At batch size 256, overall discrepancies remain below 0.6 points and mean per-anchor discrepancies below 2.0 points across four datasets. The capacity-matching advantage also persists through relation preprocessing and minibatch normalization (Section 5.6; Appendix H).

  • Training and memory costs (Rsps, PuWS). Measurements include feature extraction, clustering, OT, and bank construction. Refresh-amortized step times remain close to BYOL, with steady-window peak GPU memory increases of 5.31%/9.46% on CIFAR-100/Tiny-ImageNet (Section 5.7; Appendix J).

  • Larger models and natural imbalance (Rsps, PuWS). We added ResNet-50 evaluations on ImageNet-LT (1,000 classes) and naturally imbalanced iNature500 (500 classes), without external pretraining. PACI exceeds the strongest comparison by 0.7/0.5 CAA points. With shared-DINO ViT-B/16 on iNature500, PACI exceeds the strongest OT baseline by 2.2 points (Section 5.7; Appendix I).

Additional responses to Reviewer iKf9

  • Capacity reliability. We tracked capacity evolution alongside improving basin NMI and purity. Matched capacities reduce teacher contamination at all four tested warm-up stages, including weak initial representations (Section 5.3; Appendix G).
  • Construction K and basin errors. Teacher quality and final clustering gains persist when construction K is halved or doubled. After substantial basin corruption, teacher contamination recovers following the resumption of normal refreshes, accompanied by improved final CAA relative to the unperturbed reference (Appendix G).

Additional responses to Reviewer Rsps

  • Circularity and semantic evidence. With fixed shared features and preprocessing, disjoint subsets A/B/C fit prototypes, estimate capacities, and evaluate teacher contamination, respectively. Estimated capacities improve teacher quality in every rotation on four datasets, both before PACI's relational learning and at the final representation. Thus, the semantic benefit extends to samples excluded from prototype fitting and capacity estimation (Section 5.3; Appendix F).
  • Terminology and presentation. We clarified geometric basins, transport components, and semantic classes, explained the sample–component–sample teacher, and connected displacement, semantic composition, and minibatch supervision. Sections 3–5 and the redesigned overview figure present this progression explicitly.

Additional response to Reviewer PuWS

  • Assignment versus normalization on larger datasets. The extended four-arm training study shows that assignment capacity has the larger accuracy effect on both CIFAR-100 and Tiny-ImageNet under either normalization choice, extending the original finding to larger class counts (Section 5.5).

We believe these additional results and manuscript revisions address the reviewers' main concerns. Thank you again for your time and consideration.

Best regards,

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.