2026-06-21 — Leiden clustering: built, measured, shelved as a grouping feature

Prompted by graphify.net (open-source knowledge-graph skill for AI coding assistants; Tree-sitter + NetworkX + Leiden). Asked what's worth borrowing for demarkus. Distilled to two ideas: (1) Leiden community detection over the link graph; (2) god-node / degree-vs-importance mismatch checks in soul-doctor. Decided to build (1) first. Another Claude session had independently flagged Leiden and pushed hard for measuring the real graph before committing — that diligence is what produced the verdict below.

What got built

client/graph/cluster.go + cluster_test.go — full Leiden (Traag/Waltman/van Eck 2019), from scratch, no deps. Lives in the graph package (the agent owns intelligence; the server stays dumb). Chose full Leiden over Louvain at the user's request; the distinguishing guarantee (every community internally connected) is asserted by TestCommunitiesAreConnected. Design choices worth remembering:

Directed link graph symmetrised to undirected-weighted (reciprocal links → weight 2). Modularity is an undirected quantity.
Deterministic-greedy refinement, not the paper's randomised θ-softmax merge — the agent republishes the report each crawl, so stable output for unchanged input beats the marginal quality of randomisation. Also makes it testable.
modularity() is a brute-force reference validated against hand-computed values (single edge: together Q=0, apart Q=−0.5; two triangles: split Q=0.5) so a factor-of-2 slip in the incremental gain can't hide.

Tests pass, pre-commit clean. Not committed (per the never-commit rule); staged for a keep/shelf decision.

The measurement (the actual deliverable)

Ran it on the live soul (mark_graph /index.md depth 5), 113 internal nodes / 163 edges, via a throwaway clusterprobe harness (since deleted):

leaves (out-degree 0) = 73%
max in-degree  = 4   (/plans/universe-library.md)
max out-degree = 42  (/index.md)
clustering coefficient = 0.16
Leiden → 6 communities, modularity = 0.61

Verdict — do NOT ship Leiden as a grouping/navigation primitive

Two findings kill the case at this scale/topology:

Modularity 0.61 is a star-topology artifact, not real community structure. The soul is hub-and-spoke: index.md fans out to 45 docs, journal/ to 42 dated leaves that link nowhere. A hub+leaves star scores high modularity by construction (all edges internal). So the 6 communities mostly re-derive the folder tree (journal/, plans/, demarkus-library/) — structure already maintained by hand via index hubs. High modularity, ~zero new information.
god-node-by-in-degree is wrong for this graph. Max in-degree is 4. The structurally important nodes are high-out-degree hubs (the indexes), not in-degree authorities. Community.GodNode (built as max in-degree) mislabels every star community — it's a tie-break artifact. In hub-and-spoke the hub is an out-degree hub. If this metric is kept anywhere, base it on out-degree.

The one real signal

Leiden split demarkus-library/ into reading-room (adr-0005 ↔ reading-room ↔ roadmap) vs web-sso (adr-0004 ↔ phase-1b ↔ roadmap) — genuine sub-topics created by reciprocal cross-references, not by folder. That's the "densely cross-referenced regions" case: real but narrow (one meshed subtree out of the whole soul).

Where it lands

Not a feature. The defensible use is a soul-doctor hygiene signal: taxonomy-drift = "docs that cross-reference densely but live in different folders → missing hub / mis-filing," plus the inverse. Structural, so embeddings can't produce it — that's the one thing Leiden earns here.
Topical "related docs" is the semantic/pgvector lane, not this.
Re-test at scale later: the knowledge system (world-a) is where density could make clustering pay off, but it's near-empty today.

Reusable lesson

When a strong, well-known algorithm gets suggested for a graph, measure the graph's own properties (degree distribution, leaf fraction, clustering coefficient) before building on it. "Good algorithm" ≠ "right problem for this data." Here the data is a tree wearing a graph's clothes; modularity rewards re-finding the tree.

Persistent graph plan: the client graph package and mark_graph this ran on
Plugin knowledge quality plan: soul-doctor, where the taxonomy-drift signal would land
Graph completeness plan: graph topology work this measurement informs

Graph: plugin-knowledge-quality