To repair or not to repair: reconciling correctness and coherence in ontology reference alignments

Abstract

A recent development in the eld of ontology matching is the alignment repair process, whereby mappings that lead to unsatis able classes are removed to ensure that the nal alignment is coherent. This process was showcased in the Large Biomedical Ontologies track of OAEI 2012, where two repair systems (ALCOMO and LogMap) were used to create separate coherent reference alignments from the original alignment based on the UMLS metathesaurus. In 2013, the OAEI introduced new reference alignments for this track, created by using the two repair systems in conjunction and manual curation when necessary. In this paper, we present the results of a manual analysis of the OAEI 2013 Large Biomedical Ontologies reference alignments, focused on evaluating the equivalence mappings removed by the repair process as well as those that were replaced by subsumption mappings. We found that up to two-thirds of the removed mappings were correct and that over 90% of the analyzed subsumption mappings were incorrect, since in most cases the correct type of relation was the original equivalence. We discuss the impact that disregarding correctness to ensure coherence can have on practical ontology matching applications, as well as on the evaluation of ontology matching systems.

Keywords

• Ontology Matching
• Alignment Repair
• Reference Alignment
• Biomedical Ontologies

-

Pesquita et. al challenge [ 6 ], since the most common type of ontology matching evaluation relies on the comparison of an alignment produced by an ontology matching system against a reference alignment. For smaller ontologies, reference alignments are manually built, and can then be subject to debugging and quality checking steps [ 7, 8 ]. However for very large ontologies this is unfeasible since the number of mappings that need to be manually evaluated grows quadratically with the number of classes in an ontology. Even if some heuristics are used to reduce the search space, the human e ort is still too demanding, especially when we are facing ontologies with tens or even hundreds of thousands of classes [ 9 ]. Consequently, e orts have been made to create reference alignments in an automated or semi-automated fashion [9{11]. One possible strategy to achieve this is based on existing resources from which the reference alignment can be derived. For the three tasks in the large biomedical track in OAEI, the reference alignments were created by processing UMLS metathesaurus entries. UMLS combines expert assessment with automated methods to connect classes from distinct biomedical ontologies and thesaurii according to their meaning.

However, the produced reference alignments lead to a considerable number of unsatis able classes when they are integrated with the input ontologies, and while the integration of FMA with NCI generates only 655 unsatis able classes, the integration of SNOMED CT and NCI leads to more than 20,000 unsatis able classes [ 12 ]. To address this issue, in OAEI 2012, in addition to the original reference alignment, two additional references were created by employing two di erent techniques to repair the logical inconsistencies of the original alignment, ALCOMO [ 13 ] and the repair facility of the ontology matching system LogMap [ 14, 10 ] (LogMap-Repair).

Ensuring that the alignment between two ontologies is coherent, i.e., that no class or property is unsatis able, has recently become a major focus for ontology matching. This is especially relevant when matching very large ontologies, which typically produce more unsatis able classes. To ensure the coherence of the alignment, a system needs to rst detect the incoherencies and then repair them, by removing or altering them, in order to improve the coherent alignment with minimum intervention. However, di erent repair methods can produce different alignments. For instance, Figure 1 depicts three con icting mappings in the original UMLS reference alignment for FMA-NCI. Each system removed two mappings to solve the inconsistencies caused by the disjoint clauses in NCI, but while ALCOMO removed mappings 2 and 3, LogMap removed 1 and 3. In this case, mapping 2 is correct. However the systems have no way of inferring this from the ontologies and alignment, since there are no mappings between the superclasses. For instance, if Anatomy Kind was mapped to Anatomical Entity, then this information could be used to disambiguate between Gingiva and Gum. The application of these techniques reduced the number of unsatis able classes to a few [ 1 ]. However, this automated process for repair is rather agressive, removing a signi cant number of mappings (up to 10%). In an e ort to counteract this, in OAEI 2013, the three reference alignments were re ned by using the two repair systems in conjunction and manual curation when necessary to ensure all Anatomical_Entity

Chemicals_and_Drugs_Kind

Anatomy_Kind

Properties_or_Attributes_Kind Gingiva

Gum

Gingiva

Gingival 1 2

3 1 removed by LogMap 2 removed by ALCOMO 3 removed by both inconsistencies were solved. This resulted in more complete and fully coherent reference alignments (see Table 1).

One of the strategies employed to achieve coherence and decrease the number of removed mappings is provided by LogMap. LogMap splits the equivalence mappings into two subsumption mappings and keeps the one that does not violate any logical constraints. This however, may result in mappings that do not re ect the real relationship between classes. Taking again as an example Figure 1, in the repaired alignment in OAEI 2013 all three mappings were replaced by subsumptions: FMA:Gingiva > NCI:Gingival, FMA:Gingiva > NCI:Gingiva and FMA:Gingiva > NCI:Gum. With this solution, the alignment becomes coherent since the relation is directional and the inconsistency is only caused by the disjoint clauses in NCI. However, none of the mappings are correct. These examples showcase that: 1) di erent repair techniques produce di erent repaired alignments; and 2) that solving inconsistencies with subsumption mappings can result in an erroneous alignment. In this paper, we discuss the results of a manual analysis of the OAEI Large Biomedical track reference alignments. We focused our analysis on the di erences between the original UMLS and the repaired alignments, in particular on the removed mappings and the ones altered to subsumptions. We also investigated the in uence of using the same repair technique to repair both the matching result and to repair the reference alignment.

The paper is organized as follows: Section 2 describes how we conducted our evaluation, Section 3 presents and discusses the evaluation; and nally Section 4 proposes future alternatives for the discussed issues. 2

Methods

To compare the repaired alignments of OAEI 2013 against the original UMLS, we manually evaluated all 41 subsumption mappings in FMA-NCI and 100 randomly chosen subsumption mappings of both FMA-SNOMED and SNOMEDNCI. The evaluation was conducted by two researchers with a biomedical background. We classi ed each mapping as: correct, incorrect or debatable. We consider mappings correct, not based on their compliance with ontological constraints, but based on their depiction of a real existing relation. For instance, we consider the FMA-NCI mappings between Visceral Pleura, Lung and Thoracic Cavity to be correct even if their integration with the ontologies leads to unsatis able classes.

Furthermore, we discerned between mappings where the right relationship would have been equivalence, from those that would have been incorrect with either a subsumption or an equivalence relation. We chose to include a debatable category for those mappings that raised disagreement between the experts, or that they deemed subject to interpretation. For instance, the mappings FMA:Hormone to NCI:Therapeutic Hormone or SNOMED:Child to NCI:Children. Our manual evaluation also included the veri cation of all removed mappings in FMA-NCI and FMA-SNOMED, and of 100 randomly chosen mappings in SNOMED-NCI. These were also classi ed into the three above-mentioned categories. In addition, we also repaired the original reference alignment with our novel repair technique (AML-Repair) [ 15 ] and evaluated the removed mappings. 3

Results and Discussion

ranges from 13% in FMA-SNOMED to 54% in FMA-NCI. Furthermore, considering that the majority of the mappings altered to subsumption by the OAEI 2013 repair are actually equivalences, these alterations do not actually improve the practical quality of the alignment, they just allow the alignment to become coherent without removing the mappings.

To complement this analysis we also repaired the original UMLS reference alignments with our own repair technique (AML-Repair). Compared to the OAEI 2013 repair, AML-Repair makes far more incorrect removals (see Table 3). However, when both removal and alteration are taken into account, AML has a higher percentage of correct repairs in both FMA-SNOMED and SNOMED-NCI. FMA-NCI

FMA-SNOMED

SNOMED-NCI

Equivalence removal

Alteration to subsumption

Correct

? Incorrect

Correct ?

Incorrect

Total correct 60 6 19 1 42 16 27 46 42 8 3 2 5 4 5 30 (26) 93 (73) 91 (73) 54.4 % 13.1 % 25.7 % ?: Debatable mapping. Numbers in ( ) correspond to mappings where the correct relation is equivalence.

These results mean that a large percentage of the removed or altered mappings were correct and that both repair techniques are in fact too aggressive. A fundamental issue here is that di erent ontologies can have di erent models of the same subject, and as such, a set of mappings that should be considered correct can render some classes unsatis able when the alignment is integrated with the ontologies. For instance, consider the mappings FMA:Fibrillar Actin = NCI:F-actin and FMA:Actin = NCI:Actin. Both mappings could be considered correct, but when they are integrated with the ontologies they cause an inconsistency. Figure 2 illustrates this issue. Since in FMA F-actin is a subclass of Actin and in NCI it is a subclass of Actin Fillament which is disjoint with Actin, the two mappings are in con ict. However, from the biomedical perspective it is arguable that both mappings are correct: F-Actin is the polymer micro lament form of Actin. The OAEI 2013 repair technique solves this issue by changing the relation type in the FMA:Actin=NCI:Actin mapping to subsumption. Since the only constraints violated by the mapping reside in the NCI ontology, by making the mapping one-way, this strategy restores the coherence to the alignment. However, FMA:Actin > NCI:Actin does not represent the true relationship between these classes, which is equivalence.

Anatomic_Structure_System _or_Substance Actin_fillament

F-actin

Gene_Product Microfilament_Protein

Actin plays_role_in Cell_Motility

Actin

Fibrillar_Actin isDisjointWith hasSubclass mapping

FMA NCI

So the question is: when creating a reference alignment through automated methods, what is best, an incomplete but coherent reference alignment, or a complete but incoherent one? The answer, we think, depends on the application of the alignment. If the nal goal of creating an alignment is to support the integration of two ontologies, then it is necessary to ensure coherence, so that the derived ontology is logically correct and supports reasoning. However, if the goal is supporting the establishment of cross-references between the ontologies to allow navigation between them, then an alignment that does not support linking FMA:Actin to NCI:Actin or reduces the relation to a subsumption would prevent a user from reaching the information that actin plays a role in cell motility. One of the underlying problems is that the existing repair techniques are not guaranteed to remove the incorrect mappings and may erroneously remove correct mappings. The reason for this is that the premise of removing the minimum number of mappings possible (either locally or globally) can fail in cases where there are as many or more incorrect mappings than correct mappings leading to unsatis able classes. Indeed, this is exempli ed in Figure 1, where ALCOMO erroneously removed the correct mapping. If we evaluated an alignment containing the correct mapping and not the incorrect ones against the ALCOMO-repaired reference, the alignment would be penalized twice: rst for having a mapping not present in the reference, and second for not including the erroneous mapping. This means that, even if the true alignment between two ontologies is coherent, by employing an automated repair technique to create a coherent reference alignment we risk excluding correct mappings, and thus providing a more misleading evaluation than if we used the unrepaired reference alignment.

This problem is ampli ed by the fact that two repair techniques may remove di erent mappings and arrive at di erent coherent alignments of comparable size, as exempli ed in Figure 1. Without knowing the true alignment, it is impossible to assess which repair technique produces the more correct alignment. However, if the di erences between the techniques are statistically signi cant, in choosing one technique to repair the reference alignment we may bias the evaluation towards that technique. More concretely, if two matching systems produce a similar unrepaired algorithm but use di erent repair techniques, the one that uses the same repair technique used to repair the reference alignment is likely to produce better results. This is illustrated in Figure 3, which shows two di erent repairs with techniques 1 and 2 of the same original reference alignment (A). When technique 1 is used to repair the alignment produced by a matching system, its overlap with the reference alignment repaired by 1 (B) is considerable greater than its overlap with the reference alignment repaired by 2 (C).

A related work argued that the di erences between repair techniques were on average negligible, by comparing the results of applying LogMap-Repair and ALCOMO to the top three systems that participated in the Large Biomedical track of OAEI 2012 [ 16 ]. Although the di erences between the repair techniques were indeed generally small in percentage, they re ect di erences in tens or even hundreds of mappings and can be signi cant in the context of the OAEI competition.

To demonstrate that the alignments produced by di erent repair techniques are statistically di erent, we performed a McNemar's exact test [ 17 ] comparing two sets of reference alignments: the OAEI 2012 reference alignments repaired by LogMap and ALCOMO, and the OAEI 2013 reference alignment with the original UMLS reference alignment repaired by AML-Repair. LogMap and ALCOMO disagree over 177 mappings and UMLS original and repaired di er in 78 mappings. The results in Table 4 show that there is indeed a statistical di erence between these sets of alignments, as the p-values obtained are clearly below the lowest signi cance intervals typically considered (0.01).

To empirically test the possibility that the repair technique selected to repair the reference alignment may lead to a bias in evaluation, we produced simple lexical-based alignments for the three tasks of the Large Biomedical Ontologies (by using AML on the small overlapping ontology fragments [ 18 ]). Then, we repaired these alignments using either LogMap-Repair or AML-Repair, and evaluated the repaired alignments against a set of reference alignments: original (UMLS unrepaired), LogMap-Repair (the original repaired with LogMap, as provided in OAEI 2012), and AML-Repair (the original repaired with AML-repair). The results of this evaluation are shown in Table 5. With the sole exception of the AML + LogMap-Repair in the FMA-SNOMED task, the best evaluation results in each task were obtained when the repair technique used to repair the alignment was the same that was used in the reference. Although the di erences between the various reference alignments were relatively small (usually below 1%) they are not irrelevant from the perspective of the OAEI evaluation, as the di erences between matching systems are often in this range. Thus, the repair technique used to repair the reference alignment can indeed lead to a biased evaluation. What is more, this encourages systems competing in OAEI to adopt existing repair techniques, rather than try to develop novel and potentially better alternatives. We posit that a reference alignment for evaluating ontology matching systems should not exclude potentially correct alignments. As we have shown in Figure 2, it is possible that the true alignment between two ontologies is not coherent. In such cases, repairing the alignment should only be considered if the ontologies are to be merged into an integrated resource, as otherwise repairing it implies losing correct mappings. However, even in the cases where the true alignment between two ontologies is expected to be coherent, the use of automatic repair techniques to build a reference alignment is likely to lead to the loss of some correct mappings. Penalizing a system that nds true hard-to- nd mappings because these happened to be removed during the repair of the reference alignment is certainly not desirable. The OAEI 2013 reference alignments attempt to minimize the number of mappings removed while still maintaining coherence by replacing equivalence relations with subsumption relations where necessary. But as we have shown, only a small fraction of these relationships are correct as subsumptions. In most cases, the original equivalence relation was correct, and in some other cases the mappings should not exist at all. On the other hand, using the original (unrepaired) reference alignments is not without issues because these do contain erroneous mappings. Going back to the example in Figure 1, a system that nds only the correct mapping would get a worst result than a system that found the two incorrect mappings if it were evaluated with the original reference alignment. The same would also be true if the system were evaluated with the OAEI 2013 reference alignment, as all three mappings are present in this alignment in the form of subsumptions (assuming the evaluation only considers the presence/absence of mappings and not their relationships).

We propose that a more impartial evaluation could bene t from the fact that existing alignment repair algorithms compute the sets of con icting mappings as part of their process. Mappings within these sets would be tagged as uncertain, and their presence or absence in the evaluated alignments would not be taken into account when calculating performance metrics. A similar approach has been proposed for cases where only a fraction of the possible mappings have been manually evaluated [ 19 ]. Coupling this approach with a satis ability check on the alignment would allow a more impartial evaluation w.r.t. the repair approach chosen by the matching systems. To illustrate this we have evaluated the AML, AML+AML-Repair and AML+LogMap-Repair alignments for FMA-NCI against an unbiased reference alignment where all con icting mappings (due to disjointness clauses) have been identi ed and their presence or absence is not considered in the evaluation. Table 6 presents these results, showing that repaired alignments have a higher precision without losing recall.

Conclusions

As ontologies become more prevalent, large and complex, so must ontology matching systems evolve and with them their evaluation strategies. A recent step in this direction has been the introduction of the large biomedical track in OAEI 2012, where the reference was automatically created by processing an external set of integrated vocabularies and then taking this unre ned alignment and repairing it to diminish its incoherence.

We have found that the repair technique employed to create the OAEI 2013 reference alignment, although less aggressive than the ones used in 2012, still removes a considerable portion of correct mappings and incorrectly alters equivalence mappings to subsumptions. Furthermore, we have shown that alignments repaired with di erent techniques are signi cantly di erent, which can have an impact on the evaluation of ontology matching systems. To decrease the impact of these issues on the evaluation of ontology matching systems, we have proposed an alternative for the evaluation of repaired alignments, where the presence or absence of con icting mappings is not accounted for. We consider that an alignment between two ontologies should enforce coherence, when the advantages of doing so outweigh the disadvantages, which depends on the application of the alignment and on the ontologies themselves. For instance, if the goal of an alignment is to support integration, then coherence is paramount. However, if the alignment is only intended to support a \lighter" connection between the ontologies (e.g., cross-references), then coverage is likely more relevant than coherence, especially if we consider the error rates of repair techniques. Moreover, when ontologies do not model con icting views of their domain, then a fruitful alignment between them should be coherent, and ensuring coherence can be a crucial step in ltering out errors. However, when ontologies have incompatible ontological models, their complete integration is impossible and enforcing coherence in their alignment will necessarily remove or alter correct mappings. How to best integrate ontologies with con icting views is still a debated question [ 20 ], and in some cases the goal might not even be a full- edged integration. We agree with the opinion expressed in [ 21 ] that to solve inherent incompatibilities between ontologies, expert intervention is necessary. However, some incompatibilities are unsolvable, and consequently a full coherent integration of the ontologies is impossible. To promote the usefulness of the alignments there should be room for alignments to contain mappings that violate constraints but are ultimately relevant. A next logical step is to investigate the best approach to support the encoding of these con icts in the alignment.

Acknowledgements

DF, CP, ES and FMC were funded by the Portuguese FCT through the SOMER project (PTDC/EIA-EIA/119119/2010) and the multi-annual funding program to LASIGE. CP was funded by the FLAD-NSF 2013 Programme under the project \Turning Big Data into Smart Data".

References

1. Eckert , K. , Ferrara , A. , Hollink , L. , Meilicke , C. , Nikolov , A. , Ritze , D. , Shvaiko , P. , Grau , B.C. , Zapilko , B. : Results of the Ontology Alignment Evaluation Initiative 2012 . ( 2012 ) 73 { 115

2. Euzenat , J. , Meilicke , C. , Stuckenschmidt , H.: Ontology Alignment Evaluation Initiative : six years of experience . Volume 6720 . ( 2011 )

3. Rosse , C. , Jr , L.V.M.: A reference ontology for biomedical informatics : the Foundational Model of Anatomy . Journal of Biomedical Informatics 36 ( 2003 ) 478 { 500

4. Schulz , S. , Cornet , R. , Spackman , K. : Consolidating SNOMED CT's ontological commitment . Applied Ontology 6 ( 2011 ) 1 { 11

5. Golbeck , J. , Fragoso , G. : The National Cancer Institute's thesaurus and ontology . Web Semantics: Science, Services and Agents on the World Wide Web ( 2011 )

6. Shvaiko , P. , Euzenat , J.: Ontology Matching: State of the Art and Future Challenges . IEEE Transactions on Knowledge and Data Engineering 25 ( 1 ) ( January 2013 ) 158 { 176

7. Lambrix , P. , Ivanova , V.: A uni ed approach for debugging is-a structure and mappings in networked taxonomies . Journal of Biomedical Semantics 4 ( 1 ) ( 2013 )

8. Beisswanger , E. , Hahn , U. : Towards valid and reusable reference alignments - ten basic quality checks for ontology alignments and their application to three di erent reference data sets . Journal of Biomedical Semantics 3 Suppl 1 ( 2012 ) S4

9. Giunchiglia , F. , Yatskevich , M. , Avesani , P. , Shvaiko , P.: A large scale dataset for the evaluation of matching systems . Knowledge Eng. Review (January) ( 2009 )

10. Jimenez-Ruiz , E. , Grau , B. , Zhou , Y. , Horrocks , I. : Large-scale Interactive Ontology Matching: Algorithms and Implementation . ECAI (ii) ( 2012 ) 444 { 449

11. Rosoiu , M. , dos Santos , C. , Euzenat , J.: Ontology matching benchmarks: generation and evaluation . In: 6th ISWC workshop on ontology matching (OM) . ( 2011 )

12. Jimenez-Ruiz , E. , Grau , B.C. , Horrocks , I. : Exploiting the UMLS Metathesaurus in the Ontology Alignment Evaluation Initiative . E-LKR Workshop ( 2012 ) 1{ 6

13. Meilicke , C. : Alignment incoherence in ontology matching . PhD thesis , University of Mannheim ( 2011 )

14. Jimenez-Ruiz , E. , Grau , B. : Logmap: Logic-based and scalable ontology matching . The Semantic WebISWC 2011 ( 2011 )

15. Santos , E. , Faria , D. , Pesquita , C. , Couto , F. : Ontology alignment repair through modularization and con dence-based heuristics . arXiv:1307.5322 ( 2013 )

16. Jimenez-Ruiz , E. , Meilicke , C. , Grau , B. , Horrocks , I. : Evaluating Mapping Repair Systems with Large Biomedical Ontologies . In: 26th International Workshop on Description Logics. ( 2013 )

17. Liddell , F.D. : Simpli ed exact analysis of case-referent studies: matched pairs; dichotomous exposure . Journal of Epidemiology and Community Health 37 ( 1 ) ( 1983 ) 82 { 84

18. Faria , D. , Pesquita , C. , Santos , E. , Palmonari , M. , Cruz , I. , Couto , F.M.: The AgreementMakerLight Ontology Matching System . In: ODBASE. ( 2013 )

19. Autayeu , A. , Maltese , V. , Andrews , P. : Recommendations for better quality ontology matching evaluations . In: AISB Workshop on Matching and Meaning . ( 2010 )

20. Schulz , S. , Rector , A. , Rodrigues , J. , Chute , C. , Ustun, B. , Spackman , K. : Ontology-based convergence of medical terminologies: SNOMED CT and ICD-11 . In: eHealth2012. ( 2012 ) 89 { 94

21. Jimenez-Ruiz , E. , Grau , B.C. , Horrocks , I. , Berlanga , R. : Logic-based assessment of the compatibility of UMLS ontology sources . Journal of Biomedical Semantics 2 Suppl 1 ( 2011 ) S2