We propose the adoption of a vector extrapolation technique to accelerate convergence of correspondence problems under the quadratic assignment formulation for attributed graph matching (QAP). In order to capture a broad range of matching scenarios, we provide a class of relaxations of the QAP under elastic net constraints. This allows us to regulate the sparsity/complexity trade-off which is inherent to most instances of the matching problem, thus enabling us to study the application of the acceleration method over a family of problems of varying difficulty. The validity of the approach is assessed by considering three different matching scenarios; namely, rigid and non-rigid three-dimensional shape matching, and image matching for Structure from Motion. As demonstrated on both real and synthetic data, our approach leads to an increase in performance of up to one order of magnitude when compared to the standard methods.