{"id":"dc215496-4317-4d3e-8ac4-f2586ace68ac","arxiv_id":"1908.04976","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Exact optimal correlation clustering is recoverable with at most 2*COPT same-cluster queries, and a 2-approximation with at most COPT queries; a Gap-ETH lower bound rules out o(COPT)-query (1+alpha)-approximations.","lead":"This paper gives algorithms for correlation clustering that ask a same-cluster oracle at most twice the optimal number of disagreements, COPT, to recover an exact optimal clustering, and at most COPT queries to get a 2-approximation. It also proves a conditional lower bound showing o(COPT) queries cannot yield near-optimal approximations under Gap-ETH.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lower-bound reduction's key structural claim is false: 4-cycle gadgets give non-neighbor +-neighborhood intersections of size 2, so Lemma 7.1 cannot justify the 10m lower bound.","rationale":"The reader's verdict was CONDITIONAL, and my analysis supports keeping a conditional verdict, so the overall disposition is unchanged. However, the most load-bearing concern I identify is not the oracle-noise assumption (which is an explicit modeling assumption, not an internal gap) but a concrete false statement in the lower-bound proof. The reduction's variable gadgets are cycles of length 4c(x); when c(x)=1 this is a 4-cycle, and in a 4-cycle the +-neighborhoods of opposite vertices intersect in two vertices. This directly contradicts the proof's assertion that every non-+ edge has +-neighborhood intersection of size at most 1. That assertion is the sole justification for applying Lemma 7.1 and concluding that an optimal solution makes mistakes only on + edges. Since the entire lower-bound argument (Lemma 5.1, Theorem 5.1) depends on this structural claim, the advertised optimality within a factor of 2 is not established. This is distinct from the reader's listed issues (pseudocode typo, terse charging, notation shifts), though it is consistent with the reader's call for corrections. If the lower-bound proof cannot be repaired, the paper's main positive results (exact recovery with 2COPT queries, 2-approximation with COPT expected queries) remain potentially correct, but the 'optimal query bound' claim would need to be retracted or weakened. The concrete test of enumerating the smallest gadget instance and comparing optimal solutions quickly settles whether the flaw is merely a proof gap or indicates a real failure of the reduction.","tokens_in":23862,"tokens_out":21997,"duration_ms":210725,"concrete_test":"Build the smallest reduction instance: a single variable x with c(x)=1 (so 4 vertices forming a + cycle) plus one clause vertex and its gadget edges. Verify that the + edges form a 4-cycle and that N^+(1) ∩ N^+(3) = {2,4}, contradicting the paper's claim. Then re-solve the correlation clustering instance exactly (e.g., via brute force or ILP) and check whether the optimal cost is 10m and whether there exists an optimal solution with mistakes only on + edges. If an optimal solution with - mistakes has cost below 10m, the lower bound as stated collapses; if the optimal cost is still 10m, attempt to repair the proof by showing directly that an optimal solution can be taken without - mistakes.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The lower-bound proof (Section 5, Appendix 7.2) relies on Lemma 7.1 to assert that there exists an optimal clustering with mistakes only on + edges. The proof of Lemma 5.1 states: 'Since for any two vertices that are not +-neighbors the intersection of their +-neighborhoods is of size at most 1, it follows from Lemma 7.1...'. This is false for the constructed graph. For any variable x with c(x)=1, the variable gadget is a cycle of 4 vertices with + edges (1,2),(2,3),(3,4),(4,1). The vertices 1 and 3 are not +-neighbors (edge (1,3) is -), yet N^+(1) = {2,4} and N^+(3) = {2,4}, so their +-neighborhood intersection has size 2. The same holds for vertices 2 and 4. Thus the condition of Lemma 7.1 (|N^+(u) ∩ N^+(v)| ≤ 1 for every - edge) is not satisfied, so the lemma cannot be applied. Without Lemma 7.1, the proof's conclusion that an optimal solution can be assumed to make no mistakes on - edges is unsupported; the subsequent cost calculation (COPT ≥ 10m) and the characterization of optimal solutions as deleting all even or all odd + edges in each variable cycle may fail. Consequently, the claimed query-complexity lower bound of Theorem 5.1, and the headline 'optimal query bound within a factor of 2', are not proven as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies correlation clustering in the same-cluster query model, where an oracle answers whether two vertices belong to the same cluster in an optimal solution. The main theoretical claims are: (i) a deterministic algorithm QUERY PIVOT that recovers an exact optimal clustering using at most 2COPT queries, where COPT is the number of disagreements of the optimal clustering; (ii) a randomized algorithm RANDOM QUERY PIVOT that achieves an expected 2-approximation using at most COPT expected queries; and (iii) a Gap-ETH-based lower bound stating that no polynomial-time algorithm can achieve (1+alpha)-approximation with o(COPT) queries for some constant alpha>0. The paper also reports extensive experiments on synthetic and real-world datasets, including crowd-sourced oracles, comparing against several non-query baselines and a branching algorithm of Bocker et al.","tokens_in":24169,"tokens_out":11524,"duration_ms":106106,"significance":"If correct, the upper-bound results are significant: they give simple, COPT-parameterized query bounds that do not depend on the number of clusters, improving on the k-parameterized bound of Ailon et al., and the exact-recovery bound of 2COPT queries is clean. The experimental section is a strength: it includes real crowd oracles, several real datasets, and a comparison with multiple baselines; the code and data are provided. The lower bound, if correct, would establish near-optimality of the query bound. However, the lower-bound proof as printed contains a false claim about the constructed graph, so the optimality claim is not currently established. The algorithmic upper bounds are interesting in their own right, but the advertised 'optimal query bound within a factor of 2' rests on the unproven lower bound.","major_comments":[{"comment":"The lower-bound reduction is not valid as written. In the proof of Lemma 5.1, it is claimed that 'for any two vertices that are not +-neighbors the intersection of their +-neighborhoods is of size at most 1', and on that basis Lemma 7.1 is invoked to assert the existence of an optimal solution making mistakes only on + edges. This is false for the constructed graph. For a variable x with c(x)=1, the variable gadget is a cycle of four vertices with + edges (1,2),(2,3),(3,4),(4,1). Vertices 1 and 3 are not +-neighbors, yet N^+(1)={2,4} and N^+(3)={2,4}, so the intersection has size 2; the same holds for 2 and 4. Hence the hypothesis of Lemma 7.1 is not satisfied and the lemma cannot be applied. Consequently, the conclusion that an optimal solution may be assumed to make no mistakes on - edges is unsupported, and the subsequent lower bound COPT >= 10m and the characterization of optimal solutions as deleting all even or all odd + edges in each variable cycle do not follow. Theorem 5.1 and the paper's claim of an 'optimal query bound within a factor of 2' are therefore not proven as written. The authors should repair the construction (e.g., avoid 4-cycles) or provide a direct proof that an optimal solution makes mistakes only on + edges in this graph.","section":"§5, Appendix 7.2 (Lemma 7.1, proof of Lemma 5.1)"},{"comment":"The pseudocode of RANDOM QUERY PIVOT does not match the prose description. In lines 16-22, when the oracle reports a mistake on {pivot,w} at line 20, line 21 sets Mistake[v]<-1 instead of Mistake[w]<-1. Moreover, the comment on line 11 states 'Without loss of generality, suppose that {pivot,v} is a + edge', but the loop over T does not reorder v and w for triangles where {pivot,w} is the + edge and {pivot,v} is the - edge. The pseudocode therefore queries the - edge first in such triangles, contrary to the prose and to the analysis in Lemmas 4.3 and 4.4. As a result, the theorem statements of Section 4 are proven for an algorithm that is not the one implemented in the pseudocode.","section":"§4, Algorithm 2"},{"comment":"The proof of the query bound of QUERY PIVOT is stated too informally. The claim that 'whenever considering a particular (+,+,-) triangle, if the algorithm makes a query, it makes at most two queries ... and makes at least one mistake that had not been made' is not literally true at the time of the query: if OPT makes exactly one mistake in the triangle and that mistake is on the - edge, then the algorithm queries both + edges and receives 'no mistake' for each; the corresponding output mistake is only made later, when the cluster is formed by including both endpoints of the - edge. A rigorous charging argument, mapping each query to a distinct mistake in the final clustering, is needed. The 2COPT bound may be correct, but the proof as printed does not establish it.","section":"§3, Lemma 3.5"}],"minor_comments":[{"comment":"The table caption and text use 'sqrt' inconsistently with the dataset name 'sqrtn' defined earlier in Section 6; please unify the terminology.","section":"§6, Table 2"},{"comment":"The description of the adaptation of Bocker et al.'s branching algorithm to the same-cluster query setting is very brief; a short explanation of how the branching is interleaved with oracle queries would help readers reproduce the experiments.","section":"§6, Bocker adaptation"},{"comment":"The appendix proof of Lemma 4.3 contains confusing notation: the set Yuv is defined, but the case analysis refers to Suv_2u\\Yuv_u, and the main-text sketch uses symbols like Suv_u and Tuv_u that are not defined there. The notation should be made consistent throughout.","section":"Appendix 7.1"},{"comment":"Reference [21] for the Cora dataset is incomplete (it lists only 'Data.'); please provide the full citation.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The lower-bound flaw is a serious correctness issue for one of the main contributions. The upper-bound results seem plausible and the experiments are valuable, but the advertised optimality claim should be either fixed or substantially qualified. The authors should be asked to correct the reduction or provide a direct structural lemma for the constructed graph, and to fix the pseudocode/formal proof mismatches before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nTwo things to know about this paper. First, the COPT parameterization for same-cluster-query correlation clustering is a genuine step forward: prior work parameterized by the number of clusters k and had query complexity polynomial in k^14, while here the bounds are linear in COPT, which is the more natural parameter when clusters are few and clean. Second, the claim that the query bound is optimal within factor 2 is not proven as written: the lower-bound reduction in Appendix 7.2 relies on a false structural claim.\n\nThe construction creates variable gadgets as cycles of 4c(x) vertices. For any variable appearing in exactly one clause, c(x)=1, so the gadget is a 4-cycle. In that cycle, vertices 1 and 3 are not +-neighbors, but N+(1) = N+(3) = {2,4}, so their +-neighborhood intersection has size 2. The proof asserts \"for any two vertices that are not +-neighbors the intersection of their +-neighborhoods is of size at most 1\" and then applies Lemma 7.1. That assertion is false, and Lemma 7.1's condition is not met. Without Lemma 7.1, the conclusion that an optimal solution makes mistakes only on + edges is unsupported, and the 10m lower bound on COPT collapses. The subsequent characterization of optimal solutions as deleting all even or all odd + edges per cycle may also fail.\n\nWhat the paper does well: the deterministic QUERY PIVOT algorithm is a clean idea — charge queries to the mistakes OPT makes — and the recovery guarantee of at most 2COPT queries, if the proof can be patched, is a real result. The randomized version and the expected 2-approximation are also worth having. The experiments are extensive, including crowd oracles, and the comparison to Bocker et al. is honest. The algorithmic sections are not in bad shape; the main gap is the lower bound.\n\nOther soft spots are smaller: Algorithm 2 has an obvious pseudocode bug (line 21 sets Mistake[v] rather than Mistake[w]), and the query-accounting in Lemma 3.5 is stated informally — it is not true that every triangle with a query yields a new mistake, so the 2COPT bound needs a more careful charging argument. The appendix proof of Lemma 4.3 has notation shifts and some case analyses that are hard to verify.\n\nWho is this for: anyone working on interactive clustering or query-based correlation clustering. The paper deserves a serious referee, but it needs revision: either repair the lower-bound construction (e.g., ensure all variable gadgets have length at least 6, or add a separate argument for 4-cycles) or drop the optimality claim. As it stands, I would not cite the lower bound, and I would be cautious about citing the upper bounds until the proofs are cleaned up. I'd send it back with a request for a corrected lower bound and a pseudocode fix.\n\nBest,\n[You]","headline":"Valuable COPT parameterization and a clean exact-recovery algorithm, but the lower-bound proof has a false structural claim that invalidates the 'optimal within factor 2' headline as written.","tokens_in":24734,"tokens_out":6464,"would_cite":false,"duration_ms":58335,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A same-cluster oracle makes correlation clustering exactly recoverable with at most twice its own error count in queries.","keywords":["correlation clustering","same-cluster queries","query complexity","optimal clustering","approximation algorithm","pivot algorithm","Gap-ETH lower bound","crowdsourcing"],"falsifier":"For any complete signed graph, choose an optimal clustering by exhaustive search and let the oracle answer from it; Theorem 3.1 predicts that QUERY PIVOT returns exactly that clustering and asks at most $2C_{OPT}$ questions. A concrete way to test this is to search all signed graphs on, say, up to eight vertices: the first graph on which the algorithm asks more than $2C_{OPT}$ questions, or returns a clustering different from the oracle's, refutes the theorem.","tokens_in":23638,"feed_emoji":"🧩","tokens_out":9740,"duration_ms":90819,"temperature":0.7,"pith_summary":"This paper establishes that correlation clustering, an NP-hard partitioning problem, becomes substantially easier when an oracle can answer simple same-cluster questions about an optimal solution. The central result is a deterministic pivot algorithm that recovers the exact optimal clustering using at most $2C_{OPT}$ queries, where $C_{OPT}$ is the number of disagreements the optimal clustering makes on the input. A randomized variant reaches a 2-approximation in expectation using at most $C_{OPT}$ expected queries, and the paper proves a conditional lower bound showing that sublinear-in-$C_{OPT}$ queries cannot beat a $1+\\alpha$ approximation. Because a good clustering has small $C_{OPT}$, the query budget scales with the unavoidable error in the data rather than with the number of clusters.","feed_headline":"Exact clustering from 2COPT same-cluster queries","feed_subtitle":"Oracle questions cost at most twice the optimal clustering's own mistakes; query load tracks unavoidable error.","key_machinery":"The load-bearing object is a recursive pivot rule. QUERY PIVOT fixes an arbitrary vertex $u$, enumerates every $(+, +, -)$ triangle containing $u$, and for each such triangle queries one or both edges incident to $u$ to learn whether the optimal clustering treats that edge as a mistake; it then forms a cluster from $u$ and its positive neighbors unless a query showed that the optimal clustering makes a mistake on that edge. The bound of $2C_{OPT}$ queries is carried by a charging argument: every query fires only inside a $(+, +, -)$ triangle, and each triangle in which a query is made creates at least one mistake of the algorithm that matches a mistake of the optimal clustering, so total queries are at most twice total mistakes. The randomized version samples each triangle with probability $p$, and its analysis uses a symmetry lemma showing that the probability an edge is queried does not depend on which endpoint is chosen as pivot.","core_discovery":"The central claim is Theorem 3.1: the deterministic QUERY PIVOT algorithm, given any signed complete graph and an oracle that reports whether the optimal clustering puts two vertices together, outputs exactly that optimal clustering and asks at most $2C_{OPT}$ oracle questions, where $C_{OPT}$ is the number of edges on which the optimal clustering disagrees with the input signs. The randomized variant RANDOM QUERY PIVOT with $p=0.25$ achieves an expected 2-approximation while asking at most $C_{OPT}$ expected questions. The paper further proves, assuming the Gap Exponential-Time Hypothesis, that no polynomial-time algorithm can obtain a $(1+\\alpha)$-approximation for an absolute constant $\\alpha>0$ while asking $o(C_{OPT})$ questions, so the deterministic query bound is optimal up to a factor of 2.","pith_inferences":["One direction the paper leaves implicit is a formal noisy-oracle model: the experiments show robustness to crowd-sourced answers, but a theoretical guarantee would require quantifying oracle error and showing that the $2C_{OPT}$ bound degrades gracefully.","The mistake-charging argument suggests a budget interpretation: the algorithm spends at most one query per unit of optimal error, essentially using the instance's own noise as currency; extending this charging to weighted graphs or partial observations is a natural next step.","If the lower bound is tight, further query reductions must come either from accepting approximation factors above 2 or from richer query types, such as batch queries or answers that reveal more than one edge's status at once.","Because each query is charged to a mistake of the optimal clustering, the algorithm could be adapted to an online setting where the estimate of $C_{OPT}$ is refined as mistakes are revealed, stopping early when the budget is exhausted."],"forward_implications":["Exact recovery of the optimal clustering is possible with a query budget that scales with $C_{OPT}$, the unavoidable error, rather than with the number of clusters or vertices; nearly consistent instances are cheap to cluster.","The randomized variant gives a 2-approximation in expectation using at most $C_{OPT}$ expected queries, improving on the query-free 2.06-approximation whenever that many questions are allowed.","Because the query count is $O(C_{OPT})$, the algorithms remain practical on large instances where LP-based methods with $O(n^3)$ constraints become infeasible, as the experiments on synthetic and real datasets illustrate.","Under the Gap Exponential-Time Hypothesis, a $(1+\\alpha)$-approximation with $o(C_{OPT})$ queries is impossible in polynomial time, so the deterministic algorithm's $2C_{OPT}$ query bound is within a factor of 2 of the best possible query complexity.","A parameterized cluster-editing branching algorithm can be adapted to the same setting and competes with the pivot algorithms in query count, though with different running-time tradeoffs."],"supporting_citations":[{"why":"Supplies the basic pivot 3-approximation framework on which QUERY PIVOT is built.","marker":"[1]"},{"why":"Establishes the same-cluster query model for correlation clustering with fixed cluster count, the setting this paper re-parameterizes by $C_{OPT}$.","marker":"[2]"},{"why":"Introduces the same-cluster query framework with an optimum-knowing oracle adopted here.","marker":"[5]"},{"why":"Defines the correlation clustering objective and gives the first constant-factor approximation.","marker":"[7]"},{"why":"Provides the parameterized cluster-editing branching algorithm adapted and compared against in experiments.","marker":"[8]"},{"why":"Gives the LP-rounding 2.06-approximation used as the query-free baseline and as a comparison in experiments.","marker":"[10]"},{"why":"Supplies the Gap-ETH hypothesis on which the query lower bound rests.","marker":"[13]"},{"why":"Provides the reduction from gap 3-SAT to correlation clustering used in the lower-bound proof.","marker":"[18]"},{"why":"Supplies the optional stopping theorem used to aggregate per-iteration expected bounds in the randomized analysis.","marker":"[25]"}],"fun_headline_variants":["Exact clustering with 2C_OPT queries","Query cost equals 2X optimal mistakes","Correlation clustering: pay unavoidable errors","Perfect clusters from 2X error budget","Query bound tied to optimal disagreements"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The oracle must answer correctly and consistently according to a single fixed optimal clustering; if the oracle is noisy or can contradict itself, the exact-recovery guarantee and the $2C_{OPT}$ query bound do not follow.","fun_headline_variants_meta":{"raw":{"variants":["Exact clustering with 2C_OPT queries","Query cost equals 2X optimal mistakes","Correlation clustering: pay unavoidable errors","Perfect clusters from 2X error budget","Query bound tied to optimal disagreements"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000197,"raw_usage":{"total_tokens":1423,"prompt_tokens":1062,"completion_tokens":361,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":678,"completion_tokens_details":{"reasoning_tokens":296}},"tokens_in":678,"tokens_out":361,"duration_ms":4653,"temperature":1.0,"reasoning_tokens":296,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:30:53.389104+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For any complete signed graph, choose an optimal clustering by exhaustive search and let the oracle answer from it; Theorem 3.1 predicts that QUERY PIVOT returns exactly that clustering and asks at most $2C_{OPT}$ questions. A concrete way to test this is to search all signed graphs on, say, up to eight vertices: the first graph on which the algorithm asks more than $2C_{OPT}$ questions, or returns a clustering different from the oracle's, refutes the theorem.","supporting_citations":[{"cited_title":"Ailon, M","cited_arxiv_id":null,"evidence_quote":"Supplies the basic pivot 3-approximation framework on which QUERY PIVOT is built."},{"cited_title":"Approximate correlation clustering using same-cluster queries","cited_arxiv_id":null,"evidence_quote":"Establishes the same-cluster query model for correlation clustering with fixed cluster count, the setting this paper re-parameterizes by $C_{OPT}$."},{"cited_title":"Ashtiani, S","cited_arxiv_id":null,"evidence_quote":"Introduces the same-cluster query framework with an optimum-knowing oracle adopted here."},{"cited_title":"Bansal, A","cited_arxiv_id":null,"evidence_quote":"Defines the correlation clustering objective and gives the first constant-factor approximation."},{"cited_title":"Going weighted: Parameterized algorithms for cluster editing","cited_arxiv_id":null,"evidence_quote":"Provides the parameterized cluster-editing branching algorithm adapted and compared against in experiments."},{"cited_title":"Chawla, K","cited_arxiv_id":null,"evidence_quote":"Gives the LP-rounding 2.06-approximation used as the query-free baseline and as a comparison in experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Gap-ETH hypothesis on which the query lower bound rests."},{"cited_title":"Parameterized Algorithmics for Network Analysis: Clustering and Query- ing","cited_arxiv_id":null,"evidence_quote":"Provides the reduction from gap 3-SAT to correlation clustering used in the lower-bound proof."}],"review_version":1}