Skip to main content
Presentation
Privacy-Preserving Spectral Analysis of Large Graphs in Public Clouds
Proceedings of the 11th ACM on Asia Conference on Computer and Communications Security
  • Sagar Sharma, Wright State University - Main Campus
  • James L. Powers, Wright State University - Main Campus
  • Keke Chen, Wright State University - Main Campus
Document Type
Conference Proceeding
Publication Date
1-1-2016
Abstract
Large graph datasets have become invaluable assets for studying problems in business applications and scientific research. These datasets, collected and owned by data owners, may also contain privacy-sensitive information. When using public clouds for elastic processing, data owners have to protect both data ownership and privacy from curious cloud providers. We propose a cloud-centric framework that allows data owners to efficiently collect graph data from the distributed data contributors, and privately store and analyze graph data in the cloud. Data owners can conduct expensive operations in untrusted public clouds with privacy and scalability preserved. The major contributions of this work include two privacy-preserving approximate eigen decomposition algorithms (the secure Lanczos and Nystrom methods) for spectral analysis of large graph matrices, and a personalized privacy-preserving data submission method based on differential privacy that allows for the trade-off between data sparsity and privacy. For a N-node graph, the proposed approach allows a data owner to finish the core operations with only O(N) client-side costs in computation, storage, and communication. The expensive O(N2) operations are performed in the cloud with the proposed privacy-preserving algorithms. We prove that our approach can satisfactorily preserve data privacy against the untrusted cloud providers. We have conducted an extensive experimental study to investigate these algorithms in terms of the intrinsic relationships among costs, privacy, scalability, and result quality.
DOI
10.1145/2897845.2897857
Citation Information
Sagar Sharma, James L. Powers and Keke Chen. "Privacy-Preserving Spectral Analysis of Large Graphs in Public Clouds" Proceedings of the 11th ACM on Asia Conference on Computer and Communications Security (2016) p. 71 - 82 ISSN: 9781450342339
Available at: http://works.bepress.com/keke_chen/50/