Privacy-preserving subgraph discovery

Danish Mehmood, Basit Shafiq, Jaideep Vaidya, Yuan Hong, Nabil Adam, Vijayalakshmi Atluri

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations


Graph structured data can be found in many domains and applications. Analysis of such data can give valuable insights. Frequent subgraph discovery, the problem of finding the set of subgraphs that is frequent among the underlying database of graphs, has attracted a lot of recent attention. Many algorithms have been proposed to solve this problem. However, all assume that the entire set of graphs is centralized at a single site, which is not true in a lot of cases. Furthermore, in a lot of interesting applications, the data is sensitive (for example, drug discovery, clique detection, etc). In this paper, we address the problem of privacy-preserving subgraph discovery. We propose a flexible approach that can utilize any underlying frequent subgraph discovery algorithm and uses cryptographic primitives to preserve privacy. The comprehensive experimental evaluation validates the feasibility of our approach.

Original languageEnglish (US)
Title of host publicationData and Applications Security and Privacy XXVI - 26th Annual IFIP WG 11.3 Conference, DBSec 2012, Proceedings
Number of pages16
StatePublished - 2012
Event26th Annual WG 11.3 Conference on Data and Applications Security and Privacy, DBSec 2012 - Paris, France
Duration: Jul 11 2012Jul 13 2012

Publication series

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


Other26th Annual WG 11.3 Conference on Data and Applications Security and Privacy, DBSec 2012

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Privacy-preserving subgraph discovery'. Together they form a unique fingerprint.

Cite this