Publishing Below-Threshold Triangle Counts under Local Weight Differential Privacy
This work addresses the problem of privately counting subgraph patterns in weighted graphs, which is relevant for road and telecommunication networks, but the contribution is incremental as it extends existing differential privacy techniques to a new setting.
The paper proposes a two-round algorithm for counting below-threshold triangles in weighted graphs under local weight differential privacy, achieving reduced error and computational cost via covariance reduction and smooth sensitivity. Experiments show the biased estimator achieves up to 50% lower error than the unbiased variant.
We propose an algorithm for counting below-threshold triangles in weighted graphs under local weight differential privacy. While prior work has largely focused on unweighted graphs, edge weights are intrinsic to many real-world networks. We consider the setting in which the graph topology is publicly known and privacy is required only for the contribution of an individual to incident edge weights, capturing practical scenarios such as road and telecommunication networks. Our method uses two rounds of communication. In the first round, each node releases privatized information about its incident edge weights under local weight differential privacy. In the second round, nodes locally count below-threshold triangles using this privatized information; we introduce both biased and unbiased variants of the estimator. We further develop two refinements: (i) a pre-computation step that reduces covariance and thus lowers expected error, and (ii) an efficient procedure for computing smooth sensitivity, which substantially reduces running time relative to a straightforward implementation. Finally, we present experimental results that quantify the trade-offs between the biased and unbiased variants and demonstrate the effectiveness of the proposed improvements.