T ime T raveler: Reinforcement Learning for Temporal Knowledge Graph Forecasting (2021)

Abstract: Temporal knowledge graph (TKG) reasoning is a crucial task that has gained increasing research interest in recent years. Most existing methods focus on reasoning at past timestamps to complete the missing facts, and there are only a few works of reasoning on known TKGs to forecast future facts. Compared with the completion task, the forecasting task is more difficult that faces two main challenges: (1) how to effectively model the time information to handle future timestamps? (2) how to make inductive inference to handle previously unseen entities that emerge over time? To address these challenges, we propose the first reinforcement learning method for forecasting. Specifically, the agent travels on historical knowledge graph snapshots to search for the answer. Our method defines a relative time encoding function to capture the timespan information, and we design a novel time-shaped reward based on Dirichlet distribution to guide the model learning. Furthermore, we propose a novel representation method for unseen entities to improve the inductive inference ability of the model. We evaluate our method for this link prediction task at future timestamps. Extensive experiments on four benchmark datasets demonstrate substantial performance improvement meanwhile with higher explainability, less calculation, and fewer parameters when compared with existing state-of-the-art methods.

## introduction storing a wealth of human knowledge and facts, knowledge graphs (kgs) are widely used for many downstream artificial intelligence (ai) applications, such as recommendation systems @xcite , dialogue generation @xcite , and question answering @xcite . kgs store facts in the form of triples ( , , ), i.e. (subject entity, predicate/relation, object entity), such as (lebron_james, plays_for, cleveland_cavaliers). each triple corresponds to a labeled edge of a multi-relational directed graph. however, facts constantly change over time. to reflect the timeliness of facts, temporal knowledge graphs (tkgs) additionally associate each triple with a timestamp ( , , , ), e.g., @xcite . usually, we represent a tkg as a sequence of static kg snapshots. tkg reasoning is a process of inferring new facts from known facts, which can be divided into two types, interpolation and extrapolation. most existing methods @xcite @xcite focus on interpolated tkg reasoning to complete the missing facts at past timestamps. in contrast, extrapolated tkg reasoning focuses on forecasting future facts (events). in this work, we focus on extrapolated tkg reasoning by designing a model for the link prediction at future timestamps. e.g., "which team lebron james will play for in 2022?" can be seen as a query of link prediction at a future timestamp: @xcite . compared with the interpolation task, there are two challenges for extrapolation. (1) unseen timestamps: the timestamps of facts to be forecast do not exist in the training set. (2) unseen entities: new entities may emerge over time, and the facts to be predicted may contain previously unseen entities. hence, the interpolation methods can not treat the extrapolation task. the recent extrapolation method re-net @xcite to capture temporally adjacent facts information to predict future facts. cygnet @xcite focuses on the repeated pattern to count the frequency of similar facts in history. however, these methods only use the random vectors to represent the previously unseen entities and view the link prediction task as a multi-class classification task, causing it unable to handle the second challenge. moreover, they cannot explicitly indicate the impact of historical facts on predicted facts. inspired by path-based methods @xcite for static kgs, we propose a new temporal-path-based reinforcement learning (rl) model for extrapolated tkg reasoning. we call our agent the "time traveler" (titer), which travels on the historical kg snapshots to find answers for future queries. titer starts from the query subject node, sequentially transfers to a new node based on temporal facts related to the current node, and is expected to stop at the answer node. to handle the unseen-timestamp challenge, titer uses a relative time encoding function to capture the time information when making a decision. we further design a novel time-shaped reward based on dirichlet distribution to guide the model to capture the time information. to tackle the unseen entities, we introduce a temporal-path-based framework and propose a new representation mechanism for unseen entities, termed the inductive mean (im) representation, so as to improve the inductive reasoning ability of the model. our main contributions are as follows: ## methodology analogizing to the previous work on kgs @xcite , we frame the rl formulation as "walkbased query-answering" on a temporal graph: the agent starts from the source node (subject entity of the query) and sequentially selects outgoing edges to traverse to new nodes until reaching a target. in this section, we first define our task, and then describe the reinforcement learning framework and how we incorporate the time information into the on-policy reinforcement learning model. the optimization strategy and the inductive mean representation method for previously unseen entities are provided in the end. figure 2 is the overview of our model. ## conclusion in this work, we propose a temporal-path-based reinforcement learning model named timetraveler (titer) for temporal knowledge graph forecasting. titer travels on the tkg historical snapshots and searches for the temporal evidence chain to find the answer. titer uses a relative time encoding function and time-shaped reward to model the time information, and the im mechanism to update the unseen entities' representation in the process of testing. extensive experimental results reveal that our model outperforms state-of-the-art baselines with less calculation and fewer parameters. furthermore, the inference process of titer is explainable, and titer has good inductive reasoning ability. we can also maximize the leave-one-out likelihood. the digamma function ψ can also be inverted efficiently by using a newton-raphson method.