Comparing the importance of axioms in ontologies is an essential task in a variety of applications such as ontology repair and inconsistency management. It guides the choice of axioms to remain in the ontology or which should prevail when a con ict arises. While evaluating the importance of an axiom is di cult, there are di erent approaches to stratify ontologies by criteria that act as proxies for importance. However, there is little work about how these methods are related and their adequacy considering di erent applications. In this work, we evaluate speci city and modularity-based strati cation approaches, and work towards understanding how they relate. We compare empirically the result of ve strati cation methods over a corpus of real-world ontologies. In particular, we investigate correlations between their rankings and their ability to distinguish axioms.
When managing knowledge bases, users and designers are often confronted with the need to choose among con icting pieces of information. While the most reliable solution may be to delegate the choice to a domain specialist with information about the particular case at hand, this is not always possible, and thus many approaches propose the use of strati cation methods. Strati ed or prioritized knowledge bases are such that each axiom has a value that denotes its importance.
In the absence of further information, an axiom's importance is closely
related to its generality (or speci city), where none of these notions has a
commonly accepted de nition for complex axioms. Being able to stratify an ontology
by the importance of its axioms, will enable automatic repair algorithms [
The idea of strati cation or prioritization to solve choice problems in
knowledge bases is not new. It has appeared in repair and evolution of databases [
In this paper we consider OWL 2 DL ontologies [
The contributions described in this paper are two-fold: rstly, we devise metrics to measure the ability of these methods to distinguish between the axioms of an ontology and suitable statistical methods to measure correlation between these approaches. Secondly, we apply this framework to ve di erent strati cation methods and a corpus of existing ontologies, thereby gaining novel insights into their di erences, strengths and weaknesses.
Of the ve methods selected for this study, two encode speci city and three rely on the modular structure of the ontologies. Besides measuring correlation and axiom dispersion of these methods, we also discuss other aspects such as restrictions to applicability, feasibility and signi cance of the rankings produced. While we do not validate or compare directly proxies for importance, such as, speci city, generality and module preservation we will often refer to them to understand the strati cation methods considered. It turns out that the methods perform very di erently according to our metrics, and there are some interesting correlations between some strati cation methods.
This paper is accompanied by a technical report with more details about the
implementation of the experiments and additional results [
Before detailing the methods we evaluate, we present in this section some
fundamental concepts and establish conventions used through this work. We also
assume the reader to be familiar with description logics and its usual notation
(for more details we refer the reader to [
We call a set of terms (concept, role and individual names) a signature. Moreover, if O is an ontology, its signature ( sig(O) ) is the set of terms occurring in O. We extend the notion and de nition for axioms and sets of axioms.
Since we consider ontologies here as sets of formulas (bases) in a description
logic, we follow the approach adopted by Benferhat et al. [
The strati cation approaches we discuss in Section 3 are induced by a partial order of the axioms. Formally, if S is a set and a partial order on S then, the strati cation of S induced by is such that, for each a 2 S: rank(a) = 0; 1 + maxfb2Ojb ag rank(b); if a is minimal w.r.t.
otherwise 2.1
In this subsection, we brie y discuss the modularity approach underlying the strati cation methods that we selected for comparison.
The syntactic locality-based modules (LBMs) [
Given a signature , the locality-based module of an ontology O for the
signature is a subset of the ontology that has the same entailments as the
ontology over and all other terms that compose the module's signature. There
are two basic avours of LBMs: >-locality and ?-locality. They di er in the
syntactical rules applied to decide whether an axiom belongs to a module (due
to space constrains, we refer the reader to [
The atomic decomposition (or simply AD) of an ontology represents the set
of all locality-based modules of an ontology. The AD of an ontology consists of
a partitioning of the axioms (each partition called atom), according to their
cooccurrence in LBMs and a dependency relation between these, that is, a partial
order indicating that whenever an atom is a subset of a module, so are all atoms
that it depends on. As with LBMs, we denote the atomic decomposition of the
ontology O for the locality notion x 2 f?; >g by x-AD(O). Each atom in the
AD, together with the atoms it depends on, forms a genuine module, that is,
a locality-based module that is minimal w.r.t. set inclusion [
In this section, we present the strati cation methods selected for comparison.
We choose these methods because they only use the input ontology as parameter
and can be computed without human assistance.
3 http://owlcs.github.io/owlapi/
Axiom speci city (AxS) was described by Qi and Pan [
We extend the de nition of of speci city ( AxS) in [
Given the di erences between SROIQ(D) axioms and their OWL 2 DL
equivalents, in our implementation we handled each axiom type in a
straightforward way, more details are included in the technical report [
This method is syntax dependent, i.e., two ontologies O1 and O2 can have
equivalent axioms (for every 1 2 O1 there exists 2 2 O2, such that 1 2,
and vice versa), and yet have distinct strati cations. It is possible to change the
rank of an axiom by rewriting it in another way. Consider the axiom A u 9r:B v X,
a simple absorption, a common optimization in reasoners, would rewrite it
equivalently as A v 8r::B t X that is (usually) less speci c than its original version.
Moreover, this criterion ignores the right-hand side of axioms, hence in the
ontology O = fA v C1; B v C2; C1 v C2g, the axioms A v C1 and B v C2 would be
placed in the same stratum, even though we could say that the rst one is more
speci c than the because since A and C1 are subconcepts of C2 [
The dependency on classi cation to compute AxS also interferes with their
application on inconsistent ontologies, as the hierarchies collapse. But still, it
can be adapted to such cases [
We also de ne an alternative to AxS. First, we establish a partial order of concepts: C is more speci c than D (C v D) in O if O C v D, but O 6 D v C. Let rank(C) be the rank of the concept name C for all concept names in O in the strati cation obtained from v, then we say that 1 is more concept-speci c than 2 (written 1 CNS 2) in O if minC2 sig( 1) rank(C) < minC2 sig( 2) rank(C). The concept name speci city (CNS) is the strati cation of axioms induced by CNS.
Even though this approach does not display the same syntax sensitivity as axiom speci city for absorption, it fails to capture di erences between any pair of axioms whose most speci c concepts are at the same level of speci city. Moreover, it also has the same issues when applied to inconsistent ontologies as AxS. This dependency on the hierarchy of concept names also implies that the axioms without concepts (such as role inclusions) cannot be ranked by this method.
One notable way in which it di ers from AxS is the handling of the assertions: instead of considering all of them equally important, it also considers concepts involved. For instance if we have O = fA v B; A(a); B(b)g, the axioms A(a) and B(b) would attain the same rank by axiom speci city, however CNS would tell us that A(a) is more speci c than B(b). 3.3
x-AD Height
The last strati cation method we consider, proposed by Guimar~aes and
Wassermann [
In [
The height is a way to estimate which axioms participate of more or fewer
modules. An axiom with low height is more likely to be part of more genuine
modules and thus also of more general modules, via the dependency relations [
Proposition 1. Let O be an ontology, x 2 f?; >g a locality notion, 2 O an axiom and sig(O) a signature such that 62 x-LBM(O; ). Then, x-LBM(O n f g; ) = x-LBM(O; ).
This proposition is an immediate consequence of the fact that x-locality w.r.t. (and any of its extensions) during the computation of x-LBMs, is decided on a \per axiom" basis. As a consequence of Proposition 1, if x-AD then the removal of a ects more x-LBMs than the removal of . Therefore, axioms with lower heights can be said to be more in uential, thus more important.
As the locality-based modules and atomic decomposition are syntax-dependent, so are the x-AD heights and depths of the axioms. Therefore, all approaches we consider are syntax-dependent: AxS by ignoring the right-hand sides, CNS by considering only at the most speci c concept in the class signature and the ones based on the atomic decomposition due to the de nition of syntactic locality.
To conclude this section, we compare the selected strati cation methods illustratively with Example 1, which uses the ontology KoalaS from Table 1 and that is inspired by the ontology repair scenario.
Example 1. Consider the ontology KoalaS shown in Table 1 and suppose that we would like to restore coherence (the concept KoalaWithPhD is unsatis able) by removing a minimal set of axioms. Therefore, the candidates for removal are: 3, 5, 6 and 7. Removing any of them is enough to make the ontology coherent. TAH is unable to distinguish between them. Instead, if we follow axiom speci city, we would either remove 5 or 7, using CNS or BAD we would remove any of them, except 6, as KoalaWithPhD becomes the most speci c concept due to its unsatis ability. In contrast, since BAH is more likely to favour more general axioms (see Figure 1), it would tell us to remove (or x) 6.
In Table 1 and Figure 1 we also observe that BAH and AxS are mostly inverses of each other as we expected, if we ignore the concept assertions 8 and
Our rst methodological step is to formulate the research questions we aim to answer. The rst question is due to the fact that all strati cation methods produce partial orders and thus, do not guarantee that all the axioms have di erent ranks. It consists in determining how well these methods separate the axioms, i.e., how likely a strati cation approach is to help us pick a suitable axiom for a certain task. The second, is to verify if these methods are correlated.
Regarding dispersion, for each method, we are interested in measuring the number of strata in the whole corpus, their relative size and how many pairs of equivalent axioms exist after strati cation. The number of strata and their distribution by relative size (the percentage of axioms from the original ontology inside a stratum) show how often small and large strata occur for each method. The indistinguishable axioms rate (IAR) of a strati ed ontology is the proportion of pairs of axioms in the ontology that have axioms with the same rank, i.e., it measures how far the ranking is from a strict total order (the 0 IAR situation).
In the case of the ontology KoalaS from Table 1, we have for ?-AD height: 5 strata, with the smaller strata with approximately 11:11% of the axioms and the largest with around 33:33% of the axioms, and an IAR of roughly 0:1389.
For the second question, we test correlation between methods in two ways. First, we look at each ontology and measure the correlation between the rankings in each. Second, we normalize the ranks of the axioms in each ontology to the [0; 1] interval, join the results for the whole corpus and only then measure correlation. We call them local correlation and corpus correlation, respectively.
We choose Spearman's rank-order coe cient to measure correlation. This is a metric of monotonic association between two rankings that does not make assumptions about the distribution of the input data (i.e. is non-parametric). Its value ranges from 1 to 1 and expresses whether the association is direct or inverse. Values close 0 indicate weak or absent correlation. We will also refer to the p-values associated to the correlation measurements. The p-value indicates the probability of obtaining the same coe cient given that there is no monotonic association between the rankings, the null hypothesis for the Spearman's test. Smaller p-values mean that we have more grounds to reject the null hypothesis, thus the correlation is more statistically signi cant. 4.1
We want to answer our two research questions by looking at the strati cation over a corpus of realistic ontologies. Moreover, as we rely on reasoning to compute AxS and CNS, and on current module extraction algorithms, we only handle legal OWL 2 DL ontologies.
Among the possible corpus options, the set of ontologies hosted by
Bioportal4 stands out. This repository hosts ontologies from the biomedical domain,
many of them used in practical applications. The corpus of ontologies used in
this work is a subset of 272 ontologies out of the 438 from the Bioportal
snapshot at 30/03/20175. For brevity, we omit here other details about the corpus
and experiments which are available with additional plots, tables and discussion
regarding in uence of expressive power in the technical report [
5.1
We start our analysis of dispersion by looking at the cumulative histogram in Figure 2. For each method there is a line that can be read as the proportion of strata it produced that have size up to a certain fraction of the original ontology. Each bin corresponds to increments of 10% of relative size. In addition, since each method produces a di erent number of strata, the total number of strata in the corpus is shown as the N near the method label in the legend. 4 https://bioportal.bioontology.org/ 5 http://doi.org/10.5281/zenodo.439510 1.0 ity0.8 s n e D0.6 e v i t lau0.4 m u C0.2 AxS (N = 2367) CNS (N = 2087) BAH (N = 3838) BAD (N = 3830) TAH (N = 1512) of strata generated6, while TAH is notably the worst method in this aspect. Furthermore, BAH and BAD have the largest proportions of strata below the 20% mark and are the ones which gain the least as the relative size increases: the proportion of their strata with size 80% or more of the original ontology is negligible. In contrast, TAH has the largest proportions of bigger strata, almost 10% of the strata produced by this method has relative size of 90% or more.
The speci city-based approaches not only generated similar number of strata, but also resemble each other in the distribution of strata by relative size, as we can observe by the closeness between their histograms' curves and their trends.
In the technical report [
As discussed in Section 4, the IAR is one of the most important characteristics that we evaluate in this work, as it gives us a clear indication of how likely it is that each method improves our ability to choose between two axioms. Figure 3 displays one violin plot for each method, their external shape (the \violin") is the estimated probability density function (using kernel density estimation), cut at the range of the observations. The width of the violin indicates the probability of an ontology having the given IAR value, considering the sample distribution. The internal elements are boxplots marking from the centre to the extremities median, interquartile range and 95% con dence interval. 0.8 0.6 R A I0.4 0.2
AxS
CNS
BAH
BAD
TAH 6 The small di erent occurs because in atomic decompositions where the distance between the nodes at the top and the bottom is not unique (it depends on the pair of nodes), depth and height produce di erent number of strata.
From Figure 3, we can infer that the ?-AD height is the best approach regarding IAR, with more than a quarter of the 272 ontologies having IAR of less than 0:2. Additionally, the IAR of BAH in at least 75% of the corpus is below 0:5 and the probability density decreases rapidly at higher IAR values. While ?-AD depth also has 0 IAR in some cases, its distribution is centred on the median, which is close to 0:5 IAR, and it has also attained 1 IAR in the corpus. Excluding BAH, all methods reach 0:4 IAR in at least 50% of the ontologies.
As expected, AxS and CNS have similar IAR distributions. Also, we observe a small dominance of AxS over CNS, as the median and quartiles are marked at lower IARs. Still, given the proximity of both distributions and the higher variability of AxS when compared to CNS, we are not able to decide which one is better than the other from IAR alone. Neither speci city-based approaches nor >-AD height were able to produce any ranking with IAR smaller than 0:1, this is shown by the bottom limits of their (cut) violin plots. 5.2
We start our correlation analysis with the local version (as de ned in Section 4). Figure 4 shows violin plots (similar to ones presented in Figure 3). Each violin plot depicts the distribution of the Spearman's correlation coe cient between two metrics for each ontology in the corpus. To avoid counting results with low signi cance, we consider only instances of correlation for which the p-value was below 0.05, i.e., we only count situations whose probability of obtaining the same Spearman's coe cient under the null hypothesis was less than 5%. The value of N in the legend indicates, for each method, how many rankings out of the 272 for passed this criterion, for each pair of methods.
1.0 n o i t lea 0.5 r r o 'sC 0.0 n a rm-0.5 a e p S-1.0
H BA07 x 2 AxSN=
D BA46 x 2 AxSN=
S CN42 x 2 AxSN=
H TA06 x 2 AxSN=
BAD2 x 25 BAHN=
xCN22S4 BAHN=
xTA2H11 BAHN=
CNS9 x 23 BADN=
TAH6 x 19 BADN=
TAH87 x 1 CNSN=
As anticipated, CNS often has a very strong positive correlation with AxS and BAD, while AxS and BAD usually display a weaker, but considerable positive correlation. Generally, TAH correlates positively with CNS, AxS and BAD, but weakly. The correlations involving BAH are typically negative and weak, even though we would expect it to display stronger negative associations with BAD and TAH. We are con dent with these results since in all cases most ontologies displayed a signi cant correlation (p-value < 0.05).
Now we direct our attention to the corpus correlation (Table 2). We remind that we normalized each axiom rank to the interval [0; 1], took the union of all rankings and only then calculated the associations. For brevity, we omit the p-values because they were su ciently small (the largest at the order of 10 16).
We can observe in Table 2 some similar relationships to those seen in Figure 4. For example, the strong positive correlation between AxS and CNS and the average negative one between BAH and BAD. Also, there is a noticeable positive association between BAD and both AxS and CNS. The other interactions have values of correlation too close to zero to indicate any consistent association.
All results in this section re ect the behaviour of the methods in a particular corpus. It may be the case that the overall results di er if we consider ontologies from a di erent domain, or include more ontologies from the same corpus. 6
In this work we discussed desirable traits for strati cation procedures and evaluated ve distinct methods according to these criteria. We focused on axiom dispersion and correlation, devised suitable metrics to evaluate the methods and discussed the results obtained. The methodology we followed gives insight into a crucial component for automatic debug and repair of ontologies.
We observed that AxS and CNS displayed similar behaviour and signi cant positive association following our expectations. However, the same cannot be said about BAH and TAH. Besides the low correlation, their behaviour is very di erent regarding axiom dispersion: ?-AD height being one of the most successful according to our metrics, and >-AD height the worst in number of strata and relative size distribution. Interestingly, ?-AD depth had similar behaviour regarding dispersion as ?-AD height, but displayed a signi cant correlation with the speci city-based methods.
As future work we propose the extension of this study covering other strati cation approaches, including other metrics related to the atomic decomposition and other de nitions of speci city. Moreover, other characteristics of the stratication methods such as ease of interpretation and computational performance also need to be studied in detail. Such extended experiments will also include a larger and more diversi ed corpus and analyse whether the expressive power (i.e. the OWL 2 DL fragment considered) a ects performance and correlation.
Furthermore, the ability to distinguish axioms, feasibility and ideal of
importance can vary according to the application, thus evaluating the e ects of a range
of strati cation approaches in a particular setting, such as ontology repair, is
another possible direction. In this sense, some applications may also provide a way
to compare strati cation methods which depend on other parameters besides
the ontology itself (such as syntactic connectivity [