[ALGO-02/ALGO-11] No graph algorithm is verified against a reference implementation, and none is checked for determinism

[sandeepkunkunuru]

Goal this serves

SLT-6 (Coverage) — "graph algorithm count ≥ Neo4j GDS with numerical parity vs NetworkX/igraph". The count half is tracked by ALGO-01 (12 shipped, 40 at H1). This issue is the other half, which is the one that decides whether the count means anything.

• ALGO-02 — every algorithm matches NetworkX and/or igraph within a documented tolerance on reference graphs. Baseline: untested. H1 target: 100% of shipped.
• ALGO-11 — every algorithm is deterministic given a seed; non-deterministic ones declare it and accept a seed. Baseline: untested.

The problem

Eleven algorithms dispatch today — pageRank, shortestPath, weightedPath, wcc, scc, maxFlow, mst, triangleCount, cdlp, lcc, plus or.solve. Not one is checked against a reference implementation.

Shipping twelve algorithms that might be wrong is worse than shipping six that are known right. And this is not hypothetical for graph algorithms specifically — the classic divergences are all convention choices that produce plausible-looking wrong numbers rather than errors:

• PageRank: damping factor, dangling-node handling, normalisation, convergence criterion, iteration count vs tolerance
• triangleCount: directed vs undirected treatment, whether each triangle is counted once or once per participating node
• lcc (local clustering coefficient): the denominator for degree-0 and degree-1 nodes — 0, 1, or undefined
• wcc / scc: whether singletons are components
• mst: behaviour on a disconnected graph — forest or error
• shortestPath: tie-breaking among equal-length paths

Every one of those produces a number, not an error. ALGO-03 asks for exactly these conventions to be documented, and they cannot be documented honestly until they are known — which requires comparing against an implementation that documents its own.

Determinism is the same shape of gap

ALGO-11 is untested. This was just addressed for the optimization solvers in #473, where all 29 drew from thread_rng() and no run could be re-derived; the parallel ones needed per-element streams keyed on (seed, iteration, index) because seeding only the outer RNG produced results that looked reproducible under a single thread and were not.

The graph algorithms run under rayon too (cdlp is label propagation, which is order-sensitive by nature). The same question applies and has the same trap.

Definition of done

Phase 1 — reference corpus and harness

• A small set of reference graphs with known properties: a path, a cycle, a star, a complete graph, a disconnected graph with singletons, a directed graph with a cycle, and one real small KG
• A Python harness computing the same quantities with NetworkX (and igraph where NetworkX lacks the algorithm), emitting expected values as a checked-in fixture
• The fixture records the conventions NetworkX used, not only the numbers — that is what makes a mismatch diagnosable rather than just a failure

Phase 2 — parity

• A Rust test per algorithm comparing against the fixture within a documented tolerance (exact for integer-valued results; relative epsilon for PageRank and lcc)
• Every mismatch is resolved as either a bug or a documented convention difference — a difference that is deliberate gets written into ALGO-03's convention table with its reason; one that is not gets fixed
• 100% of the 11 shipped algorithms covered (H1 target)

Phase 3 — determinism (ALGO-11)

• Each algorithm run twice on the same input must produce identical output, including ordering
• For any algorithm that is legitimately non-deterministic (label propagation is the likely one), it accepts a seed and is then reproducible — with a test running it under a 1-thread and an N-thread pool requiring identical results, which is the check that catches scheduling-dependence rather than merely asserting it
• Any remaining non-determinism is declared in the docs rather than left for a user to discover

Phase 4 — hold it

• Parity tests run in CI (CH-ALGO-PARITY is listed in spec 18 as a commit-blocking gate). Depends on [CH-REGRESS] There is no CI running the test suite — 2571 tests gate nothing #480, since there is no CI to add them to

Why this before adding more algorithms

ALGO-01 wants 40 algorithms at H1, up from 12. Adding 28 unverified algorithms to 12 unverified ones makes the parity problem three times larger and no more tractable. Establishing the harness first means each new algorithm arrives with its parity test, at near-zero marginal cost.

Non-goals

Property-based testing (H3), GPU/CPU parity (ALGO-10 has its own lane), and performance — this is purely about producing the right numbers.