Graph Edit Distance applied to diverse frameworks: Learning, matching and exploring techniques

Abstract

Els grafs són objectes matemàtics que descriuen representacions abstractes de dades quan les relacions entre els elements estan definides. Quan les dades es representen amb grafs, els nodes representen els principals objectes de les dades i les arestes representen les relacions entre ells. En aquest context, és necessari definir o adaptar tècniques específiques d'aprenentatge automàtic per a obtenir informació de les dades i predir característiques o trets que puguin ser d'interès per a algunes aplicacions. Durant els últims 40 anys, els investigadors han analitzat com representar les dades amb grafs i com adaptar els mètodes d'aprenentatge automàtic a aquestes estructures o definir altres nous adaptats a aquest marc. Amb aquest objectiu, el concepte de Graph Edit Distance (GED) ha estat utilitzat durant dècades i diverses tècniques d'aprenentatge automàtic utilitzen la GED com a mesura de dissimilitud entre grafs per a abordar la solució de diferents problemes. Aquesta tesi presenta un compendi de mètodes d'aprenentatge automàtic centrats en dades representades per grafs. S'han afrontat diverses tasques representant les dades com a grafs i la majoria dels mètodes presentats fan ús del concepte de GED com a eina per a analitzar l'estructura de les dades. Les tècniques desenvolupades en aquesta tesi demostren que la representació mitjançant grafs de les dades és adequada per a resoldre diferents situacions i pot ser explorada per a futurs contextos.

Los grafos son objetos matemáticos que describen representaciones abstractas de datos cuando las relaciones entre los elementos están definidas. Cuando los datos se representan con grafos, los nodos representan los principales objetos de los datos y las aristas representan las relaciones entre ellos. En este contexto, es necesario definir o adaptar técnicas específicas de aprendizaje automático para obtener información de los datos y predecir características o rasgos que puedan ser de interés para algunas aplicaciones. Durante los últimos 40 años, los investigadores han analizado cómo representar los datos con grafos y cómo adaptar los métodos de aprendizaje automático a estas estructuras o definir otros nuevos adaptados a este marco. Con este objetivo, el concepto de Graph Edit Distance (GED) ha sido utilizado durante décadas y varias técnicas de aprendizaje automático utilizan la GED como medida de disimilitud entre grafos para abordar la solución de diferentes problemas. Esta tesis presenta un compendio de métodos de aprendizaje automático centrados en datos representados por grafos. Se han afrontado diversas tareas representando los datos como grafos y la mayoría de los métodos presentados hacen uso del concepto de GED como herramienta para analizar la estructura de los datos. Las técnicas desarrolladas en esta tesis demuestran que la representación mediante grafos de los datos es adecuada para resolver diferentes situaciones y puede ser explorada para futuros contextos.

Graphs are mathematical objects that depict the abstract representation of data when relations between elements are defined. When data is represented with graphs, nodes represent the main objects of the data and edges represent the relations between them. In this context, specific machine learning techniques need to be defined or adapted to obtain information from the data and predict characteristics or features that could be of interest for some applications. During the last 40 years, researchers have been analysing how to represent data with graphs and how to adapt machine learning methods to these structures or define new ones adapted to this framework. With this aim, the concept of Graph Edit Distance (GED) has been used during decades and several machine learning techniques use the GED as measure of dissimilarity between graphs to tackle the solution of different problems. This thesis presents a compendium of machine learning methods focused on graph-represented data. Diverse tasks have been faced representing the data as graphs and the majority of the presented methods make use of the concept of GED as a tool to analyse the structure of the data. The techniques developed on this thesis demonstrate that the graph representation of data is suitable to solve different situations and can be explored for future contexts.