Local Distance Query with Differential Privacy

• URL: http://arxiv.org/abs/2508.05518v1
• Date: Thu, 07 Aug 2025 15:48:35 GMT
• Title: Local Distance Query with Differential Privacy
• Authors: Weihong Sheng, Jiajun Chen, Bin Cai, Chunqiang Hu, Meng Han, Jiguo Yu,
• Abstract summary: Distance, a critical factor in graph analysis, is typically handled using curator DP.<n>In many real-world scenarios, such a curator may not be present, posing a significant challenge for implementing differentially private distance queries under Local Differential Privacy (LDP)
• Score: 37.18488513802541
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Differential Privacy (DP) is commonly employed to safeguard graph analysis or publishing. Distance, a critical factor in graph analysis, is typically handled using curator DP, where a trusted curator holds the complete neighbor lists of all vertices and answers queries privately. However, in many real-world scenarios, such a curator may not be present, posing a significant challenge for implementing differentially private distance queries under Local Differential Privacy (LDP). This paper proposes two approaches to address this challenge. The first approach generates a synthetic graph by randomizing responses and applies bitwise operations to reduce noise interference. However, like other synthetic graph methods, this approach suffers from low utility. To overcome this limitation, we propose a second approach, the first LDP method specifically designed for distance queries, which captures the global graph structure by continuously aggregating local distance vectors from neighboring vertices. This process enables the accurate updating of global distances. We demonstrate the effectiveness of our method through comprehensive theoretical analysis and experimental evaluations on real-world datasets.

Related papers

• Benchmarking Fraud Detectors on Private Graph Data [70.4654745317714]
  Currently, many types of fraud are managed in part by automated detection algorithms that operate over graphs.<n>We consider the scenario where a data holder wishes to outsource development of fraud detectors to third parties.<n>Third parties submit their fraud detectors to the data holder, who evaluates these algorithms on a private dataset and then publicly communicates the results.<n>We propose a realistic privacy attack on this system that allows an adversary to de-anonymize individuals' data based only on the evaluation results.
  arXiv  Detail & Related papers  (2025-07-30T03:20:15Z)
• Practical and Accurate Local Edge Differentially Private Graph Algorithms [11.593320678280824]
  We introduce novel LDP algorithms for two fundamental graph statistics: k-core decomposition and triangle counting.<n>Our approach leverages input-dependent private graph properties, specifically the degeneracy and maximum degree of the graph, to improve theoretical utility.<n>Our k-core decomposition achieves errors within 3x of exact values, far outperforming the 131x error in the baseline of Dhulipala et al.
  arXiv  Detail & Related papers  (2025-06-25T20:54:07Z)
• The Cost of Shuffling in Private Gradient Based Optimization [40.31928071333575]
  We show that data shuffling results in worse empirical excess risk for textitDP-ShuffleG compared to DP-SGD.<n>We propose textitInterleaved-ShuffleG, a hybrid approach that integrates public data samples in private optimization.
  arXiv  Detail & Related papers  (2025-02-05T22:30:00Z)
• Deep Efficient Private Neighbor Generation for Subgraph Federated Learning [57.39918843245229]
  We propose FedDEP to tackle the challenge of incomplete information propagation on local subgraphs due to missing cross-subgraph neighbors. FedDEP consists of a series of novel technical designs: (1) Deep neighbor generation through leveraging the GNN embeddings of potential missing neighbors; (2) Efficient pseudo-FL for neighbor generation through embedding prototyping; and (3) Privacy protection through noise-less edge-local-differential-privacy.
  arXiv  Detail & Related papers  (2024-01-09T03:29:40Z)
• Graph Learning Across Data Silos [10.448384704100684]
  We consider the problem of inferring graph topology from smooth graph signals in a novel but practical scenario.<n>Data are located in distributed clients and prohibited from leaving local clients due to factors such as privacy concerns.<n>We propose an auto-weighted multiple graph learning model to jointly learn a personalized graph for each local client and a single consensus graph for all clients.
  arXiv  Detail & Related papers  (2023-01-17T02:14:57Z)
• Differentially Private Heatmaps [41.787298418108534]
  We consider the task of producing heatmaps from users' aggregated data while protecting their privacy. We give a differentially private (DP) algorithm for this task and demonstrate its advantages over previous algorithms on real-world datasets.
  arXiv  Detail & Related papers  (2022-11-24T07:47:34Z)
• Progressive End-to-End Object Detection in Crowded Scenes [96.92416613336096]
  Previous query-based detectors suffer from two drawbacks: first, multiple predictions will be inferred for a single object, typically in crowded scenes; second, the performance saturates as the depth of the decoding stage increases. We propose a progressive predicting method to address the above issues. Specifically, we first select accepted queries to generate true positive predictions, then refine the rest noisy queries according to the previously accepted predictions. Experiments show that our method can significantly boost the performance of query-based detectors in crowded scenes.
  arXiv  Detail & Related papers  (2022-03-15T06:12:00Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  We propose differentially private (DP) algorithms for bound non-dimensional optimization. We demonstrate two popular deep learning methods on the empirical advantages over standard gradient methods.
  arXiv  Detail & Related papers  (2020-06-24T06:01:24Z)
• Continuous Release of Data Streams under both Centralized and Local Differential Privacy [30.998501044718548]
  We study the problem of publishing a stream of real-valued data satisfying differential privacy (DP) One major challenge is that the maximal possible value can be quite large. We develop a method that uses the Exponential Mechanism with a quality function that approximates well the utility goal.
  arXiv  Detail & Related papers  (2020-05-24T14:25:49Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  junction tree algorithm is the most general solution for exact MAP inference with run-time guarantees. We propose a new graph transformation technique via node cloning which ensures a run-time for solving our target problem independently of the form of a corresponding clique tree.
  arXiv  Detail & Related papers  (2019-12-27T13:30:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.