Chaining 2-FWL GNNs for Combinatorial Graph Alignment

Technische Samenvatting: Het ketenen van 2-FWL GNN's voor Combinatorische Graafalignement

Probleemdefinitie
Het artikel behandelt het Combinatorische Graafalignement Probleem (GAP), dat streeft naar het vinden van de knoopcorrespondentie tussen twee ongelabelde grafen ($G_A$ en $G_B$) die het aantal gemeenschappelijke randen (nce) maximaliseert. Formeel is dit gelijk aan het minimaliseren van de Frobeniusnorm $\|AP - PB\|_F^2$ over de verzameling permutatiematrices $P$, of het maximaliseren van de kwadratische vorm $\langle AP, PB \rangle$. Dit probleem is een specifieke instantie van het Kwadratisch Toewijzingsprobleem (QAP), wat bekend staat als NP-hard.

De auteurs richten zich strikt op de zuiver structurele setting, waarbij grafen geen knoopkenmerken hebben behalve hun topologie. In dit regime zijn bestaande Graph Neural Network (GNN) benaderingen er niet in geslaagd om de prestaties van sterke klassieke baselines te evenaren, specifiek het Fast Approximate Quadratic (FAQ) algoritme [Vogelstein et al., 2015], dat een continue relaxatie van de QAP oplost met behulp van Frank-Wolfe optimalisatie.

Methodologie: Ketenen met Discrete Feedback
De kernbijdrage is een ketenprocedure die sequentieel een reeks Folklore-type GNN's (2-FWL GNN's) traint om steeds nauwkeurigere gelijkenismatrices te genereren, die dienen als initialisaties voor het FAQ-algoritme.

1. Iteratieve Verfijningslus:

   • Stap 1 (Kenmerkextractie): Een initiële GNN ($f$) extraheert knoopkenmerken uit de adjacency matrices en berekent een gelijkenismatrix $S^{(0)}$.
   • Stap 2 (Decoding & Ranking): De gelijkenismatrix wordt gedecodeerd naar een permutatie $\pi$ via een lineaire toewijzingsoplosser (Projectie). Cruciaal is dat het papier een niet-differentieerbare rankingstap introduceert: knopen worden gerangschikt op basis van hun "alignementkwaliteit" (het aantal gematchte randen door de huidige permutatie). Dit injecteert discrete combinatorische feedback in de pijplijn.
   • Stap 3 (Ranking-versterkte Leren): Een daaropvolgende GNN ($g^{(k)}$) neemt de graafstructuur en de knooprankings als input om een versterkte gelijkenismatrix $S^{(k)}$ te berekenen. Deze matrix wordt geacht informatiever te zijn dan de vorige omdat deze kennis bevat over welke knopen momenteel goed aligneren.

2. Sequentiële Training:
   Omdat de rankingstap niet-differentieerbaar is, kunnen de GNN's niet end-to-end getraind worden. In plaats daarvan worden ze sequentieel getraind:

   • Train $f$ om de cross-entropy loss te minimaliseren ten opzichte van de grondwaarheid-permutatie.
   • Fixeer $f$, bereken rankings op de trainingsset, en train vervolgens $g^{(1)}$ om de loss tegen de grondwaarheid te minimaliseren met behulp van de nieuwe rankings.
   • Herhaal dit voor $g^{(2)}, \dots, g^{(L)}$.
     Elk netwerk leert de alignementkwaliteit bereikt door het voorgaande netwerk in de keten te verbeteren.

3. Inference met Looping:
   Tijdens de inferentie kan het laatst getrainde netwerk $g^{(L)}$ iteratief worden toegepast (looping). Na elke passage wordt een kandidaat-permutatie gegenereerd, en de permutatie met de hoogste geobserveerde nce wordt behouden. Deze "looping" fungeert als een heuristische verfijning zonder extra training.

4. Architectuur (FGNN):
   De auteurs maken gebruik van Folklore-type GNN's (FGNN), die opereren op knoopparen in plaats van individuele knopen. Deze architectuur bereikt 2-FWL (2-Folklore Weisfeiler-Leman) expressiviteit. Dit is cruciaal omdat standaard Message Passing Neural Networks (MPNN's) beperkt zijn tot 1-WL expressiviteit en er niet in slagen om knopen te onderscheiden in regelmatige grafen (waar alle knopen identieke lokale buurten hebben), wat leidt tot degeneratieve gelijkenismatrices.

Belangrijkste Bijdragen

• Keteningprocedure: Een nieuw trainingsparadigma dat de kloof overbrugt tussen discrete combinatorische optimalisatie en continue GNN-lering door discrete rankings als feedbacksignalen te gebruiken.
• Verbeterde FAQ Initialisaties: De methode leert gelijkenismatrices te leveren die aanzienlijk betere initialisaties zijn voor FAQ dan de standaard convexe relaxatie ($D_{cx}$), met name op moeilijke instanties.
• Expressiviteitsanalyse: Het papier demonstreert dat 2-FWL expressiviteit noodzakelijk is voor de zuiver structurele setting, aangezien 1-WL-gebaseerde MPNN's falen op regelmatige grafen en ijle grafen met veel ruis.
• Herwaardering van Baselines: De auteurs stellen dat eerdere vergelijkingen in de literatuur FAQ vaak onderschatten door het te initialiseren met een uniforme dubbel stochastische matrix in plaats van de oplossing van de convexe relaxatie ($D_{cx}$). Wanneer correct geïnitialiseerd, is FAQ een veel sterkere baseline dan voorheen gerapporteerd.

Resultaten
De methode werd geëvalueerd op synthetische gecorreleerde willekeurige grafen (Sparse Erdős–Rényi, Dense Erdős–Rényi, en Regelmatige grafen) en drie real-world benchmarks (Yeast PPI, Coauthorship, Road networks).

• Sparse Erdős–Rényi Grafen: Bij een ruisniveau van 0,25 bereikte de geketende FGNN met FAQ post-processing (ChFGNN FAQ) een nauwkeurigheid van 85%, vergeleken met 13% voor FAQ geïnitialiseerd vanaf de convexe relaxatie en vrijwel 0% voor eerdere GNN-methoden.
• Regelmatige Grafen: Dit is een regime waarin standaardmethoden volledig falen. De convexe relaxatie levert een degeneratieve oplossing (het barycentrum) op, en MPNN's produceren identieke embeddings. De geketende FGNN is de enige gerapporteerde methode die een niet-triviaal alignement herstelt, met een nauwkeurigheid van 56% bij een ruisniveau van 0,1, terwijl alle andere methoden faalden.
• Real-World Benchmarks: Op real-world datasets verbeterden de geketende FGNN's de versterkte FAQ-baseline (FAQ geïnitialiseerd vanaf $D_{cx}$) met ongeveer 2% in termen van nce in situaties met hoge ruis.
• Efficiëntie: Hoewel de ketenprocedure GPU-gebaseerde training vereist, vermindert de inferentiestap het aantal Frank-Wolfe iteraties dat FAQ nodig heeft aanzienlijk vergeleken met het direct gebruiken van de convexe relaxatie, wat wijst op een kwalitatief betere initialisatie.

Betekenis en Claims
Het artikel beweert dat iteratieve verfijning met discrete combinatorische feedback een veelbelovende richting is voor combinatorische problemen met een natuurlijke rankinginterpretatie. De auteurs beweren niet dat hun methode zonder aanpassing overdraagbaar is naar willekeurige combinatorische optimalisatieproblemen.

De primaire betekenis ligt in het aantonen dat geleerde representaties de state-of-the-art klassieke solver (FAQ) kunnen verbeteren in de zuiver structurele setting, een domein waar GNN's historisch gezien onderpresteerden. Het werk benadrukt dat het falen van eerdere GNN's deels te wijten was aan onvoldoende expressiviteit (1-WL beperkingen) en deels aan het gebrek aan een mechanisme om discrete structurele feedback te integreren. Door 2-FWL GNN's te ketenen, zijn de auteurs er succesvol in geslaagd deze barrières te overwinnen, waarbij zij state-of-the-art resultaten bereikten op moeilijke ijle en regelmatige graafinstanties.