Research map / Learning theory and algorithms / Matrix and tensor methods
CURSOR: Scalable Mixed-Order Hypergraph Matching with CUR Decomposition
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes CURSOR, a cascaded second- and third-order hypergraph matching framework using CUR decomposition to build sparse compatibility tensors from a rough second-order match, plus a PRL-based matcher for sparse tensors.
Problem
Hypergraph matching is computationally and memory-intensive at large scale; ANN-based compatibility tensor construction still requires exhaustive per-block computation and accuracy demands denser tensors.
Approach
Use a CUR-approximated second-order matching to get a rough correspondence, then compute only the tensor fibers indicated by that match (fiber-CUR tensor generation) so the third-order compatibility tensor is far sparser and cheaper, paired with a probability relaxation labeling solver suited to sparse tensors.
Key results
- CURSOR solves 1000-vs-1000 synthetic matching with accuracy around 0.97-0.99 at 5.03GB memory, while ADGM with ANN fails beyond n1=100 under the same memory limit.
- On Car and Motorbike datasets, CURSOR-integrated methods use compatibility tensors more than ten times sparser than ANN-based methods and improve accuracy; CURSOR with PRL achieves the highest accuracy.
- On CMU House 30-vs-30, CURSOR achieves the best accuracy among compared methods, though BCAGM3 with CURSOR degrades when the tensor is too sparse.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CURSOR instead of ANN-based ADGM | ADGM · Synthetic (n1=50, n2=100) | accuracy: 0.974 -> 0.982 | Helped |
| Use CURSOR instead of ANN-based ADGM | ADGM · Synthetic (n1=30, n2=30) | accuracy: 1 -> 1 | No clear effect |
| Use CURSOR instead of ANN-based ADGM | ADGM · Synthetic (n1=30, n2=50) | accuracy: 1 -> 1 | No clear effect |
| Use CURSOR instead of ANN-based ADGM | ADGM · Synthetic (n1=50, n2=50) | accuracy: 1 -> 1 | No clear effect |
| Use CURSOR instead of ANN-based ADGM | ADGM · Synthetic (n1=100, n2=100) | accuracy: 1 -> 1 | No clear effect |
| Replace ANN tensor generation with CURSOR tensor generation | RRWHM, ADGM, BCAGM3, and TM · Cars and Motorbikes | accuracy | Helped |
| Replace ANN tensor generation with CURSOR tensor generation | RRWHM, ADGM, and BCAGM3 · House and Hotel | accuracy | Mixed |
| Replace ANN tensor generation with CURSOR tensor generation | RRWHM, ADGM, BCAGM3, and ADGM · Shape templates with rotation, scaling, noise, and outliers | accuracy | Helped |
Surprising findings
- BCAGM3 combined with CURSOR often made descent errors and its accuracy dropped sharply when the compatibility tensor became too sparse.
Limitations
- Accuracy of the second-order CUR stage is lower with few sampled rows and columns, relying on the subsequent third-order stage for refinement.
- BCAGM3 integrated with CURSOR degrades when the compatibility tensor is too sparse.
- Parameters (c, k, r, alpha) are set manually without an adaptive scheme.
Experimental setup
Datasets: synthetic 2D Gaussian point sets 2D template shapes (whale, Chinese character, UCF fish, tropical fish) CMU House and Hotel Car and Motorbike (Caltech-style pairs)
Benchmarks: large-scale random synthetic dataset 2D templates with rotation/scaling/noise/outliers CMU House and Hotel Car and Motorbikes
Metrics: matching accuracy non-zero count of compatibility tensor memory footprint
Baselines: TM RRWHM BCAGM3 ADGM HNN-HM
Builds on: Tensor Matching (TM) CUR+ randomized fiber CUR decomposition probabilistic relaxation labeling spectral matching
Closest papers by meaning
- FRAM: Frobenius-Regularized Assignment Matching with Mixed-Precision Computing (NeurIPS 2025 · similarity 0.83)
- Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS (ICML 2024 · similarity 0.83)
- Position: Graph Matching Systems Deserve Better Benchmarks (ICML 2025 · similarity 0.83)
- Towards Unsupervised Training of Matching-based Graph Edit Distance Solver via Preference-aware GAN (NeurIPS 2025 · similarity 0.82)
- Learning Partial Graph Matching via Optimal Partial Transport (ICLR 2025 · similarity 0.82)
- CSPG: Crossing Sparse Proximity Graphs for Approximate Nearest Neighbor Search (NeurIPS 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.