PersonalizedPageRank iterates full KB graph per query — consider local PPR

[vndee]

Problem

PersonalizedPageRank in internal/graph/graph.go iterates over every node in the KB graph for up to 20 iterations (power iteration). Each iteration:

1. Iterates all nodes to distribute rank to neighbors — O(V + E)
2. Iterates all nodes again for teleport + convergence check — O(V)
3. Previously allocated a fresh newRank map per iteration (fixed — now reuses allocation)

For a KB with 50K nodes and 200K edges, one PPR call does 20 × O(V + E) = ~5M map reads on the search hot-path. This runs in a single goroutine with no ctx.Done() cancellation check.

Reachable from

• MCP memex_search with graph_scorer=pagerank
• HTTP GET /search with graph_scorer=pagerank
• CLI memex search --graph-scorer pagerank

Current mitigation

• Per-KB graphs are typically <100K nodes where this runs in milliseconds
• PPR constants are now named (pprAlpha=0.15, pprMaxIter=20, pprEpsilon=1e-6)

Proposed improvements

1. Add ctx.Done() check inside the PPR iteration loop to respect request timeouts/cancellation
2. Local PPR: Instead of iterating the full graph, first compute the BFS neighborhood of seed nodes (e.g., 3-hop), then run PPR only on that subgraph. This is the standard "local PPR" approximation used in production graph systems and would bound the computation to the relevant neighborhood
3. Pre-compute allNodes and degree: These are rebuilt from scratch on every PPR call. They could be cached as part of Graph and updated incrementally in addEdge/removeEdge