MSGNN: A Spectral Graph Neural Network Based on a Novel Magnetic Signed Laplacian

Resumo Técnico: MSGNN: Uma Rede Neural de Grafos Espectral Baseada em um Novo Laplaciano Assinado Magnético

Formulação do Problema
Redes assinadas e direcionadas são prevalentes em aplicações do mundo real, modelando fenômenos como inimizade/amizade social, fluxos de influência e relações de defasagem (lead-lag) financeiras. Embora as Redes Neurais de Grafos (GNNs) tenham alcançado um desempenho de estado da arte em grafos não assinados e não direcionados, há uma escassez relativa de GNNs espectrais projetadas para grafos onde as arestas possuem tanto um sinal (positivo/negativo) quanto uma direção. Métodos espaciais existentes (ex: SDGNN, SiGAT) existem, mas as abordagens espectrais enfrentam um desafio principal: definir um Laplaciano de grafo adequado que seja semidefinido positivo, possua um espectro limitado e, simultaneamente, codifique tanto os sinais quanto as direções das arestas.

Metodologia
Os autores propõem a MSGNN (Rede Neural de Grafo Assinado Magnético), uma arquitetura espectral construída sobre uma matriz inovadora chamada Laplaciano Assinado Magnético.

1. Laplaciano Assinado Magnético ($L^{(q)}$):
   A inovação central é a construção de uma matriz Hermitiana, semidefinida positiva, que unifica o Laplaciano assinado (para grafos assinados não direcionados) e o Laplaciano magnético (para grafos direcionados não assinados).

   • Construção: Os autores definem uma matriz de adjacência simetrizada $\tilde{A}$ e uma matriz de grau absoluto $\tilde{D}$. Para capturar a direcionalidade, eles introduzem uma matriz de fase $\Theta^{(q)}$ baseada em um "parâmetro de carga" $q$, onde $\Theta^{(q)}_{i,j} = 2\pi q (A_{i,j} - A_{j,i})$.
   • Representação Complexa: Uma matriz Hermitiana complexa $H^{(q)}$ é formada multiplicando elemento a elemento $\tilde{A}$ por $\exp(i\Theta^{(q)})$. O Laplaciano magnético assinado não normalizado é definido como $L^{(q)}_U = \tilde{D} - H^{(q)}$, e a versão normalizada é $L^{(q)}_N = I - \tilde{D}^{-1/2} H^{(q)} \tilde{D}^{-1/2}$.
   • Propriedades: Os autores provam que $L^{(q)}_N$ é semidefinido positivo com autovalores no intervalo $[0, 2]$. Quando o grafo é puramente direcionado (não assinado) ou puramente assinado (não direcionado), esta matriz reduz-se aos Laplacianos magnéticos ou assinados existentes, respectivamente.

2. Convolução Espectral:
   A MSGNN utiliza convolução espectral via decomposição de autovalores de $L^{(q)}_N$. Para evitar o custo computacional da decomposição completa de autovalores e reduzir o overfitting, o filtro espectral é aproximado usando polinômios de Chebyshev do Laplaciano normalizado. Isso permite que a convolução seja implementada no domínio espacial como um polinômio da matriz Laplaciana.

3. Arquitetura da Rede:
   A arquitetura MSGNN emprega ativações de valores complexos (uma versão complexa do ReLU) e processa as características dos nós através de múltiplas camadas convolucionais. Para agrupamento de nós (clustering), a representação complexa final é desenrolada em valores reais e passada por uma camada totalmente conectada com softmax. Para predição de links, as representações dos pares de nós são concatenadas antes da camada de classificação final.

Principais Contribuições

1. Novo Laplaciano: A introdução do Laplaciano Assinado Magnético, que lida naturalmente com redes assinadas e direcionadas, sendo Hermitiano, semidefinido positivo e reduzindo-se aos Laplacianos padrão em casos limites.
2. Arquitetura MSGNN: A proposta de uma GNN espectral eficiente baseada neste Laplaciano. Tanto quanto os autores sabem, este é o primeiro trabalho a avaliar GNNs em tarefas que exigem a extração simultânea de sinal e direcionalidade das arestas.
3. Dados Sintéticos e do Mundo Real:
   • SDSBM: Os autores introduzem o Modelo de Bloco Estocástico Direcionado Assinado (Signed Directed Stochastic Block Model), um modelo sintético que generaliza tanto o Modelo de Bloco Estocástico Assinado quanto o Modelo de Bloco Estocástico Direcionado, permitindo a geração de redes com metaestruturas específicas impulsionadas tanto pelo sinal quanto pelo fluxo.
   • Datasets Financeiros: Uma nova coleção de redes assinadas e direcionadas do mundo real derivadas de relações de defasagem (lead-lag) em séries temporais financeiras (2000–2020), especificamente construídas a partir de retornos de preços de ações.

Resultos Experimentais
Os autores conduziram experimentos extensivos em tarefas de agrupamento de nós e predição de links em datasets sintéticos (SSBM, POL-SSBM, SDSBM) e do mundo real (BitCoin-Alpha, BitCoin-OTC, Slashdot, Epinions e os novos datasets financeiros FiLL).

• Desempenho: A MSGNN alcançou o desempenho de liderança (maior acurácia) em todas as 25 variações de predição de link testadas, incluindo tarefas que priorizam o sinal, a direção ou ambos (problemas de predição de 3, 4 e 5 classes). No agrupamento de nós, a MSGNN superou o método espectral concorrente SigMaNet em todos os datasets e foi competitiva com o método espacial SSSNET.
• Eficiência: A MSGNN foi geralmente o método mais rápido entre os baselines, particularmente em grafos grandes, superando métodos baseados em atenção como SNEA e métodos de contagem de motivos como SDGNN.
• Ablação: O estudo confirmou que incorporar informações direcionais (definindo $q \neq 0$) geralmente melhora o desempenho em tarefas relacionadas à direção. Além disso, construir características baseadas em subgrafos positivos e negativos separados provou ser benéfico.

Significância e Alegações
O artigo afirma que a MSGNN incorpora efetivamente tanto a informação de sinal quanto a de direção, atingindo desempenho de estado da arte em uma ampla gama de datasets enquanto mantém a eficiência computacional. Os autores posicionam seu trabalho como um passo significativo para o aprendizado de grafos espectrais para estruturas de redes complexas, observando que abordagens espectrais anteriores estavam amplamente restritas a grafos não assinados ou não direcionados. Eles enfatizam a utilidade de seu novo modelo sintético (SDSBM) e dos datasets financeiros para pesquisas futuras neste domínio. O trabalho não pretende resolver todos os problemas de aprendizado de grafos, mas aborda especificamente a lacuna nos métodos espectrais para grafos assinados e direcionados.