Sintesi Tecnica: Modellazione Generativa su Grafi Metrici tramite Trasporto Ottimo Neurale

Definizione del Problema

Molti dataset scientifici e geometrici, come le reti stradali, le strutture vascolari e i sistemi fluviali, sono naturalmente supportati su grafi metrici. Un grafo metrico è uno spazio geodesico monodimensionale in cui gli archi portano lunghezze e sono trattati come intervalli continui. Gli approcci esistenti alla modellazione generativa affrontano un limite fondamentale: i metodi standard generano punti in uno spazio euclideo ambiente, fallendo nel garantire che i campioni rimangano supportati sul grafo o rispettino la sua geometria metrica intrinseca.

Al contrario, gli approcci tradizionali di Trasporto Ottimo (OT) per i grafi spesso si affidano alla discretizzazione, approssimando le distribuzioni continue con misure basate su nodi finiti. Sebbene siano computazionalmente accessibili, questo approccio introduce approssimazioni dipendenti dalla mesh e scala male all'aumentare della discretizzazione, perdendo la natura continua del dominio originale.

Il documento affronta la necessità di un framework generativo continuo supportato su grafo che possa sfruttare strutture ambienti lisce per il calcolo senza sacrificare la fedeltà geometrica del grafo metrico.

Metodologia

Gli autori propongono un framework di modellazione generativa profonda che incorpora il grafo metrico in uno spazio ambiente liscio, risolve un problema di OT entropico in tale spazio e proietta i campioni nuovamente sul grafo. La pipeline consiste in tre fasi principali:

1. Embedding (Imbricazione): Il grafo metrico $\Gamma$ viene incorporato in una varietà ambiente liscia $M_\Psi$ tramite una mappa $\Psi$. Il documento investiga due specifici embedding:

   • Realizzazione Euclidea Estrinseca ($\iota$): Mappa il grafo in $\mathbb{R}^m$ (ad esempio, le coordinate planari di una rete stradale).
   • Embedding Intrinseco Tropical Abel–Jacobi ($\Phi_p$): Mappa il grafo nel suo toro di Jacobian tropicale $J(\Gamma)$. Questo embedding dipende solo dalle lunghezze degli archi e dalla struttura dei cicli, fornendo una geometria intrinseca indipendente da un particolare disegno euclideo.

2. Trasporto Ottimo Entropico Neurale:

   • Le misure sorgente ($P_\Gamma$) e target ($Q_\Gamma$) vengono spinte in avanti nello spazio ambiente ($P_\Psi, Q_\Psi$).
   • Un problema di Kantorovich entropico viene risolto tra queste misure incorporate utilizzando una parametrizzazione semiduale.
   • A differenza delle formulazioni Monge basate su mappe, questo approccio apprende un accoppiamento (piano). Il potenziale di Schrödinger lato target è parametrizzato da una rete neurale $g_\theta$.
   • Per generare output continui piuttosto che campioni limitati ad atomi target, la legge condizionale appresa viene smussata utilizzando il kernel del calore ambiente. Ciò produce campioni nello spazio ambiente che potrebbero non trovarsi esattamente sul grafo incorporato.

3. Recupero (Proiezione–Pullback):

   • Poiché i campioni smussati dal calore possono cadere fuori dal grafo incorporato, viene eseguita una proiezione sul punto più vicino sull'embedding del grafo $\Psi(\Gamma)$.
   • L'embedding inverso $\Psi^{-1}$ viene quindi applicato per mappare il punto proiettato nuovamente sul grafo metrico originale $\Gamma$.
   • Il generatore finale è costruito come $\rho_\Gamma^\Psi = \Psi^{-1} \circ \text{proj}_{\Psi(\Gamma)}$, garantendo che tutti i campioni generati siano strettamente supportati sul grafo originale.

Contributi Chiave

1. Primo Framework Generativo Profondo per Grafi Metrici: Il documento introduce, per quanto ne sappiano gli autori, il primo modello generativo profondo per distribuzioni di probabilità continuamente supportate su grafi metrici compatti.
2. Geometrie di Embedding Duali: Il framework è sviluppato per due distinte geometrie di trasporto:
   • Una realizzazione euclidea estrinseca.
   • L'embedding tropicale Abel–Jacobi nel toro di Jacobian.
3. Convergenza Teorica: Gli autori dimostrano che nel limite congiunto di crescente espressività neurale e vanishing heat scale (scala del calore evanescente), il generatore proiezione–pullback smussato dal calore appreso converge debolmente a un accoppiamento di trasporto valido tra le misure del grafo originale. Ciò garantisce che, nonostante l'apprendimento in uno spazio ambiente, l'oggetto limite sia un vero accoppiamento sul grafo.
4. Gestione dei Ponti (Bridges): Il metodo include un'augumentazione canonica (aggiunta di archi paralleli virtuali) per gestire i ponti nel grafo, assicurando che la mappa tropicale Abel–Jacobi rimanga iniettiva e che il grafo possa essere recuperato dalla sua immagine.

Risultati Sperimentali

Il metodo è stato valutato attraverso benchmark sintetici e dati del mondo reale:

• Benchmark Sintetici: Testato su grafi theta, wheel, grid e piccoli grafi stradali. Le varianti di OT neurale (sia Tropical che Euclidean) hanno costantemente ridotto l'errore (in termini di distanza di Wasserstein intrinseca del grafo $W_1^\Gamma, W_2^\Gamma$ e errori di densità/CDF $L_1$) rispetto ai baseline euristici basati su OT discreto su grafo (interpolazione nodale e pushforward ambiente). Le due geometrie di embedding hanno performato in modo comparabile, suggerendo che il guadagno primario derivi dalla regola di trasporto entropico ammortizzata piuttosto che da un vantaggio specifico dell'embedding.
• Scalabilità: L'approccio neurale scala favorevolmente con la dimensione del supporto. A differenza dei metodi espliciti di OT su grafo a coppie che richiedono la valutazione delle distanze shortest-path intrinseche su grandi coppie di supporto, il metodo neurale si addestra su minibatch e applica la regola appresa tramite inferenza a batch.
• Applicazione nel Mondo Reale: Il framework è stato applicato a un milione di posizioni di pickup di Uber a Manhattan, New York City.
  • Il compito era la generazione di densità spaziale supportata su grafo (apprendere a generare i pickup da una sorgente uniforme stradale).
  • I baseline di OT su grafo denso erano impraticabili a questa scala a causa dei vincoli di memoria ($10^{12}$ costi di coppia).
  • Il modello Neural Euclidean (Gromov) ha generato con successo campioni che hanno recuperato la struttura dominante dei pickup sulla rete stradale di Manhattan, superando i baseline euristici addestrati su un sottoinsieme subsampionato (16.384 punti).

Significato e Rivendicazioni

Il documento sostiene di fornire una soluzione fondata per la modellazione generativa su grafi metrici che evita le insidie della discretizzazione. Risolvendo il problema del trasporto in uno spazio ambiente liscio e recuperando campioni supportati sul grafo tramite proiezione, il metodo mantiene la geometria continua del dominio.

Gli autori sottolineano che il loro approccio è basato su piani (plan-based) piuttosto che su mappe, permettendo la gestione di misure singolari sul grafo senza doverle smussare in densità ambienti. La garanzia teorica di convergenza debole verso un accoppiamento valido assicura che il metodo non sia meramente un'euristica, ma abbia una solida base nella teoria del trasporto ottimo.

Il lavoro dimostra che l'OT neurale può essere adattato a domini geometrici monodimensionali non euclidei, offrendo un'alternativa scalabile all'OT discreto su grafo per applicazioni che vanno dalla mobilità urbana alle reti biologiche. Gli autori segnalano i limiti, inclusa la natura asintotica della prova di convergenza (assenza di tassi a campioni finiti) e l'attuale focus sulla generazione non condizionata piuttosto che sulla previsione temporale o condizionata da covariate.