arxiv: 2605.07408 · v1 · submitted 2026-05-08 · 🧮 math.NA · cs.NA

Recognition: no theorem link

Newton's method for optimal transport problem on graphs

Haomin Zhou, Jianbo Cui, Luca Dieci, Qujiangxue Chen

Pith reviewed 2026-05-11 02:12 UTC · model grok-4.3

classification 🧮 math.NA cs.NA

keywords optimal transportgraphsNewton methodspanning treeBenamou-Brenierupwind discretizationdynamical transportinverse problems

0 comments

The pith

A spanning-tree gauge reduces Newton's method for dynamical optimal transport on graphs to a sparse, well-posed linear system at each step.

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

The authors adapt Newton's method to solve the Benamou-Brenier formulation of optimal transport on a connected graph, where vertex densities and edge velocities satisfy a continuity equation. Direct application runs into non-uniqueness when the graph contains cycles and can produce negative densities. By selecting a spanning tree, they fix a gauge that removes the redundant cycle variables, leaving an independent set whose Jacobian yields a sparse, nonsingular linear system. On the special case of lattice graphs that discretize a continuous domain, an upwind finite-difference scheme together with a CFL-type restriction on the time step guarantees that densities stay positive. The same reduced scheme is then shown to handle inverse transport problems and flow analysis on random graphs and social networks.

Core claim

We introduce a finite-difference-type Newton method that eliminates cycle-induced redundancies through a spanning-tree gauge, resulting in a reduced set of independent variables and a well-posed, sparse linear system. For the lattice graph arising from the continuous optimal transport problem, density positivity can also be guaranteed by using an upwind discretization subject to a CFL-type condition.

What carries the argument

The spanning-tree gauge, which selects a basis of tree edges whose velocities determine all other edge velocities via the cycle conditions, thereby removing redundant variables while preserving the continuity equation.

If this is right

The reduced linear system at each Newton step is sparse and can be solved efficiently for arbitrary connected graphs.
Density positivity holds automatically on lattice graphs when the upwind scheme obeys the CFL condition.
The same formulation applies without change to optimal transport on random graphs.
The method extends directly to inverse optimal transport problems and to flow analysis on social networks.

Where Pith is reading between the lines

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

The gauge reduction may preserve the quadratic convergence rate of Newton's method provided the chosen tree does not produce an ill-conditioned Jacobian.
Because the lattice case recovers a discrete version of continuous optimal transport, the scheme offers a practical way to compute transport maps on regular grids without extra positivity fixes.
The approach could be tested on graphs with time-dependent edge capacities to see whether the same gauge still yields stable iterations.

Load-bearing premise

That any spanning-tree gauge produces a reduced system whose solutions correspond exactly to those of the original cycle-containing system and that the CFL restriction can be met in practice without destroying Newton convergence or accuracy.

What would settle it

A concrete graph and initial data for which the Newton iterates on the reduced spanning-tree system yield a different density-velocity pair than a direct (regularized) solve of the full redundant system, or for which an upwind lattice discretization satisfying the CFL condition still produces a negative density at some vertex.

Figures

Figures reproduced from arXiv: 2605.07408 by Haomin Zhou, Jianbo Cui, Luca Dieci, Qujiangxue Chen.

**Figure 4.1.** Figure 4.1: Panel (a) illustrates the graph structure in Example 4.2, whereas panels (b) and (c) present the spanning trees employed in Comparison Test 4.3. The highlighted edges represent the corresponding spanning trees. 4.1. Algorithmic properties [PITH_FULL_IMAGE:figures/full_fig_p013_4_1.png] view at source ↗

**Figure 4.2.** Figure 4.2: Example 4.1. Comparison of the discrete W2 2 distance under different spanning spanning-tree parametrizations and the corresponding fivenode graph structure. t 0 0.2 0.4 0.6 0.8 1 ;i 0.05 0.1 0.15 0.2 0.25 0.3 0.35 ;1 ;2 ;3 ;4 ;5 ;6 ;7 (a) Evolution of nodal densities ρi(t). t 0 0.2 0.4 0.6 0.8 1 vij -4 -3 -2 -1 0 1 2 3 4 5 6 v12 v23 v34 v45 v56 v67 v78 (b) Evolution of edge velocities vi,j (t) [PITH_F… view at source ↗

**Figure 4.3.** Figure 4.3: Example 4.2. Dumbbell-graph experiment with M = 128 and |V | = N = 8 [PITH_FULL_IMAGE:figures/full_fig_p015_4_3.png] view at source ↗

**Figure 4.4.** Figure 4.4: Example 4.3. Topology recovery from the average edge velocity with temporal discretization parameter M = 128. 4.2.2. Opinion dynamics on social networks. In the previous sections, we assumed that the underlying graph G = (V, E, Ω) is given and formulated the dynamical OT problem directly on G. Here we adopt an equivalent but more modeling-oriented viewpoint: the network connectivity is specified by an ad… view at source ↗

**Figure 4.5.** Figure 4.5: Evolution of the nodal density ρ and edge velocity v from a random initial state to the uniform target state in Example 4.4, with M = 256 time steps. 4.3. A comparison test. To assess computational efficiency, we compare the wall-clock runtime of the multiple shooting method and the current Newton-based method under identical experimental settings. All experiments were performed in Matlab R2023b on macOS… view at source ↗

read the original abstract

In this paper, we study dynamical optimal transport on a connected graph from the perspective of the Benamou-Brenier formulation, where densities are assigned to vertices and velocities to edges. However, directly using Newton's method on the resulting nonlinear systems encounters two potential difficulties: (i) if the graph contains cycles, edge variables are not unique, and (ii) there is no guarantee that the density variables remain positive. To address these challenges, we introduce a finite-difference-type Newton method that eliminates cycle-induced redundancies through a spanning-tree gauge, resulting in a reduced set of independent variables and a well-posed, sparse linear system. For the lattice graph arising from the continuous optimal transport problem, density positivity can also be guaranteed by using an upwind discretization subject to a CFL-type condition. We further demonstrate the versatility of the proposed scheme by applying it to a range of problems, including optimal transport on lattices and random graphs, inverse optimal transport problems, and social network analysis.

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.

Desk Editor's Note private letter to a colleague

The paper gives a Newton solver for dynamical OT on graphs via spanning-tree gauge to drop cycles and upwind CFL for positivity, but the abstract leaves the key equivalence claim unproven.

read the letter

The paper presents a finite-difference Newton method for the Benamou-Brenier formulation of dynamical optimal transport on graphs. Edge velocities live on edges and densities on vertices, but cycles make the velocities non-unique and nothing forces densities to stay positive. Their fix is to pick a spanning tree, use it as a gauge to eliminate the redundant cycle variables, and thereby obtain a smaller sparse linear system for each Newton step. On lattice graphs they further switch to an upwind discretization that respects a CFL condition to keep densities positive throughout the iteration. They then run the scheme on lattices, random graphs, inverse problems, and a social-network example. That last part shows the method is flexible enough to move between different graph types without major re-engineering. The concrete algorithm and the range of test cases are the parts that stand out as useful. The main weakness is that the abstract simply states the gauge produces a well-posed system whose solutions match the original problem, without any derivation, isomorphism argument, or check that the reduced Jacobian has the right kernel. If the gauge choice removes components the objective actually depends on, the Newton iterates will solve a different, smaller problem. The upwind CFL claim also lacks error estimates or even a single convergence plot in the summary. These gaps make the soundness hard to judge from what is written. The work is aimed at people who already work on discrete optimal transport or network inverse problems and want a practical Newton code rather than a theoretical breakthrough. A reader who needs a working solver on graphs could extract something implementable, but would still have to verify the gauge reduction and positivity preservation themselves. I would send it to peer review because the numerical idea is straightforward and the applications are relevant; the referees can check whether the equivalence and stability arguments actually hold in the full manuscript.

Referee Report

2 major / 2 minor

Summary. The manuscript develops a Newton method for the Benamou-Brenier dynamical formulation of optimal transport on graphs, with densities at vertices and velocities on edges. To resolve non-uniqueness from cycles, a spanning-tree gauge reduces the system to independent variables, producing a sparse well-posed linear system at each Newton step. On lattice graphs approximating the continuous problem, an upwind finite-difference discretization together with a CFL-type condition is claimed to enforce positivity of densities. The scheme is tested on lattices, random graphs, inverse OT problems, and social-network examples.

Significance. If the reduced system is equivalent to the original and the positivity guarantee holds with controlled error, the work supplies a practical, sparse Newton solver for graph OT that directly addresses two common obstacles (cycle redundancy and sign violation). This could be useful for network applications and for discretizations of continuous OT, provided the numerical analysis is completed.

major comments (2)

[description of the spanning-tree gauge (likely §3)] The central claim that the spanning-tree gauge yields a reduced nonlinear system whose solutions correspond exactly to those of the cycle-containing original system is not accompanied by an explicit isomorphism or kernel analysis of the reduced Jacobian. Without this, it remains possible that the gauge projects out components on which the objective or constraints depend, so that the well-posed linear solves solve a different problem. This equivalence is load-bearing for the method's correctness.
[lattice-graph discretization and CFL analysis] The statement that the upwind discretization subject to a CFL condition guarantees density positivity on lattices is asserted without a derivation of the discrete maximum principle, a truncation-error estimate, or numerical verification that the Newton iteration still converges at the expected rate under the CFL restriction. This directly affects the claim that the scheme solves the continuous OT problem accurately.

minor comments (2)

Notation for the gauge variables and the reduced edge set should be introduced with a small diagram or explicit indexing to make the reduction step easier to follow.
The numerical examples would benefit from a table comparing iteration counts and CPU time against a direct (ungauged) Newton solver on acyclic graphs, to quantify the practical gain from the reduction.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. The two major points raised identify areas where additional theoretical detail would strengthen the presentation. We address each comment below and will revise the manuscript to incorporate the requested clarifications and analysis.

read point-by-point responses

Referee: [description of the spanning-tree gauge (likely §3)] The central claim that the spanning-tree gauge yields a reduced nonlinear system whose solutions correspond exactly to those of the cycle-containing original system is not accompanied by an explicit isomorphism or kernel analysis of the reduced Jacobian. Without this, it remains possible that the gauge projects out components on which the objective or constraints depend, so that the well-posed linear solves solve a different problem. This equivalence is load-bearing for the method's correctness.

Authors: We agree that an explicit isomorphism and kernel analysis are needed to rigorously establish equivalence. In the original manuscript the spanning-tree gauge is motivated by selecting a basis for the cut space that eliminates the cycle-space kernel of the incidence matrix, thereby reducing the number of independent edge variables while preserving the divergence constraint and the objective. However, we acknowledge that a formal statement is missing. In the revised manuscript we will add a proposition in Section 3 that (i) constructs an explicit linear isomorphism between the original and reduced variable spaces, (ii) shows that the objective functional and all constraints are invariant under this isomorphism, and (iii) proves that the reduced Jacobian is nonsingular precisely because its kernel coincides with the cycle space that has been gauged out. This will confirm that every solution of the reduced Newton system lifts uniquely to a solution of the original system. revision: yes
Referee: [lattice-graph discretization and CFL analysis] The statement that the upwind discretization subject to a CFL condition guarantees density positivity on lattices is asserted without a derivation of the discrete maximum principle, a truncation-error estimate, or numerical verification that the Newton iteration still converges at the expected rate under the CFL restriction. This directly affects the claim that the scheme solves the continuous OT problem accurately.

Authors: We thank the referee for highlighting the need for a self-contained analysis. The manuscript relies on the standard upwind finite-difference scheme for the continuity equation on the lattice together with a CFL restriction to preserve positivity, but does not derive the discrete maximum principle or provide truncation-error bounds. In the revision we will add a dedicated subsection that (i) proves a discrete maximum principle showing that non-negative initial densities remain non-negative under the upwind update when the CFL condition holds, (ii) derives a first-order truncation-error estimate for the combined space-time discretization, and (iii) reports numerical experiments on successively refined lattices that confirm the Newton iteration retains quadratic convergence rates when the CFL restriction is enforced. These additions will directly support the claim that the scheme approximates the continuous dynamical optimal-transport problem. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on standard graph gauge fixing and discretization

full rationale

The paper constructs a Newton method for dynamical OT on graphs by selecting a spanning tree to remove cycle redundancies in edge variables and applying upwind discretization with CFL for positivity on lattices. These are standard techniques from graph theory and finite-difference methods; the reduced system is defined explicitly from the original nonlinear equations without any fitted parameters, self-referential predictions, or load-bearing self-citations that collapse the central claim. No step equates a derived quantity to its own input by construction, and the correspondence between reduced and full systems is presented as a modeling choice rather than a tautology. The derivation remains self-contained against external benchmarks in numerical analysis.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The approach rests on the Benamou-Brenier dynamical formulation of optimal transport, standard notions from graph theory, and classical finite-difference stability conditions; no new physical entities are introduced.

axioms (2)

domain assumption The underlying graph is connected
Required for the dynamical optimal transport problem to be well-defined on the graph.
domain assumption An upwind discretization subject to a CFL-type condition preserves non-negativity of densities on lattices
Invoked to guarantee positivity; this is a standard numerical-PDE assumption whose validity depends on the time-step size.

pith-pipeline@v0.9.0 · 5468 in / 1324 out tokens · 40043 ms · 2026-05-11T02:12:18.973351+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

[1]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin.Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Upper Saddle River, NJ, 1993

work page 1993
[2]

Benamou and Y

J.-D. Benamou and Y. Brenier. A numerical method for the optimal time-continuous mass transport problem and related problems. In L. A. Caffarelli and M. Milman, editors,Monge–Ampère Equation: Ap- plications to Geometry and Optimization, volume226ofContemporary Mathematics, pages1–11.American Mathematical Society, Providence, RI, 1999

work page 1999
[3]

Benamou and Y

J.-D. Benamou and Y. Brenier. A computational fluid mechanics solution to the Monge–Kantorovich mass transfer problem.Numer. Math., 84(3):375–393, 2000. OPTIMAL TRANSPORT ON GRAPHS 21

work page 2000
[4]

Benamou, B

J.-D. Benamou, B. D. Froese, and A. M. Oberman. Numerical solution of the optimal transportation problem using the Monge–Ampère equation.J. Comput. Phys., 260:107–126, 2014

work page 2014
[5]

S.-N. Chow, W. Huang, Y. Li, and H. Zhou. Fokker–planck equations for a free energy functional or Markov process on a graph.Arch. Ration. Mech. Anal., 203(3):969–1008, 2012

work page 2012
[6]

S.-N. Chow, W. Li, and H. Zhou. A discrete Schrödinger equation via optimal transport on graphs.J. Funct. Anal., 276(8):2440–2469, 2019

work page 2019
[7]

Clarke.Optimization and Nonsmooth Analysis

Frank H. Clarke.Optimization and Nonsmooth Analysis. Wiley, New York, 1983

work page 1983
[8]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein.Introduction to Algorithms. MIT Press, 4 edition, 2022

work page 2022
[9]

J. Cui, L. Dieci, and H. Zhou. A continuation multiple shooting method for wasserstein geodesic equation. SIAM J. Sci. Comput., 44(5):A2918–A2943, 2022

work page 2022
[10]

J. Cui, L. Dieci, and H. Zhou. Time discretizations of Wasserstein–Hamiltonian flows.Math. Comp., 91(335):1019–1075, 2022

work page 2022
[11]

What is a stochastic hamiltonian process on finite graph? an optimal transport answer.Journal of Differential Equations, 305:428–457, 2021

Jianbo Cui, Shu Liu, and Haomin Zhou. What is a stochastic hamiltonian process on finite graph? an optimal transport answer.Journal of Differential Equations, 305:428–457, 2021

work page 2021
[12]

M. Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. InAdvances in Neural Information Processing Systems, pages 2292–2300, 2013

work page 2013
[13]

Dieci and D

L. Dieci and D. Omarov. Techniques for continuous optimal transport problem.Comput. Math. Appl., 146:176–191, 2023

work page 2023
[14]

Diestel.Graph Theory, volume 173 ofGraduate Texts in Mathematics

R. Diestel.Graph Theory, volume 173 ofGraduate Texts in Mathematics. Springer, Berlin, 5 edition, 2017

work page 2017
[15]

Fornito, A

A. Fornito, A. Zalesky, and E. T. Bullmore.Fundamentals of Brain Network Analysis. Elsevier, London, 2016

work page 2016
[16]

B. D. Froese. A numerical method for the elliptic monge–ampère equation with transport boundary con- ditions.SIAM J. Sci. Comput., 34(3):A1432–A1459, 2012

work page 2012
[17]

Gladbach, E

P. Gladbach, E. Kopfer, and J. Maas. Scaling limits of discrete optimal transport.SIAM Journal on Mathematical Analysis, 52(3):2759–2802, 2020

work page 2020
[18]

J. L. Gross and J. Yellen, editors.Handbook of Graph Theory. Discrete Mathematics and its Applications. CRC Press, Boca Raton, FL, 2004

work page 2004
[19]

L. V. Kantorovich. On the translocation of masses.Management Sci., 5(1):1–4, 1958. Translated from the 1942 Russian original

work page 1958
[20]

W. Li, J. Lu, and L. Wang. Fisher information regularization schemes for Wasserstein gradient flows.J. Comput. Phys., 416:109449, 2020

work page 2020
[21]

Li and H

Y. Li and H. Zhou. Computational methods for the Fokker–Planck equation on a graph.SIAM J. Numer. Anal., 56(4):2368–2389, 2018

work page 2018
[22]

J. Maas. Gradient flows of the entropy for finite Markov chains.J. Funct. Anal., 261(8):2250–2292, 2011

work page 2011
[23]

A. Mielke. A gradient structure for reaction–diffusion systems and for energy–drift–diffusion systems. Nonlinearity, 24(4):1329–1346, 2011

work page 2011
[24]

G. Monge. Mémoire sur la théorie des déblais et des remblais.Histoire de l’Académie Royale des Sciences de Paris, pages 666–704, 1781

work page
[25]

Newman.Network Science

M. Newman.Network Science. Cambridge University Press, Cambridge, 2013

work page 2013
[26]

V. I. Oliker and L. D. Prussner. On the numerical solution of the equationzxxzyy −z 2 xy =fand its discretizations, I.Numer. Math., 54(3):271–293, 1989

work page 1989
[27]

Papadakis, G

N. Papadakis, G. Peyré, and E. Oudet. Optimal transport with proximal splitting.SIAM Journal on Imaging Sciences, 7(1):212–238, 2014

work page 2014
[28]

Peyré and M

G. Peyré and M. Cuturi. Computational optimal transport.Found. Trends Mach. Learn., 11(5–6):355–607, 2019

work page 2019
[29]

C. R. Prins, R. Beltman, J. H. M. ten Thije Boonkkamp, W. L. IJzerman, and T. W. Tukker. A least-squares method for optimal transport using the Monge–Ampère equation.SIAM J. Sci. Comput., 37(6):B937–B961, 2015

work page 2015
[30]

F. Santambrogio.Optimal Transport for Applied Mathematicians: Calculus of Variations, PDEs, and Modeling, volume 87 ofProgress in Nonlinear Differential Equations and Their Applications. Springer, 2015

work page 2015
[31]

Villani.Optimal Transport: Old and New, volume 338 ofGrundlehren der Mathematischen Wis- senschaften

C. Villani.Optimal Transport: Old and New, volume 338 ofGrundlehren der Mathematischen Wis- senschaften. Springer, 2009

work page 2009
[32]

Weller, P

H. Weller, P. Browne, C. Budd, and M. Cullen. Mesh adaptation on the sphere using optimal transport and the numerical solution of a Monge–Ampère type equation.J. Comput. Phys., 308:102–123, 2016. 22 QUJIANGXUE CHEN, JIANBO CUI, DIECI LUCA, AND HAOMIN ZHOU Appendix A. Invertibility of the Jacobian for the upwind scheme In this section, we verify the nonsin...

work page 2016