Hyperplane-based time-aware knowledge graph embedding for temporal knowledge graph completion

Most of the existing KG embedding approaches are static and can be roughly divided into two categories, translational distance-based models [15, 31–33] and tensor factorization models [16, 34]. Translational distance-based models use the distance between two entities as a metric to measure the plausibility of facts, usually after a translation or rotation carried out by relations. TransE [31] is a typical translational distanced-based model. It maps facts into a real vector space and interprets the relation as a translation from the head to the tail. The score function is defined as the Euclidean distance between the translated head embedding and tail embedding. TransE can implicitly model the antisymmetry, inversion and composition relation patterns, but has difficulty in modeling the symmetry relation pattern which is common in real-world KGs. To overcome this drawback, many variations of TransE have been proposed, such as RotatE [15] and HAKE [32]. Compared with TransE, RotatE maps each triple into a complex vector space instead of a real vector space, and considers the relation as a rotation from the head embedding to the tail embedding in the complex vector space. In this way, RotatE could model and infer all four important types of relation patterns mentioned above. Moreover, HAKE is a slight extension of RotatE. By taking advantage of both the modulus and phrase part of the complex vector, HAKE is able to model not only all of the above relation patterns but also semantic hierarchies between entities.

Apart from translation distance-based models, tensor factorization models are also competitive on many benchmarks, including DistMult [20], ComplEx [16] and SimplE [21]. DistMult defines the same embedding function as in TransE, but the score function is the sum of Hadamard (element-wise) product of embedding vectors. Intuitively, DistMult is a simplified version of the tensor factorization model, which learns a symmetric tensor in the head and tail modes to keep the parameter sharing. As a result, it can only model symmetric relations and cannot infer antisymmetric relations. ComplEx enhances DistMult by mapping elements into a complex space, where head and tail embeddings share the parameters of values but are complex conjugate of each other. SimplE is another tensor factorization approach based on Canonical Polyadic (CP) decomposition [35], which employs inverse relations to associate two embeddings of the same entity locating at different positions. Compared with ComplEx, SimplE avoids computational redundancy and reduces time consumption. Besides, Lacroix et al. [34] also proposed a similar CP decomposition-based model to improve the performance.

Although static models have achieved great success, their representing and modeling capabilities are still limited due to the single static triples. Therefore, all kinds of extensions of static KG embedding models have been developed by infusing rich additional information into the process of representation learning, including time information, entity types, relation paths, etc. Especially time information, which demonstrates the specific time when an event happened or a fact was valid, can effectively avoid entity confusion and improve the performance of KG embedding.

2.2 Temporal KG embedding models

Many temporal KG embedding models have been explored and most of them can be seen as extensions of static models. Such as, TTransE [22], HyTE [24] and TA-TransE [25] are extended from TransE, TA-DistMult [25] is the temporal extension of DistMult. Similar to their static versions TransE and DistMult, these temporal KG embedding models have issues with inferring symmetric relations or antisymmetric relations. Recently, TComplEx and TNTComplEx [23] follow CP decomposition to extend ComplEx by adding a new temporal factor vector. Therefore, same as ComplEx, TComplEx and TNTComplEx also involve the problem of redundant computations. DE-SimplE [27] learns entity embeddings that evolve over time by introducing a diachronic entity (DE) embedding function. As an extension of SimplE, DE-SimplE has the capability of encoding domain knowledge by parameter sharing and is the first full expressive temporal KG embedding model. ConT [26] can be seen as an extension of Tucker [36] which replaces the core tensor in Tucker decomposition [37] with a time-specific tensor. Both DE-SimplE and ConT do not take into account facts with time intervals shaped like [2015, 2018] and are hard to predict time scopes for facts missing time information. Moreover, because of the large number of parameters per timestamp, ConT faces a high time complexity and rapid overfits during training. Inspired by RotatE, ChronoR interprets the relation and time together as a rotation from the head entity to the tail entity, and represents entities, relations and timestamps as matrices in real vector space. While the operation of the matrices brings high time and space costs. In contrast, HERCULES [38], which is a time-aware extension of the static model ATTH [39] learns embeddings in hyperbolic spaces rather than Euclidean space. But similar to DE-SimplE and ConT, HERCULES cannot model timestamps with the form of time intervals. On the other hand, recent T-GAP [40] incorporates neural network and additional relation path information to the process of temporal KG embedding, which aims to fully exploit the local neighborhood and facilitate multi-hop reasoning. However, both neural network and path traversal are time-consuming.

In contrast, our proposed model HTKE has merits to conquer these issues. That is, our model could deal with time information not only in the form of points in time but also in the form of time intervals, and predict temporal scopes for facts with missing time information. Furthermore, our model is capable of modeling and inferring all four important relation patterns including symmetry, antisymmetry, inversion and composition with linear time and space consuming.

All of the above temporal KG embedding models, including our method can be classified as the interpolation setting. Under this setting, models attempt to infer missing links at past timestamps. While most recently, several work [41–45] attempt to predict facts in the future, which is called the extrapolation setting. Under the extrapolation setting, models can better support the open-world assumption that missing facts is not necessarily false and may potentially happen in the future, which is also the direction of our future work.

3.1 Time-specific hyperplane

As mentioned above, temporal KGs provide time information of facts. In order to incorporate these time information directly during KG embedding algorithm, for a KG with time information in the form of points in time, we dismantle it into n disjoint time point subgraphs G = G _{τ 1}  ∪ G _{τ 2}  ∪ … ∪ G _{τ n} , where ∀i≠ j, G _{τ i}  ∩ G _{τ j}  = ∅ and τ _i  (i ∈ 1, 2, ⋯ , n) is one of the time points. For a KG with time information in the form of time intervals, we dismantle it into n disjoint time period subgraphs G = G _{τ 1}  ∪ G _{τ 2}  ∪ … ∪ G _{τ n} , where ∀i≠ j, G _{τ i}  ∩ G _{τ j}  = ∅ and τ _i  (i ∈ 1, 2, ⋯ , n) is one of the time periods with minimum time min(τ _i ), maximum time max(τ _i ). Each quadruple belongs to one or more time subgraphs according to its timestamp. Such as, if the timestamp is a specific point in time with the form of τ, then it only belong to one time point subgraph G _{τ i} when τ = τ _i . While if the timestamp of a quadruple is a time interval with the form of [τ _s , τ _e ], then it may belong to one time period subgraph G _{τ i} or more time period subgraphs G _{τ i}  … G _{τ j} when min(τ _i ) ≤ τ _s  ≤ τ _e  ≤ max(τ _i ) or min(τ _i ) ≤ τ _s  ≤ max(τ _i ) ≤ … ≤ min(τ _j ) ≤ τ _e  ≤ max(τ _j ).

Then, each time subgraph is associated with a time-specific hyperplane represented by a normal vector τ , where τ ∈ ℝ d and || τ _i ||₂ = 1. Thus, we can get n different hyperplanes represented by normal vectors τ ₁, τ ₂, …, τ _n . That is to say, we can segregate the space into n different time zones with the help of these time-specific hyperplanes.

Subsequently, we project each fact to time-specific hyperplanes which it belongs to. Such as Fig. 3 shows, we project two facts with time information (US, has president, Barack Obama, [2009-2017]) and (US, has president, Bill Clinton, [1993-2001]) onto different time-specific hyperplanes denoted by normal vectors τ  = [2009 - 2017] and τ  = [1993 - 2001]. In this way, facts happened at different times can be distinguished. Therefore, its easy to conclude the correct answer ‘Bill Clinton’ when answering the the query (US, has president, ?, [1993-2001]) mentioned in section 1.

OPEN IN VIEWER

Fig. 3

Simple illustration of our proposed HTKE.

In order to model and infer four common and important relation patterns introduced in section 2, we further map facts projected on the same time-specific hyperplane into a polar coordinate system. Specifically, we first map each entity e to two parts–the modulus part e m ∈ ℝ d and the phase part e _p  ∈ [0, 2π)  ^d , where the modulus part corresponds to the radial coordinate and the phase part corresponds to the angular coordinate. Thus the projections of entities on the time-specific hyperplane τ can be represented as projected modulus parts: e m ⊥ = e m - ( τ ⊤ e m τ ) ,(1) and the projected phase part: e p ⊥ = e p - ( τ ⊤ e p τ ) .(2)

On this hyperplane, we consider every dimension of projected entity representation, i.e., ([ e _m⊥]  _i , [ e _p⊥]  _i ) as a 2D point in the polar coordinate system. Inspired by static models RotatE and HAKE, we interpret each relation as a rotation from the projected head angular coordinate [ h _p⊥]  _i to the projected tail angular coordinate [ t _p⊥]  _i plus a scaling transformation form the projected head radial coordinate [ h _m⊥]  _i to the projected tail radial coordinate [ t _m⊥]  _i . Therefore, the relation r should also be mapped to two parts r m ∈ ℝ + d and r _p  ∈ [0, 2π)  ^d where r _m represents the extent of scalability, r _p represents the rotation angle. These two parts are also projected onto the corresponding time-specific hyperplane. Given a quadruple (h, r, t, τ), we adopt the basic idea of translation distance-based models, using the distance between the head entity transformed by the relation and the tail entity in the polar coordinate system to measure the factuality of this quadruple. Alternatively, for a positive quadruple, we expect that the head entity embedding rotated and scaled by the relation embedding is as close to the tail entity embedding as possible and otherwise, they are expected to be far away. As a result,the score function is defined as φ ( h , r , t , τ ) = - ‖ h m ⊥ ∘ r m ⊥ - t m ⊥ ‖ 2 - λ ‖ sin ( ( h p ⊥ + r p ⊥ - t p ⊥ ) / 2 ) ‖ 1(3) where the first part -|| h _m⊥ ∘  r _m⊥ -  t _m⊥||₂ represents the distance between the head entity after scaling by the relation and the tail entity in the radial coordinate, and the second prat -|| sin(( h _p⊥ +  r _p⊥ -  t _p⊥)/2) ||₁ represents the distance between the head entity after rotation by the relation and the tail entity in the angular coordinate. The smaller the distance, the higher the score. The sin function is used in the second part because the angular coordinates have periodic characteristics and λ ∈ ℝ is a parameter that is learned by the model. Figure 3 gives an illustration of the proposed model.

Our method can model and infer all four important relation patterns including symmetry, antisymmetry, inversion and composition. On time-specific hyperplane τ , similar to RotatE and HAKE, a relation r is symmetric(antisymmetric) if and only if each element of its projected rotation angle [ r _p⊥]  _i satisfies [ r _p⊥]  _i  = kπ  ([ r _p⊥]  _i  ≠ kπ) , k = 0, 1, 2; two relations r₁ and r₂ are inverse if and only if each element of their projected rotation angles is opposite to each other: [ r _1p⊥]  _i  = - [ r _2p⊥]  _i ; a relation r₁ is a combination of other two relations r₂ and r₃ if and only if each element of their projected rotation angle satisfy [ r _1p⊥]  _i  = [ r _2p⊥]  _i  + [ r _3p⊥]  _i . Figure 3 shows how HTKE models these relation patterns with only 1-dimensional embedding.

Lemma 1. HTKE can infer the symmetry/antisymmetry relation pattern in time-specific hyperplanes.

Proof. If (h, r, t, τ) and (t, r, h, τ) hold in their corresponding time-specific hyperplane τ , we have

t p ⊥ = ( h p ⊥ + r p ⊥ ) mod 2 π ∧ h p ⊥ = ( t p ⊥ + r p ⊥ ) mod 2 π ⇒ ∀ i , [ r p ⊥ ] i = k π , k = 0 , 1 , 2(4)

Otherwise, if (h, r, t, τ) and ¬ (t, r, h, τ) hold, we have

t p ⊥ = ( h p ⊥ + r p ⊥ ) mod 2 π ∧ h p ⊥ ≠ ( t p ⊥ + r p ⊥ ) mod 2 π ⇒ ∃ i , [ r p ⊥ ] i ≠ k π , k = 0 , 1 , 2(5)

Lemma 2. HTKE can infer the inversion relation pattern in time-specific hyperplanes.

Proof. If (h, r₁, t, τ) and (t, r₂, h, τ) hold in their corresponding time-specific hyperplane τ , we have

t p ⊥ = ( h p ⊥ + r 1 p ⊥ ) mod 2 π ∧ h p ⊥ = ( t p ⊥ + r 2 p ⊥ ) mod 2 π ⇒ ∀ i , [ r 1 p ⊥ ] i = - [ r 2 p ⊥ ] i(6)

Lemma 3. HTKE can infer the composition relation pattern in time-specific hyperplanes.

Proof. If (h, r₁, t, τ), (h, r₂, e, τ) and (e, r₃, t, τ) hold in their corresponding time-specific hyperplane τ , we have

t p ⊥ = ( h p ⊥ + r 1 p ⊥ ) mod 2 π ∧ e p ⊥ = ( h p ⊥ + r 2 p ⊥ ) mod 2 π ∧ t p ⊥ = ( e p ⊥ + r 3 p ⊥ ) ⇒ ∀ i , [ r 1 p ⊥ ] i = [ r 2 p ⊥ ] i + [ r 3 p ⊥ ] i(7)

As described in [46], to scale to the size of current KGs and keep up with their growth, a KG embedding model must have a linear time and space complexity. Models with many parameters usually overfit and present poor scalability. We calculate and analyze the time complexity and the number of parameters for several state-of-the-art temporal KG embedding approaches and our model according to embedding functions and score functions of models, which are listed in Table 2, where d is the dimension of the embedding vector space. Contrary to DE-SimplE, other models do not learn temporal embeddings that scale with the number of entities (as frequencies and biases), but rather embeddings that scale with the number of timestamps. Although our model has more parameters than HyTE, but experiments demonstrate that our model performs better than HyTE because of the ability to model the symmetry relation pattern. All of the temporal models except for ConT have the linear time complexity O (d). The large number of parameters per timestamp (a three-order tensor) makes ConT perform poorly and train extremely slowly. As an extension of ComplEx, TComplEx also involves redundant computations.

To train the model, we use the negative sampling loss function with self-adversarial training [15]: L = ∑ x ∈ G + ∑ y ∈ G - ,(8)

where γ is a fixed margin, σ is the sigmoid function, α is the temperature of sampling and G + , G - is the set of positive instances and negative instances respectively. y _i is the ith negative sample.

In order to get better performance in link prediction and temporal scopes prediction, besides the common entity negative sampling, we also explore a time-enhanced negative sampling strategy for time information:

Entity negative sampling corrupts head entities or tail entities of positive instances randomly irrespective of timestamps. More formally, negative samples come from the set

G - = { ( h ′ , r , t , τ ) | h ′ ∈ E , ( h ′ , r , t , τ ) ∉ G + } ∪ { ( h , r , t ′ , τ ) | t ′ ∈ E , ( h , r , t ′ , τ ) ∉ G + } .(9)

Time-enhanced negative sampling emphasizes on time. By corrupting timestamps, we get negative samples that do not exist in any timestamps of the temporal KG. Thus we draw negative samples from the set G - = { ( h , r , t , τ ′ ) | τ ′ ∈ T , ( h , r , t , τ ′ ) ∉ G + } .(10)

In this part, we show the performance of our proposed model HTKE against existing state-of-the-art methods. Table 4 lists the results for the link prediction task on ICEWS14, ICEWS05-15 and YAGO11k. According to the results, the temporal models outperform the static models in MRR and Hit@N in most cases which provides evidence for the merit of capturing time information.

Overall, our model matches or beats the competitive methods on all datasets. Specifically, our model significantly outperforms HyTE on all datasets since HTKE can infer all four relation patterns while HyTE cannot infer the symmetry relation pattern which is common in real-world datasets. For instance, YAGO11k dataset contains the symmetric relation ‘isMarriedTo’ and ICEWS contains symmetric relation ‘negotiate’. The superior performance of HTKE empirically shows the importance of modeling and inferring four relation patterns for the task of predicting missing links.

DE-SimplE, together with ConT, cannot get results in YAGO11k datasets, because in YAGO11k, timestamps of quadruples are time intervals and they can’t deal with this form of timestamps. Furthermore, DE-SimplE only considers entities evolving with time and ignores the time attributes of relations and whole facts. Therefore, it cannot achieve results as good as ours on ICEWS14 and ICEWS05-15. Because of the large number of parameters per timestamp, ConT performs poorly on ICEWS as it probably overfits. Apart from affecting the prediction performance, the large number of parameters makes training ConT extremely slow.

As Table 4 shows, our model gives on-par results compared with recent TComplEx on ICEWS14 and ICEWS05-15, but performs better than them on YAGO11k. Since the timestamps on ICEWS14 and ICEWS05-15 are points in time, while on YAGO11k are time intervals with the form of [t _s , t _e ], and dealing with timestamps of time intervals is a challenging task. TComplEx samples uniformly between start time and end time at random. In this way, it treats time intervals as discrete points in time and cannot capture the continuity of time. However, in our model, we divide time intervals into time period subgraphs, thus our model could maintain the continuity of time well. This result also validates the merit of our method. On the other hand, both TComplEx and our method encode timestamps with the form of time points as vectorial embeddings. And as a temporal extension of the static model ComplEx, TComplEx also has the powerful capability to model important relation patterns. Therefore, It can achieve comparable results with our model on ICEWS14 and ICEWS05-15. However, like its static version ComplEx, TComplEx faces the problem of computational redundancy. At the same time, TComplEx requires more parameters than ours, which is analyzed in Section 3.4. As a result, our model is more time and space-efficient than TComplEx. Such as, under the same hardware and software conditions, it only takes 3694s for HTKE to finish 100 training epochs, while TComplEx needs 12408s.

4.2 Temporal scope prediction

Given the scarcity of time information in temporal KG, predicting missing time information for facts is an important problem. Unlike previous baseline methods, our model can predict the temporal scope for a given quadruple (h, r, t, ?). In this task, the training procedure remains the same as the link prediction task. We project the entities and the relation of the quadruple on all time-specific hyperplanes and check the plausibility of that quadruple on each hyperplane by their scores. We select the time information of the time-specific hyperplane corresponding to the highest score as the temporal scope of that quadruple.

We plot in Fig. 5 the scores along time for facts (Ashley Cole, plays for, {Arsenal F.C. | Chelsea F.C. | A.S. Roma | LA Galaxy}, { | [2006–2014] | [2014–2016] | [2016-?]}) from YAGO11k. The time periods with the highest scores match closely the ground truth of the start and end year of these quadruples which are represented as a colored background. This result shows that our model can correctly predict temporal scopes along time periods. We also can infer the temporal scope of the end time missing in the fact (Ashley Cole, plays for, LA Galaxy, [2016-?]). From the result, we get the highest score for this fact in [2016–2019] period, and the true end time is 2019 learned from Wikipedia which matches our results very well. This result also shows that our model is effective in temporal scope prediction.

OPEN IN VIEWER

Fig. 4

Illustrations how HTKE models relation patterns with only 1 dimension of embedding.

OPEN IN VIEWER

Fig. 5

Scores for facts (Ashley Cole, plays for, {Arsenal F.C. | Chelsea F.C. | A.S. Roma | LA Galaxy}, {[1999-2006] | [2006-2014] | [2014-2016] | [2016-?]}).

In this part, we show that HTKE could implicitly represent the symmetric relation pattern by analyzing the projected rotation angle of relation embeddings.

The symmetry relation pattern requires the symmetric relation to have each element of its projected rotation angle satisfy [ r _p⊥]  _i  = kπ, k = 0, 1, 2. We investigate the relation embeddings from a 500-dimensional HTKE trained on YAGO11k. Figure 6a gives the distribution histogram of the average angle of each element projected on all time-specific hyperplanes of the symmetric relation embedding ‘isMarriedTo’. We can find that the rotation angles are 0, π or 2π. It indicates that the HTKE does infer and model the symmetry relation pattern. Figure 6b is the histogram of relation ‘wasBornIn’, which shows that the embedding of a general relation does not have such kπ pattern.

OPEN IN VIEWER

Fig. 6

Distribution histograms of two relations embedding phases that reflect the same hierarchy. The x-axis represents the value of entry [ r _p⊥]  _i , the y-axis represents the number of entry [ r _p⊥]  _i .