Automatic evaluation of complex alignments: An instance-based approach

2.1. Complex ontology alignment

Ontology matching (as in [9]) is defined as the process of generating an alignment A between two ontologies: a source ontology o and a target ontology o ′ . A is directional, denoted A o → o ′ . A o → o ′ is a set of correspondences ⟨ e , e ′ , r , n ⟩ . Each correspondence expresses a relation r (e.g., equivalence (≡), subsumption (⊒, ⊑)) between two members e and e ′ , and n expresses the level of confidence [ 0..1 ] in this correspondence. A member can be a single ontology entity (class, object property, data property, individual) of respectively o and o ′ or a more complex construction which is composed of some entities using constructors or transformation functions (as in the examples in the following). From that, two types of correspondences are considered depending on the type of their members [41]:

A simple correspondence is usually noted (s:s), and a complex correspondence can be (s:c) if its source member is a single entity, (c:s) if its target member is a single entity or (c:c) if both members are complex entities. An approach which generates a complex alignment will be referred as a “complex matching approach”, a “complex matching system” or a “complex matcher” in the rest of this paper.

2.2. Competency questions for alignment (CQAs)

In ontology authoring, in order to formalise the knowledge needs of an ontology, competency questions (CQs) have been introduced as ontology’s requirements in the form of questions the ontology must be able to answer [11]. As defined in [37,43], a competency question for alignment (CQA) is a competency question which should be covered by two or more ontologies, i.e., it expresses the knowledge that an alignment should cover (if both ontologies’ scopes can answer the CQA). The first difference between CQA and CQ is that the scope of the CQA is limited by the intersection of its source and target ontologies’ scopes. The second difference is that this maximal and ideal alignment’s scope is not known a priori (as it is the purpose of the alignment). As the ontology authoring competency questions (CQs) [27], a CQA can be expressed in natural language or as SPARQL SELECT queries.

Inspired from the predicate arity in [27], the notion of question arity, which represents the arity of the expected answers to a CQA was introduced in [43]:

A unary question expects a set of instances or values, e.g., “Which are the accepted papers?” (paper1), (paper2).

3.1. Complex alignment evaluation metrics

Most works on alignment evaluation address the evaluation of simple alignments using a reference alignment or a sample of it. This is what has been done in the context of the OAEI campaigns. With respect to the evaluation of complex alignments, they have been evaluated manually, usually in terms of precision [25,28,29,47], or on specific datasets in order to compute recall. In particular, the approach adopted in [25,47] estimated their recall based on a recurring pattern (Class by attribute-value) between DBpedia and Geonames. They estimated the number of occurrences of this pattern between these ontologies and calculated the recall based on this estimation. In [26] a set of reference correspondences between two ontologies was manually created, involving few reference correspondences from which only two could not be expressed with simple correspondences. In [47] the authors proposed an algorithm to create an evaluation dataset that is composed of a synthetic ontology containing 50 classes with Class-by-attribute-value correspondences with DBpedia and 50 classes with no known correspondences with DBpedia. Both ontologies are populated with the same instances. In [34], inspired from [12], the approach for discovering complex attribute correspondences (i.e., {First Name, Last Name} = {Author}) between web interfaces is evaluated using target accuracy (that includes target precision and target recall) as metric. It evaluates how similar the generated alignment is with respect to a set of manually collected ones, using the notion of synonym attribute sets.

As discussed in [43] (inspired from [2]), alternative metrics of accuracy and top-x accuracy have been also applied in evaluation settings in which the number of correspondences is predefined, e.g., there is one correspondence for each entity of the target schema/ontology. The accuracy is calculated as the percentage of predefined questions having a correct answer. A “question” in this context could be a source entity to be matched and the “answers” the correspondences having this entity as source member. Some approaches output various answers for each question, e.g., a ranked list of correspondences for each source entity. In this case the top-x accuracy is the percentage of questions whose correct answer is in the top-x answers to the question. For example, top-3 accuracy is the fraction of source entities for which the correct correspondence is in the three best correspondences generated by the system. Alternatively, the approach in [39], to evaluate complex correspondences between agronomic ontologies is based on manually comparing the results of the reference queries and queries automatically rewritten with the help of the complex alignments.

3.2. Complex alignment benchmarks

As discussed above, complex matchers are usually evaluated on custom evaluation alignment sets, usually covering the specificities of the approach to be evaluated. Recently, the first complex benchmark has been introduced in the OAEI campaigns [40]. The track consists of four datasets from different domains and considering different evaluation strategies:

In 2018, only two systems, AMLC [10] and CANARD [44], were able to generate complex correspondences for those datasets. In 2019, a new system has been proposed, AROA4

Regarding task-oriented evaluation, [9] argued that different task profiles can be established to explicitly compare matching systems for certain tasks, such as ontology evolution or query answering, that have different constraints in terms of coverage and runtime. One such task-oriented evaluation approach was introduced in the OAEI in 2015 at the OA4QA track5

In [13], an “end-to-end” evaluation in which a set of queries are rewritten using an evaluated alignment is proposed. The results of the queries are manually classified by relevance for a user on a 6-point scale. This evaluation was performed with two rewriting systems. If a source member e does not appear in any correspondence of the alignment, the upwards rewriting system will use super-classes of e which appear as source member in the alignment’s correspondences and the downwards system will use subclasses of e. Three alignments were evaluated. For each alignment, 20 concepts were randomly selected to be queried and evaluated.

While the task-based evaluation is relevant for both simple and complex alignments, some tasks tend to have higher expressiveness requirements, such as query rewriting and ontology merging, as discussed in [41]. Complex alignments for query rewriting have been the focus of the work of [19],6

In fact, the query rewriting task can be seen as one of the main applications for complex alignments, and evaluation approaches based on this task are highly relevant. In the case of simple alignments, a naive approach for rewriting SPARQL queries can be to simply replace the IRI of an entity of the initial query by the IRI of the corresponding entity in the alignment, as described in [4]. For complex alignments, such a naive approach is not enough, as the semantics of the alignment itself has to be taken under consideration. [7] proposed an approach for writing specific SPARQL CONSTRUCT queries, but most query rewriting systems still rely on simple or (s:c) complex correspondence and fail in covering highly expressive (c:c) correspondences.

With respect to the evaluation of complex alignments, several works focus on manually evaluating alignments, in terms of precision as in [28,29], calculating recall on recurring patterns as in [25,47], or relying on a sample of reference correspondences [26]. While most of these approaches focus on the comparison of correspondences, we shift the problem to the comparison of instances. We propose an evaluation benchmark that considers queries as references and relies on metrics based on query coverage (as for recall) and intrinsic precision (as for precision without a reference alignment). Our approach requires, however, datasets populated in a controlled manner, differently from the datasets in [49].

As [32], we have queries as references instead of reference alignments. Close to ours, the evaluation in [32] relies on a synthetically populated version of the Conference dataset. However, their queries are executed over a merged ontology and alignments are limited to simple correspondences. Here, the queries are executed over different populated ontologies. As [13], here a set of queries are rewritten using an evaluated alignment. However, their evaluation process relies on manually classifying the query results.

Table 1 summarizes the existing alignment evaluation benchmarks that are close to our proposal (CQA benchmark, marked in bold in Table 1). Automation for (c:c) correspondences is still an open issue in the field. The proposal here is to automatise the evaluation process by shifting the problem to the comparison of instances, as detailed in the following sections.

Figure 3 presents the overall workflow adopted in the proposed approach. The steps followed in the evaluation process are:

Anchor selection The anchor selection step consists of outputting a pair of comparable objects ⟨ x i , x r j ⟩ . x i is an object related to the evaluated alignment A eval and x r j is an object related to the reference reference . In the case the reference is equivalent queries, x i can be a query derived from A eval and x r j a reference query.

4.2. CQA coverage metric

With this evaluation strategy, the reference is a set of equivalent CQAs in the form of SPARQL queries. An evaluated alignment A eval will be used to rewrite each source CQA. The rewritten queries will then be compared to the reference target CQA. The comparison of the queries is instance-based and a value is associated with each query relation based on the common part of the evaluated query and target CQA instances. The scoring metric chosen is the one keeping the comparison relation value. A best-match aggregation is locally performed over the reference queries. The locally aggregated scores are then aggregated by an average. In the following, each step of the proposed evaluation process is described.

4.3. Intrinsic precision

The CQA coverage evaluation locally aggregates the results over the CQA and not the rewritten queries because of the noise added by the rewriting systems. In return, an alignment with all the possible correspondences (correct and erroneous) between the source and target ontologies would obtain a good CQA coverage score. To counterbalance the CQA coverage score, we propose to measure the intrinsic instance-based Precision of an alignment.

For each correspondence c i in the evaluated alignment, the instances I s represented by the source member are compared to the instance I t represented by the target member. Each correspondence is then classified as an equivalent, subsumed, overlapping, or disjoint, given the relation between I s and I t , or empty if I s = I t = ∅ . Therefore, a correspondence can be empty if both its members are either unsatisfiable entities or non populated entities.

Different precision scores are given for each type of correspondence member relation: the equivalent precision measures the percentage of correspondences whose members are exactly populated with the same instances, the subsumed precision measures the percentage of correspondences whose members subsume one another, the same goes for overlapping and not disjoint which consider correct all correspondences except the disjoint ones.

5.1. Dataset creation methodology

The purpose here is to create a dataset on which ontology matchers can be run and on which the evaluation described in the previous section can be performed. Therefore, the dataset must contain populated ontologies and a set of CQAs expressed as SPARQL queries over these ontologies. The population step is very important as the chosen instances may influence the result of the evaluation.

The proposed methodology has the following main steps:

In this methodology, the interpretation of the ontologies is the same for ontology population and CQA creation. The creation of CQAs can be done by interviewing users and domain experts, as recommended in the NeOn methodology [35] for competency question authoring. The CQAs can also derive from the competency questions which were used to design the ontologies of the dataset. In this implementation, however, one expert created the CQAs. This set has been discussed with a second expert who judged the set exhaustive enough for covering the conference organisation scenario.

In [41], (c:c) correspondences were not included in the dataset hence no exhaustive coverage could be guaranteed. However, as CQAs represent basic pieces of knowledge, they can be exhaustively covered by an alignment regardless of the shape of the correspondences. Using the same list of CQAs for ontology population and evaluation also insures the consistency of the answers of the evaluation CQAs.

5.2. Conference dataset

The dataset used here is the Conference dataset7

In the first OAEI complex track, an evaluation was proposed over a consensual complex alignment between three ontologies (cmt, conference, ekaw) [40]. Here, the five ontologies covered by [41] have been populated: cmt, conference (Sofsem), confOf (confTool), edas and ekaw (Table 2).

Even though this dataset has been largely used, it has only been partially populated. In the OA4QA track, only the classes covered by the 18 queries were populated and the creation of the synthetic A box has not been documented.

In order to create the CQAs and re-interpret the Conference ontologies, the conference organisation scenario has been considered. First, the list of CQA has been established by examining a real-life use case: the Extended Semantic Web Conference 2018 edition. Second, the list of CQAs created from this use case has been extended by exploring the conference ontologies scope. The Extended Semantic Web Conference8

For the evaluation, the focus is on CQAs which can actually be covered by two or more ontologies. To write the CQAs which will be used in the dataset, the list of CQAs used for the population was trimmed:

The remaining CQAs were then written as SPARQL SELECT queries by adapting the SPARQL INSERT queries. Table 8 shows the number of CQAs which were covered by the pivot format, by each ontology (in the SPARQL INSERT queries) and which were transformed into SPARQL SELECT queries for the evaluation dataset. 278 SPARQL SELECT queries result from this process.

6.1. Evaluated alignments

Existing alignments between the Conference ontologies in EDOAL format11

The ra1 alignment had been used as input by the systems of Ritze_2010 and Faria_2018. Ra1 has been added to these two alignments for the CQA coverage evaluation. The precision evaluation was made only on the complex correspondences (the output of the original approaches).

The CQA coverage evaluation was run over all datasets in order to measure the standard deviation of the query precision, recall and f-measure between the datasets, as shown in Table 9. The standard deviation is maximal for Faria_2018 and Ritze_2010, but is still rather low ( 10 − 3 ). As the standard deviation is low, the CQA coverage evaluation was performed over the 100% dataset so that the same dataset could be used for CQA coverage and instance-based precision evaluation (Table 10). Ritze_2010 and Faria_2018 both have better coverage than ra1 that they include. It means that the complex correspondences in these alignments are indeed a complement to the simple ones.

Globally, as shown in Table 10, the Query_rewriting alignments have a better coverage than the others. An exception for the edas-confOf pair could be noted. The Ontology_merging alignment outperforms the Query_rewriting one. This is explained by the choice made in the methodology for the creation of both alignments combined with the rewriting systems. In the Ontology_merging alignments, unions of properties were separated into individual subsumptions which were usable by the rewriting system, whereas in the Query_rewriting one, the subsumptions were unions. For example: Therefore, when a query contained the edas:hasStartDate relation, the Ontology_merging correspondence could be used, but the Query_rewriting ones could not. The precision-oriented methodology prevented the addition of the two Ontology_merging correspondences to the Query_rewriting alignment.

When closely looking at the results, many CQAs retrieving literals (titles, names, etc.) were not rewritten by the alignments. This is mainly explained because the rdfs:label property was introduced in the population phase when no labelling property was included in the original ontologies. The CQAs which needed (c:c) correspondences to be rewritten were not covered by the evaluated alignments. Indeed, these alignments are restricted to (s:s), (s:c) and (c:s) correspondences.

Table 11 shows the precision of the alignments considering different sets of correspondences as correct. The equivalent precision is calculated by considering that only the correspondences whose members are equivalent are correct. The subsumed precision considers correct the correspondences whose members subsume one another (this includes the equivalent ones). The overlapping precision considers correct the correspondences with equivalent, subsumed or overlapping members. The not disjoint precision considers all correspondences whose members are not disjoint correct. The difference with the overlapping one is that an empty correspondence is correct in this case.

The real precision of the alignments is considered to be between the equivalent and the not disjoint values. The Query_ rewriting, Ontology_merging alignments do not have a very good equivalent precision score (0.42 and 0.43). Indeed, their correspondences include a lot of subsumptions. For the subsumed, overlapping and not disjoint scores, their scores are much higher (0.94 and 0.91). ra1 has a better equivalence score (0.56) than the other two manually created alignments because it originally contains only correspondence with an equivalence relation. However, given this score seems low for a reference alignment. This low score is partly due to the different CQA coverage of the ontologies in the population phase.

For example, for the pair cmt-edas, the ra1 correspondence ⟨ cmt:Document , edas:Document , ≡ , 1.0 ⟩ is a subsumption in the ontology population. cmt:Document has for subclasses cmt:Paper and cmt:Review, whereas edas:Document has for subclasses edas:Paper, edas:Review, edas:Programme and edas:SlideSet which were all populated. Therefore, even if the correspondence is correct with an equivalence relation, its instance interpretation is a subsumption. Note that the instance interpretation could also be an overlap if cmt had another subclass (e.g., Website) which did not appear in edas.

The low equivalence score of ra1 is also due to the different interpretation of the ontologies. For example, in the pair cmt-confOf, the ra1 correspondence ⟨ cmt:hasAuthor , confOf:writtenBy , ≡ , 1.0 ⟩ is a subsumption in the ontology population. cmt:hasAuthor was interpreted as the “has 1st author” relationship because of its functional property (Section 5.3.1).

Ritze_2010 has only equivalent or disjoint correspondences, therefore its precision scores are the same for all metrics. Faria_2018 achieves a good precision score overall (between 0.65 and 0.71).

Given the different population issues, the overlapping and not disjoint scores give a good representation of the alignment precision.

Table 12 shows the results of the evaluation over the alignments. The CQA coverage and precision scores have been aggregated in an harmonic mean (called HM in Table 12). Overall, the Query_rewriting and Ontology_merging alignments have the better results. This is satisfactory given that these two alignments are complex reference alignments on this dataset. Even if ra1 has the best precision, its low CQA coverage (0.42) shows that a lot of CQAs from the benchmark need complex alignments to be covered. Faria_2018 and Ritze_2010 are compared to the other even if they do not contain the same number of pairs. Therefore, these numbers cannot be exactly compared to the others.

In the results of the OAEI 2018 [1], the precision measured for the Faria_2018 alignment was 0.54 (cf. Table 13). The instance-based precision gives the same result as the manual evaluation for the cmt-ekaw pair. For the other pairs, the gap is quite important. For the cmt-conference pair, this is probably due to a difference of interpretation of the ontologies. The conference:Written_contribution being considered as a superclass of cmt:Paper in the OAEI 2018 evaluation, but equivalent classes in the ontology population.

In the conference-ekaw pair, the ⟨ ∃ conference: was_a_track-workshop_chair_of. conference:Tutorial, ekaw:Tutorial_Chair , ≡ , 0.369 ⟩ was considered correct in the OAEI 2018 evaluation. However, an axiom of the conference ontology restrains the domain of conference:was_a_track-workshop_chair_of to conference:Track ⊔ conference:Workshop. This has been taken into account in the ontology population and the correspondence was evaluated as disjoint for the evaluation system.