/10

Poster4 位审稿人

最低3最高5标准差0.7

ICML 2025

Faster Global Minimum Cut with Predictions

Helia Niaparast,Benjamin Moseley,Karan Singh

提交: 2025-01-24更新: 2025-07-24

TL;DR

We incorporate predictions into Karger and Karger-Stein algorithms to develop faster methods for finding the global minimum cut.

摘要

关键词

Algorithms with PredictionsMinimum CutKargerKarger-Stein

评审与讨论

审稿意见

评分: 42025-03-14

This paper investigates how predictions can be used to improve the running time of classic algorithms for the global minimum cut problem. Given a weighted graph $G$ , the classic algorithm of Karger repeatedly selects edges randomly, proportionally to their weights, and contracts them until two vertices remain, which define the final cut.

In this paper, the authors propose a prediction-augmented framework that modifies Karger’s algorithm by boosting the weights—and consequently the contraction probabilities—of edges that are predicted not to be part of the minimum cut. The algorithm operates by defining a threshold parameter $t$ : while the graph has at least $t$ vertices, edge contractions are performed based on the boosted weights, after which the algorithm switches back to the classic Karger algorithm for the remaining steps. A similar boosting strategy is applied to the FPZ algorithm of Fox et al. (SODA 2019) to improve the running time of the Karger-Stein algorithm through prediction-guided edge contraction.

The paper provides theoretical guarantees showing that, with good predictions, the learning-augmented algorithms recover the minimum cut with high probability, resulting in improved runtime. The analysis characterizes performance in terms of the total weight of false negative edges (respectively, false positive edges) over the total weight of edges predicted to be in the min-cut. These ratios are denoted with $\eta$ for false negatives (where $\eta \in [0,1]$ ) and $\rho$ for false positives (where $\rho$ could be arbitrarily large).

The authors also show how effective prediction vectors can be learned from a distribution over graphs with a sample of polynomial size (hence establishing PAC guarantees for random graphs).

Empirically, the proposed algorithm demonstrates speedups over the classical Karger algorithm, even when predictions are moderately noisy. The experimental evaluation includes tests on synthetic graphs, minimum cut instances derived from TSP LP relaxations, and real-world graph datasets.

给作者的问题

1- Can similar theoretical results be obtained if the values of $\rho$ and $\eta$ are unknown, but upper bounds on them are available? If so, it would be helpful to include a brief discussion of this scenario in the paper.

2- One motivation for augmenting Karger’s algorithm and its variants with predictions is that they are highly parallelizable and thus attractive for practical use. Is it correct that the algorithm of Henzinger et al. (SODA 2024) is not similarly parallelizable? If so, this distinction could be highlighted more explicitly to strengthen the motivation for your approach.

论据与证据

Yes, the main claims of the paper are supported by clear and convincing evidence. The theoretical results are proven and establish how prediction accuracy—quantified through false-positive and false-negative ratios—impacts the success probability and runtime of the modified algorithms. The framework is carefully analyzed for both Karger’s and the Karger-Stein algorithms (via the FPZ framework).

方法与评估标准

Yes, I find the proposed methods and evaluation criteria to be appropriate. The paper focuses on improving the runtime of classical global minimum cut algorithms using predictions, and the evaluation criteria are natural and well-justified. The experimental inputs include synthetic graphs, structured instances derived from TSP LP relaxations, and real-world graph datasets, which are reasonable benchmarks in combination. Together, the methods and evaluation setup effectively support the paper’s goal of combining theoretical improvement with empirical applicability.

理论论述

Yes, I checked the structure and reasoning of the key theoretical results. The arguments seem correct to me, and the proofs follow standard techniques in randomized algorithm analysis. I also reviewed the use of false-positive and false-negative rates in the survival probability analysis and found the reasoning to be clear and interesting. While I did not verify every step in full detail, I found no issues in the high-level logic or conclusions in the proofs.

实验设计与分析

Yes, I reviewed the experiments, which mainly compare the proposed prediction-augmented Karger algorithm to the classical Karger’s algorithm without prediction across a range of instances. The evaluation criteria and results are appropriate and aligned with the theoretical claims.

However, a notable limitation is that the experimental results focus exclusively on the prediction-augmented variant of Karger’s algorithm, while the theoretical analysis also covers the Boosted FPZ algorithm (which is absent in the experiments). Including experiments for the latter would have improved the experiments. In addition, all graphs in the experiments are unweighted, while I believe the weighted case, where weights are highly skewed, is more aligned with worst-case scenarios. Finally, while less critical, it would have been helpful to include comparisons against recent state-of-the-art algorithms for global minimum cut, such as the algorithm by Henzinger et al. (SODA 2024).

补充材料

Yes, I reviewed the supplementary code and the presented datasets. While I did not run the code or attempt to replicate the results, the implementation appears to be correct and aligned with the description in the paper.

与现有文献的关系

The contributions of this paper lie at the intersection of classical randomized algorithms for graph problems and the more recent field of learning-augmented algorithms, which has attracted significant attention in recent years. The paper builds upon Karger’s algorithm for global minimum cut and the FPZ algorithm of Fox et al. (SODA 2019), which extends the Karger-Stein approach. The main novelty is the introduction of prediction-guided edge contraction, where edge weights are adjusted based on predicted cut membership, and a rigorous analysis of how this modification affects the algorithm’s success probability and runtime. Given the foundational importance of the minimum cut problem in both theory and practice, this contribution is valuable.

The work can also be compared to the recent improvements in exact global min-cut algorithms, such as the algorithm by Henzinger et al. (SODA 2024), which represents the current state of the art. While those advances focus on intrinsic algorithmic improvements, this paper explores a complementary direction—namely, runtime acceleration via auxiliary prediction information. That said, the paper could be strengthened by providing a theoretical comparison between the two boosted algorithms presented (i.e., the boosted Karger and boosted FPZ variants), as well as a theoretical and empirical comparison with recent state-of-the-art algorithms without predictions.

Finally, the paper connects conceptually to the broader literature on algorithms with predictions, particularly the line of work initiated by Lykouris and Vassilvitskii (2021) and others, which studies performance guarantees under prediction errors. However, unlike most work in this domain, this paper does not offer formal robustness guarantees, which is an important issue that could be acknowledged and discussed more clearly.

遗漏的重要参考文献

I did not identify any missing references essential to understanding the paper's contributions. Recent work in exact minimum cut algorithms, in particular, the algorithm by Henzinger et al. (SODA 2024), represents the current state-of-the-art algorithms without predictions. Although this paper is orthogonal in motivation, adding a short note about its details would help place the proposed contributions in a broader context.

其他优缺点

One potential weakness, which is acknowledged in the paper, is that the proposed algorithm requires knowledge of the prediction error parameters, particularly the false-positive ratio $\rho$ , to set the threshold parameter $t$ for the theoretical results to hold.
The algorithms are not robust in the following sense. The false positive ratio $\rho$ can be arbitrarily large (it is decided by the weight of the edges that is not bounded as a function of $n$ ). If one knows $\rho$ , which is somehow assumed (see the point above), the algorithm can become robust by ignoring the predictions when $\rho$ is high. But I think knowledge of $\rho$ is not given in adversarial scenarios (maybe one can justify an upper bound for $\rho$ .
Experiments only consider the Boosted Karger algorithm and the unweighted graphs.

其他意见或建议

Consider adding two plots to illustrate how the theoretical performance of the two algorithms compares. In one plot, you could fix $\rho$ (the false-positive rate) and vary $\eta$ (the false-negative rate); in the other, fix $\eta$ and vary $\rho$ . This would help compare the two algorithms, visualize the trade-offs, and provide clearer insight into the relative strengths of the two approaches.
Add a note on how the algorithms can become robust if $\rho$ is known (see above).
As a minor writing suggestion, some of the notation and variable names in the theoretical sections (e.g., survival probabilities, prediction error parameters) could be introduced more formally, with additional intuitive explanations to improve readability and accessibility.
Consider rewriting Theorems 1.1 and 1.2 in a more consistent form, possibly expressing both results in terms of running time, to make the comparison between the two algorithms clearer and easier.

伦理审查问题

作者回复

2025-04-01

Thank you for the helpful comments and suggestions. We would like to highlight the following points:

Knowing parameters: Our theoretical guarantees indeed assume knowledge of $\rho, \eta$ . However, the same analysis applies when only upper bounds on these parameters are available: simply replace $\rho, \eta$ in the analysis with those upper bounds. We will add a discussion in the paper clarifying that the results remain valid under this relaxed assumption.
Comparing to other cut algorithms: This paper is the first to demonstrate how learned predictions can speed up global min-cut algorithms, providing a proof of concept for this new direction. While advanced deterministic or near-linear-time algorithms (e.g., Henzinger et al. (SODA 2024)) exist, they often involve overheads that limit their usability in practice. In fact, as we point out on page 2, due to such overheads, the two most popular network algorithm libraries implement minimum cut algorithms which in theory are far slower. In contrast, Karger’s algorithm remains popular in many graph libraries due to its simplicity and strong parallelization potential. By incorporating learned predictions into Karger’s and Karger-Stein’s algorithms, we show how one can achieve meaningful runtime improvements in realistic settings without sacrificing their desirable practical properties. We will further expand on this point in the final version, highlighting the potential for future extensions of this prediction-augmented framework to other cut algorithms.
Parallelism: Karger’s algorithm (and, by extension, our Boosted Karger variant) is known for its high parallelizability, making it appealing for large-scale distributed settings. We will emphasize in the revised manuscript that Henzinger et al. (SODA 2024), while state-of-the-art in terms of asymptotic complexity, does not share the same level of parallelization potential. This distinction underscores one advantage of our learning-augmented framework.
Runtime of Boosted Karger vs Boosted FPZ: We remark that one theorem refers to the success probability and the other refers to the run time. Therefore, the net runtime of Boosted Karger’s under the requirement that it succeeds with constant probability is $O(n^{2\eta}\rho^{2(1-\eta)}m)$ , since each trial of Karger’s takes $O(m)$ time. Thus, mirroring comparisons between Karger’s and Karger-Stein, Boosted FPZ is always better in terms of sequential runtime. However, Boosted Karger’s like the original Karger’s remain highly parallelizable. We will be happy to make this point explicitly upon revision.

审稿人评论

2025-04-02

Thank you for the clarifications. I found the results in the paper compelling and have updated my current score.

审稿意见

评分: 42025-03-14

Algorithms for boosting minimum cut algorithms with predictions are studied. The authors propose two methods: the boosted Karger’s algorithm and the boosted Karger-Stein method. These methods rely on predictions from a machine learning model to guarantee multiplicative improvements in runtime (Theorems 1.1 and 1.2).

Additionally, the authors describe how, given samples from a fixed random graph model, to efficiently find predictions that minimize an upper bound on the expected runtime of the boosted Karger’s algorithm.

Empirical results on synthetic and real datasets demonstrate the efficacy of the boosted mincut algorithms over their non boosted counterparts when predictions are provided. A practical application to accelerating LP TSP relaxations via subtour elimination is also demonstrated as well as three real network datasets.

给作者的问题

I have no pressing questions at this time. I would be happy to see this paper in icml.

Although I would be happy to see empirical performance on a wider range of random graphs (e.g. other clustered random graphs), and an empirical demonstration of the k-cut Kargers algorithm.

论据与证据

The authors study two classic minimum cut algorithms augmented with predictions. Several theorems characterizing the runtime of these algorithms in terms of the quality of predictions are provided. Additionally, an algorithm to learn optimal predictions (with respect to the runtime of the proposed prediction-augmented cut algorithms) from data is designed and its runtime is characterized. These bounds are justified both via proof and empirical evidence on a variety of synthetic and real datasets.

方法与评估标准

The proposed evaluation criteria (synthetic random bipartite graphs, TSP problems, and real graph benchmarks) are reasonable.

理论论述

I have checked results and proofs in the main text and results in the appendix related to the learning algorithm.

实验设计与分析

Empirical evidence includes experiments on synthetic and real datasets, demonstrating the efficacy of boosted algorithms over their non boosted algorithms over a range of controlled predictions qualities

补充材料

I have reviewed section A2 in the appendix. I have not reviewed the proofs in section A1.

与现有文献的关系

Research into how predictions may inform classic algorithms has important implications in many fields. This paper serves as a good benchmark for how a thorough analysis might be conducted.

遗漏的重要参考文献

I am not aware of missing relevant citations.

其他优缺点

Strengths: The authors study variations of two min-cut algorithms with prediction advice and provide a novel analysis and suite of results to characterize how the quality of the predictions may be used to augment minimum cut algorithms. The topic is an interesting and important, and this paper serves as a nice contribution. The authors demonstrate how one may learn predictions to minimize the expected runtime of the two algorithms. Empirical evidence on synthetic and real benchmarks is provided to demonstrate how predictions may assist. The paper well-written. The analysis is comprehensive and technically correct. Code is provided, which is appreciated.

Weaknesses: The experiments are somewhat limited in scope. I would expect some empirical investigation of how the learning algorithm performs and associated bounds on the expected runtime.

其他意见或建议

"predictioas" typo in conclusion

作者回复

2025-04-01

Thank you for the thorough review. We see our work as a first step in speeding up a fundamental combinatorial optimization problem, and we certainly agree that extensively assessing and demonstrating the empirical performance improvements of prediction-augmented algorithms for such problems is both warranted and a valuable avenue for future work.

审稿意见

评分: 52025-03-15

This paper presents an adaptation of two randomized algorithms for mincut to take into account predictions about whether specific edges appear in a minimum cut. For the simpler of the algorithms, the change consists in simply making a randomized choice of edge by weighing the edges by the prediction. The paper proves the modified algorithm has improved probability of finding a minimum cut, under generous assumptions for the error in the prediction. It also proves that it is possible to learn such predictions with small error and small sample size. An experimental evaluation shows more specific data on the performance of these algorithms in practice.

给作者的问题

none

论据与证据

The claims are well supported, both theoretical and practical

方法与评估标准

I had doubts about the setting of graphs with the exact same set of vertices, but the scenario of using this in the context of solving a TSP made sense.

理论论述

I have not checked the proofs in detail.

实验设计与分析

I found no issues.

补充材料

I have not read them

与现有文献的关系

The paper follows a large body of work (correctly cited) on using predictions to improve existing algorithms.

遗漏的重要参考文献

None that I know

其他优缺点

I liked the writing: factual, honest with respect to drawbacks, to the point.

其他意见或建议

none

作者回复

2025-04-01

We thank the reviewer for their thoughtful review, and for appreciating our transparent writing style.

审稿意见

评分: 32025-03-17

The paper studies global minimum cut with predictions. The problem is given a weighted graph $G$ , find a partition of the vertices $S, V \setminus S$ that minimizes the total weight of edges crossing the cut. Without predictions, there are two main baselines: first a naive version of Karger's minimum cut algorithm which runs in $\tilde{O}(n^2)$ time and succeeds with probability $\approx 1/n^2$ . The second is a smarter version of Karger's algorithm that runs in overall $\tilde{O}(n^2)$ .

The authors present improvements on both of these algorithms using an oracle which gives a predicted set of edges constituting the minimum cut (the authors generalize this to the case where the predictions give a fraction for every edge being in the minimum cut). The two main notions used to measure the error of the predictions are false positives and false negatives (weighted fraction of edges which are incorrectly stated to be in min cut compared to opt vs weighted fraction of edges which are erroneously left out compared to opt). Interestingly the two types of errors have different influences on the final error.

The most interesting regime seems to be for sparse graphs. Assuming that false positives are $o(n)$ fraction of the actual min cut, the submission is able to get a near linear time bound. The main, and quite natural, idea is to boost the probability of picking edges that are not predicted to be in the min cut in the contraction steps of Karger's algorithm.

给作者的问题

Please see above.

论据与证据

Yes, the theorem statements seem to have correct proofs.

方法与评估标准

I have some slight issues with the experiments, see below.

理论论述

I did not check too closely but the main ideas made sense to me. There is one minor question: Should theorem 1.2 have a $+ O(m)$ factor in the running time since we need to read the graph?

实验设计与分析

The experiments seem sound but there are some drawbacks:

One needs to know the values of false positive and false negative rates to initialize the algorithm. While the authors claim that the algorithm is insensitive to such parameters, there was not an extensive empirical evidence for this. It would be better to have a version of the theoretical algo , maybe with slightly worse guarantees, but that is robust to miss-specification of these parameters.
The augmented FPZ algorithm, which is the main technical contribution, is actually not implemented. Thus, the traditional "optimized" version of Karger may actually be faster in practice.
Details on n and m are omitted for the real datasets. Overall, both synthetic and real world graphs seem to be really tiny.
Figure 2A is missing error bars

补充材料

No I did not.

与现有文献的关系

Perhaps the datasets in [1] below could be a good test bed since they test learning augmented graph algorithms on actual large graph datasets (which are varying across time so getting predictions is quite natural).

[1] Triangle and Four Cycle Counting with Predictions in Graph Streams. ICLR 2022

遗漏的重要参考文献

None, the submission is pretty self contained.

其他优缺点

Pro: boosting the weight of an edge based on its prediction seems a natural idea and it's great that they could execute this plan. I think this could be a useful meta idea for future learning augmented works and i find this conceptually very interesting.
Con: Vertex predictions seem more natural in this case? For example, edge predictions could lead to inconsistencies (that maybe one can trivially fix which doesn't seem that natural?) For example, if the prediction says edge (a,b) is in the min cut and (c, d) is in the min cut, then it should imply something about the edges between these vertices as well. However this information is not used or doesnt seem to matter which I find a bit strange.

Overall, I am leaning towards acceptance.

其他意见或建议

None.

作者回复

2025-04-01

Thank you for the thoughtful review. We would like to highlight the following points:

Theorem 1.2: We agree with the reviewer’s observation regarding Theorem 1.2, but this is already taken care of in the theorem statement. Note that the bound in Theorem 1.2 is an ( $\eta$ -weighted) geometric mean of $m$ and $n^2$ , and hence, is always $\Omega(m)$ .
Insensitivity to oracle parameters: Regarding empirical evidence of robustness to knowledge of false negatives and false positives, we refer the reviewer to the first set of experiments, as shown in Section 5.1 and Figure 1. In these, regardless of the value of $\eta, \rho$ , without any tuning, we set $(B, t) = (n,2)$ in the algorithm. Yet the algorithm demonstrates a marked improvement over Karger’s empirically for a wide variety of settings.
Vertex-partitioning predictions: We appreciate the suggestion to investigate vertex-partitioning predictions. In our setting, predictions on edges provide richer information about local pairwise interactions, and our analysis leverages these interactions for robust guarantees. As stated, we do not place any restriction on such predictions, i.e., they may not come from a cut. Note that vertex-based binary predictions can always be translated to edge-based predictions, while the reverse translation is not always possible; thus our prediction model is more generally applicable. The appropriate treatment of probabilistic predictions (as almost all ML models avail us) is also more subtle for vertex-partitioning predictions. All said, deriving faster algorithms based on vertex-based predictions with runtime parametrized by the right characterization of error in such models remains an excellent direction for future research.

最终决定Accept (poster)

2025-05-01

The submission presents an improved version of the Karger-Stein algorithm with prediction-guided edge contraction. The theoretical contribution is very interesting and contains relevant novel ideas. Empirically, the proposed algorithm demonstrates speedups over the classical algorithm, even when predictions are moderately noisy. Overall, I consider this to be a strong contribution to ICML.