Resumen Técnico: Red Neuronal de Grafos que aprovecha la Conectividad de Etiquetas de Clase de Orden Superior para Grafos Heterófilos

Planteamiento del Problema

La clasificación de nodos en Redes Neuronales de Grafos (GNN) ha alcanzado una alta precisión en grafos homófilos, donde los nodos con etiquetas de clase similares tienden a conectarse. Sin embargo, el rendimiento disminuye significativamente en grafos heterófilos, donde los nodos con diferentes etiquetas de clase tienen más probabilidades de estar conectados.

Los autores identifican una limitación específica en las GNN actuales (incluyendo aquellas derivadas de Redes Neuronales Convolucionales de Grafos como GCN, GAT y modelos avanzados para heterofilia como H2GCN y LINKX): estas transforman el problema de la clasificación de nodos en un simple mapeo del espacio de incrustaciones (embeddings) al espacio de etiquetas de clase. En consecuencia, estos modelos no logran capturar la conectividad de etiquetas de clase de orden superior —las relaciones estructurales entre etiquetas de clase que abarcan múltiples saltos a través de aristas dirigidas. Si bien algunos métodos utilizan una matriz de compatibilidad de clases para capturar la conectividad de primer orden, no tienen en cuenta las complejas interacciones de etiquetas de múltiples saltos que se observan frecuentemente en grafos dirigidos del mundo real (por ejemplo, el conjunto de datos Texas, donde los nodos "Student" se conectan con nodos "Department", que a su vez se conectan con nodos "Staff").

Metodología

El enfoque propuesto introduce un clasificador novedoso, el Clasificador de Contexto de Etiquetas (LCC), y un marco para integrarlo con las GNN existentes.

1. Clasificador de Contexto de Etiquetas (LCC)

El LCC está diseñado para capturar la conectividad de etiquetas de clase de orden superior tratando las secuencias de etiquetas de clase a lo largo de caminatas en el grafo como contexto, inspirado en el modelo Skip-gram de word2vec. El proceso involucra tres pasos principales:

• Extracción de Caminatas de Etiquetas: A partir de un nodo objetivo, se extraen cuatro tipos distintos de caminatas de etiquetas. Una caminata de etiquetas es una secuencia de etiquetas de clase donde los nodos son reemplazados por sus etiquetas. Si un nodo no está en el conjunto de entrenamiento, se utiliza una etiqueta nula.
  • Caminata hacia Adelante (Forward Walk): Una búsqueda en profundidad siguiendo la dirección de las aristas (Objetivo $\to$ Hijo $\to$ Nieto).
  • Caminata hacia Atrás (Backward Walk): Una búsqueda en profundidad siguiendo la dirección inversa de las aristas (Objetivo $\to$ Padre $\to$ Abuelo).
  • Caminata de Hermanos (Sibling Walk): Atraviesa hacia atrás hacia un nodo padre y luego hacia adelante hacia sus otros hijos (Objetso $\to$ Padre $\to$ Hermano). Esto captura la conectividad entre nodos que comparten un padre común.
  • Caminata de Guardián (Guardian Walk): Atraviesa hacia adelante hacia un nodo hijo y luego hacia atrás hacia sus otros padres (Objetivo $\to$ Hijo $\to$ Co-padre). Esto captura la conectividad entre nodos que comparten un hijo común.
• Generación de Incrustaciones de Contexto de Etiquetas: Utilizando las caminatas de etiquetas extraídas, el modelo aprende incrustaciones que representan el "contexto de la etiqueta". Un MLP (Perceptrón Multicapa) simple de dos capas se entrena para predecir las etiquetas de contexto (las etiquetas subsecuentes en la caminata) dado el input de la etiqueta del nodo objetivo. La capa oculta produce las incrustaciones de contexto de etiqueta ($Z$).
• Entrenamiento del Clasificador: El clasificador LCC final es un MLP entrenado sobre la concatenación de las características originales del nodo y las incrustaciones de contexto de etiqueta derivadas de los cuatro tipos de caminata.

2. Integración con GNNs

Para aprovechar las fortalezas tanto de las GNN tradicionales (que capturan información de características y estructura local) como del LCC (que captura la conectividad de etiquetas de orden superior), los autores proponen un esquema de integración adaptativo:

• Entrenamiento Independiente: Tanto la GNN como el LCC se entrenan de forma independiente en el conjunto de entrenamiento.
• Ponderación Adaptativa: La importancia de cada modelo se determina mediante la pérdida de validación. Los pesos ($w_{LCC}$ y $w_{GNN}$) se calculan como el recíproco de la pérdida de validación, ajustados por un parámetro de temperatura ($T$).
• Predicción de Ensamble: La predicción final es un promedio ponderado de las salidas de la GNN y del LCC. Esta integración no requiere el entrenamiento de modelos adicionales, solo el cálculo de los pesos basados en el rendimiento de validación.

Contribuciones Clave

1. Propuesta de LCC: Un clasificador novedoso que estima las etiquetas de los nodos capturando la conectividad de etiquetas de clase de orden superior a través de cuatro caminatas de etiquetas sensibles a la dirección (Adelante, Atrás, Hermano, Guardián).
2. Marco de Integración Adaptativa: Un método para integrar el LCC con cualquier GNN existente mediante la adaptación de pesos de importancia basados en la pérdida de validación, sin requerir costos de entrenamiento adicionales.
3. Validación Empírica: Resultados experimentales que demuestran que la integración del LCC con las GNN supera a los métodos del estado del arte (SOTA) en grafos dirigidos heterófilos.

Resultados Experimentales

Los autores evaluaron su método en siete conjuntos de datos de grafos dirigidos heterófilos: Cornell, Texas, Wisconsin, Chameleon, Squirrel, Roman-Empire y Amazon-Ratings.

• Mejora del Rendimiento: Los modelos integrados (por ejemplo, H2GCN+LCC, LINKX+LCC, GloGNN+LCC) lograron la mayor precisión de clasificación de nodos en todos los conjuntos de datos en comparación con las GNN independientes, los MLP y el LCC por sí solo.
• Complementariedad: Los resultados indican que el LCC y las GNN capturan propiedades de grafos diferentes. En la mayoría de los casos, la integración mejoró la precisión respecto a los componentes individuales.
• Efectividad de las Caminatas de Etiquetas: El LCC superó significativamente a un MLP vanilla (que utiliza solo las características del nodo), confirmando que las incrustaciones de contexto de etiqueta capturan eficazmente la conectividad de las etiquetas de clase. Notablemente, las ganancias de precisión superaron el 10% en conjuntos de datos como Chameleon, Squirrel, Roman-Empire y Amazon-Ratings.
• Importancia del Tipo de Caminata: La importancia de tipos de caminata específicos varió según el conjunto de datos. Por ejemplo, las caminatas de Guardián fueron más críticas para Chameleon, Squirrel y Amazon-Ratings, mientras que las caminatas de Hermanos fueron más efectivas para Roman-Empire.
• Longitud de la Caminata: Aumentar la longitud de la caminata (para las caminatas hacia adelante/atrás) o utilizar caminatas de 2 saltos (hermano/guardián) generalmente mejoró el rendimiento, resaltando la necesidad de capturar la conectividad de orden superior.

Significado y Reivindicaciones

El artículo afirma que la debilidad principal de las GNN actuales en entornos heterófilos es su incapacidad para modelar cómo se conectan las etiquetas de clase a través de múltiples saltos en grafos dirigidos. Al modelar explícitamente estas relaciones de orden superior mediante caminatas de etiquetas, el LCC proporciona una señal complementaria a las GNN basadas en características.

Los autores enfatizan que su enfoque no requiere cambios arquitectónicos complejos en las GNN existentes; más bien, ofrece un clasificador modular que puede combinarse de forma adaptativa con cualquier GNN para mejorar el rendimiento. Los resultados sugieren que aprovechar la información estructural entre las etiquetas de clase, en lugar de solo las características de los nodos o los vecinos inmediatos, es crucial para una clasificación precisa en grafos dirigidos heterófilos. Este trabajo cuenta con el apoyo de las subvenciones JSPS KAKENHI y JST ASPIRE.