Multiplicity Is Not Diversity: Replication-Invariant Ensemble Clustering

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.