SVD-Based UGRM-GFT on Directed Product Graphs

Resumen Técnico: UGRM-GFT basado en SVD sobre Grafos de Producto Dirigidos

Planteamiento del Problema
El Procesamiento de Señales en Grafos (GSP) tradicional en grafos dirigidos depende fuertamente de matrices de representación fijas, como las matrices Laplaciana o de adyacencia. Estas estructuras rígidas limitan la capacidad de un modelo para adaptarse a topologías de grafos complejas y variables, particularmente en contextos dirigidos donde la direccionalidad de las aristas significa relaciones asimétricas (por ejemplo, flujo de información o dependencias causales). Además, los métodos existentes de Transformada de Fourier en Grafos (GFT) suelen sufrir de inestabilidad numérica (por ejemplo, descomposición de Jordan) o de una alta complejidad computacional. Adicionalmente, las señales espaciotemporales modeladas en grafos producto a menudo no logran capturar atributos de correlación a través de las dimensiones cuando se restringen a grafos dirigidos singulares. Si bien enfoques recientes basados en SVD han abordado la estabilidad, estos suelen permanecer ligados a operadores estáticos que carecen de la flexibilidad para acomodar cambios estructurales en los datos del grafo.

Metodología
Para abordar estas limitaciones, los autores proponen una Transformada de Fourier en Grafos Generalizada (UGRM-GFT) basada en la Descomposición en Valores Singulares (SVD) y la Matriz de Representación de Grafo Unificada (UGRM).

1. Matriz de Representación de Grafo Unificada (UGRM): El método utiliza una matriz parametrizada $P_{\alpha,k} = \alpha D + (2k - 1)(\alpha - 1)A$, donde $D$ es la matriz de grado de entrada, $A$ es la matriz de adyacencia, y $\alpha, k \in [0, 1]$ son parámetros ajustables. Esta formulación permite que la matriz se degrade adaptativamente en representaciones clásicas (Laplaciana, de adyacencia, de grado o de Laplaciana sin signo) dependiendo de los valores de los parámetros.
2. Transformada basada en SVD: En lugar de la descomposición en autovalores, los autores aplican SVD a la UGRM. Esto produce vectores singulares izquierdos y derechos ($U_{\alpha,k}$ y $V_{\alpha,k}$) y valores singulares ($\Sigma_{\alpha,k}$). La transformada se define utilizando ambos conjuntos de vectores para asegurar la estabilidad numérica y la reconstrucción perfecta.
3. Ordenamiento Espectral: El artículo establece un ordenamiento espectral dependiente de los parámetros. Si el parámetro $\beta = (2k-1)(\alpha-1)$ es negativo, el operador se comporta como una Laplaciana (tipo diferencia), y los valores singulares se ordenan de forma no decreciente (valores más pequeños = menor frecuencia/suavidad). Si $\beta \geq 0$, el operador es de tipo adyacencia (orientado a la propagación), y los valores singulares se ordenan de forma no creciente (valores más grandes = mayor energía).
4. Dos Variantes para Grafos de Producto Cartesiano Dirigidos:
   • UGRM-GFT-I: Realiza la SVD directamente sobre la UGRM compuesta del grafo producto ($P_{\alpha,k}^{\boxtimes}$). Esto es adecuado para señales acopladas globalmente, pero tiene una complejidad computacional de $O(N^3)$ donde $N = N_1 N_2$.
   • UGRM-GFT-II: Aplica la SVD por separado a las UGRMs de los grafos factores ($P_{\alpha,k}^1$ y $P_{\alpha,k}^2$) y las recombina mediante productos de Kronecker. Este enfoque reduce la complejidad computacional de $O(N_1^3 N_2^3)$ a $O(N_1^3 + N_2^3)$ preservando la expresividad espectral.

Contribuciones Clave

• Desarrollo de Marco de Trabajo: La propuesta de un UGRM-GFT basado en SVD que unifica las matrices de grafos tradicionales en un marco parametrizado y flexible compatible con grafos dirigidos generales.
• Eficiencia Algorítmica: La introducción de UGRM-GFT-II, que reduce significativamente la complejidad computacional para grafos de producto cartesiano dirigidos sin sacrificar el rendimiento espectral.
• Análisis Teórico: El establecimiento de cotas de error de aproximación para el método propuesto. Los autores caracterizan el comportamiento espectral relativo a los parámetros $\alpha$ y $k$, demostrando que el método logra una concentración espectral más ajustada al alinear el operador con la estructura de correlación intrínseca de la señal.
• Soluciones en Forma Cerrada: Derivación de expresiones explícitas en forma cerrada tanto para las transformaciones hacia adelante como inversas, facilitando aplicaciones prácticas como la eliminación de ruido (denoising).

Resultados Experimentales
Los autores evaluaron el método en tres conjuntos de datos del mundo real: Temperatura de la Superficie del Mar (SST), concentraciones de PM-2.5 y casos confirmados de COVID-19. Estos conjuntos de datos fueron modelados como señales en grafos de producto cartesiano dirigidos.

• Desempeño en Eliminación de Ruido: En tareas de eliminación de ruido bajo niveles de ruido variables ($\sigma \in \{0.1, 0.2, 0.3, 0.4\}$) y conectividades de grafo (3-NN, 5-NN, 7-NN), UGRM-GFT superó consistentemente a los enfoques de matriz fija tradicionales (Lap-GFT, Adj-GFT, Id-GFT, SLap-GFT).
• Métricas: Los métodos propuestos lograron mayores Relaciones Señal-Ruido (SNR) y menores Errores de Aproximación de Limitación de Banda (BAE). Por ejemplo, en el conjunto de datos SST, UGRM-GFT-II logró un SNR de 9.5254 dB frente a los 9.2665 dB de Lap-GFT-II.
• Compresión de Energía: Los UGRM-GFT demostraron una compresión de energía superior. En el conjunto de datos SST, los 40 componentes espectrales principales (10% del espectro) capturaron el 95.91% de la energía total de la señal, superando significativamente a las bases de matriz fija (por ejemplo, Adj-GFT capturó solo ~22-31%).
• Adaptación de Parámetros: La optimización bayesiana identificó los parámetros óptimos $(\alpha^*, k^*)$ que variaban según el conjunto de datos. Las señales geofísicas suaves (SST, PM-2.5) favorecieron regímenes dominados por la Laplaciana ($\beta < 0$), mientras que el conjunto de datos de propagación de COVID favoreció un régimen cercano al límite ($\beta \approx -0.04$), validando la adaptabilidad del método.
• Eficiencia: UGRM-GFT-II redujo el tiempo de ejecución de la optimización de parámetros aproximadamente un 22.7% en comparación con UGRM-GFT-I en un grafo producto de $20 \times 20$.

Significancia y Reclamaciones
El artículo afirma que el propuesto UGRM-GFT aborda la rigidez del GSP tradicional mediante la introducción de una representación parametrizada que se adapta a las estructuras de correlación específicas de las señales de grafo. Al aprovechar la SVD, el método asegura la estabilidad numérica mientras que el marco UGRM permite una interpolación continua entre la información de grado y de Laplaciana. Los autores sostienen que esta flexibilidad conduce a una compresión de energía y un desempeño de eliminación de ruido superiores a través de diversos tipos de señales, desde campos geofísicos suaves hasta patrones irregulares de propagación epidémica. El trabajo proporciona una base teórica para el ordenamiento espectral basado en parámetros de operador y demuestra la utilidad práctica a través de experimentos extensos con datos reales.