Skip to content

Full/hierarchical Leiden: singleton local moves + multi-level aggregation #6

Description

@ronaldmannak

Motivation

The current LeidenCommunityDetector is a deliberately simplified single-level Leiden: local moving compares only stay/neighbor moves (never the empty-singleton candidate), and there's no multi-level aggregation. This was documented as a non-goal in the initial port (see the in-code note in Leiden.swift). Implementing it properly improves partition quality on connected graphs.

Scope

  • Add the empty-singleton move to local-moving scoring (score Σ_tot = 0), so a connected over-merge can split back out when it improves modularity. Requires supporting community ids beyond 0..<n (e.g. dictionary-backed Σ_tot).
  • Add multi-level aggregation: collapse communities into super-nodes and repeat local moving until modularity stops improving (classic Louvain/Leiden levels).
  • Preserve determinism (stable ordering, sorted iteration) and the existing LeidenConfig knobs.
  • Add a quality/regression test (e.g. a known graph where multi-level finds a better partition than single-level), plus the existing determinism tests must still pass.

Files (parallel-safe)

Sources/GraphRAG/Graph/Leiden.swift, Tests/GraphRAGTests/LightRAGTests.swift (or a new LeidenTests.swift). Isolated from LightRAG/retrieval work.

Acceptance criteria

  • Deterministic across runs; leidenIsDeterministic and disconnected-cluster tests still pass.
  • A test demonstrates multi-level/singleton refinement improving modularity vs. the single-level result.
  • Modularity is non-decreasing across levels.
  • CI green.

Note: best validated with the example/benchmark from the runnable-example issue. Context: follow-up to PR #2.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions