An Effective and Efficient Entity Alignment Decoding Algorithm via Third-Order Tensor Isomorphism (2022)

Abstract: Entity alignment (EA) aims to discover the equivalent entity pairs between KGs, which is a crucial step for integrating multi-source KGs.For a long time, most researchers have regarded EA as a pure graph representation learning task and focused on improving graph encoders while paying little attention to the decoding process. In this paper, we propose an effective and efficient EA Decoding Algorithm via Third-order Tensor Isomorphism (DATTI).Specifically, we derive two sets of isomorphism equations: (1) Adjacency tensor isomorphism equations and (2) Gramian tensor isomorphism equations. By combining these equations, DATTI could effectively utilize the adjacency and inner correlation isomorphisms of KGs to enhance the decoding process of EA.Extensive experiments on public datasets indicate that our decoding algorithm can deliver significant performance improvements even on the most advanced EA methods, while the extra required time is less than 3 seconds.

## introduction knowledge graphs (kgs) illustrate the relations between real-world entities-e.g., objects, situations, or concepts-and usually are stored in the form of triples @xcite . over recent years, a large number of kgs have been constructed to provide structural knowledge to facilitate downstream applications, such as recommendation systems @xcite and question-answering systems @xcite . most kgs are independently extracted from different languages or domains. thus, these kgs usually hold unique information individually but also have some shared parts. integrating these crosslingual / domain kgs could provide a broader view for users, especially for the minority language users who usually suffer from lacking language resources. as shown in figure 1 , entity alignment (ea) aims existing ea methods are built on the same core premise: equivalent entity pairs between kgs have similar neighborhood structures (i.e., isomorphism). therefore, most existing ea methods @xcite @xcite could be abstracted into the same architecture (as shown in figure 2 ): encoding the structural information of kgs into a low-dimensional vector space by siamese graph encoders and then mapping equivalent entity pairs into the proximate space by alignment loss functions. for a long time, most researchers have regarded ea as a graph representation learning task and focused on improving graph encoders. starting from the simplest graph encoder transe @xcite , the newest graph encoding methods are successively introduced into ea and achieve decent improvements. for example, gcn-align @xcite first proposed to use graph convolutional networks (gcn) @xcite to encode kgs. rsn @xcite introduces recurrent neural networks (rnn) @xcite and biased random walk to exploit the long-term relational dependencies existing in kgs. dual-amn @xcite proposes the proxy-matching layer and normalized hard samples mining loss to speed up the training process. in stark contrast to the efforts on graph encoders, few researchers focus on improving ea decoding algorithms @xcite , which have been proved to significantly improve performance and reliability in other fields, such as dependency parsing @xcite and machine translation @xcite . earlier ea studies @xcite simply calculate the similarities of each pair of entities and select the closest one as the alignment result. this naive strategy results in one entity may be aligned to multiple entities simultaneously, which violates the one-to-one constraint of ea 1 . thus, some recent studies @xcite propose the global alignment strategy, i.e., regarding the decoding process as a oneto-one assignment problem that could be solved by the hungarian algorithm @xcite . overall, these studies just use existing decoding algorithms without further exploration of kgs' characteristics. similar to graph encoders, we argue that a good ea decoding algorithm should also be capable of exploiting the structural information of kgs. in this paper, we propose an effective and efficient ea decoding algorithm via third-order tensor isomorphism (datti). different from recent studies @xcite that regard ea as a matrix (second-order tensor) isomorphism problem, we express the isomorphism of kgs in the form of third-order tensors, which could completely describe the structural information of kgs. specifically, we derive two sets of tensor isomorphism equations: (1) adjacency tensor isomorphism equations and (2) gramian tensor isomorphism equations. by combining these equations, datti could effectively utilize the adjacency and inner correlation isomorphisms of kgs to enhance the decoding process of ea, thus significantly improving the performance. besides, the introduction of third-order tensors will inevitably lead to a quadratic increase in space-time complexity. therefore, we adopt the randomized truncated singular value decomposition algorithm (rtsvd) @xcite and sinkhorn operator @xcite to improve efficiency. to comprehensively evaluate our proposed method, we apply datti to three advanced ea methods with different kinds of graph encoders. experimental results on two widely used public datasets show that datti can deliver significant performance improvements (3.9% on hits@1 and 3.2% on mrr) even on the most advanced ea 1 most kgs usually have removed the duplicated entities within the same kg. ## the proposed method in the following, we describe our proposed decoding algorithm (datti), which consists of two sets of tensor isomorphism equations: (1) adjacency tensor isomorphism equations and (2) gramian tensor isomorphism equations. furthermore, we adopt the randomized truncated singular value decomposition (rtsvd) algorithm and the sinkhorn operator to speed up the decoding process. ## experiments our experiments are conducted on a pc with a geforce gtx 3090 gpu and a ryzen threadripper 3970x cpu. the code and datasets are available in github 2 . ## conclusion in this paper, we propose an effective and efficient ea decoding algorithm via third-order tensor isomorphism (datti). extensive experiments on public datasets indicate that our decoding algorithm can deliver significant performance improvements even on the most advanced ea methods, while the extra required time is less than 3 seconds.