PTES: A Triangle Counting Algorithm with Local Differential Privacy

Graph analysis has become increasingly important in numerous applications and services with the widespread usage of social networks, transportation networks, and other graph-driven systems. However, the extensive exploitation of graph data also poses severe risks to users' privacy. Classical differential privacy (DP), while is effective in protecting sensitive information, but still relies on trusted data curators, which may not be accessible in distributed environments. Local differential privacy (LDP) offers a decentralized version by allowing each user to add noise to her own data before sending it to the server, thus eliminating the dependence on a trusted data curator. Despite LDP on graph data has been thoroughly studied, subgraph counting, particularly triangle counting, with LDP still faces crucial challenges, which may lead to large estimation errors. In this paper, we investigate the dense graph problem caused by applying Randomized Response mechanism and propose a mechanism called as locally differentially private triangle counting with edge selection (PTES) mechanism to improve estimation accuracy of triangle counts. PTES introduces a sparsity-related edge selection method to reduce the estimation error caused by the large number of wedges. Furthermore, we present a graph projection method to restrict the noise introduced into the results in the ∊-edge LDP mechanism. Through extensive experiments using two real-world datasets (Twitch and Github) and synthetic dataset, we demonstrate that our algorithm maintains a small estimation error of triangle counting while effectively protecting user’ privacy.