Several Link Keys are Better than One, or Extracting Disjunctions of Link Key Candidates

Manuel Atencia, Jérôme David, Jérôme EuzenatK-CAP 2019 · DOI

TL;DR

This paper tackles the challenge of data interlinking by proposing a method to combine multiple "link keys" (rules for identifying equivalent entities across datasets) into disjunctions. This approach significantly improves the accuracy of finding links compared to using single link keys, especially when datasets have different structures or cover diverse concepts.

What Problem Does This Paper Address?

Data interlinking, the process of identifying equivalent entities across different datasets, is crucial for enabling data interoperability. A common approach uses "link keys," which are conditions under which two instances from different datasets can be considered the same. While algorithms exist to extract good individual link keys, a single key often isn't sufficient to capture all the links, especially when datasets are heterogeneous or represent different aspects of the same real-world entities. This paper addresses the limitation of relying on a single link key by exploring how to effectively combine multiple link keys through disjunctions to achieve more comprehensive and accurate data interlinking.

Methods

The core contribution of this paper lies in defining and extracting disjunctions of link keys. They formally define conjunction and disjunction of link keys based on their semantic meaning (the links they generate). While conjunction doesn't offer new links beyond what individual keys provide, disjunctions are shown to be powerful. The authors extend existing quality measures (discriminability and coverage) to evaluate these disjunctions. To efficiently search for the best disjunctions within a potentially vast search space, they propose two heuristic strategies:

  • Top-k strategy: Selects the top-k best individual link key candidates and then exhaustively searches for the best disjunctions within this subset.
  • Expand-best strategy: A best-first search that iteratively expands promising antichains (sets of non-comparable link keys) by adding new candidates, aiming to find the best disjunction.

Datasets

The paper evaluates their approach using:

  • OAEI 2010 datasets: Specifically, Person1, Person2, and Restaurants datasets. These datasets are characterized by different ontologies and varying degrees of heterogeneity.
  • Doremus (OAEI 2016) datasets: PP-n and BnF-n datasets, described as small cultural institution datasets with heterogeneity.
  • SPIMBench (OAEI 2018) datasets: Abox1 and Abox2, containing around 380 instances and 10,000 triples, focusing on linking instances of classes like NewsItem, BlogPost, and Programme.
  • Libraries datasets: Sample data from the "Bibliothèque Nationale de France" (BnF) and "Agence Bibliographique de l'Enseignement Supérieur" (Abes), which use different ontologies and have only partial reference link sets.

Key Insights and Ideas

  • Disjunctions are powerful: The paper strongly advocates for using disjunctions of link keys, demonstrating that they can uncover links missed by single keys.
  • Conjunctions are redundant: The authors show that combining link keys via conjunction doesn't yield any new links beyond what individual keys can already generate.
  • Efficiency is key: The search space for disjunctions is enormous. The proposed heuristic strategies (top-k and expand-best) are crucial for making this problem tractable in practice.
  • Antichains as building blocks: The concept of antichains in the link key lattice is leveraged to represent non-redundant disjunctions, simplifying the search.
  • Quality measures extend well: Existing measures for individual link keys (discriminability and coverage) can be effectively extended to evaluate disjunctions, and their harmonic mean (κ) serves as a good overall metric.

Key Results

The experimental evaluation generally confirmed the hypothesis that disjunctions of link keys improve data interlinking performance.

  • Improved F-measure: In most cases, disjunctions achieved a better F-measure (a combined metric of precision and recall) than the best single link key candidate. For instance, in the Libraries task, the top-10 strategy marginally improved the F-measure.
  • Recall vs. Precision Trade-off: The expand-best strategy tended to generate longer disjunctions, favoring recall over precision, while the top-10 strategy often achieved better precision.
  • Strategy Performance: The top-10 strategy generally performed well and scaled better, while expand-best sometimes yielded better results but could generate very long disjunctions.
  • Limitations of κ: The paper notes that the κ measure isn't always optimal, and sometimes generated link key candidates have better F-measures than those selected by κ, especially with highly different dataset sizes.

Limitations and Future Work

  • Search Space: While heuristics are employed, the sheer size of the search space for disjunctions remains a challenge, especially with a large number of link key candidates.
  • Measure Optimality: The current quality measure (κ) isn't perfect and could be improved, particularly for datasets with significant size differences or when the target link set deviates from a one-to-one mapping.
  • Future Work: The authors suggest exploring combinations of their heuristics or developing more suitable unsupervised measures to further enhance the extraction of optimal disjunctions. They also acknowledge that while their approach doesn't require supervised learning or ontology alignments, other methods might perform better on datasets with shared ontologies.

Summary updated

BibTeX
@inproceedings{atencia2019several,
  author = {Manuel Atencia and Jérôme David and Jérôme Euzenat},
  title = {{Several Link Keys are Better than One, or Extracting Disjunctions of Link Key Candidates}},
  booktitle = {K-CAP},
  year = {2019},
  doi = {10.1145/3360901.3364427},
}

Loading related content...

Figure