Completeness and Optimality in Ontology Alignment Debugging

Abstract

The bene t of light-weight reasoning in ontology matching has been recognized by a number of researchers resulting in alignment repair systems such as Alcomo and LogMap. While the general bene t of logical reasoning has been shown in principle, there is no systematic empirical evaluation analyzing (i) the impact of completeness of the reasoning methods and (ii) whether approximate or optimal solutions to the con ict resolution problem have to be preferred. Using standard benchmark data sets, we show that increasing the expressive power does improve the matching results and that optimal resolution methods slightly outperform approximate ones.

Keywords

• ontology matching
• expressiveness
• alignment debugging

-

Research in ontology matching has been strongly in uenced by earlier results in schema matching [ 19 ]. There are several approaches that aim at being universally applicable across ontologies and database schemas by relying on a representation of ontologies and schemas as directed graphs [ 1 ]. While various studies have veri ed the bene t of explicit, logical schema semantics such as description logics and logical reasoning (e.g. [ 17 ]), there is only a limited number of approaches that exploit schema semantics to improve matching results in a principled manner. Early approaches exploiting the logical structure of class descriptions were based on specialized similarity measures that take logical operators into account (e.g. [ 2 ]). Additional methods avoid structural properties that mimic unwanted reasoning results [ 6 ] or require user interaction [ 18 ]. More recently, a number of approaches have been proposed that explicitly use ontological reasoning. Meilicke et al., for instance, compute and leverage logical inconsistencies to eliminate con icts between alignment hypotheses [ 11 ]. A related approach was proposed by Jimenez-Ruiz et al. [ 7 ]. Additional debugging strategies remove incoherent alignments during a post-processing step [ 20, 13 ]. Giunchiglia and colleagues use reasoning over logic-based representations of class labels but solely focus on the problem of matching class hierarchies [ 4 ]. Most of these approaches exploit restricted forms of reasoning so as to ensure the scalability to large models. While these approaches demonstrated the bene ts of logical reasoning for matching expressive ontologies, there has not been a systematic investigation of the impact logical reasoning has on matching results. In particular, it is not obvious whether more expressive reasoning methods provide more bene ts than less expressive ones. Furthermore, the impact of applying di erent strategies for resolving detected logical con icts, has not been analyzed in details. Within this paper we report about experiments that shed light on both research questions. Another systematic evaluation is provided in [ 8 ], where the authors focus on the need of debugging and provide a comparison of two debugging systems, while we focus on completeness and optimality.

The paper is structured as follows. In Section 2 we explain alignment incoherence and introduce the notion of completeness and optimality with respect to alignment debugging. Moreover, we describe three existing debugging systems that we use in our experiments. We discuss the setting of our experiments in Section 3 with a focus on data sets and evaluation metrics. The results of these experiments are presented in Section 4. We close with a discussion in Section 5. 2

Incoherence in Ontology Matching

Ontology Matching is the task of nding correspondences between entities of two ontologies O1 and O2. According to [ 3 ], a correspondence between an entity e1 de ned in O1 and an entity e2 de ned in O2 is a 4-tuple he1; e2; r; ni where r is a semantic relation (such as equivalence), and n is a real-valued con dence value. A set of correspondences is called an alignment. In line with most matching systems and benchmarks, we focus on equivalence correspondences, i.e., (he1; e2; ; ni), where the matched entities are either both classes or properties. However, the overall approach can also be applied to any kind of axioms as long as these axioms are supported by the debugging system (e.g., all three systems used in our experiments support also subsumption axioms as correspondences).

An alignment A can be created by a human expert or by an automated matching system. In both cases, A might include erroneous correspondences. However, it is reasonable to assume that O1 and O2 do not contain erroneous axioms. For that reason, an alignment A can be interpreted as a set of uncertain, weighted equivalence axioms, while O1 [ O2 will comprise the certain axioms. Merging A, O1, and O2 can then result into an incoherent ontology, i.e. some of the classes of O1 or O1 might be unsatis able due to the additional information encoded in A. The following example shows an incoherent alignment.

O1 = fJaguar1 v Cat1; Cat1 v Animal1g; O2 = fJaguar2 v Brand2; Animal2 v :Brand2g A = fhJaguar1

Jaguar2; 0:9i; hAnimal1

Animal2; 0:95ig

In this example the classes Jaguar1 and Jaguar2 are unsatis able in the merged ontology. There are three possible ways to resolve this incoherence: (1) Discard both correspondences, (2) discard hJaguar1 Jaguar2; 0:9i, or (3) discard hAnimal1 Animal2; 0:95i. Obviously, we prefer (2) and (3) over (1). Moreover, it seems to make more sense to remove the correspondence that is less con dent, i.e., the most reasonable decision is (2) given no further information is available.

However, with larger matching problems a solution to the debugging problem becomes more complex for two reasons. First, not all con icts (= subsets of correspondences resulting in incoherence) might be detected. This might be caused by using an incomplete reasoning technique, for example, because only a certain type of axioms are analyzed. Second, the detected con icts might be overlapping and there are several ways to resolve the incoherence. In such a situation a solution should be preferred that removes as less con dence as possible. We call such a solution an optimal solution and de ne it as a subset A such that A n is coherent and there exist no other such that A n is coherent and Pc2 conf (c) > Pc2 conf (c). This de nition corresponds to the de nition of a global optimal diagnosis given in [ 9 ].

Note that optimality and completeness are independent characteristics of a debugging system. It is possible to construct a debugging system that is complete in terms of reasoning but cannot guarantee the optimality of the solution, while it is also possible to construct a system that is incomplete and optimal, in the sense that the solution is optimal with respect to all detected con icts, even though these con icts are only a subset of all con icts due to the incompleteness. Note also that the notion of optimality is a technical notion, i.e., an optimal solution might not always be the best solution in terms of precision and recall. 3 3.1

Experimental Set-Up

Datasets

The ontologies we use for the experiments are from the ontology alignment evaluation initiative (OAEI) [ 5 ]. We selected the conference and the large Biomed ontologies because these benchmarks are not arti cially created (unlike, for instance, the benchmarks dataset), are not focused on a narrow alignment problem (unlike, for instance, the multifarm dataset which is concerned with multilingual ontology matching), and provide coherent reference alignments. Moreover, the size of the large Biomed ontologies allows us to assess the scalability of the presented approach.

The conference dataset consists of 15 ontologies which model the domain of conference organization [ 21 ]. The number of classes, properties, and axioms of a particular type of 7 ontologies are listed in Table 1 ordered by increasing expressiveness. Every row in the table, with the exception of the last row, corresponds to one expressiveness level we used for the experiments (see Section 4.1). For the 7 listed ontologies, reference alignments were created for each possible pair, resulting in 21 ontology pairs with a reference alignment.

Since the ontologies in the Conference dataset are relatively small, we also performed experiments with the large BioMed ontologies. The corresponding classes properties subsumption + disjointness + domain and range restrictions + all other EL++ axioms every axiom data set consists of the Foundational Model of Anatomy (fma)3, National Cancer Institute Thesaurus (nci)4, and SNOMED clinical terms5 ontologies. Semantically rich and with thousands of classes, the problem of aligning these ontologies is one of the computationally most challenging in the OAEI campaign. For the 2013 OAEI campaign, only 12 out of 21 participating system con gurations were able to compute results for the three combinations. We used the \small fragment" matching problems of the track. For more details on these data sets we refer the reader to the OAEI track website6. The properties of the ontologies are summarized in Table 2. 3.2

Alignment Aggregation

For each of the matching tasks described above, there are several alignments available that have been generated by di erent matching system. We decided to aggregate these alignment for each matching task in a preprocessing step. Thus, we can work with large input alignments and can avoid an additional subsequent aggregation of the debugging results. We aggregated the results of all matchers participating in the 2013 OAEI campaign. For the conference benchmark, we included all matchers which performed better than the string equality baseline [ 5 ]. For the large BioMed benchmark, we included the results of the 6 matchers which were able to compute a solution for every combination [ 5 ]. The participants in the large BioMed track were allowed to submit results for different settings of their system. We always used the best results of each system in terms of f-measure.

The method of alignment aggregation resembles the approach described in [ 9 ]. For each pair of ontologies, we union the alignments A1; : : : ; Ai; : : : ; An of each matching system i to one alignment A. To that end, we rst span the con dence values w of each correspondence hw; ai in alignment Ai to the range of (0; 1]. This ensures that the con dence values of the individual matchers are scaled identically. We then compute the aggregated a-priori con dence values for a 3 http://sig.biostr.washington.edu/projects/fm/ 4 http://ncit.nci.nih.gov/ 5 http://www.ihtsdo.org/index.php?id=545 6 http://www.cs.ox.ac.uk/isg/projects/SEALS/oaei/2013/ classes properties subsumption + disjointness + domain and range restrictions + all other EL++ axioms every axiom (without annotations) correspondence as the normalized sum of all a-priori con dences of that correspondence. The average size of one alignment for the conference benchmark is 42 ranging from at least 29 to at most 60 correspondences. For the large BioMed benchmark, we obtain 3396 correspondences for the ontology pair nci and fma; 10760 for the pair fma and snomed; and 18842 for snomed and nci. 3.3

Debugging Systems

In our evaluation we present results for the debugging systems ELog, LogMap and Alcomo that we apply on the ontologies and alignments described so far. { ELog [ 16 ] is a reasoner for log-linear description logics, which o ers complete reasoning capabilities for EL++. ELog can be used for debugging ontology alignments (details can be found in [ 15 ]). Since ELog transforms the debugging problem to nding the MAP state of a Markov Logic Network, it guarantees the optimality of the solution, i.e., the MAP state corresponds to an optimal solution. However, ELog is not complete with respect to the full expressiveness of OWL DL. { LogMap [ 7 ] is a matching system including a component for alignment debugging. In our experiments we report only about applying this component and refer to it, for the sake of simplicity, as LogMap. This component translates the ontologies into a set of Horn clauses and applies the linear Dowling-Gallier algorithm for propositional Horn satisability multiple times for repairing. The algorithm is not optimal and to our knowledge also not complete against the OWL DL pro le. LogMap is known to be the most e cient debugging tool currently available (see for example [ 8 ]). { Alcomo [ 9 ] has speci cally been developed for the purpose of debugging ontology alignments. Alcomo can be used in a setting that ensures the completeness (for OWL DL) and the optimality of the solution. The optimality of the solution is guaranteed by applying an exhaustive search algorithm to check potential solutions. However, this setting is applicable only to small matching problems. Using a lightweight setting, Alcomo can also be applied to larger matching problems loosing both the features of optimality and completeness. 3.4

Metrics

F-Measure Precision and recall of an alignment A measure the correctness of A and the completeness of A, respectively. Both measures are de ned with respect to a given reference alignment or gold standard G. The F-measure is the harmonic mean of precision an recall. Precision P , recall R, and F-measure F can be formally de ned as

P = jA \ Gj ; jAj

R = jA \ Gj ; jGj and

F = 2 P R P + R : Number of Unsatis able Classes The number of unsatis able classes is proposed as a quality measure for ontology matching in [ 10 ]. It refers to the number of classes that are unsatis able in the merged ontology A [ O1 [ O2 where O1 and O2 are the matched ontologies and A is the alignment between them. The smaller the number of unsatis able classes the higher the quality of the alignment. We computed the number of unsatis able classes with the HermiT [ 12 ] reasoner since it is known from previous work [ 8 ] that HermiT outperforms other reasoners in the computation of unsatis able classes. Unfortunately, we were not able to compute the unsatis able classes for the nci and snomed pair under 5 hours and, thus, cannot provide the number of unsatis able classes for the large BioMed benchmark.

The conference benchmark experiments were performed on a virtual machine with 8 GB RAM and 2 cores with 2,4 Ghz. The large BioMed experiments were executed on a virtual machine with 60 GB RAM and 2 cores. 4 4.1

Experimental Results

Expressiveness

Within this section we report about experiments that include axiom types with increasing expressiveness. Within these experiments we use the ELog debugging system. For the lowest level of expressiveness, we only include subsumption axioms A v B. For the second level, we add disjointness axioms A u B v ?. For the third level, we include domain and range restrictions. Finally, for the most expressive level, we include all axioms representable with the DL E L++. The size of the resulting ontologies is shown in Table 1 and 2 presented in the previous section. The ELog debugging system is complete with respect to each of the resulting matching problems. However, with this approach we simulate di erent types of debugging systems that are restricted to exploit di erent levels of expressiveness. For example, on the second level we simulate a debugging 0:7 0:6 e0:5 r u s a e m f-0:4 0:3 0:20 0.05 0.1 0.15 0.20.5 1.0 threshold system that bases its reasoning techniques only on the inter-dependencies between subsumption and disjointness axioms. Note that we analyze results for the ontologies in their full expressiveness in the subsequent section.

Figure 1 and Figure 2 depict the results for the various levels of expressiveness and for di erent thresholds for the conference and large BioMed benchmarks, respectively. The x-axis shows the di erent thresholds that we applied prior to the debugging step. The results show that the di erences between the various levels are less pronounced for lower thresholds. Hence, we put a special emphasis on the threshold areas below 0:2 (for the conference benchmark) and below 0:7 (for the large BioMed benchmark) since results for higher thresholds were nearly identical. Please note that in Figure 1 the stepsize in each chart changes at threshold 0:2 from 0:01 to 0:1 since, beyond that threshold, there are only very few logical con icts.

We observe a positive correlation between increased expressiveness and Fmeasure scores. Considering only subsumption axioms results in lower scores compared to the setting with additional disjointness axioms. Even higher Fmeasures scores are achieved if domain and range restrictions are taken into account. The highest F-measure scores are obtained if we incorporate all E L++ axioms. This holds also true for the choice of a well-suited threshold in the range of 0:15 to 0:2 in case of the conference benchmark, where we clearly observe the bene ts of exploiting the full expressiveness of E L++.

As expected, the number of unsatis able classes (center gure of Figure 1) is higher for settings with decreased expressiveness. For the subsumption only con guration, we observe the highest number of unsatis able classes in the nal alignment. On the other hand, there are only few unsatis able classes for the E L++ setting. Aside from the F-measure results, this is another indication of an improved alignment quality. The reason why we obtain unsatis able classes at all for E L++ expressiveness is that the expressiveness of our underlying ontologies is higher than E L++. In case of the large BioMed benchmark the Hermit reasoner was not able to determine the number of unsatis able classes within 5 hours. Thus, we do not provide a graphic for this benchmark.

Also as expected, we observe an increase in running time (right gures) when the number of resolved con icts increases, since runtimes are higher for low thresholds. Furthermore, runtimes also increase with increasing expressiveness. This is in line with our expectation, because a higher level of expressiveness results also in the generation of a more complex optimization problem that needs to be solved when computing the most probable coherent ontology query.

In summary, the results show that the alignment quality increases with an increase in expressiveness. F-measure scores are higher and the number of unsatis able classes is lower if expressiveness increases. We can also conclude that 0:350 0.05 0.1 0.15 0.20.5 1.0 threshold a debugging system that is more complete in terms of the supported expressivity will generate better results compared to a less complete system. Runtimes, however, increase with higher expressiveness. This shows a trade-o between runtime and alignment quality depending on the choice of the supported expressiveness. 4.2

Approximate vs. optimal solutions

In this section, we experimentally address the question if optimal algorithms lead to higher quality than approximate algorithms. To that end, we compare the log-linear description logic system ELog and the optimal algorithm of Alcomo against the approximate algorithms of LogMap and Alcomo.7

The results for the conference and large BioMed benchmark are depicted in Figure 3 and Figure 4, respectively. Again, we focus on the discussion 7 Alcomo can be executed in di erent settings. We refer to the setting using the parameters METHOD OPTIMAL/REASONING COMPLETE as optimal algorithm. We refer to the setting METHOD GREEDY/REASONING EFFICIENT as approximate algorithm. However, this settings is both incomplete and does not generate an optimal solution. 0:8 0:7 0:6 e0:5 r u s ea0:4 m f 0:3 0:2 0:1 of results for thresholds below 0:2 (for the conference benchmark) and 0:7 (for the large BioMed benchmark).

The system ELog and the optimal algorithm of Alcomo gains the highest F-measure scores (left gures). The approximate algorithms of Alcomo and LogMap reach lower F-measure scores. The di erence in F-measure results between ELog and the optimal algorithm of Alcomo is due to the fact that the associated optimization problems often have more than one solution. Each of this optimal solution has the same objective, i.e. the con dence total of the resulting alignments is the same, but sometimes di erent F-measure scores. Thus, ELog might choose a di erent optimum than the optimal algorithm of Alcomo.

ELog has the highest number of unsatis able classes (center gure of Figure 3) of all three algorithms. However, having 53 inconsistent classes is only 1.7% compared to the total sum of classes of 2,973. As explained above, ELog is complete only for E L++. Thus, all inconsistencies were caused from axioms which are out of the scope of E L++. The results indicate that the restricted expressivity seems to be less important than the optimality of the solution, since ELog generates at the same time results with the best F-measure.

The approximate algorithms of LogMap and Alcomo are more e cient, especially for lower thresholds. In case of the conference benchmark, ELog outperforms the approximate Alcomo algorithm for thresholds higher than 0:15. Except for the thresholds of 0:11 and 0:12, the exact Alcomo algorithm is slower than ELog and does not terminate within one hour for thresholds below 0:09. For the large BioMed benchmark, the approximate algorithms are faster. For thresholds below 0:7 the exact Alcomo algorithm does not terminate within one hour. LogMap achieves by far the best runtime results, which is also supported by the results reported in [ 8 ]. This is (at least partially) caused by incomplete reasoning and non-optimal con ict resolution techniques.

The non-optimal variant of Alcomo and LogMap generate very similar alignments. This becomes obvious when comparing the F-measure scores presented in the left plots of Figure 3 and 4. Obviously, the systems show a similar bevaviour and seem to apply a similar con ict resolution strategy. The same observation can be made for the optimal variant of Alcomo and ELog. Thus, the distinction between optimal and non-optimal algorithms becomes visible in the threshold/F-measure plots, which supports the importance of this distinction.

Overall, we can conclude that optimal systems achieve higher F-measure scores than the approximate algorithms. With respect to runtime, the approximate algorithms are faster than the optimal approaches. In particular LogMap outperforms all other systems. Furthermore, ELog has shorter runtimes than the optimal algorithm of Alcomo. This is remarkable since LogMap and Alcomo are specialized on ontology matching. They leverage the fact that weighted axioms can only occur between ontologies and that those axioms are either subsumption or equivalence axioms. 5

Conclusions

Our experiments indicate that an increase in expressiveness leads to an increase in F-measure scores. Furthermore, the comparison of approximate and optimal ontology alignment repairing systems shows that optimal approaches achieve better F-measure scores. However, we observe a trade-o between F-measure and runtime. Runtimes are longer for higher expressiveness and optimal approaches have, on average, longer runtimes than approximate approaches. Thus, we advice users to employ optimal approaches for non-time critical data integration tasks. If real-time ontology alignment is required, we recommend the use of approximate approaches combined with reasoning techniques that might be incomplete.

References

1. Aumueller , D. , Do , H.H. , Massmann , S. , Rahm , E.: Schema and ontology matching with coma++ . In: Proceedings of the 24th International Conference on Management of Data (SIGMOD) . pp. 906 { 908 ( 2005 )

2. Euzenat , J. , Valtchev , P. : Similarity-based ontology alignment in OWL-lite . In: Proceedings of the 16th European Conference on Arti cial Intelligence (ECAI) . pp. 333 { 337 ( 2004 )

3. Euzenat , J. , Shvaiko , P. : Ontology matching. Springer ( 2007 )

4. Giunchiglia , F. , Shvaiko , P. : Semantic matching . Knowledge Eng. Review 18 ( 3 ), 265 { 280 ( 2003 )

5. Grau , B.C. , Dragisic , Z. , Eckert , K. , Euzenat , J. , Ferrara , A. , Granada , R. , Ivanova , V. , Jimenez-Ruiz , E. , Kempf , A.O. , Lambrix , P. , Nikolov , A. , Paulheim , H. , Ritze , D. , Schar e, F., Shvaiko , P. , dos Santos, C.T., Zamazal , O. : Results of the ontology alignment evaluation initiative 2013 . In: Proceedings of the 8th Ontology Matching Workshop . pp. 61 { 100 ( 2013 )

6. Jean-Mary , Y.R. , Shironoshita , E.P. , Kabuka , M.R. : Ontology matching with semantic veri cation . J. Web Sem . 7 ( 3 ), 235 { 251 ( 2009 )

7. Jimenez-Ruiz , E. , Grau , B.C. : Logmap: Logic-based and scalable ontology matching . In: Proceedings of the 10th International Semantic Web Conference (ISWC) . pp. 273 { 288 ( 2011 )

8. Jimenez-Ruiz , E. , Meilicke , C. , Grau , B.C. , Horrocks , I. : Evaluating mapping repair systems with large biomedical ontologies . In: Proceedings of the 26th International Workshop on Description Logics . pp. 246 { 257 ( 2013 )

9. Meilicke , C. : Alignment incoherence in ontology matching . Ph.D. thesis , University Mannheim ( 2011 )

10. Meilicke , C. , Stuckenschmidt , H.: Incoherence as a basis for measuring the quality of ontology mappings . In: Proceedings of the 3rd Ontology Matching Workshop (OM) ( 2008 )

11. Meilicke , C. , Stuckenschmidt , H. , Tamilin , A. : Repairing ontology mappings . In: Proceedings of the 22nd Conference on Arti cial Intelligence (AAAI) . pp. 1408 { 1413 ( 2007 )

12. Motik , B. , Shearer , R. , Horrocks , I. : Hypertableau reasoning for description logics . Journal of Arti cial Intelligence Research 36 ( 1 ), 165 { 228 ( 2009 )

13. Ngo , D. , Bellahsene , Z. , et al.: Yam++ -a combination of graph matching and machine learning approach to ontology alignment task . Journal of Web Semantics 16 ( 2012 )

14. Niepert , M. , Noessner , J. , Stuckenschmidt , H.: Log-linear description logics . In: Proceedings of the 22nd International Joint Conference on Arti cial Intelligence (IJCAI) . pp. 2153 { 2158 ( 2011 )

15. Noessner , J.: E cient Maximum A-Posteriori Inference in Markov Logic and Application in Description Logics . Ph.D. thesis , University Mannheim ( 2014 )

16. Noessner , J. , Niepert , M. : Elog: A probabilistic reasoner for owl el . In: Proceedings of the 5th Conference on Web Reasoning and Rule Systems (RR) . pp. 281 { 286 ( 2011 )

17. Noy , N. , Klein , M. : Ontology evolution: Not the same as schema evolution . Knowledge and Information System 6 ( 4 ), 428440 ( 2004 )

18. Noy , N.F. , Musen , M.A. : Algorithm and tool for automated ontology merging and alignment . In: Proceedings of the 17th National Conference on Arti cial Intelligence ( 2000 )

19. Rahm , E. , Bernstein , P.A. : A survey of approaches to automatic schema matching . VLDB Journal 10 ( 2001 )

20. Reul , Q. , Pan , J.Z. : Kosimap: Use of description logic reasoning to align heterogeneous ontologies . In: 23rd International Workshop on Description Logics DL2010 . p. 489 . Citeseer ( 2010 )

21. Svab , O. , Svatek , V. , Berka , P. , Rak , D. , Tomasek , P. : Ontofarm: Towards an experimental collection of parallel ontologies . Poster Track of ISWC ( 2005 )