-DP, where the convexity of the distributions is leveraged to achieve a tighter privacy bound. Theoretical and numerical results demonstrate that our bound remarkably outperforms the existing results in the literature. The code is publicly available at https://github.com/Emory-AIMS/HPS.git.

The Sparse Vector Technique (SVT) is one of the most fundamental tools in differential privacy (DP). It works as a backbone for adaptive data analysis by answering a sequence of queries on a given dataset, and gleaning useful information in a privacy-preserving manner. Unlike the typical private query releases that directly publicize the noisy query results, SVT is less informative---it keeps the noisy query results to itself and only reveals a binary bit for each query, indicating whether the query result surpasses a predefined threshold. To provide a rigorous DP guarantee for SVT, prior works in the literature adopt a conservative privacy analysis by assuming the direct disclosure of noisy query results as in typical private query releases. This approach, however, hinders SVT from achieving higher query accuracy due to an overestimation of the privacy risks, which further leads to an excessive noise injection using the Laplacian or Gaussian noise for perturbation. Motivated by this, we provide a new privacy analysis for SVT by considering its less informative nature. Our analysis results not only broaden the range of applicable noise types for perturbation in SVT, but also identify the exponential noise as optimal among all evaluated noises (which, however, is usually deemed non-applicable in prior works). The main challenge in applying exponential noise to SVT is mitigating the sub-optimal performance due to the bias introduced by noise distributions. To address this, we develop a utility-oriented optimal threshold correction method and an appending strategy, which enhances the performance of SVT by increasing the precision and recall, respectively. The effectiveness of our proposed methods is substantiated both theoretically and empirically, demonstrating significant improvements up to 50% across evaluated metrics.

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.

Federated Learning, as a popular paradigm for collaborative training, is vulnerable against privacy attacks. Different privacy levels regarding users' attitudes need to be satisfied locally, while a strict privacy guarantee for the global model is also required centrally. Personalized Local Differential Privacy (PLDP) is suitable for preserving users' varying local privacy, yet only provides a central privacy guarantee equivalent to the worst-case local privacy level. Thus, achieving strong central privacy as well as personalized local privacy with a utility-promising model is a challenging problem. In this work, a general framework (APES) is built up to strengthen model privacy under personalized local privacy by leveraging the privacy amplification effect of the shuffle model. To tighten the privacy bound, we quantify the heterogeneous contributions to the central privacy user by user. The contributions are characterized by the ability of generating "echos" from the perturbation of each user, which is carefully measured by proposed methods Neighbor Divergence and Clip-Laplace Mechanism. Furthermore, we propose a refined framework (S-APES) with the post-sparsification technique to reduce privacy loss in high-dimension scenarios. To the best of our knowledge, the impact of shuffling on personalized local privacy is considered for the first time. We provide a strong privacy amplification effect, and the bound is tighter than the baseline result based on existing methods for uniform local privacy. Experiments demonstrate that our frameworks ensure comparable or higher accuracy for the global model.

Counting subgraphs in decentralized settings has drawn increasing attention for graph analysis, wherein triangle count is one of the fundamental statistics. However, triangle counts may breach edge privacy, such as sensitive relations of individuals. Protecting edge privacy in triangle counts collection is a challenging problem due to the strong correlations among data from different clients. Decentralized Differential Privacy (DDP), as a possible option, protects edge privacy on correlated data to some extent. However, DDP provides a weak privacy guarantee by only hiding one edge in global. Unlike DDP, Local Differential Privacy (LDP) is a widely adopted standard for data collection which hides multiple data points in global at a time. But the LDP notion does not consider data correlations. With the understanding of these limitations, we introduce Edge Relationship Local Differential Privacy (Edge-RLDP), which provides a strong privacy guarantee as LDP and considers data correlations simultaneously. Based on Edge-RLDP, a baseline framework for triangle counts collection is proposed, as well as an improved two-phase framework, which strikes a better balance between privacy and data utility. Our improved framework fully utilizes the privacy budget by asking each client to only report the count of randomly sampled triangles after measuring the global data correlation. Theoretically, we rigorously prove that our framework satisfies ($\varepsilon, \delta$) -Edge-RLDP. Experimentally, we demonstrate our framework outperforms the state-of-art methods in terms of triangle count accuracy under a stricter privacy definition.