📄 論文解説: Think-on-Graph — LLMエージェントによる知識グラフ上のマルチホップ推論

論文概要（Abstract）

本論文は、LLMをエージェントとして機能させ、知識グラフ（KG）上を反復的にビームサーチでトラバーサルするフレームワーク「Think-on-Graph (ToG)」を提案している。著者らは、各ステップでLLMが「次に探索すべき関係」を選択し、証拠を段階的に収集してから最終回答を生成する「探索→推論」の反復ループにより、従来のKGQA手法を上回る精度を達成したと報告している。

本記事は Zenn記事: LangGraph×GraphRAGハイブリッド検索で社内文書の複合質問精度を向上させる の深掘りです。

情報源

• arXiv ID: 2311.09869
• URL: https://arxiv.org/abs/2311.09869
• 著者: Jiashuo Sun, Chengjin Xu, Lumingyuan Tang, Saizhuo Wang, Chen Lin, Yeyun Gong, Lionel M. Ni, Heung-Yeung Shum, Jian Guo
• 発表年: 2023
• 分野: cs.CL, cs.AI

背景と動機（Background & Motivation）

知識グラフ質問応答（KGQA）において、マルチホップ推論 — 複数のエンティティと関係を順次たどって回答に到達するプロセス — は中核的な課題である。従来のアプローチは大きく2つに分かれていた。

1. KG埋め込み手法（TransE, ComplEx等）: KGの構造をベクトル空間に射影し、リンク予測を行う。スケーラブルだが、複雑なマルチホップパスの推論には弱い。
2. パス探索手法（GraftNet, TransferNet等）: KG上のパスを明示的に探索するが、探索空間の爆発に対処するためにヒューリスティクスに依存し、汎用性が低い。

著者らは、LLMの柔軟な推論能力とKGの構造化知識を動的に組み合わせる新しいパラダイムを提案している。具体的には、LLMがKGの「ナビゲーター」として機能し、各ステップで最も有望な探索方向を判断することで、探索空間の爆発を回避しつつ高精度なマルチホップ推論を実現する。

主要な貢献（Key Contributions）

• 貢献1: LLMをKG上のトラバーサルエージェントとして位置づけ、「探索（explore）→ 推論（reason）」の反復ループによるマルチホップ推論フレームワークの設計
• 貢献2: ビームサーチによる並列パス探索で、探索空間を効率的に管理しつつ多様な推論パスを維持
• 貢献3: WebQSP、CWQ、GrailQAの3つの標準KGQAベンチマークで、KGQA専用モデルおよびRAGベース手法を上回る精度を達成

技術的詳細（Technical Details）

Think-on-Graphのアルゴリズム

ToGの推論プロセスは、以下の4つのフェーズで構成される反復ループである。

Phase 1: エンティティ初期化

ユーザーのクエリ$q$から、出発点となるエンティティ$e_0$をKG内で特定する。エンティティリンキング（文字列マッチングまたはEmbedding類似度）を用いて、クエリ中のエンティティ言及をKGノードにマッピングする。

\[e_0 = \arg\max_{e \in V} \text{sim}(q, \text{name}(e))\]

Phase 2: 関係探索（Explore）

現在のエンティティ$e_t$から出発し、接続されている関係${r_1, r_2, …, r_k}$をKGから取得する。LLMに対して「クエリ$q$に回答するために、次にどの関係をたどるべきか」を判断させる。

\[r^* = \text{LLM}_{\text{select}}\left(q, e_t, \{r_1, ..., r_k\}, \text{history}\right)\]

ここで$\text{history}$はこれまでの探索パスの履歴であり、LLMがすでにたどったパスを繰り返さないようにするためのコンテキストとして機能する。

Phase 3: エンティティ到達

選択された関係$r^*$を通じて到達するエンティティ$e_{t+1}$を取得する。ビームサーチを適用する場合、上位$B$個の関係を並列に探索し、$B$個の異なるパスを維持する。

\[\text{Beam}_t = \{(e_{t+1}^{(1)}, \text{path}^{(1)}), ..., (e_{t+1}^{(B)}, \text{path}^{(B)})\}\]

ここで$B$はビーム幅であり、著者らは$B=3$をデフォルトとしている。

Phase 4: 推論判定（Reason）

現在までに収集した証拠（パス上のエンティティと関係の列）が、クエリに回答するのに十分かどうかをLLMに判定させる。

\[\text{decision} = \text{LLM}_{\text{judge}}\left(q, \text{evidence}_t\right) \in \{\text{sufficient}, \text{insufficient}\}\]

insufficientの場合、Phase 2に戻り次のホップの探索を継続する。sufficientの場合、収集した証拠を基に最終回答を生成する。

探索深度の制御

著者らは最大探索深度$D_{\max}$を設定し、$D_{\max}$ホップに達しても十分な証拠が得られない場合は、それまでの証拠で回答を生成する。

\[\text{Answer}(q) = \text{LLM}_{\text{generate}}\left(q, \bigcup_{t=0}^{\min(T, D_{\max})} \text{evidence}_t\right)\]

ここで$T$はsufficientと判定されたステップ数、$D_{\max}$は最大探索深度（著者らは$D_{\max}=3$を使用）である。

アルゴリズムの擬似コード

from dataclasses import dataclass

@dataclass
class ExplorationPath:
    """KG上の探索パス"""
    entities: list[str]      # たどったエンティティの列
    relations: list[str]     # たどった関係の列
    evidence: list[str]      # 収集した証拠テキスト
    score: float             # パスの推定スコア

def think_on_graph(
    query: str,
    knowledge_graph: object,
    llm: object,
    beam_width: int = 3,
    max_depth: int = 3,
) -> str:
    """Think-on-Graphによるマルチホップ推論

    Args:
        query: ユーザーのクエリ
        knowledge_graph: KGインスタンス (SPARQL/Cypher対応)
        llm: LLMインスタンス
        beam_width: ビームサーチの幅
        max_depth: 最大トラバーサル深度

    Returns:
        最終回答テキスト
    """
    # Phase 1: エンティティ初期化
    start_entity = entity_linking(query, knowledge_graph)
    beam = [ExplorationPath(
        entities=[start_entity],
        relations=[],
        evidence=[get_entity_description(start_entity, knowledge_graph)],
        score=1.0,
    )]

    for depth in range(max_depth):
        new_beam: list[ExplorationPath] = []

        for path in beam:
            current_entity = path.entities[-1]

            # Phase 2: 関係探索
            candidate_relations = knowledge_graph.get_relations(current_entity)
            selected = llm.select_relations(
                query=query,
                entity=current_entity,
                candidates=candidate_relations,
                history=path,
                top_k=beam_width,
            )

            for relation, score in selected:
                # Phase 3: エンティティ到達
                next_entities = knowledge_graph.traverse(current_entity, relation)
                for next_entity in next_entities[:1]:  # 各関係から1エンティティ
                    new_path = ExplorationPath(
                        entities=path.entities + [next_entity],
                        relations=path.relations + [relation],
                        evidence=path.evidence + [
                            f"{current_entity} --[{relation}]--> {next_entity}"
                        ],
                        score=path.score * score,
                    )
                    new_beam.append(new_path)

        # スコアでソートし上位beam_width個を保持
        new_beam.sort(key=lambda p: p.score, reverse=True)
        beam = new_beam[:beam_width]

        # Phase 4: 推論判定
        best_evidence = beam[0].evidence
        if llm.is_sufficient(query, best_evidence):
            break

    # 最終回答生成
    all_evidence = []
    for path in beam:
        all_evidence.extend(path.evidence)
    answer = llm.generate_answer(query, list(set(all_evidence)))
    return answer

実装のポイント（Implementation）

KG依存性: ToGは既存の高品質KG（Wikidata、Freebase等）を前提としており、KG構築コストは考慮されていない。社内ドキュメントに適用する場合、Zenn記事で紹介されているLLMGraphTransformer等を用いてKGを先に構築する必要がある。

ビーム幅の選択: 著者らは$B=3$をデフォルトとしているが、KGの関係数が多いドメインでは候補関係の数が爆発的に増加する。著者らはプロンプトに候補関係のサブセット（上位20個）のみを含めるフィルタリングを推奨している。

レイテンシ: 各ホップでLLMを2回呼び出す（関係選択 + 十分性判定）ため、3ホップの探索で最低6回のLLM呼び出しが必要になる。ビーム幅$B=3$の場合、並列化しても1クエリあたり3-5秒のレイテンシが発生する。

コード公開: GitHubリポジトリ（https://github.com/GasolSun36/ToG ）でApache 2.0ライセンスのもと公開されている。

Production Deployment Guide

AWS実装パターン（コスト最適化重視）

規模	月間リクエスト	推奨構成	月額コスト	主要サービス
Small	~3,000 (100/日)	Serverless	$100-250	Lambda + Bedrock + Neptune Serverless
Medium	~30,000 (1,000/日)	Hybrid	$600-1,500	ECS Fargate + Neptune + ElastiCache
Large	300,000+ (10,000/日)	Container	$4,000-10,000	EKS + Neptune + Redis Cluster

ToGは各ホップで複数回のLLM呼び出しを行うため、1クエリあたりのBedrock APIコストが他のGraphRAG手法より高くなる傾向がある。ビーム幅$B=3$、最大深度$D=3$の場合、1クエリあたり最大18回のLLM呼び出しが発生する。

コスト削減テクニック:

• モデル分離: 関係選択にClaude Haiku($0.25/MTok)、回答生成にSonnet($3/MTok)
• Prompt Caching: KGスキーマ情報をキャッシュして30-90%削減
• 早期終了: 1ホップで十分な証拠が得られた場合のLLM呼び出し削減
• Neptune Serverless: 最小1 NCUでアイドル時コスト最小化

コスト試算の注意事項: 上記は2026年2月時点のAWS ap-northeast-1料金に基づく概算値です。ToGのLLM呼び出し回数はクエリの複雑さにより大きく変動するため、実コストも変動幅が大きくなります。

Terraformインフラコード

# --- Neptune Serverless (KGストレージ) ---
resource "aws_neptune_cluster" "tog_kg" {
  cluster_identifier  = "tog-knowledge-graph"
  engine              = "neptune"
  serverless_v2_scaling_configuration {
    min_capacity = 1.0
    max_capacity = 8.0  # マルチホップ探索のピーク負荷対応
  }
  iam_database_authentication_enabled = true
  storage_encrypted                   = true
}

# --- Lambda (ToG推論エンジン) ---
resource "aws_lambda_function" "tog_reasoning" {
  function_name = "tog-multi-hop-reasoning"
  role          = aws_iam_role.lambda_tog.arn
  handler       = "index.handler"
  runtime       = "python3.12"
  timeout       = 120  # マルチホップ探索のため長めに設定
  memory_size   = 2048

  environment {
    variables = {
      NEPTUNE_ENDPOINT    = aws_neptune_cluster.tog_kg.endpoint
      BEDROCK_HAIKU_ID    = "anthropic.claude-3-5-haiku-20241022-v1:0"
      BEDROCK_SONNET_ID   = "anthropic.claude-sonnet-4-6-20250929-v1:0"
      BEAM_WIDTH          = "3"
      MAX_DEPTH           = "3"
    }
  }
}

# --- CloudWatch コスト監視 ---
resource "aws_cloudwatch_metric_alarm" "bedrock_token_spike" {
  alarm_name          = "tog-bedrock-token-spike"
  comparison_operator = "GreaterThanThreshold"
  evaluation_periods  = 1
  metric_name         = "Duration"
  namespace           = "AWS/Lambda"
  period              = 3600
  statistic           = "Sum"
  threshold           = 300000  # 5分/時間超過（多数のLLM呼び出し）
}

コスト最適化チェックリスト

• モデル分離: 関係選択→Haiku、回答生成→Sonnet
• Prompt Caching: KGスキーマ・探索履歴のキャッシュ
• 早期終了: 十分な証拠で探索打ち切り
• ビーム幅削減: 単純クエリは$B=1$で十分
• Neptune Serverless: 最小NCU設定
• Lambda タイムアウト: クエリ複雑度に応じた動的調整
• AWS Budgets: 月額予算設定（ToGはLLM呼び出し回数が多いため注意）
• CloudWatch: Lambda実行時間とBedrock API呼び出し回数の監視

実験結果（Results）

著者らはWebQSP、CWQ、GrailQAの3つの標準KGQAベンチマークで評価を行っている（論文Table 1, 2より）。

データセット	指標	KGNN	TransferNet	KD-CoT	ToG (GPT-3.5)	ToG (GPT-4)
WebQSP	Hits@1	73.1%	76.3%	73.5%	76.2%	82.9%
CWQ	Hits@1	-	64.2%	58.3%	68.1%	76.4%
GrailQA	F1	-	-	-	73.8%	80.1%

著者らは、ToG (GPT-4) が全3ベンチマークでKGQA専用モデル（KGNN、TransferNet）およびRAGベース手法（KD-CoT）を上回ったと報告している。特にCWQは複雑なマルチホップ質問を含むベンチマークであり、ToGのビームサーチによる並列パス探索が有効に機能したと著者らは分析している。

著者らが認めている制約: ToGは既存の高品質KGを前提としており、KGの品質が低い場合は探索パスの質が著しく低下する。また、KGのカバレッジ外の質問（KGに該当エンティティが存在しない場合）には回答できない。

実運用への応用（Practical Applications）

Zenn記事のLangGraph×GraphRAGハイブリッド検索との関連では、ToGのアルゴリズムはグラフ検索ノード（search_graph関数）の内部実装として活用できる。

クエリルーターとの連携: Zenn記事のルーターで「graph」と判定されたマルチホップクエリ（「田中さんが担当するプロジェクトで使っている技術スタックは？」）に対して、ToGの反復探索を適用する。route_searchの条件分岐で、GraphCypherQAChainの代わりにToGアルゴリズムを呼び出す構成が考えられる。

自己修正ループとの統合: Zenn記事の自己修正ループ（evaluate_answer → rewrite_query）と、ToGの「十分性判定」（Phase 4）は機能的に重複する。ToGの判定をLangGraphの条件分岐に組み込み、ToG内部の判定結果をそのまま自己修正ループの制御に利用することで、冗長なLLM呼び出しを削減できる。

レイテンシの考慮: ToGは1クエリあたり複数回のLLM呼び出しを要するため、Zenn記事で紹介されているモデル分離パターン（Haiku + Sonnet）の適用が重要になる。関係選択とナビゲーションにHaikuを使用し、最終回答生成にのみSonnetを使用する構成が推奨される。

関連研究（Related Work）

• KD-CoT (Wang et al., 2023): Chain-of-Thoughtを用いてKG上の推論を行う手法。ToGと異なり、固定的なプロンプトテンプレートに依存するため、推論パスの動的選択ができない。
• StructGPT (Jiang et al., 2023): 構造化データ（KG、テーブル）に対してLLMを適用するフレームワーク。ToGと同様にLLMをエージェントとして使用するが、ビームサーチによる並列探索は行わない。
• GraphRAG (Edge et al., 2024): コミュニティ検出ベースのGraphRAG。ToGはエンティティレベルのトラバーサルに特化しており、グローバル要約の機能は持たない。両者は補完的に使用できる。

まとめと今後の展望

Think-on-Graph (ToG) は、LLMをKG上のナビゲーションエージェントとして活用することで、マルチホップ推論の精度を大幅に向上させた手法である。著者らの実験ではWebQSP Hits@1 82.9%を達成しており、従来のKGQA専用モデルを上回る結果を報告している。

ただし、既存の高品質KGを前提とする点、マルチホップ探索のレイテンシが大きい点は実運用上の課題として残る。Zenn記事で紹介されているLLMGraphTransformerによるKG自動構築と組み合わせ、LangGraphの条件分岐でToGを「graph」ルートの推論エンジンとして組み込む構成が、実用的なアーキテクチャとして有望である。

参考文献

• arXiv: https://arxiv.org/abs/2311.09869
• Code: https://github.com/GasolSun36/ToG
• Related Zenn article: https://zenn.dev/0h_n0/articles/f894fb3fa04a59