Leiden Community Detection

Why Leiden Adds a Refinement Stage

Community detection partitions the vertices of a graph into groups with relatively strong internal connections. In single-cell analysis, the vertices may represent cells and the weighted edges may represent similarities in a cell-neighborhood graph. The partition is a grouping of graph vertices; it is not, by itself, evidence that the groups are distinct biological cell types.

Louvain community detection repeatedly moves vertices to improve an objective such as modularity, then aggregates the resulting communities into larger graph vertices. This is computationally effective, but its updates can yield communities that are disconnected or connected only through a narrow bottleneck. Leiden retains the local-moving and aggregation ideas while inserting a refinement stage between them. Refinement searches within each community for smaller, better-connected pieces before those pieces are used to construct the next graph.

The calculations below use ordinary modularity. They explain the key mechanics without treating a particular resolution setting or implementation as universal.

Graph and Modularity Assumptions

Definition: Let $G=(V,E)$ be an undirected weighted graph with $n$ vertices. Each edge $(i,j)$ has nonnegative weight $w_{ij}=w_{ji}$, and original vertices have no self-loops. Define the strength of vertex $i$ by $d_i=\sum_j w_{ij}$, and let $m=\sum_{i<j}w_{ij}$ be the total edge weight, with $m>0$. For a partition $P$ of the vertices, ordinary modularity is $$ Q(P)=\sum_{C\in P}\left[\frac{l_C}{m}-\left(\frac{d_C}{2m}\right)^2\right], $$ where $l_C$ is the total weight of edges with both endpoints in community $C$, counted once, and $d_C=\sum_{i\in C}d_i$ is the sum of the vertex strengths in $C$.

The condition $m>0$ is needed because modularity divides by total edge weight. An edgeless graph does not satisfy this definition, so it must be handled separately rather than assigned a modularity by this formula. Aggregation can create self-loops on the new, supervertex graph: a loop records weight internal to an aggregated group and must be counted consistently when computing strengths and modularity.

Modularity compares observed within-community weight with a degree-based reference: the squared-strength term is the expected contribution under the usual configuration-model null. It is a partition score, not a probability that a proposed community is real. Leiden can optimize other quality functions too; the details and guarantees depend on the chosen objective and implementation.

Worked Example: A Modularity Gain From Joining Two Groups

Suppose two candidate groups $A$ and $B$ have total strengths $d_A=3$ and $d_B=4$, with edge weight $e_{AB}=3$ between them. Let the graph’s total edge weight be $m=7$. Compare keeping them separate with merging them, holding all other communities fixed.

When the groups are merged, their internal edge weight gains $e_{AB}$, and their combined strength is $d_A+d_B$. The change in modularity is therefore $$ \Delta Q =\frac{e_{AB}}{m} -\frac{(d_A+d_B)^2-d_A^2-d_B^2}{4m^2} =\frac{e_{AB}}{m}-\frac{d_A d_B}{2m^2}. $$

Substituting the given values, $$ \Delta Q=\frac{3}{7}-\frac{(3)(4)}{2(7^2)} =0.4286-0.1224 =0.3061. $$

This merge increases modularity by about 0.3061. It is an objective comparison for these two groups under the stated graph and partition; it does not establish that the groups should be merged for every purpose.

The Three Stages of Leiden

A Leiden iteration has three linked stages. Implementations vary in details such as the objective, move ordering, and refinement settings, but the central structure is local moving, refinement, and aggregation.

Local moving.
Visit vertices, often in randomized order, and consider moving each vertex to an eligible neighboring community. Make moves that improve the chosen quality objective, repeating as needed until no further eligible improving move is found. This produces a partition to be refined.

Refinement.
Within each community from local moving, seek a finer partition into subsets. Refinement uses constrained, often randomized, moves and connectivity-related criteria so that the resulting pieces are better connected. Each refined group remains inside one community from the local-moving partition.

Aggregation.
Replace each refined group by a supervertex and sum the weights of edges between groups; internal edge weight becomes a supervertex loop. Initialize the aggregate graph’s partition according to the coarser local-moving communities, so refined groups from the same parent can still be joined during subsequent local moving.

The last detail is important. Refinement is not simply a permanent split of every parent community. It supplies smaller units for the next graph, while the next local-moving stage can reconsider joining those units. The algorithm alternates between opportunities to divide a questionable community and opportunities to combine groups when the objective supports it.

Why Refinement Helps

Louvain-style local updates are based on changes in a global score. A sequence of individually favorable moves and later aggregation can leave a community whose induced subgraph—the graph formed by its own vertices and their connecting edges—is disconnected or weakly tied together. Aggregating such a group hides its internal structure behind one supervertex. Leiden’s refinement step examines that structure before aggregation and can keep separate, better-connected pieces available to later optimization.

A simple merge calculation explains why a weak bridge can make a large group unattractive under modularity. If communities $A$ and $B$ have edge weight $e_{AB}$ between them and strengths $d_A,d_B$, merging changes modularity by $$ \Delta Q=\frac{e_{AB}}{m}-\frac{d_A d_B}{2m^2}. $$ The first term rewards their connecting edges; the second penalizes the combined strength. A narrow connection between substantial groups may not compensate for the penalty. Refinement can expose those groups as separate supervertices, allowing the next local-moving stage to act on them rather than treating the whole parent as indivisible.

Worked Example: Refining a Community Joined by a Weak Bridge

Consider two triangles, each with all three edges of weight 1, joined by one bridge of weight 0.1 between a vertex in each triangle. Thus $m=3+3+0.1=6.1$. Compare the single-community partition with a partition that assigns each triangle to its own community. This is a hypothetical graph used to illustrate the objective.

For the single-community partition, all edge weight is internal and the community strength is $2m=12.2$, so $$ Q_{\mathrm{one}}=\frac{6.1}{6.1}-\left(\frac{12.2}{12.2}\right)^2=1-1=0. $$

For the two-triangle partition, each community has internal weight $l_C=3$. Each triangle has strength $6$ from its internal edges plus $0.1$ from the bridge, so $d_C=6.1$. Therefore $$ Q_{\mathrm{two}} =2\left[\frac{3}{6.1}-\left(\frac{6.1}{12.2}\right)^2\right] =2(0.4918-0.2500) =0.4836. $$

The two-community partition has higher modularity in this comparison. Its groups are also connected internally by triangle edges, with only a weak bridge between them. Refinement can preserve the triangles as separate refined groups within a coarser parent; aggregation then retains them as distinct supervertices for another local-moving stage. This example shows why refinement is useful, not that every run must first produce the single-community partition.

Aggregation Preserves the Relevant Edge Accounting

Aggregation is not a new clustering of the original cells; it is a compressed representation for continuing the search. Edge weights between two supervertices equal the sum of weights between their constituent vertices. Weight internal to one supervertex becomes a loop. With this bookkeeping, a partition of supervertices corresponds to a partition of the original vertices, and the modularity contribution for that partition is preserved.

Worked Example: Computing an Aggregate Edge Weight

Suppose $A=\{a,b\}$ and $B=\{c,d\}$ are two refined groups. In a hypothetical original graph, the internal edge $a-b$ has weight 2, the internal edge $c-d$ has weight 2, and the cross edges $b-c$ and $a-d$ have weights 1 and 0.5. There are no other edges. Then $m=5.5$.

After aggregation, $A$ has an internal loop of weight 2, $B$ has an internal loop of weight 2, and the edge between the two supervertices has weight $1+0.5=1.5$. Each supervertex has strength $2(2)+1.5=5.5$, because a loop contributes twice to strength. The modularity of keeping $A$ and $B$ separate is $$ Q=\left[\frac{2}{5.5}-\left(\frac{5.5}{11}\right)^2\right] +\left[\frac{2}{5.5}-\left(\frac{5.5}{11}\right)^2\right] =0.2273. $$

The same values follow on the original graph: each group has internal weight 2 and strength 5.5. The aggregate representation therefore retains the quantities needed to score this partition.

Assumptions, Diagnostics, and Limitations

The modularity calculations here assume a finite undirected graph with nonnegative weights, no self-loops on the original vertices, and $m>0$. They also assume the edge weights and vertex identities represent the graph the analyst intends to cluster. Leiden does not repair a graph built from inappropriate distances, an unsuitable neighborhood size, or a flawed choice of edge weights.

Useful checks focus on both the output and the procedure:

Check connectivity within communities. Find connected components in each community’s induced subgraph. Multiple components are a clear warning that the partition does not form a connected group under the graph’s edges.
Inspect weak internal links. A group connected through a single low-weight bridge may be fragile even if it is technically connected. Examine internal edge weights and whether a small number of vertices carry most of the connection.
Track objective values and sizes. Verify that the reported objective matches the stated graph and objective definition. Very large communities, many singletons, or abrupt changes in group sizes warrant inspection, not automatic acceptance or rejection.
Repeat runs when the algorithm is stochastic. Randomized update order and initialization can lead to different partitions. Compare partitions and objective values across runs; one favorable score alone does not establish stability.

Leiden’s refinement is designed to avoid poorly connected communities and, under the algorithm’s stated conditions, provides stronger connectivity guarantees than Louvain. The exact guarantees depend on the objective and implementation; they should not be generalized to every software option without checking its documentation. Connectivity is also not the same as biological validity: connected groups can still reflect technical effects or arbitrary graph construction choices. Modularity itself has limitations, including its dependence on the null model and its tendency to favor certain community scales. Those issues require separate consideration rather than being solved by the refinement stage.

Compared with Louvain, Leiden adds this refinement step and changes how the next aggregated graph is initialized, helping prevent poorly connected groups from being carried forward as indivisible units. Compared with methods such as label propagation, which updates labels based on neighboring labels, Leiden explicitly uses an objective and a refinement-and-aggregation cycle. These approaches have different update rules; no single method is universally best for every graph.

Common Mistake

Common mistake: “Leiden is just Louvain with a different name, so a higher modularity score proves its communities are biologically correct.”

Correction: Leiden adds refinement and uses refined groups in aggregation, which addresses important connectivity weaknesses of Louvain-style updates. A modularity score measures fit to a specified graph objective, not biological truth. Check graph construction, connectivity, robustness across runs, and biological interpretation separately.

Check Your Understanding

Answer the questions, then compare your reasoning with the brief solutions.

Why does the modularity definition require $m>0$?
A pair of groups has $d_A=2$, $d_B=3$, $e_{AB}=0.2$, and $m=5$. Calculate the modularity change from merging them.
What is the role of refinement if the next local-moving stage can join refined groups again?
When two groups are aggregated, what happens to their internal edge weight and their between-group edge weight?
Why is a connected Leiden community not automatically evidence of a distinct biological cell type?

Solutions. (1) The formula divides by $m$, so it is undefined when the total edge weight is zero. (2) $\Delta Q=0.2/5-(2)(3)/(2(5^2))=0.0400-0.1200=-0.0800$, so this merge lowers modularity by 0.0800. (3) Refinement exposes better-connected subgroups as separate units before aggregation, allowing the next optimization to reconsider them instead of hiding their structure. (4) Internal weight becomes a loop on the supervertex; between-group weight is summed into an edge between supervertices. (5) Connectivity is a graph property; biological interpretation also depends on how the graph was constructed and on independent evidence about the cells.

What You'll Learn