On Data Engineering and Knowledge Graphs - A holistic, smarter approach to data enrichment

Ayala Hernández, Daniel

On Data Engineering and Knowledge Graphs - A holistic, smarter approach to data enrichment

Ayala Hernández, Daniel

Published: 2020-10-02
Repository: idus.us.es
Language: en

Abstract

The recent years have seen an increased interest in the development of large, structured data sources that allow the application of algorithms for tasks such as question answering or product recommendations. This has popularized the use of and research about knowledge graphs, which store information as a graph where nodes represent entities with attributes and edges represent relations between them. The creation of a large knowledge graph is not trivial, since it may require the use of data engineering techniques such as integration of data from several heterogeneous sources or the completion of missing knowledge. These take an initial knowledge graph and enrich it with additional facts. Integrating heterogeneous sources involves integrating external data into a local schema, which can be done by labelling external data with known classes (semantic labelling), or finding equivalences between the external schema and the local one (matching). This is usually done by means of similarity metrics or measurements about the format or values of data. Existing proposals use a limited set of features that may in some cases be insufficient to identify two concepts as equivalent or different, which motivates the design of new, more sophisticated features. Completing knowledge graphs involves guessing data that is missing in a knowledge graph, such as entity classes or relations between entities. Guessing missing edges can be seen as a classification problem in which candidate edges are classified as true or false. This is an error-prone process in which a badly trained technique could introduce a great amount of incorrect knowledge into the graph. Therefore, the creation of resources for supervised training and evaluation of such techniques is crucial. In order to make contributions to the state of the art in these fields (data integration and completion), we have developed methods and tools for three specific tasks: semantic labelling, property matching, and evaluation of knowledge graph edge completion techniques. Our contributions focus on the use of supervised data engineering, which is of particular relevance given the recent developments in the field of machine learning. Our evaluation shows that our methods achieve results that are significantly better than those of the studied baselines thanks to the use of novel groups of features which could be integrated into existing techniques. These results are expounded in detail in the publications that we present as fruits of our research.

Full text

ONDATA ENGINEERING AND KNOWLEDGE GRAPHS AHOLISTIC,SMARTER APPROACH TO DATA ENRICHMENT DANIEL AYALA HERNÁNDEZ Doctoral thesis Supervised by Dr. David Ruiz and Dr. Inma Hernández Universidad de Sevilla July 2020 ACKNOWLEDGEMENTS i Me gustaría agradecer la realización de esta tesis en primer lugar a mis padres, que con su apoyo continuo durante 4 años y su ayuda en todo lo que estaba en sus manos han hecho este momento posible. También querría agradecer la tutoría y dirección de David Ruiz e Inma Hernández, que me han permitido lidiar con los muchos obstáculos que ha habido. Por último querría agradecerle a Rocío su presencia, apoyo incondicional y alegría continua que hacen que todo esto merezca la pena. ii RESUMEN iii En los últimos años ha habido un aumento en el interés por desarrollar grandes repositorios de datos estructurados que permiten la aplicación de algoritmos para tareas como el dar respuestas a preguntas de forma automática, o la recomendación de productos. Esto ha popularizado el uso de y la investigación sobre grafos de conocimiento, que almacenan información como un grafo en el que los nodos representan a entidades con atributos, y las aristas representan relaciones entre ellas. La creación de un grafo de conocimiento de tamaño considerable no es trivial, ya que puede requerir la aplicación de técnicas de ingeniería de datos como la integración de datos de varias fuentes heterogéneas, o el completado de conocimiento ausente en el grafo. Estas toman un grafo de conocimiento inicial y lo enriquecen con datos adicionales. Integrar fuentes heterogéneas involucra integrar datos externos en un esquema local, algo que puede hacerse etiquetando datos externos con clases conocidas (etiquetado semántico), o encontrando equivalencias entre el esquema externo y el local (emparejado). Normalmente, esto se hace usando métricas relacionadas con el formato o los valores de los datos. Las propuestas existentes usan un conjunto de características reducido que en algunos casos puede ser insuficiente para identificar a dos conceptos como equivalentes o diferentes, lo que motiva el diseño de nuevas características más sofisticadas. Completar grafos de conocimiento involucra averiguar qué datos faltan en un grafo de conocimiento, como clases de entidades o relaciones entre ellas. Inferir aristas puede ser visto como un problema de clasificación in el que las aristas candidatas son clasificadas como verdaderas o falsas. Este es un proceso susceptible a fallos en el que una técnica mal entrenada podría introducir una gran cantidad de conocimiento erróneo en el grafo. Por tanto, la creación de recursos para el entrenamiento supervisado y evaluación de estas técnicas es crucial. Para contribuir al estado del arte en estos ámbitos (integración de datos y completado de grafos), hemos desarrollado métodos y herramientas para tres tareas específicas: etiquetado semántico, emparejamiento de propiedades, y evaluación de técnicas de completado de aristas en grafos de conocimiento. Nuestras contribuciones se centran en el uso de ingeniería de datos supervisada, que es de particular relevancia dados los avances recientes en el ámbito del aprendizaje automático. Nuestra evaluación muestra que nuestros métodos obtienen resultados significativamente mejores que las técnicas base estudiadas gracias al uso de grupos novedosos de características que podrían ser integradas en técnicas existentes. Estos resultados se muestran en detalle las publicaciones que presentamos como frutos de nuestra investigación. iv ABSTRACT v The recent years have seen an increased interest in the development of large, structured data sources that allow the application of algorithms for tasks such as question answering or product recommendations. This has popularized the use of and research about knowledge graphs, which store information as a graph where nodes represent entities with attributes and edges represent relations between them. The creation of a large knowledge graph is not trivial, since it may require the use of data engineering techniques such as the integration of data from several heterogeneous sources or the completion of missing knowledge. These take an initial knowledge graph and enrich it with additional facts. Integrating heterogeneous sources involves integrating external data into a local schema, which can be done by labelling external data with known classes (semantic labelling), or finding equivalences between the external schema and the local one (matching). This is usually done by means of similarity metrics or measurements about the format or values of data. Existing proposals use a limited set of features that may in some cases be insufficient to identify two concepts as equivalent or different, which motivates the design of new, more sophisticated features. Completing knowledge graphs involves guessing data that is missing in a knowledge graph, such as entity classes or relations between entities. Guessing missing edges can be seen as a classification problem in which candidate edges are classified as true or false. This is an error-prone process in which a badly trained technique could introduce a great amount of incorrect knowledge into the graph. Therefore, the creation of resources for supervised training and evaluation of such techniques is crucial. In order to make contributions to the state of the art in these fields (data integration and completion), we have developed methods and tools for three specific tasks: semantic labelling, property matching, and evaluation of knowledge graph edge completion techniques. Our contributions focus on the use of supervised data engineering, which is of particular relevance given the recent developments in the field of machine learning. Our evaluation shows that our methods achieve results that are significantly better than those of the studied baselines thanks to the use of novel groups of features which could be integrated into existing techniques. These results are expounded in detail in the publications that we present as fruits of our research. vi Figure 1: Summary of this thesis. Thanks for the drawing, Jimena! vii viii CHAPTER 1. INTRODUCTION 1.1 CONTEXT Data Engineering is a research area whose goal is to devise methods, algorithms and systems for acquisition, modelling, design, exploitation and maintenance of data [48]. From the beginning, data engineers tried to find the optimal way to store and organise data, being this one of their biggest concerns; however, it is now, with the consolidation of big data, that this concern is more present than ever. Depending on how data is presented, it can be classified as structured or unstructured. Structured data is presented as a set of entities with explicit properties, classes, and relationships between them, as opposed to unstructured data, which is presented without well-defined parts of interest [40]. For example, a plain text document describing a product would be unstructured data. A website with information about the product could be considered semi-structured because of the tree-like layout of the page elements. A database entry formally identifying the product and each of its properties would be fully structured. The most typical elements of structured data are entities, classes, and properties [14]. Figure §1.1 shows a toy example of two knowledge graphs with structured information. An entity is a representation of something that can be uniquely identified, sometimes with an attached name such as "CANON 1000D". A class denotes a semantic category of the entities is is attached to, such as "camera", "Eaccessory", or "user". A property is a type of attribute of entities, denoted by a name, such as "price" or "resolution". The value of a property can be another entity, in which case it is called an object property in some contexts, or a piece of text, in which case it is called a data property. A set of entities, classes, and properties is usually referred to as a schema or ontology depending on the context. Structured data can be easily handled by programs in order to analyze it or make decisions, which has motivated the development of initiatives to generate and share structured data. This recent interest is made evident by the increase of popularity of knowledge graphs (KGs), which are vast repositories of structured information whose growth over the past years can be related to that of the Web of Data. Large companies such as Google, Microsoft, Facebook, Netflix or Amazon are using knowledge graphs to store and process the data on which they base their business models [33,41]. Furthermore, large volumes of information about different domains can be found in some well-known open KGs such as DBpedia [20], NELL [27], GeoKG [47], Freebase [7], or Scholarlydata.org [31]. A Knowledge Graph is usually constructed by extracting in- 4 1.1. CONTEXT ^ŽƵƌĐĞϮ ^ŽƵƌĐĞϭ EKEϮϬϬϬ;ĐĂŵĞƌĂͿ ZĞƐŽůƵƚŝŽŶ “15 DW ” WƌŝĐĞ “500 Φ ” ŝƐĐƉƌŝĐĞ “400 Φ ” /^K “100 Ͳ 20000” E/<KEϱϬϬ;ĐĂŵĞƌĂͿ ZĞƐŽůƵƚŝŽŶ “13 DW ” WƌŝĐĞ “400 Φ ” /^K “500 Ͳ 12000” ŽŽŵ “ ǆϰ ” ĐĐĞƐŽƌǇϬϭ;ĂĐĐĞƐŽƌǇͿ EĂŵĞ “ ĂŶŽŶůĞŶƐ ” &> “18 Ͳ 55 ŵŵ ” /ƐŵĂĐƌŽ “ EŽ ” ĐĐĞƐƐŽƌǇϬϯ;ĂĐĐĞƐŽƌǇͿ EĂŵĞ “ EŝŬŵĂĐƌŽ ” &> “50 Ͳ 200 ŵŵ ” /ƐŵĂĐƌŽ “ zĞƐ ” WƌŝĐĞ “150 Φ ” hƐĞƌϬϮ;ƵƐĞƌͿ EĂŵĞ “ ZŽĐşŽ ” EKEϭϬϬϬ;ĐĂŵĞƌĂͿ ZĞƐŽůƵƚŝŽŶ “10 DW ” WƌŝĐĞ “300 Φ ” /^K “500 Ͳ 9000” ĐĐĞƐŽƌǇϬϮ;ĂĐĐĞƐŽƌǇͿ EĂŵĞ “ ĂŶŽŶĨŝůƚĞƌ ” WƌŝĐĞ “5.95 Φ ” ďƵǇƐ ďƵǇƐ ďƵǇƐ ŝŶĐůƵĚĞƐ ŝŶĐůƵĚĞƐ ŝŶĐůƵĚĞƐ ďƵǇƐ ŝŶĐůƵĚĞƐ hƐĞƌϬϭ;ƵƐĞƌͿ EĂŵĞ “ ĂŶŝĞů ” ϭϬϬϬ DĞŐĂƉŝǆĞůƐ “10” WƌŝĐĞ;ĞƵƌŽͿ “300 Φ ” DŝŶŝƐŽ “500” DĂǆŝƐŽ “9000” >ĞŶƐ “18 Ͳ 55” EKE;ĐŽŵƉĂŶǇͿ EĂŵĞ “ ĂŶŽŶ/ŶĐ ” /ŶĚƵƐƚƌǇ “ ĞůĞĐƚƌŽŶŝĐƐ ” ,Y “ QƚĂdŽŬǇŽ:ĂƉĂŶ ” 'ŽƌŽzŽƐŚŝĚĂ;ƉĞƌƐŽŶͿ EĂŵĞ “ 'ŽƌŽzŽƐŚŝĚĂ ” EĂƚŝŽŶĂůŝƚǇ “ :ĂƉĂŶ ” ^ĂďƵƌŽhĐŚŝĚĂ;ƉĞƌƐŽŶͿ EĂŵĞ “ ^ĂďƵƌŽhĐŚŝĚĂ ” EĂƚŝŽŶĂůŝƚǇ “ :ĂƉĂŶ ” dĂŬĞŽDĂĞĚĂ;ƉĞƌƐŽŶͿ EĂŵĞ “ dĂŬĞŽDĂĞĚĂ ” EĂƚŝŽŶĂůŝƚǇ “ :ĂƉĂŶ ” /ƐͺĨŽƵŶĚĞƌ /ƐͺĨŽƵŶĚĞƌ /ƐͺĨŽƵŶĚĞƌ ,ĂƐͺŵĂŶƵĨĂĐƚƵƌĞƌ ŚĂƐͺĨŽƵŶĚĞƌ Figure 1.1: Knowledge graph toy example. Dotted lines denote missing facts formation from different sources both structured and unstructured, providing it with semantics, and representing it by means of nodes (corresponding to entities) and edges between them (corresponding to properties), also known as triples in this context. Existing proposals build knowledge graphs by hand (based on knowledge from experts in the domain [26] or crowdsourcing approaches [7,11]), or from information automatically extracted from structured [20,23] or semi-structured [27] information 5 CHAPTER 1. INTRODUCTION sources applying heuristics, semi-automated or automated processes. In some cases, the process behind a graph creation is kept secret by its owner for trade secrecy, as happens with Google’s Knowledge Graph. Curating a graph by hand takes a significant amount of human resources, which are not available in most cases Consequently, there is a large amount of research dedicated to building of KGs in an automated way. Be it through manual curation or automatic techniques, the first version of a knowledge graph may be incomplete, with missing entities, properties or relations. Therefore, there is also interest in developing techniques for enriching a KG with additional, missing facts. Among the several ways to enrich a knowledge graph, we have focused on two of them: data integration and KG completion through data engineering. The work on these tasks was done as part of work packages in projects TIN2013-40848-R (objective 1) and TIN2016-75394-R (packages 2 and 4) Data integration [10] seeks to unify several heterogeneous sources of data into a single collection. Knowledge graphs provide partial views of the real world [30], often overlapping to a certain degree, which means that integrating them helps us achieve both bigger graphs and more complete, trustable data [4]. For example, if we wished to integrate thw two graphs in Figure §1.1, we would have to find the equivalence between "CANON 1000D" and "1000D", as well as their properties. Integration involves several tasks. The first step towards integrating new entities into a KG is to identify what their classes and properties are, so that they can be properly fused with the corresponding entities from the KG. The problem is that different sources usually define different classes and properties for the entities in their local schemas, or may not even have a schema at all. For example, in Figure §1.1, property "Resolution" in Source 1 corresponds to "Megapixels" in Source 2, "ISO" corresponds to both "Min iso" and "Max iso", and class "camera" has no equivalent. If the external data sources lack a schema with classes and properties, each new entity and its attributes have to be labelled with classes and properties defined in the local schema. This process is known as semantic labelling [38], since it consists in endowing information with known labels, thus giving it semantics. If the external data sources have a well-defined schema, then integrating information requires finding alignments between the external classes and properties and the local ones, which is known as schema matching [6]. In both cases, performing the tasks by hand is burdensome for the user, which justifies the development of techniques to automatically infer types or alignments. In the literature, these techniques are usually based on the detection of similarities between class names or textual formats [8,13,36,38]. For example, we could infer that "300€" is a price because of its numeric format and the presence of a symbol. We could also infer 6 1.2. PROBLEM that properties "Price" and "Price(euro)" match because of the textual similarity of their names. Knowledge graph completion seeks to add missing triples to an existing KG by inferring them [34]. KGs often contain incomplete information, either because such information was not present in the source, or because it was not correctly extracted and semanticised [15]. Therefore, a posterior refinement process can be used to complete the graph adding the missing entities and triples. Our focus is on completing triples, that is, adding missing edges between entities in the graph. The addition of missing edges can be seen as a binary classification problem in which we classify a candidate triple that is not present in the graph as true or false. This classification is usually based on one of two main trends: embeddings [17,22,42], or graph-based features [16,19,24]. Embeddings are representations of nodes and possible relations between them as numeric vectors that are fine-tuned so that true edges minimize a distance function. Graph-based features are measurements made from the entities involved in the potential triple, and may be related to the number of existing paths connecting the entities, their neighbours in the graph, etc. For example, in Figure §1.1, dashed links represent missing relations between entities. We could infer the fact <Canon 1000D, includes, Accessory 02>because other similar entities include the same accessory. 1.2 PROBLEM While there is a large corpus of research in the fields of data integration and knowledge graph completion, there are some widespread shortcomings in the state-of-the- art. With regards to data integration, most techniques are based on lexical similarity of textual values (JARO distance of class and property names, data instances, etc.) [25, 36,38], sometimes in a process that takes into account the structure of the information in one way or another [28,49]. The use of external knowledge bases such as DBpedia as the set of known classes used as reference is very popular [28,39,46]. To perform semantic labelling, measurements are taken from the element to be labelled and compared to the measurements of elements with known labels in order to find the label that seems to fit the observations the most. This study of similarity to known labels can be done through heuristics or supervised classification techniques. For example, we could compare "300€" with examples of properties such as "Price", "Zoom", or "Resolution" using measurements such as the number of digits, the cosine similarity, etc. The prob- 7 CHAPTER 1. INTRODUCTION lem is that certain labels have very similar formats. For example, labels "Price" and "Disc Price" would follow the exact same textual format, and even the distributions of their numerical values would be very similar. In this and similar cases, the information provided by the popular features is not enough, and a more sophisticated approach with a larger features catalogue would be needed. Furthermore, while there are several proposals of different features to use for classification, little work has been done to explore the potential of different classification techniques. Existing proposals rely on traditional techniques such as bayesian classification [46] or logistic regression [36]. A similar problem is common in the context of schema matching. Schema matching is largely based on the textual similarity of class or property names [5,6,12,32,37]. For example, string edit distance measures can be used to easily match "Price" and "Price(euro)". While a high textual similarity is usually a good indicator of a match, low similarity does not imply there is not a match, since the difference in names can be caused by synonyms, abbreviations, different technical units, or numeric values, making it difficult to find matches with standard techniques that rely on string similarity metrics. For example, properties "Resolution" and "Megapixels" should be matched even though their names are quite different. This problem becomes more prominent when matching involves many sources, since then the heterogeneity of names for the same concept increases. Because of their nature, properties seem to be more prone to some of these factors like abbreviations and units than, for example, class names. This hypothesis is supported by the fact that the effectiveness of matching techniques has been reported to be lower when applied to properties than when applied to classes [9]. To try to solve this problem, many techniques try to use similarity measurements based on external knowledge bases such as WordNet [21], which may contain synonyms or descriptions of classes/properties that can provide information beyond their basic name. However, these knowledge bases are hard to create and use, and do not usually contain information about domain-specific terms. Therefore, there is a need to develop a more sophisticated technique that is not limited to the textual similarity of the names in order to be less susceptible to name heterogeneity. Finally, when it comes to graph completion, there is a lack of an unified framework for describing the evaluation setup. The evaluation of knowledge graph completion involves selecting an existing knowledge graph, splitting it into training and testing, and generating, if necessary, a set of negative examples. It is a process with a high number of possible variations that are not trivial to define and implement. Existing proposals take different considerations into account when creating the evaluation datasets, and describe them in a different manner [16,17,24,43]. Furthermore, evaluating the results 8 1.3. OBJECTIVES of several techniques involves selecting appropriate metrics and computing statistical tests to measure the differences between each pair of techniques. Currently, there is no tool to assist in this process, which is why we can find a high heterogeneity in the state-of-the-art proposals regarding the measures, datasets and configurations used in their experimental evaluation. 1.3 OBJECTIVES Considering the former preliminaries about the context of our research, our work hypothesis is the following: The surge of interest in knowledge graphs as a way to store and use structured information has resulted in the need to develop techniques to build and enrich these knowledge graphs. Companies like Google or Facebook use massive knowledge graphs whose manual building is cumbersome and time-consuming. Therefore, research in the field of data engineering is needed to develop methods for building and enlarging knowledge graphs. Two of the most popular ways to do so are the integration of heterogeneous sources of data and the inferring of facts from a given graph. Specific tasks that are involved in this process are semantic labelling, property matching, and knowledge graph completion, all of which are of great importance in the current day. From this hypothesis, we define our thesis as follows: It is possible to develop methods and tools oriented towards the enrichment of knowledge graphs through data integration and knowledge graph completion using Data Engineering techniques focused on the application of machine learning. Specifically, it is possible to develop a semantic labelling proposal with a graphical interface and a comparison of several existing classification techniques; to develop a property matching proposal; and to develop evaluation tools for knowledge graph completion proposals that cover the entire evaluation workflow. Our focus, when possible, is on the the use of machine learning techniques that use information in a novel way. Next, we describe the specific objectives of this thesis. Each objective corresponds to one of the topics of interest. 9 CHAPTER 1. INTRODUCTION 1.3.1 Semantic labelling [SL] The state of the art semantic labelling proposals leave room for improvement when it comes to the features used to perform labelling. As we mentioned, there is a need to devise new features that are able to differentiate highly similar cases to remove ambiguity, and therefore our objective is to devise such proposal. We identified the following sub-objectives: SL-1 Design a semantic labelling proposal that uses novel features able to remove ambiguity during labelling. SL-2 Build a tool that makes the aforementioned proposal usable through a graphical interface that eases the creation of models and testing. SL-3 Identify the best classification strategy for the creation of semantic labelling models. 1.3.2 Property matching [PM] While there is an overall need for smarter schema matching that, the problem is more prominent with properties, where there is higher name heterogeneity for matching properties. Therefore our objective is to develop a property matching proposal that can overcome name heterogeneity without relying on external knowledge bases such as WordNet. 1.3.3 Knowledge graph completion [KGC] Since there are no standardised workflows or resources for the evaluation, our objective is to create a suite for the evaluation of knowledge graphs defining and covering the entire evaluation workflow. We have identified the following sub-objectives: KGC-1 Build a tool for the creation of evaluation datasets for knowledge graph completion, including variation points for every step. KGC-2 Create a set of pre-computed evaluation datasets following reasonable strategies. KGC-3 Build a tool for computing evaluation metrics from the results of several KG completion techniques. 10 2 SUMMARY OF THE RESULTS 11 In this chapter we describe the solutions that resulted from our research to address the identified problems. Regarding semantic labelling, we present TAPON, TAPON-MT, and our study of classification techniques. Regarding data property matching, we present LEAPME. Regarding knowledge graph completion, we present AYNEC. The work on these proposals has resulted in several publications in high ranking journal and conferences. Section §2.1 summarises our results with traceability to the objectives we presented, along with evaluation results when applicable. Section §2.2 comments on the results we present. CHAPTER 2. SUMMARY OF THE RESULTS 2.1 RESULTS 2.1.1 Semantic Labelling Our solution for [SL-1] is TAPON [1]. TAPON is a new two-phase, supervised, machine learning semantic labelling technique. Our main contribution is the application of novel features in two phases that go beyond simple text-based and structural features. In the first phase (the hint-free phase), we compute simple features that can be computed on attributes or the structure of the entities, such as the letter density or the number of properties they have. These features are used to obtain a set of temporary labels we call hints. In the second phase (the hint-based phase), the presence of hints allows us to compute, in addition to the former features, novel features that model the relationships between classes. After computing these features, we refine the labels with the added information. Figure §2.1 shows this workflow. Compute hint-free (HF) features Apply hint-free model Compute hint-based (HB) features Apply hint-based model Dataset 1 2 3 1 0.5 2 Attr 1 1 0.5 2 Attr 1 1 0.5 2 Rec 1 Features (HF) 1 : author 2 3 : name : location Hints 1 0.5 2 0 0.4 Rec 1 Features (HF+HB) 1 0.5 2 0 0.4 Rec 1 1 0.5 2 1 -1 Rec 1 1 : publisher 2 3 : name : location Final labels Hint-free model Hint-based model ✓ ✗ ✓ ✓ ✓ ✓ Figure 2.1: Workflow of TAPON Regarding models, our technique uses one-vs-all classifiers where the aggregation of the binary classifiers is done by means of an additional multiclass classifier that uses the outputs of the binary classifiers as features. Each binary classifier returns the probability of an instance belonging to its class. The multiclass classifier combines their outputs to infer a final label. Our hypothesis is that the hints and the information related to relationships between classes (included through the additional features) help create an improved model that can be used to provide more accurate labels. For example, in the first phase two properties, "$9.95" and "$4.95" could both be labelled as "Price". In the second phase, a hint-based feature could measure how the first one seems to be near a lesser price, while the second one is near a greater price. This information should be enough to refine the second label to "Disc. Price". 12 2.1. RESULTS In order to empirically prove this hypothesis, we have carried out experiments in which TAPON was used to label a number of realworld datasets, comparing its performance with the performance of labelling techniques based on the techniques by Ramnandan et al. [38], Pham et al. [36], and Neville and Jensen [29], as well as the features catalogues defined by Kushmerick [18] and Soru and Ngomo [44]. The experiments consisted in labelling the test fraction of the data in a dataset created by merging the data from 10 linked data repositories, with a total of 24 entity classes and 53 property classes. Figure §2.2 shows the results of our evaluation. Baselines n which hint-based features have the "-HB" suffix. Neville RamPh am TAPO N-HB 0.00 0.25 0.50 0.75 1.00 P R F1 A P R F1 A P R F1 A P R F1 A Value Measu res Precision Recall F1 Accuracy (a) Comparison with other algorithms Kush Kush−HB Soru Soru−HB TAPON−HB 0.4 0.6 0.8 1.0 P R F1 A P R F1 A P R F1 A P R F1 A P R F1 A Value Variables Precision Recall F1 Accuracy (b) Comparison with other features catalogues Figure 2.2: Evaluation results for TAPON Our solution for [SL-2] is TAPON-MT [2]. TAPON-MT is a new semantic labelling framework whose architecture has been devised with applicability and customisation in mind, and is based on the two-phase classification workflow of TAPON. Applicability implies that TAPON-MT is domain independent and does not rely on specific conditions. Customisation implies that the architecture and workflow of our framework give the possibility to integrate a wide variety of features and classification techniques. This is achieved thanks to the definition of concepts such as "featurable" or "features group", which allow us to implement complex features. 13 CHAPTER 2. SUMMARY OF THE RESULTS B r2 A C r1 B B r2 D C r1 F B r2 A C r1 B B r2 D C r1 F B r2 A C r1 B B r2 D C r1 F B r2 A C r1 B B r2 D C r1 F -1 1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 1 1 1 Splitting A B C F D E r2 r1 r2 r1 r3 r3 Original graph A B C F D E r2 r1 r3 Training set (pos) A B C F D E r2 r1 r3 Testing set (pos) Negatives generation r4 r5 Preprocessing A B C F D E r2 r1 r2 r1 r3 r3 Processed graph A B C F D E r2 r1 r3 Training set (pos/neg) A B C F D E r2 r1 r3 Testing set (pos/neg) r3 r1 r2 r2 r3 r1 Triple classification Statistical analysis P-values : (T1, T2): 0.02 (T1, T3): 0.01 (T2, T3): 0.13 ... T1 T2 T3 T4 AYNEC-DataGen tool AYNEC-ResTest tool AYNEC-Datasets T1 T2 T3 T4 Techniques to eval. Relations to eval. r1 r2 TP FP FN TN TP FP FN TN TP FP FN TN Tech Rel P R F1 T1 r1 0.5 1.0 0.7 T2 r1 - 0 - ... ... ... ... ... Figure 2.7: Knowledge graph completion workflow. While the main output are the files corresponding to the training and testing sets, DataGen also produces several additional items that provide useful information for the evaluation process. These include files listing the relations and entities in the graph along with information about their frequency and degree, an interactive visual summary with the aforementioned frequencies and degrees as shown in Figure §2.8, a file with each identified pair of inverse relations, and a file in gexf format with the entire dataset, including the negatives and positives of both training and testing sets. Our solution for KGC-2 is AYNEC-Datasets, a set of evaluation datasets generated with DataGen to standarise evaluation. The original graphs used to generate datasets were WN18, WN11, FB13, FB15K, and NELL. We configured DataGen to remove relations with a single occurrence, use 20% of the graph for testing, and generate one negative per positive by randomly replacing the target of each triple with a random entity. For FB15K and NELL, given their large number of relations, we also generated reduced datasets in which inverse relations were removed, and we set an accumulated relation frequency threshold of 95%. Our solution for KBC-3 is AYNEC-ResTest. ResTest takes as input a file with the results of several techniques when applied to each triple in the testing set, computes metrics for each technique and performs pairwise comparison by using statistical significance tests. AYNEC-ResTest computes, for each technique and relation, the confusion matrix. These matrices are used to compute metrics per technique and relation: precision, recall, and F1. ResTest also computes ranking-based metrics: MAP and MRR, as 20 2.2. DISCUSSION OF THE RESULTS Figure 2.8: AYNEC-DataGen visual summary. well as the micro and macro averages of the former metrics. Regarding statistical significance, ResTest applies both the paired Wilcoxon signed rank test and the non-paired Kolmogorov-Smirnov test. These tests are computed for each threshold, each metric, and each pair of techniques. 2.2 DISCUSSION OF THE RESULTS 2.2.1 Semantic Labelling As can be observed in Figure §2.2, the results of TAPON are significantly better than those of the baselines. Furthermore existing features catalogues achieve better accuracy when we added the hint-based features, showing that hint-based features could 21 CHAPTER 2. SUMMARY OF THE RESULTS be a good addition to several semantic labelling proposals beyond our own. However, depending on the use scenario, hint-based features should be devised accordingly. If we want to label data form an external source, the user may want to avoid features that are too specific. For example, instead of feature "number of siblings labelled as ’Price’", the user could use the binary feature "presence of at least one neighbour labelled as ’Price’". TAPON-MT can be used to test said features under different scenarios, such as training and testing with different datasets from the same domain that are known to share some classes. The model visualisation and the similarity matrix can help diagnose the behaviour of the classifier (e.g. why some data are always classified with the same class). Currently, TAPON-MT supports the visualisation of random forest classifiers, since they are particularly easy to represent and interpret. Other models would require additional visualisation modules. Regarding classification techniques, Figure §2.4 shows that neural networks achieve significantly better accuracy than the other techniques, mainly in the "ALL" scenario, which is the most challenging one due to the increased number of classes. While there may be potential for the application of further deep learning techniques, so far we have not identified more complex layers types that fit the nature of the features used for semantic labelling (without regionality or sequences). 2.2.2 Property Matching Figure §2.5 shows that LEAPME achieves better results than the baselines. While unsupervised techniques achieve an almost perfect precision, their recall is quite low. The technique by Nezhadi et al. and LSH achieve a lower accuracy, the difference being more noticeable in the headphones, phones, and tvs scenarios, which use smaller, lower quality datasets. SemProp achieves similar results to LEAPME(emb) in the cameras dataset, but only when the amount of training data is low. It is remarkable how the addition of embeddings is crucial when it comes to achieving high accuracy. While precision slightly increases, recall improves dramatically. However, this improvement requires a decent amount of training data to reach its potential, which may be problematic given that obtaining training data is usually cumbersome. However, Figure §2.6 shows that there is potential for an universal classifier that has bee pre-trained with data from other domains from the one it is being applied to, 22 2.2. DISCUSSION OF THE RESULTS thus removing the need to obtain training data for a specific scenario. In both cases, the results of LEAPME greatly depend on the quality of the data used for training (that is, its size and variety of examples). In this regard, there is a crucial need for the development of more multi-source data property matching datasets, since they are useful not only for evaluation, but for training a universal classifier that could even be plugged in existing proposals as an additional matcher. 2.2.3 Knowledge Graph Completion As Figure §2.7 shows, AYNEC overs the entire knowledge graph completion evaluation workflow but the application of completion techniques, since different techniques can be completely different from each other. The difficulty when it comes to evaluation is covering the different trends that exist for KG completion. Standard techniques classify candidate triples as true or false. In this case, AYNEC can be applied normally, generating a fixed number of negatives per positive. Other techniques work in an "answer-to-query" fashion: they receive the relation and the source or target of a triple, and generate a ranking with the most likely entities for the unknown part. In this case, the dataset would be created with no negatives, so that it is understood that any triple not present in the training set is a negative. When computing ranking-based metrics, AYNEC-ResTest will group triples per source/target and relation in order to obtain the ranking of each query. While there is an ongoing controversy about what kind of evaluation and metrics are more appropiate [35,45], AYNEC supports all popular trends. To the best of our knowledge, there is no evaluation variant that could not be covered with current AYNEC configurations. We implemented all the techniques we observed in the state of the art for the generation of negative examples. The most complex one uses random paths to replace the entities of the triple with other entities that are near the original ones so that their neighbourhood is more similar. However, there is no study on whether or not using this technique actually makes a difference when compared to simple replacement of the entities. The datasets in AYNEC-Datasets were generated using reasonable configurations, or following popular strategies when there was no clearly superior option. For example, we generated one negative per positive, which is the most popular choice in the state of the art, as well as being convenient if a ranking-based technique is applied, since the file size is smaller than if several negative examples were generated. 23 CHAPTER 2. SUMMARY OF THE RESULTS 24 PUBLICATIONS PART II 3 LIST OF PUBLICATIONS 27 The results of our work have resulted into several publications that present our research in detail. Table §3.1 lists these publications, which can be found in the next chapters. LEAPME was sent to VLDB’20 and rejected in the second round of revisions. The feedback it received was positive, which guarantees it will be published in a high ranking venue. It has been recently sent to ICDE’20, and is under review. Title Objectives Publication date Journal / Conference Rank TAPON: A two-phase machine learning approach for semantic labelling SL-1 January 2019 Knowledge-Based Systems Q1 (JCR'18 = 5.101) TAPON-MT: A versatile framework for semantic labelling SL-2 July 2019 Information Systems Q3 (JCR'18 = 2.066) A neural network for semantic labelling of structured information SL-3 April 2020 Expert Systems With Applications Q1 (JCR'18 = 4.292) AYNEC: All you need for evaluating completion techniques in knowledge graphs KGC-1,2,3 June 2019 Extended Semantic Web Conference 2019 GGS Class 2 (A) LEAPME: Learning-based Property Matching with Embeddings PM Not published - - Table 3.1: Publications. 28 4 TAPON:A TWO-PHASE MACHINE LEARNING APPROACH FOR SEMANTIC LABELLING 29 Through semantic labelling we enrich structured information from sources such as HTML pages, tables, or JSON files, with labels to integrate it into a local ontology. This process involves measuring some features of the information and then finding the classes that best describe it. The problem with current techniques is that they do not model relationships between classes. Their features fall short when some classes have very similar structures or textual formats. In order to deal with this problem, we have devised TAPON: a new semantic labelling technique that computes novel features that take into account the relationships. TAPON computes these features by means of a two-phase approach. In the first phase, we compute simple features and obtain a preliminary set of labels (hints). In the second phase, we inject our novel features and obtain a refined set of labels. Our experimental results show that our technique, thanks to our rich feature catalogue and novel modelling, achieves higher accuracy than other state-of-the-art techniques. D. Ayala et al. / Knowledge-Based Systems 163 (2019) 931–943 937 such as ensemble classifiers, random forests, logistic regression or neural networks. Since record and attribute classes are disjoint, and a class cannot be shared by both records and attributes, we create separate models for records and attributes, using different feature sets (though they may share features, like feature AR1in Table 1, which can be applied to both attributes and records). Record models are learnt using only feature vectors computed from record instances, whereas attribute models are learnt only from feature vectors computed from attribute instances. Note that this does not prevent record feature vectors from containing features that are based on attributes and vice versa. For example, feature RF3 in Table 2 is only applied to records, but it measures the number of instances in a record that belong to each class, including attribute ones. After the hint-based phase, we can use the resulting labels as hints again, which may possibly alter some of the hint-based features values. Consequently, we might apply the hint-based model again to refine the set of labels by repeating the hint-based phase. This results in an iterative process that continues until the set of labels is stable (or a maximum number of iterations is reached). However, our experiments show that repeating the hint-based phase does not improve the results in a significant way; actually, with some classification configurations, they get worse. This is probably caused by the fact that, after the second phase, hints differ too much from those in the training examples of the second model, which correspond to the labels after one iteration, not two. Some alternatives, such as training the second model with the actual classes as hints, or training further models, could make further iterations more useful, but the thorough study of how each of these alternatives behave is beyond the scope of this paper. Lastly, while we have devised a complete, independent semantic labelling technique, its hint-free phase could as well be replaced by any other existing labelling technique, as long as it provides a label that can be used to compute hint-based features in the hintbased phase. Therefore, our technique is able to integrate state- of-the-art labelling techniques, such as Ramnandan et al. [14]’s or Neumaier et al. [10]’s. 2.4. Application example To illustrate our technique, we use as an application example a scenario in which there are two data sources, related to the domains of videogames and books. For the sake of simplicity, the only existing classes are those in Fig. 2. Videogames have a title, a date, a platform and a publisher with a name and a location. Books have a title, a year, a price, and one or more authors with a name and a nationality. Some of the classes, such as the classes schema:schema:VideoGame and schema:Book, are used in structurally identical records. In order to create the models in Fig. 4, first, we create the hintfree model by learning from the feature vectors of the instances in a learning set. We only compute the features in Table 1. Afterwards, we apply these models to label the instances in the learning set (the same instances that were used to learn the hint-free model), endowing them with a hint that allows us to compute the additional features in Table 2 and create the hint-based models. Then, we apply the hint-free model in the hint-free phase to label the instances of a dataset that contains one schema:Video Game record. We initially assign label ?? to every instance to emphasise that their classes are unknown. Since we have applied the hint-free models, we only compute the hint-free features, which may have paremeters that are instanced several times, as is the case with A1. After this phase, the instances are given a label. The labels schema:Book,schema:Name, and schema:author are incorrect, since the actual classes of $C0,$C1, and $C4 are schema:VideoGame,schema:title, and schema:publisher. The incorrect label of $C0 is due to the similarity between classes schema:VideoGame and schema:Book, and the same happens with $C1 (similarity between classes schema:title and schema: name, since they have a similar format) and $C4 (similarity between classes schema:publisher and schema:author, since they are structurally identical). Note that these labels are not the final labels; they are mere hints that are corrected in the next phase. Thanks to the presence of hints, we can compute additional hint-based features and apply the hint-based models in the hintbased phase to correct the former hints. The hint-based models are more complex, and take into account features that help tell the schema:VideoGame and schema:Book classes apart, as well as the schema:name and schema:title classes, and the schema:publisher and schema:author classes. For example, the distance to an attribute of class schema:gamePlatform can help correct all incorrect labels, since in the case of books, such distance is infinite. This reduces similarity between classes and increases the quality of the models, that are now able to correctly label all instances. Note that we create instances for each known class. Some of them will be useful, such as the distance to a platform, while some may not add useful information. 3. Related work Related work includes semantic labelling techniques, as well as other techniques that were not devised with semantic labelling in mind, but that share the same principles as semantic labelling ones, i.e., creating models that provide a probabilistic view of the information. In the particular case of semantic labelling, this probabilistic view is used for classification. Proposals from other areas use it for different purposes, but the models they create are useful and relevant to semantic labelling to the point where some of the techniques can be used for semantic labelling by merely feeding the features they describe to a classifier. For this reason, we study them along with semantic labelling techniques, and refer to them, overall, as information modelling techniques. After surveying the literature, our conclusion is that the existing techniques for information modelling can be broadly classified into hard [25] and soft [4,7,9–15] techniques. The former learn a structural model for a dataset, that is, a set of properties including their type (integer,date,string, etc.) and multiplicities (1, 0..1,0..*, etc.). Soft modelling techniques go a step further since they aim to project the datasets onto a feature space which allows to infer a probabilistic representation of the information. Using these features, it is possible to model differences between classes that would go unnoticed using hard techniques, since features can cover a wide range of aspects that are not usually taken into account by hard modelling, such as the proportion of punctuation characters in a piece of text. For example, the textual value of the price attribute in Fig. 2(a),$9.70, is a string, and thus could be considered a title by a hard model, although it is a price; and a book with 400 authors would not break the cardinality restriction 1..*, so its structure would be considered correct, although it is almost certainly incorrect. We focus our study on soft techniques, since they are able to model the subtle differences between a wide variety of classes, which is key to perform web scale information modelling and labelling, in which there are many similar information classes that are difficult to tell apart. We have identified three groups of related techniques: techniques used for information verification, i.e., learning a model used to verify labelled datasets by identifying those datasets that contain errors [4,7–9], techniques used for semantic labelling, that is, labelling information with known classes so that it can be integrated into a known schema [10–15], and techniques developed in the linked data context [3], focusing on ontology integration and linking tasks. 36 938 D. Ayala et al. / Knowledge-Based Systems 163 (2019) 931–943 Regarding information verification, Kushmerick [4,7] devised a probabilistic technique that models features as Gaussian random variables. Lerman et al. [8] create a vector with the average of several features computed from the instances of a correct dataset. The vector is later compared to the vector computed from new datasets using the χ2goodness-of-fit test. McCann et al. [9] improved on Kushmerick’s technique by normalising probabilities, assigning weights to features, and adding noise using hand-crafted perturbations. The goal of the previous techniques is to raise an alarm when a new, unverified dataset deviates significantly from the information used to learn the model. The verification only relies on text-based features and the number of tuples in the dataset, and the relationships between classes are not considered. Only Kushmerick [7] can deal with any arbitrarily structured information, whereas the others deal with tuples only. Their models do not take records into account. Regarding semantic labelling, Limaye et al. [11] use objective function maximisation to find the label assignment that is more consistent with the information in a dataset. Venetis et al. [12] use Bayesian classification to find the most likely label for a group of attributes using a database of samples. Mulwad et al. [13] use an incremental message propagation algorithm to label groups of different attributes with a record class and each individual attribute with a named entity using Wikitology as an external knowledge base. Ritze et al. [16] use an iterative process to label record named entities in HTML tables and their attributes by mapping them to DBpedia types and properties. In a similar vein, Zhang [26] iteratively labels records that correspond to named entities and their attributes from HTML tables while using information from the HTML context of the tables to create a richer representation of cells and columns. Ramnandan et al. [14] use distribution equivalence tests when numeric values are detected, as well as a Lucene index when non-numeric ones are detected: they store attributes as examples and label new groups of attributes by using them to query the index (this technique was later used in [27]). Pham et al. [15] expand on this idea by enlarging the feature catalogue, introducing similarity measures. Neumaier et al. [10] focus exclusively on numerical values and compute feature vectors from sets of numbers. The majority of these techniques do not define a set of features, but rely on queries to knowledge bases. The relationships between classes are not modelled. Only Ramnandan et al. [14], Pham et al. [15] and Neumaier et al. [10] deal with any arbitrarily structured information. They do not label records beyond the first one (the one that would represent the entire row in a table), only attributes, since they assume that records always correspond to named entities, while they can be structural elements that group other instances, such as dates or addresses. Limaye et al. [11], Venetis et al. [12], Mulwad et al. [13], Ritze et al. [16], and Zhang [26] are limited to named entities, e.g., people or places. Finally, since all semantic labelling techniques label groups of instances, they assume that information is grouped into bags of examples that are known to share the same class. Regarding linked data, Soru and Ngomo [3] survey several classification techniques which are applied to feature vectors representing pairs of records. Each feature vector contains several features related to cosine distance and edit distance. Though these techniques can be applied to information with any structure, the models they create are limited to text-based features, such as cosine distance, and therefore do not model the relationships between classes. Finally, Neville and Jensen [17] introduce the idea of iteratively applying a classification model that, in each step, computes features based on the labels assigned in the former step, thus refining the labels in each iteration. This technique is similar to ours, since it performs iterative labelling by computing features that change after each iteration. However, there are substantial differences: TAPON has a two-phase application, as opposed to Neville and Jensen, that only has one which would correspond to the hintbased phase; TAPON is trained with hint-based features that have been computed from inferred labels instead of actual classes, since during application actual classes are not available; finally, TAPON focuses on semantic labelling in a multi-domain context. Overall, TAPON focuses on the specific task of semantic labelling of records and attributes, which led us to devise a more optimised technique and feature catalogue. 4. Experimental analysis Our experiments consist of performing semantic labelling on both records and attributes in a multi-source scenario with realworld information. They aim to prove that, in the application scenario we focus on, TAPON is able to model and label classes with higher accuracy than other state-of-the-art techniques, achieving improved F1score thanks to our large feature catalogue with more complex features, that is significantly enriched by the addition of hint-based features that reflect the relationship between classes of instances. The different techniques are applied to a testing dataset in order to compare the inferred labels to the actual ones. 4.1. Setup We have used Spark [28]’s random forest classifiers implementation for the creation of binary classifiers and its multilayer perceptron classifiers implementation for the creation of multiclass classifiers, since other configurations yield worse results in the informal tests that we have performed, and Soru and Ngomo [3] suggest that these classifiers yield good results in data linking tasks, which are similar in nature to semantic labelling. Our configuration of the random forest classifiers include the creation of 100 trees with a maximum depth of 40, Gini as the impurity measure, and a minimum information gain of 0.01. Our configuration of the perceptron classifiers include performing 500 iterations with no hidden layers. The other parameters were set to their defaults. We have used datasets from 10 different linked data sources obtained from RKB explorer [29], an infrastructure for linked data providers whose collection of datasets have already been used for testing elsewhere [30–32]. Note that we have used linked data datasets for convenience, since they are a good source of labelled, structured information; however, the datasets were transformed into the generic structures we have described. Our datasets contain a total of 3155 records belonging to 24 different classes, and a total of 7736 attributes belonging to 53 different classes with 3483 unique textual values. Classes have, on average, 141.44 instances, with a standard deviation of 162.20. Records have, on average, 0.72 records and 2.45 attributes. 29% of attributes have a numeric value; datasets have, on average, 2.73 levels of depth (2 levels corresponding to a flat record), and a maximum of 4 levels. The specific datasets that were used are: DBLP articles, NFS awards, EPSRC grants, Telegraphis countries, Restaurants, European Patent Office classifications, Edubase schools, DigitalEconomy profiles, Dev8d programmes, and Courseware books. They have been selected because of their varied nature so that they cover a wide range of cases and labelling them is challenging. They have classes with small and large numbers of instances (though most classes have between 40 and 100 instances), both numerical and non-numerical values among attributes, both flat records and deeper structures, and groups of classes with high similarity that make it harder to classify them. We have joined these datasets into a single testing scenario in order to increase the difficulty of labelling each instance as much as possible. Separating them would greatly lower the number of instances and thus make classification much easier. Note that we cannot give a good measure of the 37 D. Ayala et al. / Knowledge-Based Systems 163 (2019) 931–943 939 Table 3 Results summary displaying the 95% confidence interval (TAPON). Technique Precision Recall F1 Accuracy TAPON-HB [0.96, 0.96] [0.87, 0.87] [0.91, 0.92] [0.92, 0.93] TAPON-HF [0.95, 0.95] [0.75, 0.76] [0.84, 0.84] [0.82, 0.83] magnitude of this similarity in an unsupervised way, since it is precisely through modelling techniques that we can compute how difficult it is to tell apart certain classes by measuring how well said techniques perform. The overall results obtained by different techniques in our experiments are not close to perfection and thus prove that creating a model is not, in this case, a trivial task. For example, class http://xmlns.com/foaf/0.1/givenName is often confused with other classes that have a similar format such as http://xmlns.com/foaf/0.1/familyName. Among the techniques we have implemented, which are later described in detail, Soru labels 10.00% of them correctly with class http://xmlns.com/foaf/0. 1/givenName,Kush 0.00% of them, Ram 0.17% of them, Pham 0.09% of them, Neville 35.11% of them, and even our technique only labels 15.89% of them correctly. We have divided the selected datasets into 10 folds, and applied leave-p-out validation [33] by using 8 folds for training and 2 folds for testing in each experiment, resulting in a total of 45 experiments. The datasets create an experimentation scenario with the following remarkable properties: it consists of both attributes and records, labelled with a class; information is arbitrarily structured, with tuples and other deeper structures; and datasets are not aligned, which means they must be labelled individually. We measure the classification accuracy (rate of instances that were correctly labelled), as well as the macro-averaged precision, recall and F1score, computed as the average of the precision, recall and F1of each class, respectively. We consider the accuracy to be the most appropriate measure, since it has a clear interpretation in multi-class classification. Other measures have been included because they are the scientific standard, but are not always a clear indicator of labelling quality. The following situation exemplifies this: suppose there are 20 possible labels. If a classifier always outputs the same label, its macro-precision (macro-averaged precision) will be 0.95, since in 19 out of 20 classes, there are no false positives. We do not include the micro-averaged measurements (micro precision, recall, and F1) because they have the same value as the accuracy. Since Kush,Soru,Ram, and Pham are unable to label records, we only use them to label attributes, and measure their indicators by only taking attributes into account (e.g. the accuracy of Pham is measured as the rate of attributes that were correctly labelled). Ram, and Pham are fed individual attributes, and any feature that requires a group of attributes is computed from a group that contains a single one. We performed our experiments on a computer with an Intel Xeon E7-4807 that ran at 1.87 GHz, had 16 GB of RAM, Windows 7 Pro 64-bit, Java 1.7, and Spark 2.10 for Java. No changes were made to their default configurations. Our datasets, measures and source code have been made available online.2 4.2. Improvement of the hint-based phase We compare the results obtained by TAPON without including hint-based features and performing only the first phase (TAPONHF), and TAPON including hint-based features and performing two phases (TAPON-HB). This experiment aims to prove the significant 2At http://www.tdg-seville.info/dayala/TAPON. Fig. 5. Boxplot with results obtained by TAPON. Table 4 Results summary displaying the 95% confidence interval (methods). Technique Precision Recall F1 Accuracy TAPON-HB [0.96, 0.96] [0.87, 0.87] [0.91, 0.92] [0.92, 0.93] Ram [0.80, 0.81] [0.62, 0.63] [0.70, 0.71] [0.68, 0.70] Neville [0.93, 0.94] [0.55, 0.68] [0.66, 0.77] [0.54, 0.68] Pham [0.87, 0.91] [0.42, 0.49] [0.45, 0.52] [0.51, 0.58] improvement of adding hint-based features when using the same classification technique. Fig. 5 shows the results obtained by both techniques. Table 3 shows a numerical summary. The accuracy when adding hintbased features is significantly better, with an improvement of around 10%. Even without using hint-based features, the accuracy is high, thanks to the large feature catalogue. In order to prove that hint-based features are actually used by the model, we have studied their use by the binary classifiers. We have taken the top 5 features of every binary classifier in the hint-based model, sorted by their importance across all trees as suggested by Hastie et al. [34], and computed the fraction of hint-based features among the total. 40.75% of features were hintbased, which clearly shows their usefulness. 4.3. Comparison of TAPON and other methods We compare the results obtained by the following techniques: TAPON including hints-based features (TAPON-HB); Ramnandan et al. [14]’s technique (Ram); Pham et al. [15]’s technique excluding its histogram similarity feature, which cannot be computed properly from a single instance (Pham); and a version of our one-vs-all classification that implements Neville and Jensen [17]’s technique by using a single model and, during training, computing hintbased features using the actual class of the instances (Neville). This experiment aims to prove that our technique achieves better results than other techniques that represent a different approach in the application scenario we have described. Other techniques in the related work have not been included because they are not applicable in our scenario. For example, table labelling techniques can only be applied to named entities and Neumaier et al. [10]’s technique can only label numerical attributes. Fig. 6 shows the results obtained by the aforementioned techniques. Table 4 shows a numerical summary. Our technique achieves better accuracy than the other techniques that we have applied in our experiments. Neville seems to have a large instability. We believe this to be caused by the way it is trained using actual classes (while we use 38 940 D. Ayala et al. / Knowledge-Based Systems 163 (2019) 931–943 Fig. 6. Boxplot with results obtained by different methods. Fig. 7. Boxplot with results obtained by different feature catalogues. Table 5 Results summary displaying the 95% confidence interval (features). Technique Precision Recall F1 Accuracy TAPON-HB [0.96, 0.96] [0.87, 0.87] [0.91, 0.92] [0.92, 0.93] Soru-HB [0.95, 0.96] [0.77, 0.80] [0.85, 0.87] [0.86, 0.89] Soru [0.92, 0.93] [0.70, 0.70] [0.80, 0.80] [0.79, 0.80] Kush-HB [0.98, 0.98] [0.62, 0.65] [0.76, 0.78] [0.68, 0.73] Kush [0.94, 0.95] [0.47, 0.49] [0.63, 0.65] [0.50, 0.56] labels inferred by the first model). The quality of the predictions heavily depends on the quality of the labels. When applied to the testing dataset, the model is applied even when there are no labels that can be used to properly compute hint-based features and consequently, performance is poor. However, if iterations are able to slightly improve the labels, there is a slow approximation towards the actual classes which requires many iterations. If the set of labels is too distant from real classes and an iteration is not able to improve the labels, then there is convergence and the process stops. In some cases, there is no early convergence and iterations slowly reach a good set of predictions with accuracy around 0.85. In other cases, there is early convergence and the set of poor predictions remains unchanged, resulting in accuracy around 0.40. 4.4. Comparison of TAPON and other feature catalogues We compare the results obtained by the following techniques: TAPON including hints-based features (TAPON-HB); a version of our classification technique that only uses Kushmerick [4]’s feature catalogue(Kush); the former including hint-based features(Kush- HB); a version of our classification technique that only uses Soru and Ngomo [3]’s feature catalogue (Soru); and the former including hint-based features(Soru-HB). This experiment aims to prove that TAPON’s feature catalogue achieves better results than the other feature catalogue in the related work, in the application scenario we have described, and that adding hint-based features to a features catalogue improves results, not only with our specific catalogue. Table 6 summarises the features that each technique uses to model information. The techniques by Lerman et al. [8] and Mc- Cann et al. [9] use feature catalogues that are very similar to Kushmerick’s, and so they have not been included. Fig. 7 shows the macro-average of the precision, recall, and F1 score obtained by the aforementioned techniques. Table 5 shows a numerical summary. Our technique achieves better accuracy than the other techniques that we have applied in our experiments. Regarding the other techniques, the version with hint-based features outperforms the original catalogue in both cases. 4.5. TAPON applied to worst-case scenarios Fig. 8 contains a more fine-grained representation of some of the results. It depicts a comparison between TAPON and other techniques. For each technique, we compare the 3 most problematic classes for that technique (that is, those with the worst F1score). The number of classes (3) is arbitrary, since this representation of the results is not intended to be a strict report, but rather a visualisation of how our technique seems to solve whatever problems cause really low accuracy when using other techniques. Each point represents the F1score obtained by a class during one of the 45 experiments (we use the F1score instead of accuracy, since these are results per class). It can be observed how, to a greater or lesser degree, the cases that are more problematic for other techniques are dealt with relatively well, obtaining high F1when using TAPON. The only exception is when comparing to Neville and Jensen [17]. Both techniques behave similarly, probably because the similarities between them make them fail in similar situations. Still, these are only the worst cases, and our technique obtains better results overall, as explained earlier. 4.6. Statistical analysis In order to test the significance of our accuracy results, we have applied statistical tests with α=0.05. Since the variable (accuracy) is not normally distributed, we are performing a multiple comparison and there are less than five variables, we applied a Friedman Test with control estimation. The resulting p-value is 39 D. Ayala et al. / Knowledge-Based Systems 163 (2019) 931–943 941 Table 6 Features used by each technique. Technique Features TAPON Features described in Tables 1 and 2 Kushmerick [34] Density of letter characters Density of numeric characters Density of uppercase characters Density of lowercase characters Density of punctuation characters Number of HTML tags Number of words Mean word length Soru and Ngomo [17] Mean edit distance to sets of examples of each attribute class Mean trigram similarity to sets of examples of each attribute class Mean cosine distance to sets of examples of each attribute class Fig. 8. F1score obtained by the more problematic classes for each technique, compared to ours. Table 7 Average rank of each technique. Technique Ranking TAPON-HB 1.07 Soru-HB 2.16 TAPON-HF 3.20 Soru 4.27 Kush-HB 5.93 Neville 5.98 RAM 5.98 Pham 7.71 Kush 8.71 10e−10, which implies there are significant differences between the ranks (whose average is shown in Table 7). We have applied Hommel’s test to compare the results obtained by TAPON-HB to each other technique (including TAPON-HF). The resulting p-value is always below 2.84e−13. Therefore, there is statistical evidence that the results obtained by our technique are significantly different from those obtained by other techniques. Note that hint-based versions of initially worse technique surpass TAPON-HB in accuracy when adding hint-based features, proving their usefulness. 4.7. Efficiency of TAPON Regarding training time, Fig. 9 shows how much time it takes to create our two models from different amounts of training data. We have trained our models using 1 to 10 folds (10% to 100% of our available data). For each different number of folds we performed 10 experiments, where the specific folds to be used among the 10 available ones were selected by using a moving window (wrapping around 1 in a cyclical fashion). We computed the average value and the 95% confidence interval. Our main observation here is that, since the model only has to be trained once, spending a small number of hours training is not at all unreasonable. The increase in training time seems to follow a linear trend. Table 8 shows the application time per instance of each technique. TAPON’s application time is similar to most techniques, with the second phase adding additional application time. Ram and Kush have the lowest application time by a wide margin, thanks to their simplicity. The other techniques have less features, but they are more costly to compute. Adding hint-based features has a seemingly constant hit on the application time. Overall, we consider TAPON’s application time to be reasonable. 40 942 D. Ayala et al. / Knowledge-Based Systems 163 (2019) 931–943 Fig. 9. Training time of TAPON. Table 8 95% confidence interval of the application times in seconds. Technique App. time TAPON-HB [0.032, 0.035] TAPON-HF [0.020, 0.023] Soru-HB [0.056, 0.063] Soru [0.031, 0.034] Ram [0.002, 0.002] Neville [0.028, 0.032] Pham [0.030, 0.040] Kush-HB [0.015, 0.020] Kush [0.004, 0.004] 5. Conclusions In this article, we have presented a new two-phase, machinelearning semantic labelling technique that takes into account features that model the relationships between instances. It can model arbitrarily structured information from several sources, and is able to label datasets in an individual basis. We use the information from nearby instances in a novel way. By creating two models, we can compute additional hint-based features. The first model is used to endow instances with a hint, allowing us to inject features that are used by the second model. We have performed semantic labelling of information from several linked data sources in order to evaluate the effect of the features and compare our technique with other existing ones. Our experimental analysis shows that, while our rich feature catalogue helps our technique achieve better results in a stressful modelling scenario, it is the collection of hint-based features that creates a remarkable difference (from an average accuracy of 82.83% to 92.75%) by allowing us to measure features that require having a first idea of what classes the instances may belong to. Consequently, we conclude that our technique contributes to the state of the art by improving information modelling accuracy while modelling both records and attributes in arbitrary structures. Existing techniques so far have focused on application scenarios that rely on certain conditions such as specific structures of data or the presence of instances groups. When that is the case (for example, we can group instances and label them as a group), making use of that information is an advantage, but in situations where it is not, it is convenient to use a more generic approach that is not adversely affected by the absence of the aforementioned conditions. Our technique offers this approach, while being able to integrate other techniques thanks to our two-phase solution. The limitations of TAPON are mainly related to the assumptions we presented in Section 2.2; in different application scenarios, it will likely perform worse than more optimised techniques. For example, if a task involves labelling millions of attributes that are known to share the same class, TAPON may not scale well, since it labels them individually, while the technique by Pham et al. [15] would not have this problem. There may be workarounds for some of these cases, like labelling a few attributes and taking the most frequent label in the example, but other techniques in the related work have more optimal solutions. Consequently, future research could focus on how to apply the same principles of TAPON (performing a second iteration to use additional information) in other techniques that focus on different application scenarios. Furthermore, TAPON is not optimised for large numbers of classes (several hundreds or thousands) due to the use of a one-vs- all classifier. Although the scenarios we have observed have a few dozens, it would be of interest to develop a different version that sacrifices accuracy in favour of scalability and speed, in the same vein as Ramnandan et al. [14]’s. Acknowledgement Our work was supported in the Spanish R&D&I programme by grant TIN2016-75394-R. References [1] Hassan A. Sleiman, Rafael Corchuelo, A survey on region extractors from web documents, IEEE Trans. Knowl. Data Eng. 25 (9) (2013) 1960–1981, URL http://doi.ieeecomputersociety.org/10.1109/TKDE.2012.135. [2] Jérôme Euzenat, Pavel Shvaiko, Ontology Matching, second ed., Springer, ISBN: 978-3-642-38720-3, 2013. [3] Tommaso Soru, Axel-Cyrille Ngonga Ngomo, A comparison of supervised learning classifiers for link discovery, in: SEMANTICS, 2014, pp. 41–44. URL http://doi.acm.org/10.1145/2660517.2660532. [4] Nicholas Kushmerick, Regression testing for wrapper maintenance, in: AAAI/IAAI, 1999, pp. 74–79, URL http://www.aaai.org/Library/AAAI/1999/ aaai99-011.php. [5] Patricia Jiménez, Rafael Corchuelo, Roller: a novel approach to web information extraction, Knowl. Inf. Syst. 49 (1) (2016) 197–241, http://dx.doi.org/10. 1007/s10115-016-0921-4. [6] Boris Chidlovskii, Automatic repairing of web wrappers by combining redundant views, in: ICTAI, 2002, pp. 399–406, http://dx.doi.org/10.1109/TAI.2002. 1180831. [7] Nicholas Kushmerick, Wrapper verification, WWW 3 (2) (2000) 79–94, http: //dx.doi.org/10.1023/A:1019229612909. [8] Kristina Lerman, Steven Minton, Craig A. Knoblock, Wrapper maintenance: A machine learning approach, J. Artificial Intelligence Res. 18 (2003) 149–181. [9] Robert McCann, Bedoor K. AlShebli, Quoc Le, Hoa Nguyen, Long Vu, AnHai Doan, Mapping maintenance for data integration systems, in: VLDB, 2005, pp. 1018–1030. URL http://www.vldb2005.org/program/paper/fri/p1018- mccann.pdf. [10] Sebastian Neumaier, Jürgen Umbrich, Josiane Xavier Parreira, Axel Polleres, Multi-level semantic labelling of numerical values, in: International Semantic Web Conference (1), 2016, pp. 428–445. URL http://dx.doi.org/10.1007/978- 3-319-46523-4_26. [11] Girija Limaye, Sunita Sarawagi, Soumen Chakrabarti, Annotating and searching web tables using entities, types and relationships, PVLDB 3 (1) (2010) 1338–1347, URL http://www.comp.nus.edu.sg/vldb2010/proceedings/files/ papers/R118.pdf. [12] Petros Venetis, Alon Y. Halevy, Jayant Madhavan, Marius Pasca, Warren Shen, Fei Wu, Gengxin Miao, Chung Wu, Recovering semantics of tables on the Web, PVLDB 4 (9) (2011) 528–538, URL http://www.vldb.org/pvldb/vol4/p528- venetis.pdf. [13] Varish Mulwad, Tim Finin, Anupam Joshi, Semantic message passing for generating linked data from tables, in: ISWC, 2013, pp. 363–378. http://dx. doi.org/10.1007/978-3-642-41335-3_23. [14] S.K. Ramnandan, Amol Mittal, Craig A. Knoblock, Pedro A. Szekely, Assigning semantic labels to data sources, in: ESWC, 2015, pp. 403–417, http://dx.doi. org/10.1007/978-3-319-18818-8_25. [15] Minh Pham, Suresh Alse, Craig A. Knoblock, Pedro A. Szekely, Semantic labeling: A domain-independent approach, in: International Semantic Web Conference (1), 2016, 446–462. URL http://dx.doi.org/10.1007/978-3-319- 46523-4_27. [16] Dominique Ritze, Oliver Lehmberg, Christian Bizer, Matching html tables to dbpedia, in: Proceedings of the 5th International Conference on Web Intelligence, Mining and Semantics, ACM, 2015, p. 10. 41 D. Ayala et al. / Knowledge-Based Systems 163 (2019) 931–943 943 [17] Jennifer Neville, David Jensen, Iterative classification in relational data, in: Proc. AAAI-2000 Workshop on Learning Statistical Models from Relational Data, 2000, pp. 13–20. [18] Valter Crescenzi, Giansalvatore Mecca, Paolo Merialdo, Roadrunner: Towards automatic data extraction from large web sites, in: VLDB, 2001, pp. 109–118, [19] Michele Banko, Michael J. Cafarella, Stephen Soderland, Matthew Broadhead, Oren Etzioni, Open information extraction from the web, in: IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, January 6–12, 2007, 2007, pp. 2670–2676, URL http://ijcai. org/Proceedings/07/Papers/429.pdf. [20] Patricia Jiménez, Rafael Corchuelo, On learning web information extraction rules with tango, Inf. Syst. 62 (2016) 74–103, http://dx.doi.org/10.1016/j.is. 2016.05.003. [21] Juan C. Roldán, Patricia Jiménez, Rafael Corchuelo, Extracting web information using representation patterns, in: Proceedings of the fifth ACM/IEEE Workshop on Hot Topics in Web Systems and Technologies, HotWeb 2017, San Jose/Silicon Valley, CA, USA, October 12–14, 2017, 2017, 4:1–4:5, http: //doi.acm.org/10.1145/3132465.3133840. [22] Hassan A. Sleiman, Rafael Corchuelo, Trinity: On using trinary trees for unsupervised web data extraction, IEEE Trans. Knowl. Data Eng. 26 (6) (2014) 1544–1556, URL http://doi.ieeecomputersociety.org/10.1109/TKDE. 2013.161. [23] Jayant Madhavan, Philip A. Bernstein, Erhard Rahm, Generic schema matching with cupid, in: VLDB 2001, Proceedings of 27th International Conference on Very Large Data Bases, September (2001) 11-14, Roma, Italy, 2001, pp. 49–58. URL http://www.vldb.org/conf/2001/P049.pdf. [24] Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, The pagerank citation ranking: bringing order to the web, 1999. [25] Carlos R. Rivero, Inma Hernández, David Ruiz, Rafael Corchuelo, Discovering and analysing ontological models from big RDF data, J. Database Manag. 26 (2) (2015) 48–61, http://dx.doi.org/10.4018/JDM.2015040104. [26] Ziqi Zhang, Effective and efficient semantic table interpretation using tableminer+, Semantic Web (2016) 1–37, Preprint. [27] Mohsen Taheriyan, Craig A. Knoblock, Pedro A. Szekely, José Luis Ambite, Learning the semantics of structured data sources, J. Web Sem. 37-38 (2016) 152–169, URL http://dx.doi.org/10.1016/j.websem.2015.12.003. [28] The Apache Software Foundation, Apache spark, 2018, https://spark.apache. org/. (Accessed 08 June 2018). [29] Hugh Glaser, Ian Millard, Afraz Jaffri, Rkbexplorer.com: A knowledge driven infrastructure for linked data providers, in: ESWC, 2008, pp. 797–801, http: //dx.doi.org/10.1007/978-3-540-68234-9_61. [30] Dezhao Song, Jeff Heflin, Automatically generating data linkages using a domain-independent candidate selection approach, in: International Semantic Web Conference (1), 2011, pp. 649–664. URL http://dx.doi.org/10.1007/ 978-3-642-25073-6_41. [31] Carlos Buil Aranda, Aidan Hogan, Jürgen Umbrich, Pierre-Yves Vandenbussche, Sparql web-querying infrastructure: Ready for action?, in: International Semantic Web Conference, vol. 2, 2013, pp. 277–293, URL http://dx.doi.org/ 10.1007/978-3-642-41338-4_18. [32] Aidan Hogan, Antoine Zimmermann, Jürgen Umbrich, Axel Polleres, Stefan Decker, Scalable and distributed methods for entity matching, consolidation and disambiguation over linked data corpora, J. Web Sem. 10 (2012) 76–110, http://dx.doi.org/10.1016/j.websem.2011.11.002. [33] Sylvain Arlot, Alain Celisse, et al., A survey of cross-validation procedures for model selection, Statist. Surv. 4 (2010) 40–79. [34] Trevor Hastie, Robert Tibshirani, Jerome H. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction, second ed., in: Springer Series in Statistics, Springer, ISBN: 9780387848570, 2009, URL http://www. worldcat.org/oclc/300478243. 42 5 TAPON-MT: A VERSATILE FRAMEWORK FOR SEMANTIC LABELLING 43 Semantic labelling refers to the problem of assigning known labels to the elements of structured information from a source such as an HTML table or an RDF dump with unknown semantics. In the recent years it has become progressively more relevant due to the growth of available structured information in the Web of data that need to be labelled in order to integrate it in data systems. The existing approaches for semantic labelling have several drawbacks that make them unappealing if not impossible to use in certain scenarios: not accepting nested structures as input, being unable to label structural elements, not being customisable, requiring groups of instances when labelling, requiring matching instances to named entities in a knowledge base, not detecting numeric data, or not supporting complex features. In this article, we propose TAPON-MT, a framework for machine learning semantic labelling. Our framework does not have the former limitations, which makes it domain-independent and customisable. We have implemented it with a graphical interface that eases the creation and analysis of models, and we offer a web service API for their application. We have also validated it with a subset of the National Science Foundation awards dataset, and our conclusion is that TAPON-MT creates models to label information that are effective and efficient in practice. Information Systems 83 (2019) 57–68 Contents lists available at ScienceDirect Information Systems journal homepage: www.elsevier.com/locate/is TAPON-MT: A versatile framework for semantic labelling Daniel Ayala∗, Inma Hernández, David Ruiz, Miguel Toro Universidad de Sevilla, ETSI Informática, Avda. de la Reina Mercedes, s/n, Sevilla E-41012, Spain highlights •We present TAPON-MT, a versatile, customisable semantic-labelling framework. •TAPON-MT labels both textual and structural elements in arbitrary datasets. •TAPON-MT’s modular architecture enables adding complex features to the model. •TAPON-MT allows the visualisation and validation of models for diagnosis of errors. •Our validation with the NSF awards dataset, shows an improvement in accuracy. article info Article history: Received 30 June 2018 Accepted 28 December 2018 Available online 17 February 2019 Recommended by F. Carino Jr. Keywords: Semantic labelling Information integration Machine learning abstract Semantic labelling refers to the problem of assigning known labels to the elements of structured information from a source such as an HTML table or an RDF dump with unknown semantics. In the recent years it has become progressively more relevant due to the growth of available structured information in the Web of data that need to be labelled in order to integrate it in data systems. The existing approaches for semantic labelling have several drawbacks that make them unappealing if not impossible to use in certain scenarios: not accepting nested structures as input, being unable to label structural elements, not being customisable, requiring groups of instances when labelling, requiring matching instances to named entities in a knowledge base, not detecting numeric data, or not supporting complex features. In this article, we propose TAPON-MT, a framework for machine learning semantic labelling. Our framework does not have the former limitations, which makes it domain-independent and customisable. We have implemented it with a graphical interface that eases the creation and analysis of models, and we offer a web service API for their application. We have also validated it with a subset of the National Science Foundation awards dataset, and our conclusion is that TAPON-MT creates models to label information that are effective and efficient in practice. ©2019 Elsevier Ltd. All rights reserved. 1. Introduction Semantic labelling refers to the problem of analysing structured information and endowing it with labels that denote known classes from an ontology [1]. A dataset of structured information, usually extracted from the web in a crawling process [2] is taken as input, and each element in the dataset is assigned one or several labels, which correspond to the classes that best describe the element according to its features. Semantic labelling is a cornerstone for the integration of information from heterogeneous data sources, which is common in several contexts [3–5], and can be used in tasks related to information extraction [6,7] (by using the labels to determine whether or not a piece of information should be extracted), information verification [8–10] (by using the labels to ∗Corresponding author. E-mail addresses: [email protected] (D. Ayala), [email protected] (I. Hernández), [email protected] (D. Ruiz), [email protected] (M. Toro). confirm the assumed class of an element), or ontology matching [11] (by using the labels to study the similarities between pairs of classes). The format of the input information can range from simple HTML tables to complex structures in RDF datasets. Regardless of their source format, we can represent information with generic structures as exemplified in Fig. 1, which depicts information about an award from the NSF awards dataset [12]: namely an award record, which is a structural element with no associated text, containing other records and a number of attributes, which are textual elements (elements with an associated string, which includes numbers, dates, etc.). Both records and attributes are instances of a number of classes such as ‘‘title’’ or ‘‘awardee’’, though the class of instances can be unknown, which motivates their labelling. Semantic labelling can be seen as a supervised classification process in which the input is one record or attribute, and the output is one or more labels that correspond to the semantic classes that best describe them. Note that the need for supervision is not a problem, thanks to the large amount of available labelled, https://doi.org/10.1016/j.is.2018.12.006 0306-4379/©2019 Elsevier Ltd. All rights reserved. 44 58 D. Ayala, I. Hernández, D. Ruiz et al. / Information Systems 83 (2019) 57–68 Fig. 1. Structured information example. structured information in the Web of Data [13] that can be used to train the models. The selection of labels is based on features that measure the similarity between the input and the known classes, such as the number of digits in a textual value [8,9], or the score of a knowledge base query results [1,14–16]. What specific features are used by each approach greatly affects its accuracy. For example, one that only measures the number of uppercase and lowercase letters will not be able to properly classify attributes that are not characterised by those features, such as prices, telephone numbers, or emails. The area of automated classification has been extensively researched in the past [17], and many techniques have been proposed that deal with this problem. Obviously, when used as a part of a semantic labelling process, the performance of these techniques has a significant effect on the accuracy of the labelling. However, we consider the study of these techniques to be beyond the scope of the paper, since they are completely independent of semantic labelling approaches that apply them. Instead, we focus on aspects that are specific to semantic labelling. Regarding proposals in the related work, they have been devised with specific application scenarios in mind, and thus lack in versatility. They can usually be only applied suitably under certain conditions, and while focusing on certain scenarios helps them achieve better results under their conditions, they lack in applicability under different ones. The following limitations are common among them: they cannot be applied to structures with nested records, only to flat ones; they can only be used to label attributes; they rely on a particular classification technique and a specific set of features; they cannot label individual instances, but only groups; they rely on matching instances to named entities in a knowledge base; they do not detect numeric data; and they do not support complex features that are necessary to model some classes. Fig. 1 exemplifies these problematic cases. There are records inside other records, so approaches that only label flat records would obtain poor labels, if any, without computationally expensive flattening preprocessing that may not be viable. There are both records and attributes, so approaches that only label attributes would not provide a complete labelling. Several approaches that label groups of instances use the distribution of a group of numeric attributes to infer their class, but they would be unable to label the ‘‘estimatedTotalAmt’’ attribute, since there is a single instance being classified. Several attributes, such as ‘‘estimatedTotalAmt’’, or ‘‘startDate’’ do not correspond to named entities and cannot be found in a knowledge base. There are several attributes with numeric data: ‘‘estimatedTotalAmt’’ and ‘‘zipCode’’, which can only be properly processed if the approach detects that they are numeric and uses their value during the labelling process. Finally, there are some pairs of instances that are nearly indistinguishable and require complex features: the ‘‘startDate’’ and ‘‘expDate’’ attributes, which have an identical format, and the ‘‘awardee’’ and ‘‘performance’’ records, which have an identical structure. In order to solve these problems, we have created TAPONMT, a new semantic labelling framework whose architecture has been devised with applicability and customisation in mind, and is based on a two-phase classification technique of our own [18]. Applicability implies that our framework is domain-independent and does not rely on specific conditions. Customisation implies that the architecture and workflow of our framework give the possibility to integrate a wide variety of features and classification techniques. The main strengths of our framework are that it supports nested records as input; it supports the labelling of both records and attributes; its features and classification techniques can be customised; it labels structures individually; it does not rely on entity matching; it detects numeric data; and its architecture supports several kinds of complex features, including dynamically generated features, and hint-based features (a kind of feature that requires a two-phase process). Regarding the example in Fig. 1, TAPON-MT is able to label all the records and attributes in the nested structure, to label the ‘‘estimatedTotalAmt’’ attribute without other instances of the same class, to label the attributes that do not correspond to named entities, to detect what attributes are numeric and leverage the use of features based on their values, and to label the nearly indistinguishable instances thanks to one of the supported complex features: hint-based features, which allow TAPON-MT to learn that ‘‘startDate’’ attributes are near something that resembles a date but have a lower value than it, while ‘‘expDate’’ attributes have a higher value than it. Similarly, they would allow it to learn that ‘‘awardee’’ records contain an attribute that seems to be a name, while ‘‘performance’’ records contain an attribute that seems to be a location. Our framework provides two different interfaces that make it usable both as a web service API and as a desktop application with a graphical interface. The web service takes a dataset in JSON format, and the response contains the labels. The graphical interface allows the user not only to create models, but also to visualise and validate them. It can be used to create models by choosing features, classification settings and data sources; used to visualise the created models and check for suspicious classifiers; and used to test the models by selecting the data it is applied to, obtaining several measurements of performance, as well as a matrix that can be used to study the similarity between classes. In addition to these implementations, we have performed ten-fold cross validation to confirm that models created with our framework are able to achieve good results by comparing it to the results obtained by implementations of the proposals by Kushmerick [8], Ramnandan et al. [1], and Pham et al. [19] The experiments consisted in labelling information from the National Science Foundation RDF dataset. The rest of the article is organised as follows: Section 2de- scribes the analysis of the relevant approaches we have identified in the literature; Section 3reports on some preliminaries that are necessary to understand our framework; Section 4contains a detailed description of TAPON-MT, including the underlying data model and architecture; Section 5describes how we have validated our framework by implementing it and performing experiments; finally, Section 6recaps on our main conclusions. 2. Related work In this section, we present existing proposals that are related to TAPON-MT. We present both approaches for semantic labelling 45 D. Ayala, I. Hernández, D. Ruiz et al. / Information Systems 83 (2019) 57–68 65 can be used to decrease training time: tuning hyperparameters to increase training speed at the cost of classification accuracy; using a smaller set of features at the risk of losing useful ones; or using a single multiclass classifier instead of many binary ones, which may be problematic if the classifier does not handle well the large number of classes, and would require slight modifications to the architecture of TAPON-MT. Note that we use a multiclass classifier to aggregate the binary scores instead of merely taking the class with the highest probability, which is the traditional approach in one-vs-all classifiers. We do this to properly deal with complex cases in which the correct class is not the one with the highest score. For example, let us suppose there are two classes, A and B. When an instance belongs to class A, the probabilities are ⟨A=0.9,B=0.2⟩, and when it belongs to B, they are ⟨A=0.9,B=0.8⟩(probabilities are independent, so they do not necessarily amount to one). In the second case, the probability of A is the highest one, which would lead a traditional one-vs-all classifier to choose it as the label. Our method, however, is more flexible, and would learn that an instance belongs to class B when the probability of B is high enough, independently of other, potentially higher probabilities. If our approach is not needed, TAPON-MT offers the possibility of just taking the class with the highest probability. Method ‘‘classify’’ applies a model (specified by the ‘‘classifiersFolder’’ property) to a dataset. If the dataset does not have hints, as indicated by the ‘‘hasHints’’ parameter, TAPONMT applies the hint-free model, with its corresponding set of classifiers; if it does have them, it applies the hint-based model. For each instance, it first applies each binary classifier. This results in a set of classifier outputs (be it a purely binary result or a probability) that are used as the input of the multiclass classifier. The multiclass classifier outputs the final label of the instance, which may be used as a hint. If hint-based features are not needed, only the first iteration needs to be performed. Class ‘‘ClassifiersHandler’’ provides low-level functionality related to the creation and use of classifiers. Its many properties correspond, mainly, to the classifiers of a model, separated into the 8 groups we described: for attributes and records, hint-free or hint-based, and binary or multiclass. Additionally, it stores a classes configuration, since creating multiclass classifiers require knowing what classes there are in the input datasets. Any classification technique can be used to implement both the binary and multiclass classifiers. For example, in our implementation of TAPON-MT, we train random-forest binary classifiers and neural network multiclass classifiers. Method ‘‘trainBinaryClassifiers’’ trains a binary classifier for each semantic class by using method ‘‘trainBinaryClassifier’’, which trains each individual classifier and stores it in a given path. Method ‘‘trainMulticlassClassifier’’ trains the multiclass classifier for both attributes and records, using the hint-free or hintbased classifiers depending on the value of the ‘‘hasHints’’ parameter. Finally, method ‘‘classify’’ classifies a single instance, using hint-free or hint-based classifiers depending on the value of the ‘‘hasHints’’ parameter. The resulting label is stored in the instance. Information about the probability of the label is also included. Example. An already trained model was applied to the dataset in Fig. 1 by using it as input of the models handler. First, the framework classifies it specifying that there are no hints yet. Hint-free features are computed and the classifiers are applied. Most labels are correct, but some of them are wrong, as depicted in Fig. 8. There are two wrong labels: the expDate attribute has been labelled as a startDate, and the performance record has been labelled as an awardee. The ‘‘classify’’ method is applied a second time, but now specifying that there are hints. After computing hint-based features, the hint-based classifiers are applied. The additional features Fig. 8. Hints after first iteration using the model handler. Fig. 9. Dataset in JSON format. help distinguish between similar cases: the expDate is near an attribute labelled as startDate, but has a higher value, while the startDate is near another attribute labelled as startDate, but has a lower value. The performance contains an attribute labelled as a location, while the awardee contains an attribute labelled as a name. After the second iteration, all labels are correct. 5. Validation This section describes our validation of TAPON-MT by means of an implementation with a web service and a graphical interface, as well as experimental results. The source code of TAPON-MT has been made available online.1 5.1. Implementation Our framework is supported by both a web service and a graphical interface. The web service was deployed using the Java Restlet library. It offers a ‘‘classify’’ POST method that takes a dataset in JSON format, and returns the same dataset with added fields that correspond to the final label of each instance according to the multiclass classifier, as well as the top 4 most likely labels according to the binary classifiers’ confidence scores. Fig. 9 depicts the example in Fig. 9 in JSON format, without labels. The service requires the existence of already trained models, which can be obtained with creation scripts or our graphical interface. The graphical interface has been implemented using Java 1.8.0_151. We have used re2j 1.1 to implement regular expressions, Lucene 5.4.1 to create indexes, and Spark 2.2.0 to implement classification techniques which are the basis of our models. It has three modules, namely: Model creation, Model visualisation, and Model testing. 1https://github.com/dayala1/TAPON-MT. 52 66 D. Ayala, I. Hernández, D. Ruiz et al. / Information Systems 83 (2019) 57–68 Fig. 10. TAPON-MT graphical interface. In the Model creation module (cf. Fig. 10(a)) the user can create models from a training set. The training files (in JSON format) can be split into folders that correspond to different domains to separate those from different sources. Each domain folder must in turn be split into ten fold folders. The user can then select what domains and folds will be used to train the model. The files of a domain folder can be analysed to obtain some metadata, such as the number of classes, average dataset depth or the number of attributes. These details are stored in a JSON file and can be visualised. Other applications can create or modify this file to add further information about a domain. The user can also select what features groups will be used by the model, as well as the classifier settings (which, in our implementation, are related to random forest classifiers). The Model visualisation module (cf. Fig. 10(b)) allows the user to visualise the random forest classifiers that shape a model. Since a model consists of a classifier per class, the user can select a model (the training domains and folds), and visualise every decision tree in the random forest associated to every class (this visualisation is specific to decision trees, so other classification techniques would require different visualisations). This allows the user to check that the classifiers make sense, and that certain features are taken into account. For example, if a model yields bad results, it could be because the classifier is not using all the available features for some reason (e.g. the maximum decision tree depth is set to a low value). This can be done for both the hint-free and the hint-based classifiers. We used this visualisation to check that hint-based features are actually useful when introduced, mainly in record classifiers. Finally, the Model testing module (cf. Fig. 10(c)) allows the user to choose a previously created model and then apply it to a subset of the labelled information. The user must select the model to test (the domains and folds used for training), as well as the domains and folds used for testing. Note that the user can test a model with datasets from domains that contain classes that are unknown to the model. This can be used to test how the model behaves when facing information that does not belong to any known class. The results of the test include information related to each individual class, as well as global results. The class results include the precision, recall, and F1score. The global results include the accuracy, macro precision, macro recall, and macro F1score, as well as a classes similarity matrix. The classes similarity matrix is a technique to assess how similar pair of classes are from the point of view of the classifier. Fig. 11 depicts a similarity matrix corresponding to 39 classes using a color scale ranging from 0.0 (dark purple) to 1.0 (yellow) and hidden class names (visible by hovering over each square, since some class names are long). The similarity of two classes is computed as the cosine similarity between their corresponding rows in the confusion matrix. The similarity matrix is, ideally, the identity matrix: every class is perfectly similar to itself (which is always the case), and completely made apart from the others. High values for different classes mean that the classes have been classified in a similar way, and therefore the model has not been able to separate them. Note that the similarity is not an objective measurement of how similar two classes are, since it depends on the classifier, and therefore classes that are highly similar using some classification techniques and features can be perfectly separated using other classification techniques and features. The similarity matrix is useful to identify the cases in which a particular model fails. For instance, in the matrix example we provided, we observed that the pairs of classes with high similarity were almost undistinguishable, even for a human, so the accuracy of the classifier, even if not perfect, was hard to surpass. 5.2. Experimental results Apart from the main contributions of our framework, as described in Section 2, we have performed some tests to check that the models it creates work in practice and is able to model information successfully. Our experiments consists of 10-fold crossvalidation applied to a subset of the National Science Foundation Awards dataset. The subset consists of the first 500 most recent ended awards, from those that ended in 2017. These have a total of 2223 record instances distributed among 5 record classes and 17 723 attribute instances (29.48% of them numerical) distributed among 35 attribute classes. Datasets have an average depth of 53 D. Ayala, I. Hernández, D. Ruiz et al. / Information Systems 83 (2019) 57–68 67 Fig. 11. Similarity matrix example. 3 (1 being a flat record), and records contain, on average, 38.89 instances. These datasets were chosen for their non-flat structures, the high number of classes, and the variety of attributes, which include numerical values. We performed our experiments on a computer with an Intel Xeon E7-4807 that ran at 1.87 GHz, had 16 GB of RAM, Windows 7 Pro 64-bit, Java 1.7, and Spark 2.10 for Java. No changes were made to their default configurations. We compare the results obtained by models created with our framework, TAPON-MT without hints (denoted by ‘‘TAPON-MT’’) and with hints (denoted by ‘‘TAPON-MT(H)’’), to those of an implementation of RAPTURE [8] that uses random forest classifiers with the proposed features, an implementation of Ramnandan et al. [1]’s proposal (denoted by ‘‘RAM’’), and an implementation of Pham et al. [19]’s proposal. We have selected these since, as we described in Section 2, most proposals have limitations that make them completely inapplicable in our set-up (such as only being able to label tables or named entities). Since both are only able to label attributes, their quality measures are computed considering only the attributes in the datasets (though their labelling is only partial, they are not inapplicable). All classifiers were created using their Spark 2.20 Java implementation. Random forest classifiers were created with 50 trees and a maximum depth of 15 (other settings were set to their defaults). The neural networks of our multiclass classifiers had a single dense layer (other settings were set to their defaults). Results are shown in Fig. 12. The measure that better describes the quality of the results is the accuracy, since it represents the fraction of correct labels. Note that our main contribution is the flexibility of our framework as described in Section 2, independently of the results obtained a specific set of features or datasets. TAPON-MT achieves a good accuracy, even when labelling both records and attributes in an individual way. While hint-based Fig. 12. Experimental results. Table 3 Results summary displaying the 95% confidence interval. Tool Precision Recall F1 Accuracy TAPON-MT(H) [0.85, 0.87] [0.83, 0.85] [0.84, 0.86] [0.84, 0.85] TAPON-MT [0.90, 0.91] [0.73, 0.75] [0.80, 0.82] [0.71, 0.74] RAPTURE [0.76, 0.78] [0.62, 0.64] [0.69, 0.70] [0.62, 0.64] RAM [0.76, 0.77] [0.60, 0.63] [0.67, 0.70] [0.61, 0.63] PHAM [0.81, 0.83] [0.54, 0.57] [0.65, 0.67] [0.54, 0.57] features improve accuracy in a significant way, the model without them also achieves good results thanks to the large features catalogue. Table 3 contains a summary of the results. TAPONMT(H) labels correctly 85% of instances, while the results by other proposals range from 55% to 65%. Note that there are 40 classes, so a random classifier would label instances correctly 2.5% of times. Across the 10 experiments, the average training time of TAPONMT(H) was 36.59 min, with a standard deviation of 1.49 min. This time seems to be reasonable, since the model only has to be trained once. The average application time per instance was 0.11 s, which is enough for labelling datasets in real time. 6. Conclusions Semantic labelling is an area of research that has become more relevant than ever in the recent years due to the ever-increasing presence of available structured data sources in the Web. Unfortunately, most of the existing approaches to label structured information have been devised with specific situations in mind, and thus do not offer a more complete solution due to their restrictions, namely: they only accept some structures as input, which greatly limits their applicability to only some sources of data; they are unable to label both records and attributes, which prevents them from fully labelling datasets; they are tied to certain features or techniques, without offering customisable models that can be expanded with new techniques or features that are suitable to specific cases; they assume that instances are labelled in groups that share the same class, having their performance hindered when 54 68 D. Ayala, I. Hernández, D. Ruiz et al. / Information Systems 83 (2019) 57–68 such groups are not available and datasets are labelled individually; they are tied to entity matching, thus being unable to label records or attributes that do not correspond to named entities; they do not detect numeric data, which provides additional information that can be crucial to the model; finally, they do not support complex features. In this article, we present TAPON-MT, a framework to perform semantic labelling based on machine learning techniques, with a features calculation and modelling architecture that does not present any of the aforementioned problems. It deals with both records and attributes from generic structures; it is highly customisable, being able to dynamically generate complex features using features groups; it labels instances in an individual basis without assuming there are groups; it does not require the presence of named entities or performing any kind of entity matching; it detects numeric data so that additional information can be used to compute features; and it supports complex features: similarity features (by storing examples from the training set), dynamically generated features (by using features groups), incremental features (by using the listener pattern), and hint-based features (by means of a two-phase workflow). We have implemented our framework to show its usability when creating models and testing them. We have also validated it using real-world data from the National Science Foundation RDF dataset, which includes a large number of varied classes in deep structures. Our validation results show that TAPON-MT is effective and efficient in practice, achieving accuracy results that are, at least, on par with other proposals even when having to label records in addition to attributes. These results suggest that our framework is promising enough for real-world semantic labelling scenarios. Acknowledgment Our work was supported in the Spanish R&D&I programme by grant TIN2016-75394-R. References [1] S.K. Ramnandan, Amol Mittal, Craig A. Knoblock, Pedro A. Szekely, Assigning semantic labels to data sources, in: ESWC, 2015, pp. 403–417, http://dx.doi. org/10.1007/978-3-319-18818-8_25. [2] Inma Hernández, Carlos R. Rivero, David Ruiz, Deep web crawling: a survey, World Wide Web, 2018, pp. 1–34. [3] Philip A. Bernstein, Laura M. Haas, Information integration in the enterprise, Commun. ACM 51 (9) (2008) 72–79, http://dx.doi.org/10.1145/1378727. 1378745, URL http://doi.acm.org/101145/13787271378745. [4] Maurizio Lenzerini, Data integration: A theoretical perspective, in: Proceedings of the Twenty-first ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 3-5, Madison, Wisconsin, USA, 2002, pp. 233–246, http://dx.doi.org/10.1145/543613.543644, URL http://doi.acm.org/ 101145/543613543644. [5] Natalya Fridman Noy, Semantic integration: A survey of ontology-based approaches, SIGMOD Rec. 33 (4) (2004) 65–70, http://dx.doi.org/10.1145/ 1041410.1041421, URL http://doi.acm.org/101145/10414101041421. [6] Michele Banko, Michael J. Cafarella, Stephen Soderland, Matthew Broadhead, Oren Etzioni, Open information extraction from the web, in: IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, January 6-12, 2007, 2007, pp. 2670–2676, URL http://ijcai. org/Proceedings/07/Papers/429pdf. [7] Tugba Özacar, A tool for producing structured interoperable data from product features on the web, Inf. Syst. 56 (2016) 36–54, URL http://dx.doi.org/ 101016/j.is.201509002. [8] Nicholas Kushmerick, Wrapper verification, WWW 3 (2) (2000) 79–94, http: //dx.doi.org/10.1023/A:1019229612909. [9] Kristina Lerman, Steven Minton, Craig A. Knoblock, Wrapper maintenance: A machine learning approach, J. Artificial Intelligence Res. 18 (2003) 149–181, http://dx.doi.org/10.1613/jair.1145. [10] Robert McCann, Bedoor K. AlShebli, Quoc Le, Hoa Nguyen, Long Vu, AnHai Doan, Mapping maintenance for data integration systems, in: VLDB, 2005, pp. 1018–1030, URL http://www.vldb2005org/program/paper/fri/p1018- mccann.pdf. [11] Jérôme Euzenat, Pavel Shvaiko, Ontology Matching, second ed., Springer, ISBN: 978-3-642-38720-3, 2013. [12] National Science Foundation. NSF Awards API specification. https://www. research.gov/common/webapi/awardapisearch-v1.htm. Accessed: 2018-06- 08. [13] Christian Bizer, Tom Heath, Tim Berners-Lee, Linked data - the story so far, Int. J. Semantic Web Inf. Syst. 5 (3) (2009) 1–22, URL http://dx.doi.org/104018/ jswis.2009081901. [14] Varish Mulwad, Tim Finin, Anupam Joshi, Semantic message passing for generating linked data from tables, in: ISWC, 2013, pp. 363–378, http://dx. doi.org/10.1007/978-3-642-41335-3_23. [15] Dominique Ritze, Oliver Lehmberg, Christian Bizer, Matching html tables to dbpedia, in: Proceedings of the 5th International Conference on Web Intelligence, Mining and Semantics, ACM, 2015, p. 10. [16] Ziqi Zhang, Effective and Efficient Semantic Table Interpretation using Tableminer+, Semantic Web, 2016, pp. 1–37, (Preprint). [17] Sotiris B. Kotsiantis, I. Zaharakis, P. Pintelas, Supervised machine learning: A review of classification techniques, Emerg. Artif. Intell. Appl. Comput. Eng. 160 (2007) 3–24. [18] Daniel Ayala, Inma Hernández, David Ruiz, Miguel Toro, TAPON: A two-phase machine learning approach for semantic labelling, Knowledge-Based Systems 163 (2019) 931–943. [19] Minh Pham, Suresh Alse, Craig A. Knoblock, Pedro A. Szekely, Semantic labeling: A domain-independent approach, in: International Semantic Web Conference (1), 2016, pp. 446–462, URL http://dx.doi.org/10.1007/978-3- 319-46523-4_27. [20] Girija Limaye, Sunita Sarawagi, Soumen Chakrabarti, Annotating and searching web tables using entities, types and relationships, PVLDB 3 (1) (2010) 1338–1347, URL http://www.comp.nus.edu.sg/vldb2010/proceedings/files/ papers/R118pdf. [21] Petros Venetis, Alon Y. Halevy, Jayant Madhavan, Marius Pasca, Warren Shen, Fei Wu, Gengxin Miao, Chung Wu, Recovering semantics of tables on the Web, PVLDB 4 (9) (2011) 528–538, URL http://www.vldb.org/pvldb/vol4/p528- venetis.pdf. [22] Sebastian Neumaier, Jürgen Umbrich, Josiane Xavie Parreira, Axel Polleres, Multi-level semantic labelling of numerical values, in: International Semantic Web Conference (1), 2016, pp. 428–445, URL http://dx.doi.org/10.1007/978- 3-319-46523-4_26. [23] Nicholas Kushmerick, Regression testing for wrapper maintenance, in: AAAI/IAAI, 1999, pp. 74–79, URL http://www.aaai.org/Library/AAAI/1999/ aaai99-011php. [24] Hannes Mühleisen, Christian Bizer, Web data commons - extracting structured data from two large web corpora, in: LDOW, 2012, URL http://ceurws.org/Vol-937/ldow2012-inv-paper-2pdf. [25] Valter Crescenzi, Giansalvatore Mecca, Paolo Merialdo, Roadrunner: Towards automatic data extraction from large web sites, in: VLDB, 2001, pp. 109–118, URL http://www.vldb.org/conf/2001/P109pdf. 55 56 6 ANEURAL NETWORK FOR SEMANTIC LABELLING OF STRUCTURED INFORMATION 57 Intelligent systems rely on rich sources of information to make informed decisions. Using information from external sources requires establishing correspondences between the information and known information classes. This can be achieved with semantic labelling, which assigns known labels to structured information by classifying it according to computed features. The existing proposals have explored different sets of features, without focusing on what classification techniques are used. In this paper we present three contributions: first, insights on architectural issues that arise when using neural networks for semantic labelling; second, a novel implementation of semantic labelling that uses a state-of-the-art neural network classifier which achieves significantly better results than other four traditional classifiers; third, a comparison of the results obtained by the former network when using different subsets of features, comparing textual features to structural ones, and domain-dependent features to domain-independent ones. The experiments were carried away with datasets from three real world sources. Our results show that there is a need to develop more semantic labelling proposals with sophisticated classification techniques and large features catalogues. Expert Systems With Applications 143 (2020) 113053 Contents lists available at ScienceDirect Expert Systems With Applications journal homepage: www.elsevier.com/locate/eswa A neural network for semantic labelling of structured information Daniel Ayala ∗ , Agustín Borrego , Inma Hernández , David Ruiz Universidad de Sevilla, ETSI Informática. Avda. de la Reina Mercedes, s/n, Sevilla E-41012, Spain a r t i c l e i n f o Article history: Received 11 February 2019 Revised 10 October 2019 Accepted 24 October 2019 Available online 2 November 2019 Keywords: Semantic labelling Information integration Neural networks a b s t r a c t Intelligent systems rely on rich sources of information to make informed decisions. Using information from external sources requires establishing correspondences between the information and known information classes. This can be achieved with semantic labelling, which assigns known labels to structured information by classifying it according to computed features. The existing proposals have explored different sets of features, without focusing on what classiﬁcation techniques are used. In this paper we present three contributions: ﬁrst, insights on architectural issues that arise when using neural networks for semantic labelling; second, a novel implementation of semantic labelling that uses a state-of-the-art neural network classiﬁer which achieves signiﬁcantly better results than other four traditional classiﬁers; third, a comparison of the results obtained by the former network when using different subsets of features, comparing textual features to structural ones, and domain-dependent features to domain-independent ones. The experiments were carried away with datasets from three real world sources. Our results show that there is a need to develop more semantic labelling proposals with sophisticated classiﬁcation techniques and large features catalogues. ©2019 Elsevier Ltd. All rights reserved. 1. Introduction Intelligent systems rely on rich information sources to make informed decisions. Frequently, they rely on external, independent sources of data to fulﬁll different tasks ( Chen, Jia, & Xiang, 2019 ) such as making recommendations ( Laudy & Ganascia, 2008 ), question answering ( Wu, Wang, Shen, Dick, & van den Hengel, 2016 ), internet ﬁnances ( Ding, Zhang, Liu, & Duan, 2016 ), plagiarism detection ( Franco-Salvador, Gupta, Rosso, & Banchs, 2016 ), or knowledge graph completion ( Chen et al., 2019 ). To that effect, these systems leverage information from a particular domain, usually available in well-known data exchange formats such as RDF or JSON, thanks to the increase in popularity of open data practices. However, to be able to use it, the system must ﬁrst integrate it by establishing correspondences between the data and known classes from a local ontology ( Pham, Alse, Knoblock, & Szekely, 2016 ). This is the goal of semantic labelling, which consists in labelling elements in data structures with known classes from a Web ontology. Semantic labelling proposals take structured data as input, and assign them one or several labels, which correspond to the classes that best describe them according to their features. Fig. 1 (a) shows an example of a structured dataset from the ∗Corresponding author. E-mail addresses: day[email protected] (D. Ayala), [email protected] (A. Borrego), [email protected] (I. Hernández), [email protected] (D. Ruiz). Jisc repository ( Jisc, 2018 ), displaying labelled information about a R&D project in the education domain. A semantic labeller would take as input some labelled sample data from this domain and learn a classiﬁcation model for each class in the ontology, such as “jisc:name”, “jisc:title”, or “jisc:start-date”. Then, it could apply these models to unlabelled datasets like the one in Fig. 1 (b), and infer a suitable class label for each element in the dataset. Consequently, semantic labelling can be seen as a classiﬁcation problem in which each element in a data structure is classiﬁed according to its features, considering any measurable aspect of a piece of data a potential feature for classiﬁcation. In the former example, instance I2 could be classiﬁed as a “jisc:title” after an analysis of some of its features, including the number of words that start with an uppercase letter and the position of the instance in the structure, I3 could be classiﬁed as a “jisc:start-date” because of the number of digits, and I10 could be classiﬁed as a “jisc:status” because programme statuses only have a few possible values (“Complete”, “Running”, etc.), and the value of the instance matches that of other known examples of the same class. The current trend in the state of the art proposals is to focus on feature engineering ( Ayala, Hernández, Ruiz, & Toro, 2019a; Neumaier, Umbrich, Parreira, & Polleres, 2016; Pham et al., 2016; Ramnandan, Mittal, Knoblock, & Szekely, 2015 ), that is, identifying new features that endow the classiﬁer with enough power as to discern between different classes, even when those classes are highly similar like “jisc:name” and “jisc:title”. Devising elaborate features is https://doi.org/10.1016/j.eswa.2019.113053 0957-4174/© 2019 Elsevier Ltd. All rights reserved. 58 2 D. Ayala, A. Borrego and I. Hernández et al. / Expert Systems With Applications 143 (2020) 113053 Fig. 1. Dataset examples. crucial to achieve good accuracy, and in our most recent proposal in the area of semantic labelling ( Ayala et al., 2019a ) it has resulted in a large explosion of features, with potentially hundreds of them. However, our study of the literature reveals that existing proposals are based on baseline classiﬁcation techniques, neglecting advanced classiﬁcation techniques that use the features eﬃciently. The most recent proposals only use traditional classiﬁcation algorithms like random forest or logistic regression. This motivated us to study whether applying more sophisticated techniques for classiﬁcation can indeed have a positive impact on classiﬁcation performance. Our contributions are the following: 1. We explore the potential of neural networks in the area of semantic labelling: while neural networks have been successfully applied to related tasks such as information extraction, to the best of our knowledge, they have not been used for semantic labelling before. We provide some insights on architectural issues that arise when using neural networks for semantic labelling. 2. We compare the semantic labelling performance achieved using a neural network versus four traditional classiﬁcation algorithms. 3. We study the effect on the performance of using certain subsets of features over others: since computation time is directly related to the number of features used, it is of utmost interest to choose features that help achieve a good classiﬁcation performance. Our experiments in several scenarios using real world data reveal that when using a neural network the labelling accuracy improves consistently, even when there is little margin for improvement. Regarding the impact of the selection of features, we found that all considered subsets had a positive effect in the accuracy. These insights should help lead the development of new semantic labelling techniques in intelligent systems, mainly when it comes to developing classiﬁcation models and large features catalogues. The rest of the paper is organised as follows: Section 2 reports on some preliminaries that are necessary to understand the domain of the problem; Section 3 describes the analysis of the state of the art; Section 4 describes the nature of features in semantic labelling; Section 5 contains a detailed description of the application of neural networks to semantic labelling; Section 6 describes the experiments we used to test our hypothesis and their results; ﬁnally, Section 7 recaps on our main conclusions. 2. Preliminaries In this Section, we introduce deﬁnitions of concepts related to the problem of semantic labelling. Class: a piece of text that denotes semantics in a Web ontology. The output of semantic labelling is a set of labels that should match the class of every data item. Example: classes “jisc:Project” and “jisc:start-date”. Attribute: A data item with a textual value that can be an instance of a class and have a label that denotes it. Note that in this context, an attribute does not refer to an element of a data model, but to a speciﬁc data item. It may be possible to have an attribute that does not belong to any class in a particular ontology, i.e., a piece of text that is automatically extracted from a website by a crawler but does not correspond to any known class. Example: in Fig. 1 (a) we can see some examples of attributes, one of the two attributes of class “jisc:name” has a textual value of “Support & Synthesis Project”, and the attribute of class “jisc:start-date” has a textual value of “01/08/2009”. In Fig. 1 (b) there are several attributes: I2 (a name), I3 (a start date), I5 (a title), I6 (a description), I7 (a DOI), I9 (a name), I10 (a homepage), and I11 (a status), but their class is unknown by the system. Note that attribute I7 is clearly a DOI, but since there does not exist a DOI class in the ontology, the semantic labeller would not be able to ﬁnd the right label. Record: A text-less data item that has other attributes or records as children; it can be an instance of a class, in which case it would have a label that denotes it. Record classes admit a certain degree of variability in their schemas, i.e., different records of the same class may have variable attributes and records if some of them are optional or have different multiplicity. Example: in Fig. 1 (a) there are four records. The “jisc:Project” record contains instances of classes “jisc:name”, “jisc:start-date”, “jisc:Organization”, “jisc:Article”, and “jisc:Programme”. Some of them are also records with their own instances, like the “jisc:Organization” record that has a “jisc:name”. Fig. 1 (b) also shows several records: I1 (a project), I4 (an article), and I8 (a programme). Note that I1 belongs to class “jisc:Project”, but it does not contain any “jisc:Organization” record, since it is optional. Dataset: A set of attributes and records in a hierarchical structure. Usually, there is a single root record at the ﬁrst level 59 D. Ayala, A. Borrego and I. Hernández et al. / Expert Systems With Applications 143 (2020) 113053 3 of the dataset, but nothing prevents the presence of several ones, having a forest-like structure. Example: Fig. 1 (a) displays a dataset with 4 records and 9 attributes, and the root is the “jisc:Project” record. Fig. 1 (b) displays a dataset with 3 records and 8 attributes, and the root is the I1 record. Model: A classiﬁer that takes attributes as the input, and outputs their label. A model could classify a single instance or a group of them. Example: a random forest classiﬁer that takes the attributes in Fig. 1 (b), computes some features, and outputs a label for each of them. Feature: A numeric or categorical measure that can be taken from an attribute or group of attributes. Let A be the set of all attributes, features can be denoted as f : A → R . Example: a feature that computes the number of digits in the textual value of an attribute, which in Fig. 1 (b) would output 0.0 for I2 and 8.0 for I3. Internal model: A model that learns from a set of examples (labelled attributes) by using features obtained from the data item themselves, without relying on external sources of data. Example: a classiﬁer that computes features related to the format of the attributes such as the number of uppercase letters or the average word length, and labels them using a random forest or logistic regression classiﬁer. External model: A model that learns from a set of examples by using at least one feature that requires an external knowledge base (e.g. YAGO, DBpedia) for its computation. These features are usually computed by mean of queries to the knowledge base. Example: a classiﬁer that queries DBPedia using the textual value of attributes and labels them with the class of the result with the highest score. 3. Related work In the literature, there are several types of proposals that are able to provide structured information with labels that describe it. These proposals have different goals, but they can all be applied to the problem of semantic labelling, which is why we include them in this analysis. Furthermore, these proposals work with different types of features; however, in our analysis, we focus on the type of classiﬁcation technique on which they are based, regardless of the speciﬁc features. Note that none of them use neural networks, and instead use more traditional techniques like random forest, linear regression, and nearest neighbour classiﬁers. The proposals by Limaye, Sarawagi, and Chakrabarti (2010) , Venetis et al. (2011) , Mulwad, Finin, and Joshi (2013) , Ritze, Lehmberg, and Bizer (2015) , and Zhang (2017) focus on labelling Web tables, which may include labels for individual cells, rows, columns, and relationships between columns. Tables can be transformed into generic structures, each row being a record, and its cells the attributes. These proposals use knowledge bases to perform the labelling. These contain a set of entities that belong to classes, and usually offer the possibility of querying them to obtain entities that seem to match the query. In most cases, tables are labelled in an iterative process by ﬁrst obtaining a set of candidate entities for each cell, then labelling the columns according to the most frequent classes among the candidate entities, and then reﬁning the candidates by limiting them to the column classes. These proposals are based on external models, since the classiﬁcation is ultimately based on the score of queries to external sources, which in turn usually depends on the TF-IDF score and cosine distances computed from the documents in the knowledge base. The labels are limited to the existing classes in the external source. The proposals by Ramnandan et al. (2015) , Pham et al. (2016) , Neumaier et al. (2016) , and Ayala, Hernández, Ruiz, and Toro (2019b) label attributes by comparing them to sets of examples of known classes. The labels are obtained through a classiﬁcation process, based on features such as the value of numeric attributes, string distance metrics, similarity metrics, or features related to the structure of the data. These proposals are based on internal modes. The proposal by Ramnandan et al. (2015) selects the class with the highest score when querying a Lucene index that contains examples of a class in each stored document. The proposal by Pham et al. (2016) uses a one-vs-all logistic regression classiﬁer with several similarity measures. The proposal by Neumaier et al. (2016) uses a nearest neighbour classiﬁer. The proposal by Ayala et al. (2019b) uses a one-vs-all random forest classiﬁer. In addition to the former proposals, those by Kushmerick (1999) , Lerman, Minton, and Knoblock (2003) and McCann et al. (2005) focus on information veriﬁcation, and their goal is to conﬁrm that a dataset is correct according to the reference model. They learn from a number of veriﬁed labelled examples, they compute the collections of values of each feature, and infer the statistical normal distributions that best ﬁt them. When a dataset must be veriﬁed, the values of its features are compared to the inferred distributions. If some of the values associated to an element or the entire dataset deviate too much from the veriﬁed ones according to statistical tests, the dataset is considered to be anomalous. Information veriﬁcation is very similar to semantic labelling, since verifying an already labelled dataset amounts to applying semantic labelling to re-compute the set of labels for the dataset and checking that the two sets of labels are identical. We have observed that the classiﬁcation of instances is not trivial when the number of classes is large. The similarity between classes may be such that even if the computed features hold enough information to differentiate classes, their eﬃcient use by a model may require complex non-linear combinations that represent a challenge to most techniques. For example, instances of classes “jisc:title” and “jisc:name” are usually similar, and correctly separating their classes could require a combination of several features related to their length, presence of certain characters or tokens, and other measures. The existing proposals use techniques that do not deal well with cases that require non-linearity, which motivated us to implement the novel application of neural network techniques to semantic labelling. 4. Features Features in the ﬁeld of semantic labelling do not necessarily measure the occurrence of speciﬁc words in the textual value of an attribute; instead, they are mostly related to its format, i.e., the kind of characters and tokens it contains, how long it is, or how similar it is to sets of examples according to different distance functions. The features catalogue does not necessarily depend on the particular classiﬁcation algorithm that is being applied, i.e., we can create several classiﬁers for semantic labelling using the exact same features. In the past, the features set used in related proposals was limited to around a dozen features ( Kushmerick, 20 0 0; Lerman et al., 2003; McCann et al., 2005 ). However, the most recent work has started to develop larger, more expressive sets of features to include as much information as possible in the input. One of the recent additions are the so-called parametric features ( Ayala et al., 2019a ). They are a kind of feature that ﬁts well this need to include as much low-level information as possible in the ﬁrst layer. They take a parameter, which means that each parametric feature results in a family of features, each of them related to a different 60 4 D. Ayala, A. Borrego and I. Hernández et al. / Expert Systems With Applications 143 (2020) 113053 Table 1 Features. ID Feature Domain Used information Domain dependency Description F1 Number of symbol occurrences A x S Textual Independent The number of occurrences in the attribute of symbols of type S (letters, numbers, punctuation, symbols, separators, other). The considered types can be customised. F2 Number of token occurrences A x T Textual Independent The number of occurrences in the attribute of token of type T (words starting with a lowercase letter, words starting with an uppercase letter followed by a nonseparator character, uppercase words, numeric strings, HTML tags). The considered types can be customized. F3 Symbol density A x S Textual Independent The density in the attribute of symbols of type S. The density is computed as the number of occurrences of a character type divided by the total number of symbols in the attribute. F4 Token density A x T Textual Independent The density in the attribute of token of type T. The density is computed as described in AF3 F5 Average shared preﬁx length A x C Textual Dependent Average length of the shared preﬁx between the text of the attribute and a set of stored examples of class C. The shared preﬁx is the set of characters that two attributes have in common in the beginning. If the attributes start with a different character, the length is 0. F6 Average shared suﬃx length A x C Textual Dependent Average length of the shared preﬁx between the text of the attribute and a set of stored examples of class C. The shared suﬃx is the set of characters that two attributes have in common in the end. If the attributes end with a different character, the length is 0. F7 Average edit distance A x C Textual Dependent Average Jaro edit distance between the attribute and a set of stored examples of class C. F8 Numeric Value A Textual Independent The numeric value of the text of the attribute if it matches a number pattern. -1.0 otherwise F9 Depth A Structural Independent The depth in the dataset of the attribute. F10 Same level attributes A Structural Independent The number of attributes at the same structural level. F11 Same level attributes A Structural Independent The number of records at the same structural level. value of the parameter. The parameter can be one of the known classes, so that each variant of the feature gives information related to it. For example, feature F 3 expands into 6 different features of the same family. Table 1 displays the ﬁnal features that we used. S denotes the set of all symbol types. T denotes the set of all token types. C denotes the set of attribute classes that are present in the training set. These features were selected from our former semantic labelling framework ( Ayala et al., 2019a ), which uses a collection of popular features taken from the state of the art. Since we focus on classiﬁcation techniques, we have not devised additional features, but there are other possible options, such as dictionarybased features ( Ren & Sohrab, 2013; Tagarelli, 2013 ), which rely on external knowledge-bases with deﬁnitions and relations of concepts. Note that several features are parametric, three of them on a per class basis. Features F 1 , F 2 , F 3 , and F 4 give information about the textual format of the attribute. Features F 5 and F 6 help detect starting and ending patterns. Feature F 7 measures overall similarity to each class. Feature F 8 gives additional information when an attribute has a numeric value that can be considered a feature itself. Features F 9 , F 10 and F 11 give information about the structure in which the attribute is present. Note how, for example, if we have trained a classiﬁer with three known classes: “jisc:title”, “jisc:name” and “jisc:start-date”, feature F 7 , “Average edit distance”, would have three versions: “Average edit distance to examples of class jisc:title/jisc:name/jisc:start-date”. With three classes there would be a total of 35 features. Since in the real world cases we have studied there can be dozens of classes, parametric features can result in a features explosion which is diﬃcult to handle for traditional classiﬁers. We have identiﬁed two different taxonomies to organise these features. According to the information used to compute the features, we can distinguish between structural and textual features. Another taxonomy distinguishes between groups of parametrical features that are computed per class, and therefore their size is proportional to the number of classes; and groups of features that are computed with independence to the number of classes, and therefore their size is ﬁxed. The former are domaindependent features, and the latter, domain-independent ones. Domain-dependent features result in a higher computational cost when the number of classes is high. 5. Our proposal In this Section we present the neural network we have devised. First, we describe the application workﬂow in which the neural network is framed. Then, we describe in detail the architecture of the network. Finally, we justify the choices in the architecture and analyse why some popular strategies could not be applied. 5.1. Workﬂow Fig. 2 summarizes the classiﬁcation workﬂow. The original input is a dataset containing several records and attributes. Each individual attribute is fed to a features calculator that computes the lowlevel features. The features must be any measurement that we can take from the text of an attribute and the structure of the dataset that contains it. The neural network should beneﬁt from a large number of low-level features that can later be combined. The features are used to create a vector that is fed to the ﬁrst layer of the neural network, whose size is always equal to the number of features. After going through the hidden layers, the output layer, whose size is always equal to the number of known classes, gives a score to each class, which is used to select the ﬁnal label. We label individual instances as opposed to labelling a group of several attribute instances that are known to share the same class. For example, the proposal by Ramnandan et al. (2015) would take as input a set of several dozens or hundreds of instances and output a single label for them. We consider individual labelling to be a more challenging task due to the limited information available during classiﬁcation. However, the application to groups of attributes would be trivial, simply requiring a change of features, so that they are computed from several instances instead of a single one. 61 68 7 AYNEC: ALL YOU NEED FOR EVALUATING COMPLETION TECHNIQUES IN KNOWLEDGE GRAPHS 69 The popularity of knowledge graphs has led to the development of techniques to refine them and increase their quality. One of the main refinement tasks is completion (also known as link prediction for knowledge graphs), which seeks to add missing triples to the graph, usually by classifying potential ones as true or false. While there is a wide variety of graph completion techniques, there is no standard evaluation setup, so each proposal is evaluated using different datasets and metrics. In this paper we present AYNEC, a suite for the evaluation of knowledge graph completion techniques that covers the entire evaluation workflow. It includes a customisable tool for the generation of datasets with multiple variation points related to the preprocessing of graphs, the splitting into training and testing examples, and the generation of negative examples. AYNEC also provides a visual summary of the graph and the optional exportation of the datasets in an open format for their visualisation. We use AYNEC to generate a library of datasets ready to use for evaluation purposes based on several popular knowledge graphs. Finally, it includes a tool that computes relevant metrics and uses significance tests to compare each pair of techniques. These open source tools, along with the datasets, are freely available to the research community and will be maintained. AYNEC: All You Need for Evaluating Completion Techniques in Knowledge Graphs Daniel Ayala1(B),Agust´ın Borrego1, Inma Hern´andez1, Carlos R. Rivero2, and David Ruiz1 1University of Seville, Seville, Spain {dayala1,borrego,inmahernandez,druiz}@us.es 2Rochester Institute of Technology, Rochester, NY, USA [email protected] Abstract. The popularity of knowledge graphs has led to the development of techniques to reﬁne them and increase their quality. One of the main reﬁnement tasks is completion (also known as link prediction for knowledge graphs), which seeks to add missing triples to the graph, usually by classifying potential ones as true or false. While there is a wide variety of graph completion techniques, there is no standard evaluation setup, so each proposal is evaluated using diﬀerent datasets and metrics. In this paper we present AYNEC, a suite for the evaluation of knowledge graph completion techniques that covers the entire evaluation workﬂow. It includes a customisable tool for the generation of datasets with multiple variation points related to the preprocessing of graphs, the splitting into training and testing examples, and the generation of negative examples. AYNEC also provides a visual summary of the graph and the optional exportation of the datasets in an open format for their visualisation. We use AYNEC to generate a library of datasets ready to use for evaluation purposes based on several popular knowledge graphs. Finally, it includes a tool that computes relevant metrics and uses significance tests to compare each pair of techniques. These open source tools, along with the datasets, are freely available to the research community and will be maintained. Keywords: Knowledge graph ·Graph reﬁnement ·Evaluation · Datasets 1 Introduction The recent years have seen an increase in popularity of the representation of large databases as graphs with nodes that represent entities and edges that represent relations between them. The advent of Linked Open Data [4], and the development of connected sources of structured data [1,5,13–15,19,22,23]have c Springer Nature Switzerland AG 2019 P. Hitzler et al. (Eds.): ESWC 2019, LNCS 11503, pp. 397–411, 2019. https://doi.org/10.1007/978-3-030-21348-0_26 70 398 D. Ayala et al. drawn attention towards the use of knowledge graphs to represent knowledge, as well as the development of techniques that work on graph data [2,10]. These graphs are not perfect and may be incomplete or contain errors [16]. The techniques that attempt to improve the quality of knowledge graphs are known in general as graph reﬁnement proposals [16], a category that includes two types of proposals: those that detect incorrect information on graphs, and those that complete the graphs with missing information. We focus on the latter, also known as knowledge graph completion proposals, or link prediction for knowledge graphs. Adding missing knowledge to a graph might be seen as a binary classiﬁcation problem in which the input is a triple <s,r,t> (source entity, relation, target entity, also known as subject, predicate, object) that represents an edge in the graph, and the output is a binary value denoting whether or not that triple should be included in the graph. There is a wide variety of graph completion proposals based on diﬀerent approaches like embeddings [9,21] or path-based features [8,11]. Deep learning techniques have seen popularity in the recent years [18]. However, their evaluation is not homogeneous, that is, each proposal is evaluated on diﬀerent knowledge graphs, using diﬀerent methodologies and metrics to analyse results. There are well-known knowledge graphs that are commonly used for evaluation purposes, such as Freebase [8,9,11,21] or WordNet [9,11,21]. However, when used for the speciﬁc task of evaluating graph completion proposals, these graphs are usually pre-processed by the diﬀerent authors, who apply diﬀerent criteria to obtain smaller and cleaner versions of the datasets, such as FB13 [21]or WN18 [6]. This makes it diﬃcult to compare diﬀerent proposals side by side, especially considering that evaluating graph reﬁnement proposals is not trivial with many considerations and variants [16]. There is a clear need for a standard suite that deﬁnes both datasets and metrics to be used in the evaluation of graph completion proposals. To fulﬁll that need, in this paper we present AYNEC (All You Need for Evaluating Completion), a resource for the evaluation of knowledge graph completion proposals that covers the entire evaluation workﬂow: preprocessing, training/testing splitting, generation of negative examples (which we refer to as negatives generation for the sake of brevity), and statistical analysis. The main contributions of AYNEC are: AYNEC-DataGen, a tool for the generation of evaluation datasets, which includes options for exporting the datasets in open formats for their easy visualisation, and oﬀers several variation points in the preprocessing, splitting, and negatives generation steps; AYNEC-ResTest, a tool for computing metrics and signiﬁcance tests from the results of several techniques in the statistical analysis step; and an initial collection of evaluation datasets generated from high quality subgraphs of popular knowledge graphs: WN11, WN18, FB13, FB15K, and NELL. If the speciﬁc datasets that we oﬀer are not suited for a certain task, or if new requirements arise in the future, AYNEC-DataGen allows to easily extend the collection with new datasets. 71 AYNEC: All You Need for Evaluating Completion Techniques 399 Our datasets can be freely downloaded from Zenodo1, under the CC BY 4.0 license. Our tools are open source and available as a public repository in GitHub2 under the GPLv3 license. The source code of the tools is documented, describing each conﬁgurable parameter and function. The rest of this paper is structured as follows: Sect. 2describes each step in the evaluation workﬂow that we have identiﬁed, Sect. 3shows what evaluation setups were used in several completion proposals in terms of the aforementioned workﬂow, Sect. 4describes how AYNEC-DataGen implements the dataset creation steps, Sect. 5describes AYNEC-ResTest, our metrics evaluation tool, Sect. 6describes the speciﬁc datasets we propose for homogeneous evaluation, and Sect. 7summarises our work and concludes the paper. 2Workflow We have identiﬁed the necessary steps to evaluate graph completion proposals, and we have deﬁned an abstract workﬂow that can be used to describe or compare diﬀerent evaluation setups in the same terms. Fig. 1. Knowledge graph completion evaluation workﬂow. Figure 1depicts the evaluation workﬂow we have identiﬁed, which is composed of ﬁve steps. The external inputs are the original knowledge graph to use for evaluation, the techniques that are evaluated, and the relations on which the techniques will be evaluated. The ﬁnal output is the comparison of the techniques according to a number of metrics and signiﬁcance tests. For example, Gardner and Mitchell [8] take Freebase and NELL as original graphs, and evaluate two techniques on a total of 34 relations according to the metrics MAP and MRR. 1http://doi.org/10.5281/zenodo.1744988. 2https://github.com/tdg-seville/AYNEC. 72 400 D. Ayala et al. The shadowed steps in Fig. 1(preprocessing, splitting, negatives generation, and metrics analysis) are the ones covered by our suite, while triple classiﬁcation is the main task to be performed by each completion proposal. Next, we discuss every step, its inputs and outputs, and we provide examples basedonFig.1. 2.1 Preprocessing The goal of this step is to load and preprocess the original knowledge graph (which may have undergone previous preprocessing) in any way that is considered convenient. This can include, for example, the removal of relations with frequency below a threshold, the transformation of entity or relation names, or the insertion of new relations to enrich the graph. Regarding the input, in some knowledge graphs, entities have literals attached that represent simple values related to the entity (e.g. data properties in DBpedia [1]). In other graphs, this kind of data is represented with additional nodes (e.g., a node that represents the year 2008, as happens in NELL [14]). The input to this step is a knowledge graph that represents entities as nodes, and relations between them as edges. The output is an updated version of the original knowledge graph. In the example of Fig. 1, relations with less than 20% of the total edges are removed. 2.2 Splitting Evaluating techniques require using at least two sets: training and testing. The training set is the only part of the graph available when training a model, which is afterwards evaluated on the testing set. The goal of the splitting step is to divide the edges in the original graph into two disjoint sets (training and testing). This way, we simulate a controlled scenario of incompleteness in which we know the missing edges (the testing set). The testing set is usually a small fraction of the graph edges, ranging from 10% to 30%. Diﬀerent strategies can be used to split the original dataset. For example, the edges taken for the testing set could be completely random, or we could take a ﬁxed fraction of each relation for testing. The input to this step is the preprocessed knowledge graph. The outputs are two disjoint sets of edges from the input graph, corresponding to the training and testing sets. In the example of Fig. 1, 50% of the edges of each relation are taken for the testing set. 2.3 Negatives Generation The goal of this step is to generate negative triples, usually by creating new ones that are not found in the original knowledge graph. The negative examples in the training set help learn a model. Their inclusion is optional, since the techniques themselves may be able to generate them. 73 AYNEC: All You Need for Evaluating Completion Techniques 401 The negative examples in the testing set are used to compute metrics like precision or recall. If negatives are not explicitly included in the testing set, any triple that is not found in the training or testing sets would be a negative when computing metrics. This would be the case, for example, if we want to test a technique that, instead of giving a score to input triples, outputs a set of triples as the positives, and assumes every other triple is negative. The negative examples, when generated, should pose a challenge for the classiﬁcation model [21]. For instance, it is trivial to classify <John-S., cousin-of, Republic-of-Guatemala>as false by checking that “Republic-of-Guatemala” is outside the range of relation “cousin-of”. A more compelling example would be <John-S, cousin-of, Mary-S.>, in which the former sanity check is not enough. The ﬁrst point of variability when generating negative examples is how many of them should be generated. Usually, a ﬁxed numbers of negative examples are generated per each positive example. The second point of variability is the generation strategy. The idea is to take a positive example and change its source, target, or both, by choosing a replacement among a set of candidates. Some proposals [9,11,21] select as candidates the entities that are known to appear in the same position of the same relation, keeping the domain (if it is the source) or range (if it is the target) to avoid trivial cases like the <John-S., cousin-of, Republic-of-Guatemala>example. Others follow more elaborate approaches, such as giving a higher probability to nodes that are close to the original ones [8]. One of the problems when generating negative examples is that knowledge graphs are usually ruled by the open world assumption, which means that the absence of a triple in the graph does not necessarily mean that the triple is not true, just unknown. However, since knowledge graphs tend to be sparse, the probability of a true missing edge being chosen as a negative example should be negligible, which is why related datasets in practice follow a closed world assumption [8,9,11,21]. The inputs to this step are the testing set and, optionally, the training set. The outputs are the sets with added negative edges. In the example of Fig. 1 one negative example is generated for each positive one by changing the target entity while keeping the range of the relation. 2.4 Triple Classification The result of this step is a set of classiﬁcations per technique and triple, which may be a binary result (usually 1 or −1), or a probabilistic score. Some techniques do not explicitly classify triples, but output a set of new triples after learning from the training set, or output a source/target node for a query such as <John- S, father-of, ?>. In these cases, there is also a latent classiﬁcation: the former classiﬁes any triple that is not part of the output as negative, while the later classiﬁes the triples in a group obtained by the query (e.g., all triples with John-S as source and father-of as relation). 74 402 D. Ayala et al. Since a knowledge graph may contain thousands of relations, the evaluation of techniques is usually limited to the few ones that are considered specially frequent or relevant [8,11,21]. The inputs of this step are the training and testing sets, the set of techniques to be compared, and the set of relations to test. The output is the set of results from applying each technique to each edge of the input relations in the testing set. In the example of Fig. 1four techniques are compared, and only two of the three existing relations are evaluated. 2.5 Statistical Analysis The goal of this step is to generate a report that summarises the results obtained in the classiﬁcation step with metrics used to evaluate each technique. The results of the classiﬁcation can be used to generate a confusion matrix for each evaluated relation, obtaining metrics like precision or recall. The metrics are usually focused on precision [8,11], since the added knowledge, even if it is a small amount, should be reliable. A proposal with high recall but poor precision results in a high number of false positives that have to be manually checked and removed, defeating the purpose of automated graph reﬁnement. The diﬀerence between techniques regarding each metric is assessed with signiﬁcance tests, usually paired ones (the observations of a sample can be paired with those of another sample) computed from the metrics of each relation [8,11]. The input of this step is the set of classiﬁcation results from each technique. The output is a report with metrics and a comparison of the techniques. In the example of Fig. 1precision, recall, and F1are measured for each relation, and a signiﬁcance test is used to compare the diﬀerences between techniques. 3 Related Datasets Our study of the literature reveals that there is no consensus when it comes to evaluating graph completion proposals. Next, we describe several evaluation datasets in a non-exhaustive study to show that there is variability and what the popular choices are in the workﬂow. Table 1summarises our ﬁndings. Table 1. Summary of related datasets. 75 AYNEC: All You Need for Evaluating Completion Techniques 403 Socher et al. [21] evaluate their proposal using Freebase [5]andWordNet[13] as their original graphs. Preprocessing removes all but 13 relations from the People domain in Freebase, and all but 11 in WordNet. During splitting, they take around 10% of the edges for testing, and remove what they call “trivial test tuples”, described as tuples from the testing set in which either or both of their two entities also appear in the training set in a diﬀerent relation or order. They generate one negative per positive in the testing set by switching the target entity of the positive. Regarding Freebase, they keep the domain/range of the relation, but since in WordNet all entities share the same type (word), all entities are actual potential candidates. During triple classiﬁcation, they only test 7 relations from Freebase and all relations from WordNet. They measure the accuracy per relation of their proposal, and the average across relations when comparing several proposals, without using signiﬁcance tests. Gardner and Mitchell [8] use Freebase and NELL as their original knowledge graphs. During preprocessing they remove some Freebase relations considered too speciﬁc or unhelpful. During splitting, they take 25% of the edges for testing. They do not mention how many negatives are generated, but the datasets they provide show a variable number, usually more than 5 negatives per positive in both training and testing sets. They generate them by changing the source and target in each positive, keeping the domain and range, and weighting candidates by personalised page rank to favour nearby entities. Testing is limited to 25 relations from Freebase (random ones with a number of instances between 1000 and 10000, excluding those with Freebase’s mediators [3]), and 10 relations from NELL (the ones with highest frequency and reasonable precision). They measure mean average precision (MAP) and mean reciprocal rank (MRR), using an undisclosed paired permutation test to measure signiﬁcance. Ji et al. [9] use Socher et al. [21]’s datasets (FB13 and WN11) as the original graphs, adding Freebase 15K (FB15K) [7]. There is no additional preprocessing. Splitting is the same as the original datasets, which in the case of FB15K is 20% for testing. Since FB15K does not include negative examples in the testing set, they are generated in the same way as Socher et al. The relations used for testing are the same as Socher et al. [21], and all relations for FB15K. They measure the accuracy per relation, without using signiﬁcance tests, since they only report on the results of their proposal. Mazumder and Liu [11] use a subset of WordNet with only 18 relations (WN18) [6], FB15K, and ConceptNet [22] as original graphs. During preprocessing, they keep from FB15K 1000 triples from each of 25 randomly selected relations with more than 1000 instances, all triples from WN18, and all triples from relations with more than 1000 instances from ConceptNet (18 in total). During splitting, they take 20% of the edges for testing. They generate four negatives per positive in both training and testing sets. Two are generated by changing the source, and other two by changing the target, both keeping the domain/range of the relation. Testing includes all relations. They measure MAP and averaged F1across relations, using a paired t-test to measure signiﬁcance. 76 404 D. Ayala et al. 4 AYNEC-DataGen AYNEC-DataGen, our datasets generation tool, implements the ﬁrst three steps of the workﬂow in Fig. 1with several variation points. Next we describe how our tool implements the aforementioned steps of the workﬂow, presenting the variation points (VP) that can be conﬁgured. 4.1 Preprocessing AYNEC-DataGen takes as input a ﬁle with the input graph. Note that the most popular graphs we have identiﬁed (Freebase, WordNet, NELL) do not include literals, but use the additional nodes we mentioned in Sect. 1. VP1. Fraction of the graph: The original knowledge graph can be read entirely or only a fraction of it. Each triple has a conﬁgurable probability of being ignored, which can be useful to generate reduced versions of large knowledge graphs. VP2. Relation frequency threshold: Relations with a frequency below a given threshold can be removed. This is useful to remove very speciﬁc relations that may be problematic. VP3. Relation accumulated fraction threshold: A fraction can be set so that only the most frequent relations that cover that fraction of the edges are retained, removing the rest. This is useful to remove large amounts of relations with low frequency while keeping most of the graph intact. VP4. Inverse removal: Relations r1and r2are inverses of each other if for each instance of r1, there is an instance of r2with swapped source and target, and vice versa. If this option is toggled, one of the relations in each pair of inverses is removed. This reduces the size of the datasets without removing actual information, and avoids situations where triples are trivially classiﬁed as true merely by checking that the inverse relation exists between the entities, which may happen with some datasets [8,24]. 4.2 Splitting The triples resulting from preprocessing are split into the training and testing sets. VP5. Testing fraction: The graph can be split using a fraction that is applied to every relation, so that said fraction is taken from the triples of each relation for testing. VP6. Testing fraction per relation: The graph can be split using a fraction for each existing relation, so that, for each relation, the speciﬁed fraction is taken from its triples for testing. This enables full control of the representation of each relation in the testing set. 77 AYNEC: All You Need for Evaluating Completion Techniques 411 11. Mazumder, S., Liu, B.: Context-aware path ranking for knowledge base completion. In: Proceedings of the 26th International Joint Conference on Artiﬁcial Intelligence, pp. 1195–1201 (2017). https://doi.org/10.24963/ijcai.2017/166 12. McFee, B., Lanckriet, G.R.: Metric learning to rank. In: Proceedings of the 27th International Conference on Machine Learning, pp. 775–782 (2010) 13. Miller, G.A.: WordNet: a lexical database for English. Commun. ACM 38(11), 39–41 (1995). https://doi.org/10.1145/219717.219748 14. Mitchell, T.M., et al.: Never-ending learning. Commun. ACM 61(5), 103–115 (2018). https://doi.org/10.1145/3191513 15. Pasca, M., Lin, D., Bigham, J., Lifchits, A., Jain, A.: Organizing and searching the world wide web of facts - step one: the one-million fact extraction challenge. In: AAAI, pp. 1400–1405 (2006) 16. Paulheim, H.: Knowledge graph reﬁnement: a survey of approaches and evaluation methods. Semant. Web 8(3), 489–508 (2017) 17. Paulheim, H., Bizer, C.: Improving the quality of linked data using statistical distributions. Int. J. Semant. Web Inf. Syst. 10(2), 63–86 (2014). https://doi.org/ 10.4018/ijswis.2014040104 18. Schlichtkrull, M., Kipf, T.N., Bloem, P., van den Berg, R., Titov, I., Welling, M.: Modeling relational data with graph convolutional networks. In: Gangemi, A., et al. (eds.) ESWC 2018. LNCS, vol. 10843, pp. 593–607. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-93417-4 38 19. Shao, B., Wang, H., Li, Y.: The trinity graph engine. Microsoft Research 54 (2012) 20. Singh, S., Subramanya, A., Pereira, F., McCallum, A.: Wikilinks: a large-scale cross-document coreference corpus labeled via links to Wikipedia. University of Massachusetts, Amherst, Technical report UM-CS-2012 15 (2012) 21. Socher, R., Chen, D., Manning, C.D., Ng, A.Y.: Reasoning with neural tensor networks for knowledge base completion. In: Advances in Neural Information Processing Systems, pp. 926–934 (2013) 22. Speer, R., Havasi, C.: Representing general relational knowledge in ConceptNet 5. In: LREC, pp. 3679–3686 (2012) 23. Suchanek, F.M., Kasneci, G., Weikum, G.: YAGO: a core of semantic knowledge. In: WWW 2007, pp. 697–706 (2007). https://doi.org/10.1145/1242572.1242667 24. Toutanova, K., Chen, D.: Observed versus latent features for knowledge base and text inference. In: Workshop on Continuous Vector Space Models and their Compositionality, pp. 57–66 (2015) 25. Woolson, R.: Wilcoxon Signed-Rank Test. Wiley Encyclopedia of Clinical Trials, pp. 1–3 (2007) 84 8 LEAPME: LEARNING-BASED PROPERTY MATCHING WITH EMBEDDINGS 85 Data integration tasks such as the creation and extension of knowledge graphs involve the fusion of heterogeneous entities from many sources. Matching and fusion of such entities require to also match and combine their properties (attributes). However, previous schema matching approaches mostly focus on two sources only and heavily rely on the similarity of property names. They thus face problems in challenging use cases such as the integration of heterogeneous product entities from many sources. We therefore present a new machine learning-based property matching approach called LEAPME (LEArning-based Property Matching with Embeddings) that utilizes numerous features of both property names and instance values. The approach heavily makes use of word embeddings to better utilize the domain-specific semantics of both property names and instance values. Our comparative evaluation against three baselines for several multi-source datasets with real-world data shows the high effectiveness of LEAPME. We also show that our approach is even effective when training data from another domain (transfer learning) is used. LEAPME: Learning-based Property Matching with Embeddings Daniel Ayala University of Seville ETSI Inform´ atica, Avda. de la Reina Mercedes, s/n Seville, Spain [email protected] Inma Hern´ andez University of Seville ETSI Inform´ atica, Avda. de la Reina Mercedes, s/n Seville, Spain inmaher[email protected] David Ruiz University of Seville ETSI Inform´ atica, Avda. de la Reina Mercedes, s/n Seville, Spain [email protected] Erhard Rahm Leipzig University Institut f¨ ur Informatik Leipzig 04109, Germany [email protected] ABSTRACT Data integration tasks such as the creation and extension of knowledge graphs involve the fusion of heterogeneous entities from many sources. Matching and fusion of such entities require to also match and combine their properties (attributes). However, previous schema matching approaches mostly focus on two sources only and heavily rely on the similarity of property names. They thus face problems in challenging use cases such as the integration of heterogeneous product entities from many sources. We therefore present a new machine learning-based property matching approach called LEAPME (LEArning-based Property Matching with Embeddings) that utilizes numerous features of both property names and instance values. The approach heavily makes use of word embeddings to better utilize the domain-specific semantics of both property names and instance values. Our comparative evaluation against three baselines for several multi-source datasets with real-world data shows the high effectiveness of LEAPME. We also show that our approach is even effective when training data from another domain (transfer learning) is used. PVLDB Reference Format: Daniel Ayala, .... LEAPME: Learning-based Property Matching with Embeddings. PVLDB, xx(xxx): xxxx-yyyy, 2020. DOI: https://doi.org/10.14778/xxxxxxx.xxxxxxx 1. INTRODUCTION Data integration tasks such as the creation and refinement of knowledge graphs have to increasingly deal with the This work is licensed under the Creative Commons Attribution- NonCommercial-NoDerivatives 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-nd/4.0/. For any use beyond those covered by this license, obtain permission by emailing [email protected]. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. xx, No. xxx ISSN 2150-8097. DOI: https://doi.org/10.14778/xxxxxxx.xxxxxxx matching and fusion of data from many sources, e.g., different web sites, already created knowledge bases and repositories. Such knowledge graphs (KG) physically integrate numerous entities with their properties (attributes) and relationships as well as associated metadata about entity types and relationship types in a graph-like structure [26]. Many companies (including Google, Facebook, and Amazon) are increasingly relying on the integrated and curated information in knowledge graphs and there is also an increasing amount of research on KG creation [12, 35, 33, 37, 3, 8, 21, 31] and KG exploitation, e.g. for question answering [38, 17]. Integrating new data sources and their entities into a KG is challenging due to the typically large number of different kinds of entities and relationships, the high degree of heterogeneity in their representations and the often low data quality with frequently incomplete, wrong or contradicting information. Subproblems to deal with include the categorization, matching, clustering and fusion of entities. These steps in turn also require to match the properties of entities, e.g., to focus entity matching on comparable properties or to fuse the values of equivalent properties. Matching properties is far from trivial, especially with many sources. As an example, Fig. 1 shows camera entities (from a real dataset used in our evaluation) from four sources that may have to be integrated into a product KG together with some property matches indicated by symbols of the same shape. The example shows that there are numerous similar but differently named properties with diverse instance values. Matching properties often have completely different names, e.g., for properties “camera resolution”, “effective pixels” and “megapixel”. A property in one source, e.g. ”shutter speed”, may also have several matches in another source, e.g., ”min shutter speed” and ”max shutter speed”. The instance values also show a high degree of heterogeneity due to the use of synonyms, abbreviations, different technical units, or numeric values, making it difficult to find matches with standard techniques that rely on string similarity metrics. The number of properties per entity may also differ to a large degree between sources and even within 1 86 <page title>: "Kodak DC220 digital camera prices...", aperture: "F/4.0-4.8", autofocus: "Contrast Detect\n/ Live View\n/ Single", brand: "Kodak", category: "Digital Cameras", digital zoom: "2x", exposure compensation: "-/+ 2 EV range, in 1/2 EV steps", flash modes: "Auto / Fill-in / Off", focal length equivalent to 35mm: "29 - 58 mm", image ratio: "4:3", image resolutions: "640x480", light sensitivity iso: "140", live view: "Yes", lowest recommended price: "Rs.3,894.19 - http://www...", max shutter speed: "1/362", min shutter speed: "1/2", optical zoom: "2x", product name: "Kodak DC220", product rating": "0 out of 5", resolution: "0.9 MP", screen size: "2\"", sensor type: "CCD", user reviews: "Write a review", viewfinder type: "Optical", weight: "550 g" <page title>: "Nikon D3300 Kit with 18-55mm VR II Len...", aspect ratio: "3:2", battery: "EN-EL14a lithium-ion battery and charger", continuous shooting: "Yes (5.fps)", dimensions w x h x d: "124 x 98 x 76 mm (4.88 x 3.86 x...", effective pixels: "24 megapixels", focal length fmm: "1.5\u00d7", gps: "None", hdmi: "Yes (mini-HDMI)", image processor: "Expeed 4", image stabilisation: "No", iso sensitivity: "Auto, 100, 200, 400, 800, 1600, 3200,...", lcd type: "Fixed", lens mount: "Nikon F mount", max resolution: "6000 x 4000", microphone: "Mono", sensor size: "APS-C (23.5 x 15.6 mm)", sensor type: "CMOS", shutter speed: "30 sec - 1/4000 sec", storage type: "SD/SDHC/SDXC", total pixels: "25 megapixels", usb: "USB 2.0", viewfinder: "Optical (pentamirror), 95%", weight inc batteries: "430 g (0.95 lb / 15.17 oz)", wireless: "Optional" Eglobalcentral.co.uk <page title>: "Fujifilm Finepix Z70 Price In India...", aperture range: "F4.0 (W) - F4.8 (T)", audio formats: "WAV", auto focus: "Yes, Contrast Detect, Tracking, Single, Live...", camera resolution: "12 MP", digital zoom: "6.3x", focal length: "6.4 - 32 mm (35 mm Equivalent to 36 – 180...", image format: "JPEG ( Fine & Normal JPEG Quality )", image stablizer: "Yes", iso rating: "100 - 1600", lens type: "Fujinon 5x optical zoom lens", manual focus: "No", maximum shutter speed: "1/2000 sec", minimum shutter speed: "4 Sec", optical zoom: "5x", other focus features: "Normal Focus Range (80 cm)...", self timer: "Yes, 2 or 10 sec, Couple, Group", video format: "AVI", white balancing: "White Balance Presets (6), Custom..." Mypriceindia.com <page title>: "Pentax K-5 II + 18-55 mm WR – Digital...", battery type: "D-LI90 Lithium-ion battery", box contents: "AV cable USB cable Li-ion battery D-LI90...", colour of product: "Black", compatible memory cards: "SD/SDHC/SDXC", dimensions w x d x h: "131 x 72.5 x 97 mm", interface: "Mini-HDMI and AV outputs compatible with...", iso sensitivity: "80 to 51 200", lcd screen size: "3.0", lens type: "18-55MM WR Lens", megapixel: "16", sensor type: "CMOS", type: "Single Lens Kit", warranty: "1 Year", weatherproof: "Yes", weight: "760 g", white balance: "Auto Daylight Shade Cloudy Fluorescent..." Ilgs.net Shopmania.in Figure 1: Camera properties from different sources. Two properties from different sources being annotated with the same shape denotes a match. a source. To help solve the property matching problem in the case of such scenarios, we present a new approach called LEAPME (LEArning-based Property Matching with Embeddings). It uses machine learning and makes use of the typically good availability of instance data and already existing matches in a KG. LEAPME applies a dense neural network and a large set of features to classify a pair of properties from different sources as related or not. The proposed features make heavy use of word embeddings computed from both the property names and their instance values. Word embeddings are numeric vectors associated to single words, created so that they preserve their semantics. The use of embeddings gives the classifier information about the semantic proximity between two properties even when their string similarity is low. For example, we expect different words related to camera resolution such as “MP”, “resolution” or ”megapixels” to have similar embedding vectors. The use of property values provides additional information that is not tied to the name of a property, and makes the proposal applicable to scenarios in which the properties do not have meaningful names, e.g., identifiers that are automatically generated by information extraction approaches [29]. Specifically, we make the following contributions: •We propose LEAPME, a new learning-based approach for property matching that is applicable for data integration of many sources, e.g., as needed for KG creation and refinement. We propose the use of numerous features derived from both the property names and 2 87 property values and the heavy use of word embeddings for high match quality. •We comprehensively evaluate LEAPME on four realworld datasets with entities from several e-commerce sources. We also provide a comparison with three baselines and show that LEAPME clearly outperforms previous approaches even with little training data. •We show that LEAPME is also effective with training data obtained from entities of a different type or domain. The reduced need for domain-specific training data increases the applicability of the new approach. In the next section, we describe related work on schema matching and the previous use of machine learning for this task. Section 3 describes LEAPME in detail. Section 4 contains the evaluation including the comparison with several baselines and the use of transfer learning. Section 5 summarizes our contributions and discusses potential future work. 2. RELATED WORK In the last decades, a huge amount of research has been devoted to schema and ontology matching to automatically determine corresponding schema attributes (properties) and ontology concepts. As described in several survey articles and books [27, 14, 6, 7, 22], most of the proposed approaches focus on pairwise matching between two schemas or ontologies and utilize a combination of several similarity values to determine likely matches. The most common approach is to determine the linguistic similarity of property/concept names either based on string similarity metrics or synonym information from background knowledge resources such as dictionaries (e.g., WordNet [19]). Some approaches additionally utilize the structural similarity of elements (e.g., based on the similarity of neighbors in an ontology) and the similarity of associated instance data [24]. These approaches have materialized in numerous matching prototypes; we have used two of those existing tools, which have performed well in OAEI (ontology alignment evaluation initiative) contests as representative baselines in our comparative evaluation: Agreementmaker Light (AML) [15] and FCA-Map [9]. These tools can utilize several similarity values but heavily rely on linguistic name similarities. They do not use machine learning to learn optimized similarity thresholds but require the user to fine-tune parameters manually or with the help of some technique [28]. In particular, AML compares property names by doing a full-name match and computing word similarity, string similarity, and WordNet similarity. If any of the matchers returns a similarity above a user-given threshold (0.6 by default), the pair is considered a match. FCA-Map applies lexical matching to properties based on exact token co-occurrence. Both apply structural matching, but only to refine class and instance matches respectively. The use of supervised machine learning is being increasingly applied for a simplified configuration of schema and ontology matching [34, 20, 32, 18, 13, 11, 32, 10]. The training data consists of the similarity of matching and nonmatching pairs of schema/ontology elements together with multiple similarity values, e.g., according to different linguistic and structural similarities. Surprisingly, instance similarities have not been utilized so far in these approaches. As a representative baseline we consider the approach of Nezhadi et al. [20] in our evaluation that uses 12 name string similarity metrics as well as metrics derived from background knowledge by computing the distance of two concepts in the WordNet graph, and structural metrics based on the propagation of name similarities. They also considered 5 classification alternatives to determine matches and found out that an AdaBoost aggregation of Decision Tree classifiers achieves the best results. The main limitation of supervised machine learning techniques is the need for training data. There are two main ways to deal with this requirement: manual provision of training data or the use of transfer learning. Manually labelling selected pairs of properties or concepts is of course laborious and does not scale well. This approach thus has to be limited to relatively small amounts of training data. With transfer learning the goal is to obtain the training from another domain or use case to avoid the provision of specific training [13]. This is especially valuable for scenarios such as knowledge graphs, in which there are typically already integrated entities and properties from different sources so that matching information can likely be reused. In our evaluation, we will consider both approaches: the use of manually defined training matches as well as the use of transfer learning. Most previous work focuses on pairwise schema and ontology matching for two sources [25] while we have to deal with an arbitrary number of sources with different sets of properties per entity type. While multi-source property matching also builds on pairwise property matching, the degree of heterogeneity and thus the difficulty to achieve good match quality increase with more sources. In our approach, we will determine pairwise similarities between properties that can be maintained in a similarity graph of properties from several sources. Such a graph can be used as input for clustering so that all matching properties are in the same cluster that can be used as a basis to fuse these properties. Property clustering is beyond the scope of this paper but can be done with similar algorithms to those used for clustering entities based on a similarity graph, e.g., [16, 30]. 3. OUR APPROACH We first provide some definitions and define the problem we deal with in Section 3.1. Next, we give an overview of LEAPME (Section 3.2) and describe in detail how features are computed (Section 3.3). We discuss the use of embeddings in Section 3.4. Finally, we describe aspects related to the implementation of LEAPME in Section 3.5. 3.1 Problem definition The following definitions are relevant for our problem of property matching: Source: A source Sis a location from where information comes from, e.g., a website, a relational database, or a SPARQL endpoint, among other examples. It typically conforms to some kind of ontology and may contain structured entities of several types or classes. The example in Figure 1 contains camera entities from four different sources, namely e-commerce websites such as “Mypriceindia.com” and “Shopmania.in”. Entity and class: An entity eis a representation of something that can be uniquely identified, usually corresponding to some real world object. Entities belong 3 88 to a certain source and a source-specific type or class C, and we denote the source and class of entity ewith S(e) and C(e), respectively. The rectangles in Figure 1 correspond to different entities of type ”camera”: “Fujifilm Finepix Z20”, “Nikon D3300”, “Kodak DC220”, and “Pentax K-5 II”. Entities consist of several properties and their values. Property and instances: A property is an attribute to describe information about entities. The values of a property are literals known as instances. Our algorithm processes a collection of property instances represented as tuples (p, e, v) where pis the property name, eis the entity (identifier), and vis the property value. An example instance is (“camera resolution”, “Fujifilm Finepix Z20”,“12 MP”). The components of a property instance i=(p, e, v) are denoted by p(i), e(i), and v(i). Each such tuple is implicitly tied to the originating class C(e(i)) and source S(e(i)). Class schema: For the sake of flexibility in applications such as E-commerce, we do not assume the existence of a predefined schema with a fixed set of properties per class. Rather, we view the schema of class C as the collection of all differently named properties for entities of class C in the respective sources. Individual entities may thus use any subset of these class properties. Property matching: Task of determining correspondences between the properties of different class schemas from different sources. We address property matching for properties of the same class (e.g. camera properties). We consider the case of multi-source matching so that properties may relate to entities from an arbitrary number of sources. Correspondences are not limited to equivalence relationships but also to more complex relationships between semantically related properties. A property in one source may thus have 0, 1 or several matching properties in another source, e.g., as for property ”shutter speed” in Figure 1. The problem of property matching can thus be defined as follows. We use as input a collection of property instances from msources with m > 1. To enable the application of machine learning (ML) techniques, we also assume the provision of training data consisting of pairs of property instances from different sources labelled as either matching or non-matching. The goal is to determine all pairs (pi, pj, sim) of matching properties piand pjbetween any two sources together with their similarity indicating the strength of relatedness. The determined match correspondences represent a similarity graph between properties of different sources. Such a graph can be used for determining clusters of matching properties, e.g., using clustering algorithms like transitive closure or more complex approaches as in [16, 30]. A simple transitive closure would group all same-shaped properties in Figure 1 within a cluster. This would be sub-optimal if we want to ensure that only equivalent properties are grouped together, e.g., as useful for a fusion of property values within a KG. In such a case the properties ”min shutter speed” and ”max shutter speed” should be in separate clusters. This can be achieved with clustering techniques like in [30] that do not permit more than one cluster member from the same source. An alternative approach is to post-process the match correspondences, adopting a similar approach as in [2] that can determine the semantic type of correspondences (such as equality, is-a, and part-of) and only continue with equality correspondences. The analysis of such post-processing options is beyond the scope of this paper and left for future work. 3.2 Overview LEAPME is an ML-based property matching approach that focuses on the use of novel features. It computes features from property instances, property names, and property pairs to obtain large feature vectors that can be properly handled by a classifier. For example, from the instance value “12 MP” we can compute features such as the number of digits (2), the number of white spaces (1), or the fraction of letters (0.4). LEAPME thus uses such characteristics about instance values (and property names) in addition to their actual values. Algorithm 1 describes the main steps of LEAPME; the workflow is also illustrated in Figure 2. 1. First, there is the initialization of the instance feature vector IF , the property feature vector P F , the property pair feature vector P P F , and the output similarity graph (collection of matches) Sim (line 1 of Algorithm 1). 2. Next, the instance features are determined by every instance with the help of function iF eatures, and added to the respective property in the instance feature vector IF (lines 2-3 of Algorithm 1, step 1 in Fig. 2). The features we determine will be described below - they include meta-features about the instance values as well as an embedding vector for the specific property value. 3. In lines 4-6 of Algorithm 1 we compute property features with the help of function pF eatures (steps 2 and 3 in Fig. 2). They can be derived for the property name or based on the aggregation of instance features, e.g., average values of numeric instance features. 4. For each property pair, we compute the property pairs features using function ppF eatures (lines 7-9 of Algorithm 1, step 4 in Fig. 2), which may be partially based on the aggregation of property features. By default, we evaluate all property pairs but for large property sets the number of candidate pairs could be reduced, e.g., if their names or instance characteristics vary too strongly. 5. We use the input training data with their labeled property pairs and associated feature vectors to train a classification model using function trainClassifier in line 10 (labeled(PPF) denotes the already labeled property pairs). Then, we apply the trained classifier to the unlabeled property pairs to obtain a match decision and similarity score for each pair (lines 11-12 of Algorithm 1, step 5 in Fig. 2). As shown in the last step of Fig. 2, the output represents a similarity graph that can be post-processed as discussed above. 4 89 Algorithm 1: LEAPME Input: -I: set of property instances from msources - labeled property pairs (training) Output: -Sim: set of property pairs with similarities (similarity graph) Variables: -IF : Map<P roperty, F eaturesV ectorSet> with instance features vectors, grouped by property -P F : Map<P roperty, F eaturesV ector> with property features vectors. -PPF: Map<P ropertyP air, F eaturesV ector> with property pair features vectors. -m: classification model 1initialize(IF, P F, P PF, Sim) // Steps 1-4: compute features 2for iin Ido 3IF [p(i)] ←IF [p(i)] ∪iFeatures(i)) 4for (p, V )in IF do 5P F [p]←pFeatures(p) 6for p1in keyset of P F do 7for p2from different source in keyset of P F do 8P P F [(p1, p2)] ←ppFeatures(p1, p2) // Step 5: training and classification 9m←trainClassifier(labeled(P P F )) 10 for (p1, p2) : vin unlabeled(PPF)do 11 Sim.add((p1, p2, m.classify(v))) 3.3 Features Since we classify pairs of properties, the features that are ultimately fed to the classifier must be associated to a pair of properties. However, as we have mentioned, LEAPME considers features at several levels that can be later transformed into property pairs features. Next, we describe in detail each of these levels: Instance features: These features are computed from each individual instance of a property (that is, a features vector is obtained for each property value) independently of the property names. They provide information about the format of property values and can thus be considered as meta-features. We expect matching properties to follow similar formats, which should be reflected in these features. For example, while in Figure 2 properties “Res(mp)” and ”megapixel” have a different name, both have short values with numeric characters, which could be reflected in features that measure the number of such characters or token types. While on their own these features may not be enough to properly match features (since, for example, many properties follow similar numeric formats), they could help disambiguate problematic cases. Furthermore, in some contexts the name of the properties may be unknown or only a generic identifier. For example, information extraction techniques may identify a piece of text as an instance, but not be able to infer a label with its property name [29]. In these cases, no features can be computed from the property names, and only these instance features enable matching. In addition Resolution: “10 Mp ” Max-iso: “5000” Brand: “ Canon ” Res (mp): “7” ISO: “200 - 4000” S-speed: “1/4000” weight: “760 g ” Iso sens: “50 to 20000” lcd screen size: “3.0” usb: “ USB 2.0” HDMI: “ Yes ” megapixel: “16” PP 1 PP 2 PP 3 … PP O Resolution HDMI 1 1.5 1 … 0.5 Resolution Res (mp) 2 0.5 1 … 1 HDMI Res (mp) 3 1 0 … 1 … … … … … … … Properties pair features Result Resolution HDMI 0.21 Resolution Res (mp) 0.93 HDMI Res (mp) 0.15 … … … Matched properties I 1 I 2 I 3 … I M Resolution: "10 Mp" 2.0 2.0 1.0 … 0.0 Resolution: "5 Mp" 2.0 1.0 1.0 … 0.0 HDMI: "Yes" 3.0 0.0 0.0 … 0.0 HDMI: "Yes" 3.0 0.0 0.0 … 0.0 Res (mp): "7" 0.0 1.0 0.0 … 0.0 … … … … … … Instance features P 1 P 2 P 3 … P N Resolution 2.0 1.5 1.0 … 1.3 HDMI 3.0 0.0 0.0 … 0.2 Res (mp) 0.0 1.0 0.0 … 1.0 … … … … … … Property features Classifier Word embeddings 2 1 3 5 100 10101 10011 4 INPUT OUTPUT Resolution Max-iso RES (mp) USB megapixel ISO Refined matching 6 Figure 2: Workflow of LEAPME. 5 90 to format-oriented meta-features we also consider the actual property values in the form of word embeddings or the numeric value (see below). Property features: These features are computed for each individual property. They include all features computed from the property name, such as the average embeddings vector of its words. Furthermore, by grouping the instance features on a per-property basis, we can aggregate them and turn them into property features. For example, we could compute the average of each instance feature for a given property to represent the overall format followed by its instances. Property pair features: These features are computed for each pair of properties to be classified. These are the final features, and the only ones that are actually used for classification. Traditional string similarity metrics such as the Levenshtein or Jaro-Winkler distance would be part of these features, since they are computed from a pair or property names. Aggregated property features can also be used to determine property pair features. In this case, only two vectors are aggregated, e.g. by computing the numeric difference or average between the vectors, or by determining their concatenation. 3.4 Embeddings and classification When matching properties, a high value of the string similarity of the property names is usually a clear indicator of a match. Low similarity, however, can be caused by the issues we mentioned in Section 1. As discussed in Section 2, the usual way to mitigate this problem is to use external knowledge bases like WordNet to determine synonyms or name-independent similarities. These resources, however, are language-dependant and often of limited coverage. Furthermore, their use is relatively complex, and may require the use of APIs to handle the data. As a more promising and versatile approach to overcome these limitations, we propose the use of word embeddings for both property names and property values. They can provide rich information about the semantics of a property that can help solve some issues such as the potentially low string similarity between synonymous properties. While embeddings are language-dependant, versions for different languages can easily be trained from any large text corpus, unlike knowledge bases such as WordNet, whose creation requires a large manual effort. Furthermore, embeddings can be trained with a context-specific corpus, and are more likely to contain certain concepts. For example, the GloVe embeddings we use contains an entry for the word “28mm”, which is a typical aperture value for cameras. Embeddings vectors usually have hundreds of components with unknown meanings that may require nonlinear combinations to properly exploit their predictive power. For that reason, LEAPME uses a neural network for classification, which is also a popular choice in the related work. 3.5 Implementation Table 1 provides an overview about the features we have implemented. Instance features are computed with TAPON [4, 5], which includes several format-related features to which we added the embedding ones. Property features aggregate Type Description # of features The fraction and number of occurrences of several character types (letters (uppercase, lowercase, and both), mark characters, numbers, punctuation, symbols, separators, other) 18 The fraction and number of occurrences of several token types (words, words starting with a lowercase letter, words starting with an uppercase letter followed by a non-separator character, uppercase words, numeric strings) 10 The numeric value of the instance (-1 if it is not a number) 1 The average embeddings vector of the words in the instance 300 The average of every instance feature 329 The average embeddings vector of the words in the property name 300 The difference between the features vectors of the two properties 629 The optimal string alignment distance between the property names 1 The Levenshtein distance between the property names 1 The Full Damerau-Levenshtein distance between the property names 1 The longest common substring distance between the property names 1 The 3-gram distance between the property names 1 The cosine distance between the 3-gram profiles of the property names 1 The Jaccard distance between the 3-gram profiles of the property names 1 The Jaro-Winker distance between the property names 1 Instance Property Properties pair Table 1: Features used in our implementation. instance features by computing their average for every property, and add embedding features related to the property names. Property pair features aggregate property features, e.g., by computing the difference between the two vectors to obtain a rough representation of their distance. Property pair features also include traditional string similarity metrics for property names. To compute embeddings, we use the pre-trained GloVe approach [23]1, specifically for the uncased Common Crawl corpus that includes 300-dimensional vectors for 1.9 million words, promising a good coverage for different domains. Unknown words are mapped to a vector filled with zeroes. Each word in a property value or property name can thus be mapped to a point or embedding in the 300-dimensional data space so that similar words will have a small distance in this data space. For each property value and name we determine the average embeddings of the individual words represented by 300 values that serve as features for our classification approach. As indicated in Table 1, we currently use 28 meta-features for instance values. The actual instance values are reflected in one feature for numeric values and 300 features of the embeddings vector. The averages for these 329 features over all instance values of a property serve as property features. They are complemented with 300 features of the embeddings vector for the property name. The final feature vectors for property pairs thus include 629 features regarding the difference between the property features. Together with 8 features about the string similarity of property names there are 637 features for property pairs in total. 1https://nlp.stanford.edu/projects/glove/ 6 91 Prop. 1 Prop. 2 Label Levenshtein Fraction of letters Fraction of numbers Inst. emb. 3/300 Inst. emb. 4/300 Name emb. 65/300 Name emb. 66/300  camera resolution megapixel POS 13.00 0.00 0.10 0.13 0.07 0.70 0.04  camera resolution effective pixels POS 15.00 0.66 0.26 0.06 0.10 0.46 0.00  camera resolution dynamic af mode NEG 16.00 0.54 0.31 0.18 0.33 0.31 0.59  camera resolution alarm trigger NEG 14.00 0.81 0.42 0.23 0.41 0.38 0.69  Table 2: Sample feature values for matching and non-matching property pairs. Table 2 shows an example for a small subset of our features computed for four labeled property pairs (two matching and two non-matching). Note that the Levenshtein distances are similarly high in both positive and negative match cases while other features can better discriminate between them. For example, for the feature ”fraction of letters” the difference is 0 between properties “camera resolution” and “megapixel” and can thus help to determine such a match. Some of the embedding features (corresponding to individual components of the embeddings vectors) have good discriminating potential, with a low difference in positive and high difference in negative match cases (e.g., instance embedding 4 and name embedding 66). Finally, regarding the architecture of the neural network behind our proposal, it consists of two fully connected hidden layers of sizes 128 and 64. We use a batch size of 32 and perform 10 epochs with learning rate 10−3, 5 with 10−4, and 5 with 10−5. We fine-tuned these hyper-parameters manually in preliminary tests, though most alterations (such as changing the size of the layers) do not significantly impact on the results. The final layer has two neurons from which the final score is obtained for the two possible outcomes (positive/negative). This allows the use of the positive output as a similarity score, which is useful for post-processing steps such as property clustering. 4. EVALUATION We experimentally evaluate our property matching approach LEAPME on four real-word datasets with up to 24 sources. We analyze the impact of different amounts of training data and the effectiveness of the different kinds of features; in particular, the use of embeddings for both property values and property names. We further compare LEAPME with three baselines and study the use of transfer learning. The focus is on match quality with the standard metrics precision, recall and F-measure (F1 score). We first give some details about the studied feature configurations for LEAPME and the baseline approaches. Next, we describe the four datasets and the two use cases with training data from either the same or a different domain. The results for the two use cases are discussed in subsections 4.4 and 4.5, respectively. The evaluated implementations along with the detailed results and additional material are available online2. 4.1 Feature configurations and baselines The rich set of features is a main advantage of LEAPME and we therefore analyze the effectiveness of the different kinds of features in detail. Along one dimension, we compare the use of instance-related features only, name-related features only and the combined use of both kinds of features. 2https://github.eii.us.es/dayala1/LEAPME Another dimension is the consideration of embedding-based features only, non-embedding features only or the combined use of both kinds of features. In total, this sums up to 9 possible feature configurations to analyze. The LEAPME results are compared to the results obtained by the following baselines: •The latest Github implementation of Agreement Maker Light [15] (AML), the highest-ranked technique in the M2 variants of the “Conferences” track of OAEI 2019, which involve the matching of only properties 3. •The latest Github implementation of FCA-Map [9], the best-performing property matching technique in the “Knowledge Graph” track of OAEI 2019 4. •An implementation of the machine learning proposal by Nezhadi et al. [20]. It was selected among machine learning proposals for having the largest features catalogue, from which we removed the structural features since they were not applicable to our evaluation datasets. We use AdaBoost with decision trees as classifier, which achieved the best results in [20]. 4.2 Datasets For our evaluation, we use four real-word datasets with different kinds of e-commerce products (cameras, headphones, phones, and TV sets) from multiple sources. All datasets align the properties in each source to a reference ontology. We consider that two properties are related (matching) when they are both aligned to the same reference property. All four datasets have been extracted from the Web using information extraction techniques, and contain some noise that is typical of real world scenarios, making matching more challenging. Table 3 provides main statistics for the four datasets. The camera dataset comes from the DI2KG19 challenge [1]. It is the largest dataset with 24 sources, more than 3200 properties and about 9200 matching property pairs. We limited the number of entities to 100 per source in order to balance their size and impact. But, as shown in the lower part of Table 3, the number of different properties and the number of property entities differs substantially between different sources, with almost 700 properties for one of the sources (EBay.com). The other datasets contain headphones, phones and TV product entities and correspond to the WDC Gold Standard for Product Matching and Product Feature Extraction [36]. These datasets are much smaller than the camera dataset and there are different numbers of entities per source leading to a less balanced setting than 3http://oaei.ontologymatching.org/2019/results/ conference/index.html 4http://oaei.ontologymatching.org/2019/results/ knowledgegraph/index.html 7 92 Cameras Headphones Phones TVs # of Sources 24 6 12 8 Entities 2400 128 208 124 Properties 3245 172 554 415 Instances 65615 1129 5195 2069 Positives 9199 412 2677 1062 Entities per source Instances per source Properties per source 0 100 0 25 50 0 75 150 0 50 100 0 3350 6700 0 500 1000 0 1850 3700 0 350 700 0 350 700 0 50 100 0 75 150 0 75 150 Table 3: Datasets metadata. Each vertical bar in a plot represents a source within a dataset. that of the camera dataset. In our analysis of the results, we will refer to the three smaller and imbalanced datasets as low-quality datasets as opposed to the high-quality camera dataset. 4.3 Use cases and training data For training, we differentiate two use cases in which the training data either refers to properties from the same domain (entity type) or to properties from a different domain. For the first use case, which we call Single Domain (SD), we take a fraction of the sources of a dataset (at random) for training. We use the examples that involve two sources of data in the training set to train the classifier, and test it with the rest. We performed experiments using different training fractions: 0.2, 0.4, 0.6, and 0.8. For each of these fractions and for each dataset, we ran LEAPME 25 times, using different random combinations of training sources. For the second use case, called Transfer Learning (TL), we train the classifier for one dataset (entity type) with training data from the other datasets. For this purpose, we tested all possible combinations of using 1, 2, or 3 datasets for training. Figure 3 shows an example of how data is divided into training and testing for both use cases. The example illustrates SD training for the camera dataset where each labeled property pair uses properties from two of the 24 sources. For the TL use case, there are many possible configurations. The shown example refers to training pairs from the first two datasets to be used for evaluating property matching for two other datasets. For all datasets and use cases, the training data consists of two negative (non-matching) pairs of properties for every positive (matching) pair, and the negative pairs are randomly selected. 4.4 Single-domain results Next, we compare the results obtained by different configurations of LEAPME, as well as those obtained by the three baselines. We first evaluate the results in the single-domain case and compare LEAPME with the three baselines. Figure 4 shows the precision (in blue) and recall (in red) results for the four Datasets Headphones Phones TVs Cameras Mypriceindia.com Eglobalcentral.co.uk Shopmania.in Ilgs.net Training (TL) Testing (TL) Training (SD) Testing (SD) Figure 3: Use cases testing example. datasets for different amounts of training data (0.2 to 0.8) for the ML approaches LEAPME and Nezhadi. The results for the non-ML approaches AML and FCA-Map are shown as horizontal lines since they do not depend on training data. The results for LEAPME are obtained by using both features for property names and instances but we differentiate the three cases of the use of embedding features only, the use of non-embedding features only and the use of all features. The value ranges for the ML approaches reflect the different training configurations involving a random selection of the sources in a dataset. The variations are generally higher for the smaller and unbalanced datasets like headphones that provide fewer training data. We make the following observations: •Techniques that do not use machine learning achieve a very high precision but low recall. •LEAPME achieves better overall results than all the baselines, with a dramatic increase of recall when compared to AML and FCA-Map and both recall and precision improvements when compared to Nezhadi. 8 93 9 CONCLUSIONS AND FUTURE WORK 101 We have presented a total of five publications corresponding to three different objectives related to enrichment of knowledge graphs. Next, we summarize our main contributions in Section §9.1 and present, for each of the objectives, possible lines of future work that would refine our results in Section §9.2. CHAPTER 9. CONCLUSIONS AND FUTURE WORK 9.1 CONCLUSIONS In this thesis, developed in the context of data engineering, we have presented a set of methods and tools for assisting in building knowledge graphs, which have greatly increased in popularity because of their conceptual simplicity when it comes to storing and handling structured information. Our work is centered around semantic labelling, property matching, and knowledge graph completion. Our work has focused on aspects related to the application of machine learning techniques which are relatively unexplored. Regarding semantic labelling, we have developed TAPON, a new proposal that computes a large number of features to label every element in a tree-shaped piece of data. These features, along with the use of machine learning classifiers allowed us to improve labelling results when compared to other features catalogues and techniques. A significant part of this improvement was achieved with a novel set of features called hint-based features. Hint-based features can be computed after a first labelling iteration, and provide information related to the context of each element (e.g. being near something that seems to be a price). To ease the training and testing of models with TAPON, we have developed TAPONMT, which adds a graphical interface to TAPON with views for model creation, visualisation and testing. The model testing view includes the option to display a similarity metric that shows what classes are problematic to the classifier. Finally, we performed a study of different classification techniques that showed that neural networks achieve significantly better result than the more traditional classification techniques that are popular in the state of the art. This study also measured the effectiveness of different groups of features, showing that some groups are beneficial enough to justify the computational cost added by their computation. Regarding property matching, we have developed LEAPME, which heavily uses features related to word embeddings to match data properties. While the implementation of such features is simple, the effects on accuracy are significant specially when a good amount of high quality data is used for training. While this may hinder their applicability to situations where there is little available training data, we also showed that it is possible to train a classifier with data from a domain and apply it do data from a different one, thus enabling the creation of pre-trained universal classifiers. Regarding knowledge graph completion, instead of working on a proposal for com- 102 9.2. FUTURE WORK pletion, we have focused on developing tools for their evaluation, since the dataset and evaluation strategies in the state of the art are heterogeneous. With AYNEC, we offer a well defined workflow for evaluation, and tools that cover it with customisable options for each of the variation points in the workflow. AYNEC-DataGen takes a knowledge graph and outputs files corresponding to training and testing, along with several complementary files, including a gephi file with labelled edges. AYNEC-ResTest takes a file with the results of each technique and computes a large amount of metrics both for each relation and aggregated, as well as statistical tests. 9.2 FUTURE WORK We have showed in several tasks the potential of supervised machine learning techniques when it comes to data integration and enrichement. We have developed implementations that show the effectiveness of certain strategies and workflows. However, there possible untested configurations whose study could be interesting as future expansion of our work. Next we present, for each objective, the most relevant ones we have identified. 9.2.1 Semantic Labelling While in TAPON we have proposed a novel set of featurse (hint-based features), the specific features we implemented are only an initial baseline that could be expanded with new, more complex features. For example, additional hint-based features could be based on the type of attributes, so that some of them would only be computed from numerical attributes, others from purely textual ones and so on. Furthermore, some features can be devised in more or less specific ways. For example, feature "distance to the nearest price" could be transformed into the binary feature "is there a price in the neighbourhood of the node with maximum distance 3?". The rationale behind these variants would be to avoid overfitting, which can be particularly problematic when it comes to integration of completely different sources. Finally, while the features we have implemented made it impossible to use elaborate deep learning techniques, some features could be designed to make use of some layer types such as sequential or convolutional ones. For example, a feature could return a sequence of values to be encoded by a memory layer. The potential of these techniques is yet to be explored. 103 CHAPTER 9. CONCLUSIONS AND FUTURE WORK 9.2.2 Property Matching We have shown that the combination of embedding features and supervised learning achieves excellent results. However, decent amounts of good quality training data are needed to reach the full potential of LEAPME, which may not always be available. Our experiments showed that there is good potential for creating a universal classifier that can be applied to pairs of properties from any context. Therefore, it is crucial to develop more high quality, multi-domain, multi-source datasets that enable the training of such a universal classifier. This classifier could easily be plugged into existing matching systems as an additional similarity measurement. Additionally, different implementations of LEAPME could be tested to find an optimal configuration. These variants could include the use of different word embeddings, the application of dimensionality reduction techniques, or the use of different techniques to obtain sentence embeddings. Finally, our pairwise multi-source matching should be followed by a clustering of the matches in order to obtain final groups of related properties. Further research could evaluate the application of said techniques, be it applied to all possible source comparisons or to comparisons of all sources with a chosen reference. 9.2.3 Knowledge graph completion AYNEC implements several popular strategies for each step in the KG completion evaluation workflow. Thanks to its modular design, new strategies could be implemented in important steps, such as the generation of negative examples, which is particularly decisive. Furthermore, while several strategies have been implemented in some steps, there is no evaluation that shows the impact of choosing one or another. For example, the negatives generation strategy defined by Gardner et al. [16] is more complex, using personalized page rank to obtain replacements that are nearer the original entities. However, the effects of using this strategy over simpler ones are not measured. Finally, if new datasets with interesting properties are identified, they could be added to AYNEC-Datasets. 104 BIBLIOGRAPHY 105 [1] D. Ayala, I. Hernández, D. Ruiz, and M. Toro. Tapon: A two-phase machine learning approach for semantic labelling. Knowledge-Based Systems, 163:931–943, 2019. (page 12). [2] D. Ayala, I. Hernández, D. Ruiz, and M. Toro. Tapon-mt: A versatile framework for semantic labelling. Information Systems, 83:57–68, 2019. (page 13). [3] D. Ayala Hernández, A. Borrego Díaz, I. C. Hernández Salmerón, and D. Ruiz Cortés. A neural network for semantic labelling of structured information. Expert Systems with Applications, 143, 2020. (page 14). [4] B. G. Bashardoost, R. J. Miller, and K. Lyons. Towards a benchmark for knowledge base exchange. 2019. (page 6). [5] Z. Bellahsene, A. Bonifati, and E. Rahm. Schema Matching and Mapping. Springer, 2011. (page 8). [6] P. A. Bernstein, J. Madhavan, and E. Rahm. Generic schema matching, ten years later. Proceedings of the VLDB Endowment, 4(11):695–701, 2011. (pages 6 and 8). [7] K. Bollacker, C. Evans, P. Paritosh, T. Sturge, and J. Taylor. Freebase: a collaboratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 1247– 1250, 2008. (pages 4 and 5). [8] F. Chang, G. Chen, and S. Zhang. FCAMap-KG results for OAEI 2019. In CEUR Workshop Proceedings, volume 2536, pages 138–145. RWTH, 2019. (page 6). [9] M. Cheatham and P. Hitzler. The properties of property alignment. In OM, pages 13–24, 2014. (page 8). [10] A. Doan, A. Halevy, and Z. Ives. Principles of data integration. Elsevier, 2012. (page 6). BIBLIOGRAPHY [11] F. Erxleben, M. Günther, M. Krötzsch, J. Mendez, and D. Vrandeˇci´c. Introducing wikidata to the linked data web. In International Semantic Web Conference, pages 50–65. Springer, 2014. (page 5). [12] J. Euzenat, P. Shvaiko, et al. Ontology matching, volume 18. Springer, 2007. (page 8). [13] D. Faria, C. Pesquita, T. Tervo, F. M. Couto, and I. F. Cruz. AML and AMLC Results for OAEI 2019. 2536:123–130, 2019. (page 6). [14] P. A. Flach and N. Lachiche. Naive bayesian classification of structured data. Machine Learning, 57(3):233–269, 2004. (page 4). [15] E. Gabrilovich and N. Usunier. Constructing and mining web-scale knowledge graphs. In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, pages 1195–1197, 2016. (page 7). [16] M. Gardner and T. Mitchell. Efficient and expressive knowledge base completion using subgraph feature extraction. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1488–1498, 2015. (pages 7, 8, and 104). [17] G. Ji, S. He, L. Xu, K. Liu, and J. Zhao. Knowledge graph embedding via dynamic mapping matrix. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 687–696, 2015. (pages 7 and 8). [18] N. Kushmerick. Wrapper verification. World Wide Web, 3(2):79–94, 2000. (page 13). [19] N. Lao and W. W. Cohen. Relational retrieval using a combination of pathconstrained random walks. Machine learning, 81(1):53–67, 2010. (page 7). [20] J. Lehmann, R. Isele, M. Jakob, A. Jentzsch, D. Kontokostas, P. N. Mendes, S. Hellmann, M. Morsey, P. Van Kleef, S. Auer, et al. Dbpedia–a large-scale, multilingual knowledge base extracted from wikipedia. Semantic Web, 6(2):167–195, 2015. (pages 4 and 5). [21] F. Lin and K. Sandkuhl. A survey of exploiting Wordnet in ontology matching. In IFIP Int. Conf. on Artificial Intelligence in Theory and Practice, pages 341–350. Springer, 2008. (page 8). 106 BIBLIOGRAPHY [22] Y. Lin, Z. Liu, M. Sun, Y. Liu, and X. Zhu. Learning entity and relation embeddings for knowledge graph completion. In Twenty-ninth AAAI conference on artificial intelligence, 2015. (page 7). [23] F. Mahdisoltani, J. Biega, and F. M. Suchanek. Yago3: A knowledge base from multilingual wikipedias. 2013. (page 5). [24] S. Mazumder and B. Liu. Context-aware path ranking for knowledge base completion. arXiv preprint arXiv:1712.07745, 2017. (pages 7 and 8). [25] R. McCann, B. AlShebli, Q. Le, H. Nguyen, L. Vu, and A. Doan. Mapping maintenance for data integration systems. In Proceedings of the 31st international conference on Very large data bases, pages 1018–1029. VLDB Endowment, 2005. (page 7). [26] G. A. Miller. Wordnet: a lexical database for english. Communications of the ACM, 38(11):39–41, 1995. (page 5). [27] T. Mitchell, W. Cohen, E. Hruschka, P. Talukdar, B. Yang, J. Betteridge, A. Carlson, B. Dalvi, M. Gardner, B. Kisiel, et al. Never-ending learning. Communications of the ACM, 61(5):103–115, 2018. (pages 4 and 5). [28] V. Mulwad, T. Finin, and A. Joshi. Semantic message passing for generating linked data from tables. In International Semantic Web Conference, pages 363–378. Springer, 2013. (page 7). [29] J. Neville and D. Jensen. Iterative classification in relational data. In Proc. AAAI- 2000 workshop on learning statistical models from relational data, pages 13–20, 2000. (page 13). [30] N. Noy, Y. Gao, A. Jain, A. Narayanan, A. Patterson, and J. Taylor. Industry-scale knowledge graphs: Lessons and challenges. Queue, 17(2):48–75, 2019. (page 6). [31] A. G. Nuzzolese, A. L. Gentile, V. Presutti, and A. Gangemi. Conference linked data: the scholarlydata project. In International Semantic Web Conference, pages 150–158. Springer, 2016. (page 4). [32] L. Otero-Cerdeira, F. J. Rodríguez-Martínez, and A. Gómez-Rodríguez. Ontology matching: A literature review. Expert Systems with Applications, 42(2):949–971, 2015. (page 8). [33] M. Pasca, D. Lin, J. Bigham, A. Lifchits, and A. Jain. Organizing and searching the world wide web of facts - step one: The one-million fact extraction challenge. In AAAI, pages 1400–1405, 2006. (page 4). 107 BIBLIOGRAPHY [34] H. Paulheim. Knowledge graph refinement: A survey of approaches and evaluation methods. Semantic web, 8(3):489–508, 2017. (page 7). [35] P. Pezeshkpour, Y. Tian, and S. Singh. Revisiting evaluation of knowledge base completion models. In Automated Knowledge Base Construction, 2020. (page 23). [36] M. Pham, S. Alse, C. A. Knoblock, and P. Szekely. Semantic labeling: a domainindependent approach. In International Semantic Web Conference, pages 446–462. Springer, 2016. (pages 6, 7, 8, and 13). [37] E. Rahm and P. A. Bernstein. A survey of approaches to automatic schema matching. the VLDB Journal, 10(4):334–350, 2001. (page 8). [38] S. K. Ramnandan, A. Mittal, C. A. Knoblock, and P. Szekely. Assigning semantic labels to data sources. In European Semantic Web Conference, pages 403–417. Springer, 2015. (pages 6, 7, and 13). [39] D. Ritze, O. Lehmberg, and C. Bizer. Matching html tables to dbpedia. In Proceedings of the 5th International Conference on Web Intelligence, Mining and Semantics, pages 1–6, 2015. (page 7). [40] O. Rusu, I. Halcu, O. Grigoriu, G. Neculoiu, V. Sandulescu, M. Marinescu, and V. Marinescu. Converting unstructured and semi-structured data into knowledge. In 2013 11th RoEduNet International Conference, pages 1–4. IEEE, 2013. (page 4). [41] B. Shao, H. Wang, and Y. Li. The trinity graph engine. Microsoft Research, 54, 2012. (page 4). [42] B. Shi and T. Weninger. Proje: Embedding projection for knowledge graph completion. In Thirty-First AAAI Conference on Artificial Intelligence, 2017. (page 7). [43] R. Socher, D. Chen, C. D. Manning, and A. Ng. Reasoning with neural tensor networks for knowledge base completion. In Advances in neural information processing systems, pages 926–934, 2013. (page 8). [44] T. Soru and A.-C. N. Ngomo. A comparison of supervised learning classifiers for link discovery. In Proceedings of the 10th international conference on semantic systems, pages 41–44, 2014. (page 13). [45] M. Speranskaya, M. Schmitt, and B. Roth. Ranking vs. classifying: Measuring knowledge base completion quality. In Automated Knowledge Base Construction, 2020. (page 23). 108 BIBLIOGRAPHY [46] P. Venetis, A. Y. Halevy, J. Madhavan, M. Pasca, W. Shen, F. Wu, and G. Miao. Recovering semantics of tables on the web. 2011. (pages 7 and 8). [47] S. Wang, X. Zhang, P. Ye, M. Du, Y. Lu, and H. Xue. Geographic knowledge graph (geokg): A formalized geographic knowledge representation. ISPRS International Journal of Geo-Information, 8(4):184, 2019. (page 4). [48] O. Wolkenhauer. Data engineering: fuzzy mathematics in systems theory and data analysis. John Wiley & Sons, 2004. (page 4). [49] Z. Zhang. Effective and efficient semantic table interpretation using tableminer+. Semantic Web, 8(6):921–957, 2017. (page 7). 109