Distributed Models for Private Analysis of Graph Data
summary
Defines a local node-private model where each node randomizes its adjacency list noninteractively and an untrusted aggregator sums reports. Algorithms clip degrees at a bound D and add Gaussian noise with standard deviation on the order of D+√n, so edge count error scales like Θ(max(n, D√n)) (privacy constants omitted). Lower bounds prove Ω(n/ε) error in sparse graphs, while some tasks (Erdős–Rényi p) achieve near 1/n statistical accuracy.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 1:30Local node differential privacy
- 3:40Differential privacy for graphs
- 6:49Prior work in local DP
- 8:00Edge counting accuracy
- 12:40Erdős-Rényi parameters
- 13:43Clique size estimation
- 16:13Qualitative phenomena
- 18:47Edge counting protocol
- 23:01Linear queries on degree
- 26:58Connor’s lower bound
- 31:57Implications and challenges
- 32:43Q&A
related talks
54mNode Privacy, High-dimensional Graph Summaries, and Block Models
33mPrivacy of Decentralized Machine Learning
14mDistributed Private Aggregation in Graph Neural Networks
01h 04mNonparametric Bayesian Methods: Models, Algorithms, and Applications IV
35mLocal Statistics, Semidefinite Programming, and Community Detection II
24mRobust Parameter Estimation For Random Graphs
43mIs Interaction Necessary for Distributed Private Learning?
01h 07mLarge-Scale Private Learning, Part II