Local Node Differential Privacy

How can we analyze sensitive graph data without trusting a central server? In this talk, I will overview our work on local node differential privacy (LNDP), a model in which each node has access to its own neighborhood and shares only privatized information with the world. We develop algorithms for estimating a broad range of graph statistics, including the degree distribution, edge counts, and counts of arbitrary constant-size subgraphs. For some problems, our algorithms achieve accuracy comparable to that of algorithms with access to a trusted central server. We also establish lower bounds that demonstrate the optimality of several of our algorithms and reveal fundamental limitations of local node privacy. In particular, our results exhibit the first polynomial separation in accuracy between the local and central models of node privacy for general graphs. Together, these results lay the foundations for locally private graph analysis and illuminate both its possibilities and its limitations.

Based on joint work with Adam Smith, Connor Wagaman, and Anatoly Zavyalov, to appear in FOCS '26 and SODA '27.