Neurales Graph-Matching-Netzwerk: Lernen des quadratischen Zuordnungsproblems von Lawler mit Erweiterung auf Hypergraphen und das Matching mehrerer Graphen

Das Graph-Matching beinhaltet eine kombinatorische Optimierung basierend auf einer Kanten-zu-Kanten-Ähnlichkeitsmatrix, die im Allgemeinen als Lawlers quadratisches Zuordnungsproblem (Quadratic Assignment Problem, QAP) formuliert werden kann. Dieser Artikel stellt ein QAP-Netzwerk vor, das direkt mit der Ähnlichkeitsmatrix (äquivalent dem Assoziationsgraphen) lernt und dabei das Matching-Problem in eine eingeschränkte Knotenklassifizierungsaufgabe übersetzt. Der Assoziationsgraph wird durch ein Einbettungsnetzwerk für die Knotenklassifizierung gelernt, gefolgt von einer Sinkhorn-Normalisierung und einem Kreuzentropieverlust für das end-to-end-Lernen. Wir verbessern außerdem das Einbettungsmodell des Assoziationsgraphen durch die Einführung eines matching-bewussten Constraints basierend auf Sinkhorn sowie durch Platzhalterknoten zur Behandlung ungleicher Graphengrößen. Nach unserem besten Wissen ist dies eines der ersten Netzwerke, die direkt mit dem allgemeinen Lawlers QAP lernen. Im Gegensatz dazu konzentrieren sich aktuelle tiefgreifende Matching-Methoden auf das Lernen von Knoten-/Kantenmerkmalen in zwei Graphen jeweils getrennt. Wir zeigen auch, wie unser Netzwerk auf Hypergraph-Matching und das Matching mehrerer Graphen erweitert werden kann. Experimentelle Ergebnisse sowohl an synthetischen Graphen als auch an realweltlichen Bildern demonstrieren seine Effektivität. Für reine QAP-Aufgaben an synthetischen Daten und am QAPLIB-Benchmark kann unsere Methode wettbewerbsfähig agieren und sogar den neuesten Graph-Matching- und QAP-Lösern in deutlich kürzerer Rechenzeit überlegen sein. Eine Projektwebseite finden Sie unter http://thinklab.sjtu.edu.cn/project/NGM/index.html.