A quaternion-group knowledge graph embedding model

3.1 Relation pattern

To better express the relation patterns in KGs, we define them as follows:

Definition1 .  Symmetry. A relation r is symmetric if ∀e _i , e _j r ( e i , e j ) ⇒ r ( e j , e i )(1)

Definition2 .  Anti-symmetry. A relation r is anti-symmetric if ∀e _i , e _j r ( e i , e j ) ⇒ ¬ r ( e j , e i )(2)

Definition3 .  Inversion. A relation r₁ is reverse to relation r₂ if ∀e _i , e _j r 1 ( e i , e j ) ⇒ r 2 ( e j , e i ) r 2 ( e i , e j ) ⇒ r 1 ( e j , e i )(3)

Definition4 .  Commutative Composition. A relation r₃ is a commutative composition of relation r₁ and relation r₂ if ∀ e i , e j , e j ′ , e k r 1 ( e i , e j ) ∧ r 2 ( e j , e k ) ⇒ r 3 ( e i , e k ) r 2 ( e i , e j ′ ) ∧ r 1 ( e j ′ , e k ) ⇒ r 3 ( e i , e k )(4)

Definition5 .  Non-commutative Composition. A relation r₃ is a non-commutative composition of relation r₁ and relation r₂ if ∀ e i , e j , e j ′ , e k r 1 ( e i , e j ) ∧ r 2 ( e j , e k ) ⇒ r 3 ( e i , e k ) r 2 ( e i , e j ′ ) ∧ r 1 ( e j ′ , e k ) ≱ r 3 ( e i , e k )(5) where e _i , e _j , e j ′ and e _k denote different entities in a KG.

To better comprehend the relation modeling in group space, we firstly provide interrelated definitions of group theory.

Definition6 .  Group. Let G be a non-empty set. (G, ★) is composed of the binary operation ★ (i.e., multiplication) in G (i.e., G ★ G → G). (G, ★) is a group with law of composition ★ if the following axioms hold:

1. Closure: for ∀a, b ∈ G, we have a ★ b ∈ G.

2. Associativity: for ∀a, b, c ∈ G, we have (a ★ b) ★ c = a ★ (b ★ c).

3. Identity element: for ∀a ∈ G and ∃e ∈ G, we have e ★ a = a ★ e = a. We call e an identity of (G, ★).

4. Inverse element: for ∀a ∈ G and ∃b ∈ G, we have a ★ b = b ★ a = e. We call b an inverse of a, which is denoted a^-1.

Definition7 .  Abelian Group. A group (G, ★) is an abelian group if ∀a, b ∈ G, a ★ b = b ★ a.

Definition8 .  Non-Abelian Group. A group (G, ★) is an non-Abelian group if ∃a, b ∈ G, a ★ b ≠ b ★ a.

As we can see, the inversion pattern of relation (i.e., Definition 3) is similar to inverse element in the definition of the group. We summarize the correspondence between relation patterns and group theory in Table 2.

Mathematically, a KG contains an entity set E = { e i } , a relation set R = { r k } and a fact set F = { f l } . E and R form a collection of factual triplets ( F ). Each factual triplet f _l , denoted by (e _h , r, e _t ), where r is the relation pointing from the head entity e _h to the tail entity e _t . We focus on the knowledge completion task, which aims to predict missing links based on the observed facts. To fulfill this goal, KGE model usually defines a score function for triples. The score function takes the form f _r  (h, t), where h, r and t are head entity, relation and tail entity embeddings, respectively. The score function is used to measure the rationality of proposed fact candidates, and the goal of KGE model optimization is to give higher scores to the correct triplets (e _h , r, e _t ) than the corrupted triplets ( e h ′ , r , e t ) or ( e h , r , e t ′ ), where e h ′ and e t ′ are randomly replaced head and tail entities, respectively.

3.4 Quaternion group representation

A quaternion is a simple super complex number. The complex number consists of a real number plus an imaginary unit i, where i² = -1. Similarly, quaternions are composed of real numbers plus three imaginary units i, j, k, and they have the following relations: i² = j² = k² = ijk = -1,i⁰ = j⁰ = k⁰ = 1, each quaternion is a linear combination of 1, i, j, k, that is, a quaternion can generally be expressed as Q = q₀ + q₁i + q₂j + q₃k, where q₀, q₁, q₂, q₃ are real numbers and i, j, k are imaginary units. In addition, ij = k, ji = -k, jk = i, ki = j, kj = -i, ik = -j.

To better represent quaternion group, other important operational rules for quaternions are described as follows:

Conjugate :  The conjugate of a quaternion is defined as follows: Q ¯ = q 0 - q 1 i - q 2 j - q 3 k Q Q ¯ = q 0 2 + q 1 2 + q 2 2 + q 3 2(6)Quaternion Modulus :  The modulus of a quaternion is defined as follows: | Q | = | Q ¯ | = q 0 2 + q 1 2 + q 2 2 + q 3 2(7)Quaternion Inversion :  The inversion of a quaternion is denoted as Q^-1, which is defined as follows: QQ - 1 = Q - 1 Q = 1 Q - 1 = Q ¯ | Q | 2 = Q ¯ q 0 2 + q 1 2 + q 2 2 + q 3 2(8)Unit Quaternion :  The properties of unit quaternions are as follows: Q - 1 = Q ¯ | Q | 2 = q 0 2 + q 1 2 + q 2 2 + q 3 2 = 1(9)Quaternion Addition :  The quaternion addition between Q₁ = q₀ + q₁i + q₂j + q₃k and Q 2 = q 0 ′ + q 1 ′ i + q 2 ′ j + q 3 ′ k is obtained as follows: Q 1 + Q 2 = ( q 0 + q 0 ′ ) + ( q 1 + q 1 ′ ) i + ( q 2 + q 2 ′ ) j + ( q 3 + q 3 ′ ) k(10)Quaternion Hamilton Product :  The Hamilton product of between Q₁ = q₀ + q₁i + q₂j + q₃k and Q 2 = q 0 ′ + q 1 ′ i + q 2 ′ j + q 3 ′ k is obtained as follows: Q 1 ∘ Q 2 = ( q 0 q 0 ′ - q 1 q 1 ′ - q 2 q 2 ′ - q 3 q 3 ′ ) + ( q 0 q 1 ′ + q 1 q 0 ′ + q 2 q 3 ′ - q 3 q 2 ′ ) i + ( q 0 q 2 ′ - q 1 q 3 ′ + q 2 q 0 ′ + q 3 q 1 ′ ) j + ( q 0 q 3 ′ + q 1 q 2 ′ - q 2 q 1 ′ + q 3 q 0 ′ ) k Q 1 ∘ Q 2 ≠ Q 2 ∘ Q 1(11)

Definition9 .  Quaternion Group. A quaternion group (G _Q , ★) is a set composed of unit quaternions in this work, which is defined as follows: ( G Q , ★ ) = { Q = q 0 + q 1 i + q 2 j + q 3 k | | Q | = 1 }(12) Since the Hamilton product of quaternions is not commutative, the quaternion group (G _Q , ★) is a non-Abelian group.

As shown in Fig. 2(b), we use Axis–Angle representation to model a rotation operation in the quaternion group-based space. More specifically, a unit vector v → represents the direction of the rotation axis, i.e., v → = ( v x , v y , v z ) = ( sin θ cos ϕ , sin θ sin ϕ , cos θ ) , where θ ∈ [0, π] and ϕ ∈ [0, 2π); and an angle ψ denotes the magnitude of the rotation about the rotation axis, where ψ ∈ [0, 2π). In this way, a four-dimensional vector (ψ, v _x , v _y , v _z ) can represent any rotation in three-dimensional space, which is denoted as a three-dimensional vector (ψ * v _x , ψ * v _y , ψ * v _z ).

Given an entity vector w e → with the coordinate (x, y, z), its rotation about axis v → with an angle of ψ can be modeled using the quaternion group (G _Q , ★) in the three-dimensional space. Specifically, the rotation is encoded by a unit quaternion with three degrees of freedom (i.e., θ, ϕ and ψ). In this work, the quaternion group (G _Q , ★) can be viewed as a group structure on a three-dimensional sphere (i.e., S3). Furthermore, this group structure is isomorphic to SU(2) group [16]. Formally, the unit quaternion Q to model a rotation through an angle of ψ around a unit vector v → (i.e., the aforementioned axis) can be defined using an extension of Euler’s formula: Q = e ψ 2 ( v x i + v y j + v z k ) = cos ψ 2 + sin ψ 2 ( v x i + v y j + v z k ) = cos ψ 2 + v x sin ψ 2 i + v y sin ψ 2 j + v z sin ψ 2 k(13)

A 3-D Euclidean vector w e → with the coordinate (x, y, z) can be denoted as a pure quaternion (the real part of quaternion is zero), i.e., Q _w  = xi + yj + zk. The destination quaternion of the vector w e → after the rotation through an angle of ψ around a unit vector v → in the corresponding quaternion-group space, i.e., Q w ′ = x ′ i + y ′ j + z ′ k , can be calculated by the Hamilton product of quaternions: Q w ′ = Q ∘ Q w ∘ Q - 1(14) where Q^-1 is the inverse of Q, i.e., Q - 1 = e - ψ 2 ( v x i + v y j + v z k ) = cos ψ 2 - sin ψ 2 ( v x i + v y j + v z k ) .

Considering each 3-D Euclidean vector can be denoted as a pure quaternion, we can now represent the rotation using a matrix R (Q) by expanding Eq. 14: w e → ′ = R ( Q ) w e →(15) where the rotation matrix R (Q) can be obtained by the quaternion after rotation(i.e., Q w ′ ) and Rodrigues’ formula [18], which is as shown Eq. 16. R ( Q ) = e v → ψ = I + [ 0 − v z v y v z 0 − v x − v y v x 0 ] sin ψ + [ 0 − v z v y v z 0 − v x − v y v x 0 ] 2 ( 1 − cos ψ ) = [ 1 − v z sin ψ v y sin ψ v z sin ψ 1 − v x sin ψ − v y sin ψ v x sin ψ 1 ] + [ − v y 2 − v z 2 v x v y v x v z v x v y − v x 2 − v z 2 v y v z v x v z v y v z ​ − v x 2 ​ − v y 2 ] ( 1 − cos ψ ) = [ cos ψ + v x 2 ( 1 − cos ψ ) v x v y ( 1 − cos ψ ) − v z sin ψ v y sin ψ + v x v z ( 1 − cos ψ ) v z sin ψ + v x v y ( 1 − cos ψ ) cos ψ + v y 2 ( 1 − cos ψ ) v y v z ( 1 − cos ψ ) − v x sin ψ v x v z ( 1 − cos ψ ) − v y sin ψ v x sin ψ + v y v z ( 1 − cos ψ ) cos ψ + v z 2 ( 1 − cos ψ ) ](16)

According to the closure property of group theory, two rotations can be combined into one equivalent rotation operation in our model. It is to say that we can define R (Q₃) = R (Q₂) R (Q₁), where R (Q₃) corresponds to the rotation R (Q₁) followed by the rotation R (Q₂). Thus, a series of rotations can compose a single rotation. It is noted that quaternion multiplication is not commutative unless Q₁ and Q₂ have the same rotation axes (i.e., v 1 → = v 2 → ), which can be seen from Eq.11. Therefore, both commutative and non-commutative relation patterns can be modelled in our model.

A score function aims to measure the rationality of proposed fact candidates. For each triple (e _h , r, e _t ), our score function is defined as follows: f r ( h , t ) = - | h R ( r ) - t |(17) where |   ·   | denotes the Euclidean distance and R (·) stands for the relation rotation on each element of the entity embeddings in the quaternion group-based space. For each element in the embeddings, we have t _i  = h _i R (r _i ) and h i = t i R ( r i - 1 ) , where r i ∈ ℍ , h _i , t i ∈ ℝ 3 , and i indicates i-th embedding unit. Negative sampling has been proved quite effective for learning KGE [19]. To properly train the model parameters, here we use a loss function similar to the self-adversarial training negative sampling loss proposed in [11] to effectively optimize our model. The loss function is as shown Eq.18. Here, γ is a fixed margin (hyper-parameter), σ is the sigmoid function, and ( e hi ′ , r , e ti ′ ) is the i-th negative triple. p ( e hi ′ , r , e ti ′ ) is the weight of the negative sample, the higher score of the negative sample, the greater weight during training. h i ′ and t i ′ are the embeddings corresponding to the negative triplet ( e hi ′ , r , e ti ′ ) . The details about self-adversarial negative sampling technique can be found in [11]. L = − log σ ( f r ( h , t ) + γ ) − ∑ i = 1 n p ( e h i ′ , r , e t i ′ ) log σ ( − f r ( h i ′ , t i ′ ) − γ )(18)

To verify whether the relation patterns are implicitly represented by QuatGE relation embeddings, we discuss as follows.

Symmetry. In our model, a relation r is symmetric if and only if each dimension of its embedding r _i satisfies |r _i |=1 and the rotation angle ψ _i is 0 or π.

Anti-symmetry. Anti-symmetry relation pattern requires that each dimension of the relation embedding r _i satisfies |r _i |=1, but the rotation angle ψ _i is neither 0 nor π.

Inversion. Inversion relation pattern requires that the embeddings of a pair of inverse relations are conjugated, i.e., |r_1i * r_2i|=1, θ_r1i = θ_r2i, ϕ_r1i = ϕ_r2i and ψ_r1i = - ψ_r2i. In other words, the embeddings of a pair of inverse relations share the same rotation axes, but rotate in two opposite directions.

Commutative/Non-commutative Composition. Since the quaternion group (G _Q , ★) is a non-Abelian group, the commutative and non-commutative composition patterns can be naturally modeled by the property of (G _Q , ★).

4.1 Datasets and evaluation metrics

Datasets. We evaluate our proposed model on four benchmark datasets: WN18 [6], WN18RR [20], FB15k [6] and FB15k-237 [21]. WN18RR is a subset of WN18, which has many inverse relations. WN18 mainly reflects symmetry/anti-symmetry and inversion pattern of relations. FB15k-237 is a subset of FB15k, which also has many inverse relations. So the main relation patterns in FB15k are also symmetry/anti-symmetry and inversion.

Since these inverse relations in WN18 and FB15k will significantly improve the experimental results. Therefore, to solve the inverse relation problem in WN18 and FB15k, WN18RR and FB15k-237 are extracted from the original dataset WN18 and FB15 by removing inverse relations. The WN18RR and FB15k-237 datasets aim to assess the model performance on composition patterns. The statistics of the four benchmark datasets are summarized into Table 3.

Evaluation metrics. To evaluate the results of link prediction, we use three evaluation metrics: Mean Rank (MR), Mean Reciprocal Rank (MRR) and Hits at N(H@N). MR measures the average rank of all correct triples with lower value representing better performance. MRR is the average inverse rank for correct triples. H@N measures the proportion of correct triples in the top N triples. Lower MR, higher MRR or higher H@N mean better performance. Final scores on the test set are reported for the model obtaining the highest H@N on the validation set.

We use Adam as the optimizer and fine-tune the hyper-parameters on the validation dataset. All algorithms are implemented in Python, and all experiments are conducted on a server with 1755 MHz 23 GD6 GeForce RTX 2080 Ti GPU and 64 GB memory.

We train QuatGE for 3,000 epochs, using a grid search of hyper-parameters as follows: embedding size k ∈ {100, 200, 500, 1000}, batch size b ∈ {256, 512, 1024}, learning rate λ ∈ {0.00001, 0.00005, 0.0001, 0.0005}, fixed margin γ ∈ {3.0, 6.0, 9.0, 12.0, 18.0, 24.0}, negative sampling size n ∈ {128, 256, 512, 1024} and self-adversarial sampling temperature α ∈ {0.3, 0.5, 1.0}. Embeddings for each entity are initialized with a matrix with a size of 3 × k, and embeddings for each relation are initialized with a matrix with a size of 4 × k, and the rotation angle ψ is initialized between 0 and 2π. All parameters are randomly initialized from the interval [- 1 k , 1 k ]. No regularization is used since we find that the fixed margin γ could prevent QuatGE from over-fitting. The best hyper-parameters setting of QuatGE w.r.t the validation dataset on four benchmark datasets are summarized into Table 4.

Link prediction aims to predict the missing entity given a relation and another entity, i.e, inferring a head entity e _h given (r, e _t ) or inferring a tail entity e _t given (e _h , r). Link prediction results could be obtained from ranking the scores calculated by the score function f _r  (h, t) on test triples. In the link prediction task, we compare QuatGE to several previous state-of-the-art models, including TransE [6], ComplEx [19], ConvE [20], RotatE [11], TorusE [17], NagE [16] and QuatE [14]]. The empirical results on four benchmark datasets are reported in Tables 5 and 6.

As shown in Table 5, QuatGE performs better than its closely related embedding model QuatE on the FB15k dataset except MR, especially our model obtains significant improvements of 0.821 - 0.782 = 0.039 in MRR (which is about 4.987% relative improvement), and 73.2% -71.1 = 2.1 % absolute improvement in Hits@1. RotatE achieves high value on Hit@1. In addition, QuatGE outperforms all the baselines on all metrics on the WN18 dataset. The results also show that QuatGE can effectively model the symmetry, anti-symmetry and inversion patterns since they account for a large portion of the relations in these two datasets. As shown in Table 6, on the FB15k-237 dataset in which there are a large number of composition patterns, QuatE and QuatGE achieve a large performance gain over existing state-of-the-art models. On the WN18RR dataset where a number of symmetry relations exist, our model QuatGE is the first best. To further verify the modeling ability of QuatGE, we classify the relations in the FB15k-237 test set into three categories: symmetry, anti-symmetry and composition. The results of MRR for predicting head and tail entities w.r.t each relation category on FB15k-237 are summarized into Table 7. To confirm the superior representation capability of QuatGE in modelling different types of relation, we conduct a further analysis that compares the MRR performance of QuatGE to two previous models (RotatE and QuatE) for each relation on WN18RR, as listed in Table 8.

It can be seen from Table 7 that QuatGE can significantly improve the experimental results on the link prediction task, especially in modeling composition relations. As can be seen from Table 8, QuatGE is the best in many specific composition relations. Therefore, QuatGE is more focused on modeling the composition relations.

QuatGE outperforms the existing state-of-the-art models across most metrics. However, the uniqueness of identity in the quaternion group limits the modeling capacity of QuatGE. The reason is as follows: Modeling composition pattern, such as r₁ (x, y) ∧ r₁ (y, z) ⇒ r₁ (x, z) would happen. In the group formulation, G _{r 1}  ★ G _{r 1}  = G _{r 1} . Therefore, G _{r 1} is modeled as the identity in the quaternion group. Due to the uniqueness of identity, all relations that exhibit the above pattern will be modeled as the same identity element in the quaternion group. This certainly limits the modeling capacity of all models that can be formulated under the quaternion-group action perspective.