In this paper, we present the DAGOBAH system which tackles the Tabular Data to Knowledge Graph Matching (TDKGM [6]) challenge. DAGOBAH aims to semantically annotate tables with Wikidata and DBpedia entities, and more precisely performs cell and column annotation and relationship identi cation, via a pipeline starting from preprocessing to enriching an existing knowledge graph using the table information. This paper presents techniques for typing columns with negrained concepts while ensuring good coverage, and for valuing these types when disambiguating the cell content. This system obtains promising results in the CEA and CTA tasks on the challenge test datasets.
The annotation of tables using knowledge graphs is an important problem as
large parts of both companies internal repositories and Web data are
represented in tabular formats. This type of data is di cult to interpret by machines
because of the limited context available to resolve semantic ambiguities and the
layout of tables that can be di cult to handle. The ability to annotate tables
automatically using knowledge graphs (encyclopedia graphs such as DBpedia and
Wikidata or enterprise-oriented graphs) allows to support new semantic-based
services. For example, it opens the way to more e cient solutions to query (e.g.
\moving beyond keyword" for dataset search [
In this paper, we propose a complete system to annotate tabular data, from pre-processing to entities and relations extracted from knowledge bases, without using any tables context. The main contributions of our system are:
{ A new pre-processing tool chain improving the results of the DWTC framework3. { A three-step annotation process (cell-entity annotation, column-type annotation and disambiguation) leveraging on Wikidata and DBpedia. { An alternative approach based on clustering operations using Wikidata embedding. 2
DAGOBAH: an End-to-End System for Annotating
Tables
DAGOBAH is implemented as a set of tools, used in sequence, to provide three
main functionalities.
1. The identi cation of mapping relationships between tabular data and
knowledge graphs.
2. The enrichment of knowledge graphs by transforming into triples the
knowledge contained in table. DAGOBAH's target knowledge graph is Wikidata
for several reasons including its dynamics, coverage and the quality of data
[
To provide these features, DAGOBAH is structured in the following way. The pre-processing modules (Section 2.1) perform the tables cleaning and a rst high-level characterisation of their shape and content. The entity linking modules accomplish the tasks of the challenge itself, namely the cell-entity annotation (CEA), the column-type annotation (CTA) and the columns-property annotation (CPA). Two methods have been studied to carry out these tasks: a baseline exploiting lookup and voting mechanisms (Section 2.2) and a geometric approach based on clustering applied to Wikidata embeddings (Section 2.3). 2.1
In order to correctly process the information contained in the tables, it is rst necessary to infer several characteristics on the shape of the table. In a context of real exploitation in which there is sometimes little or no knowledge on the tables, the information produced by this chain is decisive for the quality of the annotations. The pre-processing toolbox of DAGOBAH, partly based on the DWTC-Extractor, generates four di erent types of information. The precision of the toolbox was evaluated on round 1 dataset (Table 1) and compared to a modi ed version of the DWTC (which does not use HTML tags and thus supports more formats). 3 https://github.com/JulianEberius/dwtc-extractor in the same column have a similar size. However, the robustness of the DWTC algorithm can be improved. Indeed, for example, two strings representing very di erent elements may have the same length (for example "Paris" and "10cm2"). DAGOBAH introduces a new algorithm based on a primitive cell typing system with eleven types (string, oating numbers, date, etc.). Based on these types ti, an homogeneity score is computed on each row and each column x (Equation 1). The mean of all rows and all columns is then compared, and depending on the ratio, the table is said \HORIZONTAL" or \VERTICAL".
Hom(x) = [ 1
X(1 len(x) ti2x (1 2 count(ti) )2)]2 len(x) (1) Header Extraction. The algorithm used in DAGOBAH is based on the primitive types de ned above. The header extractor assumes that the header of a column contain mainly strings and, in most cases, does not share the type of the column cells. The use of these two heuristics allows to identify if a table contains or not a header with a good accuracy (see Table 1). It should be noted that the DWTC framework also o ers a header detection tool but it contains several bugs that make impossible its evaluation.
Key Column Detection. A rst step aims to identify a rst low level type for each column among ve given types (Object (mentions that are potentially lookup-able in a knowledge base), Number, Date, Unit (e.g. \12 km") and Unknown (containing all the unclassi ed columns)). The key column is an Object column containing a large number of unique values and located on the left side of the table. This pre-processing toolbox was especially useful during the rst round to automatically identify the information contained in the header as well as the column to be annotated in each table. In addition, when the goal is to enrich a knowledge graph with information contained in tables, key column detection is a critical element in determining the subject of the generated RDF triples. The availability of targets during the second round made the use of this pre-processing chain obsolete. However, this does not a ect the usefulness of such tools in real world applications. Entities Lookup. A preliminary cleaning process is rst applied in order to optimize the lookups. The intent is not to correct every string issues, but to have a macroscopic transformation process covering the most known artefacts: encoding homogenization and special characters deletion (parenthesis, square bracket and non alphanumeric characters). Five lookup services are simultaneously queried to retrieve entity candidates from cell mention: Wikidata API, Wikidata Cirrus Search Engine, DBpedia API, Wikipedia API and an internal ElasticSearch index where Wikidata has been ingested, that contains labels, aliases and types associated to Wikidata QIDs. The bene t of having such source is also to manage the indexes, thus the search strategy. An occurrence count is performed at the output of the lookups to select the most popular candidates, and their corresponding types, among the ve services. As DBpedia is the target knowledge base for the challenge, QIDs and Wikidata types are translated to equivalent DBpedia entities (using SPARQL query and following owl:sameAs and owl:equivalentClass predicates). Ancestors are retrieved for each class in the resulting list through SPARQL query to the DBpedia endpoint in order to have an extended list of candidates types.
Column Typing. Before proceeding to counting, it is necessary to remove nonrelevant types. A basic type coverage of the cells criteria is not relevant as right types might be more speci c but not frequent enough to be consider as the target ones. To solve this issue, a threshold based on relative scores is used. To each type t in ftig (list of all types in a given column), a score St is rst associated, from which a relative score Rt is computed (Equation 2).
St = count(t) sum(ti) and
Rt =
St max(Sti) Only types with Rt > 0:7 (con gurable threshold) are considered in the next steps. In order to select the target type from the short-listed ones, a TF-IDF-like method is used to compute the speci city. It re ects the importance of a type t in ftig (Equation 3).
Sspec(t) = St log(
NL count(t) ) where NL is the number of lookup candidates and count(t) is the occurrences of type t within the given column. The inherent advantage of this method is to be independent from the target knowledge base.
Entities Disambiguation. In order to enhance the CEA results, the previous ordered types are used to disambiguate the candidates entities. If the rst candidate of the lookup has the target type, it is selected as the target entity; if not, we select the entity associated to this type in the lookup list (if the list is empty, no annotation is produced). 2.3
The intuition behind this approach is that entities in the same column should be closed in the embedding space as they share semantic characteristics, and thus could form coherent clusters. In order to compare this approach to the baseline, (2) (3) a syntactic lookup to Wikidata embedding is done.
Embedding enrichment and Lookup. The pre-trained Wikidata embedding
[
If an entity (label or aliases) satis es one of the previous conditions, it is accepted as candidate.
Candidates Clustering and Scoring. The challenge is to have most of the expected candidates for a given column in one of the clusters. A grid search strategy measuring precision of correct candidates clustering with di erent algorithms and K values was implemented to determine the best algorithm (K-means with hyperparameter K equals to number of lookup candidates divided by number of rows)(step 3 in Figure 1). In order to select the relevant cluster, a scoring algorithm has been de ned (step 4 in Figure 1). The clusters with the highest rows coverage (i.e. number of rows having at least one candidate in the cluster) are selected. Then, a con dence score is associated to each candidate within these clusters (Equation 4).
Sc(i) = itemconf (i) itemsim(i)x where itemconf (i) is the co-occurrence score given by Equation 5 and x 2 N+ allows to give more importance to the textual similarity. where F E and F H are de ned in Equation 6.
itemconf = F E + 0:5
F H F E = e + 1 NC ; F H = h + 1 NC where e = number of entities in other columns matching with Wikidata properties values of the candidate; h = number of headers in other columns matching with Wikidata properties labels of the candidate; NC = number of table columns. The normalized con dence score for a given cluster n is then computed using: Sk(n) =
Pi2n Sc(i) len(n) where len(n) is the number of elements within cluster n.
From all candidates in the selected clusters, a counting for every existing type is computed, each type inheriting the con dence score of its corresponding candidate (step 5 in Figure 1). All types with a score higher than a threshold (M ax(score) 0:75) is selected. Thus, the output type is the one having the highest speci city within DBpedia hierarchy (using subclasses count and distance to owl:Thing ). Finally, the candidates of each cell resulting from the lookup operations are examined according to the selected type (step 6 in Figure 1). The following score is computed for each lookup entity i belonging to cluster n: Se(i) = Rt (0:2
Sk(n) + 0:5
Sc(i)) where Rt = 1.5 if the entity belongs to the type T produced in CTA, 1:2 if it belongs to a parent of T and else 1. From a given row candidates, the output entity is the one with the highest score. 3
The baseline was used during the four rounds of the challenge (Table 2). The CEA's results are satisfactory, but the baseline has di culty in producing the CTA results expected by the evaluator. In round 1, the predicted type was often too generic or too speci c. In addition, the baseline showed two important limitations: a high dependency on lookup services (over which DAGOBAH has little control) and di culties in correctly setting up algorithms (in particular nding the right compromise between speci city and representativeness of types in the (4) (5) (6) (7) (8) case of CTA). Concerning the CPA, a simple lookup technique on the header was used during round 1 explaining the low accuracy.
For the next rounds, a search over relationships between each pair of instances (output of CEA) of the two candidate columns followed by a majority vote was used. This second technique has signi cantly improved the accuracy of the CPA. To show the contribution of the embedding approach, an evaluation was carried out on the corpus of round 14 with an enrichment of the CTA GT consisting in the addition of the parent types (except owl:Thing ) of the perfect type in order to allow the correct evaluation of the primary and secondary scores. CEA performances are slightly poorer because of basic lookup strategies used (compared to the fully-optimised lookups used in the baseline) and the absence of expected candidates in the selected clusters. But the embedding approach proves to be highly pro cient to determine the type of a column which is the core of more reliable annotations. In addition, the results are particularly interesting in cases where string mentions in the original table are incomplete. In table 54719588 0 8417197176086756912 for instance, one column references movie directors only by their family names (in that case, our baseline performance was poor). Doing K-means clustering on a subset of this table (four rows) performs pretty well even with very few data, as illustrated in Figure 2 (2 clusters shown among 12). Indeed, the green cluster gives the expected candidates, even if disambiguation still has to be done for some cells (using Se). 4
In this paper, we have presented a baseline and an embedding approach to carry
out the task of generating semantic annotations of tables. The embedding
approach shows very encouraging CTA results and an ability to infer candidates
from incomplete information and with no tailored data cleaning. However,
optimizing the hyper parameters still remains challenging. The way DAGOBAH
computes the number of clusters for K-means (based on lookup and table
properties) gives good results but might not be robust with all datasets (this is why
4 For timing and performance reasons, this approach could not be tested on other
rounds in time.
we have decided to consider the high-scored clusters instead of relying entirely
on the rst one). Other clustering algorithms shall be tested that may be more
accurate to nd the best compromise between having all candidates in the same
cluster and enough clusters for good discrimination between candidates.
Combining Wikipedia and Wikidata in a joint embedding space and use
Fasttextlike embeddings, as well as exploiting semantic lookup in addition to syntactic
one could signi cantly enhance the entities mapping. Finally, a full vectorial
approach [