Personalized PageRank, in depth: random walks with restart, local forward push with its error bound, Monte Carlo and bidirectional estimation, sweep cuts and PPR in ML systems

Definition: a walk that keeps coming home

Let the graph have adjacency matrix A and out-degrees d(u), and let W = D^-1A be the random-walk matrix whose row u spreads probability equally over u's out-neighbours. Fix a restart probability alpha (typically 0.1 to 0.25) and a source distribution s, usually a single node e_u. The PPR vector p is the unique solution of

p = alpha * s + (1 - alpha) * p W

Read it as a walk. Start at a node drawn from s. At every step, with probability alpha stop, and otherwise move to a uniformly random out-neighbour. p(v) is the probability that the walk stops at v. Because walk length is geometric with mean 1/alpha, mass decays with distance from the source, which is exactly the locality we want. Expanding the equation gives the same thing algebraically: p = alpha * sum over k of (1 - alpha)^k s W^k, a discounted sum of k-step walk distributions. Katz centrality, covered in Katz centrality in depth, is the unnormalised cousin of the same series.

Two properties do most of the practical work. Linearity: p is linear in s, so the PPR of a set of seed nodes is the weighted average of their individual PPR vectors. Topic-sensitive PageRank (Haveliwala, 2002) uses this to precompute one vector per topic and blend them at query time. Symmetry on undirected graphs: ppr_u(v) / d(v) = ppr_v(u) / d(u), which is why rankings for undirected graphs are usually reported as p(v)/d(v), stripping out the bias toward high-degree nodes.

Worked example: six nodes

Take two triangles, A-B-C and D-E-F, joined by the single edge C-D, with source A and alpha = 0.2. Solving the equation to convergence gives p = (A 0.349, B 0.206, C 0.250, D 0.103, E 0.046, F 0.046). C beats B despite both being one hop away because C has three neighbours and receives mass from both A and B. A, B and C together hold 80.5% of the mass while the far triangle holds under 20%: the single bridge throttles flow, and that is the signal local clustering exploits later.

Three ways to compute it

There are three ways to compute PPR, and choosing among them is the main engineering decision.

Power iteration repeats p <- alpha s + (1 - alpha) p W; the error shrinks by a factor of (1 - alpha) per sweep, so 50 sweeps at alpha = 0.2 reduce it by roughly 10^-5. Each sweep touches every edge, which is fine for one source on a million-edge graph and hopeless for a fresh source per request on a billion-edge graph. The other two methods exist for that case.

Forward push: local and bounded

Forward push (Andersen, Chung and Lang, 2006) keeps two vectors: an estimate p, initially zero, and a residual r, initially s. It maintains the invariant

ppr(s) = p + sum over u of r(u) * ppr(e_u)

meaning the true answer is the current estimate plus the PPR of whatever mass has not been pushed yet. A push at u moves an alpha fraction of r(u) into p(u) and spreads the remaining (1 - alpha) r(u) across u's neighbours' residuals; substituting the PPR equation for ppr(e_u) shows the invariant still holds. Pushing stops when every residual is small relative to its degree.

from collections import deque

def forward_push(adj, source, alpha=0.2, eps=1e-4):
    """adj: dict node -> list of out-neighbours. Returns (estimate, residual)."""
    p, r = {}, {source: 1.0}
    queue = deque([source])
    while queue:
        u = queue.popleft()
        du = len(adj[u])
        ru = r.get(u, 0.0)
        if ru < eps * max(du, 1):      # stale queue entry
            continue
        p[u] = p.get(u, 0.0) + alpha * ru
        r[u] = 0.0
        if du == 0:                    # dangling: send the rest back to the source
            r[source] += (1 - alpha) * ru
            queue.append(source)
            continue
        share = (1 - alpha) * ru / du
        for v in adj[u]:
            before = r.get(v, 0.0)
            r[v] = before + share
            dv = max(len(adj[v]), 1)
            if before < eps * dv <= r[v]:   # crossed the threshold: enqueue once
                queue.append(v)
    return p, r

The bound comes from accounting. Every push at u removes alpha * r(u) from the total residual, and r(u) is at least eps * d(u) when pushed, so each push removes at least alpha * eps * d(u) of residual while costing d(u) edge visits. Total residual starts at 1, so total work is at most 1 / (alpha * eps), whatever the size of the graph. On an undirected graph the symmetry property turns the leftover residual into a per-node error bound: the estimate undershoots the truth at v by less than eps * d(v).

Tracing the example: pushing A puts 0.2 into p(A) and 0.4 into each of r(B) and r(C). Pushing B adds 0.08 to p(B) and moves 0.16 each to r(A) and r(C), so r(C) becomes 0.56. Pushing C adds 0.112 to p(C) and sends 0.149 to each of A, B and D. With eps = 0.01 the run ends after 33 pushes and 77 edge visits, with p(D) = 0.088 against a true 0.103 and 6.5% of the mass still in residuals; with eps = 0.001 it takes 65 pushes and 152 visits and every entry is within 0.0013. The ordering of the top three nodes is right at both settings, which is what a ranking query needs.

Monte Carlo and bidirectional estimation

The walk definition gives a second algorithm directly: run W walks from the source, stop each with probability alpha per step, and count where they stop. The estimate is unbiased, embarrassingly parallel and needs no per-node state, so it suits graphs sharded across machines or stored in a graph database that can only answer neighbour lookups. Its weakness is resolution. An entry of size pi needs on the order of 1/pi walks for a useful relative error, so Monte Carlo finds the large entries cheaply and cannot see small ones.

Bidirectional estimators combine the two. FAST-PPR (Lofgren et al., 2014) and BiPPR (Lofgren, Banerjee and Goel, 2016) answer the pair query 'what is ppr_s(t)' by running a reverse push from the target t, which leaves estimates p^t and residuals r^t with ppr_s(t) = p^t(s) + sum over v of ppr_s(v) * r^t(v), then estimating that sum with random walks from s. Each half covers the other's blind spot, and the combined cost for a typical target is far below either method alone. Use this when queries are pairs, for example scoring candidate items for a user.

Local clustering with the sweep cut

Andersen, Chung and Lang introduced push for local graph partitioning, and the sweep cut remains one of PPR's most useful outputs. Sort nodes by p(v)/d(v) in decreasing order and consider each prefix set. Compute each prefix's conductance: the number of edges leaving the set divided by the smaller of the set's volume (sum of degrees) and the rest of the graph's volume. Return the prefix with the lowest conductance.

In the example the order is A, B, C, D, E, F. The prefix {A, B, C} has one cut edge (C-D) and volume 2 + 2 + 3 = 7, out of a total volume of 14, giving conductance 1/7 = 0.143, the best cut in the graph. The theory guarantees that if the source sits inside a set of low conductance, the sweep over its PPR vector finds a set of comparably low conductance while touching only nodes near the source. That makes it a practical tool for community detection around a seed, fraud-ring expansion from a known bad account, and building local subgraphs for downstream models.

PPR inside ML systems

PPR appears inside modern ML systems more often than its name does.

• Recommendation. Pinterest's Pixie (Eksombatchai et al., 2018) runs short random walks with restart over a bipartite pin-board graph in memory to produce candidates for a user in real time, a Monte Carlo PPR with early stopping once enough items have been visited often.
• Graph neural networks. APPNP (Klicpera, Bojchevski and Guennemann, 2019) separates prediction from propagation: a neural network predicts per-node outputs, then a few steps of the PPR iteration spread them over the graph. Because restart keeps mass near each node, it propagates further than stacking message-passing layers without washing every node toward the same representation.
• Retrieval over knowledge graphs. HippoRAG (Gutierrez et al., 2024) extracts entities from a question, uses them as seeds, runs PPR over an LLM-built knowledge graph of passages and entities, and ranks passages by the resulting mass, which lets multi-hop questions reach passages that share no words with the query.
• Feature engineering. PPR scores between a node and labelled seeds (known fraud, known spam) are strong tabular features, and their linearity means one vector per seed set can be precomputed and blended. Related diffusion models on graphs appear in influence maximization.

Running it in production

A production PPR service usually mixes the methods: precompute and store the top-k entries of PPR for heavy-traffic sources offline, compute push on demand for the long tail, and fall back to Monte Carlo on graphs too large or too distributed to push over. Store top-k only, because the full vector is dense in principle and mostly noise in its tail.

Three graph properties need explicit handling. Dangling nodes in directed graphs have no out-edges; the code above returns their mass to the source, which keeps the walk personalised; teleporting uniformly instead would leak global PageRank into the answer. Hubs with millions of edges make one push expensive and dominate unnormalised scores; normalise by degree for undirected graphs, cap or sample hub neighbourhoods, and consider removing utility nodes such as a 'Popular' board. Freshness is the last: precomputed vectors go stale as edges arrive, and incremental push updates exist, but most teams simply rebuild hot vectors on a schedule matched to how fast rankings must react.

Alpha is the main tuning knob. Larger alpha gives shorter walks, more local results and cheaper push; smaller alpha reaches further and costs more. Tune it against an offline relevance metric, not by intuition, and keep eps proportional to the scores you need to distinguish.

Failure modes

• Degree bias. Raw p(v) on undirected graphs ranks hubs highly for every source. Rank by p(v)/d(v) or filter hubs.
• Leaky dangling handling. Uniform teleport from dead ends mixes global popularity into a personal ranking. Return the mass to the source.
• Eps too large. Push stops before mass reaches the second hop and every result looks like the source's direct neighbours. Check the leftover residual mass and lower eps until rankings stabilise.
• Monte Carlo used for small entries. Long-tail candidates get zero visits and are silently excluded. Use push or bidirectional estimation for pair scores.
• Stale precomputation. New nodes have no stored vector and new edges are ignored. Fall back to on-demand push for unknown sources and monitor vector age.
• Mismatched alpha conventions. Some libraries take the damping factor (continue probability, for example 0.85) rather than the restart probability; passing 0.15 where 0.85 is meant inverts locality. Check a known small example before trusting any library.

Trade-offs

What to do next

1. Implement forward push from the listing and check it against power iteration on the six-node example; reproduce 0.349 for A.
2. Run it on your own graph from ten real sources and measure pushes, edge visits and leftover residual at eps = 1e-3 and 1e-4.
3. Decide the ranking score (raw p or p/d) and the dangling-node rule, and write both into the service contract.
4. Tune alpha against an offline relevance metric such as recall at k of known good recommendations.
5. Add a sweep-cut endpoint for seed expansion and compare its clusters with a global method.
6. Read PageRank in depth for the global version and eigenvector centrality for the spectral view of the same family.