📊 statistics

Multiple Hypothesis Testing To Estimate The Number Of Communities in Stochastic Block Models

This paper addresses the challenge of determining the number of communities in noisy single-cell RNA sequencing data by proposing a two-fold solution comprising a likelihood-based approach for extracting stochastic block models and a new sequential multiple testing method for consistently estimating community numbers, which demonstrates competitive performance on benchmark and real-world datasets.

Original authors: Chetkar Jha, Mingyao Li, Ian Barnett

Published 2026-02-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Chetkar Jha, Mingyao Li, Ian Barnett

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you walk into a massive, chaotic party where thousands of people are mingling. Your goal is to figure out how many distinct social groups are there. Are there just two groups (like "introverts" and "extroverts")? Or are there ten specific cliques (like "gamers," "artists," "athletes," etc.)?

This is exactly the problem scientists face when analyzing single-cell RNA sequencing (scRNA-seq) data. Think of this data as a giant list of instructions inside every single cell in your body. Just like people at a party, cells have different "personalities" (functions). Some make insulin, some fight infections, some help you see. Scientists want to group these cells into "communities" to understand what they do.

However, this data is incredibly noisy. It's like trying to hear conversations at that loud party while someone is blasting heavy metal music next to you. Some cells are "bad quality" (like people who left early or are just shouting nonsense), and the signals are often weak.

Here is the breakdown of the paper's solution, using simple analogies:

1. The Problem: The "Guessing Game"

Most existing computer programs that try to group these cells are like a detective who needs to know the exact number of suspects before they start solving the case.

The Issue: If you tell the computer, "There are 3 groups," it will force the data into 3 groups, even if there are actually 5. If you guess 10, it might split one group into two fake ones.
The Sensitivity: These programs are very picky. If you change a tiny setting (a "hyperparameter"), the result changes completely. It's like trying to tune a radio; if you turn the knob one millimeter, you go from clear music to static.

2. The Solution: The "Sequential Detective" (SMT)

The authors, Chetkar Jha, Mingyao Li, and Ian Barnett, propose a new method called Sequential Multiple Testing (SMT).

Instead of guessing the number of groups all at once, imagine a detective who starts with a simple assumption and tests it step-by-step:

Step 1: "Okay, let's assume there is only 1 big group. Does the data look like one big chaotic mess?"
- If yes: Great, we are done. There is 1 group.
- If no: The data looks too structured for just one group. Let's try 2.
Step 2: "Okay, let's assume there are 2 groups. Do these two groups look like two distinct, organized circles?"
- If yes: Done.
- If no: The circles are still messy. Let's try 3.

They keep adding groups one by one until the math proves that the groups are now "clean" and distinct. This is the Sequential part.

3. The Secret Weapon: Listening to the "Noise"

How do they know if a group is "clean" or just random noise?

The Analogy: Imagine a room full of people talking.
- The first sound you hear is the loud, obvious signal (the main conversation).
- The second sound is the background chatter (the noise).
In math, they look at the "second loudest sound" (the second eigenvalue) in the data.
- If the group is a real community, the "background noise" will be very low and predictable (like a steady hum).
- If the group is fake (just random people thrown together), the "background noise" will be chaotic and loud.

Their method uses a special statistical rule (called the Tracy-Widom distribution) to decide: "Is this noise normal, or is it too messy to be a real group?"

4. Why This is a Big Deal

The paper highlights two major advantages:

It's Robust to Noise: In scRNA-seq data, the "noise" (bad cells, low-quality genes) is huge. Existing methods often fail when the noise is high. This new method is like a noise-canceling headphone that works even in a hurricane. It focuses on the specific structure of the groups rather than getting confused by the chaos.
No More "Tuning": You don't need to be a computer expert to use this. The authors built a system that automatically searches for the best settings (a "grid search") and picks the winner. It's like a self-driving car that finds the best route without you needing to adjust the GPS manually.

5. The Real-World Test

The authors didn't just do math on paper. They tested their method on:

Benchmark Datasets: Standard "gold standard" data where scientists already know the answer. Their method got it right, often better than the current top tools.
Human Retina Cells: They looked at cells in the human eye (specifically bipolar cells). They successfully found subgroups of these cells, helping us understand how the eye processes visual information.

Summary

Think of this paper as inventing a smart, self-correcting sorting machine for biological cells.

Old way: You have to guess how many boxes you need, and if you guess wrong, the sorting is a mess.
New way (SMT): The machine starts with one box, checks if it fits, and if not, adds another box, checking the "noise level" every time until it finds the perfect number of groups.

This helps biologists understand the "social life" of cells without getting lost in the noise, leading to better insights into how our bodies work and how diseases develop.

1. Problem Statement

The paper addresses two critical challenges in the analysis of single-cell RNA sequencing (scRNA-seq) data:

Noisy Data and Hyperparameter Sensitivity: Existing network-based community detection methods (e.g., Louvain, Leiden) for clustering scRNA-seq data are highly sensitive to hyperparameter choices (e.g., number of nearest neighbors) and struggle with the elevated noise levels inherent in scRNA-seq datasets (e.g., low-quality cells, dropouts).
Estimating the Number of Communities ( $K$ ): Most community detection algorithms require the true number of communities ( $K$ ) to be known a priori. Existing methods for estimating $K$ (e.g., Likelihood Ratio BIC, Cross-Validation, Spectral methods) often fail in sparse, noisy networks or are computationally prohibitive. Specifically, many methods degrade in performance when the out-in ratio (the ratio of edge probability between communities to edge probability within communities) is large, a common scenario in biological networks.

2. Methodology

The authors propose a two-fold solution: a method to extract Stochastic Block Models (SBMs) from scRNA-seq data and a new algorithm to estimate $K$ .

A. Extracting SBMs from scRNA-seq Data

To apply SBM theory to scRNA-seq, the authors propose a model-based approach to construct an adjacency matrix from gene expression data without arbitrary hyperparameter tuning:

Preprocessing: Filter low-quality cells and genes; log-normalize read counts.
Grid Search: Instead of fixing hyperparameters, they perform a grid search over:
- $\eta$ : Quantile thresholds for filtering gene variability.
- $\kappa$ : Quantile threshold for converting the correlation matrix into a binary adjacency matrix ( $A_{\kappa, \eta}$ ).
- $\alpha$ : Significance level for the hypothesis test.
Selection: For each combination, they estimate $K$ using the proposed algorithm and calculate the log-likelihood under the SBM. The network configuration yielding the maximum log-likelihood is selected as the best approximation of the underlying SBM.

B. Sequential Multiple Testing (SMT) Algorithm

The core contribution is the Sequential Multiple Testing (SMT) procedure to estimate $K$ .

Core Insight: An SBM with $K$ blocks is equivalent to $K$ distinct Erdős-Rényi (ER) graphs, provided the network is assortative (within-block edge probability > between-block probability).
Hypothesis Testing Strategy:
- The algorithm starts with an assumption of $K=1$ and sequentially increments $K$ .
- At each step $\hat{K}$ , it tests the null hypothesis $H_0$ : "All $\hat{K}$ selected blocks are Erdős-Rényi graphs."
- If $H_0$ is rejected, it implies the current $\hat{K}$ is insufficient (under-fitted), and the algorithm increments $K$ .
- The process stops when $H_0$ is accepted.
Test Statistic:
- The method utilizes the second largest eigenvalue ( $\lambda_2$ ) of the scaled adjacency matrix of each block.
- According to random matrix theory, for an ER graph, the centered and scaled $\lambda_2$ converges to the Tracy-Widom distribution ( $TW_1$ ).
- The test statistic $T_{n, \hat{K}}$ is the maximum of the standardized $\lambda_2$ values across all $\hat{K}$ blocks.
- Complement Handling: To handle cases where within-block probability $p > 0.5$ , the algorithm tests the block or its complement (where probability is $1-p$ ) to ensure the edge probability remains $< 0.5$ , optimizing statistical power.
Stopping Rule: The algorithm stops when $T_{n, \hat{K}} \leq TW_{1, 1-\alpha/\hat{K}}$ (the critical value from the Tracy-Widom distribution adjusted for multiple testing).

3. Key Contributions

New Estimator (SMT): A sequential multiple testing procedure that estimates the number of communities in both sparse and dense SBMs without requiring prior knowledge of $K$ .
Theoretical Guarantees:
- Consistency: The authors prove that the estimator $\hat{K}$ is consistent (converges to the true $K$ ) under moderate sparsity conditions ( $d \ge O(\log n)$ ) and allows $K$ to grow with $n$ (up to $O(n^{1/4-\tau})$ for dense graphs).
- Asymptotic Power: The method achieves asymptotic power of 1, meaning it rejects under-fitted models with probability 1.
Robustness to Out-In Ratio: Unlike spectral methods (e.g., GoF, BHMC) that rely on the entire network spectrum and fail when the out-in ratio is high, SMT focuses on individual blocks. This makes it significantly more robust for noisy, sparse networks typical of scRNA-seq.
Hyperparameter-Free Framework: By integrating a grid-search based on log-likelihood maximization, the method removes the need for manual fine-tuning of clustering hyperparameters.

4. Results

Numerical Simulations:
- The authors compared SMT against state-of-the-art methods: LRBIC, StGoF, NCV, ECV, BHMC, EigCV, and GoF.
- Performance: SMT, BHMC, and EigCV were the top performers. However, SMT demonstrated superior robustness as the out-in ratio increased. While other methods (like BHMC and EigCV) saw accuracy drop significantly with high out-in ratios (e.g., 0.6), SMT maintained high accuracy.
- Scalability: SMT performed well even with large numbers of communities ( $K=15, 20$ ) and large network sizes ( $N=5000$ ).
Benchmark Data Analysis:
- Applied to six gold-standard scRNA-seq datasets (e.g., Biase, Yan, Kolodziejczyk).
- SMT achieved performance slightly better than or comparable to SC3 (a popular scRNA-seq clustering tool) without requiring manual parameter tuning.
Real Data Application:
- Successfully applied to a human retina bipolar single-cell dataset.
- The method successfully identified biologically relevant subgroups of bipolar cells, demonstrating its utility in extracting latent biological structures from noisy data.

5. Significance

This paper provides a rigorous statistical framework for community detection in high-dimensional, noisy biological data.

Biological Impact: It offers a reliable, automated way to cluster scRNA-seq data, helping researchers identify cell types and states without the "black box" nature of heuristic clustering algorithms.
Statistical Innovation: It bridges the gap between random matrix theory (Tracy-Widom limits) and practical community detection, specifically addressing the "out-in ratio" problem that plagues existing spectral methods.
Practical Utility: The proposed grid-search strategy for hyperparameter selection sets a new standard for model-based clustering, reducing the subjectivity and computational burden associated with tuning parameters in single-cell analysis.