[Day 151] Reading more about taxi OD matrix prediction architectures + more Scottish dataset audio included
Hello :)
Today is Day 151!
A quick summary of today:- my collaborator recorder more audio and the Scottish (Glaswegian) dataset is growing
- read more papers related to OD (origin-destination) matrix prediction for taxis
Secondly, about the papers from today
First paper is GNN for Traffic Forecasting - A survey
Problems
Traffic flow
Traffic flow is the number of vehicles that pass through a spatial unit, such as a road segment or traffic sensor point in a given time slot. Three types are considered: road-level, region-level and station-level.
Traffic speed
This is the average speed of vehicles passing through a spatial unit in a given time slot. Traffic speed problems are categorized into road-level and region-level issues, including travel time and congestion predictions. Traffic congestion prediction aids in optimizing road conditions and vehicle flow. Challenges vary between urban roads and freeways, with urban roads posing more complexities due to intricate connection patterns, speed limit variations, and spatial dependencies.
Traffic demand
Refers to the potential demand for travel. An example of demand is the amount of requests sent through taxi hiring apps (whether all the demand is met is different).
Graph Neural Networks
GNNs are currently the SoTA in traffic forecasting. Variations include recurrent GNNs, convolutional GNNs, graph autoencoders, and spatiotemporal GNNs, the last being used in this case since traffic forecasting is a spatiotemporal problem.
Open data and Source codes
Open data
Three types - graph-related data(transportation network data), historical traffic data(historical traffic state records), and external data(weather and calendar data). Links to traffic sensor data, taxi data, ride-hailing data, bike data, and subway data used in surveyed studies.
Open source codes
Links available to repositories.
Challenges
Heterogeneous data
- data quality
- incomplete data
- traffic anomalies data is difficult to collect to train DL models
- data privacy
Multi-task performance
- Multi-task frameworks in ITSs are needed to predict demand for multiple transportation modes simultaneously.
- Knowledge adaptation helps transfer information from data-rich to data-sparse sources for demand prediction.
- Challenges include data format incompatibilities and differing spatial or temporal patterns.
- Most surveyed models are designed for single-task training, though some handle multiple tasks like traffic flow and speed prediction on the same road segment.
- Multi-task forecasting is challenging in graph-based modeling due to different graph structures for different tasks (e.g., road-level vs. station-level problems).
- Some GNN-based models have tackled multi-task prediction (e.g., taxi departure/arrival flow, region-flow, transition-flow, crowd flows, OD flows).
- Existing attempts typically use the same graph with multiple outputs via feed forward layers.
- Significant further development is needed for GNN-based multi-task prediction, especially for tasks requiring multiple graph structures.
Practical implementation
- Data Bias: Existing GNN-based studies often use less than one year of data, introducing bias and limiting applicability to different times or places. Using longer traffic data requires updating underlying traffic infrastructures, increasing costs and complexity.
- Computation Scalability: GNNs face scalability issues with large-scale traffic network graphs, often leading to consideration of only subsets of nodes and edges. Solutions like graph partitioning and parallel computing have been proposed, but they provide only marginal performance improvements over simpler models.
- Infrastructure Changes: Real-world network graphs change with modifications in transportation infrastructure (e.g., new road segments, bus lines, points-of-interest). Static graph formulations are inadequate. Solutions include dynamic Laplacian matrix estimators and Data Adaptive Graph Generation (DAGG) modules to handle changing spatial dependencies.
Model interpretation
- Interpreting "black-box" machine learning or deep learning models, including GNNs, is a major criticism in traffic forecasting.
- Early-Phase Techniques: Techniques for explaining GNN predictions are still in the early stages of development and have not yet been applied to traffic forecasting.
- Severity in Transportation: The lack of model interpretation is particularly problematic in transportation due to complex and heterogeneous traffic data, making it harder to design interpretable models compared to simpler data formats like images and text.
- Current Efforts: Some efforts, such as incorporating state space models, have been made to improve model interpretation in traffic forecasting, but the issue remains largely unresolved, especially for GNN-based models.
Future directions
- creating a centralised data depository
- designing a transportation knowledge graph that leverages the traffic semantic information to improve forecasting performance
- using other techniques
- data augmentation
- transfer learning
- meta learning
- Generative Adversarial Networks (GANs)
- AutoML
- Bayesian Networks
Applications in real-world ITS systems
Most GNN-based studies are based on simulations with historical traffic data, and not used in real-world applications to test their validity.
Second paper is Taxi origin and destination demand prediction based on deep learning: a review
Introduction
When it comes to graphs and taxi demand prediction - node-level predictions are for number of trips for that particular node(region), while edge-level predictions are for demand relationships between two nodes(regions).
Mathematical statistical methods
Statistical models are based on historical and time series data. The most widely applied once are HA, ARMA, MA, ARIMA, and the Kalman filtering model. However, such models lack in the ability to work with high dimensional, spatiotemporal data such as taxi data.
Traditional machine learning methods
Common ones are linear regression, SVM, decision trees, RF, artificial neural networks. In these models feature selections directly influences their accuracy, and while they improve upon the statistical methods, they do not effectively solve the nonlinear correlation of complex multidimensional data.
Deep learning background
CNN, RNN, GCN are commonly used for extracting temporal and spatial information. Some papers also use multi-task learning, residual networks and other methods to get better accuracy. To make demand and OD matrix predictions, historical regional taxi data with both temporal and spatial information is needed. Below, the review focuses on four areas: spatial topology construction, spatial-dependent modelling, time-dependent modelling, and other factors.
Spatial topology construction
Different DL methods require different spatial topologically structured data. CNNs process raster data, while GCNs - graph data.
Raster data
For CNNs, the area of interest is partitioned into non-overlapping n amount of grids of predetermined size. However, transportation data has spatiotemporal attributes and non-Euclidean structural characteristics which renders the grid structure powerless. In addition, if the raster data is small, the area of interest may be split and result in higher data volume that increases the difficulty of prediction. If the raster is too large, then it might be harder to extract demand features and we will end up with reduction in accuracy.
Graph
For GCNs, the travel demand data is transformed into images (non-Euclidean spatial data). There are two graph structures: static and dynamic graphs. Firstly, the graph is constructed with the OD pairs serving as the nodes, and the features of the nodes and edges are included in the prediction network model.
For GCNs, the travel demand data is transformed into images (non-Euclidean spatial data). There are two graph structures: static and dynamic graphs. Firstly, the graph is constructed with the OD pairs serving as the nodes, and the features of the nodes and edges are included in the prediction network model.
- Static graph The model assumes that the graph structure is constant. To construct the OD matrix we can use methods like distance measures or Gaussian kernels. Otherwise we can construct a binary adjacency matrix using information about which nodes are connected. Studies have also looked into adding auxiliary features like connectivity maps, semantic function maps, weather, distance maps, traffic connectivity maps.
- Dynamic graph There are two types: (i) nodes and edges continually change over time, and (ii) node and edge properties vary over time. Traditional graph representation learning frameworks generate static representations and overlook the dynamic nature of transportation data. Taxi demand data is spatiotemporal so dynamic graphs can better represent it's nature. There are two construction methods:
- discrete-time dynamic graphs (DTDG): it defines a fixed length r, and updates the embedding at each t time unit. The result is a dynamic adjacency matrix or a sequence of multiple graphs. Each graph is like a snapshot at a particular time slot. DTDG relies on the length r. A loose r can result in missing useful information like trends, whereas a more tight r can lead to extra noise. Therefore the DTDG method suffers from loss of information due to the fixed (discrete) segmentation of the OD stream information.
- continuous time dynamic graphs (CTDG): here the node representation is updated based on event data which can include type of event, the location, and its time. An example of an OD request can be described by a tuple (e, l ,t), where e is the type of OD request, l is the location, and t is the timestamp. This method can only capture the time dependence of finite time steps. Also, due to the spatiotemporal demand imbalance, the OD matrix can be very sparse in some regions.
Spatial dependency
Traditional CNNs work on Euclidean structured data and lack the ability to handle the opposite. Transportation networks have spatiotemporal attributes which are well-handled by GCNs.
Temporal dependency
Three main architectures used - RNNs, Transformer, and TCN (Temporal Convolutional Network)
Other factors
External characteristics
Taxi demand can be affected by various auxiliary factors like weather.
Model helper methods
Papers have used methods like attention, multi-task learning, and ResNet networks
Challenges
Challenge 1: Representation of dynamic correlations in OD flow
It is common for the relationship between two regions to change over time (peak vs non-peak hours). Static graphs cannot capture this, so research has looked into different ways of using dynamic graphs for that purpose. papers to read
Challenge 2: Spatial-temporal correlation
Spatiotemporal correlation means that each node can influence its neighbours at the next time slot. Spatiotemporal heterogeneity comes from the fact that the OD flow is different in cases like morning, evening, downtown, or city outskirts. At the time of writing, using two independent components to capture both spatial and temporal dependencies in a chained prediction often fails to capture this correlation and heterogeneity. papers to read
Challenge 3: Differentiation of different semantics of origin and destination
In complex and irregular transportation networks, passenger demand between OD pairs can be both geographically and semantically correlated, with directed and bidirectional relationships. Modeling demand separately for origins and destinations ignores the flow relationship between OD pairs and lacks practical application. Moreover, considering only the distance and flow information between grids, without distinguishing between origin and destination, overlooks the directionality of OD flows and the varying attraction relationships at different times. papers to read
Challenge 4: Time window selection
The predominant method for predicting OD flows is the discrete dynamic graph approach, which aggregates historical transactions into demand snapshots within fixed time windows. This method results in disconnected OD flows and lacks rigor due to the arbitrary choice of time granularity, which can introduce noise or overlook important information. Continuous-time dynamic graph methods offer a solution by maintaining dynamic state vectors for traffic nodes, but they face challenges in updating and maintaining representations for numerous continuous-time nodes. Recent advancements include using a spatiotemporal attention network and developing a continuous-time dynamic graph framework to improve prediction accuracy and capture complex time patterns. papers to read
Challenge 5: Data sparseness problem solving
The time sequence associated with each OD pair involves intricate spatial dependencies. Discrete dynamic graph-based prediction methods often result in information loss and a high frequency of zero values. Continuous-time dynamic graph-based prediction methods face challenges due to sparse data for certain OD pairs, which is exacerbated by the quadratic increase in predicted OD demand. papers to read
Going forward
Spatiotemporal dynamic correlation
- An individual node is affected by interactions with its surroundings, and randomness of the network itself. Currently this is tackled using attention mechanisms, but this can be explored further
External information addition
- External factors like holidays, weather, points of interest, large events, and traffic accidents can also significantly affect taxi demand. Introducing such auxiliary information is rare in current research.
Regional division
- Current papers split the region of interest into a set of grids or traffic zones. But this method can lack in understanding all relationships between the data, so a more rigorous approach can be developed.
OD data sparseness and data overload
- Data sparsity affects the model, and future research can look into how to handle such sparsity in the OD matrix.
Technical related issues
- Most papers use RNNs, GCNs, a few use GATs and GAEs. Future research can look into how we can use GNNs for OD demand prediction problems better
On another note, tonight I have to stay up till 2am because I signed up to give a short ppt on text2chart (which I created some time ago) in a project group organised by Stanford AI professional certificate students. I uploaded the ppt pdf to the github repo.
That is all for today!
See you tomorrow :)
