# CURSOR: Scalable Mixed-Order Hypergraph Matching with CUR Decomposition

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 38 references that are in the map.
- First posted on arXiv 26 Feb 2024.

## Builds on (most cited first, 13 of 13)

- [SuperGlue: Learning Feature Matching with Graph Neural Networks](https://mlsanity.com/paper/1911.11763/) (2019)
- [Learning Combinatorial Embedding Networks for Deep Graph Matching](https://mlsanity.com/paper/1904.00597/) (2019)
- [Learning to Match Features with Seeded Graph Matching Network](https://mlsanity.com/paper/2108.08771/) (2021)
- [SIGMA: Semantic-complete Graph Matching for Domain Adaptive Object Detection](https://mlsanity.com/paper/2203.06398/) (2022)
- [Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking](https://mlsanity.com/paper/2103.16178/) (2021)
- [Robust CUR Decomposition: Theory and Imaging Applications](https://mlsanity.com/paper/2101.05231/) (2021)
- [A Functional Representation for Graph Matching](https://mlsanity.com/paper/1901.05179/) (2019)
- [Mode-wise Tensor Decompositions: Multi-dimensional Generalizations of CUR Decompositions](https://mlsanity.com/paper/2103.11037/) (2021)
- [GM-MLIC: Graph Matching based Multi-Label Image Classification](https://mlsanity.com/paper/2104.14762/) (2021)
- [Alternating Direction Graph Matching](https://mlsanity.com/paper/1611.07583/) (2016)
- [CUR Algorithm for Partially Observed Matrices](https://mlsanity.com/paper/1411.0860/) (2014)
- [A Flexible Tensor Block Coordinate Ascent Scheme for Hypergraph Matching](https://mlsanity.com/paper/1504.07907/) (2015)
- [Kernelized multi-graph matching](https://mlsanity.com/paper/2210.05206/) (2022)

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

- [AGP: A Novel Arabidopsis thaliana Genomics-Phenomics Dataset and its HyperGraph Baseline Benchmarking](https://mlsanity.com/paper/2508.14934/) (2025)
- [GRAFT: Biological Graph and Hypergraph Benchmarks for Linked Gene Expression and Phenotypic Trait Prediction in Arabidopsis thaliana](https://mlsanity.com/paper/2606.27413/) (2026)
- [Unsupervised Multi-Scale Gromov-Wasserstein Hypergraph Alignment](https://mlsanity.com/paper/2608.29635/) (2026)

## Abstract (arXiv)

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, especially 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.