# Knowledge Graph Representation via Similarity-Based Embedding

Authors: Zhen Tan; Xiang Zhao; Yang Fang; Bin Ge; Weidong Xiao
Journal: Scientific Programming
 (2018)

---

## Abstract

Knowledge graph, a typical multi-relational structure, includes large-scale facts of the world, yet it is still far away from completeness. Knowledge graph embedding, as a representation method, constructs a low-dimensional and continuous space to describe the latent semantic information and predict the missing facts. Among various solutions, almost all embedding models have high time and memory-space complexities and, hence, are difficult to apply to large-scale knowledge graphs. Some other embedding models, such asTransE andDistMult, although with lower complexity, ignore inherent features and only use correlations between different entities to represent the features of each entity. To overcome these shortcomings, we present a novel low-complexity embedding model, namely,SimE-ER, to calculate the similarity of entities in independent and associated spaces. InSimE-ER, each entity (relation) is described as two parts. The entity (relation) features in independent space are represented by the features entity (relation) intrinsically owns and, in associated space, the entity (relation) features are expressed by the entity (relation) features they connect. And the similarity between the embeddings of the same entities in different representation spaces is high. In experiments, we evaluate our model with two typical tasks: entity prediction and relation prediction. Compared with the state-of-the-art models, our experimental results demonstrate thatSimE-ER outperforms existing competitors and has low time and memory-space complexities.


---

## Body

## 1. Introduction

Knowledge graph (KG), as an important part of the artificial intelligence, is playing an increasingly more essential role in different domains [1]: question answer system [2, 3], information retrieval [4], semantic parsing [5], named entity disambiguation [6], biological data mining [7, 8], and so on [9, 10]. In knowledge graphs, facts can be denoted as instances of binary relations (e.g.,PresidentOf (DonaldTrump, American)). Nowadays, a great number of knowledge graphs, such as WordNet [11], Freebase [12], DBpedia [13], YAGO [14], and NELL [15] usually do not appear simultaneously. Instead, they were constructed to describe the structured information in various domains [16], and all of them are fairly sparse.Knowledge representation learning [17–19] is considered as an important task to extract the latent features from associated space. Recently, knowledge embedding [20, 21], an effective method of feature extraction [22], was proposed to compress a high-dimensional and sparse space into a low-dimensional and continuous space. Knowledge embedding can be used to derive new unknown facts from known knowledge bases (e.g., link prediction) and to determine whether a triplet is correct or not (e.g., triplets classification) [23]. Moreover embedding representation [24] has been used to support question answer systems [25] and machine reading [26]. However, almost all embedding models only use the features and attributes in knowledge graph to represent entities and relations, which omits the fact that entities and relations are projections of the facts in independent space. Besides, almost all of them have high time and memory-space complexities and cannot be used in large-scale knowledge graphs.In this research, we propose a novel similarity-based knowledge embedding model, namely,SimE-ER, which calculates the entity and relation similarities between two spaces (independent and associated spaces). A sketch of the model framework is provided in Figure 1. The basic idea of this paper is that independent and associated spaces are used to represent the irrelevant and interconnected entities (relations) features, respectively. In independent space, the features of entities (relations) are independent and irrelevant. By contrast, the features of entities (relations) in associated space are interconnected and interacting, and the entities and relations can be denoted by the entities and relations connected with them. Plus, the similarities of the same entities (relations) with different spaces are high. In Figure 1, we can see that, in independent space, the features of e1 are only constructed by themselves, but, in associated spaces, the entity e1¯ is denoted by other entities and relations which can be described as blue points (lines). We want the features of e1 in independent and associated spaces to be similar. Besides, vector embedding is used to represent knowledge graphs.Figure 1
Framework of our model.In associated space, take as an example the entity whichSteve Jobs has multiple triplets, such as (Steve Jobs, Apple Inc., FoundOf), (Steve Jobs, America, Nationality), and (Steve Jobs, Laurene Powell, CoupleOf). If we combine all corrupt triplets with the same missing entity, such as (…, Apple Inc., FoundOf), (…, America, Nationality), and (…, Laurene Powell, Couple), it is easy to locate that the missing entity e¯3 isSteve Jobs. Similarly, if we combine all the corrupt triplets with the same relation, such as (Steve Jobs, Apple Inc.,…), (Jack Ma, Alibaba, …), and (Sundar Pichai, Google, …), we can obtain that the missing relation r¯1 isFoundOf. The scenario is shown in Figure 2. Hence using correlation between different entities to represent features is an effective method. However, in practice, it is unsuitable to only use the correction between different entities and omit the inherent features entities have, such as the attributes of each entity which are hard to represent with the correlations between different entities. Therefore, we construct the independent space which can preserve the inherent features each entity has. We combine both independent and associated spaces to represent overall features of entities and relations, which can in turn represent the knowledge graph more comprehensively. The motivation of employing both types of spaces is to model correlation while reserving individual specificity.Figure 2
Motivation in associated space.Compared with other embedding models, vector embedding has evident advantages on time and memory-space complexities. We evaluateSimE-E andSimE-ER on the popular tasks of entity prediction and relation prediction. The experiment results validate the competitive results achieved by the proposed method compared with previous models.Contributions. To summarize, the main contributions of this paper are as follows:(i)
We propose a similarity-based embedding model, namely,SimE-ER. InSimE-ER, we consider the entity and relation similarities of different spaces simultaneously, which can extract the features of entities and relations comprehensively.(ii)
Compared with other embedding models, our model has lower time and space complexity, which improves the effectiveness of processing large-scale knowledge graphs.(iii)
Through thorough experiments on real-life datasets, our approach is demonstrated to outperform the existing state-of-the-art models in entity prediction and relation prediction tasks.Organization. We discuss related work in Section 2 and then introduce our method, along with the theoretical analysis, in Section 3. Afterwards, experimental studies are presented in Section 4, followed by conclusion in Section 5.


## 2. Related Work

In this section, we introduce several related works [19] published in recent years which get the state-of-the-art results. According to the relation features, we divide embedding models into two parts: matrix-based embedding models [27] and vector-based embedding models [28].


### 2.1. Matrix-Based Embedding Models

In this part, matrices (tensors) are used to describe relation features.Structured Embedding. Structured Embedding Model (SE) [29] considers that head and tail entities are overlapping in a specific-relation space Rn where the triplet (h,r,t) exists. It uses two mapping matrices Mrh and Mrt to extract feature from h and t.Single Layer Model. Compared withSE, Single Layer Model (SLM) [30] uses a nonlinear activation function to translate the extracted features and considers the features after activation to be orthogonal with relation features. The extracted features are comprised of the entities’ features after mapping and a bias of their relation.Neural Tensor Network. Neural Tensor Network (NTN) [30, 31] is a more complex model and considers that the tensor can be regarded as better feature extractor compared with matrices.Semantic Matching Energy. The basic idea of Semantic Matching Energy (SME) [32] is that if the triplet is correct, the feature of head entity and tail entity is orthogonal. Similar toSLM, the features of head (tail) entity are comprised of the entities’ features after mapping and a bias of their relation. There are two methods to extract features, i.e., linear and nonlinear.Latent Factor Model. Latent Factor Model (LFM) [33, 34] assumes that features of head entity are orthogonal with those of tail entity when the head entity is mapped in specific-relation space. Its score function can be defined as fr(h,t)=hTMrt, where h, Mr, t denote the features of head entity, relation, and tail entity, respectively.


### 2.2. Vector-Based Embedding Models

In this part, relations are described as vector rather than matrix to improve the effectiveness of representation models.Translation-Based Model. The basic idea of translation-based model,TransE [23, 35, 36], is that the relation r is a translation vector between h and t. The score function is fr(h,t)=h+r-tL1/L2, where h, r, and t denote the head entity, relation, and tail entity embeddings, respectively. BecauseTransE only processes simple relations, other translation-based models [37–39] are proposed to improveTransE.Combination Embedding Model. CombinE [40] describes the relation features with theplus andminus combination of each pair. Compared with other translation-based models,CombinE can represent relation features in a more comprehensive way.Bilinear-Diag Model. DistMult [41] uses a formulation of bilinear model to represent entities and relations and utilizes the learned embedding to extract logical rules.Holographic Embedding Model. HOLE [42] utilizes a compositional vector space based on the circular correlation of vectors, which creates fixed-width representations. The compositional representation has the same dimensionality as the representation of its constituents.Complex Embedding Model. ComplEx [43] divides entities and relations into two parts, i.e., real part and imaginary part. Real part denotes the features of symmetric relation, and imaginary part denotes the features of asymmetric relations.Project Embedding Model. ProjE [44], a shared variable neural network model, uses two-diagonal matrix to extract the entity and relation features and calculate the similarity between features and candidate entity. In training, the correct triplets have high similarity.Convolutional Embedding Model. ConvE [45] transfers the features into2D space and uses convolutional neural network to extract the entity and relation features.Compared with matrix-based embedding models, vector-based models have obviously advantages on time and memory-space complexities. In these vector-based models,TransE is a classical baseline and has been applied on many applications,TransR is an improved method ofTransE which solves the complex relation types, andDistMult andComplEx use probability-based method to represent knowledge and achieve state-of-the-art results.


## 2.1. Matrix-Based Embedding Models

In this part, matrices (tensors) are used to describe relation features.Structured Embedding. Structured Embedding Model (SE) [29] considers that head and tail entities are overlapping in a specific-relation space Rn where the triplet (h,r,t) exists. It uses two mapping matrices Mrh and Mrt to extract feature from h and t.Single Layer Model. Compared withSE, Single Layer Model (SLM) [30] uses a nonlinear activation function to translate the extracted features and considers the features after activation to be orthogonal with relation features. The extracted features are comprised of the entities’ features after mapping and a bias of their relation.Neural Tensor Network. Neural Tensor Network (NTN) [30, 31] is a more complex model and considers that the tensor can be regarded as better feature extractor compared with matrices.Semantic Matching Energy. The basic idea of Semantic Matching Energy (SME) [32] is that if the triplet is correct, the feature of head entity and tail entity is orthogonal. Similar toSLM, the features of head (tail) entity are comprised of the entities’ features after mapping and a bias of their relation. There are two methods to extract features, i.e., linear and nonlinear.Latent Factor Model. Latent Factor Model (LFM) [33, 34] assumes that features of head entity are orthogonal with those of tail entity when the head entity is mapped in specific-relation space. Its score function can be defined as fr(h,t)=hTMrt, where h, Mr, t denote the features of head entity, relation, and tail entity, respectively.


## 2.2. Vector-Based Embedding Models

In this part, relations are described as vector rather than matrix to improve the effectiveness of representation models.Translation-Based Model. The basic idea of translation-based model,TransE [23, 35, 36], is that the relation r is a translation vector between h and t. The score function is fr(h,t)=h+r-tL1/L2, where h, r, and t denote the head entity, relation, and tail entity embeddings, respectively. BecauseTransE only processes simple relations, other translation-based models [37–39] are proposed to improveTransE.Combination Embedding Model. CombinE [40] describes the relation features with theplus andminus combination of each pair. Compared with other translation-based models,CombinE can represent relation features in a more comprehensive way.Bilinear-Diag Model. DistMult [41] uses a formulation of bilinear model to represent entities and relations and utilizes the learned embedding to extract logical rules.Holographic Embedding Model. HOLE [42] utilizes a compositional vector space based on the circular correlation of vectors, which creates fixed-width representations. The compositional representation has the same dimensionality as the representation of its constituents.Complex Embedding Model. ComplEx [43] divides entities and relations into two parts, i.e., real part and imaginary part. Real part denotes the features of symmetric relation, and imaginary part denotes the features of asymmetric relations.Project Embedding Model. ProjE [44], a shared variable neural network model, uses two-diagonal matrix to extract the entity and relation features and calculate the similarity between features and candidate entity. In training, the correct triplets have high similarity.Convolutional Embedding Model. ConvE [45] transfers the features into2D space and uses convolutional neural network to extract the entity and relation features.Compared with matrix-based embedding models, vector-based models have obviously advantages on time and memory-space complexities. In these vector-based models,TransE is a classical baseline and has been applied on many applications,TransR is an improved method ofTransE which solves the complex relation types, andDistMult andComplEx use probability-based method to represent knowledge and achieve state-of-the-art results.


## 3. Similarity-Based Model

Given a training setS+ of triplets, each triplet (h,r,t) has two entities h,t∈E (the set of entities) and relationship r∈R (the set of relationship). Our model learns the entities embeddings (hi, ti, ha, ta) and relationship embeddings (ri, ra) to represent the feature of entities and relations, where the subscripts i, a denote the independent and associated space. The entity embedding and relation embedding take value in Rd, where d is the dimension of entity and relation embedding spaces.


### 3.1. Our Models

The basic idea of our model is that, for each entity (relation), the features are divided into two parts. The first part describes inherent features of entities (relations) in independent space. The feature embedding vectors can be denoted ashi, ri, ti. The second part signs triplet features in associated space, and the feature embedding vectors can be denoted as ha, ra, ta. In independent space, the feature vectors are described as the inherent features entities (relations) have. In associated space, the features of ha are comprised of other entities and relations which connect with entity ha.The entities (relations) in associated space are projections of entities (relations) in independent space. Hence the representation features of the same entity in independent and associated space are similar, while the representation features of different entities are not similar. The formula can be described as follows:(1)hi≈ra⊙ta,(2)ri≈ha⊙ta,(3)ti≈ha⊙ra,where ⊙ denotes element-wise product. In detail, in (1), if we combine the features of ra and ta, we can obtain part of the hi features. That is to say, the hi features are similar with ra⊙ta. In this paper, we useCosine to calculate the similarity between different spaces. Taking head entity as an example, theCosine similarity between different spaces can be denoted as(4)cos⁡hi,ra⊙ta=Dothi,ra⊙tahira⊙ta=Sumhi⊙ra⊙tahira⊙tawhereDot denotes the dot-product andSum denotes the summation over the vector element. Sum(hi⊙ra⊙ta) calculates the similarity, and hi  ra⊙ta constrain the length of features. To reduce the training complexity, we just consider the numerator and use regularization items to replace the denominator. Hence the similarity of head entity features in independent and graph spaces can be described as(5)Simh=Sumhi⊙ra⊙ta. We expect that the value of hi⊙ra⊙ta is larger when hi and ra⊙ta denote the same head entity, while the value of hi⊙ra⊙ta is smaller otherwise.To represent entities in a more comprehensive way, we consider the similarity of head and tail entities simultaneously. The score function can be denoted as(6)Simh,t=Simh+Simt=Sumhi⊙ra⊙ta+Sumha⊙ra⊙ti. The embedding model based on the similarity of head and tail entities is named asSimE-E.On the basis of entity similarity, we need to consider relation similarity, which can enhance the representation of relation features. The comprehensive model, which considers all the similarities of entity (relation) features in different spaces, can be described as(7)Simh,r,t=Simh+Simr+Simt=Sumhi⊙ra⊙ta+Sumha⊙ri⊙ta+Sumha⊙ra⊙ti.The embedding model based on the similarity of entity and relation is named asSimE-ER.


### 3.2. Training

To learn the proposed embedding and encourage the discrimination between golden triplets and incorrect triplets, we minimize the following logistic ranking loss function over the training set:(8)L=∑h,r,t∈Slog⁡1+exp⁡-YhrtSimh,r,t;Θ, where Θ corresponds to the embeddings hi, ha, ri, ra, ti, ta∈Rd and Yhrt is a label of triplet. Yhrt=1 denotes that (h,r,t) is positive and Yhrt=-1 denotes that (h,r,t) is negative. S is a triplets set [28] which contains both positive triplets set S+ and negative triplets set S-.(9)S-=h′,r,t∣h′∈E∪h,r,t′∣t′∈E∪h,r′,t∣r′∈R.The set of negative triplets, constructed according to (9), is composed of training triplets with either head (tail) entity or relation replaced by a random entity or relation. Only one entity or relation is replaced for each corrupted triplet with the same probability. To prevent overfitting, some constraints are considered when minimizing the loss function L:(10)∀hi,ti∈E,ri∈R,hi=1,ri=1,ti=1,∀ha,ta∈E,ra∈R,ha⊙ra=1,ha⊙ta=1,ra⊙ta=1.Equation (10) is to constrain the length of entity (relation) features forSimE-E andSimE-ER. We convert it to the following loss function by means of soft constraints:(11)L=∑h,r,t∈Slog⁡1+exp⁡-YhrtSimh,r,t;Θ+λΘ22,where λ is a hyperparameter to weigh the importance of soft constraints. We utilize the improved stochastic gradient descent (Adagrad) [46] to train the models. Comparing withSGD,Adagrad shrinks learning rate effectively when the number of iterations increases, which means that it is insensitive to learning rate.


### 3.3. Comparison with Existing Models

To compare the time and memory-space complexities between different models, we show the results in Table1, where d represents the dimension of entity and relation embeddings, k is the number of tensor’s slices, and ne and nr are the numbers of entities and relations, respectively.Table 1
Complexities of representation models.
Model Relation Parameters Memory-Space Complexity Time Complexity NTN W r ∈ R d × d × k , M r 1 , M r 2 ∈ R d × d O(ned+nrd2k+2nrd2+nrd) O ( d 2 k ) RESCAL Mr∈Rd×d O ( n e d + n r d 2 ) O ( d 2 ) SE M r h , M r t ∈ R d × d O ( n e d + 2 n r d 2 ) O ( d 2 ) SLM M r 1 , M r 2 ∈ R d × d O ( n e d + 2 n r d 2 + 2 n r d ) O ( d 2 ) LFM Mr,∈Rd×d O ( n e d + n r d 2 ) O ( d 2 ) TransR r ∈ R d , M r ∈ R d × d O(ned+nrd2+nrd) O ( d 2 ) DistMult r∈Rd O ( n e d + n r d ) O ( d ) ComplEx r∈Rd O ( 2 n e d + 2 n r d ) O ( d ) TransE r ∈ R d O ( n e d + n r d ) O ( d ) SimE-E r∈Rd O ( 2 n e d + n r d ) O(d) SimE-ER r∈Rd O ( 2 n e d + 2 n r d ) O(d)The comparison results are showed as follows:(i)
Except forDistMult andTransE, the baselines use relation matrix to project entities’ features into relation space, which makes these models have high memory-space and time complexities. Compared with these models,SimE-E andSimE-ER have lower time complexity.SimE-E andSimE-ER can be used on large-scale knowledge graphs more effectively.(ii)
In comparison toTransE,SimE-E andSimE-ER can dynamically control the ratio of positive and negative triplets. It enhances the robustness of representation models.(iii)
Compared withSimE-E andSimE-ER,DistMult is a special case of them when we only consider single similarity of entity or relation. That is to say,SimE-E andSimE-ER can extract the features of entities (relations) more comprehensively.


## 3.1. Our Models

The basic idea of our model is that, for each entity (relation), the features are divided into two parts. The first part describes inherent features of entities (relations) in independent space. The feature embedding vectors can be denoted ashi, ri, ti. The second part signs triplet features in associated space, and the feature embedding vectors can be denoted as ha, ra, ta. In independent space, the feature vectors are described as the inherent features entities (relations) have. In associated space, the features of ha are comprised of other entities and relations which connect with entity ha.The entities (relations) in associated space are projections of entities (relations) in independent space. Hence the representation features of the same entity in independent and associated space are similar, while the representation features of different entities are not similar. The formula can be described as follows:(1)hi≈ra⊙ta,(2)ri≈ha⊙ta,(3)ti≈ha⊙ra,where ⊙ denotes element-wise product. In detail, in (1), if we combine the features of ra and ta, we can obtain part of the hi features. That is to say, the hi features are similar with ra⊙ta. In this paper, we useCosine to calculate the similarity between different spaces. Taking head entity as an example, theCosine similarity between different spaces can be denoted as(4)cos⁡hi,ra⊙ta=Dothi,ra⊙tahira⊙ta=Sumhi⊙ra⊙tahira⊙tawhereDot denotes the dot-product andSum denotes the summation over the vector element. Sum(hi⊙ra⊙ta) calculates the similarity, and hi  ra⊙ta constrain the length of features. To reduce the training complexity, we just consider the numerator and use regularization items to replace the denominator. Hence the similarity of head entity features in independent and graph spaces can be described as(5)Simh=Sumhi⊙ra⊙ta. We expect that the value of hi⊙ra⊙ta is larger when hi and ra⊙ta denote the same head entity, while the value of hi⊙ra⊙ta is smaller otherwise.To represent entities in a more comprehensive way, we consider the similarity of head and tail entities simultaneously. The score function can be denoted as(6)Simh,t=Simh+Simt=Sumhi⊙ra⊙ta+Sumha⊙ra⊙ti. The embedding model based on the similarity of head and tail entities is named asSimE-E.On the basis of entity similarity, we need to consider relation similarity, which can enhance the representation of relation features. The comprehensive model, which considers all the similarities of entity (relation) features in different spaces, can be described as(7)Simh,r,t=Simh+Simr+Simt=Sumhi⊙ra⊙ta+Sumha⊙ri⊙ta+Sumha⊙ra⊙ti.The embedding model based on the similarity of entity and relation is named asSimE-ER.


## 3.2. Training

To learn the proposed embedding and encourage the discrimination between golden triplets and incorrect triplets, we minimize the following logistic ranking loss function over the training set:(8)L=∑h,r,t∈Slog⁡1+exp⁡-YhrtSimh,r,t;Θ, where Θ corresponds to the embeddings hi, ha, ri, ra, ti, ta∈Rd and Yhrt is a label of triplet. Yhrt=1 denotes that (h,r,t) is positive and Yhrt=-1 denotes that (h,r,t) is negative. S is a triplets set [28] which contains both positive triplets set S+ and negative triplets set S-.(9)S-=h′,r,t∣h′∈E∪h,r,t′∣t′∈E∪h,r′,t∣r′∈R.The set of negative triplets, constructed according to (9), is composed of training triplets with either head (tail) entity or relation replaced by a random entity or relation. Only one entity or relation is replaced for each corrupted triplet with the same probability. To prevent overfitting, some constraints are considered when minimizing the loss function L:(10)∀hi,ti∈E,ri∈R,hi=1,ri=1,ti=1,∀ha,ta∈E,ra∈R,ha⊙ra=1,ha⊙ta=1,ra⊙ta=1.Equation (10) is to constrain the length of entity (relation) features forSimE-E andSimE-ER. We convert it to the following loss function by means of soft constraints:(11)L=∑h,r,t∈Slog⁡1+exp⁡-YhrtSimh,r,t;Θ+λΘ22,where λ is a hyperparameter to weigh the importance of soft constraints. We utilize the improved stochastic gradient descent (Adagrad) [46] to train the models. Comparing withSGD,Adagrad shrinks learning rate effectively when the number of iterations increases, which means that it is insensitive to learning rate.


## 3.3. Comparison with Existing Models

To compare the time and memory-space complexities between different models, we show the results in Table1, where d represents the dimension of entity and relation embeddings, k is the number of tensor’s slices, and ne and nr are the numbers of entities and relations, respectively.Table 1
Complexities of representation models.
Model Relation Parameters Memory-Space Complexity Time Complexity NTN W r ∈ R d × d × k , M r 1 , M r 2 ∈ R d × d O(ned+nrd2k+2nrd2+nrd) O ( d 2 k ) RESCAL Mr∈Rd×d O ( n e d + n r d 2 ) O ( d 2 ) SE M r h , M r t ∈ R d × d O ( n e d + 2 n r d 2 ) O ( d 2 ) SLM M r 1 , M r 2 ∈ R d × d O ( n e d + 2 n r d 2 + 2 n r d ) O ( d 2 ) LFM Mr,∈Rd×d O ( n e d + n r d 2 ) O ( d 2 ) TransR r ∈ R d , M r ∈ R d × d O(ned+nrd2+nrd) O ( d 2 ) DistMult r∈Rd O ( n e d + n r d ) O ( d ) ComplEx r∈Rd O ( 2 n e d + 2 n r d ) O ( d ) TransE r ∈ R d O ( n e d + n r d ) O ( d ) SimE-E r∈Rd O ( 2 n e d + n r d ) O(d) SimE-ER r∈Rd O ( 2 n e d + 2 n r d ) O(d)The comparison results are showed as follows:(i)
Except forDistMult andTransE, the baselines use relation matrix to project entities’ features into relation space, which makes these models have high memory-space and time complexities. Compared with these models,SimE-E andSimE-ER have lower time complexity.SimE-E andSimE-ER can be used on large-scale knowledge graphs more effectively.(ii)
In comparison toTransE,SimE-E andSimE-ER can dynamically control the ratio of positive and negative triplets. It enhances the robustness of representation models.(iii)
Compared withSimE-E andSimE-ER,DistMult is a special case of them when we only consider single similarity of entity or relation. That is to say,SimE-E andSimE-ER can extract the features of entities (relations) more comprehensively.


## 4. Experiments and Analysis

In this section, our modelsSimE-E andSimE-ER are evaluated and compared with several baselines which have been shown to achieve state-of-the-art performance. Firstly, two classical tasks are adopted to evaluate our models: entity prediction and relation prediction. Then, we use cases to verify the effectiveness of our models. Finally, according to the practical experimental results, we analyze the time and memory-space costs.


### 4.1. Datasets

We use two real-life knowledge graphs to evaluate our method:(i)
WordNet   (https://wordnet.princeton.edu/download), a classical dictionary, is designed to describe correlation and semantic information between different words. Entities are used to describe the concepts of different words, and relationships are defined to describe the semantic relevance between different entities, such asinstance hypernym,similar to, andmember of domain topic. The data version we use is the same as [23] where triplets are denoted as (sway_2, has_instance, brachiate_1) or (felis_1, member_meronym, catamount_1). A subset of WordNet is adopted, named as WN18 [23].(ii)
Freebase (code.google.com/p/wiki-links), a huge and continually growing knowledge graph, describes large amount of facts in the world. InFreebase, entities are described by labels, and relations are denoted by a hierarchical structure, such as “/tv/tvgenre/programs” and “/medicine/drug_class/drugs”. We employ two subsets of Freebase, named as FB15K and FB40K [23].We show the statistics information of datasets in Table2. From Table 2, we see that, compared with WN18, FB15K and FB40K have more relationships and can be regarded as the typical large-scale knowledge graphs.Table 2
Dataset statistics.
Dataset #Entity #Relation #Train #Valid #Test WN18 40,934 18 141,442 5,000 5,000 FB15K 14,951 1,345 483,142 50,000 59,071 FB40K 37,591 1,317 325,350 5,000 5,000


### 4.2. Experiment Setup

Evaluation Protocol. For each triplet in the test set, each item of triplets (head entity or tail entity or relation) is removed and replaced by items in the dictionary in turn, respectively. Using score function to calculate these corrupted triplets and sorting the scores by ascending order, the rank of the correct entities or relations is stored. For relation in each test triplet, the whole procedure is repeated. In fact, we need to consider that some correct triplets are generated in the process of removing and replacement. Hence, we filter out the correct triplets from corrupted triplets which actually exist in training and validation sets. The evaluation measure before filtering is named as “Raw”, and the measure after filtering is named as “Filter”. We used two evaluation measures to evaluate our approach which is similar to [42]:(i)
MRR is an improved measure of MeanRank [23] which calculates the average rank of all the entities (relations) and calculates the average reciprocal rank of all the entities (relations). Compared with MeanRank, MRR is less sensitive to outliers. We report the results using both Filter and Raw rules.(ii)
Hits@n reports the ratio of correct entities inTop-n ranked entities. Because the number of entities is much larger than that of relations, we take Hits@1, Hits@3, Hits@10 for entity prediction task and take Hits@1, Hits@2, Hits@3 for relation prediction task.A state-of-the-art embedding model should have higher MRR and Hits@n.Baselines. Firstly, we compare the proposed methods withCP which uses canonical polyadic decomposition to extract the entities and relation features; then we compare the proposed methods withTransE which considers that tail entity features are close to the combined features of head entity and relation. BesidesTransR [47],ER-MLP [48],DistMult [41], andComplEx [43] are also used for comparison with our methods. We trainCP [49],DistMult,ComplEx,TransE, andTransR using the codes provided by authors. We choose the length of dimension d among {20,50,100,200}, the weight of regularization λ among {0,0.003,0.01,0.1,0.5,1}, the learning rate among {0.001,0.01,0.1,0.2,0.5}, and the ratio of negative and correct samples γ among {1,5,10,50,100}. The negative samples in different epochs are different.Implementation. For experiments usingSimE-E andSimE-ER, we select the dimension of the entity and the relation d among {50,100,150,200}, the weight of regularization λ among {0,0.01,0.1,0.5,1}, the ratio of negative and correct samples γ among {1,5,10,50,100}, and the mini-batch size B among {100,200,500,1,000}. We utilized the improved stochastic gradient descent (Adagrad) [46] to train the loss function. With the iteration epoch increasing, the learning rate inAdagrad is decreases, andAdagrad is insensitive to learning rate. The initial values of bothSimE-E andSimE-ER are generated byRandom function, and the range is (-6/d,6/d), where d is the dimension of feature vector. Training is stopped using early stopping on the validation set MRR (using theFilter measure), computed every 50 epochs with a maximum of 2000 epochs.InSimE-E model, the optimal configurations on validation set are(i)
λ=1, γ=10, d=150, B=100 on WN18,(ii)
λ=1, γ=20, d=200, B=200 on FB15K,(iii)
λ=1, γ=20, d=300, B=100 on FB40K.InSimE-ER model, the optimal configurations on validation set are(i)
λ=1, γ=10, d=150, B=100 on WN18,(ii)
λ=1, γ=20, d=200, B=200 on FB15K,(iii)
λ=1, γ=20, d=300, B=100 on FB40K.T-test. In experiments, for each model, we run 15 times independently and calculate the mean and standard deviation. Then we use Student's t-test with p-value=0.95 to compare the performance between different models, and the t-test can be shown as follows [50, 51].μ 1 and s1 are mean and standard deviation on model 1 with run n1 times; μ2 and s2 are mean and standard deviation on model 2 with n2 times. Then we can construct the hypothesis:(12)H0:μ1-μ2≤0,H1:μ1-μ2>0.And the t-test can be described as(13)t=μ1-μ21/n1+1/n2n1s12+n2s22/n1+n2-2. The degree of freedom (df) in t-distribution can be shown as follows:(14)df=s12/n1+s22/n221/n1-1s12/n12+1/n2-1s22/n22In entity and relation prediction tasks, we calculate mean and standard deviation of MRR and Hit@n and compare their performance with t-test.


### 4.3. Link Prediction

For link prediction [52–54], we tested two subtasks—entity prediction and relation prediction. Entity prediction aims to predict the missing h or t entity from the fact triplet (h,r,t); similarly, relation prediction is to determine which relation is more suitable for a corrupted triplet (h,∗,t).Entity Prediction. This set of experiments tests the models’ ability to predict entities. Experimental results of mean and plus/minus standard deviation on both WN18 and FB15K are shown in Tables 3, 4, and 5, and we can observe the following:(i)
On WN18, a small-scale knowledge graph,ComplEx, achieves state-of-the-art results on MRR and Hits@n. However, on FB15K and FB40K, two large-scale knowledge graphs,SimE-E andSimE-ER, achieve excellent results on MRR and Hits@n, and the values of Hits@10 are up to 0.868 and 0.889, respectively. The outstanding results prove that our models can represent different kinds of knowledge graphs effectively, especially on large-scale knowledge graphs.(ii)
ComplEx is better thanSimE-ER on WN18, and the reason is thatComplEx can distinguish symmetric and antisymmetric relationship contained in the relation structure of WN18. However, on FB15K and FB40K,SimE-E andSimE-ER are better thanComplEx. The reason is that the number of relations is much larger than WN18, and the relation structure is more complex and hard to represent, which has obvious influence on the representation ability ofComplEx.(iii)
The results ofSimE-E andSimE-ER are similar to each other. The largest margin is filtered MRR on FB15K at 0.013. The phenomenon demonstrates that bothSimE-E andSimE-ER can extract the entity features in knowledge graph and predict the missing entities effectively.(iv)
Compared withDistMult, the special case of our models,SimE-E andSimE-ER achieve better results, especially on FB15K, and the filter MRR is up to 0.740. The results can prove that our models which use irrelevant and interconnected features to construct independent and associated spaces can represent the entities and relations features more comprehensively.Table 3
Experimental results of entity prediction on WN18.
Model WN18 MRR Hits@ n Filter Raw 1 3 10 CP 0.065±0.002 0.051±0.001 0.043±0.002 0.069±0.001 0.107±0.002 DistMult 0.821±0.003 0.530±0.002 0.728±0.002 0.914±0.002 0.930±0.001 ER-MLP 0.712±0.002 0.508±0.003 0.626±0.002 0.775±0.002 0.863±0.003 TransE 0.445±0.002 0.318±0.002 0.081±0.002 0.801±0.001 0.937±0.003 TransR 0.415±0.002 0.414±0.003 0.378±0.002 0.635±0.003 0.724±0.001 ComplEx 0.936 ± 0.003 0.575±0.002 0.933 ± 0.001 0.939 ± 0.001 0.940 ± 0.001  SimE-E 0.823±0.003 0.572±0.002 0.726±0.001 0.917±0.002 0.938±0.001 SimE-ER 0.821±0.002 0.576 ± 0.002 0.726±0.002 0.914±0.002 0.940 ± 0.002Table 4
Experimental results of entity prediction on FB15K.
Model FB15K MRR Hits@ n Filter Raw 1 3 10 CP 0.333±0.003 0.153±0.002 0.229±0.004 0.381±0.003 0.531±0.004 DistMult 0.650±0.003 0.242±0.003 0.537±0.004 0.738±0.003 0.828±0.003 ER-MLP 0.288±0.002 0.155±0.002 0.173±0.005 0.317±0.005 0.501±0.001 TransE 0.481±0.004 0.220±0.002 0.259±0.005 0.651±0.002 0.813±0.002 TransR 0.376±0.003 0.201±0.004 0.245±0.002 0.435±0.002 0.634±0.003 ComplEx 0.691±0.003 0.241±0.002 0.596±0.003 0.752±0.002 0.838±0.003  SimE-E 0.740 ± 0.002 0.259±0.002 0.666 ± 0.002 0.795±0.003 0.860±0.003 SimE-ER 0.727±0.003 0.261 ± 0.002 0.636±0.003 0.797 ± 0.002 0.868 ± 0.003Table 5
Experimental results of entity prediction on FB40K.
Model FB40K MRR Hits@ n Filter Raw 1 3 10 CP 0.448±0.002 0.274±0.002 0.392±0.003 0.479±0.002 0.549±0.002 DistMult 0.573±0.003 0.407±0.003 0.493±0.002 0.613±0.002 0.720±0.003 ER-MLP 0.296±0.001 0.167±0.004 0.181±0.001 0.332±0.003 0.498±0.003 TransE 0.574±0.003 0.383±0.001 0.422±0.002 0.687±0.003 0.808±0.001 TransR 0.355±0.001 0.198±0.001 0.224±0.002 0.441±0.002 0.612±0.001 ComplEx 0.680±0.001 0.408±0.002 0.586±0.002 0.753±0.002 0.837±0.002  SimE-E 0.816 ± 0.001 0.439±0.002 0.781 ± 0.002 0.848±0.002 0.874±0.002 SimE-ER 0.810±0.001 0.445 ± 0.002 0.756±0.002 0.852 ± 0.002 0.889 ± 0.002We use t-test to evaluate the effectiveness of our models, and the evaluation results can prove that on FB15K and FB40K, compared with other baselines, our results achieve significant improvements, e.g., on the Hits@10 results ofComplEx andSimE-ER, t=26.45 which is larger than t0.95(28)=1.701. The t-test results can prove that, on FB15K and FB40K, our experimental results achieve significant improvement compared with other baselines.Relation Prediction. This set of experiments tests the models’ ability to predict relations. Tables 6, 7, and 8 show the prediction performance on WN18 and FB15K. From the tables, we discover the following:(i)
Similar to the results in the entity prediction, on WN18,ComplEx achieves better results on MRR and Hits@1, andSimE-ER obtains better results on Hits@2 and Hits@3. On FB15K, besides the value of Hits@1, the results ofSimE-ER are better thanComplEx and other baselines, and the value of Hits@3 is up to 0.842, which is much higher (improvement of 20.1%) than the state-of-the-art baselines. ON FB40K,SimE-ER achieves state-of-the-art results on all the measures; in particular, the filter MRR is up to 0.603.(ii)
In entity prediction task, the results ofSimE-E andSimE-ER are similar. However, in relation prediction tasks,SimE-ER achieves significant results on Raw MRR, Hits@2, and Hits@3. We use the t-test to verify the results, and the t-values are larger than t0.95(28)=1.701. The difference between entity and relation tasks can demonstrate that considering both entity and relation similarity can extract relation features more effectively on the basis of ensuring the entity-features extraction.(iii)
On FB15K, the gap is significant andSimE-E andSimE-ER outperform other models, with a MRR (Filter) of 0.593 and 0.842 of Hits@3. On both datasets,CP andTransE perform the worst, which illustrates the feasibility of learning knowledge embedding in the first case and the power of using two mutual restraint parts to represent entities and relations in the second.Table 6
Experimental results of relation prediction on WN18.
Model WN18 MRR Hits@ n Filter Raw 1 2 3 CP 0.551±0.003 0.550±0.002 0.405±0.002 0.540±0.002 0.629±0.001 DistMult 0.731±0.003 0.730±0.002 0.535±0.002 0.922±0.002 0.938±0.002 ER-MLP 0.707±0.002 0.513±0.002 0.614±0.001 0.815±0.003 0.877±0.002 TransE 0.739±0.002 0.739±0.001 0.622±0.002 0.729±0.002 0.811±0.002 TransR 0.415±0.003 0.414±0.003 0.378±0.003 0.635±0.002 0.724±0.001 ComplEx 0.866 ± 0.003 0.865 ± 0.003 0.830 ± 0.001 0.953±0.002 0.961±0.002  SimE-E 0.812±0.002 0.812±0.001 0.770±0.002 0.954±0.002 0.962±0.001 SimE-ER 0.814±0.002 0.814±0.001 0.775±0.001 0.955 ± 0.002 0.965 ± 0.001Table 7
Experimental results of relation prediction on FB15K.
Model FB15K MRR Hits@ n Filter Raw 1 2 3 CP 0.361±0.002 0.308±0.001 0.240±0.002 0.347±0.002 0.411±0.002 DistMult 0.309±0.003 0.285±0.003 0.116±0.002 0.289±0.002 0.412±0.004 ER-MLP 0.412±0.003 0.268±0.002 0.236±0.003 0.573±0.003 0.631±0.003 TransE 0.245±0.002 0.281±0.002 0.275±0.003 0.339±0.002 0.381±0.003 TransR 0.416±0.002 0.343±0.002 0.270±0.001 0.448±0.002 0.573±0.002 ComplEx 0.566±0.002 0.490±0.001 0.371 ± 0.002 0.646±0.001 0.701±0.002  SimE-E 0.579±0.002 0.523±0.001 0.321±0.002 0.708±0.002 0.823±0.002 SimE-ER 0.593  ±0.002 0.534  ±0.001 0.331±0.002 0.737 ± 0.001 0.842 ± 0.002Table 8
Experimental results of relation prediction on FB40K.
Model FB40K MRR Hits@ n Filter Raw 1 2 3 CP 0.295±0.002 0.192±0.002 0.231±0.002 0.300±0.003 0.332±0.003 DistMult 0.470±0.002 0.407±0.001 0.310±0.002 0.536±0.003 0.801±0.003 ER-MLP 0.377±0.002 0.257±0.002 0.231±0.002 0.567±0.002 0.611±0.002 TransE 0.461±0.001 0.373±0.002 0.245±0.001 0.442±0.001 0.521±0.003 TransR 0.431±0.002 0.312±0.003 0.263±0.001 0.411±0.002 0.514±0.002 ComplEx 0.576±0.002 0.496±0.003 0.329±0.003 0.595±0.002 0.790±0.001  SimE-E 0.589±0.002 0.513±0.002 0.326±0.003 0.606±0.002 0.844 ± 0.001 SimE-ER 0.603 ± 0.002 0.531 ± 0.003 0.336 ± 0.003 0.637 ± 0.001 0.843±0.001We also use t-test to evaluate our model; i.e., comparingSimE-ER withComplEx on filter MRR, t=35.72, which is larger than t0.95(28)=1.701. The t-test results can prove that the performance ofSimE-ER is better than other baselines on FB15K and FB40K.To analyze the relation features, Table9 shows the MRR with Filter of each relation on WN18, where #Tri denotes the number of triplets for each relation in the test set. From Table 9, we conclude the following:(i)
For almost all relations on WN18, compared with other baselines,SimE-E andSimE-ER achieve competitive results, which demonstrates that our methods can extract different types of latent relation features.(ii)
Compared withSimE-E, the relation MRRs ofSimE-ER are much better on most relations, such ashypernym,hyponym, andderivationally_related_form.(iii)
On almost all results of relation MRR,SimE-ER is better thanDistMult, a special case ofSimE-ER. That is to say, compared with single embedding space, using two different spaces to describe entity and relation, features can achieve better performance.Table 9
MRR for each relation on WN18.
Relation Name #Tri SimE-ER SimE-E ComplEx DistMult hypernym 1251 0.937 0.927 0.933 0.701 hyponym 1153 0.788 0.520 0.910 0.732 derivationally_related_form 1074 0.964 0.963 0.946 0.959 member_holonym 278 0.715 0.603 0.914 0.701 member_meronym 253 0.682 0.767 0.767 0.55 has_part 172 0.675 0.602 0.933 0.667 part_of 165 0.685 0.819 0.931 0.690 instance_hypernym 122 0.703 0.856 0.799 0.726 synset_domain_topic_of 114 0.792 0.847 0.813 0.584 member_of_domain_topic 111 0.695 0.523 0.714 0.799 instance_hyponym 108 0.661 0.561 0.945 0.651 also_see 56 0.769 0.680 0.603 0.727 verb_group 39 0.977 0.977 0.936 0.973 synset_domain_region_of 37 0.736 0.819 1.000 0.694 member_of_domain_region 26 0.468 0.799 0.788 0.504 member_of_domain_usage 24 0.463 0.578 0.780 0.507 synset_domain_usage_of 14 0.928 0.761 1.000 0.750 similar_to 3 1.000 1.000 1.000 1.000Case Study. Table 10 shows the detailed prediction results on test set of FB15K. It illustrates the performance of our models. Given head and tail entities, the top-5 predicted relations and relative scores ofSimE-ER are depicted in Table 10. From the table, we observe the following:(i)
In triplet 1, the relation prediction result is ranked on top-2, and in triplet 2, the result is top-1. The relation prediction results can prove the performance ofSimE-ER. However, in triplet 1, the correct result (top-2) has similar score with other prediction results (top-1, top-3). That is to say, it is difficult forSimE-ER to distinguish similar relationships.(ii)
For any relation prediction results, the top-5 relation prediction results are similar; that is to say, similar relations have similar representation embeddings, which is in line with common sense.Table 10
Case study ofSimE-ER.
Triplet 1 /m/02rgz97 /music/group_member/artists_supported /m/012d9h Score  Results 1 /music/group_member/membership./music/group_membership/group 0.997 2/music/group_member/artists_ supported 0.975 3 /music/group_member/instruments_played 0.953 4 /music/group_member/membership./music/group_membership/role 0.913 5 /music/genre/subgenre 0.891  Triplet 2 /m/02hrh1q /organization/role/governors./organization/member /m/03mnk Score  Results 1/organization/role/governors./organization//member 0.994 2 /organization/role/leaders./organization/leadership/organization 0.983 3 /organization/organization_sector/organizations_in_this_sector 0.946 4 /organization/organization_member/member_of./organization/organization 0.911 5 /people/appointed_role/appointment./people/appointment/appointed_by 0.767


### 4.4. Complexity Analysis

To compare the time and memory-space complexity of different models, we show the analytical results of FB15K in Table11, where d represents the dimension of entity and relation space, “Mini-batch” represents the mini-batch of each iteration, “Params” denotes the number of parameters in each model on FB15K, and “Time” denotes the running time of each iteration. Note that all models are run on standard hardware of Inter(R) Core(TM) i7U 3.5GHz + GeForce GTX TITAN. We report the average running time over one hundred iterations as the running time of each iteration. From Table 11, we observe the following:(i)
Except forDistMult,SimE-E andSimE-ER have lower time and memory complexities compared with the baselines, because inSimE-E andSimE-ER, we only use element-wise products between entities’ and relations’ vectors to generate the representation embedding.(ii)
On FB15K, the time costs ofSimE-E andSimE-ER in each iteration are 5.37s and 6.63s, respectively, which are lower than 7.53s, the time cost ofTransE which has fewer parameters. The reason is that the mini-batch ofTransE is 2415 which is much larger than the mini-batches ofSimE-E andSimE-ER. Besides, forSimE-E andSimE-ER, the number of iterations is 700 times with 3760 (s) and 4642 (s), respectively.(iii)
BecauseSimE-E andSimE-ER have low complexity and high accuracy, they can easily be applied to large-scale knowledge graph, while using less computing resources and running time.Table 11
Complexities comparison.
Model d Mini-batch Params Time (s) RESCAL 100 200 14.25M 121.36 NTN 100 100 78.40M 347.65 TransR 100 2145 14.38M 95.96 TransE 200 2145 3.11M 7.53 DistMult 200 100 3.11M 3.23 SimE-E 200 200 5.95M 5.37 SimE-ER 200 200 6.22M 6.63


## 4.1. Datasets

We use two real-life knowledge graphs to evaluate our method:(i)
WordNet   (https://wordnet.princeton.edu/download), a classical dictionary, is designed to describe correlation and semantic information between different words. Entities are used to describe the concepts of different words, and relationships are defined to describe the semantic relevance between different entities, such asinstance hypernym,similar to, andmember of domain topic. The data version we use is the same as [23] where triplets are denoted as (sway_2, has_instance, brachiate_1) or (felis_1, member_meronym, catamount_1). A subset of WordNet is adopted, named as WN18 [23].(ii)
Freebase (code.google.com/p/wiki-links), a huge and continually growing knowledge graph, describes large amount of facts in the world. InFreebase, entities are described by labels, and relations are denoted by a hierarchical structure, such as “/tv/tvgenre/programs” and “/medicine/drug_class/drugs”. We employ two subsets of Freebase, named as FB15K and FB40K [23].We show the statistics information of datasets in Table2. From Table 2, we see that, compared with WN18, FB15K and FB40K have more relationships and can be regarded as the typical large-scale knowledge graphs.Table 2
Dataset statistics.
Dataset #Entity #Relation #Train #Valid #Test WN18 40,934 18 141,442 5,000 5,000 FB15K 14,951 1,345 483,142 50,000 59,071 FB40K 37,591 1,317 325,350 5,000 5,000


## 4.2. Experiment Setup

Evaluation Protocol. For each triplet in the test set, each item of triplets (head entity or tail entity or relation) is removed and replaced by items in the dictionary in turn, respectively. Using score function to calculate these corrupted triplets and sorting the scores by ascending order, the rank of the correct entities or relations is stored. For relation in each test triplet, the whole procedure is repeated. In fact, we need to consider that some correct triplets are generated in the process of removing and replacement. Hence, we filter out the correct triplets from corrupted triplets which actually exist in training and validation sets. The evaluation measure before filtering is named as “Raw”, and the measure after filtering is named as “Filter”. We used two evaluation measures to evaluate our approach which is similar to [42]:(i)
MRR is an improved measure of MeanRank [23] which calculates the average rank of all the entities (relations) and calculates the average reciprocal rank of all the entities (relations). Compared with MeanRank, MRR is less sensitive to outliers. We report the results using both Filter and Raw rules.(ii)
Hits@n reports the ratio of correct entities inTop-n ranked entities. Because the number of entities is much larger than that of relations, we take Hits@1, Hits@3, Hits@10 for entity prediction task and take Hits@1, Hits@2, Hits@3 for relation prediction task.A state-of-the-art embedding model should have higher MRR and Hits@n.Baselines. Firstly, we compare the proposed methods withCP which uses canonical polyadic decomposition to extract the entities and relation features; then we compare the proposed methods withTransE which considers that tail entity features are close to the combined features of head entity and relation. BesidesTransR [47],ER-MLP [48],DistMult [41], andComplEx [43] are also used for comparison with our methods. We trainCP [49],DistMult,ComplEx,TransE, andTransR using the codes provided by authors. We choose the length of dimension d among {20,50,100,200}, the weight of regularization λ among {0,0.003,0.01,0.1,0.5,1}, the learning rate among {0.001,0.01,0.1,0.2,0.5}, and the ratio of negative and correct samples γ among {1,5,10,50,100}. The negative samples in different epochs are different.Implementation. For experiments usingSimE-E andSimE-ER, we select the dimension of the entity and the relation d among {50,100,150,200}, the weight of regularization λ among {0,0.01,0.1,0.5,1}, the ratio of negative and correct samples γ among {1,5,10,50,100}, and the mini-batch size B among {100,200,500,1,000}. We utilized the improved stochastic gradient descent (Adagrad) [46] to train the loss function. With the iteration epoch increasing, the learning rate inAdagrad is decreases, andAdagrad is insensitive to learning rate. The initial values of bothSimE-E andSimE-ER are generated byRandom function, and the range is (-6/d,6/d), where d is the dimension of feature vector. Training is stopped using early stopping on the validation set MRR (using theFilter measure), computed every 50 epochs with a maximum of 2000 epochs.InSimE-E model, the optimal configurations on validation set are(i)
λ=1, γ=10, d=150, B=100 on WN18,(ii)
λ=1, γ=20, d=200, B=200 on FB15K,(iii)
λ=1, γ=20, d=300, B=100 on FB40K.InSimE-ER model, the optimal configurations on validation set are(i)
λ=1, γ=10, d=150, B=100 on WN18,(ii)
λ=1, γ=20, d=200, B=200 on FB15K,(iii)
λ=1, γ=20, d=300, B=100 on FB40K.T-test. In experiments, for each model, we run 15 times independently and calculate the mean and standard deviation. Then we use Student's t-test with p-value=0.95 to compare the performance between different models, and the t-test can be shown as follows [50, 51].μ 1 and s1 are mean and standard deviation on model 1 with run n1 times; μ2 and s2 are mean and standard deviation on model 2 with n2 times. Then we can construct the hypothesis:(12)H0:μ1-μ2≤0,H1:μ1-μ2>0.And the t-test can be described as(13)t=μ1-μ21/n1+1/n2n1s12+n2s22/n1+n2-2. The degree of freedom (df) in t-distribution can be shown as follows:(14)df=s12/n1+s22/n221/n1-1s12/n12+1/n2-1s22/n22In entity and relation prediction tasks, we calculate mean and standard deviation of MRR and Hit@n and compare their performance with t-test.


## 4.3. Link Prediction

For link prediction [52–54], we tested two subtasks—entity prediction and relation prediction. Entity prediction aims to predict the missing h or t entity from the fact triplet (h,r,t); similarly, relation prediction is to determine which relation is more suitable for a corrupted triplet (h,∗,t).Entity Prediction. This set of experiments tests the models’ ability to predict entities. Experimental results of mean and plus/minus standard deviation on both WN18 and FB15K are shown in Tables 3, 4, and 5, and we can observe the following:(i)
On WN18, a small-scale knowledge graph,ComplEx, achieves state-of-the-art results on MRR and Hits@n. However, on FB15K and FB40K, two large-scale knowledge graphs,SimE-E andSimE-ER, achieve excellent results on MRR and Hits@n, and the values of Hits@10 are up to 0.868 and 0.889, respectively. The outstanding results prove that our models can represent different kinds of knowledge graphs effectively, especially on large-scale knowledge graphs.(ii)
ComplEx is better thanSimE-ER on WN18, and the reason is thatComplEx can distinguish symmetric and antisymmetric relationship contained in the relation structure of WN18. However, on FB15K and FB40K,SimE-E andSimE-ER are better thanComplEx. The reason is that the number of relations is much larger than WN18, and the relation structure is more complex and hard to represent, which has obvious influence on the representation ability ofComplEx.(iii)
The results ofSimE-E andSimE-ER are similar to each other. The largest margin is filtered MRR on FB15K at 0.013. The phenomenon demonstrates that bothSimE-E andSimE-ER can extract the entity features in knowledge graph and predict the missing entities effectively.(iv)
Compared withDistMult, the special case of our models,SimE-E andSimE-ER achieve better results, especially on FB15K, and the filter MRR is up to 0.740. The results can prove that our models which use irrelevant and interconnected features to construct independent and associated spaces can represent the entities and relations features more comprehensively.Table 3
Experimental results of entity prediction on WN18.
Model WN18 MRR Hits@ n Filter Raw 1 3 10 CP 0.065±0.002 0.051±0.001 0.043±0.002 0.069±0.001 0.107±0.002 DistMult 0.821±0.003 0.530±0.002 0.728±0.002 0.914±0.002 0.930±0.001 ER-MLP 0.712±0.002 0.508±0.003 0.626±0.002 0.775±0.002 0.863±0.003 TransE 0.445±0.002 0.318±0.002 0.081±0.002 0.801±0.001 0.937±0.003 TransR 0.415±0.002 0.414±0.003 0.378±0.002 0.635±0.003 0.724±0.001 ComplEx 0.936 ± 0.003 0.575±0.002 0.933 ± 0.001 0.939 ± 0.001 0.940 ± 0.001  SimE-E 0.823±0.003 0.572±0.002 0.726±0.001 0.917±0.002 0.938±0.001 SimE-ER 0.821±0.002 0.576 ± 0.002 0.726±0.002 0.914±0.002 0.940 ± 0.002Table 4
Experimental results of entity prediction on FB15K.
Model FB15K MRR Hits@ n Filter Raw 1 3 10 CP 0.333±0.003 0.153±0.002 0.229±0.004 0.381±0.003 0.531±0.004 DistMult 0.650±0.003 0.242±0.003 0.537±0.004 0.738±0.003 0.828±0.003 ER-MLP 0.288±0.002 0.155±0.002 0.173±0.005 0.317±0.005 0.501±0.001 TransE 0.481±0.004 0.220±0.002 0.259±0.005 0.651±0.002 0.813±0.002 TransR 0.376±0.003 0.201±0.004 0.245±0.002 0.435±0.002 0.634±0.003 ComplEx 0.691±0.003 0.241±0.002 0.596±0.003 0.752±0.002 0.838±0.003  SimE-E 0.740 ± 0.002 0.259±0.002 0.666 ± 0.002 0.795±0.003 0.860±0.003 SimE-ER 0.727±0.003 0.261 ± 0.002 0.636±0.003 0.797 ± 0.002 0.868 ± 0.003Table 5
Experimental results of entity prediction on FB40K.
Model FB40K MRR Hits@ n Filter Raw 1 3 10 CP 0.448±0.002 0.274±0.002 0.392±0.003 0.479±0.002 0.549±0.002 DistMult 0.573±0.003 0.407±0.003 0.493±0.002 0.613±0.002 0.720±0.003 ER-MLP 0.296±0.001 0.167±0.004 0.181±0.001 0.332±0.003 0.498±0.003 TransE 0.574±0.003 0.383±0.001 0.422±0.002 0.687±0.003 0.808±0.001 TransR 0.355±0.001 0.198±0.001 0.224±0.002 0.441±0.002 0.612±0.001 ComplEx 0.680±0.001 0.408±0.002 0.586±0.002 0.753±0.002 0.837±0.002  SimE-E 0.816 ± 0.001 0.439±0.002 0.781 ± 0.002 0.848±0.002 0.874±0.002 SimE-ER 0.810±0.001 0.445 ± 0.002 0.756±0.002 0.852 ± 0.002 0.889 ± 0.002We use t-test to evaluate the effectiveness of our models, and the evaluation results can prove that on FB15K and FB40K, compared with other baselines, our results achieve significant improvements, e.g., on the Hits@10 results ofComplEx andSimE-ER, t=26.45 which is larger than t0.95(28)=1.701. The t-test results can prove that, on FB15K and FB40K, our experimental results achieve significant improvement compared with other baselines.Relation Prediction. This set of experiments tests the models’ ability to predict relations. Tables 6, 7, and 8 show the prediction performance on WN18 and FB15K. From the tables, we discover the following:(i)
Similar to the results in the entity prediction, on WN18,ComplEx achieves better results on MRR and Hits@1, andSimE-ER obtains better results on Hits@2 and Hits@3. On FB15K, besides the value of Hits@1, the results ofSimE-ER are better thanComplEx and other baselines, and the value of Hits@3 is up to 0.842, which is much higher (improvement of 20.1%) than the state-of-the-art baselines. ON FB40K,SimE-ER achieves state-of-the-art results on all the measures; in particular, the filter MRR is up to 0.603.(ii)
In entity prediction task, the results ofSimE-E andSimE-ER are similar. However, in relation prediction tasks,SimE-ER achieves significant results on Raw MRR, Hits@2, and Hits@3. We use the t-test to verify the results, and the t-values are larger than t0.95(28)=1.701. The difference between entity and relation tasks can demonstrate that considering both entity and relation similarity can extract relation features more effectively on the basis of ensuring the entity-features extraction.(iii)
On FB15K, the gap is significant andSimE-E andSimE-ER outperform other models, with a MRR (Filter) of 0.593 and 0.842 of Hits@3. On both datasets,CP andTransE perform the worst, which illustrates the feasibility of learning knowledge embedding in the first case and the power of using two mutual restraint parts to represent entities and relations in the second.Table 6
Experimental results of relation prediction on WN18.
Model WN18 MRR Hits@ n Filter Raw 1 2 3 CP 0.551±0.003 0.550±0.002 0.405±0.002 0.540±0.002 0.629±0.001 DistMult 0.731±0.003 0.730±0.002 0.535±0.002 0.922±0.002 0.938±0.002 ER-MLP 0.707±0.002 0.513±0.002 0.614±0.001 0.815±0.003 0.877±0.002 TransE 0.739±0.002 0.739±0.001 0.622±0.002 0.729±0.002 0.811±0.002 TransR 0.415±0.003 0.414±0.003 0.378±0.003 0.635±0.002 0.724±0.001 ComplEx 0.866 ± 0.003 0.865 ± 0.003 0.830 ± 0.001 0.953±0.002 0.961±0.002  SimE-E 0.812±0.002 0.812±0.001 0.770±0.002 0.954±0.002 0.962±0.001 SimE-ER 0.814±0.002 0.814±0.001 0.775±0.001 0.955 ± 0.002 0.965 ± 0.001Table 7
Experimental results of relation prediction on FB15K.
Model FB15K MRR Hits@ n Filter Raw 1 2 3 CP 0.361±0.002 0.308±0.001 0.240±0.002 0.347±0.002 0.411±0.002 DistMult 0.309±0.003 0.285±0.003 0.116±0.002 0.289±0.002 0.412±0.004 ER-MLP 0.412±0.003 0.268±0.002 0.236±0.003 0.573±0.003 0.631±0.003 TransE 0.245±0.002 0.281±0.002 0.275±0.003 0.339±0.002 0.381±0.003 TransR 0.416±0.002 0.343±0.002 0.270±0.001 0.448±0.002 0.573±0.002 ComplEx 0.566±0.002 0.490±0.001 0.371 ± 0.002 0.646±0.001 0.701±0.002  SimE-E 0.579±0.002 0.523±0.001 0.321±0.002 0.708±0.002 0.823±0.002 SimE-ER 0.593  ±0.002 0.534  ±0.001 0.331±0.002 0.737 ± 0.001 0.842 ± 0.002Table 8
Experimental results of relation prediction on FB40K.
Model FB40K MRR Hits@ n Filter Raw 1 2 3 CP 0.295±0.002 0.192±0.002 0.231±0.002 0.300±0.003 0.332±0.003 DistMult 0.470±0.002 0.407±0.001 0.310±0.002 0.536±0.003 0.801±0.003 ER-MLP 0.377±0.002 0.257±0.002 0.231±0.002 0.567±0.002 0.611±0.002 TransE 0.461±0.001 0.373±0.002 0.245±0.001 0.442±0.001 0.521±0.003 TransR 0.431±0.002 0.312±0.003 0.263±0.001 0.411±0.002 0.514±0.002 ComplEx 0.576±0.002 0.496±0.003 0.329±0.003 0.595±0.002 0.790±0.001  SimE-E 0.589±0.002 0.513±0.002 0.326±0.003 0.606±0.002 0.844 ± 0.001 SimE-ER 0.603 ± 0.002 0.531 ± 0.003 0.336 ± 0.003 0.637 ± 0.001 0.843±0.001We also use t-test to evaluate our model; i.e., comparingSimE-ER withComplEx on filter MRR, t=35.72, which is larger than t0.95(28)=1.701. The t-test results can prove that the performance ofSimE-ER is better than other baselines on FB15K and FB40K.To analyze the relation features, Table9 shows the MRR with Filter of each relation on WN18, where #Tri denotes the number of triplets for each relation in the test set. From Table 9, we conclude the following:(i)
For almost all relations on WN18, compared with other baselines,SimE-E andSimE-ER achieve competitive results, which demonstrates that our methods can extract different types of latent relation features.(ii)
Compared withSimE-E, the relation MRRs ofSimE-ER are much better on most relations, such ashypernym,hyponym, andderivationally_related_form.(iii)
On almost all results of relation MRR,SimE-ER is better thanDistMult, a special case ofSimE-ER. That is to say, compared with single embedding space, using two different spaces to describe entity and relation, features can achieve better performance.Table 9
MRR for each relation on WN18.
Relation Name #Tri SimE-ER SimE-E ComplEx DistMult hypernym 1251 0.937 0.927 0.933 0.701 hyponym 1153 0.788 0.520 0.910 0.732 derivationally_related_form 1074 0.964 0.963 0.946 0.959 member_holonym 278 0.715 0.603 0.914 0.701 member_meronym 253 0.682 0.767 0.767 0.55 has_part 172 0.675 0.602 0.933 0.667 part_of 165 0.685 0.819 0.931 0.690 instance_hypernym 122 0.703 0.856 0.799 0.726 synset_domain_topic_of 114 0.792 0.847 0.813 0.584 member_of_domain_topic 111 0.695 0.523 0.714 0.799 instance_hyponym 108 0.661 0.561 0.945 0.651 also_see 56 0.769 0.680 0.603 0.727 verb_group 39 0.977 0.977 0.936 0.973 synset_domain_region_of 37 0.736 0.819 1.000 0.694 member_of_domain_region 26 0.468 0.799 0.788 0.504 member_of_domain_usage 24 0.463 0.578 0.780 0.507 synset_domain_usage_of 14 0.928 0.761 1.000 0.750 similar_to 3 1.000 1.000 1.000 1.000Case Study. Table 10 shows the detailed prediction results on test set of FB15K. It illustrates the performance of our models. Given head and tail entities, the top-5 predicted relations and relative scores ofSimE-ER are depicted in Table 10. From the table, we observe the following:(i)
In triplet 1, the relation prediction result is ranked on top-2, and in triplet 2, the result is top-1. The relation prediction results can prove the performance ofSimE-ER. However, in triplet 1, the correct result (top-2) has similar score with other prediction results (top-1, top-3). That is to say, it is difficult forSimE-ER to distinguish similar relationships.(ii)
For any relation prediction results, the top-5 relation prediction results are similar; that is to say, similar relations have similar representation embeddings, which is in line with common sense.Table 10
Case study ofSimE-ER.
Triplet 1 /m/02rgz97 /music/group_member/artists_supported /m/012d9h Score  Results 1 /music/group_member/membership./music/group_membership/group 0.997 2/music/group_member/artists_ supported 0.975 3 /music/group_member/instruments_played 0.953 4 /music/group_member/membership./music/group_membership/role 0.913 5 /music/genre/subgenre 0.891  Triplet 2 /m/02hrh1q /organization/role/governors./organization/member /m/03mnk Score  Results 1/organization/role/governors./organization//member 0.994 2 /organization/role/leaders./organization/leadership/organization 0.983 3 /organization/organization_sector/organizations_in_this_sector 0.946 4 /organization/organization_member/member_of./organization/organization 0.911 5 /people/appointed_role/appointment./people/appointment/appointed_by 0.767


## 4.4. Complexity Analysis

To compare the time and memory-space complexity of different models, we show the analytical results of FB15K in Table11, where d represents the dimension of entity and relation space, “Mini-batch” represents the mini-batch of each iteration, “Params” denotes the number of parameters in each model on FB15K, and “Time” denotes the running time of each iteration. Note that all models are run on standard hardware of Inter(R) Core(TM) i7U 3.5GHz + GeForce GTX TITAN. We report the average running time over one hundred iterations as the running time of each iteration. From Table 11, we observe the following:(i)
Except forDistMult,SimE-E andSimE-ER have lower time and memory complexities compared with the baselines, because inSimE-E andSimE-ER, we only use element-wise products between entities’ and relations’ vectors to generate the representation embedding.(ii)
On FB15K, the time costs ofSimE-E andSimE-ER in each iteration are 5.37s and 6.63s, respectively, which are lower than 7.53s, the time cost ofTransE which has fewer parameters. The reason is that the mini-batch ofTransE is 2415 which is much larger than the mini-batches ofSimE-E andSimE-ER. Besides, forSimE-E andSimE-ER, the number of iterations is 700 times with 3760 (s) and 4642 (s), respectively.(iii)
BecauseSimE-E andSimE-ER have low complexity and high accuracy, they can easily be applied to large-scale knowledge graph, while using less computing resources and running time.Table 11
Complexities comparison.
Model d Mini-batch Params Time (s) RESCAL 100 200 14.25M 121.36 NTN 100 100 78.40M 347.65 TransR 100 2145 14.38M 95.96 TransE 200 2145 3.11M 7.53 DistMult 200 100 3.11M 3.23 SimE-E 200 200 5.95M 5.37 SimE-ER 200 200 6.22M 6.63


## 5. Conclusion

In this paper, we propose a novel similarity-based embedding modelSimE-ER that extracts features from knowledge graph.SimE-ER considers that the similarity of the same entities (relations) is high in independent and associated spaces. Compared with other representation models,SimE-ER is more effective in extracting the entity (relation) features and represents entity and relation features more flexibly and comprehensively. Besides,SimE-ER has lower time and memory complexities, which indicates that it is applicable on large-scale knowledge graphs. In experiments, our approach is evaluated on entity prediction and relation prediction tasks. The results prove thatSimE-ER achieves state-of-the-art performances. We will explore the following future work:(i)
In addition to the facts in knowledge graph, there also are large amount of logic and hierarchical correlations between different facts. How to translate these hierarchical and logic information into low-dimensional vector space is an attractive and valuable problem.(ii)
In real world, extracting relations and entities from large-scale text information is an important yet open problem. Combining latent features of knowledge graph and text sets is a feasible method to construct the connection between structured and unstructured data. It is supposed to enhance the accuracy and efficiency of entity (relation) extraction.



---

*Source: 6325635-2018-07-15.xml*