MTab: Matching Tabular Data to Knowledge Graph using Probability Models

Abstract

This paper presents the design of our system, namely MTab, for Semantic Web Challenge on Tabular Data to Knowledge Graph Matching (SemTab 2019). MTab combines the voting algorithm and the probability models to solve critical problems of the matching tasks. Results on SemTab 2019 show that MTab obtains promising performance for the three matching tasks.

Introduction

Let a table S be a two-dimensional tabular structure consisting of an ordered set of N rows, and M columns. ni is a row of table (i = 1:::N ), mj is a column of table (j = 1:::M ). The intersection between a row ni and a column mj is ci;j is a value of the cell Si;j . In general, the tabular to KG matching problems could be formalized the three sub-tasks as follows.

{ CEA: matching a cell value ci;j into a relevance entity e 2 E. { CTA: matching a column mj into a exact relevance type and its ancestors. { CPA: matching the relation between two columns mj1 and mj2 (j1; j2 2 [1; M ]; j1 6= j2) into a relation r 2 R. 1.2

Assumption

In MTab, we adopt the following assumptions:

Assumption 1 MTab is built on a closed-world assumption. It means that the target KG is completed and corrected.

Assumption 2 The type of input table is vertical relational table. Assumption 3 Input tables are independence, it means there is no sharing information between input tables.

Assumption 4 Column cell values have the same entity types and data types. Assumption 5 The rst row of table (n1) is table header. The column is header of this column, c1;j 2 mj . rst cell of In practice, table headers could have more complicated structures. Headers could available or non-available, be located at the beginning of the table or not, have one rows or multiple rows. In this work, we omit those issues and assume that the table header is located at the rst row. 2

Approach

MTab is built on the joint probability distribution of many signals inspired by the graphical probability model-based approach [ 1 ]. However, MTab improves the matching performance by solving two major problems: { Entity lookup: We found that using only DBpedia lookup (the most popular service) does not usually get relevance entities for non-English queries. Therefore, we perform entity lookup on multiple services (with language parameter) to increase the possibility of nding the relevance entities. { Literal matching: We found that mapping cell values to corresponding values in a KG is less e ective because the corresponding value in KG is rarely equal with a query value. Therefore, with Assumption 4, we adopt literal columns matching to nd a relevance relation (property) and aggregate these signals to enhance MTab performance.

Additionally, we also adopt more signals from table elements, introduce a scoring function to estimate the uncertainly from ranking. Note that, the probabilities in this paper could be interpreted as subjective con dences.

Entity Candidate Estimation

Entity Candidate

ReEstimation

Type Candidate Estimation

Type Candidate

ReEstimation Relation Candidate Estimation Relation Candidate

ReEstimation

Input

Step 2

Step 3

Step 4

Step 5

Step 6

Step 7

Step 1

Text Decoding Language Prediction Data Type Prediction Entity Type Prediction Entity Lookup

Output

CEA Entity Candidates

CPA Property Candidates

CTA Class Candidates 2.1 Framework We design our system (MTab) as 7-steps pipeline (Fig. 2). Step 1 is to pre-process a table data S by decoding textual data, predicting languages, data type, entity type prediction, and entity lookup. Step 2 is to estimate entity candidates for each cell. Step 3 is to estimate type candidates for columns. Step 4 is to estimate relationship between two columns. Step 5 is to re-estimate entity candidates with con dence aggregation from step 2, step 3, and step 4. Step 6, and Step 7 are to re-estimate type and relation candidates with results from Step 5, respectively. 2.2 Step 1: Pre-processing We perform ve processes as follows.

{ Text Decoding: Reading table data has a problem of textual encoding where some characters are loaded as noisy sequences. Loading incorrect encoding might strongly a ect the lookup performance, therefore, we used the ftfy tool [ 2 ] to x all noisy textual data in tables. { Language Prediction: We used the pre-trained fasttext models (126 MB) [ 3 ] to predict the languages for tables (concatenate all table cell values) and each cell in the table. Since table data is not only written in English but also other languages, determining the language of the input query helpful for the lookup tasks. { Data Type Prediction: Next, we perform data type prediction to predict 13 pre-de ned data types of duckling 5 for each cell value in a table ci;j . Those types are about numerical tags, email, URL, or phone number. If there is no tag assigned, we assign this cell type as a text tag. { Entity Type Prediction: For each cell value in a table ci;j , we also perform entity type prediction with the pre-trained SpaCy models [ 4 ] (OntoNotes 5 dataset) to predict 18 entity types. If there is no tag assigned, this cell type is assigned to a text tag. We also manually map from those textual entity types (11 entity types) OntoNotes 5 to some DBpedia classes. 5 Duckling, link: https://github.com/facebook/duckling { Entity Lookup: We search the relevance entity on many services including DBpedia Lookup6, DBpedia endpoint7. Also, we search relevant entities on Wikipedia and Wikidata by redirected links to DBpedia to increase the possibility of nding the relevant entities. We use the language information of the table and cell values as the lookup parameters. If there is any nonEnglish lookup URL, it is redirected to the corresponding English URL. We use 8 as the limit of lookup results. The search query could be each cell value in a table ci;j , or other neighbor cells in the same rows i. 2.3 Step 2: Entity Candidate Estimation In this section, we explain how we estimate the entity candidates. Given a cell value ci;j , we have a set of ranking result lists from lookup services Qci;j . q is a list of ranking of entities ordered by degree of relevance of a lookup service, where q 2 Qci;j . In MTab, we adopted the four services as DBpedia lookup, DBpedia Endpoint, Wikidata lookup, and Wikipedia lookup. However, we can use any services as long as their output is a ranking list of relevance entities.

Denote EQci;j is a set of relevance entities in Qci;j , sqe is a con dence score of an entity e where e 2 EQci;j . The con dence score of entity e is calculated as seQ = max(sqe). sqe is the con dence score of entity e in q, sqe = ranke, where ranke is the ranking index of entity in q. We normalize those entity con dence score to [0; 1], where P r(EQci;j jQci;j ) = 1, P r(ejQci;j ) = PseQ seQ and associate those e2EQci;j scores as the potential probability of entities given lookup results. 2.4 Step 3: Type Candidate Estimation Regarding Assumption 4, we categorize table columns to entity columns and literal columns. We aggregate the data type (Duckling Tags and SpaCy Tags) from each cell in a column using majority voting. If the majority tag is text or entityrelated, the columns is an entity column, else a numerical column. Regarding numerical columns, we perform semantic labeling with EmbNum method [ 5 ] to annotate relations (DBpedia properties) for numerical columns 9. Then, we infer types (DBpedia classes) from those relations.

Numerical Column The set of numerical columns in table S is Mnum. Given a numerical column mj , we use re-trained EmbNum model on DBpedia [ 5 ] to derive embedding vector for the list of all numerical values of the column and then search the corresponding relations from the database of labeled attributes 10. The result qmj is a ranking of relevance numerical attributes in terms of distribution similarity. We also use as the limit for ranking result. The con dence score of a relation r is calculated as srmj = rankr, where rankr is the ranking index of r. These scores are also normalized to a range of [ 0,1 ] to associate the probability of potential of relation for numerical columns P r(rjmj ). 6 DBpedia Lookup, link: https://wiki.dbpedia.org/Lookup 7 DBpedia Endpoint, link: https://dbpedia.org/sparql 8 In MTab, we set = 100 9 We only use EmbNum for those columns have at least 10 numerical values 10 We used all numerical attributes of DBpedia as the labeled data

Next, we use DBpedia endpoint to infer the classes (types) from those relations as Figure 3. Tqmj is a set of inferred types, t denotes a type t 2 Tqmj . Those types will be used for entity columns. The con dence score of types is estimated as srt = max(srMnum ). Then, we normalized those scores to [ 0,1 ] so that P r(TqMnum ) = 1, those con dence scores are associated as the probabilities of type potential P r(tjMnum) given Mnum.

textual column numerical column

EmbNum

Relation Candidates oclc finalPublicationYear DBpeida Ontology: Domains

Type Candidates WrittenWork PeriodicalLiterature

DBpeida Ontology: Subclass of

WrittenWork 1. P r(tjMnum): the probabilities of type potential from numerical columns 2. P r(tjmj ; Qmj ): the probabilities of type potential aggregated from the types of entity lookup for the all cells in column mj ( P r(tjmj ; Qmj ) =

P P r(tjQci;j ) ). We normalized these aggregated potentials and associ;j2mj ciates these as potential probabilities. 3. P r(tjmj ; SpaCymj ): the probabilities of type potential aggregated from SpaCy entity type prediction for the all cell in column mj . We used majority voting and normalized these voting value to [ 0,1 ]. Then, we associate those normalized voting value type potential probabilities. 4. P r(tjc1;j ): the probabilities of type potential given header value of the column mj . We associate the normalized Levenshtein distance as potential probability that a type (DBpedia class) correspond with a header value. The probabilities of type potential is derived from the four signals as P r(tjmj ) = w1P r(tjMnum)w2P r(tjmj ; Qmj )w3P r(tjmj ; SpaCymj )w4P r(tjc1;j ), where w1; w2; w3; w4 are learnable weights. Note that, some probabilities of signals might be 0 or too small, and aggregate those might add too much noise to the nal aggregation. Therefore, if any signal probabilities less than 11, we omit those signals. After aggregation, we also perform normalization for P r(tjmj ) to a range of [ 0,1 ] so that P r(Tmj jmj ) = 1. 2.5 Step 4: Relation Candidate Estimation Given two columns mj1 and mj2 , we estimate the probabilities of relation potential of P r(rjmj1 ; mj2 ). We consider two type of relation between two columns:

Entity column to Entity column and Entity column to non-Entity column. To be simple, we associate the rst entity column is mj1 . If the second column is entity column, we denote it as mje2nt, else mjn2on ent.

Entity - Entity columns P r(rjmj1 ; mje2nt): Given ci;j1 is a cell value of the column mj1 and the row ri, ci;j2 is a cell value of the column mje2nt. We assume that there is a relation between entity candidates of ci;j1 and ci;j2 , therefore we use DBpedia endpoint to nd how many links (relations or properties) between entity candidates of ci;j1 and ci;j2 . The con dence score of relation is calculated as scri;j1 ;ci;j2 = 1 if there is any relation between entity candidates of two columns. Then, we aggregate those scores of all rows to get the candidate score for two columns as srmj1 ;mje2nt = P scri;j1 ;ci;j2 . Then, we normalize those score to a i2[1;N] range of [ 0,1 ] so that P r(Rmj1 ;mje2nt jmj1 ; mje2nt) and associate it as the probability of relation potential of Entity and Entity Columns P r(rjmj1 ; mje2nt). Entity - Non-Entity columns P r(rjmj1 ; mjn2on ent): Given ci;j1 is a cell value of the column mj1 and the row ri, ci;j2 is a cell value of the column mjn2on ent. We estimate the relevance ratio between entity candidates and non-entity value ci;j2 . Given an entity candidate e have pairs of relation(re)values(ve), we compare the non-entity value ci;j2 with all attribute values ve. We select those pairs have ratio larger than . We only compare two values of ci;j1 and ve based on there data types (textual type or numerical type). { For textual values: We use the normalized Levenshtein distance to estimate the relevance ratio between ve and ci;j2 as s(ve; ci;j2 ). { For numerical values: the relevance ratio is calculated as if max(jci;j2 j; jvej) = 0 and jci;j2 if max(jci;j2 j; jvej) = 0 and jci;j2 vej 6= 0 vej = 0 80; > s(ve; ci;j2 ) = <1; >:1

jci;j2 vej max(jci;j2 j;jvej) ; if max(jci;j2 j; jvej) 6= 0 (1) We aggregate all relevance ratio with respect to relations. Then we normalize those aggregated ratio to [ 0,1 ], and associate this as probability of relation potential. P r(rjmj1 ; mj2 ). If the column of mj2 is numerical columns, we also aggregate the re-calculated probability from P r(rjmj2 ) (step 3) as: P r(rjmj1 ; mj2 ; mj2 is numerical) = w5P r(rjmj1 ; mj2 )w6P r(rjmj2 ) (2) where w5; w6 are learnable parameters. 2.6

Step 5: Entity candidate Re-Estimation In this step, we present a method to re-estimate the probabilities of entity candidates P r(ejS). Given a cell Si;j containing a cell value ci;j at row ni, and column mj , we consider these signals from: { P r(ejQci;j ): The entity candidate probabilities given look up results. { P r(ejmj ): The probabilities of entity candidates given their type's probabilities (Step 3). This can be estimated by P r(ejmj ) = max(P r(tejmj ; Qmj )), where te is a type of the entity e. { P r(ejci;j ): The probabilities of entity candidates given the cell value ci;j .

We get the mean ratio of the normalized Levenshtein distance, heuristic abbreviation rules ( rst character of words, titles, dates, time). { P r(ejni; mj1 ): The probabilities of entity candidates given cell values in a row ci;j 2 ni. We do the same procedure as Step 4 to compare all entity values with a cell value, and compute the mean probability for all cell value in a row. P r(ejni; mj1 ) = mean(P r(ejmj1 ; mj2 )), where j1 6= j2.

Overall, the equation is as follows.

P r(ejS) = w7P r(ejQci;j )w8P r(ejmj )w9P r(ejci;j )w10P r(ejni; mj1 ) (3) where w7; w8; w9; w10 are learnable parameters. 2.7 Step 6, 7: Re-Estimate Types and Relations We select the highest probabilities of entity candidates in Step 5 for each cell Si;j to re-estimate types and relations with majority voting. 3

Results

In this paper, we present MTab for the three matching tasks in SemTab 2019.

Novelty: The MTab performance might be explained in part by tackle the two major problems of the three matching tasks. MTab is built on top of multiple lookup services, therefore, it increases the possibility of nding the relevant entities. Additionally, MTab adopted many new signals (literal) from table elements and use them to enhance matching performance.

Limitation: Since MTab is built on the top of lookup services, therefore, the upper bound of accuracy strongly relies on the lookup results. In MTab, it is computation-intensive because of aggregating the con dence signals from many 11 https://github.com/phucty/MTab

References

1. Girija Limaye , Sunita Sarawagi, and Soumen Chakrabarti . Annotating and searching web tables using entities, types and relationships . PVLDB , 3 ( 1 ): 1338 { 1347 , 2010 .

2. Robyn Speer . ftfy. Zenodo , 2019 . Version 5.5.

3. Armand Joulin , Edouard Grave, Piotr Bojanowski, and Tomas Mikolov . Bag of tricks for e cient text classi cation . In EACL 2017 , pages 427 { 431 . ACL, April 2017 .

4. Matthew Honnibal and Ines Montani . spaCy 2: Natural language understanding with Bloom embeddings, convolutional neural networks and incremental parsing . 2017 .

5. Phuc Nguyen , Khai Nguyen, Ryutaro Ichise, and Hideaki Takeda . Embnum: Semantic labeling for numerical values with deep metric learning . In Semantic Technology , pages 119 { 135 , Cham , 2018 . Springer.

6. Oktie Hassanzadeh , Vasilis Efthymiou, Jiaoyan Chen, Ernesto Jimenez-Ruiz, and Kavitha Srinivas. SemTab2019: Semantic Web Challenge on Tabular Data to Knowledge Graph Matching - 2019 Data Sets , October 2019 .

7. Ziqi Zhang . E ective and e cient semantic table interpretation using tableminer+ . Semantic Web , 8 ( 6 ): 921 { 957 , 2017 .

8. Kyosuke Nishida , Kugatsu Sadamitsu, Ryuichiro Higashinaka, and Yoshihiro Matsuo . Understanding the semantic structures of tables with a hybrid deep neural network architecture . In AAAI , pages 168 { 174 , 2017 .

9. Oliver Lehmberg and Christian Bizer . Stitching web tables for improving matching quality . Proc. VLDB Endow ., 10 ( 11 ): 1502 { 1513 , August 2017 .

10. Dominique Ritze . Web-scale web table to knowledge base matching . PhD thesis , Mannheim, 2017 .