论文标题
通过敏感性的个性化Pagerank进行差异私人图形学习
Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank
论文作者
论文摘要
个性化Pagerank（PPR）是无监督学习图表（例如节点排名，标签和图形嵌入）的基本工具。但是，尽管数据隐私是最近的最重要问题之一，但现有的PPR算法并非旨在保护用户隐私。 PPR对输入图边缘高度敏感：仅一个边缘的差异可能会导致PPR矢量发生很大变化，并可能泄漏私人用户数据。 在这项工作中，我们提出了一种算法，该算法可输出近似PPR，并证明对输入边缘的敏感性有限。此外，我们证明，当输入图具有较大的程度时，我们的算法与非私有算法相似。我们的敏感性构造的PPR直接暗示着用于多种图形学习工具的私有算法，例如差异私有（DP）PPR排名，DP节点分类和DP节点嵌入。为了补充我们的理论分析，我们还经验验证了算法的实际表现。
Personalized PageRank (PPR) is a fundamental tool in unsupervised learning of graph representations such as node ranking, labeling, and graph embedding. However, while data privacy is one of the most important recent concerns, existing PPR algorithms are not designed to protect user privacy. PPR is highly sensitive to the input graph edges: the difference of only one edge may cause a big change in the PPR vector, potentially leaking private user data. In this work, we propose an algorithm which outputs an approximate PPR and has provably bounded sensitivity to input edges. In addition, we prove that our algorithm achieves similar accuracy to non-private algorithms when the input graph has large degrees. Our sensitivity-bounded PPR directly implies private algorithms for several tools of graph learning, such as, differentially private (DP) PPR ranking, DP node classification, and DP node embedding. To complement our theoretical analysis, we also empirically verify the practical performances of our algorithms.
