Résumé Technique : Alignement de Graphes via l'Encodage Spectral à Double Passage et la Communication d'Espace Latent

1. Définition du Problème

L'alignement de graphes (ou alignement de réseaux) est la tâche consistant à identifier une correspondance univoque entre les nœuds de deux graphes ($G_s$ et $G_t$) tels que des nœuds structurellement similaires ou sémantiquement équivalents soient appariés. Ce problème est fondamental pour des applications en bioinformatique, l'analyse de réseaux sociaux, la vision par ordinateur et le traitement du langage naturel.

L'article se concentre sur le cadre non supervisé, où aucune correspondance de nœud de vérité terrain n'est disponible pendant l'entraînement. Les méthodes non supervisées existantes reposent généralement sur des réseaux de neurones sur graphes (GNN) pour projeter les nœuds dans des espaces latents, suivis d'un alignement via recherche de plus proches voisins ou algorithmes d'assignation. Cependant, les auteurs identifient deux limitations critiques des approches actuelles :

1. Dégradation de la Distinctivité des Nœuds : Les GNN standards (ex: GCN) agissent comme des filtres passe-bas imparfaits. En agrégeant les caractéristiques du voisinage, ils suppriment les composantes haute fréquence, ce qui entraîne un « lissage excessif » (oversmoothing). Cela réduit l'unicité des plongements de nœuds, rendant difficile la distinction entre les nœuds correspondants et les non-correspondants.
2. Espaces Latents Désalignés : En l'absence de supervision, les méthodes basées sur l'encodage peinent à produire des espaces latents comparables entre différents graphes. Le bruit structurel, l'hétérogénéité des caractéristiques et l'instabilité de l'entraînement font que des nœuds structurellement identiques sont projetés dans des régions distantes de l'espace latent, compromettant la fiabilité de l'alignement.

2. Méthodologie : Cadre GADL

Les auteurs proposent GADL (Graph Alignment with Dual-pass encoder and Latent space communication), un cadre unifié conçu pour traiter simultanément la dégradation de la distinctivité et le désalignement de l'espace latent.

2.1 Encodeur Spectral à Double Passage

Pour contrer le lissage excessif et injecter une discriminabilité haute fréquence, GADL utilise un encodeur GCN à double passage avec des paramètres partagés. Cet encodeur se compose de deux branches spectrales complémentaires :

• Branche Passe-Bas ($Z_l$) : Utilise un filtre $\tilde{A}_l = \frac{1}{2}(\tilde{A} + \tilde{D})$ pour capturer un contexte structurel et lisse. Elle préserve la cohérence du voisinage et la structure globale du graphe.
• Branche Passe-Haut ($Z_h$) : Utilise un filtre $\tilde{A}_h = \frac{1}{2}(\tilde{D} - \tilde{A})$ pour mettre en évidence les différences entre un nœud et ses voisins. Cette branche préserve la distinctivité des nœuds et capture des caractéristiques fines et discriminantes.

L'encodage final du nœud est la concaténation $Z = [Z_l \parallel Z_h]$. Les auteurs prouvent (Théorème 3.2) que cet encodage combiné est strictement plus discriminatif que chaque branche prise isolément, tout en maintenant la cohérence du voisinage. Contrairement aux GCN standards, qui peuvent devenir instables pour des valeurs propres $\lambda > 1$, les filtres proposés sont strictement monotones et prouvés stables.

2.2 Module de Cartes Fonctionnelles Sensible à la Géométrie

Pour traiter le désalignement de l'espace latent, GADL incorpore un module de cartes fonctionnelles qui opère dans l'espace des applications plutôt que dans l'espace des caractéristiques. Au lieu de comparer directement les plongements bruts, le modèle apprend des opérateurs linéaires ($C_{12}, C_{21}$) qui transforment les fonctions entre les espaces latents des deux graphes.

Ce module impose des contraintes structurelles via deux régularisations :

• Perte de Bijectivité ($L_{bij}$) : Garantit que les cartes fonctionnelles sont inversibles ($C_{12}C_{21} \approx I$), empêchant les solutions dégénérées et imposant un alignement mutuel.
• Perte d'Orthogonalité ($L_{orth}$) : Impose que les cartes se comportent comme des isométries partielles, préservant la géométrie locale lors des transformations inter-espaces.

Crucialement, ce module agit comme un filtre passe-bas sur les correspondances, imposant la fluidité et la robustesse en tant que priorité structurelle. Il fait le pont entre des plongements appris indépendamment sans nécessiter de correspondances de vérité terrain.

2.3 Optimisation

Le modèle est entraîné de bout en bout à l'aide d'un cadre d'auto-encodeur de graphe (GAE). La fonction de perte totale combine :

1. Perte de Reconstruction ($L_{rec}$) : Entropie croisée binaire pour reconstruire les matrices d'adjacence des graphes à partir des plongements.
2. Perte de Carte Fonctionnelle ($L_{FM}$) : Aligne les descripteurs spectraux via des moindres carrés régularisés, incluant des contraintes de commutativité du Laplacien.
3. Termes de Régularisation : Pertes de bijectivité et d'orthogonalité.

Les correspondances de nœuds sont prédites après l'entraînement en calculant la matrice de similitude cosinus entre les plongements normalisés en $\ell_2$ et en appliquant un appariement glouton (greedy matching).

3. Contributions Clés

L'article présente quatre contributions principales :

1. Cadre Unifié : Une nouvelle approche qui traite simultanément la dégradation de la distinctivité des nœuds dans l'espace des caractéristiques et le désalignement de l'espace latent dans l'espace des cartes.
2. Encodeur à Double Passage : L'introduction d'un mécanisme de filtrage spectral combinant des branches passe-bas et passe-haut pour injecter une discriminabilité haute fréquence tout en préservant le contexte structurel.
3. Module de Carte Fonctionnelle : Un module sensible à la géométrie qui aligne les espaces latents via des transformations bijectives et isométriques, agissant comme un filtre passe-bas sur les correspondances pour imposer la fluidité.
4. Validation Empirique : Des expériences approfondies démontrant une performance et une robustesse supérieures par rapport aux bases de référence existantes.

4. Résultats Expérimentaux

Les auteurs évaluent GADL sur des benchmarks semi-synthétiques (avec des perturbations structurelles contrôlées) et des jeux de données réels (Douban, ACM-DBLP, Cora, DBLP, etc.), ainsi que sur des tâches d'alignement vision-langage.

• Robustesse : Sur les benchmarks semi-synthétiques avec 5 % de perturbations structurelles, GADL surpasse systématiquement les méthodes de pointe (ex: T-GAE, SLOTAlign, GAE). Alors que les bases comme le GAE standard souffrent de chutes brutales de performance sous le bruit, GADL maintient une précision élevée, démontrant sa capacité à gérer les incohérences structurelles.
• Efficacité : Sur les benchmarks réels, GADL atteint les scores Hit@k les plus élevés. Par exemple, sur le jeu de données ACM-DBLP, il atteint un Hit@1 de 88,63 %, surpassant nettement la deuxième meilleure méthode (T-GAE à 73,89 %).
• Alignement de l'Espace Latent : Les visualisations qualitatives t-SNE montrent que sans le module de carte fonctionnelle, les nœuds correspondants sont dispersés dans des régions désalignées. Avec le module, les paires correspondantes se regroupent étroitement, confirmant un alignement inter-graphe efficace.
• Généralisation : La méthode est appliquée à l'alignement vision-langage (alignement des plongements de CLIP, DeiT, DINOv2 et des modèles de langage). GADL surpasse les solveurs basés sur l'optimisation (Gurobi, Hahn-Grant) et les méthodes de transport optimal, particulièrement sur des jeux de données complexes comme CIFAR-100 et ImageNet-100.
• Études d'Ablation : Le retrait de l'encodeur à double passage ou du module de carte fonctionnelle entraîne une dégradation significative des performances, validant la nécessité des deux composants. L'encodeur à double passage améliore spécifiquement les performances sur les jeux de données avec des caractéristiques éparses et de haute dimension où les GCN standards échouent à maintenir la distinctivité.

5. Signification et Revendications

L'article affirme que GADL représente une avancée significative dans l'alignement de graphes non supervisé en traitant fondamentalement le compromis entre lissage structurel et distinctivité des nœuds. En découplant ces objectifs en branches spectrales complémentaires et en imposant l'alignement dans l'espace des cartes plutôt que dans l'espace des caractéristiques, la méthode atteint une robustesse face au bruit structurel et à l'hétérogénéité des caractéristiques qui affectent les approches basées sur l'encodage existantes.

Les auteurs notent que bien que GADL induise un surcoût computationnel modeste par rapport aux GCN standards dû à l'architecture à double passage, il reste nettement plus efficace que les méthodes basées sur l'optimisation comme SLOTAlign, qui échouent souvent à passer à l'échelle sur de grands graphes. Ce travail souligne le potentiel des cartes fonctionnelles comme priorité structurelle pour aligner des données diverses structurées en graphes, s'étendant au-delà des domaines de graphes traditionnels vers les tâches vision-langage.

Limites et Travaux Futurs : Les auteurs reconnaissent que l'approche nécessite un réglage minutieux des hyperparamètres et qu'une limite clé du domaine reste l'absence de benchmarks à grande échelle avec une vérité terrain fiable pour l'alignement de graphes. Des travaux futurs sont proposés pour se concentrer sur le filtrage spectral adaptatif et les extensions aux réseaux moléculaires et à l'alignement multimodal.