Exactly solving cost-aware mass transport on graphs with matrix methods
Cost-augmented Schrödinger bridges on graphs are exactly solvable: a Feynman-Kac tilt replaces learned control
Machine Learning
Summary
Moving resources or things between points on a network often has costs depending on the path taken. The authors showed a new way to find the best paths exactly without learning or approximations by changing the underlying network with a special mathematical tilt. This approach works faster and with less memory, even on huge networks, and can model complicated costs like congestion. Their method matches or improves on previous learned approaches and gives clear error bounds during optimization.
What this means in practice
- •For transport planners: Optimize routing strategies on large road networks incorporating travel costs with exact, memory-efficient computations that avoid approximations.
- •For computational biologists: Model protein folding pathways considering energy barriers using a mathematically exact transport framework to predict folding behavior more accurately.
Authors
Akshay Balsubramani
Abstract
The generalized Schrödinger bridge on a graph moves mass between two distributions while charging a cost for the states visited. It has been approached by learning the rates of a controlled continuous-time Markov chain, with a temporal-difference penalty that restores the cost. 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, and the penalty is unnecessary. The bridge is computed exactly by alternating two endpoint rescalings, each one sparse matrix-exponential application; nothing is discretized in time or learned. The alternation converges at a rate set by the endpoint coupling alone. For a quadratic congestion cost on time-averaged occupancies, damped best response around the exact bridge is gradient descent on a strongly convex function, and its residual bounds its error. On a protein-folding model, a free-energy cost lowers the expected barrier of the folding paths. On the learned approach's road network, roll-outs of the exact bridge match the target within sampling error, and on networks with millions of intersections its memory grows linearly.