Single-Cell Clustering

A human body holds roughly 37 trillion cells, yet for most of scientific history biologists could only study them in bulk. Grind up a tissue sample, extract its RNA, and you get an average — a blurry photo of millions of overlapping voices.

Single-cell RNA sequencing (scRNA-seq) changed that. Pioneered at scale by Macosko et al. in 2015, it captures the gene-expression profile of each cell individually — how loudly it is "speaking" each of its roughly 20,000 genes at the moment of capture. The result is a table with one row per cell and one column per gene, often tens of thousands of cells wide and tall.

The catch: nobody labels these cells in advance. You have raw numbers, no cell-type annotations. The question becomes purely algorithmic: can a computer look at those numbers and find structure? It turns out the answer is yes — and the key tool is a graph-based clustering algorithm. Related ideas appear in dimensionality reduction and graph coloring, both of which share the same high-dimensional geometry at their core.

Below is a simplified view of the pipeline. The demo generates synthetic cells with gene-expression profiles that secretly belong to a few types. The algorithm builds a k-nearest-neighbor (kNN) graph connecting each cell to its most similar peers, then runs Leiden community detection to partition the graph into clusters.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label>{{lbl_k}} <input type="range" id="kSlider" min="2" max="10" value="6"> <span id="kVal">6</span></label>
  <label>{{lbl_cells}} <input type="range" id="nSlider" min="30" max="120" value="60"> <span id="nVal">60</span></label>
  <button id="recluster" type="button">{{btn_recluster}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<canvas id="cv" width="480" height="320"></canvas>
<div id="status" class="status">{{status_init}}</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; background: #f5f7fa; padding: .6rem; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin-bottom: .5rem; }
label { font-size: .85rem; display: flex; gap: .3rem; align-items: center; }
input[type=range] { width: 80px; }
button { font: 600 13px system-ui; padding: .35rem .75rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 6px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; background: #fff; display: block; max-width: 100%; }
.status { margin-top: .4rem; font-size: .88rem; font-weight: 600; min-height: 1.2em; color: #444; }
.status.ok { color: #0a7d33; }

// Code not found

Each color is a cluster the algorithm found without ever seeing the true labels. Notice how tightening the neighborhood (fewer neighbors $k$) breaks big clusters apart, while loosening it merges them. The algorithm never minimizes a single global cost — it optimizes modularity, a score that rewards dense within-cluster edges and penalizes sparse between-cluster ones.

Clustering sounds simple: group similar things together. But optimal graph clustering is a different story.

• Modularity maximization is NP-hard. The modularity score $Q$ rewards dense intra-cluster edges and penalizes inter-cluster ones: $$Q = \frac{1}{2m}\sum_{ij}\!\left[A_{ij} - \frac{k_i k_j}{2m}\right]\delta(c_i, c_j)$$ where $m$ is the number of edges, $k_i$ is the degree of node $i$, and $\delta(c_i,c_j)$ equals 1 if nodes $i$ and $j$ share a cluster. Branchinowski & Meylan (2007) proved finding the exact maximum is NP-hard — the search space is the Bell number $B_n$, which grows faster than any exponential.
• Louvain (2008) made it tractable. The Louvain algorithm greedily moves nodes between communities to improve $Q$, runs in roughly $O(n \log n)$ time, and scales to millions of cells. It became the default in single-cell pipelines.
• Leiden (2019) fixed Louvain's flaw. Traag, Waltman and van Eck showed that Louvain can produce disconnected communities — nodes that share a label but have no path between them inside the cluster. Leiden adds a refinement phase that splits and merges sub-communities to guarantee connectivity while keeping the same near-linear runtime.
• Resolution parameter $\gamma$. Both algorithms have a tunable resolution that shifts the trade-off between many small clusters and few large ones. Choosing $\gamma$ is a form of non-convex optimization: the modularity landscape has many local maxima and no efficient way to find the global one.

Single-cell clustering is not an academic curiosity — it is reshaping medicine and biology:

• Cell-type atlases: The Human Cell Atlas project is using scRNA-seq and Leiden clustering to produce a reference map of every cell type in the human body. As of 2024 it has profiled over 100 million cells across dozens of tissues.
• Cancer biology: tumors are mixtures of cell states. Clustering single-cell data from a tumor reveals rare subclones that resist treatment — the cells most important to target but least visible in bulk sequencing.
• Drug discovery: identifying which cell type a gene is expressed in narrows the search for drug targets and predicts off-target effects. The same graph pipeline drives large-scale screens in pharmaceutical labs.
• Neuroscience: the Allen Brain Cell Atlas, released in 2023, catalogued over 3,000 distinct cell types across the entire mouse brain using single-cell clustering — a number that surprised the field.
• Developmental biology: following cells through differentiation is only possible cell by cell. Clustering across time points reveals the branching paths cells take as an embryo develops.

The algorithm at the center of all of this is the same Leiden community detection that finds communities in social networks and web graphs — a beautiful case of a general algorithm finding an unexpected home in molecular biology.

Single-cell clustering is one of biology's great algorithmic success stories. A problem that looks impossibly hard in the abstract — partition tens of thousands of high-dimensional points into meaningful groups, with no ground truth — turns out to be tractable in practice because biological cell types form genuine clusters in gene-expression space.

The Leiden algorithm exploits that structure: it cannot guarantee the optimal partition (that remains NP-hard), but it finds excellent ones fast enough to run on a laptop. The result is a map of cell types drawn entirely from numbers, with no human labeling required.

Whenever you hear that scientists "discovered a new cell type" or that a tumor has a "rare drug-resistant subpopulation," there is almost certainly a graph algorithm quietly drawing the boundaries behind the headline.