{"id":"d724359c-81d4-4bb5-9def-aa104bbbb02c","arxiv_id":"2607.09441","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A high-probability polynomial-time node-private sampler nearly matches the exponential-time private minimax rate for exact SBM community recovery with ε = Θ(log n).","lead":"The paper gives a polynomial-time node-private algorithm for exact community recovery in stochastic block models that nearly matches the best exponential-time private rates. It shows privacy cost ε ~ log(n) is necessary and sufficient even when the number of communities grows slowly with n.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified beyond the exact-balance modeling restriction already flagged by the reader.","rationale":"The reader correctly isolates exact community balance (and the related SDP/orbit arguments) as the structural limitation that keeps the theorems from applying off the balanced SBM. That restriction is load-bearing for the poly-time exact sampler and the certification analysis, but it is an explicit modeling assumption, not a hidden gap inside the proofs. Privacy holds for every graph; the high-probability runtime and utility statements are conditioned on the SBM events E_D and the SDP success events whose probabilities are controlled under Assumptions 1–2. The lower-bound appendices (approximate DP and zCDP) reinforce necessity of ε = Ω(log n) and do not introduce new soundness issues. Because the paper resolves the stated open question inside the model it claims, and no further technical break was identified, the ACCEPT verdict with moderate confidence remains appropriate. The concrete test above is a short, self-contained verification of the most delicate sampling identity; if it holds, the central algorithmic claim stands.","tokens_in":34290,"tokens_out":633,"duration_ms":7398,"concrete_test":"Independently re-derive the acceptance probability identity of Lemma 7 (eqs. 18–23) under the exact-size assumption only: verify that the product proposal ν_A, the indicator of Σ ∩ R_{σ⋆}, and the final Unif(S_K) relabeling produce exactly π_A when the SDP certificate (7) holds. If the cancellation fails for any σ ∈ Σ, the poly-time exact-sampling claim collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorems 1–3 / Corollary 1) is that Algorithm 1 is pure ε-node-DP for every graph, samples (exactly or with e^{ξ_M} multiplicative distortion) from the exponential mechanism with the LP surrogate eT_{A,D}, and under Assumptions 1–2, with high probability over SBM inputs, runs in polynomial time while attaining the private minimax exact-recovery risk at ε = Θ(log n). The privacy argument (Lemma 2) is graph-agnostic and only uses the sensitivity of the LP surrogate. Exact sampling under the certificate (Lemma 7) uses the exact-size orbit bijection |orbit| = K! and the canonical set R_{σ⋆}. Utility (Theorem 2) reduces near-maximizers of eT to near-maximizers of T on the high-probability event E_D via Lemma 1, then peels with the entropy bound of Lemma 18. SDP recovery/certification (Lemmas 9, 17) is specialized to equal community sizes. All of these steps are written for the exact-balance model Σ; the paper itself flags approximately equal communities as open. Within the stated model the chain is coherent and the appendices supply the needed estimates. No internal inconsistency that would falsify the theorems as stated was found.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper constructs a polynomial-time node-private algorithm for exact community recovery in balanced stochastic block models that nearly matches the exponential-time private minimax rates of Klopp & Zadik. The algorithm uses an LP surrogate eT_{A,D} of the penalized likelihood with sensitivity controlled by an in-community degree threshold D, samples from the corresponding exponential mechanism via an SDP-certified rejection sampler (with a truncated pure-DP variant), and falls back to brute-force enumeration only when certification fails. Under Assumptions 1–2 (exact equal community sizes, K log K ≲ log n, and a/K ≳ A0 log(nK)), Theorems 1–3 and Corollary 1 establish pure ε-node-DP for every graph, high-probability polynomial expected (or worst-case truncated) runtime over SBM inputs, and expected misclassification risk matching the private minimax rate at ε = Θ(log n).","tokens_in":34683,"tokens_out":978,"duration_ms":21667,"significance":"The work resolves a concrete open question left by Klopp & Zadik by replacing their exponential-time exponential mechanism with a high-probability polynomial-time sampler while retaining the same privacy–utility tradeoff, including the sharp ε = Θ(log n) necessity for polynomially small risk. The LP surrogate, SDP margin certificate, and canonical-orbit rejection sampler are carefully engineered and fully proved; the pure-DP analysis of the truncated sampler (Lemma 10) and the zCDP/approximate-DP lower bounds in the appendices are additional conceptual contributions. Within the exact-balance model the result is near-optimal and technically substantial for private graph estimation.","major_comments":[{"comment":"The exact equal-size restriction (σ ∈ Σ with |σ^{-1}(k)| = n/K) is load-bearing for the orbit bijection |[σ]| = K! and the canonical set R_{σ⋆} used in Lemma 7 to prove that Algorithm 2 outputs exactly π_A. The discussion correctly flags approximately equal communities as open, but the abstract and introduction should state more explicitly that the poly-time exact-sampling claim is proved only for exact balance; otherwise readers may over-read the scope of Theorems 1–3.","section":null},{"comment":"Condition (7) requires exact equality of SDP optima V_θ(Y⋆) = eΨ_{A,D}(Y⋆). Remark 3 notes numerical delicacy and claims a slack analysis is analogous, but the main theorems and runtime claims are stated for the exact certificate. A short formal statement (even in an appendix) that a fixed polynomial slack ρ preserves the margin (8) up to lower-order terms, and thus the acceptance bound and utility, would make the computational claim more robust.","section":null}],"minor_comments":[{"comment":"Author affiliation: “Univesrity of Cambridge” is misspelled.","section":null},{"comment":"Figure 1 is helpful but the “Yes/No” branch after SDP certification is easy to miss; a one-line caption note that the brute-force path is taken only on the low-probability event would help.","section":null},{"comment":"Assumption 1 uses C_mg without an explicit numerical range; a parenthetical that any fixed C_mg works for large enough A0 would clarify the free-parameter hierarchy.","section":null},{"comment":"Section 8 (AI declaration) is unusually placed; journals typically prefer a short acknowledgment footnote rather than a numbered section.","section":null},{"comment":"In Lemma 18 the entropy bound is taken from Klopp–Zadik’s eS_u rather than S_u; a one-sentence pointer that the same proof already covers the larger set would save the reader a cross-check.","section":null},{"comment":"Notation: both d_v and d_orb appear; a brief reminder in Appendix A that d_v is node-edit distance on graphs while d_orb is orbit Hamming distance on labels would reduce momentary confusion.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is technically solid and suitable for a top statistics/theory venue after light revision. The exact-balance limitation is real but honestly disclosed; I would not treat it as grounds for major revision. The 2026 arXiv dates on the related Klopp–Zadik and Marchis et al. preprints are consistent within the submission’s timeline and do not raise a priority concern for me."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This is the paper that turns Klopp–Zadik’s exponential-time node-private exact recovery into a high-probability (and truncated worst-case) polynomial-time algorithm while keeping the private minimax rate and the ε = Θ(log n) necessity. That is the real advance.\n\nWhat is new is the combination: an explicit LP surrogate eT_{A,D} that has sensitivity D on the high-probability in-community degree event, stays close enough to the penalized likelihood at near-maximizers, plus an SDP candidate + certification that unlocks a product-proposal rejection sampler over a canonical set of labelings. Privacy is graph-agnostic (sensitivity of the surrogate). Exactness of the sampler under the certificate, the high-probability certification via Pirinen–Ames, and the adapted peeling/utility arguments are written out carefully. The truncated pure-DP version and the approximate-DP / zCDP lower bounds are useful extras; they show the log n privacy cost is not an artifact of pure DP.\n\nSoft spots are real but proportional. The load-bearing restriction is exact equal community sizes (and K log K ≲ log n). The orbit bijection, canonical representatives, and SDP certification are built for that model; the authors flag approximately balanced communities as open. Constants are existential, there is no code or numerical check, and the SDP equality test is idealized. None of that breaks the theorems as stated under Assumptions 1–2.\n\nThis is for people who care about private network estimation and about making exponential mechanisms sampleable. The math looks solid and the citation pattern is appropriate. I would send it to referees; it deserves a careful technical read, not a desk reject. Worth engaging if you work in this area.","headline":"They close the poly-time gap for node-private exact SBM recovery at the right ε = Θ(log n) scale, with a real algorithmic idea and full proofs.","tokens_in":35289,"tokens_out":484,"would_cite":true,"duration_ms":6540,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62H30","68Q25","05C80","68P27"],"pacs":[],"model":"grok-4.5","headline":"A polynomial-time node-private algorithm nearly matches the minimax exact-recovery rate for stochastic block models, with privacy cost only log n.","keywords":["node differential privacy","stochastic block model","exact recovery","exponential mechanism","polynomial-time sampling","semidefinite programming"],"falsifier":"On a sequence of exactly balanced SBMs with a ~ K log n and K growing as log n, either the SDP certificate fails with non-vanishing probability, or the output misclassification rate stays larger than any inverse polynomial while the privacy parameter remains O(log n).","tokens_in":35149,"feed_emoji":"🔒","tokens_out":578,"duration_ms":7129,"temperature":0.7,"pith_summary":"Community recovery from a random graph is a classic statistical problem; doing it while protecting every vertex's entire neighborhood (node privacy) previously seemed to force either exponential runtime or a much larger privacy budget. This paper shows that neither sacrifice is necessary under standard sparse balanced block models. The authors replace the usual likelihood score by an efficiently computable Lipschitz surrogate, then sample from the resulting exponential mechanism by a certified rejection sampler that runs in expected polynomial time with high probability over the graph. The same construction, with a mild truncation, yields worst-case polynomial time and pure privacy only an exponentially small amount larger. The resulting estimator attains the known information-theoretic exact-recovery rate once the privacy parameter is allowed to grow like log n, matching the lower bound and thereby closing the computational gap left open by the earlier exponential-time private algorithm.","feed_headline":"Polynomial-time node privacy matches minimax community recovery","feed_subtitle":"A Lipschitz score plus certified rejection sampling closes the gap left by the exponential-time private algorithm","key_machinery":"A linear-programming Lipschitz surrogate of the penalized likelihood, combined with an SDP certificate that a candidate labeling is a stable maximizer; once the certificate holds, a product-measure proposal plus accept/reject step samples exactly from the corresponding exponential mechanism in expected constant trials.","core_discovery":"Under the paper's balanced-community and signal assumptions, there exists a pure ε-node-private algorithm that, with high probability over the stochastic block model, runs in polynomial time and achieves the minimax exact-recovery risk whenever ε is at least a constant times log(nK). The same rates hold for a truncated variant that guarantees worst-case polynomial runtime and pure privacy only ε plus an exponentially small additive term.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Poly-time node-private algo hits minimax SBM exact recovery","Lipschitz surrogate enables poly-time private community recovery","Accept-reject sampling closes node-privacy gap for SBMs","Node privacy costs only log n for poly-time exact community recovery","Pure ε-node-private poly-time method matches minimax recovery rates"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"Communities must be exactly equal in size and their number can grow at most logarithmically with the number of nodes; the SDP certificate and exact sampling argument are built for this exact-balance setting.","fun_headline_variants_meta":{"raw":{"variants":["Poly-time node-private algo hits minimax SBM exact recovery","Lipschitz surrogate enables poly-time private community recovery","Accept-reject sampling closes node-privacy gap for SBMs","Node privacy costs only log n for poly-time exact community recovery","Pure ε-node-private poly-time method matches minimax recovery rates"]},"model":"grok-4.5","effort":"low","cost_usd":0.005768,"raw_usage":{"total_tokens":1486,"prompt_tokens":691,"num_sources_used":0,"completion_tokens":92,"cost_in_usd_ticks":57680000,"prompt_tokens_details":{"text_tokens":691,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":703,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":691,"tokens_out":92,"duration_ms":6302,"temperature":1.0,"reasoning_tokens":703,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-13T02:58:19.654302+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"On a sequence of exactly balanced SBMs with a ~ K log n and K growing as log n, either the SDP certificate fails with non-vanishing probability, or the output misclassification rate stays larger than any inverse polynomial while the privacy parameter remains O(log n).","supporting_citations":[],"review_version":1}