Core-based Hierarchies for Efficient GraphRAG | Jakir Hossain, Ahmet Erdem Sarıyüce | ResearchPod

Transcript: Core-based Hierarchies for Efficient GraphRAG

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.

Core-based Hierarchies for Efficient GraphRAG

Jakir Hossain, Ahmet Erdem Sarıyüce

Mar 5, 2026·6:50·arxiv·Original Paper

GraphRAGk-core decompositionLeiden clustering limitationsToken-budget-aware samplingGlobal sensemakingModularity optimization unreliability

Listen

7 min

Briefing

Abstract

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.

Core-based Hierarchies for Efficient GraphRAG: Research Paper Podcast

Core-based Hierarchies for Efficient GraphRAG

Listen