acceptodds
Under review as a conference paper at ICLR 2027

Multiplicity Is Not Diversity: Replication-Invariant Ensemble Clustering

Abstract

Ensemble clustering combines multiple base partitions into a consensus, yet most formulations operate on the ensemble as a multiset. Presenting the same decision repeatedly can change the result even though no new decision information is introduced. We study this multiplicity failure in the decision-only setting and formulate replication invariance. It requires the optimized consensus to remain unaffected by arbitrary copies of an observed partition. The challenge is to achieve replication invariance while retaining contributions from multiple distinct partitions. We propose LINE, a replication invariant ensemble clustering method that addresses this challenge by coupling consensus fidelity with a geometry of decision redundancy. Each partition is represented by a normalized centered co-assignment kernel, while its fidelity to the consensus is measured by normalized conditional code length. We show that the resulting objective admits a quotient representation over decision-equivalence classes, establishing exact replication invariance. We further derive a redundancy-adjusted effective ensemble size and establish stability under near replication, with a perturbation bound independent of replication multiplicity. In addition, LINE has linear time complexity with respect to the number of samples, supporting efficient large-scale ensemble clustering. Experiments on twelve datasets demonstrate strong clustering performance and substantially improved robustness to both exact and near replication. The source code is provided in the supplementary material.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Clustering, Ensemble Clustering, Replication Invariance, Multiplicity

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_Y3zVOpenReview ↗
Rating
4
Confidence
4(+1)
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper investigates replication invariance in decision-only ensemble clustering, requiring that additional copies of an existing partition leave the optimal consensus set unchanged. It introduces LINE, which integrates an entropy-normalized conditional coding loss with an information-rate term and a redundancy penalty constructed from centered co-assignment kernels. By expressing the objective over decision-equivalence classes, the authors prove exact replication invariance. They also characterize the effective ensemble size after accounting for redundancy and derive an objective perturbation bound for near replication. Evaluation on twelve datasets examines clustering quality, computational scalability, the contribution of each component, and robustness to exact and approximate duplicates, with exact-deduplication baselines included.

Critical strengths

(1) Expressing the objective in terms of decision-equivalence classes establishes that duplicating a partition does not alter the reduced objective or its global minimizers. This provides a principled basis for handling repeated evidence in ensemble clustering.

(2) The theoretical treatment also considers partitions that are similar without being identical. The bound on objective perturbation does not depend on the number of replicas, extending the relevance of the analysis beyond exact duplication.

(3) The empirical study covers a reasonable range of settings. Across twelve datasets, the authors examine individual components, conduct dedicated replication experiments, and compare against methods equipped with exact deduplication.

Critical weaknesses

(1) Normalizing by entropy gives the fidelity losses a shared numerical scale, but differences associated with partition granularity remain. A consensus may completely account for a coarser partition while retaining uncertainty about a finer one. The meaning of granularity comparability therefore needs a more precise qualification, together with a discussion of how this asymmetry influences the learned weights.

(2) Although the paper clearly frames replication invariance within a decision-only setting, the practical implications of this choice warrant more discussion. Identical partitions obtained from independent clustering runs may reveal stability in the generating procedure despite adding no new partition structure. The motivation could explain more clearly under what circumstances it is appropriate to disregard this frequency information.

(3) The effect of the rate term on the sizes of the consensus clusters is not fully explained. With hard assignments, IQ(I;Z)I_Q(I;Z) reduces to HQ(Z)H_Q(Z), and reducing the rate therefore favors cluster proportions with lower entropy. LINE uses soft assignments, but the current ablation does not clarify how this preference interacts with the fidelity loss or influences the sizes of the final clusters.

Questions for authors

(1) When base partitions are obtained from independent clustering runs, under what circumstances is it appropriate to disregard how often the same partition occurs?

(2) Were τ\tau and λ\lambda chosen once and retained across all values of LL in the replication experiments? How was the consensus initialization controlled when comparing these runs?

(3) Once the weights of identical partitions are combined, does most of the weight usually fall on a single distinct partition, or do several partitions receive substantial weight? Examples of these aggregated weight distributions would help demonstrate whether the method combines evidence from multiple distinct decisions in practice.

Reviewer_Df5HOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

LINE learns a consensus and partition weights directly from clustering decisions, with contingency-table calculations and decision-pattern compression making the formulation suitable for large datasets. The central theoretical result is that adding exact copies of a partition leaves the reduced objective and its globally optimal consensus set unchanged. Beyond this invariance result, the paper develops a redundancy-adjusted effective ensemble size and bounds the change in the objective under approximate replication. Experiments on datasets ranging from thousands to millions of samples examine clustering quality, robustness to repeated partitions, and computational efficiency.

Critical strengths

(1) Computing kernel alignments from contingency tables avoids the need to construct sample-wise co-assignment matrices. The method also aggregates samples with identical decision patterns while preserving their multiplicities. Together, these choices give the proposed formulation a practical implementation for large datasets.

(2) A useful outcome of the analysis is the effective ensemble size. Because it reflects both decision mass and alignment between partitions, it explains why adding many strongly related partitions need not provide much effective support. This gives the redundancy penalty an interpretation beyond its role in the objective.

(3) The appendix clearly explains how the optimization procedure follows from the objective: the posterior and channel variables have explicit updates, and the weight update is a convex subproblem. It also carefully separates the exact block minimization used in the analysis from the numerical solver and descent safeguard used in practice.

Critical weaknesses

(1) I would find a short optimization outline helpful before the experimental section. The update details are available in the appendix, but including the main alternating steps in the main text would make the transition from the objective to the experiments easier to follow.

(2) Table 4 leaves the fixed-parameter assumptions behind the complexity summary implicit. The relevant dependencies are given in Appendix B.2; a short note beside the table identifying the quantities held fixed would make the scope of the linear-time claim clearer.

(3) The discussion of near replication could state more clearly that the stability guarantee for the optimal consensus set is established under an additional quadratic-growth assumption. This condition appears in Appendix C.2, but mentioning it in the main text would help readers distinguish this result from the objective perturbation bound.

Questions for authors

(1) How were the numbers of clusters in the base k-means runs and the consensus size KK chosen in the experiments?

(2) What stopping tolerance was used, and how many alternating iterations did LINE typically require to converge?

(3) When an ensemble contains many exact duplicates, could LINE be implemented directly over decision-equivalence classes to reduce computation?

Reviewer_DnbtOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper proposes LINE, an ensemble clustering method combining normalized conditional-entropy fidelity, consensus-rate regularization, and a redundancy penalty based on normalized centered co-assignment kernels. It establishes replication invariance of the reduced objective and its globally optimal consensus set, together with perturbation bounds and conditional stability guarantees under near replication.

Critical strengths
  1. The distinction between multiplicity and distinct clustering decisions is clearly formalized, with a principled quotient formulation explaining exact replication invariance.
  2. The evaluation covers competitive recent baselines, component ablations, controlled replication tests, and exact-deduplication comparisons.
  3. LINE achieves competitive performance across the evaluated datasets and metrics.
Critical weaknesses
  1. The practical need for replication invariance remains insufficiently established. Replication invariance is well motivated when a result is arbitrarily copied to amplify its influence. However, repeated results from independent k-means runs may reflect stability. The paper needs to explain why their frequency should be ignored and whether doing so loses useful information. It also needs stronger evidence that existing methods’ use of this frequency creates an important problem in realistic ensemble construction.
  2. The existing ablations do not sufficiently explain the gains on ordinary ensembles. Table 3 supports the usefulness of geometry-aware weighting: replacing the redundancy matrix with the identity generally reduces performance. However, this does not establish whether Table 2’s gains come from correcting harmful natural repetition or from similarity-aware weighting more generally. The paper does not characterize redundancy in the original ensembles or connect it to the observed gains. Controlled replication tests do not answer these questions.
  3. The model-selection protocol requires clarification. The paper reports a parameter grid for LINE and recommended configurations for competing methods, but does not clearly specify how the reported LINE configuration was selected or whether one configuration was used across all metrics. The selection procedure and tuning budgets should be stated explicitly.
Questions for authors
  1. When should the frequency of naturally repeated partitions be ignored, and what useful information might be lost?
  2. Can the authors characterize redundancy in the original ensembles and examine whether the gains are associated with downweighting inaccurate, highly similar partitions?
  3. How were the reported hyperparameters selected, and was the same configuration used across all metrics?
1 comment

Dear Dnbt

Thank you again for your time and effort in reviewing our paper. As the discussion period is coming to an end, we would appreciate your feedback on whether our responses have addressed your concerns. If any questions remain, we would be happy to clarify them before the deadline.

Comments on the paper

1 comment

Dear Reviewers,

Thanks for your time and effort in reviewing this paper. The authors have responded to the comments by providing a rebuttal. Please read the rebuttal and indicate whether your concerns have been resolved. Thanks.

Regards from the AC.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.