Reliable data clustering with Bayesian community detection

Magnus Neuman; Jelena Smiljanić; Martin Rosvall

stat.MLOct 16, 2025

Reliable data clustering with Bayesian community detection

Authors: Magnus Neuman, Jelena Smiljanić, Martin Rosvall

Organizations: Integrated Science Lab, Department of Physics, Ume˚a University, Ume˚a, Sweden · Also at Scientific Computing Laboratory, Center for the Study of Complex Systems, Institute of Physics Belgrade, University of Belgrade

Abstract

From neuroscience and genomics to systems biology and ecology, researchers rely on clustering similarity data to uncover modular structure. Most methods work in two steps: first reduce noise, then cluster. The first step runs without regard to the second: it forces arbitrary choices, discards useful information, and can impose structure where none exists. Here we bring the two steps together. Using established Bayesian community detection methods, we let one minimum description length criterion choose both how much to sparsify the data and how to cluster it. This one-step approach keeps all the samples for inference, removes the arbitrary threshold choice, and returns a single cluster when there is no real structure. On synthetic data, our approach recovers clusters under more noise and with fewer samples than standard methods. On gene co-expression data from the human brain, it finds more coherent and more stable clusters than WGCNA, the standard tool in the field. Uniting sparsification and clustering in a single model-selection step provides a principled, noise-resistant way to uncover modular structure in similarity data across fields.

Figures & tables

Figure 1: Overlapping correlation distributions. In a , the planted structure is visible in the observed correlation matrix $\hat{\Sigma}$ , since the within-cluster correlations on average exceed the between-cluster correlations. This separation depends on the number of samples, nodes, and clusters, and on the population correlation $\rho$ . Colorbar truncated at 0.4; diagonal entries have correlation 1. With few samples in b , the within- and between-cluster distributions $\hat{f}$ and $\hat{f}_{0}$ overlap, and the number of false positives using the threshold $r_{i}$ , where $\hat{f}_{0}$ and $\hat{f}$ intersect, is relatively large, making correct inference difficult. With more samples in c , the situation becomes more favorable. The fractions of within- and between-cluster correlations above $r_{i}$ are $p_{\mathrm{in}}$ (green, true positives) and $p_{\mathrm{out}}$ (orange, false positives) respectively.

Figure 2: The transition to separated correlation distributions. In a , the ratio

p_{\mathrm{out}}/p_{\mathrm{in}}

shows the non-linear transition from overlapping to separated between- and within-cluster distributions as the number of samples

L

increases. More samples are required if the number of clusters

q

increases, particularly if the population correlation is weak. The number of features has a negligible effect, as shown by the barely visible dashed lines where the number of features is doubled. In b , splitting the network into more clusters increases

p_{\mathrm{out}}/p_{\mathrm{in}}

, making correct inference more difficult, particularly with weak population correlation. The number of features matters weakly in this case, where more features actually ease inference.

Figure 3: Bayesian community detection and description length compression. In a , the description length compression peaks to the right of the intersection

r_{i}

of within- and between-cluster correlation distributions. The compression peak lies between the dense ( b ) and sparse ( d ) networks, where the signal of modular structure is maximized ( c ). To avoid overfitting modular structure in sparse networks, Bayesian community detection uses a prior shown as orange, thin links in b – d . This approach regularizes correlation networks without splitting already scarce data. The node border colors in network d show the clusters without the prior.

Figure 4: Method performance measured by the adjusted mutual information (AMI) between planted and inferred partitions. For networks with

N=1000

nodes, correlation strength

\rho=0.2

, and

q=2

clusters, the noise level is low and all methods but the DC-SBM correctly infer the planted partition using few samples ( a ). The DC-SBM assumes conditional link independence given the block structure and does not explicitly model triangle closure, whereas correlation networks tend to exhibit high transitivity. With

q=50

clusters, the Regularized Map Equation and the DC-SBM recover the planted partition with fewer samples than cross-validation and hierarchical clustering ( b ). With

q=100

clusters, the noise level is higher, and hierarchical clustering struggles to infer the correct partition, as does the DC-SBM due to its resolution limit ( c ). Hierarchical clustering and the DC-SBM infer clusters (AMI

>

0) even in high noise ( b and c with few samples), making interpretation difficult. For schematic networks with

L=100

samples, correlation strength

\rho=0.3

, and two 50-node clusters ( d , f ) or ten 5-node clusters ( e , g ), the DC-SBM overfits the large clusters due to high clustering coefficients ( f ) and underfits the small clusters due to its resolution limit ( g ).

Figure 5: Detectability limits in the

L

–

\rho

space. Four methods compared on a network with

N=1000

nodes and varying number of clusters

q

. Detectability defined as the line where the AMI between planted and detected partitions on average exceeds 0.95. The link ratio

p_{\mathrm{out}}/p_{\mathrm{in}}

is shown as contour levels in the background. Cross-validation and hierarchical clustering require relatively strong signals for correct inference, and hierarchical clustering is particularly sensitive to small sample sizes. The DC-SBM faces challenges with large and dense clusters ( a ) and small clusters ( c ), where it tends to overfit and underfit respectively, but performs well in the intermediate case with

q=50

clusters ( b ). The Regularized Map Equation (RegMapEq) pushes the detectability limit furthest into the tested high-noise regions.

Figure 6: Gene clusters from gene co-expression data. Using data from the Allen Human Brain Atlas, we compare gene cluster partitions inferred by WGCNA and the Regularized Map Equation. ( a ) Clusters of the Regularized Map Equation (top) and WGCNA (bottom) in the full data and in subsamples with 20–80% of the samples. Clusters are numbered by size from the left (C1, C2, …), with WGCNA’s clusters in italics ( C1 , C2 , …). Each WGCNA cluster takes the color of the Regularized Map Equation cluster it shares most genes with. Gray marks the background cluster. Darker genes have lower co-association: they stay less often with their cluster partners. Flows show the genes that two clusters share. Almost half of the genes in WGCNA’s clusters (47%) belong to the Regularized Map Equation’s background cluster. With 20% of the samples, the mean co-association is 0.77 for the Regularized Map Equation and 0.67 for WGCNA. ( b ) Top GO term of each enriched cluster, shown for that cluster and for the cluster of the other method where the term is most significant. Marker position gives the enrichment factor, marker shape the method and color the adjusted $p$ -value, and open markers show terms that are not significant. The Regularized Map Equation has the higher enrichment factor for every term, and six of its eleven top terms are not significant in WGCNA.

Graph Clustering

Graph clustering groups network nodes by connectivity, attributes, or shared roles to reveal communities and other mesoscale structure.

See all 76 papers

Oct 9, 2026

Model-free Bayesian Clustering and Multimodal Posterior Summarisation

We develop a model-free, noise-aware Bayesian clustering framework that constructs a martingale posterior over clusterings from a predictive Bayesian perspective. This avoids explicit likelihood-prior model specification, expensive MCMC sampling, and mode-seeking variational approximations, while accommodating irregular cluster shapes and enabling parallel generation of posterior draws. To interpret the posterior over high-dimensional, noise-aware clusterings, we introduce a Wasserstein-type summarization method. Using a novel noise-aware loss, this approach compresses the large collection of posterior draws into a small set of weighted representatives, capturing distinct cluster structures and noise assignments. Further, we marginalise the uncertainty in the density level, avoiding reliance on a specific choice. We establish theoretical properties of the proposed loss and guarantees for the level-marginal posterior approximation. Results demonstrate the framework's effectiveness in capturing clustering and noise uncertainty.

Qing Li, Sara Wade

School of Mathematics University of Edinburgh

Clustering Unsupervised Clustering Bayesian Inference

Ask PDF

May 29, 2026

ERICA: Quantifying Replicability of Cluster Analysis

Despite being ubiquitous in science, clustering lacks a unified framework for quantitatively evaluating the replicability of its results. We present evaluating replicability via iterative clustering assignments (ERICA), a method for determining whether clusters can be identified reproducibly in a dataset. The pipeline computes a statistic that determines whether reproducible cluster structure is present in a dataset. Quantitative visualization methods are also introduced to characterize similarities between clusters and identify observations that may represent outliers or unstable assignments. Experiments on synthetic datasets demonstrate that ERICA successfully identifies reproducible cluster structure. In contrast, application of ERICA to three breast cancer gene-expression datasets reveals instances in which clustering solutions are not reproducible. The study underscores the importance of rigorously evaluating clustering solutions and provides a practical framework for doing so.

Siamak K. Sorooshyari, Manuel A. Rivas, Robert Tibshirani

Department of Statistics Stanford University Stanford, CA 94305, USA · Department of Biomedical Data Science Stanford University Stanford, CA 94305, USA · Department of Statistics and Biomedical Data Science Stanford University Stanford, CA 94305, USA

Clustering ML Reproducibility Scientific Reproducibility

Ask PDF

May 29, 2026

Cluster Analysis with Resampling for Validation and Exploration (CARVE)

Clustering is widely used across the sciences as the foundation for downstream data-driven scientific discoveries. However, clustering results are highly sensitive to the choice of algorithm, preprocessing, and the number of clusters

k

, producing scientific claims that are often not reproducible. The current state of the art for validating clustering solutions consists of clustering validation indices (CVIs) such as Silhouette, Davies-Bouldin, and Calinski-Harabasz, which rely on geometric assumptions that break down on the heavy-tailed, high-dimensional, and nonlinearly structured data encountered in biomedical research. Resampling-based alternatives - grounded in the ideas of clustering stability and generalizability - have been proposed but remain scattered across specialized tools with no unified, accessible software. We fill this gap with CARVE (Cluster Analysis with Resampling for Validation and Exploration), an open-source Python and R package that jointly evaluates multiple clustering algorithms and hyperparameters, returning stability and generalizability diagnostics at the global, cluster, and sample level together with principled selection rules and consensus-based cluster labels. Across six synthetic benchmarks CARVE consistently recovers near-optimal clusterings where classical indices degrade substantially. On experimental genomics and proteomics data sets, CARVE recovers finer biological structure when classical CVIs collapse entirely. CARVE is available with a scikit-learn-compatible Python API and an analogous R interface compatible with Seurat workflows.

Kai R. Wycik, Tiffany M. Tang, Tarek M. Zikry +1

Department of Statistics, Columbia University, New York, NY, USA · Center for Theoretical Neuroscience, Zuckerman Mind Brain Behavior Institute, Columbia University, New York, NY, USA · Department of Applied and Computational Mathematics and Statistics, University of Notre Dame, Notre Dame, IN, USA +2

Clustering Scientific Reproducibility

Ask PDF

Abstract

Graph Clustering

Explore similar work

Model-free Bayesian Clustering and Multimodal Posterior Summarisation

ERICA: Quantifying Replicability of Cluster Analysis

Cluster Analysis with Resampling for Validation and Exploration (CARVE)