PolyG: Effective and Efficient GraphRAG with Adaptive Graph Traversal

论文介绍

《PolyG: Effective and Efficient GraphRAG with Adaptive Graph Traversal》提出了一种自适应的图遍历策略，用于增强基于知识图谱的检索增强生成（GraphRAG）系统。传统的GraphRAG方法采用固定的图遍历策略（如广度优先搜索或随机游走），但不同问题类型需要不同的遍历策略，导致生成答案的质量和效率受限。PolyG通过问题分类和动态选择图遍历策略，显著提升了生成效果和响应速度。

问题解答

1. 论文要解决的问题

现有GraphRAG方法使用单一固定的图遍历策略，无法适应不同类型的问题。例如：
- 效果受限：某些问题需要多跳推理（如实体间关系），但固定的一阶BFS无法捕捉长距离关联。
- 效率低下：部分方法（如ToG）每一步都调用大语言模型（LLM），导致高延迟和计算开销。

2. 前人研究现状

• MSGraphRAG/LightRAG：一阶BFS，适合实体的一般信息查询，但无法处理多跳问题。
• RoG：生成推理路径，需明确的关系约束，对模糊问题失效。
• Fast-GraphRAG：基于PageRank的路径排序，可能引入不相关结果。
• ToG/Graph-CoT：每一步调用LLM，灵活但效率极低（延迟增加4倍，token消耗增加30倍）。
• 当前水平：各方法在特定问题上表现良好，但缺乏通用性（如表1中不同方法在不同问题类型的胜率差异显著）。

3. 论文的Idea来源

观察到用户问题类型多样，需匹配不同的图遍历策略。例如：
- 问题分类：将问题抽象为知识图谱三元组（s, p, o），根据缺失部分分为四类（如“s,,”为实体的一般信息查询）。
- 策略适配：每类问题对应最优遍历策略（如最短路径用于实体间关系查询）。

4. 具体方案

PolyG的流程分为五步：
1. 问题分类：通过LLM将问题分为四类（表2）。
2. 遍历计划生成：根据问题类型选择策略：
- BFS邻居扩展（s,,）：提取实体的一跳邻居。
- 元路径引导（s,p,）：生成带关系约束的推理路径。
- Top-k最短路径（s,,o）：连接两个实体的最短路径。
- 带约束的最短路径（s,p,o）：筛选满足特定关系的路径。
3. 遍历执行：通过Neo4j执行Cypher查询。
4. 上下文组织：将结果格式化为实体表、关系表或路径列表。
5. 答案生成：结合检索结果和问题生成最终回答。

5. 实验设计

• 数据集：三个知识图谱（学术、文学、电商），共320个问题（每类80个）。
• 评估指标：生成质量（胜率、F1值）、延迟、token消耗。
• 结果：
  • 生成质量：PolyG平均胜率75%，优于所有基线（表4-5）。
  • 效率：响应时间降低4倍，token消耗减少95%（表6）。
  • 分类开销：问题分类仅占10%时间和30% token（图2-3）。

6. 结论

• 有效性：四类问题的自适应策略显著提升生成质量。
• 高效性：避免不必要的LLM调用，降低计算开销。
• 通用性：统一的接口支持多样化问题（图4）。

7. 未来方向

• 复杂查询分解：将复合问题拆解为多个子问题（如“美国前五大城市”需检索+排序）。
• 非遍历操作集成：支持聚合、排序等操作（如统计作者发表次数）。
• 优化分类器：减少LLM依赖，提升分类效率。

总结

PolyG通过问题分类和自适应图遍历，解决了传统GraphRAG的局限，为知识图谱问答系统提供了高效、通用的解决方案。其核心思想是“不同问题需要不同策略”，这一思路可扩展至更复杂的查询场景。

以下是PolyG核心思想的伪代码实现，重点展现其自适应图谱遍历策略的决策逻辑：

# 输入：自然语言问题Q，知识图谱G
# 输出：增强后的答案A

def PolyG(Q, G):
    # Stage 1: 问题分类
    query_type = classify_question(Q)  # 使用LLM分类器

    # Stage 2: 自适应策略选择
    if query_type == "(s,*,*)":  # 实体概况查询
        strategy = "BFS_neighbor_expansion"
        max_depth = 2  # 默认两跳邻居
    elif query_type == "(s,p,*)":  # 关系查询
        strategy = "meta_path_guided"
        relation_constraints = extract_relations(Q)
    elif query_type == "(s,*,o)":  # 多跳路径查询
        strategy = "top_k_shortest_path"
        k = 3  # 返回前3条最短路径
    elif query_type == "(s,p,o)":  # 精确三元组验证
        strategy = "constrained_shortest_path"

    # Stage 3: 图谱遍历执行
    if strategy == "BFS_neighbor_expansion":
        subgraph = G.bfs(start=Q.s, depth=max_depth)
        context = generate_entity_table(subgraph)
    elif strategy == "meta_path_guided":
        paths = []
        for rel in relation_constraints:
            paths += G.find_paths(start=Q.s, edge_label=rel)
        context = generate_relation_table(paths)
    elif "shortest_path" in strategy:
        paths = G.k_shortest_paths(start=Q.s, end=Q.o, k=k)
        if strategy == "constrained_shortest_path":
            paths = filter(lambda p: p.contains(Q.p), paths)
        context = generate_path_list(paths)

    # Stage 4: 答案生成
    prompt = f"""基于以下上下文回答'{Q}':
    {context}"""
    A = LLM.generate(prompt)

    return A

# 辅助函数示例
def classify_question(Q):
    prompt = f"""将问题分类为以下类型之一:
    1. (s,*,*) - 询问实体属性/概况
    2. (s,p,*) - 询问特定关系
    3. (s,*,o) - 询问实体间路径
    4. (s,p,o) - 验证特定三元组

    问题:{Q}"""
    return LLM.classify(prompt)  # 返回最匹配的类型

关键设计说明：

1. 策略路由：通过classify_question实现四分类路由（第3章证明覆盖96%案例）
2. 差异化处理：
   • BFS邻居扩展：适合获取实体周边信息（如"介绍爱因斯坦"）
   • 元路径引导：处理显式关系查询（如"爱因斯坦的老师是谁"）
   • 最短路径：解决多跳推理（如"爱因斯坦和居里夫人如何关联"）
3. 效率优化：
   • 避免Graph-CoT的逐跳LLM调用
   • 不同策略生成不同上下文格式（实体表/关系表/路径列表）

复杂度分析：

• 时间复杂度：O(1)分类 + O(b^d)~O(V+E)遍历（b为分支因子，d为深度）
• 空间复杂度：O(k|P|)路径存储（k为保留路径数，|P|为平均路径长度）

该设计实现了论文第4章强调的"问题感知的检索优化"核心思想。

Thinking

核心思想是不同问题需要不同检索策略，这里和ms的pike-rag也比较像

延伸开，不同的问题其实也有不同的生成query的策略，比如不同的prompt。

以及后续不同的评测指标
* 比如我们不能用事实类问题的效果和开放性问题的效果去对比

paper里还有一个不错的图，用来解释现有的graphrag的方案：