Warm-starting Push-Relabel
Authors: Sami Davies
Sergei Vassilvitskii
Yuyan Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: algorithms with predictions
max flow
beyond worst-case analysis
Primary area: optimization
TL;DR: We provide the first theoretical guarantees for seeding the Push-Relabel algorithm with a predicted flow, and we validate this theory by showing speed ups empirically.

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.

Warm-starting Push-Relabel
Sami Davies', Sergei Vassilvitskii", Yuyan Wang' "UC Berkeley, *Google Research New York davies@berkelly edu, {sergeiv, kangyy)@google.com
Abstract
Push-Relabel is one of the most celebrated network flow algorithms. Maintaining a pre-flow that saturates a cut, enjoys better theoretical and empirical running time than other flow algorithms, such Ford-Fulkerson In practice, PelaeRelabel 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. How- ever, remains unclear how to run Push-Relabel on an arbitrary initialization that is not necessarily fre-flow or cut-saturating. We provide the first theoreti- cal guarantees for warm-starting Push-Relabel with predicted flow, where our augmeeted version benefits from fast rumning 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 theoreti- cal justification for why it can lead to run on-time improvements. We then provide experiments that show our warm-started Fush-Relabe also works well in practice.
Introduction
Maximum flow is fundamental problem in combinatorial optimization. It admits many algorithms, from the famous Ford-Fulles Fulkerson algorithm [FF56] which employs augmenting paths, to recent near-linear time scaling based approaches [CKL+ In practice, however, the Push-Relaber family of algorithms remains one of the most versatile and often the standard benchmark to which new flow algorithms compared [Wil19, CH09].
Designed by Goldberg and Tarjan [GT88], the core Push-Relabel algorithm (Algorithm 1) has running time O(n²m). where and m are the number of vertices and edges in the network. Given the popularity of max-flow as a subroutine large-scale applications [BK04, KBR07, Wil19], is no surprise that improving running times has been subject of lot of study, with multiple heuristic methods being developed 93, CG95, AKM097, Go108).
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 rumning time of the Edmonds-Karp selection rule for Ford Fulkerson can be improved from O(m²n) to Om flli), where f* is optimal flow the network and is 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 fi-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 [DMVW23] on bringing rigorous analysis for warm-starting augmennnnn path style algorithms. In the process of doing so, we provide theoretical explanation for the success of the popular gap relabeling heuristic in improving
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the running time of Push-Relabel algorithms. Specifically, both the gap relabeling heuristic and our algorithm maintain cut with monotonically decreasing 1-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 practice with experiments on the image segmentation problem.
1.1 Preliminaries
Graph, flow and cut concepts. Our input is a network G (V, E), where each directed edge e E E is equipped with an integral capacity E Z20. Let V = and [E] = m. G contains nodes the source, and t, the sink. G is connected: Vu E V. there are both s and u t paths in G. A flow S E T0 is feasible if it satisfies: flow conservation, meaning any E V \ (8, 1) satisfy EnmaER fe- = ((.w)er F fei (2) capacity constraints, meaning for all E E, fe S ce. Our goal is to find the maximum flow, i.e. one with the largest amount of flow leaving 8.
We call f pseudo-flow if it satisfies capacity constraints only. A node E V ts is said to have excess if it has more incoming flow than outgoing, i..., ((,,)eE fc > E (u,w)e fe; analogously it has deficit if its outgoing flow is more than ingoing. We denote the excess and deficit of node u with respect to f as excy(u) = max (((,))) fc Ein,weE fe, 0} and d = max (u,,,) Je- - E(D,)E See 0}, where at most one can be positive. A pseudo-flon flow can have both excesses and deficits, whereas a pre-flow is a pseudo-flow with excess only.
For pseudo-flow S. the residual graph G is network on V: for every (u,u) E E, Gf has edge e with capacity de = Ce - Se and backwards edge (v. with capacity Sa. Let F(G denote the edges in Gy- The value of pseudo-flow J is val(/)
Ee=(s,)) Ser the total flow going out of 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 - & cut in the network. Push-Relabe maintains a cut-saturating pre-flow, equivalently, there is no path in the residual graph of the pre-flow. We use 8(5, 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 E V Bu - / path in G5} } (including () and S V /T.
t
The prediction that we will use to seed Push-Relabel is some f E 2m 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. 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 good predicted flow despite its infeasibility.
Prediction.
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- seeded with f should take. A pseudo-flow becomes a maximum flow when it is both feasible and cut- sut-satura Hence, the error measures how far is from being cut- saturating while being feasible. We say that pseudo-flor flow f is far from being cut-saturating if there exists a feasible flow I' Gj where val()") S and f + f' is cut-saturating G (though the cut does not have to be 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 n such that (1) f 1) far from being cut- saturata and (2) Enev exc;(u) + def S nz.
n = 0, f is the max- -lxww and the cut that is saturated is the min-cut. The previously studied error metric for predicted flows, such as by [DMVW23] and [P722], was || - fll1. : for any max-flow f*
PAC-Icarnability is the standard to justify that the choice of prediction and error metric are reasonable. Flows are PAC-learnable with respect to the -norm [DMVW23]. Our results hold replacing our error metric with the f-oormm because our metric provides more fine-graines guarantee than the -n-nrmm (i.e., if a prediction í has error 7) then 7) S I1 - îlli). Thus we can omit any theoretical discussion of learnability. We present this work with respect to our error metric as we find the E error metric to be unintuitive, it is not really very descriptive of how good predicted flow is.
2

---

Push-Relabel. The "vanilla" Push-Relabe Relabel algorithm maintains pre-flow and set of valid heights (also called labels) on nodes. Heights h: : + Zzo are valid for for every edge (u,
E with positive capacity, h(u) < h(() + 1, and if h(s) = n. and h(t) = O. An edge (u, v) E F(G,) is called admissible if hi(u) = h(w) + and ((..)) > 0, which means we can push flow from u to v. The
algorithm starts with flnit, where fanlt c. for all (s. u) and otherwise fe 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.
Algorithm Push-Relabel
Input: Network
Define fe = ce for = (s, u) and fe = 0 for all other
Define h(w)) = for all E V {8} and h(+)) = n
Build residual network G
while node u with exc, > 0 do
if 3 admissible (u, v) E with f(u,o) < C(u.s) then
Update o by sending an additional flow value of min(excy(u), (w.)) along (u, v)
Update G accordingly
else update h(u) = 1 mmm. h(v)
Output:
All heights in Fush-Relabe are bounded.
Lemma For a pre-flow f on network G, every node u with exc; (u) 0 has path in Gf to 8. Further, for d(u, v) the length of the shortest path from u to in Gf, any valid heights in Push-Relabel (Algorithm 1) satisfy h(u) S h(v) + d(u, For all u V, h(u) S h(s) + 2n.
At any point of the algorithm, the s - cut maintained can be found using the heights. Lemma 2. For pseudo-flow f with valid heights h network G, let 0 be the smallest positive integer such that O & {h(u))we Then sets = {u E V h(u) > 0} and = {u V h(u) < 0} form a cut saturated by f.
We call this cut induced by the heights. Indeed, such a threshold 0 can be found because {h(u) JUEY has at most different values, but h(s) n and h(t) = 0, so among the n - 1 values {0, I...., n). least one not in the set. Note that 8(S, T) is 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 Gy (including t) and S = V If E S, then 5(S,T) T) is a saturated
- cut.
Lemmas 2 and apply to all pseudo-flows, whereas vanilla ReshbRelabel must take a pre- flow as input. Before this work, it was unclear how to seed Push-Relabel with anything other than finit.
With the gap relabeling heuristic, whenever there is some integer ( < 0 < n with no nodes at height 0, then nodes with height between 0 and n have their height increased to n. See Algorithm 2.
1.2 Technical contribution
We first study Push-Relabel with the gap relabeling heuristic when seeded with a prediction that is a cut-saturating pre-flow with error 7). We prove Algorithm 2 finds optimal solution in time O(n-n?). The running time also holds for cold-start versions of the algorithm when the max-flow/min-cuu value known to be bounded by 7). This is (I) 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 Fuld-Full admits naive running time bound of O(n m) when the max-flow value is at most 1), an analogous claim was not previously known for
The algorithm maintains 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 I, or updating the cut 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.
3

---

def
esc
analyses on Phose 2(s): Resolve excess on b-ide,, move oul.
Phase Reselve deficti s-aido, Min-out found end
Phase 3: Maintain cut, fh excessidefict within s and b. side.
End. excessideficil
max-flow now found.
Figure I: An illustration of warm-start Push-Relabel, seeded with a cut-saturating pseudo-flows The red eurve denotes the cut. The black arrows denote the existing flows, whereas the red arrows denote the flows sent in each phase to resolve excess/deficits.
Theorem 1. Given a predicted pseudo-flow f with error n on network G. there exists warm-start version of
that obtains the minimum cut in time O n²).
Our warm-start version of Push-Relabe that seeded with a general pseudo-flow has several phases. In the first phase, we show that one can modify the prediction to be cut-saturating pseudo-flow. We begin the second phase by routing flow within the two sides the cut induced by the pseudo-flow to resolve some of the excess and deficit. The maintained cut gradually changes 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 the s-side of the and all deficit nodes end up the t-side of the cut. This "swapping" procedure between excess and deficits nodes between the s- and t- sides of the cut biggest technical innovation. Either the excesses are resolved within the t-side of the cut, find a new cut between the i-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 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.
whose t-side is
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 (-side of the cut. This cut is actually 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 max- max-flow. See Figure for an illustration of phases and 3.
In Section we run our warm-start warm-start improves over the cold-start by larger percentage the size of the image increases.
compared to a cold-start version. We see that the
Our work identifies that there is 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 small (Corollary 1). While such 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 improving more general classes of networks.
The running time of warm-start Push-Relabel is O(n²n), while the rumning time of warm-start Edmonds-Kan is (mn) [DMVW23]. We do not believe that the bound for warm-start Push- Relabel being faster than that of warm-start Edmonds-Kaa is a weakness in our analysis, but is instead an artifact of the community's '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 is so much
be a way to parameterize instances or use practical heuristics to justify why better in practice than its theoretical worst-case bound would suggest [CG95, Hoc08, CM99].
2 Gap Relabeling Push-Relabel: Cold- and Warm-Start
We briefly overview the performance of Push-Relabel with the gap relabeling heuristic (Algorithm 2) when given cut-saturating pre-flow f. and tie the running time the error of f. Proofs this section are deferred to Appendix A.2, as their more involved analogs are in Section 3.

---

Algorithm 2 Warm-start Push-Relabel with Gap Relabeling
Input: Network G, cut-saturating pre-flow f Construct residual network G with capacity Run Algorithm 4 (see Appendix A.1) on G and f. obtain valid heights h and initial cut (S, T)
Initialize 0 - min E 200 Du E T with = = h(w)}
while 3u T with exc, (1) > 0 do
if By E ' such that (u, v) is admissible in Gy then
Update f by sending an additional flow value of min(exc,(u)) du.)) along (u, v)
Update Gj accordingly
else
Raise the height of to be h(u)) ming: h(v) +1
Update 0 min E Z= Au T with h(u))
for p E ' with h(p) > do
Remove p from T, add p to
Update p's height to h(p) =n
Take Gy as input and run Algorithm 1 on it fix excesses, outputs flow l Return flow + f" and the cut 8(S,7) 7) it maintains
Algorithm 2 begins by rumning Algorithm 4 as 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 l and names this set T. The other nodes belong S. By Lemma 3 the cut 8(S, T') is saturated by f. In the main WHILE loop, the algorithm maintains the cut 0S, T') such that all heights in T compose series of consecutive numbers starting from O. The cut only changes when a node is relabeled in a way that results in 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 I with height bigger than 0; 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-ftow saturating cut 8(S, T) on network G. If there are no excess nodes in T, then all excess in S can be sent buck to without crossing the cut, implying ö(S, T)) is min-cut.
We show that the running time is tied to 7, which, in this case, is the total excess in f. Theorem 2. Given a cul-saturating pre-flow with error nl network G, Algorithm 2 finds max-flow//mnn-cul in running time O(n n²).
Although Algorithm 2 presented as being seeded with an existing pre-flow, the same bound applies to the cold-start gap relabeling Push-Relate when the min-cut of G is at most 1). One only has to seed it with finit in Algorithm 1, which saturates the cut 8({s). V \ {s}). This will be useful in Section 3, as repeatedly use Algorithm 2 as subroutine on networks with small min-cut.
Corollary 1. If network G is known to have mlx-iloowmin-cut value of at most 7,, one can use Algorithm 2 to obtain a max-flow and min-cut for G in running time O(1 n²)).
3 Warm-starting Push-Relabel with General Pseudo-flows
We extend the results in Section 2 to when the given prediction is a general pseudo-flow f as opposed to cut-saturating pre-flow, i.e., f may not be cut-saturating and may have deficit nodes. The first phase of our algorithm computes 77 and augments by finding an 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 cut-saturating pseudo-flow f and 17, we are ready to define the accompanying heights and cut using Algorithm 4. Note that the initial cut with two sides To {u V 3u t path in G } and S. V To 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 a generalization of what happens in Algorithm 2, where transfer all excess nodes to the s-side of the cut. Here, we transfer
5

---

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 h
Let To = {u E V 3u t path in Gy} and So = V \ To Build the residual G
Build G" on copy of G [To] plus {s",
for excess node u To {t} do
Add edge (s", u) with capacity (w)
for deficit node E To do
Add edge (u, with capacity def
Add edge (t) with capacity 7 1
Let ((*"..) C(),,u) for all (s", u). and all other fanit 0 Run Algorithm 2 on G" and pinit, outputs I' and Ty T
for all copies of (u. E F(Gy) where ft > 0 do
Update fe + fe f'
Output: Flow f and cut parts So T.Yy and TV
all excess 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 out-saturating pseudo-flor f for network G, let ö(S, T) be cut it saturates. If all nodes in T have no excess and all nodes in S have no deficit, then the cut is minimum cut.
To prove Lemma 5, we use the following result from [DMVW23]:
Lemma 6 (Lemma 5 [DMVW23)) Given any pseudo-flow I for G, every excess node has a path in Gj to either a deficit node or s; every deficit node has path in G from either an excess node or t.
Proof of Lemma 5. In Gy. by Lemma 6, every excess node u in must have a path to either a deficit node or s. Since f currently saturates 8(S I',, 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 E T there is a path that starts with either an excess node or and ends with Again, since the T(,,T) is already saturated, the path must be within T, hence can only be from to v. It follows that we can send all excess
and send flow from to all deficit nodes until the pseudo-flow becomes a feasible flow. Notice that 0(5, T') remains saturated in this process, hence the resulting flow is max-flow and 8(S, T) is min-cut.
By Lemma 5, it sufficient to find a pseudo-flow floww and accompanying saturated cut where the excess nodes are all on the s-side and the deficit nodes are all on the (-side. We focus on the (-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 the t-side, solve 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 To). If the max-flow in this problem matches the total excess in To all excess can be resolved locally and only deficits remain; otherwise, the max-flow solution on the auxiliary graph also provides us with min-cut that "blocks" excess nodes from deficit nodes and I. 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 [T]]) and add super-source and -sink s* and t* to it. Add edges (s", u) with capacity exc, (u) for every excess node u E To; add edges (v, t*) with capacity (1) for every deficit node To: and add an edge (t,t") with capacity + 1.
When we run cold-start 5(TH, T Note that E TH since (t,t") ) has capacity + 1 and cannot be in the min cut which is bounded by y by definition. Any 8" path p in G' along which f sends 8 units of flow exactly identifies nodes u and v (where (s",u) E p and (v, (*) p) for which 8 units of flow can be sent from v to e along the interior p in Gy. We can send flow as indicated by I' to update f (Algorithm 3). We obtain the following guarantee.
(Algorithm 2) on G', it outputs a flow f' and the -t" cut

---

Claim 1. In Algorithm 3, the output pseudo-flow f saturates the cut (S U UT: T,), and all excess nodes are in So U To Moreover, the total excess and deficit in G has not increased.
Proof of Claim 1. Let foa denote the input to Algorithm 3. The fact that the output f saturates the cut 8SS J Ty: T immediately follows from the fact that I' saturated the cut 8(T): T5)) in G'. Indeed, all edges from To to To are now saturated and all edges from To to Tú have no flow. All edges from Sg to To' are already saturated in the old flow fold and remain so after adding f since its flows are locally within To. For the same reason, all edges from TV back to So still have 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 fold. and the excess/deficit of node is clearly never increased. Assume for sake of contradiction there is an excess node u E To Then u had excess with respect to fold too, so there is an edge (s", u) that had capacity exC (u) in G' but was not saturated by f". Further, since a min-cut in G' is 5(T), T5'), it must be that u can reach / in G'. This means that in G' there is path with positíve remaining capacity between 8 and t", contradicting the fact that I' was a max-flow G'.
By Claim 1, the updated f satisfies the conditions of Lemma 7 by taking S* = Sy UT and T = Ty The running time in Lemma 7 follows by applying Corollary on G'. Thus we have the following.
Lemma 7. Let J be a pseudo-flow for network G with error 1) saturating cut 8(So, To). Algorithm 3 finds new cut-salurating pseudo-flow in time (n- n²) ) that (i) saturates an additional I cul 5(5", ),), (ii) has no excess nodes in T and (iii) has total excess and deficit still bounded by 1j.
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 on the reversed network; see Appendix A.2 and Algorithm 6.
Corollary 2. Let f be pseudo-flow for network G with error that saturates cut 8(So, To). One can update time O( n²)) so that all flow Ty remains unchanged, but now f saturates a cut 5(S*, "T") and there are no deficit nodes in S
Coping with unknown 17 Algorithm 3 assumes 1) is given. When 1) is not know, we can run Algorithm 3 iteratively with a guess for 7 and double the guess each iteration. We initialize by guessing that 17 = 1. Run Algorithm 3 on an auxiliary graph, which is just the residual graph plus new source node s" with single edge (s", s) of capacity 17 that is saturated upon initialization. If with
Algorithm 3 returns the cut (s" s), we have augmented the pseudo-flow but have not found an 8 - 1 cut yet. Double 1/. change both the capacity and flow on (s", s) to be the new 17. and run Algorithm 3 again. Repeat this until have found an s t cut. The initial is between [1 12 r7] away from being cut-saturating, and the whole procedure has O n??) running time. See Algorithm 5 for more details.
t flow of n,
Summarizing this section, we prove our main theorem.
Proof of Theorem I. Given a predicted pseudo-flow ff with error 7) on network G. Lemma 8 proved that Algorithm 5 finds cut-saturating -fowdo-llow f for G with error 17 in time O(n n²)). To find min-cut, Lemma shows that it is enough to find a pseudo-flow saturating a cut so that the I-side of the cut contains no excess and the s-side of the cut contains deficit.
By Lemma 7, we can run Algorithm 3 seeded with f on G to obtain an updated cut cut-saturating pscudo-flow with no excess on the t-side of the maintained cut in time O(1 n²)). Then, Algorithm 3 can be run on the backwards network B, and from Corollary 2, the updated cut-saturating pseudo-flow now has 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 8(5, By the
proof of Lemma 5, to obtain max-flow flow we only need to send all excess flow back to 8, and send flow from to every deficit node, Label all nodes in S with height ri and all nodes in 7' with height O. Then run Algorithm 2 to fix all excess in S. The algorithm will only send flow back to 8, since there no way to cross the cut 5(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. L
7

---

(a) Birdhouse
(b) Head
(c) Shoe
(d) Dog
Figure 2: The cropped and gray-scaled images from Figure 4 (copy from Figure 2 in (DMVW23J).
4 Empirical Results
In this section, we validate the theoretical results in Sections 3. To demonstrate the effectiveness of our methods, we consider image segmentation, core problem computer vision that aims separating an object from the background in given image. It is common practice to re-formulate image segmentation as max-flow/min-cul optimization problem (see for example [BJ01, BK04, BFL.06),, 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 maxxfllo/mmincctt As in previous work, we do not seek state- of-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-Relabo 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-Re Relabel much faster than Ford-Fulkernn 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 7j better than the theoretical ((n²n) bound. This is not totally surprising, 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 's resolution), the size of the constructed graph increases and the savings in time becomes more significant.
Implementation choices (such 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.
Datasets and data prepossessing Our image groups from the Pattern Recognition and Image Processing dataset from the University of Freiburg, and are titled BIRDHOUSE, HEAD, SHOE, and DOG. The first three groups are jjgg images from the Image Sequences' dataset. The last group, DOG, was a video that we converted to a sequence of jpg images from the Stereo Ego-Motion dataset.
g
Each of the image groups consists of 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 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 x 600 or 500 x 500 pixel images, still containing the object, and gray-scale all images. We rescale the cropped, gray-scaled images to be N x N pixels to produce different sized datasets. Experiments are performed for N E (30, 60, 120, 240, 4803. In the constructed graph, we have [V] = N + 2. Every graph is sparse, with |E' O(VV),, hence both [V| and [E| grow O Detailed description of raw data and example original images can be found in Appendix (Table 3, Figure 4).
https://tmbinformmai.. informatik. uni mni-freiburgg www..uuifehiiinddd/seoeeeeeeeeee http://www....ooooeaaacceeeeeene http::/mmb http://mmm..ffomtitt..k informatik uni hht.w//wwww.oooooeeeeeeeeeeeeenn

---

Figure 3: Cuts (red) on images chronologically evolving from the 240 x 240 pixel images from BIRDHOUSE.
Graph construction As in [DMVW23], we formulate image segmentation as a max-flow/min-cut problem. The construction of the network flow problem applied in both our work and theirs is derived from oongesstbllished line of work graph-based image segmentation; see [BFL06]. The construction takes pixels in images to be nodes; and a penalty function value which evaluates the contrast between the pigment of any neighboring pixels to be edge capacity. We leave details on translating the images to graphs on which we solve max-flow/min-cut to Appendix B.
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, shown in Algorithm 2, and the global relabeling heuristic, which occasionally updates the heights to node's distance from in the residual graph. These heuristics are known to improve the performance of Push-Relabel. As tie-breaker for choosing the next active node push from, choose the one with highest height, which is known to improve the running time of Push-Relabel. We found the generic Push-Ret Relabel algorithm without these heuristics to be slower than Ford-Fulkerson
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 2th image in the sequence, from the i - 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 Fush-Relabe algorithm in Section 3.
reuse the optimal flow and cut
To find a saturating cut, instead of sending flow from s to f as suggested in Algorithm 5, we reuse the min-cut on the previous image SSo, To) and send flow from Sn to To that originates from either s or an excess node, and ends at either / or deficit node. We experimented with 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 Algorithm 5.
The graph-base
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-stare sarm-starting Tush-Relabel with could be beneficial. See Appendix for other examples.
In our experiments, 1/ 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- Fulkerron in [DMVW23] and Push- Relabel. The "N/A" marks overly long run-time (>I I hour), which point we stop evaluating the exact run-time.
These results show warm-starting Push-Re Relabel, while slightly losing in efficiency on small images, greatly improves in on large ones. for the scaling of run-time with growing data sizes, both cold- and warm- start's 's running time increases polynomially with the image width n, but warm-start scales better, and as n increases to 480, gains significant advantage over cold-start. Despite the different warm-start theoretical bounds (1)) for Push-Relabel versus O(nl El) for Ford-Fulkerson), in practice both warm-start algorithms scale similarly as the dataset size grows. Additionally, one can see
greatly outperforms the same image size, allowing us to collect run-time

---

Table Average run-times (s) of cold-/warm-start Ford Fulkerson (FF) and Fush-Relabel (PR)
Image Group
FF cold-start
FF warm-start
PR cold-start
PR warm-start
BIRDHOUSE 30 x 30
0.80
0.51
01.05
0.06
HEAD 30 30
0.62
0.43
0.05
0.05
SHOE 30 x 30
0.65
0.39
0.07
0.06
DOG 30 30
0.69
0.32
0.10
0.11
BIRDHOUSE 60 x 60
8.22
3.25
0.30
0..4
HEAD 60 60
9.36
4.10
0.50
0.50
SHOE 60 x 60
8.09
3.04
0.69
0.47
DOG 60 60
21.91
6.73
0.76
0.95
BIRDHOUSE 120 x 120
109.06
37.31
5.42
4.98
HEAD 120 120
101.79
28.43
5.90
5.92
SHOE 120 x 120
98.95
30.44
6.44
3.74
DOG 120 120
190.36
38.08
6.76
6.38
BIRDHOUSE 240 x 240
NA
400.19
60.67
55.68
HEAD 240 240
NA
374.79
32,46
31.00
SHOE 240 x 240
NA
338.05
69.29
35.57
DOG 240 240
NA
459.48
73.76
52.42
BIRDHOUSE 480 x 480
NA
NA
604.54
502.58
HEAD 480 480
NA
NA
365.25
285.75
SHOE 480 x 480
NA
NA
756.77
364.42
DOG 480 480
NA
NA
834.63
363.41
statisties images of sizes up to 480 480 pixels, which 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 Section 3: (1) finding cut-saturating pseudo-flow; (2) fixing excess on f-side; (3) fixing deficits 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 the cut.
Table 2: Running time of warm-start Push-Relabel break down, on BIRDHOUSE
Size
30 30
60 60
120
120
240 x 240
480 x 480
Total
0.06
0.45
4.98
55.68
502.58
Saturating cut
0.04
0.34
4.17
46.25
431.49
Fixing t excesses
0.01
0.09
0.53
5.29
64.01
Fixing s deficits
0.01
0.02
0.27
4.13
7.08
5 Conclusions
We provide the first theoretical guarantees on warm-starting Push-Relabel with predicted flow. improving the run-time from O(m n²) to O n²). 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 future work is extending the approaches this work to generalizations of s-t flow problems, for instance, tackling minimum cost flow multi-commodity flow. different line of work is to develop rigorous guarantees for other empirically proven heuristics by analyzing them through lens of predictions, providing new theoretical insights and developing new algorithms for fundamental problems.
10

---

References
[AKMO97] Ravindra K Ahuja, Murali Kodialam, Ajay K Mishra, and James B Orlin. Computational investigations of maximum flow algorithms. European Journal of Operational Research, 97(3):509 542, 1997.
[BFL06] Yuri Boykov and Gareth Funka-Lea. Graph cuts and efficient nd image segmentation. International journal of computer vision, 70(2):109-131, 2006.
[BJ01] Yuri Y Boykov and M.P. Jolly. Interactive graph cuts for optimal boundary & region segmentation of objects in nd images. In Proceedings eighth IEEE international conference on computer vision. ICCV 2001, volume 1, pages 105-112, IEEE, 2001.
[BK04] Yuri Boykov and Vladimir Kolmogorov. An experimental comparison min-cut/mmax flow algorithms for energy minimization in vision. IEEE transactions on pattern analysis and machine intelligence, 26(9):1 124-1137, 137, 2004.
[CG95] Boris V Cherkassky and Andrew V Goldberg. On implementing push-relabel method for the maximum flow problem. In International conference on integer programming and combinatorial optimization, pages 157-171. Springer, 1995.
[CH09] Bala G Chandran and Dorit S Hochbaum. A computational study of the pseudoflow and push-relabel algorithms for the maximum flow problem. Operations research, 57(2):358-376, 2009.
[CKL+22] Li Chen, Rasmus Kyng, Yang P Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 612-623. IEEE, 2022.
[CM99] Joseph Cheriyan and Kurt Mehlhorn. An analysis of the highest-level selection rule in the preflow-puse max-flow algorithm. Information Processing Letters, 69(5):239-24) 242, 1999.
[DMVW23] Sami Davies, Benjamin Moseley, Sergei Vassilvitskii, and Yuyan Wang. Predictive flows for faster ford-fulkerson. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 Proceedings of Machine Learning Research, pages 7231-7248. PMLR, 23-29 Jul 2023.
[FF56] Lester Randolph Ford and Delbert R Fulkerson. Maximal flow through network. Canadian journal of Mathematics, 8:399 404, 1956.
[Gol08] Andrew V Goldberg. The partial augment-relabed algorithm for the maximum flow problem. In European Symposium on Algorithms, pages 466-477. Springer, 2008
[GT88] Andrew Goldberg and Robert E Tarjan. A new approach to the maximum- problem. Journal of the ACM (JACM), 35(4):921-900 1988.
[Hoc08] Dorit S Hochbaum. The pseudoflow algorithm: new algorithm for the maximum- problem. Operations research, 56(4):992-1009, 2008.
[JM+93] David S Johnson, Catherine C McGeoch, al. Network flows and matching: first DIMACS implementation challenge, volume 12. American Mathematical Soc., 1993.
[KBR07] Vladimir Kolmogorov, Yuri Boykov, and Carsten Rother. Applications of parametric maxflow in computer vision. In 2007 IEEE / 1th International Conference Computer Vision, pages 1-8. IEEE, 2007.
[MV22] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Commu- nications of the ACM, 65(7)333-35, 2022.
[P722] Adam Polak and Maksym Zub. Learning- aagmente maximum flow, arXiv preprint wxXiv:220.112911 2022.

---

[Rou21] Tim Roughgarden. Beyond the worst-case analysis of algorithms. Cambridge University Press, 2021.
[Wil19] David Williamson. Network flow algorithms. Cambridge University Press, 2019.
12

---

A More Discussion on Warm-starting Push-Relabel
We include some more insights and details on warm-starting Push-Relabel, including omitted proofs and algorithms from the main body.
A.1 Omitted algorithms
Algorithm 4 is used throughout the paper obtain valid heights cut-saturating pseudo-flow. It is essentially just a BFS procedure from the sink, where nodes that can reach the sink have height equal their shortest distance to the sink in the residual graph, and nodes that cannot reach the sink have height n.
Algorithm 4 Define Heights
Input: Network G, a cut-saturating pseudo-flow f
Define h(s) = n, h+(() =
Run BFS G
Let T {u E V 3u t path in Gy}
Let S = V V
for all u E S do
Let h(u) =
for all u EET do
Let huu)) be the shortest path length from u to in G
Output: Valid heights h, and cut parts S and T
The following is straightforward pre-processing algorithm. Given a pseudo-flow f. it finds cul-saturating pseudo-flow and computes the value of the error ry.
Algorithm 5 Find Cut-saturating Pseudo-flow and Compute ry"
Input: Network G, a pseudo-flow
Initialize 1)
Build G': a copy of G plus a super-source 8 and edge (s*,
Initialize C 8(s" V)
while C = 5(8" V) do
Update the capacity of (s",s) s) in G' to be and let f(rr =
Run Algorithm with inputs G' and ginit f. call output flow f' and output cut 8(S, T)
Update C 8(S,
the current cut C = 0(s", V)) then Update 77 2n..
Let 17 = f(s"..)) delete and (s" from G. Output: f and
The mirror version of Algorithm 3 below.
A.2 Omitted proofs
Proof of Lemma 3. Fix u E S, u T. Since can reach t and u cannot, any edge (u, v) from S to T in G must saturated by f, and any edge (v, u) from T' to in G must have no flow. This is because if either of these were not true, the edge (u, v) in Gy would have positive capacity, allowing to reach f. Hence 8(S,7 T) is saturated by
Proof of Lemma 4. It is known from the proof of the vanilla nodes in fre-flow must have a path back to 8; see Lemma When f saturates 8(S, T), such path cannot go from S to T, 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 cut, meaning the flow is max-flow and the cut is min-cut.
algorithm that all excess
13

---

Algorithm 6 Moving all deficit to the L-side of the cut
Input:
Network G. a pseudo-flow f with error that saturates the cut Ö(o,, To) Build the residual G2
Build G' on copy of [S plus {s","*)
for excess node u E So do
Add edge (s", u) with capacity (x)
for deficit node v E So \ {o} do
Add edge (u,t") with capacity defr(u)
Add edge (s", with capacity v + (or other number sufficiently large) Let [(=",.) C(st,u) for all (s", u) and flait C(s",)) and all other fan Run Algorithm 2 on G' and finit, outputs f' and S St
for all copies of = (u, v) E E(Gy) where f. > 0 do
Update fo + fo fh
Output: Flow ʃ and cut parts S and S U To
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 potential function argument that is different from that in the standard Rush-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 found. We define the potential function ((()) = Σner exc;(u) l(().. The operations involved change the value of & (T') the following way.
Saturated/ Aaturated/Unsaturee Unsaturated push: In either case, at least one unit of excess flow is pushed from a higher height to lower height, since for edge (u, v) to be admissible, h(u) h(v) 1. Therefore, (TT) decreases by at least 1.
Relabeling node to open up new admissible edges: Any such relabeling operation increases & (T). However, the total all of these increases is at most v) n². The 7j term upper bounds the possible excess at any node, whereas the n² 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 permanently.
Removing node from T' by relabeling it to n: Decreases 4 (T').
Note that upon each operation of relabeling, the additional cost related to detecting the threshold value 0 is (1)) since we can maintain, for each value between 0 and current 6, the number of nodes labeled with this height. Relabeling only break the consecutive series if node is the only node with this height value; hence this value will become the new 0 and we remove from all nodes with heights above it.
Hence the total running time before finding the min-cut is bounded by O(n n²²).
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 s, the total excess also bounded by 1). The same potential function argument can be used to prove it also takes O(n- n²) time to resolve all excess in S, though using the fact that in Fush-Relabel, heights are always bounded by 2n (see Lemma 1).
Proof of Corvllary Create an auxiliary graph G' by taking a copy of G and adding a super-source s* and an edge (s" with capacity y,. Create a pre-flow finit on G' by saturating (s*, s) and letting fa = 0 on all other edges in G'. Now run Algorithm 2 with inputs G' and finit The initial (and maximum) excess in G' was 1), and so the run-time bounded by O(1 n²),, 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 but all of the edges go the opposite direction. More specifically, for every node E VGG there is mirror node u' in B, and for every edge (u, v) E E(G) with capacity
14

---

ce, there is mirror edge e' = (e', w') E E(B) with capacity ce. Note that the source in G' is mirrored to the sink s' in B, whereas the sink in G' is mirrored the source t' in B.
We can reverse any pseudo-flow f on G to be another pseudo-flow I' on B, where for all e E F(G), f² = fe- Notably, f and f' saturate the same cut, and observe exc,(u) ( and defy(u) = excy (u').
Suppose we have pseudo-flow f that saturates cut 8So, To) in G' with no excess nodes in To- Then in the backwards network B, f" saturates S(Tū, S)), where Ty (resp. Sg) is all mirror nodes p' for such p To (resp. So). Now Sy becomes the sink-side of the cut. In B, we can send flow from excess nodes and to deficit nodes within Sg 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 8 to deficit nodes in Gj [So]- After adding this reversed flow to f. the result is cut-saturating pseudo-flow for G, where there is no deficit on the s-side of the cut. Observe that there is no excess deficit created on either side of the cut in the process.
A.3 Pre-processing the pseudo-flows
Given pseudo-flow, the first phase is pre-process f into cut-saturating pseudo-flow on G and to compute 17. 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 minimum cut between 8* and and obtain a flow f". Corollary 1 bounds the
run-time in this case. Adding f' to ff creates a cut-saturating pseudo-flor flow. The next lemma proves the output of this algorithm satisfies the desired properties and that the algorithm runs in time O(1 . n²?).
Lemma 8. Suppose f is a predicted pseudo-flow with unknown error for network G. Then Algorithm 5 computes d) and finds cut-saturating pseudo-flow for G with error n in time On ne)
Proof. In the residual graph Gj. the min-cut is bounded by n, since is most 1) far from being cut-saturating, Therefore, we can apply Corollary to Gj and obtain an optimal flow f' on Gj in O(n n²) running time. The flow we desire is fe f/ + fe for all e E E. It is cut-saturating for G by the optimality of f' on G Further, it is pseudo-flow since f' does not have any excess or deficit in Gj y and clearly ft + fe < ce for all E E.
We turn our attention to the error value computed by Algorithm 5. Let 17" be the true unknown value.
Note that in the auxiliary graph G' constructed in Algorithm 5, if the current value of 1) can be sent from 8" to f,, there exists 8 f flow of 1) in the residual graph; meaning when Push-Relahel terminates the s* - f cut we will find is just the edge This is a certificate that 17" 2 r7. We double values of 7 until we find some value where the cut in G' is no longer (s",s). This is a certificate that '7" I 7). Given upper bound and lower bound 17" one run binary search in this range and continue using the cut-based certificates to further limit the range in which 17" 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 pre-flow on Gj. and the resulting f = f + f will have total excess bounded by 21y. 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-flor floww as in Algorithm 5.
By Definition 1, if a pseudo-flow f a far from cut-saturating means augmenting it by another flow f with value at most saturate some cut. Let this cut be 8(S, 2). Another way to look at
15

---

this is, within f, the total flow passing through the cut Ö(S, satisfies:
Σ
Σ
((nw) 2
Σ
C(u,o)
((v,a)) + a.
WES
MES,NET
MES,
MES,NET
Apart from solving max-flow in the residual graph to saturate this cut, there may be other options to create cut-saturating pseudo-flow. For example, the 77 bound on error does not directly tell where this cut is. However, if a practitioner can "guess" a good enough cut ö(S, T') from past problem instances, such pseudo- floo can also be obtained simply by saturating all edges (u, v) E 8(S. T) and removing the flow on all backward edges. The downside is that such practice will transfer the error on that particular cut the total excess and deficit on nodes incident to the cut. Overall, there may be trade-off where one can omit Algorithm 5 in lieu of using predicted cut, but at the cost of having to fix more excess and deficit later steps.
A.4 Early termination of auxiliary Push-Relabel upon finding min-cut
We mentioned that one can choose to quit the Push-Relas Mush-Relabel algorithm on auxiliary graphs whenever a is found. The resulting pseudo-flow although violating flow conservation constraints, still be added to the initial pseudo-flov floo.. We give a brief analysis of how this effects the execution of the algorithm.
The pseudo-flow is constructed three places:
1. In Algorithm 5, where we saturate a cut;
2. In Algorithm 3, where push flow from t-side excess nodes deficit nodes and t;
3. In Algorithm 6, where we push flow from s-side excess nodes and to deficit nodes.
Notice this simple fact: Claim For pseudo-flows f. and f" where f = + (without violating capacities constraints),
we have:
[(exc (u) + (ef - Σ (excy + defp (u)) + Σ (excxx"(x) + (w))
In Step 1, Algorithm starts with finit with excess 7), hence the resulting pre-flow also has 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 EneT, exc,(u) S 17. so the end of Algorithm the total excess also increases by this much. Step correspondingly the maximum increase is Eves, def 7 (u) I To sum up, early termination in the auxiliary networks after finding the min-cut increases the total error by (()), and therefore has the run-time bound up constant factor.
B
More on Experiments
B.1
Omitted Tables and Figures for Experiments
Table 3 contains detailed description of each of the four image groups, their original size in the raw dataset, the cropped grey-scaled image size, the foreground/backkroundd they feature, etc.
Table 3: Image groups' descriptions (copy of Table 1 from [DMVW23]]
Image Group
Object, background wood birdhouse, backyard
Original size
Cropped size
BIRDHOUSE
1280, 720
600. 600
HEAD a person's 's head, buildings
1280. 720
600, 600
SHOE
shoe, floor and other toys
1280, 720
600. 600
DoG
Bernese Mountain dog, lawn
1920, 1080
500,
Figure gives one example of raw images from each image group.
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
16

---

aa) Birdhouse
(b) Head
(c) Shoe
(d) Dog
Figure 4: Instances of images from each group (copy of Figure from [DMVW23]).
Figure 5: Cuts (red) on images chronologically evolving from the 240 x 240 pixel images from DOG.
B.2 More On the Graph Construction
We take input an image pixel set V, and two sets of seeds O, B C V. The seed set O contains pixels that are known to part of the object, while the seed set contains pixels that are known to be part of the background. The intensity gray scale of pixel is denoted by I,- We say that two pixels are neighbors they are either the same column and in adjacent rows or same row and adjacent columns. Intuitively, if neighboring pixels have very different intensities. one to be part of the object and one to be part of the background. For any two pixels p, E V, solution that separates them, i.e., puts one pixel in the object and the other one in the background, incurs a penalty of 8p.g. For neighbors p and g. 9p.q C exep(-11 - I,)² (2a²)), for C a large constant, otherwise the penalty is O. Note that the quantity Bp.q gets bigger when neighbors p and q have stronger contrast.
might expect
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 fixed segmentation solution. Then the coundary-basede objective function is the sum of of the penalties max. EpeJagg Sp.g. for J with O C J. C V \ J. As in the definition, a positive penalty cost only incurred on the object's ' boundary. The goal is to minimize the total
Figure 6: Cuts (red) images chronologically evolving from the 240 x 240 pixel images from HEAD.
17

---

Figure 7: Cuts (red) on images chronologically evolving from the 240 x 240 pixel images from DOG.
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 a node for each pixel, plus the object terminal a and the background terminal L. As notation suggests, is the source of the network and is the sink. The edge set on the nodes as follows: (1) for every v E add edge (s, e) with capacity M, for M huge enough value that it is never saturated in any optimal cut; (2) for every E B add edge (u, t), again with capacity M; (3) for every pair of nodes p, 9 E V. add edges (p, q) and (g.p) with capacity 3p.q. If an image is on n pixels, note that the graph is sparse with [V] = (( nodes and |E| = edges.
In our experiments, all 3p.q's 's are rounded down to the nearest integer, so that capacities are integral. Since Sp.g I C' by definition, it suffices for us to let M = CIV.
B.3
Other Settings
We have discussed how to cope with unknown in Algorithm 5 by using doubling search from an initial guess // = 1 in order to guarantee the (z) time bound. However, practice, we have discovered that this is not absolutely necessary. One can use other surrogates for long as they prove an effective upper bound on the error. In our experiments, rj 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 purpose.
In these experiments the real error n of the given predicted flow could be high. For example, on a sequence of 10 images of size 60 x 60 from the group DOG. The average total excess/deficit accounts for 69% of the real min cut, whereas the a. computed 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 7j not negligible but still boosts Push RelabRRlabbl'ss performance with warm-starting, despite the dependency of the theoretical bound on 1). 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 similar levels, and can be even higher than the max- flow 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 (mm)). Excesses/deficits are big in our setting, too, but the initialized pseudo-flor flow is already quite close to being sat-satura.ing. This might account for the speed-up we obtain.
18

---

NeurIPS Paper Checklist
1. Claims
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
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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 other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations 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
Guidelines:
The answer NA means that the paper has 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 (c.g.. independence assumptions, noiseless settings, model cell-speciiiaatinn 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 few datasets or with 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, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
19

---

Answer: [Yes]
Justification:
All Theorems and Lemmas are proved either in the main body or the appen-
dices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
We describe the experiment setup in detail Section 4, and in Appendix B.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
20

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We used public datasets. Links to download the datasets are given in the paper. Code uploaded in the supplementary files.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
wwwssssoooooooooooo onooloooooooooo icy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. cc/ mublic/guides SudeeS/mmm Sanasuuumssssss wwsssssollll.o..oo onnolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, 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 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, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
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, confi-
dence intervals, statistical significance tests, 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 with given experimental conditions).
21

---

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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Explained in both main body and the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: / /ttp///eerrpp.eeeee//ee htcp/pbblcc/thhhccuteeeeeeeee
Answer: [Yes]
Justification: Code of Ethics has been reviewed.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: NA
Guidelines:
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 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.
22

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Lieenses 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 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
23

---

If this information is not available online, the authors are encouraged to reach out to the asset's '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/moodl 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.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS 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.
24


Reviews:
[{"review_id": "KiSsCHJBmV", "reviewer": "Reviewer_C4XM", "summary": "This paper propose and analyzes a warm starting scheme for the classical\npush-relabel algorithm for max-flow problems. The basic approach is to convert\nthe warm-starting flow into a cut-saturating flow, at which point a clever\npush-relabel scheme is used to ensure that the source-side of the cut has only\nexcess flow while the sink side of the cut has only flow deficits.  This\nimmediately yields a min-cut and is easily transformed into a max flow\nsolution.  The authors compare their approach with warm-starting methods for\nthe Ford-Folkerson algorithm, which they show is less efficient in practice.", "questions": "- Can $\\eta$ ever exceed $O(m)$? That is, are the circumstances where \n    the warm-started version of push-relabel has worse asymptotics than\n    cold-start push relabel?\n\n\n- What about using randomized predicted pseudo-flows $\\hat f$ to\n    warm-start push-relabel? I ask because, in continuous optimization, random\n    initializations often out-perform default initializations like $0$. It\n    would be interesting to choose a distribution for $\\hat f$ and then compute \n    the expect value of $\\eta$ or perhaps high probability bounds on $\\eta$.", "limitations": "Limitations are appropriately addressed in the paper.  The paper topic might be\nconsidered somewhat niche to the majority of the NeurIPS audience. This is not\na weakness of the paper, however.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is well written and understandable by non-experts.\n\n- The warm-started version of push-relabel has a very nice instance-dependent\n    complexity compared standard push-relabel ($O(m n^2)$ to $O(\\eta n^2)$),\n    allowing for fine-grained complexity estimates.\n\n- Warm-started push-relabel works well in practice and is much faster than\n    other warm starting methods for large problem instances.", "weaknesses": "- The error $\\eta$ of a pseudo-flow $\\hat f$ is hard to estimate without\n    running Algorithm 5, meaning the total complexity of computation is not\n    known until partway through execution. Moreover, this issue is not addressed\n    in the paper.\n\n- It is difficult to compare warm-started push-relabel with the Edmonds-Karp\n    selection rule for Ford-Fulkerson because their complexities they depend on\n    different aspects of the problem. \n\n### Detailed Comments\n\nFirstly, I want to say that this paper is significantly outside of my research\narea (convex optimization) and so I cannot comment on the novelty of the ideas.\nHowever, I think the ideas in this paper are of significant interest,\nparticularly for researchers focused on deriving instance-dependent\ncomplexities. As such, I think the paper should probably be accepted.\n\n\n**Computing $\\eta$**:\nReading Section A.3, it seems like computing the value of $\\eta$ is a\nunaddressed difficulty in the main paper. I don't think it is reasonable to\nconsider $\\eta$ to be input to the algorithm, so the doubling procedure in A.3\nis required to estimate $\\eta$ when running Algorithm 5. Since the complexity\nof estimating $\\eta$ with Algorithm 5 is no greater than that of running\nAlgorithm 5 with $\\eta$ as in input, I think it makes sense to write the full\nalgorithm without knowledge of $\\eta$ in appendix. Similarly, some comment\nshould be made about this issue in the main paper. \n\n\n**Edmonds-Karp Selection Rule**: \nYou comment that Ford-Fulkerson with the Edmonds-Karp selection rule has\ncomplexity $O(m \\|f^* - \\hat f\\|_1)$. In comparison, warm started push-relabel\nhas complexity $O(\\eta n^2)$. It is difficult to compare these two complexities\nsince $m \\leq n^2$ but $\\eta \\leq \\|f^* - \\hat f\\|_1$. In practice,\nwarm-started push-relabel seems to have much better complexity, but is it\npossible to draw a rigorous comparison between the two methods? At the very\nleast, I think this issue should be addressed in the main paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Please see our responses to all reviewers for your questions on comparing warm start PR to warm start FF, as well as computing eta.\n\nQ: *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?*\n\nA: Indeed by definition \\eta can be bigger than \\Omega(m). However, the running time of our algorithm is never asymptotically worse than that of cold-start push relabel. This is because our algorithm solves Push-Relabel in several auxiliary graphs, and in each of them the running time is always bounded by the vanilla $O(n^2m)$ worst-case bound regardless of the min-cut value and $\\eta$. In other words, the running time of our algorithm is actually $O(n^2 \\min{m,\\eta})$. We will update this in the final version.\n\nQ: *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 $\\vec{0}$. It would be interesting to choose a distribution for \\hat{f}  and then compute the expected value of \\eta or perhaps high probability bounds on $\\eta$.*\n\nA: While a random $\\hat{f}$ would likely have very large $\\eta$, it would be interesting to study the expected value of $\\eta$ given a distributional assumption on $\\hat{f}$. The literature on learning-augmented algorithms has been content with proving the PAC-learnability of a prediction, and has not yet focused on obtaining predictions that are guaranteed to be of high quality with respect to the chosen error metric. A few works have started to explore this (see the recent work by Srinivas and Blum), but it is still nascent and seems quite challenging.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JGrLoQbhBm", "reviewer": "Reviewer_gRPX", "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.", "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": "No ethical limitations", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This provides the first theoretical guarantees for warm-starting Push-Relabel with a predicted flow and demonstrates the benefits of learning-augmented version in improving the running time, where the predicted flow is close to an optimal flow. \n\n- The theoretical results are further demonstrated by empirical experiments using image segmentation tasks over image sequences datasets, where the predicted flow is given by the result of the previous image sequence. \n\n- The paper is well-written and well-structured, with clear motivations. The theoretical results deliver important insights about the practical benefits of utilizing learning-based predictions for the fundamental problems on graphs.", "weaknesses": "- The algorithm (Algorithm 2) requires a bound on the error $\\eta$ of the prediction, which can be hard to estimate in practice. \n- 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Please see our responses to all reviewers for your questions on comparing warm start PR to warm start FF, as well as computing eta.\n\nComment: *The algorithm (Algorithm 2) requires a bound on the error $\\eta$ of the prediction, which can be hard to estimate in practice.*\n \nResponse: We refer the reviewer to our “Response for all reviewers” for a thorough discussion on how $\\eta$ is computed and used. To sum up, $\\eta$ can be estimated using the doubling search procedure described in Appendix A.3 (line 476-494) at no additional run-time complexity. The same procedure also transforms the given pseudo-flow to a cut-saturating one, both the flow and the estimated value $\\eta$ are output together, and that $\\eta$ is used as the input to Algorithm 2. In that response, we have also discussed $\\eta$ in the experiments, and compared it to the min-cut. Note that despite the theoretical dependency on $\\eta$, we obtained the efficiency improvements with non-negligible $\\eta$ values. Hence we are reaching conclusions similar to that in [Davies et al, 2023].", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4IFlcHVXRC", "reviewer": "Reviewer_oTzZ", "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.", "questions": "I encourage authors to discuss and address the weaknesses I have highlighted above. A few questions follow for the sake of clarity:\n- *[done]* Could you explain how the cold-start is performed ?\n- *[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": "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.\n\nNo potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- Overall the paper is well-written.\n- (Theorem 2) Authors provide the worse case complexity of their algorithm while using a cut-saturating pre-flow (arguably most intuitive init knowing maintains this structure along iterations)\n- (Theorem 1) General case given any predicted pseudo flow.\n- Good empirical validation of the theoretical results and comparison with FF algorithms using different warmstart strategy.", "weaknesses": "*edits after authors' rebuttal are in italic*\n\n1. Potentially under-exploited empirical results:\n   - 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.\n   - 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.\n   - 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.\n\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Please see our responses to all reviewers for your questions on comparing warm start PR to warm start FF.\n\nComment: *visualizations corresponding to values reported to Table 2 / 5 could have been interesting to really observe the quadratic behavior.*\n\nResponse: Please see the pdf attached in the response to all reviewers (this was the only place we could attach a pdf). In a final version, we could take more time to find better scales for each dataset.\n\nComment: *Lack of analysis w.r.t the \"parameter\" $\\eta$, that relates to the error between the previously predicted flow and the new one.*\n\nResponse: See the comments addressed to all reviewers for discussion on the a posteriori eta value measured on the real cuts. To sum up, we have a lot of excess/deficit resulting from rounding the previous max flow; however the pseudo-flow is close to saturating the real cut, making it a potentially good starting point for warm-start. The results match those in the evaluation of warm-start Ford-Fulkerson in [Davies et al., 2023] where prediction error is also big, but shorter augmenting paths used to fix excess/deficit lead to the improvement in warm-start.\n\nQ: *Could you explain how the cold-start is performed?*\n\nA: Based on each image from the sequence we construct a graph instance, where edges and their capacities are determined as instructed in Line 293-298. Then we run the vanilla Push-Relabel algorithm with gap relabeling (see Algorithm 1) on these graph instances individually. The algorithm itself is the standard Push-Relabel procedure that takes the graph, saturates all the edges going out of the source, labels the nodes with valid heights and finds an active node (in this case, the one with highest label among all the t-side nodes) to push flow from in every iteration.\n\nQ: *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.*\n\nA: The running time shown in Tables 1, 2, and 3 are averages taken over a sequence of 10 images for all 4 image groups to eliminate the bias of particular problem instances. The standard deviation is typically 5-15%, depending on different image groups and sizes. To eliminate the biases of machine status, repeating experiments on any fixed image instance has shown the per-image run-time standard deviation to be typically less than 1% of the average run-time, which is way less than the variance across different instances. This is measured over 100 repeated runs. If accepted, we will add the standard deviation data into the paper.\nAll experiments are run on a device with processor Intel(R) Core(TM) i9-12900H @ 2.50 GHz, and 36GB memory.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EkTPhrsRUP", "reviewer": "Reviewer_D3Wp", "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.", "questions": "1. How can we know $\\eta$ in Algorithm 2? Is it given as an output of Algorithm 5?\n2. 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$? \n3. 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)$.\n\n\n#### **Minor comments**\n- Please define what \"saturate\" means for clarity.\n- 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": "Yes.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The push-relabel is an important practical algorithm with a large gap between theory and practice. The paper gives an interesting result to fill the gap.\n2. Similarly, the analysis that applies to push-relabel with the gap-relabeling heuristic is also a nice result.\n3. The algorithm for swapping excess and deficit nodes between $t$- and $s$-sides is an interesting new gadget.", "weaknesses": "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.\n2. 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.\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Please see our responses to all reviewers for your questions on comparing warm start PR to warm start FF, as well as computing $\\eta$.\n\nComment: *I would like to know whether we can develop a better method for learning $\\hat{f}$ based on the error measure in Definition 1.*\n\nResponse: It is an interesting question as to whether our more fine-grained error metric can give insight into designing better predictions. We think there is room for improvement here. In our experiments, our predicted flow is the solution to a previous, similar instance. While these predictions can still have large error with respect to $\\eta$, we believe it is on the right track to a more comprehensive error metric, which would measure how far $\\hat{f}$ is to saturating a min cut. The literature on learning-augmented algorithms has not yet focused on obtaining predictions that are guaranteed to be of high quality with respect to the chosen error metric. A few works have started to explore this (see the recent work by Srinivas and Blum), but it is still nascent and seems quite challenging.\n\nQ: *If my understanding is correct, in the experiments, $\\hat{f}$  is set to the old max-flow in the previous image. Does this $\\hat{f}$ attain small $\\eta$?*\n \nA: We refer to the comments addressed to all reviewers for a more detailed discussion. We have followed the practice in [Davies et al. 2023] when testing warm-start Ford-Fulkerson. Our $\\eta$ contains both excess/deficit and the minimum slack from saturating any cut. In that sense, this choice of $\\hat{f}$ does not attain small $\\eta$, for rounding the previous max-flow by the new capacities results in a lot of excess/deficits. However, $\\hat{f}$ is close to saturating the TRUE min-cut, which promises good initial progress for warm-starting.\n\nQ: *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)$.*\n\nA: The actual running time scales with $\\eta$ better than the theoretical $O(|V|^2 \\eta)$. This is not totally surprising, as Push-Relabel is known to often enjoy subquadratic running time despite the $O(|V|^2|E|)$ bound. We refer to Table 2 for how the running time of warm-start Push-Relabel scales with growing image sizes. When the image size changes from $n \\times n$ pixels to $2n \\times 2n$, $|V|$ and $|E|$ grow by 4 since they are both roughly $n^2$, $\\eta$ typically grows as fast as the max-flow/min-cut value, which in this case is a factor of 2. One can see that warm-start Push-Relabel’s actual performance goes beyond the theoretical bound, as does the cold-start Push-Relabel.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their careful reading of our paper! We are glad they agree that warm-starting the push relabel algorithm to find a max flow/min cut is an interesting theoretical question with potentially useful practical applications.

Please see comments on questions brought up by several reviewers here, and individual replies below each review. Also, the visualization requested by Reviewer oTzZ is attached.


**Comparing to work on warm-starting Ford Fulkerson**: Recall the cold-start running time of Edmonds Karp is $O(m^2n)$, while cold-start PR is $O(mn^2)$. Previous work in [Davies, et al. 2023] shows that warm-start FF has running time $O(m ||\hat{f}-f^*||_1)$, while we show that warm-start PR has running time $O(n^2 \eta) < O(n^2 ||\hat{f}-f^*||_1)$. Our theoretical result may not always be better than warm-start FF, depending on how close $\eta$ and $||\hat{f}-f^*||_1$ are (note Push-Relabel is less affected by sparsity then Edmonds Karp). Overall, this is not a weakness to our analysis, but is an artifact of the community’s  lack of understanding on why push-relabel performs so much better in practice than its theoretical bounds guarantee.

We further explain the theoretical importance of our result. Improving our theoretical understanding of algorithms that do well in practice (like Push-Relabel) is one of the pillars of the field of beyond worst-case analysis (most famously, the smoothed analysis to analyze the Simplex Method, though see also Tim Roughgarden's book and lectures on beyond worst-case analysis). 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, and tools are actively being developed with a hope of eventually achieving this goal (e.g., the line of work by J. Diakonikolas and Song). 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 runtime when the value of the max flow/min cut is small (see our Corollary 1). While such a result was known for Ford-Fulkerson, this was NOT known for Push-Relabel prior to our work. We speculate this monotonic property may have further theoretical importance in improving Push-Relabel analyses on more general classes of networks.

We are happy to add this discussion to the main body of the paper in the technical contributions section.

**Computing $\eta$**: The error metric $\eta$, when unknown a priori, is computed synchronously while transforming the given pseudo-flow to be cut-saturating, and given as input to Algorithm 2 afterwards. This procedure is described in A.3, lines 476-491.  The doubling search finds $\eta$ “for free” (the found $\eta$ is at most twice the true error in Definition 1) without additional running time complexity for the overall algorithm. Note that the doubling trick is a standard tool in algorithm design for coping with unknown values. 

We agree with a reviewer that more discussion on computing $\eta$ should be in the main body, hence we propose making the following changes to clarify how $\eta$ is found and used. In Appendix A.3, we will explicitly add pseudocode to formally describe the doubling search procedure for $\eta$: initialize with $\eta$=1; in each iteration call Algorithm 5 as a subroutine that takes $\eta$ as input and tries to augment the pseudo-flow by value $\eta$; if successful, then $\eta$ doubles. The procedure terminates upon saturating the flow, i.e., Algorithm 5 finds a $s-t$ cut instead of cutting the edge $(s^*, s)$. The new pseudocode, along with Algorithm 5, completes the pre-process algorithm for warm-start flow initialization, and also outputs a correct error bound $\eta$ that is used in subsequent push relabel operations. In the main body before Algorithm 2 is stated, we will clarify that $\eta$, if unknown, has to be found via the algorithmic approaches in A.3 and add a short summary on the doubling search procedure.

**Empirical Values of $\eta$**: Many reviewers are interested in the computation of $\eta$ in practice and its value in our image segmentation experiments. The doubling procedure in A.3 is an option, but one can use other surrogates for $\eta$ as long as they prove an effective upper bound on the error. In our experiments, $\eta$ is estimated by computing both the total excess/deficit, and the $\sigma$ (in the “$\sigma$ away from being cut saturating” notion in Line 75) by using the old cut in the previous image in the sequence. Typically this is a loose bound, but it suffices for our purpose.

We show the error metrics on a sequence of 10 images of size 60X60 from the group DOG. The average total excess/deficit accounts for 69% of the real min cut, whereas the $\sigma$, computed a posteriori using the min cut, accounts for about 23%. The results should be read together with the measured error metric value in [Davies, et al., 2023] under the same experiment designs. Our $\eta$ is not negligible but still boosts Push-Relabel's performance with warm-starting, despite the dependency of the theoretical bound on $\eta$. This is typical --- algorithms in practice often run much faster than their theoretical bounds. In [Davies, et al. 2023], the empirical prediction errors (see, e.g., Table 5 in the Appendix) are at similar levels, and can be even higher than the max-flow 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 \eta). Excesses/deficits are big in our setting, too, but the initialized pseudo-flow is already quite close to being cut-saturating. Perhaps this explains the speed-up we obtain.

Meta-review: 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.
Decision: Accept (poster)