Skip to main content
Back

GFlowNets Were Secretly Solving Optimal Transport All Along

A new paper proves that a trained GFlowNet implicitly solves an optimal transport problem, opening a scalable neural path to OT on large graphs.

Paper, Full Access
  • Core result: A new paper proves that a minimum-flow GFlowNet trained on a graph implicitly solves a Kantorovich optimal transport problem.
  • Key insight: Fixing the initial flow distribution collapses the GFlowNet objective to OT with graph shortest-path costs; sampling trajectories recovers the optimal coupling.
  • Scalability: Neural parameterization of edge flows enables OT on large graphs where exact solvers are intractable.
  • Validation: Experiments confirm agreement with exact OT solvers and demonstrate high-quality transport plans on graph benchmarks.
  • Applications: Opens GFlowNet machinery to OT on knowledge graphs, molecular graphs, and domain adaptation; also imports OT theory into GFlowNet analysis.
  • Availability: Paper on arXiv; no code repository linked at time of publication.

Two fields that have been developing in parallel just turned out to be secretly solving the same problem. In a new paper, "Your GFlowNet Secretly Learns an Optimal Transport Plan", Maksimov, Morozov, Belomestny, and Samsonov establish a rigorous theoretical bridge between Generative Flow Networks (GFlowNets) and optimal transport (OT) -- and then use that bridge to build a scalable neural OT solver for large graphs.

Two tools, one problem

To understand why this matters, it helps to know what each framework does on its own.

GFlowNets are a generative modeling framework introduced by Bengio et al. Their sampling policy is trained to make the probability of sampling an object approximately proportional to the value of a given reward function applied to that object. Concretely, GFlowNets sample an object from an unnormalized distribution as a constructive generative process, where discrete actions iteratively modify a state -- a partially constructed object. Think of it as an agent walking through a graph, building up a structured output step by step. Instead of simply maximizing a reward, GFlowNets learn to sample objects with a probability proportional to a predefined reward function, allowing them to discover diverse sets of high-reward candidates within exceptionally large sample spaces.

Optimal transport (OT) is a classical mathematical framework for moving probability mass from one distribution to another as cheaply as possible. Optimal transport gives a framework for comparing measures in a Lagrangian framework -- essentially, one pays a cost for transporting one measure to another. The Kantorovich formulation -- the relaxed, probabilistic version -- asks for a coupling: a joint distribution over source and target that minimizes expected transport cost. Solving this exactly on large graphs is expensive, scaling poorly with the number of nodes.

The hidden equivalence

The paper's core result is surprisingly clean. The authors study a specific variant called a minimum-flow GFlowNet -- a GFlowNet trained on a graph that may contain cycles (non-acyclic), where the objective is to minimize total flow while satisfying boundary conditions. They prove that when you fix the initial flow distribution, the minimum-flow GFlowNet's training objective reduces exactly to a Kantorovich OT problem, where the transport costs are the shortest-path distances along the graph's edges.