- 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 vertices in the given graph that have a maximum number of edges between them. The best known approximation ratio is for a fixed constant with running time of . On the hardness side, randomized gap-ETH rules out -approx and ETH rules out -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 . Note that 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 and it returns two labels for and . 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 can gives information about 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) -approx for persistent vertex model
(2) -approx for non persistent vertex model
(3) -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 and 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 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.
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∣+nlogn) time using at most ∣E∣ edge queries. In particular, the running time and edge-query complexity are independent of both ϵ and δ. 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, ϵ and δ do not introduce repeated sampling. Aggregating predictions, scoring, and finding a maximal matching take O(∣E∣+n) time; sorting takes O(nlogn) 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+ϵ, but allow prediction labels of neighboring vertices to be dependent. We introduce a parameter b, allowing each vertex’s prediction label to depend on those of at most b neighbors. Formally, we select a subset F⊆E of the original graph’s edges to indicate where dependencies are permitted, with each vertex incident to at most b such edges. For any two disjoint vertex sets with no edge of F between them, their prediction-label vectors are required to be independent. When b=0, this reduces to our original independent prediction model.
Under this model, the expected neighborhood score remains 2ϵt(v). Using a concentration inequality for bounded dependencies, the uniform score deviation bound increases by a factor of at most 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.