feat: Personalized PageRank (PPR) for graph expansion recall

[danieliser]

Problem

Issue #74 documents the hub-node pollution problem: graph expansion follows too many hops through generic entities, pulling in irrelevant memories. The proposed solutions (hop limits, decay multipliers, hub detection) are heuristic — they mitigate symptoms without solving the underlying ranking problem.

The core issue is that BFS-style expansion treats all edges equally. A high-importance memory connected through a hub node gets the same traversal priority as a directly relevant one.

Proposal: Personalized PageRank (PPR)

Replace (or augment) the current BFS expansion with Personalized PageRank seeded from the vector-recall results. PPR solves the hub-node problem algorithmically:

• Teleport probability (α ≈ 0.15–0.2) naturally dampens expansion through hub nodes — the random walk "teleports" back to seed nodes rather than wandering indefinitely through high-connectivity entities
• Personalization ranks the entire graph relative to the query's seed memories, not just by edge proximity
• No manual hop limits needed — PPR's convergence naturally limits effective depth

How it works

1. Run vector recall as normal → seed memory IDs
2. Build personalization vector: uniform weight on seed nodes, zero elsewhere
3. Run PPR on the FalkorDB graph (or an in-memory projection)
4. Return top-K memories by PPR score, filtered by minimum threshold

Prior art

• HippoRAG 2 (NeurIPS 2024 / updated 2025) uses PPR on knowledge graphs for long-term memory retrieval — achieving SOTA on the LoCoMo benchmark. Their architecture is very close to AutoMem's: embeddings for initial retrieval, graph for expansion, PPR for ranking.
• Aider uses PageRank on file-level call graphs for context retrieval in code repos.
• Google's original PageRank — the teleport mechanism was specifically designed to handle hub/authority imbalance.

Implementation options

1. FalkorDB native — FalkorDB supports graph algorithms via RedisGraph compatibility. Check if PageRank/PPR is available as a procedure.
2. Python-side scipy — Export the subgraph around seed nodes, run scipy.sparse PPR (sparse matrix power iteration). Fast for <10K nodes. ~20 lines of code.
3. NetworkX fallback — nx.pagerank(G, personalization=seed_dict). Slower but dead simple.

Option 2 is probably the sweet spot — fast, no external dependencies beyond scipy, and the memory graph is small enough that in-memory computation is fine.

Relationship to existing params

• expand_min_importance / expand_min_strength could be kept as pre-filters on the graph before PPR runs
• expansion_limit maps directly to top-K PPR results
• expand_entities and expand_relations could become PPR mode toggles (which node types to include in the graph)

Impact

This would directly address #74 (hub-node pollution), improve #73 (relevance filtering), and potentially help with #71 (entity disambiguation — PPR naturally separates disconnected clusters around different "Alex" nodes).

References

• HippoRAG 2: Scalable Knowledge Integration
• Personalized PageRank on sparse graphs
• Related: We're implementing PPR for code graph retrieval in Tessera (Phase 5) — similar architecture, happy to share findings.

[coderabbitai]

🔗 Related PRs

#8 - feat: Multi-hop recall with graph expansion and multi-query support [merged]

---

📝 Issue Planner

_{Check the box below or use the @coderabbitai plan command to generate an implementation plan and prompts that you can use with your favorite coding assistant.}

• Create Plan

---

🧪 Issue enrichment is currently in open beta.

You can configure auto-planning by selecting labels in the issue_enrichment configuration.

To disable automatic issue enrichment, add the following to your .coderabbit.yaml:

issue_enrichment:
  auto_enrich:
    enabled: false

💬 Have feedback or questions? Drop into our discord!