Recursive mechanism: towards node differential privacy and unrestricted joins

Existing studies on differential privacy mainly consider aggregation on data sets where each entry corresponds to a particular participant to be protected. In many situations, a user may pose a relational algebra query on a sensitive database, and desires differentially pri-vate aggregation on the result of the query. However, no known work is capable to release this kind of aggregation when the query contains unrestricted join operations. This severely limits the ap-plications of existing differential privacy techniques because many data analysis tasks require unrestricted joins. One example is sub-graph counting on a graph. Existing methods for differentially pri-vate subgraph counting address only edge differential privacy and are subject to very simple subgraphs. Before this work, whether any nontrivial graph statistics can be released with reasonable ac-curacy under node differential privacy is still an open problem. In this paper, we propose a novel differentially private mech-anism to release an approximation to a linear statistic of the re-sult of some positive relational algebra calculation over a sensitive database. Unrestricted joins are supported in our mechanism. The error bound of the approximate answer is roughly proportional to the empirical sensitivity of the query — a new notion that measures the maximum possible change to the query answer when a partici-pant withdraws its data from the sensitive database. For subgraph counting, our mechanism provides the first solution to achieve node differential privacy, for any kind of subgraphs. 1