ASM: Adaptive Subgraph Matching via Efficient Compression and Label Filter
摘要
How to efficiently get subgraphs that match the given query graph on large-scale graphs has become a hot topic in both academia and industry. Subgraph matching, as an important research direction of graph algorithms, realizes the basic operation for efficient queries on graph data, and its essence is the subgraph isomorphism problem, which is proved to be an np-complete problem. The filtering phase in the process of subgraph matching is especially critical because it directly affects the efficiency of the overall algorithm. An excellent filtering mechanism can screen out the eligible candidate nodes in a shorter time, thus saving a lot of computing time for the whole process. By analyzing the existing methods for handling the subgraph matching problem, we find that the following problems mainly exist in the existing methods in the filtering stage: (1) the problem of repeated enumeration of equivalent nodes; (2) Incomplete filtering problems with existing structures. These will lead to a large number of redundant validation issues during the validation phase. Then (3) we propose an Adaptive Subgraph Matching (ASM) mechanism to address the aforementioned shortcomings by efficient Compressed Graph Nodes (CGN) and a Label Count Filter (LCF) algorithm to improve the performance. The experiments show that our approach outperforms state-of-the-art subgraph search and matching algorithms by several orders of magnitude in terms of query processing time.