SVD-Based UGRM-GFT on Directed Product Graphs

Resumo Técnico: UGRM-GFT Baseado em SVD em Grafos de Produto Direcionados

Declaração do Problema
O Processamento de Sinais em Grafos (GSP) tradicional em grafos direcionados baseia-se fortemente em matrizes de representação fixas, como matrizes Laplacianas ou de adjacência. Essas estruturas rígidas limitam a capacidade de um modelo de se adaptar a topologias de grafos complexas e variáveis, particularmente em contextos direcionados onde a direcionalidade das arestas significa relações assimétricas (ex: fluxo de informação ou dependências causais). Além disso, os métodos existentes de Transformada de Fourier de Grafo (GFT) frequentemente sofrem de instabilidade numérica (ex: decomposição de Jordan) ou alta complexidade computacional. Adicionalmente, sinais espaço-temporais modelados em grafos de produto podem falhar em capturar atributos de correlação entre dimensões quando restritos a grafos direcionados singulares. Embora abordagens recentes baseadas em SVD tenham tratado a estabilidade, elas tipicamente permanecem vinculadas a operadores estáticos que carecem da flexibilidade para acomodar mudanças estruturais nos dados de grafos.

Metodologia
Para abordar essas limitações, os autores propõem uma Transformada de Fourier de Grafo Generalizada (UGRM-GFT) baseada em Decomposição de Valor Singular (SVD) e na Matriz de Representação de Grafo Unificada (UGRM).

1. Matriz de Representação de Grafo Unificada (UGRM): O método utiliza uma matriz parametrizada $P_{\alpha,k} = \alpha D + (2k - 1)(\alpha - 1)A$, onde $D$ é a matriz de grau de entrada e $A$ é a matriz de adjacência, e $\alpha, k \in [0, 1]$ são parâmetros ajustáveis. Esta formulação permite que a matriz se degrade adaptativamente em representações clássicas (Laplaciana, adjacência, grau ou Laplaciana sem sinal) dependendo dos valores dos parâmetros.
2. Transformada Baseada em SVD: Em vez da decomposição em autovalores, os autores aplicam SVD à UGRM. Isso gera vetores singulares à esquerda e à direita ($U_{\alpha,k}$ e $V_{\alpha,k}$) e valores singulares ($\Sigma_{\alpha,k}$). A transformada é definida usando ambos os conjuntos de vetores para garantir estabilidade numérica e reconstrução perfeita.
3. Ordenação Espectral: O artigo estabelece uma ordenação espectral dependente de parâmetros. Se o parâmetro $\beta = (2k-1)(\alpha-1)$ for negativo, o operador comporta-se como uma Laplaciana (tipo diferença), e os valores singulares são ordenados de forma não decrescente (valores menores = frequência/suavidade mais baixas). Se $\beta \geq 0$, o operador é do tipo adjacência (orientado à propagação), e os valores singulares são ordenados de forma não crescente (valores maiores = maior energia).
4. Duas Variantes para Grafos de Produto Cartesiano Direcionados:
   • UGRM-GFT-I: Realiza SVD diretamente na UGRM composta do grafo de produto ($P_{\alpha,k}^{\boxtimes}$). Isto é adequado para sinais globalmente acoplados, mas possui uma complexidade computacional de $O(N^3)$ onde $N = N_1 N_2$.
   • UGRM-GFT-II: Aplica SVD separadamente às UGRMs dos grafos de fator ($P_{\alpha,k}^1$ e $P_{\alpha,k}^2$) e recombina-as via produtos de Kronecker. Esta abordagem reduz a complexidade computacional de $O(N_1^3 N_2^3)$ para $O(N_1^3 + N_2^3)$, preservando a expressividade espectral.

Principais Contribuições

• Desenvolvimento de Framework: A proposta de um UGRM-GFT baseado em SVD que unifica matrizes de grafos tradicionais em um framework parametrizado e flexível compatível com grafos direcionados gerais.
• Eficiência Algorítmica: A introdução do UGRM-GFT-II, que reduz significativamente a complexidade computacional para grafos de produto cartesiano direcionados sem sacrificar o desempenho espectral.
• Análise Teórica: O estabelecimento de limites de erro de aproximação para o método proposto. Os autores caracterizam o comportamento espectral em relação aos parâmetros $\alpha$ e $k$, provando que o método alcança uma concentração espectral mais estreita ao alinhar o operador com a estrutura de correlação intrínseca do sinal.
• Soluções de Forma Fechada: Derivação de expressões explícitas de forma fechada para ambas as transformações direta e inversa, facilitando aplicações práticas como a redução de ruído (denoising).

Resultados Experimentais
Os autores avaliaram o método em três conjuntos de dados do mundo real: Temperatura da Superfície do Mar (SST), concentrações de PM-2.5 e casos confirmados de COVID-19. Estes conjuntos de dados foram modelados como sinais em grafos de produto cartesiano direcionados.

• Desempenho de Denoising: Em tarefas de denoising através de vários níveis de ruído ($\sigma \in \{0.1, 0.2, 0.3, 0.4\}$) e conectividades de grafo (3-NN, 5-NN, 7-NN), o UGRM-GFT superou consistentemente abordagens de matriz fixa tradicionais (Lap-GFT, Adj-GFT, Id-GFT, SLap-GFT).
• Métricas: Os métodos propostos alcançaram Razões Sinal-Ruído (SNR) mais altas e Erros de Aproximação de Limitação de Banda (BAE) mais baixos. Por exemplo, no conjunto de dados SST, o UGRM-GFT-II alcançou um SNR de 9.5254 dB comparado a 9.2665 dB para o Lap-GFT-II.
• Compactação de Energia: Os UGRM-GFTs demonstraram uma compactação de energia superior. No conjunto de dados SST, os 40 principais componentes espectrais (10% do espectro) capturaram 95.91% da energia total do sinal, superando significativamente as bases de matriz fixa (ex: Adj-GFT capturou apenas ~22-31%).
• Adaptação de Parâmetros: A otimização Bayesiana identificou parâmetros ótimos $(\alpha^*, k^*)$ que variaram conforme o conjunto de dados. Sinais geofísicos suaves (SST, PM-2.5) favoreceram regimes dominados pela Laplaciana ($\beta < 0$), enquanto o dataset de propagação de COVID, baseado em propagação, favoreceu um regime próximo à fronteira ($\beta \approx -0.04$), validando a adaptabilidade do método.
• Eficiência: O UGRM-GFT-II reduziu o tempo de execução da otimização de parâmetros em aproximadamente 22.7% em comparação ao UGRM-GFT-I num grafo de produto $20 \times 20$.

Significância e Alegações
O artigo afirma que o proposto UGRM-GFT aborda a rigidez do GSP tradicional ao introduzir uma representação parametrizada que se adapta às estruturas de correlação específicas dos sinais de grafos. Ao alavancar o SVD, o método garante estabilidade numérica, enquanto o framework UGRM permite uma interpolação contínua entre a informação de grau e de Laplaciana. Os autores afirmam que esta flexibilidade leva a uma compactação de energia e desempenho de denoising superiores através de diversos tipos de sinais, desde campos geofísicos suaves até padrões irregulares de propagação epidêmica. O trabalho fornece uma base teórica para a ordenação espectral baseada em parâmetros de operador e demonstra utilidade prática através de extensos experimentos em dados reais.