Relation-Aware Entity Alignment for Heterogeneous Knowledge Graphs

1 Introduction

Knowledge graphs (KGs) are the building blocks for various NLP applications like question-answering [Zhang et al., 2018], text classification [Wang et al., 2016], recommendation systems [Zhang et al., 2016], etc. Knowledge in KGs is usually organized into triples of 〈head entity, relation, tail entity〉. There are considerable works on knowledge representation learning to construct distributed representations for both entities and relations. Exemplary works are the so called trans-family methods like TransE [Bordes et al., 2013], TransH [Wang et al., 2014], and PTransE [Lin et al., 2015], which interpret a relation as the translation operating on the embeddings of its head entity and tail entity.

However, KGs are usually incomplete, and different KGs are often complementary to each other. This makes a compelling case to design a technique that can integrate heterogeneous knowledge among different KGs. An effective way for doing this is Entity Alignment. There have been existing efforts devoted to embed different KGs towards entity alignment. Most of them, like JE [Hao et al., 2016], MTransE [Chen et al., 2017], JAPE [Sun et al., 2017], IPTransE [Zhu et al., 2017] and BootEA [Sun et al., 2018], rely on trans-family models to learn entity representations according to a set of prior alignments. The most recent work [Wang et al., 2018], takes a different approach by utilizing the Graph Convolutional Networks (GCNs) [Kipf and Welling, 2017] to jointly represent multiple KG entities, showing a new, promising direction for entity alignment.

∗Corresponding author.

Compared with conventional feature based methods [Sarasua et al., 2012; Mahdisoltani et al., 2013], embedding-based methods have the advantage of requiring less human involvement in feature construction and can be scaled to large KGs. However, there are still several hurdles that prevent wider adoption of embedding-based approaches. First, as mentioned above, most existing methods use trans-family models as the backbone to embed KGs, which are constrained by the assumption head + relation ≈ tail. This strong assumption makes it inefficient for the model to capture more complex relation information in multi-relational graphs.

As a motivation example, Figure 1 shows a real-world example from the DBP15KZH-EN [Sun et al., 2017] dataset. Prior study [Li et al., 2018b] shows that trans-family methods cannot capture the triangular structures depicted in the diagram. For instance, for the structure of Figure 1(a), TransE requires the three formulas v1 + ra ≈ v2, v2 + ra ≈ v3 and v1+ra ≈ v3 to hold at the same time. However, to satisfy the former two equations, we would have v1 + 2ra ≈ v3, which is contradictory to the third equation v1 + ra ≈ v3. Accordingly, the alignment performance will inevitably be compromised if the KG representations are learned with the transfamily, since more complex structures such as triangular ones frequently appear in multi-relational graphs.

The GCN-based model [Wang et al., 2018] represents a leap forward for embedding-based entity alignment. However, this approach is also unable to properly model relation information. Since the vanilla GCN operates on the undirected and unlabeled graphs, a GCN-based model would ignore the useful relation information of KGs. Although the Relational Graph Convolutional Networks (R-GCNs) [Schlichtkrull et al., 2018] could be used to model multirelational graphs, an R-GCN simply employs one weight matrix for each relation and would require an excessive set of parameters for real-world KGs that often contain thousands of relations. This drawback makes it difficult to learn an effective R-GCN model. Dual-Primal Graph CNN (DPGCNN) [Monti et al., 2018] offers a new solution for the problem. DPGCNN alternates convolution operations on the graph and its dual graph, whose vertices correspond to the edges of the original graph, and iteratively applies a graph attention mechanism to enhance primal edge representations using its dual graph. Compared with GCNs and R-GCNs, the DPGCNN can better explore complex edge structures and produce better KG representations.

Inspired by the DPGCNN, in this paper, we propose a novel Relation-aware Dual-Graph Convolutional Network (RDGCN) to tackle the challenge of proper capturing and integration for relation information. While the DPGCNN serves a good starting point, applying it to learn KG representations is not trivial. Doing so requires us to find a way to better approximate relation representations and characterize the relationship between different KG relations. We address this by extending the DPGCNN to develop a weighted model, and explore the head/tail representations initialized with entity names as a proxy to capture relation information without excessive model parameters that are often hard to train.

As a departure from GCNs and R-GCNs, our RDGCN allows multiple rounds of interactions between the primal entity graph and its dual relation graph, enabling the model to effectively incorporate more complex relation information into entity representations. To further integrate neighboring structural information, we also extend GCNs with highway gates.

We evaluate our RDGCN on three real-world datasets. Experimental results show that RDGCN can effectively address the challenges mentioned above and significantly outperforms 6 recently proposed approaches on all datasets. The key contribution of this work is a novel DPGCNN-based model for learning robust KG representations. Our work is the first to extend DPGCNN for entity alignment, which yields significantly better performance over the state-of-theart alternatives.

2 RelatedWork

2.1 Graph Convolutional Networks

Recently, there has been an increasing interest in extending neural networks to deal with graphs. There have been many encouraging works which are often categorized as spectral approaches [Bruna et al., 2014; Defferrard et al., 2016; Kipf and Welling, 2017] and spatial approaches [Atwood and Towsley, 2016; Hamilton et al., 2017; Veliˇckovi´c et al., 2018]. The GCNs [Kipf and Welling, 2017] have recently emerged as a powerful deep learning-based approach for many NLP tasks like semi-supervised node classification [Kipf and Welling, 2017], semantic role labeling [Marcheggiani and Titov, 2017] and neural machine translation [Bastings et al., 2017]. Furthermore, as an extension of GCNs, the R-GCNs [Schlichtkrull et al., 2018] have recently been proposed to model relational data and have been successfully exploited in link prediction and entity classification. Recently, the graph attention networks (GATs) [Veliˇckovi´c et al., 2018] have been proposed and achieved state-of-the-art performance. The DPGCNN [Monti et al., 2018] discussed in Section 1 generalizes GAT model and achieves better performance on vertex classification, link prediction, and graphguided matrix completion tasks.

Inspired by the capability of DPGCNN on determining neighborhood-aware edge features, we propose the first relation-aware multi-graph learning framework for entity alignment.

2.2 Entity Alignment

Previous approaches of entity alignment usually require intensive expert participation [Sarasua et al., 2012] to design model features [Mahdisoltani et al., 2013] or an external source contributed by other users [Wang et al., 2017]. Recently, embedding-based methods [Hao et al., 2016; Chen et al., 2017; Sun et al., 2017; Zhu et al., 2017; Sun et al., 2018; Wang et al., 2018] have been proposed to address this issue. In addition, NTAM [Li et al., 2018a] is a non-translational approach that utilizes a probabilistic model for the alignment task. KDCoE [Chen et al., 2018] is a semi-supervised learning approach for co-training multilingual KG embeddings and the embeddings of entity descriptions.

As a departure from prior work, our approach directly models the relation information by constructing the dual relation graph. As we will show later in the paper, doing so improves the learned entity embeddings which in turn lead to more accurate alignment.

3 ProblemFormulation

Formally, a KG is represented as G = (E,R, T), where E,R, T are the sets of entities, relations and triples, respectively. Let G1 = (E1, R1, T1) and G2 = (E2, R2, T2) be two heterogeneous KGs to be aligned. That is, an entity in G1 may have its counterpart in G2 in a different language or in different surface names. As a starting point, we can collect a small number of equivalent entity pairs between G1 and G2 as the alignment seeds L = {(ei1 , ei2 )|ei1 ∈ E1, ei2 ∈ E2}. We define the entity alignment task as automatically finding more equivalent entities using the alignment seeds. Those known aligned entity pairs can be used as training data.

4 Our Approach: RDGCN

In order to better incorporate relation information to the entity representations, given the input KG (i.e., the primal graph), we first construct its dual relation graph whose vertices denote the relations in the original primal graph, and then, we utilize a graph attention mechanism to encourage interactions between the dual relation graph and the primal graph. The resulting vertex representations in primal graph are then fed to GCN [Kipf and Welling, 2017] layers with highway gates to capture the neighboring structural information. The final entity representations will be used to determine whether two entities should be aligned. Figure 2 provides an overview architecture of our model.

4.1 Constructing the Dual Relation Graph

Without loss of generality, we put G1 and G2 together as the primal graph G e = (V e , E e ), where the vertex set V e = E1 ∪ E2 is the union of all vertices in G1 and G2, and the edge set E e = T1 ∪ T2 is the union of all edges/triples in G1 and G2. Note that we do not connect the alignment seeds in G e , thus G1 and G2 are disconnected in G e .

Given the primal graph G e , its dual relation graph G r = (V r , E r ) is constructed as follows: 1) for each type of relation r in G e , there will be a vertex vr in V r , thus V r = R1∪R2; 2) if two relations, ri and rj, share the same head or tail entities in G e , then we create an edge urij in G r connecting vr i and vr j .

Different from the original design of dual graph, here we expect the dual relation graph to be more expressive about the relationship between different vr s in G e . We thus weight each edge urij in G r with a weight wr ij according to how likely the two relations vr i and vr j share similar heads or tails in G e , computed as:

where Hi and Ti are the sets of head and tail entities for relation ri in G e respectively. Here, the overhead for constructing the dual graph is proportional to the number of relation types in the primal graph. In our cases, it takes less than two minutes to construct the graphs for each evaluation dataset.

4.2 Interactions between Dual and Primal Graphs

Our goal of introducing dual relation graph is to better incorporate relation information into the primal graph representations. To this end, we propose to apply a graph attention mechanism (GAT) to obtain vertex representations for the dual relation graph and the primal graph iteratively, where the attention mechanism helps to prompt interactions between the two graphs. Each dual-primal interaction contains two layers, the dual attention layer and the primal attention layer. Note that we can stack multiple interactions for mutual improvement on both graphs.

Dual Attention Layer

Let Xr ∈ Rm×2d denote the input dual vertex representation matrix, where each row corresponds to a vertex in the dual relation graph G r . Different from the vanilla GAT [Veliˇckovi´c et al., 2018], we compute the dual attention scores using the primal vertex features ˆXe (computed by Eq. 8) produced by the primal attention layer from previous interaction module:

where ˜xri denotes the d′ -dimensional output representation at dual vertex vr i (corresponding to relation ri ∈ G e ); xrj denotes the dual representation of vertex vr j ; N r i is the set of neighbor indices of vr i ; αr ij is the dual attention score; ar is a fully connected layer mapping the 2d′ -dimensional input into a scalar; σr is the activation function, ReLU; η is the Leaky ReLU; ‖ is the concatenation operation; ci is the relation representation for relation ri in G e obtained from the previous primal attention layer.

Note that within our graph embedding based framework, we are not able to provide relation representations directly, due to limited training data. We thus approximate the relation representation for ri by concatenating its averaged head and tail entity representations in G e as:

where ˆxek and ˆxel are the output representations of the k-th head entity and l-th tail entity of relation ri from the previous primal attention layer.

A special case is when the current dual attention layer is the first layer of our model, we do not have xrj in Eq. 3 produced by the previous dual attention layer, therefore, use an initial dual vertex representation produced by Eq. 5 with the initial primal vertex representations Xe init . Similarly, ci will be obtained with the initial primal Xe init as well.

Primal Attention Layer

In this layer, when applying GAT on the primal graph, we can compute the primal attention scores using the dual vertex representations in G r , which actually correspond to the relations in the primal graph G e . In this way, we are able to influence the primal vertex embeddings using the relation representations produced by the dual attention layer.

Specifically, we use Xe ∈ Rn×d to denote the input primal vertex representation matrix. For an entity eq in primal graph G e , its representation ˜xeq can be computed by:

where ˜xrqt denotes the dual representation for rqt (the relation between entity eq and et) obtained from G r ; αe qt is the primal attention score; N e q is the set of neighbor indices of entity eq in G e ; ae is a fully connected layer mapping the d′ -dimensional input into a scalar and σe is the primal layer activation function.

In our model, the initial representation matrix for the primal vertices, Xe init , can be initialized using entity names, which provide important evidence for entity alignment. We therefore preserve the evidence explicitly by mixing the initial representations with the output of primal attention layer:

where ˆxeq denotes the final output representation of the interaction module for entity eq in G e ; βs is a weighting parameter for the s-th primal attention layer.

4.3 Incorporating Structural Information

After multiple rounds of interaction between the dual relation graph and the primal graph, we are able to collect relationaware entity representations from the primal graph. Next, we apply two-layer GCNs [Kipf and Welling, 2017] with highway gates to the resulting primal graph to further incorporating evidence from their neighboring structures.

In each GCN layer l with entity representations X(l) as input, the output representations X(l+1) can be computed as:

where ˜ A = A+I is the adjacency matrix of the primal graph G e with added self-connections and I is an identity matrix; ˜Djj = ∑k ˜ Ajk and W (l) ∈ Rd(l)×d(l+1) is a layer-specific trainable weight matrix; ξ is the activation function ReLU. We treat G e as an undirected graph when constructing A, in order to allow the information to flow in both directions.

In addition, to control the noise accumulated across layers and preserve useful relation information learned from interactions, we introduce layer-wise gates between GCN layers, which is similar in spirit to the highway networks [Srivastava et al., 2015]:

where X(l) is the input to layer l+1; σ is a sigmoid function; · is element-wise multiplication; W (l) T and b(l) T are the weight matrix and bias vector for the transform gate T(X(l) ).

Alignment. With the final entity representations ¯X collected from the output of GCN layers, entity alignment can be performed by simply measuring the distance between two entities. Specifically, the distance, d(e1, e2), between two entities, e1 fromG1 and e2 fromG2 can be calculated as:

4.4 Training

For training, we expect the distance between aligned entity pairs to be as close as possible, and the distance between negative entity pairs to be as far as possible. We thus utilize a margin-based scoring function as the training objective:

where γ > 0 is a margin hyper-parameter; L is our alignment seeds and L′ is the set of negative instances.

Rather than random sampling, we look for challenging negative samples to train our model. Given a positive aligned pair (p, q), we choose the K-nearest entities of p (or q) according to Eq. 12 in the embedding space to replace q (or p) as the negative instances.

5 Experimental Setup

Datasets. We evaluate our approach on three large-scale cross-lingual datasets from DBP15K [Sun et al., 2017]. These datasets are built upon Chinese, English, Japanese and French versions of DBpedia. Each dataset contains data from two KGs in different languages and provides 15K pre-aligned entity pairs. Table 1 gives the statistics of the datasets. We use the same training/testing split with previous works [Sun et al., 2018], 30% for training and 70% for testing.

Comparison models. We compare our approach against 6 more recent alignment methods that we have mentioned in Section 1: JE [Hao et al., 2016], MTransE [Chen et al., 2017], JAPE [Sun et al., 2017], IPTransE [Zhu et al., 2017], BootEA [Sun et al., 2018] and GCN [Wang et al., 2018], where the BootEA achieves the best performance on DBP15K.

Model variants. To evaluate different components of our model, we provide four implementation variants of RDGCN for ablation studies, including (1) GCN-s: a two-layered GCN with entity name initialization but no highway gates; (2) R-GCN-s: a two-layered R-GCN [Schlichtkrull et al., 2018] with entity name initialization; (3) HGCN-s: a two-layered GCN with entity name initialization and highway gates; (4) RD: an implementation of two dual-primal interaction modules, but without the subsequent GCN layers.

Implementation details. The configuration we used is: β1 = 0.1, β2 = 0.3, and γ = 1.0. The dimensions of hidden representations in dual and primal attention layers are d = 300, d′ = 600, and ˜ d = 300. All dimensions of hidden representations in GCN layers are 300. The learning rate is set to 0.001 and we sample K = 125 negative pairs every 10 epochs. In order to utilize entity names in different KGs for better initialization, we use Google Translate to translate Chinese, Japanese, and French entity names into English, and then use pre-trained English word vectors glove.840B.300d 1 to construct the input entity representations for the primal graph. Note that Google Translate can not guarantee accurate translations for named entities without any context. We manually check 100 English translations for Japanese/Chinese entity names, and find around 20% of English translations as incorrect, posing further challenges for our model.

Metrics. We use Hits@k, a widely used metric [Sun et al., 2018; Wang et al., 2018] in our experiments. A Hits@k score (higher is better) is computed by measuring the proportion of correctly aligned entities ranked in the top k list.

6 Results and Discussion

6.1 Main Results

Table 2 shows the performance of all compared approaches on the evaluation datasets. By using a bootstrapping process to iteratively explore many unlabeled data, BootEA gives the best Hits@10 score on DBP15KZH-EN and clearly outperforms GCN and other translation-based models. It is not surprising that GCN outperforms most translation-based models, i.e., JE, MTransE, JAPE and IPTransE. By performing graph convolution over an entity's neighbors, GCN is able to capture more structural characteristics of knowledge graphs, especially when using more GCN layers, while the translation assumption in translation-based models focuses more on the relationship among heads, tails and relations.

We observe that RDGCN gives the best performance across all metrics and datasets, except for Hits@10 on DBP15KZH-EN where the performance of RDGCN is second to BootEA with a marginally lower score (84.55 vs 84.75). While BootEA serves a strong baseline by showing what can be achieved by exploiting many unlabeled data, our RDGCN has the advantage of requiring less prior alignment data to learn better representations. We believe that a bootstrapping process can further improve the performance of RDGCN, and we leave this for future work. Later in Section 6.3, we show that RDGCN maintains consistent performance and significantly outperforms BootEA when the training dataset size is reduced. The good performance of RDGCN is largely attributed to its capability for learning relation-aware embeddings.

1 http://nlp.stanford.edu/projects/glove/

6.2 Ablation Studies

GCN-s vs. GCN. As shown in Table 2, GCN-s considerably improves GCN in all datasets, resulting in a 17.2% increase on Hits@1 on DBP15KFR-EN . As mentioned in Section 5, the three cross-lingual datasets require us to handle cross-lingual data through rough machine translations, which is likely to introduce lots of noise (∼80% accuracy in our pilot study). But our improvement over GCN shows that although noisy in nature, those rough translations can still provide useful evidence to capture, thus should not be ignored.

GCN-s vs. R-GCN-s. R-GCN is an extension of GCN by explicitly modeling the KG relations, but in our experiments, we observe that GCN-s achieves better performance than RGCN-s on all datasets. As discussed in Section 1, R-GCN usually requires much more training data to learn an effective model due to its large number of parameters, and the available training data in our evaluation might not be sufficient for fully unlocking the potential of R-GCN.

HGCN-s vs. GCN-s. Comparing HGCN-s with GCN-s, we can see that HGCN-s greatly boosts the performance of GCN-s after employing the layer-wise highway gates, e.g., over 30% improvement of Hits@1 on DBP15KFR-EN . This is mainly due to their capability of preventing noisy vertices from driving the KG representations.

HGCN-s vs. RDGCN. When comparing HGCN-s with RDGCN, we can see that the dual-primal interaction modules are crucial to the performance: removing the dual and primal attention layers leads to a drop of 1.1% on Hits@1 and 2.02% on Hits@10 on DBP15KZH-EN . The interaction modules explore the relation characteristics of KGs by introducing the approximate relation information and fully integrate the relation and entity information after multiple interactions between the dual relation graph and the primal graph. The results show that effective modeling and use of relation information is beneficial for entity alignment.

RD vs. RDGCN. Comparing RD with RDGCN, there is a significant drop in performance when removing the GCN layers from our model, e.g., the Hits@1 of RD and RDGCN differ by 8.94% on DBP15KZH-EN. This is not surprising, because the dual-primal graph interactions are designed to integrate KG relation information, while the GCN layers can effectively capture the neighboring structural information of KGs. These two key components are, to some extent, complementary to each other, and should be combined together to learn better relation-aware representations.

6.3 Analysis

Triangular structures. Figure 3(d) shows the performance of RDGCN and BootEA, the state-of-the-art alignment model, on the testing instances with triangular structures. We can see that the alignment accuracy of our RDGCN for entities with triangular structures is significantly higher than that of BootEA in all three datasets, showing that RDGCN can better deal with the complex relation information.

Impact of available prior alignments. We further compare our RDGCN with BootEA by varying the proportion of pre-aligned entities from 10% to 40% with a step of 10%. As expected, the results of both models on all three datasets gradually improve with an increased amount of prior alignment information. According to Figure 3(a-c), our RDGCN consistently outperforms BootEA, and seems to be insensitive to the proportion of prior alignments. When only using 10% of the pre-aligned entity pairs as training data, RDGCN still achieves promising results. For example, RDGCN using 10% of prior alignments achieves 86.35% for Hits@1 on DBP15KFR-EN. This result translates to a 17.79% higher Hits@1 score over BootEA when BootEA uses 40% of prior alignments. These results further confirm the robustness of our model, especially with limited prior alignments.

Case study. Figure 4 shows an example in DBP15KZH-EN and the target entity pair, (vZH and vEN), should not be aligned. The competitive translationbased models, including BootEA, give lower distance scores for (vZH and vEN), suggesting that these two entities should be aligned. This is because those models fail to address the specific relation information associated with the three aligned neighboring entities. For this example, both v1 and v5 indicate the person Chiang Ching-kuo, but v1 has the relation parents with vZH, while v2 has the relation children with vEN. Utilizing such information, a better alignment model should produce a larger distance score for the two entities despite they have similar neighbors. By carefully considering the relation information during the dual-primal interactions, our RDGCN gives a larger distance score, leading to the correct alignment result.

7 Conclusions

This paper presents a novel Relation-aware Dual-Graph Convolutional Network for entity alignment over heterogeneous KGs. Our approach is designed to explore complex relation information that commonly exists in multi-relational KGs. By modeling the attentive interactions between the primal graph and dual relation graph, our model is able to incorporate relation information with neighboring structural information through gated GCN layers, and learn better entity representations for alignment. Compared to the state-of-the-art methods, our model uses less training data but achieves the best alignment performance across three real-world datasets.

Acknowledgements

This work is supported in part by the NSFC (Grant No. 61672057, 61672058, 61872294), the National Hi-Tech R&D Program of China (No. 2018YFC0831905), and a UK Royal Society International Collaboration Grant (IE161012). For any correspondence, please contact Yansong Feng.