Unsupervised Knowledge Graph Alignment by Probabilistic Reasoning and Semantic Embedding

1 Introduction

A knowledge graph (KG) organizes entities, attributes, relations, and other information in a structured format [Hogan et al., 2020]. One single KG is often incomplete while different KGs can complement each other to form a larger and more comprehensive KG via alignment, i.e., discovering equivalent entities, relations, and others across two KGs. Due to wide KG applications, KG alignment, especially entity alignment, has attracted massive attention.

KG embeddings have become a powerful tool to exploit KGs by encoding entities, relations, and others into a low-dimensional vector space [Wang et al., 2017]. Many embedding-based models have been proposed for entity alignment [Sun et al., 2020], and usually comply with the following paradigm. They first embed the to-be-aligned KGs into one vector space and then discover the mappings by calculating the vector distance or similarity.

∗Corresponding author (jasonxchen@tencent.com)

Although the embedding-based models have achieved encouraging results, they are still limited in some aspects especially in industrial deployment. These models usually require a number of known mappings (i.e., alignment seeds) for training. However, seed annotation requires massive manual work, which may not be available in practice. An industrial evaluation study has shown the number and the sampling distribution of alignment seeds can dramatically influence the alignment performance [Zhang et al., 2020]. The embeddingbased models emphasize establishing expressive embeddings to capture entity features and then independently predict each mapping, ignoring the holistic analysis and logical consistency, which often leads to some false mappings.

In contrast, conventional KG alignment systems exploit various more traditional techniques such as logical reasoning and lexical matching. For example, the classic system LogMap [Jim´enez-Ruiz and Grau, 2011] iteratively discovers mappings by lexical and graph matching, and repairs mappings by logical reasoning. PARIS [Suchanek et al., 2012] is another representative system that utilizes probabilistic reasoning and lexical matching. Specifically, after getting initial mappings by matching with attributes such as names, PARIS expands the entity and relation mappings in each iteration by inferring the entity and relation equivalence with probabilistic reasoning. As no training is needed, these systems never rely on any alignment seeds, and are quite scalable and efficient. It is worth noting that PARIS and LogMap often outperform those embedding-based models according to the recent studies [Sun et al., 2020; Zhang et al., 2020]. On the other hand, these conventional systems use traditional lexical and graph matching techniques that are weak at exploiting and utilizing the graph structure and other contextual information.

In light of the complementarity between the embeddingbased models and conventional systems, we propose to construct a unified framework that absorbs the advantages of both. The main challenge is to find the effective ways to make two completely different models work together. In this work, an unsupervised iterative framework named PRASE is proposed, which is composed of a Probabilistic Reasoning (PR) module and a Semantic Embedding (SE) module.

Specifically, the PR module initializes the mappings and infers logically consistent mappings with the entity embeddings from the SE module, while the SE module emphasizes learning high-quality cross-KG embeddings that encode the graph structures and the entity contexts. Note that the SE module is compatible with all kinds of embedding-based alignment models; while the PR module is currently developed based on the conventional system PARIS, but it can be extended to other reasoning-based systems such as LogMap.

The contributions of this paper are threefold. First, an unsupervised KG alignment framework termed PRASE is proposed, which integrates probabilistic reasoning and semantic embedding using an iterative algorithm. To the best of our knowledge, this is the first to combine traditional reasoning techniques and state-of-the-art embedding techniques for KG alignment. Second, the PRASE framework has been implemented with PARIS and multiple different embedding-based models. Third, the PRASE framework has been evaluated on five widely used datasets and one industry dataset. The results show the state-of-the-art performance of PRASE. On average, the F1-score of PRASE is 28.6% higher than the best embedding-based model and 5.96% higher than the best conventional system. Different settings of PRASE, such as the feedback from the SE module to the PR module and the iteration number, have also been studied.

2 Preliminaries

This section introduces the relevant background and the related work. The problem formulation is first given, and then the conventional system PARIS and the embedding-based models are briefly introduced.

2.1 ProblemFormulation

Let E, R, A, and V be the sets of entities, relations, attributes, and attribute values, respectively. A KG can be formulated as G = (E,R,A, V, T R , T A), where T R denotes the relation triples and T A represents the attribute triples. Specifically, T R and T A are formalized as

Given two KGs G and G′ , the problem of Entity Alignment is to discover the set of equivalent entity pairs (mappings) across G and G′ , denoted as

where the equivalence ≡ indicates that two entities refer to the same real-world object.

2.2 PARIS

Since the attribute triples are processed in a very similar way as the relation triples in PARIS, for convenience, we define E+ = E ∪ V , R+ = R ∪ A, and T + = T R ∪ T A . In order to derive mappings, PARIS measures the functionality and inverse functionality of each relation, i.e.,

where | · | denotes the set cardinality. The relation functionality and inverse functionality are used to determine the uniqueness of the head entity and tail entity, respectively. Take the relation founder as an example, if the relation functionality is equal to one (i.e., F(founder) = 1), it means that, given an organization, its founder can be uniquely determined. Note that the functionality and the inverse functionality of the relations are invariant for a given KG and can be computed in advance.

PARIS alternately computes the entity mappings and the subsumption relationships between relations. In computing the entity mappings, the probability of equivalence between two entities h and h′ , denoted by P(h ≡ h′ ), is estimated as 1

where P(r ⊆ r′ ) represents the probability that r is a subrelation of r′ . P(r ⊆ r′ ) is computed as

where (h, r, t) ∈ T +. Similarly, P(r′ ⊆ r) can also be computed. Note that the estimation of P(h ≡ h′ ) relies on the subsumption relationships between relations, i.e., P(r ⊆ r′ ) and P(r′ ⊆ r), and vice versa. Therefore, PARIS adopts an iterative strategy for optimization. In the initialization phase, P(r ⊆ r′ ) is set to a small value, e.g., 0.1; P(v ≡ v′ ) (v ∈ V ⊆ E+ and v′ ∈ V ′ ⊆ E′+) is set to 1 if v and v′ are identical literals, and to 0 otherwise. Although this initialization method is simple, it has been shown quite effective. Other advanced methods, e.g., using the edit distance between text literals to score the equivalence of attribute values, can also be adopted. In each iteration, the equivalence probabilities of entities are computed based on Eq. (2), and then the probabilities for the subsumption relationships between relations are computed based on Eq. (3). The system self-iterates multiple times until convergence. Finally, the PARIS system outputs the entity mappings, denoted by ˜ Y P , along with their probabilities (equivalence degrees), denoted by P o (e ≡ e′ ) with (e, e′ ) ∈ ˜ Y P and superscript o indicating output. Please see [Suchanek et al., 2012] for more details.

2.3 Embedding-based KGAlignment

Embedding-based KG alignment models usually work in the following two steps. First, the embeddings of KG components are learned based on some translational models (e.g., TransE [Bordes et al., 2013]), graph neural networks [Kipf and Welling, 2017] or other KG embedding algorithms [Guo et al., 2019]. Entities of different KGs are embedded in the same vector space through strategies including parameter sharing, parameter swapping, embedding transformation, and embedding calibration. Then, entity mappings are predicted based on the similarity measure of the entity embeddings.

1 Since PARIS augments the to-be-aligned KGs with the inverse triples, the formula actually accounts for both head and tail entities.

Take the typical embedding-based model MTransE [Chen et al., 2017] as an example. First, MTransE adopts TransE to learn embeddings by minimizing the following loss:

where || · || denotes the Euclidean norm operation; h, r, and t denote the m-dimensional embeddings of h, r, and t, respectively. To ensure the entities are embedded in the same vector space, an embedding transformation strategy is adopted. Let S = {(e, e′ )|e ∈ E, e′ ∈ E′ } be the alignment seeds, it minimizes the loss given by ∑(e,e′ )∈S ||Me-e′ ||, where e and e′ denote the entity embeddings, and M ∈ Rm×m is a transformation matrix. After learning M, entity embeddings of G are transformed into the entity vector space of G′ , i.e., e := Me. Finally, entity mappings, denoted by ˜ Y E , and their corresponding similarity scores in [0, 1], denoted by S(e ≡ e′ ) with (e, e′ ) ∈ ˜ Y E , can be obtained by performing nearest neighbor search in the embedding space.

There are some other embedding-based models. For example, GCN-Align embeds the KGs using graph convolutional networks [Wang et al., 2018]. BootEA adopts a bootstrapping strategy with an alignment editing method to reduce error accumulation, so as to overcome the lack of training data [Sun et al., 2018]. MultiKE embeds the entities with their names, relations, and attributes considered via multi-view learning [Zhang et al., 2019]. Please see [Sun et al., 2020; Zhang et al., 2020] and for more comprehensive reviews.

3 Framework

In this section, the overview of the PRASE framework is given at first, and then its probabilistic reasoning module and semantic embedding module are introduced with details.

3.1 PRASEOverview

Figure 1 shows the workflow of the PRASE framework that includes the Probabilistic Reasoning (PR) module and the Semantic Embedding (SE) module. First, the PARIS-based PR module is performed on the input KGs to discover entity mappings ˜ Y P with their probabilities P o (e ≡ e′ ). Then, the highly confident entity mappings are selected as the alignment seeds S, and the SE module is trained subsequently based on these seeds. After training, the SE module predicts mappings on the entities that have not been aligned by the PR module (denoted by ˜ U P ). The resultant entitymappings ˜ Y E with the similarity scores S(e ≡ e′ ) and the entity embeddings (denoted by ˜ E E = {e|e ∈ E} ∪ {e′ |e′ ∈ E′ }) are then fed back to the PR module. The above process can be iterated K times, and the PR module finally outputs the entity mappings. The iterative algorithm is also shown in Algorithm 1.

3.2 Probabilistic ReasoningModule

The PR module is constructed based on the PARIS system with the augmentation from KG embeddings. Let k be the iteration index of PRASE. In the initial iteration (k = 0), the PR module first computes relation functionality and inverse functionality according to Eq. (1), and then alternatively computes mappings following Eqs. (2) and (3). In the subsequent iterations (k = 1, · · · ,K), the SE and the PR modules are alternately performed. In the kth iteration (k > 0), the PR module is initialized based on its previous output and the output of the SE module. Specifically, the probabilities of subrelationships are set to the values of the (k - 1)th iteration, i.e., P ik (r ⊆ r′ ) = P ok-1 (r ⊆ r′ ) with superscripts i and o indicating the meanings of input and output, respectively, and the probabilities of entity mappings are initialized as

where P i and P o represent the input and the output mapping probabilities of the PR module, respectively; α1, α2 ∈ (0, 1] are two hyperparameters; δ1 ∈ [0, 1) is a threshold value; subscripts k and k-1 indicate the variables in the kth and the (k - 1)th iterations, respectively. This customized initialization method for PARIS directly exploits the output of the SE module, through which the PR module could absorb the benefits captured by KG embeddings and further expand the mappings by reasoning. Note that the PR module is robust and can correct those unreliable entity mappings from the SE module, since it is based on probabilistic reasoning.

In addition to directly utilizing the output from the SE module, we also seek to fully exploit the semantic and structural information contained in the embeddings during the self-iterations of the PR module. The probability of the equivalence between two entities is updated according to a modified estimation, which is given by

where e and e′ denote the embeddings of entities e and e′ , respectively; sim(·, ·) is a similarity function; β ∈ (0, 1) is a trade-off hyperparameter balancing the embedding similarity and the probability estimated by Eq. (2). Eq. (5) replaces Eq. (2) in the original PARIS. It complements the PR module with the deep structural information learned from the SE

Algorithm 1 PARIS-based PRASE Implementation

Input: two KGs G and G′ Parameter: iteration number K, hyperparameters α1, α2,

and β, thresholds δ1, δ2, and δf, similarity function sim(·, ·)

• 1: Initialize the PRmodule using Eq. (1);
• 2: Perform the PRmodule using Eqs. (2) and (3);
• 3: Generate ˜ Y P 0 and ˜ U P 0 ;
• 4: while k = 1, . . . ,K do
• 5: Generate Sk based on ˜ Y P k-1 and δ2;
• 7: Test the SE module on ˜ U P k-1 ;
• 6: Train the SE module on Sk;
• 8: Generate ˜ Y E k and ˜ E E k ;
• 9: Initialize the PR module using Eq. (4);
• 10: Perform the PRmodule using Eqs. (5) and (3);
• 11: Generate ˜ Y P k and ˜ U P k ;
• 12: end while
• 13: Generate ˜ Yf based on ˜ Y PK and δf;

Output: ˜ Yf

model, and it can help the PR module estimate the probability of entity mappings more accurately. The function sim(·, ·) measures the similarity between two embeddings, of which the range should be [0, 1]. A simple choice of sim(·, ·) is cosine similarity, i.e., sim(e, e′ ) = (e · e′ ) / (||e|| · ||e′ ||).

After several self-iterations, the PR module converges and outputs a new round of alignment results ˜ Y P k as well as the unaligned candidates ˜ U P k . Specifically, ˜ U P k = {e|e ∈ E, ∀e′ ∈ E′ , (e, e′ ) /∈ ˜ Y P k }∪{e′ |e′ ∈ E′ , ∀e ∈ E, (e, e′ ) /∈ ˜ Y P k } is a set of unaligned entities, which is later used as the test data for the SE module to compute the similarity score Sk+1(e ≡ e′ ). In the last iteration (k = K), the final output entity mappings of the PRASE framework are given by the PR module, denoted as ˜ Yf = {(e, e′ )|(e, e′ ) ∈ ˜ Y PK , P oK (e ≡ e′ ) > δf}, where δf ∈ [0, 1) is a threshold value.

3.3 Semantic EmbeddingModule

In the kth iteration, ˜ Y P k-1 is refined to generate reliable alignment seeds Sk for training the SE module. A feasible method to obtain Sk is to set a threshold δ2 ∈ [0, 1), and Sk = {(e, e′ )|(e, e′ ) ∈ ˜ Y P k-1 , P ok-1 (e ≡ e′ ) > δ2}. Although in most cases, there are still some incorrect entity mappings in Sk, the abundant correct mappings in Sk can still provide useful information. As mentioned before, the SE module outputs (i) entity mappings via a nearest neighbour search among ˜ U P k-1 , and (ii) entity embeddings ˜ E E k . Since almost all embedding-based models can output entity mappings and embeddings, PRASE can choose almost any existing embedding-based model as the SE module. Algorithm 1 shows the whole process of the PRASE framework.

4 Evaluation

This section presents the evaluation of PRASE, and the code is available at https://github.com/qizhyuan/PRASE-Python.

4.1 Datasets

In the experiments, the following datasets are used, and the statistics of these datasets are presented in Table 1.

OpenEA Datasets: The OpenEA datasets 2 are constructed based on DBpedia, YAGO, and Wikidata [Sun et al., 2020]. We use all their large-scale datasets of the version "V2" that has more complex KG structures. They include two crosslingual datasets (i.e., EN-FR-100K-V2 and EN-DE-100KV2) and two cross-KG datasets (i.e., D-W-100K-V2 and DY-100K-V2). We also use a small dataset D-W-15K-V2, a relatively difficult dataset as reported by [Sun et al., 2020]. In the following, the annotation "-V2" is omitted.

Industry Dataset: MED-BBK-9K is an industry datasetproposed by [Zhang et al., 2020], which is built from an authoritative medical KG and a KG extracted from Baidu Baike, a Chinese online encyclopedia.

4.2 Experimental Setting

The original implementation of PARIS is in Java. 3 We reimplemented PARIS in Python and updated it as the PR module such that it can easily work with the embedding-based models that are also implemented in Python. We adopt twelve competitive KG alignment methods as the baselines. They can be categorized into (i) embedding-based models that include MTransE [Chen et al., 2017], IPTransE [Zhu et al., 2017], GCNAlign [Wang et al., 2018], BootEA [Sun et al., 2018], RSN4EA [Guo et al., 2019], IMUSE [He et al., 2019], MultiKE [Zhang et al., 2019], and RDGCN [Wu et al., 2019], (ii) conventional systems including PARIS and LogMap, and (iii) two simple matching models using either the edit distance (denoted by STR-Match) or the word embedding similarity (denoted by EMB-Match) between entity names. We adopt the implementations of the embedding-based models from OpenEA [Sun et al., 2020] with the same dataset division: 20%, 10%, and 70% of the entity mappings for training, validation, and testing, respectively. Except for embeddingbased models, other models are performed in an unsupervised setting. STR-Match and EMB-Match compute the similarity between entity names with a threshold of 0.5. In the overall result analysis, BootEA and MultiKE are used as the SE module and the resultant models are denoted by PRASE-BootEA and PRASE-MultiKE; while in the ablation study, more embedding-based models are evaluated. We set α1 = α2 = 1, β = 0.8, δ1 = δ2 = δf = 0.1, and choose cosine similarity as sim(·). Since a small value of K is found to be sufficient for PRASE to demonstrate its effectiveness, we set K = 1 in the experiments unless specified.

2 https://github.com/nju-websoft/OpenEA

3 http://webdam.inria.fr/paris/

Our experiments are conducted on a workstation with an Intel Xeon E5 CPU and an NVIDIA Tesla M40 GPU. The average time cost of our PARIS implementation on the four 100K datasets is 1697 seconds 4 , while the average time costs of BootEA and MultiKE are 24727 and 3198 seconds, respectively. Therefore, the time cost of the PRASE framework is acceptable even with several iterations executed. As a comprehensive metric, F1-score is used to evaluate different models in the following experiments with the corresponding precision (P) and recall (R) reported as supplementary metrics. Since embedding-based models output a list of matching candidates for each entity, their precision, recall, and F1-score are actually equivalent to Hits@1. The best performance is bolded and the second best is underlined in our experiments.

4.3 Overall Results

Table 2 presents the experimental results (here, we directly use the results from [Sun et al., 2020] for embedding-based models and LogMap on OpenEA datasets). The results show that the two PRASE models consistently outperform all the baselines on all the datasets except D-Y-100K in terms of recall and F1-score. STR-Match reaches full scores and outperforms all other models on D-Y-100K. However, the recall of STR-Match is significantly lower than the proposed models on the other five datasets. Actually, D-Y-100K is an easy dataset on which STR-Match achieves a perfect alignment, while the proposed models are almost perfect. PRASEBootEA performs best on EN-FR-100K, D-W-100K, and DW-15K, while PRASE-MultiKE performs best on EN-DE100K and MED-BBK-9K. Besides, the F1-score of PRASEMultiKE reaches 0.711 on MED-BBK-9K, significantly surpassing PARIS by 0.212. Compared with PARIS, the precision of the proposed models is slightly decreased on ENFR-100K, D-W-100K, and D-W-15K, but the recall significantly increases. It reflects that although the incorrect entity mappings predicted by the SE module can have a negative impact on the performance, the useful information provided by the SE module can still help the PR module find more potential alignments. Table 2 also shows that the unsupervised PRASE models significantly outperform all the supervised embedding-based models with an average improvement of 28.6% in F1-score, which further confirms the effectiveness of the PRASE framework.

4 The average running time by the Java implementation is 89 s.

4.4 Ablation Studies

Impact of Embedding Feedback: In PRASE, the PR module uses both the entity mappings and the embeddings as the feedback from the SE module. To explore the role of these two types of feedback, two additional PRASE frameworks are evaluated: one uses only the mapping feedback (denoted with suffix "-M") and the other uses only the embedding feedback (denoted with suffix "-E"). Table 3 shows the comparison results. Generally, all three PRASE frameworks achieve good results, and the framework using both types of feedback performs the best on almost all datasets. Besides, the precision of the PRASE framework using only entity embeddings is higher than or close to the baseline PARIS, while the precision of the PRASE framework using only entity mappings is lower in most cases. Furthermore, the use of entity mappings can significantly improve the recall but compromise the precision; the use of entity embeddings tends to maintain the precision, while the recall improvement is relatively limited. Table 3 also shows that using both types of feedback can significantly improve the recall while maintaining the precision.

Impact of Different SE Modules: To analyze the impact of using different SE modules, four additional PRASE models are constructed based on MTransE, IPTransE, GCNAlign, and IMUSE. Table 4 shows their performance. It can be observed that all the PRASE models achieve a higher F1-score than PARIS on all datasets except for PRASE-MTransE on MED-BBK-9K, which indicates that the PRASE framework is robust and not sensitive to the selection of the SE module. However, different SE modules may bring different degrees of improvement. Table 5 shows the Hits@1 of the entity mappings predicted by different SE modules on ˜ U P . Their performance is positively correlated to the corresponding PRASE models. Specifically, BootEA and MultiKE outperform the other SE modules, and their corresponding PRASE models also perform better on most datasets. Besides, the Hits@1 of MTransE is only 0.9%, which is consistent with the degraded performance of PRASE-MTransE compared with PARIS. We additionally perform PRASE-MTransE-E on MED-BBK-9K, and the F1-score reaches 0.511, which shows that the entity embeddings can still provide useful information and benefit the PR module, even if the SE module has a poor alignment performance. Briefly, the benefit of the SE module is closely related to the selected embedding-based model. It is recommended to choose an advanced embedding-based model such as BootEA or MultiKE. If the SE module has a poor alignment performance, it would be better to only use entity embeddings as the feedback to the PR module.

Impact of Iteration Number: To analyze the impact of the iteration number K, we additionally perform PRASEBootEA and PRASE-MultiKE on D-W-15K and MED-BBK9K with K = 2, 3, and 4. The results are shown in Figure 2, where the F1-score increases as K increases. Therefore, more iterations may help to improve the PRASE model. However, in practice, since the framework converges quickly and the embedding learning in each iteration costs much more time, it is suggested to set K to a small value.

5 Conclusion and Discussion

In this work, an unsupervised KG alignment framework PRASE has been proposed, which consists of a probabilistic reasoning module, a semantic embedding module, and an iterative algorithm for the interaction of the two modules. PRASE is compatible with most existing embedding-based models. Extensive experiments on six datasets have verified the state-of-the-art performance of PRASE. More importantly, this work has shed light on the potential of unifying probabilistic reasoning and semantic embedding for KG alignment. It is therefore necessary to call for such hybrids for academic research and industrial applications. For future work, we plan to expand PRASE with other reasoning-based systems (e.g., LogMap) and enhance the interaction between the PR and SE modules by, e.g., injecting prior knowledge defined by the KGs' ontologies [Chen et al., 2021]. We will also utilize the alignment of KGs to address KG refinement problems such as error detection [Chen et al., 2020].