This paper introduces an automatic semantic annotation system, namely MTab4Wikidata, for the three semantic annotation tasks, i.e., Cell-Entity Annotation (CEA), Column-Type Annotation (CTA), Column Relation-Property Annotation (CPA), of Semantic Web Challenge on Tabular Data to Knowledge Graph Matching (SemTab 2020). In particular, we introduce (1) a novel fuzzy entity search to address misspelling table cells, (2) a fuzzy statement search to deal with ambiguous cells, (3) a statement enrichment module to address the Wikidata shifting issue, (4) an e cient and e ective post-processing for the matching tasks. Our system achieves impressive empirical performance for the three annotation tasks and wins the rst prize at SemTab 2020. MTab4Wikidata is ranked 1st in the two tasks of CEA and CPA, and 2nd rank in the CTA task on the round 1, 2, 3 datasets and 1st rank on the round 4 dataset and the Tough Tables (2T) dataset.
Thanks to the Open Data movements, many tabular resources have been made available on the Web and data portals. However, it is di cult to use such tabular data because of missing or incomplete metadata, heterogeneous table schema, table cell ambiguity, or misspelling. A promising solution to improve these tabular data's usability is to generate semantic annotations for table elements using knowledge graph concepts. As a result, such annotations could be useful for other downstream tasks such as data management and knowledge discovery.
CEA
CTA
CPA
Cell Wikidata Item (Entity)
Column Wikidata Item (Type)
Relation Wikidata Property Wikidata Knowledge Graph: Given Wikidata as a knowledge graph of G = (Q; P; S), where Q and P are the set of Wikidata items, Wikidata properties, respectively. A Wikidata item e (e 2 Q) is represented with a unique identi er as Q###; for example, Q2 is the \Earth" item. The P### unique identi er represents a Wikidata property p (p 2 P ); for example, P1082 is for the \population" property. S is a set of statements represented as a triple format of Subject - Predicate - Object. These statements describe Wikidata item information such as literal information or connect Wikidata items1. For example, the Q5 (Earth) item could have a literal statement as Q5 (Earth) - P1082 (population) 7,655,957,369; and a item statement as Q5 (Earth) - P276 (location) - Q7879772 (inner Solar System).
Tabular Data: Let a table T be a two-dimensional tabular structure consisting of an ordered set of N rows and M columns. ni is a row of a table (i = 1:::N ), mj is a column of the table (j = 1:::M ). The intersection between a row ni and a column mj is ci;j is a value of the cell Ti;j .
Annotation Tasks: We formalize the tabular data to Wikidata annotations as the three matching tasks as follows.
{ Cell-Entity Annotation (CEA): Matching a table cell ci;j into a Wikidata item (entity) e. { Column-Type Annotation (CTA): Matching a column mj into a Wikidata item (type) e. { Column Relation-Property Annotation (CPA): Matching the relation between two columns mj1 and mj2 (j1; j2 2 [1; M ]; j1 6= j2) to a relation p. ci;j
CEA
! Q mj
CTA
! Q: rmj1 ;mj2
CPA ! P (1) (2) (3) 1 Wikidata has about 89.75 million items, 7,972 properties, and 1.14 billion statements in October 2020. SemTab 2020 Challenges SemTab 2020 tasks are challenging for many reasons as follows.
Tabular data di culties: { Tabular data does not have metadata to describe the semantic meaning of table elements. { Table headers are ambiguous; for example, the most popular table headers are \col0", \col1", and \col2"; therefore, it is hard to understand table schema if we only rely on the headers. { Table cells are ambiguous, contain many spelling errors and abbreviations.
As a result, directly performing entity search with cell values (e.g., \Tokyo") using standard APIs (e.g., Wikidata API search2 or Wikidata query3) could return whereas too many relevant entities or no relevant entities in the responding list. For example, searching with Wikidata API for an ambiguous cell value of \Tokyo" could get 15,780 relevant entities, while there are no relevant entities for a misspelling cell of \6C 124133+40580".
Knowledge graph di culties: { Noisy Schema: Wikidata is a data-oriented knowledge graph. It has many entity types annotated by humans; therefore, these types are noisy and not consistent for many Wikidata items. As a result, Wikidata schema standardization is still an open challenge. { Wikidata Shifting: Wikidata is a fast-evolving knowledge graph, with around 13 million edited Wikidata items per month4. According to our analysis on the Round 1 data (Wikidata from March to August 2020), 56.09% of the matching items had changed their information statements (possibly a ect the CEA and CPA tasks), and 4.49% changes are related to Wikidata item types (possibly e ect on the CTA task).
Related work SemTab 2019 is the last year's challenge on tabular data to
DBpedia matching [
The last winner of SemTab 2019 is MTab system [
pages/normal|line|2-year| total|monthly
CSV2KG (IDLab) also uses multiple lookup services to improve matching
performance [
2.1
This section describes MTab4Wikidata's assumptions (Section 2.1) and the overall framework in Section 2.2.
Assumption 1 MTab4Wikidata is built on a closed-world assumption. Assumption 2 Input tables are in the vertical relation type.
Assumption 3 The table cells in a column have the same entity types and data types.
Assumption 4 The rst row of the table (n1) is the table header. The rst cell of column is header of this column, c1;j 2 mj .
Assumption 5 The rst column of the table (m1) is the core attribute where a cell value in this column could be matched into a Wikidata item, and other remaining cells in the same row could be matched into the item statements. 2.2
MTab4Wikidata is an automatic annotation system that could address the three
annotation tasks of CEA, CTA, and CPA. Unlike our previous system MTab
(DBpedia matching) built on the joint probability distribution of table element
signals[
MTab4Wikidata contains three steps pipeline as Figure 2. Step 0 is to prepare Wikidata resources with the entity dump and Wikidata history revisions. We use these resources to create the two indexes of fuzzy entity search and fuzzy statement search. In Step 1, we perform table cells lookup to nd relevant entity candidates for each table cell (using the fuzzy entity search) and the two cells in the same row (using the fuzzy statement search). In Step 3, we perform a post processing with a value matching module, then majority voting to select the CEA, CPA, and CTA annotations. The details of each step are described in Section 2.3 (Step 0), Section 2.4 (Step 1), and Section 2.5 (Step 2).
Step 0 Step 1
Entity dump History revisions
Indexing Lookup Fuzzy Entity Search Fuzzy Statement Search Step 2
Value Matching Property Voting Entity Voting Type Voting CPA CEA CTA
In this module, we perform the following operations: { Extracting Wikidata items and these statements: We extract this information from the Wikidata 29 June 2020 entity dump. Note that this entity dump is not available on the Wikidata server now, since they only keep the two months' latest dumps. { Getting history revision of Wikidata items: We crawl Wikidata item history revisions as a statement form (Subject - Predicate - Object) from 1 March to 29 June 20205. We use those revisions to enrich the Wikidata 5 Revision history: https://www.mediawiki.org/wiki/API:Revisions. dump statements. Since we do not know when the challenge's tabular data is generated, we only use the adding operation for all history statements of Wikidata items. In other scenarios, where we know the exact time point of Wikidata, we can reconstruct Wikidata items at this time point by using adding, removing, modifying operations. { Building an entity index: We build this index using a hash table with the entity dump data using multilingual labels, aliases, and identi ers (the identi ers to other sources). In total, the fuzzy entity search index about 150 million entity names for 87 million items of Wikidata. { Building a statement index: we use a sparse matrix to build an index for Wikidata statements. To be simple, we only encode the item statements (item - property - item) and ignore the statements' property information. In the general case, we can also index the literal statements and properties into the sparse matrix. Overall, we index around 500 million statements. 2.4
In this step, we perform entity candidate generation for each target cells using the fuzzy entity search, and two target cells in the same rows using the fuzzy statement search. Figure 3 depicts the semantic annotations of the table of 00KKIZPQ in the round 3 data. We use this table as an example to describe the two following searching module.
col0 V*!AY Psc col1 -4.593 col2 Pisces col3 Fig. 3. Semantic Annotations of the table of 00KKIZPQ in the round 3 data A cell search In this searcher, we perform a fuzzy entity search on the entity index. Given a table, this searcher returns a ranking list of relevant entities ranked with an edit distance, speci cally Levenshtein distance. We rst start with two edits; if the searcher does not have answers, the number of edits is gradually increased to a maximum of six edits. For example: in Table 3, we have four queries as two misspelling queries: \V*!AY Psc", and \SDSS J153509.57+360054.5". This fuzzy search returns the correct answers for the two misspelling queries as Q85702771 (V* AY Psc) and Q81115852 (SDSS J152509.57+360054.5). This searcher achieves coverage of 99.89% on average when performing entity lookup for table cells on SemTab 2020 datasets.
Two cells search We design this searcher to handle the ambiguity of table
cells. We assume a logical relation equivalent to a statement between two cells
of a table row. Therefore, we perform the two cells' search on the target cells in
the same rows. The rst cell is in the core attribute column, and the second cell
is in the remaining columns. We ignore the rows do not have enough two target
cells. This idea is inspired by our novel idea of entity-entity column matching in
MTab [
For example: in Table 3, we have two queries: the two cells of row 1 \V*!AY Psc", \Pisces", and row 2 \SDSS J153509.57+360054.5", \Bootes". We rst search one cell then check all combinations between the two respond lists, whereas the statements are available. In the end, we only keep entity candidates at two cells that have a statement available. Regarding the cells in the core attribute column, we concatenate all the rst cell response candidates.
Finally, for each cell that need to be annotated, we priority select the entity candidates from two cells search. If we do not have candidates in the \two cells" searches, we select the candidates from a cell search. 2.5
We perform value matching of the cells in the core attribute with the remaining cells in their corresponding rows in the post processing step. This module performs context similarity calculation between candidate statements and table row values then ranks the entity candidates based on these similarities. Value matching This module applies to each data row of a table. We calculate the similarities between the candidate statements in the core attribute column with other corresponding values in the same row for each table's data row. If many statements have the same similarity score, we select all these statements. We calculate the context similarity of the candidate in the core attribute by taking the average of all statement similarities in the same row. CEA: If the target cells are in the core attribute, we select a candidate with the highest context similarity as a CEA annotation. If the target cells are not in the core attribute, we infer these annotations from CEA results in the core attribute using value matching similarities.
CPA: To get the CPA annotations, we aggregate all properties of statement candidates in the same rows, then using majority voting to select the CPA annotations.
CTA: To get the CTA annotation, we get the direct types from the CEA annotations in a column and vote for the majority types to get CTA annotations.
In the CPA task and CTA tasks, if the system returns many answers for one target annotation, we randomly select one answer as the nal annotation. 3
SemTab 2020 has four rounds, where round 1, 2, 3 were implemented as a form
of AICrowd leaderboard, and round 4 was implemented as a blind setting. There
are ve datasets in total, including the four-round datasets and the Tough Tables
(2T) dataset 6. The four rounds datasets were generated by an automatic dataset
generator [
Table 1 reports the overall results of MTab4Wikidata for three matching tasks (CEA, CTA, and CPA) in SemTab 2020 datasets (the four datasets of four rounds and the 2T dataset). Overall, these results show that MTab4Wikidata achieves impressive performances for the three matching tasks: the 1st rank in the two tasks of CEA and CPA, and the 2nd rank in the CTA task in round 1, 2, 3 and the 1st rank in round 4 and the Tough Tables (2T) dataset.
The details of MTab4Wikidata's performance on the 2T dataset is shown in Figure 5. The overall performance decrease in both tasks of CEA and CTA compared to the four-round datasets. Although the tough tables dataset is more di cult with a high level of table noisiness, our system still performs e ectively. The F1, Precision, and Recall are quite similar in our results because our system tries to make as many annotations as possible. Even though we do not have a corresponding entity in the knowledge graph, we also return the most relevant entities.
TOUGH_MISC TOUGH_HOMO TOUGH_MISC TOUGH_HOMO
Fig. 5. MTab4Wikidata results on the Tough Tables dataset
TOUGH_N0O.9IS6E1 TOUGH_SOR0T.E8D8 0.76 MTab4Wikidata
ALL 0.91 0.75 0.50 0.25 0.62
0.74 0.87 (a) CEA 0.84CTRL_DBP
TOUGH_NOISE1 0.8C3TRL_NOISE2 TOUGH_SORTED 0.66 TOUGH_T2D
TOUGH_MISSP
0.75 TOUGH_NOISE2 0.6 0.72 0.6 f1 precision recall
MTab4Wikidata
ALL
This paper presents an automatic annotation system called MTab4Wikidata to match tabular elements: i.e., cells, columns, relations between columns to Wikidata concepts. In this work, we focus on improving the standard entity search with the fuzzy search and fuzzy statement search to deal with misspelling and ambiguity of table content. The fuzzy search works e ectively and achieves an average of 99.89% recall on the three rounds of SemTab 2020. The statement search also gives a tremendous e cient improvement where it could eliminate non-statements candidates. To this end, MTab4Wikidata wins the rst prize at SemTab 2020.
Acknowledgements This work was supported by the Cross-ministerial Strategic Innovation Promotion Program (SIP) Second Phase, \Big-data and AI- enabled Cyberspace Technologies" by the New Energy and Industrial Technology Development Organization (NEDO).