Source-linked AI summary
Differentially Private Learning of Undirected Graphical Models using Collective Graphical Models
Garrett Bernstein, Ryan McKenna, Tao Sun, Daniel Sheldon, Michael Hay, Gerome Miklau
TL;DR
The paper asks how to learn discrete, undirected graphical models while protecting individual privacy. It releases Laplace-noised sufficient statistics and uses collective graphical-model inference within EM to recover their latent true values. The resulting approach learns better models than competing methods on synthetic data and human-mobility data, while noisy-statistics learning has documented practical pathologies.
Problem
The problem is privately learning useful discrete, undirected graphical models from sensitive data while protecting individuals.
Method
The method releases Laplace-noised sufficient statistics and performs CGM-based inference over the true sufficient statistics within an expectation-maximization framework.
Results
The CGM approach learns better models than competing approaches across most synthetic scenarios and on real human-mobility data.
Takeaways & Limitations
The approach offers a practical privacy–utility trade-off by using sufficient statistics whose sensitivity is easy to analyze and whose release is simple.
Takeaways & Limitations
Noisy sufficient statistics can produce privacy-dominated error at practical sample sizes and zero marginals that cause nonexistence of the maximum-likelihood estimate.
Abstract
from arXiv · showhide
We investigate the problem of learning discrete, undirected graphical models in a differentially private way. We show that the approach of releasing noisy sufficient statistics using the Laplace mechanism achieves a good trade-off between privacy, utility, and practicality. A naive learning algorithm that uses the noisy sufficient statistics "as is" outperforms general-purpose differentially private learning algorithms. However, it has three limitations: it ignores knowledge about the data generating process, rests on uncertain theoretical foundations, and exhibits certain pathologies. We develop a more principled approach that applies the formalism of collective graphical models to perform inference over the true sufficient statistics within an expectation-maximization framework. We show that this learns better models than competing approaches on both synthetic data and on real human mobility data used as a case study.
1. Introduction
The paper studies differentially private learning for discrete, undirected graphical models, where general private-learning frameworks are impractical and the undirected setting is computationally harder. It releases noisy sufficient statistics with the Laplace mechanism and develops CGM-based inference, achieving better models than competing approaches across most synthetic scenarios and human-mobility experiments.
- The paper addresses private parameter learning for discrete, undirected graphical models, a more general and computationally harder problem than private learning for directed models.
- Differential privacy requires calibrating noise to sensitivity, creating a trade-off between privacy protection and the utility of learned models.Lower-dimensional quantities and quantities with tightly analyzable sensitivity can permit smaller noise, whereas general-purpose bounds may be loose.
- The proposed release mechanism adds Laplace noise to contingency-table sufficient statistics because they form an information bottleneck, have exactly analyzable sensitivity, and are practical to release.The authors identify public-agency adoption as a plausible practical setting.
- Naive MLE is competitive with or better than general-purpose private methods and is asymptotically consistent, but privacy error can remain substantial at practical sample sizes and the method has pathologies.These limitations motivate a more principled approach that infers the true sufficient statistics within an EM framework.
- CGM inference is adapted to the noisy-statistics problem, and the resulting approach learns better models than existing state-of-the-art methods in most scenarios across broad synthetic tasks and human-mobility data.The paper connects this approach to prior work on private contingency tables, collective graphical models, and private probabilistic inference.
2. Background and Problem Statement
The paper formulates private learning of positive discrete Markov random fields with fixed cliques and evaluates accuracy using divergence or holdout likelihood. Differential privacy is achieved by adding Laplace noise calibrated to the sensitivity of data-derived statistics, with privacy-preserving post-processing allowed thereafter.
- Differential Privacy: Differential privacy bounds how much an individual’s record can affect an algorithm, comparing datasets that differ by one individual’s data vector.The formal definition permits parameters ϵ and δ; the proposed algorithms use δ=0, while some baselines use weaker (ϵ, δ)-privacy.
- Differential Privacy: The Laplace mechanism releases f(X)+z with independent Laplace noise scaled by the global sensitivity Δf divided by ϵ.Sensitivity is the maximum neighboring-dataset change in the L1 norm, and subsequent post-processing does not weaken privacy.
- 2.2. Problem Statement: The task is to learn an accurate, ϵ-differentially private distribution p(x; ˆθ) in the class of discrete undirected graphical models, also called Markov random fields.Accuracy is measured by Kullback–Leibler divergence in synthetic experiments and holdout log-likelihood on real data.
- 2.2. Problem Statement: A graphical model represents p(x) with positive local clique potentials ψC(xC), whose products are normalized by the partition function Z.The graph connects attributes that co-occur in a clique, making each index set C a clique in the independence graph.
- 2.2. Problem Statement: The log-linear form uses indicator sufficient statistics for clique assignments, log-potentials θC(iC), and the log-partition function A(θ)=log Z(θ).Strict positivity of the potentials implies p(x; θ)>0 for every x.
- 2.2. Problem Statement: The model structure is fixed in advance: privately selecting which cliques to include, or structure learning, is outside the paper’s scope.
3. Approach
The approach releases noisy contingency-table sufficient statistics under differential privacy, analyzes naive MLE, and develops CGM-based EM inference to address its limitations.
- Maximum-likelihood estimation: The likelihood depends on the data only through clique contingency tables, which are sufficient statistics for estimating graphical-model parameters.MLE adjusts parameters so model and data marginals match, with uniqueness of the distribution requiring data marginals in the marginal polytope's interior.
- Noisy sufficient statistics: Sufficient-statistics perturbation adds Laplace noise to contingency tables before MLE, whereas output perturbation adds noise directly to the learned parameters.The sensitivity of sufficient statistics is tightly analyzable and equals the number of cliques for every input dataset.
- Naive MLE: Naive MLE using noisy statistics is asymptotically unbiased and consistent, with learned distributions converging to the true graphical model under iid sampling.Its marginal estimates have a mean-squared-error decomposition, while the estimator maximizes the likelihood formed from noisy sufficient statistics.
- Naive MLE: Privacy noise can dominate sampling error at practical population sizes, while projection and regularization address invalid marginals and zero-induced MLE pathologies.Projected marginals can remain inconsistent across cliques, and excessive regularization can underfit while insufficient regularization can produce very large KL divergence.
- Collective Graphical Models: The principled alternative treats true sufficient statistics as latent variables and uses CGM inference within EM to compute their conditional expectation given noisy observations.The joint model p(n, y; θ) combines the graphical-model distribution over sufficient statistics with the privacy mechanism p(y | n).
4. Experiments
Experiments compare Naive MLE, CGM, and PSGD on synthetic graphical models and human mobility data under varying population sizes and privacy levels. CGM generally improves model quality over Naive MLE and PSGD, but incurs greater computational cost.
- Synthetic data: CGM improves upon Naive MLE across synthetic models, privacy levels, and population sizes, while PSGD cannot attain some smaller ϵ values under δ = 1/N.Figure 2 reports KL divergence as a function of population size across privacy levels for third-order chains and ER graphs.
- Synthetic data: CGM learns edge marginals closer to the true and non-private marginals than Naive MLE on an ER graph.Naive MLE is fastest; CGM is approximately 4x slower on third-order chains and 8x slower on ER graphs, while PSGD is approximately 27x/40x slower.
- Wifi data: Wifi preprocessing normalizes each individual’s contributions so sensitivity equals the number of model edges, but biases the model toward individuals with fewer transitions.Each user contributes 1/K to each contingency table for which the user’s values are not both null.
- Wifi data: On wifi data, CGM improves upon Naive MLE across privacy regimes, population sizes, and privacy strengths, while both outperform PSGD.Holdout log-likelihood is evaluated after training on 75% of the 124,399 prepared individuals and testing on the remaining 25%.
- Wifi data: Naive MLE is fastest, whereas CGM is approximately 15x slower and PSGD approximately 46x slower on the wifi experiment.The wifi model is a time-homogeneous chain with shared adjacent-time potentials and a node potential for stationarity.
A. Extra Proofs
The proofs establish sensitivity and distributional properties of noisy sufficient statistics, then connect inferred marginals to a uniquely defined graphical-model distribution. They also state the positivity condition needed for convergence to the true model.
- Sensitivity: Each individual contributes one count to every clique contingency table, so the local and global sensitivity equal the number of cliques, |C|.This establishes the sensitivity used to calibrate noise for the contingency-table release.
- Noisy marginals: The noisy marginal estimator is unbiased because the Laplace noise has zero mean, and its mean-squared error equals its variance.The sampling count and privacy noise are independent, enabling the variance decomposition used in the proof.
- Consistency: The learned distribution converges to the true model when the true marginals lie in the interior of the marginal polytope, guaranteed here by strict positivity.The argument combines consistency of the marginals with the stated positivity condition.
- Distribution construction: For any marginals, the factorized graphical-model family contains a unique distribution with those marginals, defining q(x) from the inferred marginal vector.The mapping from parameters to distributions is many-to-one, but the marginal vector uniquely determines the distribution within the model family.