The generalized Schrödinger bridge on a graph moves mass between two distributions while charging a cost for the states visited. Previous work has approached this by learning the rates of a controlled continuous-time Markov chain and applying a temporal-difference penalty to restore the cost. This paper shows that a state cost folds into the reference process as a Feynman-Kac tilt. The cost-augmented bridge is then a plain bridge against the tilted reference, making the penalty unnecessary.
Exact solution through alternating endpoint rescalings
The bridge itself is computed exactly by alternating two endpoint rescalings. Each rescaling applies a sparse matrix-exponential to the current measure. No time discretization enters the computation, and no rates are learned. The alternation converges at a rate determined solely by the endpoint coupling, meaning the number of iterations needed depends on how strongly the start and end distributions pull the bridge toward each other.
Quadratic congestion and best-response dynamics
When the running cost is quadratic in time-averaged occupancies, the damped best-response dynamics around the exact bridge correspond to gradient descent on a strongly convex function. The residual of this gradient descent bounds the error between the approximate and exact bridges. This interpretation connects discrete-time optimization with the continuous-time bridge problem.
Protein-folding model with free-energy cost
On a protein-folding model, a free-energy cost is applied as the state cost. This lowers the expected barrier height along folding paths, making transitions between conformers more probable under the bridge. The result is a more efficient exploration of the conformational space compared to using the untilted reference process.
Road network experiments
On a road network derived from the learned approach, roll-outs of the exact bridge match the target distribution within sampling error. On networks containing millions of intersections, the memory required by the exact bridge grows linearly with the number of intersections. This scalability property makes the method applicable to large urban or infrastructure graphs.
Practical implications
For researchers and engineers working with graph-based optimal transport, the main takeaway is that Feynman-Kac tilting provides an exact alternative to learned control. The alternating rescaling algorithm requires only sparse matrix operations and converges at a rate predictable from the endpoint distributions. The method scales to million-node networks with linear memory, and the quadratic-congestion interpretation opens a route from best-response dynamics to convex optimization.