# Generalized Schr"odinger Bridge on Graphs

arXiv: https://arxiv.org/abs/2602.04675 · HTML: https://mlsanity.com/paper/2602.04675/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 53 references that are in the map.
- First posted on arXiv 4 Feb 2026.

## Builds on (most cited first, 27 of 27)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution](https://mlsanity.com/paper/2310.16834/) (2023)
- [Diffusion Schr"odinger Bridge with Applications to Score-Based Generative Modeling](https://mlsanity.com/paper/2106.01357/) (2021)
- [Likelihood Training of Schr"odinger Bridge using Forward-Backward SDEs Theory](https://mlsanity.com/paper/2110.11291/) (2021)
- [I2SB: Image-to-Image Schr"odinger Bridge](https://mlsanity.com/paper/2302.05872/) (2023)
- [Diffusion Schr"odinger Bridge Matching](https://mlsanity.com/paper/2303.16852/) (2023)
- [Solving Schr"odinger Bridges via Maximum Likelihood](https://mlsanity.com/paper/2106.02081/) (2021)
- [On the relation between optimal transport and Schr"odinger bridges: A stochastic control viewpoint](https://mlsanity.com/paper/1412.4430/) (2014)
- [Diffusion Bridge Mixture Transports, Schr"odinger Bridge Problems and Generative Modeling](https://mlsanity.com/paper/2304.00917/) (2023)
- [Deep Generalized Schr"odinger Bridge](https://mlsanity.com/paper/2209.09893/) (2022)
- [Light and Optimal Schr"odinger Bridge Matching](https://mlsanity.com/paper/2402.03207/) (2024)
- [Generalized Schr"odinger Bridge Matching](https://mlsanity.com/paper/2310.02233/) (2023)
- [Aligned Diffusion Schr"odinger Bridges](https://mlsanity.com/paper/2302.11419/) (2023)
- [The data-driven Schroedinger bridge](https://mlsanity.com/paper/1806.01364/) (2018)
- [Stability of Entropic Optimal Transport and Schr"odinger Bridges](https://mlsanity.com/paper/2106.03670/) (2021)
- [A gradient descent perspective on Sinkhorn](https://mlsanity.com/paper/2002.03758/) (2020)
- [Augmented Bridge Matching](https://mlsanity.com/paper/2311.06978/) (2023)
- [Discrete Diffusion Schr"odinger Bridge Matching for Graph Transformation](https://mlsanity.com/paper/2410.01500/) (2024)
- [Quadratically-Regularized Optimal Transport on Graphs](https://mlsanity.com/paper/1704.08200/) (2017)
- [Deep Distributed Optimization for Large-Scale Quadratic Programming](https://mlsanity.com/paper/2412.12156/) (2024)
- [Momentum Multi-Marginal Schr"odinger Bridge Matching](https://mlsanity.com/paper/2506.10168/) (2025)
- [Optimal Transport for Stationary Markov Chains via Policy Iteration](https://mlsanity.com/paper/2006.07998/) (2020)
- [Go With the Flow: Fast Diffusion for Gaussian Mixture Models](https://mlsanity.com/paper/2412.09059/) (2024)
- [Flows over time in time-varying networks](https://mlsanity.com/paper/1401.6053/) (2014)
- [Efficient preconditioners for solving dynamical optimal transport via interior point methods](https://mlsanity.com/paper/2209.00315/) (2022)
- [Approximate Wasserstein Attraction Flows for Dynamic Mass Transport over Networks](https://mlsanity.com/paper/2109.09182/) (2021)

## Built on by (most cited first, 1 of 1)

- [Cost-augmented Schr"odinger bridges on graphs are exactly solvable: a Feynman-Kac tilt replaces learned control](https://mlsanity.com/paper/2610.02195/) (2026)

## Abstract (arXiv)

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"odinger 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.