Private Approximation of Graph Spectra and Cuts via Spectral Amplifiers

本文研究在边级别差分隐私保护下发布合成图的问题，要求该合成图能近似原始输入图中所有切割的大小。作者提出一种多项式时间的 (ε,δ)-差分隐私算法，对于任意 n 顶点无权重图 G，输出一个非负权重合成图 Ĝ，使得对于任意切割 S，其权重误差以

历史摘要 · 未重新核验 · arXiv cs.CR