Entity Alignment (EA) aims to identify equivalent entities across diferent knowledge graphs. Existing methods mainly focus on EA for small to medium-sized knowledge graphs and are inefective for large-scale knowledge graphs. This paper proposes a method called ScaleEA (Scalable Entity Alignment Method) for large-scale EA tasks, which can minimize the number of model parameters and training time while ensuring EA accuracy. ScaleEA combines the advantages of pre-trained language models and graph neural network. First, pre-trained language models obtain entity names and property encodings. Then, graph neural network aggregate relation and attribute information of each entity. Finally, candidate entity sets are retrieved and fused separately within each channel. Experiments on DBP1M show that compared with existing models, ScaleEA has significant advantages in both time and alignment accuracy.
Knowledge Graph (KG) storing entities, relations and attributes in graph, has been widely used in
applications for recommendation system [1], natural language processing [2], and question answering
[3]. Current KGs are heterogeneous and cannot be merged together easily. If multiple KGs from diferent
sources can be combined, a more complete and detailed KG will help accomplish applications. Entity
Alignment (EA) is a fundamental and critical step in solving KG heterogeneity problem. Its goal is
to identify entities with the same referential meaning in diferent knowledge graphs. These aligned
entities will be used for subsequent graph fusion. The main process of EA is: (
Existing EA solutions mainly focus on: (
However, many of these methods sufer from significant scalability issues. While models achieve high accuracy in small KGs, they cannot be scaled to fit real-world KGs, which have million entities far more than artificially constructed KGs. The larger KG lead to greater memory consumption, including both entity embedding and model parameters, and higher training costs. The mainstream approach is to divide large KG into smaller ones, while inevitably loses structure and property information.
This article proposes an eficient approach: build a scalable model using property information to assist with alignment, and conduct as little training as possible overall. The specific approach is as follows. First, fine-tune cross-lingual pre-trained BERT model on a small dataset, using entity names of seed alignments as input. Second, directly apply the fine-tuned model to larger KGs, obtaining initial entity embedding from entity name, and obtain relation, attribute, and value embedding from their names. Third, add relation and attribute channels to aggregate information from both neighboring subgraphs. The name, relation, and attribute channels are used individually for target retrieval, and then we fuse candidate entity set to obtain complete candidate sets.
Overall, the innovative points of this article are as follows:
(
(
(
Early EA methods relied on handcrafted features, crowdsourcing, and OWL semantic methods [5, 6, 7, 8]. Due to the reliance on manual rules, they are not suitable for highly heterogeneous linguistic scenarios. With the development of deep learning, today EA methods focus on using graph structure, which further can be divided into two categories, translation-based EA and GNN-based EA. Translation-based EA originated from TransE [9], with other representative studies including MTransE [10], AlignE [11], and SEA [12]. Some of them focus on exploring long-term relational dependencies of entities, such as IPTransE [13], RSN4EA [14], and IMEA [15]. With GNN achieving better results in graph representation, recent research pays more attention to GNN-based EA [16, 17, 18, 19, 19, 20].
In addition, many methods have revealed that KG’s property information can improve the accuracy of EA by supplementing structure information, including names [18, 21, 22, 23, 4, 24, 25], descriptions [4, 24, 26], images [27], and attributes [25, 12, 28]. Since each entity has own name and it does not need to be pre-processed, most methods tend to use name.
Although embedding based EA methods achieved high accuracy in finding potential aligned entities of small-scale datasets, they cannot be well scaled to large-scale KGs. Faced with large-scale KGs, most of them lead to insuficient GPU memory and very long time. Recent research decompose the large-scale EA task into independent subtasks [29, 30, 31, 32], and each subtask includes small subgraphs generated from original KGs. For each subtask, existing EA models can be naturally combined to predict unknown mappings based on seed alignments.
There are four representative graph division alignment methods.
LargeEA [29] first uses METIS to divide KGs into independent subgraphs. After dividing source KG, edge weights of target KG are modified based on seed entities and METIS is used again to partition target KG. LIME [30] uses a bidirectional partition method to preserve KG structure and further increases the coverage of seed mappings in each subtask. While compared with LargeEA, it doubles the partitioning time. DivEA [31] also divides source KG, then it expands mapping target subgraphs by modeling unmatched entities to decrease information loss. LargeGNN [32] merges the seed alignments from two KGs to form a unified KG and then partition it, ensuring all pre-aligned entities are located in the same subgraph blocks. It designs centrality-based subgraph generation and cross subgraph negative sampling algorithms to recall landmark entities. In conclusion, graph division methods solve the memory problem and speed up the EA task, however, it inevitably lowers precision because of incomplete graph context.
The core of the proposed ScaleEA (Scalable Entity Alignment Method) method is to fine-tune pre-trained language model on small data, and calculate the initial vector embedding of entity names, relations, attributes, and values. Then, entity embedding are generated separately for the three respective channels of name, relation, and attribute, and candidate entity sets are retrieved separately within each channel. Finally, candidate sets from three channels are sorted and fused together to obtain the target aligned entities.
A Knowledge Graph (KG) can be represented as = (, , , , ), where is the set of entities, the set of relations between entities, the set of attributes, the set of property values of attributes, and the set of triples in the graph, which can be categorized into relation triples and attribute triples . Relation triples represent the connection between two entities through a directed relation, such as (Beijing, the capital of, China), indicating that Beijing is the capital of China. Attribute triples represent the attributes of an entity, where the property value can be a string or a number, such as (Kobe Bryant, birthDate, "1978-08-23"), indicating that Kobe Bryant’s birth date is August 23rd, 1978.
Given a source KG and a target KG , entity alignment is to find equivalent entity sets between the two KGs, = {(, )| ≡ , ∈ , ∈ }, where represents the aligned entities. During the experiments, we divide the data into training and testing sets, with the training set usually accounting for 30% of the data.
The framework of ScaleEA consists of three modules, including the entity information encoding module, similarity calculation module, and channel ensemble module, as shown in Fig.1.
(
(
(
This part introduces the generation method and specific details of entity property encoding. The overall
structure is based on BERT, which generates corresponding embedding for entities, relations, attributes,
and values based on their text, and fine-tunes BERT according to the aligned seed entities. BERT
has strong understanding ability for semantic information and can be applied to various tasks after
ifne-tuning and EA is regarded as a classification task. Given a set of seed entities , training data is
constructed as,
= {(, ′, − , ′− )| ≡ ′, (, − ) ∈ , (′, ′− ) ∈ }
(
The overall process is shown in Fig.2. A pre-trained cross-lingual BERT is used to input the entity name and obtain the entity embedding from [CLS] vector. The [CLS] vector in the BERT hidden layer represents the semantic information of the entire sentence. In order to reduce the dimension and improve task performance, an additional trainable MLP layer is added to reduce the embedding dimensions from 768 to 300. The final representation of the entity embedding is as follows, For the source entity embedding ˆ, the probability of aligning with an aligned entity ˆ′ is given by: ˆ = (()[]) ˆ (ˆ, ′) =
(ˆ, ˆ′)
(ˆ, ˆ′) + ( − ˆ , ˆ′) + (ˆ, ′ −ˆ )
(
The model is trained on a small dataset and is used to generate embedding for entity property information, which is the basis for subsequent multi-channel information fusion. The training of the model can be end-to-end, or the parameters can be trained first and then frozen. Due to the large-scale of the task, the latter is chosen in specific practice to save time. In addition, the trained model will be directly used in the large dataset to calculate the corresponding initial embedding.
The initial embedding of entity relation and attribute information do not consider the graph structure
and do not require vector random initialization followed by training. Instead, the BERT fine-tuned in
the previous section is directly inputted with the relation name, neighbor entity name, attribute name,
and value to calculate the embedding for each item. The overall process is shown in Figure 3. The
information is represented as the concatenation of the relation and neighboring entity (ˆ, ˆ), and the
attribute information is represented as the concatenation of the attribute and value (ˆ, ˆ).
(
This chapter introduces attribute encoding based on graph neural network. In the previous section, pure semantic calculation was used, which resulted in the loss of a large amount of structural information. Graph neural network can be used to compensate for this deficiency. By aggregating entity relation and attribute information, the relation and attribute encoding of the entity are calculated and generated. With the original entity encoding, a triple-channel encoding is formed for each entity, fully integrating its semantic and structural information. The overall process is shown in Fig.3.
From the perspective of the entity channel, the entity embedding ˆ in Section 3.2 is used, and the
entity channel encoding = ˆ contains the semantic information of the entity name. In the
relation channel, the information of neighbor triples (, 1, 1), · · · , (, , ) of the entity is
used, and the aggregate function (· ) is used to aggregate the information of triples. The entity encoding
in the relation channel is as follows:
= 1([1; 1], · · · , [; ])
(
= 2([1; 1], · · · , [; ]) where aggregation function 1 and 2 are supposed to be a function that can filter information.
Instead of averaging the embedding, weights are added to represent the importance of attributes and relations. Since there are many entity relations and attributes, and the attribute values are obviously heterogeneous, it is necessary to select important relation and attribute features. Not all relations and attributes can represent the distinctive features of the entity. For example, many cities share the same time zone, so the importance of attributes such as time zone ofset should be relatively low. Referring to the method of relation inference in PARIS [33], the importance of relation and attribute is represented as: () = |{|(, , ) ∈ }|
|{(, )|(, , ) ∈ }| (
|{(, )|(, , ) ∈ }| when (· ) = 1, the neighbors and attribute values corresponding to diferent relations and attributes must be diferent, which means that this relation or attribute can represent the unique property of the entity.
When calculating the channel encoding by importance weighted summation, it is also necessary to normalize the importance (· ) of all neighboring relations and attributes of the entity : ( ( )) ′( ) = ∑︀∈() ( ())
( ( )) ′( ) = ∑︀∈() ( ()) where () represents all neighboring relations or attributes of the entity .
Based on the previous process, we obtained entity embedding from entity, relation, and attribute channels respectively. The challenge in this section is how to fuse the information in the three channels without interfering with each other. We use the idea of channel isolation, which is to perform entity retrieval separately in the three channels, forming their respective candidate entity sets. We do not perform fusion training of embedding, but focus efectively fusing candidate entities, because relations, attributes, and values are heterogeneous, and the concatenation or training makes no sense and will harm the performance.
Facing the retrieval of large-scale KGs, this article uses the Locality Sensitive Hashing (LSH) algorithm to perform approximate nearest neighbor search in high-dimensional space. This algorithm has good accuracy and scalability. In the three channels, retrieval is performed separately, and the similarity threshold is set filter out low similarity entities to form target entity set ℎ: ℎ = {′|(, ′) < } where (· ) is calculated by , and we form , and respectively.
To efectively fuse candidate entity sets, it is necessary to correctly sort them. The experimental
results show that the accuracy of one-channel sorting is > > ℎ, so the candidate
sets are sorted one-dimensionally according to this order. When the matching of valid target entities
cannot be achieved because of the mismatching names, the relation and attribute channels can provide
structural information as compensation, and the noise does not interfere with each other.
(
This chapter presents a series of experiments to verify the efectiveness of ScaleEA, including experimental setting, results analysis, ablation experiment, and scalability test. The experimental settings introduce the datasets, evaluation metrics, details, and benchmarks, providing necessary background for the subsequent analysis. The result analysis focuses on the performance of ScaleEA on large, medium, and small KGs, indicating it has advantages in memory and time eficiency. The ablation experiments explore the impact of ScaleEA modules. The scalability test evaluates the performance of the model under diferent dataset sizes, revealing that the required time increases almost linearly with dataset size while accuracy maintains at a good level.
4.1.1. Dataset The experiments use cross-lingual datasets generated from DBpedia, which are widely used in EA task. In respect of KG languages, there are EN-FR (English with French) and EN-DE (English with German). In respect of scales, there are 15K, 100K, and 1M, which represent the approximate number of entities in one KG. IDS15K and IDS100K are benchmark datasets (V1) from OpenEA [34]. DBP1M is formed by LargeGNN [32], which is specifically designed for large-scale EA tasks by removing all entities with no neighbours and leaving half of entities unable to find their aligned counterparts. The number of entities, relations, attributes, and values in the dataset are shown in Table 1. The meaning of variables are as follows: entity, number of entities in corresponding KG; rel, number of relations; attr, number of attributes; val, number of attribute values. No attribute and value information of large-scale dataset are given since they won’t be used. Following LargeGNN [32], the dataset is divided into train, test, and validation set at a 30%, 60%, and 10% ratio. 4.1.2. Metrics We use Hits@N, MRR, and running time as our metrics. Hits@N also known as N-hit rate, indicating the proportion of aligned entities in the top N matching results. The higher number equals better performance in covering aligned entities in the top N query results. MRR, which stands for Mean Reciprocal Rank, indicating the average of the reciprocal rank of aligned entities in the query results. Specifically, if the rank of aligned entity is , then the MRR is 1/. If no matching entity is found, then the MRR is 0. Running time refers to the time required for the entire experiment. In large-scale experiments, time is especially significant.
The specific experimental details of ScaleEA are as follows. In the model fine-tuning phase, the dimension of the vector embedding is fixed at 300, and the AdamW optimizer is used to train for 15 epochs. As there are a large number of noisy property values in large-scale KG, for eficiency, the attribute channel is only added to the small-scale dataset. Only entity name and relation channels are used to align large-scale KGs. In entity retrieval phase, a distance threshold = 0.15 is used to filter low-similarity entities. All experiments are conducted on one NVIDIA GeForce RTX 3090 GPU.
As most embedding-based methods cannot run on large-scale datasets, we only compare our approach
with large-scale EA methods. All these methods divide graphs into small blocks, then do block alignment.
(
Table2 shows results of ScaleEA method on the DBP-datasets. Compared with existing models, our method achieves best performance in terms of accuracy and time, which outperforms the second-best baseline model LargeEA. The main reason why ScaleEA achieves good performance on such a large dataset is because of literal information. Although the improvement of hit@N is obvious, we also find that the increase of hit@5 is not as high as hit@1. The reason behind it comes from the rough channel fusion, as we only sort the candidate sets by a strict order: name, relation, attribute. If the name channel gives wrong candidates, they can’t be filtered out efectively.
In terms of time, the required time for our method is also the shortest, as we don’t need any training except fine-tuning. The other methods combine GNN training methods with graph division, training all sub-graphs to construct a robust EA model. For a fair comparison, we use the same training method RREA in diferent methods, and the results show training time is much longer than the division. For our method ScaleEA, since the overall training is minimal, the time is mainly spent on computing entity embedding. Although it’s short, it is dificult to be further compressed.
We conduct ablation experiments testing performance of ScaleEA individual channels. Since only the
small dataset use all channels, the experimental results on the 15K dataset are presented here. The
situations of other datasets are very similar, with some slight numerical changes. Compared with the
complete ScaleEA, the ablation experimental groups are: (
There are four main observations from the ablation experiments: (
DBP1M EN-FR
MRR Time(h)
Mem(GB)
DBP1M EN-DE
MRR Time(h) 0.839 0.412 0.430 0.395 0.841
Methods LargeEA
LIME
DivEA LargeGNN
Methods LargeEA
LIME
DivEA LargeGNN
ScaleEA
0.856
0.518
0.522
0.531
0.853
this: (
In general, ScaleEA has good scalability, as shown in Figure5. In terms of time, the overall time required by the model increases linearly with the rise of the dataset size, and the time required for the 1M is about ten times that of the 100K. Specially, The time for the 15K includes fine-tuning model, while the time for medium and large-scale is only related to the number of entities, relations, attributes, and values. In terms of accuracy, as the dataset size increases, the noises rise up, leading to a decrease in accuracy. While Hit@1 from 15K to 1M decreases by a maximum of 0.099, accuracy remains at a relatively high level. In terms of datasets, the required time and alignment accuracy for diferent datasets(EN-FR, EN-DE) are similar, Compared with competitors, ScaleEA is less afected by the dataset lingual property.
This article proposes ScaleEA, a model for large-scale entity alignment tasks. Rather than partitioning
large knowledge graph, ScaleEA fine-tune BERT and does not do additional training, ensuring the
fewest training parameters and time. ScaleEA has significant advantages in terms of time and memory.
The superior performance of ScaleEA reveals four points: (
In the future, we will explore better way to aggregate relation and attribute information by incorporating prior knowledge, mining potential structural information, and reducing noise interference from heterogeneous information. In each stage, we will explore more to shorten the computation time.
This work was supported by the National Natural Science Foundation of China (No. 62276026). [17] C. Li, Y. Cao, L. Hou, J. Shi, J. Li, T.-S. Chua, Semi-supervised entity alignment via joint knowledge embedding model and cross-graph model, Association for Computational Linguistics, 2019. [18] X. Mao, W. Wang, H. Xu, M. Lan, Y. Wu, Mraea: an eficient and robust entity alignment approach for cross-lingual knowledge graph, in: Proceedings of the 13th International Conference on Web Search and Data Mining, 2020, pp. 420–428. [19] Z. Sun, M. Chen, W. Hu, C. Wang, J. Dai, W. Zhang, Knowledge association with hyperbolic knowledge graph embeddings, arXiv preprint arXiv:2010.02162 (2020). [20] Z. Wang, Q. Lv, X. Lan, Y. Zhang, Cross-lingual knowledge graph alignment via graph convolutional networks, in: Proceedings of the 2018 conference on empirical methods in natural language processing, 2018, pp. 349–357. [21] Z. Liu, Y. Cao, L. Pan, J. Li, T.-S. Chua, Exploring and evaluating attributes, values, and structures for entity alignment, arXiv preprint arXiv:2010.03249 (2020). [22] H. Nie, X. Han, L. Sun, C. M. Wong, Q. Chen, S. Wu, W. Zhang, Global structure and local semantics-preserved embeddings for entity alignment, in: Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, 2021, pp. 3658–3664. [23] Z. Sun, W. Hu, C. Li, Cross-lingual entity alignment via joint attribute-preserving embedding, in: The Semantic Web–ISWC 2017: 16th International Semantic Web Conference, Vienna, Austria, October 21–25, 2017, Proceedings, Part I 16, Springer, 2017, pp. 628–644. [24] H.-W. Yang, Y. Zou, P. Shi, W. Lu, J. Lin, X. Sun, Aligning cross-lingual entities with multi-aspect information, arXiv preprint arXiv:1910.06575 (2019). [25] Q. Zhang, Z. Sun, W. Hu, M. Chen, L. Guo, Y. Qu, Multi-view knowledge graph embedding for entity alignment, arXiv preprint arXiv:1906.02390 (2019). [26] M. Chen, Y. Tian, K.-W. Chang, S. Skiena, C. Zaniolo, Co-training embeddings of knowledge graphs and entity descriptions for cross-lingual entity alignment, arXiv preprint arXiv:1806.06478 (2018). [27] F. Liu, M. Chen, D. Roth, N. Collier, Visual pivoting for (unsupervised) entity alignment, in:
Proceedings of the AAAI conference on artificial intelligence, volume 35, 2021, pp. 4257–4266. [28] K. Yang, S. Liu, J. Zhao, Y. Wang, B. Xie, Cotsae: co-training of structure and attribute embeddings for entity alignment, in: Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, 2020, pp. 3025–3032. [29] C. Ge, X. Liu, L. Chen, B. Zheng, Y. Gao, Largeea: Aligning entities for large-scale knowledge graphs, arXiv preprint arXiv:2108.05211 (2021). [30] W. Zeng, X. Zhao, X. Li, J. Tang, W. Wang, On entity alignment at scale, The VLDB Journal 31 (2022) 1009–1033. [31] B. Liu, W. Hua, G. Zuccon, G. Zhao, X. Zhang, High-quality task division for large-scale entity alignment, in: Proceedings of the 31st ACM International Conference on Information & Knowledge Management, 2022, pp. 1258–1268. [32] K. Xin, Z. Sun, W. Hua, W. Hu, J. Qu, X. Zhou, Large-scale entity alignment via knowledge graph merging, partitioning and embedding, in: Proceedings of the 31st ACM International Conference on Information & Knowledge Management, 2022, pp. 2240–2249. [33] F. M. Suchanek, S. Abiteboul, P. Senellart, Paris: Probabilistic alignment of relations, instances, and schema, arXiv preprint arXiv:1111.7164 (2011). [34] Z. Sun, Q. Zhang, W. Hu, C. Wang, M. Chen, F. Akrami, C. Li, A benchmarking study of embeddingbased entity alignment for knowledge graphs, arXiv preprint arXiv:2003.07743 (2020).