Definición, tipologías y casos de uso de Graph Neural Networks para el aprendizaje basado en relaciones

Abstract

La evolución del aprendizaje computacional y, en particular, el del aprendizaje profundo, ha acelerado de manera drástica en los últimos años. Esta progresión se ha visto centrada en el uso de datos donde sus entidades no tienen ningún tipo de dependencia entre sí: no existen jerarquías, relaciones de orden o de dependencia. Sin embargo, este proyecto se centra en dicha laguna: en la exploración de la evolución, contexto, casos de uso y técnicas existentes para el aprendizaje sobre estructuras de grafo mediante redes neuronales gráficas. Para ello, tras repasar la base histórica y teórica de las redes neuronales, se estudian distintas aproximaciones y tipos de problemas que pueden ser resueltos, para lo que se ofrece una clasificación de tipologías de modelos según su aproximación al aprendizaje. De este modo, se presentan los problemas principales sobre los que aplicar esta particularización de las redes neuronales: clasificar y predecir vértices y nodos de un grafo, catalogar estructuras, predecir cambios dentro del dominio o generar grafos según ejemplos aprendidos. Una vez se ha hecho este repaso teórico, se ha procedido a implementar con Python modelos de predicción de nodos mediante una aproximación espectral y otra espacial, así como un ejemplo de predicción de enlaces. Además, con el objetivo de contrastar los resultados, se ha realizado una implementación de clasificación de nodos mediante un algoritmo que no tenga en cuenta la estructura. Como conclusión, se destaca la alta eficacia de estos modelos para la resolución de problemas sin hacer uso de espacios euclídeos.

The evolution of machine learning and, in particular, of deep learning, has accelerated drastically in the last decade. However, this development has been focused on the use of datasets where each sample is independent from the rest, without hierarchy, order or any other kind of relationship. This project is focused on exploring the evolution, contexts, use cases and different methods to perform machine learning operations over graphs using graph neural networks. This work starts by reviewing the history and theoretical knowledge about neural networks, exploring different approximations, frameworks and types of problems. To do so, this work presents a classification of models based on its approach to learning. Different kinds of problems are presented that can be solved with this particular type of neural networks: node and edge classification, graph classification, predicting changes in the knowledge domain or generating new graphs based on examples. Following the review of these theoretical aspects, a collection of implementations is presented in a Python notebook using spectral and spatial approximations to graphs to classify nodes, as well as a link prediction model. Also, to be able to compare results, an implementation based on a traditional model that doesn't attend to data structure is used to classify nodes. At the end, all results are compared and a collection of conclusions is presented to address the motivation of using this type of models, showing that they can outperform those based on euclidean spaces when structured data is present.

L'evolució de l'aprenentatge computacional i, en particular, el de l'aprenentatge profund, ha accelerat de manera dràstica en els últims anys. Aquesta progressió s'ha vist centrada en l'ús de dades on les seves entitats no tenen cap mena de dependència entre si: no existeixen jerarquies, relacions d'ordre o de dependència. No obstant això, aquest projecte se centra en aquesta llacuna: en l'exploració de l'evolució, context, casos d'ús i tècniques existents per a l'aprenentatge sobre estructures de graf mitjançant xarxes neuronals gràfiques. Per a això, després de repassar la base històrica i teòrica de les xarxes neuronals, s'estudien diferents aproximacions i tipus de problemes que poden ser resolts, per al que s'ofereix una classificació de tipologies de models segons la seva aproximació a l'aprenentatge. D'aquesta manera, es presenten els problemes principals sobre els quals aplicar aquesta particularització de les xarxes neuronals: classificar i predir vèrtexs i nodes d'un graf, catalogar estructures, predir canvis dins del domini o generar grafs segons exemples apresos. Una vegada s'ha fet aquest repàs teòric, s'ha procedit a implementar amb Python models de predicció de nodes mitjançant una aproximació espectral i una altra espacial, així com un exemple de predicció d'enllaços. A més, amb l'objectiu de contrastar els resultats, s'ha realitzat una implementació de classificació de nodes mitjançant un algorisme que no tingui en compte l'estructura. Com a conclusió, es destaca l'alta eficàcia d'aquests models per a la resolució de problemes sense fer ús d'espais euclidians.