Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/95719
Title: | Privacy and efficiency guaranteed social subgraph matching | Authors: | Huang, K Hu, H Zhou, S Guan, J Ye, Q Zhou, X |
Issue Date: | May-2022 | Source: | VLDB journal, May 2022, v. 31, no. 3, p. 581-602 | Abstract: | Due to the increasing cost of data storage and computation, more and more graphs (e.g., web graphs, social networks) are outsourced and analyzed in the cloud. However, there is growing concern on the privacy of these outsourced graphs at the hands of untrusted cloud providers. Unfortunately, simple label anonymization cannot protect nodes from being re-identified by adversary who knows the graph structure. To address this issue, existing works adopt the k-automorphism model, which constructs (k- 1) symmetric vertices for each vertex. It has two disadvantages. First, it significantly enlarges the graphs, which makes graph mining tasks such as subgraph matching extremely inefficient and sometimes infeasible even in the cloud. Second, it cannot protect the privacy of attributes in each node. In this paper, we propose a new privacy model (k, t)-privacy that combines the k-automorphism model for graph structure with the t-closeness privacy model for node label generalization. Besides a stronger privacy guarantee, the paper also optimizes the matching efficiency by (1) an approximate label generalization algorithm TOGGLE with (1 + ϵ) approximation ratio and (2) a new subgraph matching algorithm PGP on succinct k-automorphic graphs without decomposing the query graph. | Keywords: | (K, t)-privacy Label generalization Subgraph matching |
Publisher: | Springer | Journal: | VLDB journal | ISSN: | 1066-8888 | EISSN: | 0949-877X | DOI: | 10.1007/s00778-021-00706-0 | Rights: | © The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature 2021 This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use (https://www.springernature.com/gp/open-research/policies/accepted-manuscript-terms), but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/s00778-021-00706-0. |
Appears in Collections: | Journal/Magazine Article |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Huang_Privacy_Efficiency_Guaranteed.pdf | Pre-Published version | 2.67 MB | Adobe PDF | View/Open |
Page views
80
Last Week
3
3
Last month
Citations as of Sep 22, 2024
Downloads
82
Citations as of Sep 22, 2024
SCOPUSTM
Citations
15
Citations as of Sep 26, 2024
WEB OF SCIENCETM
Citations
14
Citations as of Sep 26, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.