# Generalization Performance of Ensemble Clustering: From Theory to Algorithm

arXiv: https://arxiv.org/abs/2506.02053 · HTML: https://mlsanity.com/paper/2506.02053/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 56 references that are in the map.
- First posted on arXiv 1 Jun 2025.

## Builds on (most cited first, 11 of 11)

- [Multi-View Spectral Clustering Tailored Tensor Low-Rank Representation](https://mlsanity.com/paper/2004.14705/) (2020)
- [SimpleMKKM: Simple Multiple Kernel K-means](https://mlsanity.com/paper/2005.04975/) (2020)
- [Locally Weighted Ensemble Clustering](https://mlsanity.com/paper/1605.05011/) (2016)
- [DivClust: Controlling Diversity in Deep Clustering](https://mlsanity.com/paper/2304.01042/) (2023)
- [Enhanced Ensemble Clustering via Fast Propagation of Cluster-wise Similarities](https://mlsanity.com/paper/1810.12544/) (2018)
- [Robust Ensemble Clustering Using Probability Trajectories](https://mlsanity.com/paper/1606.01160/) (2016)
- [Weighted Clustering Ensemble: A Review](https://mlsanity.com/paper/1910.02433/) (2019)
- [Ensemble Clustering via Co-association Matrix Self-enhancement](https://mlsanity.com/paper/2205.05937/) (2022)
- [Understanding the Generalization Performance of Spectral Clustering Algorithms](https://mlsanity.com/paper/2205.00281/) (2022)
- [EGRC-Net: Embedding-induced Graph Refinement Clustering Network](https://mlsanity.com/paper/2211.10627/) (2022)
- [Similarity and Dissimilarity Guided Co-association Matrix Construction for Ensemble Clustering](https://mlsanity.com/paper/2411.00904/) (2024)

## Built on by (most cited first, 1 of 1)

- [Beyond Worst-Case Coreset Bounds for k-Clustering via Determinantal Sampling](https://mlsanity.com/paper/2609.06394/) (2026)

## Abstract (arXiv)

Ensemble clustering has demonstrated great success in practice; however, its theoretical foundations remain underexplored. This paper examines the generalization performance of ensemble clustering, focusing on generalization error, excess risk and consistency. We derive a convergence rate of generalization error bound and excess risk bound both of O(√fraclog nm+frac1√n), with n and m being the numbers of samples and base clusterings. Based on this, we prove that when m and n approach infinity and m is significantly larger than log n, i.e., m,n→ ∞, mgg log n, ensemble clustering is consistent. Furthermore, recognizing that n and m are finite in practice, the generalization error cannot be reduced to zero. Thus, by assigning varying weights to finite clusterings, we minimize the error between the empirical average clusterings and their expectation. From this, we theoretically demonstrate that to achieve better clustering performance, we should minimize the deviation (bias) of base clustering from its expectation and maximize the differences (diversity) among various base clusterings. Additionally, we derive that maximizing diversity is nearly equivalent to a robust (min-max) optimization model. Finally, we instantiate our theory to develop a new ensemble clustering algorithm. Compared with SOTA methods, our approach achieves average improvements of 6.1%, 7.3%, and 6.0% on 10 datasets w.r.t. NMI, ARI, and Purity. The code is available at https://github.com/xuz2019/GPEC.