High-Fidelity Road Network Generation with Latent Diffusion Models

1 Introduction

Road networks are fundamental to the functioning of our cities, supporting the efficient flow of goods and people, facilitating trade and economic growth, and enabling access to essential daily services. With cities expanding and road configurations evolving at a rapid pace, obtaining accurate digital representation of road networks has become increasingly vital yet difficult. In practice, roads in the real world may exhibit complex topologies, whose pattern can vary a lot across different regions. Traditional approaches for road network generation often rely on survey and/or remote sensing, using satellite or aerial images to manually or semiautomatically identify road segments [Huang et al., 2020]. Although being able to offer the bird's-eye view of the landscapes, these approaches are often time-consuming and costintensive - high-resolution imagery can be expensive to acquire, while updates may not be frequent enough to reflect the rapid road infrastructure changes. The recent widespread use of location-aware devices, such as mobile phones and vehicles with GPS, has generated an abundance of crowdsourced trajectories when their users move across the urban space, offering a unique view of the structures of the realworld road network. Such data can provide near-continuous insights on how people or vehicles may move on the roads, and thus extracting road networks from that becomes a more cost-effective way than the traditional approaches. To generate road networks, existing methods [Hong et al., 2024] typically project the trajectories on a 2D plane, where the location points of the trajectories are overlayed as density maps. These density maps are then converted to a heatmap with standard computer vision techniques, where each pixel encodes the likelihood of a valid road presents, i.e. an occupancy grid. They then apply heuristic-based algorithms such as non-maiximum suppression to extract road networks from the computed heatmaps, often in the format of a graph where vertices are road junctions while edges are segments.

∗Corresponding author.

These approaches, although more efficient than survey or remote sensing, are still lacking in many aspects. Firstly, discretizing individual location points into heatmaps inevitably causes information loss due to limited resolution, while the directional information encoded naturally in trajectories has been ignored, which are valuable to infer road segment properties, e.g., one-way roads. Secondly, these appearance-based approaches tend to be sensitive to the quality of trajectories - they may work with dense and accurate trajectory - but in reality location data such as GPS records are likely to suffer from positional errors and irregular sampling rates, resulting in disjoint or misaligned roads generated. Finally, only looking at 2D heatmaps these approach often fail to discover non-trivial road topologies. With heuristic-based algorithms like corner/edge detection, it is impossible to tell if an intersection of two lines is a normal road junction or rather an overpass/underpass, as illustrated in Fig. 1.

In this paper, we aim to overcome the shortcomings of existing solutions, and design an end-to-end approach for highfidelity road network generation. Instead of directly trying to knead trajectories into a road network graph, let us first take a step back and consider the inverse problem of generating noisy trajectories from a known road network graph. For a given road network graph, one can easily generate a trajectory by: i) select a finite sequence of edges which joins a sequence of vertices (referred to as a walk in graph theory); and ii) sampling noisy location points according to the edges of the selected walk. This indicates if there is a way to reverse this process, for any trajectory we can discover the corresponding walk describing how it has traversed the underlying road network. Then with sufficiently many trajectories one can generate a large amount of walks, each of which corresponds to a subgraph of the actual road network, and we should be able to reconstruct the final road network graph from them.

Building upon this insight, we propose a novel road network generation framework, called GraphWalker 1 , based on latent diffusion model (LDM) [Rombach et al., 2022]. We formulate the problem of road network generation from trajectories under the umbrella of denoising diffusion-based generative modeling. Essentially, we view trajectories as the noisy and "interpolated" version of corresponding walks on the graph, where GraphWalker is designed to generate those walks and assemble them into a valid road network graph. Concretely, we first train a Walk-to-Graph Variational Autoencoder (W2G-VAE) that can represent arbitrary walks on the road network graph in a latent space, and later reconstruct the graph from walk embeddings. Then we design a novel Trajectory-to-Walk Diffusion Transformer (T2W-DiT) that can generate valid latent walk embeddings with input trajectories as conditions, which are then decoded into actual walks by the previously trained W2G-VAE and assembled into the final road network graph via an end-to-end trainable neural network. In this way, we cast the problem of generating road networks from trajectories into a generative denoising process, and circumvent the challenges of directly reconstructing the whole graph by considering walks in a latent space as the intermediate representations. The technical contributions of this paper can be summarized as follows:

1 Code at: https://github.com/JinmingWang/GraphWalker.

• To the best of our knowledge, we are the first to formulate the task of road network generation from trajectories with end-to-end trainable denoising diffusionbased generative modeling. Unlike existing solutions that rely heavily on hand-crafted heuristic algorithms, our approach generates high-fidelity road networks directly from noisy trajectories via recovering the corresponding walks.
• We design a new generative framework GraphWalker based on LDM, which features a cross-domain VAE named W2G-VAE and a novel T2W-DiT, both bespoke for this particular task. The encoder of W2G-VAE maps walks into a latent space, from which the latter T2WDiT gradually generates walk embeddings given the input trajectories as conditions, while the W2G-VAE decoder recovers valid walks from the generated embeddings and reconstructs the final road networks.
• Extensive experiments conducted on diverse realworld datasets show that GraphWalker outperforms both appearance-based methods and state-of-the-art diffusion-based graph generation approaches, demonstrating significant improvements in generation accuracy and superior robustness with limited trajectory data and unusual road topologies present.

2 Preliminaries

2.1 ProblemFormulation

Trajectory. Let p = (longitude, latitude) be a GPS point. We define a trajectory τ as an ordered set of location points τ = {p1, p2, ..., pN}, which are often sampled from the continuous motion when an agent is moving across the space e.g., on a road network.

Road Network Graph. Following existing literature, we consider road network as a graph, where nodes are junctions and edges are road segments between two junctions. Instead of using the adjacency matrix representation, which often fails to capture many key properties of real-world road networks such as curved road segments, self-loops and multiple segments between two junctions, in this paper we adopt an edge-list representation. Concretely, we define road network graph as G = {e1, e2, ..., e|G|}, where each edge e = {p1, p2, ..., pK} is a polyline containing K points. In our implementation for simplicity we assume a fixed K for all edges. The vertices of the graph are then the collection of start and end points of the polylines, i.e. p1 and pK of each e. Note that G encodes both topological and absolute location information: each edge contains the locations of two junctions (p1 and pK).

Trajectory Walk. For a given trajectory τ, when mapped to the known road network graph G, the finite sequence of edges that τ traverses is defined as its walk w = {ei|i ∈ [1, |w|]} on G, where |w| is the number of edges τ visited. In this paper we assume for any trajectory τ there is always a corresponding walk w exists, i.e. many to one mapping.

End-to-End Road Network Generation. Given the input set of trajectories τ = {τ1, τ2, ..., τM}, the problem of endto-end road network generation aims to find a function f that directly generates the underlying road network graph G on which the trajectories have traversed, i.e. f(τ) →G.

2.2 DiffusionModels

A discrete-time diffusion model [Ho et al., 2020] defines a two-process paradigm. Given a clean data sample x0 ∼ pdata(x), the forward process gradually transforms it into Gaussian noise over T steps according to a predefined schedule β1, . . . , βT . At each step t, the noised sample is drawn from q(xt|xt-1) = N(xt; √1 - βtxt-1, βtI). This process can also be expressed directly in terms of x0: q(xt|x0) = N(xt; √ ¯αtx0, (1 - ¯αt)I), where ¯αt = ∏ti=1 (1 - βi).

The reverse process learns to denoise: a neural network ϵθ(xt, t) is trained to estimate the noise added at each step. This is done by minimizing the loss Et,x0,ϵ|ϵ - ϵθ(√ ¯αtx0 + √1- ¯αtϵ, t)|2 . Once trained, the model can generate samples by iteratively applying the denoising step starting from Gaussian noise. Conditioning information (e.g., labels or other signals c) can be included during both training and sampling by extending the network to ϵθ(xt, t, c).

To reduce computational cost while retaining high output quality, latent diffusion models (LDMs) [Rombach et al., 2022] perform the diffusion process in a compressed latent space. An autoencoder is used to map input data into lowdimensional latent representations, where the denoising network operates. During generation, latent samples are first produced by the diffusion model, then decoded back into the original data space by the decoder.

3 Methodology

3.1 GraphWalker Overview

A naive solution to generate a road network graph from a set of trajectories in an end-to-end manner is to simply feed the trajectories to generative models such as GANs or diffusion models [Goodfellow et al., 2014; Ho et al., 2020]. However, this approach often fails to produce high-fidelity road network graphs, since the input trajectories are typically noisy - the locations of trajectory points may be imprecise (e.g., due to GPS drift), while their distribution can be sparse and/or skewed - thus simply overlying them together as the input of generative models will propagate or even enlarge such noises, leading to inferior results. To address this, we consider a different bottom-up approach. We observe that, although noisy, for a given road network graph G, a trajectory τi can be viewed as a noisy version of a partial graph traversal, i.e. it is possible to recover a walk wi on the graph that corresponds exactly to τi. Once we are able to discover all the graph walks corresponding to input trajectories, it is also possible to assemble those into a consistent G, e.g. by merging duplicate edges/nodes.

GraphWalker follows this intuition and addresses the road network generation task in two stages: i) trajectories to walk embeddings; and ii) graph generation from walk embeddings, as illustrated in Fig. 2. In the first stage, we train a Walk-to-Graph Variational Autoencoder (W2G-VAE) that can encode arbitrary walks on G into a latent space, and later decode G from this space. Then for each input trajectory, we feed it as the condition to a LDM named Trajectoriesto-Walks Diffusion Transformer (T2W-DiT) that operates in such space, and generates embeddings of the corresponding walks. In the latter stage, we use the trained decoder of our W2G-VAE to recover walks from their latent representations, and assemble them into the complete graph G. We now elaborate on each stage in more detail.

3.2 Trajectories toWalk Embeddings

Let τ = {τ1, τ2, ...τM} be a set of M trajectories, and w = {w1,w2, ...wM} be the corresponding walks on the known road network graph G. As explained above, the first stage of GraphWalker is to construct a latent space Z of walks in which: i) any walk can be mapped to its latent representations; and ii) sampling a latent vector from this continuous space (e.g. with appropriate denoising process) can lead to a valid walk embedding - meaning that the space should be smooth under interpolation and/or extrapolation. Note that the input walks, by definition, are chain-like structures. Therefore, we design our W2G-VAE encoder with simple yet effective 1D ResNet [He et al., 2015], which essentially applies variational regularization given w. Note that for the decoding part of our W2G-VAE, instead of recovering only the walks as in standard VAE, we consider an augmented decoder to directly reconstruct G, where modules assembling walks to graph are also end-to-end learnable. We will discuss the decoder details in the following Sec. 3.3.

Now we have a latent space Z induced by our W2G-VAE, which in theory, should be able to encode all possible walks on the road network graph G. The next step is to generate valid walk embeddings, i.e., a sequence of latent vector in Z, given input trajectories τ . We design T2W-DiT, which is able to generate latent walk embeddings from Z conditioned on given trajectories. Essentially, our T2W-DiT starts from a Gaussian noise in Z, gradually performs denoising with input trajectories τ as the condition, and outputs latent embeddings z ∈ Z corresponding to τ . When incorporating τ as conditions, our T2W-DiT first concatenates features from τ and the sampled latent embedding, and then applies a 1D ResNet block to process the concatenated feature sequences. We also design modules in our model to be permutation invariant to ensure that the generated embeddings, and also the final road network graph will not be affected by the order of input trajectories.

To capture the non-trivial spatio-temporal correlations in trajectories and walks, instead of using Multi-head SelfAttention (MHSA) with layer normalization, which is a standard practice in DiTs, we bespoke our T2W-DiT with Negative Euclidean Self-attention (NESA), and consider feature but not layer normalization. Concretely, we first replace the standard layer normalization with feature normalization as follows:

where x ∈ RM×D represents the input features, assuming we have M trajectories as input conditions and D is the feature dimensions. µi = 1L ∑Lj=1 xj,i and σ2 i = 1L ∑Lj=1 (xj,i -µi)2 are the mean and variance of the i-th feature, and ϵ is a small constant (set to 10-5 ) to avoid division by zero. Then the NESA is defined as:

where q, k, v are the projections of the input feature x, analogous to query, key and value in the standard MHSA. The operation dist(·, ·) computes the Euclidean distance between each pair of tokens, and s is a learnable parameter controlling the decay rate with respect to the distance. Note that here NESA does not work well with the standard layer normalization, which will result in tokens with similar distances in Euclidean spaces - leading to very close scores across tokens. Detailed architecture of the proposed T2W-DiT is shown in Fig. 3, with NESA module highlighted on the right.

3.3 Graph Generation FromWalk Embeddings

Now given the M input trajectories τ = {τ1, τ2, ..., τM}, our T2W-DiT has recovered the corresponding latent walk embeddings z = {z1, z2, ..., zM}. The next stage is to generate the final road network graph G from z. As mentioned in Sec. 3.2, instead of employing a standard VAE decoder that only reconstructs walks and manually assembles the road network G later, our W2G-VAE considers an augmented decoder that is end-to-end trainable, and can directly output G. Concretely, our decoder uses a transformer backbone to firstly generate the corresponding walks w = {w1,w2, ...,wM}, which are then fed into an edge clustering module. Within that, the edges of all walks in w are firstly disassembled into individual edge candidates, which are then clustered based on their similarities. Let E denote the set of edge candidates. The edge clustering module constructs a matrix P ∈ R|E|×|E|×4K , where each element of P is the concatenation of two edge candidates (K location points in each edge, with (x,y) coordinates). It then processes P with an MLP and a sigmoid activation function, outputting a symmetric affinity matrix A ∈ R|E|×|E| . Each element Aij ∈ (0, 1) represents the likelihood that the i-th and j-th candidates should belong to the same cluster. With A one can infer the cluster structures among E, e.g., if we consider the affinity between edges as a binary relationship (exists when the affinity score is above a pre-defined threshold), one can discover the cluster that ei belongs to in by looking at its transitive closure.

Let C ⊆ E be a cluster of edge candidates, and AC is a sub-matrix of A, containing only the affinity scores between those edge candidates in C. Let ACuv be the largest value in AC , meaning that eu and ev are the most similar candidates. We then perform a row-wise softmax on the u-th row - ACu,: becomes a probability distribution, which can be seen as the weights of each candidate contributing to the cluster center. Now we can compute the cluster centre by averaging the location points between all edge candidates eu ∈ C, weighted by the normalized ACu,: . We iteratively perform the above for all clusters in E, and obtain a new set of edges, one of each cluster, which is exactly the desired road network G.

3.4 Training

Our approach adopts the standard simulation-free LDM training paradigm. Concretely, we first pre-train W2GVAE with w sampled from a known road network graph G. During training, we consider the following three loss functions: i) KL-divergence as in typical VAE training: - 12 ∑ni=1 (1 + log σ2 i -µ2i -σ2 i ), where µ and σ are the mean and logarithmic variance of the latent embedding z; ii) MSE loss to ensure correct reconstruction of walks: 1M ∑Mi=1 (wi - ˆwi)2 , where wi and ˆwi denote the ground truth and predicted walks; and iii) a binary cross-entropy loss to measure graph reconstruction quality:

and ˆ A are the affinity matrices, calculated from the ground truth w and the reconstructed ˆw respectively. The final loss used for W2G-VAE training is a linear combination of the above three functions.

Then we fix the parameters of W2G-VAE and follow the standard training procedures for diffusion models to train our T2W-DiT. In particular, we encode w into latent encodings z with the pre-trained W2G-VAE, and add noise through the forward diffusion process at a randomly selected timestep t to obtain zt - then T2W-DiT is trained to predict the added noise ϵ using theMSE loss: 1M ∑Mi=1 (ϵi - ˆ ϵi)2 , where ϵi and ˆ ϵi are the ground truth and predicted noise for the i-th data point.

4 Evaluation

4.1 Experimental Settings

Datasets. We evaluate the proposed GraphWalker on realworld datasets collected from three different cities: Tokyo (TYO), Shanghai (SHA) and Las Vegas (LAS). To ensure fair comparison with the appearance-based road network generation approaches, which requires both trajectory data and aerial or satellite images, we follow the existing literature [Hong et al., 2024] and synthesize trajectories with respect to the ground truth road network. This also allows us to have trajectories with diverse motion patterns covering different areas across the cities, which is often limited in most of the publicly available trajectory datasets [Didi, 2017; Crailtap, 2018; Zheng et al., 2011]. Concretely, for an area within the city specified by a bounding box of certain size, we collect its road network data using OpenStreetMap [OpenStreetMap contributors, 2017], and aerial images from Google Maps [Google, nd]. To generate trajectories, we employ the recent work ControlTraj, a diffusionbased trajectory generation technique [Zhu et al., 2024], which can generate human-directed, high-fidelity trajectories constrained by the road network topology. For numerical stability, the generated location coordinates (in the format of GPS coordinates) are z-score normalized. We apply standard data augmentation techniques such as random rotations and flips, while also randomly shuffling the order of data to facilitate permutation-invariant learning.

Baselines. We compare the proposed approach against four strong baselines. i) TR2RM [Yang et al., 2024b], which uses AD-LinkNet to process aerial images and trajectory density maps and capture multi-scale geographical features. ii) DF-DRUNet [Li et al., 2024], which employs two separate UNet [Ronneberger et al., 2015] to process aerial image and trajectory density maps, and then combine them with Gated Fusion Modules. iii) SmallMap [Hong et al., 2024], which uses GANs to generate trajectories heatmaps and resolve irregularities in generated roads. Note that all the above baselines are appearance-based, i.e., eventually they need to extract road network graphs with heuristic algorithms like thinning, corner detection and flood-fill. We also consider a stateof-the-art diffusion-based approach: iv) Graphusion [Yang et al., 2024a], which is a generic graph generation approach based on LDM. We adapt Graphusion to work in our settings, and feed trajectories as the conditions into its generation process. Note that unlike the proposed approach, Graphusion does not consider walks, and its VAE directly encodes/decodes the entire graph.

Metrics. We consider the following metrics, Firstly, we care about the correct ordering and alignment between the generated edges and the ground truth. Therefore we first perform Hungarian algorithm to discover the optimal one-toone mapping between the generated and ground truth edges, and then evaluate Mean Absolute Error (MAE) and Mean Squared Error (MSE) for each matched pair. This gives us two metrics: i) Hungarian MAE; and ii) Hungarian MSE. On the other hand, we are also interested in the point-wise matching error in both directions, and thus we also consider Chamfer Loss, resulting in two additional metrics: iii) Chamfer MAE and iv) Chamfer MSE. Finally, we consider the v) Wasserstein Distance between the distributions of edge lengths in the generated and ground truth graphs, which describes the global structural consistency of road network produced by different algorithms.

4.2 Results

Overall Performance. We evaluate the competing approaches with data across three different cities, each of which is trained on one city and tested on all three, to study their performance when generalized to unseen settings with heterogeneous road network topologies. The results are shown in Table 1. As we can see, appearance-based approaches generally underperform the proposed GraphWalker in most settings, despite TR2RM and DF-DRUNet which also use aerial images during generation. Surprisingly, the more recent diffusion-based Graphusion fails to demonstrate significant improvements over the existing appearance-based methods, indicating that although powerful, without careful customization LDM are not directly applicable to address the problem of road network generation from trajectories. On the other hand, the proposed GraphWalker outperforms all baselines in most cases, showcasing that our W2G-VAE and T2W-DiT, when work in tandem, can effectively generate high-fidelity road networks from noisy trajectories. In particular, GraphWalker consistently performs well when tested on different cities other than training - demonstrating up to 33% improvement over the baselines.

Performance vs. Area Sizes. In this experiment, we investigate how competing approaches perform when generating road networks for an area (bounding box) of different sizes. Specifically, we use data from a bounding box of approximately 250m×250m for training, and evaluate the quality of the generated road networks in areas of four different sizes, as shown in Fig. 4. We observe that most of the approaches except Graphusion enjoy an improved performance as the size increases, most likely due to the fact that more information is available in larger areas despite the noise in trajectories, i.e. the signal-to-noise ratio increases. Graphusion fails in such cases, potentially due to their diffusion models may not be robust enough when road network topologies change significantly as the area expands. Note that the proposed GraphWalker consistently outperforms all baselines in most cases, showing much lower errors especially in settings that they have not been trained on.

Performance vs. Limited Data. This experiment studies how competing approaches perform when input trajectories are limited. This is common in practice as real-world trajectories are often unevenly distributed across the cities: some areas may only have a few sparse trajectories available. In such cases, as shown in Fig. 6 (3rd row), the appearance-based approaches struggle to recover meaningful road networks. To evaluate quantitatively, we train all approaches with 48 trajectories, and during generation provide them with different amount of input trajectories. As shown in 5, the generation accuracy of appearance-based baselines degrades drastically with fewer input trajectories, while Graphusion and our GraphWalker maintain strong performance. This confirms that diffusion-based approaches are inherently robust to limited input data - the proposed GraphWalker is still the best overall with much lower errors.

Robustness toNon-trivial Topology Patterns. In practice, road networks may exhibit complex topology patterns that are challenging to discover only from a bird's-eye view. In this experiment, we show that appearance-based approaches cannot recover road networks with non-trivial topology patterns. The results of different cases are visualized in Fig. 6. For instance, those baselines may generate erroneous road networks when there are multiple road segments between two junctions (row 1), there are overpasses/underpasses (row 2 and 3), or just roads with self-loops (row 4). On the contrary, we see that the proposed GraphWalker (column 4) is robust to such challenging cases and can generate graphs that are very close to the ground truth (column 5).

Computational Efficiency. Diffusion models can be more computationally intensive compared to appearance-based methods. In Table 2, we show the wall-clock inference time per input trajectory (averaged over 1000 randomly selected trajectories, measured on a single NVIDIA 4090 GPU). We also compute the FLOPS of both the VAE and DiT of our approach and also the diffusion-based Graphusion.

5 RelatedWork

Road Network Generation. Early road network generation methods rely on heuristic algorithms [Biagioni and Eriksson, 2012; Stanojevic et al., 2018; Gao et al., 2022; He et al., 2018]. They are mainly based on trajectory data and human flow data. Benefit from the advancement in deep learning, many methods adopt CNNs to infer road networks from aerial imagery, such as SOC-RoadNet [Zhou et al., 2022], CasNet [Cheng et al., 2017] and SII-Net [Tao et al.,

2019]. RoadTracer [Bastani et al., 2018] proposed an iterative graph construction algorithm, which is capable of accurately deriving the graph from the semantic segmentation output guided by a CNN decision function. Some other methods argue that adopting both remote sensing images and trajectory data makes the solution more robust, including DuARE [Yang et al., 2022], TR2RM [Yang et al., 2024b] and DFDRUnet [Li et al., 2024]. Moreover, some methods leverage power content generation tools such as generative adversarial network (GAN) [Goodfellow et al., 2014; Yao et al., 2024; Li et al., 2022] and diffusion models [Gu et al., 2024].

Graph Generation. Graph generation methods are popular in the chemistry and biology fields, where they are used to predict protein and molecular structures. They can be categorized into five classes based on the generative model used. The auto-regressive methods, including GraphRNN [You et al., 2018] and MolecularRNN [Popova et al., 2019]. The VAE-based methods, such as GraphVAE [Simonovsky and Komodakis, 2018], CGVAE [Liu et al., 2019] and Graphite [Grover et al., 2019]. The normalizing flow based methods, including MoFlow [Zang and Wang, 2020] and GraphDF [Luo et al., 2021]. The GAN based methods, such as GraphGAN [Wang et al., 2017] and Mol-CycleGAN [Maziarka et al., 2020]. Finally, the diffusion model based methods including GraphGDP [Huang et al., 2022], EDP-GNN [Niu et al., 2020] and Graphusion [Yang et al., 2024a].

6 Conclusion

This paper proposes GraphWalker, a novel end-to-end trainable framework for high-fidelity road network generation from noisy trajectories. We draw from the powerful latent diffusion models, and design a bespoke cross-domain VAE, W2G-VAE, as well as a novel diffusion transformer T2WDiT, that can iteratively recover the road network graph via denoising walk embeddings in a latent space with the input trajectories as conditions. Extensive experiments with realworld trajectories collected from three different cities show that GraphWalker consistently outperforms both appearancebased and state-of-the-art diffusion-based baselines, and is more robust under different settings such as heterogenous area sizes, limited input data and challenging road topologies.