Skip to content

v0.2.50 — sdivi-rust v0.2.50 — Fix Leiden non-termination on pathological graphs

Choose a tag to compare

View all tags
@GeoffGodwin GeoffGodwin released this 03 Jun 17:00
· 3 commits to main since this release
v0.2.50
a2eb0d0

sdivi-rust v0.2.50 — Fix Leiden non-termination on pathological graphs

A correctness/reliability release (M49) that eliminates a non-termination path in
the native Leiden implementation. Certain small graphs with certain seeds could
make run_leiden — and therefore Pipeline::snapshot / detect_boundaries —
run for many minutes on inputs as small as 8 nodes. This is fixed, and the
regression is guarded so it cannot silently return.

snapshot_version stays "1.0". No public-API or config change. One caveat:
the fix changes the RNG draw order, so some inputs produce different — but
deterministic and quality-preserving — cluster assignments (see "Impact" below).

Highlights

  • Leiden exponential-blowup fix (M49.2). leiden_recursive previously descended
    into the aggregated graph on every outer-loop iteration in which local moves
    fired, compounding to O(max_iterations^depth) work — on the order of 100^8 for
    an 8-node graph. It is now restructured to match Traag et al. 2019 Algorithm 1:
    local moves run to convergence at each level, then the aggregate is descended into
    at most once per invocation, bounding total work to
    O(max_iterations × n × max_recursion_depth). The minimal reproducer found by
    property testing (a K₁,₅ star, n=6, seed=0) now completes instantly.
  • The hang is now caught in seconds, not 30 minutes (M49.1). proptest's
    fork + timeout features are enabled for the sdivi-detection refinement
    proptests with a per-case timeout, so any future non-terminating case fails fast
    with its minimized input instead of hanging the CI runner to its job timeout. The
    captured case is committed as a regression and guarded by a deterministic
    termination test.

Impact on existing baselines

The category contract, snapshot schema, and config are all unchanged. The only
observable change is in community/cluster assignments for a subset of inputs:

  • Inputs that previously converged in a single local-move sweep are unaffected.
  • Inputs that required multiple sweeps may produce different cluster assignments
    than pre-M49.2 — deterministic for a fixed seed, and within the verify-leiden
    quality tolerance (modularity within 1%, community count within ±10%).
  • If you diff snapshots across the upgrade, re-baseline boundary/cluster fields.
    See MIGRATION_NOTES.md for the full note.

What did not change

  • snapshot_version is still "1.0". Snapshot JSON, pattern_metrics,
    DivergenceSummary, and the 19-category contract are unchanged.
  • No public-API change, no new .sdivi/config.toml keys.
  • Determinism contract holds: same repo state + same seed ⇒ bit-identical Snapshot
    (a different-but-stable output than pre-M49.2 for the affected inputs).
  • WASM dependency invariant (Rule 21) holds; the .wasm stays size-optimised (~1.53 MB).

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.50/sdivi-x86_64-unknown-linux-gnu
chmod +x sdivi && mv sdivi ~/.local/bin/

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

Documentation

Released under Apache 2.0.

Full Changelog: v0.2.48...v0.2.50

Assets 7
Loading