codegraph communities --drift is non-deterministic across runs on identical source (breaks /titan-gate arch-snapshot comparison)

[carlos-alm]

Summary

While running /titan-gate's Step 5.5 (architectural snapshot comparison, A1 community stability) against a pure dead-code-deletion diff in src/types.ts (#1727), codegraph communities --drift -T --json reported "new" split/merge candidates that appeared unrelated to the diff (directories like src/cli, src/mcp, src/domain/search, nowhere near src/types.ts).

To rule out a real architectural side effect, I isolated the variable: reverted src/types.ts back to the exact HEAD commit (byte-identical to when .codegraph/titan/arch-snapshot.json was captured), rebuilt, and re-ran codegraph communities --drift -T --json fresh.

Result: even with zero code difference from the snapshot's capture point, a fresh run produced a different result than the stored snapshot:

	baseline (arch-snapshot.json)	fresh run, same HEAD commit
modularity	0.5568	0.5542
splitCandidates	68 entries	69 entries, 15 differing
mergeCandidates	13 entries	14 entries, 27 differing

This is more drift than what appeared when comparing the baseline against the actual (unrelated) diff. Running the drift command twice in a row on the same already-built graph state does produce identical results (confirmed separately), so the non-determinism is introduced somewhere in the build/community-detection pipeline itself (e.g., non-fixed iteration order feeding the Louvain optimizer, a timing-dependent node/edge insertion order, or a missing fixed random seed for tie-breaking) — not in the comparison/query logic.

Impact

This makes /titan-gate Step 5.5 (A1 community stability, A3 cohesion delta) unreliable: it will report spurious "new drift" / "significant community restructuring" warnings against essentially any diff, independent of whether the diff has any real architectural effect, because the noise floor between two identical-source runs already exceeds the threshold gate uses to flag a real regression. Left unaddressed, this will produce false FAILs/WARNs on every /titan-forge phase, similar in spirit to (but a distinct root cause from) #1732's checkNoSignatureChanges false positive.

Suggested next step

Investigate the Louvain/community-detection implementation (src/graph/algorithms/leiden/ per the module map, or the native Rust equivalent) for non-deterministic ordering — likely a Map/Set/HashMap iteration order that isn't stable, or a random seed that isn't fixed per build. Not investigated further here — this diagnosis was a side-finding while gating an unrelated dead-code-removal commit, and root-causing/fixing non-determinism in a community-detection algorithm is a substantial, separate effort out of scope for that change.

[carlos-alm]

Additional evidence from Titan Paradigm phase 25 (presentation/audit.ts decomposition, low-risk pure refactor + type fix): the same class of non-determinism also affects codegraph audit <target>'s impact-level (BFS transitive-caller) rendering, not just communities --drift.

Isolation performed: ran codegraph build --no-incremental twice in a row on byte-identical source (no code changes between the two builds), then diffed codegraph audit buildGraph -T and codegraph audit src/shared/errors.ts -T output between the two builds. Both showed reordering within "Level N: ..." lines and within caller/impact lists (same set of names, different order) -- confirming the non-determinism originates in the build/graph-construction pipeline (consistent with this issue's hypothesis of non-fixed node/edge insertion order), not in the Louvain/community-detection code specifically, and not in any per-command query/rendering logic.

For contrast: re-running the exact same codegraph audit command twice against the same already-built DB (no rebuild in between) produced byte-identical output both times -- so the query/render layer itself is deterministic; only the build-time ordering varies.

This broadens the likely blast radius of the root cause: anything that renders an unordered adjacency/BFS-level list (audit, fn-impact, impactAnalysis, diffImpact, communities) is potentially affected, not just Louvain community detection. Recommend prioritizing a fix for stable node/edge insertion order (e.g. explicit ORDER BY id or a stable sort key at the point objects are rendered) since it's a small ask relative to the "substantial, separate effort" of fully fixing Louvain-specific instability, and would resolve the false-drift-noise problem for most consumers.