FRIGATE: Frugal Spatio-temporal Forecasting on Road Networks
Mridul Gupta Hariprasad Kodamana Sayan Ranu
Modelling spatio-temporal processes on road networks is a task of growing
importance. While significant progress has been made on developing
spatio-temporal graph neural networks (Gnns), existing works are built upon
three assumptions that are not practical on real-world road networks. First,
they assume sensing on every node of a road network. In reality, due to
budget-constraints or sensor failures, all locations (nodes) may not be
equipped with sensors. Second, they assume that sensing history is available at
all installed sensors. This is unrealistic as well due to sensor failures, loss
of packets during communication, etc. Finally, there is an assumption of static
road networks. Connectivity within networks change due to road closures,
constructions of new roads, etc. In this work, we develop FRIGATE to address
all these shortcomings. FRIGATE is powered by a spatio-temporal Gnn that
integrates positional, topological, and temporal information into rich
inductive node representations. The joint fusion of this diverse information is
made feasible through a novel combination of gated Lipschitz embeddings with
Lstms. We prove that the proposed Gnn architecture is provably more expressive
than message-passing Gnns used in state-of-the-art algorithms. The higher
expressivity of FRIGATE naturally translates to superior empirical performance
conducted on real-world network-constrained traffic data. In addition, FRIGATE
is robust to frugal sensor deployment, changes in road network connectivity,
and temporal irregularity in sensing.