Community detection robustness of graph neural networks

Résumé technique : Robustesse de la détection de communautés par les réseaux de neurones à graphes

Énoncé du problème
Les réseaux de neurones à graphes (GNN) sont devenus des outils dominants pour la détection de communautés dans les réseaux attribués, intégrant efficacement la topologie structurelle et les attributs des nœuds via le passage de messages et l'agrégation. Cependant, la robustesse de ces modèles face aux perturbations et aux attaques ciblées dans le contexte spécifique de la détection de communautés reste mal comprise. Si la robustesse des GNN a été largement étudiée pour la classification de nœuds, la stabilité de la détection de communautés basée sur les GNN sous l'effet de perturbations du graphe — telles que le bruit, les données incomplètes et les manipulations adverses — a été largement négligée. Les études existantes sur la robustesse de la détection de communautés se sont principalement concentrées sur des algorithmes classiques sous de simples ajouts ou suppressions d'arêtes, négligeant souvent les architectures GNN modernes et les sources complexes et interactives de perturbation rencontrées dans les scénarios réels.

Méthodologie
Les auteurs mènent une évaluation computationnelle systématique de six architectures GNN largement adoptées, catégorisées en paradigmes supervisés et non supervisés :

• Supervisé : Réseaux de convolution de graphes (GCN), réseaux d'attention de graphes (GAT) et GraphSAGE.
• Non supervisé : DiffPool, MinCUT et DMoN (qui utilise la maximisation de la modularité).

L'évaluation couvre trois catégories distinctes de perturbations :

1. Manipulations des attributs des nœuds : Altération de la localisation (moyenne) et de l'échelle (variance) des distributions d'attributs pour créer des chevauchements entre les clusters.
2. Distorsions de la topologie des arêtes : Suppressions aléatoires d'arêtes (simulant des pannes réseau) et suppressions ciblées d'arêtes basées sur la centralité d'intermédiarité (simulant des attaques structurelles adverses).
3. Attaques adverses : Utilisation de Nettack et Metattack, qui emploient des modèles de substitution et l'apprentissage par méta pour perturber stratégiquement à la fois la topologie et les attributs tout en préservant les propriétés statistiques du graphe original (par exemple, les distributions de degrés en loi de puissance).

Les expériences sont menées sur des benchmarks synthétiques, spécifiquement les graphes Lancichinetti–Fortunato–Radicchi (LFR) et le modèle de blocs stochastiques à degrés corrigés attribués (ADC-SBM), ainsi que sur des réseaux de citations réels (Cora, Citeseer et Pubmed). La métrique d'évaluation principale est la similarité centrée sur les éléments (ECS), qui fournit une vue détaillée au niveau des nœuds de la préservation de la structure communautaire, capable de gérer des communautés disjointes, chevauchantes et hiérarchiquement structurées.

Contributions et résultats clés
L'étude présente le premier benchmark de robustesse complet pour la détection de communautés basée sur les GNN, révélant plusieurs constatations critiques :

• Compromis Supervisé vs Non Supervisé : Les GNN supervisés (GCN, GAT, GraphSAGE) atteignent généralement une précision de base plus élevée sur des données propres et bien structurées. Cependant, ils présentent une dégradation significative des performances sous l'effet du bruit d'attributs et des attaques structurelles. En revanche, les méthodes non supervisées, en particulier DMoN, démontrent une plus grande résilience face aux perturbations ciblées et adverses, maintenant des performances de détection de communautés plus cohérentes même lorsque l'intensité des perturbations augmente.
• Impact de la force communautaire : La robustesse est fortement influencée par la force inhérente de la structure communautaire (contrôlée par le paramètre de mélange $\mu$). Des communautés bien définies (faible $\mu$) réduisent considérablement la perte de performance pour tous les modèles, tandis que des structures communautaires faibles entraînent une détérioration rapide.
• Vulnérabilité aux perturbations d'attributs : Pour tous les modèles, les perturbations associées aux suppressions d'arêtes ciblées et aux déplacements des distributions d'attributs (spécifiquement les déplacements de localisation) provoquent la plus grande dégradation dans la récupération des communautés.
• Comportements spécifiques à l'architecture :
  • GAT montre une vulnérabilité élevée, avec des performances fortement dépendantes de l'intégrité structurelle et de distributions de caractéristiques spécifiques ; les mécanismes d'attention semblent surajuster aux distributions d'entraînement, entraînant des défaillances en cascade sous perturbation.
  • GraphSAGE présente une robustesse modérée, attribuée à son agrégation basée sur l'échantillonnage qui fournit une régularisation inhérente face aux déplacements de distributions de caractéristiques.
  • DMoN émerge comme la méthode non supervisée la plus robuste. Son objectif basé sur la modularité, qui considère la structure globale du réseau plutôt que les motifs de caractéristiques locaux, offre une stabilité inhérente face aux attaques structurelles. Il offre un équilibre favorable entre performance et robustesse, surpassant les autres méthodes d'agrégation (DiffPool, MinCUT) dans le maintien de la récupération des communautés sous des perturbations sévères.
• Validation sur des données réelles : Sur les réseaux de citations réels, les modèles supervisés montrent des chutes dramatiques de performance sous perturbations (par exemple, GAT chutant de plus de 70 % sous des perturbations de moyenne sur Cora), tandis que DMoN maintient une stabilité relative significativement plus élevée, bien qu'avec des scores de base absolus inférieurs à ceux des méthodes supervisées sur des données propres.

Signification et affirmations
L'article prétend combler une lacune critique dans la compréhension de la sensibilité de la détection de communautés basée sur les GNN face à diverses attaques et des mécanismes latents qui sous-tendent cette sensibilité. Les résultats mettent en évidence un compromis fondamental entre précision et robustesse : si les méthodes supervisées excellent dans des conditions idéales, les approches non supervisées comme DMoN offrent une résilience supérieure dans des environnements bruyants ou adverses.

Les auteurs suggèrent que ces résultats fournissent de nouvelles perspectives pour le choix des architectures GNN en fonction du régime de perturbation attendu de l'application. Ils postulent que les objectifs basés sur la modularité peuvent être la clé de la récupération des communautés lorsque l'intégrité du graphe est remise en question. De plus, l'article décrit des orientations de recherche futures, notamment l'investigation des lois d'échelle neuronales pour les GNN dans la détection de communautés, l'exploration des plongements hyperboliques pour mieux soutenir les incertitudes, et l'examen des relations en loi de puissance entre les facteurs du modèle et la robustesse. Ce travail vise à guider le développement d'architectures GNN plus robustes et adaptées aux tâches pour la détection de communautés dans des réseaux réels et bruyants.