ADR 0047 — Graph-augmented retrieval (Personalized PageRank re-ranking)

• Status: accepted
• Date: 2026-10-06
• Slice: P47 (engine core) + P48 (DSL + codegen) + P49a (code-RAG tools) + P49b (precise structural edges) — part of the EE knowledge/GraphRAG parity program

Context

The K5 knowledge graph (mosaic_knowledge::graph) is a deterministic, in-process graph derived from the indexed entries: symbol / file / endpoint nodes from code (K2), book / chapter nodes from the book library (K3), and report nodes + cites edges from citation counts. It has uses / contains / serves / next / cites edges. But retrieval never used it — Store::hybrid fuses BM25 + cosine with RRF and returns; the graph was only ever rendered (the /knowledge graph page) or profiled. So a globally central entity (a hub symbol that many others call, a load-bearing chapter) was not resurfaced by search even when it was the most structurally important answer.

The EE reference (ee commit ef03fe0, "GraphRAG upgrade") ships exactly this signal: Personalized PageRank over the knowledge graph, wired as an opt-in re-ranking on top of the existing retrieval (HippoRAG-style). EE gates the storage of the graph behind an optional Apache AGE backend; Mosaic already has the graph in-process, so we take the retrieval idea without the external graph-DB.

Goal: let a generated app resurface globally-central entities by re-ranking the hybrid hits with PPR over the existing knowledge graph — opt-in per collection, graceful when the graph is empty.

Decision

1. Engine core: mosaic_knowledge::rank (P47)

A new pure-Rust module with four functions (no new dependencies):

• undirected_weighted_adjacency(&Graph) -> BTreeMap<String, Vec<(String, f64)>> — the symmetric, weight-count adjacency the rank algorithms operate on.
• personalized_pagerank(&Graph, seeds, damping, max_iter) -> BTreeMap<String, f64> — power-iteration PPR with a teleport vector uniform over the distinct seeds; dangling mass redistributed to the seeds. Deterministic (BTree iteration).
• modularity(&Graph, community, r) -> f64 — Newman modularity of a community assignment on the undirected graph.
• louvain_communities(&Graph, r) -> BTreeMap<String, u32> — greedy Louvain (one-pass, per-node best-gain moves to fixed point); returns a deterministic node→community-id map (ids assigned by first-seen order).

All are unit-tested (tests/engine.rs, 10 rank tests): PPR personalization, seed-vs-far-end ordering, mass conservation, modularity sanity, Louvain two-clique recovery + determinism, and the no-edge singleton case.

2. Retrieval: Store::graph_rerank (P48)

Store::graph_rerank(hits, graph_weight) -> Vec<Hit> seeds PPR from the graph nodes that back the hits' entries (GraphNode.entry links a node to its chunk), then re-orders the hits by a weighted blend:

score' = (1 - w) * score + w * (ppr(node) / max_ppr)     where w = graph_weight

Hits whose entry has no graph node keep score' = (1-w)*score (their PPR term is 0), so they rank after the graph-backed ones at a given w. Ties break by original position. It is a no-op when w == 0, the graph has no edges, or no hit maps to a graph node (a pure-prose corpus) — so it is always safe to call.

3. DSL: vector_dbs[].retrieval.graph + graph_weight (P48)

Two new keys under the existing retrieval: block (ADR 0018):

vector_dbs:
  - name: docs
    retrieval:
      mode: hybrid      # unchanged
      top_k: 8          # unchanged
      graph: true       # NEW: enable PPR re-ranking (default false)
      graph_weight: 0.5 # NEW: blend strength in [0,1] (default 0.5)

graph_weight is fail-closed-validated (bad-knowledge-graph-weight, must be finite and in 0..=1). The model decl VectorRetrievalDecl carries graph: bool

• graph_weight: f64 (defaulted at parse: false / 0.5).

This is distinct from strategy.graph (ADR 0018), which gates building the graph layer at index time — retrieval.graph gates using it at query time.

4. Codegen (P48)

knowledge_retrieval(name) now returns the 8-tuple (vw, bw, mmr, rerank, mode, top_k, graph, graph_weight) and vector_search applies the re-ranking right after the fused hits are produced:

let hits = if graph && hits.len() > 1 { store.graph_rerank(hits, graph_weight) } else { hits };

Because it runs per collection from the collection's own config, every surface that calls vector_search — the /api/vectordb/{name}/search REST endpoint, the search_knowledge MCP tool, and the Aide/voice site-search tool loop — inherits the graph re-ranking automatically when the collection opts in. No per-surface plumbing.

Why not port AGE / a graph-DB backend

EE's headline feature is the optional Apache AGE GraphStorage (a per-KB backend: "age" that stores the graph in Postgres+AGE and runs Cypher). Mosaic already keeps the graph in-process (deterministic, cheap, no server), and its retrieval + code-RAG needs only PPR + community structure — not Cypher. Porting AGE would add a Postgres/AGE deployment dependency for a signal that the in-process graph already provides. We therefore match EE on the retrieval idea (PPR re-ranking) and defer an external graph store until a real persistence/Cypher need appears. The graph itself is already persisted transitively via the entries (the JSON knowledge store + LanceDB).

Is AGE the best OSS graph store? It depends on the posture, and Mosaic is embedded-first (SQLite for state, LanceDB for vectors — no server). On that axis AGE is the wrong shape: it is a Postgres extension, so adopting it means running Postgres. For the embedded scenario (the LanceDB analog for graphs) the best OSS option is Kuzu — a C++ embedded graph DB that persists to a single file, speaks Cypher, needs no server, and links the same way LanceDB links. So the decision ladder is: (1) in-process K5 graph (default — already persists via the entries, zero extra deps, PPR/Louvain in-crate); (2) Kuzu as the first external backend if a server-less Cypher store is ever required; (3) AGE only if the app already runs Postgres (reuse the DB, get Cypher). We do not proliferate backends — the in-process graph is the default and the others are opt-in escape hatches, added only when a real need appears.

P49a — the four bounded code-RAG tools

The EE ee-pages demo exposes four code-search tools. We re-implement them over the existing in-process K5 graph + K2 symbol census (no tree-sitter, no new deps, no LLM):

New module mosaic_knowledge::codegraph (pure-Rust, vendored into every generated app) holds the first three + is_code_entry; find_similar is a Store method (it needs the store's vector/keyword legs). The tools are bounded by construction (name lookup, reverse-edge aggregation, depth-clamped BFS, top_k-capped search) — the same "bounded by depth/node caps" posture EE takes. All four are unit-tested (tests/engine.rs, p49_*): name/file/kind matching, reverse-uses correctness, bounded neighborhood, and the code-only/target-excluded similarity filter.

This makes the graph usable for code-RAG over the deterministic K2 token-intersection uses-graph; P49b (below) makes it precise.

P49b — precise structural edges (calls + imports)

The K2 uses edges are a token-intersection: any indexed symbol name that appears in a chunk's text creates an edge. That is a coarse reference signal — a name in a comment, a doc line, or a string literal still counts, so X is "called by" any chunk that merely mentions X. P49b adds the precise structural edges derived from the source itself, on top of uses (not replacing it — the token-match still captures prose→symbol references).

New module mosaic_knowledge::code_ast (pure Rust, no parser dependency — the generated app's engine stays dependency-free, so no C FFI in every generated app). It exposes two deterministic extractors:

• call_sites(text) -> BTreeSet<String> — identifiers actually invoked (an identifier immediately followed by (), excluding definitions (fn/def) and a Rust+Python keyword blocklist. A name in a comment or string is NOT a call site.
• import_names(text) -> BTreeSet<String> — names pulled in by use a::b::c (Rust, the last :: segment) and import a / from a import b (Python) — the module dependencies a body token-match misses.

build_graph (graph.rs) resolves these to symbol node ids (same same-file-first / unique / first resolution as uses) and emits two new edge kinds, calls and imports. find_callers (codegraph.rs) now prefers the precise calls edges and falls back to the token-match uses only when a symbol has no calls edges — so a comment-only mention is no longer reported as a caller. get_call_graph / the graph page already walk all edge kinds, so they pick up calls / imports automatically.

File-level imports. import_names (and the per-chunk imports edges) read each chunk's text, so a module-level use/import in the file header is not in any symbol chunk and would be missed. code_ast::file_imports therefore extracts only the column-0 (module-level) import names — disjoint from the function-local ones — and the K2 ingest records them on the code-summary chunk's meta.imports. build_graph turns each cross-file one into a file → symbol imports edge (a same-file name is not a real import), so module dependencies (use crate::report::{build_report, …} → file:serve.rs → build_report) are in the graph too. Brace groups (use a::b::{x, y}), aliases (Read as R → the imported Read), and glob imports are handled.

Live check on the portal's code corpus: parse_date is mentioned in a comment inside handle_summary but only called by build_report + normalize_date. The coarse uses edge handle_summary → parse_date is still present (the mention), but the precise calls graph omits it, so find_callers(parse_date) returns exactly build_report + normalize_date.

Rust/Python are the tuned targets; other languages degrade to the name( call-site rule.

P51 — the book concept graph ("symbols for a thesis")

The code tier gets its "symbols" from the K2 census (real AST-ish functions), but the book tier only had a chapter hierarchy (book → chapter → next) + citations — no way to ask "which chapters discuss X?" the way a thesis writer needs. P51 adds a concept layer to the book graph, so a book is indexed with the same "symbol" discipline as code.

New module mosaic_knowledge::concepts (pure Rust, vendored, no deps). extract_concepts(chapter_text, heading) -> BTreeMap<String, u32> deterministically scores the salient terms of a chapter:

• term frequency — how often a word appears (stopwords + single chars dropped);
• capitalization signal — a mid-sentence capitalized word is a proper noun / technical term ("Projections", "Event Sourcing") and is weighted higher (a sentence-start capital is not a signal — that's just the grammar);
• heading terms — the chapter title's words are always concepts (the title names the chapter's subject), weighted higher.

The result is ranked by (capitalized, frequency, name) and capped at MAX_CONCEPTS (25) per chapter, so the graph stays bounded. build_graph (book tier) turns each chapter's concepts into topic entities + chapter → entity mentions edges (weight = salience). find_concept(graph, name) is the thesis query: it returns the concept node id (case-insensitive) + the chapters that mention it (reverse of mentions), so you can then get_graph(node=<concept>) to expand the neighborhood or search the chapters that mention it. (P52 — below — unifies these auto concepts as type = "topic" entities, so the node id is now entity:topic:{name}, kind = entity; find_concept is a back-compat alias for find_entity(name, "topic").)

Exposed like the P49a tools: GET /api/vectordb/{name}/concept?name= + the find_concept MCP tool. With retrieval.graph: true (P48), a PPR re-rank now propagates through these concept nodes too, so a central concept (a "load-bearing" term in the thesis) resurfaces the chapters that cluster around it.

This is the what's-missing piece for the book-library / thesis use case: the deterministic, citation-ready concept graph over prose, mirroring the code symbol/uses graph. (Entity relations between concepts — "X is-a Y", "X used-by Z" — are a later slice; the concept→chapter mentions edges are the substrate.)

P52 — the typed-entity gazetteer ("entity types on all important levels")

P51's concepts are untyped topics. A thesis needs typed entities on the levels that matter — persons, locations, topics, doctrines, councils, written works, sermons/preaching, institutions, events. P52 adds a typed-entity gazetteer: the researcher curates a small dictionary (per entity: a type, a canonical name, and alias surface forms), and the engine matches it against the book chapters deterministically.

New module mosaic_knowledge::entities (pure Rust, vendored, no deps). extract_entities(text, gazetteer) -> BTreeMap<String, u32> matches each entity's surface forms against the chapter text, case-insensitive, word-boundary- anchored (so "Calvin" does not match "Calvinism"), and per entity the longest form wins per span (so "Council of Trent" is not double-counted by its "Trent" alias). It returns entity:{type}:{canonical} → mention count (only entities actually mentioned).

DSL: vector_dbs[].entities — a list of typed gazetteer entries:

entities:
  - type: person
    names: [John Calvin, Calvin, Jean Calvin]   # names[0] = canonical
  - type: council
    names: [Council of Trent, Trent]
  - type: location
    names: [Geneva]
  - type: doctrine
    names: [Sola Fide]

Types are free-form (the researcher declares whatever the domain needs); ENTITY_TYPES is the recommended standard set for a research/thesis corpus (esp. theology): person, location, topic, doctrine, council, book, sermon, institution, event, concept, other. build_graph (book tier) turns each matched entity into an entity:{type}:{name} node (kind=entity) + a chapter → entity mentions edge (weight = mention count). P51's auto topics fold in as type = "topic" entities, so a corpus gets a fully typed concept graph with zero gazetteer, and the researcher's curated entities layer on top.

find_entity(graph, name, type?) returns the entity node id + the chapters that mention it (the type filter is optional); list_entities(graph, type?) enumerates every typed entity with its mention salience, most-mentioned first. Exposed like the P49a tools: GET /api/vectordb/{name}/entity?name=&type=, GET /api/vectordb/{name}/entities?type=, + MCP find_entity / list_entities. The gazetteer is set on the Store at boot (idempotent) + persisted, so it survives reboots. With retrieval.graph: true (P48), PPR now propagates through the typed entities too — a central person/council/doctrine resurfaces the chapters that cluster around it.

This is the "symbols for a book" with types: the deterministic, citation-ready typed-entity graph over prose, mirroring the code symbol/uses graph, tuned for the library/thesis/research use case. (Gazetteer relations between entities — "X is-a Y", "X attended council Z" — and LLM-assisted entity discovery are later slices; the chapter → entity mentions substrate is what lands here.)

P52 (runtime) — the runtime entity registry

The DSL gazetteer is a floor, set at boot from the tessera — but a researcher curating a thesis on a live server shouldn't have to edit the tessera + redeploy for every new person/council/doctrine they discover. So the Store carries a second, additive runtime_entities layer (persisted alongside the entries in the store file, restored at boot, never clobbered by the boot-time set_gazetteer of the DSL floor). Store::effective_gazetteer() is the DSL floor

• the runtime layer de-duplicated by node id (declared wins), and that is what graph() matches against — so a runtime add is reflected in the graph immediately (no reindex) and survives a reboot.

Semantics mirror the K9 runtime-source registry:

• add_entity appends to the runtime layer. A node id already in the DSL floor is rejected (the tessera is the source of truth for declared entities — they are immutable at runtime); re-adding an existing runtime entity is an idempotent no-op.
• remove_entity(type, name) removes from the runtime layer only; removing a declared entity is rejected (edit the tessera).
• gazetteer_listing() returns every row with provenance — origin = "declared" (tessera) or "runtime" (API-added) — for the listing surface.

Exposed like the rest of P52: GET /api/vectordb/{name}/gazetteer (list with provenance), POST /api/vectordb/{name}/gazetteer/add ({"type":"…","names":[…]} or {"type":"…","name":"…"}), DELETE /api/vectordb/{name}/gazetteer/remove?type=&name=, + MCP list_gazetteer / add_entity / remove_entity. Because the graph is derived on demand from the effective gazetteer, an add/remove needs no reindex — the next find_entity / list_entities / make_report already sees the change, and it persists across restarts. This is what lets the researcher (or an LLM agent via MCP) curate the entity types live as they read, without touching the tessera.

Non-goals (later slices)

• Entity relations — edges between typed entities (is-a / used-by / attended / authored / co-occurrence) for a true thesis entity graph, on top of the P52 chapter → entity mentions substrate.
• LLM-assisted entity discovery — an agent-layer pass (an MCP tool + the LLM seam) that extracts typed entities/relations from a chapter the deterministic gazetteer can't know in advance, feeding the researcher's gazetteer. The engine stays LLM-free (the LLM is the app/agent's, not the vendored engine's).
• Cross-book concept alignment + disambiguation — the same surface form across books / homographs ("Trent" the council vs. the town; "Apple" the company vs. the fruit) resolved to the right typed entity.
• tree-sitter precision upgrade — replace the pure-Rust code_ast call-site/import extractors with real tree-sitter ASTs (Rust/Python calls/imports/implements) for full-precision edges (method/qualified calls, implements). The dependency-free code_ast already delivers the high-value precise calls edges; tree-sitter would be a build-time (compiler) pass shipping pre-computed edges, keeping the app engine dependency-free.
• P50 — wire graph-RAG (+ code-RAG) into the mosaic-pages site and deploy to li7.
• Community-augmented retrieval (Louvain as a second re-ranking signal) and a local-vs-global retrieval mode split — the Louvain/modularity core is in (P47) for when those land.

Consequences

• Opt-in and backward-compatible: default graph: false means existing apps and goldens are byte-identical unless they opt in.
• The graph becomes load-bearing in retrieval, not just a rendered diagram.
• Pure-prose collections are unaffected (no-op), so enabling it is safe.