Multilingual Knowledge Graph Embeddings for Cross-lingual Knowledge Alignment

1 Introduction

Multilingual knowledge bases such as Wikipedia [Wikipedia, 2017], WordNet [Bond and Foster, 2013], and ConceptNet [Speer and Havasi, 2013] are becoming essential sources of knowledge for people and AI-related applications. These knowledge bases are modeled as knowledge graphs that store two aspects of knowledge: the monolingual knowledge that includes entities and relations recorded in the form of triples, and the cross-lingual knowledge that matches the monolingual knowledge among various human languages.

The coverage issue of monolingual knowledge has been widely addressed, and parsing-based techniques for completing monolingual knowledge bases have been well studied in the past [Culotta and Sorensen, 2004; Zhou et al., 2005; Sun et al., 2011]. More recently, much attention has been paid to embedding-based techniques, which provide simple methods to encode entities in low-dimensional embedding spaces and capture relations as means of translations among entity vectors. Given a triple (h, r, t) where r is the relation between entities h and t, then h and t are represented as two k-dimensional vectors h and t, respectively. A function fr(h, t) is used to measure the plausibility of (h, r, t), which also implies the transformation r that characterizes r. Exemplarily, the translation-based model TransE [Bordes et al., 2013] uses the loss function fr(h, t) = ‖h+ r - t‖ 1 , where r is characterized as a translation vector learnt from the latent connectivity patterns in the knowledge graph. This model provides a flexible way of predicting a missing item in a triple, or verifying the validity of a generated triple. Other works like TransH [Wang et al., 2014] and TransR [Lin et al., 2015], introduce different loss functions that represent the relational translation in other forms, and have achieved promising results in completing the knowledge graphs.

While embedding-based techniques can help improve the completeness of monolingual knowledge, the problem of applying these techniques on cross-lingual knowledge remains largely unexplored. Such knowledge, including inter-lingual links (ILLs) that match the same entities, and triple-wise alignment (TWA) that represents the same relations, is very helpful in synchronizing different language-specific versions of a knowledge base that evolve independently, as needed to further improve applications built on knowledge bases, such as Q&A systems, semantic Web, and Web search. In spite of its importance, this cross-lingual knowledge remains largely intact. In fact, in the most successful knowledge base Wikipedia, we find that ILLs cover less than 15% entity alignment.

Leveraging knowledge graph embeddings to cross-lingual knowledge no doubt provides a generic way to help extract and apply such knowledge. However, it is a non-trivial task to find a tractable technique to capture the cross-lingual transitions 2 . Such transitions are more difficult to capture than relational translations for several reasons: (i) a cross-lingual transition has a far larger domain than any monolingual relational translation; (ii) it applies on both entities and relations, which have incoherent vocabularies among different languages; (iii) the known alignment for training such transitions usually accounts for a small percentage of a knowledge base. Moreover, the characterization of monolingual knowledge graph structures has to be well-preserved to ensure the correct representation of the knowledge to be aligned.

1 Hereafter, ‖ · ‖ means l1 or l2 norm unless explicitly specified.

To address the above issues, we propose a multilingual knowledge graph embedding model MTransE, that learns the multilingual knowledge graph structure using a combination of two component models, namely knowledge model and alignment model. The knowledge model encodes entities and relations in a language-specific version of knowledge graph. We explore the method that organizes each languagespecific version in a separated embedding space, in which MTransE adopts TransE as the knowledge model. On top of that, the alignment model learns cross-lingual transitions for both entities and relations across different embedding spaces, where the following three representations of crosslingual alignment are considered: distance-based axis calibration, translation vectors, and linear transformations. Thus, we obtain five variants of MTransE based on different loss functions, and identify the best variant by comparing them on cross-lingual alignment tasks using two partially aligned trilingual graphs constructed fromWikipedia triples. We also show that MTransE performs as well as its monolingual counterpart TransE on monolingual tasks.

The rest of the paper is organized as follows. We first discuss the related work, and then introduce our approach in the section that follows. After that we present the experimental results, and conclude the paper in the last section.

2 RelatedWork

While, at the best of our knowledge, there is no previous work on learning multilingual knowledge graph embeddings, we will describe next three lines of work which are closely related to this topic.

Knowledge Graph Embeddings. Recently, significant advancement has been made in using the translation-based method to train monolingual knowledge graph embeddings. To characterize a triple (h, r, t), models of this family follow a common assumption hr + r ≈ tr, where hr and tr are either the original vectors of h and t, or the transformed vectors under a certain transformation w.r.t. relation r. The forerunner TransE [Bordes et al., 2013] sets hr and tr as the original h and t, and achieves promising results in handling 1-to-1 relations. Later works improve TransE on multimapping relations by introducing relation-specific transformations on entities to obtain different hr and tr, including projections on relation-specific hyperplanes in TransH [Wang et al., 2014], linear transformations to heterogeneous relation spaces in TransR [Lin et al., 2015], dynamic matrices in TransD [Ji et al., 2015], and other forms [Jia et al., 2016; Nguyen et al., 2016]. All these variants of TransE specialize entity embeddings for different relations, therefore improving knowledge graph completion on multi-mapping relations at the cost of increased model complexity. Meanwhile translation-based models cooperate well with other models. For example, variants of TransE are combined with word embeddings to help relation extraction from text [Weston et al., 2013; Zhong et al., 2015].

2 We use the word transition here to differentiate from the relational translations among entities in translation-based methods.

In addition to these , there are non-translation-based methods. Some of those including UM [Bordes et al., 2011], SE [Bordes et al., 2012], Bilinear [Jenatton et al., 2012], and HolE [Nickel et al., 2016], do not explicitly represent relation embeddings. Others including neural-based models SLM [Collobert and Weston, 2008] and NTN [Socher et al., 2013], and random-walk-based model TADW [Yang et al., 2015a], are expressive and adaptable for both structured and text corpora, but are too complex to be incorporated into an architecture supporting multilingual knowledge.

Multilingual Word Embeddings. Several approaches learn multilingual word embeddings on parallel text corpora. Some of those can be extended to multilingual knowledge graphs, such as LM [Mikolov et al., 2013] and CCA [Faruqui and Dyer, 2014] which induce offline transitions among pre-trained monolingual embeddings in forms of linear transformations and canonical correlation analysis respectively. These approaches do not adjust the inconsistent vector spaces via calibration or jointly training with the alignment model, thus fail to perform well on knowledge graphs as the parallelism exists only in small portions. A better approach OT [Xing et al., 2015] jointly learns regularized embeddings and orthogonal transformations, which is however found to be overcomplicated due to the inconsistency of monolingual vector spaces and the large diversity of relations among entities.

Knowledge Bases Alignment. Some projects produce crosslingual alignment in knowledge bases at the cost of extensive human involvement and designing hand-crafted features dedicated to specific applications. Wikidata [Vrandeˇci´c, 2012] and DBpedia [Lehmann et al., 2015] rely on crowdsourcing to create ILLs and relation alignment. YAGO [Mahdisoltani et al., 2015] mines association rules on known matches, which combines many confident scores and requires extensively fine tuning. Many other works require sources that are external to the graphs, from well-established schemata or ontologies [Nguyen et al., 2011; Suchanek et al., 2011; Rinser et al., 2013] to entity descriptions [Yang et al., 2015b], which being unavailable to many knowledge bases such as YAGO, WordNet, and ConceptNet [Speer and Havasi, 2013]. Such approaches also involve complicated model dependencies that are not tractable and reusable. By contrast, embedding-based methods are simple and general, require little human involvement, and generate task-independent features that can contribute to other NLP tasks.

3 Multilingual Knowledge Graph Embeddings

We hereby begin our modeling with the formalization of multilingual knowledge graphs.

3.1 Multilingual Knowledge Graphs

In a knowledge base KB, we use L to denote the set of languages, and L2 to denote the 2-combination of L (i.e., the set of unordered language pairs). For a language L ∈ L, GL denotes the language-specific knowledge graph of L, and EL and RL respectively denote the corresponding vocabularies of entity expression and relation expression. T = (h, r, t) denotes a triple in GL such that h, t ∈ EL and r ∈ RL. Boldfaced h, r, t respectively represent the embedding vectors of head h, relation r, and tail t. For a language pair (L1,L2) ∈ L2 , δ(L1,L2) denotes the alignment set which contains the pairs of triples that have already been aligned between L1 and L2. For example, across the languages English and French, we may have ((State of California, capital city, Sacramento), ( ´Etat de Californie, capitale, Sacramento)) ∈ δ(English, French). The alignment set commonly exists in a small portion in a multilingual knowledge base [Vrandeˇci´c, 2012; Mahdisoltani et al., 2015; Lehmann et al., 2015], and is one part of knowledge we want to extend.

Our model consists of two components that learn on the two facets of KB: the knowledge model that encodes the entities and relations from each language-specific graph structure, and the alignment model that learns the cross-lingual transitions from the existing alignment. We define a model for each language pair from L2 that has a non-empty alignment set. Thus, for a KB with more than two languages, a set of models composes the solution. In the following, we use a language pair (Li, Lj) ∈ L2 as an example to describe how we define each component of a model.

3.2 Knowledge Model

For each language L ∈ L, a dedicated k-dimensional embedding space RkL is assigned for vectors of EL and RL, where R is the field of real numbers. We adopt the basic translationbased method of TransE for each involved language, which benefits the cross-lingual tasks by representing embeddings uniformly in different contexts of relations. Therefore its loss function is given below:

It measures the plausibility of all given triples. By minimizing the loss function, the knowledge model preserves monolingual relations among entities, while also acts as a regularizer for the alignment model. Meanwhile, the knowledge model partitions the knowledge base into disjoint subsets that can be trained in parallel.

3.3 Alignment Model

The objective of the alignment model is to construct the transitions between the vector spaces of Li and Lj. Its loss function is given as below:

for which the alignment score Sa(T, T ′ ) iterates through all pairs of aligned triples. Three different techniques to score the alignment are considered: distance-based axis calibration, translation vectors, and linear transformations. Each of them is based on a different assumption, and constitutes different forms of Sa alongside.

Distance-based Axis Calibration. This type of alignment models penalize the alignment based on the distances of cross-lingual counterparts. Either of the following two scorings can be adopted to the model.

Sa1 regulates that correctly aligned multilingual expressions of the same entity tend to have close embedding vectors. Thus by minimizing the loss function that involves Sa1 on known pairs of aligned triples, the alignment model adjusts axes of embedding spaces towards the goal of coinciding the vectors of the same entity in different languages.

Sa2 overlays the penalty of relation alignment to Sa1 to explicitly converge coordinates of the same relation.

The alignment models based on axis calibration assume analogous spatial emergence of items in each language. Therefore, it realizes the cross-lingual transition by carrying forward the vector of a given entity or relation from the space of the original language to that of the other language.

Translation Vectors. This model encodes cross-lingual transitions into vectors. It consolidates alignment into graph structures and characterizes cross-lingual transitions as regular relational translations. Hence Sa3 as below is derived.

ve ij and vr ij thereof are respectively deployed as the entitydedicated and relation-dedicated translation vectors between Li and Lj , such that we have e+ve ij ≈ e′ for embedding vectors e, e′ of the same entity e expressed in both languages, and r + vr ij ≈ r′ for those of the same relation. We deploy two translation vectors instead of one, because there are far more distinct entities than relations, and using one vector easily leads to imbalanced signals from relations.

Such a model obtains a cross-lingual transition of an embedding vector by adding the corresponding translation vector. Moreover, it is easy to see that ve ij = -ve ji and vr ij = -vr ji hold. Therefore, as we obtain the translation vectors from Li to Lj, we can always use the same vectors to trans-

late in the opposite direction.

Linear Transformations. The last category of alignment models deduce linear transformations between embedding spaces. Sa4 as below learns a k × k square matrix Meij as a linear transformation on entity vectors from Li to Lj , given k as the dimensionality of the embedding spaces.

Sa5 additionally brings in a second linear transformationMrij for relation vectors, which is of the same shape as Meij . The use of a different matrix is again due to different redundancy of entities and relations.

Notation: e and r are respectively the vectors of an entity e and a relation r, k is the dimension of the embedding spaces, l is the cardinality of L, ne and nr are respectively the number of entities and the number of relations, where ne ≫ nr .

Unlike axis calibration, linear-transformation-based alignment model treats cross-lingual transitions as the topological transformation of embedding spaces without assuming the similarity of spatial emergence.

The cross-lingual transition of a vector is obtained by applying the corresponding linear transformation. It is noteworthy that, regularization of embedding vectors in the training process (which will be introduced soon after) ensures the invertibility of the linear transformations such that Meij -1 = Meji andMrij -1 =Mrji . Thus the transition in the revert direction is always enabled even though the model only learns the transformations of one direction.

3.4 Variants of MTransE

Combining the above two component models, MTransE minimizes the following loss function J = SK + αSA, where α is a hyperparameter that weights SK and SA.

As we have given out five variants of the alignment model, each of which correspondingly defines its specific way of computing cross-lingual transitions of embedding vectors. We denote Vark as the variant of MTransE that adopts the k-th alignment model which employs Sak . In practice, the searching of a cross-lingual counterpart for a source is always done by querying the nearest neighbor from the result point of the cross-lingual transition. We denote function τij that maps a cross-lingual transition of a vector from Li to Lj, or simply τ in a bilingual context. As stated, the solution in a multi-lingual scenario consists of a set of models of the same variant defined on every language pair in L2 . Table 1 summarizes the model complexity, the definition of cross-lingual transitions, and the complexity of searching a cross-lingual counterpart for each variant.

3.5 Training

We optimize the loss function using on-line stochastic gradient descent [Wilson and Martinez, 2003]. At each step, we update the parameter θ by setting θ ← θ - λ∇θJ, where λ is the learning rate. Instead of directly updating J, our implementation optimizes SK and αSA alternately. In detail, at each epoch we optimize θ ← θ - λ∇θSK and θ ← θ - λ∇θαSA in separated groups of steps.

We enforce the constraint that the l2 norm of any entity embedding vector is 1, thus regularize embedding vectors to a unit spherical surface. This constraint is employed in the literature [Bordes et al., 2013; 2014; Jenatton et al., 2012] and has two important effects: (i) it helps avoid the case Table 3: Number of entity inter-lingual links (ILLs).

where the training process trivially minimizes the loss function by shrinking the norm of embedding vectors, and (ii) it implies the invertibility of the linear transformations [Xing et al., 2015] for Var4 and Var5.

We initialize vectors by drawing from a uniform distribution on the unit spherical surface, and initialize matrices using random orthogonal initialization [Saxe et al., 2014]. Negative sampling is not employed in training, which we find does not noticeably affect the results.

4 Experiments

In this section, we evaluate the proposed methods on two cross-lingual tasks: cross-lingual entity matching, and triplewise alignment verification. We also conduct experiments on two monolingual tasks. Besides, a case study with knowledge alignment examples is included in the Appendix of [Chen et al., 2017].

Data Sets. Experimental results on the trilingual data sets WK3l are reported in this section. WK3l contains English (En), French (Fr), and German (De) knowledge graphs under DBpedia's dbo:Person domain, where a part of triples are aligned by verifying the ILLs on entities, and multilingual labels of the DBpedia ontology on some relations. The number of entities in each language is adjusted to obtain two data sets. For each of the three languages thereof, WK3l-15k matches the number of nodes (about 15,000) with FB15k-the largest monolingual graph used by many recent works [Zhong et al., 2015; Lin et al., 2015; Ji et al., 2015; Jia et al., 2016], and the number of nodes in WK3l-120k is several times larger. For both data sets, German graphs are sparser than English and French graphs. We also collect extra entity ILLs for the evaluation of cross-lingual entity matching, whose quantity is shown in Table 3. Meanwhile, we derive another trilingual data set CN3l from ConceptNet [Speer and Havasi, 2013]. Additional results on CN3l that lead to similar evaluation conclusions are reported in the Appendix of [Chen et al., 2017].

4.1 Cross-lingual EntityMatching

The objective of this task is to match the same entities from different languages in KB. Due to the large candidate space, this task emphasizes more on ranking a set of candidates rather than acquiring the best answer. We perform this task on both data sets to compare five variants of MTransE.

To show the superiority of MTransE, we adapt LM, CCA, and OT (which are introduced in Section 2) to their knowledge graph equivalences.

Evaluation Protocol. Each MTransE variant is trained on a complete data set. LM and CCA are implemented by inducing the corresponding transformations across separately trained knowledge models on monolingual graphs, while using the alignment sets as anchors. Training OT is quite similar to MTransE, we add the process of orthogonalization to the training of the alignment model, since the regularization of vectors has already been enforced. The entity ILLs are used as ground truth for test. We take these unidirectional links between English-French and English-German, i.e., four directions in total. For each ILL (e, e′ ), we perform a kNN search from the cross-lingual transition point of e (i.e., τ(e)) and record the rank of e′ . Following the convention [Xing et al., 2015; Jia et al., 2016], we aggregate two metrics over all test cases, i.e., the proportion of ranks no larger than 10 Hits@10 (in percentage), and the mean rank Mean. We prefer higher Hits@10 and lower Mean that indicate a better outcome.

For training, we select the learning rate λ among {0.001, 0.01, 0.1}, α among {1, 2.5, 5, 7.5}, l1 or l2 norm in loss functions, and dimensionality k among {50, 75, 100, 125}. The best configuration on WK3l-15k is λ = 0.01, α = 5, k = 75, l1 norm for Var1, Var2, LM, and CCA, l2 norm for other variants and OT. While the best configuration on WK3l120k is λ = 0.01, α = 5, k = 100, and l2 norm for all models. The training on both data sets takes 400 epochs.

Results. We report Hits@10 and Mean for WK3l-15k, and Hits@10 for WK3l-120k, on the four involved directions of cross-lingual matching in Table 4. As expected, without jointly adapting the monolingual vector spaces with the knowledge alignment, LM and CCA are largely outperformed by the rest. While the orthogonality constraint being too strong to be enforced in these cases, OT performs at most closely to the simplest cases of MTransE. For MTransE, Var4 and Var5 outperform the other three variants under all settings. The fairly close results obtained by these two variants indicate that the interference caused by learning an additional relation-dedicated transformation in Var5 is negligible to the entity-dedicated transformation. Correspondingly, we believe that the reason for Var3 to be outperformed by Var4 and Var5 is that it fails to differentiate well the over-frequent crosslingual alignment from regular relations. Therefore, the characterization for cross-lingual alignment is negatively affected by the learning process for monolingual relations in a visible degree. Axis calibration appears to be unstable on this task. We hypothesize that this simple technique is affected by two factors: coherence between language-specific versions, and density of the graphs. Var2 is always outperformed by Var1 due to the negative effect of the calibration based on relations. We believe this is because multi-mapping relations are not so well-captured by TransE as explained in [Wang et al., 2014], therefore disturb the calibration of the entire embedding spaces. Although Var1 still outperforms Var3 on entity matching between English and French graphs in WK3l-15k, coherence somewhat drops alongside when scaling up to the larger data set so as to hinder the calibration. The German graphs are sparse, thus should have set a barrier for precisely constructing embedding vectors and hindered calibration on the other side. Therefore Var1 still performs closely to Var3 in the English-German task on WK3l-15k and English-French task on WK3l-120k, but is outperformed by Var3 in the last setting. In general, the variants that use linear transformations are the most desired. This conclusion is supported by their promising outcome on this task, and it is also reflected in the precision-recall curves shown in Figure 1.

4.2 Triple-wise Alignment Verification

This task is to verify whether a given pair of aligned triples are truly cross-lingual counterparts. It produces a classifier that helps with verifying candidates of triple matching [Nguyen et al., 2011; Rinser et al., 2013].

Evaluation Protocol. We create positive cases by isolating 20% of the alignment set. Similar to [Socher et al., 2013], we randomly corrupt positive cases to generate negative cases. In detail, given a pair of correctly aligned triples (T, T ′ ), it is corrupted by (i) randomly replacing one of the six elements in the two triples with another element from the same language, or (ii) randomly substituting either T or T ′ with another triple from the same language. Cases (i) and (ii) respectively contribute negative cases that are as many as 100% and 50% of positive cases. We use 10-fold cross-validation on these cases to train and evaluate the classifier.

We use a simple threshold-based classifier similar to the widely-used ones for triple classification [Socher et al., 2013; Wang et al., 2014; Lin et al., 2015]. For a given pair of aligned triples (T, T ′ ) = ((h, r, t), (h′ , r′ , t′ )), the dissimilarity function is defined as fd(T, T ′ ) = ‖τ(h) -h′ ‖2 + ‖τ(r) - r′ ‖2 + ‖τ(t) - t′ ‖2 . The classifier finds a threshold σ such that fd < σ implies positive, otherwise negative. The value of σ is determined by maximizing the accuracy for each fold on the training set. Such a simple classification rule adequately relies on how precisely each model represents cross-lingual transitions for both entities and relations.

We carry forward the corresponding configuration from the last experiment, just to show the performance of each variant under controlled variables.

Results. Table 5 shows the mean accuracy, with a standard deviation below 0.009 in cross-validation for all settings. Thus, the results are statistically sufficient to reflect the performance of classifiers. Note that the results appear to be better than those of the previous task since this is a binary classification problem. Intuitively, the linear-transformationbased MTransE perform steadily and take the lead on all settings. We also observe that Var5, though learns an additional relation-dedicated transformation, still performs considerably close to Var4 (the difference is at most 0.85%). The simple Var1 is the runner-up, and is between 1.65% and 3.79% to the optimal solutions. However the relation-dedicated calibration in Var2 causes a notable setback (4.12%∼8.44% from the optimal). The performance of Var3 falls behind slightly more than Var2 (4.52%∼10.79% from the optimal) due to the failure in distinguishing cross-lingual alignment from regular relations. Meanwhile, we single out the accuracy on the portion of negative cases where only the relation is corrupted for English-French in WK3l-15k. The five variants receive 97.73%, 93.78%, 82.34%, 98.57%, and 98.54%, respectively. The close accuracy of Var4 and Var5 indicates that the only transformation learnt from entities in Var4 is enough to substitute the relation-dedicated transformation in Var5 for discriminating relation alignment, while learning the additional transformation in Var5 does not notably interfere the original one. However, it applies differently to axis calibration since Var2 does not improve but actually impairs the cross-lingual transitions for relations. For the same reasons as above, LM and CCA do not match with MTransE in this experiment as well, while OT performs closely to some variants of MTransE, but is still left behind by Var4 and Var5.

4.3 Monolingual Tasks

The above experiments have shown the strong capability of MTransE in handling cross-lingual tasks. Now we report the results on comparing MTransE with its monolingual counterpart TransE on two monolingual tasks introduced in the literature [Bordes et al., 2013; 2014], namely tail prediction (predicting t given h and r) and relation prediction (predicting r given h and t), using the English and French versions of our data sets. Like previous works [Bordes et al., 2013; Wang et al., 2014; Jia et al., 2016], for each language version, 10% triples are selected as the test set, and the remaining becomes the training set. Each MTransE variant is trained upon both language versions of the training set for the knowledge model, while the intersection between the alignment set and the training set is used for the alignment models. TransE is trained on either language version of the training set. Again, we use the configuration from the previous experiment.

Results. The results for Hits@10 are reported in Tables 6 and 7. They imply that MTransE preserves well the characterization of monolingual knowledge. For each setting, Var1, Var4, and Var5 perform at least as well as TransE, and some even outperforms TransE under certain settings. This signifies that the alignment model does not interfere much with the knowledge model in characterizing monolingual relations, but might have actually strengthened it since coherent portions of knowledge are unified by the alignment model. Since such coherence is currently not measured, this question is left as a future work. The other question that deserves further attention is, how other knowledge models involving relation-specific entity transformations [Wang et al., 2014; Lin et al., 2015; Ji et al., 2015; Jia et al., 2016; Nguyen et al., 2016] may influence monolingual and cross-lingual tasks.

5 Conclusion and FutureWork

At the best of our knowledge, this paper is the first work that generalizes knowledge graph embeddings to the multilingual scenario. Our model MTransE characterizes monolingual relations and compares three different techniques to learn crosslingual alignment for entities and relations. Extensive experiments on the tasks of cross-lingual entity matching and triple alignment verification show that the linear-transformationtechnique is the best among the three. Moreover, MTransE preserves the key properties of monolingual knowledge graph embeddings on monolingual tasks.

The results here are very encouraging, but we also point out opportunities for further work and improvements. In particular, we should explore how to substitute the simple loss function of the knowledge model used in MTransE with more advanced ones involving relation-specific entity transformations. More sophisticated tasks of cross-lingual triple completion may also be conducted. Combining MTransE with multilingual word embeddings [Xing et al., 2015] is another meaningful direction since it will provide a useful tool to extract new relations frommultilingual text corpora.