AROA Results for 2019 OAEI

Abstract

This paper introduces the results of alignment system AROA in the OAEI 2019 campaign. AROA stands for Association Rule-based Ontology Alignment system. This ontology alignment system can produce simple and complex alignment between ontologies that share common instance data. This is the rst participation of AROA in the OAEI campaign, and it produces best performance on one of complex benchmarks (GeoLink).

-

1.1

Presentation of the system

State, purpose, general statement

AROA (Association Rule-based Ontology Alignment) system is aimed to automatically generate simple and complex alignment between two and more ontologies. These ontologies would be required to share common instance data because AROA relies on association rule mining and would require these instances as inputs. After generating a set of association rules, AROA utilizes some simple and complex correspondences that have been widely accepted in Ontology Matching community [ 4, 6 ] to further narrow the large number of rules down to more meaningful ones and nally establishes the alignments. 1.2

Speci c techniques used

Figure 1 illustrates the overview of AROA alignment system. In this section, we introduce each step of AROA alignment system along with some concepts that we frequently use in AROA system, such as association rule mining, FP-growth algorithm, and complex alignment generation.

Clean Triple. First, AROA extracts all triples as the format of hSubject, Predicate, Objecti from the source and target ontologies. Each item in a triple is expressed as a web URI. After collecting all of the triples, we clean the data based on the following criteria: we only keep the triples that contain at least one entity under the source or the target ontology namespace or the triples contain rdf:type information, since our algorithm relies on this information.

Copyright c 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).

Generate Transaction Database. After ltering process, we generate the transaction database as the input for the FP-growth algorithm. Let I = fi1; i2; : : : ; ing be a set of distinct attributes called items. Let D = ft1; t2; : : : ; tmg be a set of transactions where each transaction in D has a unique transaction ID and contains a subset of the items in I. Table 1 shows a list of transactions corresponding to a list of triples. Instance data can be displayed as a set of triples, each consisting of subject, predicate, and object. Here, subjects represent the identi ers and the set of corresponding properties with the objects represent transactions, which are separated by the symbol \j". I.e., a transaction is a set T = (s; Z) such that s is a subject, and each member of Z is a pair (p; o) of a property and an object such that (s; p; o) is an instance triple.

Generate Typed Transaction Database. Then we replace the object

in the triples with its rdf:type3 because we focus on generating schema-level (rather than instance-level) mapping rules between two ontologies, and the type 3If there are multiple types of the object, it can also combine the subject and predicate as additional information to determine the correct type, or keep both types as two triples.

TID s1 s2 s3

Itemsets p1jo1, p2jo2, p4jo4 p1jo1, p2jo2, p3jo3, p4jo4 p1jo1, p2jo2 TID Itemsets x1 gbo:hasAwardjgbo:Award, gmo:fundedByjgmo:FundingAward x2 gbo:hasFullNamejxsd:string, gmo:hasPersonNamejgmo:PersonName x3 rdf:typejgbo:Cruise, rdf:typejgmo:Cruise information of the object is more meaningful than the original URI. If an object in a triple has rdf:type of a class in the ontology, we replace the URI of the object with its class. If the object is a data value, the URI of the object is replaced with the datatype. If the object already is a class in the ontology, it remains unchanged. Tables 2 and 3 show some examples of the conversion.

Generate Association Rules. Our alignment system mainly depends on a data mining algorithm called association rule mining, which is a rule-based machine learning method for discovering interesting relations between variables in large databases [ 3 ]. Many algorithms for generating association rules have been proposed, like Apriori [ 1 ] and FP-growth algorithm [ 2 ]. In this paper, we use FP-growth to generate association rules between ontologies, since the FP-growth algorithm has been proven superior to other algorithms [ 2 ]. The FPgrowth algorithm is run on the transaction database in order to determine which combinations of items co-occur frequently. The algorithm rst counts the number of occurrences of all individual items in the database. Next, it builds an FP-tree structure by inserting these instances. Items in each instance are sorted by descending order of their frequency in the dataset, so that the tree can be processed quickly. Items in each instance that do not meet the prede ned thresholds, such as minimum support and minimum con dence (see below for these terms), are discarded. Once all large itemsets have been found, the association rule creation begins. Every association rule is composed of two sides. The lefthand-side is called the antecedent, and the right-hand-side is the consequent. These rules indicate that whenever the antecedent is present, the consequent is likely to be as well. Table 4 shows some examples of association rules generated from the transaction database in Table 1.

Generate Alignment. AROA utilizes some simple and complex correspondences that have been widely accepted in Ontology Matching community to further lter rules [ 4, 6 ] and nally generate the alignments. There are totally 10 di erent types of correspondences that AROA covers in this year. Table 5 lists all the simple and complex alignment correspondences and corresponding category. Since the association rule mining might generate a large number of rules, in order to narrow the association rules down to a smaller set, AROA follows these patterns to generate corresponding alignments. For example, Class by Attribute Type (CAT) is a classic complex alignment pattern. This type of pattern was rst introduced in [ 4 ]. It states that a class in the source ontology is in some relationship to a complex construction in the target ontology. This complex construction may comprise an object property and its range. Class C1 is from ontology O1, and object property op1 and its range t1 are from ontology O2.

Association Rule format: rdf:typejC1 ! op1jt1 Example: rdf:typejgbo:PortCall ! gmo:atPortjgmo:Place Generated Alignment: gbo:PortCall(x) ! gmo:atPort(x; y) ^ gmo:Place(y) In this example, this association rule implies that if the subject x is an individual of class gbo:PortCall, then x is subsumed by the domain of gmo:atPort with its range gmo:Place. The equivalence relationship can be generated by combining another association rule holding the reverse information. Other simple and complex alignments are also generated by following the same steps. 1.3

Adaptations made for the evaluation

AROA is an instance-based ontology alignment system. Therefore, AROA embeds Apache Jena Fuseki server in the system. The ontologies are rst downloaded from the SEALS repository. And then, AROA uploads and stores the ontologies in the embedded Fuseki server, which might take some time for this step to load large-size ontology pairs. The generated alignments in EDOAL format are available at this link.4 2

Results

Since this is the rst-year participation, AROA alignment system only evaluates its performance on the GeoLink benchmark. We will evaluate on other benchmarks in the near future. In the GeoLink benchmark, there are 19 simple mappings, including 10 class equivalences, 2 class subsumption, and 7 property equivalences. And there are 48 complex mappings, including 5 property subsumption, 26 property chain equivalences, and 17 property chain subsumption. Table 6 shows alignment patterns and categories in the GeoLink Benchmark and the results of AROA system. We list the numbers of identi ed mappings for each pattern. There are two dimensions that we can look into the performance. One is the entity identi cation, which means, given an entity in the source ontology, the system should be able to generate related entities in the target ontology. Another dimension is relationship identi cation, which the system should detect the correct the relationship between these entities, such as equivalence and subsumption. Therefore, we list the number of correct entities and the number of correct relationships in order to help the reader to understand the strengths and weaknesses of the system. For example, In the Table 6, AROA correctly identi es all 1:1 class equivalence including entity and relationship. However, AROA also nds one class subsumption alignment, which is the class P ortCall in the GeoLink Base Ontology (GBO) is related to the class F ix in the GeoLink Modular Ontology (GMO). However, it outputs the relationship between P ortCall and F ix as equivalence, which it should be subsumption. Therefore, we count the number of correct entities as 1 and number of correct relations as 0. This criterion is also applied to other patterns. In addition, we compare the performance of AROA against other alignment systems in Table 7. And AROA achieved the best performance in terms of relaxed recall and f-measure.5 4http://oaei.ontologymatching.org/2019/results/complex/geolink/geolink results.zip 5http://oaei.ontologymatching.org/2019/results/complex/geolink/index.html From the performance comparison, only AROA and CANARD [ 5 ] can generate almost correct complex alignment, which means some alignments found by these two systems may not be completely correct, but it can be easily improved by semi-automated fashion. For example, the system can produce correct entities that should be involved in a complex alignment, but it doesn't output the correct relationship. Another situation is that the system can detect the correct relationship but fails to nd all the entities. Based on these situations, we will investigate the incorrect alignments and improve the algorithm to nd the relationship and entities as accurate as possible. 4

Conclusions

This paper introduces the AROA ontology alignment system and its preliminary results in the OAEI 2019 campaign. This year, AROA evaluates its performance on GeoLink benchmark and achieves the best performance in terms of recall and f-measure. We will continue to evaluate AROA on other benchmarks and improve the algorithm in the near future.

References

1. Agrawal , R. , Srikant , R.: Fast algorithms for mining association rules in large databases . In: VLDB'94, Proc. of 20th International Conference on Very Large Data Bases, September 12-15 , 1994 , Santiago de Chile, Chile. pp. 487 { 499 ( 1994 ), http://www.vldb.org/conf/1994/P487.PDF

2. Han, J ., et al.: Mining frequent patterns without candidate generation: A frequent-pattern tree approach . Data Min. Knowl. Discov . 8 ( 1 ), 53 { 87 ( 2004 ). https://doi.org/10.1023/B:DAMI. 0000005258 .31418.83, https://doi.org/10.1023/B:DAMI. 0000005258 .31418.83

3. Piatetsky-Shapiro , G. : Discovery, analysis, and presentation of strong rules . In: Knowledge Discovery in Databases , pp. 229 { 248 . AAAI/MIT Press ( 1991 )

4. Ritze , D. , Meilicke , C. , Svab-Zamazal , O. , Stuckenschmidt , H.: A pattern-based ontology matching approach for detecting complex correspondences . In: Proceedings of the 4th International Workshop on Ontology Matching (OM- 2009 ) collocated with the 8th International Semantic Web Conference (ISWC-2009) Chantilly , USA, October 25 , 2009 ( 2009 ), http://ceur-ws. org/ Vol- 551 /om2009 Tpaper3.pdf

5. Thieblin , E. , et al.: CANARD complex matching system: results of the 2018 OAEI evaluation campaign . In: Proc. of the 13th Int. Workshop on Ontology Matching, OM@ISWC 2018 , Monterey, CA, USA, Oct. 8 , 2018 . pp. 138 { 143 ( 2018 ), http://ceur-ws. org/ Vol- 2288 /oaei18 paper4.pdf

6. Zhou , L. , et al.: A complex alignment benchmark: Geolink dataset . In: The Semantic Web - ISWC 2018 - 17th International Semantic Web Conference , Monterey, CA, USA, October 8- 12 , 2018 , Proceedings, Part II. pp. 273 { 288 ( 2018 ). https://doi.org/10.1007/978-3- 030 -00668-6 17, https://doi.org/10.1007/978-3- 030 - 00668-6 17