-
Notifications
You must be signed in to change notification settings - Fork 1
Restart Probability
type: concept up: "Random-Walk-With-Restart" tags: [rwr, hyperparameter, hop-range, calibration] related: ["Random-Walk-With-Restart", "Path-Length-Decomposition"]
The restart probability c is the parameter that couples the random walk to the query and selects how local or global the resulting retrieval is.
At each step the walker either takes a transition along an outgoing edge with probability 1 - c, or jumps back to the seed distribution π₀ with probability c. The seed distribution is fixed across all restarts. The walker does not pick a new random starting point and does not remember previous restarts. Each restart is a clean reset to the same π₀ that was constructed from the query.
This is what makes RWR a personalized chain. The seed encodes "what the query is about," and the resulting stationary distribution reflects "where mass accumulates given that the walker keeps returning to the query."
| Variant | Restart target | Stationary distribution depends on |
|---|---|---|
| PageRank | Uniform over all nodes | The graph alone |
| RWR | Query-derived π₀
|
The graph and the query |
Without restart the walker diffuses to the graph's natural stationary distribution and forgets the query entirely. With uniform restart you get plain PageRank. With query-anchored restart you get a chain whose ranking is meaningful for that specific query.
The path-length decomposition of the stationary distribution is
π* = c · Σ_{k=0}^∞ (1-c)^k (P^T)^k π₀
The term for paths of length exactly k carries weight c · (1-c)^k, a geometric distribution over path lengths. The expected number of steps the walker takes between restarts is the mean of that geometric distribution:
E[steps] = (1 - c) / c
Restart probability c
|
Expected steps before restart |
|---|---|
| 0.85 | 0.18 |
| 0.50 | 1.00 |
| 0.30 | 2.33 |
| 0.15 | 5.67 |
| 0.10 | 9.00 |
| 0.05 | 19.00 |
At the tutorial's c = 0.15, the walker takes on average about 5 to 6 steps between restarts. In the heterogeneous graph this corresponds roughly to two or three structural hops, because each conceptual hop typically traverses two edges (chunk to concept then concept to chunk, for instance, is one conceptual hop but two graph edges).
The geometric distribution has support over all positive integers. The walker can in principle reach any node in any finite number of steps. What changes with c is the probability mass on long paths, not whether they are possible.
At c = 0.15:
Path length k
|
Weight c (1-c)^k
|
|---|---|
| 1 | 0.128 |
| 3 | 0.092 |
| 5 | 0.067 |
| 10 | 0.030 |
| 20 | 0.006 |
A node 15 hops from the query gets some mass, just not much. The decay is geometric but never reaches zero.
Figure 3 of the tutorial PDF shows this directly. HoosierMetals' overview chunk has substantial mass at k = 1, smaller mass at k = 3, and tail mass continuing through k = 8.
| Regime | Behavior |
|---|---|
High c (≥ 0.50) |
Walker barely leaves the seed. Chain is approximately a one-step re-ranker. Roughly equivalent to concept boost re-ranking. |
Mid c (0.10 to 0.30) |
Multi-hop paths contribute meaningfully while the walker stays query-anchored. The chain's distinctive structural reasoning happens here. |
Low c (≤ 0.05) |
Walker mixes globally. Result is close to graph-wide PageRank with a soft personalization toward the query. |
c = 0.15 was chosen for the tutorial because it puts substantial mass on paths of length 1 to 5, the range where the chunk-document-chunk and concept-chunk-concept paths in the heterogeneous graph encode useful signal. Paths longer than 10 hops are statistically present but architecturally not informative for the tutorial's question types.
The right c depends on how cleanly the graph encodes signal versus noise.
| Graph character | Suggested c regime |
|---|---|
| Sparse, high quality (every edge carries meaning) | Lower c, let the walker mix and exploit structure |
| Dense, noisy (many edges with weak meaning) | Higher c, keep the walker close to the query so noise does not dominate |
This is a parameter to calibrate against real query-result pairs. The tutorial's value is reasonable but not optimized. The optimum is corpus-dependent: it shifts with corpus size, edge density, and how each propagation step is normalized, so it should be calibrated rather than inherited from the tutorial.
Each k-th term has known weight c (1-c)^k. When a chunk's mass is concentrated at k = 3, that is genuine three-hop recovery and not an artifact of the walker happening to pass through. The decomposition lets you read off, for any retrieved item, what hop range its relevance came from. This is the kind of inspectability vanilla RAG cannot provide and that the chain framework gives for free as a property of the algorithm.
Vary c across, for example, 0.05, 0.15, 0.30, 0.50 and re-run all five tutorial queries. The expected pattern:
- High
c: rankings collapse toward the vanilla baseline. The walker barely moves. - Low
c: rankings shift toward whatever the graph's global structure favors, including chunks that are not particularly query-anchored. - Mid
c: the chain's distinctive structural reasoning shows up.
This would be a worthwhile addition to docs/tutorial.tex if it would help readers see the role of c concretely.