Title: RECURRENT EVENT NETWORK: GLOBAL STRUCTURE INFERENCE OVER TEMPORAL KNOWLEDGE GRAPH Anonymous authors Paper under double-blind review

Abstract: Modeling dynamically-evolving, multi-relational graph data has received a surge of interests with the rapid growth of heterogeneous event data. However, predicting future events on such data requires global structure inference over time and the ability to integrate temporal and structural information, which are not yet well understood. We present Recurrent Event Network (RE-NET), a novel autoregressive architecture for modeling temporal sequences of multi-relational graphs (e.g., temporal knowledge graph), which can perform sequential, global structure inference over future time stamps to predict new events. RE-NET employs a recurrent event encoder to model the temporally conditioned joint probability distribution for the event sequences, and equips the event encoder with a neighborhood aggregator for modeling the concurrent events within a time window associated with each entity. We apply teacher forcing for model training over historical data, and infer graph sequences over future time stamps by sampling from the learned joint distribution in a sequential manner. We evaluate the proposed method via temporal link prediction on five public datasets. Extensive experiments 1 demonstrate the strength of RE-NET, especially on multi-step inference over future time stamps.

1. INTRODUCTION:

Representation learning on dynamically-evolving, graph-structured data has emerged as an important problem in a wide range of applications, including social network analysis (Zhou et al., 2018a; Trivedi et al., 2019) , knowledge graph reasoning (Trivedi et al., 2017; Nguyen et al., 2018; Kazemi et al., 2019) , event forecasting (Du et al., 2016) , and recommender systems (Kumar et al., 2019; You et al., 2019) . Previous methods over dynamic graphs mainly focus on learning time-sensitive structure representations for node classification and link prediction in single-relational graphs. However, the rapid growth of heterogeneous event data (Mahdisoltani et al., 2014; Boschee et al., 2015) has created new challenges on modeling temporal, complex interactions between entities (i.e., viewed as a temporal knowledge graph or a TKG), and calls for approaches that can predict new events in different future time stamps based on the history-i.e., structure inference of a TKG over time.

Recent attempts on learning over temporal knowledge graphs have focused on either predicting missing events (facts) for the observed time stamps (García-Durán et al., 2018; Dasgupta et al., 2018; Leblay & Chekol, 2018) , or estimating the conditional probability of observing a future event using temporal point process (Trivedi et al., 2017; 2019) . However, the former group of methods adopts an interpolation problem formulation over TKGs and thus cannot predict future events, as representations of unseen time stamps are unavailable. The latter group of methods, including Know-Evolve and its extension, DyRep, computes the probability of future events using ground-truths of the proceeding events during inference time, and cannot model concurrent events occurring within the same time window-which often happens when event time stamps are discrete. It is thus desirable to have a principled method that can infer graph structure sequentially over time and can incorporate local structural information (e.g., concurrent events) during temporal modeling.

To this end, we propose a sequential structure inference architecture, called Recurrent Event Network (RE-NET), for modeling heterogeneous event data in the form of temporal knowledge graphs. Key ideas of RE-NET are based on the following observations: (1) predicting future events can be viewed as a sequential (multi-step) inference of multi-relational interactions between entities over time; (2) Grant diplomatic recognition at 1/1/18 M a k e s ta te m e n t a t 3 /8 /1 8 C o n su lt a t 4 /1 0 /1 8 M a k e a re q u e s t a t 4 /2 2 /1 8 C r it ic iz e a t 5 /5 /1 8 V is it a t 5 /6 /1 8 Mak e stat eme nt at 6/13 /18 (a) An example of temporal KG (modeled by a neighborhood aggregator) at different time t. Also the global information from G t is used to capture the global graph structures. Recurrent event encoder updates its state with graph sequences in an autoregressive manner. The decoder defines the probability P(s t , r t , o t |G :t-1 ) at current time step conditioned on the preceding events. temporally adjacent events may carry related semantics and informative patterns, which can further help inform future events (i.e., temporal information); and (3) multiple events may co-occur within the same time window and exhibit structural dependencies as they share entities (i.e., local structural information). To incorporate these ideas, RE-NET defines the joint probability distribution of all the events in a TKG in an autoregressive fashion, where it models the probability distribution of the concurrent events at the current time step conditioned on all the preceding events (see Fig. 1b for an illustration). Specifically, a recurrent event encoder, parametrized by RNNs, is used to summarize information of the past event sequences, and a neighborhood aggregator is employed to aggregate the information of concurrent events for the related entity within each time stamp. With the summarized information of the past event sequences, our decoder defines the joint probability of a current event. Such an autoregressive model can be effectively trained by using teacher forcing. Global structure inference for predicting future events can be achieved by performing sampling in a sequential manner.

We evaluate our proposed method on temporal link prediction task, by testing the performance of multi-step inference over time on five public temporal knowledge graph datasets. Experimental results demonstrate that RE-NET outperforms state-of-the-art models of both static and temporal graph reasoning, showing its better capacity to model temporal, multi-relational graph data with concurrent events. We further show that RE-NET can perform effective multi-step inference to predict unseen entity relationships in a distant future.

2. RELATED WORK:

Our work is related to previous studies on temporal knowledge graph reasoning, temporal modeling on homogeneous graphs, recurrent graph neural networks, and deep autoregressive models.

Temporal KG Reasoning. There are some recent attempts on incorporating temporal information in modeling dynamic knowledge graphs. (Trivedi et al., 2017) presented Know-Evolve which models the occurrence of a fact as a temporal point process. However, this method is built on a problematic formulation when dealing with concurrent events, as shown in Section F. Several embedding-based methods have been proposed (García-Durán et al., 2018; Leblay & Chekol, 2018; Dasgupta et al., 2018) 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 & Chekol, 2018) , and temporal hyperplanes (Leblay & Chekol, 2018) . However, these models do not capture temporal dependency and cannot generalize to unobserved time stamps.

Temporal Modeling on Homogeneous:

Graphs. There are attempts on predicting future links on homogeneous graphs (Pareja et al., 2019; Goyal et al., 2018; 2019; Zhou et al., 2018b; Singer et al., 2019) . Some of the methods try to incorporate and learn graphical structures to predict future links (Pareja et al., 2019; Zhou et al., 2018b; 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 (i.e., for t + 1, . . . , t + k).

Recurrent Graph Neural Models.:

There have been some studies on recurrent graph neural models for sequential or temporal graph-structured data (Sanchez-Gonzalez et al., 2018; Battaglia et al., 2018; Palm et al., 2018; Seo et al., 2017; Pareja et al., 2019) . These methods adopt a messagepassing framework for aggregating nodes' neighborhood information (e.g., via graph convolutional operations). GN (Sanchez-Gonzalez et al., 2018; Battaglia et al., 2018) and RRN (Palm et al., 2018) update node representations by a message-passing scheme between time stamps. Some prior methods adopt an RNN to memorize and update the states of node embeddings that are dynamically evolving (Seo et al., 2017) , or memorize and update the model parameters for different time stamps (Pareja et al., 2019) . In contrast, our proposed method, RE-NET, aims to leverage autoregressive modeling to parameterize the joint probability distributions of events with RNNs.

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 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 my knowledge, this is the first paper to formulate the structure inference (prediction) problem for temporal, multi-relational (knowledge) graphs in an autoregressive fashion.

3. PROPOSED METHOD: RE-NET:

We consider a temporal knowledge graph (TKG) as a multi-relational, directed graph with timestamped edges (relationships) between nodes (entities). An event is defined as a time-stamped 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 . A TKG is built upon a sequence of event quadruples ordered ascending based on their time stamps, i.e., {G t } t = {(s i , r i , o i , t i )} i (with t i < t j , ∀i < j), 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 temporal knowledge graphs, based on a set of observed event sets {G 1 , ..., G T }. To model lasting events which span over a time range, i.e., (s, r, o, [t 1 , t 2 ]), we simply partition such event into a sequence of time-stamp events {G t1 , ..., G t2 }. We leave more sophisticated modeling of lasting events as future work.

3.1. RECURRENT EVENT NETWORK:

Sequential Structure Inference in TKG. The key idea in RE-NET is to define the joint distribution of all the events G = {G 1 , ..., G T } in an autoregressive manner, i.e., P(G) = T t=1 P(G t |G t-m:t-1 ). Basically, we decompose the joint distribution into a sequence of conditional distributions (e.g., P(G t |G t-m:t-1 )), where we assume the probability of the events at a time step, e.g. G t , only depends on the events at the previous m steps, e.g., 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.

P(G) = t (st,rt,ot)∈Gt P(s t , r t , o t |G t-m:t-1 ) = t (st,rt,ot)∈Gt P(o t |s t , r t , G t-m:t-1 ) • P(r t |s t , G t-m:t-1 ) • P(s t |G t-m:t-1 ).

(1) Intuitively, the generation process of each triplet (s t , r t , o t ) is defined as below. Given all the past events G t-m:t-1 , we fist generate a subject entity s t through the distribution P(s t |G t-m:t-1 ). Then we further generate a relation r t with P(r t |s t , G t-m:t-1 ), and finally the object entity o t is generated by defining P(o t |s t , r t , G t-m:t-1 ).

In this work, we assume that P(o t |s t , r t , G t-m:t-1 ) and P(r t |s t , G t-m:t-1 ) depend only on events that are related to s, and focus on modeling the following joint probability: where

EQUATION

G t becomes N (s)

t which is a set of neighboring entities interacted with subject entity s under all relations at time stamp t. For the third probability, the event sets should be considered since subject is not given. Next, we introduce how we parameterize these distributions.

Recurrent Event Encoder. RE-NET parameterizes P(o t |s, r, G t-m:t-1 ) in the following way:

EQUATION

where e s , e r ∈ R d are learnable embedding vectors specified for subject entity s and relation r. h t-1 (s, r) ∈ R d is a history vector which encodes the information from the neighbor sets interacted with s in the past, as well as the global information from graph structures of G t-1:t-m . Basically, [e s : e r : h t-1 (s, r)] is an encoding to summarize all the past information. Based on that, we further compute the probability of different object entities o t by passing the encoding into a linear softmax classifier parameterized by {w ot }.

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

EQUATION

EQUATION

where h t-1 (s) captures all the local information about s in the past, and H t-1 ∈ R d is a vector representation to encode the global graph structures G t-1:t-m .

For each time step t, since the hidden vectors h t-1 (s), h t-1 (s, r) and H t-1 preserve the information from the past events, and we update them in the following recurrent way:

EQUATION

EQUATION

EQUATION

where g is an aggregation function, and N (s)

t stands for all the events related to s at the current time step t. Intuitively, we obtain the current information related to s by aggregating all the related events at time t, i.e., g(N (s) t ). Then we update the hidden vector h t (s, r) by using the aggregated information g(N (s) t ) at the current step, the past value h t-1 (s, r) and also the global hidden vector H t . The hidden vector h t (s) is updated in a similar way. For the aggregation of all events g(Gt), we define g(Gt) = max({g(N (s) t )}s), which is from the element-wise max-pooling operation over all g(N (s) t ). We use Gated Recurrent Units Cho et al. (2014) as RNN. Details are described in Section A. For each subject entity s, it can interact with multiple relations and object entities at each time step t. In other words, the set N (s) t can contain multiple events. Designing effective aggregation functions g to aggregate information from N (s) t for s is therefore a nontrivial problem. Next, we introduce how we design g(•) in RE-NET.

3.2. MULTI-RELATIONAL GRAPH (RGCN) AGGREGATOR:

Here we discuss the aggregate function g(•), which capture different kinds of neighborhood information for each subject entity and relation, i.e., (s, r). We first introduce two simple aggregation functions, i.e., mean pooling aggregator and attentive pooling aggregator. These two simple aggregators only collect neighboring entities under the same relation r. Then we introduce a more powerful aggregation function, i.e., multi-relational aggregator.

Mean Pooling Aggregator. The baseline aggregator simply takes the element-wise mean of the vectors in {eo : o ∈ N (s,r) t }, where N (s,r) t is a set of objects interacted with s under r at t. But the mean aggregator treats all neighboring objects equally, and thus ignores the different importance of each neighbor entity.

Attentive Pooling Aggregator. We define an attentive aggregator based on the additive attention introduced in (Bahdanau et al., 2015) to distinguish the important entities for (s, r). The aggregate function is defined as g(N (s,r) t ) = o∈N (s,r) t αoeo, where αo = softmax(v tanh(W (es; er; eo))). v ∈ R d and W ∈ R d×3d are trainable weight matrices. By adding the attention function of the subject and the relation, the weight can determine how relevant each object entity is to the subject and relation.

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

EQUATION

where initial hidden representations for each node (h

(0)

o ) are set to trainable embedding vectors (e o ) for each node.

Basically, each relation can derive a local graph structure between entities, which further yield a message on each entity by aggregating the information from the neighbors of that entity, i.e.,

o∈N (s,r) t 1 cs W (l) r h (l)

o . The overall message on each entity is further computed by aggregating all the relation-specific messages, i.e., r∈R o∈N (s,r)

t 1 cs W (l) r h (l) o . Finally, the aggregator g(N (s)

t ) is defined by combining both the overall message and the information from past steps, i.e., W (l) 0 h (l) s .

To distinguish between different relations, we introduce independent weight matrices {W (l) r } for each relation r. Furthermore, the aggregator collects representations of multi-hop neighbors by introducing multiple layers of the neural network, with each layer indexed by l. The number of layers determines the depth to which the node reaches to aggregate information from its local neighborhood. We depict this aggregator in Fig. 2 .

The major issue of this aggregator is that the number of parameters grows rapidly with the number of relations. In practice, this can easily lead to overfitting on rare relations and models of very large size. Thus, we adopt the block-diagonal decomposition (Schlichtkrull et al., 2018) , where each relation-specific weight matrix is decomposed into a block-diagonal by decomposing into lowdimensional matrices. W (l) r in equation 9 is defined as a block diagonal matrix, diag(A

(l) 1r , ..., A (l) Br ) where A (l) kr ∈ R (d (l+1) /B)×(d (l) /B

) and B is the number of basis matrices. The block decomposition reduces the number of parameters and helps to prevent overfitting.

3.3. PARAMETER LEARNING AND INFERENCE OF RE-NET:

Parameter Learning via Event Prediction. The (object) entity prediction given (s, r) can be viewed as a multi-class classification task, where each class corresponds to one object entity. Similarly, relation prediction given s and subject entity prediction can be considered as a multi-class classification task. Here we omit the notation for previous events. To learn weights and representations for entities and relations, we adopt a multi-class cross-entropy loss to the model's output.The loss function is comprised of three losses and is defined as:

EQUATION

)

where G is set of events, and λ 1 and λ 2 are importance parameters that control the importance of each loss term. λ 1 and λ 2 can chosen depending on a task. If the task aims to predict o given (s, r), then we can give small values to λ 1 and λ 2 . Each probability is defined in equations 3, 4, and 5, respectively. We apply teacher forcing for model training over historical data. 

, r k , o k , t )} t = t + 1

Estimate the probability of each event P(s, r, o| Ĝt+1:t+∆t-1, G:t) by Equation 2.

Estimate the joint distribution of all events P(Gt+∆t| Ĝt+1:t+∆t-1, G:t) by Equation 1. return P(Gt+∆t| Ĝt+1:t+∆t-1, G:t) as the estimation.

Multi-step Inference over Time. At inference time, RE-NET seeks to predict the forthcoming events based on the previous observations. Suppose that the current time is t and we aim at predicting events at time t + ∆t, then the problem of multi-step inference can be formalized as an inference problem, i.e., inferring the conditional probability P(Gt+∆t|G:t). The problem is nontrivial as we need to integrate over all G t+1:t+∆t-1 . To achieve efficient inference, we draw a sample of G t+1:t+∆t-1 , and estimate the conditional probability in the following way:

P(G t+∆t |G :t ) = Gt+1:t+∆t-1 P(G t+∆t |G :t+∆t-1 )P(G t+∆t-1 |G :t+∆t-2 ) • • • P(G t+1 |G :t ) = E P(Gt+1:t+∆t-1|G:t) [P(G t+∆t |G :t+∆t-1 )] P(G t+∆t | Ĝt+1:t+∆t-1 , G :t ) (11)

Such an inference procedure is intuitive. Basically, one starts with computing P(Gt+1|G:t), and drawing a sample Ĝt+1 from the conditional distribution. With this sample, one can further compute P(Gt+2| Ĝt+1, G:t). By iteratively computing the conditional distribution for G t and drawing a sample from it, one can eventually estimate P(Gt+∆t|G:t) as P(Gt+∆t| Ĝt+1:t+∆t-1, G:t). In practice, we can improve the estimation by drawing multiple graph samples at each step, but RE-NET already performs very well with a single sample, and thus we only draw one sample graph at each step for better efficiency. Based on the estimation of the conditional distribution, we can further predict events which are likely to form in the future. We summarize the detailed inference algorithm in Algorithm 1. In Algorithm 1, we sample one graph at a time. To obtain the graph, we first sample M number of s (line 3) and pick top-k triples (line 4). Then we have a knowledge graph at time t (line 5).

Computational Complexity Analysis.:

Here we analyze the time complexity of the graph generation algorithm 1. To compute P(s t |G t-m:t-1 ) (equation 5), it takes O(|E|Lm), where |E| is the maximum number of triples among {G t-m , ..., G t-1 }, L is the number of layers of aggregation, and m is the number of the past time steps since we unroll m time steps in RNN. From this probability, we sample M number of subjects s. To compute P(s t , r t , o t |G t-m:t-1 ) (equation 2), it takes O(D L m), where D is the maximum degree of entities. To get probabilities of all possible triples given sampled subjects, it needs O(M |R||O|D L m) where |R| is the total number of relations and |O| is the total number of entities. Thus, the time complexity for generating one graph is

O(|E|Lm + M |R||O|(D L m + log k))

where k is the cutoff number for picking top-k triples. The time complexity is linear to the number of entities and relations, and the number of sampled s.

4. EXPERIMENTS:

Evaluating the quality of generated graphs is challenging, especially in knowledge graphs (Theis et al., 2015) . Instead, we evaluate our proposed method on a link prediction task on temporal knowledge graphs. 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)), based on the 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.

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 parameter sensitivity and ablation of our proposed method. Section 4.1

Table 1: Performance comparison on temporal link prediction (average metrics in % over 5 runs) on three event-based TKG datasets with filtered setting. RE-NET achieves the best results. Results with raw setting are in the supplementary material.

Method:

ICEWS18 -filtered GDELT -filtered ICEWS14 -filtered MRR H@1 H@3 H@10 MRR H@1 H@3 H@10 MRR H@1 H@3 H@10 summarizes the datasets, and the supplementary material contains additional information. In all these experiments, we perform predictions on time stamps that are not observed during training.

4.1. EXPERIMENTAL SET-UP:

Datasets. We use five datasets: 1) three event-based temporal knowledge graphs: ICEWS18 (Boschee et al., 2015) , ICEWS14 (Trivedi et al., 2017) , and GDELT (Leetaru & Schrodt, 2013) ; and 2) two knowledge graphs where temporally associated facts have meta-facts as (s, r, o, [t s , t e ]) where t s is the starting time point and t e is the ending time point: WIKI (Leblay & Chekol, 2018) and YAGO (Mahdisoltani et al., 2014) . The details of the datasets are described in Section B.

Evaluation Setting and Metrics. For each dataset except ICEWS14, we split it into three subsets, i.e., train(80%)/valid(10%)/test(10%), by time stamps. Thus, (times of train) < (times of valid) < (times of test). We report Mean Reciprocal Ranks (MRR) and Hits@1/3/10, using the filtered version and the raw version of the datasets. Similar to the definition of filtered setting in (Bordes et al., 2013) , during evaluation, we remove from the list of corrupted triplets all the triplets that appear either in the train, dev, or test set.

Competitors. We compare our approach to baselines for static graphs and temporal graphs:

(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 TransE (Bordes et al., 2013) , DistMult (Yang et al., 2015) , ComplEx (Trouillon et al., 2016) , 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-Evolve3 (Trivedi et al., 2017) In this section we compare our proposed method with other baselines. The test results are obtained by averaged metrics over the entire test sets on datasets.

Performances on Event-based TKGs. Table 1 summarizes results on three event-based datasets: ICEWS18, GDELT, and ICEWS14. Our proposed RE-NET outperforms all other baselines on these datasets. Static methods show good results but they underperform our method since they do not consider temporal factors. Also, RE-NET outperforms all other temporal methods, which demonstrates effectiveness of the proposed method. The modified Know-Evolve with our MLP decoder (Know-Evovle+MLP) achieves the better performances than Know-Evolve, which shows effectiveness of our MLP decoder, but there is still a large gap from our model. We notice that Know-Evolve and DyRep has a gradient exploding issue on their encoder since their RNN-like structures keep accumulating embedding over time. This issue degrades their performances. Graph Convolutional Recurrent Network (GCRN) is not for dynamic and multi-relational graphs, and is not capable of link prediction. We modified the model to work on dynamic graphs and our problem setting by using RGCN instead of GCN, and our MLP decoder. The modified model (R-GCRN+MLP) shows good performances but it does not outperform our method. 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 sophisticated modeling for the recurrent encoder. These results of the combined models suggest the our recurrent event encoder shows better performances in link prediction. Importantly, all these temporal methods are not capable of multi-step inference, while RE-NET sequentially infers multi-step events.

Performances on Public KGs. Previous results have proved the effectiveness of RE-NET, and here we will compare the method on the Public KGs: WIKI and YAGO. In Table 2 , our proposed RE-NET outperforms all other baselines. 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 2 0 0 8  2 0 0 9  2 0 1 0  2 0 1 1  2 0 1 2  2 0 1 3  2 0 1 4  2 0 1 5  2 0 1 6  2 0 1 methods. which implies that RE-NET effectively infers new events using a powerful event encoder and an aggregator, and provides accurate prediction results.

Performances of Prediction over Time. Next, we further study performances of RE-NET over time.

Figs. 3 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. Performances of each method fluctuate since testing entities are different at each time step. We notice that with the increase of time step, the difference between RE-NET and ConvE is getting smaller as shown in Fig. 3 . This is expected since further future events are harder to predict. Furthermore, we can think that the decline of the performances is due to the generation of a long graph sequence. To estimate the joint probability distribution of all events in a distant future, RE-NET should generates a long sequence of graphs. The quality of generated graphs deteriorates when RE-NET generates a long graph sequence.

4.3. ABLATION STUDY:

In this section, we study the effect of variations in RE-NET. To evaluate the importance of different components of RE-NET, we varied our base model in different ways, measuring the change in performance on the link prediction task on the ICEWS18 dataset. We present the results in Tables 1, 2 , and Figs. 4.

Different Aggregators. We first analyze the effect of the aggregator. In Tables 1, 2 , we observe that RE-NET w/o agg. hurts model quality. This suggests that introducing aggregators make the model capable of dealing with concurrent events and aggregators improve the prediction performances. Fig. 4a shows the performances of RE-NET with different aggregators. Among them, RGCN aggregator outperforms other aggregators. This aggregator has the advantage of exploring multirelational neighbors not limited to neighbors under the same relation. Also, RE-NET with an attentive aggregator shows better performances than RE-NET with a mean aggregator, which implies that giving different attention weights to each neighbor helps predictions.

Global Information. We further observe that representations from global graph structures help the predictions. Fig. 4b shows effectiveness of a representation of global graph structures. We consider that global representations give information beyond local graph structures. Empirical Probabilities. Here, we study the role of P(s t |G t-m:t-1 ) and P(r t |s, G t-m:t-1 ). We simply denote them as P(s) and P(r) for brevity. Also, P(s t , r t |G t-m:t-1 ) (or simply P(s, r)) is equivalent to P(s)P(r). In Fig 4c , emp. P(s) denotes a model with empirical P(s) (or P e (s)) which is defined as P e (s) = (# of s-related triples) / (total # of triples). Also, emp. P(s, r) denotes a model with P e (s) and P e (r) which is defined as P e (r) = (# of r-related triples) / (total # of triples). Thus, P e (s, r) = P e (s)P e (r). RE-NET use a trained P(s) and P(r). The results show that the trained P(s) and P(r) help RE-NET for multi-step predictions. Using P s (s) underperforms RE-NET, and using P e (s, r) = P e (s)P e (r) shows the worst performances, which suggests that training each part of the probability in equation 2 gives better prediction performances.

4.4. 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. Furthermore, we study the layers of RGCN aggregator. We report the performance change of RE-NET on the ICEWS18 dataset by varying the hyper-parameters in Table 5 .

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. Figure 5a shows the performances with varying length 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. This implies that long history does not make big differences.

Cut-off Position k at Inference Time. To generate a graph at each time, we cut off top-k triples on ranking results. Fig. 5b shows the performances with choosing different cutoff position k. When k is 0, RE-NET does not generate graphs for estimating P(G t+∆t |G :t ), and it shows the lowest result. which means RE-NET performs single-step predictions, . When k is larger, the performance is getting higher and it is saturated after 500. We notice that the conditional distribution P(G t+∆t |G :t ) can be approximated by P(G t+∆t | Ĝt+1:t+∆t-1 , G :t ) by using a larger cutoff position.

Layers of RGCN Aggregator. We examine the number of layers in the RGCN aggregator. The number of layers in the aggregator means the depth to which the node reaches. Fig. 5c shows the performances according to different numbers of layers of RGCN. We notice that 2-layered RGCN improves the performances 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.

5. CONCLUSION:

In this work, we studied the sequential graph generation on temporal knowledge graphs. To tackle this problem, we proposed Recurrent Event Network (RE-NET) which models temporal, multi-relational, and concurrent interactions between entities. A recurrent event encoder in RE-NET summarizes information of the past event sequences, and a neighborhood aggregator collects the information of concurrent. RE-NET defines the joint probability of all events, and thus is capable of inferring global structures in a sequential manner. We tested the proposed model on a link prediction task on temporal knowledge graphs. The experiment revealed that the proposed RE-NET outperforms all the static and temporal methods and our extensive experiments shows its strength. Interesting future work includes modeling lasting events and performing inference on the long-lasting graph structures.

A RECURRENT EVENT ENCODER:

We define a recurrent event encoder based on RNN as follows: h t (s, r) = RNN(g(N t (s)), H t , h t-1 (s, r)).

We use Gated Recurrent Units (Cho et al., 2014) as RNN: a t = [e s : e r : g(N t (s)) :

H t ] z t = σ(W z a t + U z h t-1 ) r t = σ(W r a t + U r h t-1 ) h t = (1 -z t ) • h t-1 + z t • tanh(W h a t + U h (r t • h t-1 )

), where : is concatenation, σ(•) is an activation function, and • is a Hadamard operator. The input is a concatenation of four vectors: subject embedding, object embedding, aggregation of neighborhood representations, and global information vector (e s , e r , g(N t (s)), H t ). h t (s) and H t are similarly defined. For h t (s), a concatenation of subject embedding, aggregation of neighborhood representations, and global information vector (e s , g(N t (s)), H t ) is input. For H t , aggregation of the whole graph representations g(G t ) is input.

B DATASET:

We use five datasets: 1) three event-based temporal knowledge graphs and 2) two knowledge graphs where temporally associated facts have meta-facts as (s, r, o, [t s , t e ]) where t s is the starting time point and t e is the ending time point. The first group of graphs includes Integrated Crisis Early Warning System (ICEWS18 (Boschee et al., 2015) and ICEWS14 (Trivedi et al., 2017) ), and Global Database of Events, Language, and Tone (GDELT) (Leetaru & Schrodt, 2013) . The second group of graphs includes WIKI (Leblay & Chekol, 2018) and YAGO (Mahdisoltani et al., 2014) .

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.

WIKI and YAGO datasets have temporally associated facts (s, r, o, [t s , t e ]). We preprocess the datasets such that each fact is converted to {(s, r, o, t s ), (s, r, o, t s + 1 t ), ..., (s, r, o, t e )} where 1 t is a unit time to ensure each fact has a sequence of events. Noisy events of early years are removed (before 1786 for WIKI and 1830 for YAGO).

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.

Dataset statistics are described on table 3. 

C DETAILED EXPERIMENTAL SETTINGS:

Model details of RE-NET. We use Gated Recurrent Units (Cho et al., 2014) as our recurrent event encoder, where the length of history is set as m = 10 which means saving past 10 event sequences.

If the events related to s are sparse, we check the previous time steps until we get m previous time steps related to the entity s. We pretrain the parameters related to equations 5 and 8 due to large size of training graphs. We use a multi-relational aggregator to compute H t . The aggregator provides hidden representations for each node and we max-pool over all hidden representations to get H t . At inference time, RE-NET performs multi-step prediction across the time stamps in dev and test sets. To examine aggregation techniques in other baselines, we combine ConvE and R-GCN. We first run 2-layered R-GCN over the training graph and then each node has its own transformed representations. We run ConvE on this transformed representations. As in Table 5 , ConvE+R-GCN shows better performances than R-GCN and worse performances than ConvE, which implies that the aggregation technique is not helpful to ConvE. However, aggregators in our framework is a complementary and necessary component to the temporal part, which shows superiority over the baselines.

D.3 COMPARISONS WITH DYNAMIC METHODS.:

Here we compare our method with dynamic methods on homogeneous graphs: EvolveGCN-O (Pareja et al., 2019) , DynGEM (Goyal et al., 2018) , dyngraph2vecAE (Goyal et al., 2019) , DynTriad (Zhou et al., 2018b) , and tNodeEmbed (Singer et al., 2019) . 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.

Experimental Settings. 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 Theorem 1 Let {G t } τ t=1 be the snapshot of temporal knowledge graph after τ time-steps. Let h 0 v ∈ R d , v ∈ {s i } ∪ {o i } to be the input feature representation for Algorithm 1 of each entity node v. Suppose that there exists a fixed positive constant C ∈ R + such that ||h 0 v -h 0 v || > C for all pair of all pair of entities v, v . Then we have that ∀ > 0, there exist a parameter setting Θ for RE-NET s.t. after K = 4 layers of aggregation, |h K v,τ -c v,τ , | < , ∀v ∈ V, ∀τ ∈ [T ], where h K v,τ are output values generated by RE-NET and c v,τ are clustering coefficients of {G i } τ i=1 .

Observation 1 Consider a temporal graph under stochastic block model described in Section G.2. Let h 0 v ∈ R d , v ∈ {s i } ∪ {o i } to be the input feature representation for Algorithm 1 of each node. Suppose that a constant portion p c of input representations can be linearly separated by a hyperplane, while the representation of other nodes lies on the hyperplane. There exists a parameter setting of RE-NET that can output the probability that new node j connected to node i.

G.1 PROOF FOR THEOREM 1:

Using pooling aggregator of GraphSAGE, we can actually copy its behavior by setting recurrent weight matrix of the RNN model to be 0. In this case, we lose all time-dependency our RE-NET and the representation model becomes time-invariant. However, RE-NET have exactly the same model capacity as GraphSAGE.

G.2 ANALYSIS FOR OBSERVATION 1:

Here we define the generation process of our temporal graph. Assume that the generation process of the graph follows a stochastic block model, and there are two communities in the graph. Half of the nodes belong to community A and the other half belong to community B. Nodes within one community have probability p s to be connected while other pairs have p d < p s probability to be connected. The edges in the graph are introduced into the graph in a time. Suppose a sequence of time-steps, a new node is introduced to the community and each edge is added to the graph. This observation follows from three facts: (1) For each node v j in the neighborhood N (v), using pooling aggregator, we can detect their community assignment s j . We assign the output of community A to be +1 and the output of community B to be -1. (2) The error of incorrectly discerning the community of a node decrease exponentially with the number of links. For example let the node v be in community A. Let the total number of nodes at time t to be n t , by Hoeffding's inequality we have P( j:vj ∈N (j) t s j < 0) < exp(-2(p s -p d ) 2 |N (j) t |)

(3) Given the correct community classification, the relation classifier is able to predict the probability of linking nodes.

Combining these three facts, RE-NET is able to infer the community structure of the node.

:

Code and data have been uploaded and will be published upon acceptance of the paper.

The same triple (s, r, o) may occur multiple times in different time stamps, yielding different event quadruples.

*: We found a problematic formulation in Know-Evolve when dealing with concurrent events (Eq. (3) in its paper) and a flaw in its evaluation code. The performance dramatically drops after fixing the evaluation code. Details of this issues are discussed in Section F.

Figures and Tables:

Figure 1: Illustration of (a) temporal knowledge graph and (b) the Recurrent Event Network architecture. RE-NET employs an RNN to capture s-related interactions N (s) t

Figure 3: Performance of temporal link prediction over future time stamps with filtered Hits@3. RE-NET consistently outperforms the baselines.

Figure 5: Parameter sensitivity on RE-NET. We study the effects of (a) length of RNN history in event sequence encoder, (b) cutoff position at inference time, and (c) number of RGCN layers in neigborhood aggregation.

Figure6: Performance of temporal link prediction over future time stamps. We report filtered MRR (average metrics in %) on the test sets of ICEWS18, GDELT, WIKI, and YAGO datasets.

Performance comparison on temporal link prediction (average metrics in % over 5 runs) on two public temporal knowledge graphs, i.e., WIKI and YAGO.

Table content: <table><tr><td/><td>Method</td><td colspan="11">WIKI -filtered MRR H@3 H@10 MRR H@3 H@10 MRR H@3 H@10 MRR H@3 H@10 WIKI -raw YAGO -filtered YAGO -raw</td></tr><tr><td/><td>TransE</td><td colspan="11">46.68 49.71 51.71 26.21 31.25 39.06 48.97 62.45 66.05 33.85 48.19 59.50</td></tr><tr><td/><td>DistMult</td><td colspan="11">46.12 49.81 51.38 27.96 32.45 39.51 59.47 60.91 65.26 44.05 49.70 59.94</td></tr><tr><td>Static</td><td>ComplEx R-GCN ConvE</td><td colspan="11">47.84 50.08 51.39 27.69 31.99 38.61 61.29 62.28 66.82 44.09 49.57 59.64 37.57 39.66 41.90 13.96 15.75 22.05 41.30 44.44 52.68 20.25 24.01 37.30 47.57 50.10 50.53 26.03 30.51 39.18 62.32 63.97 65.60 41.22 47.03 59.90</td></tr><tr><td/><td>RotatE</td><td colspan="11">50.67 50.74 50.88 26.08 31.63 38.51 65.09 65.67 66.16 42.08 46.77 59.39</td></tr><tr><td/><td>HyTE</td><td colspan="11">43.02 45.12 49.49 25.40 29.16 37.54 23.16 45.74 51.94 14.42 39.73 46.98</td></tr><tr><td/><td>TTransE</td><td colspan="11">31.74 36.25 43.45 20.66 23.88 33.04 32.57 43.39 53.37 26.10 36.28 47.73</td></tr><tr><td/><td>TA-DistMult</td><td colspan="11">48.09 49.51 51.70 26.44 31.36 38.97 61.72 65.32 67.19 44.98 50.64 61.11</td></tr><tr><td/><td>Know-Evolve*</td><td>0.09 00.03</td><td>0.10</td><td>0.03</td><td>0</td><td>0.04</td><td>00.07</td><td>0</td><td>0.04</td><td>0.02</td><td>0</td><td>0.01</td></tr><tr><td>Temporal</td><td colspan="12">Know-Evolve+MLP DyRep+MLP R-GCRN+MLP RE-NET w/o multi-step 51.01 51.14 52.91 29.91 32.60 40.29 64.21 64.70 67.11 45.88 51.78 60.97 12.64 14.33 21.57 10.54 13.08 20.21 6.19 6.59 11.48 5.23 5.63 10.23 11.60 12.74 21.65 10.41 12.06 20.93 5.87 6.54 11.98 4.98 5.54 10.19 47.71 48.14 49.66 28.68 31.44 38.58 53.89 56.06 61.19 43.71 48.53 56.98</td></tr><tr><td/><td>RE-NET w/o agg.</td><td colspan="11">31.08 33.98 45.53 17.55 20.65 33.51 33.86 36.89 50.72 27.37 30.20 46.35</td></tr><tr><td/><td>RE-NET w. mean agg.</td><td colspan="11">51.13 51.37 53.01 30.19 32.94 40.57 65.10 65.24 67.34 46.33 52.49 61.21</td></tr><tr><td/><td>RE-NET w. attn agg.</td><td colspan="11">51.25 52.54 53.12 30.25 30.12 40.86 65.13 67.54 67.87 46.56 52.56 61.35</td></tr><tr><td/><td>RE-NET</td><td colspan="11">51.97 52.07 53.91 30.87 33.55 41.27 65.16 65.63 68.08 46.81 52.71 61.93</td></tr><tr><td/><td>RE-NET w. GT (s, r)</td><td colspan="11">53.57 54.10 55.72 32.44 35.42 43.16 66.80 67.23 69.77 48.60 54.20 63.59</td></tr></table>

Dataset Statistics.

Table content: <table><tr><td>Data</td><td>N train</td><td>N valid</td><td>N test</td><td>N ent</td><td colspan="2">N rel Time granularity</td></tr><tr><td>GDELT</td><td colspan="4">1,734,399 238,765 305,241 7,691</td><td>240</td><td>15 mins</td></tr><tr><td>ICEWS18</td><td>373,018</td><td>45,995</td><td colspan="3">49,545 23,033 256</td><td>24 hours</td></tr><tr><td>ICEWS14</td><td>323,895</td><td>-</td><td colspan="3">341,409 12,498 260</td><td>24 hours</td></tr><tr><td>WIKI</td><td>539,286</td><td>67,538</td><td colspan="2">63,110 12,554</td><td>24</td><td>1 year</td></tr><tr><td>YAGO</td><td>161,540</td><td>19,523</td><td colspan="2">20,026 10,623</td><td>10</td><td>1 year</td></tr></table>

Performance comparison on temporal link prediction on three TKG datasets with filtered metrics. RE-NET achieves the best results.

Table content: <table><tr><td>Method</td><td colspan="12">ICEWS18 -filtered MRR H@1 H@3 H@10 MRR H@1 H@3 H@10 MRR H@1 H@3 H@10 ICEWS14 -filtered WIKI -filtered</td></tr><tr><td>R-GCN</td><td colspan="12">23.19 16.36 25.34 36.48 26.31 18.23 30.43 45.34 37.57 37.44 39.66 41.90</td></tr><tr><td>ConvE</td><td colspan="12">36.67 28.51 39.80 50.69 40.73 33.20 43.92 54.35 47.57 48.89 50.10 50.53</td></tr><tr><td>ConvE+RGCN</td><td colspan="12">24.59 17.77 27.19 37.41 27.76 20.23 30.13 42.16 38.76 38.46 40.88 43.12</td></tr><tr><td>EvolveRGCN</td><td colspan="12">18.50 16.38 19.19 22.09 21.70 18.21 22.81 28.04 36.58 32.50 38.10 41.30</td></tr><tr><td>DynGEM</td><td>0.00</td><td>0</td><td>0</td><td>0</td><td>0.01</td><td>0</td><td>0</td><td>0</td><td>0.01</td><td>0</td><td>0</td><td>0</td></tr><tr><td colspan="2">dyngraph2vecAE 1.88</td><td>1.77</td><td>1.99</td><td>2.02</td><td colspan="4">11.30 8.67 13.31 15.66</td><td>1.08</td><td>1.05</td><td>1.09</td><td>1.10</td></tr><tr><td>DynTriad</td><td>3.48</td><td>0</td><td>3.55</td><td>11.47</td><td>8.49</td><td>0</td><td colspan="2">12.45 24.24</td><td colspan="3">2.62 00.01 4.26</td><td>6.63</td></tr><tr><td>tNodeEmbed</td><td>8.32</td><td>3.19</td><td>9.74</td><td colspan="5">17.47 17.84 9.98 20.16 32.88</td><td>9.54</td><td colspan="3">5.78 10.44 16.60</td></tr><tr><td>RE-NET</td><td colspan="12">42.93 36.19 45.47 55.80 45.71 38.42 49.06 59.12 51.97 51.01 52.07 53.91</td></tr><tr><td colspan="5">D ADDITIONAL EXPERIMENTS</td><td/><td/><td/><td/><td/><td/><td/><td/></tr></table>



Table content: <table><tr><td>shows the performance comparison on ICEWS18, GDELT, ICEWS14 with raw settings. Our</td></tr><tr><td>proposed RE-NET outperforms all other baselines. Figs. 6 shows the performance comparisons over</td></tr><tr><td>different time stamps on the ICEWS18, GDELT, WIKI and YAGO datasets with filtered MRR. Our</td></tr><tr><td>proposed RE-NET consistently outperform baselines over time.</td></tr><tr><td>D.2 COMPARISONS WITH CONVE+RGCN.</td></tr></table>

Peer review (iclr2020):
This paper properly applied several technique from RNN and graph neural networks to model dynamically-evolving, multi-relational graph data. There are two key component: a RNN to encode temporal information from the past event sequences, and a neighborhood aggregator collects the information from the neighbor nodes. The contribution on RNN part is design the loss and parameterizes the tuple of the graph. The contribution of the second part was adapting Multi-Relational Aggregator to this network. The paper is well-written. Although I*m familiar with the dataset, the analysis and comparison seems thorough. I*m leaning to reject or give borderline for this paper because (1) This paper is more like an application paper. Although the two component is carefully designed, the are more like direct application. I*m not challenge this paper is not good for the target task. But from the point of view on Machine learning / deep learning, there is not much insight from it. The technical difficult was more from how to make existing technique to fit this new problem. This *new* problem seems more fit to data mining conference. (2) The experiments give tons of number but it lack of detailed analysis, like specific win/loss case of this model. As a more application-side paper, these concrete example can help the reader understand why this design outperform others. For example, it can show what the attention weights look like, and compare to the proposed aggregator. Some questions: [This question is directly related to my decision] Does this the first paper to apply autoregressive to knowledge graph? from related work, the answer is no. Can the author clarify more on this sentence? *In contrast, our proposed method, RE-NET, augments a RNN with message passing procedure between entity neighborhood to encode temporal dependency between (concurrent) events (i.e., entity interactions), instead of using the RNN to memorize historical information about the node representations.* The paper give complexity of this algorithm but no comments about how it compare with other method and how practical it is. It lacks of some details for the model: (1) what is the RNN structure? (2) For the aggregator, what is the detailed formulation of h_o^0?