[Day 161] Learning about GANs' use in generating OD demand matrix

 Hello :)
Today is Day 161!

A quick summary of today:

• explored how Generative Adversarial Networks can be used for OD demand matrix generation

• found that the original graph attention network has limitations and read the paper for GATv2

First paper - A GAN framework-based dynamic multi-graph convolutional network for origin–destination-based ride-hailing demand prediction [ScienceDirect]

Introduction

OD-based prediction focuses on estimating travel demand between specific origin and destination regions, which is useful for understanding inter-regional travel patterns. This approach requires consideration of complex spatio-temporal correlations, making it more challenging than region-level prediction. Although some progress has been made in OD-level prediction, several key issues remain:

• Practical OD Demand Forecasting: Previous studies often only consider relationships between OD pairs, rather than between OD regions. Accurate OD demand matrices and inter-regional relationships need to be developed.
• Dynamic and Directed Topology Modelling: Current models use static and undirected graphs, which fail to capture the time-varying and directed nature of OD demand. Dynamic and directed OD graphs are needed for better spatial dependence modelling.
• Addressing Matrix Sparsity: OD demand matrices often contain more zeros than non-zeros, reducing prediction accuracy. A suitable model structure is required to address this sparsity.

To tackle these issues, the authors propose the Dynamic Multi-Graph Convolutional Network with Generative Adversarial Network (DMGC-GAN). This model captures directed and time-changing correlations in dynamic OD graphs. Key components include:

• Dynamic OD Graphs: Represent irregular regions as nodes with weighted matrices for different inter-regional relationships.
• Temporal Multi-Graph Convolutional Network (TMGCN) Layer: Integrates various spatial-temporal information from different dynamic OD graphs, such as static neighbourhood relationships, dynamic mutual attraction, and mobility association modes.
• GAN Structure: Helps overcome the high sparsity of OD demand matrices.

Related work

Graph convolutional network

To adapt CNNs for urban demand forecasting, cities are often partitioned into rectangular grids, which do not accurately reflect the urban road network. CNNs are also limited in capturing semantic correlations between geographically distant regions with similar functions. Hexagon-based CNNs (H-CNN) improve precision but still fail to account for actual road layouts. Since passengers' demand data is non-Euclidean, traditional CNNs are inadequate for ride-hailing demand forecasting.

Graph Convolutional Networks (GCNs) have been introduced in traffic fields to address these limitations, such as traffic flow and speed forecasting. The Temporal Graph Convolutional Network (TGCN) models roads as graph nodes to capture spatial and temporal dependencies. The Spatial-Temporal Multi-Graph Convolutional Network (ST-MGCN) captures dependencies like geographical distance, functional similarity, and traffic connectivity, using grouped lower and higher layer GCNs for generalised feature extraction. The Multi-Community Spatial-Temporal Graph Convolutional Network (MC_STGCN) incorporates GRU for temporal relationships and various graph structures to model spatial dependencies. The Multiple Spatio-Temporal Information Fusion Networks (MSTIF-Net) combines GCN and Variational Auto-Encoders (VAE) for dynamic spatio-temporal characteristics. Additionally, the Temporal Attention Graph Convolutional Network (TAGCN) describes spatial and temporal relationships with a temporal attention mechanism.

OD-level demand forecasting

While region-based demand forecasting is well-studied, OD-based demand prediction is less explored. OD-based prediction is valuable for understanding travel demand and inter-regional relationships. Existing models use static and undirected OD graphs based on geographic proximity or passenger demand, but these fail to capture dynamic and directed dependencies over time.

Recent efforts, like LSTM and CNN-based encoder-decoder structures, still struggle with dynamic graphs. The Dynamic Node-Edge Attention Network (DNEAT) addresses evolving road network topologies in dynamic OD graphs.

Motivated by these limitations, the authors propose a novel neural network to efficiently capture spatio-temporal correlations in OD demand data for better OD-based prediction.

Methodology

OD graph, OD demand intensity (split into hourly trends, daily cycle and weekly cycle)

Problem

Given a dynamic topology and the sequence of OD demand intensity at time t, the OD-based demand prediction problem is to determine the OD demand intensity and t+1.

Framework

TMGCN cell

Training algorithm

Experiments

Dataset

Provided by NY taxi and limousine commission

Example demand distributions between regions 4-68 and 4-74

Evaluation metrics

RMSE, MAE, MAPE, R^2

Baselines

HA, MLP, LSTM, GRU, ConvLSTM, GCN, TGCN, TMGCN

Results

Example of OD demand prediction

Second paper - Ride-hailing origin-destination demand prediction with spatiotemporal information fusion [link]

Introduction

Traditional methods for OD demand prediction often rely on static models and linear approximations, which fail to account for dynamic and complex traffic conditions. Recent approaches employ machine learning techniques, such as clustering and neural networks, but they still face limitations in handling high-dimensional, sparse data and incorporating spatial-temporal dependencies effectively.

Deep learning, particularly generative adversarial networks (GANs), offers advanced capabilities for capturing complex spatial-temporal patterns in traffic data. Various GAN models, including conditional GANs (CGANs) and Wasserstein GANs (WGANs), have shown promise in traffic prediction tasks.

This paper proposes a novel approach using a CGAN with a Wasserstein divergence objective (CWGAN-div) for predicting ride-sourcing OD demand. This model integrates the strengths of CGAN and WGAN-div to ensure stable training and accurate prediction by capturing both internal and external spatial-temporal correlations.

Methodology

Results

Third paper - GATv2 [link]

Introduction

Graph Attention Networks (GATs) are a widely used (and SoTA) type of Graph Neural Networks (GNNs) known for their effectiveness in learning representations from graphs. However, we found that GATs employ a limited form of attention where the ranking of attention scores is fixed and not dependent on the query node. We call this restricted attention "static" and contrast it with a more flexible "dynamic" attention. Due to this limitation, GATs struggle with certain graph problems, as demonstrated in controlled experiments where they fail to fit the training data. To address this, we propose GATv2, a modified version that utilizes dynamic attention, making it more expressive than traditional GATs - in GATv2, every node can attend to any other node.

In GAT, the standard averaging or max-pooling aggregation technique is standardised and every node updates its representation by attending to its neighbours. This way the node can compute a weighted average of its neighbours, and (softly) select which are the most relevant.

The expressive power of graph attention mechanisms

Theorems

Evaluation

Discussion

Which graph attention mechanism should I use?

'We believe that the more complex the interactions between nodes are – the more benefit a GNN can take from theoretically stronger graph attention mechanisms such as GATv2'.

The author of GAT, said on twitter that GAT was designed to work in the 'easy-to-overfit' datasets of that time.

On another note ~

Today I also re-read my notes in obsidian to get an idea again of what I have read and note down any potential ideas for research. I read lots of papers and I have an idea of what direction I want to go to, but still I am keeping my options open as I want to read a few more papers and explore my current ideas.

The 'reference' graph does not make much sense now, but it is nice to see it grow.

That is all for today!

See you tomorrow :)