-
Notifications
You must be signed in to change notification settings - Fork 1
Path Length Decomposition
type: concept up: "Markov-Retrieval-Tutorial" tags: [diagnostic, analysis, retrieval] related: ["Random-Walk-With-Restart", "Tutorial-Figures", "Restart-Probability"]
A first-class diagnostic that reports how much of a node's stationary mass arrived through paths of each length from the seed.
The stationary distribution from Random Walk With Restart tells you which nodes are relevant. Path-length decomposition tells you how that relevance arrived: directly from the seed (length 1), through one intermediary (length 2), through two intermediaries (length 3), and so on.
This is the quantitative form of the trajectory respect commitment of the project. Retrieval treats questions as having trajectories across the corpus, and this diagnostic exposes those trajectories rather than collapsing them into a single score.
Implemented in markov.py alongside the RWR iteration. Both are pure linear algebra (scipy.sparse and numpy), no learned parameters.
run_tutorial.py prints a path-length decomposition for selected entities on the tail-test queries, the queries chosen specifically to require multi-step reasoning across the corpus. For these queries, comparing a chunk the chain recovered against one it did not is the most direct way to see the chain's behavior.
fig3_path_decomposition.pdf shows side-by-side bar charts contrasting one chunk that was successfully recovered against one that was not. See Tutorial Figures.
For the query "DLA suppliers with defense procurement experience," the writeup contrasts two chunks. HoosierMetals' overview chunk (recovered, rank 4) shows a clean k=1 spike with sustained contributions through k=3 and total stationary mass 0.0315. ITAMCO's capabilities chunk (not recovered) shows flat, small contributions across all path lengths and total mass 0.013, well below the threshold for the top five. The contrast is not about ranking but about reachability: HoosierMetals is reachable from the query concepts through short paths via the bridge entity; ITAMCO is not. See Tutorial Queries for the broader query results.
The contribution from paths of exactly length k carries weight c · (1-c)^k, a geometric distribution. This is what makes the diagnostic quantitative: when a chunk's mass concentrates at k = 3, that is genuine three-hop recovery, not an artifact. See Restart Probability for the full derivation and the table of expected hop counts at common values of c.
When the chain underperforms on a query, the decomposition usually reveals one of two failure modes:
- The expected path simply does not exist in the graph (a missing concept link, or a chunk that was not embedded close enough to its bridge).
- The expected path exists but is dominated by a shorter, less informative one.
Either failure points at a specific structural fix in corpus.py, graph.py, or the chain hyperparameters, rather than at vague "tune until better" advice.