Solving Soft Clustering Ensemble via $k$-Sparse Discrete Wasserstein Barycenter

Ruizhe Qin, Mengying Li, Hu DingNeurIPS 2021 · OpenReview

Introduction

Clustering is a foundational technique in unsupervised learning, but individual algorithms—or even the same algorithm with different initializations—often yield conflicting results. Clustering ensemble addresses this by aggregating various outputs into a single, more reliable "consensus" clustering, effectively leveraging the "wisdom of the crowd" for data partitioning.

While traditional research has heavily focused on "hard" clustering (where a data point belongs to exactly one group), real-world data is often more ambiguous. This paper tackles the more complex soft clustering ensemble (SCE) problem, where data points have fractional degrees of membership across multiple clusters (e.g., a point might be 70% "Cat" and 30% "Dog"). By bridging the gap between clustering ensembles and optimal transport, the authors demonstrate that finding a consensus for soft clusterings is mathematically equivalent to computing a $k$-sparse discrete Wasserstein barycenter.

The Challenge with Existing Methods

Existing ensemble methods face two significant hurdles when applied to large-scale or soft clustering tasks:

  1. Computational Complexity: Most consensus models rely on heavy optimization techniques, such as spectral clustering or semi-definite programming. These approaches scale poorly as dataset sizes grow.
  2. Theoretical Gaps: While numerous heuristic methods exist to accelerate the process, they frequently lack rigorous mathematical proofs guaranteeing that the resulting consensus accurately reflects the underlying "ground truth."

Geometric Reframing and Methodology

The core contribution of this paper is reframing the SCE problem as a geometric optimization task in high-dimensional space. The authors prove that finding the soft clustering consensus is equivalent to finding a $k$-sparse Discrete Wasserstein Barycenter (DWB).

Key technical components of their approach include:

  • Geometric Prototypes: Each clustering is treated as a set of $k$ vectors in an $n$-dimensional space. The distance between two distinct clusterings is measured using a minimum-weight bipartite matching, calculated via the Hungarian algorithm.
  • Random Sampling: Instead of processing all $m$ input clusterings in the ensemble, the authors introduce a sampling-based algorithm. They prove that a $(1+\epsilon)$ approximation can be achieved by randomly sampling a small subset of clusterings. Crucially, the sample size required depends only on the desired error ($\epsilon$) and confidence ($\delta$), and is entirely independent of the data's dimensionality.
  • Fixed-Parameter Tractability: For scenarios where the number of clusters ($k$) is small and constant, the authors provide an algorithm that remains highly efficient regardless of the number of data points or ensemble members.
  • Alternating Minimization (AM-r): To handle cases where $k$ is large, the sampling concept is integrated into an iterative "alternating minimization" framework. This bypasses the computational bottleneck of calculating Wasserstein distances across the entire ensemble.

Experimental Evaluation and Results

The researchers evaluated their Wasserstein-based approach (AM-r) against representative baselines like BGP (graph-based) and FURTHEST (top-down) using three standard machine learning benchmarks: USPS ($k=10$), IRIS ($k=3$), and CIFAR-10 ($k=10$). Initial diverse clusterings were generated using random projections.

Key Findings

  • Superior Consensus: The proposed AM-r algorithm consistently achieved lower objective values, indicating a better, tighter consensus compared to baseline methods.
  • Speed and Scalability: On the high-dimensional CIFAR-10 dataset (3,072 dimensions), the sampling-based approach was significantly faster than baselines while maintaining or even improving clustering quality.
  • Theoretical Validation: The experiments empirically confirmed the paper's "consensus theorem." As the number of clusterings in the ensemble ($m$) increases, the aggregated result demonstrably converges toward the ground-truth clustering. Furthermore, the authors relaxed previous theoretical assumptions, proving that the DWB will approximate the ground truth even if the underlying ensemble model is imperfect, provided the ensemble is sufficiently large.

Limitations and Future Directions

While the proposed framework offers robust theoretical guarantees and practical speedups, it does have limitations. The fixed-parameter algorithm's complexity grows exponentially relative to $k$ (specifically, $\mathcal{O}(\exp(k \log k))$). While this is perfectly manageable for $k=10$, it becomes computationally prohibitive for datasets requiring hundreds or thousands of clusters.

Future work will need to address the model's robustness against adversarial attacks, such as intentionally "poisoning" the ensemble with malicious clusterings. Additionally, exploring how to incorporate social constraints—such as fairness or privacy preservation—into the Wasserstein barycenter framework remains an open and promising area of research to ensure the consensus does not inherit or amplify biases from individual input models.

Summary updated

Abstract

Clustering ensemble is one of the most important problems in ensemble learning. Though it has been extensively studied in the past decades, the existing methods often suffer from the issues like high computational complexity and the difficulty on understanding the consensus. In this paper, we study the more general soft clustering ensemble problem where each individual solution is a soft clustering. We connect it to the well-known discrete Wasserstein barycenter problem in geometry. Based on some novel geometric insights in high dimensions, we propose the sampling-based algorithms with provable quality guarantees. We also provide the systematical analysis on the consensus of our model. Finally, we conduct the experiments to evaluate our proposed algorithms.
BibTeX
@inproceedings{qin2021solving,
  author = {Ruizhe Qin and Mengying Li and Hu Ding},
  title = {{Solving Soft Clustering Ensemble via $k$-Sparse Discrete Wasserstein Barycenter}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=yAIYc7YjGbd},
}
Figure