Chaining 2-FWL GNNs for Combinatorial Graph Alignment

Résumé Technique : Chaînage de GNN 2-FWL pour l'Alignement de Graphes Combinatoires

Définition du Problème
Le document traite du Problème d'Alignement de Graphes Combinatoires (GAP), qui cherche à trouver la correspondance entre les nœuds de deux graphes non étiquetés ($G_A$ et $G_B$) maximisant le nombre d'arêtes communes (nce). Formellement, cela revient à minimiser la norme de Frobenius $\|AP - PB\|_F^2$ sur l'ensemble des matrices de permutation $P$, ou à maximiser la forme quadratique $\langle AP, PB \rangle$. Ce problème est une instance spécifique du Problème d'Assignation Quadratique (QAP), connu pour être NP-difficile.

Les auteurs se concentrent strictement sur le cadre purement structurel, où les graphes ne possèdent aucune caractéristique de nœud en dehors de leur topologie. Dans ce régime, les approches existantes basées sur les Réseaux de Neurones sur Graphes (GNN) ont peiné à égaler les performances des bases classiques solides, spécifiquement l'algorithme Fast Approximate Quadratic (FAQ) [Vogelstein et al., 2015], qui résout une relaxation continue du QAP via l'optimisation de Frank-Wolfe.

Méthodologie : Chaînage avec Feedback Discret
La contribution centrale est une procédure de chaînage qui entraîne séquentiellement une série de GNN de type Folklore (GNN 2-FWL) pour générer des matrices de similarité de plus en plus précises, lesquelles servent d'initialisations pour l'algorithme FAQ.

1. Boucle de Raffinement Itératif :

   • Étape 1 (Extraction de Caractéristiques) : Un GNN initial ($f$) extrait les caractéristiques des nœuds à partir des matrices d'adjacence et calcule une matrice de similarité $S^{(0)}$.
   • Étape 2 (Décodage et Classement) : La matrice de similarité est décodée en une permutation $\pi$ via un solveur d'assignation linéaire (Projection). Crucialement, le papier introduit une étape de classement non différentiable : les nœuds sont classés selon leur « qualité d'alignement » (le nombre d'arêtes appariées par la permutation actuelle). Cela injecte un feedback combinatoire discret dans le pipeline.
   • Étape 3 (Apprentissage Renforcé par le Classement) : Un GNN subséquent ($g^{(k)}$) prend la structure du graphe et les classements de nœuds comme entrée pour calculer une matrice de similarité améliorée $S^{(k)}$. Cette matrice est censée être plus informative que la précédente car elle incorpore la connaissance des nœuds qui s'alignent bien actuellement.

2. Entraînement Séquentiel :
   Parce que l'étape de classement est non différentiable, les GNN ne peuvent pas être entraînés de bout en bout. Au lieu de cela, ils sont entraînés séquentiellement :

   • Entraîner $f$ pour minimiser la perte d'entropie croisée par rapport à la permutation réelle (ground-truth).
   • Fixer $f$, calculer les classements sur l'ensemble d'entraînement, puis entraîner $g^{(1)}$ pour minimiser la perte par rapport à la vérité terrain en utilisant les nouveaux classements.
   • Répéter pour $g^{(2)}, \dots, g^{(L)}$.
     Chaque réseau apprend à améliorer la qualité d'alignement atteinte par le réseau précédent dans la chaîne.

3. Inférence avec Bouclage :
   À l'inférence, le réseau final entraîné $g^{(L)}$ peut être appliqué de manière itérative (bouclage). Après chaque passage, une permutation candidate est générée, et celle ayant le nce observé le plus élevé est conservée. Ce « bouclage » agit comme un heuristique de raffinement sans entraînement supplémentaire.

4. Architecture (FGNN) :
   Les auteurs utilisent des GNN de type Folklore (FGNN), qui opèrent sur des paires de nœuds plutôt que sur des nœuds individuels. Cette architecture atteint une expressivité 2-FWL (2-Folklore Weisfeiler-Leman). Ceci est critique car les MPNN standards sont limités à une expressivité 1-WL et échouent à distinguer les nœuds dans les graphes réguliers (où tous les nœuds ont des voisinages locaux identiques), menant à des matrices de similarité dégénérées.

Contributions Clés

• Procédure de Chaînage : Un nouveau paradigme d'entraînement qui comble le fossé entre l'optimisation combinatoire discrète et l'apprentissage continu des GNN en utilisant des classements discrets comme signaux de feedback.
• Initialisations FAQ Améliorées : La méthode apprend à fournir à FAQ des matrices de similarité qui sont des initialisations nettement meilleures que la relaxation convexe standard ($D_{cx}$), particulièrement sur les instances difficiles.
• Analyse de l'Expressivité : Le papier démontre que l'expressivité 2-FWL est nécessaire pour le cadre purement structurel, car les MPNN basés sur 1-WL échouent sur les graphes réguliers et les graphes creux avec un bruit élevé.
• Réévaluation des Baselines : Les auteurs soutiennent que les comparaisons antérieures dans la littérature sous-estiment souvent FAQ en l'initialisant avec une matrice doublement stochastique uniforme plutôt qu'avec la solution de la relaxation convexe ($D_{cx}$). Lorsqu'il est correctement initialisé, FAQ est une base bien plus forte que ce qui était rapporté précédemment.

Résultats
La méthode a été évaluée sur des graphes aléatoires corrélés synthétiques (Erdős–Rényi creux, Erdős–Rényi dense et graphes réguliers) ainsi que sur trois benchmarks du monde réel (Yeast PPI, Coauthorship, réseaux routiers).

• Graphes Erdős–Rényen Creux : À un niveau de bruit de 0,25, le FGNN chaîné avec post-traitement FAQ (ChFGNN FAQ) a atteint 85 % de précision, contre 13 % pour FAQ initialisé à partir de la relaxation convexe et pratiquement 0 % pour les méthodes GNN antérieures.
• Graphes Réguliers : C'est un régime où les méthodes standards échouent complètement. La relaxation convexe produit une solution dégénérée (le barycentre), et les MPNN produisent des plongements (embeddings) identiques. Le FGNN chaîné est la seule méthode rapportée capable de récupérer un alignement non trivial, atteignant 56 % de précision à un niveau de bruit de 0,1, alors que toutes les autres méthodes ont échoué.
• Benchmarks Réels : Sur les jeux de données réels, les FGNN chaînés ont amélioré la base FAQ renforcée (FAQ initialisé de $D_{cx}$) d'environ 2 % en termes de nce dans les contextes à bruit élevé.
• Efficacité : Bien que la procédure de chaînage nécessite un entraînement sur GPU, l'étape d'inférence réduit considérablement le nombre d'itérations de Frank-Wolfe requises par FAQ par rapport à l'utilisation directe de la relaxation convexe, indiquant une initialisation de meilleure qualité.

Signification et Revendications
Le papier affirme que le raffinement itératif avec feedback combinatoire discret est une direction prometteuse pour les problèmes combinatoires possédant une interprétation de classement naturelle. Les auteurs ne prétendent pas que leur méthode se transfère sans modification à des problèmes d'optimisation combinatoire arbitraires.

La principale signification réside dans la démonstration que des représentations apprises peuvent améliorer l'état de l'art du solveur classique (FAQ) dans le cadre purement structurel, un domaine où les GNN ont historiquement sous-performé. Le travail souligne que l'échec des GNN précédents était en partie dû à une expressivité insuffisante (limitations 1-WL) et en partie à l'absence d'un mécanisme pour incorporer le feedback structurel discret. En chaînant des GNN 2-FWL, les auteurs parviennent avec succès à surmonter ces barrières, atteignant des résultats de pointe sur des instances de graphes creux et réguliers difficiles.