Personalized Sampling Graph Collection with Local Differential Privacy for Link Prediction

Link prediction (LP) is an attractive research problem on social network data. Yet, the link information may be leaked by the untrusted collector. As countermeasures, there are a few methods specially designed for link prediction under local differential privacy (LDP), which allow the third-party data collector collects user data for link prediction while protecting user connection privacy. In this paper, we propose a Community-based graph collection with Personalized sampling Randomized Response (CPRR) which is a novel graph collection algorithm with LDP and reaches decent trade-off between sensitive link protection and link prediction performance. The proposed mechanism adopts a personalized sampling technique for each connection of a user and then utlizes the randomized response mechanism on the sampled subset. Based on the personalized sampling technique, we can reduce the injected noise in LDP. Meanwhile, considering the different edge distributions of the different regions on the original graph, we propose a community-based sampling strategy. Then, we prove that the proposed CPRR satisfies LDP. %We compare the performance of CPRR and other privacy-preserving graph collection methods under LDP in terms of link prediction accuracy. Through extensive experiments on several real-life graph datasets, we demonstrate that CPRR can achieve better results in balancing privacy protection and link prediction performance than the state-of-art baselines