Research map / Learning theory and algorithms / Combinatorial and search optimization
FRAM: Frobenius-Regularized Assignment Matching with Mixed-Precision Computing
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 FRAM, a graph matching method that replaces the doubly stochastic projection in projected fixed-point iterations with a Frobenius-regularized linear assignment (FRA) solved by a scaling doubly stochastic normalization (SDSN), plus a GPU mixed-precision (TF32/FP32/FP64) implementation giving large speedups.
Problem
Graph matching, cast as a QAP, is NP-hard; projection-based convex relaxations enlarge the feasible set, causing sensitivity to numerical scale and geometric misalignment between relaxed and original domains, and the approach is computationally expensive at large scale.
Approach
Reformulate the doubly stochastic projection as a Frobenius-regularized linear assignment with a tunable parameter theta that controls relaxation bias and enables scale invariance via normalization; solve it with an SDSN iteration whose truncation residuals vanish, enabling a theoretically motivated mixed-precision GPU pipeline.
Key results
- On real-world picture sets (1000 nodes, FP64), FRAM averages 2.3s vs 6.5s for DSPFP (2.8x speedup) and achieves lower matching error than DSPFP in most sets.
- On Facebook network with 5% noise, FRAM reaches 94.7% accuracy vs 91.1% for ASM (second best), at about 2x ASM's speed.
- With GPU mixed precision on ubc(2000), FRAM achieves 371.4x speedup over CPU-FP64 and 12.7x over GPU-FP64.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FRAM instead of DSPFP for attributed matching | FRAM · Real-world pictures: bark, boat, graf, wall, ubc | matching error (× 10^4): 5.0 -> 4.2; 4.4 -> 4.0; 4.9 -> 4.6; 4.1 -> 3.6; 4.0 -> 3.1 | Helped |
| Use FRAM instead of ASM for attributed matching | FRAM · Real-world pictures: leuv, tree, bikes | matching error (× 10^4): 3.7 -> 4.9; 3.5 -> 3.8; 3.6 -> 4.4 | Hurt |
| Use FRAM instead of DSPFP for house-sequence matching | FRAM · CMU House | running time: 3.83s -> 0.93s | Helped |
| Use FRAM instead of ASM for house-sequence matching | FRAM · CMU House | matching error: 7341 -> 7047 | Helped |
| Use FRAM instead of ASM on noisy Facebook networks | FRAM · Facebook-ego, 5%, 15%, and 25% noise | accuracy: 91.1% -> 94.7%; 88.4% -> 91.1%; 85.7% -> 89.5% | Helped |
| Use mixed-precision GPU computation instead of GPU-FP64 | FRAM · ubc(2000) | speedup: 12.7× | Helped |
| Use mixed-precision GPU computation instead of CPU-FP64 | FRAM · ubc(2000) | speedup: 371.4× | Helped |
Surprising findings
- Excessively large theta can slightly degrade final matching performance because assignments become over-confident too early.
- Mixed-precision speedups are below 4x for tasks with at most 1000 nodes, attributed to Amdahl's law overheads.
Limitations
- The regularization parameter theta is chosen empirically (theta=2 dense, theta=10 sparse), without an adaptive selection strategy.
- Mixed-precision speedup is small for graphs of 1000 nodes or fewer due to fixed overheads.
- Many state-of-the-art QAP solvers were excluded because they do not scale beyond about 1000 nodes.
Experimental setup
Datasets: Real-world pictures (affine covariant regions dataset, 8 image sets) CMU House Sequence Facebook ego social circles
Benchmarks: Real-world pictures (bark, boat, graf, wall, leuv, tree, ubc, bikes) CMU House Sequence Facebook ego network with noise
Metrics: running time matching error node matching accuracy
Baselines: DSPFP AIPFP GA ASM GWL S-GWL GRASP
Builds on: DSPFP doubly stochastic normalization (DSN) graduated assignment integer projected fixed point (IPFP) Hungarian method
Closest papers by meaning
- KerGM: Kernelized Graph Matching (NeurIPS 2019 · similarity 0.89)
- Generalizing Graph Matching beyond Quadratic Assignment Model (NeurIPS 2018 · similarity 0.88)
- A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching (CVPR 2017 · similarity 0.88)
- Graph Alignment via Birkhoff Relaxation (NeurIPS 2025 · similarity 0.87)
- Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS (ICML 2024 · similarity 0.85)
- Learning Partial Graph Matching via Optimal Partial Transport (ICLR 2025 · similarity 0.84)
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.