Random Wavelet Features for Graph Kernel Machines

Resumo Técnico: Random Wavelet Features for Graph Kernel Machines

1. Problema e Motivação

O artigo aborda o desafio de escalar máquinas de kernel para grandes redes (grafos).

• Contexto: Em aprendizado de máquina, kernels definem similaridades entre dados. Para grafos, os kernels (matrizes $N \times N$) capturam a estrutura relacional entre nós, sendo essenciais para tarefas como classificação de nós e reconstrução de sinais.
• O Desafio: O cálculo direto de matrizes de kernel baseadas no Laplaciano do grafo é proibitivo para redes grandes, com custo computacional de $O(N^3)$ devido à necessidade de decomposição espectral completa (autovalores e autovetores).
• Limitação de Métodos Existentes: Métodos de aproximação por características aleatórias (Random Features) existentes, como os baseados em passeios aleatórios (spatial random features), muitas vezes falham em capturar dependências de longo alcance ou têm convergência lenta para kernels que são localizados no domínio espectral (banda estreita), mas espalhados no domínio espacial.

2. Metodologia Proposta

Os autores propõem uma nova abordagem baseada em Processamento de Sinais em Grafos (GSP) e Transformada Wavelet em Grafos para criar embeddings de nós aleatórios que aproximam kernels de grafos de baixo posto.

A metodologia segue um procedimento de duas etapas (Algoritmo 1):

1. Busca de Faixa (Range Finding):

   • O objetivo é estimar o subespaço gerado pelos $K$ primeiros autovetores do Laplaciano ($V_{:K}$), que correspondem às frequências mais baixas (suaves) do grafo.
   • Em vez de calcular a decomposição espectral completa, o método filtra $K$ sinais aleatórios (Gaussianos) através de um filtro polinomial de baixa passagem $p_\chi(L)$, que aproxima um filtro ideal que seleciona apenas os autovalores menores que $\lambda_K$.
   • Os sinais filtrados são ortogonalizados (via Gram-Schmidt) para formar uma base $Q$ que aproxima o subespaço espectral desejado.
   • O autovalor de corte $\lambda_K$ é estimado dinamicamente usando um método de dicotomia com contagem de autovalores, sem necessidade de decomposição completa.

2. Aproximação do Kernel (Embedding):

   • Uma vez obtida a base $Q$, os autores constroem o mapa de características $\Phi$ aplicando a raiz quadrada do filtro do kernel ($h^{1/2}(L)$) sobre $Q$.
   • Na prática, o filtro $h^{1/2}$ também é aproximado por um polinômio $p_h(L)$ para permitir computação rápida via produtos matriz-vetor.
   • O produto escalar entre os vetores de embedding de dois nós $i$ e $j$ ($\langle \phi_i, \phi_j \rangle$) fornece uma aproximação de baixo posto ($\tilde{\Gamma}$) do kernel original $\Gamma = h(L)$.

Complexidade:

• O método evita a decomposição espectral explícita ($O(N^3)$).
• A complexidade de tempo é dominada por produtos matriz-vetor com o Laplaciano, resultando em $O(MEK + NK^2)$, onde $M$ é o grau do polinômio e $E$ é o número de arestas.
• A complexidade de memória é $O(NK)$.

3. Contribuições Principais

• Novo Método de Aproximação: Introdução de embeddings espectrais aleatórios baseados em wavelets para grafos, que estimam kernels baseados no Laplaciano.
• Superioridade para Kernels Localizados: Demonstração teórica e empírica de que o método supera métodos existentes (como g-GRFs) na aproximação de kernels espectralmente localizados (ex: kernels de difusão com largura de banda estreita).
• Conexão com Álgebra Linear Numérica: Estabelecimento de uma ligação clara entre o método proposto e a Decomposição em Valores Singulares Aleatória (RSVD), utilizando estratégias de oversampling para mitigar erros de aproximação.
• Análise de Erro Rigorosa: Derivação de limites teóricos para o erro de aproximação, separando o erro devido à aproximação polinomial do filtro e o erro devido à estimativa do subespaço (range finding).

4. Resultados Experimentais

Os experimentos foram realizados em grafos sintéticos (Swiss-Roll e Community) com até 5.000 nós.

• Precisão vs. Largura de Banda:
  • O método proposto é significativamente mais preciso que o método g-GRFs para kernels com baixa largura de banda espectral (alta localização espectral).
  • O método g-GRFs funciona melhor para kernels de banda larga (comportamento local espacial), enquanto o método proposto captura melhor as propriedades geométricas globais.
• Influência do Posto Alvo ($K$):
  • No grafo Swiss-Roll (autovalores distribuídos uniformemente), o método atinge erros próximos ao limite ótimo de posto-$K$ até $K \approx 1000$.
  • No grafo Community (autovalores agrupados em clusters), o desempenho degrada-se quando $K$ entra em regiões de alta densidade de autovalores, devido à dificuldade em estimar o corte espectral preciso ($\lambda_K$) e à contaminação de frequências indesejadas.
• Eficiência Computacional:
  • O tempo de execução escala linearmente com o número de nós ($O(N)$) para $K$ fixo, confirmando a análise teórica.
  • Para grafos grandes, o método é drasticamente mais rápido que a decomposição espectral completa, tornando viável o aprendizado baseado em kernels em larga escala.

5. Significado e Impacto

Este trabalho oferece uma ferramenta escalável e teoricamente fundamentada para aprendizado de representação em grafos. Ao permitir a aproximação eficiente de kernels espectrais localizados, o método viabiliza a aplicação de máquinas de vetores de suporte (SVMs) e outros algoritmos de kernel em redes massivas, onde métodos tradicionais falham devido ao custo computacional. A capacidade de capturar dependências de longo alcance (global) através de uma abordagem espectral aleatória preenche uma lacuna importante deixada por métodos baseados em passeios aleatórios locais.

Em suma, o artigo demonstra que a combinação de filtragem espectral aproximada (via polinômios de Chebyshev/Jackson) e busca de subespaço aleatório é uma estratégia poderosa para a representação de grafos em larga escala.