Local Node Differential Privacy
This work addresses privacy concerns in graph data analysis for applications like social networks, offering a local model approach that avoids trusted servers, but it is incremental as it builds on existing differential privacy concepts.
The paper tackles the problem of node differential privacy for graphs in the local model, where nodes privately release edge data to an untrusted server, by developing a novel algorithmic framework based on a blurry degree distribution to accurately answer linear queries about graph statistics, achieving accuracy matching central model privacy for some problems and proving optimality for edge counting in sparse graphs and Erdos-Renyi parameter estimation.
We initiate an investigation of node differential privacy for graphs in the local model of private data analysis. In our model, dubbed LNDP*, each node sees its own edge list and releases the output of a local randomizer on this input. These outputs are aggregated by an untrusted server to obtain a final output. We develop a novel algorithmic framework for this setting that allows us to accurately answer arbitrary linear queries about the input graph's degree distribution. Our framework is based on a new object, called the blurry degree distribution, which closely approximates the degree distribution and has lower sensitivity. Instead of answering queries about the degree distribution directly, our algorithms answer queries about the blurry degree distribution. This framework yields accurate LNDP* algorithms for the edge count, PMF and CDF of the degree distribution, and other graph statistics. For some natural problems, our algorithms match the accuracy achievable with node privacy in the central model, where data are held and processed by a trusted server. We also prove lower bounds on the error required by LNDP* algorithms that imply the optimality of our framework for edge counting in sparse graphs and Erdos-Renyi parameter estimation. Our lower bounds apply even to interactive protocols with a constant number of rounds of interaction between the nodes and the server. Existing lower-bound techniques for related models either yield loose bounds or do not apply in our setting, as graph data results in inherently overlapping inputs to local randomizers. To prove our bounds, we develop a splicing argument that stitches together views from locally similar but globally different distributions on graphs to obtain hard instances. Finally, we prove structural results that reveal qualitative differences between local node privacy and the standard local model for tabular data.