Learning Product Graphs from Two-dimensional Stationary Signals

Resumo Técnico: Aprendizado de Grafos de Produtos a partir de Sinais Estacionários Bidimensionais

Enunciado do Problema
As estruturas tradicionais de aprendizado de grafos tipicamente inferem estruturas de rede a partir de sinais escalares observados nos nós, tratando múltiplas realizações (por exemplo, amostras temporais, repetições experimentais ou dados populacionais) como uma única dimensão. Essa abordagem frequentemente ignora as dependências estruturadas existentes nessas dimensões adicionais. Em muitas aplicações, como processos espaço-temporais ou sistemas de recomendação, os dados são naturalmente representados como sinais bidimensionais indexados tanto pelo nó (entidades) quanto por uma dimensão de realização (tempo, usuários ou experimentos). Tratar esses dados como uma única dimensão vetorizada leva a problemas de escalabilidade devido ao crescimento quadrático no número de incógnitas ($P^2Q^2$ para $P \times Q$ nós) e à dificuldade de estimar com precisão matrizes de covariância de alta dimensão a partir de amostras limitadas. Embora métodos recentes tentem modelar essas dependências usando grafos de produtos (por exemplo, produtos de Kronecker ou Cartesianos), as abordagens existentes frequentemente dependem de otimização não convexa ou ainda exigem a estimativa de grandes matrizes de covariância de dimensão completa.

Metodologia
Os autores propõem um framework de Processamento de Sinais em Grafos (GSP) que modela sinais bidimensionais como saídas de um processo de filtragem conjunta atuando sobre ruído gaussiano branco. A suposição central é que o sinal matricial observado $Y \in \mathbb{R}^{P \times Q}$ é gerado por:
$$Y = H_P(S_P) W H_Q(S_Q)$$
onde $S_P$ e $S_Q$ são os Operadores de Deslocamento de Grafo (GSOs) para as duas dimensões, $H_P$ e $H_Q$ são filtros polinomiais em grafos, e $W$ é uma matriz de ruído com entradas i.i.d.

Com base nesse modelo, o artigo deriva três formulações distintas para o problema de aprendizado de grafos:

1. Modelo Vetorizado Geral: Trata o sinal $P \times Q$ como um único vetor e aprende um GSO não estruturado. Isso é computacionalmente proibitivo devido à complexidade $O((PQ)^2)$.
2. Modelo de Grafo de Produto Estruturado: Assume que o grafo subjacente é um produto (Kronecker, Cartesiano ou forte) de dois grafos. Isso reduz as variáveis para $P^2 + Q^2$, mas introduz uma restrição não convexa envolvendo o produto de Kronecker, tipicamente exigindo otimização alternada sem garantia de recuperação.
3. Formulação de Covariância por Dimensão (Proposta): Aproveitando o modelo específico de geração de sinais, os autores mostram que as matrizes de covariância marginais $C_P = E[YY^\top]$ e $C_Q = E[Y^\top Y]$ são polinômios em $S_P$ e $S_Q$, respectivamente. Isso permite que o problema de aprendizado seja desacoplado em dois problemas de otimização convexa separados:
   $$\min_{S_P, S_Q} \|S_P\|_1 + \beta\|S_Q\|_1 \quad \text{s.t.} \quad C_P S_P = S_P C_P, \quad C_Q S_Q = S_Q C_Q$$
   Essa formulação evita a estimativa da matriz de covariância completa $PQ \times PQ$, reduzindo significativamente o custo computacional e a complexidade de amostragem, mantendo a estrutura do grafo de produtos.

Principais Contribuições

• Extensão da Estacionariedade: O trabalho estende o conceito de estacionariedade em grafos para sinais bidimensionais, modelando-os como o resultado de filtragem conjunta ao longo de dimensões independentes.
• Otimização Tratável: Ao explorar a estrutura das covariâncias por dimensão, os autores reformulam a tarefa de identificação de topologia em dois problemas convexos separáveis e de baixa dimensão. Isso contorna a não convexidade e a alta dimensionalidade associadas aos métodos anteriores de aprendizado de grafos de produtos.
• Garantias Teóricas: A formulação proposta permite a recuperação provável dos grafos de produtos de Kronecker, Cartesianos ou fortes ótimos subjacentes sob o modelo de sinal declarado.

Resultados Experimentais
Os autores avaliam seu método (especificamente a variante "Separate Kronecker-ST" ou SepK-ST) contra modelos espectrais (ST), Kronecker-ST (K-ST), DNNLasso e TERRALasso usando dados sintéticos.

• Precisão vs. Complexidade: O SepK-ST alcança uma precisão de recuperação comparável à do K-ST, mas com tempo de execução significativamente menor. Diferentemente do método ST não estruturado, que falha em capturar a estrutura subjacente e escala mal, o SepK-ST aproveita efetivamente a estrutura 2D.
• Eficiência de Amostragem: Em regimes com um número limitado de realizações de sinal ($R$), o SepK-ST supera tanto o ST quanto o K-ST. Como opera em matrizes de covariância menores $P \times P$ e $Q \times Q$ em vez da matriz completa $PQ \times PQ$, requer menos amostras para alcançar estimativas confiáveis e melhor estacionariedade (comutatividade).
• Robustez a Modelos de Sinal: Quando testado contra sinais gerados a partir de diferentes modelos (Campos Aleatórios de Markov versus filtros Polinomiais), o SepK-ST recupera consistentemente a estrutura do grafo. Em contraste, o DNNLasso e o TERRALasso mostram degradação de desempenho quando o modelo de geração de sinal se desvia de suas suposições específicas.

Significância
O artigo afirma que sua principal contribuição é fornecer um framework que equilibra precisão de estimação e eficiência computacional para o aprendizado de grafos a partir de sinais estacionários bidimensionais. Ao desacoplar o problema de aprendizado em otimizações convexas específicas por dimensão, a abordagem oferece uma alternativa escalável aos métodos existentes que lutam com a maldição da dimensionalidade ou restrições não convexas. Os resultados sugerem que modelar explicitamente a estrutura de produtos e o processo de filtragem através das dimensões é essencial para inferência precisa em cenários onde existem dependências entre múltiplas modalidades.