Spatio-temporal prediction is fundamental to a wide range of applications, including traffic flow forecasting and air quality monitoring. However, real-world spatio-temporal systems are rarely governed by homogeneous or synchronized interactions. Spatial dependencies often vary across regions, temporal patterns evolve at multiple scales, and the influence of one location on another may emerge with dynamic, region-specific delays rather than in a synchronized manner. These heterogeneous and asynchronous lag characteristics pose substantial challenges to accurate prediction, whereas most existing methods rely on static spatial graphs or synchronized temporal modeling, which limits their ability to capture complex real-world dynamics. To address this, we propose the lag-heterogeneity guided spatio-temporal graph neural network (LH-GSTGNN). Rather than relying on stationary assumptions, LH-GSTGNN treats lag heterogeneity as an explicit modeling target. It characterizes evolving spatial dependencies, captures temporal dynamics across multiple ranges, and highlights delayed responses embedded in intermediate representations. In this way, the proposed framework preserves heterogeneous and asynchronous interactions that are otherwise prone to being smoothed out, yielding a more faithful representation of real-world spatio-temporal dynamics. Extensive experiments on nine real-world datasets covering traffic flow, traffic speed, and air quality prediction show that LH-GSTGNN consistently outperforms strong baselines, achieving up to 4.9% lower MAE and 2.9% lower RMSE than the second-best method. Visualization-based case studies further demonstrate its effectiveness in modeling both spatial heterogeneity and diverse lagged fluctuations.

Abstract Traffic prediction has attracted a lot of attention in recent years. However, it is challenging due to the dynamic and heterogeneous spatial–temporal correlations. Most of the existing methods adopt the attention mechanism to capture the dynamic spatial features, but it is difficult for the attention mechanism to learn the real-time change of spatial dependencies, which restrict accurate spatial dependencies learning. Furthermore, most methods are out at elbows when solving heterogeneous spatial–temporal data. To overcome these problems, we propose a novel traffic prediction model called Dynamic spatial–temporal Heterogeneous Graph Convolution Network. Different from the existing methods, we have designed a dynamic localized graph and a corresponding adaptive localized graph convolution network, which are capable of simultaneously capturing dynamic and heterogeneous spatial correlations. We propose a gated adaptive temporal convolution network to capture the temporal heterogeneity of traffic data and enjoy global receptive fields. Finally, a global correlations fusion network is provided to incorporate the global spatial–temporal correlations. Compared with 11 baselines, our proposed model achieves state-of-the-art performance in the accuracy of prediction.

Spatial temporal forecasting of urban sensors is essentially important for many urban systems, such as intelligent transportation and smart cities. However, due to the problem of hardware failure or network failure, there are some missing values or missing monitoring sensors that need to be interpolated. Recent research on deep learning has made substantial progress on imputation problem, especially temporal aspect (i.e., time series imputation), while little attention has been paid to spatial aspect (both dynamic and static) and long-term temporal dependencies. In this article, we proposed a spatial temporal imputation model, named Long Short-Term Graph Convolution Networks (LSTGCN), which includes gated temporal extraction (GTE) module, multi-head attention-based temporal capture (MHAT) module, long-term periodic temporal encoding (LPTE) module, and bidirectional spatial graph convolution (BSGC) module. The GTE adopts a gated mechanism to filter short-term temporal information, while the MHAT utilizes position encoding to enhance the difference of each timestamps, then use multi-head attention to capture short-term temporal dependency. The BSGC is adopted to handle with spatial relationships between sensor nodes. And we design a periodic encoding technique to process long-term temporal dependencies. The BSGC handles spatial relationships between sensor nodes, and a periodic encoding technique is used to process long-term temporal dependencies. Our experimental analysis includes completion and forecasting tasks, as well as transfer and ablation analyses. The results show that our proposed model outperforms state-of-the-art baselines on real-world datasets.

Recent studies have focused on using natural language (NL) to automatically retrieve useful data from database (DB) systems. As an important component of autonomous DB systems, the NL-to-SQL technique can assist DB administrators in writing high-quality SQL statements and make persons with no SQL background knowledge learn complex SQL languages. However, existing studies cannot deal with the issue that the expression of NL inevitably mismatches the implementation details of SQLs, and the large number of out-of-domain (OOD) words makes it difficult to predict table columns. In particular, it is difficult to accurately convert NL into SQL in an end-to-end fashion. Intuitively, it facilitates the model to understand the relations if a "bridge" [transition representation (TR)] is employed to make it compatible with both NL and SQL in the phase of conversion. In this article, we propose an automatic SQL generator with TR called GTR in cross-domain DB systems. Specifically, GTR contains three SQL generation steps: 1) GTR learns the relation between questions and DB schemas; 2) GTR uses a grammar-based model to synthesize a TR; and 3) GTR predicts SQL from TR based on the rules. We conduct extensive experiments on two commonly used datasets, that is, WikiSQL and Spider. On the testing set of the Spider and WikiSQL datasets, the results show that GTR achieves 58.32% and 71.29% exact matching accuracy which outperforms the state-of-the-art methods, respectively.

Recently, group link prediction has received increasing attention due to its important role in analyzing relationships between individuals and groups. However, most existing group link prediction methods emphasize static settings or only make cursory exploitation of historical information, so they fail to obtain good performance in dynamic applications. To this end, we attempt to solve the group link prediction problem in continuous-time dynamic scenes with fine-grained temporal information. We propose a novel continuous-time group link prediction method CTGLP to capture the patterns of future link formation between individuals and groups. A new graph neural network CTGNN is presented to learn the latent representations of individuals by biasedly aggregating neighborhood information. Moreover, we design an importance-based group modeling function to model the embedding of a group based on its known members. CTGLP eventually learns a probability distribution and predicts the link target. Experimental results on various datasets with and without unseen nodes show that CTGLP outperforms the state-of-the-art methods by 13.4% and 13.2% on average.

Abstract Spatial–temporal graph neural network has drawn more and more attention in recent years and is widely used to various real-world applications. However, learning the spatial–temporal graph neural network structure presents unique challenges including: (i) the dynamic spatial correlation; (ii) the dynamic temporal correlation. Even the existing methods take into account the spatial correlation, they still learn the static road network structure information, which cannot reflect the dynamic of road relations. Some of the works has focused on modeling the long-term time series, but the improvements have been limited tightly. To overcome these challenges, we proposed a novel approach called Multi-View Spatial–Temporal Graph Neural Network. Differ from the existing research, we designed a multi-view temporal transformer module to extract dynamic temporal correlation and enhance the expression of medium and long-term temporal features. We propose a multi-view spatial structure and a corresponding multi-view graph convolutional module, which are capable of simultaneously combining the features of static road network structure and dynamic changes. Compared with 11 baselines, our proposed model has achieved significant improvement in the accuracy of prediction.

Abstract Graph partitioning is an NP-hard combinatorial optimization problem, and is a fundamental step in distributing workloads on parallel compute systems, circuit placement, and sparse matrix reordering. The proposed heuristic algorithms such as streaming graph partitioning provide solutions to large-scale graph in a reasonable amount of time. However, the ability of breaking out of local minima in existing these methods is very limited as they are simple in reflecting the connectivity between vertices in real graphs with power-law distribution characteristic. As hill climbing algorithm is a local search method, it can be adopted to improve the result of graph partitioning. However, directly adopting the existing hill climbing algorithm to graph partitioning will result in local minima and poor convergence speed during the iterative process. In this paper, we propose an improved hill climbing graph partitioning algorithm based on clustering. Instead of taking a single vertex as a basic unit, the proposed method considers a cluster consisting of a series of vertices as a hill to move during each iteration. The method uses a new metric that considers both balance and edgecuts to look for the most beneficial cluster as the hill. With these improvements, the method provides a strong power to break out of local minima and achieve an adaptive tradeoff between balance and edgecuts. Experimental results on real-world graphs show that the proposed algorithm substantially reduces edgecuts within a controlled imbalance range.

Traffic prediction is the core task of intelligent transportation system (ITS) and accurate traffic prediction can greatly improve the utilization of public resources. Dynamic interaction of multiple spatial relationships will influence the accuracy of traffic prediction. However, many existing methods only consider static spatial relationships, which restricts the accuracy of the prediction. To address the above problem, in this article, we propose the Dynamic Multi-Graph Fusion Network (DMGF-Net) to model the spatial-temporal correlations in traffic network. In the DMGF-Net, the fusion graph is designed to leverage and extract the various spatial correlations between different regions by fusing spatial graph, semantic graph, and spatial-semantic graph. Further, to dynamically learn the importance of different neighbors, we design the Dynamic Spatial-Temporal Unit (DSTU), which can adjust the aggregation weights of different neighbors by combining the convolution operation and the attention mechanism. It can selectively aggregate spatial-temporal features from different neighbors. Extensive experiments on three datasets demonstrate that effectiveness of our model, especially on PEMS08, our model achieves an increase of about 8.55% and 7.55% in terms of MAE and RMSE than the static model STGCN.

Due to sensor failure or power failure, the spatiotemporal data missing tends to have a greater impact on downstream tasks. Meanwhile, if sensors are scarce, some spatial positions without sensors need data augmentation. Existing workarounds focus on spatial information, often ignoring temporal information, or modeling the spatial and temporal domain separately for imputation. In this paper, we propose Long-term Multidimensional Spatial-Temporal Graph Convolution Network (LMSTGCN), which can not only inductively estimate some missing information, but also achieve data augmentation of target locations. It contains a gated temporal capture module and a multidimensional graph convolution module. The multidimensional graph convolution module can simultaneously model spatial and extra-short term temporal information, and can achieve exponential growth in the range of receptive fields. Corresponding to this module, we designed a spatiotemporal adjacency matrix construction method, which can generate spatiotemporal adjacency matrices of corresponding time lengths as needed. The gated temporal capture module can deal with the short term dependencies in sequences. In experimental analysis, results demonstrate that the proposed model outperforms the state-of-the-art baselines on real-world data sets.

Abstract Predicting the bike demand can help rebalance the bikes and improve the service quality of a bike-sharing system. A lot of works focus on predicting the bike demand for all the stations, which is unnecessary as the travel cost of rebalance operations increases sharply as the number of stations increases. In this paper, we propose a framework for predicting the hourly bike demand based on the central stations we define. Firstly, we propose Two-Stage Station Clustering Algorithm to assign central stations and common stations into each cluster. Secondly, we propose a hierarchical prediction model to predict the hourly bike demand for every cluster and each central station progressively. Thirdly, we use a well-studied queuing model to determine the target initial inventory for each central station. The most innovative contribution of this paper is proposing the concept of central station, the use of a novel algorithm to cluster the central stations and present a hierarchical model, containing the Time and Weather Similarity Weighted K-Nearest Neighbor Algorithm and a linear model to predict the bike demand for central stations. The experimental results on the New York citi bike system demonstrate that our proposed method is more accurate than other methods in solving existing problems.

Abstract This paper addresses the anomaly detection problem in feature-evolving systems such as server machines, cyber security, financial markets and so forth where in every millisecond, $N$-dimensional feature-evolving heterogeneous time series are generated. However, due to stochasticity and uncertainty in evolving heterogeneous time series coupled with temporal dependencies, their anomaly detection are extremely challenging. Furthermore, it is practically impossible to train an anomaly detection model per single time series across millions of metrics, leave alone memory space required to maintain the model and evolving data points in memory for timely processing in feature-evolving data streams. Thus, this paper proposes $\underline{o}$ne sketch $\underline{f}$its all $\underline{a}$lgorithm (OFA), which is a real-time stochastic recurrent deep neural network anomaly detector built on assumption-free probabilistic conditional quantile regression with well-calibrated predictive uncertainty estimates. The proposed framework is capable of detecting anomalies robustly, accurately and efficiently in real time while handling randomness and variabilities in feature-evolving heterogeneous time series. Extensive experiments and rigorous evaluation on large-scale real-world data sets showcase that OFA outperforms other competitive state-of-the-art anomaly detector methods.

Multi-view data effectively model and characterize the underlying complex systems, and multi-view clustering is of great significance for revealing the mechanisms of systems, which groups objects into different clusters with high intra-cluster and low inter-cluster similarity for all views. Current algorithms are criticized for undesirable performance because they solely focus on either the shared features or correlation of objects, failing to address the heterogeneity and structural constraint of various views. To overcome these problems, a novelMulti-viewClustering withSelf-representation andStructuralConstraint (MCSSC) is proposed, which is a network-based method by fusing matrix factorization and low-rank representation of various views. Specifically, to remove heterogeneity of multi-view data, a network is constructed for each view, which casts the multi-view clustering into the multi-layer networks clustering problem. To extract the shared features of multiple views, MCSSC factorizes matrices associated with networks by projecting them into a common space and jointly learns an affinity graph for objects in multiple views with self-representation. To facilitate the clustering, the structural constraint is imposed on the affinity graph, where the clusters are identified. Extensive experiments demonstrate that MCSSC significantly outperforms the state-of-the-art in terms of accuracy, implying that the superiority of the proposed method.

With the increase in popularity of graph structured data arising in different areas such as Web, social network, communication network, knowledge graph, etc., there is a growing need for partitioning and repartitioning large graph data in a distributed system. However, the existing graph repartitioning methods are known for poor efficiency in the distributed environment and most of them lack a balance mechanism between edge cut and load balance. In this article, we introduce a new two-phase method to improve the result of distributed graph repartitioning. We first design a local method to identify all the potential candidate vertices that could improve the graph repartitioning result in load balance and edge cut at once in each partition locally. After that, we propose to migrate the selected vertices among the given initial partitions to improve the result of graph repartitioning. During this procedure, we propose to adopt a synchronous vertex migration method to balance both the edge cuts and load balance problems. Extensive experimental results demonstrate that the proposed method is more efficient than the existing methods in several aspects such as communication cost, running time, edge cut, and load balance. We also run SSSP and PageRank applications based on the graph repartitioning result on Giraph to indicate the efficiency of the proposed method.

Graph partitioning is a mandatory step in distributed graph computing systems. Some existing systems use edge partitioning methods to partition static graphs. However, the structure of the real-world graphs changes dynamically, which leads to unnecessary vertex replicas and load imbalance, reducing the performance of graph computation. In this article, we focus on improving the lower partitioning quality caused by the dynamics of the graph structure. We propose an edge repartitioning algorithm via structure-aware group migration (SAGM-ER). We define a special structure edge group (EG) consisting of multiple edges, which can reduce vertex replicas by migrating to other partitions. In repartitioning, we search for EGs in parallel by a method based on a structure-aware priority and then migrate EGs to reduce vertex replicas. Compared to the state of the art, SAGM-ER can reduce more vertex replicas. We implement SAGM-ER on Powergraph, which reduces the redundant replicas by 63.33%, thus reducing executing time and communication costs in graph computation by 33.72% and 37.51%, respectively.

Dynamic pricing plays an important role in solving the problems such as traffic load reduction, congestion control, and revenue improvement. Efficient dynamic pricing strategies can increase capacity utilization, total revenue of service providers, and the satisfaction of both passengers and drivers. Many proposed dynamic pricing technologies focus on short-term optimization and face poor scalability in modeling long-term goals for the limitations of solution optimality and prohibitive computation. In this article, a deep reinforcement learning framework is proposed to tackle the dynamic pricing problem for ride-hailing platforms. A soft actor-critic (SAC) algorithm is adopted in the reinforcement learning framework. First, the dynamic pricing problem is translated into a Markov Decision Process (MDP) and is set up in continuous action spaces, which is no need for the discretization of action space. Then, a new reward function is obtained by the order response rate and the KL-divergence between supply distribution and demand distribution. Experiments and case studies demonstrate that the proposed method outperforms the baselines in terms of order response rate and total revenue.

Traffic flow prediction is the upstream problem of path planning, intelligent transportation system, and other tasks. Many studies have been carried out on the traffic flow prediction of the spatio-temporal network, but the effects of spatio-temporal flexibility (historical data of the same type of time intervals in the same location will change flexibly) and spatio-temporal correlation (different road conditions have different effects at different times) have not been considered at the same time. We propose the Deep Spatio-temporal Adaptive 3D Convolution Neural Network (ST-A3DNet), which is a new scheme to solve both spatio-temporal correlation and flexibility, and consider spatio-temporal complexity (complex external factors, such as weather and holidays). Different from other traffic forecasting models, ST-A3DNet captures the spatio-temporal relationship at the same time through the Adaptive 3D convolution module, assigns different weights flexibly according to the influence of historical data, and obtains the impact of external factors on the flow through the ex-mask module. Considering the holidays and weather conditions, we train our model for experiments in Xi’an and Chengdu. We evaluate the ST-A3DNet and the results show that we have better results than the other 11 baselines.

Traffic spatial-temporal prediction is of great significance to traffic management and urban construction. In this paper, we propose a multi-task graph Synchronous neural network (MTSGNN) to synchronously predict the spatial-temporal data at the regions and transitions between regions. The method of constructing "multitask graph representation" is proposed to retain the information of regions and transitions that existing works can not reflect. Then our model synchronously captures multiple types of dynamic spatial correlations, models dynamic temporal dependencies and re-weights different time steps to solve the problem of long-term time modeling. In three real data sets, we verify the validity of the proposed model.

Detectors with high coverage have direct and far-reaching benefits for road users in route planning and avoiding traffic congestion, but utilizing these data presents unique challenges including: the dynamic temporal correlation, and the dynamic spatial correlation caused by changes in road conditions. Although the existing work considers the significance of modeling with spatial-temporal correlation, what it has learned is still a static road network structure, which cannot reflect the dynamic changes of roads, and eventually loses much valuable potential information. To address these challenges, we propose DetectorNet enhanced by Transformer. Differs from previous studies, our model contains a Multi-view Temporal Attention module and a Dynamic Attention module, which focus on the long-distance and short-distance temporal correlation, and dynamic spatial correlation by dynamically updating the learned knowledge respectively, so as to make accurate prediction. In addition, the experimental results on two public datasets and the comparison results of four ablation experiments proves that the performance of DetectorNet is better than the eleven advanced baselines.

Graph partitioning is a mandatory step in large-scale distributed graph processing. When partitioning real-world power-law graphs, the edge partitioning algorithm performs better than the traditional vertex partitioning algorithm, because it can cut a single vertex into multiple replicas to apportion the computation. Many advanced edge partitioning methods are designed for partitioning a static graph from scratch. However, the real-world graph structure changes continuously, which leads to a decrease in partition quality and affects the performance of the graph applications. Some studies are devoted to offline repartitioning or batch incremental partitioning, but how to deal with dynamics in real-time is still worthy of in-depth study. In this article, we discuss the impact of dynamic change on partition and discover that both insertion and deletion will lead to local suboptimal partitioning, which is the reason for the degradation of partition quality. As a solution, a dynamic edge partitioning algorithm is proposed to partition dynamics in real-time. Specifically, we deal with dynamics by a distributed stream and improve partition quality by reassigning some closely connected edges. Experiments show that it is robust to initial partition quality, dynamic scale and type, and distributed scale. Compared with the state-of-the-art dynamic partitioner, it can reduce vertex-cuts by 29.5 percent. Compared with the repartitioning algorithms, it can save the partitioning time by 91.0 percent. Applied on the graph task, it can reduce the increase of communication cost and the increase of the total time of task by 41.5 and 71.4 percent.

Traffic prediction has become increasingly hot in real-world applications. However, even though massive previous works have been conducted, traffic prediction based on the sensor is still confronted with unique challenges. In a nutshell, it is difficult for us to model both spatial dependency and temporal dependency. In this paper, we propose a novel model called GraphSANet which ensures both spatial and temporal dependencies are considered. With the usage of Temporal Self Attention, the temporal dependency could be captured perfectly and effectively, even if the problem caused by long-distance dependency could be alleviated. In the end, we conducted extensive experiments on two datasets, and vastly better prediction results prove the effectiveness of our model.

To improve the performance of large graph computing, graph partitioning has become a mandatory step in distributed graph computing frameworks. Some existing frameworks partition edges of an input graph in a streaming way. As the scale of real-world graphs grows dynamically, they need to limit the increasing communication cost and time cost in graph computing by reducing vertex replicas(each vertex can be replicated to multiple partitions). In this paper, we propose a real-time edge repartitioning algorithm for dynamic graph, which reduces the vertex replicas by reassigning edges near the new edge. We find that some edges are migrated just after being assigned, which leads to unnecessary migrations. To reduce migration cost, according to the replicas distribution of neighbors of two vertices connected by the new edge, we assign the new edge to the partition where it is most likely to be located after repartitioning. Our evaluation shows that it improves the performance of graph computing by only a small amount of migration.

Not only the expertise of people but also the collaboration among people are of great importance for a team. Given a set of experts with different skills, a social network that reflects the collaboration among people and a task, the team formation problem in social networks aims at forming a team to complete the task. The team is required to satisfy the skill requirements of the task and collaborates efficiently. Different communication cost functions have been proposed to have a good measure on the collaboration strength of a team in the existing work. However, the grouped organization structure inside team is never considered, which is very common in real life scenarios. In a grouped team, we are more concerned with the collaboration among people in same group and among leaders. In this paper, a novel communication cost function for a grouped team is proposed, and we define the Grouped Team Formation problem. To solve the problem, an exact algorithm is proposed. We further modify the exact algorithm to propose two heuristic algorithms with higher efficiency. Extensive experiments evaluate the effectiveness and efficiency of the proposed methods, and validate the reasonability of our problem definition in practical settings.

The increasing popularity of social networks improves information sharing among different users. Most existing online social networks involve the client/server architecture where each user needs to access to a server for contents sharing with other users. In this paper, we focus on constructing a mobile peer-to-peer based social network. We propose an efficient mobile social network to facilitate contents sharing over mobile ad hoc networks, in which social communities are built based on the interesting keywords, location histories and the current locations of different users. The users with common interest keywords, similar location histories and nearby current location are recommended as friends and connect directly in the mobile social network. The performance results show that the proposed method outperforms the existing methods in terms of the network management cost and contents search.

With the rapid development of wireless communication technologies and mobile devices, the mobile peer to peer (MP2P) network has been emerged. Since the existing MP2P architectures have high management cost, in this paper, we propose a hierarchical MP2P architecture using clustering mobile peers. The proposed method clusters the mobile peers by considering three aspects like the maximum connection time, the minimum hop count and the number of the connected peers. The connection times between the connected peers can be determined by the location, velocity vector and communication range of the mobile peers. Since the maximum connection time of the connected peers are considered, the network topology is relatively stable. Therefore, the management cost of the network is decreased and the success rate of contents search is increased. Experiments have shown that our proposed method outperforms the existing schemes.