Inferencia de topología en línea de señales de grafo estacionarias en streaming con información parcial de conectividad
Autores: Shafipour, Rasoul; Mateos, Gonzalo
Idioma: Inglés
Editor: MDPI
Año: 2020
Acceso abierto
Artículo científico
2020
Inferencia de topología en línea de señales de grafo estacionarias en streaming con información parcial de conectividad
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Algoritmos de aprendizaje de gráficos en línea
Datos de red en tiempo real
Topología de red
Ahorro de memoria y computacional
Señales de gráficos
Inferencia de topología
Datos en tiempo real
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 29
Citaciones: Sin citaciones
Desarrollamos algoritmos de aprendizaje de gráficos en línea a partir de datos de red en continuo. Nuestro objetivo es rastrear la topología de la red (posiblemente) variable en el tiempo y lograr ahorros de memoria y computación procesando los datos sobre la marcha a medida que se adquieren. La configuración implica observaciones modeladas como señales de gráficos estacionarios generadas por dinámicas de difusión locales en la red desconocida. Además, podemos tener información a priori sobre la presencia o ausencia de algunos bordes como en el problema de predicción de enlaces. La suposición de estacionariedad implica que la matriz de covarianza de las observaciones y el llamado operador de cambio de gráfico (GSO, una matriz que codifica la topología del gráfico) conmutan bajo requisitos leves. Esto motiva la formulación de la tarea de inferencia de topología como un problema inverso, en el que se busca un GSO disperso que sea estructuralmente admisible y que conmute aproximadamente con la matriz de covarianza empírica de las observaciones. Para datos en continuo, dicha covarianza se puede actualizar de forma recursiva, y mostramos que las iteraciones en línea del gradiente proximal pueden utilizarse eficientemente para rastrear la solución variable en el tiempo del problema inverso con garantías cuantificables. Específicamente, derivamos condiciones bajo las cuales el costo de recuperación de GSO es fuertemente convexo y usamos esta propiedad para demostrar que el algoritmo en línea converge dentro de un vecindario de la solución de lote óptima variable en el tiempo. Las pruebas numéricas ilustran la efectividad del enfoque propuesto de aprendizaje de gráficos en adaptarse a la información en continuo y rastrear cambios en la red dinámica buscada.
Descripción
Desarrollamos algoritmos de aprendizaje de gráficos en línea a partir de datos de red en continuo. Nuestro objetivo es rastrear la topología de la red (posiblemente) variable en el tiempo y lograr ahorros de memoria y computación procesando los datos sobre la marcha a medida que se adquieren. La configuración implica observaciones modeladas como señales de gráficos estacionarios generadas por dinámicas de difusión locales en la red desconocida. Además, podemos tener información a priori sobre la presencia o ausencia de algunos bordes como en el problema de predicción de enlaces. La suposición de estacionariedad implica que la matriz de covarianza de las observaciones y el llamado operador de cambio de gráfico (GSO, una matriz que codifica la topología del gráfico) conmutan bajo requisitos leves. Esto motiva la formulación de la tarea de inferencia de topología como un problema inverso, en el que se busca un GSO disperso que sea estructuralmente admisible y que conmute aproximadamente con la matriz de covarianza empírica de las observaciones. Para datos en continuo, dicha covarianza se puede actualizar de forma recursiva, y mostramos que las iteraciones en línea del gradiente proximal pueden utilizarse eficientemente para rastrear la solución variable en el tiempo del problema inverso con garantías cuantificables. Específicamente, derivamos condiciones bajo las cuales el costo de recuperación de GSO es fuertemente convexo y usamos esta propiedad para demostrar que el algoritmo en línea converge dentro de un vecindario de la solución de lote óptima variable en el tiempo. Las pruebas numéricas ilustran la efectividad del enfoque propuesto de aprendizaje de gráficos en adaptarse a la información en continuo y rastrear cambios en la red dinámica buscada.