Entity matching (EM) seeks to match pairs of entity records from (the same or different) data sources that refer to the same real-world entity. EM is very useful in many applications domains, including (a) healthcare, where matching of patient records from different healthcare facilities (e.g., emergency rooms, hospitals, etc.) can be used to determine if they refer to the same real-world person; (b) airline security, where airline passenger records are matched against no-fly list records to identify people who should be prevented from boarding flights or should undergo additional screening; (c) e-commerce, where product records from different retailers' websites can be matched to identify popular products and fraudulent knockoffs; and so on.
EM is a challenging problem that has been extensively investigated for over half a century by different communities, e.g., statistics, databases (DB), natural language processing (NLP), and machine learning (ML), resulting in a variety of techniques proposed in the literature for addressing this problem. These challenges arise because entities in autonomous data sources can be represented in a variety of ways (e.g., highly structured records versus textual descriptions), using different conventions (e.g., the many ways in which person names and postal addresses are represented), data quality issues (e.g., misspellings, missing values), and so on. A consequence is that, despite significant advances in recent years (especially with recent neural techniques like Ditto [36]), EM techniques still result in both false positives (non-matching record pairs that are declared as matches) and false negatives (matching record pairs that are declared as non-matches). These errors can have serious consequences in practice, as seen in the following examples.
Example 1: (No-fly list) Consider the airline security application, which aims to identify passengers that are likely to be dangerous (e.g. terrorists) for screening and potentially preventing them from boarding the flights. Using a dataset of criminal records called the no-fly list, passenger names (and other information) are matched against the no-fly list for this purpose. False positives in airline security can lead to significantly inconveniencing passengers. On the other hand, false negatives can result in known terrorists being permitted to board flights with undesirable consequences. Due to historical biases, the no-fly list datasets could over-represent some minority groups in comparison to society's population distribution. This, as we shall evaluate in our experiments, can result in higher false positive rates for those demographic groups. Another potential issue is that some demographic groups have more similar names. Hence, passengers from those groups may have a higher chance of having the same or similar information to those of known terrorists, which in turn will cause higher false positive rates for them. □ In Example 1, getting (falsely) matched is harmful. We next show an example where not getting matched can be harmful.
Example 2: (High-value customers list) Upselling to potentially high-value customers is critical for many businesses such as the fashion industry, airlines, and tourism. Suppose business 𝐴 acquires a list 𝐿 of names of high-value customers from other businesses. Business 𝐴 uses EM techniques to match its own customers against list 𝐿 and sends exclusive offers to upsell to the matching cases in order to prioritize them. Unlike the previous example, in this case, over-representation in the high-value customer's list 𝐿 is beneficial. However, unlike the no-fly list, the privileged group(s) are likely to be over-represented and minority groups under-represented in the list 𝐿. As a result, a lower (true and false) positive match rate is expected for minority groups and they end up receiving fewer exclusive offers, resulting in biased advertising [4,9,40].
□ When such disparities (e.g., false positives) occur in a systematic way for some demographic (sub-)groups, thereby disadvantaging them over others, concerns about the fairness of EM techniques arise. While the fairness of ML models has been the topic of much recent work in the literature [12,23,25,25,28,34,61,62,64], not much attention has been paid to the fairness of EM techniques.
In this paper, we seek to address this gap in the literature and perform an extensive experimental evaluation and analysis of a variety of EM techniques on a range of datasets through the fairness lens. Traditionally, blocking may precede matching to reduce the space of possible matching candidates from quadratic to subquadratic, e.g., linear. A rich body of research focuses on blocking algorithms [19,35,46,47]. In this paper, our goal is to audit offthe-shelf entity matching systems used in practice. As such, our evaluation and analysis are performed on end-to-end matching systems which may include their own built-in blocking algorithms.
In summary, we make the following technical contributions in this paper:
• Given the pairwise nature of EM, we propose the use of single fairness and pairwise fairness to evaluate entity matchers. We adopt 11 popular fairness measures from the literature for this task and analyze their suitability for EM. • We select a suite of 13 EM techniques (including 1 declarative rule-based technique, 7 non-neural ML techniques, and 5 neural ML techniques) and 6 benchmark datasets (including 2 structured datasets, 2 textual datasets, and 2 dirty datasets) that have been used in prior work on entity matching for fairness evaluation. Using publicly available individual-level data, we also created and used two semi-synthetic matching social datasets for fairness evaluation. These datasets are shared publicly as benchmarks for auditing the fairness of matchers. • We evaluated all combinations of EM techniques, datasets, and fairness measures and analyzed the outcomes. We classified the results into four cases based on whether an (EM technique, dataset, or fairness measure) yielded (i) accurate or inaccurate matching results, and (ii) fair or unfair matching results. Some of our findings in this study are as follows:
ś Our results on social data confirm matching unfairness when (i) there are higher similarities among records of a certain group, (ii) the representation of demographic groups in data is biased. ś Our results underscore that responsible EM requires training data that is representative of different possibilities from various (demographic) groups. ś While different fairness measures are valuable for different settings, due to the class-imbalance property of EM, measures such as positive predictive value parity and true positive rate parity are more capable of revealing EM unfairness. ś Significantly relying on proxy attributes such as name, can cause unfairness in non-neural models. On the other hand, relying on pre-trained language models and embeddings, or not fully considering the dataset structure can cause unfairness in neural matchers. We use our findings and lessons learned to put together a set of rules of thumb for responsible entity matching (Table 8).
Fairness in entity resolution (ER) has briefly been studied in the literature. In [24], a constraint-based formulation for fairness is proposed to mitigate bias in ER tasks by ensuring that all (sub-)groups have the same opportunity to be resolved. Furthermore, [38] proposes a (sub-)group-based training for different ethnicities in order to increase both accuracy and fairness in SVM-based ER which is consistent with our suggestion to use ensemble learning for EM. Finally, in a parallel work [43], the authors propose an AUCbased fairness definition for EM and ER tasks and try to resolve the bias issues through a data augmentation solution. To the best of our knowledge, we are the first to comprehensively audit off-the-shelf entity matching models for fairness and propose proper measures, datasets, and comparison angles fitting the problem settings given the inherent differences with typical machine learning tasks.
Given two sets of records 𝐴 and 𝐵, the EM problem is to identify all correspondences between record pairs in 𝐴 × 𝐵 that correspond to the same real-world entity. A correspondence 𝑐 = (𝑒 𝑖 , 𝑒 𝑗 , 𝑠) interrelates two records 𝑒 𝑖 and 𝑒 𝑗 with a confidence value 𝑠 ∈ [0, 1] that indicates the similarity of 𝑒 𝑖 and 𝑒 𝑗 or the confidence of a matcher about 𝑒 𝑖 and 𝑒 𝑗 referring to the same entity [33]. To decide whether the record pair of 𝑐 = (𝑒 𝑖 , 𝑒 𝑗 , 𝑠) is a match or non-match, matchers often apply a threshold on 𝑠 [11,60]. We decouple the choice of a threshold from the outcome of the matching and consider the outcome of an EM task as pairs of matching and non-matching records. Formally, we consider the following EM problem: Definition 1 (Entity Matching Problem). Consider two sets of records 𝐴 and 𝐵. For every pair of records (𝑒 𝑖 , 𝑒 𝑗 ) ∈ 𝐴 × 𝐵, let 𝑦 𝑖 𝑗 be the ground-truth label indicating if 𝑒 𝑖 and 𝑒 𝑗 refer to the same entity. Given all pairs (𝑒 𝑖 , 𝑒 𝑗 ) ∈ 𝐴 × 𝐵, the EM problem is to predict 𝑦 𝑖 𝑗 with a label ℎ 𝑖 𝑗 . That is, ℎ 𝑖 𝑗 refers to the decision of the matcher about the label of 𝑒 𝑖 and 𝑒 𝑗 (match or non-match).
In a fairness-sensitive setting, records are accompanied by sensitive attributes (e.g. gender, country, race, etc.). Let A = {𝐴 1 , . . . , 𝐴 𝑛 } be the sensitive attributes, 𝑑𝑜𝑚(𝐴 𝑖 ) be the domain of 𝐴 𝑖 , and G = {𝑔 1 , . . . , 𝑔 𝑚 } be the set of all groups of interest, i.e. G = ⋃︁ 𝐴 𝑖 ∈ A 𝑑𝑜𝑚(𝐴 𝑖 ). The mapping 𝐿(𝑒 𝑖 ) relates a record to its associated groups 𝐺 𝑖 ⊆ G. In other words, 𝐺 𝑖 is the group that 𝑒 𝑖 belongs to. Given two sets of records 𝐴 and 𝐵 and the set [(𝑒 𝑖 , 𝑒 𝑗 , 𝐺 𝑖 , 𝐺 𝑗 , ℎ 𝑖 𝑗 , 𝑦 𝑖 𝑗 )] ∀ (𝑒 𝑖 ,𝑒 𝑗 ) ∈𝐴×𝐵 , we would like to audit the fairness of a matcher with respect to groups.
3.2.1 Group Selection. The first step in auditing an entity matcher for fairness is identifying meaningful (sub-)groups in sensitive attributes. An input dataset to a matcher M includes record ids, the value ((sub-)group) of each record for sensitive attributes, the decisions of M, as well as true labels for the record pairs. Depending on the type, cardinality, and the number of sensitive attributes, multiple fairness cases may happen that are presented in Table 1.
The space of groups for a single attribute with binary or multiple values is the domain of the corresponding attribute. In multipleattribute settings, we can define intersectional subgroups, as the cartesian product of group values. More details about intersectional subgroups are provided in the technical report [50].
. Given the pairwise nature of EM tasks, there are two ways to audit entity matchers: We consider the EM task to be symmetric in single and pairwise fairness definitions. We remark that these definitions can be extended to ordered single and ordered pairwise fairness where the groups are defined on left or right records. In this paper, we focus on non-directional single and pairwise fairness.
The correctness of a matcher measures how well its matching predictions conform with the ground-truth. Given a test dataset with correspondences of 𝑡 = (𝑒 𝑖 , 𝑒 𝑗 , ℎ, 𝑦), where ℎ is a binary variable indicating the result of EM (match or non-match) for records with encodings 𝑒 𝑖 and 𝑒 𝑗 , and 𝑦 is a binary variable indicating the groundtruth for matching, we profile predictions of ℎ using the numbers of true positives (TP), true negatives (TN), false positives (FP), and false negatives (FN), respectively. Unlike a classification task, in the confusion matrix of a matching task, the result is counted both for the group(s) of 𝑒 𝑖 and the group(s) of 𝑒 𝑗 . For further explanations, please refer to the technical report [50].
Similar to many of the existing works on algorithmic fairness and responsible data science [5,15,16,25,28,42,52,54], we use the terms bias and unfairness interchangeably to refer to when a matcher is not fair. At a high level, fairness definitions can be viewed from three perspectives: group, subgroup, and individual fairness [12]. The most granular notion of fairness is individual fairness that requires similar outcomes for similar individuals [23]. The more popular perspective of fairness, (sub)group fairness, requires similar treatment for different (sub)groups. A model/algorithm satisfies some fairness constraints if it has equal or similar performance (according to some fairness measure) on different (sub)groups. The focus of this paper is on (sub)group fairness. Most of the group fairness measures belong to one of the following four categories [6,12].
(1) Independence requires independence of analysis outcome from demographic groups. (2) Separation requires independence of the outcome from demographic groups conditioned on the target variable. (3) Sufficiency requires independence of the target variable from demographic groups conditioned on the outcome. (4) Causation requires that in a counterfactual world, the decision would not change had the individual belonged to a different demographic group. We do not consider Causal fairness in our audit. In Table 2, we present our suite of fairness measures, adapted from the notions of fairness in classification [12], for auditing an entity matcher M for a set G of (sub)groups.
Depending on the context of an EM task at hand, proper fairness measures should be employed. Besides, a major difference between EM and regular classification tasks is that the input to EM tasks is a pair of records. Due to its pairwise matching nature, class imbalance is a distinguishing property of EM, compared to regular classification tasks. To better explain this, let us consider a toy example, where two data sources 𝐷 and 𝐷 ′ contain exactly the same set of 𝑛 records. Each pair of records 𝑒 ∈ 𝐷 and 𝑒 ′ ∈ 𝐷 ′ is passed as an input to an entity matcher. In this setting, only 𝑛 of the 𝑛 2 pairs are matches, and the others are non-matches. In other words, the probability a random pair is a match is as low as 1 𝑛 . Class imbalance is also a challenge in some of classification problems but the degree of imbalance is often constant while in EM tasks, it is as high as 𝑂 (𝑛). Indeed, blocking techniques [46] can help in reducing the extreme class imbalance. Even after blocking, a high class imbalance is expected for EM tasks.
Guide for Practitioners: Let us consider the fairness measures in Table 2. Which measures to choose depends on the downstream task and the problem context. Therefore, practitioners should choose measures depending on the importance of TPs (true match), FPs, FNs, and TNs in the problem context. For example, among the fairness measures, statistical parity does not consider the groundtruth labels and requires equal match ratios from different groups, independent of whether they really are a match or not. As a result, this measure does not seem reasonable for deduplication tasks using EM. On the other hand, it may be useful to ensure equal representation of different groups when using EM for joining tables.
When the input to the EM task is imbalanced and most of the pairs are non-matches, some measures are more capable of revealing the unfairness of matchers. First, note that even a matcher that marks all pairs as non-matches has high accuracy in this setting. Subsequently, accuracy parity may not reveal the unfairness. Similarly, measures such as FPRP and TNRP may fail to reveal unfairness in detecting true matches. In these settings, the fairness measure for successfully discovering these events is Positive Predictive Value Parity (PPVP). Another important measure in this context is True Positive Rate Parity (TPRP), a.k.a Equal Opportunity, which focuses on correct match predictions among the (rare) true
Groups could be either one or attributes: genre and gender a combination of the three cases above. group(e) = {male-Pop, male-Rock, male-Jazz} Table 2: Fairness measures. ℎ(𝑒, 𝑒 ′ ) is the output of a matcher M (match ('M') or non-match ('N')) and 𝑦 is the ground-truth.
Description Equation (∀𝑔 𝑖 ∈ G)
Accuracy Parity (AP) requires the independence of matchers's accuracy from groups 𝑃𝑟 (ℎ (𝑒,
Statistical Parity (SP) requires the independence of the matcher from groups
foot_0 True Positive Rate a.k.a Equal Opportunity; in the group of true matches
requires the independence of match predictions from groups False Positive Rate in the group of true non-matches, requires
the independence of match predictions from groups 1 False Negative Rate in the group of true matches, requires
the independence of non-match predictions from groups
True Negative Rate in the group of true non-matches, requires
the independence of non-match predictions from groups 1 Equalized Odds (EO) in both groups of true matches and true non-matches the independence of true non-matches from groups 1 False Omission Rate among the pairs predicted as non-match, requires
the independence of true matches from groups matches. These recommendations are consistent with our comprehensive experiments on several data sets, in ğ 5, where PPVP and TPRP were the two measures that could reveal the unfairness of the matchers. We also note that some of the measures cannot be applied in pairwise fairness scenarios where conceptually, the equality of groups restricts matching results. In some scenarios, two records with different groups can never be considered match in the ground-truth. For instance, in a matching task defined between DBLP and ACM publications, two records with different venues (after standardization) are never a true match. More concretely, when pairwise fairness is evaluated on non-overlapping groups, TPs and FNs are always zero; hence, measures based on TPs and FNs become inapplicable.
Consider a fairness notion and a group 𝑔 𝑖 ∈ G. In a perfect situation, the matcher should satisfy the parity (equality) between two probabilities in the following form:
where 𝛼 and 𝛽 are specified by the fairness measure. For example, for Positive Predictive Parity, 𝛼 is 𝑦 = '𝑀' and 𝛽 is ℎ(𝑒, 𝑒 ′ ) = '𝑀'. On the other hand, due to the trade-offs [31] between different fairness notions and the impossibilities theorems [18], it is often not possible to satisfy complete parity on all fairness measures. As a result, the objective is to make sure that disparity (also known as unfairness) is less than a given threshold for a matcher to be fair. Given a fairness notion and a group 𝑔 𝑖 ∈ G, one way to compute disparity is to use subtraction [13], as follows.
𝐹
For example, for accuracy parity (𝛼 is ℎ(𝑒, 𝑒 ′ ) = 𝑦 and 𝛽 is null), the disparity can be computed as follows.
Alternatively, given a fairness notion and a group 𝑔 𝑖 ∈ G, the disparity can be computed using division [25] , as follows.
Guide for Practitioners: When evaluating the unfairness of a matcher, the objective is to determine whether unfairness is less than a given threshold. For example, the 20% rule [25] suggests the threshold as 0.2. Note that if the accuracy for the group 𝑔 𝑖 is higher than the average accuracy of the matcher, it is not considered as unfairness. Also, note that Equation 1 considers the higher the probability, the better. Depending on fairness measures (and application), the direction may be as the lower the probability, the better. For example, for FNRP, a lower probability of a false negative is preferred. For such cases, one should consider
As a result, for false negative rate (𝛼 is ℎ(𝑒, 𝑒 ′ ) = '𝑁 ' and 𝛽 is 𝑦 = '𝑀') the disparity can be computed as
Similar to Equation 1, Equation 3 also considers the higher the probabilities the better. For the cases (such as FNRP or FDRP) where the lower probabilities are better, one should swap the numerator and the denominator in the equation. Therefore, for false discovery rate (𝛼 is 𝑦 = 0 and 𝛽 is ℎ(𝑥) = 1) the disparity can be computed as
Our proposal in this paper is agnostic to the choice of operation for computing the disparities. Still, in our experiments, without any preference, we use subtraction to compute the disparities.
The existing techniques for EM fall into one of the following three categories: 1) declarative rule-based, 2) ML-based, and 3) crowdsourcing-based approaches. The last class of techniques relies on crowd-worker knowledge for EM tasks and we do not include them in our analysis. From each of the remaining categories, we select a few important matchers to be assessed for fairness. The specifications of the evaluated matchers are presented in Table 3.
Rule-based approaches perform EM based on the conjunction/disjunction of a few logical predicates, each specifying a matching condition. Each matching condition consists of a similarity measure (e.g., Hamming, cosine, Levenshtein, Jaccard, etc.) computed between record pair columns, a comparison operator (e.g., <, =, >), and a threshold value specifying the similarity value. Rule-based matchers are scalable to large settings and provide results that are explainable. However, they highly depend on human experts with relevant domain knowledge to assist with rule specification. For more information on rule specification in EM, we would like to direct the reader to [44,45,53,56].
A crucial part of rule-based matching that affects the overall correctness of the task is the selection and configuration of the rules used for comparison. This task is difficult and laborious even for domain experts. ML-based supervised EM approaches reduce the associated manual labor by benefiting from the training data at hand. They significantly reduce the rule discovery efforts by extracting fitting parameters (e.g., model weights) from the data. However, preparing the training data itself imposes an additional cost. Furthermore, such techniques are computationally expensive (demanding a blocking phase to reduce the search space) [33] and are less explainable on account of using black-box classification methods [10,57]. Depending on the employed classification technique, ML-based matchers belong to one of the non-neural or neural categories.
Matchers. This category of matchers uses traditional ML algorithms such as decision tree, SVM, etc., to decide whether or not a pair of records is a match. Since the number of meaningful insights that can be extracted from data and fed as features to the learning algorithm are limited to word-level similarity metrics and TF-IDF scores, non-neural matchers may not perform well for cases where datasets are less structured, and column values are more in a textual format consisting of long spans of text.
shown promising results in NLP applications. Due to the growing demand for matching textual data instances, it only makes sense to adopt such techniques where the other approaches usually fall short. Deep learning methods transform text into numerical values using character/word embeddings often through pre-trained embedding models such as word2vec [39], GloVe [48], fastText [14]. Due to the sequential nature of text, to better capture the semantics of the data, sequence models such as RNN and its variants (e.g., LSTM, GRU, etc.), where prior sequences of inputs can affect the current input and output, are utilized [11]. Further improvement mechanisms such as attention [55], pre-trained language models [21], domain knowledge injection, data augmentation, summarization, etc., deliver further insights into the models to make better matching decisions. The superiority of neural matchers for textual and dirty data sets has been pointed out in the existing research [41]. However, there are associated challenges, such as high computation costs and large training data requirements, making them not suitable for every EM scenario.
To evaluate the matchers for fairness, we investigate the performance of matchers in terms of single and pairwise fairness for all valid groups in the datasets w.r.t. a variety of fairness definitions. To present a side-by-side comparison and visualization, we aggregate the results based on the dataset and the type of fairness (i.e., single and pairwise). Next, we look into some of the identified discriminated groups from different settings and investigate the reasoning behind the unfair behavior of matchers. 5.1.1 Experimental Settings. We conducted the experiments on a 3.5 GHz Intel Core i9 processor, 128 GB memory, running Ubuntu. The evaluation framework was implemented in Python. We accessed the source code of the entity matchers either through the authors' public GitHub or by directly contacting the authors. 5.1.2 Social Datasets. The concept of fairness holds significant societal implications and carries more significance when studied on the individual records. Unfortunately, public access to such data, especially demographic information, is restricted owing to privacy concerns. Therefore, we construct semi-synthetic datasets based on two publicly available real-world datasets CSRankings and Compas [2]. We selected these datasets based on our airline security example discussed in the introduction. Particularly, we want to evaluate the fairness of the matchers under two conditions: (a) when two demographic groups have different degrees of similarities in their names, and (b) when there is an over-representation of some groups in the data. CSRankings 2 is a global ranking system that evaluates computer science departments based on the scholarly research activities of their faculty members from universities across the world.
CSRankings dataset is publicly available [3]. For each faculty, in addition to their names, the dataset contains other information such as affiliation country. Having observed various name similarities between different geographical regions, we found this dataset as a good candidate for evaluating (a). Compas, on the other hand, is a public dataset of criminal records that has been widely used in Fair ML research. In addition to names and other information, the 2 csrankings.org dataset contains demographic information for each individual. The dataset over-represents Black/African-Americans, which makes it a good candidate for evaluating (b).
To create our first EM dataset FacultyMatch based on CSRankings, we do the following stepsfoot_1 : Using fullName and country for matching, we focus on two groups of faculties working in Germany de and China cn. Next, we perform a Cartesian product on the sample and label each pair as a match if left and right records have identical scholarIDs. Finally, we perturb the values of fullName column for the right-side records which involve randomly adding, removing, or replacing a random character in the cell.
Following our motivating example in the introduction, we create NoFlyCompas, a no-fly list scenario based on Compas: First, using firstName, lastName, and race for matching, we focus on individuals that are either Caucasian or Black/African-American. We next create the no-fly list by taking a uniform sample from Compas comprising of 48% Caucasian records and 52% Black/African-American (the distribution of the two groups in the Compas dataset). Then, in accordance with the racial distribution of the U.S. population, as reported by the Census Bureau Data [1], we create a passenger table by taking a sample from Compas that includes 80% Caucasian and 20% Black/African-American individuals. Next, we perform a Cartesian product on the two tables and label each pair as a match if left and right records have identical personIDs. Similar to the process for FacultyMatch, the right records (that correspond to the no-fly list table) undergo perturbation in the firstName and lastName columns. • Structured: In this category of datasets, attribute values are atomic, meaning that they cannot be broken into multiple values. Furthermore, there are no missing values in the data. • Dirty: This category of datasets is similar to structured datasets; however, they include far too many random missing values in their columns. Therefore an attribute value may appear for a record while it does not exist for another one. • Textual: Textual datasets are made of a single attribute per record containing a textual description.
For the completeness of our experiments, we select several datasets from each category on which we evaluate the matchers. The complementary datasets are chosen from WDC [49] and Magellan [41] repositories which are the standard benchmark corpora used in EM literature. Aside from the dataset type, we carefully handpicked the datasets w.r.t. domain, sensitive attribute type, and ground-truth class balance to cover a variety of possible settings. For the textual datasets Shoes and Cameras, we extract the manufacturer of the corresponding product from the description as the sensitive attribute. Table 4 shows the details of the selected datasets.
To cover the breadth of existing methods in our experiments, we picked 13 EM tools from each of the discussed approaches (1 rule-based, 7 non-neural, and 5 neural). The selection criteria included the public availability and error-free execution of the source codes. To ensure the satisfactory performance of the entity matchers, we took the following steps:
BooleanRuleMatcher. We used the automatic feature generation tool provided in the Magellan library to extract features based on the similarity of the columns in the input table w.r.t. multiple distance measures. Next, we handpick some of the generated features based on which we declare matching conditions. For each attribute, the generator creates multiple features based on different distance measures. Depending on the attribute involved in the generated features, we either use the exact match of the attribute values (for attributes with short and atomic values, e.g., year) or choose one of the distance-based features (e.g. cosine similarity between left and right attribute values) with a similarity threshold of greater than 0.5 (for attributes with longer values, e.g., paper title). 4 Non-neural Matchers. For all non-neural matchers except for Dedupe, we used the automatic feature generation tool in the Magellan library. Next, all of the generated features are fed to the models for training. Dedupe's active learning component requires manual labeling of difficult record pairs, which is an uphill task. To bypass this step, we converted the training data into Dedupe's generated 4 Details on the specified rules for each dataset are provided in the GitHub repository. cache file format and utilized the entire training samples to keep the experiment consistent with the other matchers. Finally, Dedupe did not scale for FacultyMatch, NoFlyCompas, Shoes and Cameras.
Neural Matchers. We tuned the hyper-parameters of all the matchers according to their results on the validation set. For Deep-Matcher, HierMatcher, and Mcan we trained the models for 10 epochs with a batch size of 16 and used fastText [14] pre-trained word embeddings. We used the hybrid model of DeepMatcher that reportedly performs better than the other models. For Hier-Matcher, we used the attribute-aware attention mechanism. For Mcan, we utilized self-attention, pair-attention, global-attention, and gating mechanisms that reportedly would achieve the best results. For Gnem, we trained the GCN models for 10 epochs with a batch size of 2 and 768 nodes at each layer. For Ditto, we trained the models for 40 epochs with a batch size of 64 while using the DistilBERT language model and optimizations such as data augmentation, sequence summarization, and domain knowledge injection.
For all datasets except Cricket, we declare a pair of records as a łmatchž if the similarity between the two is greater than 0.5. Our choice of threshold value has a probabilistic interpretation of having a higher likelihood of being a match rather than being non-match. In other words, we follow a randomized rounding logic, where non-integer values in range (0, 1) are rounded to the closer integer. Moreover, we empirically observed that a reasonably high accuracy occurs among all the matchers with a threshold over 0.5, as shown in ğ 5.3.4. For the Cricket dataset, however, due to the high similarity of all pairs, we had to choose a higher similarity threshold of 0.9 because otherwise, all of the models would predict all pairs as łmatchž, which would affect the models' correctness. As for the fairness threshold, we follow EEOC's 80% rule [20], that only 20% disparity is tolerated.
NoFlyCompas. We begin our experiments by evaluating matchers' fairness on our NoFlyCompas dataset. Recall that NoFly-Compas dataset is the matching between the no-fly list and the passengers list, where the two lists have different distributions of the demographic groups. In particular, while in the U.S. population (passenger list) the White population (75%) is significantly higher than the Black (13%), in the no-fly list Blacks are over-represented and the White and Black ratios are almost the same. It is common for a no-fly list to suffer from sampling bias. Table 5 includes the breakdown of experiment results. All the non-neural matchers had a perfect prediction performance, meaning that the TPR, FDR, and disparity values were 1.00, 0.00, and 0.00 respectively.
Due to the disjoint nature of the binary-sensitive attribute race in our comparison, single and pairwise fairness results are identical and therefore we only report the single fairness results. The first observation is the superiority of non-neural matchers over neural matchers for this task, both on fairness and the overall performance. The higher performance of these models for structured datasets has previously been reported in [41], where the majority of nonneural matchers performed on par with or outperform the neural matchers. Next, by looking into the neural matchers in Table 5, we see a significant disparity against African-American group. More specifically, in terms of FDR the African-American to Caucasian ratio is between 1.11 to 3.8 (280% larger) across different matchers. This translates to a significantly higher chance of preventing an African-American person to board a flight or enter a country compared to a Caucasian person.
To better illustrate the root cause behind the disparity, let us highlight the following case that is falsely labeled as łmatchž by Ditto:
(left record) firstName: James lastName: Brown race: African-American (right record) firstName: Samanthai lastName: Browne race: African-American Some names are more common within certain demographic groups than others. For example, last names that are very common among black people include Brown, Jackson, Williams, Johnson, etc. Since the no-fly list in our NoFlyCompas dataset over-represents the Black group, for an individual in this group there is a higher chance of getting falsely labeled as a match.
Consider the FacultyMatch dataset described in ğ 5.1.2. There are 2,061 Chinese cn in this dataset compared to 1,595 German de ones. Therefore, when we create the EM dataset by performing the Cartesian product, the group of Chinese faculty members has the larger population in the dataset. To increase the population gap even wider, we remove 80% of the non-match pairs that have a German faculty member either on the right side or the left side. As a result, the number of Chinese pairs becomes more than 6 times the number of German pairs in the final sample ensuring proper representation. Next, using a variety of matchers, we conduct the matching task on the data and audit the matchers for fairness. Table 6 includes the breakdown of experiment results. Overall, non-neural matchers outperform neural matchers in terms of model performance and fairness. Within the neural matchers we observe between 9% to 22% more prone to make an erroneous positive prediction (match) for the cn group. Further investigating the false-positives, we observed that those mostly include names that are very similar in the English transcription. An example of such cases (FP by Ditto) is brought in the following:
(left record) fullName: Qingming Huang country: cn (right record) fullName: Qing-Hu Huang country: cn Furthermore, the models make somewhere between 44% to 75% more mistakes in terms of false-negative predictions for the cn group. Due to the higher degree of similarities in Chinese names, models in general become more sensitive to minor differences and tend to mismatch. An example of such cases is the following:
(left record) fullName: LinLin Shen country: cn (right record) fullName: Linlin phen country: cn More extensive results on the overall performance of the matchers across social datasets are provided in [50].
This section provides a comprehensive evaluation of the matchers' fairness and correctness using the benchmark datasets.
Summary of result: In summary, our results confirm the higher accuracy (ğ 5.3.1) and fairness (ğ 5.3.3) of neural matchers for textual and dirty data (Figure 9), and non-neural matchers for structured data (Figures 4 and5). While heavily relying on problematic proxies hurts the fairness of non-neural matchers, not fully considering the dataset structure and heavily relying on semantic similarities and (biased) pretrained models hurts the fairness of neural matchers. TPRP and PPVP were more capable of revealing matching unfairness (ğ 5.3.2). Finally, we observed a higher fairness sensitivity of neural matchers on matching thresholds (ğ 5.3.4). 5.3.1 Correctness. Due to space limitations, here we present a summary of our correctness results. More extensive results on the overall performance of the matchers across the datasets, fairness and accuracy synergies, and detailed discussions can be found in the technical report [50]. In summary, aligned with [41], throughout our extensive experiments, we observed that neural matchers are more accurate than non-neural matchers on textual and dirty data. Modern neural matchers draw on external knowledge by incorporating language models, which helps a matcher to learn the relevance of records despite the lack of structure and syntactic similarity in text records. This result is consistent with what is reported by the state-of-art matchers. On the other hand, our results corroborate that non-neural matchers are more accurate than neural matchers on structured data. Various combinations of correctness and fairness exist in EM as some matchers have low accuracy and F-1 score, while no unfairness issue is observed. This can be explained by the low accuracy of these matchers for all groups across the board which makes the disparity a low value. In each plot, the x-axis shows the groups (single or pairwise), while the fairness measures are provided in the y-axis. The corresponding marker of a matcher is placed in a specific cell, if that matcher is unfair for the group shown in the cell's column based on the measure in its row. In the majority of our experiments, PPVP and TPRP were the measures that discover unfairness the most across all datasets and matchers. Nevertheless, it is not the case that one measure fits all settings. When data has match/non-match negative imbalance, i.e., the number of matching pairs is much higher than non-matching pairs in the ground-truth, NPVP and FPRP are the most appropriate measures. This is because while the majority of pairs are positive instances, the failure of a matcher in identifying non-matches makes it unfair to certain groups. Consider the Cricket dataset that contains a larger number of pairs of matching cricket batters than non-matching batters. As shown in Figure 7, NPVP allows us to detect the unfairness of a matcher such as LogRegMatcher to left-handed batters due to the large number of FNs generated by this matcher. SP does not consider the ground-truth labels and requires the independence of the matching prediction from the groups. In other words, SP requires equal match ratios from different groups, independent of whether they really are Then, when the ground-truth has (non-)match imbalance for a group, that is, the ratio of matched pairs to unmatched ones, is low, the SP measure falsely identifies a matcher as unfair for that group. An example of this phenomenon can be observed in Figure 4, for French-Pop group in the iTunes-Amazon dataset, where SP unfairness is indeed due to the fact that the ground-truth only contains TNs. Some measures can be explained by others. For example, let us consider the AP unfairness of Gnem on iTunes-Amazon for the group of country genres, including Country, Cont. Country, and Honky Tonk, reported in Figure 4. This matcher has low accuracy for this group of genres because it identifies a small number of true matches (i.e., has a low number of TPs, thus, suffers from TPRP). Instead, the matchers falsely identify many pairs as non-match (i.e., have a high number of FPs, thus, suffer from NPVP). Similarly, we observe that HierMatcher demonstrates AP unfairness on iTunes-Amazon for the group of country genres because it incurs a large number of FPs, thus, suffers from FPRP unfairness.
Single unfairness can potentially propagate to pairwise fairness. In Figure 7 and 8, we observe that the unfairness of LogRegMatcher for the single Left Handed group incurs its unfairness for the pairwise Left Handed-Left Handed groups because most likely only a left-handed batter can be matched with another left-handed batter. 5.3.3 Fairness: Matcher Types. Neural Matchers: Neural matchers demonstrate more unfairness on structured datasets than non-neural matchers, as shown in Figures 4 and5. One reason is that matchers such as Ditto merge the content of different attributes as a single block and use token similarity as a signal for matching. However, for structured data, this technique may lose the important information specified by the structure. In particular, in the following example from Dblp-Acm dataset, the two records have similar titles and are predicted as match despite the fact that they are (i) written by different authors, (ii) published in different venues, and (iii) published in different years.
(left record) title: lineage tracing for general data warehouse transformations; author: jennifer widom , yingwei cui; venue: VLDBJ; year: 2003 (right record) title: data extraction and transformation for the data warehouse; author: case squire; venue: SIGMOD; year: 1995 One of the reasons Ditto was unfair for VLDBJ is that, similar to the following example, it is common to publish extended versions of previously published papers in this venue. As a result, after merging different attributes as a block of text for each record, similar titles and authors may cause enough similarity between the two phrases that the Ditto mistakenly predicts them as a match. External bias could be injected into neural matchers through the use of language models and word embeddings. For example, Hiermatcher uses language models and word embeddings to compare the attribute similarities of records. As a result, it may mistakenly match articles with similar titles. Below is an FP example for Hier-Matcher. Both articles are published in the same year. But they appear in different venues and are written by different authors. Still, language models find sufficient similarity between titles to persuade the matcher to label the records as a match. Perhaps this is because of the similarity of words like łefficientž and łeffectivež in the embedding space.
(left record) title: efficient and cost-effective techniques for browsing and indexing large video databases; author: kien a. hua , jung-hwan oh; venue: SIGMOD; year: 2000 (right record) title: effective timestamping in databases; author: kristian torp , christian s. jensen , richard thomas snodgrass; venue: VLDBJ; year: 2000 Another example we bring is from iTunes-Amazon dataset. The following pair records is an FP by Ditto. First, both songs are by Kenny Chesney. But more importantly, using a pre-trained language model, Likes Me and Loves Me are considered (almost) identical. As a result, the model mistakenly labeled the left and right songs as a match. Interestingly, such cases happen to be more frequent in genres such Country, resulting in FPRP unfairness for those groups, as shown in Figure 4. Our fourth example is from the Cameras dataset, where camera records are matched based on their descriptions. A successful matcher on a dataset that includes descriptions in many languages requires extensive coverage of language models on various languages. For example, Mcan returns the following pair of records as an FN, although the model and the brand match, and Prijzen is the Dutch translation of word Prices. We suspect that this is due to the poor coverage of word embeddings on the Dutch language.
(left record) title: Sony Cyber-shot RX100@en RX100 Prices -CNET@en (right record) tile: Sony Cyber-shot RX100 Zwart -Prijzen @NL Tweakers@NL One model does not fit all. In iTunes-Amazon dataset, an interesting observation is that neural matchers perform poorly for the class of country (because a neural matcher creates a curvy decision boundary for all groups and fails for easy groups), while non-neural matchers perform poorly for the class of rap (because non-neural matchers make simple decision boundaries which may not work for a difficult group such as the class of rap genres).
For setwise attributes, matchers demonstrate similar unfair behavior on groups with overlapping semantics. In practice, we observe that, in single setwise sensitive attributes, different sets of groups highly overlap. This is sometimes due to the existence of a semantic hierarchy of groups. For example, in the iTunes-Amazon dataset, Honky Tonk and Cont. Country are subclasses of Country in the semantic taxonomy of Wikipedia. As a result, we observe similar behavior of matchers across these groups. For instance, Figure 4 shows extensive unfair behavior of neural matchers on country music groups: Honky Tonk, Cont. Country, and Country. Following the same trend, non-neural matchers perform poorly on groups Hip-hop/Rap and Rap and Rap & Hip-Hop, suggesting these matchers are unfair to rap and hip-hop singers. Non-neural Matchers: The non-neural matchers universally failed for the textual datasets (Camera and Shoes), with F-1 measures as low as zero in several cases. This underscores that these matchers are not fit for unstructured data. Still, in some settings, these matchers were both inaccurate and unfair for different groups, as shown in Figure 9. Note that a matcher being fair in these cases simply means that it equally failed for all groups, not that it is a good choice. On the other hand, non-neural matchers performed well for the structured datasets. Still, similar to the neural matchers, all of them showed unfairness in multiple cases. Further investigating this unfairness, we realized that by minimizing the overall error, these models put high weights on attributes that often indicate a match. In other words, overall, those attributes are good proxies for the ground-truth labels. However, when it comes to certain groups, they may not be as good proxies, causing the model to underperform for those groups. For example, consider SvmMatcher for the Dblp-Acm dataset, which was unfair for SIGMOD Rec. and VLDBJ. First, we realized that both these groups frequently publish reports or editorial articles with the same title but different years and authors. Being trained to perform for all groups, the SvmMatcher model assigned a high weight to the title, assuming that different articles have different titles. Therefore, for examples like the one below, it matched them, although different authors wrote those in different years. This caused a higher ratio of false match detection (FP) compared to the other groups resulting in PPVP unfairness. as well. Note that this issue is not necessarily limited to the nonneural matchers. For example, [22] also reports that an RNN-based matcher heavily relied on the łtimež attribute when matching songs in the iTunes-Amazon dataset. Lack of proper coverage [7,8,51] from some groups is the reason the models do not get well-trained for those. For example, in the Dblp-Acm case, the training data did not include enough non-match cases with (almost) identical titles to reduce the correlation of the title with the ground-truth label.
Matching Threshold vs. Fairness and Accuracy. In this experiment, we study the sensitivity of the models' fairness to the matching threshold. Based on our previous results, we only focus on the two measures of TPRP and PPVP. Figure 10 shows the number of discriminated groups with respect to TPRP (as the color code) and the overall TPR values (written in every cell) for different threshold values on the iTunes-Amazon dataset. The complementary results on other datasets are provided in [50]. It is evident in Figure 10 that neural matchers are more sensitive to the choice of thresholds. For example, while Ditto is completely fair at threshold 0.6, with a small increase in the matching threshold (to 0.65) it becomes unfair for 7 groups. To further investigate this empirical observation over various datasets and both TPRP and PPVP, we define the threshold sensitivity of each matcher on a dataset as the ℓ 2 distance on the number of groups a matcher is being unfair for between the adjacent matching thresholds. The results are provided in Table 7. Larger values indicate more sensitivity to the matching threshold. Aligned with our observation in Figure 10, the table shows higher sensitivity (less robustness) for the neural matchers. Some of the non-neural matchers have high sensitivity values for Cameras dataset. However, the model accuracy was universally bad for non-neural matchers on this dataset and regardless of fairness those matchers are not reliable.
Some of the lessons learned in this study include:
(i) Call for action to collect EM benchmarks on societal applications: Perhaps the most challenging burden when auditing EM techniques from the fairness perspective is lack of proper benchmark datasets. Although the EM community already has some benchmarks [32,58], a thorough audit of existing and future EM techniques requires benchmark entity-matching data for societal applications. In this paper, we took the first steps by creating and publishing two semi-synthetic social datasets using publicly available real datasets. NoFlyCompas and FacultyMatch are generated for auditing the fairness of EM techniques when some groups are over-represented in data and when two demographic groups have different degrees of similarity in their names.
(ii) Over-representation and name similarity in social data: Group over-representation and higher similarity degrees for specific groups are common in social data. Experiment results on our social datasets confirm the general unfairness of entity matchers under these conditions. Interestingly, under the group over-representation, we observed the superiority of non-neural matchers in terms of model performance and accuracy. Over-representation in general can increase the chance of finding similar non-matches for an entity, which can be falsely labeled as a match. Likewise, when names in one group are more similar, there is a higher chance of mistakenly labeling non-matching tuples from that group as a match. data can bias these models to significantly rely on attributes (such as name) that are highly correlated with the ground-truth label but may bias their performance for the minority groups. Neural matchers, on the other hand, generally perform well for different dataset types. Still, (a) using pre-trained language models and embeddings, (b) relying less on the structure of data caused these matchers to be unfair for different settings. The fairness of neural matchers is more sensitive to the choice of the similarity threshold, as small changes in the threshold value can significantly change their fairness. Therefore, it is important to identify the right threshold to find the most fair/accurate one.
(vi) Ensemble learning for fair EM: We observed that, in a fixed dataset, some groups needed matchers with more complex decision boundaries, while others required matchers with simpler decision boundaries. As a result, adapting either of the neural/non-neural matchers would show unfairness for some groups. This observation underscores the need for techniques such as ensemble learning to consider a range of matchers with different properties to assure similar performance across different groups. Specifically, for cases with a single sensitive attribute with exclusive values, we recommend to train a set of matchers, for each group identify the one that performs the best, and use it for that group. This helps to maximize the performance for the under-performing groups. Note that this is different from the ensemble-learning-based approaches, since their goal is to improve the overall EM accuracy [37], not reducing unfairness. For instance, Jurek et al. apply ensemble learning based on feature selection [30], while Yu et al. create an ensemble of models based on different similarity metric schemes [59]. We leave designing ensemble EM techniques for fairness as future work.
Rule of Thumb: Following our findings and the lessons learned in this study, we would like to conclude the paper by Table 8, which provides some actionable insights and rules of thumb for responsible entity matching.
This measure is only meaningful for (a) single fairness and (b) pairwise fairness cases when groups are overlapping.
Semi-synthetic data generators are available for public access in[29].
For the evaluation of ML-based matchers, we used random train/test splits from the datasets published by Magellan[32]. To be consistent, all matchers are evaluated in a standard framework against the same datasets. We acknowledge that these results may not exactly match the accuracy results reported by matchers' papers.
Across all plots, Equalized Odds (EO) is the union of FPRP and TPRP rows. A matcher that is appears either in row 3 or row 4 of any column is unfair from EO perspective.