{"id":"81951695-d95d-4d2a-98a4-8c7cf7c23f21","arxiv_id":"2506.13533","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper gives a learning-augmented k-clustering algorithm for general metric (graph) spaces and an ETH-based query-complexity lower bound, though the lower-bound proof contains an arithmetic gap.","lead":"This paper designs clustering algorithms that use a learned predictor's labels to cluster graph data, for both sum-of-distances and squared-distance costs. It also claims a mathematical limit on how few label queries such algorithms can make, based on the assumption that the Exponential Time Hypothesis holds.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.4's equation (8) drops a coefficient-1 term on cost(P*\\P, C_{P∩P*}), so the q=2 case of Theorem 3.1 is unproven as written.","rationale":"The reader's conditional verdict is directionally appropriate, but their stated weakest assumption (NP-hardness of the subset argmin) does not land: min over S of cost(S,C_S) can be rewritten as min over centers c of the sum of the (1−α)|X| smallest distances from c, which is polynomial by enumerating centers. The genuine load-bearing defect is in Lemma 3.4: equation (8) is not a consequence of (6) and (7). The coefficient of cost(P*\\P, C_{P∩P*}) is reduced from at least 1 to about 2√α, so the proof omits a first-order term that can be as large as OPT when an α-fraction of points is far away. This directly undermines the q=2 case of Theorem 3.1, the paper's central algorithmic claim. Because the error appears fixable with a correct coefficient accounting or a different argument, I would keep the manuscript conditional rather than reject outright. The query-complexity section also contains an unproved simulation-equality, reinforcing the need for revision before acceptance.","tokens_in":12572,"tokens_out":38537,"duration_ms":348810,"concrete_test":"Re-derive equation (8) coefficient-wise from (6) and (7). Isolate all terms containing cost(P*\\P, C_{P∩P*}): from (7) their coefficient is 1+2√(α(1−α)/(1−2α)), whereas (8) gives them coefficient G2≈2√α. Since G2<1 for small α, (8) fails. Numerical check: use a path metric with 499 vertices at distance 0 from each other, 500 at distance 100, and 1 vertex at distance 10^6; set q=2, k=1, α=0.001. Then cost(P*, C_B) ~ 10^12, while the right-hand side of (8) is roughly 7×10^10, so the inequality is false. Fixing the coefficient accounting would determine whether the claimed (1+O(√α)) bound can still be recovered.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The q=2 half of Theorem 3.1 rests on Lemma 3.4. In the proof, inequalities (6) and (7) are summed. The term cost(P*\\P, C_{P∩P*}) appears in (7) with coefficient 1+2√(α(1−α)/(1−2α)), which is at least 1. Equation (8) instead places this term in the last grouped bracket, where its coefficient becomes G2 = (1+k1√α)(√(α/(1−α)) + 2α/(1−α)) + √(α(1−α)/(1−2α)) + 2α(1−α)/(1−2α). For small α, G2 ≈ 2√α, which is below 1. Thus (8) is not a valid upper bound: it can discard nearly all of a nonnegative term that the left-hand side contains. This is not a loose-constant issue. In a metric with (1−α)|P*| points near 0/100 and an α-fraction of points at distance L, the excluded-point cost can be comparable to OPT, while (8) captures only a G2 fraction of it. Since Lemma 3.4 is the sole support for the q=2 case, the main approximation theorem is not established by the written proof. The reader's concern about NP-hardness of the subset argmin is not the real obstruction: minimizing over S is equivalent to choosing the (1−α)|X| closest points to some center, so enumerating centers solves Algorithm 2 in polynomial time.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies learning-augmented k-clustering in general metric graphs. It proposes Algorithm 1, which uses predictor labels and a subroutine GetCenter that returns the metric median of the predicted cluster for q=1 and the center of a minimum-cost (1−α)-subset for q=2, and claims a (1+O(α^{1/q}))-approximation. The paper also claims an ETH-based lower bound on the number of label queries needed by any polynomial-time (1+O(α^{1/q}))-approximation algorithm. The q=1 proof is largely sound, but the q=2 proof of the main theorem and the query-complexity lower-bound proof contain load-bearing gaps.","tokens_in":12900,"tokens_out":15102,"duration_ms":122746,"significance":"If the main theorem were correct, the contribution would be useful: it extends learning-augmented clustering from Euclidean spaces to arbitrary metric graphs, removes minimum-cluster-size assumptions, and replaces the Euclidean centroid identity with a triangle-inequality argument that is a natural and potentially reusable idea. The q=1 side and the overall problem formulation are clean, and the lower-bound reduction from vertex cover is a plausible route to strengthen known query-complexity results. However, the manuscript as written does not establish the q=2 case of the main theorem or the query-complexity lower bound.","major_comments":[{"comment":"The summation of inequalities (6) and (7) does not imply (8). In (7), the term cost(P*\\P, C_{P∩P*}) appears with coefficient at least 1+2√(α(1−α)/(1−2α)), which is at least 1. In (8), this term is moved into the last bracket, whose coefficient is (1+k1√α)(√(α/(1−α)) + 2α/(1−α)) + √(α(1−α)/(1−2α)) + 2α(1−α)/(1−2α), which is O(√α) for small α and is below 1. The proof therefore discards part of a nonnegative summand that can be comparable to OPT (for instance, when an α-fraction of P* lies far from C_{P∩P*}). Since (8) is the key bound leading to cost(P*,C_B) ≤ (1+45√α) cost(P*,C_{P*}), Lemma 3.4 is not established, and the q=2 case of Theorem 3.1 is not proven as written.","section":"Section 3.1, Lemma 3.4, Eq. (8)"},{"comment":"The pseudocode of GetCenter for q=2 is inconsistent with the proof of Lemma 3.4. Line 4 computes S over subsets of V(G) of size (1−α)|V(G)|, independent of the input X. With this statement, GetCenter ignores the predictor's cluster and returns the same center for every cluster label i, so Theorem 3.1 does not follow from the stated algorithm. The proof requires B to be a subset of the predictor's cluster P of size (1−α)|P|, so line 4 should read S ← argmin_{S⊂X, |S|=(1−α)|X|} cost(S,C_S). This is a load-bearing correctness issue for the q=2 half of the main theorem.","section":"Algorithm 2, line 4"},{"comment":"The proof of Lemma 3.4 uses a lower bound on |R| that is not justified. From the preceding facts one gets |R| ≥ (1−2α)|P| by intersecting two subsets of P of size at least (1−α)|P|, and hence |R1|/|R| ≤ α/(1−2α). The proof instead claims |R| ≥ (1−2α)/(1−α)|P*| and then uses √(|R1|/|R|) ≤ √(α/(1−α)) and |R1|/|R| ≤ 2α/(1−α) in (6), which are stronger than what the given assumptions imply. This is an additional gap in the q=2 proof and must be repaired together with the algebra in (8).","section":"Section 3.1, Lemma 3.4, bound on |R| and |R1|/|R|"},{"comment":"The query-complexity statement and proof have load-bearing inconsistencies. The abstract claims that any polynomial-time algorithm must make approximately Ω(k/α) queries, while Theorem 4.5 states impossibility for algorithms making at most O(k^{1−δ} log k) queries and omits the factor 1/α; these are not compatible, and prior work is cited with a bound containing 1/α. In the proof, the simulation step asserts k^{O(k^{1−δ} log k)} = O(2^{k^{1−δ}}), but actually k^{O(k^{1−δ} log k)} = 2^{O(k^{1−δ} log^2 k)}. Since k=Θ(n), this exponent is larger than n^{1−δ} by a log^2 k factor, so the simulation cannot be performed within the assumed running time O(2^{n^{1−δ}}). The contradiction argument therefore does not go through.","section":"Section 4, Theorem 4.5 and its proof"},{"comment":"The soundness lemma is asserted in a single sentence that cites 'the proof of Lemma 5 from Lee et al. [2017]' and notes that the special node contributes nonnegative cost. Since Lemma 4.4 is the crux of the hardness-of-approximation gap and the reduction is not standard in this exact form, the proof needs to be supplied explicitly, including the calculation that the gap (αmax−αmin)/3 survives in the constructed graph G''.","section":"Section 4, Lemma 4.4"}],"minor_comments":[{"comment":"There is a typo in 'simultaneouly' in the introduction; it should read 'simultaneously'.","section":"Introduction"},{"comment":"Algorithm 1's Ensure clause states '(1+O(α))-approximate k-means clustering', whereas Theorem 3.1 claims (1+O(α^{1/q}))-approximation; for q=2 this would be (1+O(√α)). The statements should be made consistent.","section":"Theorem 3.1 and Algorithm 1"},{"comment":"Theorem 3.1 states α ∈ (0,1/2), but Lemma 3.2 only proves the q=2 case for α < 1/8. The proof of Theorem 3.1 should either use the same threshold or justify why the larger range is valid.","section":"Lemma 3.2 and Theorem 3.1"},{"comment":"The term 'semi-ball' is introduced informally after Lemma 3.3, but Lemma 3.4 uses B as an arbitrary cost-minimizing subset, not as a geometric ball B(x,r). The notation should be clarified so that B is not confused with the earlier ball notation B(x,r).","section":"Section 3.1, semi-ball definition"},{"comment":"In the last paragraph of the proof of Lemma 4.2, the expression 'cost(CX)' should read 'cost(X,C_X)' for consistency with the definitions.","section":"Lemma 4.2"}],"recommendation":"major_revision","confidential_remarks":"The paper reads like a conference extended abstract that needs substantial technical repair. The q=2 proof of the main theorem has a clear coefficient error, and the query-complexity lower-bound proof has an invalid simulation step. I would ask the authors for a complete corrected proof of Lemma 3.4 and a corrected statement and proof of Theorem 4.5 before considering acceptance; if the algebra in Lemma 3.4 cannot be repaired, the q=2 claim should be withdrawn or substantially revised."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know three things about arXiv:2506.13533. First, the q=1 side of Theorem 3.1 is a clean, correct extension of learning-augmented k-clustering to general metrics: Lemma 3.3 uses only the triangle inequality and gives the claimed (1+O(α))-approximation. Second, the q=2 side is not established by the written proof. In Lemma 3.4, equation (8) does not follow from summing (6) and (7). The term cost(P*\\P, C_{P∩P*}) carries a coefficient of at least 1 from (7), but in (8) it is grouped with coefficient G2 ≈ 2√α < 1, which can drop a nonnegative term comparable to OPT. That is a load-bearing flaw, not a loose constant. Third, the query lower bound proof contains a plainly false equality: k^{O(k^{1−δ} log k)} is not O(2^{k^{1−δ}}); the left side has log^2 k in the exponent, so the ETH simulation step does not close. The abstract also claims Ω(k/α) queries, but the theorem states at most O(k^{1−δ} log k) queries, which is a mismatch worth fixing.\n\nWhat is genuinely new: the semi-ball based center estimation is a sensible replacement for Euclidean centroid computation, and removing the minimum cluster size constraint is a real advance. The reader's worry about the subset argmin in Algorithm 2 is not the real obstruction: minimizing over S of size (1−α)|X| for a fixed center is just choosing the closest points, so enumerating centers gives a polynomial-time algorithm. However, the pseudocode says S ⊂ V(G) rather than S ⊂ X, which is a minor inconsistency with the proof.\n\nThese issues are specific and likely fixable. The q=1 result is likely correct, and the q=2 proof probably can be repaired with a more careful coefficient bookkeeping. The lower bound may also be salvageable, though as written the ETH argument fails. The paper is worth referee time, but it is not ready in its current form. I would send it to peer review and ask for a major revision that fixes the coefficient error, corrects the simulation bound, and aligns the abstract with the theorem statement.","headline":"The q=2 half of the main theorem is unproven as written due to a coefficient error in Lemma 3.4, and the query lower bound proof has an arithmetic flaw, but the q=1 result is solid and the paper deserves a careful referee.","tokens_in":13380,"tokens_out":7874,"would_cite":false,"duration_ms":63096,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"Learning-augmented k-clustering can operate in any metric space, including graphs, with approximation error that vanishes as the predictor's label error goes to zero.","keywords":["learning-augmented algorithms","k-clustering","general metric spaces","graph clustering","k-median","k-means","query complexity","approximation algorithms"],"falsifier":"A concrete check would be to enumerate all small weighted graphs with planted optimal clusters, run the predictor with label error $\\alpha<1/8$, and compare the cost of the center returned by Algorithm 2, computed by exhaustive search over every $(1-\\alpha)$-subset, against $(1+45\\sqrt{\\alpha})\\cdot \\mathrm{OPT}$. Any instance exceeding that ratio would falsify Lemma 3.4, and showing that finding the required argmin subset is NP-hard would falsify the polynomial-time claim of Theorem 3.1.","tokens_in":12384,"feed_emoji":"🕸️","tokens_out":12940,"duration_ms":113711,"temperature":0.7,"pith_summary":"This paper tries to show that learning-augmented k-clustering, using a predictor that supplies noisy cluster labels, can be made to work in any metric space rather than only in Euclidean space, and without assuming each cluster has a minimum size. For costs that sum distances raised to the first or second power, it proves that a simple center-estimation rule gives a $(1+O(\\alpha^{1/q}))$-approximation whenever the predictor's label error rate is below $\\alpha<1/2$. It also claims an ETH-based lower bound showing that, in general metrics, any fast algorithm needs many true-label queries, so the predictor cannot be queried too sparingly. If these results hold, learning-augmented clustering becomes applicable to graph-structured and non-Euclidean data.","feed_headline":"Noisy labels can guide k-clustering on any graph metric","feed_subtitle":"General-metric proof replaces Euclidean centroids with a trimmed center inside each predicted cluster.","key_machinery":"The load-bearing object is the estimated center produced by Algorithm 2. For $q=1$ it is simply $C_X$, the metric center of the predictor-labeled set $X$; for $q=2$ it is $C_S$, where $S$ is the subset of $X$ of size $(1-\\alpha)|X|$ with minimum clustering cost, called a semi-ball because it may include only some points at the boundary radius rather than a full geometric ball. The argument runs on a metric analogue of the Euclidean centroid identity: instead of an exact decomposition, the paper uses the triangle inequality to show that the cost error caused by replacing the true center with an estimated center at distance $D$ is bounded by terms proportional to $D$ times the number of outliers and, for squares, to $D^2$. That inequality is what transfers the old Euclidean proof to graphs.","core_discovery":"The central claim, stated as Theorem 3.1, is that for the k-clustering problem with $\\ell_q$ cost ($q=1,2$) over a general metric space, a predictor with label error rate $\\lambda\\le\\alpha<1/2$ suffices for Algorithm 1 to output a $(1+O(\\alpha^{1/q}))$-approximation in polynomial time. The proof replaces the Euclidean identity $\\mathrm{cost}(X,c)=\\mathrm{cost}(X,C_X)+|X|\\|c-C_X\\|^2$ with a triangle-inequality bound in which the distance $D$ between the true center and the estimated center is charged against the cost of a $(1-\\alpha)$-majority subset. For squared-distance cost, the algorithm does not use the raw predictor center; it first discards outliers by selecting the cheapest $(1-\\alpha)$-fraction of the predicted cluster, which the paper calls a semi-ball, and uses that subset's center. The paper also claims that the same hardness phenomenon as in Euclidean space carries over: under ETH, a $(1+O(\\alpha^{1/q}))$-approximation is impossible in subexponential time with only a sublinear number of label queries.","pith_inferences":["Beyond the paper, the semi-ball center estimator is a trimmed estimator in the metric space; it would be natural to test whether simpler outlier filters, such as pruning by eccentricity or distance from the raw center, preserve the same $O(\\alpha^{1/q})$ rate while avoiding the subset-search step.","The query lower bound is worst-case over instances; on structured graphs such as trees or low-treewidth graphs, a stronger upper bound on the number of useful queries may exist.","If the argmin subset in Algorithm 2 turns out not to be polynomially computable in general, an approximate version of the densest-subset step could still yield a $(1+O(\\sqrt{\\alpha}))$-approximation with extra computational effort; the paper does not address this."],"forward_implications":["Learning-augmented k-means and k-median can be applied to shortest-path distances on weighted graphs, so social, biological, and recommendation networks become legitimate inputs for the predictor model.","The removal of minimum-cluster-size constraints means the same guarantees cover imbalanced clusters whose true sizes are unknown in advance.","The approximation ratio improves continuously with predictor quality: as $\\alpha\\to 0$, the ratio tends to $1$ at rate $\\alpha$ for $q=1$ and $\\sqrt{\\alpha}$ for $q=2$.","The ETH-based lower bound indicates that, in the worst case, an algorithm making only $O(k^{1-\\delta}\\log k)$ label queries cannot match the full-information guarantee, so label access is a real bottleneck in general metrics."],"supporting_citations":[{"why":"Establishes the learning-augmented k-means setup, the predictor model with label error rate, and the query-complexity framework that this paper generalizes to general metrics.","marker":"[Ergun et al., 2022]"},{"why":"Supplies the reduction from vertex cover on 4-regular graphs used to construct the hard k-clustering instances for both lower bounds.","marker":"[Lee et al., 2017]"},{"why":"Gives the APX-hardness threshold for vertex cover on bounded-degree graphs that sets the constants $\\alpha_{\\min}$ and $\\alpha_{\\max}$ in the query-complexity proof.","marker":"[Chlebík and Chlebíková, 2006]"},{"why":"Contributes the hardness-of-approximation result for k-means that the line-graph construction leans on.","marker":"[Awasthi et al., 2015]"},{"why":"Proposes approximate cluster recovery from noisy labels, an earlier learning-augmented method restricted to Euclidean space that this paper extends.","marker":"[Gamlath et al., 2022]"},{"why":"Removes minimum-cluster-size constraints in the Euclidean case using coordinate-wise subset selection, which the paper contrasts with its full-space subset estimator.","marker":"[Nguyen et al., 2023]"},{"why":"Provides the Euclidean centroid identity whose failure in general metrics motivates the paper's triangle-inequality cost bound.","marker":"[Inaba et al., 1994]"}],"fun_headline_variants":["General-metric k-clustering with noisy label guide","Noisy labels suffice for near-optimal graph clustering","Label errors tolerated in general-metric k-clustering","Extending learning-augmented clustering to graph metrics","Graph k-clustering benefits from imperfect labels"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole guarantee rests on being able to find, in polynomial time, the subset of each predicted cluster that has size $(1-\\alpha)$ and the smallest total distance to its own best center; the paper states this subset as an argmin but does not show how to compute it.","fun_headline_variants_meta":{"raw":{"variants":["General-metric k-clustering with noisy label guide","Noisy labels suffice for near-optimal graph clustering","Label errors tolerated in general-metric k-clustering","Extending learning-augmented clustering to graph metrics","Graph k-clustering benefits from imperfect labels"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000281,"raw_usage":{"total_tokens":1654,"prompt_tokens":928,"completion_tokens":726,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":544,"completion_tokens_details":{"reasoning_tokens":652}},"tokens_in":544,"tokens_out":726,"duration_ms":6929,"temperature":1.0,"reasoning_tokens":652,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:59:49.344825+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete check would be to enumerate all small weighted graphs with planted optimal clusters, run the predictor with label error $\\alpha<1/8$, and compare the cost of the center returned by Algorithm 2, computed by exhaustive search over every $(1-\\alpha)$-subset, against $(1+45\\sqrt{\\alpha})\\cdot \\mathrm{OPT}$. Any instance exceeding that ratio would falsify Lemma 3.4, and showing that finding the required argmin subset is NP-hard would falsify the polynomial-time claim of Theorem 3.1.","supporting_citations":[],"review_version":2}