论文标题
图形laplacian光谱的节点和边缘差异隐私：机制和缩放定律
Node and Edge Differential Privacy for Graph Laplacian Spectra: Mechanisms and Scaling Laws
论文作者
论文摘要
本文开发了一个框架，用于使用差异隐私使用差异图私有化图形的图形laplacian的范围。我们考虑两个隐私配方。第一个混淆了图中边缘的存在，第二个则混淆了节点的存在。我们比较了这两个隐私公式，并表明认为边缘的隐私公式更适合大多数工程应用程序。我们使用有界的拉普拉斯机制为图laplacian的特征值提供差异性隐私，我们特别注意代数连接性，该代数连接性是Laplacian的第二小特征值。分析范围是关于机制的准确性和用私有光谱计算的某些图形特性的。一套数字示例证实了私人光谱在实践中的准确性。
This paper develops a framework for privatizing the spectrum of the graph Laplacian of an undirected graph using differential privacy. We consider two privacy formulations. The first obfuscates the presence of edges in the graph and the second obfuscates the presence of nodes. We compare these two privacy formulations and show that the privacy formulation that considers edges is better suited to most engineering applications. We use the bounded Laplace mechanism to provide differential privacy to the eigenvalues of a graph Laplacian, and we pay special attention to the algebraic connectivity, which is the Laplacian's second smallest eigenvalue. Analytical bounds are presented on the the accuracy of the mechanisms and on certain graph properties computed with private spectra. A suite of numerical examples confirms the accuracy of private spectra in practice.
