Leiden Clustering

Unlike Louvain, Leiden guarantees that all communities are internally connected subgraphs. The algorithm introduces a refinement phase that splits clusters before aggregation, ensuring no cell is assigned to a community it is not densely linked to. This eliminates the 'disconnected community' artifact where Louvain could group cells that share no direct edges.

Leiden operates in three distinct phases per iteration:

• Local moving: Cells are greedily assigned to neighboring communities to maximize modularity
• Refinement: Communities are split into well-connected sub-communities using a randomized local merging procedure
• Aggregation: A reduced graph is built where refined partitions become new nodes This structure ensures both speed and quality guarantees that Louvain lacks.

Leiden maximizes the Constant Potts Model (CPM) or Reichardt-Bornholdt quality functions, controlled by a resolution parameter γ. Lower γ values produce fewer, larger clusters; higher γ values yield more granular partitions. This tunable granularity allows bioinformaticians to explore cellular hierarchies from broad lineages to fine subtypes without changing the underlying algorithm.

Empirical benchmarks demonstrate Leiden runs 2-10× faster than Louvain on large single-cell k-nearest neighbor graphs. The refinement phase prevents the 'zigzag' oscillations that slow Louvain's convergence. For datasets exceeding 1 million cells, Leiden's computational efficiency becomes critical, reducing clustering time from hours to minutes on standard high-performance computing nodes.

Leiden is the default clustering algorithm in Scanpy (via sc.tl.leiden()) and is available in Seurat through the FindClusters(algorithm = 4) parameter. Both frameworks wrap the leidenalg Python package or the igraph R implementation, accepting a precomputed shared nearest neighbor graph and returning integer cluster labels directly usable for differential expression and visualization.

The refinement phase introduces stochasticity; different random seeds can produce slightly different partitions. For reproducible research, always set a fixed random_state or seed parameter. The algorithm's output is robust across seeds for well-separated populations, but borderline cells at cluster boundaries may shift assignments. Running with multiple seeds and assessing stability is recommended for publication-quality results.

The direct predecessor to Leiden, the Louvain algorithm is a greedy optimization method for maximizing modularity in large networks. It iteratively moves nodes between communities to increase a quality score. However, Louvain can produce badly connected or even disconnected communities internally, a flaw the Leiden algorithm explicitly guarantees against by adding an intermediate refinement phase. While Louvain remains widely cited, Leiden has largely superseded it in single-cell genomics for its speed and theoretical guarantees.

A quality function that measures the density of edges inside communities compared to edges between communities in a random graph. Both Louvain and Leiden aim to maximize this score. The formula is:

• Q = (1/2m) * Σ[A_ij - (k_i * k_j)/2m] * δ(c_i, c_j)
• A_ij: Edge weight between nodes i and j
• k_i: Sum of edge weights attached to node i
• m: Total edge weight in the graph
• δ: 1 if i and j are in the same community, else 0 Higher modularity indicates a stronger community structure, but the metric has a resolution limit that can obscure small clusters.

The input graph structure on which Leiden operates in single-cell analysis. An SNN graph is constructed from a k-nearest neighbor (k-NN) graph by weighting edges based on the overlap in their local neighborhoods. The Jaccard index is commonly used:

• J(A, B) = |N_A ∩ N_B| / |N_A ∪ N_B| This construction amplifies dense local connectivity and suppresses spurious edges caused by noise in high-dimensional gene expression space, making community boundaries sharper and more robust.

A critical hyperparameter that controls the granularity of detected clusters. It scales the null model in the modularity formula:

• Low resolution (< 1.0): Produces fewer, larger, coarser clusters
• High resolution (> 1.0): Produces more, smaller, finer clusters
• Default (1.0): Standard modularity In single-cell analysis, tuning the resolution parameter is a primary method for matching computational clusters to known biological cell types. Tools like Seurat expose this as a direct parameter in their FindClusters function.

An alternative quality function to modularity that Leiden can optimize. Unlike modularity, the CPM does not suffer from the resolution limit problem, meaning it can detect both very small and very large communities in the same graph without bias. The CPM uses a resolution parameter γ that directly sets a density threshold for internal community edges. This makes it particularly useful for single-cell data where rare cell populations (e.g., <1% of cells) must be distinguished from abundant ones.