{'fraction_non_alphanumeric': 0.040781748689861695, 'fraction_numerical': 0.011387367508570077, 'mean_word_length': 4.688032272523532, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Entity Alignment with Reliable Path Reasoning and Relation-Aware Heterogeneous Graph Transformer

Entity Alignment (EA) has attracted widespread attention in both academia and industry, which aims to seek entities with same meanings from different Knowledge Graphs (KGs). There are substantial multi-step relation paths between entities in KGs, indicating the semantic relations of entities. However, existing methods rarely consider path information because not all natural paths facilitate for EA judgment. In this paper, we propose a more effective entity alignment framework, RPR-RHGT, which integrates relation and path structure information, as well as the heterogeneous information in KGs. Impressively, an initial reliable path reasoning algorithm is developed to generate the paths favorable for EA task from the relation structures of KGs, which is the first algorithm in the literature to successfully use unrestricted path information. In addition, to efficiently capture heterogeneous features in entity neighborhoods, a relation-aware heterogeneous graph transformer is designed to model the relation and path structures of KGs. Extensive experiments on three well-known datasets show RPR-RHGT significantly outperforms 11 state-of-the-art methods, exceeding the best performing baseline up to 8.62% on Hits@1. We also show its better performance than the baselines on different ratios of training set, and harder datasets.


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 * Corresponding Author methods for EA tasks, while translation-based methods are designed for link prediction.
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 , text descriptions , and multi-modal information . 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.

Related Work
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 Zhang et al., 2019b;Trisedya et al., 2019], entity descriptions , 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 . 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 . 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  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  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.

Problem Definition
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 (e 1 h , e 2 k ) is an aligned entity, where superscripts denote different KGs. There is a path relation (r 1 f , r 1 g ) near e 1 h , because the following relation exists: t , but there may not be a similar path near e 2 k . 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 = {p 1 , ..., p i , ..., p N } represents reliable path set, where each p i = (r f , r g ) 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 (KG with Reliable Path Set). We define KG as G = (E, R, T rel , P, T path ), where E is entity set, R is relation set, T rel ⊆ E ×R×E is relation triple set, P is reliable path set, and T path = { e h , p k , e t |p k = (r f , r g ) ∈ P, e h , r f , e a ∈ T rel , e a , r g , e t ∈ T rel } is path triple set.
j } 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, E 1 represents the embedding matrix of entities in G 1 , and e 1 i represents the i-th row of E 1 . 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, E n , and use them as the input of our framework.

Overview Framework of RPR-RHGT
In this section, we introduce our proposed framework RPR-RHGT, 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.

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 (e 1 a , e 2 a ) ∈ L, the similarity matrix S denotes the similarities between path neighborhoods P N (e 1 a ) and P N (e 2 a ), where P N (·) 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 e 1 2 match with e 2 n−1 simultaneously. Therefore, the neighbor matching requires some one-to-one constraints: 1) the similarity of matching neighbor must reach a certain threshold: M N (S) = {e 2 s max k |s max k > τ sim }; 2) sort the similarity values that satisfy the threshold from high to low, and then perform one-to-one matching: M atch 1:1 (M N (S)) = [(e 1 1 , e 2 i ), (e 1 2 , e 2 j ), ...]. So as a result, e 1 1 is chosen to match e 2 n−1 , because 0.9 > 0.7. Obviously, only some neighbors of e 1 a may end up finding matching neighbors. Secondly, for each (e 1 i , e 2 j ) ∈ M atch 1:1 (M N (S)), we can deduce the path matching pair (p 1 k , p 2 t ) according to the following reasoning relationship, as shown in Figure 2 where ↔ indicates the matching relationship; (e 1 a , p 1 k , e 1 i ) and (e 2 a , p 2 t , e 2 j ) are the path triples. The last step is to count the matching number of each matching path, counter(p 1 k ↔ p 2 t ), and select those paths with high numbers of matches to form reliable path set P : Algorithm 1 Procedure of RPR Algorithm. Input: (1) G = (E, R, T rel ); (2) pre-aligned entities L; (3) entity name embeddings E n . Output: reliable path set P , path triple set T path .
1: Set P all ← ∅; 2: for (e 1 a , e 2 a ) ∈ L do 3: Compute matching neighbors of path structures M atch 1:1 (M N (S)) between P N (e 1 a ) and P N (e 2 a );

Relation-Aware Heterogeneous Graph
Transformer (RHGT) 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 , 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) = E n . 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 H r and associated tail entities T r as: where |·| indicates the size of collection; b h , b t are the attention vectors; denotes concatenation and σ is ReLU function. (b) Heterogeneous Attention. Inspired by , we map the entity h into a key vector K i (h) and its neighborhood entity t into a query vector Q i (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 R l (r). R l (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, R l (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 K i (h) = K Linear i (e (l−1) h ); Q i (t) = Q Linear i (e (l−1) t ); RN (h) denotes the neighborhood of entity h; a ∈ R d/hn×1 is the attention parameter; h n is the number of attention heads and d/h n 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: HM SG Head i (h, r, t), To get the i-th head message HM SG Head i (h, r, t), we first apply a linear projection V Linear i 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 h n 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ẽ (l) h of h can be obtained simply by averaging the corresponding messages from neighborhood entities with the attention coefficients as weights: HAttention(h,r,t)·HMessage(h,r,t), (7) 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 E rel and path-based embeddings E path based on entire relation structure T rel and path structure T path respectively, and use them for end-to-end EA tasks.

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 E rel and E path : where f = {rel, path}; L 1 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.

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.

Experiment Settings
Datasets. Three experimental datasets contain crosslingual datasets and mono-lingual dataset: WK31-15K [Sun   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.   For all datasets, we use the same weight hyper-parameters: τ sim = 0.5, τ path = 20, h n = 4, γ 1 = γ 2 = 10, θ = 0.3.

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 RPR-RHGT. We believe that ZH-EN(DBP) has more mismatched paths as one of the reasons. As shown in Table 1, ZH-EN(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. 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, RPR-RHGT 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. 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., Regu-  lar(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.

Further Analysis
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.

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.