HIP Network: Historical Information Passing Network for Extrapolation Reasoning on Temporal Knowledge Graph

1 Introduction

Knowledge graphs (KGs) are multi-relational graphs, where nodes and various types of edges reflect entities and relations respectively. Each edge is presented as a triple of the form (subject, relation, object), e.g., (Obama, visit,China). Due to most of the KGs are far from complete, knowledge graph reasoning is proposed to infer missing facts [Dai et al., 2020]. And this problem has been extensively studied for static KGs. The common way is to embed entities and relations into the continuous vector spaces, and computing a score for each triple by applying a scoring function to these embeddings [Bordes et al., 2013; Yang et al., 2015; Trouillon et al., 2016]. However, facts may not always be true in the real world, which introduces the concept of the temporal knowledge graph (TKG). And each fact can be seen as a quadruple which takes the timestamp into consideration, i.e., (subject, relation, object, timestamp). Reasoning on TKGs is more complex because of its native dynamic nature.

∗Corresponding Author

To solve this problem, previous works attempt to extend the static KG embedding methods which score the likelihood of missing facts with timestamps [Jiang et al., 2016; Dasgupta et al., 2018; Garc´ıa-Dur´an et al., 2018; Goel et al., 2020]. But these methods neglect the structure during learning the representations. So methods like TeMP [Wu et al., 2020] are proposed recently. They focus on the evolving graph snapshots at multiple time steps for the dynamic representation and inference. However, they are not suitable for predicting future events, as the timestamps and the corresponding graphs are unknown. This problem is called extrapolation reasoning, which aims to predict new facts over future timestamps [Jin et al., 2020]. Extrapolation reasoning over TKGs is less studied but significant, since forecasting emerging events is useful for real-world applications.

Recently, RE-NET [Jin et al., 2020] and CyGNet [Zhu et al., 2021] are proposed to tackle the extrapolation reasoning problem. RE-NET uses RNNs [Cho et al., 2014] and RGCNbased aggregator [Schlichtkrull et al., 2018] to encode historical information for future predictions. And CyGNet proposes a copy-generation mechanism, which generates future events based on the historical distribution. However, there are still several challenges not fully addressed. As the patterns associated with the occurrence of events are sophisticated, how to disentangle and model these patterns is useful and challenging. As shown in Figure 1, we can see the temporal evolution of events (blue edges), as policy options are often considered before making a statement. And at the same time step, the co-occurring events in a neighborhood structure also have dependencies and interactions (dotted lines). Moreover, events may occur repeatedly along the history (red edges). These phenomenons highlight the importance of learning different patterns to access more reference information. Besides, due to the dynamic nature of TKGs, only a part of entities are active at each time step. And the relations between entity pairs also change. Previous methods usually update the embeddings as static KG methods or only concentrate on the representations of entities, which can not fully learn the timesensitive features for both entities and relations.

In this paper, we propose Historical Information Passing (HIP) network, a novel framework for extrapolation reasoning on TKGs. In the structural information passing part, our method uses CompGCN [Vashishth et al., 2020] to update the structural representations in a disentangled manner, which utilizes the relation embeddings and aggregates neighborhood information selectively. As for the temporal part, we generate the relation embeddings for specific entity pairs to capture the temporal evolution, and get the current embeddings for entities with the temporal self-attention mechanism. We also select object entities from history, to make reference to repetitive facts. Then HIP network adopts a multi-step reasoning algorithm with three score functions, to generate predictions in a sequential manner.

Our contributions are summarized as follows: 1)We propose a novel learning framework to handle the extrapolation reasoning problem on TKGs, which passes historical information from the temporal, structural and repetitive perspectives. 2)Our method specifically considers the updating of relation embeddings in the information passing process and proposes a multi-step reasoning algorithm with three scoring functions, which can infer future events sequentially. 3) The experimental results on five TKG datasets achieve stateof-the-art performance, and the significant improvements on Hits@1 prove the effectiveness of our method.

2 RelatedWork

Static KG embeddings. There are increasing interests in knowledge graph embedding (KGE) methods, which aim to embed entities (nodes) and relations (edges) into the continuous vector spaces, such as the translating models [Bordes et al., 2013; Wang et al., 2014] and the semantic matching models [Yang et al., 2015; Trouillon et al., 2016; Sun et al., 2019]. And some other models score facts based on the deep neural network with feed-forward or convolutional layers [Dettmers et al., 2018; Schlichtkrull et al., 2018; Wang et al., 2019; Vashishth et al., 2020]. There are also works that use external information, such as typing information [Zhang et al., 2018] and logic rules [He et al., 2020]. More details can be found in recent surveys [Dai et al., 2020]. However, these methods are not able to predict future events, as all entities and relations are treated as static.

Temporal KG reasoning. Recent works attempt to extend the static KG embeddings methods with temporal information. HyTE [Dasgupta et al., 2018] projects the entities and the relations onto timestamp specific hyperplanes. DESimpIE [Goel et al., 2020] defines a function that takes an entity and a timestamp as input, to generate time-specific representations. And there are many other methods consider the timestamp to do the temporal reasoning [Jiang et al., 2016; Garc´ıa-Dur´an et al., 2018]. Another line of works try to capture changes in neighborhood structure, which use temporal recurrence and graph neural network together [Wu et al., 2020; Sankar et al., 2020]. However, the above methods are not suitable for extrapolation reasoning on TKGs, because the structure and timestamp of the future graph are unknown. To solve this problem, RE-NET [Jin et al., 2020] and CyGNet [Zhu et al., 2021] are proposed, which are the most relevant methods to our work. RE-NET defines the joint probability distribution of all events in an autoregressive fashion. And CyGNet proposes a copy-generation mechanism, which makes predictions with the historical vocabulary.

3 Method

This section introduces the proposed model, named HIP network, for extrapolation reasoning on TKGs. We first define the task and notations, and give an overview of the model architecture. Then we detail the individual components in the following sections.

3.1 Task Definition andModel Architecture

Notations and task definition. A temporal knowledge graph (TKG) is composed of a sequence of time-stamped subgraphs, i.e., G = {G (1) , G (2) , ..., G (T) }, where G (t) = {E,R,Ot }. Here, E and R are known entities and relations across all time steps. And Ot is the events (edges) set at time t, each event is denoted as (s, r, o, t), where s, o ∈ E and r ∈ R. Our task is to predict missing events about an object query (s, r, ?, t + ∆t) (or a subject query (?, r, o, t + ∆t)), through using the historical information in {G (t′ ) }(t′ ≤ t), even if the events in time period ∆t are unknown.

Model architecture. As shown in Figure 2, our model has three main components, namely structural information passing (SIP) module, temporal information passing (TIP) module, and history forward (HF) module. In the SIP module, we consider the interactions of co-occurring events in the latest graph through the CompGCN-based aggregator. We divide the representations into multiple independent components, and update structural embeddings for the entities and relations according to the attention weight of each component. And in the TIP module, we focus on capturing the temporal evolution patterns of the events between specific entity pairs and integrating structural embeddings across time. We selectively incorporate historical representations for entities with a temporal self-attention layer, and use RNN to model evolution process of events to generate the temporal embeddings for relations. Finally, in the HF module, we need to predict what events are likely to occur. We adopt three scoring functions to evaluate the events from different perspectives. Then we generate the predicted graph according to the reasoning results and move to the next time step.

3.2 Structural Information PassingModule

To capture the neighborhood interactions, we update the structural embeddings of entities and relations based on the recently historical graph G (t-1) . However, due to the streaming nature of the temporal knowledge graph, when new neighbors come or disappear, we need to update the related parts of embeddings while retaining useful information. So our method uses CompGCN [Vashishth et al., 2020] in a disentangled manner to selectively pass structural information.

In this module, we aim to learn a disentangled embedding xs,t for entity s. Firstly, we project xs,t-1 onto K spaces as follows:

where Uk ∈ Rdin× din K is the parameter of channel k and K is the hyperparameter. Then we can obtain the node embeddings of K different components, i.e., hs = {hs,1, hs,2, ..., hs,k, ..., hs,K}.

Unlike most graph neural networks which embed only nodes in the graph, CompGCN uses embeddings of relations instead of matrices [Schlichtkrull et al., 2018; Vashishth et al., 2020]. So for each quadruple (s, r, o, t -1) ∈ G (t-1) , we also need to project the results of entity-relation composition operation onto the K spaces as follows:

where Vk ∈ Rdin× din K is the parameter of channel k. And φ(xr, xo) is the composition operation, such as subtraction, multiplication and circular-correlation. Then we can set K attention values, and the k-th attention value αk indicates how related the message φ(xr, xo) is to the k-th component hs,k. The attention weight αk is computed as:

where W ∈ R1× 2din K is a transformation matrix that can be trained. Then the update equation of the structural aggregator is given as:

Here, W l,k λ(r) ∈ R out K × in K is a relation-type parameter about the k-th component for the original, inverse and self-loop relations. Finally, We tile the K output embeddings xLs,k to obtain the structural representation xs,t of entity s at time t, where L is the last layer. And as the CompGCN can consider the embeddings of relations in the aggregating process, we can also get the refined embedding xr,t for relation r.

3.3 Temporal Information PassingModule

This module seeks to model the events evolution patterns between entity pairs and integrate information across time, to generate the temporal embeddings for entities and relations.

We assume that the embeddings from the SIP module sufficiently capture local structural information at each time step, which enables a disentangled modeling of structural and temporal information. For each entity s, the input is {xs,t-m+1, xs,t-m+2, ..., xs,t}, where m is the size of time window. We use a temporal self-attention layer to integrate the representations of entities in the temporal dimension, and the output embedding sequence for entity s is defined as {zs,t-m+1, zs,t-m+2, ..., zs,t}. We perform the scaled dotproduct form of attention [Vaswani et al., 2017] over the input embeddings at each time step, to generate the time-dependent embedding zs,t:

where X ∈ Rm×d and Z ∈ Rm×d are the input and output representations packed together across time. β ∈ Rm×m is the attention weight matrix obtained by the multiplicative attention function. And Wq ∈ Rd×d , Wk ∈ Rd×d and Wv ∈ Rd×d are the linear projection matrices corresponding to the queries, keys, and values. To ensure that future information is not exposed, we use the mask matrix M ∈ Rm×m as

In this way, when i >j, the attention weight βij → 0, which enables that only representations in the past are assigned nonzero weights.

As the SIP module is used to model the neighborhood interactions, the TIP module focuses more on fine-grained changes, i.e., the events (relations) that occur between specific entity pairs across the time steps. For each entity pair (s, o), we aim to predict what events may happen. So we use the sequence of relations between s and o, i.e., {r0 so , r1 so , ..., rn so , ..., rN so }(1 ≤ n ≤ N), where N is the number of the events that occur in the time window. And relations are sorted by occurrence time. We use a gated recurrent unit (GRU) [Cho et al., 2014] to get the relation transition representation for entity pair (s, o) as follows:

where xso,n ∈ Rd is the structural representation of relation rn so at corresponding time. Noting that an entity pair can have multiple events at the same time step, we simply follow the order in the raw data set. And we take the output of the last hidden layer as the temporal relation representation zso,t.

3.4 History ForwardModule

In this section, we introduce our scoring functions, which can evaluate an event from the structural, temporal and repetitive perspectives. And we proposed a multi-step inference algorithm, which can generate new graphs sequentially for future time step to handle the extrapolation reasoning problem.

The temporal scoring function is used to predict what events may occur. So we use the output from the TIP module as:

where Wt ∈ Rp×3d and p is the number of relation types. In this way, we can focus on the temporal evolution of events between specific entity pairs to predict the next event.

The structural scoring function evaluates events based on the structural representations, to consider the interactions between them at the same time step. And borrowing scoring function from static KGE methods, we use DistMult [Yang et al., 2015] to assign scores for the quadruples as follows:

where σ is the sigmoid function. And 〈·〉 denotes the trilinear dot product. Through the above two scoring functions,

Algorithm 1 Reasoning algorithm of HIP network

Input: Historical graph sequence {G (1) , G (2) , ..., G (t) }, Query set Squery with object entities missing at time t +∆t. Output: The reasoning results for each query in descending order of scores.

• 1: t′ = t +1.
• 2: while t′ < t +∆t do
• 3: Structural embeddings for entities and relations. ▷SIP
• 4: Temporal embeddings for entities. ▷TIP
• 5: for each (s, r, ?, t + ∆t) ∈ Squery do
• 6: Generate candidate entity pair set S t′ ep (s).
• 7: Generate candidate quadruple set S t′ q (s). ▷Eq. 10
• 8: Pick top-k quadruples in S t′ q (s) and add them to G (t′ ) . ▷Eq. 11 and 12
• 9: end for
• 10: Add G (t′ ) to the graph sequence and update the historical vocabulary.
• 11: end while
• 12: Update structural embeddings.
• 13: Replace the missing part with all entities for each query and compute scores for them. ▷Eq. 11 and 12

our method can consider the evolution patterns of events between entity pairs across time and neighborhood interactions at the same time step.

However, the existence of entities and events is timesensitive, which may lead to less information available for some entities in the time window. And based on the observation that many facts occur repeatedly along the history [Zhu et al., 2021], we can generate new events from the historical events selectively to solve this problem. In our method, we use historical vocabulary for each entity and relation. For a query (s, r, ?, t), we compute the repetitive history score as follows:

where Wh ∈ Rq×2d and q is the number of entities. es,t ∈ Rd and er,t ∈ Rd are representations of entities and relations to model the preference of the history, which are independent of time and structure. And v(s,r) t- is an q-dimensional multihot indicator vector for subject s and relation r, and position o is 1 represents that (s, r, o, t-) exists in graph G (t-) .

Now our goal is to handle the extrapolation reasoning problem with these scoring functions. And the reasoning process during testing is shown in Algorithm 1 and Figure 2. At each time step, the first thing is to update representations using the SIP and TIP module (line 3-4). But we compute the temporal embeddings for relations later. Then the reasoning for queries can be divided into three main steps (line 5-10).

Step 1: When given a query (s, r, ?, t + ∆t) and current time is t′ , we don't take all entities in E. We generate the candidate entity pair set S t′ ep (s) by searching for all entities that had events with s, to reduce noise and computed space.

Step 2: Our method focuses on temporal information in this step. We get the temporal embeddings for relations and use equation 10 to find the most likely event for each entity pair in S t′ ep (s). We put the event with the highest score of each entity pair into candidate quadruple set S t′ q (s). This step enables our approach to incorporate temporal evolution, which can avoid predicting the same result at every step.

Step 3: We use the sum of equation 11 and 12 to evaluate the plausibility of quadruples in S t′ q (s), which consider the preferences of current structure and history. We choose the top-k quadruples for each query, add them to the predicted graph G (t′ ) , and then move on to the next time step t′ + 1.

To answer the queries, we use the sum of equation 11 and 12 to assign scores for each query with the missing part completed at target time step t +∆t (line 13), and rank them in descending order.

3.5 Training Objective

As the query (s, r, ?, t) for an object entity can be seen as a multi-class classification problem, where each class corresponds to each object entity. And if we need to predict what events will happen between entity pairs, we can also regard this as a multi-classification problem for relation types. So the loss function in each time step can be defined as follows:

Here, I∗(·) are the scoring functions defined in the previous section, i.e., equation 10, 11 and 12.

4 Experiments

In this section, we evaluate our proposed framework, HIP network, on five public datasets.

4.1 Experimental Setup

Datasets. We use five TKG datasets, namely ICEWS14 [Trivedi et al., 2017], ICEWS18 [Boschee et al., 2015], GDELT [Leetaru and Schrodt, 2013], WIKI [Leblay and Chekol, 2018] and YAGO [Mahdisoltani et al., 2015]. ICEWS14, ICEWS18 and GDELT are event-based TKGs which record events with timestamps. WIKI and YAGO are subsets of Wikipedia history and YAGO3 respectively. And we preprocess these datasets for extrapolation reasoning task as prior works [Jin et al., 2020; Zhu et al., 2021]: we split them into three subsets by timestamps except ICEWS14, i.e., train(80%)/valid(10%)/test(10%). Thus, (timestamps of train) < (timestamps of valid) < (timestamps of test). More details about the five datasets can be found in Table 1.

Evaluation metrics. We evaluate our method on the link prediction task which evaluates whether the ground-truth entity is ranked ahead of other entities. We report the results of mean reciprocal rank (MRR), hits at 1/3/10 (Hits@1/3/10) in our experiments. And we remove corrupted entities as other baselines during evaluation which is called filtered setting.

Baselines. We mainly focus on comparing to the methods of static KGs and temporal graphs as prior works. Static KG learning methods include TransE [Bordes et al., 2013], DistMult [Yang et al., 2015], ComplEx [Trouillon et al., 2016], ConvE [Dettmers et al., 2018], RotatE [Sun et al., 2019], RGCN-DistMult [Schlichtkrull et al., 2018], and CompGCNDistMult [Vashishth et al., 2020]. And temporal reasoning methods include TTransE [Jiang et al., 2016], HyTE [Dasgupta et al., 2018], TA-DistMult [Garc´ıa-Dur´an et al., 2018], DySAT [Sankar et al., 2020], TeMP [Wu et al., 2020], RENET [Jin et al., 2020] and CyGNet [Zhu et al., 2021]. Since RE-NET and CyGNet are the most relevant methods for extrapolation reasoning, we will do more analysis on them.

4.2 Results on TKGs

In this task, we finetune the hyperparameters according to the MRR performance on each validation set. Since ICEWS14 is not provided with a validation set, we use the same settings in ICEWS18. And to be consistent with the baselines, most hyperparameters are the same on all datasets. We use the ADAM optimizer with a learning rate of 0.001 to minimize the global loss. The embedding dimension is 200. The dropout rate is 0.5. The batch size is 1024. And the time window size is set to 10. Additionally, in our SIP module, we use multiplication as the composition operation and adopt 4 channels. For the static KG methods, we simply remove all timestamps in datasets.

As Table 2 shows, our HIP network outperforms all the baselines. All static methods perform worse than our method since they do not consider temporal factors. And TTransE, HyTE, TA-DistMult and DySAT don't even work as well as some static methods. RE-NET, TeMP, CyGNet and our method outperform other methods by a large margin. TeMP is not primarily proposed to solve the extrapolation reasoning problem, but it's also trained along history, which proves that modeling historical evolution patterns can better deal with this problem. And compared to the best baseline CyGNet, our improvements on MRR and Hits@1 are more significant than Hits@10. This may be because CyGNet generates predictions based on the historical distribution, which can narrow the scope of predictions. And some entities never appear in the training set, which also makes it difficult to improve Hits@10. The improvements on Hits@1 and MRR fully demonstrate that our method is able to utilize historical information more effectively, to predict exactly what is going to happen.

4.3 Ablation Study

We conduct ablation experiments on the WIKI and ICEWS14 datasets. Firstly, we only use the SIP module and score the events through equation 11. Then we consider historical vocabulary, i.e., equation 12. In the third setting, we combine historical vocabulary with structural representations to measure the plausibility of events. Finally, we evaluate our method with all components according to Algorithm 1.

As shown in Table 3, under the first setting, our method still performs better than most static KGE models, especially CompGCN. This proves the usefulness of our SIP module which updates representations in a disentangled manner, as changes often occur in the part of the neighborhood structure on TKGs. And in the second setting, scoring with equation 12, our model can achieve better results, which demonstrates the importance of selectively incorporating historical information for each query. When we combine the two settings together, the result on all metrics still improves. As we consider the evolution patterns about events between entity pairs, HIP network achieves the best results by using the multi-step reasoning process. In particular, the improvements in the purely event-based dataset (ICEWS14) are more significant, this may be because events in the ICEWS14 have more evolution patterns (the time gap in ICEWS14 is only 24 hours), which proves the importance of considering the temporal evolution of events.

4.4 Sensitivity Analysis

In this section, we investigate the influence of hyperparameters on YAGO.

Number of channels in the structural aggregator. To update the related parts of embeddings in the aggregated process, we project the embeddings and the results of composition operation onto K subspaces. We consider the value of K from 1 to 10. As Figure 3(a) shows, our model achieves the best result when K is set to 4. And our model is sensitive to K especially when K is larger than 4. Since the weight of each subspace is calculated in a similar way to the multi-head attention mechanism, large K results in a smaller subspace dimension. So we need to choose K more carefully according to the embedding dimension.

Length of history in the temporal part. The input of the TIP module is the information in the time window. In detail, we take the sequence of events up to m between each entity pair. Note that there may be multiple events between each entity pair at the same time step, we take the m events that have recently occurred in the order of the original dataset. And we simply remove the above events that do not occur in the time window. So m is the limit on the number and scope of events. And in the temporal self-attention layer, we only consider the embeddings within the time window. Figure 3(b) shows that the longer the history is considered, the higher the Hits@1. When the history length is around 8, Hits@1 starts to be relatively stable. And a large time window may result in a long sequence of events in RNN. Therefore, to simplify the computation and save time, we don't need to set m too large.

5 Conclusions

In this paper, we propose HIP network to solve the extrapolation reasoning problem on TKGs. We pass historical information from the temporal, structural and repetitive perspectives to make future predictions. And the proposed HIP network not only considers the important role of relations in the information passing process, but also evaluates the plausibility of an event from above perspectives, which can effectively model the evolution patterns, neighborhood interactions, and historical repetition. Experimental results show that HIP network achieves improvements over state-of-the-art baselines.

Acknowledgments

This work was supported by the National Key R&D Program with No.2016QY03D0503,2016YFB081304, and Strategic Priority Research Program of Chinese Academy of Sciences, Grant No.XDC02040400.