acceptodds
Under review as a conference paper at ICLR 2027

Learning-Augmented Approximation Algorithms for Densest -Subgraph

Abstract

We study learning-augmented approximation algorithms for the Densest -Subgraph (DkS) problem under vertex and edge predictions. In the persistent Vertex Prediction Model, each vertex receives a single noisy prediction of its membership in a fixed, unknown optimum ; the predictions are independent and each is correct with probability . We give a polynomial-time algorithm that requires no knowledge of and combines a prediction-guided construction with prediction-free approximation algorithms. For every even , it achieves, with high probability over the predictions, an -approximation, where is the maximum degree and is fixed. Under the Strongish Planted Clique Hypothesis (SPCH), we show that there is a constant such that, for every fixed , no randomized polynomial-time algorithm using persistent vertex predictions achieves an -approximation or, separately, an -approximation with constant success probability. We also establish approximation guarantees for non-persistent vertex predictions and edge predictions. Experiments on real-world and planted graphs with up to millions of vertices show that moderately informative predictions often improve solution quality over prediction-free baselines while maintaining practical running times.

Primary area:
learning theory
Keywords:
Learning-augmented algorithms, Densest k-subgraph, Approximation algorithms, Algorithms with predictions, Hardness of approximation

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_rG4NOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studied the learning augmented algorithm for densest k-subgraph. In the classic version of the problem the goal is to find a subset of exactly kk vertices in the given graph that have a maximum number of edges between them. The best known approximation ratio is O(n1/4+η)O(n^{1/4 + \eta}) for a fixed constant with running time of n1/ηn^{1/\eta}. On the hardness side, randomized gap-ETH rules out ko(1)k^{o(1)}-approx and ETH rules out n1/(log⁡log⁡n)cn^{1/ (\log \log n)^c}-approx in polynomial time. Authors considered learning augmented setting where the input is augmented with machine learned predictions. There exists an oracle that outputs binary predictions on if a vertex is in the optimal solution or not which is correct with probability of 1/2+ϵ1/2 + \epsilon. Note that ϵ\epsilon is not known to the algorithm. Three types of oracles were considered in the paper:

(1) Persistent vertex prediction: the label that oracle assigns to each vertex is fixed and independent.

(2) Non persistent vertex prediction: the label might be different if the algorithm queries a fixed vertex multiple times. Each time the algorithm queries the vertex it gets a newly fresh independent sample of the label.

(3) Edge prediction: where the algorithm can query the oracle for an edge (u,v)(u,v) and it returns two labels for uu and vv. Each edge label is independent from others but it is fixed if the algorithm queries the same edge again.

Intuitively, non-persistent model is easier to think about because for a fixed vertex, the algorithm can query it multiple times and then based on which label appears most, it can increase the accuracy. Edge prediction model is something in between because each edge adjacent to uu can gives information about uu because of the noise assigned to it but it it’s harder than non-persistent model because the algorithm does not have access to infinite number of independent samples for a vertex.

Authors proved the following: (1) Oη(min(k,1+Δlog⁡n/ϵ,n¼+η)O_\eta(min(k, 1 + \sqrt{\Delta \log n}/\epsilon , n^{¼ + \eta})-approx for persistent vertex model

(2) O(1)O(1)-approx for non persistent vertex model

(3) O(1/ϵ2log⁡(n/δ))O(1/\epsilon^2 \log (n/\delta))-approx for fixed constant eps and delta in polynomial time.

In terms of techniques, the main algorithmic idea is the two stages scoring mechanism. First, they use neighborhood information to find k/2 vertices that have most neighbors in the OPT solution and then they choose the second k/2 vertices in such way that they produce most number of induced edges with the first selected half.

Critical strengths

the paper is well written, and proofs are correct as far as I was able to check. The problem they studied is a central problem in computer science and the learning augmented setting is aligned with the conference agenda.

Critical weaknesses

I think the main idea and technicality in the paper is somehow limited and I found the idea behind the algorithm quite simple. Also, another weakness that I see in the paper from the modeling side is the fact that the paper assume independent noise on vertices however, in different applications usually these noises are correlated for neighboring vertices.

Questions for authors

1-would you please mention in theorem 27 statement how δ\delta and ϵ\epsilon appear in the running time?

2-did you think about any formal way of defining noises that can be correlated in local neighborhood?

2 comments

Thank you for the careful review and for recognizing the paper’s presentation, the correctness of the proofs you checked, and the relevance of the problem. We address the concern about technical contribution and your two questions below.

1. Q1: Running Time in Theorem 27.

Algorithm 3 can be implemented in O(∣E∣+nlog⁡n)O(|E|+n\log n) time using at most ∣E∣|E| edge queries. In particular, the running time and edge-query complexity are independent of both ϵ\epsilon and δ\delta. These parameters only determine the degree threshold $ D_{\mathrm{edge}}= \left\lceil\frac{1}{2\epsilon^2}\log\frac{n}{\delta}\right\rceil. $ Each edge is queried at most once, and majority voting uses its existing predictions. Thus, ϵ\epsilon and δ\delta do not introduce repeated sampling. Aggregating predictions, scoring, and finding a maximal matching take O(∣E∣+n)O(|E|+n) time; sorting takes O(nlog⁡n)O(n\log n) time. We will explicitly state these bounds in Theorem 27 and its proof.

2. Q2: Locally Correlated Prediction Noise.

We thank the reviewer for the suggestion. In the new Appendix G, we consider relaxing the mutual independence assumption in the persistent Vertex Prediction Model to allow bounded local dependence.

Specifically, we retain the marginal prediction accuracy of 1/2+ϵ1/2+\epsilon, but allow prediction labels of neighboring vertices to be dependent. We introduce a parameter bb, allowing each vertex’s prediction label to depend on those of at most bb neighbors. Formally, we select a subset F⊆EF\subseteq E of the original graph’s edges to indicate where dependencies are permitted, with each vertex incident to at most bb such edges. For any two disjoint vertex sets with no edge of FF between them, their prediction-label vectors are required to be independent. When b=0b=0, this reduces to our original independent prediction model.

Under this model, the expected neighborhood score remains 2ϵt(v)2\epsilon t(v). Using a concentration inequality for bounded dependencies, the uniform score deviation bound increases by a factor of at most b+1\sqrt{b+1}. Consequently, the original algorithm achieves an approximation ratio of

k, 1+\frac{\sqrt{(b+1)\Delta\log(n/\delta)}}{\epsilon}, n^{1/4+\eta} \right\rbrace\right)$$ with probability at least $1-\delta$. The algorithm remains unchanged and requires neither $\epsilon$ nor $b$. Its query complexity and running time are also unchanged. In particular, for $b=O(1)$, the approximation ratio is the same as under independent predictions. Our algorithm also applies to $t$-wise independent prediction labels, which means any set of at most $t$ labels is mutually independent, while larger sets need not be. If each vertex’s prediction is still correct with probability $1/2+\epsilon$ and $t\ge C\log(2n/\delta)$ for a sufficiently large absolute constant $C$, the algorithm achieves the same asymptotic approximation guarantee as when all prediction labels are mutually independent. ### 3. Technical contributions. Our technical contributions include both the approximation algorithm and the hardness proofs under persistent predictions. There are very few results on the hardness of approximaiton when the algorithm is given the prediction, due to the lack of the techqniues. Existing results include hardness bounds for CSPs with advice (Ghoshal et al., 2025). Our work provides a prediction-removal framework for proving lower bounds in LAA, which may also be useful for other problems. The proofs must simulate predictions without knowing an optimum. Building on the graph-product framework of Manurangsi et al. (2021), we use simulated labels and repeated runs for the $k$-dependent bound, and a mixture over optimal targets for the $n$-dependent bound to avoid exponential repetition. We also extend the soundness analysis using sparse witnesses.

Thank you so much for your response to my questions. I am still not convinced that the technical depth is in the level of this conference, so I'll keep my current score.

Reviewer_DBMCOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies learning-augmented algorithms for Densest kk-Subgraph under noisy predictions of membership in a fixed optimal solution. Its main algorithm combines neighborhood scoring, greedy completion, and prediction-free fallbacks to achieve an Oη(min⁡(k,1+Δlog⁡n/ϵ,n1/4+η))O_\eta(\min(k,1+\sqrt{\Delta\log n}/\epsilon,n^{1/4+\eta}))-approximation without knowing the prediction accuracy. Under the Strongish Planted Clique Hypothesis, it also establishes approximation hardness despite persistent vertex predictions. Additional results address fresh vertex queries and edge predictions, while experiments evaluate the algorithms using simulated predictions on real and synthetic graphs.

Critical strengths
  1. I like the simplicity of the prediction-guided greedy construction. It uses neighborhood predictions to select an initial set, then greedily completes that set with vertices having the most connections to it. Reserving space for the completion is important, since high-scoring vertices need not induce many edges themselves. The resulting guarantee improves on the matching and general BCCFV guarantees when Δ\Delta is sufficiently small and kk sufficiently large, without requiring knowledge of the prediction accuracy.

  2. I find the prediction-removal argument for the nn-dependent lower bound particularly interesting. The reduction cannot generate genuine predictions directly because it does not know an optimum. The authors address this by constructing YES instances with many optimal solutions and showing that genuine predictions averaged over these solutions are statistically close to easily simulated, uninformative labels. Since the algorithm must succeed for every fixed optimum, its guarantee carries over to this mixture and then, with only a small loss in success probability, to the simulated labels. This avoids the exponential repetition cost used in the kk-dependent lower bound. The argument helps clarify the limits of what persistent predictions can offer for approximating Densest kk-Subgraph.

Critical weaknesses
  1. My main concern is the restrictive prediction model and its practical motivation. Although the persistent Vertex Prediction Model has precedents in the literature, it assumes that, conditional on a fixed optimum, every vertex’s membership label is independently correct with exactly the same probability 1/2+ϵ1/2+\epsilon. It is unclear how predictions learned from historical data would satisfy these conditions. The experiments use simulated labels with the prescribed noise distribution, so they demonstrate that the algorithm can exploit such predictions but do not establish whether realistic predictors provide comparable benefits. This limits the evidence for the practical applicability of the results.

    Although the exact correctness probability is stated in the model definition, I believe its importance to the upper bound should be emphasized earlier in the main text. The analysis relies on exact calibration and does not automatically extend to predictions that are correct with probability at least 1/2+ϵ1/2+\epsilon. This limitation is discussed in Appendix C, Remark 12, but is important enough for interpreting the result that it deserves explicit discussion in the main text.

Questions for authors

N/A

2 comments

Thank you for the careful review and for recognizing our algorithmic and hardness results.

1. Prediction model and experiments.

We agree that predictors learned from historical data may not satisfy our assumptions: their errors can be correlated, and their accuracy can differ across vertices. We use simulated labels in our experiments so that we can vary prediction accuracy and compare the algorithm with prediction-free baselines. We view this work as a first step toward understanding the role of predictions in approximation algorithms design. We leave the study of more realistic prediction models to future work.

2. Exact calibration.

As suggested, we will add the discussion from Appendix C, Remark 12 to the main text after Definition 3. We will explicitly state that the upper bound requires correctness probability exactly 1/2+ϵ1/2+\epsilon, rather than merely at least 1/2+ϵ1/2+\epsilon.

Thank you for the responses and revisions. I will maintain my score.

Reviewer_W7RnOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies learning-augmented approximation algorithms for Densest k-Subgraph under noisy membership predictions. It gives guarantees for persistent vertex predictions, including an unknown-accuracy variant, establishes conditional hardness under the Strongish Planted Clique Hypothesis, and studies non-persistent vertex and edge predictions.

Critical strengths

Strengths:

  1. The learning-augmented Densest k-subgraph problem has wide impacts in machine learning and algorithms, and their implications in community detection and network analysis.

  2. The proposed algorithm appears to work using fast polynomial run-time, providing an improved approximation factor by combining three ingredients.

Critical weaknesses

Weaknesses:

  1. The presentation of this paper needs to greatly enhanced before it can be published. I spent quite a few hours reading the descriptions on the algorithms, trying to understand the main ideas. The current writing assumes many prior knowledge on the studied problem and can be very hard for readers with only general algorithm background to follow. Textual descriptions should be accompanied with math definitions to explain the motivations/intuitions. This is the biggest concern for me to recommend it to the ICLR.

  2. The hardness results follow the prior work (Manurangsi et al., 2021) and the authors indicate that they “used AI to assist with parameter selection and the derivation of specific proof steps”. The credit to the authors is therefore lower.

  3. The oracle assumptions limit practical conclusions. The guarantees and experiments assume independent errors with homogeneous, exactly calibrated accuracy. Not requiring ϵ\epsilon as input does not relax these assumptions. Synthetic labels from fixed targets offer limited evidence about learned predictors; correlated errors, heterogeneous accuracy, and misspecified ϵ\epsilon remain untested. The unknown-accuracy variant is also not evaluated. The edge model can supply multiple independent membership observations to a vertex through incident edges, which should be acknowledged when interpreting its stronger guarantee.

Questions for authors

Please see the weaknesses above.

1 comment

Thank you for the careful reading and specific suggestions. We address the three main concerns below.

1. Presentation and algorithmic intuition.

We have revised Section 4 to add a high-level description of the algorithm before the formal definitions. We query each vertex label once and use neighboring labels to score how strongly each vertex connects to the unknown optimum. For each 1≤h≤k1\le h\le k, we take the hh highest-scoring vertices and complete them with the k−hk-h outside vertices having the most neighbors in that initial set. We choose hh by maximizing a computable lower bound Q(h)Q(h) on the resulting edge count, while also retaining the candidate with h=k/2h=k/2, which underlies our approximation guarantee. Finally, we return the densest among these prediction-guided candidates and two prediction-free candidates obtained from a maximal matching and BCCFV.

We note that the score estimates how many neighbors a vertex has in S⋆S^\star, not whether the vertex itself belongs to S⋆S^\star. Thus, high-scoring vertices may have few edges among themselves (e.g., vertices on one side of a bipartite graph). The completion step selects vertices adjacent to the initial set, turning these connections into induced edges. Choosing h=k/2h=k/2 reserves half of the kk positions for this step.

In Section 4.1, we add explanations alongside the mathematical definitions: what the neighborhood scores estimate, how completion uses the known graph edges, why we consider different initial set sizes, and the roles of the matching and BCCFV candidates.

2. Hardness contributions beyond prior work.

There are very few results on the hardness of approximaiton when the algorithm is given the prediction, due to the lack of the techqniues. Existing results include hardness bounds for CSPs with advice (Ghoshal et al., 2025). Our work provides a prediction-removal framework for proving lower bounds in LAA, which may also be useful for other problems.

The proofs must simulate predictions without knowing an optimum. Building on the graph-product framework of Manurangsi et al. (2021), we use simulated labels and repeated runs for the kk-dependent bound, and a mixture over optimal targets for the nn-dependent bound to avoid exponential repetition. We also extend the soundness analysis using sparse witnesses.

3.Relaxing the independence assumption and experiments with unknown ϵ\epsilon.

We relax the assumption of independent prediction errors in the new Appendix G. Each vertex’s prediction may depend on those of at most bb neighbors. The uniform score-error bound increases by at most a factor of b+1\sqrt{b+1}, and the prediction-dependent approximation term becomes O(1+(b+1)Δlog⁡(2n/δ)ϵ).O\left(1+\frac{\sqrt{(b+1)\Delta\log(2n/\delta)}}{\epsilon}\right). The algorithm remains unchanged and requires neither bb nor ϵ\epsilon. For b=O(1)b=O(1), the asymptotic approximation ratio is unchanged. This extension retains homogeneous, exactly calibrated marginal accuracy, whose role is now discussed after Definition 3.

Our algorithm also applies to tt-wise independent prediction labels, which means any set of at most tt labels is mutually independent, while larger sets need not be. If each vertex’s prediction is still correct with probability 1/2+ϵ1/2+\epsilon and t≥Clog⁡(2n/δ)t\ge C\log(2n/\delta) for a sufficiently large absolute constant CC, the algorithm achieves the same asymptotic approximation guarantee as when all prediction labels are mutually independent.

We have replaced the experiments with the version that does not receive ϵ\epsilon, updating Section 6 and Appendix F. All 31 crossover thresholds and the main experimental conclusions remain unchanged. These experiments still use simulated labels from fixed targets.

Finally, the Edge Prediction Model can provide multiple independent membership observations of the same vertex through incident edges. We acknowledge this distinction: its stronger guarantee should be interpreted in light of this additional information.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.