De-coupled NeuroGF for Shortest Path Distance Approximations on Large Terrain Graphs
Authors: Samantha Chen
Pankaj K Agarwal
Yusu Wang
Venue: ICML 2025 poster (2025)
Keywords: geospatial analysis
graph neural networks
terrains
shortest paths
Primary area: applications
TL;DR: We investigate neural data structures for approximating shortest paths on terrain DEMs

Abstract: The ability to acquire high-resolution, large-scale geospatial data at an unprecedented using LiDAR and other related technologies has intensified the need for scalable algorithms for terrain analysis, including *shortest-path-distance* (SPD) queries on large-scale terrain digital elevation models (DEMs). 
In this paper, we present a *neural data structure* for efficiently answering SPD queries approximately on a large terrain DEM, which is based on the recently proposed neural geodesic field (NeuroGF) framework (Zhang et al., 2023)---the state-of-the-art neural data structure for estimating geodesic distance.
In particular, we  propose a decoupled-NeuroGF data structure  combined with an efficient two-stage mixed-training strategy, which significantly reduces computational bottlenecks and enables efficient training on terrain DEMs at a scale not feasible before. We demonstrate the efficacy 
of our approach by performing detailed experiments on both synthetic and real data sets.
For instance, we can train a small model with around 70000 parameters on a terrain DEM with 16 million nodes in a matter of hours that can answer SPD queries with 1\% relative error in at most 10ms per query.

De-coupled NeuroGF for Shortest Path Distance Approximations on Large Terrain Graphs
Samantha Chen
Pankaj K. Agarwal? Yusu Wang?
Abstract
out availability of simple, scalable algorithms for various terrain-analysse tasks. This has led to extensive work on developing efficient algorithms for many terrain-analysis tasks such as visibility computation, hydrology analysis, mobility analysis, and answering proximity queries. In this paper, we focus on answering shortest-path distance (SPD) queries (also referred as geodesic distance queries) on terrains. Throughout this paper we assume that terrain is represented as zry-monotone triangulated surface E in R3 Many applications call for answering many SPD queries on the same terrain, so it is desirable to pre-process the input terrain into a data structure so that SPD queries can an- swered quickly. The key metrics associated with such an approach are the trade-off between the size and the query time of the data structure well as the preprocessing time.
The ability to acquire high-resolution, large-scale geospatial data an unprecedented using LiDAR and other related technologies has intensified the need for scalable algorithms for terrain analysis, including thortest-path-ddsttnee (SPD) queries on large-scale terrain digital elevation models (DEMs). In this paper, we present a neural data structure for efficiently answering SPD queries approximately on large terrain DEM, which based on the recently proposed neural geodesic field (NeuroGF) framework (Zhang et al., 2023) the state-of-te of-the-art neural data structure for esti- mating geodesic distance. In particular, we pro- pose a Eecouupled-Neurodee data structure com- bined with an efficient two-stage mixxddtraiiing strategy, which significantly reduces computa- tional bottlenecks and enables efficient training terrain DEMs scale not feasible before. We demonstrate the efficacy of our approach by per- forming detailed experiments on both synthetic and real data sets. For instance, we can train a small model with around 70000 parameters on a terrain DEM with million nodes matter of hours that can answer SPD queries with 1% relative error in at most 10ms per query.
Despite a rich body of literature on this topic, the SPD query problem on terrains is far from being solved both from theoretical and practical perspectives. For instance, state-of-the-a algorithmic approach in a recent paper by (Wei et al., 2022) takes more than 200 hours build data structure of size around 1000MB for terrain with 180K nodes to support approximate SPD queries, between pairs of vertices on the terrain, with relative error at most 0.1 in 10ms per query. Furthermore, it is hard to scale the current approaches to terrain DEMs with millions of nodes.
In view of the remarkable success of deep learning methods across various domains such as vision, graphics, robotics and GIS, it is natural ask whether one can develop an effective neural data structure answer SPD-queries effi- ciently on large-scale terrain DEMs. Precisely, given a ter- rain DEM Σ, we ask whether we can train a neural network that can accurately and efficiently estimate the geodesic distance between any two points on Σ. this paper, we explore the design space of neural data structures for an- swering SPD-queries and propose method that is scalable to large terrain DEMs.
1. Introduction
With rapid advances in LiDAR and related technologies, high-resolution, large-scale digital elevation models of ter- rains are being generated and made publicly available at an unprecedented rate. The tremendous opportunities pro- vided by these data sets will, however, not be realized with-
'Equal contribution 'University of California San Diego, Department of Computer Science and Engineering *Duke Univer- sity, Department of Computer Science 'University of California San Diego, Halıcoogu Data Science Institute, Correspondence to: Samantha Chen <sac003 udsd.
Related work. Motivated by applications in robotics and GIS, algorithms for computing shortest paths on polyhedral surfaces in R have been studied extensively over the last four decades. The best-known algorithm for computing shortest path between two given points on terrain takes On²²) time (Xin & Wang, 2009; Chen & Han, 1990;
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

De-coupled NeuroGF for Terrains
(a) Siamese ambedding module
(b) Final distance approximation
(bv) E R
P
(1²)) e RD
Figure 1. High level pipeline of NeuroGF (Zhang al., 2023). Part (a): Siamese embedding module. Part (b): the distance approximation module. We propose to decouple the training of these two stages by first training the Siamese embedding module, freezing the trained Siamese network. and optimizing only the final distance approximation module.
Mitchell al., 1987; 2000), where is the number of ver- tices on Σ. Although the running time can be improved to On log n) time (Schreiber & Sharir, 2008) for convex surfaces, no subquadratic algorithm is known for nonconvex surfaces. This has led to faster approximation algorithms for this problem: a subquadratic (1 + e) approxximatoo al- gorithm was proposed in (Varadarajan & Agarwal, 2000). Subsequently, more approximation algorithms were devel- oped in(Aleksandrov et al., 1998; Lanthier al., 2001), whose run time is near linear under some assumptions the geometry of the terrain, e.g., if the minimum angle of any face is bounded from below by a constant. There also has been much work in computational geometry, database, and GIS communities on developing practical algorithms for computing shortest paths on terrains; see (Kaul al., 2013; 2015; Tran al., 2020; Wei et al., 2022: 2024; Hazel et al., 2008) and references therein. Most of these approaches choose a large set of points on the terrain and construct a graph G on the points so that the shortest-path distance on G approximates the geodesic distance on the original terrain.
neural geodesic field (NeuroGF), consisting of an initial Siamese embedding module & mapping input points to latent space, combined with final multilayer perceptron (MLP) p as the distance approximation module. See Figure 1. (Pang et al., 2023) suggests a similar network architecture for approximating SPD on mesh surfaces but incorporates a hierarchical pooling module within their suggested architec- ture. Both (Zhang al., 2023) and (Pang et al., 2023) state-of-the-aa (SOTA) neural approaches to approximating SP- SP-distances for smooth meshed surfaces. However, we will see later, these models (especially (Pang et al., 2023)) do not yet scale to the size encountered in terrain graphs.
Our model. Terrains. Let C TR2 be a triangulation of a bounded polygonal region. With slight abuse of notation, we also denote this region by Ω. Let V be the set of vertices of Ω; set We assume that the restriction of h to each triangle of Ω is a linear map. Given Ω and h, the graph of h, called a (polygonal) terrain and denoted by Σ = (22, h). is an xy my-monotone triangulated surface whose triangulation induced by Ω. For any point (x. y) E IR.,, we define its lift the point v (a,, y, h(2, v)) E R
|V Let h Ω - R be height function.
In machine learning, SPD queries are related deep met- ric learning, where given collection of pairwise distance between points sampled from certain space X, one aims to train a neural network that can accurately estimate the metric dx= X x X + I on X (Ghojogh et al., 2022). Metric learning is often done via a Siamese network where given x, E X, each point is transformed by an identical neural network A to produce high-dimensional embeddings and the distance [x:( ~y())) is then returned estimation for dx (x., y)-
Paths and terrain graphs. Our focus is on processing high- resolution terrain data sets, in which triangles in Ω will be tiny. Therefore we ignore the interiors of triangles and con- sider the terrain as a weighted graph G₁, = (V, E), where V and E are the vertices and edges of 22 and the weight of an edge (u, 2) is || ell (the Euclidean distance between the lifts of and v). We refer to G₁, as terrain graph. For two vertices û, é, we assume that a path on Σ between â and i lies along the edges of Gh, and thus the shortest path
Two very recent concurrent works (Zhang et al., 2023) and (Pang et al., 2023) have initiated the use of such metric learning approaches to approximate geodesic distances on meshed surfaces for graphics and vision applications. In par- ticular, (Zhang et al., 2023) introduces general framework,
For example, most of the terrain data is available as grid DEM. i.e.. height function over points on regular grid, which case each grid point is connected its eight neighbors; see e.g. (Arge et al., 2001).
2

---

De-coupled NeuroGF for Terrains
between à and ê on Σ is represented as the shortest path between them in the graph G₁.- This simplified assumption is justified because of high-resolution data and because we are interested in computing the geodesic distance approxi- mately. Furthermore, most approximation algorithms also construct a discrete graph and compute shortest paths in the resulting graph. This assumption enables us to simplify the problem at a small loss in accuracy and to use graph neural network architectures (Scarselli et al., 2009).
and continuous changes driven by natural processes. Re-training the entire NeuroGF model whenever the height function is modified is expensive. With our de- coupled training approach, the previously trained ø can be re-used to map nodes to an initial representation and we re-train only the final distance-computation module p using the perturbed graph with the updated height function. Via our de-coupled training strategy, we can efficiently update our neural DS whenever the height function changes and maintain high quality SPD approximations.
Our contributions. This paper aims to develop an effi- cient and compact neural data structure for the estimation of shortest path distance (SPD) for massive terrain graphs at an unprecedented scale. While (Pang et al., 2023) shows promising results for SPD estimation on well-behaved tri- angular meshes of smooth 3D geometric shapes (e.g. from ShapeNet), terrain graphs pose unique challenge they are significantly larger in size. We instead explore the use of the conceptually simpler NeuroGF framework proposed in (Zhang et al., 2023) to develop an effective model for massive terrain graphs.
In Section 4, demonstrate the utility of our decoupled- NeuroGF and its mixed training strategy for large terrain graphs at an unprecedented scale. Specifically, we evaluate real-world terrains containing up to 16 million nodes, a sig- nificant increase compared to prior algorithmic approaches. We can train a small model with around 70000 parame- ters on a terrain DEM with 16 million nodes in a matter of hours in contrast to the previous best-known (non-neural) algorithms which require several days of pre-processing time for terrains with 180,000 nodes. Our mixed training strategy also leads to orders of magnitude speedup in train- ing, while still outperforming previous SOTA neural based approaches. Our experiments also show that our decoupled- NeuroGF supports efficient updates (retraining of only the distance-compun computation MLP module) as the input terrain graph undergoes small changes.
Our main contributions are as follows: We propose a simple decoupled-Neurode NeurooGG framework for answering shortest path distance queries approximately on massive terrain graphs, which has two stage training process. In the first stage, only the Siamese embedding module ø is trained to ap- proximate the SP-distance via the Ln distance in the latent space, and its weights are subsequently frozen. In the sec- ond stage, we finetune the final MLP (which refines the distance approximation) using the fixed embeddings output by the Siamese network. We call this MLP part the distance- computation module. This decoupling of the two stages of NeuroGF has several ad advantages:
2. Preliminaries
Given a height function h : Ω + R. our input is a terrain graph Go, = (V, F; Xx, w) where X,, = {(ar, y. h(, y)) e = (z, E V) (the set of lifts of nodes in V w.r.t. the height function h V IR) and w E - IK assigns edge weights. We often omit the subscript h from the notations when its choice is clear. In practice, terrain data is often given as a grid of evenly spaced measurements within a constrained region. In this case, we simply set V to be the set of grid vertices, and for each node (grid point) v, we connect it to each of its 8 neighbors around it. Our goal is to estimate the shortest path distance do, (u, v) w.r.t. the terrain graph Gt.
Better performance. As we show in Section 4, it achieves superior performance in practice, with up to a 10% reduction in relative error as compared to the end-to-end NeuroGF pipeline.
Efficient mixed-training strategies. Training the Siamese embedding module & takes significantly longer than training the distance-computation MLP p. As the size of terrain grows, training & becomes very expensive. Our decoupled-NeuroGF uses a mixed training-strategy: We first train the embedding mod- ule é using only coarsened terrain graph. While keeping the coarse embedding module & frozen, we then train the distance-compuration prove and refine distance estimates using the original full-resolutinn terrain graph. This strategy allows us to scale our neural model to very large terrains.
Graph neural networks Graph neural networks (GNNs) are class of deep learning model specifically designed to work with graph structured input (Scarselli et al., 2009). In practice, the most commonly used graph neural net- work architecture is the message passing neural network (Gilmer et al., 2017: Jegelka, 2022) where node features are learned by aggregating neighboring node features. For- mally, suppose we are given a graph G = (V, X,), where X = {zo E R : E V} represents the initial node fea- tures; that is, (0)) = Fy- Then at each of the I. layers of
module to im-
Efficient updates for terrain changes. Unlike 3D mesh graphs, terrains are inherently dynamic as they are subject to uncertainty (due to measurement errors)
3

---

De-coupled NeuroGF for Terrains
C(S, Go. &. p)
the GNN, l E [1, LJ. we update the node features at each node as follows:
Σ
((o()) (2)
|s|
2/ = fup (egg : u e(o)))) (1)
(wosda, (wa))s
3.2. Instantiation of the NeuroGF
where 2. denotes the updated feature of node v E V at layer f. (w)) is the set of neighbors of v Jagg aggre- gates previous features from the neighbors (including edge weights) in a permutation invariant manner, and fup com- putes the updated node feature from the aggregated infor- mation. In practice, graph convolutional networks (GCN) (Kipf & Welling. 2016) and graph attention networks (GAT) (Veličković et al., 2018) are among the most commonly used variants of GNNs and have been explored for learning algorithmic tasks (Veličković et al., 2022; Veličković et al., 2020). We consider both GCNs and GAT's in our explo- ration of the design space of NeuroGF. See Appendix A for exposition regarding GCNs and GATss Once trained, GNN can be applied to any graph with any combinatorial structure because the learnable parameters in the aggregate and update functions are shared across all nodes. A single forward pass through the GNN takes time O[IV] + [E)) linear with respect to the number of nodes and edges.
In this paper, we instantiate the embedding module o with several choices of neural network architectures: (1) a stan- dard MLP (2) GCN (3) GAT and (4) transformer architec- ture. The specific input for & varies depending on the chosen architecture. The instantiation of p will be discussed at the end of this subsection. We describe the MLP and GNN instantiation of é denoted as MLP and GNN respectively. We leave the description of the transfomer Appendix B.2.
Multilayer perceptron (MLP). The simplest approach for instantiating the embedding module e is to use an MLP. Given pair of nodes u, v and their initial node features Tu = u, Hy = G. we train a neural model to predict (MLP( R p (MLL) MLP(x.)). Note that FMLP does not utilize the input graph structure and depends solely on the input feature representations of individual nodes. aims to directly learn the shortest path distance function de V x V + E from the train set general function approximation problem. However, our de, is not an arbi- trary function - it is induced by G Thus, using MLPs, as opposed to GNNs or transformers, as & to process nodes independently fails to capture relational information from the terrain graph Gt.
In this paper, we also use the transformer model, which captures global relations between nodes via self-attention but is computationally expensive (O(1112)). We leave the description of transformers in Appendix B.
3. Neural Shortest Path Data Structures
3.1. The NeuroGF pipeline (Zhang et al., 2023)
Graph neural network. In general, when given a terrain graph G and node and when we are using a GNN the initial embedding module, we write the output embedding (1;; G) GNNc(u) to emphasize the incorporation of graph structure as the input of Φ. Hence the full model now is (G, Iup G) = (G.)) (*.)) We use GCNs and GATs as the choices for the (message passing) graph neural network GNNG: GCNs are the specific mes- sage passing architecture originally used in (Zhang et al., 2023); we include GAT's (Veličković et al., 2018) they are able to attend to more 'important" vertices.
We begin by reviewing the framework of NeuroGF (Zhang al., 2023). Given a metric space dx), the goal of the NeuroGF framework is to approximate the target geodesic (or SP-distance in our case) function f = =dx= X'x - IR. That is. we approximte dx(x1, by p(z2)) where 6= : X' + R and p TRD - RR. See Figure 1 for an illustration. To motivate this formulation, consider a tradi- tional metric learning scenario where p simply represents an I distance in the embedding space. In this case, NeuroGF is simply a Siamese network that uses 6 as an embedding module to map input node features to high-dimensional latent space Z = R However, by using an MLP in the place of p. we can approximate distance functions that are not Lp embeddable. Thus, the entire NeuroGF framework is intuitively an initial Siamese embedding module & followed by a final distance computation module p.
For a general GNN, the output node embeddings are com- puted as described in Equation (1). In our setup, for each node v E V. the initial input node features are 1 = â E R3,, and the output of Φ(t) is the final node embedding I!)"), where L represents the number of layers in the GNN. In practice, we also incorporate the terrain edge weights in the computation of the next node features (see details in Appendix A).
Recall that we represent the terrain a graph Gr, (V. E, X, w E + R-) where w represents the edge weights and X is the set of input node features, i = (x. y, ((x,v))))))))))) v)) E R3. Our training set S is made up of a subset of pairs of vertices and their shortest path distances. The final loss function is:
Each forward pass of the GNN is more than one forward pass of the MLP, as it takes time 0( + +|El) + (((SSra) l), while in the case of MLP, a forward pass only linear in the number of training set size. However, one would expect
4

---

De-coupled NeuroGF for Terrains
that the embedding learned by the GNN is much better than that of MLP with even a small number of training pairs, the utilization of the graph structure allows the embedding module to be aware of global relation between graph nodes. Finally, while the GNN can incorporate the graph structure in each node embedding output, it can only see within an L-hop neighborhood of each node where is the number of layers in the GNN.
Intuitively, this de-coupled training strategy uses e to gener- ate 'decent' first embedding and delegates fine-tuning to the final distance computation module p MLP to correct any errors incurred by Φ. De-coupling the training of @ and also allows us to quickly adapt to any changes to the input terrain as we can avoid re-training & and simply re-train the final p. which is faster than re-training the entire NeuroGF.
Mixed coarse-to-refined de-coupled training. This de- coupled training process can be extended to a mixed coarse- to-refined training framework (M-CTR) to further reduce training costs, especially when the initial embedding mod- ule (Φ) is implemented using computationally expensive architectures like GNNs or transformers. In particular, each forward pass in stage 1 takes O + |F] + [Stain,.)) time if we use GNN for Φ, or O(IV)2 + Strain, if we use transformer. This step is the computational bottleneck, and takes orders of magnitude longer time than just training the MLP in the distance computation module (which takes only ((SSuainn22)) for each forward pass).
Instantiation of the distance computation module. We explore two choices of the distance-computation module p: (1) is an Lp distance function or (2) parameterize p as an MLP. The case that is an Lp distance represents the traditional metric-lcarning paradigm, where the embed- ding module & is a Siamese network. the case where we parameterize p as final MLP (as proposed by NeuroGF (Zhang et al., 2023)), the model more accurately approxi- mates distance functions that may not be isometrically em- beddable into Lg space. Given some instantiation of o, the final output is (LP((((e)) + (é(u:))((() []. where we concatenate (1s)) + ((1z) and the absolute difference (ō(v:) d.,,]l
The key idea of M-CTR training is to leverage a coars- ened version of the input terrain to train the initial embed- ding module & in order to reduce the computational bottle- neck. One can compute the downsampled (coarsened) ter- rain graph via many strategies. In our experiments, since our terrain graph Gj, (V, E, w) is induced by a N1 N₂ grid, we simply produce coarsened graph by downsample the grid to be Ni induced downsampled terrain graph by G¹,-
3.3. De-coupled training process
We now describe our new de-coupled training process for the NeuroGF framework which leverages the distinct roles of the embedding module Φ and the distance computation module nt e usually does not capture global information in highly accurate manner. For instance, if ø GNN, the receptive field is limited by the number of layers in the GNN and restricts the o from capturing the global terrain structure. The distance-decoding stage, when implemented via the MLP, addresses these limitations by learning how to better combine the embeddings to produce more accurate approximation of the target distance. Therefore, we propose two-stage training process which explicitly de-couples the process of embedding generation via á and distance com- putation via p. This decoupling of embedding generation and distance computation is a novel perspective that has so far not been explored in prior work and offers significant practical advantages (which we will explore in Section 4).
Ni for some integer k. Denote the
K x "
Instead of training ø on the full graph Gn, we first train ø on this coarsened version G², using a training set Serain, 1 constructed from C₁2- Then, we freeze e and train only the distance computation module p using a training set Strain.2 from the original high-resolution terrain graph G2, Note that the number of training samples in Strain,2 can be much larger than in Strain, This distance computation module p learns to correct inaccuracies arising from the initial coarse embedding trained on coarsened graph G²2-
4. Experiments
Our new training process proceeds as follows:
We first explore the design space of the NeuroGF pipeline (Zhang et al., 2023), both in terms of the choice of neural networks for the embedding module é, and the effect of the distance computation MLP module p. We then show the benefit of our decoupled- NeurooGF framework and our strategy (M-CTR) as compared to our im- plementation of the original NeuroGF framework for real terrains. We also compare our method to GeGNN, another SOTA neural data structure (Pang et al., 2023). We measure two error metrics: (1) the average relative error with respect to the true SPD (2) accuracy, defined as the percentage of test instances where relative error is below 2%. As we will
Training the embedding module. We train only the embedding module & on training set Strain.1 as a Siamese network to generate node embeddings and use 1, distance between embeddings ([((()) Φ(v)] as the estimate of da(u, u) to compute training loss.
Stage 1:
Stage 2: Training the distance-computation mod- ule. After training é. we freeze its weights and use its output embeddings as input to train the final distance computation module = MLP using a second training set Strain,
5

---

De-coupled NeuroGF for Terrains
kx
De-coupled
GAT 11
1.0
4.1
0.52 = 0.61
0.61 = 0.88
4.0
4.4
1.32 + 1.84
1.66 = 3.19
10.0
4.7
1.86
3.48
3.29 + 6.76
Figure 2. Synthetic terrain surfaces of three of the synthetic terrains (Gaussian amplitudes visualized {1.0, 4.0,, 10.0)).
Table I. Approximate doubling dimension (denoted by kxx) com- pared again the average relative error (%, +)) for the Siamese model and the de-coupled training procedure on synthetic terrains. We also include the maximum amplitude of the Gaussians in the syn- thetic terrain and denote as a. Notice that the de-coupled training procedure can help mitigate the errors introduced by the Siamese embedding.
Norway Number of nodes: 4,000,000
Los Angeles, CA, USA Number of nodess 16,000,000
Resolution: 10 meters
Resolution: meters
California, USA (16M nodes) (3) Holland, Indiana, USA (IM nodes), and (4) Philadelphia (Phil.), Pennsylvania, USA (IM nodes). See Figure 3 for illustrations. We point out the unique complexities of the LA and Norway terrains: the LA dataset is the largest, with 16 million nodes, while the Norway dataset represents a highly mountainous region.
Philadelphia, PA, USA
Holland, IN, USA
Numbor of nodes: 1,0000000
Number ordee: 1,000000 Resolution:
Besolutions 0.9 meterss
Design space and experimental setup. The framework of NeuroGF (Zhang et al., 2023) consists of an embedding module 6 and a distance-computation module p. We instan- tiate the embedding module ø by (1) MLP, (2) GCN (Kipf & Welling, 2016), (3) GAT (Veličković et al., 2018), 8), and (4) a transformer (Vaswani et al., 2017). In what follows, we use X + Y,X E { MLP, GCN, GAT, Transformer } and E {Lp. MLP } to represent all these model designs. The original NeuroGF of (Zhang al., 2023) corresponds to the setup X MLP with X E {MLP, GCN, Transformer). For our de-coupled NeuroGF (indicated by 'de-coupled') ) we first train GAT J,,, freeze its weights, and then train an MLP for the
Figure 3. Visualization of cach terrain's 's height function. Lighter areas correspond to more mountainous regions.
see later, our new strategies significantly improve previous neural approaches on large scale terrains, e.g, an improve- ment (reduction) of more than 10% of error (Table 3) as well as even more significant improvements for weighted terrains (Table 4) and SPD estimation in for terrains with uncertainty (Table 5). Details regarding training, hyperparameters, etc. given in the Appendix C.
module.
4.2. Design space of NeuroGF and de-coupled NeuroGF
Design space of NeuroGF. First, we test the relative error w.r.t. SP-distances by different model designs (including GeGNN of (Pang et al., 2023)) for synthetic terrains. We leave detailed figure and results in Appendix C.3, and only list the key observations here: (1) GCN and GAT far outperform MLP transformer based instantiation of the embedding module & (cf. Appendix C.3, Figure 5). (2) GeGNN (Pang et al., 2023) performs much worse than the original NeuroGF (Zhang et al., 2023) with any instantiation of the embedding module (X+MLP in our setup). (3) Using only X+L1 consistently outperforms X+MLP (the original NeuroGF). Interestingly, using L1 in the latent space out- performs using L2 in the latent space well; that is, X+L, is (sometimes much) better than X+ for any choice of X (cf. Appendix C.3, Figure 5). From these observations, we narrow our architectural explorations and exclude the MLP and Transformer architectures, as well as X+L2 from our further experiments.
4.1. Experimental setup
We use two types of data: synthetic terrain DEMs of dif- ferent "complexity", and real terrain DEMs with up 16 million nodes.
Synthetic terrains. To understand the performance of differ- ent model designs, we generate a series of terrains with the same size but different complexity. These synthetic terrain graphs are generated using a mixture of 2D Gaussians over [0, 10 and the amplitudes from {1.0, 2.0, 4.0...,, 18.0). See Figure 2 for examples. Each terrain graph is induced by 50 x 50 grid and has 2500 nodes. To generate the down- sampled terrain graphs for M-CTR training, we downsample the grid to a 25 x 25 grid (625 nodes).
Real terrains. We use four real-world terrain DEMs: (1)
Troms region of Norway (4M nodes) (2) Los Angeles (LA),
6

---

De-coupled NeuroGF for Terrains
Cribedciig modu catput dieenoeeed
Cribadiing mode sxtput cimonsian-16
Embsdd rg meddle evextt dmmrnim--44
3.25
3.19
0:31
037
De-coup ed
8.28
0123
GAT-L1
0,00
0,103
GAT-MLLL MILP
6075
GCN
2.27
0/2k
335
25
200
1500
305
201
0:00
25
253
Figure 4. Average relative error (y-axis) of each GNN based model against the the amplitude of the Gaussians ('complexity") in an synthetic terrain. Each plot corresponds a different latent space dimension for the embedding module Φ.
Model
Relative Error (%,
Accuracy (%, f) Training Time (min, J)
G1
0.92 = 0.95
91.5
153
GAT+MLP
1.32 = 2.03
89.4
155
GeGNN
13. + 2. 10
34.5
127
Decoupled (ours)
0.84 1.66
92.3
200
Table 2. Results for a downsampled 250x250 version of Norway-250. The GAT+MLP is the same as the NeuroGF framework. Note that the training time for the de-coupled version of NeuroGF includes both the time for training GAT+L1 as well the time to finetune the final MLP distance computation module (which takes approximately Ihr). Best results are highlighted in red.
Effectiveness of de-coupled NeuroGF. In Figure 4, we compare our de-coupled NeuroGF framework with the orig- inal NeuroGF with GNN instantiation (i.e, GLP and GCN+MLP),, as well as with two baseline Siamese architectures, G1 and GCN+L1, over a series of syn- thetic terrains. We include a comparison with the mixed 2500),
de-coupled framework and the Siamese baseline becomes even more pronounced. The de-coupled training of the MLP-basee distance computation module proves crucial in synthetic terrains where the shortest path contour deviates substantially from the Euclidean (L2) distance contour.
Overall, we believe that the approximation quality of each neural method depends on the intrinsic "complexity" of the terrain graph metric, which dimension of the terrain (denoted by kx). A metric space X has doubling constant k if for all >> O, every r-ball (radius r-neighborhood around any point in X) can be covered by at most k 5 balls and and the doubling dimension of X is the base-2 logarithm of the doubling constant (kx = log, (l))). The relationship between doubling dimension and approx- imation quality is theoretically motivated by Theorem 2.1 of (Naor & Neiman, 2012), which states that every metric space can be approximately embedded into Euclidean space with distortion dependent on the doubling dimension the space. In Table we compare the approximate doubling dimension against the relative error of GAT L, as well as our de-coupled neural method. We observe that as dou- bling dimension increases, the relative error incurred by the Siamese embedding approach GAT+Li also increases. Ad- ditionally, our de-coupled training approach seems to help adjust the errors from the Siamese embedding approach. The relative error of the de-coupled approach also seems to increase a lower rate than that of GAT+
coarse-to-refined training approach, M-CTR(6225 where we train the initial embedding module & on coarse version of each synthetic terrain with 625 nodes, then freeze Ø and train only the distance-come computation module on the refined version of the terrain with 2500 nodes. We plot the average relative error in y-axis against the 'complexity' (the maximum amplitutude of Gaussians) of terrains in x-axis.
quantify as the doubling
in Figure 4, our de-coupled NeuroGF frame- work consistently outperforms both the original NeuroGF and the Siamese baselines. We note that our mixed-training strategy M-CTR performs comparable or better than the two NeuroGF instantiations (GAT+MLP and GCN+MLPP) even though its embedding module trained on a much coarser terrain graph (and thus faster). This improvement consistently observed across all output embedding sizes, further emphasizing the robustness of the de-coupled Neu- roGF approach. Finally, using GAT as the initial embedding module outperforms GCN, we will use GAT as the initial embedding module for real terrain experiments below. An expanded version of Figure 4 for a larger set of embedding sizes in Appendix C.
As
Effect of terrain complexity. In Figure 4, we note that as the maximum amplitude of the Gaussians in the syn- thetic terrain increases, the performance gap between the
7

---

De-coupled NeuroGF for Terrains
Dataset
Model
Relative Error (%, 4)
Accuracy (%,1 f)
Training Time (min, .))
Full-GA+
0.94 = 0.95
90.5
683
Norway
Cearse-GAT& L11
1.05 + 0.99
89.2
150
(4M nodes)
M-CTR (ours)
0.90 + 1.49
91.1
183
Our improvement
-14.2 %
+1.9%
Full-GAT+Le
2733
LA
Boarse-GAT+La
1.04 = 1.09
85.51
137
(16M nodes)
M-CTR (ours)
0.88 3.47
94.41
183
Our improvement
-15.4 %
+8.9%
Full-GAT+
0.21 + 0.29
99.6
147
Philadelphia
Cearse-GAT++
2.07 = 1.47
30.1
31
(IM nodes)
M-CTR (ours)
0.51 = 0.71
94.4
Our improvement
-75.4%
+64.3%
Full-GT+ +11
0.11 = 0.12
99.9
123
Holland
2.06 = 1.54
65.1
32
(IM nodes)
M-CTR (ours)
0.86 2.29
90.8
Our improvement
-58.3%
+25.7 %
Table 3. Results for LA (16M nodes), Norway (4M nodes). Philadelphia (IM nodes), and Holland (IM nodes). Our M-CTR and Coarse-GAT L1 have similar training time, however, our M-CTR has much better performance (best performance marked in red). In the last row for each dataset we list our improvement (of M-CTR) over Searse-GAT. +1,): note that for relative error, reduce error (thus the 1-' sign). while for accuracy. we improve (thus the '4' sign). While the full GAT L1 has better performance for Philadelphia and Holland than M-CTR. we note that it takes much longer train. For both Philadelphia and Holland, M-CTR model has much hetter performance than Betrse-GGT+Li For Norway, our model has slightly hetter performance than Bull-GAT+Ta, but is much faster. We extrapolate the training time for Full-GAT +I, on LA (which did finish after 30+ hours) from the training time for Norway under the assumption that training time is linear to input graph size.
4.3. Decoupled-NeuroGHH on massive real terrains
with two approaches: (a) the GAT+L, the full-resolution terrain, represented by Full-GAT+L, in Table 3; and (b) the Cooarse-GA++Ae where we simply apply the coarse embedding network ø trained over the same downsampled version, then use L, distance in the latent space.
For all terrains, the time NeuroGF (and all variants, includ- ing the Siamese network) needs to complete SPD query at inference time is at most 10 ms. See Appendix C for a table of the time needed to compute embeddings. We use a downsampled 250x250 version of Norway as a case study to demonstrate the utility of the de-coupled NeuroGF training procedure compared to the entire end-to-end Neu- roGF pipeline, the Siamese network approach, and the other SOTA model GeGNN. The downsampled graph is used be- cause GeGNN cannot be trained on terrain graphs exceeding 62,500 nodes due to memory limitations. See Table 2 for our results. Similar to what we observed for synthetic terrains, we see that our de-coupled approach has the best perfor- mance compared to all tested baselines. Interestingly, GA outperforms both GeGNN and NeuroGF (which is denoted as GLT+MLP).
As seen in Table 3, our M-CTR has much better relative er- ror and accuracy than Coarse-GAT+LI while the training times are very similar. In particular, the improvements for the LA, Philadelphia, and Holland are notable for both error and accuracy - about 10% for both on LA and over 20% for both on Philadelphia and Holland. For Philadelphia and Hol- land, the Full-GAT T, has better performance than M-CTR but our M-CTR much faster. Interestingly, our M-CTR has better performance than the Full-GAT L1 on Norway as well while it is much faster (only takes quarter of the time needed by the full model). The training of Full-GAT+1A + L1 on the 16M LA model is prohibitively expensive in both time and memory, taking 30+ hours without completion. Note that the training time scales linearly, the training time for Full-GAT+1 is expected to be approximately four times that of training Full-GAT+I, on the Norway dataset.
We evaluate our de-coupled training pipeline, in particu- lar, our mixed coarse-to-refines strategy M-CTR, to full resolution Los Angeles (16M nodes), Norway (4M nodes), Holland (IM nodes), and Philadelphia (IM nodes). In par- ticular, terrains at the size of Los Angeles and Norway have not previously been explored. For our M-CTR, all ter- rains, we first train the embedding network & on (coarse) downsampled version of each terrain (250x250 for Norway and LA, 50x50 for Philadelphia and Holland. We then fine- tune the final distance computation MLP p on train instances over the full-resolution terrain. We compare our M-CTR
Weighted terrains. The improvement of our M-CTR is even more significant when the input terrain graph is weighted. Following usual practices in GIS, we assign each edge (u, v) by (1 + 0)llū - ö1|B where 0 is the absolute value of the angle of elevation. In Table 4, we compare our Note that our improve- ment for the larger LA dataset significant: the relative
M-CTR with the
8

---

De-coupled NeuroGF for Terrains
Datasets
Models
Rel. Err. (%, 4)
Ace. (%; f)
Datasets
Models
Rel. Err. (%, 4)
Acc. (%, f)
Coarse-GAT +11
2.30 = 2.96
62.14
GAT L1
19.4 = 3.04
0.078
Norway
M-CTR (ours)
2.04 = 3.53
68. 06.06
Norway
Decoupled (ours)
1.76 1: 2.30
70.0
Our improvement
-11.3%
+5.9%
Our improvement
-90.9%
+69.9%
Coarse-GAT +L+
3.55 = 2.76
27.53
GAT Li
2.27 1: 2.06
34.6
LA
M-CTR (ours)
1.91 = 4.66
69.42
LA
Decoupled (ours)
0.77 1: 1.04
94.1
Our improvement
-46.2%
+41.89%
Our improvement
-66.0%
+59,5%
Coarse-GAT
2.43
4.62
61.4
GAT L
29.8 1 6.84
0.048
Phil.
M-CTR (ours)
1.32 = 2.96
83,9
Phil.
Decoupled (ours)
6.14 1: 7.88
26.4
Our improvement
-45.7%
+22.5%
Our improvement
-79,4%
+26.3%
Coarse-GAT+L5
2.48
6.20
61.9
GAT L1
48.79 = 7.08
0.092
Holland
M-CTR (ours)
0.82 1.69
93.3
Holland
Decoupled (ours)
9.35 1: 13.2
17.3
Our improvement
-66.9%
+31.4%
Our improvement
-81.0%
+17.2%
Table 4. Weighted terrains results. The improvement has '-' sign for error as we reduce it and "+' for accuracy as we increase it. We note that our M-CTR approach far out-performs the Coarse- GAT + L1 approach for all weighted terrains.
Table S. Results for uncertainty models. Improvement has '-' sign for error as we reduce and "+" for accuracy as we increase For each terrain, our de-coupled approach outperforms I1.+
by averaging the output of our retrained decoupled models (indicated as 'Decoupled (ours)' in the table) and the esti- mate of single G (which has comparable training time as ours). Notice that Holland and Philadelphia have much larger errors as compared to Norway and LA, possibly because a 00.0 perturbation in vertex height represents a far more significant relative change on those comparatively flatter terrains. Overall, our approach achieves dramatically better performance with comparable training time.
error for Coarse-GAT+L, almost doubles that of our M- CTR, while its accuracy is only half of ours.
4.4. J Dynamic terrain changes
Our de-coupled pipeline allows us to efficiently handle up- dates to the terrain. We illustrate this advantage when con- sidering the presence of uncertainty in terrain measurements. See Appendix C for the improvement by our approaches for synthetic scenario where there are edge-weight updates to the terrain.
5. Conclusion
DEMs can have inherent uncertainties from measurement
We demonstrate the effectiveness of neural data tures approximating SPD on large-scale terrain graphs. By leveraging learned embeddings and efficient distance- computation modules, our de-coupled NeuroGF is scalable and allows for more efficient updates with dynamic terrain changes. Our decoupled NeuroGF offers promising al- ternative to traditional data structure for SPD queries for massive terrains. This opens more venues for exploring neural data structures that can summarize input data in a succinct manner yet support efficient queries.
struc-
errors or incomplete data (Banerjee et al., 2003; Zhang et al., 2015). For example, (Zhang et al., 2015) treats terrain height as random variable within a range (instead of fixed value): the height of any vertex v lies in [h) 0.05, (v) 0.05) for height function h Ω + IR. Then can sample mul- tiple potential terrain height maps, and estimate SPD as the average shortest path distance across these multiple samples. Specifically, we randomly sample K terrain instantiations, [G Gi ), each with unique shortest path distances. The ground truth shortest path between vertices u and is computed 1x ΣK dG., v). v).
Impact statement
If we use neural data structure to estimate the SPD, in general, one would need to re-train K models, one for each terrain instantiation G However, with our decoupled training procedure, we only need to train an embedding map once, and retrain only the much cheaper distance com- putation MLPs K times. This improves the time needed to estimate average SPDs by a factor proportional K. To test, carry out this model on downsampled Holland, Philadelphia, Norway and LA terrains (250x250 for Norway and LA, 50x50 for Holland and Philadelphia). For K = 50, our entire retraining takes around 12 hours, while retrain- ing GAT+L, 50 times would take 100 hours. In Table 5, we compare the SPD estimation accuracy of the estimate
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
A Acknowledgements
Work by Pankaj K. Agarwal was partially supported by NSF grants CCF-20-07556, CCF-22-23870, and IIS-24-02823, and by the Binational Science Foundation Grant 2022131. Work by Samantha Chen and Yusu Wang is additionally supported by NSF grants CCF-21 12665 and CCF-2310411.

---

De-coupled NeuroGF for Terrains
References
stone. Proc. VLDB Endow. 7(1):73-84, 2013. doi: 10. 14778/2732219.2732226 URL http://tt/// http:://wwwwlll.. vldb. kaul. pdf.
Aleksandrov, L., Lanthier, M., Maheshwari, A., and Sack, J. R. An e- --aapoxximation algorithm for weighted short- est paths on polyhedral surfaces. In Algorithm The- Dry-SWAT"'8: 6th Scandinavian Workshop on Algo- rithm Theory Stockholm, Sweden, July 8-10, 1998 Pro- ceedings 6, pp. 11-22. Springer. 1998.
Kaul, M., Wong, R. C., and Jensen, C. S. New lower and upper bounds for shortest distance queries on terrains. Proc. VLDB Endow. 9()):188-17, 2015. doi: 10.14778/ 2850583.2850591. URL http: /ww. vldb. org/ pvldb/ holdd//oll// wwwl9ppp1l. /p 68 kaul.
Arge, L., Toma, L., and Vitter, J. S. I/o-efficient algorithms for problems on grid-based terrains. ACM J. Exp. Algo- rithmics, 6:1, 2001. doi: 10.1 0..114599553444445535, URL https: / /doi. org/ / 10. 1145/ 1144/1453594444 945395.
Kim, J., Nguyen, D., Min, S., Cho, S., Lee, M., Lee, H., and Hong, S. Pure transformers are powerful graph learners. Advances in Neural Information Processing Systems, 35: 14582-14592 2022.
Banerjee, S., Carlin, B. P., and Gelfand, A. E. Hierarchical modeling and analysis for spatial data. Chapman and Hall/CRC, 2003.
Kipf, T. and Welling, M. Semi-supervised classification with graph convolutional networks, 2016.
Chen, J. and Han, Y. Shortest paths on polyhedron. In Proceedings of the sixth annual symposium Computa- lional geomelry, pp. 360-369, 1990.
Lanthier, M., Maheshwari, A., and R. Sack, J. Approxi- mating shortest paths on weighted polyhedral surfaces. Algorithmica, 30:527-562, 2001.
Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani. M., Minderer, M., Heigold, G., Gelly, S., et al. An image is worth 16x16 words: Transformers for image recognition at scale. International Conference Learning Representations (ICLR), 2021.
Liu, Z., Lin, Y., Cao, Y., Hu, H., Wei, Y., Zhang, Z., Lin, S., and Guo, B. Swin transformer: Hierarchical vision transformer using shifted windows. Proceedings of the IEEE/CVE International Conference on Computer Vision (ICCV), pp. 10012-10022, 2021.
Loshchilov, and Hutter, Decoupled weight decay regu- larization. In 7th International Conference on Learning Representattins (ICLR), 2019.
Dwivedi, V. P. and Bresson, X. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699, 2020.
Mitchell, J. S., Mount, D. M., and Papadimitriou, C. H. The discrete geodesic problem. SIAM Journal on Computing, 16(4):647-668, 1987.
Ghojogh, B., Ghodsi, A., Karray, F., and Crowley, M. Spec- tral, probabilistic, and deep metric learning: Tutorial and survey, 2022. URL https: /aap/axxivv.//////a///aaa orggorgggao....... abs/ 2201. 09267.
Mitchell, J. S. et al. Geometric shortest paths and network optimization. Handbook of computational geometry. 334: 633-702, 2000.
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chem- istry. In Proceedings the 34th International Conference on Machine Learning (ICML), pp. 1263-1272. PMLR, 2017.
Naor, A. and Neiman, O. Assouad's 's theorem with dimension independent of the snowflaking. Revista Matematica Iberoamericana,
2012.
Hazel, T., Toma, L., Vahrenhold, J., and Wickremesinghe, R. Terracost: Computing least-cost-path surfaces for massive grid terrains. ACM J. Exp. Algorith-
Pang, B., Zheng, Z., Wang, G., et al. Learning the geodesic embedding with graph neural networks. ACM Transac- tions on Graphics (SIGGRAPH Asia), 42(6), 2023.
mics, 12:1.9:1-1.9:1 2008. doi: 10.1145/1227161.
Scarselli, F., Gori, M., Tsoi, A. C.,, Hagenbuchner, M., and Monfardini, G. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2009. doi: 10.1 10.11099TNN
1370600. URL https::/ddas /ttp::::/ddoiiooo www.oi.ooog//000 stttp://doi.org/10..12 1145/
1227161 61 1370600.
Jegelka, S. Theory of graph neural networks: Representa- tion and learning. In Proc. of the International Congress of Mathematicians (ICM), 2022. Also see arXiv at 2204.07697.
Schreiber, Y. and Sharir, M. An optimal-time algorithm for shortest paths on convex polytope in three dimensions. Discret. Comput. Geom., 39(1-)):500-57 2008. doi: 10. 1007//004544000-993331 URL https: / /doiioo.or 10. 10.1007//0004440077-000
Kaul, M., Wong, R. C., Yang. B., and Jensen, C. Finding shortest paths on terrains by killing two birds with one
10

---

De-coupled NeuroGF for Terrains
Tran, N., Dinneen, M. and Linz, S. Close weighted shortest paths 3d terrain surfaces. In Lu, C., Wang. F,, Trajcevski, G., Huang, Y., Newsam, S. D., and Xiong, L. (eds.), SIGSPATIAL '20: 28th International Conference on Advances in Geographic Information Systems, Seattle, WA, USA, November 3-6, 2020, pp. 597-607, ACM, 2020. doi: 10. N0.11445/3397533334422222 org/10. 11.11....1//11
Zhang, Q., Hou, J., Adikusuma, Y. Y., Wang, W., and He, Y. Neurogf: A neural representation for fast geodesic distance and path queries. In Advances in Neural Infor- mation Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
URL https: pntttps://d... //doi. 3422216
Zhang, W., Agarwal, P. K., and Mukherjee, S. Contour trees of uncertain terrains. In Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 1-10, 2015.
Varadarajan, K. R. and Agarwal, P. K. Approximat- ing shortest paths on nonconvex polyhedron. SIAM Comput., 30(4);13, 2000. doi: 10.1137/
500975337999352759, URL https::t///c..... https::/do..org//// 1137/500975399993222
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. At- tention all you need. Advances in neural information processing systems, 30, 2017.
Veličković, P., Cucurull, G., Casanova, A., Romero, A.,
Liò, P., and Bengio, Y. Graph attention networks. Proceedings of the International Conference on Learning Representations (ICLR), 2018.
Veličković, P., Ying, R., Padovano, M., Hadsell, R., and Blundell, C. Neural execution of graph algorithms. In Pro- ceedings of the 8th International Conference on Learning Representations (ICLR 2020), 2020.
Veličković, P., Badia, A. P., Budden, D., Pascanu, R., Banino, A., Dashevskiy, M., Hadsell, R., and Blundell, C. The clrs algorithmic reasoning benchmark. Pro- ceedings of the 39th International Conference on Ma- chine Learning (ICML 2022), pp. 22084-22102 PMLR, 2022. URL /ttp://eoccceecssceeee// .ww.mrr..... press/ v1 1el.veelccooviii c22a. html.
Wei, V. J., Wong, R. C.-W., Long. C., Mount, D., and Samet, H. Proximity queries on terrain surface. ACM Transactions Database Systems, 47(4):1-59, 2022.
Wei, V. J., Wong, R. C.- Long, C., and Mount, D. M. efficient shortest path computation on terrain surfaces: A direction-oriented approach. IEEE Transactions on Knowledge and Data Engineering (TKDE), xx(xx):xX- 2024. doi: xxx.
Xin, S.-Q. and Wang, G.-J Improving chen and han's algorithm on the discrete geodesic problem. ACM Trans- actions Graphics (TOG), 28(4))1-8, 2009.
Xu, K., Li, Zhang, M., Du, S. S., Kawarabayashi, K.-i., and Jegelka, What can neural networks reason about? arXiv preprint arXiv: /905 / 2019.

---

De-coupled NeuroGF for Terrains
A. Graph Neural Networks
We provide exposition regarding different message passing GNN architectures architectures. Recall that the general form of the a message passing GNN was given in Equation (I). Most popular architectures, such as GCN or GAT, follow the general format in Equation (I) with differences between architectures arising from the implementation of the aggregation and update functions. A GCN uses normalized mean pooling the update and aggregation function so each layer E the node is updated as
2 10 - ( Σ
w(u v) uEN(O))UG) Veg(() ()) deg(u)
W 20 (L-1)
(3)
where W(() represents the learnable weights at layer l and w(u, v) is the weight of an edge (u, v). Note that if there are no edge weights in the input graph, w(u, u) = 1. In contrast, graph attention networks (GATs) use sum-pooling to aggregate neighboring node features along with attention mechanisms within the aggregation function in order to assign levels of importance to node neighbors. At each layer E, GATs update node features as
x
-
Ovu W (()eeeee)) Σ
(4)
(uE((e)
where Oeu is learnable attention coefficient. Edge features for this network are incorporated when computing the attention mechanism One by concatenating the edge feature with the node feature before applying/computing the attention mechanism. Note that in our case, our input node features are the lift (0) e for each v E V and input edge features, given an edge (u, v), is the Euclidean distance between the lifts of and v.
B. Transformers
B.1. Transformer architecture
Transformers have become the state-of-the architecture for handling tasks in natural language processing and computer vision (Vaswani et al., 2017: Dosovitskiy et al., 2021: Liu et al., 2021). Each layer of the transformer is a sequence- to-sequence permulation equivariant function and consists of transformer block. Each transformer block includes multi-head self-attention mechanism and a position-wis wise feed-forward neural network. Given sequence X E RnxD, the output of single attention head Attn Rax D + Rax is computed as
Attn(X X) softmax (WQ(X)))))
where Wo, Wx E DxD, The output of this attention mechanism is then passed through an MLP which then computes the updated feature for each token independently so the final output is MLP(X + X where Wv E DxD Intuitively, the N x N matrix X (XX(Xxx)² computes self-similarity of any two elements in (although after linear transformations by WQ and WK. Using the softmax normalizes the self-similarity values across each row, and therefore records, for each element in X, the "influence" ("attention") ") of any other element, and the multiplication with XWy then integrates such influences update each element in X.
Since transformer parameters are shared across all elements of the input sequence, once the transformer is trained it can be applied to an input sequence of any size. While there have been several works adapting transformers for graph structured input (Dwivedi & Bresson, 2020), one can also directly apply standard transformers directly to graphs (Kim et al., 2022). In fact, one can view a transformer as graph neural network over a complete graph where we compute an additional edge feature which captures the relative importance of pairs of nodes. However, the transformer takes quadratic time (((V)2) whereas the standard message passing GNN is linear with respect to the size of the input graph O([VI |EE).
B.2. Intialization of embedding module with transformer
We also explore the use of a transformer as the initial embedding module ø. In this approach, the entire graph is tokenized and presented
input sequence, deseribed earlier in Section 2. The transformer treats the terrain graph global
2A sequence of N elements, each being a D-dimensional vector, can be represented by point E ND Intuitively, X is a N x matrix, where each of the N rows is a D-dimensional vector. A function RND - N'D is permutation equivariant if its output respects the permutation of the rows the input. In other words, for any permutation matrix II, we have that f(IIX) = I
12

---

De-coupled NeuroGF for Terrains
Latent embedding dimension
4
16
32
64
128
2.0
3.63
+ 2.84
1.32 + 1,11
1.04 + 1.16
0.82 + 1.19
1,27 = 1.70
4.0
6.46
+ 4.98
2.93 + 3.34
1.69 + 2.50
1.95 + 3.09
1.96 + 3.33
10.0
9,41 + 8.57
3.72 + 4.59
2.77 + 3.81
2.86 + 6.11
2.87 + 7.16
Table Relative error (%,, 4) versus latent embedding dimension for GAT Ta for the synthetic dataset with Gaussian amplitude a E (2.0, 1.0, 10.03. We see that relative error is mostly stable after embedding in R244.
information, where information from all nodes are simultaneously accessible during the embedding computation. Unlike when the GNN is used as the Φ. which explicitly leverages local connectivity to compute embeddings, the transformer operates on a global scale and can capture long-range dependencies. In short, transformers excel at incorporating global context at the cost of not necessarily being able to explicitly leverage local graph structure, whereas GNNs are more naturally suited for encoding local connectivity patterns but may struggle to capture long-range dependencies effectively, as mentioned previously.
While our discussion focuses on the single-terrain case, it is important to note that both the GNN and transformer-based approaches can naturally extend to cross cross-terrain settings. These models take the terrain graph as input, allowing them to generalize to multiple terrains without requiring separate model for each. In contrast, the MI.P-ased approach is limited in this regard. Since the MLP processes input features independently and lacks any inherent mechanism to incorporate graph structure, a single MLP model specific to single function. Applying an MLP to cross-terrain settings would require retraining or maintaining a separate model for each terrain.
C. Additional experimental details
C.1. Training details
We train all models using PyTorch and 8 NVidia A1000 GPUs. As a note on hyperparameter tuning: in general, we tuned the depth (between 3,, 4} layers) and output latent embedding of the initial embedding module & (between {4, 16, 32, 64, 128)) on the small synthetic datasets. The best hyperparameters are then used to training the networks on the real-world terrain datasets. We focus on tuning the hyperparameters for Siamese embedding module and fix the final distance computation MLP hyperparameters at two layers and 256 hidden units. We make a special note of the dimension of the latent embedding for the Siamese GNN module as this is likely affect the final quality of the Siamese network approaches and report the relative error for the Siamese network approach (GAT + L1) on various synthetic terrains as the latent embedding dimension increases in Table 6. We note that more detailed results showing the relative error of all approaches with different latent embedding dimensions can be seen in Appendix C.3, Figure 5. Observe that the error incurred by the Siamese network stabilizes after embedding to R64, Therefore, for each GNN-based model, we utilize an embedding module with three GNN layers each with 128 hidden units and an output embedding dimension of 64, An exception is when training the full GAT+Li model on the Norway dataset where resource constraints necessitate training a smaller embedding module model configured with an output embedding dimension of 16 and 32 hidden units per layer. We use the same configuration for MLP and Transformer-basee models and use two attention heads for the Transformer- based model. Note that in the case of M-CTR training on Norway, we first train on downsampled terrain, which allows us to maintain the original configuration with a 64-dimensional output embedding. Each neural network is trained using the AdamW (Loshchilov & Hutter, 2019) optimizer with learning rate of 0.001. Finally, each model is trained for 500 epochs except for GAT+L1 trained on the full Norway, Holland, and Philadelphia datasets, which are trained on 100 epochs because of time considerations. In the final finetuning of the distance computation module (in our de-coupled/M--CT training approach), we train the final MLP for 1000 epochs.
C.1.1. DATASET DETAILS
A complete table of train and test set sizes is provided in Table 7. As described in Section 3, Strain,1 serves as the initial training set in our decoupled approach, used to train the embedding module o, while Strain.2 is used to fine-tune the final distance computation MLP.
Since the artificial terrains are significantly smaller, we construct both Strain, and Strain.2 by randomly sampling 50K
13

---

De-coupled NeuroGF for Terrains
source and target nodes along with their shortest path lengths. However, generating 50K random source-target pairs is computationally expensive for real terrains, even in their downsampled versions. To address this, we sample 1000 random source points per real terrain. For Strain, we select 500 targets per source, and for Strain.2, we sample 3500 targets. For the experiments with terrain uncertainty models, we reduce |Strain.2| to accelerate training to ensuring that finetuning all 50 ML.ss was computationally feasible. Specifically, we sample 500 targets per source for these models.
For the artificial terrains, we generate the test sets by sampling 1000 sources and taking their shortest path distances to every other node in the terrain. For the real terrains, we generate test sets by sampling 1000 source points and then sampling 500,000 targets across the terrains.
Strain 1
Strain.2 2
Test
Artificial
5 x 10
5 x 10*
2.5 x 10
Norway-250
5 x 10a
3.5 105
5 x 10
Norway
5 x 10a
3.5 x 10
5 x 10s
LA
5 x 10a
3.5 x 10
5 x 108
Holland
X 104
3.5 x 10a
5 X 10s
Philadelphia
X 104
3.5 105
5 X 108
Uncertainty models
5 x 104
5 104
5 X 10
Table 7. Dataset sizes for all terrains. Note that Norway 250 refers to the downsampled 250x250 version of Norway used in Section 4
Table for comparison with GeGNN.
C.2. Time to generate initial embeddings
In addition to the time required for SP-distance approximation at inference, we also measure the time needed to compute each embedding for the GNN-based module in Table (as GNNs were shown to have the best performance among all tested models). Since a single GNN pass scales linearly with the number of nodes and edges, O[[V] + [E)), the embedding computation time increases with terrain graph size, as expected. However, once computed, embeddings can be stored and reused for distance queries, offering significant time savings especially compared to the nen-ne SOTA approach, which required several days of pre-processing time to construct a data structure for terrain with 180,000 nodes (Wei et al., 2024).
# of nodes
625
2500
62500
4M
16M
Time (s)
0.001
0.5
2
21
107
Table Time required generate embeddings using a GAT with the specified hy hyperaarameters above for input graphs of varying sizes. As the number of nodes increases, the embedding computation time scales accordingly.
C.3. More results on exploring the design space on artificial terrains
In Figure we show the average relative error of different model designs over the test sets for artificial terrains. We plot the average relative error (y-axis) against the 'complexity' (the maximum amplitude of the Gaussians) of each artificial terrain in the -raxis. We observe that GNN-based embedding modules consistently outperform MLP and transformer-based modules by a significant margin. This result is expected as MLP-based embedding methods, as discussed in Section 3, rely solely on pointwise information for training and cannot incorporate the terrain structure. Additionally, while transformers can encode global terrain information via the initial position encoding (of coordinates) as well as global self-attention operations, the self-attention mechanism does not appear to be as effective as GNN message-passing in retrieving path information. Indeed, have been previously observed that GNNs naturally align with classical shortest-pathl algorithms like Bellman-Fort Ford and Dijkstra, enabling them to better capture and propagate graph structure in way that facilitates accurate SP-distance estimation (Xu et al., 2019; Veličković et al., 2020). We also note that transformers require @(IV)²) time to compute self-attention, while GCNs and GAT's are linear O(VVI + FE)) to the size of input graph.
Furthermore, among the GNN choices, we observe that the GAT consistently performs better than the GCN. This again might not be surprising as GAT allows attending to different neighbors differently when aggregating messages at graph node. We also note that GeGNN of (Pang et al., 2023) is worse than GCN+MLPP (which can be viewed as the original
14

---

De-coupled NeuroGF for Terrains
aimorsioneé
Emboddlnn suiput dimensiote16
Enbbedding dimonsoti322
Aee 000000000000000000
10-1
10
175
2.5
325
17.5
Angliaed Cousiaass
Arpttadeed SUASAAOTS
Embedding medule output dimessio=544
Embadding moduls oulpuu depputddmmnnn dimansio=1128
GAT+L2
GAT+MLP
MLP+L1
MLP+MLP
Transfomer+Mle
GON+L1
GCN+L2
7.5 12.0
17. 2013
32.5
35.0
GEN+MLP
GeGNN
Figure 5. Average relative error for each model artificial terrains. Each plot corresponds to different output embedding size for The x-axis each plot corresponds to the amplitude of the Gaussians a given artificial terrain and the y-axis corresponds to the average relative error.
NeuroGF (Zhang et al., 2023)). Most interestingly, we note that using only X+L consistently outperforms X+MLP as well as L2 From these observations, we narrow down our architectural explorations and exclude MLP and Transformer based architectures from our further experiments.
C.4. Synthetic perturbations terrain edge weights
We artificially perturb the terrain graphs of downsampled versions of Norway and Los Angeles (each of them 250x250 terrains) and introduce perturbations by scaling each edge weight by some value sampled from (V.00, 1.0). Instead of retraining the GAT L1 embedding module, which is expensive, we can simply use de-coupled training approach and re-train the final distance computation module according to the new weighted terrain. The relative error of the previously trained GAT L1 and the de-coupled approach is shown in Table 9. This updated de-coupled model achieves significantly lower error compared to directly using the previously trained model. While the original model cannot approximate shortest paths at all on the perturbed terrain, retraining just the distance computation module yields accurate shortest path estimates with minimal computational overhead.
Norway
Los Angeles
GAT +L1
132%
186%
updated-de-coupe 3.46%
4.36%
Table Average relative error on perturhed versions of 250 250 downsampled version of each node. We compare the decoupled training approach, where & is first trained on downsampled version of the terrain and then final distance adjustment MLP is re-trained on the new terrain, against original &, which directly uses the L1 distance between embeddings as the final estimate.
15

---

De-coupled NeuroGF for Terrains
Embetding module dmensioned
Embetding matule dimenion-15
Emoedding madule dimensionn52
0.175
2.150
3.500
6.152
2.125
0.12
2.05
3.05
0.335
1.000
2080
0:355
5.005
3.05
0.529
2,000
25
53
12.0
12.5
150
37.5
200
25
50
75
160
125
35.0
175
20
10
75
10.0
125
150
20.
oulputt
De-coupled
5.150
M-CTR
5.125
3.25-
GAT+L1
GAT+MLP
2,100
GCN+MLP
2.60
1.25
3.05
1.000
3.
12.5 Amgiitute Gaserrbone
15.0
150
20.0
3.000
5.
7.5
12.3
35.0
Amplhude CaGunarare
Figure 6. Expanded version of Figure 5 for GNN-based approaches only. We plot the average relative (y-axis) of each GNN based model against the the amplitude the Gaussians ("complexity") in an artificial terrain. Each plot corresponds to a different latent space dimension for the embedding module ó.
16


Reviews:
[{"review_id": "i1SAx1tm2A", "reviewer": "Reviewer_Qpau", "summary": "This paper presents decoupled-NeuroGF framework for efficient approximate SPD queries on large terrain DEMs, based on the NeuroGF framework. This paper appropriately abstracts high-resolution terrain datasets as weighted graphs. The proposed decoupled-NeuroGF with a two-stage mixed-training strategy significantly improves computational efficiency and model performance, making the method suitable for large scale terrain. It reduces training time from days to hours for million-scale terrains and maintains high SPD approximation accuracy. The method also supports efficient updates for terrain changes through retraining only the distance-adjustment module. Experiments on real-world terrains with up to 16 million nodes demonstrate its scalability and superiority over previous approaches.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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. \n\n**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.\n\nWe 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).\nTheoretically, it could be interesting to provide sample complexity bounds w.r.t. doubling dimension but we leave this to future work.\n| Doubling Dimension| De-coupled| GAT + L |\n|-|-|-|\n| 4.1| **0.0052**| 0.0061|\n| 4.4| **0.0132**| 0.0166|\n| 4.7| **0.0186**| 0.0329|\n*Table:  Approximate doubling dimension, and average relative error of each model.*\n\n**Comparisons to other methods:** Please see our response to Reviewer 2aDC. \n\n**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.\n\nWe 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).\n| Dataset| Model| Relative Error (%) ↓ | Accuracy (%) ↑ |\n|-|-|-|-|\n|**Holland, IN**| Coarse GAT + L1| 2.06 ± 1.54| 65.1|\n| | M-CTR| **0.86 ± 2.29** | **90.8**|\n| **Philadelphia, PA**| Coarse GAT + L1| 2.07 ± 1.47| 30.1|\n|  | M-CTR| **0.51 ± 0.71** | **94.4** |\n\n**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.", "claims_and_evidence": "The paper's claims are well - supported by evidence:\n\n[1] The significant reduction in training time is evidenced by experiments showing the method cuts training from days to hours for large terrains.\n\n[2] Model performance improvement is proven by data indicating the method maintains high SPD approximation accuracy and enables efficient updates for terrain changes.\n\n[3] The two - stage mixed - training strategy's benefits are experimentally validated, proving its effectiveness in enhancing computational efficiency and model performance.\n\nTo strengthen the evidence:\n\nMore comparative data on terrains of different scales could be provided to better demonstrate the method's versatility and efficiency across various terrains.", "methods_and_evaluation_criteria": "The methods and evaluation criteria presented in the paper are reasonable for the problem of efficient SPD queries on large-scale terrain DEMs. The decoupled-NeuroGF data structure and the two-stage mixed-training strategy address computational bottlenecks and enable efficient training on large terrains. The evaluation focuses on key aspects like training time reduction, approximation accuracy, and efficient updates for terrain changes, which are appropriate for assessing the method's effectiveness in real-world applications.", "theoretical_claims": "The theoretical claims regarding complexity in the paper are correctly proven.", "experimental_designs_or_analyses": "The paper's experimental design for SPD queries on large-scale terrain DEMs is reasonable. It uses synthetic terrains with varying complexity but the same size, generated via 2D Gaussian mixtures, to evaluate different model designs. However, evolving more datasets with more vertices and corresponding complexity is recommended, as this paper aims to solve SPD question on high-resolution terrain datasets.", "relation_to_broader_scientific_literature": "The key contributions of this paper are closely related to the broader scientific literature in several ways:\n\n[1] Extension of NeuroGF Framework: This paper builds upon the existing NeuroGF framework, which is already a significant contribution to the field of geodesic distance estimation. By proposing a decoupled-NeuroGF data structure, the authors extend the applicability and efficiency of the original framework, addressing its limitations in handling large-scale terrain DEMs.\n\n[2] Innovative Training Strategy: The two-stage mixed-training strategy is an advancement in training neural data structures for terrain analysis. This approach not only reduces computational bottlenecks but also allows for efficient training on large terrains, which was previously challenging. This strategy can be seen as a progression from traditional training methods, incorporating insights from model optimization and efficient learning techniques.", "essential_references_not_discussed": "No essential references appear to be missing from the paper's discussion.", "other_strengths_and_weaknesses": "Strengths.:\n1. The proposed decoupled-NeuroGF framework represents a creative advancement in the field. By separating the training process into two stages, it effectively reduces computational demands and enhances training efficiency on large-scale terrains, which is a significant improvement for practical applications.\t\n2. The method's ability to handle dynamic terrains by updating only the distance-adjustment module is also a valuable contribution, as it addresses the realistic challenge of terrain changes.\n\nWeaknesses:\n1. The experimental section could be strengthened by including more diverse and large-scale datasets to better showcase the method's generalizability.\n2. While the paper presents a novel approach, a more detailed comparison with other existing methods would help better position its contributions within the broader literature.\n3. The scope of the work appears to be somewhat limited. The paper could benefit from a more extensive exploration of the framework's capabilities and potential applications, which would provide a more comprehensive understanding of its value and impact.", "other_comments_or_suggestions": "No additional comments.", "questions_for_authors": "High-resolution terrain data set is a fundamental assumption in this paper. \n\n[1] How to determine whether a data set belongs to this category? \n\n[2] Could some indicators like vertex density be used for quantification? The paper seems to lack relevant analysis.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DvF0Zyag5D", "reviewer": "Reviewer_2aDC", "summary": "This paper proposes a De-coupled NeuroGF for efficiently approximating SPD queries on large-scale DEMs. The key contribution authors decouples the Siamese embedding module and the distance calculation module in NeuroGF. By combining an efficient two-stage hybrid training strategy, the method significantly reduces computational bottlenecks, making training on large-scale terrain DEMs (up to 16 million nodes) feasible. Experimental results demonstrate that the method performs excellently on both synthetic and real datasets.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**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.\n\n**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:\n\n(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.)\n\n(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.\n\n(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.)\nCurrent 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.\n\nIn 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).", "claims_and_evidence": "The main claim is the decoupled training framework, combined with a two-stage hybrid training strategy, provides an efficient solution for SPD queries on large-scale terrain DEMs. This claim is supported by clear by experiments.", "methods_and_evaluation_criteria": "The evaluation criteria include mean relative error and accuracy, which are commonly used metrics for SPD approximation problems and are both reasonable and standard. The datasets including synthetic and real-world terrains, fully test method performance.", "theoretical_claims": "I think this paper focus on the practical implementation. Therefore, there are no theoretical claims or proofs that need to be verified.", "experimental_designs_or_analyses": "I have read the experimental section and believe that it provides sufficient evidence to support the paper's claims.", "relation_to_broader_scientific_literature": "This paper refers to NeuroGF, and extend this idea to large-scale terrain DEMs, addressing the scalability challenges", "essential_references_not_discussed": "The comparison methods in the paper are only up to 2023, which may be somewhat outdated for ICML 2025. Are there any updated methods from 2024?", "other_strengths_and_weaknesses": "Strength:\n\n1.\tThe paper is generally well-written, well-structured, and easy to read and understand.\n\n2.\tThe proposed method achieves training on large-scale terrain DEMs and accelerates the training stage. This is the main advantage of the proposed method and is a good improvement.\n\n3.\tExtensive experiments on both synthetic and real datasets provide strong evidence.\n\nWeakness:\n\n1.\tThe paper does not provide detailed information on hyperparameter tuning or sensitivity analysis, which could affect the understanding of reproducibility and robustness. For example, in M-CTR, increasing the value of k reduces training time, but what impact does this have on accuracy? Does each dataset require separately designed parameters?\n\n2.\tThe comparison methods are only up to 2023. Are there any methods from 2024 or more recent ones?", "other_comments_or_suggestions": "1.\tIt is recommended to include a sensitivity discussion or ablation study on key hyperparameters (such as embedding dimension, number of GNN layers, and coarsening factor) to improve reproducibility.\n\n2.\tcompare with more recent methods.", "questions_for_authors": "Dividing the network into two parts to accelerate training is a common approach in the computer vision (CV) field, such as in ACE[1]. What are the advantages and differences of the method proposed by the authors?\n\n[1] Brachmann E, Cavallari T, Prisacariu V A. Accelerated coordinate encoding: Learning to relocalize in minutes using rgb and poses[C]//Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2023: 5044-5053.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethics_expertise_needed": ["Other expertise"]}}, {"review_id": "k1GbaFgmUD", "reviewer": "Reviewer_j9PW", "summary": "This paper proposes a new learning-based approach for answering shortest path distances on large-scale terrain DEMs. Overall, the proposed method extends the prior work of NeuroGF while providing a comprehensive and in-depth analyses on the training mechanisms and design choices of neural components. Extensive experiments demonstrate that the proposed method brings obvious improvement in terms of both accuracy, efficiency, and scalability.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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. \n\n**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.", "claims_and_evidence": "Well supported.", "methods_and_evaluation_criteria": "Comprehensive experimental evaluations.", "theoretical_claims": "Technically sound.", "experimental_designs_or_analyses": "Well-organized experimental setup.", "relation_to_broader_scientific_literature": "Closely related to geometry processing and downstream applications of geospatial data processing.", "essential_references_not_discussed": "Reference adequate.", "other_strengths_and_weaknesses": "In general, this paper deals with an essential and highly valuable problem of developing efficient geodesics answering frameworks, which are not fully investigated in the current community, especially for \"neuralized\" design paradigms. The ways of analyzing the working mechanisms and restrictions of existing baselines and further exploring more effective structural designs are solid and inspiring.\n\nParticularly, the decoupled training of embedding and distance adjustment modules are technically sound. Since the first stage is performed on coarsen graphs, the overall training efficiency can be greatly improved when facing large-scale data. More importantly, we can circumvent the cumbersome re-training process by only fine-tuning the second stage.\n\nIn summary, I tend to think the proposed method is an insightful work to the problem of neural geodesics learning.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "In the right column of page 1, the authors mentioned \"Throughout this paper we assume that a terrain is represented as a xy-monotone triangulated surface Σ in R^3\". What does it mean specifically?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a novel decoupled neural geodesic field framework and an efficient training strategy for approximating shortest-path distances on large-scale terrain digital elevation models. All three reviewers with scores ranging from 3 to 5, recommend accepting the paper. I believe this paper can be a good addition to the ICML 2025. The authors are encouraged to incorporate the reviewers' constructive feedback into the final camera-ready version.
Decision: Accept (poster)