Private Graphon Estimation for Sparse Graphs *
We design algorithms for fitting a high-dimensional statistical model to a large, sparse network without revealing sensitive information of individual members. Given a sparse input graph G, our algorithms output a node-differentially private nonparametric block model approximation. By node-differentially private, we mean that our output hides the insertion or removal of a vertex and all its adjacent edges. If G is an instance of the network obtained from a generative nonparametric model defined in terms of a graphon W , our model guarantees consistency: as the number of vertices tends to infinity, the output of our algorithm converges to W in an appropriate version of the L 2 norm. In particular, this means we can estimate the sizes of all multi-way cuts in G. Our results hold as long as W is bounded, the average degree of G grows at least like the log of the number of vertices, and the number of blocks goes to infinity at an appropriate rate. We give explicit error bounds in terms of the parameters of the model; in several settings, our bounds improve on or match known nonprivate results.
The main theoretical contributions are: (i) in the finite graph setting, the authors provide an analysis of the L2 estimation quality of symmetric probability matrices using an ideal stochastic block model estimator (ii) the analysis is extended to a consistency analysis of the graphon parameter in a sparse graph generative model (combined with a sample-size dependent sparsity parameter), again using the L2 loss (iii) for both cases the analysis is extended to propose a mechanism for differentially private graph estimation. Each of these results is interesting and important in its own right, and advance the state of the art under what seem like reasonable conditions. Overall, the manuscript well written and conveys the main ideas, though it is clearly compressed from a full version. The "longer version" mentioned in the manuscript they refers to the supplement - which is an extended version of the submitted paper. While I like that the supplement is self contained, this is non-standard for a conference paper. If this paper is accepted, I suggest that the authors modify the appendix to the standard format. - Some standard elements e.g. a conclusion, statement of future work, and some (possibly preliminary) experimental evaluation are not included, I imagine due to limited space, or differences in writing styles/expectations across communities?- The metric on line 219 seems to me comparing a matrix A with a graphon function W using the L2 error. This does not make sense to me. I suspect it is simply a mistake in the definition. Should the definition be min_{A'} || W[A']-W ||?- It will be useful for the authors to specify explicit conditions (if any) under which the function line: 308 is normalizable as a density.Minor comments:- The definitions of L_p norm in lines 209, 210 are quite non-standardize. the authors use the p^th power of the standard definition. I suggest the authors clarify this choice in the manuscript.- Line 234: Authors should note which theorem in [7] they refer to.- Could the authors expand on an explicit algorithm for sampling from the density (line: 308) e.g. an importance sampling or Metropolis-Hastings based approach?- Line 284: "small" g' should be "capital" G.