# An Efficient Multilinear Optimization Framework for Hypergraph Matching

arXiv: https://arxiv.org/abs/1511.02667 · HTML: https://mlsanity.com/paper/1511.02667/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2015.

## Built on by (most cited first, 3 of 3)

- [An Exact Hypergraph Matching Algorithm for Nuclear Identification in Embryonic Caenorhabditis elegans](https://mlsanity.com/paper/2104.10003/) (2021)
- [Statistical Limits for Testing Correlation of Hypergraphs](https://mlsanity.com/paper/2202.05888/) (2022)
- [A flexible PageRank-based graph embedding framework closely related to spectral eigenvector embeddings](https://mlsanity.com/paper/2207.11321/) (2022)

## Abstract (arXiv)

Hypergraph matching has recently become a popular approach for solving correspondence problems in computer vision as it allows to integrate higher-order geometric information. Hypergraph matching can be formulated as a third-order optimization problem subject to the assignment constraints which turns out to be NP-hard. In recent work, we have proposed an algorithm for hypergraph matching which first lifts the third-order problem to a fourth-order problem and then solves the fourth-order problem via optimization of the corresponding multilinear form. This leads to a tensor block coordinate ascent scheme which has the guarantee of providing monotonic ascent in the original matching score function and leads to state-of-the-art performance both in terms of achieved matching score and accuracy. In this paper we show that the lifting step to a fourth-order problem can be avoided yielding a third-order scheme with the same guarantees and performance but being two times faster. Moreover, we introduce a homotopy type method which further improves the performance.