Differentially Private Frequent Subgraph Mining.
Mining frequent subgraphs from a collection of input graphs is an important topic in data mining research. However, if the input graphs contain sensitive information, releasing frequent subgraphs may pose considerable threats to individual's privacy. In this paper, we study the problem of frequent subgraph mining (FGM) under the rigorous differential privacy model. We introduce a novel differentially private FGM algorithm, which is referred to asDFG. In this algorithm, we first privately identify frequent subgraphs from input graphs, and then compute the noisy support of each identified frequent subgraph. In particular, to privately identify frequent subgraphs, we present a frequent subgraph identification approach which can improve the utility of frequent subgraph identifications through candidates pruning. Moreover, to compute the noisy support of each identified frequent subgraph, we devise a lattice-based noisy support derivation approach, where a series of methods has been proposed to improve the accuracy of the noisy supports. Through formal privacy analysis, we prove that ourDFGalgorithm satisfiesε-differential privacy. Extensive experimental results on real datasets show that theDFGalgorithm can privately find frequent subgraphs with high data utility.
State Key Laboratory of Networking and Switching Technology Beijing University of Posts and Telecommunications, Beijing, China.
Shengzhi
S
Xu
State Key Laboratory of Networking and Switching Technology Beijing University of Posts and Telecommunications, Beijing, China.
Sen
S
Su
Math and Computer Science Department, Emory University, Atlanta, GA.
Li
L
Xiong
State Key Laboratory of Networking and Switching Technology Beijing University of Posts and Telecommunications, Beijing, China.
Xiang
X
Cheng
State Key Laboratory of Networking and Switching Technology Beijing University of Posts and Telecommunications, Beijing, China.
Ke
K
Xiao