Random Walk Algorithms on Graphs, Explained

A random walk on a graph is one rule — from where you are, step to a uniformly chosen neighbour — and almost every graph algorithm that scales is built on it. What makes it useful is that the walk forgets where it started and settles into a fixed distribution over nodes. What makes it subtle is that on perfectly ordinary graphs, it does not.

One step, as a matrix

Write the walk as a transition matrix P, where P[u][v] is the probability of stepping from u to v. For a simple undirected graph that is 1/deg(u) if u and v are adjacent and 0 otherwise. Every row sums to 1.

If your position after t steps is the row vector x_t, your position after one more step is x_t P. That is the entire algorithm: repeated vector-matrix multiplication. The reason walks scale to graphs with billions of edges is that you never form P — you sample one neighbour at a time, and each step costs O(1) with the right data structure.

graph
  A—B   B—C   C—D   D—A   D—E

degrees:  A=2  B=2  C=2  D=3  E=1
edges m = 5,  so 2m = 10

transition probabilities from D:  to A, C, E each 1/3
transition probabilities from E:  to D with probability 1

The stationary distribution, verified

A distribution π is stationary when pi P = pi: one more step leaves it unchanged. For a connected undirected graph there is a closed form and it is worth committing to memory, because it says something strong — the walk’s long-run visit frequency depends on nothing but degree.

pi(v) = deg(v) / 2m

  pi(A) = 2/10 = 0.2
  pi(B) = 2/10 = 0.2
  pi(C) = 2/10 = 0.2
  pi(D) = 3/10 = 0.3
  pi(E) = 1/10 = 0.1
                 ---
                 1.0

Check two entries against the definition rather than trusting it:

pi(E) should equal the mass arriving at E in one step.
  E's only in-neighbour is D, which sends 1/3 of its mass to E.
  0.3 × 1/3 = 0.1  ✓

pi(A) should equal mass from B and from D.
  B has degree 2 and sends A half its mass:  0.2 × 1/2 = 0.10
  D has degree 3 and sends A a third:        0.3 × 1/3 = 0.10
  total = 0.20  ✓

The immediate consequence is that an unbiased random walk is a popularity measure and nothing else. If you use walk-visit counts as a relevance score you have re-derived degree, at considerable expense. Every useful walk-based algorithm therefore breaks this uniformity deliberately: by restarting at a fixed node, by damping, or by biasing the step choice as node2vec does with its p and q parameters.

Two conditions, and a graph that fails one

“There is a stationary distribution” and “the walk converges to it” are different claims. Convergence needs the chain to be irreducible (every node reachable from every node — the graph is connected) and aperiodic (the possible return times to a node have greatest common divisor 1).

The graph above is connected. It is also bipartite: colour {A, C, E} black and {B, D} white, and check every edge — A–B, B–C, C–D, D–A, D–E all join a black node to a white one. Every edge crosses, so every cycle has even length, so every return time is even, so the period is 2.

start at A (black). Track where the walk can possibly be:

  step 0  A            (black)
  step 1  B or D       (white)   P(A) = P(C) = P(E) = 0
  step 2  A, C or E    (black)   P(B) = P(D) = 0
  step 3  B or D       (white)
  ...

The distribution oscillates forever and never approaches
pi = (0.2, 0.2, 0.2, 0.3, 0.1), even though that pi satisfies pi P = pi.

This is not a pathological construction. Bipartite graphs are everywhere — user-item interaction graphs, account-attribute graphs, any two-sided market — and if you estimate a stationary distribution by simulating and counting, and you happen to stop on an even step, you will get zeros for half the graph.

• The lazy walk fixes it directly: with probability 1/2 stay where you are, otherwise step. Self-loops make odd return times possible, the period becomes 1, and the stationary distribution is unchanged.
• Damping fixes it as a side effect. Jumping to a random node with probability 1 − d, as PageRank does at d = 0.85, makes the chain both irreducible and aperiodic regardless of the graph — which is why damping is not only about dangling nodes.
• Directed graphs need more care. A node with no out-edges absorbs the walk entirely, and a set of nodes with no edges leaving it is a trap that accumulates all the mass. Both are handled by the same random-restart term, worked through on citation network analysis.

How long convergence takes

Even when a walk does converge, the rate is a property of the graph, not a constant. It is governed by the spectral gap — the difference between the largest eigenvalue of the transition matrix (always 1) and the second-largest in absolute value. A large gap means fast mixing; a gap near zero means the walk stays where it started for a very long time.

The structural reading of a small gap is a bottleneck. Two dense clusters joined by a single edge give a walk almost no chance of crossing per step, so short walks sample one cluster only. That is simultaneously bad news and the entire basis of spectral clustering: the eigenvector associated with that second eigenvalue is close to constant within each cluster and different between them, so reading it off partitions the graph. The classic treatment is László Lovász’s survey Random Walks on Graphs (1993), which is still the reference for the bounds.

There is a related quantity that is often the one you actually want: the hitting time from u to v, the expected number of steps for a walk started at u to first reach v. Unlike the stationary distribution it is a pairwise measure and it is asymmetric — reaching a hub from a leaf is fast, reaching the leaf from the hub is slow — which makes it a natural proximity score. Its drawback is exactly that asymmetry with respect to degree: hitting times to high-degree nodes are short from almost anywhere, so an unadjusted hitting-time score degenerates into popularity for the same reason the stationary distribution does.

Practically, this means walk length is not a free parameter you set to a round number. A short walk on a graph with strong community structure samples locally — which is exactly what you want for a personalised recommendation and exactly wrong for estimating a global measure.

What consumes walks

• PageRank is the stationary distribution of a damped walk on a directed graph. Personalised PageRank replaces the uniform restart with a restart at one node, and its stationary distribution is a similarity vector for that node — the standard primitive for node-to-node relevance.
• Random walk with restart is the same object under another name and is the basis of production recommendation neighbourhoods: run short walks from a node, count visits, keep the top few hundred by visit frequency, as on graph embedding recommendation systems.
• Embedding methods use walks as training corpora rather than as estimators, which is a genuinely different use: the walk provides co-occurrence statistics for skip-gram and the stationary distribution never appears.
• Graph sampling for training uses walks to choose which subgraph a mini-batch sees, so that neighbourhoods are bounded and importance-weighted rather than exhaustive.
• Approximate counting and estimation. Walks estimate triangle counts, effective resistance and community membership without touching most of the graph, which for a graph that does not fit in memory is often the only option available.