TL;DR
This paper introduces Secuer, a novel spectral clustering algorithm designed to efficiently and accurately cluster ultra-large single-cell RNA sequencing (scRNA-seq) datasets. Secuer significantly reduces computational time and memory usage, making it suitable for datasets with millions of cells, and also forms the basis for Secuer-consensus, a faster and more scalable consensus clustering method.
What Problem Does This Paper Address?
Single-cell RNA sequencing (scRNA-seq) has revolutionized biological research by allowing us to study cellular heterogeneity at an unprecedented resolution. A crucial step in analyzing scRNA-seq data is identifying distinct cell populations through clustering. However, the rapid growth in the size of scRNA-seq datasets, now frequently exceeding one million cells, has rendered many existing clustering algorithms computationally infeasible due to their high runtime and memory demands. This bottleneck hinders the analysis of large-scale atlases and the discovery of rare cell types. The paper aims to address this by developing a clustering method that is both highly scalable and accurate for these massive datasets.
Methods
Secuer is a spectral clustering algorithm that introduces several key innovations to achieve scalability:
- Anchor-based Bipartite Graph: Instead of constructing a dense similarity matrix between all cells (which is computationally prohibitive for large datasets), Secuer uses a subset of "anchors" (representative cells identified via k-means on a subsample). It then builds a bipartite graph between cells and these anchors. This significantly reduces the complexity of graph construction.
- Locally-Scaled Gaussian Kernel: To quantify the similarity between cells and anchors, Secuer employs a locally-scaled Gaussian kernel. This approach is designed to better capture the local geometry of the gene expression landscape compared to traditional kernels.
- Efficient Eigen-decomposition: For solving the eigen-problem, Secuer utilizes an efficient "transfer-cuts" (T-cut) algorithm on the bipartite graph, further reducing computational cost.
- Automatic Cluster Number Estimation: Secuer offers two methods to automatically infer the number of clusters (K), removing the need for manual parameter tuning.
Secuer-consensus is built upon Secuer. It runs Secuer multiple times with varied parameters (distance metrics, number of clusters) to generate diverse clustering outputs. These outputs are then aggregated by constructing an unweighted bipartite graph between cells and the generated clusters, followed by k-means clustering to obtain a stable and accurate consensus result.
Datasets
The authors evaluated Secuer and Secuer-consensus on a comprehensive set of datasets:
- Simulated Datasets: Generated to mimic realistic data, ranging from 10,000 to 40 million cells.
- Real Datasets:
- Small/Moderate Benchmark Datasets: 12 gold-standard and silver-standard scRNA-seq datasets (ranging from 49 to 110,832 cells) with high-confidence cell type labels.
- Large/Ultra-large Datasets: Three datasets with over 1 million cells each, including the COVID-19 dataset (1.46 million immune cells), MCA dataset (325,486 cells), and Mouse Brain dataset (over 1 million cells).
Key Insights and Ideas
- The bottleneck is scale, not just accuracy: While many clustering methods exist, their computational demands become prohibitive for the increasingly large datasets being generated. Secuer directly tackles this scalability issue.
- Anchors as a smart shortcut: Using a smaller set of "anchors" to represent the data's structure is a clever way to avoid the O(N^2) complexity of pairwise cell similarity calculations.
- Spectral clustering can be made fast: Traditional spectral clustering is powerful but slow. Secuer demonstrates that with algorithmic modifications (bipartite graphs, efficient eigen-solvers), it can become a viable option for massive datasets.
- Consensus clustering benefits from efficiency: Secuer's speed allows for the generation of many diverse clustering results, which can then be combined by Secuer-consensus to achieve improved stability and accuracy, outperforming existing consensus methods.
- Overestimation of clusters is a problem for existing methods: Louvain and Leiden were shown to erroneously identify millions of clusters in large datasets, a problem Secuer avoids.
Key Results
- Speed: Secuer is significantly faster than existing methods. For ultra-large datasets (>10 million cells), it's 12 times faster than Louvain/Leiden and 5 times faster than k-means. For a 10 million cell dataset, Secuer completes in under 2 minutes, while Louvain/Leiden struggle to process it. Secuer-consensus is over 100 times faster than SC3.
- Accuracy: Secuer achieves comparable or better accuracy (measured by ARI and NMI) than Louvain, Leiden, and k-means on both simulated and real benchmark datasets, including small and large ones.
- Memory Usage: Secuer uses significantly less memory, requiring only one-tenth of the memory of Louvain/Leiden for datasets over 1 million cells.
- Cluster Number Estimation: Secuer reliably estimates the number of clusters, even for very large datasets, where Louvain and Leiden fail.
- Secuer-consensus Performance: Secuer-consensus shows similar or superior accuracy to Secuer and SC3, while being dramatically faster and capable of processing datasets where SC3 fails.
Limitations and Future Work
- Parameter Sensitivity: While Secuer offers automatic cluster number estimation, the paper notes that parameters like the number of anchors (p) and nearest neighbors (k) in MAKNN can affect results, though default values are provided and benchmarked.
- Generalizability: The authors suggest that Secuer's framework could be adapted to other clustering algorithms and applied to different types of omics data (e.g., scATAC-seq, CyTOF, spatial data), indicating future research directions.
- Preprocessing Impact: The paper briefly touches on the impact of preprocessing steps (normalization, HVG selection) on clustering accuracy, suggesting that further investigation into optimal preprocessing pipelines for Secuer could be beneficial.
Summary updated