Enhanced Markov Clustering Algorithm Improves Graph Partitioning on Tabular Datasets

Researchers Le Li, Fei Wang, and Pasi Fränti have introduced an enhanced Markov clustering algorithm that substantially improves unsupervised data partitioning on complex tabular datasets. Traditional Markov clustering models stochastic flow across graphs through alternating expansion and inflation steps, but adapting it to tabular data has long faced severe hurdles, including unreliable graph transformations, difficult expansion parameter tuning, and uniform global pruning that damages local structures. The newly proposed enhanced Markov clustering framework overcomes these obstacles by combining reverse k-nearest neighbor graph construction, an adaptive min–max expansion mechanism, and column-wise local adaptive pruning via knee-point detection. Across nine synthetic and real-world benchmark datasets, the enhanced framework consistently outperformed existing Markov clustering variants while reducing hyperparameter tuning complexity.

Introduced by Stijn van Dongen in 2000, Markov clustering exploits the tendency of random walks to become trapped within densely connected graph regions. The algorithm constructs a column-stochastic transition matrix from an undirected network and alternates between expansion and inflation. Expansion raises the matrix to an exponential power, conventionally fixed at two, simulating random walk propagation to explore connectivity. Inflation then applies an element-wise power transformation followed by column normalization, amplifying strong transitions while suppressing weak connections. Together, these steps emulate water flow across a landscape to carve distinct drainage basins, reinforcing intra-cluster cohesion and attenuating inter-cluster connections until reaching an idempotent state. While successful in analyzing biological networks and social communities, the algorithm struggles when applied to tabular datasets in fields such as bioinformatics and finance. Traditional distance-based graph construction methods, such as Euclidean k-nearest neighbor graphs, fail to align with the underlying flow dynamics, causing severe clustering degradation.

To establish structural compatibility between tabular features and stochastic flow dynamics, the authors introduced graph construction based on reverse k-nearest neighbors. In conventional k-nearest neighbor graphs, each node links to its closest neighbors based on proximity, creating asymmetric directed edges where selection is not mutual. Crucially, standard neighbor graphs reverse the natural flow semantics of Markov clustering: an edge indicating that a node selects a neighbor contradicts the transition matrix framework, where flow is directed into receiving nodes. Under Proposition 1, the researchers proved that transposing the neighbor adjacency matrix to form a reverse k-nearest neighbor graph establishes strict consistency with Markov clustering inflow. Non-zero entries in the initial transition matrix correspond precisely to nodes that selected the target. Consequently, nodes with high reverse neighbor degrees correspond to natural density attractors, accumulating higher stationary probabilities. Boundary points and noise instances naturally receive fewer incoming connections, producing sparser inter-cluster links and a wider spectral gap between eigenvalues.

The second major innovation in the enhanced framework addresses the difficulty of tuning the expansion power parameter. In standard Markov clustering implementations, fixing the expansion exponent at two frequently leads to under-expansion on sparse or complex graphs. Under-expansion prevents stochastic flow from exploring full intra-cluster connectivity, leaving natural clusters fragmented into numerous small sub-components. Conversely, manually selecting an overly large expansion exponent causes over-expansion, where flow bridges separate clusters, blurring boundaries and merging distinct groups into single undifferentiated clusters. To resolve this dilemma, the authors introduced an adaptive min–max expansion strategy that dynamically identifies the optimal expansion depth. The algorithm computes successive matrix multiplications of the transition matrix by its initial state while tracking the emergence of non-zero entries. Expansion halts automatically at the minimal integer depth where the pattern of non-zero entries stabilizes. By capturing the transitive closure of random walks without unnecessary propagation, this strategy achieves full cluster reachability while preventing artificial cluster merging.

Following expansion, the framework refines the transition matrix using a column-wise local adaptive pruning mechanism designed to replace rigid global thresholds. Existing Markov clustering variants rely on a uniform numerical cut-off across the entire matrix to enforce sparsity. However, uniform global pruning ignores local density variations across the graph, frequently removing informative connections in sparse regions while retaining redundant links in dense regions. In sparse areas, global thresholds sever weak yet essential structural bridges, disconnecting peripheral nodes and causing severe fragmentation. In contrast, the proposed local adaptive pruning strategy evaluates each column of the expanded matrix independently using the Kneedle algorithm. Non-zero transition probabilities within each column are sorted in descending order, and the Kneedle algorithm detects the knee point corresponding to the maximum curvature along the sorted value curve. By retaining only the top entries up to this knee point and resetting remaining entries to zero, the algorithm automatically adapts to local distributions, preserving critical connections while suppressing noise.

The complete execution pipeline unifies these components into an iterative three-stage cycle: transition matrix expansion, column-wise knee-based pruning, and inflation via element-wise squaring followed by column normalization. The iterative procedure continues until two convergence criteria are satisfied simultaneously: the support of the transition matrix remains identical across consecutive iterations, and the L1 matrix norm difference between consecutive states drops below 10^-5. The researchers emphasized that enforcing both conditions is essential for algorithmic reliability. Relying solely on support stabilization can cause premature termination in sparse graphs before intra-cluster reachability is fully established, whereas in noisy networks, persistent weak bridges can permit continuous flow leakage. Reverse neighbor graph initialization and local adaptive pruning resolve these failure modes by suppressing boundary connections and removing residual cross-cluster transitions prior to inflation. Once both convergence conditions are met, final clusters are extracted directly by identifying connected components within the stabilized transition matrix, cleanly mapping data points into discrete partitions without heuristic post-processing.

Theoretical complexity analysis and empirical runtime evaluations confirm that the enhanced framework maintains computational efficiency despite its adaptive mechanisms. Constructing the initial reverse neighbor graph requires pairwise distance computation in O(n^2 d) time and nearest neighbor sorting in O(n^2 log k) time, yielding O(n^2 d) complexity when dimensionality d exceeds log k. During each iteration, adaptive expansion operates with complexity O(e * d_bar * log n), while column-wise Kneedle pruning requires O(e log s_bar) time, simplifying to O(nk log k) on sparse graphs. In empirical trials on the 784-dimensional MNIST dataset scaling to 10,000 instances on an Intel Core i7-12700K processor, the proposed method finished in 56.1 seconds, running faster than standard Markov clustering at 60.1 seconds and BMCL at 72.1 seconds. Reverse neighbor initialization produces sparser inter-cluster connectivity, while adaptive expansion eliminates redundant iterations. Although DPC at 2.3 seconds and Leiden at 3.1 seconds ran faster, their accuracy was limited, while HDBSCAN scaled to 88.94 seconds and G-CEALS required 266.27 seconds.

To quantify the specific contribution of each module, the researchers performed an ablation study across nine benchmark datasets, evaluating performance using the Adjusted Rand Index. The comparative configurations systematically disabled reverse neighbor graph construction, adaptive min–max expansion, and local adaptive pruning. Experimental results demonstrated that the complete implementation achieved the highest or near-highest clustering accuracy across all nine datasets, confirming strong operational synergy. Reverse neighbor graph construction proved to be the most critical module: reverting to conventional k-nearest neighbor graphs caused substantial performance drops, with the Adjusted Rand Index decreasing from 0.99 to 0.84 on Aggregation and from 0.44 to 0.27 on Pathbased. Disabling adaptive min–max expansion similarly caused severe performance degradation, reducing accuracy from 0.97 to 0.73 on Flame and from 0.99 to 0.71 on Aggregation due to cluster fragmentation. Removing local pruning produced accuracy drops of 2 to 6 percentage points on Digits, MNIST, and Wine, while removing both reverse neighbor construction and adaptive expansion yielded scores of just 0.09 on Pathbased and 0.15 on Flame.

In comparative evaluations against diverse clustering paradigms—including density-based HDBSCAN and DPC, model-based NGMM, deep G-CEALS, spectral clustering, and community detection algorithms Louvain and Leiden—enhanced Markov clustering delivered consistently superior or competitive partitioning performance. On synthetic two-dimensional datasets featuring complex non-convex boundaries, the proposed method achieved remarkable precision, recording Normalized Mutual Information of 0.93, an Adjusted Rand Index of 0.97, and Accuracy of 0.99 on Flame, alongside near-perfect scores of 0.99 NMI, 0.99 ARI, and 1.00 ACC on Aggregation. While density-based algorithms excelled exclusively in low-dimensional settings with distinct gaps, their efficacy faltered on high-dimensional feature spaces. On the 784-dimensional MNIST dataset, where spectral clustering variants achieved Adjusted Rand Index scores of 0.33 and 0.34 and NGMM achieved 0.22, enhanced Markov clustering maintained competitive performance with 0.50 NMI, 0.36 ARI, and 0.54 ACC. The deep learning model G-CEALS exhibited notable performance instability, dropping to an ARI of 0.00 on Banknote and 0.23 on Flame due to structural conflicts between reconstruction and clustering objectives. Across all nine benchmark datasets, enhanced Markov clustering achieved an average Adjusted Rand Index of 0.61, substantially outperforming the standard Markov clustering baseline of 0.36.

Despite the clear empirical gains and theoretical consistency demonstrated throughout the study, the authors documented several specific limitations in the current formulation of enhanced Markov clustering that warrant future investigation. First, while empirical evaluations confirmed the practical superiority of reverse nearest neighbor graphs over conventional formulations, the reverse neighbor construction component currently lacks a complete theoretical characterization under arbitrary feature distributions. Second, although the algorithm demonstrated stable runtime scalability up to 10,000 samples on high-dimensional benchmarks, its performance and structural stability have not yet been evaluated on ultra-large-scale graphs exceeding 100,000 nodes. Third, although the framework successfully eliminates manual tuning for expansion exponents and pruning thresholds, the initial neighbor parameter k must still be specified by the user and continues to influence final clustering results.

Subject of Research: Enhanced Markov clustering algorithm for graph-based data partitioning

Article Title: Enhanced Markov clustering with reverse k-nearest neighbors, min–max expansion, and adaptive local pruning

Article References: Li, L., Wang, F., & Fränti, P. (2026). Enhanced Markov clustering with reverse k-nearest neighbors, min–max expansion, and adaptive local pruning. Knowledge and Information Systems, 68(1), Article 306. https://doi.org/10.1007/s10115-026-02925-9

Image Credits: AI Generated

DOI: 10.1007/s10115-026-02925-9

Keywords: Markov clustering, unsupervised learning, graph partitioning, reverse nearest neighbors, data clustering, algorithm design, computational complexity, machine learning, Enhanced, Markov, clustering, reverse