Differentially Private Link Prediction With Protected Connections
arXiv:1908.04849
Abstract
Link prediction (LP) algorithms propose to each node a ranked list of nodes that are currently non-neighbors, as the most likely candidates for future linkage. Owing to increasing concerns about privacy, users (nodes) may prefer to keep some of their connections protected or private. Motivated by this observation, our goal is to design a differentially private LP algorithm, which trades off between privacy of the protected node-pairs and the link prediction accuracy. More specifically, we first propose a form of differential privacy on graphs, which models the privacy loss only of those node-pairs which are marked as protected. Next, we develop DPLP , a learning to rank algorithm, which applies a monotone transform to base scores from a non-private LP system, and then adds noise. DPLP is trained with a privacy induced ranking loss, which optimizes the ranking utility for a given maximum allowed level of privacy leakage of the protected node-pairs. Under a recently-introduced latent node embedding model, we present a formal trade-off between privacy and LP utility. Extensive experiments with several real-life graphs and several LP heuristics show that DPLP can trade off between privacy and predictive performance more effectively than several alternatives.
References in corpus (13)
- Emergence of scaling in random networks
- Semi-Supervised Classification with Graph Convolutional Networks
- Deep Learning with Differential Privacy
- Finding community structure in networks using the eigenvectors of matrices
- Link Prediction in Complex Networks: A Survey
- struc2vec: Learning Node Representations from Structural Identity
- Kronecker Graphs: An Approach to Modeling Networks
- Effective and Efficient Similarity Index for Link Prediction of Complex Networks
- Empirical Bernstein Bounds and Sample Variance Penalization
- Optimal Noise-Adding Mechanism in Additive Differential Privacy
- Differentially Private Continual Release of Graph Statistics
- Fast Differentially Private Matrix Factorization
- Privacy for the Protected (Only)