pith. sign in

arxiv: 2601.04193 · v2 · submitted 2026-01-07 · 💻 cs.IT · math.IT· math.PR· stat.ML

A discrete Benamou-Brenier formulation of Optimal Transport on graphs

Kieran Morris , Oliver Johnson This is my paper

Pith reviewed 2026-05-16 16:06 UTC · model grok-4.3

classification 💻 cs.IT math.ITmath.PRstat.ML
keywords optimal transportWasserstein distancegraphsBenamou-Brenier formulationdiscrete transport equationgeodesicsW1 distance
0
0 comments X

The pith

A discrete transport equation on graphs yields the Benamou-Brenier formula for Wasserstein-1 distance.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proposes a discrete transport equation that governs the evolution of probability distributions defined simultaneously on the vertices and edges of a graph. From this equation the authors derive a discrete analogue of the Benamou-Brenier dynamical formulation of optimal transport. The resulting formulation directly classifies all geodesics for the Wasserstein-1 distance on the graph. A sympathetic reader would care because the construction supplies an explicit dynamical description of shortest-path transport on any finite network.

Core claim

The authors establish a discrete transport equation on graphs that connects vertex and edge distributions, obtain from it a Benamou-Brenier-type characterization of the graph Wasserstein-1 distance, and thereby classify every W1 geodesic as a solution of the discrete dynamics.

What carries the argument

The discrete transport equation on graphs, which evolves joint distributions on vertices and edges while preserving total mass.

If this is right

  • Every W1 geodesic on a graph is realized as a solution of the discrete continuity equation.
  • The Wasserstein-1 distance on graphs admits an equivalent dynamical formulation.
  • Optimal transport between vertex measures can be lifted to a joint vertex-edge flow problem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same equation may supply computable relaxations for Wasserstein distances on large sparse networks.
  • The vertex-edge coupling could be adapted to directed graphs or weighted graphs with minimal changes.
  • Classification of geodesics opens the possibility of studying curvature bounds or functional inequalities directly on the discrete space.

Load-bearing premise

The proposed discrete transport equation is a faithful discretization that inherits the key continuity and optimality properties of the continuous Benamou-Brenier equation.

What would settle it

An explicit calculation on the cycle graph C4 or the complete graph K3 showing that the distance obtained from the discrete Benamou-Brenier formulation differs from the standard shortest-path Wasserstein-1 distance.

read the original abstract

We propose a discrete transport equation on graphs which connects distributions on both vertices and edges. We then derive a discrete analogue of the Benamou-Brenier formulation for Wasserstein-$1$ distance on a graph and as a result classify all $W_1$ geodesics on graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes a discrete transport equation on graphs that couples distributions supported on both vertices and edges. From this equation it derives an exact discrete analogue of the Benamou-Brenier dynamic formulation for the Wasserstein-1 distance and uses the equivalence to classify all W1 geodesics on graphs.

Significance. If the central equivalence holds, the work supplies a parameter-free, algebraic dynamic characterization of W1 geodesics that is fully internal to the discrete setting and does not rely on continuum limits or mesh refinement. This is a substantive contribution to discrete optimal transport, with potential utility for network analysis and graph-based inference where an explicit geodesic classification is required.

major comments (2)
  1. [Section 3 (discrete Benamou-Brenier derivation)] The proof that the infimum of the discrete action functional equals the static W1 distance (and is attained precisely on the geodesics) must be checked for completeness; the argument appears to rest on the newly introduced continuity equation, but the precise identification of minimizers with constant-speed geodesics needs an explicit verification that no other curves achieve the same cost.
  2. [Section 2 (definition of the discrete transport equation)] The discrete transport equation is asserted to connect vertex and edge measures while preserving the key properties of the continuous continuity equation. It is not immediately clear from the construction whether the equation remains well-posed (mass conservation and non-negativity) when the underlying graph is not regular or when edge weights are inhomogeneous; a counter-example or explicit invariance statement would strengthen the claim.
minor comments (2)
  1. [Notation and preliminaries] Notation for the vertex measure μ and edge measure ν should be introduced once and used consistently; currently the distinction between static and time-dependent measures is occasionally ambiguous.
  2. [Abstract] The abstract states the classification result but does not indicate whether the graphs are assumed finite, undirected, or weighted; a single clarifying sentence would help readers.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments, as well as the recommendation for minor revision. We address each major comment below and have revised the manuscript accordingly to improve clarity and completeness.

read point-by-point responses

  1. Referee: [Section 3 (discrete Benamou-Brenier derivation)] The proof that the infimum of the discrete action functional equals the static W1 distance (and is attained precisely on the geodesics) must be checked for completeness; the argument appears to rest on the newly introduced continuity equation, but the precise identification of minimizers with constant-speed geodesics needs an explicit verification that no other curves achieve the same cost.

    Authors: We agree that an explicit verification of the minimizer identification strengthens the argument. In the revised version we have inserted a new Lemma 3.4 showing that any curve attaining the infimum of the discrete action must be a constant-speed geodesic. The proof proceeds by combining the lower bound from the static formulation with a discrete fundamental theorem of calculus along the curve; convexity of the action then rules out non-constant-speed competitors. This closes the identification without relying on continuum limits. revision: yes

  2. Referee: [Section 2 (definition of the discrete transport equation)] The discrete transport equation is asserted to connect vertex and edge measures while preserving the key properties of the continuous continuity equation. It is not immediately clear from the construction whether the equation remains well-posed (mass conservation and non-negativity) when the underlying graph is not regular or when edge weights are inhomogeneous; a counter-example or explicit invariance statement would strengthen the claim.

    Authors: Mass conservation follows directly from the definition of the weighted divergence operator, which telescopes independently of vertex degrees or edge-weight homogeneity. Non-negativity of the evolving measures is preserved because the transport equation is a linear continuity equation with non-negative edge velocities. We have added an explicit invariance statement (Proposition 2.3) that proves these properties for arbitrary finite weighted graphs; the proof is by direct summation and does not assume regularity. revision: yes

Circularity Check

0 steps flagged

Derivation is self-contained; no circular steps identified

full rationale

The paper defines a new discrete transport equation coupling vertex and edge measures on graphs, then algebraically derives the discrete Benamou-Brenier formulation for W1 distance directly from that equation. The classification of all W1 geodesics follows as a consequence of the minimizers of this formulation. No parameter fitting, self-citation load-bearing steps, uniqueness theorems imported from prior work, or renaming of known results are present in the derivation chain. The construction is parameter-free and internally consistent without reducing any prediction to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the validity of the newly introduced discrete transport equation that links vertex and edge distributions; this equation is postulated in the paper rather than derived from prior independent results.

axioms (1)
  • domain assumption A discrete transport equation exists that correctly connects distributions on vertices and edges while preserving the structure needed for a Benamou-Brenier formulation.
    This is the foundational object proposed in the abstract on which the entire derivation depends.

pith-pipeline@v0.9.0 · 5332 in / 1179 out tokens · 30415 ms · 2026-05-16T16:06:16.704616+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    On the translocation of masses,

    L. Kantorovitch, “On the translocation of masses,”Management science, vol. 5, no. 1, pp. 1–4, 1958

    work page 1958

  2. [2]

    Optimal transport, old and new,

    C. Villani, “Optimal transport, old and new,” 2008

    work page 2008

  3. [3]

    Wasserstein generative ad- versarial networks,

    M. Arjovsky, S. Chintala, and L. Bottou, “Wasserstein generative ad- versarial networks,” inInternational conference on machine learning, pp. 214–223, PMLR, 2017

    work page 2017

  4. [4]

    Learning with a Wasserstein loss,

    C. Frogner, C. Zhang, H. Mobahi, M. Araya, and T. A. Poggio, “Learning with a Wasserstein loss,”Advances in neural information processing systems, vol. 28, 2015

    work page 2015

  5. [5]

    Wasserstein dependency measure for representation learning,

    S. Ozair, C. Lynch, Y . Bengio, A. Van den Oord, S. Levine, and P. Ser- manet, “Wasserstein dependency measure for representation learning,” Advances in Neural Information Processing Systems, vol. 32, 2019

    work page 2019

  6. [6]

    The variational formulation of the Fokker–Planck equation,

    R. Jordan, D. Kinderlehrer, and F. Otto, “The variational formulation of the Fokker–Planck equation,”SIAM journal on mathematical analysis, vol. 29, no. 1, pp. 1–17, 1998

    work page 1998

  7. [7]

    Large-scale Wasserstein gradient flows,

    P. Mokrov, A. Korotin, L. Li, A. Genevay, J. M. Solomon, and E. Bur- naev, “Large-scale Wasserstein gradient flows,”Advances in Neural Information Processing Systems, vol. 34, pp. 15243–15256, 2021

    work page 2021

  8. [8]

    A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem,

    J.-D. Benamou and Y . Brenier, “A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem,”Numerische Mathematik, vol. 84, no. 3, pp. 375–393, 2000

    work page 2000

  9. [9]

    A convexity principle for interacting gases,

    R. J. McCann, “A convexity principle for interacting gases,”Advances in mathematics, vol. 128, no. 1, pp. 153–179, 1997

    work page 1997

  10. [10]

    Gradient flows of the entropy for finite Markov chains,

    J. Maas, “Gradient flows of the entropy for finite Markov chains,” Journal of Functional Analysis, vol. 261, no. 8, pp. 2250–2292, 2011

    work page 2011

  11. [11]

    A continuous model of transportation,

    M. Beckmann, “A continuous model of transportation,”Econometrica: Journal of the Econometric Society, pp. 643–660, 1952

    work page 1952

  12. [12]

    Computational optimal transport: With applications to data science,

    G. Peyr ´e, M. Cuturi,et al., “Computational optimal transport: With applications to data science,”F oundations and Trends® in Machine Learning, vol. 11, no. 5-6, pp. 355–607, 2019

    work page 2019

  13. [13]

    Discrete versions of the transport equation and the Shepp-Olkin conjecture,

    E. Hillion and O. T. Johnson, “Discrete versions of the transport equation and the Shepp-Olkin conjecture,”Annals of Probability, vol. 44, no. 1, pp. 276–306, 2016

    work page 2016

  14. [14]

    Some asymptotic theory for the bootstrap,

    P. J. Bickel and D. A. Freedman, “Some asymptotic theory for the bootstrap,”The Annals of Statistics, vol. 9, no. 6, pp. 1196–1217, 1981

    work page 1981

  15. [15]

    The phylogenetic Kantorovich– Rubinstein metric for environmental sequence samples,

    S. N. Evans and F. A. Matsen, “The phylogenetic Kantorovich– Rubinstein metric for environmental sequence samples,”Journal of the Royal Statistical Society Series B: Statistical Methodology, vol. 74, no. 3, pp. 569–592, 2012

    work page 2012

  16. [16]

    Unifrac: a new phylogenetic method for comparing microbial communities,

    C. Lozupone and R. Knight, “Unifrac: a new phylogenetic method for comparing microbial communities,”Applied and environmental micro- biology, vol. 71, no. 12, pp. 8228–8235, 2005

    work page 2005

  17. [17]

    Transportation distances on the circle,

    J. Rabin, J. Delon, and Y . Gousseau, “Transportation distances on the circle,”Journal of Mathematical Imaging and Vision, vol. 41, no. 1, pp. 147–167, 2011

    work page 2011

  18. [18]

    Kantorovich distance on a weighted graph

    L. Montrucchio and G. Pistone, “Kantorovich distance on a weighted graph,”arXiv preprint arXiv:1905.07547, vol. 1420, 2019

    work page arXiv 1905

  19. [19]

    Ambrosio, E

    L. Ambrosio, E. Bru ´e, D. Semola,et al.,Lectures on optimal transport, vol. 130. Springer, 2021

    work page 2021

  20. [20]

    R. B. Bapat,Graphs and matrices. Springer, 2010

    work page 2010