Finding Justifications by Approximating Core for Large-scale Ontologies

Mengyu Gao, Yuxin Ye, Dantong Ouyang, Bin WangIJCAI 2019 · DOI

TL;DR

This paper tackles the challenge of finding "justifications" (minimal sets of axioms) for inconsistencies in large-scale ontologies, which is crucial for debugging and understanding them. They propose a novel approach that uses a fast, approximate "local search" method to quickly identify a small subset of relevant axioms before employing a more computationally intensive exact method, leading to significantly faster justification finding for large ontologies.

What Problem Does This Paper Address?

Ontologies, which are formal representations of knowledge, often contain inconsistencies. Finding "justifications" for these inconsistencies is essential for debugging and understanding why an ontology behaves a certain way. Traditionally, this involves finding Minimal Unsatisfiable Subsets (MUSes) of the ontology's axioms. However, as ontologies grow larger and more complex (especially light-weight ones like those in the EL family), existing methods for finding MUSes become computationally prohibitive. This paper addresses the need for more efficient justification-finding techniques that can scale to these large, real-world ontologies.

Methods

The core of the proposed method is a two-stage approach. First, it employs a local search (LS) technique to find an approximating core. This LS is a heuristic, meaning it's not guaranteed to find the absolute smallest set of axioms but is much faster. The idea is that clauses (axioms) that are part of a justification are likely to be unsatisfied during a local search. This LS step aims to quickly narrow down the search space to a small, relevant subset of axioms.

Crucially, the paper states that this LS approach is complete in the sense that it always delivers a MUS for any unsatisfiable SAT instance, even though the intermediate "approximating core" might not be the absolute minimal justification. After identifying this approximating core, a more precise method (like SAT-based techniques for finding MUSes) is then applied to this reduced set of axioms. This significantly reduces the computational burden compared to applying the exact method to the entire ontology.

Datasets

The paper evaluates their approach on several large-scale ontologies:

  • NOT-GALEN
  • NCI
  • GO (Gene Ontology)
  • FULL-GALEN

These ontologies were preprocessed to be compliant with the EL+2SAT grammar, which involved removing comments and annotations and rewriting axioms syntactically. The experiments involved randomly selecting 20 queries for each ontology.

Key Insights and Ideas

  • Approximation for Speed: The key insight is that a fast, approximate method (local search) can effectively prune the search space for justifications, making the overall process much more scalable.
  • Local Search as a Pruning Tool: Local search, while heuristic, is surprisingly effective at identifying critical clauses that are likely to be part of a justification.
  • Scalability Benefit: The effectiveness of the local search approach is more pronounced as the size of the ontology increases, directly addressing the paper's motivation.
  • Completeness Despite Heuristics: The method maintains completeness for finding MUSes, meaning it will eventually find a valid justification, even though the intermediate "approximating core" is not necessarily the minimal one.

Key Results

The paper presents preliminary experimental results comparing their LS approach with Zcore (a SAT-based method for finding justifications).

  • Significant Speedup: The LS approach consistently achieved much faster computing times compared to Zcore. For example, on NOT-GALEN, Zcore took 0.260 seconds while LS took only 0.162 seconds. On the larger FULL-GALEN, Zcore took 12.85 seconds, and LS took 9.32 seconds.
  • Reduced Axiom Scope: The LS approach effectively reduces the number of axioms considered for justification finding from the original scale (e.g., 4th power of 10) down to the "single-digit level" for the approximating core.
  • Comparable Clause Sizes: The size of the delivered clauses (approximating core) by LS was often similar to those obtained by Zcore, indicating that the approximation did not drastically inflate the size of the potential justification.

Limitations and Future Work

  • Approximating Core vs. Exact MUS: The paper acknowledges that the "approximating core" found by LS is not necessarily the exact Minimal Unsatisfiable Subset (MUS). The LS step is a heuristic for pre-selection.
  • Future Work: The authors plan to use the "Insertion method" to calculate the MUS and then employ the method from [Ignatiev et al., 2017] to compute MUSes. Finally, these MUSes will be decoded into justifications for given queries. They expect these future experiments to yield substantial and practically valuable results.

Summary updated

BibTeX
@inproceedings{gao2019finding,
  author = {Mengyu Gao and Yuxin Ye and Dantong Ouyang and Bin Wang},
  title = {{Finding Justifications by Approximating Core for Large-scale Ontologies}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/905},
}
Figure