MHS-MXP is an ABox abduction algorithm for DL, that leverages the divide-and-conquer strategy of the efective but incomplete MergeXplain and jointly uses the Minimal Hitting Set algorithm (MHS) to track the search-space exploration in order to ensure completeness. In this extended abstract we focus on our updated implementation which achieved a black-box combination of the abduction component and the JFact DL reasoner via the OWLKnowledgeExplorerReasoner interface of OWL API. We then present the results of our empirical evaluation showing that, compared to MHS, MHS-MXP has a significant advantage on favourable inputs, however, it does not perform as well as MHS on unfavourable inputs.
ABox abduction [
MHS-MXP is a “hybrid” abduction algorithm, that leverages the divide-and-conquer strategy
of the efective but yet incomplete MergeXplain [
We report on an updated implementation which fixes a serious flaw of the previous version, namely in the integration of the external DL reasoner. The flaw greatly limited the inputs the solver could correctly handle. MHS and MHS-MXP call an external DL reasoner for consistency checking and obtaining certain information about the model (specifically, the set of all atomic concept and role assertions that are true in the model); this task is referred to as “model LGOBE https://dai.fmph.uniba.sk/~pukancova/ (J. Pukancová); https://dai.fmph.uniba.sk/~homola/ (M. Homola)
© 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
extraction”. It is, however, highly non-standard for DL reasoners to output model information
(some of then may not even construct a model, e.g. consequence-based reasoners such as Elk [
In our current implementation, model extraction from the JFact reasoner is achieved via the experimental OWLKnowledgeExplorerReasoner interface of OWL API. We also report on an empirical evaluation that we were able to run on this implementation. It is conjectured that cases with a lower number of contradictory abducibles and those with smaller sizes of explanations and a lower overall count of explanations are favourable for MHS-MXP. It was also confirmed by our evaluation. On the other hand, on cases where the search space was clogged by large numbers of contradictory abducibles, MHS-MXP did not perform as well as MHS.
An implementation1 of the abduction solver was developed in Java. It implements the DL
Abducion API [
The solver relies on OWL API. DL reasoning, in the form of consistency checking and model extraction, is provided by an external DL reasoner. In the new version, we access the completion graph through an OWL API OWLKnowledgeExplorerReasoner2 interface implemented by the JFact reasoner3. In fact, it required some adjustments to make the interface work in JFact4.
Apart from the input ontology and the observation, the solver allows additional settings: the choice of abduction algorithm; a timeout; a depth limit for HS-tree exploration; and abducibles, either as a set of symbols or assertions. In the new version, it is also possible to toggle role assertions and role looping (role assertions of form (, ) s.t. ∈ and ∈ ) in explanations, and diferent ways how relevant explanation is defined for a multiple observation.
An example input file follows, in which the ontology is loaded from familyX.owl and the observation is set to Father(jack). In addition, the timeout is set to 14,400 seconds, and negations and role assertions in explanations are suppressed: -f: files/familyX.owl -o: Prefix: fam: <http://www.semanticweb.org/julia/ontologies/2017/8/family\#>
Class: fam:Father Individual: fam:jack Types: fam:Father -t: 14400 -n: false -r: false 1Available at https://github.com/boborova3/MHS-MXP-algorithm. 2https://owlcs.github.io/owlapi/apidocs_4/org/semanticweb/owlapi/reasoner/knowledgeexploration/ OWLKnowledgeExplorerReasoner.html 3https://github.com/owlcs/jfact 4The version we actually used is avalable at https://github.com/boborova3/jfact/tree/test4.
We evaluated5 the implementation of MHS-MXP against MHS. We conjecture that MHS-MXP
will perform better when the maximum size or the total count of explanations is lower. We used
the LUBM ontology [
The theoretical properties of MHS-MXP [
We observe that in the unfavourable case (Figure 1 (a,b)), both algorithms computed explanations up to size 3, but MHS-MXP achieved slightly worse results than MHS. This verifies our hypothesis that MHS-MXP is not able to handle large numbers of conflicting abducibles well.
On the other hand, in the favourable case (Figure 1 (c,d)), MHS-MXP achieved significantly better results than MHS, which performs similarly in both cases. All MHS-MXP groups except for S5 and C5 terminated successfully within the timeout. MHS-MXP managed to find all explanations. We also observe a correlation in the increase of computation time and the size of the largest explanation (groups S) and likewise for the explanation count (groups C). 5The evaluation was executed on a virtual machine with 8 cores (16 threads) of Intel Xeon CPU E5-2695 v4, 2.10GHz, with 32GB RAM, running Ubuntu 20.04 and Oracle Java SE Runtime Environment v1.8.0_201. Execution times were measured using ThreadMXBean from the java.lang.management package. We measured user time –- the actual time without system overhead. The maximum Java heap size to 4GB. Each input was run 5 times and the results were averaged for each group. The timeout was set to 4 hours (=14,440 seconds).
104 103 102 101 100 104 103 102 101 100 all S5 S4 S3 S2 S1 all S5 S4 S3 S2
S1 MHS
MHS-MXP
MHS
MHS-MXP
We have reported on the current implementation of the MHS-MXP ABox abduction solver and
its evaluation which demonstrated an advantage of MHS-MXP over MHS on a significant class
of inputs, particularly those where abducibles can be carefully configured by a knowledgeable
user (as not uncommon in real-world applications [
While there are currently approaches in ABox abduction [
This research was sponsored by the Slovak Republic under the grant APVV-19-0220 (ORBIS) and by the EU under the H2020 grant no. 952215 (TAILOR). J. Boborová was supported by an extraordinary scholarship awarded by Comenius University in Bratislava, Faculty of Mathematics, Physics and Informatics and by a DL student grant.