Las señales soportadas en grafos pueden modelar, por ejemplo, niveles de congestión vehicular sobre redes viales, actividad económica entre sectores industriales, estados infecciosos en una epidemia, la actividad cerebral en redes de conectividad cerebral, o la difusión de noticias falsas.
Comprender datos a gran escala desde una perspectiva centrada en la red es clave para obtener nuevos conocimientos en diversas áreas de la ciencia y la ingeniería; y el procesamiento de señales cumple un papel central. El aprendizaje automático, en particular, puede beneficiarse significativamente de representaciones basadas en grafos. Sin embargo, existe una brecha entre el entendimiento de señales en dominios regulares (tiempo o espacio) y señales en grafos. Mientras el conocimiento sobre series temporales se desarrolló por décadas, los problemas de procesamiento de señales en redes son recientes.
En este contexto, este curso se centra en fundamentos y avances algorítmicos para aprender a partir de datos de red (i.e., grafos). Se aborda desde el aprendizaje de representaciones de grafos para señales complejas, hasta fundamentos de procesamiento de señales en grafos, modelos estadísticos, y aprendizaje de representaciones eficientes mediante arquitecturas modernas de redes neuronales sobre grafos.
Introducimos el problema de la inferencia de la topología de la red. En particular, las GNNs estudiadas en la clase anterior presuponen la disponibilidad de un grafo que codifica la información relacional relevante asociada al problema que queremos resolver. Sin embargo, en algunas instancias dicha suposición puede ser insostenible en la práctica – el grafo puede ser desconocido y queremos estimar su topología a partir de observaciones nodales.
Primero se cubren enfoques estadísticos bastante maduros, donde el análisis de correlación ocupa un lugar central junto con sus conexiones al método de selección de covarianza
Clase 1 — Lunes — Introducción y motivación
Se introduce la noción de red y se presenta una visión "a vuelo de pájaro" del área interdisciplinaria conocida como Network Science, comenzando con un trasfondo histórico. Continuaremos con una serie de ejemplos motivadores para argumentar la importancia, actualidad y relevancia del tema para el procesamiento de señales. El resto de la clase se divide en cuatro "historias cortas" sobre problemas prototípicos en aprendizaje estadístico a partir de datos de red: (i) procesamiento de señales en grafos (GSP); (ii) clasificación de nodos semisupervisada; (iii) detección de comunidades en redes; y (iv) predicción de enlaces. En el proceso, destacamos una serie de cuestiones intrigantes y los desafíos de análisis y cómputo.
Clase 2 — Martes — Redes neuronales sobre grafos (GNNs)
En esta clase introduciremos el concepto de Redes Neuronales sobre Grafos (GNNs), que pretenden extender el éxito de las redes neuronales convolucionales al procesamiento de señales de alta dimensión en dominios no euclidianos. Los siguientes temas serán cubiertos:
(i) Convoluciones en grafos y arquitecturas GNN. El concepto clave que permite la definición de GNNs es el filtro de convolución sobre grafos introducido en la literatura de procesamiento de señales en grafos (GSP). Las arquitecturas GNN componen filtros de grafos con no-linealidades punto a punto. Se ilustrará con ejemplos prácticos.
(ii) Propiedades fundamentales de las GNNs. Los filtros de grafos y las GNNs son arquitecturas adecuadas para procesar señales en grafos porque presentan equivarianza a la permutación.
(iii) Transformers y su interpretación en el marco de GNNs.
Clase 3 — Miércoles — Aprendizaje de grafos
y regresión de alta dimensionalidad para aprender modelos grafológicos gaussianos. También se describen los recientes marcos de inferencia de redes basados en GSP, los cuales postulan que la red existe como estructura latente subyacente y que las observaciones se generan como resultado de un proceso de red definido en ese grafo.
Ilustraremos las diversas metodologías de inferencia de topología mediante aplicación a movilidad urbana, clasificación de emociones, identificación de estructuras proteicas, entre otras.
Clase 4 — Jueves — Modelos para datos de red
Presentamos varias clases importantes de modelos de grafos de red: (i) modelos de grafos aleatorios; (ii) modelos "small-world"; (iii) modelos de crecimiento de redes; (iv) modelos aleatorios exponenciales de grafos; y (v) modelos de red con variables latentes. Por razones de aplicabilidad, relevancia y madurez de resultados existentes, nos enfocamos mayormente en (v), cubriendo modelos de bloques estocásticos (SBMs), su contraparte no paramétrica basada en graphones, y los Random Dot Product Graphs (RDPGs).
El énfasis está en la construcción de modelos, la simulación, la inferencia de parámetros del modelo y los diagnósticos de bondad de ajuste. A lo largo se ilustran algunos de los usos estadísticos a los que estos modelos han sido sometidos, incluyendo la detección de motivos de red, la evaluación de mecanismos generativos de redes propuestos, detección de puntos de cambio, y la evaluación de factores predictivos potenciales de vínculos relacionales.
Clase 5 — Viernes — Graph Representation Learning
Presentamos un amplio espectro de enfoques para aprender representaciones de datos estructurados como grafos. Basándonos en instancias particulares que hemos visto en clases anteriores (por ejemplo, representaciones aprendidas con GNN y embebidos espectrales de adyacencia para RDPGs), definimos formalmente el problema de embebido de redes y describimos un modelo codificador-decodificador unificado para comparar una selección de enfoques de aprendizaje de representaciones de grafos bajo un marco común.
Estos enfoques incluyen: (i) embebidos superficiales ("shallow embeddings"); (ii) auto-codificadores de grafos; (iii) regularización de grafos; y (iv) métodos de agregación de vecindario. Discutimos el papel de la supervisión y la búsqueda de embebidos optimizados para una tarea posterior (downstream task).
Cerramos con varios estudios de caso de aplicación, provenientes de neurociencia de redes, síntesis molecular y redes sociales dinámicas.
Objetivos del curso:
Al finalizar este curso, los estudiantes serán capaces de:
Comprender los fundamentos del procesamiento de señales sobre grafos y las diferencias frente a dominios regulares.
Identificar y modelar señales definidas sobre redes y grafos, conociendo los principales retos de inferencia y representación.
Conocer los principales modelos estadísticos de datos en redes, incluidas estructuras generativas de grafos, como por ejemplo Stochastic Block Model, grafos geométricos (como Random Dot Product Graphs), y grafones.
Entender el funcionamiento de arquitecturas modernas de aprendizaje sobre grafos —especialmente las GNNs—, sus propiedades, ventajas y limitaciones.
Implementar métodos aplicados sobre datos en grafos: manipulación de grafos, inferencia de estructura de grafo, aprendizaje de embeddings, predicción de nodos/enlaces.
Aplicar estos métodos en diferentes dominios (por ejemplo redes de comunicación, sociales, cerebrales o de infraestructura) para extraer significado de datos complejos con estructura de red.
Statistical Analysis of Network Data: Methods and Models, Eric D. Kolaczyk, Springer 2009.
M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, P. Vandergheynst, "Geometric deep learning: going beyond Euclidean data," 2017.
G. Mateos, S. Segarra, A. G. Marques, A. Ribeiro, "Connecting the dots: Identifying network structure via graph signal processing," 2019.
V. Kalofolias, "How to learn a graph from smooth signals," 2016.
E. R. Scheinerman, K. Tucker, "Modeling graphs using dot product representations," 2010.
A. Athreya, D. E. Fishkind, K. Levin, V. Lyzinski, Y. Qin, Y. Park, D. L. Sussman, M. Tang, J. T. Vogelstein, and C. E. Priebe, "Statistical inference on random dot product graphs: A survey," 2018.
William L. Hamilton, "Graph Representation Learning Book", 2020.
I. Chami, S. Abu-El-Haija, B. Perozzi, C. Ré, K. Murphy, "Machine learning on graphs: A model and comprehensive taxonomy," Journal of Machine Learning Research, 2022.
Desarrollado por el Departamento de Computación, FCEyN, UBA