Private Graph All-Pairwise-Shortest-Path Distance Release with Improved Error Rate
Authors: Chenglin Fan
Ping Li
Xiaoyun Li
Venue: NeurIPS 2022 Accept (2022)
Keywords: All-Pairwise-Shortest-Path
Distance Release
Differential Privacy

Abstract: Releasing all pairwise shortest path (APSP) distances between vertices on general graphs under weight Differential Privacy (DP) is known as a challenging task. In previous work, to achieve DP with some fixed budget, with high probability the maximal absolute error among all published pairwise distances is roughly O(n) where n is the number of nodes. It was shown that this error could be reduced for some special graphs, which, however, is hard for general graphs. Therefore, whether the approximation error can be reduced to sublinear is posted as an interesting open problem.

In this paper, we break the linear barrier on the distance approximation error of previous result, by proposing an algorithm that releases a constructed synthetic graph privately. Computing all pairwise distances on the constructed graph only introduces O(n^{1/2}) error in answering all pairwise shortest path distances for fixed privacy parameter. Our method is based on a novel graph diameter (link length) augmentation via constructing ``shortcuts'' for the paths. By adding a set of shortcut edges to the original graph, we show that any node pair has a shortest path with link length O(n^{1/2}). Then by adding noises with some positive mean to the edge weights, the new graph is differentially private and can be published to answer all pairwise shortest path distances with O(n^{1/2}) approximation error using standard APSP computation. Numerical examples are also provided.

Additionally, we also consider the graph with small feedback vertex set number. A feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles, and the feedback vertex set number of a graph, k, is the size of a smallest feedback vertex set. We propose a DP algorithm with error rate O(k), which improves the error of general graphs provided k=o(n^{1/2}).

Private Graph All-Parwiie--hoortst--tt Distance Release With Improved Error Rate
Chenglin Fan, Ping Li, Xiaoyun Li
Cognitive Computing Lab
Baidu Research
10900 8th St. Bellevue, WA 98004, USA
{chenglinfan2020 pingli98, #ixiaoyun996)$gma com
Abstract
Releasing all pairwise shortest path (APSP) distances among vertices on general graphs under weight Differential Privacy (DP) known as challenging task that has gained increasing interest recently. Previous work achieved DP with the maximal absolute error among all published pairwise distances bounded by the number of nodes. Whether the approximation error can
(n) where be reduced to sublinear in is still an interesting open problem. In this paper, we break the linear barrier on the distance approximation error APSP release, by proposing an algorithm that releases a constructed synthetic graph privately. Computing all pairwise distances on the constructed graph only introduces Ö(n 1/2) error answering all pairwise shortest path distances for fixed privacy parameter. Our method is based on novel graph diameter (link length) augmentation via constructing "shortcuts" for the paths and the use of Laplace noise with non-zero mean. Numerical examples are also provided. Additionally, we also propose a DP algorithm with error rate Ö(k), which improves the error of general graphs, when the graph has small feedback vertex set number k = o(n
Introduction
In recent years, there has been growing interest in private data analysis, from academic research to industry practice. Typically, many industrial machine learning applications consist of two steps: 1) collecting data from users; 2) training models using the collected user data. One key question is: throughout this process, how can we extract meaningful information from the data, without leaking sensitive data of each user? In other words, how can prevent an adversarial attacker from inferring any user's data, given the public information that can be accessed? This has been the overarching question in line of research that studies private algorithms under various settings. The concept of differential privacy (DP) (Blum et al., 2005; Chawla et al., 2005; Dwork, 2006) has been a popular approach for rigorously defining and resolving the problem of keeping useful information for model learning, while protecting privacy for each individual. In the traditional setting, databases and D' are collections of data records and considered to be neighboring if they are identical except for a single record (individual information). DP requires that the output of running a randomized algorithm D and D' should have very close probability distributions. There are many types of databases, and in this work, we will specifically focus on the differential privacy of graphs.
Weight private graphs. In general, there are three types of private graph models, regarding the nodes, the edges and the edge weights, respectively. The node private model requires DP for two adjacent graphs differing in one node. In the edge private model, two neighboring graphs are defined such that they only differ by one edge, while sharing the same set of nodes.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In this paper, we focus on the weight private graph model, which was first proposed by Sealfon (2016). In the weight private graph problem, the topology of the graph is public, which means that the adjacent graphs (databases) when considering DP have same nodes and edges, while this is not the case other two DP models. Specifically, in the weight private model we consider two graphs as being adjacent if the difference between the sums of their edge weights is no more than one unit. One example application of this problem is where one tries to release the transportation volume between several places of interest with privacy constraints, where the roads are regarded edges. In some sense, it might be hard to keep the graph structure private in practice, since one may easily obtain the map by modern tools like Google Earth. However, in some cases, information like traffic flows could also be sensitive and needs to be kept private. Releasing such private information is well suited for the setting of weight private graph model.
1.1 Open Problem, and Previous Results
In this paper, we study the problem of releasing all pairwise shortest-path (APSP) distances with weight privacy. Two standard strategies in DP are: 1) adding Laplace noise each edge, 2) adding Laplace noise to the output distance matrix. As discussed in Sealfon (2016), the errors of these two strategies are roughly I n) by adding noise to each edge and O (oog////oog(1/)) using DP composition theorems, respectively, where is the number of nodes in the graph and (c. 5) are the DP parameters. Here, the approximation error is measured by the largest absolute difference among all released pairwise distances and the ground truth. As we see, both of these errors are roughly O(n), i.e., linear in n when and ó are fixed. Whether we can achieve differential privacy with error sublinear n is still an open problem, as recognized by the online repository Ihttps://dist http///ffffeeeeaaaaaaaa coentialprivacee vvac........ . org/open- open-proble problem- amm-all-pp all-pairs/) focusing on the research of DP, quoted "... this linear dependence on n inherent, or is it possible to release all all-pairs distances with error sublinear in n ?"
While this linear barrier seems to hold for general graphs, we can derive improved results on several special types of graph. Firstly, for graph with weights bounded in [0. M), Sealfon (2016) picked a subset Z V of vertices as the "le-covernng set" to approximate the original graph. Each vertex u can map to its closest vertex 2n in the covering set. For any node pair u, their distance is approximated by the distance between 2, and 2, plus OkkM) additional error. Then, the author proposed to use (( pairs of distances to approximate all (n²²) pairwise distances, which leads to O (VnM) approximation error for fixed privacy parameters eventually. Secondly, for grid graph with arbitrary positive weights, Fan and Li (2022) proposed to select an intermediate vertex set and divide the shortest path between any node pair into at most three parts depending By connecting the nodes in the intermediate set and applying the standard Laplace mechanism, the authors constructed DP algorithm with 3/43 approximation error. Thirdly, for trees, Sealfon (2016) gave a recursive algorithm to release all all-pairs distances with error Ollog 2.5 n), which was improved to Ollog 1.5 n log h) by Fan and Li (2022), where is the depth of tree and can be as small Olog n). The general idea was to build a collection T of subtrees of log levels, where the subtrees in each level are disjoint to each other such that each edge appears in at most Ollg n) trees, allowing to only add Ollog n) units of Laplace noise each path in T. This leads poly log n/e approximation error on trees.
its traverse of the set.
1.2 Our Results and Techniques
In this paper, we propose an algorithm that is able to surpass the linear (nn) error of differentially privately releasing all pairwise distances on general weighted graphs. We make use of the improved and extended techniques from Fan and Li (2022) to general graphs to obtain Ó(n approximation error. Moreover, when the graph exhibits some special property having small feedback vertex set number, we develop a new algorithm with further improved error bound.
Breaking the linear error barrier for general graphs. Let G(V, E, w) denote an undirected graph, where V is the set of nodes with | = n, E is the set of all edges, and w is the set of corresponding weights. We use wree) to denote the weight of a specific edge e E E. The key challenge in this problem is that, we need to bound the error of all shortest paths instead of just one. Since the shortest paths could overlap with each other, the dependency among the shared edges (and the noises) hinders us from applying standard concentration results. To achieve sublinear error in DP all pairwise distance

---

release problem, our idea, intuitively, is to find "shortcuts" that will reduce the number of edges in long shortest paths (consisting of many edges). The algorithm proceeds as follows. Denote d(u, v) as the true shortest path distance between node and u w.r.t. graph G(V, E, w). First, we randomly sample n. n/// vertices from V to form a subset of vertices V1 C W. We then create an edge set E, = =[(u, u) : u E V1, E V1, u o ea and assign each edge the weight wh (u, v) = d( B). Denote Eg =: {u, v) E E: u $ V1 or & V1 } as the edge set between nodes that are not both in V1, Next, we add noise to the edges in Eg and E,, respectively. For e E IE,, we add Laplace noise following Lap(uo, o0) where To O(1/e), /o = a log(n/7); for e E E1, the noise is from Lap(un; 01) with Φ1 On /log////) and μ41 σi log( log(n/7). Note that, the mean of the Laplace noise is non-zero in our approach. We will show that this novel design guarantees that the APSP distances computed directly from the synthetic and noisy graph G' are lower bounded by the true distances for all node pairs (w.h.p.), and the approximation error is at most (12)/22 (Theorem 3.6).
Graph with small feedback vertex set number. A feedback vertex set (FVS) of a graph, also called loop cutset (Freuder, 1982), is set of vertices whose removal leaves a graph without cycles, and the feedback vertex set number of a graph is the size of a smallest feedback vertex set. The feedback vertex set problem is NP-hard (Lewis, 1978) and the best known approximation algorithm on undirected graphs is by a factor of two (Becker and Geiger, 1996). Beyond the results derived for general weighted graphs, we also consider the problem for graphs with small feedback vertex set. We design a new algorithm that releases the distances privately with (k)) error where k the feedback vertex set number, improving the error bound when k o(n compared with the result for general weighted graphs.
1.3 More Related Work
The topic of private graphs has attracted substantial research interests in the recent years, including edge privacy, node privacy and weight privacy (Hay al., 2009: Rastogi et al., 2009; Gupta et al.. 2010; Karwa et al., 2011; Gupta et al., 2012; Blocki et al., 2013; Kasiviswanathan et al., 2013; Bun et al., 2015; Sealfon, 2016; Ullman and Sealfon, 2019; Borgs et al., 2018; Arora and Upadhyay, 2019; Fan et al., 2022; Fan and Li, 2022). Our work focuses on the weight private problem (Sealfon, 2016) as described above. We generalize the previous work (Fan and Li, 2022) which focused on trees and grid graphs to general weighted graphs. We are also aware of two concurrent works (Chen et al., 2022; Ghazi et al., 2022). Both these two papers claim (nn4/2) error upper bound same as our result, using a similar high-level idea of constructing "shorteuts". However, our approach is novel and different in that the Laplace noise we add has non-zero mean. As will be shown in the paper, this allows us to simply publish the constructed synthetic graph, upon which standard APSP computation leads to the desired error level. However, in both Ghazi et al. (2022) and Chen et al. (2022), the noise is centered and one has to use some specifically designed calculation (optimization) to obtain the estimated distances. In other words, only the estimated distances, but not the graph itself, can be published. Typically, releasing the graph (ours) is more difficult than releasing the distances only.
2 Background: Differential Privacy (DP) on Graph
Consider a connected graph G = (V,E, w), with w the collection of the weights of E. We use w(e) to denote the weight of an edge E E. Denote n IV. m = [EE, with n S m +
We first define the notion of neighboring graphs. In weight private model, since the nodes and edges of the graph G are unchanged, can simply use edge weights to represent the graph.
Definition 2.1 (Neighboring). Graph G = (V, w) and G' = (V, E,E, w') are called neighboring, noted as G G', if
|| - w'lli := Σ (w(e - w' 1 eEB
The Differential Privacy (DP) introduced by Dwork (2006) is defined below adapted to our problem.
Definition 2.2 (Differential Privacy (Dwork, 2006)). for any two neighboring graphs G (V, R. w) and G' = (V, E, w²), randomized algorithm A, and a set of outcomes O C Range(A) (A),
Pr(A(G) E 0] e Pr(A(G") E 0] + 6,
say algorithm A is (e, 8) diffeerrrntllllly private.
3

---

I = O, we say that the algorithm is c-DP. The parameter ò is usually interpreted as the probability allowed for bad cases where c-DP is violated. Intuitively, differential privacy requires that after changing the database by a little (the total weights in our case), the output should not be too different from that of the original database. Differential privacy may be achieved through the introduction of noise to the output. To attain general (c. 6)-D,, we may add Gaussian noise to the output. To achieve e-DP, the noise added typically comes from the Laplace distribution. Smaller and ó indicate stronger privacy, which, however, usually sacrifices utility. Thus, one of the central topics in the differential privacy literature is to reduce the scale of noise added, while satisfying the privacy constraint, In this work, we focus the popular approach to achieve DP by adding Laplace noises. The Laplace distribution with parameter b has density function f(x = 26 exp(-Ix1/0)
Lemma 2.1 (Dwork (2006)), For a function f g + R with G the input space of graphs. define the sensifivity
4
max llf fl GmG
where G, G' are two neighboring graphs. Let X be a random noise drawn from Lap(O, /s/e). The Laplace mechanism outpuls
Mf, f(G) X,
which achieves c-differential privacy.
One important and attractive property of DP is that, different DP algorithms can be easily combined together, also with strict DP guarantee.
Lemma 2.2 (Advanced Composition Theorem (Dwork et al., 2010)). For any e, 2 0, the adaptive composition of times (e, diifferennnl private mechanisms (c', kō + ( d'd-fffrrreltially private for
é'
2k 2llo8(1/8)) c e(c" 1),,
which is O( k log(1/8') E) when is 1/e.. In particular, if'' (0, 1), 8'' > O, the composition of times (e, -idiffeertt private mechanism ( 8---fffereennillllly private for
6 6= é =/V////k log(1/8))
Finally, we introduce a high probability upper bound on the maximum of Laplace random variables which will be used in the error analysis.
Lemma 2.3. Consider i.i.d. random variables Z1, Zz, .... Zn from Lap(b). With probability at
least - % YO < y < 1, all n Laplace random variables have magnitude bounded by b blog(n/7).
Proof. For each Z, P(|zd I = - eex((=f) Thus,
P max
7 < 1 (1 (1-exp) (1-exp(-))) exp(-
Let t == blo((n/)) With 2 1, the probability becomes (1 2)" 1 as claimed.
3 Private Synthetic Graph Release for APSP Distance
We formally define the problem interest and some basic concepts as below.
Definition 3.1. (Approximate Distances Release) Given an graph G(V, E, w). our task is to release all pairwise shortest path distances privately. Let d((,-) .) be the output (approxinate) distance function. Our object is to minimize the maximal absolute error over all pairs, namely, max(Id(u, v) d(u, v) u, V}. with d(u, v), Vu, error of node pair (u,v).
being DP weight w. We call Id(u, d(u, w)] the additive
Definition 3.2 (Path), A path Poy,r. between Un UL defined Per,er. ((v,, 0(41), ),
L L- 1,, the collection of edges between connected node sequence U1 U2 .... Uk, with some L $ n. A segment of path P is defined consecutive sub-path, {(v,, 1t 1), < 1} for some s.t.

---

Definition 3.3 (Shortest path). Let Su. be the set of all paths between u, E V. For path P E Sa,e and weights w, denote d) Leer w(e). The shortest path of u, E V w.t.t weights w is
P Pu.e argmin ((P,00
P,
and the shortest path distance is d( d(Pu.v.)) Definition 3.4 (Canonical shortest path). For a given graph G(V, E, w), let S CV be a subset of Let Pa. {2r, v1, U2, .... UL v' be the shortest path between I, y E V. Then canonical shortest path p is defined by either of the following:
1. PW, PL.y if Pzyy contains at most one vertex in 1
2. PV, (I, .. P.q. .... UL y}. if p.g q are the closest nodes in Pa.y a, y respectively, and p,qe E V1.
Intuitively, the canonical shortest path finds shorteut by directly connecting two nodes in set 11- This definition will be the key in our algorithm and construction. One important fact is that, if we connect each pair of nodes in V1 and assign the true pairwise distance between them as the edge weight (as in our main algorithm). then d(Pu,v w) = d( (P",, w) by definition.
3.1 Challenges and the New Algorithm
First, we revisit the prior approach to release all pairwise distances in the private weight model and the challenges. Since neighboring (total) weights differ by at most one unit in 4 norm, the distance between any two nodes also changes by most one unit. Releasing single path can be done by computing the accurate shortest path distance between pairs of inputs and adding Laplace noise proportional to 1/c, which is trivial task in DP. However, releasing all distances privately is much more challenging, since the Laplace mechanism requires Lap(n2 /c) noise (because of the n² queries), resulting in the (n)) eтror eventually. As introduced in Section 1.1, in prior literature, there are two ways (e.g.. Sealfon (2016)) to achieve this error level, either by adding noise to each edge or to the output distances. In this paper, will focus the first strategy.
The simple approach is as follows: 1) add Lap(1/c) noise to each edge, i.e., w'= Lap(1/e) to get graph G = (V, E, w'); 2) report all pairwise distances G" (note that, the shortest paths on G' found might be different from the true shortest paths G). By the Laplace mechanism (Dwork, 2006), all the weights in graph G become differentially private. By the post-processing property of DP, all the output pairwise distances are also DP. Note that there are 0(r²) pairs of vertices, so the number of edges is bounded by On??). By Lemma 2.3, with probability - 7, all O(n²) Laplace random variables will have magnitude bounded by (1/c) log(n? /n), ) so the length of every path in the released synthetic graph is within n log(n/n)) / additive error, thus roughly (n)).
Statistically, the general problem can descrihed informally and approximately as: given a set of n² i.i.d. Laplace random variables, we want to bound the sum of the variables among n² size-n subsets simultancously. Since the graph topology can be arbitrary, it is not hard to find examples where getting sublinear error seems impossible, and a straightforward additive bound exactly leads to the previous (n) error as mentioned above. this section, we propose an algorithm that leverages the concept of canonical shortest paths (Definition 3.4), which finally leads to (nn additive approximation error.
As summarized in Algorithm 1, for a general weighted graph G(V, E, w), our proposed algorithm proceeds as follows:
1) Sample n 1/2 vertices from V uniformly to form set V1;
2) Create an edge set E2 == {(u, v): u E V1 u E V1, u + v}. For each e = (u, v) E Ej, set w(e) d(u, v) as the true shortest path distance;
3) Add Lap((1, 01) noise to each edge E E₁, i.e., w' = w + t1)(
4) Add Lap(po, σo) noise to each edge e E Rg,, w' = w po+Tap(uuo σo) where Eg = EEEE;
5) Obtain and release the merged graph G' = =V, = Eg UB, w²). One can simply compute all pairwise distances on G' as the estimation.
5

---

Input:
General graph G (V, E,,,, private parameter c, y- c/2.
Sample (n1/2) vertices from V uniformly and add them to V1. Create an edge set E_ == {(u, e): u E V1, E Vi, * v).
For each E E1, let (P)P((e be the exact shortest path distance in G between (u, v) where E e= (u, v). for each edge E, do
Let 01 (2 12 log(1/8))/e and μn on log(n/7).
Draw X. Lap(u1, o.).
w'(e) ;= APSP(e)) Xe.
Bo B E
for each edge e Eg
Let on 1/6', Mo To log(n2 //).
Draw X. ~ Lap((un,o))
w re((e) == w(ee) Xe-
Compute all pairwise distances in graph G' EY, U1, Output: All pairwise distances of G".
Algorithm 1: Private all pairwise shortest paths distance release.
Comments. Note that in Algorithm 1, the final estimated distances are calculated by using standard APSP distance computation graph G'. One implication of this construction that, beyond outputting the pairwise distances with privacy, we can in fact also publish the graph G'VV, E', w') privately and allow the users to compute the private distances using standard algorithms by themselves. This is due to the positive mean of the Laplace noises. If we instead add zero-mean (centered) Laplace noises in most standard approaches. then computing the APSP distances G' would not ensure the desired approximation eπror rate. We will provide more discussion on the role of the shifted noises the end of this section.
Next, we provide theoretical analysis of our proposed algorithm. Firstly, recall that V1 contains n 1/2 uniformly sampled nodes from V. Our analysis starts with the following fact.
Lemma 3.1 (Sampling Intersection). Suppose U C V is fixed vertex set and [U] = n/2 (n? /7). With probability at least 7/n², we have that U V1 + 0.
Proof. Suppose pick random vertex from V each time, the probability that is not in
V, is 1 - 1/2 Then the probability of interest is bounded by Pr(U n Vi 0) - (1
1/n 1//1///(// =//"².
3.2 Privacy Analysis and Sublinear Error Bound
Lemma 3.2. Algorithm I achieves (c, 6D-
Proof. The privacy budget is divided into two parts:
(Part 1) The noise added Eg. is obvious that for two neighboring inputs differ the total weights of edges in Ho by 1, by adding Laplace noises according Lap(uo. 1/e'), ), it achieve (e', O)-DP, Note that adding a constant Ho independent of the edge weights to the edges does not affect weight privacy.
(Part 2) The noise added to edges in E,. Similar arguments hold. There are at most n///2 nn222 pairs in E, Applying Laplace mechanism with composition theorem (Lemma 2.2), we know that adding noise following Lap(H1, o1) with 0 = / /8n log(L/o)/e = 2/2 / /log (og)(//)/e' suffices to achieve (e', dDDP. Applying simple DP composition theorem again proves the (2e', 8) We conclude by noticing that e' e/2.
We have the following fact that, any "long path" in G' would contain at least two nodes in V1 with high probability.
Lemma 3.3. For given path in G(V, E, w) with number of edges larger than 2n2/2 log(n? 1/7)//))))))))))))))) contains least two vertices in V with probability 1 2x/n².

---

Proof. Let us divide the path into three parts, such that two of them have at least n 1/22 log(n") //) edges. Based on Lemma 3.1, we have that each part above intersects with V, with at least one vertex, each with probability at least 7/n². As a result, by union bound, the whole path contains at least two nodes in V1 with probability 2y/n2.
Recall G = (V, = Eo E1, w') is the constructed synthetic graph with noisy weights. From now on we denote w as the weight set containing the constructed shorteut weights, and define G (V. E., w) as the graph with nodes V, edges E' and weights w (notice that it is different from G² (V, E', w²)). Consider those canonical shortest paths found by the true weights w on G (V, w). We show that each canonical shortest path u.b. u, v V in G has error Id(Pa, w') - d( Pa u, w)l bounded by O where d(Pu, w) is defined by Definition 3.3.
Lemma 3.4. For any u E V, let P be the canonical shortest path (Definition 3.4) found by the true weights W. Then, it holds that [d(P)), u,bs w') - -d(P 0,21 w) = O(n2/2 Vlog(1////// log (n/>)/e) with probability 1 47 for Vu, V E V.
Proof. Firstly, we have [d(P", u,o0 w²) - d d(P",, M, w)l = -E (w'(c) w(e)), and (e) w(e) is the corresponding Laplace noise added to edge e in Pi,,- The key observation in the proof is that, each canonical shortest path PWW, can be divided into three parts (u,.... p). (p. 9). (g...., U), where P. q are the closest nodes in 1 to respectively, and the edge (p, () is the constructed shortcut provided by V, and E, Note that, u,u also might not contain a shortcut, but this does not matter in our analysis in the sequel. Denote Pu,e, as the shortest path between u and Consider two cases:
Pa,el S 2n2 log(n"/n) //). In this case, we know that the total length of (u. p) and (g...., u) is bounded by 2n log(n?/>) That is, p contains at most 2n 2/2 log(n? /7) edges from Eg- By Laplace mechanism, with probability 1 Y every edge in Eo leads to at most Ollo((n7)//e) error. Thus, edges in Eo contribute at most (n log"(n/ (n/r)/<) error. PV, also contains at most one shortcut edges from V1, which gives O(n (tga:/))////////oggg /log(1/))// error, with another probability - 7. Thus, with probability 1 - 22, the error is bounded by 1/2 1og2 (ng)(n////c.
Pa.e > 1/2 log(n2//) In this case, by Lemma 3.3 and union bound, we know that with probability 27 n² = 2y, pWy contains shortcut (p. q), and both the lengths of (u,..,, p) and (u,... 9) are upper bounded by n² log(n"/ //). The remaining proof is similar to the arguments above. We have that with probability at least - 44, Id (P.,,. w²) di (V, w)l is bounded by O(n 1/2 (n/7)nn)))
In summary, we have shown that with probability at least 1 - 4r, [d(P),, u, w') - d( d(PY. w) is bounded by On22/2 10////oog(/ log" (n/n)/e). The proof is complete.
Additionally, we have the following result stating that the estimated distance is no smaller than the true distance for all pairs of vertices, with high probability.
Lemma 3.5. Let Pu.e be the shortest path between u, u E V on G, and P Pa., the shortest path found on G'. Then with probability 1 - -2y, d(P:. w') 2 d((u,us w) for all u, V.
Proof. By adding each edge in E, with noise according to Lap(un,o)) where an 2 2/2n / (o/(1/))/e and μr = 01 log(n/>)) with high probability 1 - 7, every Lap(u1, σ1) variable is greater or equal to μ4 - 01 log(n/7) 2 O with probability 1 - based on Lemma 2.3.
Similarly, for edges in Eo, we add to each of them Lap(Ho- σo) noise where au 1/C',
oo log(n"/7) Then with another high probability - 7, every variable according to Lap(po, on)
is non-negative based on Lemma 2.3. Therefore, since with high probability the added noises on all the edges are positive, the noisy shortest path distance must be larger than the true distance i.e. d(P) w w²). This proves the claim.
7

---

x10*
x10*
10
Approx. Error Rate
empirical
Approx. Error Rate
10
empirical
scale n
scale
c 0.1
scale n 1ogg n
" scale n log
= 0.1
5
0.5
0.5
=1
0
0
500
1000
1500
500
1000
1500
Figure 1: Empirical approx. error rate graph size (solid curve), with predicted growth rate of n) (dash and dotted curves). 8 = 10, 7 0.01. Left: each edge weight is U200 3000). Rightredge weight from Unif(10*, 10"). Averaged over 200 repetitions.
(n)) and O/n log 2
Now, we are in the position to present the main error guarantee of this work.
Theorem 3.6. Let G = (V, E. w) be general graph with n vertices. For some e, > O, running Algorithm I publishes the graph G' with (e, 8) diiffereetii privacy w.rd. the weights w. Let d(u, v) be the estimated shortest path distance between u, v E V computed on G'. Then, with probability 1 4y,, we have |d(u, v) d(u, v)l S 100='''' 1og" log (n/7) (lg((18)) for all u, V.
Proof. Let Pu, be the shortest path between u and v in the synthetic graph G'VV w'), then trivially, d(P,, u,u. w') I d(P",, n.n w'). By Lemma 3.4, we know that Id(P", u,0: w²) d(PW,, u,u w)) is bounded by O(21/2 /log(1/1 (og))oognnn))))) (n/7)/c) with probability 1 - 4y, Vu, U E V. In this event, we have d(P', d(PM, w/) 2 d(Pu,v: w) based on Lemma 3.5. Notice that, d(P Pa.p w) = d(Pi), w) by definition. Therefore, with probability 1 47
(d(u,v) - d(u v) Id(Pu.. w') - d(Pa w)l S [d [d(P w') - d( ((P,) u.v: (. w) (a)
s O(n (og (og7))))
which verifies the claim.
Comments. As we see, the positive mean Laplace noises implies Lemma 3.5 which provides key inequality in the proof of Theorem 3.6. This result in fact allows us to only consider the error on the positive side. On the contrary, we use mean-zero Laplace noises, then we can no longer bound [d(P' n, w/) d(u, v)] by [d(P"; u, w') d(u, v)] as in Lemma 3.4, since it is possible that e, w') S ((P", w') d(u,v) Thus, if we simply add zero-mean noises, directly computing the APSP distances on the constructed graph G' would not guarantee the desired error level.
3.3 Numerical Example
We present numerical example on a multi-stage graph to justify the theory. We simulate a multi- stage graph, where each edge weight is generated from i.i.d. uniform distribution. The graph contains concatenated blocks, each with start node, end node, and 9 nodes in the middle connected to both the start node and the end node. The end node then becomes the start node of the next block. We consider multi-stage graphs here because in some sense it is one the "hardest" cases for private APSP computation, since many shortest paths contain O(n) edges. In Figure 1, present the empirical largest absolute error over all pairwise distances against the size of graph n. For the theoretical bounds, we start with the first empirical error (black) associated with
100, and increase at the rate of (dash) and n 1/2 log" (dotted), respectively. We validate that the empirical error grows with rate slower than n 1/ n, given by our theory, for all values. Note that the error bound becomes tighter with large edge weights (right) than with small weights (left). When the edge weights follow Unif((00 10a) which is much larger than the noise magnitude, the shortest path Pr found on G' would be the same Pu., (or PKt) in most cases. Thus, the LHS and the RHS of (a) (1) would be close, making the bound tighter.

---

Graph with Small Feedback Vertex Set
General graph G EV w), private parameter 6, e/3. Compute the FVS using the 2-approx. algorithm in Becker and Geiger (1996). Step 1) Let G" be the induced subgraph of vertex set V V S in G. Let k: == (S).
Input:
Compute the differentially private pairwise shortest path distances d((u, v) on trees/forest G' using Algorithm 1 in Sealfon (2016) with privacy parameter ç'.
// Step 2) Compute d( u. v) for u, S, where d(u, v) is the exact shortest path distance in G. // Step 3)
for each u E S, E do
Let Ø1 := (2v/kk (2//2k /og(118))/ee
Draw X. ~ Lap(0 o.). d(u, :): = d(u, v) Xe.
for each vertex E S do
for each vertex $ adjacent do
// Step 4): To deal with the edges between S and V V.5 Let on := 1/c'.
Draw X. ~ Lap(0, 0o).
w'(u, v) = w(u, v) + X
d(u. v) = u',,
for each vertex u V V do
for each vertex in S do
11 Step 4): To deal with the case that only the last vertex of shortest path S d(u,v) = minpes for each vertex in V \ do for each vertex
w/ (p, v)}.
do // Step 5): To deal with the case that shortest path passes vertex in S
d(u, v) == minpes(d(u..)) + d(p.v)) for each pair u. V S do
// Step 6): To deal with the case that shortest path passes some vertex u in S d(u, v) = minpestddin
d(p,
Output : All pairwise distances d(u, v).
Algorithm 2: Differentially private all pairwise shortest path distances release for graph with small feedback vertex number.
In previous section, we have investigated the problem of DP all pairwise shortest distance problem on general weighted graphs. In this section, we consider a more special type graph with small feedback vertex set (FVS), which is a common concept graph analysis, e.g., (Kratsch and Schweitzer, 2010; Papadopoulos and Tzimas, 2020). We will design new algorithm based on FVS computation that privately releases all pairwise distances. We will show that this method improves the error general graphs when the FVS number is small. To begin with, the definition of FVS is given as below.
Definition 4.1 (Feedback Vertex Set (Becker and Geiger, 1996)). Let (V, E) be undirected graph. A set X C V is called a feedback vertex set (FVS) if \ X is forest, where G \ X is the induced graph by V V X. The feedback vertex number is the minimal cardinality over all the possible feedback sets.
In words, feedback vertex set (FVS) of graph is subset of vertices X such that after removing these nodes from the graph, the subgraph induced by V \ X contains no cycles (i.e., is a forest). The FVS number is the smallest size of all the FVS's.
Next, we propose differentially private algorithm that releases the APSP distances of graphs based on the feedback vertex set computation. The steps of Algorithm 2 are summarized below:
1) We compute a feedback vertex set S of by using the 2-approximation algorithm Becker and Geiger (1996), with |S| k; the induced subgraph G' of vertex set V S is forest;

---

2) We use Algorithm I in Sealfon (2016) to obtain the private all pairwise shortest path distances in G'. For any pair (u, v) in G whose shortest path does not pass any vertex in S, d(u, v) on G" is already a good estimation for d(u, v);
3) For the k2 (recall k = (S)) pairwise distances of the node pairs in S, we can compute the APSP distances directly and add Lap(O, σ1) to achieve DP. We still use the d(u, v) to represent them;
4) For each edge (u, r) with E S E V \ S, we add noise according Lap(O, w(u, u). For a pair in f(u, v)lu E V S, E 5), if the shortest path between u and y does not pass other vertex in S except then there exist some neighbor p of such that de(u,,)) v) = der (u, + w(p, v) based on Lemma A.I, where do(u, v), do (u, v) represent the shortest path distance between and in G and G' respectively. Hence we use d(u, v) == minpes (d(u, p) + w w'(p,)) e)} to estimate d(u, v);;
1/e')
5) For a pair in {(u, v) u V S, 8). if the shortest path between u and v passes some vertex p E S except v, then there exist p E S, & S such that da(u, e) = da(u, p) (p, v), and the shortest path between and p does not pass any vertex in S except p based on Lemma A.1. We obtained diu. p) in step 4). We then use d(u, v) == minpes (imppesd(uu))) d(p, } to estimate d(u, e);
6) For pairs in {(u, v) E (V) ?)), if the shortest path between and passes some vertex in S, then dg(u,,) v) du p) (p, v). We can use d(u, v) := minpes (d(u,, p) + d(p. v)} to estimate d(uu, r), also d(u, p), d(p, 1) had been computed in 4), 5).
The auxiliary lemma mentioned in step 4) and 5) is given Lemma A. in the Appendix.
4.1 Privacy and Error Analysis
Lemma 4.1. Algorithm 2 achieves (e, 0)-DP.
The proof is placed in the Appendix. The error bound of Algorithm 2 is given as below.
Theorem 4.2. Let G (V,E, w) be general graph with n vertices. For some e, > 0, running Algorithm 2 publishes all APSP distances that is (c. (..))-differentiall private w.r.t the weights
w. With probability 1 - 17,, the additive error is bounded by kklokkk////) (log(//))))(((())) - (log2s n) log(1/7))
Comments. We see that when k = 1S| = o(n2/2), the error in Theorem 4.2 is smaller than the 0(n m) error in Theorem 3.6 for the general weighted graphs. Therefore, our result implies improved error bounds when the graph has small feedback vertex set such that k = o(n2/2), Further, if k = o(lgg nt), i.e., the graph is "almost" forest, then the first term vanishes and the error reduces to (log 2.5 n) for trees (Sealfon, 2016).
Conclusion
In literature, to achieve (e, -diifferrentt privacy (DP) in general weight private graphs, releasing all pairwise shortest path (APSP) distances incurs maximal approximation error Ön)), linear in the number of vertices. Recently, Fan and Li (2022) studied this problem on grid graphs and trees, but the linear error barrier for general weighted graphs is still an open problem (Sealfon, 2020). In this work, we propose differentially private algorithm to release carefully constructed graph, and computing the APSP distance on the synthetic graph achieves 1/2) error sublinear in n, thus answering the open question. With improved and extended techniques from Fan and Li (2022), the idea of our approach is to augment the diameter of graph by a set of shortcuts along with adding shifted Laplace noise. Moreover, for graphs with small feedback vertex set number k, we also propose a DP algorithm to answer all pairwise shortest path distances each with error Ó(k).. This improves the result for general graphs when k the feedback vertex set number, is small.
10

---

References
Raman Arora and Jalaj Upadhyay. On diffcrentially private graph sparsification and applications. In Advances in Neural Information Processing Systems (NeurIPS), pages 13378-13333 Vancouver, Canada, 2019.
Ann Becker and Dan Geiger. Optimization of pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artif. Intell., 83(1):167-188, 1996.
Jeremiah Blocki, Avrim Blum, Anupam Datta, and Sheffet. Differentially private data analysis of social networks via restricted sensitivity. In Proceedings of the Innovations in Theoretical Computer Science (ITCS), pages 87-96, Berkeley, CA, 2013.
Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: the SuLQ framework. In Proceedings of the Twenty-fourth ACM HICAC--SIMMOD-SS Principles of Database Systems (PODS), pages 128-138, Baltimore, MD, 2005.
Symposium
Christian Borgs, Jennifer T. Chayes, Adam D. Smith, and Ilias Zadik. Revealing network structure, confidentially: Improved rates for pode-privane graphon estimation. In Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 533-543, Paris, France, 2018.
Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. Differentially private release and learning of threshold functions. In Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pages 634, Berkeley, CA, 2015.
Shuchi Chawla, Cynthia Dwork, Frank McSherry, Adam D. Smith, and Hoeteck Wee. Toward privacy in public databases. In Proceedings of the Second Theory of Cryptography Conference (TCC), pages 363-385, Cambridge, MA, 2005.
Justin Y Chen, Shyam Narayanan, and Yinzhan Xu. All-pairs shortest path distances with dif- ferential privacy: Improved algorithms for bounded and unbounded weights. arXiv preprint arXiv:2204.02335, 2022.
Cynthia Dwork.
Differential privacy. In Proceedings of the 33rd International Colloquium Automata, Languages and Programming (ICALP), Part II, pages 1-12, Venice, Italy, 2006.
Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential privacy. In Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 51-60, Las Vegas, NV, 2010.
Chenglin Fan and Ping Li. Distances release with differential privacy in tree and grid graph. In IEEE International Symposium on Information Theory (ISIT), pages 2190-2195, 2022.
Chenglin Fan, Ping Li, and Xiaoyun Li. k-median clustering via metric embedding: Towards better initialization with differential privacy. arXiv preprint 2rXiv:2206.128990 2022.
Eugene C. Freuder. A sufficient condition for backtrack-free search. J. ACM, 29(1): 1982.
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, and Jelani Nelson. Differentially private pal-s shortest path distances: Improved algorithms and lower bounds. arXiv preprint arXiv:2203. /6476. 2022.
Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 1006-1125, Austin, TX, 2010.
Anupam Gupta, Aaron Roth, and Jonathan R. Ullman. Iterative constructions and private data release. In Proceedings of the 9th Theory of Cryptography Conference (TCC), pages 339-356, Taormina. Sicily, Italy, 2012.
Michael Hay, Chao Li, Gerome Miklau, and David D. Jensen. Accurate estimation of the degree distribution of private networks. In Proceedings of the Ninth IEEE International Conference on Data Mining (ICDM), pages 169-178, Miami, FL, 2009.

---

Vishesh Karwa, Sofya Raskhodnikova, Adam D. Smith, and Grigory Yaroslavtsev. Private analysis of graph structure. Proc. VLDB Endow. 4(11):114-1115, 2011.
Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. Ana- lyzing graphs with node differential privacy. In Proceedings of the 10th Theory of Cryptogruphy Conference (TCC), pages 457-476, Tokyo, Japan, 2013.
Stefan Kratsch and Pascal Schweitzer. Isomorphism for graphs of bounded feedback vertex set number. In Proceedings of the 12th Scandinavian Symposium and Workshops Algorithm Theory (SWAT), pages 81 81-92, Bergen, Norway, 2010.
John M. Lewis. On the complexity of the maximum subgraph problem. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC), pages 265-274, San Diego, CA, 1978.
Charis Papadopoulos and Spyridon Tzimas. Subset feedback vertex set on graphs of bounded independent set size. Theor Comput. Sci., 814:177-188 2020.
Vibhor Rastogi, Michael Hay, Gerome Miklau, and Dan Suciu. Relationship privacy: output perturbation for queries with joins. In Proceedings of the Twenty-Eigth ACM SIGMOD-SIGACT SIGART Symposium on Principles of Database Systems (PODS), pages 107-116, Providence, RI, 2009.
Adam Sealfon. Shortest paths and distances with differential privacy. In Proceedings of the 35th ACM SIGMOD--IGACCT-SIAA Symposium Principles of Database Systems (PODS), pages 29-41, San Francisco, CA, 2016.
Adam Sealfon. Open problem private all-pairs distances, 2020. httpss//ddifferratiaalvvywy heg/open-problee em em- all -aairs.
Jonathan R. Ullman and Adam Sealfon. Efficiently estimating erdos-renyi graphs with node differen- tial privacy. In Advances in Neural Information Processing Systems (NeurlPS), pages 3765-3775, Vancouver, Canada, 2019.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "XxZ8fegmvMW", "reviewer": "Reviewer_f9J1", "summary": "The manuscript tackles the problem of estimating all pairwise shortest path distances between nodes where sensitive edge lengths have to be protected by differential privacy (while the graph topology is non-sensitive and public). The work extends prior results with sublinear error that were limited to grid graphs and trees to general graphs and thereby answers a previously open problem. Even stronger results are obtained for \"nearly acyclic\" graphs (removing a limited number of edges results in a forest).", "questions": "Q1. What is the expected performance on real-world graphs? Which topologies would work better/worse?\n\nQ2. Suppose we limit ourselves to grid graphs and trees. How does the performance of the proposed approach compare to prior work numerically/empirically?\n\nQ3. Is there some reason why delta is so large for Figure 1 (compared to other approximate DP works) and what is the rationale behind the other numerical values (e.g., edge weight ranges)?", "limitations": "The performance on real-world graphs is not quite clear, e.g., which topologies would work better or not. It would be good to either declare it as an open question or to add an empirical study with 1-2 real-world graphs (where the weights ideally also relate to users). For instance, the citation graph of papers indexed in DBLP relates to users, e.g., one could use authors as nodes and suppose that the number of co-authored papers between two authors was a sensitive edge weight (representing social network type of graphs). As another example, the road network of Open Street Map is publicly available and can be cross-referenced with population grids--using the number of inhabitants along a road as sensitive edge weights (representing almost planar graphs).", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "STRENGTHS\n\nS1. Novelty/Significance: The work extends prior results with sublinear error that were limited to grid graphs and trees to general graphs and thereby answers a previously open problem by leveraging \"canonical shortest paths\" (Definition 3.4).\n\nS2. Novelty/Significance: Even stronger results are obtained for graphs with a small feedback vertex set (minimal set of nodes whose removal turns the graph into a forest).\n\nS3. Relevance/Presentation/Related Work/Soundness: The problem is well-motivated, the manuscript is well-written, relevant prior work is considered and the claims appear to be appropriately substantiated.\n\nWEAKNESSES\n\nW1. The significance would be greater with an empirical study to provide an intuition for how well the proposed techniques work on different types of real-world graphs\n\nW2. It would be easier to replicate Figure 1 if code was provided in the supplementary material\n\nW3. Minor issues\n\n- l. 182 \"Definition Definition 3.4\" => \"Definition 3.4\"\n- is the red/blue color for external/internal references intended?\n\n*Edit after author rebuttal / reviewer discussion*:\n\nThe overall rating and confidence level has been increased after considering the lack of empirical evaluation in the two contemporaneous works (https://arxiv.org/pdf/2203.16476, https://arxiv.org/pdf/2204.02335) which defuses W1 a bit. Furthermore, it is presumed that the authors will follow the many suggestions by the other reviewers to improve the presentation.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["Privacy and Security (e.g., consent)"]}, "extra_text": {}}, {"review_id": "B0qtiJZd09G", "reviewer": "Reviewer_USDQ", "summary": "This paper investigates how to release all-pairs shortest paths under edge\ndifferential privacy. The paper achieves an sublinear (\\sqrt{n}) error for this\nproblem using a vertex sampling scheme and adding Laplace noise (plus a positive\nconstant) to the edge weights. They solve the more general problem of\nreleasing a graph privately whose shortest paths match those of the input graph\nup to the stated bounds.\n\nFurthermore, they develop a second algorithm which computes all-pairs shortest\npaths in a graph with bounded feedback vertex set size. This assumption allows\nthem to leverage the tree-like properties of these graphs which enables better\nerror when this number is less than \\sqrt{n}.", "questions": "  Introduction: what are examples of graphs with small feedback vertex set?\n  Does the second algorithm have practical interest?\n\n  Related work: what are all of these papers and why are they somewhat relevant\n  to this setting?\n\n  Section 3.2: The graph $G_w' = (V, E', w)$ doesn't make sense because $w$ is\n  defined on just the original set $E$ of edges, whereas $E'$ contains more\n  edges. The explanations after Lemmas 3.3-3.5 are not providing much intuition\n  or a clear explanation.\n\n  Section 4: How does the FBS algorithm work on a high level? What do steps 1-5 \n  mean? What is the point of Lemma 4.1? ", "limitations": "There are no real limitations to this work.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ The algorithm achieves sublinear error which is often not possible for DP algorithms.\n\n+ The algorithm is simple and would be straightforward to implement. The \n  computational overhead is not too high and only involves releasing a graph\n  with O(n) more edges than the input graph.\n\n+ Their improved algorithm for graphs with bounded feedback vertex set is a good\n  generalization of the core ideas to a large class of graphs.\n\n- The writing of the paper is lacking. The section organization, the notation,\n  and the explanations, particularly in the algorithm sections, can be confusing\n  or non-existent.\n  The paper could also use general style and language improvements.\n\n- Their experiments are not very strong, providing just an example on a uniformly\n  random graph (which quite different from real-world graphs).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ALho227tbkR", "reviewer": "Reviewer_a4xF", "summary": "This paper studies the problem of computing differentially private (DP) estimates of all-pairs shortest path distances (APSP). In this setting, we are given a weighted graph $G = (V, E, w)$ and the goal is to output the shortest path distances between all pairs of vertices; the error is defined as the maximum error among all pairs of vertices. DP constraint here is on the *weights*. Specifically, it is assume that the underlying graph $(V, E)$ is public and two weights $w, w'$ are neighbors if $\\|w - w'\\|_1 \\leq 1$. DP then constrains that the output distribution on two such neighboring weights should not change too much. The changes are parameterized by two parameters $\\epsilon, \\delta$.\n\nSealfon (PODS 2016) was the first to study the question and gave an $\\epsilon$-DP algorithm with error $O(n)$ for general graphs and $O(\\log^{2.5} n)$ on trees. The main result of this paper is an $(\\epsilon, \\delta)$-DP algorithm with improved error of $\\tilde{O}(\\sqrt{n})$ in general graphs. The algorithm works roughly as follows.\n- First, add \"shifted\" non-negative version of Laplace noise to each edge. Note that here we may select Laplace noise to have std $O(1/\\epsilon)$.\n- Second, randomly select $\\sqrt{n}$ \"shortcut\" vertices, compute shortest paths (in $G$) between all pairs of shortcuts, add Laplace noise to these paths and then add these shortcut pairs as edges. Note that in this case there are only $n$ pairs and therefore the STD of the noise required is only $\\tilde{O}(\\sqrt{n} / \\epsilon)$ due to advanced composition theorem. \n- Compute the APSP in this new noised and \"shortcut-augmented\" graph.\n\nThe crux of the analysis is based on the fact that w.h.p. any shortest path from between nodes $u$ to $v$ can be decomposed into three parts: a \"short\" path $u$ to a shortcut, a path from a shortcut to another shortcut, and a \"short\" path from the second shortcut to $v$. \"Short\" here means that the path consists of at most $\\tilde{O}(\\sqrt{n})$ edges. Since we add Laplace noise with STD $O(1/\\epsilon)$ to each edge, this roughly means that the error in the first and last part is $\\tilde{O}(\\sqrt{n}/\\epsilon)$. On the other hand, we add Laplace noise with STD $\\tilde{O}(\\sqrt{n}/\\epsilon)$ to APSP of shortcuts, so the error in the second part is also $\\tilde{O}(\\sqrt{n}/\\epsilon)$. In total, we have that the error is $\\tilde{O}(\\sqrt{n}/\\epsilon)$.\n\nFinally, the authors extend the algorithm to graphs that have small feedback vertex set (FVS), which is the set of vertices whose removal makes the graph a forest. The algorithm proceeds by using vertices in FVS as shortcut, and then use Sealfon's algorithm for trees for the vertices outside. In total, this results in an error that is nearly-linear in the size of the FVS.", "questions": "- Can you please clarify the similarities / differences between this work and the other two concurrent works?\n\n### Comments for Authors (Non-Questions)\n\n- DP definition (Definition 2.2): the quantifier for $O$ is unclear. Please consider rephrasing.\n- I find the way noise random variables are defined in the algorithms to be strange. Currently, they are written as $X_e := Lap(\\mu, \\sigma)$. This is a bit strange; it almost looks like you define $X_e$ to be the distribution. Please consider rephrasing / changing the notation.\n- The notion for Laplace noise is also confusing: sometimes you write $Lap(\\mu, \\sigma)$ but sometimes only $Lap(\\sigma)$. Please consider fixing this.\n- Line 165: I think the noise $Lap(n^2/\\epsilon)$ should be changed to $Lap(O(n\\sqrt{\\log(1/\\delta)}/\\epsilon))$ due to advanced composition.\n- Line 177-180: \"To our best knowledge, this problem has no solution sublinear in $n$ in literature\". Actually it is pretty obvious to see that getting sublinear in $n$ is impossible. Let's consider the following example in the DP APSP setting: consider a graph where there are $n/2$ layers, each node connected to the consecutive layers, and let the weight of each edge be equal to some large number $W$. In this case, the original distance between the leftmost and rightmost nodes are $W(n/2 - 1)$, i.e. we pay $W$ to move to the next layer. Now, if you add Laplace noise to each entry, then we can continue moving from left to right while picking the lighter of the two edges. It can be seen that the expectation of the weight of such an edge is $W - \\Omega_\\epsilon(1)$. In total, this means that we get an expected error of $\\Omega_\\epsilon(n)$. \n- Section 3.3: I find the graph description to be vague. (E.g. the graph is \"multi-stage\" but currently only one stage is described.) Please add more details on how exactly are the graph generated.", "limitations": "No ethical concerns about this work as far as I can tell.\n\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n- APSP is one of the most important problems in algorithmic graph theory and is used as subroutine for many tasks. Therefore, it is likely that DP algorithm for APSP can be highly impactful. (In fact, as stated in the paper, this is a moderately well-known open problem in DP community.)\n- The algorithms presented are simple and practical.\n\n## Weaknesses\n\nI do not see major weaknesses. A couple minor points are:\n- There are two concurrent papers that seem to be achieving a similar result (in fact one of them seems to be getting better by some polylogarithmic factor). The current paper fails to discuss this, so it is unclear what the relationships / differences / similarities between the papers are.\n- The writing can be improved (see \"Comments for Authors\" below).\n\n## Evaluation\n\nGiven that the paper makes progresses on a fundamental problem in DP graph analysis and that the algorithm is simple & practical, I support acceptance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "A79r-Wt8Sak", "reviewer": "Reviewer_vGTs", "summary": "Overview of Problem:\nThis paper studies the problem of all-pairs shortest path distances (APSP) with differential privacy. In this setting, we are given an weighted graph, where the set of vertices and edges are known (and public), but the weights should be kept private. Since we cannot reveal the edge weights, the goal is to approximate every shortest path approximately up to small error. The model of privacy is where two weighted graphs are adjacent if one edge weight changes by 1 (in reality their definition is slightly more general).\n\nOverview of results:\nThey provide an algorithm that, under the approximate-differential privacy setting, can release all n^2 shortest paths simultaneously up to error roughly \\tilde{O}(sqrt{n}), while preserving privacy between adjacent datasets. This improves over the previous best work of Sealfon (PODS, 2016), which could do \\tilde{O}(n) error, or \\tilde{O}(sqrt{n}) error if the weights were sufficiently small (such as at most polylog(n)). They also consider special graphs where the underlying graph topology (i.e., the unweighted part of the graph) has feedback vertex set number k, meaning there exist k vertices that if you remove them you are left with no cycles. In this setting, they show one can get O(k*polylog n) error. Finally, they also provide some rudimentary experiments showing that on synthetic graphs, the error is in fact even smaller.", "questions": "N/A", "limitations": "This paper is almost entirely theoretical. While they do not discuss any potential negative societal impact, I cannot think of anything that needs to be said here so I don't think discussing this is necessary.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1) The main strength is that this is an interesting open question and significantly improves over a previous paper of Sealfon which was the PODS 2016 best student paper. It also resolves a main question which was also posed in the differentialprivacy.org website.\n2) The algorithms are simple and seem easy to implement.\n3) The technique for the O(sqrt{n}) error is based on a rather classic method of random hitting sets, meaning a random subset of vertices is well connected to the rest of the graph. While hitting sets have been used a lot in graph algorithms, using hitting sets in the correct way is still tricky, though does not seem to require incredibly clever ideas.\n4) The feedback vertex set result I believe is much more straightforward, and it is not clear whether graphs have small feedback vertex number in practice. This is a minor weakness since their main result appears to be the general graph case.\n5) There are some other papers which also studied this problem at the same time. These other papers also prove other results not in this work, such as proving a lower bound of n^{1/6}, and doing better than n^{1/2} when the weights are not too large. The authors indeed acknowledge these concurrent works in the appendix, and this also suggests this is an important problem if multiple groups were interested in this problem, so this is not entirely a disadvantage.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept