Ontology Alignment (OA) is the process of determining the mappings between two ontologies. A number of systems currently exists and many of them are participating in the annual Ontology Alignment Evaluation Initiative (OAEI).3
Ontology alignment for two very large ontologies becomes time consuming and memory intensive. For example, the largebio track in the OAEI campaign still poses serious challenges to participants and only 4 out of 11 systems managed to complete the largest largebio task. A general approach to address these challenges is to partition each ontology into cohesive blocks. The matching task is then divided into smaller tasks involving only relevant pair of blocks (i.e., partitions). Ontology partitioning brings new challenges: how best to partition each ontology into blocks and whether the partitioning process on each ontology should be independent of each other. Three main strategies exist: (i) totally independent partitioning of both ontologies using various clustering algorithms, (ii) independent partitioning of the better structured ontology and then use its partitioning to direct the partitioning of the other, and (iii) dependent partitioning between the two using a quick and efficient initial mapping of the two and then this mapping directs their partitioning.
A preliminary study of these three partitioning strategies and their effects on
ontology alignment is presented. The objective of this preliminary work is to determine the
suitability of these strategies to improve the performance of OA systems when dealing
with large ontologies, especially those unable to cope with the largest tasks.
Partitioning strategies in [
Once the anchor pairs are found, a block similarity between each pair of blocks,
one from the source and one from the target, is determined using Dice’s coefficient
calculated as the ratio of the intersection of the anchor pairs between the two blocks bs
and bt over the sum of the total number of anchors in bs and the total number of anchors
in bt. A user-settable similarity threshold in [
For dependent partitioning with PAP (partition, anchor, partition) and APP (anchor,
partition, partition) [
For PAP, the first two steps are identical to that of PBM: (i) independently partition the more structured ontology OT , and (ii) find anchor pairs between OS and OT .The less structured ontology OS is then partitioned using the blocks bTi built for OT in step (i), and the anchor pairs (aT ; aS ) identified in step (ii). Centers CBSi for a prospective block bSi in OS are determined from the anchor pairs existing for bTi . For each aT , its corresponding aS becomes a center CBSi for a prospective matching block bSi . A future block bSi may have multiple centers since multiple anchor pairs may be associated with block bTi . The centers CBSi are used to initialize the PBM algorithm for partitioning instead of its simply using each concept in OS as an individual block. These centers are given the highest cohesiveness value to begin growing the blocks from these centers. A final block bSi built from a center is matched with the corresponding block bTi . Not handled by PAP are blocks in OT and in OS that have no anchors in them. These blocks are simply ignored and not considered in the mathcing.
The APP method first finds anchors between OS and OT . It uses them to partition
OT by favoring the fusion of blocks sharing anchors with OS . It then partitions OS by
favoring the fusion of blocks sharing anchors with the blocks in the partitioned OT . The
blocks of OT are generated using PBM but with a modified measure that incorporates
not only the strength of the link between blocks bTi and bTj within OT but also the
strength of the link of BTj to OS as measured by the number of anchors in BTj relative
to the total number of anchors between OT and OS . The blocks of OS are generated by
PBM but with another modified measure that uses both the strength of the link between
the blocks bSi and bSj within OS and the strength of the link of bSj to bTk which is the
block in OT having the highest number of anchors with block bSi . Blocks of OS and
OT sharing the highest number of anchors become a matched block pair. One block of
OS can be matched with only one block of OT . Then alignment between the concepts
in each matched block pair is performed.
The PBM, PAP and APP partitioning methods have been implemented as independent
methods from the alignment system. In the preliminary experiments included in this
paper we report results for the systems LogMap [
The initial experiments were performed on task 1 of the OAEI largebio track,4 involving small fragments of FMA and NCI, using all three methods. The results using Wu-Palmer are shown below in Table 1 and those for Lin in Table 2. The parameters used are an of 0.05 for PBM, an of 0.75 for APP. A maximum block size of 500 and a depth difference of one for semantic similarity calculation is used for all three methods. Blocks with only one concept are considered isolated blocks. Coverage represents how many of the entities occurring in the OAEI reference alignments are present in the identified block pairs. The precision and recall are calculated over the combined alignment results for all the matching tasks (i.e., pair of modules extracted from the block pairs). FMA blocks (resp. NCI blocks) represents the number of total blocks produced after partitioning of the FMA ontology (resp. NCI ontology).
The results from task 1 suggest that the PBM method provides much higher recall values than the other two methods. The Wu-Palmer measure performed slightly better than Lin. The next experiments examined how the PBM with the Wu-Palmer performed on the OAEI largebio tasks that use the whole ontologies, that is, task 2, task 4 and task 6. The maximum block size is 3000. Table 3 presents these results.
4
In this paper we have presented a preliminary evaluation of state of the art partitioning algorithms for ontology alignment. The obtained results are not good as expected since, after the partitioning and identification of the (sub)matching tasks, the coverage of the entities in the reference alignments is rather low. For example, in the FMA-SNOMED case only 59% of the entities appearing in the reference alignment are covered by the modules in the identified matching tasks. In this case 41% of the entities were lost in either isolated blocks or blocks for which a suitable pair could not be found.
As expected, given the coverage of entities in the reference alignment, the results
obtained by LogMap are very low as compared to the results reported for LogMap in last
OAEI campaign [
In the close future we aim at investigating new algorithms to provide a suitable partitioning for ontology alignment where the loss of coverage in the identified (sub)matching tasks, in terms of entities of the reference alignments, is minimized. We also intend to perform an extensive evaluation of the novel partitioning algorithms with all OAEI participating systems, especially those failing to cope with the largest tasks.