Interactive Ontology Matching: Using Expert Feedback to Select Attribute Mappings

Abstract

Interactive Ontology Matching considers the participation of domain experts during the matching process of two ontologies. An important step of this process is the selection of mappings to submit to the expert. These mappings can be between concepts, attributes or relationships of the ontologies. Existing approaches de ne the set of mapping suggestions only in the beginning of the process before expert involvement. In previous work, we proposed an approach to re ne the set of mapping suggestions after each expert feedback, bene ting from the expert feedback to form a set of mapping suggestions of better quality. In this approach, only concept mappings were considered during the re nement. In this paper, we show a new approach to evaluate the bene t of also considering attribute mappings during the interactive phase of the process. The approach was evaluated using the OAEI conference data set, which showed an increase in recall without sacri cing precision. The approach was compared with the state-of-the-art, showing that the approach has generated alignment with state-of-the-art quality.

Keywords

• ontology matching
• Wordnet
• interactive ontology matching
• ontology alignment
• interactive ontology alignment

-

Ontology matching aims to discover correspondences (mappings) between entities of di erent ontologies [ 1 ]. One of its strategies is the interactive one. Interactive ontology matching approaches consider the knowledge of domain experts during the matching process. The interaction with the user can be used to improve the results over fully automatic approaches [ 2 ]. An important step of this strategy is the de nition of the set of mappings to be submitted to the expert for feedback. This set to be submitted to the expert was called, in this paper, set of mapping suggestions. Existing approaches [ 3 ][ 4 ][ 5 ][ 6 ][ 7 ][ 8 ][ 9 ][ 10 ][ 11 ][ 12 ][ 13 ][ 14 ][ 15 ] de ne this set before the interaction with the expert begins; thus, the approaches do not use expert feedback to select mappings to the set of mapping suggestions.

In previous work [ 16 ], we combined a structural and a semantic technique for interactively considering the expert feedback in the revision of the set of mapping suggestions, but taking into account only concept mappings. However, considering also the properties of these concepts may bring a better integration of the ontologies.

In this work, we propose ALINAttr to evaluate the bene t of also considering attribute mappings during the interactive strategy. The attribute mappings suggested are associated with the concept mappings evaluated by the expert; therefore, they are more prone to be correct and potentially increase the recall compared with existing strategies that automatically include attribute mappings [ 14 ][ 15 ].

The evaluation results evidenced the bene t of considering attributes during the interactive phase, using a heuristic for choosing the attribute mappings inspired on the Stable Marriage Problem [ 17 ][ 18 ]. In addition, the current approach was compared to the state-of-the-art.

The rest of this paper is organized as follows. Section 2 reviews interactive ontology matching. Section 3 presents the approach, which is called ALINAttr, and its implementation. Section 4 describes our evaluation methodology and discusses experimental results. Finally, section 5 concludes the paper. 2

Interactive Ontology Matching

An interactive ontology matching process is an ontology matching process considering the involvement of domain experts. In this paper, we consider this involvement as the domain experts providing feedback about mappings of ontologies entities, that is, mapping are presented to the expert who replies which of them should be accepted or rejected. Therefore, the approach takes advantage of the knowledge of domain experts towards nding an alignment.

The most relevant steps in this process are the selection of the mappings to receive expert feedback and the propagation of this feedback. Furthermore, the propagation may also impact the mappings selected for future expert feedback. The di erent existing approaches for interactive ontology matching vary in techniques for these two steps.

In the selection step, the existing approaches of interactive ontology matching use similarity metrics to select the set of mapping suggestions. The similarity metric is a function that returns a numeric value, indicating the similarity between the two entities of a mapping, according to some criterion. An approach can associate one or several similarity values, each of a di erent similarity metric, to a mapping.

In the selection step, the approaches can use multiple matchers, algorithms that receive, as input, entities and generate, as output, mappings. Each matcher can use di erent similarity metrics, among other features. At the end of the selection step, the results of these matchers can be combined and ltered generating the set of mapping suggestions [ 13 ].

In the propagation step, user feedback can be used in di erent ways. Some approaches automatically classify some mapping suggestions using a threshold, a value that indicates whether a mapping should be automatically accepted (in some cases rejected) if its similarity values are greater (or smaller) than it. Expert feedbacks are used to calculate this threshold [ 3 ][ 4 ][ 5 ][ 6 ][ 7 ]. Some approaches automatically classify some mappings of the set of mapping suggestions using a classi er. These approaches use expert feedbacks to create the training dataset for learning the classi ers [ 8 ][ 9 ]. Some approaches use expert feedbacks to modify the weight of similarity metrics [ 5 ][ 6 ][ 10 ] or to directly change the value of similarity metrics [ 11 ][ 12 ]. Expert feedbacks are also used to remove mapping suggestions from the set of mapping suggestions [ 13 ][ 14 ][ 15 ]. 3

The ALI NAttr Approach

In this section, we describe our approach, ALINAttr, for interactively matching two ontologies. ALINAttr, at each interaction, uses expert feedback to remove mapping suggestions and include new attribute mapping suggestions into the set of mapping suggestions.

The ALINAttr top-level algorithm (Algorithm 1) starts with a pair of ontologies (O and O0) and a set of similarity metrics (SoM). Then, it splits in two main steps. The rst one de nes the initial mapping suggestions (SMS) and the initial alignment (A) (line 1 to line 17 of Algorithm 1) and the second one interactively receives expert feedback to a mapping suggestion and propagate it (lines 18 to 29 of Algorithm 1).

The initialization step starts collecting all concepts of ontology O (SCO) and O0 (SCO0) and then for each similarity metric (SimM) a set of mapping suggestions is found using the simple matching algorithm (line 5 of Algorithm 1). This algorithm treats the matching problem as a stable marriage problem with size list limited to 1 [ 17 ][ 18 ], i.e., the algorithm only selects one mapping if similarity value between the two entities of the mapping is the highest considering all the mappings with at least one of these entities (Algorithm 2). At this moment only concept mappings, not property mappings, are chosen. The initial set of mapping suggestions is de ned as the union of the mapping suggestions found for each similarity metric (lines 6 to 10 of Algorithm 1). The mappings in which their entity names are the same are placed in the alignment and removed from the set of mapping suggestions (lines 12 to 17 of Algorithm 1). Moreover, ALINAttr inserts into the set of mapping suggestions attribute mappings associated with these concept mappings placed in the alignment (line 15 of Algorithm 1). The approach uses the structural attribute selection technique, which will be explained later, to choose the attribute mappings.

After de ning the initial set of mapping suggestions and the initial alignment, ALINAttr moves to the interactive step, in which the mapping suggestions receive the feedback of the expert (line 20 of Algorithm 1). If the expert accepts a mapping suggestion, then it is included in the alignment (line 23 of Algorithm 1). ALINAttr simulates the expert feedback by accessing a reference alignment. Session 4 further explains the reference alignment.

Up to this point, as we use several similarity metrics and the set of mapping suggestions is the union of the formed sets made for each metric there may be mappings with one of the entities equal. Since we want to generate a one-to-one alignment, once one of these mappings is accepted, the others will be rejected and removed from the set of mapping suggestions (line 24 of Algorithm 1) It is worth noting that ALINAttr uses expert feedback to reject these mappings. If ALINAttr would automatically reject these mappings, it would probably make mistakes.

At this point, the ALINAttr approach uses the structural attribute selection technique which will try to select, based on expert feedback, the best attribute mappings to be included into the set of mapping suggestions. The assumption behind the structural attribute selection technique is that if the attributes in an attribute mapping are attributes of concepts of a concept mapping, then this attribute mapping is more likely to be correct.

Algorithm 3 describes the structural attribute selection technique. It considers all attributes of the concepts of the input accepted mapping (lines 1 and 2 of Algorithm 3) and for each similarity metric it uses the simple matching algorithm to de ne attribute mapping suggestions. The output of the algorithm is the union of the set of attribute mappings found for each similarity metric.

Instead of selecting mappings between concepts of the two ontologies, like in the ALINAttr top-level algorithm, the structural attribute selection technique (Algorithm 3) uses the simple matching algorithm (Algorithm 2) to select mappings between attributes of the concepts in an accepted mapping. The use of the simple matching algorithm proved to be e cient in choosing the attribute mappings to be inserted in the set of mapping suggestions, as will be shown later in this paper.

ALINAttr was implemented in Java using the following Java APIs: Stanford coreNLP API [ 19 ] with a routine to put a word in canonical form; Simmetrics API [ 20 ], with string-based similarity metrics; HESML API [ 21 ], with Wordnet [ 22 ] based linguistic metrics; And the Alignment API [ 23 ], which contains routines for handling ontologies written in OWL. The most frequent synsets of words are used to calculate semantic similarities. To nd this synset is used the WS4J API3. 4

Experimental Evaluation

In this section, we evaluate our approach for interactive ontology matching considering attribute mappings. 4.1

Con guration of the experiment

The evaluation is designed towards answering three research questions: RQ1: Does the consideration of attribute mappings improve the quality of the nal alignment? RQ2: Does the use of expert feedback for the inclusion of attribute mappings in the set of mapping suggestions improve the quality of the nal alignment? RQ3: Does the simple matching algorithm between the attributes of the concepts improve the quality of the nal alignment?

The quality of an alignment is generally measured by F-measure, which is the harmonic mean between recall and precision. In an interactive approach another quality metric should be taken into account, the number of interactions with the expert that was necessary to achieve the alignment. The lower the number of interactions, the better. Thus, the two quality metrics were used to answer the research questions in this work. 3 'WS4J'. Available at https://github.com/Sciss/ws4j Last accessed on Jan, 16, 2018.

Towards answering these questions, some variations of ALINAttr were considered:

ALINW Attr: This variation didn't take into account attribute mappings, i.e., only concept mappings compose the set of mapping suggestions. For that, the ALINW Attr variation removes the calls for the structural attribute selection technique (Algorithm 3) in line 15 and from line 25 to line 27 of the ALINAttr top-level algorithm (Algorithm 1).

ALINAttrAuto: This variation includes the attribute mappings only in the initialization step, i.e., not considering expert feedback. For that, the ALINAttrAuto variation removes the calls for the structural attribute selection technique (Algorithm 3) in line 15 and from line 25 to line 27 in the ALINAttr top-level algorithm (Algorithm 1) and includes a call for attribute inclusion technique for ALINAttrAuto (Algorithm 4) in the ALINAttr top-level algorithm (Algorithm 1) after line 17.

ALINAttrF Back: This variation includes all attribute mappings related to the accepted concept mapping into the set of mapping suggestions, i.e., this variation doesn't use the simple matching algorithm (Algorithm 2) to reduce the number of included attribute mappings. For that, the ALINAttrAuto variation makes a call to the structural attribute selection technique for ALINAttrF Back (Algorithm 5) instead of a call to the structural attribute selection technique (Algorithm 3) in lines 15 and 26 of the ALINAttr top-level algorithm (Algorithm 1).

OAEI provides several data sets, which are sets of ontologies, to be used in the evaluation of ontology matching tools. From the data sets provided by OAEI, the only one that contained documentation of attributes and that had size that allowed the execution of ALINAttr is the conference data set. Therefore, the conference data set was used to evaluate the approach. OAEI provides reference alignments, which are alignments that contains the mappings that are believed to be correct, between the pairs of the ontologies of the conference data set. In the ALINAttr approach, a reference alignment query simulates the consult to the expert. The selection of the similarity metrics was based on two criteria: available implementations and the result of these metrics in assessments, such as those carried out in [ 24 ] and [ 25 ]. Based on [ 24 ] and [ 25 ], ALINAttr uses Jaccard, Jaro-Wrinkler and n-gram string-based metrics and the Resnick, Jiang-Conrath and Lin linguistic metrics. Resnick, Jiang-Conrath and Lin are metrics that require a taxonomy to be computed [ 24 ], this taxonomy being provided, in this algorithm, by Wordnet [ 22 ]. 4.2

Results

The results in terms of number of interactions (NI), precision, recall and F-measure can be seen in Table 1.

Total of questions NI Precision F-measure Recall ALINW Attr ALINAttrAuto ALINAttrF Back

ALINAttr 1183 1574 1321 1242 582 739 631 614 0.921 0.905 0.924 0.924 0.783 0.809 0.817 0.815 0.692 0.741 0.741 0.738

In each interaction with the expert, up to three mapping suggestions can be presented, since each mapping suggestion has one entity in common with another mapping suggestion of the interaction [ 26 ].

Comparing ALINW Attr with the other three approaches, that considered attributes mappings, we can see the improvement in the recall, which was expected since other mappings were evaluated. It is also possible to notice an increase in the number of interactions with the expert. Therefore, the inclusion of attribute mappings without taking into account the expert feedback generates an increase in the F-measure, but also an increase in the number of interactions with the expert leading to an inconclusive answer to the RQ1 question.

Comparing ALINAttrAuto, which did not take into account the feedback of the expert, with ALINAttrF Back and ALINAttr, which considered it, we can observe an improvement in the F-measure and a decrease in the number of interactions with the expert. This demonstrates that using expert feedback is a good practice, answering positively RQ2. It is important to note that it was assumed that the expert did not make mistakes. Therefore, these results are valid when the expert makes no mistakes.

Addressing RQ3, i.e., comparing ALINAttr with ALINAttrF Back towards evaluating the bene t of reducing the number attribute mappings by using the simple matching algorithm, we observed a decrease in the number of interactions with almost no loss of quality of the alignment, what answer positively to the RQ3 question. 4.3

Comparison between tools that participated in the OAEI interactive conference track

OAEI annually provides a comparison between ontology matching tool performances, and one ontology group used is the conference dataset, used in this paper [ 31 ]. Table 2 depicts a comparison between some the tools that participated in the OAEI 2017 interactive conference track and ALINAttr and ALINAttr+Syn.

The tools AML, LogMap, and XMAP (Table 2) are interactive ontology matching tools. This tools, like ALINAttr, include attribute mappings in the generated alignment but this inclusion is done in a non-interactive way, not taking into account the expert feedback.

The Table 2 depicts results with the expert hitting 100% of the answers. The results showed that ALINAttr generated a high level result when running the conference data set when the expert hit 100% of the answers, but with a very large number of interactions when compared to the other tools.

To verify the quality of ALINAttr if it uses a number of interactions more compatible with the other tools, two techniques, described in [ 16 ], were added to ALINAttr. In [ 16 ], these techniques proved to be very e cient in reducing the number of interactions without signi cantly reducing quality. The inclusion of the two techniques generates the results shown on line 'ALINAttr+Syn' of Table 2 and shows that, as the quality as the number of interactions, ALINAttr+Syn is good when compared to other tools. 5

Conclusion

Ontology matching is a necessary step for establishing interoperation among semantic web applications. Its purpose is to discover mappings between the entities of at least two ontologies. The quality of an alignment generated by a matching approach is generally measured by F-measure, which is the harmonic means between recall and precision. Another quality metric, when the ontology matching process is interactive, is the number of interactions with the expert.

An important step in the process of interactive ontology matching is the de nition of the set of mapping suggestions, that is, the set of mappings that will be shown to the expert. The problem seen in this paper is how to e ciently include attribute mappings into the set of mapping suggestions. The ALINAttr approach includes attribute mappings taking advantage of the expert feedback, of the structures of the involved ontologies, as well as the use of the simple matching algorithm. Experimental results showed the bene t of the approach when assuming that the expert does not make mistakes.

In addition, the quality of the alignment provided by ALINAttr was compared to state of the art tools that have participated in the track of interactive ontology matching in OAEI 2017. The results obtained show that ALINAttr generates an alignment with a good quality in comparison to other tools, with regard to precision, recall and F-measure, when the expert never makes mistakes, but with a number of interactions far superior to other tools. When performed with techniques to decrease the number of interactions, the number of interactions was compatible with that of the other tools, preserving a good quality.

As future work, one interesting direction is to explore how to reduce the negative e ects of expert mistakes. The ALINAttr generates good results when the expert does not make mistakes, but because the approach uses the expert feedback as the input of the structural attribute selection technique, probably incorrect attribute mappings will be generated when the expert makes a mistake.

Acknowledgement

The second author was partially funding by project PQ-UNIRIO No01/2017 ("Aprendendo, adaptando e alinhando ontologias:metodologias e algoritmos.") and CAPES/PROAP. The fourth author was partially funding by 'CNPq Special visiting researcher grant (314782/2014-1)'.

References

1. Euzenat , J. , Shvaiko , P. : Ontology Matching - Second Edition . Springer-Verlag ( 2013 )

2. Paulheim , H. , Hertling , S. , Ritze , D. : Towards Evaluating Interactive Ontology Matching Tools. Lecture Notes in Computer Science 7882 ( 2013 ) 31 { 45

3. Paulheim , H. , Hertling , S. : Wesee-match results for oaei 2013 . In: Proceedings of the 8th International Conference on Ontology Matching - Volume 1111. OM'13 , Aachen , Germany, Germany, CEUR-WS.org ( 2013 ) 197 { 202

4. Hertling , S. : Hertuda results for oeai 2012 . In: Proceedings of the 7th International Conference on Ontology Matching - Volume 946. OM'12 , Aachen , Germany, Germany, CEUR-WS.org ( 2012 ) 141 { 144

5. Duan , S. , Fokoue , A. , Srinivas , K. : One size does not t all: Customizing ontology alignment using user feedback . In Patel-Schneider, P.F. , Pan , Y. , Hitzler , P. , Mika , P. , Zhang , L. , Pan , J.Z. , Horrocks , I. , Glimm , B., eds.: The Semantic Web { ISWC 2010 , Berlin, Heidelberg, Springer Berlin Heidelberg ( 2010 ) 177 { 192

6. Shi , F. , Li , J. , Tang , J. , Xie , G. , Li , H. : Actively learning ontology matching via user interaction . In Bernstein, A. , Karger , D.R. , Heath , T. , Feigenbaum , L. , Maynard , D. , Motta , E. , Thirunarayan , K., eds.: The Semantic Web - ISWC 2009 , Berlin, Heidelberg, Springer Berlin Heidelberg ( 2009 ) 585 { 600

7. Chunhua Li , Zhiming Cui , P.Z.J.W.J.X.T.H. : Improving ontology matching with propagation strategy and user feedback . In: Seventh International Conference on Digital Image Processing (ICDIP 2015 ). Volume 9631 . ( 2015 ) 6

8. Lopes , V. , Bai~ao, F. , Revoredo , K. : Alinhamento Interativo de Ontologias Uma Abordagem Baseada em Query-by- Committee . Master's thesis , UNIRIO ( 2015 )

9. To H., I.R. , Le , H. : An Adaptive Machine Learning Framework with User Interaction for Ontology Matching . Twenty- rst International Joint Conference on Arti cial Intelligence ( 2009 )

10. Balasubramani , B. , Taheri , A. , Cruz , I.: User involvement in ontology matching using an online active learning approach . In: CEUR Workshop Proceedings . Volume 1545 ., CEUR-WS ( 2015 ) 45 { 49

11. Cruz , I.F. , Stroe , C. , Palmonari , M. : Interactive user feedback in ontology matching using signature vectors . In: 2012 IEEE 28th International Conference on Data Engineering. (April 2012 ) 1321 { 1324

12. Cruz , I.F. , Loprete , F. , Palmonari , M. , Stroe , C. , Taheri , A. : Pay-as-you-go multiuser feedback model for ontology matching . In Janowicz, K. , Schlobach , S. , Lambrix , P. , Hyvonen, E., eds.: Knowledge Engineering and Knowledge Management , Cham, Springer International Publishing ( 2014 ) 80 { 96

13. Lambrix , P. , Kaliyaperumal , R.: A Session-based Ontology Alignment Approach enabling User Involvement . Semantic Web 1 ( 2016 ) 1 { 28

14. Faria , D. , Pesquita , C. , Santos , E. , Palmonari , M. , Cruz , I.F. , Couto , F.M.: The agreementmakerlight ontology matching system . In Meersman, R., Panetto , H. , Dillon , T. , Eder , J. , Bellahsene , Z. , Ritter , N. , De Leenheer , P. , Dou , D., eds.: On the Move to Meaningful Internet Systems: OTM 2013 Conferences , Berlin, Heidelberg, Springer Berlin Heidelberg ( 2013 ) 527 { 541

15. Jimenez-Ruiz , E. , Grau , B.C. , Zhou , Y. , Horrocks , I. : Large-scale interactive ontology matching: Algorithms and implementation . In: ECAI 2012 - 20th European Conference on Arti cial Intelligence . Volume 242 . ( 2012 ) 444 { 449

16. Da Silva , J. , Baia~o, F.A. , Revoredo , K. , Euzenat , J.: Semantic interactive ontology matching: Synergistic combination of techniques to improve the set of candidate correspondences . In: OM 2017 - 12th ISWC workshop on ontology matching. Volume 2032 . ( 2017 ) 13 { 24

17. Gale , D. , Shapley , L.S.: College admissions and the stability of marriage . The American Mathematical Monthly 69 ( 1 ) ( 1962 ) 9 { 15

18. Irving , R.W. , Manlove , D.F. , O'Malley , G. : Stable marriage with ties and bounded length preference lists . Journal of Discrete Algorithms 7 ( 2 ) ( 2009 ) 213 { 219 Selected papers from the 2nd Algorithms and Complexity in Durham Workshop ACiD 2006 .

19. Manning , C.D. , Surdeanu , M. , Bauer , J. , Finkel , J. , Bethard , S.J. , McClosky , D. : The Stanford CoreNLP natural language processing toolkit . In: Association for Computational Linguistics (ACL) System Demonstrations . ( 2014 ) 55 { 60

20. Surhone , L.M. , Timpledon , M.T. , Marseken , S.F. : SimMetrics. VDM Publishing ( 2010 )

21. Lastra-Daz , J.J. , Garca-Serrano , A. , Batet , M. , Fernndez , M. , Chirigati , F.: Hesml. Inf. Syst. 66(C) ( June 2017 ) 97 { 118

22. Fellbaum , C., ed.: WordNet: An electronic lexical database . MIT Press ( 1998 )

23. David , J. , Euzenat , J. , Schar e, F., Trojahn dos Santos, C. : The alignment api 4.0 . Semant. web 2 ( 1 ) ( January 2011 ) 3 { 10

24. Petrakis , E.G.M. , Varelas , G. , Hliaoutakis , A. , Raftopoulou , P. : Design and Evaluation of Semantic Similarity Measures for Concepts Stemming from the Same or Di erent Ontologies object instrumentality . Proceedings of the 4th Workshop on Multimedia Semantics (WMS) 4 ( 2006 ) 233 { 237

25. Cheatham , M. , Hitzler , P. : String similarity metrics for ontology alignment . In: Proceedings of the 12th International Semantic Web Conference - Part II. ISWC '13 , New York, NY, USA, Springer-Verlag New York, Inc. ( 2013 ) 294 { 309

26. Faria , D. : Using the SEALS Client's Oracle in Interactive Matching ( 2016 )

27. Faria , D. , Balasubramani , B.S. , Shivaprabhu , V.R. , Mott , I. , Pesquita , C. , Couto , F.M. , Cruz , I.F. : Results of AML in OAEI 2017 . In: CEUR Workshop Proceedings . Volume 2032 . ( 2017 ) 122 { 128

28. Jimenez-Ruiz , E. , Grau , B.C. , Cross , V.: LogMap family participation in the OAEI 2017 . In: CEUR Workshop Proceedings . Volume 2032 . ( 2017 ) 153 { 157

29. Djeddi , W.E. , Khadir , M.T.: A novel approach using context-based measure for matching large scale ontologies . In Bellatreche, L., Mohania , M.K., eds. : Data Warehousing and Knowledge Discovery , Cham, Springer International Publishing ( 2014 ) 320 { 331

30. Djeddi , W.E. , Khadir , M.T. , Yahia , S.B.: XMap : Results for OAEI 2017 . In: CEUR Workshop Proceedings . Volume 2032 . ( 2017 ) 196 { 200

31. Achichi , M. , Cheatham , M. , Dragisic , Z. , Euzenat , J. , Faria , D. , Ferrara , A. , Flouris , G. , Fundulaki , I. , Harrow , I. , Ivanova , V. , Jimenez-Ruiz , E. , Koltho , K. , Kuss , E. , Lambrix , P. , Leopold , H. , Li , H. , Meilicke , C. , Mohammadi , M. , Montanelli , S. , Pesquita , C. , Saveta , T. , Shvaiko , P. , Splendiani , A. , Stuckenschmidt , H. , Thieblin , E. , Todorov , K. , Trojahn , C. , Zamazal , O. : Results of the Ontology Alignment Evaluation Initiative 2017 . In: Proceedings of the 12th International Workshop on Ontology Matching co-located with the 16th International Semantic Web Conference (ISWC 2017 ) Vienna, Austria, October 21st , 2017 . ( 2017 )