Abstract
MOTIVATION: Single-cell RNA sequencing (scRNA-seq) data analysis is often performed using network projections that produce co-expression networks. These network-based algorithms are attractive because regulatory interactions are fundamentally network-based and there are many tools available for downstream analysis. However, most network-based approaches have two major limitations. First, they are typically unipartite and therefore fail to capture higher-order information. Second, scRNA-seq data are often sparse, so most algorithms for constructing unipartite network projections are inefficient and may overestimate co-expression relationships, or may under-utilize the sparsity when clustering (e.g. with cosine distance). To address these limitations, we propose representing scRNA-seq expression data as hypergraphs, which are generalized graphs where a hyperedge can connect more than two nodes. In this context, hypergraph nodes represent cells, and hyperedges represent genes. Each hyperedge connects all cells in which its corresponding gene is actively expressed, indicating the expression of that gene across different cells. The resulting hypergraph can capture higher-order information and appropriately handle varying levels of data sparsity. This representation enables clustering algorithms to leverage higher-order relationships for improved cell-type differentiation. RESULTS: To distinguish cell types using hypergraph representations of scRNA-seq data, we introduce two novel clustering algorithms: (i) Dual-Importance Preference Hypergraph Walk (DIPHW) and (ii) Co-expression and Memory-Integrated Dual-Importance Preference Hypergraph Walk (CoMem-DIPHW). DIPHW is a new hypergraph-based random walk algorithm that computes cell embeddings by considering the relative importance of genes to cells and cells to genes, incorporating a preference exponent to facilitate clustering. CoMem-DIPHW integrates two unipartite projections, the gene co-expression and cell co-expression networks, along with the cell-gene expression hypergraph derived from single-cell abundance count data into the random walk model. The advantage of CoMem-DIPHW is that it accounts for both local information from single-cell gene expression and global information from pairwise similarity in the two co-expression networks. We benchmark the performance of our algorithms against established and state-of-the-art deep learning approaches using both real-world and simulated scRNA-seq data. Real-world datasets include cells from the human pancreas, mouse pancreas, human brain, and mouse brain tissues. We also use a ground-truth labeled cell-type annotation dataset based on human lung adenocarcinoma cell lines. Quantitative evaluation shows that CoMem-DIPHW consistently outperforms established algorithms and state-of-the-art deep learning algorithms for cell-type clustering. Our proposed algorithms show the greatest improvement on scRNA-seq data with weak modularity. Moreover, CoMem-DIPHW successfully annotates clusters with biologically relevant cell types. Our results highlight the utility of hypergraph representations in the analysis of scRNA-seq data. AVAILABILITY AND IMPLEMENTATION: Our methods are implemented in Python and available on GitHub (https://github.com/wanhe13/CoMem-DIPHW) and archived at Zenodo (https://doi.org/10.5281/zenodo.18927437).