Small Is Beautiful: Computing Minimal Equivalent EL Concepts

Nadeschda Nikitina, Patrick KoopmannAAAI 2017 · DOI

Abstract

Modern knowledge representation relies heavily on ontologies, yet these systems often suffer from "bloated" concept definitions that are redundant and difficult to maintain. This paper introduces a novel algorithm that computes the absolute smallest equivalent concept in $\mathcal{EL}$ logic. By utilizing Regular Tree Grammars (RTGs) and dynamic derivation rules, the authors transform a theoretically NP-complete problem into a practical tool capable of optimizing massive medical ontologies like SNOMED CT and GALEN in seconds or minutes.

Introduction: The Problem of Structural Complexity

In Description Logics (DLs), the $\mathcal{EL}$ fragment is the standard for large-scale biomedical ontologies. However, because these ontologies are often developed collaboratively over decades or generated automatically, they frequently contain "wordy" definitions with redundant logical intersections and existential quantifications. For instance, a definition for "Clotting" might redundantly list physical states of blood already covered by more concise terms. This bloat hinders human readability, increases computational overhead for reasoners, and complicates maintenance. While finding the minimal equivalent concept is known to be NP-complete, this work provides the first practical solution for large-scale systems.

Methodology: Dynamic Regular Tree Grammars

The proposed minimization algorithm is built upon the framework of Regular Tree Grammars (RTGs), enhanced by several key optimizations:

  1. Subsumer Grammars: The search space is restricted to "subsumers"—concepts more general than the target. The authors prove that a minimal equivalent concept for $\mathcal{EL}$ always exists within this set.
  2. Dynamic Derivation Rules: Unlike traditional static rules, the algorithm updates its derivation rules "on-demand" based on the specific context and non-terminal being processed. This innovation reduces the number of applied rules by approximately eight orders of magnitude.
  3. Aggressive Pruning: The search is constrained by Size Monotonicity (discarding branches that exceed the current best candidate's size) and Subsumption Monotonicity (discarding concepts too general to be equivalent).
  4. Irreducible Sets: The algorithm identifies minimal sets of equivalence classes to ensure no redundant conjuncts are included in the final output.
Example of concept sets and their subsumers used in the grammar construction.

Experimental Evaluation

The researchers evaluated the tool using 100 concepts from five major biomedical ontologies: SNOMED CT, GALEN, NCI Thesaurus (NCIT), FYPO, and Genomic CDS.

Experimental results across major biomedical ontologies showing reduction rates and processing times.

Key Results

  • Efficiency: For most ontologies (NCIT, Galen, FYPO), minimal concepts were found in seconds. Even for the massive SNOMED CT (320k+ axioms), the tool averaged approximately 5 minutes per concept.
  • Significant Redundancy: A notable proportion of concepts in every dataset were reducible. In GALEN, 100% of tested concepts with a size of 10 or more were found to have a smaller equivalent, with an average size reduction of 72%.
  • Search Space Optimization: The dynamic rule approach was critical, reducing the number of considered subsets by five orders of magnitude compared to baseline methods.

Discussion and Future Work

The study demonstrates that the hierarchical structure of real-world ontologies allows for efficient optimization of NP-complete problems. However, the current methodology is limited to $\mathcal{EL}$ logic and does not yet support negation, universal quantification, or disjunction. Future research will focus on extending these techniques to more expressive Description Logics and exploring global ontology refactoring to improve usability for medical professionals.

Summary updated

BibTeX
@inproceedings{nikitina2017small,
  author = {Nadeschda Nikitina and Patrick Koopmann},
  title = {{Small Is Beautiful: Computing Minimal Equivalent EL Concepts}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10684},
}
Figure