Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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).
strengths_and_weaknesses: STRENGTHS

S1. 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).

S2. 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).

S3. 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.

WEAKNESSES

W1. 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

W2. It would be easier to replicate Figure 1 if code was provided in the supplementary material

W3. Minor issues

- l. 182 "Definition Definition 3.4" => "Definition 3.4"
- is the red/blue color for external/internal references intended?

*Edit after author rebuttal / reviewer discussion*:

The 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.

questions: Q1. What is the expected performance on real-world graphs? Which topologies would work better/worse?

Q2. Suppose we limit ourselves to grid graphs and trees. How does the performance of the proposed approach compare to prior work numerically/empirically?

Q3. 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).
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Overview of Problem:
This 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).

Overview of results:
They 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.
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.
2) The algorithms are simple and seem easy to implement.
3) 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.
4) 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.
5) 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.
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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper investigates how to release all-pairs shortest paths under edge
differential privacy. The paper achieves an sublinear (\sqrt{n}) error for this
problem using a vertex sampling scheme and adding Laplace noise (plus a positive
constant) to the edge weights. They solve the more general problem of
releasing a graph privately whose shortest paths match those of the input graph
up to the stated bounds.

Furthermore, they develop a second algorithm which computes all-pairs shortest
paths in a graph with bounded feedback vertex set size. This assumption allows
them to leverage the tree-like properties of these graphs which enables better
error when this number is less than \sqrt{n}.
strengths_and_weaknesses: + The algorithm achieves sublinear error which is often not possible for DP algorithms.

+ The algorithm is simple and would be straightforward to implement. The 
  computational overhead is not too high and only involves releasing a graph
  with O(n) more edges than the input graph.

+ Their improved algorithm for graphs with bounded feedback vertex set is a good
  generalization of the core ideas to a large class of graphs.

- The writing of the paper is lacking. The section organization, the notation,
  and the explanations, particularly in the algorithm sections, can be confusing
  or non-existent.
  The paper could also use general style and language improvements.

- Their experiments are not very strong, providing just an example on a uniformly
  random graph (which quite different from real-world graphs).

questions:   Introduction: what are examples of graphs with small feedback vertex set?
  Does the second algorithm have practical interest?

  Related work: what are all of these papers and why are they somewhat relevant
  to this setting?

  Section 3.2: The graph $G_w' = (V, E', w)$ doesn't make sense because $w$ is
  defined on just the original set $E$ of edges, whereas $E'$ contains more
  edges. The explanations after Lemmas 3.3-3.5 are not providing much intuition
  or a clear explanation.

  Section 4: How does the FBS algorithm work on a high level? What do steps 1-5 
  mean? What is the point of Lemma 4.1? 
limitations: There are no real limitations to this work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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$.

Sealfon (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.
- 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)$.
- 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. 
- Compute the APSP in this new noised and "shortcut-augmented" graph.

The 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)$.

Finally, 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.
strengths_and_weaknesses: ## Strengths

- 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.)
- The algorithms presented are simple and practical.

## Weaknesses

I do not see major weaknesses. A couple minor points are:
- 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.
- The writing can be improved (see "Comments for Authors" below).

## Evaluation

Given that the paper makes progresses on a fundamental problem in DP graph analysis and that the algorithm is simple & practical, I support acceptance.
questions: - Can you please clarify the similarities / differences between this work and the other two concurrent works?

### Comments for Authors (Non-Questions)

- DP definition (Definition 2.2): the quantifier for $O$ is unclear. Please consider rephrasing.
- 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.
- The notion for Laplace noise is also confusing: sometimes you write $Lap(\mu, \sigma)$ but sometimes only $Lap(\sigma)$. Please consider fixing this.
- 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.
- 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)$. 
- 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.
review_title: null

Meta-review: metareview: The paper makes an important contribution on DP graph optimization literature. Most reviewers found the paper well written with no serious doubts regarding the correctness. We hope authors incorporate the comments from the reviewers in their final revision to improve the presentation.
confidence: Certain
Decision: Accept