Abstract
Traditional clustering algorithms often struggle with high-dimensional data residing on nonlinear manifolds. This paper presents MC-MCL, a novel extension of Markov Clustering (MCL) that incorporates the Minimum Curvilinearity (MC) principle. By approximating nonlinear distances through Minimum Spanning Trees (MST) and implementing an automated sparsity enforcement strategy, MC-MCL significantly improves clustering performance on complex biological and image datasets, including MNIST and synthetic manifolds.
Introduction
Clustering is a fundamental task in unsupervised learning, yet many established methods—such as K-means and the original Markov Clustering (MCL) algorithm—operate under the assumption of linear relationships between data points. In domains like systems biology and computer vision, data frequently follows complex, "curved" manifolds. While MCL is renowned for its ability to detect natural clusters via stochastic flow simulation, its traditional reliance on Euclidean or linear similarity measures limits its efficacy in these nonlinear spaces.
The MC-MCL Framework
The proposed MC-MCL algorithm addresses these limitations by integrating two primary innovations: the Minimum Curvilinearity kernel and an automated sparsity enforcement mechanism.
1. Minimum Curvilinearity (MC) Kernel
The MC principle posits that the hierarchical organization of samples in a high-dimensional space can serve as a proxy for the underlying manifold geometry. Instead of calculating straight-line Euclidean distances, which may cut across "empty" regions of the feature space, MC-MCL identifies the shortest path between points along a Minimum Spanning Tree (MST). This process effectively "unfolds" the data manifold, allowing the algorithm to respect the intrinsic shape of the data. The authors explored three distance transformations:
- MC-MCLo (Original): Direct MST-based distance.
- MC-MCLs (Square Root): Attenuates large distances but may over-amplify short ones.
- MC-MCLl (Logarithmic): Regularizes distance estimations to improve stability.
2. Automated Sparsity Enforcement
MCL efficiency depends on a sparse similarity matrix. Traditionally, selecting a sparsity threshold has been a manual and often arbitrary process. MC-MCL introduces a "progressive pruning" strategy that automatically identifies the maximum similarity threshold possible while maintaining the network as a single connected component. This ensures that stochastic flows remain continuous across the entire dataset without requiring user-defined parameters.
Experimental Evaluation
The performance of MC-MCL was benchmarked against four distinct datasets:
- MNIST: 3,000 handwritten digits (784 features) used to test high-dimensional pattern recognition.
- Tripartite-Swiss-Roll: A synthetic 3D spiral manifold designed to evaluate "unrolling" capabilities.
- Radar Signal: 350 ionosphere returns from the Johns Hopkins University Applied Physics Laboratory.
- Gastric Mucosa Microbiome: A real-world biological dataset (187 features) characterized by complex nonlinear patterns related to infections.
Results and Discussion
MC-MCL demonstrated superior performance across all benchmarks. On the MNIST dataset, MC-MCL variants achieved an accuracy exceeding 0.7, representing a massive leap over classical MCL (~0.48) and K-means (~0.57). In the synthetic Swiss-Roll test, the original and logarithmic variants achieved perfect (1.0) accuracy, whereas linear methods failed significantly to recover the three-segment structure.
Notably, in the Radar dataset, MC-MCL identified a three-cluster structure that provided a more nuanced representation of the data than the standard binary "good/bad" labels. This suggests that the nonlinear approach can uncover latent sub-groups that linear methods overlook.
Conclusion and Future Work
MC-MCL represents a significant advancement in graph-based clustering by providing a principled, self-tuning method for navigating nonlinear manifolds. While the square root variant (MC-MCLs) showed limitations on specific synthetic manifolds due to distance distortion, the framework as a whole offers a robust alternative to traditional linear clustering. Future research may explore the integration of curvilinear kernels into deep learning architectures and optimization for large-scale applications where MST construction costs may be a factor.
Summary updated