Spectrum: Fast density-aware spectral clustering for single and multi-omic data

Christopher R. John, David Watson, Michael R. Barnes, Costantino Pitzalis, Myles LewisbioRxiv 2019 · DOI

Abstract

Clustering of single or multi-omic data is key to developing personalised medicine and identifying new cell types. We present Spectrum, a fast spectral clustering method for single and multi-omic expression data. Spectrum is flexible and performs well on single-cell RNA-seq data. The method uses a new density-aware kernel that adapts to data scale and density. It uses a tensor product graph data integration and diffusion technique to reveal underlying structures and reduce noise. We developed a powerful method of eigenvector analysis to determine the number of clusters. Benchmarking Spectrum on 21 datasets demonstrated improvements in runtime and performance relative to other state-of-the-art methods.

Introduction

In the era of precision medicine, the ability to group patients or cells into meaningful categories—such as therapy responders or novel cell types—is paramount. This task relies heavily on the analysis of massive molecular datasets (omics). However, researchers face three significant hurdles: the integration of disparate data types (e.g., mRNA, miRNA, and protein levels), the geometric complexity of biological data which rarely forms simple Gaussian distributions, and the computational scalability required for massive single-cell RNA sequencing (scRNA-seq) datasets. Traditional spectral clustering, while mathematically robust, often suffers from $O(N^3)$ complexity and struggles with varying local densities.

Spectrum is introduced as a high-performance spectral clustering framework designed to unify single-omic and multi-omic data analysis. By combining a novel density-aware kernel with a "multimodality gap" heuristic for cluster estimation, Spectrum aims to provide superior biological accuracy and computational efficiency.

Methodology

Adaptive Density-Aware Kernel

Standard clustering methods typically employ kernels that measure similarity based solely on Euclidean distance. Spectrum introduces a density-aware kernel that strengthens connections between points in high-density regions of the data space. This allows the algorithm to adapt to the local scale and density of each unique dataset, making it more robust to outliers and varying cluster shapes.

Tensor Product Graph (TPG) Diffusion

For multi-omic integration, Spectrum utilizes Tensor Product Graphs to capture higher-order relationships across different data modalities. By applying graph diffusion, the method "smooths" the data, effectively amplifying the underlying biological signal while canceling out platform-specific random noise.

The Multimodality Gap

Determining the optimal number of clusters ($K$) remains a fundamental challenge in unsupervised learning. Spectrum addresses this via a novel heuristic: the multimodality gap. Rather than analyzing eigenvalues (the standard "eigengap" approach), Spectrum examines the distribution of eigenvectors using the Hartigan’s dip test for multimodality. The method identifies the point where eigenvectors transition from carrying structural information to representing random noise, providing a data-driven estimate for $K$.

Fast Approximate Spectral Clustering (FASP)

To handle the scale of modern scRNA-seq data, Spectrum incorporates FASP. This technique uses a compression strategy that clusters representative centroids rather than every individual data point. This drastically reduces the computational burden without a significant loss in clustering resolution.

Experimental Results

The authors benchmarked Spectrum against 21 datasets, including 7 TCGA multi-omic cancer datasets (mRNA, miRNA, and protein), 7 scRNA-seq datasets (e.g., Baron, Muraro, Pollen), and various simulated non-Gaussian shapes (spirals, worms, and complex manifolds).

Clinical and Biological Accuracy

On TCGA datasets, Spectrum identified patient clusters with significantly different survival outcomes, outperforming established integration methods like Similarity Network Fusion (SNF) and iClusterPlus. In the single-cell domain, Spectrum achieved the highest summed Normalized Mutual Information (NMI) score of 5.89 across seven datasets, surpassing Seurat (5.74) and SC3 (5.49).

Computational Efficiency

Spectrum demonstrated massive speedups, particularly through its FASP implementation. In a benchmark using the Baron dataset ($N=8569$), Spectrum reduced the required runtime from 1.95 hours to just 14 seconds. Even on smaller datasets, Spectrum often outperformed competitors by orders of magnitude, such as completing a task in 1.13 seconds compared to 123 seconds for M3C.

Discussion and Limitations

Spectrum proves that a well-designed spectral approach can bridge the gap between bulk cancer data and single-cell analysis. While highly versatile, the authors note that Spectrum may still be slightly slower than specific "community detection" methods used in Seurat when FASP is not utilized. Furthermore, the multimodality gap heuristic may occasionally require kernel tuning (specifically the nearest neighbor parameter $P$) when faced with highly irregular, non-Gaussian structures.

Despite these considerations, the multimodality gap represents a novel solution to a long-standing problem in spectral clustering, with potential applications extending beyond genomics into broader data science fields.

Summary updated

Abstract

Abstract Clustering of single or multi-omic data is key to developing personalised medicine and identifying new cell types. We present Spectrum, a fast spectral clustering method for single and multi-omic expression data. Spectrum is flexible and performs well on single-cell RNA-seq data. The method uses a new density-aware kernel that adapts to data scale and density. It uses a tensor product graph data integration and diffusion technique to reveal underlying structures and reduce noise. We developed a powerful method of eigenvector analysis to determine the number of clusters. Benchmarking Spectrum on 21 datasets demonstrated improvements in runtime and performance relative to other state-of-the-art methods. Contact: [email protected]
BibTeX
@misc{john2019spectrum,
  author = {Christopher R. John and David Watson and Michael R. Barnes and Costantino Pitzalis and Myles Lewis},
  title = {{Spectrum: Fast density-aware spectral clustering for single and multi-omic data}},
  year = {2019},
  doi = {10.1101/636639},
  howpublished = {bioRxiv},
}
Figure