Warm-starting Push-Relabel

Authors: sami  davies
sergei  vassilvitskii
yuyan  wang
u c berkeley
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 21:02:32

Abstract: Push-Relabel is one of the most celebrated network flow algorithms. Maintaining a pre-flow that saturates a cut, it enjoys better theoretical and empirical running time than other flow algorithms, such as Ford-Fulkerson. In practice, Push-Relabel is even faster than what theoretical guarantees can promise, in part because of the use of good heuristics for seeding and updating the iterative algorithm. However, it remains unclear how to run Push-Relabel on an arbitrary initialization that is not necessarily a pre-flow or cut-saturating. We provide the first theoretical guarantees for warm-starting Push-Relabel with a predicted flow, where our learning-augmented version benefits from fast running time when the predicted flow is close to an optimal flow, while maintaining robust worst-case guarantees. Interestingly, our algorithm uses the gap relabeling heuristic, which has long been employed in practice, even though prior to our work there was no rigorous theoretical justification for why it can lead to run-time improvements. We then show our algorithmic framework works well in practice, as our warm-start version of Push-Relabel improves over the cold-start version by a larger and larger percentage as the size of the image increases.

Main paper: 
 introduction: 
 Maximum flow is a fundamental problem in combinatorial optimization. It admits many algorithms, from the famous Ford-Fulkerson algorithm [FF56] which employs augmenting paths, to recent near-linear time scaling based approaches [CKL + 22]. In practice, however, the Push-Relabel family of algorithms remains one of the most versatile and is often the standard benchmark to which new flow algorithms are compared [Wil19, CH09] .Designed by Goldberg and Tarjan [GT88] , the core Push-Relabel algorithm (Algorithm 1) has running time O(n 2 m), where n and m are the number of vertices and edges in the network. Given the popularity of max-flow as a subroutine in large-scale applications [BK04, KBR07, Wil19] , it is no surprise that improving running times has been a subject of a lot of study, with multiple heuristic methods being developed [JM + 93, CG95, AKMO97, Gol08].To complement these heuristics, researchers studied max-flow in the algorithms with predictions framework (or learning-augmented algorithms) [MV22] . Two groups initiated the study and proved that the running time of the Edmonds-Karp selection rule for Ford Fulkerson can be improved from O(m 2 n) to O(m||f * -f || 1 ), where f * is an optimal flow on the network and f is a predicted flow [DMVW23, PZ22] . These algorithms start the augmenting path algorithms from a feasible flow obtained from the predicted flow, then bound the number of augmentations by the ℓ 1 -distance between the predicted and maximum flows. While these works have improved upon the cold-start, non learning-augmented versions, it is important to note that they have improved upon sub-optimal algorithms for max flow. In this work, we show how to warm-start Push-Relabel, whose cold-start version is nearly state-of-the-art for the maximum flow problem. This directly addresses the challenge specified in [DMVW23] on bringing a rigorous analysis for warm-starting non-augmenting path style algorithms. In the process of doing so, we provide a theoretical explanation for the success of the popular gap relabeling heuristic in improving the running time of Push-Relabel algorithms. Specifically, both the gap relabeling heuristic and our algorithm maintain a cut with monotonically decreasing t-side nodes (see Section 1.2 for more), which directly leads to improved running times for our version of Push-Relabel and the gap relabeling heuristic. Lastly, we show that our theory is predictive of what happens in practice with experiments on the image segmentation problem.Graph, flow and cut concepts. Our input is a network G = (V, E), where each directed edge e ∈ E is equipped with an integral capacity c e ∈ Z ≥0 . Let |V | = n and |E| = m. G contains nodes s, the source, and t, the sink. G is connected: ∀u ∈ V , there are both s -u and u -t paths in G. A flow f ∈ Z m ≥0 is feasible if it satisfies: (1) flow conservation, meaning any u ∈ V \ {s, t} satisfy (v,u)∈E f e = (u,w)∈E f e ; (2) capacity constraints, meaning for all e ∈ E, f e ≤ c e . Our goal is to find the maximum flow, i.e. one with the largest amount of flow leaving s.We call f a pseudo-flow if it satisfies capacity constraints only. A node u ∈ V \ {s, t} is said to have excess if it has more incoming flow than outgoing, i.e., (v,u)∈E f e > (u,w)∈E f e ; analogously it has deficit if its outgoing flow is more than ingoing. We denote the excess and deficit of a node u with respect to f as exc f (u) = max{ (v,u)∈E f e -(u,w)∈E f e , 0} and def f (u) = max{ (u,w)∈E f e -(v,u)∈E f e , 0}, where at most one can be positive. A pseudo-flow can have both excesses and deficits, whereas a pre-flow is a pseudo-flow with excess only.For a pseudo-flow f , the residual graph G f is a network on V ; for every e = (u, v) ∈ E, G f has edge e with capacity c ′ e = c e -f e and a backwards edge (v, u) with capacity f e . Let E(G f ) denote the edges in G f . The value of a pseudo-flow f is val(f ) = e=(s,u) f e , the total flow going out of s. Notice that this is not necessarily equivalent to the total flow into t since flow conservation is not satisfied. A cut-saturating pseudo-flow is one that saturates some s -t cut in the network. Push-Relabel maintains a cut-saturating pre-flow; equivalently, there is no s -t path in the residual graph of the pre-flow. We use δ(S, T ) to denote an s -t cut between two sets S and T . Note that the cut induced by any cut-saturating pseudo-flow f can be found by taking T = {u ∈ V : ∃u -t path in G f } (including t) and S = V \ T .Prediction. The prediction that we will use to seed Push-Relabel is some f ∈ Z m ≥0 , which is a set of integral values on each edge. Observe that one can always cap the prediction by the capacity on every edge to maintain capacity constraints, so throughout this paper we will assume f is a pseudo-flow. It is important to note that our predicted flow is not necessarily feasible or cut-saturating, and part of the technical challenge is making use of a good predicted flow despite its infeasibility.Error metric. We measure the error of a predicted pseudo-flow f on G. The smaller the error is, the higher quality the prediction is, and the less time Push-Relabel seeded with f should take. A pseudo-flow becomes a maximum flow when it is both feasible and cut-saturating. Hence, the error measures how far f is from being cut-saturating while being feasible. We say that a pseudo-flow f is σ far from being cut-saturating if there exists a feasible flow f ′ on G f where val(f ′ ) ≤ σ and f + f ′ is cut-saturating on G (though the cut does not have to be a min-cut). To measure how far f is from being feasible, we sum up the total excesses and deficits. In total we use the following error metric: Definition 1. For pseudo-flow f on network G, the error of f is the smallest integer η such that (1) f is η far from being cut-saturating and (2) u∈V \{s,t} exc f (u) + def f (u) ≤ η.If η = 0, f is the max-flow and the cut that is saturated is the min-cut. The previously studied error metric for predicted flows, such as by [DMVW23] and [PZ22] , was ||f * -f || 1 , for any max-flow f * . PAC-learnability is the standard to justify that the choice of prediction and error metric are reasonable. Flows are PAC-learnable with respect to the ℓ 1 -norm [DMVW23] . Our results hold replacing our error metric with the ℓ 1 -norm because our metric provides a more fine-grained guarantee than the ℓ 1 -norm (i.e., if a prediction f has error η, then η ≤ ||f * -f || 1 ). Thus we can omit any theoretical discussion of learnability. We present this work with respect to our error metric as we find the ℓ 1 error metric to be unintuitive, as it is not really very descriptive of how good a predicted flow is. Push-Relabel. The "vanilla" Push-Relabel algorithm maintains a pre-flow and set of valid heights (also called labels) on nodes. Heights h : V → Z ≥0 are valid for f if for every edge(u, v) ∈ E(G f ) with positive capacity, h(u) ≤ h(v) + 1, and if h(s) = n and h(t) = 0. An edge (u, v) ∈ E(G f ) is called admissible if h(u) = h(v) + 1 and c ′ (u,v)> 0, which means we can push flow from u to v. The algorithm starts with f init , where f init e = c e for all e = (s, u) and otherwise f init e = 0. It then pushes flow on admissible edges (u, v) for u with excess flow when possible, and otherwise the algorithm updates the heights. See Algorithm 1.Input: Network G Define f e = c e for e = (s, u) and f e = 0 for all other e Define h(u) = 0 for all u ∈ V \ {s} and h(s) = n Build residual network G f while ∃ node u with exc f (u) > 0 do if ∃ admissible (u, v) ∈ E(G f ) with f (u,v) < c (u,v) then Update f by sending an additional flow value of min{exc f (u), c ′ (u,v) } along (u, v) Update G f accordingly else update h(u) = 1 + min v:(u,v)∈E(G f ) h(v) Output: f All heights in Push-Relabel are bounded. Lemma 1. For a pre-flow f on network G, every node u with exc f (u) > 0 has a path in G f to s. Further, for d(u, v) the length of the shortest path from u to v in G f , any valid heights in Push-Relabel (Algorithm 1) satisfy h(u) ≤ h(v) + d(u, v). For all u ∈ V , h(u) ≤ h(s) + n = 2n.At any point of the algorithm, the s -t cut maintained can be found using the heights. Lemma 2. For a pseudo-flow f with valid heights h on network G, let θ be the smallest positive integer such that θ / ∈ {h(u)} u∈V . Then sets S = {u ∈ V : h(u) > θ} and T = {u ∈ V : h(u) < θ} form a cut saturated by f . We call this cut induced by the heights. Indeed, such a threshold θ can be found because {h(u)} u∈V has at most n different values, but h(s) = n and h(t) = 0, so among the n + 1 values {0, 1, . . . , n}, at least one is not in the set. Note that δ(S, T ) is a saturated cut by definition of valid heights. A saturated cut can also be defined by whether a node can reach the sink in the residual graph. Lemma 3. For any pseudo-flow f on network G, let T be all nodes that can reach t in G f (including t) and S = V \ T . If s ∈ S, then δ(S, T ) is a saturated s -t cut.Lemmas 2 and 3 apply to all pseudo-flows, whereas vanilla Push-Relabel must take a pre-flow as input. Before this work, it was unclear how to seed Push-Relabel with anything other than f init .With the gap relabeling heuristic, whenever there is some integer 0 < θ < n with no nodes at height θ, then nodes with height between θ and n have their height increased to n. See Algorithm 2.We first study Push-Relabel with the gap relabeling heuristic when seeded with a prediction that is a cut-saturating pre-flow with error η. We prove Algorithm 2 finds an optimal solution in time O(η • n 2 ). The running time also holds for cold-start versions of the algorithm when the max-flow/min-cut value is known to be bounded by η. This is (1) the first theoretical analysis of the gap relabeling heuristic, and, (2) the first result showing a running time bounded by the volume of the cut in Push-Relabel. While Ford-Fulkerson admits a naive running time bound of O(η • m) when the max-flow value is at most η, an analogous claim was not previously known for Push-Relabel.The algorithm maintains a cut whose t-side is monotonically decreasing (i.e., it moves nodes on the t-side of the cut to the s-side, but not the other way around), and resolves excess on the t-side by routing excess flow to t, or updating the cut so the excess node is on the s-side of the new cut. The same insight will be used in our warm-started version of Push-Relabel seeded with any pseudo-flow.Our main result applies in the general setting where the prediction is any pseudo-flow. Our warm-start version of Push-Relabel that is seeded with a general pseudo-flow has several phases. In the first phase, we show that one can modify the prediction to be a cut-saturating pseudo-flow. We begin the second phase by routing flow within the two sides of the cut induced by the pseudo-flow to resolve some of the excess and deficit. The maintained cut gradually changes as we send flow from node to node, and push certain nodes to different sides of the cut. We continue changing the cut until all excess nodes end up on the s-side of the cut and all deficit nodes end up on the t-side of the cut. This "swapping" procedure between excess and deficits nodes between the sand tsides of the cut is our biggest technical innovation. Either the excesses are resolved within the t-side of the cut, or we find a new cut between the t-side excess nodes and the t-side deficit nodes plus t. We modify the cut in G accordingly to separate all excess from the t-side, which also results in a cut whose t-side is monotonically decreasing-an interesting point which also occurs in the cut maintained by the gap relabeling heuristic. A mirrored version of this process is performed on the s-side of the cut.In the final phase, we have a new cut-saturating pseudo-flow with all excess nodes on the s-side of the cut and all deficit nodes on the t-side of the cut. This cut is actually a min-cut. On the s-side, the excess nodes send flow to the source, and on the t-side, the sink sends flow to deficit nodes (hence removing existing flows). The result is a max-flow. See Figure 1 for an illustration of phases 2 and 3.In Section 4, we run our warm-start Push-Relabel compared to a cold-start version. We see that the warm-start improves over the cold-start by a larger percentage as the size of the image increases.Our work identifies that there is a monotonic property in the cuts when Push-Relabel is implemented with the gap relabeling heuristic that directly results in faster running time when the value of the max flow/min cut is small (Corollary 1). While such a result was known for Ford-Fulkerson, this was not known for Push-Relabel prior to our work. We leave as an open direction whether this monotonic property may have further theoretical importance in improving Push-Relabel analyses on more general classes of networks.The running time of warm-start Push-Relabel is O(n 2 η), while the running time of warm-start Edmonds-Karp is O(mη) [DMVW23] . We do not believe that the bound for warm-start Push-Relabel being no faster than that of warm-start Edmonds-Karp is a weakness in our analysis, but is instead an artifact of the community's lack of understanding on why Push-Relabel performs so much better in practice than its theoretical bounds guarantee. Improving our theoretical understanding of algorithms that do well in practice (like Push-Relabel or the Simplex Method) is one of the pillars of the field of beyond worst-case analysis [Rou21] . Researchers have long suspected that there should be a way to parameterize instances or use practical heuristics to justify why Push-Relabel is so much better in practice than its theoretical worst-case bound would suggest [CG95, Hoc08, CM99].2 Gap Relabeling Push-Relabel: Cold-and Warm-StartWe briefly overview the performance of Push-Relabel with the gap relabeling heuristic (Algorithm 2) when given a cut-saturating pre-flow f , and tie the running time to the error of f . Proofs in this section are deferred to Appendix A.2, as their more involved analogs are in Section 3. (u), c ′ (u,v) } along (u, v) Update G f accordingly else Raise the height of u to be h(u) = min v:(u,v) h(v) + 1 Update θ = min{z ∈ Z >0 : ∄u ∈ T with z = h(u)} for p ∈ T with h(p) > θ doRemove p from T , add p to S Update p's height to h(p) = n Take G f as input and run Algorithm 1 on it to fix excesses, outputs flow f * Return flow f + f * and the cut δ(S, T ) it maintains Algorithm 2 begins by running Algorithm 4 as a subroutine to find the cut saturated by f and define valid heights for f which also induce that cut. Algorithm 4 runs a BFS in the residual graph to find all nodes that have a path to t and names this set T . The other nodes belong to S. By Lemma 3 the cut δ(S, T ) is saturated by f . In the main WHILE loop, the algorithm maintains the cut δ(S, T ) such that all heights in T compose a series of consecutive numbers starting from 0. The cut only changes when a node is relabeled in a way that results in a break in the series of consecutive heights starting from 0 in T , where the smallest missing height (the node's height before relabeling) is denoted by θ. The algorithm then removes all nodes from T with height bigger than θ; importantly, these nodes will never enter T again. The WHILE loop terminates when T has no excess, thus finding the min cut.Lemma 4. Let f be a pre-flow saturating cut δ(S, T ) on network G. If there are no excess nodes in T , then all excess in S can be sent back to s without crossing the cut, implying δ(S, T ) is a min-cut.We show that the running time is tied to η, which, in this case, is the total excess in f . Theorem 2. Given a cut-saturating pre-flow f with error η on network G, Algorithm 2 finds a max-flow/min-cut in running time O(η • n 2 ).Although Algorithm 2 is presented as being seeded with an existing pre-flow, the same bound applies to the cold-start gap relabeling Push-Relabel when the min-cut of G is at most η. One only has to seed it with f init as in Algorithm 1, which saturates the cut δ({s}, V \ {s}). This will be useful in Section 3, as we repeatedly use Algorithm 2 as a subroutine on networks with small min-cut.Corollary 1. If network G is known to have a max-flow/min-cut value of at most η, one can use Algorithm 2 to obtain a max-flow and min-cut for G in running time O(η • n 2 ).3 Warm-starting Push-Relabel with General Pseudo-flowsWe extend the results in Section 2 to when the given prediction is a general pseudo-flow f as opposed to a cut-saturating pre-flow, i.e., f may not be cut-saturating and may have deficit nodes. The first phase of our algorithm computes η and augments f by finding an s -t flow to add to f so that the resulting pseudo-flow saturates a cut. We defer discussion of this pre-processing phase to Appendix A.2 (see Lemma 8 and Algorithm 5). Once we have a cut-saturating pseudo-flow f and η, we are ready to define the accompanying heights and cut using Algorithm 4. Note that the initial cut with two sides T 0 = {u ∈ V : ∃u -t path in G f } and S 0 = V \ T 0 is by definition the same cut as that induced by the heights (as in Lemma 2).We update the pseudo-flow so that it always maintains a saturated cut, but eventually, the nodes with excess and the nodes with deficit are separated by the saturated cut. This is a generalization of what happens in Algorithm 2, where we transfer all excess nodes to the s-side of the cut. Here, we transfer Algorithm 3 Moving all excess to the s-side of the cut Input: Network G, a cut saturating pseudo-flow f , and error η Run Algorithm 4, get output heights hLet T 0 = {u ∈ V : ∃u -t path in G f } and S 0 = V \ T 0 Build the residual G f Build G ′ on copy of G f [T 0 ] plus {s * , t * } for excess node u ∈ T 0 \ {t} do Add edge (s * , u) with capacity exc f (u) for deficit node v ∈ T 0 do Add edge (v, t * ) with capacity def f (u) Add edge (t, t * ) with capacity η + 1 Let f init (s * ,u) = c (s * ,u) for all (s * , u), and all other f init e = 0 Run Algorithm 2 on G ′ and f init , outputs f ′ and all excess to the s-side, and all deficit to the t-side of the cut. Interestingly, we observe that this is the sufficient condition for the pseudo-flow to saturate a min-cut. Lemma 5 extends Lemma 4. Lemma 5. For a cut-saturating pseudo-flow f for a network G, let δ(S, T ) be a cut it saturates. If all nodes in T have no excess and all nodes in S have no deficit, then the cut is a minimum cut.T ′ 0 , T ′′ 0 for all copies of e = (u, v) ∈ E(G f ) where f ′ e > 0 do Update f e ← f e + f ′To prove Lemma 5, we use the following result from [DMVW23]: Lemma 6 (Lemma 5 [DMVW23] ). Given any pseudo-flow f for G, every excess node has a path in G f to either a deficit node or s; every deficit node has a path in G f from either an excess node or t.Proof of Lemma 5. In G f , by Lemma 6, every excess node u in S must have a path to either a deficit node or s. Since f currently saturates δ(S, T ), the path cannot go across this cut and reach T , where all the deficits are. Therefore, u has a path back to s within set S. Similarly, for every deficit node v ∈ T there is a path that starts with either an excess node or t and ends with v. Again, since the cut δ(S, T ) is already saturated, the path must be within T , hence can only be from t to v. It follows that we can send all excess to s and send flow from t to all deficit nodes until the pseudo-flow becomes a feasible flow. Notice that δ(S, T ) remains saturated in this process, hence the resulting flow is max-flow and δ(S, T ) is min-cut.By Lemma 5, it is sufficient to find a pseudo-flow and accompanying saturated cut where the excess nodes are all on the s-side and the deficit nodes are all on the t-side. We focus on the t-side of the cut, and show that the same can be done for the s-side by considering the backwards network.Moving excess to the s-side. To resolve excess on the t-side, we solve an auxiliary graph problem.The goal is to send the maximum amount of flow from excess nodes to either deficit nodes or t within the t-side (currently denoted T 0 ). If the max-flow in this problem matches the total excess in T 0 , all excess can be resolved locally and only deficits remain; otherwise, the max-flow solution on the auxiliary graph also provides us with a min-cut that "blocks" excess nodes from deficit nodes and t. This cut will become the new cut maintained by the pseudo-flow after adding the auxiliary flow to it.To construct the auxiliary G ′ , take the induced subgraph G f [T 0 ], and add a super-source and -sink s * and t * to it. Add edges (s * , u) with capacity exc f (u) for every excess node u ∈ T 0 ; add edges (v, t * ) with capacity def f (v) for every deficit node v ∈ T 0 ; and add an edge (t, t * ) with capacity η + 1.When we run cold-start Push-Relabel (Algorithm 2) on G ′ , it outputs a flow f ′ and the s * -t * cut δ(T ′ 0 , T ′′ 0 ). Note that t ∈ T ′′ 0 , since (t, t * ) has capacity η + 1 and cannot be in the min cut which is bounded by η by definition. Any s * -t * path p in G ′ along which f sends δ units of flow exactly identifies nodes u and v (where (s * , u) ∈ p and (v, t * ) ∈ p) for which δ units of flow can be sent from u to v along the interior of p in G f . We can send flow as indicated by f ′ to update f (Algorithm 3). We obtain the following guarantee.Claim 1. In Algorithm 3, the output pseudo-flow f saturates the cut δ(S 0 ∪ T ′ 0 , T ′′ 0 ), and all excess nodes are in S 0 ∪ T ′ 0 . Moreover, the total excess and deficit in G has not increased.Proof of Claim 1. Let f old denote the input to Algorithm 3. The fact that the output f saturates the cut δ(S 0 ∪ T ′ 0 , T ′′ 0 ) immediately follows from the fact that f ′ saturated the cut δ(T ′ 0 , T ′′ 0 ) in G ′ . Indeed, all edges from T ′ 0 to T ′′ 0 are now saturated and all edges from T ′′ 0 to T ′ 0 have no flow. All edges from S 0 to T ′′ 0 are already saturated in the old flow f old and remain so after adding f ′ since its flows are locally within T 0 . For the same reason, all edges from T ′′ 0 back to S 0 still have no flow. Now, we consider the total excess and deficit. First note that the nodes that have excess/deficit with respect to the updated pseudo-flow f are a subset of the nodes that had excess/deficit with respect to f old , and the excess/deficit of a node is clearly never increased. Assume for sake of contradiction there is an excess node u ∈ T ′′ 0 . Then u had excess with respect to f old too, so there is an edge (s * , u) that had capacity exc f old (u) in G ′ but was not saturated by f ′ . Further, since a min-cut in G ′ is δ(T ′ 0 , T ′′ 0 ), it must be that u can reach t in G ′ . This means that in G ′ there is a path with positive remaining capacity between s * and t * , contradicting the fact that f ′ was a max-flow in G ′ .By Claim 1, the updated f satisfies the conditions of Lemma 7 by taking S * = S 0 ∪ T ′ 0 and T * = T ′′ 0 . The running time in Lemma 7 follows by applying Corollary 1 on G ′ . Thus we have the following.Lemma 7. Let f be a pseudo-flow for network G with error η saturating cut δ(S 0 , T 0 ). Algorithm 3 finds a new cut-saturating pseudo-flow in time O(η • n 2 ) that (i) saturates an additional s -t cut δ(S * , T * ), (ii) has no excess nodes in T * , and (iii) has total excess and deficit still bounded by η.We can do a similar procedure for the s-side of the cut, this time removing deficit nodes. This is the backward process of what happens to the t-side, and can be done by reversing the graph edges and flows and running Algorithm 3 on the reversed network; see Appendix A.2 and Algorithm 6.Corollary 2. Let f be a pseudo-flow for network G with error η that saturates cut δ(S 0 , T 0 ). One can update f in time O(η • n 2 ) so that all flow in T 0 remains unchanged, but now f saturates a cut δ(S * , T * ) and there are no deficit nodes in S * .Coping with unknown η Algorithm 3 assumes η is given. When η is not know, we can run Algorithm 3 iteratively with a guess for η and double the guess each iteration. We initialize by guessing that η = 1. Run Algorithm 3 on an auxiliary graph, which is just the residual graph plus a new source node s * with a single edge (s * , s) of capacity η that is saturated upon initialization. If Algorithm 3 returns the cut (s * , s), we have augmented the pseudo-flow f with an s -t flow of η, but have not found an s -t cut yet. Double η, change both the capacity and flow on (s * , s) to be the new η, and run Algorithm 3 again. Repeat this until we have found an s -t cut. The initial f is between [ η 2 , η] away from being cut-saturating, and the whole procedure has O(η • n 2 ) running time. See Algorithm 5 for more details.Summarizing this section, we prove our main theorem.Proof of Theorem 1. Given a predicted pseudo-flow f with error η on network G, Lemma 8 proved that Algorithm 5 finds a cut-saturating pseudo-flow f for G with error η in time O(η • n 2 ). To find a min-cut, Lemma 5 shows that it is enough to find a pseudo-flow saturating a cut so that the t-side of the cut contains no excess and the s-side of the cut contains no deficit.By Lemma 7, we can run Algorithm 3 seeded with f on G to obtain an updated cut-saturating pseudo-flow with no excess on the t-side of the maintained cut in time O(η • n 2 ). Then, Algorithm 3 can be run on the backwards network B, and from Corollary 2, the updated cut-saturating pseudo-flow now has no excess on the t-side of the cut and no deficit on the s-side.The last phase can be left out if only the min-cut is desired. Suppose the min-cut is δ(S, T ). By the proof of Lemma 5, to obtain a max-flow we only need to send all excess flow back to s, and send flow from t to every deficit node. Label all nodes in S with height n and all nodes in T with height 0. Then run Algorithm 2 to fix all excess in S. The algorithm will only send flow back to s, since there is no way to cross the cut δ(S, T ). Then reverse the graph and flow, and run Algorithm 2 to fix the excess in the reversed graph, which exactly correspond to the deficit nodes in the original graph. Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: Section 1.2, Section 3, Section 4 Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
limitations: 
 Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: Any assumptions for the theoretical results are within the appropriate theorem statements. Empirically, we discuss limitations/ scope of graph cuts for image segmentation in the beginning of 4.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
theory assumptions and proofs: 
 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: We used public datasets. Links to download the datasets are given in the paper. Code is uploaded in the supplementary files.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
empirical results: 
 In this section, we validate the theoretical results in Sections 3. To demonstrate the effectiveness of our methods, we consider image segmentation, a core problem in computer vision that aims at separating an object from the background in a given image. It is common practice to re-formulate image segmentation as a max-flow/min-cut optimization problem (see for example [BJ01, BK04, BFL06]), and solve it with combinatorial graph-cut algorithms.The experiment design we adopt largely resembles that in [DMVW23] , which studied warm-starting the Ford-Fulkerson algorithm for max-flow/min-cut. As in previous work, we do not seek stateof-the-art running time results for image segmentation. Our goal is to show that on real-world networks, warm-starting can lead to significant run-time improvements for the Push-Relabel min-cut algorithm, which claims stronger theoretical worst-case guarantees and empirical performance than the Ford-Fulkerson procedures. We highlight the following:• Our implementation of cold-start Push-Relabel is much faster than Ford-Fulkerson on these graph instances, enabling us to explore the effects of warm-starting on larger image instances. This improved efficiency results from implementing the gap labeling and global labeling heuristics, both known to boost Push-Relabel's performance in practice. The actual running time scales with η better than the theoretical O(n2 η) bound. This is not totally surprising, as Push-Relabel is known to often enjoy subquadratic running time despite the bound. • As we increase the number of image pixels (i.e., the image's resolution), the size of the constructed graph increases and the savings in time becomes more significant. • Implementation choices (such as how to learn the seed-flow from historical graph instances and their solutions) that make the predicted pseudo-flow cut-saturating and that reroute excesses and deficits are crucial to the efficiency of warm-starting Push-Relabel.Each of the image groups consists of a sequence of photos of an object and its background. There are slight variations between consecutive images in a sequence, which are the result of the object and background's relative movements or a change in the camera's position. These changes alter the solution to the image segmentation problem, but the effects should be minor when the change between consecutive images is minor. In other words, we expect an optimal flow and cut found on an image in a sequence to be a good prediction for the next image in the sequence.From each group, we consider 10 images and crop them to be either 600 × 600 or 500 × 500 pixel images, still containing the object, and gray-scale all images. We rescale the cropped, gray-scaled images to be N × N pixels to produce different sized datasets. Experiments are performed for N ∈ {30, 60, 120, 240, 480}. In the constructed graph, we have 4 ). Implementation details in warm-start Push-Relabel Throughout the experiments, whenever the Push-Relabel subroutine is called on any auxiliary graph, it is implemented with the gap relabeling heuristic, as shown in Algorithm 2, and the global relabeling heuristic, which occasionally updates the heights to be a node's distance from t in the residual graph. These heuristics are known to improve the performance of Push-Relabel. As a tie-breaker for choosing the next active node to push from, we choose the one with highest height, which is known to improve the running time of Push-Relabel. We found the generic Push-Relabel algorithm without these heuristics to be slower than Ford-Fulkerson.|V | = N 2 + 2.All images from the same sequence share the same seed sets. The constructed graphs are on the same sets of nodes and edges, but the capacities on the edges are different. The first image in the sequence is solved from scratch. For the second image in the sequence, we reuse the old optimal flow and cut from the first image one, then for the i th image in the sequence, we reuse the optimal flow and cut from the i -1 st image. We reuse the old max-flow on the new network by rounding down the flow on edges whose capacity has decreased, hence producing excesses and deficits, and pass this network and flow to the warm-start Push-Relabel algorithm in Section 3.To find a saturating cut, instead of sending flow from s to t as suggested in Algorithm 5, we reuse the min-cut on the previous image δ(S 0 , T 0 ) and send flow from S 0 to T 0 that originates from either s or an excess node, and ends at either t or a deficit node. We experimented with a few different ways of projecting the old flow to a cut-saturating one on the new graph. The way we implemented was by far the most effective, although it shares the same theoretical run-time as Algorithm 5.The graph-based image segmentation method finds reasonable object/background boundaries. Figure 3 shows an example of how the target cut could evolve as the image sequence proceeds. Even with the same set of seeds, the subtle difference in images could lead to different min-cuts that need to be rectified. However, the hope is that the old min-cut bears much resemblance to the new one, hence warm-starting Push-Relabel with it could be beneficial. See Appendix B for other examples.In our experiments, η is estimated by computing both the total excess/deficit. Typically this is a loose bound, but it suffices for our purpose.Results Table 1 shows average running times for both Ford-Fulkerson in [DMVW23] and Push-Relabel. The "N/A" marks overly long run-time (>1 hour), at which point we stop evaluating the exact run-time.These results show warm-starting Push-Relabel, while slightly losing in efficiency on small images, greatly improves in it on large ones. As for the scaling of run-time with growing data sizes, both coldand warm-start's running time increases polynomially with the image width n, but warm-start scales better, and as n increases to statistics on images of sizes up to 480 × 480 pixels, which we could not do with implementations of Ford-Fulkerson, due to its slow run-time.Table 2 shows how the running time of warm-start Push-Relabel breaks down into the three phases described in Section 3: (1) finding a cut-saturating pseudo-flow;(2) fixing excess on t-side;(3) fixing deficits on s-side. Note phase (1) takes the most time, but results in a high-quality pseudo-flow, in that it takes little time to fix the excess/deficits appearing on the "wrong" side of the cut.  
conclusions: 
 We provide the first theoretical guarantees on warm-starting Push-Relabel with a predicted flow, improving the run-time from O(m • n 2 ) to O(η • n 2 ). Our algorithm uses a well-known heuristics in practice, the gap relabeling heuristic, to keep track of cuts in a way that allows for provable run-time improvements. One direction of future work is extending the approaches in this work to generalizations of s-t flow problems, for instance, tackling minimum cost flow or multi-commodity flow. A different line of work is to develop rigorous guarantees for other empirically proven heuristics by analyzing them through a lens of predictions, providing new theoretical insights and developing new algorithms for fundamental problems.A More Discussion on Warm-starting Push-RelabelWe include some more insights and details on warm-starting Push-Relabel, including omitted proofs and algorithms from the main body. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: Explained both in Section 4 and Appendix B.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: explained statistical significance.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: NA Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: NA Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.• If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [NA] Justification: NA Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Algorithm 4 is used throughout the paper to obtain valid heights on a cut-saturating pseudo-flow. It is essentially just a BFS procedure from the sink, where nodes that can reach the sink have height equal to their shortest distance to the sink in the residual graph, and nodes that cannot reach the sink have height n.Algorithm 4 Define HeightsInput: Network G, a cut-saturating pseudo-flow f Define h(s) = n, h(t) = 0 Run BFS in G f Let T = {u ∈ V : ∃u -t path in G f } Let S = V \ T for all u ∈ S do Let h(u) = n for all u ∈ T doLet h(u) be the shortest path length from u to t in G f Output: Valid heights h, and cut parts S and TThe following is a straightforward pre-processing algorithm. Given a pseudo-flow f , it finds a cut-saturating pseudo-flow and computes the value of the error η. The mirror version of Algorithm 3 is below.Proof of Lemma 3. Fix u ∈ S, v ∈ T . Since v can reach t and u cannot, any edge (u, v) from S to T in G must be saturated by f , and any edge (v, u) from T to S in G must have no flow. This is because if either of these were not true, the edge (u, v) in G f would have positive capacity, allowing u to reach t. Hence δ(S, T ) is saturated by f . Proof of Lemma 4. It is known from the proof of the vanilla Push-Relabel algorithm that all excess nodes in a pre-flow must have a path back to s; see Lemma 1. When f saturates δ(S, T ), such a path cannot go from S to T , so the path must be within S. The last two lines of Algorithm 2 will resolve the excesses without effecting the saturated cut. So we have a feasible flow saturating a cut, meaning the flow is a max-flow and the cut is a min-cut. Proof of Theorem 2. The algorithm first works to resolve excess in T , possibly moving nodes from T to S to do so. Once all excess is in S, correctness follows from Lemma 4. Note that the conditions of Lemma 4 are satisfied since by Lemma 3 the cut output by Algorithm 4 is saturated by f .To bound the running time of Algorithm 2, we use a potential function argument that is different from that in the standard Push-Relabel analysis.We first bound the running time of the main WHILE loop that terminates when all excess is contained in S and the min-cut is found. We define the potential function Φ(T ) = u∈T exc f (u) • h(u). The operations involved change the value of Φ(T ) in the following way.-Saturated/Unsaturated push: In either case, at least one unit of excess flow is pushed from a higher height to a lower height, since for edge (u, v) to be admissible, h(u) = h(v) + 1. Therefore, Φ(T ) decreases by at least 1.-Relabeling a node to open up new admissible edges: Any such relabeling operation increases Φ(T ). However, the total of all of these increases is at most η • n 2 . The η term upper bounds the possible excess at any node, whereas the n 2 term is because any node's (of which there are at most n) height only ever increases, and the height cannot increase beyond n before it must leave T permanently.-Removing a node from T by relabeling it to n: Decreases Φ(T ).Note that upon each operation of relabeling, the additional cost related to detecting the threshold value θ is O(1) since we can maintain, for each value between 0 and current θ, the number of nodes labeled with this height. Relabeling can only break the consecutive series if a node is the only node with this height value; hence this value will become the new θ and we remove from T all nodes with heights above it.Hence the total running time before finding the min-cut is bounded by O(η • n 2 ).To bound the time for finding the max-flow, notice that the total excess in G only decreases, so when we start to route excesses in S to s, the total excess is also bounded by η. The same potential function argument can be used to prove it also takes O(η • n 2 ) time to resolve all excess in S, though using the fact that in Push-Relabel, heights are always bounded by 2n (see Lemma 1).Proof of Corollary 1. Create an auxiliary graph G ′ by taking a copy of G and adding a super-source s * and an edge (s * , s) with capacity η. Create a pre-flow f init on G ′ by saturating (s * , s) and letting f e = 0 on all other edges in G ′ . Now run Algorithm 2 with inputs G ′ and f init . The initial (and maximum) excess in G ′ was η, and so the run-time is bounded by O(η • n 2 ), as in the proof of Theorem 2.Proof of Corollary 2 . We will build the reverse network of G, call it B (for backwards). The network B consists of a copy of G but all of the edges go the opposite direction. More specifically, for every node u ∈ V (G) there is a mirror node u ′ in B, and for every edge e = (u, v) ∈ E(G) with capacity c e , there is a mirror edge e ′ = (v ′ , u ′ ) ∈ E(B) with capacity c e . Note that the source s in G is mirrored to the sink s ′ in B, whereas the sink t in G is mirrored to the source t ′ in B.We can reverse any pseudo-flow f on G to be another pseudo-flow f ′ on B, where for all e ∈ E(G), f ′ e ′ = f e . Notably, f and f ′ saturate the same cut, and we observe excf (u) = def f ′ (u ′ ) and def f (u) = exc f ′ (u ′ ).Suppose we have a pseudo-flow f that saturates cut δ(S 0 , T 0 ) in G with no excess nodes in T 0 . Then in the backwards network B, f ′ saturates δ(T ′ 0 , S ′ 0 ), where T 0 (resp. S 0 ) is all mirror nodes p ′ for such p ∈ T 0 (resp. S 0 ). Now S ′ 0 becomes the sink-side of the cut. In B, we can send flow from excess nodes and s ′ to deficit nodes within S ′ 0 , and this can be done by running Algorithm 3 on B. The true algorithm in G is Algorithm 6, as it is just the mirror image of Algorithm 3, though we may skip the execution of Algorithm 4, as we already know the cut. This flow, when reversed back into G, is the maximum amount of flow that can go from excess nodes and s to deficit nodes in G f [S 0 ]. After adding this reversed flow to f , the result is a cut-saturating pseudo-flow for G, where there is no deficit on the s-side of the cut. Observe that there is no excess or deficit created on either side of the cut in the process.Given a pseudo-flow, the first phase is to pre-process f into a cut-saturating pseudo-flow on G and to compute η. See Algorithm 5.We create the auxiliary graph G ′ as in Algorithm 5, and then run the gap-relabeling Push-Relabel on G ′ (together with the standard initializing pre-flow) to find a minimum cut between s * and t and obtain a flow f ′ . Corollary 1 bounds the Push-Relabel run-time in this case. Adding f ′ to f creates a cut-saturating pseudo-flow. The next lemma proves the output of this algorithm satisfies the desired properties and that the algorithm runs in time O(η • n 2 ). Lemma 8. Suppose f is a predicted pseudo-flow with unknown error η for network G. Then Algorithm 5 computes η and finds a cut-saturating pseudo-flow f for G with error η in time O(η • n 2 ).Proof. In the residual graph G f , the min-cut is bounded by η, since it is at most η far from being cut-saturating. Therefore, we can apply Corollary 1 to G f and obtain an optimal flow f ′ on G f in O(η • n 2 ) running time. The flow we desire is f e = f ′ e + fe for all e ∈ E. It is cut-saturating for G by the optimality of f ′ on G f . Further, it is a pseudo-flow since f ′ does not have any excess or deficit in G f and clearly f ′ e + fe ≤ c e for all e ∈ E. We turn our attention to the error value computed by Algorithm 5. Let η * be the true unknown value.Note that in the auxiliary graph G ′ constructed in Algorithm 5, if the current value of η can be sent from s * to t, there exists a s -t flow of η in the residual graph; meaning when Push-Relabel terminates the s * -t cut we will find is just the edge η. This is a certificate that η * ≥ η. We double values of η until we find some value where the cut in G ′ is no longer (s * , s). This is a certificate that η * ≤ η. Given an upper bound and lower bound on η * , one can run binary search in this range and continue using the cut-based certificates to further limit the range in which η * lies, until it is found exactly.Notably, one can also run Algorithm 2 and terminate it upon finding the min-cut, in which case f ′ will be a pre-flow on G f , and the resulting f = f ′ + f will have total excess bounded by 2η. In fact, one can do this in other steps of the algorithm as well, if the goal is only to find a min-cut, and only lose an additional constant factor in the running time; see Appendix A.4. As discussed, in practice one may wish to use a predicted cut instead of finding a cut-saturating pseudo-flow as in Algorithm 5.By Definition 1, if a pseudo-flow f is σ far from cut-saturating it means augmenting it by another flow f with value at most σ can saturate some cut. Let this cut be δ(S, T ). Another way to look at this is, within f , the total flow passing through the cut δ(S, T ) satisfies:u∈S,v∈T f(u,v) - u∈S,v∈T f(v,u) ≥ u∈S,v∈T c (u,v) - u∈S,v∈T c (v,u) + σ.Apart from solving max-flow in the residual graph to saturate this cut, there may be other options to create a cut-saturating pseudo-flow. For example, the η bound on error does not directly tell us where this cut is. However, if a practitioner can "guess" a good enough cut δ(S, T ) from past problem instances, such a pseudo-flow can also be obtained simply by saturating all edges (u, v) ∈ δ(S, T ) and removing the flow on all backward edges. The downside is that such a practice will transfer the error on that particular cut to the total excess and deficit on nodes incident to the cut. Overall, there may be a trade-off where one can omit Algorithm 5 in lieu of using a predicted cut, but at the cost of having to fix more excess and deficit in later steps.We mentioned that one can choose to quit the Push-Relabel algorithm on auxiliary graphs whenever a cut is found. The resulting pseudo-flow, although violating flow conservation constraints, can still be added to the initial pseudo-flow. We give a brief analysis of how this effects the execution of the algorithm.The pseudo-flow is constructed in three places:1. In Algorithm 5, where we saturate a cut; 2. In Algorithm 3, where we push flow from t-side excess nodes to deficit nodes and t; 3. In Algorithm 6, where we push flow from s-side excess nodes and s to deficit nodes.Notice this simple fact: Claim 2. For pseudo-flows f, f ′ , and f ′′ where f = f ′ +f ′′ (without violating capacities constraints), we have:u (exc f (u) + def f (u)) ≤ u (exc f ′ (u) + def f ′ (u)) + u (exc f ′′ (u) + def f ′′ (u))In Step 1, Algorithm 2 starts with f init with excess η, hence the resulting pre-flow also has at most η excess, and adding this pre-flow without restoring it to a max-flow may increase the excess by η. In Step 2, the initial flow in G ′ also has total excess of at most u∈T0 exc f (u) ≤ η, so at the end of Algorithm 3 the total excess also increases by this much. In Step 3, correspondingly the maximum increase is u∈S0 def f (u) ≤ η. To sum up, early termination in the auxiliary networks after finding the min-cut increases the total error by O(η), and therefore has the same run-time bound up to a constant factor.Table 3 contains a detailed description of each of the four image groups, their original size in the raw dataset, the cropped grey-scaled image size, the foreground/background they feature, etc. In the main body, Figure 3 shows examples of cuts found in some images from the BIRDHOUSE image sequence. Figure 5 , 7, 6 show example cuts from the other image groups. We take as input an image on pixel set V , and two sets of seeds O, B ⊆ V . The seed set O contains pixels that are known to be part of the object, while the seed set B contains pixels that are known to be part of the background. The intensity or gray scale of pixel v is denoted by I v . We say that two pixels are neighbors if they are either in the same column and in adjacent rows or same row and adjacent columns. Intuitively, if neighboring pixels have very different intensities, we might expect one to be part of the object and one to be part of the background. For any two pixels p, q ∈ V , a solution that separates them, i.e., puts one pixel in the object and the other one in the background, incurs a penalty of β p,q . For neighbors p and q, β p,q = C exp(-(I p -I q ) 2 /(2σ 2 )), for C a large constant, otherwise the penalty is 0. Note that the quantity β p,q gets bigger when neighbors p and q have stronger contrast.A segmentation solution seeded with O and B labels each pixel as either being part of the object or part of the background, and the labeling must be consistent with the seed sets. Let J denote the object pixels for a fixed segmentation solution. Then the boundary-based objective function is the sum of all of the penalties max J p∈J,q / ∈J β p,q , for J with O ⊆ J, B ⊆ V \ J. As in the definition, a positive penalty cost is only incurred on the object's boundary. The goal is to minimize the total penalty, which is in turn maximizing the contrast between the object and background, for the given object and background seed sets.Solving this maximization problem is equivalent to solving the max-flow/min-cut problem on the following network. There is a node for each pixel, plus the object terminal s and the background terminal t. As notation suggests, s is the source of the network and t is the sink. The edge set on the nodes is as follows: (1) for every v ∈ O add edge (s, v) with capacity M , for M a huge enough value that it is never saturated in any optimal cut; (2) for every u ∈ B add edge (u, t), again with capacity M ; (3) for every pair of nodes p, q ∈ V , add edges (p, q) and (q, p) with capacity β p,q . If an image is on n × n pixels, note that the graph is sparse with |V | = O(n 2 ) nodes and |E| = O(n 2 ) edges.In our experiments, all β p,q 's are rounded down to the nearest integer, so that capacities are integral. Since β p,q ≤ C by definition, it suffices for us to let M = C|V | 2 .We have discussed how to cope with unknown η in Algorithm 5 by using a doubling search from an initial guess η = 1 in order to guarantee the O(η|V | 2 ) time bound. However, in practice, we have discovered that this is not absolutely necessary. One can use other surrogates for η as long as they prove an effective upper bound on the error. In our experiments, η is estimated by computing both the total excess/deficit induced by rounding down the flow, and the σ (in the "σ away from being cut saturating" notion) by using the old cut in the previous image in the sequence. Typically this is a loose bound, but it suffices for our purpose.In these experiments the real error η of the given predicted flow could be high. For example, on a sequence of 10 images of size 60 × 60 from the group DOG. The average total excess/deficit accounts for 69% of the real min cut, whereas the σ, computed a posteriori using the min cut, accounts for about 23%. The results should be read together with the measured error metric value in [DMVW23] under the same experiment designs. Our η is not negligible but still boosts Push-Relabel's performance with warm-starting, despite the dependency of the theoretical bound on η. This is typical -algorithms in practice often run much faster than their theoretical bounds. In [DMVW23] , the empirical prediction errors (see, e.g., Table 5 in their Appendix) are at similar levels, and can be even higher than the maxflow value. As is discussed in their paper, the savings in running time results from the augmenting paths routing excess to deficit being much shorter than the source-sink augmenting paths; hence the performance goes beyond the theoretical O(mη). Excesses/deficits are big in our setting, too, but the initialized pseudo-flow is already quite close to being cut-saturating. This might account for the speed-up we obtain.https://lmb.informatik.uni-freiburg.de/resources/datasets/sequences.en.htmlhttps://lmb.informatik.uni-freiburg.de/resources/datasets/StereoEgomotion.en.html 


Decision: Dear authors -- thank you for an interesting well-written paper that provides new theoretical insights into the surprisingly good performance of warm-starting for push-relabel algorithms for max-flow.  While the topic of the paper is specialized to a fairly narrow area -- the reviewers all enjoyed the paper, and the analysis makes a tangible contribution to the "observed" (beyond worst case) behavior of combinatorial algorithms .  We hope that you'll be able to incorporate reviewer's suggestions in the final version (e.g. incorporating more detailed description of computing eta).  I recommend the paper for acceptance.

Reviews: review: paper_summary: paper_summary: This paper propose and analyzes a warm starting scheme for the classical
push-relabel algorithm for max-flow problems. The basic approach is to convert
the warm-starting flow into a cut-saturating flow, at which point a clever
push-relabel scheme is used to ensure that the source-side of the cut has only
excess flow while the sink side of the cut has only flow deficits.  This
immediately yields a min-cut and is easily transformed into a max flow
solution.  The authors compare their approach with warm-starting methods for
the Ford-Folkerson algorithm, which they show is less efficient in practice.
strength_weakness: strength_weakness: - The error $\eta$ of a pseudo-flow $\hat f$ is hard to estimate without
    running Algorithm 5, meaning the total complexity of computation is not
    known until partway through execution. Moreover, this issue is not addressed
    in the paper.

- It is difficult to compare warm-started push-relabel with the Edmonds-Karp
    selection rule for Ford-Fulkerson because their complexities they depend on
    different aspects of the problem. 

### Detailed Comments

Firstly, I want to say that this paper is significantly outside of my research
area (convex optimization) and so I cannot comment on the novelty of the ideas.
However, I think the ideas in this paper are of significant interest,
particularly for researchers focused on deriving instance-dependent
complexities. As such, I think the paper should probably be accepted.


**Computing $\eta$**:
Reading Section A.3, it seems like computing the value of $\eta$ is a
unaddressed difficulty in the main paper. I don't think it is reasonable to
consider $\eta$ to be input to the algorithm, so the doubling procedure in A.3
is required to estimate $\eta$ when running Algorithm 5. Since the complexity
of estimating $\eta$ with Algorithm 5 is no greater than that of running
Algorithm 5 with $\eta$ as in input, I think it makes sense to write the full
algorithm without knowledge of $\eta$ in appendix. Similarly, some comment
should be made about this issue in the main paper. 


**Edmonds-Karp Selection Rule**: 
You comment that Ford-Fulkerson with the Edmonds-Karp selection rule has
complexity $O(m \|f^* - \hat f\|_1)$. In comparison, warm started push-relabel
has complexity $O(\eta n^2)$. It is difficult to compare these two complexities
since $m \leq n^2$ but $\eta \leq \|f^* - \hat f\|_1$. In practice,
warm-started push-relabel seems to have much better complexity, but is it
possible to draw a rigorous comparison between the two methods? At the very
least, I think this issue should be addressed in the main paper.
questions: questions: - Can $\eta$ ever exceed $O(m)$? That is, are the circumstances where 
    the warm-started version of push-relabel has worse asymptotics than
    cold-start push relabel?


- What about using randomized predicted pseudo-flows $\hat f$ to
    warm-start push-relabel? I ask because, in continuous optimization, random
    initializations often out-perform default initializations like $0$. It
    would be interesting to choose a distribution for $\hat f$ and then compute 
    the expect value of $\eta$ or perhaps high probability bounds on $\eta$.
limitations: limitations: Limitations are appropriately addressed in the paper.  The paper topic might be
considered somewhat niche to the majority of the NeurIPS audience. This is not
a weakness of the paper, however.
paper_summary: paper_summary: This paper provides the running-time complexity analysis for warm-start Push-Relabel algorithm for the fundamental max-flow/min-cut problem. In particular, they study learning-augmented version of the Push-Relabel algorithm, where the algorithm can start from a pseudo-flow with error bounded by $\eta$. The main result is that a minimum cut can be found in time $O(\eta\cdot n^2)$, which improves upon the $O(n^2 m)$ runtime of basic Ford Fulkerson.
strength_weakness: strength_weakness: - The algorithm (Algorithm 2) requires a bound on the error $\eta$ of the prediction, which can be hard to estimate in practice. 
- Even though the Push-Relabel performs much faster than Ford-Fulkerson procedures in image segmentation task (Sec. 4), when just comparing the theoretical bounds, $O(\eta n^2)$ (warm-starting Push-Relabel) and $O(\eta m)$ (warm-starting Ford-Fulkerson), the run-time benefits of warm-starting Push-Relabel cannot be seen compared to that of warm-starting Ford-Fulkerson. Is this due to a loose bound on the warm-starting Push-Relabel?
questions: questions: - Theoretically, the provided run-time order for the warm-starting Push-Relabel is not smaller than that of the warm-starting Ford-Fulkerson) especially for a sparse graph when $m\ll n^2$, even though one can run Push-Relabel much faster empirically. Can the authors comment on any reasons for this result? Can the bound for warm-starting Push-Relabel be made even tighter by considering sparsity of the graphs?
limitations: limitations: No ethical limitations
paper_summary: paper_summary: Authors provide the first theoretical guarantees for the Push-Relabel (PR) algorithm coupled with the gap relabeling heuristic, to address max flow problems, while using an arbitrary (pseudo-flow) initialization such as a predicted flow. The main result relates to proving a worse case complexity of $O(\eta * n^2)$ for their algorithm given a predicted pseudo-flow with error $\eta$ (cf Def 1) on the network with $n$ nodes. Finally, they validate empirically their theoretical analysis while showing the relevance of their algorithm compared to well-known competitive algorithms.
strength_weakness: strength_weakness: *edits after authors' rebuttal are in italic*

1. Potentially under-exploited empirical results:
   - a) *[addressed, see suggested improvements in discussions]*  visualizations corresponding to values reported to Table 2 / 5 could have been interesting to really observe the quadratic behaviour.
   - b) *[partly addressed in answer to all reviewers, paper to adjust accordingly]* Lack of analysis w.r.t the "parameter" eta, that relates to the error between the previously predicted flow and the new one. Potentially synthetic datasets could have been designed to control eta and compare theoretical results with empirical ones. It seems also possible on real-world dataset to compute a posteriori eta (e.g knowing all optimal flows over a sequence) along iterations to perform this comparison between theory and practice more accurately.
   - c) Even if authors explicitly state that their goal is not to claim SOTA results, it is interesting to have a benchmark to SOTA approaches for reference.

2. Limitations of theoretical results could be further discussed. In theory, FF algorithm has a better worse case complexity than the PR algorithm studied by authors, but the later is faster in practice. This either question the tightness of the bound given by authors, or that the average (not worse case) complexity is simply better for the later than the FF one, which is not theoretically studied by authors.
questions: questions: I encourage authors to discuss and address the weaknesses I have highlighted above. A few questions follow for the sake of clarity:
- *[done]* Could you explain how the cold-start is performed ?
- *[done, to integrate in the paper]* How many times were run experiments to eliminate the biases of the state of the machine? I believe only once, so reporting averaged runtimes over several runs would be better. For reference, authors should also report the type of machines which were used to perform the experiments.
limitations: limitations: The authors have made an effort to address the limitations of their work, I encourage them to answer the questions above to ensure that all potential limitations have been covered.

No potential negative societal impact.
paper_summary: paper_summary: This paper studies the push-relabel algorithm with warm-starts for the max-flow problem. Despite its empirical efficiency, the standard analysis of the algorithm is known to result in a somewhat pessimistic bound of $O(n^2m)$. The current paper considers a situation where the algorithm takes a predicted pseudo-flow $\hat f$ and has shown that the running time can be bounded by $O(n^2\eta)$, where $\eta$ is a prediction error that is at most $\\| \hat f - f^* \\|\_1$ for an optimal flow $f^*$. En route to this result, the authors have also shown that push-relabel with the gap-relabeling heuristic fed with a cut-saturating pre-flow (Algorithm 1) enjoys the same error-dependent bound. Overall, the algorithm converts $\hat f$ into a cut-saturating pseudo-flow $f$ in $O(n^2\eta)$ time (Algorithm 5), updates $f$ in $O(n^2\eta)$ time so that the $t$-side ($s$-side) has no excess (deficit) nodes (Algorithm 2), and fixes excess (deficit) in the $t$-side ($s$-side) with Algorithm 1. The main technical novelty lies in the update step, which swaps excess and deficit nodes between $t$- and $s$-sides. Finally, experiments on image-segmentation datasets confirm the effectiveness of push-relabel with warm-starts, compared with cold-start push-relabel and cold- and warm-start Ford--Fulkerson.
strength_weakness: strength_weakness: 1. I agree that analyzing push-relabel is important due to its practicality. On the theoretical side, however, the impact of the $O(n^2\eta)$ bound is somewhat weak since Ford-Fulkerson is already shown to run in $O(m \\| \hat f - f^* \\|\_1)$ time.
2. The paper has little implication about how we should learn $\hat f$. I understand that $\\| \hat f - f^* \\|\_1$ can be used as a surrogate loss that upper bounds $\eta$ in Definition 1. However, since it is mentioned in lines 86--87 that the $\ell_1$-error is not a good measure of the prediction quality, I would like to know whether we can develop a better method for learning $\hat f$ based on the error measure in Definition 1.
3. The paper is somewhat hard to follow as it involves many pseudo-codes, most of which are in the appendix. For me, the proof of Theorem 1, which includes a brief explanation of what each algorithm does, was helpful to overview the entire algorithm with predicted pseudo-flow. It might be better to present a similar technical overview when describing Figure 1.
questions: questions: 1. How can we know $\eta$ in Algorithm 2? Is it given as an output of Algorithm 5?
2. If my understanding is correct, in the experiments, $\hat f$ is set to the old max-flow in the previous image. Is this $\hat f$ attains small $\eta$? 
3. I'm also curious about how the actual running time scales with the error level $\eta$ and how it aligns with the theoretical bound of $O(n^2\eta)$.


#### **Minor comments**
- Please define what "saturate" means for clarity.
- Do lines 64--65 and Lemma 3 state the same thing? If so, I would prefer to merge them or add a reference from lines 64--65 to Lemma 3.
limitations: limitations: Yes.

Comments: title: Answer to authors
comment: Thank the authors for the detailed responses. I will keep my score.
Thank you for your detailed answers.

Indeed for the visualizations it would be better to draw complete ranges of values in log-scale, with variances illustrated for each method with a lower intensity. Main points addressed in the answer to all reviewers should be clearly integrated in the paper.

Overall I find authors' rebuttal compelling, therefore i increase my score from 6 to 7.
Thank you for the detailed response. I appreciate your answers to my questions. I have increased my score to 6.
Thanks for your response and for the new plots. 

I think my concerns have been addressed in so far as that is possible. The difficulty of estimating $\eta$ before executing the algorithm is somewhat abated by the practical procedure described in the general response. The comparison to warm-started Ford-Fulkerson appears to be fundamental problem, at least until further technical tools are developed for analysis beyond the worst case. 

I will keep my score at 7 for now, but I do like this paper and feel it should be accepted.