Ontology Matching is the task of nding a set of entity correspondences between a pair of ontologies, i.e. an alignment. It has been receiving a lot of attention due to its broad applications. Many techniques have been proposed, among which the ones applying interactive strategies. An interactive ontology matching strategy uses expert knowledge towards improving the quality of the nal alignment. When these strategies are based on the expert feedback to validate correspondences, it is important to establish criteria for selecting the set of correspondences to be shown to the expert. A bad de nition of this set can prevent the algorithm from nding the right alignment or it can delay convergence. In this work we present techniques which, when used simultaneously, improve the set of candidate correspondences. These techniques are incorporated in an interactive ontology matching approach, called ALINSyn. Experiments successfully show the potential of our proposal.
Ontology matching seeks to discover correspondences between entities of di
erent ontologies [
An expert can be involved by giving his feedback to a correspondence, indicating whether or not it belongs to the alignment. Therefore, de ning the set of correspondences to show to the expert is one of the problems of these interactive techniques. If this set is not well de ned, the nal alignment may be imprecise or incomplete, or convergence to a good alignment can be delayed. Therefore, the scienti c problem addressed in this paper is how to improve the set of correspondences to receive expert feedback.
This paper proposes ALINSyn, an approach that uses two techniques { a
semantic and a structural { for the improvement of a given set of candidate
correspondences. The semantic technique works by temporarily removing
correspondences from the set of candidate correspondences. The structural technique
interactively places part of the correspondences taken by the semantic technique
back in the set of candidate correspondences. ALINSyn uses techniques used in
the ALIN [
To evaluate ALINSyn, we de ned ALINBasic, a basic ontology matching algorithm that generates and use a set of candidate correspondences to do the matching. Each of the two ALINSyn techniques was added to ALINBasic in order to modify the set of candidate correspondences generated by it, and the obtained alignments were compared. ALINSyn was also compared to state-of-the-art interactive ontology matching systems, showing the potential of our proposal.
This paper is structured as follows: Section 2 describes interactive ontology matching, Section 3 describes the ALINBasic algorithm, section 4 describes ALINSyn approach, by explaining its two steps, in section 5 the evaluation of the approach is made and the section 6 is the conclusion. 2
An ontology O is represented as a labeled graph G = (V, E, vlabel, elabel).
The set of vertices V contains ontology entities such as concepts and properties.
Edges in E (E V V ) represent structural relationships between entities.
The edge labeling function elabel, which maps an edge (v, v) 2 E to a subset of
the set SL of structural labels, which in turn specify the nature of the structural
relationships between entities (e.g., subclassOf). Let LL denote the set of lexical
labels associated with entities (e.g., name, documentation). Finally, the vertex
labeling function, vlabel : V LL ! String, maps a pair (e, l) 2 V LL to
a string corresponding to the value of the lexical label l (e.g., name) associated
with the entity e [
Given two ontologies O and O', an ontology matching is the process that aims to nding a set of correspondences (e, e'), where e and e' are entities in O and O', respectively. Interactive ontology matching takes advantage of user feedback to perform ontology matching.
Within the set of all possible correspondences between the entities of two ontologies, in the context of the interactive ontology matching, we distinguish two types of correspondences: { Candidate correspondences are those possible correspondences that have been selected to be presented to the expert but have not yet received decision, { Classi ed correspondences are those possible correspondences that have been selected to be presented to the expert and have received decision.
There are similarity measures, denoted sim, which map the possible
correspondence (e, e') 2 O O' to a real number in [
According to Meilicke and Stuckenschmidt [
To reduce the need to classify all possible correspondences (all pairs of entities) between two ontologies as belonging or not to alignment, the algorithm selects a subset called set of candidate correspondences; { In the second phase, each correspondence in the set of candidate correspondences is classi ed by the ontology matching algorithm. In an interactive strategy, at least part of these correspondences is classi ed by the expert, and the other part can be classi ed by some automatic technique. 3
When the ontology matching is done interactively, we have two quality measures that are con icting: the number of interactions with the expert and the quality of the generated alignment. It is interesting that a technique to be used in an algorithm of ontology matching can improve one of these qualities without worsening the other in an accentuated way. That is, to decrease the number of interactions without decreasing proportionally the quality of the generated alignment, or to increase the quality of the generated alignment without increasing proportionally the number of interactions with the expert.
In this paper two techniques will be presented, which used alone, cannot increase one of the qualities without considerably worsening the other. The rst one, the semantic technique, decreases the number of interactions with the expert, but greatly decrease the quality of the generated alignment. The other, structural technique, enhances the quality of the generated alignment, but increasing a lot the number of interactions with the expert. But when used together, they can mitigate the disadvantages of each other, reducing the number of interactions without dramatically decreasing the quality of the generated alignment.
To evaluate the results of the two proposed techniques, three algorithms will be compared. An algorithm without the inclusion of any of the two techniques, called ALINBasic, a second algorithm, with the inclusion of the semantic technique, called ALINSem, and a third one with the inclusion of both the semantic and structural techniques, called ALINSyn. The two techniques are included in the algorithms as steps of these algorithms, so ALINSem is equivalent to the ALINBasic algorithm plus a semantic step that implements the semantic technique, and the ALINSyn algorithm is equivalent to the ALINSem algorithm plus a structural step that implements the structural technique.
The ALINBasic algorithm has two phases, as described by Meilicke and
Stuckenschmidt [
In the phase of generating the candidate correspondences, only class correspondences, not property correspondences, are chosen, therefore, the ALINBasic algorithm nds only class correspondences.
The rst phase of ALINBasic (Algorithm 1) will use the stable marriage
algorithm with size list limited to 1 [
The stable marriage algorithm will be executed six times, each time with a
di erent similarity metric (Jaccard, Jaro-Winkler, n-Gram, Wu-Palmer,
JiangConrath and Lin) and the result of the six executions will form a set of
correspondences by the union of the six formed sets (Steps 1 to 4 of Algorithm 1). The
process of selecting the similarity metrics was based on two criteria: available
implementations and the result of these metrics in assessments, such as those
carried out in [
From the set of correspondences formed by the union of the six sets all correspondence whose classes have exactly the same name will be classi ed as true (Step 5 of Algorithm 1). The correspondences selected by the running of stable marriage algorithm and not automatically classi ed will be the candidate correspondences (Step 6 of Algorithm 1).
Input: Two ontologies to be aligned Output: Candidate correspondences 1: for Each one of the similarity metrics: Jaccard, Jaro-Winkler, n-Gram, Wu
Palmer, Jiang-Conrath and Lin do 2: Run stable Marriage Algorithm forming the set Asim (being sim the corresponding similarity metric) 3: end for 4: Let A = AJaccard [ AJaro-Winkler [ An-Gram [ AWu-Palmer [ AJiang-Conrath [
ALin 5: Let B = Correspondences, from A, automatically classi ed as true by the fact that their entities have the same name 6: Set of candidate correspondences = A - B
Then begins the classi cation phase of the candidate correspondences of the ALINBasic. At this phase all the candidate correspondences will be presented to the expert to receive his feedback.
For this, the concept of interaction with the expert will be used. An
interaction with the expert corresponds to a question asked about at most three
correspondences, as long as they pair-wisely have at least one of the entities
in common. This is compliant with the OAEI de nition [
The ALINBasic algorithm can be seen in Algorithm 2.
Input: Two ontologies to be aligned Output: Alignment between the two ontologies 1: Run candidate correspondence generation (Algorithm 1) 2: for Each candidate correspondence do 3: Receive feedback (the candidate correspondence is transformed to classi ed correspondence) 4: end for 4
The objective of the ALINSyn algorithm is to decrease the number of interactions with the expert without decreasing in the same proportion the quality of the generated alignment. To achieve this objective, two steps, one semantic step and one structural step, are added to the ALINBasic algorithm to improve the set of candidate correspondences.
We rst introduce another type of correspondence: { Temporarily suspended correspondences are correspondences that are no longer candidate correspondences because of the semantic step. These correspondences can once again be candidate correspondences after the structural step.
The semantic step transforms some candidate correspondences to temporarily suspended correspondences. The structural step can transform some temporarily suspended correspondences to candidate correspondences again.
At the end of the non-interactive phase, by the use of the semantic step, all candidate correspondences that are not semantically equivalent will be transformed to temporarily suspended correspondences. In the interactive phase, by the use of the structural step, after each interaction with the expert, the expert's feedback can transform temporarily suspended correspondences in candidate correspondences if they have a particular structural relationship with a candidate correspondence that received positive feedback. 4.2 The action of this step is to transform all candidate correspondences with semantically di erent entity names to temporarily suspended correspondences. The step will be added to the ALINBasic algorithm at the end of the generation phase.
The semantic step uses Wordnet. Wordnet consists of synonym sets called
synsets [
1. If the name contains a preposition (e.g. HeadOfDepartment) then the head noun is the token before the preposition.
2. Otherwise the head noun is the last token in the name.
Input: Candidate correspondences Output: Temporarily suspended correspondences (ex-candidate correspondences) 1: for Each candidate correspondence do 2: Choose the head noun of each entity of the name of the correspondence 3: Put the head noun of each name in the canonical form 4: if The two head nouns are not in the same wordnet synset then 5: Transform the candidate correspondence to temporarily suspended correspondence 6: end if 7: end for Example of the semantic step The semantic step can be seen in the Algorithm 3. To illustrate the semantic step we assume that we have the candidate correspondences selected by Algorithm 1 shown in Table 1. The rst correspondence to be analyzed will be (Author, Regular Author) (step 1 of Algorithm 3). The head noun of Author is Author, since it has only one word. The head noun for Regular Author is Author, because it does not have a preposition and the last word is Author (step 2). The two head nouns are already in canonical form (step 3) and as they are the same word they are in the same synset, so they are not transformed to temporarily suspended correspondences.
The second correspondence in the table is the correspondence (Chairman,Chair) (step 1). Chairman is considered a word because a term is only divided into words if it has hyphen, white space or is in camelcase (step 2). Since the two are in the canonical form (step 3) of the word their synsets are compared in Wordnet, and they are di erent. It is important to note that the most common meanings of words are searched for in wordnet, so Chair is the object of sitting and not Boss. Therefore this correspondence will be transformed to temporarily suspended correspondences (step 5).
The result after following these steps for all correspondences is shown in Table 1, in the column 'after the semantic step'.
Input: Two ontologies to be aligned Output: Alignment between the two ontologies 1: Run candidate correspondence generation (Algorithm 1) 2: Run semantic step (Algorithm 3) 3: for Each candidate correspondence do 4: Receive feedback (the candidate correspondence is transformed to classi ed correspondence) 5: Run structural Step (Algorithm 5 ) 6: end for
With the inclusion of the semantic step, the algorithm will be called ALINSem. As an illustration, this algorithm is the same as the algorithm ALINSyn (Algorithm 4) without the inclusion of step 5 (Run structural step). The results of ALINSem will be compared to the results of ALINSyn with the objective of verifying if the combined use of the semantic step and the structural step improves the result achieved by the use of the semantic step alone.
Input: Temporarily suspended Correspondences, Classi ed correspondences Output: Candidate Correspondences (ex-temporarily suspended correspondences) 1: for Each temporarily suspended correspondence do 2: if The two classes of the temporarily suspended correspondence are subclasses of classes of a correspondence classi ed as true then 3: Transform the temporarily suspended correspondence to candidate correspondence 4: end if 5: end for 4.3
When only the semantic step is applied, experiments showed that the number of interactions with the expert were reduced, i.e. convergence was reached faster, however the nal alignment lost in quality. This is because some true correspondences have been taken from the set of candidate correspondences because of semantic step. The main goal of the structural step is to recover part of the quality lost through the use of the semantic step by transforming some temporarily suspended correspondences again to candidate correspondences.
At each iteration, all temporarily suspended correspondences that are formed by subclasses of the classes of the correspondences that received positive feedback from the expert are transformed again to candidate correspondences. Tests were performed again using the two techniques, which showed that the use of both techniques makes the number of interactions decrease considerably, but with a much lower quality loss, in relation to the results obtained with the ALINBasic algorithm. The structural step can be seen in Algorithm 5.
To illustrate the technique let us assume the situation described in Figure 1, where Co author is a subclass of Person in the cmt ontology and Regular author is a subclass of Person in the Conference ontology. Let us assume that the correspondence A (Person, Person) is a candidate correspondence and correspondence B (Co author, Regular author) is a temporarily suspended correspondence. If the correspondence A receive positive feedback, the correspondence B by having its classes that are subclasses of the classes of A is transformed to candidate correspondence. The result of the structural step can be seen in Table 1 in the column 'after the rst run of the structural step'. With the inclusion of the structural step in the interactive phase, the algorithm is called ALINSyn and can be seen in the Algorithm 4. 5
The goal of the ALINSyn approach is to reduce the number of interactions with the expert without greatly diminishing the quality of the generated alignment. Thus a rst research question is:
RQ1: Does the semantic step allow the ontology matching strategy to decrease the number of interactions with the expert? This question is answered with the use of the semantic step in the ALINBasic algorithm, as we see in the section "Analysis of the Results", which shows that the number of interactions with the expert has been reduced, but with a great drop in quality. That is why it is important to address other research questions.
RQ2: Can the expert feedback reduce the quality loss by the use of the semantic step?
RQ3: Does the use of both, semantic step and structural step together, generate an alignment with quality and number of interactions compatible with the state of the art proposals? 5.1
Results obtained in the interactive matching of OAEI 2016 using the conference dataset were used to compare with the state of the art.
The OAEI interactive track is performed with percentages of expert correctness, from 70% to 100%. This paper has taken into consideration, for the evaluation of the execution of the ALINSyn and of other tools, 100% of correctness by the expert. 5.2
After using the semantic step the results presented in Table 2 (ALINSem row) were reached, which shows that the use of the semantic step decreases the number of expert interactions, which responds to 'RQ1: Does the semantic step allow the ontology matching strategy to decrease the number of iterations with the expert ?', but there has been a sharp drop in quality, which shows the need to answer the question 'RQ2: Can the expert feedback reduce the quality loss by using the semantic step?'.
The recovery in the quality of the generated alignment was attempted by the use of structural step. After the inclusion of this new step the results shown in Table 2 (ALINSyn row) were reached. That shows that the goal of the ALINSyn was achieved using the two techniques. The number of interactions with the expert decreased greatly, from 619 to 219, with the quality decreasing proportionally much less, the f-measure was from 0.79 to 0.75, what responds to RQ2: Can the expert feedback reduce the quality loss by the use of the semantic step ?. The result achieved is due to the combined e ect of the joint use of the two techniques.
If we use only the semantic step we have a good decrease in the number of interactions with the expert, but with a sharp drop in quality. The subsequent use of the structural step, interactively, causes some of the lost quality to be recovered.
If we use only the structural step, without using the semantic step before, with all possible correspondences, not only the temporarily suspended correspondences, we would have an increase in quality, but a large number of correspondences would be added to the set of candidate correspondences, which would make the number of interactions with the expert too large (Table 2, ALINStr row). The transformation of candidate correspondences into temporarily suspended correspondences, through the semantic step, and the search, by the structural step, only among the temporarily suspended correspondence reduces the search space, which means that the number of interactions with the expert do not go up explosively.
The combined use of the two techniques results in a more balanced result, with a reduction in the number of interactions without a big loss of quality ( Table 2, ALINSyn row ).
OAEI provides a comparison among tool performance in the ontology matching
process each year, and one of the ontology groups used is the conference dataset
used in this paper [
Table 3 shows a comparison of some tools that participated in the OAEI 2016 interactive conference track. NI means number of interactions. In each interaction there can be up to three questions. "%" is the ratio of the number of interactions to the number of possible correspondences among all the alignments of the conference dataset. Progress in information and communication technologies has made a large number of data repositories available, but with a great deal of semantic heterogeneity, which makes it di cult to integrate. A process that has been used to solve this problem is the ontology matching, which tries to discover the existing correspondences between the entities of two distinct ontologies, which in turn structures the concepts that de ne the data stored in each repository.
This work presented an interactive approach for ontology matching, based on manipulation of the set of candidate correspondences with techniques to decrease the number of interactions with the expert, without greatly reducing the quality of the alignment.
Two techniques were combined, one semantic and the other structural. The goal of the semantic technique was to decrease the number of interactions with the expert. The structural technique came in support of the semantic technique, and its objective was to decrease the quality loss resulting from the decrease in the number of interactions with the expert.
In order to evaluate if the techniques generated a decrease in the number of interactions without signi cantly lowering the quality, the executions of a basic algorithm with and without the techniques were compared, which showed that the techniques, when combined, reach their goal.
In addition, the quality of the alignment provided by the ALINSyn approach was compared to state of the art tools that have participated in the track of interactive ontology matching in OAEI 2016. The results obtained show that ALINSyn 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, keeping the number of interactions within the range achieved by the other tools.
The third author was partially funding by project PQ-UNIRIO N01/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)'.