Resumo Técnico: Sinais de Distribuição de Grafos em Espaços de Wasserstein

1. Enunciado do Problema

O Processamento de Sinais em Grafos (GSP) clássico representa sinais como vetores indexados por vértices de um grafo, baseando-se em operadores lineares como a Transformada de Fourier de Grafo (GFT) e filtros de grafo. Embora eficaz, este arcabouço baseado em vetores enfrenta três limitações críticas em aplicações do mundo real:

1. Suposição de Observações Completas: O GSP clássico requer dados síncronos e completos em todos os nós para aplicar operadores como a GFT. Na prática, a coleta de dados é frequentemente assíncrona ou incompleta (ex: relatórios de sensores ausentes), tornando os métodos padrão baseados em vetores inaplicáveis ou exigindo imputação enviesada.
2. Exigência de Correspondência Estrita de Sinal: Métodos estatísticos de GSP tipicamente aprendem filtros a partir de amostras de vetores de entrada-saída pareadas $\{(x_i, y_i)\}$. Isso impõe uma correspondência temporal um-para-um rígida. Dados do mundo real frequentemente sofrem com deslocamentos temporais, sobreposições ou embaralhamentos, quebrando esse alinhamento.
3. Suposição de Topologia Determinística: O GSP clássico assume uma topologia de grafo fixa e conhecida (ex: uma matriz de adjacência específica). No entanto, em muitos sistemas, a estrutura do grafo é incerta, parcialmente observada ou inerentemente dependente da própria realização do sinal.

Abordagens de GSP estatístico existentes frequentemente tratam a aleatoriedade por meio de variáveis aleatórias, mas ainda operam sobre amostras vetoriais, falhando em abordar plenamente essas incertezas estruturais e observacionais.

2. Metodologia

Os autores propõem um arcabouço unificado onde os sinais de grafo são modelados não como vetores, mas como Sinais de Distribuição de Grafo (GDSs) — medidas de probabilidade que residem em um espaço de Wasserstein ($\mathcal{P}_p(\mathbb{R}^N)$).

Conceitos Centrais

• Sinal de Distribuição de Grafo (GDS): Um sinal é definido como uma medida de probabilidade de Borel $\mu \in \mathcal{P}_p(\mathbb{R}^N)$. Sinais vetoriais tradicionais $x$ são recuperados como casos especiais onde $\mu = \delta_x$ (medida de Dirac).
• Estruturas de Grafo Adaptativas ao Sinal (SAGS): O arcabouço generaliza topologias de grafos fixos ao modelar o grafo $G$ como uma variável aleatória condicionada ao sinal $x$. Formalmente, para um sinal $x$, a estrutura do grafo segue uma distribuição condicional $\nu_x$. Isso captura padrões de conectividade dependentes do sinal.
• Distância de Wasserstein: O arcabouço utiliza a distância $p$-Wasserstein ($W_p$) para medir discrepâncias entre distribuições de sinais, fornecendo uma métrica que considera tanto deslocamentos de média quanto mudanças de covariância/estrutura.

Operações Generalizadas

O artigo estabelece um dicionário sistemático mapeando conceitos de GSP clássico para seus análogos de GDS via medidas de pushforward:

• Transformada de Fourier de GDS (GDS-FT): Definida como a medida de pushforward da distribuição do sinal $\mu$ através da matriz da base de Fourier de grafo $U_G^\top$. Para uma distribuição conjunta de sinal e grafo, a transformada leva em conta a incerteza na topologia do grafo.
• Filtro de Convolução de GDS: Um filtro $F_G$ (tipicamente um polinômio do Operador de Deslocamento de Grafo) atua sobre a distribuição $\mu$ via aplicação de pushforward $(F_G)_*\mu$. Esta operação transforma a distribuição no domínio dos vértices para o domínio espectral, a remodela e a transforma de volta.
• Transformadas Generalizadas: O arcabouço define transformadas generalizadas para configurações de SAGS, onde a distribuição de saída é derivada da distribuição conjunta do sinal e do grafo dependente do sinal.

Garantias Teóricas

Os autores estabelecem propriedades analíticas para estas transformadas generalizadas:

• Continuidade: As transformadas são mostradas como uniformemente contínuas em domínios de sinal compactos e contínuas pontualmente sob condições de Lipschitz na distribuição da transformada induzida.
• Estabilidade: Estes resultados de continuidade garantem que pequenas perturbações na distribuição de entrada (devido a ruído, mudanças de distribuição ou aproximação de amostra finita) levam a perturbações controladas na saída, assegurando robustez para aprendizado e inferência.

Algoritmos de Aplicação

Duas aplicações específicas são desenvolvidas para demonstrar o arcabouço:

1. Aprendizado de Filtro de Grafo: O objetivo é aprender um filtro $F_G$ que transporta uma distribuição de entrada $\mu_\theta$ para uma distribuição alvo $\mu^\star$. Os autores propõem duas abordagens paramétricas:
   • Baseada em Cópula: Modela a distribuição conjunta acoplando marginais via uma cópula Gaussiana, permitindo uma modelagem de dependência flexível mesmo com dados ausentes.
   • Baseada em GMM: Representa a distribuição conjunta como um Modelo de Mistura Gaussiana (GMM), utilizando a distância de Mistura-Wasserstein ($MW_2$) para otimização tratável.
2. Detecção de Anomalias: Em vez de aplicar limiares em estatísticas escalares (como o coeficiente de alta frequência máxima), o método caracteriza a distribuição empírica das características espectrais de alta frequência. Anomalias são detectadas medindo a discrepância (via $MW_2$ ou distância de localização de pico) entre a distribuição de um lote de teste e uma distribuição de referência estimada a partir de dados normais.

3. Principais Contribuições

1. Arcabouço Unificado: Desenvolvimento de um arcabouço de GSP onde os sinais são medidas de probabilidade em espaços de Wasserstein e as topologias de grafo são distribuições adaptativas ao sinal, generalizando estritamente o GSP clássico baseado em vetores.
2. Correspondência Sistemática: Formalização de um dicionário que mapeia operações centrais de GSP (transformada de Fourier, filtragem, convolução) para seus equivalentes em nível de distribuição, mostrando as formulações clássicas como casos especiais.
3. Teoria de Estabilidade: Estabelecimento de resultados de continuidade para transformadas de GDS generalizadas, fornecendo garantias teóricas de estabilidade para perturbações de entrada e aproximações de distribuição.
4. Validação Empírica: Demonstração da utilidade do arcabouço no aprendizado de filtros de grafo e detecção de anomalias, mostrando desempenho superior sob observações incompletas e desalinhadas em comparação com métodos baseados em vetores de última geração.

4. Resultados Experimentais

Os autores validam o arcabouço usando dois conjuntos de dados:

• Dados de COVID-19 (Aprendizado de Filtro): Usando contagens diárias de casos de 58 condados, os métodos GDS propostos (GDS-Cop e GDS-GMM) foram comparados contra filtragem de grafo por Mínimos Quadrados (LS), LS Regularizado e Correspondência de Covariância.
  • Robustez a Dados Ausentes: Sob uma taxa de ausência de 20% por nó, os métodos clássicos (GSP-LS, GSP-RLS) degradaram significativamente. Os métodos GDS permaneceram robustos porque modelam distribuições em vez de exigir vetores completos.
  • Robustez ao Embaralhamento: Quando os dados de treinamento foram embaralhados temporalmente, os métodos clássicos que dependem de alinhamento temporal estrito falharam. Os métodos GDS permaneceram estáveis, pois aprendem a partir de propriedades distributivas em vez de pares de amostras específicos.
  • Tamanho da Janela: Os métodos GDS superaram os baselines para janelas de tempo maiores, onde amostras suficientes existem para estimativa de distribuição. No entanto, para janelas muito pequenas (2-4 dias), os métodos GDS tiveram desempenho inferior devido à dificuldade de estimar distribuições precisamente a partir de poucas amostras.
• Dados de ECoG Cerebral (Detecção de Anomalias): Usando dados pré-ictal (normais) e ictal (anormais) de convulsões, os detectores de anomalias baseados em GDS (usando distâncias de Localização de Pico e Mistura-Wasserstein) foram comparados contra baselines de GFT, Variação Total (TV) e Autoencoder Variacional (ELBO).
  • Desempenho: Os métodos GDS alcançaram a maior precisão em todos os tamanhos de lote de teste.
  • Eficiência de Amostra: Os métodos GDS mantiveram alta precisão mesmo com pequenos tamanhos de lote, enquanto os baselines pontuais (GSP-GFT) estagnaram em baixa precisão, e outros (GSP-TV, ELBO) exigiram significativamente mais amostras para se aproximar do desempenho de GDS.

5. Significância e Alegações

O artigo afirma que o arcabouço GDS oferece uma abordagem fundamentada para lidar com a incerteza e a estocasticidade tanto em sinais de grafo quanto em topologias. Ao mudar de espaços vetoriais para espaços de Wasserstein, o arcabouço:

• Relaxa os Requisitos de Dados: Elimina a necessidade de observações completas e síncronas e de alinhamento temporal estrito, tornando-o adequado para cenários do mundo real com dados ausentes ou irregulares.
• Captura Estruturas Mais Ricas: Codifica a incerteza na topologia do grafo e nas correlações de sinal diretamente na representação do sinal, em vez de tratar isso como ruído ou exigir suposições fixas.
• Generaliza a Teoria Existente: Abrange estritamente o GSP clássico como um caso especial (medidas de Dirac), garantindo compatibilidade reversa enquanto expande as capacidades.

Os autores observam que essa flexibilidade vem com um compromisso: o arcabouço requer dados suficientes para estimar com precisão as distribuições subjacentes. Em regimes de poucas amostras, métodos clássicos baseados em vetores podem continuar sendo preferíveis. No entanto, para aplicações envolvendo ausência substancial de dados, variabilidade de amostragem ou estruturas dependentes do sinal, o arcabouço GDS fornece uma alternativa mais flexível e robusta.