GraphRAG: Community Detection and the Modularity of Knowledge

From a path to a partition

Multi-hop retrieval closed on a sentence that pointed past itself. Having traced the relation “retrievable-from” from query to bridge to answer, it observed that once iterative retrieval has traversed those edges enough times, the relation has drawn a graph over the whole corpus, “and the question shifts from finding a single path to understanding that graph’s global structure — its dense communities of mutually-retrievable filings.”

This is that shift. Every topic in this layer so far has answered a local question: which documents are near this query, which subset covers it, what path reaches this answer. A global, sensemaking question is different in kind. Ask what are the dominant themes across this entire corpus of filings? and no single document holds the answer, no single retrieval surfaces it, and no path traverses to it — because the answer is not a document at all. It is a property of how the corpus partitions into communities. The object of study moves from a trajectory through the graph to the graph’s partition, and the mathematics is the mathematics of that partition: when does a good partition exist, when can we find it, and what are the fundamental limits.

This is the architecture of GraphRAG (Edge et al. 2024). Rather than retrieve passages for each query, it builds an entity–relationship graph from the corpus once, partitions it into a hierarchy of communities, summarizes each community, and answers a global query by map-reducing over those summaries — each summary producing a partial answer, the partials reduced into a whole. The community detection is the load-bearing step, and it is the one with genuine mathematics. We will make five movements precise on the same finance geometry the rest of the arc used: what scores a partition (modularity), how to find the optimal one (the spectral relaxation), what scale it cannot see (the resolution limit), when thematic structure exists to be found at all (the stochastic block model’s detectability threshold), and the heuristics that do the work in practice (Louvain and Leiden).

The entity graph and modularity

Fix the object. The entity co-occurrence graph $G = (V, E, A)$ has one node per entity — here a company — and a weight $A_{ij} \ge 0$ on the edge between $i$ and $j$ measuring how strongly they co-occur. We build it from the dual-encoder geometry the arc has used throughout: each company has a unit direction on the sphere, and the edge weight is the sharpened cosine between two companies, so companies in the same sector — near on the sphere — are strongly connected and companies in different sectors are nearly unlinked. The sectors are the planted communities, and the question is whether the graph’s structure reveals them.

Write $k_i = \sum_j A_{ij}$ for the weighted degree of node $i$ and $2m = \sum_{ij} A_{ij}$ for twice the total edge weight. A partition assigns each node $i$ a community label $c_i$. We need a number that says how good a partition is, and the idea — due to Newman and Girvan — is to compare the within-community edge weight to what a degree-preserving random graph would have.

The configuration-model null is the whole idea. A partition that simply groups high-degree nodes together collects a lot of within-community edge weight, but those nodes would be linked even at random; modularity subtracts that baseline, so it rewards only the edge weight a partition captures beyond what degrees alone explain. On the finance entity graph the planted sectors score $Q = 0.778$ — the Panel A readout — while a random relabeling of the same nodes scores $-0.04$. The structure is real, and modularity sees it.

What modularity does not hand us is the optimal partition. Searching all partitions is hopeless; we need a way to find the one that maximizes $Q$, and the first move is a beautiful relaxation.

The spectral relaxation

Restrict to a bipartition — two communities — and encode it with a sign vector $s \in \{\pm 1\}^n$, with $s_i = +1$ for group one and $s_i = -1$ for group two. Then $\delta(c_i, c_j) = \tfrac{1}{2}(s_i s_j + 1)$, and substituting into $Q$ something clean happens. Define the modularity matrix

$$B_{ij} \;=\; A_{ij} - \frac{k_i k_j}{2m}, \qquad B = A - \frac{\mathbf{k}\mathbf{k}^\top}{2m}.$$

Every row of $B$ sums to zero, because $\sum_j B_{ij} = k_i - k_i \cdot \tfrac{2m}{2m} = 0$. That is exactly what kills the constant $\tfrac{1}{2}$ term when we substitute, leaving

$$Q \;=\; \frac{1}{4m}\, \mathbf{s}^\top B\, \mathbf{s}.$$

Maximizing this over $s \in \{\pm 1\}^n$ is the integer problem we cannot solve directly. So we relax: allow $s$ to be any real vector on the sphere $\lVert s \rVert^2 = n$. Then $Q$ is a Rayleigh quotient, and the maximizer is the eigenvector of $B$ with the largest eigenvalue.

The proof is the Rayleigh-quotient argument: on the sphere, $s^\top B s$ is maximized by the top eigenvector, because expanding $s$ in $B$‘s orthonormal eigenbasis (it is real-symmetric, so the spectral theorem applies) puts all the weight on the largest eigenvalue. Two honest caveats live right here. First, $B$ is indefinite — it has negative eigenvalues — so “largest algebraic” is not “largest magnitude”; a large negative eigenvalue is the wrong one to round. Second, the rounded integer partition is not the true optimum — rounding loses the relaxation’s guarantee — and finding the true optimum is genuinely hard, which Movement 5 confronts. But the indivisibility test is exact and useful: a single clique, which has no community structure, has $\lambda_1(B) \le 0$ and is correctly reported indivisible. On a small graph of two cliques joined by one edge, the spectral sign vector matches the brute-force modularity-optimal bipartition exactly (both find $Q = 0.42$), the collapse anchor that pins the method.

This is the natural place to meet the lab. Panel A is the finance entity graph with a resolution slider; Panel B is the detectability phase diagram of Movement 4; Panel C is the resolution limit and the Louvain/Leiden contrast of Movements 3 and 5.

A · entity graph + γB · SBM detectabilityC · resolution & Louvain/Leiden

resolution γ = 1.00 → 5 communities

modularity Q (at this γ)

0.778

communities found

5

Q(planted sectors), γ=1

0.778

Q(random partition)

-0.043

The 25 nodes are companies; edges are co-occurrence weights, and the 5 sectors are the planted communities. Modularity scores a partition against the degree-preserving null: the planted sectors score 0.778 against a random partition's -0.043. The resolution parameter γ tunes the scale: at low γ two sectors merge (4 communities), a broad plateau recovers the 5 sectors, and at high γ the graph fragments toward singletons (10 → 25). No single γ is canonical — the resolution limit is intrinsic, not a knob to be tuned away.

Finance entity graph on the shared dense-retrieval vMF cloud (seed 7): 25 companies in 5 sectors, edge weight = the sharpened cosine of the company directions, so the sectors are the planted communities. The SBM panel is the canonical two-block generative model that says when such structure is detectable at all; the ring-of-cliques and the Louvain/Leiden witness are dedicated toy graphs. Every modularity, overlap, label, and Q is mirrored from graphrag_community_detection.py (viz_constants()); the lab recomputes only the Kesten–Stigum parabola, the SNR, and √(2m) in closed form.

The resolution limit

Modularity has a flaw that is not a bug to be patched but a property to be understood, and it is the load-bearing caveat of the whole topic. The $1/2m$ in the definition is a global normalization — it depends on the total size of the graph — and that couples the score of a small community to the size of the entire network. The consequence, proved by Fortunato and Barthélemy, is that modularity maximization cannot resolve communities below a scale set by the whole graph.

The cleanest witness is a ring of cliques: $n_c$ cliques of size $s$, each pair of adjacent cliques joined by a single edge, arranged in a ring. Each clique is unambiguously a community. Yet for the partition that puts each clique in its own community, compare its modularity to the partition that merges adjacent cliques in pairs.

The notebook makes the contrast concrete. On a ring of $30$ cliques of size $5$, where $\sqrt{2m} \approx 25.7$ dwarfs each clique’s internal edge count, the pairs-merged partition scores $Q = 0.888$ against the natural partition’s $0.876$ — so the optimum merges, and Louvain (which maximizes modularity) finds only $15$ communities, not $30$. On a small ring of $6$ cliques the same comparison flips, $0.742$ against $0.621$: the cliques are resolved. Panel C’s resolution view is exactly these two comparisons. Raising $\gamma$ on the large ring un-merges the cliques — $\gamma$ shrinks the resolvable scale — but at the price of fragmenting larger communities elsewhere, which is why Panel A’s slider, pushed past the plateau, shatters the sectors into singletons. There is no canonical $\gamma$; the limit is intrinsic to single-scale modularity.

The stochastic block model and the detectability transition

The resolution limit asks whether modularity can find a community of a given size. The deeper question is whether the community structure is there to be found at all — and it has a sharp, surprising answer that earns this topic its place in the information-theory layer. We need a generative model of a graph with planted communities.

The affinities $c_{\text{in}}$ and $c_{\text{out}}$ are the signal: when $c_{\text{in}} \gg c_{\text{out}}$ the blocks are assortative and obvious, and when $c_{\text{in}} = c_{\text{out}}$ the graph is plain Erdős– Rényi with no community structure at all. Between them lies a phase transition — and it is not a gradual fade.

Read that converse carefully, because it is the heart of the topic. It is not a statement that our particular algorithm is too weak. It is a statement that the information is not present: below the threshold, the graph that the SBM generated carries no recoverable trace of which nodes belonged together. This is the exact shape of the limit the noisy-channel topic met in Fano — an entropy lower bound below which no decoder can succeed — transposed from channel decoding to community detection. The community-detection world has a recovery threshold, and Kesten–Stigum is its converse: an information-theoretic limit on what the graph makes knowable, not a limitation of any one method.

We demonstrate it rather than reprove it (the proof is a multi-paper research program). The notebook samples SBMs on both sides of the parabola at $n = 3000$ and recovers the partition from the most extreme eigenvector of the modularity matrix. Above the line, at $c_{\text{in}} = 10$, $c_{\text{out}} = 1$ (signal-to-noise $3.68$), recovery overlaps the truth at $0.93$. Below the line, at $c_{\text{in}} = 6$, $c_{\text{out}} = 4$ (signal-to-noise $0.20$), recovery overlaps at $0.01$ — chance. Panel B is this phase diagram: the Kesten–Stigum parabola drawn in closed form, the measured overlap heatmap riding its boundary, and an inset graph whose blocks line up with the truth above the line and scatter into noise below it. Two honest notes qualify the picture. At finite $n$ the transition is smeared, not the asymptotic discontinuity, so the headline is the clear above/below contrast and not the exact crossing. And the clean coincidence of the information-theoretic and the efficient-algorithm thresholds holds for two blocks; with four or more, a hard phase opens where detection is possible in principle but no known efficient algorithm achieves it. We show the two-block case and name the gap.

GraphRAG, Louvain, and Leiden

The spectral relaxation handles a bipartition and recurses; in practice the workhorses are different, and the reason is one more piece of honesty.

This is the same hardness that context selection escaped by having a submodular objective with a greedy $1 - 1/e$ certificate. Modularity has no such structure, so its greedy heuristics carry no certificate — they are fast and good in practice, and that is all the theory promises. Louvain (Blondel et al. 2008) runs two phases, iterated. In local moving, each node is, in turn, removed from its community and rejoined to the neighboring community of greatest modularity gain — a gain available in closed form, $\Delta Q$ a function of the node’s weight into the target community, the community’s total degree, and the node’s own degree. In aggregation, each community collapses to a super-node and the process repeats on the smaller graph. The aggregation preserves modularity exactly, so the recursion is sound, and it produces a hierarchy of partitions, fine to coarse — precisely the dendrogram GraphRAG summarizes at multiple levels.

Louvain has a defect that Leiden was built to fix, and it is the clean Panel C demonstration.

The witness is small and exact. Two triangles with no edge between them, labeled one community: it is disconnected, yet no single node wants to leave — each triangle is internally cohesive and no node is more attracted elsewhere — so it is a Louvain local optimum that local moving cannot break. Leiden’s refinement splits it into its connected pieces. Panel C’s connectivity view draws exactly this: the Louvain partition with its disconnected community flagged, beside the Leiden partition where every community is connected. The honest framing matters — run from singletons, Louvain recovers the correct partition on this graph; it is not broken generically. The guarantee is what differs, and for a knowledge graph whose communities become retrievable summaries, a community that is secretly two disconnected halves is a summary of two unrelated things.

With the heuristics in hand, the GraphRAG pipeline is now fully specified mathematically. Extract the entity graph; run Leiden to get a hierarchy of communities; summarize each community at each level; answer a global query by map-reducing over the summaries. The modularity of knowledge is literal: a corpus decomposes into themes worth summarizing exactly when its entity graph has high modularity, the resolvable scale is coarse enough to keep genuine themes intact, and — the deepest condition — the block signal clears Kesten–Stigum. Below that threshold there is no thematic decomposition to summarize, and GraphRAG has nothing to offer over flat retrieval, because the structure it would summarize is not there.

What community detection trades, in one line

Local retrieval finds a path; global sensemaking needs the partition — and the partition exists, is findable, and is summarizable exactly when modularity is high, the resolvable scale is coarse enough, and the block signal clears the Kesten–Stigum threshold. Three limits, one for each pillar: NP-hardness forces heuristics, the resolution limit caps the scale they can see, and detectability decides whether there is anything to see at all.