📊 statistics

A discrete Benamou-Brenier formulation of Optimal Transport on graphs

This paper proposes a discrete transport equation on graphs that connects distributions on vertices and edges, leading to a discrete Benamou-Brenier formulation for the Wasserstein-1 distance and a complete classification of all $W_1$ geodesics on graphs.

Original authors: Kieran Morris, Oliver Johnson

Published 2026-04-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kieran Morris, Oliver Johnson

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a logistics manager for a massive, complex delivery network. You have a pile of packages (mass) scattered across a city (a graph made of intersections and roads), and you need to move them to a new location. Your goal is simple: move everything as cheaply as possible.

In the world of mathematics, this is called Optimal Transport.

For a long time, mathematicians had two ways to solve this:

The "Snapshot" method: Look at where the packages start and where they end, then figure out the cheapest map to get them there all at once.
The "Movie" method (Benamou-Brenier): Imagine the packages flowing like water over time. You track the speed of the water and the amount of water at every moment. The "cost" is the energy required to keep that water moving.

The problem? The "Movie" method works beautifully for smooth, continuous spaces (like a flat field), but it breaks down when you are on a discrete graph (like a city grid, a social network, or a computer chip) where you can only move from one specific node to another, not float freely in between.

This paper by Kieran Morris and Oliver Johnson solves that problem. They figured out how to create a "Movie Method" for graphs.

Here is the breakdown of their discovery using simple analogies:

1. The Problem: The "Missing Middle"

Imagine you have a pile of sand on a hill (Node A) and you want to move it to a valley (Node B).

The Old Way: You just calculate the total distance and multiply by the weight. Easy.
The "Movie" Way: You need to describe how the sand flows. In a smooth world, the sand flows continuously. But on a graph, the sand jumps from one rock to another. If you try to force the smooth "movie" math onto a graph, the sand seems to vanish or appear out of nowhere because the math expects a continuous stream, not a jump.

2. The Solution: The "Traffic Light" System

The authors realized that to make the "movie" work on a graph, you need three things, not just two. Think of it like a traffic system:

$f$ (The Traffic): The amount of "stuff" (probability mass) sitting at each intersection (node) at any given time.
$v$ (The Speed): How fast the traffic is moving along a specific road (edge).
$g$ (The Traffic Density): This is the new, clever ingredient. In a smooth world, the speed and the amount of stuff are linked. But on a graph, the "stuff" moving along a road isn't just the stuff at the intersection; it's a specific distribution of stuff on the road itself.

The Analogy:
Imagine a conveyor belt between two factories.

$f$ is the number of boxes in Factory A and Factory B.
$v$ is how fast the belt is spinning.
$g$ is the pattern of boxes on the belt. Are they packed tight? Are they spread out?

The authors discovered that to calculate the cost of moving the boxes correctly, you don't just multiply speed by the number of boxes at the factory. You multiply the speed by the density of boxes on the belt.

3. The "Tail" Trick (For Trees)

The paper first solves this for Trees (networks with no loops, like a family tree or a river system).
They used a clever trick called "Tail Distributions."

Imagine standing at a specific intersection. A "Tail" is everything "downstream" from you.
Instead of tracking every single box, they realized you only need to track how the total amount of stuff in the "Tail" changes over time.
If the "Tail" loses 5 boxes, those 5 boxes must have crossed the road you are standing on. This makes the math much simpler and allows them to prove exactly how to move the stuff with minimum energy.

4. The Big Breakthrough: General Graphs

The real magic happens when they apply this to any graph, even ones with loops (like a city with roundabouts).

In a city with loops, there are many ways to get from A to B. You could go the "long way round" or the "short way."
The authors proved that even with these loops, you can still find the perfect "movie" (a path of distributions) that minimizes the cost.
They showed that the "cheapest movie" is always a Constant Speed Geodesic.
- Translation: The most efficient way to move your packages is to move them at a steady, unchanging pace from start to finish. You don't speed up, slow down, or stop. You just flow steadily.

5. Why Does This Matter?

This isn't just about moving sand or packages. This math is the engine behind:

Machine Learning: Training AI models to understand how data distributions change (e.g., turning a picture of a cat into a picture of a dog).
Network Analysis: Understanding how information or viruses spread through social networks.
Image Processing: Morphing one image into another smoothly.

The Takeaway

The authors took a complex, continuous idea (fluid dynamics) and built a bridge to the discrete world (graphs). They showed that even in a world of jumps and steps, the most efficient path is always a steady, constant flow.

They gave us a new "rulebook" (a discrete transport equation) that tells us exactly how to calculate the cost of moving things on a network, ensuring that whether you are moving data on a computer chip or people in a city, you can always find the most efficient route.

1. Problem Statement

The paper addresses the challenge of formulating the Wasserstein-1 distance ( $W_1$ ) on discrete domains (specifically graphs) using a Benamou-Brenier dynamic formulation.

Context: In continuous spaces ( $\mathbb{R}^d$ ), the Benamou-Brenier formulation re-parameterizes the static Optimal Transport problem (minimizing transport cost) into a dynamic problem involving a time-dependent probability density $f_t$ and a velocity field $v_t$ , constrained by the continuity equation $\partial_t f_t + \nabla \cdot (f_t v_t) = 0$ .
The Gap: While discrete analogues exist for $W_2$ (Erbar-Maas metric), they do not correspond to the true $W_2$ distance. For $W_1$ , a true discrete Benamou-Brenier formulation was previously established only for the integer line $\mathbb{Z}$ (Hillion and Johnson). The problem of extending this formulation to general graphs and characterizing the resulting geodesics remained open.
Goal: To derive a discrete transport equation and an associated energy functional on general graphs that exactly recovers the static $W_1$ distance and to classify the constant-speed geodesics that minimize this functional.

2. Methodology

A. Discrete Transport Equation

The authors introduce a novel discrete transport equation involving a triple $(f, v, g)$ :

$f(t)$ : A path of probability distributions defined on the vertices $V$ of a graph $G=(V, E)$ .
$v(t)$ : A velocity function defined on the edges $E$ .
$g(t)$ : A distribution function defined on the edges $E$ .

The equation is defined using the incidence matrix $\Omega$ of the graph:
$\partial_t f = \Omega \cdot (v \cdot g)$
where the product $v \cdot g$ is component-wise on the edges. This generalizes the continuous continuity equation. The term $v \cdot g$ represents the flow of mass across edges.

B. Energy Functional

To formulate the distance, the authors define an energy functional $I_q(v, g)$ for $q \geq 1$ :
$I_q(v, g) = \left( \int_0^1 \sum_{k \in E} g_k(t) |v_k(t)|^q \, dt \right)^{1/q}$
The proposed discrete distance $V_q(f(0), f(1))$ is the infimum of this energy over all triples $(f, v, g)$ satisfying the transport equation and boundary conditions $f(0), f(1)$ .

C. Analytical Approach

The paper proceeds in two main stages:

Tree Graphs: The authors first solve the problem for trees. They utilize tail distributions (analogous to cumulative distribution functions on $\mathbb{Z}$ ) to invert the transport equation. This allows them to explicitly construct the minimizing triple and prove that $V_q = W_1$ .
General Graphs: For graphs with cycles, the incidence matrix is not invertible. The authors use a reduced formulation based on the Beckmann problem. They show that any solution $(v, g)$ can be transformed into a "constant speed" solution without increasing the energy, effectively reducing the search space to pairs where the flow magnitude is uniform across edges at any given time.

3. Key Contributions

Discrete Transport Equation: The definition of the transport equation $\partial_t f = \Omega \cdot (vg)$ , which correctly models mass conservation on graphs by introducing an edge-based distribution $g$ alongside velocity $v$ .
Benamou-Brenier Theorem for $W_1$ :
- Theorem 1 (Trees): Proves that for rooted trees, the infimum of the energy functional $I_2$ (and generally $I_q$ ) subject to the transport equation is exactly the static $W_1$ distance.
- Theorem 2 (General Graphs): Extends the result to any connected graph, proving $V_q(f(0), f(1)) = W_1(f(0), f(1))$ for all $q \geq 1$ .
Characterization of Geodesics:
- Proposition 4: Establishes that the paths $f(t)$ induced by minimizing triples $(v, g)$ with constant speed ( $|v_k| = c$ ) are exactly the constant speed $W_1$ geodesics.
- Corollary 1: Demonstrates that convex interpolations $f(t) = (1-t)f(0) + tf(1)$ are always constant speed $W_1$ geodesics on graphs.
- Non-Uniqueness: The paper highlights that geodesics are not unique. For example, between two Binomial distributions, both the linear interpolation of the distributions (convex) and the interpolation of the underlying parameter $p(t)$ (non-linear) can be valid constant speed geodesics.

4. Key Results

Equivalence of Formulations: The dynamic formulation (minimizing kinetic energy over time) is mathematically equivalent to the static Kantorovich formulation for $W_1$ on graphs.
Constant Speed Solutions: The authors prove that for any valid transport path, there exists a "constant speed" re-parametrization that minimizes the energy. In this optimal state, the velocity magnitude $|v|$ is constant in time.
Metric Properties: The functional $V_q$ satisfies the triangle inequality, symmetry, and positive definiteness, confirming it is a valid metric on the space of probability measures on the graph.
Relation to Beckmann: The formulation is shown to be a time-dependent generalization of the Beckmann formulation (which is time-independent and minimizes total flow cost).

5. Significance

Theoretical Unification: This work bridges the gap between static optimal transport (Kantorovich/Beckmann) and dynamic optimal transport (Benamou-Brenier) in the discrete setting. It resolves the open problem of finding a true $W_1$ dynamic formulation on general graphs.
Algorithmic Implications: By characterizing geodesics via the transport equation, the paper provides a framework for Wasserstein Gradient Flows on graphs. This is crucial for machine learning applications where one needs to evolve probability distributions on network structures (e.g., social networks, biological networks) while minimizing transport cost.
Geometric Insight: The classification of geodesics reveals that on graphs, the "straightest" path between distributions is not unique. The existence of both linear (convex) and non-linear (parameter-based) geodesics offers new perspectives on how probability mass moves through network topologies.
Generalizability: The methodology using incidence matrices and tail distributions provides a robust toolkit for analyzing optimal transport on arbitrary discrete structures, extending beyond simple paths or trees.

In summary, Morris and Johnson successfully generalize the Benamou-Brenier formulation to discrete graphs, proving that the dynamic minimization of a specific energy functional recovers the exact $W_1$ distance and providing a complete characterization of the geodesics that achieve this minimum.