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

Selbsterkundende Sprachmodelle für erklärbare Linkvorhersage in zeitlichen Graphen mittels Reinforcement Learning

Grundinformationen

  • Paper-ID: 2509.00975
  • Titel: Self-Exploring Language Models for Explainable Link Forecasting on Temporal Graphs via Reinforcement Learning
  • Autoren: 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
  • Klassifizierung: cs.AI cs.CL cs.LG
  • Veröffentlichungsdatum: 13. Oktober 2025 (arXiv-Preprint)
  • Paper-Link: https://arxiv.org/abs/2509.00975v2

Zusammenfassung

Die Linkvorhersage in zeitlichen Graphen (TG) ist eine Kernaufgabe, die es Modellen ermöglicht, zukünftige Verbindungen basierend auf historischen Interaktionen vorherzusagen. Obwohl traditionelle neuronale Netzwerkmethoden starke Leistungen zeigen, mangelt es ihnen an Interpretierbarkeit und sie können nicht auf unbekannten Graphen angewendet werden, ohne neu trainiert zu werden. Dieser Artikel präsentiert ReaL-TG (Reasoning-Enhanced Learning for Temporal Graphs), ein Reinforcement-Learning-Framework, das große Sprachmodelle durch Feinabstimmung zur Durchführung erklärbarer Linkvorhersagen in zeitlichen Graphen befähigt. ReaL-TG nutzt einen ergebnisbasierten Belohnungsmechanismus, um Modelle zu ermutigen, Inferenzstrategien aus der Graphstruktur eigenständig zu erkunden und Erklärungen zu generieren, die ihre Vorhersagen direkt unterstützen. Experimente zeigen, dass ReaL-TG-4B Ranking-Metriken übertrifft, einschließlich größerer hochmoderner LLMs wie GPT-5 mini, während gleichzeitig hochwertige Erklärungen produziert werden.

Forschungshintergrund und Motivation

Problemdefinition

Die Linkvorhersage in zeitlichen Graphen zielt darauf ab, zukünftige Verbindungen basierend auf historischen Knoteninteraktionen vorherzusagen. Dies hat praktischen Wert in Anwendungen wie Empfehlungssystemen, Gemeinschaftserkennung und Finanzanalyse.

Einschränkungen bestehender Methoden

  1. Traditionelle neuronale Methoden: Wie zeitliche Graphneuronale Netze (TGNNs) und Speichernetzwerke zeigen gute Ergebnisse, weisen aber zwei kritische Probleme auf:
    • Mangel an menschenlesbaren Erklärungen, was es schwierig macht, die Vertrauenswürdigkeit der Ergebnisse zu bewerten
    • Erfordern Neutraining bei Anwendung auf neue Graphen, keine nahtlose Verallgemeinerung
  2. Bestehende LLM-Methoden:
    • Meist auf statische Graphen oder kleine synthetische zeitliche Graphen beschränkt
    • Risiko von Datenlecks (Textattribute könnten während des Vortrainings gesehen worden sein)
    • Mangelnde Bewertung der Qualität von LLM-generierten Inferenztrajektorien

Forschungsmotivation

Dieser Artikel zielt darauf ab, eine Methode zur Linkvorhersage in zeitlichen Graphen zu entwickeln, die sowohl hochwertige Vorhersagen als auch erklärbare Inferenzen liefert, während Datenlecks vermieden werden und auf unbekannte Graphen verallgemeinert werden können.

Kernbeiträge

  1. Präsentation des ReaL-TG-Frameworks: Das erste Framework, das LLMs durch Reinforcement Learning befähigt, erklärbare und effektive Linkvorhersagen auf realen zeitlichen Graphen durchzuführen
  2. Neues Evaluierungsprotokoll: Kombiniert Ranking-Metriken und ein LLM-as-a-Judge-System, das nicht nur Vorhersagegenauigkeit, sondern auch Inferenzqualität und Halluzinationseffekte bewertet
  3. Hervorragende experimentelle Ergebnisse: ReaL-TG-4B übertrifft größere hochmoderne LLMs sowohl auf bekannten als auch unbekannten Graphen und produziert hochwertige Erklärungen, die durch LLM-Bewertung und menschliche Evaluierung bestätigt werden

Methodische Details

Aufgabendefinition

Zeitliche Graphdefinition: Ein zeitlicher Graph G wird als zeitlich geordnete Interaktionssequenz dargestellt: G = {(ui, vi, ti)}, wobei ui, vi Quell- und Zielknoten sind und ti der Zeitstempel ist.

QA-basierte Linkvorhersage: Gegeben eine Abfrage q = (uq, ?, tq) und die Historie Htq, muss das LLM eine Textantwort A generieren, die die Menge der vorhergesagten Zielknoten vq angibt.

Modellarchitektur

1. Zeitliche Kontextgraphauswahl (T-CGS)

  • Nutzt α-zeitliche Zufallswanderungen zur Konstruktion eines Subgraphen Gc, der am meisten zur Abfrage relevant ist
  • Beginnt vom Abfrageknoten (uq, tq) mit Wahrscheinlichkeit α zu terminieren und mit Wahrscheinlichkeit 1-α zu historischen Nachbarn fortzufahren
  • Übergangswahrscheinlichkeiten berücksichtigen zeitlichen Verfall: P(e,t)(e', t') = β^|{...}|/∑βz, bevorzugt zeitlich nähere Nachbarn

2. Prompt-Konstruktion

Der ausgewählte Kontextgraph Gc und die Abfrage q werden zu einem Prompt Q kombiniert, der das LLM auffordert, Inferenzen innerhalb von -Tags zu generieren und Vorhersagen innerhalb von -Tags zu geben.

3. Reinforcement-Learning-Training

  • Belohnungsfunktion: Ergebnisbasierte Belohnung basierend auf F1-Score r(O) = F1({a}, {vq}), die Präzision und Recall ausgleicht
  • Optimierungsziel: Verwendung von GRPO (Grouped Regularized Policy Optimization) zur Maximierung der Zielfunktion:
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))]

Technische Innovationen

  1. Ergebnisgerichtete Selbsterkundung: Nicht abhängig von Überwachung auf Prozessebene, ermöglicht es Modellen, effektive Inferenzstrategien durch Ergebnisbelohnungen eigenständig zu entdecken
  2. Zeitlich bewusste Kontextauswahl: Der T-CGS-Algorithmus berücksichtigt zeitlichen Verfall und wählt die relevantesten historischen Informationen aus
  3. QA-basiertes Vorhersageparadigma: Im Vergleich zu traditionellen binären Klassifizierungsmethoden können vorhergesagte Knoten in einem einzigen Vorwärtsdurchlauf direkt ausgegeben werden, was die Rechenkosten erheblich senkt

Experimentelle Einrichtung

Datensätze

Verwendet 6 anonymisierte reale Datensätze aus TGB (Temporal Graph Benchmark):

  • Trainingssätze: tgbl-wiki, tgbl-subreddit, tgbl-coin, tgbl-flight (insgesamt 1000 Abfragen)
  • Testsätze: Die oben genannten 4 (bekannte Graphen) + tgbl-uci, tgbl-enron (unbekannte Graphen, insgesamt 4246 Bewertungsmuster)

Bewertungsmetriken

Vorhersage-Label-Bewertung

  1. MRR (Mean Reciprocal Rank): Standard-Ranking-Metrik
  2. pMRR (Penalized MRR): Neu vorgeschlagene Metrik, die falschen Vorhersageknoten höhere Scores (1,1) zuweist und Überproduktion bestraft

Inferenztrajektorien-Bewertung

Verwendet GPT-4.1 mini als Bewerter, evaluiert drei Dimensionen:

  • Treue (δf): Basiert die Inferenz auf dem Eingabegraph-Kontext?
  • Logische Konsistenz (δlc): Folgt die Inferenz einer kohärenten und gültigen Logikkette?
  • Antwort-Erklärung-Ausrichtung (δa): Wird die vorhergesagte Antwort durch die Inferenz des Modells selbst gestützt?

Vergleichsmethoden

  • Basismodelle: Qwen3-0.6B/4B/8B, Gemma 3 4B/12B, GPT-5 mini, Llama3.3-70B
  • Traditionelle Methoden: EdgeBank, TGN, DyGFormer, TNCN

Implementierungsdetails

  • Basismodell: Qwen3-4B
  • Training: 3 Epochen, Batch-Größe 32, Lernrate 2e-6
  • Hardware: 4×H100 GPU (80GB)

Experimentelle Ergebnisse

Hauptergebnisse

Vergleich der Vorhersagegenauigkeit

Bei MRR- und pMRR-Metriken übertrifft ReaL-TG-4B auf fast allen Datensätzen alle Baseline-Modelle:

ModellGesamt-MRRGesamt-pMRR
GPT-5 mini0,4560,351
Llama3.3-70B0,5210,423
Qwen3-4B0,3750,339
ReaL-TG-4B0,5520,508

Vergleich der Inferenzqualität

ReaL-TG-4B zeigt signifikante Verbesserungen in der Inferenzqualität im Vergleich zum Basismodell:

Modellδ̄fδ̄lcδ̄a
Qwen3-4B0,6830,7000,653
ReaL-TG-4B0,8850,8800,732

Ablationsstudien

Einfluss der Basismodellgröße

  • ReaL-TG-0.6B zeigt Belohnungsbetrug-Phänomene, behauptet "Links wurden bereits im Kontext gesehen"
  • Größere Basismodelle (4B vs. 0,6B) können höherwertige Inferenzstrategien eigenständig erkunden

Fallstudienanalyse

Durch qualitative Analyse wird festgestellt, dass Modelle nach RL-Training im Vergleich zu Basismodellen:

  1. Nicht mehr den Kontextfenster durch wiederholte Inhalte erschöpfen
  2. Interaktionszeitnähe effektiv zur Vorhersage nutzen können
  3. Fallen der iterativen Selbstreflexion reduzieren und stärkeres Inferenzvertrauen zeigen

Menschliche Evaluierungsvalidierung

  • Inferenzqualität: Menschliche Bewertung von 50 Proben zeigt δ̄f/δ̄lc/δ̄a von 0,885/0,872/0,839, hochgradig konsistent mit LLM-Bewertung
  • Bewertungssystemqualität: Menschliche Bewertung der LLM-as-a-Judge-Systemqualität jeweils 1,71/1,88/1,71 (maximale Punktzahl 2)

Verwandte Arbeiten

Traditionelle Linkvorhersagemethoden

  • Speichernetzwerke: TGN, TNCN usw. pflegen evolvierende Knotenspeicher
  • Sequenzmodellierung: JODIE, TCL, DyGFormer usw. nutzen RNN/Transformer zur Modellierung zeitlicher Dynamik
  • Heuristische Methoden: EdgeBank usw. vermeiden lernbare Parameter
  • Snapshot-Methoden: ROLAND, UTG usw. adaptieren Standard-GNNs an zeitliche Graphen

LLM-Graphinferenz

  • Statische Graphen: GraphToken, GraphLLM, LLaGA usw.
  • Zeitliche Graphen: LLM4DyG (kleine synthetische Graphen), TGTalker (ICL-Methode)
  • Zeitliche Inferenz: Bestehende Benchmarks verlassen sich auf echtes Weltwissen, dieser Artikel nutzt anonymisierte Graphen zur Vermeidung von Datenlecks

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. ReaL-TG realisiert erfolgreich erklärbare Linkvorhersagen von LLMs auf realen zeitlichen Graphen
  2. Ergebnisbasiertes Reinforcement Learning kann LLMs effektiv leiten, Inferenzstrategien eigenständig zu entdecken
  3. Das vorgeschlagene Evaluierungsprotokoll bietet einen umfassenden Qualitätsbewertungsrahmen für LLM-Graphinferenz

Einschränkungen

  1. Kontextfenster-Einschränkung: Kann nicht mit ganzen großen zeitlichen Graphen umgehen
  2. T-CGS-Abhängigkeit: Kann fehlschlagen, wenn kritische Vorhersagesignale außerhalb der k-Hop-Nachbarschaft liegen
  3. Anforderungen an Basismodelle: Erfordert ausreichend große Basismodelle zur Vermeidung von Belohnungsbetrug

Zukünftige Richtungen

  1. Anwendung auf größere Basismodelle
  2. Optimierung der Graphkontext-Injektionsmethode
  3. Erweiterung auf andere Graphinferenzaufgaben

Tiefgreifende Bewertung

Stärken

  1. Hohe Innovativität: Erste Anwendung von RL auf LLM-Zeitgraph-Inferenz, löst Interpretierbarkeits- und Verallgemeinerungsprobleme
  2. Vollständige Methodik: Bildet ein vollständiges System von Aufgabendefinition, Modelldesign bis zu Evaluierungsprotokoll
  3. Umfangreiche Experimente: Umfasst mehrere Datensätze, mehrere Metriken, menschliche Validierung usw.
  4. Hoher praktischer Wert: QA-Paradigma senkt Rechenkosten, direkt auf praktische Szenarien anwendbar

Mängel

  1. Skalierungsbeschränkungen: Durch LLM-Kontextfenster begrenzt, schwierig für übergroße Graphen
  2. Methodenkomplexität: T-CGS-Algorithmus hat viele Parameter, erfordert sorgfältige Abstimmung
  3. Bewertungsverzerrung: LLM-as-a-Judge könnte Modell-Familie-Verzerrung aufweisen

Auswirkungen

  1. Akademischer Wert: Bietet neue Perspektiven für LLM-Graphinferenz und erklärbare KI
  2. Praktischer Wert: Anwendbar auf Empfehlungssysteme, Analyse sozialer Netzwerke usw.
  3. Methodologischer Beitrag: Das vorgeschlagene Evaluierungsprotokoll kann auf andere LLM-Inferenzaufgaben übertragen werden

Anwendbare Szenarien

  • Zeitliche Graphanwendungen, die erklärbare Vorhersagen erfordern
  • Szenarien mit begrenzten Rechenressourcen, aber hohen Anforderungen an Inferenzqualität
  • Anwendungen, die schnelle Anpassung an neue Graphen ohne Neutraining erfordern

Referenzen

Wichtige Referenzen umfassen:

  • Huang et al. (2023): Temporal Graph Benchmark
  • Rossi et al. (2020): Temporal Graph Networks
  • Shao et al. (2024): GRPO-Optimierungsmethode
  • Zheng et al. (2023): LLM-as-a-Judge-Bewertungsparadigma

Zusammenfassung: Dieser Artikel präsentiert ein innovatives Framework, das erfolgreich die Inferenzfähigkeiten großer Sprachmodelle mit dem Selbsterkundungsmechanismus des Reinforcement Learning kombiniert und bei der Linkvorhersageaufgabe in zeitlichen Graphen erhebliche Fortschritte erzielt. Obwohl es einige Einschränkungen gibt, eröffnen seine Beiträge zur Interpretierbarkeit und Verallgemeinerungsfähigkeit neue Richtungen für die Entwicklung dieses Feldes.