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

# 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:

```js
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](https://claude.com/claude-code)