TL;DR
This paper introduces the first deep generative modeling framework for probability distributions continuously supported on compact metric graphs (such as road, river, or biological networks). By embedding the graph into a smooth ambient space, solving an entropic neural optimal transport problem, and projecting the results back, the method generates valid graph-supported samples while scaling efficiently to millions of data points.
What Problem Does This Paper Address?
Many real-world datasets are naturally constrained to networks, such as traffic traffic on road systems, blood flow in vasculature, or water in river networks. Mathematically, these are modeled as metric graphs—one-dimensional structures where edges have continuous lengths.
Standard generative models (like GANs or VAEs) operate in unconstrained Euclidean spaces and fail to keep generated points strictly on the graph. Conversely, traditional optimal transport (OT) methods require discretizing the graph into a finite mesh, which scales poorly ($O(N^2)$ or worse) and introduces mesh-dependent approximations. This paper tackles the challenge of continuous, scalable generative modeling strictly supported on metric graphs without relying on discretization.
Methods
The authors propose a projection-pullback pipeline based on Neural Optimal Transport:
- Graph Embedding: The metric graph is mapped into a smooth ambient space. The authors explore two geometries: an extrinsic Euclidean embedding (using spatial coordinates) and an intrinsic tropical Abel–Jacobi embedding (mapping the graph into a flat torus based purely on edge lengths and cycles).
- Neural Entropic OT: They solve the entropic Kantorovich regularized OT problem directly between the embedded graph-supported measures using a neural semidual parameterization, learning a target-side Schrödinger potential via a neural network.
- Heat Smoothing & Projection: To generate continuous outputs rather than discrete target atoms, the learned conditional law is smoothed using the ambient space's heat kernel. Because smoothed samples can drift off the graph, a nearest-point projection maps them back onto the embedded graph, followed by an inverse embedding to return to the original metric graph.
The authors provide a theoretical guarantee proving that this pipeline converges weakly to a valid transport coupling as neural expressivity increases and heat smoothing vanishes.
Datasets
- Synthetic Geometry Benchmarks: Four distinct metric graph topologies designed to test different structural challenges: a theta graph (homologically distinct branches), a wheel graph (radial/cyclic structure), a rectangular grid (multiple homotopy-equivalent routes), and a small planar road graph (irregular geometry).
- Manhattan Uber Pickups: A large-scale, real-world dataset consisting of 1 million Uber pickup locations from 2014 in Manhattan, New York City, map-matched continuously along an OpenStreetMap road network.
Key Insights and Ideas
- Amortization Beats Discretization: Instead of computing a massive pairwise distance matrix over a discretized graph, parameterizing the transport plan with a neural network allows the model to learn a continuous transport rule via minibatches, unlocking scalability to millions of points.
- Intrinsic vs. Extrinsic Geometry: The tropical Abel–Jacobi embedding provides a purely intrinsic way to learn transport based solely on the graph's topology and edge lengths, making it independent of how the graph is visually drawn. However, for massive real-world networks, the Euclidean embedding paired with graph-distance features (Gromov features) scales much better due to the high computational cost of solving closest-vector problems in high-genus tropical tori.
- The Power of Plan-Based OT: By focusing on a plan-based (coupling) formulation rather than a deterministic map-based (Monge) formulation, the model naturally handles singular measures supported on 1D graphs embedded in higher-dimensional spaces without needing artificial data mollification.
Key Results
- On synthetic benchmarks, both the tropical and Euclidean neural OT variants consistently reduced transport errors ($W_1$ and $W_2$ Wasserstein distances) compared to the best heuristic baselines (node interpolation and ambient pushforward).
- In the million-sample Manhattan Uber pickup experiment, where standard dense graph OT baselines fail due to out-of-memory errors, the Neural Euclidean model with Gromov features achieved a $W_1$ error of 0.662, approaching the fundamental evaluation noise floor of 0.542 and vastly outperforming the ambient pushforward heuristic ($W_1 = 7.273$).
Limitations and Future Work
- Asymptotic Guarantees: The weak convergence proof holds in the limit of infinite neural expressivity and vanishing heat scale, but explicit finite-sample bounds or optimization rates are not yet established.
- Marginal Mismatch: At finite heat-smoothing scales, the final generated distribution may not perfectly match the target marginals because the smoothing step pushes mass off the graph before projection.
- Unconditional Generation: The current model is purely spatial and unconditional; it does not incorporate temporal dynamics, weather, or other covariates that influence real-world mobility patterns. Extending this to conditional or dynamically evolving graph distributions is highlighted as a key direction for future work.
Summary updated