# FRAM: Frobenius-Regularized Assignment Matching with Mixed-Precision Computing

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 46 references that are in the map.
- First posted on arXiv 26 Jul 2025.

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

- [Mixed Precision Training](https://mlsanity.com/paper/1710.03740/) (2017)
- [Gromov-Wasserstein Learning for Graph Matching and Node Embedding](https://mlsanity.com/paper/1901.06003/) (2019)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [Robust Point Cloud Registration Framework Based on Deep Graph Matching](https://mlsanity.com/paper/2103.04256/) (2021)
- [Cross-lingual Knowledge Graph Alignment via Graph Matching Neural Network](https://mlsanity.com/paper/1905.11605/) (2019)
- [Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking](https://mlsanity.com/paper/2103.16178/) (2021)
- [GraphAlign: Enhancing Accurate Feature Alignment by Graph matching for Multi-Modal 3D Object Detection](https://mlsanity.com/paper/2310.08261/) (2023)
- [DS*: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problems](https://mlsanity.com/paper/1711.10733/) (2017)
- [More Interpretable Graph Similarity Computation via Maximum Common Subgraph Inference](https://mlsanity.com/paper/2208.04580/) (2022)
- [Fabricated Pictures Detection with Graph Matching](https://mlsanity.com/paper/2002.03720/) (2020)
- [Adaptive Softassign via Hadamard-Equipped Sinkhorn](https://mlsanity.com/paper/2309.13855/) (2023)

## Abstract (arXiv)

Graph matching, typically formulated as a Quadratic Assignment Problem (QAP), seeks to establish node correspondences between two graphs. To address the NP-hardness of QAP, some existing methods adopt projection-based relaxations that embed the problem into the convex hull of the discrete domain. However, these relaxations inevitably enlarge the feasible set, introducing two sources of error: numerical scale sensitivity and geometric misalignment between the relaxed and original domains. To alleviate these errors, we propose a novel relaxation framework by reformulating the projection step as a Frobenius-regularized Linear Assignment (FRA) problem, where a tunable regularization term mitigates feasible region inflation. This formulation enables normalization-based operations to preserve numerical scale invariance without compromising accuracy. To efficiently solve FRA, we propose the Scaling Doubly Stochastic Normalization (SDSN) algorithm. Building on its favorable computational properties, we develop a theoretically grounded mixed-precision architecture to achieve substantial acceleration. Comprehensive CPU-based benchmarks demonstrate that FRAM consistently outperforms all baseline methods under identical precision settings. When combined with a GPU-based mixed-precision architecture, FRAM achieves up to 370X speedup over its CPU-FP64 counterpart, with negligible loss in solution accuracy.