Research: how & why Graphify uses Leiden community detection

TL;DR

Companion to #35 (Graphify's LLM usage). This documents, with source-pinned evidence, how and why Graphify uses Leiden community detection — the cluster step that the project's marketing describes as "Leiden community detection … that does not require embeddings or a vector database."

The short version:

Graphify runs Leiden (graspologic, with a Louvain fallback) over the whole knowledge graph to partition it into communities = subsystems / neighborhoods. It stamps a community id onto every node, then uses those communities as the mesoscale backbone for navigation (--wiki), agent retrieval (the get_community MCP tool), reporting, and visualization grouping. Communities are advisory topology, computed deterministically and kept stable across incremental re-runs; an LLM only enters afterward to name each community.

Analyzed at Graphify commit 1bb30fc (v0.8.38, 2026-06-11). All line numbers are pinned to that commit. (Relevant to us because ts-knowledge-graph has no equivalent mesoscale layer — see §6.)

---

Why this exists at all (the conceptual role)

Graphify graphs are large and multi-modal (code AST nodes + doc/paper/image concept nodes in one graph). Between "the whole graph" (too big to show or hand to an agent) and "a single node" (too small), there is a missing middle. Communities are that middle — coherent subsystems you can name, render as a region, or retrieve as one chunk. Almost everything user-facing in Graphify (wiki, server, report, visualization) is built on this mesoscale layer.

Where it lives

File	Role
graphify/cluster.py	The algorithm — Leiden/Louvain + splitting + cohesion + stable-id remap
graphify/export.py	Writes the community id onto every node (the backbone)
graphify/serve.py	MCP server — exposes get_community + god_nodes retrieval tools
graphify/wiki.py	--wiki — one article per community + cross-community links + god-node pages
graphify/report.py	GRAPH_REPORT.md — subsystems + cohesion + god nodes
graphify/callflow_html.py	Visualization grouped/colored by community
graphify/analyze.py	god_nodes (hub centrality) + surprising_connections (cross-community bridges)
graphify/llm.py	generate_community_labels — names each community (the only LLM touch)
graphify/watch.py	Incremental re-cluster + remap ids to previous run

---

1. The algorithm — cluster.py

Community detection runs on a NetworkX graph and returns {community_id: [node_ids]}, IDs ordered by size (0 = largest). It is modality-agnostic graph topology, so it applies equally to a pure-code graph.

Engine (cluster.py#L22-L77):

# graphify/cluster.py:47
try:
    from graspologic.partition import leiden          # best quality
    ...
    kwargs["random_seed"] = 42                          # deterministic
    kwargs["trials"] = 1
    kwargs["resolution"] = resolution                   # >1 = more/smaller, <1 = fewer/larger
    result = leiden(stable, **kwargs)
    return result
except ImportError:
    pass
# Fallback: networkx Louvain (seed=42, threshold=1e-4)
communities = nx.community.louvain_communities(stable, **kwargs)

Determinism is taken seriously: nodes/edges are inserted in sorted order before partitioning, the seed is fixed, and the final list is re-indexed by (-size, tuple(sorted(nodes))) so an identical grouping always yields identical IDs (cluster.py#L181-L188).

cluster() refinements (cluster.py#L86-L188) — these are the parts that make raw Leiden usable on real codebases:

• DiGraph → undirected before partitioning (Leiden/Louvain need undirected input).
• Hub exclusion (exclude_hubs_percentile): high-degree super-hubs are pulled out before partitioning and reattached afterward by majority-vote neighbour community, so a utility/staging hub doesn't fuse unrelated subsystems (#L114-L159).
• Isolates each become their own single-node community.
• Oversized-community split: any community larger than 25% of the graph (min 10 nodes) is re-partitioned with a second Leiden pass (#L161-L168, thresholds at #L80).
• Low-cohesion re-split: a community of ≥50 nodes with intra-edge density < 0.05 is re-split — explicitly to defeat "a doc hub like CLAUDE.md bridges everything into one blob" (#L170-L179).

Cohesion score = actual / maximum-possible intra-community edges (cluster.py#L209-L217) — used both as the re-split trigger and as a reported quality metric.

Stable IDs across runs — remap_communities_to_previous greedily matches new communities to a previous assignment by overlap size, so neighborhood IDs don't churn on re-extraction (cluster.py#L224-L272). This is what makes communities safe to reference from a persisted wiki/report.

2. The community id is stamped onto every node

cluster() runs during the build/cluster commands (__main__.py#L3207, #L4447), and the result is written back onto each node so every downstream consumer reads it as a plain property (export.py#L516):

# graphify/export.py:516
node["community"] = node_community.get(node["id"])

The viz export additionally writes a human label per node (export.py#L733-L734):

"community": cid,
"community_name": sanitize_label((community_labels or {}).get(cid, f"Community {cid}")),

So "community" is not an internal artifact — it is a first-class node attribute in the serialized graph.

3. What the communities are for (the consumers)

a. Agent retrieval — the MCP server exposes communities as a tool

serve.py reconstructs the community map from the community node property (serve.py#L45-L48) and exposes two tools to the AI assistant (serve.py#L609-L618):

name="get_community",
description="Get all nodes in a community by community ID.",
...
name="god_nodes",

This is the operational core of the "traverse structure instead of re-reading files" / token-economy claim: an agent fetches a whole named subsystem in one call instead of hopping node-by-node or re-reading source.

b. Navigation — the wiki is one article per community

wiki.py is literally "index.md + one article per community + god node articles" (wiki.py#L2). Each community article lists members and a cross-community links section (_cross_community_links, wiki.py#L26) showing how this subsystem connects to others; god nodes get their own pages tagged with their community (wiki.py#L105-L110).

c. Architecture signals — analyze.py

• god_nodes (analyze.py#L100-L121): the top-N highest-degree real entities (file/concept/JSON-key hub nodes excluded) — "the core abstractions."
• surprising_connections (analyze.py#L124-L153): for single-source corpora it surfaces cross-community bridge edges (edge betweenness) — couplings that aren't obvious from the file layout.

d. Legibility — the LLM names each community (and only this)

generate_community_labels / label_communities / _community_label_lines (llm.py#L1983-L2142) send the model node-label samples per community (god nodes first) and get back a name like "Authentication." Note: the clustering is pure topology; the LLM is a thin post-hoc labeler — and per #35 it receives only symbol labels, never code bodies.

e. Reporting & visualization

• report.py emits GRAPH_REPORT.md with per-community sections, cohesion, and god nodes.
• callflow_html.py / export.py group and color the rendered graph by community — the single biggest legibility win for a force-directed view.

f. Incremental stability — watch.py

On a re-run, watch.py re-clusters then remaps to the previous assignment so IDs stay put (watch.py#L660-L663):

communities = cluster(G)
previous_node_community = _node_community_map(existing_graph_data)
if previous_node_community:
    communities = remap_communities_to_previous(communities, previous_node_community)

---

4. Why Graphify uses it (rationale, in one paragraph)

Leiden gives Graphify a deterministic, embedding-free way to decompose a big heterogeneous graph into nameable subsystems. That single primitive simultaneously powers (1) token-economy retrieval — hand an agent a cohesive neighborhood instead of files; (2) navigation — a wiki page per subsystem; (3) comprehension — community-colored visualization and an architecture report; and (4) architecture signals — god nodes (core abstractions) and cross-community bridges (non-obvious couplings). It is the connective tissue between the raw graph and every human/agent-facing surface — and notably it needs no vector DB, which is a deliberate positioning choice.

5. What it deliberately does not do (honest scoping)

• It does not participate in extraction or in any exact lookup — it is a derived, advisory layer computed after the graph exists.
• Leiden is stochastic; the value comes only after the determinism + stability machinery (seeding, total-order tiebreaks, remap_communities_to_previous) is paid for.
• Communities are heuristic boundaries — useful for orientation, not authoritative module definitions.
• It pulls in networkx (+ optional graspologic) — a non-trivial dependency.

---

6. Does this transfer to ts-knowledge-graph? (condensed)

We have no mesoscale layer today. Every query is either micro (per-symbol: whoCalls, blastRadius, references, neighborhood, deadExports — src/query/graph_query.ts) or global ranking (hotspots, costRanking). Community detection is the missing middle: "what are the de-facto subsystems, and do they match the folders?"

Candidate use-cases, ranked, with whether they're possible without clustering:

#	Use-case	Possible today?	Verdict
1	Color/group the web viz by subsystem	viz exists, kind-filters only	Enhances — best value/risk
2	modules command: coupling-vs-folders divergence (tangled modules, misplaced files, low-cohesion dirs, hidden subsystems)	❌ No query expresses it	New — the genuinely novel capability
3	Cross-community bridge edges as an agent risk signal (complements blast-radius count with boundary-crossing)	partial (blastRadius = reachable count)	New signal
4	Per-subsystem god node + cohesion report (onboarding/architecture)	partial (hotspots is global)	Mostly enhances
5	Community as a bounded retrieval chunk for /code-graph-optimize	partial (neighborhood is 1-hop, explodes on hubs)	Enhances — smallest marginal win

Costs / cautions for us: a new graph-lib dependency (we are lean — 5 deps, Kùzu/Cypher); stochasticity vs. our position-stable-id ethos (we'd inherit the stability machinery); and labeling without an LLM — we just established (#35) that this project is LLM-free, so clusters should be labeled heuristically (dominant directory, most-central symbol, top identifier token) rather than via a model. Keep any clustering strictly advisory — it must never touch the exact queries (deadExports/blastRadius stay precise).

Suggested first step if pursued: ship #1 (viz coloring) as the low-risk win, then #2 (modules/divergence report) as the flagship new capability.

---

Appendix — evidence index (all @ 1bb30fc)

Claim	Source
Leiden + Louvain fallback, deterministic	cluster.py#L22-L77
cluster() refinements (hub-exclude, split, re-split)	cluster.py#L86-L188
Cohesion score	cluster.py#L209-L217
Stable-id remap	cluster.py#L224-L272
community written onto every node	export.py#L516
get_community + god_nodes MCP tools	serve.py#L609-L618
Wiki = one article per community	wiki.py#L2, #L26-L110
God nodes + surprising (bridge) connections	analyze.py#L100-L153
LLM community labeling (labels only)	llm.py#L1983-L2142
Cluster call sites	__main__.py#L3207, #L4447
Incremental re-cluster + remap	watch.py#L660-L663

Analysis produced by reading Graphify @ 1bb30fcc567a72280f4dc1763947140268f101c5 (v0.8.38). No code in this repo was modified. Companion to #35.

Start with the pinned Graphify commit, especially graphify/cluster.py, export.py, watch.py, wiki.py, serve.py, report.py, and llm.py, then inspect the corresponding graph implementation in codespine. Document whether codespine has an equivalent community layer and which Graphify behaviors could transfer; the research is done when the comparison and rationale are recorded with source-pinned evidence.