Core-based Hierarchies for Efficient GraphRAG

This paper proposes a deterministic and efficient GraphRAG framework that replaces non-reproducible Leiden clustering with k-core decomposition and lightweight heuristics to improve global sensemaking, answer comprehensiveness, and diversity while reducing token costs across diverse real-world datasets.

The Gist

Imagine you are trying to solve a massive mystery. You have a library containing millions of books, articles, and podcast transcripts. Your goal is to answer a big, complex question like, "How have semiconductor companies changed their strategies over the last decade?"

To do this, you hire a brilliant detective (an AI Large Language Model). But there's a problem: the detective can only read a few pages at a time. If you just hand them random pages, they might miss the big picture.

This is where GraphRAG comes in. It's a system that organizes your library into a giant map (a "knowledge graph") where related ideas are connected by strings. The current best way to organize this map is to group related ideas into "communities" (like neighborhoods) and summarize each neighborhood.

However, the authors of this paper, Jakir Hossain and Ahmet Erdem Sarıyüce, discovered a flaw in how these "neighborhoods" are currently built. Here is their story, explained simply.

The Problem: The "Leiden" Neighborhood Builder is Unreliable

Currently, most systems use a method called Leiden to draw the boundaries of these neighborhoods. Think of Leiden as a very popular, but slightly chaotic, town planner.

• The Chaos: The authors proved that on sparse maps (where most ideas are only connected to a few others, like in a library of diverse documents), Leiden is like a coin flip. If you run the planner twice, it might draw the neighborhood lines in two completely different ways, even though the map hasn't changed.
• The Result: Sometimes, it splits a single important topic into two unrelated neighborhoods. Other times, it shoves unrelated topics together just because the math said so. This makes the detective's summaries inconsistent and unreliable. It's like asking a tour guide to show you the "Historic District," but one day they show you the library, and the next day they show you the grocery store.

The Solution: The "Core" Organizer

The authors propose replacing the chaotic town planner with a new method based on $k$-core decomposition.

Imagine your library map is a giant, tangled ball of yarn.

• The Old Way (Leiden): Tries to cut the yarn into chunks based on how "clumpy" the yarn looks. It often gets confused by loose ends.
• The New Way ($k$-core): Looks for the tightest, most tightly wound knots in the center of the ball.
  • The 1-core is the whole ball.
  • The 2-core is the ball with all the loose, dangling strings removed.
  • The 3-core is the even tighter knot inside that.
  • And so on.

This method is deterministic. If you do it twice, you get the exact same result every time. It naturally organizes the map from the "dense, important center" (the core topics) out to the "sparse, peripheral edges" (the minor details).

How They Built the New System

The authors didn't just swap the planner; they built a whole new workflow around this "Core" idea:

1. Residual Awareness: They realized that after peeling away the tight knots, you are left with loose, single threads (isolated facts). Their new system, called RkH, carefully handles these loose threads so they don't get lost or accidentally glued to the wrong knot.
2. Merging Tiny Groups: Sometimes the system creates tiny "neighborhoods" with only two people in them. These are too small to be useful. The authors added a rule to merge these tiny groups into their neighbors, ensuring every summary has enough meat to be interesting.
3. Token Budgeting: Large Language Models cost money based on how much they read (tokens). The authors added a "Round-Robin" strategy. Instead of reading every connection in a neighborhood, the system picks the most important ones, like a chef tasting the best ingredients from a pot rather than eating the whole pot. This saves money without losing flavor.

The Results: A Better Detective

They tested this new system on real-world data: financial earnings calls, news articles, and tech podcasts. They used three different AI "detectives" to answer questions and five other AIs to grade the answers.

• Better Answers: The new system consistently gave more comprehensive and diverse answers. It was better at connecting the dots across the whole library.
• Cheaper: Because of their smart "token budgeting," they used fewer words to get the same (or better) results, saving money.
• Reliable: Most importantly, the results were consistent. You could run the system a hundred times, and it would organize the library the same way every time.

The Big Takeaway

In the world of AI, we often try to make sense of huge amounts of data. The old way of organizing this data was like trying to sort a messy room by guessing where things go; it worked okay, but it was inconsistent.

This paper introduces a new way: finding the tightest knots first. By focusing on the most connected, central parts of the information and working our way out, we can build a system that is faster, cheaper, and much more reliable at helping AI understand the "big picture" of our world's knowledge.

Technical Summary

Here is a detailed technical summary of the paper "Core-based Hierarchies for Efficient GraphRAG" by Jakir Hossain and Ahmet Erdem Sarıyüce.

1. Problem Statement

Retrieval-Augmented Generation (RAG) enhances Large Language Models (LLMs) but struggles with global sensemaking tasks—queries requiring reasoning across many documents to synthesize themes, reconcile conflicts, or identify patterns (e.g., "How have patient outcomes evolved over 15 years?").

Current GraphRAG approaches attempt to solve this by organizing documents into a knowledge graph and using hierarchical community detection (specifically the Leiden algorithm) to recursively summarize communities. However, the authors identify a critical flaw:

• Modularity Degeneracy: Knowledge graphs are typically sparse (low average degree, many low-degree nodes). The authors prove that on such sparse graphs, modularity optimization admits an exponentially large number of near-optimal partitions.
• Non-Reproducibility: Because Leiden relies on modularity optimization, it is inherently unstable on sparse graphs. Minor changes in random seeds or edge perturbations lead to structurally different communities, making summaries non-reproducible and often semantically incoherent (fragmenting topics or grouping unrelated nodes).

2. Methodology

The authors propose replacing Leiden-based community detection with $k$-core decomposition, a deterministic graph algorithm, combined with specific heuristics to handle the resulting hierarchy.

A. Theoretical Foundation: $k$-Core vs. Modularity

• $k$-Core Decomposition: This algorithm recursively removes nodes with degree less than $k$, assigning each node a "core number" (the largest $k$ for which it belongs to a $k$-core).
• Advantages:
  • Deterministic: Unlike Leiden, $k$-core decomposition yields a unique hierarchy for a given graph, eliminating randomness.
  • Density-Aware: It naturally captures nested, dense substructures. In knowledge graphs, higher $k$-cores represent entities connected by multiple distinct relational paths, serving as a proxy for topical centrality.
  • Efficiency: It runs in linear time $O(|E|)$, whereas Leiden involves iterative optimization.
• Theoretical Proof (Theorem 1): The authors prove that for sparse graphs (where average degree is constant and most nodes have low degree), the number of near-optimal modularity partitions is exponential ($2^{\Theta(n)}$). This formally explains why Leiden fails to find a stable "right" partition in this regime.

B. Proposed Heuristics

To make $k$-core decomposition practical for GraphRAG, the authors introduce a pipeline of lightweight heuristics:

1. Residual-aware $k$-core Hierarchy (RkH):

   • Processes the graph level-by-level (from $k=1$ upwards).
   • Separates dense cores (nodes with $core \ge \ell$) from sparse residuals (nodes with $core < \ell$).
   • Splits oversized dense components into size-bounded clusters using a greedy growth strategy (Algorithm 3) to respect LLM context limits.
   • Handles singleton and residual nodes separately to prevent them from distorting the core structure.

2. Merging Small Clusters (M2hC & MRC):

   • Problem: The $k$-core process often leaves tiny clusters (e.g., size 2) that are too small to be useful for summarization and are often ignored by LLMs.
   • Solution:
     • M2hC (Merge 2-hop Clusters): Merges small 2-hop connected clusters into larger neighboring clusters if they share edges.
     • MRC (Merge Residual Clusters): Extends M2hC to handle all small residual components (size 2), merging them into parent clusters to reduce fragmentation.

3. Token-Efficient Sampling (RRTC):

   • Round-Robin Token-Constrained Selection: To reduce LLM costs, this heuristic selects a representative subset of edges from leaf-level communities based on a token budget.
   • It ranks edges by the combined degree of endpoints and selects them in a round-robin fashion across communities, ensuring coverage of the most informative parts of the graph without exceeding token limits.

3. Key Contributions

1. Theoretical Insight: Proved that modularity optimization is fundamentally unreliable on sparse knowledge graphs due to exponential degeneracy, providing a formal justification for abandoning Leiden in this context.
2. Algorithmic Innovation: Introduced $k$-core decomposition as a drop-in replacement for Leiden, offering a deterministic, linear-time, density-aware hierarchy.
3. Practical Heuristics: Developed RkH, M2hC, and MRC to construct size-bounded, connectivity-preserving communities suitable for LLM summarization.
4. Cost Reduction: Introduced RRTC to significantly reduce token usage while maintaining retrieval quality.
5. Comprehensive Evaluation: Validated the approach across three real-world datasets (Financial transcripts, News, Podcasts) using three different LLMs (GPT-3.5-turbo, GPT-4o-mini, GPT-5-mini) and five independent LLM judges.

4. Experimental Results

The authors evaluated their methods against the standard Leiden-based GraphRAG (Edge et al.) using Comprehensiveness and Diversity metrics.

• Performance:
  • Across all datasets and models, $k$-core based heuristics (specifically M2hC LF and MRC LF) consistently outperformed Leiden's C2 and C3 levels.
  • Win Rates: The proposed methods achieved win rates of 70–75% against Leiden baselines on post-knowledge-cutoff data (where models cannot rely on memorized training data).
  • Statistical Significance: The improvements were statistically significant ($p < 0.005$) for the M2hC LF configuration across all datasets.
• Robustness:
  • The advantage held true for both weaker (GPT-3.5) and stronger (GPT-5) models, though the margin narrowed slightly with stronger models due to their prior knowledge.
  • Leaf-level (LF) variants generally outperformed higher-level (L1) variants, confirming that finer-grained communities yield better summaries.
• Efficiency:
  • The MRC heuristic reduced the number of communities and token coverage by up to 40% compared to Leiden while maintaining or improving answer quality.
  • The RRTC sampling strategy allowed for edge budgets as low as 60% of the original graph while retaining competitive performance, further reducing costs.

5. Significance

This paper addresses a fundamental instability in the current GraphRAG paradigm. By demonstrating that modularity-based clustering is mathematically unsuited for the sparse nature of knowledge graphs, the authors provide a robust alternative.

• Reliability: The shift to $k$-core decomposition ensures that GraphRAG pipelines are deterministic and reproducible, a critical requirement for enterprise and scientific applications.
• Scalability: The linear-time complexity and token-saving heuristics make global sensemaking more feasible and cost-effective.
• Quality: The results suggest that structurally grounded hierarchies (based on connectivity density) lead to more comprehensive and diverse answers than those based on modularity optimization, which can be arbitrary in sparse regimes.

In conclusion, the paper establishes $k$-core-based GraphRAG as a superior framework for global sensemaking, offering a balance of theoretical rigor, computational efficiency, and practical performance improvements.