2 Interactive ontology matching

The ontology matching process starts with two ontologies, O and Oʹ, and returns an alignment $A_{\textrm{final}}$ between the input ontologies. An alignment is a set of mappings between entities e and eʹ from O and Oʹ, respectively, defining pairs of entities. The ontology matching process can receive as input an initial alignment $A_{\textrm{init}}$. Besides, it can get input parameters and can access external resources, such as a dictionary (Figure 1).

Figure 1 Ontology matching process – based on Euzenat & Shvaiko (Reference Euzenat and Shvaiko2013)

A mapping asserts a semantic relationship between its entities, such as disjunction, subsumption or equivalence. In this paper, we only consider the equivalence relationship. The ontology matching system is responsible to find, among all the possible mappings, the ones to be included in the alignment.

Given that two ontologies representing the same domain may present different types of heterogeneity (terminological, structural or semantic, among others), we need a combination of distinct techniques to correctly discover mappings between their entities. We can see an ontology matching tool as a collection of several matching components, each implementing a specific technique dealing with a specific heterogeneity type (Ngo et al., Reference Ngo, Bellahsene, Todorov, Cimiano, Corcho, Presutti, Hollink and Rudolph2013).

Interactive ontology matching processes involve domain experts. The type of expert involvement used in this paper is through feedback on selected mappings. This type takes benefit from the domain expert knowledge by submitting selected mappings to the expert who assesses which of them should be accepted or rejected (Figure 2).

Figure 2 Interactive ontology matching process – based on Paulheim et al. (Reference Paulheim, Hertling and Ritze2013)

One common type of approach for this type of expert involvement is to divide the process into two main steps: the selection of mappings and the propagation of expert feedback. The current tools that follow this type of approach only select mappings in the selection step. They do not select any new mappings in the propagation step, thus not taking advantage of the expert feedback to select mappings.

This paper presents an approach where various techniques are used to use the expert feedback to improve the set of selected mappings, including a new technique for interactively select relationship mappings and also including the interactive use of mapping anti-patterns.

This paper shows that the new technique causes an increase in F-measure, and, if the approach uses expert feedback as the input of the technique, then the approach requires fewer interactions with the expert to do so. It also shows that the interactive use of mapping anti-patterns decreases the number of interactions with the expert.

3 Related work

There are at least three areas in which users may be involved in a matching solution (Euzenat and Shvaiko, Reference Euzenat and Shvaiko2013):

• by providing initial alignments to the system (before matching),

• by configuring (which includes strategy and parameter selection) and tuning the system and

• by providing feedback to matchers (during or after the automatic matching process) in order for them to adapt their results.

The type of user, a domain expert, involvement used in this paper is through feedback to matchers. They benefit from the domain expert knowledge by submitting selected mappings to the expert who assesses which of the mappings should be accepted or rejected. One common type of approach for this type of expert involvement is to divide the process into two main steps: the selection of mappings and the propagation of expert feedback.

In the propagation step, different approaches can use expert feedback in different ways. Some of these approaches automatically classify selected mappings using a threshold. The threshold is a value that indicates whether a mapping should be automatically accepted (or rejected) when its similarity values are greater (or smaller) than the threshold. Expert feedback is used to calculate this threshold (Shi et al., Reference Shi, Li, Tang, Xie, Li, Bernstein, Karger, Heath, Feigenbaum, Maynard, Motta and Thirunarayan2009; Duan et al., Reference Duan, Fokoue, Srinivas, Patel-Schneider, Pan, Hitzler, Mika, Zhang, Pan, Horrocks and Glimm2010; Hertling, Reference Hertling2012; Paulheim & Hertling, Reference Paulheim and Hertling2013; Chunhua et al., Reference Chunhua, Zhiming, Pengpeng, Jian, Jie and Tianxu2015). Some approaches automatically classify some selected mappings using a classifier. These approaches use expert feedback to create the training data set for learning the classifiers (To H. & Le, Reference To and Le2009; Lopes et al., Reference Lopes, Baião and Revoredo2015). Others approaches use expert feedback to modify the weight of similarity metrics (Shi et al., Reference Shi, Li, Tang, Xie, Li, Bernstein, Karger, Heath, Feigenbaum, Maynard, Motta and Thirunarayan2009; Duan et al., Reference Duan, Fokoue, Srinivas, Patel-Schneider, Pan, Hitzler, Mika, Zhang, Pan, Horrocks and Glimm2010; Balasubramani et al., Reference Balasubramani, Taheri and Cruz2015) or to change the value of similarity metrics (Cruz et al., Reference Cruz, Stroe and Palmonari2012, Reference Cruz, Loprete, Palmonari, Stroe, Taheri, Janowicz, Schlobach, Lambrix and Hyvönen2014).

Alin and its previous versions use the expert feedback to improve the set of selected mappings. Others approaches also use expert feedback to improve the set of selected mappings (Jiménez-Ruiz et al., Reference Jiménez-Ruiz, Cuenca Grau, Zhou and Horrocks2012; Faria et al., Reference Faria, Pesquita, Santos, Palmonari, Cruz, Couto, Meersman, Panetto, Dillon, Eder, Bellahsene, Ritter, De Leenheer and Dou2013; Lambrix & Kaliyaperumal, Reference Lambrix and Kaliyaperumal2016).

$ALIN_{Syn}$ (Da Silva et al., Reference Da Silva, Revoredo, Baião and Euzenat2017), an earlier version of Alin, in the mapping selection phase, selects concept mappings through semantic and lexical similarity metrics. Afterward, it automatically accepts the selected concept mappings with the same names. Then, it suspends some of these mappings using a semantic technique. In the propagation phase, $ALIN_{Syn}$ uses expert feedback to unsuspend some of these suspended mappings, returning them to the set of selected mappings, thus improving it. Alin uses all the techniques used in $ALIN_{Syn}$.

$ALIN_{Attr}$ (Da Silva et al., Reference Da Silva, Revoredo and Baião2018), another earlier version of Alin, has the same mapping selection phase as $ALIN_{Syn}$, but without suspending selected concept mappings. In the programming phase, $ALIN_{Attr}$ uses expert feedback to select attribute mappings. Alin uses the attribute mapping selection technique used in $ALIN_{Attr}$.

System for Aligning and Marging Biomedical Ontologies (SAMBO) (Lambrix & Kaliyaperumal, Reference Lambrix and Kaliyaperumal2016) takes advantage of the expert feedback to improve the set of selected mappings, removing the selected mappings that conflict with the accepted mappings, according to a reasoner.

Logmap (Jiménez-Ruiz & Grau, Reference Jiménez-Ruiz, Cuenca Grau, Aroyo, Welty, Alani, Taylor, Bernstein, Kagal, Noy and Blomqvist2011; Jiménez-Ruiz et al., Reference Jiménez-Ruiz, Cuenca Grau, Zhou and Horrocks2012), in the selection step, selects mappings based on similarity metrics seeking to achieve a high recall. Still, in this step, the approach also uses automatic, non-interactive, techniques for improving the precision of the set of selected mappings. In the propagation step, the approach takes advantage of the expert feedback by identifying mappings that are inconsistent with the accepted mappings, according to a reasoner, and removes them from the set of selected mappings.

AML (Faria et al., Reference Faria, Pesquita, Santos, Palmonari, Cruz, Couto, Meersman, Panetto, Dillon, Eder, Bellahsene, Ritter, De Leenheer and Dou2013) initially selects mappings based on lexical, semantic and structural similarities. AML places, in automatic mode, mappings that are above a given threshold in the alignment, which then goes through a repair process.

In the interactive mode, AML uses two thresholds. Those selected mappings that are below the lower threshold are automatically rejected. Selected mappings above the higher threshold are automatically accepted unless they generate an inconsistency. In such a case, they are submitted to the expert. Concerning the selected mappings between the two thresholds, those which generate inconsistency are automatically rejected; the others are submitted to the expert.

AML uses the expert feedback to remove mappings from the set of selected mappings. If a selected mapping is accepted, all selected mappings that have an entity in common with it are rejected, as well as all those that are inconsistent with it.

In the current approaches, the impact of expert feedback on the set of selected mappings is the removal of mappings from it, to increase the precision and decrease the number of interactions. Alin and its previous versions also focus on using the expert feedback to select mappings to improve the set of selected mappings.

Alin uses, besides the techniques of the earlier versions, another that selects relationships mappings associated with accepted concept mappings, and mapping anti-patterns.

In the approach of Chunhua et al. (Reference Chunhua, Zhiming, Pengpeng, Jian, Jie and Tianxu2015), there are formulas that associate relationships mappings to the concept mappings of the concepts associated with these relationships. The formulas serve to increase the weight of these concept mappings, which increases the likelihood of the approach automatically include them into the final alignment. Alin selects relationships mappings, to receive the expert feedback, associated with accepted concept mappings.

Alin uses mapping anti-patterns to remove mappings from the set of selected mappings. Automated Semantic Mapping of Ontologies with Validation (ASMOV) (Jean-Mary et al., Reference Jean-Mary, Shironoshita and Kabuka2009) uses concepts similar to mapping anti-patterns, which it calls semantic verification inferences. ASMOV chooses from the mappings found in one of these semantic verification inferences to take out of the alignment. ASMOV is an automatic matching tool, so unlike Alin, it does not use expert feedback to identify which mappings to exclude from alignment.

Section 4 further explains the Alin approach.

Several areas use user knowledge to improve their performance. In information search and retrieval area, for example, feedback data based on direct interaction (e.g., clicks, scrolling) as well as on user profiles/preferences have been proven valuable for personalizing the search process, for example, from how queries are understood to how relevance is assessed (Buscher et al., Reference Buscher, Gwizdka, Teevan, Belkin, Bierig, van Elst and Jose2009). However, in such cases, the feedback is provided by users and is used for answering the query of the same user (in a single session for relevance feedback, or across session for personalization). Ontology matching could take advantage of user feedback to improve alignments. However, interactive ontology matching is usually disconnected from the use of the resulting alignments, which may be used in different contexts. It relies on expert feedback, as opposed to user feedback, in order to find the correct alignment, not one that suits the need of a particular user. In addition, relevance feedback in information retrieval is rather used to give more or less weight to characteristics of the instances. Here, it is used to revise the mappings based on more logical constraint propagation, for example, anti-patterns.

4 The Alin approach

In this section, we describe our approach for interactively matching two ontologies. The next subsection presents the overall Alin procedure. Section 4.2 presents the terminology used to explain our approach. Section 4.3 describes the Alin algorithms.

4.2 Terminology

In an ontology O, its entities e can be concepts (c), which are concepts in a domain, organized in a subconcept–superconcept hierarchy, or properties, which describe attributes (a) of concepts and relationships (r) between concepts. Table 1 provides predicates that can be used to model an ontology.

Given two ontologies O and Oʹ, an ontology matching approach will search for mappings between the entities of these two ontologies. In this paper, all entities from O have no prime (ʹ); all entities from Oʹ have a prime (ʹ). We use the notation $\langle e, e'\rangle$ to represent a mapping between two entities, $\langle c, c'\rangle$ between two concepts, and $\langle r, r'\rangle$ and $\langle a, a'\rangle$ between two relationships and two attributes.

Table 1 Predicates for ontology description (based on Chunhua et al. (Reference Chunhua, Zhiming, Pengpeng, Jian, Jie and Tianxu2015)).

4.3 Algorithms

The Alin algorithms (Algorithms 1 to 14) use the variables described below:

• Selected – Set of selected mappings;

• Suspended – Set of suspended mappings;

• Accepted – Set of accepted mappings;

• SetofSimMet – Set of similarity metrics;

• SetofSemSim – Set of semantic similarity metrics, it is a subset of the set of similarity metrics;

• SimMet – one similarity metric.

Alin uses the functions defined in Table 2 in its algorithms.

Table 2 Functions used in the Alin algorithms.

Alin (Algorithm 1) has two main steps: the selection step and the propagation step. The selection step is responsible for defining the initial selected, accepted and suspended mappings. The propagation step is where the expert provides feedback to the selected mappings and this feedback is propagated.

The following subsections detail these two steps.

4.3.1 Selection step

The Alin selection step (from line 1 to line 3 of Algorithm 1) describes the activities for defining the initial set of selected mappings, the initial set of suspended mappings and the initial alignment (accepted mappings). The algorithm has as input the two ontologies to be matched and, as parameters, a set of similarity metrics chosen by the user. The chosen similarity metrics can be semantic or lexical.

The algorithm starts selecting concept mappings (line 1 of Algorithm 1) using the SelectConcept Mappings algorithm (Algorithm 2). Inside this algorithm, the SelectMappingsPerMetric algorithm (Algorithm 3) selects mappings for each similarity metric. The SelectMappingsPerMetric algorithm treats the matching problem as a stable marriage problem with size list limited to 1 (Gale & Shapley, Reference Gale and Shapley1962; Irving et al., Reference Irving, Manlove and O’Malley2009), that is, 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.

The SelectMappingsPerMetric algorithm is executed once for each chosen metric, where it generates a set of mappings for each metric (lines 4 and 5 of Algorithm 2). The union of these sets defines the initial set of selected mappings (from line 6 to line 10 of Algorithm 2).

Algorithm 1 ALIN TopLevel

Algorithm 2 SelectConceptMappings

Algorithm 3 SelectMappingsPerMetric

Algorithm 4 AcceptConceptMappings

Algorithm 5 SuspendConceptMappings

After defining an initial set of selected mappings, Alin evaluates each of them to verify if some of them can already be automatically accepted (line 2 of Algorithm 1) using the AcceptConceptMappings algorithm (Algorithm 4). At first, Alin automatically accepts concept mappings whose entity names are the same and moves them from the set of selected mappings to the accepted ones (from line 1 to line 6 of Algorithm 4). After that, Alin identifies all automatically accepted concept mappings that are in an anti-pattern with other automatically accepted concept mappings (line 7 of Algorithm 4) using the UndoConceptAntiPatterns algorithm (Algorithm 10) and moves them from the accepted mappings to the set of selected mappings. This use of anti-patterns is done to minimize the precision decrease that can occur because of the automatic acceptation of mappings. Subsection 4.3.3 explains anti-patterns.

In the selection step, selected mappings less likely to be correct are suspended (line 3 of Algorithm 1), using the SuspendConceptMappings algorithm (Algorithm 5). The SuspendConceptMappings algorithm identifies all selected mappings in which the two concepts have all semantic similarity metric values under a threshold (here 0.9, see Section 5.2) and suspends them. The similarity metrics used in this technique are chosen by the user, for example, Resnick, Jiang-Conrath or Lin. The suspended mappings can become selected again after interaction with the expert, during the propagation step (Subsection 4.3.2), by the use of the UnsuspendConceptMappings algorithm (Algorithm 7).

Subsection 4.3.2 describes the propagation of the accepted mappings.

4.3.2 Propagation step

The Alin propagation step (from line 4 to line 15 of Algorithm 1) describes the activities to choose the selected mapping to receive expert feedback, the feedback itself and the feedback propagation.

At the beginning, Alin propagates the automatically accepted mappings (line 5 of the Algorithm 1) in the same way as it does with the mappings accepted by the expert.

At each iteration in the propagation step (from line 7 to line 15 of the Algorithm 1), Alin chooses among all the selected mappings, the one that has the highest sum of their similarities (line 8 of Algorithm 1). After that, this mapping receives the expert feedback (line 9 of Algorithm 1), where the expert can accept or reject the selected mapping. If the expert accepts the mapping, Alin moves it to the set of accepted mappings (line 12 of Algorithm 1) and propagates its effects (line 13 of Algorithm 1) through the PropagateAcceptedMapping algorithm (Algorithm 6).

Algorithm 6 PropagateAcceptedMapping

In the propagation step, Alin only accepts mappings that have received positive feedback from the expert. So, if the expert does not make mistakes, the monotonic growth of the recall and the precision in the propagation step is guaranteed.

The techniques used to propagate the effects of the expert feedback are described in this subsection. The first three techniques described are structural ones that select new mappings. A structural technique takes, as input, one or more mappings, and it generates, as output, mappings structurally related to them.

The UnsuspendConceptMappings algorithm (Algorithm 7) implements the first structural technique. This algorithm assumes that concept mappings are more prone to be true if the superconcepts of both concepts in the mapping are in an accepted mapping. This algorithm, at each iteration, identifies all suspended mappings that are formed by subconcepts of the concepts of the accepted mappings and unsuspend them, that is, they become again selected mappings. We implemented this technique in a prior version of Alin: $ALIN_{Syn}$ (Da Silva et al., Reference Da Silva, Revoredo, Baião and Euzenat2017).

Algorithm 7 UnsuspendConceptMappings

So far, the Alin approach has only taken into account concept mappings. With the second structural technique, implemented by the SelectAttributeMappings algorithm (Algorithm 8), attribute mappings of the accepted mappings were selected, that is, once the expert accepts a concept mapping, Alin selects some mappings between the attributes of its concepts.

To develop the SelectAttributeMappings algorithm, we have assumed that attribute mappings are more prone to be a mapping between attributes of concepts if their concepts are in an accepted mapping. To reduce the search space to the SelectAttributeMappings algorithm, Alin (line 4 of the Algorithm 8) used the SelectMappingsPerMetric algorithm (Algorithm 3). We implemented this technique in a prior version of Alin: $ALIN_{Attr}$ (Da Silva et al., Reference Da Silva, Revoredo and Baião2018).

Algorithm 8 SelectAttributeMappings

To develop the third structural technique, implemented by the SelectRelationshipMappings algorithm (Algorithm 9), we have assumed that relationships are more prone to be in a mapping if they are relationships between the concepts of two accepted concept mappings. We have also assumed that relationships between subconcepts of these concepts are more prone to be in a mapping too. These situations in which the SelectRelationshipMappings algorithm selects relationship mappings are called triggers for the selection of relationship mappings (Definition 4.1).

Algorithm 9 SelectRelationshipMappings

Definition 4.1 (Triggers). Given $\langle c_1,c^{\,\prime}_1\rangle$ and $\langle c_2,c^{\,\prime}_2\rangle$, the following conditions:

• rconcept(r, $c_1$, $c_2$) $\wedge$ rconcept(rʹ, $c'_1$, $c'_2$)

• sub($c_3$, $c_1$, 2) $\wedge$ rconcept(r, $c_3$, $c_1$) $\wedge$ rconcept(rʹ, $c'_1$, $c'_2$)

• sub($c'_3$, $c'_1$, 2) $\wedge$ sub($c_3$, $c_1$, 2) $\wedge$ rconcept(rʹ, $c'_3$, $c'_1$) $\wedge$ rconcept(r, $c_3$, $c_1$)

are called triggers between $\langle c_1,c^{\,\prime}_1\rangle$ and $\langle c_2,c^{\,\prime}_2\rangle$ for the selection of the relationship mapping $\langle r,r'\rangle$.

4.3.3 Mapping Anti-patterns

An ontology may have construction constraints, such as a concept cannot be equivalent to its superconcept. An alignment may have other constraints, for example, an entity of ontology O cannot be equivalent to two entities of the ontology Oʹ. A mapping anti-pattern is a combination of mappings that generates a problematic alignment, that is, a logical inconsistency or a violated constraint.

Alin uses three mapping anti-patterns empirically identified by Guedes et al. (Reference Guedes, Baião and Revoredo2014b) (Definitions 4.2 to 4.4), extracted from the results of ontology matching tools evaluated by OAEI (Guedes et al. Reference Guedes, Baião and Revoredo2014a).

The multiple-entity anti-pattern (Definition 4.2) applies when a single entity does not participate in two mappings (Figure 3(a)). The cross-mapping anti-pattern (Definition 4.3) applies when no subconcept can be equivalent to its superconcept. This mapping anti-pattern applies when a concept $c_1$ is a subconcept of the concept $c_2$ and $c'_1$ is subconcept of the concept $c'_2$ and $c_1$ is in a mapping with $c'_2$ and $c_2$ is in a mapping with $c'_1$ (see Figure 3(b)). The disjunction and generalization anti-pattern (Definition 4.4) applies when a pair of concepts of an ontology that are subconcept and superconcept are in mappings with two disjoint concepts of the other ontology (Figure 3(c)).

Figure 3 The three mapping anti-pattern used in Alin: (a) multiple-entity anti-pattern; (b) cross-mapping anti-pattern; (c) disjunction and generalization anti-pattern. Based on Jean-Mary et al. (Reference Jean-Mary, Shironoshita and Kabuka2009)

Definition 4.2 (Multiple-entity anti-pattern). If the entities $e_1$, $e'_1$ and $e'_2$ of mappings $\langle e_1,e'_1\rangle$ and $\langle e_1,e'_2\rangle$ occur in the situation described by the formula $entity(e_1,O)\wedge entity(e'_1,O')\wedge entity(e'_2,O')$, then $\langle e_1,e'_1\rangle$ and $\langle e_1,e'_2\rangle$ are said to be in a multiple-entity anti-pattern.

Definition 4.3 (Cross-mapping anti-pattern). If the concepts $c_1$, $c_2$, $c'_1$ and $c'_2$ of mappings $\langle c_2,c'_1\rangle$ and $\langle c_1,c'_2\rangle$ occur in the situation described by the formula $concept(c_1,O)\wedge concept(c'_1,O')\wedge concept(c_2,O)\wedge concept(c'_2,O')\wedge sub(c_1,c_2) \wedge sub(c'_1,c'_2)$, then $\langle c_2,c'_1\rangle$ and $\langle c_1,c'_2\rangle$ are said to be in a cross-mapping anti-pattern.

Definition 4.4 (Disjunction and Generalization anti-pattern). If the concepts $c_1$, $c_2$, $c'_1$ and $c'_2$ of mappings $\langle c_1,c'_1\rangle$ and $\langle c_2,c'_2\rangle$ occur in the situation described by the formula $concept(c_1,O)\wedge concept(c'_1,O')\wedge concept(c_2,O)\wedge concept(c'_2,O')\wedge sub(c_1,c_2)\wedge dis(c'_1,c'_2)$, then $\langle c_1,c'_1\rangle$ and $\langle c_2,c'_2\rangle$ are said to be in a disjunction and generalization mapping anti-pattern.

Alin takes advantage of the fact that if a correct mapping is in a mapping anti-pattern with another mapping, the other mapping is wrong. It uses (line 7 of Algorithm 4) the UndoConceptAntiPatterns algorithm (Algorithm 10) to identify automatically accepted concept mappings that are in mapping anti-patterns with others automatically accepted concept mappings and moves these mappings from the set of accepted mappings to the set of selected mappings. Alin (line 5 of Algorithm 6) uses the AvoidConceptAntiPatterns algorithm (Algorithm 11) to identify those selected concept mappings that are in a mapping anti-patterns with an accepted concept mapping and removes them from the set of selected mappings. Alin (lines 8 and 11 of Algorithm 6) uses the AvoidAttributeMultipleEntityAntiPattern algorithm (Algorithm 12) and the AvoidRelationshipMultipleEntityAntiPattern algorithm (Algorithm 13) to identify selected attribute and relationship mappings that are in the multiple-entity anti-pattern with an accepted mapping and removes them from the set of selected mappings.

Algorithm 10 UndoConceptAntiPatterns

Algorithm 11 AvoidConceptAntiPatterns

Algorithm 12 AvoidAttributeMultipleEntityAntiPattern

Algorithm 13 AvoidRelationshipMultipleEntityAntiPattern

5 Evaluation overview

Alin is implemented in Java using the following Application Programming Interfaces (APIs): Stanford CoreNLP API (Manning et al., Reference Manning, Surdeanu, Bauer, Finkel, Bethard and McClosky2014) to put a word in canonical form; Simmetrics API (Surhone et al., Reference Surhone, Timpledon and Marseken2010), for string-based similarity metrics; HESML API (Lastra-Díaz et al., Reference Lastra-Díaz, García-Serrano, Batet, Fernández and Chirigati2017), for Wordnet (Fellbaum, Reference Fellbaum1998) based linguistic metrics; the OWL API for handling ontologies written in OWL and the Alignment API (David et al., Reference David, Euzenat and Scharffe2011) to deal with alignments.

In the executions described in this section, Alin receives as input parameters six similarity metrics. We based the process of choosing the similarity metrics used by Alin on the result of these metrics in assessments (Petrakis et al., Reference Petrakis, Varelas, Hliaoutakis and Raftopoulou2006; Cheatham & Hitzler, Reference Cheatham and Hitzler2013). We chose Jaccard, Jaro-Winkler and n-gram lexical metrics and the Resnick, Jiang-Conrath and Lin semantic metrics. Resnick, Jiang-Conrath and Lin are metrics that require a taxonomy to be computed, this taxonomy is provided by Wordnet (Fellbaum, Reference Fellbaum1998).

The OAEI is a coordinated international initiative, which organizes the evaluation of ontology matching systems. Its main goal is to compare systems and algorithms openly and on the same basis, to allow anyone to draw conclusions about the best matching strategies. OAEI provides ontologies for various domains (data sets). The ontologies of data sets can have three types of entities: concepts (classes), data properties (attributes) and object properties (relationships). OAEI provides reference alignments, which are alignments that contain the mappings that are believed to be correct, for each ontology pair in a data set.

To evaluate Alin, we followed the same protocol as the OAEI 2018 interactive matching track (Algergawy et al., Reference Algergawy, Cheatham, Faria, Ferrara, Fundulaki, Harrow, Hertling, Jiménez-Ruiz, Karam, Khiat, Lambrix, Li, Montanelli, Paulheim, Pesquita, Saveta, Schmidt, Shvaiko, Splendiani, Thiéblin, Trojahn, Vataščinová, Zamazal and Zhou2018) in which Alin participated (Da Silva et al., Reference Da Silva, Revoredo and Baião2018). An interactive matcher is run and the reference alignment is used to simulate the expert answering. At each interaction, up to three selected mappings can be submitted to the expert, as long as each selected mapping has one entity in common with another selected mapping in the interaction (Faria, Reference Faria2016). The quality of an alignment generated by a matching approach is generally measured by the F-measure, which is the harmonic mean between recall and precision. When the ontology matching process is interactive another quality metric occurs, it is the number of interactions with the expert. In Tables 4, 5, 6, 7, 8, 9, 10 and 11 hereafter, ‘Total Requests’ is the number of interactions with the expert.

The OAEI 2018 interactive matching track (Algergawy et al., Reference Algergawy, Cheatham, Faria, Ferrara, Fundulaki, Harrow, Hertling, Jiménez-Ruiz, Karam, Khiat, Lambrix, Li, Montanelli, Paulheim, Pesquita, Saveta, Schmidt, Shvaiko, Splendiani, Thiéblin, Trojahn, Vataščinová, Zamazal and Zhou2018) is based on two data sets: Conference and Anatomy.

The Conference data set consists of 7 ontologies, resulting in a total of 21 ontology pairs. There are 125,860 possible mappings when we take into account only the mappings of the same entity type among all 21 ontology pairs. Alin takes into account only the mappings of the same entity type. Among the 21 ontology pairs of the Conference data set, there are 305 mappings in the reference alignments.

The Anatomy data set contains two ontologies, one with the mouse anatomy and another with the human anatomy. The number of possible mappings between the two ontologies is 9,066,176. There are 1516 mappings in the reference alignment.

5.1 Evaluation criteria

We measure efficiency in the use of expert feedback as the ratio between the F-measure gain over the baseline ($ALIN_{NoRel}$) and the additional number of expert answers.

We raise the following research questions to evaluate if the techniques used in Alin help to achieve the objective to generate a better alignment:

1. RQ1: Does the SelectRelationshipMappings algorithm increase the F-measure of the generated alignment?

2. RQ2: Is the expert feedback more efficiently used when it assists the SelectRelationshipMappings algorithm?

3. RQ3: Does the interactive use of mapping anti-patterns decrease the number of interactions with the expert?

4. RQ4: Does the use of the techniques described in this paper generate a final alignment with quality and number of interactions compatible with the state-of-the-art proposals?

In order to evaluate the benefit of the proposed solutions, we developed several versions of Alin:

• Alin is the full version of Alin. It uses only the accepted mappings as input of the SelectRelationshipMappings algorithm, that is, it uses the expert feedback to assist the SelectRelationshipMappings algorithm.

• ALIN _NoAP is the full Alin without using anti-patterns. Comparing its results with the results of full Alin allows answering to RQ3.

• ALIN _Aut uses all the automatically selected concept mappings as input to the Select RelationshipMappings algorithm, that is, the line 3 of the PropagateAcceptedMapping algorithm (Algorithm 6) is removed and the AutomaticallySelectRelationshipMappings algorithm (Algorithm 14) is called between the lines 1 and 2 of Algorithm 1. Since it uses the automatically selected concept mappings as input, it does not use the expert feedback to the SelectRelationshipMappings algorithm. Comparing the results of its execution with the results of $ALIN_{NoRel}$ allows answering to RQ1. Comparing the results of its execution with the results of $ALIN_{NoRel}$ and the results of full Alin allows answering to RQ2.

• ALIN _NoRel does not use the SelectRelationshipMappings algorithm, that is, line 3 and lines from 10 to 12 are removed from the PropagateAcceptedMapping algorithm (Algorithm 6). Comparing the results of its execution with the results of $ALIN_{Aut}$ allows answering to RQ1. Comparing the results of its execution with the results of $ALIN_{Aut}$ and the results of full Alin allows answering to RQ2.

Algorithm 14 AutomaticallySelectRelationshipMappings

Table 3 shows the characteristics of Alin versions.

Table 3 Alin versions.

5.2 Parameter tuning

In the SelectRelationshipMappings algorithm, we searched for the relationship mappings of the subconcepts of the concepts of two accepted concept mappings. During the creation of this algorithm, we found out that if we fixed a maximum depth of the subconcepts that we searched, the number of relationship mappings that the algorithm would select decreased. As a consequence, the number of interactions with the expert also decreases. The depth of 2 was where we found the maximum recall, and we set this value for Alin. From this value, we found only relationships mappings that were not accepted by the expert (Table 4).

Table 4 Comparison between Alin executions with different maximum depths of the subconcepts using Conference data set.

We modified the SuspendConceptMapping algorithm in Alin. We removed, in $ALIN_{Syn}$ (Da Silva et al., Reference Da Silva, Revoredo, Baião and Euzenat2017), all mappings from the set of selected mappings in which the two mapping concepts were not semantically equivalent, that is, if all of the semantic similarity metrics were less than 1. In Alin, using the Conference data set, we did several executions changing the minimum value of similarity, and we found that the value of 0.9 reached the best result, so in Alin, we fixed the value in 0.9 (Table 5). Although we have found the value by running Alin with the Conference data set, we used the same value with the Anatomy data set.

Table 5 Comparison between Alin executions with different minimum semantic similarity values of the entities using the Conference data set.

Since the parameter values were empirically set, further study would be required to make them more general.

Table 6 Comparison between different ontology matching executions with Conference data set.

5.3 Analysis of the results

We made executions with the three versions of Alin for both the Conference data set and the Anatomy data set. The execution of $ALIN_{Aut}$, for the Conference data set, using the SelectRelationshipMappings algorithm generates an alignment with higher F-measure relatively to $ALIN_{NoRel}$. Thus, this execution responds positively to RQ1.

With all the selected mappings as input to the SelectRelationshipMappings algorithm in $ALIN_{Aut}$, there is an increase of 1.02% in F-measure, but with 29.26% more interactions with the expert relative to $ALIN_{NoRel}$. With the use of accepted mappings as input to the SelectRelationshipMappings algorithm in Full Alin, we got almost the same increase in F-measure, but with only 12.19% more interactions relative to $ALIN_{NoRel}$. So, concerning $ALIN_{NoRel}$, the Full Alin allows more efficiency in the use of the expert feedback than $ALIN_{Aut}$. Thus, this execution responds positively to RQ2.

With the use of the Anatomy data set, all versions achieved the same alignment, and thus the same F-measure (Table 7). This is because there are no relationships in the ontologies of the Anatomy data set, hence the SelectRelationshipMappings algorithm brings no benefit.

Table 7 Comparison between different ontology matching executions with Anatomy data set.

Thus, the executions show that we can only respond positively to both RQ1 and RQ2 if that involved ontologies have relationships.

The interactive use of mapping anti-patterns by the Alin approach decreases the number of interactions with the expert without decreasing the F-measure (Tables 8 and 9), which respond positively to the RQ3.

Table 8 Comparison between Alin executions with and without mapping anti-patterns using the Conference data set.

Table 9 Comparison between Alin executions with and without mapping anti-patterns using the Anatomy data set.

5.4 Comparison between tools that participated in the OAEI 2018 interactive matching track

Alin participated in the OAEI 2018 interactive matching track. OAEI provides a comparison between tool performance in the interactive matching track each year, and it uses the Conference and the Anatomy data sets (Algergawy et al., Reference Algergawy, Cheatham, Faria, Ferrara, Fundulaki, Harrow, Hertling, Jiménez-Ruiz, Karam, Khiat, Lambrix, Li, Montanelli, Paulheim, Pesquita, Saveta, Schmidt, Shvaiko, Splendiani, Thiéblin, Trojahn, Vataščinová, Zamazal and Zhou2018), as we can see in Tables 10 and 11.

Table 10 Comparison between OAEI 2018 interactive matching track tools using Conference data set with 100% hit rate (Algergawy et al., Reference Algergawy, Cheatham, Faria, Ferrara, Fundulaki, Harrow, Hertling, Jiménez-Ruiz, Karam, Khiat, Lambrix, Li, Montanelli, Paulheim, Pesquita, Saveta, Schmidt, Shvaiko, Splendiani, Thiéblin, Trojahn, Vataščinová, Zamazal and Zhou2018).

Table 11 Comparison between OAEI 2018 interactive matching track tools using Anatomy data set with 100% hit rate (Algergawy et al., Reference Algergawy, Cheatham, Faria, Ferrara, Fundulaki, Harrow, Hertling, Jiménez-Ruiz, Karam, Khiat, Lambrix, Li, Montanelli, Paulheim, Pesquita, Saveta, Schmidt, Shvaiko, Splendiani, Thiéblin, Trojahn, Vataščinová, Zamazal and Zhou2018).

The tools AML, LogMap and XMAP (Tables 10 and 11) are interactive ontology matching tools which select attribute and relationship mappings, but in a non-interactive way, not taking into account the expert feedback.

In relation to the F-measure, the results show that Alin generated a high-level result when running the Conference data set (Table 10) and Alin got a result close to other tools when running the Anatomy data set (Table 11) when the expert hit 100% of the answers, which answers positively to RQ4.

In relation to the number of interactions with the expert, Alin, when running with the Conference data set, has a number of interactions more compatible with the other tools than with the Anatomy data set. That is because the ontologies of the Conference data set, contrary to those of Anatomy, contain attributes and relationships, which allows the use of the SelectRelationshipMappings and the SelectAttributeMappings algorithms to improve the set of selected mappings.

When the expert makes mistakes, Alin suffers a sharp fall, relative to other tools (Figures 4 and 5), of the F-measure. This fall is because Alin uses expert feedback as input to the used techniques, which causes these techniques to generate erroneous results when the expert fails. Besides, these outputs of the techniques serve to modify the set of selected mappings, which causes the set of selected mappings to get worse, that is, correct mappings can come out, and wrong mappings can enter.

Figure 4 Comparison of execution of several interactive tools with different hit rates – Conference data set

Figure 5 Comparison of execution of several interactive tools with different hit rates – Anatomy data set