Hierarchical Matching Network for Heterogeneous Entity Resolution

1 Introduction

Entity resolution (ER) aims to identify entity records referring to the same real-world entity from different data sources, which is important in data cleaning [Chaudhuri et al., 2007], data integration [Sehgal et al., 2006] and knowledge graph integration [Kong et al., 2016]. For example, in Figure 1 the two records fromWalmart and Amazon refer to the same product, and knowing this fact can help in product search, product recommendation, etc.

Currently, most existing ER approaches rely on the assumption that all entity records to be resolved are homogeneous, i.e., they consist of the same attributes. Based on this assumption, given two entity records, typical ER approaches first compare values between aligned attributes, then aggregate comparison results of all attributes to make the final ER decision [Benjelloun et al., 2009; Mudgal et al., 2018; Bhattacharya and Getoor, 2007; Mudgal et al., 2018; Bhattacharya and Getoor, 2007; Ailon et al., 2008]. Take the two entity records in Figure 1 as an example, the similarities between their aligned attributes (e.g., < title, description > and < price, retailprice >) will be first computed independently and then aggregated to predicate whether they refer to the same laptop bag.

* Corresponding author.

The above entity homogeneity assumption, unfortunately, often suffers from schema heterogeneity and dirty data problems when applied to real-world scenarios:

Schema heterogeneity. In many ER problems, entities usually come from different sources and are represented using heterogeneous schemas, i.e., they have different attributes. For instance, the first product e1 in Figure 1 is described using attributes {title, category, type, price}, and the second one e2 uses different attributes {description, brand,model, retailprice}. To enable aligned attribute-based approaches to these heterogeneous entity records, an additional schema matching step is needed to align attributes [Rahm and Bernstein, 2001; Bilke and Naumann, 2005]. However, due to the complex relationships between heterogeneous attributes, schema matching is not a trivial task. For instance, there are three types of attribute alignments in Figure 1: a) 1-to-1: price in e1 corresponds to retail price in e2; b) 1-to-N: title in e1 corresponds to description and brand in e2; c) N-to-N: category and type in e1 together correspond to brand and model in e2. Furthermore, because schema matching and entity matching are conducted independently, it often results in error propagation and causes difficulty in the global optimization of ER systems.

Dirty data. In real-world datasets, it is very common that attribute values may be redundant, noisy, missing, misplaced, or misspelled - this paper refers it as the dirty data problem. For instance, in Figure 1, model "39203" of the second product entity e2 is misplaced in its title. It is obvious that aligned attribute-based ER approaches can not effectively solve dirty entity resolution problem - by restricting comparison only between aligned attributes, they can not capture evidence across different attributes (e.g., similarity of product model between the entity records in Figure 1), and different attributes can not share and reinforce with each other.

Some recently proposed deep ER models can be directly applied to such heterogeneous and dirty ER scenarios by treating a whole entity record as a sequence of tokens, e.g., DeepER [Ebraheem et al., 2018] and DeepMatcher [Mudgal et al., 2018], but they completely ignore entity structure information which is usually critical for ER task. Seq2SeqMatcher [Nie et al., 2019] is a work specially designed for heterogeneous ER, whose motivation is quite similar to ours. However, it only models structure information by learning an embedding vector for each attribute, and mainly applies them to the token-level matching, therefore also can not make full use of hierarchical structure informations of entities.

To address the above two challenges, this paper proposes a hierarchical matching network (HierMatcher), which can jointly model entity matching at three levels (token, attribute, and entity) in a unified neural framework. At the token level, we construct a cross-attribute token alignment module. By selecting comparison objects for all tokens across all attributes, it can effectively address the schema heterogeneity and the misplaced-type dirty data problems. At the attribute level, we design an attribute-aware attention mechanism, which can learn to identify important information for different attributes, therefore can effectively resolve the redundant-type and noisy-type dirty data problems. Furthermore, by obtaining matching evidence level by level, i.e., aggregating comparison results from token level to attribute level, and then to entity level, our model can fully take advantage of hierarchical structure information of entities. Finally, because all alignment, comparison and aggregation components in our framework are learnable, our model can be globally optimized in an end-to-end way, which prevents the error propagation problem and the local optimum problem.

We evaluate our approach on ten datasets. Experimental results show that, by adaptively selecting cross-attribute matching objects for tokens and effectively identifying important information of each attribute, our method significantly outperforms previous methods on all three kinds of datasets (homogeneous, heterogeneous and dirty).

2 Entity Resolution via Hierarchical Matching Network

This section describes how to resolve heterogeneous entities via our hierarchical matching network model. We first introduce our framework, then present the cross-attribute token alignment module used for selecting the most similar tokens from the other entity, and then describe the attribute-aware attention mechanism used for identifying important information of each attribute. Finally, we describe the entity level matching of our model.

Formally, given two entity records e = {< A11, a11 > , . . . ,< A1m, a1m >} and e′ = {< A21, a21 >, . . . ,< A2n, a2n >} respectively from two data sources E and E′ , with heterogeneous attributes {A11, A12, . . . , A1m} and {A21,A22, . . . ,A2n}, where each attribute value aij is a token sequence, our entity matching model aims to predict the probability that e and e′ refer to the same entity P(y = 1|e, e′ ). Because the size of record collections can be very large (e.g., Amazon contains millions of products), a complete ER system usually performs an additional blocking step to find candidate pairs, which has been extensively studied and well addressed [Christen, 2011; Kenig and Gal, 2013; Papadakis et al., 2016]. Like previous entity matching studies [Mudgal et al., 2018; Fu et al., 2019], this paper focuses on entity matching and will not describe blocking.

2.1 Hierarchical EntityMatching Framework

Our neural entity matching framework is shown in Figure 2. Given two heterogeneous entity records, we first encode all attribute values via a bi-directional RNN (representation layer), then align and compare all tokens via a cross-attribute token alignment module (token matching layer), and then perform attribute level comparisons employing an attributeaware attention mechanism (attribute matching layer), finally aggregate all attribute level comparison results to get entity level matching evidence and make the final ER decisions (entity matching layer). In following we describe our framework layer by layer.

Representation Layer. In this layer, we take each attribute value as a token sequence and get an embedding vector and a contextual vector for each token. Formally, given an attribute value a with tokens wt, t ∈ [1, T ], where T is the token number of a, we first represent each token as a pre-trained embedding vector xt ∈ Rd , then utilize a bi-directional GRU (BiGRU) [Cho et al., 2014] to incorporate their contextual information. We denote hidden state at the tth time-step of the BiGRU as ht ∈ R2u , where u is the hidden size, and take it as contextual vector representation of wt.

TokenMatching Layer. Given an attribute value, this layer first aligns all tokens it contains using a cross-attribute alignment module, then compare each token with its aligned token from the other entity. In this way, alignment of each token may come from any attribute of the other entity. Therefore, schema homogeneity constraint existed in previous aligned attribute-based approaches can be broken here. Details of this layer will be described in Section 2.2.

Attribute Matching Layer. This layer aggregates all token level comparison results of each value to generate its attribute level matching evidence using an attribute-aware attention mechanism, which can adaptively identify important information for each attribute. Details of this layer will be described in Section 2.3.

Entity matching Layer. In this layer, we first concatenate all attribute level comparison results of e and e′ into a comparison vector, and make final decisions based on it using a neural network layer. The output of this layer is the matching probability P(y = 1|e, e′ ), where y = 1 indicates that e and e′ refer to the same entity. Details of this layer will be described in Section 2.4.

Model Learning. Given a training set D that contains a set of training instances (ei, e′i , yi), where ei and e′i are a pair of entity records and yi ∈ {0, 1} is the golden label, we train our model by minimizing the cross-entropy loss:

where |D| is the number of training examples, and p is the probability of yi output by our model.

We can see that, the proposed framework models all token level alignment, hierarchical comparison and aggregation as learnable neural layers in a single neural network. The main advantage of our framework is that all components can be learned end-to-end, allowing for easy global optimization of the ER framework.

2.2 TokenMatching via Cross-Attribute Alignment

In heterogeneous and dirty entity records, corresponding information of one attribute may be scattered in multiple attributes of the other entity. For example, the brand attribute of e2 in Figure 1 consists of two types of information: product category and brand information, which are correspondingly contained in the category attribute and type attribute of e1. It means that, to obtain an accurate comparison object of an attribute value, we must look over the whole entity, instead of only one specific attribute. To this end, we design a cross-attribute token alignment module, which uses a global selection mechanism to select the most similar token from the other entity for each token.

Take the tth token w1it of the ith attribute value in entity record e as an example, let its contextual representation be h1it ∈ R2u , and let contextual representation matrix of record e′ be H2 ∈ R2u×Q, where Q is the total number of all tokens in e′ and therefore each column of H2 represents contextual representation of a token. Via an elementwise absolute difference comparison operation, we first compare w1it with all tokens in entity e′ to get a compare matrix C1it ∈ R2u×Q:

where the outer product (. ⊗ eQ) produces a matrix by repeating the vector on the left for Q times. Then we feed the compare matrix through a two-layer HighwayNet [Srivastava et al., 2015], and transform the outputted matrix G1it ∈ R2u×Q to an attention vector v1it ∈ RQ using a linear layer followed by a softmax function:

where w ∈ R2u and b ∈ R1 are parameters to be learned. After that, we transform the attention vector to a one-hot selection vector s1it ∈ RQ by an element-wise function f which assigns 1 to s1it[l] if v1it[l] == max(v1it), otherwise 0:

Finally, we can use the global selection vector s1it to pick out the aligned token for w1it, and take its final token level matching result as:

We can see that, no matter how complex the relationships between attributes are, or whether values are misplaced, by using the above cross-attribute token alignment module, we can adaptively get suitable matching object for each attribute, therefore can effectively address the schema heterogeneity and misplaced-type dirty data problems.

2.3 Attribute Matching via Attribute-aware Attention

Given results output by the token matching layer, we can match each attribute via effectively aggregating comparison results of all its tokens. One main challenge for attribute matching is that, the importance of different tokens in the same attribute are usually different, therefore their comparison results should be assigned different weights when being aggregated. Take the brand value of e2 in Figure 1 as an example, its token "Microsoft" describing brand information is much more important than the other two ("Bags" and "cases"), which are used to describe the product category information. Furthermore, the dirty data problem may make some attribute values contain amounts of misplaced, redundant or noisy information, therefore how to denoise such attribute values is critical for entity resolution.

Inspired by the sentence level attention in [Yang et al., 2016], we design an attribute-aware attention mechanism to address the above challenge. Our proposed attribute-aware attention mechanism can effectively identify important information for each attribute value. Specifically, we learn a context vector for each attribute, and model the importance of all tokens as their similarities with the context vector. One such context vector can be seen as a high-level representation of a query "what is the informative token in this attribute".

Formally, given an attribute value a1i of entity record e with T tokens. On basis of its token level comparison results output by the previous token matching layer, we compute the attribute level comparison result of a1i as a weighted sum of comparison results of all its tokens:

where r1it is the comparison vector of the tth token w1it, and α1it is an attention score representing the importance of w1it. In this paper, α1it is obtained as:

where pit ∈ R2u is the context vector of attribute A1i, it is randomly initialized and jointly learned during training.

We can see that, by learning to assign more weights to important tokens, the proposed attention mechanism can reduce the influence of redundant and noisy information, therefore can effectively relieve the dirty data problem.

2.4 Entity matching Layer

Because heterogeneous entity records consist of different attributes, we need to aggregate attribute level comparison evidence from both entity records to make final ER decisions. Formally, to determine whether entity records e and e′ match, in this layer, we first concatenate all their attribute level comparison results as a 2u(m + n) dimension evidence vector:

then feed r into a two-layer fully-connected ReLU HighwayNet followed by a softmax layer, which outputs the matching probability P (y = 1|e, e′ ).

3 Experiments

In this section, we evaluate our method and compare it with previous methods. Our code is freely available online 1 .

1 https://github.com/cipnlu/EntityMatcher

3.1 Datasets

We conduct experiments on ten datasets of three types, whose statistics are shown in Table 1:

• Four homogeneous datasets: Walmart-Amazon1, Amazon-Google, DBLP-ACM1, and DBLP-Scholar1, which are commonly used real-world datasets. Because this paper focuses on entity matching, we use their afterblocking versions provided by Mudgal et al. [2018].
• Three dirty datasets: Walmart-Amazon2, DBLPACM2, and DBLP-Scholar2, which are individually derived from Walmart-Amazon1, DBLP-ACM1, and DBLP-Scholar1 by randomly moving the value of each attribute to attribute title in the same tuple with 50% probability. These datasets are also provided by Mudgal et al. [2018].
• Three heterogeneous datasets: Walmart-Amazon3, Walmart-Amazon4, and Walmart-Amazon5, which are all pseudo datasets derived from Walmart-Amazon1 using different attribute merging operations. Specifically, for Walmart-Amazon3, we merge brand and model attributes of entities from Walmart to get a new attribute brand-model. For Walmart-Amazon4, we further merge the category and brand of entities from Amazon to get a new attribute category-brand on basis of WalmartAmazon3. For Walmart-Amazon5, we merge the category and model of entities from Amazon to get a new attribute category-model on basis of Walmart-Amazon3. After the above operations, there are respectively 1-to-2, 2-to-2 and 2-to-2 attribute corresponding relations in the three datasets.

3.2 Baselines

Four baselines are used in our experiments:

• Magellan: A state-of-the-art non-deep learning ER baseline proposed by Konda et al. [2016]. In this paper, We use its performance on all homogeneous and dirty datasets reported by Mudgal et al. [2018].
• DeepMatcher: A deep ER framework proposed by Mudgal et al. [2018], which consists of three modules: attribute embedding, attribute aimilarity representation and classifier. For the homogeneous and dirty datasets, we use its performance from Mudgal et al. [2018]. For the heterogeneous datasets, We use the performance from its implement in the open-source deepmatcher Python package.
• MPM: A deep ER model used for resolving attribute aligned entities proposed by Fu et al. [2019], which can adaptively select optimal similarity measures for heterogeneous attributes in an end-to-end way.
• Seq2SeqMatcher: A deep model proposed for heterogeneous ER tasks [Nie et al., 2019], which models ER as a token-level sequence-to-sequence matching task. We re-implement this model and use it for Amazon-Google and the three heterogeneous datasets in our experiments.

3.3 System Settings

We use two model settings in our experiments:

• HierMatcher-ave: A variant of our model, which does not distinguish the importance of different tokens when conducting the attribute level comparison. Given all token level comparison vectors of an attribute, it simply performs an element-wise average operation to get the final attribute comparison result.
• HierMatcher: The full entity matching model proposed in this paper, which uses the attribute-aware attention mechanism to identify important information for each attribute. Given all token level comparison results, it performs a weight-sum operation to get the final attribute level matching evidence.

For our systems, we use the pre-trained FastText 300dimensional word embedding [Bojanowski et al., 2017] and fix the embeddings during training. The hidden size of each GRU layer is set 150. For model learning, we use the same 60%/20%/20% train/dev/test split as in [Mudgal et al., 2018], and use Adam algorithm for optimization. Following previous studies, we evaluate all systems using precision (P), recall (R), and F1 score, and F1 is used as the primary measure.

3.4 Overall Results

The performance of our models and all baselines are shown in Table 1. From the table we can see that:

• By performing hierarchical cross-attribute entity matching, our model can effectively solve the schema heterogeneity and dirty data problems in ER. Specifically, compared with the state-of-the-art aligned attributebased baselines (Magellan, DeepMatcher and MPM), our best system HierMatcher achieves 15.4 and 5.1 average F1 score improvements correspondingly on the heterogeneous and the dirty datasets. Even compared with Seq2SeqMatcher model, which is also specially designed for heterogeneous ER, HierMatcher achieves 6.1 and 0.1 average F1 score improvements correspondingly on the heterogeneous and the dirty datasets. This is mainly because, via cross-attribute token alignment, our model can adaptively obtain the optimal matching

object for each attribute value, even if it is misplaced or broken into multiple parts, which are respectively distributed in different attributes. Furthermore, by employing a three-level hierarchical matching strategy, our model can make full use of entity structure information.

• Due to the prevalence of dirty data (redundant, noisy, etc.) in real-world applications, effectively identifying important information for each attribute is critical for entity resolution. Compared to the full model HierMatcher, our HierMatcher-ave system gets large performance declines on all three types of datasets. Specifically, because of treating all tokens equally when aggregating their comparison results, HierMatcher-ave gets 2.6, 2.8, and 13.0 average F1 score reductions correspondingly on the homogeneous, dirty, and heterogeneous datasets. We can see that, the performance declines on the dirty and the heterogeneous datasets are larger than on the homogeneous datasets, this is because their entity records are dirtier. Especially for the three heterogeneous datasets, tokens in their merged attribute values may seriously interfere with each other, therefore can result in large performance decline. The above results further demonstrate the necessity of our attributeaware attention mechanism in entity resolution tasks.
• Our matching model is quite robust in multiple types of entity resolution scenarios. We can see that, even without using explicit attribute alignment information, our model can significantly outperform all baselines on the two challenging homogeneous datasets - WalmartAmazon1 and Amazon-Google. Specifically, correspondingly on them, HierMatcher system achieves 8.0 and 4.2 F1 improvements compared with all aligned attribute-based baselines, and achieves 3.4 and 13.7 F1 improvements compared with Seq2SeqMatcher. We believe this is because attribute alignment information of these datasets can be adaptively learned by our model. Besides, there are also some dirty records existed in them, i.e., records with missing, misplaced or noisy values, which can be better resolved by our model. This effectively demonstrates the universality of our approach.

3.5 Detailed Analysis

Effects of the cross-attribute token alignment. In order to illustrate the effect of our cross-attribute token alignment module, we take a pair of entity records < R1,R2 > from heterogeneous dataset Walmart-Amazon5 as an example and display their alignment results in Figure 3. We can see that, although counterparts of some attribute values in R1 are scattered in multiple attributes of the record R2, and there are different attribute corresponding relations (1-1, 1-2, 2-2) between the two records, our cross-attribute alignment module can learn to adaptively get suitable matching object for each attribute value. For example, for the key attribute brandmodel in R1, our model correctly selects "microsoft" from the title of R2 as the alignment of its token used to describe brand information, and selects "39203" from category-model of R2 as the alignment of its token used to describe product model information. The above results further demonstrate the effectiveness of our cross-attribute token alignment module.

Effects of the attribute-aware attention mechanism. To illustrate the effect of our attribute-aware attention mechanism used in the attribute matching layer, we display attention scores of all tokens in an entity record pair < R1,R2 > (the same as the one in Figure 3) from Walmart-Amazon5 in Figure 4. We can see that, by using the attention mechanism, our model can learn to assign higher weights to more important tokens. For example, in the value of category-model, the highest attention (0.95) is assign to the token "39203" representing the model of the product, and attention scores of the two tokens "bags cases" describing product category information are quite close to zero (0.03 and 0.02), this is because product model information in this dataset is much more discriminating for ER task than product category information. This example further demonstrates the effect of our attributeaware attention mechanism in reducing influences of unimportant tokens on attribute level matching results.

4 RelatedWork

Entity resolution (ER) aims at detecting entity records which describe the same real-world object from given datasets. It has been extensively studied since the 1950s [Newcombe et al., 1959], thus a variety of methods for solving the ER problem have been proposed [Doan and Halevy, 2005; Koudas et al., 2006]. The existing ER approaches can be roughly divided into two categories: rule-based, and machine learning-based. Rule-based approaches resolve entity record pairs using matching rules given by domain experts [Hern´andez and Stolfo, 1995] or automatically learned from labeled examples [Chaudhuri et al., 2007; Wang et al., 2011; Singh et al., 2017]. Machine learning (ML)-based approaches usually treat entity resolution as a classification problem [Fellegi and Sunter, 1969]. Traditional ML approaches include SVM-based models [Bilenko and Mooney, 2003], Markov logic-based methods [Singla and Domingos, 2006], active learning-based solutions [Sarawagi and Bhamidipaty, 2002], etc. Recently, some deep learning-base methods were also proposed for ER. One main advantage of such approaches is that they can better capture semantic similarity between textual attributes, and can efficiently reduce human cost in ER pipeline [Ebraheem et al., 2018; Mudgal et al., 2018; Fu et al., 2019; Nie et al., 2019].

Most of existing approaches focus on resolving homogeneous entity records with aligned attributes. When applied to real-world scenarios, such approaches usually suffer from schema heterogeneity and dirty data problems. To address these problems, some methods have been proposed, which includes traditional ML-based approaches [Lin et al., 2019] and recent DL-based models [Ebraheem et al., 2018; Mudgal et al., 2018; Nie et al., 2019]. These approaches either can not handle complex attribute corresponding relations, or can not make full use of entity structure information. Compared with previous studies, by designing a 3-level hierarchical matching framework, our model can not only directly resolve heterogeneous and dirty entities, but also take advantage of hierarchical structure information of entities.

5 Conclusions

This paper proposes a hierarchical matching network for entity resolution, which uses a cross-attribute token alignment module to adaptively compare heterogeneous entities, and employs an attribute-aware attention mechanism to denoise dirty attribute values. Experimental results show that our method outperforms previous methods on multiple types of datasets. In future work, we plan to further take the importance of different attributes into consideration when aggregating their comparison results to make the final ER decisions.

Acknowledgments

This work is supported by the National Natural Science Foundation of China under Grants no. U1936207 and 61772505, the National Key Research and Development Program of China under Grant No.2017YFB1002104, and Beijing Academy of Artificial Intelligence (BAAI2019QN0502).