{"id":"2aedf636-a620-4923-8e2b-9e968e8d724e","arxiv_id":"2506.21543","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A weighted generalization of the planted clique problem is introduced, with detection thresholds governed by divergence measures between the two edge-weight distributions.","lead":"This paper studies how to detect a hidden group of k vertices in a complete graph whose edge weights are drawn from an unusual distribution. It gives statistical limits for when detection is possible and polynomial-time spectral tests that work when the group size is at least on the order of the square root of the number of vertices.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.7 collapses for continuous singular Q: no P-null interval with positive Q-mass exists, so the proposed interval-scan test cannot support the claimed polynomial-time detection.","rationale":"The reader's weakest_assumption correctly isolates Theorem 3.7, and I agree with that diagnosis: the proof's interval assertion fails for continuous singular Q, and this is the only result supporting the abstract's claim that an unknown singular pair can always be distinguished in polynomial time as soon as k→∞. For P=Uniform[0,1] and Q=Cantor, Q⊥P but no interval with positive Q-mass has P-mass zero, so the proposed event E cannot occur with the required probability. The Frostman calculation makes this quantitative: any interval containing enough Q-mass to certify k clique edges has P-mass at least k^{-1/α}, α=log2/log3, so it contains many outside edges; the no-outside-edge condition is exponentially rare. The failure is structural, not a typo: the proof cannot be repaired by a finer interval net, and the test itself fails for a natural singular pair. I also note a secondary issue in Proposition 3.3: the test rejecting when τmin<1/(2n) has Type I error tending to 1, since the null minimum of binom(n,2) uniforms is of order 1/n^2, not exceeding 1/(2n). That proposition is likely repairable by choosing a much smaller threshold, so I do not base the verdict change on it, but it confirms that the manuscript needs careful revision. Because Theorem 3.7 is a headline contribution and the flaw is not a simple fix, I move the verdict from CONDITIONAL to REJECT for the current version.","tokens_in":15411,"tokens_out":22687,"duration_ms":279208,"concrete_test":"Take P=Uniform[0,1], Q=the standard Cantor distribution, and analyze the event E in the proof of Theorem 3.7 for a sequence k=k_n→∞ with k≤n/2. For each interval I with Q(I)≥k/binom(k,2), use the Frostman property Q(I)≤C|I|^α (α=log2/log3) to lower-bound P(I)=|I|≥c k^{-1/α}, and bound the probability that no edge outside the planted clique falls in I by exp(-(N-binom(k,2))c k^{-1/α}). Taking a union bound over the at most N^2 distinct intervals determined by the observed values, show this tends to 0 because N=binom(n,2) and k≤n/2 imply N k^{-1/α}→∞. This would establish P1(E)→0, so the test's risk tends to 1, contradicting Theorem 3.7.","verdict_should_be":"REJECT","load_bearing_attack":"Theorem 3.7 (Section 4.6) is the load-bearing point. The proof begins by asserting that if Q is not absolutely continuous with respect to P, then some interval I has P(I)=0 and Q(I)>0. This is false for continuous singular Q: for P=Uniform[0,1] and Q the standard Cantor distribution, Q⊥P, Q has no atoms, and every interval with positive Q-measure has positive P-measure. Consequently the scan event E in the proof—an interval I with at least k edges inside the planted clique and no edges outside it—cannot be relied upon. For any interval I with Q(I)≥k/binom(k,2), the Frostman bound Q(I)≤C|I|^α (α=log2/log3) forces P(I)≥c k^{-1/α}; the expected number of outside edges in I is then ≳ n^2 k^{-1/α}, which diverges for every k≤n/2. The no-outside-edge condition is exponentially unlikely, uniformly over the polynomial number of intervals determined by the data. Hence the Type II error of the proposed test tends to 1, not 0, for this natural singular pair, and the abstract's claim that an unknown singular pair is always detectable in polynomial time whenever k→∞ is not supported. This is a central advertised contribution, not a peripheral lemma.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies a weighted generalization of the hidden clique problem. Under the null hypothesis all edge weights of the complete graph are i.i.d. from P; under the alternative, a random set of k vertices has all internal edge weights drawn from Q. The paper gives statistical limits and tests in two scenarios. When P and Q are known, Theorem 3.1 shows that if Q is not absolutely continuous with respect to P then the optimal risk tends to 0 whenever k tends to infinity; Theorem 3.4 gives divergence-based bounds when Q is absolutely continuous with respect to P; Theorem 3.6 gives a spectral test for k=Omega(sqrt(n)). In the partial-information scenario, Theorem 3.7 claims a polynomial-time interval-scan test for unknown singular Q whenever k tends to infinity, and Theorem 3.8 gives a spectral test using only the means and support when k=Omega(sqrt(n)). The proofs of Theorems 3.1, 3.2, 3.3, 3.4, 3.6, and 3.8 are mostly standard second-moment and concentration arguments. The main gap is Theorem 3.7, whose key geometric assertion about singular measures is false.","tokens_in":15579,"tokens_out":14661,"duration_ms":172842,"significance":"The weighted hidden clique problem is a natural and timely generalization, and the divergence-based thresholds in Theorem 3.4 are clean and potentially useful. The spectral tests are explicit and apply in both information scenarios. If Theorem 3.7's claim could be established, the paper would make a strong contribution by showing that unknown singular alternatives are always polynomially detectable at any k tending to infinity. However, the central advertised result for unknown singular Q is currently unsupported: the proposed interval-scan test provably fails for continuous singular measures such as the Cantor distribution against Lebesgue measure. The remaining results appear sound and are likely publishable after substantial revision.","major_comments":[{"comment":"The proof begins with the key assertion that if Q is not absolutely continuous with respect to P, then there exists an interval I with P(I)=0 and Q(I)>0. This is false for continuous singular measures: take P=Uniform[0,1] and Q the standard Cantor distribution. Then Q is singular with respect to P, but every interval with Q(I)>0 also has P(I)>0. For such a pair, the event E used to define the test cannot occur under H1: any interval with positive Q-mass has positive P-mass, so outside edges of the planted clique fall in I with positive probability, making the condition sum over e not in E(S) of 1{X_e in I}=0 fail. The Type II error of the proposed test therefore tends to 1 rather than 0 when k tends to infinity. Consequently Theorem 3.7 and the corresponding claim in the abstract are not established; a different test or a different argument is needed for singular continuous Q.","section":"Section 4.6, Theorem 3.7"}],"minor_comments":[{"comment":"The statement should explicitly assume P is not equal to Q, or that rho = chi^2(Q||P)+1 > 1. Otherwise, for P=Q the conditions have D_KL=0 and chi^2=0, and part (a) would assert R(T*)->0 for k at least (2+epsilon) log n / 0, which is vacuous and false because H0 and H1 are identical.","section":"Section 3.1, Theorem 3.4"},{"comment":"The display after the inequality 'P1(Tscan <= n^k) <= P1(...)' is garbled; it contains stray factors such as '{k choose 2} k^2/2' and should be rewritten as P1( (1/{k choose 2}) * sum_{e in E(S*)} log(q(X_e)/p(X_e)) <= 2 log n / k ), so that the strong-law step is clear.","section":"Section 4.4, proof of Theorem 3.4(a)"},{"comment":"The cardinality of the epsilon-net on the unit sphere should be 9^n, not 9n as written. With the printed '9n' the union bound in equation (5) does not yield the claimed delta/2; the later substitution t = 4(b-a) sqrt((log 9)n + log(4/delta)) explicitly requires the 9^n bound.","section":"Section 4.7, proof of Theorem 3.8"},{"comment":"The polynomial-time implementation of the interval scan could be clarified: for a fixed interval I, the condition that all edges with weights in I lie inside some set S of size k depends only on the set V_I of vertices incident to those edges and the number of such edges. The check reduces to whether |V_I| <= k and the number of edges with weights in I is at least k, not to an explicit search over all k-subsets.","section":"Section 4.6, Theorem 3.7"},{"comment":"There are minor typographical issues, such as 'scantest' in Section 3.1, 'definea' in the introduction, and 'coloumns' in the proof of Theorem 3.8, which should be corrected in a revision.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern about Theorem 3.7 is valid and lands directly on the paper's central claim. This is a genuine mathematical gap, not a presentation issue: the proposed interval-scan test fails for continuous singular Q, and the proof's initial assertion is false. I recommend major revision. If the authors can prove the result only under an extra condition (for example, Q has an atom, or there exists a P-null interval with positive Q-mass), they should restate the theorem and adjust the abstract. The other results appear sound, the proofs are standard, and the self-citations are appropriate; there is no circularity."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Let me give you the short version: the paper's main statistical-limits results for the weighted hidden clique problem are largely right and worth a careful look, but the central claim about unknown singular distributions — Theorem 3.7 — does not hold up. The proof assumes that if Q is not absolutely continuous with respect to P, then some interval has P-measure zero and Q-measure positive. That's false: take P uniform on [0,1] and Q the Cantor measure. Q is singular with respect to P, yet every interval with positive Q-mass has positive P-mass. The interval-scan event then cannot separate the hypotheses; the no-outside-edge condition fails, and the claimed Type II error bound is actually backwards: for a Bin(C(k,2), 1/k) random variable, the probability of being below k tends to 1, not to 0. So the polynomial-time test for all non-absolutely-continuous pairs, prominently advertised in the abstract, is unsupported. This is a load-bearing flaw, not a typo.\n\nWhat is genuinely new and solid: the weighted hidden clique model with general P and Q is a natural generalization, and the KL/chi-square thresholds in Theorem 3.4 look correct in outline. The scan-test upper bound and the second-moment lower bound are standard but well executed. The spectral tests in Theorems 3.6 and 3.8 are also standard, apart from a typo (the net size is 9^n, not 9n) and the garbled display in Section 4.4. Proposition 3.3's construction is actually a valid density; the integral identity in the proof is wrong as written, but the needed inequality holds after a small fix. Corollary 3.5 is a nice unifying observation. The citation pattern is fine; the self-citations to Lugosi are to textbook facts.\n\nFor a referee: this paper deserves engagement. The information-theoretic part is publishable after minor repairs, but Theorem 3.7 needs either a corrected proof with additional assumptions (e.g., Q having atoms) or the claim must be withdrawn. The authors should also clarify that Theorem 3.7's statement says R(T*) but the proof bounds the risk of a specific test. I would send it to review, but tell the authors the singular-continuous case is a mandatory revision. It is a specialist paper for people working on planted problems and anomaly detection; I would discuss it in my reading group, but not as a clean result.","headline":"A useful information-theoretic extension of planted clique with a mostly sound KL/chi-square threshold, but the advertised polynomial-time test for all singular pairs rests on a false interval-separation claim and a backwards binomial bound.","tokens_in":16227,"tokens_out":10578,"would_cite":true,"duration_ms":118305,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","62C20","62G10"],"pacs":[],"model":"deepseek-v4-flash","headline":"A weighted analogue of the hidden clique problem is statistically detectable once the planted set has logarithmically many vertices, with polynomial-time spectral tests when $k=\\Omega(\\sqrt{n})$.","keywords":["weighted hidden clique","planted clique","hypothesis testing","edge weights","Kullback-Leibler divergence","chi-squared divergence","spectral test","random graphs"],"falsifier":"Take $P$ uniform on $[0,1]$ and $Q$ a countable mixture of point masses on the rationals: $Q$ is not absolutely continuous with respect to $P$, yet every interval has positive $P$-mass, so the interval-scan test in Theorem 3.7 loses its key guarantee that outside edges almost surely avoid the chosen interval; checking whether any polynomial-time test still achieves vanishing risk for $k_n\\to\\infty$ on this pair would settle whether the claimed conclusion holds beyond the proof.","tokens_in":15128,"feed_emoji":"🔍","tokens_out":11871,"duration_ms":115734,"temperature":0.7,"pith_summary":"The paper studies a weighted version of the hidden clique problem: a complete graph on $n$ vertices has edge weights drawn independently from $P$, except that the edges among $k$ randomly chosen vertices are drawn from $Q$, and the statistician must decide which model produced the observed weights. The central result is that, when $P$ and $Q$ are known and $Q$ is absolutely continuous with respect to $P$, the optimal risk tends to $0$ as soon as $k_n \\ge (2+\\epsilon)\\log n / D_{\\mathrm{KL}}(Q\\Vert P)$, and tends to $1$ when $k_n$ is below a threshold expressed through the $\\chi^2$-divergence. If $Q$ is not absolutely continuous with respect to $P$, then $k_n\\to\\infty$ is enough for detection, and in the unknown-distribution case a polynomial-time scan over intervals can achieve this under an interval-positivity condition. The interest is that a canonical statistical-computational problem is extended to general weighted graphs, with an information-theoretic crossover expressed in standard divergences and polynomial-time spectral tests working at the $\\sqrt{n}$ scale.","feed_headline":"Weighted hidden cliques are detectable once their size reaches log n","feed_subtitle":"With known distributions the threshold is log n; with only means, a spectral test works at √n.","key_machinery":"Three objects carry the argument. The likelihood ratio is $L(X)=\\frac{1}{\\binom{n}{k}}\\sum_{|S|=k}\\prod_{e\\in E(S)}\\frac{q(X_e)}{p(X_e)}$; its second moment under the null reduces to a sum over subset pairs in which the overlap size $i$ contributes $\\rho^{\\binom{i}{2}}$, and this is what yields the logarithmic threshold in the lower-bound direction. The scan statistic maximizing $\\prod_{e\\in E(S)} q(X_e)/p(X_e)$ over all $k$-subsets and comparing with $n^k$ yields the detectability bound in the upper direction. The spectral test transforms each edge weight $x$ into the indicator of the set $A=\\{x:p(x)>q(x)\\}$; because $\\mathbb{E}_0[\\phi(X)]-\\mathbb{E}_1[\\phi(X)]=d_{TV}(P,Q)$, the centred maximum eigenvalue separates the two hypotheses at the $\\sqrt{n}$ scale, and the same transform works with only a set where the densities are ordered instead of the full densities.","core_discovery":"The paper claims that the weighted hidden clique problem has a logarithmically growing information-theoretic threshold for essentially every distinct pair of distributions. The optimal likelihood-ratio test has risk controlled by the second moment $\\mathbb{E}_0[L(X)^2]$, which evaluates to an average of $\\rho^{\\binom{|S\\cap T|}{2}}$ over pairs of $k$-subsets, where $\\rho=\\chi^2(Q\\Vert P)+1$; this produces an indistinguishability bound near $k_n \\approx 2\\log_\\rho n$ and, through a scan test, a detection guarantee near $k_n \\ge (2+\\epsilon)\\log n / D_{\\mathrm{KL}}(Q\\Vert P)$. When $Q$ has mass on a set that $P$ assigns probability zero, a simple test looking for any edge weight in that set makes the risk at most $(1-Q(A))^{\\binom{k}{2}}$, so $k_n\\to\\infty$ suffices. The paper also establishes that polynomial-time spectral tests succeed once $k_n=\\Omega(\\sqrt{n})$, both with full knowledge of the densities and, when the means differ and the supports are bounded, with knowledge of only the means.","pith_inferences":["Editorial inference: the interval-positivity condition in Theorem 3.7 is not implied by non-absolute continuity; $P$ uniform on $[0,1]$ and $Q$ a countable sum of point masses on the rationals form a singular pair with no $P$-null interval of positive $Q$-mass, so the conclusion is not proved for such pairs even if it is true.","Editorial inference: the gap between the KL-based detectability threshold and the $\\chi^2$-based indistinguishability threshold suggests that a sharp phase transition, if it exists, is governed by an intermediate divergence; computing the risk of the likelihood-ratio test near $k_n \\sim \\log n$ for pairs like $N(0,1)$ versus $N(1,1)$ would locate the crossover.","Editorial inference: the spectral transform is exactly the test built from total-variation separation, so the required $k_n=\\Omega(\\sqrt{n})$ is plausibly the price of discarding the likelihood structure; simulating the spectral gap for $k_n$ between $\\log n$ and $\\sqrt{n}$ would quantify the computational gap for weighted graphs."],"forward_implications":["For any distinct $P$ and $Q$, $k_n\\ge c\\log n$ makes the optimal risk vanish, so the weighted problem inherits the classical logarithmic information-theoretic threshold.","If $Q$ is not absolutely continuous with respect to $P$, detection requires only $k_n\\to\\infty$; with unknown distributions a polynomial-time interval scan achieves this whenever the singular set can be witnessed by an interval.","The spectral test based on the indicator transform decides with risk at most $\\delta$ whenever $k_n > 4\\sqrt{(\\log 9)n + \\log(4/\\delta)}/d_{TV}(P,Q)$, using only the ordering of the densities.","When the densities are unknown but the means are known and differ, the same spectral test works at $k_n = \\Omega(\\sqrt{n}/|\\mu_Q-\\mu_P|)$ for bounded supports.","The classical hidden clique is the special case $P=\\mathrm{Bernoulli}(p)$, $Q=\\delta_1$; substituting gives the familiar $k_n\\sim 2\\log_{1/p} n$ detection threshold."],"supporting_citations":[{"why":"Supplies the threshold expansion for sums over subset overlaps that gives the $k_n$ bound in Theorem 3.4(b).","marker":"[14]"},{"why":"Supplies the epsilon-net covering bound used to control the spectral norm of the centered weight matrix in Theorems 3.6 and 3.8.","marker":"[38]"},{"why":"Supplies the identity that the optimal risk equals $1-d_{TV}(P_0,P_1)$, used throughout the risk computations.","marker":"[20]"},{"why":"Supplies the standard inequalities relating total variation, Hellinger, KL and $\\chi^2$ divergences used in Proposition A.1.","marker":"[33]"},{"why":"Supplies the Rényi divergence inequalities invoked for the divergence relations in Proposition A.1.","marker":"[46]"},{"why":"Establishes the classical $2\\log_{1/p}n$ detection threshold for the unweighted hidden clique problem that this paper generalizes.","marker":"[35]"},{"why":"Provides the spectral method for cliques of size $\\Omega(\\sqrt{n})$ that anchors the computational comparison.","marker":"[4]"}],"fun_headline_variants":["Hidden clique detection scales to log n for weighted graphs","Weighted hidden cliques: log n threshold, sqrt n spectral","Detecting subtle weighted cliques: from log n to sqrt n","Log n threshold for weighted hidden clique detection","Spectral tests crack weighted hidden cliques at sqrt n"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of the unknown-distribution result assumes that whenever $Q$ is not absolutely continuous with respect to $P$, some interval has zero $P$-mass and positive $Q$-mass; singular pairs built from countable point masses can violate this, so the stated claim is not established for those pairs.","fun_headline_variants_meta":{"raw":{"variants":["Hidden clique detection scales to log n for weighted graphs","Weighted hidden cliques: log n threshold, sqrt n spectral","Detecting subtle weighted cliques: from log n to sqrt n","Log n threshold for weighted hidden clique detection","Spectral tests crack weighted hidden cliques at sqrt n"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000379,"raw_usage":{"total_tokens":2044,"prompt_tokens":1001,"completion_tokens":1043,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":617,"completion_tokens_details":{"reasoning_tokens":962}},"tokens_in":617,"tokens_out":1043,"duration_ms":8340,"temperature":1.0,"reasoning_tokens":962,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T22:27:21.079494+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $P$ uniform on $[0,1]$ and $Q$ a countable mixture of point masses on the rationals: $Q$ is not absolutely continuous with respect to $P$, yet every interval has positive $P$-mass, so the interval-scan test in Theorem 3.7 loses its key guarantee that outside edges almost surely avoid the chosen interval; checking whether any polynomial-time test still achieves vanishing risk for $k_n\\to\\infty$ on this pair would settle whether the claimed conclusion holds beyond the proof.","supporting_citations":[{"cited_title":"Bollobás.Random graphs","cited_arxiv_id":null,"evidence_quote":"Supplies the threshold expansion for sums over subset overlaps that gives the $k_n$ bound in Theorem 3.4(b)."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the epsilon-net covering bound used to control the spectral norm of the centered weight matrix in Theorems 3.6 and 3.8."},{"cited_title":"Springer-Verlag, New York, 1996","cited_arxiv_id":null,"evidence_quote":"Supplies the identity that the optimal risk equals $1-d_{TV}(P_0,P_1)$, used throughout the risk computations."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the standard inequalities relating total variation, Hellinger, KL and $\\chi^2$ divergences used in Proposition A.1."},{"cited_title":"van Erven and P","cited_arxiv_id":null,"evidence_quote":"Supplies the Rényi divergence inequalities invoked for the divergence relations in Proposition A.1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the classical $2\\log_{1/p}n$ detection threshold for the unweighted hidden clique problem that this paper generalizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the spectral method for cliques of size $\\Omega(\\sqrt{n})$ that anchors the computational comparison."}],"review_version":1}