Temporal Knowledge Graph Reasoning Triggered by Memories

Static knowledge graphs ignore the sequence of events. Recent researches in knowledge reasoning based on KGs (KGs reasoning) focus on knowledge representation learning, namely, mapping entities and relations into low-dimensional vectors. TransE [15] proposed to embed entities and relationships of multi-relational data into low-dimensional vector spaces. TransH [16] took relations as a hyperplane, which aimed to incorporate mapping properties between relations. TransR [17] built entity and relation representations in separate spaces and then learn embeddings by projecting entities from entity space to corresponding relation space. ComplEx [18] introduced complex value embedding, which can handle various binary relationships, including symmetric and antisymmetric relations. RotatE [19] realized the KG embedding by relational rotation in complex space and defined each relation as a rotation from the source entity to the target entity in the complex vector space. DistMult [20] proved that generalized bilinear formulation achieved excellent link prediction performance. Researchers also adopted learned relation representations to learn logical rules. SimplE [21] proposed a simple enhancement of Canonical Polyadic (CP) decomposition to learn embeddings of entities dependently and the complexity grows linearly with the size of embeddings. ConvE [22] used neural convolution to build the interactions between entities and relations after mapping entities and relations into variables. RSN [23] was proposed to exploit long-term relational dependencies in knowledge graphs, which employed a skipping mechanism to bridge the gaps between entities. The designed recurrent skip mechanism helped distinguish relations and entities.

Moreover, researchers [24] applied the transformer into the KGs completion and named their framework as knowledge graph bidirectional encoder representations from the transformer (KG-BERT). KG-BERT treated facts in KGs as a textual sequence. The structure-aware convolutional network (SACN) [25] combined the benefit of the graph convolution network (GCN) [26] and ConvE, which consisted of a weighted graph convolutional network as an encoder and a convolutional network called Conv-TransE as a decoder.

Temporal knowledge graphs gradually attract the attention of researchers for the structured knowledge existing within a specific period and the evolution of facts following the time order.

Researchers of [1] considered the temporal knowledge graphs by annotating relations between entities within time intervals. HyTE [27] projected entities and relations into a hyperplane that associated with the corresponding timestamp. [28] introduced a temporal order constraint based on a manifold regularization term considering the happen time of facts. Han et.al [29] introduced the Hawkes process into the TKG reasoning task. Sankalp Garg et.al [30] proposed the temporal attribute prediction, in which each entity extra contained the attribute description. RE-Net [7] was an autoregressive architecture for predicting future missing facts. History facts that share the same subject entity with the predictive event are selected as past knowledge. Tao et.al [6] proposed a TKGs reasoning method based on the reinforcement learning technique. Researchers trained a time-aware agent to navigate the graph conditioned on known facts to find predictive routes. CluSTeR [31] predicted future missing facts in a two-stage manner, Clue Searching and Temporal Reasoning. The clue searching stage induced clues from historical facts based on reinforcement learning. The temporal reasoning stage deduced answers from clues using a graph convolution network. RE-GCN [9] learned the evolutional representations of entities and relations at each timestamp recurrently. All history facts are adopted to construct a knowledge graph to learn structural dependencies.

Compared with these temporal reasoning methods, this work also combines deep memories and transient memories by constructing a joint prediction network for solving the time dependence of the reasoning process under the supervision of the dissolution learning constraint.

We first introduce TREN since the final outputs of it are used in TLN.

TREN can be regarded as a sequence of evolution units. Although recent historical facts contribute more than earlier historical facts when reasoning future events, long-term memories still play an indispensable role. To extract as much historical information as possible, TREN incorporates all facts that occurred in history.

TLN consists of a structural encoder Res-GCN and a time encoder that selects entity attribute representations - the control gating unit.

Previous works [33, 34] show that KG reasoning tasks with the convolutional neural network as the decoder displays excellent performance. Thus, we choose the ConvTransE as the network decoder following [25], which contains several convolution layers, and a fully connected layer. For reasoning missing entity facts ($t_{p}>t_{n}$), both entity attribute representations ($\mathbf{H}_{t_{n}+1}^{\text{TREN}},\mathbf{H}_{t_{n}+1}^{\text{TLN}}$) extracted by the MTDM and static relation representations $\mathbf{R}$ are used as decoder inputs. Thus, the entity prediction probability is defined as,

where $\mathbf{H}_{t_{n}+1}^{\text{TREN}}$, $\mathbf{H}_{t_{n}+1}^{\text{TLN}}$ are sets of $\mathbf{H}_{s,t_{n}+1}^{\text{TREN}}$, $\mathbf{H}_{s,t_{n}+1}^{\text{TLN}}$, $<$,$>$ denotes the matrix concatenate, $\mathbf{P}_{o,t_{p}}$ is the entity prediction vector decoded by the ConvTransE, $\otimes$ denotes the matrix multiplication, $\dagger$ means matrix transpose, and $\sigma(\cdot)$ is the sigmoid function. Since the static relation representations significantly affect the entity reasoning performance, we construct the relation prediction probability for better extracting relation representations, which is expressed as,

Based on pediction probabilities $\vec{p}_{t_{p}}(o),\vec{p}_{t_{p}}(r)$, the loss function for entity prediction is defined as,

where ${(\mathrm{s}_{t_{p}},\mathrm{r}_{t_{p}},\mathrm{o}_{t_{p}})\in\mathcal{F}_{t_{p}}}$. We experimentally assign the value for the hyper-parameter $\lambda_{1}$.

To reflect the deep memories in learned entity attribute representations, following [9], we constraint the difference between the deep memory representations $\mathbf{H}_{<t_{1}}$ and the entity attribute representations $\mathbf{H}_{t}^{\text{TREN}}$ of the same entity to not exceed the threshold $\theta_{t}$. Additionally, the embedding threshold will increase over time since recent historical facts gradually modify the deep memory.

where $\theta_{t}$ = $\gamma\cdot(t-t_{1}+1)$, $\gamma$ represents the angle stride.

We have experimentally found that transient memories greatly affect long-term memory-dependent decisions. Therefore, we introduce a 0-1 constraint on gating parameters $\mathrm{U}_{t}$.

where $\bar{\mathrm{U}_{t}}$ denotes the average value of gating parameters.

By observing training data in TKGs reasoning tasks, we found that most relations between two observed entities do not change, while only a few new relations have formatted and dissolved since the last observation. Thus, we construct dissolved events for each prediction timestamp. Specifically, for predicted facts ($s$, $r$, ?, $t_{p}$), $t_{p}>t_{n}$, we collect historical facts $adv=(s,r,?)$ within a temporal interval [$t_{1},t_{n}$], $adv\in\mathcal{F}_{t_{1}\thicksim t_{n}}$, $adv\not\in\mathcal{F}_{t_{p}}$. Then we assign temporal information for these newly constructed facts, {$adv$, $t_{p}$}$\in\mathcal{F}_{adv}$.

Based on above mentioned loss functions, the final loss constraint is defined as:

$\lambda_{1-4}$ are hyper-parameters that distinguish the importance of different tasks. $\lambda_{4}$ = 0 by default. We ablatively study the impact of dissolution learning constraint $\mathcal{L}_{adv}$ on the reasoning performance in Section V-D3. The process for entity prediction task based on MTDM is highlighted in Algorithm 1.

We evaluate the performance of the MTDM on three standard datasets and compare it with recent temporal reasoning models. Code to reproduce our experimental results will be publicly available in https://github.com/Dlut-lab-zmn/MTDM.

We evaluate the model performance on the time-aware filtered matrix. Table II summarizes entity prediction performance comparison on three benchmark datasets, where $w.eval$ denotes utilizing the evaluation data and training data to train the model. By default, only training data is used in the training process. The training data and evaluation data are adopted as historical facts in the reasoning process. Specificlly, given triples with timestamps in [$t_{I}$, $t_{T}$] as the training set, [$t_{T}$, $t_{E}$] as the evaluation set, triples with timestamps in [$t_{I}$, $t_{E}$] as historical evaluation facts, predicting triples with the timestamp $t_{p}>t_{E}$.

Results in Table II demonstrate that MTDM outperforms all interpolation baselines on three standard datasets, which illustrates the effectiveness of utilizing evolutionary representation learning on entity predictions. Additionally, MTDM achieves state-of-the-art performance than all extrapolation baselines. It is worth noting that only xERTE, RE-GCN, MTDM can tackle unseen entities by dynamically updating new entity representations based on temporal message aggregation, namely, incorporating evaluation data as historical facts to predict future missing entities but not using the evaluation data to train the model. Therefore, we also provide the prediction performance with or without utilizing evaluation data when training the model for methods CyGNet, RE-Net. As we can see, MTDM performs better than CyGNet and RE-Net even these methods combine the evaluation data in the training process. For instance, the MRR of MTDM is 5.1% and 7.7% higher than RE-Net and CyGNet under the YAGO dataset, 4.6% and 5.6% higher than RE-Net and CyGNet under the WIKI dataset ($w.eval$). For clarifying the impact of history length on the prediction performance, three history lengths are set for RE-GCN [9], 1, 4, 10. We observe that RE-GCN reaches optimal performance for YAGO, WIKI, and ICEWS14 when we set the history length to 1, 4, and 10. In comparison, MTDM leverages deep memories, long-short-term memories, and transient memories, which alleviates the history dependence on history length. Thus, MTDM sets the fixed history length for convenience, 10 for TREN, and 1 for TLN. Even so, MTDM performs better prediction performance than the best RE-GCN, i.e. the MRR of MTDM achieves 3.8% performance improvement than RE-GCN on the YAGO dataset, 1.6% improvement on WIKI, and 3.4% improvement on ICEWS14.

We can draw the following conclusions through the experimental results. For WIKI and YAGO, short-term memories perform better than long-term memories in predicting future missing entities, i.e. the MRR of RE-GCN under the latest knowledge graph as historical facts achieve 74.69% prediction accuracy, 6.1% performance improvement compared with lengths of history to 10 on the YAGO dataset. For ICEWS14, short-term memories combined with long-term memories perform better than only using short-term memories. Therefore, MTDM combines the entity attribute representations in TLN selected by the gating unit C-Gate, and the entity attribute representations in TREN that neglect invalid long-term memories for reasoning all standard benchmarks.

In addition, Table II also provides the comparative experiment results of MTDM, RE-GCN, xERTE with the ground truth events (GT) as historical evaluation facts, where MTDM realizes a 5.1% MRR improvement than RE-GCN for the YAGO dataset, 2.3% improvement for WIKI, and 2.8% improvement for ICEWS14. Specifically, GT means given triples with timestamps in [$t_{I}$, $t_{T}$] as the training set, triples with timestamps in [$t_{I}$, $t_{d}$] as historical evaluation facts, and predicting triples with the timestamp $t_{d+1}$ ($t_{d}>t_{E}$). Evaluation with GT as historical evaluation facts can better illustrate the transferability of models, namely, incorporating the newest information for predicting the following possible events. In summary, the MTDM successfully alleviates the temporal dependence problem and outperforms previous works in the temporal reasoning task.

To evaluate the efficiency of MTDM, we compare MTDM with the newest TKG reasoning methods, including RE-GCN, RE-Net, and CyGNet, in terms of total training time under the same setting. Comparison results are shown in Fig. 3. We observe that RE-Net takes amounts of time consumption than MTDM, RE-GCN. That is because RE-Net needs to extract temporally adjacent history facts for each given entity as a sequential to predict future events, while MTDM and RE-GCN utilize the evolutionary representation learning. Meanwhile, MTDM performs better than CyGNet and RE-GCN in time cost, about 4.1 times faster than CyGNet, and 2.9 times faster than RE-GCN. On the one hand, MTDM only contains a structural encoder, a time encoder with a reset gating unit, and the deep memory learning module that takes less computational time, which means MTDM trains fast in a single epoch. On the other hand, the memory combination operation accelerates the model convergence speed. For example, MTDM reaches the optimal performance in the 6th and 8th epoch for YAGO and ICEWS14, while the best available work converges in the 24th and 25th epoch.

This subsection investigates the impact of variations in MTDM on reasoning performance, including memory-related variants, model structure-related variants, and data source-related variants. For ablation studies towards various memories, we conduct three sub-MTDM, without the deep memory - w.o DM, without the time-aware recurrent evolutional network - w.o TREN, and without the transient learning network - w.o TLN. Additionally, we experimentally analyze the impact of reset gating units - w.o R$\_$Gate, different structural encoders, different time encoders, and various recurrent modes towards the model prediction. Finally, we conduct researches towards the event dissolution constraint, w. ED, namely, adding dissolved events as negative samples into the training data. Meanwhile, we experimentally analyze the influence of various hyper-parameters on MTDM.

We provide several case studies in Table III. The first case (South$\_$Korea, Intent intelligence, Japan?) indicates that evaluation with $G_{<t_{d}}$ performs better than with $G_{<t_{E}}$. Historical facts in $G_{<t_{E}}$ tend to associate South$\_$Korea to North$\_$Korea, i.e. (South$\_$Korea, Host a visit, North$\_$Korea). However, there are directly related historical facts in $G_{<t_{d}}$, (South$\_$Korea, Intent intelligence, Japan).

Meanwhile, closely related entities affect the prediction results. For instance, both historical facts in $G_{<t_{E}}$ and $G_{<t_{d}}$ contain amounts of triplets (Japan, $*$, South$\_$Korea), as a result, the prediction probability of South$\_$Korea for (Japan, Intent cooperate, China?) is higher than of China even though there is directly related historical facts (Japan, Intent cooperate, China) in $G_{<t_{E}}$.

The third case indicates that recent facts will greatly affect the reasoning results even these intentions are not correct for the prediction, i.e. MTDM assigns South$\_$Korea and Barack$\_$Obama as the targets of (North$\_$Korea, Criticize or denounce, Japan?) for historical facts (North$\_$Korea, Criticize or denounce, South$\_$Korea) and (North$\_$Korea, Criticize or denounce, Barack$\_$Obama).

Finally, we observe that reasoning results are affected by the frequency of entities. We list Top$\_$10 entities and their occurrence times summarized within recent historical facts, that is, (‘Vietnam’, 38), (‘Afghanistan’, 38), (‘North$\_$Korea’, 43), (‘South$\_$Korea’, 46), (‘Thailand’, 48), (‘Japan’, 67), (‘Citizen$\_$(India)’, 77), (‘Iraq’, 83), (‘Iran’, 136), (‘China’, 181). Therefore, ‘Vietnam’, ‘Afghanistan’, ‘Thailand’ are selected as the targets for the prediction of (China, Intent cooperate, Japan?) even there are no direct links between entities.