Walktrap Clustering with Short Random Walks

Why Walks Can Reveal Communities

In a cell neighborhood graph, a community is a group of vertices with comparatively strong connections within the group. Walktrap looks for this structure through a simple question: if a random walk starts at a cell, where is it likely to be after a few steps? Short walks tend to spend more time among vertices in densely connected regions than among vertices separated by sparse connections. Vertices with similar short-walk behavior are therefore candidates to belong to the same community.

Walktrap turns that intuition into a distance between vertices and, as vertices are grouped, between communities. It starts with each vertex as its own community, repeatedly merges the pair with the smallest current distance, and produces a hierarchy of partitions. The method does not require a known number of communities in advance, but choosing a final cut through the hierarchy is a separate decision.

Random Walks on an Undirected Graph

The transition probabilities in each row sum to 1. In an unweighted graph, a walk chooses uniformly among the current vertex’s neighbors; in a weighted graph, it chooses an edge with probability proportional to its weight. Walktrap is usually described for undirected graphs, so directed k-nearest-neighbor graphs must first be symmetrized or otherwise handled with a method appropriate to directed data.

For a connected undirected graph, the random walk has stationary probabilities proportional to vertex degree: \(\pi_i=d_i/\sum_j d_j\). The walk is not assumed to be at stationarity after the small number of steps used by Walktrap. Instead, the differences in its short-term distributions are the signal used to compare vertices. Vertices in the same densely connected region often have similar destinations after a few steps; a sparse bridge between regions can make their distributions more distinct.

Walktrap Distance

A plain Euclidean comparison of destination probabilities would give equal weight to discrepancies at high-degree and low-degree destinations. Walktrap instead scales each squared discrepancy by the destination vertex’s degree. It also adjusts the distance for the sizes, measured by total degree, of the communities being compared.

For a singleton community \(\{i\}\), the degree-weighted average reduces to \(P^t_{ij}\), so the formula compares the two vertices’ walk distributions. The inverse-degree factor means that a given probability difference at a high-degree destination contributes less than the same difference at a low-degree destination. The volume factor accounts for community size and gives the distance its Ward-type form.

From Vertex Distances to a Hierarchy

Walktrap begins with singleton communities and merges the pair with the smallest current distance. After a merge, the destination distribution of the combined community is the degree-weighted average of its members’ distributions. Distances to the other communities can be updated using a Lance–Williams formula, rather than recalculating every walk distribution from scratch.

This update is a Ward-type identity. To see why it applies, regard each community’s walk distribution as a vector \(q_C=(P^t_{Cj})_{j\in V}\), with squared norm \(\|x\|_D^2=\sum_j x_j^2/d_j\). The distance definition is \(d_t(A,B)^2=\frac{a b}{a+b}\|q_A-q_B\|_D^2\), where \(a=\mathrm{vol}(A)\) and \(b=\mathrm{vol}(B)\). The merged distribution is \(q_{A\cup B}=(a q_A+b q_B)/(a+b)\). Substituting this weighted average into the distance to \(q_C\), and expanding the squared norms, gives

where \(c=\mathrm{vol}(C)\). This establishes the update formula and explains the negative term: the merged community’s distance depends on the separation already present between the two communities that were combined.

Assumptions, Diagnostics, and Alternatives

The stated definitions assume an undirected graph with nonnegative weights and positive degree for every vertex included in the walk calculations. Isolated vertices have no defined transition probabilities under this formulation and should be diagnosed and handled before applying it. If the graph is disconnected, walks cannot cross between its connected components; analyze components appropriately rather than interpreting a lack of cross-component movement as evidence about finer community boundaries. A self-loop, if present in the input, contributes to the transition probabilities and degree under the chosen graph convention, so preprocessing choices should be explicit.

Walk length \(t\) controls the scale of the comparison. Very short walks emphasize immediate neighborhoods and may fail to distinguish groups with similar local connections. Longer walks can blur boundaries by spreading across a larger part of the graph; in a connected graph they increasingly reflect broad, long-run behavior rather than local community structure. There is no universally optimal value of \(t\). Check whether conclusions are stable across reasonable short lengths, and inspect whether the walk distributions become nearly indistinguishable or remain dominated by local irregularities.

Edge weights also matter: a strong edge increases the chance of traversing it, while weak edges are less influential. Compare the weighted graph with a justified unweighted version when weight construction is uncertain. Large hubs may affect many paths, and sparse bridges or uneven local density can make a clean hierarchy difficult to interpret. These are graph-structure issues, not a guarantee that the algorithm has found biological cell types.

Walktrap differs from label propagation, which updates labels based on neighboring labels and can depend on update order. It also differs from Louvain and Leiden, which seek improvements to a partition objective such as modularity. Walktrap’s defining comparison is the distance between short-walk destination distributions; its agglomerative process provides a hierarchy directly. None of these approaches removes the need to examine the graph and assess whether the resulting groups are useful for the scientific question.

Common Pitfall

• Incorrect reasoning: “A small Walktrap distance proves that two cells have similar expression profiles and belong to the same biological type.”
• Correction: The distance measures similarity in their short-walk destination distributions on the constructed graph. It depends on graph construction, edge weights, and walk length; it is not a direct test of expression similarity or biological identity.
• Another common error: Treating the last or smallest-distance merge as the uniquely correct partition. Walktrap builds a hierarchy; selecting its cut requires a separate criterion and contextual judgment.