Year: 2019

Abstract:
This paper studies aligning knowledge graphs from different sources or languages. Most existing methods train supervised methods for the alignment, which usually require a large number of aligned knowledge triplets. However, such a large number of aligned knowledge triplets may not be available or are expensive to obtain in many domains. Therefore, in this paper we propose to study aligning knowledge graphs in fully-unsupervised or weakly-supervised fashion, i.e., without or with only a few aligned triplets. We propose an unsupervised framework to align the entity and relation embddings of different knowledge graphs with an adversarial learning framework. Moreover, a regularization term which maximizes the mutual information between the embeddings of different knowledge graphs is used to mitigate the problem of mode collapse when learning the alignment functions. Such a framework can be further seamlessly integrated with existing supervised methods by utilizing a limited number of aligned triples as guidance. Experimental results on multiple datasets prove the effectiveness of our proposed approach in both the unsupervised and the weakly-supervised settings.

text: This paper studies aligning knowledge graphs from different sources or languages. Most existing methods train supervised methods for the alignment, which usually require a large number of aligned knowledge triplets. However, such a large number of aligned knowledge triplets may not be available or are expensive to obtain in many domains. Therefore, in this paper we propose to study aligning knowledge graphs in fully-unsupervised or weakly-supervised fashion, i.e., without or with only a few aligned triplets. We propose an unsupervised framework to align the entity and relation embddings of different knowledge graphs with an adversarial learning framework. Moreover, a regularization term which maximizes the mutual information between the embeddings of different knowledge graphs is used to mitigate the problem of mode collapse when learning the alignment functions. Such a framework can be further seamlessly integrated with existing supervised methods by utilizing a limited number of aligned triples as guidance. Experimental results on multiple datasets prove the effectiveness of our proposed approach in both the unsupervised and the weakly-supervised settings.

heading: 1 INTRODUCTION
text: Knowledge graphs represent a collection of knowledge facts and are quite popular in the real world. Each fact is represented as a triplet (h, r, t), meaning that the head entity h has the relation r with the tail entity t. Examples of real-world knowledge graphs include instances which contain knowledge facts from general domain (e.g., Freebase 1, WordNet 2) or facts from specific domains such as biomedical ontology (e.g., UMLS 3). Knowledge graphs are critical to a variety of applications such as question answering (Bordes et al., 2014) and semantic search (Guha et al., 2003). Research on knowledge graphs is attracting growing interest recently in both academia and industry communities.
In practice, each knowledge graph is usually constructed from a single source or language, the coverage of which is limited. To enlarge the coverage and construct more unified knowledge graphs, a natural idea is to integrate multiple knowledge graphs from different sources or languages (Arens et al., 1993). However, different knowledge graphs use distinct symbol systems to represent entities and relations, which are not compatible. Therefore, it is critical to align the entities and relations across different knowledge graphs (a.k.a., knowledge graph alignment) before integrating them.
Recently, many methods have been proposed to align entities and relations from a source knowledge graph to a target knowledge graph (Zhu et al., 2017a; Chen et al., 2017a;b; Sun et al., 2018a). These methods first represent the entities and relations in low-dimensional spaces and then learn mapping functions to align the entities and relations from the source knowledge graph to the target one. Though these methods are proven quite effective, they rely on a large number of aligned triplets for training supervised alignment models, and such aligned triplets may not be available or can be expensive to obtain. As a result, the performance of these methods will be comprised. Therefore, it would be desirable to design an unsupervised or weakly-supervised approach for knowledge graph alignment, which requires a few or even without aligned triplets.
1 https://developers.google.com/freebase/ 2 https://wordnet.princeton.edu/ 3 https://www.nlm.nih.gov/research/umls/
In this paper, we propose an unsupervised approach to knowledge graph alignment with adversarial training (Goodfellow et al., 2014). Our proposed approach first represents the entities and relations in low-dimensional spaces with existing knowledge graph embedding methods (e.g., TransE (Bordes et al., 2013)) and then learns alignment functions, i.e., pe(et|es) and pr(rt|rs), to map the entities and relations (es and rs) from the source knowledge graph to those (et and rt) in the target graph. Intuitively, an ideal alignment function is able to map all triples in the source graph to valid ones in the target graph. Therefore, we train a triplet discriminator to distinguish between the real triplets in the target graph and those aligned ones from the source graph. Such a discriminator measures the plausibility of a triplet in the target graph and provides a reward function for optimizing the alignment functions, which are optimized to fool the discriminator. The above process naturally forms an adversarial training procedure. By alternatively optimizing the alignment functions and the discriminator, the whole process can constantly enhance the alignment functions.
Despite the effectiveness of adversarial learning in many scenarios, one big problem it may suffer from is the mode collapse (Salimans et al., 2016). Specifically, in our case, it means that many entities in the source knowledge graph are aligned to only a few entities in the target knowledge graph. We propose to mitigate this problem by maximizing the mutual information between the entities in the source graph and those aligned entities, which can be effectively and effectively optimized with some recent techniques on mutual information neural estimation (Belghazi et al., 2018). We further prove that by maximizing the mutual information, different source-graph entities are encouraged to be aligned to different target-graph entities, which mitigates the mode collapse.
The whole framework can also be seamlessly integrated with existing supervised methods, in which we can use a few aligned entities or relations as guidance, yielding a weakly-supervised approach. Our approach can be effectively optimized with stochastic gradient descent, where the gradient for the alignment functions is calculated by the REINFORCE algorithm (Williams, 1992). We conduct extensive experiments on several datasets. Experimental results prove the effectiveness of our proposed approach in both the weakly-supervised and unsupervised settings.

heading: 2 RELATED WORK
text: Our work is related to knowledge graph embedding, which represents entities and relations as lowdimensional vectors (a.k.a., embedding). A variety of approaches have been proposed (Bordes et al., 2013; Wang et al., 2014; Yang et al., 2014; Sun et al., 2018b), which can effectively preserve the similarities of entities and relations into the learned embeddings. We treat these techniques as tools to learn entity and relation embeddings, which serve as features for knowledge graph alignment.
In literature, there are also some studies focusing on knowledge graph alignment. Most of them perform alignment by considering contextual features of entities and relations, such as their names (Lacoste-Julien et al., 2013) or text descriptions (Chen et al., 2018; Wang et al., 2012; 2013). However, such contextual features are not always available, and therefore these methods cannot generalize to most knowledge graphs. In this paper, we consider the most general case, in which only the triplets in knowledge graphs are used for alignment. The studies most related to ours are Zhu et al. (2017a), Chen et al. (2017a) and Sun et al. (2018a). Similar to our approach, they treat the entity and relation embeddings as features, and jointly train an alignment model. However, they totally rely on the labeled data (e.g., aligned entities) to train the alignment model, whereas our approach incorporates additional signals by using adversarial training, and therefore achieves better results in the weakly-supervised and unsupervised settings.
More broadly, our work belongs to the family of domain alignment, which aims at mapping data from one domain to the other domain. With the success of generative adversarial networks (Goodfellow et al., 2014), many researchers have been bringing the idea to domain alignment, getting impressive results in many applications, such as image-to-image translation (Zhu et al., 2017b;c), word-to-word translation (Conneau et al., 2017) and text style transfer (Shen et al., 2017). These studies typically train a domain discriminator to distinguish between data points from different domains, and then the alignment function is optimized by fooling the discriminator. Our approach shares similar idea, but is designed with some specific intuitions in knowledge graphs.
Besides, our work is also related to recent studies on neural mutual information estimation (Belghazi et al., 2018), which estimate the mutual information of two distributions by using neural networks.
Such a technique has been utilized in many applications, including image classification (Hjelm et al., 2018) and unsupervised node representation learning (Veličković et al., 2018). All these studies use the technique to improve representation learning (e.g., image representation, node representation). In contrast, our approach uses the technique to avoid mode collapse in adversarial learning.
Finally, Cai & Wang (2018) propose a method called KBGAN recently, which uses adversarial learning for generating negative examples in knowledge graph embedding algorithms. Compared with this work, both our method and KBGAN use the adversarial learning framework, but our work is fundamentally different from KBGAN. More specifically, the goal of KBGAN is to use adversarial learning to generate effective negative samples for knowledge graph embedding, while our work studies a very different problem, that is, knowledge graph alignment. We use the adversarial learning framework to learn effective mapping functions to align entities and relations across different knowledge graphs. Moreover, a major challenge in knowledge graph alignment is that the entities (or relations) in the source knowledge graph could be mapped to only a subset of entities (or relations) in the target knowledge graph. We propose to maximize the mutual information between the source entities (relations) and the mapped entities (relations) to mitigate this problem.

heading: 3 PROBLEM DEFINITION
text: Definition 1 (KNOWLEDGE GRAPH.) A knowledge graph is denoted as G = (E,R,X), where E is a set of entities, R is a set of relations and X is a set of triplets. Each triplet x = (h, r, t) consists of a head entity h, a relation r and a tail entity t, meaning h has relation r with t.
In practice, the coverage of each individual knowledge graph is usually limited, since it is typically constructed from a single source or language. To construct knowledge graphs with broader coverage, a straightforward way is to integrate multiple knowledge graphs from different sources or languages. However, each knowledge graph uses a unique symbol system to represent entities and relations, which is not compatible with other knowledge graphs. Therefore, a prerequisite for knowledge graph integration is to align entities and relations across different knowledge graphs (a.k.a., knowledge graph alignment). In this paper, we study how to align entities and relations from a source knowledge graph to those in a target knowledge graph, and the problem is formally defined below:
Definition 2 (KNOWLEDGE GRAPH ALIGNMENT.) Given a source knowledge graph Gs = (Es,Rs,Xs) and a target knowledge graph Gt = (Et,Rt,Xt), we aim at learning an entity alignment function pe and a relation alignment function pr. Given an entity es in the source graph and an entity et in the target graph, pe(et|es) gives the probability that es aligns to et. Similarly, for a source relation rs and a target relation rt, pr(rt|rs) gives the probability that rs aligns to rt.

heading: 4 MODEL
text: In this paper we propose an unsupervised approach to learning the alignment functions, i.e., pe(et|es) and pr(rt|rs), for knowledge graph alignment. To learn them without supervision, we notice that we can align each source-graph triplet with a target-graph triplet by aligning the head/tail entities and relation respectively. For an ideal alignment model, all the aligned triplets should be valid ones (i.e., triplets expressing true facts). Therefore, we can improve the alignment functions by raising the plausibility of the aligned triplets. With the intuition, our approach trains a triplet discriminator to distinguish between valid and invalid triplets. Then we build a reward function from the discriminator to facilitate the alignment functions.
However, adversarial training may cause the problem of mode collapse, i.e., many entities in the source graph are aligned to only a few entities in the target graph. We avoid the problem by maximizing the mutual information between the source-graph and the aligned entities, which can effectively enforce different source-graph entities to be aligned to different target-graph entities.
The above strategies yield an unsupervised approach. However, in many cases, the structures of the source and target knowledge graphs (e.g., entity and triplet distributions) can be very different, making our unsupervised approach unable to perform effective alignment. In such cases, we can integrate our approach with existing supervised methods, and use a few labeled data as guidance, yielding a weakly-supervised approach.

heading: 4.1 FORMULATION OF THE ALIGNMENT FUNCTIONS
text: In this section, we introduce how we formulate the alignment functions, i.e., pe(et|es) and pr(rt|rs). To build the alignment functions, our approach first pre-trains the entity and relation embeddings with existing knowledge graph embedding techniques (Bordes et al., 2013; Wang et al., 2014; Yang et al., 2014), where the embeddings are denoted as {ves}es∈Es , {vet}et∈Et and {vrs}rs∈Rs , {vrt}rt∈Rt . In practice, our approach is flexible with any knowledge graph embedding algorithms, and we analyze some of them in Section 5.2.
The learned embeddings preserve the semantic correlations of entities and relations, thus we treat them as features and build our alignment functions on top of them. Specifically, we define the probability that a source entity es or relation rs aligns to a target entity et or relation rt as follows:
pθ(et|es) ∝ exp(−η||θeves − vet ||22) pθ(rt|rs) ∝ exp(−η||θrvrs − vrt ||22). (1)
Here, η is a temperature parameter, θe and θr are linear projection matrices, which map an entity/relation embedding in the source knowledge graph (e.g., ves ) to one in the target graph (e.g., θeves ), so that we can perform alignment by calculating the Euclidean distance between those embeddings (e.g., vet and θeves ).
With the definition of entity and relation alignment functions, we can further align a source-graph triplet to a target-graph triplet by aligning the head/tail entities and the relation respectively. Based on that, the probability of aligning a source-graph triplet xs = (hs, rs, ts) to a target-graph triplet xt = (ht, rt, tt) is given as follows:
pθ(xt|xs) = pθ(ht|hs)pθ(rt|rs)pθ(tt|ts). (2)
Basically, we align the head/tail entities and the relation independently, and use the product of those probabilities to define the triplet alignment function.
By applying the triplet alignment function to all the triplets in the source graph, we obtain a distribution of the aligned triplet, which is given below:
pθ(xt) = ∑ xs pd(xs)pθ(xt|xs) = Epd(xs)[pθ(xt|xs)], (3)
where pd(xs) is the data distribution of the triplets in the source graph.

heading: 4.2 THE ADVERSARIAL TRAINING FRAMEWORK
text: With the above formulation, we have obtained pθ(xt), which is the distribution of the triplets aligned from the source graph. Intuitively, we expect every triplet sampled from the distribution to be valid ones. For this purpose, we introduce a discriminator to discriminate between valid and invalid triplets. Such a discriminator essentially estimates the plausibility of a triplet, from which we can build a reward function to guide the alignment functions.
Formally, given a triplet xt = (ht, rt, tt) in the target domain, the discriminator Dφ is defined as:
Dφ(xt) = σ(fφ(vht) + fφ(vtt) + gφ(vht ,vrt ,vtt)). (4)
Here, σ is the sigmoid function. fφ and gφ are potential functions parameterized by multi-layer neural networks. The potential functions take the entity and relation embedding as input, and output a unary and a ternary potential scores to calculate Dφ(xt), which measures the probability that xt is a valid triplet.
We train the discriminator Dφ by using the following objective as in Goodfellow et al. (2014):
Oφ = Epd(xt)[logDφ(xt)] + Epθ(xt)[log(1−Dφ(xt))], (5)
where pd(xt) is the distribution of the real triplet in the target knowledge graph, and pθ(xt) is the distribution of triplets generated by our alignment functions. Basically, the real triplets in the target knowledge graph are treated as positive examples, and those generated by our aligned functions serve as negative examples.
Based on the discriminator, we can construct a scalar-to-scalar reward function R to measure the plausibility of a triplet. Then the alignment functions can be trained by maximizing the reward, and the objective function is given below:
Oθ = Epθ(xt)[R(Dφ(xt))]. (6)
There are several ways to define the reward function R, which yields different adversarial training frameworks. For example, Goodfellow et al. (2014) and Ho & Ermon (2016) treat R(x) = log x as the reward function. Finn et al. (2016) uses R(x) = log x1−x . Che et al. (2017) considers R(x) = x 1−x . Besides, we may also leverage R(x) = x, which is the first-order Taylor’s approximation of − log(1 − x) at x = 1. All different reward functions essentially seek to minimize certain divergences between the data distribution pd(xt) and the model distribution pθ(xt), and therefore they yield the same optimal solution (i.e., pθ(xt) = pd(xt)). In practice, these reward functions may have different variance, and we empirically compare them in the experiments (Table 4).
During optimization, the derivative with respect to the alignment functions cannot be calculated directly, as the triplets sampled from the alignment functions are discrete. Therefore, we leverage the REINFORCE algorithm (Williams, 1992), which calculates the gradient as follows:
∇θOθ = Epθ(xt)[R(Dφ(xt))∇θ log pθ(xt)]. (7)
During training, we will alternate between optimizing the discriminator and optimizing the alignment functions, so that the discriminator can consistently provide effective supervision to benefit the alignment functions.

heading: 4.3 DEALING WITH MODE COLLAPSE
text: Although the above framework provides an effective way to learn alignment functions in an unsupervised manner, the training procedure may suffer from the problem of mode collapse. More specifically, the entities in the source graph may be aligned to only a few entities in the target graph.
To avoid the problem, a natural way is to maximize the mean KL divergence between the alignment distributions of two source-graph entities Ees,u,es,v∼pd(es)[KL(pθ(et|es,u), pθ(et|es,v))]. In this way, we can encourage the entities in the source graph to be aligned to different target-graph entities.
However, directly maximizing the mean divergence can be problematic. This is because the gradient of the alignment functions may explode when the mass of pθ(et|es,u) and pθ(et|es,v) concentrates in different areas (i.e., their KL divergence is very large). Due to the problem, we instead maximize a lower bound of the mean KL divergence, and a natural choice is the mutual information between the aligned entities and source-graph entities as shown in the following theorem.
Theorem 1 The mutual information I(es, et) = Epθ(es,et)[log pθ(es,et) pd(es)pθ(et) ] provides a lower bound of the mean KL divergence between the alignment distributions of two source-graph entities Ees,u,es,v∼pd(es)[KL(pθ(et|es,u), pθ(et|es,v))].
We prove the theorem in the appendix. With the theorem, we see that by maximizing the mutual information between the aligned entities and source-graph entities, we can guarantee the mean KL divergence not to be so small, and therefore mitigate mode collapse.
Following recent studies on neural mutual information estimation (Belghazi et al., 2018), we calculate the mutual information by introducing a function Tγ as follows:
I(es, et) ≥ Iγ(es, et) = sup Tγ∈F
{ Epθ(es,et)[Tγ(es, et)]− log(Epd(es)pθ(et)[e Tγ(es,et)]) } . (8)
Basically, Iγ(es, et) is an estimation of I(es, et), where we parameterize Tγ(es, et) as a neural network, which takes the embeddings of es and et as input to output a scalar value. As we optimize Tγ , the above neural estimation will become more precise.
In most existing studies (Hjelm et al., 2018; Veličković et al., 2018), only the function Tγ is optimized, since their end-goal is to improve representation learning by approximating the mutual information. In contrast, our end-goal is to improve the alignment function pθ by maximizing the mutual
information I(es, et). Therefore, besides optimizing Tγ to tighten the bound, we also optimize pθ to push the bound up. Specifically, the gradient for θ can be calculated as follows:
∇θIγ = Epθ(es,et)[Tγ∇θ log pθ(es, et)]− Epd(es)pθ(et)[eTγ∇θ log pθ(et)]
Epd(es)pθ(et)[eTγ ] , (9)
where we again leverage the REINFORCE algorithm (Williams, 1992) to for gradient calculation. In practice, the gradient can be approximated as follows:
∇θIγ ' n∑ i=1 Tγ(ê (i) s , ê (i) t )∇θ log pθ(ê (i) t |ê (i) s ) n − ∑n i=1 e Tγ(ê (n+i) s ,ê (i) t )∇θ log pθ(ê(i)t |ê (i) s )∑n i=1 e Tγ(ê (n+i) s ,ê (i) t ) , (10)
where we have ê(i)s ∼ pd(es) for i ∈ [1, 2n], and ê(i)t ∼ pθ(ê (i) t |ê (i) s ) for i ∈ [1, n].

heading: 4.4 WEAKLY-SUPERVISED LEARNING
text: The above sections introduce an unsupervised approach to knowledge graph alignment. In many cases, the source and target knowledge graphs may have very different structures (e.g., entity or triplet distributions), making our approach fail to perform effective alignment. In these cases, we can integrate our approach with a supervised method, and leverage a few labeled data (e.g., aligned entity or relation pairs) as guidance, which yields a weakly-supervised approach.

heading: 4.5 OPTIMIZATION
text: We leverage the stochastic gradient descent algorithm for optimization. In practice, we find that first pre-training the alignment functions with existing supervised approaches, then fine-tuning them with the triplet discriminator and the mutual information maximization strategy leads to impressive results. Consequently, we adopt this framework. The detailed algorithm is presented in Algorithm 1.

heading: 5 EXPERIMENT

heading: 5.1 EXPERIMENT SETUP
text: Following existing studies (Zhu et al., 2017a; Chen et al., 2017a; Sun et al., 2018a), we perform evaluation on the task of entity alignment. Three different settings are considered, including supervised, weakly-supervised and unsupervised settings. Hit ratio and mean rank (MR) are reported.
1. Datasets. We use four datasets in experiment, and their statistics are available in Table 1.
• FB15k-1, FB15k-2: Following Zhu et al. (2017a), we construct two datasets from the FB15k dataset (Bordes et al., 2013). In FB15k-1, the two knowledge graphs share 50% triplets, and in FB15k-2 10% triplets are shared. According to the study, we use 5000 and 500 aligned entity pairs as labeled data in FB15k-1 and FB15k-2 respectively, and the rest for evaluation. • WK15k(en-fr): A bi-lingual (English and French) dataset in Chen et al. (2017a). Some aligned triplets are provided as labeled data, and some aligned entity pairs as test data. The labeled data and test data have some overlaps, so we delete the overlapped pairs from labeled data. Also, some entities in the test set are not included in the training set, and thus we filter out those entities. • WK15k(en-de): A bi-lingual (English and German) dataset used in Chen et al. (2017a). The dataset is similar to WK15k(en-fr), so we perform preprocessing in the same way.
2. Compared Algorithms. (1) iTransE (Zhu et al., 2017a): A supervised method for knowledge graph alignment. (2) MLKGA (Chen et al., 2017a): A supervised method for multi-lingual
knowledge graph alignment. (3) AlignE (Sun et al., 2018a): A supervised method for knowledge graph alignment, which leverages a bootstrapping manner for training. (4) BootEA (Sun et al., 2018a): Another bootstrapping method for knowledge graph alignment. (5) Procrustes (Artetxe et al., 2017): A supervised method for word translation, which learns the translation in a bootstrapping way. We apply the method on the pre-trained entity and relation embeddings to perform knowledge graph alignment. (6) UWT (Conneau et al., 2017): An unsupervised word translation method, which leverages adversarial training and a refinement strategy. We apply the method to the entity and relation embeddings to perform alignment. (7) KAGAN: Our proposed approach, which uses both the triplet discriminator and the mutual information maximization strategy for training.
3. Parameter Settings. For all datasets, 10% labeled pairs are treated as the validation set, which is used for hyper-parameter selection for each compared algorithm. For the dimension of the entity embedding, we choose the optimal value from {64, 128, 256, 512} based on the performance on the validation set. For our proposed approach, the entity and relation embeddings are trained with the TransE (Bordes et al., 2013) algorithm by default, because of its simplicity and effectiveness. The alignment functions are pre-trained with the Procrustes (Artetxe et al., 2017) algorithm in the weakly-supervised and supervised settings, because Procrustes is both effective and efficient. For the potential functions fφ and gφ in the discriminator, and the T function Tγ in the neural estimator of mutual information, we build each of them using a two-layer neural network with 2048 hidden units and the LeakyReLU activation function (Maas et al.). SGD is used for optimization. The learning rates for the triplet discriminator and the mutual information estimator are set as 0.1 during pre-training, and 0.001 during training. The learning rate for the alignment functions is set as 0.001. Early stopping is used during training.

heading: 5.2 EXPERIMENT RESULTS
text: Table 3: Results of Entity Alignment on the FB datasets.
Table 4: Study of Reward Functions.
1. Comparison with Baseline Methods. The main results are presented in Table 2 and 3. In the supervised setting, our approach significantly outperforms all the compared methods, showing our
approach can utilize the labeled data more effectively. In the unsupervised setting on FB15k datasets, without using any labeled data, our approach already achieves close results as in supervised settings.
However, the performance on WK15k in the unsupervised setting is quite poor. The reason is that the source and target knowledge graphs in WK15k have very different structures (i.e., entity distribution and triplet distribution). Therefore, the triplet discriminator cannot well discriminate between the real and fake triplets, and further provides effective reward. In such cases, we may leverage a few aligned entity pairs to pre-train our alignment functions, leading to a weakly-supervised approach. We present the results of this weakly-supervised approach in Figure 1. The Procrustes algorithm (Artetxe et al., 2017) is chosen as the compared method, since it has the best performance in the supervised setting. From the results, we see that by using a very small number of aligned pairs, our approach (blue line) already outperforms Procrustes in the supervised setting (black line), showing that our approach is also quite effective in the weakly-supervised setting.
2. Analysis of Mutual Information Maximization. In KAGAN, we avoid mode collapse by maximizing the mutual information between the source-graph entities and the aligned entities. To understand its effect, we conduct some ablation studies in the supervised setting. Table 5 presents the results. With mutual information maximization, we consistently get better results, which proves the effectiveness of such a strategy. We also conduct some cases studies in appendix (see Section B).
Table 6: Analysis of the Discriminator Training.
Method FB15k-2 WK15k fr2en H@1 H@10 MR H@1 H@10 MR
Rand. 68.72 81.34 37.8 32.90 67.22 178.9 Rand.+Adv. 72.72 88.34 28.0 33.88 66.86 166.2
Adv. 73.68 88.91 26.3 35.88 68.59 136.3
Table 7: Comparison of Embedding Methods.
Method FB15k-2 WK15k fr2en H@1 H@10 MR H@1 H@10 MR TransE 73.68 88.91 26.3 35.88 68.59 136.3 TransH 34.39 47.99 464.2 12.04 25.41 1493.6 DistMult 0.15 0.31 5351.2 0.12 0.20 5754.8
3. Analysis of the Discriminator Training. In our approach, a discriminator is trained to discriminate between the real and fake triplets. During discriminator training, we choose the triplets generated by our alignment models as fake triplets by default, and there are also some other ways to generate the fake triplets. In this section, we compare different options of the fake triplets. Our default method, which treats the generated triplets as fake ones, is denoted as “Adv.”. Another common choice is to use random triplets as fake ones, as used in most knowledge graph embedding algorithms. We denote this variant as “Rand.”. Besides, we can also leverage both the random and the generated triplets as fake ones, and such a method is denoted as “Rand.+Adv.”.
We compare the three variants on the FB15k-2 dataset (unsupervised setting) and the WK15k datasets (supervised setting), and the results are presented in Table 6. We see that using random triplets as fake ones (“rand.” and “rand.+adv.”) leading to inferior results compared with using only generated triplets, which proves the effectiveness of our adversarial training framework.
4. Comparison of Knowledge Graph Embeddings. In our approach, we pre-train the entity and relation embeddings with existing knowledge graph embedding algorithms, and then use these embeddings as features for training the alignment functions. Our approach is compatible with a wide range of knowledge graph emebedding algorithms. In this section, we compare different knowledge graph embedding algorithms. We choose three commonly-used embedding algorithms, including TransE (Bordes et al., 2013), TransH (Wang et al., 2014) and DistMult (Yang et al., 2014).
The results on the FB15k-2 dataset (unsupervised setting) and the WK15k dataset (supervised setting) are presented in Table 7. We see that TransE achieves the best performance among all three algorithms. The reason is that TransE uses a linear scoring function, and the relations are characterized as linear translations in the embedding space. The information encoded in the learned embeddings can be effectively recovered by a linear alignment function, as used in our approach. In contrast, TransH and DistMult use more complicated scoring functions, and the information in the learned embeddings cannot be well recovered by a simple linear alignment function. In the future, we plan to explore some nonlinear alignment functions to further improve the performance.
5. Comparison of Reward Functions. In our approach, we can choose different reward functions, leading to different adversarial training frameworks. These frameworks have the same optimal solution, but with different variance. Next, we compare them on WK15k in the supervised setting, and the results are presented in Table 4. We notice that all reward functions lead to significant improvement compared with using no reward. Among them, x1−x and x obtain relatively better results.

heading: 6 CONCLUSION
text: This paper studies knowledge graph alignment, and an unsupervised approach is proposed based on adversarial training and mutual information maximization, which can also be seamlessly integrated with existing supervised methods for weakly-supervised learning. Experimental results on several real datasets prove the effectiveness of our approach in both the unsupervised and weakly-supervised settings. In the future, we plan to learn alignment functions from two directions (source to target and target to source) to further improve the results, which is similar to CycleGAN (Zhu et al., 2017b).

heading: A PROOF OF THE THEOREM 1
text: We first restate the theorem and then give the proof.
Theorem 2 The mutual information I(es, et) = Epθ(es,et)[log pθ(es,et) pd(es)pθ(et) ] provides a lower bound of the mean KL divergence between the alignment distributions of two source-graph entities Ees,u,es,v∼pd(es)[KL(pθ(et|es,u), pθ(et|es,v))].
Proof 1 For the mean KL divergence, we have: Ees,u,es,v∼pd(es)[KL(pθ(et|es,u)||pθ(et|es,v))] = Epd(es,u)pd(es,v)pθ(et|es,u)[log pθ(et|es,u)]− Epd(es,u)pd(es,v)pθ(et|es,u)[log pθ(et|es,v)]
For the first term, it equals to Epθ(et,es,u)[log pθ(et|es,u)]. For the second term, we have:
Epd(es,u)pd(es,v)pθ(et|es,u)[log pθ(et|es,v)] = Epθ(et,es,u)[Epd(es,v)[log pθ(et|es,v)]] ≤ Epθ(et,es,u)[logEpd(es,v)[pθ(et|es,v)]] = Epθ(et,es,u)[log pθ(et, es,v)]
Here, the inequation is based on the Jensen’s inequality (logE[f(x)] ≥ E[log f(x)]). By combing the above terms, we obtain:
Ees,u,es,v∼pd(es)[KL(pθ(et|es,u)||pθ(et|es,v))] =Epθ(et,es,u)[log pθ(et|es,u)]− Epθ(et,es,u)[log pθ(et, es,v)] ≥Epd(es)[KL(pθ(et|es)||pθ(et))] = I(es, et)
The theorem is proved.

heading: B MORE ANALYSIS ON MUTUAL INFORMATION MAXIMIZATION
text: To further understand the effect of mutual information maximization, we show some case study results on the WK15k datasets in Fig. 2. For each entity in the target knowledge graph, we count how many source-graph entities are aligned to that entity. Then we find top 100 target-graph entities with the largest counts, and their counts are reported. From the figure, we see that by maximizing the mutual information, the alignment counts of the top-ranked entities become smaller, which proves that our method can indeed encourage different source-graph entities to be aligned to different targetgraph entities, and thus alleviate mode collapse.

heading: C OPTIMIZATION ALGORITHM OF KAGAN
text: We present the detailed optimization algorithm of our approach as follows:
Algorithm 1 Optimization Algorithm 1: Input: Two knowledge graphs Gs and Gs, some aligned entity/relation pairs (optional). 2: Output: The alignment functions pθ. 3: Pre-train the alignment functions with the aligned pairs. 4: Pre-train the triplet discriminator Dφ according to Equation 5. 5: Pre-train the mutual information estimator Iγ according to Equation 8. 6: while not converge do 7: Update the triplet discriminator Dφ according to Equation 5. 8: Update the alignment functions pθ with Dφ according to Equation 7. 9: Update the mutual information estimator Iγ according to Equation 8. 10: Update the alignment functions pθ to maximize Iγ according to Equation 10. 11: end while

heading: D ADDITIONAL EXPERIMENTS ON LARGE DATASETS
text: We also conduct some experiments on WK120k(en-de), which is a dataset in Chen et al. (2017a). Similar to WK15k, as the training data and test data have some overlap, we filter out those overlapped data in the training set. Also, some entities in the test set are not included in the training set, and thus we remove those entities in the test set. The detailed statistics are summarized in Table 8.
The results of the compared methods are presented in Table 9. We see that our proposed approach outperforms all the baseline methods, which shows the effectiveness of KAGAN on large datasets.

Review summaries:
The authors propose KAGAN, a novel method for knowledge graph (KG) alignments using GANs. In contrast to most other methods, KAGAN does not rely on a supervised setting where a set of already aligned triples is used as seed. In addition, the authors propose modifications such that their method can also integrate information about aligned triples.

The authors propose an unsupervised knowledge graph alignment framework, KAGAN, using adversarial training. Specifically, they utilize a triple discriminator to discriminate the aligned source triples and target triples, and a reward function to minimize the divergence between source triples and target triples. Also, they propose to leverage the lower bound of the mean KL divergence (mutual information) to resolve the mode collapse problem. The proposed method can be incorporated with a supervised method to be a weakly-supervised approach. Even though there are a family of unsupervised approaches for domain alignment, this paper is the first to solve the knowledge graph alignment problem in an unsupervised/weakly supervised way.