TransR * : Representation learning model by flexible translation and relation matrix projection

TransE. The algorithmic idea of the TransE model [5] is: entities and relations are mapped to the vector space, and the representation of entities and relations becomes the representation between vectors; at the same time, consider the relation r in each triple instance (h, r, t) as a translation from entity h to entity t.

TransH. The algorithmic idea of the TransH model [6] is: try to express the entity structure in different relationships by different forms, and for the same entity, it also plays different roles under different relationships; firstly, the model selects a hyperplane through the relation vector and its orthogonal normal vector, and then projects the head entity vector and tail entity vector into the hyperplane along the direction of the normal vector; finally, the loss function is calculated.

TransR. The algorithm idea of the TransR model [13] is: for each type of relationship, not only has a vector r to describe itself, but also a mapping matrix M _r to describe the relationship space in which the relationship is located. The entity and relationship are respectively mapped to the entity vector space and relationship vector space.

2.2 Other models

The NTransGH model [14] combines a transformation mechanism that models a relationship as a transformation operation of a generalized hyperplane, and a neural network that captures more complex interactions between entities and relationships. The SProje model [15] introduces an adaptive measurement method to reduce the influence of noise information. On this basis, by further optimizing the loss function to increase the loss weight of the complex relationship triples. The TransGraph model [16] is based on the ability of TransE to learn the characteristics of the triplet and the knowledge graph network structure simultaneously, which enhances the representation effect of the knowledge graph effectively; in order to achieve the deep integration of network structure information and triplet information, a cross-training mechanism for vector sharing is presented. The STransH model [17] is modeled in the entity space and the relationship space, and uses the nonlinear operation of a single-layer neural network to strengthen the semantic connection between entities and relationships. At the same time, inspired by the TransH model, the mechanism of projecting to a specific relationship hyperplane is introduced, so that entities have different roles in different relationships. The SME model [3] proposes more complex operations to portray the internal connections between entities and relationships. The SE model [2] introduce a new method for automatically learning the embedding of a structured distributed knowledge base. The NTN model [6] uses bilinear vectors to replace the linear transformation layer in traditional neural networks. The Unstructured model [1] is a specific framework for performing semantic analysis on free text. The RESCAL model [9] is the representative of the matrix factorization model, which uses the matrix factorization method for knowledge representation learning. The DistMult model [10] uses embedding without explicit logical constraints to mine logical rules directly from the knowledge base. HolE model [11] proposes using holographic embedding to learn the combined vector space representation of the entire knowledge graph. The ComPlEX model [12] discusses the application of complex embeddings in low-rank matrix factorization.

3.1 Our motivation

TransR model projects the head entity and tail entity of each triple (h, r, t) in the knowledge base into the relational space through a mapping matrix, so that h _r  + r ≈ t _r (Fig. 1(a) represents the entity space, Fig. 1(b) represents the relationship space); and construct a corresponding vector space for each relationship, and separate entities and relationships in different vector spaces [13]. The TransR model solves the problem that the TransE model and TransH model may not be sufficient for modeling in public spaces. It is a very potential knowledge representation learning model. However, the TransR model still uses the translation principle of h _r  + r ≈ t based on the TransE model, and this constraint is still too strict. When different entities are very similar, the TransR model’s ability to distinguish between different entities is still low, which makes it less effective when dealing with complex types of relationships.

OPEN IN VIEWER

Fig. 1

Algorithm idea of TransR model.

Where circles represent specific relational projections, and triangles represent entities that do not have h _r  + r ≈ t _r relations. The dots refer to entities that satisfy the h _r  + r ≈ t _r relationship.

In order to solve the problem that the TransR model has low distinguishing ability for different entities that are very similar, we propose the relational matrix projection model TransR* based on the principle of flexible translation. We put forward the principle of flexible translation for the first time, and its translation principles is: For each triplet (h, r, t), assuming that r and t are given, then we allow h to have the same direction but different sizes, and ϕ is adjusted as a hyperparameter (e.g. Fig. 2(a)); Similarly, assuming that h and t are given, we allow r to have the same direction and different sizes, and β as a hyperparameter to adjust (e.g. Fig. 2(b)); h and r are given, we allow t to have the same direction but different sizes, and λ is adjusted as a hyperparameter (e.g. Fig. 2(c)).

OPEN IN VIEWER

Fig. 2

Principles of flexible translation.

Considering the problem of random errors in the experiment, it is possible that h +ϕ+ r is not enough to equal t, h + r +β is not enough to equal t, and h + r is not enough to equal t +λ. Therefore, we set three random numbers j₁, j₂, j₃ as error adjustment. The situation after setting the random number is shown in Fig. 3(a-c):

OPEN IN VIEWER

Fig. 3

The principle of flexible translation after setting a specific range of random numbers.

In translation, the embedding of entities and relationships are in the same space. The translation principle is defined as:

( h + ϕ + j 1 ) + ( r + β + j 2 ) ≈ ( t + λ + j 3 )(1)

Among them, ϕ, β, λ, j₁, j₂, j₃ ɛ R^m×n. Correspondingly, the scoring function is: f r ( h , t ) = | | h + r - t + μ ∥ l 1 / l 2(2) μ = ϕ + j 1 + β + j 2 - ( λ + j 3 )(3)

On the basis of TransR model relation matrix projection, we added the principle of flexible translation proposed by us. In the relational representation space of r, for a given r and t _r , the head entity is represented by h _r  + ϕ + j₁ (e.g. Fig. 4(a)); for a given h _r and t _r , the relation is represented by r +β+j₂ (e.g. Fig. 4(b)); for a given h _r and r, the tail entity is represented by t _r +λ+j₃ (e.g. Fig. 4(c)). The score function of TransR* is:

OPEN IN VIEWER

Fig. 4

Algorithm idea of TransR* model.

f r ( h , t ) = | | h r + r - t r + u | | l 1 / l 2(4)

In model training, constructing negative triples is an important task. The method we use is the probability method, which replaces the head and tail entities with different probabilities. When generating negative triples, the selected strategy is to replace entities for different relationship types. Specifically, for a N-to-1 relationship, choose a higher probability to replace the tail entity; for a 1-to-N relationship, choose a higher probability to replace the head entity. Since an entity contains multiple attributes, when dealing with N-to-1 relationships, replacing the tail entity can fully train multiple attributes of the tail entity; when dealing with 1-to-N relationships, replacing the head entity can also make the head entity’s multiple attributes are fully trained [17].

(1) Probability method replaces head and tail entities

During model training, we can get the following data: first, the average number of tail entities corresponding to each head entity tqh; second, the average number of head entities corresponding to each tail entity hqt. When we use the probability method, we sample according to the Bernoulli distribution of q = tqh / (tqh + hqt). When we use positive triples to construct negative triples, we replace the head entity with probability q, and replace the tail entity with probability 1-q, so that the total probability is 1, and the sampling method conforms to Bernoulli distribution. The Bernoulli distribution is chosen, because this method can bring two benefits: first, it can increase the probability of getting a positive triplet, and second, it can reduce the computational complexity.

We stipulate that when tqh < 1.5 and hqt < 1.5, then the relationship r is 1-to-1; when tqh > 1.5 and hqt > 1.5, then the relationship r is N-to-N; when tqh≥1.5 and hqt < 1.5, Then it means that the relation r is 1-to-N; when tqh < 1.5 and hqt≥1.5, it means that the relation r is N-to-1 [26].

(2) The prior probability of the relationship

We use the prior probability of the relationship to solve the problem of encoding similar relationships. That is, the more times a relationship appears, the greater the probability that the entity pair (h, t) has the relationship. Given the candidate triples (h, r, t), we determine the prior probability of the relation r by comparing the most similar relation r’ to the given relation r. The specific formula is as follows: p r ( r ) = N r N r + N r ′(5)

Where N_r is the number of times the relationship r appears in the training set, and N_r’ is the relationship most similar to the relationship r. In the model training process, in order to distinguish between positive triples and negative triples, the following margin-based loss function is used as the optimization objective function of the training model: L = ∑ ( h , r , t ) ∈ S ∑ ( h ′ , r , t ′ ) ∈ S ′ max ( f r ( h , t ) + γ - f r ( h ′ , t ′ ) , 0 )(6)

Where S represents the set of positive triples, the relational matrix projection S’ represents the set of negative triples, and max (x, y) refers to the larger value between x and y, γ represents the distance between the score of the loss function of the positive triple and the score of the loss of the negative triple. Therefore, the optimization goal of this objective function is to separate the positive triples from the negative triples to the greatest extent.

4.1 Data set

When selecting the data set, consider the need to compare the data with the classic TransE, TransH, TransR, Unstructured, SE, SME, LFM, NTN and other models. Therefore, we chose the common datasets for these models: two subsets WN18 and WN11 in WordNet [23, 27], and two subsets FB15K and FB13 in Freebase [18]. Among them, FB15K is considered to be a large data set due to the relatively large number of relations. The specific number of entities and relations are shown in Table 2.

Given an entity and relationship in the triplet, the purpose of the link prediction task is to predict the correct other entity [19, 28]. For example, given the head entity “United States” and the relationship “capital”, it is predicted that the tail entity should be “Washington”. Link prediction can find the missing knowledge in the knowledge graph and is an important means of knowledge completion.

Evaluation index. In the link prediction task, the average ranking (Mean Rank) and the top 10 probability rate (Hits@10) are used to evaluate the quality of the model [18]. For a triple in the test set, use any other entity in the knowledge graph as the wrong entity, and replace the original correct head entity or tail entity in the triple to construct a negative triple. The link prediction task sorts the original triples and all negative triples after scoring. The first sorting indicates that it is more likely to predict that it is the correct triplet, and the lower sorting indicates that it is less likely to be the correct triplet. Lower Mean Rank and higher Hits@10 means better prediction effect.

When constructing the negative example triples, one entity in the original correct triples is replaced with any other entity in the knowledge graph. There is a situation: the new triples generated by the replacement originally exist in the knowledge graph. In this case, the newly generated triples may rank higher than the original correct triples, which will interfere with the prediction results. Therefore, it is necessary to remove the existing part in the newly generated triplet. This filtered experiment is called “Filter", and the experiment without removal is called “Raw".

Experimental realization. We chose some representative models as the basis for comparison, such as Unstructured, RESCAL, SE, SME, LFM, NTN, TransE, TransH, TransR etc. In the process of reproducing experiments, due to parameter settings, random initialization of parameters, and differences in the experimental environment, we did not get the best results in the references. However, considering that the same data set is used and the same indicators are selected, we directly use the best experimental data in the references. In addition, in order to reduce the impact of accidental experimental data on the experimental results, we repeated each task 10 times; then, the average of the 10 results was taken as the final result. When training TransR*, the learning rate α among {0.0001, 0.001, 0.005, 0.01}, the margin γ among {1, 1.5, 2, 3, 3.5, 4}, the embedding dimension k among {50, 100, 150, 200}, the hyperparameter μ among {0, 0.1, 0.5, 1, 2}, the random numbers j₁, j₂, j₃ between (0.0001, 0.001), and the batch size B among {20, 50, 75, 120, 4800, 9600}. The best parameters are determined by the validation set.

Under the “unif” setting, the best configuration is: on WN18, μ= 0.1, α= 0.0001, γ= 3.5, k = 50, B = 75; on FB15K, μ= 0.1, α= 0.001, γ= 3, k = 50, B = 50. Under the “bern” setting, the best configuration is: on WN18, μ= 0.1, α= 0.0001, γ= 3.5, k = 50, B = 75; on FB15K, μ= 0.1, α= 0.001, γ= 3, k = 50, B = 50. For these two data sets, this experiment will iterate all training triples 500 times.

Experimental results. It can be seen from Table 3 that on the WN18 data set, TransR* (unif) and TransR* (bern) are better than other methods in Mean Rank and Hits@10. Among them, in the Hits@10 indicator, TransR* is 2.6% higher than TransR. This may be because the number of relationships in WN18 is relatively small, so it is reasonable to ignore different types of relationships. On the FB15K data set, in the index of Hits@10, TransR* is 2.9% higher than TransR.

In order to prove that TransR* has better expressive ability and can better handle complex relationships. We conducted an in-depth analysis of the FB15K data set and found that the number of 1-to-1 relationships in FB15K reached 323, the number of 1-to-N relationships reached 309, the number of N-to-1 relationships reached 390, and the number of N-to-N relationships reached 323. Thus, FB15K can be used as a large data set. We used the optimal configuration parameters of the TransR* model on FB15K, and tested the scores of the model under the relationship of 1-to-1, 1-to-N, N-to-1, and N-to-N. From the experimental results in Table 4, it can be seen that the TransR* model achieves the best results on Predicting Left and Predicting Right, which is better than other models. Among them, TransR* reached 92.8% on the 1-to-N relationship of Predicting Left and 93.2% on the N-to-1 relationship of Predicting Right.

Triple classification is used to determine whether a given triple (h, r, t) is correct, and its main task is to classify a triple as “correct” or “wrong” [29]. In the triple classification test, firstly, perform a classification test on the verification set, and maximize the classification accuracy for each relationship r to obtain the classification threshold σ _r ; secondly, when testing the triple (h, r, t), the classification greater than the threshold σ _r is positive, otherwise it is negative; in the training process, the verification set is used to test the model effect, and then the accuracy of triple classification is given on the test set.

Evaluation index. The triple classification task uses the accuracy rate (ACC) as the evaluation index [30]. The higher the ACC, the better the effect of the model on the triple classification task. The calculation method is as follows: ACC = T p + T n N pos + N neg(7)

Where T _p represents the number of positive triples that are predicted correctly; T _n represents the number of negative triples that are predicted correctly; N _pos and N _neg represent the number of positive triples and negative triples in the training set, respectively.

Experimental realization. In the SGD process, we select μ among 0, 0.1, 0.5, 1, 2, the range of random numbers j₁, j₂, j₃ among (0.0001, 0.001), and the range of learning rate α among {0.0001, 0.001, 0.01, 0.1}, the range of the marginal γ among {1, 2, 3, 3.5, 4, 4.5, 5, 10}, the dimension k of the entity vector and the relationship vector among {18, 20, 50, 100, 200}, and the batch size B among {20, 50, 75, 120, 150, 480, 960, 4800}. The accuracy of the best configuration is determined by the validation set. The best configuration on WN11 is: μ= 0.1, α= 0.0001, γ= 4.5, k = 18, B = 4800, and use l₁ as the similarity measure; the best configuration on FB13 is: μ= 0.1, α= 0.0001, γ= 3.5, k = 50, B = 75, and use l₁ as the similarity measure; the best configuration on FB15K is: μ= 0.1, α= 0.0001, γ= 3, k = 50, B = 50, and use l₁ as the similarity measure.

Experimental results. Table 5 lists the evaluation results of triple classification. It can be seen that on WN11, the TransR* model is better than TransR, and on the ACC index, TransR* is improved by 0.3%; on FB13, the NTN model performed best, with TransR* scored lower than TransR. On the FB15K, TransR* performed best. Compared with TransR, the ACC index increased by 13.2%, indicating that the TransR* model is more suitable for large-scale knowledge graphs. This is because there are only 13 relationships in FB13, and the NTN model has certain advantages in tensor decomposition modeling on FB13. However, FB15K has a large number of relations and is relatively sparse, and the performance of NTN is significantly weaker than that of TransR*.