We consider the problem of releasing all pairs shortest path distances (APSD) in a weighted undirected graph with differential privacy (DP) guarantee. We consider the weight-level privacy introduced by Sealfon [PODS'16], where the graph topology is public but the edge weight is considered sensitive and protected from inference via the released all pairs shortest distances. The privacy guarantee ensures that the probability of differentiating two sets of edge weights on the same graph differing by an $\ell_1$ norm of $1$ is bounded. The goal is to minimize the additive error introduced to the released APSD while meeting the privacy guarantee. The best bounds known (Chen et al. [SODA'23]; Fan et al. [Arxiv'22]) is an $\tilde{O}(n^{2/3})$ additive error for $\varepsilon$-DP and an $\tilde{O}(n^{1/2})$ additive error for $(\varepsilon, \delta)$-DP. In this paper, we present new algorithms with improved additive error bounds: $\tilde{O}(n^{1/3})$ for $\varepsilon$-DP and $\tilde{O}(n^{1/4})$ for $(\varepsilon, \delta)$-DP, narrowing the gap with the current lower bound of $\tilde{\Omega}(n^{1/6})$ for $(\varepsilon, \delta)$-DP. The algorithms use new ideas to carefully inject noises to a selective subset of shortest path distances so as to control both `sensitivity' (the maximum number of times an edge is involved) and the number of these perturbed values needed to produce each of the APSD output. In addition, we also obtain, for $(\varepsilon, \delta)$-DP shortest distances on lines, trees and cycles, a lower bound of $\Omega(\log{n})$ for the additive error through a formulation by the matrix mechanism.


翻译:我们考虑释放所有配对最短路径距离( APSD) 的问题。 我们考虑的是, 在一个有不同隐私( DP) 保障的加权非方向图中, 释放所有配对最短路径距离( APSD) 。 我们考虑Selfon [PODS' 16] 引入的重量级隐私, 图表表层是公开的, 但边缘重量被视为敏感, 并且不会通过释放的所有配对最短距离释放所有配对的所有配对。 隐私保障可以确保在同一图表上区分两组不同的$( ell_ 1美元) 标准为$( $) 的加值。 目标是在满足隐私保障的同时, 尽量减少对已释放的 APSDSD的添加错误 。 已知的最佳范围( CHen et al. [Sat' 23] ; Fan. [Arxivar] 是一个$( 美元) 递增的递增错误, 美元1美元( 美元) 和美元( 美元) 的递解数( 美元) 在本文中, 我们用新的递增的 IM1- IM1 IM1 IM 的递增的递增的 IMFDLI1 的递解 值 。

0
下载
关闭预览

相关内容

专知会员服务
25+阅读 · 2021年4月2日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
IEEE ICKG 2022: Call for Papers
机器学习与推荐算法
3+阅读 · 2022年3月30日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium9
中国图象图形学学会CSIG
0+阅读 · 2021年12月17日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2023年2月14日
VIP会员
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
IEEE ICKG 2022: Call for Papers
机器学习与推荐算法
3+阅读 · 2022年3月30日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium9
中国图象图形学学会CSIG
0+阅读 · 2021年12月17日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
相关基金
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员