Chain-of-History Reasoning for Temporal Knowledge Graph Forecasting (2024)

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.

## introduction as a carrier of facts with temporal information, temporal knowledge graphs (tkgs) hold significant practical value across various applications @xcite . most advanced research on tkgs mainly focuses on predicting future facts occur at time t n based on given historical facts occur at time t with @xmath0. recent supervised methods @xcite @xcite primarily rely on graph neural figure 1 : an example of reasoning over tkg with @xcite and (b), we provide llms with different histories, which prompt llms to reason different answers for the predicted fact. networks (gnns) to capture structural dependencies within tkgs, yet they often fall short in effectively modeling semantic information. with the advent of large language models (llms), the potential for enhanced temporal reasoning across various tasks is becoming increasingly evident @xcite . @xcite the first attempt at tkg reasoning using llms @xcite , presenting histories to llms in textual form. despite these advancements, we contend that significant challenges remain unaddressed. firstly, the existing tkg prediction model with llms only focuses on the first-order histories, ignoring important high-order historical information. taking figure 1 as an example, llms aim to infer "germany will support whom at t 4 " with provided histories. the existing model provides llms with only first-order histories. in this case, llms are constrained to infer wrong answers to "denmark" 1 16144 50 75 100 125 150 33 37 mistral-7b (%) mixtral-8x7b (%) figure 2 : the performance (mrr (%)) of llms of two sizes based on different history lengths on tkg prediction. the provided histories contain both first-and second-order histories. the y-axis represents the mrr (%) value, and the x-axis denotes the total length of provided first-and second-order histories. the results are based on the commonly used tkg dataset icews14. and "russia" because given histories fail to encompass the correct answer. when supplied with more high-order histories, llms can utilize the history chain "@xmath1. secondly, llms struggle to maintain reasoning performance under heavy historical information loads. intuitively, we provide more comprehensive high-order histories for llms to infer. however, as shown in figure 2 , the performance of llms does not necessarily improve or remain stable with the increase in history length, instead experiencing a steep decline beyond a certain threshold of history length regardless of the model size. this indicates that over-complicated historical information may confuse llms @xcite , making llms hard to reason correct answers. thus, exploring ways to offer higher-order histories for llms effectively is a worthwhile investigation. thirdly, relying solely on the reasoning capabilities of llms still remains limited on tkg prediction. though llms possess unique semantic comprehension advantages in reasoning, they still struggle to achieve the same level of ability in capturing complex structural information as graphbased models. however, this unique advantage of llms precisely compensates for the shortcomings of graph-based models in modeling semantic information, thereby enhancing the performance of graph-based models on tkg prediction. to address the above issues, we propose a chainof-history (coh) reasoning method for tkg prediction. instead of providing llms with all histories at once, coh provides llms with high-order histories step-by-step. specifically, coh adopts llms to explore important high-order history chains step-by-step, and reason the answers to the query only based on inferred history chains in the last step. a two-step coh reasoning procedure is shown in figure 3 . this also can extend to multiple-step reasoning for complex situations. llms can continue inferring important secondorder history chains in step 2, then infer answers with third-order history chains in step 3, and so on. in this way, llms only need to process a limited quantity of histories at each step, preventing an overwhelming influx of complex information while effectively leveraging a more comprehensive set of high-order information. this approach enables llms to perform more accurate reasoning with higher-order information for tkg prediction. moreover, we design coh as a plug-and-play module for tkg reasoning. as shown in figure 3 , we fuse the predicted results obtained by llms and graph-based tkg models to make the final prediction more comprehensively. to summarize, the contributions of this paper can be listed as follows: temporal knowledge graph prediction. let e and r represent a set of entities and relations. a temporal knowledge graph (tkg) g can be defined as each g @xmath2. each fact is represented as a quadruple (s, r, o, t), in which s, @xmath3. given a query @xmath4, r q , ?, t q ) or @xmath5, r q , o q , t q ), tkg prediction task aims to predict the missing object entity or subject entity with historical kg sequence high-order history chains in tkgs. for each query @xmath6, r q , ?, t q ) to be predicted, we denote {(s q , r, o, t)|(s q , r, o, t) ∈ @xmath7. if (s q , r, o, t) is the first-order history of q, we denote histories in the form of (o, r, o ′ , t) as a set of second-order histories of q. the higherorder histories of q are deduced in this way. and we denote [(s q , r, o, t), (o, r, o ′ , t j )] as a second-order history chain of q, which consists of a first-order history of q and its associated second-order history of q. the higher-order history chains of q can be deduced in this way. ## chain-of-history reasoning over temporal knowledge graph for a given query @xmath8, r q , ?, t q ), coh predicts the answers by exploring history chains related to q step-by-step, then answers are fused with predicted results by graph-based tkg models to make the final prediction for q. in this section, we illustrate coh shown in figure 3 in detail. section 3.1 explains how to convert quadruples in tkgs into text formats suitable for llms. section 3.2 demonstrates how to properly provide histories from @xmath9. section 3.3 shows how to transform an-swers predicted by llms into scores and fuse them with the results from graph-based tkg models. ## experiments in this section, we conduct extensive experiments to evaluate and analyze coh on three typical datasets and three backbones for tkg prediction. details of datasets and backbones can be referred to appendix b and c, respectively. ## related works temporal knowledge graph forecasting with supervised models. as a carrier of real-world events extracted from news and documents @xcite @xcite , tkgs hold significant practical research value. previous classic methods include ghnn @xcite and know-evolve @xcite , which model the temporal information within tkgs by temporal point process (ttp). and cygnet @xcite proposes a copygeneration mechanism to explore patterns among repetitive histories. as gnns have shown promise in sequential modeling @xcite , recently, most supervised models @xcite @xcite @xcite for tkg prediction adopt gnns to capture the structural information within tkgs. in particular, zhang et al. consider both long-term @xcite ) and shortterm information. based on these, tango @xcite employs neural ordinary differential equations to build up continuous temporal information, cenet @xcite adopts contrastive learning to identify important non-historical entities, metatkg @xcite and metatkg++ @xcite explore the evolution patterns of events with meta-learning, and xerte @xcite proposes an explainable model by searching sub-graph in tkgs. besides, some works @xcite ) search significant paths with reinforcement learning, and tlogic @xcite extracts paths via temporal logic rules for tkg prediction. ## conclusion in this paper, we first analyze the shortcomings and challenges of the existing llm-based model about how to effectively provide comprehensive high-order historical information for llm. then we point out that relying solely on the reasoning capability of llms is still limited for tkg prediction. to resolve these issues, we propose coh reasoning which achieves effective utilization of high-order histories for llm. and we design coh as plugand-play, serving to complement and enhance the performance of graph-based models. extensive experimental results demonstrate the superiority of coh, and its effectiveness in enhancing the performance of graph-based models for tkg prediction.