The performance of alignment systems on property matching lags signi cantly behind that on class and instance matching. This work seeks to understand the reasons for this and consider possible avenues for improvement. The paper contains an in-depth exploration of the performance of current alignment systems on the only commonly accepted alignment benchmark that involves matches between properties. A second benchmark involving properties is also proposed. Finally, an entirely string-based approach targeted towards aligning properties is presented and evaluated using both benchmarks.
properties as well as classes. Table 1 shows the results of the top 2013 OAEI competitors on the Conference track, broken down into classes and properties1. The average f-measure for classes is more than three times that for properties.
Table 2 presents the most common correct and incorrect property matches identi ed by the participants in the 2013 OAEI, along with the valid property matches that were most frequently omitted by those systems. The frequency column in the table indicates the number of alignment systems out of the 15 qualifying2 systems that produced (or failed to produce, in the case of false negatives) each match. The rst section of the table shows that the equivalent properties that were most frequently correctly identi ed all have very high string similarity. Unfortunately, the second section shows that high string similarity is also the de ning characteristic of the most common false positives. It may seem surprising that some of the matches in this section of the table are not valid. In some cases the domain or range of the matched properties indicate that they are not being used in the same way. For instance, the domain of cmt:name is the union of Person and Conference whereas the domain of sigkdd:Name is only Person and a separate property, Name of conference, is used to represent a conference's name. In other cases the match may make sense in isolation but would lead to logical inconsistency of the merged ontology. Finally, we see in the last section of the table that the properties involved in the most common false negatives generally have a much lower string similarity, such as cmt:hasBeenAssigned and ekaw:ReviewerOfPaper. In many of these cases, the domain and range of the properties do have strong syntactic similarity however, e.g. Reviewer and Paper for hasBeenAssigned and Possible Reviewer and Paper for reviewerOfPaper. Further, there were some quite frequently missed equivalent properties that have
strong clues in the labels themselves, such as cmt:writePaper and confOf:writes. Of the 31 common false negatives, 13 have noticeable string similarity. 3
In addition to the OAEI Conference test set, we would also like to analyze the performance of alignment systems on properties from another real-world alignment task. For this we have chosen DBPedia3 and YAGO.4 DBPedia is a linked data version of the information in Wikipedia. The YAGO knowledge base has been automatically extracted from Wikipedia, WordNet, and GeoNames by researchers at the Max Planck Institute for Computer Science. Both DBPedia and YAGO contain millions of instances and thousands of schema-level entities. This scale is too large for many current alignment systems. We are speci cally interested in aligning the properties of these two datasets, so we have extracted a cohesive subset of each one that will allow us to do this without requiring an inordinately long runtime. This was done using the following procedure: 1. For each property in YAGO, randomly choose ve facts that involve the property. For properties with less than ve facts, use all that are available. 2. Add the classes (type) of every instance mentioned in the facts from step 1. 3. Randomly add up to ve other facts related to the instances from step 1. 4. Repeat step 2 for any additional instances added during step 3. 5. Compute the \closure" of this set of entities by recursively retrieving all schema-related axioms related to any entity within our sample.
The procedure for creating the DBPedia sample was analogous, except that instead of randomly choosing the facts in step 1, we selected facts with the same instances as our YAGO sample when available. This is possible because, since DBPedia and YAGO both represent information from Wikipedia, there is errorfree mapping of instances that point to the same Wikipedia page. When there were no matching YAGO instances for the facts related to a particular DBPedia property, we reverted to randomly choosing facts. The characteristics of these dataset samples are shown in Table 3.
This dataset sample may be of use to other researchers, so we have made it publicly available at http://www.michellecheatham.com/ les/dbpedia-yago.zip. It should be noted that DBPedia and YAGO have some idiosyncrasies. For instance, many properties de ned in the ontologies are never used or are incompletely de ned (e.g. missing domain or range de nitions). Also, the de nitions of some properties are spread across a datatype property, which speci es the range, and an annotation property, which speci es the domain. Furthermore, some of the properties appear to be used inconsistently, or at least more broadly than they are de ned. For instance, in DBPedia we see that the instance HAL 9000
4 http://www.mpi-inf.mpg.de/departments/databases-and-informationsystems/research/yago-naga/
Type Property 1 Property 2 Freq. Correct cmt:email confOf:hasEmail 11 confOf:hasFirstName edas:hasFirstName 11 conference:has an email confOf:hasEmail 9 cmt:email conference:has an email 9 conference:has the last name edas:hasLastName 9 conference:has a review ekaw:hasReview 9 conference:has the rst name edas:hasFirstName 9 conference:has the rst name confOf:hasFirstName 9 False Positive iasted:pay sigkdd:pay 9 confOf:hasEmail edas:hasEmail 9 cmt:email edas:hasEmail 8 cmt:name sigkdd:Name 8 confOf:hasPhone edas:hasPhone 8 confOf:hasStreet edas:hasStreet 7 confOf:hasPostalCode edas:hasPostalCode 7 iasted:obtain sigkdd:obtain 7 confOf:hasTopic edas:hasTopic 7 conference:has an email edas:hasEmail 7 cmt:writtenBy confOf:writtenBy 7 False Negative cmt:hasBeenAssigned ekaw:reviewerOfPaper 15 cmt:assignExternalReviewer conference:invites co-reviewers 15 cmt:assignedByReviewer conference:invited by 15 edas:endDate sigkdd:End of conference 15 conference:is given by sigkdd:presentationed by 15 conference:has a...tutorial topic confOf:hasTopic 15 conference:contributes iasted:write 15 cmt:hasBeenAssigned confOf:reviewes 15 conference:gives presentations sigkdd:presentation 15 conference:has the last name confOf:hasSurname 15 cmt:assignedTo ekaw:hasReviewer 15 confOf:reviewes edas:isReviewing 15 confOf:hasSurname edas:hasLastName 15 conference:has a review expertise edas:hasRating 15 cmt:writtenBy ekaw:reviewWrittenBy 15 cmt:hasSubjectArea confOf:dealsWith 14 cmt:writePaper confOf:writes 14 edas:isReviewedBy ekaw:hasReviewer 14 cmt:hasAuthor confOf:writtenBy 14 confOf:writes edas:hasRelatedPaper 14 edas:hasCostAmount sigkdd:Price 14 cmt:assignedTo edas:isReviewedBy 14 edas:startDate sigkdd:Start of conference 14 cmt:hasConferenceMember edas:hasMember 14 cmt:hasBeenAssigned edas:isReviewing 14 edas:hasLocation ekaw:heldIn 14 edas:hasName sigkdd:Name of conference 14 edas:isReviewing ekaw:reviewerOfPaper 14 confOf:hasEmail sigkdd:E-mail 13 conference:has an email sigkdd:E-mail 13 conference:contributes ekaw:authorOf 13 Table 2. Most common correct, false positive, and false negative property matches identi ed by alignment systems in the 2013 OAEI has a gender property with a value of male and that Eaglet (Alice's Adventures in Wonderland) has a gender value female. In some cases the gender property is used di erently, however: the instance Alexander has a gender property value of Alexandra, and the value for Maine North High School is mixed-sex education. While these issues can be a pain to work with, they are realistic concerns that ontology alignment systems will need to face for many application scenarios.
There is currently no curated alignment of the properties in the DBPedia and
YAGO datasets. We would like to use the crowdsourcing approach described in
Section 4 based on Amazon's Mechanical Turk system to create a complete
reference alignment for the properties in these two datasets. It is not realistic to
crowdsource opinion on all possible pairs of properties, however. A set of
potential mappings is needed to bootstrap the crowdsourcing e ort. Unfortunately, not
many alignment systems have made results available for this pair of ontologies.
The developers of the PARIS alignment system are the exception { they have
produced and made public a set of subsumption relationships between
properties [
In this section we present an entirely string-based approach to property alignment, which we will call PropString.5
Four strings are extracted for each property: the label, the core concept,
the domain, and the range. The label is simply the entity's label. The core
5 http://michellecheatham.com/ les/PropString.zip
concept is either the rst verb in the label that is greater than four characters
long or, if there is no such verb, the rst noun in the label, together with any
adjectives that modify that noun. For example, the label \wrote paper" has
the core concept \wrote" and the label \has corresponding author" has the
core concept \corresponding author." We arrived at this technique through an
analysis of common naming patterns for properties. We used the Standford
loglinear part of speech tagger to compute the core concept [
While the vast majority of alignment systems use a string similarity metric, they use them in di erent ways. One approach is to nd highly precise \anchor" matches which serve as the seed that the rest of the alignment grows out from. Another approach is to use a string metric to lter out any obviously incorrect matches in order to reduce computational complexity. This requires a string metric with high recall. To address both of these use cases, the PropString approach can be run in two con gurations: precision-oriented and recall-oriented. In the precision-oriented mode, a pair of entities is considered a match if the similarity values for their core concepts, domains, and ranges are all greater than the threshold. In the recall-oriented mode, the pair is considered a match if the similarity values for their core concepts or their domains and ranges are greater than the threshold.
Allowing matches based solely on high similarity of domain and range in the recall-oriented con guration results in very low precision unless further steps are taken. We use a combination of two approaches to reduce the number of false positives. The rst is the calculation of the con dence value: this is done by averaging the similarity values for the exact labels, their domains, and their ranges. The second is that we keep a list of each entity that is considered a match so far, along with the entity it maps to and the con dence value. Every time a new potential match between properties is identi ed, its con dence value is checked against any existing current matches involving those properties. If the new match has a greater con dence value, the old match is removed in favor of the new one, otherwise the new match is ignored. Using the exact label similarity when computing the con dence values rather than the core concept eliminates the loss of precision associated with extracting the core concept, e ectively breaking any ties in favor of the closer lexical matches. The e ect of this approach is that any properties with the same domain and range act as a lter, with the speci c match from that set chosen based on the actual property label. 4.1
Table 4 shows the results of PropString on the OAEI Conference track. The
system was con gured with a threshold of 0.9 and to only include matches in which
both entities were in the namespace of the ontologies to be matched (in
accordance with the OAEI guidelines). The results are compared with those of Soft
TF-IDF with a threshold of 0.8. This was shown in [
We also conducted a series of tests which show that there are no redundant aspects to the PropString metric: removing any element reduces performance. In particular, removing the idea of extracting the core concept from property labels has such a disastrous e ect on recall that the precision-oriented con guration becomes useless. Similarly, removing either the best match lter or using simple label similarity for the con dence value rather than averaging label, domain, and range similarity cuts precision in half in the recall-oriented con guration. Consideration of domain and range in the similarity computation is shown to be the key to this approach. 4.2
We also evaluated the performance of PropString on the YAGO-DBPedia
alignment task. We compare the performance of PropString to that of the basic
Soft TF-IDF similarity metric and the PARIS alignment system. PARIS is an
acronym for Probabilistic Alignment of Relations, Instances, and Schema. The
system approaches property alignment by considering the degree of overlap
between the sets of instances involving each property [
There is no established reference alignment for the DBPedia and YAGO
ontologies. We begin the process of creating one by collecting the equivalent
property relationships generated by PropString, Soft TF-IDF, and PARIS and
using Amazon's Mechanical Turk to verify their accuracy. In total, these three
approaches produced 133 unique equivalence matches that involved properties.
We formulated questions for each match of the form \Does property label A
mean the same thing as property label B?" Respondents were instructed to
choose one of four options: they mean the same thing, one is a more general or
more speci c term than the other, they are related in some other way, or there
is no relation. We provided these more nuanced options rather than just yes
or no because we would like to eventually develop a reference alignment useful
for evaluating the performance of alignment systems that produce all types of
matches. There has been some debate in the alignment community on how to
phrase questions to crowdsourcing participants in order to acquire good-quality
matches [
The 133 matches were grouped into 19 sets of 7 questions each, and we paid
25 cents for each set. Preliminary testing showed that the general response on
these nuanced veri cation questions were not very reliable (others have
indicated problems with scammers for these tasks as well [
Rather than requiring precise agreement on the type of relationship (if any) for each potential match, it might make sense for our current purposes to consider a weaker sense of agreement. One option is to consider two answers to be in agreement if they both either indicate some relationship exists or they both conclude there is no relation between the two properties. In this case, if one person indicated two entities are related in a sub/super relationship and another indicated that they are equivalent, these answers would be considered in agreement. Two answers would only be seen to disagree if one indicated there is no relation at all and the other disagreed. This way of interpreting the results might be useful for an alignment system if the results from this phase were being used to either nd all types of relationships between entities or to gather all possible matches and use further processing to lter the set down to only equivalence relations. We will call this \recall-oriented." Figure 1 (top) shows the results of PARIS, Soft TF-IDF, and PropString on the YAGO-DBPedia property alignment task using this de nition of correctness.
Another possible way to interpret the results is to consider two answers to be in agreement only if they both conclude either that the entities are precisely equivalent or that they are not equivalent. Using this viewpoint, if one person indicated that two entities are related in a sub/super relationship and another indicated that they are precisely equivalent, these answers would be seen as disagreeing. If instead one person considered the match to be a sub/super relationship and another considered them to have no relationship at all, these two individuals would be seen as in agreement because they both conclude that there is no equivalence relationship. This interpretation may be useful if an alignment system is attempting to nd high-quality equivalence relations between entities, which it may subsequently use as a seed for further processing. We will refer to this as \precision-oriented." Figure 1 (bottom) is analogous to Figure 1 (top) but uses this precision-oriented de nition of correctness.
The basic string metric Soft TF-IDF produces the highest precision, regardless of how correctness is measured. Further, that precision is 0.79 and .96 (depending on evaluation approach), which is on par with the degree of agreement among the Turkers on these matches. So we see that a straightforward string metric can in some ways outperform more sophisticated alignment strategies. In fact, PARIS and the precision-based con guration of PropString have such low 0.9 0.8 recall that they may not be of much utility for many application scenarios. This is surprising considering the strong performance of this PropString con guration on the properties within the Conference track.
Another thing to note from these results is the very strong performance of the recall-based con guration of PropString, both relative to the other approaches and in an absolute sense. When PropString is run in its recall con guration with a threshold of 0.5, both the precision and recall are in the neighborhood of that produced by much more complex alignment systems on the simpler task of class equivalence in smaller test sets, such as the Conference track. Of course, the very preliminary nature of the YAGO-DBPedia reference alignment must be kept in mind. More work, hopefully involving results produced by many other alignment system on this pair of ontologies, is needed to con rm these results. 5
The only existing work focused speci cally on property matching of which we
are aware is the extensional approach described in [
There has also been some analysis of the particular characteristics of
properties versus classes and instances in ontologies. For instance, [
In 2002 Melnik and his colleagues developed a strategy called \similarity
ooding" to improve the performance of alignment systems [
There have been several attempts to modify the standard similarity
ooding approach to further improve the performance on property matching. For
example, comparison of instance data and datatype property range values can
be improved by using di erent similarity metrics for strings, dates, integers, etc.
[
The PropString algorithm's consideration of the lexical similarity of the
domain and range of properties is somewhat similar to the work by Vizenor and
his colleagues in [
This work explored the performance of current ontology alignment systems on property alignment using the OAEI Conference track as a benchmark. In addition, a second benchmark involving property matches was suggested. The paper also introduced PropString, an entirely string-based approach to aligning properties. The performance of PropString was evaluated using both benchmarks and was shown to be better than the best-performing string metric by a wide margin. PropString also compared favorably to the PARIS alignment system on the secondary benchmark, based on a crowdsourced evaluation of matches using Mechanical Turk. While the performance of PropString is encouraging, the f-measure on property still lags that of classes, and more work needs to be done in this area.
Several aspects of the work presented here require further validation. In particular, additional experimentation regarding crowdsourcing reference alignments using Mechanical Turk needs to be done to verify the potential uses of the approach. For instance, our preliminary results showed that general users can often give good input on \yes or no" alignment veri cation tasks but that more complex questions regarding the type of relationship between two entities (e.g. equivalence, subsumption, inverse properties) is more di cult. It would be useful to develop guidelines for when and how to qualify users for di erent types of alignment tasks. More work in particular remains to be done in order to generate an established high-quality reference alignment for the YAGO-DBPedia alignment task. In order to do this, we need to generate results on this ontology pair using more alignment systems. These results can then be manually veri ed, either through Mechanical Turk or by experts. Additionally, we would like to incorporate the PropString approach into a full-featured alignment system and evaluate the di erence in performance.
Acknowledgments. This work was supported by the National Science Foundation award 1017225 \III: Small: TROn|Tractable Reasoning with Ontologies."