Improved Approximations for Hard Graph Problems using Predictions

We thank the reviewer for their careful reading and comments. We address the weaknesses they mentioned below.

On datasets and Benchmarks: The main focus of our paper is on giving rigorous theoretical improvements for classic NP-hard problems. We view our experiments as proof-of-concept, demonstrating that our theoretical ideas are also implementable. (We note that prior work such Cohen-Addad et al. who also studied augmenting NP-hard problems don't have experiments).

We also provide some intuition for our experimental choices. For independent-set, we believed it is natural to test on social networks since the problem is optimizing for a collection of nodes with no mutual connections. Thus in our paper, we selected two social networks from the popular SNAP library. We picked moderately sized networks since we wanted to validate the quality of the approximation returned by our augmented algorithm by comparing to the exact optimal solution. However, the independent set is NP hard, so computing the exact optimal requires running an expensive integer linear program, which is prohibitive for large graphs (this is exactly why approximation algorithms for NP hard problems are useful!). Note that to use our algorithm, computing the optimum is not necessary; we only do it to compute our algorithm’s exact approximation factor on real world datasets. In practice, this step can be skipped since we already give a mathematical guarantee bounding the approximation factor.

Lastly, we ran a new experiment on a much larger graph on a subgraph of large social network from SNAP (https://snap.stanford.edu/data/twitch_gamers.html) with ~50k nodes and ~1.1 million edges (we pruned the original graph to make the integer linear program for finding the optimal feasible). As seen in the figure in this anonymous link (https://ibb.co/60N2W8T1), the qualitative behavior remains the same: our learning-based algorithm can outperform the standard greedy approximation algorithm as well as the algorithm that only uses the predictions.

does not explicitly address whether the algorithm remains efficient in terms of both time and space complexity when applied to very large graphs.

All of our algorithms provably run in polynomial time and space so theoretically they are efficient for even very large graphs. This is our main message: by using very noisy predictions, we can get improved approximation algorithms for fundamental optimization problems in polynomial time. Our approximations using predictions overcome existing barriers which without predictions are not possible in polynoial time (assuming P != NP).

the paper does not provide a clear explanation of how to determine this ε for graphs of different sizes

The paper doesn't clearly explain how prediction errors are handled

Our guarantees already have worst case guarantees built in, even if the predictions are arbitrarily corrupt, in three ways.

1. Our approximation factors consist of two terms: one coming from the classic bounds without predictions and a term $f(\epsilon)$ that is the advantage that we have using edge-predictions that are correct with probability $½ + \epsilon$. (Note $f(\epsilon)$ depends on the problem). We recover the original worst-case guarantees by letting $\epsilon \rightarrow 0$. This corresponds to predictions that are random noise with no signal. On the other hand, our approximation factors improve as $\epsilon$ increases. Thus, our bounds naturally interpolate between the purely noisy case and to the case of large $\epsilon$ where we provably obtain an advantage over no predictions.

2. Even if the $\epsilon$ parameter is not known in practice, we can simply guess over multiple choices of $\epsilon$, run our algorithm, and take the best solution. E.g. in vertex cover, we can instantiate our algorithm for different $\epsilon$ values and take the smallest cover over all choices. This is because the problems we study are in NP, so we can compute the quality of the solution in polynomial time. Since for our theoretical bounds we only need to know $\epsilon$ up to a constant factor, our guess over $\epsilon$ can be done efficiently. That this also handles the reviewer’s other concern about determining $\epsilon$ in practice.

3. Lastly, we can also run another approximation algorithm in parallel to our algorithm, e.g. classic approximation algorithms, and take the best solution (this is because the problems are in the class NP so we can compute the quality of the solution returned by both algorithms). This ensures that we can never output something worse than the classic algorithm.

Overall, we thank the reviewer for their feedback. We believe we have addressed the reviewer’s main concerns about how our algorithms scale, as well as how our algorithms handle prediction errors. We are happy to provide additional clarifications and engage further in the discussions if we have misunderstood any crucial points.

Many thanks, The Authors.

We thank the reviewer for their careful reading and comments.

report the variance of the results for algorithms

Thank you; we will do this in the final version.

It would be interesting to see how the algorithms perform if the predictions are not eps-accurate

Thank you for this question. This is a nice future direction to study. However, we note that even if the $\epsilon$ parameter is not known in practice, we can simply guess over multiple choices of $\epsilon$, run our algorithm, and simply take the best solution. E.g. in the vertex cover example, we can instantiate our algorithm for different $\epsilon$ values and take the smallest vertex cover over all choices.

We thank the reviewer for their careful reading and comments.

a few typos and corrections:

Thank you, we have fixed the typos.

It is not clear how in practical cases one can make available predictions with the desired bounded reliability.

How do you guarantee the goodness of the prediction?

Our guarantees already have worst case guarantees built in, even if the predictions are arbitrarily corrupt, in three ways.

1. Our approximation factors consist of two terms: one coming from the classic bounds without predictions and a term $f(\epsilon)$ that is the advantage that we have using edge-predictions that are correct with probability $½ + \epsilon$. (Note $f(\epsilon)$ depends on the particular problem studied). We recover the original worst-case guarantees by letting $\epsilon \rightarrow 0$. This corresponds to predictions that are random noise and have no signal. On the other hand, our approximation factors improve as $\epsilon$ increases. Thus, our bounds naturally interpolate between the purely noisy case (where our guarantees converge to worst-case bounds) and to the case of large $\epsilon$ where we provably obtain an advantage over the setting with no predictions.

2. Even if the $\epsilon$ parameter is not known in practice, we can simply guess over multiple choices of $\epsilon$, run our algorithm, and simply take the best solution. E.g. in the vertex cover example, we can instantiate our algorithm for different $\epsilon$ values and take the smallest vertex cover over all choices. This is because the problems we study are in the class NP, so we can compute the quality of the solution in polynomial time. Since for our theoretical bounds we only need to know $\epsilon$ up to a constant factor, our guess over $\epsilon$ can be done efficiently. Note that this also handles the reviewer’s other concern about determining $\epsilon$ in practice.

3. Lastly, we can simply run another approximation algorithm in parallel to our algorithm, e.g. the classic approximation algorithms without predictions, and take the best solution (again this is because the problems are in the class NP so we can compute the quality of the solution returned by both algorithms). This ensures that we can never output something worse than the classic algorithms.

Can you provide experimental comparison with the other prediction-augmented algorithms proposed in the literature.

For independent-set (the setting of our experiments) we are only aware of one prior work of Braverman et al. They use a different prediction model (vertex-based predictions) and obtain a substantially worse theoretical approximation factor (their approximation factor can be $\sqrt{n}$ whereas we get a constant approximation). The authors did not provide an implementation of their algorithm.

Nevertheless, we tested their algorithm on the two datasets in our main submission. If we implement their algorithm as it is written in their paper, then their algorithm just converges to the standard greedy algorithm (dotted green line in our Figures). This is because their algorithm first prunes nodes based on a complicated degree condition (see Algorithm 1 in https://arxiv.org/pdf/2407.11364) and then runs the greedy solution on the pruned graph. However, the constants are quite large in the pruning condition so in the two graphs we tested, none of the nodes were pruned (and we suspect this to be the case for most “real world” graphs). Thus, their algorithm performs their step 4 (compute the greedy solution on the remaining un-pruned nodes) on the entire graph. (More precisely, their condition 2 of including all nodes in L with degrees at most $36 \cdot \log n$ always includes all nodes in our datasets). Perhaps one can optimize their constants to obtain a more reasonable bound, but we did not pursue this. Given this, we believe their algorithm to be mostly of theoretical interest, but it is an interesting direction for future work to devise a more practical version of their algorithm.

We thank the reviewer for their careful reading and comments. We address the weaknesses they mentioned below.

Their general idea is that for high degree vertices, decide their status in the solution based on the majority of information we have about them ... Finally, they handle low-degree vertices using a simple greedy approach specific to each problem.

We agree that our high level idea of separating the vertices into heavy and light degrees is quite intuitive and generalizes across many problems. We view this as a strength of our framework. However, we would like to point out the many technical challenges we need to overcome.

Our ‘high degree’ threshold is a constant (depending on $\epsilon$ and independent of the graph size). This alone is not enough to union bound over potentially $O(n)$ high-degree vertices. Thus, there is always a non-negligible chance that a high-degree vertex gets misclassified. This can be very problematic since high-degree vertices can be highly influential in the final solution. For example in vertex cover, a high-degree vertex which is misclassified to not be in the solution can make us add all of its neighbors in the vertex cover, leading to an unbounded competitive ratio if we are not careful. Thus in all of our problems, we need a sophisticated “cleaning step” which not only fixes any misclassifications, but also helps us successfully merge the solution found for low-degree vertices. This is non-trivial since the solution on low-degree vertices may conflict with the solution on high-degree vertices, e.g. for independent set. Our cleaning step is especially subtle for the weighted vertex cover problem,where the weight of a vertex is unrelated to its degree (see the paragraph starting on line 589 for a technical discussion).

I am not sure why their model is interesting.

We believe the edge-based prediction model that we introduce is interesting for the following reasons:

1. Our model gives much stronger theoretical results compared to vertex predictions. For example in Max Cut, vertex predictions in Cohen-Addad et al. give $\approx \epsilon^4$ additive approximation advantage over the best classical approximation whereas edge predictions give $\approx \epsilon^2 \gg \epsilon^4$ advantage. The difference is much more pronounced for independent set where we can get a constant factor approximation, whereas prior work Braverman et al. can only guarantee a $O(\sqrt{n})$ factor approximation with vertex predictions. For vertex cover (weighted and unweighted), we can get strictly smaller than a factor of 2 approximation whereas the vertex prediction based algorithm of Antoniadis et al. has an approximation factor depending on the number of predicted false positives and negatives, which can lead to an unbounded approximation ratio.

2. Our results do not require i.i.d. predictions across edges. Rather, 4-wise independence of the predictions suffices (see our Remark 4.6). This means that our algorithms can handle potentially a huge number of correlations among the predictions.

3. Lastly, while our work is the first to introduce edge predictions for augmenting NP-hard problems, we remark that edge based predictions have also been used in other learning-augmented optimization problems (unrelated to NP-complete problems), e.g. [1] for correlation clustering and [2] for metric clustering.

• KwikBucks: Correlation Clustering with Cheap-Weak and Expensive-Strong Signals. ICLR ‘23
• Metric Clustering and MST with Strong and Weak Distance Oracles. COLT ‘24.

You mention previous work on vertex-based predictions but do not provide their approximation factors. Including these would facilitate comparison with your results.

Please see the first point of our response above. We also note that our submission does contain a thorough discussion on prior work on vertex-based predictions. See Lines 146-164 (right column) for discussion on prior work on vertex-cover, Lines 174-185 (left column) for independent set, and Lines 186-190 for discussion of prior work on max-cut.

Overall, we thank the reviewer again for their feedback. We believe we have addressed the reviewer’s main concern about why our new model is interesting. We are happy to provide additional clarifications and engage further in the discussions if we have missed or misunderstood any crucial points.

Many thanks, The Authors.