Collecting Triangle Counts with Edge Relationship Local Differential Privacy

Counting subgraphs in decentralized settings has drawn increasing attention for graph analysis, wherein triangle count is one of the fundamental statistics. However, triangle counts may breach edge privacy, such as sensitive relations of individuals. Protecting edge privacy in triangle counts collection is a challenging problem due to the strong correlations among data from different clients. Decentralized Differential Privacy (DDP), as a possible option, protects edge privacy on correlated data to some extent. However, DDP provides a weak privacy guarantee by only hiding one edge in global. Unlike DDP, Local Differential Privacy (LDP) is a widely adopted standard for data collection which hides multiple data points in global at a time. But the LDP notion does not consider data correlations. With the understanding of these limitations, we introduce Edge Relationship Local Differential Privacy (Edge-RLDP), which provides a strong privacy guarantee as LDP and considers data correlations simultaneously. Based on Edge-RLDP, a baseline framework for triangle counts collection is proposed, as well as an improved two-phase framework, which strikes a better balance between privacy and data utility. Our improved framework fully utilizes the privacy budget by asking each client to only report the count of randomly sampled triangles after measuring the global data correlation. Theoretically, we rigorously prove that our framework satisfies ($\varepsilon, \delta$) -Edge-RLDP. Experimentally, we demonstrate our framework outperforms the state-of-art methods in terms of triangle count accuracy under a stricter privacy definition.