Chain-of-History Reasoning for Temporal Knowledge Graph Forecasting

Yuwei Xia, Ding Wang, Qiang Liu, Liang Wang, Shu Wu, Xiao-Yu Zhang

TL;DR

This paper introduces Chain-of-History (CoH) reasoning, a novel method to improve Temporal Knowledge Graph (TKG) forecasting by enabling Large Language Models (LLMs) to effectively utilize high-order historical information. CoH addresses LLMs' limitations in handling complex historical data and their weaker structural reasoning compared to graph-based models, by acting as a plug-and-play module to enhance existing TKG prediction systems.

What Problem Does This Paper Address?

Temporal Knowledge Graphs (TKGs) store facts that evolve over time, and predicting future facts from historical data is a crucial task with applications ranging from event forecasting to recommendation systems. While traditional graph-based models excel at capturing the structural relationships within TKGs, they often struggle with the semantic nuances of the data. The recent advent of Large Language Models (LLMs) offers a promising avenue for TKG forecasting due to their strong semantic understanding. However, existing LLM-based approaches face several challenges:

  1. Limited Historical Context: They primarily rely on "first-order" historical facts (events directly preceding the prediction time), ignoring potentially crucial "high-order" historical information that could provide deeper insights.
  2. Information Overload: LLMs can struggle to maintain optimal reasoning performance when presented with a large volume of historical data, leading to performance degradation.
  3. Structural Reasoning Gap: While LLMs are strong in semantic reasoning, they are not as adept as graph-based models at capturing complex structural dependencies within TKGs.

This paper aims to bridge these gaps by developing a method that allows LLMs to leverage rich, high-order historical information in a structured, step-by-step manner and to synergize with graph-based models.

Methods

The core innovation is the Chain-of-History (CoH) reasoning method. Instead of feeding all historical data to the LLM at once, CoH breaks down the reasoning process into multiple steps.

  • Step-by-Step High-Order History Exploration: In each step, LLMs are prompted to identify the most important historical events or chains of events that are relevant to the query. This process iteratively builds "history chains" of increasing order. For example, in Step 1, LLMs identify key first-order histories. In Step 2, they use these to infer important second-order history chains, and so on. This approach prevents information overload by processing history in manageable chunks.
  • Textual Representation: TKGs are converted into natural language sentences to be understood by LLMs. Time information is abstracted to prevent LLMs from relying on their pre-existing knowledge.
  • Plug-and-Play Module: CoH is designed to be a flexible module that can enhance existing graph-based TKG prediction models. It fuses the predictions made by the LLM with those from a graph-based model. The LLM's output (ranked by probability) is converted into scores, which are then combined with graph-based model scores using a weighted average.

Datasets

The authors evaluated their method on three widely used Temporal Knowledge Graph datasets:

  • ICEWS14
  • ICEWS18
  • ICEWS05-15

These datasets are sourced from the Integrated Crisis Early Warning System (ICEWS) and document events over various time periods. No new benchmarks were introduced.

Key Insights and Ideas

  • High-order history is crucial: The paper strongly demonstrates that simply providing first-order history is insufficient for effective TKG forecasting. LLMs can significantly improve their predictions by reasoning over progressively higher-order historical chains.
  • LLMs can be "chunked" for better reasoning: The step-by-step approach of CoH is key to overcoming LLMs' limitations with large inputs. By breaking down the reasoning, LLMs can handle more complex historical contexts without performance degradation.
  • LLMs and GNNs are complementary: The paper highlights that LLMs' semantic reasoning and graph-based models' structural reasoning are distinct but complementary. CoH effectively leverages this by fusing their outputs, leading to better overall performance than either approach alone.
  • LLMs can identify relevant historical facts: The case studies show that LLMs can intelligently select crucial historical events from a large set, demonstrating their ability to discern semantically important information.

Key Results

  • Improved LLM Performance: CoH significantly outperforms a baseline LLM approach (ICL) that only uses first-order histories, showing relative improvements of up to 11.30% in MRR on the ICEWS18 dataset.
  • Enhanced Graph-Based Models: When plugged into existing graph-based TKG models (RE-NET, RE-GCN, TiRGN), CoH consistently boosts performance across all metrics (MRR, Hit@1, Hit@3, Hit@10) on all three datasets. For instance, RE-NET + CoH showed relative improvements of up to 4.34% in MRR.
  • Effectiveness of Step-by-Step Reasoning: Ablation studies confirm that the step-by-step reasoning mechanism is crucial for CoH's success, outperforming a version that skips the initial step-by-step history inference.
  • Importance of Ranking: Shuffling the order of LLM-predicted answers significantly degrades performance, indicating that the LLM's probability ranking is valuable for the fusion process.

Limitations and Future Work

  • Inference Complexity: CoH requires multiple LLM invocations, increasing the overall inference time and complexity.
  • Fixed Fusion Weights: The current fusion of LLM and graph-based model scores uses a fixed weight (w), which cannot adapt to different queries. The authors suggest that developing an adaptive fusion strategy that learns optimal weights for different queries would be a valuable future direction.
  • Prior Knowledge Impact: While anonymization experiments show that LLMs' prior knowledge aids performance, the exact nature and extent of this influence warrant further investigation.
  • Data Leakage Mitigation: The authors acknowledge the potential for data leakage from LLMs and describe efforts to mitigate it by conversing with the LLM and excluding known facts from the test set. However, this remains an ongoing challenge in LLM research.

Summary updated

Abstract

Temporal Knowledge Graph (TKG) forecasting aims to predict future facts based on given histories. Most recent graph-based models excel at capturing structural information within TKGs but lack semantic comprehension abilities. Nowadays, with the surge of LLMs, the LLM-based TKG prediction model has emerged. However, the existing LLM-based model exhibits three shortcomings: (1) It only focuses on the first-order history for prediction while ignoring high-order historical information, resulting in the provided information for LLMs being extremely limited. (2) LLMs struggle with optimal reasoning performance under heavy historical information loads. (3) For TKG prediction, the temporal reasoning capability of LLM alone is limited. To address the first two challenges, we propose Chain-of-History (CoH) reasoning which explores high-order histories step-by-step, achieving effective utilization of high-order historical information for LLMs on TKG prediction. To address the third issue, we design CoH as a plug-and-play module to enhance the performance of graph-based models for TKG prediction. Extensive experiments on three datasets and backbones demonstrate the effectiveness of CoH.
BibTeX
@inproceedings{xia2024chain,
  author = {Yuwei Xia and Ding Wang and Qiang Liu and Liang Wang and Shu Wu and Xiao-Yu Zhang},
  title = {{Chain-of-History Reasoning for Temporal Knowledge Graph Forecasting}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2024},
  doi = {10.18653/v1/2024.findings-acl.955},
}
Figure