Search papers, labs, and topics across Lattice.
This paper introduces Local Node Differential Privacy (LNDP), a new privacy model for graph data where each node's edge list is privatized locally before aggregation by an untrusted server. They develop an algorithmic framework for answering linear queries on the degree distribution of the graph under LNDP, achieving accuracy comparable to central node privacy for some problems. The authors also establish lower bounds on the error required by LNDP, proving the optimality of their algorithms and revealing fundamental differences between LNDP and the standard local model.
Local node differential privacy can achieve accuracy comparable to centralized node privacy for some graph problems, challenging the conventional wisdom that local privacy always implies a significant accuracy loss.
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 on a blurry approximation of the input graph's degree distribution. For some natural problems, the resulting 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 that imply the optimality of our algorithms for several fundamental graph statistics. We then lift these lower bounds to the interactive LNDP setting, demonstrating the optimality of our algorithms even when constantly many rounds of interaction are permitted. Obtaining our lower bounds requires new approaches, since those developed for the usual local model do not apply to the inherently overlapping inputs that arise from graphs. Finally, we prove structural results that reveal qualitative differences between local node privacy and the standard local model for tabular data.
