Local privacy method counts small network patterns with optimal accuracy
Subgraph Counting with Local Node Differential Privacy
Data Structures and AlgorithmsCryptography and Security
Summary
Counting small patterns in social networks helps understand connections, but sharing this data can threaten privacy. The authors developed a new method that protects individual users' connections while still counting these patterns accurately. They prove their method is about as good as possible and show that protecting privacy this way is harder than traditional methods. This improves on previous work which only handled simpler statistics about networks.
What this means in practice
- •For social network engineers: Count important small connection patterns in user graphs while ensuring individual user privacy in distributed settings.
- •For data privacy teams: Implement privacy-preserving algorithms for releasing complex network statistics that go beyond simple degree counts.
Authors
Sofya Raskhodnikova, Adam Smith, Connor Wagaman, Anatoly Zavyalov
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 $(\varepsilon,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}}/\varepsilon^{k-1})$, for any constant $k$. We complement this algorithm with a lower bound showing that every noninteractive $(\varepsilon,δ)$-LNDP algorithm for counting copies of any $k$-node template graph with maximum degree greater than $1$ must have error $Ω(n^{k - \frac{1}{2}})$. Thus, our algorithm achieves optimal error for counting constant-size subgraphs, up to $\mathrm{poly}(1/\varepsilon)$ 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/\varepsilon)$ factors or only applied to promise problems.