TiRGN: Time-Guided Recurrent Graph Network with Local-Global Historical Patterns for Temporal Knowledge Graph Reasoning

1 Introduction

Knowledge graphs (KGs) have been widely used in intelligent applications, such as question answering, recommendation systems, and information retrieval. However, the incompleteness of KGs limits their performance in downstream tasks. In this regard, there have been many studies focusing on the reasoning and completion of static KGs. In reality, many data often have complex dynamics, and it is a challenge to characterize the dynamics and reason over temporal knowledge graphs (TKGs).

Each fact in TKGs is represented by a quadruple containing a timestamp, which indicates that the fact occurred at a specific time. For example, (Barack Obama, impose sanctions, Sudan, 2013-11-7) indicates the fact that Obama imposed sanctions on Sudan in 2013-11-7. In this paper, we mainly solve the extrapolation problem of TKG reasoning, including entity prediction and relation prediction. This is significant for many practical applications, such as event process induction, social relation prediction, disaster relief, and financial analysis.

∗Corresponding author.

Making accurate predictions about future facts needs to learn more about historical facts based on the laws of historical development. According to historic recurrence [Trompf, 1979] and social cycle theory [Schlesinger, 1999], historical facts may have a repetitive or even cyclical pattern. Besides, according to human cognition, the historical facts at adjacent timestamps have a sequential pattern, in which the evolution law of adjacent events can be captured to predict what will happen next. For example, as shown in Figure 1, we predict the query (Barack Obama, impose sanctions, ?, 2013-11-7). We can get a series of historical adjacent facts and global facts related to the query. The countries in the relevant local facts include Iran which has recently been sanctioned, and Sudan which has recently criticized Obama. In the relevant global facts, Obama imposed sanctions on eight countries, including sanctions on Iran 46 times and Sudan eight times. If both local and global facts are considered, we can narrow the scope of the prediction results of the example query to Iran and Sudan. In addition, we find that Obama imposed sanctions on Sudan around November annually from 2009 to 2012. Considering periodicity and the other two historical patterns simultaneously, it is more likely that the predicted result will be Sudan, which is indeed the case. Therefore, capturing different historical patterns can constrain the range of the final prediction results and improve accuracy.

Recently, some methods have tried to extract relevant historical information for different queries in a heuristic way. However, they did not comprehensively consider the different historical characteristics. RE-Net [Jin et al., 2020] and CyGNet [Zhu et al., 2021] only consider the entities or entityrelation pairs in the global history. Among them, RE-Net can only capture global facts within a limited time. Otherwise, it will cause huge time complexity. CyGNet describes global facts by occurrence frequency, which leads to the narrow results that the prediction always tends to the facts with the highest frequency. RE-GCN [Li et al., 2021b] attempts to model local historical dependency but lacks the capture of global historical information. Furthermore, although these methods extract historical information, none of them models the periodicity of historical facts.

To this end, we propose a model that captures multiple historical characteristics with local-global historical information, called Time-Guided Recurrent Graph Network (TiRGN). The main ideas of TiRGN are (1) to combine the local and global historical information to capture sequential, repetitive, and cyclical patterns of historical facts, (2) to regard the temporal subgraphs at adjacent timestamps as a sequence and regard the subgraphs at global timestamps as a constraint, and (3) to design a time-guided periodic decoder by using model-independent time vectors. Specifically, in order to capture the sequential pattern of historical facts, we design a graph neural network-based encoder with a double recurrent mechanism to simultaneously evolve the entity and relation representations at adjacent timestamps. In addition, we use the global one-hop or multi-hop repeated history information to capture repetitive patterns of historical facts. Furthermore, the time vectors involved in the model can capture the periodicity of facts. Finally, the scores calculated by the decoder are used to realize entity and relation predictions.

In general, this work presents the following contributions:

• We propose a representation learning model TiRGN for TKG reasoning, which simultaneously considers the sequential, repetitive and cyclical patterns of historical facts. As far as we know, this is the first time to integrate these historical characteristics for TKG reasoning.
• We design a double recurrent mechanism with longdistance dependencies to encode the adjacent subgraph sequences and use a low-complexity global history encoder to collect repeated facts. We use periodic time vectors to guide the decoder and realize the trade-off between local and global historical information.
• Experiments on six public TKG datasets demonstrate that TiRGN is consistently effective on both entity prediction and relation prediction.

2 RelatedWork

Recently, some studies have tried to incorporate temporal information into KG reasoning, which can be classified into two settings: interpolation and extrapolation [Jin et al., 2020]. Interpolation is used to predict missing historical facts. For this setting, several embedding-based methods associate time with facts and map them to a low-dimensional space [Garc´ıaDur´an et al., 2018; Ma et al., 2019; Wu et al., 2020]. TTransE [Jiang et al., 2016] is a variant of TransE [Bordes et al., 2013], which treats relation and time as translation between entities. DE-SimplE [Goel et al., 2020] and ChronoR [Sadeghian et al., 2021] characterize temporal information by learning the embeddings of different timestamps. However, these models cannot predict future facts.

This paper focuses on the extrapolation setting of predicting future facts according to history, which has been studied recently. Know-Evolve [Trivedi et al., 2017] and DyREP [Trivedi et al., 2019] use the temporal point process to model the occurrence of facts in TKGs. Glean [Deng et al., 2020] incorporates relational and word contexts to enrich the features of facts for reasoning. RE-NET [Jin et al., 2020] employs a neighborhood aggregator and recurrent event encoder to model the historical facts as subgraph sequences. TANGO [Han et al., 2021b] explores the neural ordinary differential equation to build a continuous-time reasoning model. xERTE [Han et al., 2021a] uses a subgraph sampling technique to construct interpretable reasoning graphs. CluSTeR [Li et al., 2021a] and TITer [Sun et al., 2021] both use reinforcement learning to search a series of historical facts for reasoning. CyGNet [Zhu et al., 2021] and RE-GCN [Li et al., 2021b] are the most relevant work to us. CyGNet uses a copy-generation mechanism to capture the global repetition frequency of facts. RE-GCN learns the evolutional representations of entities and relations at each timestamp through the structures that capture local historical dependency. However, none of the above methods simultaneously consider the sequential, repetitive, and cyclical historical facts.

3 The ProposedMethod

3.1 Notations

In this paper, we formalize a TKG G as a sequence of subgraphs, i.e., G = {G1, G2, . . . , GT}. The subgraph Gt = (E,R,Ft) at t is a directed multi-relational graph, where E is the set of entities, R is the set of relations, and Ft is the set of facts at t. A fact in Ft can be formalized as a quadruple (s, r, o, t), where s, o ∈ E and r ∈ R. It represents that there is a relation r between the subject entity s and the object entity o at t. For each quadruple (s, r, o, t), an inverse relation quadruple (o, r-1 , s, t) is often added to the dataset. TKG reasoning can be classified into entity prediction (s, r, ?, t) and relation prediction (s, ?, o, t) given the set of historical facts before t. For each prediction at t, we formalize the subgraph sequence of its previous m timestamps as Gt-m:t-1.

For all timestamps before t, the set of all candidate object entities for each entity prediction (s, r, ?, t) is denoted as C s,r t , and the set of all candidate relations for each relation prediction (s, ?, o, t) is denoted as C s,o t .

3.2 Model Overview

The overall framework of TiRGN is shown in Figure 2. According to the laws of historical development, TiRGN consists of three components, which are used to capture the sequential, repetitive, and cyclical patterns of historical facts, respectively. Local recurrent encoder is used to explore structural features and historical dependency. If there are facts in the subgraphs of adjacent timestamps containing the same semantic information as the query, the probability of predicting the entity in these facts will increase. According to common sense, TiRGN assumes that the closer the time of the facts, the more significant the impact on the final results. Global history encoder takes the relevant facts at all previous timestamps into account to avoid missing entities or relations that have not appeared at the adjacent timestamps. Periodicity is introduced into the decoder by the time vector generator to find possible periodic facts. Finally, TiRGN combines the periodic local and global decoders to realize the trade-off between the importance of local and global historical facts.

3.3 Local Recurrent Encoder

The local recurrent encoder focuses on the adjacent histories. For each query (s, r, ?, t), we consider the subgraphs Gm-1:t-1 of m adjacent timestamps. We aggregate and transfer the KG information from spatial and temporal views, respectively. Specifically, the graph convolutional network (GCN) is used to make single-step aggregation and the gated recurrent unit (GRU) is used among multiple timestamps to perform multi-step evolution.

Single-Step Aggregation

At each timestamp, we want to cover the facts related to the entity in the query as many as possible. Therefore, we design a one-dimensional convolution-based GCN, a multi-relation aggregator, to merge multiple relations and multi-hop neighbor information at a single timestamp. Compared with REGCN which sums relation embedding to entity embedding in GCN to make single-step aggregation, our TiRGN uses the one-dimensional convolution on entity embedding and relation embedding and thus can merge them better. The aggregator is defined as:

where hls,t , hlo,t denote the lth layer embeddings of entities s, o at t, Wlr , Wlo denote learnable weights and Wlr is relation-specific, co is a normalizing factor equal to the indegree of o, σ is the RReLu activation function, and ψ is the one-dimensional convolution operator. Note that when an entity does not have any relation with other entities in the subgraph, there will still be a self-loop edge to update it.

Multi-Step Evolution

For each query, in order to include the sequential dependencies of subgraphs at the previous timestamps, we use a double recurrent mechanism to update the representations of entities and relations progressively, i.e., entity-oriented GRU and relation-oriented GRU, so that it can obtain information at more distant timestamps. Entity-oriented GRU is used to update embeddings of entities in the sequence of subgraphs:

where Ht,Ht-1 ∈ R|E|×d are the d-dimensional entity embedding matrices at t and t - 1, and HGCN t-1 ∈ R|E|×d is the entity embedding matrix after singe-step aggeration at t - 1. For relations, in order to maintain the consistency with the update of the entity embedding in the subgraph sequence, relation-oriented GRU is also used for update:

where Hr,t is all entities connected to r at t, r′t is obtained by Ht-1 and Hr,t using mean pooling operation, R′t consists of rt of all relations, and Rt,Rt-1 ∈ R|R|×d are relation embedding matrices at t and t - 1. Rt is finally updated by Rt-1 and R′t through relation-oriented GRU.

3.4 Global History Encoder

The global history encoder is designed to get the repetitive global candidate facts, so as to provide global constraints for scoring in the decoder. For each query (s, r, ?, t) or (s, ?, o, t), we use this encoder to obtain candidate one-hop or multi-hop entities and relations. It is worth noting that, unlike CyGNet, we only consider whether the entity or relation has appeared before, without considering the frequency of its occurrence. We believe that directly using frequency as features may mislead prediction as the fact happened long ago does not necessarily occur in the future. The local recurrent encoder have been able to capture the impact of frequency of recent facts. This module is more to narrow the scope of prediction and avoid omissions rather than directly determining the final result. Specifically, we traverse all the subgraphs G0:t-1 before t and get the query results {cs,r 0 , cs,r 1 , . . . , cs,r t-1 }, {cs,o 0 , cs,o 1 , . . . , cs,o t-1 }. Then we take the union of the set of candidate entities at timestamp t:

Therefore, for the query (s, r, ?, t), the candidate entity matrix Ms,r t ∈ Z|E|×|R|×|E| assigns the values of positions existent in C s,r t to 1 and the non-existent to 0. The same operations and settings are also used for the candidate relation set C s,o t and candidate relation matrix Ms,o t ∈ Z|E|×|E|×|R| . Although these two matrices have large dimensions, they are both sparse (0, 1)-matrices, so they have a low space complexity and time complexity during access. In addition, the global history encoder can be used for different levels of candidate fact records, including one-hop and multi-hop. At present, we only consider the one-hop candidate set.

3.5 Time Guided Decoder

After getting the embeddings of the local entities and relations, as well as the candidate sets of global entities and relations, we use the local and global decoders to score the facts. Periodic and non-periodic time vectors guide the decoders to incorporate the periodicity of facts into the model when calculating local and global scores.

Periodic and Non-Periodic Time Vectors

Some facts happen periodically throughout the timeline, such as presidential elections, while some facts are more likely to happen within a certain period of time, e.g., the elected president will participate in more activities in a certain period of time. Therefore, it makes sense to consider both the periodicity and non-periodicity of the historical facts. We design the periodic and non-periodic time vectors, respectively:

where vp t and vnp t are d-dimensional periodic and nonperiodic time vectors, respectively, ωp, φp, ωnp and φnp are learnable parameters, and f is a periodic activation function. We chose the sine function as the periodic function because the sine function is expected to work well when extrapolated to future and out-of-sample data [Vaswani et al., 2017]. When f = sin, ωp and φp are the frequency and the phase-shift of the sine function. The period of vp t is 2π/ωp, so it has the same value at t and t + 2π/ωp. In addition, referring to Time2Vec [Kazemi et al., 2019], we can also prove that the both time vectors are invariant to the scaling of the time interval and adapt to datasets with different time intervals.

Time-ConvTransE/Time-ConvTransR

After obtaining time vectors, in order to perform entity prediction and relation prediction simultaneously, we design Time-ConvTransE and Time-ConvTransR inspired by ConvTransE [Shang et al., 2019] for the two tasks, respectively. Specifically, the decoder performs one-dimensional convolution on concatation of four embeddings (entity embedding hst , realtion embedding rt, two time embedding vp t , vnp t ) and scores the resulting representation. Formally, the convolution operator is computed as follows:

where c is the number of convolution kernels, K is the kernel width, n ∈ [0, d] indicates the entries in the output vector, and wc are learnable kernel parameters. ˆhst , ˆrt, ˆvp t and ˆvnp t are padding versions of hst , rt, vp t and vnp t , respectively. Similar to the improvement from TransE to TTransE, the convolution operation integrates time information while maintaining the translational property of embeddings. Thus, each convolution kernel forms an output vector mc (hst , rt, vp t , vnp t ) = [m0c ,m1c , . . . ,md-1 c ] can be aligned to get the matrix Mconv ∈ Rc×d .

After nonlinear one-dimensional convolution, the final output of Time-ConvTransE is defined as follows:

where vec is a feature map operator, and W ∈ Rcd×d is a matrix for linear transformation. Time-ConvTransR calculates the scores in the same way, only replacing rt with hot .

3.6 Scoring Function and Training Objective

Since the impact of local and global historical facts may be different, we weight their importance through a variable factor. If ht and rt in Eq. (9) are the entity and relation embeddings obtained by the local recurrent encoder, then we get the output of local time-guided decoder. The output of the global decoder needs to mask the position where the value of the candidate matrix is equal to 0. After calculating the local probability decoding score plocal and the global probability decoding score pglobal by softmax activation function, the final score is obtained by summing in proportion:

where variable factor α ∈ [0, 1]. Entity prediction and relation prediction calculate the score in the same way, but can take different values of α.

We regard both entity and relation predictions as multilabel learning problems and train them together. Therefore, the total loss that contains the loss of entity prediction Le and the loss of relation prediction Lr is formalized as:

where p (o | s, r, t) and p (r | s, o, t) are the final probabilistic scores of entity and relation predictions. ye t ∈ R|E| and yr t ∈ R|R| are the label vectors for the two tasks, of which the element is 1 if the fact occurs, otherwise 0.

4 Experiments

4.1 Setup

Datasets

We use six TKG datasets to evaluate TiRGN on entity prediction and relation prediction tasks, including ICEWS14

[Garc´ıa-Dur´an et al., 2018], ICEWS18 [Jin et al., 2020], ICEWS05-15 [Garc´ıa-Dur´an et al., 2018], GDELT [Jin et al., 2020], WIKI [Leblay and Chekol, 2018], and YAGO [Mahdisoltani et al., 2015]. We follow the preprocessing strategy for datasets in RE-NET.

Evaluation Metrics

We adopt two widely used metrics to evaluate the model performance on TKG reasoning, mean reciprocal rank (MRR) and Hits@k. MRR is the average reciprocal values of the ranks of the true entity candidates for all queries, and Hits@k represents the proportion of times that the true entity candidates appear in the top k of the ranked candidates. Some recent works mention that the filtered setting [Bordes et al., 2013] is not suitable for extrapolation on TKG reasoning [Han et al., 2021a; Han et al., 2021b]. Therefore, we use the time-aware filtered setting to report the experimental results.

Implementation Details

For all the datasets, the embedding dimension d is set to 200. The number of one-dimensional convolution-based GCN layers is set to 2 and the dropout rate for each layer is set to 0.2. The optimal local history lengths m are set to 10, 9, 15, 2, 1, and 7 for ICEWS18, ICEWS14, ICEWS05-15, WIKI, YAGO, and GDELT, respectively. Similar to RE-GCN, static graph constraints are added for ICEWS14, ICEWS18, and ICEWS05-15. For time-guided decoders, the number of channels is set to 50 and the kernel size is set to 4×3. We tried multiple α values from 0.1 to 0.9 and finally selected 0.3 as the global weight for all the datasets. Adam is used for parameter learning, and the learning rate is set to 0.001. The code is available in https://github.com/Liyyy2122/TiRGN.

4.2 Results

Results on Entity Prediction

The results of the entity prediction task are shown in Tables 1 and 2. On the six benchmark datasets, TiRGN continuously outperforms all baselines. Specifically, the performance of TiRGN is better than CyGNet because it not only considers the global historical repetitive facts but also pays attention to the facts at the adjacent timestamps and the periodicity of facts. RGCRN, RE-NET, TANGO, xERTE and RE-GCN consider the facts of adjacent timestamps and show strong performance in the experiment. Nevertheless, TiRGN uses a one-dimensional convolution-based GCN and double recurrence mechanism to capture more comprehensive structural features and historical dependency. Therefore, TiRGN is superior to these models that capture a single historical characteristics. Due to the historical facts search strategy based on reinforcement learning, TITer performs well on YAGO. The historical facts search strategy of TITer is suitable for the datasets with fewer timestamps and facts. However, once the dataset has too many timestamps, TITer will cause performance degradation due to its inability to model the ample search space, such as on the GDELT. In contrast, TiRGN only obtains the set of candidate entities and relations that record the occurrence of global facts without worrying about excessive complexity. Therefore, TiRGN has more substantial applicability for different datasets.

As shown in Tables 1 and 2, TiRGN has significantly improved the performance on ICEWS05-15 and GDELT with a large number of timestamps. It proves the effectiveness of capturing longer local historical dependencies through a double recurrent network. Besides, TiRGN has the most obvious effect on the datasets with more facts such as ICEWS05-15, WIKI, and GDELT, which also demonstrates that it is necessary to consider different historical characteristics when historical information is sufficient.

Results on Relation Prediction

Since some models are not designed for relation prediction, we select temporal models that can be used for relation prediction. As shown in Table 3, TiRGN performs better than all baselines. TiRGN achieves limited improvement on datasets that is easy to achieve high performance due to few relations. For the datasets with a larger number of relations, the performance of TiRGN improves significantly, which verifies the observation results mentioned in the entity prediction again.

4.3 Ablation Studies

To better understand the effectiveness of different model components that capture the corresponding historical characteristics, we conduct ablation studies. As shown in Table 4, the local recurrent encoder (le) has the greatest impact on performance, which indicates that adjacent historical facts are crucial for the prediction. The global history encoder (ge) has a consistent impact on all the datasets, which shows the necessity of avoiding omissions for prediction. Besides, a single global history encoder that directly uses frequency (ge+fre) as features performs worse than that without frequency, which is in line with our assumptions. Since periodic facts are special cases in the datasets, the periodic time decoder (td) does not greatly improve the performance, but it will not reduce the performance even for non-periodic facts. Therefore, these results further show that different historical characteristics are all helpful to the prediction.

4.4 Sensitivity Analysis

To explore the importance of global and local historical facts to the prediction results, we conduct a sensitivity analysis. α is a variable trade-off factor between global and local historical facts. As shown in Figure 3, neither ignoring the facts at adjacent timestamps nor ignoring the global repetitive facts can make effective prediction, which further demonstrates the necessity of combining local and global historical patterns in TiRGN. Besides, the results show that the performance is better when the value of α is from 0.2 to 0.5. This phenomenon shows that the facts of adjacent timestamps are more important than global repeated facts. By adjusting the value of α on the validation set, TiRGN can obtain the best trade-off between local and global historical facts.

5 Conclusion

In this paper, we propose a model named TiRGN for TKG reasoning, which learns the representations of entities and relations by capturing multiple characteristics of historical facts. We combine a local encoder that captures the structural dependency of local histories with a global encoder that captures the pattern of global repetitive histories, so as to conduct reasoning through a time-guided decoder with periodicity. The experimental results on six benchmark datasets demonstrate the significant advantages and effectiveness of TiRGN on temporal entity and relation predictions. In addition, ablation experiments show that these characteristics of historical facts play positive roles in TKG reasoning.

Acknowledgements

This work was supported by the Shanghai Municipal Project 20511100900, the NSFC Projects 62076096 and 62006078, Shanghai Knowledge Service Platform Project ZF1213, STCSM Project 22ZR1421700 and the Fundamental Research Funds for the Central Universities.