The evaluation of complex ontology alignments is an open challenge, as the traditional syntactic evaluation employed for simple alignments is too unforgiving given the di culty of accurately nding complex mappings and the usefulness of approximate solutions. In this work we compare and discuss two simple evaluation strategies: the entity-based evaluation strategy employed in the complex track of the OAEI 2020, and a novel element-overlap{based evaluation approach we propose. While it is clear that both strategies only provide a gross approximation of usefulness, our element-overlap strategy is the more accurate of the two, by taking semantic constructs into account. It is also more interpretable, as the nal metrics are based on the total number of mappings rather than an arbitrary number of entities. Given that complex mappings often fall outside the DL spectrum, and thereby are non-decidable, a signi cantly more accurate measure of usefulness is not trivial.
Ontology alignment (or matching) emerged to overcome the semantic
heterogeneity problem, by providing mappings interrelating the concepts of related
ontologies [
A complex ontology mapping is one where at least one of the mapped entities is an expression that involves multiple entities and/or logical operators or restrictions (e.g. Accepted contribution = min 1 acceptedBy). Complex mappings thus enable us to express rich semantic relations between entities of two ontologies, and precisely capture the rules for converting instance data between them.
Copyright © 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
The inclusion of a complex ontology alignment track in the Ontology
Alignment Evaluation Initiative1 (OAEI) of 2018 [
For simple mappings, the traditional evaluation employed in most OAEI
tracks|computing precision, recall and F-measure through exact match against
a reference alignment|is fairly adequate. One could argue that even in this
context, some mappings should be considered semi-correct, such as a
subsumption mapping between two classes that are in fact equivalent, or an equivalence
mapping where one of the classes is a superclass of the correct class [
For complex mappings the outlook is very di erent. First, building a
complete complex reference alignment that contains all non-trivial complex
correspondences is extremely laborious, which typically results in either a manual
evaluation of produced mappings [
A number of potential evaluation approaches have been overviewed by Zhou
et al. [
As of the 2020 edition, the OAEI's complex track employs two di erent
evaluation approaches in addition to the traditional exact match approach. In the
Hydrography, Geolink and Enslaved datasets, the evaluation is an entity-based
relaxed precision and recall approach which is comprehensive but neither fully
automated (as the transformation of complex mappings into mapped entities is
done manually) nor entirely accurate (as it doesn't account for the semantic
constructs in the complex mappings, only the entities). In the Conference and Taxon
datasets, the evaluation approach is based on query answering, automatically in
the case of Conference [
rewrite SPARQL queries, which is still an open challenge for more expressive mappings.
In this work, we propose a novel automated element-overlap evaluation strategy for complex ontology alignments, as well as a fully automated implementation of the entity-based evaluation strategy employed in the OAEI. We assess these two strategies by using them to reevaluate the OAEI 2020 complex results, and discuss their strengths and limitations. 2
The evaluation of complex ontology alignments has been comprehensively
overviewed by Zhou et al. [
C1: avoid the necessity of a full pairwise comparison of reference and system mappings.
Comparison
C2: determine the relation between a candidate mapping and a reference mapping.
C3: handle mapping decomposition (as two separate mappings can be equivalent to a single other mapping).
C4: factor the mapping relation.
Scoring
C5: accurately re ecting the quality/usefulness of each mapping. Aggregation
C6: factor partially correct mappings.
C7: factor cases of mapping decomposition.
C8: handle the occurrence of (redundant) multiple candidate mappings that are implied by a single reference mapping.
These authors also discuss and present the challenges for evaluation without a reference alignment, namely for query answering approaches such as those employed in the OAEI. However, as these approaches are less comprehensive than evaluation with a reference alignment, we focus only on the latter.
The entity-based relaxed precision and recall approach employed in the complex track of the OAEI2 begins with a manual pre-processing step, where reference and candidate mappings are converted into a list of key-value pairs of related entities plus their mapping relation. The key is a source ontology entity (or combination of entities) belonging to the mappings and manually chosen to represent them (several mappings can share the same key if they have the same 2 Unpublished; code provided by the OAEI complex track organisers source entity). The value is the set of all remaining source and target ontology entities for the mapping(s) that have the key. Considering the following mappings from cmt conf erence task of the OAEI (including reference and hypothetical candidate mappings) as a running example:
(A) [hasDecision some Acceptance] or [min 1 acceptedBy] =
Accepted contribution (B) ExternalReviewer = min 1 inverseOf (invited by) (C) Reviewer or ExternalReviewer = Reviewer
(A') hasDecision some Acceptance > Accepted contribution (B') ExternalReviewer = min 1 invited by (C') Reviewer = Reviewer The pre-processing step would result in the following key-value pairs:
(A) hasDecision : fAccepted contribution; Acceptance; acceptedByg; = (B) ExternalReviewer : finvited byg; = (C) Reviewer : fReviewer; ExternalReviewerg; =
(A') hasDecision : fAccepted contribution; Acceptanceg; > (B') ExternalReviewer : finvited byg; = (C') Reviewer : fReviewerg; = This pre-processing step is followed by an evaluation step, where each candidate mapping is compared with the reference mapping that has the same key-entity. This comparison is done by computing the entity-precision and entity-recall of the value-entities in the candidate mapping against those in the reference mapping, and multiplying these with a relation similarity score according to the following criteria: 1.0 if the candidate and reference mapping have the same relation; 0.8 if the candidate mapping has a narrower relation (i.e. < vs: =, = vs: >); 0.6 if the candidate mapping has a broader relation (i.e. > vs: =, = vs: <); 0.3 otherwise (e.g. < vs: >, > vs: <).
The nal score of an alignment is the average of the entity scores. Applying this evaluation algorithm to the example above would result in the scores listed in Table 1. The element-overlap{based evaluation strategy we propose aims at gauging the expected e ort to manually correct the alignment. It is based on a weighted Jaccard index between all elements of the mappings being compared (both ontology entities, and semantic constructs of the expressions) for scoring. It is not an edit-distance in the strict sense, as it captures similarity rather than dissimilarity. However, it allows us to quantify manual correction e ort while re ecting mapping correctness.
Given candidate and reference complex alignments, Ac and Aref , stored in data structures where each mapping is indexed by each of the ontology entities it contains, our algorithm begins with a pre-processing step, where all candidate and reference mappings are decomposed into lists of elements. For our running example, the decomposition would result in the following sets: Reference mappings: (A) fhasDecision, Acceptance, or, min, 1, accepted by, =,
Accepted contributiong (B) fExternalReviewer, =, min, 1, InverseOf , invited byg (C) fReviewer, or, ExternalReviewer, =, Reviewerg
(A') fhasDecision, Acceptance, >, Accepted contributiong (B') fExternalReviewer, =, min, 1, invited byg (C') fReviewer, =, Reviewerg
We then iterate through all candidate mappings and perform anchoring by nding related reference mappings (i.e., those that share at least one entity from both ontologies with the candidate mapping). For each related reference mapping, we compute the weighted Jaccard score between its list of elements and that of the candidate mapping. The weighted Jaccard score between two lists Lc and Lref is given by:
WJaccard(Lc; Lref ) = Pk2Lc[Lref max(count(k; Lc); count(k; Lref ))
Pk2Lc[Lref min(count(k; Lc); count(k; Lref )) This is an adaptation of the traditional Jaccard score between sets, taking into account that the same element can occur multiple times in a list (as is the case in a complex mapping).
We store the maximum Jaccard score found for each candidate mapping as well as for each reference mapping, which will be aggregated to compute the precision and recall respectively. Precision is computed as the average of the best scores obtained for each mapping in the candidate alignment (Ac), whereas Recall is the average of the best scores obtained for each mapping in the reference alignment (Aref ). The scores for our running example are listed in Table 2.
The detailed description of our algorithm is provided in Algorithm 1. As detailed in Section 2, the OAEI's entity-based evaluation strategy includes a manual pre-processing step whereby reference and candidate mappings are converted into key-value pairs of related entities plus the mapping relation. The fact this step is manual obviously hinders scalability and reproducibility.
Our proposed algorithm to automate the pre-processing step of this evaluation strategy aims at emulating the manual process of identifying key-entities while operating under a set of rules that ensure an objective solution, to enable reproducibility. First, the reference alignment is converted into key-value pairs under the following rules: 1. All mappings that have a single source entity will be identi ed by that entity as key, and have the set of target entities as value. If more than one mapping has the same key, the values will be merged. 2. All mappings that have multiple source entities will be identi ed by each of the source entities that is not already the key of a single-source mapping. (a) If there are multiple such source entities, the mapping will be decomposed into a key-value pair with each of those source entities as key, and the set of all target entities and all other source entities as value. (b) If there are no such source entities and the mapping contains exactly two source entities, it will be identi ed by the set of those two source entities as key. (c) If there are no such source entities and the mapping contains more than two entities, it will be identi ed by all pairwise combinations of source entities that are not keys of two-entity mappings. Algorithm 1 Element-overlap evaluation algorithm [Pre-processing] Function convert (A) init : HashTable lists for mappingi in A: for elementj in mappingi :
lists. add (mappingi ,elementj ) End Function init : HashTable listsref = convert (Aref ),
listsc = convert (Ac ), Scoresref , Scoresc init : double P recision = 0 for mappingi in Ac : [Anchoring] init : Ar sources , Ar targets for source entityj 2 mappingi :
Ar sources . addAll (Aref . get (source entityj )) for target entityj 2 mappingi :
Ar targets . addAll (Aref . get (target entityj )) Arelated = Ar sources . retainAll (Ar targets ) [Comparison & Scoring] for mappingj in Arelated sim = WJaccard (listsc . get (mappingi ),
listsref . get (mappingj )) if sim > Scoresref . get (mappingj )
Scoresref . add (mappingj , sim ) if sim > Scoresc . get (mappingi )
Scoresc . add (mappingi , sim ) [Aggregation]
P recision += Scoresc . get (mappingi ) P recision /= Ac . size init : double Recall = 0 for mappingi in Aref :
Recall += Scoresref . get (mappingi ) Recall /= Aref . size i. If there are multiple such pairs of source entities, the mapping will be decomposed into a key-value pair with each of those pairs as key. ii. If there is no such pair, the mapping will be identi ed by the set of all source entities.
Then, the candidate alignment is converted into key-value pairs using analogous rules, except that the reference alignment is used as anchor. For example, rule 2 becomes: 2'. All mappings that have multiple source entities will be identi ed by each of the source entities that is not the key of a single-source mapping in the reference alignment. The same logic is applied to all rules, as the goal is to establish a parallel between the candidate alignment and the reference alignment so as to enable the evaluation of the former. 4 4.1
The datasets we employed to compare the evaluation strategies were the
Conference, Geolink and Hydrography datasets from the OAEI 2020 Complex track,
which are detailed in Table 3. For the Geolink and Hydrography datasets we use
the reference alignment provided by the OAEI, and for the Conference dataset
we employ the reference alignment provided by Thieblin et al. [
Alignment Evaluation system strategy dataset. This means that our automated implementation did not replicate all the rules that went into the manual pre-processing of the alignments, although it provided a reasonable approximation. There were likely additional criteria of a di erent nature (e.g. favouring classes over properties as key-entities of mappings) which we failed to identify in our analysis of the pre-processed alignments from the OAEI.
We must also note that both the OAEI entity-based pre-processing and our attempt to automate it are unnecessarily complex. Representing mappings by only key-entities, instead of simply contemplating all the entities in a mapping seems rather arbitrary, and could conceivably lead to a candidate mapping being represented by a key entity that would result in it being compared with a reference mapping that is not the most similar to it. Moreover, the result of this approach is that the precision and recall scores are neither based on the number of mappings (as in a traditional evaluation and our element-overlap approach) nor based on the total number of mapped entities (as in a pure entity-based approach), but somewhere in between, making them hard to interpret or compare. On the whole, a complete decomposition of the complex alignment into key-value pairs that encompass all mapped entities would be both more straightforward to implement and more intuitive to interpret. 4.2.2 Element-overlap vs. entity-based We can observe from the results that the entity-based evaluation is consistently more generous in terms of precision than the element-overlap-based evaluation, while recall tends to be similar for both strategies. This can be attributed to the fact that the element-overlap approach factors both the ontology entities and the semantic constructs of the expressions in its scoring, whereas the entity-based evaluation factors only the entities. Since it is generally easier to automatically nd related entities than to infer the exact semantic relations between them, matching systems would tend to score higher in precision under an entity-based evaluation.
An alignment accurately capturing related entities is the most critical aspect for a human reviewer, as nding which entities are related is a more timeconsuming task than assessing how they are related. However, there is still a cost to the latter, which should be factored into scoring the usefulness of a mapping. As an example, consider the two reference mappings (R1, R2) from the conf erence conf Of task and the two corresponding hypothetical candidate mappings (S1, S2): (R1) Reviewed Contribution = min 1 InverseOf(reviews) (R2) Reviewer = min 1 reviews (S1) Reviewed Contribution = min 1 reviews (S2) Reviewer = min 1 InverseOf(reviews) Essentially, the candidate mappings have inverted the intended usage of the reviews property, which would require analysis of the de nition of the property to correct. Yet, under an entity-based evaluation, both candidate mappings would score 100% in precision and recall, as the presence of the InverseOf construct is invisible to this evaluation strategy. With our element-overlap, on the other hand, the construct would be factored into the score, providing a more accurate measure of the usefulness of the mappings.
Table 5 summarises how the two strategies address the challenges listed in Section 2. There are several challenges not addressed by our element-overlap approach, as we based it on a simple Jaccard index, knowingly sacri cing accuracy for scalability. However, there is no challenge that it addresses worse than the entity-based approach. In assessing the relation between mappings and re ecting their usefulness, it is more accurate because it takes the semantic constructs of the mappings into account. It also accounts for cases of mapping decomposition, if not very accurately, as it allows multiple candidate mappings to be compared against the same reference mapping. Since the two approaches have a similar computational cost (the pre-processing cost is much lower for the element-overlap, but the comparison cost is higher because each mapping can be compared with several other mappings), the element-overlap should be preferred. 4.2.3 Jaccard vs. other similarity metrics One limitation of our element-overlap strategy is that it doesn't factor the order in which the elements appear in a mapping, and thus would not be able to distinguish between cases such as the following two hypothetical mappings that have the opposite meaning: { (Reviewer or ExternalReviewer) and (not Author) = Reviewer { not (Reviewer or ExternalReviewer) and author = Reviewer To accurately capture such cases, we could use a canonical edit-distance approach, such as Levenshtein, but this would produce erroneous results in cases where the order of elements is irrelevant, such as within disjunction or conjunction (e.g. if Reviewer were swapped with ExternalReviewer), and would also have a higher computational cost. Another limitation of our strategy is that it cannot capture semantically related mappings (e.g. where one has a subclass or subproperty of the other) or semantically equivalent mappings that are syntactically distinct, such as these produced by CANARD for the conf erence conf Of task: { [contributes and domain(Reviewer)] and
[reviews and domain(Review)] = reviews { [InverseOf(has authors) and domain(Reviewer)] and
[InverseOf(has a review) and domain(Review)] = reviews These mappings are semantically equivalent because has authors and contributes are inverse properties in the conference ontology, and so are has a review and reviews. To detect such mappings, an evaluation strategy would have to employ an OWL reasoner, which would have an even greater computational cost. Furthermore, there would be hurdles to overcome in that: (a) complex alignments are often expressed in the EDOAL format4 which includes semantic constructs that aren't expressible in OWL; and (b) even OWL compliant mappings can be beyond DL semantics and therefore compromise the decidability of the reasoning problem.
Thus, while our element-overlap approach only provides a gross estimate of the usefulness of mappings, providing a signi cantly more accurate estimate in a scalable manner is not trivial. 5
We have proposed a novel element-overlap{based evaluation strategy for complex ontology alignments, as well as an automated pre-processing algorithm that
approximates the manual pre-processing of the entity-based evaluation employed in the OAEI 2020.
We conclude that the entity-based evaluation employed in the OAEI is
unnecessarily complex, and falls shorter of addressing the challenges identi ed for the
evaluation of complex alignments [
Nevertheless, in future work we will explore simple rule-based approaches for semantic comparison that can provide a more accurate evaluation without sacri cing scalability.
Acknowledgements The authors would like to thank Lu Zhou for kindly providing the source code used in the OAEI evaluation. This work was supported by FCT through the LASIGE Research Unit (UIDB/00408/2020 and UIDP/00408/2020). It was also partially supported by the KATY project which has received funding from the European Union's Horizon 2020 research and innovation program under grant agreement No 101017453.