Recurrent Event Network: Autoregressive Structure Inferenceover Temporal Knowledge Graphs (2020)

Abstract: Knowledge graph reasoning is a critical task in natural language processing. The task becomes more challenging on temporal knowledge graphs, where each fact is associated with a timestamp. Most existing methods focus on reasoning at past timestamps and they are not able to predict facts happening in the future. This paper proposes Recurrent Event Network (RE-Net), a novel autoregressive architecture for predicting future interactions. The occurrence of a fact (event) is modeled as a probability distribution conditioned on temporal sequences of past knowledge graphs. Specifically, our RE-Net employs a recurrent event encoder to encode past facts, and uses a neighborhood aggregator to model the connection of facts at the same timestamp. Future facts can then be inferred in a sequential manner based on the two modules. We evaluate our proposed method via link prediction at future times on five public datasets. Through extensive experiments, we demonstrate the strength of RE-Net, especially on multi-step inference over future timestamps, and achieve state-of-the-art performance on all five datasets.

## introduction knowledge graphs (kgs), which store real-world facts, are vital in various natural language processing applications @xcite @xcite . due to the high cost of annotating facts, most knowledge graphs are far from complete, and thus predicting missing facts (a.k.a., knowledge graph reasoning) becomes an important task. most existing efforts study reasoning on standard knowledge graphs, where each fact is represented as a triple of subject entity, object entity and the relation between them. however, in practice, each fact may not be true forever, each edge or interaction between entities is associated with temporal information and a set of interactions build a multi-relational graph at each time. our task is to predict interactions and build graphs at future times. and hence it is useful to associate each fact with a timestamp as a constraint, yielding a temporal knowledge graph (tkg). fig. 1 shows example subgraphs of a temporal knowledge graph. despite the ubiquitousness of tkgs, methods for reasoning over such kind of data are relatively unexplored. given a temporal knowledge graph with timestamps varying from t 0 to t t , tkg reasoning primarily has two settings -interpolation and extrapolation. in the interpolation setting, new facts are predicted for time t such that t 0 ≤ @xmath0. in contrast, extrapolation reasoning, as a less studied setting, focuses on predicting new facts (e.g., unseen events) over timestamps t that are greater than t t (i.e., @xmath1. the extrapolation setting is of particular interests in tkg reasoning as it helps populate the knowledge graph over future timestamps and facilitates forecasting emerging events @xcite @xcite . recent attempts to solve the extrapolation tkg reasoning problem are know-evolve @xcite and its extension dyrep @xcite , which predict future events assuming ground truths of the preceding events are given at inference time. as a result, these methods are unable to predict events sequentially over future timestamps without ground truths of the preceding events-i.e., a practical requirement when deploying such reasoning systems for event forecasting @xcite . moreover, these approaches do not model concurrent events occurring within the same time window (e.g., a day, or 12 hours), despite their prevalence in real-world event data @xcite . thus, it is desirable to have a principled method that can extrapolate graph structures over future timestamps by modeling the concurrent events within a time window as a local graph. to this end, we propose an autoregressive architecture, called recurrent event network (re-net), for modeling temporal knowledge graphs. key ideas of re-net are based on: (1) predicting future events over multiple time stamps can be formulated as a sequential and multi-step inference problem; (2) temporally adjacent events may carry related semantics and informative patterns, which can further help predict future events (i.e., temporal information); and (3) multiple events may co-occur within the same time window and exhibit structural dependencies between entities (i.e., local graph structural information). given these observations, re-net defines the joint probability distribution of all events in a tkg in an autoregressive fashion. the probability distribution of the concurrent events at the current time step is conditioned on all the preceding events (see fig. 2 for an illustration). specifically, a recurrent event encoder summarizes information of the past event sequences, and a neighborhood aggregator aggregates the information of concurrent events within the same time window. with the summarized information, our decoder defines the joint probability of a current event. inference for predicting future events can be achieved by sampling graphs over time in a sequential manner. we evaluate our proposed method on five public tkg datasets via a temporal (extrapolation) link prediction task, by testing the performance of multi-step inference over time. experimental results demonstrate that re-net outperforms stateof-the-art models of both static and temporal knowledge graph reasoning, showing its better capability to model temporal, multi-relational graph data. we further show that re-net can perform effective multi-step inference to predict unseen entity relationships in a distant future. ## problem formulation we first describe notations for building our model and problem definition, and then we define the joint distribution of temporal events. notations and problem definition. we consider a temporal knowledge graph as a multi-relational, directed graph with time-stamped edges between nodes (entities). an event is defined as a timestamped edge, i.e., (subject entity, relation, object entity, time) and is denoted by a quadruple (s, r, o, t) or (s t , r t , o t ). we denote a set of events at time t as g t . in our setup, the timestamps are discrete integers and used for the relative order of graphs or events. a tkg is built upon a sequence of event quadruples ordered ascending based on their timestamps, i.e., {g t } @xmath2, r i , o i , t i )} i (t @xmath3, ∀@xmath4, where each time-stamped edge has a direction pointing from the subject entity to the object entity. 2 the goal of learning generative models of events is to learn a distribution p(g) over tkgs, based on a set of observed event sets {g 1 , ..., g t }. ## recurrent event network in this section, we introduce our proposed method, recurrent event network (re-net). re-net consists of a recurrent neural network (rnn) as a recurrent event encoder (sec. 3.1) for temporal dependency and a neighborhood aggregator (sec. 3.2) for graph structural dependency. we also discuss parameter learning of re-net and define multistep inference for distant future by sampling intermediate graphs in a sequential manner (sec. 3.3). ## experiments evaluating the quality of generated graphs is nontrivial, especially for knowledge graphs @xcite . in our experiments, we evaluate the proposed method on a extrapolation link prediction task on tkgs. the task of predicting future links aims to predict unseen relationships with object entities given (s, r, ?, t) (or subject entities given (?, r, o, t)) at future time t, based on the past observed events in the tkg. essentially, the task is a ranking problem over all the events (s, r, ?, t) (or (?, r, o, t)). re-net can approach this problem by computing the probability of each event in a distant future with the inference algorithm in algorithm 1, and further rank all the events according to their probabilities. note that we are only given a training set as ground truth at inference and we do not use any ground truth in the test set for the next time step predictions when performing multi-step inference. this is the main difference from previous work; they use previous ground truth in the test set. we evaluate our proposed method on three benchmark tasks: (1) predicting future events on three event-based datasets; (2) predicting future facts on two knowledge graphs which include facts with time spans, and (3) studying ablation of our proposed method. section 4.1 summarizes the datasets. in all these experiments, we perform predictions on time stamps that are not observed during training. ## conclusion to tackle the extrapolation problem, we proposed recurrent event network (re-net) to model temporal, multi-relational, and concurrent interactions between entities. re-net defines the joint probability of all events, and thus is capable of inferring graphs in a sequential manner. the experiment revealed that re-net outperforms all the static and temporal methods and our extensive analysis shows its strength. interesting future work includes developing a fast and efficient version of re-net, and modeling lasting events and performing inference on the long-lasting graph structures.