A discrete Benamou-Brenier formulation of Optimal Transport on graphs

1. Il Problema

Il lavoro si inserisce nel campo del Trasporto Ottimo (Optimal Transport - OT), specificamente mirando a estendere la formulazione di Benamou-Brenier (originariamente definita per spazi continui $\mathbb{R}^d$) al dominio discreto dei grafi.

• Contesto: La distanza di Wasserstein ($W_p$) è una metrica fondamentale per misurare la discrepanza tra distribuzioni di probabilità. La formulazione classica di Kantorovich definisce $W_p$ come un problema di ottimizzazione statica sui piani di accoppiamento.
• La sfida: La formulazione di Benamou-Brenier reinterpreta $W_p$ come un problema dinamico di controllo ottimo, minimizzando l'energia cinetica di un campo di velocità $v_t$ soggetto all'equazione di continuità $\partial_t f_t + \nabla \cdot (f_t v_t) = 0$.
• Gap nella letteratura: Mentre esistono analoghi discreti per $W_2$ su grafi (es. Erbar e Maas), questi definiscono una metrica Riemanniana che non coincide con la distanza di Wasserstein standard. Per $W_1$, la formulazione di Beckmann (indipendente dal tempo) è nota, ma una formulazione dinamica di Benamou-Brenier completa per $W_1$ su grafi generali rimaneva un problema aperto.

2. Metodologia

Gli autori propongono un nuovo approccio basato su un'equazione di trasporto discreta definita su grafi diretti $G=(V, E)$.

A. L'Equazione di Trasporto Discreta

A differenza del caso continuo dove la densità $f$ e la velocità $v$ sono definite sullo stesso spazio, nel caso discreto gli autori introducono una terna $(f, v, g)$:

• $f(t)$: Distribuzione di probabilità sui nodi (vertici) $V$.
• $v(t)$: Campo di velocità definito sugli archi (edge) $E$.
• $g(t)$: Una distribuzione di probabilità definita sugli archi $E$.

L'equazione di trasporto è data da:
$$\partial_t f(t) + \nabla \cdot (v(t) g(t)) = 0$$
dove $\nabla \cdot$ è l'operatore di divergenza discreto (definito tramite la matrice di incidenza $\Omega$ del grafo). Il termine $v(t)g(t)$ rappresenta il flusso di massa sugli archi. La presenza di $g$ è cruciale perché permette di bilanciare la massa che fluisce tra i nodi, dato che la velocità $v$ da sola non può trasportare massa senza un "peso" associato all'arco.

B. Funzionale Energetico

Gli autori definiscono un funzionale energetico $I_q(v, g)$ per $q \ge 1$:
$$I_q(v, g) = \left( \int_0^1 \sum_{k \in E} g_k(t) |v_k(t)|^q dt \right)^{1/q}$$
L'obiettivo è minimizzare questo funzionale soggetto al vincolo dell'equazione di trasporto, partendo da una distribuzione iniziale $f(0)$ e arrivando a $f(1)$.

C. Approccio Teorico

1. Caso degli Alberi (Trees): Sfruttando la struttura aciclica degli alberi, gli autori definiscono le "code" (tails) delle distribuzioni rispetto a una radice. Dimostrano che per gli alberi, la soluzione ottima può essere espressa esplicitamente in termini di queste code, permettendo di invertire l'equazione di trasporto e trovare una soluzione a velocità costante.
2. Caso dei Grafi Generali: Per grafi con cicli, l'inversione della matrice di incidenza non è unica (esiste uno spazio nullo legato ai cicli). Gli autori introducono una formulazione ridotta che elimina la dipendenza esplicita da $f$ nel vincolo, mostrando che il problema è equivalente a trovare un flusso $J = \int_0^1 v(t)g(t) dt$ che soddisfi l'equazione di Beckmann statica.

3. Risultati Chiave

Teorema Principale (Teorema 2)

Per un grafo connesso $G$ e per qualsiasi $q \ge 1$, la distanza di Wasserstein-1 tra due distribuzioni $f(0)$ e $f(1)$ è data esattamente dal minimo del funzionale dinamico:
$$W_1(f(0), f(1)) = \inf_{f, v, g} \left\{ \left( \int_0^1 \sum_{k \in E} g_k(t) |v_k(t)|^q dt \right)^{1/q} : \partial_t f = \Omega \cdot (vg) \right\}$$
Questo risultato conferma che la formulazione di Benamou-Brenier vale anche nel dominio discreto per $W_1$, generalizzando i lavori precedenti su $\mathbb{Z}$ e sugli alberi.

Caratterizzazione delle Geodetiche

Il paper classifica le geodetiche a velocità costante $W_1$ sui grafi:

• Una geodetica è indotta da una terna $(f, v, g)$ che minimizza il funzionale.
• È dimostrato che esistono soluzioni a velocità costante dove $|v_k(t)| = c$ (costante nel tempo e uniforme sugli archi attivi).
• Interpolazione Convessa: Viene dimostrato che l'interpolazione lineare semplice $f(t) = (1-t)f(0) + tf(1)$ è una geodetica a velocità costante. Tuttavia, non è l'unica: il paper fornisce esempi (es. distribuzioni Binomiali e Poisson) in cui esistono geodetiche non lineari che sono anch'esse ottimali.

Relazione con Beckmann

Il lavoro collega la formulazione dinamica a quella statica di Beckmann. Viene mostrato che il flusso ottimo nel problema dinamico, integrato nel tempo, corrisponde esattamente al flusso ottimo del problema statico di Beckmann.

4. Contributi Principali

1. Definizione dell'Equazione di Trasporto Discreta: Integrazione di una distribuzione sugli archi ($g$) per gestire correttamente il flusso di massa su grafi discreti, risolvendo l'ambiguità della definizione di velocità su spazi discreti.
2. Generalizzazione a Grafi Arbitrari: Estensione della formulazione di Benamou-Brenier da $\mathbb{Z}$ e alberi a grafi generali con cicli, risolvendo il problema dell'inversione della matrice di incidenza tramite la formulazione ridotta.
3. Classificazione delle Geodetiche: Fornitura di una caratterizzazione completa delle geodetiche $W_1$ su grafi, dimostrando che includono sia interpolazioni lineari che soluzioni più complesse (es. interpolazioni di parametri di distribuzioni come Binomiali).
4. Unificazione: Dimostrazione che per $W_1$, la metrica dinamica (Benamou-Brenier) coincide esattamente con la metrica statica (Kantorovich/Beckmann) anche nel caso discreto, a differenza di quanto accade per $W_2$ su grafi.

5. Significato e Impatto

Questo lavoro è significativo per diverse ragioni:

• Teorico: Chiude un gap importante nella teoria del trasporto ottimo discreto, fornendo una base rigorosa per l'uso della dinamica di Benamou-Brenier su reti e grafi.
• Computazionale: La formulazione ridotta suggerisce nuovi algoritmi per calcolare $W_1$ su grafi, potenzialmente più efficienti dei metodi lineari standard su grandi dataset, sfruttando la struttura sparsa del grafo.
• Applicativo: La capacità di definire geodetiche e gradienti su grafi è fondamentale per l'apprendimento automatico (Machine Learning), in particolare per:
  • Wasserstein Gradient Flows: Estensione di flussi di gradiente su strutture discrete per l'ottimizzazione.
  • Loss Functions: Utilizzo di $W_1$ come funzione di perdita in reti neurali che operano su dati strutturati a grafo.
  • Analisi di Reti: Migliore comprensione del trasporto di risorse o informazioni in reti complesse (sociali, biologiche, di comunicazione).

In sintesi, il paper fornisce il quadro matematico necessario per trattare il trasporto ottimo dinamico su grafi come un problema di calcolo delle variazioni ben definito, aprendo la strada a nuove applicazioni in statistica computazionale e intelligenza artificiale.