Neighborhood Matching Network for Entity Alignment (2020)

Abstract: Structural heterogeneity between knowledge graphs is an outstanding challenge for entity alignment. This paper presents Neighborhood Matching Network (NMN), a novel entity alignment framework for tackling the structural heterogeneity challenge. NMN estimates the similarities between entities to capture both the topological structure and the neighborhood difference. It provides two innovative components for better learning representations for entity alignment. It first uses a novel graph sampling method to distill a discriminative neighborhood for each entity. It then adopts a cross-graph neighborhood matching module to jointly encode the neighborhood difference for a given entity pair. Such strategies allow NMN to effectively construct matching-oriented entity representations while ignoring noisy neighbors that have a negative impact on the alignment task. Extensive experiments performed on three entity alignment datasets show that NMN can well estimate the neighborhood similarity in more tough cases and significantly outperforms 12 previous state-of-the-art methods.

## introduction by aligning entities from different knowledge graphs (kgs) to the same real-world identity, entity alignment is a powerful technique for knowledge integration. unfortunately, entity alignment is nontrivial because real-life kgs are often incomplete and different kgs typically have heterogeneous schemas. consequently, equivalent entities from two kgs could have distinct surface forms or dissimilar neighborhood structures. in recent years, embedding-based methods have become the dominated approach for entity alignment @xcite @xcite @xcite al., * corresponding author. 布鲁克林区 纽约 美国 子行政区 子行政区 纽约州 子行政区 最大城市 最大城市 brooklyn queens southwest new york city subdivision subdivision new york state manhattan south dan houser residence northwest . . . birthplace david julius kg1: 布鲁克林区 # neighbors: 3 # common neighbors: 2 kg2: brooklyn # neighbors: 21 # common neighbors: 2 case 1: equivalent entities with different sizes of neighborhoods (a) 利物浦 英格兰 英国 子行政区 国家 利物浦大学 城市 liverpool labour party (uk) executive england constituent country united kingdom sovereign state . . . birthplace george harrison kg1: 利物浦 # neighbors: 20 # common neighbors: 3 kg2: liverpool # neighbors: 22 # common neighbors: 3 case 2: most common neighbors are not discriminative for alignment (b) 工党(英国) 行政 . . . 2020). such approaches have the advantage of not relying on manually constructed features or rules @xcite . using a set of seed alignments, an embedding-based method models the kg structures to automatically learn how to map the equivalent entities among different kgs into a unified vector space where entity alignment can be performed by measuring the distance between the embeddings of two entities. the vast majority of prior works in this direction build upon an important assumption -entities and their counterparts from other kgs have similar neighborhood structures, and therefore, similar embeddings will be generated for equivalent entities. unfortunately, the assumption does not always hold for real-life scenarios due to the incompleteness and heterogeneities of kgs. as an example, consider figure 1 (a) , which shows two equivalent entities from the chinese and english versions of wikipedia. here, both central entities refer to the same real-world identity, brooklyn, a borough of new york city. however, the two entities have different sizes of neighborhoods and distinct topological structures. the problem of dissimilar neighborhoods between equivalent entities is ubiquitous. @xcite reports that the majority of equivalent entity pairs have different neighbors in the benchmark datasets dbp15k, and the proportions of such entity pairs are over @xcite in different language versions of dbp15k. particularly, we find that the alignment accuracy of existing embedding-based methods decreases significantly as the gap of equivalent entities' neighborhood sizes increases. for instance, rdgcn @xcite , a state-of-the-art, delivers an accuracy of 59% on the hits@1 score on entity pairs whose number of neighbors differs by no more than 10 on dbp15k zh-en . however, its performance drops to 42% when the difference for the number of neighbors increases to 20 and to 35% when the difference increases to be above 30. the disparity of the neighborhood size and topological structures pose a significant challenge for entity alignment methods. even if we were able to set aside the difference in the neighborhood size, we still have another issue. since most of the common neighbors would be popular entities, they will be neighbors of many other entities. as a result, it is still challenging to align such entities. to elaborate on this point, let us now consider figure 1 @xcite . here, the two central entities (both indicate the city liverpool) have similar sizes of neighborhoods and three common neighbors. however, the three common neighbors (indicate united kingdom, england and labour party (uk), respectively) are not discriminative enough. this is because there are many city entities for england which also have the three entities in their neighborhoods -e.g., the entity birmingham. for such entity pairs, in addition to common neighbors, other informative neighbors -like those closely contextually related to the central entities -must be considered. because existing embedding-based methods are unable to choose the right neighbors, we need a better approach. we present neighborhood matching network (nmn), a novel sampling-based entity alignment framework. nmn aims to capture the most informative neighbors and accurately estimate the similarities of neighborhoods between entities in different kgs. nmn achieves these by leveraging the recent development in graph neural networks (gnns). it first utilizes the graph convolutional networks (gcns) @xcite to model the topological connection information, and then selectively samples each entity's neighborhood, aiming at retaining the most informative neighbors towards entity alignment. one of the key challenges here is how to accurately estimate the similarity of any two entities' sampled neighborhood. nmn addresses this challenge by designing a discriminative neighbor matching module to jointly compute the neighbor differences between the sampled subgraph pairs through a cross-graph attention mechanism. note that we mainly focus on the neighbor relevance in the neighborhood sampling and matching modules, while the neighbor connections are modeled by gcns. we show that, by integrating the neighbor connection information and the neighbor relevance information, nmn can effectively align entities from real-world kgs with neighborhood heterogeneity. we evaluate nmn by applying it to benchmark datasets dbp15k @xcite and dwy100k @xcite , and a sparse variant of dbp15k. experimental results show that nmn achieves the best and more robust performance over state-ofthe-arts. this paper makes the following technical contributions. it is the first to: ## related work embedding-based entity alignment. in recent years, embedding-based methods have emerged as viable means for entity alignment. early works in the area utilize transe @xcite to embed kg structures, including mtranse @xcite , jape @xcite , iptranse @xcite , bootea @xcite , naea @xcite and otea @xcite . some more recent studies use gnns to model the structures of kgs, including gcn-align @xcite , gmnn @xcite , rdgcn @xcite , avr-gcn @xcite , and hgcn-je @xcite . besides the structural information, some recent methods like kdcoe @xcite , @xcite , multike @xcite and hman @xcite also utilize additional information like wikipedia entity descriptions and attributes to improve entity representations. however, all the aforementioned methods ignore the neighborhood heterogeneity of kgs. mugnn @xcite and alinet @xcite are two most recent efforts for addressing this issue. while promising, both models still have drawbacks. mugnn requires both pre-aligned entities and relations as training data, which can have expensive overhead for training data labeling. alinet considers all one-hop neighbors of an entity to be equally important when aggregating information. however, not all one-hop neighbors contribute positively to characterizing the target entity. thus, considering all of them without careful selection can introduce noise and degrade the performance. nmn avoids these pitfalls. with only a small set of pre-aligned entities as training data, nmn chooses the most informative neighbors for entity alignment. graph neural networks. gnns have recently been employed for various nlp tasks like semantic role labeling @xcite and machine translation @xcite . gnns learn node representations by recursively aggregating the representations of neighboring nodes. there are a range of gnn variants, including the graph convolutional network (gcn) @xcite , the relational graph convolutional network @xcite , the graph attention network @xcite . giving the powerful capability for modeling graph structures, we also leverage gnns to encode the structural information of kgs (sec. 3.2). ## our approach formally, we represent a kg as @xmath0, r, t ), where e, r, t denote the sets of entities, relations and triples respectively. without loss of generality, we consider the task of entity alignment between two kgs, g 1 and g 2 , based on a set of pre-aligned equivalent entities. the goal is to find pairs of equivalent entities between g 1 and g 2 . ## conclusion we have presented nmn, a novel embedded-based framework for entity alignment. nmn tackles the ubiquitous neighborhood heterogeneity in kgs. we achieve this by using a new sampling-based approach to choose the most informative neighbors for each entity. as a departure from prior works, nmn simultaneously estimates the similarity of two entities, by considering both topological structure and neighborhood similarity. we perform extensive experiments on real-world datasets and compare nmn against 12 recent embedded-based methods. experimental results show that nmn achieves the best and more robust performance, consistently outperforming competitive methods across datasets and evaluation metrics.