Apprentissage combinatoire de correspondance de graphes profonds robustes : une approche basée sur l’embedding.

L’appariement de graphes vise à établir une correspondance entre les nœuds de deux graphes, un problème fondamental en raison de sa nature NP-complette. Une considération pratique consiste à modéliser efficacement la fonction d'affinité en présence de bruit, afin que le résultat optimal au sens mathématique soit également significatif du point de vue physique. Ce papier recourt aux réseaux de neurones profonds pour apprendre de manière end-to-end les caractéristiques des nœuds et des arêtes, ainsi que le modèle d'affinité pour l’appariement de graphes. L’apprentissage est supervisé par une perte de permutation combinatoire sur les nœuds. Plus précisément, les paramètres incluent des réseaux de neurones convolutifs pour l’extraction de caractéristiques d’image, des réseaux de neurones de graphes pour l’encodage des nœuds, qui transforment les informations structurelles (au-delà de l’ordre deux) en caractéristiques locales aux nœuds, conduisant à un problème d’affectation linéaire, ainsi que le noyau d'affinité entre deux graphes. Notre approche présente une grande flexibilité, car la perte de permutation est indépendante du nombre de nœuds, et le modèle d’encodage est partagé entre les nœuds, permettant au réseau de traiter des nombres variables de nœuds tant en phase d’entraînement qu’en phase de déduction. En outre, notre réseau est indépendant de la catégorie (class-agnostic). Les résultats expérimentaux sur de nombreuses benchmarks montrent une performance au niveau de l’état de l’art. L’approche présente également une certaine capacité de généralisation entre catégories et jeux de données, et est capable de réaliser un appariement robuste en présence d’outliers.