Discovering a Representative Set of Link Keys in RDF Datasets

Nacira Abbas, Alexandre Bazin, Jérôme David, Amedeo NapoliEKAW 2024 · DOI

TL;DR

This paper tackles the challenge of efficiently identifying and validating "link keys" – crucial for data interlinking in RDF datasets. They introduce LKCLUST, a novel algorithm that combines Formal Concept Analysis (FCA) with hierarchical clustering to generate a concise, representative set of link key candidates, significantly reducing the burden on human analysts.

What Problem Does This Paper Address?

Data interlinking, the process of connecting entities across different datasets, is vital for creating richer, more comprehensive knowledge graphs. A key technique for this is "link key discovery," which aims to find patterns (sets of properties and classes) that can reliably identify equivalent entities in two separate RDF datasets. However, existing methods often produce a massive number of potential link keys, making it impractical for domain experts to manually validate them. This paper addresses the need for a method that not only discovers link keys but also distills them into a manageable, representative set that preserves essential information and relationships.

Methods

The authors propose a two-stage approach:

  1. Link Key Candidate Discovery (FCA-based): They leverage Formal Concept Analysis (FCA) to build an "LK-lattice." FCA is a mathematical framework for data analysis that identifies concepts (pairs of objects and attributes) and organizes them into a lattice structure. In this context, concepts represent potential link key candidates, and the lattice captures their relationships and hierarchies.
  2. Representative Set Generation (LKCLUST): To address the problem of a large number of candidates, they introduce the LKCLUST algorithm. This algorithm employs agglomerative hierarchical clustering (AHC) on the LK-lattice. LKCLUST is designed to preserve the lattice's ordering while minimizing the number of selected candidates. It prioritizes candidates that offer good "compression rate" (fewer candidates representing more information) and "proportion of preserved links" (maintaining the ability to identify as many entity links as possible). A key innovation is how LKCLUST adapts AHC to work efficiently with the lattice structure, reducing the number of dissimilarity computations required.

Datasets

The experiments were conducted on ten different tasks, involving two types of datasets:

  • Synthetic Datasets: Seven tasks were based on datasets from the Ontology Alignment Initiative (OAEI), including "Restaurants," "Person1," "Person2," and "Doremus" tasks, as well as the "SPIM-Bench" task. These datasets share the same ontology/schema.
  • Real-World Datasets: Three tasks involved real-world data interlinking scenarios with different ontologies. These include a "Libraries" task using data from the Bibliothèque nationale de France (BnF) and Agence bibliographique de l'enseignement supérieur (Abes), and two tasks using samples from DBPedia and Wikidata ("wiki-random" and "wiki-person").

Key Insights and Ideas

  • FCA as a Foundation for Link Key Discovery: Using FCA to build an LK-lattice provides a structured way to discover link key candidates and understand their relationships, moving beyond simple candidate generation.
  • The Challenge of Candidate Explosion: The sheer volume of potential link keys generated by FCA necessitates a method for summarization and representation.
  • Hierarchical Clustering for Summarization: LKCLUST effectively uses AHC to navigate the LK-lattice and create a compact, representative set of link keys.
  • Balancing Compression and Preservation: The core idea is to find a REPLKSET that is small (high compression) but still captures most of the important identity links. This is a trade-off that LKCLUST aims to optimize.
  • Efficiency Gains: The LKCLUST algorithm, by leveraging the lattice structure, significantly reduces the computational cost compared to standard AHC, especially when convexity is enforced.

Key Results

  • Computational Efficiency: LKCLUST demonstrated significantly faster clustering times compared to classical AHC, with reductions of up to an order of magnitude in some cases. Enforcing cluster convexity further boosted performance.
  • Quality of Representative Sets: Experiments showed that the REPLKSET generated by LKCLUST achieved good compression rates and preserved a high proportion of identity links.
  • Precision and Recall: When evaluating selected link key candidates (medoids) against a gold standard, LKCLUST-based sets showed good precision and recall, particularly when a discriminability threshold was applied.
  • Convexity Impact: Forcing convexity in clusters led to similar compression and preservation results but with even greater computational efficiency.

Limitations and Future Work

  • Discriminability Threshold: The paper notes that the arbitrary setting of the discriminability threshold (0.9) might lead to sudden drops in recall in certain tasks. Future work could involve adapting this threshold on a case-by-case basis.
  • Alternative Clustering/Distance Measures: The authors suggest exploring other clustering algorithms and distance measures for building REPLKSETs.
  • Lattice Reduction: They propose that this approach could be extended to the challenging problem of lattice reduction.
  • Characterizing Mapping: Further research is needed to better characterize the mapping between an LK-lattice and a REPLKSET.

Summary updated

BibTeX
@inproceedings{abbas2024discovering,
  author = {Nacira Abbas and Alexandre Bazin and Jérôme David and Amedeo Napoli},
  title = {{Discovering a Representative Set of Link Keys in RDF Datasets}},
  booktitle = {EKAW},
  year = {2024},
  doi = {10.1007/978-3-031-77792-9\_4},
}
Figure