NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID:7360
Title:On Differentially Private Graph Sparsification and Applications

This paper presents a method for private graph sparsification under edge DP based on effective resistance sampling. This is an interesting contribution to the literature on DP with graph data which advances the state of the art. When preparing the final version of the paper, the authors must address the presentation issues raised by the reviewers, including: - A more concise description of the practical applications of their method, including a justification of why edge-level privacy is sufficient in such applications. - Properly introduce all the notation used in the manuscript. - A discussion to motivate Def 2, in particular the reasons behind the proposed notion of accuracy in point 3 as opposed to the one in Def 1. - A clear discussion of the computational cost of the algorithm to justify the efficiency claim in Thm 3.