L ight EA : A Scalable, Robust, and Interpretable Entity Alignment Framework via Three-view Label Propagation (2022)

Abstract: Entity Alignment (EA) aims to find equivalent entity pairs between KGs, which is the core step to bridging and integrating multi-source KGs. In this paper, we argue that existing complex EA methods inevitably inherit the inborn defects from their neural network lineage: poor interpretability and weak scalability. Inspired by recent studies, we reinvent the classical Label Propagation algorithm to effectively run on KGs and propose a neural-free EA framework — LightEA, consisting of three efficient components: (i) Random Orthogonal Label Generation, (ii) Three-view Label Propagation, and (iii) Sparse Sinkhorn Operation.According to the extensive experiments on public datasets, LightEA has impressive scalability, robustness, and interpretability. With a mere tenth of time consumption, LightEA achieves comparable results to state-of-the-art methods across all datasets and even surpasses them on many. Besides, due to the computational process of LightEA being entirely linear, we could trace the propagation process at each step and clearly explain how the entities are aligned.

## introduction knowledge graph (kg) describes the real-world entities and their internal relations by triples @xcite , expressing the information on the internet in a form closer to human cognition. to this day, kgs have facilitated a mount of downstream internet applications (e.g., search engines @xcite and dialogue systems @xcite ) and become one of the core driving forces in the development of artificial intelligence. in practice, kgs are usually constructed by various departments with multi-source data. therefore, they typically contain complementary knowledge while having overlapping parts. integrating these independent kgs could significantly improve the coverage rate, which is especially beneficial to lowresource language users. entity alignment (ea) aims to find equivalent entity pairs between kgs (as shown in figure 1 ), which is the core step of bridging and integrating multi-source kgs. therefore, ea attracts enormous attention and progresses rapidly. most existing methods regard ea as a graph representation learning task and share the same two-stage architecture: (i) encoding the kgs into low-dimensional spaces via graph encoders (e.g., transe @xcite and gcn @xcite ) and (ii) mapping the embeddings of equivalent entity pairs into a unified vector space through contrastive losses @xcite . recently, graph neural network (gnn) has achieved impressive success in many sorts of graph applications. following @xcite , who first introduced graph convolutional network (gcn) into ea, numerous new fancy mechanisms are proposed and stacked over vanilla gcn for better performance, such as graph matching @xcite , relational attention @xcite , and hyperbolic embedding @xcite . according to an ea paper list foot_0 on github, over 90% of ea methods adopted gnns as their graph encoders in recent three years. however, there is no such thing as a free lunch. these increasingly complex gnn-based methods inherit the following inborn defects from their gnn lineage: (i) weak scalability. since the scales of real-world graphs are usually massive (e.g., yago3 @xcite ) contains 17 million entities), the scalability of graph algorithms is crucial. however, as summarized by @xcite , most advanced ea methods require several hours @xcite or even days @xcite on the dwy100k dataset, which only contains 200, 000 nodes. although an efficient loss function @xcite or a graph sampler @xcite could effectively alleviate this problem, all existing ea methods are still overstretched when facing the real-world kgs. (ii) poor interpretability. interpreting neural networks is a recognized challenge, and the complex graph structure makes it more difficult. a few studies try to explain the behaviors of ea methods by showing wrong cases @xcite or visualizing attention weights @xcite . and most ea studies @xcite @xcite do not attempt to give any interpretation, only focusing on improving the performances on evaluation metrics. an ancient chinese saying goes, "drawing new inspiration while reviewing the old." a recent study @xcite reinvents the classical graph algorithm -label propagation (lp) @xcite , combining it with shallow neural networks. surprisingly, this simple method outperforms the current best-known gnns with more than two orders of magnitude fewer parameters and more than two orders of magnitude less training time. inspired by their excellent work, this paper proposes the three-view label propagation mechanism that enables the lp algorithm, designed for homogeneous graphs, to effectively run on kgs (a kind of typical heterogeneous graph). besides, we further propose two approximation strategies to reduce the computational complexity and enhance the scalability: random orthogonal label generation and sparse sinkhorn iteration. the above three components constitute the proposed non-neural ea framework -lightea. according to the extensive experiments on four groups of public datasets, lightea has impressive scalability, robustness, and interpretability: in addition to the above contributions, we further design extensive auxiliary experiments to investigate the behaviors of lightea in various situations. the source code and datasets are now available in github (github.com/maoxinn/lightea). ## task definition a kg could be defined as @xmath0, r, t ), where e is the entity set, r is the relation set, and t ⊂ e × r × e represents the set of triples. given the source graph g s , the target graph g t , and the set of pre-aligned entity pairs p, ea aims to find new equivalent entity pairs based on g s , g t , and p. ## the proposed method lightea is a non-neural ea framework consisting of three components: (i) random orthogonal label generation, (ii) three-view label propagation, and (iii) sparse sinkhorn iteration. we will describe each component of lightea in this section. ## experiments all experiments are conducted on a pc with an nvidia rtx3090 gpu and an epyc 7452 cpu. ## conclusion label propagation algorithm to effectively run on kgs and propose a non-neural ea framework -lightea. according to the experiments on public datasets, lightea has impressive scalability, robustness, and interpretability. with a mere tenth of time consumption, lightea achieves comparable results to state-ofthe-art methods across all datasets.