Traffic prediction is a critical task in spatial-temporal forecasting with broad applications in travel planning and urban management. To model the complex spatial-temporal dependencies in traffic data, Spatial-Temporal Graph Convolutional Networks (STGCNs) have been widely employed, achieving advanced performance. However, when applied to large-scale road networks, the quadratic computational complexity of traditional graph convolution operations severely limits their scalability. Several methods attempt to address this issue through approximation, compression, or spatial partitioning. Nevertheless, these methods often either fail to achieve sufficient computational efficiency or compromise prediction accuracy. To address these challenges, we propose a Regularized Adaptive Graph Convolution (RAGC) model. First, to ensure scalability on large road networks, we develop the Efficient Cosine Operator (ECO), which performs graph convolution based on the cosine similarity of node embeddings with linear time complexity. Second, we introduce a regularized adaptive graph convolution framework that combines Stochastic Shared Embedding (SSE) and adaptive graph convolution through a residual difference mechanism. This design enables the model to learn high-quality node embeddings, thereby improving prediction accuracy while maintaining computational efficiency. Extensive experiments on four large-scale real-world traffic datasets show that RAGC consistently outperforms state-of-the-art methods in terms of prediction accuracy and exhibits competitive computational efficiency. The code is available at: https://github.com/wkq-wukaiqi/RAGC.

Traffic flow forecasting is a critical spatio-temporal data mining task with wide-ranging applications in intelligent route planning and dynamic traffic management. Recent advancements in deep learning, particularly through Graph Neural Networks (GNNs), have significantly enhanced the accuracy of these forecasts by capturing complex spatio-temporal dynamics. However, the scalability of GNNs remains a challenge due to their exponential growth in model complexity with increasing nodes in the graph. Existing methods to address this issue, including sparsification, decomposition, and kernel-based approaches, either do not fully resolve the complexity issue or risk compromising predictive accuracy. This paper introduces GraphSparseNet (GSNet), a novel framework designed to improve both the scalability and accuracy of GNN-based traffic forecasting models. GraphSparseNet is comprised of two core modules: the Feature Extractor and the Relational Compressor. These modules operate with linear time and space complexity, thereby reducing the overall computational complexity of the model to a linear scale. Our extensive experiments on multiple real-world datasets demonstrate that GraphSparseNet not only significantly reduces training time by 3.51x compared to state-of-the-art linear models but also maintains high predictive performance.

Crowd flows prediction is an important problem for traffic management and public safety. Graph Convolutional Network (GCN), known for its ability to effectively capture and utilize topological information, has demonstrated significant advancements in addressing this problem. However, GCN-based models were often based on predefined crowd-flow graphs via historical movement behaviors of human beings and traffic vehicles, which ignored the abnormal changes in crowd flows. In this study, we propose a multi-scale fusion GCN-based framework with Tucker decomposition named mTDNet to enhance dynamic GCN for crowd flows prediction. Following the paradigm of extant methods, we also employ the predefined crowd-flow graphs as a part of mTDNet to effectively capture the historical movement behaviors of crowd flows. To capture the abnormal changes, we propose a Tucker decomposition-based network with the product of the adjacency matrix of historical movement pattern graphs and an Adaptive Learning Tensor ( ALT ) by reconstructing the crowd flows. Particularly, we utilize the Tucker decomposition scheme to decompose ALT , which enhances the dynamic learning of graph structures, allowing for effective capturing of the dynamic changes in crowd flow, including abnormal changes. Furthermore, a multi-scale 3DGCN is utilized to mine and fuse the multi-scale spatio-temporal information from crowd flows, to further boost the mTDNet prediction performance. Experiments conducted on two real-world datasets showed that the proposed mTDNet surpasses other crowd flow prediction methods.

Traffic flow forecasting is a classical spatio-temporal data mining problem with many real-world applications. Recently, various methods based on Graph Neural Networks (GNN) have been proposed for the problem and achieved impressive prediction performance. However, we argue that the majority of existing methods disregarding the importance of certain nodes (referred to as pivotal nodes) that naturally exhibit extensive connections with multiple other nodes. Predicting on pivotal nodes poses a challenge due to their complex spatio-temporal dependencies compared to other nodes. In this paper, we propose a novel GNN-based method called Spatio-Temporal Pivotal Graph Neural Networks (STPGNN) to address the above limitation. We introduce a pivotal node identification module for identifying pivotal nodes. We propose a novel pivotal graph convolution module, enabling precise capture of spatio-temporal dependencies centered around pivotal nodes. Moreover, we propose a parallel framework capable of extracting spatio-temporal traffic features on both pivotal and non-pivotal nodes. Experiments on seven real-world traffic datasets verify our proposed method's effectiveness and efficiency compared to state-of-the-art baselines.

Anomaly detection in time series data (e.g., sensor data) is becoming a fundamental research problem that has various applications. Due to the complex inter-sensor relationships, it is challenging to detect anomalous events such as system faults and attacks hidden the high-dimensional time series. Recent advancements in deep learning approaches such as Graph Neural Networks (GNN) have greatly improved anomaly detection performance in time series data. However, existing methods do not learn the dependence relationships between sensors and groups of sensors and may not efficiently detect anomalous events in time series. In this paper, we propose a novel approach GGNN (short for Grouped Graph Neural Networks) that combines a structure learning approach with graph neural networks. In particular, GGNN learns the graph structure containing groups of sensors, which are represented by virtual nodes. In addition, we use the learned graph structure and attention weights to explain the detected anomalies. The experiments on three real world datasets show our superiority in detection accuracy, anomaly diagnosis, and model interpretation compared with state-of-the-art methods.

The computation of a group Steiner tree (GST) in various types of graph networks, such as social network and transportation network, is a fundamental graph problem in graphs, with important applications. In these graphs, time is a common and necessary dimension, for example, time information in social network can be the time when a user sends a message to another user. Graphs with time information can be called temporal graphs. However, few studies have been conducted on GST in terms of temporal graphs. This study analyzes the computation of GST for temporal graphs, i.e., the computation of temporal GST (TGST), which is shown to be an NP‐hard problem. We propose an efficient solution based on a dynamic programming algorithm for our problem. This study adopts new optimization techniques, including graph simplification, state pruning, and A∗ search, are adopted to dramatically reduce the algorithm search space. Moreover, we consider three extensions for our problem, namely the TGST with unspecified tree root, the progressive search of TGST, and the top‐N search of TGST. Results of the experimental study performed on real temporal networks verify the efficiency and effectiveness of our algorithms.

Traffic prediction is a classical spaial-temporal prediction problem with many real-world applications.In general, existing traffic prediction methods capture the complex spatial-­temporal features by iterative mechanism or non-iterative mechanism. However, the iterative mechanism often causes the prediction error accumulation and the non-­iterative mechanism is hard to capture the dynamic propagation information. The shortcomings of both mechanisms lead to their poor performance in long-­term prediction tasks. Target at the shortcomings of existing methods, in this paper, we propose a novel deep learning framework called Long-term Traffic Prediction based on Hybrid Model (LTPHM), which is designed to simulate the dynamic transmission process of traffic information on the road network by connecting the prediction values of the current step with the next step. Each spatial-­temporal module uses graph convolution (GCN) with an adaptive matrix to capture spatial dependence. Besides, we use Gated Dilated Convolution Networks (GDCN) and Gated Linear Unit convolution networks (GLU) to capture temporal dependence. Since LTPHM integrates the advantages of both iterative and non-iterative prediction, it can efficiently capture the complex and dynamic spatial-temporal features, especially the long-range temporal sequences. Experiments with three real-world traffic datasets demonstrate the effectiveness of our proposed model.

Traffic prediction is a classical spatial-temporal prediction problem with many real-world applications such as intelligent route planning, dynamic traffic management, and smart location-based applications. Due to the high nonlinearity and complexity of traffic data, deep learning approaches have attracted much interest in recent years. However, few methods are satisfied with both long and short-term prediction tasks. Target at the shortcomings of existing studies, in this paper, we propose a novel deep learning framework called Long Short-term Graph Convolutional Networks (LSGCN) to tackle both traffic prediction tasks. In our framework, we propose a new graph attention network called cosAtt, and integrate both cosAtt and graph convolution networks (GCN) into a spatial gated block. By the spatial gated block and gated linear units convolution (GLU), LSGCN can efficiently capture complex spatial-temporal features and obtain stable prediction results. Experiments with three real-world traffic datasets verify the effectiveness of LSGCN.