Time-Aware Projections: Truly Node-Private Graph Statistics under Continual Observation

arXiv:2403.04630v1 Announce Type: cross
Abstract: We describe the first algorithms that satisfy the standard notion of node-differential privacy in the continual release setting (i.e., without an assumed promise on input streams). Previous work addresses node-private continual release by assuming an unenforced promise on the maximum degree in a graph; indeed, the algorithms from these works exhibit blatant privacy violations when the degree bound is not met. Our algorithms are accurate on sparse graphs, for several fundamental graph problems: counting edges, …

addresses algorithms arxiv aware cs.cr cs.ds differential privacy graph indeed input node notion privacy private release standard statistics under work