Shortest Paths and Distances with Differential Privacy

Summary: DP model: public topology, private edge weights (neighbors: ℓ1 distance ≤1); studies private release of shortest paths and all-pairs distances. Proves an Ω(|V|) additive lower bound for path release and gives a near-matching algorithm with error scaling with path length; all-pairs: trees O(log^{2.5}|V|) and bounded-weight graphs Õ(|V|M). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1686
Venue: PODS
Year: 2016
Pagerank: 7.2211576e-05
Overall Rank: 3,325 | 76.87%
DOI: 10.1145/2902251.2902291

Incoming Non-self Citations Over Time

Authors

1. Adam Sealfon

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,235	Global and Local Differentially Private Release of Count-Weighted Graphs	2023	SIGMOD	5.1451658e-05
7,897	Correlation Constraint Shortest Path over Large Multi-Relation Graphs	2019	VLDB	4.6230399e-05
10,094	N2E: A General Framework to Reduce Node-Differential Privacy to Edge-Differential Privacy for Graph Analytics	2026	SIGMOD	4.1945683e-05
10,352	Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation	2025	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
642	Private Analysis of Graph Structure	2011	VLDB	0.00018755196

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,907	Shortest Paths Discovery in Uncertain Networks via Transfer Learning	2023	SIGMOD	4.427232e-05
642	Private Analysis of Graph Structure	2011	VLDB	0.00018755196
8,234	Robust Privacy-Preserving Triangle Counting under Edge Local Differential Privacy	2025	SIGMOD	4.5535352e-05
2,683	Private Release of Graph Statistics using Ladder Functions	2015	SIGMOD	8.315553e-05
10,209	Scalable Privacy-Preserving Shortest Path Distance Computation via 2-Hop Labeling in MPC	2026	SIGMOD	4.1945683e-05
10,728	Continuous Publication of Weighted Graphs with Local Differential Privacy	2025	VLDB	4.1945683e-05
7,447	Shortest Path Computation with No Information Leakage	2012	VLDB	4.7273556e-05
11,164	Node-Differentially Private Estimation of the Number of Connected Components	2023	PODS	4.1945683e-05
6,235	Global and Local Differentially Private Release of Count-Weighted Graphs	2023	SIGMOD	5.1451658e-05
10,352	Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation	2025	PODS	4.1945683e-05