GGraphRAG 文献图谱自动同步
LIT-5346AD22 · 2026

PRoH - Dynamic Planning over Knowledge Hypergraphs

PRoH 用局部 KH sketch 生成初始 reasoning DAG,再在状态空间中迭代求解和重写 DAG,并用 Entity-Weighted Overlap 选择超图中的下一跳 reasoning path。

PDF 级阅读卡优先级 P1Xiangjun Zai, Xingyu Tan, Xiaoyang Wang, Qing Liu, Xiwei Xu, Wenjie ZhangWWW 2026
内容状态:PDF 级阅读卡。结构化摘录继承当前知识库的来源等级;具体 claim 应回到一手论文核验。

研究问题与动机

  • 研究问题:Knowledge Hypergraph 可以把 n-ary relation 作为一个 hyperedge 表达,但现有 KH-based RAG 往往仍用固定 pipeline 做一次性检索,没有把 query 分解、图搜索和中间答案反馈放进同一个动态规划过程。
  • 为什么重要:复杂多跳问题经常需要在多个实体和多个 hyperedge 之间跳转。若只按原始 query 做相似度检索,系统容易拿到语义相近但推理链不完整的证据。
  • 现有路线:
    • 普通 KG / GraphRAG 多把关系拆成二元边,表达多实体事实时会丢失整体语义。
    • HyperGraphRAG 等 KH 路线能表达 hyperedge,但检索过程仍偏 static retrieval plan。
    • Agentic GraphRAG / RL GraphRAG 强调多轮轨迹,但不一定显式利用 hyperedge overlap 的结构语义。
  • 对本知识库的意义:PRoH 把 Graph-R1 - Agentic GraphRAG via End-to-end Reinforcement Learning 的 hypergraph environment、GraphRAG作为Query-Planning 的 query planning、以及 DOTRAG - Retrieval-Time Reasoning Along Paths 的 path-first retrieval 连接起来:它不是单纯换成超图索引,而是把“规划 DAG -> 状态搜索 -> EWO 路径检索”做成一条可归因的执行链。

Figure 1 的关键不是“超图更复杂”,而是 n-ary fact 在超图里以一个 hyperedge 承载完整语义;如果拆成普通二元边,Nintendo、Ubisoft、Mario + Rabbids Kingdom Battle 和 E3 2021 的联合事实会被切碎。

  • Static retrieval planning:KH-based RAG 通常使用预定义检索步骤,不能根据问题语义和局部图结构改变检索计划。
  • Non-adaptive retrieval execution:检索多为 one-shot,不能用中间 subquestion answer 反向修正后续子问题和检索方向。
  • Superficial hyperedge use:很多方法把 hyperedge 视作访问 text chunk 的入口,而不是可评分、可遍历、可组合的推理对象。
  • 复杂多跳中的 branch ambiguity 没被显式处理:一个子问题可能有多个候选答案和路径,线性分解会过早锁死错误分支。
  • 缺少细粒度路径选择信号:普通 overlap 或相似度无法判断两个 hyperedge 共享的实体是否真的支持当前 subquestion。

方法与机制

1. 总体框架:Graph Anchoring -> Planning -> Reasoning -> Final Answer

输入:问题 $q$ 和知识超图:

H=(V,E)

其中实体 $v=(v_{nm},v_{desc})$,hyperedge $e=(e_{nm},V(e),e_{ref})$。

计算链路:

  1. Graph Anchoring:从 $q$ 中识别 topic entities,并匹配 target hyperedges,构造 question subgraph $H_q$。
  2. Planning:在 $H_q$ 的局部 plan context 上生成多个初始 reasoning DAG。
  3. Reasoning:把每个 DAG 当作状态搜索树的根,逐层求解 subquestions;每个子问题调用 answer-and-path retrieval。
  4. Final Answer Generation:把 completed DAGs 中的 answer-path pairs 聚合为候选答案,再由 LLM judge 选出最终答案。

输出:最终答案 $a^*(q)$,以及可追踪的 completed reasoning DAG、answer-path pairs 和超图路径证据。

直观解释:PRoH 把 GraphRAG 的检索从“取一批相似节点/文本”改成“围绕问题生成可执行 DAG,并在每个 DAG 状态下取可解释路径”。

2. Graph Construction and Synonym Hyperedge Augmentation

输入:从语料构建的 KH,以及实体名、实体描述、hyperedge name 的向量索引。

计算链路:

  1. 采用 HyperGraphRAG 风格构建 KH:
H=(V,E)
  1. 对实体名 embedding 计算相似度:
sim(v_i,v_j)=cos(z(v_i^{nm}),z(v_j^{nm}))
  1. 若 $sim(v_i,v_j)\ge \tau$,先形成相似实体图,再取 connected components。
  2. LLM 判断 component 内实体是否同义。
  3. 对确认同义的实体组添加 synonym hyperedge。

输出:带 synonym hyperedges 的 KH。

直观解释:这一步减少同义实体分裂导致的 anchor miss。它不是最终推理模块,但会影响 topic entity initialization、target hyperedge match 和后续 path search 的召回。

3. Graph Anchoring:把问题固定到局部超图

输入:问题 $q$、KH $H$、topic keyword candidates、hyperedge name vector index。

计算链路:

  1. LLM 从问题中抽取 topic keywords。
  2. 用 keyword embedding 与 entity name embedding 做 cosine matching,得到 topic entities $\mathcal{T}$。
  3. 用 question embedding 与 hyperedge name embedding 匹配 target hyperedges $\mathcal{R}$。
  4. 取 $\mathcal{T}$ 和 $\mathcal{R}$ 的 $D_{max}$-hop neighborhood,形成 question subgraph:
H_q=(V_q,E_q)

输出:面向当前问题的局部 KH scope。

直观解释:Graph Anchoring 决定 planner 能看到什么。如果 anchor 错,后续 DAG 再聪明也会在错误子图里搜索。

4. Planning:从局部 KH 生成可执行 reasoning DAG

输入:question subgraph $H_q$、问题 $q$、topic entities $\mathcal{T}$、target hyperedges $\mathcal{R}$、plan depth $d_p$、初始 plan 数 $n_0$。

计算链路:

  1. 先围绕 topic entities / target hyperedges 构造 plan context graph:
H_p=(V_p,E_p)
  1. 对实体计算 question relevance:
SE(v|q)=cos(z(v_{desc}),z(q))
  1. 对候选 hyperedge 与当前 hyperedge 的 overlap 计算 relevance:
SH(e'|q,e)=AGG(\{SE(v|q)\mid v\in V(e)\cap V(e')\})
  1. 按 $SH$ 选择局部搜索方向,形成 plan context $c_p$。
  2. LLM 基于 $(q,\mathcal{T},c_p)$ 生成候选 subquestions 和 dependencies:
(Q,L)=LLMPlan(q,\mathcal{T},c_p)
  1. 对 dependency graph 做 Hasse reduction,去掉传递冗余边:
D=(Q,L_H)

输出:一组初始 reasoning DAGs $\mathcal{D}0={D_1,\ldots,D{n_0}}$。

直观解释:这里的 planner 不是纯语言分解器,而是先用局部超图约束 LLM:它生成的 subquestion 必须更贴近可检索的实体和 hyperedge。

5. Reasoning:在 DAG 状态空间中迭代求解和改写

原始笔记摘录已截断;请打开来源笔记阅读完整内容。

证据与结果

1. 主结果:PRoH 在五个 KHQA domain 上超过 HyperGraphRAG

Table 1 显示 PRoH 在 Medicine、Agriculture、CS、Legal、Mix 上整体优于 HyperGraphRAG:

  • PRoH F1:52.94、56.67、54.15、58.81、69.16。
  • HyperGraphRAG F1:35.35、33.89、31.30、43.81、48.71。
  • PRoH G-E:67.35、69.46、66.79、69.88、76.17。
  • 论文报告相对 HyperGraphRAG 平均提升:F1 +19.73%,G-E +8.41%。

解读:PRoH 的提升集中在 answer F1 和 generation evaluation,而 R-S 不总是最高。这说明它不是简单追求检索片段语义相似,而是通过路径和 DAG 让证据更服务最终推理。

2. 消融与搜索深度:目标 hyperedge、plan context、EWO 都有贡献

Table 2 的 F1 消融显示:

  • 去掉 Target Hyperedge,Mix 从 69.39 降到 60.81,是最明显的单模块下降之一。
  • 去掉 Plan Context,Agriculture / CS / Mix 变为 53.70 / 53.67 / 64.59,说明 graph-aware planning 确实影响初始 DAG 质量。
  • 去掉 EWO Guide 后为 53.22 / 56.27 / 65.63,说明路径方向选择需要语义化 overlap,而不是只看结构连接。
  • w/o ALL 下降到 51.93 / 51.96 / 55.84,证明多个模块互补。

Figure 3 显示 $d_{max}=3$ 时 F1/G-E 达到峰值;继续增加深度会带来冗余上下文和轻微性能下降,同时平均实际深度 $d_{avg}$ 继续增加。

3. 长程多跳:3-6 hop 下优势更明显

Table 3 针对 long-range multi-hop QA:

  • PRoH F1:Medicine 51.26,Agriculture 81.01,CS 74.83,Legal 71.93,Mix 79.69。
  • HyperGraphRAG F1:Medicine 39.94,Agriculture 52.40,CS 29.95,Legal 38.45,Mix 64.55。
  • 论文报告平均 F1 +26.68%,CS 最高提升到 +44.87%。

解读:PRoH 的优势在长程多跳更强,符合它的设计假设:动态 DAG 和 EWO 路径搜索主要解决的是长链、分支和跨 hyperedge 组合问题。

4. 效率与 backbone:PRoH-L 降 token,较强 LLM 提升规划/检索质量

Table 4 比较 PRoH-L 与 HyperGraphRAG 的 token:

  • Medicine 少 6.54%,F1 +10.28。
  • Agriculture 少 30.07%,F1 +16.58。
  • CS 少 34.82%,F1 +15.31。
  • Legal token 增加 30.54%,但 F1 +7.59。
  • Mix 少 30.09%,F1 +5.10。

Table 5 显示 Qwen3 backbone 从 4B 到 80B,Agriculture / CS 的 F1 和 G-E 整体提高。解读上,PRoH 依赖 LLM 做 planning、path selection 和 final judge,因此模型规模会影响规划质量和路径筛选质量。

局限与开放问题

  • Final answer generation 仍是最大误差来源:附录 Figure 7 报告 Final Answer Generation 占 43% error,Planning 占 33%,Reasoning State Search 和 Graph Anchoring 各 10%,Answer and Path Retrieval 约 5%。

  • Answer and Path Retrieval 是 token 大户:附录 Figure 6 显示该模块消耗最多 token,尤其是 LLM-based entity scoring 和 path selection。

  • 规划质量仍依赖 LLM:PRoH 把 planning 显式化,但没有训练 planner;错误 subquestion 或 dependency 仍会让搜索树扩大或偏离。

  • Anchor 仍是上游瓶颈:topic entity 和 target hyperedge 匹配错误会限制 plan context,进而影响整个 DAG。

  • 搜索成本与轨迹数量相关:BFS 在部分设置中 F1 更高,但 state visits 明显增多;论文选择 DFS 是性能/成本折中。

  • 实验主要围绕 KHQA domain,尚未证明在开放域文档 GraphRAG、动态增量图、多模态图或用户私有知识库中的泛化。

  • EWO 中的 LLMScore 和 path selection 仍是黑盒判断,缺少可学习的、可校准的路径效用模型。

  • 把 PRoH 的 DAG state search 变成可训练策略:对接 Graph-R1 - Agentic GraphRAG via End-to-end Reinforcement Learning 和 GraphRAG-R1 - Process-Constrained Reinforcement Learning for GraphRAG,用过程奖励优化 LLMSelectDirections、LLMSelectPaths 和 LLMGenerateNewDAG。

  • 做 query complexity routing:不是所有问题都需要 PRoH 级别的动态超图规划,可在 2026-06-09-Open-Problems 下比较 flat RAG、light graph、PRoH-style hypergraph planning 和 RL agentic graph environment。

  • 建立 evidence path utility:围绕 2026-06-09-Open-Problems,把 EWO、path score、support coverage、semantic shortcut rate、tail path miss 统一到一个路径效用诊断框架。

  • 做 planning-guided attribution:在 2026-06-09-Open-Problems 中记录 plan_context_graph、initial_reasoning_DAG、state=(D,i)、frontier F、answer_path_pairs、EWO、selected_directions、selected_paths、D_new、completed_DAGs、d_max、d_avg、n0、K、state visits 和 support gain。

  • 用可学习 scorer 替代部分 LLM judge:把 EWO entity score、direction choice、path acceptance 和 final answer consistency 分别蒸馏成轻量模型,降低 token 成本。

  • 将 PRoH 与 NaviRAG - Active Knowledge Navigation for RAG 对照:NaviRAG 处理 hierarchical document navigation,PRoH 处理 knowledge hypergraph traversal,两者可以统一为“局部 scope 选择 -> 分支展开 -> sufficiency stop”。

关联与拓展

研究问题入口

Q2 图构建与表示, Q3 证据检索与集合形成, Q4 查询规划与执行, Q5 动态状态与学习策略, Q6 证据来源与可解释性

展开原始论文笔记全文

基本信息

  • 英文标题:PRoH: Dynamic Planning and Reasoning over Knowledge Hypergraphs for Retrieval-Augmented Generation
  • 中文标题:PRoH:面向 RAG 的知识超图动态规划与推理
  • 方法名:PRoH
  • 作者:Xiangjun Zai, Xingyu Tan, Xiaoyang Wang, Qing Liu, Xiwei Xu, Wenjie Zhang
  • 机构:University of New South Wales, Data61 CSIRO
  • 年份:2026
  • 会议:WWW 2026
  • 版本:arXiv v2,2026-02-18 更新;初版 2025-10-14
  • 链接:arXiv
  • DOI:10.1145/3774904.3792611
  • PDF:查看论文原文
  • 代码:https://github.com/zaixjun/PRoH ,2026-06-09 检查为 MIT license,默认分支 main
  • Semantic Scholar:2026-06-09 查询 API 多次遇到 429,待复查。
  • 阅读状态:PDF级
  • 所属方向:Knowledge Hypergraph RAG、dynamic planning、reasoning DAG、EWO-guided path retrieval、multi-hop QA
  • 优先级:P1

Background

  • 研究问题:Knowledge Hypergraph 可以把 n-ary relation 作为一个 hyperedge 表达,但现有 KH-based RAG 往往仍用固定 pipeline 做一次性检索,没有把 query 分解、图搜索和中间答案反馈放进同一个动态规划过程。
  • 为什么重要:复杂多跳问题经常需要在多个实体和多个 hyperedge 之间跳转。若只按原始 query 做相似度检索,系统容易拿到语义相近但推理链不完整的证据。
  • 现有路线:
    • 普通 KG / GraphRAG 多把关系拆成二元边,表达多实体事实时会丢失整体语义。
    • HyperGraphRAG 等 KH 路线能表达 hyperedge,但检索过程仍偏 static retrieval plan。
    • Agentic GraphRAG / RL GraphRAG 强调多轮轨迹,但不一定显式利用 hyperedge overlap 的结构语义。
  • 对本知识库的意义:PRoH 把 Graph-R1 - Agentic GraphRAG via End-to-end Reinforcement Learning 的 hypergraph environment、GraphRAG作为Query-Planning 的 query planning、以及 DOTRAG - Retrieval-Time Reasoning Along Paths 的 path-first retrieval 连接起来:它不是单纯换成超图索引,而是把“规划 DAG -> 状态搜索 -> EWO 路径检索”做成一条可归因的执行链。

PRoH-fig1-knowledge-hypergraph

Figure 1 的关键不是“超图更复杂”,而是 n-ary fact 在超图里以一个 hyperedge 承载完整语义;如果拆成普通二元边,Nintendo、Ubisoft、Mario + Rabbids Kingdom Battle 和 E3 2021 的联合事实会被切碎。

Gap

  • Static retrieval planning:KH-based RAG 通常使用预定义检索步骤,不能根据问题语义和局部图结构改变检索计划。
  • Non-adaptive retrieval execution:检索多为 one-shot,不能用中间 subquestion answer 反向修正后续子问题和检索方向。
  • Superficial hyperedge use:很多方法把 hyperedge 视作访问 text chunk 的入口,而不是可评分、可遍历、可组合的推理对象。
  • 复杂多跳中的 branch ambiguity 没被显式处理:一个子问题可能有多个候选答案和路径,线性分解会过早锁死错误分支。
  • 缺少细粒度路径选择信号:普通 overlap 或相似度无法判断两个 hyperedge 共享的实体是否真的支持当前 subquestion。

Insight

  • 一句话创新点:PRoH 用局部 KH sketch 生成初始 reasoning DAG,再在状态空间中迭代求解和重写 DAG,并用 Entity-Weighted Overlap 选择超图中的下一跳 reasoning path。
  • 核心洞察:
    • 规划必须 graph-aware:先看 topic entities 和 target hyperedges 周围的局部 KH,再让 LLM 生成 decomposition,能减少“语言上合理但图里不可执行”的计划。
    • 子问题不是线性链,而是可演化 DAG:中间 answer-path pair 出现后,后续 subquestion 和 dependency 需要被改写。
    • 超图遍历的关键不是“共享多少实体”,而是“共享实体对当前 subquestion 有多大贡献”。
    • 多条轨迹并存比单一路径更稳:state search 允许多个 completed DAG 竞争,再由 final judge 选择与 reasoning path 一致的答案。

Method

1. 总体框架:Graph Anchoring -> Planning -> Reasoning -> Final Answer

PRoH-fig2-framework

输入:问题 $q$ 和知识超图:

H=(V,E)

其中实体 $v=(v_{nm},v_{desc})$,hyperedge $e=(e_{nm},V(e),e_{ref})$。

计算链路:

  1. Graph Anchoring:从 $q$ 中识别 topic entities,并匹配 target hyperedges,构造 question subgraph $H_q$。
  2. Planning:在 $H_q$ 的局部 plan context 上生成多个初始 reasoning DAG。
  3. Reasoning:把每个 DAG 当作状态搜索树的根,逐层求解 subquestions;每个子问题调用 answer-and-path retrieval。
  4. Final Answer Generation:把 completed DAGs 中的 answer-path pairs 聚合为候选答案,再由 LLM judge 选出最终答案。

输出:最终答案 $a^*(q)$,以及可追踪的 completed reasoning DAG、answer-path pairs 和超图路径证据。

直观解释:PRoH 把 GraphRAG 的检索从“取一批相似节点/文本”改成“围绕问题生成可执行 DAG,并在每个 DAG 状态下取可解释路径”。

2. Graph Construction and Synonym Hyperedge Augmentation

输入:从语料构建的 KH,以及实体名、实体描述、hyperedge name 的向量索引。

计算链路:

  1. 采用 HyperGraphRAG 风格构建 KH:
H=(V,E)
  1. 对实体名 embedding 计算相似度:
sim(v_i,v_j)=cos(z(v_i^{nm}),z(v_j^{nm}))
  1. 若 $sim(v_i,v_j)\ge \tau$,先形成相似实体图,再取 connected components。
  2. LLM 判断 component 内实体是否同义。
  3. 对确认同义的实体组添加 synonym hyperedge。

输出:带 synonym hyperedges 的 KH。

直观解释:这一步减少同义实体分裂导致的 anchor miss。它不是最终推理模块,但会影响 topic entity initialization、target hyperedge match 和后续 path search 的召回。

3. Graph Anchoring:把问题固定到局部超图

输入:问题 $q$、KH $H$、topic keyword candidates、hyperedge name vector index。

计算链路:

  1. LLM 从问题中抽取 topic keywords。
  2. 用 keyword embedding 与 entity name embedding 做 cosine matching,得到 topic entities $\mathcal{T}$。
  3. 用 question embedding 与 hyperedge name embedding 匹配 target hyperedges $\mathcal{R}$。
  4. 取 $\mathcal{T}$ 和 $\mathcal{R}$ 的 $D_{max}$-hop neighborhood,形成 question subgraph:
H_q=(V_q,E_q)

输出:面向当前问题的局部 KH scope。

直观解释:Graph Anchoring 决定 planner 能看到什么。如果 anchor 错,后续 DAG 再聪明也会在错误子图里搜索。

4. Planning:从局部 KH 生成可执行 reasoning DAG

输入:question subgraph $H_q$、问题 $q$、topic entities $\mathcal{T}$、target hyperedges $\mathcal{R}$、plan depth $d_p$、初始 plan 数 $n_0$。

计算链路:

  1. 先围绕 topic entities / target hyperedges 构造 plan context graph:
H_p=(V_p,E_p)
  1. 对实体计算 question relevance:
SE(v|q)=cos(z(v_{desc}),z(q))
  1. 对候选 hyperedge 与当前 hyperedge 的 overlap 计算 relevance:
SH(e'|q,e)=AGG(\{SE(v|q)\mid v\in V(e)\cap V(e')\})
  1. 按 $SH$ 选择局部搜索方向,形成 plan context $c_p$。
  2. LLM 基于 $(q,\mathcal{T},c_p)$ 生成候选 subquestions 和 dependencies:
(Q,L)=LLMPlan(q,\mathcal{T},c_p)
  1. 对 dependency graph 做 Hasse reduction,去掉传递冗余边:
D=(Q,L_H)

输出:一组初始 reasoning DAGs $\mathcal{D}0={D_1,\ldots,D{n_0}}$。

直观解释:这里的 planner 不是纯语言分解器,而是先用局部超图约束 LLM:它生成的 subquestion 必须更贴近可检索的实体和 hyperedge。

5. Reasoning:在 DAG 状态空间中迭代求解和改写

PRoH-algorithms-plan-reason-retrieve

输入:初始 DAG 集合 $\mathcal{D}0$、question subgraph $H_q$、KH exploration depth $d{max}$、beam width $b$、最大 completed solution 数 $K$。

计算链路:

  1. 定义 reasoning state:
s=(D,i)

其中 $D$ 是当前 DAG,$i$ 是正在处理的 topological level。

  1. 用 DFS 维护 frontier $\mathcal{F}$,每次弹出一个 state。
  2. 取当前 level 的 subquestions $Q_i$。
  3. 对每个 $q_j\in Q_i$ 调用 RetrieveAnswersWithPaths,得到 answer-path pairs:
AP_j=\{(a_j,p_j)\}
  1. 对同一 level 的 answer-path combinations,调用 LLM 生成 successor DAG:
D_{new}=LLMGenerateNewDAG(D,AP)
  1. 若 $D$ 所有 level 都完成,则加入 completed DAG 集合:
\mathcal{D}_{comp}\leftarrow \mathcal{D}_{comp}\cup\{D\}

输出:最多 $K$ 个 completed DAGs。

直观解释:Reasoning 负责“计划的运行时修正”。如果某个 subquestion 的答案改变了后续问题的约束,DAG 会被重写,而不是继续执行旧计划。

6. Answer and Path Retrieval:用 EWO 指导超图路径搜索

PRoH-ewo-formulas

输入:当前 subquestion $q_j$、question subgraph $H_q$、depth limit $d_{max}$、beam width $b$。

计算链路:

  1. Graph re-anchoring:针对 $q_j$ 重新识别 topic entities $\mathcal{T}_j$ 与 target hyperedges $\mathcal{R}_j$。
  2. 初始化 frontier:
\mathcal{F}_e=\{(e,[e])\mid e \cap \mathcal{T}_j\ne\varnothing \lor e\in \mathcal{R}_j\}
  1. 对当前 hyperedge $e$ 的邻居 $e'$,先判断 overlap entity 的 embedding relevance:
EW(v|q_j)= \begin{cases} LLMScore(v,q_j), & SE(v|q_j)\ge \theta_{emb}\\ 0, & otherwise \end{cases}
  1. 聚合 overlap entities 的 relevance,得到 EWO:
EWO(e'|q_j,e)=AGG(\{EW(v|q_j)\mid v\in V(e)\cap V(e')\})
  1. 用 EWO 排序候选方向,并让 LLM 从 top directions 中选择:
F_{sel}=LLMSelectDirections(F_{cand},q_j,b)
  1. 形成候选 paths 后,按路径级 relevance 排序:
SP(p)=\sum\{EW(v|q_j)\mid v\in e \land e\in p\}
  1. LLM 选择是否存在足够路径:
P_{sel}=LLMSelectPaths(P_{cand},q_j)
  1. 对每条选中路径 $p_j$,构造 step context:
c_j=p_j\cup Desc(V(p_j))\cup Chunks(E(p_j))
  1. 生成 step answer:
a_j=LLMAnswerStep(c_j,q_j)

输出:当前 subquestion 的 answer-path pairs $AP_j={(a_j,p_j)}$。

直观解释:EWO 把“hyperedge 是否相连”改成“相连处的实体是否对当前问题有用”。这比简单 hyperedge overlap 更适合 n-ary relation,因为不同共享实体的证据价值并不相同。

7. Final Answer:从 completed DAGs 中选择一致答案

输入:completed DAG:

D_{comp}=(Q,L_H,AP)

计算链路:

  1. 按 DAG dependency 聚合每个 subquestion 的 answer-path pairs。
  2. 对每个 completed DAG 生成 candidate answer:
a(q)=LLMGenerate(q,D_{comp})
  1. LLM-based evaluation agent 检查候选答案是否与 reasoning path 一致。
  2. 选择 top-ranked answer:
a^*(q)=Judge(\mathcal{A}(q))

输出:最终答案和其对应的 reasoning path evidence。

直观解释:最终答案不是只看文本相似度,而是要和 completed DAG 上的路径证据一致。

Results

1. 主结果:PRoH 在五个 KHQA domain 上超过 HyperGraphRAG

PRoH-table1-main-results

Table 1 显示 PRoH 在 Medicine、Agriculture、CS、Legal、Mix 上整体优于 HyperGraphRAG:

  • PRoH F1:52.94、56.67、54.15、58.81、69.16。
  • HyperGraphRAG F1:35.35、33.89、31.30、43.81、48.71。
  • PRoH G-E:67.35、69.46、66.79、69.88、76.17。
  • 论文报告相对 HyperGraphRAG 平均提升:F1 +19.73%,G-E +8.41%。

解读:PRoH 的提升集中在 answer F1 和 generation evaluation,而 R-S 不总是最高。这说明它不是简单追求检索片段语义相似,而是通过路径和 DAG 让证据更服务最终推理。

2. 消融与搜索深度:目标 hyperedge、plan context、EWO 都有贡献

PRoH-table2-fig3-ablation-depth

Table 2 的 F1 消融显示:

  • 去掉 Target Hyperedge,Mix 从 69.39 降到 60.81,是最明显的单模块下降之一。
  • 去掉 Plan Context,Agriculture / CS / Mix 变为 53.70 / 53.67 / 64.59,说明 graph-aware planning 确实影响初始 DAG 质量。
  • 去掉 EWO Guide 后为 53.22 / 56.27 / 65.63,说明路径方向选择需要语义化 overlap,而不是只看结构连接。
  • w/o ALL 下降到 51.93 / 51.96 / 55.84,证明多个模块互补。

Figure 3 显示 $d_{max}=3$ 时 F1/G-E 达到峰值;继续增加深度会带来冗余上下文和轻微性能下降,同时平均实际深度 $d_{avg}$ 继续增加。

3. 长程多跳:3-6 hop 下优势更明显

PRoH-table3-long-range-results

Table 3 针对 long-range multi-hop QA:

  • PRoH F1:Medicine 51.26,Agriculture 81.01,CS 74.83,Legal 71.93,Mix 79.69。
  • HyperGraphRAG F1:Medicine 39.94,Agriculture 52.40,CS 29.95,Legal 38.45,Mix 64.55。
  • 论文报告平均 F1 +26.68%,CS 最高提升到 +44.87%。

解读:PRoH 的优势在长程多跳更强,符合它的设计假设:动态 DAG 和 EWO 路径搜索主要解决的是长链、分支和跨 hyperedge 组合问题。

4. 效率与 backbone:PRoH-L 降 token,较强 LLM 提升规划/检索质量

PRoH-table4-table5-efficiency-backbones

Table 4 比较 PRoH-L 与 HyperGraphRAG 的 token:

  • Medicine 少 6.54%,F1 +10.28。
  • Agriculture 少 30.07%,F1 +16.58。
  • CS 少 34.82%,F1 +15.31。
  • Legal token 增加 30.54%,但 F1 +7.59。
  • Mix 少 30.09%,F1 +5.10。

Table 5 显示 Qwen3 backbone 从 4B 到 80B,Agriculture / CS 的 F1 和 G-E 整体提高。解读上,PRoH 依赖 LLM 做 planning、path selection 和 final judge,因此模型规模会影响规划质量和路径筛选质量。

Limitations

  • Final answer generation 仍是最大误差来源:附录 Figure 7 报告 Final Answer Generation 占 43% error,Planning 占 33%,Reasoning State Search 和 Graph Anchoring 各 10%,Answer and Path Retrieval 约 5%。
  • Answer and Path Retrieval 是 token 大户:附录 Figure 6 显示该模块消耗最多 token,尤其是 LLM-based entity scoring 和 path selection。
  • 规划质量仍依赖 LLM:PRoH 把 planning 显式化,但没有训练 planner;错误 subquestion 或 dependency 仍会让搜索树扩大或偏离。
  • Anchor 仍是上游瓶颈:topic entity 和 target hyperedge 匹配错误会限制 plan context,进而影响整个 DAG。
  • 搜索成本与轨迹数量相关:BFS 在部分设置中 F1 更高,但 state visits 明显增多;论文选择 DFS 是性能/成本折中。
  • 实验主要围绕 KHQA domain,尚未证明在开放域文档 GraphRAG、动态增量图、多模态图或用户私有知识库中的泛化。
  • EWO 中的 LLMScore 和 path selection 仍是黑盒判断,缺少可学习的、可校准的路径效用模型。

Future Directions

  • 把 PRoH 的 DAG state search 变成可训练策略:对接 Graph-R1 - Agentic GraphRAG via End-to-end Reinforcement Learning 和 GraphRAG-R1 - Process-Constrained Reinforcement Learning for GraphRAG,用过程奖励优化 LLMSelectDirections、LLMSelectPaths 和 LLMGenerateNewDAG。
  • 做 query complexity routing:不是所有问题都需要 PRoH 级别的动态超图规划,可在 2026-06-09-Open-Problems 下比较 flat RAG、light graph、PRoH-style hypergraph planning 和 RL agentic graph environment。
  • 建立 evidence path utility:围绕 2026-06-09-Open-Problems,把 EWO、path score、support coverage、semantic shortcut rate、tail path miss 统一到一个路径效用诊断框架。
  • 做 planning-guided attribution:在 2026-06-09-Open-Problems 中记录 plan_context_graph、initial_reasoning_DAG、state=(D,i)、frontier F、answer_path_pairs、EWO、selected_directions、selected_paths、D_new、completed_DAGs、d_max、d_avg、n0、K、state visits 和 support gain。
  • 用可学习 scorer 替代部分 LLM judge:把 EWO entity score、direction choice、path acceptance 和 final answer consistency 分别蒸馏成轻量模型,降低 token 成本。
  • 将 PRoH 与 NaviRAG - Active Knowledge Navigation for RAG 对照:NaviRAG 处理 hierarchical document navigation,PRoH 处理 knowledge hypergraph traversal,两者可以统一为“局部 scope 选择 -> 分支展开 -> sufficiency stop”。

与本知识库的连接

一句话定位

PRoH 是把 Knowledge Hypergraph RAG 从静态相似度检索推进到“图感知规划 DAG + 状态空间推理 + EWO 路径搜索”的代表性工作,适合作为 GraphRAG 中 agentic planning、hypergraph traversal 和路径归因的核心参照。