Recurrent Event Network: Autoregressive Structure Inference over Temporal Knowledge Graphs

Introduction

Knowledge graphs (KGs), which store real-world facts, are vital in various natural language processing applications Bordes et al. (2013); Schlichtkrull et al. (2018); Kazemi et al. (2019). 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, 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}\leq t\leq t_{T}$ García-Durán et al. (2018); Leblay and Chekol (2018); Dasgupta et al. (2018). 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., $t>t_{T}$). 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 Muthiah et al. (2015); Phillips et al. (2017); Korkmaz et al. (2015).

Recent attempts to solve the extrapolation TKG reasoning problem are Know-Evolve (Trivedi et al., 2017) and its extension DyRep (Trivedi et al., 2019), 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 Morstatter et al. (2019). 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 Boschee et al. (2015); Leetaru and Schrodt (2013). 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 state-of-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.

Approach Overview. The key idea of our approach is to learn temporal dependency from the sequence of graphs and local structural dependency from the neighborhood (Fig. 2). Formally, we represent TKGs as sequences, and then build an autoregressive generative model on the sequences. To this end, RE-Net defines the joint probability of concurrent events (or a graph), which is conditioned on all the previous events. Specifically, RE-Net consists of a Recurrent Neural Network (RNN) as a recurrent event encoding module and a neighborhood aggregation module to capture the information of graph structures. We first start with the definition of joint distribution of temporal events.

Modeling Joint Distribution of Temporal Events. We define the joint distribution of all the events $G=\{G_{1},...,G_{T}\}$ in an autoregressive manner. Basically, we decompose the joint distribution into a sequence of conditional distributions, $p(G_{t}|G_{t-m:t-1})$), where we assume the probability of the events at a time step, $G_{t}$, depends on the events at the previous $m$ steps, $G_{t-m:t-1}$. For each conditional distribution $p(G_{t}|G_{t-m:t-1})$, we further assume that the events in $G_{t}$ are mutually independent given the previous events $G_{t-m:t-1}$. In this way, the joint distribution can be rewritten as follows:

Next, we introduce how these probabilities are defined and parameterized in our method.

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 multi-step inference for distant future by sampling intermediate graphs in a sequential manner (Sec. 3.3).

Similarly, we define probabilities for relations and subjects as follows:

In the next section, we introduce how we design $g$ in RE-Net.

2 Neighborhood Aggregators

Multi-Relational Graph (RGCN) Aggregator. We introduce a multi-relational graph aggregator from (Schlichtkrull et al., 2018). This is a general aggregator that can incorporate information from multi-relational and multi-hop neighbors. Formally, the aggregator is defined as follows:

3 Parameter Learning and Inference

In this section, we discuss how RE-Net is trained and infers events over multiple time stamps.

where $G$ is set of events, and $\lambda_{1}$ and $\lambda_{2}$ are importance parameters that control the importance of each loss term. $\lambda_{1}$ and $\lambda_{2}$ can be chosen depending on the task. If a task aims to predict $o$ given $(s,r)$, then we can give small values to $\lambda_{1}$ and $\lambda_{2}$.

Multi-step Inference over Time. RE-Net seeks to predict the forthcoming events based on the previous observations. Suppose that the current time is $t$ and we aim to predict events at time $t+\Delta t$ where $\Delta t>0$. Then the problem of multi-step inference can be formalized as inferring the conditional probability $p(G_{t+\Delta t}|G_{:t})$. The problem is nontrivial as we need to integrate over all $G_{t+1:t+\Delta t-1}$. To achieve efficient inference, we draw a sample of $G_{t+1:t+\Delta t-1}$, and estimate the conditional probability as follows:

Experiments

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.

We compare the performance of our model against various traditional models for knowledge graphs, as well as some recent temporal reasoning models on five public datasets.

Evaluation Setting and Metrics. For each dataset except ICEWS14We used the splits as provided in (Trivedi et al., 2017)., we split it into three subsets, i.e., train(80%)/valid(10%)/test(10%), by time stamps. Thus, (time stamps of train) $<$ (time stamps of valid) $<$ (time stamps of test). We report a filtered version of Mean Reciprocal Ranks (MRR) and Hits$@3$/$10$. Similar to the definition of filtered setting in (Bordes et al., 2013), during evaluation, we remove all the valid triplets that appear in the train, valid, or test sets from the list of corrupted triplets.

Baselines. We compare our approach to baselines for static graphs and temporal graphs as follows:

(1) Static Methods. By ignoring the edge time stamps, we construct a static, cumulative graph for all the training events, and apply multi-relational graph representation learning methods including DistMult (Yang et al., 2015), R-GCN (Schlichtkrull et al., 2018), ConvE (Dettmers et al., 2018), and RotatE (Sun et al., 2019).

(2) Temporal Reasoning Methods. We also compare state-of-the-art temporal reasoning methods for knowledge graphs, including Know-Evolve*: We found a problematic formulation in Know-Evolve. Details of this issues are discussed in Section G of appendix. (Trivedi et al., 2017), TA-DistMult (García-Durán et al., 2018), and HyTE (Dasgupta et al., 2018). TA-DistMult and HyTE are for an interpolation task whereas we focus on an extrapolation task. To do this, we assign random values to temporal embeddings that are not observed during training. To see the effectiveness of our recurrent event encoder, we use encoders of previous work and our MLP decoder as baselines; we compare Know-Evolve, Dyrep (Trivedi et al., 2019), and GCRN (Seo et al., 2017) combined with our MLP decoder, called Know-Evolve+MLP, DyRep+MLP, and R-GCRN+MLP. The GCRN utilizes Graph Gonvolutional Network (Kipf and Welling, 2016). Instead, we use RGCN (Schlichtkrull et al., 2018) to deal with multi-relational graphs.

We also compare our method with dynamic methods on homogeneous graphs: dyngraph2vecAE (Goyal et al., 2019), tNodeEmbed (Singer et al., 2019), and EvolveRGCN (Pareja et al., 2020). These methods were proposed to predict interactions at future time on homogeneous graphs. Thus, we modified the methods to apply them on multi-relational graph.

(3) Variants of RE-Net. To evaluate the importance of different components of RE-Net, we varied our model in different ways: RE-Net w/o multi-step which does not update history during inference, RE-Net without the aggregator (RE-Net w/o agg.), RE-Net with a mean aggregator (RE-Net w. mean agg.), and RE-Net with an attentive aggregator (RE-Net w. attn agg.). RE-Net w/o agg. takes a zero vector instead of an aggregator. RE-Net w. GT denotes RE-Net with ground truth history.

Please refer to Section D of appendix for detailed experimental settings.

2 Performance Comparison on TKGs.

We compare our proposed method with other baselines. The test results are obtained by averaged metrics (5 runs) over the entire test sets on datasets.

Results on Event-based TKGs. Table 1 summarizes results on all datasets. Our proposed RE-Net outperforms all other baselines on ICEWS18 and GDELT. Static methods underperform compared to our method since they do not consider temporal factors. Also, RE-Net outperforms all other temporal methods including TA-DistMult, HyTE, and dynamic methods on homogeneous graphs. Know-Evovle+MLP significantly improves Know-Evolve, which shows effectiveness of our MLP decoder. However, there is still a large gap from our model, which also indicates effectiveness of our recurrent event encoder. R-GCRN+MLP has a similar structure to ours in that it has a recurrent encoder and an RGCN aggregator but it lacks multi-step inference, global information, and the sophisticated modeling for the recurrent encoder. Thus, it underperforms compared to our method. More importantly, none of the prior temporal methods are capable of multi-step inference, while RE-Net can sequentially infer multi-step events (Details in Section 4.3).

Results on Public KGs. Previous results have demonstrated the effectiveness of RE-Net on event-based KGs. In Table 1 we compare RE-Net with other baselines on the Public KGs WIKI and YAGO. Our proposed RE-Net outperforms all other baselines on these datasets. In these datasets, baselines show better results than in the event-based TKGs. This is due to the characteristics of the datasets; they have facts that are valid within a time span. However, our proposed method consistently outperforms the static and temporal methods, which implies that RE-Net effectively infers new events using a powerful event encoder and an aggregator, and provides accurate prediction results.

Performance of Prediction over Time. Next, we further study performance of RE-Net over time. Figs. 4 shows the performance comparisons over different time stamps on the ICEWS18, GDELT, WIKI, and YAGO datasets with filtered Hits@3 metrics. RE-Net consistently outperforms baseline methods for all different time stamps. Performance of each method fluctuate since testing entities are different at each time step. We notice that with increasing time steps, the difference between RE-Net and ConvE gets smaller as shown in Fig. 4. This is expected since further future events are harder to predict. To estimate the joint probability distribution of events in a distant future, RE-Net needs to generate a long graph sequence. The quality of generated graphs deteriorates when RE-Net generates a long graph sequence.

3 Ablation Study

In this section, we study the effect of variations in RE-Net on the ICEWS18 dataset. We present the results in Tables 1, 2, and Fig. 5.

Different Aggregators. In Table 2, we observe that RE-Net w/o agg. hurts model quality, suggesting that introducing aggregators makes the model capable of dealing with concurrent events and improves performance. Table 1 and Fig. 5a show the performance of RE-Net with different aggregators. Among them, RGCN aggregator outperforms other aggregators. This aggregator has the advantage of exploring multi-relational neighbors. Also, RE-Net with an attentive aggregator shows better performance than RE-Net with a mean aggregator, which implies that giving different attention weights to each neighbor helps predictions.

Multi-step Inference. In Table 2, we observe that RE-Net outperforms RE-Net w/o multi-step. The latter one does not update history during inference; keeps its last history in the training set. So it is not affected by time stamps. Without the multi-step inference, the performance of RE-Net is decreased as is shown. Also we expect that RE-Net w. GT shows significant improvement when RE-Net uses ground truth of triples at the previous time step which are not allowed in our setup.

Related Work

Temporal KG Reasoning. There have been some recent attempts on incorporating temporal information in modeling dynamic knowledge graphs, broadly categorized into two settings - extrapolation (Trivedi et al., 2017) and interpolation (García-Durán et al., 2018; Leblay and Chekol, 2018; Dasgupta et al., 2018; Goel et al., 2020; Lacroix et al., 2020). For the former setting, Know-Evolve (Trivedi et al., 2017) models the occurrence of a fact as a temporal point process. For the latter setting, several embedding-based methods have been proposed (García-Durán et al., 2018; Leblay and Chekol, 2018; Dasgupta et al., 2018; Goel et al., 2020; Lacroix et al., 2020) to model time information. They embed the associate into a low dimensional space such as relation embeddings with RNN on the text of time (García-Durán et al., 2018), time embeddings (Leblay and Chekol, 2018), temporal hyperplanes (Leblay and Chekol, 2018), diachronic entity embedding (Goel et al., 2020), and tensor decomposition (Lacroix et al., 2020). However, these models cannot predict future events, as representations of unseen time stamps are unavailable.

Temporal Modeling on Homogeneous Graphs. There are attempts on predicting future links on homogeneous graphs (Pareja et al., 2020; Goyal et al., 2018, 2019; Zhou et al., 2018; Singer et al., 2019). Some of the methods try to incorporate and learn graphical structures to predict future links (Pareja et al., 2020; Zhou et al., 2018; Singer et al., 2019), while other methods predict by reconstructing an adjacency matrix by using an autoencoder (Goyal et al., 2018, 2019). These methods seek to predict on single-relational graphs, and are designed to predict future edges in one future step (i.e., for $t+1$). However, our work focuses on multi-relational knowledge graphs and aims for multi-step prediction.

Deep Autoregressive Models. Deep autoregressive models define joint probability distributions as a product of conditionals. DeepGMG (Li et al., 2018) and GraphRNN (You et al., 2018) are deep generative models of graphs and focus on generating static homogeneous graphs where there is only a single type of edge. In contrast to these studies, our work focuses on generating heterogeneous graphs, in which multiple types of edges exist, and thus our problem is more challenging. To the best of our knowledge, this is the first paper to formulate the structure inference (prediction) problem for temporal, multi-relational (knowledge) graphs in an autoregressive fashion.

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.

Acknowledgement

This research is based upon work supported in part by the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA), via Contract No. 2019-19051600007, the DARPA MCS program under Contract No. N660011924033 with the United States Office Of Naval Research, the Defense Advanced Research Projects Agency with award W911NF-19-20271, and NSF SMA 18-29268. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of ODNI, IARPA, or the U.S. Government. We would like to thank all the collaborators in USC INK research lab for their constructive feedback on the work.

References

Appendix A Recurrent Neural Network

We define a recurrent event encoder based on RNN as follows:

We use Gated Recurrent Units (Cho et al., 2014) as RNN:

Appendix B Details of RGCN Aggregator

The RGCN aggregator is defined as follows:

Appendix C Computational Complexity Analysis.

Appendix D Detailed Experimental Settings

ICEWS18 is collected from 1/1/2018 to 10/31/2018, ICEWS14 is from 1/1/2014 to 12/31/2014, and GDELT is from 1/1/2018 to 1/31/2018. The ICEWS14 is from (Trivedi et al., 2017). We didn’t use their version of the GDELT dataset since they didn’t release the dataset.

The difference between the first group and the second group is that facts happen multiple times (even periodically) on the first group (event-based knowledge graphs) while facts last long time but are not likely to occur multiple times in the second group.

Experimental Settings for Baseline Methods. In this section, we provide detailed settings for baselines. We use implementations of DistMulthttps://github.com/jimmywangheng/knowledge_representation_pytorch. We implemented TA-DistMult based on the implementation of Distmult. For TA-DistMult, We use temporal tokens with the vocabulary of year, month and day on the ICEWS dataset and the vocabulary of year, month, day, hour and minute on the GDELT dataset. We use use a binary cross-entropy loss for DistMult and TA-DistMult. We validate the embedding size among 100 and 200. We set the batch size to 1024, margin to 1.0, negative sampling ratio to 1, and use the Adam optimizer.

We use the implementation of HyTEhttps://github.com/malllabiisc/HyTE. We use every timestamp as a hyperplane. The embedding size is set to 128, the negative sampling ratio to 5, and margin to 1.0. We use time agnostic negative sampling (TANS) for entity prediction, and the Adam optimizer.

We use the codes for ConvEhttps://github.com/TimDettmers/ConvE and use implementation by Deep Graph Libraryhttps://github.com/dmlc/dgl/tree/master/examples/pytorch/rgcn. Embedding sizes are 200 for both methods. We use 1 to all negative sampling for ConvE and use 10 negative sampling ratio for RGCN, and use the Adam optimizer for both methods. We use the codes for Know-Evolvehttps://github.com/rstriv/Know-Evolve. For Know-Evolve, we fix the issue in their codes. Issues are described in Section G. We follow their default settings.

We use the code for RotatEhttps://github.com/DeepGraphLearning/KnowledgeGraphEmbedding. The hidden layer/embedding size is set to 100, and batch size 256; other values follow the best values for the larger FB15K dataset configurations supplied by the author. The author reports filtered metrics only, so we added the implementation of the raw setting.

Experimental Settings for Dynamic Methods. We compare our method with dynamic methods on homogeneous graphs: dyngraph2vecAE (Goyal et al., 2019), tNodeEmbed (Singer et al., 2019), and EvolveGCN-O (Pareja et al., 2020). These methods were proposed to predict interactions at a future time on homogeneous graphs, while our proposed method is for predicting interactions on multi-relational graphs (or knowledge graphs). Furthermore, those methods predict links at one future time stamp, whereas our method seeks to predict interactions at multiple future time stamps. We modified some methods to apply them on multi-relational graphs as follows. We adopt R-GCN (Schlichtkrull et al., 2018) for EvolveGCN-O and call it EvolveRGCN. We convert knowledge graphs into homogeneous graphs for dyngraph2vecAE. The idea of this method is to reconstruct an adjacency matrix using an auto-encoder and regard it as a future adjacency matrix. If we keep relations, relation-specific adjacency matrices will be extremely sparse; the method learns to reconstruct near-zero adjacency matrices. tNodeEmbed is a temporal method on homogeneous graphs. To use this on multi-relational graphs, we first train entity embeddings with DistMult and set these as initial embeddings for entities in tNodeEmbed. Also we give entity embeddings as input to LSTM of tNodeEmbed. We concatenate output of LSTM and relation embeddings to predict objects. We did not modified other methods since it is not trivial to extend the methods.

Appendix E Additional Experiments

Table 4 shows the performance comparison on ICEWS18, GDELT, ICEWS14 with raw settings. Our proposed RE-Net outperforms all other baselines.

E.2 Sensitivity Analysis

In this section, we study the parameter sensitivity of RE-Net including the length of history for the event encoder, cutoff position k for events to generate a graph, the number of layers of the RGCN aggregator, and effect of the global representation from a global graph structure. We report the performance change of RE-Net on the ICEWS18 dataset by varying the hyper-parameters (Figs. 7 and 7c).

Length of Past History in Recurrent Event Encoder. The recurrent event encoder takes the sequence of past interactions up to $m$ graph sequences or previous histories. Fig. 7a shows the performance with various lengths of past histories. When RE-Net uses longer histories, MRR is getting higher. However, the MRR is not likely to go higher when the length of history is 5 and over.

Cut-off Position $k$ at Inference. To generate a graph at each time, we cut off top-$k$ triples on ranking results. In Fig. 7b, when $k$ is 0, RE-Net does not generate graphs for estimating $p(G_{t+\Delta t}|G_{:t})$, i.e., RE-Net performs single-step predictions, and it shows the lowest result. When $k$ is larger, the performance is getting higher and it is saturated after 500. We notice that the conditional distribution $p(G_{t+\Delta t}|G_{:t})$ can be approximated by $p(G_{t+\Delta t}|\allowbreak\hat{G}_{t+1:t+\Delta t-1},G_{:t})$ by using a larger cutoff position.

Layers of RGCN Aggregator. The number of layers in the aggregator means the depth to which the node reaches. Fig. 7c shows the performance according to different numbers of layers of RGCN. 2-layered RGCN improves the performance considerably compared to 1-layered RGCN since 2-layered RGCN aggregates more information. However, RE-Net with 3-layered RGCN underperforms RE-Net with 2-layered RGCN. We conjecture that the bigger parameter space leads to overfitting.

Global Information. We further observe that representations from global graph structures help the predictions. Fig. 7d shows effectiveness of a representation of global graph structures. The improvement is marginal, but we consider that global representations at different time steps give distinct information beyond local graph structures.

Appendix F Case Study

In this section, we study RE-Net’s predictions. Its predictions depend on interaction histories. We categorize histories into three cases: (1) consistent interactions with an object, (2) a specific temporal pattern, and (3) irrelevant history (Fig. 8). RE-Net can learn (1) and (2) cases, so it achieves high performances. For the first case, RE-Net can predict the answer because it consistently interacts with an object. However, static methods are prone to predicting different entities which are observed under relation ”Accuse” in training set. The second case shows specific temporal patterns on relations: ( Arrest, $o$ ) $\rightarrow$ ( Use force, $o$ ). Without knowing this pattern, one method might predict “Businessman” instead of “Men”. RE-Net is able to learn these temporal patterns so it can predict the second case. Lastly, the third case shows irrelevant history to the answer and the history is not helpful to predictions. RE-Net fails to predict the third case.

Appendix G Implementation Issues of Know-Evolve

We found a problematic formulation in the Know-Evolve model and codes. The intensity function (equation 3 in (Trivedi et al., 2017)) is defined as $\lambda_{r}^{s,r}(t|\bar{t})=f(g_{r}^{s,r}(\bar{t}))(t-\bar{t})$, where $g(\cdot)$ is a score function, $t$ is current time, and $\bar{t}$ is the most recent time point when either subject or object entity was involved in an event. This intensity function is used in inference to rank entity candidates. However, they don’t consider concurrent event at the same time stamps, and thus $\bar{t}$ will become $t$ after one event. For example, we have events $e_{1}=(s,r,o_{1},t_{1}),e_{2}=(s,r,o_{2},t_{1})$. After $e_{1}$, $\bar{t}$ will become $t$ (subject $s$’s most recent time point), and thus the value of intensity function for $e_{2}$ will be 0. This is problematic in inference since if $t=\bar{t}$, then the intensity function will always be 0 regardless of entity candidates. In inference, all object candidates are ranked by the intensity function. But all intensity scores for all candidates will be 0 since $t=\bar{t}$, which means all candidates have the same 0 score. In their code, they give the highest ranks (first rank) for all entities including the ground truth object in this case. Thus, we fixed their code for a fair comparison; we give an average rank to entities who have the same scores.