Technische Samenvatting: Generatieve Modellering op Metrische Grafen via Neurale Optimale Transport

Probleemstelling

Veel wetenschappelijke en geometrische datasets, zoals wegennetwerken, vasculaire structuren en riviersystemen, zijn van nature ondersteund op een metrische graaf. Een metrische graaf is een eendimensionale geodesische ruimte waar randen lengtes dragen en worden behandeld als continue intervallen. Bestaande generatieve modelleringsbenaderingen kampen met een fundamentele beperking: standaardmethoden genereren punten in een omringende Euclidische ruimte, waardoor ze er niet in slagen om te garanderen dat de monsters ondersteund blijven op de graaf of de intrinsieke metrische geometrie respecteren.

Daartegenover staat dat traditionele Optimal Transport (OT) benaderingen voor grafen vaak vertrouwen op discretisatie, waarbij continue verdelingen worden benaderd met eindige, op knooppunten gebaseerde maten. Hoewel deze aanpak computationeel toegankelijk is, introduceert het mesh-afhankelijke benaderingen en schaalt het slecht wanneer de discretisatie wordt verfijnd, waardoor het continue karakter van het oorspronkelijke domein verloren gaat.

Dit artikel adresseert de behoefte aan een continue, graaf-ondersteunde generatieve framework die gladde omringende structuren kan benutten voor berekeningen zonder de geometrische getrouwheid van de metrische graaf op te offeren.

Methodologie

De auteurs stellen een diep generatief modelleringsframework voor dat de metrische graaf inbedt in een gladde omringende ruimte, daar een entropische OT-probleem oplost, en de monsters terug projecteert naar de graaf. De pijplijn bestaat uit drie hoofdfasen:

1. Inbedding (Embedding): De metrische graaf $\Gamma$ wordt ingebed in een gladde omringende variëteit $M_\Psi$ via een afbeelding $\Psi$. Het artikel onderzoekt twee specifieke inbeddingen:

   • Extrinsieke Euclidische Realisatie ($\iota$): Brengt de graaf naar $\mathbb{R}^m$ (bijv. de planaire coördinaten van een wegennetwerk).
   • Intrinsieke Tropische Abel–Jacobi Inbedding ($\Phi_p$): Brengt de graaf naar zijn Tropische Jacobiaanse torus $J(\Gamma)$. Deze inbedding hangt alleen af van de randlengtes en de cyclusstructuur, wat een intrinsieke geometrie biedt die onafhankelijk is van een specifieke Euclidische tekening.

2. Neurale Entropische Optimale Transport:

   • De bronmaat ($P_\Gamma$) en de doelmaat ($Q_\Gamma$) worden voortgestuwd naar de omringende ruimte ($P_\Psi, Q_\Psi$).
   • Een entropisch Kantorovich-probleem wordt tussen deze ingebedde maten opgelost met behulp van een neurale semiduale parametrisatie.
   • In tegenstelling tot kaart-gebaseerde Monge-formuleringen leert deze aanpak een koppeling (plan). De Schrödinger-potentiaal aan de doelzijde wordt geparametriseerd door een neuraal netwerk $g_\theta$.
   • Om continue outputs te genereren in plaats van monsters beperkt tot doel-atomen, wordt de geleerde conditionele wet gladgestreken met behulp van de omringende hittekernel (heat kernel). Dit produceert monsters in de omringende ruimte die mogelijk niet exact op de ingebedde graaf liggen.

3. Herstel (Projectie–Terugtrekking):

   • Omdat de met de hittekernel gladgestreken monsters buiten de ingebedde graaf kunnen vallen, wordt een nabijste-punt projectie op de ingebedde graaf $\Psi(\Gamma)$ uitgevoerd.
   • Vervolgens wordt de inverse inbedding $\Psi^{-1}$ toegepast om het geprojecteerde punt terug te mappen naar de oorspronkelijke metrische graaf $\Gamma$.
   • De uiteindelijke generator wordt geconstrueerd als $\rho_\Gamma^\Psi = \Psi^{-1} \circ \text{proj}_{\Psi(\Gamma)}$, wat ervoor zorgt dat alle gegenereerde monsters strikt ondersteund zijn op de oorspronkelijke graaf.

Belangrijkste Bijdragen

1. Eerste Diepe Generatieve Framework voor Metrische Grafen: Het artikel introduceert, naar weten van de auteurs, het eerste diepe generatieve model voor waarschijnlijkheidsverdelingen die continu ondersteund zijn op compacte metrische grafen.
2. Duale Inbeddingsgeometrieën: Het framework is ontwikkeld voor twee verschillende transportgeometrieën:
   • Een extrinsieke Euclidische realisatie.
   • De intrinsieke tropische Abel–Jacobi inbedding in de Jacobiaanse torus.
3. Theoretische Convergentie: De auteurs bewijzen dat in de gezamenlijke limiet van toenemende neurale expressiviteit en verdwijnende hitte-schaal, de geleerde hitte-gesmoothde projectie–terugtrekking generator zwak convergeert naar een geldige transportkoppeling tussen de oorspronkelijke graafmaten. Dit garandeert dat, ondanks het leren in een omringende ruimte, het limiterende object een authentieke koppeling op de graaf is.
4. Brugbehandeling: De methode bevat een canonieke augmentatie (het toevoegen van virtuele parallelle randen) om bruggen in de graaf te verwerken, waardoor de tropische Abel–Jacobi-afbeelding injectief blijft en de graaf uit zijn beeld kan worden hersteld.

Experimentele Resultaten

De methode werd geëvalueerd over synthetische benchmarks en real-world data:

• Synthetische Benchmarks: Getest op theta-, wiel-, grid- en kleine wegengrafen. De neurale OT-varianten (zowel Tropisch als Euclidisch) verminderden consistent de fout (in termen van intrinsieke graaf-Wasserstein afstand $W_1^\Gamma, W_2^\Gamma$ en dichtheid/CDF $L_1$-fouten) vergeleken met heuristische baselines gebaseerd op discrete graaf-OT (knooppunt-interpolatie en omringende pushforward). De twee inbeddingsgeometrieën presteerden vergelijkbaar, wat suggereert dat de primaire winst voortkomt uit de geamortiseerde entropische transportregel in plaats van een specifiek inbeddingsvoordeel.
• Schaalbaarheid: De neurale aanpak schaalt gunstig met de grootte van de support. In tegenstelling tot expliciete paarwise graaf-OT methoden die intrinsieke kortste-pad-afstanden op grote support-paren vereisen, traint de neurale methode op minibatches en past de geleerde regel toe via gebatteerde inferentie.
• Real-World Toepassing: Het framework werd toegepast op één miljoen Uber-ophaallocaties in Manhattan, New York City.
  • De taak was graaf-ondersteunde ruimtelijke dichtheidsgeneratie (leren om ophaalmomenten te genereren vanuit een uniforme wegbron).
  • Dichte graaf-OT baselines waren op deze schaal onhaalbaar vanwege geheugenbeperkingen ($10^{12}$ paarwise kosten).
  • Het Neurale Euclidische (Gromov) model genereerde succesvol monsters die de dominante ophaalstructuur op de Manhattan wegen-graaf herstelden, waarbij het heuristische baselines die getraind waren op een gesubsampleerde subset (16.384 punten) overtrof.

Betekenis en Claims

Het artikel claimt een principiële oplossing te bieden voor generatieve modellering op metrische grafen die de valkuilen van discretisatie vermijdt. Door het transportprobleem in een gladde omringende ruimte op te lossen en graaf-ondersteunde monsters te herstellen via projectie, behoudt de methode de continue geometrie van het domein.

De auteurs benadrukken dat hun aanpak plan-gebaseerd is in plaats van kaart-gebaseerd, wat het mogelijk maakt om singuliere maten op de graaf te verwerken zonder deze te mollificeren naar omringende dichtheden. De theoretische garantie van zwakke convergentie naar een geldige koppeling zorgt ervoor dat de methode niet louter een heuristiek is, maar een rigoureuze basis heeft in de optimale transporttheorie.

Het werk demonstreert dat neurale OT kan worden aangepast aan niet-Euclidische, eendimensionale geometrische domeinen, wat een schaalbare alternatief biedt voor discrete graaf-OT voor toepassingen variërend van stedelijke mobiliteit tot biologische netwerken. De auteurs merken beperkingen op, waaronder het asymptotische karakter van het convergentiebewijs (geen eindige-steekproefsnelheden) en de huidige focus op onvoorwaardelijke generatie in plaats van temporele of covariaat-geconditioneerde voorspelling.