Adam Sealfon
ABSTRACT
We introduce a model for differentially private analysis of weighted graphs in which the graph topology (υ,ε) is assumed to be public and the private information consists only of the edge weights ω : ε → R+. This can express hiding congestion patterns in a known system of roads. Differential privacy requires that the output of an algorithm provides little advantage, measured by privacy parameters ε and δ, for distinguishing between neighboring inputs, which are thought of as inputs that differ on the contribution of one individual. In our model, two weight functions w,w' are considered to be neighboring if they have l1 distance at most one.
We study the problems of privately releasing a short path between a pair of vertices and of privately releasing approximate distances between all pairs of vertices. We are concerned with the approximation error, the difference between the length of the released path or released distance and the length of the shortest path or actual distance.
For the problem of privately releasing a short path between a pair of vertices, we prove a lower bound of Ω(|υ|) on the additive approximation error for fixed privacy parameters ε,δ. We provide a differentially private algorithm that matches this error bound up to a logarithmic factor and releases paths between all pairs of vertices, not just a single pair. The approximation error achieved by our algorithm can be bounded by the number of edges on the shortest path, so we achieve better accuracy than the worst-case bound for pairs of vertices that are connected by a low-weight path consisting of o(|υ|) vertices.
For the problem of privately releasing all-pairs distances, we show that for trees we can release all-pairs distances with approximation error $O(log2.5|υ|) for fixed privacy parameters. For arbitrary bounded-weight graphs with edge weights in [0,M] we can brelease all distances with approximation error Õ(√>(|υ|M).
- Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The johnson-lindenstrauss transform itself preserves differential privacy. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 410--419. IEEE, 2012. Google Scholar
Digital Library
- Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. Differentially private data analysis of social networks via restricted sensitivity. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 87--96. ACM, 2013. Google ScholarDigital Library
- Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions. arXiv preprint arXiv:1504.07553, 2015.Google Scholar
- GJ Chang and GL Nemhauser. The k-domination and k-stability problem on graphs. Techn. Report, 540, 1982.Google Scholar
- TH Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. In Automata, Languages and Programming, pages 405--417. Springer, 2010. Google ScholarDigital Library
- 6}DKMMN06Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology-EUROCRYPT 2006, pages 486--503. Springer, 2006. Google ScholarDigital Library
- Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography, pages 265--284. Springer, 2006. Google ScholarDigital Library
- Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 715--724. ACM, 2010. Google ScholarDigital Library
- Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Theoretical Computer Science, 9(3--4):211--407, 2013. Google ScholarDigital Library
- Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pages 51--60. IEEE, 2010. Google ScholarDigital Library
- 0}GLMRT10Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1106--1125. Society for Industrial and Applied Mathematics, 2010. Google ScholarDigital Library
- Anupam Gupta, Aaron Roth, and Jonathan Ullman. Iterative constructions and private data release. In Theory of Cryptography, pages 339--356. Springer, 2012. Google ScholarDigital Library
- Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden, and Zhiwei Steven Wu. Private matchings and allocations. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 21--30. ACM, 2014. Google ScholarDigital Library
- Michael Hay, Chao Li, Gerome Miklau, and David Jensen. Accurate estimation of the degree distribution of private networks. In Data Mining, 2009. ICDM'09. Ninth IEEE International Conference on, pages 169--178. IEEE, 2009. Google ScholarDigital Library
- Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Analyzing graphs with node differential privacy. In Theory of Cryptography, pages 457--476. Springer, 2013. Google ScholarDigital Library
- Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, and Grigory Yaroslavtsev. Private analysis of graph structure. Proceedings of the VLDB Endowment, 4(11):1146--1157, 2011.Google ScholarDigital Library
- A Meir and JW Moon. Relations between packing and covering numbers of a tree. Pacific J. Math, 61(1):225--233, 1975.Google ScholarCross Ref
- Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 75--84. ACM, 2007. Google ScholarDigital Library
- Stanley L Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63--69, 1965.Google ScholarCross Ref
Index Terms
- Shortest Paths and Distances with Differential Privacy
Recommendations
Improved algorithms for the k simple shortest paths and the replacement paths problems
Given a directed, non-negatively weighted graph G=(V,E) and s,t@?V, we consider two problems. In the k simple shortest paths problem, we want to find the k simple paths from s to t with the k smallest weights. In the replacement paths problem, we want ...
Replacement paths and k simple shortest paths in unweighted directed graphs
Let G = (V,E) be a directed graph and let P be a shortest path from s to t in G. In the replacement paths problem, we are required to find, for every edge e on P, a shortest path from s to t in G that avoids e. The only known algorithm for solving the ...
Edge types vs privacy in K-anonymization of shortest paths
Information breaches in social networks and other published data have caused many concerns of privacy issues in recent years. Since information in networks can be modeled as graphs, various techniques have been proposed to preserve privacy of sensitive ...
Comments