Repository navigation
Extend native Leiden port to cover full LeidenOptions surface (directed, CPM, weights, candidate strategies) #1936
Description
Status: closed as won't-do for the remainder. Per-edge weights shipped (#2593); the guard that made the whole thing safe shipped in #2592; directed / CPM / confidence-weighting were measured and declined. The numbers and the replacement trigger are below. See the closing comment for the full analysis.
Do not re-verify this by grepping call sites. The original gate ("only take this on if/when a real caller needs one of these knobs") was unsatisfiable by construction — the knobs are unreachable because
LouvainOptionsdoes not expose them, and exposing them is the work being gated. Four consecutive/fixerpasses re-derived the same "not met" conclusion from the same grep before this was spotted.
Background
#1804 ported Leiden community detection to Rust (crates/codegraph-core/src/graph/algorithms/leiden.rs) so the native and JS/WASM engines run the same algorithm instead of native running classic Louvain and JS running Leiden. That port was deliberately scoped to the option surface reachable through louvainCommunities/LouvainOptions (src/graph/algorithms/louvain.ts).
This issue tracked extending it to the rest of the TS reference implementation's surface (src/graph/algorithms/leiden/*).
What shipped
#2592 — the actual bug. louvainCommunities handed native graph.toEdgeArray(), which drops every edge attribute at the FFI boundary, and passed no node attributes at all, while the JS reference resolved per-edge weight and per-node size from attributes. Any graph carrying either would have had the two engines optimize different weighted graphs and return different partitions — silently. nativeParityBlocker now detects that up front and defers to the JS reference. Latent rather than live at the time (no in-tree builder set those attrs), but silent, so it was closed first.
#2593 — per-edge weights, item 3 of the plan below. leidenWeightedCommunities reads per-edge weights natively, with byte-for-byte native/JS parity across weighted bridges, weighted reciprocal edges (the undirected averaging path), weighted self-loops, zero/NaN weights, and a weighted multi-level graph over 3 resolutions × 3 seeds. The attribute-to-number rule now has exactly one implementation shared by both engines, so they cannot drift apart on what a graph weighs. It also fixed buildTemporalGraph, which advertised a graph "weighted by Jaccard similarity" but stored the score under a jaccard key neither engine read.
What was measured and declined
Measured on this repo's own graph (1099 files, 23048 nodes, 49714 edges). Modularity is not comparable across different weightings or across directed/undirected — those are different objective functions — so the readout is directory purity: the size-weighted share of each community sitting in its modal directory.
| candidate | result |
|---|---|
Directed (directed: true) |
Degrades alignment. File-level purity 0.7325 → 0.6724; function-level 0.9624 → 0.9213, with the largest community ballooning 195 → 665. Measurable without the Rust port because the JS reference already implements it. |
CPM (quality: 'cpm') |
No value case found. Addresses modularity's resolution limit, which is not a problem observed at this repo's scale. |
Confidence-weighting (the cheapest real weight, already on CallEdgeRow for 22% of call edges) |
Neutral-to-worse: file-level purity 0.7771 → 0.7725, function-level 0.9647 → 0.9641. Confidence clusters at 0.9–1.0, so it perturbs the graph without restructuring it. |
| Call-site multiplicity | Premise false — it is never recorded. idx_edges_content_unique (#2072) makes duplicate rows impossible; this repo has 10712 calls rows for 10711 distinct pairs. Split out as #2594. |
preserveLabels |
No value: analyzeDrift compares communities to directory structure within a single run, not across commits, so stable IDs buy nothing. |
Alternate candidate strategies, allowNewCommunity, fixedNodes |
Library-completeness knobs; no value case found. |
Stated honestly: directory purity is a proxy. Directed communities may be capturing flow/layer structure that deliberately cuts across directories — which would be useful to a caller who wants that. But absent such a caller, and with the only available quality proxy pointing down, porting ~63 directed branches across adapter.ts, modularity.ts and partition.ts is not justified.
Reopen trigger (a product decision, not a grep)
Reopen if either of these turns up:
- a caller that wants flow-based or layer-based communities → port
directed(plan step 1) - a caller that needs small-community resolution below modularity's resolution limit → port CPM (plan step 2)
#2594 (record call-site multiplicity) is the most likely thing to make the weight plumbing actually pay off, and it is tracked independently.
Original implementation plan (still accurate for the unported items)
- Add a
directed: boolparameter to the native binding; portadapter.ts's directed adjacency population (populateDirectedEdges),modularity.ts'sdiffModularityDirected/directed branch ofqualityModularity, and the directed branches ofpartition.ts's aggregate/move functions. - Add a
quality: 'modularity' | 'cpm'+ expose it throughLouvainOptions; portcpm.ts'sdiffCPM/qualityCPM. Extend— done in feat(communities): native Leiden reads per-edge weights #2593 (newGraphEdge(or add a new napi struct) to carry an optional weightLeidenWeightedEdgestruct; a field on the sharedGraphEdgewas rejected becausedetectCycles/shortestPath/fanInOut/bfsalso consume it and ignore weights). The node-size input array remains unported and is still guarded bynativeParityBlocker.- Port the
all/random/random-neighborcandidate strategies infind_best_community_move(note: these consume RNG draws, so the seeded-RNG stream must be replicated exactly, same as the existing "neighbors" port). - Port
allowNewCommunity(requires theensure_capacity/growth-on-new-id path currently asserted unreachable inmove_node_to_community),fixedNodes(skip-mask), andpreserveLabels(compact_community_ids'skeepOldOrder/preserveMapbranches, currently only the default size-desc sort is ported). - For each addition, replicate parity: native community detection uses Louvain, WASM/JS fallback uses a different algorithm (Leiden) #1804's verification methodology: build/synthetic graphs exercising the new option, compare native vs JS byte-for-byte across multiple seeds, and re-confirm determinism across rebuilds. feat(communities): native Leiden reads per-edge weights #2593's weighted parity suite is a worked example.
Activity
carlos-alm commentedon Aug 2, 2026
Reviewed as part of a
/fixerpass.This issue is explicitly self-gated: "Only take this on if/when a real caller needs it — until then the current scope is sufficient and correct for every reachable call path." I checked the current call sites (
features/communities.ts,features/graph-enrichment.ts) and confirmed none of them drivelouvainCommunities/native Leiden withdirected,quality: 'cpm', custom edge weights/node sizes, an alternatecandidateStrategy,allowNewCommunity,fixedNodes, orpreserveLabels— the gate condition this issue sets for itself has not been met.Per this repo's engineering convention (no speculative features or hypothetical-future-requirement code without a driving need), and the issue's own explicit scoping, I'm not implementing any of the six sub-features now. Each one is a substantial algorithm port in its own right (seeded-RNG-exact replication for the candidate-strategy branches, a full CPM quality-function port, native/JS byte-for-byte parity verification across seeds per #1804's methodology) that would produce a large surface of untested-by-real-usage code.
No change made. Leaving this open as the tracking issue for when a real caller does need one of these knobs — the implementation plan in the issue body remains accurate and actionable at that point.
carlos-alm commentedon Aug 5, 2026
Re-checked as part of a
/fixerpass.Re-verified the self-gate condition against current
main:features/communities.tsstill only passesresolution,maxLevels,maxLocalPasses,refinementTheta,capacityGrowthFactortolouvainCommunities, andfeatures/graph-enrichment.tscalls it with no options object at all. No call site drivesdirected,quality: 'cpm', custom edge weights/node sizes, an alternatecandidateStrategy,allowNewCommunity,fixedNodes, orpreserveLabels.No change made — the gate condition this issue sets for itself remains unmet. Leaving open as the tracking issue for when a real caller needs one of these knobs.
carlos-alm commentedon Aug 7, 2026
Re-checked as part of a
/fixerpass.Re-verified the self-gate condition against current
main(post-#2313):features/communities.tsstill only passesresolution,maxLevels,maxLocalPasses,refinementTheta,capacityGrowthFactortolouvainCommunities, andfeatures/graph-enrichment.tsstill calls it with no options object at all (both of its two call sites, for the function-level and file-level graphs). No call site drivesdirected,quality: 'cpm', custom edge weights/node sizes, an alternatecandidateStrategy,allowNewCommunity,fixedNodes, orpreserveLabels.No change made — the gate condition this issue sets for itself remains unmet, per this repo's convention against speculative features with no driving caller. Leaving open as the tracking issue for when a real caller needs one of these knobs; the implementation plan in the issue body remains accurate and actionable at that point.
carlos-alm commentedon Aug 7, 2026
Re-checked as part of a
/fixerpass — re-verified again against currentmain:features/communities.tsstill only passesresolution,maxLevels,maxLocalPasses,refinementTheta,capacityGrowthFactor;features/graph-enrichment.ts's two call sites still pass no options object at all. The self-gate condition remains unmet (fourth consecutive/fixerpass reaching the identical conclusion).Applying the
blockedlabel (newly created — this repo had noblockedlabel at all, so/fixer's queue-exclusion filter for it has never actually excluded anything in any prior run) so this issue stops consuming a batch slot on every future/fixerrun while it remains self-gated. Filed #2324 to track the underlying gap. Remove the label whenever a real caller needs one of the LeidenOptions knobs described above — that's exactly the trigger condition this issue is waiting on.carlos-alm commentedon Aug 20, 2026
The gate in this issue was unsatisfiable by construction
Reopening the reasoning behind four consecutive
/fixerpasses (2026-08-02, 08-05, 08-07 ×2), each of which re-verified the same self-gate and reached the identical conclusion.The gate reads: "Only take this on if/when a real caller needs to drive native Leiden with one of these knobs."
A "real caller" has to pass the knob through
louvainCommunities— butLouvainOptionsexposes onlyresolution,maxLevels,maxLocalPasses,refinementTheta,capacityGrowthFactor. There is nodirected, noquality, no weight input. Adding the field is itself steps 1–5 of this issue's own plan. So a caller cannot come into existence before the fix, and the fix waits on the caller.Each pass verified the gate by grepping call sites — a check that can never return anything but "no", because the only thing that could change it is the work being gated. That is why four independent passes produced four identical comments. The
blockedlabel added in the fourth pass stopped the wasted batch slots but froze the loop rather than breaking it.To be fair to those passes: the gate is satisfiable, just never from code inspection — it needs a product decision, not a call-site survey. That mismatch is the actual defect, and it is why the wording is being replaced rather than re-verified a fifth time.
What was actually broken, independent of the gate
louvainCommunitieshands nativegraph.toEdgeArray(), which drops every edge attribute at the FFI boundary, and passes no node attributes at all. The JS reference resolves per-edge weight and per-node size from attributes. On a graph carrying either, the two engines optimize different weighted graphs and can return different partitions — silently, since nothing errors and both answers look plausible.Latent rather than live (no in-tree builder set
weight/size), but it fails quietly, so it is fixed in #2592: a capability check routes any graph native cannot represent to the JS reference.Weights: implemented, with native/JS parity
#2593 adds
leidenWeightedCommunities, so per-edge weights reach native Leiden. Byte-for-byte parity asserted across weighted bridges, weighted reciprocal edges, weighted self-loops, zero/NaN weights, and a weighted multi-level graph over 3 resolutions × 3 seeds. The attribute-to-number rule now has exactly one implementation shared by both engines, so they cannot drift apart on what a graph weighs.It also fixes a real bug found on the way:
buildTemporalGraphadvertises a graph "weighted by Jaccard similarity" but stored the score under ajaccardkey neither engine reads, so every weight-aware consumer saw a uniformly weighted graph and the whole co-change signal was discarded.Measurements — why the remaining knobs are not being ported
Rather than defer the "does a caller need it?" question again, each candidate was measured on this repo's own graph (1099 files, 23048 nodes, 49714 edges). Modularity is not comparable across different weightings or across directed/undirected — those are different objective functions — so the readout is directory purity: the size-weighted share of each community sitting in its modal directory, i.e. how well communities line up with how the codebase is actually organized.
Call-site multiplicity — premise false, nothing to weight.
idx_edges_content_unique(#2072) makes duplicate(source, target, kind, confidence, …)rows impossible in both engines. This repo has 10712callsrows for 10711 distinct pairs. Multiplicity is not merely discarded by the graph builders — it is never recorded. Filed as #2594.Resolution
confidenceweighting — measured, no value. Already onCallEdgeRowfor 22% of call edges, so it was the cheapest real weight available:Confidence clusters at 0.9–1.0 (78% of calls and 74% of imports are exactly 1.0), so it perturbs the graph without restructuring it.
Directed clustering — measured, degrades alignment. The JS reference already implements
directed: true, so this was measurable without doing the Rust port first:Directed clustering produces fewer, much larger, blurrier communities that align notably worse with the directory tree on both levels. The higher "quality" number is directed modularity — a different objective, not an improvement.
Caveat stated honestly: directory purity is a proxy. Directed communities may be capturing flow/layer structure that deliberately cuts across directories, which would be useful for a caller who wants that. But absent such a caller, and with the only available quality proxy pointing down, porting ~63 directed branches across
adapter.ts,modularity.tsandpartition.tsto Rust is not justified.CPM, alternate candidate strategies,
allowNewCommunity,fixedNodes,preserveLabels— no value case found.preserveLabelswas checked specifically against drift:analyzeDriftcompares communities to directory structure within a single run, not across commits, so stable IDs buy nothing there.Disposition
Closing as won't-do for the remainder, rather than leaving a permanently-
blockedissue that re-enters every queue. The body has been rewritten to record what shipped, what was measured, and the numbers — so the next person is not re-deriving this.The replacement trigger is a product decision, not a grep: a caller that wants flow-based or layer-based communities (directed), or one that needs small-community resolution below modularity's resolution limit (CPM). If either turns up, reopen — the implementation plan in the body is still accurate, and #2593 has already built the weight plumbing and the parity-test methodology the rest would follow.
fix(communities): defer to JS Leiden for graphs native cannot represe…
feat(communities): native Leiden reads per-edge weights (#2593)