We present new approaches used in the DAGOBAH system to perform automatic semantic table interpretation. DAGOBAH semantically annotates tables with Wikidata entities and relations to perform three tasks: Columns-Property Annotation (CPA), Cell-Entity Annotation (CEA) and Column-Type Annotation (CTA). In our system, the initial scores from entity disambiguation in uence the CPA output, which, in turn, in uences the output of the CEA. Finally, the CTA is computed using the type hierarchy available in the knowledge graph in order to annotate columns with the most suitable ne-grained types. This approach that leverages mutual in uences between annotations allows DAGOBAH to obtain very competitive results on all tasks of the SemTab2020 challenge.
Within the ever-expanding Web of data, more and more knowledge graphs (KGs)
become available. However, these KGs may su er from inconsistency and
incompleteness issues [
These automatic annotation tasks raise several challenges. For example,
tables present limited context to resolve semantic ambiguities, and their layout can
be complex (e.g. merged rows, missing headers, table orientation to determine).
The aforementioned perspectives and challenges have motivated the development
of numerous approaches that perform table annotation with entities and relations
from a KG via three main tasks: Cell-Entity Annotation (CEA), Column-Type
Annotation (CTA) and Columns-Property Annotation (CPA) [
During the SemTab2019 challenge, we rst developed and evaluated the
DAGOBAH system [
The remainder of this paper is organized as follows. In Section 2, we introduce some related approaches tackling the tasks associated with tabular data annotation. In Section 3, we detail the algorithms used in the DAGOBAH system, whose performance on the SemTab2020 corpus is presented and discussed in Section 4. Finally, we outline some future works in Section 5. 2
Two main approaches are used to carry out the CEA task. The most
common approach consists in nding a match for each cell of a given table using
syntactic lookups (e.g. Levenshtein distance), aligning ontologies, or exploiting
embeddings [
In parallel, e orts have been made by the community to provide
evaluation corpora for these di erent tasks. While the rst corpus only contained
428 Wikipedia tables [
More recently, the SemTab2019 challenge invited research teams to compare
the performance of their tabular data annotation systems for the three tasks
mentioned above. The challenge took place in four rounds [
The DAGOBAH system is designed to interpret relational tables by annotating them with entities and relations from the Wikidata knowledge graph (KG). It mostly consists of the following steps (Fig. 1). Given a relational table as input, the entity lookup module retrieves candidate entities from the KG for each target cell (Section 3.1). The pre-scoring module evaluates each candidate with a con dence score (Section 3.2). Then, the Columns-Property Annotation (CPA) is carried out (Section 3.3). Its output is used during the Cell-Entity Annotation (CEA) to disambiguate entities (Section 3.4). Finally, the Column Type Annotation (CTA) uses the output entities and a majority vote to annotate columns with types (Section 3.5).
An embedding approach has also been implemented, based on the intuition
that semantically similar entities can be clustered in a vector space,
allowing geometrical disambiguation. The implementation is similar to the one
described in [
Given a target cell3 em contained in a table, we aim at retrieving a set of relevant candidates Ec from a KG, i.e. entities whose labels or aliases are similar to the text of the cell. We employ two strategies to evaluate the similarity between a cell and the candidate entities: an exact match using a regex similarity and a threshold-based match using the Levenstein ratio. We take the maximum value between all comparisons made across entity labels and aliases.
Regex similarity Candidate labels or aliases should include all the words of em in any order. This is particularly useful to match the full name of a person since the rst and last names could appear in any order, e.g. \Elon Musk" versus \Musk Elon". A full edit ratio on these two multiple tokens string would yield the relatively low score of 0.44.
Levenshtein ratio This ratio is computed between the candidate labels and aliases, and the text of the cell. We empirically x the threshold to 0.65 to ensure that a cell has at least one candidate and we then retain the top 50 candidates for each cell.
In the context of the SemTab2020 challenge, the table corpora are signi cantly large with thousands of tables and cells to annotate (Table 1). The public Wikidata API is not an ideal lookup service due to restrictions on the number of concurrent connections, result set sizes, and query time. To avoid these limitations, we built our own lookup service using the Wikidata Toolkit4 and a Spark-based big data platform. Speci cally, from the initial raw Wikidata dump, we use the Wikidata Toolkit to lter out the unnecessary documents such as Form, Lexeme, MediaInfo, Sense and Statement documents, so that we only retain entities that are item documents identi ed by QID and property documents identi ed by PID, associated with their labels and aliases in all languages. We 3 In the context of the SemTab2020 challenge, the target cells are provided. In general, DAGOBAH has a module that enables to infer a primitive type for any arbitrary cell so that lookups are only triggered on cells that have entities as values. 4 https://github.com/Wikidata/Wikidata-Toolkit then store the ltered dump in a Hadoop Distributed File System (HDFS) and perform the entity lookup via the Spark framework. Table 2 presents the Wikidata KG used in the challenge. It should be noted that during the Round 1, we built the lookup service based on an old version of Wikidata (from 2017) that contains fewer entities (50 millions vs. 86 millions in version 2020), which has resulted in incomplete lookups, and thereby hindered the annotation results as discussed in Section 4.
We provide in Table 3 the complete lookup time for the Round 1, 2, and 3 (line \Current Time"). To construct our lookup service, we considered a pure Python Levenshtein module which has very poor performance (generally, 50 to 100 times slower than the more e cient Cython Levenshtein library5). As a result, our current lookup service is not optimized yet, taking about 268h ( 11 days) for the lookups of Round 3. In a future system, we will install the Cython Levenshtein library to signi cantly reduce the execution time. We roughly estimate the potential lookup time of such a future system (line \Ideal Time") by inducing the time of Cython Levenshtein usage from the pure Python Levenshtein's time. The pre-scoring step aims to assign a preliminary con dence score to each candidate ec 2 Ec generated after the lookup step. The con dence score function (Equation (1)) leverages the semantic contextual relationships and literal similarity between the candidate ec and the cell em.
Sc(ec; em) = Sccontext(Ntable(em); Ngraph(ec)) Scsim(em; ec)x (1)
Sc(em; ec) is the product of a context factor Sccontext(Ntable(em); Ngraph(ec)) and a literal factor Scsim(em; ec). Scsim(em; ec) gives the highest Levenshtein ratio between the cell and the label set of the candidate. This label set is composed of the labels and aliases of the entity (e.g. \France", \La France" for Q142). x 2 N+ allows to de ne the importance of the textual similarity acting as an ampli cation factor. We empirically observed that 5 was an appropriate ampli cation factor for x for this challenge.
The context score is calculated by Equation (2):
Sccontext(Ntable(em); Ngraph(ec)) = (
Ns if Ns 0:1 0:0001 otherwise (2) Ntable(em) is the set of neighboring cells in the same row as em. Ngraph(ec) is the set of neighboring elements of ec in the KG6. Neighboring literals are directly added to Ngraph(ec) whereas, for neighboring entities, their labels and aliases are added. Ns is a set which contains the best neighborhood matching score nsi for each neighboring cell ni 2 Ntable(em) and all neighboring literals or nodes in Ngraph(ec). For each neighboring cell ni, the neighborhood matching score nsi 2 Ns is generated as follow: { If ni is a string, then nsi is the highest Levenshtein similarity value. { If ni is a number, then nsi is given by Equation (3): jni
ngj nsi = max 1 (3)
ng2Ngraph(ec) jnij+jngj { If ni is a date-time value, and if a matching exists between the cell and a neighboring element, then we set nsi to 1, otherwise nsi = 0. { If the previous steps gives a nsi value lower than 0.85, then the system resets nsi to 0.0001.
For example, the con dence score Sc(em; ec) of the candidate ec \Q1574185" with the cell em \University College Cork" is equal to 1 since \Q1574185" has this exact label and all neighboring cells share information with neighboring elements of \Q1574185". 3.3
The CPA task involves nding a semantic relation between a pair of ordered columns fhead; tailg. In other words, we try to gure out the most suitable relation among the ones connecting a candidate entity in Ehead for the head column to a candidate entity in Etail for the tail column. We employ a simple majority voting strategy which relies on the occurrence and accumulated con dence score of the relation r that we de ne as: 6 Neighboring elements are object (resp. subject) of triples whose subject (resp. object) is ec.
{ Occurrence(r) = #(ehead; etail), { AccumulatedCon denceScore(r) = P Sc(ehead) Sc(etail) such that ehead 2 Ehead, etail 2 Etail, and hehead; r; etaili 2 KG.
In contrast to the relation's head which is always an entity, its tail can be an entity, a textual value, a numerical value, or a date-time value. Literal values may be noisy (e.g. \370.1069999997" may represent the integer value \369", \1845-01-01" may correspond to \1845/01/01" or \1845" in the KG). Due to the di erent natures of each tail type, we consider di erent matching metrics to verify whether a triple hehead; r; etaili exists in the KG: { For entity IDs, score(id1; id2) = 1 if the two ids are exactly the same, otherwise 0. { For numerical values, score(num1; num2) = 1 jnum1j + jnum2j { For string values, score(text1; text2) = Levenshtein(text1; text2) { For date-time values, we compare many variants of date-time values (e.g. from the initial value \2020", we could have \2020-01-01" or \2020/01/01"). Two date-time values are matched, i.e., score(date1; date2) = 1 if one is a variant of the other.
From the criteria above, the relation with the highest occurrence is considered the target relation. If there are several relations having this highest occurrence, we select the one with the highest score. For example, consider the table provided in Fig. 1. The two relations P131 (\located in the administrative territorial entity") and P159 (\headquarters location") can relate the rst (Col 0) and the third (Col 2) columns. Speci cally, Q1574185-\University College Cork" (resp. Q245247-\King's College London") is located (P131) in Q36647-\Cork" (resp. Q202059-\London Borough of Lambert"). Cork is also the headquarter (P159) of University College Cork. Therefore, the occurrence count of P131 is 2, and 1 for P159. We conclude that P131 is the CPA for the column pair fCol0, Col2g. jnum1 num2j 3.4
The CEA task aims to annotate the table cells with entities from the KG. Taking the CPA into account, for each candidate entity in a given row, we update its score computed in the pre-scoring step (Section 3.2) by adding a constant score 1 (resp. 0) if the CPA relation can (resp. cannot) connect this candidate to the counterpart in the remaining column. The output entity is the one with the highest score.
For example, for the cell \Cork" in Fig. 1, two of the candidate entities are Q36647 (\Cork city in Munster, Ireland") and Q162475 (\Cork County, Ireland"). They both have the same score output from the pre-scoring step (Section 3.2). Given we have determined the relation between \Col 0" and \Col 2" to be P131 and that the candidate Q36647 is linked to the cell \University College Cork" via this relation, we increase the score of Q36647 by 1. Q36647 then becomes the candidate with the highest score, and is chosen as the CEA output for the \Cork" cell. 3.5
After getting the output of CEA, a majority voting strategy is adapted to identify the most precise type for target columns. This process is illustrated in Fig. 2 for the rst column (\Col 0") of the example table depicted in Fig. 1.
The CTA annotation begins with a type enrichment step. Let Tj be the set of candidate types for the cell j from a target column. Tj is represented by a hierarchical tree with 3 levels of types. We consider the types related by the P31 predicate (\instance of ") to the predicted CEA entity as level 0. Their parent types linked through the P279 predicate (\subclass of ") are assigned to level 1 and their ancestors to level 2. The system gives priority to the direct types. The rank of a candidate type is another useful factor for the CTA decision. According to Wikidata's mechanism for annotating multiple values for a statement, a type for an entity may have three ranks7. We represent those ranks as priority numbers: PREFERRED-2, NORMAL-1 and DEPRECATED-0.
The second step consists in a preliminary selection of types. We compute the frequency, accumulated level, and accumulated rank for all candidate types of a target column, i.e. all types appearing in at least one Tj of the column. We then select the types with the highest occurrence, the lowest accumulated level, and the highest accumulated rank at the same time. In case of ties, we give priority to the occurrence, then to the accumulated level, and nally to the accumulated rank. In the example of Fig. 2, Q2385804 and Q38723 are chosen at this step.
The nal step consists in computing the distance between the chosen candidate types and the entity Thing (Q35120) in order to select the most speci c type. We rst consider the mutual inheritance relationship between the remaining candidate types. When such a relationship exists, we select the most speci c type. If no inheritance relationship can be found, we compute the shortest distance to Thing. If there is still a tie among some candidate types, the system randomly selects one of them as CTA output. 4
Table 4 provides the annotation scores (F1-score, precision, and coverage) of our
system for the three tasks in Rounds 1, 2, 3, and 4 of the challenge. Note that the
datasets used in Rounds 1, 2, and 3 are automatically generated in a synthetic
way by adding some arti cial noise (Synthetic Tables). Interestingly, in Round 4,
beside a synthetic dataset, a novel corpus (Tough Tables [
As stated in Section 3, during Round 1, we implemented two variants of DAGOBAH: an embedding-based version (DAGOBAH Embedding) and an optimised scoring-based version (DAGOBAH SL). We notice that DAGOBAH SL performs much better than DAGOBAH Embedding. The drop in the scores is arguably derived from the fact that DAGOBAH Embedding retains only 3 clusters for the entity disambiguation, which does not always involve all the good candidates given the imperfection of the current clustering algorithm.
We observe that one di culty concerns the dynamic and evolving nature of KGs such as Wikidata. During Round 1, we used an outdated KG version (circa 2017 vs. target March 2020, see Table 2). Hence, the lookup service was not able to retrieve relevant candidates for 5% of the target cells, leading to a signi cant drop in performance, compared to the leader MTab. Challenge organizers should either consider distributing the reference KG to use alongside the tables to annotate, or consider tables with evolving annotations along the time, anticipating that new items or even properties may be added in the KG.
The other main limitation of Rounds 1, 2, and 3 of SemTab2020 resides in the nature of the data to annotate. Indeed, tables are synthetically generated from the Wikidata knowledge graph. Consequently, the proposed tables are relatively clean and lookup operations can easily match cells in the tables to entities in Wikidata even if noising techniques are introduced. In real-world applications, tabular data can contain complex values (e.g., cells containing lists of entities using various separators, alternative entity names), artifacts (e.g., data encoding problems, formatting errors, input errors, missing values), and more complex layouts (e.g., merged rows/columns, multi-line headers, horizontal/vertical/matrix tables) making table manipulation and annotation much more complicated. In order to produce more robust, generic, and intelligent annotation systems, it seems important that evaluation corpora take these challenges into account in the future. An example can be found in the Tough Tables corpus from Round 4 which contains tables manually scraped from the Web. We observe a remarkable degradation in performance of CTA and CEA tasks given the complexity and ambiguity of this corpus. 5
In this paper, we presented the improvements implemented in DAGOBAH, a generic and scalable system for table annotation. In particular, our approach involves mutual in uences between the two tasks of Cell-Entity Annotation and Columns-Property Annotation to resolve ambiguities. Additionally, by leveraging the type hierarchy, we are able to determine the most ne-grained type in the Column-Type Annotation task. We also focused on the scalability of our system since computational time is an important limitation in real-world use cases.
Our promising results pave the way for several perspectives. First, APIs and
GUIs will be developed around DAGOBAH to enable its real-world and
industrial usage. Second, following some preliminary work [