Community detection robustness of graph neural networks

Resumen Técnico: Robustez de la Detección de Comunidades en Redes Neuronales de Grafos

Enunciado del Problema
Las Redes Neuronales de Grafos (GNN) se han convertido en herramientas dominantes para la detección de comunidades en redes atribuidas, integrando eficazmente la topología estructural con los atributos de los nodos mediante el paso de mensajes y el agrupamiento (pooling). Sin embargo, la robustez de estos modelos frente a perturbaciones y ataques dirigidos dentro del contexto específico de la detección de comunidades sigue siendo poco comprendida. Si bien la robustez en las GNN ha sido estudiada extensamente para la clasificación de nodos, la estabilidad de la detección de comunidades basada en GNN bajo perturbaciones de grafos —tales como ruido, datos incompletos y manipulaciones adversarias— ha permanecido en gran medida inexplorada. Los estudios existentes sobre la robustez en la detección de comunidades se han centrado principalmente en algoritmos clásicos bajo adiciones o eliminaciones simples de aristas, a menudo descuidando las arquitecturas modernas de GNN y las fuentes complejas e interconectadas de perturbación presentes en escenarios del mundo real.

Metodología
Los autores realizan una evaluación computacional sistemática de seis arquitecturas de GNN ampliamente adoptadas, categorizadas en paradigmas supervisados y no supervisados:

• Supervisados: Redes de Convolución de Grafos (GCN), Redes de Atención de Grafos (GAT) y GraphSAGE.
• No supervisados: DiffPool, MinCUT y DMoN (que utiliza la maximización de la modularidad).

La evaluación abarca tres categorías distintas de perturbación:

1. Manipulaciones de Atributos de Nodos: Alteración de la ubicación (media) y la escala (varianza) de las distribuciones de atributos para crear superposiciones entre clústeres.
2. Distorsiones de la Topología de Aristas: Eliminaciones aleatorias de aristas (simulando fallos de red) y eliminaciones dirigidas de aristas basadas en la centralidad de intermediación (simulando ataques estructurales adversarios).
3. Ataques Adversarios: Utilización de Nettack y Metattack, que emplean modelos sustitutos y meta-aprendizaje para perturbar estratégicamente tanto la topología como los atributos, manteniendo al mismo tiempo las propiedades estadísticas del grafo original (por ejemplo, distribuciones de grado de ley de potencias).

Los experimentos se realizan en benchmarks sintéticos, específicamente en grafos Lancichinetti–Fortunato–Radicchi (LFR) y en el Modelo de Bloques Estocásticos de Grado Corregido Atribuido (ADC-SBM), así como en redes de citación del mundo real (Cora, Citeseer y Pubmed). La métrica principal de evaluación es la Similitud Centrada en Elementos (ECS), que proporciona una visión detallada a nivel de nodo de la preservación de la estructura comunitaria, capaz de manejar comunidades disjuntas, superpuestas y estructuralmente jerárquicas.

Contribuciones y Resultados Clave
El estudio presenta el primer benchmark integral de robustez para la detección de comunidades basada en GNN, revelando varios hallazgos críticos:

• Compensaciones entre Supervisado y No Supervisado: Las GNN supervisadas (GCN, GAT, GraphSAGE) logran generalmente una mayor precisión de referencia en datos limpios y bien estructurados. Sin embargo, exhiben una degradación significativa del rendimiento bajo ruido de atributos y ataques estructurales. En contraste, los métodos no supervisados, particularmente DMoN, demuestran una mayor resiliencia bajo perturbaciones dirigidas y adversarias, manteniendo un rendimiento de detección de comunidades más consistente incluso a medida que aumenta la intensidad de la perturbación.
• Impacto de la Fuerza de la Comunidad: La robustez está fuertemente influenciada por la fuerza inherente de la estructura comunitaria (controlada por el parámetro de mezcla $\mu$). Las comunidades bien definidas (bajo $\mu$) reducen significativamente la pérdida de rendimiento en todos los modelos, mientras que las estructuras comunitarias débiles conducen a un deterioro rápido.
• Vulnerabilidad a Perturbaciones de Atributos: En todos los modelos, las perturbaciones asociadas con eliminaciones dirigidas de aristas y desplazamientos en las distribuciones de atributos (específicamente desplazamientos de ubicación) causan la mayor degradación en la recuperación de comunidades.
• Comportamientos Específicos de la Arquitectura:
  • GAT muestra una alta vulnerabilidad, con un rendimiento que depende en gran medida de la integridad estructural y distribuciones específicas de características; los mecanismos de atención parecen sobreajustarse a las distribuciones de entrenamiento, lo que lleva a fallos en cascada bajo perturbación.
  • GraphSAGE exhibe una robustez moderada, atribuida a su agregación basada en muestreo, que proporciona una regularización inherente contra los desplazamientos en la distribución de características.
  • DMoN emerge como el método no supervisado más robusto. Su objetivo basado en la modularidad, que considera la estructura global de la red en lugar de patrones de características locales, proporciona estabilidad inherente contra ataques estructurales. Ofrece un equilibrio favorable entre rendimiento y robustez, superando a otros métodos de agrupamiento (DiffPool, MinCUT) en el mantenimiento de la recuperación de comunidades bajo perturbaciones severas.
• Validación en el Mundo Real: En redes de citación del mundo real, los modelos supervisados muestran caídas dramáticas en el rendimiento bajo perturbaciones (por ejemplo, GAT disminuye más del 70% bajo perturbaciones de media en Cora), mientras que DMoN mantiene una estabilidad relativa significativamente mayor, aunque con puntuaciones de referencia absolutas más bajas en comparación con los métodos supervisados en datos limpios.

Significado y Afirmaciones
El artículo afirma llenar una brecha crítica en la comprensión de la sensibilidad de la detección de comunidades basada en GNN frente a diversos ataques y los mecanismos latentes que impulsan esta sensibilidad. Los hallazgos destacan una compensación fundamental entre precisión y robustez: mientras que los métodos supervisados sobresalen en condiciones ideales, los enfoques no supervisados como DMoN ofrecen una resiliencia superior en entornos ruidosos o adversarios.

Los autores sugieren que estos resultados proporcionan nuevas perspectivas para la selección de arquitecturas de GNN basadas en el régimen de perturbación esperado de la aplicación. Plantean que los objetivos basados en la modularidad pueden ser clave para la recuperación de comunidades cuando se desafía la integridad del grafo. Además, el artículo esboza direcciones futuras de investigación, incluyendo la investigación de leyes de escalado neuronal para GNN en la detección de comunidades, la exploración de incrustaciones hiperbólicas para sostener mejor las incertidumbres y el examen de relaciones de ley de potencias entre factores del modelo y robustez. El trabajo tiene como objetivo guiar el desarrollo de arquitecturas de GNN más robustas y adaptadas a la tarea para la detección de comunidades en redes del mundo real y ruidosas.