FRAM:  Frobenius-Regularized Assignment Matching with Mixed-Precision Computing
Authors: Binrui Shen
LiangYuan
Shengxin Zhu
Venue: NeurIPS 2025 poster ()
Keywords: graph matching
network alignment
quadratic assignment problem
linear assignment problem
Primary area: optimization
TL;DR: We present a graph matching algorithm that mitigates relaxation bias through a regularization term and achieves substantial acceleration via an innovative mixed-precision architecture.

Abstract: Graph matching, usually cast as a discrete Quadratic Assignment Problem (QAP), aims to identify correspondences between nodes in two graphs. Since QAP is NP-hard, many methods its discrete constraints by projecting the discrete feasible set onto its convex hull and solving the resulting continuous problem. However, these relaxations inevitably enlarge the feasible set and introduce two errors: sensitivity to numerical scales and geometric misalignment between the relaxed and original feasible domains. To address these issues, we propose a novel relaxation framework to reformulate the projection step as a Frobenius-Regularized Linear Assignment (FRA) problem. This formulation incorporates a tunable regularization term to curb the inflation of the feasible region and ensure numerical scale invariance. To solve the FRA efficiently, we introduce a scaling algorithm for doubly stochastic normalization. Leveraging its favorable computational properties, we design a theoretically grounded, accelerated mixed-precision algorithm. Building on these components, we propose Frobenius-Regularized Assignment Matching (FRAM), which approximates the QAP solution through a sequence of FRA problems. Extensive CPU experiments show that FRAM consistently outperforms all baselines. On GPUs, with mixed precision, FRAM achieves up to a 370× speedup over its FP64 CPU implementation without sacrificing accuracy.

FRAM: Frobenius-Regularzzed Assignment Matching with Mixed-Precision Computing
Binrui Shen Yuan Liang?, and Shengxin Zhu +4.5
School Mathematical Sciences, Laboratory Mathematics and Complex Systems, MOE, Beijing
Normal University, Beijing 100875, P.R. China
Faculty of Arts and Sciences, Beijing Normal University, Zhuhai 519087, P.R. China
School of Mathematical Sciences, Beijing Normal University, Beijing 100875, P.R. China
4 RReearcch Centers for Mathematics, Advanced Institute of Natural Science, Beijing Normal University, Zhuhai 519087, P.R. China
Guangdong Provincial Key Laboratory of Interdisciplinary Research and Application for Data Science, BNU-HKBU United International College, Zhuhai 519087. P.R. China binrui shen@bnu.....ee.. edu. cn, 1. y@mail. bnu. edu. cn, Shengxin. Zhu@bnu. edu cn
Abstract
Graph matching, usually cast as discrete Quadratic Assignment Problem (QAP), aims to identify correspondences between nodes in graphs. Since QAP is NP- hard, many methods its discrete constraints by projecting the discrete feasible set onto its convex hull and solving the resulting continuous problem. However, these relaxations inevitably enlarge the feasible set and introduce two errors: sensitivity numerical scales and geometric misalignment between the relaxed and original feasible domains. To address these issues, we propose a novel relaxation framework reformulate the projection step as a Frobenius- Reguuaaiu-- Linear Assignment (FRA) problem. This formulation incorporates a tunable regularization term to curb the inflation of the feasible region and ensure numerical scale invariance. To solve the FRA efficiently, we introduce scaling algorithm for doubly stochastic normalization. Leveraging its favorable computational properties, we design a theoretically grounded, accelerated mixed-precision algorithm. Building on these components, we propose Frobenius- Reegniiuiee Assignment Matching (FRAM), which approximates the QAP solution through a sequence of FRA problems. Ex- tensive CPU experiments show that FRAM consistently outperforms baselines. On GPUs, with mixed precision, FRAM achieves up 370x speedup over its FP64 CPU implementation without sacrificing accuracy.
Introduction
Graph matching aims find correspondences between graphs that share potential relationships. can
be used in various fields of intelligent information processing, e.g., image similarity detection
(3
graph similarity computation [19 20 knowledge graph alignment [4], autonomous driving 36
vision-language model alignment 30 point cloud registration [10], deep neural network fusion 25
multi-object tracking [14], and COVID-19 disease mechanism study [13. However, graph matching
is an NP-hard discrete optimization problem [32] and computationally prohibitive for large-scale
instances.
To scale up the graph matching problem, many relaxation methods were proposed 5
21
27
34
These methods relax the discrete problem continuous domain and then project the
CCommunication author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

continuous solution back to the original discrete domain. The doubly stochastic projection is typical representative and frequently used recently 43]. This projection maps the gradient matrix onto the convex hull of the original domain. However, such relaxations inevitably enlarge the feasible region and result in two sources of errors: (1) geometric misalignment between the relaxed and original domains, which undermines the quality of the recovered integer solution; and (2) the loss of numerical scale invariance due to the projections in the nonconvex setting. Such limitations motivate our current research.
Our contributions include
1. Theoretical results:
We extend the doubly stochastic projection to the FRA by introducing a tunable regularization parameter that controls relaxation-inde distortion. We provide a thorough analysis of how the regularization parameter affects performance, and address the numerical scale sensitivity through an integrated normalization mechanism.
2. Algorithm: we propose FRAM, a graph matching algorithm, that solves the QAP approxi- mately by iteratively solving sequence of FRA problems. Each FRA problem can be solved efficiently by our proposed Scaling Doubly Stochastic Normalization (SDSN). Empirical evaluations show that FRAM achieves superior performance compared to state-of-the-art baselines.
3. Computing acceleration: We develop a theoretically grounded muxxd-preeision implemen- tation of FRAM. Compared to CPU-based couble-precision computation, it achieves up to a 370x speedup on an NVIDIA RTX 4080 SUPER GPU across some benchmark problems, with at most 0.2% drop in accuracy. To the best of our knowledge, this is the first graph matching algorithm built upon a theoretically grounded mixed- peeeddppeiiiion design.
2
Related Works
Related graph matching algorithms. We categorize related graph matching algorithms into three representative classes. (1) Methods based on doubly stochastic optimization: these works employ continuous relaxations. Graduated Assignment (GA) [2] pioneers this approach via sequence of linear approximations. Adaptive softassign (34] improves GA by automatically tuning entropic parameter. IPFP [22) projects gradients onto permutations, while DSN [43 finds the nearest doubly
stochastic matrix. DSN is adopted by (27] for gradient projection. (2) Spectral-based methods:
these approaches leverage spectral properties. Typical methods 21 35 recover assignments from the leading eigenvector. The method in [5] adds affine constraints improve accuracy while maintaining speed. Recent research [16] connects eigenvectors to multiscale structural features. (3) Methods based on optimal transport: these techniques formulate graph matching as an optimal transport problem. GWL [39] measures graph distance via Gromov- Wasserstein discrepancy, while S-GWL 38 scalable variant, applies divide-and-conquer strategy enhance efficiency. For comprehensive survey, we refer readers to 8
Mixed-preeision computing is sophisticated technique for accelerating computationally intensive applications. has been successfully applied to solving linear systems 44] [5] and large-scale AI models such as DeepSeek-V. V3 (24] However, little attention has been paid to its in the graph matching context, partly due to a lack of theoretical understanding. The main challenges in mixed- formats, which increases the risk of overflow or underflow, and (2) rounding errors introduced by lower-precision operations, which may lead to error propagation (28). See [17] for more details on mixed-precision algorithms. This paper provides theoretical guarantees for mixed-precision graph matching algorithm, achieving both numerical stability and computational speedups.
precision computing stem from (1) the limited range of
3 Preliminaries
An undirected altributed gruph G EV, A, F) consists a finite set of nodes V (1,..., and finite set of edges E C V x V. The matrix A is a nonnegative symmetric edge-uttribute matrix whose element Ay specifies the attribute of the edge between nodes and j. The i-th row of the feature matrix F' represents the attribute vector of node i.

---

Matching matrix. Given two attributed graphs G = V.E, A, F and G V., we first assume that the two graphs have the same number of vertices, i... n. for simplicity. matching matrix M E R encodes the correspondence between nodes: M2; = 1 node in matches node i G, and M; 0 otherwise. Under the one-to-one constraint, matching matrix is a permutation matrix. The set of permutation matrices is denoted as II (M M1 1, M M, {0,1)"x"), where 1 represents vectors with all ones.
The graph matching problem is typically formulated as QAP that is NP-hard [1]. common strategy handle such discrete problems is relaxation. first finds solution on Dxxn == {N N1 1, 1,N 1, N 2 0) which is the convex hull of the original domain. The relaxed problem then formulated as
Continuous relaxation.
N arg max ((N), $(N) I (r(N"AAA)) +X kr( NED
Edges similarites
Nodes' similaritss
where is a parameter, = FēT, and tr(.) represents the trace operator. And then N is transformed back to the original discrete domain Iax by solving linear assignment problem:
M arg min ||P-N Pellaxa
The matrix M is the final solution. Although relaxation allows the use of continuous optimization, the problem T is non-convex and thus remains NP-hard [3]] Hence, existing algorithms typically aim to obtain high-quality approximate solutions within acceptable time. Further discussions on convex relaxations and their constructions can be found in 91
The projected fixed-point method. Many existing methods 5
adopt similar
iterative framework to efficiently approximate the objective in
N(++1) (1- + (1) ( P(V = P(ANO)
where is step-size parameter and P(-) is operator which maps the gradient matrix onto certain set. When the solution domain is relaxed to the convex hull of the original domain (i.e., the set of doubly stochastic matrices), a natural choice for P(.) is the doubly stochastic projection 27 43
finds the closest doubly stochastic matrix to the gradient matrix Vo(N()) in terms of the Frobenius norm:
PD(X) arg min DEDaXn
x|Ix.
The resulting algorithm is the Doubly Stochastic Projected Fixed-Point method (DSPFP) [2
4 Projection to Assignment
We first propose a regularized linear assignment formulation by examining the numerical sensitivity of the doubly stochastic projection, and then analyze how the regularization parameter affects performance.
4.1 Doubly stochastic projection to assignment
It can be observed that the solution to the quadratic assignment problem ( also maximizes (vV(N) where w positive scaling constant. This reflects the numerical scale-invariant property of the objective. However, the doubly stochastic projection PD(() fails to preserve this property:
PD(X) # PD(wX),
for E 178""
(5)
Since the objective function is non-convex, this sensitivity can cause the projection- based algorithm to converge to different points under different scalings.
To elaborate the sensitivity, consider:
Px(wX) = arg min
|| - wX = arg min
| - w w
(6)
DED,xn
DED,xm
3

---

By expanding the quadratic norm, we have
- w = (D, D) 2(D,, wx) + (wX,wxX, wx),
(7)
where (; represents the Frobenius inner product. Since ( wx independent of D, it does affect the optimization. Thus,
Pr(wX)= arg min (D, - 2w(D, DEDaxn
(8)
As result, the problem reduces to
1 (D,
PD(wX)= arg max DEDaXH
(D,X)
(9)
2w
(D, X) represents an assignment score.
By referring back the update formula 3 X corresponds to the gradient matrix V
PD(WV)(NO)) arg max (D, VD(N())) 1
(D,
(10)
DEDaxn
2w
arg max DEDnXn
(D A+ XK)
(D.D)
(11)
2w
1 (D.
arg max tr(DD AN
Ā) + Att(DD K)
(12)
DE
2w
Intuitively, higher assignment scores [1] lead larger objective values ( during the iterative process. As w increases, the projection process emphasizes optimizing the objective assignment score (T). Conversell. when w decreases, the significance of the objective assignment score diminishes. This finding characterizes how the scaling constant w affects the optimization process.
Motivated by the above observation, we propose converting the uncontrollable scaling constant w of the problem into a controllable modeling parameter 0, as follows. Specifically, we extend the doubly stochastic projection to Frobenius Trobenius-regularizze linear assignment problem by introducing a modeling parameter 0, leading to the following formulation.
Theorem 1. The solution the scaled doubly stochastic projection problem
D = arg min || - X
(13)
DEDuxn
is equivalent to the solution of a Frobenius-regularize linear assignment problem: I (X), (x(X) = (D, X) - D).
D% arg max
(14)
DEP,x.
Furthermore, the flexibility this formulation allows us normalize the input matrix X by dividing by max(X), thereby eliminating the influence of the scaling constant w. Consequently, the weighting of the assignment term during optimization is entirely controlled by
4.2 Convergence to optimal assignment
To investigate the properties of FRA, we analyze the limiting behavior of D& as 0 approaches infinity and O.
Theorem 2. Let X E RRX and F be the convex hull of the optimal permutation matrices for the linear assignment problem with X. As 0 co, the matrix D% converges to unique matrix D F. where D* is the unique solution minner 1 (D,
This theorem reveals key advantage of FRA: unlike standard linear assignment solvers 22 that return an optimal permutation and discard others, D& approximates a convex combination of all optimal permutations, preserving richer solution information.
Corollary If there is only one optimal permutation, then D& converges to the corresponding permutation matrix.
When D corresponds to the unique permutation matrix, our algorithm becomes equivalent to IPFP and the classical Frank-Wolfe algorithm [37]. In contrast, when multiple optimal per- mutations exist, our matching algorithm can capture richer set of high-quality matches than these two methods [22 37 However, if is chosen too small, the resulting matrix D may fail to reveal high-quality correspondences, as the following proposition demonstrates.
Proposition 1. As 0 0, the matrix D& converges the matrix 11"

---

4.3 Influence of the parameter
To analyze the impact of the parameter, we quantify the solution quality through a distance metric between D3 and DX for a given matrix X E R+ The total assignment score (D", .)) scales with the problem size. To enable scale-independent error analysis, we define normalized assignment enror to quantify the performance gap:
<x (1D2, (Dx,
(15)
This normalization effectively decouples the approximation error from the problem scale, providing stable metric assess the quality of D& across different numbers of nodes nodes-like how the Mean Squared Error (MSE) serves as reale-independent alternative to the Sum of Squared Errors. Proposition For a matrix E Rox" the following inequality holds:
S
(16)
This proposition establishes that the performance gap between D& and D& is bounded by 1/0. This theoretical bound guarantees the stability and accuracy of our approximation scheme, ensuring that the solution asymptotically approaches optimal performance as becomes sufficiently large.
Figure illustrates how the matrix D evolves as 0 varies. When is small, the matrix entries nearly uniform. As / increases, D& progressively approaches a permutation matrix that lies within the original feasible domain the QAP. This observation demonstrates that a larger 0 effectively suppresses the bias introduced by relaxation. By selecting an appropriate value of 0, the intermediate solution during the matching process remains confined to a relaxed region that stays close to the original feasible domain of graph matching problems.
= 0.1
(b) 0
(c) 0 10
Figure 1: Visualization of D& under different values of 0. The color of each cell represents the matrix entry, with darker shades indicating larger values.
When FRA serves as component within the graph matching framework increasing 0 generally improves the per-iteration matching score by enforcing sharper correspondences. However, an excessively large 9 may slightly degrade the final matching performance due to premature convergence. This phenomenon can be interpreted from a probabilistic perspective, where each entry in the doubly stochastic matrix D% represents the probability of potential correspondence. A large 0 may lead to overconfident assignments at early stages, thereby hindering the exploration of alternative matching possibilities.
Scaling Doubly Stochastic Normalization
This section introduces the Scaling Doubly Stochastic Normalization (SDSN) method to efficiently solve the FRA. The method further adapted to achieve low-precision acceleration, accompanied by theoretical guarantees.
5.1 Doubly stochastic normalization
Due to the equivalence between FRA and the scaling doubly stochastic projection, FRA admits solution via tailored modifications of standard projection algorithms. Zass and Shashua [43 solved
5

---

the doubly stochastic projection by alternately solving two subproblems: (i())= = arg
mii
| Y (2()) = arg min X 112 (17)
Y20
The von-Neumann successive projection lemma [29] states that to PD(X). The derived doubly stochastic normalization (DSN) 43
PIPP converges
for X EE IR4 works as follows.
x Pi (x(x-1)) x(k) =P3 (x(()
(18)
( 17 n² 1
X
11
P2(X) X [X]
P X
11
(19)
where 7 is the identity matrix. It alternately applies row and column normalization Pi and non-negativity enforcement P2 for the doubly stochastic property. Each iteration requires (n²²) operations. The DSN algorithm converges linearly, meaning that there exists constant 0 < <
x 1x0-1-X-
such that c= lim
XX-
k-000
5.2 Convergence criterion
An explicit convergence criterion is notably absent in DSN. Zass and Shashua 43
terminated the
iterations once the updated matrix became doubly stochastic. However, this approach is computation- ally expensive and thus inefficient for large-scale tasks. In contrast, Lu et al. (27) fixed the number of iterations to 30 to improve efficiency, but this heuristic did not guarantee that the output matrix remained doubly stochastic.
We propose criterion to quantify the deviation be- tween the current matrix and the ideal solution. To ensure dimension-invariiat analysis and computational efficiency, we define a dimensional scaled error as
XP
2110
P4
Ps
P
(x)())
(k) X
1. (20)
n
Opteral soluion
Normalization by n ensures that the metric remains com- parable across matrices of different sizes. A detailed derivation of the convergence condition is provided in Appendix B and the overall process is illustrated in Figure
Figure 2: Convergence process of SDSN.
5.3 Number of iterations
The SDSN is summarized in Algorithm 2
We analyze the influence of the parameter 9 on the number of SDSN iterations in the following theorem, which shows that the iteration count grows proportionally with the value of 0.
Proposition 3. For X R the SDSN algorithm requires
In
0(| + n)) In(c)
iterations to produce solution X* that satisfies ||x D& ll < ehere D is the exact solution and c E (0, 1) is the convergence rate constant of the DSN algorithm.
5.4 Robustness to rounding error
Our method leverages a unique property SDSN, where the effect of rounding errors diminishes over iterations. This enables theoretically guaranteed low-precision acceleration on modern GPUs. The preservation of accuracy is theoretically guaranteed, ensuring the stability and correctness the entire process.

---

Theorem 3. In the SDSN algorithm, the k-th iterate Xx can be split as X Xx + AX2, where AX represents the rounding error. Then, the projection operator satisfies
Pi(Xa) = P((x)) Pa(AXi),
where P3(AX) is the solution the following minimization problem:
Pa(AX) arg min ||A YIl s.t. =1= 0, Y
The subsequent transformations of the error term A be expressed
P2P3 ... P2P3(AXH),
which asymptotically converges to the zero matrix 0nxn-
This property of SDSN prevents the accumulation of rounding errors arising from both the gradient- matrix computation in ( and the subsequent SDSN operations that correspond to A.X, and (AX:)12 Therefore, this property enables efficient low-precision computation with negligible loss of accuracy.
6 Matching Algorithm
We propose the Frobenius-Regularizze Regularized Assignment Matching (FRAM) algorithm which approx- imates the QAP via a sequence of FRA problems. Each FRA is efficiently solved by the scalable SDSN solver. The overall procedure of FRAM summarized in Algorithm
Mixed-precision Design on GPU. The selection of numerical precision for each operation detailed in inline code annotations. Steps 2-3 perform matrix scaling enabling stable low-precision acceleration in steps and 6. This scaling adjustment is offset by the normalization in SDSN. The subsequent steps conducted in double precision to compensate for the accuracy degradation. Further implementation details are provided in Appendix
Complexity. For n, steps 2-3 require O(n²) operations. Step 5 requires ((1²) operations per iteration, regardless of whether fast or sparse matrix computations are used. Step 6 requires OlIn²) operations where / denotes the number of iterations in SDSN. Step 10 transforms the doubly stochastic matrix N back to a matching matrix M using the Hungarian method [18] which has worst-case complexity of ( In practice, the cost is significantly lower because N is sparse in most cases. In short, this algorithm has time complexity O(n² In?) per iteration and space complexity O(n²).
Algorithm Frobenius-Regularizz Assignment Matching (FRAM)
Algorithm Scaling Doubly Stochastic Nor- malization (SDSN)
Require: A, A. K, X, a. a,0,8
Require: Matrix X, 0, Tish I: ( _ X max(X)
1: Initial (0) Onxă
2: while (()) > Yeh do
2: ma K)
FP64
3: A A/Ve, Ā Å/Ve, k= K/Ve
FP64
3:
(A) = n²
X1
4: while g(1) deh do
4:
x(1) I x(() x (+))
11T
5:
(1) = (N((-1) Ā+NK
TF32
6:
D (D),(X 0)
FP32
5:
(k+11 = -((k) + x
11 (1)
7:
NOO (1 (1-((11) + (D)
FP64
6:
((++1) (8(++1) (k++1) 1)/2
8:
g(t) ||NT00 -( ||/||
FP64
7:
= -
9: end while
8:
end while
Discretize N' to obtain M
FP64
Output: Doubly stochastic matrix X
11: return Matching matrix M
htugss//gthhb.cco///miiiheeeeef

---

7 Experiments
We evaluate the proposed algorithm (FRAM) and additional contributions from the following perspectives:
Q1. What improvements does FRAM deliver over basclines attributed graph matching tasks?
Q2. How robust is FRAM on attribute-free graph matching tasks?
Q3. How does the mixed-precision design accelerate FRAM?
In addition, we discuss the regularization parameter in Appendix
Setting, For FRAM. we set = 2 for attributed graph matching tasks and 0 = 10 for unattributed tasks. Following (27], set the regularization parameter to À in our experiments, since the results are not sensitive to A. We configure a to 0.95 to align with the parameter settings used in DSPFP (77] All algorithmic comparison experiments are conducted in Python 3 workstation equipped with an Intel Core (2.80 GHz) processor. All numerical computations are performed in double precision (FP64) to ensure numerical stability. Typical algorithms such as ASM and GA involve exponential operations and are sensitive to floating-poin precision. For evaluating the mixed-precision design, we utilize hardware platform equipped with an Intel Core 19-14900 (3.20 GHz) CPU and an NVIDIA RTX 4080 SUPER GPU.
Dataset. We evaluate algorithm on three types of graph data: graphs with attributes on both edges and nodes, graphs with attributed edges only, and graphs without attributes. The dataset specifications summarized in Table L and the graph construction procedure from images is described in Appendix
Dataset
Attributed nodes
Attributed edges
Ground-tutth
Dense graphs
Real-world pictures
(700, 1000)
(244 650, 499 500)
CMU House
(600,800)
(179 319
Facehook ego
039
88 234
Table 1: Datasets.
[V] is the number of nodes and E is the number of edges. (.) represents a range.
Criteria. For attributed graph matching tasks, we evaluate the matching error of algorithms by
A MÄMT| + 1
(21)
r
This formulation is mathematically equivalent to the original objective function ( differing only by an additive constant and a scaling factor. These terms do not affect the optimization process, while the new formulation provides a more intuitive understanding of the problem. For graphs containing only edge attribute matrices, the metric reduces to the first term of (21). For attribute-free graph matching tasks, the metric defined Rs where n. denotes the number of correctly matched nodes.
Baselines include project fixed-point algorithms such as DSPFP 27 and AIPFP 22 27|; I; softassign-
based algorithms such GA [12 (based on (1) and ASM 44 optimal transport methods such as GWL. 339 and S-GWL [8]] : and a spectral-based algorithm, GRASP 16]. Among these, methods based optimal transport and GRASP designed for attribute-free graph matching tasks. Most baselines suffer from numerical overflow and accumulation of rounding error under low precision. Therefore, we omit their low-precision comparisons (see Appendix for details). Many state-of-the- art algorithms, including Path Following (42,, FGM 44), RRWM 21, PM [7]. BGM (5), and MPM B do not scale well large graphs (e.g., with more than 1000 nodes), and are thus not included in our scage graph matching comparisons.
7.1 Real-world pictures
In this experiment, the attributed graphs are constructed from public datase containing eight sets of pictures. The dataset covers five common transformations: viewpoint change, scale change. image blur, JPEG compression and illumination. The numerical results are presented in Table 2
htttp://www.robot ac. wwtg//eeeaarcc//ffineee
8

---

Arformano
Kunning Time
Performance
Masching EaTor Lx100)
Imige Set
bark
book
geal
wall
INc
uboe
bikes
Image Set
back
bost
gmal
wall
leuv
ubc
bikes
DSPFP
9.15
1.36
8.86
6.14
3.86
7.66
6.15
5.36
DSPTP
3.0
3.1
58
4.0
4.9
AIPEP
44.3s
44.86
26.3s
40.3s
16.36
AIPLY
4,6
30.8s
54.2a
ASM
FRAM
2.6
2.8
2,45
2,36
2.26
2.5
2.46
1.15
FRAM
4.2
4.6
31
Table 2: Performance comparison in terms of (a) running time and (b) matching error on different image sets. The number of nodes is set to 1000 (bike with 700 nodes). All algorithms evaluated using double precision (FP64).
As revolutionary version of DSPFP, FRAM achieves significant acceleration across all image sets. The average runtime of FRAM is 2.3s, compared to 6.5s for DSPFP, yielding an overall speedup of 2.8x. In addition acceleration, FRAM consistently outperforms DSPFP regarding matching accuracy, demonstrating the effectiveness of the algorithmic design. Overall, FRAM achieves the best matching performance more than half of the experiments while being nearly twice as fast as the second-fastest fastest method, ASM.
7.2 House sequence
CMU house sequence" is a classic benchmark dataset. consists a sequence images showing a toy house captured from different viewpoints. Figure demonsttetts that FRAM achieves the best performance in both speed and accuracy on the House sequence dataset. It runs 4.1x faster than DSPFP and 3.4x faster than ASM, while attaining the lowest matching error. These results clearly highlight FRAM's efficiency and effectiveness.
16:75a
9600
16
8.142
Running Time (s)
Matching Error
Running (seconda)
14
8000
Matching Error
10-
7,341
7500
5.85
7000
6000
DSPFP
AIPFP
FRAM
Figure 3: Comparisons between algorithms on graphs from the house sequence. All algorithms are
evaluated using double precision (FP64).
Social networks
The social network, comprising 'circles' (or 'friends lists") from Facebook [23), contains 4039 users (nodes) and 88234 relations (edges). We compare different methods in matching networks with noisy versions 5%, 15% and 25%. Table shows that FRAM achieves the highest node accuracy across all noise levels while maintaining computational efficiency. FRAM achieves 4% higher accuracy than ASM (the second-best method) while running twice as fast. Although FRAM slightly slower than DSPFP, it offers substantial 15% improvement in accuracy, demonstrating a favorable trade-off between precision and efficiency.

---

Social network
5% noise
15%
noise
25%
noise
Methods
Time
Time
Acc
Time
S-GWL
26.4%
1204.1s
18.3%
1268.2s
17.9%
1295.85
GWL
78.1%
3721.6s
68.4%
4271.38
60.8%
4453.9s
DSPEP
79.7%
151.3s
68.3%
154.2s
62.25
156.9s
GA
35.5%
793.2s
21.4%
761.7s
16.0%
832.68
GRASP
37.9%
63.6s
20.3%
67.46
15.7%
71.3s
ASM
91.1%
387.2s
88.4%
391.7s
85.7%
393.18
AIPFP
68.6%
2705.5s
55.1%
2552.7s
47.8%
2513.88
FRAM
94.7%
211.1s
91.1%
221.6s
89.5%
222.9s
Table 3: Results Facebook network matching, which are evaluated using double precision (FP64).
7.4 Mixed-precision acceleration
This subsection analyzes the acceleration performance of mixed-precision design in FRAM across varying tasks. As demonstrated in Figure _] the design shows markedly higher acceleration ratios for large-scale problems. Specifically, the ubc(2000) matching task, mixed-precision design achieves (a) 12.7x speedup over standard GPU-FP64 implementations, and (b) a 371. 1.1.4x acceleration compared CPU-FP64 baselines. Conversely, for tasks with up to 1000 nodes, the observed speed-ups are below 4x, likely because the problem scale is insufficient to fully utilize the hardware's computational capacity. These observations are consistent with Amdahl's law: fixed computational overheads dominate runtime at small scales, significantly reducing achievable performance improvements.
119603.3 3
230.2x
8690
4200.0
2167.5
8.1x
102-
159.4k
432.7
450.9
520.0
298.1
42.0%
42.1K
53.7
15.2
3.9x
24.7
1.5x
2.3x
Hessetta
hestmalkatao
Figure 4: Runtime comparison of FRAM across different precisions and processors. The y-axis shows runtime (log scale), and the r-axis indicates datasets and their sizes. Red boxed numbers show the speedup of GPU the speedup over CPU double precision.
over GPU double precision, and yellow boxed numbers show
8 Conclusion
In the context of graph matching, this study investigates the bias introduced by projection-bais based relaxations. To address this issue, we reformulate the projection step regularized linear assignment problem, providing principled way to control the relaxation error. Building on this formulation, propose robust algorithm that achieves competitive accuracy while providing substantial speed advantages over existing baselines, including a significant improvement over the second-best method. On the computational side, we propose a theoretically grounded mixed-preet -ixed-precision design. To the best of our knowledge, this is the first theoretically grounded mixed-precision design for graph matching. It achieves significant acceleration while maintaining numerical stability.
limitation of this study lies in the empirical selection of the parameter 6, so we plan to develop an adaptive parameter selection strategy in future work. While our framework validates the effectiveness of mixed-precision computation, its computational efficiency can be improved. Future work may explore low-level compilation techniques to further optimize the implementation and unlock additional speed gains.
10

---

Acknowledgements
This work was partially supported by the Natural Science Foundation of China (12271047), the National Key Technologies Research and Development Program (2055YFG0202100) and the BNBU research fund (UICR0400008-21: UICR04202405-21), Thanks the support by the Inter- disciplinary Intelligence Super Computer Center of Beijing Normal University at Zhuhai and the Guangdong Provincial Key Laboratory of Interdisciplinary Research and Application for Data Science 0022B1212010000
References
[1] Florian Bernard, Christian Theobalt, and Michael Moeller, DS*: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problems, In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pages 4310-4319, 2018.
[2] Minsu Cho, Jungmin Lee, and Kyoung Mu Lee. Reweighted Random Walks for Graph Matching. In European Conference on Computer Vision, 2010.
[3] Minsu Cho, Jian Sun, Olivier Duchenne, and Jean Ponce. Finding matches in a haystack: A max- max-pooling strategy for graph matching in the presence of outliers. Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pages 2083-2090, 2014.
[4] Michael P Connolly, Nicholas Higham, and Theo Mary. Stochastic rounding and its proba- bilistic backward error analysis. SIAM Journal on Scientific Computing, A385, 2021.
[5] Timothee Cour, Praveen Srinivasan, and Jianbo Shi. Balanced Graph Matching. Advances in Neural Information Processing Systems, 19, 2006.
[6] Nadav Dym, Haggai Maron, and Yaron Lipman. DS++: A Flexible, Scalable and Provably Tight Relaxation for Matching Problems. ACM Transactions on Graphics, 36(6))1-14 2017.
[7] Amir Egozi, Yosi Keller, and Hugo Guterman. A probabilistic approach spectral graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(1):18- 2012.
[8] Frank Emmert-Streib, Matthias Dehmer, and Yongtang Shi. Fifty years of graph matching, network alignment and network comparison. Information Sciences, 346: 180-197, 2016.
[9] Fajwel Fogel, Rodolphe Jenatton, Francis Bach, and Alexandre d' Aspremont. Convex Relax- ations for Permutation Problems. Advances in Neural Information Processing Systems, 26, 2013.
[10] Kexue Fu, Shaolei Liu, Xiaoyuan Luo, and Manning Wang. Robust point cloud registration framework based deep graph matching. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8893-8902, 2021.
[11] Michael Garey and David Johnson. Computers and Intractability; A Guide the Theory of NP-Comple Completeness. WH Freeman & Co., 1979.
[12] Steven Gold and Anand Rangarajan. A graduated assignment algorithm for graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(4):377-388, 1996.
[13] David E Gordon, Joseph Hiatt, Mehdi Bouhaddou, Veronica V Rezelj. Svenja Ulferts, Hannes Braberg, Alexander S Jureka, Kirsten Obernier, Jeffrey Z Guo, Jyoti Batra, et al. Comparative host-coronavirus protein interaction networks reveal pan-viral disease mechanisms. Science, 37066521)eabe9440. 2020.
[14] Jiawei He, Zehao Huang, Naiyan Wang, and Zhaoxiang Zhang. Learnable graph matching: Incorporating graph partitioning with deep feature learning for multiple object tracking. In Proceedings of the JEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 5299-5309, 2021.
11

---

[15] Greg Henry, Ping Tak Peter Tang, and Alexander Heinecke. Leveraging the 6 artificial intelligence datatype for higher-precision computations. In 2019 IEEE 26th Symposium on Computer Arithmetic (ARITH), pages 69-76. IEEF, 2019.
[16] Judith Hermanns, Konstantinos Skitsas, Anton Tsitsulin, Marina Munkhoeva, Alexander Kyster, Simon Nielsen, Alexander M Bronstein, Davide Mottin, and Panagiotis Karras. GRASP: Scal- able Graph Alignment by Spectral Corresponding Functions. ACM Transactions on Knowledge Discovery from Data, 17(4):1-26, 2023.
[17] Nicholas Higham and Theo Mary. Mixed precision algorithms in numerical linear algebra. Acta Numerica, 31:347-441 414, 2022.
[18] Harold W Kuhn. The Hungarian method for the assignment problem. Naval Research Logisties Quarterly, 2(1-2):83-97, 1955.
[19] Zixun Lan, Ye Ma, Limin Yu, Linglong Yuan, and Fei Ma. AEDNet: Adaptive Edge-Deleting Network For Subgraph Matching. Pattern Recognition, page 109033, 2022.
[20] Zixun Lan, Binjie Hong, Ye Ma, and Fei Ma. More Interpretable Graph Similarity Computation Via Maximum Common Subgraph Inference. IEEE Transactions on Knowledge and Data Engineering, pages 1-12, 2024.
[21] Marius Leordeanu and Martial Hebert. A spectral technique for correspondence problems using pairwise constraints. In Tenth IEEE International Conference Compuler Vision (ICCV'05) Volume 1, volume 2. pages 1482-1489. IEEE, 2005.
[22] Marius Leordeanu, Martial Hebert, and Rahul Sukthankar. An integer projected fixed point method for graph matching and map inference. In Advances in Neural Information Processing Systems, pages 1114-11 122, 2009.
[23] Jure Leskovec and Andrej Krevi. SNAP Datasets: Stanford large network dataset collection. http://snap... stanford...r..o edu/data, June 2014.
[24] Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, et al. Deepseek-v3 technical report. arXiv preprint 1144377412.19437, 2024.
[25] Chang Liu, Chenfei Lou, Runzhong Wang. Alan Yuhan Xi, Li Shen, and Junchi Yan. Deep neural network fusion via graph matching with applications to model ensemble and federated learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song. Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning. volume 162 of Proceedings of Machine Learning Research, pages 13857-13869 PMLR, 17-23 Jul 2022.
[26] David G Lowe. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 60(2):91-110, 2004.
[27] Yao Lu, Kaizhu Huang, and Cheng Lin Liu, A fast projected fixed-point algorithm for large graph matching. Pattern Recognition, 60:971-988 2016.
[28] Sharan Narang, Gregory Diamos, Erich Elsen, Paulius Micikevicius, Jonah Alben, David Garcia, Boris Ginsburg, Michael Houston, Oleksii Kuchaiev, Ganesh Venkatesh, et al. Mixed precision training. In Int. Conf. on Learning Representation, 2017.
[29] John Von Neumann. Functional Operators, Volume II: The Geometry of Orthogonal Spaces. Princeton University Press, Princeton, NJ, 1932. Reprinted in 1950.
[30] Duy M. H. Nguyen, Nghiem T. Diep, Trung Q. Nguyen, Hoang- Bao Le, Tai Nguyen, Tien Nguyen, Trung'Tin Nguyen, Nhat Ho, Pengtao Xie, Roger Wattenhofer, James Zhou, Daniel Sonntag, and Mathias Niepert. LoGra-Medt Long Context Multi- Alignment for Medical Vinion-Language Model, 2024. URL https: arxivv www.iv.ogg/aaaaaa..aaaa otgg/bss///rarr 02615
[31] Sartaj Sahni. Computationally related problems. SIAM Journal on computing, 3(4):222-279 1974.
12

---

[32] Sartaj Sahni and Teofilo Gonzalez. P-complete approximation problems. Journal of the ACM (JACM), 23(3):555- 565, 1976.
[33] Binrui Shen, Qiang Niu, and Shengxin Zhu. Fabricated Pictures Detection with Graph Matching. In Proceedings of the 2020 2nd Asia Pucific Information Technology Conference, pages 46-51, 2020.
[34] Binrui Shen, Qiang Niu, and Shengxin Zhu. Adaptive Softassign via Hadamard- Hadumard-Equipped Sinkhorn. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 17638-17647, 2024.
[35] Binrui Shen, Qiang Niu, and Shengxin Zhu. Lightning graph matching. Journal of Computa- tional and Applied Mathematics, 354:116189, 2025.
[36] Ziying Song, Haiyue Wei, Lin Bai, Lei Yang, and Caiyan Jia. Graphalign: Enhancing accurate feature alignment by graph matching for multi-modal 3d object detection. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 2358-3369, 2023.
[37] Vogelstein, Joshua and Conroy, John and Lyzinski, Vince and Podrazik, Louis J and Kratzer, Steven G and Harley, Eric T and Fishkind, Donniell E and Vogelstein, R Jacob and Priebe, Carey E. Fast Approximate Quadratic Programming for Graph Matching. PLOS one, 10(4):e0121002, 2015.
[38] Hongteng Xu, Dixin Luo, and Lawrence Carin. Scalable gromov-wasserstiin learning for graph partitioning and matching. In Advances in Neural Information Processing Systems, volume 32, 2019.
[39] Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin Duke. learning for graph matching and node embedding. In International Conference Machine Learning, pages 9932-6941. PMLR, 2019.
[40] Kun Xu, Liwei Wang, Mo Yu, Yansong Feng, Yan Song, Zhiguo Wang, and Dong Yu. Cross- lingual Knowledge Graph Aligmment via Graph Matching Neural Network. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 3156-3161, 2019.
[41] Junchi Yan, Xu-Cheng Yin, Weiyao Lin, Cheng Deng, Hongyuan Zha, and Xiaokang Yang. A short survey of recent advances in graph matching. In Proceedings of the 2016 ACM on international conference on multimedia retrieval, pages 167-174, 2016.
[42] Mikhail Zaslavskiy, Francis Bach, and philPPhlippp Vert. A path following algorithm for the graph matching problem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31 (12):2227-2243) 2008
[43] Ron Zass and Amnon Shashua. Doubly stochastic normalization for spectral clustering. Ad- vances in Neural Information Processing Systems, 19, 2006.
[44] Feng Zhou and Fernando De la Torre. Factorized Graph Matching. IEEE Transactions Pattern Analysis and Machine Intelligence, 177471777- 2015.
13

---

A
Notations
The common symbols are summarized in Table A
Table Symbols and Notations.
Symbol
Definition
G, G
matching graphs edge attribute matrices of G and G node attribute matrices number of nodes of G and G matching matrix
A, A
F,
and G
n,n
M
Nxx=
the set of n permutation matrices the set of n. doubly stochastic matrices a column vector of all Is,0s frace
Daxe
1,0
tr(-)
Frobenius inner product Frobenius norm the parameter in FRA the step-size parameter 8/16/32/64-bil Floating Point TensorFloat 32
0
FP8/16/32/64
TF32
B
Convergence Criterions
B.1 Convergence criterion of SDSN
We recall the SDSN projection steps below:
x*) PP (x(R-1)).
x(t) x(h)= (X(())
1 12x1
X
11
x [X|
Pi(X) X
11
P2(X)
n²
n
Before the non non-negative projection, the updated matrix satisfies
Σ
Σ
(k)
Σ
(2) i
n.
(22)
co
After applying the non-negative projection (all negative elements are set to 0), we obtain
Σ
x (k)
Σ x
=
|
(23)
8 (K)
&
<0
Since Eeg (K) converges to n,
Σ
(2)
Σ
(k)
(24)
c0
natural represent the residual. Moreover, the von Neumann successive projection lemma 29 guarantees that this distance decreases monotonically over successive iterations. Therefore, we define a dimensional scaled error as
1 x (k)
(x)(
1,
(25)
n
where normalization by n ensures applicability to matrices of any size. Furthermore, since 1 x (k- 1) computed in Pi (-), we can avoid the computation for the error by approximately using 7 (x (k-1))
in k-th iteration.
14

---

B.2 Convergence criterion of the matching algorithm
The matching algorithm in DSPFP
27 adopts the following original convergence criterion:
NTO))
N(--1
max
max(
max (((-))
(26)
which was also adopted by the ASM [34]. This metric primarily captures local fluctuations between the successive iterations. To better characterize the global structural evolution, we adopt the following
normalized Frobenius criterion:
8 |LNC NÚ-D ||
(27)
This criterion demonstrates enhanced suitability for our framework due to two principal considerations: (1) The Frohenius norm inherently aligns with the FRA and the objective formulation, ensuring mathematical consistency throughout the optimization process. (2) The normalization scheme
provides a scale-invariant measurement the variation of the solution trajectory.
C Proofs in Section 4
Theorem 1. The solution to the scaled doubly stochastic projection problem
D arg
min
|| - ID- X
(28)
DED
is equivalent to the solution of a Frobenius-regularii linear assignment problem:
Dx arg max
(X),
(x) (D, - (D.
(29)
DEDaxm
Proof. The squared Frobenius norm can be expanded as:
D - 0 =
0 0 (xx,,,))) X)
(30)
Since the term g x, X) is constant with respect to D, it does not affect the optimization. Thus, the objective simplifies to:
D arg min DEPaxn
-DD.
(31)
As result, the problem reduces to:
(D,X) 1 (D,
D& arg DEDaxa
(32)
Proposition 1. For nonnegative matrix X RRxn the following inequality holds:
1
e s 0
(33)
Proof. Since D& is the maximizer of I (X). ) we have
r r
(34)
where D& is maximizer of the unperturbed problem maxDE (D,X). Expanding the incquality gives:
(Dx. (D%. (DX, x) - (Dx
(35)
Rearranging terms, we have:
(D& X) (DX)) ( 2 1 (D& D&) (D D
(36)
15

---

In particular, the maximum of (Dx: DX) is n when Dx is a permutation matrix. Therefore, we have (DX. D S for general cases.
(D X) (DX, X) 2 0 (1D2, n).
1
(37)
Taking the negative of both sides,
1
X) X)= (n (D) D)
(38)
0
Note that D& E Daxx is doubly stochastic, so S (D* xxx S n (The inner product achieves
its maximum value when D& is a permutation matrix, while attaining its minimum value under the condition that all elements of D& are 1t). Therefore,
- n-1
(39)
which completes the proof.
Theorem 2. Let X E R4x" and F be the convex hull of the optimal permutation matrices for the linear assignment problem with X. As 9 + co, the matrix D converges to unique matrix D E F, where D* is the unique solution to minDer //6 (D.
Proof. We prove the theorem in two steps: (1) DE lies on the face F, and (2) D& must equal D
Step 1. Since D is defined as the maximizer of
= (D,)) 8 (D.
(40)
we have
(D 2 (D"),
(41)
which implies
1 1 D3) D2) 2 (D", X)
1
(Dx,))
/ Dr, D*).
(42)
As 0 + oc, we have
Φ (D) D2) - 0 and | 0
1
DD D 0.
(43)
Taking the limit, we get
lim (D* X) (D* x)- (+xx0
(44)
Since D is the optimal solution to the linear assignment problem, for any D E D Daxn
(D,X) S (D*,)).
(45)
In particular,
(D X) (D",)).
(46)
Combining both inequalities, we obtain
lim (D)x X) X)*,X),
(47)
80000
which means D& lies in the face
Step 2. For each fixed 0, the objective (D) is strictly concave in D due to the quadratic term D), Strict concavity ensures that for large 0, the maximizer of I (D) is unique.
Suppose, for the sake of contradiction, that D& # D* Since both are in F, we have
(DX,
X).
(48)
If D& were distinct from D*, then 0 + xc, the perturbed objective (D) would admit at least two different maximizers (D& and D*) with the same objective value. This contradicts the uniqueness guaranteed by strict concavity. Therefore, D& must coincide with D*.
Since the entire sequence D& is bounded and any convergent subsequence converges to D" it follows that
D& + D as 0 + oc.
(49)
This establishes the desired convergence.
D
16

---

Proposition 2. As 0 - 0, the malrix D& converges to the matrix 11
Proof. As f + 0, the matrix D& exhibits the limiting behavior:
lim D arg min DEDax
(D, 1 Dg.
(50)
8-0
Since Dij n. Σ Dij achieve minimum when all entries are equal to 1/n. Consequentl,
11
lim D = 8-0
(51)
Proposition 3. For X E IRT"" the SDSN algorithm requires
In (ecIxT + m)) In(c)
iterations to produce solution X that satisfies | Dl < and c (0, 1) the convergence rate constant of the DSN algorithm.
c. where D& is the exact solution
Proof.
X = P1P2(X))
(52)
where Pi and P2 denote projection operators maintaining the constraint X,1 = (1TXa)* = 1. This operation can be explicitly expressed as:
XE+1 Pi (Xx + (x+))
(53)
with the absolute value operation applied element-wise to matrix entries. Expanding the projection operators yields the detailed formulation:
Xx41 ; (x++|xa)++ 1 (Xx + IX&D]1
11 1. (x 11'1 (x 11". n
n
(54)
Through vectorization and Kronecker product analysis, we transform the matrix equation into its vector form:
vec(Xe+1) vec (|X&|+ Xx) + vec (11?)
(55)
7
where A = =1 -1 _11") @ (1 111T' possesses spectral radius of }.2 Defining the error vector es = vec(Xt) - vec(X.) for solution matrix X., we derive the enror propagation relationship:
ck+1 A vec (|Xg) X.) Ae Applying norm inequalities and leveraging the spectral properties of A, we obtain:
(56)
1 ||e+1ll S (c& (clllexll + [ewll)) = c|lex|l
(57)
2
where c = sup ( } < establishes the linear convergence rate.
Considering scaled initial conditions 0X, the first iteration enror becomes |/e]|| ||0 iterations with scaling factor 0, the error evolution follows:
-oll. For k
||ex || = |0 -
(58)
The e-accuracy requirement | ck coll S e leads to the logarithmic relationship:
1n + k Inc + In |eoll < Ine
(59)
17

---

Solving for the required iterations yields:
k' In(e/0) + In(e//leol) In (e/(O)))o)))
(60)
Inc
l
Given the initial error bound |leoll || + || + finalize the iteration complexity:
8(IX F+n)
(61)
Inc
This demonstrates the logarithmic relationship between the scaling factor 0 and the required iterations to maintain solution accuracy, completing the proof.
Lemma 1. The closed-form solution to the optimization problem
Px(X) = arg min X YIlis s.t. =1= x
(62)
is given by:
1 (1 11 -x 11 11 n2
(63)
Proof. The Lagrangian corresponding the problem takes the form:
L(Y, = ir(Y'" 2XY) - 1:00~--'0 y - 12 Y
(64)
By differentiating 64
we obtain the following:
àL
0L 0ul
0L
x u11" 1
Y1,
T
(65)
0Y
0p1
Thus, let OL
0, we have:
y= x 1 1p2
(66)
Applying 1 to both sides of the equation above, we get:
0 X1 + 1/41 + 1 1.
(67)
Multiplying both sides of 667 by n., we get:
nX1 + n² #1 + m111 1.
(68)
Multiplying both sides of 668 by 11 we get:
11 + m11 #I m1p211
(69)
Subtracting (68 and 669
we obtain:
(nI - 11 x1=-11))x1+n(111 n(nI -11 0.
(70)
Solving this equation, find:
P1
X1 n
k11,
#2
x 1, n
(71)
where k1, h2 E R.
Substituting the results into 64 rewrite the Lagrangian as:
L(Y,k1, k2) tr(FFT 2XF) + L x1 111 - 1
(72)
n
n
Finally, setting #1
8L.
0L
solve for Y:
Dke
1xx1
1
Y
I
X
11T
11
(73)
n²
71
which completes the proof.
18

---

Theorem 3. In the SDSN algorithm, the k-th iterate Xx can be split as X Xx + AX2, where A represents the rounding error. Then, the projection operator satisfies
P = P((E)) Pa(AXa),
where (x(AX) is the solution to the following minimization problem:
Pa(AX) = arg min |AX- YIl s.t. Y1 0
The subsequent transformations of the error term A X can be expressed as
P2Pa ... PaPa(
which asymptotically converges the zero matrix 0nxn-
Proof. In SDSN calculations, the nonnegativity-enforree precision, so this error analysis focuses the first component P1 (9).. To examine the behavior of the rounding error AX during iterations, we split X2, the variable at the k-th iteration,
part can be computed entirely in low
X X + AX2
(74)
Then, P becomes
I
1s
(Xx
AXx
(X+ AXx]1
11 + Xx + AX 1Xie + AXx)
(75)
n
1 X
11 X
1'AXx n²2
AX
11
Xa
11
+AX++ +
11
2
T
P1(8x)
AT
Lemma establishes that AT: Ps(AXE), so the subsequent transformation of A can be represented as
P2P3 ... P2P3(
Through this process, the propagation of this rounding error ultimately converges to Onxn to satisfy the constraints imposed by both (-).) and Pz(-).
D Details of the Mixed-Precision Design
Algorithm 1 Frobbnnis-Regulanee Assignment Matching (FRAM)
Require: A, A, K, X, a, 8ph
I: Initial (U) Onxä
2: max(A, (A, A, K)
FP64
3: A A/Ve, À A/ve, K K-
FP64
4: while ((t) > Sth do
5:
((t) = AN 1) A + AK
TF32
6:
D (D) ,0)
FP32
7:
NT
a)N(--1) + aD 8(0) ||A7(0)
FP64
8:
FP64
9: end while
Discretize to oblain M
> FP64
11: return Matching matrix M
Implementation details of the mixed-precision design.
Algorithm employs mixed-preeite precision design to improve computational efficiency while maintaining numerical stability, with precision for each operation specified via inline annotations. It starts by
19

---

normalizing matrices A, A, and K in steps 2-3 using FP64 to prevent overflow and ensure input consistency, enabling subsequent low-precision acceleration.
Step 5 employs TF32 (which is computationally similar to FP16) for critical computations. This strategy strikes balance between performance and accuracy: it utilizes high-throughuut GPU fused multiply-add operations while keeping precision loss within acceptable limits, as proven in Theorem In contrast, further reducing the precision risks numerical instability due to inadequate accuracy.
3
Step then switches to FP32 to maintain consistency, as FPI6 would introduce additional truncation error, reducing accuracy by approximately 5% without increasing iterations. In contrast, FP32 maintains nearly the same number of iterations as FP64, balancing efficiency and precision.
Finally, step reverts to FP64 for high-precision iterative updates, compensating for earlier precision trade-off'. Steps 8 and 10 continue in FP64 to ensure final output accuracy. This precision hierarchy accelerates performance in preconditioned computations while maintaining the reliability required for assignment matching tasks.
Introduction to different data type.
Data Type
Bits
Range
Precision
FLOPs (RTX 4080)
FP32
32
f-10ss
100s1
10
52.2 TeraFLOPS
TF32
[-10ss
10
10
209 TeraFLOPS
FP64
64
1030s
10305)
10 10-16
0.82 TeraFL.PS
Table 5: Characteristics of FP32, TF32, and FP64 floating-poin formats. The listed ranges are approximate, based on the IEEE 754 standard. The FLOPs column reports the theoretical peak performance (in TeraFLOPS) achieved by the NVIDIA RTX 4080 GPU for each format. Here, i TeraFLOPS equals 1022 floating-poin operations per second, providing standard measure of compute performance.
Why were competing algorithms not evaluated lower precision settings? Mixed precision requires careful theoretical justification to ensure robustness against truncation errors and to preserve numerical stability. Not all baseline methods are robust in this regard. In particular, GA, S-GWL, GWL, and ASM all involve exponential operators, which prone to numerical instability. For example, even in double precision, the default parameter settings in S-GWL can already cause numerical overflow, documented in Appendix F of [34), making single-precision computation more problematic. Among the remaining baselines, though AIPFP is comparatively more tolerant of reduced precision, it suffers from slow runtime; GRASP is inherently sensitive to noise. Lowering the precision does not alleviate their main limitations.
E Graphs from Images
The construction consists of three primary steps. (1) Node extraction: SIFT (26
extracts key points
as potential nodes and computes the nodes' attributes; (2) Node selection: select the nodes that exhibit a high degree of similarity (i.e., the inner product of feature vectors) to all candidate nodes of the other graph. (3) Edge attribute calculation: nodes form a fully connected graph weighted by inter-node Euclidean distances.
Real-world images. The graphs are constructed as described in the previous paragraph. The number of nodes is set to 1000 (For the bike set, only record the results for the first three pictures with 700 nodes, as the other images lack sufficient keypoints.). The running time and matching error are computed by averaging the results over five matching pairs (1 vs. 2, 2 vs. 3, ..... 5 vs. 6) from the same image set.
House sequence is widely used benchmark dataset consisting of 111 grayscale images of a toy house taken from different viewpoints. The graphs are constructed as described the previous paragraph, but without node attributes, to evaluate the algorithms from a different perspective. Matching pairs consist of the first image and subsequent images with 5 image sequence gaps (such as image vs. image 6 and on).
20

---

Discussion of the regularization parameter
We evaluated the impact of the parameter 0 on the FRAM algorithm across different types of tasks, as shown in T Overall, the algorithm's 's performance increases as the parameter grows, but the improvements follow a pattern diminishing marginal effect, while an excessively large 0 may lead to slight degradation in performance. For tasks with attributed information, relatively small values of 0 are sufficient to achieve good performance. contrast, for more challenging tasks without attributed information, larger values of 0 are required to achieve the best performance.
House (attributed edges)
Bark (attributed edges and nodes)
Facebook Network
8
Time (sec)
Error 10))
Time (sec)
Error 10*)
Time (sec)
Node Accuracy
0.1
0.4
16.4
0.1
0.5
5.4
1
165
69.26%
0.5
0.6
7.3
0.5
0.6
4.1
5
192
85.92%
1
0.7
7.2
0.9
4.2
10
222
91.69%
2
0.9
7.0
1.1
4.2
15
246
93.48%
4
1.2
7.1
4
1.2
4.3
20
263
93.98%
Table 6: Influence of the parameter on algorithmic performance across diverse graph types.
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide detailed proofs and many numerical experiments for what claimed in the abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: As mentioned in the conclusion, the parameter 0 is set empirically, and the implementation mixed-preed sixeddprecision acceleration remains preliminary.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
22

---

Answer: [Yes]
Justification: We have clearly listed the assumptions of each theorem, and have provided the proof in the appendix
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We have provided the code to reproduce the experiments in the article.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. .., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
23

---

reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
All datasets used are publicly available, and we have provided the programming
code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/
Cooee//dddeeebmimiia ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All the settings mentioned in this article are included in the programming.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This article concerned the optimization algorithm instead of statistical uncer- tainties.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We have provided the details Section 7.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The research this article does not involve human subjects and therefore will not be harmful to humans.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This article is mostly a theoretical and computational work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
25

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No such risks are associated with this study.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We have cited the original papers that provide the datasets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
26

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
We do release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
27

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The core contributions of this research are independent of LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy for what should or should not be described.
28


Reviews:
[{"review_id": "qbNVYFnr4h", "reviewer": "Reviewer_2pmt", "summary": "This paper presents a novel algorithm for graph matching, reformulating the projection step as a Frobenius-regularized linear assignment (FRA) problem to address the NP-hardness of the Quadratic Assignment Problem (QAP), mitigating errors from feasible region inflation and numerical scale sensitivity via a tunable regularization term. It introduces the Scaling Doubly Stochastic Normalization (SDSN) algorithm to solve FRA efficiently. Furthermore, a theoretically grounded mixed-precision architecture that achieves acceleration on GPU with negligible accuracy loss compared to CPU. The approach outperforms baselines in accuracy and efficiency across various datasets, and provides theoretical analyses of regularization effects, convergence, and error bounds, marking the first graph matching algorithm with a theoretically sound mixed-precision design.", "questions": "Q1. It seems that each iteration in Algorithm~2 takes $O(n^2)$ time complexity, and the number of iterations is related to more parameters rather than $n$. So the complexity of Step~6 in Algorithm~1 seems not accurate, which also influences the total time complexity of Algorithm~1.\n\nQ2. What does the matching error refer to? I guess it should be the accuracy defined in Equation~(18), so please use a consistent terminology in the paper. \n\nQ3. What does $K$ refer to in Algorithm~1? I guess it should be the $F\\tilde{F}^T$. Please introduce it in Algorithm~1.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n\nS1. This paper improves the popular DSPFP methods by reformulating the projection step as an FRA problem, extending the selection of projections such that improve the solution. Corresponding solution, SDNS algorithm, is also proposed.\n\nS2. The paper provides a solid theoretical analysis of the proposed FRA problem and SDSN solution, including the impact of the regularization parameter, convergence properties, and error bounds. \n\nS3. Extensive experiments on real-world datasets demonstrate that FRAM outperforms baselines in both accuracy and speed. \n\nWeakness:\n\nW1. In my comprehension, the proposed FRA problem introduces a family of projection problems, which should lead to equivalent graph matching, but actually results differently due to the projection. In other words, the FRA introduces a family of alternatives in the projection step. Hence, the issue of my most concern is how to select the proper FRA problem, in other words, the parameter $\\theta$. However, such strategies are not discussed in the paper.\n\nW2. The paper only conducts the experiments with $\\lambda = 1$. It remains unclear whether the value of $\\lambda$ will influence the performance of graph matching algorithms.\n\nW3. The $O(n^2)$ space complexity leads to the worry about the scalability of the proposed FRAM method.", "was_revised": true, "final_justification": "Most of my concerns are addressed. Thus, I will increase my rating.", "rebuttal": "We sincerely thank the reviewer for the positive and encouraging comments on our work. We are pleased that you recognized our improvements to the DSPFP methods (S1), the solid theoretical analysis provided (S2), and the extensive experiments demonstrating the advantages of our approach on real-world datasets (S3). Your affirmation is truly motivating and strengthens our confidence to continue pursuing research in this direction. Thank you again for your thoughtful review and kind recognition.\n\n**W1:** We thank the reviewer for this insightful comment. The parameter $\\theta$ indeed plays a pivotal role: it governs the error bound between the projected matrix $D_X^\\theta$ and the optimal linear assignment solution $D_X^\\infty$ (Theorem 2), and it also correlates with the number of iterations required by SDSN (Theorem 6). Accordingly, our selection strategy is to choose the smallest feasible value of $\\theta$ that preserves matching performance, thereby maximizing computational efficiency. Empirically, when graphs are plain (e.g., unattributed nodes and edges), a larger $\\theta$ is necessary; conversely, when attribute information is richer (e.g., edges carry meaningful attributes), a smaller $\\theta$ suffices.\n\nWe will supplement the manuscript with a dedicated discussion of parameter‐selection strategies for $\\theta$, along with comprehensive experimental results. Due to space constraints in this rebuttal, we present below a concise summary of how varying $\\theta$ impacts both runtime and matching accuracy.\n\n\n**Plain Graph: Facebook**\n| $\\theta$ | Time (sec) | Mean Node Acc |\n| :------: | :--------: | :-----------: |\n|    1     |    165    |    69.26%     |\n|    5     |    192    |    85.92%     |\n|    10    |    222    |    91.69%     |\n|    15    |    246    |    93.48%     |\n|    20    |    263    |    93.98%     |\n\n**Attributed Graph: House**\n|  θ  | Time (sec) | Matching Error($\\times 10^3$) |\n| :-: | :--------: | :---------------------------: |\n| 0.1 |    0.4     |             16.4              |\n| 0.5 |    0.6     |              7.3              |\n|  1  |    0.7     |              7.2              |\n|  2  |    0.9     |              7.0              |\n|  4  |    1.2     |              7.1              |\n\n**Attributed Graph: Bark**\n|  θ  | Time (sec) | Matching Error($\\times 10^4$) |\n| :-: | :--------: | :---------------------------: |\n| 0.1 |    0.5     |              5.4              |\n| 0.5 |    0.6     |              4.1              |\n|  1  |    0.9     |              4.2              |\n|  2  |    1.1     |              4.2              |\n|  4  |    1.2     |              4.3              |\n\n**W2:** We sincerely thank the reviewer for the careful reading and insightful comment. The parameter $\\lambda$ serves to balance the contributions of edge and node information in the graph matching process. As discussed in detail in DSPFP [23] (see lines 244–245), this parameter has already been extensively studied. To maintain focus and avoid redundancy, we did not re-evaluate this parameter.\n\nIn line with DSPFP [23], we set $\\lambda = 1$ in our experiments to ensure a fair and consistent comparison.  We will clarify this point in the revised manuscript to avoid any potential misunderstanding.\n\n**W3:** We thank the reviewer for this valuable observation. The $O(n^2)$ space requirement primarily stems from storing graph-related structures such as adjacency or affinity matrices, rather than from the FRAM algorithm itself. To some extent, this is an inherent limitation of the graph matching problem. Nevertheless, this quadratic memory footprint is sufficient to handle the vast majority of practical graph matching tasks. Tackling significantly larger-scale problems may require fundamentally new paradigms—an important direction for future work, while it beyond the scope of this manuscript. Many classical methods incur even higher memory costs, such as those with $O(n^4)$ space complexity (see lines 261–262), demonstrating the relative efficiency of FRAM.\n\n**Q1**: We thank the reviewer for pointing out this oversight. We agree with the observation and will revise the complexity of Step 6 in Algorithm 1 to $O(Ln^2)$, where $L$ denotes the number of iterations as specified in Theorem 6. This revision ensures a more accurate characterization of the computational cost.\n\n**Q2:** We thank the reviewer for the helpful comment. The term _matching error_ is defined in Equation (18). To maintain consistency in terminology, we will revise the sentence on line 252 from\n\n> “For attributed graph matching tasks, we evaluate the accuracy of algorithms”  \n> to  \n> “For attributed graph matching tasks, we evaluate the performance of algorithms using the matching error defined in Equation (18).”\n\nThis revision will help avoid confusion and ensure consistent usage of terminology throughout the paper.\n\n**Q3:** We thank the reviewer for pointing this out. In Algorithm 1, the matrix $K$ indeed refers to the product $FF^T$. We appreciate the reviewer’s suggestion and will explicitly introduce and clarify the definition of $K$ in Algorithm 1 in the revised manuscript to avoid any confusion."}, {"review_id": "y5prHswH6Q", "reviewer": "Reviewer_tDfZ", "summary": "This work presents a method for graph matching by reformulating projection-based regularizations as linear assignment problems. Doing so, the authors devise an effective and elegant algorithm to control the relaxation. The method is fast without compensating for substantial accuracy. Moreover, the paper introduces a mixed-precision architecture that seems novel and is validated to contribute to the stability of the approach. Overall, this work is a well-written contribution that, although niche in its application, might be interesting to the broader field and could spur further applications beyond graph matching.", "questions": "- What are the limits of the precision? At what point does the accuracy break down dramatically?", "limitations": "None", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength: \n- The paper makes a nice theoretical contribution with the formulation of a linear assignment in the projection step for graph matching. The approach is core to a graph matching algorithm by iteratively solving a regularized linear assignment. This is shown to be a fast and effective method.\n- The mixed-precision scheme proposed in the paper is a further well-crafted implementation detail that is shown to be effective and well-grounded.\n- The manuscript is well written and covers the body of existing work adequately, which allows the authors to situate their work in the landscape of prior work.\n- The convergence proofs, although not extensive, are convincing.\n- The evaluation leaves no gaps and the experiments are confirming the effectiveness of the method.\n\nWeaknesses: \n- While the method may potentially be broadly applicable, the application is limited to graph matching in this manuscript as a rather niche paper. \n- Although this is adequately evaluated, there is cost in accuracy.", "was_revised": true, "final_justification": "As discussed post-rebuttal, I did not have many concerns and still support acceptance.", "rebuttal": "We sincerely appreciate the reviewer’s thoughtful and positive feedback. We are pleased that you found the theoretical contribution—particularly the formulation of the linear assignment in the projection step and the iterative regularized approach—both core and effective. We’re also grateful for your recognition of the mixed-precision scheme as a meaningful implementation detail, as well as your comments on the clarity of the manuscript and its positioning within the existing literature. Your affirmation of the convergence analysis and the thoroughness of our evaluation is especially encouraging. Thank you again for your valuable and encouraging review.\n\n**Weakness1. Broadly applicable:** We are grateful to the reviewer for the high appreciation of our work. While this manuscript focuses on graph matching as a representative application, we plan to explore and extend its applicability to other domains in future work.\n\n**Weakness2. Cost in accuracy:** We thank the reviewer for the careful reading and thoughtful comment. In practice, the mixed-precision version exhibits only a negligible drop in accuracy—at worst, 0.2% lower than the full double-precision variant. Interestingly, due to the final discretization step from the continuous solution, the mixed-precision implementation even slightly outperforms the double-precision version in some cases. We will incorporate these observations into the main text to provide a more complete and balanced evaluation.\n\n**Q1. Precision:** \nWe thank the reviewer for raising this important question. Mixed-precision computation indeed introduces two key considerations: numerical stability and error propagation. In our method, low-precision computation is used in two core modules: gradient matrix calculation and SDSN. We address the reviewer’s question from the perspective of precision design in these two components:\n\n- Gradient Matrix Computation: We use TensorFloat-32 (TF32) for this step, which shares a similar precision with FP16. Further reducing the precision beyond TF32 risks numerical instability, especially for large-scale problems, due to insufficient representation accuracy.\n    \n- SDSN Module: This component is executed in FP32. While it is technically possible to use FP16, doing so introduces additional truncation residual. Without increasing the number of iterations accordingly, the accuracy drops by approximately 5%. On the other hand, the number of iterations under FP32 is almost identical to that of FP64, offering a good balance between efficiency and precision. Thus, we adopt FP32 as the most reliable choice in this context.\n\nWe appreciate the reviewer’s insightful question and will incorporate a detailed discussion of these design choices and precision limitations into the revised manuscript to enhance completeness."}, {"review_id": "zeDb0GMnJN", "reviewer": "Reviewer_6upw", "summary": "This paper considers the problem of solving quadratic assignment problems via the convex relaxation of replacing the set of permutation matrices by the set of doubly stochastic matrices. It focuses on a specific algorithm for solving the resulting problem by first projecting the gradient of the cost function onto the set of doubly stochastic matrices and subsequently forming a convex combination of the projected gradient with the current iterate. In particular, it investigates scaling the cost function by a constant positive factor (which alters the iterates), and considers conducting different parts of the computation in different precision. Numerical results demonstrate that the resulting scheme is faster and yields lower cost functions than the compared competitors.", "questions": "- Please detail the setting of the relaxation, and put the presented work into context of the literature on such relaxations  (see 1) above).\n- Please explain the novelty in Algorithm 2, comment on why alternating projections instead of algorithms like Dykstra/ADMM with a common stopping criterion like the primal-dual gap was used (see 2) above).\n- Please revisit the presentation of the results incorporating the suggestions in 4) above.", "limitations": "yes", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "While the overall problem is interesting and investigations on different ways of solving the relaxation are interesting, the presented work has several structural weaknesses. \n1) It does not specify any properties of the cost function. When optimizing quadratic costs over the set of permutation matrices, $||P||_F^2 = n$ is a constant, such that it can be added or subtracted without changing the minimizer. Thus, for the optimization problem over permutation matrices, it does not matter if the costs are convex, concave or neither of the two. Yet, this property heavily affects the type of problem after relaxing the permutation matrices to doubly stochastic matrices, see \n- F. Fogel, R. Jenatton, F. Bach, and A. d’Aspremont. Convex Relaxations for Permutation Problems, NeurIPS 2013.\n- N. Dym, H. Maron, and Y. Lipman. DS++ - A flexible, scalable and provably tight relaxation for matching problems, ACM Transactions on Graphics (TOG), 2017.\n- F. Bernard, C. Theobalt and M. Moeller, DS*: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problems, CVPR 2018.\n\n for exemplary works that discuss and exploit this aspect. In case the quadratic costs are (strongly) convex, the particular choice of optimization algorithm should not matter in terms of the solution quality anymore – the minimizer of the relaxed problem is unique and can be computed by a wide range of different convex optimization algorithms. For a sufficiently concave objective, the minimizer over the doubly stochastic matrices will coincide with the minimizer over the permutations, thus making the relaxation exact, but also NP-hard to minimize. These aspects are neglected in the presented paper. It remains unclear if the claim is to solve a convex problem faster, or a non-convex problem heuristically better for common problem instances. \n\n2) Independent of the properties of the cost function, the subproblem of projecting the (scaled) gradient onto the set of doubly-stochastic matrices is a convex problem. This is well-known, yet the alternating projection algorithm (Alg. 2) takes a lot of room in the paper. Results like the projection of a variable onto a 2-dimensional linear subspace (row- and column-sum equal to one) and the projection onto the non-negative orthant are presented as a theorem despite being standard results from convex optimization. Accelerations of the alternating projection method (such as Dykstra’s algorithm) or ADMM/Douglas-Rachford splitting algorithms are not discussed. In this respect, the paper significantly lacks context in the fundamentals of convex optimization. \n\n3) The aforementioned lack of context is also reflected in phrasing several very simple results from convex analysis (such as theorems 1, 2 and 4) as theorems, partially without a proper contextualization such as the considered algorithm for $\\theta=\\infty$ becoming the Frank-Wolfe Algorithm. \n\n4) In my opinion, the paper is not well-written and confusing in several aspects. For example, \n- “the numerical scale invariance of the quadratic objective, which is destroyed under the projections”  is irritating. I do not know what is meant by “numerical scale invariance of the quadratic objective”. The minimizer of any cost function remains unchanged when multiplying the costs by a positive number. If the costs are convex, then the projection does not “destroy” this property. The iterates might change, but still converge to the same point (under suitable conditions/algorithm parameters). \n- Writing that DSN finds \"the nearest doubly stochastic matrix\", and Lu et al. “adapt the DSN so that the projected gradient matrix is doubly stochastic” is irritating. What is the difference? It would be better to formalize this.\n- As discussed above, I do not think that inequality (5) is a good argument to say that some scaling invariance is destroyed. \n- $D^*$ in Theorem 3 should be defined mathematically. The current description remains a little vague. \n- Alg. (2) uses the max(X,0) for the projection onto the non-negative orthant. I recommend using the same in eq. (16). They are of course identical, but having consistency would be clearer. \n- In Theorem 6 the term “convergence rate constant” crucially needs to be defined. \n- The phrase that  the “truncation residual vanishes over iterations in SDSN” is unclear to me and should be rephrased/detailed. Similarly $\\Delta X_k$ should be related to quantities defined in the algorithm. The current version is difficult to follow.\n- The costs in eq. (18) are not identical (up to a constant) to the original costs that are minimized. Squares are missing at the Frobenius norms. Have these been included in the numerical experiments? \n\n5) Considering that one of the main technical contributions is rescaling the cost function (so far in a heuristic way/via a hyperparameter as admitted in the conclusions), I consider the contribution to be somewhat limited. The mixed precision computation is interesting, but needs to be detailed. Running competing algorithms at lower precision is – to my mind – a crucial baseline.", "was_revised": true, "final_justification": "I appreciate the authors' response to my concerns and realize that I am an 'outlier' among the reviewers. Yet, I'd like to keep my rating. The authors' response that \"the optimization objective we consider is very classic in the graph matching literature, and its properties are often taken as implicit knowledge in the field. [...] The quadratic cost function used in our formulation is non-convex [41]. \" still poses a major problem for me. The problem the authors are trying to solve is the discrete problem of minimizing quadratic costs over the set of permutation matrices. As permutation matrices $P$ have the property that $\\|P\\|_F^2 = n$ (a constant), the original discrete cost function has the property that it is invariant to adding $\\alpha \\|P\\|_F^2$ for arbitrary $\\alpha$. By choosing $\\alpha$ to be the largest singular value of the original quadratic costs, the objective becomes convex (but still needs to be minimized over the non-convex, discrete set of permutation matrices). Similarly, choosing $\\alpha$ to be minus the largest singular value makes the objective concave. To my mind, there is no \"natural\" choice of $\\alpha$, not even $\\alpha=0$ because different ways of modelling the same problem could implicitly cause different $\\alpha$. After the convex relaxation, i.e., after relaxing the set of permutation matrices to the set of doubly stochastic matrices, the properties of the quadratic costs matter heavily. Citing [41] to claim the costs are non-convex is, in my opinion, not correct. The prior works I cited have exploited the property of identical formulations over the set of permutation matrices giving rise to different continuous relaxations. As the authors propose a new heuristic to solve graph matching problems via a continuous relaxation, it seems to me that the insight about the properties of the cost function needs to be discussed and possibly compared against (including possible follow-up works that I am not familiar with). I think this is particularly important because the term $\\alpha \\|P\\|_F^2$ I discussed above is identical to the second term in (9) for $\\alpha = -2/w$ (although I do not see the connection immediately).  \n\nFurthermore, not all answers by the authors seem mathematically correct. The authors state that \"Indeed, equation (18) differs from the original objective by a constant factor.\" I disagree. I agree that - up to a constant - (18) is the same as (1) if both terms in (18) had a square. This is what I remarked in my original review. But in general, $\\|X\\|_F + \\|Y\\|_F$ is not a strictly monotone rescaling of $\\|X\\|_F^2 + \\|Y\\|_F^2$, which would be needed in order to compare algorithms that minimize the objective with squares via a formulation that does not contain the squares. \n\nIn summary, although the focus of the paper might be more on mixed-precision computing than on the above discussion, I do not feel comfortable recommending the acceptance of this paper in its current form.", "rebuttal": "We sincerely thank the reviewer for the careful reading and many valuable comments. We find there may be some misunderstandings regarding the core idea of our work. To address this, we would first like to clarify the possible confusion. Below, we highlight the reviewer’s comments, with potentially misinterpreted phrases emphasized:\n\n- “It focuses on a specific algorithm for solving the resulting problem by **first projecting the gradient of the cost function onto the set of doubly stochastic matrices and subsequently forming a convex combination of the projected gradient with the current iterate.**”\n\n- “In particular, it investigates **scaling the cost function by a constant positive factor.**”\n\nThe algorithm described above corresponds to the DSPFP method instead of our FRAM. A key observation that motivated our work is that the doubly stochastic projection (DSP) step in DSPFP does not preserve the scaling-invariance property of the cost function, which we address in our formulation. By analyzing this mismatch, we show that the projection step in DSP is a special case of a more general FRA ( Frobenius-regularized Linear Assignment) problem. Under this interpretation, scaling the objective function implicitly changes the regularization parameter in the FRA, thereby leading to different solutions (the objective is non-convex).\n\nThis insight naturally motivates our main idea: using FRA to systematically approximate solutions to the QAP. Compared to the projection, this approach offers greater flexibility and interpretability. As noted in lines 163–164, increasing $\\theta$ typically improves the step-wise objective score, offering a more principled mechanism for controlling optimization behavior. Empirically, our proposed algorithm demonstrates strong performance across multiple benchmarks, validating our design. \n\nImportantly, we emphasize that $\\theta$ is a parameter of the FRA formulation, not a simple scaling factor—in fact, we deliberately use a different symbol $w$ in the paper when referring to scaling. Although FRA can be solved as a scaled DSN, the roles they play in the algorithm are fundamentally different.\n\nWe hope this clarification helps the reviewer appreciate the novelty and conceptual depth of our work—beyond simply tuning a boring scaling factor.\n\n**W1**:\nWe thank the reviewer for the thoughtful comment. The paper currently does not explicitly discuss the properties of the cost function. This is primarily because the optimization objective we consider is very classic in the graph matching literature, and its properties are often taken as implicit knowledge in the field. The baselines ([9,19,24,30])  do not explicitly analyze the properties of the objective. Nonetheless, we agree with the reviewer that incorporating a discussion (including the references recommended by the reviewer) of the cost function’s properties would enhance the theoretical understanding, especially for non-expert readers. We will clarify this aspect in the revision as follows:\n- The set of doubly stochastic matrices forms a convex set. The quadratic cost function used in our formulation is non-convex [41]. Consequently, the overall optimization problem is non-convex.\n    \n- Our algorithm heuristically addresses the non-convex problem and performs well on typical instances.\n\n[41] Aflalo, Y., Bronstein, A., & Kimmel, R. (2015). On convex relaxation of graph isomorphism. _Proceedings of the National Academy of Sciences_, _112_(10), 2942-2947.\n\n**W2**: Regarding Theorem 5, we appreciate the reviewer’s concern. Our intent in including it as a formal theorem was to close a research gap that existed in earlier work, where this step was only implicitly assumed but not explicitly derived. In response to the reviewer’s comment, we will revise the manuscript to downgrade Theorem 5 to a Proposition, to better reflect its foundational but non-novel status.\n\nWe also appreciate the reviewer’s suggestion to consider acceleration methods. However, at present, it remains unclear whether these methods (e.g., Dykstra’s algorithm, ADMM, or Douglas-Rachford splitting) exhibit robustness to truncation residual (like Theorem 7). Without such robustness, their potential acceleration effect is likely to be inferior to the overall speedup achieved by Alg.2 under a mixed-precision implementation. **This is because the mixed-precision computing accelerates not only the Alg.2, but also the matrix gradient computation ( $O(n^3)$ complexity), potentially achieving more than a 50X speedup (GPU).** A detailed numerical analysis of these acceleration techniques under reduced precision could be a valuable direction, but it may beyond the scope of the paper.\n\n**W3**: Thanks for the comment. In light of the reviewer’s suggestion, we have downgraded Theorems 2 and 4 to propositions. However, we retain Theorem 1 as a central result of the paper, as it provides the theoretical basis for extending the projected fixed-point framework to a Frobenius-regularized Linear Assignment approximation to the Quadratic Assignment Problem (QAP).\n\nWe have also incorporated the connection between the case of $\\theta =\\infty$ and the classical Frank-Wolfe algorithm, as pointed out by the reviewer. That said, we note that in practice, $\\theta$ is not set to infinity due to both computational considerations and potential degradation in performance when $\\theta$ becomes too large (see lines 164–168 for details).\n\n**W4.1**：The reviewer is correct that “numerical scale invariance of the quadratic objective” refers to the fact that the minimizer of a cost function remains unchanged under positive scaling of the cost values. However, in our setting, the cost function is non-convex, and we empirically observe that scaling the objective may lead the projection-based algorithm to converge to different points. To avoid confusion, we will revise the original phrasing:\n\n\t“the numerical scale invariance of the quadratic objective, which is destroyed under the projections”\nwill be replaced with\n\n\t“the numerical scale invariance of the quadratic objective is not preserved by the projections in the non-convex setting”.\n\n**W4.2:** We appreciate the comment. In fact, there is no significant difference between the two statements. Both refer to the use of DSN to project the gradient matrix onto the set of doubly stochastic matrices during the optimization process. We will revise the manuscript to make this clearer.\n\n**W4.3:** We agree that the objective function itself remains invariant under positive scaling. What we intended to convey is that although the minimizer of the objective is unchanged in theory, the intermediate projection steps are sensitive to such scaling. Since the problem is non-convex, this sensitivity can cause the projection-based algorithm to converge to different points under different scalings. We will revise the manuscript to make this clearer.\n\n**W4.4:** Thanks for the suggestion, we will revise the manuscript.\n\n**W4.5:** Thanks for the comment. Equation (16) follows the original DSPFP formulation. Our implementation, as shown in Algorithm (2), includes a minor modification that yields a slight speed improvement. We will emphasize this distinction more clearly.\n\n**W4.6:** We thank the reviewer for this valuable comment. Indeed, the term “convergence rate constant” is already defined in the proof of Theorem 6. To enhance clarity and readability, we will provide a formal definition of this term in the main text.\n\n**W4.7:** Truncation residual refers to the error introduced in numerical calculations when certain parts of a value are truncated (cut off) or approximated due to the limitation in precision. This typically occurs when a high precision value is converted into a lower precision value, resulting in the loss of some information.\n\n Example: let's say we have a floating point number x = 3.14159265358979, and we need to approximate it by converting it to low precision (for example, 4 decimal places): $x_{\\text{low}} = 3.1416$. The truncation residual is the difference between the original value and the truncated value:\n$\\text{Truncation Residual} = x - x_{\\text{low}} = 3.14159265358979 - 3.1416 = -0.00000734641021$.\n\n**W4.8:** We fully agree with the reviewer’s observation. Indeed, equation (18) differs from the original objective by a constant factor. Since our focus is on the matching matrix rather than the objective value, we chose to follow previous work and used the more interpretable form of equation (18) as the experimental metric. To ensure greater rigor in our manuscript, we will include a clarification of this point in the revised version.\n\n**W5:** We sincerely thank the reviewer for the positive assessment of our use of mixed precision computation. As noted at the beginning of our rebuttal, our approach does not involve “rescaling the cost function,” so we will not repeat that clarification here.\n\nWe agree that, in principle, evaluating competing algorithms under lower precision could serve as a valuable baseline. However, mixed precision requires careful theoretical justification to ensure robustness against truncation residual and to preserve numerical stability. Not all baseline methods are robust in this regard. In particular, GA, S-GWL, GWL, and ASM all involve exponential operators, which are prone to numerical instability. For example, even in double precision, the default parameter settings in S-GWL can already cause numerical overflow, as documented in the appendix (Section F) of the ASM [29]. Among the remaining baselines, though  AIPFP is comparatively more tolerant of reduced precision, it suffers from slow runtime; GRASP is inherently sensitive to noise. Lowering the precision does not alleviate their main limitations.\n\nTo provide a more complete perspective, we will include in the appendix E (Implementation Details of the Mixed-Precision Architecture) a clarification discussing these precision-related considerations about the baseline methods."}, {"review_id": "bndQO1EkjA", "reviewer": "Reviewer_jPAJ", "summary": "This paper proposes a novel algorithm that approximately solves the NP-hard quadratic assignment problem, a fundamental task for many AI-field applications. The method introduces a scaling factor, which can control the sharpness of relaxed matrix values and enables gradually reaching a solid permutation matrix.\nIn addition, it proposes a novel convergence criterion to stop the iteration at the right time. All results are theoretically supported and its superiority is experimentally proven, being approximately three times faster than the SOTA fastest method while maintaining comparable accuracy to the SOTA precise method.", "questions": "- Could you clarify the items in Weakness 1?\n- An error analysis could enhance the value of this work. Is there any possibility?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "## Strength\n1. Graph matching is a fundamental problem for the NeurIPS community.\n2. The presentation is kind for many readers.\n3. The method includes a theorem and its proof. \n4. The experimental results revealed that the method actually works faster, while maintaining SOTA performance.\n\n\n## Weakness\n### 1. Although well written, some sections are unclear.\n\n- The reviewer is unsure if normalizing with $n$ in Eq. (12) is appropriate, given the non-linear complexity increase. Despite this, Eq. (12) claims to provide \"a stable metric to assess the quality of …\" (L142). A more precise justification is needed.\n\n- “the regularization term” (L150) is not very specific. \n\n- In Fig. 3, the use of stacked bar charts makes it difficult to understand. This reviewer suggests using simple bar charts for clarity.", "was_revised": true, "final_justification": "Please see [my last comments in the rebuttal discussion](https://openreview.net/forum?id=rqn7XLNUAv&noteId=IyaLCUFb0h).", "rebuttal": "We sincerely thank the reviewer for the positive and encouraging feedback. We are glad that the reviewer found the problem of graph matching relevant to the NeurIPS community, and that the presentation was accessible to a broad audience. We also appreciate your recognition of the theoretical contribution and the empirical results demonstrating both efficiency and strong performance. Your support is greatly appreciated.\n\n**Weakness1. (a)**: We thank the reviewer for the insightful comment. The normalization by $n$ in Equation (12) is not related to algorithmic complexity, but rather serves to define a scale-independent assignment error. Since the assignment score scales linearly with $n$, this normalization decouples the error measure from the problem size, allowing fair comparison across graphs of different scales.\n\nThis is similar in spirit to the mean squared error (MSE) metric, where the total squared error is normalized by the number of elements to make the result independent of data size. Likewise, our normalized error provides a stable and interpretable measure of solution quality. We will include this clarification in the revised manuscript.\n\n**Weakness1. (b)**: We thank the reviewer for this helpful suggestion. We will revise the manuscript to clarify the meaning of “the regularization term” on line 150 by explicitly stating it as the term $\\frac{1}{\\theta} \\langle D, D \\rangle$.\n\n **Weakness1. (c)**: We thank the reviewer for the helpful suggestion.  Following the reviewer's advice, we will revise the figure to use simple (unstacked) bar charts to improve readability and make the comparison more straightforward.\n\n**Q1.  Error analysis**\nThis is a good question. FRAM searches for a solution to the graph matching problem within a doubly stochastic domain and subsequently discretizes this solution back to a permutation matrix. However, the discretization step renders the perturbation analysis of the algorithm extremely challenging. To indirectly assess the noise robustness of FRAM, we can refer to the perturbation analyses of other algorithms that, while potentially less robust, offer more tractable theoretical guarantees.\n\n - One class of such algorithms is *matching via degree profiles* [Ding et al.(2021)Ding, Ma, Wu, and Xu], which utilizes node centrality for matching. For Erdős-Rényi graphs $G(n, d/n)$, the algorithm can perfectly recover the true vertex correspondence with high probability, provided that the average degree satisfies $d = \\Omega(\\log^2 n)$ and the two graphs differ by at most a $\\delta = O(\\log^{-2}(n))$ fraction of edges. For dense and sparse graphs, these bounds can be further improved to $\\delta = O(\\log^{-2/3}(n))$ and $\\delta = O(\\log^{-2}(d))$, respectively.\n -  Another approach is *spectral-based methods*, including the GRASP \\cite{hermanns2023grasp} discussed in our manuscript and LiSA [Shen et al.(2025)Shen, Niu, and Zhu]. These spectral algorithms use leading eigenvectors to match nodes. Consequently, the robustness of these methods is approximately equivalent to the robustness of the principal eigenvector. For instance, one result from LiSA is as follows:\n$$\n\\tilde{A} = A + E,\n$$where $E$ represents the perturbations. If\n$$\n\\sqrt{2}\\|E\\|_F \\leq \\frac{\\rho}{2},\n$$\nwith $\\rho$ denoting the eigengap (i.e., the difference between the two largest eigenvalues of $A$), then the following bound holds:\n$$\n    \\|\\varphi - \\tilde{\\varphi}\\|_2 \\leq 2\\sqrt{2}.\n$$\nwhere $\\varphi$ and $\\tilde{\\varphi}$ are leading eigenvectors of $A$ and $\\tilde{A}$.\n\n[Ding et al.(2021)Ding, Ma, Wu, and Xu] J. Ding, Z. Ma, Y. Wu, and J. Xu. Efficient random graph match-\ning via degree profiles. Probability Theory and Related Fields, 179:29–115, 2021.\n\n[Shen et al.(2025)Shen, Niu, and Zhu] B. Shen, Q. Niu, and S. Zhu. Lightning graph matching. Journal of\nComputational and Applied Mathematics, 454:116189, 2025."}]

Author rebuttal:

Meta-review: This paper provides a novel heuristic for Quadratic Assignment Problem(QAP) by posing it as a Frobenius regularized Linear Assignment problem. A new algorithm SDSN is provided which can solve the posed problem. While there was all around appreciation for the proof of convergence of SDSN, the major concern is lack of discussion on other continuous relaxations of QAP and how to position this result in that context. At this point the paper can at best be recommended as borderline due to these concerns.
In case the paper is accepted the authors should implement all the changes, and more so have a detailed discussion of contrasting the proposed objective with existing relaxations.
Decision: Accept (poster)