Nonlinear Markov Clustering by Minimum Curvilinear Sparse Similarity

Claudio Durán, Aldo Acevedo, Sara Ciucci, Alessandro Muscoloni, Carlo V. CannistraciarXiv 2019 · arXiv

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

Abstract

The development of algorithms for unsupervised pattern recognition by nonlinear clustering is a notable problem in data science. Markov clustering (MCL) is a renowned algorithm that simulates stochastic flows on a network of sample similarities to detect the structural organization of clusters in the data, but it has never been generalized to deal with data nonlinearity. Minimum Curvilinearity (MC) is a principle that approximates nonlinear sample distances in the high-dimensional feature space by curvilinear distances, which are computed as transversal paths over their minimum spanning tree, and then stored in a kernel. Here we propose MC-MCL, which is the first nonlinear kernel extension of MCL and exploits Minimum Curvilinearity to enhance the performance of MCL in real and synthetic data with underlying nonlinear patterns. MC-MCL is compared with baseline clustering methods, including DBSCAN, K-means and affinity propagation. We find that Minimum Curvilinearity provides a valuable framework to estimate nonlinear distances also when its kernel is applied in combination with MCL. Indeed, MC-MCL overcomes classical MCL and even baseline clustering algorithms in different nonlinear datasets.
BibTeX
@misc{duran2019nonlinear,
  author = {Claudio Durán and Aldo Acevedo and Sara Ciucci and Alessandro Muscoloni and Carlo V. Cannistraci},
  title = {{Nonlinear Markov Clustering by Minimum Curvilinear Sparse Similarity}},
  year = {2019},
  eprint = {1912.12211},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1912.12211},
}
Figure