  The graph isomorphism is to determine whether two graphs are isomorphic. A
closely related problem is automorphism 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/automorphism include database indexing, network
simplification, network anonymization. By graph automorphism, we deal with
symmetric subgraph matching (SSM), which is to find all subgraphs 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 seed set 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 using a search tree, and select the minimum as the canonical
labeling, which prunes candidates during enumeration. Despite high performance
in benchmark graphs, these algorithms face difficulties in handling massive
graphs. In this paper, we design a new efficient canonical labeling algorithm
DviCL. Different from previous algorithms, we take a divide-&-conquer approach
to partition G. By partitioning G, an AutoTree is constructed, which preserves
symmetric structures and 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.
