Differentially private data analysis of social networks via restricted sensitivity

By Jeremiah Blocki, Avrim Blum, Anupam Datta, Or Sheffet. 2012

245 citations recorded by the source corpus.

We introduce the notion of restricted sensitivity as an alternative to global and smooth sensitivity to improve accuracy in differentially private data analysis. The definition of restricted sensitivity is similar to that of global sensitivity except that instead of quantifying over all possible datasets, we take advantage of any beliefs about the dataset that a querier may have, to quantify over a restricted class of datasets. Specifically, given a query f and a hypothesis HH about the structure of a dataset D, we show generically how to transform f into a new query fHH whose global sensitivity (over all datasets including those that do not satisfy HH) matches the restricted sensitivity of the query f. Moreover, if the belief of the querier is correct (i.e., D ∈ HH) then fHH(D) = f(D). If the belief is incorrect, then fHH(D) may be inaccurate. We demonstrate the usefulness of this notion by considering the task of answering queries regarding social-networks, which we model as a combination of a graph and a labeling of its vertices. In particular, while our generic procedure is computationally inefficient, for the specific definition of H as graphs of bounded degree, we exhibit efficient ways of constructing fH using different projection-based techniques. We then analyze two important query classes: subgraph counting queries (e.g., number of triangles) and local profile queries (e.g., number of people who know a spy and a computer-scientist who know each other). We demonstrate that the restricted sensitivity of such queries can be significantly lower than their smooth sensitivity. Thus, using restricted sensitivity we can maintain privacy whether or not D ∈ HH, while providing more accurate results in the event that HH holds true.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Bounding User Contributions: A Bias-Variance Trade-off in Differential Privacy (2019, background): “On the other hand, while the work of Blocki et al. (2013) does not require additional assumptions, their method for finding a bounded degree graph is not computationally efficient.”
Differentially Private Data Publishing and Analysis: A Survey (2017, background): “With the observation that many useful statistics have low sensitivities on graphs Gu with a small degree u, a common approach to achieve node differential privacy is to transform the graph G to a u-degree-bounded graph Gu, in which the nodes with degrees of more than u are deleted [33], [34].”
Analyzing Graphs with Node Differential Privacy (2013, background): “[1] also consider node-level differential private algorithms for analyzing sparse graphs.”
Practical Differential Privacy for SQL Queries Using Elastic Sensitivity (2017, methodology): “Requirement 1 {}}{ Requirement 2 { }} { Database One-to-one One-to-many Many-to-many compatibility equijoin equijoin equijoin PINQ [27] X wPINQ [33] X X X Restricted sensitivity [10] X X DJoin [29] X Elastic sensitivity (this work) X X X X”
DStress: Efficient Differentially Private Computations on Distributed Data (2017, background): “Restricted sensitivity [10] takes advantage of the queriers’ prior beliefs about the data to achieve higher accuracy.”
Towards Practical Differential Privacy for SQL Queries (2017, methodology): “1 Motivation Many previous differential privacy mechanisms [14,40] are based on global sensitivity.”