Publishing Below-Threshold Triangle Counts under Local Weight Differential Privacy

We propose an algorithm for counting below-threshold triangles in weighted graphs under local weight differential privacy. Although many prior studies have considered the setting in which the graph topology is public and only the edge weights are sensitive, to the best of our knowledge, this is the first work to study this privacy notion in the local model. Building on a two-round protocol for locally differentially private triangle counting, we exploit the public graph topology to design a novel algorithmic framework. This leads to significant improvements in both accuracy and scalability. In particular, when the input graph is planar, our algorithm eliminates the covariance arising from distributed triangle counting at nodes; for graphs with bounded degeneracy, it significantly reduces this covariance. Since covariance is the dominant source of error in the counting task, our method achieves accuracy that closely aligns with the lower bound. We also present an efficient algorithm for the computation of the smooth sensitivity and provide experiments that quantify the trade-off between the biased and unbiased variants of our estimator and demonstrate the effectiveness of the proposed improvements.