Towards Entity Alignment in the Open World:
An Unsupervised Approach

Remark.    The goal of this step is to exploit available side information to generate useful features for alignment. Other types of side information, e.g., attributes and entity descriptions, can also be leveraged. Besides, more advanced textual encoders, such as misspelling oblivious word embeddings [39] and convolutional embedding for edit distance [40], can be utilized. We will investigate them in the future.

Structural information.    As mentioned above, we forward the textual distance matrix $\mathbf{M^{t}}$ generated by using the side information to the unmatchable entity prediction module to produce the preliminary alignment results, which are considered as pseudo-labeled data for learning unified KG embeddings. Concretely, following [25], we adopt GCN ¹¹1More advanced structural learning models, such as recurrent skipping networks [20], could also be used here. We will explore these alternative options in the future. to capture the neighboring information of entities. We leave out the implementation details since this is not the focus of this paper, which can be found in [25].

The progressive learning algorithm.    The amount of training data has an impact on the quality of the unified KG embeddings, which in turn affects the alignment performance [10, 41]. As thus, we devise an algorithm (Algorithm 2) to progressively augment the pseudo training data, so as to improve the quality of KG embeddings and enhance the alignment performance. The algorithm starts with learning unified structural embeddings and generating the fused distance matrix $\mathbf{M}$ by using the preliminary pseudo-labeled data $S_{0}$ (line 1). Then, the fused distance matrix is used to produce the new alignment results $\Delta S$ using TBNNS (line 2). These newly generated entity pairs $\Delta S$ are added to the alignment results (which are considered as pseudo-labeled data for the next round), and the entities in the alignment results $S$ are removed from the entity sets (line 3-6). In order to progressively improve the quality of KG embeddings and detect more alignment results, we perform the aforementioned process recursively until the number of newly generated entity pairs is below a given threshold $\gamma$ (line 7-13).

Dynamic threshold adjustment.    It can be observed from Algorithm 2 that, the matches generated by the unmatchable entity prediction module are not only part of the eventual alignment results, but also the pseudo training data for learning subsequent structural embeddings. Therefore, to enhance the overall alignment performance, the alignment results generated in each round should, ideally, have both large quantity and high quality. Unfortunately, these two goals cannot be achieved at the same time. This is because, as stated in Section 3.2, a larger threshold in TBNNS can generate more alignment results (large quantity), whereas some of them might be erroneous (low quality). These wrongly aligned entity pairs can cause the error propagation problem and result in more erroneous matches in the following rounds. In contrast, a smaller threshold leads to fewer alignment results (small quantity), while almost all of them are correct (high quality).

Remark.    As mentioned in the related work, there are some existing EA approaches that exploit the iterative learning (bootstrapping) strategy to improve EA performance. Particularly, BootEA calculates for each source entity the alignment likelihood to every target entity, and includes those with likelihood above a given threshold in a maximum likelihood matching process under the 1-to-1 mapping constraint, producing a solution containing confident EA pairs [22]. This strategy is also adopted by [15, 23]. Zhu et al. use a threshold to select the entity pairs with very close distances as the pseudo-labeled data [21]. DAT employs a bi-directional margin-based constraint to select the confident EA pairs as labels [24]. Our progressive learning strategy differs from these existing solutions in three aspects: (1) we exclude the entities in the confident EA pairs from the test sets; and (2) we use the dynamic threshold adjustment strategy to control the pace of learning process; and (3) our strategy can deal with unmatchable entities. The superiority of our strategy is validated in Section 4.3.

Datasets.    Following existing works, we adopt the DBP15K dataset [10] for evaluation. This dataset consists of three multilingual KG pairs extracted from DBpedia. Each KG pair contains 15 thousand inter-language links as gold standards. The statistics can be found in Table 1. We note that state-of-the-art studies merely consider the labeled entities and divide them into training and testing sets. Nevertheless, as can be observed from Table 1, there exist unlabeled entities, e.g., 4,388 and 4,572 entities in the Chinese and English KG of $\texttt{DBP15K}_{\texttt{ZH-EN}}$, respectively. In this connection, we adapt the dataset by including the unmatchable entities. Specifically, for each KG pair, we keep 30% of the labeled entity pairs as the training set (for training the supervised or semi-supervised methods). Then, to construct the test set, we include the rest of the entities in the first KG and the rest of the labeled entities in the second KG, so that the unlabeled entities in the first KG become unmatchable. The statistics of the test sets can be found in the Test set column in Table 1.

Parameter settings.    For the side information module, we utilize the fastText embeddings [42] as word embeddings. To deal with cross-lingual KG pairs, following [32], we use Google translate to translate the entity names from one language to another, i.e., translating Chinese, Japanese and French to English. $\alpha$ is set to 0.5. For the structural information learning, we set $\beta$ to 0.5. Noteworthily, since there are no training set or validation set for parameter tuning, we set $\alpha$ and $\beta$ to the default value (0.5). We will further verify that the hyper-parameters do not have a large influence on the final results in Section 4.4. For progressive learning, we set the initial threshold $\theta_{0}$ to 0.05, the incremental parameter $\eta$ to 0.1, the termination threshold $\gamma$ to 30. Note that if the threshold $\theta$ is over 0.45, we reset it to 0.45. These hyper-parameters are default values since there is no extra validation set for hyper-parameter tuning.

Evaluation metrics.    We use precision (P), recall (R) and F1 score as evaluation metrics. The precision is computed as the number of correct matches divided by the number of matches found by a method. The recall is computed as the number of correct matches found by a method divided by the number of gold matches. The F1 score is the harmonic mean between precision and recall.

Competitors.    We select the most performant state-of-the-art solutions for comparison. Within the group that solely utilizes structural information, we compare with BootEA [22], TransEdge [15], MRAEA [41] and SSP [43]. Among the methods incorporating other sources of information, we compare with GCN-Align [25], HMAN [16], HGCN [11], RE-GCN [44], DAT [24] and RREA [45]. We also include the unsupervised approaches, i.e., IMUSE [36] and PARIS [37]. To make a fair comparison, we only use entity name labels as the side information.

The threshold $\theta$ in TBNNS.    We discuss the setting of $\theta$ to reveal the trade-off between the risk and gain from generating the alignment results in the progressive learning. Identifying a match leads to the integration of additional structural information, which benefits the subsequent learning. However, for the same reason, the identification of a false positive, i.e., an incorrect match, potentially leads to mistakenly modifying the connections between KGs, with the risk of amplifying the error in successive rounds. As shown in Figure 3, a smaller $\theta$ (e.g., 0.05) brings low risk and low gain; that is, it merely generates a small number of matches, among which almost all are correct. In contrast, a higher $\theta$ (e.g., 0.45) increases the risk, and brings relatively higher gain; that is, it results in much more aligned entity pairs, while a certain portion of them are erroneous. Additionally, using a higher threshold leads to increasingly more alignment results, while for a lower threshold, the progressive learning process barely increases the number of matches. This is in consistency with our theoretical analysis in Section 3.2.

Unmatchable entity prediction.    Zhao et al. [19] propose an intuitive strategy (U-TH) to predict the unmatchable entities. They set an NIL threshold, and if the distance value between a source entity and its closest target entity is above this threshold, they consider the source entity to be unmatchable. We compare our unmatchable entity prediction strategy with it in terms of the percentage of unmatchable entities that are included in the final alignment results and the F1 score. On $\texttt{DBP15K}_{\texttt{ZH-EN}}$, replacing our unmatchable entity prediction strategy with U-TH attains the F1 score at 0.837, which is 8.4% lower than that of UEA. Besides, in the alignment results generated by using U-TH, 18.9% are unmatchable entities, while this figure for UEA is merely 3.9%. This demonstrates the superiority of our unmatchable entity prediction strategy.

Influence of parameters.    As mentioned in Section 4.1, we set $\alpha$ and $\beta$ to 0.5 since there are no training/validation data. Here, we aim to prove that different values of the parameters do not have a large influence on the final results. More specifically, we keep $\alpha$ at 0.5, and choose $\beta$ from [0.3, 0.4, 0.5, 0.6, 0.7]; then we keep $\beta$ at 0.5, and choose $\alpha$ from [0.3, 0.4, 0.5, 0.6, 0.7]. It can be observed from Figure 4 that, although smaller $\alpha$ and $\beta$ lead to better results, the performance does not change significantly.

Influence of input side information.    We adopt different side information as input to examine the performance of UEA. More specifically, we report the results of UEA-$\mathbf{M^{l}}$, which merely uses the string-level feature of entity names as input, UEA-$\mathbf{M^{n}}$, which only uses the semantic embeddings of entity names as input. We also provide the results of $\mathbf{M^{l}}$ and $\mathbf{M^{n}}$, which use the string-level and semantic information to directly generate alignment results (without progressive learning), respectively.

Pseudo-labeled data.    We further examine the usefulness of the preliminary alignment results generated by the side information, i.e., the pseudo-labeled data. Concretely, we replace the training data in HGCN with these pseudo-labeled data, resulting in HGCN-U, and then compare its alignment results with the original performance. Regarding the F1 score, HGCN-U is 4% lower than HGCN on $\texttt{DBP15K}_{\texttt{ZH-EN}}$, 2.9% lower on $\texttt{DBP15K}_{\texttt{JA-EN}}$, 2.8% lower on $\texttt{DBP15K}_{\texttt{FR-EN}}$. The minor difference validates the effectiveness of the pseudo-labeled data generated by the side information. It also demonstrates that this strategy can be applied to other supervised or semi-supervised frameworks to reduce their reliance on labeled data.