TY - JOUR
T1 - Privacy and efficiency guaranteed social subgraph matching
AU - Huang, Kai
AU - Hu, Haibo
AU - Zhou, Shuigeng
AU - Guan, Jihong
AU - Ye, Qingqing
AU - Zhou, Xiaofang
N1 - Funding Information:
This work was supported by National Natural Science Foundation of China (Grant Nos: 62072390, U1936205, U1636205, 61572413, 62072125) and the Research Grants Council, Hong Kong SAR, China (Grant Nos: 15238116, 15222118, 15218919, 15203120).
Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature.
PY - 2022/5
Y1 - 2022/5
N2 - 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.
AB - 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.
KW - (k, t)-privacy
KW - Label generalization
KW - Subgraph matching
UR - http://www.scopus.com/inward/record.url?scp=85118858592&partnerID=8YFLogxK
U2 - 10.1007/s00778-021-00706-0
DO - 10.1007/s00778-021-00706-0
M3 - Journal article
AN - SCOPUS:85118858592
SN - 1066-8888
VL - 31
SP - 581
EP - 602
JO - VLDB Journal
JF - VLDB Journal
IS - 3
ER -