Communicate Less, Learn More: A Locally Differential Private Approach for Counting Triangles with Better Accuracy
Sasi Bhushan V Saladi, Nagesh Bhattu Sristy · 2024
Local differential privacy (LDP) offers strong privacy guarantees, but with reduced accuracy due to noise addition. More often than not, the accuracy of the statistical computations is improved at the cost of high communication overhead. The existing works either have less communication overhead at the cost of accuracy or have a better accuracy at the expense of huge communication cost or involve a trusted entity called shuffler and make an assumption that the shuffler and the data collector do not collude with each other. This work proposes a novel LDP mechanism, LocalShuffle, that addresses above challenges, improving communication efficiency while maintaining or even enhancing the accuracy of statistical analysis. Inspired by previous works, our approach leverages a single round algorithm to significantly reduce the amount of data communicated between devices and the central aggregator. Additionally, we incorporate novel noise injection technique, to minimize information loss and achieve higher accuracy in counting triangles. Our comprehensive evaluation demonstrates that the proposed mechanism achieves communication cost reduction, while preserving or even exceeding the accuracy compared to existing methods.