Subgraph matching is a fundamental problem in graph analysis. Recently, many algorithms have been developed, often using classic backtracking search. This traditional backtracking search matches one vertex at a time, denoted as BⓈ1, which can lead to redundant computations due to overlapping search spaces. To address this problem, we propose a novel batch-backtracking search framework that enables matching a set of data vertices X , denoted as BⓈ X , in each backtracking step. BⓈ X models the search space as a "search box", allowing for flexible search space exploration and significantly minimizing the overlap between search spaces. It effectively selects batches to cluster data vertices with similar search spaces. For each search box, we introduce a refinement method to filter out unpromising candidate mappings. Furthermore, we propose a homomorphism termination to break the backtracking process as early as possible and an efficient embedding enumeration method to list all embeddings within the search box simultaneously. Extensive experiments on real-world graphs demonstrate that BⓈ X significantly outperforms existing state-of-the-art algorithms, achieving a speedup of one to two orders of magnitude on most graphs under the EPS metric.

The constrained shortest path problem is a fundamental and challenging task in applications built on graphs. In this paper, we formalize and study the$Min$-$Max$resource-constrained shortest path ($Min$-$Max$RCSP) problem, which generalizes the well-studied$Max$RCSP problem. The objective is to find a simple path of minimum cost between two query nodes, subject to resource constraints between minimum and maximum limits. This problem has wide applications in fields such as delay networks and transportation. However, we theoretically prove that computing the optimal solution is NP-hard. We propose a two-stage approach that involves resource-based graph reduction followed by cost-guided path generation. To reduce the cost of expensive acyclicity checking, we introduce the technique of ancestor checking based on the shortest path tree. Furthermore, we present an even faster incremental search approach that considers both the path cost and resource constraints while avoiding acyclicity checking. Extensive experiments on twenty real graphs consistently demonstrate the superiority of our proposed methods, achieving up to two orders of magnitude improvement in time efficiency over the baseline algorithms while producing high-quality solutions.

Subgraph matching is a fundamental problem in graph analysis. In recent years, many subgraph matching algorithms have been proposed, making it pressing and challenging to compare their performance and identify their strengths and weaknesses. We observe that (1) The embedding enumeration in the classic filtering-ordering-enumerating framework dominates the overall performance, and thus enhancing the backtracking paradigm is becoming a current research trend; (2) Simply changing the limitation of output size results in a substantial variation in the ranking of different methods, leading to biased performance evaluation; (3) The techniques employed at different stages of subgraph matching interact with each other, making it less feasible to replace and evaluate a single technique in isolation. Therefore, a comprehensive survey and experimental study of subgraph matching is necessary to identify the current trends, ensure unbiasedness, and investigate the potential interactions. In this paper, we comprehensively review the methods in the current trend and experimentally confirm their advantage over prior approaches. We unbiasedly evaluate the performance of these algorithms by using an effective metric, namely embeddings per second. To fully investigate the interactions between various techniques, we select 10 representative techniques for each stage and evaluate all the feasible combinations.

Streaming graphs are drawing increasing attention in both academic and industrial communities as many graphs in real applications evolve over time. Continuous subgraph matching (shorted as CSM) aims to report the incremental matches of a query graph in such streaming graphs. It involves two major steps, i.e., candidate maintenance and incremental match generation, to answer CSM. Throughout the course of continuous subgraph matching, incremental match generation backtracking over the search space dominates the total cost. However, most previous approaches focus on developing techniques for efficient candidate maintenance, while incremental match generation receives less attention despite its importance in CSM. Aiming to minimize the overall cost, we propose two techniques to reduce backtrackings in this paper. We present a cost-effective index CaLiG that yields tighter candidate maintenance, shrinking the search space of backtracking. In addition, we develop a novel incremental matching paradigm KSS that decomposes the query vertices into conditional kernel vertices and shell vertices. With the matches of kernel vertices, the incremental matches can be produced immediately by joining the candidates of shell vertices without any backtrackings. Benefiting from reduced backtrackings, the elapsed time of CSM decreases significantly. Extensive experiments over real graphs show that our method runs faster than the state-of-the-art algorithm orders of magnitude.

With the rapid growth of graph scale, challenges emerge for subgraph search when the data graph cannot reside in the memory of a single machine. It is important to develop practical algorithms to answer subgraph queries in distributed systems and has attracted extensive attention in recent years. The existing join-based algorithms are natively supported in many distributed engines, but they often suffer from a large number of invalid intermediate results and duplicate computation. The exploration-based algorithms minimize invalid intermediate results, while they are likely to produce results of exponential size. In this paper, we propose an efficient hybrid subgraph matching framework that integrates the advantages of both join-based and exploration-based paradigms. We formulate a novel decomposition for the query graph, namely sketch tree, which can reduce invalid intermediate results and avoid duplicate computation. We implement the proposed algorithm in the Pregel + system and optimize the communication cost powered by the sketch tree. Extensive experiments on real graphs demonstrate that our proposed algorithm significantly outperforms the state-of-the-art join-based and exploration-based methods.