De-coupled NeuroGF for Shortest Path Distance Approximations on Large Terrain Graphs

Thank you for your review! We are glad that you appreciate our proposed advancement in the problem of neural data structures for SP queries on terrains.

Regarding your question about $xy$-monotone surfaces, a continuous surface in $\mathbb{R}^3$ is called $xy$-monotone if every line parallel to the $z$-axis only intersects the surface at a single point.

We thank you for your time and constructive feedback. We are glad the reviewer appreciates our de-coupled and mixed coarse-to-refined training strategy for efficiently processing large terrain graphs at scales previously which were not able to be considered. As you point out, our de-coupled training strategy is particularly useful for dynamically updating neural data structures efficiently.

Hyperparameter tuning: Thank you for these comments. We should have included such information in the paper. In fact, we do deploy hyperparameter tuning in the paper. For our experiments, we perform all hyperparameter tuning on smaller-scale synthetic terrains, selecting the best-performing hyperparameters based on these trials. These optimized hyperparameters are then applied across all subsequent experiments on large-scale terrain graphs. We will include detailed hyperparameter tuning in the revision. An example of how the model accuracy changes with different embedding dimensions for the latent space is shown in Figure 1 (https://shorturl.at/SXyB2). In general, we observe that model performance stabilizes after a while.

Comparisons with other work: The primary goal of our paper is to develop a lightweight neural data structure to answer shortest-path (SP) distance queries for extremely large terrain graphs. We see three relevant areas of work for comparison:

(1) Metric learning: Siamese networks are the SoTA architecture in the field of metric learning and we already compare with state-of-the-art Siamese network, denoted by $\mathsf{X}$+$L_p$ in our paper. Furthermore, we explored the design space of Siamese learning approaches by using different SoTA GNN architectures and transformers used as the network backbone. (See C.3 in the Supplement.)

(2) Neural models specific for geodesic distance queries: GeGNN and NeuroGF are the current SoTA architectures for processing geodesic distance queries (i.e. shortest path distance) on graphs induced by meshes. In our paper, we provide direct comparisons to both GeGNN and NeuroGF.

(3) General graph learning: While SPD approximation is a commonly considered problem in the graph learning community, our goals are different as we seek a lightweight and efficient neural data structure. The setting here is that once we preprocess the data (i.e. trained the model), the users might have many future SP queries, each of which consists of two points, and the model should return the SP distance between them quickly. (This is a fundamental primitive in GIS applications.) Current GNNs are not directly suitable as a neural data structure for answering many future SP queries. For example, there are several existing recurrent GNN methods which imitates algorithmic control flows in order to generalize all graph instances (Tang, et al. 2020, Luca, et al. 2024). However, such iterative approaches are computationally expensive during the inference time for each SP distance query, as it requires many iterations of the models to essentially explore the entire graph. In contrast, our latent embedding can capture hidden patterns in the SP distance function, while MLP can effectively retrieve the final distance. As an example, we trained a lightweight GNN model trained to learn two steps of single-source shortest paths. The inference time for approximating the SPD between a pair of nodes with 100 iterations of our lightweight model is 307 seconds on Norway as such a model is essentially forced to compute all shortest paths on the graph from a single source even though we are only interested the SP distance between a single pair. In contrast, our M-CTR method, after computing all initial embeddings, achieves an inference time of merely $7 \times 10^{-6}$ seconds. We would be happy to add such a comparison to the revised paper.

In short, we have compared our method with all relevant neural approaches; but we would be happy to add additional comparisons with iterative GNNs. Note that all neural approaches are orders of magnitude more efficient than SoTA classical algorithmic approaches (as we described in paper).

We thank the reviewer for your time and constructive feedback. We are happy that the reviewer appreciated our innovative training strategy: with our de-coupled and mixed coarse-to-refined training strategy, we introduce a lightweight neural data structures that can efficiently answer many shortest path distance (SPD) queries over massive terrain graphs orders of magnitude faster than classic algorithmic approaches. Note that this is a fundamental problem in GIS (see also our discussion in “Scope of work”). Below we provide responses for main questions/comments.

High-resolution terrain datasets: In our experiments, we use high-resolution terrain graphs because the shortest paths on these graphs provide more accurate approximations of the true geodesic on the terrain surface (and as a result, these are the most common data available). However, our technique is applicable to any terrain graph, including lower resolution ones where the geodesic approximation is coarser.

We think that the resolution of the terrain graph does not directly affect the quality of the approximation; rather, the ``complexity" of the metric induced over the terrain graph would. As an example, we measure complexity by the doubling dimension of the terrain graph. This is theoretically motivated by Theorem 1.2 of (Naor et al. 2012), which states that every metric space can be approximately embedded into $R^N$ with distortion dependent on the doubling dimension of the original metric space. We conduct new experiments on synthetic terrains (see Table 1). We observe that: (1) as the doubling dimension increases, the relative error incurred by the Siamese embedding approach (i.e, GAT+$L_1$) also increases. (2) Our de-coupled training approach can help to adjust the errors from the Siamese approach (via the distance-computation module) and further improve the SPD approximation. Also the relative error by our de-coupled approach increases at a slower rate as doubling dimension increases, compared to that of the Siamese approach (GAT+L1). Theoretically, it could be interesting to provide sample complexity bounds w.r.t. doubling dimension but we leave this to future work.

Comparisons to other methods: Please see our response to Reviewer 2aDC.

Experiments with more diverse and large-scale datasets: Thank you for the suggestion. First, we note that we focus on Norway and Los Angeles in our experiments as are they are both complex and large-scale. Both Norway (4M nodes) and Los Angeles (16M nodes) are far larger than any terrain graphs considered in previous work. They both represent highly complex terrains: The Norway terrain graph is taken from a highly mountainous region and the Los Angeles dataset spans all of LA county and has both flat and mountainous regions with elevations varying between 3000m and 0m.

We will include more large-scale datasets in the revision. We have already obtained results for two additional datasets: Holland and Philadelphia, both of which contain 1M nodes. Results are shown in Table 2. For both datasets, our new M-CTR approach outperforms just simply using the Siamese network trained on a coarse 2500 node version of the terrain (Coarse GAT+L1). We will update our paper with these results, as well as additional results from larger datasets (e.g. a 25M node Norway dataset which covers a different region of Norway than our current Norway dataset).

Scope of the work: First, we would like to emphasize that the development of succinct data structures to support efficient SP distance queries on massive terrain graphs is important in its own right: it is a fundamental problem in geospatial data analysis and GIS database systems with a wide range of applications, as SPD queries is a key primitive operation from terrain-navigation, to point of interest search problems, to flood simulations. Thus a scalable, practical data structure for SP-distance queries on terrains will have a huge impact. This explains the huge literature on this problem both in GIS and computational geometry. We also show that our two-stage mixed training strategy leads to an easy-to-update neural data structure when there are dynamic changes in the terrain (e.g. in time-sensitive natural disaster relief scenarios). Furthermore, while not explored in this paper, our de-coupled training framework could also be applicable to other general metric learning setups, when the input metric space is massive, and a large number of future SP queries are expected.