v0.2.18 — sdivi-rust v0.2.18 — Leiden no longer hangs on large sparse graphs

sdivi-rust v0.2.18 — Leiden no longer hangs on large sparse graphs

This release lands M28: two performance fixes to the recursive Leiden
implementation in sdivi-detection. Before M28, Pipeline::snapshot could
hang for minutes-to-hours on large sparse weakly-connected graphs (e.g. an
MFE shell with ~1800 files and ~700 import edges) because (1) every call to
refine_community allocated state for the entire graph regardless of how
few nodes were in the coarse community being refined, and (2) recursion
only stopped when an aggregation level produced literally zero merges, so
graphs that compressed by 1–3% per level recursed dozens of times paying
the full setup cost at each level.

After this release, refinement is O(|members| + induced_edges) per
coarse community, recursion stops once compression falls below a
configurable ratio, and a hard recursion-depth cap provides a
belt-and-suspenders safeguard. Snapshots that previously took minutes
complete in seconds.

snapshot_version stays at "1.0". No CLI flag, exit code, or existing
.sdivi/config.toml key changed.

Highlights

• M28 — Induced-subgraph refinement and recursion cutoff.
  • LeidenGraph::induced_subgraph(members) builds a per-community
    subgraph in O(|members| + induced_edges). refine_community uses
    it instead of walking the full graph on every call.
  • The recursive Leiden driver now exits early when an aggregation
    level would compress the graph by less than
    boundaries.leiden_min_compression_ratio (default 0.1).
  • A hard cap at boundaries.leiden_max_recursion_depth (default 32,
    enough for ~4 billion nodes) guards against pathological inputs.
  • Modularity quality stays inside the existing verify-leiden 1%
    tolerance band. Snapshot determinism is preserved bit-for-bit on the
    same repo state with the same seed.
• New [boundaries] config keys (additive, both optional):
  • leiden_min_compression_ratio: f64 (default 0.1, range [0.0, 1.0)).
  • leiden_max_recursion_depth: u32 (default 32, must be >= 1).
  • Out-of-range values produce ConfigError::InvalidValue (CLI exit 2).
• LeidenConfig / LeidenConfigInput gain matching fields so the
  pure-compute (sdivi-core) and WASM callers can tune the cutoffs
  without going through .sdivi/config.toml. WasmLeidenConfigInput
  exposes min_compression_ratio?: number and
  max_recursion_depth?: number to TypeScript.
• WASM edge-weight hardening. parse_wasm_edge_weights now rejects
  f64::INFINITY and f64::NEG_INFINITY in the same guard as NaN,
  closing a non-blocking finding from the M27 review. Two regression
  tests guard the boundary.

Impact on existing baselines

Modularity values for snapshots taken post-M28 may differ by up to ~1%
from snapshots taken pre-M28 on the same repo state. This is within the
existing verify-leiden 1% tolerance band — the algorithm is
mathematically equivalent; the numerical difference stems from the new
compression-ratio cutoff stopping recursion a level earlier on sparse
graphs. Trend analyses that span the M28 cutover should treat it as a
baseline reset for modularity-sensitive metrics.

coupling_delta, community_count_delta, and boundary_violation_rate
on the same snapshots are unaffected.

What did not change

• snapshot_version is still "1.0". v0.2.16 snapshots load and diff
  cleanly under v0.2.18.
• LeidenPartition JSON shape is unchanged. BoundarySpec YAML
  untouched.
• Public API is additive only: existing callers that omit the new
  LeidenConfigInput / WasmLeidenConfigInput fields receive the
  defaults (0.1 and 32) and behave identically to pre-M28 except
  for the early-exit behaviour described above.
• Snapshot atomic-write, retention, and exit-code contracts unchanged.
• Tree-sitter grammars, language adapters, and import resolution are
  untouched.

Install

# crates.io
cargo install sdivi-cli

# pre-built binary (Linux x86_64 example)
curl -Lo sdivi https://github.com/GeoffGodwin/sdivi-rust/releases/download/v0.2.18/sdivi-x86_64-unknown-linux-gnu
chmod +x sdivi && mv sdivi ~/.local/bin/

# WASM / npm
npm install @geoffgodwin/sdivi-wasm@0.2.18

Documentation

• Migration notes: https://github.com/GeoffGodwin/sdivi-rust/blob/main/MIGRATION_NOTES.md
• CHANGELOG: https://github.com/GeoffGodwin/sdivi-rust/blob/main/CHANGELOG.md

Released under Apache 2.0.

What's Changed

• Milestone/m28 by @GeoffGodwin in #5

Full Changelog: v0.2.16...v0.2.18