Abstract
We develop the first pure node-differentially-private algorithms for learningstochastic block models and for graphon estimation with polynomial running timefor any constant number of blocks. The statistical utility guarantees matchthose of the previous best information-theoretic (exponential-time)node-private mechanisms for these problems. The algorithm is based on anexponential mechanism for a score function defined in terms of a sum-of-squaresrelaxation whose level depends on the number of blocks. The key ingredients ofour results are (1) a characterization of the distance between the blockgraphons in terms of a quadratic optimization over the polytope of doublystochastic matrices, (2) a general sum-of-squares convergence result forpolynomial optimization over arbitrary polytopes, and (3) a general approach toperform Lipschitz extensions of score functions as part of the sum-of-squaresalgorithmic paradigm.