Optimal Flow Transport and its Entropic Regularization: a GPU-friendly Matrix Iterative Algorithm for Flow Balance Satisfaction
Authors: Liangliang Shi
Yufeng Li
Kaipeng Zeng
Yihui Tu
Junchi Yan
Venue: ICLR 2025 Poster (2025)
Keywords: Optimal Transport
Flow Balance Constraints
Sinkhorn Algorithm
Network Flow Theory
Primary area: optimization

Abstract: The Sinkhorn algorithm, based on Entropic Regularized Optimal Transport (OT), has garnered significant attention due to its computational efficiency enabled by GPU-friendly matrix-vector multiplications. However, vanilla OT primarily deals with computations between the source and target nodes in a bipartite graph, limiting its practical application in real-world transportation scenarios.
In this paper, we introduce the concept of Optimal Flow Transport (OFT) as an extension, where we consider a more general graph setting and the marginal constraints in vanilla OT are replaced by flow balance constraints. 
To obtain solutions, we incorporate entropic regularization into the OFT and introduce virtual flows for individual nodes to tackle the issue of potentially numerous isolated nodes lacking flow passages. Our proposition, the OFT-Sinkhorn algorithm, utilizes GPU-friendly matrix iterations to maintain flow balance constraints and minimize the objective function, and theoretical results for global convergence is also proposed in this paper.
Furthermore, we enhance OFT by introducing capacity constraints on nodes and edges, transforming the OFT problem into a minimum-cost flow problem. We then present the Capacity-Constrained EOFT-Sinkhorn algorithm and compare it with the traditional Minimum cost flow (MCF) algorithm, showing that our algorithm is quite efficient for calculation. 
In particular, our EOFT-Sinkhorn is evaluated on high-precision and integer-precision MCF problems with different scales from one hundred to five thousand size, exhibiting significant time efficiency and the ability to approximate optimal solutions.

Published as a conference paper at ICLR 2025
OPTIMAL FLOW TRANSPORT AND ITS ENTROPIC REG- ULARIZATION: A GPU-FRIENDE MATRIX ITERATIVE ALGORITHM FOR FLOW BALANCE SATISFACTION
Liangliang Shi', Yufeng Li', Kaipeng Zeng', Yihui Junchi Yan 13+
Sch. of Computer Science & Sch. of Artificial Intelligence, Shanghai Jiao Tong University 2Department of Mathematics, Shanghai University SShanghai Artificial Intelligence Laboratory Schilianglinne liyufeng, zengkaipeng ) @ jautu.ee edu. en tuyihui @shu. edu. en, yan junchiniiii es jtu. edu. cn
Code: https//gittub.coo//siiiittttttt
ABSTRACT
The Sinkhorn algorithm, based on Entropic Regularized Optimal Transport (OT), has garnered significant attention due its computational efficiency enabled by GPU-friendly matrix-vecto multiplications. However, vanilla OT primarily deals with computations between the source and target nodes in bipartite graph, limiting its practical application in real-world transportation scenarios. In this paper, we introduce the concept of Optimal Flow Transport (OFT) as an extension, where we consider more general graph setting and the marginal constraints in vanilla OT are replaced by flow balance constraints. To obtain solutions, we incorporate entropic regularization into the OFT and introduce virtual flows for individual nodes to tackle the issue of potentially numerous isolated nodes lacking flow passages. Our proposition, the OFT-Sinkhorn algorithm, utilizes GPU-friendly matrix iterations to maintain flow balance constraints and minimize the objective function, and theoretical results for global convergence is also proposed in this paper. Furthermore, we enhance OFT by introducing capacity constraints on nodes and edges, transforming the OFT problem into a minimum-cost flow problem. We then present the Capacity- -onetity-ontt EOFT-Sinkhorn algorithm and compare it with the traditional Minimum cost flow (MCF) algorithm. showing that our algorithm is quite efficient for calculation. In particular, our EOFT-Sinkhorn is evaluated on high-precision and integer-precision MCF problems with different scales from one hundred to five thousand size, exhibiting significant time efficiency and the ability to approximate optimal solutions.
INTRODUCTION
Optimal Transport (OT) has shown increasingly important role in solving various problems in machine learning, including domain adaptation (Tzeng al. 2017; Cui et al. 2018), generative models (Arjovsky et al., 2017] Li et al., 2022), self-supervised contrastive learning (Caron et al.. 2020, Shi al. 2023), and long-tail recognition (Peng al. 2021 Shi et al. 2024b) etc. As an efficient method for solving OT, the Sinkhorn algorithm relies on matrix-vector iterations to solve the transportation problem, which is GPU-friendly with high-speed calculations. However, the Sinkhorn algorithm's 's applicability is limited to bipartite graphs, as it only involves computations between sets of source and target nodes, which significantly deviates from real transportation scenarios. Naturally, a question arises: can optimal transport with matrix iterations be extended to more general graphs?
Numerous researchers have made significant efforts the field of optimal transport on graphs. For instance, based on the graph structure, (Le et al. 2022) propose a variant of OT called Sobolev transport, which provides closed-form solution for efficient computation. Additionally, in a related work, (Le et al. 2024) utilize a specific class of convex functions with an Orlicz structure to introduce
* Junchi Yan is the correspondence author. This work was in part supported by by NSFC (62222607) and Shanghai Municipal Science and Technology Major Project under Grant 202152222X0002..

---

Published as a conference paper at ICLR 2025
Nodes of (k)
Nodes of
10
5
10
40
13
Σ Pu Σ Pa -
1
(a) Vanilla OT
(b) Optimal Flow Transport
(c) Flow Balance
Figure 1: Illustration of our optimal flow transport and difference to vanilla OT. (a): Vanilla OT
focuses on solving the transportation within a bipartite graph, focusing on transportation between source and target nodes. (b): Our OFT aims to solve transportation on a more general graph, focusing on the flow between each pair of nodes. (c): In our OFT, we consider the constraints on each node satisfying the flow balance constraint.
the generalized form of Sobolev transpor((TT). However, previous works have mostly overlooked the flow balance constraints on nodes graph transport. They indirectly compute the flow between two nodes by calculating the shortest paths between source and target nodes, thus failing to incorporate capacity constraints on nodes and edges, which are common in real-world transportation scenarios.
In this paper, we aim to fill this gap by proposing Optimal Flow Transport (OFT), in which the constraints for marginals are replaced by flow balance constraints on nodes. As illustrated in Figure I we consider more complex transportation problems where the source nodes (blue) may not directly transport to the target nodes (orange). Instead, it may pass through other nodes, such as transshipment points (yellow). As result, the original transportation problem is generalized into broader min-cost flow (MCF) problem where the marginal constraints are replaced by flow balance constraints as unable to derive matrix-vector iterative
shown in Figure I(c) However, in the current works, algorithm for flow balance satisfaction in OFT by introducing an entropic regularization (Benamou et al. 2015) directly. This limitation can be attributed to the following reasons: 1) the marginals unknown in OFT, and we only have information about their differences; 2) the presence of isolated points in the graph that do not carry any flow contradicts the non-sparse nature of matrix iteration.
To overcome these limitations, in this paper, we propose entropic optimal flow transport, in which we do the following reformulation for the flow problem: 1) we introduce virtual transport flows from each node to itself in the graph, allowing isolated points to participate in the iterations even if they do not have any incoming or outgoing flows originally: 2) reformulating the flow balance constraints with marginal-like constraints via adding a new marginal variable for the optimization; 3) Finally adding the entropic regularization to get the relaxation for OFT. The above reformulations of OFT enable us to iteratively update the coupling and marginals to compute approximate solution for the OFT problem, where we refer to this algorithm as the OFT-Sinkhorn algorithm, and the theoretical guarantee is also proposed for convergence. Moreover, we can impose capacity constraints and edges in our OFT-Sinkhone algorithm, in which the proposed method can serve as a matrix iteration-based solver for the minimum-cost flow problem, and experimental results demonstrate the efficiency of our algorithm with minimal computational errors. Finally, this paper contributes:
nodes
We extend the vanilla OT within a bipartite graph to a more general graph case, and thus propose optimal flow transport, in which the marginal constraints are replaced by flow balance constraints.
We propose the entropic OFT to derive the GPU-friendly OFT-Sinkhorn algorithm to get the approximate solution of the OFT problem. The global convergence is theoretically guaranteed.
We incorporate node and edge capacity constraints into the OFT, and in this case our OFT is equivalent to the minimum-cost flow problem. By considering these constraints, we modify the OFT-Sinkhorn algorithm to ensure that the output satisfies capacity constraints. Experimental results on the minimum-cost flow problem showcase the superiority of our algorithm.
RELATED WORKS AND BACKGROUND
Entropic Optimal Transport. The Optimal Transport (OT) theory can be traced back to (Monge) 1781) where the objective is to seek mapping that minimizes the total cost of transporting mass
2

---

Published as a conference paper at ICLR 2025
from source measure target measure, which has various applications in visual matching (Wang iet al. 2013), long-tailed learning (Shi et al., 2024b c). time series analysis (Zhang et al.] 2020; Shi al. 2020). multi- learning (Shi et al. 2024a; Wang et al. 2024), and etc. Specifically, given the cost matrix C and two marginals (a. b). Kantorovich's OT (Kantorovich, 1960) with entropic
regularization involves solving the coupling P by:
min (a
<CP -cH(P), where U(a,b) = (P E R mn Pl, = a, P 1mbb) bb (I)
Note that ((P) = < P. log 11mxm > represents the entropic regularization, and 6 is the coefficient. When = O, the entropic OT degenerates to vanilla Kantorovich, and when >> 0, the objective in Eq. is e-strongly convex. Consequently, it possesses a unique solution that can be determined using Sinkhorn algorithms, as discussed in (Cuturi 2013 Benamou al. 2015).
Proposition 1 (Solution Form of Entropic OT (Peyre & Cuturi, 2019)). The solution to Eq. 7 is
unique and satisfy P diag( (u) (ydig()()), where K = C/C is the Gibbs kernel associated to the cost matrix C and (u, v) are two (unknown) scaling variables.
With the solution form of entropic OT, Sinkhorn algorithms (Cuturi 2013 Benamou et al. 2015)
were proposed to obtain the solution of Eq. [ where one can iteratively update u a/(kv (Kv) and b/(K v) approximate the solution of the transportation problem. However, research on solving operational research problems using GPU-friendly matrix iteration algorithms seems to be focused only on transportation problems or matching problems, rather than other complex problems in operation research. In this paper, we propose to use matrix-vector iterative algorithms to solve more generalized transportation problem, i.e. MCF. To the best of our knowledge, our algorithm is the first GPU-friendly matrix iterative method specifically designed for solving MCF.
Optimal Transport on the Graph. The concept of optimal transport on graphs can be attributed to (Feldman & McCann 2002), who initially compute the shortest distances between source and target nodes to establish a cost matrix. This matrix is then used to calculate the 1 I-Wasserstein distance, transforming the problem into linear program, specifically min-cost flow problem. This methodology has been applied and expanded to formulate and analyze traffic congestion models. Recently, (Le et al. (202)) introduced new variation named Sobolev transport (ST), tailored for measures supported on graphs, enabling closed-form expression for quicker computation. Furthermore, (Le et al.. 2024) extended Sobolev transport with an Orlicz structure (Orlicz, 1932). They need to first calculate shortest paths before solving the optimal transport between source and target and they can't handle capacity constraints at nodes. In this paper, we introduce optimal flow transport and its entropic regularized case, which calculate the flow in the graph via matrix iterative methods without the need for precomputing the shortest distances on the graph.
Minimum Cost Flow. Machine learning has been leveraged to handle optimization problems (Bengio et al., 202T). Minimum-cost flow (MCF) (Goldberg) 1997) is one of the optimization problems from the network flow theory (Iri 1996), which involves finding the minimum-cost transportation of the specified amount of a commodity from a set of supply nodes to a set of demand nodes in a directed network, considering capacity constraints and linear cost defined problem arises in diverse applications, including transportation (Ahmady & Eftekhari Yeghanch
the ares. The MCF
2022). logistics (Krile 2004), and many other industrial scenes (Choi al. 1988). Efficient algorithms have been developed to solve the MCF problem. For instance, Fulkerson's 's out-of--ilter algorithm (Fulkerson) 1961) takes advantage of the special structure of MCF and adjusts the ares that do not satisfy optimality properties. The cycle canceling algorithm is proposed by Klein (Klein 1967), which focuses on maintaining feasible flow at each iteration. Recent years, advancements in the MCF problem have been marked by several pivotal studies. However, most of the previous methods is based on CPU calculations and also make an assumption that all the data is integers (de Vos, 2023), which limits the solution of the MCF problem when dealing with high-precision data. In this paper, we solve MCF by using a GPU-friendly matrix iterative method to get the approximate solutions.
3 METHDOLOGY
3.1 OPTIMAL FLOW TRANSPORT
In this subsection, We give the definition of Optimal Flow Transport and its exact methods for solving.
3

---

Published as a conference paper at ICLR 2025
Formulation of OFT We begin by defining the OFT follows. Consider Ex= a,dy; and 3= = bydv; are two measures on the graph &(),E), where N = |V| and (a, b) are two balanced vectors satisfying < a b >= 0. The formulation of OFT can be specified as:
min D
PIx PIIN=S
where D 2 is the distance matrix and
b. Note for each node v, V, 0, refer to node v; as a supply node with a supply value s; > O. 8f < 0, it is a demand node with a demand of Ss If S; O, we categorize node v; as transshipment node. Besides, considering each edge EG E E, Dij is the distance of the edge Eij and we set D,, + +oo to prevent self-transportation of nodes here. In comparison traditional vanilla OT, our OFT considers flow balance constraints
Ply P 1N instead of the marginal constraints in U(a, b) in Eq.
Exact Solving for OFT For solving the optimization in Eq. typically obtained indirectly. Specifically, one can first define the cost matrix using the geodesic distance (or shortest path metric):
the field of OT, solutions are
K-I Σ
C
min
Disihe_, 0S K, CH.
K (2:
where i + indicates 1 = i and ix = j. which the path starts at and ends at j. The primary formulation of OT, or called the 1- I-Wasserstein distance can be formulated as
min < C
slN a, IN =b
where pi represents the final transportation results between the source and target nodes, which can
be equivalent to P given the routing of the shortest path in Eq. Then one can adopt the Network Simplex (Dantzig, 1951) or Sinkhorn Algorithms (Cuturi 2013 to get the solutions. However, these shortest path- bash- approachs have some notable limitations because the routes in the graph are fixed, and there is way to impose constraints on the flow of any arbitrary edge or node, which limits the potential for real applications such real traffic scenarios. Another line of approaches (Li et al. 2010, Mohammad Ebrahim Razmi 2009) is use heuristic algorithms based on minimum cost flow. However, different from the algorithms of transportation problems, most of these algorithms assume that all data are integers (e.g. (de Vos 2023)) and aim to find an integer-valued flow with the minimum total cost while meeting the supply-demand constraints for the graph. This severely limits the algorithms' applications on high-precision data.
3.2 OPTIMAL FLOW TRANSPORT WITH ENTROPIC REGULARIZATION
In this subsection, we propose the definition of entropic OFT and corresponding OFT-Sinkhone get the approximate solution for OFT.
Formulation for Entropic OFT Differing from previous CPU-based algorithms, in this paper, following (Cuturi 2013). we consider the entropic OFT and employ a GPU-friendly matrix-vector iterative algorithm to speed up the computations for OFT. However, directly adding entropy regularization cannot derive an algorithm to obtain an approximate solu- tion as directly as vanilla OT. The reason is that: 1) there are many isolated points that do not have any flow passing through them in the exact solution, while under entropy regu- larization, flows are necessarily channeled through them, causing significant bias; 2) the flow balance constraint cannot directly form alternating iterative algorithm like
Nodes of (k)
Nodes of (i}
Σ PLI P k
Pis q +d
Figure 2: Illustration of our constraints Entropic OFT. The flow constraints satisfied by Eq. where each node includes virtual flow(d), input flow(q:). and output flow(q: s; + d).
4

---

Published as a conference paper at ICLR 2025
= 2 10
= 10-5
2 x 10-6
0(Gurobi)
Figure 3: Visualization of network flow results by varying the regularization coefficient OFT. We observe that as decreases, approximate solution calculated by EOFT-Sinkhom approaches closer to the exact solution computed by Gurobi.
the marginal constraint. To address the issues mentioned above, have modified the optimization objectives and constraints:
min D,P> (H(PP) s.t. Plx q + = - --- s diagg(P)) P.q
(5)
where d = d 1N represents the virtual flow from each node to itself, given the constant d. Here, D is the distance matrix and we set D;; = for every node i and increase the constraint Pи: = ensuring that each node, including the isolated nodes mentioned earlier, carries at least d units of flow, which reduces the impact isolated points for the solutions. Additionally, represents the flow out of the nodes (excluding the virtual flow). Then given the net outflow s, we infer the flow into each node as s. The purpose of these transformations above is to establish a form similar to the marginal constraints in line with vanilla OT, thereby enabling the derivation of Sinkhorn-like algorithm to obtain an approximate solution for OFT. Based on the method of Lagrange multipliers, can derive the following proposition (see the proof in Appendix C.I.. which aids in further understanding the prosperity of the solution for OFT.
Proposition 2.
The solution to Eq. is unique and has the form:
82
P= Diag( u KDiag(v) and 9=2 2
s
(Kv) (K uuCuu +
Here u, v are two (unknown) scaling variables satisfying u and (C---tdigghhi) where h is defined as:
<loog d log log v)
(7)
Similar to the entropic OT, the solution still satisfies P = diag( Kdiag(v). However, the output flow q needs be calculated, and the Gibbs kernel K is longer fixed matrix. Therefore, the iteration process appears more complex compared to the vanilla Sinkhorn algorithm, which we will discuss in detail next.
OFT-Sinkhorn Algorithm Here we propose the OFT-Sinkhorn algorithm 3.2, in which we aim to get the optimal solution of Eq. through matrix-vector iterations. An intuitive idea is to iteratively update P, q. and K to obtain the optimal solution. For the coupling P, based on the solution form P Diag( (u) (iagvv() and the marginal constraints Eq. 55 we derive the following iterations for (!) and y()) with the (1 -) iteration:
Algorithm OFT-Sinkhora: Sinkhorn-based AI- gorithm for Entropic Optimal Flow Transport Input: Distance Matrix D, Marginal Difference maximum iteration number L, Virtual- flowwl-flow d.
Output: The Flow Matrix P
Initialize K = exp (-2)
P) element-wise.
for / = 0 to L do
Update v and ((++)) according to Eq.
Update (1++1) by Eq. 10
Update q (1+1) according to Eq.
q s + [K))TT T (((+1)
u (1+1)
(0) (1-1)
end for
Compute P Diag(u) K (KDiag(v) return p P
where we initialize (0) 1, ()) = e D/c and ( = max(7, T., r + s} where 7 a sufficiently ensure that the marginals of the
small positive value. By initializing in this manner,
5

---

Published as a conference paper at ICLR 2025
Σ = 2 X 10
Σ = 2 X 10
= 2 x 10-6
O(Gurobi)
Figure 4: Visualization of the coupling and marginals by varying the regularization coefficient for BOFT. As decreases, the solutions of the coupling and marginals calculated by EOFT-Sinkhorn become increasingly sparse, approaching the exact solution.
coupling are positive (q and q (0) guaranteeing that P is positive. Regarding the calculation of q, following Eq. o we can update it as:
> 7) making both and v positive, thereby
(++1) q(+1)
2 =
(K (K(44)))()))
((K) ((K))(+)))) 1
s²
In fact, for the iteration of q (1+1), would need to apply truncation operation as done for (0) to ensure q (1+1] > and (1+1) 2 However, in practical iterations, we find that the computed result for q (1+1) typically naturally satisfies these conditions. Furthermore, for the iteration of K, we can utilize the constraints Diag(K) = d in Eq. 5 to obtain:
Diag (K (4+1)
(10)
u(++)) 3 v(++]
and the remaining matrix elements still maintain K k(+1) -Dy/e for # j. By iterating / = obtain the optimal solution P for entropic OFT. Similar to how
1, 2.... until convergence, the Sinkhorn algorithm for entropic OT often serves as an activation layer to ensure that the output of neural networks is doubly stochastic matrix (Wang al. 2019), our OFT-Sinkhom algorithm can also serve as a layer to ensure that the output matrix satisfies flow balance constraints, which are typically enforced using loss functions in previous works (Bengio al. 2023). Furthermore, since the matrix P exhibits backflow (i.c.. P > 0 and P >> 0 for any node indices and j). we can perform a backflow removal operation P max(0, P (P*) }) which results in P closer to the exact solution of OFT.
Global Convergence Then give the convergence discussion. Following (Franklin & Lorenz 1989), we adopt the Hilbert projective metric to prove our global convergence which is defined as:
nuu u
du (u1, u') def. log
i.
Then we can get the theoretical results that our OFT-Sinkhorn algorithm has linear convergence and the proof are given in Appendix E
Theorem 1. The iterative scheme for OFT-Sinkhron algorithm has linear convergence. More precisely: one has (u v(1), v(0,K()) (()) q(1)) (u', K* K", .²") and
du (u()) uu()),u) (((())2)) and du (v0),v-)=(AA()))) ((A(K)?)
(11)
where
du (K KW)
X(K) = max () = sup
51
(12)
dy (V,
Additionally, we further discuss the numerical convergence of our OFT-Sinkhorn algorithm by varying the iterations in the experimental section.

---

Published as a conference paper at ICLR 2025
3.3 CAPACITATED OPTIMAL FLOW TRANSPORT WITH ENTROPIC REGULARIZATION
To align with the minimum cost flow problems, in this subsection, we consider adding constraints our OFT that our algorithm can address the minimum cost flow problem with matrix-vector iterations. The detailed algorithm is shown in Alg. in Appendix [ Next, we will categorize the capacity constraints into node constraints and edge constraints, and subsequently refine our OFT-Sinkhomn algorithm accordingly.
Capacitated Constraints on Nodes Initially, we consider Capacitated constraints on nodes, which involve imposing constraints on the optimization in Eq. q and q S where r represents the maximum capacity for incoming or outgoing flows at nodes. To address these capacity constraints in the OFT-Sinkhorn Algorithm modification, we perform truncation operation, specifically setting
ql+ + min r, min(r s, q q where q'+ (+1 defined in Eq. 9 for the (I + 1)-th iteration within
the OFT-Sinkhorn Algorithm.
Capacitated Constraints on Edges Then we examine the capacitated constraints on edges, which replace the constraints diag(P) d in Eq. 5 with the constraints < S. where Sā d represents the constraints of virtual flow and S; denotes the capacity for edge esj. By employing the Lagrangian method, we can derive the following proposition, with the proof provided in the Appendix C.2
Proposition 3. The solution of entropic OFT with edge capacity is unique and has the form:
((Kv) 3 (K u) + $2
P -Diaa(u)
and q =
(13)
Here u, v are two (unknown) scaling variables satisfying u @ v= and K c(D++)// where is defined as
G
= min (D ee. log (Diag(u (Diag(u-')SDiege SSDiaasSDDiVVVVVS ())
(14)
For the Capacitated Edges Constraints in the OFT-Sinkhorn algorithm, we will modify the iteration for in Eq. 10 as follows:
K min (K, Diagaaanuae (u(t)) Sddiag(
( (((iii((((()))))))
(15)
By iteratively applying Eq. Eq. 9 and Eq. 15 until convergence, we can derive the modified OFT-Sinkhom algorithm based on edge capacity constraints.
Capacitated constraints on nodes and edges are typically meaningful practical scenarios. For instance, in transportation problems where edges represent roads and nodes denote intersections at either end of the roads, node capacity constraints can effectively express the limit of vehicles passing through intersections. Mcanwhile, edge capacity constraints can depict the maximum flow allowed on each road, thereby enabling our capacitated OFT to more accurately model transportation issues within a traffic road network.
4 EXPERIMENT
4.1 DATASETS AND EXPERIMENT SETTINGS
We conduct experiments using an NVIDIA GeForce RTX 4090 GPU, with programs implemented in Python and PyTorch We evaluate our approach on three graph datasets: Uniform-MCF NETGEN- MCF and Vision-MCF. For all experiments except the ablation study, we use the same settings to demonstrate method's robustness. Since only matrix iteration algorithm run efficiently GPU, the other three comparison methods were tested on the Intel 19-10X20X CPU.
Datasets We adopt the following datasets in experiments:
Uniform-MCF (Double-precision): We consider the symmetry between source and target nodes(i.e.. 10% nodes designated as sources and targets), constructing four synthetic datasets accordingly(w/o constraint, w/edge constraint, w/node constraint, w/edge+node constraint). We utilizes Gaussian function to generate double- -rebbi--reiision point within Euclidean space. The initial flow of source and target nodes generated by Uniform function which is also double-precision The edge capacity are set to the same value on the same set of parameters. For more details, please refer to Appendix D
7

---

Published as a conference paper at ICLR 2025
Table 1: Evaluation Results Uniform-MCF-5000 Uniform-MCF-5k and Uniforn-MCF-10k, We compared our matrix-vector iterative algorithm (such as Real and ZKW) and commonly used general solver Gurobi. One can find that our algorithm is significantly more efficient than traditional algorithms when computing large-scale Maximum Flow
with classical MCF algorithms
instances, all while maintaining low computational errors. The fastest solution time is bolded.
w/o constraint
w/ edge constraint
w/ node constraint
w/ edge+node constraints
Size
Methods
obj
time
obj
time
obj
time
obj
time
500 x x000
Real
10.02
s
10.067
101 s
10.065
101 s
10.066
101.9
ZKW
10.02
s
10.067
129
10.065
1
10.066
120.8 s
Gurobi
10.02
768 s
10.067
4254 s
10.066
4314
10.067
4052
ours
10.11
s.18
10.137
34s
10.67
4
10.138
7
Real
10.059
1843
10.071
1036
10.071
899
10.064
868
5k x 5.
ZKW
10.059
2034 s
10.071
977s
10.071
1200 s
10.064
1015
Gurohi
3 hours
3 hours
2 3 hours
2 3 hours
ours
10.311
33
10.18
814
10.431
316s
10.186
656
106 X 10k:
Real
10.08
3363 s
10.0898
2032
10.0898
1842 s
10.0898
1425
ZKW
10.08
3781 s 3 hours
10.0898
2396 s
10.0898
2543 s 2 3 hours
10.0898
1961
Gurobi
2 hours
2 3 hour
ours
10.728
47
10.1496
1352 s
10.18
1021
10.147
1462 8
NETGEN Enteger-pprecsionn Note that NETGEN (Klingman et al., 1974) is a well-established generator that produces integer-precision instances for the Minimum Cost Flow (MCF) problem and other network optimization problems. It is designed to generate minimum-cost flow problems based on a set of parameters including node size, arc costs, and are capacities. In our data generation process, we utilize PyNETGEN, Python implementation of NETGEN. For further details, please refer to Appendix D
Vision (Real Scene): This (Goldbergl 2008) consists of MCF instances based large- scale maximum flow problems arising in computer vision applications(with over one million nodes). These data files were made available by the Computer Vision Research Group at the University of Western Ontario. The detail of the data is given in Appendix D
Baselines. To demonstrate the feasibility and effectiveness of our OFT-Sinkhorn method, we compare it with representative MCF algorithms (including classic and SOTA algorithms). We consider the following five methods as our baselines: 1)Real( (Papadimitriou & Steiglitz)) is an exact algorithm that combines SPFA (Ahuja et al. 1995) and augmenting paths which is particularly suitable for solving minimum cost flow problems in graphs of fixed distribution of capacity; 2)2K W (Goldberg et al.)) is variant of Successive Shortest Path Algorithm based on augmenting paths and DFS to efficiently find the shortest path. It is particularly suitable for solving minimum cost flow problems in graphs of random distribution of capacity. Gurobb (Gurobi Optimization, LLC, 2021)) is powerful optimization solver that can efficiently handle a wide range of mathematical optimization problems, including the minimum cost flow problem. However, as the number of nodes and instances increases, Gurobi's computational efficiency decreases. 4)pns( (Kara & Özturan 2022))s iss one of the SOTA Parallel network simplex algorithm for the MCF problem. 5)lemon( (Király & Kovács 2012)) is a is a Highly optimized CPU based solver for MCF problems. Here we test on lemon-ns which is the network simplex version of lemon.
4.2 EXPERIMENTAL RESULTS
In this section, we discuss the overall performance of various methods on uniform, NETGEN and Vision datasets which is presented in Table D. Table 2 and Table
and
Evaluation on Uniform Data. Uniform-MCF a double-precision MCF instance with predefined edge capacities. In terms of Obj across each dataset, both Real and ZKW consistently achieve the optimal solution, while Gurobi gave a tight approximate solution with a gap of less than 0.1 1% as shown in Table[[] This might be attributed to the fact that the MCF problem is solvable in polynomial time, where exact algorithms can always provide the optimal solution. However, their efficiency significantly decreases with larger datasets. Notably, Gurobi struggles with problems exceedomg
8

---

Published as a conference paper at ICLR 2025
Table 2: Evaluation of MCF on Small to medium-sized NETGEN dataset.
Methods
100
100
500
500
1k x
x
obj
time
obj
time
obj
time
obj
time
Real( Paaadamitrioo & Steightz
64.58
421 ms
20.418
1028 s
23.365
s
15.652
18592
Goltherr ef al.
504
20.418
23.365
1639
15.652
7491
Gurobi Gurobi Optimiiaiion LLC 2021
64.58
77.3 s
20.42
4572
2 3 hours
10 hours
BOFF-Sinkhom
65.05
22.2
20.548
82 8
24.696
420
16.41
1261 s
Table 3: Evaluation of MCF on very large sparse graph.
Netgen_ 8
Netgen lo_8 8
Vision
Methods
obj
time
obj
time
obj
time
pns(k=1.p==) (Kara & Özluran 2022
18.33
335 s
12.88
8
30.16
1774
pos(k=1.p=4) pns(k=16.p=16
18.33
261 s
12.88
30.16
2579 s
18.33
286 s
12.88
91
30.16
2
lenmon-ns KKrály & Kováes 2012
18.33
186 s
12.88
30.16
2805 s
EOFI-Sinkhorn
18.83
50.4
13.08
59.3
32.04
1802
5,000 nodes, which we indicate with "-" symbol. On w/o constraints, there are only flow balance constraints mentioned in Eq. For problems that incorporate both capacity and node constraints, the objective (obj) of the problem slightly increases (e.g.. from 10.02 to 10.06) due to the additional constraints, and the computational time increases almost linearly with the problem size. In contrast, our entropy regularization method, specifically the Sinkhorn algorithm (Cuturi 2013), offers faster solving speeds due to its GPU-friendinnsss The results demonstrate that our algorithm significantly outperforms traditional algorithms in terms of efficiency when computing large-scale MCF instances, while maintaining low computational eπror gap. For further details and parameters regarding the Uniform-MCF please refer to Table in Appendix D
Evaluation Results on small to medium-size NETGEN. The experimental details of NETGEN datasets are given in Table and the results are given in Table 2 For smaller problems, Real (Paapadimitriou & Steiglitz)) and ZKW ((Goldberg et al.)) achieve the best solution quality and computational time. However, as the dataset size [D]. the total number of nodes [V] and the total number of edges [E] increase, our method demonstrates superior solution speed over former 3 methods. Lemon achieve best solution and speed under all-cases, demonstrated outstanding performance in solving small to medium-scall MCF problems SOTA method." Appendix D shows the parameters and details about NETGEN experiments.
Evaluation Results on very large sparse graph. The experimental details for large sparse datasets are presented in Ta while the corresponding results are summarized in Table To efficiently better
solve these three exceptionally large sparse MCF problems, we tailored our algorithm leverage the triplet structure inherent in sparse graphs. As the pioneering work applying entropic regularization to the MCF problem and developing a GPU-friendly algorithm, our approach effectively tackles the minimum cost flow problem on extremely large sparse graphs. In certain cases, it even surpasses state-of-the-art algorithms in obtaining high-quality approximate solutions.
4.3 ABLATION STUDY
Then we will analyze the convergence, effect of regularization, and numerical stability in depth.
Convergence of EOFT In Figure we illustrate how the marginal distribution evolves with the number of iterations for an instance with 5000 nodes. The marginal difference is computed as PIN- - PT_ 1N (denoted as Ssoft), while the Ground Truth (GT) marginals are represented by Initially, we generate the flow for the source and target separately using one-dimensional Gaussian function, denoted as Ssource and Starget. To estimate the distribution of the source and target marginals, we employ Gaussian Kernel Density Estimation (KDE) (Pazzen 1962), defined as K(u)= = /2n
2 The marginal difference at transshipment nodes is obtained by computing the
difference between the estimated distributions of the source and target marginals, i.e. Ssource Starget- The results demonstrate that the number of iterations increases, EOFT progressively converges to the GT marginals, validating the accuracy and stability of our algorithm. (c.g., the red dotted line (EOFT-200 iterations) in Figure 5 almosst overlaps with the solid black line which is GT marginals).

---

Published as a conference paper at ICLR 2025
0.020
0.015
047123 Am
0.030
0.030
0.23
0.025
(1F154
0.055
O011
0.020
0.020
0.000
0.015
0.015
-0.005
0.000
0.010
-0.010
0.005
0.005
-0.015
0.000
20
60
0.000
-0.020
20
80
(a) Source Marginals
(b) Target Marginals
(c) Marginal Difference
Figure 5: Visualization of the marginals by varying iterations for EOFT. As iterations increase, the marginals calculated by the OFT-Sinkhorn algorithm (dotted line) gradually approach Ground Truth (black solid line).
Sparsity of the Coupling In domains such as logistics planning, an exact and sparse transport plan is desired. In this section, we conduct tests on the sparsity of the transport plan for EOFT-Sinkhorn methods with different regularization coefficients e, We uniformly sample a network of 60 nodes, designating 15 as sources and 15 as targets. Figure 3 visualizes the transportation plan generated by the EOFT method. The dotted green lines represent potential node connections, whereas the red solid lines signify the actual transportation routes. The color intensity along these paths is indicative of the flow volume, offering clear visual illustration of the plan's 's density. The results reveal that as the of e decrease, the approximate solution from the EOFT-Sinkhorn method converges more closely to the optimal solution achieved using Gurobi. Similarly, Figure iillustrates the transformation of the coupling matrix and marginals as the regularization coefficient e decreased. With a decreasing e, the optimal coupling matrix exhibits increased sparsity, and the transportation plan P progressively aligns with the solution delivered by Gurobi.
Numerical Stability Note the stability is critical in algorithm design and Figure evaluutes the numerical stability of the OFT- Sinkhorn algorithm. Each data point reflects the mean perfor- mance of four random instances, with all other parameters kept constant to ensure fair compar- ison. The heatmap displays both cost and time, where NaN rep- resents computational failure at that particular parameter com- bination. The horizontal axis shows the progressively reducing Err (the algorithm'ss 's convergence threshold, defined illustrates the gradually decreasing e. The findings reveal that as either the convergence threshold or diminishes, the EOFT algorithm requires more time to converge, yet it achieves a solution of higher quality. Our algorithm exhibits remarkable stability across a wide range of parameters, notably when e range from x 10 to 10 and convergence threshold ranges from 1 x 10 2 x 10-5
Heatmap of Cost
Heatmap of Time
36-1
522
121
S21
522
532
503
36-1
31.6
5.5
10.5
30.6
32.4
3
88
5e-3
30.7
12.1
15.5
20.4
10-3
3:25
10.43
11:00
31.00
11.05
11.67
16:3
33.5
233
35,0
30,5
41.4
43.0
7.76
3354
1.550
25.5
56.
Ie-E
30
5e
16
52 4
30
10:5
20 5c.
16
50 10.4 16.5
Converocnce thrcshold
Converpence thrcchod
Figure 6: Visualization of the cost and time by varying the and Ervor(convergence threshold) for EOFT. Under most cases, EOFT exhibits a smooth changing process. Each point is obtained by the average of 4 instance
- s) and the vertical axis
CONCLUSION AND FUTURE WORK
This paper has formulated the optimal flow transport problem beyond the vanilla discrete OT, to improve its applicability in real-world problems. We also present new time-efficient methods OFT- Sinkhorn algorithm to solve the problem and its variants, which is solved by GPU-friendly matrix iterations. Experiments show that our method is more efficient than general solvers in solving the minimum cost flow problem, which proves that our EOFT algorithm can be effectively used to solve the minimum cost flow problem. For future work, we will combine approach with other OT variants, such as partial transportation Phatak et al. (2023). robust optimization Raghvendra et al. (2024), or explore parallel computation of OFT (Lahn et al. 2023)
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Mahmuod Ahmady and Yones Eftekhari Yeghaneh. Optimizing the cargo flows in multi-modal freight transportation network under disruptions. Iranian Journal of Science and Technology. Transactions of Civil Engineering, 46(1):453-472, 2022.
Ravindra K Ahuja, Thomas Magnanti, and James Orlin. Network flows: theory, algorithms and applications. Prentice hall, 1995.
M. Arjovsky, S. Chintala, and L. Bottou. Wasserstein gan. ICML, 2017.
Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyré. Itera- tive bregman projections for regularized transportation problems. SIAM Journal on Scientific 2015.
Computing, 37(2):A111-AIII
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological tour d' horizzo.. European Journal of Operational Research, 2021.
Yoshua Bengio, Salem Lahlou, Tristan Deleu, Edward J. Hu, Mo Tiwari, and Emmanuel Bengio. Gflownet foundations, 2023. BtLpttps:/// ltttps:/aarxiv.orgg
09266
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. Advances in neural information processing systems, 33:9912-9924, 2020.
Wonjoon Choi, Horst W Hamacher, and Suleyman Tufekci. Modeling of building evacuation problems by network flows with side constraints. European Journal of Operational Research, 35 (1):98-1100 10, 1988.
Yin Cui, Yang Song, Chen Sun, Andrew Howard, and Serge Belongie. Large scale fine- ane-grained categorization and domain-specifie transfer learning. In Proceedings of the IEEE conference computer vision and pallern recognition, pp. 4109-4118, 2018.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural
information processing systems, 26, 2013.
George B Dantzig. Application of the simplex method to transportation problem. Activity analysis and production and allocation, 1951.
Tijn de Vos. Minimum cost flow in the congest model, 2023. URRpptttss//axxxv.ooo
Mikhail Feldman and Robert J. McCann. Uniqueness and transport density in monge's 's mass transportation problem. Calculus of Variations and Partial Differential Equations, 15:81-113, 2002. URL htt.h:tts: //api. semant ientiiisccllln Io...appsiorrrr. 6328939
Joel Franklin and Jens Lorenz. On the scaling of multidimensional matrices. Linear Algebra and its applications, 114:717-735, 1989.
Delbert R Fulkerson. An nut-of-kilter method for minimal-cost flow problems. Journal of the Society for Industrial and Applied Mathematics, 91):118-7,, 1961.
Andrew Goldberg. An efficient implementation a scaling minimum-cost flow algorithm. Journal of algorithms, 22(1):1-25 1997.
Andrew V Goldberg. The partial augment-relabel algorithm for the maximum flow problem. In European Symposium on Algorithms, pp. 466 477. Springer, 2008.
Andrew V Goldberg, Éva Tardos, and Robert Tarjan. Network flow algorithm. Technical report,
Cornell University Operations Research and Industrial Engineering.
Gurobi Optimization, LLC. Gurobi Optimization, LLC.C 2021. WRRLhhtts://www.cok
Masao Iri. Network flow-theory theory and applications with practical impact. In System Modelling and Optimization: Proceedings of the Seventeenth IFIP TC7 Conference on System Modelling and Optimization, 1995, pp. 36.36.65 Springer, 1996.
11

---

Published as a conference paper at ICLR 2025
Leonid V Kantorovich. Mathematical methods of organizing and planning production. Management science, 6(4):366-42)) 1960.
Gökçehan Kara and Can Özturan. Parallel network simplex algorithm for the minimum cost flow problem. Concurrency and Computation: Practice and Experience, 34(4):66659, 2022.
Zoltán Király and Péter Kovács, Efficient implementations of minimum-com flow algorithms. arXiv preprint 12XXiv:207..3330 2012.
Morton Klein. A primal method for minimal cost flows with applications to the assignment and transportation problems. Management Science, 14(3):205-220, 1967.
Darwin Klingman, Albert Napier, and Joel Stutz. Netgen: A program for generating large scale capacitated assignment, transportation, and minimum cost flow network problems. management science, (0(5):814-82) 1974.
Srećko Krile. Application of the minimum cost flow problem in container shipping. In Proceedings. Elmar-2004. 46th International Symposium on Electronics in Marine, pp. 466-471. IEEE, 2004.
Nathaniel Lahn, Sharath Raghvendra, and Kaiyi Zhang. combinatorial algorithm for approximating the optimal transport in the parallel and mpc settings. Advances in Neural Information Processing Systems, 36:21675-21686, 2023.
Tam Le, Truyen Nguyen, Dinh Phung, and Viet Anh Nguyen. Sobolev transport: A scalable metric for probability measures with graph metrics. International Conference on Artificial Intelligence and Statistics, pp. 9844-9868. PMLR, 2022.
Tam Le, Truyen Nguyen, and Kenji Fukumizu. Generalized sobolev transport for probability measures on a graph. arXiv preprint arXiv:2402.045.. 16, 2024.
XY Li, Yash P Aneja, and F Baki. An ant colony optimization metaheuristic for single-path multicommodity network flow problems. Journal of the Operational Research Society, (1): 1340-1355,10 2010.
Yang Li, Yichuan Mo, Liangliang Shi, and Junchi Yan. Improving generative adversarial networks via adversarial learning in latent space. Advances in Neural Information Processing Systems, 35: 8868 8881, 2022.
R. Mohammad Ebrahim and Razmi. A hybrid meta heuristic algorithm for bi-objective minimum cost flow (bmef) problem. Advances in Engineering Software, 40(10):1056-1000 1062. 2009. ISSN 0965-9978. doi: http:///..c.eeeeeea.aaae////////
URL https
/ www. www.ssceeiccccc..
rect. rect. com
Gaspard Monge. Mémoire sur la théorie des déblais et des remblais. Mem. Math. Phys. Acad. Royale Sci., pp. 666-704, 1781.
W. Orlicz. Ueber eine gewisse klasse von räumen vom typus. Bulletin International de l'Académie Polonaise des Sciences el des Lettres, pp. 8-9, 1932.
Christos H Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: algorithms and complexity. Courier Corporation.
Emanuel Parzen. On estimation of probability density function and mode. Annals of Mathe-
matical Statistics, 33:1065-1099 1962. URL htttps://api. www.eesssemmaacccccic..c. org
Corpus 12:932222222222
Hanyu Peng, Mingming Sun, and Ping Li. Optimal transport for long-tailed recognition with learnable cost matrix. In International Conference on Learning Representations, 2021.
Gabriel Peyre and Marco Cuturi. Computational optimal transport. Foundations and Trends in Machine Learning, 1 115-6):555-677, 2019.
Abhiject Phatak, Sharath Raghvendra, Chittaranjan Tripathy, and Kaiyi Zhang. Computing all optimal partial transports. In International Conference Learning Representations, 2023.
12

---

Published as a conference paper at ICLR 2025
Sharath Raghvendra, Pouyan Shirzadian, and Kaiyi Zhang. A new robust partial p-wasserstein-bise based metric for comparing distributions. In International Conference on Machine Learning, 2024.
Liangliang Shi, Peili Lu, and Junchi Yan. Causality learning from time series data for the industrial finance analysis via the multi-dimensional point process. Intelligent Automation & Soft Computing, 26(5), 2020.
Liangliang Shi, Gu Zhang, Haoyu Zhen, Jintao Fan, and Junchi Yan. Understanding and generalizing contrastive learning from the inverse optimal transport perspective. International conference on machine learning, 2023.
Liangliang Shi, Jack Fan, and Junchi Yan. Ot-clip: Understanding and generalizing clip via optimal transport. In Forty-first International Conference on Machine Learning, 2024a.
Liangliang Shi, Zhaoqi Shen, and Junchi Yan. Double- optimal transport for advanced clustering and classification. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 38, pp. 14982-14990, 2024b.
Liangliang Shi, Haoyu Zhen, Gu Zhang, and Junchi Yan. Relative entropic optimal transport: (prior-aware) matching perspective to (unbalanced) classification, Advances Neural Information Processing Systems, 36, 2024c.
Eric Tzeng, Judy Hoffman, Kate Saenko, and Trevor Darrell. Adversarial discriminative domain adaptation. In Proceedings of the IEFE conference on computer vision and pattern recognition, pp. 7167-7176, 2017.
Guolong Wang, Xun Wu, Zheng Qin, and Liangliang Shi. Routing evidence for unseen actions in video moment retrieval. In Proceedings of the 30th ACM SIGKDD conference on knowledge discovery and data mining, pp. 6024-3035, 2024.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Learning combinatorial embedding networks for deep graph matching. In Proceedings of the IEEE/CVF international conference computer vision, pp. 3056-3065 3065, 2019.
Wei Wang, Dejan Slepčev, Saurav Basu, John A Ozolek, and Gustavo K Rohde. A linear optimal transportation framework for quantifying and visualizing variations in of images. International journal of computer vision, 101(2):254-26) 269, 2013.
Zheng Zhang, Ping Tang, and Thomas Corpetti. Time adaptive optimal transport: A framework of time series similarity measure. IEEE Access, 8:149764-149774 2020.
13

---

Published as a conference paper at ICLR 2025
A APPENDIX
B DETAILS ALGORITHM OF EOFT WITH NODE AND EDGE CONSTRAINTS
Algorithm 2 OFT-Sinkhorn: Iterative Sinkhorn-based Algorithm for (capacitied) Entropic Optimal
Flow Transport with Edge and Node Constraints
Input: Distance Matrix D, Edge Capability S, Node Capability r, Marginal Difterence maximum iteration number L. Virtual-flow
Output: The Allocation Matrix Pij for i, 1, ..... N
Initialize K exp P) element-wise.
for / = 0 to L - do
Update u (1+1), v(++1 according Eq.
Update (1+1) according Eq.
Update G (I+1) according Eq. 14
Update K (I+1) by exp -D+
end for
Compute P = Diag(u) K (Via(g)() return P P P
C PROOF FOR ALGORITHEM EOFT-SH, EOFT-SH-C
Here we provide the Mathematical proof for Proposition and in main text.
C.1 WITHOUT CONSTRAINS
min
D,P> (P)
P20.
q20
(16)
subject to
PI = + 1 = 1x - Diag(P) =d
Adding dual variables f,g, h, the lagrange equation is then:
- D,P -HI < <f, -.P=)-((0P-...------- -
Dia
(17)
We can get partial differential of lagrange equation with respect
ac
Dij + elog (Pt) - f; - --gi- 0
(18)
0P
Then get:
Pg fi/ec Dil/c
(19)
Similarly:
OC
Dí + +elog (Pi) fi gi h
(20)
0P
Then we can get:
Px h/e (Du -Di-e///e//
(21)
Thus for the whole matrix P. we can get:
P = Diag(e DDDDeeDt///////iia((SS.
(22)
Letting u = e/c, = e8/c K _e" DDDDiig(hh// we can get the optimal solution from P Diag(u)KDiag(1)
14

---

Published as a conference paper at ICLR 2025
We get partial differential of lagrange equation with respect qi
0c
f + g = O.
(23)
Qq
Thus we can get f -g ie: u ==
Knowing PlN + d and P 1x q + d, get:
q d
q q-s+
u
v=
(24)
Kv
K
Thus have
9 d
9 + d
Kv
(K)
Then can get the solution of as:
(Kv) 2 (K u) + s2 $
q" 2
d.
(25)
4
Knowing Diag(P (P) = d, we can get that
Diag(P) u; (L-Da-Diag(Lu))/ Vi d
So the solution of d is
h = e x (log d log u log + Diag D)
From the above derivation, we can know:
K e DD+Dlag(b)/
By iterating through ①
2. 3
and
4 we obtain the final Proposition
C.2 WITH CONSTRAINS
min P20.
D,P (H
920
(26)
subject to
PIN = = = s
P < S
Adding dual variables f.g. H(H 2 0), the lagrange equation then:
= D,P> -P < f, Pl q-d < gg - H,P S>
(27)
The partial differential of lagrange equation with respect to P:
dC
Dij + e log (Pij) f11 1 gi Hij 0
(28)
ii
Thus we get:
Pij = (Djtt(DDuttt)/eeeeee
Diag (DiagV)))
(29)
where e/5 v= cR/E K = c(-D+H)/e
We can get partial differential of lagrange equation with respect to
ac
f
=
(30)
0q
Thus get f -g i.e: Similar to the Section 3.1:
15

---

Published as a conference paper at ICLR 2025
9+d d Kv
9 9-8-
u u
=1
(K)
Due to the constraint on
8² 5²) (K")) u)= 7) drr
q = min (Kv) (KV))
(31)
Due to S we can get that
P= Diag u (DD+H///--- DiaglV S S
(32)
Thus: H D log (Diag(u u "JSDiag(v 1)) Thus get that
min (D + log (Diag(u (SSDiaay 1))
(33)
D DETAILS ABOUT EXPERIMENTS
D.1 DETAILS ABOUT PARAMETERS
Table 4 show the parameters of MCF experiments at Table iin main text ,including the Batch size, Regularization coefficients, Split of the node set, d (Virtual flow)) Node_ C (Capacity for flows at nodes), Edge_ C (Capacity for edges)), and err (Convergence threshold of the iterations).
Table 4: The parameters for experiments on synthetic dataset
Instance
Splli
Edgee
Convergence
Node_500 [odee_500_wwr constraint
64
30-4
50_400 50
Ic-3
Io-6
wiedge constraint
N00 winode constraint
256
Sc4
50 400
Io-4
0.1
lc-5
Node Node_500_wy wi edgesnode constraints
256
50 400 .00
0.5
le-5
Node 5k, wlo construint
16
Se-4
500, 4000 500
le44
le-6
Node_5k. Sk__/edge
16
Se-4
500_40000 500
lc44
0.05
le:5
Node 5k_ edge-node comstraints
8
Se-4
500_4000
500
le-4
0.1
0.5
le:5
Node_1Ok, constraint
Node_ 10k w/ odge constraints
2
5e-
1000.
8000
1000
1o-4
0.05
lc-5
Node_ 10k w/ node conerraints
Se-4
1000
8000 1000
0.1
le.5
Node_1Ok_w w/ edge+aode constraints
504
1000_8000_1000
1000
10-4
0.5
1o-5
Similarly, Table 5 show the parameters of MCF experiments Table 2 in main text, including the Batch size, Regularization coefficients, Split of the node set, d (Virtual-flow), Range (Capacity range for NETGEN randomly generate), Arc_Num Num (Totak are number)), and err (Convergence threshold of the iterations).
The Convergence threshold err is defined the average differance the marginals:
batch size
P11, -P. 1m s.|l
eTT
batch_size
Table 5: The parameters for experiments on NETGEN dataset
Instance
Instance Num
Node Split
d0
Cap_ Range
Are_Num
err
Node_ 100_ NETGEN
128
le-3
10. 80 10
le-4
[0.5.1]
800
le-5
Node_500 500 NETGEN
Node
256
5e-4
50 400 50
le-4
[0.5.1]
64 k
le-4
Node 1k JENNEEEEN
128
5c-4
100. 100_800,
800_000010000 100
le-4
[0.5.1]
80 k
1c-4
Node 5k NETGEN
8
5e-4
500 4000 500
le-4
[0.5.]]
10000 k
le-4
Table 7 shows the Sparsity degree of the Table including the Cost Matrix, Guroobi and EOFT.The results shows that the Uniform-datasee is sparse graph, and both Gurobi and EOFT have obtained nearly equally sparse solutions across various constraint scenarios and problem sizes. The are number of NETGEN dataset about O(n2) on 500/1k/5k instances, which means they Dense graph.
16

---

Published as a conference paper at ICLR 2025
Table 6: The parameters for very large sparse graph. For netgen generator, netgen 8 is sparse graph
with degree 8, and netgen 1o are variants with lower supplies. Vision we adopt the Vision inv 05
instance mentioned in Kara & Özturan (2022)
Instance
Instance Num
Node Num
Total Supply
Capacity Range
Range
do
Netgen 8
[048376
8388608
1024000
[1,1000]
[1.00000]
lo-3
lo-2
le-4
Netgen
10240
[0,
[1,10000]
le.3
le-2
le-4
Vision
3899394
23091149
10000
[0,100]
0000
1e:3
1e-2
1e-4
ropority
Table 7: The sparsity degree of the solutions
Instance
Cost Mat
Gurobi Sol
EOFT
Node_500 550050000wooo constraint
0.02
0.998
0.996
1ode__500mmm w/ edge+node constraints
0.02
0.999
0.992
Nodc_5k_wwil w/o constraint
0.002
0.998
0.997
Node w/ edge+node constraints
0.002
0.982
0.951
Node_ w/o constraint
0.002
0.999
0.999
Node 10k w/ edge+node constraints
0.002
0.962
0.934
D.2 DETAILS ABOUT DATASET
Salform-MMCF The average out-degree of this dataset 16, indicating that Uniform-MCE is and sparse graph dataset. The Distance matrix here is generated by gaussian function within [0, 1]2 Euclidean space
NETGEN (Klingman et al. 1974) was used to generate random minimum-cost flow, maximum flow, and assignment problems, exported DIMACS graph format. We use PyNETGEN as Python implementation of NETGEN in our data generating process.
PyNETGEN are capable generating minimum-cost network flows problems according to a set of tuneable parameters that control things like the size of the network and the acceptable ranges of are costs and capacities. It begins by defining source and sink nodes and randomly distributing supply among them. It then generates set of "skeleton arcs" create paths from the sources the sinks. Skeleton ares are guaranteed to have enough capacity to carry all required flow, ensuring that the problem instance is feasible. After the skeleton is defined, ares randomly generated between pairs of mandomly-seletter nodes until the desired density is reached The main parameters used for the NETGEN are as follows:
nodes number of nodes (default 10)
sources number of source nodes (default
sinks number of sink nodes (default 3)
density number of ares (shown in Table 4)
mincost minimum are cost (we set 10)
maxcost maximum are cost (we set as 100)
supply y total supply (we as 10000)
capacitated percent of skeleton ares (0-100) that are capacitated (we set as 100)
mincap minimum are capacity (shown in Table
maxcap maximum are capacity (shown in Table
E
CONVERGENCE OF OFT-SINKHRON ALGORITHM.
Based the OFT-Sinkhom algorithm, the corresponding iterative scheme is follows,
17

---

du (u, u') log max Published as a conference paper at ICLR 2025
u (+1) q0 + +d
k()(()'
vl+1) (1)
- -
(K()) ul(+1);
(34)
d
Diag K (
u (1- @ v(I+1j
s²) d,
q (++1) + (k(+)))(())) o (K ( ((
for = 1, I,...,M, M. The stopping criteria are chose as max 1 (A)) criteria 5. Before analyzing the global convergence of OFT-Sinkhorn algorithm, we introduce the Hilbert projection metric, which defined as,
( < 8 with small emror
u,u 4. u,u
(35)
Lemma 1. For matrix K, vector v and v', the following inequality holds
du (Kv, Kv') S X(K)dx (v.v')
(36)
with
v1 A(K)
Vi(K)+1 < 1,
(37)
K.tKK, ?(K) max K,,KK,,"
The above theoretical results given in Theorem 4.1 in the paper (Peyre & Cuturi 2019) and use it to prove the following theorem to show our convergence.
Theorem 2. The iterative scheme Eq. for OFT-Sinkhron algorithm has linear convergence. More precisely: one has (u()) v(1) ()))
(u", , K* q²)) and
dH (1()) u² =(((K)?*
(38)
dx (00)rr)) -(((K)))))
where
dx (K()), KW) 11. dH v')
X(K) max X(K()) sup
(39)
Proof. For any v and v', we have
du (v, = du (v/v' 1x) = dx (1N/v,1x/v).
(40)
Then,
(1) + q- - -
du (ult)), ,u²) = du
k())(()) K'v'
K (()( K'v'
= =du
(()) + d' q" +d
(41)
v(()
< max(X((")) ((IKK"))("K)))) X(KK))dx
(()) '''q std -sdd
v
< <(K)dd
(
d q"' - -
18

---

Published as a conference paper at ICLR 2025
Lemma used in Eq. 41 which implies u u² v() Furthermore,
q-
du (vllt.), v²) dn
(1)
q" d
((+t((
K'u
(1+1)
K*1
dh
(42)
q + d
qr - d
(1+1)
u'
<(K)da
q d q" d
Lemma used again in Eq. 42 which shows that v(O v
9th
q"
Substituiing u" and v into Eq. 34 which deduces
+ ((K'r'))(()) (((T)(u²)) + 5²
Diag(K") u
q -==2" 2
d.
(43)
19


Reviews:
[{"review_id": "NtOFsFhJP9", "reviewer": "Reviewer_vSLu", "summary": "This paper proposed efficient algorithms to address the minimum cost flow (MCF) problem with Sinkhorn iterations. The authors claim a problem named the Optimal Flow Transport (OFT) problem as an extension of OT to general graphs by replacing marginal constraints with flow balance constraints. They use entropic regularization and virtual flows to propose a GPU-friendly/matrix-based OFT-Sinkhorn algorithm. Furthermore, they apply capacity constraints on nodes and edges, transforming the OFT problem into a capacity-constrained MCF problem. Experiments demonstrate computational efficiency on various datasets.", "questions": "- How does the proposed algorithm compare with existing GPU-accelerated methods for solving the MCF problem? Including such comparisons within the experiment will strengthen this paper.\n- Is there any machine learning problem that can apply the algorithms of this paper? \n- Have the authors evaluated the performance of their algorithm on CPUs? Will the code be public?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper applied the entropic regularization and Sinkhorn iterations to the MCF problem and provided algorithms that can run on GPU. This is good for solving large flow problems more efficiently than the traditional method. The paper includes experimental evaluations demonstrating that the proposed algorithm can solve the problem efficiently on large-scale problems. In addition, this work provides the proof for the convergence of the proposed algorithms looks good to me.", "weaknesses": "My primary concern is about the novelty. This work claims to extend OT to general graphs with flow balance constraints, which is essentially a restatement of the classic minimum cost flow (MCF) problem. The MCF problem is well-studied, and applying entropic regularization is a common practice. Secondly, this paper needs further literature review of existing work that applies similar techniques to the MCF problem using GPU acceleration or matrix-based methods. such as [1][2]. Additionally, another concern is that this paper does not show how their proposed method benefits the machine learning community. There is a lack of discussion on the applications of MCF in machine learning tasks, and no such experiments are provided. Given these weaknesses, I tend to reject this paper.\n\n[1] Harish, Pawan, Vibhav Vineet, and P. J. Narayanan. \"Large graph algorithms for massively multithreaded architectures.\" International Institute of Information Technology Hyderabad, Tech. Rep. IIIT/TR/2009/74 (2009).\n\n[2] Wu, Jiadong, Zhengyu He, and Bo Hong. \"Efficient CUDA algorithms for the maximum network flow problem.\" GPU Computing Gems Jade Edition. Morgan Kaufmann, 2012. 55-66.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ROhATihnWb", "reviewer": "Reviewer_42rw", "summary": "The authors provide a Sinkhorn-like algorithm (hence involving parallelizable matrix multiplication) for the case of optimal transport on more general graphs than the bipartite graph.", "questions": "In Table 1, there is an error in the 10kx10k line for the W/ edge+note constraints: the fastest method in 'Real\" with 1425s not \"ours\" with 1462s.\n\nIn general, when there are constraints, the \"Real\" method has similar orders of magnitude results and still has a better solution quality in terms of objective. So what if the authors stop the compared algorithms at the same obj value their algorithm achieves? It is unclear which algorithm would be faster between \"Real\" and \"ours\"?\n\n\"However, these studies primarily rely on graph's shortest distances and do not directly compute transport couplings within the graph.\" -> How is that a problem? Is it slower? Not GPU friendly? Or is it not as generic as the authors' solution? Are there settings where the authors could compare their approach with theirs?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well written and theoretically sound and possibly introduces a new interesting method that can leverage modern GPU infrastructure.", "weaknesses": "The numerical experiments are not completely clear, and their relation to existing works could be slightly clarified.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6aIUGRfAWW", "reviewer": "Reviewer_6h6u", "summary": "This paper introduces the concept of Optimal Flow Transport (OFT) as an extension of vanilla OT, where the authors consider a more general graph setting and the marginal constraints in vanilla OT are replaced by flow balance constraints. Adding entropy regularization directly cannot derive an algorithm to obtain an approximate solution as directly as vanilla OT due to two reasons. First of all, there are many isolated points that do not have any flow passing through them in the exact solution, while under entropy regularization, flows are necessarily channeled through them, causing significant bias. Second, the flow balance constraint cannot directly form an alternating iterative algorithm like the marginal constraint. The authors address these issues by modifying the original problem formulation and proposing the new OFT-Sinkhorn algorithm. The new approach utilizes GPU-friendly matrix iterations and is guaranteed to converge globally (with the rate). The authors also extend their approach to a more general setting where the capacity constraints on nodes\nand edges are avaliable. The encouraging empirical results are presented and discussed.", "questions": "1. I encourage the authors to further clarify the difference between the current paper and the existing works. For example, you state that the previous studies primarily rely on graph’s shortest distances and do not directly compute transport couplings within the graph. In my understanding, these studies can compute transport couplings but need to precompute the shortest distances on the graph (please correct me if I am wrong). Then, why can you directly compute transport couplings within the graph? It seems counterintuitive to me if this is only because you use the entropy regularization. Would you like to provide me more details? \n\n2. You state that your EOFT-Sinkhorn is evaluated on high-precision and integer-precision MCF problems with different scales from one hundred to five thousand size, exhibiting significant time efficiency and the ability to approximate optimal solutions. The experimental results confirm that your method can achieve a solution of higher quality. It is a bit surprising since the vanilla implementation of Sinkhorn algorithm requires much time to converge to a high-accurate solution. Would you like to give me some reasons why your method could achieve the high-accurate solutions in practice?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The authors extend the vanilla OT within a bipartite graph to a more general graph case, and thus propose optimal flow transport, in which the marginal constraints are replaced by flow balance constraints.\n\n2. The authors propose the entropic OFT to get the GPU-friendly OFT-Sinkhorn algorithm to get the approximate solution of the OFT problem. The theoretical guarantee is also proposed for global convergence.\n\n3. The authors incorporate node and edge capacity constraints into the OFT, and in this case our OFT is equivalent to the minimum-cost flow problem. By considering these constraints, the authors modify the OFT-Sinkhorn algorithm to ensure that the output satisfies capacity constraints. Experimental results on the minimum-cost flow problem showcase the superiority of the proposed algorithm.", "weaknesses": "1. The idea of extending the vanilla OT within a bipartite graph to a more general graph case is not new and have been investigated in the literature. While I agree that it is meaningful to replace the marginal constraints by by flow balance constraints on nodes, this idea is novel by itself and the optimal flow transport problem in Eq. (2) is rather standard. \n\n2. It is important to note that directly adding entropy regularization cannot derive an algorithm to obtain an approximate solution as directly as vanilla OT. However, I do not think addressing this issue would be difficult and the modified formulation is Eq. (5) is also based on some standard tricks from network flow literature. Based on this formulation, the development of OFT-Sinkhorn algorithm is almost the same as that of Sinkhorn algorithm and handling node and edge capacity constraints would not significantly change the algorithmic scheme. \n\nI would like to say that I do not undermine the value of new methods but the contribution of this paper is a little bit incremental to me from a technical viewpoint. This is a good work by itself but does not offer too much insights.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZkDvc4Kvug", "reviewer": "Reviewer_T4Wu", "summary": "This work extends optimal transport to network flow problems and formulated an entropic algorithm.", "questions": "No questions. All are suggestions listed in weakness already.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The writing is clear and clarity is good.\n\n2. The numerical proposal is sound.\n\n3. The contribution of this work is hard to gauge due to point 3,4,5 in the weakness section. So the result, while looking promising, is currently only a minor strength of this work.", "weaknesses": "1. The authors omitted connections to constrained optimal transport, such as Benamou et al 2014 (1412.5154) and Tang et al 2024 (2403.05054), which are both general-purpose algorithms with entropic regularization.\n\n2. There are numerous instances of grammatical errors in this work. The authors are advised to change it. (This doesn't affect this reviewer's evaluation for the score.)\n\n3. While OFT-Sinkhorn with edge/node/node&edge constraints is definitely a good contribution, it doesn't seem clear why one would not simply use Sinkhorn in the unconstrained case. The authors have not included numerical comparison to make this point across. What is better? Sinkhorn has more GPU acceleration and should be much better in the unconstrained case (say, you take the same regularization strength and compare results).\n\n4. In the numerical experiments, the proposed OFT-Sinkhorn algorithm seems to do better than Gurobi, which is quite confusing as Gurobi should output the ground truth. The reviewer suspects that it is because the OFT-Sinkhorn solution is unfeasible, thereby giving a better objective. If this interpretation is correct, then the authors need to change to a better metric for comparison.\n\n5. The benchmark ZKW and Real methods are exact methods and they do not seem to be up to date. The authors need to also consider state-of-the-art methods for comparison, and the authors need to consider approximate algorithms.\n\n6. The conclusion section needs a rewrite. It seems to suggest that this method can solve NP-hard graph-based problems, which is why the wording needs to be refined.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)