Optimal Flow Transport and its Entropic Regularization: a GPU-friendly Matrix Iterative Algorithm for Flow Balance Satisfaction

Thank you for your valuable feedback. We will adress all the grammatical errors in the next version. Hopefully, our response below adequately addresses your concerns.

Q1.The authors omitted connections to constrained optimal transport

Thank you for your suggestion, we will provide a related description:

Both [1, 2] and our method are based on entropic regularized algorithms and use the objective as an evaluation metric.

The main difference is that [1, 2] are bipartite graph-based algorithms and the constraints used are different.

[1] also mentions transportation problems with capacity constraints:

$

\min_{\mathbf{P} \in \mathbb{R}_+^{N \times N}} { \langle \mathbf{D}, \mathbf{P} \rangle - \epsilon H(\mathbf{P}) ; ; ; \mathbf{P} \mathbf{1} = \mathbf{p}, ; \mathbf{P}^T \mathbf{1} = \mathbf{q}, ; \mathbf{P} \leq \mathbf{S} }

$

The difference lies in: 1. We extend OT on transport problem to a more general graph case (the MCF problem).

2. The capacity constraints in [1] are limited on bipartite graphs, while ours can impose capacity on any node or edge.

3. [1] follows marginal constraint while we use flow balance constraint:

$

\min_{\mathbf{P} \in \mathbb{R}_+^{N \times N}} { \langle \mathbf{D}, \mathbf{P} \rangle - \epsilon H(\mathbf{P}) ; ; ; \mathbf{P} \mathbf{1} = \mathbf{q+d}, ; \mathbf{P}^T \mathbf{1} = \mathbf{q-s+d}, ; \mathbf{P} \leq \mathbf{S} }

$

To the best of our knowledge, we are the first to apply entropic regularization to solve approximate solutions to the MCF problem with capacity constraint.

[2] primarily consisting of inequality constraints. However, the formulations differ: in [2], the inequality constraint is on the assignment matrix, while still retaining the original Sinkhorn-style marginal constraints:

$

\min_{\mathbf{P} \in \mathbb{R}_+^{N \times N}} { \langle \mathbf{D}, \mathbf{P} \rangle + \epsilon H(\mathbf{P},s_1, \ldots, s_K) ; ; ; \mathbf{P} \mathbf{1} = \mathbf{p}, ; \mathbf{P}^T \mathbf{1} = \mathbf{q} ; }

$

Whereas our work transforms the marginal probability constraints into flow balance constraints and provide a new perspective to introdece new iteration variable q, for details please refer to Appendix-C.1.

Those works are parallel relationship and can be complementary. In the future, we could consider combining their constraints to solve new problems.

Q2 It doesn't seem clear why one would not simply use Sinkhorn in the unconstrained case.

Apologies for any misunderstanding. We would like to provide the following clarification and hope it addresses your concerns.
The original Sinkhorn algorithm [1] is a matrix iterative algorithm applied to transportation problems, where an entropic regularization term is introduced to obtain an approximate solution. Our algorithm extends the original Sinkhorn from bipartite graphs to more general graph cases. The flow balance constraint of ours is :

More comparison with SOTA/Approximate MCF Method

Here, we further incorporated the suggestions of the reviewers by adding more comparison between our method and SOTA MCF algorithm. We observed that their experiments focused on extremely large sparse graphs. To align with this, we've re-implemented our algorithm to better suit the triplet structure of sparse graphs. For a comparative analysis, we used the three massive datasets they published, pitting our method against theirs. Additionally, we ran their approach on the medium and small datasets from Table 2 in our paper, with the results summarized as follows. The pns method refers to the approach outlined in [1], while lemon[2] is a classic solver for MCF problems(Here we test on lemon-ns which is the network simplex version of lemon). The new dataset(Netgen_8_20/Netgen_lo_8_20/Vision_inv_05) used in this study are all sourced from [1]. Besides the original generater(NETGEN) taken in our main paper, Vsion instance is based on large-scale maximum flow problems arising in computer vision applications.The EOFT timings were tested on an NVIDIA GeForce RTX 4090 GPU.

This table is the experiment setting:

From the results, we have found that Lemon is best suited for running on medium and small datasets, as it is a highly optimized CPU-based MCF solver. On the three newly added large-scale datasets, Real/ZKW/Gurobi exceeded the maximum time limit we set, hence represented as ‘-’, while our algorithm can quickly obtain a stable approximate-optimal solution.

As the first work to apply entropic regularization to the MCF problem and achieve a GPU-friendly algorithm, our algorithm effectively addresses the minimum cost flow problem on extremely large sparse graphs, and in some instances, even outperforms the current SOTA algorithms in obtaining approximate solutions. This demonstrates the huge potential of matrix-iteration-based algorithms for designing more efficient GPU algorithms in the flow community. Hope that our additional experiments will enhance your confidence and recognition of our work.

Reference

[1] Parallel network simplex algorithm for the minimum cost flow problem. Concurrency and Computation: Practice and Experience, 2022 [2] Efficient implementations of minimum-cost flow algorithms. arxiv 2012

Q1 Further clarify the difference between the current paper and the existing works

Q1.1 In my understanding, these studies can compute transport couplings but need to precompute the shortest distances on the graph.

Sorry for any misunderstanding. Yes, they can compute transport couplings, but they first need to calculate the shortest path before solving the optimal transport problem between the source and target nodes.

As demonstrated in [1, 2], their algorithms do not directly compute the flow and are unable to impose capacity constraints on the nodes. Consequently, they cannot address constrained MCF problems as our method does.

Additionally, they are not GPU-friendly and cannot be embedded into neural networks. They will cause gradient truncation while ours and Sinkhorn[3] allowing the gradient backpropagation.

Q1.2 Why can you directly compute transport couplings within the graph?

We will explain why our method can directly compute the coupling from three perspectives, hope this will address your concerns.

1. Compared to [4], we address the iteration issue for isolated points on the graph, a problem not considered in previous works. By introducing virtual transport flows from each node to itself, we enable isolated points to participate in the iterations, even if they originally have no incoming or outgoing flows.

2. We extend the marginal probability constraints in the original Sinkhorn algorithm: $\mathbf{P}\mathbf{1} = \mathbf{a}, \mathbf{P}^\top\mathbf{1}=\mathbf{b}$ into flow balance constraint:

May we ask if we have addressed your concern? We do hope we could resolve your any potential questions!

We would like to express our sincere gratitude for thoroughly evaluating our paper and providing insightful and valuable feedback. We are genuinely committed to addressing your concerns and respond to your specific comments below.

Q1. There is an error in the 10kx10k line for the W/ edge+note constraints.

Sorry for the writing errors，we fixed it in the next version main paper,thank you for your valuable advice.

Q2.What if the authors stop the compared algorithms at the same obj value their algorithm achieves?

Thank you for the reminder. However, these algorithms do not support using the objective (Obj) value as an early stopping criterion.

Both Real and ZKW are augmentation path-based algorithms that repeatedly check if the residual network can accommodate more flow. As a result, their Obj value increases throughout the solving process, making it unsuitable for early termination.

Regarding Gurobi, experiments show that when solving MCF problems, it uses either the dual simplex or primal simplex algorithm. During iterations, the objective value only change between Inf and the optimal solution (e.g., in an experiment with 500 nodes, the first 10,089 iterations showed "Inf," and the optimal solution was reached only after the 10,090th iteration). This behavior likely stems from the nature of the MCF problem.

In contrast, our matrix-based approximation algorithm can quickly provide approximate solutions, offering a significant speed advantage.

Q3 It is unclear which algorithm would be faster between "Real" and "ours"?

We apologize for the misunderstanding, and we will clarify the experimental setup more thoroughly in the next version of the paper. Our algorithm is more effective than Real at solving dense graphs problems. In Table 1, under the 10k × 10k W/edge+node constraint, Real is indeed slightly faster than our algorithm. However, across other scales and constraints, our algorithm outperforms Real. Furthermore, under integer precision (as shown in Table 2), our algorithm is consistently faster than Real. We believe the main factor here is the sparsity of the graph. As shown in Appendix D, the out-degree of the Uniform dataset is typically 8, making it a sparse graph, whereas the Integer dataset usually has an edge count exceeding nlog n, making it a dense graph. Matrix-iteration-based algorithms tend to perform better on dense graphs. If needed, we would be happy to provide more detailed decoupled experiments on graph density for further analysis.

Q4 The explanation for "these studies primarily rely on graph's shortest distances" Is it slower?

Apologies for not clearly explaining our advantages. While OT algorithms on graphs may not be slower—and could even be faster than ours—they are not generic or GPU-friendly.

As shown in [1, 2], these algorithms do not compute the flow at intermediate nodes or enforce capacity constraints, so they cannot solve constrained MCF problems like ours. They also aren't compatible with neural networks and may cause gradient truncation, unlike our method and Sinkhorn[3], which support gradient backpropagation.

These algorithms treat the graph problem as a transportation problem on the nodes, first calculating shortest paths before solving the optimal transport between source and target. They can't handle capacity constraints at nodes. In contrast, our matrix-based entropic regularization algorithm directly iterates to compute the coupling on the constrained graph.

There is no available PyTorch or Python code for comparison, but we will make every effort to replicate it and report it as soon as possible.

Q5.Their relation to existing works could be slightly clarified.

Thank you for your valuable advice. We will provide a more detailed explanation of the settings on our next main papaer. Next, we will explain the differences between our method and other approaches:

As a more general form of the transportation problem, the MCF problem has been well studied. However, to the best of our knowledge, we are the first to apply entropic regularization for approximate solutions to the MCF problem. Given the use of entropic regularized methods in machine learning, they can be embedded in the output layer of neural networks to enable gradient backpropagation. Thus, the matrix-vector iterative algorithm we propose also holds potential for applications in fields like GFlowNets[4], where the generation process aligns with our algorithm's flow balance constraints, making it a promising tool for future GFlowNet designs.

Reference

[1] Sobolev transport: A scalable metric for probability measures with graph metrics. AISTATS 2022

[2] Generalized Sobolev Transport for Probability Measures on a Graph. ICML 2024

[3] Learning combinatorial embedding networks for deep graph matching. CVPR 2019.

[4] Gflownet foundations. JMLR 2023

May we ask if we have addressed your concern? We do hope we could resolve your any potential questions!

Thank you for your thorough review. Hopefully, our response below adequately addresses your concerns.

Sorry, we forgot to mention in the main paper that our code is provided in the supplementary files. We have added it in the next version.

Q1. How does the proposed algorithm compare with existing GPU-accelerated or matrix-based methods.

Thank you for the reminder. However, we are the only GPU-accelerated algorithm with a matrix-based approach. Other papers, such as [4, 5], focus on the maximum flow problem, which differs from the minimum cost flow problem. The maximum flow aims to maximize the flow without considering costs, while the MCF problem includes both capacity limits and associated costs. We reviewed existing MCF solvers, including [6, 7, 8, 9]. [6] offers a parallel network simplex algorithm but lacks open-source code. [7] presents the classic MCF solver LEMON, while [8] introduces a continuous shortest path algorithm, and [9] discusses a parallel simplex algorithm for CPU-based multi-threading. None of them can run on GPU. To our knowledge, we are the first to apply entropic regularization to the MCF problem and propose a GPU-efficient matrix iterative algorithm. If we've missed anything, we would be happy to include additional comparative experiments.

Q2. Is there any machine learning problem that can apply the algorithms of this paper?

Thank you for your valuable advice. Our method can indeed be applied to machine learning, including solving NP-hard problems like the TSP and traffic flow prediction. Many real-world problems, such as the TSP, involve flow balance constraints, which can be formulated as:

$

% \textstyle \min_{\mathbf{X} \in U(\mathbf{1}, \mathbf{1})} \langle \mathbf{D}, \mathbf{X} \rangle \quad \text{s.t.} , \mathbf{P} \leq (n-1)\mathbf{X}, , \mathbf{P}\mathbf{1}_n - \mathbf{P}^\top\mathbf{1}_n = \mathbf{s}

$

Here, $\mathbf{D}$ is the distance matrix, $\mathbf{X} \in U(\mathbf{1}, \mathbf{1})$ enforces $\mathbf{X}\mathbf{1} = \mathbf{1}$ and $\mathbf{X}^\top\mathbf{1} = \mathbf{1}$, $\mathbf{P}$ is the commodity flow matrix, and $\mathbf{s} = (n-1, -1, -1, \dots, -1)$ represents the flow starting from the first node.

Our method satisfies these constraints and can be used as the output layer of a neural network to produce sparse assignment matrices, acting as supervision for the TSP neural solver.

Q3. Have the authors evaluated the performance of their algorithm on CPUs?

Thank you for the reminder. We will provide the CPU experiments of the algorithm as follows:

Here, we show a comparison of the algorithm's running time when executed on both CPU and GPU under four constraints.

Q4. The MCF problem is well-studied, and applying entropic regularization is a common practice.

Although the MCF problems as well as the transportation problem is well-studied, but significant advances in optimal transport theory, such as entropic regularized algorithms for doubly stochastic matrices [1] or domain adaptation [2], continue to emerge. MCF problem is a more general form of the transport problem, and to our knowledge, we are the first to apply entropic regularization for approximate solutions to MCF.

Given the application of these entropic regularized methods in the field of machine learning, they can be embedded in the output layer of neural networks allowing backpropagation of gradients. Our matrix-based iterative algorithm also shows potential for applications in fields like GFlowNets[3], where the generation process aligns with our algorithm’s flow balance constraints, making it a promising tool for future GFlowNet designs.

Reference

[1] Learning combinatorial embedding networks for deep graph matching.CVPR 2019.

[2] Optimal transport for multi-source domain adaptation under target shift.PMLR 2019

[3] Gflownet foundations. JMLR 2023

[4] Large graph algorithms for massively multithreaded architectures. IIIT Hyderabad 2009

[5] Efficient CUDA algorithms for the maximum network flow problem. GPU Computing Gems Jade Edition 2012

[6] Multi-granularity hybrid parallel network simplex algorithm for minimum-cost flow problems. J Supercomput 2020

[7] Efficient implementations of minimum-cost flow algorithms. arXiv 2012

[8] muSSP: Efficient Min-cost Flow Algorithm for Multi-object Tracking. NIPS 2020

[9] Parallel network simplex algorithm for the minimum cost flow problem. CONCURR COMP-PRACT E 2022

May we ask if we have addressed your concern? We do hope we could resolve your any potential questions!

More comparison with SOTA/Approximate MCF Method

Here, we further incorporated the suggestions of the reviewers by adding more comparison between our method and SOTA MCF algorithm. We observed that their experiments focused on extremely large sparse graphs. To align with this, we've re-implemented our algorithm to better suit the triplet structure of sparse graphs. For a comparative analysis, we used the three massive datasets they published, pitting our method against theirs. Additionally, we ran their approach on the medium and small datasets from Table 2 in our paper, with the results summarized as follows. The pns method refers to the approach outlined in [1], while lemon[2] is a classic solver for MCF problems(Here we test on lemon-ns which is the network simplex version of lemon). The new dataset(Netgen_8_20/Netgen_lo_8_20/Vision_inv_05) used in this study are all sourced from [1]. Besides the original generater(NETGEN) taken in our main paper, Vsion instance is based on large-scale maximum flow problems arising in computer vision applications.The EOFT timings were tested on an NVIDIA GeForce RTX 4090 GPU.

This table is the experiment setting:

From the results, we have found that Lemon is best suited for running on medium and small datasets, as it is a highly optimized CPU-based MCF solver. On the three newly added large-scale datasets, Real/ZKW/Gurobi exceeded the maximum time limit we set, hence represented as ‘-’, while our algorithm can quickly obtain a stable approximate-optimal solution.

As the first work to apply entropic regularization to the MCF problem and achieve a GPU-friendly algorithm, our algorithm effectively addresses the minimum cost flow problem on extremely large sparse graphs, and in some instances, even outperforms the current SOTA algorithms in obtaining approximate solutions. This demonstrates the huge potential of matrix-iteration-based algorithms for designing more efficient GPU algorithms in the flow community. Hope that our additional experiments will enhance your confidence and recognition of our work.

Reference

[1] Parallel network simplex algorithm for the minimum cost flow problem. Concurrency and Computation: Practice and Experience, 2022 [2] Efficient implementations of minimum-cost flow algorithms. arxiv 2012