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.

“I think it would be interesting to abstract the general binary tree mechanism beyond DP APSP.”

This is indeed a very interesting point, and we would love to discuss more: The 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.

”What do you think is the "correct" answer to DP APSP?”

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

We thank the reviewer for their valuable comments. We will include the link to the code in later non-anonymous versions of this paper.

We thank the reviewer for their valuable comments.

“Could the authors test the algorithm on more diverse datasets or real-world graph structures to better demonstrate its practical performance?”

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

To 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. Specifically, 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:

Jinan Metro Network (G1) has 46 stations (including 2 interchange stations), 45 edges;

Suzhou Metro Network (G2) has 134 stations (including 9 interchange stations), 138 edges;

Nanjing Metro Network (G3) has 218 stations (including 20 interchange stations), 229 edges.

(We must note that our dataset was manually compiled based on publicly available information and maps, so there may be minor inaccuracies.)

We 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. We define the error as the maximum difference in all-pair shortest distances, that is,

$\text{error} = max_{u,v} | d_{u,v} - \hat{d}_{u,v} |$.

Each result is the average over 10 independent trials. The results are summarized in the table below:

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

To 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:

We thank the reviewer for their valuable comments.

“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…”

We thank the reviewer for bringing this up; we will make the presentation of the algorithm more readable.

“Can you elaborate on which other interesting graph classes can be captured by recursively separable graphs?”

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

“Do you expect that one could design other optimized version of your framework for them?”

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