Predicción de Aristas para Data Augmentation en Problemas de Clasificación de Nodos con Graph Neural Networks

Predicción de Aristas para Data Augmentation en Problemas de Clasificación de Nodos con Graph Neural Networks Gonzalo Carmona López Predicción de Aristas para Data Augmentation en Problemas de Clasificación de Nodos con Graph Neural Networks Gonzalo Carmona López Memoria presentada como parte de los requisitos para la obtención del título de Máster Universitario en Matemáticas por la Universidad de Sevilla. Tutorizada por Prof. Tutora María del Rocío González Díaz Prof. Tutor Eduardo Paluzo Hidalgo Resumen En este trabajo, repasamos detalladamente el planteamiento de un problema de aprendizaje supervisado en general, sobre datos en forma de grafo en particular, y la construcción de la arquitectura de Graph Neural Networks para la resolución del mismo. En concreto, nos centramos en SEAL, una metodología basada en Graph Neural Networks para predicción de aristas. Además, explicaremos el método GAug-M para data augmentation en problemas de clasificación de nodos, que consiste en añadir o eliminar aristas en base a las probabilidades obtenidas de un modelo predictor de aristas, para enriquecer la información del grafo y aumentar el rendimiento del modelo de clasificación. En este TFM se propone un nuevo uso de la metodología SEAL como modelo predictor de aristas junto con GAug-M para realizar data augmentation en un grafo. Evaluaremos el rendimiento de usar esta combinación, y lo compararemos con el rendimiento obtenido en [37] con otro modelo predictor de aristas, en los mismos datasets y con el mismo modelo de clasificación de nodos. 1 Abstract In this work, we explain in detail the formulation of a supervised learning problem in general, over graph data in particular, and the arquitecture of Graph Neural Networks for solving them. In particular, we focus on SEAL, a Graph Neural Network framework for predicting the existence of a link between nodes. We also talk about GAug-M, a method for data augmentation in node classification problems, which consists in adding or removing links based in precalculated probabilities, in order to improve the graph information, and also improve the performance of the node classification model. In this work, we propose a new use of SEAL as the link predictor, together with GAug-M for performing data augmentation in a graph. We evaluate the performance of this combination, and we compare it with the performance obtained in [37] with a different link prediction model, in the same datasets and with the same model for node classification. Moreover, we explain how to use this arquitecture for performing data augmentation on a graph, whose nodes we want to classify, using the GAug-M method, explained and tested in [37] with other link prediction arquitectures different from SEAL. . We evaluate the performance when using SEAL as the link predictor, and we compare it with the efficiency obtained in [37] by using other predictor models, in the same datasets and with the same node classification model. 2 Índice general 1. Introducción 6 2. Grafos 8 2.1. TeoríadeGrafos ........................... 8 3. Aprendizaje automático 13 3.1. Aprendizaje Supervisado . . . . . . . . . . . . . . . . . . . . . . . 13 3.1.1. Conjunto de datos de entrenamiento y de test ....... 14 3.2. Funcionesdecoste .......................... 15 3.3. Optimización del modelo . . . . . . . . . . . . . . . . . . . . . . . 17 3.3.1. Descenso del gradiente y variantes . . . . . . . . . . . . . 17 3.4. Evaluación del modelo . . . . . . . . . . . . . . . . . . . . . . . . 21 3.4.1. Overfitting,underfitting y conjunto de validación . . . . . 21 3.4.2. Métricas de evaluación . . . . . . . . . . . . . . . . . . . . 23 4. Redes Neuronales 29 4.1. Componentes de una red neuronal . . . . . . . . . . . . . . . . . 29 4.1.1. Perceptrones ......................... 29 4.1.2. Neuronas y funciones de activación . . . . . . . . . . . . . 31 3 ÍNDICE GENERAL 4 4.2. El modelo de aprendizaje de redes neuronales . . . . . . . . . . . 33 4.2.1. Redes Neuronales . . . . . . . . . . . . . . . . . . . . . . . 33 4.2.2. Descenso del gradiente en redes neuronales y propagación haciaatrás .......................... 36 5. Graph Neural Networks 42 5.1. Definición del modelo de Graph Neural Networks . . . . . . . . . 42 5.2. Graph Neural Network básica . . . . . . . . . . . . . . . . . . . . 45 5.3. Normalización del operador aggregate: Graph Convolutional Network.................................. 47 5.4. Deep Graph Convolutional Network . . . . . . . . . . . . . . . . 48 6. El método SEAL 51 6.1. Heurísticas de predicción de aristas . . . . . . . . . . . . . . . . . 52 6.1.1. Heurísticas de orden bajo . . . . . . . . . . . . . . . . . . 52 6.1.2. Heurísticas de orden alto . . . . . . . . . . . . . . . . . . 53 6.1.3. γ-heurísticas ......................... 54 6.2. SEAL ................................. 57 6.2.1. Features explícitas ...................... 57 6.2.2. Etiquetas de estructura . . . . . . . . . . . . . . . . . . . 58 6.2.3. Node Embeddings ....................... 59 6.2.4. Definición de SEAL . . . . . . . . . . . . . . . . . . . . . 61 6.3. Elección del modelo y evaluación del rendimiento de SEAL . . . 61 7. Método GAug-M para data augmentation en grafos. 65 7.1. Posibles estrategias para data augmentation en grafos . . . . . . 66 7.2. GAug-M ............................... 66 7.2.1. Motivación teórica . . . . . . . . . . . . . . . . . . . . . . 66 4 ÍNDICE GENERAL 5 7.2.2. Definición de GAug-M ................... 67 7.2.3. Evaluación y rendimiento de GAug-M ........... 69 8. Evaluación de GAug-M usando SEAL 72 8.1. Obtención de la matriz de probabilidades . . . . . . . . . . . . . 73 8.2. Aplicación de GAug-M yevaluación................ 75 9. Conclusiones y trabajos futuros 77 5 Capítulo 1 Introducción En los últimos años, el novedoso campo de estudio de las Graph Neural Networks (GNNs) ha avanzado enormemente, desarrollando nuevas y mejores arquitecturas para la resolución de problemas de aprendizaje supervisado sobre datos con estructura de grafo, como pueden ser; clasificar las funciones de cada proteína en un interactoma1[9] (clasificación sobre nodos de un grafo), predicción de la toxicidad o la solubilidad de una molécula [6], o encuadrarla en una categoría (clasificación/regresión sobre un grafo), además de predicción de la probabilidad de que dos usuarios sean amigos en una red social (obtención de la probabilidad de la existencia de una arista entre dos nodos [34]). La idea principal de un modelo de Graph Neural Network es la de actualizar los estados de los nodos en base a los estados de sus nodos vecinos, cuya información viene codificada por una función de agregación, para utilizarla junto con el estado anterior en una función de actualización. En el ámbito de data augmentation (cuyo objetivo es aumentar o mejorar los datos de entrenamiento, para obtener un mejor rendimiento del modelo), campos de estudio como reconocimiento de imágenes aprovechan la naturaleza euclídea de los datos, para generar nuevos datos de entrenamiento, realizando operaciones como voltear la imagen, reflejarla, aplicar filtros visuales, etc. Sin embargo, en el caso de datos estructurados en grafos, los métodos convencionales de data augmentation no funcionan debido a que están definidos en un espacio no euclídeo [4]. Es por ello que se han ideado nuevos métodos que manipulan aristas y nodos para llevar a cabo la tarea de data augmentation sobre grafos. En este trabajo, veremos uno de esos métodos, conocido como GAug-M [37], pensado para mejorar un grafo a la hora de enfrentarnos a un problema de clasificación de sus nodos. El método se basa en alguna estructura de Graph 1Conjunto de todas las interacciones moleculares dentro de una célula en particular. 6 7 Neural Network de la que podamos obtener la probabilidad de existencia de cualquier posible arista del grafo, para luego añadir al grafo las aristas con mayor probabilidad, y eliminar (si existían) las de menor probabilidad, de manera que se enriquezca la información del grafo, y el modelo sea capaz de distinguir más fácilmente las clases. Originalmente, el rendimiento de GAug-M se evalúa utilizando Variational Graph Auto Encoder (VGAE) [14] como modelo predictor de aristas. Sin embargo, en este TFM, como novedad, nosotros emplearemos la metodología SEAL para obtener las probabilidades, y llevaremos a cabo experimentos con esta nueva combinación bajo las mismas condiciones que los realizados en [37] (misma GNN para clasificación de nodos, sobre los mismos datasets), y compararemos el rendimiento obtenido con el rendimiento original, para concluir si la mejora de SEAL respecto a otros modelos de predicción de aristas (incluido VGAE) se traduce en una mejora de rendimiento de GAug-M. Llevaremos a cabo estos experimentos mediante scripts de python, que pueden consultarse en el repositorio SEAL-GAugM, creado por mí específicamente para este trabajo. En el Capítulo 2 recordamos las definiciones básicas de grafos, y mostramos algunos ejemplos de tipos de datos que se pueden estructurar como grafos, mientras que en el Capítulo 3 explicamos en qué consiste un problema de aprendizaje supervisado de forma general, y los conceptos y métodos necesarios para resolverlos. A continuación, explicamos las redes neuronales (Capítulo 4), modelos ampliamente conocidos y usados en aprendizaje automático, comúnmente encuadrados en aprendizaje profundo (deep learning). Esto nos permitirá comprender las Graph Neural Networks, de las que hablaremos en el Capítulo 5. A continuación, explicaremos y justificaremos la metodología SEAL para predicción de aristas (Capítulo 6), para luego hablar del método de data augmentation GAug-M (Capítulo 7), además de comentar el rendimiento de cada uno de ellos. Finalmente, llevaremos a cabo experimentos con la nueva combinación de GAug-M ySEAL (Capítulo 8), para comparar los resultados con los obtenidos en [37] (obtenidos con la combinación GAug-M yVGAE). Terminaremos la memoria con un capítulo dedicado a conclusiones y trabajos futuros (Capítulo 9). 7 3.1. APRENDIZAJE SUPERVISADO 14 3.1.1. Conjunto de datos de entrenamiento y de test En aprendizaje supervisado, un modelo se ajusta a un conjunto de datos finito del que conocemos el valor de la variable objetivo (conjunto de entrenamiento) con el fin de poder predecir o clasificar datos nuevos, lo que se conoce como capacidad de generalización. El modelo puede entenderse como una función que depende de un conjunto de parámetros que se ajustan durante un proceso de optimización. Se parte de un conjunto de parámetros iniciales que se suelen llamar pesos y que, a partir de una función objetivo o error, se ajustan durante un proceso de minimización. El objetivo en aprendizaje automático es la búsqueda de un modelo capaz de predecir o aproximar una función "ideal" f:X−→ Y, que asocia a cada vector de datos de entrada el valor correcto (real) de la variable objetivo (p.ej., la clase a la que pertenece, o el valor de la magnitud numérica que queremos predecir). Conocemos el valor de esta función fpara los datos de entrenamiento, lo que nos sirve para llevar a cabo un proceso de optimización de los parámetros del modelo. Formalmente, podemos definir un modelo como una función gθ:X−→ Y, que depende de un conjunto de parámetros θ⊆Θ, donde Θes el espacio de posibles parámetros. Estos parámetros se determinan escogiendo unos valores iniciales1, y optimizándolos usando el conjunto de entrenamiento, junto con una función error que compara gθcon f, y un algoritmo que minimiza esta función de error, ajustando los parámetros durante el proceso, hasta que se obtenga el rendimiento deseado o se haya repetido el algoritmo una cantidad de veces previamente prefijada (criterios de parada). Definición 3.1.1. Un conjunto de datos de entrenamiento, T={(x1, y1), ..., (xN, yN)}, está formado por pares, donde los xison vectores de un cierto conjunto de datos de entrada, X⊆Rn(decimos que nes el número de variables de entrada, o features), y los yison los valores de la variable objetivo asociados a cada uno de los vectores. En la práctica, el conjunto de datos de entrenamiento nunca está formado por la totalidad de los datos de los que conocemos la variable objetivo, sino que se realiza una división de los mismos en conjunto de entrenamiento y conjunto de test. Este último sirve para, una vez entrenado el modelo, medir el rendimiento del mismo, para tener una idea de lo buenas que serán las predicciones y compararlo con otros modelos. De esta manera, conseguimos simular el rendimiento del modelo con datos reales de los que no conocemos la variable a predecir, ya que en la fase de entrenamiento, el modelo solo aprende de información que proviene del conjunto de entrenamiento, mientras que la del conjunto 1Existen distintas formas de tomar los valores iniciales, aunque suelen ser escogidos de manera aleatoria. 14 3.2. FUNCIONES DE COSTE 15 de test es información nueva. Además de la división en entrenamiento y test, hay otras técnicas de evaluación y entrenamiento como la validación cruzada (cross-validation). Es muy importante evitar que el modelo obtenga información del conjun- to de test, ya que entonces no simularía correctamente su comportamiento con datos reales. Cuando esto ocurre, diremos que se está produciendo data leakage. Veremos más adelante que hay situaciones en las que tenemos que dividir nuestros datos hasta en 3 partes para evitar este fenómeno. En el caso particular de las Graph Neural Networks, que introduciremos en el Capítulo 5, veremos que no se cumple del todo el requisito de no obtener información de los datos de test, debido a su arquitectura, a pesar de que sigue los principios de un problema de aprendizaje supervisado (optimizamos sobre el conjunto de entrenamiento, y evaluamos sobre el de test). Es por ello que los consideramos modelos de aprendizaje semi-supervisado. 3.2. Funciones de coste Hemos hablado de funciones que miden el error que comete gθal aproximar f. Estas funciones son las funciones de coste, que estudiamos a continuación. Definición 3.2.1. Una función de coste (loss function), L, se define sobre el espacio de parámetros Θ, y mide el error que cometen las predicciones del modelo sobre el conjunto de entrenamiento, cosa que podemos hacer ya que conocemos los yisobre ese conjunto. L: Θ −→ R≥0 θ−→ εT Damos a continuación los ejemplos más importantes de funciones de coste, tanto para: Problemas de regresión, donde la variable objetivo es un valor numérico continuo, y el modelo calcula el valor de la misma correspondiente a una observación. Problemas de clasificación, donde la variable objetivo toma un número finito de valores, que identificamos con clases, y el modelo calcula la probabilidad de que una observación pertenezca a cada clase. Ejemplo 3.2.2. La función de error medio absoluto, o MAE (mean absolute error) se define como: 15 3.2. FUNCIONES DE COSTE 16 L(θ) = 1 N N X i=1 |gθ(xi)−yi|,(3.1) donde Nes la cardinalidad de T. Ejemplo 3.2.3. La función de error cuadrático medio, o MSE (mean squared error) se define como: L(θ) = 1 N N X i=1 (gθ(xi)−yi)2.(3.2) Ambas funciones de coste sirven para medir el error en problemas de regresión, pero son muy parecidas entre sí. Sin embargo, la diferencia entre las dos es que la función de error cuadrático medio penaliza más los errores graves del modelo, ya que, en ese caso, el cuadrado de la diferencia es mayor que la diferencia absoluta (generalmente, se tiene |gθ(xi)−yi|>1si el error se considera grave). Por otro lado, la función de error medio absoluto penaliza más un modelo que cometa muchos errores pequeños (|gθ(xi)−yi|<1), ya que elevar al cuadrado estas cantidades las hace más pequeñas. Por lo tanto, la elección de una función u otra dependerá de cada problema en particular, y del objetivo que busquemos cumplir con el modelo. Si queremos un modelo que, sin ser el más preciso, sea fiable y no cometa errores muy graves, utilizaremos el error cuadrático medio. Sin embargo, si podemos permitirnos pocos errores graves pero buscamos mucha precisión en general, utilizaremos el error medio absoluto. Veamos ahora una función de coste más adecuada para medir el error en un problema de clasificación. Ejemplo 3.2.4. La función de coste cross-entropy se define como: L(θ) = − N X i=1 M X k=1 yi,k log(gθ(xi)k),(3.3) donde Mes el número de valores que puede tomar la variable objetivo (número de clases), yi,k = 1 si la observación xipertenece a la clase k, e yi,k = 0 en caso contrario, y gθ(xi)kes la probabilidad (calculada por el modelo, y estrictamente positiva) de que la observación xipertenezca a la clase k. Parece una definición complicada, pero analicémosla para entender la lógica que hay detrás: 16 3.3. OPTIMIZACIÓN DEL MODELO 17 Los valores gθ(xi)kse encuentran en el intervalo (0,1] al ser probabilidades no nulas, por lo que log(gθ(xi)k)≤0, y por ello incluimos un signo menos antes del sumatorio sobre las clases. Por otro lado, sólo uno de los yi,k es igual a 1(el correspondiente a la clase a la que pertenece xi), mientras que el resto es igual a 0. Con lo cual, tenemos las siguientes situaciones: – Si el modelo hace una buena predicción, es decir, la probabilidad gθ(xi)kes alta, donde kes tal que yi,k = 1, el valor −log(gθ(xi)k)es cercano a cero, por lo que el valor de la función de coste es pequeño. – Si, en su lugar, gθ(xi)kes baja, el valor −log(gθ(xi)k)es más grande que en el caso anterior, por lo que la función de coste penaliza esta mala predicción. 3.3. Optimización del modelo Ahora que sabemos el planteamiento de un problema de aprendizaje supervisado, la siguiente pregunta es: ¿cómo lo resolvemos? ¿Cómo actualizamos los parámetros para minimizar la función de coste? Lo primero en lo que podríamos pensar es en encontrar el mínimo de manera analítica, usando optimización de funciones en varias variables. Sin embargo, esto no va a funcionar en general, ya que lo normal es que el conjunto de parámetros θsea grande, y no dos o tres variables, como la mayoría de funciones de las cuales obtenemos los máximos y mínimos en cálculo en varias variables. Por lo tanto, lo normal es que tengamos una expresión que no sea posible optimizar de manera analítica. Por otro lado, queremos que el aprendizaje del modelo sea un proceso automático, e implementable en un ordenador. Es por ello que aplicaremos un algoritmo heurístico para aproximar un mínimo local que no nos proporcionará la solución óptima al problema de minimización, es decir, en general alcanzaremos un mínimo local ya que la función no tiene por qué ser convexa. 3.3.1. Descenso del gradiente y variantes El algoritmo del que hablamos es el método de descenso del gradiente. Este método se basa en la siguiente idea: el gradiente de la función coste, ∇L es un vector que indica, en cada punto, la dirección hacia la cual la función L crece. Basándonos en esta idea, formalizaremos lo siguiente: partimos de un punto cualquiera, calculamos el gradiente de la función en ese punto, y nos movernos un poco en la dirección contraria al gradiente hacia un nuevo punto 17 3.3. OPTIMIZACIÓN DEL MODELO 18 (donde esperamos que la función coste tenga un valor inferior al del punto anterior), en el que volvemos a repetir el proceso, hasta que se cumpla cierto criterio de parada que puede ser, entre otros, que la función coste alcance un valor aceptable (tolerancia), o simplemente hacer un número fijo de iteraciones. Podemos imaginar este proceso en dos dimensiones más fácilmente, donde el mínimo local se encuentra en el punto más bajo de un valle de la función, y el movimiento sería el de una pelota que cae hacia el mínimo en cada caso. Para entender el algoritmo, recordemos algunas definiciones de cálculo en varias variables. Definición 3.3.1. Sea f:Rn→R. Definimos el gradiente de fcomo ∇f=∂f ∂x1 , ..., ∂f ∂xn, donde cada coordenada es la derivada parcial ∂f ∂xi = l´ım h→0 f(x1, ..., xi+h, ..., xn)−f(x1, ...xn) h. En nuestro problema, tendríamos ∇L =∂L ∂θ1 , ..., ∂L ∂θk, donde θ={θ1, ..., θk}es el conjunto de parámteros del modelo. Utilizaremos una herramienta clave del cálculo en varias variables, que es la aproximación lineal de la función en un punto. Podemos asumir que, dado un punto θ0(vector de kcomponentes), y un entorno suficientemente pequeño del mismo, se tiene L(θ)≈ L(θ0) + ∇L · (θ−θ0) Y por lo tanto, si llamamos ∆θ=θ−θ0, tenemos que: L(θ)− L(θ0)≈ ∇L · ∆θ(3.4) Por tanto, esta ecuación nos permite escoger ∆θde manera que ∆Lsea negativo, reduciendo así el valor de la función objetivo. No podemos realizar cambios muy grandes cada vez, ya que no debemos alejarnos demasiado del punto debido a la aproximación lineal de ∆Lque estamos utilizando, por lo que restringimos: ||∆θ|| =ε,ε > 0.Teniendo en cuenta esta restricción, es lógico pensar que no solo queremos una elección de ∆θque consiga este objetivo, sino la mejor. 18 3.3. OPTIMIZACIÓN DEL MODELO 19 Teorema 3.3.2 ([18]).La elección de ∇θque minimiza ∆Len la ecuación 3.4, sujeta a ||∆θ|| < ε, ε > 0es ∆θ=−µ∇L, µ =ε ||∇L|| (3.5) Demostración. Tenemos, por la desigualdad de Cauchy-Bunyakovsky-Schwarz, que |∇L · ∆θ| ≤ ||∇L||||∆θ|| =||∇L||ε y sabemos que la igualdad, que nos daría el mayor cambio que podemos conseguir en el valor absoluto de ∇L · ∆θ, se da cuando los vectores son linealmente dependientes, es decir, ∆θ=±µ· ∇L,µ∈R>0. Naturalmente, escogemos el signo negativo, ya que queremos minimizar ∇L · ∆θ. Por otra parte, por la restricción, tenemos que ||∆θ|| =ε=µ||∇L|| ⇒ µ=ε ||∇L||. Llamamos a µcoeficiente de aprendizaje (o learning rate), y normalmente lo utilizaremos como valor por defecto para determinar los cambios ∆θ(escogido µ,εestá unívocamente determinado por la ecuación 3.5). Este valor no debe escogerse muy grande, dado que no podemos hacer cambios muy grandes debido a la aproximación de la ecuación 3.4 que utilizamos para ∆L. Sin embargo, tampoco debe escogerse demasiado pequeño, ya que eso hará que el algoritmo trabaje lentamente, es decir, que necesite muchas iteraciones hasta satisfacer alguna condición de parada. En la práctica, se escoge un valor de entre una serie de valores en escala logarítmica, (p. ej., µ∈ {0.001,0.01,0.1,1,10}). Para ello, se entrena el modelo con cada una de las posibilidades, y se comprueba el valor de la función coste asociado a cada uno en el conjunto de test, para elegir el valor del parámetro que nos de mejor rendimiento. Parámetros del mismo tipo que el learning rate, distintos a los parámetros intrínsecos del modelo, θ, que no se optimizan en el proceso de aprendizaje, sino que tenemos que escogerlos previamente, se conocen como hiperparámetros del modelo. Sin embargo, para escoger el valor de un hiperparámetro como hemos descrito, es necesario tener un tercer conjunto de datos etiquetados para evaluar el modelo, que llamamos conjunto de validación. Esto se debe a que, al usar el conjunto de test para escoger los hiperparámetros del modelo final, estamos obteniendo información del mismo, por lo que evaluar el modelo con el conjunto de test daría lugar a data leakage. Un tercer conjunto distinto a los otros dos del que no hayamos obtenido ninguna información resuelve este problema. Una práctica común es dividir los datos disponibles de manera que un 50 % sea el 19 3.3. OPTIMIZACIÓN DEL MODELO 20 conjunto de entrenamiento, y cada 25 % restante sea cada uno de los otros dos conjuntos. Algoritmo 3.3.1 (Descenso del gradiente).Dado un modelo de aprendizaje supervisado, inicializado con parámetros θ, un conjunto de entrenamiento Tde tamaño N, una función de coste L, un coeficiente de aprendizaje µy, o bien un entero k(número de iteraciones) o bien un ε > 0(tolerancia), hacer: 1. Calcular ∇L =Px∈T∇Lx2. 2. Actualizamos cada componente del vector de parámetros según la regla θi−→ θ′ i=θi−µ∂L ∂θi 3. Si el criterio de parada es tolerancia, comprobar si L(θ′)≤ε. En caso afirmativo, parar y devolver θ′. En caso contrario, repetir 1. Si el criterio de parada es el número de iteraciones, repetir 1., y parar y devolver θ′en la k-ésima iteración. Esta aproximación inicial a un buen algoritmo presenta un problema: para calcular el gradiente ∇L, es necesario calcular cada uno de los gradientes ∇Lx. Normalmente, los conjuntos de entrenamiento son grandes, para que el modelo disponga de suficientes datos para aprender los patrones y extraer suficiente información para ser predictivo. Por lo tanto, este cálculo puede hacer que nuestro algoritmo sea muy ineficiente. Para solucionarlo, se usa una versión ligeramente distinta de este algoritmo, el descenso del gradiente estocástico. Esta consiste en tomar aleatoriamente un subconjunto {X1, ..., Xm}de T, relativamente pequeño en comparación, y entrenar el modelo con el mismo para reducir el número de cálculos. Una vez hecho esto, desechamos estos datos de entrenamiento, y tomamos otro subconjunto de Tdisjunto del anterior, y volvemos a entrenar el modelo. Cuando ya no podemos escoger otro subconjunto de tamaño mde T, decimos que termina una época de aprendizaje. A continuación, podemos volver a aplicar este proceso un número determinado de veces, ya que cada vez los subconjuntos se escogen aleatoriamente, es decir, entrenar el modelo durante varias épocas. Esta idea mejora considerablemente la eficiencia, pero también tiene sus contras. En concreto, no calculamos el valor real del gradiente ∇L, sino una aproximación basada en el subconjunto tomado aleatoriamente. Sin embargo, es esperable que sea una aproximación suficientemente buena si escogemos subconjuntos de un tamaño msuficiente. 2Asumimos que la función coste se puede escribir como suma de costes asociados a cada elemento del conjunto de entrenamiento. En la práctica esto ocurre prácticamente en la totalidad de los casos, como en los ejemplos de funciones coste que hemos visto. 20 3.4. EVALUACIÓN DEL MODELO 21 Algoritmo 3.3.2 (Descenso del gradiente estocástico).Dado un modelo de aprendizaje supervisado, inicializado con parámetros θ, un conjunto de datos de entrenamiento Tde tamaño N, una función de coste L, un coeficiente de aprendizaje µ, un entero positivo m<N(tamaño de los subconjuntos) y, o bien un entero ko bien un ε > 0, hacer Eveces (épocas de entrenamiento): 1. Generar aleatoriamente {X1, ..., Xm} ⊆ D. 2. Aplicar el Algoritmo 3.3.1 con D={X1, ..., Xm}y con kiteraciones o tolerancia εcomo criterio de parada. 3. Actualizar D−→ D′=D− {X1, ..., Xm}. Si |D′|> m, repetir 1., en caso contrario, terminar y devolver los parámetros θ′. Otra variante, conocida como on-line leraning, se da cuando tomamos m= 1, es decir, entrenamos el modelo con una única muestra cada vez que llegamos al paso 2. Este método se utiliza cuando se tiene un modelo listo para hacer predicciones sobre datos reales, pero también aparecen nuevos datos de entrenamiento con el paso del tiempo. Con el aprendizaje en línea, el modelo puede mantenerse actualizado cada vez que aparece un nuevo dato de entrenamiento, en lugar de reentrenarlo cada cierto período de tiempo añadiendo los nuevos datos, lo que le permite estar completamente actualizado. 3.4. Evaluación del modelo Una vez que hemos finalizado el entrenamiento del modelo, el siguiente paso es evaluar su rendimiento. Esto se lleva a cabo calculando ciertos valores predefinidos sobre el conjunto de test, que llamamos métricas de evaluación, y que nos dan una idea del rendimiento de las distintas cualidades del modelo. 3.4.1. Overfitting,underfitting y conjunto de validación Los cálculos de las métricas de evaluación deben realizarse sobre el conjunto de test, ya que si los hiciésemos sobre el conjunto de entrenamiento, estaríamos evaluando únicamente la capacidad del modelo de ajustarse a esos datos, en lugar de su capacidad de generalizar a nuevas observaciones. Cuando un modelo se ajusta de manera excesiva al conjunto de entrenamiento, y no generaliza bien a nuevos datos (su evaluación en el conjunto de entrenamiento es buena, pero en el de test es mala), decimos que se produce overfitting (el modelo se sobreajusta) situación que sugiere reducir la complejidad del modelo. Por el contrario, si el modelo tiene un mal rendimiento en ambos conjuntos, decimos 21 3.4. EVALUACIÓN DEL MODELO 22 que se produce underfitting, lo que indica que el modelo no está aprendiendo correctamente de los datos de entrenamiento, y que es necesario aumentar la complejidad del modelo (flexibilidad, número de features de las que aprende, etc). En definitiva, debemos modificar los hiperparámetros, y escoger una combinación adecuada para obtener la versión final del modelo. Sin embargo, si evaluamos los modelos obtenidos con las distintas combinaciones de hiperparámetros en el conjunto de test para escoger la combinación óptima, y usamos esa evaluación como medidor final del rendimiento del modelo, no sería del todo fiable, ya que estaríamos evaluando una vez más la capacidad del modelo de ajustarse a los datos de test, en lugar de su capacidad de generalizar a los nuevos datos. Es por ello que es necesario utilizar un tercer conjunto de datos (conjunto de validación) para evaluar cada una de las combinaciones de hiperparámetros, y así poder dar la evaluación final usando el conjunto de test, para dar una estimación fiable del rendimiento del modelo. Con lo cual, el proceso para entrenar y escoger un modelo podría ser el siguiente: 1. Separar el conjunto de datos en conjuntos de entrenamiento, test y validación. Comúnmente, se reservan la mayoría de los datos para el entrenamiento, de manera que el modelo tenga más datos de donde aprender. Un ejemplo de separación sería utilizar el 60 % de los datos para el conjunto de entrenamiento, un 20 % para el de test y el 20 % restante para el de validación. 2. Escoger posibles combinaciones de hiperparámetros del modelo, como pueden ser, si se trata por ejemplo de una red neuronal, el número de capas, las conexiones entre ellas, o la probabilidad límite de decisión si se trata de un problema de clasificación. A continuación, entrenar el modelo en el conjunto de entrenamiento con cada una de las combinaciones. 3. Calcular las métricas de evaluación correspondientes para cada combinación de hiperparámetros sobre el conjunto de validación. Escogemos el modelo correspondiente a la combinación que haya obtenido la mejor evaluación. 4. Evaluar el modelo escogido sobre el conjunto de test, para obtener la evaluación final. Este proceso que acabamos de describir no es la única manera de utilizar el conjunto de validación para escoger un modelo. Por ejemplo, cuando se entrenan modelos de aprendizaje profundo (redes neuronales o Graph Neural Networks) a lo largo de varias épocas (ver Algoritmo 3.3.2), se suele utilizar el conjunto de validación para evaluar el modelo resultante después de cada una de las épocas, de manera que, cuando finaliza el entrenamiento, podamos escoger el modelo resultante de la época en la que hayamos obtenido la mejor evaluación. 22 3.4. EVALUACIÓN DEL MODELO 23 Esto previene el posible overfitting resultante de entrenar durante demasiadas iteraciones el modelo. Esta técnica es la que emplearemos en la práctica para entrenar el modelo SEAL, que veremos más adelante en el Capítulo 6. Ahora que tenemos una idea general de cómo se evalúa un modelo, veamos algunas de las métricas más usadas, y en qué casos se utiliza cada una. 3.4.2. Métricas de evaluación En el caso de problemas de clasificación, veremos primero métricas específicas para problemas de clasificación binarios, y después veremos cómo generalizan a problemas con más de dos clases. Definición 3.4.1. Dado un conjunto de pares clase-predicción P={(c1, v1), . . . ,(cn, vn)}(clase real de un dato, y predicción obtenida por un modelo), donde ci, vi∈ {P, N}(clase positiva y clase negativa), definimos: El número de verdaderos positivos, TP (True Positives) como el número de pares tales que ci=vi=P. El número de falsos positivos, FP (False Positives) como el número de pares tales que ci=Nyvi=P. El número de verdaderos negativos, TN (True Negatives) como el número de pares tales que ci=vi=N. El número de falsos negativos, FN (False Negatives) como el número de pares tales que ci=Pyvi=N. Estos valores se suelen representar en una matriz de dimensión 2×2llamada matriz de confusión, donde cada fila y cada columna se asocia con cada una de las clases reales y predichas respectivamente, obteniendo así los 4 valores en cada una de las entradas de la matriz (Figura 3.1). Los valores de la definición anterior son las piezas con las que se definen las métricas que vemos a continuación. Definición 3.4.2. Dado un conjunto de pares clase-predicción P={(c1, v1), ..., (cn, vn)}, donde las predicciones han sido obtenidas mediante un modelo, se definen: La accuracy3del modelo como Accuracy =TP +TN TP +FP +TN +FN . 3Utilizamos el término en ingles debido a la falta de un término distinto a "Precisión" en castellano que nos permita distinguir accuracy y precisión 23 4.1. COMPONENTES DE UNA RED NEURONAL 30 donde los wison números reales que llamamos pesos, y ces otro número real, comúnmente llamado bias. Intuitivamente, un perceptrón es una máquina que, en función de una serie de valores binarios (que pueden representar, por ejemplo, si se cumplen determinadas condiciones o no) toma una decisión (1 o 0). Nosotros definimos los pesos wiy el bias c, de manera que: Controlamos si una condición influye positiva o negativamente y en qué medida a la hora de decidir, mediante los pesos wi. Controlamos el umbral con el que el perceptrón responde afirmativa o negativamente, aumentando o disminuyendo c. Por ejemplo, supongamos que queremos diseñar un perceptrón que responda si va a llover o no mañana, en función de la predicción de AEMET1,x1, y la opinión de dos amigos, x2yx3(Figura 4.1). Supongamos que nos fiamos más de la predicción de AEMET, y a continuación de la del primer amigo. Una manera de diseñar el perceptrón sería: w1= 5,w2= 2,w3= 1 yc= 4. En este caso, podemos observar que el perceptrón predice que va a llover si y solo si x1= 1. Es decir, nuestro perceptrón ignora la opinión de nuestros amigos y se fía únicamente de la predicción de AEMET. x1 x2 x3 c= 4 f(x1, x2, x3) 5 2 1 Figura 4.1: Un ejemplo de perceptrón Sin embargo, podríamos modificarlo, poniendo c= 6. Ahora, no basta con x1para responder que sí. El perceptrón responde “sí” si AEMET y el primer amigo dicen que sí, sin embargo, no le bastaría con el “sí” de AEMET y el segundo amigo. Por lo tanto, en función de la situación o de cómo queremos que se comporte el perceptrón, podemos modificar sus pesos y su límite para cambiar su decisión. Veremos más adelante que la misma idea de modificar los pesos para cambiar la decisión es la clave del aprendizaje de una red neuronal. Otra manera de escribir la definición de f(que usaremos de ahora en adelante) es usando lo que llamamos el sesgo, que es sencillamente b=−c. Además, podemos utilizar la notación vectorial n P i=1 wixi=wTxlo que nos permite escribir 1Agencia Estatal de Meteorología https://www.aemet.es/es/ 30 4.1. COMPONENTES DE UNA RED NEURONAL 31 fcomo: f(x1, ..., xn) = (1,si wTx+b > 0 0,si wTx+b≤0 que es más compacto y fácil de manejar. 4.1.2. Neuronas y funciones de activación Sin embargo, para poder aplicar el algoritmo de descenso del gradiente buscamos que, mediante pequeños cambios en los pesos y en el sesgo, modifiquemos ligeramente la respuesta de los perceptrones hasta que den la respuesta buscada para ciertos datos de entrada. Pero pequeños cambios en wiy en bcon la definición que hemos dado solo pueden provocar que el perceptrón cambie bruscamente su respuesta de 0a1o viceversa, o bien que el perceptrón responda lo mismo que antes del cambio, con lo cual no podemos saber de qué forma hay que cambiar los wiy los bde manera que haya un aprendizaje. Por ello, necesitamos hacer uso de una cierta función continua creciente σ, que llamamos función de activación, de manera que σ:R→(0,1) y tal que l´ım z→∞ σ(z) = 1,l´ım z→−∞ σ(z)=0. De esta manera, si z=wTx+b, la función simula el comportamiento del perceptrón θ, pero además podemos ver el resultado como una probabilidad entre 0y1, y pequeños cambios a los parámetros provocarán pequeños cambios al valor de probabilidad σ(z). Así, podremos acercar el perceptrón al valor deseado mediante pequeños cambios en los parámetros. En conclusión, modificaremos ligeramente la definición de perceptrón incluyendo esta idea. Definición 4.1.2. Una neurona, es una función continua f: [0,1]n→(0,1), de manera que f(x1, ..., xn) = σ(z), z =wTx+b, donde σes una función de activación. Es decir, una neurona puede recibir valores reales entre 0 y 1, lo cual es una ventaja para problemas como, por ejemplo, reconocimiento de imágenes, ya que los datos pueden representar la intensidad de cierto color en cada píxel. En el caso del ejemplo anterior sobre predecir el clima, obtendríamos la probabilidad de que mañana llueva o no, en lugar de un simple "sí" o "no". Sin embargo, también pueden usarse para resolver problemas de decisión al igual que un perceptrón. Para ello, consideramos un límite de probabilidad, a partir del cual damos una respuesta positiva. Por ejemplo, podríamos definir que la respuesta 31 4.1. COMPONENTES DE UNA RED NEURONAL 32 es “sí” si la neurona responde un valor de probabilidad superior a 0.5, o “no” si es menor que 0.5. Existen varias funciones de activación conocidas y muy usadas, sin embargo, el ejemplo que damos a continuación es la que usaremos con más frecuencia en el trabajo. Ejemplo 4.1.3. La función logística se define como: σ(z) = 1 1 + e−z, z ∈R(4.1) Es una función de activación, ya que σ(z)∈(0,1), debido a que 1 + 1 ez>1 ∀z∈R, y además es fácil comprobar que es creciente y que cumple l´ım z→∞ σ(z)=1,l´ım z→−∞ σ(z)=0. La función logística es ideal para representar el resultado de un perceptrón como una probabilidad, ya que se tiene σ(0) = 0.5, y además, crece muy rápidamente, tanto hacia 0para valores negativos como hacia 1para valores positivos (Figura 4.2) Otros ejemplos importantes de funciones de activación son: Ejemplo 4.1.4. La función ReLu (Rectified Linear Unit). σ(z) = m´ax(0, z) = (0,si z < 0 z, si z≥0 Es utilizada comúnmente en redes neuronales para que ciertas neuronas no se activen (devuelvan 0 como respuesta), lo que consigue reducir los cálculos y hacer que neuronas que no sean relevantes para la decisión no sean tenidas en cuenta. Ejemplo 4.1.5. La función SoftMax. A diferencia de las anteriores, recibe como entrada un vector de datos. σ:Rn−→ [0,1]n σ(z)j=ezj Pn k=1 ezk, j = 1, ..., n. La función SoftMax es comúnmente usada en problemas de clasificación en los que se usan redes neuronales, ya que si se escoge como función de activación de la última capa, se obtiene como resultado una distribución de probabilidades de pertenecer a cada una de las clases. 32 4.2. EL MODELO DE APRENDIZAJE DE REDES NEURONALES 33 Figura 4.2: Gráfica de la función logística para valores cercanos a 0. 4.2. El modelo de aprendizaje de redes neuronales Ahora que conocemos el funcionamiento de las neuronas, podemos hablar de redes neuronales. Comentaremos algunos tipos de capas comúnmente usadas en redes neuronales, y también explicaremos el algoritmo de propagación hacia atrás para poder optimizarlas mediante descenso del gradiente. 4.2.1. Redes Neuronales Las redes neuronales son uno de los modelos más importantes en Machine Learning. Conforman su propia rama, llamada deep learning, y son ampliamente usadas en diversos problemas, como por ejemplo, reconocimiento de imágenes, como identificar dígitos escritos a mano [18], entre otros. Además de ver su definición, veremos algunos ejemplos comúnmente usados de tipos de capas de redes neuronales, diseñadas para tareas específicas. Definición 4.2.1. Una red neuronal es un modelo de aprendizaje supervisado que está formado por lconjuntos ordenados de neuronas, llamados capas, de manera que: 1. La primera capa, o capa de entrada, recibe valores de entrada x1, ..., xn para cada neurona. 2. Las capas intermedias, o capas ocultas, reciben valores arrojados por las neuronas de capas anteriores, pero nunca de neuronas de capas posteriores, es decir, no existen conexiones hacia atrás. Es por ello que también se suelen llamar feedforward neural networks, en contraposición a las recurrent neural networks, que sí pueden presentar este tipo de conexiones. 33 4.2. EL MODELO DE APRENDIZAJE DE REDES NEURONALES 34 La respuesta de una neurona puede ser valor de entrada de más de una neurona en las capas siguientes. 3. La respuesta de la red neuronal es el conjunto de respuestas de las neuronas de la última capa, o capa de salida. x1 x2 Entrada x3 x4 x5 Salida Figura 4.3: Un ejemplo de una red neuronal, en este caso con una capa oculta, 5 valores de entrada y uno de salida. Cada nodo es una neurona con distinto número de entradas, con sus correspondientes pesos y sesgos. Un detalle a tener en cuenta es que el número de entradas y de neuronas de salida depende del problema en cuestión. Por ejemplo, si tenemos un problema de clasificación con kcategorías, y queremos obtener la probabilidad de pertenecer a cada categoría, necesitaremos tener kneuronas en la capa de salida (con una activación SoftMax a continuación), mientras que el número de entradas siempre será el número de variables que tendremos en cuenta para hacer la predicción. En contraposición, el número de capas ocultas de la red neuronal y el número de neuronas en cada una de las capas que no sean la salida son, esencialmente, hiperparámetros de nuestro modelo, al igual que el learning rate. Esto quiere decir que podríamos comparar distintas arquitecturas de redes neuronales utilizando el conjunto de test, para luego medir el rendimiento de la que escojamos utilizando el conjunto de validación. Veamos algunos ejemplos de tipos de capas de redes neuronales comúnmente usadas. Ejemplo 4.2.2. Decimos que una capa de red neuronal es completamente conexa si todos los outputs de la capa anterior son inputs de todas las neuronas de la capa. Es decir, tendríamos todas las conexiones posibles entre neuronas de la capa anterior y la capa completamente conexa, como en la Figura 4.4 Los siguientes ejemplos están inspirados en las convolutional neural networks, pero en este caso, trabajan en una dimensión. 34 4.2. EL MODELO DE APRENDIZAJE DE REDES NEURONALES 35 Figura 4.4: Ejemplo de una capa completamente conexa con 3 neuronas. Ejemplo 4.2.3. Una capa de convolución 1-D, con tamaño de kernel ky step s, es una capa de red neuronal cuyas conexiones se definen de la siguiente manera: si el output de la capa anterior tiene longitud n, de manera que n=k+ms para algún m∈N: colocamos una neurona que recibe las coordenadas 1, ..., k del vector, a continuación, la segunda neurona, que recibe las coordenadas 1 + s, ..., k +sdel vector, etc. Así, hasta la última neurona, que recibe las coordenadas n−s, ..., n del vector. Intuitivamente, podemos imaginar un filtro de tamaño ksobre las coordenadas del vector, del cual tomamos los inputs de cada neurona que se coloca. Una vez colocada la neurona, movemos el filtro sposiciones a la derecha, y colocamos otra, así hasta que no podamos mover más el filtro a la derecha. La condición n=k+ms se impone para que el último filtro coincida con las kcoordenadas finales del vector. El esquema de la Figura 4.5 hace más facil la comprensión de una capa de convolución 1-D. Ejemplo 4.2.4. Una capa MaxPooling funciona exactamente igual que una capa de convolución 1-D, salvo que, para cada posición del filtro, en lugar de definir una neurona, simplemente tomamos el máximo de las coordenadas del kernel como output de esa posición del kernel. Supongamos que, en un situación igual que la de la Figura 4.5, el vector input es v= (2,5,6,5,9,3,9,0). Entonces, una capa MaxPooling con la misma arquitectura devolvería el vector u= (6,6,9,9,9,9), que son los valores máximos para cada posición del filtro. De la misma manera que podemos ver una neurona como una función no solo de los valores de entrada, sino también de los pesos; f(x, w, b) = σ n X i=1 wTx+b podemos ver una red neuronal como una función de la misma manera, que es a su vez composición de lfunciones (una por cada capa), introduciendo la siguiente notación: y=fΘ(x) = f(l) θl◦f(l−1) θl−1◦ · · · ◦ f(2) θ2◦f(1) θ1(x). 35 4.2. EL MODELO DE APRENDIZAJE DE REDES NEURONALES 36 Figura 4.5: Una capa de convolución que recibe un vector de longitud n= 8, con tamaño de kernel k= 3 y step s= 1. Se pueden observar todas las posibles posiciones del kernel, y los pesos w1, w2, w3de las neuronas que cada posición va definiendo. Los pesos pueden escogerse tanto distintos como iguales para cada neurona (Fuente). Donde cada θies el conjunto de parámetros de la capa i(vectores de pesos y sesgos de cada neurona de la capa), y Θes el conjunto de todos los θ1, ..., θl. De esta manera, conseguimos una notación compacta que casa con las generalidades sobre aprendizaje supervisado que vimos en la sección anterior. Por lo tanto, estamos preparados para aplicar el algoritmo de descenso del gradiente en el caso particular de redes neuronales. 4.2.2. Descenso del gradiente en redes neuronales y propagación hacia atrás Indaguemos ahora en la optimización de redes neuronales, en concreto, en la aplicación del descenso del gradiente a las mismas. Esto se consigue mediante el algoritmo de propagación hacia atrás, el cual explicamos en esta subsección. Para formular el descenso del gradiente, separaremos los parámetros de toda la red neuronal Θen pesos de todas las neuronas (wk) por un lado, y en sesgos (bl) por otro. De esta manera, actualizaríamos los parámetros de una red neuronal en cada paso del descenso del gradiente como sigue: 36 4.2. EL MODELO DE APRENDIZAJE DE REDES NEURONALES 37 wk→w′ k=wk−µ∂L ∂wk , bl→b′ l=bl−µ∂L ∂bl , ya que el gradiente en este caso sería ∇L = ( ∂L ∂w1 , ..., ∂L ∂wm ,∂L ∂b1 , ..., ∂L ∂bn ) si tenemos mpesos y nsesgos en total. Pero, ¿cómo calculamos el gradiente ∇L? Es aquí donde entra en juego el algoritmo de propagación hacia atrás. Lo primero que tenemos que tener en cuenta es que el algoritmo de propagación hacia atrás calcula el error asociado a cada muestra de entrenamiento, lo que permite calcular el gradiente ∇L, ya que ∇L =Px∈D∇Lxpero, para no sobrecargar la notación, en lo que sigue escribiremos Lpara referirnos al error asociado únicamente a una muestra del conjunto de entrenamiento. Por otro lado, el algoritmo será mas fácil de formular y entender si utilizamos una notación que concrete la capa y la neurona en la que se encuentran los pesos y los sesgos de los que hablemos en todo momento, que explicamos a continuación. 1. wl jk denota el peso asociado a la entrada en la neurona jde la capa l, que proviene de la neurona ken la capa l−1. 2. bl jdenota el sesgo de la neurona jde la capa l. 3. Escribimos el output de la neurona jde la capa l(antes de la aplicación de la función de activación) como zl j. 4. Finalmente, usamos al jpara referirnos a la activación de la neurona jde la capa l. Con esta notación, la relación entre la activación de una neurona en la capa ly los inputs que provienen de la capa anterior se expresa como: al j=σzl jσ X k wl jkal−1 k+bl j!,(4.2) donde la suma es sobre cada neurona kde la capa l−1. Podemos escribir esta expresión de manera matricial, para que sea más compacta. Para ello, definimos una matriz de pesos para cada capa l,wl, cuyas entradas no son más que los pesos de las neuronas de la capa, de manera que el elemento en la posición (j, k) sea wl jk. Es decir, que cada fila de la matriz corresponde a los pesos de cada 37 4.2. EL MODELO DE APRENDIZAJE DE REDES NEURONALES 38 neurona de la capa. De manera similar, para cada capa l, denotamos el vector de sesgos como bl, y el vector cuyas componentes son las activaciones al jcomo al. Así, reescribimos la Ecuación 4.2 como: al=σzl=σwlal−1+bl,(4.3) donde la función de activación σse aplica componente a componente. De esta manera, evitamos la notación de la Ecuación 4.2, más confusa debido a los subíndices. El algoritmo de propagación hacia atrás consiste en operaciones comunes de álgebra lineal en su mayoría, como la suma componente a componente, o el producto de matrices. Sin embargo, necesitamos conocer la siguiente operación, no tan común. Definición 4.2.5. Sean sytvectores de un cierto Rn. Definimos el producto de Hadamard (también conocido como producto de Schur o producto componente a componente) como (s⊙t)i=siti, i = 1, ..., n. Lo que queremos entender es cómo influye en la función coste cambiar cada peso y sesgo de la red. Pero al cambiar el peso o el sesgo de la neurona jen la capa l, también estamos cambiando el output de la neurona, zl j. Este cambio, ∆zl j, se propaga a lo largo de las capas siguientes, hasta que provoca un cambio en la función coste: ∂L ∂zl j ∆zl j. Por lo tanto, cuando ∂L ∂zl j es muy pequeño, el cambio producido en la función coste es muy bajo cuando realizamos un cambio ∆zl j. Intuitivamente, esto quiere decir que es difícil hacer la neurona más eficiente de lo que ya es mediante cambios en los parámetros, lo que significa que, en cierto sentido, ∂L ∂zl j mide el error cometido por la neurona respecto a su configuración óptima. Es por ello que en el algoritmo de propagación hacia atrás definimos el "error" de la neurona jde la capa lcomo δl j=∂L ∂zl j . Como viene siendo habitual con nuestra notación, usaremos δlpara el vector de errores de la capa l. El algoritmo de propagación hacia atrás nos permitirá calcular estos errores, y relacionarlos con las derivadas parciales de la función coste respecto de los parámetros, que son las que realmente nos interesan. Damos a continuación el resultado clave para el funcionamiento del algoritmo. 38 4.2. EL MODELO DE APRENDIZAJE DE REDES NEURONALES 39 Teorema 4.2.6 (Ecuaciones fundamentales del algoritmo de propagación hacia atrás, [18]).Sea Lla capa de salida de una red neuronal, lcualquiera de sus capas ocultas, jykneuronas de las capas lyl−1respectivamente. Se cumplen las siguientes igualdades: 1. Propagación hacia atrás de errores. δL=∇aLL ⊙ σ′(zL)(4.4) δl= ((wl+1)Tδl+1)⊙σ′(zl)(4.5) 2. Derivadas parciales respecto de cualquier parámetro de la red. ∂L ∂bl=δl(4.6) ∂L ∂wl jk =al−1 kδl j.(4.7) Donde ∇aLLes un vector cuyas componentes son las derivadas parciales de L respecto de cada una de las activaciones de la capa L,aL i, y donde (wl+1)Tes la matriz de pesos de la capa l+ 1 traspuesta. Con estas ecuaciones, podemos calcular el gradiente de L, ya que primero, podemos calcular las activaciones de la última capa, y en la práctica podremos calcular ∇aLLya que Lse trata de una expresión sencilla en función de aL, que es el output de toda la red neuronal. Por ejemplo, si Les la función de error cuadrático medio, tenemos ∇aLL=2(aL−y) N. Con esto y con la Ecuación 4.4, obtenemos los errores δLque, gracias a la Ecuación 4.5, nos permite calcular los errores de la capa anterior, que podemos volver a utilizar para calcular los de la siguiente, así hasta obtener todos los errores de todas las neuronas de la red. Finalmente, conociendo estos valores, podemos calcular todas las parciales gracias a las Ecuaciones 4.6 y 4.7. Demostración. Demostremos cada una de las igualdades del Teorema 4.2.6: Ecuación 4.4: Por definición, δL j=∂L ∂zL j y, si aplicamos la regla de la cadena para varias variables para expresarlo en función de las activaciones de cada neurona kde la capa L, obtenemos δL j=X k ∂L ∂aL k ∂aL k ∂zL j . Pero lógicamente, la activación de la neurona k,aL k=σ(zL k), depende solo del output zL k, por lo que ∂aL k ∂zL j = 0 si j=k. Por lo tanto, la ecuación 39 5.2. GRAPH NEURAL NETWORK BÁSICA 46 a b c d Figura 5.1: Grafo G= (V,E) za zb, zdm0 N(a) h1 a[1] h1 b, h1 dm1 N(a) h2 a=xa Figura 5.2: GNN básica de 2capas sobre el grafo de la Figura 5.1. En esta GNN, tendríamos W1 self, W1 neigh ∈R4×3,b1∈R4, y W2 self, W2 neigh ∈R1×4,b2∈R. El vector h1 a∈R4, cuyas coordenadas provienen de cada una de las 4 neuronas de la primera capa, h1 a[i] = σW1 self[i]za+W1 neigh[i]m0 N(a)+b1 i, es el input de la última neurona, que devuelve el output h2 a=σW2 selfh1 a+Wneighm1 N(a)+b2 1. Podemos observar que, aunque zatiene tres features, la primera capa devuelve un vector oculto h1 ade cuatro coordenadas (al igual que puede ocurrir con las capas ocultas de redes neuronales). La elección del número de neuronas (cuatro en este caso) no tiene relación con la estructura del grafo, y es por ello que es un hiperparámetro del modelo. En este caso, la capa final tiene una neurona, por lo que esta red podría estar diseñada para, por ejemplo, un problema de clasificación binario, donde el embedding xasería la probabilidad de que el nodo pertenezca a la clase positiva. En la figura también se observa con claridad cómo una capa de la GNN coincide con una capa usual de red neuronal, con la salvedad de que realizamos las operaciones m0 N(a)ym1 N(a). Sin embargo, esto último no afecta a la hora de aplicar el algoritmo de propagación hacia atrás, ya que lo que importa es que se cumplan las ecuaciones (que ocurre siempre que la información fluya hacia adelante) y que podamos calcular las activaciones de cada capa. En contraste con lo anterior, una GNN genérica de dos capas de acuerdo con la Ecuación 5.3, vendría representada por la Figura 5.3, donde ΘiyΦi, i = 1,2 46 5.3. NORMALIZACIÓN DEL OPERADOR AGGREGATE: GRAPH CONVOLUTIONAL NETWORK 47 son los parámetros de los que dependen las funciones/redes neuronales arbitrarias update yaggregate. za zb, zdaggregate1 θ1 update1 ϕ1h1 a h1 b, h1 daggregate1 θ2 update2 ϕ2h2 a=xa Figura 5.3: GNN genérica sobre el grafo de la figura 5.1 Una manera alternativa de plantear una GNN es omitir la función update, y en su lugar, añadir bucles en todos los nodos del grafo. De esta manera, incluimos la información del nodo en la capa anterior en la función aggregate junto con la de sus vecinos, y ahorramos la definición de update. hk u=aggregate {h(k−1) v,∀v∈ N(u)∪ {u}}.(5.7) En el caso de una GNN básica, esto equivale a que las matrices Wneigh y Wself sean iguales, dando lugar a la siguiente ecuación matricial hk u=σ(A+I)H(k−1)W(k).(5.8) 5.3. Normalización del operador aggregate: Graph Convolutional Network Un problema que surge de utilizar el operador aggregate de una GNN básica (i.e., simplemente sumar) es que puede crear grandes diferencias en las magnitudes de las features si un nodo tiene un grado bastante alto. En efecto, supongamos que un nodo u∈ V tiene muchos más vecinos que otro nodo u′∈ V (por ejemplo, δ(u)>100δ(u′)). Entonces, es esperable que || Pv∈N(u)hk v|| >> || Pv′∈N(u′)hk v′||, lo cual daría lugar a problemas en el aprendizaje y la optimización del modelo. Para solucionar este problema, agregamos un elemento de normalización en aggregate; en primera instancia, sería lógico pensar en mk N(u)=Pv∈N(u)hk v |N(u)|.(5.9) 47 5.4. DEEP GRAPH CONVOLUTIONAL NETWORK 48 Otra alternativa es la llamada normalización simétrica, que también tiene en cuenta el grado de los vecinos de ua la hora de normalizar, con la idea de que un vecino que esté conectado con muchos otros nodos es poco indicativo de las propiedades o la estructura en la que se encuentra u. mk N(u)=X v∈N(u) hk v p|N(u)||N(v)|(5.10) Basada en esta idea de normalización, se definen las graph convolutional networks, propuestas por primera vez por Kipf y Welling en 2016 [15], que también utilizan la idea de añadir bucles de la Ecuación 5.7. Nosotros utilizaremos graph convolutional networks con la idea de normalización de la Ecuación 5.9 (Ecuaciones 5.11 y 5.12 en forma matricial), aunque también son comunes las que utilizan la normalización simétrica (Ecuaciones 5.13 y 5.14 en forma matricial): hk u=σ WkPv∈N(u)∪{u}h(k−1) v |N(u)|!,(5.11) Hk=σ˜ D−1˜ AH(k−1)Wk−1,(5.12) hk u=σ WkX v∈N(u)∪{u} hv p|N(u)||N(v)| ,(5.13) Hk=σ˜ D−1 2˜ A˜ D−1 2H(k−1)Wk−1,(5.14) donde ˜ A=A+Iy˜ Des la matriz diagonal de grados: ˜ Dii =Pj˜ Aij. 5.4. Deep Graph Convolutional Network Hasta ahora, hemos visto arquitecturas de GNN que sirven para actualizar la información de los nodos un determinado número de veces, y obtener un output 48 5.4. DEEP GRAPH CONVOLUTIONAL NETWORK 49 de la última capa, xu, que nos sirve para clasificar el nodo u. Sin embargo, ¿cómo modificamos una GNN para que clasifique el grafo entero que recibe como input? La Deep graph convolutional network (DGCN) [35], que explicamos a continuación, resuelve este tipo de problemas, y es la GNN utilizada en el método SEAL. Figura 5.4: Esquema de la arquitectura DGCNN. En el esquema, se refiere a las features obtenidas por cada capa como colors, en referencia al kernel Weisfeiler- Lehman, en el que está basada la arquitectura de la GCN [35]. La arquitectura de una DGCN consiste en lo siguiente: 1. Primero, aplicamos una GCN de lcapas sobre el grafo, de acuerdo con la Ecuación 5.12, para obtener embeddings hl u=xupara cada nodo u∈ V, pero en su lugar, almacenamos los vectores hk upara cada capa ky damos como output, para cada nodo u∈ V, los vectores hk u, k = 1, ..., l concatenados horizontalmente. Es decir, obtenemos una matriz H1:l= [H1, H2, ..., Hl]de manera que H1:l∈R|V|×Pl t=1 ct, donde ctes la dimensión de los vectores ht u. 2. A continuación, dotamos de un orden a los vértices del grafo, utilizando la matriz H1:ldel paso anterior. El método utilizado para ordenarlos es Sort- Pooling, que consiste en, primero, ordenar las filas de la matriz de acuerdo con Hl, comparando primero la última feature y escogiendo la mayor, y en caso de que sean iguales, comparando la penúltima, etc. En caso de que los hl usean iguales para dos vértices, se compara el vector de la capa anterior (l−1), etc. Por lo tanto, se trata de un orden lexicográfico, pero donde leemos las coordenadas de derecha a izquierda. Una vez ordenados, se escoge un número fijo de filas k, y se descartan las que sobren, o se completa la matriz con ceros en caso de que el subgrafo tenga menos de knodos. Esto se hace precisamente porque no todos los subgrafos recubridores tienen la misma cantidad de nodos, pero es necesario fijar una cantidad de filas para el siguiente paso. 3. Una vez que tenemos el output de SortPooling, una matriz Hsp como la anterior, pero esta vez en Rk×Pl t=1 ct, la reescribimos como un vector de longitud k(Pl t=1 ct)concatenando horizontalmente las filas, para utilizarlo 49 5.4. DEEP GRAPH CONVOLUTIONAL NETWORK 50 como input de una red neuronal, que clasificará el grafo. Esta red neuronal consta de, primero, una capa de convolución 1-D, de tamaño y step Pl t=1 ct. A continuación, se añaden algunas capas MaxPooling, y algunas capas de convolución 1-D, para acabar con varias capas completamente conexas, y una capa final con una activación SoftMax, con tantas neuronas como clases haya en las que clasificar el grafo. En nuestro caso tendríamos dos clases, correspondientes a predecir que (no) existe la arista en la que se centra el grafo recubridor. 50 Capítulo 6 El método SEAL En este capítulo explicaremos la metodología SEAL para predecir una arista entre dos nodos xeyen un grafo, la cual se basa en usar la información de los llamados subgrafos h-recubridores de xey(Definición 2.1.14). Esta metodología queda justificada por los resultados de la Subsección 6.1.3, donde veremos que estos subgrafos contienen casi toda la información necesaria sobre la existencia de la arista. Al principio del capítulo, en la Sección 6.1, exploraremos algunas de las heurísticas más importantes para la predicción de aristas entre dos nodos. Además, veremos que estas heurísticas se pueden encuadrar en una clase, las γ-heurísticas, las cuales tienen una propiedad clave, que es que pueden ser aproximadas con subgrafos h-recubridores de xey, donde el error de aproximación decrece de manera exponencial respecto de h. Esto nos indica que dichos subgrafos contienen la mayoría de la información necesaria para realizar una predicción de la arista, incluso si el valor de hes bajo, lo que justifica utilizarlos como datos de entrada al modelo que realizará la predicción. Además de la utilización de subgrafos recubridores, la metodología también se basa en la generación de features adicionales a las intrínsecas del problema (Secciones 6.2.2 y 6.2.3). Por una parte, se etiquetan los nodos del subgrafo en función de su rol estructural respecto de los nodos base xey(etiquetas de estructura), y por otra parte, se utilizan node embeddings, codificaciones de los nodos en vectores numéricos que almacenan su información estructural (como por ejemplo, node2vec). Los tres tipos de features se concatenan para obtener el vector de features de cada nodo; esto, junto con los subgrafos, es por lo que el método es conocido como SEAL;learning from Subgraphs, Embeddings, and Attributes for Link prediction. Finalmente, se escoge una arquitectura o modelo, diseñada para realizar una clasificación binaria de los subgrafos (existencia o no de la arista), el cual se entrena con la ayuda de un muestreo de datos de 51 6.1. HEURÍSTICAS DE PREDICCIÓN DE ARISTAS 52 entrenamiento negativos (parejas de nodos entre los que no existe arista en el grafo). 6.1. Heurísticas de predicción de aristas En esta sección, estudiaremos algunos índices heurísticos para medir la probabilidad de que exista una arista entre un par de nodos cualesquiera (x, y), en base a la estructura del grafo. Veremos una serie de heurísticas que se pueden englobar en una clase, las γ-heurísticas. Probaremos que cualquier γ-heurística se aproxima bien con subgrafos h-recubridores, cosa que justificará el uso de los mismos como datos de entrenamiento para el modelo SEAL. En lo que sigue, trabajamos con un grafo simple G= (V,E), y x, y serán nodos del grafo. Alternativamente, podremos referirnos a los nodos del grafo mediante el conjunto ordenado {v1, ..., v|V|}. Una heurística H(x, y)es un cálculo en función de los nodos x, y ∈ V e información estructural del grafo, que da una estimación de la probabilidad de que exista la arista entre xey. Definimos el orden de una heurística como el h mínimo de manera que el subgrafo h-recubridor contenga toda la información necesaria para el cálculo exacto de la heurística. Sin embargo, también existen heurísticas que necesitan información del grafo entero para ser calculadas de manera exacta. En ese caso, decimos que son heurísticas de orden alto. 6.1.1. Heurísticas de orden bajo Todas las heurísticas de orden bajo que veremos son de primer o segundo orden, y siguen principios muy básicos. Definición 6.1.1. Definimos la heurística de vecinos comunes como CN(x, y) = |N(x)∩ N(y)|.(6.1) Definición 6.1.2. El índice de Jaccard, que sirve en general para teoría de conjuntos, se define como Jac(x, y) = |N(x)∩ N(y)| |N(x)∪ N(y)|.(6.2) Definición 6.1.3. El índice de conexión preferencial se define como PA(x, y) = |N (x)||N (y)|.(6.3) Como podemos ver, se tratan de heurísticas de primer orden muy simples, que siguen el principio básico de que mientras más vecinos tengan en común 52 6.1. HEURÍSTICAS DE PREDICCIÓN DE ARISTAS 53 los nodos xey, más posibilidades hay de que exista la arista entre ellos. Claro está que, tanto vecinos comunes como el índice de conexión preferencial no dan un valor de probabilidad como resultado (cosa que sí hace el de Jaccard), pero siguen siendo índices indicadores de la probabilidad de la arista. Veamos ahora dos heurísticas de segundo orden, similares y algo más complejas que las tres primeras que hemos visto. Definición 6.1.4. Definimos el índice de Adamic-Adar como AA(x, y) = X z∈N(x)∩N (y) 1 log |N(z)|.(6.4) Definición 6.1.5. La heurística de resource allocation (asignación de recursos) se define como RA(x, y) = X z∈N(x)∩N (y) 1 |N(z)|(6.5) En ambos casos, se mide cómo de "exclusivos" son los vecinos de xy de y, es decir, un nodo que tenga muchos más vecinos además de xeyes menos significativo del parecido entre ellos que un nodo que los conecte exclusivamente a ellos. En el caso de Adamic-Adar, se calcula de manera que los nodos menos significativos tengan un aporte mayor al índice que en resource allocation. Ambas heurísticas son de segundo orden, ya que no se necesita información más allá de los segundos vecinos de xey. 6.1.2. Heurísticas de orden alto Las heurísticas de orden alto necesitan información de todo el grafo para ser calculadas de manera exacta. Por lo que, si uno piensa en trabajar con subgrafos h-recubridores, puede parecer necesario un hbastante grande para tener una buena aproximación de las mismas. En esta sección, definiremos algunas heurísticas de orden alto, demostraremos que pertenecen a la clase de γ-heurísticas, y probaremos que no es necesario un hdemasiado grande para aproximarlas bien. Definición 6.1.6. Dado un grafo G= (V,E)y un par de nodos x, y ∈ V, definimos el índice de Katz [13] como Katzx,y = ∞ X l=1 βl[Al]x,y,(6.6) donde [Al]x,y es el número de caminos de longitud lentre xey(Teorema 2.1.12), yβ∈(0,1) es un parámetro con el que damos más peso a los caminos más cortos. 53 6.1. HEURÍSTICAS DE PREDICCIÓN DE ARISTAS 54 El índice de Katz estima que es más probable que exista una arista entre dos nodos si hay muchos caminos entre esos nodos, dando especial importancia a los de longitud pequeña. La siguiente heurística calcula la distribución estacionaria de un camino aleatorio comenzando en el nodo x, que se mueve cada vez a un vecino aleatorio con probabilidad α, o regresa a xcon probabilidad 1−α(esto es un ejemplo de cadena de Markov, de la que proviene la distribución estacionaria [22]). Sea πx el vector de probabilidades de la distribución estacionaria, donde [πx]idenota la probabilidad de que el camino se encuentre en el nodo x(coordenada i). Si el camino no tuviese la opción de volver al nodo x, (α= 1) la matriz de transición sería P, donde Pi,j =1 |N(vj)|si (vi, vj)∈ E yPi,j = 0 en caso contrario. Entonces, la distribución estacionaria satisface πx=αPπx+ (1 −α)ei, donde eies el vector canónico (1en la coordenada iy0en el resto). Definición 6.1.7. Definimos entonces la heurística PageRank como PageRank(x, y)=[πx]y(6.7) Veamos ahora SimRank, una heurística que se define de manera recursiva, y que se basa en la idea de que dos nodos son parecidos si sus entornos son parecidos. Definición 6.1.8. La heurística SimRank se define de manera recursiva como s(x, y)=1si x=y, y en caso contrario, como γPa∈N(x)Pb∈N (y)s(a, b) |N(x)||N(y)|.(6.8) 6.1.3. γ-heurísticas ¿Cómo se define entonces la clase de γ-heurísticas? Definición 6.1.9. Una γ-heurística sobre x, y ∈ V es de la forma H(x, y) = η ∞ X l=1 γlf(x, y, l),(6.9) donde γ∈(0,1),ηes, o bien una constante positiva, o bien una función positiva de γacotada superiormente por una constante, y fes una función no negativa definida sobre el grafo. 54 6.1. HEURÍSTICAS DE PREDICCIÓN DE ARISTAS 55 La propiedad clave de las γ-heurísticas es que, bajo ciertas condiciones, pueden ser aproximadas por un subgrafo h-recubridor, de manera que el error decrece, al menos, exponencialmente respecto de h. Teorema 6.1.10 ([34]).Dada una γ-heurística H(x, y) = ηP∞ l=1 γlf(x, y, l), si f(x, y, l)satisface las siguientes condiciones: 1. f(x, y, l)≤λl, donde λ < 1 γ. 2. f(x, y, l)se puede calcular con información de Gh x,y para l= 1,2, ..., g(h), donde g(h) = ah +bcon a, b ∈Nya > 0, entonces H(x, y)puede aproximarse con información de Gh x,y de manera que el error decrece al menos exponencialmente respecto de h. Demostración. Podemos aproximar la γ-heurística sumando sobre sus primeros g(h)términos, que nos permiten el cálculo de f(x, y, l)gracias a la condición 2. ˜ H(x, y) = η g(h) X l=1 γlf(x, y, l).(6.10) El error de aproximación puede ser acotado de la siguiente manera: |H(x, y)−˜ H(x, y)|=η ∞ P l=g(h)+1 γlf(x, y, l) ≤η ∞ P l=ah+b+1 γlλl=η(γλ)ah+b+1(1 −γλ)−1. En el último paso, entra en juego la condición λ < 1 γpara poder realizar la suma de la serie geométrica de razón γλ < 1. Este resultado sugiere que casi toda la información relevante para la existencia (o no) de la arista se encuentra en un subgrafo h-recubridor, sin necesidad de que hsea demasiado grande, y esto constituye el hecho principal en el que se basa la metodología SEAL, como veremos en la Subsección 6.2.4. Ahora, veamos que las heurísticas de orden alto que hemos definido son γ-heurísticas, y que cumplen las condiciones del Teorema 6.1.10. Lema 6.1.11 ([34]).Cualquier camino entre xeyde longitud l≤2h+ 1 está contenido en Gh x,y. 55 6.3. ELECCIÓN DEL MODELO Y EVALUACIÓN DEL RENDIMIENTO DE SEAL 62 Figura 6.1: Esquema de la metodología SEAL [34]. Se visualizan dos posibles inputs; las parejas de nodos (A, B)(entre los que existe arista) y (D, C)(entre los que no existe arista). Podemos observar que, para ambos casos, se procede extrayendo el subgrafo recubridor, construyendo su matriz de información y utilizando un clasificador de grafos (p.ej., DGCNN) para obtener la predicción. Para la obtención de esos resultados, se tomaron el 10 % de las aristas del grafo como datos positivos del conjunto de test, y se muestrea la misma cantidad de aristas no existentes (pares de nodos entre los cuales no existe arista) como datos de test negativos. Se realiza el mismo procedimiento para obtener un 5% de las aristas como datos del conjunto de validación. El 90 % de aristas restantes se utilizan como datos de entrenamiento positivos y, análogamente, se muestrea la misma cantidad de aristas negativas para usarse como datos de entrenamiento negativos. Como parámetros concretos del modelo DGCNN tenemos: Cuatro capas de convolución, las tres primeras con outputs de dimensión 32, con una capa final con output de dimensión 1. Para la capa SortPooling se escoge el parámetro kde manera que el 60% de los grafos tengan menos de knodos. Es decir, que solo un 40 % de los subgrafos recubridores ven truncado su número de nodos hasta k, mientras que el resto, o bien ya tenía exactamente knodos, o ven su matriz completada con ceros. Los outputs son vectores (de dimensión k(32·4+1)). A continuación se encuentra la red neuronal final. La arquitectura de la misma consta de: Primero, una capa de convolución 1-D, con tamaño de kernel ystep 32 · 4+1, y con 16 features de salida, es decir, que hay 16 conjuntos de pesos distintos en esta capa, que dan lugar a 16 outputs distintos para cada posición del kernel. Por lo tanto, el output de esta capa es una matriz de dimensiones 16 ×k. A continuación, una capa MaxPooling de tamaño de kernel ystep 2 para cada una de las 16 features. 62 6.3. ELECCIÓN DEL MODELO Y EVALUACIÓN DEL RENDIMIENTO DE SEAL 63 La matriz de dimensiones 16×k 2que obtenemos, la utilizamos a continuación como input de otra capa de convolución 1-D, con tamaño de kernel de 5 y step 1, con 32 features de salida. Esto nos deja con una matriz de dimensiones 32 ×(k 2−4). Finalmente, aplicamos una capa lineal que toma, precisamente 32·(k 2−4) valores de entrada, y devuelve 128, a los que aplicamos otra capa lineal, que lo transforma en solo 1 valor, al que finalmente aplicamos una función sigmoide para obtener la probabilidad que buscábamos. El entrenamiento del modelo se realiza a lo largo de 50 épocas, y se escoge como modelo final el que haya resultado en un valor más bajo de la métrica AUC en el conjunto de validación. Los distintos datasets sobre los que se evalúa SEAL son USAir, NS, PB, Yeast, C.ele, Power, Router y E.Coli (consultar Apéndice C de [34] para más información sobre los mismos). Es importante determinar el valor h, que establece el tamaño de los subgrafos h-recubridores; se escoge h= 1 oh= 2, dependiendo del dataset, pero no se escogen valores iguales o mayores que 3, ya que, por un lado, en [34] se comprueba experimentalmente que el rendimiento no aumenta con h > 3y, por otro lado, debido a que h= 3 puede acabar generando subgrafos demasiado grandes, sobre todo si un nodo central/muy conectado (hub node) se incluye en el grafo. En definitiva, el valor se selecciona de {1,2}en base al siguiente criterio: Si la heurística de segundo orden Adamic-Adar (AA, Definición 6.1.4) consigue un rendimiento superior a la heurística de primer orden de vecinos comunes (Definición 6.1.1), entonces se escoge h= 2; de lo contrario, se utiliza h= 1. Primero, se compara el rendimiento de SEAL con las heurísticas que ya hemos visto, además de con otros dos métodos de aprendizaje automático que también aprenden de subgrafos: el kernel de Weisfeiler-Lehman (WLK, [25]), yWLNM [33] (Figura 6.2). Se incluye también Ensemble (ENS), que consiste en entrenar un clasificador de regresión logística sobre las ocho heurísticas. Dado que los métodos heurísticos solo obtienen información estructural de los subgrafos, no se han utilizado ni features explícitas ni node embeddings con SEAL, para que aprenda precisamente sólo de la estructura del subgrafo. Lo primero que podemos observar es que los métodos que utilizan subgrafos recubridores (WLK,WLNM ySEAL) tienen, en general, mejor rendimiento que los métodos heurísticos. Entre ellas, SEAL es la que presenta mejor rendimien- to, lo que demuestra la mejora que supone el uso de GNN’s respecto de los métodos utilizados por WLNM yWLK (graph kernels y redes neuronales completamente conexas). Por otra parte, podemos observar que, sobre los datasets Power yRouter, las heurísticas presentan un rendimiento similar a adivinar al azar (i.e., AUC ≃0.5, ver Figura 3.3), mientras que los métodos de aprendizaje automático los mejoran muchísimo y obtienen un rendimiento muy bueno. Esto sugiere que, mediante el aprendizaje automático, se pueden incluso descubrir nuevas heurísticas para grafos sobre los cuales las heurísticas predefinidas no funcionan. 63 6.3. ELECCIÓN DEL MODELO Y EVALUACIÓN DEL RENDIMIENTO DE SEAL 64 Figura 6.2: Rendimiento (AUC) de diversas heurísticas en comparación con SEAL en distintos datasets ([34]). A continuación, se compara SEAL con otros métodos de aprendizaje automático; matrix factorization (MF), stochastic block model (SBM) [1], node2vec (N2V) [7], LINE [27], spectral clustering (SPC) y variational graph auto-encoder (VGAE) [14]. Estos métodos consisten en obtener node embeddings, que luego son utilizados como datos de entrada de un clasificador binario que predice la existencia o no de una arista entre nodos. Los resultados se muestran en la Figura 6.3. Podemos observar que SEAL supone una mejora notable en general respecto al resto de métodos. En estos datasets en concreto, no disponemos de features explícitas, lo que llama la atención ya que SEAL (que, recordemos, utiliza los embeddings de node2vec como parte del input) mejora mucho el rendimiento de sólo node2vec, gracias al aprendizaje obtenido de los subgrafos y de las etiquetas de estructura. Una observación interesante es que, en ciertos casos, SEAL sin uso de node embeddings (6.2) mejora el rendimiento de SEAL cuando sí se hace uso de ellos, lo que indica que no siempre supone una mejora de rendimiento usarlos como parte del input. Figura 6.3: Rendimiento (AUC) de diversos métodos de aprendizaje automático, en comparación con el método SEAL sobre distintos datasets [34]. Como conclusión, hemos explorado algo de teoría sobre heurísticas para predicción de aristas y hemos explicado la metodología SEAL para predicción de aristas mediante Graph Neural Networks que, basada en el Teorema 6.1.10, utiliza como elementos clave subgrafos recubridores, además de features explícitas, node embeddings y etiquetas de estructura, junto con una arquitectura de GNN para clasificación de grafos. Posteriormente, hemos explicado los experimentos llevados a cabo en [34] utilizando esta metodología, junto con el clasificador de grafos DGCNN, y hemos explorado los resultados, concluyendo que SEAL supone una mejora respecto de otros muchos métodos de predicción de aristas del momento, justificando así su posterior uso en este trabajo. 64 Capítulo 7 Método GAug-M para data augmentation en grafos. El campo de estudio de data augmentation tiene como objetivo aumentar o mejorar los datos de entrenamiento disponibles en un problema de aprendizaje supervisado, de manera que el modelo a entrenar mejore su rendimiento. En otros ámbitos del aprendizaje automático, como puede ser reconocimiento de imágenes, se emplean técnicas como voltear o invertir las imágenes para generar nuevos datos. En problemas de clasificación tradicionales (los datos no son más que vectores de features) se emplean técnicas de muestreo (oversampling oundersampling) y métodos de interpolación. En problemas de NLP (Natural Language Processing), un ejemplo de modificación de los textos consiste en sustituir ciertas palabras por sinónimos. En el contexto de datos estructurados en grafos, se trata de un ámbito menos estudiado, y que requiere de estrategias distintas a las mencionadas anteriormente, ya que estamos ante un tipo de estructura de datos completamente distinto. En realidad, no son más que conjuntos de vértices y aristas, para los que modificar la representación gráfica no modifica la información que codifican, lo que limita mucho las técnicas para crear nuevos datos de entrenamiento. Por ejemplo, las técnicas de voletado de imágenes de Computer Vision no nos servirían. Por lo tanto, es necesario desarrollar métodos más específicos para grafos [4]. En este capítulo introducimos GAug-M (Graph Augmentation Modified1, [37]), un método para modificar un grafo que, mediante un modelo de predicción de aristas, agrega al grafo las aristas más probables y elimina las aristas menos probables, para mejorar el rendimiento de un modelo de clasificación de nodos. 1En contraposición a Graph Augmentation Original, o GAug-O, también desarrollado en [37] 65 7.1. POSIBLES ESTRATEGIAS PARA DATA AUGMENTATION EN GRAFOS 66 7.1. Posibles estrategias para data augmentation en grafos Para abordar el problema de data augmentation en datos estructurados en forma de grafos, las ideas inmediatas pasan por añadir o eliminar nodos o aristas. En el caso de los nodos, añadir nodos presenta un problema a la hora de decidir la conectividad que el nuevo nodo tendrá con el resto de nodos ya existentes, así como el problema de dotarlo de un vector de features, mientras que eliminando un nodo solo se consigue reducir la información de entrenamiento. Por lo tanto, la estrategia que a priori parece más viable es añadir o eliminar aristas. El problema pasa a ser entonces, ¿qué método empleamos para añadir o eliminar aristas, de manera que la información del grafo se enriquezca y mejore el rendimiento de un modelo de clasificación de nodos? Existen varios métodos que han sido propuestos recientemente para abordar este problema. DropEdge [21] elimina aleatoriamente una fracción de las aristas del grafo antes de cada época de entrenamiento, para evitar el overfitting de una manera parecida a como hace DropOut [26] para redes neuronales. Entre otras maneras más complejas de abordar el problema, más robustas en cuando a eliminación de ruido (datos o información no relevantes a la hora de la predicción) se encuentran AdaEdge [2], que añade (elimina) aristas de manera iterativa entre nodos para los que se ha predicho la misma (distinta) clase con alta confianza, o BGCN [36], que crea múltiples grafos tras eliminar ruido mediante un método estocástico que utiliza predicciones de una GCN. Sin embargo, en este trabajo, nos centraremos en GAug-M, que explicamos en la siguiente sección. 7.2. GAug-M 7.2.1. Motivación teórica Un grafo sirve para representar el proceso o situación real de interés sobre la que queremos trabajar, pero no tiene porqué coincidir exactamente con el proceso o situación que pretende modelar (relaciones reales vs. relaciones observadas). Esto es debido a que muchos grafos que modelan situaciones reales son susceptibles al ruido, provocado por varias razones, como pueden ser: Spammers que contaminan el espacio de observaciones. En el preprocesado de los grafos, se pueden añadir o eliminar bucles, eliminar nodos aislados o aristas en base a sus pesos. 66 7.2. GAUG-M 67 Errores humanos. Por ejemplo, en un grafo que modele artículos de investigación como nodos, y aristas en función de cómo se citen unos a otros (p.ej.: los datasets Cora oCiteSeer) un paper puede omitir (incluir) la cita a un paper muy importante (irrelevante) por error, lo que provoca la ausencia (presencia) de una arista no deseada en el grafo. Todas estas situaciones producen una diferencia entre el grafo que observamos, y el "grafo ideal", que puede afectar al rendimiento de nuestra tarea, que en este caso, sería clasificar los nodos en clases. En el mejor de los casos, mediante adición y eliminación de aristas, podríamos producir un grafo con conectividad ideal Gi, donde aristas esperadas (pero inexistentes) sean agregadas, y aristas insignificantes (pero existentes) sean eliminadas. En la Figura 7.1 se puede apreciar un ejemplo sobre el famoso grafo Zachary’s Karate Club, donde los nodos representan los miembros del club, y las aristas relacionan a miembros que socializan fuera del ámbito del club: añadir aristas entre nodos de la misma clase, y eliminar aristas entre nodos de distintos grupos provoca una mejora esperada en el rendimiento de la clasificación de nodos, siendo el mejor caso en el que añadimos/eliminamos todas las posibles aristas, cosa que lógicamente no podemos hacer, ya que requiere de conocer las clases de los nodos de antemano. El siguiente teorema muestra cómo, con conocimiento total de las clases de los nodos, la tarea de clasificación de nodos con una GNN pasa a ser trivial. Teorema 7.2.1 ([37]).Sea G= (V,E)un grafo simple con matriz de adyacencia Ay matriz de features de nodos X. Sea u∈ V,f:A, X, W →Huna capa de GNN con una función de agregación invariante por permutaciones sobre u∪ N(u), con matriz de parámetros W, y sea H=f(A, X, W)el embedding resultante. Supongamos que Gcontiene kcomponentes conexas completas. Entonces, se tiene: 1. Para dos nodos i, j ∈ V cualesquiera que estén en una misma componente conexa, se tiene Hi=Hj. 2. Para dos nodos i, j ∈ V cualesquiera que estén en distintas componentes conexas, Sa, Sb∈ V, se tiene Hi=Hjcuando Wno es una matriz de ceros y Pv∈SaXv=εPu∈SbXu,∀ε∈R. Esto nos motiva a buscar una manera de añadir y eliminar aristas de manera que se de importancia a las aristas intra-clase, y se eliminen aristas entre clases, asumiendo que es más probable que existan las primeras que las últimas (homofilia). 7.2.2. Definición de GAug-M El método GAug-M sigue los siguientes pasos: 67 7.2. GAUG-M 68 Figura 7.1: Rendimiento de una GCN, medido con el valor F1, en el grafo Zachary’s Karate Club, y en verisones modificadas del mismo. a) Grafo original, b) Aristas agregadas y eliminadas aleatoriamente, c) Aristas agregadas y eliminadas usando GAug-M, d) Modificaciones realizadas conociendo las clases de los nodos. Fuente: [37] 1. Se utiliza un modelo de predicción de aristas para obtener la matriz M de probabilidades de existencia de todas las posibles aristas del grafo G= (V,E). 2. Utilizando la matriz M,GAug-M añade, de manera determinista, las i|E| aristas no existentes con mayor probabilidad, y elimina las j|E| aristas ya existentes con menor probabilidad, para generar un nuevo grafo modificado Gm, donde i, j ∈[0,1] (i.e., porcentaje de aristas a añadir/eliminar). 3. A continuación, procedemos a entrenar y evaluar el modelo de clasificación de nodos, tanto en el grafo Gcomo en el grafo Gi, y se compara el rendimiento en ambos casos. En [37], se utiliza VGAE (Variational Graph Auto-Encoder, [14]) como modelo predictor de aristas, y como modelos de clasificación de nodos se emplean GCN [15], GSAGE [9], GAT [29] y JK-Net [30]. Como comprobación experimental de que este método consigue el objetivo de promover las aristas entre nodos de la misma clase y desincentivar las aristas entre nodos de clases distintas, se ha aplicado GAug-M al grafo Cora utilizando probabilidades obtenidas por Graph Auto Encoder [37]. En la Figura 7.2 podemos ver el número total de aristas, tanto intra-clase como entre clases, en función del porcentaje de aristas agregadas y eliminadas (iyj), en comparación con un predictor de probabilidades aleatorio, además de la métrica micro-F1 de un clasificador de nodos sobre el grafo evaluada sobre el conjunto de test. Podemos observar que al añadir aristas, GAug-M provoca un aumento mayor de las aristas intra-clase que entre clases, además de mejorar el rendimiento del clasificador consistentemente, mientras que añadir aristas de manera aleatoria no tiene un efecto claro sobre aristas intra-clase, sino que aumenta las aristas entre clases (debido a que, de todas las aristas posibles, existen más entre clases que intra-clase), además de empeorar el rendimiento del modelo. Se produce un efecto análogo al eliminar aristas aleatoriamente, solo que esta vez se eliminan 68 7.2. GAUG-M 69 sobre todo aristas intra-clase (debido a que es el tipo más común entre las aristas existentes), mientras que eliminar aristas mediante GAug-M tiene un efecto de mejora de rendimiento con porcentajes entre el 15 % y25 %, aunque lo empeora para porcentajes superiores, lo cual tiene sentido ya que estaríamos eliminando demasiadas aristas, y por lo tanto demasiada información del grafo, en lugar de solamente eliminar ruido. Figura 7.2: Efecto de GAug-M sobre las aristas del grafo Cora, y el rendimiento de un clasificador de nodos. Fuente: [37] 7.2.3. Evaluación y rendimiento de GAug-M En esta subsección nos centramos en presentar los resultados de los experimentos de evaluación de GAug-M realizados en [37], que también describimos, así como de qué se puede concluir del rendimiento obtenido en ellos. Para llevar a cabo la evaluación del rendimiento de GAug-M, primero se calcula la matriz de probabilidades de todas las posibles aristas sobre cada uno de los datasets (grafos) con los que evaluaremos los modelos, que son los siguientes Cora yCiteSeer, grafos que modelan conjuntos de artículos científicos, y las citas entre ellos. 69 7.2. GAUG-M 70 Figura 7.3: Características de los distintos datasets con los que evaluamos GAug-M. Fuente: [37] Protein-Protein Interactions (PPI), grafo que modela proteínas y las interacciones entre ellas. Flickr yBlogCatalog, grafos que modelan redes sociales y las relaciones entre sus usuarios Air-USA, grafo que modela el tráfico aéreo entre aeropuertos de E.E.U.U. En la Figura 7.3 se pueden apreciar las características de cada dataset (número de nodos, de aristas, de features, etc.) A continuación, se entrenan y evalúan los modelos de clasificación de nodos mencionados anteriormente (GCN [15], GSAGE [9], GAT [29] y JK-Net [30]), sobre los grafos originales Gy sobre los grafos modificados por GAug-M,Gm, utilizando el predictor de aristas GAE [14]. Se realiza una separación de los nodos en distintos conjuntos, un 10 % para el conjunto de entrenamiento, un 20 % para el conjunto de validación y un 70 % para el conjunto de test. Comparamos el rendimiento de GAug-M con el de otros dos métodos de data augmentation similares: AdaEdge [2] y BGCN [36]. Evaluamos el rendimiento calculando la media y la desviación de la métrica micro-F1 a lo largo de 30 entrenamientos de los modelos (runs), al mismo tiempo que se usa la librería de Python Optuna para escoger los hiperparámetros de los modelos. En la Figura 7.4 podemos observar una tabla con los resultados obtenidos en [37] con el predictor de aristas GAE, organizados por modelo de clasificación de nodos, y luego método de data augmentation (o grafo original) en las filas, y por datasets en las columnas. GAug-M consigue mejoras de rendimiento en con todas las arquitecturas de GNN, más notablemente sobre GAT. Fijándonos en los datasets,GAug-M consigue mejorar el rendimiento en Cora yCiteSeer, pero la mejora es especialmente grande sobre los datasets Flickr,BlogCatalog yAir-USA. Es interesante que la mejora sea notable en los datasets que modelan redes sociales, ya que son en los que esperamos más ruido, procedente de spammers,bots u otras causas, lo que apoya a la intuición que comentábamos en la motivación teórica (Subsección 7.2.1). En cuanto a la comparación 70 7.2. GAUG-M 71 con el resto de métodos de data augmentation,GAug-M consigue, en general, un rendimiento superior a los otros dos métodos, en especial en los datasets BlogCatalog,Flickr, y Air-USA. Figura 7.4: Valores de la métrica micro-F1 (expresada en porcentaje) para distintas combinaciones de modelo-método de data augmentation, sobre cada uno de los distintos datasets. Fuente: [37] 71 78 Entre los posibles trabajos futuros que puedan complementar a estos experimentos, la posibilidad más inmediata es realizar el mismo esquema de experimentos (con SEAL como predictor de aristas), pero con el método de data augmentation GAug-O, introducido también en [37]. La idea es comprobar si, en ese caso, el uso de SEAL supone una mejora de rendimiento. Se trata de una variante de GAug-M en la que, en lugar de entrenar el modelo y evaluarlo sobre el grafo modificado Gm(Graph Augmentation-Modified), se modifica el grafo original Gpara obtener grafos Gi, i = 1, ..., N, sobre los que se realiza el entrenamiento, para luego evaluar el modelo sobre el grafo original (Graph Augmentation-Original). No hemos incluido este posible experimento en el trabajo debido a la complejidad del método GAug-O, que habría supuesto un aumento considerable de la longitud del trabajo. Otra idea es hacer que SEAL sea más eficiente a la hora de trabajar sobre grafos grandes y a la vez muy densos (que contienen un gran porcentaje de aristas respecto del número máximo posible), ya que extraer subgrafos hrecubridores para el entrenamiento puede dar lugar a fallos de tipo OOM (out of memory), debido a la cantidad de aristas que contienen, como ocurre por ejemplo en los datasets Flickr,BlogCatalog oPPI, donde surge este problema incluso con h= 1. Una idea que se propone en [34] es la de establecer una manera de muestrear cierta cantidad de nodos de los subgrafos recubridores, y considerar el subgrafo inducido por esos nodos, de manera que no se tengan en cuenta todas las aristas del subgrafo recubridor y aliviar un poco la carga de memoria. 78 Bibliografía [1] Edoardo M Airoldi, David M Blei, Stephen E Fienberg, and Eric P Xing. Mixed membership stochastic blockmodels. Journal of Machine Learning Research, 9(Sep):1981–2014, 2008. [2] Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. Proceedings of the AAAI Conference on Artificial Intelligence, 34, 2020. [3] Jesse Davis and Mark Goadrich. The relationship between precision-recall and roc curves. URL: https://www.biostat.wisc.edu/~page/rocpr. pdf. [4] Kaize Ding, Huan Liu, Zhe Xu, and Hanghang Tong. Data augmentation for deep graph learning: A survey, 2022. URL: https://arxiv.org/pdf/ 2202.08235.pdf. [5] Andrew Duncan. Powers of the adjacency matrix and the walk matrix, 2004. URL: https://www.um.edu.mt/library/oar/bitstream/ 123456789/24439/1/powers%20of%20the%20adjacency%20matrix.pdf. [6] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. ICML, 2017. [7] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. 2016. URL: https://arxiv.org/pdf/1607.00653.pdf. [8] William L. Hamilton. Graph representation learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 14(3):1–159, 2020. [9] William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. NeurIPS, 2017b, 2017. [10] N. Hartsfield and G. Ringel. Pearls in Graph Theory: A Comprehensive Introduction. Dover Books on Mathematics. Dover Publications, 2013. 79 BIBLIOGRAFÍA 80 [11] Glen Jeh and Jennifer Widom. Simrank: a measure of structural-context similarity. Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 538–543, 2002. [12] Glen Jeh and Jennifer Widom. Scaling personalized web search. Proceedings of the 12th international conference on World Wide Web, pages 271–279, 2003. [13] Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39–43, 1953. [14] Thomas N. Kipf and Max Welling. Variational graph auto-encoders. 2016. URL: https://dare.uva.nl/personal/search?metis.record.id= 547366. [15] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. Published as a conference paper at ICLR 2017, 2017. URL: https://openreview.net/pdf?id=SJU4ayYgl. [16] Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching networks for learning the similarity of graph structured objects. ICML, 2019. URL: https://proceedings.mlr.press/v97/li19d. html. [17] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning (Second edition). MIT Press, 2018. [18] Michael Nielsen. Neural Networks and Deep Learning. 2019. URL: http: //neuralnetworksanddeeplearning.com/index.html. [19] Santiago Pascual. Imagen capa de convolución 1-d. Enlace. [20] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701–710, 2014. [21] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. ICLR, 2019. [22] Sheldon Ross. Introduction to Probability Models, 11th edition. Elsevier, 2014. [23] David E. Rumelhart, Geoffrey E. Hinton, and Ronald J. Williams. Learning representations by back-propagating errors. Nature, 323:533–536, 1986. [24] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61–80, 2009. doi:10.1109/TNN.2008.2005605. 80 BIBLIOGRAFÍA 81 [25] Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(Sep):2539–2561, 2011. [26] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. JMLR, 2014. [27] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. Proceedings of the 24th International Conference on World Wide Web, page 1067–1077, 2015. [28] R.J. Trudeau. Introduction to Graph Theory. Dover Books on Mathematics. Dover Pub., 1993. [29] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. 2017. URL: https://arxiv.org/pdf/1710.10903.pdf. [30] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. 2018. URL: https://arxiv.org/pdf/1806. 03536.pdf. [31] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for webscale recommender systems. KDD 2018, pages 974–983, 2018. [32] Manzil Zaheer, Satwik Kottur, Siamak Ravanbhakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexander J Smola. Deep sets. NIPS 2017, 2017. URL: https://arxiv.org/pdf/1703.06114.pdf. [33] Muhan Zhang and Yixin Chen. Weisfeiler-lehman neural machine for link prediction. Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, page 575–583, 2017. [34] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, pages 5165–5175, 2018. URL: https://proceedings.neurips.cc/paper/2018/ file/53f0d7c537d99b3824f0f99d62ea2428-Paper.pdf. [35] Muhan Zhang, Zhicheng Hui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. The Thirty- Second AAAI Conference on Artificial Intelligence, pages 4438–4445, 2018. [36] Yingxue Zhang, Soumyasundar Pal, Mark Coates, and Deniz Üstebay. Bayesian graph convolutional neural networks for semi-supervised classification. The Thirty-Third AAAI Conference on Artificial Intelligence, 2019. 81 BIBLIOGRAFÍA 82 [37] Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data augmentation for graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35(12), pages 11015–11023, 2021. 82