Learning Discrete Diffusion on Graphs via Free-Energy Gradient Flows

Dario Rancati, Jan Maas, Francesco Locatello · 2026

Read Learning Discrete Diffusion on Graphs via Free-Energy Gradient Flows by Dario Rancati, Jan Maas, Francesco Locatello (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-11311.txt.

Introduction

Rancati, Maas, and Locatello learn discrete diffusion on graphs through free-energy gradient flows. They extend the Wasserstein-2 gradient-flow picture from continuous spaces. A metric WK on the simplex of probability distributions lets them interpret paths such as the discrete heat equation as gradient flows of free-energy functionals. Their method recovers the underlying functional from JKO optimality rules. It optimizes a simple squared loss, trains fast, and needs no single sampled paths.

Catalog record

CREATORDario Rancati, Jan Maas, Francesco Locatello
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE85072
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.11311

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Learning Discrete Diffusion on Graphs via Free-Energy Gradient Flows Dario Rancati, Jan Maas, Francesco Locatello Abstract Diffusion-based models on continuous spaces have seen substantial recent progress through the mathematical framework of gradient flows, leveraging the Wasserstein-2 ( W 2 {W}_{2} ) metric via the Jordan-Kinderlehrer-Otto (JKO) scheme. Despite the increasing popularity of diffusion models on discrete spaces using continuous-time Markov chains, a parallel theoretical framework based on gradient flows has remained elusive due to intrinsic challenges in translating the W 2 {W}_{2} distance directly into these settings. In this work, we propose the first computational approach addressing these challenges, leveraging an appropriate metric W K W_{K} on the simplex of probability distributions, which enables us to interpret widely used discrete diffusion paths, such as the discrete heat equation, as gradient flows of specific free-energy functionals. Through this theoretical insight, we introduce a novel methodology for learning diffusion dynamics over discrete spaces, which recovers the underlying functional directly by leveraging first-order optimality conditions for the JKO scheme. The resulting method optimizes a simple quadratic loss, trains extremely fast, does not require individual sample trajectories, and only needs a numerical preprocessing computing W K W_{K} -geodesics. We validate our method through extensive numerical experiments on synthetic data, showing that we can recover the underlying functional for a variety of graph classes. 1 Overview Over the last few years, a broad family of diffusion-based methods has modeled the evolution of a particle population as a trajectory of probability measures in a metric space ( 7 ; 44 ; 47 ; 10 ; 32 ; 36 ; 23 ) . A central tool behind many of these approaches is the following discretization scheme, introduced by Jordan, Kinderlehrer and Otto in their seminal paper ( 26 ) : p_{t+1}:=\underset{p\in\mathcal{P}(\mathbb{R}^{n})}{\arg\min}\left\{\mathcal{F}(p)+\frac{1}{2\tau}W_{2}(p,p_{t})^{2}\right\}. (1) Each step of this scheme (typically called the JKO scheme) solves a proximal optimization problem in the Wasserstein-2 ( W_{2} ) geometry under the influence of the functional \mathcal{F} . This line of work is mostly known for the striking mathematical property of identifying certain PDEs, such as the Fokker-Planck equation, with the gradient flow ( 1 ) of free-energy functionals which are the sum of a potential and an entropic term. Nonetheless, this variational viewpoint is also attractive from the practical point of view of machine learning: models built off this idea typically exhibit fast training loops and operate directly at the sample level, with no need for trajectory-level observations ( 7 ; 37 ) . In parallel, models based on probability flows on discrete spaces have recently gained significant popularity, impacting areas such as language modelling, molecule generation and machine learning for material sciences ( 5 ; 29 ; 8 ; 38 ; 9 ; 42 ; 13 ; 48 ; 27 ) . These models typically study discrete probability evolutions structured by an underlying, known, Markov kernel K that specifies the state-transition probabilities at each time-step. In this context, however, a direct translation of the JKO framework in the W_{2} metric breaks down: for finite state spaces, any non-constant curve of probability distributions has infinite W_{2} -metric derivative, hence common trajectories such as the discrete heat equation cannot be interpreted as a W_{2} -gradient flow of any functional. In this work, we introduce the first machine learning method that addresses this difficulty, allowing us to learn functionals from their gradient-flow trajectories in the space of probability measures via a JKO-style proximal scheme. Our framework builds on a body of mathematical works on probability gradient flows over discrete spaces ( 30 ; 31 ; 11 ; 16 ; 15 ; 17 ; 14 ; 12 ) . These works rely on the use of a different metric W_{K} depending on the Markov kernel K through a discrete analog of the Benamou-Brenier formula ( 4 ) . We stress that these constructions were developed in pure mathematics, and it is not obvious that they would have computational implications. In fact, they have seen almost no practical adoption, with minor exceptions in applied mathematics ( 17 ) , and, within machine learning, only in the specific case of discrete samplers ( 43 ) . In our work, we translate this theory to derive a practical, implementable methodology, building a principled discrete analogue of the JKO scheme, which is already successful in continuous settings. Within the geometry induced by W_{K} , we use the fact that important discrete diffusion trajectories (such as the discrete heat equation on a graph) arise as gradient flows of free-energy functionals, in direct analogy with the continuous case. We devise a strategy to learn these functionals given this characterization, based on first-order necessary conditions of optimality for our discrete JKO scheme, requiring only the computation of geodesics in W_{K} as a preprocessing step, for which we build a customized and efficient numerical routine. The resulting training loop is lightweight, and in experiments we benchmark extensively and outperform standard Markov jump-process baselines. We summarize our contributions as follows: • We translate the theoretical framework for probability gradient flows in discrete spaces into the context of machine learning. In particular, we focus on the tools that enable applications of this theory to computational domains. While this theory already existed in pure mathematics, it had seen close to no computational applications and was largely inaccessible to researchers in the ML field. A key barrier was that results on the uniqueness of solutions for the discrete JKO scheme and on the form of its gradients in the W_{K} metric are critical for implementation, but were missing. • Based on said framework, we devise a practical strategy to learn discrete gradient flows from temporal snapshots. Our approach is based on imposing first-order necessary conditions for the discrete JKO scheme, and its main components are a numerical routine to numerically compute geodesics and a quadratic-loss training loop based on said geodesics; • We extensively benchmark our framework on a variety of graph classes, sizes and regimes. Through comparison with existing methods for learning Markov Jump Process dynamics, we find our method to have better performances while being extremely favorable in both training time, number of parameters, and scaling behavior. 2 Problem Setup We are interested in studying probability flows on a finite space \mathcal{X}=\left\{x_{1},...,x_{N}\right\} equipped with a Markov transition kernel K\in\mathbb{R}^{N\times N} , that is, a non-negative, row-stochastic real matrix. We make the standard assumption for K to be irreducible and reversible ( 8 ; 29 ) : irreducibility implies in particular the existence and uniqueness of an invariant probability measure \pi such that \pi^{T}K=\pi^{T} . We denote by: \begin{split}&\mathcal{P}(\mathcal{X}):=\\ &\left\{\rho:\mathcal{X}\rightarrow\mathbb{R},\;\;\rho(x)\geq 0\;\;\forall x\in\mathcal{X},\;\ \sum_{x\in\mathcal{X}}\pi(x)\rho(x)=1\right\}\end{split} the set of all probability densities on \mathcal{X} , and by \mathcal{P}_{*}(\mathcal{X})\subseteq\mathcal{P}(\mathcal{X}) the subset of densities that are strictly positive. Throughout the paper, we use \rho to denote densities and p to denote probabilities. The core example of the probability evolution processes we are interested in is the discrete heat equation : \frac{\mathrm{d}}{\mathrm{d}t}\rho_{t}=(K-I)\rho_{t}, (2) which is the most widely used process in discrete generative applications ( 29 ; 8 ) . Our goal is to describe processes such as ( 2 ) as gradient flows of functionals on \mathcal{P}(\mathcal{X}) , mirroring the continuous case ( 26 ; 7 ; 44 ) : in

Read the complete text