nips nips2013 nips2013-25 nips2013-25-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Krzysztof M. Choromanski, Tony Jebara, Kui Tang
Abstract: The adaptive anonymity problem is formalized where each individual shares their data along with an integer value to indicate their personal level of desired privacy. This problem leads to a generalization of k-anonymity to the b-matching setting. Novel algorithms and theory are provided to implement this type of anonymity. The relaxation achieves better utility, admits theoretical privacy guarantees that are as strong, and, most importantly, accommodates a variable level of anonymity for each individual. Empirical results confirm improved utility on benchmark and social data-sets.
[1] G. Aggarwal, T. Feder, K. Kenthapadi, R. Motwani, R. Panigrahy, D. Thomas, and A. Zhu. Approximation algorithms for k-anonymity. Journal of Privacy Technology, 2005.
[2] M. Allman and V. Paxson. Issues and etiquette concerning use of shared measurement data. In Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, 2007.
[3] M. Bugliesi, B. Preneel, V. Sassone, I Wegener, and C. Dwork. Lecture Notes in Computer Science - Automata, Languages and Programming, chapter Differential Privacy. Springer Berlin / Heidelberg, 2006.
[4] K. Chaudhuri, C. Monteleone, and A.D. Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, (12):1069–1109, 2011.
[5] G. Cormode, D. Srivastava, S. Bhagat, and B. Krishnamurthy. Class-based graph anonymization for social network data. In PVLDB, volume 2, pages 766–777, 2009.
[6] G. Cormode, D. Srivastava, T. Yu, and Q. Zhang. Anonymizing bipartite graph data using safe groupings. VLDB J., 19(1):115–139, 2010.
[7] R. Duan and S. Pettie. Approximating maximum weight matching in near-linear time. In Proceedings 51st Symposium on Foundations of Computer Science, 2010.
[8] J. Edmonds. Paths, trees and flowers. Canadian Journal of Mathematics, 17, 1965.
[9] H.N. Gabow. An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In Proceedings of the fifteenth annual ACM symposium on Theory of computing, 1983.
[10] A. Gionis, A. Mazza, and T. Tassa. k-anonymization revisited. In ICDE, 2008.
[11] B. Huang and T. Jebara. Fast b-matching via sufficient selection belief propagation. In Artificial Intelligence and Statistics, 2011.
[12] M.I. Jordan, Z. Ghahramani, T. Jaakkola, and L.K. Saul. An introduction to variational methods for graphical models. Machine Learning, 37(2):183–233, 1999.
[13] V.N. Kolmogorov. Blossom V: A new implementation of a minimum cost perfect matching algorithm. Mathematical Programming Computation, 1(1):43–67, 2009.
[14] N. Li, T. Li, and S. Venkatasubramanian. t-closeness: Privacy beyond k-anonymity and ldiversity. In ICDE, 2007.
[15] S. Lodha and D. Thomas. Probabilistic anonymity. In PinKDD, 2007.
[16] A. Machanavajjhala, D. Kifer, J. Gehrke, and M. Venkitasubramaniam. L-diversity: Privacy beyond k-anonymity. ACM Transactions on Knowledge Discovery from Data (TKDD), 1, 2007.
[17] A. Meyerson and R. Williams. On the complexity of optimal k-anonymity. In PODS, 2004.
[18] P. Samarati and L. Sweeney. Generalizing data to provide anonymity when disclosing information. In PODS, 1998.
[19] L. Sweeney. Achieving k-anonymity privacy protection using generalization and suppression. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 10(5):571– 588, 2002.
[20] Y. Tao and X. Xiao. Personalized privacy preservation. In SIGMOD Conference, 2006.
[21] Y. Tao and X. Xiao. Personalized privacy preservation. In Privacy-Preserving Data Mining, 2008.
[22] O. Williams and F. McSherry. Probabilistic inference and differential privacy. In NIPS, 2010.
[23] M. Xue, P. Karras, C. Rassi, J. Vaidya, and K.-L. Tan. Anonymizing set-valued data by nonreciprocal recoding. In KDD, 2012.
[24] E. Zheleva and L. Getoor. Preserving the privacy of sensitive relationships in graph data. In KDD, 2007. 9