Towards Multiple Ontology Merging with C oMerger

Abstract

To obtain a knowledge graph representing a domain of interest, it is often necessary to combine several, independently developed ontologies. Existing approaches are mostly limited to binary merge and lack scalability. This paper presents the development of an e cient multiple ontologies merging method, CoMerger. For e cient processing, rather than directly merging a large number of ontologies, we group related concepts across ontologies into partitions and merge first within and then across those partitions. Experiments on real-life datasets confirm the feasibility of our approach and demonstrate its superiority over binary strategies. Our implementation is available through a live web portal.

Keywords

• Ontology merging
• Partitioning
• N-ary merge

Introduction

Ontologies represent the semantic model of data on the web. For many usecases, individual ontologies cover just part of or one specific perspective on the domain of interest. By merging them into one knowledge graph their complementarity can be leveraged. The merge process plays an important role in multiple di erent aspects of the Semantic Web (cf. [ 1 ]). Most existing approaches [ 2, 3 ] are limited to merging two ontologies at a time, due to using a binary merge. Merging n > 2 ontologies in a single step using a so called n-ary strategy [ 4 ], has not been extensively studied so far, but seems to be promising to obtain better scalability. We aim to investigate to which extent this is the case.

Let us consider five source ontologies with their correspondences depicted by dashed lines (Fig. 1). To estimate the merge e ort, we measure combining the corresponding entities into an integrated entity jcombinej, reconstructing the relationship jreconstj, and output generation jout putj. In the binary-ladder strategy [ 4 ], a popular type of binary merge, first, O1 and O2 are combined into an O12. Then, O12 is merged with O3 and so on (see Fig. 1 and Table 1). The merged ontology obtained by an n-ary approach has the same structure as the final merged ontology of the binary-ladder merge for our example. The binary merge approach needs 10 combinations, 32 reconstructions, and 4 times output generation, while the n-ary method needs 6, 28, and 1, respectively. This means that for our example, the n-ary method reduces the e ort to 3 1 1 5 2 7 2 4 8 10 6 9 jcombinej jreconstj jout putj 60, 87,5, and 25% of the e ort needed with the binary method. The general pattern will be the same for other examples. The achieved improvements are significant compared to binary approaches, especially when dealing with a large number of ontologies.

To handle a large number of source ontologies, we aim to reduce the time and operational complexity while achieving at least the same quality of the final result compared to the binary merge or even improve upon it. In our n-ary method, CoMerger1, we develop an e cient merging technique that scales to many ontologies. It takes as input a set of source ontologies OS = fO1; :::; Ong with a set of corresponding sets CS extracted from their mappings and generates a merged ontology OM. At first, the n source ontologies are partitioned into k blocks (k << n). After that, the blocks are individually refined and finally combined to produce the merged ontology followed by a global refinement. 2

Proposed Method

Our method implemented in CoMerger consists of three main phases: initialization, partitioning, and combining. Mappings between source ontologies can be given or can be created with a matching tool [ 5 ] embedded in CoMerger in a preprocessing step. These mappings consists of sets of corresponding entities. The relationship determining correspondence can be equality, similarity, or subset (is-a) types. In CoMerger, we consider the similarity type with at least a given similarity value (1:1 mapping). We maintain a model M which keeps the information across a group of correspondences over multiple ontologies. We denote the cardinality of each corresponding set by Card(cs j), where cs j 2 CS.

(1) Initialization Phase. We build an initial merge model IM and parse the source ontologies by extracting all entities into the IM. After that, the list of corresponding 1 The tool as well as all data used for evaluation are available online at

http://comerger.uni-jena.de and https://github.com/fusion-jena/CoMerger sets CS from the given mappings are processed to build the model of mappings M over multiple ontologies. For each entry of M, a new integrated entity in IM is created. To construct the initial relations between the entities in IM, all axioms from the source ontologies should be processed. Thus, we translate the source ontologies’ axioms concerning the corresponding sets that exist in M. If an axiom’s entities have a corresponding entity in M, the axiom is translated with the generated integrated entity; if not, the axiom is imported into IM without any changes.

(2) Partitioning Phase. An ontology block L is a subset (or whole) of one (or more) source ontologies with no overlap with other blocks. The number of blocks is denoted by k and CL = fL1; :::; Lkg is the set of all blocks. We decompose the ontologies merging task Merge(O1; :::; On) to the blocks merging task Merge(L1; :::; Lk), k << n. To achieve this, we use a set of pivot P classes:

(i) Finding pivot classes P. To find the pivot set of classes P for the divide process, we measure a reputation degree of each class belonging to CS, as reputation(ct) = Card(ct) Conn(ct). It is based on the number of corresponding classes Card(ct) along with their connectivity degree Conn(ct) from the respective source ontologies. The classes with high Card(ct) values in CS have the best overlap within OS . However, contemplating only this metric tends to choose isolated classes as the pivot classes. Thus, class connectivity has been taken into account. The connectivity degree Conn(ct) of a class is indicated by the number of associated taxonomic and non-taxonomic relations for that class. Thus, P is realized by a sorted list of CS’s elements based on their reputation degrees.

(ii) Partitioner. This step divides all classes from IM into a set of blocks CL = fL1; :::; Lkg based on a structural-based similarity, in which classes close in the hierarchy are considered similar and should be placed in the same block. Thus, once a class is assigned to a block, all its adjacent classes consequently will also be added. The first block L1 is created by picking the first P’s element, which has the highest reputation degree. For each corresponding class of P’s element, all classes with their adjacent classes on their respective ontologies are added to the block. Then, the next element of P is selected to create a new block, if at least one of its classes has not been assigned to the previous blocks. This process is continued until all elements of P are processed. The overall number of blocks is determined based on the number of P’s elements and the amount of shared classes between P’s elements.

(3) Combining Phase. This phase is split into two steps. In the intra-combination step, the entities inside the blocks are combined to create local sub-ontologies. We retrieve all existing axioms from IM. Each class is augmented by the original or translated properties axioms, including taxonomic and non-taxonomic relations. We assign each axiom to a block in which at least all its entities are contained. If the classes of each axiom are distributed across multiple blocks, they are not added to any block and are marked as distributed axioms distaxiom. Finally, the local refinement process takes place for each sub-ontology. To further improve performance, this step can utilize parallel processing. In the inter-combination step, the final merged ontology OM is constructed. We follow a sequential merging based on the inter-block relatedness, jdistaxiom(Li) \ distaxiom(L j)j. It is based on the number of shared distributed axioms between two blocks Li and L j. At first, the two blocks with the highest inter-block similarity value are merged. This includes adding all distributed axioms to them. Then, the next block with the highest inter-block relatedness will be selected to be merged. This process is continued until all blocks are merged. A set of global refinement will be applied on the last combined block. Upon that, the merged ontology OM is built. To apply local and global refinement within CoMerger, we include a list of General Merge Requirements (GMR)s [ 6 ], containing, e.g., entities preservation, one type restriction, acyclicity, and connectivity. 3

Experimental Evaluation

We have selected sets of ontologies frequently used for evaluation tasks (see our repository), with 134 jaxiomsj 30364 and 2 n 55 and have created mappings with SeeCOnt [ 5 ]. To demonstrate the feasibility of our n-ary strategy, we compared it with binary ladder and balanced strategies [ 4 ]. The runtime performance (in seconds) for each merge strategy is shown in the third row (time) of Table 2. The n-ary merge is on average 4 (9) times faster than the balance (ladder) binary merge, respectively. Moreover, we present the operation complexity of these three strategies in Table 2. In each test of a binary merge, only the correspondence between two entities can be integrated simultaneously into a new entity. However, in n-ary merge, the corresponding entities from multiple source ontologies can be integrated into the new entities. Thus, the number of total corresponding entities jCorj in the binary merge is much higher than in the n-ary approach. Consequently, the required amount of combining them into new entities and translating their axioms jtrj is high. For global refinement, in most cases, the n-ary approach requires less actions compared to binary merges. We also compare the number of merge processes jMer:j. While the n-ary approach only uses one iteration, ladder and balance methods require n 1 merge processes. Overall the result demonstrates that the n-ary approach has better (runtime and complexity) performance than binary approaches. In terms of quality, the n-ary approach achieves comparable results to its binary counterparts (see full result in our repository). 4

State of the Art

Merging strategies have been divided into two main categories [ 4 ]: “binary” and “n-ary”. The binary approach allows the merging of two ontologies at a time, while the n-ary strategy merges n ontologies (n > 2) in a single step. Most methodologies in the literature, such as [ 2, 3 ] agree on adopting a binary strategy. The few existing n-ary approaches [ 7, 8 ] su er certain drawbacks: In [ 8 ], the final merge result depends on the order in which the source tree-structured XML schemas are matched and merged. In [ 7 ], the experimental tests were carried out on a few small source ontologies, only. Despite the e orts of these research studies, developing an e cient, scalable n-ary method has not been practically applied. 5

Conclusion

Existing ontology merge approaches scale rather poorly to the merging of multiple ontologies. We proposed the n-ary multiple ontologies merging approach CoMerger based on a partitioning based method, to overcome this issue. Taking advantage of the parallelization is on our future research agenda.

Acknowledgments

S. Babalou is supported by a scholarship from German Academic Exchange Service (DAAD).

References

1. M. T. Finke , R. W. Filice , and C. E. Kahn Jr , “ Integrating ontologies of human diseases, phenotypes , and radiological diagnosis,” J AM MED INFORM ASSN , vol. 26 , no. 2 , pp. 149 - 154 , 2019 .

2. M. Priya and C. A. Kumar , “ An approach to merge domain ontologies using granular computing , ” Granular Computing , pp. 1 - 26 , 2019 .

3. S. Raunich and E. Rahm, “ Target-driven merging of taxonomies with ATOM,” Inf . Syst., vol. 42 , pp. 1 - 14 , 2014 .

4. C. Batini , M. Lenzerini , and S. B. Navathe , “ A comparative analysis of methodologies for database schema integration ,” In CSUR , 1986 .

5. A. Algergawy , S. Babalou , M. J. Kargar , and S. H. Davarpanah , “ SeeCOnt: A new seeding-based clustering approach for ontology matching ,” in ADBIS, 2015 .

6. S. Babalou and B. Ko¨ nig-Ries, “ GMRs: Reconciliation of generic merge requirements in ontology integration,” In SEMANTICS Poster and Demo ., 2019 .

7. N. Maiz , M. Fahad , O. Boussaid , and F. Bentayeb , “ Automatic ontology merging by hierarchical clustering and inference mechanisms,” in I-KNOW , pp. 1 - 3 , 2010 .

8. K. Saleem , Z. Bellahsene , and E. Hunt, “Porsche: Performance oriented schema mediation,” Inf . Syst., vol. 33 , no. 7 , pp. 637 - 657 , 2008 .