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
Fristly, about the Glaswegian dataset
The process of adding data to huggingface is faster now, so it is going great. We are up to ~18 mins.
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 centralized 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: 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 the 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 ones are HA, ARMA, MA, ARIMA, and the Kalman filtering model. However, such models lack 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 selection 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 modeling, time-dependent modeling, and other factors.
Spatial topology construction
Raster data
- For CNNs, the area of interest is partitioned into non-overlapping 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 a 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.
- 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 its nature. There are two construction methods:
- Discrete-time dynamic graphs (DTDG): 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, 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.
Challenge 2: Spatial-temporal correlation
- Spatiotemporal correlation means that each node can influence its neighbors 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.
**Challenge 3: Differenti
ation 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.
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.
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.
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 organized by Stanford AI professional certificate students. I uploaded the PPT PDF to the GitHub repo.
That is all for today!
See you tomorrow :)