SymmPi: Exploiting Symmetry Removal for Fast Subgraph Matching

Symmetry, a phenomenon of self-similarity, is common in many networks, which often incurs a lot of redundant accesses and computations, even duplicate results when executing graph matching tasks. Many approaches (e.g. symmetry-breaking methods) try to disrupt symmetry by translating symmetry into restrictions and then imposing restrictions on the exploration order. However, the restrictions are finer-grained. If the pattern graph is complex, more restrictions are generated from symmetry breaking methods, thus complicating the exploration process and degrading the performance. Here, we present novel SymmPi, which exploits symmetry removal for fast graph matching. SymmPi first identifies the coarse-grained axisymmetric subgraphs of the given pattern graphs instead of finer relationships. If a pattern graph is not axisymmetric, SymmPi will remove some of its edges until axisymmetric subgraphs are found. Thus, the original pattern graph is transformed to a set of axisymmetric subgraphs plus some edges. Then, SymmPi finds the matches of the axisymmetric subgraph and extends these matches to the original pattern graphs by permuting the matches with additional checks. Our experiments on both directed and undirected graphs, demonstrate that SymmPi achieves a significant performance improvement over the state-of-the-art undirected and directed graph matching methods and systems.