Aprendizaje Automático para Datos en Grafos
Diagrama de temas
-
IMPORTANTE: Esta versión intensiva de una semana del curso se dictó por única vez en 2021. Una versión extendida de todo el semestre se puede encontrar [aquí].
Los grafos (o redes) son una estructura de datos presente en muchísimas áreas de conocimiento: redes de telecomunicaciones, sistemas de recomendación, redes de regulación genética, estructuturas de proteínas o movilidad urbana son solo algunos ejemplos. Básicamente, son entidades (nodos) que interactúan entre sí (aristas).
Sobre estos datos existen muchos problemas interesantes de aprendizaje automático, donde básicamente se busca realizar predicciones o descubrir cierta estructura en los datos: detección de anomalías en una red inalámbrica, recomendación de libros a partir de clasificaciones anteriores y de otros usuarios, o clasificación del rol de ciertas proteínas en redes de interacción biológica. Sin embargo, está claro que técnicas de aprendizaje “tradicionales” (donde los datos son básicamente un vector o una matriz) que no toman en cuenta las relaciones entre las distintas entidades tendrán menor poder de generalización (y por lo tanto mucho peor desempeño) que aquellas que sí lo tomen en cuenta.
El objetivo general del curso es que los estudiantes puedan afrontar un problema de aprendizaje automático donde los datos se encuentran en forma de grafos. Se brindarán los conceptos teóricos fundamentales y las herramientas prácticas necesarias para ello. Al finalizar el curso los estudiantes serán capaces de implementar y entender distintas técnicas del estado del arte en inferencia y predicción en grafos.
Docente: Prof. Gonzalo Mateos (Universidad de Rochester, EEUU).Docente invitado: Fernando Gama (Universidad de California Berkeley, EEUU).Otros docentes: Marcelo Fiori y Federico La Rocca.Fechas: Lunes 1º de febrero alviernes 5jueves 4 de febrero, y jueves 11 de febrero.Horario: 9hs a 12hs15 (lunes a jueves) y 14hs a 17hs15 el jueves 11/2.Lugar: remoto via zoomIMPORTANTE:Inscripciones como curso de posgrado en: https://bedelias.udelar.edu.uy/Inscripciones como Educación Permanente en: https://www.fing.edu.uy/bedelia/inscripciones/actualizacionDe todas formas quienes planean inscribirse deben matricularse en este EVA para recibir los anuncios y demás información.-
Encuestas obligatorias por la Unidad de Enseñanza, Unidad de Posgrados y Educación Permanente
-
Enviar retroalimentación
-
-
Charla dictada por Federico La Rocca en el marco de las Tech Meetings de Tryolabs. Puede servir como introducción al curso.
-
Se cubren las nociones y definiciones básicas relacionadas con los grafos dirigidos y no dirigidos, el movimiento en un grafo y la conectividad, así como la aparición de una componente conexa gigante en muchas redes reales. A continuación, describimos familias de grafos clásicas que incluyen grafos completos, regulares, bipartitos, árboles y planares. Nos resultaran de gran utilidad las nociones de teoría algebraica de grafos, como la matriz adyacencia, la matriz de incidencia y el Laplaciano de un grafo, sus relaciones y propiedades espectrales. Terminamos con algoritmos y estructuras de datos para grafos y describimos breadth-first-search (BFS) para, por ejemplo, calcular distancias desde un vértice determinado.
-
Se repasan elementos básicos de inferencia estadística tales como los modelos paramétricos y no paramétricos, y los problemas fundamentales de estimación, predicción y test de hipótesis. Esbozaremos los conceptos de estimación puntual, intervalos de confianza y estadístico de prueba, ademas de estimadores clásicos como el método de los momentos, máxima verosimilitud, mínimos cuadrados y máximo a posteriori (MAP). Todos estos métodos se discutirán en el contexto de dos problemas clásicos: inferencia de la media de una distribución y regresión (mas predicción) con modelos lineales.
-
En esta clase introductoria comenzamos con una presentación de los aspectos administrativos del curso. Se introduce el concepto fundamental de red (así como su abstracción mediante un grafo) y desde una perspectiva histórica motivamos la “ciencia de datos de redes”. A través de ejemplos en múltiples disciplinas intentamos justificar la importancia e impacto del aprendizaje automático para datos en grafos. El resto de la clase se divide en cuatro “cuentos cortos” sobre problemas prototípicos del aprendizaje automático para datos en grafos. Durante esta recorrida resaltaremos el nuevo paradigma necesario para atacar problemas de inferencia estadística con datos irregulares, es decir donde no hay un dominio Euclideo subyacente como en series temporales o imágenes. También delineamos los principales desafíos técnicos (metodológicos y computacionales) de esta área emergente donde las oportunidades son cada vez mayores, motivando el camino a seguir en el resto del curso.
-
-
-
En esta clase introduciremos las Graph Neural Networks (GNN), mediante las cuales se busca extender el éxito de las redes convolucionales (CNNs) al procesamiento de señales de alta dimensión en dominios no Euclideos. Esto se logra explotando la estructura irregular del dominio de los datos (estructuras que naturalmente representamos mediante un grafo). Se cubrirán los siguientes temas:
- Convoluciones de señales en grafos y arquitecturas GNN. El concepto fundametal que permite la definición de GNNs es el filtro convolucional para señales en grafos, cuyo origen puede trazarse a la literatura de Graph Signal Processing (GSP). Las arquitecturas GNN componen filtros con no linealidades formando capas. Se cubrirán ejemplos ilustrativos sobre sistemas de recomendación y atribución de autoría en textos.
- Propiedades fundamentales de las GNN. Los filtros convolucionales y las GNN son arquitecturas ideales para procesar señales en grafos debido a su equivariancia respecto a las permutaciones. Las GNNs tienden a ser mas efectivas que los filtros lineales porque son Lipschitz-estables a las deformaciones del grafo subyacente. Esta es una propiedad que los filtros convolucionales lineales no pueden tener.
- Control distribuido de sistemas multiagente. Un dominio de aplicación interesante para las GNNs es el control distribuido de sistemas multiagente a gran escala. Se desarrollarán aplicaciones referentes al control de equipos de robots autónomos y a la signación de recursos en redes de comunicación inalámbrica.
-
-
-
En esta clase estudiamos el problema de inferencia de topología de la red. En particular, las GNNs que estudiamos la clase pasada presuponen que se dispone de un grafo que contiene información relevante sobre el problema a resolver. Sin embargo, tal suposición es a menudo insostenible en la práctica — el grafo puede ser desconocido y deseamos estimar su estructura a partir de observaciones de señales en los nodos. Presentaremos diversos métodos comenzando por enfoques estadísticos basados en modelos gráficos, inferencia de correlaciones y algoritmos para problemas en altas dimensiones. Luego estudiamos avances recientes inspirados en modelos de Graph Signal Processing (GSP) de una manera integral y unificadora, con aplicaciones a mobilidad urbana, clasificación de emociones, e identificación de la estructura de proteínas, entre otras.
-
-
-
En esta cuarta clase estudiaremos el modelado estadístico de datos relacionales que representamos mediante grafos. Introducimos varias familias de modelos generativos para dichos datos: (i) modelos clásicos de grafos aleatorios; (ii) modelos de redes “small world”; (iii) modelos de crecimiento y conexión preferencial; (iv) modelos de grafos aleatorios de la familia exponencial; y (v) modelado de grafos mediante variables latentes. Por un tema de aplicabilidad, relevancia y madurez de los resultados existentes, nos enfocaremos principalmente en (v), cubriendo “stochastic block models” (SBMs), la contraparte no paramétrica basada en “graphons”, y los “random dot product graphs” (RDPGs). Haremos énfasis en la construcción de los modelos y su plausibilidad a la hora de representar datos de grafos reales, en la simulación, la inferencia de los parámetros del modelo (discutiendo aspectos computacionales de los estimadores y sus propiedades asintóticas), así como diagnósticos de bondad del ajuste. Durante la clase ilustraremos la utilidad práctica de estos modelos mediante aplicaciones, incluyendo la detección de motifs y comunidades, la evaluación formal de hipótesis acerca de mecanismos generativos de red y de factores predictivos de vínculos relacionales.
-
-
-
Un primer laboratorio para familiarizarse con algunas herramientas para procesar grafos.
-
Un laboratorio para repasar algunos modelos clásicos de grafos, y sobre cómo usar espacios latentes para detectar comunidades en grafos.
-
Un laboratorio sobre sistemas de recomendación para afianzar conceptos de GNNs.
-
Entregar un único pdf con las respuestas a los tres laboratorios. Hay tiempo hasta el domingo 28 de febrero a las 23:55.
-
-
El plazo para entregar la propuesta de trabajo final es el viernes 19/2 a las 23:55.
-
Entregar un único pdf con el informe. Material extra, como código o demos en google colab, deben referirse desde este pdf. La fecha límite para la entrega del informe final es el lunes 5 de abril a las 23:55.
-
-
-
Uno de los paquetes de análisis de grafos más populares para Python. Muy fácil de usar y se integra con otras bibliotecas.
-
El equipo dirigido por Jure Leskovec comparte una biblioteca (en C++ y Python), además de varios dataset.
-
Una biblioteca bastante popular para aprendizaje en grafos.
-
Una biblioteca para implementar GNNs con el gran plus de que es agnóstico al framework (PyTorch o TensorFlow).
-
Una biblioteca basada en TensorFlow para implementar GNNs.
-
Una biblioteca libre y gratuita básicamente para GNNs.
-
Una biblioteca en python para signal processing en grafos.
-
Similar a networkx, pero más eficiente.
-
Otra biblioteca similar a networkx, pero disponible en varios lenguajes (C, python y R), y también más rápida.
-
Otra biblioteca similar a networkx, pero también más rápida.
-
Un scikit específico para grafos.
-
El grupo de Alejandro Ribeiro comparte implementaciones basadas en Pytorch de casi todos sus trabajos en este repo.
-
El equipo dirigido por Jure Leskovec comparte una biblioteca (en C++ y Python), además de varios dataset.
-
Un catálogo de grafos del grupo del creador de graph-tools.
-
Un catálogo de grafos, que además pueden visualizarse en línea.
-
Varios datasets de la Universidad de Harvard. No es específico de grafos, pero varios se pueden analizar desde esa perspectiva.
-
El grupo Grouplens de la Universidad de Minnesota tiene varios datasets disponibles.
-
Es un catálogo de datos abiertos a nivel gubernamental del Uruguay. Tiene varios datasets que pueden interpretarse como grafos. Por ejemplos, viajes de ómnibus (https://catalogodatos.gub.uy/dataset/intendencia-montevideo-viajes-realizados-en-los-omnibus-del-stm).
-
Varios datasets para hacer benchmark. Incluye métodos para cargarlos desde PyTorch Geometric o DGL, además de Leaderboards (con código asociado).
-
Kaggle ofrece varios datasets, códigos de ejemplo y turoriales. El link es para la sección de datasets.