Inferencia de la topología de una red a partir de observaciones nodales con variables ocultas: Un enfoque basado en procesamiento de señales en grafos

Abstract

La generación, acceso y capacidad de procesar cantidades ingentes de datos es una de las características que definen nuestro tiempo. La mayor parte de estos datos se generan en sistemas conectados e interdependientes con estructuras complejas tales como las cascadas de información en redes sociales o los datos biomédicos en redes cerebrales o moleculares. El hecho que la información se genere en redes complejas hace que la estructura de la red (inequívocamente ligada a la de los propios datos) juegue un papel crucial a la hora del procesamiento, análisis y representación de la información generada. La forma más habitual de atacar estos problemas consiste en intentar utilizar una representación tratable de los elementos de la red (típicamente a través de un grafo) y la postulación de modelos que relacionen los datos observados con la estructura del grafo. Muchos modelos de análisis de datos parten del conocimiento de la topología de red y se centran en el impacto del grafo en las propiedades de los datos. Este análisis es viable cuando se trata de redes físicas o relaciones fácilmente observables. En muchas otras ocasiones no se tiene acceso a dicha estructura (la topología puede cambiar a lo largo del tiempo o pueden existir restricciones de privacidad) y, en esos casos, el primer objetivo es inferir el grafo a partir de los datos generados (observados) en los nodos. Este es un problema clásico en estadística, con contribuciones de hace más de 100 años, y que, recientemente, ha atraído la atención de las comunidades del aprendizaje máquina y el Graph Signal Processing (GSP). En este contexto, el objetivo de este Trabajo Fin de Máster (TFM) consiste en modificar algoritmos recientes de inferencia de grafos propuestos en el ámbito de GSP para que sean capaces de tratar con variables ocultas. La presencia de nodos cuyo estado no se puede observar es frecuente en la práctica y, por tanto, resulta primordial que se desarrollen algoritmos capaces de operar en esas condiciones. El modelo considerado en este TFM asume que las observaciones son estacionarias en el grafo (lo que equivale a decir que la relación entre la matriz de adyacencia del grafo y la matriz de covarianza de las observaciones viene dada por un polinomio) y, mediante el uso de técnicas de sparse and low-rank optimization, propone varios algoritmos para inferir la topología del grafo en presencia de variables ocultas. Las prestaciones de dichos algoritmos son cuantificadas y comparadas y la influencia de ciertos parámetros en la calidad de la solución obtenida es estudiada a partir de simulaciones numéricas.