Statistical Guarantees for Consensus Clustering

Zhixin Zhou, Gautam Dudeja, Arash A AminiICLR 2023 · OpenReview

Introduction

Consensus clustering—combining multiple different clusterings into one—is notoriously difficult because cluster labels are arbitrary and "switch" between runs. This paper introduces a way to bypass this "label-switching" problem by lifting the task into the space of association matrices. It provides the first rigorous statistical guarantees for consistency and near-optimal performance under a new Random Perturbation Model (RPM).

The Challenge of Unsupervised Label Aggregation

In data science, we often find ourselves with multiple different clusterings of the same dataset. This happens when we run a randomized algorithm (like K-means) with different initializations, or when we sample from the posterior of a Bayesian model using Markov Chain Monte Carlo (MCMC). The goal of consensus clustering is to find a single "barycenter" clustering that represents the best agreement among all these inputs.

The core challenge is unsupervised label aggregation. Unlike classification, where "Label 1" always means "Cat," in clustering, "Cluster 1" in run A might correspond to "Cluster 5" in run B. To find a consensus, traditional methods attempt to solve for the optimal matching (permutation) between every pair of input clusterings—a combinatorial nightmare. This paper asks: Can we find a consensus without explicitly solving for these permutations, and can we prove that the result is statistically "correct"?

Methods: Lifting to Association Matrices

The authors propose a clever workaround: Lifting to Association Matrices. Instead of working with label vectors directly, they represent each clustering as an $n \times n$ binary matrix $X$, where $X_{ij} = 1$ if objects $i$ and $j$ are in the same cluster, and $0$ otherwise. This representation is naturally invariant to label switching.

They introduce three main algorithms:

  1. Basic Aggregation: Average the association matrices of the $N$ input clusterings and then perform K-means on the rows of this average matrix.
  2. Spectral Aggregation: Similar to the basic version, but it uses a truncated eigendecomposition (spectral clustering) on the average matrix before the K-means step to handle noise better.
  3. Local Refinement: A post-processing step that takes an initial consensus and iteratively updates each object's label based on how strongly it "connects" to other objects in a given cluster.

To analyze these, they define the Random Perturbation Model (RPM), where input clusterings are viewed as noisy, permuted versions of a "true" ground-truth clustering with a noise/perturbation probability $p$.

Key Insights and Theoretical Guarantees

  • Permutation-Free Aggregation: By averaging association matrices, the basic algorithm effectively solves a relaxed version of the barycenter problem without ever needing to know which cluster in run A matches which cluster in run B.
  • The Power of Refinement: The basic algorithm achieves a misclassification rate that decays linearly ($1/N$). However, by adding the Local Refinement step, the error rate drops exponentially ($e^{-NI}$), matching the performance of an "oracle" that knows the true permutations.
Chernoff divergence and Bayesian Error Probability
  • Consistency: The authors provide the first proof of statistical consistency for this type of aggregation. They show that as the number of objects ($n$) or the number of input clusterings ($N$) grows, the consensus clustering converges to the truth.
  • Handling Unbalance: One of the most striking insights is that local refinement is particularly crucial for "unbalanced" datasets, where standard spectral methods often struggle to distinguish smaller clusters from noise.

Empirical Results

The paper primarily evaluates its methods using synthetic datasets generated under the RPM, allowing precise control over the number of objects ($n$), input clusterings ($N$), clusters ($K$), and noise probability ($p$).

In numerical experiments, the proposed Basic and Spectral algorithms consistently outperformed existing state-of-the-art methods like KCC (K-means-based consensus clustering) and BOEM (Best One Element Move), especially as the noise level ($p$) increased. The plots of Adjusted Rand Index (ARI) vs. noise show a clear "failure threshold." The proposed methods maintain high accuracy for much higher noise levels than competing algorithms. Furthermore, for unbalanced clusters, the refinement step significantly improved the ARI, often jumping from a mediocre score to near-perfect recovery.

Limitations and Future Work

  • I.I.D. Assumption: The theoretical guarantees assume that the input clusterings are independent and identically distributed. In practice, MCMC samples are correlated, and extending the theory to handle dependent samples is a vital next step.
  • Two-Stage vs. One-Stage: The current best performance requires a two-stage approach (initialization + refinement). The authors speculate whether a single-stage EM-type algorithm could be developed to achieve the same optimal rates more elegantly.
  • Computational Scaling: While more scalable than combinatorial matching, the $n \times n$ association matrix can become memory-intensive for very large $n$. Future work might explore low-rank approximations or "sketching" techniques to handle massive datasets.

Summary updated

Abstract

Consider the problem of clustering $n$ objects. One can apply multiple algorithms to produce $N$ potentially different clustersings of the same objects, that is, partitions of the $n$ objects into $K$ groups. Even a single randomized algorithm can output different clusterings. This often happens when one samples from the posterior of a Bayesian model, or runs multiple MCMC chains from random initializations. A natural task is then to form a consensus among these different clusterings. The challenge in an unsupervised setting is that the optimal matching between clusters of different inputs is unknown. We model this problem as finding a barycenter (also known as Fr\'{e}chet mean) relative to the misclassification rate. We show that by lifting the problem to the space of association matrices, one can derive aggregation algorithms that circumvent the knowledge of the optimal matchings. We analyze the statistical performance of aggregation algorithms under a stochastic label perturbation model, and show that a $K$-means type algorithm followed by a local refinement step can achieve near optimal performance, with a rate that decays exponentially fast in $N$. Numerical experiments show the effectiveness of the proposed methods.
BibTeX
@inproceedings{zhou2023statistical,
  author = {Zhixin Zhou and Gautam Dudeja and Arash A Amini},
  title = {{Statistical Guarantees for Consensus Clustering}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=kQxry8Z6Fd9},
}
Figure