The AgreementMaker system for ontology matching includes an extensible architecture that facilitates the integration and performance tuning of a variety of matching methods, an evaluation mechanism, which can make use of a reference matching or rely solely on \inherent" quality measures, and a multi-purpose user interface, which drives both the matching methods and the evaluation strategies. In this paper, we focus on two main features of AgreementMaker. The former is an optimized method that performs the selection of mappings given the similarities between entities computed by any matching algorithm, a threshold value, and the desired cardinalities of the mappings. Experiments show that our method is more e cient than the typically adopted combinatorial method. The latter is the evaluation framework, which includes three \inherent" quality measures that can be used both to evaluate matching methods when a reference matching is not available and to combine multiple matching results by de ning the weighting scheme of a fully automatic combination method.
The quest for correctness, completeness, and e ciency in the process of nding
correspondences (or mappings) between semantically related entities of di erent real-world
ontologies is a di cult and challenging task for several reasons. For example, an
algorithm may be e ective for a given scenario, but not for others. Even within the same
scenario, the use of di erent parameters can change the outcome signi cantly.
Therefore, state-of-the-art ontology matching systems [
Our collaboration with domain experts in the geospatial domain [
We describe next the main components of the paper. In Section 2, we cover related work. In Section 3, we describe several of the matching methods, or matchers, and their organization in layers. The ontologies being matched are called source and target ontologies. Matchers perform similarity computation in which each concept of the source ontology is compared with all the concepts of the target ontology, thus producing two similarity matrices (one for classes and one for properties), which contain a value for each pair of concepts.
In Section 4, we describe the process of mappings selection in which a similarity
matrix is scanned to select the best mappings according to a given threshold and to
the cardinality of the correspondences. For the mappings selection, we distinguish
the following four cases: 1-1, n-m, n- (analogous to -m), - , where 1, n, and m
indicate speci c input parameters and indicate that there is no constraint on the
number of relations. For example, 1-1 means that each concept in the source ontology
will be matched with at most one concept in the target ontology, n-m means that
each concept in the source ontology will be matched with at most m concepts in the
target ontology, whereas each concept in the target ontology will be matched with at
most n concepts in the source ontology. In the case n- , for example, each concept in
the source ontology can be matched to any number of concepts in the target ontology.
We note that in this case the chosen similarity threshold will in fact determine the
number of concepts in the target ontology. In order to maximize the overall similarity
of the selected mappings in a 1-1 or n-m matching, an optimization problem (namely
the Assignment Problem) has to be solved. We provide an e cient solution to this
problem by reducing it to the maximum weight matching in a bipartite graph and
by adopting the Shortest Augmenting Path algorithm (SAP) [
In Section 5, we describe the evaluation framework, which can make use of a
reference matching or rely solely on \inherent" quality measures. In particular, we have
adopted in our system two quality measures proposed by others [
There are several notable systems related to ours [
RiMOM [
Falcon-AO [
SAMBO and SAMBOdtf [
None of the above systems proposes quality measures. One approach in this
direction reduces mapping incoherence of the computed mappings to concept unsatis
ability in the ontology that results from merging matched ontologies [
Mapping incoherence is also used in the ILIADS system [
Other work proposes new measures that extend precision and recall to objects that
are semantically de ned, such as those in ontologies and alignments [
Our architecture allows for serial and parallel composition where, respectively, the output of one or more methods can be used as input to another one, or several methods can be used on the same input and then combined. A set of mappings may therefore be the result of a sequence of steps, called layers, to obtain a nal matching or alignment (i.e., a set of mappings).
First layer matchers compare concept features (e.g., label, comments,
annotations, and instances) and use a variety of methods including syntactic and lexical
comparison algorithms as well as the use of a lexicon like WordNet in the Base
Similarity Matcher (BSM) [
In several methods, the common information between two concepts is kept into separate features and compared within each feature: labels are compared with labels and concept descriptions are compared with concept descriptions, for example. For this reason, we adopt a Vector-based Multi-word Matcher (VMM) that treats concepts as virtual documents containing the information pertaining to them. This information includes their descriptions, the information about their neighbors, and extensional information (e.g., class instances). These containers of terms are transformed into TF-IDF vectors and the similarity is computed using the cosine similarity metric, which is a common technique used to compare documents (see Figure 3).
Second layer matchers use structural properties of the ontologies. Our own
methods include the Descendant's Similarity Inheritance (DSI) and the Sibling's Similarity
Contribution (SSC) [
Finally, third layer matchers combine the results of two or more matchers so as to obtain a unique nal matching in two steps. In the rst step, a similarity matrix is built for each pair of concepts, using our Linear Weighted Combination (LWC) matcher, which processes the weighted average for the di erent similarity results (see Figure 4). Weights can be assigned manually or automatically, the latter kind being determined using our evaluation methods (presented in Section 5). The second step uses that similarity matrix and takes into account a similarity value and the desired cardinality to generate the nal set of mappings, which maximizes the overall similarity while satisfying the selection constraints. 4
Four cases are considered in the selection process (see Section 1), depending on the desired cardinality: 1-1, n-m, n- (analogous to -m), and - . The solution to ncan be found by scanning each row in the similarity matrix (or each column in the case -m) and by selecting the n most similar correspondences with similarity values higher than the threshold (see Figure 5). For the - case, only the threshold constraint has to be satis ed.
The 1-1 matching case, which is often required in real-world scenarios, is a
challenging problem. In order to maximize the overall similarity in such scenarios, an
optimization problem (namely the Assignment Problem) has to be solved. Usually,
combinatorial algorithms (e.g., the Hungarian Method [
We provide an e cient alternative solution to this problem by reducing it to
the maximum weight matching in the bipartite graph G = (S [ T, E ), where S
contains the source ontology concepts, T contains the target ontology concepts, and
E contains an edge oriented from S to T for each correspondence with a similarity
value higher than the threshold, weighted with the threshold value itself. We recall
that a maximum weight matching M is a subset of the edges in E such that for
each vertex in G at most one adjacent edge is contained in M and the sum of the
weights (i.e., the similarity values) of the selected edges is maximized. Thanks to this
transformation, we can adopt the Shortest Augmenting Path algorithm (SAP) [
Finally, in the n-m selection case, we reuse our algorithm for the 1-1 matching case several times sequentially. We keep track of the number of mappings found for each vertex, and at the end of each iteration, we remove from the bipartite graph all the vertices together with their adjacent edges that have reached the maximal cardinality. The algorithm terminates when the graph is empty. We do not know of any other ontology matching system that has investigated the selection process with this level of detail. The most e ective evaluation technique compares the mappings found by the system between the two ontologies with a reference matching or \gold standard," which is a complete set of correct mappings as built by domain experts, in order to measure precision, recall, and F-measure. The AgreementMaker system supports this evaluation technique. In addition, a reference matching can also be used to tune algorithms by using a feedback mechanism provided by a succession of runs.
However, a gold standard is usually not available. Therefore, \inherent" quality
measures need to be considered. These measures can be de ned at two levels as
associated with the two main modules of a matcher: similarity or selection level. As
illustrated in Figure 5, we can consider local quality as associated with a single row
(or a single column) of the similarity matrix at the similarity level (or mapping at
the selection level) or global quality as associated with all the correspondences in the
similarity matrix at the similarity level (or with all the mappings in a matching at
the selection level). This categorization of quality measures is summarized in Table 1.
We have incorporated in our system two global-selection quality measures proposed
by others [
The intuition behind the two global-selection quality measures, namely (1) order and (2) distance preservation, is that given a set of mappings we can measure the structural properties of the produced matching to help determine its quality. In particular, according to (1), a matching should not change the order of concepts as de ned by the is-a or part-of relations, and, according to (2), it should preserve the distance between concepts as much as possible. These metrics are good measures of the quality of a set of mappings if the ontologies are structurally similar.
In contrast with the two global-selection measures, the local-similarity quality measure is independent of the properties of the ontologies. Indeed, it tries to measure the reliability of the similarity measures assigned by a matching method, which is an intrinsic property of the matching method and therefore scenario independent. In particular, for each source (or target) concept we want to measure the con dence of the matcher as related to the selected mappings for that concept. Similarity-based matching techniques are based on the idea that if two concepts are very similar, they probably deserve to be matched. Therefore, our measure should be directly proportional to the similarity values of selected mappings. At the same time, we want to detect and penalize those matchers that tend to assign high similarity values too generously. For instance, if the correct solution is a 1-1 matching we expect each concept to be very similar (i.e., have high similarity value) to one concept at most, and very di erent (i.e., have low similarity value) to all others. Moreover, we want the similarity assignments to be stable in respect to the threshold value, so that changing the threshold slightly should not a ect the nal alignment considerably.
Therefore, given a matcher M and a concept c, we can de ne the local con dence of M with respect to c, LCM (c), as follows: { let T be the set of all target concepts; { let mM(c) T be the set of concepts c0 2 T that have been mapped to c by M ; { let simM(c; c0) be the similarity value between c and c0 assigned by M ; { then LCM (c) is de ned as the di erence between the average of selected mappings' similarities for c and the average of the remaining correspondences' similarities:
LCM(c) =
X c0 2 mM(c)
simM(c; c0) j mM (c) j
X j T c0 2 (T mM(c))
simM(c; c0) mM (c) j : With the reasonable assumption that M maps the most similar concepts, then
X simM(c; c0) X simM(c; c0) c0 2 mM(c) 1 jmM (c)j LCM(c) 2 [0; 1] c0 2 (T mM(c)) jT mM (c)j 0 , therefore A simple application of this quality measure is shown in Figure 6. 6
In this section, we rst report on the e ciency tests of the mappings selection
algorithm. Then we compare the rst layer matchers proposed in this paper (i.e., PSM
and VMM) with the matching methods we used in the OAEI 2007 competition (i.e.,
BSM followed by DSI) [
Mappings selection The most relevant module in this component is the 1-1
matching algorithm, which is also used to solve the n-m matching case. We compare the
algorithm that we have adapted and implemented, the Maximum Weight Bipartite
Matching, MWBM, with the Hungarian method [
In the second experiment, we investigated the e ects of the threshold value on the performance of the algorithms. This time, we ran both methods on the same 2 The implementation is available at konstantinosnedas.com/dev/soft/munkres.htm. 1000 1000 matrix using di erent threshold values (varying from 10% to 90%). As shown in Figure 8, the Hungarian method is not a ected by the di erences in the threshold values while the performance of MWBM improves when the threshold increases. That is, combinatorial matching methods, such as the Hungarian method, process the whole similarity matrix including those values that do not satisfy the threshold constraint. Instead, our algorithm transforms the similarity matrix into a weighted bipartite graph whose size is directly a ected by the threshold value. Indeed, those correspondences that do not satisfy the threshold constraint are not translated into edges of the bipartite graph.
First layer matchers We ran the rst two experiments on the alignment of eight pairs of ontologies. In particular, each set contains a source ontology, a target ontology, and the reference matching (expected matching) between them. The following ontology pairs were provided by I3CON 2004:3 { weapons set (WEP) contains two classi cations of various weapon types; { people and pets set (PP), contains two ontologies describing people and pets; { networks set (NET) contains two classi cations of computer networks; { Russia set (RUS) contains general information about Russia.
The other four sets of ontologies are part of the OAEI benchmark.4 The domain of these ontologies is bibliographic references. We consider those test cases in which the reference ontology #101 has to be aligned with the following real-world ontologies: { #301 is the BibTex bibliographic ontology from MIT; { #302 is the BibTex bibliographic ontology from UMBC; { #303 is the Karlsruhe bibliographic ontology used in the OntoWeb portal; { #304 is the INRIA bibliographic ontology.
In the rst experiment, we ran the rst layer matchers on all sets of ontologies using multiple threshold values for all of them. In Figure 9, for each method and for each ontology set, we report on the best F-measure of all runs. PSM is usually more e ective than the others except for test cases #302 and #303, where it is slightly worse. However, the overall F-measure is de nitely the highest. We further investigated the result of this experiment and noticed that BSM followed by DSI is quite accurate (high precision) but is able to nd mappings only when the concepts are quite similar (otherwise displays low recall on dissimilar ontologies). Instead, PSM usually nds more mappings, even though some of them may be wrong occasionally. That is why it is less e ective than BSM on the #303 set which contains mainly trivial mappings. VMM is sometimes better than the combination BSM+DSI, but it is usually worse than PSM. The problem is that these ontologies do not provide enough information to allow for this matcher to be very e ective; however, it nds some non-trivial mappings not discovered by the other methods.
In summary, PSM is quite e ective and stable, BSM is important for his high accuracy and VMM is able to nd non-trivial mappings. Given the di erent qualities demonstrated by these matchers, we thought of combining them, thus motivating our next experiment.
LWC matcher We ran the rst layer matchers (BSM, PSM, and VMM) and combined their results with the LWC matcher using four di erent linear operations: average of similarities, LWC-avg, maximum similarity, LWC-max, minimum similarity, LWC-min, and quality-based weighted average of similarities, LWC-weight avg.
In the quality-based strategy, we adopted the local con dence quality to measure the relevance of the mappings generated by each matcher. In particular, the LWC method computes a combined similarity matrix that is obtained as the weighted average of the similarity matrices produced by the three matchers (see Figure 4). In this experiment, the weights are assigned by evaluating each matcher with the local condence quality measure. Being a local similarity level quality measure (see Table 1), it de nes a di erent value for each row of a similarity matrix, which is directly used to compute the weighted average for that row in the combination of the similarity matrices.
For each ontology set, we report in Figure 10 the best performance of the matchers to be combined, henceforth called input matchers, and the performance of the di erent versions of the LWC matcher. In most cases, almost all the mappings found by a single matcher are included in the set generated by another one, therefore any combination of these matchers cannot provide a signi cant improvement. A combined result equivalent to the best matcher in the input is already a good result. However, in all test cases, at least one of the combined results is equivalent to or better than the best result of the input matchers.
Considering the complexity of combining multiple matchings, which is still an open research problem, the most important result of this experiment is that the weighted average based on the local con dence quality is the most e ective technique. Moreover, we note that the weights are chosen automatically. 7
In this paper, we make a contribution to the automatic evaluation of matchings by de ning a quality measure that does not take into account the prior knowledge of a reference matching. We use this quality measure to de ne the weighting scheme of a fully automatic combination method. We also propose an e cient solution for the mappings selection task, whose performance is also positively a ected by the threshold value. We plan to provide an API to make this functionality available to other matching systems.
In the future, we will take advantage of our extensible architecture and add new matching methods, for example, to our instance based methods. We plan to study new quality measures to enhance the current evaluation capabilities and our qualitybased combination technique. Another direction for future research includes using partial reference matchings to perform the alignment of full ontologies.