Ontology Classification is a central DL reasoning task and supported by several highly-optimised reasoners for OWL ontologies. Diferent notions of modularity, including the atomic decomposition (AD), have already been exploited by diferent modular reasoners. In our previous work, we have designed and implemented a new AD-informed and MORe-inspired algorithm that uses Hermit and ELK as delegate reasoners, but avoids any duplicate subsumption tests between these two reasoners. In this paper, we push the algorithm further with easyfication (checking subsumption tests in a module rather than in the whole ontology) and parallelization. We empirically evaluate our algorithm with a set of SNOMED CT extensions ontologies and a corpus of BioPortal ontologies. We also design, implement and empirically evaluate a new modular reasoner, called Crane, which works with “coarsened” AD.
Both approaches had successes but, even excluding decomposition time, they were not robust. While for certain ontologies they showed worthwhile improvement, sometimes they make things significantly worse. One hypothesis is that locality-based modules tend to overlap a lot thus potentially inducing repeated work. The only information communicated between classified modules is their final class hierarchy. To take an extreme example, if the ℰ ℒ++ module and the remainder module have 90% overlap, the ℛℐ-reasoner might take nearly as long on that as it would on the whole ontology and it would still have the cost of the ℰ ℒ++-reasoner on top. If the whole ontology took infeasibly long for the ℛℐ-reasoner to classify, then the modularisation was pointless.
In [19], diferent strategies for “chunking" a set of Chainsaw like modules were explored, attempting to mitigate the duplicated work problem. However, none of the strategies proved very robust or provide reliable improvements over a whole ontology approach.
Alternatively, one can abandon the black-box approach and modify a reasoner to communicate
partial results between classifications of diferent modules. In [
In this paper, we report on several new variants of the basic light-touch glass-box approach. In particular, we apply a (glass-box) Chainsaw like algorithm to the remainder module with and without parallelisation both for the most fine grained modules (Granular ReAD) possible and for a slightly coarsened set of modules (Crane). Somewhat surprisingly, we show that Crane, excluding decomposition time, shows near dominance over all our variants and both HermiT and a HermiT-MORe style system, often dramatically so. We also show that Crane is comparable with Konclude even including decomposition time on versions of SNOMED CT that has been enriched with disjunctive axioms.
These results suggest that glass-box approaches can realise the promise of modular reasoning.
We assume people are familiar with Description Logic [
In this paper, we use for an ontology, NC for a set of concept names and NR for a set of role names. A signature is a set Σ ⊆ NC ∪ NR of terms. For an axiom, a concept expression or an ontology , we use ̃︀ to denote its signature, i.e. the set of concept and role names. We use C() for the set of concept names in , and C+() = C() ∪ {⊥, ⊤} for concept names in together with ⊤, ⊥.
Modules based on syntactic or semantic locality [
The atomic decomposition (AD) A() [27, 22] partitions an ontology into logically inseparable sets of axioms, so-called atoms a, and relates these atoms via a dependency relation ⪰ . The principal ideal of a, defined as ↓ a = { ∈ b | a ⪰ b}, is a genuine module [27, 22].
In [
Ats() := MinAts() :=
CanS(a) := {a ∈ A() | ∈ ̃a︀} {a ∈ Ats() |̸ ∃b ∈ Ats() with a ≻ b} the lowest atoms of { | a ∈ MinAts() and #MinAts() = 1} an atom’s candidate set the atoms of BTop() := { | ∈ ̃︀ ∩ NC and #MinAts() > 1} concept names below ⊤ The candidate set CanS(a) of an atom a are those concept names for which STs need to be run for a, and concepts in BTop() have only trivial subsumers.
Definition 1.
[
Subs() := ⋃︀a∈A() Subs(a) ∪ {(⊤, ) | ∈ BTop()} ∪ {(⊤, ⊥)}.
As a consequence of the following theorem, a reasoner that tests only STs in Subs() during
classification will (a) test all required, non-trivial 2 STs and (b) never duplicate a test.3
Theorem 1. [
3It may, though, include a test (, ) in addition to (, ) and (, ). 2.2. Enhanced KP Algorithm, MORe and ReAD HermiT uses the Enhanced KP (EKPA) classification algorithm [28, 21]. It builds a completion graph with two sets of concepts pairs: One is known (K) subsumer pairs which records positive subsumption relations. The other one is remaining possible (P) subsumer pairs which contains remaining STs. The whole algorithm aims to empty P and increase K. HermiT aggressive strives to fill K whenever it performs a satisfiability check, whether directly on a concept name or as part of ST. For example, if the structures HermiT builds to test whether ⊑ allow it to determine that ⊑ it will add ⊑ to K and remove it from P.
MORe [
ReAD [
ReAD avoids repeating work done by the EL reasoner and exploits some information from the
AD in HermiT. But HermiT still remains a significant bottleneck. Thus, the natural next step is
to try to break down the remainder module into smaller, we hope in aggregate, easier modules.
3.1. Granular ReAD (ReADG)
Since we pre-compute an AD, we can use it to reason over a covering set of minimal modules
of RAs. Rather than checking RAs |=? ⊑ with (, ) ∈ Subs(a) and a ⊆ RAs, we
check ↓ a |=? ⊑ with (, ) ∈ Subs(a). For every genuine module ↓ a with a ⊆ RAs, we
initialize a modified HermiT which only checks Subs(a) and classifier ↓ a. One benefit for that
is that we can parallelize this procedure, called ReADGP. Algorithm 1 shows how ReADG works.
Compared to ReAD’s algorithm in [
Since ontologies tend to have lots of atoms, there is a risk that the overhead for “reasoner swap” (building the reasoner, initializing, and deleting the reasoner instances) will be significant. There are also three potential limitations for this approach due to interactions with other optimizations for classification. First, HermiT uses a Hypertableau algorithm as its ST engine and may get some "free" inferred subsumption relations from each ST.
4The diferences in deriving the EL and Remainder modules in the direct MORe or via a union of appropriate modules does not seem significant for classification. In our case, we have the AD so it is convenient to use the union technique.
module ℳRAs = ℳ(C+() ∖ ℳ˜︁EL, ) 3: Compute the ⊥-AℳRAs 4: ELAtoms := {a ∈ ⊥-A() | ↓ a is in ℰ ℒ++ 5: EL := ℳEL ∪a∈ELAtoms a 6: ℋ := Classify(EL) 7: for atom a ∈ RemainingAtoms 8: ℋ := ℋ∪ Classify ↓ a 9: end for 10: return ℋ Algorithm 1 ReADG Require: an ontology 1: Initialize a hierarchy ℋ := {(⊥, ⊤)} 2: use MORe approach to compute a (potentially large) ℰ ℒ++ module ℳEL and a remaining }
{Find all ℰ ℒ++ modules} {Compute union of ℰ ℒ++ modules}
{use ELK for this} {build a HermiT for ↓ a} do
{use modified HermiT only checks Subs(a)} {If a call to Classify found inconsistency, we would have exited early}
Some optimizations for STs like pseudo-model merging are not shared between reasoner instantiation.
Finally, ET-based algorithms avoid STs by exploring the transitivity of the (inferred) subsumption relation but these “transitive shortcuts” are included in Subs(). Hence we may lose this benefit of ET for these inferred subsumption relation.
Going more glass-box (e.g., caching completion graphs or pseudomodels) might help in some cases, but it may be that smaller is not always better. More fundamentally, computing the AD can be very expensive, often dwarfing classification time. While work is ongoing to optimise AD computation, for any AD approach to be reasonable, we have to assume that the AD is computed ofline and perhaps maintained through updates. While this is not particularly challenging, it is a change to the basic infrastructure. 3.2. “Coarsened” AD and Crane Motivated by these issues, we have experimented with using a “coarser" version of the AD. In [22], we find ADs are often very fine-grained and computing AD is, in particular, very costly despite it being in PTime. In our new system, Crane, we build “coarsened” AD as an approximation of the AD and use this for AD-based traversal and classification. Furthermore, we compute this coarsened AD on the fly interleved with classification call. This could be changed to a pre-computation strategy.
The general idea is to get coarsened AD and thus larger atoms and modules and classify them. When we classify a coarsened module, we check the subsumers of the concept names in this coarsened module. We have a global set ClassifiedCof concept names to record the concept names which are already checked for their subsumers.
We first compute the signature ΣEL from the MORe approach and use it to compute an ℰ ℒ++ module ℳ1 and a remaining module ℳ2. We use ELK to classify ℳ1. Now we already checked all subsumers of concept names in ℳ1. We add these concept names into ClassifiedC in line 4. In Algorithm 2, we make this genuine module coarsened so we get the module w.r.t the signature of several axioms. Here picking how many axioms to get the coarsened module is 12: 13: 14: 15: 16: crucial and a parameter to Crane. In our experiments, we have set this parameter to = 100. Then we can also further decompose these modules. Here we choose to further decompose these modules once. So we use the threshold 10 = 10 to extract smaller modules and then classify them.
We use HermiT version 1.3.8 5, Konclude [29] version v0.7.0-1135 6 as base reasoners in this
paper. We use our own implementation of a MORe-like approach (see [
We ran three experiments. The first two experiments are essentially expanded versions
of those in [
5http://www.hermit-reasoner.com 6https://github.com/konclude/Konclude
In the final experiment, we look at several versions of SNOMED CT which enrich the ℰ ℒ++ version to include disjunctions. These ontologies prove dificult to impossible for HermiT and MORe-like so we expand our comparison to include Konclude, which is capable of classifying all version. This experiment explores whether our modular optimisations applied to HermiT can be competitive with Konclude in an otherwise impossible for HermiT case.
We use OWL API [30] version 3.4.3, ELK version 0.4.2 andHermiT (modified as indicated) version 1.3.8 in all our systems. Crane also uses the module extraction code from MORe 7.
Most of experiments have been performed on Intel(R) Core(TM) i7-6700HQ CPU 2.60GHz RAM 8GB, called Mach1, running Java version 1.8 with an initial heap size of 1GB and a maximal heap size of 8GB. Time is measured in CPU time. All experiments related to Konclude have been performed on Intel(R) Core(TM) i7-5820K CPU 3.30GHz RAM 62GB, called Mach2, running Java version 1.8 JDK with an initial heap size of 1GB and a maximal heap size of 60GB.
Throughout these experiments, we report classification times excluding the time to compute modules or the AD even when interleaved in Crane, though we do report the Crane modularising time separately. This introduces a potentially misleading bias in our reporting that we strongly caution against. Indeed, if one is starting “cold", i.e., from an unmodularised input, one should presume that all systems with an unreported modularisation time might have taken longer, even much longer. While that is not always the case, it is often enough, especially for AD-based systems that it is the right bet.
We do this because we are trying to understand how exploiting modules afects the classification process itself. If an approach to exploiting modules does not win then the issue of modularisation overhead is moot.
Furthermore, there is an in principle solution to high modularisation cost: modularise “ofline" and amortise the cost. Since an AD based storage format and, indeed, AD-maintenance algorithms are both straightforward, it is reasonable to focus on classification itself. Plus, speeding up AD computation is ongoing with some promising eforts.
We report on Crane’s modularisation time since we had originally hoped that this coarsening time would reduce the modularisation overhead to negligible. It did not do that overall, but there are some interesting results aroudn that.
In this section, we re-use a corpus from 2017 NCBO BioPortal ontology already described in
[
7https://github.com/anaphylactic/MORe 8HermiT threw OutOfMemory exceptions or timed-out after 10 hours for 11 ontologies; it failed to handle 26 ontologies due to unsupported syntax or syntax errors.
We further discarded the 164 ontologies that are either purely ℰ ℒ++ (122 ontologies) or have no ℰ ℒ++ modules (42 ontologies)9 which leaves us 63 ontologies with non-deterministic tableaux graphs and 81 ontologies with deterministic tableaux graphs; for the latter, HermiT does not check STs as the concept name satisfiability tests produce, as a side-efect, all subsumers of each concept name. We use CT to represent the classification time and H, M, R, RG, RGP, C for HermiT, MORe-like, ReAD, ReADG, ReADGP and Crane respectively.
We show the results for deterministic ontologies in Table 1.
For the first three columns, we have roughly what we might expect: A MORe like approach shows, with some noise, some improvement over monolithic HermiT. ReAD does not show any systematic improvement over MORe. ReADG shows some dramatic improvements but also some odd reversals, especially for CHEBI and HRDP where it is an order of magnitude worse than the baseline! Parallelisation improves matters greatly but not quite enough to ensure dominance over baseline, at least, not with the number of cores we had available. Crane, on the other hand, dominates, and typically by two orders of magnitude. The catch is that if we include the modularisation time, Crane is hopeless. Thus, with current modularisation technology, Crane needs to ofline modularisation.
We might expect deterministic ontologies are the best case for HermiT and the worst case for any granular approach, but the results for non-deterministic ontologies, shown in Table 2, are startling.
HermiT, MORe, and ReAD show their usual pattern with somewhat less noise. But, ReADG shows quite bad behavior which parallelisation only mitigates in most cases. While throwing threads at a problem to get faster overall performance is reasonable, throwing lots of threads to just catch up with baseline is not.
Crane, excluding pre-processing time, continues its near dominance, only falling behind baseline with the ONL-MSA and behind ReAD with PHAGE. While dominant, the degree of 9These are, indeed, comparable with a MORe system. . . but it would reduce to a comparison with the expressive reasoner component and thus would not test glass vs. black-box issues. Testing against these ontologies is future work. dominance is less robustly significant. While sometimes it is 2 orders of magnitude faster, there are cases where it is merely a nice speed up or, for CAO, barely an improvement. By itself, these results do not clearly establish a case for requiring the infrastructure overhaul needed to mitigate the modularisation time, even for Crane. However, the fact that coarse-grain modules tend to dominate performance and often produce orders of magnitude speed ups suggests that investigating more ways to share information between classification of modules would be fruitful. Clearly, the finest grain modules disrupt something. but Crane shows that some level of module by module classifying is a big win. 5.3. SNOMED CT Experiment SNOMED CT [31] is a medical terminology ontology that describes the knowledge of health information and is used in medical records as a source of unambiguous, medicine processable terms.10 The oficial development of SNOMED CT is constrained to be in ℰ ℒ++ and is wellsupported by the reasoner ELK, e.g. the 2021-Jan-28 version SNOMED CT ontology is classified by ELK in only 11 seconds.
Extending the SNOMED CT ontology to be an expressivity beyond ℰ ℒ++ draws a lot of
interest in both academic research [
From conversation with a SNOMED CT developer, we found that 4 minutes to reclassify was about as much as they were willing to pay. They also helped derive three sets of more expressive axioms that they found desirable from a modelling perspective. We combined these with two versions of ℰ ℒ++ SNOMED CT to produce a test set.11 Note that this is the basic scenario that MORe was designed for: A mostly ℰ ℒ++ ontology with some more expressive additions. The base versions were from 2020-July (S20July) and 2021-Jan (S21Jan). We add the 9-axiom expansion to S20July and the other two to S21Jan. For some details of all versions, see Table 5.3. Note that the length of these ontologies is much larger than its “size" indicating a large average length of axiom.
The 9 axiom extension have axioms of two forms and was part of an initial proof of concept efort:
6 axioms of the form 4 ≡ 2 ⊔ 3, 5 ⊓ ∃1.(∃2.¬6 ⊓ ∃3.7 ⊓ ∃4.8 ⊓ ∃5.9)
The modelling scenario for the remaining versions is based on importing into SNOMED CT a modified version of an Anatomy ontology to incorporate a disjunction based approach to propagation of properties through part-whole relations (see [32] for an extensive discussion of the modelling problem and diferent ways of solving it).
The basic move is to replace axioms in Anatomy of the form:
≡ BodyStructure ⊓ ∃AllOrPartOf. ⊓ ∃Laterality.QualifierValue with ∈ StructureConcept, ∈ EntireConcept, with axioms of the form:
≡ BodyStructure ⊓ ( ⊔ ∃ProperPartOf.) ⊓ ∃Laterality.QualifierValue . One then deletes the corresponding atomic subsumptions between a StructureConcept and EntireConcept in SNOMED CT and imports the modified ontology. The deleted subsumptions are then entailed.
This produces an extremely dificult ontology even if, as we did, you only convert a random sample of 1000 style 1 axioms (SA21Jan1000). To make an intermediately dificult version (S21Jan7905), we extracted all 7,905 axioms in the Anatomy ontology of the form in Equation 1, modified them, and added them directly to SNOMED CT, discarding the rest of Anatomy. We also left in the relevant atomic subsumptions to (hopefully) ease matters. Thus we have three expressive versions of SNOMED CT of ascending dificulty.
Table 3 shows the number of TBox axioms in the variants of the SNOMED CT ontologies and the length of these ontologies. We notice these SNOMED CT ontologies all have axioms with a generally complex structure since the length of these ontologies is more than 5 times larger than their size. (1) (2) 5.3.1. Results As baseline, we note that ELK classifies S20July and S21Jan in 9 seconds and 12s respectively. In contrast to this, HermiT classifies these two ontologies with 5,199s (around 1.44 hours) and 5,929s (around 1.65 hours). All of the MORe descendents, including our own, show ELK like performance on these as the ℰ ℒ++module is the entire ontology.
Table 4 shows the results of classifying our three extended versions of SNOMED CT by our prior test systems (excluding non-parallel ReAD) with the addition of Konclude..
11Note, for historical reasons, we did not do a full cross product.
The first observation is that only Crane and Konclude handle all three versions. We see a variably steep slowdown for all reasoners across the samples. None of the reasoners approach the 4 minute mark for the most realistic version, in spite of it being only a partial conversion.
That said, Crane beats Konclude by at least an order of magnitude on pure classification time and shows a competitive time when modularisation time is included. Moreover, Crane uses much less memory, never exceeding 8GB even for the most dificult version while Konclude needs 29GB. 12 Finally, we can, in principle, improve Crane’s performance by scaling up the cores available. The dramatic improvement of granular ReAD over more for S21Jan7905 suggests that its optimisations do distinguish it if not robustly.
These results suggest that light touch, glass box modularisation is a useful optimisation approach even given the inconveniences of having to manage ontologies in a decomposed form. Further tuning of the coarseness factor in Crane needs to be explored and there may be a value that is efective across the board. Of course, once your ontology is modularised and classified, modular incremental algorithms can be used which may bring the re-classification time of even the most dificult versions of SNOMED CT to the 4 minute mark. Using Konclude as the delegate reasoner for the remainder module might accomplish that directly.
Understanding the causal story of the interaction of various granularities of modularisation with other optimisations is critical. If we can identify these factors we may be able to dervive a notion of module that is “right sized" for reasoning.
12We run experiments for Konclude with another machine with maximal heap size of 30GB since Konclude throw out of memory for 8GB heap size as we described in Section 4
Thanks to Dr Yongsheng Gao from IHTSDO for providing various SNOMED CT ontologies including how to enrich them beyond ℰ ℒ in a realistic way. [18] B. Glimm, I. Horrocks, B. Motik, G. Stoilos, Z. Wang, Hermit: an owl 2 reasoner, Journal of Automated Reasoning 53 (2014) 245–269. [19] N. A. Matentzoglu, Module-based classification of OWL ontologies, Ph.D. thesis, University of Manchester, 2016. [20] F. Baader, B. Hollunder, B. Nebel, H.-J. Profitlich, E. Franconi, An empirical analysis of optimization techniques for terminological representation systems: or:’making kris get a move on’, in: 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR-92), 1992, pp. 270–281. [21] B. Glimm, I. Horrocks, B. Motik, R. Shearer, G. Stoilos, A novel approach to ontology classification, Journal of Web Semantics 14 (2012) 84–101. [22] C. Del Vescovo, M. Horridge, B. Parsia, U. Sattler, T. Schneider, H. Zhao, Modular structures and atomic decomposition in ontologies, Journal of Artificial Intelligence Research 69 (2020) 963–1021. [23] S. Ghilardi, C. Lutz, F. Wolter, Did I damage my ontology? A case for conservative extensions in description logics, in: KR, AAAI Press, 2006, pp. 187–197. [24] B. Konev, C. Lutz, D. Walther, F. Wolter, Semantic modularity and module extraction in description logics, in: ECAI-08, 2008, pp. 55–59. [25] C. Lutz, D. Walther, F. Wolter, Conservative extensions in expressive description logics, in: IJCAI, 2007, pp. 453–458. [26] B. Cuenca Grau, I. Horrocks, Y. Kazakov, U. Sattler, Extracting modules from ontologies: A logic-based approach, in: H. Stuckenschmidt, C. Parent, S. Spaccapietra (Eds.), Modular Ontologies: Concepts, Theories and Techniques for Knowledge Modularization, volume 5445 of LNCS, SV, 2009, pp. 159–186. [27] C. Del Vescovo, B. Parsia, U. Sattler, T. Schneider, The modular structure of an ontology:
Atomic decomposition, in: IJCAI, 2011, pp. 2232–2237. [28] R. Shearer, I. Horrocks, Exploiting partial information in taxonomy construction, in:
International Semantic Web Conference, Springer, 2009, pp. 569–584. [29] A. Steigmiller, T. Liebig, B. Glimm, Konclude: system description, Journal of Web Semantics 27 (2014) 78–85. [30] M. Horridge, S. Bechhofer, The owl api: A java api for owl ontologies, Semantic web 2 (2011) 11–21. [31] S. Schulz, B. Suntisrivaraporn, F. Baader, M. Boeker, Snomed reaching its adolescence: Ontologists’ and logicians’ health check, International journal of medical informatics 78 (2009) S86–S94. [32] P. Seyed, A. L. Rector, U. Sattler, B. Parsia, R. Stevens, Representation of part-whole relationships in snomed ct, in: ICBO, Citeseer, 2012.