2013 MiningFrequentGraphPatternswith

• (Shen & Yu, 2013) ⇒ Entong Shen, and Ting Yu. (2013). “Mining Frequent Graph Patterns with Differential Privacy.” In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ISBN:978-1-4503-2174-7 doi:10.1145/2487575.2487601

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222013%22+Mining+Frequent+Graph+Patterns+with+Differential+Privacy
• http://dl.acm.org/citation.cfm?id=2487575.2487601&preflayout=flat#citedby

Quotes

Author Keywords

• Differential privacy; graph pattern mining; security and protection

Abstract

Discovering frequent graph patterns in a graph database offers valuable information in a variety of applications. However, if the graph dataset contains sensitive data of individuals such as mobile phone-call graphs and web-click graphs, releasing discovered frequent patterns may present a threat to the privacy of individuals. Differential privacy has recently emerged as the de facto standard for private data analysis due to its provable privacy guarantee. In this paper we propose the first differentially private algorithm for mining frequent graph patterns.

We first show that previous techniques on differentially private discovery of frequent itemsets cannot apply in mining frequent graph patterns due to the inherent complexity of handling structural information in graphs. We then address this challenge by proposing a Markov Chain Monte Carlo (MCMC) sampling based algorithm. Unlike previous work on frequent itemset mining, our techniques do not rely on the output of a non-private mining algorithm. Instead, we observe that both frequent graph pattern mining and the guarantee of differential privacy can be unified into an MCMC sampling framework. In addition, we establish the privacy and utility guarantee of our algorithm and propose an efficient neighboring pattern counting technique as well. Experimental results show that the proposed algorithm is able to output frequent patterns with good precision.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2013 MiningFrequentGraphPatternswith	Entong Shen Ting Yu			Mining Frequent Graph Patterns with Differential Privacy				10.1145/2487575.2487601		2013