Timezone: »

 
Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank
Alessandro Epasto · Vahab Mirrokni · Bryan Perozzi · Anton Tsitsulin · Peilin Zhong

@
in New Frontiers in Graph Learning »
Event URL: https://openreview.net/forum?id=dzVZGSe0NoJ »

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.

Keywords: graph algorithms · differential privacy · ranking · Personalized Page Rank

Author Information

Alessandro Epasto (Google)
Alessandro Epasto

I am a staff research scientist at Google, New York working in the OMEGA team part of the Google Research and lead by Vahab Mirrokni. I received a Ph.D in computer science from Sapienza University of Rome, where I was advised by Professor Alessandro Panconesi and supported by the Google Europe Ph.D. Fellowship in Algorithms. I was also a post-doc at the department of computer science of Brown University in Providence (RI), USA where I was advised by Professor Eli Upfal. My research interests include algorithmic problems in machine learning and data mining, in particular in the areas of clustering, and privacy.

Vahab Mirrokni (Google Research)
Bryan Perozzi (Google Research)
Anton Tsitsulin (Google)
Peilin Zhong (Google)

More from the Same Authors