Seeking affinity structure: Strategies for improving m-best graph matching

Abstract

State-of-the-art methods for finding the m-best solutions to graph matching (QAP) rely on exclusion strategies. The k-th best solution is found by excluding all better ones from the search space. This provides diversity, a natural requirement for transforming a MAP problem into a m-best one. Since diversity enforces mode hopping, it is usually combined with a mode-approximation strategy such as marginalisation. However, these methods are generic insofar they do not incorporate the detailed structure of the problem at hand, i.e. the properties of the global affinity matrix which characterise the search space. Without this knowledge, it is thus hard to devise a practical criterion for choosing the next variable to clamp. In this paper, we propose several strategies to select the next variable to clamp, spanning the whole range between depth-first and breadth-first search, and we contribute with a unifying view for characterising the search space on the fly. Our strategies are: a) Number of factors in which the variables participate, b) centrality measures associated with the affinity matrix, and c) discrete pooling. Our experiments show that max number of factors and centrality provide a trade-off between efficiency and accuracy, whereas discrete pooling leads to an improvement of the state-of-the-art.