Abstract: Traditional learning graph matching usually performs unstably in case of deformation and noise. For these problems, this paper presents a supervised learning graph matching method combined with graduated non-convexity and concavity procedure（i.e. GNCCP）. The method first solves a set of quadratic assignment problems by GNCCP to get the convex upper bound of the training problem, which is subsequently optimized by the bundle method; after that, we use GNCCP again for the trained graph matching model to get the final matching. On CMU House/Hotel data sets and three synthetic data sets with rotation, shear and noise, experimental results show that the method can significantly improve the matching accuracies and even up to 100% for some data sets. In addition, with a shape context pairwise feature descriptor the proposed method can perform competitively on the WILLOW data set.