A discrete Benamou-Brenier formulation of Optimal Transport on graphs

1. Problématique et Contexte

Le transport optimal (Optimal Transport - OT) est une théorie fondamentale pour mesurer la distance entre deux distributions de probabilité, $\mu$ et $\nu$. La distance de Wasserstein ($W_p$) est définie classiquement via la formulation de Kantorovich comme le coût minimal de transport. Une avancée majeure, la formulation de Benamou-Brenier, a réinterprété ce problème comme un problème variationnel dynamique : elle minimise l'énergie cinétique d'un champ de vitesse $v_t$ sur une trajectoire de distributions $f_t$, sous la contrainte de l'équation de continuité (ou équation de transport) $\partial_t f_t + \nabla \cdot (f_t v_t) = 0$.

Bien que cette formulation soit bien établie dans le cas continu (sur $\mathbb{R}^d$), son extension aux espaces discrets, et plus particulièrement aux graphes, reste un défi.

• Sur les graphes, le calcul de $W_1$ est généralement un programme linéaire de dimension $|V|^2$ (formulation de Kantorovich) ou $|E|$ (formulation de Beckmann, statique).
• Des travaux antérieurs (Erbar et Maas) ont proposé une version discrète pour $W_2$ basée sur une équation de transport, mais cette métrique est riemannienne et ne coïncide pas avec la distance $W_2$ standard.
• Le problème ouvert était de trouver une formulation de type Benamou-Brenier (dynamique) qui soit exactement équivalente à la distance de Wasserstein-1 ($W_1$) sur des graphes discrets.

2. Méthodologie

Les auteurs proposent une généralisation de l'équation de transport sur les graphes en introduisant une triplets de variables $(f, v, g)$ :

1. $f(t)$ : Une distribution de probabilité sur les sommets $V$ du graphe.
2. $v(t)$ : Un champ de vitesse défini sur les arêtes $E$.
3. $g(t)$ : Une distribution (ou densité) définie sur les arêtes $E$.

L'Équation de Transport Discrète

Contrairement au cas continu où le flux est $f \cdot v$, les auteurs définissent l'équation de transport discrète comme :
$$\partial_t f + \nabla \cdot (v \cdot g) = 0$$
où $\nabla \cdot$ est l'opérateur de divergence discret (basé sur la matrice d'incidence $\Omega$ du graphe). Ici, le produit $v \cdot g$ est un produit composante par composante sur les arêtes. Cette formulation permet de séparer la vitesse ($v$) de la densité de masse transportée sur les arêtes ($g$), ce qui est crucial pour la discrétisation.

Fonctionnelle d'Énergie

Ils définissent une fonctionnelle d'énergie $I_q(v, g)$ pour $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'objectif est de minimiser cette fonctionnelle sous la contrainte de l'équation de transport, reliant les distributions initiale $f(0)$ et finale $f(1)$.

Approche par Cas

La démonstration procède en deux étapes principales :

1. Arbres (Trees) : En exploitant la structure acyclique, les auteurs utilisent des distributions de "queue" (tail distributions) pour inverser l'équation de transport et établir une relation exacte avec la formule de $W_1$ basée sur les coupes (Evans).
2. Graphes Généraux : Pour les graphes avec cycles, l'inversion de la matrice d'incidence n'est pas unique. Les auteurs utilisent une "formulation réduite" en s'appuyant sur la formulation de Beckmann (statique) et montrent que l'on peut toujours construire une solution à vitesse constante qui atteint l'infimum.

3. Résultats Clés

Théorème 1 : Équivalence sur les Arbres

Pour un arbre enraciné, les auteurs démontrent que la distance de Wasserstein-1 est exactement égale à l'infimum de la fonctionnelle $I_2$ (ou $I_q$ pour tout $q \ge 1$) sous la contrainte de l'équation de transport :
$$W_1(f(0), f(1)) = \inf_{f,v,g} \left\{ I_2(v, g) : \partial_t f = \Omega \cdot (vg) \right\}$$
Ils caractérisent explicitement les solutions minimisantes (triplets $(f, v, g)$) en utilisant les distributions de queue, montrant que les géodésiques à vitesse constante existent et sont atteignables.

Théorème 2 : Équivalence sur les Graphes Généraux

Le résultat principal de l'article étend cette équivalence à n'importe quel graphe connexe :
$$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\}$$
Cela prouve que la formulation dynamique de Benamou-Brenier est valide pour $W_1$ sur les graphes, indépendamment de la présence de cycles.

Caractérisation des Géodésiques (Proposition 4)

Les auteurs caractérisent les géodésiques à vitesse constante de $W_1$ sur les graphes :

• Un chemin $f(t)$ est une géodésique à vitesse constante si et seulement s'il est induit par un triplet $(v, g)$ minimisant l'énergie où la norme de la vitesse est constante ($|v_k| = c$).
• Ils montrent que les interpolations convexes simples $f(t) = (1-t)f(0) + tf(1)$ sont des géodésiques, mais ne sont pas les seules. D'autres géodésiques "exotiques" existent (par exemple, des interpolations binomiales ou de Poisson qui ne sont pas linéaires en $t$).

4. Contributions Principales

1. Nouvelle Équation de Transport : Introduction d'une équation de transport discrète faisant intervenir un triplet $(f, v, g)$, permettant de gérer la géométrie discrète des graphes sans perdre l'information de la masse sur les arêtes.
2. Preuve d'Équivalence $W_1$ : Démonstration rigoureuse que la formulation variationnelle dynamique (Benamou-Brenier) est équivalente à la distance de Wasserstein-1 statique sur les graphes, comblant ainsi un vide théorique laissé par les travaux antérieurs sur $W_2$.
3. Classification des Géodésiques : Fourniture d'une caractérisation complète des géodésiques à vitesse constante pour $W_1$ sur les graphes, montrant la multiplicité des solutions optimales (contrairement au cas continu où la solution est souvent unique via l'interpolation de McCann).
4. Généralisation : Passage d'un cadre restreint (arbres ou $\mathbb{Z}$) à un cadre général (graphes connexes arbitraires).

5. Signification et Impact

Ce travail est significatif pour plusieurs raisons :

• Théorique : Il unifie les approches statiques (Beckmann, Kantorovich) et dynamiques (Benamou-Brenier) pour le transport optimal discret, confirmant que la structure géométrique sous-jacente de $W_1$ sur les graphes peut être capturée par une dynamique temporelle.
• Algorithmique : Bien que la formulation soit variationnelle, elle ouvre la voie à de nouvelles méthodes d'optimisation pour le calcul de $W_1$ sur les réseaux, potentiellement plus efficaces que les solveurs de programmation linéaire classiques pour certaines structures de graphes.
• Applications : La capacité à classifier les géodésiques et à comprendre la dynamique du transport sur des réseaux est cruciale pour les applications en apprentissage automatique (Machine Learning), notamment pour les flots de gradient de Wasserstein, l'analyse de données sur des réseaux complexes, et la modélisation de processus stochastiques discrets.

En résumé, Morris et Johnson réussissent à transposer l'élégance de la formulation de Benamou-Brenier du monde continu au monde discret des graphes, en fournissant les outils mathématiques nécessaires pour traiter le transport optimal $W_1$ comme un problème de dynamique de fluides sur un réseau.