ISTA Bridges Discrete Optimal Transport and Diffusion, Beating OpenFIM in Minutes
New method translates a decade-old piece of pure mathematics into a fast, quadratic-loss training loop for learning discrete diffusion dynamics on graphs.
ProTakeaways
- First practical method translating discrete optimal transport theory into a trainable ML pipeline for graph diffusion.
- Uses the W_K metric from Maas 2011 where the discrete heat equation becomes a gradient flow of KL divergence.
- Learns free-energy functionals via first-order optimality of a discrete JKO scheme with a simple quadratic loss.
- Geodesics computed in O(N^3) via Cholesky and Schur complement, done once as preprocessing.
- Beats OpenFIM baseline with Hellinger 0.06 vs 0.14, using 10k parameters and under a minute of training.
- Currently synthetic-only; does not yet scale to language-sized Hamming graphs with n^d states.
Diffusion models have taken over continuous domains partly because of a beautiful mathematical fact: many diffusion PDEs, including the Fokker-Planck equation, can be seen as gradient flows of free-energy functionals in Wasserstein-2 (W2) space. That geometric picture, formalized by the Jordan-Kinderlehrer-Otto (JKO) scheme, gives clean training objectives, fast trainers, and no need to observe individual particle trajectories. A new paper from ISTA ports that machinery to discrete state spaces, where the W2 story famously breaks.
The obstruction on discrete spaces is sharp. On a two-point space, any non-constant solution of the discrete heat equation has infinite W2 metric derivative. So the discrete heat equation, the workhorse behind most modern discrete diffusion models for text and molecules, cannot arise as a W2 gradient flow of any functional.
Borrowing a metric from pure math
The fix comes from a line of work in optimal transport that most ML researchers have never touched. In place of W2, the authors use a metric called W_K, built from the Markov kernel K itself via a discrete analogue of the Benamou-Brenier formula. The key modelling choice is the mobility function, which controls how the cost of moving mass between two states depends on the mass already there. With the logarithmic mean as the mobility, something clean happens: the discrete heat equation becomes the gradient flow of the KL divergence with respect to the invariant measure, mirroring exactly how the continuous heat equation is the gradient flow of Shannon entropy in W2.