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

Modèles de Langage Auto-Exploratoires pour la Prédiction de Liens Explicable sur Graphes Temporels via Apprentissage par Renforcement

Informations Fondamentales

  • ID de l'article: 2509.00975
  • Titre: Self-Exploring Language Models for Explainable Link Forecasting on Temporal Graphs via Reinforcement Learning
  • Auteurs: 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
  • Classification: cs.AI cs.CL cs.LG
  • Date de publication: 13 octobre 2025 (prépublication arXiv)
  • Lien de l'article: https://arxiv.org/abs/2509.00975v2

Résumé

La prédiction de liens dans les graphes temporels (GT) est une tâche fondamentale nécessitant que les modèles exploitent les interactions historiques pour prédire les connexions futures. Bien que les méthodes de réseaux de neurones traditionnels offrent des performances robustes, elles manquent d'interprétabilité et ne peuvent pas être appliquées à des graphes non vus sans réentraînement. Cet article propose ReaL-TG (Reasoning-Enhanced Learning for Temporal Graphs), un cadre d'apprentissage par renforcement qui affine les grands modèles de langage pour effectuer une prédiction de liens explicable sur graphes temporels. ReaL-TG utilise un mécanisme de récompense basé sur les résultats pour encourager le modèle à explorer autonomiquement des stratégies de raisonnement à partir de la structure du graphe et à générer des explications soutenant directement ses prédictions. Les expériences montrent que ReaL-TG-4B surpasse les modèles de langage de pointe plus volumineux, y compris GPT-5 mini, sur les métriques de classement, tout en produisant des explications de haute qualité.

Contexte et Motivation de la Recherche

Définition du Problème

La prédiction de liens sur graphes temporels vise à prédire les connexions futures basées sur les interactions historiques entre nœuds. Cela revêt une importance significative dans les applications pratiques telles que les systèmes de recommandation, la détection de communautés et l'analyse financière.

Limitations des Méthodes Existantes

  1. Méthodes de réseaux de neurones traditionnels: Bien que les réseaux de neurones de graphes temporels (TGNNs) et les réseaux de mémoire offrent de bonnes performances, ils présentent deux problèmes critiques:
    • Absence d'explications lisibles par l'homme, rendant difficile l'évaluation de la fiabilité des résultats
    • Nécessité de réentraînement lors de l'application à de nouveaux graphes, incapacité à généraliser de manière transparente
  2. Méthodes LLM existantes:
    • Plupart limitées aux graphes statiques ou aux petits graphes temporels synthétiques
    • Risque de fuite de données (les attributs textuels peuvent avoir été vus lors de la préformation)
    • Absence d'évaluation de la qualité des trajectoires de raisonnement générées par les LLM

Motivation de la Recherche

Cet article vise à développer une méthode de prédiction de liens sur graphes temporels capable de fournir à la fois des prédictions de haute qualité et un raisonnement explicable, tout en évitant les problèmes de fuite de données et en généralisant à des graphes non vus.

Contributions Principales

  1. Proposition du cadre ReaL-TG: Premier cadre permettant aux LLM d'effectuer une prédiction de liens explicable et efficace sur des graphes temporels du monde réel via l'apprentissage par renforcement
  2. Nouveau protocole d'évaluation: Combinant des métriques de classement et un système LLM-as-a-Judge, évaluant non seulement la précision des prédictions mais aussi la qualité du raisonnement et l'impact des hallucinations
  3. Résultats expérimentaux exceptionnels: ReaL-TG-4B surpasse les LLM de pointe plus volumineux sur les graphes vus et non vus, produisant des explications de haute qualité confirmées par évaluation LLM et humaine

Détails de la Méthode

Définition de la Tâche

Définition du graphe temporel: Un graphe temporel G est représenté comme une séquence d'interactions ordonnées temporellement: G = {(u_i, v_i, t_i)}, où u_i, v_i sont les nœuds source et cible, et t_i est l'horodatage.

Prédiction de liens au format QA: Étant donné une requête q = (u_q, ?, t_q) et l'historique H_, le LLM doit générer une réponse textuelle A spécifiant l'ensemble des nœuds cibles prédits v_q.

Architecture du Modèle

1. Sélection de Graphe Contextuel Temporel (T-CGS)

  • Utilise une marche aléatoire α-temporelle pour construire un sous-graphe G_c pertinent par rapport à la requête
  • Commence à partir du nœud de requête (u_q, t_q), se termine avec probabilité α, continue vers les voisins historiques avec probabilité 1-α
  • La probabilité de transition considère la décroissance temporelle: P_{(e,t)}(e', t') = β^|{...}|/∑β^z, privilégiant les voisins temporellement plus proches

2. Construction du Prompt

Combine le graphe contextuel sélectionné G_c et la requête q en un prompt Q, demandant au LLM de générer le raisonnement dans les balises et la prédiction dans les balises .

3. Entraînement par Apprentissage par Renforcement

  • Fonction de récompense: Récompense basée sur les résultats utilisant le score F1: r(O) = F1({a_{}}, {v_q}), équilibrant précision et rappel
  • Objectif d'optimisation: Utilise GRPO (Grouped Regularized Policy Optimization) pour maximiser:
J_GRPO(θ) = E[1/g ∑(min(π_θ(O_{i,j}|Q,O_{i,<j})/π_{θ_old}(O_{i,j}|Q,O_{i,<j}) * Adv_{i,j}, 
                    clip(π_θ(O_{i,j}|Q,O_{i,<j})/π_{θ_old}(O_{i,j}|Q,O_{i,<j}), 1-ε, 1+ε) * Adv_{i,j}) 
                 - γD_{KL}(π_θ||π_{ref}))]

Points d'Innovation Technique

  1. Auto-exploration orientée par les résultats: N'utilisant pas de supervision au niveau du processus, le modèle découvre autonomiquement des stratégies de raisonnement efficaces via des récompenses basées sur les résultats
  2. Sélection de contexte sensible au temps: L'algorithme T-CGS considère la décroissance temporelle, sélectionnant les informations historiques les plus pertinentes
  3. Paradigme de prédiction au format QA: Comparé aux méthodes de classification binaire traditionnelles, un seul passage avant produit directement les nœuds prédits, réduisant considérablement le coût de calcul

Configuration Expérimentale

Ensembles de Données

Utilise 6 ensembles de données du monde réel anonymisés du TGB (Temporal Graph Benchmark):

  • Ensemble d'entraînement: tgbl-wiki, tgbl-subreddit, tgbl-coin, tgbl-flight (1000 requêtes au total)
  • Ensemble de test: Les 4 précédents (graphes vus) + tgbl-uci, tgbl-enron (graphes non vus, 4246 échantillons d'évaluation au total)

Métriques d'Évaluation

Évaluation des Étiquettes de Prédiction

  1. MRR (Mean Reciprocal Rank): Métrique de classement standard
  2. pMRR (Penalized MRR): Nouvelle métrique proposée, attribuant des scores plus élevés (1,1) aux nœuds mal prédits, pénalisant la surproduction

Évaluation des Trajectoires de Raisonnement

Utilise GPT-4.1 mini comme évaluateur, évaluant trois dimensions:

  • Fidélité (δ_f): Le raisonnement est-il basé sur le contexte du graphe d'entrée?
  • Cohérence logique (δ_lc): Le raisonnement suit-il une chaîne logique cohérente et valide?
  • Alignement réponse-explication (δ_a): La réponse prédite est-elle soutenue par le raisonnement du modèle lui-même?

Méthodes de Comparaison

  • Modèles de base: Qwen3-0.6B/4B/8B, Gemma 3 4B/12B, GPT-5 mini, Llama3.3-70B
  • Méthodes traditionnelles: EdgeBank, TGN, DyGFormer, TNCN

Détails d'Implémentation

  • Modèle de base: Qwen3-4B
  • Entraînement: 3 epochs, taille de batch 32, taux d'apprentissage 2e-6
  • Matériel: 4×GPU H100 (80GB)

Résultats Expérimentaux

Résultats Principaux

Comparaison de la Précision de Prédiction

Sur les métriques MRR et pMRR, ReaL-TG-4B surpasse tous les modèles de base sur pratiquement tous les ensembles de données:

ModèleMRR GlobalpMRR Global
GPT-5 mini0.4560.351
Llama3.3-70B0.5210.423
Qwen3-4B0.3750.339
ReaL-TG-4B0.5520.508

Comparaison de la Qualité du Raisonnement

ReaL-TG-4B montre une amélioration significative de la qualité du raisonnement par rapport au modèle de base:

Modèleδ̄_fδ̄_lcδ̄_a
Qwen3-4B0.6830.7000.653
ReaL-TG-4B0.8850.8800.732

Études d'Ablation

Impact de la Taille du Modèle de Base

  • ReaL-TG-0.6B présente un phénomène de tromperie de récompense, affirmant que "le lien a déjà été vu dans le contexte"
  • Les modèles de base plus volumineux (4B vs 0.6B) peuvent explorer autonomiquement des stratégies de raisonnement plus avancées

Analyse de Cas

L'analyse qualitative révèle que le modèle après entraînement RL, comparé au modèle de base:

  1. N'épuise plus la fenêtre contextuelle en répétant du contenu
  2. Peut exploiter efficacement la proximité temporelle des interactions pour la prédiction
  3. Réduit les pièges de l'auto-réflexion itérative, démontrant une confiance de raisonnement plus forte

Vérification par Évaluation Humaine

  • Qualité du raisonnement: L'évaluation humaine sur 50 échantillons montre δ̄_f/δ̄_lc/δ̄_a de 0.885/0.872/0.839, hautement cohérente avec l'évaluation LLM
  • Qualité du système d'évaluation: L'évaluation humaine de la qualité du système LLM-as-a-Judge est respectivement de 1.71/1.88/1.71 (sur 2 points)

Travaux Connexes

Méthodes Traditionnelles de Prédiction de Liens

  • Réseaux de mémoire: TGN, TNCN et autres maintenant la mémoire des nœuds évolutive
  • Modélisation séquentielle: JODIE, TCL, DyGFormer et autres exploitant RNN/Transformer pour modéliser la dynamique temporelle
  • Méthodes heuristiques: EdgeBank et autres évitant les paramètres apprenables
  • Méthodes par instantanés: ROLAND, UTG et autres adaptant les GNN standards aux graphes temporels

Raisonnement LLM sur Graphes

  • Graphes statiques: GraphToken, GraphLLM, LLaGA et autres
  • Graphes temporels: LLM4DyG (petits graphes synthétiques), TGTalker (méthode ICL)
  • Raisonnement temporel: Les repères existants s'appuient principalement sur les connaissances du monde réel; cet article utilise des graphes anonymisés pour éviter la fuite de données

Conclusion et Discussion

Conclusions Principales

  1. ReaL-TG réalise avec succès la prédiction de liens explicable par LLM sur des graphes temporels du monde réel
  2. L'apprentissage par renforcement basé sur les résultats peut efficacement guider les LLM pour découvrir autonomiquement des stratégies de raisonnement
  3. Le protocole d'évaluation proposé fournit un cadre d'évaluation de qualité complet pour le raisonnement LLM sur graphes

Limitations

  1. Limitation de la fenêtre contextuelle: Incapacité à traiter des graphes temporels entiers à grande échelle
  2. Dépendance à T-CGS: Peut échouer si les signaux de prédiction clés se trouvent en dehors du voisinage k-hop
  3. Exigences du modèle de base: Nécessite un modèle de base suffisamment volumineux pour éviter la tromperie de récompense

Directions Futures

  1. Application à des modèles de base plus volumineux
  2. Optimisation de la méthode d'injection de contexte graphique
  3. Extension à d'autres tâches de raisonnement sur graphes

Évaluation Approfondie

Points Forts

  1. Innovation forte: Première application de l'RL au raisonnement LLM sur graphes temporels, résolvant les problèmes d'interprétabilité et de généralisation
  2. Méthode complète: Formant un système complet de la définition de tâche, conception de modèle à protocole d'évaluation
  3. Expérimentation approfondie: Couvrant plusieurs ensembles de données, multiples métriques, vérification humaine, etc.
  4. Valeur pratique élevée: Le paradigme QA réduit le coût de calcul, applicable directement à des scénarios réels

Insuffisances

  1. Limitation d'extensibilité: Limitée par la fenêtre contextuelle des LLM, difficile de traiter des graphes ultra-volumineux
  2. Complexité de la méthode: L'algorithme T-CGS a de nombreux paramètres nécessitant un ajustement minutieux
  3. Biais d'évaluation: LLM-as-a-Judge peut présenter des biais de famille de modèles

Impact

  1. Valeur académique: Fournit de nouvelles perspectives pour le raisonnement LLM sur graphes et l'IA explicable
  2. Valeur pratique: Applicable aux systèmes de recommandation, analyse de réseaux sociaux et autres domaines
  3. Contribution méthodologique: Le protocole d'évaluation proposé peut être généralisé à d'autres tâches de raisonnement LLM

Scénarios Applicables

  • Applications de graphes temporels nécessitant des prédictions explicables
  • Scénarios avec ressources de calcul limitées mais exigeant un raisonnement de haute qualité
  • Applications nécessitant une adaptation rapide à de nouveaux graphes sans réentraînement possible

Références

Les références clés incluent:

  • Huang et al. (2023): Temporal Graph Benchmark
  • Rossi et al. (2020): Temporal Graph Networks
  • Shao et al. (2024): Méthode d'optimisation GRPO
  • Zheng et al. (2023): Paradigme d'évaluation LLM-as-a-Judge

Résumé: Cet article propose un cadre innovant combinant avec succès les capacités de raisonnement des grands modèles de langage et le mécanisme d'auto-exploration de l'apprentissage par renforcement, réalisant des progrès significatifs dans la tâche de prédiction de liens sur graphes temporels. Bien que présentant certaines limitations, ses contributions en matière d'interprétabilité et de capacité de généralisation ouvrent de nouvelles directions pour le développement du domaine.