Résumé technique : Modélisation générative sur des graphes métriques via le transport optimal neuronal

Énoncé du problème

De nombreux ensembles de données scientifiques et géométriques, tels que les réseaux routiers, les structures vasculaires et les systèmes fluviaux, sont naturellement supportés sur des graphes métriques. Un graphe métrique est un espace géodésique unidimensionnel où les arêtes portent des longueurs et sont traitées comme des intervalles continus. Les approches de modélisation générative existantes font face à une limitation fondamentale : les méthodes standards génèrent des points dans un espace euclidien ambiant, échouant ainsi à garantir que les échantillons restent supportés sur le graphe ou respectent sa géométrie métrique intrinsèque.

Inversement, les approches traditionnelles de transport optimal (OT) pour les graphes reposent souvent sur la discrétisation, approximant les distributions continues par des mesures finies basées sur les nœuds. Bien qu'accessible sur le plan computationnel, cette approche introduit des approximations dépendantes du maillage et passe mal à l'échelle lorsque la discrétisation est affinée, perdant ainsi la nature continue du domaine original.

Le présent article traite de la nécessité d'un cadre génératif continu supporté par un graphe capable de tirer parti de structures ambiantes lisses pour le calcul sans sacrifier la fidélité géométrique du graphe métrique.

Méthodologie

Les auteurs proposent un cadre de modélisation générative profonde qui implante le graphe métrique dans un espace ambiant lisse, résout un problème d'OT entropique dans celui-ci, puis projette les échantillons sur le graphe. Le pipeline se compose de trois étapes principales :

1. Immersion (Embedding) : Le graphe métrique $\Gamma$ est immergé dans une variété ambiante lisse $M_\Psi$ via une application $\Psi$. L'article étudie deux immersions spécifiques :

   • Réalisation Euclidienne Extrinsèque ($\iota$) : Projette le graphe dans $\mathbb{R}^m$ (par exemple, les coordonnées planaires d'un réseau routier).
   • Immersion Intrinsèque Tropicale d'Abel–Jacobi ($\Phi_p$) : Projette le graphe dans son tore Jacobien tropical $J(\Gamma)$. Cette immersion dépend uniquement des longueurs d'arêtes et de la structure cyclique, fournissant une géométrie intrinsèque indépendante de tout dessin euclidien spécifique.

2. Transport Optimal Entropique Neuronal :

   • Les mesures sources ($P_\Gamma$) et cibles ($Q_\Gamma$) sont poussées en avant vers l'espace ambiant ($P_\Psi, Q_\Psi$).
   • Un problème de Kantorovich entropique est résolu entre ces mesures immergées en utilisant une paramétrisation semi-duale neuronale.
   • Contrairement aux formulations de Monge basées sur des applications, cette approche apprend un couplage (plan). Le potentiel du côté cible est paramétré par un réseau de neurones $g_\theta$.
   • Pour générer des sorties continues plutôt que des échantillons restreints aux atomes cibles, la loi conditionnelle apprise est lissée à l'aide du noyau de la chaleur ambiant (heat kernel). Cela produit des échantillons dans l'espace ambiant qui peuvent ne pas se situer exactement sur le graphe immergé.

3. Récupération (Projection–Rétraction) :

   • Puisque les échantillons lissés par la chaleur peuvent tomber hors du graphe immergé, une projection au point le plus proche sur le graphe immergé $\Psi(\Gamma)$ est effectuée.
   • L'immersion inverse $\Psi^{-1}$ est ensuite appliquée pour ramener le point projeté sur le graphe métrique original $\Gamma$.
   • Le générateur final est construit comme $\rho_\Gamma^\Psi = \Psi^{-1} \circ \text{proj}_{\Psi(\Gamma)}$, garantissant que tous les échantillons générés sont strictement supportés sur le graphe original.

Principales contributions

1. Premier cadre génératif profond pour les graphes métriques : L'article introduit, à la connaissance des auteurs, le premier modèle génératif profond pour des distributions de probabilité continûment supportées sur des graphes métriques compacts.
2. Géométries d'immersion duales : Le cadre est développé pour deux géométries de transport distinctes :
   • Une réalisation euclidienne extrinsèque.
   • L'immersion tropicale d'Abel–Jacobi intrinsèque dans le tore de Jacobien.
3. Convergence Théorique : Les auteurs prouvent que dans la limite conjointe de l'augmentation de l'expressivité neuronale et de l'annulation de l'échelle de la chaleur, le générateur de projection–rétraction lissé par la chaleur converge faiblement vers un couplage de transport valide entre les mesures de graphes originales. Cela garantit que, malgré l'apprentissage dans un espace ambiant, l'objet limite est un véritable couplage sur le graphe.
4. Gestion des ponts : La méthode inclut une augmentation canonique (ajout d'arêtes parallèles virtuelles) pour gérer les ponts du graphe, garantissant que l'application d'Abel–Jacobi tropicale reste injective et que le graphe peut être récupéré de son image.

Résultats Expérimentaux

La méthode a été évaluée à travers des benchmarks synthétiques et des données du monde réel :

• Benchmarks Synthétiques : Testée sur des graphes de type theta, roue (wheel), grille et petits réseaux routiers. Les variantes d'OT neuronal (tant Tropical que Euclidien) ont systématiquement réduit l'erreur (en termes de distance de Wasserstein intrinsèque du graphe $W_1^\Gamma, W_2^\Gamma$ et d'erreurs de densité/CDF $L_1$) par rapport aux bases heuristiques basées sur l'OT de graphe discret (interpolation de nœuds et pushforward ambiant). Les deux géométries d'immersion ont obtenu des performances comparables, suggérant que le gain principal provient de la règle de transport entropique amortie plutôt que d'un avantage spécifique d'immersion.
• Scalabilité : L'approche neuronale passe favorablement à l'échelle avec la taille du support. Contraৰément aux méthodes d'OT de graphe explicites par paires qui nécessitent d'évaluer les distances de chemin le plus court intrinsèques sur de grands couples de support, la méthode neuronale s'entraîne sur des mini-lots (minibatches) et applique la règle apprise via une inférence par lots.
• Application Réelle : Le cadre a été appliqué à un million de localisations de trajets Uber à Manhattan, New York.
  • La tâche consistait en la génération de densité spatiale supportée par un graphe (apprendre à générer des trajets à partir d'une source routière uniforme).
  • Les bases de comparaison d'OT de graphes denses étaient irréalisables à cette échelle en raison des contraintes de mémoire ($10^{12}$ coûts par paires).
  • Le modèle Euclidien Neuronal (Gromov) a réussi à générer des échantillons qui ont récupéré la structure dominante des trajets sur le graphe routier de Manhattan, surpassant les bases heuristiques entraînées sur un sous-ensemble échantillonné (16 384 points).

Signification et Revendications

L'article prétend fournir une solution principled pour la modélisation générative sur des graphes métriques qui évite les pièges de la discrétisation. En résolvant le problème de transport dans un espace ambiant lisse et en récupérant des échantillons supportés par le graphe via la projection, la méthode préserve la géométrie continue du domaine.

Les auteurs soulignent que leur approche est basée sur un plan (couplage) plutôt que sur une application (map), permettant de gérer des mesures singulières sur le graphe sans les lisser en densités ambiantes. La garantie théorique de convergence faible vers un couplage valide assure que la méthode n'est pas simplement une heuristique, mais possède un fondement rigoureux dans la théorie du transport optimal.

Ce travail démontre que l'OT neuronal peut être adapté à des domaines géométriques unidimensionnels et non euclidiens, offrant une alternative scalable à l'OT de graphe discret pour des applications allant de la mobilité urbaine aux réseaux biologiques. Les auteurs notent des limites, notamment la nature asymptotique de la preuve de convergence (absence de taux pour échantillons finis) et l'accent actuel mis sur la génération inconditionnelle plutôt que sur la prévision temporelle ou conditionnée par des covariables.