Entity Alignment with Reliable Path Reasoning and Relation-aware Heterogeneous Graph Transformer

1 Introduction

Most Knowledge Graphs (KGs) are often disconnected from each other because they are constructed with different technologies and languages, which poses challenges for merging and integrating different KGs. Entity Alignment (EA) is a task to connect entities with the same meaning in different KGs, which plays a fundamental role in the knowledge fusion of KGs. Recently, EA methods based on the Graph Neural Networks (GNNs) are more favored by researchers than the translation-based methods. GNNs not only exhibit excellent performance in aggregating the neighborhood features of nodes, but also can design corresponding feature acquisition methods for EA tasks, while translation-based methods are designed for link prediction.

∗Corresponding Author

Although current GNNs-based methods have achieved promising results, they still suffer from the following three limitations. First, many methods [Wu et al., 2019; Sun et al., 2020a] treat KGs as homogeneous graphs without considering the heterogeneous features of sides between entities. Actually, the heterogeneous information helps to improve the accuracy and robustness of alignment judgments. Second, some semantic information other than relation structures is considered by many works, such as entity attributes [Liu et al., 2020; Cai et al., 2022], text descriptions [Yang et al., 2019], and multi-modal information [Liu et al., 2021]. However, the more semantic information a method integrates, the more data its application requires, which cannot be satisfied in some scenarios. Third, some other works [Wu et al., 2020; Zhu et al., 2020] only rely on the relation structures, and obtain inter-graph information based on Graph Matching Networks (GMN) [Li et al., 2019] to mine more similar features between aligned entities. Nonetheless, the matching module they introduced for learning inter-graph information runs through the entire training process with high temporal and space complexity.

Therefore, for the first limitation above, we design a Relation-Aware Heterogeneous Graph Transformer (RHGT) to effectively extract the similarity features of aligned entities in their heterogeneous structures. For the latter two limitations above, we develop a Reliable Path Reasoning algorithm (RPR) that can directly extract the path structures favorable for EA tasks from the original relation structures. Existing methods rarely consider the path information of KGs (i.e., the indirect neighborhood of aligned entities), despite their success in modeling of direct relationship facts. It is known that substantial multi-step relational paths exist between entities, indicating their semantic relationships. But not all natural paths facilitate EA judgment, and some even backfire. Although IPTransE [Zhu et al., 2017] considers the reliability of paths, it assumes all relations between KGs are pre-aligned. Essentially, our idea is to make full leverage of the richness of KGs by simultaneously comparing the similarities of relation and path structures of aligned entities. We believe the paths that frequently appear near pre-aligned entities can be regarded as reliable and used to align other entities. The fusion of relation and path structure information complements each other, alleviating the inconsistency between each type information of aligned entities.

After all, we combine above two methods into a entity alignment framework called RPR-RHGT, which not only considers the heterogeneous information of sides in KGs, but also mines the path information within the relation structures of KGs. Extensive experiments on three well-known benchmark datasets show RPR-RHGT not only outperforms 10 state-ofthe-art models significantly, but also has impressive scalability and robustness.

2 RelatedWork

Translation-based Entity Alignment. Such methods are mainly based on TransE [Bordes et al., 2013] and its variants. MTransE [Chen et al., 2017] is the pioneering work, which uses TransE to model the entities and relations and evaluates the transform between two vector spaces based on pre-aligned entities. Other works utilize additional information or external knowledge of KGs, such as attribute structures [Sun et al., 2017; Zhang et al., 2019b; Trisedya et al., 2019], entity descriptions [Chen et al., 2018], entity names [Zhang et al., 2019b], ontology schemata [Xiang et al., 2021], to find more similar features of aligned entities. There are also some works [Sun et al., 2018; Zhu et al., 2017] that try to discover more new aligned entities by iterative strategies.

GNNs-based Entity Alignment. GNNs-based methods mainly utilize Graph Convolutional Networks (GCNs) and Graph Attention Networks (GATs) to aggregate the neighborhood feature of each entity, thereby obtaining the neighborhood similarity between aligned entities. Most of them directly compare the neighborhood similarity between aligned entities in relation structures [Wu et al., 2019]. There are several attemptsto simultaneously consider the similarities in the attribute and relation structures [Liu et al., 2020]. Some other works smartly model both intra-graph and crossgraph information, and learn similarities by building crossgraph attention mechanism using GMN [Wu et al., 2020; Zhu et al., 2020]. Besides, some researchers believe that the heterogeneity of edges in KGs should be considered when aggregate the neighborhood features, because KGs are heterogeneous graphs. They propose or apply some heterogeneous graph embedding methods to learn better representations for entities [Cai et al., 2022]. All aforementioned works only consider the similarity of direct neighborhoods between aligned entities. However, aligned entities have some similarity in their indirect neighborhoods. Hence, we attempt to obtain the similarity between aligned entities in the relation structures and multi-hop path structures of KGs simultaneously in the paper.

Heterogeneous GNNs. Recently, many works have tried to extend GNNs to the modeling of heterogeneous graphs. RGCNs [Schlichtkrull et al., 2018] and RGATs [Busbridge et al., 2019] model heterogeneous graphs by using a weight matrix for each relation. HAN [Wang et al., 2019] proposes a hierarchical attention mechanism to learn the weights of nodes and meta-paths from node-level and semantic-level attention, respectively. HetGNN [Zhang et al., 2019a] adopts different Recurrent Neural Networks (RNNs) for different types of nodes to integrate multi-modal features. Howerer, due to the large number of relations in KGs, the training complexity is high when applying them to model KGs. More recently, HGT [Hu et al., 2020] and RHGT [Mei et al., 2022] try to model the heterogeneity by heterogeneous graph transformers. But they are not designed to capture neighborhood similarity, so it is difficult to directly apply to EA tasks. Therefore, an improved heterogeneous graph transformer is designed to consider the heterogeneity of KGs, thereby obtaining highquality entity embeddings for EA tasks.

3 Proposed Framework

3.1 ProblemDefinition

To increase the neighborhood semantics of entities, we introduce a meta path-based similarity framework for EA. The classic meta-path paradigm is defined as a sequence of relations between objects, so we define the new compound relation between two entities as a relation path in this paper. For example, suppose (e1h , e2k ) is an aligned entity, where superscripts denote different KGs. There is a path relation (r1 f , r1 g ) near e1h , because the following relation exists:

r1 r1

e1h f→ e1i g→ e1t , but there may not be a similar path near e2k . Therefore, not all paths in the neighborhood of entities are reliable for EA learning. In other words, we should only keep partially reliable paths to learn the neighborhood similarity of aligned entities.

Definition 1 (Reliable Path Set). In this paper, we use P = {p1, ..., pi, ..., pN} represents reliable path set, where each pi = (rf , rg) is effective for EA learning. "Reliable path" here refer to path that facilitate EA learning, rather than the meaningful path. We believe the paths that frequently occur in the neighborhoods of pre-aligned entities can be considered reliable. In this paper, we only consider paths based on two-hop relations, and the study of a wider range of path structures will be left to future work.

Definition 2 (KGwith Reliable Path Set). We define KG as G=(E, R, Trel, P, Tpath), where E is entity set, R is relation set, Trel ⊆E×R×E is relation triple set, P is reliable path set, and Tpath ={〈eh, pk, et〉|pk =(rf , rg)∈P, 〈eh, rf , ea〉∈ Trel, 〈ea, rg, et〉∈Trel} is path triple set.

Definition 3 (Entity Alignment). G1 = (E1 ,R1 , T 1 rel , P 1 , T 1 path ) and G2 = (E2 ,R2 , T 2 rel , P 2 , T 2 path ) are two KGs to be aligned. Let L={(e1i , e2j )|e1i ∈E1 , e2j ∈E2 , e1i ≡e2j } be the pre-aligned entity set, where ≡ refers to the same realworld object. Entity Alignment tasks aim to find the remaining aligned entities between two KGs.

Formally, we use bold letter for embedding vector. For example, E1 represents the embedding matrix of entities in G1 , and e1i represents the i-th row of E1 . In addition, the entity name is the most common text used to identify a entity, which can be used to effectively capture the semantic similarity of aligned entities. Therefore, we apply pre-trained word embeddings to generate initial representations of entities, En , and use them as the input of our framework.

3.2 Overview Framework of RPR-RHGT

In this section, we introduce our proposed framework RPRRHGT, a novel robust EA framework based on a reliable path reasoning algorithm and a relation-aware heterogeneous graph transformer. Specifically, RPR-RHGT is mainly composed of three modules, as shown in Figure 1: (1) Reliable Path Reasoning (RPR). A reliable path reasoning algorithm is developed to infer the reliable relation paths and form path structures of two KGs. (2) Relation-Aware Heterogeneous Graph Transformer (RHGT). We design the RHGT to capture the features of specific patterns of relations and paths with fewer parameters, which contain the heterogeneous neighborhood features of aligned entities in relation and path structures. (3) Alignment Learning. This module computes the loss function and similarity matrices of pathbased and relation-based entity embeddings, and evaluates the probabilities of EA.

3.3 Reliable Path Reasoning (RPR)

As discussed in Section 1, not all relation paths are reliable for EA learning. It is known that each KG is constructed according to relatively stable data sources and construction rules. Our key insight is the path with a high number of matches between the neighborhoods of pre-aligned entities (small range) can be regarded as reliable, which can be used to match judgments of other entities (large range). We first establish the path neighborhood matching between each prealigned pair (see Figure 2(a)), derive the matching paths (see Figure 2(b)), finally select those paths with high numbers of matches to form a reliable path set P .

Specifically, for a given pair (e1a , e2a ) ∈ L, the similarity matrix S denotes the similarities between path neighborhoods PN(e1a ) and PN(e2a ), where PN(·) indicates path neighborhood of a entity. Firstly, the entities with maximum similarities in each row of S are selected as the matching neighbors. As shown in Figure 2(a), the matching result of e11 (one neighbor of e1a ) is e2n-1 , because their similarity is the largest in first row. However, there may be multiple neighbors of e1a that match the same neighbor of e2a , such as e11 and e12 match with e2n-1 simultaneously. Therefore, the neighbor matching requires some one-to-one constraints: 1) the similarity of matching neighbor must reach a certain threshold: MN(S) = {e2smax k |smax k > τ sim}; 2) sort the similarity values that satisfy the threshold from high to low, and then perform one-to-one matching: Match1:1(MN(S)) = [(e11 , e2i ), (e12 , e2j ), ...]. So as a result, e11 is chosen to match e2n-1 , because 0.9 > 0.7. Obviously, only some neighbors of e1a may end up finding matching neighbors.

Secondly, for each (e1i , e2j ) ∈ Match1:1(MN(S)), we can deduce the path matching pair (p1k , p2t ) according to the following reasoning relationship, as shown in Figure 2(b):

where ↔ indicates the matching relationship; (e1a , p1k , e1i ) and (e2a , p2t , e2j ) are the path triples.

The last step is to count the matching number of each matching path, counter(p1k ↔ p2t ), and select those paths with high numbers of matches to form reliable path set P :

where τ path is set according to the specific dataset. Algorithm 1 gives the procedure of our RPR algorithm.

Algorithm 1 Procedure of RPR Algorithm.

Input: (1) G = (E,R, Trel); (2) pre-aligned entities L; (3) entity name embeddings En .

Output: reliable path set P, path triple set Tpath.

• 1: Set Pall ← ∅;
• 2: for (e1a , e2a ) ∈ L do
• 3: Compute matching neighbors of path structures Match1:1(MN(S)) between PN(e1a ) and PN(e2a );
• 4: for (e1i , e2j ) ∈ Match1:1(MN(S)) do
• 5: Deduce the path matching pair (p1k , p2t ) using Eq.(1);
• 6: Pall ←Pall ∪ (p1k , p2t );
• 7: end for
• 8: end for
• 9: Generate the reliable path set P using Eq. (2);
• 10: Generate the path triple set Tpath using Definition 2;
• 11: Return P and Tpath;

3.4 Relation-Aware Heterogeneous Graph Transformer (RHGT)

The process of Graph Transformer [Yun et al., 2019] aggregating all neighborhood features of node h can be briefly expressed as:

where Attention is to estimate the importance of each neighborhood node; Message is to extract the feature of each neighborhood node; and Aggregate aggregates the neighborhood message through attention weights.

As shown in Eq.(3), Graph Transformer does not consider the edge features. Inspired by [Hu et al., 2020], we design a relation-aware heterogeneous graph transformer (RHGT), which enables our model to distinguish the heterogeneity features of relations and paths, to better obtain the neighborhood similarity of aligned entities. Let E(l) denote the output of (l)-th layer of RHGT, which is also the input of the (l +1)-th layer. Initially, E(0) = En . When the input of RHGT is the relation triples, the output is relation-based embeddings, and when the input is the path triples, the output is path-based embeddings. As shown in Figure 3, RHGT is mainly composed of four layers.

(a) Relation Embedding. Considering that the head entities and tail entities associated with aligned relations or aligned paths have certain similarities, we generate relation features by aggregating the features of associated entities. Specifically, the embedding of r is approximated by averaging the embeddings of its associated head entities Hr and associated tail entities Tr as:

where | · | indicates the size of collection; bh, bt are the atten-

tion vectors; ‖ denotes concatenation and σ is ReLU function. (b) Heterogeneous Attention. Inspired by [Hu et al., 2020], we map the entity h into a key vector Ki (h) and its neighborhood entity t into a query vector Qi (t). The key difference from other methods is that instead of directly using the dot product of key and query vector as attention, we use the dot product between their concatenated result and Rl (r). Rl (r) comes from the feature aggregation of the associated head and tail entities (see Eq.(4)), so it will not deviate too far from the embeddings of its associated entities. Moreover, Rl (r) denotes heterogeneous features of edges, so neighbors associated with different edges contribute differently to the entity h. Specifically, we compute the multi-head attention for each neighborhood relation (h, r, t), as follows:

where Ki (h) = K Lineari (e(l-1) h ); Qi (t) = Q Lineari (e(l-1) t ); RN(h) denotes the neighborhood of entity h; a ∈ Rd/hn×1 is the attention parameter; hn is the number of attention heads and d/hn is the vector dimension per head. Note that the Softmax process is to make the sum of attention vectors of all neighborhood entities equal to 1.

(c) Heterogeneous Message. Similarly, we hope to incorporate relations into the message passing process to distinguish the differences of different types of edges. For any (h, r, t) ∈ T , its multi-head message is computed as follows:

To get the i-th head message HMSGHeadi(h, r, t), we first apply a linear projection V Lineari to project the features of tail entity t, and then concatenate the features of t and relation r. The final heterogeneous message can be obtained by concatenating all hn message headers.

(d) Heterogeneous Aggregate. The final step is to aggregate heterogeneous multi-head attentions and messages of entities (see Figure 3 (c)), thereby aggregating the information from neighbors with different feature to entity h. The update vector ˜e(l) h of h can be obtained simply by averaging the corresponding messages from neighborhood entities with the attention coefficients as weights:

where ⊕ denotes the overlay operation. To incorporate the name features and the features obtained by the multilayer neural network, the residual connection is used to generate the final updated embeddings as following:

where wβ is trainable weights, A Linear(·),N Linear(·) are linear projections. Finally, we can generate relation-based embeddings Erel and path-based embeddings Epath based on entire relation structure Trel and path structure Tpath respectively, and use them for end-to-end EA tasks.

3.5 Alignment Learning

After obtaining the final entity representations, we use Manhattan distance to measure the similarity of candidate entity pair. A smaller distance means a higher probability of entity alignment. The following function is used to compute the similarity of candidate entity pair based on Erel and Epath:

where f ={rel, path}; L1 indicates the Manhattan distance. To capture various aspects of the entities, previous methods usually concatenate the multi-source embeddings of entities and directly use them for the loss function. However, we argue that the contribution of relation-based and path-based embeddings to EA should be different, since these two structures of a entity may be quite diverse. Therefore, instead of directly using concatenated embeddings, we assign different weights to the loss functions of the two embeddings, thereby distinguishing their different contributions during training. In view of this, the following margin-based ranking loss function is used in model training, the goal of which is to keep the embedding distance of positive pair as small as possible and the embedding distance of negative pair as large as possible:

where [·]+ =max{0, ·}; L′rel and L′path represent the negative pair of relation-based and path-based embeddings, respectively; γ1, γ2 > 0 are the margin hyper-parameters for separating positive and negative pairs, respectively.

4 Experiments

In this section, we evaluate the performance of RPR-RHGT on three widely used benchmark datasets. The code is now available at https://github.com/cwswork/RPR-RHGT.

4.1 Experiment Settings

Datasets. Three experimental datasets contain crosslingual datasets and mono-lingual dataset: WK31-15K [Sun et al., 2020b] is from multi-lingual DBpedia and used to evaluate model performance on sparse and dense datasets, where each subset contains two versions: V1 is sparse set obtained by using IDS algorithm, and V2 is twice as dense as V1. DBP-15K [Sun et al., 2017] is the most used dataset in the literature, and is also from DBpedia. DWY-100K [Sun et al., 2018] contains two mono-lingual KGs, which serve as largescale datasets to better evaluate the scalability of experimental models. Table 1 outlines the statistics of above datasets which also contains the numbers of paths and path triples generated by Algorithm 1, to demonstrate the effect of the RPR module. Due to five-fold cross-validation used on WK31-15K and DBP-15K, the "Path.Paths" and "Path.Triplets" of these two datasets are the average statistic for the five training sets.

Metrics. Hits@k is the proportion of correctly alignment ranked at the top-k candidates; MRR (Mean Meciprocal Rank) is the average of the reciprocal ranks. Higher Hits@k and MRR scores indicate better performance of EA.

Baselines. For WK31-15K and DBP-15K, we compare RPR-RHGT with eight previous state-of-the-art alignment models (mentioned in Section 2): MTransE [Chen et al., 2017], IPTransE [Zhu et al., 2017], JAPE [Sun et al., 2017], BootEA [Sun et al., 2018], AttrE [Trisedya et al., 2019], RDGCN [Wu et al., 2019], NMN [Wu et al., 2020], RAGA [Zhu et al., 2021]. Since only a few models are evaluated on DWY-100K, we compare with the following models: MultiKE [Zhang et al., 2019b], RDGCN [Wu et al., 2019], NMN [Wu et al., 2020], COTSAE [Yang et al., 2020].

Implementation Settings. For WK31-15K and DBP-15K, the proportion of train, validation and test is 2:1:7, the same as [Sun et al., 2020b]. For DWY-100K, we adopt the same train (30%) / test (70%) split as baselines. We use fastText 1 to generate entity name embeddings that are uniformly applied to baseline recurrence, including RDGCN, NMN, RAGA, MultiKE and COTSAE. The embedding dimensions of 15K and 100K datasets are 300 and 200, respectively.

1 https://fasttext.cc/docs/en/crawl-vectors.html

For all datasets, we use the same weight hyper-parameters: τ sim = 0.5, τ path = 20, hn =4, γ1 =γ2 =10, θ = 0.3.

4.2 Main Results

Tables 2 and 3 report all performances on three datasets. The Hits@k is in percentage (%), while number in bold denotes the best results of all models and number in underline denotes the best result of baselines.

Results on WK31-15K. As shown in Table 2, RPR-RHGT achieves the best performance on WK31-15K, exceeding by 4.28%∼8.62% on Hits@1. By reducing the numbers of relations and triples, WK31-15K challenges the ability of EA models to model sparse KGs. RPR-RHGT achieves significant improvements over the baselines on both sparse KGs and dense KGs. Besides, it is noteworthy that the improvements of RPR-RHGT on Hits@1 are much higher than that on Hits@5, indicating that RPR-RHGT can more accurately identify true entity among the top-5 indistinguishable alignment candidates. This experiment shows RPR-RHGT can compensate the neighborhood sparsity problem of some entities to a certain extent.

Results on DBP-15K. From observing Table 2, the Hits@1 of RPR-RHGT on DBP-15K is higher than the best baselines by 4.35%∼0.58%, which indicates that our model performs best on all DBP-15K. It is noteworthy that the performance of RAGA on ZH-EN(DBP) is comparable to that of RPRRHGT. We believe that ZH-EN(DBP) has more mismatched paths as one of the reasons. As shown in Table 1, ZHEN(DBP) has more relations than other datasets, but no more reliable paths obtained by RPR algorithm. Besides, NMN

is one of the best performing baselines and effectively captures the cross-graph information and relation information of KG, while RPR-RHGT still achieves good performance. Although the gap between RPR-RHGT and RAGA is smaller, RPR-RHGT has an advantage on DBP-15K.

Results on DWY-100K. As the largest dataset, DWY-100K raises challenges to the time and space complexity of EA models. As show in Table 3, although RPR-RHGT does not rely on attribute structures, it still outperforms all baselines on DWY-100K. Since DWY-100K is several times larger than other datasets, this experiment demonstrates that RPR-RHGT has good scalability and superiority in larger real-world and monolingual KGs.

4.3 Ablation Experiments

w/o.RPR is the RPR-RHGT without RPR module, the results of which are shown at the bottom of Tables 2 and 3. It can be observed that w/o.RPR performs better than all baseline models on all datasets, except for ZH-EN(DBP), which confirms the effectiveness of RHGT design. Besides, RPRRHGT achieves better performance than w/o.RPR across all metrics and datasets. This experiment confirms the assumption that the relational and path structure information of KGs can mutually reinforce each other.

4.4 Further Analysis

Sensitivity to Ratios of Pre-Aligned Entities. To explore the impact of pre-aligned entities on EA model training, we implement a further evaluation based on different ratios of training set. We take EN-DE(V1) and EN-DE(V2) as examples, and vary the ratio from 5% to 30%, while the validation dataset remains at 10%. RDGCN, NMN and RAGA are chosen as comparison models, all of which use name embeddings and perform best among baselines. As shown in Figure 4, our two models maintain consistent performance, significantly outperforming the baselines on training sets for all scales. This indicates that RPR-RHGT can achieves satisfactory results based on fewer pre-aligned entities.

Analysis on Harder Datasets. For a more objective evaluation of EA models, we take EN-DE(V1) and EN-DE(V2) as examples (called regular datasets), to construct two experimental datasets with relatively low similarities of entity names (called harder datasets). Specifically, we first compute the name embedding similarities of aligned entity pairs and rank them (low to high), then pick the highest-ranked 50% as the harder datasets, which are divided in the same way as above. To compare the effects of name embeddings on the performances of regular and harder datasets, we also compute the alignment accuracy of entity embeddings based only on their name embeddings without training, i.e., Regular(name) and Harder(name). As shown in Figure 5, the performances of all models based on name embeddings drop on harder datasets. However, comparing the performance on regular datasets, the performance of all models on harder dataset shows a more significant improvement over the performance of name embeddings. In particular, RPR-RHGT achieves up to 32.48% and 41.1% improvement over the name embeddings in Hits@1 on two harder datasets. This result demonstrates the robustness of RPR-RHGT, which can still promote effective EA on the datasets with less similar entity names.

Analysis on Training Time and Alignment Time. To evaluate the training and alignment efficiency of RPR-RHGT, we compare the training time and alignment time of the following four models on EN-DE(V1). The results running on a workstation with CPU (EPYC 3975WX +256G RAM) and GPU (RTX A4000 with 16G) are shown in Table 4, which shows large differences between different methods. Although the training time of RPR-RHGT is not optimal, its time complexity is competitive. Overall, our model balances well between effectiveness and efficiency.

5 Conclusions

Traditional GNNs either donot consider the heterogeneous information of KGs, or cannot effectively extract heterogeneous information that is effective for EA tasks. This paper proposes a new EA framework, RPR-RHGT, which focuses on mining reliable path information and heterogeneous information, thereby making full use of KGs' own relation structures to improve alignment accuracy. First, we develop a RPR algorithm, which infers reliable paths from relation structures and only needs to be executed once. This algorithm is the first in the literature to successfully use unrestricted path information. Second, we improve a RHGT model for modeling the heterogeneity of KGs, to better capture the heterogeneous neighborhood similarity of aligned entities. Experimental results show RPR-RHGT not only outperforms state-of-the-art models, but also achieves better performance in multiple ablation studies and analysis experiments. In the future, we will continue to explore better ways to mine the heterogeneous information and path information of KGs for EA tasks.

Acknowledgments

The works described in this paper are supported by The National Natural Science Foundation of China under Grant Nos. 61772210 and U1911201; Guangdong Province Universities Pearl River Scholar Funded Scheme (2018); The Project of Science and Technology in Guangzhou in China under Grant No. 202007040006.