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
  • Дата публикации: 13 октября 2025 г. (препринт arXiv)
  • Ссылка на статью: https://arxiv.org/abs/2509.00975v2

Аннотация

Прогнозирование связей на временных графах (TG) является ключевой задачей, требующей от моделей использования исторических взаимодействий для предсказания будущих соединений. Хотя традиционные нейросетевые методы демонстрируют высокую производительность, им не хватает интерпретируемости и они не могут применяться к неизвестным графам без переобучения. В данной работе предлагается ReaL-TG (Reasoning-Enhanced Learning for Temporal Graphs) — фреймворк обучения с подкреплением, который выполняет интерпретируемое прогнозирование связей на временных графах путём тонкой настройки больших языковых моделей. ReaL-TG использует механизм вознаграждения на основе результатов, побуждающий модель самостоятельно исследовать стратегии рассуждений из структуры графа и генерировать объяснения, непосредственно поддерживающие её предсказания. Экспериментальные результаты показывают, что ReaL-TG-4B превосходит более крупные передовые LLM, включая GPT-5 mini, по метрикам ранжирования, одновременно производя объяснения высокого качества.

Исследовательский контекст и мотивация

Определение проблемы

Прогнозирование связей на временных графах направлено на предсказание будущих соединений на основе исторических взаимодействий узлов. Это имеет значительную практическую ценность в рекомендательных системах, обнаружении сообществ и финансовом анализе.

Ограничения существующих методов

  1. Традиционные нейросетевые методы: Такие как временные графовые нейронные сети (TGNN), сетевые модели памяти и другие, хотя и показывают хорошие результаты, имеют две критические проблемы:
    • Отсутствие читаемых человеком объяснений, что затрудняет оценку надёжности результатов
    • Требуют переобучения при применении к новым графам, не обладают бесшовной обобщаемостью
  2. Существующие методы на основе LLM:
    • Большинство ограничены статическими графами или небольшими синтетическими временными графами
    • Существует риск утечки данных (текстовые атрибуты могут быть встречены во время предварительного обучения)
    • Отсутствует оценка качества траекторий рассуждений, генерируемых LLM

Исследовательская мотивация

Целью данной работы является разработка метода прогнозирования связей на временных графах, который одновременно обеспечивает высокое качество предсказаний, генерирует интерпретируемые рассуждения, избегает утечки данных и обобщается на неизвестные графы.

Основные вклады

  1. Предложение фреймворка ReaL-TG: Первый фреймворк, позволяющий LLM выполнять объяснимое и эффективное прогнозирование связей на реальных временных графах через обучение с подкреплением
  2. Новый протокол оценки: Сочетание метрик ранжирования и системы LLM-as-a-Judge, оценивающей не только точность предсказаний, но и качество рассуждений и влияние галлюцинаций
  3. Превосходные экспериментальные результаты: ReaL-TG-4B превосходит более крупные передовые LLM как на известных, так и на неизвестных графах, производя объяснения высокого качества, подтверждённые оценкой LLM и человеческой оценкой

Подробное описание метода

Определение задачи

Определение временного графа: Временный граф G представляется как последовательность взаимодействий, упорядоченных по времени: G = {(ui, vi, ti)}, где ui, vi — исходный и целевой узлы, ti — временная метка.

Прогнозирование связей в формате вопрос-ответ: Учитывая запрос q = (uq, ?, tq) и историю Htq, LLM должна сгенерировать текстовый ответ A, указывающий набор предсказанных целевых узлов vq.

Архитектура модели

1. Выбор временного контекстного графа (T-CGS)

  • Использует α-временное случайное блуждание для построения подграфа Gc, наиболее релевантного запросу
  • Начинается с узла запроса (uq, tq), завершается с вероятностью α, продолжается с вероятностью 1-α к историческим соседям
  • Вероятность переходов учитывает временное затухание: P(e,t)(e', t') = β^|{...}|/∑βz, отдавая предпочтение соседям, более близким по времени

2. Построение подсказки

Выбранный контекстный граф Gc и запрос q объединяются в подсказку Q, требуя от LLM генерировать рассуждения в тегах и давать предсказание в тегах .

3. Обучение с подкреплением

  • Функция вознаграждения: Вознаграждение на основе результатов 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))]

Технические инновации

  1. Самоисследование, ориентированное на результаты: Не зависит от надзора на уровне процесса, позволяя модели самостоятельно открывать эффективные стратегии рассуждений через вознаграждение за результаты
  2. Выбор контекста с учётом времени: Алгоритм T-CGS учитывает временное затухание и выбирает наиболее релевантную историческую информацию
  3. Парадигма предсказания в формате вопрос-ответ: По сравнению с традиционными методами бинарной классификации, прямой проход позволяет непосредственно вывести предсказанные узлы, значительно снижая вычислительные затраты

Экспериментальная установка

Наборы данных

Используются 6 анонимизированных реальных наборов данных из TGB (Temporal Graph Benchmark):

  • Обучающие наборы: tgbl-wiki, tgbl-subreddit, tgbl-coin, tgbl-flight (всего 1000 запросов)
  • Тестовые наборы: вышеперечисленные 4 (известные графы) + tgbl-uci, tgbl-enron (неизвестные графы, всего 4246 образцов оценки)

Метрики оценки

Оценка предсказанных меток

  1. MRR (Mean Reciprocal Rank): Стандартная метрика ранжирования
  2. pMRR (Penalized MRR): Новая предложенная метрика, назначающая более высокие баллы ошибочным предсказанным узлам (1.1), штрафующая чрезмерное генерирование

Оценка траектории рассуждений

Использует GPT-4.1 mini в качестве судьи для оценки трёх измерений:

  • Верность (δf): Основаны ли рассуждения на входном контексте графа
  • Логическая согласованность (δlc): Следуют ли рассуждения связной и действительной логической цепи
  • Выравнивание ответа и объяснения (δa): Поддерживается ли предсказанный ответ собственными рассуждениями модели

Методы сравнения

  • Базовые модели: Qwen3-0.6B/4B/8B, Gemma 3 4B/12B, GPT-5 mini, Llama3.3-70B
  • Традиционные методы: EdgeBank, TGN, DyGFormer, TNCN

Детали реализации

  • Базовая модель: Qwen3-4B
  • Обучение: 3 эпохи, размер пакета 32, скорость обучения 2e-6
  • Оборудование: 4×H100 GPU (80GB)

Экспериментальные результаты

Основные результаты

Сравнение точности предсказаний

По метрикам MRR и pMRR ReaL-TG-4B превосходит все базовые модели почти на всех наборах данных:

МодельОбщий MRRОбщий pMRR
GPT-5 mini0.4560.351
Llama3.3-70B0.5210.423
Qwen3-4B0.3750.339
ReaL-TG-4B0.5520.508

Сравнение качества рассуждений

ReaL-TG-4B демонстрирует значительное улучшение качества рассуждений по сравнению с базовой моделью:

Модельδ̄fδ̄lcδ̄a
Qwen3-4B0.6830.7000.653
ReaL-TG-4B0.8850.8800.732

Абляционные исследования

Влияние размера базовой модели

  • ReaL-TG-0.6B демонстрирует явление обмана вознаграждением, утверждая, что "связь уже встречена в контексте"
  • Более крупные базовые модели (4B против 0.6B) способны самостоятельно исследовать более продвинутые стратегии рассуждений

Анализ примеров

Качественный анализ показывает, что обученная моделью RL по сравнению с базовой моделью:

  1. Больше не исчерпывает контекстное окно повторением содержания
  2. Может эффективно использовать близость времени взаимодействия для предсказания
  3. Снижает попадание в ловушку итеративного самоотражения, демонстрируя более сильную уверенность в рассуждениях

Проверка человеческой оценкой

  • Качество рассуждений: Человеческая оценка 50 образцов показывает δ̄f/δ̄lc/δ̄a 0.885/0.872/0.839, высоко согласуясь с оценкой LLM
  • Качество системы судей: Человеческая оценка качества системы LLM-as-a-Judge составляет 1.71/1.88/1.71 (максимум 2 балла)

Связанные работы

Традиционные методы прогнозирования связей

  • Сетевые модели памяти: TGN, TNCN и другие, поддерживающие эволюционирующую память узлов
  • Моделирование последовательностей: JODIE, TCL, DyGFormer и другие, использующие RNN/Transformer для моделирования временной динамики
  • Эвристические методы: EdgeBank и другие, избегающие обучаемых параметров
  • Методы снимков: ROLAND, UTG и другие, адаптирующие стандартные GNN к временным графам

Рассуждения LLM на графах

  • Статические графы: GraphToken, GraphLLM, LLaGA и другие
  • Временные графы: LLM4DyG (небольшие синтетические графы), TGTalker (метод ICL)
  • Временные рассуждения: Существующие эталоны часто зависят от знаний реального мира; данная работа использует анонимизированные графы для избежания утечки данных

Заключение и обсуждение

Основные выводы

  1. ReaL-TG успешно реализует объяснимое прогнозирование связей LLM на реальных временных графах
  2. Обучение с подкреплением на основе результатов эффективно направляет LLM на самостоятельное открытие стратегий рассуждений
  3. Предложенный протокол оценки обеспечивает комплексную оценку качества для рассуждений LLM на графах

Ограничения

  1. Ограничение контекстного окна: Невозможно обработать весь крупномасштабный временный граф
  2. Зависимость от T-CGS: Может быть неэффективен, если критические сигналы предсказания находятся за пределами k-hop соседства
  3. Требования к базовой модели: Требуется достаточно крупная базовая модель для избежания обмана вознаграждением

Направления будущих исследований

  1. Применение к более крупным базовым моделям
  2. Оптимизация способов внедрения контекста графа
  3. Расширение на другие задачи рассуждений на графах

Глубокая оценка

Преимущества

  1. Высокая инновационность: Первое применение RL к рассуждениям LLM на временных графах, решающее проблемы интерпретируемости и обобщаемости
  2. Полнота метода: От определения задачи, проектирования модели до протокола оценки формирует полную систему
  3. Достаточные эксперименты: Охватывают несколько наборов данных, множество метрик, человеческую проверку и другое
  4. Высокая практическая ценность: Парадигма вопрос-ответ снижает вычислительные затраты, может быть непосредственно применена в практических сценариях

Недостатки

  1. Ограничения масштабируемости: Ограничено контекстным окном LLM, сложно обрабатывать сверхкрупномасштабные графы
  2. Сложность метода: Алгоритм T-CGS имеет множество параметров, требует тщательной настройки
  3. Смещение оценки: LLM-as-a-Judge может иметь смещение семейства моделей

Влияние

  1. Академическая ценность: Предоставляет новые идеи для рассуждений LLM на графах и объяснимого ИИ
  2. Практическая ценность: Может быть применена в рекомендательных системах, анализе социальных сетей и других областях
  3. Вклад методологии: Предложенный протокол оценки может быть обобщён на другие задачи рассуждений LLM

Применимые сценарии

  • Приложения временных графов, требующие объяснимых предсказаний
  • Сценарии с ограниченными вычислительными ресурсами, но требующие высокого качества рассуждений
  • Приложения, требующие быстрой адаптации к новым графам без переобучения

Библиография

Ключевые ссылки включают:

  • Huang et al. (2023): Temporal Graph Benchmark
  • Rossi et al. (2020): Temporal Graph Networks
  • Shao et al. (2024): Метод оптимизации GRPO
  • Zheng et al. (2023): Парадигма оценки LLM-as-a-Judge

Резюме: В данной работе предложен инновационный фреймворк, успешно сочетающий способности рассуждений больших языковых моделей с механизмом самоисследования обучения с подкреплением, достигший значительного прогресса в задаче прогнозирования связей на временных графах. Хотя существуют некоторые ограничения, вклад в интерпретируемость и способность обобщения открывает новые направления для развития данной области.