Détection supervisée de communautés avec des réseaux neuronaux de graphes linéaires

Traditionnellement, la détection de communautés dans les graphes peut être résolue en utilisant des méthodes spectrales ou une inférence postérieure sous des modèles graphiques probabilistes. En se concentrant sur des familles de graphes aléatoires telles que le modèle de bloc stochastique, les recherches récentes ont unifié ces deux approches et identifié à la fois les seuils de détection statistiques et computationnels en termes de rapport signal-bruit. En reformulant la détection de communautés comme un problème de classification nodale sur les graphes, nous pouvons également l'étudier sous l'angle de l'apprentissage. Nous présentons une nouvelle famille de Réseaux Neuronaux Graphiques (GNN) pour résoudre des problèmes de détection de communautés dans un cadre d'apprentissage supervisé. Nous montrons qu'à partir d'une approche basée sur les données et sans accès aux modèles génératifs sous-jacents, ils peuvent égaler voire surpasser les performances de l'algorithme de propagation des croyances sur les modèles de bloc stochastique binaires et multiclasses, qui est considéré comme atteignant le seuil computationnel. Plus particulièrement, nous proposons d'augmenter les GNN avec l'opérateur non-rétrograde défini sur le graphe linéaire des adjacences d'arêtes. Nos modèles obtiennent également d'excellentes performances sur des jeux de données du monde réel. De plus, nous effectuons la première analyse du paysage d'optimisation lors de l'entraînement de GNN linéaires pour des problèmes de détection de communautés, démontrant que sous certaines simplifications et hypothèses, les valeurs de perte aux minima locaux et globaux ne sont pas très éloignées.