Pith. sign in

REVIEW 2 major objections 6 minor 51 references

A polynomial-time node-private algorithm nearly matches the minimax exact-recovery rate for stochastic block models, with privacy cost only log n.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-13 02:58 UTC pith:HI6O452M

load-bearing objection 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. the 2 major comments →

arxiv 2607.09441 v1 pith:HI6O452M submitted 2026-07-10 math.ST stat.MLstat.TH

Near-optimal node-private community estimation in polynomial-time

Laurentiu Marchis , Olga Klopp , Po-Ling Loh , Ilias Zadik This is my paper
classification math.ST stat.MLstat.TH MSC 62H3068Q2505C8068P27
keywords node differential privacystochastic block modelexact recoveryexponential mechanismpolynomial-time samplingsemidefinite programming
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

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.

Core claim

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.

What carries the argument

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.

Load-bearing premise

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.

What would settle it

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).

Watch this falsifier — get emailed when new claim-graph text bears on it.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 6 minor

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).

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 (2)
  1. 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.
  2. 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.
minor comments (6)
  1. Author affiliation: “Univesrity of Cambridge” is misspelled.
  2. 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.
  3. 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.
  4. Section 8 (AI declaration) is unusually placed; journals typically prefer a short acknowledgment footnote rather than a numbered section.
  5. 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.
  6. 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.

Circularity Check

0 steps flagged

No significant circularity: poly-time sampler and LP surrogate are constructed and analyzed independently; prior Klopp–Zadik bounds are external benchmarks, not definitional inputs.

full rationale

The paper’s central claims (Theorems 1–3, Corollary 1) are that an explicitly constructed LP surrogate eT_{A,D} has bounded node-sensitivity (Lemma 2), that SDP certification plus product-proposal rejection sampling yields exact (or e^{ξ_M}-multiplicative) samples from the corresponding exponential mechanism in high-probability polynomial time (Lemmas 6–7, Algorithms 1–3), and that utility on SBMs matches the private minimax rate at ε = Θ(log n). These steps are derived from first principles: the LP (1)–(2), the acceptance probability b_A, the canonical set R_{σ⋆}, and the SDP certificate (7) are defined and proved without assuming the target risk. Utility peels near-maximizers of eT to near-maximizers of T on E_D via Lemma 1, then uses entropy bounds adapted from [34]; the adaptation is explicit and does not force the risk by construction. Citations to Klopp & Zadik [34] supply the open question, the exponential-time benchmark, and the ε = Ω(log n) lower bound used only for tightness comparison; that is standard sequential research, not a self-definitional or uniqueness-import loop. SDP exact recovery is imported from Pirinen–Ames [46], an external source. No fitted parameters are renamed as predictions, no ansatz is smuggled in as a uniqueness theorem, and no equation reduces to its own input. Within the stated exact-balance model the derivation chain is self-contained.

Axiom & Free-Parameter Ledger

5 free parameters · 6 axioms · 2 invented entities

Central claims rest on the balanced SBM generative model, standard pure/approximate/zCDP definitions, an external SDP exact-recovery theorem, and several absolute constants chosen large/small enough for concentration and signal-to-noise. The main invented objects are the LP likelihood surrogate, the SDP certificate, and the canonical-permutation rejection sampler; none are physical entities, but they are paper-specific constructions whose utility depends on the SBM high-probability events.

free parameters (5)
  • C_deg (degree threshold multiplier)
    D = C_deg a/K; C_deg must be large enough for in-community degree concentration (Lemma 8) and for the privacy–utility tradeoff. Not fitted to data but chosen by hand as ‘sufficiently large’.
  • χ (SDP shift fraction)
    θ = χa with χ small enough that a−b−4θ ≥ c_ρ a (Lemma 9). Hand-chosen absolute constant controlling the certification margin.
  • L (privacy lower-order constant)
    ε ≥ L log(nK) needed so η ≥ 4B and κ ≥ log(4n(K−1)). Absolute constant, not data-fitted.
  • A0 (SNR constant in Assumption 2)
    a/K ≥ A0 log(nK); A0 must be large enough for SDP recovery, degree tails, and utility peeling. Hand-chosen ‘sufficiently large’.
  • C_mg (community-growth constant)
    K log K ≤ C_mg log n (Assumption 1). Restricts the regime; absolute constant.
axioms (6)
  • domain assumption Homogeneous balanced SBM: equal community sizes s = n/K; edges independent Bern(a/n) within and Bern(b/n) across (Section 2.2).
    All utility and high-probability runtime claims are under this generative model; privacy holds for all graphs.
  • domain assumption Assumption 2: 0 < ρ− ≤ b/a ≤ ρ+ < 1, a,b = o(n), a/K ≥ A0 log(nK).
    Sparse constant-SNR regime needed for signal gap, SDP recovery, and minimax rate nI/K ≍ a/K.
  • standard math Pirinen–Ames-type SDP exact recovery for weighted graphs under mean-gap condition (Lemma 17 / [46]).
    Used to prove candidate recovery and certification (Lemma 9, Theorem 1).
  • standard math Exponential mechanism is pure ε-DP when sensitivity of the score is bounded (McSherry–Talwar).
    Privacy of π_A follows from |eT_{A,D}(σ) − eT_{A′,D}(σ)| ≤ D d_v(A,A′) (Lemma 2).
  • standard math Non-private minimax exact-recovery rate and entropy peeling structure from Zhang–Zhou / Klopp–Zadik.
    Utility upper bound adapts Lemmas A.1/A.5 of [34]; lower bound cited as [34, Thm 4.1].
  • ad hoc to paper Exact equality V_θ(Y⋆) = eΨ_{A,D}(Y⋆) is checkable and holds w.h.p. (condition (7)); numerical slack left as analogous.
    Remark 3 notes exact SDP equality is numerically delicate; analysis uses the exact condition.
invented entities (2)
  • LP likelihood surrogate eT_{A,D} / eH_{A,D} no independent evidence
    purpose: Low node-sensitivity score close to penalized likelihood on in-community bounded-degree graphs, enabling private exponential mechanism with D ≍ a/K rather than D ≍ a.
    Defined in (1)–(2); not a physical object but a paper-specific construction central to matching ε = Θ(log n).
  • SDP-certified rejection sampler (Algorithms 2–3) with canonical set R_σ⋆ no independent evidence
    purpose: Sample exactly (or approximately) from the Gibbs law π_A in expected or worst-case polynomial time when certification succeeds.
    Core algorithmic contribution; correctness relies on Lemmas 4–7 and the SDP margin (8).

pith-pipeline@v1.1.0-grok45 · 38221 in / 3969 out tokens · 50457 ms · 2026-07-13T02:58:19.654302+00:00 · methodology

0 comments
read the original abstract

In this paper, we resolve an open question of Klopp & Zadik (2026) by providing a high-probability polynomial-time, node-private algorithm which nearly matches the performance of their exponential-time node-private algorithm for exact recovery in stochastic block models. Our result involves an explicitly constructed Lipschitz surrogate for the penalized likelihood function, as well as a carefully devised accept-reject algorithm that samples community labels from the corresponding exponential mechanism in polynomial-time. We rigorously analyze the privacy, runtime, and utility of our proposed algorithm, showing that even when the number of communities K grows logarithmically with the number of nodes n, we can achieve the minimax rates for exact recovery with the privacy parameter epsilon growing as log(n), thus matching known lower bounds on the cost of privacy for this setting.

Figures

Figures reproduced from arXiv: 2607.09441 by Ilias Zadik, Laurentiu Marchis, Olga Klopp, Po-Ling Loh.

Figure 1
Figure 1. Figure 1: High-level structure of the proposed node-private estimator (cf. Algorithm 1). [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

51 extracted references · 4 linked inside Pith

  1. [1]

    Abadi, A

    M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. InProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 308–318, 2016

    2016

  2. [2]

    E. Abbe. Community detection and stochastic block models: Recent developments.Journal of Machine Learning Research, 18(177):1–86, 2018

    2018

  3. [3]

    Awan and V

    J. Awan and V. Rao. Privacy-aware rejection sampling.Journal of Machine Learning Research, 24(74):1–32, 2023

    2023

  4. [4]

    Blocki, A

    J. Blocki, A. Blum, A. Datta, and O. Sheffet. The Johnson-Lindenstrauss transform itself pre- serves differential privacy. In2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 410–419. IEEE, 2012

    2012

  5. [5]

    Bombari, I

    S. Bombari, I. Seroussi, and M. Mondelli. Better rates for private linear regression in the proportional regime via aggressive clipping.arXiv preprint arXiv:2505.16329, 2025

    Pith/arXiv arXiv 2025

  6. [6]

    Bun and T

    M. Bun and T. Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. InTheory of Cryptography Conference, pages 635–658. Springer, 2016

    2016

  7. [7]

    M. Bun, J. Ullman, and S. Vadhan. Fingerprinting codes and the price of approximate dif- ferential privacy. InProceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, pages 1–10, 2014

    2014

  8. [8]

    T. T. Cai, Y. Wang, and L. Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy.The Annals of Statistics, 49(5):2825–2850, 2021. 37

    2021

  9. [9]

    M. X. Cao, N. Ramakrishnan, M. Berta, and M. Tomamichel. Channel simulation: Finite blocklengths and broadcast channels.IEEE Transactions on Information Theory, 70(10):6780– 6808, 2024

    2024

  10. [10]

    Chakraborty, S

    A. Chakraborty, S. Chatterjee, and S. Nandy. PriME: Privacy-aware membership profile estimation in networks.arXiv preprint arXiv:2406.02794, 2024

    arXiv 2024

  11. [11]

    H. Chen, V. Cohen-Addad, T. d’Orsi, A. Epasto, J. Imola, D. Steurer, and S. Tiegel. Private estimation algorithms for stochastic block models and mixture models.Advances in Neural Information Processing Systems, 36:68134–68183, 2023

    2023

  12. [12]

    H. Chen, J. Ding, T. d’Orsi, Y. Hua, C. Liu, and D. Steurer. Private graphon estimation via sum-of-squares. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 172–182, 2024

    2024

  13. [13]

    H. Chen, L. Qi, L. Caccetta, and G. Zhou. Birkhoff-von Neumann theorem and decomposition for doubly stochastic tensors.Linear Algebra and its Applications, 583:119–133, 2019

    2019

  14. [14]

    Chen and R

    Y. Chen and R. Eldan. Localization schemes: A framework for proving mixing bounds for Markov chains. In2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 110–122. IEEE, 2022

    2022

  15. [15]

    T. M. Cover.Elements of Information Theory. John Wiley & Sons, 1999

    1999

  16. [16]

    Z. Ding, Y. Wang, G. Wang, D. Zhang, and D. Kifer. Detecting violations of differential pri- vacy. InProceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 475–489, 2018

    2018

  17. [17]

    J. C. Duchi, M. I. Jordan, and M. J. Wainwright. Minimax optimal procedures for locally private estimation.Journal of the American Statistical Association, 113(521):182–201, 2018

    2018

  18. [18]

    C. Dwork. Differential privacy. In M. Bugliesi, B. Preneel, V. Sassone, and I. Wegener, editors, Automata, Languages and Programming, pages 1–12, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg

    2006

  19. [19]

    C. Dwork. Differential privacy: A survey of results. InInternational Conference on Theory and Applications of Models of Computation, pages 1–19. Springer, 2008

    2008

  20. [20]

    Dwork, F

    C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. InTheory of Cryptography Conference, pages 265–284. Springer, 2006

    2006

  21. [21]

    W. R. Gilks and P. Wild. Adaptive rejection sampling for Gibbs sampling.Journal of the Royal Statistical Society: Series C (Applied Statistics), 41(2):337–348, 1992

    1992

  22. [22]

    Gupta, A

    A. Gupta, A. Roth, and J. Ullman. Iterative constructions and private data release. InTheory of Cryptography Conference, pages 339–356. Springer, 2012

    2012

  23. [23]

    M. Hay, C. Li, G. Miklau, and D. Jensen. Accurate estimation of the degree distribution of private networks. In2009 Ninth IEEE International Conference on Data Mining, pages 169–178. IEEE, 2009

    2009

  24. [24]

    Hehir, A

    J. Hehir, A. Slavkovi´ c, and X. Niu. Consistent spectral clustering of network block models under local differential privacy.The Journal of Privacy and Confidentiality, 12(2), 2022. 38

    2022

  25. [25]

    Hoeffding

    W. Hoeffding. Probability inequalities for sums of bounded random variables.Journal of the American statistical association, 58(301):13–30, 1963

    1963

  26. [26]

    P. W. Holland, K. B. Laskey, and S. Leinhardt. Stochastic blockmodels: First steps.Social Networks, 5(2):109–137, 1983

    1983

  27. [27]

    J. Hubbard. Calculation of partition functions.Physical Review Letters, 3:77–78, 1959

    1959

  28. [28]

    Jagielski, J

    M. Jagielski, J. Ullman, and A. Oprea. Auditing differentially private machine learning: How private is private SGD?Advances in Neural Information Processing Systems, 33:22205–22216, 2020

    2020

  29. [29]

    Kamath, J

    G. Kamath, J. Li, V. Singhal, and J. Ullman. Privately learning high-dimensional distributions. InConference on Learning Theory, pages 1853–1902. PMLR, 2019

    1902

  30. [30]

    Kamath, A

    G. Kamath, A. Mouzakis, M. Regehr, V. Singhal, T. Steinke, and J. Ullman. A bias-accuracy- privacy trilemma for statistical estimation.Journal of the American Statistical Association, 120(552):2338–2349, 2025

    2025

  31. [31]

    Karwa, S

    V. Karwa, S. Raskhodnikova, A. Smith, and G. Yaroslavtsev. Private analysis of graph struc- ture.Proceedings of the VLDB Endowment, 4(11):1146–1157, 2011

    2011

  32. [32]

    Karwa and A

    V. Karwa and A. B. Slavkovi´ c. Differentially private graphical degree sequences and syn- thetic graphs. InInternational Conference on Privacy in Statistical Databases, pages 273–285. Springer, 2012

    2012

  33. [33]

    Karwa and S

    V. Karwa and S. Vadhan. Finite sample differentially private confidence intervals.arXiv preprint arXiv:1711.03908, 2017

    Pith/arXiv arXiv 2017

  34. [34]

    Klopp and I

    O. Klopp and I. Zadik. Node-private community detection in stochastic block models.arXiv preprint arXiv:2604.09078, 2026

    Pith/arXiv arXiv 2026

  35. [35]

    Koskela, J

    A. Koskela, J. J¨ alk¨ o, and A. Honkela. Computing tight differential privacy guarantees using FFT. InInternational Conference on Artificial Intelligence and Statistics, pages 2560–2569. PMLR, 2020

    2020

  36. [36]

    Koskela, M

    A. Koskela, M. Seif, and A. J. Goldsmith. On the price of differential privacy for spectral clus- tering over stochastic block models.IEEE Transactions on Network Science and Engineering, 13:5176–5191, 2025

    2025

  37. [37]

    Lattimore and C

    T. Lattimore and C. Szepesv´ ari.Bandit Algorithms. Cambridge University Press, 2020

    2020

  38. [38]

    Marchis, E

    L. Marchis, E. D’souza, T. Fl´ ıdr, and P. Loh. Node-private community estimation in stochastic block models: Tractable algorithms and lower bounds.arXiv preprint arXiv:2605.15943, 2026

    Pith/arXiv arXiv 2026

  39. [39]

    McSherry and K

    F. McSherry and K. Talwar. Mechanism design via differential privacy. In48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 94–103. IEEE, 2007

    2007

  40. [40]

    Minami, H

    K. Minami, H. Arai, I. Sato, and H. Nakagawa. Differential privacy without sensitivity.Ad- vances in Neural Information Processing Systems, 29, 2016

    2016

  41. [41]

    M. S. Mohamed, D. Nguyen, A. Vullikanti, and R. Tandon. Differentially private community detection for stochastic block models. InInternational Conference on Machine Learning, pages 15858–15894. PMLR, 2022. 39

    2022

  42. [42]

    M. Nasr, J. Hayes, T. Steinke, B. Balle, F. Tram` er, M. Jagielski, N. Carlini, and A. Terzis. Tight auditing of differentially private machine learning. In32nd USENIX Security Symposium (USENIX Security 23), pages 1631–1648, 2023

    2023

  43. [43]

    Nguyen and A

    D. Nguyen and A. K. Vullikanti. Differentially private exact recovery for stochastic block models. InInternational Conference on Machine Learning, pages 37798–37839. PMLR, 2024

    2024

  44. [44]

    Nissim, S

    K. Nissim, S. Raskhodnikova, and A. Smith. Smooth sensitivity and sampling in private data analysis. InProceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, pages 75–84, 2007

    2007

  45. [45]

    C. H. Papadimitriou and K. Steiglitz.Combinatorial Optimization: Algorithms and Complex- ity. Courier Corporation, 1998

    1998

  46. [46]

    Pirinen and B

    A. Pirinen and B. Ames. Exact clustering of weighted graphs via semidefinite programming. Journal of Machine Learning Research, 20(30):1–34, 2019

    2019

  47. [47]

    Steinke, M

    T. Steinke, M. Nasr, and M. Jagielski. Privacy auditing with one (1) training run.Advances in Neural Information Processing Systems, 36:49268–49280, 2023

    2023

  48. [48]

    R. L. Stratonovich. On a method of calculating quantum distribution functions.Soviet Physics Doklady, 2:416, 1958

    1958

  49. [49]

    Y.-X. Wang, S. Fienberg, and A. Smola. Privacy for free: Posterior sampling and stochastic gradient Monte Carlo. InInternational Conference on Machine Learning, pages 2493–2502. PMLR, 2015

    2015

  50. [50]

    A. Y. Zhang and H. H. Zhou. Minimax rates of community detection in stochastic block models.The Annals of Statistics, pages 2252–2280, 2016

    2016

  51. [51]

    Y. Zhu, J. Dong, and Y.-X. Wang. Optimal accounting of differential privacy via characteristic function. InInternational Conference on Artificial Intelligence and Statistics, pages 4782–4817. PMLR, 2022. 40

    2022