PlumX Metrics
Embed PlumX Metrics

Private Graphon Estimation via Sum-of-Squares

Proceedings of the Annual ACM Symposium on Theory of Computing, ISSN: 0737-8017, Page: 172-182
2024
  • 0
    Citations
  • 0
    Usage
  • 0
    Captures
  • 0
    Mentions
  • 0
    Social Media
Metric Options:   Counts1 Year3 Year

Conference Paper Description

We develop the first pure node-differentially-private algorithms for learning stochastic block models and for graphon estimation with polynomial running time for any constant number of blocks. The statistical utility guarantees match those of the previous best information-theoretic (exponential-time) node-private mechanisms for these problems. The algorithm is based on an exponential mech- anism for a score function defined in terms of a sum-of-squares relaxation whose level depends on the number of blocks. The key ingredients of our results are (1) a characterization of the distance between the block graphons in terms of a quadratic optimization over the polytope of doubly stochastic matrices, (2) a general sum-of-squares convergence result for polynomial op- timization over arbitrary polytopes, and (3) a general approach to perform Lipschitz extensions of score functions as part of the sum-of-squares algorithmic paradigm.

Bibliographic Details

Hongjie Chen; Jingqiu Ding; Yiding Hua; David Steurer; Tommaso D'Orsi; Chih Hung Liu

Association for Computing Machinery (ACM)

Computer Science

Provide Feedback

Have ideas for a new metric? Would you like to see something else here?Let us know