A privacy-preserving framework for subgraph pattern matching in cloud

Jiuru Gao, Jiajie Xu, Guanfeng Liu, Wei Chen, Hongzhi Yin, Lei Zhao*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

4 Citations (Scopus)


The growing popularity of storing large data graphs in cloud has inspired the emergence of subgraph pattern matching on a remote cloud, which is usually defined in terms of subgraph isomorphism. However, it is an NP-complete problem and too strict to find useful matches in certain applications. In addition, there exists another important concern, i.e., how to protect the privacy of data graphs in subgraph pattern matching without undermining matching results. To tackle these problems, we propose a novel framework to achieve the privacy-preserving subgraph pattern matching via strong simulation in cloud. Firstly, we develop a k-automorphism model based method to protect structural privacy in data graphs. Additionally, we use a cost-model based label generalization method to protect label privacy in both data graphs and pattern graphs. Owing to the symmetry in a k-automorphic graph, the subgraph pattern matching can be answered using the outsourced graph, which is only a subset of a k-automorphic graph. The efficiency of subgraph pattern matching can be greatly improved by this way. Extensive experiments on real-world datasets demonstrate the high efficiency and effectiveness of our framework.

Original languageEnglish
Title of host publicationDatabase Systems for Advanced Applications
Subtitle of host publication23rd International Conference, DASFAA 2018 Gold Coast, QLD, Australia, May 21–24, 2018 Proceedings, Part I
EditorsJian Pei, Yannis Manolopoulos, Shazia Sadiq, Jianxin Li
Place of PublicationCham, Switzerland
PublisherSpringer, Springer Nature
Number of pages16
ISBN (Electronic)9783319914527
ISBN (Print)9783319914510
Publication statusPublished - 2018
Externally publishedYes
Event23rd International Conference on Database Systems for Advanced Applications, DASFAA 2018 - Gold Coast, Australia
Duration: 21 May 201824 May 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10827 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference23rd International Conference on Database Systems for Advanced Applications, DASFAA 2018
CityGold Coast


  • k-automorphism
  • Label generalization
  • Privacy-preserving
  • Strong simulation
  • Subgraph pattern matching


Dive into the research topics of 'A privacy-preserving framework for subgraph pattern matching in cloud'. Together they form a unique fingerprint.

Cite this