A Generalized Binary Tree Mechanism for Private Approximation of All-Pair Shortest Distances
Authors: Zongrui Zou
Chenglin Fan
Michael Dinitz
Jingcheng Liu
Jalaj Upadhyay
Venue: NeurIPS 2025 poster ()
Keywords: differential privacy
graph theory
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: We study the problem of approximating all-pair distances in a weighted undirected graph with differential privacy, introduced by Sealfon [Sea16]. Given a publicly known undirected graph, we treat the weights of edges as sensitive information, and two graphs are neighbors if their edge weights differ in one edge by at most one. We obtain efficient algorithms with significantly improved bounds on a broad class of graphs which we refer to as *recursively separable*. In particular, for any $n$-vertex $K_h$-minor-free graph, our algorithm achieve an additive error of $ \widetilde{O}(h(nW)^{1/3} ) $, where $ W $ represents the maximum edge weight; For grid graphs, the same algorithmic scheme achieve additive error of $ \widetilde{O}(n^{1/4}\sqrt{W}) $.

Our approach can be seen as a generalization of the celebrated binary tree mechanism for range queries, as releasing range queries is equivalent to computing all-pair distances on a path graph. In essence, our approach is based on generalizing the binary tree mechanism to graphs that are *recursively separable*.

A Generalized Binary Tree Mechanism for Private Approximation of All-Pair Shortest Distances
Zongrui Zou, Jingcheng Liu"
State Key Laboratory for Novel Software Technology, New Comerstone Science Laboratory Nanjing University
zou zou.zonuuii@mmal @amailll@mmmlllmm .nju. edu cn, liuEnju. eaiinju.edu.cco
Chenglin Fan
Department of Computer Science and Engincering Seoul National University
Emnchenllin@gmil.. com
Michael Dinitzi
Department of Computer Science Johns Hopkins University
mdinitz0cs. jhu. edu
Jalaj Upadhyay?
Management Science & Information Systems Department Rutgers University
jalaj upwdhyayrrutgers.... edu
Abstract
We study the problem of approximating all-pair distances in weighted undirected graph with differential privacy, introduced by Sealfon [Sea16]. Given publicly known undirected graph, treat the weights of edges sensitive information, and two graphs are neighbors if their edge weights differ in one edge by at most one. We obtain efficient algorithms with significantly improved bounds a broad class of graphs which we refer to as recursively separable. In particular, for any n-vertex K₁ (iy-mioor-free graph, our algorithm achieve an additive error of (l(3W))333 where W represents the maximum edge weight; For grid graphs, the same algorithmic scheme achieve additive error of O(n be seen as a generalization of the celebrated binary /W). ). Our approach mechanism for range queries, as releasing range queries is equivalent to computing all-pair distances on path graph. In essence, our approach based on generalizing the binary tree mechanism to graphs that are recursively separable.
"L and ZZ have been supported by National Science Foundation China under Grant No. 62472212 and the New Cornerstone Science Foundation.
SSupported part by NSF award 2228995 JJ''s research was funded by the NSF CNS 2433628, Google Seed Fund grant, Google Research Scholar Award, Dean Research Seed Fund, and Rutgers Decanal Grant 302918.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Introduction
Graph-structured data arises in an enormous number of settings. As a result, analysis of graphs has important applications in not just computer science (networking, search engine optimization, bioinformatics, machine learning, etc.), but also in biology, chemistry, transportation and logistics, supply-chain management, operations research, and even in everyday applications like finding the shortest route on a map using GPS navigation. Since in some applications these graphs can encode sensitive personal information, the analysis of sensitive graph data while preserving privacy has attracted growing attention in recent years. One of the main privacy notions that has been proposed and used extensively in such graph analysis is differential privacy, with successful applications including cut approximation [30 24
15
11 spectral approximation 6 4 correlation or among
hierarchical clustering 19 32 and numerical statistics release
others.
Recently, starting with Sealfon 42,, the problem of releasing All-Pair Shortest Distances (APSD) on a weighted graph with differential privacy has received significant attention [26 25
12
23 16 7] due
to the practical importance and applicability of private graph distances and the fact that the problem itself is inherently natural. In this line of work. given an nevertex weighted graph G = ([z]. E, w), the goal is to output the values of the shortest distances between each pair of vertices, while preserving weight-level differential privacy, where two graphs are considered neighboring if they share the same edge set (i.e., the topology is public information) and differ in the weight of exactly one edge by at most one.
Sealfon 42 introduced the problem and use a post-processing scheme to gave algorithm with Önn/s) additive enror for pure and approximate differential privacy with privacy budget E. This bound was improved subsequently [12 26 using a simple sub-sampling technique, reducing it to only O (T/s)) for approximate differential privacy. For the lower bound side, the first result on private APSD was provided by Chen et al. [12), who established a lower bound of Q( (()) This bound was recently improved to 22(n2/4/e) by Bodwin et al.
Though ((v ((v1) error is the best known for answering private APSD in general graphs, it is possible to significantly improve it for many special classes of graphs. For example, outputting all pairs shortest distances in an n-vertex path graph is equivalent to answering all possible range queries on a vector of length n
42 Under weight-level privacy, this task can be solved with only polylog(n) (n) additive
error using the classic binary free mechanism [9 10. This mechanism leverages the Bentley and Saxe data structure [5] to reduce the number of compositions required for privacy. More generally, Sealfon 42 shows that the polylog(11) error can also be achieved when privately answering the shortest distances in an n-vertex tree.
However, there is a lack of work on private APSD for graphs that lie between trees and general graphs a gap that encompasses many graph classes commonly encountered in practical applications. such as planar graphs. Perhaps the most natural example of such an application is finding the shortest distances in road maps or metro networks, where all the routes can usually be represented in the plane, and edge weights are determined by traffic (higher edge weights indicate more traffic, which navigation tools should tend to avoid). Therefore, we have the following natural question:
Question Is it possible to solve private all- all-pairs shortest distances with better utility in planar graphs (or other natural class of graphs) than in general graph
In this paper we answer this question in the affirmative, by showing that for any Ky-minor--ree graph there exists an efficient and differentially private algorithm that achieves an additive error of O(h (nW) for answering APSD, where W is the maximum edge weights. This result immediately implies an (((n))133 error for private APSD on planar graphs, as every planar graph K5-minor-free free [37]. Additionally, for a v' v/n grid graph, within the same framework, we 1/441//
further reduce the error of private APSD to only Ö 2123 ). These results improve multiple previous upper bounds that also depend on W. (See Section I.I for details.) Such an upper bound W
presents a purely differentially private *On graphs with bounded tree-width p. interesting result by 23
algorithm that outputs all- pair shortest distances with an additive error of Ö(p²/e) /e). This bound however, does not lead improvement planar graphs, as the tree-width of planar graph can be large as O(yn).

---

on edge weights is also natural in real-world scenarios, such as packet routing, where it is defined by the bandwidth of the network.
From a technical point of view, our results can be considered as generalization of the mechanism
proposed in Sealfon [42] for computing APSD on n-vertex tree. Their mechanism inherently extends the binary tree mechanism, which originally operates on a single path, to a tree structure, achieving an error bound of polylog(n). Therefore, to further extend this approach more general graph topologies beyond paths or trees, we pose the following fundamental question:
What underlying property allows the binary tree mechanism to reduce the error in answering APSD queries on paths or trees?
Question 2
To answer this question, we propose the concept of recursive separability (Definition We show that the recursive separability of tree graphs is the inherent reason why the binary tree mechanism significantly reduces the error in answering APSD. Intuitively, graph as recursively separable if it has a balanced separator such that when the separator is removed, the resulting subgraphs themselves are also recursively separable.
By working with recursively separable graphs, we develop a private algorithm based on a divide-and- conquer strategy to compute all-pair shortest distances, with an additive error characterized by the quality of the separators of the input graph. As a consequence, our algorithm not only encompasses the older use cases of the binary tree mechanism [19] 10 20 42), but also extends to much broader class of graphs that exhibit recursive separability, including planar graphs or Kg-minor--f Importantly, our results also open up the opportunity to leverage rich body of prior work on graph separation theorems (e.g. 38
graphs
28 3
29
2
35
27
36 to the design of private APSD algorithms.
1.1 Our Results
In this paper, we consider the standard weight-level privacy setting 42 In this setting, two positive weighted vertices graphs G ([x), E, w). G' ([n), E, w') with the same edge topology neighboring if w - w'loo I and w w 11 I 1, ic.. there is an edge which differ by at most 1. [B] Here, w, w 20 encodes the edge weights, where Rzu denote the set of positive real numbers.
For a graph G, a separator of G a subset of vertices that, when removed, splits the graph into two or more disconnected components. Formally, separator is subset of vertices C V where there exist disjoint vertex sets A and B such that A U B = V and no edge joins a vertex in A with vertex in B. To privately compute all-pairs shortest distances using divide-andd-onquee approach, we first introduce the concept of recursive separability.
Definition 1. Fix p E N and 9,4 E TR such that 5 < q' 1. An undirected graph G (V, F) is (p, q, d') recursivvly separable if and only if either [V| = O(1) or:
G has separator S C V of size |S| < min (g' v)]V such that each connected component G" = (V E(V) has at most q V vertices, and
Every subgraph of Gs (p. q. q')")
( recuussivey separable.
Remark 2. We note that the definition of recursive separability is oblivious to edge weights. Thus, we say a weighted graph is recursively separable if its underlying graph is recursively separable.
Our first result is a general algorithm that privately computes all all-pairs shortest distances for any graph, with an error bound that depends on the quality of the graph's 's separators.
Theorem 3. Fix privacy budgets 0 < e, < 1, and suppose 2 S < g' < 1 are constants. For any weighted n-vertex (p, q, 9 "recursvvv separable graph G. there exists an (s, -)differrentiall private algorithm such that with high probability, outputs APSD on G with worst case additive error at most O (n//)(n/))
Notably, Theorem 3 offerrs wide range of intriguing implications, as the definition of recursive separability captures large class of natural graphs. Some example with implication includes
1. All n-vertex trees are (1, 3- ately recovers the error bound for privately computing APSD on trees in 42 (though with extra logarithmic factor).
2
separable. Therefore, Theorem 3 immedi-
3

---

free Table Current error bounds for APSD under (E, -ddffferrent privacy with bounded edge weights.
Sealfon
[42
Chen et al. [12
Ours
planar graph
nW
Ōs [= 2
Ös
(nW)
e2/3
grid graph
Os W 1/3
173
(same above)
Os
n1/4//0
ga/2
2.
Any graph with tree-width p is (p 1, 3: o(1)) -(e))rrecussvvely separable (which follows as an immediate corollary of Robertson and Seymour (4T). Therefore, Theorem imppoves the private APSD result for bounded tree-width graphs in 23 from O(p²/e /E) to (p/s))
Leveraging the well-known separation theorem for planar graphs 28 38 we also conclude that all planar graphs are (O(vn). 5. + o(1))- separable. Though applying Theorem does not immediately yield any non-trivial improvement for planar graphs, we demonstrate that with slight modification to the recursive framework of the algorithm in Theorem 3 we can achieve an improvement not only on planar graphs but also K2, Ky-minor-free graphs. Recall that graph is K₁- minor-free if the clique of size h, denoted by Ki, is not a minor of it. If graph is but contains K2, minor, then h is also known the Hadwiger number [31]
Theorem 4. Fix privacy budgets O < E < 1, and integers W,h 2 1. For any weighted Ki- minor-free graph G (In), w) with ||w]| I W. there exists a (e, (eiff-eieerrettialll private algorithm such that with high probability, it outputs APSD on G with worst case additive ervor at most Og (h- (mW)1/8
22/3
By Kuratowski's Theorem 371. planar graphs are K5 finer-free. This gives the following corollary: Corollary 5. Fix privacy budgets 0 < 8 < 1, and integer W 2 1. For any planar graph G ([n], E, w) with ||o S W, there exists (e, diffferrent private algorithm such that with high probability, oulputs APSD on G with worst case additive error most Os (nW)
Building on the same algorithmic framework, we show further improvement for a specific subclass of planar graphs: grid graphs.
Theorem 6. Fix privacy budgets O < E, < 1, and integers W 2 1. For any n/a grid graph G ([a n/a), E,, w) with ||l]] S W, there exists a (c, 8) -iiffferrnttill private algorithm such that with high probability, it outputs APSD on G with worst case additive error at most (1442
Os
2172
In Table provide brief overview of the existing results differentially private all all-pairs shortest distances approximation when assuming an upper bound W on edge weights (in this table,
= 2 1 x 0.4143). This assumption also appears in Sealfon 42 and Chen et al. 12
1.2 Technical Overview
Here, we introduce the technical ingredients that underpin our results on the private APSD approxi- mation and discuss the key concepts behind our analysis of privacy and utility guarantees.
1.2.1 Recursively computing APSD by separators
One of the most basic approaches to computing all-pair shortest distances on graph is to add noise to the weight of each edge in E. This results in the error of a path being roughly proportional the number of hops on the path, which leads to ((n/s) error 42]. Using basic probability theory, can be shown that with high probability, uniformly sampling Ol ni log n) vertices from the vertex set of a connected graph forms k-covering set (see Definition 10p of the original graph, where k 0( n). By privately computing all-pair shortest distances within the ((vn) vertices in the
covering set, the error private APSD can be further reduced to Ö(Vn/E) 12 26 since in each
path, the covering set is guaranteed to be encountered after passing through the O O(yn) vertices.
Thiis also suggested open problem by Sealfon in personal communication.

---

However, the above methods do not make use of any combinatorial properties or topological structure of the graph. To take advantage of this, we observe that some specific classes of graphs, including trees or planar graphs, exhibit good separability, allowing us to use the divide-and-conquee method to recursively compute the shortest path. Specifically, for a graph G (V. E, w); and x. y E V, let da(2; y) be the distance between I. y in G. Then, if G has separator S S V that separates the graph into two subgraphs G1 and G2, we observe that for any pair z, y E V that are not in S, their distance can be written as
do(r.v) min (d,,(1;)) do(a, (b,(b,)))) (b, a.bES
if G1 and y E G2- Then, the error accumulated in each recursion corresponds the error in privately computing the distances in Go between each vertex inside S. Intuitively, the recursion step can be illustrated by binary tree of O [VI) levels if the input graph can be recursively divided by a series of well-balanced separators. However, this does not directly give the Ö(p/s) error if the input graph is (p. (1), ((1)) recursively separable, since the error accumulates across all leaf vertices in the corresponding recursion tree. To address this issue, we employ a pruming trick that directly establishes relationships between adjacent levels of separators, preventing errors from accumulating within the same level. In particular, we add shortcuts between adjacent levels of separators to form a series of complete bipartite graphs to control the error.
In summary, the key distinction between our technique and those employed in other works that improves private APSD [12 (26) lies in our utilization of the graph's topology to construct highly structured shortcuts. In contrast, the shortcuts constructed in previous works are oblivious to any combinatorial properties of the graph.
1.2.2 Approximating distances within separator using covering sets
In Section 1.2.1
we briefly introduced how construct an algorithmic framework such that the error in estimating private APSI primarily depends on the size of the separators for recursively separable graphs. Recall that in our recursive framework, we need to construct two types of shorteuts: those within the separators and those between adjacent separators. Therefore, by examining the separability of certain classes of graphs, the overall error for private APSD can be further reduced by optimizing the error incurred when estimating the distances of vertices inside or between separators. In this section, we focus solely on illustrating the idea for reducing the error in estimating the APSD (i.e., the lengths of the shortcuts) inside separator. The idea for reducing the error in estimating the lengths of shortcuts between two adjacent separators is similar.
Specifically, suppose that the edge weights are upper-bounded by some constant W 2 1. Then, we observe that finding a k-covering set (Definition 10) of the separator S and computing the all-pair distances for all vertices inside the k-covering set provides an approximation of all-pair distances within S. with extra additive error at most kW. The advantage is that by computing APSD only for the k-covering set, the number of compositions required to preserve privacy is significantly reduced when k < [S]. This approach is similar to the one by Sealfon 42] for improving the error in estimating APSD for grid graphs. However, without our recursive framework, they use this trick by finding a k-covering set for the whole graph instead of only for separators, which limits its ability to achieve further improvements. In our recursive framework, we observe that a grid graph is separable with series of connected separators of size at most (VVn). Consequently, one can show that each separator has a (n1/4) (n'/*))-overing --ooeeiigg set of size at most On On!//), /4), which finally leads to an Ö(n error (for constant W) for grid graphs by the advanced composition theorem.
Achieving improvements on general planar graphs is similar but somewhat more tricky, as the separators are not necessarily connected. To make progress, for connected planar graph G on vertices, we first partition the vertex set of G into about ((n/d) disjoint subsets, such that each subset has diameter most d (in terms of the subgraph defined by this subset of vertices). Then, we contract each subset into a super-node, merge all multi-edges and obtain smaller planar graph G with On /d) super-nodes. By Lipton-Tarjan separation theorem for planar graphs 38 G has separator of size at most O ((Vn/d), and thus privately computing the all-pair shortest distances
'We have to privately compute de (a, b) for any a, b E S instead of ds b) because that the shortest path between v, y may repeatedly enter and exit the separator S.
5

---

inside Š iincurs an error of at most Ö( ((yn/d=²). This implies an approximation of the APSD within the original separator S with an error of
2dW + Õ( ((vn/de
(I)
since the diameter of each super-node is at most d. By choosing an appropriate value for d, we obtain an (((w))//s) error for estimating APSD inside separators of a planar graph, and thus the same error with some extra logarithmic factors for estimating the APSD in the entire graph. Finally, this approach can also identically applied to Ka-minorr-ree graphs (see Lemma (1). Note that the dependence on the maximum edge weight W in ( is inevitable, as it ensures that the shortest paths within S remain reasonably close in length to the global (true) shortest paths.
2 Private APSD Approximation For Recursively Separable Graph
In this section, we study answering all all-pair shortest distances recursively separable graphs with differential privacy. Let G be a graph with non-negative edge weights, and let v. y be two vertices in G. da (ar, y) denote the (shortest) distance between and y in G. Specifically, we establish the following result:
Theorem 7 (Restatement of Theorem 3 Fix any O < e, < 1, and n, E N. For any graph G = ([n), F., w) that is 9, g. separable (Definition [ for some constants 1 S S o' < 1, there is an (e, diffferrentiall private algorithm such that, with high probability, it outputs estimations of shortest distances (do(s, 2.g(())) satisfying
( llg' n log(n/6)
(da(s t) - do t) S So
We provide our algorithms for privately computing APSD in recur- sively separable graphs in Section 2.1 Because of the space limit, we defer the privacy guarantee (Theorem [9) of our algorithms and its analysis Appendix [.1] The utility guarantee (Thcorem 20) with detailed analysis is given in Appendix B.2
Proof outline of Theorem 7
Combining Theorem 19 and Theorem 20 concludes
the proof of Theorem]
The corresponding result for pure-DP. Our framework can be easily adapted to pure differential privacy by (1) replacing Gaussian noise with Laplace noise in the shortcuts, and (2) employing basic composition instead of advanced composition. Using the Laplace mechanism and the tail bound for Laplace noise, one can directly derive the following theorem from our framework. The proof is therefore omitted.
Theorem 8. Fix aixape E N. Let G = (V,E, w) be a (q. P. p. separable graph for some constant 1/2 S <. Then, there is (c, -)diifferettially private algorithm estimating APSD such that with probability at least 1 - %
p22 1p2log" n(logn log(1/7))
((s,t) - d(s,t) t)l s
2.1 The Algorithm
Our algorithm is built upon a sequence of decompositions applied the input graph, with the resulting process being traceable through a binary tree.
The Construction of the Binary Tree. Given unweighted and undirected graph G ([n], E) that is (p, g, g' )')rreursivelly separable, we consider deterministic and recursive procedure that finally separates the graphs into O(n) pieces of subgraphs of constant size (we note that the vertex in these pieces may have intersection). We will see later that the bounded number of pieces is ensured by the property of recursive separability. More specifically, in the first epoch, since G is (p. q, q precurssyy separable, then there exists an S C [n] such that removing vertices in S results in two subgraphs G6 (Vg (Vi)), G² (V1, E(Vi)) that are not connected, and max([V6 [V]1] S gn. We let
Go = (V) U E(V U ()))(S)) and G (V US E(V' U (S)).
(2)

---

That is, we union S into G2 (or G%) together with all edges incident between S and Gý (or G22.. From the recursive separability of G, we also have that
max [il} S qn + |S| S q'n.
where Vo (or V/1) is the set of vertices of Go (or G1).
In the recursive subroutine, for graph Gb where b is binary string of length that depends on the current depth of recurrence, there must exist a separator S. that separates G5, into G/11 and Goo Similarly in eq. 2 we let
Gb01 (Vis1 U Sb, EVV.. U (t)) and Gooo = (Vion U Sb, E(Vhoo U (E))))))))
The recursive procedure terminates when Gg has constant size c. Clearly, the depth of the recursion is /0g1//²= n log(n/e)
log(1/q/) = O(log n) for any constant 0 < o < 1. Further, these graphs construct a binary tree T with (log n) levels. where the root of T is G, and the nodes in the i-th level is just the all G2 's with |b] = i, and each G₁ in the leaves of T has size at most c. In each non-leaf node of T, associate it with a label (Gs, S.) denote the subgraph it represents and the separator used to further split Gg. We note that for the root, b = Ø
The Algorithm. With the construction of the binary tree described above, we are ready to present our algorithm. For keeping the presentation modular, we present in form of three algorithms: Algorithm defines how we add shortcuts, Algorithm 3 describes the recursive procedure that is used by Algorithm 2 to compute all all-pair-shortest distances.
In Algorithm D we first add highly structured shortcuts based on the decomposition described above to generate private synthetic graph. particular, there are two types of shortcuts: (1) between all pairs of vertices within each separator that is determined by the decomposition procedure, forming a complete graph, and (2) between vertices in every pair of adjacent separators, forming a complete bipartite graph.
Then, post- post-prceessing stage, in Algorithm 2 we compute the all-pair shortest path distances privately for a weighted graph by calling the recursive procedure for each pair (AlgorithmB) B3. Here, for any 8, L V, use (s, to denote the value of the local shortest distance between s and in the subgraph G3. If either 8 or / does not appear in Vn, then we set do(s, L) co. In our algorithms, for any y, E [n] and b E (0, 1)", we define IsShortcut(ss (x, b) True if noisy edge (i.e., shortcut) is added between x, y within the separator of Go, or between the separator of G. and that of its precursor graph.
3 Improved Results for -innorrreere Graphs
In this section, we utilize the algorithmic framework proposed in Section to present our improved results privately answering APSD for some special classes of graphs. In particular, assuming bounded weights, where the maximum weight of edges is denoted as W, and by some specific separa- tion theorems for special graphs, we use the general framework (along with sub-sampling trick inside the separator) achieve purely additive error of ~ (nW))1/3 when privately approximating APSD K₁, Ką,minor-fiee graphs for any constant h. Additionally, as a special subclass of Kş-minor free graphs, we able to leverage some unique structural properties of grid graphs to further reduce the additive error approximately ~ n- /W.
Theorem 9. Fix any O < E, < and n E N. There exists an (e, 8) -iiffefrretti private algorithm for estimating all- all-pairs shortest path distances in G such that, with high probubility, the worst-case error is bounded by (1//4 ///4//W Aog? n log log for any grid graph G = ([a x b), E, w) where ab = n. Further, the error is bounded by O (h- (nW) 1/9)1/9.oo""
///2
log
log
with high probability,
2473
for any Ky.-minor-free graph G = -[n], F,W). w).
Proof outline of Theorem 9 We first present here the modifications to the recursive framework described Section 2 that are required to derive Theorem while deferring the detailed analysis of to Appendix C Specifically, instead of constructing the all-pair shortcut inside or between separators we find a k-covering set of each separator and only add shortcuts inside or between such covering sets to reduce the number of compositions needed to preserve privacy.
as in Algorithm I
7

---

Algorithm 1: Constructing private shortcuts.
Input: Graph (V, F., w), private parameter e, 6.
1. Recursively construct a binary tree 'I as described in this section.
Set à log1// (n/c), c/v /4/ log(80)))) and 8' (4h).
3. Let (lg2202112))/8 /s'.
for non-leaf node Sc) E (7) do for x, y E Sb such that # y do
IsShortcut(z, y. b) True
Let dz = (z v) +((, end if
* 23 then
Let b' be the binary string that removes the last bit in b.
for (x, y) E Sy x S, do
if σ. y & Sy n SS, then IsShorteut(z, y. = True. Let (z v) = do(x, v) (N0
end
end
end
end
5. for leaf node (Go, -) E (()) do for x. E Vo such that + y do
IsShortcut(I.) y. True
Let de dz( .N (o. 2c 1og(1.25/8))
(E')²
end end
Output:The
binary tree T, and du, v) for all u, E and {0, 1] such that IsShortcut(r: y. b) True.
Algorithm 2: Differentially private all pai---i---- shortest- approximation
Input: Graph G = (V, E, w). private parameter E, 6. 1. Run A on G' and 6, obtain the labeled binary tree T. for s, E V such that + t do
d(z y) < Recursive-APSDD? (,, (s,
// Algorithm
end
Output estimated distances dx y) on G.
Definition 10 (k-covering). Given a graph G (V, E). a subset 2 C V is k-covering of V if for every vertex E V. there is vertex 6 Z such that the hop distance between and b is most k.
The construction of the binary tree for Ka-minor-free graphs is similar to that for general graphs, and that Ki-mmnorrfrre graph G with n vertices are guaranteed to always have (not necessarily connected) separator of size at most O(vhán) such that removing S results in two disjoint subgraphs G and G' (see Lemma 27). Both subgraphs are clearly also Ka-minor-free and are of size most 2n/3. This process can be repeated recursively, splitting each subgraph until every part has constant size. For any grid graph on vertices of shape x b, we can split the graph into two sub-grid graphs of (almost) equal size using a separator size at most (vv)). and that the separator is connected. Hence we have the lemma below.
Lemma 11. Fix integer h > 1, any Ki-minor-free graph G = ([n], E) is (eVhin 2/3,2/3 cx3/2 ( rrecuusvvv separuble for some constant In particular; planur gruphs (as well as grid graphs Gynd ([a x b), F.) with ab n) are (dl nn, 2/3, + -ecuureely sepurable for some constant d.

---

Algorithm 3: Recursive-APSD(T Gb, ts)
Input: A binary tree constructed out of some graph G (V, E, w). a graph Gb, a pair of vertices s, E Vo, integer N. 1. if IsShortcut(s; f, b) = True then
Halt and directly output da(s, i) computed by Algorithm end
2. if' A: O then
both s, E Vooa for a E {0,1) then
for 2 S do
dona (8, 2) Recursive-APSD(T.C Gboar (s, (), k 1).
dona (t, (t,z) 2) t Recursive-APSD((, Gboas 2), K + 1).
end
Jnea (8, 1) + Recursive-APSDDT Gboa; (8, 0), (s, + min(fboa (s, t), minz.yes, ( x) + do(2,, y) + 2soa (y., {)}
end
if
Vhoa and E Vboa. then
for 2 E Sb do
droa (s, 2) & Recursive-APSD(T. Gboa. (s, le 1).
dhoa (t,z) 2) t Recursive-APSD(T Gboa (t, 2), k + 1).
end
(s, t) + minz,yes, Aboa((s + do(xr v) + doca (v, 1)
end
end
3. if A 0 then
Let be the binary string that removes the last bit in b.
s, & Sy then
Halt and output FAIL.
end
WLOG let Sy (if not we just switch and t).
for z Si do
drea (8, 2) Recursive-APSD(T Gboa: (8, 2), 2), 1).
end
both s, E Vosa for {0, then
dhea (8, 1) + Recursive-APSD(T. Gboas (8, 1),0).
Let do(s,t) min(dhoa (s. f), min droa (s, + do (z, f)).
end
if
Vhon and E Vhoas then ds(s,t) + minges, Ahoa (s, x) + dd(xx t).
end end
local distance (s,tt..
As we introduced earlier, with this decomposition, the only modification required is in Algorithm In Algorithm [ we construct private shortcuts by connecting all pairs of vertices in separator. We
now modify Algorithm into Algorithm 4 follows: for each separator, we begin by finding k-covering for it. Then, we construct private shortcuts by connecting all pairs of vertices within the k-covering sets. We provide the complete pseudocode for Algorithm in Appendix D and here we only highlight the differences. The modified step 4 of Algorithm is as follows.

---

Step 4 of Algorithm 4 (modified step 4 of Algorithm for non-leaf node (Gb, St) E ((T) do
Find k-covering set of So, and let it be S for æ,, y/ E S such that x + y do
IsShortcut(r.. y. b) True. Let do, v) do(r, + +N(00
end
if b * Ø then
Let 6' be the binary string that removes the last bit in b.
Find a k-covering set of Sy, and let it be Sg.
for (xc, y) St x S do
if xr y $ S n S then
IsShortcut (1
True. Let dz(x, = do(o,)) +N(0,02).
end
end
end
end
We also modify Step of Algorithm|] to revise the number of compositions needed for privacy from O(p²) Of (p, k)), follows:
Step 3 of Algorithm Let a = (v. k) 2 log(1 (ogg(.2/1188 1.25/88)/e', where f(p, k) is the upper bound of the size of the k-covering set for the separator of size p.
References
[1] Almost linear time differentially private release of synthetic graphs, 2025.
[2] Noga Alon, Paul Seymour, and Robin Thomas. separator theorem for nonplanar graphs. Journal of the American Mathematical Society, 3(4):801 1990.
[3] Noga Alon, Paul Seymour, and Robin Thomas. Planar separators. SIAM Journal on Discrete Mathematics, 7(2):184-193, 1994.
[4] Raman Arora and Jalaj Upadhyay. On differentially private graph sparsification and applications. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc Emily B. Fox, and Roman Garnett, editors, Advances Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 13378-1323 -3389, 2019.
[5] Jon Louis Bentley and James B Saxe. Decomposable searching problems. 1978.
[6] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The Johnson-Lindenstrauue transform itself preserves differential privacy. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 410-419. IEEE, 2012.
[7] Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth. Jalaj Upadhyay, and Chen Wang. The discrepancy of shortest paths. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 5 International Colloquium on Automala, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia, volume 297 of L.Ples, pages 27:1-27:20. Schloss Dagstuhl- Leibniz-7entrum für Informatik, 2024.
[8] Christian Borgs, Jennifer T. Chayes, Adam D. Smith, and Ilias Zadik. Revealing network structure, confidentially: Improved rates for node-private graphon estimation. In Mikkel Thorup, editor, 59th IEEE Annual Symposiun on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 533-543. IEEE Computer Society, 2018.
[9] Mark Bun, Marek Elias, and Janardhan Kulkarni. Differentially private correlation clustering. In International Conference on Machine Learning, pages 136--116 PMLR, 2021.
[10] T.-.. Hubert Chan, Flaine Shi, and Dawn Song. Private and continual release of statisties. ACM
Trans. Inf. Syst. Secur. 14(3):26:1-22 1-::2224 1.
10

---

[11] Rishi Chandra, Michael Dinitz, Chenglin Fan, and Zongrui Zou. Differentially private algorithms for graph cuts: shifting mechanism approach and more. arXiv preprint arXiv:2407.0633 0691 2024.
[12] Justin Y. Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Shyam Narayanan, Jelani Nelson, and Yinzhan Xu. Differentially private all-pairs shortest path distances: Improved algorithms and lower bounds. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 5040-5067. SIAM, 2023.
[13] Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi, Vahab Mirrokni, Andres Munoz Medina, David Saulpic, Chris Schwiegelshohn, and Sergei Vassilvitskii. Scalable differentially private clustering via hierarchically separated trees. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 221 221-230, 2022.
[14] Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi- Fard, Nikos Parotsidis, and Jakub Tarnawski. Near-optimal correlation clustering with privacy. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave. K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Anmual Conference Neural Informa- tion Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28- December 2022, 2022.
[15] Mina Dalirrooyfard, Slobodan Mitrovic, and Yuriy Nevmyvaka. Nearly tight bounds for differentially private multiway cut. In Proceedings of the 37th International Conference on Neural Information Processing Systems, pages 24947-24965, 2023.
[16] Chengyuan Deng, Jie Gao, Jalaj Upadhyay, and Chen Wang. Differentially private range query on shortest paths. In Pat Morin and Subhash Suri, editors, Algorithms and Data Structures 18th International Symposium, WADS 2023, Montreal, QC, Canada, July 31 Augustt 2, 2023, Proceedings, volume 14079 of Lecture Notes in Computer Science, pages 340-370. Springer, 2023.
[17] Xiaofeng Ding, Shujun Sheng, Huajian Zhou, Xiaodong Zhang, Zhifeng Bao, Pan Zhou, and Hai Jin. Differentially private triangle counting in large graphs. IEEE Transactions on Knowledge and Data Engineering, 34(1 11:52))-5529) 2021.
[18] Cynthia Dwork, Frank McSherry. Kobbi Nissim, and Adam Smith. Calibrating Noise to Sensitivity in Private Data Analysis. TCC, pages 265-284, 2006.
[19] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In Proc. of the Forty-Secone ACM Symp. on Theory of Computing (STOC'IO), pages 715-724, 2010.
[20] Cynthia Dwork, Moni Naor, Omer Reingold, and Guy N Rothblum. Pure differential privacy for rectangle queries via private partitions. In International Conference on the Theory and Application of Cryptology and Information Security, pages 735-751. Springer, 2015.
[21] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Founda- tions and Trends in Theoretical Computer Science, (1:41))::400 2014.
[22] Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In Proc. of the 51 Annual IEEE Symp. on Foundations of Computer Science (FOCS), pages 51-60, 2010.
[23] Javad Ebrahimi, Alireza Tofighi Mohammadi, and Fatemeh Kermani. Differentially private all-pairs shortest distances for low tree-width graphs. In 2023 International Symposium on Networks, Computers and Communications (ISNCC). pages 1 1-6. IEEE, 2023.
[24] Marek Eliáš, Michael Kapralov, Janardhan Kulkarni, and Yin Tat Lee. Differentially private release of synthetic graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 560-578. SIAM, 2020.

---

[25] Chenglin Fan and Ping Li. Distances release with differential privacy in tree and grid graph. In 2022 IEEE International Symposium on Information Theory (ISIT), pages 2190-2195, IEEE, 2022.
[26] Chenglin Fan, Ping Li, and Xiaoyun Li. Private graph all pwwpwiiss--hootett-attte distance release with improved error rate. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NewrlPS 2022, New Orleans, LAA, USA, November 28- December 9, 2022, 2022.
[27] Jacob Fox and János Pach. A separator theorem for string graphs and its applications. Combi- natorics, Probability and Computing, ((3))371-390 2010.
[28] John R Gilbert, Joan P Hutchinson, and Robert Endre Tarjan, A separator theorem for graphs of bounded genus. Journal of Algorithms, 5(3):391-407, 1984.
[29] Michelangelo Grigni and Andrzej P. Woloszyn. Well-connected separators for planar graphs. CiteSeerX, 2004.
[30] Anupam Gupta, Aaron Roth, and Jonathan Ullman. Iterative constructions and private data release. In Theory of cryptography conference, pages 339-356. Springer, 2012.
[31] Hugo Hadwiger. Über eine klassifikation der streckenkomplexe. Vierteljschr Naturforsch. Ges. Zürrich, 88(2)1333-42,, 1943.
[32] Jacob Imola, Alessandro Epasto, Mohammad Mahdian, Vincent Cohen-Addad, and Vahab Mirrokni. Differentially private hierarchical clustering with provable approximation guarantees. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolula, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, PMLR, 2023.
pages
[33] Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. Differentially private triangle and 4-cycle counting in the shuffle model. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pages 1505-1519, 2022.
[34] Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. Analyzing graphs with node differential privacy. In Amit Sahai, editor, Theory of Cryptogra- phy 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings, volume 7785 of Lecture Notes in Computer Science, pages 457-476 Springer, 2013.
[35] Ken-ichi Kawarabayashi and Bruce Reed. A separator theorem in minor-closed classes. In 2010 IEEE 51st Annual Symposium Foundations of Computer Science, pages 153-162. IEEE, 2010.
[36] Tuukka Korhonen and Daniel Lokshtanov. Induced-minor-fie minor-free free graphs: Separator theorem, subexponential algorithms, and improved hardness of recognition. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5249-5275. SIAM, 2024.
[37] Casimir Kuratowski. Sur le probleme des courbes gauches en topologie. Fundamenta mathe- maticae, 15(1):271-283, 1930.
[38] Richard Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM Journal Applied Mathematics, 36(2):177-189, 1979.
[39] Jingcheng Liu, Jalaj Upadhyay, and Zongrui Zou. Optimal bounds on private graph approxi- mation. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1019-1049. SIAM, 2024.
[40] A. Meir and J. W. Moon. Relations between packing and covering numbers of a tree. Pacific Journal of Mathematics, 61(1):225- - -233, 1975.
12

---

[41] Neil Robertson and Paul D Seymour. Graph minors. v. excluding planar graph. Journal of Combinatorial Theory, Series B, 41(1))92-114, 1986.
[42] Adam Sealfon. Shortest paths and distances with differential privacy. Proceedings of the 35th ACM SIGMOD-SIGAC7-SIGAA Symposium Principles of Database Systems, pages 29-41, 2016.
[43] Jonathan R. Ullman and Adam Sealfon. Efficiently estimating erdos-renyi graphs with node differential privacy. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence A'Ach--Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference Neural Information Processing Systems 2019, NeurlPS 2019, December 8- 14, 2019, Vancouver, BC, Canada, pages 3765-3775, 2019.
[44] Jalaj Upadhyay, Sarvagya Upadhyay, and Raman Arora. Differentially private analysis on graph streams. In International Conference on Artificial Intelligence and Statistics, pages 1171-1179. PMLR, 2021.
[45] K. Wagner. Uber eine erweiterung eines satzes von kuratowski, deutsche math. 1937.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Our abstract summarizes the main contributions and their scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We mentioned why the error bounds depend on edge weights, and clearly stated the lower bound results.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
We provide full proof of each result.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We give detailed instructions on the implementation.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer:
[Yes]
Justification: Provided in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cppppi.ccppulli//uuuiu wwwtii/gguie///eeeeceoocc CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We stated details in the setting of experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
The error metric corresponds to the one used in theoretical results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
16

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We stated the computer resources.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: h/tprrip/////ips.eeeeeepr httpp///....pppppieicccccccciiee
Answer:
[Yes]
Justification:
We follow the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: We present theory work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
17

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We present theory work.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: We present a theory work.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppswpptseeee wwworeewwthhhe....c. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
18

---

Answer:
[NA]
Justification:
We present a theory work.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/codd/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We present a theory work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: We present theory work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
19

---

Justification:
We do not use LLM at all.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy htteap////aarrppcccc////f/rrrerp for what should or should not be described.
20

---

A Notations and Preliminaries
Throughout this paper, we work on weighted graphs G (V, E, w) where w R encodes edge weights. Let a, b be two binary strings, we use a to denote the binary string obtained concatenating a and b. When edge weights are not concern, for a graph G = E) and S C V. we use Gss = (S, B(S) to denote the subgraph induced by S. For any h 2 1, we use KA to denote clique of size h. A graph H is a minor edge deletion or edge contraction, and we say graph G is Ka-minor-free if G does not have Kn as its minor. well-known that all planar graphs are K5 Ky-minor-free:
graph if a copy H can be obtained from via repeated
Lemma 12 (The Kuratowski's reduction theorem complete graph K5 and the complete bipartite graph K3,3 are not minors of G.
45
graph planar if and only if the
Here, we provide the necessary background on differential privacy to facilitate understanding of this paper. A key feature of differential privacy algorithms is that they preserve privacy under post- processing. That is to say. without any auxiliary information about the dataset, any analyst cannot compute function that makes the output less private.
Lemma 13 (Post processing (21). Let A: X + R be diffe-diffrylltialll private algorithm. Let f: be any function, then f o A also (e, diifffrrreet private.
Sometimes need to repeatedly use differentially private mechanisms the dataset, and obtain a series of outputs.
Lemma 14 (Basic composition 18). let be a dataset in X and A2....... .A be k algorithms
where A, (for i E [R:) preserves 6.) differential privacy, then the composed algorithum A(D) (A1(D), ... ;z,)) .A((D)) preserves (Eieja) Ei, Eiejs difffrrerll privacy.
Lemma 15 (Advanced composition (22). For parameters
and 5, 8' E [0, the composition o k (diff-rirrrrentialll private algorithms is a (E', kō + +') differentially private algorithm, where
v 2/2kloo (oallog(//)))) E ke(e- 11.
The Laplace mechanism is one of the most basic mechanisms preserve differential privacy for numeric queries, which calibrates a random noise from the Laplace distribution (or double exponential distribution) according to the é sensitivity of the function.
Lemma 16. (Laplace mechanism) Suppose f X R is query function with e sensitivity sensi (f) < Aj. Then the mechanism
M(D) S(D) + (Zi, Zx)
is (e, 0) -)differretti private, where Z1, Zy are i.i.d random variables drawn from Lap( (1EE).
Adding Gaussian noise based on the E sensitivity guarantees approximate differential privacy.
Lemma 17. (Gaussian mechanism) Suppose f X R is a query function with & sensitivity sens, (f) < A2. Then the mechanism
M(D) S(D) + (Z1, Zx)
diiferriielylltlally private, where Z,, Zz i..d random variables drawn from
N/ (, (Ag)* (2n)(221(11.25 2ln(1.25/8)
B Proof of Theorem 7
B.1 Privacy Analysis
Here, we analyze the privacy guarantee of our algorithm. We observe that constructing the binary tree T does not compromise privacy, as it only requires the topology, not the edge weights, as input. Consequently, the recursive procedure (Algorithm(3) and Algorithm involving the tree T are simply post-processing steps Algorithm[] T. Therefore, we focus our privacy analysis solely on Algorithm []] We use the following lemma to bound the sensitivity of the binary tree that traces the decomposition:
21

---

Lemma 18. Let T be the labeled tree constructed from G. For any vertex u, v with an edge {u, v) between them, e appears in most logi// (n/c) nodes in T.
Proof. Suppose is in the edge set of some internal node Gb. Recall that in the division of Gb. the edge will be removed if and only if u, v E Sb. Then e only exists in any Gy such that b' is the prefix of b. Since [6] S h, the lemma holds.
On the other hand, if is in the edge set of some leaf node Go. Then the recursive construction terminates on Gb. and e only exists in any Gy such that is the prefix of b, again the number of such nodes is at most h. This completes the proof of Lemma 18
We are now ready to prove the following theorem on the privacy guarantee, utilizing the advanced composition lemma (Lemma 15
Theorem 19. Algorithm 2 preserves (e, -ddfffrrenti privacy.
Proof. Suppose for a pair of neighhoring graphs G and G', they have a difference in the edge weight by of e {u, v). Let G2, be the subgraph of G that contains its edge set.
1. If G₁ is internal node of TT let ds, [do(x, x o y (z. v) S be the vector of distances between vertices in the separator of Gb. Since (ds(x,)) y) d' (x, y)] S for any distinct y, So. then ||ds, ll S p |S, Sol S p². Then, by the Gaussian mechanism, outputting dd(x, y) for all distinct x, y E S, preserves (E', deiff'-aiifereential privacy. Similarly, outputting d, y) for all (x. v) E Sy. x Sy where x, & Sy 0 S.s also preserves (e', 8') diifferrntial privacy, as [S, x Sy p².
2. If G1 leaf node of T. Since VB S c, then again be the Gaussian mechanism, outputting the all cil-pair-ssoteee distance ds(,,-) in G2 preserves (s', p diffferretl privacy.
Combining the above argument, Lemma 18 and the advanced composition, we have that Algorithm
preserves (c, 5)DP, as well as Algorithm This completes the proof of Theorem 19
B.2 Utility Analysis
Here, we present the utility guarantee of Algorithm 2 which privately computes the all-pair shortest distances for the input graph by repeatedly invokes Algorithm 3 for each pair.
Theorem 20. Fix any 0 < S. and any 0 < 7 < 1. Let G = (V. F, w) be (p. g') "rrecusvvvlyy separable graph for some p E N and that for any s, EV
2 S q S d <
Then with probability at least 7 we have
(hp (hp c) log (h/6)- v h2 + h hloggmaa ct) + log(1/7)
[s 1) ((s.1))50
where h loogi// (n/c). That is, for any constant and d', we have with high probability,
a(s.t) d(s,t) so p plogg n log
log n 8
To prove Theorem 20 First, we observe that, with probability 1, Algorithm terminates normally without any abnormal termination.
Fact 21. For any pair of vertices s.t E V, Algorithm Sasesimmmmdoo Idoes not output "FAIL".
Proof. The only case when Algorithm 3 outputs "FAIL" that the parameter k: 2 and both 8, l are not in the separator of the predecessor graph of Gb. However, it is not possible because when
Algorithm 3 called with k 2 at least one of the vertex in 8, / from the separator Sy where G Go or Go Gy
D
22

---

The following lemma is used for building the correctness of the recursion.
Lemma 22. Fix any 8, t,t E Vs. Without the lose of generality, we assume either both 8, Vhso or 8 E Vieu and E Vbo1 (otherwise we just switch and i, and the proof for both s, E Voo1 is symmetric). We have
do(s,t) min dico(s, deo1 min 2)) + do(x, + dbor dool (2. a.yES
Proof. We discuss by difference cases:
1. When at least one of s, is in Sy.. By the construction of Gbea such that
Gboa- (Voo USS, E(Vooo (.)))))))),,
we have do(s, t) 2 dsou(s, , t) and ds(s,t) 2 dooi t). Similarly, we have that min 2)) (x + dac (v. () > min ds() + da v) + do(u, 2 do(s,()
(3)
2.9E9,
z.yESs
by the triangle inequality. On the other hand, if both 8, f Sb, then have
ts dhoo (s ds 1) + dooi 2 min (so0 x) + do y) + droi
(4)
a.yES,
exactly one of s, E Sb, we note that any path (vj = s, ...... 2k = t) from 8 to t, must satisfy that U; E Sy for at least one i E [K] since E Sb or t St. Again by the symmetry, we assume t E Sb. Suppose 2 is the first vertices in Sb of any shortest path from s to t. Then,
do(s, () dseo(s, 2) + do(2, () + deei (1,1) 2 min dnoo(s, x) + da da v) + doo (v, l).
(5)
z,yES,
Combining Equation 3. Equation 4 and Equation (5) completes the proof in this case.
When both 8, & S₁. First, we assume that s and are on different sides such that Vhoo and i E Voo1- In this case deoo(s, t) = doo1 (s, t) = co. By the fact that S. is a separator, any path (U) s, U2, ... 2/ = t) from s to must also satisfy that 2/ E S, for at least one E [k]] Let &1 22 be the first and last vertices in one of the shortest paths from to such that ø1, 21,22 S, (we allow 21 = 22). Then it easy to verify that do(s, 21) = doon 21) and dz(22, 1) doo (z2, t). Thus, min dooa(s, 22 + dz y) + doo1 (y,, t) & (s, 21) + d2(21 22) + doo1 (22, t) ds(s,)) t). a.yES,
Again by the triangle inequality, suppose that both s and are in the same side VicO. Then the shortest path either crosses S₁ or not. the path crosses Sz. then the previous argument suffices to prove Lemma 22 If the path does not crosses Sp, then we have (s, t) = min (d (s, t), doo1 (s, f)), which completes the proof.
also have Equation holds, which proves Lemma 22 Now,
The following lemma utilizes the shortcut between the separators of two adjacent layers (built by step 4 of Algorithm 1 for pruning.
Lemma 23, Let Sy and Sy be two adjacent separators where b' for u E {0, 1}. Then for any So, {0, 1 and y E Sv.
ds(r, y) min (z, 2) + aboa (2,
zES,
Proof. Let P = (vj = x. u.. Uh = y) be any shortest path from x to and let w be the last vertex in P such that w S.. Such w exists since x E Ss. Then,
dx y) = do(z, w) + do = do w) + dooa (w, 2 min do(x,, 2) + doea (z. v).
=eS,
On the other hand,
dx < min do 2) + dz v) min do 2) + d (2. 2ESs
2E8,
due to the triangle inequality and the fact that do(2, v) S dzoa(2,y) y). This completes the proof of Lemma 23
D
23

---

Without the lose of generality, we assume the T is a complete binary tree of height h. (If one branch terminates early, we just let continue split with one of its branches be an empty graph, until the height is h.) We need to use the following observation to control the accumulation of the error:
Fact 24, During the execution of Algorithm 2 for any E {0, } such that [b] S h and any pair of vertices 8, I. Vb, Algorithm 3 with parameter Gb and (s, is invoked exactly once.
Proof. We prove it by induction on the size of b. We claim that if Aecursive-APSDC" Go, (s, k) where [6] S h 1 is called for any s, G6 and some k, then both Recursive- APSD(T, GboD. (s,t). k') k') and Recursive-APSD(T. Gho1. (s, t). k') will be called for some k'. This clearly true since Recursive-APSD(T Ghea. (s,t),
1) will invoked if both and t lies in Gana- Then, since Algorithm 2 invokes Algorithm B for any distinct s, E V, we conclude that Algorithm will be invoked at least once for every Gs, and all-pair vertices GB. On the other hand, since Al Algorithm 3 with Gj as parameter will only be invoked by b' such that b b' for E (0, }}. then it will only be invoked once.
Next, we analyze the error on each shortcut. We write 01 c (1228(125//8)/ and 02 lo2((..25//
Lemma 25. With probability at least 1 - "/ both the following holds:
1. For any 8, tt where h and that IsShortcut(s,t.b) True.
3 31.3mmmmxxpppc c)) + In (do(s,t) - do(s.t) s sor V h
1
27
2. For any 8,t, where [b] < h and that IsShortcut(s,t,b) = True,
(do(s,t) āo(s, ()s,t))= S 02 / h (1+3Immmax(ppcom c)) + In
1
27
Proof. We recall that for the Gaussian variable X ~ NOO of Pr||X| 2 < exp(-t²/2o" for any 2 For any 8, t, b with IsShortcut(s, t, b) = True and Go is a leaf node, the difference in do (s, t) and (s, t) is Gaussian noise with variance σ1. and thus
Pr(ds(s, t) ds, 2 2| < Y
we choose σ / log m (27)) for any m 2 1 and 0 <<> < Also, G, is not leaf node,
then according Algorithm 1 we have
Pr (d(s,)) ds(s, σ2v log m (27)
Y
The number of noises added in Algorithm is bounded by m 2 max(p2 cc2) Lemma 25 now follows using the union bound.
With all the aforementioned preparations, we are now ready to prove Theorem 20 regarding the utility guarantee of Algorithm by induction. We restate this theorem here.
Theorem 26 (Restatement of Theorem 20). Fix any 0 < S n and any 0 < < 1. Let
G (V, w) be a (p. q, ) -recursivvly separable graph for some p N and 1 S q S d Then with probability at least 1 ?,, we have that for any s, V.
(hp + c) log (h/8). / /h2 hllogmma + log( log(1/7)
[(s, t) d(s, ((s,t)] 50
where h = loggi// (n/c). That is, for any constant c and p'. we have with high probability.
p log log(n/8)
[d(s,t) - d(s, t)1 s
24

---

Proof. With the help of Fact 24 we prove this theorem by induction on the size of b. We first define
err (b) = {1 + (h [b))C2-
/ + (n and C2 02 /2(h + 3 In( (n( e}) + In(1/(27))) Then, is sufficient just show that for any G Vo.
for any b E 10 and b6| S h. Here, 5
in the binary tree T and any
[d(s, (s, 2err(b),
as letting b Ø completes the proof. For the base case, this is true for all [6] h because in this case Gb is the leaf node of and thus [dy(s, t) ds, S (i err(b). For all |6] and IsShortcut pennttuutssst,,,b, bs) = True, we also have that
[d,(s,t) t) do(s, t)) S C2 S Gi + 52 S err(b).
Suppose that for any 8, and b with < h. always have
1. If do(ss () is computed by the unique invocation of Algorithm 3 with parameter 0, then [boo (s, dhoa , t)] err(b o a) for {0, 1};
2. If do(s, t) is computed by the unique invocation of Algorithm 3 with parameter 0, then [bea (8, 1) Uhea (s, t) 2err(b a) for a E 10.
Now we look at the induction case.
Case(1) Suppose t) is computed by the unique invocation of Algorithm with parameter and that IsShortcut(s, E {0, 1). since the proof for the case where l are in the different sides is identical. In this case, by Algorithm 3
= False. only analysis the case when both 8, & E Vhoa for
ds(s f) = min(choa (8, t), min dsoa (s, + d2 (),
zeS.
On the other hand, from Lemma 22 have that
ds(s, = min dhoa (doa(ss))) (o,(s,)),, (), min droa (8, + do(x, u) + dhoa (u, 11) 2.yESh
where
min (s,a() + do(a, + dooa (1,a(1; min s,yES,
dood dooo (8, + min do(2, + docalvs)) (6) yES.
zESh
min doea (s, 2) + do (x,t). t).
zE8.
Here, the second equality comes from Lemma predecessor of b. Therefore,
23 together with the fact that E Sy where the
do t) = min (dsoa (s, (s, t), min dooa (s, + (2,
zeS,
By the induction assumption, we have both
Idboa (s, t) - dooa (s, 6) S err(b a) a) and (dooa(s,1)) droa (s, S err a).. Again by the fact that Sy and ir Sb, then IsShortcut(r, 1, 1, = True and therefore dd (x, t) do( t) 5 S2. Combining these together we have
[d,(s,t) t) d,(s,t)) t) err(boa) + Ca S C1 (h (16) + 1]){2 + err(b).
(s. t) is computed by the unique invocation of Algorithm with parameter k 0 and that IsShortcut(s,, t, b) False. Still, we assume s, t Vboa for {0.1), Since for any z E Sb, both DocurSive-APSDTT Gtear (8, K') Recursive-APSD(T. Gtea: (1, 2), k') will be invoked with &' > 0, then from case (2), we have that for any v, S. both dooa (s, x) and
Case(2) Suppose ds,
25

---

(v, is arr(boa) far from déoa (s, 2)) and dooa (v. (, t) respectively. Also, for any 2, E Sb, since IsShortcut(2, y, True, then
dd da(,,,)] S2
From the induction assumption, we also have
doea (s, doea (8, t) S 2err(boa))
Combining these facts together Lemma 22 we have that (do(s,t) do(s,t) t)1 = min
(ainfddoc (dsoa (s, t): min aboa (s, x)) + dz( (z. y) + aboa (y, 1)} z,yES,
min dooa (s, t), min dica (8, + dr( y) + doea (v, t) 2.yESb
- 2err(boo + C2 2(1 - 2(h (o]) - 2 + C2 S 2err(b).
This finishes the proof Theorem 26
C Proof of Theorem
To prove Theorem begin by presenting the decomposition procedure for K₁ fy-mmioo--fee graphs, which relies on the well-known lemma characterizing the separability of such graphs:
Lemma 27 (Alon al. (2)). Let h E N+ be an integer, and G be a Kn-mmnorrfree graph on vertices. Then, there exists a separator S of G of order most ((23/222222) such that no connected components in G(V)S, E(V) has more than fn vertices.
C.1 Privacy Analysis
give the following privacy guarantee Algorithm Theorem 28. Algorithm 4 preserves (s, -ddifferent privacy.
Based the proof of Theorem 19
The proof Theorem 28 is almost identical to that of Theorem 19
except that we re-calibrate the variance of Gaussian noise according to the size of the lc-covering set of separator S, instead of the size of the whole separator.
C.2 Utility Analysis
To demonstrate the improvement in finding k-covering sets within separators, we first present several useful facts and lemmas related to k-covering. The following lemmas state that each connected n-vertex graph has a k-covering set of size most (nnkk).
Lemma 29 (Meir and Moon (4)). Any connected undirected graph with vertices has a k-covering with size at most + [n/(k: + +1].
Lemma 30. Any graph with vertices composed of x connected components has k-covering with size at most x + [n/(k + 1)].
Proof. Let æ be the number of components with sizes ni, 12,, ... F2g. respectively. Each component has k-covering set of size 1 + [n./(k + 1)J) for i = 1,2,..., T. Summing these sizes yields the desired result.
We use the above lemmas to prove the following structural result, which establishes covering set for the separator of Ky-minor-free graphs.
Lemma 31 (Covering lemma for minor free graphs). Fix an h > Let G ([n), E) be a connected Ky Ki-minor-free graph. Then for any 1 < d < n, there exists subset of vertices S S [m] such that:
(I) S is separator of G and (2) there is d-covering of S with size at most O (h/hn//d).
Proof. We first claim that for any connected graph on n vertices, there exists a partition of [n] into O(/dd) disjoint subsets (V1, V2, V.) such that the diameter of each V,(1 < i < s) is at
26

---

most d. Indeed, by Lemma 29 G has d-covering C S [n] of size O(n/d). For each u E C, let Vi [n] be the vertices covered by with most d hops. Then, the partition (V,, V2.-.. V.) can be constructed from we" by removing duplicate elements. Next, by contracting each V; for v S 8 into super-node and merging all multi-edges between the super-nodes, we obtain smaller graph G with nodes, and clearly G K, -iimmooor-fii
is Ka.minor-free
Thus, by the separation theorem for K₁, ta--mioo--iiee free graphs (Lemma 27 G has a separator of size 0(18/2 V8) D(yhnn/d) Picking one vertex from each super-node in the separator of G forms d-covering set of the corresponding separator of the original graph, since each super-node has diameter at most d. This completes the proof of Lemma 31
We note that from Kuratowski's theorem [37] each planar graph is Kg-minor-Be Therefore, Lemma directly implies that each connected n-vertex planar graph has a separator with d-covering of size O( O(/n/d) for any S dds n.
Remark 32.
Lemma 33, For any two vertices a and b in graph X, and Za, E Z, where Z is k-covering of X, such that the hop distance belween (resp. b) and za (26) is at most k; have:
[d(a,b) b) d( Za, =6)1 S 2k W
where W is the maximum weight of edges in the graph
Proof. The lemma follows using the following set of inequalities: (d(a, b) d(za, 26)1 $ Id(zas 2b)
d(a, 2a) + d(b, 2b) d(za: =)) < 2k W.
The following lemmas are used to derive the error bound of the recursion based on two different types of separators.
Lemma 34. Fix any t E Vo, we have:
ds(s, t) minfchoo(ss t), dbo1 (s, (s,
or
do(s, 1)
min (dhon(8, 27) + do(xr,) drat (y, ()) + 2kW.
a,yESt
Without loss of generality, assume that either both s, f Voso. or s Vo-o and t E Voo1 (otherwise, we switch s and f, and the proof for s, E Vho1 symmetric)
Proof. The proof is based Lemma 33 and the proof of Lemma 22
When both s, & S.. The proof is the same as the proof of the proof of Lemma 22
When at least one of s, t in Sh. By the construction of G such that Ghoo (Vbsa St. E(Vooa (
we have
min (doon(8, x)) + do(x,, u) drat (v, ()) min dbea(s, do(x, v) + dia (v. 2kW z.yESt
z.yES,
Combining Equation 3.. Equation 4 and Equation (5) completes the proof in this case.
Lemma 35. Let Sy and So be two adjacent separators, where b = b' o for {0, 1). Then for any x E St, E (0,1) 1)", and y E Sy, we have:
de(x, v) S min ds(x, 2) + dooa v) S ds(x, 22W.
zESI
Recall that St is as defined in Step 4 of Algorithm
Proof. Let P = (vi = x, U2 Us = y) be any shortest path from xr to and let w be the last vertex in P such that w S. Such w exists since x E Sb. Then,
ds(x, 3) = d1(2, w) + do y) dx w) + doea (w, y) 2 min do (I, 2) + dooa y)
2ES,
min (x(x; ) droa (2. -2kW.
=ES
27

---

On the other hand,
(, v) S min do(2, 2) + (2. v) S min d2 2) + (2oa(2.)) (2. =ESğ
=ESg
due to the triangle inequality and the fact that do(z, v) S dooa (2,y). y). This completes the proof.
Next, we write of = c. v llloogl..25 (1225/88)/ and 02 - f(v, k) logg1125//0)//
Lemma 36. Let h, k, c, be before and
1
g(p, K G, h; / 3ln(max
2
With probability at least - 7, the following holds for Algorithm
1. For any s,t, where [6| = h and that IsShortcut(s,t..) = True,
(d(s, ds(stt) - V20i g(p, k. c, ht).
2. For any 8, where [b] and that IsShortcut 1,b) True,
[d((s t) do(s, - 220g g(p k, c, 7,).
Proof. The proof is analogous that of Lemma 25 in Appendix In particular, for any 8, 4, with IsShortcut(s,k. b) True and Gb is leaf node, the difference in do(s, t) and do(s, t) is Gaussian noise with variance of, and thus
Pr (d(s, - do 1) 2 I 2
m
we choose = /20 / log m/ (2?]) for any m 2 and 0 < y Also, if G, a leaf node, then according to Algorithm 4 we have
Pr (s, dss,t) 2 do 2lo m/ (2x) S m
The number of noises added in Algorithm 4 bounded by = 5. 2 max (fx,(f(p, c))) Then, Lemma 36 can be proved by the union bound.
To prove the utility guarantee for Algorithm 4 now state the following error bound which follows directly from Lemma 34 Lemma (35 and Lemma 36
Lemma 37. Fix any O < ê < 1, and n, E N. For any planar graph G = (In), E, w) that is (p, q, of recuusiivly separable for some constants
q S q < 1, there is an (c, d'lloorii for estimating all all-pair shortest distances in G such that with high probability,
d((st) ((s)))d(ssst)))) 5O ((e,k) log" log(n/6) kW
By applying Lemma 31 to bound f(p k)) in Lemma 37
we are now ready to present the proof of the
error bound stated in Theorem
Proof Of Theorem The privacy guarantee follows from Theorem 28 Now we give the proof for the utility guarantee.
(1) For grid graph, let p = vn, the decomposition described in Section 3 gives that f(p k)) On 1/4 /We) when Io = n 1/4 //We. Then, the result can be obtained by substituting this into Lemma 37 This choice of parameters is optimal due the arithmetic- geometric mean inequality.
(2) For -iimorrrrfrre graph, we choose k = O( (eW)as) balance the number of hops required to reach the covering set for each vertex in the separator and the size of the k-covering of the separator.
n4//
In this case, from Lemma 31 we have f(p, k) Ohh (1/5) Then, the desired result follows
by substituting this into Lemma 37
28

---

D The Complete Pseudocode of Algorithm
Algorithm 4: Constructing private shortcuts via sub-sampling in separator.
Input: Graph G = (V, E, w), private parameter e, 6, sampling parameter k.
Recursively construct a binary tree T as described in this section.
Set = / (n/c), E' = E/
/hh 4h (og(//"), and = 6/(h).
Let = fp.
4. for non-leaf node (Go, S.) E (T) do Find a k-covering set of S₁ and let be S
for x, E St such that a + do IsShortcut(r,
True.
Let do(2, v) = ds(2,)) v) + oZ) end if b o 2 then
Let 1 be the binary string that removes the last bit in b. Find a k-covering set of Sy and let it be St.
for (ar, v) E Sp S do
v. y E Sy n S. then
IsShortcut(z,y,
True. Let (z, v) = do(x, y) - o2)
end end
end
end
for leaf node (Gb.-) -) E V(T) do for x, y E Vo such that IsShortcut(I,) y, b) True.
do
Let dz = dz v) N (o, 2c log(1. 25/8")
(og(1.25/8))
(c))²
end end
Output:
The The binary tree T, and (u, v) for all u, V and b f0, 1)" such that IsShortcut(z, y. True.
E
Empirical Simulation
Here, we present a numerical example over varying graph scales to validate our theoretical results and conduct an empirical comparison between the utility of our algorithms and that of existing methods. In particular, for given graph size n E N4. we consider ( (vTr ni [nn) grid graph, where edge weights are either uniformly sampled from given range that can be defined as functions of the graph size. For comparison, we consider two previous algorithms that are specifically designed for grid graphs:
1. The algorithm by Sealfon 42
constructs an 133 -iized covering set for the entire grid graph, and then applies output perturbation to approximate the distances between every pair of points within the covering set.
2. Another approach is to first release all edge lengths using the Laplace mechanism. The length of shortest path is then estimated using at most O(n2/3) noisy edges, combined with the k-covering scheme from Sealfon 42] to eliminate the dependency on the edge
weights This idea was firstly introduced by Chen et al. [12].
To thoroughly examine the performance of these algorithms across different grid graphs, we designed two sets of empirical simulations shown in Figure I the low-weight scenario and the weight

---

scenario. In the low-weight scenario, each edge weight is uniformly sampled from [0. 1], whereas in the weegeweightt scenario, each edge weight sampled from [0, J. all experiments, we set & = 1 and 8 = n 10 Each test is repeated 50 times on MacBook M1 air, and the results are averaged.
n-10,
[seaioo:6) (COK-23)
Iseafindsi [CGX+
Approx. Error x100
Apprex. Errnr x100
Dur
1200
2000
2000
4003
3005
2002
2000
5020
4000
5000
Number of Vertices
Number Vertices
(a) W ~ Unif [O,
1]
(b) W Unif [0, n 1.1
Figure I: Numerical simulations across various graph scales.
30


Reviews:
[{"review_id": "OjF1TBDVDt", "reviewer": "Reviewer_PAPk", "summary": "This paper proposes algorithms to compute all-pair distances in a\nweighted graph under the constraints of differential privacy. Similar\nto previous work, the algorithm proposed here are based on the binary\ntree mechanism, a classical method to achieve good utility in the\ncontinual observation model of differential privacy. In particular,\nthe algorithms proposed in this paper expand the class of graphs,\ncalled recursively separable in the paper, to which this method is\napplicable.", "questions": "Can you elaborate on which other interesting graph classes can be captured by recursively separable graphs? \n\nDo you expect that one could design other optimized version of your framework for them?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n- the paper identifies a large class of graphs, recursively separable,\n  that can be analyzed using the binary tree mechanism\n\n- the paper presents algorithms for the compute all-pair distances\n  problem that provide good utility on a large class of graphs\n\nWeaknesses\n\n- the improvement in utility for planar graphs and grid graphs do not\n  follow directly from the main result but they require some further\n  steps,\n\n- the presentation of the algorithms can be improved with some more\n  explanations and without showing the concrete algorithms.\n\nThe main contribution of the paper is to extend the range of\napplicability of the binary tree mechanism for computing all-pair\ndistances in a weighted graph in a differentially private way.  In\nparticular, the paper interestingly connect it with a specific class\nof graph which the paper calls recursively separable. Intuitively,\nthese are graphs that can be separated recursively in a balanced way.\nThis connection is intuitive and works well in practice providing a\ngeneral framework for the computing all-pair distances problem.  To\nachieve good accuracy, the algorithm uses the topology of the graph to\nidentify private shortcuts that can be used in separators and across\ndiffernet separators. These topology-based shortcuts permits to reduce\nthe error. Using this framework the paper can provide useful\nalgorithms for a large class of graphs, and achieve utility similar to\nprevious works on some classes of graphs (e.g. bounded tree-width\ngraphs).\nHowever, in order to achieve improved utility with respect to previous\nworks on specific families of graphs, such as planar graphs and grid\ngraphs, the algorithmic framework needs some further optimization\n(e.g. finding shortcuts in k-covering sets). This shows that there is\nlimiting trade-off between generality and accuracy of the proposed\nframework. Nevertheless, the general framework and the optimizations\nare both meaningful and provide good utility.\nOne minor negative aspect of the paper is in its presentation of the\nalgorithms. The paper tries to give some intuition about the algorithms\nbefore presenting them formally. However, this intuition is limited\nand a reader is left alone in decoding the algorithms. The presentation\ncould be improved by moving some of the formal details to the appendix,\nleaving more space for the intuition behind them. \nAlso, as another minor negative point, some of the references are\nmissing important info. E.g. [1] has only title and year, [29] is just\nan unpublished reference, [45] the journal title seems part of the\npaper title.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable comments.\n\n> “The presentation of the algorithms can be improved with some more explanations and without showing the concrete algorithms….One minor negative aspect of the paper is in its presentation of the algorithms…”\n\nWe thank the reviewer for bringing this up; we will make the presentation of the algorithm more readable.\n\n> “Can you elaborate on which other interesting graph classes can be captured by recursively separable graphs?”\n\nApart from planar graphs and grid graphs, other interesting recursively separable graphs can include (i) series–parallel graphs (with $p = 2$) that can be used in flow networks or circuit design and (ii) interval graphs (with p = their clique number minus one) that can be used in scheduling or resource reallocation. More generally, recursively separable graphs can be considered as a superclass of all bounded tree-width graphs.\n\n> “Do you expect that one could design other optimized version of your framework for them?”\n\nYes. Since recursive separability is a relatively weak requirement, and we only look at minor-free graphs and grid graphs (with a more specified version of the algorithm for the latter), we would expect there are other optimized versions for other specific types of graphs. Presumably, one could take advantage of the extra structure, similar to our improved bounds for planar and minor-free graphs."}, {"review_id": "yE2cZ3HAzL", "reviewer": "Reviewer_Ta62", "summary": "This paper presents an algorithm for solving the differentially private all-pairs shortest distances (APSD) problem on a special class of graphs called recursively separable graphs. The authors further develop an improved algorithm for a subset of these graphs, namely $K_h$​-minor-free graphs, and demonstrate enhanced approximation guarantees on specific graph classes. In particular, they achieve approximation error bounds of ${\\tilde O}((nW)^{1/3}/\\epsilon^{2/3})$ on planar graphs and ${\\tilde O}(n^{1/4}W^{1/2}/\\epsilon^{1/2})$on grid graphs.\n\nA key technical innovation lies in a new recursive decomposition approach: the graph is partitioned into subgraphs using a divide-and-conquer strategy. For $K_h$​-minor-free graphs, the authors further construct a k-covering structure, which plays a crucial role in optimizing the algorithmic performance.", "questions": "The experimental evaluation is limited to randomly generated grid graphs. Could the authors test the algorithm on more diverse datasets or real-world graph structures to better demonstrate its practical performance?", "limitations": "This is a theoretical paper, and I do not see any negative societal impacts.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths\n\n1.The differentially private APSD problem is a classical and well-studied problem in the context of graph algorithms and privacy. Since its introduction by Sealfon[1], it has seen significant attention, and further progress in this area is of broad interest.\n\n2.The proposed use of recursive structures over graphs introduces a novel and elegant algorithmic technique, showcasing theoretical creativity.\n\n3.The algorithm achieves significantly improved approximation error bounds on widely studied graph families such as planar and grid graphs.\n\nWeaknesses\n\n1.The proposed method applies only to graphs with specific structural properties, such as recursively separable graphs and $K_h$-minor-free graphs (including planar and grid graphs). Its applicability to general graphs remains limited.\n\n[1] Adam Sealfon. Shortest paths and distances with differential privacy. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 29–41, 2016.", "was_revised": true, "final_justification": "The authors' detailed response answered my questions. Since my rating is positive, I will keep my rating.", "rebuttal": "We thank the reviewer for their valuable comments. \n\n> “Could the authors test the algorithm on more diverse datasets or real-world graph structures to better demonstrate its practical performance?”\n\nWe initially focus only on grid graphs mainly because the implementation of this case is much easier, and the goal is to verify whether the theoretical dependency on n is correct. \n\nTo evaluate the performance of our algorithms on real-world graph structures, we consider metro line networks—one of the most natural application scenarios for private all-pairs shortest distance (APSD) computation. We note that there might be cycles in the metro network, so the binary tree mechanism is not directly applied.\nSpecifically, we select metro networks from three Chinese cities: Jinan, Suzhou, and Nanjing. Each network is modeled as a planar graph based on the most up-to-date publicly available information, and we refer to these graphs as G1, G2 and G3 respectively. The datasets vary significantly in scale:\n\nJinan Metro Network (G1) has 46 stations (including 2 interchange stations), 45 edges;\n\nSuzhou Metro Network (G2) has 134 stations (including 9 interchange stations), 138 edges;\n\nNanjing Metro Network (G3) has 218 stations (including 20 interchange stations), 229 edges.\n\n(We must note that our dataset was manually compiled based on publicly available information and maps, so there may be minor inaccuracies.)\n\nWe compare our proposed algorithm with two baselines: (1) the post-processing scheme from Sealfon [2016], and (2) the k-covering scheme in [Chen et al. 2023]. In all experiments, we set the privacy budget epsilon = 1 and delta = 0.01. Each graph is modeled based on the corresponding metro network topology, and as described in the main paper, edge weights are assigned independently at random from the uniform distribution over $[0, n^{0.1}]$, where n is the number of nodes in the graph.\nWe define the error as the maximum difference in all-pair shortest distances, that is, \n\n$\\text{error} = max_{u,v} | d_{u,v} - \\hat{d}_{u,v} |$.\n\n\nEach result is the average over 10 independent trials. The results are summarized in the table below:\n\n\n| Algo    | Error in G1 (Jinan) | Error in G2 (Suzhou) | Error in G3 (Nanjing) |\n| -------- | ------- | ------- | ------- |\n| Sealfon 16  | 10.568 | 16.988 | 29.247 |\n| Chen et al. 23 | 12.860 | 15.793 | 22.772 |\n| Ours    | 14.118 | 16.416 | 19.972 |\n\nTo better demonstrate the performance of our algorithm, we consider larger datasets. In particular, we consider the dataset of geographic faces from the dataset TIGER-Hawaii, provided by the U.S. Census Bureau. It corresponds to the state of Hawaii, with a total of 33,558 vertices, 80,882 edges and 17 connected components. This dataset considers five aggregation levels: states, counties, census tracts, census block groups and census blocks.\n\nTo test the algorithm's performance at different scales while controlling the data size, we adopt the following strategy to select a random subgraph of size k that does not contain too many connected components: (1) uniformly and randomly select a vertex, (2) grow a subgraph using BFS strategy, truncate when the size of subgraph is already > k and (3) randomly select another vertex if the number of vertices found by the BFS is < k. Using the same settings as above, we present the following results under different sizes of the subgraph:\n\n| Algo    | k = 300 | k = 500 | k = 700 |\n| -------- | ------- | ------- | ------- |\n| Sealfon 16  | 26.040 |  32.245 | 40.441 |\n| Chen et al. 23 | 21.964 | 27.784 | 31.136 |\n| Ours    | 17.557 | 20.366 | 22.354 |"}, {"review_id": "pJcNo7Vl7j", "reviewer": "Reviewer_Pxjc", "summary": "The problem of releasing All-Pair Shortest Distances (APSD) on a (general) weighted graph with differential privacy has been well-studied. However, when the given graph has special properties, the error bound can be further improved. In this paper, the authors propose efficient algorithms with significantly improved bounds on graphs that are recursively separable (**Definition 1**). Typical examples of such graphs are trees or planar graphs. The property of recursive separability allows one to use the divide-and-conquer method (or a generalization of the binary tree mechanism) to recursively compute the shortest path, thus improving the bound for APSD on these graphs.", "questions": "No.", "limitations": "Thanks for the submission. In its current form, I think the paper is well-written, and I cannot find limitations.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths\n\n1. The proposed solutions seem reasonable and correct.\n2. The paper is well-written, including intuitive explanations and sufficient theoretical analysis.\n\n# Weaknesses\n\n1. It would be better to open-source the implementations that can reproduce the results shown in Appendix E.", "was_revised": true, "final_justification": "Thanks again for the rebuttal. I wish to see the open-source code of this paper in the final version.", "rebuttal": "We thank the reviewer for their valuable comments. We will include the link to the code in later non-anonymous versions of this paper."}, {"review_id": "5K56BvtHUM", "reviewer": "Reviewer_HpTQ", "summary": "This paper studies a fundamental differential privacy problem on graph, namely estimating all pairs shortest distances privately. The main contribution is to design a generic adaptation of the binary tree mechanism to a class of graphs that could be recursively separated, e.g., the grid graph. In particular, they show that if the graph is $(p, q, q')$ recursively separable, then their algorithm achieves an additive error of $p\\log^3(n/\\delta)/\\epsilon$ for $(\\epsilon, \\delta)$-DP. For planar and general $K_h$ minor free graphs, their algorithm achieves an error of $\\tilde O_\\delta(h\\cdot (\\frac{(nW)^{1/3}}{\\epsilon^{2/3}}))$ and the bound is further improved for grid graphs to $\\tilde O_\\delta(\\frac{n^{1/4}W^{1/2}}{\\epsilon^{1/2}})$.", "questions": "1. What do you think is the \"correct\" answer to DP APSP? At least from the results of this paper, it seems for a large class of graphs, the correct answer might be closer to the previous proved lower bound?", "limitations": "Authors didn't discuss limitations. One source of possible improvements is suggested in the weakness section.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The results are quite important, as it improves upon the additive error for a large class of graphs and it introduces the binary tree mechanism into the picture of DP APSP. It is known that binary tree mechanism works for path graph due to the range counting \"1D\" nature of APSP on a path. This paper demonstrates that for graphs that have good separability structures, you can essentially reduce to the case of a path (to some extent). While natural, this gives us better understanding for the class of graphs that could leverage the powerful binary tree mechanism.\n\n2. Conceptually, the idea is quite neat and simple, and the paper is well-written. I find it easy to read and parse.\n\nWeaknesses:\n\n1. As illustrated in strengths, the main contribution of this paper is figuring out the correct class of algorithm that resembles the \"path\" behavior in order to apply binary tree mechanism. As such, once the property of recursively separable is spelled out, both the algorithms are the analysis become relatively straightforward. It does not bring much more insights beyond that. I think it would be interesting to abstract the general binary tree mechanism beyond DP APSP.\n\n2. The paper is quite technically dense, authors could consider adding more discussions and a conclusion section in the appendix.", "was_revised": true, "final_justification": "I'm happy with authors' response to my questions, in particular whether it's possible to generalize the technique to other problems. As my initial rating is positive, I've decided to keep it as is.", "rebuttal": "We thank the reviewer for their valuable comments. We would love to add more discussions and high-level intuitions in the paper to make it less dense.\n\n> “I think it would be interesting to abstract the general binary tree mechanism beyond DP APSP.”\n\nThis is indeed a very interesting point, and we would love to discuss more: \nThe construction of our generalized binary tree mechanism relies on carefully designing the shortcuts inside and between separators, while adding shortcuts to reduce the number of hops in the shortest path between any two vertices is a natural strategy for APSD-type problems (with or without privacy constraints). Therefore, the construction of our framework is not problem-independent, and thus it is not very direct to abstract this beyond APSD. Moreover, our recursive strategies – such as leveraging triangle inequalities to control error rather than explicitly identifying the exact shortest path – are specifically tailored to address the challenges posed by general separable graphs in which the paths between two vertices are not unique, and the real shortest path may traverse separators in a nontrivial, back-and-forth manner. These properties also distinguish general recursively separable graphs from simpler structures like paths, in which the path between any pair of points is unique. Indeed, the Bentley&Saxe data structure as in the standard binary tree mechanism implicitly, but also crucially take advantage of the uniqueness of shortest paths, so that shortcuts can be easily constructed without further privacy loss.\n\n\n>”What do you think is the \"correct\" answer to DP APSP?”\n\nWe share the same curiosity about this question, and the reviewer’s bringing it up has encouraged us to continue exploring how to close the gap in private APSD. Admittedly, we do not think we have a concrete answer. However, in light of our present results, we believe the “correct” dependency on $n$ might be different depending on whether we assume a bounded maximum edge weight."}]

Author rebuttal:

Meta-review: The paper introduces a new method for privately computing the all pair shortest distances in a graph. Previously it was known how to do this for general graphs with error roughly sqrt(n)/epsilon, where n is the number of vertices and epsilon is the privacy parameter. The goal of the paper is to go beyond this bound for special families of graphs. It achieves this goal for "recursively separable" graphs, which include planar graphs and grid graphs as examples and only when the maximum weight is not large. 

The strength of the result is that it is an approach to a broad family of graphs. 

The downside is that the results require specific constructions for different subcases such as planar graphs and grid graphs and not a common algorithm, and it also imposes restrictions on the weight. It is also unclear if the bound given here are tight even for special cases.

All reviewers are positive about the contribution to a problem that attracted a lot of prior works in a broad class of graphs.
Decision: Accept (poster)