Generative Diffusion Models of Stochastic Graph Signals

Sintesi Tecnica: Modelli di Diffusione Generativa per Segnali su Grafi Stocastici

Enunciato del Problema
Molte attività di apprendimento automatico su grafi—che spaziano dai sistemi di raccomandazione all'ottimizzazione delle reti wireless e alla previsione finanziaria—coinvolgono segnali supportati su strutture a grafo che sono realizzazioni di distribuzioni condizionali sconosciute. Gli approcci esistenti spesso si affidano a progettazioni intricate e specifiche per ogni applicazione che regressionano verso una media condizionale piuttosto che campionare dalla piena legge condizionale. Questo limite impedisce di catturare l'incertezza, gli eventi rari nelle code (tail events) e la natura stocastica delle soluzioni ottimali (ad esempio, nel riparto delle risorse tramite time-sharing). Il documento affronta la necessità di un framework unificato capace di modellazione generativa di segnali su grafi stocastici, condizionati sia dalla topologia del grafo che dalle informazioni ausiliarie sui nodi.

Metodologia
Gli autori propongono un framework di diffusione di denoising condizionale adattato per dati strutturati su grafi. L'innovazione principale è la U-Graph Neural Network (U-GNN), un adattamento al dominio dei grafi della U-Net con convoluzioni su immagini.

1. Processo di Diffusione Condizionale:
   Il metodo formula la generazione di segnali su grafi come un processo di denoising diffusion condizionato. Un processo forward corrompe gradualmente un segnale sul grafo pulito $x_0$ con rumore gaussiano per raggiungere un prior trattabile. Un processo inverso appreso, parametrizzato dalla U-GNN, denoise i campioni verso la distribuzione dei dati condizionata all'operatore di shift del grafo $S$ (topologia) e agli stati ausiliari dei nodi $u$ (informazioni ausiliarie). L'obiettivo di addestramento minimizza l'errore di predizione del rumore, in modo coerente con i modelli di diffusione standard.

2. Architettura U-GNN:
   Per adattare l'architettura U-Net ai domini irregolari dei grafi, gli autori introducono un nuovo meccanismo di pooling e unpooling che evita il coarsening esplicito del grafo:

   • Selezione dei Nodi Appresa: Invece di lattice di pooling fissi, il down-sampling e l'up-sampling sono formalizzati come operazioni apprese di (de)selezione dei nodi utilizzando matrici di selezione annidate ($D_b$). Queste matrici sono addestrate end-to-end per trattenere i nodi più informativi per il compito di denoising a ogni risoluzione.
   • Lift-Filter-Reduce: L'architettura elabora i segnali mediante il "lifting" di un segnale ridotto all'intero set di nodi tramite zero-padding (usando la trasposta della matrice di selezione), applicando convoluzioni su grafi sul grafo originale, e poi riducendo il risultato nuovamente al set di nodi attivi. Ciò assicura che il filtraggio rimanga interpretabile come una convoluzione sul grafo originale a ogni risoluzione.
   • Stride sugli Shift del Grafo: Per evitare che i nodi attivi aggreghino prevalentemente valori sottoposti a zero-padding sotto un pesante down-sampling, gli autori introducono un parametro di stride $\gamma$. Questo sostituisce l'unità di shift del grafo $S$ con uno shift a $\gamma$-hop ($S^\gamma$), aumentando efficacementmente il campo recettivo e mantenendo la connettività, analogamente alle convoluzioni dilatate nelle CNN.
   • Condizionamento: La rete incorpora embedding globali del passo di diffusione $k$ e degli stati dei nodi $u$, fondendoli nel percorso del segnale in ogni blocco di encoder e decoder tramite strati di proiezione.

Contributi Chiave
Il documento delinea tre contributi primari:

• (C1) Un approccio di modellazione generativa di segnali su grafi che combina modelli di diffusione denoising con le Graph Neural Networks (GNN) per campionare segnali su grafi stocastici.
• (C2) L'architettura U-GNN, che parametrizza il processo di diffusione inversa. Essa generalizza la U-Net ai segnali strutturati su grafi utilizzando strati GNN con stride e pooling con zero-padding, eliminando la necessità di un esplicito coarsening del grafo ad ogni risoluzione.
• (C3) L'applicazione del framework a due distinte attività generative: la previsione dei prezzi azionari su un grafo di correlazione di indicatori finanziari e l'allocazione ottimale delle risorse wireless sotto requisiti ergodici di qualità del servizio (QoS).

Risultati Sperimentali
Il framework è stato valutato su due domini con estesi risultati numerici:

1. Previsione dei Prezzi Azionari (S&P 500):

   • Compito: Generare traiettorie di log-rendimento future per 468 titoli azionari, condizionati dalla storia di mercato e dalle caratteristiche fondamentali.
   • Performance: La U-GNN ha superato la baseline Geometric Random Walk (GRW) in quasi tutte le metriche, inclusi Continuous Ranked Probability Score (CRPS), RMSE e Mean Absolute Error (MAE).
   • Fedeltà Distribuionale: A differenza della GRW, la U-GNN è riuscita a riprodurre i fatti stilizzati dei rendimenti finanziari, come il clustering della volatilità e il momentum. Sebbene abbia leggermente sovrastimato l'eccesso di curtosi (catturando gli eventi rari nelle code in modo più aggressivo rispetto ai dati), ciò è stato attribuito a un compromesso tra nitidezza (sharpness) e fedeltà. Il modello ha catturato la struttura di autocorrelazione dei rendimenti e la correlazione cross-settoriale degli stock meglio della baseline.

2. Allocazione delle Risorse Wireless (WRA):

   • Compito: Apprendere a campionare politiche di allocazione della potenza ottimali per 400 coppie trasmettitore-ricevitore in reti di interferenza, condizionate dalle informazioni sullo stato del canale.
   • Performance: La politica U-GNN si è avvicinata molto a un algoritmo esperto primal-dual (PD) in termini di sum-rate ergodica e fattibilità. Ha superato significativamente le baseline deterministiche (politiche Full Power e Average Power), specialmente nel mantenere la fattibilità per gli utenti ai bordi della cella (5° e esimo percentile).
   • Stocasticità: I risultati hanno dimostrato che la politica ottima è intrinsecamente stocastica (multimodale). La U-GNN ha ottenuto la fattibilità ergodica attraverso il time-sharing (campionando diverse allocazioni nel tempo), mentre le baseline deterministiche non sono riuscite a soddisfare i vincoli di QoS per tutti gli utenti simultaneamente.
   • Scalabilità: Il modello ha mostrato una forte trasferibilità dimensionale, mantenendo le prestazioni su reti da 200 a 1600 nodi senza ri-addestramento, grazie alla natura permutazione-equivariante del backbone GNN.

Significatività e Rivendicazioni
Il documento sostiene di fornire un framework metodologico generale per la generazione di segnali su grafi che unifica vari problemi specifici per applicazione sotto un singolo paradigma di denoising diffusion. Sostituendo i design deterministici, spesso specifici per l'applicazione, con un framework stocastico unificato, il metodo consente la generazione di campioni diversificati dalle leggi condizionali. Ciò è particolarmente significativo per compiti in cui la soluzione è una distribuzione (ad esempio, politiche ottime di time-sharing) o dove la quantificazione dell'incertezza è critica (ad esempio, previsioni finanziarie). L'architettura U-GNN è presentata come uno strumento general-purpose per l'apprendimento su segnali su grafi, ereditando le proprietà di stabilità e trasferibilità delle GNN, estendendo al contempo le capacità multi-risoluzione delle U-Net a domini irregolari senza l'uso di un coarsening esplicito del grafo.