Fast and scalable approximate spectral graph matching for correspondence problems

Establishing consistent correspondences between two sets of features is a fundamental problem in computer vision. This problem can be well formulated as graph matching in which nodes and edges represent feature points and pairwise relationships between feature points, respectively. Spectral matching [19] is the state-of-the-art eigenvector-based method for graph matching. The spectral matching algorithm has been used successfully for small data, but its heavy memory requirement limited the maximum data sizes and contexts it can be used. In this paper, we propose FaSM, a fast and scalable approximate spectral matching algorithm. The main ideas are twofold. First, we exploit the redundancy in the data generation process to approximate the affinity matrix with the linear combination of Kronecker products between bases and index matrices. The bases and index matrices are highly compressed representation of the approximated affinity matrix, requiring much smaller memory than in previous works which store the whole affinity matrix. Second, we compute the eigenvector of the approximated affinity matrix using the small bases and index matrices without explicitly materializing the approximated matrix. Experimental results show that our proposed method is up to 33× faster, requiring up to 645× smaller memory than the exact algorithm, with little or no loss of accuracy.