Graph Iso/Auto-morphism: A Divide-&-Conquer Approach

The graph isomorphism is to determine whether two graphs are isomorphic. A closely related problem is graph automorphism (symmetry) detection, where an isomorphism between two graphs is a bijection between their vertex sets that preserves adjacency, and an automorphism is an isomorphism from a graph to itself. Applications of graph isomorphism and automorphism detection include database indexing, network model, network measurement, network simplification, and social network anonymization. By graph automorphism, we deal with symmetric subgraph matching (SSM), which is to find all subgraphs in a graph G that are symmetric to a given subgraph in G. An application of SSM is to identify multiple seed sets that have the same influence power as a set of seeds found by influence maximization in a social network. To test two graphs for isomorphism, canonical labeling has been studied to relabel a graph in such a way that isomorphic graphs are identical after relabeling. Efficient canonical labeling algorithms have been designed by individualization-refinement. They enumerate all permutations of vertices using a search tree, and select the minimum permutation as the canonical labeling. The candidates are pruned by the minimum permutation during enumeration. Despite their high performance in benchmark graphs, these algorithms face difficulties in handling massive graphs, and the search trees used are for pruning purposes which cannot answer symmetric subgraphs matching.

In this paper, we design a new efficient canonical labeling algorithm DviCL. DviCL designed is based on the observation that we can use the k-th minimum permutation as the canonical labeling. Different from previous algorithms, we take a divide-and-conquer approach to partition a graph G. By partitioning G, an AutoTree is constructed, which preserves symmetric structures as well as the automorphism group of G. The canonical labeling for a tree node can be obtained by the canonical labeling of its child nodes. and the canonical labeling for the root is the one for G. Such AutoTree can also be effectively used to answer the automorphism group, symmetric subgraphs. We conducted extensive performance studies using 22 large graphs, and confirmed that DviCL is much more efficient and robust than the state-of-the-art.