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.

To achieve greater accuracy, hypergraph matching algorithms require exponential increases in computational resources. Recent kd-tree-based approximate nearest neighbor (ANN) methods, despite the sparsity of their compatibility tensor, still require exhaustive calculations for large-scale graph matching. This work utilizes CUR tensor decomposition and introduces a novel cascaded second and third-order hypergraph matching framework (CURSOR) for efficient hypergraph matching. A CUR-based second-order graph matching algorithm is used to provide a rough match, and then the core of CURSOR, a fiber-CUR-based tensor generation method, directly calculates entries of the compatibility tensor by leveraging the initial second-order match result. This significantly decreases the time complexity and tensor density. A probability relaxation labeling (PRL)-based matching algorithm, specifically suitable for sparse tensors, is developed. Experiment results on large-scale synthetic datasets and widely-adopted benchmark sets demonstrate the superiority of CURSOR over existing methods. The tensor generation method in CURSOR can be integrated seamlessly into existing hypergraph matching methods to improve their performance and lower their computational costs.