Edge-Protected Triangle Count Estimation Under Relationship Local Differential Privacy
Yuhan Liu, Tianhao Wang, Yixuan Liu, Hong Chen, Cuiping Li
Abstract
Triangle count estimation is a fundamental task in federated graph analysis. Yet, directly collecting local counts from users exposes individuals to severe privacy risks, as the local reports may reveal sensitive social connections. Protecting edge privacy in triangle count estimation is extremely challenging due to the strong data correlation among distinct users and large data sensitivity. Though many efforts have been put into addressing this issue, the existing works fail to provide a stringent privacy guarantee as well as a promising data utility. Motivated by this, we first propose an enhanced privacy notion namely Edge Relationship Local Differential Privacy (Edge-RLDP) that formally considers data correlations and provides a stringent privacy guarantee by hiding multiple edges in the global graph. Based on Edge-RLDP, we further propose a PRIvacy-preserved federated Estimator for Triangle count (PRIVET) with three perturbation algorithms, which enhances the estimation accuracy by designing specialized noise calibration schemes and leveraging a triangle-subsample trick. Theoretically, we prove that PRIVET achieves (ε δ)-Edge-RLDP. Empirically, we verify that PRIVET provides promising estimation accuracy in terms of mean relative error.