-
Notifications
You must be signed in to change notification settings - Fork 1
Random Walk With Restart
type: concept up: "Markov-Retrieval-Tutorial" tags: [algorithm, markov-chain, retrieval] related: ["Heterogeneous-Graph", "Path-Length-Decomposition", "Restart-Probability"]
Random Walk With Restart (RWR) is the parametric Markov chain at the heart of the tutorial's retrieval method.
A walker steps along edges of the heterogeneous graph according to a transition matrix. At each step there is a probability r (the restart probability) that the walker teleports back to a fixed seed distribution that encodes the query. Iterating to convergence yields a stationary distribution over all nodes, and that distribution is the retrieval ranking.
markov.py contains the pure linear-algebra implementation:
- Transition matrix construction (scipy.sparse).
- The RWR iteration to a stationary vector.
- Path-length decomposition that reconstructs how relevance arrived at each node.
There are no learned parameters. Behavior is controlled by graph structure plus a small set of hyperparameters: restart probability, type weights, and similarity sparsification thresholds.
| Knob | Where set | Effect |
|---|---|---|
Restart probability r
|
run_tutorial.py call to rwr
|
Higher r keeps mass near the seed, lower r lets it spread |
| Type weights | build_transition_matrix |
Controls the relative pull of chunk, document, and concept edges |
| Similarity threshold | build_transition_matrix |
Sparsifies the embedding-similarity edges below the cutoff |
The expected number of steps between restarts is (1 - r) / r, so the tutorial's r = 0.15 corresponds to roughly five or six steps before the walker is pulled back to the seed. See Restart Probability for the full geometric-weighting account, calibration intuition, and how r interpolates between concept-boost-style local re-ranking and global PageRank.
Changes should be evaluated against all five tutorial queries, not one, and the path-length decompositions should still tell a coherent story.
Plain cosine similarity treats each chunk as independent. RWR on a graph that includes concept and document nodes propagates relevance through shared structure, recovering chunks that the encoder would not have ranked highly on text alone. The tutorial's tail-test queries are exactly the cases where this matters.
Concept boost re-ranking, the team's earlier retrieval approach, is formally a one-step Markov chain on a heterogeneous graph restricted to the embedding-retrieved candidate set. The full chain in this repository generalizes that work to multi-step propagation over the entire graph.