{"id":"a97279fc-446e-484d-9bfc-a50c4ef74f42","arxiv_id":"2601.03946","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Under certain separation and size conditions, a nuclear-norm convex program recovers a planted dense submatrix hidden among many dense blocks, with dual-certificate proofs and numerical tests.","lead":"This paper proves conditions under which a convex optimization program can find a deliberately planted dense block of a binary matrix even when the matrix contains many other dense blocks. The result matters for detecting communities or hidden structures in networks where dense regions are common, not just a single anomaly.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.4's S-bound is not justified as written: S1 is independently resampled, so S2 is not the coupled Θ−Θ̃ object that Lemma 3.5 bounds.","rationale":"The reader's weakest_assumption identifies exactly the same load-bearing concern: Lemma 3.4's proof requires a coupling between the actual column/row statistics and the approximating matrix S1 that the paper's independent resampling does not provide. I independently checked the construction and confirmed that S2 is not of the form covered by Lemma 3.5. This is the single point on which the central theorem rests: if the S-bound fails, the dual certificate is not certified and Theorem 2.1 is unproven. However, the gap appears repairable by defining S1 as a deterministic function of the same A entries (the centered Bernoulli transform) rather than as fresh independent draws; with that modification, Lemma 3.2 and Lemma 3.5 both apply. This is why the appropriate verdict is unchanged: conditional rather than accept or reject. The experimental mismatch flagged by the reader is real but secondary; it affects the empirical validation, not the truth of the theorem.","tokens_in":33052,"tokens_out":18706,"duration_ms":156532,"concrete_test":"Re-derive Lemma 3.4 with S1 redefined as the deterministic centered transform of the same A entries: set [S1]_ij = 1 if A_ij=1 and −p_rs/(1−p_rs) if A_ij=0 for all (r,s)≠(1,1). Verify two properties: (a) S1 has independent mean-zero entries with variance bounded by σ̃², so Lemma 3.2 applies; (b) on U1×V_s, S2=S−S1 equals Θ̃−Θ where Θ=A[U1,V_s] and Θ̃ is the column-count-corrected matrix from Lemma 3.5 (with n=m1 and n_j=ν_j), so Lemma 3.5 bounds S2. If both properties hold, the gap is closed and Theorem 2.1 stands; if either fails, an alternative argument for Lemma 3.4 is needed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 2.1 depends on the KKT certificate, and the certificate requires ∥W∥≤1, which is obtained via (50) from Lemma 3.3 (R bound) and Lemma 3.4 (S bound). Lemma 3.4 is the load-bearing step. In its proof, S1 is constructed by independently sampling fresh Bernoulli variables for entries in U1×V_s and U_r×V1. Then S2=S−S1 is claimed to have the same form as Θ−Θ̃ in Lemma 3.5. But Lemma 3.5's Θ̃ is a deterministic column-count correction of the same Θ: the n_j in (47) are counts from Θ itself. In contrast, the ν_j and μ_i appearing in S (Cases 4 and 5 of the W construction) are counts from the original matrix A, and S1 is a fresh independent draw, independent of those counts. Hence S2 is not a function of a single Θ with matched column counts; the coupling required by Lemma 3.5 is absent. Consequently, the stated proof does not establish the claimed bound on ∥S∥, and the sufficient conditions of Theorem 2.1 are not proven as written. This is a genuine missing argument, not merely a loose constant: without a valid S-bound, the dual certificate cannot be certified.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the densest m×n submatrix problem for binary matrices that may contain many planted dense blocks. It proposes a nuclear-norm relaxation (3), constructs explicit dual certificates, and states sufficient conditions for a planted block to be the unique densest submatrix and the unique optimal solution of the relaxation. Theorem 2.1 gives such conditions for a heterogeneous stochastic block model; Theorem 2.2 gives an analogous deterministic adversarial guarantee. Numerical experiments on synthetic matrices and real-world networks are presented as empirical verification of the predicted phase transitions. The main technical engine is a KKT certificate whose dual subgradient W is decomposed as W = λR + λS, with ∥R∥ bounded by Lemma 3.3 and ∥S∥ by Lemma 3.4.","tokens_in":33408,"tokens_out":11671,"duration_ms":99668,"significance":"If the recovery guarantees were fully established, the paper would be a useful advance: it extends convex-relaxation recovery beyond the single-planted-block setting to multiple dense blocks with heterogeneous edge probabilities, and it provides an adversarial counterpart. The dual-certificate construction is concrete, and the authors release implementations in Python, MATLAB, and R. The catch is that the proof of the key S-bound is incomplete as written, and the numerical experiments do not provide the claimed verification of the theoretical phase transition. The contribution is therefore conditional, but the issues are of the kind that can, in principle, be repaired or reframed; this is not a desk-reject situation.","major_comments":[{"comment":"The proof defines S1 by independently resampling fresh Bernoulli variables in U1×V_s and U_r×V1, then sets S2 = S − S1. Lemma 3.5 bounds Θ − Θ̃ where Θ̃ is a deterministic function of the same Θ through the column counts n_j in (47). In contrast, the ν_j and μ_i used in S are counts from the original A, while S1 is a fresh draw independent of those counts. Hence S2 does not have the coupled form required by Lemma 3.5; equalities (48) and (49) do not follow. Since the bound ∥W∥ ≤ 1 in (50) relies on (48)–(49), the KKT certificate for Theorem 2.1 is not established as written. A genuinely different argument is needed for S.","section":"Section 3.5.3, Lemma 3.4/3.5"},{"comment":"The claimed verification is not tied to Theorem 2.1. In Experiment 1 the plotted threshold q = 0.25 + max{sqrt(M log M/(3m)), log M/m} has constants 3 and 1 chosen ad hoc; the third term of (4c), sqrt(max{σ̃²,1}(log N)^3 / min{m1,n1}), is absent and would dominate for the tested sizes. In Experiment 2, p11 = p22 = q, so p* = q and the gap p11 − p* = 0, violating (4c); for m > 250 condition (4a) also fails, and for m < M/2 the target is not the unique densest m×m-submatrix. Thus the experiments do not verify the phase transition claimed in Theorem 2.1; they only illustrate behavior in related regimes.","section":"Section 5.2, Figures 4a/4b"},{"comment":"The certificate in Theorem 3.1 uses the subgradient u1v1^T/√(m1n1), so λ must be compared to 1/√(m1n1). The displayed condition in (51), λ ≥ 1/(m1n1) + 2(1−δ̃)γ, and the final choice λ = 1/(m1n1) + c(1−δ̃)√(m1n1) use 1/(m1n1) instead. Consequently (52) and (53) have the wrong scale, and the proof of nonnegativity of Λ and the bound ∥W∥ < 1 for Theorem 2.2 does not go through. If this is a typo it should be corrected and the surrounding algebra checked; as written it is a load-bearing inconsistency.","section":"Section 4, Eqs. (51)–(53)"},{"comment":"Theorem 2.1 also asserts that (U1,V1) is the unique densest m1×n1-submatrix with high probability. Section 3 proves uniqueness of the optimal solution of (3) via Theorem 3.1, but I did not find an argument showing that the optimality of X* implies, or that (4a)–(4c) directly imply, combinatorial uniqueness among all O(M^{m1} N^{n1}) submatrices. Since Remark 2 says (4a) is imposed 'largely to ensure' this, the theorem should either include the missing concentration argument or state the uniqueness claim with a separate proof.","section":"Theorem 2.1, uniqueness claim"}],"minor_comments":[{"comment":"The abstract says 'deterministic adversarial' without completing the phrase; it should be 'deterministic adversarial model' or 'adversarially generated matrices.' Also, 'wide application the study' is missing 'in.'","section":"Abstract and Section 1"},{"comment":"The display 'p_s n − 6 max{...} < n_j < p_s n − 6 max{...}' has the same expression on both sides; the right-hand side should be p_s n + 6 max{...}.","section":"Appendix A, Lemma A.1 proof"},{"comment":"The notation σ²_{p1s} is not defined; it should be p_{1s}(1 − p_{1s}) or a variance proxy explicitly defined before use.","section":"Section 3.4.2, Eq. (33)"},{"comment":"The displayed value 'γ=12√mn=0.03' appears to be missing a denominator; it should be γ = 12/√(mn), since m = n = 400 gives 12/400 = 0.03.","section":"Section 5.5.1.1"},{"comment":"The statement that 'Conditions (4a) and (4b) hold by our choice of m and M' in Experiment 1 ignores the third term of (4c); the plotted curve also omits that term, which confuses the reader about what is being verified.","section":"Section 5.2.1"},{"comment":"The lemma statement lacks the side condition, used in the proof, that the block sizes n_s are large enough relative to log N. It should either state that condition or be formulated for the parameter regime guaranteed by (4b).","section":"Lemma 3.5"}],"recommendation":"major_revision","confidential_remarks":"The main issue is not a matter of polishing. The S-bound in Lemma 3.4 is the central step, and the current argument is not a valid application of Lemma 3.5 because of the missing coupling. I would send the paper back for major revision with a request for a repaired proof or a clearly weakened theorem. The numerical experiments should be reframed as illustrations, not verifications, unless the plotted curves are actually derived from (4c). The adversarial section appears to contain a simple but consequential scaling typo; this should be checked carefully."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The multi-block generalization is real and worth taking seriously; the proof as written has a load-bearing gap in Lemma 3.4 that takes the main theorem down with it until fixed.\n\nWhat is new: the paper extends convex recovery guarantees for planted dense submatrices from a single hidden block to many blocks in a heterogeneous stochastic block model, and gives a deterministic adversarial counterpart. That is a proper extension, not a re-coordinatization. The KKT certificate construction follows the standard strategy from Ames/Vavasis and Bombina/Ames, and the structure is explained carefully. Section 2.3.3 does an honest job of comparing with biclustering results and where the DSM formulation is wider.\n\nThe soft spot is exactly the stress-test: Lemma 3.4's S-bound does not follow. S1 is built from fresh independent Bernoulli draws, so S2 = S - S1 is not the object in Lemma 3.5, whose Theta-tilde is a deterministic column-count correction of the same Theta. The counts nu_j and mu_i in S come from the original matrix A, while S1 is independent of them. The coupling required for Lemma 3.5 is absent. Without a valid bound on ||S||, the certificate cannot be certified and Theorem 2.1 is unproven as stated. This is a genuine missing argument, not a loose constant.\n\nThe numerics are also presented too kindly. The plots mark phase-transition curves with hand-picked constants (c1=1 and c1=6) that are not derived from the stated inequalities. Experiment 2 sets p11 = p22, so p* = p11 and condition (4c) cannot hold, yet the paper claims the success region matches the theorem. That is misleading even if the convex program works in practice.\n\nThe adversarial section has a few sign/typo slips, but those are minor relative to the Lemma 3.4 gap.\n\nWho this is for: researchers working on convex relaxations for planted subgraphs, and people who want to push DSM guarantees to multiple blocks. The paper deserves a serious referee, but the referee should be asked to insist that Lemma 3.4 be repaired or the theorem weakened, and that the experimental section not claim verifications its own inequalities do not provide.","headline":"A real multi-block extension with a genuine gap in the key spectral bound; worth refereeing, not yet proven.","tokens_in":33870,"tokens_out":2306,"would_cite":false,"duration_ms":21685,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C27","60B20"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that a convex program can recover a hidden dense submatrix exactly, even when many other dense submatrices are planted in the same matrix, provided the target block is sufficiently dense and large relative to its rivals.","keywords":["densest submatrix problem","convex relaxation","nuclear norm minimization","planted dense submatrix","stochastic block model","perfect recovery","phase transition","maximum clique"],"falsifier":"Generate a planted-model instance that satisfies (4a)-(4c) exactly (e.g. m1=80, n1=80, M=N=1000, p11=0.8, p*=0.2) and solve the convex relaxation (3); if the support of the resulting optimal X is not exactly U1 x V1, then Theorem 2.1 is falsified.","tokens_in":32964,"feed_emoji":"🔍","tokens_out":5914,"duration_ms":52655,"temperature":0.7,"pith_summary":"The densest submatrix problem asks for the fixed-size submatrix with the most 1s in a binary matrix; it is NP-hard and generalizes maximum clique. Prior convex-relaxation guarantees assumed a single dense block hidden in noise. This paper relaxes that to a heterogeneous planted-submatrix model with many dense blocks of varying sizes, and proves that a nuclear-norm convex program uniquely recovers the planted block when its expected density is sufficiently above the next-densest block and the block is large enough. The same framework gives an adversarial guarantee. Experiments on synthetic matrices and real collaboration networks match the predicted phase transitions.","feed_headline":"Hidden dense submatrix provably recovered among many rivals","feed_subtitle":"A nuclear-norm convex program with a phase-transition bound matches recovery on real collaboration networks.","key_machinery":"The machinery is the convex relaxation (3): minimize ||X||_* + gamma Tr(Y 1^T) subject to Tr(X 1^T)=mn, P_Omega(X-Y)=0, 0<=X<=11^T, Y>=0, where the nuclear norm promotes a rank-one solution X=uv^T. The proof builds a Lagrange-multiplier dual certificate with a matrix W in the nuclear-norm subdifferential, decomposes W = lambda R + lambda S, and bounds the spectral norms of R and S via Bernstein and matrix concentration inequalities; the required bound on S relies on Lemma 3.5, a coupling argument for random matrices with Bernoulli resampling.","core_discovery":"The central claim is Theorem 2.1: for matrices sampled from the planted submatrix model (a rectangular stochastic block model with per-block Bernoulli probabilities), if the target block is no larger than every other block, all blocks are large enough, and the density gap p11 - p* satisfies the explicit bound (4c), then the planted block is the unique densest m1 x n1 submatrix and X* = u1 v1^T is the unique optimal solution of the convex relaxation (3), with high probability. Theorem 2.2 gives an analogous guarantee against a deterministic adversary that adds and deletes a controlled number of entries. The proof constructs an explicit dual certificate satisfying the KKT conditions.","pith_inferences":["The proof gap around Lemma 3.4 and Lemma 3.5 (independent resampling versus the required coupling) suggests a concrete repair: construct S1 by resampling only off-diagonal blocks after conditioning on the planted block's column sums, or replace Lemma 3.5 with a direct two-sided concentration bound; until then, the claimed spectral bound is not fully established.","The phase-transition condition (4c) has the same qualitative shape as recovery thresholds in biclustering and semidefinite-programming community detection, so the result likely extends to weighted or dense matrices after binarization, and to recovering all dense blocks via a union of rank-one solutions.","When several blocks tie for densest (as in multiple maximum cliques), the paper's experiments show the convex solution becomes a convex combination of the tied blocks; a rounding scheme based on the diagonal of X may disambiguate them, but the paper leaves this unproven.","The condition (4a) that the planted block is no larger than any rival block is an admitted simplification; the authors note a deterministic condition on average densities should remove it, so a natural next step is a version without (4a)."],"forward_implications":["If Theorem 2.1 holds, the densest submatrix can be found in polynomial time (via SDP or ADMM) for a broad class of instances with many dense blocks, not just a single planted block.","The sufficient condition gives a quantitative phase-transition curve: recovery is guaranteed once p11 - p* exceeds a max of terms scaling like sqrt(sigma_tilde^2 N log N / (m1 n1)), sqrt(sigma11^2 log N / min(m1,n1)), and sqrt(max{sigma_tilde^2,1} (log N)^3 / min(m1,n1)), which can be used to tune the regularization parameter gamma.","The adversarial guarantee (Theorem 2.2) shows the convex program is robust to a two-person hiding game: unless the adversary is allowed to add or delete Omega(m1 n1) entries or create near-planted blocks, the planted block is recovered.","The results specialize to and generalize prior guarantees for planted cliques, max-edge bicliques, and dense subgraphs; on real networks, the program recovers known maximum cliques in the Jazz, Karate, Dolphins, Les Miserables, and ASOIAF networks."],"fun_headline_variants":["Provable recovery of hidden dense block among many","Convex program finds hidden dense submatrix among many","Guaranteed recovery for densest submatrix with many rivals","Phase transition bound for hidden dense submatrix recovery"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof's bound on the spectral norm of the dual certificate's off-block term S requires that the actual column statistics inside the planted block be coupled with an independent Bernoulli resampling (Lemma 3.5); as written, S1 is resampled independently, so this coupling is absent and the sufficient conditions in Theorem 2.1 are not fully proven unless that step is repaired.","fun_headline_variants_meta":{"raw":{"variants":["Provable recovery of hidden dense block among many","Convex program finds hidden dense submatrix among many","Guaranteed recovery for densest submatrix with many rivals","Phase transition bound for hidden dense submatrix recovery"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000489,"raw_usage":{"total_tokens":2259,"prompt_tokens":777,"completion_tokens":1482,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":521,"completion_tokens_details":{"reasoning_tokens":1419}},"tokens_in":521,"tokens_out":1482,"duration_ms":9217,"temperature":1.0,"reasoning_tokens":1419,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T12:10:39.863210+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Generate a planted-model instance that satisfies (4a)-(4c) exactly (e.g. m1=80, n1=80, M=N=1000, p11=0.8, p*=0.2) and solve the convex relaxation (3); if the support of the resulting optimal X is not exactly U1 x V1, then Theorem 2.1 is falsified.","supporting_citations":[],"review_version":1}