Enhancing Ensemble Clustering with Adaptive High-Order Topological Weights
Introduction
Ensemble clustering aims to improve the robustness and accuracy of unsupervised learning by combining multiple "weak" base clusterings into a single consensus result. This "wisdom of the crowd" approach typically relies on a Co-association (CA) matrix, which captures the frequency with which pairs of samples are grouped together across different base partitions. However, traditional ensemble methods often struggle with a fundamental limitation: the "missing connection" problem.
The Challenge of Missing Connections
A critical flaw in standard ensemble clustering arises when base algorithms consistently fail to group samples from the same class. If every base clustering mistakenly separates a pair of related samples, their entry in the CA matrix becomes zero. Most existing consensus functions treat these zeros as hard constraints, permanently preventing the samples from being clustered together.
As shown in the figure above, missing edges are prevalent in real-world datasets like USPS, Coil20, and Binalpha, sometimes accounting for a significant portion of the ground-truth relationships. This sparsity in the CA matrix severely limits the potential accuracy of the final consensus.
The AWEC Framework
To address this, the authors propose AWEC (Adaptive High-Order Topological Weights for Ensemble Clustering). This framework is designed to recover missing information by mining the underlying manifold structure of the data through three key mechanisms:
- High-Order Connectivity: AWEC moves beyond direct (first-order) connections. By examining neighborhood relationships—such as "friends-of-friends"—the model can identify latent similarities that were missed by individual base clusterings.
- Adaptive Weighting: Recognizing that different orders of connectivity contain varying levels of noise, AWEC automatically learns weights to prioritize the most reliable topological information.
- Unified Topology Learning: The framework decomposes the observed CA matrix into a "pure" connection matrix and a noise component. By optimizing this structure using the Alternating Direction Method of Multipliers (ADMM), AWEC produces a denoised, topologically sound consensus graph.
Key Insights and Results
The "bridge effect" of high-order connections allows the algorithm to reconstruct relationships that were previously invisible. Experimental evaluations on 14 diverse datasets demonstrate that AWEC significantly outperforms state-of-the-art methods like ECCMS and LWEA. For instance, on the Vertebral3c dataset, AWEC achieved a 38% improvement in Adjusted Rand Index (ARI) over its closest competitor.
The effectiveness of the denoising process is evident in the resulting consensus matrices, which exhibit a clear block-diagonal structure corresponding to the true clusters, even when the input data is noisy. This structured output confirms that the model successfully captures the underlying manifold of the data.
Conclusion and Future Directions
AWEC provides a powerful solution to the missing connection problem in ensemble clustering. While the current $O(n^3)$ complexity and hyperparameter sensitivity present opportunities for further optimization, the framework's ability to recover latent topological structures marks a significant advancement in unsupervised learning. Future work will focus on improving scalability for large-scale applications and reducing the need for manual parameter tuning.
Summary updated