An Effective and Efficient Time-aware Entity Alignment Framework via Two-aspect Three-view Label Propagation

1 Introduction

Knowledge graphs (KGs) describe the real world with structured facts. A fact consists of a head entity, a tail entity, and a relation connecting them, which can be formally represented as a triple (eh, r, et), such as (George Porter, hasWonPrize, Nobel Prize in Chemistry). KGs have been widely used in information retrieval [Dietz et al., 2018], question answering [Lan et al., 2021], and recommedation systems [Guo et al., 2022].

∗Corresponding author

Existing KGs ignore the temporal information which indicates when a fact occurred. In the real world, some facts only happened at a specific time. Therefore, Wikidata [Vrandecic and Kr¨otzsch, 2014] and YOGO2 [Hoffart et al., 2013] add temporal information to represent the KGs more accurately, and some event KGs [Lautenschlager et al., 2015; Leetaru and Schrodt, 2013] also contain the timestamps indicating when the events occurred. In the temporal knowledge graphs (TKGs), a fact is expanded into a quadruple (eh, r, et, τ), where τ represents the timestamps.

Entity alignment (EA) seeks to find the same entities in the real world between different KGs, which is important for knowledge fusion between multi-source and multi-lingual KGs. In recent years, the embedding-based EA methods [Sun et al., 2020] have been widely investigated, which represent the entities in the low-dimensional vector space, and calculate the similarity of these vectors to obtain the equivalent entity pairs. Earlier EA methods [Chen et al., 2017; Sun et al., 2017] are based on the translation model. However, since the inability of such models to effectively capture graph structures, graph neural networks (GNN)-based models [Wang et al., 2018; Mao et al., 2020a] emerge and achieve superior performance. Due to the scalability limitation of GNN [Wu et al., 2022], these models are not suitable for large-scale KGs. LightEA [Mao et al., 2022b] significantly enhances the efficiency of EA by utilizing a three-view label propagation instead of GNN.

Despite the success of the above EA methods, they all ignore the temporal information in the KGs, thus may lead to wrong alignment between similar entities in different KGs. Take Figure 1 as an example. There are two subgraphs from YAGO and Wikidata. George Porter in TKG1 and Harray Kroto in TKG2 have similar structure and relations. Both of them have the same neighbors (Copley Medal, Nobel Prize in Chemistry, and Michael Faraday Prize) and relations (hasWonPrize in TKG1 is same as award recieved in TKG2). George Porter has another neighbor Davy Medal and relation hasWonPrize. Existing EA methods disregard temporal information of KGs and may wrongly take George Porter and Harray Kroto as an equivalent entity pair.

Recently, time-aware methods [Xu et al., 2021; Xu et al., 2022] emerge to improve the performance of EA between TKG. STEA [Cai et al., 2022] adopts a simple GNN with a temporal information matching mechanism and achieves state-of-the-art (SOTA) performance. All of these TEAmethods are based on GNN [Wu et al., 2022], which has an inherent defect: the GNN is trained using the gradient descent algorithm and takes much time to converge to the optimal solution. Therefore, to promote the development of EA between TKGs, a straightforward approach is to combine the advantages of EA and TEA methods.

To this end, we propose an effective and efficient nonneural EA framework between TKGs, namely LightTEA, which consists of four key components: (1) Two-aspect Three-view Label Propagation. We combine relational-aspect and temporal-aspect three-view label propagation (LP) to improve the performance of EA. In this module, GNN is replaced by LP, which does not require gradient propagation to train the neural networks, greatly reducing the time consumption of the model. (2) Sparse Similarity with Temporal Constraints. Instead of calculating the similarity of all entities, we only retrieve the top-k nearest neighbors of each entity to find the equivalent entity pairs, which saves the time complexity and space complexity of calculation. By utilizing the temporal information of each entity as the constraints of entity similarity, the EA performance is also improved. (3) Sinkhorn Operator. To further promote the model's effectiveness, we regard the EA problem as a one-to-one assignment problem and use the Sinkhorn operator to solve it. The Sinkhorn operator is a fast and completely parallelizable algorithm and only takes seconds to converge to the optimal solution. and (4) Temporal Iterative Learning. Several studies have demonstrated that iterative learning effectively enhances EA and helps address the lack of alignment seeds in the real scenario. We adopt a temporal iterative learning strategy, which utilizes the additional temporal information of entities to get more credible alignment pairs for augmenting the training set to obtain better alignment results. In general, this paper presents the following contributions:

• We propose an effective and efficient TEA framework that consists of four essential components: (1) Twoaspect Three-view Label Propagation, (2) Sparse Similarity with Temporal Constraints, (3) Sinkhorn Operator, and (4) Temporal Iterative Learning. All of these modules work together to improve the performance of EA while reducing time consumption.
• The proposed TEA framework combines the strengths of the latest SOTA EA and TEA models and addresses the limitations of current EA models that do not effectively utilize time information, as well as the scalability constraints of TEA models due to GNN usage.
• Extensive experiments on public datasets indicate that our proposed model significantly outperforms the SOTA methods for EA between TKGs, and the time consumed by LightTEA is only dozens of seconds at most, no more than 10% of the most efficient TEA method.

2 RelatedWork

2.1 Entity Alignment

The purpose of EA is to find the equivalent entity pairs from different KGs. EA usually adopts embedding-based approaches, which are divided into two sub-categories: translation-based and GNN-based models.

Translation-based models regard the relations as the translation from the head entities to the tail entities, such as (heh +hr ≈ het ). MTransE [Chen et al., 2017] is the early entity alignment model based on TransE [Bordes et al., 2013], which maps two KGs into different vector spaces and considers the entities with similar positions in the two vector spaces as equivalent pairs. In addition to learning the structure embeddings of entities based on TransE with the relation triples, JAPE [Sun et al., 2017] joins the attribute embedding and structure embedding of entities to align entities. BootEA [Sun et al., 2018] obtains the alignment-oriented KG embeddings and proposes a bootstrapping process by adding likely alignment entities into training data iteratively to improve the performance of EA.

GNN-based models promote EA by utilizing the graph structure of KGs. GCN-Align [Wang et al., 2018] encodes the entities into a unified vector space via GCN [Kipf and Welling, 2017] and aligns the entities with their structure embeddings and attribute embeddings. However, GCNAlign does not effectively utilize the relation of KGs. MRAEA [Mao et al., 2020a] learns the entity embeddings through a relation-aware self-attention GNN to obtain the alignment entities. RREA [Mao et al., 2020b] proposes a GNN with relational reflection to get the relation-specific embeddings and uses an iterative strategy to enhance EA.

The above methods focus on encoding the entity embeddings and aligning the entities by calculating the similarity of their embeddings, DATTI [Mao et al., 2022a] applies a decoding process using the adjacency and inner correlation isomorphisms of KGs to the advanced methods and gains significant performance improvements. LightEA [Mao et al., 2022b] adopts a three-view label propagation approach for entity alignment instead of using GNN and achieves comparable performance with SOTA EA methods while taking only one-tenth of the time consumption of those methods.

Although these methods have significantly advanced the development of EA, they all have the limitation of neglecting the temporal information in KGs.

2.2 Time-aware Entity Alignment

Recently, the research on TKGs has developed rapidly, and TEA methods have also sprung up. TEA-GNN [Xu et al., 2021] is the first TEA method using temporal information in KGs. It introduces a time-aware attention mechanism to learn entity embedding based on GNN and constructs five datasets extracted from ICEWS, YAGO3, and Wikidata to evaluate the model. TREA [Xu et al., 2022] utilizes a temporal relational attention mechanism to integrate relational and temporal features of entities from the neighborhood and adopts the margin-based multi-class log-loss (MML) with sequential time regularizer to train the model. TREA is the most efficient TEA model since the MML can achieve fast convergence. STEA [Cai et al., 2022] presents a simple GNN to learn the entity embeddings and uses a temporal information matching mechanism to calculate the time similarity of entities. Then it balances the time similarity and embedding similarity of entities to obtain the equivalent pairs.

By using the temporal information, the TEA methods achieve better performance. However, since the experimental datasets are much smaller than real-world KGs, these methods focus on improving performance and ignore efficiency. Although TREA utilizes MML to accelerate convergence, all TEA methods are based on GNN [Wu et al., 2022] and suffer from scalability issues. So we propose an effective and efficient TEA framework to address the limitations.

3 ProblemFormulation

A TKG can be formalized as G = (E,R, T,Q), where E, R and T are the sets of entities, relations, and timestamps respectively, Q ⊂ E ×R×E × T denotes the set of quadruples. A quadruple stores the real-world fact and can be presented as (eh, r, et, τ), where eh, et ∈ E. Given two TKGs G1 = (E1,R1, T1,Q1), G2 = (E2,R2, T2,Q2), and alignment seeds set S = {(e1i , e2j )|e1i ∈ E1, e2j ∈ E2, e1i ≡ e2j } where ≡ denotes equivalence. EA task aims to find new equivalent entity pairs between G1 and G2 based on S. C is the set of reference entity pairs used for evaluation. Specifically, a uniform time set T ∗ = T1 ∪ T2 is constructed by merging the timestamps in the two time sets. Therefore, the two TKGs can be renewed as G1 = (E1,R1, T ∗ ,Q1) and G2 = (E2, R2, T ∗ , Q2) sharing the same set of timestamps.

4 The Proposed Approach

The LightTEA framework can be described as three phases with time similarity enhancement. (1) For pre-alignment phase, we use two-aspect three-view label propagation to learn the labels of entities. (2) For alignment phase, we first compute the sparse similarity with temporal constraints, then translate the EA problem to the assignment problem and utilize the Sinkhorn operator to resolve it. (3) For postalignment phase, we adopt a temporal iterative learning strategy to enhance EA. Figure 2 shows the framework of LightTEA.

4.1 Two-aspect Three-view Label Propagation

Inspired by LightEA [Mao et al., 2022b], we extend the threeview label propagation to two-aspect (relational-aspect and temporal-aspect) three-view label propagation, which can enhance EA with temporal information while not increase the time and space complexity.

Specifically, the TKG requires a four-order tensor A ∈ R|E|×|E|×|R|×|T| to fully describe the adjacency relations. As shown in Figure 3(a), we regard TKG as two three-order tensor AR ∈ R|E|×|E|×|R| and AT ∈ R|E|×|E|×|T| , there are five-view in TKGs: AER ∈ R|E|×|R| , ARE ∈ R|R|×|E| , AEE ∈ R|E|×|E| , ATE ∈ R|T|×|E| , and AET ∈ R|E|×|T| , which represent the adjacency relations from head entity to relation, relation to tail entity, head entity to tail entity, timestamps to tail entity, head entity to timestamps, respectively. Then, we use the relational-aspect and temporal-aspect threeviews label propagation to update the labels of entities, relations, and timestamps (as shown in Figure 3(b)).

The relational-aspect three-views label propagation can be presented as follows:

where Le ∈ R|E|×|d| , Lr ∈ R|R|×|d| are label matrixs of entities and relations, · means the dot product. Following LightEA, we regard each pair of alignment entities as an independent class, and independently sample random vectors on the d-dimensional hyper-sphere to approximate the onehot label vectors for representing the alignment seeds, so we set l(0) ei = l(0) ej = random(d) ∀(ei, ej) ∈ S. For the entities in the candidate set C, we initialize the label of them as l(0) ek = l(0) el = 0 ∀(ek, el) ∈ C, and the initial label matrix of relations is also set to all-zero L(0) r = 0.

The final label of entity ei in the relational aspect is the concatenation of label vectors in all steps:

The temporal-aspect three-views label propagation can be expressed as follows:

where L′e ∈ R|E|×|d| , and the initializtion label matrix of L(0)′ e is the same as L(0) e . Lt ∈ R|T|×|d| is label matrix of timestamps and is initialized to L(0) t = 0.

We concatenate the label vectors of all steps as the final label of entity ei in the temporal aspect:

Finally, the label of entity ei is the balanced result of the two aspect labels:

where α is a hyper-parameter to balance the label of relational aspect and temporal aspect.

4.2 Temporal Information Similarity Calculation

Recent research( [Cai et al., 2022]) suggests that the temporal information similarity can enhance the EA between TKGs, so we calculate the time similarity matrix and use it in the alignment and post-alignment phase.

First, we collect all timestamps of entities. Then we calculate the time similarity steiej of ei and ej by the following:

where v denote the number of same items of ei and ej, k and q are the numbers of timestamps of ei and ej, respectively.

4.3 Sparse Similarity with Temporal Constraints

After obtaining the labels of entities, we calculate the similarity of entities by their labels in a sparse way with temporal constraints.

Early studies [Chen et al., 2017; Wang et al., 2018; Xu et al., 2021] calculate the embedding similarity (Cosine, Euclidean, or Manhattan distance) of all entities to find the equivalent entity pairs. The calculation complexity is O(|E|2d), and the space complexity of the similarity matrix is O(|E|2 ). LightEA [Mao et al., 2022b] notices that the similarity of many entities is very small and infinitely close to zero. Even if these smaller values are removed initially, it does not significantly affect the alignment results. Therefore, instead of calculating the similarities between all entities, we only retrieve the top-k nearest neighbors for each entity by approximate nearest neighbor (ANN) algorithms 1 . It only takes several seconds to find the top-k nearest neighbors, and the space complexity of the sparse similarity matrix is O(|E|k), k ≪ |E|.

Different from LightEA, we use the time similarity matrix as a constraint to obtain the sparse similarity of entities. Specifically, we get the sparse similarity matrix Sl ∈ R|E|×k by the ANN algorithms with the labels of entities and find the related time similarity of these entities, the final sparse similarity of entities is as follows:

1 In LightTEA, we use the FAISS framework [Johnson et al., 2021] for approximate vector retrieval

where β is the hyper-parameter for balancing the label similarity and time similarity of entities.

4.4 Sinkhorn Operator

Existing TEA methods [Xu et al., 2021; Xu et al., 2022; Cai et al., 2022] simply calculate the similarity of the entities to obtain the equivalent entity pairs in the alignment phase. To further improve the effectiveness of the model, we adopt the Sinkhorn operator in the alignment phase to enhance EA.

LightEA [Mao et al., 2022b] regards the EA problem as a one-to-one assignment problem to improve the performance of EA. The goal of the assignment problem is to find the optimal strategy to obtain the maximum profit and can be formulated as follows:

where P is a permutation matrix that has exactly one entry of 1 in each row and each column and 0s elsewhere. P|E| is the set of |E| × |E| permutation matrices, S ∈ R|E|×|E| is the similarity matrix of entities, and ⟨·⟩F represents the Frobenius inner product.

The Sinkhorn operator proposes a fast and completely parallelizable algorithm for the assignment problem. It iteratively normalizes rows and columns of the similarity matrix:

where Nr(S) = S ⊘ (S1N1⊤N ), Nc(S) = S ⊘ (1N1⊤N S) are the row and column-wise normalization operators, ⊘ denotes the element-wise division, 1N represents a column vector of ones, and m is the iterations. The time complexity of Sinkhorn is O(m|E|2 ).

We also regard the EA problem as an assignment problem and employ the Sinkhorn operator to obtain the approximate solution:

where S′ ∈ R|E|×k is the sparse similarity matrix with temporal constraints, which is calculated by equation (9), t is the temperature. In this way, the performance of EA improves significantly, and the computational complexity drops to O(m|E|k).

4.5 Temporal Iterative Learning

Iterative Learning is proposed by BootEA [Sun et al., 2018] to address the problem of fewer alignment seeds and enhance the performance of EA. It is also called a semi-supervised alignment strategy which continuously selects possible entity pairs to augment the training data through an iterative method in the post-alignment phase.

To promote EA, we adopt temporal iterative learning. Different from STEA [Cai et al., 2022], which adopts a bidirectional iterative strategy, we simply choose the entity and its nearest neighbor whose similarity value is greater than the threshold 2 as the alignment pairs and add them to the training set for the next iteration.

5 Experiments

We conduct the experiments on a workstation with a GeForce RTX 3090 GPU and an AMD EPYC 7502 32-Core Processor CPU, 128GB memory. The codes and datasets will be available on GitHub 3 .

5.1 Datasets

To comprehensively evaluate the effectiveness and efficiency of the proposed model, we experiment on two widely used public datasets. The statistics of these datasets are listed in Table 1.

1. DICEWS-1K/200 [Xu et al., 2021] is constructed from the event knowledge graph ICEWS05-15 which contains events during 2005 to 2015. It consists of two subsets with different alignment seeds 1K/200.
2. YAGO-WIKI50K-5K/1K [Xu et al., 2021] extracts the equivalent entities with temporal information from YAGO and Wikidata. There are two subsets, one with 5K alignment seeds and the other with 1K.

5.2 Baselines

In the experiments, we compared our proposed model with two categories of advanced entity alignment methods:

1. Supervised methods: JAPE [Sun et al., 2017], AlignE [Sun et al., 2018], GCN-Align [Wang et al., 2018], MRAEA [Mao et al., 2020a], LightEA* [Mao et al., 2022b], TEA-GNN [Xu et al., 2021], TREA [Xu et al., 2022], and STEA* [Cai et al., 2022]. JAPE, AlignE, GCNAlign, MRAEA, and LightEA* are EA methods, TEA-GNN, TREA, and STEA* are TEA methods.
2. Semi-supervised methods: BootEA [Sun et al., 2018], RREA [Mao et al., 2020b], LightEA [Mao et al., 2022b], STEA [Cai et al., 2022]. BootEA, RREA, and LightEA are EA methods, STEA is a TEA method.

2 The threshold is 0.8 in LightTEA.

3 https://github.com/lcai2/LightTEA

The main experiment results of these methods reported in the paper are from STEA (SOTA TEA method), except the latest SOTA EA method LightEA. The experiments of LigthEA are implemented on its open-source code. For a fair comparison, LightTEA has two corresponding versions: (1) LightTEA* is the supervised version. (2) LightTEA is the semi-supervised version with iterative learning.

5.3 Settings

Evaluation Metrics

Following the conventions, we adopt mean reciprocal rank (MRR) and Hits@k (k = 1, 10) as the evaluation metrics. MRR reports the average reciprocal of the ranks, and Hits@k calculates the proportion of correct alignment pairs whose rank is not greater than k. In particular, Hits@1 represents the accuracy of the results, which is the most important indicator. The higher the MRR and Hits@k, the better the performance.

Implementation Details

We use the fixed training set and validation set provided by TEA-GNN. The hyper-parameters are set as follows: the dimension of the hyper-sphere is d = 512, the factor α is set to 0.6 for DICEWS and 0.5 for YAGO-WIKI50K to balance the relational-aspect and temporal-aspect label propagation, the factor β is set to 0.4 for balancing the label similarity and time similarity. Following LightEA, we use rounds n = 2 for two-aspect three-view label propagation, retrieve the topk = 500 nearest neighbors for sparse similarity, set the number of iterations of the Sinkhorn operator to m = 15, and set the temperature to t = 0.05. The reported performances are the averages of five independent runs.

5.4 Main Experiments

Table 2 lists the main experimental results of our proposed model and all baselines on the four datasets. Among the supervised methods, LightTEA* has significant improvements in all metrics. Compared to the SOTA supervised TEA method STEA*, LightTEA* improves the Hits@1 by 2.61%, 2.33%, 5.45%, and 9.22%, respectively. In the semisupervised methods, LightTEA outperforms all the baselines on all datasets across all metrics. The improvements of Hits@1 compared with STEA are 0.93%, 1.57%, 2.79%, and 4.77%, respectively. TEA methods perform better in these two categories of methods than EA methods by using temporal information. The semi-supervised methods achieve better performance than supervised methods, which indicates the effectiveness of temporal iterative learning. Without iteration, LightTEA* outperforms all baselines except for STEA's Hits@10 on DICEWS-200 with tiny gap 0.002. The high performance of LightTEA* demonstrates that the two-aspect three-view label propagation, the sparse similarity with temporal constraints, and the Sinkhorn operator are effective in promoting EA. We conduct one sample t-test between LightTEA(/LightTEA*) and their corresponding strong baselines. All the p-value << 0.01 indicates that our proposed model significantly outperforms all baselines.

5.5 Ablation Study

We conduct an ablation experiment on DICEWS-200 and YAGO-WIKI50K-1K to investigate the contributions of three critical components of LightTEA: (1) Temporal-aspect Label Propagation (TLP), (2) Temporal Constraints (TC), and (3) Sinkhorn Operator (SO).

As reported in Table 3, without temporal-aspect label propagation (w/o TLP), the performance of LightTEA drops a little, which indicates the effectiveness of the temporal-aspect label propagation. When removing the temporal constraints (w/o TC), the underperformance of LightTEA implies the effectiveness of the temporal constraints. Without the Sinkhorn operator (w/o SO), the performance of LightTEA drops significantly, demonstrating the contribution of utilizing the Sinkhorn operator in the alignment phase to enhance EA.

5.6 Efficiency Studys

Table 4 shows the overall time costs on DICEWS-200 and YAGO-WIKI50K-1K datasets by TEA methods from data loading to evaluation. The results of TREA are from [Xu et al., 2022] since it doesn't provide the source codes. The other results are obtained by directly running the source codes provided by the author.

It can be seen from Table 4, in the supervised time-aware methods, TREA costs less time than TEA-GNN with MML, which speed up the convergence. LightTEA* takes much less time than the above two methods. The time costs of LigthTEA* are 5 seconds and 24 seconds on the two datasets, respectively, which are only 3.91% and 0.90% of TREA. In the semi-supervised methods, the time costs of LightTEA are 12 seconds and 85 seconds, which are 2.08% and 1.70% of STEA on the two datasets, respectively. The time consumed by LightTEA is no more than 10% of the most efficient methods TREA. By using temporal iterative learning, LightTEA increases the time consumption while improving performance compared to LightTEA*. The high efficiency of LightTEA indicates that it could be applied to large-scale datasets for EA between TKGs.

5.7 Hyper-parameter Analysis

We conduct experiments on the following hyper-parameters to investigate their effect on the performance of LightTEA.

(1) The dimension of hyper-sphere d. We select the dimension in the set {64, 128, 256, 512, 1024, 2048} and conduct the experiments. The Hits@1 scores with different dimensions on DICEWS-200 are shown in Table 5.

From the table we can see that as the dimension increases, the Hits@1 score for both LightTEA and LightTEA* gradually improves until it reaches their best performance at the dimension of 512. Even if the dimension is further increased, the performance remains unchanged. This indicates that when the dimension of the label vector is greater than 512, it only increases memory consumption and provides no benefit to performance.

1. The balance factors α and β. We set the two factors in range 0∼1 with interval 0.1 to investigate the impact of different values. The experimental results with different α and β on YAGO-WIKI50K-1K are shown in Figure 4.
2. α balances the relational-aspect label propagation (RLP) and temporal-aspect label propagation (TLP). Figure 4(a) shows the Hits@1 of LightTEA* and LightTEA with different α. Due to the use of temporal iterative learning, the performance of LightTEA does not change significantly with different α. The Hits@1 curve of LightTEA* shows that the result of combining RLP and TLP with appropriate weight (α = 0.5) is better than using only one of them (α = 0 or α = 1).

β is used to balance the label similarity and time similarity. As shown in Figure 4(b), with the increase of β, the Hits@1 first increases slowly (reaching the maximum value when β = 0.4), and then decreases rapidly. When β = 1, Hits@1 of LightTEA with temporal iterative learning are lower than LightTEA*, it indicates that only using time similarity to generate the possible alignment pairs and add them to the training set for the next iteration will hurt the performance of the model.

6 Conclusion

Existing EA methods ignore the temporal information in KGs, which may wrongly align similar entities. The TEA methods lack scalability since the inherent defect of GNN. To address the limitations, we proposes an effective and efficient TEA framework that consists of four important components: (1) Two-aspect Three-view Label Propagation, (2) Sparse Similarity with Temporal Constraints, (3) Sinkhorn Operator, and (4) Temporal Iterative Learning. These modules work collaboratively to enhance the model's performance while reducing time consumption.

Extensive experiments on public datasets indicate that the proposed model significantly outperforms the SOTA methods. The time consumed by the model is only dozens of seconds at most, no more than 10% of the most efficient TEA methods, which denotes that our model has high efficiency and can be applied to large-scale TKGs.

Acknowledgements

We appreciate the support from National Natural Science Foundation of China with the Main Research Project on Machine Behavior and Human-Machine Collaborated Decision Making Methodology (72192820 & 72192824), Pudong New Area Science & Technology Development Fund (PKX2021R05), Science and Technology Commission of Shanghai Municipality (22DZ2229004), and Shanghai Trusted Industry Internet Software Collaborative Innovation Center.