Mining Definitions from RDF Annotations Using Formal Concept Analysis

Mehwish Alam, Aleksey Buzmakov, Víctor Codocedo, Amedeo NapoliIJCAI 2015

Linked Open Data (LOD) sources like DBpedia are invaluable knowledge reservoirs, yet they frequently suffer from two critical shortcomings: data incompleteness and semantic looseness. While DBpedia utilizes "categories" (e.g., "French films") to organize information, these often function as informal tags rather than machine-readable definitions. This lack of formal structure prevents automated systems from inferring logical properties—for instance, that a "French film" should inherently possess a hasCountry property linked to "France."

This research introduces a method to bridge this gap by transforming these loose annotations into formal definitions and identifying missing triples within the RDF graph using Formal Concept Analysis (FCA).

Methodology: Formal Concept Analysis

The core of this approach lies in FCA, a mathematical framework that organizes objects and their attributes into a hierarchical structure known as a concept lattice. In this context, objects are DBpedia entities (like specific car models), and attributes are their RDF properties and categories.

A concept lattice representing Lamborghini models and their associated attributes, illustrating the hierarchical structure mined by FCA.

To handle the complexity of real-world RDF data, which includes numerical values and dates, the authors utilize Heterogeneous Pattern Structures. This extension allows the model to process data like productionStartYear as numerical intervals rather than simple strings, enabling a unified lattice that can define a "Sports Car" using both categorical tags and numerical ranges.

From Tags to Formal Definitions

The system mines implication rules ($X \implies Y$) to find attributes shared by members of a category. A key innovation is the use of the "inverted rule": by examining the confidence of $Y \implies X$, the researchers can identify equivalences. If both directions have high confidence, the system has likely discovered a formal definition (e.g., "An entity is a Lamborghini vehicle if and only if it is an automobile manufactured by Lamborghini").

This method also serves as a data quality check. If an entity is tagged with a category but lacks the properties common to 99% of other members in that category, it is flagged for potential correction or completion.

Evaluation and Results

The approach was tested on four DBpedia subsets: Cars, Videogames, Smartphones, and Countries. The results demonstrated both high accuracy and computational efficiency.

Precision-Recall curves for the four evaluation datasets, demonstrating high precision across various domains.

Key findings include:

  • High Precision: The "Countries" dataset achieved a precision of 0.9, while "Cars" reached 0.85, indicating that the vast majority of mined rules were valid candidates for formal definitions.
  • Efficiency: Even the largest dataset, containing 50,000 triples, was processed in under 60 seconds.
  • Data Enrichment: The model successfully identified missing annotations. For example, it flagged that the "Estoque" and "Gallardo" models were missing the "Lamborghini vehicles" category despite meeting all other criteria.

Limitations and Future Outlook

While promising, the method currently operates under a Closed World Assumption, which can lead to trivial rules if the dataset is biased. Additionally, a human-in-the-loop remains necessary to verify definitions and avoid adopting accidental correlations. Future research will focus on scaling these FCA techniques to the billions of triples found in the full LOD cloud, potentially through distributed lattice construction.

Summary updated

BibTeX
@inproceedings{alam2015mining,
  author = {Mehwish Alam and Aleksey Buzmakov and Víctor Codocedo and Amedeo Napoli},
  title = {{Mining Definitions from RDF Annotations Using Formal Concept Analysis}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure