When, Where, What: Structural Guarantees for Travel Time Prediction on Temporal Graphs

Accurate traversal (travel) time distribution estimation on temporal graphs benefits from satisfying six structural properties: when (ordering, flexibility), where (composition with prefix equivariance), and what (non-Markov, snapshot). No existing temporal graph learning method jointly satisfies these properties. We propose PATH-HAZ, a discrete-time hazard model that provides guarantees of all six requirements. It composes per-step PMFs via dynamic programming for spatially consistent predictions across shared paths, while cross-attention over historical graph snapshots encodes confounder-induced dependencies between non-adjacent steps on the path. Evaluated on simulated logistics and real-world high-speed rail data, PATH-HAZ surpasses both point-estimate (19.3% RMSE improvement) and probabilistic baselines (56% CRPS reduction), while also allowing for detailed structural explainability of delays.