Locally Differentially Private Graph Clustering via the Power Iteration Method
Vorapong Suppakitpaisarn and Sayan Mukherjee
我们提出了一个局部差分私有图聚类算法。 以前的工作已经探讨了这个问题,包括将光谱聚类应用于通过随机响应算法生成的图形的方法。 但是,这些方法只有在隐私预算为Ω(log n)时才能达到准确的结果,这不适合许多实际应用。 作为回应,我们提出了一个基于功率迭代方法的交互式算法。 鉴于最大的特征向量常数引入的噪声可能很大,我们采用了一种技术来消除这种常数。 因此,我们的算法在图形优砥如缀且 Ω̃(√(n) 的最小度)时,通过恒定的隐私预算获得本地差分隐私。 相比之下,虽然随机响应已被证明在相同的最小度条件下产生准确的结果,但它仅限于从随机块模型生成的图形。 我们进行实验以证明我们的方法优于应用于随机反应结果的光谱聚类。
We propose a locally differentially private graph clustering algorithm. Previous works have explored this problem, including approaches that apply spectral clustering to graphs generated via the randomized response algorithm. However, these methods only achieve accurate results when the privacy budget is in Ω(log n), which is unsuitable for many practical applications. In response, we present an interactive algorithm based on the power iteration method. Given that the noise introduced by the lar...