Multilingual Knowledge Graph Completion With Joint Relation and Entity Alignment
Year: 2021

Abstract:
Knowledge Graph Completion (KGC) predicts missing facts in an incomplete Knowledge Graph. We study Multilingual KGC for KGs that associate entities and relations with surface forms from different languages. In such a setting, an entity (or relation) may be mentioned as separate IDs in different KGs, necessitating entity alignment (EA) and relation alignment (RA). In addition to EA and RA being important subtasks for Multilingual KGC, we posit that high confidence fact predictions may also, in turn, add valuable information for alignment tasks, and vice versa. In response, we present the novel task of jointly training multilingual KGC, EA and RA models. Our approach, ALIGNKGC, uses mBERT-based surface form overlap for EA, and combines it with a KGC approach, extended to the multiple KG setting via a loss term that incentivizes RA. On experiments with DBPedia in five languages, we find that ALIGNKGC achieves up to 17% absolute MRR improvements in KGC compared to a strong completion model that combines known facts in all languages. It also outperforms an mBERT-only alignment baseline for EA, underscoring the value of joint training for these tasks.

text: We study Multilingual KGC for KGs that associate entities and relations with surface forms from different languages. In such a setting, an entity (or relation) may be mentioned as separate IDs in different KGs, necessitating entity alignment (EA) and relation alignment (RA). In addition to EA and RA being important subtasks for Multilingual KGC, we posit that high confidence fact predictions may also, in turn, add valuable information for alignment tasks, and vice versa. In response, we present the novel task of jointly training multilingual KGC, EA and RA models. Our approach, ALIGNKGC, uses mBERT-based surface form overlap for EA, and combines it with a KGC approach, extended to the multiple KG setting via a loss term that incentivizes RA. On experiments with DBPedia in five languages, we find that ALIGNKGC achieves up to 17% absolute MRR improvements in KGC compared to a strong completion model that combines known facts in all languages. It also outperforms an mBERT-only alignment baseline for EA, underscoring the value of joint training for these tasks.

heading: 1. Introduction
text: A knowledge graph (KG) has nodes representing entities and directed edges representing relations between subject and object entities. An entity has a unique node (ID). Relations also have canonical labels such as born-in or works-at, with associated IDs. A KG is usually associated with a single human language — an entity node (or relation ID) is associated with one or more surface forms in that language. E.g., the ID for the country USA may have aliases like “United States of America".
KGs are usually very incomplete, as curators struggle to keep up with the real world. KG completion (KGC) is thus a strongly motivated problem and studies the prediction of true facts unknown to the KG. While the problem has been intensively researched over the last few years [Bordes et al., 2013, Trouillon et al., 2016, Jain et al., 2018, Sun et al., 2019], most KGC research is applicable to only one KG in one language at a time. However, different language speakers would maintain separate KGs in their own languages. Independent completions of each KG may not be optimal, since information from one KG will likely help completion of the other.
Each KG will give a different ID, and often also a different surface form, to the same entity, such as “Estados Unidos de América” for the USA entity in a Spanish KG. This leads to the problem of ID proliferation. Recent work on entity alignment (EA) across KGs attempts to assign a unique ID to all nodes representing the same entity [Chen et al., 2017, Sun et al., 2017, 2018, 2020, Cao et al., 2019, Chen et al., 2021, Tang et al., 2020]. A related but under-explored task is relation alignment (RA) — assigning synonymous relations in different KGs the same relation ID. We note that RA involves global evidence, because the decision to merge two relations in two languages can have far-reaching consequences to many facts in both KGs.
Our key contribution is to recognize and exploit the synergy between multilingual KGC, EA and RA tasks. Entity and relation alignments expose a KGC algorithm to more facts, which can lead to better completion. Conversely, a high-confidence completion can give additional evidence to align its constituent entities and relation. (See Appendix A for an extended example.) In this paper, we present ALIGNKGC, a multi-task system that learns to optimize for KGC, EA and RA jointly. ALIGNKGC uses state-of-the-art mBERT-based models for EA and combines it with an extension of the state-of-the-art ComplEx model [Trouillon et al., 2016] for single KGC. ALIGNKGC uses a novel subject-object signature of each relation, which it represents as a bag of embeddings, and compares them for equivalence and implication between relations. ALIGNKGC uses this information as additional term in its loss function for better RA and multilingual KGC performance.
We evaluate ALIGNKGC on slices of DBPedia in five languages. We compare it against two single-KGC systems, one trained over each monolingual KG separately, and the other trained over a union of all KG facts. Compared to these strong baselines, we find that ALIGNKGC achieves substantial accuracy boost due to better entity and relation alignment, obtaining up to 17% absolute MRR improvements in KGC across languages, around 20% absolute HITS@1 gain for RA for rare relations, around 26% absolute HITS@1 gain for RA for more frequent relations, and around 61% absolute HITS@1 gain for EA. ALIGNKGC also achieves a 5.3% absolute HITS@1 gain over an even stronger EA baseline that uses mBERT embeddings on entity names. These results underscore the value of joint training for these tasks.

heading: 2. Notation and preliminaries
text: A knowledge graph (KG) provides a graph-view to a knowledge-base (KB). A KG consists of entities E and relations (aka relation types) R. A KG instance is a triple (s, r, o) where s, o ∈ E and r ∈ R. These are all canonical IDs. Each ID is associated with one or more textual aliases. KGC task: For any single KG, training data is provided as (s, r, o) triples. A test instance has the form (s, r, ?) or (?, r, o) where the system has to predict o or s. Multiple correct values are possible. The evaluation protocol takes a system-ranked list of candidate objects or subjects, and then measures MRR or hits@K. Many KG embedding and KGC algorithms have been proposed in the last few years. ComplEx [Trouillon et al., 2016] with all negative instances (no sampling) is a simple model that gives near state-of-the-art predictions [Jain et al., 2020a]. It has also formed the basis for many KGC extensions (e.g., [Jain et al., 2020b]). So we use it as our baseline KGC gadget. ComplEx defines a triple score as f(s, r, o) = < (〈s, r,o?〉), where c? is complex conjugate, 〈· · · 〉 is a 3-way elementwise inner product and <(·) is the real part of a complex number. Using f , ComplEx defines
Pr(o|s, r) = ef(s,r,o) /∑
o′ e f(s,r,o′), Pr(s|o, r) = ef(s,r,o) /∑ s′ e f(s′,r,o) (1)
and the log-likelihood KGC loss as LKGC = ∑ (s,r,o)∈KG− log Pr(o|s, r)− log Pr(s|o, r).
Alignment tasks: We consider a set L = {l1, l2, . . .} of languages. KGl represents the KG supported by the language l. An entity in this KG is called el. A relation in this KG is called rl. While trying to improve KGC for target language l′, KGs in multiple source languages l may be combined.
An equivalence between entities el and el′ in KGs of two languages l and l′ is specified as el ≡ el′ , also written as the triple (el,≡, el′). Similarly, an equivalence between relations rl and rl′ is specified as rl ≡ rl′ . Other types of alignment may be possible between relation pairs, such as rl ⇒ rl′ , which means, for all s, o such that (s, rl, o) holds, so does (s, rl′ , o). During training, a set of entity equivalences {(enl ,≡, enl′) : n = 1, . . . , N} and a set of relation equivalences {(rml ,≡, rml′ ) : m = 1, . . . ,M} are revealed to the system between each KGl and KGl′ . The goal of the system is to infer additional entity and relation equivalences. The system is usually called upon to produce a ranked list of equivalences, which is evaluated using HITS@K or MRR.
To achieve KGC enhanced with alignment, the system has to infer additional triples in each KG, making best use of the revealed equivalences, while also inferring additional alignment triples between entities or relations across KGs of different languages.

heading: 3. Proposed methods

heading: 3.1 KGC baselines
text: When ComplEx is applied to any one KG in isolation, we call this method KGCMONO. Perhaps the most straight-forward way to apply a KGC system across multiple KGs is to compute KGU =⋃
l∈L KGl such that for all revealed entity equivalences {(el,≡, el′)}, collapse their node pairs, and rename all equivalent rl, rl′ relation IDs to a common new ID. A standard KGC system can work on the resulting KGU , and we call this method KGCUNION.

heading: 3.2 Joint alignment and completion
text: For both textual and structured inputs, the problem of inferring a predicate or relation as entailed by another has been well-studied [Lin and Pantel, 2001, Bhagat et al., 2007, Nakashole et al., 2012]. With that work as our point of departure, we ask: How similar are two relations rl, rl′ in KGU? Comparing their embedding vectors rl, rl′ , as computed by a KGC algorithm such as ComplEx, gives an estimate. However, when training these embeddings, we found that a simple union of facts (KGCMONO) did not yield the best results. Instead, guiding the training through an auxiliary loss, computed using the following explicit relation signatures helped the model learn better embeddings. Here s, o are interpreted as canonical IDs (hence, ‘hard’). This will be generalized shortly.
Definition 1 (Hard SO-signature). The (‘hard’) subject-object (SO) signature of a relation is defined as SO(r) = {(s, o) : (s, r, o) ∈ KGU}.

heading: 3.2.1 HARD SO-OVERLAP & JACCARD SIMILARITY
text: Definition 2 (SO-overlap). The (hard) overlap between two relations rl, rl′ is |SO(rl) ∩ SO(rl′)|.
Jaccard similarity can then be used as a standard symmetric belief that two relations IDs in different languages are equivalent:
bJ(rl ⇔ rl′) = |SO(rl) ∩ SO(rl′)| |SO(rl) ∪ SO(rl′)| . (2)
If bJ(rl ⇔ rl′) exceeds a threshold θ (tuned using dev set), we add (rl, rl′) to set AJ of ‘silver’ alignments. We define an additional RA loss term encouraging such embeddings to be aligned:
LRA-J = ∑
(rl,rl′ )∈AJ
bJ(rl ⇔ rl′) ∥∥rl − rl′∥∥1. (3)
We call this scheme Jaccard.

heading: 3.2.2 ASYMMETRIC SUBSUMPTION
text: A problem with Jaccard similarity is that it can give a symmetric high score to relation pairs having asymmetric implications between them. E.g., in the DBP5L data set, Jaccard similarity gives a large symmetric similarity score between locationCity and headquarter, or keyPerson and founders relations in different KGs. However, these relation pairs clearly involve asymmetric implication, and should not be linked.
Therefore, we need an asymmetric belief measure (bA) for one relation subsuming another, which we define as
bA(rl⇒rl′) = | SO(rl) ∩ SO(rl′)|
|SO(rl)| ∈ [0, 1] (4)
The asymmetry in (4) refrains from pushing those relation pairs together. This avoids some erroneous inferences, generally boosting precision — possibly at the expense of some recall, as this may also remove some “reasonable inferences”. Extending the logical statement (rl ⇔ rl′) iff (rl⇒rl′) ∧ (rl′⇒rl) to the fuzzy domain, we get bA(rl⇔rl′) = min {bA(rl⇒rl′), bA(rl′⇒rl)}, which we readily see as equivalent to
| SO(rl) ∩ SO(rl′)|min {
1 | SO(rl)| , 1 | SO(rl′ )|
} =
|SO(rl)∩SO(rl′ )| max{| SO(rl)|,|SO(rl′ )|} ∈ [0, 1]. (5)
Similar to Eqn. (3), we incentivize the model to align rl and rl′ if their bA(rl⇔rl′) is high. In particular, we search for pairs of ‘silver’ alignments (rl, rl′) ∈ AA, where rl = argmaxr′l bA(rl′ ⇒ r′l) and rl′ = argmaxr′ l′ bA(rl ⇒ r′l′). In other words, we want to apply the loss only to partner relations with mutually largest implication beliefs in that language. We define an asymmetric RA loss as:
LRA-A = ∑
(rl,rl′ )∈AA
bA(rl ⇔ rl′) ∥∥rl − rl′∥∥1. (6)
We call this method Asymmetric.

heading: 3.2.3 SOFT OVERLAP AND APPROXIMATION
text: In the above definitions involving SO, we assumed the (s, o) pairs were represented using canonical entity IDs. Unless explicit entity equivalences are provided, ‘hard’ SO overlap will underestimate relation similarities. We now extend these ideas to redefine SO-signatures using entity embeddings, which can be trained via gradient descent.
Recall that the KGC system obtains embedding vectors e for each entity e in the KG. Overloading notation, we modify our earlier definition of subject-object signature.
Definition 3 (Soft SO signature). For each relation r, SO(r) = {(s,o) : (s, r, o) ∈ KGU}.
Each element is the concatenation of the subject and object embedding vectors. The ith embedding pair in SO(r) is denoted SO(r)[i]. Two such pairs can be compared by, say, extending
cosine similarity with an AND-semantic: sim ( (s,o), (s′,o′) ) = σ(cos(s, s′))σ(cos(o,o′)), where σ is the sigmoid nonlinearity. This captures the requirement that the subjects have to be similar and the objects have to be similar. The key challenge is to compare two sets of such SO vectors, SO(rl), SO(rl′) for extending Defn. 2. A simple approach is to use a network to encode each SO-set [Zaheer et al., 2017, Lee et al., 2019] into a set embedding and then compare these (see Appendix B for details). However, recent work [Pabbaraju and Jain, 2019, Tang et al., 2020] suggests that we should drill down to pairwise interactions between set elements. To that end, consider two relations from different languages, rl, rl′ , that are candidates for alignment. Suppose the (s,o) pairs of rl are indexed by i and pairs of rl′ are indexed by j. We build a matrix Arl,rl′ of pairwise cosine similarities: Arl,rl′ [i, j] = sim ( SO(rl)[i], SO(rl′)[j] ) .
Definition 4 (Soft SO-Overlap). The continuous extension of |SO(rl) ∩ SO(rl′)|, denoted by SoftOv(rl, rl′), is defined as the value of the maximal matching on the weighted bipartite graph induced by Arl,rl′ .
Note that SoftOv(rl, rl′) depends on entity embeddings, which are to be trained. Ideally, we should be able to backpropagate various KGC and alignment losses past the solution of the matching problem to the entity and relation embeddings. Gumbel-Sinkhorn matrix scaling [Cuturi, 2013, Mena et al., 2018] can be used for this purpose, but it is computationally expensive at KG scales. (See Appendix C for details.) Here we use a computationally cheaper approximation: only if i is j’s strongest partner (i = argmaxi′ A[i ′, j]) and j is i’s strongest partner (j = argmaxj′ A[i, j ′]), we choose edge (i, j) in our matching. For each such edge (i, j), we add in SoftOv(rl, rl′) a score increment σ ( Arl,rl′ [i, j]w + c ) , where σ is the sigmoid nonlinearity, and w > 0, c ∈ R are model parameters trained along with all embeddings. We continue to use (4)-(5) as defined for Asymmetric, except we replace the hard overlap |SO(rl) ∩ SO(rl′)| by SoftOv(rl, rl′). We denote the beliefs computed thus by bSA (for soft asymmetric). The rest of the machinery of the previous section follows, i.e., we compute ‘silver’ alignments (rl, rl′) ∈ ASA, leading to a soft asymmetric RA loss as:
LRA-SA = ∑
(rl,rl′ )∈ASA
bSA(rl ⇔ rl′) ∥∥rl − rl′∥∥1. (7)
We call the resulting method SoftAsymmetric.

heading: 3.2.4 ADDING TEXT SIGNALS TO ALIGNKGC
text: BERT-INT [Tang et al., 2020] demonstrated the power of using mBERT [Devlin et al., 2019] to derive text-based features that effectively pull together duplicate entities. A short text passage t(e) is collected from the name (alias) and description of each entity e, which is then sent into mBERT, and the [CLS] embedding output by mBERT used as the textual representation of e. Optionally, to better map textual embeddings into the KG space, we use a small feed-forward network mlp(mbert(t(e))), which, for economy of notation, we will write as mbert(e). For entity alignment, we define an additional loss term LEA= ∑ el,el′
cos(mbert(el),mbert(el′))‖el − el′‖1 The intuition is that when the mBERT embeddings are similar, we want the L1 distance between KG embeddings to be small, and vice versa. Because we found Asymmetric generally better than Jaccard, we add the above mBERT-based loss term LEA to two previous variations. When we add it to Asymmetric, we call the resulting system Asym.+mBERT. When we add it to SoftAsymmetric, the resulting system is called SoftAsym.+mBERT, which is the full form of ALIGNKGC, with all other variations regarded as
ablations. In a similar way, we can also obtain a textual embedding of a relation and use that to create a textual RA loss. In our test bed, we did not have reliable surface forms of relations in multiple languages, so we turned off this component. Further details of this loss are described in Appendix D.

heading: 4. Experiments
text: We study the following research questions through our experiments. (1) Does our joint KGC, EA and RA model (ALIGNKGC) improve upon independent models for each of these tasks? (2) Is there any cross-lingual transfer of knowledge, for facts that may be mentioned in one language, but are queried in another? (3) What are the incremental contributions of soft overlap and mBERT’s surface form encoding in the overall performance of ALIGNKGC? (4) How does performance vary with the number of seed alignments (both entity and relation) provided at training time?

heading: 4.1 Experimental Settings
text: Dataset: Standard mono-lingual KGC datasets such as FB15k, FB15k-237, WN18, WN18RR, and YAGO-3-10, are not suited for evaluation of multi-lingual alignment or KGC.
A few recent EA datasets such as DBP15K [Sun et al., 2017] and DB2.0 [Sun et al., 2021] provide gold EAs (or ‘dangling’ nonEAs in DB2.0) between two languages at a time. They do not provide direct support for synergistic training and evaluation of
RA and KGC at the same time. Adaptations of such benchmarks in either direction appear fraught with potential unfairness. If we evaluate ALIGNKGC on two languages at a time, it loses its essential advantage of EAs across KGs in multiple languages, together with integrated RA and KGC supervision. On the other hand, if we collapse all but the target language into a “super language”, we severely distort the distribution of entity equivalence class sizes and frequency of relations, for other systems.
Most suited for our purpose is the recently-released DBP5L benchmark [Chen et al., 2020], which is derived from DBPedia in five languages: English (En), Greek (El), Spanish (Es), Japanese (Ja) and French (Fr). We use the same 60-30-10 splits of the KG triples into train-dev-test folds as in Chen et al. [2020] and combine the train sets of all source languages for training. Importantly, DBP5L also provides about 40% EAs between language pairs. We randomly pick half of seed entity alignments for training; the rest are used for testing. Because DBPedia uses a uniform relation vocabulary that is normalized across all languages, it cannot be directly
used to test relation alignment. To test RA capabilities of our models, we create separate ID spaces for each language. The original normalized IDs create gold data for alignment. The models do not get any seed relation alignments, and the whole alignment data is used for testing RA. Note that no asymmetric gold relation implication r1 ⇒ r2 are available, only equivalences r1 ≡ r2.
Table 1 lists the statistics of the five KGs in DBP5L. Unsurprisingly, En is the most wellpopulated, with 5–7 times more relations than other KGs. Figure 2 shows that a majority of the relation labels have associated string descriptions in only one of five languages (usually English). However, relations with monolingual aliases account for only 8% of fact triples. Meanwhile, almost 80% of fact triples use a relation label that has aliases in all five languages. Performance metrics: We evaluate ALIGNKGC on all the three tasks — KGC, EA and RA. As is common when evaluating a system for KGC, we regard test instances (s, r, ?) as a task of ranking o (on the basis of scores computed in equations (1)), with gold o∗ known. We report MRR (Mean Reciprocal Rank) and the fraction of queries where o∗ is recalled within rank 1 and rank 10 (HITS). The filtered evaluation removes valid train or test tuples ranking above (s, r, o∗) for scoring purposes.
To evaluate the system for EA, we use the test instance (el,≡, ?l′) as a task of ranking el′s, using the cosine distance between the entity embeddings of the language pair. We calculate Hits@1 and Hits@10 on the resulting rankings. A similar evaluation is done for RA by ranking rl′s for the query (rl,≡, ?l′). All pairs of languages are considered as l and l′ for these evaluations. Algorithms compared: For KGC, our baselines are KGCMONO and KGCUNION, and the recent multilingual KGC method called Knowledge Ensemble (KEnS) [Chen et al., 2020]. KEnS had strictly more information than ALIGNKGC, since it had access to aligned relation IDs at train time. We report scores from its best reported setting: KEnSb(RotatE).
The full form of ALIGNKGC (SoftAsym.+mBERT) uses the following loss function:
LKGC + αLreg + βLRA-SA + γLEA. (8)
Here Lreg is an L2 regularization on embeddings. α, β, γ ≥ 0 are tuned hyperparameters. We also evaluate other variations described in Section 3.2.
To understand the marginal utility of joint training over pre-trained knowledge in EA, we also compare against an extremely competitive mBERT-only baseline, since it is known that mBERT, by itself, can effectively align entities, given their aliases in different languages [Tang et al., 2020].
Since completion is most useful around nascent entities, we use the entity surface form(s) as t(e) and not, e.g., its full Wikipedia description or infoboxes. Training policies and hyperparameters: We fine-tune mBERT on entity surface forms to get 300-dim vectors. We use Adagrad as the optimizer and fine tune hyper-parameters on a dev set. We select among the following sets of hyper-parameter values: learning rate from {0.2,0.4,0.6,0.8,1}, α from {0.002, 0.02, 0.2}, β from {1, 2, 5, 10}, and γ from {1, 5, 10, 50}. We fix a batch size of 500. Our best choices for ALIGNKGC were: learning rate=0.8, α=0.02, β=5, and γ=50. We choose θ=0.01 for Jaccard. We use a negative sampling of 2000 instances for each positive triple when training ComplEx.
We sample initial entity and relation embeddings via N (0, 0.05). As a form of curriculum, we let relation alignments stabilize over a few iterations and then make the equivalence scores trainable.

heading: 4.2 Results: KGC performance
text: Table 3 reports KGC performance on the five languages. Not surprisingly, all models outperform KGCMONO, since it does not perform multilingual training. KGCUNION obtains much better scores because of combining different language KGs. Both baselines are outperformed by all ALIGNKGC variants. Each successive model enhancement — Jaccard, Asymmetric Model, Soft Asymmetric Model, and addition of mBERT — achieves progressively better performance. mBERT also provides similar boost to the ‘hard’ Asymmetric variant, but Asym.+mBERT is beaten by SoftAsym.+mBERT.
To analyze the performance further, we split the test set into two subsets: seen and unseen. The seen test set refers to those test facts that are already seen at train time, but in a KG of a different language. I.e., a test fact (sl, rl, ol) is in seen test if ∃(sl′ , rl′ , ol′) ∈ KGl′(train) s.t. sl ≡ sl′ , ol ≡ ol′ and rl ≡ rl′ , even though the model may/may not know these alignments. All other test facts are part of the unseen test set. Qualitatively, performance on the seen split represents the capacity of the model to memorize known facts in a language and align them to another language; the unseen split gives a true sense of a system’s inference capability, since the fact has likely not been read in any language at train time (except if an entity alignment is missing).
We first note that the performance on seen test is generally high, suggesting that the models do a good job of memorizing and aligning facts. We find that Jaccard signficantly helps with seen split, since it is able to learn similar embeddings for two aligned relations, and yields high scores for seen tuple in a different language. Asymmetric loss helps further as it removes false positives in RA, suffered by (symmetric) Jaccard. But it has a slight negative effect on unseen test instances, likely because of removal of some reasonable inferences. Making SO-overlap soft and trainable
enables more information flow, and better learning of embeddings and implication scores. This leads to significant improvement in both test splits. Finally, addition of mBERT yields massively better entity alignments, which has an impact on all tasks.
We notice that KEnS performs even worse than KGCUNION, even though it has knowledge of all relation alignments. We attribute this to (1) a stronger KGC baseline of ComplEx (with high negative sampling), compared to KEnS’s use of RotatE with only one negative sample, and (2) ALIGNKGC’s hard alignment policy of providing aligned entities in one unified KG with a single embedding, instead of KEnS’s approach of finding nearest entities in each language KG separately and then creating an ensemble.

heading: 4.3 Results: Alignment performance
text: Table 4 reports the performance of the various models on RA and EA tasks. We find that all ALIGNKGC variants outperform KGCUNION baseline by vast margins. We notice that asymmetric models perform better for more frequent relations. Because a much larger fraction of triples (see Figure 2) expresses these highly frequent relations, asymmetric models improve aggregate KGC performance. Because RA has not been studied on DBP5L to our knowledge, these are the best numbers yet.
We also note that Jaccard and Asymmetric models do not have any learnable parameters to explicitly encourage EA — any EA gains are due to better RA and KGC. Since those models improve EA performance substantially, we have evidence that other tasks can in turn aid better EA. The learnable asymmetric model, of course, explicitly incentivizes better alignment, leading to a further improvement
Simply computing mBERT embeddings of entity alias texts beats all ALIGNKGC variations that do not use mBERT, by a large margin. This is corroborated by Tang et al. [2020]: mBERT-based EA beats most other baselines reviewed in Section 5. However, joint training with the combination of mBERT with SoftAsymmetric shows a very significant improvement in EA, over and above mBERT. A more detailed report is in Appendix G.

heading: 4.4 Effect of the number of seed alignments
text: We also study the effect of the number of seed alignments available to the model at train time, on task accuracies. For this we vary the percentage of seed relation alignments (RA%) and entity alignments (EA%) on x and y axes, and observe KGC and EA HITS@1 performances. Because of diverse and unknown frequencies in its pretraining corpus, the entity alias embeddings provided by mBERT may be of variable quality. To better control for the amount of information available to the model as we vary EA%, we use the SoftAsymmetric model for this experiment.
Figure 5(a) shows KGC hits@1 and Figure 5(b) shows EA hits@1 against EA% and RA%. We observe that (predictably) increasing both EA% and RA% improves KGC performance. At any RA% value, increase in EA% has a powerful impact on both KGC and EA performances. Owing to the collapsing of entity nodes, it increases the number of triples that are seen in some language — these are easier to reason with for ALIGNKGC. Moreover, the model is able to infer many relation IDs as synonymous when more EAs are known, due to the explicit incentivization via asymmetric loss in the loss function — these significantly improve downstream KGC performance.
At low EA%, increasing RA% has limited KGC impact. In this setting, entities in different languages have limited connections, and so the KGs are sparsely connected. Increasing RA% adds further information on fact similarity across KGs, thus improving EA score, but the numbers remain low, due to the overall difficulty of the task.
At high EA% values, increasing RA% does not further improve EA performance. This is because aligned entities (as in the DBP5L data) generally target more frequent relations. Even at low RA%, this enables adequate alignment of frequent relations, leading further to adequate alignment of the entities attached to such relations. However, we posit that it still improves alignment of other entities (not in our gold set), leading to a substantial increase in KGC performance.

heading: 4.5 Soft overlap approximation quality
text: We described in Section 3.2.3 our fast approximation for maximal matching, required to evaluate the overlap between SO(r1) and SO(r2). In Figure 6 we show a scatter plot of a sample of relation pairs; the x-axis is the true optimal overlap found via the Hungarian matching algorithm, and the y-axis is our approximation. We can see that the approximation is very close to the optimal.

heading: 5. Related work
text: KG Completion: KGC, through learning embeddings for entities and relations, is a denselypopulated research landscape. Among the best performers are ComplEx [Trouillon et al., 2016], ConvE [Dettmers et al., 2018], and RotatE [Sun et al., 2019]. Almost all such systems are designed for a single KG, or are agnostic to the language used in entity and relation aliases.
KG alignment: Interest in KG alignment has grown rapidly of late. MTransE [Chen et al., 2017] uses TransE [Bordes et al., 2013] on each KG, while penalizing large distances between embeddings of equivalent entities. BootEA [Sun et al., 2018] is semi-supervised bootstrap EA algorithm. JAPE [Sun et al., 2017] builds attribute- and network neighborhood-based embeddings of entities and combines them with EA constraints. MuGNN [Cao et al., 2019] uses a graph neural network (GNN) to find node embeddings, which are compared to propose ≡ links. AliNet [Sun et al., 2020] also uses a GNN, with an attention mechanism over larger node neighborhoods. BERT-INT [Tang et al., 2020] combines local mBERT features with 1-hop neighborhood interactions. MultiKE [Zhang et al., 2019] treats EA and RA at par. However, they use relation names rather than their SO-signatures. JEANS [Chen et al., 2021] links KG entities to a text corpus. It uses TransE for the KG, skip-grams for the text, with additional alignment constraints.

heading: 6. Conclusion
text: We have presented ALIGNKGC, a system that jointly learns to complete multiple monolingual KGs in different languages (KGC) and align their entities and relations. KGC and entity alignment are known tasks, but relation alignment, to our knowledge, has never been integrated with them. ALIGNKGC operates on the KG constructed by taking a union of all monolingual KGs, and extends KGC models to use novel EA and RA loss terms. In extensive experiments, ALIGNKGC significantly improves KGC accuracy, as well as alignment accuracy, underscoring the value of joint alignment and completion.
Acknowledgments: Soumen Chakrabarti is partly supported by a Jagadish Bose Fellowship, grants from Google and IBM, and a Halepete Family Chair. Mausam is supported by grants from Huawei, IBM, Google, Bloomberg and 1MG, a Visvesvaraya faculty award by Govt. of India, and Jai Gupta Chair professorship. We thank the IITD HPC facility for compute resources.

heading: Appendix A. Example of KGC, EA and RA synergy
text: A.1 EA helps RA
Suppose a KGC+alignment system is given the equivalences between English (En) and Greek (El) entity names:
• Botafogo_de_Futebol_e_Regatas ≡ Μποταφόγκο ντε Φουτεμπόλ ε Ρεγκάτας (a football club)
• Brazil ≡ Βραζιλία Now suppose the system sees these two triples in En and El KGs, respectively: En: (Botafogo_de_Futebol_e_Regatas,
:::::::::::: home_arena, Brazil)
El: (Μποταφόγκο ντε Φουτεμπόλ ε Ρεγκάτας, :::: σπίτι :::::: αρένα, Βραζιλία) If this pattern occurs often enough, the system can infer the relation alignment “home_arena” = “σπίτι αρένα”. This is an example of inferring RA from EA.
A.2 EA, RA helps KGC
Suppose the system knows that • Rot-WeissEssen (English) ≡ Ροτ Βάις ΄Εσσεν (Greek) (a football club) • Essen (English) ≡ ΄Εσσεν (a town in Germany) • (Rot-WeissEssen, homeArena, Essen) holds in the English KG Then the system can potentially infer (Ροτ Βάις ΄Εσσεν, σπίτι αρένα, ΄Εσσεν) in the Greek KG. This is an example of EA and RA helping KGC.
A.3 KGC helps EA
Now suppose the KGC system has already learnt the (soft) inference pattern
([club], home_arena, [city]) and ([city], country, [country]) =⇒ ([club], home_arena, [country])
where home_arena and country (Χώρα in Greek) are assumed to be ‘universal’ across languages. Now if we know that (΄Εσσεν, Χώρα, Γερμανία) holds in the Greek KG, we can apply the above rule to infer (Ροτ Βάις ΄Εσσεν, σπίτι αρένα, Γερμανία). If the corresponding fact was already in the English KG as (Rot-WeissEssen, homeArena, Germany), Then we can infer the EA Γερμανία ≡ Germany.

heading: Appendix B. Differentiable set representations
text: Given a finite set X = {xi} where xi ∈ X , Zaheer et al. [2017] showed that any set function f(X) that is invariant to permutations ofX can be expressed as ρ (∑ x∈X φ(x) ) for suitable transformations
ρ and φ. In practice, capturing correlations between features of xs requires unreasonably deep/wide networks for ρ and φ. Pabbaraju and Jain [2019] proposed to present X , after applying adversarial permutations, to an order-sensitive recurrent network which can better capture correlations among xs, while using lower network capacity. The RNN must reduce variability of its set encoding in the face of these permutations. Lee et al. [2019] replaced the RNN with a transformer network.

heading: Appendix C. Matching via matrix scaling
text: Consider two sets {xi : i ∈ [I]} and {yj : j ∈ [J ]} with a metric dij = d(xi, yj). Let Tij ∈ R+ be a transportation matrix, subject marginal constraints to ∑ i Tij = cj for all j and ∑ j Tij = ri
for all i. Often, ri = cj = 1 or ri = 1/I and cj = 1/J . Our goal is to minT ∑
i,j dijTij . While this can be solved via linear programming, it is not clear how to backpropagate losses based on the optimal transportation back to networks that output {xi}, {yj}. (In our case, these set elements are functions of KG embedding vectors, through SO-sets.) Cuturi [2013] showed that if the objective is mildly augmented with an entropy term λH(T ) = −λ ∑ i,j Tij log Tij , then the optimal transport can be approximated by iterative row and column scaling of (dij), which are differentiable operations. However, this is computationally expensive for large KGs.

heading: Appendix D. Exploiting relation descriptions
text: Along with entities, relations, too, come with textual aliases in some KGs like WikiData. If we denote the textual description of relation r using t(r), we can also use mlp(mbert(t(r))) as additional intrinsic features of r. (This MLP is different from the one for entities.) Similar to entity alignment, if b(rl ⇔ rl′) is high, then we want mbert(rl) ≈ mbert(rl′). Accordingly, we can assess another
loss term LRA3 = ∑ rl≡rl′ b(rl ⇔ rl′) ∥∥mbert(rl)−mbert(rl′)∥∥1. (9) In ongoing work, we are preparing a new data set based on WikiData to evaluate the above extension.

heading: Appendix E. Soft SO-overlap generalizes discrete SO-overlap
text: Proposition 1. If entities are represented as 1-hot vectors (i.e., not using a continuous embedding space), then soft overlap in Definition 4 reduces to discrete overlap in Definition 2.
Proof sketch: it is easy to verify that with 1-hot vectors, soft overlap is exactly the size of the intersection of the two SO sets.

heading: Appendix F. Other ways to use mBERT signals
text: Beyond what is presented in the main paper, we explored some other ways to incorporate mBERT outputs, but these did not perform as well as the approach we chose in the end. One idea was to augment the soft SO signature with vectors output from BERT. Specifically, we redefine SO(r) as{(
s,mbert(s));o,mbert(o) ) : (s, r, o)∈KG } (10)
This MLP may be trained as BERT is pinned down, or BERT may also be fine tuned. This suggests the alternative loss term
LEA = ∑ el≡el′ ∥∥mbert(el)−mbert(el′)∥∥1 (11) We may not want a flat cosine (as matrix Arl,rl′ was defined), but introduce some and-like semantics for the match between the vectors with four fields (s1, s′1; o1, o ′ 1) and (s2, s ′ 2; o2, o ′ 2). As one example, we might use
σ ( cos((s1, s ′ 1), (s2, s ′ 2)) ) σ ( cos((o1, o ′ 1), (o2, o ′ 2)) ) . (12)
Relative weights balancing e and mbert(e) may also help.

heading: Appendix G. Detailed EA evaluation for all language pairs
text: In Table 7 we show EA performance on all pairs of languages, with one as source and other as target. For the two ‘mBERT’ columns, we fine-tune 10 mBERT models, one for each of ( 5 2 ) language pairs. For the two ‘mBERT(comb)’ columns, we combine all the language entity pairs to train a single global mBERT model, which gives a benefit on all language pairs. Adding mBERT(comb) to AlignKGC provides structural information to improve EA performance significantly in a majority of language pairs, particularly the ones with smaller, sparser KGs.

heading: Appendix H. Standard deviation over random initialization
text: The table below shows the standard deviation over three runs corresponding to AlignKGC+mBERT. Usually it is considerably smaller than 1%.
El Ja Fr Es En H@1 H@10 MRR H@1 H@10 MRR H@1 H@10 MRR H@1 H@10 MRR H@1 H@10 MRR 1.01 0.261 0.607 2.826 0.685 1.872 0.632 0.225 0.538 1.07 0.118 0.785 0.815 0.744 0.876
Appendix I. Statistical significance
The table below shows the p-values for a t-test between KGCUNION and Jaccard. Greek Japanese French Spanish English H@1 H@10 MRR H@1 H@10 MRR H@1 H@10 MRR H@1 H@10 MRR H@1 H@10 MRR 1.03E-07 4.1E-07 2.07E-08 2.84E-05 1.09E-06 2.85E-06 3.3E-06 1.23E-07 2.47E-07 6.19E-09 1.76E-08 7.93E-10 9.23E-06 2.28E-04 1.18E-05

heading: Appendix J. Code and data
text: Please visit https://www.cse.iitb.ac.in/~soumen/doc/AlignKGC/

Review summaries:
This paper introduces AlignKGC, a neural model that performs knowledge graph completion (KGC) on multilingual knowledge graphs that have entity and relation overlap. AlignKGC makes use of some of this overlap during training to optimize its parameters for two auxiliary tasks, entity alignment (EA) and relation alignment (RA). The resulting model demonstrates strong empirical results on DBP5L for all three tasks, and the paper demonstrates through extensive experiments the efficacy of each model components introduced.

This paper explores how entity alignment (EA), relation alignment (RA), and knowledge graph completion (KGC) can benefit each other. It proposes a model which jointly optimizes the three tasks using a linear combination of their losses. A contribution within this is a method for aligning relations in the absence of gold entity alignments. KGC is evaluated on each of 5 languages for which a KG is available, and EA & RA are evaluated jointly. The paper is easy to follow throughout.