For graphs generated from stochastic blockmodels, adjacency spectral
embedding is asymptotically consistent. Further, adjacency spectral embedding
composed with universally consistent classifiers is universally consistent to
achieve the Bayes error. However when the graph contains private or sensitive
information, treating the data as non-private can potentially leak privacy and
incur disclosure risks. In this paper, we propose a differentially private
adjacency spectral embedding algorithm for stochastic blockmodels. We
demonstrate that our proposed methodology can estimate the latent positions
close to, in Frobenius norm, the latent positions by adjacency spectral
embedding and achieve comparable accuracy at desired privacy parameters in
simulated and real world networks.

该论文提出了一种差分隐私邻接谱嵌入算法，用于随机块模型，实现了邻接谱嵌入的近似一致性，并且在确定的隐私参数下，可以实现与邻接谱嵌入相当的准确性。

隐私保护的随机块模型邻接谱嵌入

Privacy Preserving Adjacency Spectral Embedding on Stochastic  Blockmodels

We develop differentially private methods for estimating various
distributional properties. Given a sample from a discrete distribution $p$,
some functional $f$, and accuracy and privacy parameters $\alpha$ and
$\varepsilon$, the goal is to estimate $f(p)$ up to accuracy $\alpha$, while
maintaining $\varepsilon$-differential privacy of the sample.
We prove almost-tight bounds on the sample size required for this problem for
several functionals of interest, including support size, support coverage, and
entropy. We show that the cost of privacy is negligible in a variety of
settings, both theoretically and experimentally. Our methods are based on a
sensitivity analysis of several state-of-the-art methods for estimating these
properties with sublinear sample complexities.

本论文提出了一种隐私保护的差分私有方法，基于几种最先进的方法进行灵敏度分析，以实现估计分布属性方面的准确性，同时保持样本的 ε- 差分隐私，并在几种感兴趣的功能上证明了问题所需的样本大小的近乎严格的边界。

INSPECTRE: 估算未知部分的隐私方法

INSPECTRE: Privately Estimating the Unseen

We propose a novel framework for the differentially private ERM, input
perturbation. Existing differentially private ERM implicitly assumed that the
data contributors submit their private data to a database expecting that the
database invokes a differentially private mechanism for publication of the
learned model. In input perturbation, each data contributor independently
randomizes her/his data by itself and submits the perturbed data to the
database. We show that the input perturbation framework theoretically
guarantees that the model learned with the randomized data eventually satisfies
differential privacy with the prescribed privacy parameters. At the same time,
input perturbation guarantees that local differential privacy is guaranteed to
the server. We also show that the excess risk bound of the model learned with
input perturbation is $O(1/n)$ under a certain condition, where $n$ is the
sample size. This is the same as the excess risk bound of the state-of-the-art.

提出了一种新的差分隐私 ERM 框架：输入扰动。在这种框架中，每个数据贡献者独立地对其数据进行随机化并将扰动数据提交给数据库。我们证明了该框架在一定条件下，确保了使用随机化数据学习到的模型最终满足差分隐私，同时确保本地差分隐私得到了保证。该方法也展示了有关模型的风险界限。