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

Resumen Técnico: MSGNN: Una Red Neuronal de Grafos Espectral Basada en un Nuevo Laplaciano Magnético con Signo

Formulación del Problema
Las redes con signo y dirección son prevalentes en aplicaciones del mundo real, modelando fenómenos como la enemistad/amistad social, los flios de influencia y las relaciones de adelanto-retraso (lead-lag) financieras. Aunque las Redes Neuronales de Grafos (GNN) han logrado un rendimiento de vanguardia en grafos sin signo y no dirigidos, existe una escasez relativa de GNN espectrales diseñadas para grafos donde las aristas poseen tanto un signo (positivo/negativo) como una dirección. Existen métodos espaciales actuales (p. ej., SDGNN, SiGAT), pero los enfoques espectrales enfrentan un desafío principal: definir un Laplaciano de grafo adecuado que sea semidefinido positivo, tenga un espectro acotado y, simultáneamente, codifique tanto los signos como las direcciones de las aristas.

Metodología
Los autores proponen MSGNN (Red Neuronal de Grafos Magnética con Signo), una arquitectura espectral construida sobre una matriz novedosa llamada Laplaciano Magnético con Signo.

1. Laplaciano Magnético con Signo ($L^{(q)}$):
   La innovación central es la construcción de una matriz hermítica, semidefinida positiva que unifica el Laplaciano con signo (para grafos con signo no dirigidos) y el Laplaciano magnético (para grafos dirigidos sin signo).

   • Construcción: Los autores definen una matriz de adyacencia simetrizada $\tilde{A}$ y una matriz de grado absoluto $\tilde{D}$. Para capturar la direccionalidad, introducen una matriz de fase $\Theta^{(q)}$ basada en un "parámetro de carga" $q$, donde $\Theta^{(q)}_{i,j} = 2\pi q (A_{i,j} - A_{j,i})$.
   • Representación Compleja: Se forma una matriz hermítica compleja $H^{(q)}$ mediante la multiplicación elemento a elemento de $\tilde{A}$ con $\exp(i\Theta^{(q)})$. El Laplaciano magnético con signo no normalizado se define como $L^{(q)}_U = \tilde{D} - H^{(q)}$, y la versión normalizada como $L^{(q)}_N = I - \tilde{D}^{-1/2} H^{(q)} \tilde{D}^{-1/2}$.
   • Propiedades: Los autores demuestran que $L^{(q)}_N$ es semidefinido positivo con autovalores en el intervalo $[0, 2]$. Cuando el grafo es puramente dirigido (sin signo) o puramente con signo (no dirigido), esta matriz se reduce a los Laplacianos magnéticos o con signo existentes, respectivamente.

2. Convolución Espectral:
   MSGNN utiliza la convolución espectral mediante la descomposición en autovectores de $L^{(q)}_N$. Para evitar el gasto computacional de la descomposición completa en autovalores y reducir el sobreajuste, el filtro espectral se aproxima utilizando polinomios de Chebyshev de el Laplaciano normalizado. Esto permite que la convolución se implemente en el dominio espacial como un polinomio de la matriz Laplaciana.

3. Arquitectura de la Red:
   La arquitectura MSGNN emplea activaciones de valor complejo (una versión compleja de ReLU) y procesa las características de los nodos a través de múltiples capas convolucionales. Para el agrupamiento (clustering) de nodos, la representación compleja final se desenrolla en valores reales y se pasa a través de una capa totalmente conectada con softmax. Para la predicción de enlaces, las representaciones de pares de nodos se concatenan antes de la capa de clasificación final.

Contribuciones Clave

1. Nuevo Laplaciano: La introducción del Laplaciano Magnético con Signo, que maneja naturalmente redes con signo y dirección, es hermítica, semidefinida positiva y se reduce a Laplacianos estándar en casos límite.
2. Arquitectura MSGNN: La propuesta de una GNN espectral eficiente basada en este Laplaciano. Hasta el conocimiento de los autores, este es el primer trabajo que evalúa GNN en tareas que requieren la extracción simultánea de tanto el signo como la direccionalidad de las aristas.
3. Datos Sintéticos y del Mundo Real:
   • SDSBM: Los autores introducen el Modelo de Bloque Estocástico Dirigido con Signo (Signed Directed Stochastic Block Model), un modelo sintético que generaliza tanto al Modelo de Bloque Estocástico con Signo como al Modelo de Bloque Estocástico Dirigido, permitiendo la generación de redes con metaestructuras específicas impulsadas tanto por el signo como por el flujo.
   • Conjuntos de Datos Financieros: Una nueva colección de redes con signo y dirección derivadas de relaciones de adelanto-retraso (lead-lag) en series temporales financieras (2000–2020), construidas específicamente a partir de retornos de precios de acciones.

Resultados Experimentales
Los autores realizaron experimentos extensos en tareas de agrupación de nodos y predicción de enlaces en conjuntos de datos sintéticos (SSBM, POL-SSB, SDSBM) y del mundo real (BitCoin-Alpha, BitCoin-OTC, Slashdot, Epinions y los nuevos conjuntos de datos financieros FiLL).

• Rendimiento: MSGNN alcanzó un rendimiento de vanguardia (la precisión más alta) en las 25 variaciones de predicción de enlaces probadas, incluyendo tareas que priorizan el signo, la dirección o ambos (problemas de predicción de 3, 4 y 5 clases). En la agrupación de nodos, MSGNN superó al método espectral concurrente SigMaNet en todos los conjuntos de datos y fue competitivo con el método espacial SSSNET.
• Eficiencia: MSGNN fue generalmente el método más rápido entre los modelos de referencia (baselines), particularmente en grafos grandes, superando a los métodos basados en atención como SNEA y a los métodos de conteo de motivos como SDGNN.
• Ablación: El estudio confirmó que incorporar información direccional (estableciendo $q \neq 0$) generalmente mejora el rendimiento en tareas relacionadas con la dirección. Además, construir características basadas en subgrafos positivos y negativos separados resultó beneficioso.

Significancia y Reivindicaciones
El artículo afirma que MSGNN incorpora eficazmente tanto la información de signo como la de dirección, alcanzando un rendimiento de vanguardia en una amplia gama de conjuntos de datos manteniendo la eficiencia computacional. Los autores posicionan su trabajo como un paso significativo hacia adelante en el aprendizaje de grafos espectrales para estructuras de redes complejas, señalando que los enfoques espectrales previos estaban mayormente restringidos a grafos sin signo o no dirigidos. Enfatizan la utilidad de su nuevo modelo sintético (SDSBM) y de los conjuntos de datos financieros para la investigación futura en este dominio. El trabajo no pretende resolver todos los problemas de aprendizaje de grafos, sino que aborda específicamente la brecha en los métodos espectrales para grafos dirigidos con signo.