Graphenabgleich über konvexe Relaxation zum Simplex

Dieses Papier behandelt das Graphenabgleichsproblem, das darin besteht, die bestmögliche Übereinstimmung zwischen zwei Eingabegraphen zu finden, und hat viele Anwendungen in der Computer Vision, der Netzwerk-Deanonymisierung und dem Proteinabgleich. Ein üblicher Ansatz zur Lösung dieses Problems erfolgt durch konvexe Relaxationen des NP-schweren Quadratischen Zuordnungsproblems (QAP). Hier stellen wir eine neue konvexe Relaxation auf dem Einheits-Simplex vor und entwickeln ein effizientes Spiegelabstiegsverfahren mit geschlossenen Iterationsformen zur Lösung dieses Problems. Im korrelierten Gaußschen Wigner-Modell zeigen wir, dass die Simplex-Relaxation mit hoher Wahrscheinlichkeit eine eindeutige Lösung zulässt. Im rauschfreien Fall impliziert dies die exakte Wiederherstellung der wahren Permutation. Zusätzlich etablieren wir eine neuartige hinreichende Bedingung für die Eingangsmatrix bei den Standard-Gierigen Rundungsmethoden, die weniger restriktiv ist als die üblicherweise verwendete "diagonale Dominanz"-Bedingung. Wir nutzen diese Bedingung, um die exakte einstufige Wiederherstellung der wahren Lösung (fast sicher) mittels des Spiegelabstiegsverfahrens im rauschfreien Setting zu zeigen. Ebenso verwenden wir diese Bedingung, um deutlich verbesserte Bedingungen für den Algorithmus GRAMPA 26 im rauschfreien Setting zu erhalten. Unsere Methode wurde sowohl an synthetischen als auch an realen Daten evaluiert und zeigt eine überlegene statistische Leistung im Vergleich zu bestehenden konvexen Relaxationsmethoden mit ähnlichen Rechenkosten.