Combining the convex and relaxations, and following the solution path of convex-concave problem, the path following algorithm exhibits an excellent accuracy on graph matching approximately. In this paper, the path following algorithm is employed to address the problem of ear matching. Firstly, the PCA method is used to construct the set of salient keypoints of 3D ear point cloud data. Then the neighborhood of each keypoint is fitted to a single-valued quadric surface on a tensor-product parameter domain to define the local shape feature on the surface as the similarity measures. Next, the keypoints are triangulated into 3D topological graph using Delaunay triangulation, and the global structure discrepancy on the graph is obtained. Finally, the overall similarity measure is marked as the linear interpolation combination of the graph structure discrepancy and the local shape feature discrepancy, and the path following algorithm is then used to address the optimal matching between two keypoint graphs. The experiments show that the presented method provides a better matching result in terms of efficiency and accuracy than other similar approaches.