Graph-based threat detection methods model Indicators of Compromise (IoC) using heterogeneous graphs and train node classifiers to identify malicious domains. Despite their promising performance, these approaches still face two major challenges. Firstly, the high cost of node annotation leads to a lack of evaluation on extensive gray data (unlabeled data). Secondly, the previous observations reveal a significant distribution shift in the Domain Maliciousness Graph (DMG), where structural differences between labeled and unlabeled domains hinder model performance. Existing graph learning methods have not yet considered both of these challenges simultaneously. To fill the gap, we frame the problem as semi-supervised graph node classification under out-of-distribution (OOD) constraints. We introduce graph aggregative contrastive learning (GRAVEL), which leverages the inherent structure of DMG to enhance detection performance on OOD unlabeled domains. GRAVEL is pre-trained end-to-end on abundant in-distribution malicious and benign samples, then fine-tuned with scarce OOD malicious data via mixup. During pre-training, label propagation seeds pseudo-labels, and a label-guided aggregation classifier is used to warm up the model, after which multi-view contrastive learning sharpens features for unlabeled domains. Extensive industrial evaluations demonstrate that GRAVEL improves F1 by 5–20% across diverse benchmarks for OOD malicious domain detection, consistently outperforming state-of-the-art baselines.

Cohesive subgraph mining has been extensively studied and finds numerous graph mining applications such as link farm identification, community detection, and product recommendation. Among various cohesive subgraph structures, the$k$-truss is particularly notable for its strong structural cohesiveness based on triangles. However, the classical$k$-truss problem aims to find the$k$-truss with the maximum number of vertices, which is often extremely large and complex in practice. To fully leverage the benefits of the$k$-truss, we consider a novel problem called theminimum$k$-truss problem, which seeks to identify a$k$-truss with the minimum number of vertices, where$k\geq 2$is a positive integer. We first formally prove the NP-hardness of the problem. We then design a baseline algorithmMTEnumthat is based on the vertex enumeration and a heuristic method for computing an upper bound. Despite these efforts,MTEnumstill faces practical efficiency issues which may be due to the fact that the$k$-truss lacks the hereditary property. To address this issue, we develop a novel decomposition-based frameworkDSA, which elegantly transforms the problem into a sequence of problems that are based on a new cohesive subgraph model callededge-based$s$-plex ($s$-eplex). With the hereditary property of$s$-eplex, we design a branch-and-bound algorithm with several customized techniques for the newly formulated problem. Extensive experiments demonstrate the effectiveness of our studied problem and the efficiency of our proposed algorithmDSA. In particular,DSAruns up to five orders of magnitude faster than the baselineMTEnum.

The problem of human spatiotemporal (ST) decision understanding, which consists of extracting faithful and interpretable decision strategies from human agents' behavioral records in space and time, is important for many applications, such as improving taxi drivers' route planning and efficiency. It is challenging because ST data are not as readily interpretable as images or text data, which leads to difficulties in constructing data-driven explanations. Existing research on this topic defines the problem as a Markov Decision Process (MDP) and uses imitation learning to extract a policy approximating the underlying human policy for post-hoc interpretation. However, such methods cannot provide direct interpretation through model training and may result in incomprehensible interpretations when using ST data. We address these limitations by designing ConPro-GAIL, a prototype-based interpretable GAIL model for intrinsically interpretable ST policy extraction. ConPro-GAIL learns and represents the optimal policy in terms of prototypical sets of concepts that correspond to general scenarios in the MDP. It explains a decision associated with an input state via inductive generalization from what occurred in the state's most similar prototypes to the input state itself. Experiments and case studies on two taxi trajectory datasets show that ConPro-GAIL achieves better policy faithfulness than its black-box competitors and better interpretability than post-hoc explainers.

Cohesive subgraph mining is a fundamental problem in graph theory with numerous real-world applications, such as social network analysis and protein-protein interaction modeling. Among various cohesive subgraphs, the γ-quasi-clique is widely studied for its flexibility in requiring each vertex to connect to at least a γ proportion of other vertices in the subgraph. However, solving the maximum γ-quasi-clique problem is NP-hard and further complicated by the lack of the hereditary property, which makes designing efficient pruning strategies challenging. Existing algorithms, such as DDA and FastQC, either struggle with scalability or exhibit significant performance declines for small values of γ. In this paper, we propose a novel algorithm, IterQC, which reformulates the maximum γ-quasi-clique problem as a series of k-plex problems that possess the hereditary property. IterQC introduces a non-trivial iterative framework and incorporates two key optimization techniques: (1) the pseudo lower bound (pseudo LB) technique, which leverages information across iterations to improve the efficiency of branch-and-bound searches, and (2) the preprocessing technique that reduces problem size and unnecessary iterations. Extensive experiments demonstrate that IterQC achieves up to four orders of magnitude speedup and solves significantly more graph instances compared to state-of-the-art algorithms DDA and FastQC.

Given historical traffic distributions and associated urban conditions observed in a city, the conditional urban traffic estimation problem aims at estimating realistic future projections of the traffic under a set of new urban conditions, e.g., new bus routes, rainfall intensity, and travel demands. The problem is important in reducing traffic congestion, improving public transportation efficiency, and facilitating urban planning. However, solving this problem is challenging due to the strong spatial dependencies of traffic patterns and the complex relations between the traffic and urban conditions. Recently, we proposed a Complex-Condition-Controlled Generative Adversarial Network ( \(\boldsymbol{C^{3}}\) -GAN) , which tackles both of the challenges and solves the urban traffic estimation problem under various complex conditions by adding a fixed embedding network and an inference network on top of the standard conditional GAN model. The randomly chosen embedding network transforms the complex conditions to latent vectors, and the inference network enhances the connections between the embedded vectors and the traffic data. However, a randomly chosen embedding network cannot always successfully extract features of complex urban conditions, which indicates \(C^{3}\) -GAN is unable to uniquely map different urban conditions to proper latent distributions. Thus, \(C^{3}\) -GAN would fail in certain traffic estimation tasks. Besides, \(C^{3}\) -GAN is hard to train due to vanishing gradients and mode collapse problems. To address these issues, in this article, we extend our prior work by introducing a new deep generative model, namely, \(C^{3}\) -GAN \(+\) , which significantly improves the estimation performance and model stability. \(C^{3}\) -GAN \(+\) has new objective, architecture, and training algorithm. The new objective applies Wasserstein loss to the conditional generation case to encourage stable training. Shared convolutional layers between the discriminator and the inference network help to capture spatial dependencies of traffic more efficiently, part of the shared convolutional layers are used to update the embedding network periodically aiming to encourage good representation and avoid model divergence. Extensive experiments on real-world datasets demonstrate that our \(C^{3}\) -GAN \(+\) produces high-quality traffic estimations and outperforms state-of-the-art baseline methods.

Finding cohesive subgraphs from a directed graph is a fundamental approach to analyze directed graph data. We consider a new model called directed$(k,\ell )$-plex for a cohesive directed subgraph, which is generalized from the concept of$k$-plex that is only applicable to undirected graphs. Directed$(k,\ell )$-plex (or DPlex) has the connection requirements on both inbound and outbound directions of each vertex inside, i.e., each vertex disconnects at most$k$vertices and is meanwhile not pointed to by at most$\ell$vertices. In this paper, we study the maximum DPlex search problem which finds a DPlex with the most vertices. We formally prove the NP-hardness of the problem. We then design a heuristic algorithm calledDPHeuris, which finds a DPlex with the size close to the maximum one and runs practically fast in polynomial time. Furthermore, we propose a branch-and-bound algorithm calledDPBBto find the exact maximum DPlex and develop effective graph reduction strategies for boosting the empirical performance. We also consider the problem of querying personalized maximum DPlex, and design a new method calledDPBBQfor the problem. Finally, we conduct extensive experiments on real directed graphs. The experimental results show that (1) our heuristic method can quickly find a near-optimal solution and (2) our branch-and-bound method runs up to six orders of magnitude faster than other baselines.

Traffic accident forecasting is an important task for intelligent transportation management and emergency response systems. However, this problem is challenging due to the spatial heterogeneity of the environment. Existing data-driven methods mostly focus on studying homogeneous areas with limited size (e.g. a single urban area such as New York City) and fail to handle the heterogeneous accident patterns over space at different scales. Recent advances (e.g. spatial ensemble) utilize pre-defined space partitions and learn multiple models to improve prediction accuracy. However, external knowledge is required to define proper space partitions before training models and predefined partitions may not necessarily reduce the heterogeneity. To address this issue, we propose a novel Learning-Integrated Space Partition Framework (LISA) to simultaneously learn partitions while training models, where the partitioning process and learning process are integrated in a way that partitioning is guided explicitly by prediction accuracy rather than other factors. Experiments using real-world datasets, demonstrate that our work can capture underlying heterogeneous patterns in a self-guided way and substantially improve baseline networks by an average of 13.0%.

Over the last decades, a rapidly growing volume of spatiotemporal data has been collected from smartphones and GPS, terrestrial, seaborne, airborne, and spaceborne sensors, as well as computational simulations. Meanwhile, advances in deep learning technologies, especially the recent breakthroughs of generative AI and foundation models such as Large Language Models (LLMs) and Large Vision Models (LVMs), have achieved tremendous success in natural language processing and computer vision applications. There is growing anticipation of the same level of accomplishment of AI on spatiotemporal data in tackling grand societal challenges, such as national water resource management, monitoring coastal hazards, energy and food security, as well as mitigation and adaptation to climate change. When deep learning, especially emerging foundation models, intersects spatiotemporal data in scientific domains, it opens up new opportunities and challenges. The workshop aims to bring together academic researchers in both AI and scientific domains, government program managers, leaders from non-profit organizations, as well as industry executives to brainstorm and debate on the emerging opportunities and novel challenges of deep learning (foundation models) for spatiotemporal data inspired by real-world scientific applications.

Human-generated Spatial-Temporal Data (HSTD), represented as trajectory sequences, has undergone a data revolution, thanks to advances in mobile sensing, data mining, and AI. Previous studies have revealed the effectiveness of employing attention mechanisms to analyze massive HSTD. However, traditional attention models face challenges when managing lengthy and noisy trajectories as their computation comes with large memory overheads. Furthermore, attention scores within HSTD trajectories are sparse (i.e., most of the scores are zeros), and clustered with varying lengths (i.e., consecutive tokens clustered with similar scores). To address these challenges, we introduce an innovative strategy named Memory-efficient Trajectory Attention (MeTA). We leverage complicated spatial-temporal features (e.g., traffic speed, proximity to PoIs) and design an innovative feature-based trajectory partition technique to shrink trajectory length. Additionally, we present a learnable dynamic sorting mechanism, with which attention is only computed between sub-trajectories that have prominent correlations. Empirical validations using real-world HSTD demonstrate that our approach not only yields competitive results but also significantly lowers memory usage compared with state-of-the-art methods. Our approach presents innovative solutions for memory-efficient trajectory attention, offering valuable insights for handling HSTD efficiently.

Rapid advances in perception, planning, and decision-making areas for self-driving vehicles have led to great improvements in their function and capabilities and enabled several prototypes to be driving on the roads and streets, such as Waymo Driver, TuSimple, Nuro, etc. Among various applications of self-driving vehicles, a promising one is the ride service as it has the potential to improve service quality and productivity and to provide service to anyone at any time. Extensive studies have been conducted on self-driving planning and safety, but few works focus on self-driving ride service decision-making and routing. In this work, we take the lead to study self-driving ride service planning and decision-making problem leveraging human-generated spatial-temporal data, and propose the data-driven Conservative Actor-Critic approach – CAC – based on offline reinforcement learning. Our CAC is able to make conservative decisions in a complicated environment with multiple goal states, and avoid dangerous and overly optimistic behaviors by exploiting human decisions. Extensive experiments with real-world data demonstrate that our CAC-learned policies are able to improve taxi service operation efficiency and quality drastically in terms of shortening passenger waiting time and improving service revenue.

Advancements in mobile sensing, data mining, and artificial intelligence have revolutionized the collection and analysis of Human-generated Spatial-Temporal Data (HSTD), paving the way for diverse applications across multiple domains. However, previous works have primarily focused on designing task-specific models for different problems, which lack transferability and generalizability when confronted with diverse HSTD. Additionally, these models often require a large amount of labeled data for optimal performance. While pre-trained models in Natural Language Processing (NLP) and Computer Vision (CV) domains have showcased impressive transferability and generalizability, similar efforts in the spatial-temporal data domain have been limited. In this paper, we take the lead and introduce the Spatial-Temporal Pre-Training model, $i.e$., STPT, which is connected with a self-supervised learning task, to address these limitations. STPT enables the creation of robust and versatile representations of HSTD. We validate our framework using real-world data and demonstrate its efficacy through two downstream tasks, $i.e$., trajectory classification and driving activity identification $(e.g$., identifying seeking $vs$. serving behaviors in taxi trajectories). Our results achieve an accuracy of 83.125% (16.2% higher than the average baseline) for human mobility identification and an accuracy of 77.88% (13.0% higher than the average baseline) for the human activity identification task. These outcomes underscore the potential of our pre-trained model for diverse downstream applications within the spatial-temporal data domain.

The Human Mobility Signature Identification (HuMID) problem aims at determining whether the incoming trajectories were generated by a claimed agent from the historical movement trajectories of a set of individual human agents such as pedestrians and taxi drivers. The HuMID problem is significant, and its solutions have a wide range of real-world applications, such as criminal identification for police departments, risk assessment for auto insurance providers, driver verification in ride-sharing services, and so on. Though Deep neural networks (DNN) based HuMID models on spatial-temporal mobility fingerprint similarity demonstrate remarkable performance in effectively identifying human agents' mobility signatures, it is vulnerable to adversarial attacks as other DNN-based models. Therefore, in this paper, we propose a Spatial-Temporal iterative Fast Gradient Sign Method with L0 regularization - ST-iFGSM - to detect the vulnerability and enhance the robustness of HuMID models. Extensive experiments with real-world taxi trajectory data demonstrate the efficiency and effectiveness of our ST-iFGSM algorithm. We tested our method on both the ST-SiameseNet and an LSTM-based HuMID classification model. It shows that ST-iFGSM can generate successful attacks to fool the HuMID models with only a few steps of attack in a small portion of the trajectories. The generated attacks can be used as augmented data to update and improve the HuMID model accuracy significantly from 47.36% to 76.18% on testing samples after the attack(86.25% on the original testing samples).

With large amounts of human-generated spatial-temporal urban data (e.g., GPS trajectories of vehicles, passengers’ trip data on buses and trains, etc.), human urban strategy analysis has become an important problem in many urban scenarios. This problem is hard to solve due to two major challenges: (1) data scarcity (i.e., each human agent can only provide limited observations) and (2) data heterogeneity (i.e., having mixed observations from many different human agents). Most of the existing works on this problem usually require a large amount of historical observations aiming to correctly infer a human agent's urban strategy and thus fail to properly address both challenges at the same time. To solve the human urban strategy analysis problem in case of data scarcity and data heterogeneity, we design a novel learning paradigm — Spatial-Temporal Meta-GAIL (STM-GAIL), which can successfully learn diverse human urban strategies from heterogeneous human-generated spatial-temporal urban data. STM-GAIL models the human decision processes as variable length Markov decision processes (VLMDPs) and incorporates the surrounding spatial feature patterns (e.g., traffic volume patterns, etc.) into states to better capture the spatial-temporal dependencies of human decisions. Besides, STM-GAIL learns diverse human urban strategies from the meta-learning perspective, and can distinguish various human urban strategies by adding an inference network on top of the standard GAIL. STM- GAIL can be quickly adapted to a new human expert's urban strategy with a single trajectory. Extensive experiments on real-world human-generated spatial-temporal dataset are performed.

Traffic congestion on a road segment typically begins as a small-scale spatiotemporal event that can then propagate throughout a road network and produce large-scale disruptions to a transportation system. In current techniques for the analysis of network flow, data is often aggregated to relatively large (e.g. 5 min) discrete time steps that obscure the small-scale spatiotemporal interactions that drive larger-scale dynamics. We propose a new method that handles fine-grained data to better capture those dynamics. Propagation patterns of traffic congestion are represented as spatiotemporally connected events. Each event is captured as a time series at the temporal resolution of the available trajectory data and at the spatial resolution of the network edge. The spatiotemporal propagation patterns of traffic congestion are captured using Dynamic Time Warping and represented as a set of directed acyclic graphs of spatiotemporal events. Results from this method are compared to an existing method using fine-grained data derived from an agent-based model of traffic simulation. Our method outperforms the existing method. Our method also successfully detects congestion propagation patterns that were reported by media news using sparse real-world data derived from taxis.

Speed-control forecasting, a challenging problem in driver behavior analysis, aims to predict the future actions of a driver in controlling vehicle speed such as braking or acceleration. In this paper, we try to address this challenge solely using egocentric video data, in contrast to the majority of works in the literature using either third-person view data or extra vehicle sensor data such as GPS, or both.To this end, we propose a novel graph convolutional network (GCN) based network, namely, EgoSpeed-Net. We are motivated by the fact that the position changes of objects over time can provide us very useful clues for forecasting the speed change in future. We first model the spatial relations among the objects from each class, frame by frame, using fully-connected graphs, on top of which GCNs are applied for feature extraction. Then we utilize a long short-term memory network to fuse such features per class over time into a vector, concatenate such vectors and forecast a speed-control action using a multilayer perceptron classifier. We conduct extensive experiments on the Honda Research Institute Driving Dataset, and demonstrate superior performance of EgoSpeed-Net.

As the adoption of machine learning continues to thrive, fairness of the algorithms has become a key factor determining their long-term success and sustainability. Among them, location-based fairness - or spatial fairness - is critical for a variety of essential societal applications that commonly rely on spatial data, including agriculture, disaster response, urban planning, etc. Spatial biases incurred by learning, if left unattended, may cause or exacerbate unfair distribution of resources, spatial disparity, social division, etc. However, very limited understanding has been developed on location-based fairness and bias in machine learning. Compared to traditional fairness-preserving techniques, the spatial consideration introduces two major layers of complication: (1) Space is continuous with no well-defined categories (e.g., categories by race or gender); and (2) Categorizations given by space-partitionings are known to be subject to high statistical sensitivity (e.g., gerrymandering). Under these challenges, we formally explore and demonstrate the fragility of learning methods in the spatial fairness-bias sphere. Specifically, we present a set of techniques that can maneuver the training process towards various targeted fairness-bias outcomes, while maintaining the same level of overall prediction performance (i.e., for "free"). Extensive experiments are carried out on two real-world problems: crop monitoring in the US and palm oil plantation mapping in Indonesia. The results demonstrate the effectiveness of the manipulation algorithms and the importance of explicitly regulating location-based fairness using a diverse set of criteria.

The conditional urban traffic estimation problem aims to accurately estimate the future traffic status based on the changing local travel demands, which has long been an important issue in urban planning. However, most existing methods require the target city to provide a large amount of traffic data. Once traffic estimation is performed in a “new” city where many urban services and transportation infrastructures are not built and thus no prior data is available, those works would fail due to the lack of data. In this paper, we aim to solve the conditional urban traffic estimation problem in case of data scarcity (i.e., the target city cannot provide any prior data) and tackle the main challenges including (1) knowledge learning from the source and (2) knowledge adaptation without prior traffic data. We propose a novel generative adversarial network — Meta Spatial-Temporal Generative Adversarial Network (Mest-GAN), which can successfully estimate traffic in the target city based on local travel demands without the access to any prior traffic data. To address the first challenge, we learn the latent distribution of travel demands with the inference network, the latent distribution also indicates the diverse spatial-temporal traffic patterns. To solve the second challenge, we use the travel demand data in the target city for adaptation, where the inference network infers a latent code guiding the generator to produce accurate traffic estimations. Extensive experiments on real-world multiple-city datasets demonstrate that our Mest-GAN produces high-quality traffic estimations and outperforms state-of-the-art baseline methods.

Conditional traffic estimation is a vital problem in urban plan deployment, which can help evaluate urban construction plans and improve transportation efficiency. Conventional methods for conditional traffic estimation usually focus on supervised settings, which require a large amount of labeled training data. However, in many urban planning applications, the large amount of traffic data in a new city can be hard or impossible to acquire. To tackle the conditional traffic estimation problem in data scarcity situations, we formulate the problem as a spatial transfer generative learning problem. Compared to prior spatial transfer learning frameworks with only single source city, we propose to extracts knowledge from multiple source cities to improve the estimation accuracy and transfer stability, which is a technically more challenging task. As a solution, we propose a new cross-city conditional traffic estimation method — Spatially-Transferable Generative Adversarial Networks (STrans-GAN) with novel pre-training and fine-tuning algorithms. STransGAN preserves diverse traffic patterns from multiple source cities through traffic clustering, and incorporates meta-learning idea into the pre-training process to learn a well-generalized model. During fine-tuning, we propose to add a cluster matching regularizer to realize the flexible adaptation in different scenarios. Through extensive experiments on multiple-city datasets, the effectiveness of STrans-GAN is proved.

Human mobility estimation is crucial during the COVID-19 pandemic due to its significant guidance for policymakers to make non-pharmaceutical interventions. While deep learning approaches outperform conventional estimation techniques on tasks with abundant training data, the continuously evolving pandemic poses a significant challenge to solving this problem due to data non-stationarity, limited observations, and complex social contexts. Prior works on mobility estimation either focus on a single city or lack the ability to model the spatio-temporal dependencies across cities and time periods. To address these issues, we make the first attempt to tackle the cross-city human mobility estimation problem through a deep meta-generative framework. We propose a Spatio-Temporal Meta-Generative Adversarial Network (STORM-GAN) model that estimates dynamic human mobility responses under a set of social and policy conditions related to COVID-19. Facilitated by a novel spatio-temporal task-based graph (STTG) embedding, STORM-GAN is capable of learning shared knowledge from a spatio-temporal distribution of estimation tasks and quickly adapting to new cities and time periods with limited training samples. The STTG embedding component is designed to capture the similarities among cities to mitigate cross-task heterogeneity. Experimental results on real-world data show that the proposed approach can greatly improve estimation performance and outperform baselines.

With the advancement of GPS and remote sensing technologies and the pervasiveness of smartphones and IoT devices, an enormous amount of spatiotemporal data are being collected from various domains. Knowledge discovery from spatiotemporal data is crucial in addressing many grand societal challenges, ranging from flood disaster management to monitoring coastal hazards, and from autonomous driving to disease forecasting. The recent success in deep learning technologies in computer vision and natural language processing provides new opportunities for spatiotemporal data mining, but existing deep learning techniques also face unique spatiotemporal challenges (e.g., autocorrelation, non-stationarity, physics awareness). This workshop provides a premium platform for researchers from both academia and industry to exchange ideas on the opportunities, challenges, and cutting-edge techniques related to deep learning for spatiotemporal data.

Traffic accident forecasting is a significant problem for transportation management and public safety. However, this problem is challenging due to the spatial heterogeneity of the environment and the sparsity of accidents in space and time. The occurrence of traffic accidents is affected by complex dependencies among spatial and temporal features. Recent traffic accident prediction methods have attempted to use deep learning models to improve accuracy. However, most of these methods either focus on small-scale and homogeneous areas such as populous cities or simply use sliding-window-based ensemble methods, which are inadequate to handle heterogeneity in large regions. To address these limitations, this paper proposes a novel Hierarchical Knowledge Transfer Network (HintNet) model to better capture irregular heterogeneity patterns. HintNet performs a multi-level spatial partitioning to separate sub-regions with different risks and learns a deep network model for each level using spatio-temporal and graph convolutions. Through knowledge transfer across levels, HintNet archives both higher accuracy and higher training efficiency. Extensive experiments on a real-world accident dataset from the state of Iowa demonstrate that HintNet outperforms the state-of-the-art methods on spatially heterogeneous and large-scale areas.

Estimating human mobility responses to the large-scale spreading of the COVID-19 pandemic is crucial, since its significance guides policymakers to give Non-pharmaceutical Interventions, such as closure or reopening of businesses. It is challenging to model due to complex social contexts and limited training data. Recently, we proposed a conditional generative adversarial network (COVID-GAN) to estimate human mobility response under a set of social and policy conditions integrated from multiple data sources. Although COVID-GAN achieves a good average estimation accuracy under real-world conditions, it produces higher errors in certain regions due to the presence of spatial heterogeneity and outliers. To address these issues, in this article, we extend our prior work by introducing a new spatio-temporal deep generative model, namely, COVID-GAN+. COVID-GAN+ deals with the spatial heterogeneity issue by introducing a new spatial feature layer that utilizes the local Moran statistic to model the spatial heterogeneity strength in the data. In addition, we redesign the training objective to learn the estimated mobility changes from historical average levels to mitigate the effects of spatial outliers. We perform comprehensive evaluations using urban mobility data derived from cell phone records and census data. Results show that COVID-GAN+ can better approximate real-world human mobility responses than prior methods, including COVID-GAN.

Urban traffic status (e.g., traffic speed and volume) is highly dynamic in nature, namely, varying across space and evolving over time. Thus, predicting such traffic dynamics is of great importance to urban development and transportation management. However, it is very challenging to solve this problem due to spatial-temporal dependencies and traffic uncertainties. In this article, we solve the traffic dynamics prediction problem from Bayesian meta-learning perspective and propose a novel continuous spatial-temporal meta-learner (cST-ML), which is trained on a distribution of traffic prediction tasks segmented by historical traffic data with the goal of learning a strategy that can be quickly adapted to related but unseen traffic prediction tasks. cST-ML tackles the traffic dynamics prediction challenges by advancing the Bayesian black-box meta-learning framework through the following new points: (1) cST-ML captures the dynamics of traffic prediction tasks using variational inference, and to better capture the temporal uncertainties within tasks, cST-ML performs as a rolling window within each task; (2) cST-ML has novel designs in architecture, where CNN and LSTM are embedded to capture the spatial-temporal dependencies between traffic status and traffic-related features; (3) novel training and testing algorithms for cST-ML are designed. We also conduct experiments on two real-world traffic datasets (taxi inflow and traffic speed) to evaluate our proposed cST-ML. The experimental results verify that cST-ML can significantly improve the urban traffic prediction performance and outperform all baseline models especially when obvious traffic dynamics and temporal uncertainties are presented.

Thanks to the rapid development of mobile sensing techniques, massive human-generated spatial-temporal data (HSTD) are generated from the urban areas, e.g., passenger-seeking trajectories from taxi drivers, and public transit trips from urban dwellers. These HSTD record sequential decisions made by human agents. Studying human behavior from HSTD provides benefits to many aspects, for example, studying passenger-seeking strategies from experienced taxi drivers can help improve the operation efficiencies of those new drivers. One common method to analyze human behavior from HSTD is Imitation Learning (IL). Existing IL approaches rely on data collected from experts. However, human agents who generate HSTD may have diverse expertise levels across geographical regions, i.e., with good policies in some regions and poor policies in less experienced regions. The problem of how to infer the optimal policy for agents in their unfamiliar or less-experienced regions remains open. In this paper, we propose the novel Generative Adversarial Imitation Learning for Non-experts (NEXT-GAIL) framework to first disentangle expert knowledge, which is irrelevant to spatial-temporal regions, from the demonstration data. Then, such knowledge can be transferred to regions, where the agent does not possess an expert policy. We take the real-world taxi trajectory data as an example to evaluate the performance of our proposed framework. The comparison results illustrate that our proposed NEXT-GAIL outperforms existing state-of-the-art approaches regarding the accuracy of the inferred optimal policy for non-experts.

Knowledge discovery from spatial data is essential for many important societal applications including crop monitoring, solar energy estimation, traffic prediction and public health. This paper aims to tackle a key challenge posed by spatial data - the intrinsic spatial heterogeneity commonly embedded in their generation processes - in the context of deep learning. In related work, the early rise of convolutional neural networks showed the promising value of explicit spatial-awareness in deep architectures (i.e., preservation of spatial structure among input cells and the use of local connection). However, the issue of spatial heterogeneity has not been sufficiently explored. While recent developments have tried to incorporate awareness of spatial variability (e.g., SVANN), these methods either rely on manually-defined space partitioning or only support very limited partitions (e.g., two) due to reduction of training data. To address these limitations, we propose a Spatial-Net to simultaneously learn a space-partitioning scheme and a deep network architecture with a Significance-based Grow-and-Collapse (SIG-GAC) framework. SIG-GAC allows collaborative training between partitions and uses an exponential reduction tree to control the network size. Experiments using real-world datasets show that Spatial-Net can automatically learn the pattern underlying heterogeneous spatial process and greatly improve model performance.

The Bayes Classifier is shown to have the minimal classification error, in addition to interpretable predictions. However, it requires the knowledge of underlying distributions of the predictors to be usable. This requirement is almost never satisfied. Naive Bayes classifiers and variants estimate this classifier by assuming the independence among predictors. This restrictive assumption hinders both the accuracy of these classifiers and their interpretability, as the calculated probabilities become less reliable. Moreover, it is argued in the literature that interpretability comes at the expense of accuracy and vice versa. In this paper, we are motivated by the accurate and interpretable nature of the Bayes Classifier. We propose Precise Bayes, which is a computationally efficient estimation of the Bayes Classifier based on a new formulation. Our method makes no assumptions, neither on independence nor on underlying distributions. We devise a new theoretical minimal error rate for our formulation and show that the error rate of Precise Bayes approaches this limit with increasing number of samples learned. Moreover, the calculated posterior probabilities, are actual empirical probabilities calculated by counting the observations and outcomes. This makes the predictions made by Precise Bayes fully explainable. Our evaluations on generated datasets and real datasets validate our theoretical claims on prediction error rate and computational efficiency.

Spatial data are ubiquitous, massively collected, and widely used to support critical decision-making in many societal domains, including public health (e.g., COVID-19 pandemic control), agricultural crop monitoring, transportation, etc. While recent advances in machine learning and deep learning offer new promising ways to mine such rich datasets (e.g., satellite imagery, COVID statistics), spatial heterogeneity – an intrinsic characteristic embedded in spatial data - poses a major challenge as data distributions or generative processes often vary across space at different scales, with their spatial extents unknown. Recent studies (e.g., SVANN, spatial ensemble) targeting this difficult problem either require a known space-partitioning as the input, or can only support very limited number of partitions or classes (e.g., two) due to the decrease in training data size and the complexity of analysis. To address these limitations, we propose a model-agnostic framework to automatically transform a deep learning model into a spatial-heterogeneity-aware architecture, where the learning of arbitrary space partitionings is guided by a learning-engaged generalization of multivariate scan statistic and parameters are shared based on spatial relationships. We also propose a spatial moderator to generalize learned space partitionings to new test regions. Experiment results on real-world datasets show that the spatial transformation and moderation framework can effectively capture flexibly-shaped heterogeneous footprints and substantially improve prediction performances.

Given historical traffic distributions and associated urban conditions observed in a city, the conditional urban traffic estimation problem aims at estimating realistic future projections of the traffic under a set of new urban conditions, e.g., new bus routes, rainfall intensity and travel demands. The problem is important in reducing traffic congestion, improving public transportation efficiency, and facilitating urban planning. However, solving this problem is challenging due to the strong spatial dependencies of traffic patterns and the complex relations between the traffic and urban conditions. In this paper, we tackle the challenges by proposing a novel Complex-Condition-Controlled Urban Traffic Estimation through Generative Adversarial Networks (C3-GAN) for urban traffic estimation of a region under various complex conditions. C3-GAN features the following three novel designs on top of standard cGAN model: (1) an embedding network mapping the complex conditions to a latent space to find representations of the urban conditions; (2) an inference network to enhance the relations between the embedded latent vectors and the traffic data. Extensive experiments on real-world datasets demonstrate that our C3-GAN produces high-quality traffic estimations and outperforms state-of-the-art baseline methods.

Given the underlying road network of an urban area, the problem of urban dynamics prediction aims to capture the patterns of urban dynamics and to forecast short-term urban traffic status continuously from the historical observations. This problem is of fundamental importance to urban traffic management, planning, and various business services. However, predicting urban dynamics is challenging due to the highly dynamic (i.e., varying across geographical locations and evolving over time) and uncertain (i.e., affected by unexpected factors) nature of urban traffic systems. Recent works adopt meta-learning approaches to capture irregular and rare patterns but make unrealistic assumptions such as single-domain uncertainties and explicit temporal task segmentation. In this paper, we solve the urban dynamics prediction problem from the Bayesian meta-learning perspective and propose a novel domain adaptable continuous meta-learning approach (DAC-ML) that does not require task segmentation. Trained on a sequence of spatial-temporal urban dynamics data, DAC-ML aims to detect and infer unobserved latent variations (from task and domain levels) and generalize well in a sequential prediction setting, where the underlying data generating process varies over time. Experimental results on three real-world datasets demonstrate that DAC-ML can outperform baselines in urban dynamics prediction, especially when obvious urban dynamics and temporal uncertainties are present.

With the recent advances in mobile sensing technologies, large amounts of sequential data are collected, such as vehicle GPS records, stock prices, sensor data from air quality detectors. Recurrent neural networks (RNNs) have been studied extensively to learn complex patterns for sequential data, with applicatons in natural language processing for sentence prediction/completion, human activity recognition for predicting or classifying human activities. However, there are many practical issues when training RNNs, e.g., vanishing and exploding gradients often occur due to the repeatability of network weights, etc. In this paper, we study the training stability in deep recurrent neural networks (RNNs), and propose a novel network, namely, deep incremental RNN (DIRNN). In contrast to the literature, we prove that DIRNN is essentially a Lyapunov stable dynamical system where there is no vanishing or exploding gradient in training. To demonstrate the applicability in practice, we also propose a novel implementation, namely TinyRNN, that sparsifies the transition matrices in DIRNN using weighted random permutations to reduce the model sizes. We evaluate our approach on seven benchmark datasets, and achieve state-of-the-art results. Demo code is provided in the supplementary file.

With the advancement of GPS and remote sensing technologies and the pervasiveness of smartphones and mobile devices, large amounts of spatiotemporal data are being collected from various domains. Knowledge discovery from spatiotemporal data is crucial in broad societal applications. Examples range from mapping flooded areas on satellite imagery for disaster response to monitoring crop health for food security, from estimating travel time between locations on Google Maps to forecasting hotspots of diseases like Covid-19 in public health. The recent success in deep learning technologies in computer vision and natural language processing provides unique opportunities for spatiotemporal data mining (e.g., automatically extracting spatial contextual features without manual feature engineering) but also faces unique challenges (e.g., spatial autocorrelation, heterogeneity, multiple scales, and resolutions, the existence of domain knowledge and constraints). This workshop provides a premium platform for researchers from both academia and industry to exchange ideas on opportunities, challenges, and cutting-edge techniques of deep learning for spatiotemporal data. We hope to inspire novel ideas and visions through the workshop and facilitate the development of this emerging research area.

Urban dispersal events occur when an unexpectedly large number of people leave an area in a relatively short period of time. It is beneficial for the city authorities, such as law enforcement and city management, to have an advance knowledge of such events, as it can help them mitigate the safety risks and handle important challenges such as managing traffic, and so forth. Predicting dispersal events is also beneficial to Taxi drivers and/or ride-sharing services, as it will help them respond to an unexpected demand and gain competitive advantage. Large urban datasets such as detailed trip records and point of interest ( POI ) data make such predictions achievable. The related literature mainly focused on taxi demand prediction. The pattern of the demand was assumed to be repetitive and proposed methods aimed at capturing those patterns. However, dispersal events are, by definition, violations of those patterns and are, understandably, missed by the methods in the literature. We proposed a different approach in our prior work [32]. We showed that dispersal events can be predicted by learning the complex patterns of arrival and other features that precede them in time. We proposed a survival analysis formulation of this problem and proposed a two-stage framework (DILSA), where a deep learning model predicted the survival function at each point in time in the future. We used that prediction to determine the time of the dispersal event in the future, or its non-occurrence. However, DILSA is subject to a few limitations. First, based on evidence from the data, mobility patterns can vary through time at a given location. DILSA does not distinguish between different mobility patterns through time. Second, mobility patterns are also different for different locations. DILSA does not have the capability to directly distinguish between different locations based on their mobility patterns. In this article, we address these limitations by proposing a method to capture the interaction between POIs and mobility patterns and we create vector representations of locations based on their mobility patterns. We call our new method DILSA+. We conduct extensive case studies and experiments on the NYC Yellow taxi dataset from 2014 to 2016. Results show that DILSA+ can predict events in the next 5 hours with an F1-score of 0.66. It is significantly better than DILSA and the state-of-the-art deep learning approaches for taxi demand prediction.

Cluster detection is important and widely used in a variety of applications, including public health, public safety, transportation, and so on. Given a collection of data points, we aim to detect density-connected spatial clusters with varying geometric shapes and densities, under the constraint that the clusters are statistically significant. The problem is challenging, because many societal applications and domain science studies have low tolerance for spurious results, and clusters may have arbitrary shapes and varying densities. As a classical topic in data mining and learning, a myriad of techniques have been developed to detect clusters with both varying shapes and densities (e.g., density-based, hierarchical, spectral, or deep clustering methods). However, the vast majority of these techniques do not consider statistical rigor and are susceptible to detecting spurious clusters formed as a result of natural randomness. On the other hand, scan statistic approaches explicitly control the rate of spurious results, but they typically assume a single “hotspot” of over-density and many rely on further assumptions such as a tessellated input space. To unite the strengths of both lines of work, we propose a statistically robust formulation of a multi-scale DBSCAN, namely Significant DBSCAN+, to identify significant clusters that are density connected. As we will show, incorporation of statistical rigor is a powerful mechanism that allows the new Significant DBSCAN+ to outperform state-of-the-art clustering techniques in various scenarios. We also propose computational enhancements to speed-up the proposed approach. Experiment results show that Significant DBSCAN+ can simultaneously improve the success rate of true cluster detection (e.g., 10–20% increases in absolute F1 scores) and substantially reduce the rate of spurious results (e.g., from thousands/hundreds of spurious detections to none or just a few across 100 datasets), and the acceleration methods can improve the efficiency for both clustered and non-clustered data.

Given a set of user-specified locations and a massive trajectory dataset, the task of mining spatio-temporal reachable regions aims at finding which road segments are reachable from these locations within a given temporal period based on the historical trajectories. Determining such spatio-temporal reachable regions with high accuracy is vital for many urban applications, such as location-based recommendations and advertising. Traditional approaches to answering such queries essentially perform a distance-based range query over the given road network, which does not consider dynamic travel time at different time of day. By contrast, we propose a data-driven approach to formulate the problem as mining actual reachable regions based on a real historical trajectory dataset. Efficient algorithms for the Single-location spatio-temporal reachability Query (S-Query) and the Union-of-multi-location spatio-temporal reachability Query (U-Query) were presented in our recent work. In this paper, we extend the previous ideas by introducing a new type of reachability query with multiple sources, namely, the Intersection-of-multi-location spatio-temporal reachability Query (I-Query). As we demonstrate, answering I-Queries efficiently is generally more computationally challenging than answering either S-Queries or U-Queries because I-Queries involve complicated intersect conditions. We propose two new algorithms called the Intersection-of-Multi-location Query Maximum Bounding region search (I-MQMB) algorithm and the I-Query Trace Back Search (I-TBS) algorithm to efficiently answer I-Queries, which utilize an indexing schema composed of a spatio-temporal index and a connection index. We evaluate our system extensively by using a large-scale real taxi trajectory dataset that records taxi rides in Shenzhen, China. Our results demonstrate that the proposed approach reduces the running time of I-Queries by 50 percent on average compared to the baseline method.

Identifying urban gathering events is an important problem due to challenges it brings to urban management. In our prior work, we proposed a hybrid model (H-VIGO-GIS) to predict future gathering events through trajectory destination prediction. Our approach consisted of two models: historical and recent and continuously predicted future gathering events. However, H-VIGO-GIS has limitations. (1) The recent model does not capture the newly-emerged abnormal patterns effectively, since it uses all recent trajectories, including normal ones. (2) The recent model is sparse due to limited number of trajectories it learns, i.e., it cannot produce predictions in many cases, forcing us to rely only on the historical model. (3) The accuracy of both recent and historical models varies by space and time. Therefore, combining them the same way at all times and places undermines the overall accuracy of the hybrid model. Addressing these issues, in this paper we propose a Dynamic Hybrid model called (DH-VIGO-TKDE) that addresses the above-mentioned issues. We perform comprehensive evaluations using two large real-world datasets and an event simulator. The experiments show the proposed model significantly improves the prediction accuracy and timeliness of forecasting gathering events, resulting in average precision of 0.91 and recall of 0.67 as opposed to 0.74 and 0.50 of H-VIGO-GIS.

The COVID-19 pandemic has posed grand challenges to policy makers, raising major social conflicts between public health and economic resilience. Policies such as closure or reopen of businesses are made based on scientific projections of infection risks obtained from infection dynamics models. While most parameters in infection dynamics models can be set using domain knowledge of COVID-19, a key parameter - human mobility - is often challenging to estimate due to complex social contexts and limited training data under escalating COVID-19 conditions. To address these challenges, we formulate the problem as a spatio-temporal data generation problem and propose COVID-GAN, a spatio-temporal Conditional Generative Adversarial Network, to estimate mobility (e.g., changes in POI visits) under various real-world conditions (e.g., COVID-19 severity, local policy interventions) integrated from multiple data sources. We also introduce a domain-constraint correction layer in the generator of COVID-GAN to reduce the difficulty of learning. Experiments using urban mobility data derived from cell phone records and census data show that COVID-GAN can well approximate real-world human mobility responses, and that the proposed domain-constraint based correction can greatly improve solution quality.

Cycling, as a green transportation mode, provides an environmentally friendly transportation choice for short-distance traveling. However, cyclists are also getting involved in fatal accidents more frequently in recent years. Thus, understanding and modeling their road behaviors is crucial in helping improving road safety laws and infrastructures. Traditionally, people understand road user behavior using either purely spatial trajectory data, or videos from fixed surveillance camera through tracking or predicting their paths. However, these data only cover limited areas and do not provide information from the cyclist's field of view. In this paper, we take advantage of geo-referenced egocentric video data collected from the handlebar cameras of cyclists to learn how to predict their behaviors. This approach is technically more challenging, because both the observer and objects in the scene might be moving, and there are strong temporal dependencies in both the behaviors of cyclists and the video scenes. We propose Cycling-Net, a novel deep learning model that tracks different types of objects in consecutive scenes and learns the relationship between the movement of these objects and the behavior of the cyclist. Experiment results on a naturalistic trip dataset show the Cycling-Net is effective in behavior prediction and outperforms a baseline model.

Learning to make optimal decisions is a common yet complicated task. While computer agents can learn to make decisions by running reinforcement learning (RL), it remains unclear how human beings learn. In this paper, we perform the first data-driven case study on taxi drivers to validate whether humans mimic RL to learn. We categorize drivers into three groups based on their performance trends and analyze the correlations between human drivers and agents trained using RL. We discover that drivers that become more efficient at earning over time exhibit similar learning patterns to those of agents, whereas drivers that become less efficient tend to do the opposite. Our study (1) provides evidence that some human drivers do adapt RL when learning, (2) enhances the deep understanding of taxi drivers' learning strategies, (3) offers a guideline for taxi drivers to improve their earnings, and (4) develops a generic analytical framework to study and validate human learning strategies.

Urban traffic status (e.g., traffic speed and volume) is highly dynamic in nature, namely, varying across space and evolving over time. Thus, predicting such traffic dynamics is of great importance to urban development and transportation management. However, it is very challenging to solve this problem due to spatial-temporal dependencies and traffic uncertainties. In this paper, we solve the traffic dynamics prediction problem from Bayesian meta-learning perspective and propose a novel continuous spatial-temporal meta-learner (cST-ML), which is trained on a distribution of traffic prediction tasks segmented by historical traffic data with the goal of learning a strategy that can be quickly adapted to related but unseen traffic prediction tasks. cST-ML tackles the traffic dynamics prediction challenges by advancing the Bayesian black-box meta-learning framework through the following new points: 1) cST-ML captures the dynamics of traffic prediction tasks using variational inference; 2) cST-ML has novel designs in architecture, where CNN and LSTM are embedded to capture the spatial-temporal dependencies between traffic status and traffic related features; 3) novel training and testing algorithms for cST-ML are designed. We also conduct experiments on two real-world traffic datasets (taxi inflow and traffic speed) to evaluate our proposed cST-ML. The experimental results verify that cST-ML can significantly improve the urban traffic prediction performance and outperform all baseline models.

Mobile sensing and information technology have enabled us to collect a large amount of mobility data from human decision-makers, for example, GPS trajectories from taxis, Uber cars, and passenger trip data of taking buses and trains. Understanding and learning human decision-making strategies from such data can potentially promote individual's well-being and improve the transportation service quality. Existing works on human strategy learning, such as inverse reinforcement learning, all model the decision-making process as a Markov decision process, thus assuming the Markov property. In this work, we show that such Markov property does not hold in real-world human decision-making processes. To tackle this challenge, we develop a Trajectory Generative Adversarial Imitation Learning (TrajGAIL) framework. It captures the long-term decision dependency by modeling the human decision processes as variable length Markov decision processes (VLMDPs), and designs a deep-neural-network-based framework to inversely learn the decision-making strategy from the human agent's historical dataset. We validate our framework using two real world human-generated spatial-temporal datasets including taxi driver passenger-seeking decision data and public transit trip data. Results demonstrate significant accuracy improvement in learning human decision-making strategies, when comparing to baselines with Markov property assumptions.

To make daily decisions, human agents devise their own "strategies" governing their mobility dynamics (e.g., taxi drivers have preferred working regions and times, and urban commuters have preferred routes and transit modes). Recent research such as generative adversarial imitation learning (GAIL) demonstrates successes in learning human decision-making strategies from their behavior data using deep neural networks (DNNs), which can accurately mimic how humans behave in various scenarios, e.g., playing video games, etc. However, such DNN-based models are "black box" models in nature, making it hard to explain what knowledge the models have learned from human, and how the models make such decisions, which was not addressed in the literature of imitation learning. This paper addresses this research gap by proposing xGAIL, the first explainable generative adversarial imitation learning framework. The proposed xGAIL framework consists of two novel components, including Spatial Activation Maximization (SpatialAM) and Spatial Randomized Input Sampling Explanation (SpatialRISE), to extract both global and local knowledge from a well-trained GAIL model that explains how a human agent makes decisions. Especially, we take taxi drivers' passenger-seeking strategy as an example to validate the effectiveness of the proposed xGAIL framework. Our analysis on a large-scale real-world taxi trajectory data shows promising results from two aspects: i) global explainable knowledge of what nearby traffic condition impels a taxi driver to choose a particular direction to find the next passenger, and ii) local explainable knowledge of what key (sometimes hidden) factors a taxi driver considers when making a particular decision.

Given the historical movement trajectories of a set of individual human agents (e.g., pedestrians, taxi drivers) and a set of new trajectories claimed to be generated by a specific agent, the Human Mobility Signature Identification (HuMID) problem aims at validating if the incoming trajectories were indeed generated by the claimed agent. This problem is important in many real-world applications such as driver verification in ride-sharing services, risk analysis for auto insurance companies, and criminal identification. Prior work on identifying human mobility behaviors requires additional data from other sources besides the trajectories, e.g., sensor readings in the vehicle for driving behavior identification. However, these data might not be universally available and is costly to obtain. To deal with this challenge, in this work, we make the first attempt to match identities of human agents only from the observed location trajectory data by proposing a novel and efficient framework named Spatio-temporal Siamese Networks (ST-SiameseNet). For each human agent, we extract a set of profile and online features from his/her trajectories. We train ST-SiameseNet to predict the mobility signature similarity between each pair of agents, where each agent is represented by his/her trajectories and the extracted features. Experimental results on a real-world taxi trajectory dataset show that our proposed ST-SiamesNet can achieve an $F_1$ score of $0.8508$, which significantly outperforms the state-of-the-art techniques.

Given an urban development plan and the historical traffic observations over the road network, the Conditional Urban Traffic Estimation problem aims to estimate the resulting traffic status prior to the deployment of the plan. This problem is of great importance to urban development and transportation management, yet is very challenging because the plan would change the local travel demands drastically and the new travel demand pattern might be unprecedented in the historical data. To tackle these challenges, we propose a novel Conditional Urban Traffic Generative Adversarial Network (Curb-GAN), which provides traffic estimations in consecutive time slots based on different (unprecedented) travel demands, thus enables urban planners to accurately evaluate urban plans before deploying them. The proposed Curb-GAN adopts and advances the conditional GAN structure through a few novel ideas: (1) dealing with various travel demands as the "conditions" and generating corresponding traffic estimations, (2) integrating dynamic convolutional layers to capture the local spatial auto-correlations along the underlying road networks, (3) employing self-attention mechanism to capture the temporal dependencies of the traffic across different time slots. Extensive experiments on two real-world spatio-temporal datasets demonstrate that our Curb-GAN outperforms major baseline methods in estimation accuracy under various conditions and can produce more meaningful estimations.

Public transports, such as subway lines and buses, offer affordable ride-sharing services and reduce the road network traffic. Extracting passengers’ preferences from their public transit choices is important to city planners but technically non-trivial. When traveling by taking public transits, passengers make sequences of transit choices, and their rewards are usually influenced by other passengers’ choices. This process can be modeled as a Markov Game (MG). In this paper, we make the first effort to model travelers’ preferences of making transit choices using MGs. Based on the discovery that passengers usually do not change their policies, we propose novel algorithms to extract reward functions from the observed deterministic equilibrium joint policy of all agents in a general-sum MG to infer travelers’ preferences. First, we assume we have the access to the entire joint policy. We characterize the set of all reward functions for which the given joint policy is a Nash equilibrium policy. In order to remove the degeneracy of the solution, we then attempt to pick reward functions so as to maximize the sum of the deviation between the the observed policy and the sub-optimal policy of each agent. This results in a skillfully solvable linear programming algorithm for the multi-agent inverse reinforcement learning (MA-IRL) problem. Then, we deal with the case where we have access to the equilibrium joint policy through a set of actual trajectories. We propose an iterative algorithm inspired by single-agent apprenticeship learning algorithms and the cyclic coordinate descent approach. We evaluate the proposed algorithms on both a simple Grid Game and a unique real-world dataset (from Shenzhen, China). Results show that when we have access to the full policy, our algorithm can efficiently recover most of the reward structure, especially the interaction of agents. In the case where we only have access to a set of sampled expert trajectories, our algorithm can provide an explanation of the expert trajectories. Measured with respect to the experts’ unknown reward function, the performance of the policy output by our algorithm is close to that of the expert policy.

Many real-world human behaviors can be modeled and characterized as sequential decision-making processes, such as a taxi driver’s choices of working regions and times. Each driver possesses unique preferences on the sequential choices over time and improves the driver’s working efficiency. Understanding the dynamics of such preferences helps accelerate the learning process of taxi drivers. Prior works on taxi operation management mostly focus on finding optimal driving strategies or routes, lacking in-depth analysis on what the drivers learned during the process and how they affect the performance of the driver. In this work, we make the first attempt to establish Dynamic Human Preference Analytics. We inversely learn the taxi drivers’ preferences from data and characterize the dynamics of such preferences over time. We extract two types of features (i.e., profile features and habit features) to model the decision space of drivers. Then through inverse reinforcement learning, we learn the preferences of drivers with respect to these features. The results illustrate that self-improving drivers tend to keep adjusting their preferences to habit features to increase their earning efficiency while keeping the preferences to profile features invariant. However, experienced drivers have stable preferences over time. The exploring drivers tend to randomly adjust the preferences over time.

Given a path in a spatial or temporal framework, we aim to find all contiguous subpaths that are both interesting (e.g., abrupt changes) and statistically significant (i.e., persistent trends rather than local fluctuations). Discovering interesting subpaths can provide meaningful information for a variety of domains including Earth science, environmental science, urban planning, and the like. Existing methods are limited to detecting individual points of interest along an input path but cannot find interesting subpaths. Our preliminary work provided a Subpath Enumeration and Pruning (SEP) algorithm to detect interesting subpaths of arbitrary length. However, SEP is not effective in avoiding detections that are random variations rather than meaningful trends, which hampers clear and proper interpretations of the results. In this article, we extend our previous work by proposing a significance testing framework to eliminate these random variations. To compute the statistical significance, we first show a baseline Monte-Carlo method based on our previous work and then propose a Dynamic Search-and-Prune (D-SAP) algorithm to improve its computational efficiency. Our experiments show that the significance testing can greatly suppress the noisy detections in the output and D-SAP can greatly reduce the execution time.

The rapid progress of urbanization has expedited the process of urban planning, e.g., new residential, commercial areas, which in turn boosts the local travel demand. We propose a novel "off-deployment traffic estimation problem", namely, to foresee the traffic condition changes of a region prior to the deployment of a construction plan. This problem is important to city planners to evaluate and develop urban deployment plans. However, this task is challenging. Traditional traffic estimation approaches lack the ability to solve this problem, since no data about the impact can be collected before the deployment and old data fails to capture the traffic pattern changes. In this paper, we define the off-deployment traffic estimation problem as a traffic generation problem, and develop a novel deep generative model TrafficGAN that captures the shared patterns across spatial regions of how traffic conditions evolve according to travel demand changes and underlying road network structures. In particular, TrafficGAN captures the road network structures through a dynamic filter in the dynamic convolutional layer. We evaluate our TrafficGAN using a large-scale traffic data collected from Shenzhen, China. Results show that TrafficGAN can more accurately estimate the traffic conditions compared with all baselines.

Smart passenger-seeking strategies employed by taxi drivers contribute not only to drivers' incomes, but also higher quality of service passengers received. Therefore, understanding taxi drivers' behaviors and learning the good passenger-seeking strategies are crucial to boost taxi drivers' well-being and public transportation quality of service. However, we observe that drivers' preferences of choosing which area to find the next passenger are diverse and dynamic across locations and drivers. It is hard to learn the location-dependent preferences given the partial data (i.e., an individual driver's trajectory may not cover all locations). In this paper, we make the first attempt to develop conditional generative adversarial imitation learning (cGAIL) model, as a unifying collective inverse reinforcement learning framework that learns the driver's decision-making preferences and policies by transferring knowledge across taxi driver agents and across locations. Our evaluation results on three months of taxi GPS trajectory data in Shenzhen, China, demonstrate that the driver's preferences and policies learned from cGAIL are on average 34.7% more accurate than those learned from other state-of-the-art baseline approaches.

Many real world human behaviors can be modeled and characterized as sequential decision making processes, such as taxi driver's choices of working regions and times. Each driver possesses unique preferences on the sequential choices over time and improves their working efficiency. Understanding the dynamics of such preferences helps accelerate the learning process of taxi drivers. Prior works on taxi operation management mostly focus on finding optimal driving strategies or routes, lacking in-depth analysis on what the drivers learned during the process and how they affect the performance of the driver. In this work, we make the first attempt to inversely learn the taxi drivers' preferences from data and characterize the dynamics of such preferences over time. We extract two types of features, i.e., profile features and habit features, to model the decision space of drivers. Then through inverse reinforcement learning we learn the preferences of drivers with respect to these features. The results illustrate that self-improving drivers tend to keep adjusting their preferences to habit features to increase their earning efficiency, while keeping the preferences to profile features invariant. On the other hand, experienced drivers have stable preferences over time.

Predicting traffic accidents is a crucial problem to improving transportation and public safety as well as safe routing. The problem is also challenging due to the rareness of accidents in space and time and spatial heterogeneity of the environment (e.g., urban vs. rural). Most previous research on traffic accident prediction conducted by domain researchers simply applied classical prediction models on limited data without addressing the above challenges properly, thus leading to unsatisfactory performance. A small number of recent works have attempted to use deep learning for traffic accident prediction. However, they either ignore time information or use only data from a small and homogeneous study area (a city), without handling spatial heterogeneity and temporal auto-correlation properly at the same time. In this paper we perform a comprehensive study on the traffic accident prediction problem using the Convolutional Long Short-Term Memory (ConvLSTM) neural network model. A number of detailed features such as weather, environment, road condition, and traffic volume are extracted from big datasets over the state of Iowa across 8 years. To address the spatial heterogeneity challenge in the data, we propose a Hetero-ConvLSTM framework, where a few novel ideas are implemented on top of the basic ConvLSTM model, such as incorporating spatial graph features and spatial model ensemble. Extensive experiments on the 8-year data over the entire state of Iowa show that the proposed framework makes reasonably accurate predictions and significantly improves the prediction accuracy over baseline approaches.

Urban gathering events such as social protests, sport games, and traffic congestions bring significant challenges to urban management. Identifying gathering events timely is thus an important problem for city administrators and stakeholders. Previous techniques on gathering event detection are mostly descriptive, i.e., using realtime on-site observations (e.g., taxi drop-offs, traffic volume) to detect the gathering events that have already emerged. In this paper we propose a predictive approach to identify future gathering events through destination prediction of incomplete trajectories. Our approach consists of two parts, i.e., destination prediction and event forecasting. For destination prediction, we relax the Markov property assumed in most of the related work and address the consequent high-memory-cost challenge by proposing a novel Via Location Grouping (VIGO) approach for destination prediction. For event forecasting, we design an online prediction mechanism that learns from both historical and recent trajectories to address the non-stationarity of urban trip patterns. Gathering events are forecast based on projected arrivals in each location and time. A case study on real taxi data in Shenzhen, China shows that our proposed approach can correctly and timely predict gathering events. Extensive experiments show that the proposed VIGO approach achieves higher accuracy than related work for destination prediction and saves more than 82% memory cost over a baseline approach. The event forecasting based on VIGO is effective and fast enough for continuous event forecasting at one-minute frequency.

Given a spatial field and the traffic flow between neighboring locations, the early detection of gathering events ( edge ) problem aims to discover and localize a set of most likely gathering events. It is important for city planners to identify emerging gathering events that might cause public safety or sustainability concerns. However, it is challenging to solve the edge problem due to numerous candidate gathering footprints in a spatial field and the nontrivial task of balancing pattern quality and computational efficiency. Prior solutions to model the edge problem lack the ability to describe the dynamic flow of traffic and the potential gathering destinations because they rely on static or undirected footprints. In our recent work, we modeled the footprint of a gathering event as a Gathering Graph (G-Graph), where the root of the directed acyclic G-Graph is the potential destination and the directed edges represent the most likely paths traffic takes to move toward the destination. We also proposed an efficient algorithm called SmartEdge to discover the most likely nonoverlapping G-Graphs in the given spatial field. However, it is challenging to perform a systematic performance study of the proposed algorithm, due to unavailability of the ground truth of gathering events. In this article, we introduce an event simulation mechanism, which makes it possible to conduct a comprehensive performance study of the SmartEdge algorithm. We measure the quality of the detected patterns, in a systematic way, in terms of timeliness and location accuracy. The results show that, on average, the SmartEdge algorithm is able to detect patterns within a grid cell away (less than 500 meters) of the simulated events and detect patterns of the simulated events as early as 10 minutes prior to the first arrival to the gathering event.

Taxi services play an important role in the public transportation system of large cities. Improving taxi business efficiency is an important societal problem since it could improve the income of the drivers and reduce gas emissions and fuel consumption. The recent research on seeking strategies may not be optimal for the overall revenue over an extended period of time as they ignored the important impact of passengers' destinations on future passenger seeking. To address these issues, this paper investigates how to increase the revenue efficiency (revenue per unit time) of taxi drivers, and models the passenger seeking process as a Markov Decision Process (MDP). For each one-hour time slot, we learn a different set of parameters for the MDP from data and find the best move for a vacant taxi to maximize the total revenue in that time slot. A case study and several experimental evaluations on a real dataset from a major city in China show that our proposed approach improves the revenue efficiency of inexperienced drivers by up to 15% and outperforms a baseline method in all the time slots.

Given a spatial field and the traffic flow between neighboring locations, the early detection of gathering events (edge) problem aims to discover and localize a set of most likely gathering events. It is important for city planners to identify emerging gathering events which might cause public safety or sustainability concerns. However, it is challenging to solve the edge problem due to numerous candidate gathering footprints in a spatial field and the non-trivial task to balance pattern quality and computational efficiency. Prior solutions to model the edge problem lack the ability to describe the dynamic flow of traffic and the potential gathering destinations because they rely on static or undirected footprints. In contrast, in this paper, we model the footprint of a gathering event as a Gathering directed acyclic Graph (G-Graph), where the root of the G-Graph is the potential destination and the directed edges represent the most likely paths traffic takes to move towards the destination. We also proposed an efficient algorithm called SmartEdge to discover the most likely non-overlapping G-Graphs in the given spatial field. Our analysis shows that the proposed G-Graph model and the SmartEdge algorithm have the ability to efficiently and effectively capture important gathering events from real-world human mobility data. Our experimental evaluations show that SmartEdge saves 50% computation time over the baseline algorithm.

Given learning samples from a raster data set, spatial decision tree learning aims to find a decision tree classifier that minimizes classification errors as well as salt-and-pepper noise. The problem has important societal applications such as land cover classification for natural resource management. However, the problem is challenging due to the fact that learning samples show spatial autocorrelation in class labels, instead of being independently identically distributed. Related work relies on local tests (i.e., testing feature information of a location) and cannot adequately model the spatial autocorrelation effect, resulting in salt-and-pepper noise. In contrast, we recently proposed a focal-test-based spatial decision tree (FTSDT), in which the tree traversal direction of a sample is based on both local and focal (neighborhood) information. Preliminary results showed that FTSDT reduces classification errors and salt-and-pepper noise. This paper extends our recent work by introducing a new focal test approach with adaptive neighborhoods that avoids over-smoothing in wedge-shaped areas. We also conduct computational refinement on the FTSDT training algorithm by reusing focal values across candidate thresholds. Theoretical analysis shows that the refined training algorithm is correct and more scalable. Experiment results on real world data sets show that new FTSDT with adaptive neighborhoods improves classification accuracy, and that our computational refinement significantly reduces training time.

Given a collection of geo-located activities (e.g., Crime reports), ring-shaped hotspot detection (RHD) finds rings, where concentration of activities inside the ring is much higher than outside. RHD is important for the applications such as crime analysis, where it may focus the search for crime source's location, e.g. The home of a serial criminal. RHD is challenging because of the large number of candidate rings and the high computational cost of the statistical significance test. Previous statistically significant hotspot detection techniques (e.g., Sat Scan) identify circular/rectangular areas, but can not discover rings. This paper proposes a dual grid based pruning (DGP) approach to detect ring-shaped hotspots. A case study on real crime data confirms that DGP detects novel ring-shaped regions, regions that go undetected by Sat Scan. Experiments show that DGP improves the computational cost of a naive approach substantially.

Given a raster spatial framework, as well as training and test sets, the spatial decision tree learning (SDTL) problem aims to minimize classification errors as well as salt-and-pepper noise. The SDTL problem is important due to many societal applications such as land cover classification in remote sensing. However, the SDTL problem is challenging due to the spatial autocorrelation of class labels, and the potentially exponential number of candidate trees. Related work is limited due to the use of local-test-based decision nodes, which can not adequately model spatial autocorrelation during test phase, leading to high salt-and-pepper noise. In contrast, we propose a focal-test-based spatial decision tree (FTSDT) model, where the tree traversal direction for a location is based on not only local but also focal (i.e., neighborhood) properties of the location. Experimental results on real world remote sensing datasets show that the proposed approach reduces salt-and-pepper noise and improves classification accuracy.

Efficient tools are needed to identify routes and schedules to evacuate affected populations to safety in the event of natural disasters. Hurricane Rita and the recent tsunami revealed limitations of traditional approaches to provide emergency preparedness for evacuees and to predict the effects of evacuation route planning (ERP). Challenges arise during evacuations due to the spread of people over space and time and the multiple paths that can be taken to reach them; key assumptions such as stationary ranking of alternative routes and optimal substructure are violated in such situations. Algorithms for ERP were first developed by researchers in operations research and transportation science. However, these proved to have high computational complexity and did not scale well to large problems. Over the last decade, we developed a different approach, namely the Capacity Constrained Route Planner (CCRP), which generalizes shortest path algorithms by honoring capacity constraints and the spread of people over space and time. The CCRP uses time-aggregated graphs to reduce storage overhead and increase computational efficiency. Experimental evaluation and field use in Twin Cities Homeland Security scenarios demonstrated that CCRP is faster, more scalable, and easier to use than previous techniques. We also propose a novel scalable algorithm that exploits the spatial structure of transportation networks to accelerate routing algorithms for large network datasets. We evaluated our new approach for large-scale networks around downtown Minneapolis and riverside areas. This article summarizes experiences and lessons learned during the last decade in ERP and relates these to Professor Goodchild's contributions.

Given a spatiotemporal (ST) dataset and a path in its embedding spatiotemporal framework, the goal is to to identify all interesting sub-paths defined by an interest measure. Sub-path discovery is of fundamental importance for understanding climate changes, agriculture, and many other application. However, this problem is computationally challenging due to the massive volume of data, the varying length of sub-paths and non-monotonicity of interestingness throughout a sub-path. Previous approaches find interesting unit sub-paths (e.g., unit time interval) or interesting points. By contrast, we propose a Sub-path Enumeration and Pruning (SEP) approach that finds collections of long interesting sub-paths. Two case studies using climate change datasets show that SEP can find long interesting sub-paths which represent abrupt climate change. We provide theoretical analyses of correctness, completeness and computational complexity of the proposed approach. We also provide experimental evaluation of two traversal strategies for enumerating and pruning candidate sub-paths.