In this paper, we examine the possibility of using data collected from millions of tables on the Web to extend an ontology with new attributes. There are two major challenges in using such a large number of potentially noisy tables for this task. First, table columns need to be matched to create groups of columns that represent a new (or existing) attribute for a particular class in the ontology. Second, the column groups need to be ranked according to their \usefulness" in augmenting the ontology. We show several approaches to addressing these challenges and report on the results of our extensive experiments using Web Tables from the Web Data Commons corpus, and using the DBpedia Ontology as our target ontology.
The Web is a vast source of valuable knowledge that can be used to extend
or augment a given ontology. Knowledge extraction from the Web is a
wellstudied problem and an active area of research [
In this paper, we examine the possibility of using Web tables to augment a given ontology with a new set of attributes. Our hypothesis is that for each class in the given ontology, there are tables on the Web describing instances of the class and their various attributes. Further, not only a large number of these attributes are not already captured in the ontology, but many are not considered \useful", i.e., may be irrelevant, inaccurate, or redundant.
The approach we take in this work is a two-step process. First, tables are matched among each other and to the target ontology, to group columns that refer to the same attribute and align them with classes and existing attributes in the target ontology. The second step ranks the column groups based on a measure of quality or usefulness of the group in augmenting the existing attributes in the target ontology. We perform an empirical study of the performance of this approach in using Web Tables extracted from the Common Crawl3 to augment the properties in DBpedia ontology.
The pioneering work using Web tables to discover new attributes was done by
Cafarella et al. in 2008 [
Das Sarma et al. [
Lee et al. [
Several systems have been proposed to extend a user-speci ed query table
with content from a corpus of Web tables [
Our goal is to design an ontology augmentation solution to nd new attributes for an ontology using an external source of structured data, such as a corpus of web tables. The general idea followed by existing approaches is to count attribute occurrences in the table corpus and use them to estimate probabilities for encountering these attributes. Based on these probabilities, several di erent metrics can be de ned to assess the value of adding an attribute to the ontology (see Section 3.3). These metrics measure how likely a new attribute is to co-occur with existing attributes (in the ontology) or how consistent the resulting schema would be if the new attribute is added to the ontology.
Existing methods often consider the use-case of extending a user-provided data source in an ad-hoc setting. In the case of extending an ontology, however, a variety of matching methods can be used to align the schema of the Web tables with the ontology. We propose to incorporate the mapping created by such methods by calculating all co-occurrence frequencies based on the mapping.
The relevance of new attributes is measured based on how frequently they
co-occur with known attributes. Using exact string matching, these frequencies
can be obtained from a corpus of web tables by counting, as shown by the
approaches using the AcsDb [
We compare several di erent approaches of de ning attribute similarity, which will be introduced in the following.
Equality of Known Attributes. For the attributes that already exist in the
ontology, we create a mapping from the web tables to the ontology. For the
results in this paper, we use T2K Match [
Equality of Unknown Attributes. Based on the mapping produced by T2K
Match, we can group the web tables by their class in the knowledge base
(blocking step) and then match all un-mapped attributes among each other. For
attributes which do not exist in the ontology, we compare the following schema
matching approaches:
Label-based Matching. Using the column headers of web tables as features, we
evaluate using exact column header equality to nd matching columns. We
refer to this approach as \Exact" in our experiments. We further evaluate \String
Similarity", which calculates the similarity of the column headers using the
Generalised Jaccard Similarity with Edit Distance as inner similarity function.
Instance-based Equality. We further evaluate similarities which are created by
the instance-based schema matcher of the Helix System [
Key/Value-based Equality. The Key/Value-based equality \Key/Value Matching" compares only those values of two columns, which are mapped to the same instance in the ontology. This means, two columns are equivalent only if they contain similar values for the same instances. To obtain the similarity values, we use the value-based matching component of T2K Match.
After the calculation of the similarity values, we must decide which set of columns
refers to the same attribute. For attributes that already exist in the ontology,
all columns with a similarity value which is above a threshold are considered to
be equal to the existing attribute. However, for attributes which do not exist
in the ontology, there is no such central attribute. We hence evaluate di erent
partitioning strategies [
Connected Components. We calculate the connected components on the similarity graph. Each resulting component is a cluster.
Center. The Center algorithm uses the list of similarities sorted in descending order to create star-shaped clusters. The rst time a node is encountered in the sorted list, it becomes the center of a cluster. Any other node appearing in a similarity pair with this node is then assigned to the cluster having the former node as center.
MergeCenter. The MergeCenter algorithm is similar to the Center algorithm, but has one extension. This extension is that if a node is similar to the centers of two di erent clusters, these clusters are merged together. 3.3
After de ning attribute equality, we can now specify how the relevance of new
attributes is determined. All compared ranking methods are de ned based on
attribute cooccurrence probabilities, which we de ne according to Cafarella et
al. [
Let a schema s 2 S be a set of attributes and S be the set of all schemata. A table has this schema if its columns correspond to the attributes (based on the schema mapping), regardless of their order and column header. Let f req(s) be the number of tables with schema s in the corpus and schema f req(a) be the number of tables that contain attribute a:
Then the probability of encountering a in any table in the corpus is schema f req(a) =
f req(s)
X fsjs2S^a2sg p(a) = schema f req(a)
Ps2S f req(s) (1) (2)
The number of tables that contain two attributes a1; a2 is de ned analogously as schema f req(a1; a2). The conditional probability of seeing attribute a1 given a2 is And the joint probability is (3) (4) (5) (6) (7) Attribute Ranking Methods. We now de ne the methods that are used to calculate a score for each attribute, which is then used to rank all unknown attributes. A higher score indicates a higher relevance of the attribute for the schema extension task.
Conditional Probability based on Class. Given the class C in the ontology, how
likely is it to encounter the attribute a [
p(ajC) = P
schema f req(a; C)
a22SC schema f req(a2; C)
Schema Consistency. This measure re ects the likelihood of seeing a new
attribute together with the existing attributes [
SchemaConsistency(a; s) = 1
X p(aja2)
jsj a22s
Schema Coherency. Based on Point-wise Mutual Information (PMI), schema
coherency is the average of the PMI scores of all possible attribute combinations
[
SchemaCoherency(a; s) = 1
X npmi(a1; a) jsj a12s npmi(a1; a2) =
4.1
Our rst set of experiments are performed on the T2D Gold Standard [
Identifying equal Attributes We evaluate the di erent matching and partitioning approaches introduced in Section 3.1. The gold standard contains mappings from the web table columns to properties in the ontology. As we are interested in nding partitions of columns which represent the same attribute, we create one partition for each property in the ontology, which contains all columns which are mapped to this property. We then apply the di erent methods to all columns of the web tables in the gold standard and measure the degree to which we can reconstruct these partitions.
Figure 1 shows a comparison of the di erent partitioning approaches. The xaxis depicts the similarity threshold and the y-axis shows the resulting F1-score. We can see that the best performance is achieve with rather low thresholds and the Center algorithm.
Figure 2 shows the quality of the Clusterings using di erent matching approaches. Again, the x-axis depicts the similarity threshold and the y-axis shows the resulting F1-score. We see that the label-based matching with string similarity outperforms the instance-based approaches. The reason for the good performance of the label-based approach is that the web tables are grouped by the class in the ontology to which they are mapped, and hence column headers are in most cases not ambiguous. The rather bad performance of the instance-based approaches is explained by the fact that web tables usually only have very few rows and there might not be enough overlap among the columns from di erent tables.
Combining the instance-based and label-based approach into a hybrid matcher did not signi cantly improve the performance compared to the label-based approach. Closer inspection of the results showed that this is due to the used gold standard, which contains mostly tables with columns labels of high quality. Attribute Ranking For a subset of the T2D tables, those mapped to the country class, we manually label all columns with either \useful" or \not useful". In total, this subset contains 207 columns, of which 86 are annotated as \useful". We then evaluate the performance of the di erent ranking methods. Figure 3 shows the precision@K and recall@K achieved by the di erent ranking approaches. In addition to the ranking methods described in Section 3.3, we further evaluate each of the ranking methods in a variant that is weighted by PageRank. The intuition is that web pages with a high PageRank likely contain useful content and hence the web tables on these pages also contain relevant attributes. The used PageRank values are obtained from the publicly available Common Crawl WWW Ranking.4 For each partition of columns, we use the maximum PageRank of all source web pages and multiply it with the score that was calculated by the ranking method. Among the di erent ranking methods, schema consistency performs best, followed by schema coherency. The variations with PageRank
perform worst, which might be caused by the rather small number of web sites in the gold standard.
Remove one Attribute Experiment The assessment of the usefulness of an attribute can be subjective. Hence we design another experiment, where we remove one existing attribute from the ontology for several classes. As this attribute was already existing, we can objectively say that it is useful. We then measure the quality of the rst cluster that resembles this attribute and also the rank at which we can nd it in the output. We use the following classes and attributes in this experiment: Company (industry ), Country (population), Film (year ), Mountain (height ), Plant (family ), VideoGame (genre). The left chart in Figure 4 shows the average rank of the rst attribute cluster which matches the removed attribute over all ranking methods by matcher. The bar \No Matching" shows the result of neither using correspondences to the ontology nor any of the matching approaches, i.e., attributes are equal only if their column headers match exactly. The results without prior mapping knowledge show the importance of matching attributes before calculating the ranking functions. Without mapping knowledge, attribute frequencies are under-estimated, and the respective attribute is ranked too low. The right chart in Figure 4 shows the average rank over all matching methods by ranking method. Again, the schema consistency ranking performs best and the variations including PageRank consistently perform worse. We now repeat our experiments on the WDC Web Tables Corpus 20125, which contains 147 million relational web tables. To give an overall impression of the full corpus, Figure 5 shows the number of new columns and clusters that we can generate for selected classes. These numbers show the large amount of potentially new attributes that can be found in the corpus.
Attribute Ranking As we have no gold standard for the full corpus, we manually annotate the top 15 ranked clusters for each ranking method for several classes with either \useful" or \not useful". Figure 5 shows the performance of each method averaged over all classes in terms of precision@15. The results show again that the schema coherency and consistency measures outperform the conditional measure. This indicates that attribute co-occurrence is a stronger signal than pure frequency of attributes, even if conditioned with a class from the ontology.
Remove one Attribute Experiment Again, to have a more objective view on the results, we remove one attribute from DBpedia as before and nd the topranked attribute cluster which matches the removed attribute. The left chart in Figure 6 shows the rank of these clusters by matcher and the right chart by ranking method. Concerning the matching approach, we now nd that the label-based and key/value-based methods achieve comparable results. The difference here to the experiment on the gold standard is that we take into account a much larger number of tables and hence have more variety and a more realistic sample of the data quality. If we compare both of the matching approaches to a baseline approach (\No Matching"), which does not use the prior knowledge of the mappings to the ontology, we can again see that the ranking results are worse. Looking at the di erent ranking methods, we see a result that di ers from the previous results. The Conditional Probability ranking now performs best. A possible explanation is that the attributes that we removed are quite common. Hence, many tables have such attributes and the ranking by frequency is su cient. Another interesting fact is that now the PageRank makes a di erence. Although it is still worse than without, we can presume that a reasonable evaluation of a ranking method incorporating the PageRank requires the use of a large corpus.
In summary, the results of our experiments show that: { It is feasible to use a large corpus of structured data from the Web to augment an ontology. In particular, we are able to augment a general-domain ontology such as DBpedia with millions of Web Tables extracted from the Web. We manually veri ed that a number of attributes ranked highly by our algorithms were strong candidates for augmenting the DBpedia ontology, and such augmentations would enable new applications of the ontology. { Our results comparing di erent algorithms were mixed and without a clear winner across all the experiments. The size of the gold standard and the classes chosen for manual veri cation clearly a ected the relative performance of the algorithms. This calls for larger benchmarks, more comprehensive evaluation, and hybrid/ensemble methods that e ectively take advantage of the bene ts of each of the algorithms.
Future work also includes: 1) extending our framework to include more advanced matching techniques particularly from recent work in ontology matching 2) evaluation on other sources of structured data (e.g., open data portals such as data.gov), and other ontologies 3) Extending the augmentation to relations and classes of the ontology 4) using the same quality metrics for ontology augmentation from textual and semi-structured sources and an evaluation of how well structured data on the Web can contribute to building and augmenting an ontology, comparing with the textual and semi-structured sources.