{"id":337,"date":"2024-05-19T17:18:49","date_gmt":"2024-05-19T17:18:49","guid":{"rendered":"https:\/\/omaintec.org\/journal\/?post_type=docs&p=337"},"modified":"2024-05-27T01:19:42","modified_gmt":"2024-05-27T01:19:42","password":"","slug":"graph-neural-networks-for-traffic-forecasting","status":"publish","type":"docs","link":"https:\/\/omaintec.org\/journal\/index.php\/docs\/graph-neural-networks-for-traffic-forecasting\/","title":{"rendered":"Graph Neural Networks for Traffic Forecasting"},"content":{"rendered":"

Jo\u00e3o Rico*1,2,3, Jos\u00e9 Barateiro1,2, Arlindo Oliveira2,3<\/strong><\/p>\n

1Laborat\u00f3rio Nacional de Engenharia Civil, Av. do Brasil 101, Lisbon, Portugal 2INESC-ID, R. Alves Redol 9, Lisbon, Portugal<\/em><\/p>\n

3Instituto Superior T\u00e9cnico, University of Lisbon, Lisbon, Portugal jmrico@lnec.pt,<\/a> jbarateiro@lnec.pt,<\/a> arlindo.oliveira@tecnico.ulisboa.pt<\/a><\/em><\/p>\n

<\/p>\n

Abstract<\/strong><\/h2>\n

The significant increase in world population and urbanisation has brought several important challenges, in particular regarding the sustainability, maintenance and planning of urban mobility. At the same time, the exponential increase of computing capability and of available sensor and location data have offered the potential for innovative solutions to these challenges. In this work, we focus on the challenge of traffic forecasting and review the recent development and application of graph neural networks (GNN) to this problem. GNNs are a class of deep learning methods that directly process the input as graph data. This leverages more directly the spatial dependencies of traffic data and makes use of the advantages of deep learning producing state-of-the-art results. We introduce and review the emerging topic of GNNs, including their most common variants, with a focus on its application to traffic forecasting. We address the different ways of modelling traffic forecasting as a (temporal) graph, the different approaches developed so far to combine the graph and temporal learning components, as well as current limitations and research opportunities.<\/p>\n

Keywords: graph neural networks, traffic forecasting, deep learning<\/p>\n

Introduction<\/strong><\/h2>\n

The world\u2019s urban population will increase from 4.2 billion to 6.7 billion by 2050 as estimated by the United Nations [1]. In spite of the accompanying social evolution and benefits, the rapid rate of urbanization has significant social, economic and environmental costs associated, including air and water pollution, unsustainable energy consumption, toxic waste disposal, inadequate urban planning, decreased public health and safety, social vulnerability and community disruption. Notably, the mobility of passengers and freights in most large cities of the world is not yet sustainable. Urbanization has given rise to traffic congestion, increase of transports needs, ineffective accessibility, and reduced productivity. In particular, traffic congestion costs billions of dollars per year due to lost time, air pollution, and wasted fuel. In 2017, in the United States alone, traffic congestion induced a total of<\/p>\n

8.8 billion hours of travel delay and 12.5 billion liters of extra fuel consumption, corresponding to a congestion cost of 166 billion dollars [2]. Efforts to develop solutions to the challenges brought by traffic congestion have focused on three avenues: championing transport alternatives, enlarging the infrastructure, and managing traffic flows [3]. While championing transport alternatives is mostly a public policy issue, and geographical and social constraints limit the increase of the size of infrastructure, the potential to efficiently manage traffic flows has increasingly become one important solution to traffic congestion. Today, the exponential increase of available data in cities and the growth of computing capabilities represents a crucial opportunity to tackle these challenges by leveraging innovative and<\/p>\n

integrated solutions. These include the development of intelligent transportation systems (ITS), smart vehicle sharing systems and home automation, and smart grids and energy solutions – all of which fall under the umbrella of the recent area of urban computing [4].<\/p>\n

A core component of ITS is traffic forecasting. Its goal is to measure, model and predict traffic conditions in real-time, accurately and reliably, in order to optimize the flow and mitigate the congestion of traffic, and to respond adequately to other problems such as traffic light control, time of arrival estimates, and planning of new road segments. However, this is a very challenging problem due to several important factors. The successful forecasting of traffic conditions requires adequately handling heterogeneous data (e.g., integrating loop counter and floating car data) with complex spatio-temporal dependencies which are typically sparse, incomplete and high-dimensional. In addition, it requires computing in real-time and the inclusion of external factors such as weather conditions and road accidents.<\/p>\n

This review is focused on the recent developments and applications of graph neural networks, a new family of deep learning models, to road traffic forecasting. In Section 2, we present a succinct history of traffic forecasting including traditional approaches and deep learning models that have had a great deal of success. Section 3 presents and discusses graph neural networks (GNN) and Section 4 reviews the literature of traffic forecasting based on GNN. W1e conclude, in Section 5, with a discussion of open challenges and research opportunities.<\/p>\n

Traffic forecasting<\/strong><\/h2>\n

W the weighted adjacency matrix. Denoting \ud835\udc4b!! as the values of all the features of node i at time t, we aim to learn a function F that given a sequence of M historical time steps predicts the next N time steps:<\/p>\n

\ud835\udc39([\ud835\udc4b!!!!!, \u2026 , \ud835\udc4b!]; \ud835\udc3a) = [\ud835\udc4b!!!, \u2026 , \ud835\udc4b!!!]. (1)<\/p>\n

Traffic data<\/strong><\/h2>\n

Urban data can be classified according to their structures and spatiotemporal properties [9], as Figure 1 illustrates. We can distinguish datasets with respect to their spatiotemporal properties: spatiotemporal static data, spatial static but temporal dynamic data, or spatiotemporal dynamic data. They can also be classified with respect to their data structures in one of two types – point-based and network-based. In addition, urban data can also be classified according to its sources, such as geographical data, traffic data, and social network data, to name a few, and each of these can be further subclassified. Focusing on traffic data, this source can include loop detector data, floating car data, mobile phone data, call detail records, surveillance cameras, bike-sharing data, taxi records, mobile phone location data, parking records, and mobile apps\u2019 logs.<\/p>\n

<\/p>\n

Figure 1: Six types of urban data [9]. Reprinted with permission.<\/p>\n

Traditional approaches to traffic forecasting<\/strong><\/h2>\n

In the last decades, traffic forecasting methods have been developed by researchers from different fields such as transportation systems [10], economics [11], statistics, and machine learning [12]. The methods can be divided into two categories: the knowledge- or model-driven approach and the data-driven approach. Knowledge-driven approaches usually aim at modeling and explaining the transportation network through differential equations and numerical simulation [13], [14]. Although the models can reproduce real traffic conditions fairly accurately, they require prior knowledge and detailed modeling, are not easily transferable to other cases, and require significant computational resources.<\/p>\n

Traditional data-driven methods used in traffic forecasting can be divided into two categories: methods that do not model the spatial dependency and models that do model this dependency. The former category includes the Historical Average (HA) model, the auto-regressive integrated moving average (ARIMA) [15] and seasonal ARIMA (SARIMA) [16], K-nearest Neighbour (KNN) [17], support vector regression [18], hidden Markov models [19], among others. These approaches often require careful feature engineering and also rely on data to satisfy certain assumptions, such as stationarity. However, real data is often too complex and violates often these assumptions, leading in many cases to poor performance. Approaches that model the spatial dependency include Vector ARIMA, Spatiotemporal ARIMA and Spatiotemporal HMM [20]\u2013[23]. Again, these methods perform poorly since they are not complex enough to model the non-linearity and non-stationarity of the data.<\/p>\n

Deep learning approaches to traffic forecasting<\/strong><\/h2>\n

Deep learning methods [24] are a class of machine learning methods that learn multiple layers of representations by composing increasingly more complex non-linear features on the upper layers by combining simpler features from the lower layers. This learning of complex representations is done mostly automatically and does not depend on a human doing manual feature engineering, which would require time and expert domain knowledge. In recent years, deep learning represents the state of the art in fields such as image recognition [25], natural language understanding [26],<\/p>\n

drug discovery [27], recommendation systems [28], and board and video games playing [29]. This success is mainly due to their representation power (as explained above) and to the fact that there exists an efficient method for training them (namely gradient descent through error backpropagation).<\/p>\n

As in other domains, the application of deep learning methods to traffic forecasting has been very successful and has produced state-of-the-art results. Some of the earlier architectures did not model the spatial dependency, and used standard feedforward networks or deep belief networks [30] as well as recurrent neural networks such as long short- term memory (LSTM) and the gated recurrent unit (GRU)<\/p>\n

[31]\u2013[33]. However, these models still fail to model the complex spatial dependencies that exist in traffic problems. Several models were proposed that aim at capturing these dependencies, using convolutional neural networks (CNN) [34] or a combination of CNN and LSTM [35], [36]. Still, since CNNs are mainly suited for data embedded in grid-line Euclidean spaces, they are not the natural architecture to real-world road networks. The next sections expand on how models using a graph neural network improved on these architectures.<\/p>\n

Graph neural networks<\/strong><\/h2>\n

The convolutional operator used in CNNs is very powerful but is limited to standard grid data, i.e., to data that originates in regular, two-dimensional, tri-dimensional, or higher-dimensional Euclidean spaces. Since various important machine learning problems involve tasks on graph structured data such as node classification [37] or molecule generation [38], researchers have developed a family of deep learning models that can leverage this inductive bias [37], [39]\u2013[41]. These models are usually called graph neural networks (GNN) because they are neural networks that naturally handle graph data. In this section, we briefly review the area of graph neural networks and some of the most relevant works, and refer the reader to other reviews for more details and specific perspectives on this topic [41]\u2013 [46]. In Section 3.1, we categorize and describe several GNN models, and in Section 3.2 we list current open-source libraries for implementing GNNs.<\/p>\n

Models<\/strong><\/h2>\n

In this section, we describe several of the most relevant GNNs models developed so far. As shown in Table 1, we categorize GNNs into four main types, namely recurrent graph neural networks, convolutional graph neural networks, graph autoencoders and graph attention networks.<\/p>\n\n\n\n\n\n\n\n
Category<\/strong><\/td>\nReferences<\/strong><\/td>\n<\/tr>\n
Recurrent Graph Neural Networks<\/td>\n]50[\u2013]47[ ,]39[<\/td>\n<\/tr>\n
Convolutional Graph Neural Networks<\/td>\n]53[\u2013]51[ ,]40[ ,]37[<\/td>\n<\/tr>\n
Graph Attention Networks<\/td>\n]55[ ,]54[<\/td>\n<\/tr>\n
Graph Autoencoders<\/td>\n]61[\u2013]56[<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Table 1. Categorization of graph neural network models and representative publications.<\/p>\n

Recurrent graph neural networks<\/strong><\/h2>\n

Extending previous work [62], [63], the Graph Neural Network model (GraphNN) [39] was the first neural network model that could process general types of graphs (eg, directed, undirected, cyclic, or acyclic). The fundamental concept of the GraphNN model is that every node \ud835\udc63 can be represented by a low-dimensional state vector \u210e!and be defined by its features and by its neighbours based on an information diffusion mechanism from every node to its neighbors. The goal is to learn this representation which can be fed to an output function g, called the local output function, resulting in an output value or label \u043e\ud835\udc97, for regression or classification, respectively. The model also defines the local transition function \ud835\udc53, a parametric function, to be learned alongside g – both shared by all nodes. Together, these node representation and output are defined as:<\/p>\n

\u210e! = \ud835\udc53(\ud835\udc65!, \ud835\udc65!\u201d[!], \u210e!\u201d[!], \ud835\udc65!\u201d[!]), (1)<\/p>\n

\ud835\udc90! = \ud835\udc54(\ud835\udc89!, \ud835\udc65!), (2)<\/p>\n

where \ud835\udc65!, \ud835\udc65!\u201d[!], \ud835\udc89!\u201d[!], \ud835\udc65!\u201d[!] are the features of v, the features of its edges, and the states and features of its neighborhood, respectively.<\/p>\n

Denoting the vectors constructed by stacking all the states, all the features, all the node features and all the outputs by<\/p>\n

\ud835\udc3b, \ud835\udc4b, \ud835\udc4b!, \ud835\udc42 equations (1) and (2) can be rewritten compactly as<\/p>\n

\ud835\udc3b = \ud835\udc39(\ud835\udc3b, \ud835\udc4b), (3)<\/p>\n

\ud835\udc42 = \ud835\udc3a(\ud835\udc3b, \ud835\udc4b!), (4)<\/p>\n

where F and G are the stacked versions of f and g for all nodes, respectively.<\/p>\n

If F is a contraction map, Banach\u2019s Fixed Point Theorem [64] guarantees the existence and uniqueness of the system of equations (3) and (4). This suggests iteratively updating the following equation:<\/p>\n

\ud835\udc3b! = \ud835\udc39(\ud835\udc3b!!!, \ud835\udc4b) (5)<\/p>\n

where \ud835\udc3b! is the t-th iteration of \ud835\udc3b, and \ud835\udc3b!can be initialized randomly.<\/p>\n

<\/p>\n

Figure 2 shows the intuition behind equations (1) and (5): to learn a node representation by propagating information from its neighbors, iteratively, until convergence.<\/p>\n

\u210e! = (\ud835\udc65!, \ud835\udc65(!,!), \ud835\udc65(!,!), \ud835\udc65(!,!), \u210e!, \u210e!, \u210e!, \ud835\udc65!, \ud835\udc65!, \ud835\udc65!)<\/p>\n

Figure 2: Example graph of how GraphNN propagates information from the states and features of the immediate neighborhood of a node.<\/p>\n

To learn the functions \ud835\udc53 and \ud835\udc54, GraphNN defines a loss function at the supervised nodes, and uses a gradient descent<\/p>\n

scheme: iteratively updating \ud835\udc3b! until a convergence criterion is reached; calculating the gradients of the loss with respect to the weights of \ud835\udc53 and \ud835\udc54; and updating the weights.<\/p>\n

Although it is a simple and powerful model, GraphNN has several limitations. Most importantly, it is computationally inefficient to compute the iterations for the fixed point and requiring \ud835\udc39 to be a contraction map limits the modeling capacity of the approach, including the long range dependencies of nodes (see appendix A of [47]).<\/p>\n

The Gated Graph Neural Network (GatedGNN) [47] is another recurrent graph neural network, and it improves on some of the drawbacks of GraphNN. This model modifies the original GraphNN substituting the recurrence function in equation (1) for a Gated Recurrent Unit (GRU) [65]. GatedGNN uses backpropagation through time (BPTT), unrolling the recurrence for a fixed number of T steps. While for a large graph this can present a drawback by requiring a large amount of memory to store the intermediate states computed over all nodes, on the other hand this removes the requirement for a contraction map in order to guarantee convergence. The model recurrence is defined as follows<\/p>\n

\ud835\udc4e!! = \ud835\udc34!:[\u210e!!!!. . . \u210e!!!!] + \ud835\udc4f, \ud835\udc54!! = \ud835\udc61\ud835\udc4e\ud835\udc5b\u210e(\ud835\udc4a\ud835\udc4e!! + \ud835\udc48(\u210e!!!! \u2299 \u210e!!!!),<\/p>\n

\ud835\udc67!! = \ud835\udf0e(\ud835\udc4a!\ud835\udc4e!! + \ud835\udc48!\u210e!!!!), \u210e!! = (1 \u2212 \ud835\udc67!!) \u2299 \u210e!!!! + (\ud835\udc67!! \u2299 \ud835\udc54!!), (6)<\/p>\n

\ud835\udc5f!! = \ud835\udf0e(\ud835\udc4a!\ud835\udc4e!! + \ud835\udc48!\u210e!!!!),<\/p>\n

where \ud835\udc34 is the modified adjacency matrix composed of two submatrices, one for outgoing edges, the other for incoming edges. Figure 3 shows the parameter tying and sparsity structure in the adjacency matrix, as well as an example of the unrolling of the recurrence for one time step. \ud835\udc68\ud835\udc97: corresponds to the two columns of the submatrices \ud835\udc68(\ud835\udc90\ud835\udc96\ud835\udc95)and \ud835\udc68(\ud835\udc90\ud835\udc96\ud835\udc95) referring to node \ud835\udc63, and \ud835\udc9b and \ud835\udc93 correspond to the update and reset gates of the GRU.<\/p>\n

Figure 3: (a) Example graph,<\/p>\n

where edge color denotes edge type. (b) Unrolling of one t)<\/sup>im!(!<\/sup>e step. (c) Parameter tying and sparsity in adjacency matrix. Letters denote edge types. B\u2032 corresponds to the reverse edge of type B. B and B \u2032 denote distinct parameters [47]. Reprinted with permission.<\/p>\n

Other recurrent graph neural networks have been developed, including the Graph Echo State Network [66],Graphrnn<\/p>\n

[50] and Stochastic Steady-state Embedding [49].<\/p>\n

Convolutional graph neural networks<\/strong><\/h2>\n

The generalization of the very successful CNN to non-Euclidean data such as graphs and manifolds has followed two distinct avenues, the so-called spectral methods and spatial methods. Briefly, spectral based methods define the convolution based on the graph Laplacian and use the corresponding Fourier basis in the spectral domain, and spatial methods use a localized parameter-sharing filter on the neighbors of each node, in essence, aggregating local features.<\/p>\n

Spectral Convolutional Neural Networks (SpectralCNN) [51] was the first model to introduce the convolution for graph data. Given an undirected graph its normalized graph Laplacian is defined as<\/p>\n

\ud835\udc3f = \ud835\udc3c! \u2212 \ud835\udc37!!\/!\ud835\udc34\ud835\udc37!!\/!, (7)<\/p>\n

where \ud835\udc68 is the adjacency matrix and \ud835\udc37 is the diagonal matrix of node degrees. The graph Laplacian is a real symmetric positive semidefinite matrix which implies that it can be factorized as<\/p>\n

\ud835\udc3f = \ud835\udc48\ud835\udeec\ud835\udc48!, (8)<\/p>\n

where \ud835\udeec is the diagonal matrix of eigenvalues – the spectrum – and \ud835\udc7c is the matrix of eigenvectors. Given a graph signal<\/p>\n

\ud835\udc65 \u2208 \ud835\udc45!where \ud835\udc65! is the feature of the i-th node. The graph Fourier transform \u2131 – and its inverse \u2131!! are defined by<\/p>\n

\u2131(\ud835\udc65) = \ud835\udc48!\ud835\udc65 = \ud835\udc65, (9)<\/p>\n

\u2131!!(\ud835\udc65) = \ud835\udc48!\ud835\udc65. (10)<\/p>\n

The graph convolution operation of a graph signal x with a filter g on a graph G is defined as<\/p>\n

\ud835\udc65 \u2217 \ud835\udc54 = \u2131!!(\ud835\udc65)(\u2131(\ud835\udc65) \u2299 \u2131(\ud835\udc65)),<\/p>\n

= \ud835\udc48(\ud835\udc48!\ud835\udc65 \u2299 \ud835\udc48!\ud835\udc54) (11)<\/p>\n

where \u2299 is the Hadamard product. The equation above can be simplified, by considering a filter \ud835\udc54 =<\/p>\n

\ud835\udc51\ud835\udc56\ud835\udc4e\ud835\udc54(\ud835\udf03)parametrized by \ud835\udf03 \u2208 \ud835\udc45! in the Fourier domain, to the following expression<\/p>\n

\ud835\udc65 \u2217 \ud835\udc54 = \ud835\udc48\ud835\udc54\ud835\udc48!\ud835\udc65, (12)<\/p>\n

where filter \ud835\udc54 can be understood as a function of eigenvalues of the Laplacian, that is \ud835\udc54(\ud835\udeec).<\/p>\n

This model has several drawbacks. It is computacional inefficient since multiplication by \ud835\udc48 is \ud835\udc42(\ud835\udc5b!) and calculating the eigen-decomposition is \ud835\udc42(\ud835\udc5b!). In addition, the dimensionality of the trainable filter depends on the number of nodes of the graph, and the filters are non-localized depending on the graph structure – if a graph changes at all, so will its eigenvalues and eigenvectors.<\/p>\n

Chebyshev Spectral Convolutional Neural Networks (ChebNet) [40] proposes to approximate the filter by Chebyshev polynomials of the diagonal matrix of eigenvalues, that is,<\/p>\n

<\/p>\n

where \ud835\udc3f\u2217 = 2\ud835\udc3f\/\ud835\udf06!\u201d# \u2212 \ud835\udc3c! and \ud835\udf06!\u201d# is the maximum eigenvalue. The Chebyshev polynomials are defined by the recursion \ud835\udc47!(\ud835\udc65) = 2\ud835\udc65\ud835\udc47!!!(\ud835\udc65) \u2212 \ud835\udc47!!!(\ud835\udc65) with \ud835\udc47!(\ud835\udc65) = 1 and \ud835\udc47!(\ud835\udc65) = \ud835\udc65. In this setting, the computational complexity reduces to \ud835\udc42(\ud835\udc3e\ud835\udc40) where \ud835\udc3e is the polynomial order of the expansion above and \ud835\udc40 is the number of edges, rendering the model linear with respect to the graph size. This also renders the filters spatially localized, since for an expansion of degree \ud835\udc3e each node only receives information from a node at maximum \ud835\udc3e hops away.<\/p>\n

Graph Convolutional Networks (GCN) [37] extends ChebNet by limiting the Chebyshev expansion to only the first order, \ud835\udc3e = 1, and employing some additional modifications. It assumes \ud835\udf06!\u201d# = 2, simplifying equation (13) to<\/p>\n

\ud835\udc65 \u2217 \ud835\udc54 = \ud835\udf03!\ud835\udc65 \u2212 \ud835\udf03!\ud835\udc37!!\/!\ud835\udc34\ud835\udc37!!\/!\ud835\udc65. (14)<\/p>\n

Setting \ud835\udf03! = \u2212\ud835\udf03!and substituting \ud835\udc34for \ud835\udc34\u2217 = \ud835\udc34 + \ud835\udc3c!, equation (12) can be written as<\/p>\n

\ud835\udc65 \u2217 \ud835\udc54 = \ud835\udf03(\ud835\udc3c! + \ud835\udc37\u2217!!\/!\ud835\udc34\u2217\ud835\udc37\u2217!!\/!\ud835\udc65. (15)<\/p>\n

Generalizing to the signal to \ud835\udc36 input channels and \ud835\udc39 filters for feature maps, the graph convolution can be written as<\/p>\n

\ud835\udc4d = \ud835\udc37\u2217!!\/!\ud835\udc34\u2217\ud835\udc37\u2217!!\/!\ud835\udee9, (16)<\/p>\n

where \ud835\udc4d \u2208 \ud835\udc45!\u00d7!, and \ud835\udee9 \u2208 \ud835\udc45!\u00d7! is a matrix of filter parameters.<\/p>\n

ChebNet and GCN bridge the gap between spectral- and spatial based methods. Equation (16) can be expressed as<\/p>\n

(16)<\/p>\n

\u210e! = \ud835\udc53((<\/p>\n

!\u2208{!(!)\u222a!)<\/p>\n

\ud835\udc34!,!\ud835\udc65!)\ud835\udee9),<\/p>\n

which can be interpreted as a spatial-based method, each node aggregating information from its neighbors.<\/p>\n

\ufffd Neural Fingerprints (Neural FPs) [53] generalized GNNs by using different learning parameters for nodes with different degrees, as follows:<\/p>\n

\ud835\udc65 = \u210e!!!! +<\/p>\n

!!!<\/p>\n

\u210e!!!!\ud835\udf03!\ud835\udc47!(\ud835\udeec\u2217))\ud835\udc48!\ud835\udc65,<\/p>\n

(17)<\/p>\n

\u210e!! = \ud835\udf0e(\ud835\udc65\ud835\udc4a!|!(!)|), (18)<\/p>\n

where \ud835\udc4a! !(!) is the weight matrix for nodes of degree \ud835\udc41 at layer \ud835\udc61.<\/p>\n

Another interesting model is the dual graph convolutional network (DGCN) [67] which jointly uses two convolutions: one based on the adjacency matrix is the same as equation (16), and the second one is based on a diffusion process to capture global relationships by substituting the adjacency matrix \ud835\udc68 with the positive pointwise mutual information (PPMI) matrix [52].<\/p>\n

Graph Attention Networks<\/p>\n

Attention mechanisms [68], [69] are a recent development in deep learning that has had success in tasks such as machine translation. Figure 4 illustrates the intuition of why attention mechanisms could be helpful in modelling the neighborhood of a node, namely by leveraging the type of each neighbor to assign different importance weights.<\/p>\n

<\/p>\n

Figure 4: The type of each neighbor is used to assign attention, and the link size denotes how much attention to apply to each neighbor. This example illustrates how concentrating our attention on the node\u2019s classmates, would improve our prediction of the enjoyment of the activity [70]. Reprinted with permission.<\/p>\n

Graph Attention Networks (GAT) [54] was the first model to incorporate an attention mechanism in GNNs by removing the requirement that all the neighbors of a node contribute with equal or pre-defined weights. Rather, the relative weights between two connected weights are learned as follows:<\/p>\n

\u210e!! = \ud835\udf0e(<\/p>\n

<\/p>\n

!\u2208{!(!)\u222a!}<\/p>\n

\ud835\udefc!\u201d\ud835\udc4a!!!\u210e!!!!),<\/p>\n

(19)<\/p>\n

where \ud835\udefc!\u201d is the attention coefficient of node j to i defined as<\/p>\n

\ud835\udefc!\u201d = \ud835\udc60\ud835\udc5c\ud835\udc53\ud835\udc61\ud835\udc5a\ud835\udc4e\ud835\udc65(\ud835\udc54(\ud835\udc4e![\ud835\udc4a!!!\u210e!||\ud835\udc4a!!!\u210e!])), (20) where \ud835\udc4e is a vector of learnable parameters and \ud835\udc54 is a LeakyReLU unit.<\/p>\n

GAT also proposes incorporating a multi-head attention mechanism [69], and have the important advantage of being efficient since the computation of the node-neighbor pairs is parallelizable and because it can naturally be applied to nodes with a different number of neighbors.<\/p>\n

Gated Attention Network (GAAN) [55] is an extension of GAT which, in addition to the multi-head attention mechanism, also incorporates a self-attention mechanism which replaces the averaging operation of GAT with an attention score on each attention head. For more details and different taxonomies of attention models in graphs, we refer the reader to a comprehensive review [70].<\/p>\n

Graph Autoencoders<\/strong><\/h2>\n

Graph neural networks have also been used in unsupervised learning settings. In particular, successful deep learning models such as autoencoders [71] and variational autoencoders [72] have been generalized to handle graph data. These models are usually developed to either learn network embeddings, such as Structural Deep Network Embedding [56] and Variational Graph Autoencoder [57], or to generate new graphs such Deep Generative Model of Graphs [58] and Graph Variational Autoencoder [59].<\/p>\n

Some models have also incorporated adversarial training, in particular Generative Adversarial Networks (GAN) [73]. In a GAN, two networks compete against each other: the generator network is optimized to produce realistic samples of data that the discriminator network tries to distinguish from real data. GANs have been used together with GCN for generation of molecular graphs [60], link prediction, node clustering, and graph visualization [61].<\/p>\n

Frameworks<\/strong><\/h2>\n

In addition to the different types of GNN models that have been developed so far, some of which we describe above, there has been an effort to unify GNNs under a general and common framework. Non-local Neural Networks (NLNN)<\/p>\n

[74] unifies different self-attention mechanisms, and Message Passing Neural Networks (MPNN) [75] generalizes several GNN approaches using a message passing scheme. In MPNNs, messages \ud835\udc5a!! at timestep t are passed from each node v as follows:<\/p>\n

\ud835\udc5a!!!! =<\/p>\n

<\/p>\n

!\u2208!(!)<\/p>\n

\ud835\udc40!(\u210e!!, \u210e!!, \ud835\udc52!\u201d),<\/p>\n

(21)<\/p>\n

\u210e!!!! = \ud835\udc48!(\u210e!!, \ud835\udc5a!!!!), (22)<\/p>\n

where \ud835\udc48! is the vertex update function, \ud835\udc40! is the message function and \ud835\udc52!\u201drepresents the features of the edge from node<\/p>\n

v to u.<\/p>\n

The Graph Networks (GN) model [41] generalizes both the NLNN and MPNN frameworks and other types of GNNs. It defines a GN block containing three update functions and three aggregation functions as follows:<\/p>\n

\ud835\udc52!\u2032 = \ud835\udf11!(\ud835\udc52!, \u210e!\u201d, \u210e!\u201d, \ud835\udc62), \ud835\udc52!\u2217\u2032 = \ud835\udf0c!\u2192!(\ud835\udc38!\u2032),<\/p>\n

\u210e!\u2032 = \ud835\udf11!(\ud835\udc52!\u2217\u2032, \u210e!, \ud835\udc62), \ud835\udc52\u2217\u2032 = \ud835\udf0c!\u2192!(\ud835\udc38\u2032), (23)<\/p>\n

\ud835\udc62\u2032 = \ud835\udf11!(\ud835\udc52\u2217\u2032, \u210e\u2217\u2032, \ud835\udc62), \u210e\u2217\u2032 = \ud835\udf0c!\u2192!(\ud835\udc3b\u2032), where \ud835\udf0c() are the message passing functions and \ud835\udf11() the update functions.<\/p>\n

Software<\/p>\n

The research and application of GNNs has been greatly enhanced by the development and publishing of several open- source libraries, specifically written to handle GNNs. These are built on top of already powerful deep learning frameworks, such as PyTorch [76] and Tensorflow [77]. These GNN libraries can greatly reduce the time of testing and deployment of new models, by providing useful abstractions that simplify the code required while automatically handling several low-level optimizations, such as scaling, parallelization and taking advantage of sparse structure. It is also common for authors to release implementations of their models in these libraries, which are, in turn, often integrated in these libraries in a ready-to-use manner.<\/p>\n\n\n\n\n\n\n\n
Library<\/strong><\/td>\nRefer-<\/strong>ence<\/strong><\/td>\nDL Framework<\/strong><\/td>\nURL<\/strong><\/td>\n<\/tr>\n
DGL<\/td>\n]78[<\/td>\nMXNet, Pytorch<\/td>\nhttps:\/\/github.com\/dmlc\/dgl<\/td>\n<\/tr>\n
Euler<\/td>\n]79[<\/td>\nTensorflow<\/td>\nhttps:\/\/github.com\/alibaba\/euler<\/td>\n<\/tr>\n
Graph Nets<\/td>\n]41[<\/td>\nTensorflow<\/td>\nhttps:\/\/github.com\/deepmind\/graph_nets<\/td>\n<\/tr>\n
PyTorch Geomet-ric<\/td>\n]80[<\/td>\nPytorch<\/td>\nhttps:\/\/github.com\/rusty1s\/pytorch_geometric<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Table 2: Graph deep learning libraries.<\/p>\n

Graph neural networks for traffic forecasting<\/p>\n

The connection between graphs and roads or maps is as old as graph theory, dating back to Euler\u2019s formulation and solution to the K\u00f6nigsberg problem. Nodes can represent road intersections and edges can model the road segments between them. Or, almost as naturally, nodes can represent points on a road segment where a traffic variable is being measured by a sensor and edges represent some relationship between these locations, such as the shortest path distance between them. The addition of a temporal component can be just as natural, as Figure 6 illustrates. Typically, each node in a graph would define a time-series of a feature vector, such as the history of traffic speed and traffic flow at a certain location.<\/p>\n

<\/p>\n

Figure 6: (a) Typical spatio-temporal structure of traffic data with each time slice forming a graph. (b) Representation of a three-dimensional time series at a certain node and a forecast of one of these features. [8]. Reprinted with permission.<\/p>\n

Traffic forecasting based on graph neural networks can be viewed as the problem of extending the models of the previous section and the categories of Table 1 to the temporal domain. In principle, combining the many types of GNNs approaches with the immense diversity of existing time series analysis models and forecasting methods offers a wide space of possibilities.<\/p>\n

In this section, we will present and compare the graph neural network models for traffic forecasting that have been developed so far. These have in common a graph neural network as a centerpiece of the model and they vary along most modern deep learning paradigms, combining recent techniques that have been found powerful in other domains of applications. These include attention mechanisms [8], [55], multi- graphs [81], dynamic graphs [82], diffusion kernels [83], graph wavenet [84], inception models [85], deep<\/p>\n

graph infomax [86], residual nets [87], wavelet transforms [88], among others [6], [7], [89]\u2013[95]. In section<\/p>\n

4.1. we review these models and compare different approaches, and in Section 2 we describe typical datasets in which these models are evaluated.<\/p>\n

Models<\/strong><\/h2>\n

Table 3 lists the GNNs models developed for traffic forecasting so far, which we describe below. We start by describing Spatio-Temporal Graph Convolutional Networks (STGCN) [92] and Diffusion Convolutional Recurrent Neural Networks (DCRNN) [83]. As of the writing of this review, these two models stand out as the most cited and most often compared to when developing a new model, in part because they are some of the models first developed while also representing opposite approaches in some aspects.<\/p>\n

STGCNs combine the spectral-based ChebNets [40] with 1D-CNNs to model and predict traffic speed at various locations where sensors are located. The GCN and the CNN operate alternately along several layers, with the GCN capturing the spatial dependency while the CNN captures the temporal dependency. Figure 7 shows an illustration of scheme similar to the one used by STGCN, in which a CNN is combined with a GCN.<\/p>\n

<\/p>\n

Figure 7: Illustration of how to combine GNN and CNN to capture the spatial and temporal dependencies, respectively [8]. Reprinted with permission.<\/p>\n

DCRNNs take the opposite direction: they use RNNs instead of 1D-CNN to model the time dependencies and, in addition, use a spatial-based GCN for the spatial dependency instead of a spectral-based one. This is done by incorporating the GCN inside a GRU. Based on Diffusion-Convolution Neural Networks [96], DCRNN uses the probability transition matrix \ud835\udc43 = \ud835\udc37!!\ud835\udc34 to define the graph convolution as follows:<\/p>\n

\ud835\udc3b =<\/p>\n

!<\/p>\n

<\/p>\n

!!!<\/p>\n

\ud835\udc53(\ud835\udc43!\ud835\udc4b\ud835\udc4a(!)),<\/p>\n

(24)<\/p>\n

where \ud835\udc53() is an activation function and \ud835\udc4a(!) \u2208 \ud835\udc45!\u00d7!. Effectively, DCRNN assumes that by passing information from node to node the network can reach an equilibrium state which is captured by the probability transition matrix. DCRNN also uses an enconder-decoder architecture to predict future timesteps.<\/p>\n

<\/p>\n

Figure 8: Architecture of MVGCN, displaying the views capturing different timescale dependencies, and their fusion in the final layer. [90]<\/p>\n

A different and promising approach has been proposed by several recent models, including Multi-View Graph Convolutional Networks (MVGCN) [90], Multi Residual Recurrent Graph Neural Networks (MRes- RGNN) [87], Motif-based Graph Convolutional Recurrent Neural Network (Motif-GCRNN) [88] and Spatial- Temporal Graph Inception Residual Networks (STGI-ResNet) [85]. In these approaches, typical repeating time patterns are grouped in order to leverage the inductive bias we know is present in typical traffic, such as daily or weekly periods. As an illustration, if one is predicting traffic speed at 9am on a friday, in principle, one can make a better prediction by considering not only the last previous hours, but also, for example, the traffic at 9am in the previous four days of the week, and in the previous fridays, at 9am. These different views are then fused in the last layers of the architecture. This fusion layer is also learnable. Figure 8 shows the architecture of MVGCN which exemplifies this approach. As shown in the figure, these approaches can also typically handle exogenous factors such as weather and irregular events (e.g., road accidents), that have a significant impact in urban traffic.<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
Model<\/strong><\/td>\n.Ref<\/strong><\/td>\nScope<\/strong><\/td>\nPredicts<\/strong><\/td>\nData source<\/strong><\/td>\nDatasets<\/strong><\/td>\n?Open dataset<\/strong><\/td>\nCode avail-<\/strong>?able<\/strong><\/td>\n<\/tr>\n
ST-GCN<\/td>\n]92[<\/td>\nFw, Ur<\/td>\nS<\/td>\nL<\/td>\nBJER4, PeMS<\/td>\n\n
    \n
  • ,\u2717<\/li>\n<\/ul>\n<\/td>\n
<\/td>\n<\/tr>\n
DCRNN<\/td>\n]83[<\/td>\nFw<\/td>\nS<\/td>\nL<\/td>\nMETR-LA, PeMS<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
MRes-RGNN<\/td>\n]87[<\/td>\nFw<\/td>\nS<\/td>\nL<\/td>\nMETR-LA, PeMS<\/td>\n<\/td>\n\u2717<\/td>\n<\/tr>\n
TGC-LSTM<\/td>\n]7[<\/td>\nFw, Ur<\/td>\nS<\/td>\nL, FCD<\/td>\nLOOP, INRIX<\/td>\n\n
    \n
  • ,\u2717<\/li>\n<\/ul>\n<\/td>\n
\u2717<\/td>\n<\/tr>\n
ASTGCN<\/td>\n]8[<\/td>\nFw<\/td>\nF, S<\/td>\nL<\/td>\nPeMSD4, PeMSD8<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
STDGI<\/td>\n]86[<\/td>\nFw<\/td>\nS<\/td>\nL<\/td>\nMETR-LA<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
MVGCN<\/td>\n]90[<\/td>\nUr<\/td>\nF<\/td>\nFCD<\/td>\nTaxiNYC, Tax- iBJ, BikeDC, BikeNYC<\/td>\n<\/td>\n\u2717<\/td>\n<\/tr>\n
DST-GCNN<\/td>\n]82[<\/td>\nFw, Ur<\/td>\nS, V<\/td>\nL, FCD<\/td>\nMETR-LA,TaxiBJ<\/td>\n<\/td>\n\u2717<\/td>\n<\/tr>\n
GSRNN<\/td>\n]91[<\/td>\nUr<\/td>\nF<\/td>\nFCD<\/td>\nBikeNYC,TaxiBJ<\/td>\n<\/td>\n\u2717<\/td>\n<\/tr>\n
GraphWavenet<\/td>\n]84[<\/td>\nFw<\/td>\nS<\/td>\nL<\/td>\nMETR-LA,PeMS<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
3D-TGCN<\/td>\n]6[<\/td>\nFw<\/td>\nS<\/td>\nL<\/td>\nPeMS<\/td>\n<\/td>\n\u2717<\/td>\n<\/tr>\n
ST-UNet<\/td>\n]93[<\/td>\nFw<\/td>\nS<\/td>\nL<\/td>\nMETR-LA,PeMS<\/td>\n<\/td>\n\u2717<\/td>\n<\/tr>\n
GaAN<\/td>\n]55[<\/td>\nFw<\/td>\nS<\/td>\nL<\/td>\nMETR-LA<\/td>\n<\/td>\n\u2717<\/td>\n<\/tr>\n
Mo-tif-GCRNN<\/td>\n]88[<\/td>\nUr<\/td>\nS<\/td>\nFCD<\/td>\nTaxiChengdu<\/td>\n\u2717<\/td>\n\u2717<\/td>\n<\/tr>\n
STGi-Res-Net<\/td>\n]85[<\/td>\nUr<\/td>\nF<\/td>\nFCD<\/td>\nDidi Chengdu<\/td>\n<\/td>\n\u2717<\/td>\n<\/tr>\n
T-GCN<\/td>\n]94[<\/td>\nFw, Ur<\/td>\nS<\/td>\nFCD<\/td>\nSZ-taxi, Los-loop<\/td>\n\n
    \n
  • ,\u2717<\/li>\n<\/ul>\n<\/td>\n
\u2717<\/td>\n<\/tr>\n
FlowConv-GRU<\/td>\n]97[<\/td>\nUr<\/td>\nF<\/td>\nFCD<\/td>\nTaxiNYC,TaxiCD<\/td>\n<\/td>\n\u2717<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Table 3: Graph Neural Networks approaches to traffic forecasting. For each publication, we list the scope of application (Ur: urban, Fw: freeway) , the variables predicted (S: speed, F: flow, V: volume), the data source (L: loop counters, FCD: floating car data), the datasets used for experiments, whether or not these datasets are open, and whether there exists open-source code implementations of the models.<\/p>\n

<\/p>\n

Attention mechanisms have also shown to be a promisingapproach to spatio-temporal forecasting. In addition to the GaAN architecture [55] described in Section 3.1.3, Attention Based Spatial-Temporal Graph Convolutional Networks (ASTGCN) [8] combine attention mechanisms on both the spatial and the temporal components with a multi-view approach on temporal patterns (namely, recent, daily-periodic and weekly- periodic). Figure 9 illustrates the intuition on how attention mechanisms can help make better predictions as well as output more interpretable models.<\/p>\n

<\/p>\n

(c) Attention matrix obtained from the spatial attention mechanism.<\/p>\n

Figure 9: (a) and (b) Spatial-temporal correlation diagram of traffic flow. (c) Attention matrix of sub-graph with 10 detectors, where the i-th row indicates how strong the time series of node i correlates with every other node. As an example of the interpretability aspect of this model, we can see that it indicates that pairs of nodes most strongly correlated tend to be spatially close, such as 1 and 6, 5 and 4, and 9 and 3.<\/p>\n

[8] Reprinted with permission.<\/p>\n

Another rich approach has been to enable models to learn the graph adjacency matrix from the data and its patterns such as time series similarity between different nodes instead, or in addition to, the usual spatial distance. Variants of this approach are proposed by models that include Dynamic Spatio-Temporal Graph-based CNNs (DST-GCNN) [82], 3D Temporal Graph Convolutional Networks (3D-TGCN) [6], Graph WaveNet [84] and FlowConvGRU [97].<\/p>\n

Finally, other models focus on leveraging other approaches such as the sparsity of traffic data [91], pooling and unpooling layers [93] or unsupervised learning of node representations [86].<\/p>\n

Datasets<\/strong><\/h2>\n

In spite of the differences described above, nearly every model has been experimentally evaluated in similar datasets with a similar configuration. In particular, the timestep of the datasets is, with few exceptions, 5 minutes, and the prediction horizon is 15, 30 and 60 minutes (that is, 3, 6, and 10 timesteps). The extension of the dataset is also very often around 4 months, which is equivalent to about 35000 timesteps.<\/p>\n

Two datasets in particular standout as the most used for benchmarking: METR-LA and PEMS-BAY. These datasets contain traffic information collected from loop sensors at various locations of two networks of freeways in California, one in Los Angeles, the other in the Bay Area. Typically only a small fraction of the data is used. For example, data is aggregated in 5 minutes interval and only between 200 and 1000 sensors are used to test the models.<\/p>\n

<\/p>\n

Figure 6: Sensor distribution of the METR-LA and PEMS-BAY datasets [83]. Reprinted with permission.<\/p>\n

Challenges and research opportunities<\/strong><\/h2>\n

While the results obtained in various traffic forecasting tasks by deep learning models and, notably, graph neural networks have been very successful, there are still a number of open issues and traffic forecasting is still an unsolved problem. These challenges constitute a rich set of research and engineering opportunities [3], [98] which include integrating in a systematic way exogenous factors (such as road accidents and weather), designing more sophisticated evaluation metrics, integrating traffic forecasting with other downstream applications, going from volume or speed prediction to travel time prediction, improving the interpretability of the models and moving from prediction to causation. Additionally, ongoing work tackles the problem of developing Bayesian methods that provide adequate predictions beyond point estimates (such as confidence intervals) and tackling the issue of data ageing and concept drift by developing models that take into account when road segments or bus lines are added or removed from the network.<\/p>\n

Acknowledgments<\/strong><\/h2>\n

This work was partly supported by the projects iLU-DSAIPA\/DS\/0111\/2018 and UID\/CEC\/50021\/2019 funded by the FCT (Funda\u00e7\u00e3o para a Ci\u00eancia e Tecnologia). Work by Jo\u00e3o Rico is supported by a research grant by LNEC (Laborat\u00f3rio Nacional de Engenharia Civil) and FCT.<\/p>\n

References<\/strong><\/h2>\n

United Nations, Department of Economic and Social Affairs, Population Division., \u201cWorld urbanization prospects. the 2018 revision,\u201d ST\/ESA\/SER. A\/421, 2019.<\/p>\n

D. Schrank, B. Eisele, and T. Lomax, \u201c2019 Urban Mobility Report,\u201d Texas A&M Transportation Institute, 2019.<\/p>\n

I. Lana, J. Del Ser, M. Velez, and E. I. Vlahogianni, \u201cRoad Traffic Forecasting: Recent Advances and New Challenges,\u201d IEEE Intell. Transp. Syst. Mag., vol. 10, no. 2, pp. 93\u2013109, 2018.<\/p>\n

Y. Zheng, L. Capra, O. Wolfson, and H. Yang, \u201cUrban Computing: Concepts, Methodologies, and Applications,\u201d ACM Trans. Intell. Syst. Technol., vol. 5, no. 3, pp. 38:1\u201338:55, Sep. 2014.<\/p>\n

E. I. Vlahogianni, M. G. Karlaftis, and J. C. Golias, \u201cShort-term traffic forecasting: Where we are and where we\u2019re going,\u201d Transp. Res. Part C: Emerg. Technol., vol. 43, pp. 3\u201319, 2014.<\/p>\n

B. Yu, M. Li, J. Zhang, and Z. Zhu, \u201c3D Graph Convolutional Networks with Temporal Graphs: A Spatial Information Free Framework For Traffic Forecasting,\u201d arXiv [cs.LG], 03-Mar-2019.<\/p>\n

Z. Cui, K. Henrickson, R. Ke, and Y. Wang, \u201cTraffic Graph Convolutional Recurrent Neural Network: A Deep Learning Framework for Network-Scale Traffic Learning and Forecasting,\u201d arXiv [cs.LG], 20-Feb-2018.<\/p>\n

S. Guo, Y. Lin, N. Feng, C. Song, and H. Wan, \u201cAttention Based Spatial-Temporal Graph Convolutional Networks for Traffic Flow Forecasting,\u201d in Proceedings of the AAAI Conference on Artificial Intelligence, 2019, vol. 33, pp. 922\u2013929.<\/p>\n

Y. Zheng, Urban Computing. MIT Press, 2019.<\/p>\n

Smith Brian L. and Demetsky Michael J., \u201cTraffic Flow Forecasting: Comparison of Modeling Approaches,\u201d J. Transp. Eng., vol. 123, no. 4, pp. 261\u2013266, Jul. 1997.<\/p>\n

K. A. Small, E. T. Verhoef, and R. Lindsey, The economics of urban transportation. Routledge, 2007.<\/p>\n

G. A. Davis and N. L. Nihan, \u201cNonparametric regression and short-term freeway traffic forecasting,\u201d J. Transp. Eng., vol. 117, no. 2, pp. 178\u2013188, 1991.<\/p>\n

D. Chowdhury, L. Santen, and A. Schadschneider, \u201cStatistical physics of vehicular traffic and some related systems,\u201d Phys. Rep., vol. 329, no. 4, pp. 199\u2013329, May 2000.<\/p>\n

M. Saidallah, A. El Fergougui, and A. E. Elalaoui, \u201cA Comparative Study of Urban Road Traffic Simulators,\u201d MATEC Web of Conferences, vol. 81, p. 05002, 2016.<\/p>\n

S. Lee and D. B. Fambro, \u201cApplication of Subset Autoregressive Integrated Moving Average Model for Short- Term Freeway Traffic Volume Forecasting,\u201d Transp. Res. Rec., vol. 1678, no. 1, pp. 179\u2013188, Jan. 1999.<\/p>\n

Williams Billy M. and Hoel Lester A., \u201cModeling and Forecasting Vehicular Traffic Flow as a Seasonal ARIMA Process: Theoretical Basis and Empirical Results,\u201d J. Transp. Eng., vol. 129, no. 6, pp. 664\u2013672, Nov. 2003.<\/p>\n

L. Zhang, Q. Liu, W. Yang, N. Wei, and D. Dong, \u201cAn Improved K-nearest Neighbor Model for Short-term Traffic Flow Prediction,\u201d Procedia – Social and Behavioral Sciences, vol. 96, pp. 653\u2013662, Nov. 2013.<\/p>\n

H. Su, L. Zhang, and S. Yu, \u201cShort-term Traffic Flow Prediction Based on Incremental Support Vector Regression,\u201d in Third International Conference on Natural Computation (ICNC 2007), 2007, vol. 1, pp. 640\u2013645.<\/p>\n

Y. Qi and S. Ishak, \u201cA Hidden Markov Model for short term prediction of traffic conditions on freeways,\u201d Transp. Res. Part C: Emerg. Technol., vol. 43, pp. 95\u2013111, Jun. 2014.<\/p>\n

Y. Kamarianakis and P. Prastacos, \u201cForecasting Traffic Flow Conditions in an Urban Network: Comparison of Multivariate and Univariate Approaches,\u201d Transp. Res. Rec., vol. 1857, no. 1, pp. 74\u201384, Jan. 2003.<\/p>\n

W. Min and L. Wynter, \u201cReal-time road traffic prediction with spatio-temporal correlations,\u201d Transp. Res. Part C: Emerg. Technol., vol. 19, no. 4, pp. 606\u2013616, Aug. 2011.<\/p>\n

J. Kwon and K. Murphy, \u201cModeling freeway traffic with coupled HMMs,\u201d Technical report, Univ. California, Berkeley, 2000.<\/p>\n

J. Xu, D. Deng, U. Demiryurek, C. Shahabi, and M. van der Schaar, \u201cMining the Situation: Spatiotemporal Traffic Prediction With Big Data,\u201d IEEE Journal of Selected Topics in Signal Processing, vol. 9, no. 4. pp. 702\u2013715, 2015.<\/p>\n

Y. LeCun, Y. Bengio, and G. Hinton, \u201cDeep learning,\u201d Nature, vol. 521, no. 7553, pp. 436\u2013444, May 2015.<\/p>\n

A. Krizhevsky, I. Sutskever, and G. E. Hinton, \u201cImageNet Classification with Deep Convolutional Neural Networks,\u201d in Advances in Neural Information Processing Systems 25, F. Pereira, C. J. C. Burges, L. Bottou, and<\/p>\n

K. Q. Weinberger, Eds. Curran Associates, Inc., 2012, pp. 1097\u20131105.<\/p>\n

R. Collobert, J. Weston, L. Bottou, M. Karlen, K. Kavukcuoglu, and P. Kuksa, \u201cNatural Language Processing (Almost) from Scratch,\u201d J. Mach. Learn. Res., vol. 12, no. Aug, pp. 2493\u20132537, 2011.<\/p>\n

J. Ma, R. P. Sheridan, A. Liaw, G. E. Dahl, and V. Svetnik, \u201cDeep Neural Nets as a Method for Quantitative Structure\u2013 Activity Relationships,\u201d Journal of Chemical Information and Modeling, vol. 55, no. 2. pp. 263\u2013274, 2015.<\/p>\n

H. Wang, N. Wang, and D.-Y. Yeung, \u201cCollaborative Deep Learning for Recommender Systems,\u201d in Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, 2015,<\/p>\n

pp. 1235\u20131244.<\/p>\n

V. Mnih et al., \u201cHuman-level control through deep reinforcement learning,\u201d Nature, vol. 518, no. 7540. pp. 529\u2013 533, 2015.<\/p>\n

W. Huang, G. Song, H. Hong, and K. Xie, \u201cDeep Architecture for Traffic Flow Prediction: Deep Belief Networks With Multitask Learning,\u201d IEEE Trans. Intell. Transp. Syst., vol. 15, no. 5, pp. 2191\u20132201, Oct. 2014.<\/p>\n

X. Ma, Z. Tao, Y. Wang, H. Yu, and Y. Wang, \u201cLong short-term memory neural network for traffic speed prediction using remote microwave sensor data,\u201d Transp. Res. Part C: Emerg. Technol., vol. 54, pp. 187\u2013197, May 2015.<\/p>\n

R. Yu, Y. Li, C. Shahabi, U. Demiryurek, and Y. Liu, \u201cDeep Learning: A Generic Approach for Extreme Condition Traffic Forecasting,\u201d in Proceedings of the 2017 SIAM International Conference on Data Mining, Society for Industrial and Applied Mathematics, 2017, pp. 777\u2013785.<\/p>\n

Z. Cui, R. Ke, and Y. Wang, \u201cDeep Bidirectional and Unidirectional LSTM Recurrent Neural Network for Network-wide Traffic Speed Prediction,\u201d arXiv [cs.LG], 07-Jan-2018.<\/p>\n

X. Ma, Z. Dai, Z. He, J. Ma, Y. Wang, and Y. Wang, \u201cLearning Traffic as Images: A Deep Convolutional Neural Network for Large-Scale Transportation Network Speed Prediction,\u201d Sensors , vol. 17, no. 4, Apr. 2017.<\/p>\n

J. Zhang, Y. Zheng, and D. Qi, \u201cDeep spatio-temporal residual networks for citywide crowd flows prediction,\u201d in Thirty-First AAAI Conference on Artificial Intelligence, 2017.<\/p>\n

H. Yu, Z. Wu, S. Wang, Y. Wang, and X. Ma, \u201cSpatiotemporal Recurrent Convolutional Networks for Traffic Prediction in Transportation Networks,\u201d Sensors , vol. 17, no. 7, Jun. 2017.<\/p>\n

T. N. Kipf and M. Welling, \u201cSemi-Supervised Classification with Graph Convolutional Networks,\u201d arXiv [cs.LG], 09-Sep- 2016.<\/p>\n

Q. Liu, M. Allamanis, M. Brockschmidt, and A. Gaunt, \u201cConstrained Graph Variational Autoencoders for Molecule Design,\u201d in Advances in Neural Information Processing Systems 31, S. Bengio, H. Wallach, H. Larochelle, K. Grauman,<\/p>\n

N. Cesa-Bianchi, and R. Garnett, Eds. Curran Associates, Inc., 2018, pp. 7795\u20137804.<\/p>\n

F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini, \u201cThe graph neural network model,\u201d IEEE Trans. Neural Netw., vol. 20, no. 1, pp. 61\u201380, Jan. 2009.<\/p>\n

M. Defferrard, X. Bresson, and P. Vandergheynst, \u201cConvolutional Neural Networks on Graphs with Fast Localized Spectral Filtering,\u201d in Advances in Neural Information Processing Systems 29, D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, Eds. Curran Associates, Inc., 2016, pp. 3844\u20133852.<\/p>\n

P. W. Battaglia et al., \u201cRelational inductive biases, deep learning, and graph networks,\u201d arXiv [cs.LG], 04-Jun- 2018.<\/p>\n

M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst, \u201cGeometric Deep Learning: Going beyond Euclidean data,\u201d IEEE Signal Process. Mag., vol. 34, no. 4, pp. 18\u201342, Jul. 2017.<\/p>\n

W. L. Hamilton, R. Ying, and J. Leskovec, \u201cRepresentation Learning on Graphs: Methods and Applications,\u201d arXiv [cs.SI], 17-Sep-2017.<\/p>\n

Z. Zhang, P. Cui, and W. Zhu, \u201cDeep Learning on Graphs: A Survey,\u201d arXiv [cs.LG], 11-Dec-2018.<\/p>\n

Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu, \u201cA Comprehensive Survey on Graph Neural Networks,\u201d arXiv [cs.LG], 03-Jan-2019.<\/p>\n

J. Zhou et al., \u201cGraph Neural Networks: A Review of Methods and Applications,\u201d arXiv [cs.LG], 20-Dec-2018.<\/p>\n

Y. Li, D. Tarlow, M. Brockschmidt, and R. Zemel, \u201cGated Graph Sequence Neural Networks,\u201d arXiv [cs.LG], 17- Nov-2015.<\/p>\n

L. Ruiz, F. Gama, and A. Ribeiro, \u201cGated Graph Convolutional Recurrent Neural Networks,\u201d arXiv [cs.LG], 05- Mar-2019.<\/p>\n

H. Dai, Z. Kozareva, B. Dai, A. Smola, and L. Song, \u201cLearning Steady-States of Iterative Algorithms over Graphs,\u201d in Proceedings of the 35th International Conference on Machine Learning, 2018, vol. 80, pp. 1106\u2013 1114.<\/p>\n

J. You, R. Ying, X. Ren, W. L. Hamilton, and J. Leskovec, \u201cGraphRNN: Generating Realistic Graphs with Deep Auto- regressive Models,\u201d arXiv [cs.LG], 24-Feb-2018.<\/p>\n

J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun, \u201cSpectral Networks and Locally Connected Networks on Graphs,\u201d arXiv [cs.LG], 21-Dec-2013.<\/p>\n

O. Levy and Y. Goldberg, \u201cNeural Word Embedding as Implicit Matrix Factorization,\u201d in Advances in Neural Information Processing Systems 27, Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, Eds. Curran Associates, Inc., 2014, pp. 2177\u20132185.<\/p>\n

D. K. Duvenaud et al., \u201cConvolutional Networks on Graphs for Learning Molecular Fingerprints,\u201d in Advances in Neural Information Processing Systems 28, C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, Eds. Curran Associates, Inc., 2015, pp. 2224\u20132232.<\/p>\n

P. Veli\u010dkovi\u0107, G. Cucurull, A. Casanova, A. Romero, P. Li\u00f2, and Y. Bengio, \u201cGraph Attention Networks,\u201d arXiv [stat.ML], 30-Oct-2017.<\/p>\n

J. Zhang, X. Shi, J. Xie, H. Ma, I. King, and D.-Y. Yeung, \u201cGaAN: Gated Attention Networks for Learning on Large and Spatiotemporal Graphs,\u201d arXiv [cs.LG], 20-Mar-2018.<\/p>\n

D. Wang, P. Cui, and W. Zhu, \u201cStructural Deep Network Embedding,\u201d in Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, California, USA, 2016, pp. 1225\u20131234.<\/p>\n

T. N. Kipf and M. Welling, \u201cVariational Graph Auto-Encoders,\u201d arXiv [stat.ML], 21-Nov-2016.<\/p>\n

Y. Li, O. Vinyals, C. Dyer, R. Pascanu, and P. Battaglia, \u201cLearning Deep Generative Models of Graphs,\u201d arXiv [cs.LG], 08-Mar-2018.<\/p>\n

M. Simonovsky and N. Komodakis, \u201cGraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders,\u201d in Artificial Neural Networks and Machine Learning \u2013 ICANN 2018, 2018, pp. 412\u2013422.<\/p>\n

N. De Cao and T. Kipf, \u201cMolGAN: An implicit generative model for small molecular graphs,\u201d arXiv [stat.ML], 30-May- 2018.<\/p>\n

S. Pan, R. Hu, S.-F. Fung, G. Long, J. Jiang, and C. Zhang, \u201cLearning Graph Embedding With Adversarial Training Methods,\u201d IEEE Transactions on Cybernetics. pp. 1\u201313, 2019.<\/p>\n

A. Sperduti and A. Starita, \u201cSupervised neural networks for the classification of structures,\u201d IEEE Trans. Neural Netw., vol. 8, no. 3, pp. 714\u2013735, 1997.<\/p>\n

M. Gori, G. Monfardini, and F. Scarselli, \u201cA new model for learning in graph domains,\u201d in Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., 2005, vol. 2, pp. 729\u2013734 vol. 2.<\/p>\n

M. A. Khamsi and W. A. Kirk, An Introduction to Metric Spaces and Fixed Point Theory. John Wiley & Sons, 2011.<\/p>\n

J. Chung, C. Gulcehre, K. Cho, and Y. Bengio, \u201cEmpirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling,\u201d arXiv [cs.NE], 11-Dec-2014.<\/p>\n

C. Gallicchio and A. Micheli, \u201cGraph Echo State Networks,\u201d in The 2010 International Joint Conference on Neural Networks (IJCNN), 2010, pp. 1\u20138.<\/p>\n

C. Zhuang and Q. Ma, \u201cDual graph convolutional networks for graph-based semi-supervised classification,\u201d Proceedings of the 2018 World Wide Web Conference, 2018.<\/p>\n

D. Bahdanau, K. Cho, and Y. Bengio, \u201cNeural Machine Translation by Jointly Learning to Align and Translate,\u201d arXiv [cs.CL], 01-Sep-2014.<\/p>\n

A. Vaswani et al., \u201cAttention is All you Need,\u201d in Advances in Neural Information Processing Systems 30, I. Guyon, U.<\/p>\n

V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds. Curran Associates, Inc., 2017, pp. 5998\u20136008.<\/p>\n

J. B. Lee, R. A. Rossi, S. Kim, N. K. Ahmed, and E. Koh, \u201cAttention Models in Graphs: A Survey,\u201d arXiv [cs.AI], 20-Jul-2018.<\/p>\n

P. Vincent, H. Larochelle, I. Lajoie, Y. Bengio, and P.-A. Manzagol, \u201cStacked Denoising Autoencoders: Learning Useful Representations in a Deep Network with a Local Denoising Criterion,\u201d J. Mach. Learn. Res., vol. 11, no. Dec, pp. 3371\u2013 3408, 2010.<\/p>\n

D. P. Kingma and M. Welling, \u201cAuto-Encoding Variational Bayes,\u201d arXiv [stat.ML], 20-Dec-2013.<\/p>\n

I. Goodfellow et al., \u201cGenerative Adversarial Nets,\u201d in Advances in Neural Information Processing Systems 27, Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, Eds. Curran Associates, Inc., 2014, pp. 2672\u20132680.<\/p>\n

X. Wang, R. Girshick, A. Gupta, and K. He, \u201cNon-local neural networks,\u201d in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2018, pp. 7794\u20137803.<\/p>\n

J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl, \u201cNeural Message Passing for Quantum Chemistry,\u201d in Proceedings of the 34th International Conference on Machine Learning – Volume 70, 2017, pp. 1263\u20131272.<\/p>\n

A. Paszke et al., \u201cAutomatic differentiation in PyTorch,\u201d 28-Oct-2017.<\/p>\n

M. Abadi et al., \u201cTensorflow: A system for large-scale machine learning,\u201d in 12th ${USENIX} Symposium on Operating Systems Design and Implementation ({OSDI}$ 16), 2016, pp. 265\u2013283.<\/p>\n

M. Wang et al., \u201cDeep graph library, 2018,\u201d URL http:\/\/dgl.<\/a> ai. Alibaba, \u201cEuler,\u201d 2019.<\/p>\n

M. Fey and J. E. Lenssen, \u201cFast Graph Representation Learning with PyTorch Geometric,\u201d arXiv [cs.LG], 06-Mar- 2019.<\/p>\n

D. Chai, L. Wang, and Q. Yang, \u201cBike Flow Prediction with Multi-graph Convolutional Networks,\u201d in Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Seattle, Washington, 2018, pp. 397\u2013400.<\/p>\n

M. Wang et al., \u201cDynamic Spatio-temporal Graph-based CNNs for Traffic Prediction,\u201d arXiv [cs.CV], 05-Dec- 2018.<\/p>\n

Y. Li, R. Yu, C. Shahabi, and Y. Liu, \u201cDiffusion Convolutional Recurrent Neural Network: Data-Driven Traffic Forecasting,\u201d arXiv [cs.LG], 06-Jul-2017.<\/p>\n

Z. Wu, S. Pan, G. Long, J. Jiang, and C. Zhang, \u201cGraph WaveNet for Deep Spatial-Temporal Graph Modeling,\u201d arXiv [cs.LG], 31-May-2019.<\/p>\n

Y. Zhang, T. Cheng, and Y. Ren, \u201cA graph deep learning method for short7term traffic forecasting on large road networks,\u201d Computer-Aided Civil and Infrastructure Engineering. 2019.<\/p>\n

F. L. Opolka, A. Solomon, C. Cangea, P. Veli\u010dkovi\u0107, P. Li\u00f2, and R. Devon Hjelm, \u201cSpatio-Temporal Deep Graph Infomax,\u201d arXiv [cs.LG], 12-Apr-2019.<\/p>\n

C. Chen et al., \u201cGated Residual Recurrent Graph Neural Networks for Traffic Prediction,\u201d in Proceedings of the AAAI Conference on Artificial Intelligence, 2019, vol. 33, pp. 485\u2013492.<\/p>\n

N. Zhang, X. Guan, J. Cao, X. Wang, and H. Wu, \u201cA Hybrid Traffic Speed Forecasting Approach Integrating Wavelet Transform and Motif-based Graph Convolutional Recurrent Neural Network,\u201d arXiv [cs.CV], 14-Apr- 2019.<\/p>\n

X. Cheng, R. Zhang, J. Zhou, and W. Xu, \u201cDeepTransport: Learning Spatial-Temporal Dependency for Traffic Condition Forecasting,\u201d in 2018 International Joint Conference on Neural Networks (IJCNN), 2018, pp. 1\u20138.<\/p>\n

J. Sun, J. Zhang, Q. Li, X. Yi, and Y. Zheng, \u201cPredicting Citywide Crowd Flows in Irregular Regions Using Multi- View Graph Convolutional Networks,\u201d arXiv [cs.CV], 19-Mar-2019.<\/p>\n

B. Wang, X. Luo, F. Zhang, B. Yuan, A. L. Bertozzi, and P. Jeffrey Brantingham, \u201cGraph-Based Deep Modeling and Real Time Forecasting of Sparse Spatio-Temporal Data,\u201d arXiv [cs.LG], 02-Apr-2018.<\/p>\n

B. Yu, H. Yin, and Z. Zhu, \u201cSpatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting,\u201d arXiv [cs.LG], 14-Sep-2017.<\/p>\n

B. Yu, H. Yin, and Z. Zhu, \u201cST-UNet: A Spatio-Temporal U-Network for Graph-structured Time Series Modeling,\u201d arXiv [cs.LG], 13-Mar-2019.<\/p>\n

L. Zhao et al., \u201cT-GCN: A Temporal Graph ConvolutionalNetwork for Traffic Prediction,\u201d arXiv [cs.LG], 12- Nov-2018.<\/p>\n

H. Yao, X. Tang, H. Wei, G. Zheng, and Z. Li, \u201cRevisiting spatial-temporal similarity: A deep learning framework for traffic prediction,\u201d in AAAI Conference on Artificial Intelligence, 2019.<\/p>\n

J. Atwood and D. Towsley, \u201cDiffusion-convolutional neural networks,\u201d in Advances in Neural Information Processing Systems, 2016, pp. 1993\u20132001.<\/p>\n

X. Zhou, Y. Shen, and L. Huang, \u201cRevisiting Flow Information for Traffic Prediction,\u201d arXiv [eess.SP], 03-Jun- 2019.<\/p>\n

Y. Li and C. Shahabi, \u201cA Brief Overview of Machine Learning Methods for Short-term Traffic Forecasting and Future Directions,\u201d SIGSPATIAL Special, vol. 10, no. 1, pp. 3\u20139, Jun. 2018.<\/p>\n","protected":false},"excerpt":{"rendered":"

Jo\u00e3o Rico*1,2,3, Jos\u00e9 Barateiro1,2, Arlindo Oliveira2,3 1Laborat\u00f3rio Nacional de Engenharia Civil, Av. do Brasil 101, Lisbon, Portugal 2INESC-ID, R. Alves Redol 9, Lisbon, Portugal 3Instituto Superior T\u00e9cnico, University of Lisbon, Lisbon, Portugal jmrico@lnec.pt, jbarateiro@lnec.pt, arlindo.oliveira@tecnico.ulisboa.pt Abstract The significant increase in world population and urbanisation has brought several important challenges, in particular regarding the sustainability, maintenance […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","template":"","meta":{"footnotes":""},"doc_category":[12],"glossaries":[],"doc_tag":[],"knowledge_base":[3],"class_list":["post-337","docs","type-docs","status-publish","hentry","doc_category-articles-issue2","knowledge_base-issue-2"],"year_month":"2026-07","word_count":7386,"total_views":"2890","reactions":{"happy":"0","normal":"0","sad":"0"},"author_info":{"name":"support","author_nicename":"support","author_url":"https:\/\/omaintec.org\/journal\/index.php\/author\/support\/"},"doc_category_info":[{"term_name":"Articles2","term_url":"https:\/\/omaintec.org\/journal\/index.php\/docs\/issue-2\/articles-issue2\/"}],"doc_tag_info":[],"knowledge_base_info":[{"term_name":"ISSUE# 2","term_url":"https:\/\/omaintec.org\/journal\/index.php\/docs\/issue-2\/","term_slug":"issue-2"}],"knowledge_base_slug":["issue-2"],"_links":{"self":[{"href":"https:\/\/omaintec.org\/journal\/index.php\/wp-json\/wp\/v2\/docs\/337","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/omaintec.org\/journal\/index.php\/wp-json\/wp\/v2\/docs"}],"about":[{"href":"https:\/\/omaintec.org\/journal\/index.php\/wp-json\/wp\/v2\/types\/docs"}],"author":[{"embeddable":true,"href":"https:\/\/omaintec.org\/journal\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/omaintec.org\/journal\/index.php\/wp-json\/wp\/v2\/comments?post=337"}],"version-history":[{"count":3,"href":"https:\/\/omaintec.org\/journal\/index.php\/wp-json\/wp\/v2\/docs\/337\/revisions"}],"predecessor-version":[{"id":1231,"href":"https:\/\/omaintec.org\/journal\/index.php\/wp-json\/wp\/v2\/docs\/337\/revisions\/1231"}],"wp:attachment":[{"href":"https:\/\/omaintec.org\/journal\/index.php\/wp-json\/wp\/v2\/media?parent=337"}],"wp:term":[{"taxonomy":"doc_category","embeddable":true,"href":"https:\/\/omaintec.org\/journal\/index.php\/wp-json\/wp\/v2\/doc_category?post=337"},{"taxonomy":"glossaries","embeddable":true,"href":"https:\/\/omaintec.org\/journal\/index.php\/wp-json\/wp\/v2\/glossaries?post=337"},{"taxonomy":"doc_tag","embeddable":true,"href":"https:\/\/omaintec.org\/journal\/index.php\/wp-json\/wp\/v2\/doc_tag?post=337"},{"taxonomy":"knowledge_base","embeddable":true,"href":"https:\/\/omaintec.org\/journal\/index.php\/wp-json\/wp\/v2\/knowledge_base?post=337"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}