Hierarchical Spectral Analysis Isomorphism Testing Algorithm for Undirected Graph

In this paper, a hierarchical isomorphism testing algorithm based on spectral analysis is proposed for undirected graphs. The proposed algorithm firstly checks the vertices number, edge number and degree sequence of the two graphs. Afterwards, a hierarchical spectral algorithm is employed to further test the isomorphism of the graphs. The proposed algorithm can achieve higher efficiency for graphs of regular grid or fixed degrees compared with the state-of-the-art Nauty algorithm.