The traffic assignment problem (TAP) is one of the key components of transportation planning and operations. It is used to determine the traffic flow of each link of a transportation network for a given travel demand based on modeling the interactions among traveler route choices and the congestion that results from their travel over the network (Sheffi, 1985). Traditionally traffic assignment problems have been formulated as mathematical programs and solved based on user equilibrium (UE) principles (Wardrop, 1952). The UE solution relies on several assumptions on user behavior and knowledge such as: (i) drivers have perfect information and knowledge about the underlying network; (ii) drivers make rational choices when choosing a route; and (iii) all drivers are homogeneous (Kim et al., 2009). Although some of these assumptions may not hold in a real-world scenario, this approach has been providing the most reasonable solutions of the traffic assignment problem (Bar-Gera, 2002;Jafari et al., 2017;LeBlanc et al., 1975;Leurent et al., 2011;Mitradjieva and Lindberg, 2013;Tizghadam and Leon-garcia, 2007). One of the major issues with the static traffic assignment solution is that it assumes constant OD demand whereas traffic demand may significantly change over time, which makes it unsuitable to deploy for real world traffic scenario.
Static traffic assignment problem fails to capture traffic dynamics of a network, which motivated researchers to move towards dynamic traffic assignment methods. Dynamic traffic assignment (DTA) has become a state-of-the-art solution method to capture traffic network dynamics in a more realistic way. Numerous formulation and solution approaches have been introduced ranging from dynamic programming to variational inequality to simulation-based approaches (Abdelfatah and Mahmassani, 2002;Ban et al., 2008;Barthélemy and Carletti, 2017;Ben-Akiva et al., 2012;Boyles et al., 2006;Foytik et al., 2017;Friesz et al., 1989;He et al., 2010;Janson, 1989;Ji et al., 2016;Jiang et al., 2011aJiang et al., , 2011b;;Liu et al., 2007;Lo and Szeto, 2002;Mahmassani, 2001;Merchant and Nemhauser, 1978;Nie and Zhang, 2010;Peeta and Mahmassani, 1995;Peeta and Ziliaskopoulos, 2001;Primer, 2011;Ran et al., 1993;Shafiei et al., 2018;Ukkusuri et al., 2012;Waller et al., 2013;Watling and Hazelton, 2003). In a smaller model with less complexity, the DTA process works well in converging to a point of equilibrium. As the scale of a model grows in size, complexity, and congestion, the DTA procedure may become more difficult and require more computational time making it less suitable for a real-time deployment. Researchers are exploring to develop efficient solution methods for traffic assignment problem (TAP) which can be deployed for real-time transportation operation purposes.
Optimization of a transportation network largely depends on how accurately we capture the traffic dynamics of the network to forecast traffic in real-time. In particular, active traffic management requires a system that can estimate and forecast traffic in real-time. Over the last decade, traffic sensing technologies and emerging connected vehicles environment with added computational power has created an opportunity towards developing a data-driven approach as an alternative to traditional approaches of solving traffic assignment problems. Roadway sensors and devices provide us information on instantaneous travel time variation for different links indicating the congestion propagation throughout the network. Moreover, OD demand can be extracted from emerging data sources such as mobile phones, GPS observations, and social media posts. As such, we now have real-world O-D demand and traffic flow data available at large-scale over many days. However, one challenge is how to develop a data-driven framework at a network scale to learn the relationship between OD demand and link flows.
To overcome this challenge, in this paper, we present a novel data-driven approach of learning traffic flow patterns of a transportation network given that many instances of OD demand and traffic flow of the network are available. Instead of estimating traffic flow patterns assuming certain user behavior (e.g., user equilibrium), here we explore the idea of learning those patterns from large-scale training data by developing a neural network architecture. In particular, we use the Graph Convolutional Neural Networks (GCNN) which generalize traditional neural networks to work on structured graphs (Kipf and Welling, 2016). GCNNs utilize an adjacency matrix or a Laplacian matrix to represent the structure of a graph. Recently, several studies have utilized the concept of graph convolution to represent traffic network as a generalized graph for traffic state prediction (Cui et al., 2018a;Li et al., 2018). Moreover, Graph Convolution Neural Network has emerged as a new approach to overcome the challenge of high dimensionality when predicting travel demand for a large-scale network (Kim et al., 2019;Lin et al., 2018). 2.
With the emergence of big data and scalable data processing technologies data-driven modeling of complex system is gaining more attention. In transportation data-driven approaches have widely been applied to solve traffic prediction problems. These involve forecasting traffic speed (Cai et al., 2016;Ma et al., 2015;Polson and Sokolov, 2017;Rahman and Hasan, 2018), volume (Luo et al., 2019;Yasdi, 1999), and travel time (Billings and Jiann-Shiou, 2006;Chien and Kuchipudi, 2003;Elhenawy et al., 2014;Innamaa, 2005;Myung et al., 2011;Wu et al., 2004;Zhang and Haghani, 2015). Traditional data-driven methods such as Support vector regression (SVR), K-nearest Neighbor regression (KNN), Kalman Filtering (KF), Autoregressive Integrated Moving Average (ARIMA), Decision Tree, Artificial Neural Network (ANN), and Long Short Term Neural Network (LSTM) have been applied for shortterm traffic prediction over only one or multiple segments of highways, but not at the scale of a network (Billings and Jiann-Shiou, 2006;Cai et al., 2016;Chien and Kuchipudi, 2003;Deshpande and Bajaj, 2016;Elhenawy et al., 2014;Innamaa, 2005;Lee, 2009;Luo et al., 2019;Ma et al., 2015;Myung et al., 2011;Polson and Sokolov, 2017;Rahman and Hasan, 2018;Wu et al., 2004;Yu et al., 2016;Zhang and Haghani, 2015). Moreover, they do not consider network wide travel demand variations while predicting future traffic. As such, these approaches consider traffic prediction as a simple time series problem and predict the traffic state for a shorter time horizon (e.g., next 5 to 15 min). However, to estimate traffic for an entire network similar to the solution of a traffic assignment problem, we need to understand traffic evolution and congestion propagation for an entire road network rather than on a single road. Hence, researchers are investigating new data-driven methods to estimates network scale traffic which can be deployed for real-time transportation operation purposes.
Network level traffic prediction is more challenging due to the higher computational complexity required by the network topology. Such a problem requires (i) to capture the travel demand variation in the network, (ii) to capture the correlation of traffic in interconnected roads and mapping it in a spatial network (Polson and Sokolov, 2017), and (iii) to reflect drivers' route choice and associated congestion propagation inside the network. Convolutional Neural Network (CNN) methods are the initial attempt to model spatial and temporal correlation among the traffic states for network level traffic prediction. A few studies (Liu et al., 2017;Ma et al., 2017), have implemented the CNN and its variants such as CNN-LSTM model for network level traffic prediction. Although this model outperforms existing state-of-the-art datadriven models, in a CNN model, the traffic network is considered as an image and network information is extracted using a convolution filter, which is then fed into a fully connected layer or an LSTM layer to predict future traffic state. While traffic network is converted into an image, a certain amount of noise is included into the spatial relationships of traffic state causing erroneous results in prediction. Moreover, CNN cannot capture the long-term congestion propagation inside the network for long term traffic forecasting. Hence, it fails to capture the stochastic nature of traffic dynamics of a transportation network.
Recently, graph theory coupled with generalized neural network architecture has been utilized to model the dynamics between the structural properties and the functions of a network (Atwood and Towsley, 2015;Defferrard et al., 2016;Li et al., 2018;Sanchez-Gonzalez et al., 2020;Zhang et al., 2019;Zhou et al., 2018). Thereby, solving problems such as modeling physical systems, learning molecular fingerprints, predicting protein interface, and classifying diseases, which require that a model learns from graph-based inputs. Several studies have applied graph convolution-based approaches to learn spatiotemporal features of a transportation network (Atwood and Towsley, 2015;Cui et al., 2020Cui et al., , 2018bCui et al., , 2018a;;Guo et al., 2021Guo et al., , 2020Guo et al., , 2019;;Kim et al., 2019;Li et al., 2021Li et al., , 2018;;Lin et al., 2018;Peng et al., 2021Peng et al., , 2020;;Tang et al., 2020;Yu et al., 2018;Zhao et al., 2020). One of the main limitations of these studies is that they focused on learning traffic representation at a network scale rather than modeling the interaction between travel demand and traffic flow diffusion process. In other words-without including demand in the modeling framework-these methods disregard the fundamental concept of network flow modeling. Consequently, they fail to explain the working mechanism and support the reliability of these methods in network wide traffic flow estimation.
In this study, we develop a data-driven method to model the interaction between network wide travel demand variations and links flows. Thereby, we formulate the traffic assignment problem as data-driven learning problem. To solve this problem, we proposed a novel deep learning architecture adapting the concept of graph convolution.
In this section, first we formulate the data-driven traffic assignment problem. We then describe the Graph Convolutional Neural Network (GCNN) approach to model traffic flow propagation in the network.
In a transportation network, all nodes are connected, and each link is associated with information such as distance, speed limit, capacity etc. Here, we consider the transportation network as a weighted directed graph 𝒢(𝑣, ℰ, 𝑨 𝒘 ) where 𝑣 denotes the set of nodes and ℰ denotes the set of links between nodes (𝑖, 𝑗). 𝑨 𝒘 represents the connectivity between nodes as a weighted adjacency matrix, where weights are based on free flow travel time between any two nodes (𝑖, 𝑗), defined as follows:
where, 𝑡 𝑜 denotes the free flow travel time between the origin and the destination nodes. The proposed data-driven formulation of the traffic assignment problem aims to learn the flow patterns of a transportation network based on the network structure and the instances available on origin to destination (OD) travel demand and link flows (Fig. 1). Also, we have the information on network characteristics, such as location of each node with respect to other nodes, travel distance or free flow travel time between different nodes. From this information, we develop a data-driven method to estimate the link flows for given travel demands. During the estimation process, we also learn the traffic flow propagation from origin nodes toward destination nodes in a transportation network. Let, 𝑿 be the demand matrix for the transportation network 𝒢, where each element of a row indicates the travel demand between origin node (𝑖) and the destination node (𝑗).
The traffic assignment problem aims to learn a function ℱ(. ) that maps 𝑚 instances of
where, 𝑨 𝒘 indicates the weighted adjacency matrix, ℰ indicates the set of links of the network, and the vector 𝐹 𝑚 contains the link flows for each link of the network for a given OD demand (𝑿 𝒎 ). In this formulation, OD demands and network properties are input variables and link flows are the target variables.
here, 𝑓 1 (. ) denotes the nonlinear activation function for the convolution layer and 𝐇 𝟏 ∈ 𝑅 𝑁×𝑁 indicates the output from the graph convolution layer (1 st layer). From this layer, we obtain a convoluted demand matrix (𝐇 𝟏 ) representing the flow diffusion process (from origin nodes towards destination nodes) inside a network.
The convoluted demand matrix is then fed into the 2 nd layer of the GCNN, where we model traffic flow distribution from origin nodes towards adjacent links. In this layer, we create a simple neural network model with parameters 𝑊 𝑞 , which maps the convoluted demand matrix to a 𝑁 × 𝐸 dimensional space (same size as the link-node adjacency matrix) via matrix multiplication. In this way, the GCNN captures how flow diffusion process will assign traffic at different links of the network. We define the 2 nd layer of the model as follows, Finally, the distributed link flow matrix (𝒒) is transposed and fed into the output layer (see Fig. 2). Inside the transposed matrix (𝒒 𝑻 ∈ 𝑅 𝐸×𝑁 ) each row indicates the distributed link flows for a given link from all the origin nodes (𝑁). In the output layer, we assign a linear activation function (𝑓 3 (. )) with 𝑁 parameters, which aggregates the distributed link flows and outputs assigned traffic flow for a given link. We define the output layer as follows,
Here, 𝑓 3 denotes the linear activation function and H 3 (= 𝐹) ∈ 𝑅 𝐸 denotes the assigned traffic flows for all the links. From the output layer (H 3 ), we obtain link flows (𝐹) for a given OD demand (𝑿). So, the mathematical formulation of the GCNN model to estimate the link flows can be generalized as follows,
here, we select the hyperbolic tangent function 𝑡𝑎𝑛ℎ = 𝑒(𝑥)-𝑒(-𝑥) 𝑒(𝑥)+𝑒(-𝑥)
as the nonlinear activation function (𝑓 1 (. ) = 𝑓 2 (. ) = 𝑡𝑎𝑛ℎ) for the model.
In the following section, we describe the graph convolution operations and the parameters associated with graph convolution filter in details.
In a transportation network, the traffic flow pattern changes in response to the changes in travel demand. We represent this relationship via flow diffusion process from origin nodes towards destination nodes. To capture the stochastic nature of traffic flow variation at a network level, we consider the flow diffusion process by a random walk (random movement into adjacent neighboring nodes) in the network, 𝒢 with restart probability 𝛼 ∈ [0,1] and a state transition matrix 𝑫 ̅ 𝒘 -𝟏 𝑨 ̅ 𝒘 , where 𝑨 ̅ 𝒘 is the neighborhood matrix. In the neighborhood matrix, we add an identity matrix (𝑰) with the adjacency matrix (𝑨 𝒘 ). By adding the identity matrix, we create a self-loop for each node; for a given diffusion step it will capture the traffic flows having same node as origin and destination; in other words, it captures that the traffic flow remains in the origin node rather than diffusing from origin node to destination nodes. The neighborhood matrix 𝑨 ̅ 𝒘 is defined as,
The restart probability indicates the probability of starting of a random walk from node 𝑖. From the starting node such random walks take multiple steps (diffusion steps, 𝐾) to traverse the adjacent nodes until reaching the destination node 𝑗 . After many time steps, such diffusion process converges to a stationary distribution 𝓹 ∈ 𝑹 𝑵×𝑵 where 𝑖 th row of 𝓹 indicates the probability of flow diffusion from node 𝑖 towards 𝑗. The stationary distribution of the diffusion process can be represented as a weighted combination of infinite random walks on the graph (Teng, 2016) and be calculated in closed form,
where 𝑘 is the diffusion step. In practice, we can consider a finite number of diffusion steps and assign a trainable weight at each step. Similar diffusion processes have been adopted in previous research (Atwood and Towsley, 2015;Li et al., 2018). Based on that we can define the diffusion convolution over the network features (e.g., OD demand) 𝑋 as follows,
If we consider a 2-step diffusion process the above equation becomes,
where, Θ 0 and Θ 1 are the weights for each of the steps. While modeling the traffic flow pattern of transportation network, we can consider different number of diffusion steps to reach to a stationary distribution. However, as the network grows, this process becomes computationally expensive, since for a larger network the value for the diffusion step will be higher. Hence, such diffusion processes are only applicable for small scale networks, where flow diffusion occurs among the nearest neighbors (Li et al., 2018;Wang et al., 2020).
In our problem, we propose an alternative approach to represent the diffusion process.
Instead of selecting a value of the diffusion step (𝐾) and assigning parameter to each step, we assign parameters (𝚯 ) to locally learn the stationary probability distributions (probability matrix). So, while the training the model we estimate the parameters (𝚯 ) to learn the stationary probability distribution for the flow diffusion process. In other words, we obtain a routing matrix (Leon-Garcia and Tizghadam, 2009) which indicates the probability of diffusion of flow from node 𝑖 to node 𝑗 . The resulted diffusion convolution over the OD demand 𝑿 can be written as follows:
where, 𝚯 ∈ 𝑹 𝑵×𝑵 are the parameters of the convolution filter and 𝑫 ̅ 𝒘 -𝟏 𝑨 ̅ 𝒘 represents the transition probability matrix of the diffusion process. In the demand matrix 𝑿 , each row indicates travel demand from origin node 𝑖 to destination node 𝑗. So, when we perform the matrix multiplication between the operator Θ(𝑫 ̅ 𝒘 -𝟏 𝑨 ̅ 𝒘 ) and 𝑿, we obtain a convoluted feature matrix which captures the influence all OD pairs on link flows associated with origin node.
We can also model the diffusion process using a normalized Laplacian matrix.
Laplacian matrix better represents the structural properties of a network: the diagonal elements indicate the number of links originating at a given node, while the other elements indicate the connection between the origin and destination nodes. We define the Laplacian matrix as follows,
Normalizing the Laplacian matrix with degree matrix,
Now, the convolution over OD Demand matrix, 𝑿 can be written as follows,
where, 𝚯 ∈ 𝑹 𝑵×𝑵 are the parameters of the convolution filter, in other words, the coefficient matrix of the diffusion equation. During the training of deep learning model, we learn these parameters, which capture the flow diffusion process inside the network.
In this study, we focus on a probabilistic approach to model the flow diffusion by estimating transition probability matrix in two ways: using a random walk on adjacency matrix (equation 11) and Laplacian matrix (equation 14). We also compare these approaches with spectral graph convolutional neural network (Kipf and Welling, 2016) to learn traffic flow patterns. In a spectral graph convolutional approach, the convolutional filter is estimated by decomposing the adjacency matrix into its eigenvalues to represent different properties of the graph such as strength of a node, shortest path distance etc. In Appendix A, we provide the details of the concepts of spectral graph convolution to learn traffic flow patterns of a transportation network.
Although we propose this method for real-world traffic data, recent sensing technologies are not densely distributed yet to provide us data necessary to test this approach. Especially, for large networks the OD demand variations are not accessible to us, though such OD demand data exist due to the availability of mobile phone data (Alexander et al., 2015;Gundlegård et al., 2016). In addition, we seek to verify if the proposed approach works across different congested conditions and to measure the gaps between the actual traffic assignment solutions (i.e., analytical solutions) and the solutions obtained from the proposed neural network-based approach. Thus, to verify our approach, we generate synthetic traffic data based on user equilibrium (UE) solutions of static traffic assignments over two networks: Sioux Falls network (24 nodes and 76 links) and East Massachusetts Network (74 nodes and 258 links). It should be noted that our approach is not an alternative method to determine UE solutions. We use the UE based traffic assignment mainly to generate the data to verify our approach.
We obtained the OD demand and information on network characteristics from (Transportation Networks for Research Core Team, 2016). To generate multiple OD demand, we multiplied the OD demand matrix by random factors collected from a uniform distribution which varies 0.1 to 1.0. To test our approach in different scenarios, we consider three conditions:
uncongested, moderately congested, and fully congested. We generate 5,000 OD matrices for each condition and solve both networks using the Frank Wolfe algorithm to obtain user equilibrium traffic flows. To represent the prevailing traffic condition, we estimate the flow over capacity ratio. We assume that, for uncongested condition the flow-capacity ratio remains less than 0.5, for moderate condition the flow-capacity ratio varies between 0.4 and 0.8, and for uncongested condition, most of the cases the flow-capacity ratio is greater than 1.0. Fig. 4 shows the traffic flow variations for different links of Sioux Falls Network.
We implemented all the models using PyTorch ("PyTorch," 2016) library and train our model with dual NVIDIA Tesla V100 16GB PCIe GPU. Among the OD demand matrices, we use Performance metrics are defined as,
In Table 2, we report the performance of model on the test dataset. From the result, we find that both diffusion convolution and spectral convolution have similar accuracy, which is expected, since the spectral convolution operation is a special case of the diffusion convolution (Li et al., 2018). Based on performance metrics values, we can conclude that the proposed approaches are performing well to capture the flow diffusion. RMSE and MAE values provides aggregated information (average over all the outputs) on the performance of the models, hence, we also estimated 𝑅 2 score. As shown in Table 2, for each model the 𝑅 2 score is nearly 1, indicating the accuracy of the model to learn traffic flows in the network. We have also compared between actual and estimated link flows for a given OD demand. Fig. 4 and Fig. 5 show that for both Sioux Falls and East Massachusetts networks the difference between actual and estimated link flow is quite low. From the results, we observe that: (i) a neural network can capture the traffic assignment of a network without any prior knowledge on user behavior; (ii) we can achieve a better accuracy with an appropriate representation of the physical process of flow propagation.
To understand how well the model has learned the flow propagation for the given networks, we perform network topology analysis for the Sioux Falls network based on the betweenness centrality of the nodes and correlate them with the variations in trained parameters.
Betweenness centrality of a node indicates the fraction of the total number of shortest paths passing through that node (Brandes, 2001), which means a node with a higher value of betweenness centrality will have a higher number of shortest paths incidence on that particular node.
For a given OD demand matrix, to estimate betweenness centrality values we need to find the shortest paths for all pairs of origin-destination nodes at user equilibrium. However, the shortest path for a pair of origin and destination nodes depends on link travel times. In our analytical solutions (i.e., using Frank-Wolfe algorithm), we use BPR travel time function (see equation 17) to update link travel times. Based on the updated travel time, we find the shortest paths for assigning traffic to the network. These steps continue iteratively prior to reaching an user equilibrium solution, when travel time for all the used paths remain same for a given O-D pair. Hence, we use the same function to estimate user equilibrium travel time (𝑡 𝑖,𝑗 ) for all the links of the network.
where
indicates the flow-capacity ratio for a given link. Based on the estimated links' travel time from equilibrium link flows we find the shortest paths and estimate the betweenness centrality for all the nodes. We apply this approach on all the training OD demand samples.
Fig. 6 shows the distribution of betweenness centrality values for each node of the Sioux Falls Network across different traffic conditions. From the figures we find that except nodes 1, 2, 9, and 23, all the nodes have higher betweenness centrality values. Nodes 6,8,12,15,16,and 18 are the most critical for the Sioux Falls network. Moreover, we find that for congested condition (i.e., higher demand), variations of betweenness centrality values are higher compared to moderately and uncongested conditions. From the BPR function, we find that, if flow capacity ratio is less than 1.0, there will be no significant change in travel time with link flow variations or demand variations. However, when the flow capacity ratio is greater than 1.0, travel time will vary significantly with demand variations (i.e., link flow variations). Consequently, the shortest paths will change abruptly (i.e., shortest path are nor stable) leading to significant variations in betweenness centrality for all the nodes. In our case, for congested condition, the flow capacity ratio mostly varies from 1.0 to 2.0, thereby we observe a significant variation of betweenness centrality for different nodes.
Whereas for moderately congested and uncongested conditions, since the flow capacity ratio is mostly less than 1.0 so we, do not see significant variations in Betweenness Centrality.
In the proposed model, we assign parameters (𝑾 𝒒 ) to learn the flow propagation from nodes into adjacent neighboring links. We assume that the weight parameters associated with critical nodes will be higher and will vary significantly due to the changes in betweenness centrality of nodes. In other words, the weight parameter associated with a node is likely be correlated with the betweenness centrality value of the node.
In Fig. 7, we plot the weight distributions for node-link flow propagation inside Sioux Falls network at different traffic conditions. Since for uncongested and moderately congested conditions, the variations of betweenness centrality for different nodes are similar, the distributions of weight parameter (𝑊 𝑞 ) are also similar. In both cases, the critical nodes 6, 8, 15, and 16 have high positive weights (Fig. 7 (a) & (b)). For congested condition, the variation of betweenness centrality over different nodes are higher, thereby the weight parameters vary significantly compared to uncongested and moderately conditions (Fig. 7(c)). In a congested condition, the model cannot identify the critical nodes from all nodes to pass the traffic efficiently. This could be a possible reason that the model does not give higher positive weights for critical nodes similar to uncongested and moderately congested conditions.
We train the model using mean squared error as the loss function. At each iteration, the model estimates the mean squared error for the estimated flows (𝐹 ̂𝑚 ℇ ) and the actual flows (𝐹 𝑚 ℰ ) of the network. Afterward, the gradient of the loss function is backpropagated to adjust the weights to reduce loss function value. The loss function can be defined as,
where, 𝐿𝑜𝑠𝑠(. ) is the function to estimate the error between the actual (𝐹 𝑚 ℰ ) and estimated values (𝐹 ̂𝑚 ℰ ) and ℰ denotes the set of links for the network. In this study, we estimate mean square error (MSE) as a loss function. To check the stability of solution, we observed the training and test loss values for the model (Fig. 8). We train each model for 10,000 iterations to check variation of train and We also check the computation time required to train the models. It takes about 19
minutes to train the models on Sioux Falls network for 10,000 iterations, while for East Massachusetts network it takes 30 minutes. So, our approach performs reasonably well to estimate network level traffic flows with less computation time. method is completely data-driven without requiring any assumption on user behavior. Thus, it will improve the reliability and stability of traffic assignment solutions.
To extend this framework towards a data-driven dynamic traffic assignment method, we need to consider the representation of the physical process of flow propagation to account travel time variations. In addition, existing data sources are not widely available to researchers to infer travel demand at a higher spatiotemporal resolution. Alternative data augmentation approach can be explored to prepare the travel demand data. Future research should consider these issues to develop a framework that can solve the dynamic traffic assignment problem and prepare demand data that can be fed into such frameworks.
A data-driven network modeling approach is warranted in the era of big data.
Ubiquitous use of mobile phones, availability of GPS based vehicle trajectory data, emerging connected and automated vehicle data, and so on will give us the opportunities to model travel demand and traffic flows at a high spatio-temporal resolution. The proposed deep learning architecture for solving a traffic assignment learning problem is an initial step towards exploiting such high-fidelity data for data-driven network modeling research.
connecting nodes 𝑖 and 𝑗 is longer than 𝐾 , such that 𝐿 𝐾 (𝑖, 𝑗) = 0 (Hammond et al., 2011).
Consequently, for a given pair of origin (𝑖) and destination (𝑗) nodes, a spectral graph filter of size K has access to all the nodes on the shortest path of the graph. It means that the spectral graph convolution filter of size 𝐾 captures flow propagation through each node on the shortest path. So, the spectral graph convolution operation can model the interdependency between a link and its 𝑖 th order adjacent nodes on the shortest paths, given that 0 ≤ 𝑖 ≤ 𝐾.
The computational complexity of calculating 𝑳 𝒘 𝒌 is high due to K times multiplication of 𝐿 𝑤 . A way to overcome this challenge is to approximate the spectral filter 𝑔 𝜃 with Chebyshev polynomials up to ( 𝐾 -1 )th order (Hammond et al., 2011). Defferrard et al. (Defferrard et al., 2016) applied this approach to build a K-localized ChebNet, where the convolution is defined as, where, Chebyshev coefficient, 𝜃 = 𝜃 0 = -𝜃 1 , All the detail about the assumptions and their implications of Chebyshev polynomial can be found in (Hammond et al., 2011) 21, we can observe that spectral graph convolution is a special case of diffusion convolution (Li et al., 2018), only difference is that in spectral convolution we symmetrically normalized the adjacency matrix.