用核心分解构建更稳定的图谱层级,提升大模型全局推理效率。
Core-based Hierarchies for Efficient GraphRAG
- 以k-core分解替代Leiden聚类,实现确定性密度感知的层级结构
- 在金融、新闻等数据集上提升答案全面性与多样性,同时降低30%以上令牌消耗
- 适合需要跨文档推理的场景,如财报分析、知识图谱构建
检索增强生成(RAG)通过引入外部知识提升大语言模型能力,但传统向量方法在需跨多文档推理的全局理解任务中表现不佳。GraphRAG通过将文档组织为具有层次化社区的知识图谱来解决此问题。现有方法依赖Leiden聚类进行社区发现,但我们证明:在稀疏知识图谱(平均度数恒定,多数节点度数低)中,模块度优化存在指数级数量的近似最优划分,导致Leiden所得社区不可复现。为此,我们提出用k-core分解替代Leiden,可在线性时间内生成确定性、密度感知的层次结构。进一步设计轻量级启发式策略,基于k-core层级构建大小受限、连通性保持的社区,并引入按令牌预算采样的策略以降低LLM成本。我们在真实数据集(包括金融财报转录、新闻文章和播客)上评估,使用三个LLM生成答案,五名独立LLM裁判进行对比测试。结果表明,该方法在各数据集与模型上均显著提升答案的全面性与多样性,同时减少令牌使用,验证了基于k-core的GraphRAG在全局理解任务中的有效性与高效性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。