Subgraph Counting with Local Node Differential Privacy

Abstract

We study the problem of approximately counting subgraphs under local node differential privacy (LNDP), a recently introduced model that enforces strong privacy guarantees in analyses of distributed social networks. We design a noninteractive $(\epsilon ,0)$-LNDP algorithm that, given any public $k$-node template graph $H$, counts occurrences of $H$ in a sensitive undirected $n$-node graph with additive error $O(n^{k-\frac{1}{2}}/{\epsilon }^{k-1})$, for any constant $k$. We complement this algorithm with a lower bound showing that every noninteractive $(\epsilon ,\delta )$-LNDP algorithm for counting copies of any $k$-node template graph with maximum degree greater than $1$ must have error $\Omega (n^{k-\frac{1}{2}})$. Thus, our algorithm achieves optimal error for counting constant-size subgraphs, up to $\mathrm{poly}(1/\epsilon )$ factors. Our results substantially expand the types of network statistics known to be approximable under LNDP: prior work considered only functions of the degree distribution. In addition, our lower bound yields the first known $\mathrm{poly}(n)$ gap between central and local node differential privacy when accuracy is required for all input graphs. Previous separations either only involved $\mathrm{poly}(1/\epsilon )$ factors or only applied to promise problems.

To appear at the ACM-SIAM Symposium on Discrete Algorithms (SODA) 2027