Label Propagation for Graph Clustering

How Labels Turn a Cell Graph into Clusters

A cell-neighborhood graph represents cells as vertices and their neighborhood relationships as edges. Label propagation turns that structure into a partition by repeatedly assigning each vertex a label that is common among its neighbors. Vertices sharing a final label are placed in the same cluster. The method is simple, but its simplicity has consequences: the labels can depend on the order in which vertices are updated and on how ties are resolved.

The procedure is a graph-clustering algorithm, not a test of whether two cells have the same biological identity. A cluster is a group induced by the chosen graph and algorithm. Its interpretation still depends on the quality of the graph and on subsequent biological assessment.

The standard initialization gives every vertex its own distinct label. An iteration visits vertices and updates their labels according to the labels currently held by their neighbors. In an asynchronous schedule, each update takes effect immediately, so a vertex visited later in the same iteration can use labels updated earlier. In a synchronous schedule, every vertex's new label is computed from the labels at the start of the iteration, and all changes take effect together. These schedules need not produce the same result.

For the basic rules described here, assume the graph is undirected, has no self-loops, and has nonnegative edge weights. An unweighted graph is the special case in which every edge has weight 1. If a cell graph is directed, first choose a suitable symmetrization; otherwise, “neighbor” and the edge contribution need additional direction-specific definitions. Isolated vertices have no neighboring labels to copy and are ordinarily left with their initial labels.

Local Updates and What They Optimize

For a vertex \(v\), let \(N(v)\) be its set of neighbors and let \(w_{vu}\) be the weight of the edge between \(v\) and neighbor \(u\). In an unweighted graph, set \(w_{vu}=1\). For a candidate label \(c\), define its support at \(v\) as the total weight of edges from \(v\) to neighbors currently carrying \(c\):

Here \(\mathbf{1}\{\ell(u)=c\}\) is 1 when \(u\) has label \(c\), and 0 otherwise. An update chooses a label maximizing \(S_v(c)\). For an unweighted graph, this is simply the label held by the largest number of neighbors. If more than one label has maximum support, there is a tie, and the algorithm needs a tie rule.

One common tie rule is to retain the vertex's current label whenever that label is among the maximizers. Another is to choose randomly among the tied labels. A deterministic implementation might instead use a fixed ordering of labels. These rules are not interchangeable: they can lead to distinct final partitions.

The argument assumes the neighbors' labels stay fixed during the update. With asynchronous single-vertex updates, that condition holds at each step. If ties are resolved by retaining the current label, any label change is to a strictly higher-support label, so \(F\) strictly increases at that step. Since a finite graph has finitely many label assignments, such a sequence of strict increases must terminate. But if tied labels can replace the current label, \(F\) can stay constant during a change; cycles are then possible. With synchronous updates, multiple vertices change at once, so the single-vertex argument does not guarantee that \(F\) increases.

Weights, Update Schedules, and Stopping

Weights affect the strength of a neighbor's vote, not the definition of a label. A high-weight edge contributes more support to its neighbor's label than a low-weight edge. This is appropriate when edge weights represent relative neighborhood strength, as in a weighted cell graph, but it does not make the final labels uniquely determined.

Asynchronous updates allow a label to travel through the graph within an iteration: cells visited later can use labels that have already moved. Synchronous updates instead use the same previous state for all vertices in an iteration. Neither schedule is automatically equivalent to the other, and an iteration count alone does not ensure that the labels have stabilized.

In practice, a label-propagation implementation needs a stopping rule, such as stopping when a full asynchronous sweep makes no changes, or stopping at a prespecified iteration limit. For stochastic tie-breaking, repeated runs can be useful for assessing how much the partition varies. If an iteration limit is reached while labels are still changing, the output should be treated as an unfinished or schedule-dependent result, not silently described as a stable fixed point.

Diagnostics, Alternatives, and Limitations

Useful diagnostics begin with the graph and then examine the algorithm's behavior. Check that edge weights are nonnegative and that the graph has the intended symmetry. Record the update schedule, initialization, tie rule, and stopping rule. Inspect whether any vertices remain isolated and whether any labels are still changing at termination. Compare partitions across different update orders or tie-breaking seeds; substantial differences indicate that the result is sensitive to implementation choices.

Label propagation is fast and easy to implement because each update only aggregates labels among a vertex's neighbors. Its main alternative in the immediate graph-clustering context is an objective-based community method such as Louvain or Leiden: those methods use a community quality objective and their own iterative procedures, whereas basic label propagation copies a locally most-supported label. The local within-label weight justification above does not turn label propagation into modularity optimization. These methods can therefore return different partitions even on the same graph.

The most important failure modes are:

• Order sensitivity: asynchronous updates use the latest labels, so changing the vertex order can change later votes.
• Tie sensitivity: several labels may have equal support, especially at the start when every vertex has a distinct label.
• Over-merging: labels can spread across a connected graph and produce very large communities; connectedness alone does not establish that one cluster is meaningful.
• Nonconvergence: permitted tie changes or synchronous updating can cause cycles or persistent changes.
• Graph dependence: missing, spurious, or poorly weighted edges alter the votes and therefore the clusters.
• Isolated vertices: without neighbors, a vertex has no label evidence from the graph and ordinarily retains its own label.

These limitations matter in single-cell analysis because a partition is conditional on the constructed graph. Label propagation does not independently validate cell types, select a biologically correct number of clusters, or remove artifacts from the graph. Its speed is useful for exploration, but it should not be mistaken for stability or biological confirmation.