Retrieval-Augmented Generation (RAG) enhances large language models by incorporating external knowledge. However, existing vector-based methods often fail on global sensemaking tasks that require reasoning across many documents. GraphRAG addresses this by organizing documents into a knowledge graph with hierarchical communities that can be recursively summarized. Current GraphRAG approaches rely on Leiden clustering for community detection, but we prove that on sparse knowledge graphs, where average degree is constant and most nodes have low degree, modularity optimization admits exponentially many near-optimal partitions, making Leiden-based communities inherently non-reproducible. To address this, we propose replacing Leiden with k-core decomposition, which yields a deterministic, density-aware hierarchy in linear time. We introduce a set of lightweight heuristics that leverage the k-core hierarchy to construct size-bounded, connectivity-preserving communities for retrieval and summarization, along with a token-budget-aware sampling strategy that reduces LLM costs. We evaluate our methods on real-world datasets including financial earnings transcripts, news articles, and podcasts, using three LLMs for answer generation and five independent LLM judges for head-to-head evaluation. Across datasets and models, our approach consistently improves answer comprehensiveness and diversity while reducing token usage, demonstrating that k-core-based GraphRAG is an effective and efficient framework for global sensemaking.
Alex: Welcome to another episode of ResearchPod. Sam, what paper are we diving into today?
Sam: This is about a paper called "Core-based Hierarchies for Efficient GraphRAG" by Jakir Hossain and Ahmet Erdem Sarıyüce from the University at Buffalo. It tackles a key issue in systems that help large language models reason across many documents at once. The central puzzle is why the popular GraphRAG method, which builds hierarchies in knowledge graphs to summarize big sets of texts, keeps giving unreliable results—specifically, because its clustering step fails reproducibly on real-world graphs.
Alex: So this paper is basically asking why GraphRAG's Leiden clustering doesn't work consistently on actual knowledge graphs from things like financial transcripts?
Sam: Yes, exactly. First, a bit of background. Large language models handle questions from their training data well, but for tough queries needing info from hundreds of documents—like spotting common supply chain strategies across earnings call transcripts—they need external help. That's where Retrieval-Augmented Generation, or RAG, comes in: it grabs relevant text bits and feeds them to the model. But standard RAG, which searches by word similarity, struggles with global sensemaking tasks that weave themes from everywhere in a big pile of documents.
Alex: Right, so vector-based RAG works for simple facts in one spot, but falls short when connecting dots across a whole corpus. And GraphRAG tries to fix that by turning documents into a graph?
Sam: Precisely. GraphRAG builds a knowledge graph from the texts—nodes are key entities or claims, edges are relationships like "company A supplies part B." It groups these into hierarchical communities, summarizing smaller groups first and rolling up to bigger ones for the big picture. Leiden clustering finds these groups, but on sparse graphs—where most nodes have few connections, like in news or earnings data—it produces unpredictable hierarchies that fragment or merge inconsistently.
Alex: Unpredictable how? Like, the same graph gives different clusters each run?
Sam: That's the core problem. Leiden's modularity optimization scores good groupings, but on sparse graphs it allows exponentially many near-optimal splits. Tiny changes in starting point lead to different structures. This instability means summaries don't reliably capture themes. Their fix: k-core decomposition, which peels the graph like an onion, layer by layer. It removes loosely connected nodes to reveal denser cores of tightly linked topics—all in a fixed, fast way every time.
Alex: Okay, so it's about making the hierarchy stable and efficient for real graphs.
Sam: Imagine peeling an onion: start from the outside, remove loose outer layers until the dense center remains. In a graph, repeatedly remove nodes with fewer than k connections—and their edges—until every remaining node has at least k solid links. This builds natural layers, with innermost ones as tight groups of well-connected nodes, like core topics.
Alex: That onion idea clicks—denser inside means central ideas stay together. But what about nodes peeled off early? Don't they get lost?
Sam: Good question. Residual-aware k-core Hierarchy, or RkH, handles "residual" sparse nodes by separating them from dense cores at each layer. It splits oversized groups from high-degree seeds to keep connections intact. Single leftovers group by 2-hop links—like friends of friends—or attach to nearby clusters, forming a stable tree hierarchy without random splits.
Alex: Right, so peeling gives nested levels, and RkH cleans up edges without messing up cores. Does this respect token limits for language models?
Sam: Yes—it sets cluster sizes by estimating tokens per node for efficient summaries. Unlike Leiden's random outputs, this runs in linear time, always the same way. It's more robust on sparse graphs, where low-degree nodes cause modularity degeneracy—many near-equal groupings.
Alex: Huh, so the math shows why sparse graphs fool Leiden, but k-cores ignore that noise. That seems like a clear win for consistency.
Sam: Precisely. The paper tests it across datasets with language models judging summaries head-to-head. RkH hierarchies yield steadier, more complete retrieval—about twice as reliable in preserving key themes without fragmentation.
Alex: You mentioned handling peeled-off residuals carefully. How does it deal with tiny groups in sparse graphs without fragmenting everything?
Sam: Peeling often leaves tiny groups, like pairs of loosely connected nodes. These get low summary scores and ignored, hurting the picture. The cleanup merges them into the nearest bigger cluster via strong links—like attaching small puzzle pieces—or uses rules for 2-hop pairs and residuals to keep the hierarchy tight.
Alex: So it's tidying up after peeling to avoid losing info. And it respects token limits?
Sam: Exactly. To cut token costs from overlapping info, it ranks edges by endpoint connections, picking prominent ones first. Round-Robin Token-Constrained Selection shares the budget across communities from outer to inner shells for balanced coverage.
Alex: Huh, prioritizing busy edges and sharing evenly. How did they test improvements over Leiden?
Sam: Head-to-head on podcast transcripts, news, and earnings calls—using post-training-cutoff data. Three models generated answers from hierarchies, judged blindly by five others on thoroughness. K-core setups, especially with leaf-level merges, beat Leiden in about three-quarters of matchups.
Alex: Solid edge in consistency, with few ties on tougher data.
Sam: Yes. Wilcoxon tests confirm wins aren't luck, with low p-values. Leaf-level clusters beat higher ones by 5 to 10 percentage points on average. Stronger models narrow the gap slightly, but k-cores still edge out Leiden systematically on sparse graphs.
Alex: Token savings stand out—fewer communities, less text, yet performance holds. How big a deal practically?
Sam: Substantial for cost. Heuristics cut communities by 30 to 40 percent and token coverage to 55 to 60 percent of source text, matching or topping Leiden. RRTC preserves quality even trimming edges.
Alex: Efficiency without much loss. Any spots where it falls short?
Sam: The paper notes heuristics work well here but could lag on triangle-rich graphs—tight loops of three nodes. K-truss might fit better there, demanding edges surrounded by triangles. No single method fits all perfectly.
Alex: Huh, so heuristics trade generality for speed on sparse real-world graphs like financial or news data.
Sam: Precisely. The takeaway: a reliable, deterministic swap for Leiden in GraphRAG—linear time hierarchies that boost steady reasoning on sparse knowledge graphs, with token savings.
Alex: That's a grounded step forward for trustworthy global questions across documents. Thanks, Sam, for breaking it down so clearly.
Sam: My pleasure, Alex. Thanks for listening to ResearchPod.