Sandwich: An Algorithm for Discovering Relevant Link Keys in an LKPS Concept Lattice

Nacira Abbas, Alexandre Bazin, Jérôme David, Amedeo NapoliICFCA 2021 · DOI

TL;DR

This paper introduces the "Sandwich" algorithm, a novel approach for efficiently identifying relevant "link keys" within large concept lattices derived from RDF datasets. By combining top-down and bottom-up pruning strategies, Sandwich effectively balances the trade-off between correctness and completeness, leading to more accurate data interlinking.

What Problem Does This Paper Address?

In the realm of linked data, where information is spread across various RDF datasets, a crucial task is "data interlinking." This involves identifying pairs of identical entities (represented by IRIs) that exist in different datasets. A key mechanism for achieving this is the discovery of "link keys." Link keys are essentially rules that, when applied to two datasets, can infer identity links between entities.

The challenge lies in the sheer volume of potential link keys that can be generated. Traditional methods, often based on Formal Concept Analysis (FCA), can produce massive "concept lattices" where each concept's "intent" represents a potential link key. However, not all these candidates are useful; many are either too specific (low completeness) or too general and potentially incorrect (low correctness). The paper addresses the problem of efficiently sifting through these vast lattices to find the most relevant and reliable link keys that strike a good balance between these two critical criteria.

Methods

The core contribution of this paper is the Sandwich algorithm. This algorithm operates on an LKPS-lattice (Link Key Pattern Structure lattice), which is a structure generated from two RDF datasets to represent potential link key candidates. The Sandwich algorithm employs a dual pruning strategy:

  • Bottom-up Pruning: This strategy focuses on correctness. It identifies link keys that are highly likely to generate correct identity links. This is achieved by retaining concepts whose intents (representing link keys) meet a minimum correctness threshold. The paper notes that more correct link keys tend to be found in the "lower part" of the lattice.
  • Top-down Pruning: This strategy focuses on completeness. It identifies link keys that can generate the largest possible set of correct identity links. This is done by retaining concepts whose extents (representing the set of links generated) meet a minimum completeness threshold. The paper observes that more complete link keys are typically found in the "upper part" of the lattice.

The "Sandwich" algorithm combines these two pruning strategies. It first splits the lattice into sub-lattices based on the pairs of classes the link keys apply to. Then, it applies both the bottom-up and top-down pruning to each sub-lattice. The final output is a set of link key candidates that satisfy both the correctness and completeness criteria, effectively finding the "middle ground" where the best compromise is achieved.

Datasets

The paper uses example datasets (D1 and D2, and later D3 and D4) to illustrate its concepts and algorithms. These are described as RDF datasets populated with instances of various classes (e.g., Vaccine, Organism, Drug, Virus, Bacteria, Person, Newspaper). The paper does not introduce new benchmark datasets but rather uses these examples to demonstrate the LKPS-lattice generation and the Sandwich algorithm's pruning process.

Key Insights and Ideas

  • Duality of Correctness and Completeness: The paper highlights a fundamental duality between correctness and completeness in link key discovery. As you increase one, the other tends to decrease. This inverse relationship is key to understanding why a combined approach is necessary.
  • LKPS-Lattice as a Rich Source: The LKPS-lattice, derived from pattern structures, provides a structured way to represent all potential link key candidates, making them amenable to systematic exploration.
  • The "Sandwich" Strategy: The core innovation is the Sandwich algorithm's ability to leverage the lattice structure and the duality principle. By performing both bottom-up (correctness-focused) and top-down (completeness-focused) pruning, it efficiently identifies the "sweet spot" of relevant link keys.
  • Monotonicity is Key: The effectiveness of the pruning strategies relies on the chosen quality measures (correctness and completeness) being monotone with respect to the lattice's order. This ensures that the pruning process correctly identifies candidates in the relevant parts of the lattice.

Key Results

The paper presents a conceptual algorithm and demonstrates its application with examples. It shows how the Sandwich algorithm, given an LKPS-lattice and appropriate quality measures (e.g., intent size for correctness, coverage for completeness) and thresholds, can effectively prune the lattice to identify the most relevant link key candidates. For instance, in the example with datasets D3 and D4, the algorithm identifies k5 as the best link key candidate for the (Person, Personne) class pair, achieving a coverage of 1 and an intent size of 4, balancing both criteria. The paper emphasizes the elegance of this approach in leveraging the inherent structure of Galois connections.

Limitations and Future Work

  • Choice of Quality Measures: The paper acknowledges that the effectiveness of the Sandwich algorithm depends on the choice of quality measures. While it demonstrates with "intent size" and "coverage," future work could explore a wider range of measures, including those commonly used in FCA and data mining like "stability" or "lift," to better characterize link keys.
  • Global Traversal Strategy: The authors suggest improving the global traversal strategy by potentially integrating the characterization of link key candidates during the construction of the pattern concept lattice itself, rather than pruning an already built lattice. This could lead to more efficient processing.
  • Experimental Validation: The paper mentions the need for a complete set of experiments on real-world data to validate the proposed approach and its algorithmic components thoroughly.
  • Generalization: While the Sandwich algorithm is presented as generic and adaptable to different monotone quality measures, further exploration of its performance with various measure combinations is warranted.

Summary updated

BibTeX
@inproceedings{abbas2021sandwich,
  author = {Nacira Abbas and Alexandre Bazin and Jérôme David and Amedeo Napoli},
  title = {{Sandwich: An Algorithm for Discovering Relevant Link Keys in an LKPS Concept Lattice}},
  booktitle = {ICFCA},
  year = {2021},
  doi = {10.1007/978-3-030-77867-5\_15},
}
Figure