This paper presents the results from the CANARD system in the OAEI 2019 campaign. CANARD is a system able to generate complex alignments. It is based on the notion of competency questions for alignment, as a way of expressing user needs. The system has participated in tracks where instances are available (populated Conference and Taxon datasets). This is the second participation of CANARD in the OAEI campaigns.
1.1
The CANARD (Complex Alignment Need and A-box based Relation
Discovery) system discovers complex correspondences between populated ontologies
based on Competency Questions for Alignment (CQAs). CQAs represent the
knowledge needs of a user and de ne the scope of the alignment [
In comparison with last year's version [
The approach has not changed much from last year [
The approach is detailed in the following steps over an example: the CQA expressed as a SPARQL query over the source knowledge base is: SELECT ?x ?y WHERE f ?x o1:paperWrittenBy ?y. g 1 Extract source DL formula es (e.g., o1:paperWrittenBy) from the SPARQL query. 2 Extract lexical information from the CQA, Ls set labels of atoms from the
DL formula (e.g., \paper written by"). 3 Extract source answers anss of the CQA (e.g., a pair of instances (o1:paper1, o1:person1)). 4 Find equivalent or similar target answers anst to the source instances anss (e.g. o1:paper1 o2:paper1 and o1:person1 o2:person1 ). 5 Retrieve the subgraphs of target answers: for a binary query, it is the set of paths between two answer instances as well as the types of the instances appearing in the path (e.g., a path of length 1 is found between o2:paper1 and o2:person1 ). The path is composed of only one property and there are no other instances than o2:paper1 and o2:person1 in this path. Their respective types are retrieved: (o2:Paper,o2:Document ) for o2:paper1 and (o2:Person) for o2:person1. 6 For each subgraph, retrieve Lt the labels of its entities (e.g., o2:writes ! \writes", o2:Person ! \person", o2:Paper ! \paper", etc.). 7 Compare Ls and Lt. 8 Select the subgraph parts with the best score, transform them into DL formulae. Keep the best path variable types if their similarity is higher than a threshold. (e.g., the best type for the instance o2:paper1 is o2:Paper because its similarity with the CQA labels is higher than the similarity of o2:Document ). 9 Filter the DL formulae based on their con dence score (if their con dence score is higher than a threshold). 10 Put the DL formulae es and et together to form a correspondence (e.g., h o1:paperWrittenBy , dom(o2:Paper) u o2:writes , i and express this correspondence in a reusable format (e.g., EDOAL). The con dence assigned to a correspondence is the similarity score of the DL formula computed.
The instance matching phase (Step 4 ) is based on existing owl:sameAs, skos:closeMatch, skos:exactMatch. In case these links are not available, and exact label matching is applied instead.
Finding a subgraph (Step 5 and 8 ) for a pair of instances consists in nding a path between the two instances. The shortest paths are considered more accurate. Because nding the shortest path between two entities is a complex problem, paths of length below a threshold are sought. First, paths of length 1 are sought, then if no path of length 1 is found, paths of length 2 are sought, etc. If more than one path of the same length are found, all of them go through the following process. When a path is found, the types of the instances forming the path are retrieved. If the similarity of the most similar type to the CQA is above a threshold, this type is kept in the nal subgraph.
For example, for a \paper written by" CQA with the answer (o2:paper1,o2:person1 ) in the target knowledge, a subgraph containing the following triples is found: 1. h o2:person1 , o2:writes , o2:paper1 i 2. h o2:paper1 , rdf:type , o2:Paper i 3. h o2:paper1 , rdf:type , o2:Document i 4. h o2:person1 , rdf:type , o2:Person i The most similar type of o2:person1 is o2:Person, which is below the similarity threshold. Triple 4 is then removed from the subgraph. The most similar type of o2:paper1 is o2:Paper. Triple 3 is therefore removed from the subgraph. o2:Paper 's similarity is above the similarity threshold: triple 2 stays in the subgraph. The translation of a subgraph into a SPARQL query is the same for binary and unary CQAs. Therefore, the subgraph will be transformed into a SPARQL query and saved as the following DL formula: dom(o2:Paper) u o2:writes .
The similarity between the sets of labels Ls and Lt of Step 7 is the cartesian product of the string similarities between the labels of Ls and Lt (equation 1). (1) (2) (3) sim(Ls; Lt) = X
X strSim(ls; lt) ls2Ls lt2Lt strSim is the string similarity between two labels ls and lt (equation 2). is the threshold for the similarity measure. In our experiments, we have empirically set up = 0:5. = 0:5 in our implementation.
strSim(ls; lt) = 8 < if :0 otherwise > , where = 1 levenshteinDist(ls; lt) max(jlsj; jltj)
The con dence value score of a correspondence (Step 9 ) is calculated with the following equation, then truncated to 1:
conf idence = labelSim + structuralSim Label similarity labelSim is the sum of the label similarity of each entity of the formula with the CQA.
Structural similarity structSim. This similarity was introduced to enhance some structural aspects in a formula. In the implementation of the approach, this value is set to 0.5 when a path between the two instances of the answer, and 0 for a unary CQA subgraph. Indeed, if the label similarity of the path is 0, the structural similarity hints that the fact that a path was found is a clue in favour of the resulting DL formula. 1.3
Automatic generation of CQAs OAEI tracks do not cover CQAs i.e., the
CQAs can not be given as input in the evaluation. We extended last year's query
generator so that it can output binary queries. The query generator now produces
three types of SPARQL queries: Classes, Properties and Property-Value pairs.
Classes For each owl:Class populated with at least one instance, a SPARQL
query is created to retrieve all the instances of this class. If <o1#class1> is a
populated class of the source ontology, the following query is created:
SELECT DISTINCT ?x WHERE f?x a <o1#class1>.g
Properties For each owl:ObjectProperty or owl:Dataproperty with at least one
instantiation in the source knowledge base, a SPARQL query is created to
retrieve all instantiations of this property. If <o1#property1> is an instantiated
property of the source ontology, the following query is created:
SELECT DISTINCT ?x ?y WHERE f?x <o1#property1> ?y.g
Property-Value pairs Inspired by the approaches of [
Implementation adaptations In the initial version of the system, Fuseki server endpoints are given as input. For the SEALS evaluation, we embedded a Fuseki server inside the matcher. The ontologies are downloaded from the SEALS repository, then uploaded in the embedded Fuseki server before the matching process can start. This downloading-uploading phase takes time, in particular when dealing with large les.
The CANARD system in the SEALS package is available at http://doi. org/10.6084/m9.figshare.7159760.v2. The generated alignments in EDOAL format are available at: { Populated Conference: http://oaei.ontologymatching.org/2019/results/ complex/popconf/populated_conference_results.zip { GeoLink: http://oaei.ontologymatching.org/2019/results/complex/ geolink/geolink_results.zip { Taxon: http://oaei.ontologymatching.org/2019/results/complex/taxon/ results_taxon_2019.zip
In this year's OAEI complex track, the Populated Conference, GeoLink and Taxon subtracks provide datasets with common instances. CANARD could generate alignments on these three datasets. 2 2.1
CANARD achieves this task with the longest runtime (96 min). The number of correspondences output by CANARD is detailed in Table 1. The results are detailed in Table 2.
CANARD achieves the highest the best query Fmeasure CQA Coverage score. AMLC achieves the best classical CQA Coverage, CANARD the second best. Both achieve CQA Coverage scores above ra1, but CANARD does not rely on an input alignment (in opposite to AMLC).
The classical Precision of CANARD is the lowest, its query Fmeasure precision above that of AMLC. 2.2
The number of correspondences output by CANARD is detailed in Table 3. The results are detailed in Table 4.
Relaxed precision and recall scores are calculated based on how the entities in the output correspondences are similar to those in the reference correspondences. All multiplied by a coe cient given the relation of the output correspondence and that of the reference one.
CANARD achieves the second best relaxed precision score, behind POMAP++ and the second best relaxed recall score behind AROA. CANARD has the longest runtime over the Taxon dataset (512 minutes 8h32). It is longer than last year's rutime (42 minutes) because the inclusion of binary queries in the process increases the number of input queries. Moreover the path nding algorithm consists in looking for all possible paths between two instances relies on SPARQL queries which take a long time to be executed.
The number of correspondences output by CANARD is detailed in Table 1. The results are detailed in Table 2.
Last year, CANARD had output 142 correspondences. This year it has output 791.
CANARD achieves the best CQA Coverage scores over the Taxon dataset. This year, the evaluation was oriented. For example, let's take a set of equivalent correspondences: Q=hSELECT ?x WHEREf ?x a agtx:Taxong, SELECT ?x WHEREf ?x a dbo:Speciesgi. If an output alignment agronomicTaxon-dbpedia contains h agtx:Taxon , dbo:Species , i but the alignment dbpedia-agronomicTaxon does NOT contain h dbo:Species , agtx:Taxon , i. The coverage score of Q for the pair agronomicTaxon-dbpedia is 1 but the coverage score of Q for dbpediaagronomicTaxon is 0. Last year the evaluation was non-oriented, so the coverage score of Q would be the same (1.0) for both pairs. Taking that into consideration, we computed that if the evaluation was oriented this year, the classical pair cmt-conference cmt-confOf cmt-edas cmt-ekaw conference-cmt conference-confOf conference-edas conference-ekaw confOf-cmt confOf-conference confOf-edas confOf-ekaw edas-cmt edas-conference edas-confOf edas-ekaw ekaw-cmt ekaw-conference ekaw-confOf ekaw-edas Average CQA Coverage of CANARD would have been 0.197, which shows signi cant improvement over last year's result: 0.13.
Some correspondences such as h agronomicTaxon:FamilyRank , 9 dbo:family .wikidata:Q756 , i or h agronomicTaxon:GenusRank , 9 dbo:genus .wikidata:Q756 , ( iwikidata:Q756 being the Plant class in wikidata) have more speci c target members because of the Plant type restriction. Such correspondences entail higher precision-oriented CQA Coverage and Precision scores than classical ones. 3
CANARD relies on common instances between the ontologies to be aligned. Hence, when such instances are not available, as for the Hydrography datasets, the approach is not able to generated complex correspondences. Furthermore, CANARD is need-oriented and requires a set competency questions to guide the matching process. Here, these \questions" have been automatically generated based on a set of patterns.
In comparison to last year's campaign, CANARD can now deal with binary CQAs in the form of SPARQL queries with two variables in the SELECT clause.
CANARD's runtime is extremely long. It depends (among other things) on the performance of the SPARQL endpoint it interrogates and the presence (or not) of equivalent links.
However, even with generated queries (instead of user input CQAs) it obtains some of the best coverage scores. 4
This paper presented the adapted version of the CANARD system and its preliminary results in the OAEI 2019 campaign. This year, we have been participated in the Taxon, Populated Conference and GeoLink track, in which ontologies are populated with common instances. CANARD was the only system to output complex correspondences on the Taxon track.
Elodie Thieblin has been funded by P^ole Emploi for the redaction of this paper. The authors have also been partially supported by the CNRS Blanc project RegleX-LD. pair agronomicTaxon-agrovoc agronomicTaxon-dbpedia agronomicTaxon-taxref agrovoc-agronomicTaxon agrovoc-dbpedia agrovoc-taxref dbpedia-agronomicTaxon dbpedia-agrovoc dbpedia-taxref taxref-agronomicTaxon taxref-agrovoc taxref-dbpedia Average