2025-11-12T08:22:09.411485

PRoH: Dynamic Planning and Reasoning over Knowledge Hypergraphs for Retrieval-Augmented Generation

Zai, Tan, Wang et al.
Knowledge Hypergraphs (KHs) have recently emerged as a knowledge representation for retrieval-augmented generation (RAG), offering a paradigm to model multi-entity relations into a structured form. However, existing KH-based RAG methods suffer from three major limitations: static retrieval planning, non-adaptive retrieval execution, and superficial use of KH structure and semantics, which constrain their ability to perform effective multi-hop question answering. To overcome these limitations, we propose PRoH, a dynamic Planning and Reasoning over Knowledge Hypergraphs framework. PRoH incorporates three core innovations: (i) a context-aware planning module that sketches the local KH neighborhood to guide structurally grounded reasoning plan generation; (ii) a structured question decomposition process that organizes subquestions as a dynamically evolving Directed Acyclic Graph (DAG) to enable adaptive, multi-trajectory exploration; and (iii) an Entity-Weighted Overlap (EWO)-guided reasoning path retrieval algorithm that prioritizes semantically coherent hyperedge traversals. Experiments across multiple domains demonstrate that PRoH achieves state-of-the-art performance, surpassing the prior SOTA model HyperGraphRAG by an average of 19.73% in F1 and 8.41% in Generation Evaluation (G-E) score, while maintaining strong robustness in long-range multi-hop reasoning tasks.
academic

PRoH: 知識ハイパーグラフ上の動的計画と推論による検索拡張生成

基本情報

  • 論文ID: 2510.12434
  • タイトル: PRoH: Dynamic Planning and Reasoning over Knowledge Hypergraphs for Retrieval-Augmented Generation
  • 著者: Xiangjun Zai, Xingyu Tan, Xiaoyang Wang, Qing Liu, Xiwei Xu, Wenjie Zhang
  • 分類: cs.CL (計算言語学)
  • 発表日: 2024年10月14日 (arXiv プレプリント)
  • 論文リンク: https://arxiv.org/abs/2510.12434

要旨

知識ハイパーグラフ(Knowledge Hypergraphs, KHs)は検索拡張生成(RAG)の新興知識表現形式として、複数実体関係を構造化形式でモデル化するパラダイムを提供しています。しかし、既存のKHベースのRAG手法には3つの主要な制限があります：静的検索計画、非適応的検索実行、およびKH構造セマンティクスの浅層的利用であり、これらは効果的な多ホップ質問応答の能力を制限しています。これらの制限を克服するため、本論文ではPRoH——動的知識ハイパーグラフ計画と推論フレームワークを提案します。PRoHは3つの核心的革新を含みます：(1)局所KH近傍をスケッチして構造化推論計画生成をガイドするコンテキスト認識計画モジュール；(2)部分問題を動的に進化する有向非環グラフ(DAG)に組織して適応的マルチトラック探索を実現する構造化問題分解プロセス；(3)実体加重重複(EWO)ガイド推論パス検索アルゴリズムであり、セマンティック一貫性のあるハイパーエッジトラバーサルを優先します。

研究背景と動機

問題定義

従来のRAGシステムは主にセマンティック類似性に依存して検索を行うため、多くの情報領域に固有の構造化関係知識をキャプチャできず、冗長またはノイズの多いコンテンツを頻繁に検索します。グラフベースのRAGは知識グラフ(KG)を通じてこの問題を改善していますが、既存フレームワークの大部分は2つの実体を含む関係のみをモデル化し、現実世界の多くの関係が本質的にn元であるという特性を無視しています。

重要性分析

現実世界の多くの関係は複数の実体を含みます。例えば、「Mario + Rabbids Kingdom Battleは任天堂とユービーアイソフト間の初の大型コラボレーション」という関係は3つの実体を同時に接続しています。これらのn元関係を複数の二元エッジに分解すると、必然的に重要な構造とセマンティック情報が失われます。

既存手法の制限

既存のKHベースのRAG手法には3つの主要な制限があります：

  1. 静的検索計画：事前定義されたハードコード化された検索パイプラインに依存し、クエリ内容またはグラフコンテキストに関わらず同じ操作シーケンスを適用
  2. 非適応的検索実行：一度限りの非反復的検索方式を採用し、中間推論結果を使用して検索を最適化できない
  3. グラフ構造セマンティクスの浅層的利用：ハイパーエッジを主に単純なリンクまたは関連テキストブロックへのアクセスルーティングメカニズムとして扱い、ハイパーエッジにエンコードされた豊かな関係セマンティクスを無視

核心的貢献

  1. PRoHフレームワークの提案：ハイパーグラフの表現力を十分に活用して多ホップ質問応答を行う動的知識ハイパーグラフRAGフレームワーク
  2. コンテキスト認識計画メカニズム：基盤となる知識ハイパーグラフをスケッチして実行可能な推論計画を生成する計画メカニズム
  3. EWOガイド推論パス検索戦略：知識ハイパーグラフに対する細粒度でセマンティック認識の探索戦略
  4. 顕著な性能向上：複数の知識領域でSOTA性能を達成し、F1スコアで平均19.73%向上、生成評価(G-E)スコアで8.41%向上

手法の詳細

タスク定義

問題qと知識ハイパーグラフH = (V, E)が与えられたとき、ハイパーグラフRAGはHから問題関連知識(事実集合F)を検索し、その後qとFに基づいて答えa(q)を生成する必要があります。

モデルアーキテクチャ

PRoHフレームワークは4つの主要コンポーネントで構成されています：

1. グラフ構築とインデックス作成

  • KH構築：HyperGraphRAGの手法を採用してドキュメントからハイパーエッジを抽出し、実体を識別してKHを構築
  • 同義語ハイパーエッジ拡張：3段階プロセスを通じて同義語ハイパーエッジを追加してグラフ接続性を強化：
    • 実体ペアのコサイン類似度を計算
    • 類似度部分グラフを形成して連結成分を計算
    • LLMを使用して同義実体を決定し、同義語ハイパーエッジを追加

2. グラフアンカリング

  • トピック実体識別：LLMを使用してキーワードを抽出し、類似度マッチングを通じて候補実体にリンク
  • ターゲットハイパーエッジマッチング：問題とセマンティック関連のあるハイパーエッジを検索
  • 問題部分グラフ構築：トピック実体とターゲットハイパーエッジのDmax-ホップ近傍の和集合を抽出

3. 推論計画初期化

  • 問題部分グラフスケッチ：計画コンテキストグラフHpを構築してLLMに構造化入力を提供
  • 初期推論計画生成：計画コンテキストに基づいて推論計画を生成
  • 推論DAG構築：推論計画をDAGとして表現し、Hasse簡約を適用して最小表現を取得

4. 推論プロセス

  • 状態空間探索：推論をDAG状態上の探索問題としてモデル化
  • 状態遷移：現在のレベルの部分問題を解決することで次の状態に遷移
  • 動的DAG最適化：中間答えに基づいて推論DAGを動的に最適化

技術的革新点

実体加重重複(EWO)スコアリング

EWOアルゴリズムは2段階の計算を通じて探索方向選択をガイドします：

  1. 実体スコアリング：
EW(v|qj) = {
    LLMScore(v, qj), if SE(v|qj) ≥ θemb
    0, otherwise
}
  1. ハイパーエッジスコアリング：
EWO(e'|q,e) = Aggregate({SE(v,q) | v ∈ V(e) ∩ V(e')})

構造化問題分解

  • 部分問題を線形シーケンスではなく動的に進化するDAGに組織
  • 複数の候補答えと複数の推論トラックの共存をサポート
  • ローカルエラーからの回復を許可

実験設定

データセット

  • KHQAデータセット：医学、農業、コンピュータサイエンス、法律、混合の5つの領域をカバー
  • 長距離問題拡張：各領域で追加で200個の3～6ホップの長距離問題を生成して多ホップ推論能力を評価

評価指標

  • F1スコア：答えの正確性を測定
  • 検索類似度(R-S)：検索コンテンツの品質を評価
  • 生成評価(G-E)：生成答えの品質を評価

比較手法

  • LLM-only：LLMの固有知識のみを使用
  • StandardRAG：従来のチャンクベースのRAG
  • PathRAG：パスベースのRAG手法
  • HippoRAG2：神経生物学にインスパイアされた長期記憶手法
  • HyperGraphRAG：現在のSOTA超グラフRAG手法

実装詳細

  • LLM：GPT-4o-mini
  • 埋め込みモデル：text-embedding-3-small
  • 主要パラメータ：計画深度dp=3、KH探索深度制限dmax=3、初期計画数n0=2

実験結果

主要結果

PRoHはすべての領域のF1およびG-EスコアでSOTA性能を達成しました：

領域HyperGraphRAG F1PRoH F1向上
医学35.3552.94+49.7%
農業33.8956.67+67.2%
コンピュータサイエンス31.3054.15+73.0%
法律43.8158.81+34.2%
混合48.7169.16+42.0%

アブレーション実験

アブレーション実験は各コンポーネントの重要性を示しています：

  • EWOガイダンスの削除：F1が最大5.3%低下
  • 同義語マージの削除：F1が最大5.2%低下
  • 計画コンテキストの削除：F1が最大5.8%低下
  • ターゲットハイパーエッジマッチングの削除：F1が最大8.6%低下

長距離推論性能

長距離マルチホップ質問応答タスクでは、PRoHは強力なロバスト性を示し、平均F1で26.68%向上し、コンピュータサイエンス領域で最高44.87%向上しました。

効率分析

PRoH-L変体はトークン使用量を大幅に削減しながら競争力のある性能を維持し、農業領域でトークンを30.07%削減しながらF1を16.58%向上させました。

関連研究

グラフベースRAG

既存のグラフベースRAG手法は知識グラフを通じてより正確な検索と関係認識推論を実現していますが、大部分は二元関係表現に限定されています。

知識ハイパーグラフRAG

HyperGraphRAGやHyper-RAGなどの初期システムは高次関係をキャプチャするためにハイパーエッジを抽出していますが、依然としてヒューリスティックな一度限りの検索パイプラインに依存し、コンテキスト認識と反復推論能力が不足しています。

結論と考察

主要結論

PRoHはコンテキスト認識計画、構造化反復問題分解、およびEWOガイド推論パス検索を導入することで、既存のKHベースRAG手法の3つの主要な制限を成功裏に解決し、複数の知識領域で顕著な性能向上を達成しました。

制限事項

  1. 計算複雑性：動的計画と状態空間探索は追加の計算オーバーヘッドをもたらす可能性があります
  2. パラメータ感度：複数のハイパーパラメータ(dp、dmax、n0など)は異なる領域に対して調整が必要です
  3. グラフ品質依存性：性能は初期知識ハイパーグラフの品質と完全性に大きく依存しています

今後の方向性

  1. より効率的な状態空間探索戦略の探索
  2. 適応的パラメータ調整メカニズムの研究
  3. より大規模な知識ハイパーグラフと複雑な推論タスクへの拡張

深層評価

利点

  1. 革新性が強い：動的計画と推論のKH-RAGフレームワークを初めて提案し、既存手法の核心的制限を解決
  2. 技術的貢献が顕著：EWOスコアリングメカニズムと構造化問題分解はハイパーグラフ特性に対する重要な革新
  3. 実験が充分：複数の領域と長距離推論タスクをカバーし、アブレーション実験が包括的
  4. 性能向上が明確：SOTA手法と比較して顕著で一貫した改善

不足点

  1. 複雑性が高い：手法は複数のモジュールとパラメータを含み、実際の展開の利便性に影響する可能性があります
  2. 計算コスト分析が不十分：トークン使用分析は提供されていますが、詳細な時間複雑度分析が不足しています
  3. 汎化性検証が限定的：実験は主に特定のKHQAデータセットに集中しています

影響力

  1. 学術的価値：KH-RAG領域に新しい研究方向と技術フレームワークを提供
  2. 実用的価値：複雑な多ホップ推論が必要なアプリケーションシナリオで重要な価値を持つ
  3. 再現性：詳細なアルゴリズム説明と実装詳細を提供

適用シナリオ

PRoHは特に以下に適しています：

  1. 複雑な多ホップ推論が必要な質問応答システム
  2. 複数実体関係を含む知識集約的タスク
  3. 推論パスの解釈可能性に要件があるアプリケーションシナリオ

参考文献

本論文は40篇の関連文献を引用しており、グラフベースRAG、知識ハイパーグラフ、多ホップ推論などの関連領域の重要な研究をカバーしており、研究に堅実な理論的基礎を提供しています。