2025-11-13T20:01:11.522868

Self-Exploring Language Models for Explainable Link Forecasting on Temporal Graphs via Reinforcement Learning

Ding, Huang, Cao et al.

Forecasting future links is a central task in temporal graph (TG) reasoning, requiring models to leverage historical interactions to predict upcoming ones. Traditional neural approaches, such as temporal graph neural networks, achieve strong performance but lack explainability and cannot be applied to unseen graphs without retraining. Recent studies have begun to explore using large language models (LLMs) for graph reasoning, but most of them are constrained to static graphs or small synthetic TGs and lack the evaluation of the quality of reasoning traces generated by LLMs. In this work, we present Reasoning-Enhanced Learning for Temporal Graphs (ReaL-TG), a reinforcement learning framework that fine-tunes LLMs to perform explainable link forecasting on real-world TGs. ReaL-TG uses outcome-based reward to encourage models to self-explore reasoning strategies from graph structure and to produce explanations that directly justify their predictions. To enable evaluation on LLM-generated reasoning traces, we propose a new evaluation protocol combining ranking metrics with an LLM-as-a-Judge system that assesses both the quality of reasoning and the impact of hallucinations. Experiments with ReaL-TG-4B, obtained by fine-tuning Qwen3-4B under our framework, show that it outperforms much larger frontier LLMs, including GPT-5 mini, on ranking metrics, while producing high-quality explanations confirmed by both the LLM judge and human evaluation.

academic

強化学習による時系列グラフの説明可能なリンク予測のための自己探索言語モデル

基本情報

論文ID: 2509.00975
タイトル: Self-Exploring Language Models for Explainable Link Forecasting on Temporal Graphs via Reinforcement Learning
著者: Zifeng Ding, Shenyang Huang, Zeyu Cao, Emma Kondrup, Zachary Yang, Xingyue Huang, Yuan Sui, Zhangdie Yuan, Yuqicheng Zhu, Xianglong Hu, Yuan He, Farimah Poursafaei, Michael Bronstein, Andreas Vlachos
分類: cs.AI cs.CL cs.LG
発表日: 2025年10月13日 (arXiv プレプリント)
論文リンク: https://arxiv.org/abs/2509.00975v2

概要

時系列グラフ(TG)におけるリンク予測は、過去の相互作用を活用して将来の接続を予測する必要がある中核的なタスクです。従来のニューラルネットワーク手法は性能が優れている一方で、解釈可能性に欠け、未見のグラフに対して再学習なしに適用できません。本論文では、ReaL-TG(Reasoning-Enhanced Learning for Temporal Graphs)を提案します。これは大規模言語モデル(LLM)を微調整して説明可能な時系列グラフリンク予測を実行する強化学習フレームワークです。ReaL-TGは結果ベースの報酬メカニズムを使用して、モデルがグラフ構造から推論戦略を自律的に探索し、その予測を直接支持する説明を生成するよう促します。実験により、ReaL-TG-4BはGPT-5 miniを含むより大規模な最先端LLMを上回るランキング指標を達成しながら、高品質の説明を生成することが示されました。

研究背景と動機

問題定義

時系列グラフリンク予測は、過去のノード相互作用に基づいて将来の接続関係を予測することを目的としています。これは推奨システム、コミュニティ検出、金融分析などの実用的なアプリケーションで重要な価値があります。

既存手法の限界

従来のニューラル手法：時系列グラフニューラルネットワーク(TGNNs)やメモリネットワークなどは効果的ですが、2つの重要な問題があります：
- 人間が読める説明に欠け、結果の信頼性を評価することが困難
- 新しいグラフへの適用時に再学習が必要であり、シームレスな汎化ができない
既存のLLM手法：
- ほとんどが静的グラフまたは小規模な合成時系列グラフに限定
- データ漏洩のリスク(テキスト属性が事前学習時に見られている可能性)
- LLMが生成する推論軌跡の品質評価が不足

研究動機

本論文は、高品質の予測と解釈可能な推論の両方を提供できる時系列グラフリンク予測手法を開発することを目指しており、データ漏洩問題を回避しながら未見のグラフに汎化できます。

核心的貢献

ReaL-TGフレームワークの提案：強化学習を通じてLLMが実世界の時系列グラフ上で説明可能かつ効果的なリンク予測を実行できるようにする初めてのフレームワーク
新しい評価プロトコル：ランキング指標とLLM-as-a-Judge システムを組み合わせ、予測精度だけでなく推論品質と幻覚の影響も評価
優れた実験結果：ReaL-TG-4Bは見たことのあるグラフと未見のグラフの両方でより大規模な最先端LLMを上回り、LLM評価と人間評価で確認された高品質の説明を生成

方法の詳細

タスク定義

時系列グラフの定義：時系列グラフGは時系列順に並べられた相互作用シーケンスとして表現されます：G = {(ui, vi, ti)}、ここでui、viはソースノードとターゲットノード、tiはタイムスタンプです。

QA形式のリンク予測：クエリq = (uq, ?, tq)と履歴Htqが与えられた場合、LLMは予測されたターゲットノード集合vqを指定するテキスト回答Aを生成する必要があります。

モデルアーキテクチャ

1. 時系列コンテキストグラフ選択(T-CGS)

α-時系列ランダムウォークを使用してクエリに最も関連するサブグラフGcを構築
クエリノード(uq, tq)から開始し、確率αで終了、確率1-αで過去の隣接ノードに継続
遷移確率は時間減衰を考慮：P(e,t)(e', t') = β^|{...}|/∑βz、時間的に近い隣接ノードを優先

2. プロンプト構築

選択されたコンテキストグラフGcとクエリqを組み合わせてプロンプトQを構成し、LLMにタグ内で推論を生成し、タグ内で予測を提供するよう要求します。

3. 強化学習訓練

報酬関数：F1スコアベースの結果報酬 r(O) = F1({a}, {vq})、精度と再現率のバランスを取ります
最適化目標：GRPO(Grouped Regularized Policy Optimization)を使用して目的関数を最大化：

JGRPO(θ) = E[1/g ∑(min(πθ(Oi,j|Q,Oi,<j)/πθold(Oi,j|Q,Oi,<j) * Advi,j, 
                    clip(πθ(Oi,j|Q,Oi,<j)/πθold(Oi,j|Q,Oi,<j), 1-ε, 1+ε) * Advi,j) 
                 - γDKL(πθ||πref))]