Research: how & why Graphify uses Leiden community detection

Bắt đầu với commit được ghim của Graphify, đặc biệt là graphify/cluster.py, export.py, watch.py, wiki.py, serve.py, report.py và llm.py, sau đó kiểm tra phần triển khai đồ thị tương ứng trong codespine. Ghi lại liệu codespine có một lớp cộng đồng tương đương hay không và những hành vi nào của Graphify có thể được chuyển sang; nghiên cứu được hoàn tất khi phần so sánh và lý do được ghi lại kèm bằng chứng được ghim theo mã nguồn.

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.