[graph] Performance & completeness roadmap to v1.0.0

[epicsagas]

Summary

The graph stack is feature-complete through v0.9.0 — graph-cjk, vector-index/TurboVec, graph-pool, graph-pg, qdrant, elastic, and federation all ship behind feature gates — but it is not performance-characterized, and its algorithmic surface is shallow. This issue tracks bringing the graph stack to production readiness for v1.0.0: published baselines, real algorithmic depth, and measured quality.

Why now

v1.0.0 locks the public API under semver. Before that lock, the graph stack needs three things it currently lacks: (1) published performance baselines, (2) the algorithmic depth users expect from a graph-capable dependency, and (3) at least one real-world integration to validate the design. It ships breadth (CJK search, ANN, WAL pool, multi-backend, federation) without measured guarantees — and with only BFS for traversal.

Current state (code evidence)

Area	State	Evidence
Graph algorithms	Shallow — BFS only	src/graph/traversal.rs (206 LOC): graph_neighbors, related_nodes (recursive-CTE BFS), build_graph. No PageRank, community detection, shortest-path, connected components, node similarity, or centrality.
Benchmarks	Exist, no baseline	benches/graph_bench.rs, benches/compute_bench.rs present. ROADMAP v1.0.0 #3 "Performance baseline + CI regression detection" is not done.
Korean recall	Implemented, unmeasured	src/graph/cjk.rs (185 LOC, shipped v0.7.0). No quantified recall@k on a Korean corpus; quality vs trigram is asserted, not measured.
Concurrency	Implemented, unproven	src/graph/async_pool.rs (417 LOC, WAL pool). No contention benchmark under concurrent writes + reads.
Integration	None yet	No external project ships on the graph stack.

Workstreams

Axis A — Benchmarks & baselines (gating)

• Publish recall@k / latency / p99 for FTS (graph-cjk vs trigram), ANN (vector-index vs brute-force), hybrid (search RRF / CombMNZ)
• Korean-corpus numbers specifically (the differentiator vs. generic embeddings)
• Federation overhead (qdrant + elastic + TurboVec)
• Wire benches/graph_* into CI as a perf-regression gate (closes ROADMAP v1.0.0 docs(i18n): add 10-language README translations #3)

Axis B — Scale ceiling

• Characterize graph-pool (SQLite WAL) and PgGraph from ~10K to 1M nodes
• Document the SQLite→PostgreSQL cutover point (when migrate.rs pays off)

Axis C — Algorithmic depth (the gap vs. Neo4j/GDS)

• Connected components
• Node similarity (Jaccard / cosine over neighborhoods)
• Community detection (e.g., label propagation)
• (Stretch) PageRank / shortest-path
• Gate behind a feature flag, consistent with the zero-mandatory-dep philosophy

Axis D — Recall quality

• Korean recall eval harness (reuse eval / eval-full)
• Quantify graph-cjk vs trigram false-positive reduction on a Korean corpus

Axis E — Concurrency proof

• async_pool.rs contention benchmark (concurrent writer + reader)
• Demonstrate the WAL pool actually delivers reader/writer concurrency

Acceptance criteria

• Published benchmark numbers on a Korean corpus
• At least one graph algorithm beyond BFS shipped behind a feature gate
• CI perf-regression gate active
• v1.0.0 exit criterion met: real-world integration validated

Non-goals

• Auto entity extraction (consumer concern, not the library's)
• Replacing a server graph DB for workloads that genuinely need GDS at scale

Related

• Strategy doc: docs/research/graph_performance_strategy.md (commit bbcf7db)
• Prior research: docs/research/fts5_cjk_alternatives.md, docs/research/roadmap_evaluation.md