We consider differentially private range queries on a graph where query ranges are defined as the set of edges on a shortest path of the graph. Edges in the graph carry sensitive attributes and the goal is to report the sum of these attributes on a shortest path for counting query or the minimum of the attributes in a bottleneck query. We use differential privacy to ensure that the release of these query answers provide protection of the privacy of the sensitive edge attributes. Our goal is to develop mechanisms that minimize the additive error of the reported answers with the given privacy budget.
In this talk I will report new results for private range queries on shortest paths. For counting range queries we can achieve an additive error of $O(n^{1/3})$ for ε-DP and $O(n^{1/4})$ for (ε,δ)-DP. We present two algorithms where we control the final error by carefully balancing perturbation added to the edge attributes directly versus perturbation added to a subset of range query answers (which can be used for other range queries). Bottleneck range queries are easier and can be answered with polylogarithmic additive errors using standard techniques.
This is joint work with Chengyuan Deng, Jalaj Upadhyay and Chen Wang. It was presented at WADS’23.
Bio: Jie Gao is currently a Professor at Computer Science department of Rutgers University. From 2005-2019 she was on the faculty of Computer Science department of Stony Brook University. She received Ph.D degree from Stanford University under the supervision of Leo Guibas in 2004 and B.Eng from University of Science andcp Technology of China in 1999. She received the NSF career award in 2006, IMC best paper award (2009), EWSN best paper award (2021) and multiple Research Excellence Awards in computer science department of Stony Brook. She currently serves on the editorial board of ACM Transactions on Sensor Networks, International Journal of Computational Geometry and Applications and IEEE Transactions on Network Science and Engineering. She published over 150 referred papers in computer networking and theoretical computer science fields, and has graduated 17 Ph.D students.