The Node Classification Problem: aplicación al problema de clasificación multiclase en artículos relacionados con el aprendizaje automático

Abstract

La teoría de grafos es un área en constante crecimiento, pues su aplicación se extiende en diferentes áreas de las matemáticas, la ciencia y la tecnología. Se utiliza de manera activa en los campos como la bioquímica, las redes de comunicación y la teoría de la codificación, la informática (algoritmos y computación) y la investigación operativa (programación), así como en otra gran variedad de aplicaciones como la teoría de la codificación, el radar, la astronomía, el diseño de circuitos, el direccionamiento de redes de comunicación y la gestión de bases de datos. Este trabajo refleja el gran potencial de esta herramienta en el campo de la Inteligencia Artificial y, en concreto, del Machine Learning. La capacidad única de los grafos permite capturar las relaciones estructurales entre los datos y, por lo tanto, permite obtener más información en comparación con el análisis de datos aislados. La mayoría de las técnicas de ML no representan o no tienen en cuenta las posibles estructuras o relaciones que pudieran existir entre los objetos, asumiendo por simplicidad que los items son independientes entre sí. Por otro lado, y para todos aquellos escenarios y problemas de ML en que los datos presentan relaciones intrínsecas entre ellos, parece una necesidad tener en cuenta esta información adicional, eliminando la hipótesis de independencia (o no dependencia entre los datos). Sin embargo, a menudo es muy difícil resolver los problemas de aprendizaje en grafos debido a que, principalmente, muchos tipos de datos no están estructurados originalmente como grafos (como las imágenes y los datos de texto) y que, para datos estructurados como grafos, los patrones de conectividad subyacentes suelen ser complejos. Por lo tanto, dado un grafo con etiquetas en algunos nodos, ¿es posible predecir el valor que tendrán los valores no etiquetados? Este problema se conoce como el Node Clas- sification Problem. Aunque se han hecho algunos esfuerzos por incorporar la Teoría de Grafos a los modelos de aprendizaje, muchos de ellos siguen adoleciendo de mecanismos de aprendizaje poco profundos. Los modelos de aprendizaje profundo sobre grafos (por ejem- plo, las Redes Neuronales de Grafos - GNN) han surgido recientemente en el aprendizaje de otras áreas relacionadas, y han demostrado un rendimiento superior en varios problemas.

En este trabajo se estudiarán e implementarán las últimas técnicas de aprendizaje sobre redes para problemas de ML donde los objetos están relacionados entre sí por medio de un grafo. En particular, se implementarán y analizarán las PRM (Probabilistic Relational Methods) y GCN (Graph Convolutional Networks) adaptadas al problema del Node Classi- fication Problem, esta última basándonos en el trabajo de Thomas N. Kirf y Max Welling, que forman parte del elenco de pocos autores que aborda este problema para el Node Clas- sification Problem. Es importante notar que las Redes Convolucionales (CNN) han sido usadas con frecuencia para problemas de imágenes donde las relaciones entre los píxeles que se pretende clasifi se modelizan mediante una estructura de grafo específi en rejilla, pero el Node Classifi n Problem permite relaciones entre objetos de cualquier tipo con una estructura de grafo general donde las técnicas clásicas (Redes Convolucionales) para imágenes no pueden aplicarse directamente.

Graph theory is a constantly growing area, as its application extends into different areas of mathematics, science and technology. It is actively used in fields such as bio- chemistry, communication networks and coding theory, computer science (algorithms and computation) and operations research (programming), as well as in a wide variety of other applications such as coding theory, radar, astronomy, circuit design, addressing communi- cation networks and database management. This work reflects the great potential of this tool in the field of Artificial Intelligence and, in particular, Machine Learning.

The unique capability of graphs allows capturing structural relationships between data and, therefore, allows obtaining more information compared to the analysis of isolated da- ta. Most ML techniques do not represent or do not take into account the possible structures or relationships that may exist between objects, assuming for simplicity that items are in- dependent of each other. On the other hand, and for all those ML scenarios and problems in which the data present intrinsic relationships between them, it seems a necessity to take into account this additional information, eliminating the hypothesis of independence (or non-dependence between the data). However, it is often very difficult to solve graph learning problems because, primarily, many types of data are not originally structured as graphs (such as images and text data) and that, for data structured as graphs, the underlying connectivity patterns are often complex. Therefore, given a network with labels at some nodes: is it possible to predict the value that unlabeled values will have? This problem is known as the Node Classification Problem. Although some eff rts have been made to incorporate graph theory into learning models, many of them still suffer from shallow learning mechanisms. Deep learning models on graphs (e.g., graph neural networks) have recently emerged in learning in other related areas, and have demonstrated superior performance on several problems. In this paper we will study and implement the latest network learning techniques for ML problems where objects are related to each other by means of a graph. Specifically, we will implement PRM (Probabilistic Relational Methods) and GCN (Graph Convolutional Networks), adapted to the Node Classifi Problem, this last one based on the work of Thomas N. Kirf and Max Welling, who are among the few authors who address this problem for the Node Classifi tion Problem. It is important to note that Convolutional Networks (CNN) have been frequently used for image classifi where the elationships between the the pixels to be classifi are modelled by a specifi graph structure as a grid, but the Node Classifi Problem allows relationships between objects of any type with a general graph structure where classical techniques (Convolutional Networks) for images cannot be directly applied.