Abnormal behavior detection is crucial in many fields, such as social networks, financial transactions, and cyber security. However, it poses significant challenges due to the intricate structural evolution of heterogeneous graphs and the need for explainable models. To address these issues, we propose a novel method called Explainable anomalous behavior (edge) detection for dynamic heterogeneous Graphs (ExpGraph). ExpGraph captures relation-aware structural evolution to model temporal behavioral patterns and introduces a prototype alignment mechanism to improve both performance and interpretability. Specifically, prototype alignment enhances detection by en couraging discriminative representations of normal behaviors, which facilitates more accurate identification of anomalies. It also improves interpretability by enabling intuitive explanations through measuring how anomalous behaviors differ from learned normal prototypes. We conduct extensive experiments to evaluate ExpGraph against advanced competitors. It demonstrates that ExpGraph is 16.2% more effective than other methods on average. Moreover, it offers a deeper insight into abnormal behaviors in dynamic heterogeneous graphs. Our code is available at https://github.com/anonymous-123a/ExpGraph.

Similar trajectory retrieval is crucial for maritime trajectory data analysis. However, due to issues such as errors in maritime positioning devices and the accuracy limitations of satellite positioning systems at sea, maritime trajectory data often exhibit characteristics of non-uniform sampling. Existing algorithms struggle to effectively model the irregularity of non-uniformly sampled maritime trajectories, leading to reduced performance in similar trajectory retrieval. In this demonstration, we present STORM, a system designed to effectively retrieve the top-k similar trajectories, which supports both user-specified and automated query settings. STORM utilizes a learnable Fourier-based encoding method to efficiently extract spatiotemporal features from non-uniform trajectories, significantly enhancing the model's performance in similar trajectory retrieval. Our demonstration shows that, compared to state-of-the-art (SOTA) methods, STORM achieves a 41.9% improvement in performance for similar trajectory retrieval on non-uniform maritime data. Our demonstration video is available at https://github.com/itszzzyyy/STORM.

Trajectory data are crucial in intelligent transportation management, road network optimization, and urban mobility analysis. Many downstream applications, such as trajectory prediction and travel time estimation, rely on high-resolution trajectory data. However, real-world trajectories are often sparse due to GPS signal loss and power constraints. Existing trajectory recovery methods often struggle to utilize the latent hierarchical traffic conditions, and they often overlook complex movement semantics. To address these limitations, we propose sparse trajectory recovery with hierarchical dynamic traffic pattern inference (STREAM), a unified framework that collectively infers latent global and local traffic conditions from observed trajectories. By modeling these multi-scale dependencies in its encoder, STREAM enables the decoder to accurately reconstruct missing trajectory points. Additionally, our model effectively captures multi-step movement patterns to enhance the accuracy of next-location inference. Extensive experiments on real-world datasets demonstrate that our model outperforms nine existing competitors with an average improvement of 42.52% in trajectory recovery.

In this paper, we investigate the discovery of temporal anomalous subgraphs in large-scale financial networks, aiming to identify abnormal transaction behaviors among users over time. This task is crucial for the real-time detection of transaction anomalies in financial networks, such as money laundering and trading fraud. However, it poses significant challenges due to the diverse distribution of transactions, the dynamic nature of temporal networks, and the absence of theoretical foundation. To tackle these challenges, we introduce a novel Temporal Anomalous Subgraph Discovery (TempASD) algorithm with theoretical analysis. First, we propose a temporal candidate detection module that quickly pinpoints abnormal candidates by detecting anomalies in both the temporal structure and transaction distribution. Then, we introduce a carefully crafted reinforcement-learning-based refiner to optimize these candidates toward the most abnormal directions. We conducted extensive evaluations against thirteen advanced competitors. TempASD achieves an average improvement of 7x in abnormal degree compared to the state-of-the-art and is efficient in large-scale dynamic financial networks.

Motif counting is fundamental in graph analytic tasks (e.g., clustering and recommendation) but #P-hard. Recent research has focused on exploring and applying deep learning-based solutions to tackle this problem. However, these solutions assume a deterministic graph where edge existence is certain, which may not hold due to the measurement and statistical prediction errors. Meanwhile, existing methods for uncertain graphs still face considerable time costs. To address the above issues, we propose UnG-MoCha, a novel deep-learning approach to efficiently count motifs in uncertain graphs. UnG-MoCha extracts representative subgraphs via graph structure learning and learns graph and motif representations using hierarchical and classic graph neural networks, respectively. Canonical correlation analysis is used to exploit correlations between graph and motif representations, boosting accuracy. Experiments on real-world graphs demonstrate UnG-MoCha's superior performance for scalable motif counting on uncertain graphs.

In many real-world applications, the evolving relationships between entities can be modeled as temporal graphs, where each edge has a timestamp representing the interaction time. As a fundamental problem in graph analysis, community search (CS) in temporal graphs has received growing attention but exhibits two major limitations: (1) Traditional methods typically require predefined subgraph structures, which are not always known in advance. (2) Learning-based methods struggle to capture temporal interaction information. To fill this research gap, in this paper, we propose an effective Unsupervised Temporal Community Search with pre-training of temporal dynamics and subgraph knowledge model (UTCS ). UTCS contains two key stages: offline pre-training and online search. In the first stage, we introduce multiple learning objectives to facilitate the pre-training process in the unsupervised learning setting. In the second stage, we identify a candidate subgraph and compute community scores using the pre-trained node representations and a novel scoring mechanism to determine the final community members. Experiments on five real-world datasets demonstrate the effectiveness of the proposed method.

Road network applications, such as navigation, incident detection, and Point-of-Interest (POI) recommendation, make extensive use of network edge weights (e.g., traveling times). Some of these weights can be missing, especially in a road network where traffic data may not be available for every road. In this article, we study the stochastic weight completion (SWC) problem, which computes the weight distributions of missing road edges. This is difficult, due to the intricate temporal and spatial correlations among neighboring edges. Besides, the road network can be sparse , i.e., there is a lack of traveling information in a large portion of the network. To tackle these challenges, we propose a multi-granularity framework for Region-Wise Graph Completion (RegGC) . To learn coarse spatial correlations among distantly located roads, we construct a region-wise hypergraph neural architecture based on semantic region dependencies. For finer spatial correlations, we incorporate contextual road network properties (e.g., speed limits, lane counts, and road types). Moreover, it incorporates recent and periodic dimensions of road traffic. We evaluate RegGC against 10 existing methods on 3 real road network datasets. They show that RegGC is more effective and efficient than state-of-the-art solutions.

Road network applications, such as navigation, incident detection, and Point-of-Interest (POI) recommendation, make extensive use of network edge weights (e.g., traveling times). Some of these weights can be missing, especially in a road network where traffic data may not be available for every road. In this paper, we study the stochastic weight completion (SWC) problem, which computes the weight distributions of missing road edges. This is difficult, due to the intricate temporal and spatial correlations among neighboring edges. Moreover, the road network can be sparse, i.e., there is a lack of traveling information in a large portion of the network. To tackle these challenges, we propose the Contextual Graph Completion (ConGC). We propose to incorporate the contextual properties about the road network (e.g., speed limits, number of lanes, road types) to provide finer granularity of spatial correlations. Moreover, ConGC incorporates temporal and periodic dimensions of the road traffic. We evaluate ConGC against existing methods on three real road network datasets. They show that ConGC is more effective and efficient than state-of-the-art solutions.

Given a directed graph G, the directed densest subgraph (DDS) problem refers to finding a subgraph from G, whose density is the highest among all subgraphs of G. The DDS problem is fundamental to a wide range of applications, such as fake follower detection and community mining. Theoretically, the DDS problem closely connects to other essential graph problems, such as network flow and bipartite matching. However, existing DDS solutions suffer from efficiency and scalability issues. In this paper, we develop a convex-programming-based solution by transforming the DDS problem into a set of linear programs. Based on the duality of linear programs, we develop efficient exact and approximation algorithms. Especially, our approximation algorithm can support flexible parameterized approximation guarantees. We have performed an extensive empirical evaluation of our approaches on eight real large datasets. The results show that our proposed algorithms are up to five orders of magnitude faster than the state-of-the-art.

In this paper, we study anomalous trajectory detection, which aims to extract abnormal movements of vehicles on the roads. This important problem, which facilitates understanding of traffic behavior and detection of taxi fraud, is challenging due to the varying traffic conditions at different times and locations. To tackle this problem, we propose the deep -probabilistic-based time-dependent anomaly detection algorithm ( DeepTEA ). This method, which employs deep-learning methods to obtain time-dependent outliners from a huge volume of trajectories, can handle complex traffic conditions and detect outliners accurately. We further develop a fast and approximation version of DeepTEA, in order to capture abnormal behaviors in real-time. Compared with state-of-the-art solutions, our method is 17.52% more accurate than seven competitors on average, and can handle millions of trajectories.

Finding the densest subgraph (DS) from a graph is a fundamental problem in graph databases. The DS obtained, which reveals closely related entities, has been found to be useful in various application domains such as e-commerce, social science, and biology. However, in a big graph that contains billions of edges, it is desirable to find more than one subgraph cluster that are not necessarily the densest, yet they reveal closely-related vertices. In this paper, we study the locally densest subgraph (LDS), a recently-proposed variant of DS. An LDS is a subgraph which is the densest among the "local neighbors". Given a graph G , a number of LDS's can be returned, which reflect different dense regions of G and thus give more information than DS. The existing LDS solution suffers from low efficiency. We thus develop a convex-programming-based solution that enables powerful pruning. Extensive experiments on seven real large graph datasets show that our proposed algorithm is up to four orders of magnitude faster than the state-of-the-art.

Graph databases witness the rise of Graph Query Language (GQL) in recent years, which enables non-programmers to express a graph query. However, the current solution does not support motif-related queries on knowledge graphs, which are proven important in many real-world scenarios. In this paper, we propose a GQL framework for mining knowledge graphs, named M-Cypher. It supports motif-related graph queries in an effective, efficient and user-friendly manner. We demonstrate the usage of the system by the emerging Covid-19 knowledge graph analytic tasks.

Incident detection (ID), or the automatic discovery of anomalies from road traffic data (e.g., road sensor and GPS data), enables emergency actions (e.g., rescuing injured people) to be carried out in a timely fashion. Existing ID solutions based on data mining or machine learning often rely on dense traffic data; for instance, sensors installed in highways provide frequent updates of road information. In this paper, we ask the question: Can ID be performed on sparse traffic data (e.g., location data obtained from GPS devices equipped on vehicles)? As these data may not be enough to describe the state of the roads involved, they can undermine the effectiveness of existing ID solutions. To tackle this challenge, we borrow an important insight from the transportation area, which uses trajectories (i.e., moving histories of vehicles) to derive incident patterns. We study how to obtain incident patterns from trajectories and devise a new solution (called Filter-Discovery-Match (FDM)) to detect anomalies in sparse traffic data. Experiments on a taxi dataset in Hong Kong and a simulated dataset show that FDM is more effective than state-of-the-art ID solutions on sparse traffic data.

Traffic incidents cause great losses to people's lives and property, and have aroused great attention from researchers. In recent years, many machine learning methods have been utilized for traffic incident detection, e.g. Support Vector Machine (SVM) and Neural Networks (NN). However, all of them fail to consider the full spatial-temporal correlation on traffic data. In addition, the periodicity in traffic data is not well utilized. Traffic data in the same workday usually follows a similar pattern. In this paper, we introduce a deep learning framework, which captures both full spatial-temporal correlation and periodicity, to detect incidents on freeways. Experiments show that our method performs better than the state-of-the-art.