A Frequent Subgraph Publishing Algorithm Based on Differential Privacy
Wenfen Liu, Di Chen, MingHao Yu, Qiang Xu · 2022
Frequent subgraph mining is a common technology in data mining and has important application value. However, If graph data contains private information, publishing frequent subgraphs and support directly will lead to privacy leakage. Aiming at the problem of lower availability of the published results of the existing differential privacy frequent subgraphs publishing algorithms, this paper proposes a frequent subgraphs publishing algorithm based on differential privacy (DPFSG). First, in order to improve the availability of frequent subgraphs, we design an improved frequent subgraphs preprocessing strategy based on exponential mechanism. We reduce the scale of candidate subgraphs based on threshold, and mine frequent subgraphs combined with exponential mechanism. Secondly, in order to improve the availability of the published results of the frequent subgraphs support, we combine the hierarchical clustering method to cluster and group the support of each frequent subgraphs, and then use the Laplace mechanism to add noise to each group. Theoretical analysis and experimental results verify that the method improves the availability of published data while preserving privacy.