Efficient Graph Matching with Pattern Reduction

The prevalence of similar sub-structures in graphs and the inherent characteristics of graph matching tasks incur a large amount of redundant data accesses and computations. Many existing graph matching approaches to date first identify some sub-structures (e.g., symmetric structure, dense subgraphs) of the pattern graphs, which then serve as the basis to reduce or postpone Cartesian products in graph matching tasks. However, the methods based on the structures may not work efficiently when such structures are fewer or absent in pattern graphs. This paper presents PMiner - an efficient pattern-reduction approach to both undirected and directed graph matching problem with three original contributions. First, we exploit the inclusion relationships between the matching sets of edges and vertices in the pattern graph and convert the redundancy reduction in subgraph matching into a pattern reduction problem. Second, we reduce the original pattern graph to a more compact pattern graph by finding a minimum edge constraint cover over the pattern graph with the goal of reducing redundant data accesses and redundant computations. Finally, PMiner generates an efficient execution plan for the subgraph matching problem, consisting of an exploration plan and a materialization plan. When executing this plan, PMiner employs a bi-directional breadth-first search with mini-frontiers and reuses partial matches, ensuring low memory usage. By transforming a graph matching problem into a pattern reduction problem, PMiner can address both undirected and directed graph matching problems in a uniform manner while it effectively minimizes redundant operations for both data access and graph exploration throughout the graph matching process. Extensive experiments show that PMiner outperforms the representative standalone directed and undirected graph matching methods or systems and can scale to complex graph pattern matching tasks on large graphs.