Réseau de Correspondance Graphique Neuronal : Apprentissage du Problème d'Assignation Quadratique de Lawler avec Extension à l'Hypergraphe et à la Correspondance de Graphes Multiples

L'appariement de graphes implique une optimisation combinatoire basée sur la matrice d'affinité arête-arête, qui peut être généralement formulée comme le problème d'affectation quadratique de Lawler (QAP). Cet article présente un réseau QAP apprenant directement avec la matrice d'affinité (équivalente au graphe d'association), transformant ainsi le problème d'appariement en une tâche de classification de sommets sous contrainte. Le graphe d'association est appris par un réseau d'embedding pour la classification des sommets, suivi d'une normalisation Sinkhorn et d'une perte de cross-entropie pour l'apprentissage end-to-end. Nous améliorons davantage le modèle d'embedding sur le graphe d'association en introduisant une contrainte sensible à l'appariement basée sur Sinkhorn, ainsi que des nœuds fictifs pour traiter les graphes de tailles inégales. À notre meilleure connaissance, c'est l'un des premiers réseaux à apprendre directement avec le QAP général de Lawler. En revanche, les méthodes récentes d'appariement profond se concentrent sur l'apprentissage des caractéristiques des nœuds/arrêtes dans deux graphes respectivement. Nous montrons également comment étendre notre réseau à l'appariement de hypergraphes et à l'appariement de plusieurs graphes. Les résultats expérimentaux sur des graphes synthétiques et des images du monde réel démontrent son efficacité. Pour les tâches purement QAP sur des données synthétiques et la base de référence QAPLIB, notre méthode peut performer compétitivement et même surpasser les solveurs d'appariement de graphes et les solveurs QAP les plus avancés actuellement disponibles, avec un coût temporel notablement inférieur. Nous fournissons une page d'accueil du projet à l'adresse http://thinklab.sjtu.edu.cn/project/NGM/index.html.