Global Structure and Local Semantics-Preserved Embeddings for Entity Alignment

1 Introduction

KGs, such as DBpedia [Lehmann et al., 2015] and YAGO [Rebele et al., 2016], store structured knowledge as triples of the form <head, relation, tail>, which can support many natural language processing applications, e.g., question answering [Zhang et al., 2018] and information extraction [Hoffmann et al., 2011]. Unfortunately, KGs are usually separately constructed and often contain different but complementary knowledge, thus it is essential to merge different KGs into a unified one. Entity alignment (EA) [Hao et al., 2016; Trisedya et al., 2019; Cao et al., 2019], also known as Entity Resolution (ER) [Nie et al., 2019; Fu et al., 2019] in database community, is such a technique that aims to find entities in different data sources that refer to the same real-world object. For example, by aligning entities "CA" and "California" from triples <Apple Inc., locatedIn, CA> and <California, country, USA>, we can obtain additional knowledge <Apple Inc., locatedIn, USA>.

∗Corresponding author.

Currently, most EA approaches firstly represent entities as distributed vectors, and then align two entities if they have similar representations [Hao et al., 2016]. To accurately represent an entity, existing approaches can be classified into two categories. The first one is translation-based [Bordes et al., 2013; Wang et al., 2014] embedding methods, which represent an entity by exploiting its local semantics, i.e., the relational triples in which this entity appears. The other one is GCN-based [Kipf and Welling, 2017; Wang et al., 2018] methods, which represent an entity by exploiting the global KG structure, i.e., all neighbors of this entity. The global structure-based methods represent an entity by aggregating all its neighbors' features, which can provide comprehensive and robust information for entity alignment, as it is less vulnerable to the missing of partial information and the schema heterogeneity of different KGs. However, it may lose fine-grained details for EA. For example in Figure 1, entities New York (state) and New York (city) cannot be distinguished using the KG structure only as they have the same neighbors, and fine-grained relations are needed to distinguish them, i.e., hasRiver and adjoin. In contrast, the local semantics-based methods represent an entity by considering the triples in which it appears, which can provide fine-grained information for EA. However, it is not robust enough if some triples are missing or two KGs are represented using different schemas. Therefore, we believe global KG structure and local relation semantics can provide complementary information for each other and can be jointly exploited for better EA performance.

In this paper, we propose Structure and Semantics Preserving (SSP) network for entity alignment, which can learn the entity representations by simultaneously exploiting both the global structure and local semantics of knowledge graphs. Given a knowledge graph, our method learns entity representations in a coarse-to-fine manner. First, we employ a GCN to explicitly encode the global structure features into entity representations, which can provide comprehensive and robust information for entity alignment. Then, we adopt a modified translation-based method to refine entity representations by further exploiting the local semantics of entities. This learning strategy will ensure that the entity representation is both robust and accurate: the global structure can provide a comprehensive representation by aggregating all information about an entity's neighbors, and then the fine-grained local semantics is used to refine the representation so that even similar entities, such as New York (state) and New York (city), can be distinguished. We conduct extensive experiments on several EA benchmarks (DBP15k and DWY100k), the experimental results show that our model achieves new stateof-the-art performance by outperforming previous baselines by a large margin. Detailed analyses verify the effectiveness and robustness of our proposed model.

The main contributions of this paper are:

• We propose to jointly leverage the global structure and local semantics for entity alignment. By exploiting both the global structure and local semantics, the entity representations can be both robust and accurate.
• We design a Structure and Semantics Preserving (SSP) network which can learn the entity representations by simultaneously exploiting both the global structure and local semantics of KGs in a coarse-to-fine manner.
• Because entity representation is fundamental to many NLP applications, we believe the proposed method can also benefit many other entity representation-based tasks, e.g., link prediction and entity linking.

2 RelatedWork

In this section we briefly review both the Translation-based and GCN-based entity alignment methods.

Translation-based Entity Alignment. Translation-based methods [Bordes et al., 2013; Wang et al., 2014] represent entities by estimating the plausibility of relational triples using a scoring function, e.g., MtransE [Chen et al., 2016] learns cross-lingual transitions between different embedding spaces, JAPE [Sun et al., 2017] jointly trains the attribute and structure embeddings, TransEdge [Zequn et al., 2019] extends TransE to an edge-centric fashion. The main advantage of translation-based methods is that they can model fine-grained relation semantics. However, they cannot preserve the global structure of KGs.

In the meantime, there are also some efforts that address the data scarcity issue. Iterative methods have been employed to improve EA performance. IPTransE [Zhu et al., 2017] and BootEA [Sun et al., 2018] fuse knowledge from different KGs by expanding the prior alignment seeds in a bootstrapping way. KDCoE [Chen et al., 2018] performs iterative co-training of a KG embedding model and an entity description embedding model, which utilizes the entity description to assist entity alignment. Though effective, these iterative methods require more training time and computing resources. Compared with these methods, we tackle the EA problem in an end-to-end, non-iterative paradigm.

GCN-based Entity Alignment. GCN-based [Kipf and Welling, 2017] methods represent an entity by recursively aggregating its neighbors' features. GCN-Align [Wang et al., 2018] seeks to embed entities and attributes as lowdimensional vectors. AliNet [Sun et al., 2020] introduces distant neighbors to overcome graph heterogeneity. The main advantage of GCN-based methods is that they can obtain comprehensive and robust entity representations. However, it is difficult to model fine-grained relation semantics - because GCN jointly considers all neighbors and often ignores semantic types of relations. Following this idea, RDGCN [Wu et al., 2019a] introduces the relation information of KGs through graph interactions, AVR-GCN [Ye et al., 2019] devises the relation embeddings via entity embeddings, while HGCN [Wu et al., 2019b] approximated relation representations via adjacent entity embeddings. Although these methods can encode relations implicitly, they cannot accurately model fine-grained relation semantics, which may severely restrict their EA performance.

In addition, there are also some other works that utilize additional information, such as attribute [Trisedya et al., 2019] or description [Yang et al., 2019] information to enhance entity representations. Since such additional information isn't always available, this paper merely utilize KG structure to tackle EA problem.

Based on the above discussion, we find that global structure and local semantics provide complementary information for EA: global structure can provide comprehensive and robust information for entity representations, while local semantics can provide fine-grained details to refine the coarse-grained entity representations. In this paper, we make complementary use of them to learn the global structure and local semanticspreserved entity representations for EA.

3 ProblemFormulation

This section formulates the entity alignment problem. A knowledge graph G = (E, R, T ) is a directed graph consisting of a set of entities E, relations R, and triples T. A triple t = (ei, rij, tj) ∈ T denotes head entity ei is connected to tail entity ej through relation rij.

Now suppose we have two different KGs to be aligned, where the source KG is denoted as G1 = (E1,R1, T1) and the target KG is denoted as G2 = (E2,R2, T2). Given a set of pre-aligned entity pairs S = {(u, v)|u ∈ E1, v ∈ E2, u ↔ v}, where ↔ denotes equivalence, entity alignment task can be formulated as automatically discovering more aligned entity pairs based on the existing alignment seeds. Specifically, given two KGs G1 and G2, and a set of alignment seeds S, our method will first merge two KGs by injecting the alignment seeds, then learn entity representations with a guarantee that aligned entities should have as similar embeddings as possible, finally new aligned pairs are found using similarities between entities.

4 Structure and Semantics Preserving Networks for Entity Alignment

This section describes how to simultaneously exploit the global structure and local semantics information for entity alignment. To this end, we employ a coarse-to-fine strategy. Firstly, we employ a GCN [Kipf and Welling, 2017] to encode the KG structure into entity representations, which is comprehensive and robust. Afterward, we refine the entity representations by leveraging its local semantics via a modified translation-based embedding model. The above two modules are learned in an end-to-end manner. Figure 2 depicts the overall architecture of our model, which mainly consists of two parts: Global Structure Preserving Network and Local Semantics-based Refining Network. In follows, we describe these two networks in detail.

4.1 Global Structure Preserving Network

The global structure of KG provides useful information for entity alignment, i.e., entities with similar neighboring structures are highly likely to be aligned. This paper employs a GCN to explicitly encode the global KG structure information. Specifically, GCN follows a neighborhood aggregation scheme, where the representation vector of a node is computed by recursively aggregating and transforming representation vectors of its neighboring nodes. Concretely, GCN consists of several stacked layers. Given a set of node features X(l) = {x(l) 1 , x(l) 2 , · · · , x(l) n |x(l) i ∈ Rd(l) } as input to GCN layer l, where n is the number of nodes (entities) in the unified KG, and d(l) is the number of features in layer l, the output of the l-th layer is obtained following the convolution computation:

where σ is an activation function; A is a n × n adjacency matrix that denotes the structure information of the KG; ˆ A = A + I, and I is the identity matrix; ˆD is the diagonal node degree matrix of ˆ A; W (l) ∈ d(l) ×d(l+1) is the weight matrix of the l-th layer in the GCN, d(l+1) is the number of features in the (l + 1)-th layer.

Inspired by HGCN [Wu et al., 2019b], we also employ layer-wise highway gates [Srivastava et al., 2015] to control the balance of how much neighborhood information should be passed to a node and reduce noise propagation, where the output of a layer is the weighted sum of its input and the original output via gating weights T (X(l) ):

We also find that initializing the weight matrix WT in each GCN layer using a diagonal identity matrix can further reduce parameters and boost performance. Based on GCN, our model can explicitly preserve the global structure information of KG and encode it into the learned entity representations.

4.2 Local Semantics-based Refining Network

The structure information of KGs provides useful information for representing entities. However, as mentioned above, it is hard to distinguish similar entities using KG structure only, especially for entities that have fine-grained differences. To accurately disambiguating entities with similar structures, we refine the structure-based representation using the local semantics information via translational algorithms. However, conventional translational methods are not expressive enough to model complex relation types due to their strong assumptions on the relational triples. Inspired by the recent work ELMo [Peters et al., 2018] that has achieved state-of-theart performance in many NLP tasks, we propose a modified translational method with contextualized relation learning for knowledge embedding. Our method is based on the assumption that relations occurred in different entity contexts should have distinct embeddings, regardless of whether they have the same surface forms or not. Following this idea, we calculate the relation embeddings based on the adjacent entities and the relation itself. This is intuitive that even relations with the same surface form but occurred in different contexts should have minor differences in their semantics.

Contextualized Relation Learning. Given a relational triple (h, r, t) ∈ T, we first calculate the contextualized relation embedding based on the head h, tail t and relation r itself. The entity embeddings are the output of the last layer in the HGCN described previously. Specifically, we first concatenate the embeddings of head entity h and tail entity t to aggregate context information and then use a one-layer MLP with non-linear activation to compress the entity contexts:

where [; ] means vector concatenation. Then, we utilize context projection inspired by TransEdge [Zequn et al., 2019] to further incorporate the relation embedding itself. As pointed out in TransEdge, projecting embeddings onto hyperplane has shown promising effects on the processing of disparate feature representations. The major differences between our model and TransEdge are that they rely solely on a translational method to model KG structure and introduce extra interaction entity vectors for edge-centric relation calculation. While our model employs an HGCN network to explicitly preserve the graph structure information and utilize parameter efficient relation representation method to learn knowledge embeddings, which requires less computing cost. Let nht be the norm vector of the hyperplane supported by h and t. The contextualized relation embedding rc is computed via vector projection as follows:

The contextualized relation learning mechanism can accurately model fine-grained relation semantics. We will testify the effectiveness of relation contextualization in the experiments.

Entity Embeddings Refinement. Having obtained the contextualized relation embedding rc, we apply it to the translational model to refine entity embeddings. Like TransE, we define a scoring function to estimate the plausibility of relational triples as:

where relational triples that exist in the KG are expected to be more plausible with low energy score. By distinctly modeling relational triples in the KG, we can further incorporate complex relation semantics information into entity embeddings and obtain more expressive knowledge embeddings. Therefor better entity alignment performance can be achieved.

Alignment Prediction. Having obtained entity embeddings with global structure and local semantics information preserved, we align entities using the similarities between their embeddings. Specifically, for each entity to be aligned, we rank all candidate entities based on their similarities to the target entity.

4.3 End-to-End Learning

For training, we regard all observed relational triples in KGs as positive samples, while all unobserved ones as negative samples (either false or missing triples). It is expected that positive samples are supposed to have lower energy than their negative counterparts. We thus minimize the following limitbased loss function as in [Zequn et al., 2019] to distinguishably separate positive triples from negative ones, aiming to gather aligned entities together, and in the meantime tell unaligned ones apart.

α is a hyper parameter for balancing positive and negative samples, β1 and β2 denote positive and negative margins respectively. [x]+ denotes max(0, x). T + is the set of observed triples, and T - is the negative triples set with each triple created using the truncated uniform sampling strategy.

5 Experiments and Discussion

5.1 Experimental Settings

Datasets. We evaluate different methods using the following benchmark datasets.

• DBP15K [Sun et al., 2017] is extracted from DBpedia, which contains three cross-lingual datasets: DBPZH-EN, DBPJA-EN and DBPFR-EN, with popular entities from English to Chinese, Japanese and French respectively. Each dataset has 15 thousand interlingual links (ILLs) as reference alignments.
• DWY100K [Sun et al., 2018] contains two large-scale monolingual datasets, namely DBP-WD (DBpediaWikidata) and DBP-YG (DBpedia-YAGO3). Each dataset has 100,000 aligned entity pairs and hundreds of thousands of relational triples. All the datasets use the 3:7 train-test split. We refer the readers to the original papers for detailed data statistics.

Baselines. We compare with both translation-based and GCN-based EA baselines: 1) translation-based methods - MtransE [Chen et al., 2016], IPtransE [Zhu et al., 2017], BootEA [Sun et al., 2018], TransEdge [Zequn et al., 2019], MMR [Shi and Xiao, 2019]; and 2) GCN-based methods - GCN-Align [Wang et al., 2018], AliNet [Sun et al., 2020], where MMR is state-of-the-art end-to-end EA method that merely uses KG structure information. For fair comparison, we don't compare with EA methods which require additional information (entity names, attributes or descriptions), such as KDCoE [Chen et al., 2018] and HMAN [Yang et al., 2019].

System Settings. The hyper-parameters used in our model are tuned on development set and their values are: β1 = 0.2, β2 = 2.0, α = 0.8. The dimensionality for embeddings in DBP15K and DWY100K datasets are 300 and 200 respectively. We set different learning rates for the structure preserving network and semantics-based refining network, they are 0.001 and 0.005 respectively. For DBP15K dataset, we uniformly sample 20 negative examples in its nearest neighbors for each relational triple (half for head and tail entities respectively), for DWY100K, the sampling size is 30. We implement our model using Pytorch - a popular deep learning framework.

Evaluation Metrics. Following previous work [Sun et al., 2017], we use Hits@k, mean rank (MR) and mean reciprocal rank (MRR) to measure the performance. For MR, the smaller, the better; for other metrics, the larger, the better.

5.2 Overall Results

Table 1 and Table 2 show the overall results of all approaches on the DBP15K and DWY100K datasets. Since MMR [Shi and Xiao, 2019] doesn't release their source code, we don't report the results on DWY100K dataset. From the results, it can be seen that:

• By exploiting both the global structure and the local semantics for entity representation, the proposed model - SSP can effectively solve the entity alignment problem. Compared with other methods, our method obtains significant performance improvement on almost all

datasets. We believe that is because the structure and semantics-preserving network can effectively leverage global structure and local semantics information of KGs, both of them benefit entity alignment.

• Our method can effectively leverage the global structure and local semantics for entity representation. Compared with the naive joint method that simply concatenates the GCN-based and Translation-based entity embeddings (see SSP(Concate) in Table 2), our method outperforms it by a large performance margin. This verifies the reasonableness and effectiveness of our joint structure and semantics preserving framework.
• Our joint structure and semantics preserving network can effectively make use of the information contained in the KG triples, thus achieving robust performance on either small or large-scale EA datasets. Given no additional information, our model even significantly outperforms TransEdge‡ [Zequn et al., 2019], except for MR on the DBPFR-EN dataset and Hits@1 on the DBPWD dataset. Note that, TransEdge‡ employs a bootstrapping strategy to iteratively select likely-aligned entity pairs to enlarge the training set, while our model - SSP follows a completely end-to-end paradigm and requires no data augmentation.

5.3 Detailed Analyses

To better understand how and why our method works, we conduct a series of detailed analyses.

Effect of Highway Gates. To analyze the effectiveness of highway gates in EA. We remove the highway gates from the model and use exactly the original output of each GCN layer as structure-preserved entity embeddings. SSP(-HW) from Table 1 and Table 2 denotes the ablated model. From the results, we can see that removing the highway gates results in a large performance drops on all datasets. This verifies the effectiveness of highway gates in EA. We believe that highway networks can make use of gating units to regulate the flow of information through a network and reduce noise propagation during updating node features.

We also find that the performance drop on DWY100K dataset is not as large as that of the DBP15K dataset. This is because the DBP15K dataset is much sparser, thus removing the highway gates would add to the difficulty of disambiguating entities with similar embeddings.

Effect of Relation Contextualization. Relation contextualization is an important component in our local semanticsbased refining network. To explore the effectiveness of contextualized relation learning on entity alignment, we replace it with a standard translational method, where the relation representation only depends on its type. SSP(-RC) from Table 1 and Table 2 denotes this ablated model. From the results, we can see that the model performance drops significantly, which verifies the effectiveness of contextualized relation learning. These results confirm that distinctly representing relations in different contexts can help modeling fine-grained relation semantics in KG, which benefits entity alignment.

From the above ablation studies, we can also find that removing the highway gates from SSP leads to much larger performance decline compared to SSP(-RC), this phenomenon verifies the usefulness of highway gates in regulating information flow and reducing noise propagation in GCN layers.

5.4 Discussion

Impact of Number of Alignment Seeds. To explore the impact of the number of alignment seeds (training data) on our model, we compare our model SSP with GCN [Wang et al., 2018], MMR [Shi and Xiao, 2019] and TransEdge [Zequn et al., 2019] by varying the proportion of pre-aligned entity pairs from 20% to 50% with a step of 10% and regard the rest of the alignment seeds as the testing set. As depicted in Figure 3, the performances of all models increase consistently on all datasets as the proportion of alignment seeds rises. It is clear that our model consistently outperforms its comparative counterparts by a significant margin, which verifies the robustness of our model. Notably, given 20% of alignment seeds as training data, our model achieves even comparable performance with TransEge when the latter is trained with 40% of alignment seeds. This verifies the robustness of SSP under scenarios where training data is scarce.

Impact of Entity Sparsity. In real-worldKGs, the node degree (number of adjacent entities) usually follows a long-tail distribution, which means a large proportion of entities have a moderate degree and the proportion of entities with a very high or low degree is relatively small. This practical situation can have a big critical impact on EA. For sparse nodes (entities) with little structure information, it is also very hard for an embedding method to learn high-quality entity embeddings, thus would deteriorate the EA performance.

To explore the model performance on different levels of node (entity) degree, we conduct experiments on DBP15kZH-EN dataset. Three representative models (SSP, SSP(-HW) and TransEdge) are selected. Specifically, we first count the degree (number of adjacent entities) of all entities in the knowledge graph. Then, we evaluate all models on the testing set and subsequently classify entities to be aligned in the testing set into three groups (with node degree in {Low, Medium, High} respectively) in ascending order according to their node degree. Finally, we count the correctly aligned entities in these three groups and calculate the respective alignment accuracy (Hits@1). Figure 4 shows the results of the above experiments. It can be seen that, under each setting, the accuracy consistently increases as the degree rises (from low degree to a high degree) in these groups. This confirms the hypothesis that densely connected (high degree) entities in the KG contain rich structure information which benefits entity alignment, while sparse entities (low degree) lack enough structure information to learn expressive embeddings, thus resulting in inferior performance.

We also find in Figure 4 that, the models exhibit much larger performance decline in the Low degree group than in High degree group when the highway gates are removed from SSP. For example, in Low and Medium degree groups, the accuracy decline are 27.7% and 24.6% respectively when it changes from SSP to SSP(-HW), while that for the High degree group is only 15.7%. This further reveals that the highway gates can help make the best of structure information of sparse entities and further boost EA performance.

6 Conclusions

In this paper, we propose a Structure and SemanticsPreserved network for entity alignment that can learn robust and accurate entity representations by leveraging the global KG structure and local semantics. Experimental results show that, our model obtains substantial performance gains on 5 standard benchmarks, and achieves new SOTA performance.

Acknowledgments

This work is supported by National Key R&D Program of China under Grant 2018YFB1005100, the National Natural Science Foundation of China under Grants no. U1936207 and 61772505, and Beijing Academy of Artificial Intelligence (BAAI2019QN0502).