Abstract: Spectral correspondence finding is an important method for point pattern matching. But it’s sensitive to noise and outliers. In order to overcome the traditional spectral correspondence finding method’s problem, a new algorithm is proposed for non-rigid point pattern matching by using spectral graph analysis combining with relaxation labeling. The algorithm first compute the matching probability by KL features of the points, then use the relaxation labeling method to get the correspondences between the point sets. At the same time, an objective function on matching is defined for the relaxation labeling method, and the algorithm find the optimal solution for matching under the iterative optimal frame. There are three improvements made to the traditional spectral correspondence finding method in this paper. First, KL correspondence probability method is used to improve the algorithm’s ability for standing the noises. Secondly, the spectral method is embedded in the relaxation labeling framework to get the method more robust while outliers appear. Thirdly, two kinds of information are utilized for correspondence finding, namely spectral information, and space distribution information, . These makes the algorithm be able to handle with large deformation.