High-Fidelity Road Network Generation with Latent Diffusion Models

Jinming Wang, Hongkai Wen, Geyong Min, Man LuoIJCAI 2025 · DOI · OpenReview

TL;DR

This paper introduces GraphWalker, a novel end-to-end framework for generating high-fidelity road networks from noisy GPS trajectories. By leveraging latent diffusion models and a custom Walk-to-Graph Variational Autoencoder, GraphWalker effectively reconstructs complex road structures, outperforming existing methods, especially in challenging scenarios with sparse data or intricate road topologies.

What Problem Does This Paper Address?

Maintaining accurate and up-to-date road network information is crucial for modern cities, but it's a persistent challenge, especially in rapidly developing areas. While crowdsourced GPS trajectories offer a rich data source, their inherent noise, irregular sampling, and sparsity make direct road network extraction difficult. Traditional methods often rely on rendering trajectories as 2D density maps and then applying heuristic algorithms, which can lead to information loss and poor performance, particularly with sparse data or complex features like flyovers. This paper aims to bridge this gap by proposing a more robust and accurate method for generating road network graphs directly from these noisy trajectory datasets.

Methods

GraphWalker tackles the problem by reframing it as an inverse problem: instead of directly generating a graph from trajectories, it first learns to generate trajectories from a known graph. This insight leads to a two-stage approach:

  1. Trajectories to Walk Embeddings: A custom Walk-to-Graph Variational Autoencoder (W2G-VAE) is trained. This VAE learns a latent space where "walks" (sequences of road segments traversed by a trajectory) can be represented. The encoder maps walks to this latent space, and the decoder reconstructs walks from latent representations.
  2. Graph Generation from Walk Embeddings: A novel Trajectory-to-Walk Diffusion Transformer (T2W-DiT) is introduced. This model acts as a latent diffusion model that takes input trajectories as conditions. It gradually denoises samples in the latent space to generate embeddings of the corresponding walks. These generated walk embeddings are then decoded by the W2G-VAE into actual walks, which are finally assembled into the complete road network graph.

Key novelties include the T2W-DiT, which uses a bespoke Negative Euclidean Self-attention (NESA) mechanism instead of standard Multi-head Self-Attention for better handling of trajectory correlations, and an augmented W2G-VAE decoder that directly reconstructs the graph from walk embeddings, rather than just individual walks.

Datasets

The authors evaluate GraphWalker on real-world trajectory datasets collected from three cities: Tokyo (TYO), Shanghai (SHA), and Las Vegas (LAS). To ensure fair comparison and control over data quality, they synthesize trajectories based on existing OpenStreetMap road network data and aerial imagery. This approach allows for trajectories with diverse motion patterns and covers areas within specified bounding boxes.

Key Insights and Ideas

  • Inverse Problem Framing: The core insight is that understanding how trajectories are generated from road networks can inform how to recover road networks from trajectories. This leads to the concept of "walks" as intermediate representations.
  • Latent Diffusion for Walks: Applying latent diffusion models not directly to the graph, but to the latent representations of walks, proves to be a powerful strategy for handling noisy and sparse trajectory data.
  • NESA for Trajectory Correlation: The custom NESA attention mechanism is crucial for capturing the non-trivial spatio-temporal correlations within trajectories, which is a significant improvement over standard attention.
  • End-to-End Graph Reconstruction: The W2G-VAE's augmented decoder that directly outputs the graph from walk embeddings streamlines the process and avoids separate heuristic steps.

Key Results

  • Superior Performance: GraphWalker consistently outperforms appearance-based methods (TR2RM, DF-DRUNet, SmallMap) and a diffusion-based baseline (Graphusion) across various metrics (Hungarian MAE/MSE, Chamfer MAE/MSE, Wasserstein Distance of Edge Length Distributions).
  • Robustness to Generalization: The model shows significant improvements (up to 33%) when tested on cities different from the training city, indicating strong generalization capabilities.
  • Scalability with Area Size: GraphWalker's performance improves with larger area sizes, suggesting it effectively leverages available data.
  • Resilience to Limited Data: The approach maintains strong performance even with a limited number of input trajectories, outperforming baselines that degrade significantly.
  • Handling Challenging Topologies: Qualitative results demonstrate GraphWalker's ability to accurately reconstruct complex road structures like multi-branch junctions, overpasses/underpasses, and self-loops, where other methods struggle.

Limitations and Future Work

  • Computational Cost: While effective, diffusion models can be computationally intensive. Table 2 shows GraphWalker's inference time per trajectory is higher than some baselines, though comparable to Graphusion.
  • Future Work: The paper implicitly suggests that further optimization of the diffusion process and VAE architecture could lead to even greater efficiency and accuracy. The robustness shown across different cities and data conditions also opens avenues for deployment in real-world, dynamic urban environments.

Summary updated

Abstract

Road networks are the vein of modern cities. Yet, maintaining up-to-date and accurate road network information is a persistent challenge, especially in areas with rapid urban changes or limited surveying resources. Crowdsourced trajectories, e.g., from GPS records collected by mobile devices and vehicles, have emerged as a powerful data source for continuously mapping the urban areas. However, the inherent noise, irregular and often sparse sampling rates, and the vast variability in movement patterns make the problem of road network generation from trajectories a non-trivial task. Existing methods often approach this from an appearance-based perspective: they typically render trajectories as 2D density maps and then employ heuristic algorithms to extract road networks - leading to inevitable information loss and thus poor performance especially when trajectories are sparse or ambiguities present, e.g. flyovers. In this paper, we propose a novel approach, called GraphWalker, to generate high-fidelity road network graphs from raw trajectories in an end-to-end manner. We achieve this by designing a bespoke latent diffusion transformer T2W-DiT, which treats input trajectories as generation conditions, and gradually denoises samples from a latent space to obtain the corresponding walks on the underlying road network graph - then assemble them together as the final road network. Extensive experiments on multiple datasets demonstrate the proposed GraphWalker can effectively generate high quality road networks from noisy and sparse trajectories, showcasing significant improvements over state-of-the-art.
BibTeX
@inproceedings{wang2025high,
  author = {Jinming Wang and Hongkai Wen and Geyong Min and Man Luo},
  title = {{High-Fidelity Road Network Generation with Latent Diffusion Models}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/702},
}
Figure