A quaternion-group knowledge graph embedding model

Abstract

Capturing the composite embedding representation of a multi-hop relation path is an extremely vital task in knowledge graph completion. Recently, rotation-based relation embedding models have been widely studied to embed composite relations into complex vector space. However, these models make some over-simplified assumptions on the composite relations, resulting the relations to be commutative. To tackle this problem, this paper proposes a novel knowledge graph embedding model, named QuatGE, which can provide sufficient modeling capabilities for complex composite relations. In particular, our method models each relation as a rotation operator in quaternion group-based space. The advantages of our model are twofold: (1) Since the quaternion group is a non-commutative group (i.e., non-Abelian group), the corresponding rotation matrices of composite relations can be non-commutative; (2) The model has a more expressive setting with stronger modeling capabilities, which is flexible to model and infer the complete relation patterns, including: symmetry/anti-symmetry, inversion and commutative/non-commutative composition. Experimental results on four benchmark datasets show that the proposed method outperforms the existing state-of-the-art models for link prediction, especially on composite relations.

Keywords

Knowledge graph embedding quaternion group link prediction

1 Introduction

Knowledge Graphs (KGs) play a vital role in solving Artificial Intelligence tasks including information retrieval [1], knowledge inference [2], question answering [3], data integration [4], recommender systems [5] and so on. Research on KGs is attracting more and more interests in academia and industry communities.

Although some large scale KGs contain millions of entities and billions of facts, they still might be far from complete due to missing links (relations) among entities. Hence, an increasing amount of recent works [6 –13] have devoted to complete KGs (i.e., link prediction) by learning a set of low-dimensional representation of entities and relations. The general purpose of these works is to model and infer the connectivity patterns in the KGs according to the existing facts. For example, some relations are symmetric (e.g., classmate) while others are anti-symmetric (e.g., filiation); some relations are the inverse of other relations (e.g., hypernym and hyponym); and some relations may be composed by others (e.g., my father’s wife is my mother).

Currently, rotation-based relation embedding models, e.g., RotatE [11], QuatE [14] and our previous work [7] (i.e., CapS-QuaR), have concerned these relation patterns, symmetry/anti-symmetry, inversion, and composition. However, it is ignored that some composite relations are non-commutative (Fig. 1(b)). Intuitively, these relation patterns have natural correspondence to notions in group theory [15]. In addition, non-Abelian group is applied to introduce non-commutative nature [16]. Quaternions enable expressive rotation in the three-dimensional space and have more degrees of freedom than rotation in complex plane (e.g., RotatE) [14]. Additionally, the Hamilton product of quaternions accords with the characteristics of non-Abelian group, which is as shown Eq.11 in this paper. Therefore, we propose QuatGE (Quaternion Group-based Embedding), which models each relation as a quaternion group-based rotation operator (Fig. 2(b)). Furthermore, QuatGE focus on the modeling of composite relations, accounting for their possible non-commutative nature.

Fig. 1

(a) A commutative composition relation; (b) A non-commutative composition relation.

Fig. 2

(a) In complex plane (e.g., RotatE), composite relations are assumed to be commutative. In addition, the rotation axis (perpendicular to the paper) is orthogonal to the entity embeddings. (b) In QuatGE model, each relation is modeled as a rotation operator R (Q) in the quaternion group-based space. A unit vector $\vec{v}$ denotes the direction of the axis of rotation, i.e., $\vec{v} = (v_{x}, v_{y}, v_{z}) = (sin θ cos ϕ, sin θ sin ϕ, cos θ)$ , where θ ∈ [0, π] and ϕ ∈ [0, 2π). An angle ψ represents the magnitude of the rotation about the rotation axis, where ψ ∈ [0, 2π) .

Specifically, our contributions are summarized as the following:

To the best of our knowledge, QuatGE is the first model that embeds each relation as a rotation into quaternion group-based space. The model can capture the composite embedding representation of multi-hop relations, accounting for possible non-commutative composite relations.

Our method has a more expressive setting with stronger modeling capabilities, which is flexible to model and infer the complete relation patterns, including: symmetry/anti-symmetry, inversion and commutative/non-commutative composition.

We evaluate our model QuatGE by link prediction task on four benchmark datasets. The experimental results show QuatGE outperforms the state-of-the-art results with significant improvements over strong baselines.

The remaining sections are organized as following: Section 2 mentions some related works of modeling composite relations; in Section 3, we briefly introduce background knowledge, and propose a new approach to obtain embeddings by modeling relational rotation using quaternion group; we present experimental results and analyses in Section 4; and conclude with future directions in Section 5.

2 Related work

From the group theory perspective, QuatGE may be related to the TorusE [17] and NagE [16] models. To deal with the compactness problem, TorusE model defines knowledge graph embedding as translations on a compact Lie group (i.e., n-torus). Moreover, TorusE focuses on the problem of regularization in TransE while QuatGE focuses on modeling and inferring multiple types of relation patterns. NagE, a group theory-based knowledge graph embedding framework that firstly attempts to apply non-Abelian group in modeling relational rotations, and empirical results show limited performance advance over previous methods.

From the perspective of modeling multi-hop relations (i.e., a relation path composed of a series of relations), QuatGE may be related to the TransE [6], the RotatE [11] and QuatE [14] models. TransE, a well-known Knowledge Graph Embedding (KGE) model that models each relation as a pure translational transformation and uses Eucleadian distance as score function. Specifically, TransE assumes a fixed addition composition pattern between relations (i.e., r₃ = r₁ + r₂), which is commutative and irrelevant to entity embeddings. In addition, TransE brings about r = 0 for symmetric relations, so it cannot model the symmetry relation pattern. RotatE models relations as rotational operator (rotation matrix) in the complex vector space, and it can effectively model all relation patterns (i.e., symmetry/anti-symmetry, inversion, and composition). To model a multi-hop relation path composed of multiple relations, RotatE uses Hadamard product to combine the rotation matrices of the relations i.e., r₃ = r₁ ∘ r₂, and all relations in the relation path have the same rotation axis (Fig. 2(a)). Thus, the composite relations in RotatE are also commutative. QuatE provides a more expressive model for composite relations and represents each relation type as a rotational operator in quaternion space (an extension of complex plane). However, QuatE applies the quaternion inner product (commutative) as the scoring function. Consequently, QuatE also cannot model the non-commutative composite relation pattern. In the QuatGE model, we use Axis–Angle representation to model each relation as a rotation operation in the quaternion group-based space, and take fully advantage of the natural correspondence between relation patterns and quaternion group notions for the first time. Moreover, QuatGE applies the Hamilton product (not commutative) of quaternions as the scoring function. Thus, QuatGE is flexible to model and infer the relation patterns, including: symmetry, anti-symmetry, inversion, commutative composition and non-commutative composition. A reasonable KGE model should be designed to accommodate various relation patterns existing in real world KGs, including the atomic relation patterns (inferable within one hop, i.e., symmetry, anti-symmetry and inversion) and the complex composition patterns (inferable within multi-hop). Compared to modeling atomic relation patterns, modeling complex composition patterns poses special challenges (e.g., commutative/non-commutative composition). In addition, the complex composition patterns are not always inferable by the multi-hop relations alone. For example, given that factual triplets (y, isElderBrotherOf, x) and (z, isYoungerBrotherOf, y), we can not infer whether x is elder or younger than z from the given facts. In fact, to figure out their relationships, we need to know more about x, y and z from their own attributes and their other relationships. As a contrast, our QuatGE model leverages rotation operation for relation modeling in the quaternion group-based space for the first time, which can effectively model all relation patterns, accounting for special challenges of modeling complex composition patterns. We summarize the capability of several models for modeling relation patterns, as shown in Table 1.

Table 1
Modeling capability of several models for relation patterns

Model Sym Ant Inv Com Non-com

TransE × ✓ ✓ ✓ ×

RotatE ✓ ✓ ✓ ✓ ×

QuatE ✓ ✓ ✓ ✓ ×

QuatGE ✓ ✓ ✓ ✓ ✓

Model	Sym	Ant	Inv	Com	Non-com
TransE	×	✓	✓	✓	×
RotatE	✓	✓	✓	✓	×
QuatE	✓	✓	✓	✓	×
QuatGE	✓	✓	✓	✓	✓

3 Background and method

In this section, we would firstly provide background knowledge, including definitions of relation patterns, the correspondence between relation patterns and group theory, problem formulation and quaternion group representation. Next, we would focus on modeling relational rotation using quaternion group. Then, score function and loss function are defined. Lastly, we would dicuss capability of our model in modeling relation patterns.

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}) \Rightarrow 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}) \Rightarrow \neg r (e_{j}, e_{i})$ (2)

Definition3 . Inversion. A relation r₁ is reverse to relation r₂ if ∀e_i, e_j $\begin{matrix} r_{1} (e_{i}, e_{j}) \Rightarrow r_{2} (e_{j}, e_{i}) \\ r_{2} (e_{i}, e_{j}) \Rightarrow r_{1} (e_{j}, e_{i}) \end{matrix}$ (3)

Definition4 . Commutative Composition. A relation r₃ is a commutative composition of relation r₁ and relation r₂ if $\forall e_{i}, e_{j}, e_{j}^{'}, e_{k}$ $\begin{matrix} r_{1} (e_{i}, e_{j}) \land r_{2} (e_{j}, e_{k}) \Rightarrow r_{3} (e_{i}, e_{k}) \\ r_{2} (e_{i}, e_{j}^{'}) \land r_{1} (e_{j}^{'}, e_{k}) \Rightarrow r_{3} (e_{i}, e_{k}) \end{matrix}$ (4)

Definition5 . Non-commutative Composition. A relation r₃ is a non-commutative composition of relation r₁ and relation r₂ if $\forall e_{i}, e_{j}, e_{j}^{'}, e_{k}$ $\begin{matrix} r_{1} (e_{i}, e_{j}) \land r_{2} (e_{j}, e_{k}) \Rightarrow r_{3} (e_{i}, e_{k}) \\ r_{2} (e_{i}, e_{j}^{'}) \land r_{1} (e_{j}^{'}, e_{k}) ≱ r_{3} (e_{i}, e_{k}) \end{matrix}$ (5) where e_i, e_j, $e_{j}^{'}$ and e_k denote different entities in a KG.

3.2 Group and relation modeling

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.

Table 2
The correspondence between relation patterns and group theory

Relation Pattern Group Example

Symmetry $G_{r} = G_{r}^{- 1}$ r = isClassmateOf

Anti-symmetry $G_{r} \neq G_{r}^{- 1}$ r = isFiliationOf

Inversion $G_{r_{1}} = G_{r_{2}}^{- 1}$ r₁ = isHypernymOf, r₂ = isHyponymOf

Commutative Composition Abelian Group r₁ = r₂ = r₃ = isElderBrotherOf

r₁ ★ r₂ = r₂ ★ r₁ = r₃ = isElderBrotherOf

Non-commutative Composition Non-Abelian Group r₁ = isMotherOf, r₂ = isFatherOf

r₁ ★ r₂ = r₃ = isGrandmotherOf

r₂ ★ r₁ = isGrandfatherOf ≠ r₁ ★ r₂

Relation Pattern	Group	Example
Symmetry	$G_{r} = G_{r}^{- 1}$	r = isClassmateOf
Anti-symmetry	$G_{r} \neq G_{r}^{- 1}$	r = isFiliationOf
Inversion	$G_{r_{1}} = G_{r_{2}}^{- 1}$	r₁ = isHypernymOf, r₂ = isHyponymOf
Commutative Composition	Abelian Group	r₁ = r₂ = r₃ = isElderBrotherOf
		r₁ ★ r₂ = r₂ ★ r₁ = r₃ = isElderBrotherOf
Non-commutative Composition	Non-Abelian Group	r₁ = isMotherOf, r₂ = isFatherOf
		r₁ ★ r₂ = r₃ = isGrandmotherOf
		r₂ ★ r₁ = isGrandfatherOf ≠ r₁ ★ r₂

3.3 Problem formulation

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: $\begin{matrix} \bar{Q} = q_{0} - q_{1} i - q_{2} j - q_{3} k \\ Q \bar{Q} = q_{0}^{2} + q_{1}^{2} + q_{2}^{2} + q_{3}^{2} \end{matrix}$ (6)Quaternion Modulus : The modulus of a quaternion is defined as follows: $| Q | = | \bar{Q} | = \sqrt{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: $\begin{matrix} {QQ}^{- 1} = Q^{- 1} Q = 1 \\ Q^{- 1} = \frac{\bar{Q}}{| Q |^{2}} = \frac{\bar{Q}}{q_{0}^{2} + q_{1}^{2} + q_{2}^{2} + q_{3}^{2}} \end{matrix}$ (8)Unit Quaternion : The properties of unit quaternions are as follows: $\begin{matrix} Q^{- 1} = \bar{Q} \\ | Q |^{2} = q_{0}^{2} + q_{1}^{2} + q_{2}^{2} + q_{3}^{2} = 1 \end{matrix}$ (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: $\begin{matrix} Q_{1} + Q_{2} = (q_{0} + q_{0}^{'}) + (q_{1} + q_{1}^{'}) i \\ + (q_{2} + q_{2}^{'}) j + (q_{3} + q_{3}^{'}) k \end{matrix}$ (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: $\begin{matrix} Q_{1} \circ 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} \circ Q_{2} \neq Q_{2} \circ Q_{1} \end{matrix}$ (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.

3.5 Modeling relational rotation using quaternion 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 $\vec{v}$ represents the direction of the rotation axis, i.e., $\vec{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 $\vec{w_{e}}$ with the coordinate (x, y, z), its rotation about axis $\vec{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 $\vec{v}$ (i.e., the aforementioned axis) can be defined using an extension of Euler’s formula: $\begin{matrix} Q & = e^{\frac{ψ}{2} (v_{x} i + v_{y} j + v_{z} k)} \\ = cos \frac{ψ}{2} + sin \frac{ψ}{2} (v_{x} i + v_{y} j + v_{z} k) \\ = cos \frac{ψ}{2} + v_{x} sin \frac{ψ}{2} i + v_{y} sin \frac{ψ}{2} j + v_{z} sin \frac{ψ}{2} k \end{matrix}$ (13)

A 3-D Euclidean vector $\vec{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 $\vec{w_{e}}$ after the rotation through an angle of ψ around a unit vector $\vec{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 \circ Q_{w} \circ Q^{- 1}$ (14) where Q^-1 is the inverse of Q, i.e., $Q^{- 1} = e^{- \frac{ψ}{2} (v_{x} i + v_{y} j + v_{z} k)}$ $= cos \frac{ψ}{2} - sin \frac{ψ}{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: ${\vec{w_{e}}}^{'} = R (Q) \vec{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. $\begin{array}{l} R (Q) = e^{\vec{v} ψ} = I + [\begin{matrix} 0 & - v_{z} & v_{y} \\ v_{z} & 0 & - v_{x} \\ - v_{y} & v_{x} & 0 \end{matrix}] \sin ψ + {[\begin{matrix} 0 & - v_{z} & v_{y} \\ v_{z} & 0 & - v_{x} \\ - v_{y} & v_{x} & 0 \end{matrix}]}^{2} (1 - \cos ψ) \\ = [\begin{matrix} 1 & - v_{z} \sin ψ & v_{y} \sin ψ \\ v_{z} \sin ψ & 1 & - v_{x} \sin ψ \\ - v_{y} \sin ψ & v_{x} \sin ψ & 1 \end{matrix}] + [\begin{matrix} - 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} \end{matrix}] (1 - \cos ψ) \\ = [\begin{matrix} \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 ψ) \end{matrix}] \end{array}$ (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., $\vec{v_{1}} = \vec{v_{2}}$ ), which can be seen from Eq.11. Therefore, both commutative and non-commutative relation patterns can be modelled in our model.

3.6 Score function and loss function

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_iR (r_i) and $h_{i} = t_{i} R (r_{i}^{- 1})$ , where $r_{i} \in ℍ$ , h_i, $t_{i} \in ℝ^{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]. $\begin{array}{l} L = - \log σ (f_{r} (h, t) + γ) \\ - \sum_{i = 1}^{n} p (e_{h i^{'}}, r, e_{t i^{'}}) \log σ (- f_{r} (h_{i^{'}}, t_{i^{'}}) - γ) \end{array}$ (18)

3.7 Capability of QuatGE in modeling relation patterns

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 Experiments

In this section, the experimental datasets and evaluation metrics would firstly be provided, and then implementation details would be described. Lastly, we would report the link prediction results and analysis.

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.

Table 3
Statistics of the datasets used in this paper

Dataset #entity #relation #training #validation #test

WN18 40943 18 141442 5000 5000

WN18RR 40943 11 86835 3034 3134

FB15k 14951 1345 483142 50000 59071

FB15k-237 14541 237 272115 17535 20466

Dataset	#entity	#relation	#training	#validation	#test
WN18	40943	18	141442	5000	5000
WN18RR	40943	11	86835	3034	3134
FB15k	14951	1345	483142	50000	59071
FB15k-237	14541	237	272115	17535	20466

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.

4.2 Implementation details

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 [- $\frac{1}{\sqrt{k}}$ , $\frac{1}{\sqrt{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.

Table 4
The best hyper-parameters setting of QuatGE on the four benchmark datasets

Dataset Embedding Dimension k Batch Size b Negative Samples n α γ

WN18 200 512 512 0.3 12.0

WN18RR 200 512 512 0.5 6.0

FB15k 500 1024 128 1.0 24.0

FB15k-237 500 1024 256 1.0 9.0

Dataset	Embedding Dimension k	Batch Size b	Negative Samples n	α	γ
WN18	200	512	512	0.3	12.0
WN18RR	200	512	512	0.5	6.0
FB15k	500	1024	128	1.0	24.0
FB15k-237	500	1024	256	1.0	9.0

4.3 Results and analysis

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.

Table 5
Link prediction results on FB15K and WN18

FB15K WN18

Model MR MRR H@1 H@3 H@10 MR MRR H@1 H@3 H@10

TransE - 0.463 0.297 0.578 0.749 - 0.495 0.113 0.888 0.943

ComplEx - 0.692 0.599 0.759 0.840 - 0.941 0.936 0.945 0.947

ConvE 51 0.657 0.558 0.723 0.831 374 0.943 0.935 0.946 0.956

TorusE - 0.733 0.674 0.771 0.832 - 0.947 0.943 0.950 0.954

RotatE 40 0.797 0.746 0.830 0.884 309 0.949 0.944 0.952 0.959

NagE - 0.791 0.734 0.831 0.886 - 0.950 0.944 0.954 0.960

QuatE 17 0.782 0.711 0.835 0.900 162 0.950 0.945 0.954 0.959

QuatGE 30 0.821 0.732 0.852 0.907 158 0.953 0.949 0.957 0.960

FB15K	WN18
TransE	-	0.463	0.297	0.578	0.749	-	0.495	0.113	0.888	0.943
ComplEx	-	0.692	0.599	0.759	0.840	-	0.941	0.936	0.945	0.947
ConvE	51	0.657	0.558	0.723	0.831	374	0.943	0.935	0.946	0.956
TorusE	-	0.733	0.674	0.771	0.832	-	0.947	0.943	0.950	0.954
RotatE	40	0.797	0.746	0.830	0.884	309	0.949	0.944	0.952	0.959
NagE	-	0.791	0.734	0.831	0.886	-	0.950	0.944	0.954	0.960
QuatE	17	0.782	0.711	0.835	0.900	162	0.950	0.945	0.954	0.959
QuatGE	30	0.821	0.732	0.852	0.907	158	0.953	0.949	0.957	0.960

Results of TransE are taken from [22]. Other results are taken from the corresponding original papers.

Table 6

Link prediction results on FB15K-237 and WN18RR

FB15K-237						WN18RR
Model	MR	MRR	H@1	H@3	H@10	MR	MRR	H@1	H@3	H@10
TransE	357	0.294	-	-	0.465	3384	0.226	-	-	0.501
ComplEx	339	0.247	0.158	0.275	0.428	5261	0.440	0.410	0.460	0.510
ConvE	244	0.325	0.237	0.356	0.501	4187	0.430	0.400	0.440	0.520
RotatE	177	0.338	0.241	0.375	0.533	3340	0.476	0.428	0.492	0.571
NagE	-	0.340	0.243	0.376	0.532	-	0.476	0.429	0.493	0.575
QuatE	87	0.348	0.248	0.382	0.550	2314	0.488	0.438	0.508	0.582
QuatGE	112	0.350	0.242	0.384	0.550	2263	0.494	0.440	0.510	0.586

Results of TransE are taken from [23]. Results of ComplEx are taken from [20]. Other results are taken from the corresponding original papers.

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.

Table 7

MRR for predicting head and tail entities w.r.t relation patterns on FB15K-237

	Predicting Head (? , r, e_t)			Predicting Tail (e_h, r, ?)
Relation Pattern	RotatE	QuatE	QuatGE	RotatE	QuatE	QuatGE
Symmetry	0.494	0.497	0.500	0.464	0.485	0.487
Anti-symmetry	0.483	0.487	0.485	0.486	0.490	0.491
Composition	0.278	0.292	0.308	0.285	0.296	0.318

Table 8

MRR comparison on each relation type of WN18RR

Relation Type	Relation Name	RotatE	QuatE	QuatGE
Atomic	similar_to	1.000	1.000	1.000
	verb_group	0.943	0.924	0.940
	also_see	0.585	0.629	0.641
	derivationally_related_form	0.947	0.953	0.955
Composite	member_of_domain_usage	0.318	0.441	0.445
	member_of_domain_region	0.200	0.193	0.392
	synset_domain_topic_of	0.341	0.468	0.469
	instance_hypernym	0.318	0.364	0.372
	has_part	0.184	0.233	0.235
	member_meronym	0.232	0.232	0.239
	hypernym	0.148	0.173	0.180

Results of RotatE and QuatE are taken from [14].

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
₁} ★ G_{r
₁} = G_{r
₁}. Therefore, G_{r
₁} 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.

5 Conclusion

In this paper, we propose QuatGE, a knowledge graph embedding model which operates in the quaternion group-based space. In the QuatGE model, we use Axis–Angle representation to model each relation as a rotation operation in the quaternion group-based space, the rotation operation is encoded by a unit quaternion with three degrees of freedom (i.e., θ, ϕ and ψ). We take fully advantage of the natural correspondence between relation patterns and quaternion group notions for the first time in the QuatGE model. Moreover, QuatGE applies the Hamilton product (not commutative) of quaternions as the scoring function. Therefore, QuatGE is advantageous with its capability in modelling several pivotal relation patterns, expressing with higher degrees of freedom as well as its good generalization. In our experiments, we evaluate our model QuatGE by link prediction task on four benchmark datasets. The experimental results show that QuatGE achieves consistent and significant improvements compared to the state-of-the-art baselines. In the future, we will consider overcoming the uniqueness of identity in the quaternion group to improve the modeling capacity of QuatGE.

Footnotes

Acknowledgment

This work was supported by the National Natural Science Foundation of China (No.61976032 and No.61806038), the Scientific Research Funding Project of Education Department of Liaoning Province (No.2020JYT03) and the Innovative Talents in Colleges and Universities of Liaoning Province (No.WR2019005).

References

Dietz

, Kotov

and Meij

, Utilizing knowledge graphs for text-centric information retrieval, In The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval, 2018, 1387–1390.

Bansal

, Juan

D.C.

, Ravi

and McCallum

, A2N: attending to neighbors for knowledge graph inference, In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, 2019, 4387–4392.

Huang

, Zhang

, Li

and Li

, Knowledge graph embedding based question answering, In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, 2019, 105–113.

Jozashoori

and Vidal

M.E.

, MapSDI: A Scaled-Up Semantic Data Integration Framework for Knowledge Graph Creation, In OTM Confederated International ConferencesOn theMove toMeaningful Internet Systems, 2019, 58–75.

Zhou

, Zhao

W.X.

, Bian

, Zhou

, Wen

J.R.

and Yu

, Improving Conversational Recommender Systems via Knowledge Graph based Semantic Fusion, In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2020, 1006–1014.

Bordes

, Usunier

, Garcia-Duran

, Weston

and Yakhnenko

, Translating embeddings for modeling multi-relational data, In Advances in neural information processing systems, 2013, 2787–2795.

Chen

, Wang

, Li

and Shi

, A Quaternion-embedded Capsule Network Model for Knowledge Graph Completion, IEEE Access 8 (2020), 100890–100904.

, Nguyen

T.D.

, Nguyen

D.Q.

and Phung

, A capsule network-based embedding model for knowledge graph completion and search personalization, In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), 2019, 2180–2189.

Moon

, Jones

and Samatova

N.F.

, Learning entity type embeddings for knowledge graph completion, In Proceedings of the 2017 ACM Conference on Information and Knowledge Management, 2017, 2215–2218.

10.

Wang

, Zhang

, Feng

and Chen

, Knowledge graph embedding by translating on hyperplanes, In Aaai, 2014, 1112–1119.

11.

Sun

, Deng

Z.-H.

, Nie

J.-Y.

and Tang

, Rotate: Knowledge graph embedding by relational rotation in complex space, In ICLR, 2019, 1–18.

12.

Lin

, Liu

, Sun

, Liu

and Zhu

, Learning Entity and Relation Embeddings for Knowledge Graph Completion, In Aaai, 2015, 2181–2187.

13.

, He

, Xu

, Liu

and Zhao

, Knowledge graph embedding via dynamic mapping matrix, In Proceedings of the 53rd annual meeting of the association for computational linguistics and the 7th international joint conference on natural language processing (volume 1: Long papers), 2015, 687–696.

14.

Zhang

, Tay

, Yao

and Liu

, Quaternion knowledge graph embeddings, In Advances in Neural Information Processing Systems, 2019, 2735–2745.

15.

Cai

, Group Representation Theory for Knowledge Graph Embedding, 2019, arXiv preprint arXiv:1909.05100.

16.

Yang

, Sha

and Hong

, AGroup-Theoretic Framework for Knowledge Graph Embedding, 2020, arXiv preprint arXiv:2005.10956.

17.

Ebisu

and Ichise

, Toruse: Knowledge graph embedding on a lie group, In Aaai, 2018, 1819–1826.

18.

Dai

J.S.

, Euler–Rodrigues formula variations, quaternion conjugation and intrinsic connections, Mechanism and Machine Theory 92 (2015), 144–152.

19.

Trouillon

, Welbl

, Riedel

, Gaussier

É.

and Bouchard

, Gaussier and G. Bouchard, Complex embeddings for simple link prediction, International Conference on Machine Learning (ICML), 2016, 2071–2080.

20.

Dettmers

, Minervini

, Stenetorp

and Riedel

, Convolutional 2d knowledge graph embeddings, 2017, arXiv preprint arXiv:1707.01476.

21.

Toutanova

and Chen

, Observed Versus Latent Features for Knowledge Base and Text Inference, In Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionality, 2015, 57–66.

22.

Nickel

, Rosasco

and Poggio

, Holographic embeddings of knowledge graphs, 2015, arXiv preprint arXiv:1510.04935.

23.

Nguyen

D.Q.

, Nguyen

T.D.

and Phung

, A novel embedding model for knowledge base completion based on convolutional neural network, 2017, arXiv preprint arXiv:1712.02121.

A quaternion-group knowledge graph embedding model

Abstract

Keywords

1 Introduction

Table 1 Modeling capability of several models for relation patterns Model Sym Ant Inv Com Non-com TransE × ✓ ✓ ✓ × RotatE ✓ ✓ ✓ ✓ × QuatE ✓ ✓ ✓ ✓ × QuatGE ✓ ✓ ✓ ✓ ✓

3.1 Relation pattern

3.4 Quaternion group representation

4 Experiments

4.1 Datasets and evaluation metrics

Table 3 Statistics of the datasets used in this paper Dataset #entity #relation #training #validation #test WN18 40943 18 141442 5000 5000 WN18RR 40943 11 86835 3034 3134 FB15k 14951 1345 483142 50000 59071 FB15k-237 14541 237 272115 17535 20466

Table 4 The best hyper-parameters setting of QuatGE on the four benchmark datasets Dataset Embedding Dimension k Batch Size b Negative Samples n α γ WN18 200 512 512 0.3 12.0 WN18RR 200 512 512 0.5 6.0 FB15k 500 1024 128 1.0 24.0 FB15k-237 500 1024 256 1.0 9.0

Footnotes

Acknowledgment

References

Table 1
Modeling capability of several models for relation patterns

Model Sym Ant Inv Com Non-com

TransE × ✓ ✓ ✓ ×

RotatE ✓ ✓ ✓ ✓ ×

QuatE ✓ ✓ ✓ ✓ ×

QuatGE ✓ ✓ ✓ ✓ ✓

Table 3
Statistics of the datasets used in this paper

Dataset #entity #relation #training #validation #test

WN18 40943 18 141442 5000 5000

WN18RR 40943 11 86835 3034 3134

FB15k 14951 1345 483142 50000 59071

FB15k-237 14541 237 272115 17535 20466

Table 4
The best hyper-parameters setting of QuatGE on the four benchmark datasets

Dataset Embedding Dimension k Batch Size b Negative Samples n α γ

WN18 200 512 512 0.3 12.0

WN18RR 200 512 512 0.5 6.0

FB15k 500 1024 128 1.0 24.0

FB15k-237 500 1024 256 1.0 9.0