pipette
ENEnglish

Subgraph Counting with Local Node Differential Privacy

Sofya Raskhodnikova, Adam Smith, Connor Wagaman, Anatoly Zavyalov

Preprint

En palabras de los autores

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 -LNDP algorithm that, given any public -node template graph , counts occurrences of in a sensitive undirected -node graph with additive error , for any constant . We complement this algorithm with a lower bound showing that every noninteractive -LNDP algorithm for counting copies of any -node template graph with maximum degree greater than must have error . Thus, our algorithm achieves optimal error for counting constant-size subgraphs, up to 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 gap between central and local node differential privacy when accuracy is required for all input graphs. Previous separations either only involved factors or only applied to promise problems.

Resultado principalLimitación que admiten los autores

Apareció: viernes, 16 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: To appear at the ACM-SIAM Symposium on Discrete Algorithms (SODA) 2027