Generalized Schrödinger Bridge on Graphs

Transportation on graphs is a fundamental challenge across many domains, where decisions must respect topological and operational constraints. Despite the need for actionable policies, existing graph-transport methods lack this expressivity. They rely on restrictive assumptions, fail to generalize across sparse topologies, and scale poorly with graph size and time horizon. To address these issues, we introduce Generalized Schrödinger Bridge on Graphs (GSBoG), a novel scalable data-driven framework for learning executable controlled continuous-time Markov chain (CTMC) policies on arbitrary graphs under state cost augmented dynamics. Notably, GSBoG learns trajectory-level policies, avoiding dense global solvers and thereby enhancing scalability. This is achieved via a likelihood optimization approach, satisfying the endpoint marginals, while simultaneously optimizing intermediate behavior under state-dependent running costs. Extensive experimentation on challenging real-world graph topologies shows that GSBoG reliably learns accurate, topology-respecting policies while optimizing application-specific intermediate state costs, highlighting its broad applicability and paving new avenues for cost-aware dynamical transport on general graphs.

Many important real-world problems boil down to moving "stuff" through a network: goods flowing through a supply chain, vehicles routing across a road map, requests traversing a communications grid, or atoms rearranging as a protein folds into its functional shape. In each case, decisions have to respect the structure of the network (you can only move along existing connections), avoid bottlenecks like congestion or capacity limits, and unfold sensibly over time rather than in a single static step. Existing tools for this kind of "transport on networks" tend to fall short in one of three ways. Some give only a static plan that says how much should move overall, but not how the mass should travel through the network step by step. Others can produce a time-evolving plan but become prohibitively slow or memory-hungry on networks with many nodes or long time horizons. And most struggle to incorporate practical, situation-specific costs such as congestion, capacity, or energy. We introduce Generalized Schrödinger Bridge on Graphs (GSBoG), a method that learns a flexible, time-dependent routing strategy directly on a given network. Instead of solving one giant optimization problem over the whole network, GSBoG learns local rules that say, at each node and time, where mass should move next. It simultaneously matches a desired starting and ending distribution while keeping intermediate costs low. Because each decision only depends on a node's immediate neighbors, the method scales gracefully to large, sparse networks that previous methods cannot handle. We demonstrate GSBoG on three settings: routing in a large supply-chain network, assigning items to slots while respecting cost trade-offs, and steering a molecular simulation of protein folding. In each case, GSBoG reliably reaches the desired target, respects the structure of the network, and produces well-behaved intermediate dynamics, paving the way for cost-aware, deployable transport policies on the many graph-shaped systems that arise in science and engineering.