Among the variety of alignment approaches (e.g., using machine learning, subsumption computation, formal concept analysis, etc.) similarity-based ones rely on a quantitative assessment of pair-wise likeness between entities. Our own alignment tool, OLA, features a similarity model rooted in principles such as: completeness on the ontology language features, weighting of different feature contributions and mutual influence between related ontology entities. The resulting similarities are recursively defined hence their values are calculated by a step-wise, fixed-point-bound approximation process. For the OAEI 2005 contest, OLA was provided with an additional mechanism for weight determination that increases the autonomy of the system.
vironment for alignment manipulation. Indeed, in its current version, the system offers, via its GUI component VisOn, the following services: • parsing and visualization of OWL-Lite and OWL
DL ontologies, • computation of similarities between entities from two ontologies, • extraction of alignments from a pair of ontologies, provided with a set of similarity matrices, one per category of ontology entities (see below), • manual construction of alignments by composing entity pairs from two ontologies, • use of an existing (partial) alignment as a seed for automated alignment construction (alignment completion), • alignment visualization, • comparison of two alignments.
In the remainder, the focus will be limited to the automated alignment construction with OLA.
The following fundamental principles underly the design of the three key mechanisms in OLA, internal representation of the ontology, similarity computation and alignment extraction, that are involved in the global ontology alignment process: All-encompassing comparison : We tend to believe that all the available knowledge about a pair of ontology entities should be taken into account when aligning. This does not exclude the possibility of ignoring particular aspects, i.g., OWL instances in case of OWL class comparison. However such a choice should be deliberately made by the tool user, here through appropriate weight assignment, or, if performed by an automated mechanisms, should reflect some particularity, either of the entire ontology (e.g., global absence of instances in both ontologies) or of the pair of entities at hand (e.g., local absence of instances in the pair of classes to be compared).
Highest automation level : Although we recognize that the entire alignment process often needs to be set on a semi-automated basis, we nevertheless argue in favor of a completely automated process for ”draft” alignment generation. Thus, we see the OLA user providing a minimal set of parameters at the initial steps of the process whereas the tool will suggest one or more candidate alignments at the end, without any other human intervention. Category-dependent comparison : Following the syntactic structure of the OWL language, entities are divided into categories, e.g., classes, objects, properties, relations, and only entities of the same category are compared. Moreover, the entities of a category are compared using similarity functions of the same basic shape. The respective category functions comprise the same factors and the same weights. They are further customized for each pair of category entities by projecting them over the actual feature space of the entities (which may be far smaller than the complete space of the category). Comparability of similarity results : To enable comparison of similarity scores between different alignment tasks but also for some computational reasons, a set of useful properties is insured for the similarity functions: normalization, positiveness, maximalness2, and symmetry 3. 1.1.3 Current limitations • Although it would be of certain value for alignment, OLA currently offers no inference mechanisms that could help complete the entity descriptions. In particular, inheritance is not used to expand entities, mostly out of efficiency considerations. • Although neighborhoods play crucial role in the similarity definition, two neighbor entities are not necessarily affecting each other’s respective similarities to a pair of other entities. As only descriptive knowledge is taken into account, given two such entities, say e1 and e2, for e2 to appear in a similarity expression for e1, it should be considered as part of the description of the latter. For instance, a data type is not seen as being described by a property whose range the datatype represents. Consequently, datatypes are compared in an ontology-independent manner. • Category borders are not similarity-permeable: Only entities from the same category are compared for similarity and hence for alignment. 1.2
2With normalization, this amounts to forcing scores of 1 for identical entities within identical ontologies 3The price to pay for symmetry is the impossibility of detecting subsumption by this purely numerical procedure. OLA features an alignment process that splits into three basic steps: constructing the intermediate representation of the compared ontologies as labeled graphs, computing the similarity of each pair of same-category entities from the respective ontology graphs, extracting an alignment from the similarity matrices for each category.
OL-Graphs are graph structures that provide an
easyto-process inner representation of OWL ontologies. An
OL-Graph is a labeled graph where vertices correspond
to OWL entities and edges to inter-entity relationships.
As described in [
The OL-Graph model allows the following relationships among entities to be expressed: • specialization between classes or relations (denoted
S),
• instanciation (denoted I) between objects and classes,
property instances and properties, values and datatypes,
• attribution (denoted A) between classes and
properties, objects and property instances;
• restriction (denoted R) expressing the restriction
on a property in a class,
• valuation (denoted U ) of a property in an object.
The OL-Graph of an ontology is built after the ontology
is parsed4. The process of OL-Graph construction is
described in [
The similarity functions used in OLA are designed in
a category-specific manner and cover all the available
descriptive knowledge about an entity pair. Thus, given
a category X of OL-Graph nodes, the similarity of two
nodes from X depends on:
• the similarities of the terms used to designate them,
i.e., URIs, labels, names, etc.,
• the similarity of the pairs of neighbor nodes in the
respective OL-Graphs that are linked by edges
expressing the same relationships (e.g., class node
similarity depends on similarity of superclasses, of
property restrictions and of member objects),
• the similarity of other local descriptive features
depending on the specific category (e.g., cardinality
intervals, property types)
4So far, we use the OWL API [
Datatype and datavalue similarities are external to our model and therefore they are either user-provided or measured by a standard function (e.g., string identity of values and datatype names/URIs).
Formally, given a category X together with the set of
relationships it is involved in, N (X), the similarity
measure SimX : X2 → [
πFX M SimY (F (x), F (x0)).
X
F∈N (X)
The function is normalized, i.e., the weights πX sum to
a unit, PF∈N (X) πFX = 1. for the computabFility The
set functions M SimY compare two sets of nodes of the
same category (see [
Following the lessons learned with our participation in
the EON 2004 alignment contest [?], we have adapted
the above measure to fit cases where particular pair
of entities is described only by a small subset of the
entire set of category descriptors. Thus, a descriptive
factor is ignored for similarity computation whenever
neither of the compared entities possesses a neighbor
with the underlying link label (e.g., no instances for a
pair of compared classes). In this case, not only its
weight is set to 0, but also the weights of the remaining
”active” factors are increased correspondingly. To scale
that principle up to the entire set of descriptive factors,
the following simple mechanism has been realized in
OLA: In order to keep both normalization and equity
in similarity values, the weights of all non-null factors
for a given entity pair are divided through their sum.
Thus, for a category X, the similarity measure Sim+X :
X2 → [
Sim+X (x, x0) = P
SimX (x, x0) F∈N +(x,x0) πF where N +(x, x0) is the set of all relationships F for which F (x) ∪ F (x0) 6= ∅ 5.
OLA relies on various functions for identifiers
comparison. Both string distances and lexical distances are
used. Lexical distances rely on an exploration of
WordNet 2.0 [
OLA is implemented in Java. Its architecture follows
the one of the Alignment API and the recent
implementation that was described in [
Along the preparation of the AOEI 2005 contest, a row of changes have been made to the system in order to make it fit the complexity of the alignment discovery task. The most striking one is the introduction of a weight-computing mechanism that eliminates the necessity for the tool user to provide initial weights and hence makes a significant step towards full automation of the alignment process. 5That is, there exists at least one y such that (x, y) ∈ F or at least one y0 such that (x0, y0) ∈ F .
As it is far from obvious for novice users how to weigh the different similarity factors, we initiated work on incorporating a weight computing mechanism within the system. The intended mechanism is both intuitive and effective so that alignment practitioners with various skill levels could find a match for their knowledge and experience. So far, we used a simple heuristic method that, according to the obtained results, performs reasonably well. The basic idea of the method consists in distributing the weights among similarity factors in the generic similarity function of a node category according to the relative importance of the corresponding category in the entire ontology. That is to say we use the average number of links of the corresponding type per entity of the category at hand. For instance, the greater the number of super-class links in the ontology, the higher the weight of the super-class factor in the class similarity formula.
OLA uses two alternative modes of comparison for entity names (URIs, labels, etc.): a string measure6 (a default) and a lexical similarity measure that relies on WordNet 2.0 (see above).
The highly sophisticated lexical similarity measure that was used in OLA for the EON competition has been replaced by a simpler but more purposeful one. Indeed, the initial function compared multi-word terms on three separate axes: nouns, verbs and adjectives, as provided by WordNet 2,0. Such comparison seemed appropriate for cases where the meanings of a word fall in more than one part-of-speech category. The inter-word similarities on each axis were aggregated by an independent best-match computations while the three resulting values were further combined to a single one via a weighted sum.
The new measure trades separate matchings on speechpart-wise basis to a single global matching along entry similarities that aggregate all three possible aspects of a word. Thus, the words are compared to each other with all possible meanings and the highest similarity over a single pair of meanings is taken for the words. For the OAEI competition, as we had to rely on a fixed parameter set for the entire collection of tests, we have chosen to force the use of the string distance. Indeed, it showed better performances while being much more efficient than the WordNet-based computation. Nevertheless, the improved lexical similarity was not completely discarded: it is currently used as a preprocessing tool that helps decide automatically the distribution of weights among similarity factors. 6subString distance provided by the Alignment API
Following experiences from EON 2004, a set of simple but decisive modifications have been applied in order to prevent the precision leak in the tests. First, the instances have been excluded from the alignments by default, although the possibility is given to the user to reverse this choice. Then, entities external to the ontologies at hand have also been excluded from the alignment (but not from the similarity computation). Finally, one-to-one alignment production has been enforced in OLA to increase the potential recall of the resulting alignment.
The comments are grouped by test categories. 2.101 Tests 10X OLA performed very well on the tests of this group. This seems to be due to the fact that while the language varies along the individual tests of the group, the basic ontology entities involved in the similarity computation remain unchanged with respect to the reference ontology. 2.102 Tests 2XX The performances of the algorithm seem to suggest that three sub-groups of tests can be distinguished. The first one comprises the tests 21X, 22X, 23X and 24X, with a small number of exceptions where the performance have been: • Quite good: This is the case of tests 201, 202, with random class names. The random names were putting a strain on the ability of the algorithm to propagate similarity along the network of node pairs. Obviously, our technique needs some improvements on that point. • Satisfactory: In the case of tests 248, 249, there is a combination of missing (or random) names with one other missing factor. For tests 248, 249, the missing factors are hierarchy (sub-class links) and instances, respectively. Both play important role in similarity computation of classes, whenever these are stripped of their names as is the case with these two ontologies. Hence the sharp drop in precision and recall with respect to the preceding tests. • Weak: The notorious failure here have been the tests 205, 209, which are the only ones to use of synonymous names in the ontology entities (with respect to the intial ontology). As WordNet has been plugged-out of the similarity computation, these results are not surprising.
The second groups is made of the tests 25X. Here OLA performances varied substantially: from extremely poor (254) to satisfactory (252, 259).
The last five ontologies of the group, the 26X ones, have proven to represent a serious obstacle for OLA. The performances of the system here were poor to very poor. 2.103 Tests 30X The real-world ontologies of the group 30X made OLA perform in an unimpressive way. We believe that this is due to the fact that string similarity was systematically used as identifier comparison means. Indeed, tentative runs with WordNet as basis for name similarity yielded way more precise alignments on that group. Unfortunately, they also brought down the overall statistics from the entire test set such as mean precision and mean recall. Hence the choice of the WordNet-based lexical similarity for a default name comparison means has been dropped.
The results show a substantial progress has been made since the EON 2004 alignment contest. With respect to the performances of OLA at that forum, we made a big leap amounting to about 25% in both mean precision and mean recall.
Nevertheless, we see that a vast space for improvement lays ahead of our project. The weaknesses of the current similarity mechanisms can be summarized as follows. First, the tuning of the algorithm is still a rigid process. Indeed, while the weights can now be computed following a specific footprint of the ontology, a mechanism for the choice of a particular name similarity on the same basis has yet to be defined.
Second, although we take into account the biggest possible amount of knowledge about entities, there are sources of similarity that have been ignored so far, in particular entity comments.
Besides expanding the lexical processing to comments in entities and providing a flexible decision mechanism for the choice of the default name similarity, a possible improvement of the system will be the integration of a learning module for weight estimation. As for similarity, the biggest challenge here is to define the representation of the input data, i.e., the descriptors of the entries for the learning algorithm.
Another research track would be the definition of an optimal matching algorithm. In fact, the current procedures are sub-optimal in the sense that they only chose local optima for each aligned entity. Consequently, as strict 1:1 matchings are to be produced, a single bad choice could easily generate a chain of wrong alignment decisions and thus negatively impact the performances of the tool.
Two months during summer period is definitely too short to run shuch an experiment.
In its latest version, OLA has proven a more robust tool for alignment than it was a year before. While the difficulties with real-world ontologies persist, the progress on noisy ones has been substantial. The next key topic of the research around OLA will be the automation of the weight computation for a specific pair of ontologies. 5.
A .zip archive of all the contest results is available at the following URL: http://www.iro.umontreal.ca/∼owlola/OAEI.html
A similar archive with the parameters and the .jar files used in the contest-related experiments is available at the following URL: http://www.iro.umontreal.ca/∼owlola/OAEI.html 5.3
Matrix of results
No names & no comments No comments Naming conventions Synonyms Translation
No restrictions No properties Flattened classes
Rec.