Entity Resolution

Entity Resolution in Health Data and Knowledge Graphs

Entity resolution is a data analytics task that decides when several records describe one real-world person, organisation, study or other thing, and then joins those records up. In health economics a common case is a trial participant who also appears in hospital episode records and a death register, where identifiers are missing or recorded differently, or one trial report retrieved from several bibliographic databases before a systematic review. A missed or false match therefore changes the admissions and costs that reach a decision model.

Descriptions, entities and the missing identifier

Christophides and colleagues give the aim of entity resolution as identifying different descriptions that refer to the same real-world entity, within or across data sources, when unique entity identifiers are not available. Matching records within one table is called deduplication and matching across two tables is called record linkage, while matching descriptions across RDF knowledge bases is called link discovery.

The task exists because identifiers are rarely shared across public services. Harron and colleagues note that Scandinavian countries give each resident one personal identity number used across health care, taxation, education and other services, which lets sources be linked with marginal error. In the UK the NHS number is used for health services in England and the Community Health Index number is the main health identifier in Scotland, and neither is reliably used in education data. Linkage then relies on names, dates of birth, sex and postcodes, which carry recording errors.

For trial-based economic evaluation, Franklin and Thorn describe Hospital Episode Statistics as a source in England of person-level hospital data whose Healthcare Resource Group codes, held in the dataset only until 2012 and otherwise derived from its codes with grouper software, can be linked with reference cost data. Linked routine records, such as administrative data and electronic health records, let a randomised controlled trial measure resource use without relying only on patient recall, which the same authors note is often inaccurate.

Cleaning, blocking, comparing and classifying record pairs

Most systems follow a similar sequence. Christophides and colleagues describe a generic workflow of blocking, block processing, matching and clustering, and Sayers and colleagues add data cleaning before any comparison, such as unifying date formats and using checksums to find invalid NHS numbers.

The number of comparisons grows with the product of the file sizes. Sayers and colleagues show that two files of 10,000 people give 100,000,000 candidate pairs, and that blocking by region, with people spread equally over 10 regions, leaves 10 × 1,000 × 1,000 = 10,000,000 pairs. Blocking assumes that records in different blocks cannot match, and Harron and colleagues warn that an error in the blocking variable prevents a true pair from linking.

Each candidate pair is then compared field by field. An edit distance counts the insertions, deletions and substitutions needed to turn one string into another, and Sayers and colleagues score agreement between Steele and Steel as 1 − 1/6 = 0.83.

Pairs are then classified. Deterministic linkage applies fixed rules, and Harron and colleagues report that hospital admission records for the same person over time in the UK are linked with a three-step deterministic algorithm using combinations of NHS number, date of birth, sex and postcode. Such rules tend to miss matches when an identifier is mistyped or missing, while false matches are rare. Probabilistic linkage in the Fellegi-Sunter framework gives each pair a match weight.

$$w_j = \sum_{i=1}^{K} \left[ \gamma_{ij} \log_2\left(\frac{m_i}{u_i}\right) + (1-\gamma_{ij}) \log_2\left(\frac{1-m_i}{1-u_i}\right) \right]$$

where $w_j$ is the match weight for candidate pair $j$, $K$ is the number of compared fields, $\gamma_{ij}$ is 1 if field $i$ agrees in pair $j$ and 0 if it disagrees, $m_i$ is the probability that field $i$ agrees when both records belong to the same person and $u_i$ is the probability that field $i$ agrees by chance when they belong to different people. Sayers and colleagues show how Bayes' theorem turns the weight and the prior odds into a match probability, and how two thresholds sort pairs into links, non-links and possible links for clerical review.

A final clustering step turns pairwise decisions into groups that each stand for one entity, and Christophides and colleagues note that taking the transitive closure of all matches raises recall but is sensitive to noise, because one false link can join two people's records.

Identity links in ontologies and knowledge graphs

The OWL 2 specification states that an individual equality axiom, the sameAs property in RDF, lets each named individual be replaced by the other without changing the meaning of the ontology. OWL 2 does not make the unique name assumption, so two names may denote one individual unless a DifferentIndividuals axiom says otherwise.

OWL 2 keys show deterministic linkage in logical form. The specification's example makes a social security number property a key, so two individuals with the same value are inferred to be one. A patient identifier declared as a key would merge any two patient nodes sharing a value, even two different people who share it through a typing error. Hogan and colleagues treat identity-link prediction in knowledge graphs as analogous to entity matching.

Concept schemes need a softer link. The SKOS Reference states that the OWL sameAs property would typically be inappropriate for linking SKOS concepts in different concept schemes, because its formal consequences could be undesirable, and provides the closeMatch and exactMatch mapping properties instead. A close match is not transitive, to avoid compound errors when mappings across more than two schemes are combined, while an exact match is transitive. A link between a concept in HEO, HealthEconomics.wiki's own concept scheme published in OWL, and a heading in another thesaurus would therefore use a SKOS mapping property such as closeMatch or exactMatch, not sameAs.

Choices that move the balance between missed and false links

Every linkage trades missed matches against false matches. Sayers and colleagues note that threshold placement can be a matter of trial and error, and that favouring the sensitivity of detecting matches brings more clerical review than favouring specificity. The right balance depends on the question.

The standard weights assume that agreement on different fields is conditionally independent given match status, which Sayers and colleagues note is often violated, since records that agree on postcode are more likely to agree on street name. Governance also shapes what analysts can check. Harron and colleagues describe the separation of linkage, done by a trusted third party that sees identifiers, from analysis of de-identified data as best practice for confidentiality in many jurisdictions, and note that the separation can hide aspects of the linkage that affect reliability. Where identifiers cannot be released, privacy-preserving methods compare encrypted identifiers, alongside de-identification.

Measuring linkage quality and its effect on estimates

Linkage quality is summarised with the two-by-two table of diagnostic testing. Doidge and Harron define recall as the sensitivity of linkage and precision as its positive predictive value.

$$\text{Precision} = \frac{TP}{TP + FP}, \qquad \text{Recall} = \frac{TP}{TP + FN}$$

where $TP$ is the number of true links between records of the same entity, $FP$ is the number of false links between different entities and $FN$ is the number of missed links. Because true match status is unknown, Sayers and colleagues list ways to estimate quality, including a gold-standard subsample, sensitivity analysis of the match parameters, comparison of linked and unlinked records, and implausible links such as a mortality sequence of alive, dead and then alive.

Doidge and Harron set out how linkage error becomes bias. Missed links produce missing data, or misclassification when the presence of a link is itself read as a value, as when mortality is inferred by linkage to a death register. False links import another person's values. The bias depends on the error rates and on how errors are spread across the variables of interest, and Harron and colleagues report that some sources show lower match rates in more vulnerable or deprived populations.

Worked example with missed hospital links in a two-arm trial (illustrative)

A hypothetical trial compares a new care pathway (arm A) with usual care (arm B), with 1,000 participants per arm. Hospital costs are measured by linkage to hospital episode records, and absence of a link is read as no admission. Each admitted participant has one admission costing GBP 3,000, and all figures are illustrative.

The true mean cost in arm A is 250 × 3,000 / 1,000 = 750 and in arm B is 300 × 3,000 / 1,000 = 900, a true saving of GBP 150 per participant (900 − 750 = 150). Linkage finds 0.96 × 250 = 240 admissions in arm A, giving 240 × 3,000 / 1,000 = 720, and 0.90 × 300 = 270 in arm B, giving 270 × 3,000 / 1,000 = 810. The estimated saving is 810 − 720 = 90, which understates the true saving by 150 − 90 = 60, or 40% of it. Evenly spread missed links would shrink the saving in proportion to recall, to 0.90 × 150 = 135 at 90% recall, while differential linkage distorts it further.

The error reaches the ICER. If the pathway costs GBP 500 more per participant to deliver and gains 0.02 QALYs, the true incremental cost is 500 − 150 = 350 and the ICER is 350 / 0.02 = GBP 17,500 per QALY. With the differential linkage the incremental cost becomes 500 − 90 = 410 and the ICER 410 / 0.02 = GBP 20,500 per QALY. False links push the other way by adding other people's admissions, so the two error types can partly offset each other, as Doidge and Harron note.

Neighbouring tasks and where each applies

Record linkage is the statistical tradition for joining records about people across files, and its probabilistic theory is treated separately. Entity linking matches a name found in text to one entry in a knowledge base, after named entity recognition has found the name, and ontology matching aligns mainly classes and properties between ontologies, not individual records.

Systematic reviews meet the same problem as reference de-duplication. McKeown and Mir compared the default de-duplication of a database platform, reference managers and review software against a manually built benchmark and found differences in sensitivity and specificity. A false duplicate removes an eligible study before screening and data extraction.

Limitations and frequent misreadings

A high match rate counts links without saying whether they are true, and Harron and colleagues note that it helps only when the number of records that should link is known. Doidge and Harron point out that many algorithms are designed to keep precision very high, so false links are often rare enough to ignore, while missed links that depend on variables of interest can cause selection bias and information bias.

Similar records are not the same entity. Two people can share a name and a date of birth, and Doidge and Harron note that false links occur more often to records with frequent values, which makes analyses of rare conditions more sensitive to linkage error. Under OWL reasoning, a sameAs link asserted in error makes every statement about one node hold for the other, so a wrong identity link between two drugs or two patients affects every query that uses them.

A linked dataset is usually analysed as if every link were certain. Doidge and Harron describe methods that carry linkage uncertainty into the analysis, such as multiple imputation, inverse probability weighting and linkage error-adjusted regression, which they note are relatively new.

Sources

• Christophides V, Efthymiou V, Palpanas T, Papadakis G, Stefanidis K. End-to-end entity resolution for big data: a survey. arXiv:1905.06397v3, 19 August 2020, published as An overview of end-to-end entity resolution for big data, ACM Computing Surveys 2020;53(6). https://arxiv.org/abs/1905.06397
• Doidge JC, Harron KL. Reflections on modern methods: linkage error bias. International Journal of Epidemiology. 2019;48(6):2050-2060. https://doi.org/10.1093/ije/dyz203
• Franklin M, Thorn J. Self-reported and routinely collected electronic healthcare resource-use data for trial-based economic evaluations: the current state of play in England and considerations for the future. BMC Medical Research Methodology. 2019;19:8. https://doi.org/10.1186/s12874-018-0649-9
• Harron K, Dibben C, Boyd J, et al. Challenges in administrative data linkage for research. Big Data & Society. 2017;4(2):2053951717745678. https://doi.org/10.1177/2053951717745678
• Hogan A, Blomqvist E, Cochez M, et al. Knowledge graphs. ACM Computing Surveys. 2021;54(4):1-37. https://doi.org/10.1145/3447772
• McKeown S, Mir ZM. Considerations for conducting systematic reviews: evaluating the performance of different methods for de-duplicating references. Systematic Reviews. 2021;10:38. https://doi.org/10.1186/s13643-021-01583-y
• Miles A, Bechhofer S, eds. SKOS Simple Knowledge Organization System Reference. W3C Recommendation, 18 August 2009. https://www.w3.org/TR/skos-reference/
• Motik B, Patel-Schneider PF, Parsia B, eds. OWL 2 Web Ontology Language Structural Specification and Functional-Style Syntax (Second Edition). W3C Recommendation, 11 December 2012. https://www.w3.org/TR/owl2-syntax/
• Sayers A, Ben-Shlomo Y, Blom AW, Steele F. Probabilistic record linkage. International Journal of Epidemiology. 2016;45(3):954-964. https://doi.org/10.1093/ije/dyv322