Clustering Node Attributed Networks with Graph Neural Networks and Self Learning

Resumen Técnico: Agrupamiento de Redes de Nodos con Atributos mediante Redes Neuronales de Grafos y Autoaprendizaje

Formulación del Problema
El artículo aborda el problema del agrupamiento (clustering) de nodos en redes con atributos, donde cada nodo posee tanto conexiones topológicas (aristas) como atributos de características. El objetivo es particionar el conjunto de nodos en subconjets disjuntos (comunidades) que reflejen estructuras latentes mediante el aprovechamiento conjunto de la topología de la red y los atributos de los nodos. Crucialmente, este trabajo opera en un entorno totalmente no supervisado, lo que significa que no hay etiquetas de clústeres de verdad fundamental (ground-truth) disponibles durante el entrenamiento; las únicas entradas son la estructura del grafo, los atributos de los nodos y el número objetivo de clústeres ($K$). Los autores señalan que, si bien el agrupamiento conjunto es intuitivamente superior al uso exclusivo de la topología o de los atributos, diseñar algoritmos que fusionen eficazmente estas señales —especialmente cuando una de las fuentes es ruidosa— no es una tarea trivial.

Metodología: DCSL-GNN
Los autores proponen la Red Neuronal de Grafos de Autoaprendizaje de Contexto Dinámico (DCSL-GNN), un marco que opera en rondas iterativas para refinar las representaciones de los nodos y las asignaciones de clústeres. El marco consta de tres módulos interconectados:

1. Generación de Contexto Dinámico:

   • Las Redes Neuronales de Grafos (GNN) estándar suelen sufrir de "alcance insuficiente" (profundidad insuficiente para capturar centros de clústeres distantes) o "sobre-suavizado" (pérdida de distintividad con demasiadas capas). Para mitigar esto, DCSL-GNN construye un Grafo de Contexto ($G_c$) para cada ronda, el cual difiere del grafo original.
   • Aristas Virtuales: El grafo de contexto introduce "aristas virtuales" que conectan los nodos con los vecinos más cercanos del centro de masa de su clúster (en el espacio de representación). Esto permite que la información de los centros de los clústeres se propague directamente, evitando la necesidad de capas de GNN profundas.
   • Caminatas Aleatorias: El grafo de contexto se genera mediante caminatas aleatorias sesgadas. En cada paso, la caminata sigue una arista original (ponderada por la similitud de las representaciones de los nodos de la ronda anterior) o salta mediante una arista virtual a un nodo cercano a un centro de clúster.
   • Vecindarios Basados en la Importancia: El vecindario de un nodo en $G_c$ se determina mediante los conteos de visitas de las caminatas aleatorias que parten de ese nodo, utilizando un umbral basado en el percentil $k$ de la distribución de visitas. Esto asegura que los nodos más influyentes (incluso si están distantes en el grafo original) se conviertan en vecinos directos en el grafo de contexto.

2. Incrustación (Codificador GNN):

   • Un codificador GCN estándar procesa el grafo de contexto $G_c$ y los atributos de los nodos para generar incrustaciones (embeddings) de nodos.
   • Pesos de las Aristas: Las aristas en $G_c$ se ponderan dinámicamente. Si los atributos de los nodos conectados son altamente similares (verificado por un umbral de coeficiente de silueta $\beta$), el peso de la arista es inversamente proporcional a la distancia euclidiana entre sus atributos. De lo contrario, el peso permanece neutral (1).
   • Entrenamiento: Los parámetros de la GNN se entrenan utilizando una función de pérdida de triplete (triplet loss). Esta pérdida minimiza la distancia entre un nodo ancla y las muestras positivas (nodos en el mismo clúster) mientras maximiza la distancia hacia las muestras negativas (nodos en diferentes clústeres).
   • Persistencia de Parámetros: A diferencia del entrenamiento estándar, los pesos de la GNN aprendidos en la ronda $r$ se inicializan con los valores de la ronda $r-1$, lo que permite al modelo refinar su comprensión a lo largo del tiempo sin tener que reentrenar desde cero.

3. Bucle de Agrupamiento y Autoaprendizaje:

   • Las incrustaciones generadas se introducen en un algoritmo K-means estándar para producir las asignaciones de clústeres.
   • Estas nuevas asignaciones de clústeres se utilizan luego para actualizar los centros de los clústeres y los sesgos de las caminatas aleatorias para la siguiente ronda.
   • Esto crea un mecanismo de autorrefuerzo: mejores representaciones conducen a mejores clústeres, los cuales a su vez generan mejores grafos de contexto y representaciones para la ronda subsecuente.

Contribuciones Clave

• Marco Novedoso: La introducción de DCSL-GNN, un marco totalmente no supervisado que refina iterativamente las representaciones de los nodos a través de un bucle de autoaprendizaje.
• Grafo de Contexto Dinámico: Un mecanismo para construir un grafo de contexto que combina la topología original con aristas virtuales hacia los centros de los clústeres, abordando eficazmente las limitaciones de profundidad de las GNN sin requerir capas excesivas.
• Mecanismo de Autoaprendizaje: Un proceso iterativo donde los resultados del agrupamiento de una ronda influyen directamente en la estructura del grafo (contexto) y los pesos de las aristas de la siguiente ronda, permitiendo al modelo denotar el ruido y alinear progresivamente la topología con los atributos.
• Robustez al Ruido: La metodología está diseñada para aprovechar la fuente de información más fiable (ya sea la topología o los atributos) para corregir la fuente más ruidosa.

Resultados Experimentales
Los autores evaluaron DCSL-GNN en datos sintéticos (Modelos de Bloques Estocásticos Atribuidos) y tres conjuntos de datos de referencia del mundo real (Cora, Citeseer, PubMed).

• Datos Sintéticos:

  • Eficacia del Autoaprendizaje: Múltiples rondas de autoaprendizaje superaron consistentemente a una única ronda larga de entrenamiento (equivalente al agrupamiento clásico de GNN).
  • Manejo de Ruido: El marco extrajo con éxito información de la fuente fiable cuando la otra era ruidosa. Por ejemplo, cuando la información de la red era muy ruidosa ($p_I=0.2$) pero los atributos eran limpios, el rendimiento mejoró a lo largo de las rondas. Inversamente, cuando los atributos eran ruidosos pero la red era limpia, el modelo también convergió bien. Sin embargo, cuando ambas fuentes eran altamente ruidosas, el rendimiento degradó hasta el azar, como era de esperar.
  • Comparación: DCSL-GNN superó a los algoritmos que dependen únicamente de la estructura de la red (Louvain) o únicamente de los atributos (K-means) en escenarios donde ninguna fuente era perfectamente informativa.

• Conjuntos de Datos Reales:

  • Citeseer: DCSL-GNN alcanzó la mayor Información Mutua Normalizada (NMI) entre todos los métodos de vanguardia comparados.
  • Cora y PubMed: El modelo se desempeñó de manera competitiva pero no superó al estado del arte (MGCCN para Cora, SEComm para PubMed).
  • Limitación: Los autores atribuyen el menor rendimiento en Cora y PubMed en parte al desequilibrio de clústeres. El modelo mostró una alta precisión para los clústeres dominantes pero una precisión insignificante para los clústeres más pequeños, lo que sugiere un sesgo hacia los grupos más grandes en la función objetivo.

Significancia y Reivindicaciones
El artículo afirma que DCSL-GNN ofrece un enfoque flexible para el agrupamiento de grafos con atributos que fusiona eficazmente la información estructural y de atributos sin supervisión. Los autores enfatizan que el autoaprendizaje de múltiples rondas es un componente crítico, ya que permite al modelo refinar iterativamente el "contexto" en el que se ven los nodos, lo que conduce a un agrupamiento superior en comparación con los enfoques de una sola ronda.

Los autores concluyen modestamente que, si bien el método es altamente efectivo en escenarios con clústeres equilibrados o niveles de ruido mixtos (como se demostró en Citeseer y datos sintéticos), enfrenta desafíos con conjuntos de datos del mundo real altamente desequilibrados. Afirman que el marco demuestra el potencial de los mecanismos de autoaprendizaje para mejorar las representaciones de los nodos y la calidad del agrupamiento en ausencia de datos etiquetados, aunque no pretende ser una solución universal superior a todos los métodos existentes a través de todas las características de los conjuntos de datos.