Publishing Below-Threshold Triangle Counts under Local Weight Differential Privacy

Abstract

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.