Continuous Publication of Weighted Graphs with Local Differential Privacy

Download PDF

Abstract

Although a large amount of valuable knowledge can be obtained from the weighted graph snapshots modeled over time, it may cause privacy issues. Local differential privacy (LDP) provides a strong solution for private graph data publishing in decentralized networks. However, most existing LDP studies over graphs are only applicable to static unweighted graphs. This paper investigates the problem of continuous publication of weighted graph snapshots and proposes a graph publication framework, WGT-LDP, under 𝑤-event edge weight LDP, which can protect the privacy of edges and weights over any 𝑤 consecutive time steps. WGT-LDP consists of four key components: population division-based sampling that overcomes the problem of over-segmentation of the privacy budget, data range estimation that mitigates noise on edge weights, aggregate information collection that obtains important information about the graph structure and edge weights, and graph snapshot generation that reconstructs weighted graph snapshot at each time step. We provide theoretical guarantees on privacy and utility, and perform extensive experiments on three real-world and two synthetic datasets, using four commonly used metrics. Our experiments show that WGT-LDP produces high-quality synthetic weighted graphs and significantly outperforms baseline methods.