Robust Graph Topology Inference

Abstract

En los últimos años, hemos presenciado una explosión masiva de datos. Esto se debe principalmente a la proliferación de dispositivos de sensores, al uso extendido de las redes sociales y a la creciente digitalización de nuestras actividades diarias. Al mismo tiempo, conforme los sistemas en red contemporáneos crecen en tamaño e importancia, los datos que generan se vuelven más complejos y diversos. Esto impulsa el rápido desarrollo de nuevos métodos y técnicas para procesar conjuntos de datos que se definen sobre dominios irregulares (no euclidianos). Entre los enfoques innovadores que han surgido para abordar los datos contemporáneos, uno especialmente eficaz y prometedor implica modelar la estructura irregular subyacente mediante un grafo y luego interpretar los datos como señales definidas en dicho grafo. Esta perspectiva basada en grafos ha ganado popularidad rápidamente y ha tenido éxito en diversos campos, como las redes sociales, geográficas, energéticas, de comunicación, financieras o biológicas, entre otras. También ha atraído la atención de investigadores de diversos campos, como la estadística, el aprendizaje automático y el procesamiento de señales. Esta forma de interpretar señales con soporte irregular como señales definidas en grafos, y utilizar la estructura subyacente del grafo para procesarlas, constituye el principio básico del procesado de señales definidas en el grafo, también conocido como graph signal processing (GSP), un campo que está en rápido desarrollo. El GSP se enfoca en crear nuevos modelos y algoritmos para el tratamiento de señales definidas en el grafo, a menudo adaptando herramientas clásicas diseñadas originalmente para señales definidas en un soporte regular como el tiempo o el espacio. El GSP se fundamenta en la idea de que existe una estrecha relación entre las propiedades de las señales y la estructura del grafo en el que se definen. Aprovechar eficazmente esta relación es clave para el éxito de GSP. Una parte importante de la investigación en GSP se dedica a comprender cómo las propiedades algebraicas y espectrales del grafo influyen en las propiedades de las señales definidas en él. El graph-shift operator (GSO) juega un papel crucial en este análisis. El GSO es una matriz dispersa que codifica la estructura del grafo, lo que lo convierte en un elemento fundamental dentro del marco de GSP. Por ejemplo, el uso del GSO permite definir diversas herramientas espectrales, como la transformada de Fourier en grafos. También facilita la creación de operadores de señales definidas en el grafo más generalizados, como los sistemas de filtros en grafos, que pueden expresarse como polinomios del GSO...