Local Node Differential Privacy

LNDP is a privacy model for distributed networks where each node applies a randomized algorithm to its own edge list. It guarantees that the entire vector of outputs is indistinguishable across 'node-neighboring' graphs (graphs differing in one node's entire edge set). Crucially, changing one node's data can affect the inputs to multiple randomizers, distinguishing it from the standard local model.

We say that an algorithm satisfies epsilon-delta local node differential privacy if these entire vectors of outputs are indistinguishable when for all node neighboring input graphs. [...] Changing one individual's data can change the input to multiple randomizers.

To improve accuracy for linear queries about degree distributions, the algorithm uses a 'blurry degree distribution'. Each node splits its degree between the two nearest multiples of a smoothing parameter (S). This 'blurry vector' representation significantly reduces the L2 sensitivity of individual node contributions from order N to order 1 + N/S^2, allowing for much less Gaussian noise to be added.

To get away with adding less noise, we're going to shift from using the graph's degree distribution to using what I call a blurry approximation of the graph's degree distribution. [...] The vector of blurry vectors has low L2 sensitivity. [...] For comparison, the L2 squared sensitivity of the vector of indicator vectors is of order N. So, for all S bigger than a constant, we're like we're we're winning in terms of in terms of L2 squared sensitivity.

For edge counting in graphs with maximum degree at most D, LNDP algorithms require an error of N/epsilon, which is substantially higher than the D/epsilon error achievable in the central model. This indicates a strong privacy-utility trade-off when strict local node privacy is enforced for sparse graphs.

In the central model, error D over epsilon is both necessary and sufficient. So what that means is that we have a really strong local central gap here. [...] In the local model, you can't do any non-trivial edge counting when you want accuracy for graphs with degree at most one over epsilon.

Despite the general local-central gap, LNDP can surprisingly achieve central model optimal accuracy for certain problems. For instance, estimating the parameter P of an Erdos-Renyi graph or the size of a clique (in a specific graph structure where nodes are either isolated or part of a large clique) can be done with error bounds matching the central model's 1/epsilon dependence, a feat impossible for the standard local model due to privacy amplification by shuffling.

For the regime where epsilon is constant, our local model upper bounds are matching the central model lower bounds for this task. [...] The fact that we're able to match the central model is really surprising because, um, it's actually impossible to match the central model in this in this manner in the standard local model.

The lower bound for edge counting (error N is necessary even for graphs with maximum degree 1) is proven using a 'splicing argument'. This involves demonstrating that no LNDP algorithm can distinguish an empty graph from a random perfect matching. This is achieved by showing both are indistinguishable from a 'random star' graph, leveraging the tensorization property of distance measures and the fact that only one node can differentiate between these graph types.

We're going to show that no LNDP algorithm can distinguish an empty graph from a random perfect matching. [...] We're going to go through a third family of graphs, the random star. [...] The key insight in this lower bound is what we call the splicing argument.

Unlike the non-interactive standard local model where approximate LDP can be simulated by pure LDP, LNDP exhibits a clear separation. This is evidenced by the ability to accurately estimate clique sizes with approximate LNDP but not with pure LNDP, suggesting fundamental differences in how privacy guarantees compose and behave in this network-centric model.

One interesting structural result is that like there's this separation between pure and approximate LDP. [...] The reason why that's interesting is that that separation doesn't hold in the non-interactive standard local model.