Research map / Graph learning / Graph algorithms and clustering
Efficient Axiomatization of OWL 2 EL Ontologies from Data by Means of Formal Concept Analysis
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Revises and extends the FCA-based method for axiomatizing complete OWL 2 EL TBoxes (CIs, range restrictions, role inclusions) from graph data, with an efficient multi-threaded implementation and variations that drop disjointness axioms or huge CIs.
Problem
Automatically axiomatizing a complete OWL 2 EL TBox from graph-structured data (knowledge graphs, RDF) is computationally expensive, since canonical bases can produce extremely large concept inclusions and exponential blowup.
Approach
Reformulates the Baader–Distel FCA axiomatization using maximal simulations and model-based most specific concepts (MMSCDs) over the powering interpretation, computes attributes via closure enumeration (FCbO) and canonical implication bases via LinCbO, and offers variants that skip disjointness axioms, bound conjunction size or role depth, trading completeness for practicality.
Key results
- Weak reduction computed successfully for 599 of 614 test datasets (97.56%), often reducing object count by more than an order of magnitude.
- Computation finished for all reduced datasets with no more than 100 objects; datasets with 1,000–10,000 objects failed without restrictions but often succeeded under restricted settings.
- Computing disjointness axioms accounts for more than half of computation time, so skipping them (None/Fast modes) saves substantial resources.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| reduce the input interpretation by grouping objects that satisfy the same CDs | FCA-based axiomatization prototype · ORE 2015-derived test datasets | number of objects: often by more than one order of magnitude | Helped |
| omit disjointness axioms (ablation) | FCA-based axiomatization prototype · ORE 2015-derived test datasets | computation time: more than half of the computation time | Helped |
| compute disjointness axioms in the fast way rather than the canonical way (ablation) | FCA-based axiomatization prototype · ORE 2015-derived test datasets | computation resources | Helped |
| set a role-depth bound or conjunction-size limit (ablation) | FCA-based axiomatization prototype · ORE 2015-derived test datasets | resource consumption | Helped |
| set a role-depth bound or conjunction-size limit (ablation) | FCA-based axiomatization prototype · ORE 2015-derived test datasets | completeness | Hurt |
Surprising findings
- More than half of the computation time is spent generating disjointness axioms, making the witnessed-only variant considerably cheaper.
Limitations
- Completeness is lost when conjunction size limits, role-depth bounds, or the successor-count abort are used; the effect is not fully investigated.
- RRs and RIs are not rewritten into RIs without auxiliary role names, and the EL rewriting and RR/RI axiomatization were not implemented or measured.
- Some large datasets (over 300,000 objects) ran out of memory; ORE ontologies were approximated into EL by removing unsupported axioms.
Experimental setup
Datasets: ORE 2015 Reasoner Competition ontologies (614 derived test datasets)
Benchmarks: ORE 2015 Reasoner Competition ontologies
Metrics: computation time number of CIs in base number of objects after reduction success/failure rate (timeouts, out-of-memory)
Baselines: Baader-Distel 2008 axiomatization Fast CI base None mode (no disjointness axioms)
Builds on: Baader–Distel FCA-based EL axiomatization LinCbO FCbO ELK Completion algorithm EL⊥si
Closest papers by meaning
- Efficient Extraction of EL-Ontology Deductive Modules (AAAI 2023 · similarity 0.85)
- Minimal Macro-Based Rewritings of Formal Languages: Theory and Applications in Ontology Engineering (and Beyond) (AAAI 2024 · similarity 0.84)
- End-to-End Ontology Learning with Large Language Models (NeurIPS 2024 · similarity 0.82)
- Stable Model Semantics for Description Logic Terminologies (AAAI 2024 · similarity 0.82)
- Answering Conjunctive Queries with Safe Negation and Inequalities over RDFS Knowledge Bases (AAAI 2025 · similarity 0.81)
- Spectra of Cardinality Queries over Description Logic Knowledge Bases (AAAI 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.