Search from History and Reason for Future: Two-stage Reasoning on Temporal Knowledge Graphs (2021)

Abstract: Temporal Knowledge Graphs (TKGs) have been developed and used in many different areas. Reasoning on TKGs that predicts potential facts (events) in the future brings great challenges to existing models. When facing a prediction task, human beings usually search useful historical information (i.e., clues) in their memories and then reason for future meticulously. Inspired by this mechanism, we propose CluSTeR to predict future facts in a two-stage manner, Clue Searching and Temporal Reasoning, accordingly. Specifically, at the clue searching stage, CluSTeR learns a beam search policy via reinforcement learning (RL) to induce multiple clues from historical facts. At the temporal reasoning stage, it adopts a graph convolution network based sequence method to deduce answers from clues. Experiments on four datasets demonstrate the substantial advantages of CluSTeR compared with the state-of-the-art methods. Moreover, the clues found by CluSTeR further provide interpretability for the results.

## introduction temporal knowledge graphs (tkgs) @xcite @xcite have emerged as a very active research area over the last few years. each fact in tkgs has a timestamp indicating its time of occurrence. for example, the fact, (covid-19, new medical case occur, shop, 2020-10-2), indicates that a new medical case of covid-19 occurred in a shop on 2020-10-2. in this paper, reasoning on tkgs aims to predict future facts (events) for timestamp @xmath0, where t t is assumed to be the current timestamp @xcite . an example of the task is shown in figure 1 , which attempts to answer the query (covid-19, new medical case occur, ?, 2020-12-23) with the given historical facts. obviously, such a task may benefit many practical applications, such as, emerging events response @xcite @xcite , disaster relief @xcite , and financial analysis @xcite . how do human beings predict future events? according to the dual process theory @xcite @xcite , the first thing is to search the massive-capacity memories and find some related historical information (i.e., clues) intuitively. as shown in the left part of figure 1 , there are mainly three categories of clues vital to the query: 1) the 1-hop paths with the same relation to the query (thus called repetitive 1-hop paths), such as (covid-19, new medical case occur, shop); 2) the 1-hop paths with relations different from the query (called non-repetitive 1-hop paths), such as (covid-19, new suspected case occur, bank); and 3) the 2-hop paths, such as (covid-19, diagnose -1 , the man, go to, police station). human beings recall these clues from their memories and have some intuitive candidate answers for the query. secondly, human beings get the accurate answer by diving deeper into the clues' temporal information and performing a meticulous reasoning process. as shown in the right part of figure 1 , the man went to the police station more than two months earlier than the time when he was diagnosed with covid-19, indicating that police station is probably not the answer. finally, human beings derive the answer, shop. existing models mainly focus on the above second process but underestimate the first process. some recent studies @xcite learn the evolving embeddings of entities with all historical facts considered. however, only a few historical facts are useful for a specific prediction. thus, some other studies @xcite @xcite ) mainly focus on encoding the 1-hop repetitive paths (repetitive facts) in the history. however, besides the 1-hop repetitive paths, there are massive other related information in the datasets. taking the widely used dataset icews18 @xcite as an example, 41.2% of the training queries can get the answers through the 1-hop repetitive paths in the history. but, almost 64.6% of them can get the answers through 1hop repetitive and non-repetitive paths, and 86.2% through the 1-hop and 2-hop paths. thus, we propose a new model called cluster, consisting of two stages, clue searching (stage 1) and temporal reasoning (stage 2). at stage 1, cluster formalizes clue-searching as a markov decision process (mdp) @xcite and learns a beam search policy to solve it. at stage 2, cluster reorganizes the clues found in stage 1 into a series of graphs and then a graph convolution network (gcn) and a gated recurrent unit (gru) are employed to deduce accurate answers from the graphs. in general, this paper makes the following contributions: temporal kg reasoning. reasoning on temporal kg can broadly be categorized into two settings, interpolation @xcite @xcite @xcite @xcite @xcite and extrapolation @xcite @xcite @xcite @xcite , as mentioned in @xcite . under the former setting, models attempt to infer missing facts at historical timestamps. while the latter setting, which this paper focuses on, attempts to predict facts in the future. orthogonal to our work, @xcite estimate the conditional probability of observing a future fact via a temporal point process taking all historical facts into consideration. although @xcite extends temporal point process to model concurrent facts, they are more capable of modeling tkgs with continuous time, where no events may occur at the same timestamp. glean @xcite incorporates a word graph constructed by the summary texts of events into tkg reasoning. the most related works are re-net @xcite and cygnet @xcite . re-net uses a subgraph aggregator and gru to model the subgraph sequence consist-es, rq, ?, ts r-gcn gru+mlp es mlp randomized beam search lstm clue paths hi rq candidates clue facts es es es j ts-2 ts-1 r-gcn r-gcn stage 1: clue searching stage 2: temporal reasoning ts-1 ts-2 ts-3 ts-4 ts-5 es es es es es r es g rq j es rq ts-2 g es rq ts-1 g timeconstrained actions next state reward environment agent ei hi+1 es path in es figure 2: an illustrative diagram of the proposed cluster model. ing of 1-hop facts. cygnet uses a sequential copy network to model repetitive facts. both of them use heuristic strategies in the clue searching stage, which may lose lots of other informative historical facts or engage some noise. although the above two models attempt to consider other information by pre-trained global embeddings or an extra generation model, they still mainly focus on modeling repetitive facts. besides, all the models almost can not provide interpretability for the results. ## the proposed cluster model we start with the notations, then introduce the model as well as its training procedure in detail. ## experiment we design experiments to answer the following questions: q1. how does cluster perform on the tkg reasoning task? q2. how do the two stages contribute to the final results respectively? q3. which clues are found and used for reasoning? q4. can cluster provide some interpretability for the results? @xcite and gdelt @xcite . the first three datasets are from the integrated crisis early warning system (icews) @xcite and the last one is from global database of events, language, and tone (gdelt) @xcite . we evaluate cluster on all these datasets. icews14 and icews05-15 are divided into training, validation, and test sets following the preprocessing on icews18 in re-net @xcite . the details of the datasets are presented in in the experiments, the widely used mean reciprocal rank (mrr) and hits@{1,10} are employed as the metrics. without loss of generality, only the experimental results under the raw setting are reported. the filtered setting is not suitable for the reasoning task under the exploration setting, as mentioned in @xcite @xcite . the reason is explained in terms of an example as follows: given a test quadruple (barack obama, visit,?, 2015-1-25) with the correct answer india. assume there is a quadruple (barack obama, visit, germany, 2013-1-18) in the training set. the filtered setting used in the previous studies ignores time information and considers (barack obama, visit, germany, 2015-1-25) to be valid because (barack obama, visit, germany, 2013-1-18) appears in the training set. it thus removes the quadruple from the corrupted ones. however, the fact (barack obama, visit, germany) is temporally valid on 2013-1-18, instead of 2015-1-25. therefore, to test the quadruple (barack obama, visit,?, 2015-1-25), (barack obama, visit, germany, 2015-1-18) should not be removed. in this way, the filtered setting wrongly removes quite a lot of quadruples and thus leads to over-optimistic experimental performance. baselines. the cluster model is compared with two categories of models, i.e., models for static kg reasoning and models for tkg reasoning under the exploration setting. the typical static models distmult @xcite , com-plex @xcite , rgcn @xcite , conve @xcite and ro-tae @xcite are selected with the temporal information of facts ignored. we also choose min-erva @xcite , the rl-based multi-hop reasoning model, as the baseline. for tkg models, the representative know-evolve @xcite , dyrep @xcite , cygnet @xcite and re-net @xcite are selected. besides, following re-net @xcite , we extend two models for temporal homogeneous graphs, gcrn @xcite and evolvegcn-o @xcite ), to rgcrn and evolvergcn by replacing gcn with rgcn. we use conve @xcite , a more stronger decoder to replace the mlp @xcite for the two models. for know-evolve and dyrep, re-net extends them to tkg reasoning task but does not release their codes. thus, we only report the results from their papers. for other baselines, we reproduce all the results with the optimal parameters tuning on the validation set. ## conclusions in this paper, we proposed a two-stage model from the view of human cognition, named cluster, for tkg reasoning. cluster consists of a rl-based clue searching stage (stage 1) and a gcn-based temporal reasoning stage (stage 2). in stage 1, cluster finds reliable clue paths from history and generates intuitive candidate entities via rl. with the found clue paths as input, stage 2 reorganizes the clue facts derived from the clue paths into a sequence of graphs and performs deduction on them to get the answers. by the two stages, the model demonstrates substantial advantages on tkg reasoning. finally, it should be mentioned that, although the four tkgs adopted in the experiments were created based on the events in the real world, the motivation of this paper is to propose this tkg reasoning model only for scientific research.