Node Privacy, High-dimensional Graph Summaries, and Block Models
summary
Algorithms for node-level differential privacy that estimate stochastic block model parameters and, in many regimes, match the optimal non-private error; method uses a noisy edge-count/Laplace density estimate then the exponential mechanism over K×K models (inefficient search), plus a constructive extension lemma that turns an algorithm private on a “typical” subset into one private on all graphs (privacy loss ≤2×). Lower bounds show some epsilon-dependent terms are necessary, a surprising improvement appears for K=1 (Erdos–Rényi) by restricting to cut-density typical graphs; finding polynomial-time and tight epsilon-rate algorithms remains open.
AI-written summary · about
chapters (15)
- 0:00Start
- 2:27Two variants of differential privacy for graphs
- 4:12Challenge for node privacy: high sensitivity • Global sensitivity of a function f is
- 13:52Stochastic K-Block Model
- 16:31Stochastick-Block Model
- 19:30The Statistical Setting
- 23:18The Statistical Question
- 29:16Upper Bound: Proof Idea
- 38:30A lower bound fork 2. Result
- 39:17The case k=1: Learning privately Erdos Reny graphs
- 41:31Upper Bound: The Laplace estimator (suboptimal)
- 44:28Upper Bound: Improving the Laplace estimator
- 47:58The case k=1: Main Result and Extension Lemma
- 49:56Proof Ideas of Extension Lemma
- 52:36Open Questions for node DP, more generally
related talks
35mDistributed Models for Private Analysis of Graph Data
33mPrivacy of Decentralized Machine Learning
01h 03mStatistical Inference and Privacy, Part II
26mAlgorithms with More Granular Differential Privacy Guarantees
17mData privacy and reliable learning
58mLarge-Scale Private Learning, Part III
35mPairwise Network Differential Privacy
01h 00mDifferential Privacy: Fundamentals to Forefront I