Linkex: A Tool for Link Key Discovery Based on Pattern Structures

Nacira Abbas, Jérôme David, Amedeo NapoliICFCA (Supplements) 2019

TL;DR

This paper introduces Linkex, a novel tool for discovering "link keys" – rules that identify equivalent entities across different Linked Data datasets. By leveraging Pattern Structures, a generalization of Formal Concept Analysis, Linkex can automatically extract these link key candidates, offering a scalable and applicable solution for the growing challenge of data interlinking.

What Problem Does This Paper Address?

The explosion of Linked Data on the web has made data interlinking – the task of identifying the same real-world entities described in different datasets – a critical challenge. One key aspect of this is discovering "identity links" between entities. Traditional approaches often rely on "link keys," which are sets of property-value pairs that can infer these identity links. However, existing methods for discovering these link keys can be computationally expensive, especially with the massive scale of RDF datasets. This paper addresses this by proposing a more efficient and formal method for link key discovery using Pattern Structures, which can handle non-binary data directly, avoiding the need for costly data binarization.

Methods

The core of this paper's contribution lies in its formalization of link key discovery using Pattern Structures (PS). PS is a generalization of Formal Concept Analysis (FCA) that is well-suited for dealing with non-binary data, which is common in RDF datasets.

Here's a breakdown of their approach:

  • Link Key Expressions: They define a "link key expression" as a formal representation of a link key, consisting of two sets of property pairs: Eq (properties that must have identical values) and In (properties that must have at least one shared value).
  • Pattern Structure for Link Key Extraction: They define a specific Pattern Structure tailored for this task. This structure maps pairs of instances from two classes (e.g., Person and Inhabitant) to their "description," which is the maximal link key expression satisfied by that pair.
  • Pattern Concepts and Link Key Candidates: The key insight is that the intents of the resulting pattern concepts in the PS lattice directly correspond to link key candidates. The extents of these concepts represent the sets of identity links generated by those candidates.
  • Linkex Tool: They have implemented a prototype tool called Linkex that automates this process. Linkex computes the PS, generates the pattern concept lattice, and identifies link key candidates.

Datasets

The authors experimented with two bibliographical datasets:

  • BnF (Bibliothèque nationale de France): Provided samples of author instances and their associated book instances.
  • ABES (Agence Bibliographique de l'Enseignement Supérieur): Also provided samples of author instances and their book instances.

They used two specific samples for their experiments:

  • Sample 1: Authors with first name/last name combinations in the top 1000 most frequent homonyms.
  • Sample 2: Authors with last names starting with the letter 'A'.

These datasets were used to demonstrate the applicability and scalability of their Linkex tool.

Key Insights and Ideas

  • Pattern Structures as a Natural Fit: The paper highlights that Pattern Structures are a powerful and natural framework for discovering link keys because they can directly handle the multi-valued nature of RDF properties without requiring data binarization, which is a significant advantage over traditional FCA.
  • Intents as Link Key Candidates: The most crucial insight is the direct correspondence between the intents of pattern concepts and link key candidates. This provides a clear and formal way to extract these candidates.
  • Scalability and Efficiency: The experimental results suggest that their PS-based approach is both applicable and scalable, producing a manageable number of link key candidates even from large datasets. This is a significant practical benefit for data interlinking.
  • Expert Navigation: The reduced number of link key candidates allows human experts to more easily navigate and evaluate them, making the process more efficient in practice.

Key Results

The paper demonstrates the effectiveness of their approach through experimentation with bibliographical datasets.

  • Efficient Candidate Generation: For Sample 1 (1,564,495 pattern structure descriptions), Linkex identified only 155 link key candidates. For Sample 2 (12,348,012 pattern structure descriptions), it found 186 link key candidates.
  • Processing Time: The processing times were relatively short, with Sample 1 taking 2 minutes and 10 seconds and Sample 2 taking 6 minutes and 50 seconds.
  • Scalability: The processing time was observed to be correlated with the size of the datasets, indicating that the method scales with data volume.
  • Applicability: The tool successfully identified link key candidates that could be applied to generate expected identity links between the datasets.

Limitations and Future Work

  • Limitations:
    • The paper focuses on extracting link key candidates. The quality assessment and selection of the "best" link key candidate are noted as being out of the scope of this particular paper, though they mention that quality measures have been proposed elsewhere.
  • The current approach relies on exact equality for literal comparisons.
  • Future Work:
    • Interdependent Classes: Extend the work to handle interdependent classes, where RDF objects might be instances of other classes.
  • Similarity Measures: Relax the strict equality constraints for literal comparisons by incorporating similarity measures. This would allow for more flexible and robust link discovery, especially for data with variations in spelling or formatting.

Summary updated

BibTeX
@inproceedings{abbas2019linkex,
  author = {Nacira Abbas and Jérôme David and Amedeo Napoli},
  title = {{Linkex: A Tool for Link Key Discovery Based on Pattern Structures}},
  booktitle = {ICFCA (Supplements)},
  year = {2019},
}
Figure