Clustering Node Attributed Networks with Graph Neural Networks and Self Learning

Résumé Technique : Regroupement de réseaux à attributs de nœuds par réseaux de neurones graphiques et auto-apprentissage

Formulation du Problème
L'article traite du problème du regroupement (clustering) de nœuds dans des réseaux à attributs, où chaque nœud possède à la fois des connexions topologiques (arêtes) et des attributs de caractéristiques. L'objectif est de partitionner l'ensemble des nœuds en sous-ensembles disjoints (communautés) qui reflètent des structures latentes en exploitant conjointement la topologie du réseau et les attributs des nœuds. Crucialement, ce travail opère dans un cadre entièrement non supervisé, ce qui signifie qu'aucune étiquette de groupe de vérité terrain n'est disponible pendant l'entraînement ; les seuls intrants sont la structure du graphe, les attributs des nœuds et le nombre cible de clusters ($K$). Les auteurs notent que, bien que le regroupement conjoint soit intuitivement supérieur à l'utilisation de la seule topologie ou des seuls attributs, concevoir des algorithmes capables de fusionner efficacement ces signaux — surtout lorsqu'une source est bruitée — est non trivial.

Méthodologie : DCSL-GNN
Les auteurs proposent le Dynamic Context Self-Learning Graph Neural Network (DCSL-GNN), un cadre qui opère par cycles itératifs pour affiner les représentations des nœuds et les assignations de clusters. Le cadre se compose de trois modules interconnectés :

1. Génération de Contexte Dynamique :

   • Les réseaux de neurones graphiques (GNN) standards souffrent souvent de « sous-atteinte » (profondeur insuffisante pour capturer les centres de clusters éloignés) ou de « sur-lissage » (perte de distinction avec trop de couches). Pour atténuer cela, DCSL-GNN construit un Graphe de Contexte ($G_c$) pour chaque cycle, lequel diffère du graphe original.
   • Arêtes Virtuelles : Le graphe de contexte introduit des « arêtes virtuelles » connectant les nœuds aux plus proches voisins du centre de masse de leur cluster (dans l'espace de représentation). Cela permet à l'information des centres de clusters de se propager directement, évitant ainsi le besoin de couches GNN profondes.
   • Marches Aléatoires : Le graphe de contexte est généré via des marches aléatoires biaisées. À chaque étape, la marche suit soit une arête originale (pondérée par la similitude des représentations de nœuds du cycle précédent), soit effectue un saut via une arête virtuelle vers un nœud proche d'un centre de cluster.
   • Voisinages Basés sur l'Importance : Le voisinage d'un nœud dans $G_c$ est déterminé par les comptes de visites des marches aléatoires partant de ce nœud, en utilisant un seuil basé sur le $k$-ième percentile de la distribution des visites. Cela garantit que les nœuds les plus influents (même s'ils sont distants dans le graphe original) deviennent des voisins directs dans le graphe de contexte.

2. Plongement (Encodeur GNN) :

   • Un encodeur GCN standard traite le graphe de contexte $G_c$ et les attributs des nœuds pour générer des plongements (embeddings) de nœuds.
   • Poids des Arêtes : Les arêtes dans $G_c$ sont pondérées dynamiquement. Si les attributs des nœuds connectés sont hautement similaires (vérifié par un seuil de coefficient de silhouette $\beta$), le poids de l'arête est inversement proportionnel à la distance euclidienne entre leurs attributs. Sinon, le poids reste neutre (1).
   • Entraînement : Les paramètres du GNN sont entraînés à l'aide d'une fonction de perte triplet (triplet loss). Cette perte minimise la distance entre un nœud ancre et les échantillons positifs (nœuds du même cluster) tout en maximisant la distance par rapport aux échantillons négatifs (nœuds de clusters différents).
   • Persistance des Paramètres : Contra contrairement à un entraînement standard, les poids du GNN appris au cycle $r$ sont initialisés avec les valeurs du cycle $r-1$, permettant au modèle d'affiner sa compréhension au fil du temps sans repartir de zéro.

3. Boucle de Regroupement et d'Auto-apprentissage :

   • Les plongements générés sont injectés dans un algorithme K-means standard pour produire des assignations de clusters.
   • Ces nouvelles assignations de clusters sont ensuite utilisées pour mettre à jour les centres de clusters et les biais de marche aléatoire pour le cycle suivant.
   • Cela crée un mécanisme d'auto-renforcement : de meilleures représentations mènent à de meilleurs clusters, qui à leur tour génèrent de meilleurs graphes de contexte et de meilleures représentations pour le cycle suivant.

Contributions Clés

• Cadre Novateur : L'introduction de DCSL-GNN, un cadre entièrement non supervisé qui affine itérativement les représentations de nœuds via une boucle d'auto-apprentissage.
• Graphe de Contexte Dynamique : Un mécanisme pour construire un graphe de contexte combinant la topologie originale avec des arêtes virtuelles vers les centres de clusters, traitant efficacement les limitations de profondeur des GNN sans nécessiter de couches excessives.
• Mécanisme d'Auto-apprentissage : Un processus itératif où les résultats du regroupement d'un cycle influencent directement la structure du graphe (contexte) et les poids des arêtes du cycle suivant, permettant au modèle de débruiter progressivement et d'aligner la topologie avec les attributs.
• Robustesse au Bruit : La méthodologie est conçue pour exploiter la source d'information la plus fiable (soit la topologie, soit les attributs) pour corriger la source la plus bruitée.

Résultats Expérimentaux
Les auteurs ont évalué DCSL-GNN sur des données synthétiques (Attributed Stochastic Block Models) et trois jeux de données de référence du monde réel (Cora, Citeseer, PubMed).

• Données Synthétiques :

  • Efficacité de l'Auto-apprentissage : Plusieurs cycles d'auto-apprentissage ont systématiquement surpassé un cycle d'entraînement long unique (équivalent au clustering GNN classique).
  • Gestion du Bruit : Le cadre a réussi à extraire l'information d'une source fiable lorsque l'autre était bruitée. Par exemple, lorsque l'information réseau était très bruitée ($p_I=0.2$) mais que les attributs étaient propres, les performances se sont améliorées au fil des cycles. Inversement, lorsque les attributs étaient bruités mais que le réseau était propre, le modèle a également bien convergé. Cependant, lorsque les deux sources étaient hautement bruitées, les performances se sont dégradées jusqu'à un choix aléatoire, comme prévu.
  • Comparaison : DCSL-GNN a surpassé les algorithmes reposant uniquement sur la structure du réseau (Louvain) ou uniquement sur les attributs (K-means) dans les scénarios où aucune source n'était parfaitement informative.

• Jeux de Données Réels :

  • Citeseer : DCSL-GNN a obtenu l'Information Mutuelle Normalisée (NMI) la plus élevée parmi toutes les méthodes de pointe comparées.
  • Cora et PubMed : Le modèle a performé de manière compétitive mais n'a pas surpassé l'état de l'art (MGCCN pour Cora, SEComm pour PubMed).
  • Limitation : Les auteurs attribuent la performance moindre sur Cora et PubMed en partie à l'déséquilibre des clusters. Le modèle a montré une grande précision pour les clusters dominants mais une précision négligeable pour les clusters plus petits, suggérant un biais vers les groupes plus larges dans la fonction objectif.

Signification et Revendications
L'article affirme que DCSL-GNN offre une approche flexible pour le regroupement de graphes à attributs qui fusionne efficacement les informations structurelles et d'attributs sans supervision. Les auteurs soulignent que l'auto-apprentissage multi-cycles est un composant critique, car il permet de raffiner itérativement le « contexte » dans lequel les nœuds sont perçus, menant à un regroupement supérieur par rapport aux approches à cycle unique.

Les auteurs concluent modestement que, bien que la méthode soit très efficace dans les scénarios avec des clusters équilibrés ou des niveaux de bruit mixtes (comme démontré sur Citeseer et les données synthétiques), elle fait face à des défis avec les jeux de données réels hautement déséquilibrés. Ils affirment que le cadre démontre le potentiel des mécanismes d'auto-apprentissage pour améliorer les représentations de nœuds et la qualité du regroupement en l'absence de données étiquetées, bien qu'ils ne prétendent pas être une solution universelle supérieure à toutes les méthodes existantes selon toutes les caractéristiques de jeu de données.