The intrinsic information of a graph can be fully encoded into its spectrum and corresponding eigenvectors of its adjacency matrix, which provides a solid foundation for the success of spectral graph matching methods. The spectral multiplicity, however, may significantly affect the matching accuracy. In this paper, we propose a spectral-multiplicity-tolerant graph matching approach. We start from modeling the spectral multiplicity in the matching error measurement. Next, we address the equal-size graph matching problem, and show how to establish the vertex-to-vertex correspondence by alternatively optimizing the multiplicity matrix C and the permutation matrix P. We also propose a reliable initialization method to make the iterative optimization process converge rapidly. Then, we extend the algorithm to unequal-size graph matching by optimally warping two graphs into the same size. A comprehensive performance evaluation has been conducted on a large synthetic dataset. We also demonstrate the effectiveness of our approach on shape retrieval. The experimental results show that compared with existing methods, the proposed approach is more robust to noise and structural corruption and has a comparable complexity. © 2013 Elsevier Ltd. All rights reserved.