Privacy and efficiency guaranteed social subgraph matching

Kai Huang, Haibo Hu, Shuigeng Zhou, Jihong Guan, Qingqing Ye, Xiaofang Zhou

Research output: Journal article publicationJournal articleAcademic researchpeer-review

12 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)581-602
Number of pages22
JournalVLDB Journal
Issue number3
Publication statusPublished - May 2022


  • (k, t)-privacy
  • Label generalization
  • Subgraph matching

ASJC Scopus subject areas

  • Information Systems
  • Hardware and Architecture


Dive into the research topics of 'Privacy and efficiency guaranteed social subgraph matching'. Together they form a unique fingerprint.

Cite this