Differentially Private Link Prediction with Protected Connections


  • Abir De IIT Bombay
  • Soumen Chakrabarti IIT Bombay




Social Networks, Security


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.




How to Cite

De, A., & Chakrabarti, S. (2021). Differentially Private Link Prediction with Protected Connections. Proceedings of the AAAI Conference on Artificial Intelligence, 35(1), 63-71. https://doi.org/10.1609/aaai.v35i1.16078



AAAI Technical Track on Application Domains