TACE: TIME-AWARE CONVOLUTIONAL EMBEDDING LEARNING FOR TEMPORAL KNOWLEDGE REASONING
Year: 2021

Abstract:
Temporal knowledge graph completion (TKGC) is a challenging task to infer the missing component for quadruples. The key challenge lies at how to integrate time information into the embeddings of entities and relations. Recent TKGC methods tend to capture temporal patterns via linear or multilinear models, which are fast but not expressive enough. In this study, we propose a novel time-aware convolutional embedding model (TaCE) to represent the time-dependent facts in the task of TKGC. It highlights its novelty to feasibly convert timestamps as temporal convolutional filters to fully interact with entities and relations and learn temporal patterns in knowledge graphs (KGs). An extensive comparison proves that our model outperforms the state-of-the-art models on three public benchmark datasets of ICEWS14, ICEWS05-15 and GDELT. Results also demonstrate good temporal expressiveness and computation efficiency performed by our TaCE.

heading: 1 INTRODUCTION
text: Knowledge graphs (KGs), storing facts in tuples, are often faced with incompletion. To solve this problem, knowledge graph embedding (KGE), mapping the entities and relations into a continuous vector space, has been developed to capture the semantic meanings for the task of KG reasoning (KGR) or KG completion (KGC) (Bordes et al., 2013; Trouillon et al., 2016; Sun et al., 2019). Both KGR and KGC aim at inferring the missing facts for a given knowledge graph (Chen et al., 2020). Traditional KGE or KGC approaches usually treat KGs to be static, which means that the nodes and edges of a KG would not evolve with the time (Kazemi et al., 2020; Ji et al., 2021). However, in reality, most facts or events are only valid at a specific point or over a certain period. For example, in “Franklin D.Roosevelt was in office during 1933-1945 and died on April 12th, 1945”, it indicates two facts (‘in office’ and ‘death’) related to the target person following different time orders and spans. In that case, KGC should be implemented at the temporal scale, and KGE models are supposed to have temporal awareness.
To better capture the knowledge evolution, recent temporal KG reasoning (TKGR) or temporal KG completion (TKGC) researches try to integrate the temporal information into the KGE procedure. Methods can be roughly divided into two categories: the structure-based methods and the sequencebased methods. Acting as an extension of static KGE modelling, the former type aims to project the entities and relations into a time-dependent vector space with the inherent KG structure preserved (Jiang et al., 2016; Dasgupta et al., 2018; Xu et al., 2020; Lacroix et al., 2020); they behave to be time-efficient on account of linear or multi-linear transformations but face with the shallow representation problem. The sequence-based methods (Jin et al., 2020; Wu et al., 2020; Li et al., 2021), splitting the entire KG into a sequence of graph snapshots along the time, rely on the sequence models such as the recurrent neural network (RNN) (Jin et al., 2020; Trivedi et al., 2017; Seo et al., 2018), long and short-term memory (LSTM) (Wu et al., 2020) or gated recurrent unit (GRU) (Li et al., 2021) to inherently encode temporal features. Although the performances based on the sequence models are reasonably good, they are computationally expensive when running over a large-scale KG. Moreover, their prediction results would be undermined by temporal sparsity to some extent due to the reason that only a small fraction of nodes and edges are activated at each time (Wu et al., 2020).
In this paper, we are inclined to apply the structure-based method to manage TKGR or TKGC. Inspired by the successful applications of convolutional networks on static KGE (Dettmers et al., 2018;
Jiang et al., 2019; Balažević et al., 2019a), we hereby build a novel time-aware convolutional embedding (TaCE) model to infer the missing facts for a temporal knowledge graph (TKG). It highlights its advantage in generating the convolution filters constructed from timestamps and convolving the time information into the embeddings of entities and relations. Such a convolutional design enables the model to deeply, comprehensively and efficiently extract the temporal features and the static ones and achieves a better link prediction for the TKGC task. Results demonstrate that TaCE has the superiority in learning temporal information as well as its interactions with the entities and the relations. It balances the tradeoff between expressiveness and training speed. The key contributions of this article can be summarized as follows:
• We creatively propose time-aware convolution method to integrate the time information into the embeddings of entities and relations for a better link prediction.
• An extensive comparison has been conducted between TaCE and the state-of-the-art models to verify their performances on different public datasets.
• Further analyses have been done to prove that our model, TaCE, is able to capture the semantic meanings for the timestamps and learn facts with proper time order and consistency.

heading: 2 RELATED WORK
text: Static KG representation learning To discover the unknown facts in KGs, substantial static KGE methods have been proposed in the last decade. These methods commonly convert entities and relations into continuous vector spaces, and employ a scoring function to measure the plausibility of each candidate for KGC. TransE (Bordes et al., 2013), is one of the most widely-used transitional distance models, to embed entities and relations. Motivated by TransE, a series of similar models including TransH (Wang et al., 2014), TransR (Lin et al., 2015), and TransD (Ji et al., 2015) are developed to achieve better link predictions. RESCAL (Nickel et al., 2011) and its extensions (DistMult (Yang et al., 2014), ComplEx (Trouillon et al., 2016), and TuckER (Balažević et al., 2019b)) represent typical semantic matching models using tensor/matric factorization. Apart from them, ConvE (Dettmers et al., 2018), ConvR (Jiang et al., 2019) and HypER (Balažević et al., 2019a) recently ignite the passions of using convolution networks for KGE; they successfully prove their feature expressiveness better than those linear ones in link prediction. However, there is no study by far introducing convolution modelling into TKGC.
Temporal KG representation learning As forementioned, representation learning for TKG can be roughly categorized into two classes: structure-based models and sequence-based models. The former represent the quadruples in TKG by building time-sensitive embedding models. TTransE (Jiang et al., 2016) and DE-SimplE (Goel et al., 2020) integrate timestamp information into the corresponding the embeddings of relations and entities to infer the missing knowledge. HyTE (Dasgupta et al., 2018) projects the entities and relations to the temporal hyperplanes. ChronoR (Sadeghian et al., 2021) and TeRo (Xu et al., 2020), the most recent works, treat the timestamped relations as a temporal rotation from the head entity to the tail entity. Sequence-based models, including KnowEvolve (Trivedi et al., 2017), GCRN (Seo et al., 2018), RE-NET (Jin et al., 2020) and RE-GCN (Li et al., 2021), attempt to use the sequential networks such as RNN, LSTM and GRU to learn timedependent facts. However, they are designed for the task of graph extrapolation and “not compatible with TKGC settings (Wu et al., 2020). TeMP (Wu et al., 2020) is one of the sequence-based models, designed for TKGC tasks using graph neural network (GNN) and LSTM to capture the intra-graph patterns and inter-graph relationships, respectively. Therefore, we group TeMP, as the representative for the sequence-based model, into our baselines.

heading: 3 PROBLEM FORMULATION
text: Before going to the details of our TaCE model, we formally define the key notations and TKGC task.
Temporal Knowledge Graph (TKG) A TKG G is composed by a set of real-world facts G = {(s, r, o, t) | s, r ∈ E , r ∈ R, t ∈ T }, where, in each quadruple, s denotes the head entity, r is the relation, o is the tail entity, t is a discretized timestamp; E , R and T stand for the all the entities, relations and timestamps belong to the TKG.
Temporal Knowledge Graph Completion (TKGC) The task of TKGC or TKGR is to infer the missing component, (?, r, o, t), (s, r, ?, t) or (s, ?, o, t), given that the other three elements of the quadruple are known. It is supposed that the missing part exists in E , R. In this article, our job focuses on predicting the missing head or tail entity, but we only take (s, r, ?, t) as the example for modelling expression in later section.

heading: 4 METHOD: TACE

heading: 4.1 FRAMEWORK OF TACE
text: The model of TaCE is mainly composed of four components: the temporal convolution module aims to construct temporal convolution filters to go through the input entities and relations to obtain the time-aware representations for all the input; the static convolution module, as the name suggests, is to facilitate the convolution across all the entities and relations again to learn the context information changed without the time; the deep learning module, made up of several hidden layers, is responsible for comprehensively and deeply drawing the representations carried both from the temporal and static modules; after that, the prediction layer delivers the probability for each tail entity candidate to suggest the most likely answer for the incomplete G. Figure 1 displays the architecture of TaCE.

heading: 4.2 TEMPORAL CONVOLUTION MODULE
text: In this module, the temporal information formed by the timestamp t ∈ T is fully integrated into the subject entity s ∈ E and the relation r ∈ R via the convolution filters adaptively constructed from the timestamp t.
• Firstly, to integrate the time information into the entity s and the relation r, the temporal convolution filters are developed. They are constructed from the timestamp embedding et ∈ Rdt , where dt is the embedding size of the timestamps. Originally derived from the timestamp t, et is the input into a fully connected layer fc to get a vector vt with a proper length for further processing; then et is further split into a set of 1D convolution filters Ft = { k (1) t ,k (2) t , . . . ,k (c) t } sharing
the same size, where k(l)t ∈ Rw represents the lth convolution filter, w denotes the embedding
size of the filters and c denotes the number of the filters. The procedure of constructing temporal convolution filters is illustrated in Figure 2.
• Secondly, before filtered by temporal convolutional filters Ft, the subject entity embedding es ∈ Rde and the relational embedding er ∈ Rdr are stacked up like an ‘image’ with multi channels, with de = dr arepresenting the embedding size of entities and relations respectively. Such a stacking operation enables both the entity information and relation information to feasibly act with Ft. After convolved by Ft, the corresponding temporal feature maps Mtemp = { m (1) t ,m (2) t , . . . ,m (c) t } , where m(l)t ∈ Rde−w+1 is the lth feature map convolved
from the subject entity embedding es and the relational embedding er, and c is equal to the number of filters. The convolution with temporal convolution filters is illustrated in Figure 3. hs and hr denote the convolved es and er respectively in Figure 3.
• Finally, the matrix Mtemp feed into a fully connected layer ftemp to obtain the flatten knowledge feature of atemp ∈ Rde .
The equation of the temporal block is formulated as follow: atemp = ftemp ( [es; er]3 ∗ vec −1 (fc(et)) )
(1)
where, vec−1 is a splitting operator to reshape the embedding et of the timestamp t into a set of filters, ∗ represents the convolutional operations, and [es; er]3 represents the stacked tensor made up of the embedding es and the embedding er.

heading: 4.3 STATIC CONVOLUTION MODULE
text: To capture the potential static information from a TKG, all the nodes and edges to form a TKG will go through the same set of the time-independent convolutional filters F = { k(1),k(2), . . . ,k(c) } with timestamps omitted. Each filter k(l) ∈ Rw in F is randomly initialized rather than constructed
from timestamps, as so to make filters time-irrelevant. The procedure of static embedding is described as:
astat = fstat ([e ′ s; e ′ r]3 ∗ F) (2)
where, e′s ∈ R′ de and e′r ∈ R′ dr represent the static embeddings for the subject s and the relation r, respectively. fstat is a fully connected layer; astat presents the final extracted static KGs patterns.

heading: 4.4 DEEP LEARNING MODULE
text: Deep learning module brings the temporal feature atemp (derived from the temporal block) and the static feature astat (derived from the static block) into the multiple hidden layers to extract a better representation of a ∈ Rde for all knowledge. The hidden layers are defined as follows: u1 = σ1(f1([atemp;astat])) u2 = σ2(f2(u1)) . . .
un = σn(fn(un−1))
(3)
where, n is the number of hidden layers, fn denotes the linear operation for the hidden layer n, σn is the activation function of the hidden layer n, ui is the result of the ith hidden layer, and we use LeakyReLU as the activation function for hidden layers.

heading: 4.5 LINK PREDICTION MODULE
text: The sigmoid is chosen as the scoring function ϕ to predict the missing object entity o for the quadtuple (s, r, ?, t):
ϕ(s, r, o, t) = f(eoun) (4)
where f is the sigmoid function; un is the hidden representation from the deep learning module. The complete formulation of ϕ for the task of TKGC is defined as:
ϕ (s, r, o, t) =
f(eoσn(fn(. . . (σ1(f1([ftemp([es; er]3 ∗ vec−1fc(et); fstat([e′s; e′r]3 ∗ F))])))))) (5)
TaCE is capable of providing scores for all candidate object entities contained by E , by employing an 1-N strategy. Such the 1-N strategy can speed up the entire scoring procedure which can be referenced to Dettmers et al. (2018) and Balažević et al. (2019a). We apply the binary cross entropy (BCE) loss function L to train the model:
L = − 1 n n∑ i=1 yilog(pi) + (1− yi)log(1− pi) (6)
where n presents the number of candidate entities; yi labels the true (yi = 1) or false (yi = 0) prediction for the ith candidate tail entity; pi denotes the probability of the ith candidate object entity upon the score function ϕ.

heading: 5 EXPERIMENTS

heading: 5.1 EXPERIMENTAL SETTINGS
text: Datasets We test TaCE on six public benchmarks, namely, ICEWS14, ICEWS05-15, GDELT, YAGO11k, WIKIDATA12k and YAGO15k. Among them ICEWS14 and ICEWS05-15 are collected from the Integrated Crisis Early Warning System (ICEWS) with different time spans (Ward et al., 2013); the GDELT dataset is obtained from the Global Database of Events, Language, and Tone (GDELT) (Leetaru & Schrodt, 2013), spanning from April 1st, 2015 to March 31st, 2016; YAGO11k and WIKIDATA12k are extracted from YAGO3 (Mahdisoltani et al., 2014) and Wikidata (Erxleben et al., 2014) with time intervals (Xu et al., 2020); YAGO15k is the only one among the six that has incomplete time information, with 73.4% of the total number having no timestamps (Lacroix et al., 2020). Data details can be referred to Table 1.
Evaluation Metrics Metrics including Hits@1, Hits@3, Hits@10, and Mean Reciprocal Rank (MRR) are involved to measure the performances of TaCE against the baseline models. Metric formulations can be found in Appendix A.2.
Baselines For a broad comparison, we collect as many KGE models as we can find. These baseline models are grouped into two: 1) the static ones, including TransE (Bordes et al., 2013), DistMult (Yang et al., 2014), ComplEx Trouillon et al. (2016), ConvE (Dettmers et al., 2018) and HypER (Balažević et al., 2019a); 2) the temporal ones, covering TTransE (Jiang et al., 2016), HyTE (Dasgupta et al., 2018), TA-DistMult (Garcı́a-Durán et al., 2018), DE-SimplE (Goel et al., 2020), TIMEPLEX (Jain et al., 2020), TNTComplEx (Lacroix et al., 2020), TeRo (Xu et al., 2020), TeMP (Wu et al., 2020), and ChronoR (Sadeghian et al., 2021). The latter three, TNTComplEx, TeMP and ChronoR, to the best of our knowledge, are most recent models.
Parameter Settings For training and evaluation, the embedding size for entity, for relation and for timestamp are set equally the same, de = dr = dt = 200; the batch size is set to 512. We adopt Adam Optimizer (Kingma & Ba, 2015) for parameter training. More details about the parameter settings can be found in Appendix A.3.

heading: 5.2 RESULTS AND COMPARISON
text: The experimental results associated with each model are summarized: the results on ICEWS14, ICEWS05-15 and GDELT are shown in Table 2; the results on YAGO11k, WIKIDATA12k and YAGO15k are shown in Table 5 in Appendix A.1 due to the page limitation. In general, our TaCE achieves the better performances on the datasets. When driving five traditional static models over the six TKG datasets, it is not surprising that none of them can provide satisfactory link predictions due to incapability of considering temporal information. Impressively, TaCE generally achieves better performances against its temporal opponents. On ICEWS14 and ICEWS05-15, TaCE delivers the upmost improvement of 4.9% on MRR and 6.5% on Hits@1 against the latest competitor, ChronoR. Although TaCE does not outperform TeMP on Hits@10, the rest marks on ICEWS14 and ICEWS0515 indicate the superiority of TaCE. On GDELT dataset, TaCE leverages the rates of four metrics by at least 7% against its temporal opponents. Compared with our compellers, TaCE achieves the best on YAGO11k and WIKIDATA12k in terms of MRR, Hits@1 and Hits@3; results on YAGO15k are also acceptable, with Hits@1 reaching the highest and MRR and Hits@3 slightly lower than the SOTA (ChronoR). Overall, TaCE presents its effectiveness on link prediction by employing temporal convolutional filters to represent its interactions with entities and with relations.

heading: 5.3 EMBEDDING VISUALIZATION
text: To demonstrate the temporal expressiveness learned by TaCE, we use T-SNE to project the trained embeddings of et (for timestamps) and atemp (for entity+relation) onto a 2D plane. Results are displayed in Figure 4&5.
Visualization of et According to Figure 4, the dimension-reduced et representing for the timestamps shows a good clustering pattern at different time scales: (a) and (b) demonstrate that the et points for ICEWS05-15 within the same year are clustered well together, transitioning from one
year to another; interestingly, the et for GDELT in (c) and (d) within the same months consecutively form a curving chain. In summary, the time embedding et, trained by the convolution networks in TaCE, can automatically learn good sematic meanings for temporal order by itself.
Visualization of atemp In Figure 5, atemp stands for the mapping representations of facts (s: boko haram, r: use conventional military force) in different years. It can be observed that this sampled temporal fact based on ICEW05-15 is evolving with time in 2011, 2013 and 2015; points sharing close distances are usually those falling in the same year. Hence, it convinces that our model has the capability of capturing evolving facts with semantic meanings.

heading: 5.4 THE AWARENESS OF TIME
text: To further demonstrate the time awareness of TaCE in factual prediction, we further plot the probabilities provided by TaCE for the fact who (Umaru Musa Yar’Adua or Muhammadu Buhari) potentially made a “statement” for the “Government (Nigeria)” during 2005-2015 as shown in Figure 6. Upon the knowledge shown in Appendix A.4, Umaru Musa Yar’Adua and Muhammadu Buhari hold their president tenure in different years. Our TaCE infers that Umaru Musa Yar’Adua has the highest scores for the fact (s: ?, r: make statement, o: Government (Nigeria), 2007-2011), but Muhammadu Buhari for (s: ?, r: make statement, o: Government (Nigeria), 2015). The reasoning results match the grounding truth, implying that our model has good time awareness to distinguish fact rankings along the time. A list of Nigerian presidents and their tenure during 2005-2015 can be found in Appendix A.4.

heading: 5.5 ABLATION STUDY
text: We conduct ablation studies on ICEWS14 to explore to what extent the temporal and static components may impact on the model prediction. The testing results are reported in Table 3.
Impact of temporal embedding module When we remove the temporal embedding module from TaCE, the model only performs as a static KGE model. The prediction results for MRR, Hits@1, Hits@3 and Hits@10 all bear significant drops compared to the states under the full condition. It highlights that the model closely relies on the temporal module to capture the evolving knowledge to enhance its prediction accuracy.
Figure 5: Visualization of atemp representing the incomplete fact of s: boko haram, r: use conventional military force in different years, based on the training of ICEWS05-15.
Figure 6: Probabilities for the fact (s:?, r: make statement, o: Government (Nigeria)) druing 2005-2015, based on the training of ICEWS0515.
Impact of static embedding module The static embedding module is responsible for learning the context knowledge of a KG. It can be observed that the performance of TaCE is slightly undermined when removing the static component off the model. This is due to the reason that ICEWS are highly dynamic data. If a KG contains more static facts, i.e., (Beijing, located in, China) or (Barack Obama, spouse of, Michelle Obama), the KGE model is necessary to incorporate the static embedding module to represent the context knowledge properly.

heading: 5.6 TRAINING EFFICIENCY
text: To test the training efficiency of TaCE for the TKGC task, we conduct a comparison of our model against its two competitors, TNTComplEx (a structure-based model) and TeMP (a sequence-based model). The tests are implemented on training 72,826 quadruples for ICEWS14 under the same computing environment. The results are shown in Table 4. Among the three tested models, TNTComplEx performs as the fastest one due to owning the tensor factorization method in its algorithm. TaCE, running convolution networks over a KG, can achieve a satisfying efficiency. TeMP costs two orders of magnitude of time to complete the whole train task, as it applies a complex GRU model to learn temporal patterns. The runtime will soar up to a high level when running over billions or trillions of facts.

heading: 6 CONCLUSION
text: In this paper, a convolution-based model called TaCE is proposed to manage the task of TKGC. The key idea is to generate the timestamp-based convolution filters based on timestamps to convolve the time-dependent entities and relations contained in a knowledge graph. Such a design allows the model to have a good expressiveness for the evolving knowledge and enables it to distinguish the facts with the time order and consistency. Furthermore, it can easily combine the static knowledge features together to achieve a better link prediction. The model has good efficiency in training procedure which allows it to run over those large-scale KGs. Additional properties such as spatial information or the description of an entity are expected to add in easily, however, this would refer to another paper in the future.

heading: A APPENDIX
text: A.1 EXPERIMENTS ON YAGO11K, WIKIDATA12K AND YAGO15K
The experimental results on YAGO11k, WIKIDATA12k and YAGO15k are shown in Table 5.
A.2 THE DETAILS OF DEFINITIONS ON EVALUATION METRICS
MRR, Hits@1, Hits@3 and Hits@10 are employed to score measure the model performance. MRR is defined as follow:
MRR = 1 2‖test‖ ∑
(s,r,o,t)∈test
( 1
ranko +
1
ranks ) (7)
where ranko and ranks denote the ranking of tail entity o and head entity s for tail and head queries, respectively. Hits@K, K=1,2,3. . . , is defined as follow:
Hits@K = 1 2‖test‖ ∑
(s,r,o,t)∈test
(I(ranko ≤ k) + I(ranks ≤ k)) (8)
where k = 1, 2, 3 . . . , I denotes the indicator function.
A.3 PARAMETER SETTINGS
The parameter settings for TaCE is listed in Table 6.
A.4 NIGERIAN PRESIDENTS AND THEIR TENURE FROM 2005 TO 2015
There mainly refer to four presidents of Nigeria from 2005 to 2015 by checking on the Wikipedia. Their tenure information is listed in Table 7.
A.5 THE NUMBER OF PARAMETERS (SPACE COMPLEXITY) OF TKGC MODELS
The number of parameters or the space complexity of TKGC models are shown in Table 8.

Review summaries:
This paper presents a time-aware convolutional embedding learning for temporal KGC. It converts timestamps as temporal convolutional filters fo fully interact with entities and relations. Overall, this paper is well written. 

The paper proposes a novel and more expressive model TaCE for temporal knowledge base completion. TaCE has 4 modules - the Temporal Convolution module (generates a time-aware representation of (s,r) or (r,o) depending on the query), Static Convolution module (generates a time-independent representation of (s,r) or (r,o) depending on the query), Deep Learning module (output of previous two modules is passed through various fully-connected layers), and Link prediction module (this final module takes input from deep learning module and scores all entities on their likelihood of being the correct answer to the query). The superiority of the model is demonstrated via extensive experimentation.

The authors propose a novel temporal knowledge graph embedding approach that is based on convolutional neural networks. To create a feature on which the link prediction is performed, the presented approach first creates both a static and a temporal feature (both in their own respective convolution modules) and fuses them together in a third deep learning module. The so generated general feature is then used to calculate scores for the missing element in a tuple (s,r,o,t). The experimental section provides a performance overview of the proposed TaCE approach on standard benchmark datasets for TKGC tasks (ICEWS{14|05-15} and GDELD). As seen in the evaluation, the proposed approach performs better or on-par with most recent SOTA approaches in the field. The result presentation is followed by a more detailed analysis of the learned temporal embeddings that appear to contain a good semantic representation of temporal order. An ablation study further shows the huge impact that the temporal embedding module has on the overall results.