Publishing Graph Data with Subgraph Differential Privacy

Abstract

The eruption of social networks, communication networks etc. makes them become valuable resources for the research community. However, the graph data owners hesitate to share their data due to the barrier of privacy leakage. In this work, we propose a new privacy definition, called subgraph-differential privacy (subgraph-DP), for graph data publishing based on the conventional differential privacy definition. Subgraph-DP is against the graph-based attacks by restricting the adversaries predict the true subgraph with a high confidence. We provide the mechanism that gives subgraph-DP in which noise will be added to a small set of edges to make sure that all k-vertices connected subgraphs are perturbed. The experimental results show that our perturbation mechanism preserves most of the important statistic features of graph while still guarantees privacy. It is flexible that the owners can adapt the mechanism to decide what they want to publish. We also discuss some limitations in our work.