Structure-Preserving Subgraph Query Services

Zhe Fan*, Byron Choi, Qian Chen, Jianliang Xu, Haibo Hu, Sourav S. Bhowmick

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

15 Citations (Scopus)
20 Downloads (Pure)


A fundamental problem of graph databases is subgraph isomorphism query (a.k.a subgraph query): given a query graph Q and a graph database, it retrieves the graphs Gs from the database that contain Q. Due to the cost of managing massive data coupled with the computational hardness of subgraph isomorphism testing, outsourcing the computations to a third-party provider is an appealing alternative. However, confidentiality has been a critical attribute of quality of service (QoS) in query services. To the best of our knowledge, subgraph query services with tunable preservation of privacy of structural information have never been addressed. In this paper, we present the first work on structure-preserving subIso (SPsubIso). A crucial step of our work is to transform subIso-the seminal subgraph isomorphism algorithm (the Ullmann's algorithm)-into a series of matrix operations. We propose a novel cyclic group based encryption (CGBE) method for private matrix operations. We propose a protocol that involves the query client and static indexes to optimize SPsubIso. We prove that the structural information of both Q and G are preserved under CGBE and analyze the privacy preservation in the presence of the optimizations. Our extensive experiments on both real and synthetic datasets verify that SPsubIso is efficient and the optimizations are effective.

Original languageEnglish
Article number7029663
Pages (from-to)2275-2290
Number of pages16
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number8
Early online date3 Feb 2015
Publication statusPublished - 1 Aug 2015

Scopus Subject Areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

User-Defined Keywords

  • outsourced graph databases
  • structure-preserving query processing
  • Subgraph isomorphism search


Dive into the research topics of 'Structure-Preserving Subgraph Query Services'. Together they form a unique fingerprint.

Cite this