Improving Cross-lingual Entity Alignment via Optimal Transport

1 Introduction

Along with the fast development of knowledge graphs (KGs) in different languages, cross-lingual entity alignment has become increasingly important due to its substantial assistance to many NLP applications. The mission is to align two entities in different KGs if they share the same semantic meaning. Given a number of labeled entity pairs, the alignment problem can be addressed in supervised ways with entity vectors described by human-designed features [Mahdisoltani et al., 2013; Nguyen et al., 2011] or with entity embeddings learned from KG embedding models [Chen et al., 2016; Sun et al., 2017; Wang et al., 2018], as shown in Figure 1(a). However, labeled entity pairs are often difficult to obtain, and thus much less than unlabeled entities. Following ideas in semi-supervised learning, representative works like [Zhu et al., 2017; Chen et al., 2018b; Sun et al., 2018] employ self-training to iteratively retrieval potentially aligned entities from unlabeled samples, then feed them back to update the alignment models. In spite of their success, current solutions minimize the alignment loss function defined at the entity level (focusing on the distance of given or augmented aligned entities), and thus suffer from the following shortcomings:

• Limited gain due to the shortage of labeled entity pairs: labeled entities usually take only a small portion of the entity set. Even though we can iteratively do data augmentation with learned alignment function, the mapping error will be accumulated along with the depth of augmentation. There will be no benefits to gain from data augmentation after certain iterations.
• Ignorance of duality: alignment models through entity embedding map entities of different KGs to the shared concept space. Hence, the distribution of entity embedding should be similar in cross-lingual KGs. From the toy example shown in Figure 1(b), we can see that learned representations of entities in X and Y appear with similar shapes. One overlaps the other by taking a rotation. Such similarity between two distributions has been only explored by learning a translation function fromX M1 --→ Y or Y M2 --→ X, without investigating the dual alignment (X M1 ⇄ M2 Y ) of entities from different KGs.
• Failure on matching the whole distribution: alignment loss functions defined at the entity level serve well the

purpose of aligning labeled entities but fail to match the whole picture of labeled and unlabeled entities in different KGs. In Figure 1(c), the learned mapping function works well on labeled entities, but unlabeled samples in the red circle will impose a large loss since no objective functions of entity alignment have incorporated the group-level loss between embeddings of different KGs.

The aforementioned problems motivate us to design a novel Optimal Transport-based Entity Alignment (OTEA) model that learns the translation matrix by dually minimizing both entity-level and group-level loss. The group-level loss describes the discrepancy between two distributions of different embeddings. However, unlike entity-level loss, the grouplevel loss is difficult to measure using a statistical distance between two probability distributions, because the marginal distributions of two embedding sets are not available. Recently, adversarial training has emerged as a powerful paradigm to address this issue. Generative Adversarial Network (GAN) [Goodfellow et al., 2014] is the representative work for distribution matching. However, GAN still suffers from an unstably weak learning signal due to the problem of JS divergence and the gradient vanishing effect. Inspired by the progress of Optimal Transport (OT), we set group-level loss by the minimum cost of transporting mass in converting the distribution of embedding in X to the distribution of embedding in Y. By jointly minimizing the entity-level and group-level loss, the entity alignment model can improve its generalization ability, and thus the accuracy of entity alignment.

We also propose to impose L2,1 norm of the translation matrix as a regularizer in the alignment loss function, in order to force the translation matrix to be orthogonal. Orthogonal translation matrix is desirable when transforming one isomorphic embedding to another, as theoretically proved in [Smith et al., 2017]. However, it is difficult to enforce the orthogonality of the translation matrix. L2,1 norm has been widely used in machine learning community [Nie et al., 2010] and compressed sensing theory [Yin et al., 2015]. It plays here a new role on regularizing the translation matrix to make orthogonal transformation between two KG embeddings.

Our contributions in this work are summarized as follows:

• We propose to solve entity alignment by dually minimizing both the entity-level loss and the group-level loss via optimal transport theory.
• We impose L2,1 norm on the dual translation matrices, which can enforce the translation matrix to be close to orthogonal.
• We conduct extensive experiments on six real-world datasets and show the superior performance of our proposed model over the state-of-the-art methods, with significant improvement on entity alignment accuracy.

2 RelatedWork

2.1 KGEmbedding

Knowledge graph (KG) embedding has been developed as a fundamental tool to analyze and model the structure and semantic information in KG. Researchers explored semantic matching models which employ the similarity-based scoring functions, like DistMult [Yang et al., 2014]. Many translational distance based models have been developed recently. The most representative translational distance model is TransE [Bordes et al., 2013]. Several approaches improved TransE by introducing relation-specific hyperplanes [Wang et al., 2014], relation-specific spaces [Lin et al., 2015], decomposing the projection matrix into a product of two vectors in TransD [Ji et al., 2015].

2.2 Entity Alignment

Pioneering work proposed to address entity alignment by hand-crafted features [Mahdisoltani et al., 2013]. Crowdsourcing [Vrandeˇci´c and Kr ¨otzsch, 2014] was also employed. These methods suffer from the requirement of heavy human efforts. Alignment by leveraging extra resources was studied in OWL properties [Hu et al., 2011], and entity descriptions [Yang et al., 2015]. However, it is hard to obtain the extra resources for all KGs and modeling different extra resources is a complex process.

Recently, finding alignment using KG embeddings becomes the most popular solution. MTransE [Chen et al., 2016] is the earliest work which encodes entities and relations of languages in a separated embedding space. Encoding entities and relations of different KGs into a unified lowdimensional space jointly [Zhu et al., 2017] is the other way to do alignment. BootEA [Sun et al., 2018] mitigated the problem of lacking labeled data by bootstrapping strategy and achieved a significant performance improvement. Further, JAPE [Sun et al., 2017], KDCoE [Chen et al., 2018b], GCN-based approach [Wang et al., 2018] jointly modeled the structure and attributes information of KGs. However, all these models suffer from the three limitations discussed in the Introduction section.

It is worth noting that entity alignment differs from entity co-reference resolution [Ng and Cardie, 2002] and link discovery [Nentwig et al., 2017] problem, because entity alignment focuses on the alignment of the entity in KGs, rather than text and knowledge bases.

2.3 Optimal Transport

Optimal transport (OT) is the natural geometry for probability measures supported on a geometric space [Peyr´e and Cuturi, 2018]. [Cuturi, 2013] proposed sinkhorn distance to improve the computational problem of OT, and [Arjovsky et al., 2017] views the learning of generative adversarial networks (GANs) as a transportation problem by introducing the Wasserstein distances. OT has been widely used in many tasks which include, but not limited to, image segmentation [Peyr´e et al., 2012], word embedding [Xu et al., 2018] and text generation [Chen et al., 2018a]. Yet, to the best of our knowledge, we are the first to adapt the theory of optimal transport for crosslingual entity alignment between KGs.

3 Methodology

A knowledge graph can be denoted as G = (E, R, T ), where E is the set of entities, R is the set of relations, and T is the set of triples, each of which is a triple (h, r, t), including the head entity h, the relation r and the tail entity t. By using KG embedding, each triple can be presented as (h, r, t), in which boldfaced h, r, and t represent the embedding vectors of head h, relation r, and tail t, respectively. Cross-lingual knowledge graphs are a set of KGs with the language set LA denoted as GLA = {G1,G2, ...,Gi}, where Gi denotes the KG with language i ∈ LA. In our work, we only consider the 1-to-1 entity alignment between two cross-lingual KGs.

Let Gi = (Ei,Ri, Ti) and Gj = (Ej,Rj, Tj) be two KGs in different language i and j. AS = {(ei, ej)|ei ∈ EL i , ej ∈ EL j } is a set of labeled entity pairs that have same meaning, e.g., ei in Gi shares same meaning with its counterpart ej in Gj. Entity alignment is a task to find and align the remaining entities {ei ∈ EU i } and {ej ∈ EU j } which share same meaning, where EU i = Ei\EL i and EU j = Ej \ EL j .

Fig.2 shows the overall framework of our approach. The whole process involves minimizing the loss for knowledge graph embeddings (Lk), the entity-level alignment loss (Le), the group-level alignment loss (Lg) and a regularizer (Lr).

3.1 Knowledge Graph Embedding

We build our model based on the basic TransE [Bordes et al., 2013], like the previous works in [Chen et al., 2016; Zhu et al., 2017; Chen et al., 2018b], as we focus on the alignment problem, rather than KG embedding that has a number of candidate solutions. When employing TransE on both knowledge graphs Gi and Gj, entities and relations are projected into the same low-dimensional space by encoding the triples (h, r, t), and making h + r ≈ t when (h, r, t) holds. Specifically, the embeddings of relations can translate the embeddings of head entities to tail entities. The marginbased ranking objective function minimized by TransE over a knowledge graph Gi is defined as:

where θie presents the learned embedding from Gi, and Lt(h, r, t) is the objective function defined for a triple (h, r, t):

where [x]+ = max{0, x} denotes the positive part of x, γ is a margin hyper-parameter which is greater than 0, and E(h, r, t) indicates the energy function:

and T ′ denotes the negative sample set for the triple (h, r, t):

where (h′ , r, t) and (h, r, t′ ) are the Bernoulli negativesampled triples by replacing h or t in (h, r, t). The loss function of KG embedding for Gi and Gj together is:

3.2 Entity-level Loss

We first define the entity-level loss. After obtaining entity embeddings of graph Gi and Gj from TransE, we make labeled entities aligned by dually minimizing

whereM1 andM2 are the d×d translation matrices, d is the dimension of entity embedding, and α1 is a trade-off parameter. Note that our model dually learns the two translations of two embedding spaces in both directions. That is to say, M1 is learned to transfer the embeddings of Gi into the embedding space of Gj, and M2 is to transfer the embeddings of Gj into the embedding space of Gi.

3.3 Group-level Loss

Then, we define the group-level loss. Setting Gi as the source KG, and Gj is the target KG, as an example. After translating, we can measure howM1 θie and θje are close. At the grouplevel, the embedding distribution of θje should be similar to the distribution of M1 θie . Let p be the distribution of M1 θie , and q be the distribution of θje . We define the group-level loss by measuring the difference between p and q with optimal transport distance, which is [Peyr´e and Cuturi, 2018]:

where ∏(p, q) denotes the set of all joint distributions γ(p, q) with marginals p(x) and q(y); c(x, y) : G×G → R indicates the transportation cost function for moving x to y.

Since p and q are discrete distributions, they can be represented by a sum of Dirac delta functions. That is, p = ∑ni=1 uiδxi and q = ∑mi=1 viδyi with the Dirac function δ. The weight vectors u = {ui}ni=1 ∈ ∆n and v = {vi}mi=1 ∈ ∆m belong to the n and m-dimensional simplex. Then, the distance measure defined in Eq. (7) is equivalent to solving the following network-flow problem [Luise et al., 2018]:

where T denotes the transport matrix, ∏(p, q) is the transport polytope, defined as: ∏(p, q) = {T ∈ Rn×m + |T1m = u,TT 1n = v}, where 1n indicates an n-dimensional all-one vector. The transport matrix T stores information of the transport plan, a non-zero Tij denotes the amount of probability mass transported from xi to yj. When c(x, y) is a metric on G, Dc(p, q) induces a proper metric on the space of probability distribution supported on G, commonly known as the Wasserstein distance [Villani, 2008].

The group-level loss measured by Eq. (8) is hard to calculate directly due to its high computational complexity. According to Kantorovich-Robinstein duality and Farkas Theorem [Villani, 2008], Eq. (8) is equivalent to as follow:

where the supremum is over all K-Lipschitz functions f. Hence, solving the optimal transport problem has been tranformed to optimize Wasserstein GAN [Arjovsky et al., 2017]. We adopt a neural network to approximate the function f, since the neural networks are universal function approximators. A simple MLP can be used as the approximator, also called critic D1. Similar to [Arjovsky et al., 2017], we employ weight clipping to ensure the function family is KLipschitz. The loss function of the critic is defined as:

It means that the critic D1 tries to distinguish the target embeddings and the transferred source embeddings. The D1 denotes the distance between two sets of embeddings. The loss function of the translation matrix is defined as:

where the M1 aims to minimize the approximate distance to fool the critic, such that the critic cannot distinguish the target embeddings and the transferred source embeddings.

Finally, the minimax loss function for group-level loss is defined as follow:

The similar idea applies for the other direction, transferring from target KG to the source KG. We define the similar minimax loss function:

Therefore, we convert the calculation and optimization of group-level loss to the problem of directly optimizing the Wasserstein GAN. By skipping the calculation step, the high computational of OT is avoidable.

3.4 Regularizer

As the discussion in Section 1, the translation matrix is desired to be orthogonal by enforcing the translation matrix to be a sparse matrix, or controlling the trend to be a dense matrix. In our work, we employ L2,1 norm as the regularizer to prevent the translation matrix to be dense.

We define the regularizer (for two translation matrices) as:

Algorithm 1: OTEA

Input: KG Gi and Gj , the set of aligned entity pairs AS. Output: Mappings M1 , M2 . 1 Initialize parameters of critics D1 and D2, embeddings θie, θje, and mappingsM1 , M2 ; 2 for iteration = 1, ... MaxIter do 3 for batch = 1, ... NumBatch K do 4 Sample a batch ˆ Ti of triples (h, r, t) in Gi and ˆ Tj in Gj ; 5 Update θie and θje, according to Lk with the batch ˆ Ti and ˆ Tj ; 6 end 7 for batch = 1, ... NumBatch AS do 8 Sample a batch ˆ AS from AS; 9 Update M1 , M2 , θie, θje according to {Lr + Le} with the batch ˆ AS. 10 end 11 for batch = 1, ... NumBatch G do 12 Sample a batch ˆEi fromEi, and ˆEj fromEj; 13 Update D1, D2 by fixing M1 , θie, M2 , θje, according to Lg1 and Lg2, with weight clipping c; 14 Update M1 , M2 , θie, θje by fixing D1, D2, according to Lg1 and Lg2; 15 end 16 end

where α is the tradeoff parameter.

To demonstrate the effectiveness of L2,1 norm, we show v = ∥∥MMT - I∥∥F which measures how matrix M is far from an orthogonal matrix, in the training process on two datasets in Figure 3. We can observe that M1 and M2 regularized by L2,1 norm are closer to orthogonal than those without regularization. The results demonstrate that the L2,1 norm as a regularizer can effectively prevent the matrix to be dense, and mitigating the error induced by dense matrix.

The overall optimization process of our model is given in Algorithm 1. The embeddings of KGs and matrices are initialized by drawing from a Gaussian and orthogonal initialization, respectively. We use SGD as our optimizers, and normalize all embeddings by L2 norm. The tradeoff parameters are set by grid search. In the testing stage, an entity e in Gi can be aligned by first transferring to Gj as M1 θe and then selecting the most similar entity in Gj. Similarly, an entity e in Gj can be aligned by first transferring to Gi as M2 θe and then selecting the most similar entity in Gi.

4 Experiments

In this section, we conduct experiments on several realworld datasets with different sizes, and evaluate our proposed method for entity alignment. Specifically, we attempt to answer the following research questions:

(RQ1) Can our approach OTEA (OT-based Entity Alignment) outperform the state-of-the-art approaches?

(RQ2) How important the dual alignment is? comparing with the single translation.

• (RQ3) How important the L2,1 regularizer is?
• (RQ4) Sensitivity of the parameter settings and complexity.

4.1 Experimental Design

Datasets. We used three trilingual knowledge graph datasets from WK31 provided in [Chen et al., 2016; Chen et al., 2018b]. English(En), French(Fr), and German(De) knowledge graphs are included in WK31 datasets, and the KGs are extracted from Person domain of DBpedia with known aligned entities as the ground truth. WK31 includes three datasets with different sizes, as shown in Table 1.

Baselines. To comprehensively evaluate the effectiveness of our proposed method, we include the following methods for performance comparison, including: MTransE [Chen et al., 2016] and ITransE [Zhu et al., 2017] encode the KGs in separated embedding space or unified embedding space, respectively. JAPE [Sun et al., 2017] and GCN-based method jointly model the KGs and attributes, we only use the structure part of their models, and BootEA [Sun et al., 2018] iteratively enlarges the labeled entity pairs based on the bootstrapping strategy.

Experimental settings. In this work, we adopt popular metrics, Hits@k and MRR for evaluating entity alignment results. We find the optimal parameters or follow the settings in original papers of baselines. For our OTEA method, the best configuration is γ = 0.5, α = 0.025, α1 = 2.5, weight clippling c = 0.01. Critics are set as two-layers MLPs with 500 hidden units. We use Adam [Kingma and Ba, 2014] to optimize the Lk, Le +Lr with lr = 0.001, and use RMSProp [Hinton et al., 2012] to optimize the Lg with lr = 5e - 5. Meanwhile, we use L2 norm to avoid potential over-fitting. We randomly sample 30% of the aligned entities as the training set, and the rest aligned entities for testing. Each evaluation is repeated 5 times and we report the averaged Hits@k and MRR.

4.2 Performance Evaluation Results (RQ1)

Table 2 shows the experimental results of baselines and our method. We can find that our proposed method consistently outperforms all baselines methods on all datasets under different evaluation metrics. Especially, we have significant improvement (10%∼50%) of Hits@1 value on almost all datasets, it means that our method achieves the better performance on directly successful aligning entities.

In the largest dataset WK31-120K, our method improves the best baseline with 33%∼59% under different metrics, indicating the significant advantage of our method works in the large KGs scenario. BootEA is the best baseline method in the results, since it improves the KG embedding method and also employs improved bootstrapping strategy with an alignment editing method to reduce the error accumulation. The results show that the improved bootstrapping strategy has better performance than the original bootstrapping method (ITransE). However, the error is not avoidable even though the improved method is adopted. On the largest dataset WK31-120k, it sometimes performs worse than MTransE. All the results demonstrate the advantage of our OTEA method.

4.3 Components Analysis (RQ2, RQ3)

To answer RQ2 and RQ3, we compare OTEA with its variant without dual alignment (only single translation), noted at "OTEA w/o dual", and another variant without the L2,1 regularizer, noted at "OTEA w/o reg". The performance of "OTEA w/o dual" and "OTEA w/o reg" in Table 2 shows that these components are important for OTEA to achieve superior results. The "OTEA w/o reg" results in dense translation matrices, which introduce increased noise into the translation (demonstrated also in Figure 3). The "OTEA w/o dual" is harder than OTEA to reach the optimal and convergence, because it needs to search in a broader parameter space.

4.4 Parameter Sensitivity and Complexity (RQ4) Sensitivity to the Proportion of Prior Aligned Entities

We randomly sample 10%, 30%, 50% and 70% of the aligned entities from WK31-15K(En-Fr) and WK31-60K(EnFr) datasets as the training samples, and compare the performance of our model to that of other baseline models. Figure 4 shows Hits@10 of different methods when varying the proportion of prior aligned entities. First, as expected, all methods have better performance with the growth of the proportion of aligned entities, because more information has been provided to align the entities. Second, OTEA and BootEA have much better performance than other baselines, due to the employment of unlabeled data and the selection of labeled data, respectively. Last, OTEA is persistently better than all other baselines, including BootEA, when varying the proportion of aligned entities on two datasets.

Sensitivity to the Dimension of KG Embeddings

Figure 5(a) shows how the dimensionality of embeddings influences the performance of different entity alignment methods on WK31-15K(En-Fr) dataset. We can see that our OTEA method is consistently better than all other baselines. In addition, its performance is quite stable when varying d.

WK31-60K dataset

WK31-120K dataset

Time Complexity Comparison

Figure 5(b) shows the running time comparison of the best baseline (BootEA), simplest method (MTransE) and our method (OTEA). We set same batch size for all methods and run them on a same GPU device, then record the running time of each iteration. The results show that OTEA is (3 times) faster than BootEA, because the bootstrapping based method need to propose the new aligned entities by calculating the similarity with all unaligned entities. Our method need more time than MTransE, but it is worthwhile to spend the time to achieve significant improvement on the task.

5 Conclusion

We introduced a novel framework for cross-lingual entity alignment in knowledge graphs. We proposed to solve the entity alignment by dually minimizing both the entity-level loss and the group-level loss via optimal transport theory, in order to model the whole picture of labeled and unlabeled entities in different language KGs. We also impose L2,1 regularizer on the dual translation matrices to mitigate the effect of noise during transformation. Our experiments on real-world datasets demonstrated that our approach achieved superior results comparing with other state-of-the-art methods on alignment accuracy.

Acknowledgments

The research reported in this publication was supported by funding from King Abdullah University of Science and Technology (KAUST), under award number FCC/1/1976-19-01, and NSFC No. 61828302.