研究问题与动机
- GraphRAG 的社区摘要依赖模块度优化;在稀疏图上,存在大量近似等价的 partition,初始化和随机性会影响层次结果。
- 社区大小失衡会造成摘要粒度不稳定,并增加 LLM 调用与上下文冗余。
- 论文的理论和工程问题分别是:Leiden 在稀疏图上的可复现性如何解释,以及能否用线性时间的 k-core 层次替代它。
方法与机制
k-core 层次
节点的 core number 是其所属最大 k-core 的 k。k-core 分解在给定图上是确定性的,计算复杂度为线性级别。论文证明稀疏图的模块度优化存在指数级多个近优 partition,并据此论证 Leiden 层次可能不稳定;这不是对所有 Leiden 实现的运行时间定理。
三种层次启发式
- RkH:按 core level 构造层次并处理残余节点;
- M2hC:合并过小的 2-hop cluster,减少碎片;
- MRC:进一步合并 residual/small clusters,降低社区数量和摘要覆盖。
每种策略都评估 leaf(LF)和 leaf 的直接父层(L1)。
RRTC
Round-Robin Token-Constrained Selection 在叶社区中按端点度数排序边,从不同 k-shell 轮询选择边,直到达到固定 token 预算。它通过保留各社区代表性边来减少冗余,而不是声称保留完整图信息。
证据与结果
- 在 GPT-3.5 post-cutoff 比较中,k-core 启发式在约 70–75% 的数据集×层次×指标比较中获得更高胜率;M2hC LF 的综合表现最稳定。
- M2hC LF 在 diversity 上对 podcast 的 Leiden C2 胜率为 66%,对 news 的 C3 胜率为 61%;semiconductor 上 MRC LF 在 comprehensiveness 的部分比较达到 67%。这些是 pairwise win rates,不是绝对准确率。
- 通过 k-core 层次构建,层次构建开销平均降低约 31%,LLM 调用数平均减少约 30–35%。
- RRTC 在固定边预算下最多可相对 Leiden 降低约 40% token 使用,同时保持有竞争力的 comprehensiveness/diversity;收益随预算变化,不能概括为固定的 40% 性能提升。
- 25 个问题/数据集的 claim support rate 分析中,k-core 与 Leiden 平均约为 0.89;作者明确说明这受
+more引用截断影响,且二者 grounding 相近。
局限与开放问题
- 主要评价依赖 LLM judge 和无 gold reference 的 global sensemaking,人工验证规模有限。
- 评测语料和问题主要覆盖 global sensemaking;对 factoid、多跳 KGQA、开放域增量更新的结论尚不充分。
- MRC 以更低覆盖换取更少社区,token 节省与证据丢失之间需要按任务校准。
- 论文未来工作才提出动态图更新和替代边采样;当前结果不等于已经解决索引生命周期。
关联与拓展
暂无可可靠提取的关联研究段落;先从研究问题索引横向比较。