/Fast and Scalable Approximate Spectral Matching for Higher-Order Graph Matching

Fast and Scalable Approximate Spectral Matching for Higher-Order Graph Matching

Soonyong Park, Sung-kee Park and Martial Hebert
Journal Article, Carnegie Mellon University, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 36, No. 3, pp. 479-492, March, 2014

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.


This paper presents a fast and efficient computational approach to higher-order spectral graph matching. Exploiting the redundancy in a tensor representing the affinity between feature points, we approximate the affinity tensor with the linear combination of Kronecker products between bases and index tensors. The bases and index tensors are highly compressed representation of the approximated affinity tensor, requiring much smaller memory than in previous methods which store the full affinity tensor. We compute the principal eigenvector of the approximated affinity tensor using the small bases and index tensors without explicitly storing the approximated tensor. In order to compensate for the loss of matching accuracy by the approximation, we also adopt and incorporate a marginalization scheme that maps a higher-order tensor to matrix as well as a one-to-one mapping constraint into the eigenvector computation process. The experimental results show that the proposed method is faster and requiring smaller memory than the existing methods with little or no loss of accuracy.

BibTeX Reference
author = {Soonyong Park and Sung-kee Park and Martial Hebert},
title = {Fast and Scalable Approximate Spectral Matching for Higher-Order Graph Matching},
journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
year = {2014},
month = {March},
volume = {36},
number = {3},
pages = {479-492},
keywords = {Higher-order graph matching, spectral relaxation, approximation algorithm},