Combinaison de l'Transport Optimal et des Approches Basées sur l'Emballage pour Plus d'Expressivité dans l'Alignement Graphique Non Supervisé

L'alignement graphique non supervisé trouve la correspondance nœud à nœud entre une paire de graphes attribués en exploitant uniquement la structure du graphe et les caractéristiques des nœuds. Une catégorie de travaux existants calcule d'abord la représentation des nœuds puis fait correspondre les nœuds avec des embeddings proches, ce qui est intuitif mais manque d'un objectif clair adapté à l'alignement graphique dans le cadre non supervisé. L'autre catégorie réduit le problème au transport optimal (OT) via l'apprentissage Gromov-Wasserstein (GW) avec un objectif bien défini mais laisse une grande marge pour explorer la conception du coût de transport. Nous proposons une approche principielle pour combiner leurs avantages motivée par une analyse théorique de l'expressivité du modèle. En constatant la limitation du pouvoir discriminatif dans la séparation des paires de nœuds appariées et non appariées, nous améliorons la conception du coût de l'apprentissage GW avec transformation des caractéristiques, ce qui permet l'interaction des caractéristiques à travers les dimensions. De plus, nous proposons une heuristique basée sur l'embedding simple mais efficace inspirée par le test de Weisfeiler-Lehman et ajoutons ses connaissances préalables à l'OT pour plus d'expressivité lors du traitement des données non-euclidiennes. En outre, nous sommes les premiers à garantir la contrainte d'appariement un à un en réduisant le problème à un appariement de poids maximum. La conception de l'algorithme combine efficacement nos prédictions OT et basées sur l'embedding via un empilement, une stratégie d'apprentissage d'ensemble. Nous proposons un cadre de modèle nommé CombAlign intégrant tous les modules ci-dessus pour affiner progressivement l'alignement des nœuds. À travers des expériences approfondies, nous démontrons des améliorations significatives de la précision d'alignement par rapport aux approches de pointe et validons l'efficacité des modules proposés.