Paths-over-Graph: Knowledge Graph Empowered Large Language Model Reasoning
| 項目 | 内容 |
|---|---|
| 論文ID | P51 |
| 区分・分類 | 論文・構造化知識の利用 |
| 著者・所属 | Xingyu Tan（University of New South Wales／Data61, CSIRO）、Xiaoyang Wang（University of New South Wales、責任著者）、Qing Liu（Data61, CSIRO）、Xiwei Xu（Data61, CSIRO）、Xin Yuan（Data61, CSIRO）、Wenjie Zhang（University of New South Wales） |
| 発表先 | Proceedings of the ACM Web Conference (WWW 2025) |
| 発表日 | 2025-04-22 |
| 引用数 | 62（OpenAlex 2026-10-06時点） |
| 言語 | 英語 |
| URL | https://doi.org/10.1145/3696410.3714892 |
| 論文/pdf/P51.pdf | |
| 読んだ範囲 | 全文 |
論文タイプ
新技術。KG を使って LLM に推論させる新しい手法 PoG を提案し、5つの KGQA データセットで評価している。
研究の目標
LLM は、複雑な推論ではハルシネーションを起こし、学習データにない知識には答えられない。KG を外部知識として使う既存手法（ToG、MindMap 等）には、著者が挙げる課題が3つある。 1. 1-hop 近傍を順にたどるため、multi-hop 推論でもっともらしい誤答を出したり、正解を早い段階で除外したりする 2. 質問に複数のトピックエンティティがあっても別々に探索し、エンティティ同士のつながりを見ない 3. グラフ構造を使わず、トリプルをテキストにして LLM に入力している
PoG は、トリプルではなく「全トピックエンティティを含む推論パス」を LLM に渡す。これで、忠実で解釈可能な推論を目指す。
技術的なやり方
学習なしのプロンプトベース手法で、LLM や KG を差し替えて使える（plug-and-play）。
| 段階 | 内容 |
|---|---|
| Initialization | LLM が質問からトピックエンティティを抜き出し、BERT 系の類似度で KG 上のエンティティに対応付ける。各エンティティから D_max-hop 以内の部分グラフを SPARQL で取得する。ノードと関係をクラスタリングして supernode にまとめ、双方向 BFS によるグラフ縮約で不要部分を削る。LLM は質問を split question に分け、エンティティの順序と答えの位置を示す「LLM indicator」と予測深さ D_predict を出す |
| Exploration（3段階） | ① Topic entity path：D_predict から始めて、全トピックエンティティを indicator の順に含むパスを探す。足りなければ深さを1ずつ増やす。② LLM supplement path：LLM が自分の知識で答えの候補を予測し、それを加えてパスを探す。③ Node expand：未訪問のエンティティを 1-hop 広げ、既存のパスにつなげる |
| Path Pruning（3段階ビームサーチ） | Fuzzy selection（SentenceBERT で indicator と各パスの類似度を計算し上位 W1 本を残す）→ Precise path selection（LLM が上位 W_max 本を選ぶ）→ Branch reduced selection（パスの先頭から1ステップずつ絞り込み、トークンを減らす）。この組み合わせで4つの戦略を選べる |
| Question Answering | LLM がパスを要約する（Path Summarizing）。そのパスで split question と元の質問に答えられるかを判定し、答えられれば回答、足りなければ次の探索段階へ進む。最後まで足りないときは LLM 自身の知識も使って答える |
実験設定は次のとおり。 - データセット：CWQ、WebQSP、GrailQA、SimpleQuestions、WebQuestions - KG：Freebase - LLM：GPT-3.5-Turbo、GPT-4 - 評価指標：Hits@1 - 既定設定：Fuzzy + Precise Path Selection、W1=80、W_max=D_max=3 - 比較用の変種：PoG-E（クラスタ化した各エッジから関係を1つランダムに選ぶ）
結果
Table 1（Hits@1、%）
| 手法 | CWQ | WebQSP | GrailQA | SimpleQuestions | WebQuestions |
|---|---|---|---|---|---|
| Prior FT SOTA | 70.4 | 85.7 | 75.4 | 85.8 | 56.3 |
| ToG（GPT-3.5-Turbo） | 58.9 | 76.2 | 68.7 | 53.6 | 54.5 |
| ToG（GPT-4） | 69.5 | 82.6 | 81.4 | 66.7 | 57.9 |
| PoG（GPT-3.5-Turbo） | 74.7 | 93.9 | 91.6 | 80.8 | 81.8 |
| PoG（GPT-4） | 81.4 | 96.7 | 94.4 | 84.0 | 84.6 |
- 精度：GPT-3.5 と GPT-4 の両方で、ToG を平均18.9%上回る。GPT-3.5 の PoG が GPT-4 の ToG を最大23.9%上回る。GPT-4 の PoG は、multi-hop と open-domain のデータセットで fine-tuned SOTA を平均17.3%、最大28.3%（WebQuestions）上回る
- グラフ縮約：探索前に1問あたりの平均エンティティ数を最大54%（CWQ）減らす
- ビームサーチ戦略：Branch reduced selection は、入力トークンを50%以上減らしつつ、精度の差は±2%に収まる（CWQ：216,884→101,455トークン、精度 81.4%→79.3%）
- Path Summarizing：精度が最大10%上がり（CWQ、PoG-E）、入力トークンが最大36%減る（WebQSP）
- LLM 呼び出し回数（1問あたり平均）：PoG は6.1〜10.7回、ToG は8.7〜11.2回。GrailQA では最大40%減る
- 答えの根拠：正答のうち KG のパスだけで答えたものが77〜95%。KG で足りず LLM の知識で補ったものが最大14%。LLM の予測を KG で検証したものが最大9%
- 探索深さ：D_max を深くすると精度は上がるが、3を超えると伸びが小さくなる
限界・課題
限界を述べた専用の節はない。本文で著者が述べている点は次のとおり。 - D_max を深くしすぎると、LLM のハルシネーションが起き、長い推論パスを扱いにくくなる - GrailQA の multi-entity 質問は精度がやや低い（70.7%）。原因は、一部の質問でトピックエンティティが KG と対応付けられないこと - より強い LLM（GPT-4）では、出力のフォーマットエラーが増える - 精度の高い設定ほど実行時間が延びる（CWQ で ToG は78.7秒、PoG は118.9秒）
要点
KG のトリプルではなく、「全トピックエンティティをつなぐ推論パス」を LLM に渡す、学習なしの KGQA 手法。 グラフ構造による枝刈りと3段階ビームサーチで候補を絞る。 ToG より少ない LLM 呼び出しで、5つのデータセットすべてで ToG の Hits@1 を上回った。