Graph Neural Networks are Heuristics

Sintesi Tecnica: Le Reti Neurali a Grafo sono Euristiche

Definizione del Problema
Il documento affronta il Problema del Commesso Viaggiatore (TSP) Euclideo, un problema di ottimizzazione combinatoria canonico in cui l'obiettivo è trovare il ciclo hamiltoniano più breve attraverso un insieme di $n$ città. Gli autori sfidano il paradigma prevalente secondo cui le Reti Neurali a Grafo (GNN) fungano meramente da ausiliari — fornendo punteggi, guidando la ricerca o imitando algoritmi per solver classici. Inveio, il documento pone l'ipotesi che una GNN possa funzionare come un'euristica autonoma e appresa. La sfida specifica è costruire un tour completo in un singolo passaggio in avanti (forward pass) senza fare affidamento sulla decodifica autoregressiva, ricompense di apprendimento per rinforzo, procedure di ricerca esplicite (come il beam search) o miglioramento locale post-hoc (come il 2-opt).

Metodologia
Il metodo proposto è un framework GNN non autoregressivo e non supervisionato che apprende a risolvere le istanze del TSP direttamente dalla struttura geometrica del problema.

1. Obiettivo e Formulazione:
   Il TSP è formulato come la minimizzazione della traccia del prodotto tra la matrice delle distanze $D$ e una matrice di permutazione $P$ trasformata da una matrice di shift ciclico $V$. Per consentire l'ottimizzazione end-to-end basata sul gradiente, la permutazione discreta $P$ viene rilassata in una matrice di permutazione "soft" $T$ utilizzando la rilassazione Gumbel-Sinkhorn durante l'addestramento. La funzione di perdita è semplicemente la lunghezza attesa del tour: $L_{TSP} = \langle D, TVT^\top \rangle$. Durante l'inferenza, la permutazione soft viene convertita in una permutazione "hard" utilizzando l'algoritmo di Hungarian.

2. Estrazione di Caratteristiche Sensibile alla Simmetria:
   Per garantire che il modello rispetti le simmetrie del gruppo euclideo (invarianza e equivarianza per permutazione e traslazione), gli autori introducono un estrattore di caratteristiche deterministico.

   • Invarianza per Traslazione: Le coordinate delle città vengono centrate sottraendo la media.
   • Frame Canonico: Un sistema di riferimento ortonormale viene costruito utilizzando gli autovettori della matrice di covarianza empirica dei punti centrati. Ciò rimuove le ambiguità di rotazione e riflessione.
   • Codifica Armonica: I punti sono proiettati su questo frame canonico per derivare coordinate polari intrinseche ($r, \theta$). L'informazione angolare è codificata tramite $M$ armoniche di Fourier ($\sin(m\theta), \cos(m\theta)$), fornendo alla GNN indizi strutturali invarianti per rotazione.

3. Architettura della Rete:
   Il modello centrale è una Rete Neurale a Grafo con Attenzione-Scattering (SCT-GNN). Combina rappresentazioni basate sulla diffusione (utilizzando operatori di grafo derivati dalle potenze di una matrice di cammino casuale smussata) con meccanismi di attenzione apprendibili che mescolano adattivamente le caratteristiche attraverso diverse scale di diffusione. La rete è per costruzione permutazione-equivariante.

4. Strategie di Ensemble per la Diversità:
   Per generare diversità nelle soluzioni senza addestrare più modelli o eseguire una ricerca iterativa, il documento impiega due meccanismi all'interno di un singolo percorso di addestramento:

   • Monte Carlo (MC) Dropout: Il dropout viene applicato durante l'inferenza. Eseguendo molteplici passaggi in avanti stocastici con diverse maschere di dropout, il modello genera tour diversificati da un singolo istanza addestrata.
   • Snapshot Ensembling: Più checkpoint vengono salvati in diversi epoch durante un singolo ciclo di addestramento. Questi snapshot, che rappresentano punti distinti nel panorama dell'ottimizzazione, vengono utilizzati congiuntamente durante l'inferenza. Il miglior tour tra gli snapshot viene selezionato.

Contributi Chiave

• GNN come Euristiche Autonome: Il documento dimostra che una GNN può essere un'euristica completa, producendo un tour valido in un solo passaggio in avanti senza ricerca ausiliaria o raffinamento.
• Apprendimento Non Supervisionato: Il modello non richiede soluzioni ottime ground-truth o ricompense di reinforcement learning; apprende esclusivamente minimizzando l'obiettivo della lunghezza del tour.
• Apprendimento della Struttura Globale: Rimuovendo i meccanismi greedy locali e facendo affidamento su un obiettivo di ciclo hamiltoniano globale, il modello apprende vincoli combinatori non locali che le regole decisionali puramente locali (come il nearest-neighbor) perdono.
• Efficienza: Il metodo raggiunge un'inferenza su scala millisecondo su GPU, offrendo un rapporto qualità-efficienza favorevole rispetto agli euristici classici e ad altri approcci basati sull'apprendimento che si affidano alla decodifica autoregressiva o alla ricerca.

Risultati
Gli esperimenti sono stati condotti su istanze TSP con $n=100, 200$ e $500$ nodi estratti da una distribuzione euclidea uniforme.

• Performance vs. Greedy: Il modello supera costantemente il baseline Greedy Nearest-Neighbor (NN). Per il TSP100, la lunghezza media del tour è migliorata da 9.67 (Greedy) a 8.18 (GNN deterministica).
• Performance vs. Euristici Classici: Il metodo supera significativamente l'euristica di Christofides su istanze piccole (TSP100, TSP200) e eguaglia il suo livello su TSP500, ma con tempi di inferenza ordini di grandezza inferiori su GPU.
• Performance vs. Baseline basate sull'Apprendimento: Rispetto ai baseline di Reinforcement Learning (RL) e Supervised Learning (SL) (es. GAT, GCN), il metodo proposto raggiunge gap di ottimalità competitivi o superiori (es. gap del 4.39% su TSP100 rispetto al 2.48% di un forte baseline RL con beam search) pur essendo significativamente più veloce perché evita la decodifica autoregressiva e il beam search.
• Effetti dell'Ensemble: Sia il MC dropout che lo snapshot ensembling riducono ulteriormente il gap di ottimalità. La combinazione di entrambe le strategie ha prodotto i migliori risultati (gap del 4.39% su TSP100, 8.25% su TSP200, 12.11% su TSP500) con tempi di inferenza che rimangono nel regime dei millisecondi (fino a circa 82ms per l'ensemble combinato su TSP500).

Significatività e Rivendicazioni
Il documento sostiene che le euristiche non devono necessariamente essere regole create a mano o procedure di ricerca, ma possono emergere direttamente dall'apprendimento della struttura del problema. Formulando il TSP come apprendimento diretto di una permutazione con un obiettivo di ciclo hamiltoniano differenziabile, gli autori mostrano che le GNN possono interiorizzare vincoli combinatori globali. La significatività risiede nello spostamento del paradigma dell'ottimizzazione combinatoria: i vincoli strutturali e i modelli generativi possono sostituire la ricerca esplicita come fondamento per risolvere problemi intrattabili. I risultati suggeriscono che le "euristiche apprese" possono competere o superare i metodi ingegnerizzati classici sia in termini di qualità della soluzione che di efficienza computazionale, specialmente quando il costo della ricerca è proibitivo. Il lavoro posiziona le GNN non supervisionate come una nuova classe di euristiche apprese e veloci per l'ottimizzazione combinatoria.