TSGL: A Framework Boosting Locally Differential Private Graph Analysis Under Truncation Mechanism
Jiayu Li, Zejun Zhou, Xiaoguang Li, Jin Ping Cao, Lingcui Zhang, Fenghua Li, Ben Niu · 2025
Local differential privacy (LDP) preserves privacy without a trusted third party. In LDP-based graph analysis, the upper bound of sensitivity is often large, truncation mechanism can effectively reduce sensitivity and improve estimation accuracy. However, existing methods typically focus only on limiting truncation errors without balancing noise, leading to unnecessarily large noise. To tackle this issue, this paper proposes a threshold selection framework for graph analysis based on LDP (TSGL) to guide the selection of thresholds, using the privacy budget, pre-collected noisy degrees, dataset size as constraints. TSGL comprises four steps, enabling servers to quantify the relationships between truncation error, noise, overall error and threshold with limited knowledge. By leveraging this quantification, TSGL facilitates better threshold selection to minimize overall errors. To demonstrate the efficacy of TSGL, we present two use cases involving threshold selection: 2-star counting and global triangle counting. Experimental results on three real-world datasets show that the selected thresholds significantly improve estimation accuracy.