LINK: Lightweight and Inductive Node-to-Node Propagation Rule Learning for Traffic Kriging

You Shang, Yu-Kwan Ching, Weifeng Su, Guanyao Li, Ruiyuan Li, Gary Shueng-Han ChanarXiv 2026 · arXiv

TL;DR

LINK is a new lightweight framework for "traffic kriging"—estimating traffic conditions at locations with zero historical data. By shifting from standard Graph Neural Network (GNN) neighborhood aggregation to explicitly learning a shared node-to-node propagation rule, LINK achieves a 54.7% reduction in error while being significantly faster and more memory-efficient than state-of-the-art baselines.

What Problem Does This Paper Address?

In intelligent transportation, we often need a complete picture of city traffic, but sensors are expensive and only cover a fraction of the road network. Traffic Kriging is the task of reconstructing traffic time series at these "blind spots" (unobserved nodes) using data from nearby sensors (observed nodes).

This is harder than typical traffic forecasting or data imputation because the target locations have no historical data to learn from. Existing GNN-based methods struggle here for two reasons:

  1. Implicit Modeling: They rely on "neighborhood aggregation," which updates node representations but doesn't explicitly model how traffic state actually flows from one point to another.
  2. Fixed-Depth Propagation: Standard GNNs use a fixed number of layers (hops) for every node. In reality, an unobserved road might be one hop away from a sensor or ten, making a "one-size-fits-all" depth inefficient and inaccurate.

Methods

The authors introduce LINK (Lightweight and Inductive Node-to-node propagation rule learning), which features three main innovations:

  • Adaptive Subgraph Extraction: Instead of processing the whole graph, LINK uses a Breadth-First Search (BFS) for each target node to find the nearest "boundary" sensors. This creates a focal-specific subgraph, ensuring information only propagates from relevant, observed locations.
  • Shared Propagation Rule ($P_\theta$): Rather than learning unique node embeddings, LINK learns a single, transferable rule that describes how traffic state transforms across any road segment. This rule is conditioned on road metadata (like road type and direction), allowing it to adapt to different contexts.
  • Spectral Propagation Network (SPN): LINK operates in two domains:
  • Spectral Domain: It uses a Fast Fourier Transform (FFT) to extract low-frequency "trends" (the slow-moving patterns of traffic).
  • Time Domain: It uses a "Residual Refinement" module to handle high-frequency "residuals" (sudden, short-term fluctuations).

Datasets

The authors argue that existing benchmarks lack the rich metadata needed for realistic kriging. They introduce TraffiKrig, a benchmark derived from the TraffiDent dataset.

  • Structure: Four regional subsets (381 to 1,151 nodes) in California.
  • Metadata: Includes road type (mainline, ramp, HOV), travel direction, and freeway identity.
  • Comparison: They also evaluate against standard GNN baselines like GCN, GIN, and specialized kriging models like IGNNK and KITS.

Key Insights and Ideas

  • Rules over Representations: The "Aha!" moment is that for kriging, the transition is more important than the node. By learning a shared rule ($P_\theta$), the model becomes truly inductive—you can train it in one city and apply it to another (zero-shot) because the "physics" of traffic flow remains similar.
  • Efficiency through Sparsity: By using adaptive subgraphs, LINK avoids the "over-smoothing" and computational waste of deep GNNs. It only does the work necessary to reach the nearest sensors.
  • The Power of Metadata: The paper shows that simply adding road metadata to existing baselines can reduce their error by over 40%. However, LINK’s architecture is uniquely designed to exploit this context through its shared propagation rule.

Key Results

  • Accuracy: LINK achieved an average 54.7% reduction in Mean Absolute Error (MAE) compared to the strongest baselines across the TraffiKrig subsets.
  • Efficiency:
    • Training: 66.5% faster than the fastest competing method.
  • Inference: 86.6% faster (only 0.084 ms per sample).
  • Memory: Used significantly less GPU memory (190 MiB vs. ~300-17,000 MiB for baselines).
  • Zero-Shot Transfer: When trained on one region and tested on a completely unseen region, LINK still outperformed baselines that were trained directly on that target region.

Limitations and Future Work

  • Static vs. Dynamic: The current model relies on static road metadata. Future work could incorporate dynamic context, such as weather or special events, which might alter the propagation rules in real-time.
  • Sensor Density: While LINK handles varying distances well, its performance still depends on the underlying sensor density. In extremely sparse networks, the "adaptive subgraphs" might become too large, potentially impacting efficiency.
  • Directed Graphs: The current BFS approach assumes a directed graph. While this fits road networks well, extending the logic to more complex, multi-modal transport graphs remains an open area.

Summary updated

Abstract

Spatio-temporal traffic kriging aims to reconstruct traffic time series at unobserved locations with no historical traffic observations by leveraging spatial and temporal dependencies across the road network. Existing Graph Neural Network (GNN)-based approaches primarily rely on neighborhood aggregation to capture spatial dependencies, thereby modeling traffic interactions implicitly and making it difficult to accurately recover traffic magnitudes at locations without historical observations. To address this limitation, we propose LINK, a Lightweight and Inductive Node-to-node propagation rule learning paradigm for traffic Kriging. LINK introduces three key designs: 1) a propagation-centric traffic kriging paradigm that explicitly learns a shared node-to-node transition rule; 2) a context-aware Spectral Propagation Network that performs traffic-state propagation in both the spectral and time domains; and 3) TraffiKrig, a realistic traffic kriging benchmark that preserves heterogeneous road-segment characteristics and road-specific metadata while enabling systematic comparison of representative kriging methods under a unified metadata-enhanced setting. Extensive experiments demonstrate that LINK achieves strong reconstruction accuracy and computational efficiency. Compared with the strongest baseline on each subset, LINK achieves an average MAE reduction of 54.7% over original baselines. LINK also achieves substantial efficiency improvements, reducing training time by 66.5% and inference time by 86.6% compared with the fastest competing methods. Zero-shot experiments further demonstrate the transferability of the learned propagation rule across regions.
BibTeX
@misc{shang2026link,
  author = {You Shang and Yu-Kwan Ching and Weifeng Su and Guanyao Li and Ruiyuan Li and Gary Shueng-Han Chan},
  title = {{LINK: Lightweight and Inductive Node-to-Node Propagation Rule Learning for Traffic Kriging}},
  year = {2026},
  eprint = {2611.20521},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.20521},
}
Figure