Chaining 2-FWL GNNs for Combinatorial Graph Alignment

Technisches Resümee: Verkettung von 2-FWL GNNs für kombinatorische Graph-Alignment-Probleme

Problemdefinition
Die Arbeit befasst sich mit dem kombinatorischen Graph-Alignment-Problem (GAP), bei dem die Knotenkorrespondenz zwischen zwei unbeschlabelten Graphen ($G_A$ und $G_B$) gesucht wird, die die Anzahl der gemeinsamen Kanten (nce) maximiert. Formal entspricht dies der Minimierung der Frobenius-Norm $\|AP - PB\|_F^2$ über der Menge der Permutationsmatrizen $P$, oder der Maximierung der quadratischen Form $\langle AP, PB \rangle$. Dieses Problem ist ein spezifischer Fall des Quadratischen Zuweisungsproblems (QAP), welches als NP-schwer bekannt ist.

Die Autoren konzentrieren sich strikt auf das rein strukturelle Setting, in dem Graphen keine Knotenmerkmale außer ihrer Topologie besitzen. In diesem Regime haben sich bestehende Graph Neural Network (GNN)-Ansätze bisher kaum in der Lage gezeigt, die Leistung starker klassischer Baselines zu erreichen, insbesondere des Fast Approximate Quadratic (FAQ) Algorithmus [Vogelstein et al., 2015], der eine kontinuierliche Relaxation des QAP mittels Frank-Wolfe-Optimierung löst.

Methodik: Verkettung mit diskretem Feedback
Der Kernbeitrag ist ein Verkettungsverfahren (Chaining Procedure), das eine Serie von Folklore-Typ GNNs (2-FWL GNNs) sequenziell trainiert, um zunehmend präzisere Ähnlichkeitsmatrizen zu generieren, die als Initialisierungen für den FAQ-Algorithmus dienen.

1. Iterative Verfeinerungsschleife:

   • Schritt 1 (Merkmalsextraktion): Ein initiales GNN ($f$) extrahiert Knotenmerkmale aus den Adjazenzmatrizen und berechnet eine Ähnlichkeitsmatrix $S^{(0)}$.
   • Schritt 2 (Dekodierung & Ranking): Die Ähnlichkeitsmatrix wird über einen linearen Zuweisungslöser (Projektion) in eine Permutation $\pi$ dekodiert. Entscheidend ist, dass das Papier einen nicht-differenzierbaren Ranking-Schritt einführt: Knoten werden basierend auf ihrer „Alignment-Qualität“ (der Anzahl der korrespondierenden Kanten durch die aktuelle Permutation) gerankt. Dies injiziert diskretes kombinatorisches Feedback in die Pipeline.
   • Schritt 3 (Ranking-verstärktes Lernen): Ein nachfolgendes GNN ($g^{(k)}$) nimmt die Graphstruktur und die Knoten-Rankings als Eingabe, um eine verbesserte Ähnlichkeitsmatrix $S^{(k)}$ zu berechnen. Diese Matrix soll informativer sein als die vorherige, da sie das Wissen darüber integriert, welche Knoten derzeit gut ausgerichtet sind.

2. Sequenzielles Training:
   Da der Ranking-Schritt nicht differenzierbar ist, können die GNNs nicht end-to-end trainiert werden. Stattdessen werden sie sequenziell trainiert:

   • Trainiere $f$, um die Cross-Entropy-Loss gegen die Ground-Truth-Permutation zu minimieren.
   • Fixiere $f$, berechne Rankings auf dem Trainingsdatensatz, und trainiere dann $g^{(1)}$, um den Loss gegen die Ground Truth unter Verwendung der neuen Rankings zu minimieren.
   • Wiederhole dies für $g^{(2)}, \dots, g^{(L)}$.
     Jedes Netzwerk lernt, die durch das vorherige Netzwerk im Chain erreichte Alignment-Qualität zu verbessern.

3. Inferenz durch Looping:
   In der Inferenz kann das final trainierte Netzwerk $g^{(L)}$ iterativ angewendet werden (Looping). Nach jedem Durchgang wird eine Kandidaten-Permutation generiert, und diejenige mit der höchsten beobachteten nce wird beibehalten. Dieses „Looping“ fungiert als heuristische Verfeinerung ohne zusätzliches Training.

4. Architektur (FGNN):
   Die Autoren verwenden Folklore-Typ GNNs (FGNN), die auf Knotenpaaren statt auf einzelnen Knoten operieren. Diese Architektur erreicht eine 2-FWL (2-Folklore Weisfeiler-Leman) Expressivität. Dies ist entscheidend, da Standard-Message-Passing-Neural-Networks (MPNNs) auf 1-WL-Expressivität beschränkt sind und Schwierigkeiten haben, Knoten in regulären Graphen (in denen alle Knoten identische lokale Nachbarschaften haben) zu unterscheiden, was zu degenerierten Ähnlichkeitsmatrizen führt.

Hauptbeiträge

• Verkettungsverfahren: Ein neuartiges Trainingsparadigma, das die Lücke zwischen diskreter kombinatorischer Optimierung und kontinuierlichem GNN-Lernen schließt, indem es diskrete Rankings als Feedbacksignale nutzt.
• Verbesserte FAQ-Initialisierungen: Die Methode lernt, FAQ Ähnlichkeitsmatrizen zur Verfügung zu stellen, die signifikant bessere Initialisierungen als die Standard-konvexe Relaxation ($D_{cx}$) darstellen, insbesondere bei schwierigen Instanzen.
• Analyse der Expressivität: Das Papier zeigt, dass eine 2-FWL-Expressivität im rein strukturellen Setting notwendig ist, da 1-WL-basierte MPNNs auf regulären Graphen und dünnbesetzten Graphen mit hohem Rauschen versagen.
• Neubewertung der Baselines: Die Autoren argumentieren, dass vorangegangene Vergleiche in der Literatur FAQ oft unterschätzen, indem sie es mit einer uniformen doubly stochastischen Matrix anstatt mit der Lösung der konvexen Relaxation ($D_{cx}$) initialisieren. Bei korrekter Initialisierung ist FAQ eine wesentlich stärkere Baseline als bisher berichtet.

Ergebnisse
Die Methode wurde auf synthetischen korrelierten Zufallsgraphen (Sparse Erdős–Rényi, Dense Erdős–Rényi und reguläre Graphen) sowie drei Realwelt-Benchmarks (Yeast PPI, Coauthorship, Road networks) evaluiert.

• Sparse Erdős–Rényi Graphen: Bei einem Rauschpegel von 0,25 erreichte das Chained FGNN mit FAQ-Post-Processing (ChFGNN FAQ) eine Genauigkeit von 85 %, verglichen mit 13 % für FAQ initialisiert aus der konvexen Relaxation und praktisch 0 % für vorherige GNN-Methoden.
• Reguläre Graphen: Dies ist ein Regime, in dem Standardmethoden völlig versagen. Die konvexe Relaxation liefert eine degenerierte Lösung (das Baryzentrum), und MPNNs produzieren identische Embeddings. Das Chained FGNN ist die einzige berichtete Methode, die ein nicht-triviales Alignment wiederherstellt, wobei es bei einem Rauschpegel von 0,1 eine Genauigkeit von 56 % erreicht, während alle anderen Methoden scheiterten.
• Realwelt-Benchmarks: Bei Realwelt-Datensätzen verbesserten die Chained FGNNs die verstärkte FAQ-Baseline (FAQ initialisiert von $D_{cx}$) um etwa 2 % in Bezug auf die nce in Szenarien mit hohem Rauschen.
• Effizienz: Während das Verkettungsverfahren ein GPU-basiertes Training erfordert, reduziert der Inferenzschritt die Anzahl der Frank-Wolfe-Iterationen, die von FAQ benötigt werden, im Vergleich zur direkten Verwendung der konvexen Relaxation erheblich, was auf eine qualitativ hochwertigere Initialisierung hindeutet.

Bedeutung und Ansprüche
Das Papier behauptet, dass die iterative Verfeinerung mit diskretem kombinatorischem Feedback eine vielversprechende Richtung für kombinatorische Probleme mit einer natürlichen Ranking-Interpretation ist. Die Autoren behaupten nicht, dass ihre Methode ohne Modifikation auf beliebige kombinatorische Optimierungsprobleme übertragbar ist.

Die primäre Bedeutung liegt darin, zu zeigen, dass gelernte Repräsentationen in der Lage sind, den Stand der Technik des klassischen Solvers (FAQ) im rein strukturellen Setting zu übertreffen – ein Bereich, in dem GNNs historisch unterperformt haben. Die Arbeit hebt hervor, dass das Scheitern früherer GNNs teils auf unzureichender Expressivität (1-WL-Limitierungen) und teils auf dem Fehlen eines Mechanismus zur Integration diskreten strukturellen Feedbacks beruhte. Durch die Verkettung von 2-FWL GNNs konnten die Autoren diese Barrieren erfolgreich überwinden und State-of-the-Art-Ergebnisse auf schwierigen Sparse- und Regular-Graph-Instanzen erzielen.