Temporal Knowledge Graph Reasoning Based on Evolutional Representation Learning

The structural dependencies among concurrent facts capture the associations among the entities through facts and the associations among relations through the shared entities. Since each KG is a multi-relational graph and GCN is a powerful model for the graph-structured data (Schlichtkrull et al., 2018; Shang et al., 2019; Ye et al., 2019; Vashishth et al., 2019), an $\omega$-layer relation-aware GCN is used to model the structural dependencies. More specifically, for a KG at timestamp $t$, an object entity $o$ at layer $l\in[0,\omega-1]$ gets information from its subject entities under a message-passing framework with embeddings of the relations at layer $l$ considered and obtains its embedding at the next $l+1$ layer, i.e.,

where $\vec{h}_{o,t}^{l}$, $\vec{h}_{s,t}^{l}$, $\vec{r}_{t}$ denote the $l^{th}$ layer embeddings of entities $o,s$ and relation $r$ at timestamp $t$, respectively; $\mathbf{W}_{1}^{l}$, $\mathbf{W}_{2}^{l}$ are the parameters for aggregating features and self-loop in the $l^{th}$ layer; $\vec{h}_{s,t}^{l}+\vec{r}_{t}$ implies the translational property between the subject entity and the corresponding object entity via the relation $r$; $c_{o}$ is a normalization constant, equal to the in-degree of entity $o$; $f(\cdot)$ is the RReLU activation function (Xu et al., 2015). Note that, for those entities that are not involved in any fact, only a self-loop operation with the extra parameters $\mathbf{W}_{3}^{l}$ is carried out. Actually, the relation-aware GCN gets the entity embeddings according to the facts occurred among them at each timestamp and the self-loop operation can be considered as the self-evolution of the entities.

For an entity $o$, the sequential patterns contained in its historical facts reflect its behavioral trends and preferences. To cover the historical facts as many as possible, the model needs to take all its temporally adjacent facts into consideration. As the output of the final layer of the relation-aware GCN, $\vec{h}_{o,t-1}^{\omega}$, already models the structure of the adjacent facts at timestamp $t-1$, one straightforward and effective approach to contain the information of the temporally adjacent facts is to use the output entity embedding matrix at $t-1$, $\mathbf{H}_{t-1}$, as the input of the relation-aware GCN at $t$, $\mathbf{H}^{0}_{t}$. Therefore, the potential sequential patterns are modeled by stacking the $\omega$-layer relation-aware GCN. However, although the adjacent KGs are different, the over-smoothing problem (Kipf and Welling, 2016), i.e., the embeddings of entities converge to the same values, also exists when the repetitive relations occur between the same entity pairs at adjacent timestamps (Zhu et al., 2020). And when the historical KG sequence gets longer, the large number of stacked layers of GCN may cause the vanishing gradient problem. Thus, following (Li et al., 2019), we apply a time gate recurrent component to alleviate these problems. In this way, the entity embedding matrix $\mathbf{H}_{t}$ is determined by two parts, namely, the output $\mathbf{H}^{\omega}_{t}$ of the final layer of the relation-aware GCN at timestamp $t$ and $\mathbf{H}_{t-1}$ from the previous timestamp. Formally,

where $\otimes$ denotes the dot product operation. The time gate $\mathbf{U}_{t}\in\mathbb{R}^{d\times d}$ conducts nonlinear transformation as:

where $\sigma(\cdot)$ is the sigmoid function and $\mathbf{W}_{4}\in\mathbb{R}^{d\times d}$ is the weight matrix of the time gate. Besides, the sequential pattern of relations captures the information of entities involved in the corresponding facts. Thus, the embeddings of a relation $\vec{r}_{t}$ at timestamp $t$ are influenced by the evolutional embeddings of $r$-related entities $\mathcal{V}_{r,t}=\{i|(i,r,o,t)\ or\ (s,r,i,t)\in\mathcal{E}_{t}\,\}$ at timestamp $t$ and its own embedding at timestamp $t-1$. Thus, a GRU component is adopted to model the sequential pattern of relations.

By applying mean pooling operation over the embedding matrix of $r$-related entities at timestamp $t-1$, $\mathbf{H}_{t-1,\mathcal{V}_{r,t}}$, the input of the GRU at timestamp $t$ for relation $r$, is

where $\vec{r}$ is the embedding of relation $r$ in $\mathbf{R}$ and $[;]$ denotes the vector concatenation operation. For the relation that does not have corresponding facts occurred at timestamp $t$, $\vec{r}^{\prime}_{t}=\vec{0}$. Then we update the relation embedding matrix $\mathbf{R}_{t-1}$ to $\mathbf{R}_{t}$ via the GRU,

where $\mathbf{R}^{\prime}_{t}\in\mathbb{R}^{|\mathcal{R}|\times d}$ consists of $\vec{r}^{\prime}_{t}$ of all the relations. Note that, the L2-norm of each line of $\mathbf{H}_{t}$ and $\mathbf{R}_{t}$ is constrained to $1$.

Besides the information contained in the historical KG sequence, some static properties of entities, which form a static graph, can be seen as the background knowledge of the TKG and is helpful for the model to learn more accurate evolutional representations of entities. Thus we incorporate the static graph into the modeling of the evolutional representations. We construct the static graphs of the three TKGs from ICEWS based on the entity property information originally contained in the name strings of entities. Most name strings of entities therein are in the form of ‘entity types (country)’. Take an entity named ‘Police (Australia)’ in ICEWS18 (Jin et al., 2019) for example, we add relation ‘isA’ from this entity to the property entity ‘Police’ and relation ‘country’ to the property entity ‘Australia’. The bottom left of figure 2 shows an example of a static graph. Since the static graph is a multi-relational graph and R-GCN (Schlichtkrull et al., 2018) can model the multi-relational graph without any more extra embeddings for relations. Thus, we adopt a 1-layer R-GCN (Schlichtkrull et al., 2018) without self-loop to get the static embeddings of entities in the TKG. Then, the update rule for the static graph is defined as follows:

where $\vec{h}^{s}_{i}$ and $\vec{h}^{\prime s}_{j}$ are the $i^{th}$ and $j^{th}$ lines of $\mathbf{H}^{s}$ and $\mathbf{H^{\prime}}^{s}$, which are the output and randomly initialized input embedding matrices, respectively; $\mathbf{W}_{r^{s}}\in\mathbb{R}^{d\times d}$ is the relation matrix of $r^{s}$ in R-GCN; $\Upsilon(\cdot)$ is ReLU function; $c_{i}$ is a normalization constant equal to the number of entities connected with entity $i$. Note that, $||\vec{h}^{s}_{i}||_{2}=1$.

To reflect the static properties in the learned sequence of entity embedding matrices $\mathbf{H}_{t-m}$, $\mathbf{H}_{t-m+1}$,…$\mathbf{H}_{t}$, we confine the angle between the evolutional embedding and the static embedding of the same entity not to exceed a timestamp related threshold. It increases over time since the permitted variable range of the evolutional embeddings of entities continuously extends over time with more and more facts occurring. Thus, it is defined as

where $\gamma$ denotes the ascending pace of the angle and $x\in[0,1,..,m]$. We set the max angle of the two embeddings of an entity to $90^{\circ}$.

Then, the cosine value of the angle between the two embeddings of entity $i$, denoted as $cos(\vec{h}^{s}_{i},\vec{h}_{t-m+x,i})$, should be more than $cos\theta_{x}$.

Thus, the loss of the static graph constraint component at timestamp $t$ can be defined as below:

The loss of the static graph constraint component is $L^{st}=\sum_{x=0}^{m}L^{st}_{x}$.

There are six typical TKGs commonly used in previous works, namely, ICEWS18 (Jin et al., 2020), ICEWS14 (García-Durán et al., 2018), ICEWS05-15 (García-Durán et al., 2018), WIKI (Leblay and Chekol, 2018), YAGO (Mahdisoltani et al., 2014) and GDELT (Leetaru and Schrodt, 2013). The first three datasets are from the Integrated Crisis Early Warning System (Boschee et al., 2015) (ICEWS). GDELT (Jin et al., 2020) is from the Global Database of Events, Language, and Tone  (Leetaru and Schrodt, 2013). We evaluate RE-GCN on all these datasets. We divide ICEWS14 and ICEWS05-15 into training, validation, and test sets, with a proportion of 80%, 10% and 10% by timestamps following  (Jin et al., 2020). The details of the datasets are presented in Table 2. The time interval represents time granularity between temporally adjacent facts.

In the experiments, $MRR$ and $Hits@\{1\\ ,3,10\}$ are employed as the metrics for entity prediction and relation prediction. For the entity prediction task on WIKI and YAGO, we only report the $MRR$ and $Hits@3$ results because the results of $Hits@1$ were not reported by the prior work RE-NET (Jin et al., 2020).

As mentioned in  (Han et al., 2020b; Ding et al., 2021; Jain et al., 2020), the filtered setting used in (Bordes et al., 2013; Jin et al., 2020; Zhu et al., 2020), which removes all the valid facts that appear in the training, validation, or test sets from the ranking list of corrupted facts, is not suitable for temporal reasoning tasks. Take a typical query $(s,r,?,t_{1})$ with answer $o_{1}$ in the test set for example, and assume there is another fact $(s,r,o_{2},t_{2})$. Under this filtered setting, $o_{2}$ will be wrongly considered a correct answer and thus removed from the ranking list of candidate answers. However, $o_{2}$ is incorrect for the given query, as $(s,r,o_{2})$ occurs at timestamp $t_{2}$ instead of $t_{1}$. Thus, the filtered setting may probably get incorrect higher ranking scores. Without loss of generality, only the experimental results under the raw setting are reported.

The RE-GCN model is compared with two categories of models: static KG reasoning models and TKG reasoning models. DistMult (Yang et al., 2014), ComplEx (Trouillon et al., 2016), R-GCN (Schlichtkrull et al., 2018), ConvE (Dettmers et al., 2018), ConvTransE (Shang et al., 2019), RotatE (Sun et al., 2018) are selected as static models. HyTE (Dasgupta et al., 2018), TTransE (Leblay and Chekol, 2018) and TA-DistMult (García-Durán et al., 2018) are selected as the temporal models under the interpolation setting. For temporal models under the extrapolation setting, CyGNet (Zhu et al., 2020) and RE-NET (Jin et al., 2020) are compared. For Know-evolve and DyRep, RE-NET extends them to temporal reasoning task but does not release their codes. Thus, we only report the results in their papers. Besides, GCRN (Seo et al., 2018) is the model for homogeneous graphs and RE-NET extends it to R-GCRN by replacing GCN with R-GCN.

For the evolution unit, the embedding dimension $d$ is set to 200; the number of layers $\omega$ of the relation-aware GCN is set to 1 for YAGO and 2 for the other datasets; the dropout rate is set to 0.2 for each layer of the relation-aware GCN. We perform grid search on the length of the historical graph sequence (1, 15) and the ascending pace of the angle $\gamma$ ($1^{\circ}$-$20^{\circ}$) on the validation sets. The optimal lengths of history $m$ for ICEWS18, ICEWS14, ICEWS05-15, WIKI, YAGO, and GDELT are 6, 3, 10, 2, 1, 1, respectively. $\gamma$ is experimentally set to $10^{\circ}$. Adam (Kingma and Ba, 2014) is adopted for parameter learning with the learning rate 0.001. As for the R-GCN used in the static graph constraint component, we set the block dimension to $2\times 2$ and the dropout rate for each layer to 0.2. For ConvTransE, the number of kernels is set to 50, the kernel size is set to $2\times 3$ and the dropout rate is set to $0.2$. For the joint learning of the entity prediction task and the relation prediction task, $\lambda_{1}$ and $\lambda_{2}$ are experimentally set to $0.7$ and $0.3$, respectively. The statistics of the static graphs are presented in Table 2. We only report the results without the static graph constraint on WIKI, YAGO and GDELT because the static information is missing in these datasets. To conduct the multi-step inference (Jin et al., 2020) in the validation set and the test set, we evaluate the performance of RE-GCN with the evolutional embeddings of entities and relations at the final timestamp of the training set as the input of score functions following (Zhu et al., 2020). Besides, we also report the results of the models with ground truth history given during multi-step inference on the test set, namely, w. GT. All experiments are carried out on Tesla V100. Codes are avaliable at https://github.com/Lee-zix/RE-GCN.

The experimental results on the entity prediction task are presented in Tables 3 and 4. RE-GCN consistently outperforms the baselines on the three ICEWS datasets, WIKI and YAGO. The results convincingly verify its effectiveness. Specifically, RE-GCN significantly outperforms the static models (i.e., those in the first blocks of Tables 3 and  4) because RE-GCN considers the sequential patterns across timestamps. RE-GCN performs better than the temporal models for the interpolation setting (i.e., those in the second blocks of Tables 3 and  4) because RE-GCN additionally captures temporally sequential patterns and static properties of entities. It can thus obtain more accurate evolutional representations for the unobserved timestamps. Especially, RE-GCN outperforms the temporal models for the extrapolation setting (i.e., those in the third blocks of Tables 3 and  4). It outperforms RGCRN because the newly designed graph convolution operation and the two recurrent components in the evolution unit learn better evolutional embeddings and the static graph helps learn better evolutional embeddings of entities. CyGNet and RE-NET’s good performance verifies the importance of the repetitive patterns and 1-hop neighbors to the entity prediction task. Despite this, it is not surprising that RE-GCN performs better than CyGNet because there is much useful information except the repetitive patterns in the history. RE-GCN also performs better than RE-NET, which neglects the structural dependencies within a KG and the static properties of entities. By capturing more comprehensive structural dependencies and sequential patterns, RE-GCN outperforms RE-NET on most datasets. From the last two lines in Tables 3 and  4, it can be observed that the performance gap between the last two lines becomes large when the time interval between two adjacent timestamps of the datasets becomes large. For the two datasets, WIKI and YAGO, with the time interval as one year, the model’s performance drops rapidly without knowing the ground truth history. This is because the evolutional representations become inaccurate when the time interval is large during the multi-step inference.

Note that RE-GCN even achieves the improvements of 8.97/11.46% in MRR, 10.60/12.91% in Hits@3 and 12.61/14.01% in Hits@10 over the best baseline on WIKI and YAGO. For the two datasets, there are more structural dependencies within the KG at each timestamp because the time interval is much large than the other datasets. Therefore, only modeling repetitive patterns or one-hop neighbors will loses a lot of structural dependencies and sequential patterns. The results demonstrate that RE-GCN is more capable of modeling these datasets containing complex structural dependencies among concurrent facts.

The experimental results of static models and temporal models are similarly poor on GDELT, as compared with those of the other five datasets. We further analyze the GDELT dataset and find that many of its entities are abstract concepts that do not indicate specific entities (e.g., POLICE and GOVERNMENT). Among the top 50 frequent entities, 28 are abstract concepts and 43.72% corresponding facts involve abstract concepts. Those abstract concepts make the temporal reasoning for some entities under the raw setting almost impossible, since we cannot predict a government’s activities without knowing which country it belongs to. Thus, all the models can only predict partial facts in the GDELT dataset and get similar results. Besides, the noise produced by the abstract concepts influences the evolutional representations of other entities as RE-GCN models the KG sequence as a whole, which makes the results of RE-GCN a little worse than RE-NET.

Since some models are not designed for the relation prediction task and for space limitation, we select the typical ones from the baselines and present the experimental results in terms of only MRR in Table 5. In more detail, we select ConvE (Dettmers et al., 2018), ConvTransE (Shang et al., 2019) from the static models, as well as RGCRN (Seo et al., 2018) from the temporal models. RE-NET and CyGNet are not adopted, as they cannot be applied to the relation prediction task directly. It can observe that RE-GCN performs better than all the baselines. The outperformance of RE-GCN demonstrates that our evolution unit can obtain more accurate evolutional representations by modeling the history comprehensively.

The performance gap between RE-GCN and other baselines on the relation prediction task is smaller than the entity prediction task. It is because the number of relations is much less than the number of entities. Fewer candidates make the relation prediction task much easier than the entity prediction task. The performance on WIKI and YAGO is much better than the other datasets because the numbers of relations in the two datasets are only 24 and 10, respectively. The results on the GDELT dataset for the static models and the temporal models are also similarly poor, which verifies our observations mentioned in Section 5.2.1 again.

To demonstrate how the evolution unit contributes to the final results of RE-GCN, we conduct experiments of only using the ConvTransE score function with the randomly initialized learnable embeddings. The results denoted as -EE w. GT, are demonstrated in Tables 6 and  7. It can be observed that removing the evolution unit has a great impact on the results for all the datasets except GDELT, suggesting that modeling the historical information is vital for all the datasets. For GDELT, only using the ConvTransE can get good results. It also matches our observations mentioned in Section 5.2.1.

To further verify the effectiveness of our evolution unit under different score functions, we replace the ConvTransE in RE-GCN with a simple one layer Fully Connected Network (FCN), denoted as +FCN w. GT. The experimental results are presented in Tables 6 and  7. It can be observed that the results are worse than RE-GCN w. GT on most datasets. It matches the observation in  (Ye et al., 2019), the convolutional score functions are more suitable for the GCN. However, even with a simple score function, +FCN w. GT still shows strong performance on both entity and relation predictions.

The results denoted as –st w. GT in Tables 6 and 7 demonstrate the performance of RE-GCN without the static graph constraint component. It can be seen that –st w. GT performs consistently worse than RE-GCN w. GT in ICEWS datasets, which justifies the necessity of the static graph constraint component to the RE-GCN model. The static information can be seen as the background knowledge of the TKG. The entity type and location information in the static graph enriches the evolutional representations of entities and helps obtain better initial evolutional representations of entities. Note that, even without the static information, –st w. GT still outperforms the state-of-art RE-NET w. GT and RGCRN w. GT.

–tg w. GT in Tables 6 and  7 denotes a variant of RE-GCN directly using the evolutional representations at the last timestamp as the input of the evolution unit at the current timestamp without the time gate. It can observe that the performance of –tg w. GT decreases rapidly when the historical KG sequence gets longer, as compared to RE-GCN w. GT, which sufficiently indicates the necessity of the time gate recurrent component. Actually, the time gate recurrent component helps RE-GCN capture the sequence patterns by a deep-stacked GCN, which usually faces the over-smoothing and vanishing gradient problems when the number of the layers becomes large.