Graph-augmented vector retrieval: ANN-seeded relationship expansion (GraphRAG-lite)

Problem

Pure vector similarity misses context that is relationally adjacent but not semantically adjacent to the query. The canonical RAG failure: the chunk that matches the query mentions "the incident," and the chunk that actually explains the incident is the parent document's summary, the next chunk in sequence, or a referenced record — none of which embed anywhere near the query vector. Graph-RAG systems (Microsoft GraphRAG, arXiv:2404.16130, and successors) address this by expanding retrieval along an entity/knowledge graph, but they require building and maintaining a separate graph store.

Harper already has both halves natively: HNSW vector indexes and explicit typed edges via @relationship declarations (resources/graphql.ts:193–198), with join machinery that traverses them (joinTo/joinFrom, resources/search.ts:503–637). This issue connects them: use the ANN result as seeds, expand along declared relationships with hop-decayed scoring, and re-rank the union. No new graph store, no new index type — a query-time composition of existing structures.

Proposed API

A new expand option alongside a vector sort:

Chunks.search({
  sort: { attribute: 'embedding', target: queryVector, distance: 'cosine' },
  expand: {
    hops: 2,                              // max relationship hops from a seed (default 1)
    hopPenalty: 0.1,                      // distance added per hop (default 0.1; see Scoring)
    relationships: ['next', 'parent', 'references'],  // which edges to follow (default: all declared)
    candidates: 100,                      // cap on total expanded candidates (default 4 × limit)
  },
  limit: 10,
});

REST surface mirrors the existing FIQL sort(...) function style; exact string syntax is the implementer's call (precedent: sort(vector,cosine,[1,2,3]) parsing in search.ts:1290).

Execution pipeline

1. Seed retrieval. Run the normal HNSW search (over-fetch seeds: max(limit, ef) candidates as today). Seeds carry their (reranked, exact — see the int8 rerank block in search.ts) distances.
2. Expansion. Breadth-first from each seed along the configured @relationship edges, up to hops. Edge resolution reuses the existing foreign-key machinery: from relationships are a forward key lookup; to relationships are a reverse-index lookup — the same paths joinFrom/joinTo use. Track (recordId, hopCount) with the minimum hop count per record; stop at the candidates cap (log/explain when capped).
3. Scoring. For each expanded record:
   • If it has the same embedding attribute, compute its exact distance to the query via exactDistance() (HNSW line ~732) from its full-precision vector.
   • If it lacks a vector (e.g. a metadata record), inherit the best seed's distance along its path.
   • Apply hop decay: adjustedDistance = baseDistance + hops × hopPenalty.
4. Merge + rerank. Union seeds (hop 0) and expanded candidates, dedupe keeping the best adjustedDistance per record, sort ascending, apply limit/offset as usual (Table.ts:2434).
5. Metadata. Expose per-result $distance (adjusted) plus $hops, following the existing $distance property-resolver pattern (Table.ts:3542–3544, resolver registered by the HNSW index at HierarchicalNavigableSmallWorld.ts:892–915). Raw distance vs. adjusted distance: return adjusted as $distance, raw as $rawDistance if cheap.

Scoring decision (recommendation, not mandate)

Additive hop penalty in distance space is the recommendation: it is metric-agnostic (works for cosine [0,2], squared-euclidean [0,∞), and negated dot product, which can be negative — multiplicative decay breaks there), and it has one intuitive knob. A multiplicative decay^hops on similarity is more common in the literature but requires per-metric normalization. If the implementer finds additive penalties behave poorly on euclidean (unbounded distances dwarf the penalty), normalizing distances to ranks before penalizing is an acceptable fallback — document whichever lands.

Same-table vs. cross-table expansion

Relationships may point at other tables (Post.author → User). A flat ranked result list must be homogeneous, so for v1:

• Same-table relationships (chunk→chunk: next, previous, parent, references — the common shape for chunked-document corpora) produce candidates that enter the ranked result set.
• Cross-table relationships do not enter the flat ranking; related records are available through the existing select relationship projection on each result, exactly as today. So "give me matching chunks, each with its source document" already composes.

Cross-table ranked retrieval (heterogeneous result sets) is explicitly out of scope for v1 — it needs a result-shape design discussion first.

Permissions

Expanded records must pass the same visibility rules as seeds. With predicate-aware traversal (series part 1) in place, apply the same record predicate (condition-derived + vectorFilter + RBAC hook) to expansion candidates before they enter the merge. Without part 1, fall back to post-filtering the merged set — correct, but reintroduces under-fill; this is why part 1 sequences first.

Implementation notes

• Primary site: Table.search() / searchByIndex() orchestration layer (search.ts), not inside HierarchicalNavigableSmallWorld — the index stays a pure vector structure. Expansion is a post-ANN stage like the existing int8 rerank.
• Reverse (to) relationship lookups hit the related attribute's index via getRange on the foreign-key value — same as joinTo. Budget roughly seeds × avgDegree^hops index lookups; the candidates cap is the safety valve.
• The expansion stage needs full-precision vectors for expanded records; they're on the record itself (the @embed/[Float] attribute), so it's one primaryStore.getEntry per candidate — entries are likely needed anyway for the result.
• explain: true should report seed count, expansion counts per hop, cap truncation, and per-stage timing.

Acceptance

• expand option implemented for vector-sort queries (JS API + REST/FIQL surface), with hops, hopPenalty, relationships, candidates.
• Same-table relationship expansion enters ranked results with hop-decayed exact distances; vectorless records inherit seed distance.
• Dedupe keeps best score; results carry $distance and $hops.
• Cross-table relationships are skipped for ranking but continue to work via select projection (test both).
• Permission/visibility filtering applied to expanded candidates (with and without predicate-traversal available).
• candidates cap enforced and surfaced in explain; no unbounded fan-out on dense graphs.
• Tests: a chunked-document fixture (chunks with next/parent self-relationships) where a known-relevant chunk is retrievable only via expansion (its own distance is poor); verify it ranks within top-k with expansion on and absent with expansion off.
• Benchmark: retrieval-quality harness comparing plain ANN vs. expanded retrieval on the fixture corpus (hit-rate of "gold context" records at k=5/10), plus latency overhead per hop.
• Docs: option reference, scoring semantics, chunk-graph modeling guidance (how to declare next/parent relationships on a chunks table), and a worked RAG example.

Out of scope (follow-ups if benchmarks justify)

• Spreading activation / personalized PageRank over the combined typed-edge + HNSW-layer-0 graph (bounded iterative propagation seeded by ANN hits). Strictly more powerful than BFS-with-decay, and the layer-0 adjacency lists are already persisted per node — but it needs its own convergence/cost analysis.
• Injecting typed edges into the HNSW adjacency lists themselves. Rejected by design: the M-bounded connection lists and the insert/delete/orphan-repair logic exist to maintain navigability invariants; non-metric edges belong in a parallel structure, not in the beam search.
• Heterogeneous (cross-table) ranked results.
• LLM-based entity extraction to create relationship edges (that's an app/component concern; core consumes declared relationships).

Series

Part 2 of the hybrid graph/semantic retrieval sequence: #1241 (predicate-aware traversal) → this → #1243 (conversational retrieval primitives) → #1244 (semantic hierarchy research). Depends on #1241 for correct permission filtering of expanded candidates; functional without it via post-filter fallback.

🤖 Generated with Claude Code