Similarity-based vector search, which retrieves the most similar vectors to a given query vector from a large vector dataset, underlies many applications such as search, recommendation, and Large Language Models (LLMs). Some systems run vector search on GPUs to enjoy GPU's high parallelism, but we observe that they are limited in query throughput and latency. In particular, their query-centric GPU kernel conducts computation independently for each query, failing to reuse data loaded to the GPU shared memory across queries and leading to a low GPU compute utilization. While their batch-based task reordering rearranges computation for queries in a batch to reduce CPU-GPU data transfer, but latency is prolonged since each query needs to wait for its slowest task. To tackle these problems, we propose Hitcher. Specifically, to reuse data across queries and improve GPU utilization, Hitcher implements a cluster-centric GPU kernel to batch computation on the same data for multiple queries. To reduce query latency, Hitcher adopts the hitch-ride ordering, which preserves the arrival order for query processing while batching computation across queries to improve efficiency. Hitcher can also offload computation tasks to the CPU to reduce CPU-GPU data transfer and utilize multiple GPUs. Experimental results show that Hitcher achieves up to 22× lower P99 query latency and 9× higher query throughput when compared with the state-of-the-art GPU-based vector query processing systems.

Modeling asynchronous event sequences is crucial in numerous real-world applications such as healthcare monitoring, financial transaction analysis, and so on. Traditional temporal point processes, including Hawkes Processes, often fail to capture complex dependencies due to their parametric limitations. While neural approaches like RNNs and Transformers have improved flexibility, they struggle with computational inefficiency, and attention saturation. In this paper, we introduce the Mamba Hawkes Process (MHP), the first framework to integrate selective state space model (Mamba) with temporal point processes. MHP leverages time-varying state transitions and input-dependent gating to efficiently encode event history and capture long-term dependencies with linear complexity. Importantly, we provide theoretical guarantees showing that MHP generalizes both classical multi-exponential Hawkes processes and exponential-decay gated RNNs, underscoring its expressive power and theoretical soundness. To address the inherent constraints of pure state space models in handling heterogeneous event interactions, we further develop Adaptive Mamba Hawkes Process (A-MHP) that incorporates two novel mechanisms: a Time-Scaling Mechanism that adaptively weights time intervals based on event type and history, and a Dual-Channel State Transition that adaptively processes event content and temporal dynamics for more refined state updates. Extensive experiments on synthetic and real-world datasets demonstrate that MHP and A-MHP consistently outperform state-of-the-art baselines in event prediction tasks, particularly in long-sequence scenarios. Our work establishes a scalable and theoretically grounded paradigm for event sequence modeling, with practical implications for predictive maintenance, anomaly detection, and dynamic system analysis. The code is available at https://github.com/Ethan-Shen-Individual-Lab/Mamba-Hawkes-Process.

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.

Structural Graph Clustering is a well-known problem that aims to identify clusters and distinguish between special roles, such as hub and outlier. However, SCAN, the fundamental structural clustering model, is designed for pairwise graphs and fails to capture the unique structural information inherent in hypergraphs when clustering hypergraphs. Motivated by this, we propose a new structural clustering model, HSCAN, specifically for hypergraphs. We further design an Order-Index to accelerate fetching the key information of the HSCAN and a Lightweight Similarity Bucket Index to reduce the index cost. Next, we present an index-based sequential query algorithm with high performance and a parallel query algorithm to process large hypergraphs faster. Additionally, we provide the algorithms for constructing Order-Index and Lightweight Similarity Bucket Index. Extensive experiments on both real-world and synthetic datasets show that HSCAN performs better than existing models, and the two index-based query algorithms are up to three orders of magnitude faster than the existing algorithm.

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.

Temporal graphs, widely used in social network modeling, are valuable for research but pose challenges due to data accessibility and privacy concerns. High-quality graph generation models can produce surrogate data for sharing and training, benefiting tasks such as behavior analysis, anomaly detection, and data augmentation. However, existing deep learning and probabilistic approaches often struggle to balance global statistical properties with local structural details. To overcome this limitation, we leverage motifs, small subgraphs that serve as the building blocks of complex networks, to encode local information. Based on a spectral analysis of motifs, we propose MoDiff, a novel motif-aware diffusion model for temporal graph generation. MoDiff integrates motifs into a diffusion framework by employing motif-enhanced Hermitian matrices that capture local structures and edge orientations, while the spectral diffusion model efficiently generates graphs. Moreover, MoDiff supports controllable graph generation by adjusting density parameters to simulate the evolution of temporal graphs. Experimental results demonstrate that MoDiff outperforms existing approaches, reducing degree discrepancies by 10-50% and clustering discrepancies by 50-90%, while better preserving higher-order structural features. Our code is available at: https://github.com/Yuwe1XU/MoDiff.

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.

With the growing integration of structured and unstructured data, new methods have emerged for performing similarity searches on vectors while honoring structured attribute constraints, i.e., a process known as Filtering Approximate Nearest Neighbor (Filtering ANN) search. Since many of these algorithms have only appeared in recent years and are designed to work with a variety of base indexing methods and filtering strategies, there is a pressing need for a unified analysis that identifies their core techniques and enables meaningful comparisons. In this work, we present a unified Filtering ANN search interface that encompasses the latest algorithms and evaluate them extensively from multiple perspectives. First, we propose a comprehensive taxonomy of existing Filtering ANN algorithms based on attribute types and filtering strategies. Next, we analyze their key components, i.e., index structures, pruning strategies, and entry point selection, to elucidate design differences and tradeoffs. We then conduct a broad experimental evaluation on 10 algorithms and 12 methods across 4 datasets (each with up to 10 million items), incorporating both synthetic and real attributes and covering selectivity levels from 0.1% to 100%. Finally, an in-depth component analysis reveals the influence of pruning, entry point selection, and edge filtering costs on overall performance. Based on our findings, we summarize the strengths and limitations of each approach, provide practical guidelines for selecting appropriate methods, and suggest promising directions for future research. Our code is available at: https://github.com/lmccccc/FANNBench.

As a building block of many graph-based areas, the s-t path enumeration problem aims to find all paths between s and t by satisfying a given constraint, e.g., hop numbers. In many real-world scenarios, graphs are multi-attribute, where vertices and edges are associated with numerical attributes, such as expense or distance in road networks. However, existing methods have not fully leveraged all attributes in s-t path analysis. Hence, in this paper, we study the problem of skyline path enumeration, which aims to identify paths that balance multiple attributes, ensuring that no skyline result is dominated by another, thus meeting diverse user needs. To efficiently tackle this problem, we design a task-oriented core attribute index, called CAI, to rule out all redundant vertices and edges not located in any skyline path. Additionally, we introduce a hop-dependency label propagation strategy to construct the CAI index in parallel, improving the indexing process. Based on this index, we further design a CAI-based querying strategy that reduces fruitless explorations between candidate vertices not in the same skyline path, significantly optimizing query processing time. Experimental evaluations on fifteen real-world graphs show that CAI outperforms existing methods by up to four orders of magnitude in speed while demonstrating enhanced scalability and well-bound memory costs.

Bipartite graphs are ubiquitous in many domains, e.g., e-commerce platforms, social networks, and academia, by modeling interactions between distinct entity sets. Within these graphs, the butterfly motif, a complete 2×2 biclique, represents the simplest yet significant subgraph structure, crucial for analyzing complex network patterns. Counting the butterflies offers significant benefits across various applications, including community analysis and recommender systems. Additionally, the temporal dimension of bipartite graphs, where edges activate within specific time frames, introduces the concept of historical butterfly counting, i.e., counting butterflies within a given time interval. This temporal analysis sheds light on the dynamics and evolution of network interactions, offering new insights into their mechanisms. Despite its importance, no existing algorithm can efficiently solve the historical butterfly counting task. To address this, we design two novel indices whose memory footprints are dependent on #butterflies and #wedges, respectively. Combining these indices, we propose a graph structure-aware indexing approach that significantly reduces memory usage while preserving exceptional query speed. To further reduce the index size and boost the query efficiency, we design an index compression strategy, enabling the fast, high-quality, and unbiased approximation of historical butterfly counts. We theoretically prove that our approach is particularly advantageous on power-law graphs, a common characteristic of real-world bipartite graphs, by surpassing traditional complexity barriers for general graphs. Extensive experiments reveal that our query algorithms outperform existing methods by up to five magnitudes, effectively balancing speed with manageable memory requirements.

2-hop labeling has been widely utilized to accelerate the efficiency of online shortest distance queries. Given the nature of frequent changes in real-world graphs, the efficient maintenance of 2-hop labeling index has been extensively studied recently. However, existing methods cannot efficiently process large-scale graphs due to their high time and memory costs, and most of them process large batches of updates sequentially, significantly decreasing efficiency. In this paper, we propose a novel algorithm for maintaining the 2-hop labeling index in a parallel manner, called M2HL , which can efficiently handle both edge insertions and deletions. Moreover, we theoretically prove that M2HL maintains both correctness and minimality for the updated 2-hop labeling index. Our experiments on ten large-scale graphs demonstrate that M2HL outperforms the state-of-the-art 2-hop labeling maintenance methods by up to four orders of magnitude in speed while maintaining correctness and minimality, as well as exhibiting strong scalability and low memory usage.

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.

Job-market mobility prediction plays a crucial role in optimizing human capital usage for both employees and employers. Most conventional methods primarily focus on learning sequential career sequences while ignoring the sufficient information extraction of mutual entity correlations in the job market. In this work, we push forward to exploit the heterogeneous relational knowledge among the job market structures by proposing a model namely Attentive Heterogeneous Knowledge Learning and Synergy (AHKLS). Equipped with the subsequent module of time-aware perception, AHKLS achieves effective career trajectory encoding for job-market mobility prediction. To evaluate the AHKLS performance, we conduct extensive experiments on three real-world datasets with different sizes. The empirical analyses demonstrate not only the performance superiority of AHKLS over several competing methods, but also the module effectiveness and model compatibility with other methods in enhancing the mobility prediction tasks accordingly.

Core decomposition is a critical metric for evaluating the vertex importance and analyzing graph structure. Given a graph$G$, a k-core is the largest subgraph of$G$where each vertex has at least$k$neighbors. Most existing works mainly focus on homogeneous graphs in which edges are of the same type and cannot be applied to heterogeneous information networks (HINs) directly. However, most real-world networks are HINs which consist of different vertex types and edge types. To reveal the cohesive subgraphs with hierarchical relations on HINs, we adopt the well-known$(k,\mathcal{P})$-core model to compute coreness over HINs, where$\mathcal{P}$is a meta-path, i.e., a sequence of relations defined between different types of vertices. Hence, the$(k,\mathcal{P})$-core is a subgraph where each vertex is connected to at least$k$other vertices via instances of$\mathcal{P}$. Based on two kinds of sparse matrix products, we propose two kinds of algebraic core decomposition algorithms, which are suitable for general HINs and locally dense HINs, respectively. We have performed extensive empirical evaluations of our algorithms on six large real-world HINs. The results show that the proposed solutions are highly efficient for core decomposition and achieve up to$258.84\times$speedup than the state-of-the-art parallel algorithm on 20 cores. Moreover, other HIN tasks that involve homogeneous graph construction can also benefit from our algorithms.

Signed networks, characterized by edges labeled as either positive or negative, offer nuanced insights into interaction dynamics beyond the capabilities of unsigned graphs. Central to this is the task of identifying the maximum balanced subgraph, crucial for applications like polarized community detection in social networks and portfolio analysis in finance. Traditional models, however, are limited by an assumption of perfect partitioning, which fails to mirror the complexities of real-world data. Addressing this gap, we introduce an innovative generalized balanced subgraph model that incorporates tolerance for imbalance. Our proposed region-based heuristic algorithm, tailored for this NP -hard problem, strikes a balance between low time complexity and high-quality outcomes. Comparative experiments validate its superior performance against leading solutions, delivering enhanced effectiveness (notably larger subgraph sizes) and efficiency (achieving up to 100× speedup) in both traditional and generalized contexts.

Identifying dense subgraphs called quasi-cliques is pivotal in various graph mining tasks across domains like biology, social networks, and e-commerce. However, recent algorithms still suffer from efficiency issues when mining large quasi-cliques in massive and complex graphs. Our key insight is that vertices within a quasi-clique exhibit similar neighborhoods to some extent. Based on this, we introduce NBSim and FastNBSim, efficient algorithms that find near-maximum quasi-cliques by exploiting vertex neighborhood similarity. FastNBSim further uses MinHash approximations to reduce the time complexity for similarity computation. Empirical evaluation on 10 real-world graphs shows that our algorithms deliver up to three orders of magnitude speedup versus the state-of-the-art algorithms, while ensuring high-quality quasi-clique extraction.

Sparse matrices are often used to model the interactions among different objects and they are prevalent in many areas including e-commerce, social network, and biology. As one of the fundamental matrix operations, the sparse matrix chain multiplication (SMCM) aims to efficiently multiply a chain of sparse matrices, which has found various real-world applications in areas like network analysis, data mining, and machine learning. The efficiency of SMCM largely hinges on the order of multiplying the matrices, which further relies on the accurate estimation of the sparsity values of intermediate matrices. Existing matrix sparsity estimators often struggle with large sparse matrices, because they suffer from the accuracy issue in both theory and practice. To enable efficient SMCM, in this paper we introduce a novel row-wise sparsity estimator (RS-estimator), a straightforward yet effective estimator that leverages matrix structural properties to achieve efficient, accurate, and theoretically guaranteed sparsity estimation. Based on the RS-estimator, we propose a novel ordering algorithm for determining a good order of efficient SMCM. We further develop an efficient parallel SMCM algorithm by effectively utilizing multiple CPU threads. We have conducted experiments by multiplying various chains of large sparse matrices extracted from five real-world large graph datasets, and the results demonstrate the effectiveness and efficiency of our proposed methods. In particular, our SMCM algorithm is up to three orders of magnitude faster than the state-of-the-art algorithms.

The enumeration of hop-constrained simple paths is a building block in many graph-based areas. Due to the enormous search spaces in large-scale graphs, a single machine can hardly satisfy the requirements of both efficiency and memory, which causes an urgent need for efficient distributed methods. In practice, it is inevitable to produce plenty of intermediate results when directly extending centralized methods to the distributed environment, thereby causing a memory crisis and weakening the query performance. The state-of-the-art distributed method HybridEnum designed a hybrid search paradigm to enumerate simple paths. However, it makes massive exploration for the redundant vertices not located in any simple path, thereby resulting in poor query performance. To alleviate this problem, we design a distributed approach DistriEnum to optimize query performance and scalability with well-bound memory consumption. Firstly, DistriEnum adopts a graph reduction strategy to rule out the redundant vertices without satisfying the constraint of hop number. Then, a core search paradigm is designed to simultaneously reduce the traversal of shared subpaths and the storage of intermediate results. Moreover, DistriEnum is equipped with a task division strategy to theoretically achieve workload balance. Finally, a vertex migration strategy is devised to reduce the communication cost during the enumeration. The comprehensive experimental results on 10 real-world graphs demonstrate that DistriEnum achieves up to 3 orders of magnitude speedup than HybridEnum in query performance and exhibits superior performances on scalability, communication cost, and memory consumption.

Densest subgraph discovery (DSD) is a fundamental topic in graph mining. It has been extensively studied in the literature and has found many real applications in a wide range of fields, such as biology, finance, and social networks. As a typical problem of DSD, the k-clique densest subgraph (CDS) problem aims to detect a subgraph from a graph, such that the ratio of the number of k-cliques over the number of its vertices is maximized. This problem has received plenty of attention in the literature, and is widely used in identifying larger ''near-cliques''. Existing CDS solutions, either k-core or convex programming based solutions, often need to enumerate almost all the k-cliques, which is very inefficient because real-world graphs usually have a vast number of k-cliques. To improve the efficiency, in this paper, we propose a novel framework based on the Frank-Wolfe algorithm, which only needs k-clique counting, rather than k-clique enumeration, where the former one is often much faster than the latter one. Based on the framework, we develop an efficient approximation algorithm, by employing the state-of-the-art k-clique counting algorithm and proposing some optimization techniques. We have performed extensive experimental evaluation on 14 real-world large graphs and the results demonstrate the high efficiency of our algorithms. Particularly, our algorithm is up to seven orders of magnitude faster than the state-of-the-art algorithm with the same accuracy guarantee.

Distance labeling approaches are widely adopted to speed up the shortest-distance query performance. Due to the explosive growth of data graphs, a single machine can hardly satisfy the requirements of both computational power and memory capacity, which causes an urgent need for efficient distributed methods. As the graph is distributed across different machines, it is inevitable to frequently exchange messages among different machines when deploying the existing centralized distance labeling methods on the distributed environment, thereby producing serious communication costs and weakening the scalability. To alleviate this problem, we design a distributed hop-based indexDH-Index, which is designed based on a newly proposed boundary graph structure and restricts the index-based hop number of each connected vertex pair within 4 hops. In addition, we propose a hierarchical algorithm to accelerate the index construction and reduce the communication cost. Furthermore, a bidirectional searching strategy is proposed to efficiently resolve the query tasks based on DH-Index. The comprehensive experimental results on eight real-world graphs demonstrate that DH-Index achieves up to 65.5× and 3 orders of magnitude speedup than the existing methods in indexing time and query performance respectively, and exhibits superior capabilities on memory space, communication cost, and scalability.

In the heterogeneous information network (HIN), a motif-clique is a "complete graph" for a given motif (or a small connected graph) that could capture the desired relationship in the motif. The maximal motif-cliques of HINs have found various applications in community discovery, recommendation, and biological network analysis. The state-of-the-art algorithm for enumerating maximal motif-cliques may have to explore all possible subgraphs of a maximal motif-clique and check whether a maximal motif-clique has been enumerated at each recursive step, which is very time-consuming. To improve the efficiency of enumeration, in this paper, we develop efficient algorithms for maximal motif-clique enumeration over large HINs. We first introduce an order-based framework to avoid duplicated enumeration, which results in lower time complexity compared to the existing algorithm. We then propose a pivot-based pruning strategy, which significantly reduces the search space. We further optimize the process of identifying the candidate sets and locating the subgraphs containing the maximal motif-cliques. Extensive experiments on five real-world HINs demonstrate that our proposed algorithm achieves high efficiency and is up to three orders of magnitude faster than the state-of-the-art algorithm.

As a fundamental topic in graph mining, Densest Subgraph Discovery (DSD) has found a wide spectrum of real applications. Several DSD algorithms, including exact and approximation algorithms, have been proposed in the literature. However, these algorithms have not been systematically and comprehensively compared under the same experimental settings. In this paper, we first summarize a unified framework to incorporate all DSD algorithms from a high-level perspective. We then extensively compare representative DSD algorithms over a range of graphs - from small to billion-scale - and examine the effectiveness of all methods, providing a thorough analysis of DSD algorithms. As a byproduct of our experimental analysis, we are also able to identify new variants of the DSD algorithms over undirected graphs, by combining existing techniques, which are up to 10× faster than the state-of-the-art algorithm with the same accuracy guarantee. Finally, based on the findings, we offer promising research opportunities. We believe that a deeper understanding of the behavior of existing algorithms can provide new valuable insights for future research.

Searching on bipartite graphs serves as a fundamental task for various real-world applications, such as recommendation systems, database retrieval, and document querying. Conventional approaches rely on similarity matching in continuous euclidean space of vectorized node embeddings. To handle intensive similarity computation efficiently, hashing techniques for graph-structured data have emerged as a prominent research direction. However, despite the retrieval efficiency in Hamming space, previous studies have encounteredcatastrophic performance decay. To address this challenge, we investigate the problem of hashing with Graph Convolutional Network for effective Top-N search. Our findings indicate the learning effectiveness of incorporating hashing techniques within the exploration of bipartite graph reception fields, as opposed to simply treating hashing as post-processing to output embeddings. To further enhance the model performance, we advance upon these findings and proposeBipartiteGraphContrastiveHashing (BGCH+). BGCH+ introduces a novel dual augmentation approach to bothintermediate informationandhash code outputsin the latent feature spaces, thereby producing more expressive and robust hash codes within a dual self-supervised learning paradigm. Comprehensive empirical analyses on six real-world benchmarks validate the effectiveness of our dual feature contrastive learning in boosting the performance of BGCH+ compared to existing approaches.

As a fundamental problem in graph data mining, Densest Subgraph Discovery (DSD) aims to find the subgraph with the highest density from a graph. It has been studied for several decades and found a large number of real-world applications, such as network community detection, regulatory motif discovery in DNA, graph index construction, and fake follower detection. Although there are many existing DSD algorithms, they are often not scalable or efficient to process large-scale graphs, since most of them are serial algorithms and can only leverage the computing resource of a single CPU core. To tackle these issues, in this paper we propose efficient parallel algorithms for solving the DSD problems on both undirected and directed graphs at scale. Our main idea is to use the k-cores (a kind of dense subgraph) to approximate the densest subgraph in the undirected graphs, and then propose efficient parallel algorithms for computing the cores by optimizing the iterative process and also reducing the number of iterations. We further extend this idea for directed graphs by introducing a novel concept, named w-induced subgraph, to avoid unnecessary enumerations of x or y when searching [x,y]-cores (a kind of directed dense subgraph to approximate the densest). To verify the scalability and efficiency of the proposed algorithms, we have conducted extensive experiments on 12 large real-world graphs, and four of them are billion-scale. The experimental results show that our proposed algorithms outperform the state-of-the-art algorithms on both undirected and directed graphs, in terms of scalability and efficiency.

In this paper, for the first time, we introduce the concepts of window-CCs and window-SCCs on undirected and directed temporal graphs, respectively. We then study the queries of window-CC and window-SCC by developing several efficient index-based query solutions. The space costs of the best indices are linear to the sizes of the temporal graphs. The extensive experimental evaluation on 12 real-world datasets demonstrates the high efficiency and effectiveness of the proposed solutions. In the future, we will develop distributed index construction algorithms, which would be useful for very large temporal graphs containing billions of edges. In the future, we will implement our algorithms by using a distributed computing platform (e.g., Pregel), which would be very useful when the temporal graph is too large to be kept by a single machine.

The densest subgraph problem (DSP) is of great significance due to its wide applications in different domains. Meanwhile, diverse requirements in various applications lead to different density variants for DSP. Unfortunately, existing DSP algorithms cannot be easily extended to handle those variants efficiently and accurately. To fill this gap, we first unify different density metrics into a generalized density definition. We further propose a new model, c-core, to locate the general densest subgraph and show its advantage in accelerating the searching process. Extensive experiments show that our c-core-based optimization can provide up to three orders of magnitude speedup over baselines. Moreover, we study an important variant of DSP under a size constraint, namely the densest-at-least-k-subgraph (DalkS) problem. We propose an algorithm based on graph decomposition, and it is likely to give a solution that is at least 0.8 of the optimal density in our experiments, while the state-of-the-art method can only ensure a solution with density at least 0.5 of the optimal density. Our experiments show that our DalkS algorithm can achieve at least 0.99 of the optimal density for over one-third of all possible size constraints.

Given a graph G , a motif (e.g., 3-node clique) is a fundamental building block for G. Recently, motif-based graph analysis has attracted much attention due to its efficacy in tasks such as clustering, ranking, and link prediction. These tasks require Network Motif Discovery (NMD) at the early stage to identify the motifs of G. However, existing NMD solutions have two drawbacks: (1) Lack of theoretical guarantees on the quality of the samples generated using the existing methods, and (2) inefficient algorithms, which are not scalable for large graphs. These limitations hinder the exploration of motifs for analyzing large graphs. To address the above issues, we propose a novel solution named MOSER ( MO tif Discovery using SER ial Test). This novel NMD framework leverages a significance testing method known as the serial test, which differs from the existing solutions. We further propose two fast incremental subgraph counting algorithms, allowing MOSER to scale to larger graphs than ever possible before. Extensive experimental results show that using MOSER can improve the state-of-the-art up to 5 orders of magnitude in efficiency and that the motifs found by MOSER facilitate downstream tasks such as link prediction.

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.

As one of the most fundamental problems in graph data mining, the densest subgraph discovery (DSD) problem has found a broad spectrum of real applications, such as social network community detection, graph index construction, regulatory motif discovery in DNA, fake follower detection, and so on. Theoretically, DSD closely relates to other fundamental graph problems, such as network flow and bipartite matching. Triggered by these applications and connections, DSD has garnered much attention from the database, data mining, theory, and network communities. In this tutorial, we first highlight the importance of DSD in various applications and the unique challenges that need to be addressed. Subsequently, we classify existing DSD solutions into several groups, which cover around 50 research papers published in many well-known venues (e.g., SIGMOD, PVLDB, TODS, WWW), and conduct a thorough review of these solutions in each group. Afterwards, we analyze and compare the models and solutions in these works. Finally, we point out a list of promising future research directions. We believe that this tutorial not only helps researchers have a better understanding of existing densest subgraph models and solutions, but also provides them insights for future study.

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.

Community search (CS) enables personalized community discovery and has found a wide spectrum of emerging applications such as setting up social events and friend recommendation. While CS has been extensively studied for conventional homogeneous networks, the problem for heterogeneous information networks (HINs) has received attention only recently. However, existing studies suffer from several limitations, e.g., they either require users to specify a meta-path or relational constraints, which pose great challenges to users who are not familiar with HINs. To address these limitations, in this paper, we systematically study the problem of CS over large star-schema HINs without asking users to specify these constraints; that is, given a set Q of query vertices with the same type, find the most-likely community from a star-schema HIN containing Q , in which all the vertices are with the same type and close relationships. To capture the close relationships among vertices of the community, we employ the meta-path-based core model, and maximize the number of shared meta-paths such that each of them results in a cohesive core containing Q. To enable efficient CS, we first develop online algorithms via exploiting the anti-monotonicity property of shared meta-paths. We further boost the efficiency by proposing a novel index and an efficient index-based algorithm with elegant pruning techniques. Extensive experiments on four real large star-schema HINs show that our solutions are effective and efficient for searching communities, and the index-based algorithm is much faster than the online algorithms.

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.

Path-based solutions have been shown to be useful for various graph analysis tasks, such as link prediction and graph clustering. However, they are no longer adequate for handling complex and gigantic graphs. Recently, motif-based analysis has attracted a lot of attention. A motif, or a small graph with a few nodes, is often considered as a fundamental unit of a graph. Motif-based analysis captures high-order structure between nodes, and performs better than traditional "edge-based" solutions. In this paper, we study motif-path , which is conceptually a concatenation of one or more motif instances. We examine how motif-paths can be used in three path-based mining tasks, namely link prediction, local graph clustering and node ranking. We further address the situation when two graph nodes are not connected through a motif-path, and develop a novel defragmentation method to enhance it. Experimental results on real graph datasets demonstrate the use of motif-paths and defragmentation techniques improves graph analysis effectiveness.

Given a directed graph G , the directed densest subgraph (DDS) problem refers to the finding of a subgraph from G , whose density is the highest among all the subgraphs of G . The DDS problem is fundamental to a wide range of applications, such as fraud detection, community mining, and graph compression. However, existing DDS solutions suffer from efficiency and scalability problems: on a 3,000-edge graph, it takes three days for one of the best exact algorithms to complete. In this article, we develop an efficient and scalable DDS solution. We introduce the notion of [ x , y ]-core, which is a dense subgraph for G , and show that the densest subgraph can be accurately located through the [ x , y ]-core with theoretical guarantees. Based on the [ x , y ]-core, we develop exact and approximation algorithms. We further study the problems of maintaining the DDS over dynamic directed graphs and finding the weighted DDS on weighted directed graphs, and we develop efficient non-trivial algorithms to solve these two problems by extending our DDS algorithms. We have performed an extensive evaluation of our approaches on 15 real large datasets. The results show that our proposed solutions are up to six orders of magnitude faster than the state-of-the-art.

Given a directed graph G, the directed densest subgraph (DDS) problem refers to the finding of a subgraph from G, whose density is the highest among all the subgraphs of G. The DDS problem is fundamental to a wide range of applications, such as fraud detection, community mining, and graph compression. However, existing DDS solutions suffer from efficiency and scalability problems: on a three-thousand-edge graph, it takes three days for one of the best exact algorithms to complete. In this paper, we develop an efficient and scalable DDS solution. We introduce the notion of [x, y]-core, which is a dense subgraph for G, and show that the densest subgraph can be accurately located through the [x, y]-core with theoretical guarantees. Based on the [x, y]-core, we develop exact and approximation algorithms. We have performed an extensive evaluation of our approaches on eight real large datasets. The results show that our proposed solutions are up to six orders of magnitude faster than the state-of-the-art.

In graph applications (e.g., biological and social networks), various analytics tasks (e.g., clustering and community search) are carried out to extract insight from large and complex graphs. Central to these tasks is the counting of the number of motifs , which are graphs with a few nodes. Recently, researchers have developed several fast motif counting algorithms. Most of these solutions assume that graphs are deterministic, i.e., the graph edges are certain to exist. However, due to measurement and statistical prediction errors, this assumption may not hold, and hence the analysis quality can be affected. To address this issue, we examine how to count motifs on uncertain graphs, whose edges only exist probabilistically. Particularly, we propose a solution framework that can be used by existing deterministic motif counting algorithms. We further propose an approximation algorithm. Extensive experiments on real datasets show that our algorithms are more effective and efficient than existing solutions.