Chaining 2-FWL GNNs for Combinatorial Graph Alignment

Riepilogo Tecnico: Chaining di GNN 2-FWL per l'Allineamento Combinatorio di Grafi

Definizione del Problema
Il documento affronta il Problema dell'Allineamento di Grafi Combinatori (GAP), che mira a trovare la corrispondenza tra i nodi di due grafi non etichettati ($G_A$ e $G_B$) che massimizzi il numero di archi comuni (nce). Formalmente, questo è equivalente a minimizzare la norma di Frobenius $\|AP - PB\|_F^2$ su un insieme di matrici di permutazione $P$, o massimizzare la forma quadratica $\langle AP, PB \rangle$. Questo problema è un'istanza specifica del Problema di Assegnazione Quadratica (QAP), noto per essere NP-hard.

Gli autori si concentrano esclusivamente sul setting puramente strutturale, dove i grafi non possiedono feature di nodo oltre alla loro topologia. In questo regime, gli approcci esistenti basati su Graph Neural Networks (GNN) hanno faticato a eguagliare le prestazioni di solidi baseline classici, specificamente l'algoritmo Fast Approximate Quadratic (FAQ) [Vogelstein et al., 2015], che risolve una rilassazione continua del QAP tramite ottimizzazione Frank-Wolfe.

Metodologia: Chaining con Feedback Discreto
Il contributo principale è una procedura di chaining che addestra sequenzialmente una serie di GNN di tipo Folklore (2-FWL GNN) per generare matrici di similarità sempre più accurate, che fungono da inizializzazioni per l'algoritmo FAQ.

1. Ciclo di Raffinamento Iterativo:

   • Step 1 (Estrazione delle Feature): Una GNN iniziale ($f$) estrae le feature dei nodi dalle matrici di adiacenza e calcola una matrice di similarità $S^{(0)}$.
   • Step 2 (Decoding & Ranking): La matrice di similarità viene decodificata in una permutazione $\pi$ tramite un risolutore di assegnazione lineare (Proiezione). Fondamentalmente, il documento introduce un passaggio di ranking non differenziabile: i nodi vengono classificati in base alla loro "qualità di allineamento" (il numero di archi corrispondenti nella permutazione corrente). Ciò inietta un feedback combinatorio discreto nel pipeline.
   • Step 3 (Learning Potenziato dal Ranking): Una successiva GNN ($g^{(k)}$) prende come input la struttura del grafo e i ranking dei nodi per calcolare una matrice di similarità potenziata $S^{(k)}$. Questa matrice si prevede sia più informativa della precedente perché incorpora la conoscenza di quali nodi si stanno allineando bene in quel momento.

2. Addestramento Sequenziale:
   Poiché il passaggio di ranking è non differenziabile, le GNN non possono essere addestrate end-to-end. Invece, vengono addestrate sequenzialmente:

   • Si addestra $f$ per minimizzare la perdita di cross-entropy rispetto alla permutazione ground-truth.
   • Si fissa $f$, si calcolano i ranking sul set di addestramento, quindi si addestra $g^{(1)}$ per minimizzare la perdita rispetto al ground truth utilizzando i nuovi ranking.
   • Si ripete il processo per $g^{(2)}, \dots, g^{(L)}$.
     Ogni rete impara a migliorare la qualità dell'allineamento ottenuta dalla rete precedente nella catena.

3. Inferenza con Looping:
   In fase di inferenza, la rete addestrata finale $g^{(L)}$ può essere applicata iterativamente (looping). Dopo ogni passaggio, viene generata una permutazione candidata, e viene mantenuta quella con il più alto nce osservato. Questo "looping" agisce come un euristica di raffinamento senza ulteriore addestramento.

4. Architettura (FGNN):
   Gli autori impiegano GNN di tipo Folklore (FGNN), che operano sulle coppie di nodi anziché sui singoli nodi. Questa architettura raggiunge un'espressività 2-FWL (2-Folklore Weisfeiler-Leman). Questo è critico perché le standard MPNN (Message Passing Neural Networks) sono limitate all'espressività 1-WL e falliscono nel distinguere i nodi in grafi regolari (dove tutti i nodi hanno identici vicinati locali), portando a matrici di similarità degenerate.

Contributi Chiave

• Procedura di Chaining: Un nuovo paradigma di addestramento che colma il divario tra l'ottimizzazione combinatoria discreta e l'apprendimento continuo delle GNN, utilizzando i ranking discreti come segnali di feedback.
• Migliori Inizializzazioni per FAQ: Il metodo impara a fornire a FAQ matrici di similarità che sono inizializzazioni significativamente migliori rispetto alla standard rilassazione convessa ($D_{cx}$), specialmente su istanze difficili.
• Analisi dell'Espressività: Il documento dimostra che l'espressività 2-FWL è necessaria per il setting puramente strutturale, poiché le MPNN basate su 1-WL falliscono su grafi regolari e grafi sparsi con alto rumore.
• Rivalutazione dei Baseline: Gli autori sostengono che i confronti precedenti nella letteratura spesso sottostimano FAQ inizializzandolo con una matrice stocastica doppia uniforme invece che con la soluzione della rilassazione convessa ($D_{cx}$). Quando opportunamente inizializzato, FAQ è un baseline molto più forte di quanto riportato in precedenza.

Risultati
Il metodo è stato valutato su grafi casuali correlati sintetici (Sparse Erdős–Rényi, Dense Erdős–Rényi e Grafi Regolari) e tre benchmark del mondo reale (Yeast PPI, Coauthorship, Reti Stradali).

• Grafi Erdős–Rényi Sparsi: A un livello di rumore di 0.25, il Chained FGNN con post-processing FAQ (ChFGNN FAQ) ha raggiunto l'85% di accuratezza, rispetto al 13% di FAQ inizializzato dalla rilassazione convessa e quasi lo 0% dei metodi GNN precedenti.
• Grafi Regolari: Questo è un regime in cui i metodi standard falliscono completamente. La rilassazione convessa produce una soluzione degenerata (il baricentro) e le MPNN producono embedding identici. Il Chained FGNN è l'unico metodo riportato in grado di recuperare un allineamento non banale, raggiungendo il 56% di accuratezza al livello di rumore 0.1, mentre tutti gli altri metodi sono falliti.
• Benchmark del Mondo Reale: Sui dataset del mondo reale, i Chained FGNN hanno migliorato il baseline rafforzato di FAQ (FAQ inizializzato da $D_{cx}$) di circa il 2% in termini di nce in scenari ad alto rumore.
• Efficienza: Sebbene la procedura di chaining richieda l'addestramento su GPU, il passaggio di inferenza riduce significativamente il numero di iterazioni di Frank-Wolfe richieste da FAQ rispetto all'uso diretto della rilassazione convessa, indicando un'inizializzazione di qualità superiore.

Significato e Rivendicazioni
Il documento sostiene che il raffinamento iterativo con feedback combinatorio discreto è una direzione promettente per problemi combinatori con una naturale interpretazione di ranking. Gli autori non pretendono che il loro metodo sia trasferibile senza modifiche ad arbitri problemi di ottimizzazione combinatoria.

La significatività primaria risiede nel dimostrare che le rappresentazioni apprese possono migliorare le prestazioni dello stato dell'arte dei solver classici (FAQ) nel setting puramente strutturale, un dominio in cui le GNN hanno storicamente performato meno bene. Il lavoro evidenzia come il fallimento delle GNN precedenti sia dovuto in parte a un'espressività insufficiente (limitazioni 1-WL) e in parte alla mancanza di un meccanismo per incorporare il feedback strutturale discreto. Tramite il chaining di 2-FWL GNN, gli autori riescono con successo a superare queste barriere, ottenendo risultati allo stato dell'arte su istanze difficili di grafi sparsi e regolari.