A CUR Decomposition-Based Mix-Order Framework for Large-Scale Hypergraph Matching

Compatibilities between the hyperedges of two hypergraphs can be represented as a sparse tensor to avoid exponentially increasing computational costs in hypergraph matching. Kd-tree-based approximate nearest neighbor (ANN) methods have been widely adopted to obtain the sparse compatibility tensor and usually need a relatively high density to guarantee greater accuracy without prior knowledge of the correspondences between a pair of feature point sets. For large scale problems, they require exhaustive computations. This work introduces a novel cascaded second and third-order framework for efficient hypergraph matching. Its core is a CUR decomposition-based sparse compatibility tensor generation method. A rough node assignment is calculated first by a CUR-based pairwise matching process that has a lower computational cost in the second order. Using that intermediate assignment as prior knowledge, a compatibility tensor with higher sparsity can be calculated, with a significantly decreased memory footprint by a novel probability relaxation labeling (PRL)-based hypergraph matching algorithm. The term "reliability" was used to describe how the tensor affects the matching performance and a new measurement, the reliability rate, was proposed to quantify the reliability of a sparse compatibility tensor. Experiment results on large-scale synthetic datasets, and widely adopted benchmarks, demonstrated that the proposed framework outperformed existing methods, creating a more than ten times sparser, but more reliable, compatibility tensor. This proposed CUR-based tensor generation method can be integrated into existing hypergraph matching algorithms and will significantly increase their performance with lower computational costs.