Graph Alignment via Birkhoff Relaxation
Authors: Sushil Mahavir Varma
Irène Waldspurger
Laurent Massoulié
Venue: NeurIPS 2025 poster ()
Keywords: Graph Alignment
Quadratic Assignment Problem
Convex Relaxation
Sensitivity Analysis
Primary area: theory
TL;DR: First theoretical guarantees on Birkhoff relaxation for Graph Alignment

Abstract: We consider the graph alignment problem, wherein the objective is to find a vertex correspondence between two graphs that maximizes the edge overlap. The graph alignment problem is an instance of the quadratic assignment problem (QAP), known to be NP-hard in the worst case even to approximately solve. In this paper, we analyze Birkhoff relaxation, a tight convex relaxation of QAP, and present theoretical guarantees on its performance when the inputs follow the Gaussian Wigner Model. More specifically, the weighted adjacency matrices are correlated Gaussian Orthogonal Ensemble with correlation $1/\sqrt{1+\sigma^2}$. Denote the optimal solutions of the QAP and Birkhoff relaxation by $\Pi^\star$ and $X^\star$ respectively. We show that $\|X^\star-\Pi^\star\|_F^2 = o(n)$ when $\sigma = o(n^{-1})$ and $\|X^\star-\Pi^\star\|_F^2 = \Omega(n)$ when $\sigma = \Omega(n^{-0.5})$. Thus, the optimal solution $X^\star$ transitions from a small perturbation of $\Pi^\star$ for small $\sigma$ to being well separated from $\Pi^\star$ as $\sigma$ becomes larger than $n^{-0.5}$. This result allows us to guarantee that simple rounding procedures on $X^\star$ align $1-o(1)$ fraction of vertices correctly whenever $\sigma = o(n^{-1})$. This condition on $\sigma$ to ensure the success of the Birkhoff relaxation is state-of-the-art.

Graph Alignment via Birkhoff Relaxation
Sushil Mahavir Varma Industrial and Systems Engineering University of Michigan Ann Arbor
Irêne Waldspurger CNRS, INRIA Université Paris Dauphine
Michigan, USA sushilveumich. edu
Paris, France
waldppurgee/eeeeeaadee www.://aeeeaaadddd..ae...eeeeeee dauphine
Laurent Massoulié
INRIA, DI/ENS
PSL Research University
Paris, France
laurent.. www.oulsssllsaooooooooo paaasssuuieiiiiiar
Abstract
We consider the graph alignment problem, wherein the objective is to find vertex correspondence between two graphs that maximizes the edge overlap. The graph alignment problem is an instance of the quadratic assignment problem (QAP), known to be NP-hard the worst case even to approximately solve. In this paper, analyze Birkhoff relaxation, tight convex relaxation of QAP, and present theoretical guarantees on its performance when the inputs follow the Gaussian Wigner Model. More specifically, the weighted adjacency matrices correlated Gaussian Orthogonal Ensemble with correlation 1/ //v1 + σ² Denote the optimal solutions of the QAP and Birkhoff relaxation by II* and X respectively. We show that ||X* IIo I|? o(n) when o(n -) and || I 92()) when a = On Thus, the optimal solution X transitions from small perturbation of II* for small being well separated from II* as a becomes larger than n 0.5 This result allows us to guarantee that simple rounding procedures on X align o(1) fraction of vertices correctly whenever o(n -). This condition on to ensure the success of the Birkhoff relaxation is state-of-the-art.
Introduction
Consider two undirected graphs G₁ and G2 with vertices [n]. The graph matching/alignmeent problem defined finding a mapping between the vertices of G1 and G2 such that the edge overlap is maximized. The graph isomorphism problem is special case when G₁ G2 up to the permutation of the vertices. The graph matching problem has widespread applications in network de-anonymization (28), computational biology [30), pattern recognition 6 etc., underlining the need to design and study efficient algorithms for this problem.
More formally, let and B be the adjacency matrices (possibly weighted) of G3 and G2 respectively, then, the vertex correspondence that maximizes the edge overlap given by the optimal solution of the following quadratic assignment problem:
I arg min |AX -XBI2
XEP,
where P,, the set of all n X n permutation matrices. Quadratic assignment problems are NP- hard in the worst case and are known to be difficult to even solve approximately (24). However, for typical graphs, one could expect to efficiently solve the graph matching problem. Indeed,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

polynomial time algorithms are known for the graph isomorphism problem when G₁ = G2 is an Erdös-Rényt Rényi random graph 7 More generally, the setting with noise, where G1, G2 are not exactly equal but are correlated Erdös-Rényí graphs, has been extensively studied in the last decade 8
26 25 27 21.
A popular class of algorithms in practice with good empirical and computational performance is the convex relaxations of ( We are interested in the Birkhoff relaxation, which is tight convex relaxation, wherein the set of permutation matrices Pa, is replaced by its convex hull to get
X arg min ||AX -BBI X
where B, is the Birkhoff polytope, i.e., the set of all doubly stochastic matrices. Such relaxation has been an attractive approach in practice, with strong empirical performance for shape matching [ and ordering images in grid [TO]. It is also observed in [23] that Birkhoff relaxation, when combined with indefinite relaxation, yields excellent empirical performance on real datasets. More generally, similar relaxations proposed for gene sequencing [14), and computer vision [4].
While these results highlight the usefulness of the Birkhoff relaxation to practice due to its attractive computational and empirical performance, there is limited understanding of its theoretical perfor- mance. Theoretical guarantees for alternate convex relaxations of the QAP ( are available in the literature [1] 12 2 however, they lack in their empirical performance compared to the Birkhoff relaxation (see Section 5). Motivated by this gap the literature, we provide the first theoretical guar- antees on the performance of the Birkhoff relaxation 2 when A, B are sampled from the Gaussian Wigner Model with correlation 1/v1+ + o². Imposing such distributional assumptions on the input graphs allows for mathematical analysis, as otherwise, graph matching an NP-hard problem in the worst case.
1.1 Gaussian Wigner Model
We say that a matrix A := {AAg (.j())) is (GOE) matrix if Ay ~ 2/0,2/n) for all i [n]. Ag Ay ~ (O, 1/n) for all # j. and {Ag : i j} are mutually independent. We say that A, B E maxx follows the Gaussian Wigner Model when for all i [n]. we have (x((),
Ao to Zaj. where A, Z are i.id. GOE matrices Alternatively, we can write B = (AAo [j x² (i)}. Given an observation of A and B, the goal is to infer the ground truth n'*
where I that aligns A and B, which corresponds to the optimal solution of QAP (T] for 0² < O(n/ log n) by [15 [32. In particular, [15] shows that Ii" II' with probability o() for σ² S On// logn) and n large enough. We fix a S for simplicity.
1.2 Main Contributions
In this paper, we establish bounds on the distance of the optimal solution of the Birkhoff relaxation X* from the optimal solution of the QAP II", which is equal to the true permutation Ii with high probability. Our contributions two-fold.
Firstly, we show that ||X* -***-III1 I = o(n) whenever o o(n-')) asserting that X* is close the true permutation II. This bound in turn implies that one can use simple rounding procedures on X* to correctly align o(1) fraction of vertices. Our proof technique motivated by the literature on the sensitivity analysis of convex problems. In particular, we formulate the dual of a version of (2) for a = O. The novelty of the proof lies in the careful construction of a feasible dual solution, which in turn, provides useful bounds on X Secondly, we show that if Ωin -0.5), then ||X+ - 11 = (m)) and so, X* is far away from the true permutation 11*
The above two results establish phase transition in the behavior of (2): the optimal solution X* transitions from being small perturbation of II for slowly growing o to moving far away from II* as σ becomes greater than I/vn. In the next section, we discuss that the population version of (2) exhibits such a phase transition at 1/vn and so we believe our sufficient condition on a is loose, i.e., one can possibly show | [| = o(n) for o(n -0.5). Nonetheless, to the best of our knowledge, the sufficient condition = o(n -1) is the state-of-the to ensure that succeeds in recovering the true permutation.

---

Note that o 0 is the special case of the graph isomorphism problem. As the value of a increases, the correlation between the two graphs reduces, which makes harder to align them. In other words, noise increases, making it harder to extract the correct signal. Thus, serves as a tuning parameter to increase the hardness of the problem. The takeaway then to establish that the Birkhoff relaxation succeeds for large values of a, establishing the robustness of the relaxation. We make progress in this direction by improving upon the previously known result [2] that shows the simplex relaxation succeeds for O. These results contribute to explaining the strong empirical performance of the Birkhoff relaxation.
1.3 Related Work
Regarding practical algorithms for graph alignment, there is rich literature on optimization- based methods [21 10 22
and simple spectral-basd methods [31 13 16. The works [1] focus
on the Gaussian Wigner model and are closest to our paper. In particular, 11 proposes the GRAMPA
algorithm which solves the following convex relaxation of [
arg min X11
||AX
XBI / X for some v > 0.
Note that the optimization problem above further relaxes ( and adds quadratic regularizer. The authors in [11] establish that GRAMPA (3) succeeds recovering IT* whenever o = O(1 (1/logg/ n). While [|] asserts that GRAMPA succeeds with weaker condition on a than ours, its empirical performance is observed to be worse than the Birkhoff relaxation (2). In addition, GRAMPA requires one tune the regularization parameter 7) which is completely avoided for the Birkhoff relaxation In addition,
2 analyzes the Simplex Relaxation defined as follows:
arg
min X:1 NITT1
|AX- XBI
X
They prove that the simplex relaxation tighter convex relaxation and allow a to be non-zero. Comparison to these methods is summarized in Table [ setting.
succeeds for O. On the other hand, we consider
We refer the reader to [19 7 9 7 and the references within for analysis beyond the GOE
Paper
Algorithm Type
Algorithm Name
Noise Threshold
16
Top Eigenvector Alignment Regularized Convex Relaxation
EIG1
= ( 776
GRAMPA 3
(1/ log
Simplex Relaxation
Simplex 44
Our work
Birkhoff Relaxation
Birkhoff
a O(n
Table 1: Comparison of the spectral and optimization-bant algorithms for graph alignment on the
Gaussian Wigner Model.
2
Main Result
We now present the main theorem of the paper that characterizes when X is well separated from II+ and when X* is a small perturbation of II*
Theorem Let A, B E RRxx follow the Gaussian Wigner model with some a S (possibly dependent 1) and let II* and X* be defined as in ( and (2) respectively. Then, for any fixed e > 0 and n large enough, the following statements hold with probability 1- o()().
.
Well- Well-Separation: When 2 n--00 -0.5+t then ||X* II* 2 En for some 8 > 0.
Small- Perturbatiin:: When a S n -1-e then X
II
II
1| < 2-e322
Using the small-perturbation result above, one can implement simple rounding procedure on X* to recover 1 o(1) fraction of the permutation "t correctly.
Corollary 2. Under the hypothesis of Theorem let #(i) arg max X for all i E [n].
S -1-e for some O, then Σ 1 (a(1) # n (1)) = o(n) with probubility - o(1) for large enough.
3

---

In practice, one may want to implement more sophisticated rounding procedure such as Hungarian projection. Theorem I ensures that Hungarian projection also succeeds to recover a o(1) fraction of the permutation x correctly.
Corollary 3. Under the hypothesis of Theorem 1 let Ii arg maxnep, (X*, I1). Ifo S n-1-c for some > then (II*, II)
o(n) with probability o(1) for n large enough.
We refer the reader to Appendix A for proof details. Note that similar negative result for the well-separated case may not hold. In particular, while X is far away from II" for σ = Q(n (2(=0- does not imply that the Birkhoff relaxation fails to recover the permutation n" correctly, procedures like above can be used to post-process X which could recover IT". As our proof technique is based on sensitivity analysis of convex problems, do not explore this direction in this paper, except in Section where we conduct numerical experiments to provide insights.
rounding
To gain intuition, consider the population version of 2 where we replace the objective with its expected value to get the following optimization problem for I1 = I:
min (2 + (n + 1)I 2Tx(X)² x(x, XEB
whose optimal value is given by
X = el + 1 1-EJ, J, where = 2 2n 1)
2
where we denote the all-ones n X n matrix by J. The above can be verified using the KKT conditions. Now, using the above characterization, we get
_ = (1- (1-
oanva (0(vn) fovn= (1)
11-X11
2+ o (((Vn) iovn= (1).
The first case above asserts that whenever a >> n 0.5 we have X-11 far from J, so, we should not expect X* be close 7 as well. The first assertion of Theorem 1 formalizes this intuition. The above equation also shows that X is close to / whenever a < n -0.5
ie., X* is
we expect X to be small perturbation of T. Theorem | formalizes this only for < n n1 which only partially resolves this case. However, analyzing the Birkhoff convex relaxation (2) is known to be challenging task, and this paper provides the first results in understanding this relaxation. In particular, one of the main difficulties is in handling the non-negativity constraints. The paper [TT circumvents such difficulty by relaxing the non-negativity constraints and compensating for it with a quadratic regularizer in the objective function. Such a modification allows them to obtain closed-form expression of X*, which then shown to satisfy certain desirable properties (diagonal dominance). More recently, (2] preserves the non-negativity constraints, but the result is restricted to a and the proof exploits the structural properties of (2) that hold only when B A. We, on the other hand, tackle the challenges head-on presented by non-negativity constraints and also allow a O. Our proof technique is to carefully construct a suitable feasible solution of the dual of (2) which provides required bounds on X The main difficulty in constructing such feasible dual certificate is its high dimension as the non-negativity constraints result in n² dual variables.
3 Proof of Theorem
Without loss of generality, we assume that . T. Indeed, if ft* + 1, then, we have
||A- - XB ||AX-
x(ir)) (A+ " -1= -x((i) Z)
Thus, defining
X arg min X
|AX - (AAAA(+))))
- || A]] where we conclude that X = (ū+)"" and so | - 11 -
the last equality holds as π = II with probability 1 - o by 15 32 So, in summary, we have ii II' I without loss of generality.

---

3.1 Part I: Well-Separation
Proof of Theorem (Prtt I):, We start by upper bounding || X= by the objective function value of (2) for J/n.
Claim 4. For large enough, with probability at least Ane we have
| X
AJ
JB -JB
S 9n
n2a
The proof details of the above claim is deferred to Appendix
B.1 We now construct lower bound
on ||AX** X BI? as function of || F/ We have
||AX* - B1 ||A(1 -1 X oZ
||A(T - XX') - + 20 (A(1 X²) - (1 -I,-X)),,
||A(1 -X") - -
20 (AZ - -2B,1 - -
||A(T - -X) - -1-
0z 20 - ZA,X*) - 202
o'n
2a max (AZ 2 1#j
X Σ ifj
20 20 12 F| X
(5)
2
where the last inequality is true because
- where ă ~ N(0, I (n(x+1//2) Thus, by M
Lemma 15], with probability at least ~ have || 2 n n nvōn 2 n/2, for sufficiently large n since ē 0 constant independent of We now bound maxiz( (AZ ZAAss in the following claim.
Claim 5. For n large enough, w.p. 1 - 2n²e we have maxigj (AZZ - ZA) < 8n./2-0.5,
The proof details of the claim is deferred to Appendix B.2 Substintiing the above bound back in (5)
and noting that Eijj X I n. as X E Bn, we get
2n
|AX X B1? 2
16an 1/2te/2
X
2
0
22n
2
200²
Vn -x'1rr
(6)
4
where the last inequality holds for n large enough as 02n = ((2 and on 1/2+e/2 0n
2r/2) In
addition, use the inequality || Z I Z13 < cvn for some 0 sufficiently
large, which holds with probability at least - e by 3 Lemma 6.3). Now combining the upper
bound in Claim 4 with the lower bound in (6). get
o2n
Vn
200² 20o2Vrill1 |
9n
| X
4
8
16c
where (+) holds for n large enough. The above assertion holds with probability at least 1- -5"2e-nn/4 > e -n'² for large enough by the union bound over all the high probability bounds in the proof. This completes the proof with 1/(16c), a universal constant.
Note that the above proof does not rely on specific properties of GOE matrices. Thus, such conclusion would hold for more general symmetric matrices with i.id. entries that concentrate sufficiently, e.g., subgaussian concentration.
3.2 Part II: Small-Perturbation
The main idea of the proof is to construct a suitable dual feasible solution that provides upper bound on the off-diagonal entries of X the primal problem 2 is non-linear, resulting in an involved dual problem, we start up considering simpler optimization problem corresponding to 2.. As we will see below, this analysis, in turn, allows us to conclude meaningful bounds on X for o(n -1). For 0, we have minxeB. ||XXX XA Note that X I is an
5

---

optimal solution as it results in 0 objective function value. Thus, any optimal solution must satisfy AX -XA and so, we can further simplify write the following optimization problem.
min X
subject to AX XA
We introduce dual variables R E 14 M4, 1 E R" for the non-negativity, row sum, and column sum constraints, and M E Rexn for the constraint AX X A = 0. Then, the Lagrangian is given by
min max R.
-AX- - XA, (R, X) _ x1 1' n² pi'1. 1.
Now, we swap the order of the min and the max to obtain the dual problem.
max min(AA (AX XA, M)
+ X1 1" X' 17"1
M20.P.MM
max (MM MA + n1d + 1j X) p.=1 1-1--11
R20.PM
max -p" -p j.J subject to, AM MA R + 411 17 0.
R20.P.MMM
We are now looking for a dual feasible solution (R, H. p, M) that also satisfies strong duality. We construct approximately feasible dual solution, i.e., we have
1º + p² 1= 0, R 0, AM MA R+ p1
+17 = 0
(7)
which implies for any X E Bn with AX XA 0
X) = X) -AX - XA, 11 p
= X) -(AM - MA,X) - (p1' + 1 .X)
=(R- RAM MA - 1 -17 x) = 0.
To get meaningful bound, set R J I and appropriately construct (M, μr, (1) which implies
Xxy
We formalize this argument in the lemma below:
Lemma 6. Under the hypothesis of Theorem 7 for any X E Bn and any >> 0, for large enough, we have
S2, f#L
XAlle + 4n 1-/32 w.p. on (1).
Now to show that the bound obtained in the above lemma is small enough, upper bound ||AX XAIEF for the optimal solution X = X in the following lemma.
Lemma 7. Under the setting of Theorem 7 there exists constant e > 0 such that |AX*-X* S ca /n with probability at least e for n large enough.
The proof strategy of the above lemma is follows: As I B, feasible solution to (2) we immediately obtain AA XBB < || - B o Z O(avn), where the last inequality follows as || = ((vn) for a GOE matrix. The rest of the argument is show that - Alle S AX' Bl + O(avn) by writing B = A + oZ, expanding IAX* X XBBIF, and appropriately bounding terms involving ø. The proof details are deferred to
Appendix C.1
Proof of Theorem ( (Part II): By Lemma 6 and Lemma 7 for n n1-- get
Σ
X s 247e8+ 4n 1-e33 2en 1-e8 4n 1-e322 & 5n 1-e/32
(8)

---

where the first inequality holds with probability at least ---- -1x)== on (1) by the union bound. The last inequality holds for all large enough (depending on E). We are now ready obtain a bound on ||
r.
n
a
| 11
E
(xz)²
|| 1x
Σ
(1 (1-
+
Σ
X S 2n
2
Σ
X
=
E
X
10n 10//-r/32
(JE m
[Xiz n for any X where (*) follows as || S max Ei=1 X3 S n maxxel]] Ei=
BR This completes the second part of the proof of Theorem !
Remark 8 (Generalization beyond GOE Matrices). The main difficulties are get handle on the eigenvalues and eigenvectors of A. In particular, we explicitly use the properlies of a GOE matrix in two places in the proof. (1) Eigenvalue separation /Claim 8): We use tail bounds on the eigenvalues of random matrix from [5]. The results of [5] are applicable for all Wigner matrices (i.id. subgaussian entries), and so Claim can be extended to Wigner matrices. (2) Eigenvector Concentration [Claim 7]: To prove Claim 7, we rely on the fact that the orthonormal eigenvectors of a GOE matrix uniformly distributed on Sn-1 to obtain upper and lower concentrations on (1, u.). This step is the bottleneck, as we require such concentration results for general Wigner matrices.
Proof of Lemma 6
Proof of Lemma 6 the corresponding set of orthonormal eigenvectors. Now, we construct a dual feasible solution (R, M, ps. (i) using eigenvectors of A as the basis vectors. First, set j 0 and
For the GOE matrix A, let {1: be the set of eigenvalues and {u, J be
R
wiyu.y = =J-1, I, with wij = (ws, 1) (ug, 1) - 1 j}. 1===1
Now, to ensure approximate dual feasibility and strong duality in carefully set (M, μ1) as follows. We have
C 1
{((uEs 1) 2 n n-/o6]
P witt with w. (u,, 1) + {us 1)
where C' = 11=1- # 1yv..)22nnar with # {1(4, 1) 2 n -/16] = Em= 1 {Ku,, 1 2 n -/166.
Note that (p, 1) = O which ensures strong duality. One quickly verify it follows:
(n, 1) = Σ wikui, 1)
Σ (us, 1)2 (C 1)# {Itus 1>1 2 n -1/66]
Σ (u, 1)2 -
1=1
Next, we set
M Σ
\ wig u.u with Kij = ((u 1) 1) - (u, 1)w;) Lii j}.
(jE(n|aat
Now, we show that (R, Mb fi, M) is approximately dual feasible as
By construction, we have
R - (AM MA)- 1p
aa +
Σ
(u, 1)w,uuuf -142
n
Wh uu
Σ
(ui, 1u
Σ (un 1) 1)u
(jE(n]ass
(ui 1)
Σ
mnn - C
Σ
uau T A D.
ie(n]d 12a-3/0--/
7

---

Now, we show that | o(n) asserting that R - (AM - -MM 1,² is small. As the Frobenius norm is unitary invariant, we have
| # {Keu, 1)1 S nnn////0 + C2# {l(u,, 2
S V # {Ku 1) S sn + C2n.
Next, we get a handle on C' using the following claim, proved at the end of this section.
Claim 9. There exists constant > 0 such that, for large enough n >> O, we have, with a probability of at least - -ent 4/16
# [I(u,, 1)1 S n //366] I 3nn2-e116.
To prove the above claim, we use the fact that the orthonormal eigenvector basis of a GOE matrix is uniformly distributed Sn-1 and the details are provided in Appendix
C.2 Thus, (ws, 1) is
approximately standard normal and # (K 1) S </166]
~ n 1-16
By the above claim
0 M C
7
n
55 1/16
n nー# # (1u 1)1 S n n
n 3n c/16
where the last inequality follows for > 0 large enough (depending on c). The bound on C' implies
| $ V # {1, 1)1 S n s/16] + Can S v 3-111/16 + 25m - 2n 1/2- where the last inequality holds for large enough (depending on e). Now, for any X E Bn, we have (R (AM MA) 1p² x) = (R, X) (AM MA, x (1,² ,X)
(10)
Σ X, (M, AX xA) (p, Σ
X,j
(M, AX XA),
i.j(m))iis where the last inequality holds as (n. 1) = 0 by construction. Thus, we have
T0
Σ
X. (M, AX A) + (X, D)
(M, XA) + 2n 2-e322
where the last incquality holds (X, I |X and |X I maxjeej E < for any X Bn. Now, to complete the proof, we upper bound (M, AX AA below. Let X Enj= zuju,u for some Tiy E R for all i E [m]. Then,
n max >i= [Xyl
(M, AX - XA)
Wij uuu
Σ
Isy(A, - -y)uuuu
A - X/
Wij
Σ
Dzj (1), >11 al - u.uf
n U
A A3
3
(JElnaay (() - 21- (I - (IAX-XA|la + -U3-c)
Σ
(11)
where (+) follows from the nnuway-Schwarz inequality. In addition, we upper bound the second term by using the triangle inequality and noting that n 2 || Σx 2ij 2 Eijempjas zi for all X E B, In addition, we also note that Eije(n))ss (2; X,) ||AX - X A. Now,
we focus on getting handle on the term involving the eigenvalue separation (A: Ag). We have
(lA: مأا 1
(u; 1)2
1 El(ug, 1)1 2 n=/16
(JE(m]atss {uz, 1)2 (1A: A31 + n 11133
< 2/16
(u: 1)
5 2/
*0
Σ (sE(nlay
(p) dul + n-1-0 (12)
NJE[mjays (1) A + n 1-ez
8

---

where (*) follows for large enough by 9 In addition, (**) follows with probability 1 - m1 no- -n
ne meen"" Indeed, one can combine the union bound over E [r]] with Ku,, 1) |= - 2|(2,101 S
|zl|
vn
n //1 where 2 ~ (0, The second inequality holds with probability 1 - e e- for n large
enough (e.g. see: [T Lemma 15]). In addition, the last inequality holds with probability e- -
(e.g. see: [I]] Lemma 13J). Now, we get handle on the eigenvalue separation in the following
claim:
Claim 10. For large enough, w.p. 1 - on (1), we have Liselniagt (A::AA;+4n o)2 S Sn² <n3-3e/2
Note that naively bounding (IA, Xyا + n-1--)-2 < 2+22 results in a weaker upper bound of n#+22, We perform much tighter analysis by carefully using the tail bounds for the separation of the eigenvalue from [29]. In particular, depending on whether i - is small or large, we perform a separate analysis to lower bound [), -xyl. The analysis is especially delicate when l - - is small:
directly using the tail bounds of [29] combined with union bound over i E [rx] is not sufficient.
We instead use the tail bounds to first compute E
Σ ( ( and then use the
Markov's inequality to get a tighter upper bound. Note that the trick to introduce n -11- in (TT) is crucial here ensure the finiteness of the expectation. The proof details of this claim are deferred to Appendix C.3 Now, we continue with the proof of Lemmal6jbelov
Using the above claim along with and for large enough, we get
(M, AX
XA)
S
(IAX- - XAA(e + +n 0.5--) 2n 3/247e/8
which further implies
Σ Xij S 2m 3/2 Te/ |AX - XAI| + 2n 1-/8 + 2n 1-132
< 2n 3/2
7
|AX - + 1-
where the last inequality holds for large enough (depending on e). This completes the proof with probability - on (1) for n large enough by the union bound over all the bounds in the proof. O
Simulations
We conduct simulations on the Gaussian Wigner Model to verify our results and provide further insights (The code is publicly available at /attps://qithut
com/ smv30/ cocvex/ccee..///////o/o//o/eec/ rel We set n = 400 (unless otherwise specified) and consider o E . }]. For these parameters, we test the performance of three convex relaxations: GRAMPA M. simplex 22, and Birkhoff. We set the regularization parameter to 0.2 in GRAMPA suggested by the authors. The convex relaxations are solved using the cvxpy library in Python using SCS (Splitting Conic Solver) and we set use _se__nde rect to True, recommended for large instances for better memory management. We then project the solution of the convex relaxation to the set of permutation matrices using the Hungarian algorithm. For each n and a, we repeat the simulation 10 times and report the average fraction of correctly matched vertices in Figure [] We run the simulations on a CPU with 50GB of memory and impose a maximum run time of 3 hours for each instance.
For lergggaaaaggggieee al
On the left of Figure I we observe that the Birkhoff relaxation outperforms both Simplex and GRAMPA by exactly aligning all vertices for up to 0.5. On the other hand, the performance of Simplex and GRAMPA starts degrading for o = 0.4 and a = 0.2 respectively. Such a strong empirical performance motivates the theoretical analysis of the Birkhoff relaxation.
In the center plot of Figure 1 we plot the fraction of matched vertices and || 111 [ / VT as function of a for Birkhoff relaxation. In conjunction with Theorem | (case I), | II* / increases rapidly and converges to one as a function of a. However, even when | II* ll/ V is close to one for a E [0.3, 0.5], the Birkhoff relaxation still manages to align all the vertices. In particular, while the optimal solution X* is not close to IT*, it has a slight bias toward II as opposed to other permutation matrices. So, X is projected to I in the post-processing step of projection onto the set of permutation matrices. This result suggests that Birkhoff relaxation combined with post-processe processocssing could succeed beyond n -0.5

---

400
Birshofff reloxation with 400
Birkhoff Relaxation
Fraction Matthed Werlices
Stnkheff Simplex
Fraction Matthec Vertices
Fraction Werlices
0.n-
0.8-
03
-7 1177
n=
100
0.4-
C4-
200
300
400
0.0-
0.0
0.
0.2
0.4
0.5
0.8
1.0
0.0
0.2
0.4 0.6
0.0
1.0
0.
02
0.4
0.6
0.6
1.0
Sigma (e)
Sigma (o)
Sigma (0)
Figure 1: Fraction of Matched Vertices and X IT' l1/vn as a function of a for the Gaussian
Wigner Model: Performance GRAMPA [1. Simplex (2) and Birkhoff Relaxations
-0450
-2.3
simulated
-2.5-
-2.6
-2.7
log
-2.9
-3.9
4.6
4.8
5.0
5.2
544
5.6
58
6.0
622
log
Figure 2: Log-log plot for such that ||X
-I--
0.5 function of n.
Vn
In the right plot of Figure [ we test the performance of Birkhoff relaxation for n E {100, 200, 300, 400, 500). Although the fraction of correctly matched vertices function of a worsens as n increases, the performance degradation is gradual. Such an empirical observation hints that the Birkhoff relaxation combined with post-processing could succeed for nearly constant Although we take a first step in this direction, non-trivial ideas are needed for stronger guarantees.
In Figure
empirically compute the value of a at which ||X* -**--I111 [1*||F transitions from o(vn) to 2 y n ). In particular, for each n {0, 0.01,..., 1} to infer the value of which ||X I| /vii 0.5. A linear regression between these thresholds (log o) and log n outputs a slope of -0.45, supporting the phase transition at (l/vvn) as in Theorem
we implement the Birkhoff relaxation for
Conclusion and Future Work
In this paper, we study Birkhoff relaxation, tight convex relaxation of the Quadratic Assignment Problem (QAP). The input is sampled from Gaussian Wigner model with correlation 1 1/v1 + d² We show that X* (optimal solution of Birkhoff relaxation)
small perturbation of II" (optimal solution of QAP) when Ø < n and X is far away from II" when > n 0.55 More specifically, we show that || This result allows to align 1 o(1) fraction of vertices whenever
II* -I'-
(n) when o(n and - I|
[(() when Q(n 0.5).
o(n 11).
Based heuristic calculations using the population version of the Birkhoff relaxation, believe the condition to ensure X 11* 1|3- o(n) can be improved to a = onn-0.5 0.5), which is an immediate future work. In addition, while we show that || 11 1 a(n) when o 2(n -05). it does not imply the failure of Birkhoff relaxation, i.e., one can still post-process X appropriately to recover 11*, Hence, another future direction is to establish the success of post-processing procedures combined with the Birkhoff relaxation for greater than 00.5
10

---

References
[1] Yonathan Aflalo, Alexander Bronstein, and Ron Kimmel. On convex relaxation of graph isomorphism. Proceedings of the National Academy of Sciences, 112(10):2442-944) 2015.
[2] Ernesto Araya and Hemant Tyagi. Graph matching via convex relaxation to the simplex. Foundations of Data Science, pages 0-0, 2024.
[3] G Ben Arous, Amir Dembo, and Alice Guionnet. Aging of spherical spin glasses. Probability theory and related fields, 120:1-67, 2001.
[4] Tolga Birdal and Umut Simsekli. Probabilistic permutation synchronization using the rie- mannian structure of the birkhoff polytope. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 11105-11116. 2019.
[5] Béla Bollobás. Distinguishing vertices of random graphs. In North-Holland Mathematics Studies, volume 62, pages 33-49. Elsevier, 1982.
[6] Donatello Conte, Pasquale Foggia, Carlo Sansone, and Mario Vento. Thirty years of graph matching in pattern recognition. International journal of pattern recognition and artificial intelligence, 18(03):265-299 2004.
[7] Tomek Czajka and Gopal Pandurangan. Improved random graph isomorphism. Journal of Discrete Algorithms, 6(1):85-9)) 92, 2008.
[8] Osman Emre Dai, Daniel Cullina, Negar Kiyavash, and Matthias Grossglauser. Analysis of a canonical labeling algorithm for the alignment of correlated erdos-rényí graphs. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3(2):1-25, 2019.
[9] Jian Ding, Zongming Ma, Yihong Wu, and Jiaming Xu. Efficient random graph matching via degree profiles. Probability Theory and Related Fields, 179:29- 115, 2021.
[10] Nadav Dym, Haggai Maron, and Yaron Lipman. DS++ flexible, scalable and provably tight relaxation for matching problems. ACM Transactions on Graphics (TOG), 36(6):1-14, 2017.
[11] Zhou Fan, Cheng Mao, Yihong Wu, and Jiaming Xu. Spectral graph matching and regular- ized quadratic relaxations I: algorithm and gaussian analysis. Foundations of Computational Mathematics, 23(5):1511-155; 2023.
[12] Zhou Fan, Cheng Mao, Yihong Wu, and Jiaming Xu. Spectral graph matching and regularized quadratic relaxations II: Erdös-rényí graphs and universality. Foundations of Computational Mathematics, 2365):1567-166 2023.
[13] Soheil Feizi, Gerald Quon, Mariana Recamonde-Mendozz, Muriel Medard, Manolis Kellis, and Ali Jadbabaie. Spectral alignment of graphs. IEEE Transactions on Network Science and Engineering,
2019.
[14] Fajwel Fogel, Rodolphe Jenatton, Francis Bach, and Alexandre d' d'Aspremott. Convex re- laxations for permutation problems. Advances in neural information processing systems, 26, 2013.
[15] Luca Ganassali. Sharp threshold for alignment of graph databases with gaussian weights. In Mathematical and Scientific Machine Learning, pages 314-335. PMLR, 2022.
[16] Luca Ganassali, Marc Lelarge, and Laurent Massoulié. Spectral alignment of correlated gaussian matrices. Advances in Applied Probability, 54(1):279-310, 2022.
[17] Luca Ganassali, Mare Lelarge, and Laurent Massoulié. Correlation detection in trees for planted graph alignment. The Annals of Applied Probability, 34(3):2799-2844) 2024.
[18] Luca Ganassali and Laurent Massoulié. From tree matching to sparse graph alignment. In Conference on Learning Theory, pages 1633-1665. PMLR, 2020.
[19] Julia Gaudio, Miklós 7. Rácz, and Anirudh Sridhar. Average-case and smoothed analysis of graph isomorphism. The Annals of Applied Probability, 35(2):1373-1406 2025.
11

---

[20] Zhao-Lin Jiang and Yau Tam. On the spectral norm of doubly stochastic matrix and level-k circulant matrix. Special Matrices, 12(1):2023016, 2024.
[21] Itay Kezurer, Shahar Z Kovalsky, Ronen Basri, and Yaron Lipman. Tight relaxation quadratic matching, In Computer graphics forum, volume 34(5), pages 115-128. Wiley Online Library, 2015.
[22] Shuyang Ling. On the exactness of SDP relaxation for quadratic assignment problem. 2Xiv:2408.059422 2024.
[23] Vince Lyzinski, Donniell E Fishkind, Marcelo Fiori, Joshua T Vogelstein, Carey E Priebe, and Guillermo Sapiro. Graph matching: Relax at your own risk. IEEE transactions on pattern analysis and machine intelligence. 38(1):60-73, 2015.
[24] Konstantin Makarychev, Rajsekar Manokaran, and Maxim Sviridenko. Maximum quadratic assignment problem: Reduction from maximum label cover and Ip-based approximation al- gorithm. In International Colloquium on Automata, Languages, and Programming, pages 594-604. Springer, 2010.
[25] Cheng Mao, Mark Rudelson, and Konstantin Tikhomirov. Random graph matching with improved noise robustness. In Conference on Learning Theory, pages 3296-3329. PMLR, 2021.
[26] Cheng Mao, Mark Rudelson, and Konstantin Tikhomirov. Exact matching of random graphs with constant correlation. Probubility Theory and Related Fields, 186( 186(1):3273389 2023.
[27] Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie Yu. Random graph matching at otter's threshold via counting chandeliers. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1345-1356. 2023.
[28] Arvind Narayanan and Vitaly Shmatikov. Robust de-anonymization of large sparse datasets. In 2008 IEEE Symposium Security and Privacy (sp 2008), pages 111-125. IEEE, 2008
[29] Hoi Nguyen, Terence Tao, and Van Vu. Random matrices: tail bounds for gaps between eigenvalues. Probability Theory and Related Fields, 167:777-816, 2017.
[30] Rohit Singh, Jinbo Xu, and Bonnie Berger. Global alignment of multiple protein interaction networks with application functional orthology detection. Proceedings of the National Academy of Sciences, 105335):12633-1276 2008.
IEEE transactions on pattemn analysis and machine intelligence, 10(5):695-700 703,, 1988. [31] Shinji Umeyama. An eigendecomposition approach to weighted graph matching problems.
[32] Yihong Wu, Jiaming Xu, and H Yu Sophie. Settling the sharp reconstruction thresholds of random graph matching. IEEE Transactions on Information Theory, 6895553911 2022.
12

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Theorem and Corollary 2 formalize the claims in the abstract and introduction. To the best of our knowledge, these results are the state-of of-the-art art for Graph Alignment via Birkhoff Relaxation.
Justification:
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 in the paper and important assumptions and limitations. A No or
NA answer to this question will not 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 other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In Section (Main Result) and Section 6 (Conclusion and Future Work), we discuss that theoretical results be improved and how they pave the way for further research on Birkhoff Relaxation.
Guidelines:
The answer NA means that the paper has no 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 their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should 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 is low or images are taken in low lighting. Or speech-to-text system might not be used reliably 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 fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
13

---

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?
Answer: [Yes]
The proof of Corollary 2 is provided in Section 2. In addition, Section is dedicated to the proof of Theorem 1, while Section and the Appendix include all the necessary proofs of Lemmas and Claims.
Justification:
Guidelines:
The answer NA means that the paper does not 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 the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix 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 the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: In Section (Simulations), we mention the Python functions (including the arguments) used to solve the convex problems discussed in the paper. Values of all hyperparameters used are also indicated.
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 perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access 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 replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate 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.
14

---

reproducible, they (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If 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 instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e-g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: The code can be found on this link: https: com/ smv 30/ convex Leneex_eeele__eeee for ceerr_rapphp_ al alignment
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips) cc/ public/gee des CodeSuummi ssi iosoolooci cy) for more details.
While we encourage the release of code and data, we understand that this might not 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 source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results, See the NeurlPS code and data submission guidelines (https / //nips ctt.lss.cc.pubbiccguu....
SoddeSeeeeeu as onPol olyyy) 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. If 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 supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
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 understand the results?
Question:
Answer: [Yes]
Justification: In Section (Simulations), we mention the Python functions (including the arguments) used to solve the convex problems discussed in the paper. Values of all hyperparameters used are also indicated.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
15

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: For each set parameters, we repeat the simulation 10 times and report the complete distribution of the objective in Figure 1.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, at 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 run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
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 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
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We have included the CPU specifications and run time in the simulation
section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
16

---

Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not 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 special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
The paper provides theoretical guarantees for a well-known algorithm that has already been used practice. better theoretical understanding allows for more confidence while deploying such an algorithm in practice.
Justification:
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 or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymennt 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 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 an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that 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 as 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 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 to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
The results (simulations and otherwise) do not pose any such risk.
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
17

---

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 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: [NA]
Justification: The paper does not use existing assets.
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 released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi sswi thcode. com/ / da a asets s has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
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 creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
The paper does not release any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooell as part 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 an anonymized URL or include an 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 details about compensation (if any)?
18

---

Answer:
[NA]
Justification:
The paper does not involve crowdsoureing 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 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 the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, 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/teview based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The 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.
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 expect authors adhere the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if 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, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The paper does not involve any 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 our LLM policy (https / //tpurip///ur/psss/// wwwpeuurrpssscccofffeeeeeeeeeeee wwt.c///oeeeene////00000000
LLM) for what should should not be described.
19

---

A Rounding Procedures
Proof of Corollary Z
We bound the number of incorrectly matched indices as follows:
1
Σ (
(0)
X in (1) 2
1 X
i=1
1=1
$ 4
IT" 11 = 4||
II"
1|?
I
40n 10n3-s/32
where (x) holds as 11 = 11 with probability
- o(1) by
15 32
The last inequality is followed by
the second part of Theorem with probability o(1).
Proof of Corollary Bi Similar the proof of Theorem Now, let II arg maXneP, (X*,II, Then, we have
let IT' II* / without loss of generality.
(x* II) 2 (x*
1) o(n).
Also, we have
(X (X', [i) (4, fi> (X* I, i, - (I, + |X - -||-||i|| S (I, + o(n),
where the last inequality follows by Theorem for 2 -1-e Combining the above two inequalities, we get (T, IT) 2 n- o(n) showing that the Hungarian solution πi overlaps with the correct permutation
I for at least 1 (1) fraction of the vertices, concluding the proof.
B Technical Details for Part I: Well-Separation
B.1 Proof of Claim 4
We have
1
1
|AX - X
< |AJ JBI
= 7/
|JJ
JA - JJ-
n
xx 3
(|AJ|? +
+
n²
2
Σ Ask + Σ
Zik S Inn'
(13)
where (+) uses the inequality (a + b + c)² < 3(a² + b² + c²), and (x*) holds as S 1. Moreover, the last inequality follows with probability at least 1 - 4ne /4 for n large enough. Indeed,
Ex Ask NO, 1 1//n) and so Σ Ask S n/ for all [n] with probability -n=-n'A /1
for large enough. Thus, since A, Z are i.i.d,, by the union bound, E (E Aw) nntee and E (Eh Zix) < l+ with probability at least 4ne -nn /4
B.2 Proof of Claim 5
For any i,j E [n]. we have
2n//2 ||A
(AZ)a) =
Au Lki S
w.p. at least e =n
Vn
2/2
Vn
where (x) is true because [2, A E [n]} are independent from each other, and independent from
A. Thus, (+) follows by conditioning on A and using [I]] Lemma 13). Next, (**) holds with
probability at least - -- as ||A, < x2 || where z ~ (0, I,) and by [I] Lemma 15].
20

---

| I n -+ē2v S 2n for sufficiently large n. Thus, by the union bound, (AZ)k; S 4nn/2-112 with probability at least 1 - _e_ By further employing union bound on i, E [mx. with probability at least 1 - e nn' we have
8nf/2
max - -AA)ss - 2 max (AZ)a) S vn.
C Technical Details for Part II: Small-Perturbation
C.1 Proof of Lemma 7
We prove the desired inequality in the event where
117 E
for some constant > 0, which occurs with probability at least e if is large enough, from Lemma 15], because |||| is sum of m(n+1) independent squared Gaussian variables with variance
First, we show that ||AX - X= = O(avn). As X is the minimizer of 2 and / E Ba.
|AX" -x* x=B
S ||A B = o² 1212 < o
We now obtain an upper bound on |AX* X A using the upper bound on |AX X XBBlrr
||AX - Al / < ||AX* B + ( B)Il
= ||AX" - X F x Z
I čσσ' + + |2|
I + 2o |2
< 220
The last inequality follows as X* B, and the spectral norm of a doubly stochastic matrix is most 1, e.g., see 20 It completes the proof with e = 22.
C.2 Proof of Claim
Let U E Rax= be the matrix whose lines are M1,..., Uny It is orthogonal, and its distribution is uniformed on the set of orthogonal matrices. Therefore, U1 is uniformly distributed in VniS,-1. so that it is equal in distribution vi | for NO0, 4,). In particular,
IP #
(w
1)
< n f/16 > 3n 3n--s/10)
=
IP
#
n 1/2 e/ 16112112 > 3n 3n166/116
11/2-
< IP
#
|
< 2n =9100 > 3m 33'-e/110 1c/11)))) +P =P(1==122 2/7)
3 IP
|zo|
- 2n 2/16] 3n- 1-/16 te (for some constant C₁ > 0)
1 |2sl < 2n- -
-E1 { | < 2n 2/16]] n rc/10 + cin
I -onnnnn 1-110
cin
(for some constant C2 > 0).
Inequality (+) is true, again, from [T] Lemma 15]. Inequality (**) is true because
2n </16
Σ 1 12 < 2n -/100]
3)
n
1 dt < 2m
2
n < 2n 1-e116
c/16
e
2
2n
π
Inequality (* *) is due to Bernstein's inequality. This completes the proof of claim with = c2// for n large enough.
---nn-e/// + -in <
21

---

C.3 Proof of Claim
10
We pick (constant depending on e) such that min D - 2 n n-1e//2 with probability
least 1 (1) by [29 Corollary 2.5]. So have
Σ
E Mg (A, - +
Σ
n
(1) - 2yl 1
0=
li -l,
7
Σ
E
| K-jル- (1), 1 -
(4: - X,)
| jE(L,
n²
Σ
|ijjish (1), AUl n-1ー-)
4:2
[
Kij (D) Agl + n- + n Ste L
Σ
E
|e-l (I) Ayl 2gl+ + 10
Σ
Now, we bound the remaining terms below. We have
1
E
(12 - Aul + n 1
1
P
de
(11 - Aol + n 11-=-
P
()
Axl <
-1-e
n
dx
V
2+2c
-11-) dx + Srem P (MS del < 1 -/---// -n dr
P
<
V
V
2t2c
P
( [1
A < dæ S 2con 2+e.
where the last inequality holds by 229 Corollary 2.2] for some constant co > 0. Using the above inequality, we get
E Σ
20g 3tt
(
>ıl
1-62
Now, by the Markov's inequality, with probability
n t/4 we get
Σ
( Aul + nI1-- S 20p Lm
1
Thus, we get
Σ itj
Ayl nn S 2c
3+e 3-3e/22
(|)
where the last inequality holds for n large enough (depending on E). The proof is now complete.
22


Reviews:
[{"review_id": "BPnK9ichi8", "reviewer": "Reviewer_a4Lo", "summary": "This paper presents a theoretical analysis of Birkhoff relaxation for graph alignment under the Gaussian Wigner Model (claimed as a first). The authors establish theoretical guarantees showing that when $\\sigma = o(n^{-1})$, the optimal solution $X^* $ approximates the true permutation with $||X^* - \\Pi^*||^2_F = o(n)$, while solutions become well-separated when $\\sigma = \\Omega(n^{-\\frac{1}{2}})$. The work employs dual certificate construction techniques to handle non-negativity constraints and provides rigorous mathematical analysis including eigenvalue separations and concentration inequalities. The paper provides a synthetic simulation showcasing its prowess over the traditional baseline.", "questions": "1. **Real-world relevance:** Is it a valid question to ask how the noise levels in your theoretical model relate to those encountered in practical applications mentioned in the introduction? What range of σ values is typical in practice? Are applications grouped based on where such a relaxation can be applied and where it cannot be?\n\n2. **Scope extension:** Can these techniques extend beyond the Gaussian Wigner model to more general graph alignment settings? What are the main technical challenges when you are thinking of, let us say, sub-Gaussian, Bernoulli, etc.? Is there practical relevance to these other extension models?", "limitations": "It would be great if the authors added a dedicated limitations section discussing the points touched upon in the Weaknesses and Questions section.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 1, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\n- **Novel theoretical contribution:** A rigorous theoretical analysis of Birkhoff relaxation for graph alignment, which serves as a significant contribution to support the method's empirical success.\n- **Technical rigor:** Mathematical analysis is thorough with dual certification and proofs demonstrate rigorous treatment (eigenvalue separations, concentration inequalities, etc).\n- **Clear phase transition:** Establishes a meaningful theoretical phase regime where alignment succeeds versus fails.\n\n**Weaknesses:**\nWhile I see that the paper seems like a nice theoretical contribution, I still think that the paper reads as something developed in a vacuum. More discussion of why these results are an important event, which is needed for the next step in a practically relevant application, would be a great addition. There is limited discussion on the impact of this particular result proved in the paper.\n\n- **Limited practical relevance:** The paper fails to connect theoretical insights to downhill ramification (practical algorithm design, impact on real-world applications, etc.).\n- **Narrow experimental validation:** Evaluation restricted to synthetic Gaussian Wigner experiments. The paper is missing evaluations on standard graph matching benchmarks or real-world datasets. Graph alignment has extensive applications in computational biology, social networks, and computer vision; however, there are no specific ablation studies on the impact of specific graph strucutre on the bounds, even empirically would be great to see. Helps talk about future directions.", "was_revised": true, "final_justification": "I am updating my score as I found the reponse from the authors partially satisfactory", "rebuttal": "**Comment: Real-world relevance:** Is it a valid question to ask how the noise levels in your theoretical model relate to those encountered in practical applications mentioned in the introduction? What range of $\\sigma$ values is typical in practice? Are applications grouped based on where such a relaxation can be applied and where it cannot be?\n\n**Response:** Thank you for your comment. We more broadly discuss the implications of our result for practice. \n\n**Real-world relevance:** Doubly stochastic relaxations for graph matching problems has been an attractive approach in practice, with strong empirical performance for shape matching [Aflalo-Bronstein-Kimmel 2015] and ordering images in a grid [Nadav-Maron-Lipman 2017]. It is also observed in [Lyzinski et.al. 2015] that Birkhoff relaxation, when combined with indefinite relaxation, yields excellent empirical performance on real datasets. While these results highlight the usefulness of the Birkhoff relaxation to practice due to its attractive computational and empirical performance, there is limited understanding of its theoretical performance. Our paper is one of the first results in filling this gap in the literature.\n\n**Analysis of Graph Matching:** Graph Matching is an instance of the quadratic assignment problem, which is NP-hard in the worst case. Thus, one cannot guarantee the success of convex relaxations (e.g., Birkhoff) in the worst case. A ubiquitous approach in the literature is then to consider a stylized model, where the inputs are sampled from certain distributions. We take this approach where the problem instance is sampled as a correlated Gaussian Wigner Model with correlation $1/\\sqrt{1+\\sigma^2}$. Imposing such distributional assumptions on the input graphs allows for mathematical analysis.\n\n**Role of $\\sigma$:** Note that $\\sigma=0$ is the special case of the graph isomorphism problem. As the value of $\\sigma$ increases, the correlation between the two graphs reduces, which makes it harder to align them. In other words, noise increases, making it harder to extract the correct signal. Thus, $\\sigma$ serves as a tuning parameter to increase the hardness of the problem. The takeaway is then to establish that the Birkhoff relaxation succeeds for large values of $\\sigma$, establishing the robustness of the relaxation. We make progress in this direction by improving upon the previously known result [Araya-Tyagi 2023] that shows the simplex relaxation succeeds for $\\sigma=0$. These results contribute to explaining the strong empirical performance of the Birkhoff relaxation.\n\n\n[Aflalo-Bronstein-Kimmel 2015] Aflalo, Yonathan, Alexander Bronstein, and Ron Kimmel. \"On convex relaxation of graph isomorphism.\" Proceedings of the National Academy of Sciences 112.10 (2015): 2942-2947\n\n[Nadav-Maron-Lipman 2017] Nadav, D. Y. M., Haggai Maron, and Yaron Lipman. \"DS++: A flexible, scalable and provably tight relaxation for matching problems.\" ACM Transactions on Graphics 36.6 (2017): a184.\n\n[Lyzinski et.al. 2015] Lyzinski, Vince, et al. \"Graph matching: Relax at your own risk.\" IEEE transactions on pattern analysis and machine intelligence 38.1 (2015): 60-73.\n\n[Araya-Tyagi 2023] Araya, Ernesto, and Hemant Tyagi. \"Graph Matching via convex relaxation to the simplex.\" Foundations of Data Science 7.2 (2023): 464-501.\n\n\n\n**Comment: Scope extension:** Can these techniques extend beyond the Gaussian Wigner model to more general graph alignment settings? What are the main technical challenges when you are thinking of, let us say, sub-Gaussian, Bernoulli, etc.? Is there practical relevance to these other extension models?\n\nThank you for this insightful question! It is an interesting research direction to extend these results to more general input distributions. We discuss below the technical challenges that entail these generalizations:\n\n**Extensions of our results:** It would be desirable to consider the input matrices sampled from a certain generic distribution with some concentration properties, e.g., subgaussian and subexponential. \n\n**Well Separation Result:** We believe this part of the theorem can be generalized to more general symmetric matrices $A$ with i.id. entries that concentrate sufficiently, e.g., subgaussian concentration would suffice. In particular, we only need the following concentration properties of our random matrices $A, Z$: $\\Vert Z\\Vert_2 \\leq c$, $\\Vert Z\\Vert_F^2 \\geq n/2$, $\\\\max\\_{i,j \\\\in [n]} |(AZ)\\_{ij}| \\\\leq 2n\\^{\\\\epsilon/2-0.5}$, $\\max_{i \\in [n]}\\big|\\sum_{k=1}^n A_{ik}\\big| \\leq n^{\\epsilon/2}$. We will add that as a remark in the paper.\n\n\n**Small Perturbation Result:** The main difficulties are to get a handle on the eigenvalues and eigenvectors of $A$. Below, we outline the instances in the proof where we explicitly use the properties of a GOE matrix:\n\n*Eigenvalue separation [Claim 8]:* We use tail bounds on the eigenvalues of a random matrix from [5]. The results of [5] are applicable for all Wigner matrices (i.id. subgaussian entries), and so Claim 8 can be extended to Wigner matrices.\n\n*Eigenvector Concentration [Claim 7]:* To prove Claim 7, we rely on the fact that the orthonormal eigenvectors of a GOE matrix is uniformly distributed on $\\mathcal{S}_{n-1}$ which guarantees that $\\langle \\mathbf{1}, u_i\\rangle$ has the same distribution as $z/\\|z\\|_2$, where $z \\sim N(0, I_n)$. Thus, we can get upper and lower concentrations on $|\\langle \\mathbf{1}, u_i \\rangle|$. This step is the bottleneck, as we require such concentration results for general Wigner matrices. We will discuss this difficulty in the paper to highlight the limitations."}, {"review_id": "zTEvnUWamg", "reviewer": "Reviewer_gpnQ", "summary": "The paper considers the graph-alignment (quadratic assignment) problem under the Gaussian Wigner Model and delivers the first guarantees for the Birkhoff relaxation. It shows a sharp phase transition: when noise is $o(1/n)$, the relaxed solution remains close to the true permutation, while for noise on $\\Omega(1/\\sqrt{n})$ it drifts significantly away. The author's analysis relies on a dual certificate that respects the non-negativity constraints of the Birkhoff polytope, combined with sensitivity analysis of convex problems. The experiments are simulated on graphs of up to 500 nodes to verify theoretical results.", "questions": "1. The authors should further discuss the comparison with previous works and the generalizability of theoretical frameworks.\n\n2. Would the authors consider sampling $\\sigma$ more densely within the intermediate range $[1/n,1/\\sqrt{n})]$ and reporting how the empirical error aligns with the predicted behavior?\n\n3. The reported runtime (up to 3 hours) appears significantly higher than related works on graph matching [1, 2], where solving times are typically reported in seconds. Could the authors explain this difference?\n\n4. The authors mention that the code is simple and thus not released. However, reproducibility is critical, especially for optimization problems where solver settings can influence results.\n\n[1]. Bernard, Florian, Daniel Cremers, and Johan Thunberg. \"Sparse quadratic optimisation over the stiefel manifold with application to permutation synchronisation.\" Advances in Neural Information Processing Systems 34 (2021): 25256-25266.\n\n[2]. Dröge, Hannah, et al. \"Kissing to find a match: efficient low-rank permutation representation.\" Advances in Neural Information Processing Systems 36 (2023): 48459-48471.", "limitations": "The authors partially address the limitations of their work in Sections 2 and 6. However, a more explicit discussion of the two main limitations mentioned above would strengthen the paper.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths\n1. The paper provides the first formal guarantee for the Birkhoff relaxation in the graph alignment problems and identifies a meaningful threshold on the noise level that separates success from failure.\n\n2. The paper is well written and easy to follow. The main contributions are presented in a straightforward manner, and the core theoretical result is introduced early on, accompanied by helpful intuition.\n\n## Weaknesses\n1. The relative improvement over prior work is difficult to assess. Although the paper offers a comprehensive literature review, it does not quantitatively compare its theoretical results with existing works. A concise comparison table—summarizing assumptions, noise thresholds, and relaxation types—would help clarify the novelty of this work.\n\n2. The analysis is limited to the correlated Gaussian Wigner model. It is unclear whether the proposed proof techniques can generalize to new settings.\n\n3. While the theory predicts a sharp transition based on the noise level, this phenomenon is not fully explored in the experiments. In particular, it would be valuable to examine how the error evolves more finely across the noise regime, especially when $\\sigma$ lies between $1/n$ and $1/\\sqrt{n}$.", "was_revised": true, "final_justification": "This rebuttal address most of my concerns, and I decide to raise my rating.", "rebuttal": "**Comment:** The relative improvement over prior work is difficult to assess. Although the paper offers a comprehensive literature review, it does not quantitatively compare its theoretical results with existing works. A concise comparison table—summarizing assumptions, noise thresholds, and relaxation types—would help clarify the novelty of this work.\n\n**Response:** Adding a concise comparison table to compare our results with the literature is a good idea. We will add such a table to the paper. \n\nTable headers: Paper, Algorithm Type, Algorithm Name, Noise Threshold\n\nRow 1: [Ganassali-Lelarge-Massoulie 2022], Top Eigenvector Alignment, EIG1,  $\\sigma=\\Theta(n^{-7/6})$\n\nRow 2: [Fan-Mao-Wu-Xu 2022], Regularized Convex Relaxation, GRAMPA, $\\sigma = O(1/\\log n)$\n\nRow 3: [Araya-Tyagi 2023], Simplex Relaxation, Simplex, $\\sigma=0$\n\nRow 4: Our work, Birkhoff Relaxation, Birkhoff, $\\sigma = O(n^{-1})$\n\nCaption: Comparison of the spectral and optimization-based algorithms for graph alignment on the Gaussian Wigner Model. \n\nDiscussion: Our established threshold of $\\sigma = O(n^{-1})$ improves over the guarantees in [Ganassali-Lelarge-Massoulie 2022] [Araya-Tyagi 2023]. On the other hand, GRAMPA has better theoretical guarantees; however, the Birkhoff relaxation has better empirical performance, hence the need to develop a rigorous analysis for this strategy as well.\n\n[Ganassali-Lelarge-Massoulie 2022] Ganassali, Luca, Marc Lelarge, and Laurent Massoulié. \"Spectral alignment of correlated Gaussian matrices.\" Advances in Applied Probability 54.1 (2022): 279-310.\n\n[Fan-Mao-Wu-Xu 2022] Fan, Z., Mao, C., Wu, Y. et al. Spectral Graph Matching and Regularized Quadratic Relaxations I Algorithm and Gaussian Analysis. Found Comput Math 23, 1511–1565 (2023)\n\n[Araya-Tyagi 2023] Araya, Ernesto, and Hemant Tyagi. \"Graph Matching via convex relaxation to the simplex.\" Foundations of Data Science 7.2 (2023): 464-501.\n\n**Comment:** The analysis is limited to the correlated Gaussian Wigner model. It is unclear whether the proposed proof techniques can generalize to new settings.\n\nIt is an interesting research direction to extend these results to more general input distributions. We discuss below the technical challenges that entail these generalizations:\n\n**Extensions of our results:** It would be desirable to consider the input matrices sampled from a certain generic distribution with some concentration properties, e.g., subgaussian and subexponential. \n\n**Well Separation Result:** We believe this part of the theorem can be generalized to more general symmetric matrices $A$ with i.id. entries that concentrate sufficiently, e.g., subgaussian concentration would suffice. In particular, we only need the following concentration properties of our random matrices $A, Z$: $\\Vert Z\\Vert_2 \\leq c$, $\\Vert Z\\Vert_F^2 \\geq n/2$, $\\\\max\\_{i,j \\\\in [n]} |(AZ)\\_{ij}| \\leq 2n\\^{\\epsilon/2-0.5}$, $\\\\max_{i \\\\in [n]}\\\\big|\\\\sum\\_{k=1}\\^n A\\_{ik}\\\\big| \\\\leq n\\^{\\epsilon/2}$. We will add that as a remark in the paper.\n\n**Small Perturbation Result:** The main difficulties are to get a handle on the eigenvalues and eigenvectors of $A$. Below, we outline the instances in the proof where we explicitly use the properties of a GOE matrix:\n\n*Eigenvalue separation [Claim 8]:* We use tail bounds on the eigenvalues of a random matrix from [5]. The results of [5] are applicable for all Wigner matrices (i.id. subgaussian entries), and so Claim 8 can be extended to Wigner matrices.\n\n*Eigenvector Concentration [Claim 7]:* To prove Claim 7, we rely on the fact that the orthonormal eigenvectors of a GOE matrix is uniformly distributed on $\\mathcal{S}_{n-1}$ which guarantees that $\\langle \\mathbf{1}, u_i\\rangle$ has the same distribution as $z/\\|z\\|_2$, where $z \\sim N(0, I_n)$. Thus, we can get upper and lower concentrations on $|\\langle \\mathbf{1}, u_i \\rangle|$. This step is the bottleneck, as we require such concentration results for general Wigner matrices. We will discuss this difficulty in the paper to highlight the limitations.\n\n**Comment:** Would the authors consider sampling $\\sigma$ more densely within the intermediate range $[1/n,1/\\sqrt{n})]$ and reporting how the empirical error aligns with the predicted behavior?\n\n**Response:** That is an excellent suggestion! We simulated the Birkhoff relaxation for several values of $\\sigma \\in [0, 0.1]$ to estimate the value of $\\sigma$ for which $\\|X^\\star-\\Pi^\\star\\|_F/\\sqrt{n} = 0.5$. We obtain the following values of $\\sigma$ as the output: 0.105 (for $n=100$); 0.077 (for $n=200$); 0.063 (for $n=300$); 0.054 (for $n=400$); 0.050 (for $n=500$). A linear regression between these thresholds ($\\log \\sigma$) and $\\log n$ outputs a slope of $-0.475$, verifying the phase transition at $\\sigma = \\Theta(n^{-0.5})$. We will add these simulation results to the paper. \n\n**Comment:** The reported runtime (up to 3 hours) appears significantly higher than related works on graph matching [1, 2], where solving times are typically reported in seconds. Could the authors explain this difference?\n\n**Response:** Thank you so much for this comment. As the contributions of this paper are the theoretical analysis, and the Birkhoff relaxation is well-known in the literature, we did not attempt to improve the run-times and simply employed the SCS solver using the cvxpy library of Python. The previous work [Araya Tyagi 2023] focuses on the computational times of these convex relaxations and reports a run-time of 35 seconds for the Birkhoff relaxation with $n=300$ using the method of Alternating\nDirection Method of Multipliers (ADMM). The SCS solver, on the other hand, requires about 15 mins to converge for $n=300$, suggesting that alternative optimization techniques can perform substantially better computationally. As our focus is on the theoretical analysis, we did not attempt to improve the run-time. As a sanity check, note that our empirical results (Fig. 1 left) closely match those of [Fig. 1a, 1].\n\n[Araya Tyagi 2023] Araya, Ernesto, and Hemant Tyagi. \"Graph Matching via convex relaxation to the simplex.\" Foundations of Data Science 7.2 (2023): 464-501.\n\n**Comment:** The authors mention that the code is simple and thus not released. However, reproducibility is critical, especially for optimization problems where solver settings can influence results.\n\n**Response:** Thank you so much for this comment. We will make the code open source and include it with the paper."}, {"review_id": "EGqYBNIOF5", "reviewer": "Reviewer_dUSb", "summary": "This paper studies the problem of graph alignment in the Gaussian Wigner Model. The goal is to align the vertex sets of two correlated matrices A, B where B has an unknown permutation applied to it. The authors consider the Birkhoff relaxation of the problem, which is a well-known (but poorly studied) relaxation of the QAP formulation. When the correlation between A and B is $o(n^{-1})$, the Frobenius norm between the optimal solution and the true permutation matrix is $o(n)$. In turn, this guarantees that a simple rounding technique recovers the true permutation. On the other hand, when the correlation between A and B is $\\Omega(n^{-0.5}),$ then the Frobenius norm between the optimal solution and the true permutation matrix is $\\Omega(n)$. However, the latter result does not rule out the possibility of rounding the relaxed solution.", "questions": "In Equation (3), don’t we need an upper bound on $\\Vert Z^2 \\Vert_F$ in order to derive a lower bound on $\\Vert I – X^{\\star} \\Vert_F$?\n\nI am not following the equality in Line 198. Could you please clarify?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Analyzing Birkhoff relaxation has been a difficulty in the graph alignment literature, so I view this paper as making a solid step forward, even though the correlation algorithmic guarantees are weaker than those of competing approaches (GRAMPA, simplex relaxation). Still, empirical results show that the Birkhoff relaxation strategy (+ Hungarian algorithm) performs better than those approaches.\n\nThe cited works are incomplete. Most crucially, reference [8] is cited but not included in Section 1.3. Also, a recent paper of Gaudio, Racz, and Sridhar (“Average-case and smoothed analysis of graph isomorphism”) provides improved guarantees for matching in the noiseless Erdos-Renyi setting. \n\nLine 215: “the triangle’s inequality”\n\nLine 260: “left plot” should be “right plot”\n\nCorollary 2 uses the greedy approach for matching. However, the simulations use the Hungarian algorithm. Therefore, I don’t see the simulations as validating Theorem 1, but rather as a standalone investigation. This shortcoming should be acknowledged, and there should be an empirical evaluation that uses the greedy approach.", "was_revised": true, "final_justification": "Viewed as a theoretical contribution, I support the acceptance of this paper. In their rebuttals, the authors proposed adding several concrete elements to the paper, which I view positively.", "rebuttal": "**Comment:** In Equation (3), don’t we need an upper bound on $\\Vert Z^2 \\Vert_F$ in order to derive a lower bound on $\\Vert I – X^{\\star} \\Vert_F$?\n\n**Response:** You are correct that we need an upper bound on $\\Vert Z^2 \\Vert_F$. We obtain such an upper bound as follows: $\\Vert Z^2 \\Vert_F \\leq \\sqrt{n}\\Vert Z^2 \\Vert_2 \\leq \\sqrt{n}\\Vert Z \\Vert_2^2 \\leq c\\sqrt{n}$ for some $c>0$ large enough with high probability. The first two inequalities hold for any square matrix. The third inequality holds as $Z$ is GOE and so its spectral norm is bounded by a constant (say 3). These steps are mentioned in Line 148 of the paper.\n\n**Comment:** I am not following the equality in Line 198. Could you please clarify?\n\n**Response:** Thank you for your comment. Define a diagonal matrix $\\tilde{D}$ with $\\tilde{D}(ii) = -1$ for all $i \\in [n]$ such that $|\\langle \\mathbf{1}, u_i \\rangle| \\leq n^{-\\epsilon/16}$ and $\\tilde{D}(ii)=-C$ otherwise. Also, let $U$ to be the unitary matrix with columns $\\{u_i\\}_{i=1}^n$. Then, we have $D = U \\tilde{D} U^T$. As the Frobenius norm is unitary invariant, we have $\\|D\\|_F = \\|U \\tilde{D} U^T\\|_F = \\|\\tilde{D}\\|_F$, and so the result follows. We will mention that we are using unitary invariance of the Frobenius norm to improve the exposition, thank you!\n\n**Comment:** Corollary 2 uses the greedy approach for matching. However, the simulations use the Hungarian algorithm. Therefore, I don’t see the simulations as validating Theorem 1, but rather as a standalone investigation. This shortcoming should be acknowledged, and there should be an empirical evaluation that uses the greedy approach.\n\n**Response:** Thank you for raising this interesting point! You are correct to point out that Corollary 2 deals with a simple rounding procedure and not the Hungarian algorithm. Actually, Theorem 1 (Eq. (6) more precisely) also implies the success of the Hungarian rounding procedure. The following simple proof suffice: Let $\\Pi^\\star =I$ be the correct permutation (WLOG), $X^\\star$ be the solution of Birkhoff relaxation and $\\tilde{\\Pi} \\in \\arg\\max_{\\Pi \\in \\mathcal{P}_n} \\langle X^\\star, \\Pi\\rangle $. Then, we have $\\langle X^\\star, \\tilde{\\Pi}\\rangle \\geq \\langle X^\\star, I\\rangle \\geq n - o(n)$ by Eq. (6). Also, we have $\\langle X^\\star, \\tilde{\\Pi}\\rangle = \\langle I, \\tilde{\\Pi}\\rangle + \\langle X^\\star-I, \\tilde{\\Pi}\\rangle \\leq \\langle I, \\tilde{\\Pi}\\rangle + \\|X^\\star-I\\|_F, \\|\\tilde{\\Pi}\\|_F \\leq \\langle I, \\tilde{\\Pi}\\rangle + o(n)$ by Theorem 1. Combining the two inequalities above, we get $\\langle I, \\tilde{\\Pi} \\rangle \\geq n - o(n)$, showing that the Hungarian solution $\\tilde{\\Pi}$ overlaps with the correct permutation $I$ for at least $1-o(1)$ fraction of the vertices. We will include this result as another corollary in the paper, thank you for raising this point!"}, {"review_id": "x4YhgxiTm2", "reviewer": "Reviewer_59z5", "summary": "The paper \"Graph Alignment via Birkhoff Relaxation\" analyzes the Birkhof relaxation of quadratic assignment problems (QAPs) from a theoretical perspective. It considers the setting of inputs following a Gaussian Wigner Model, and gives guarantees based on the dependence of the standard deviation $\\sigma$ of the perturbation (in the input) on the dimensionality of the problem. The analysis results in a state-of-the-art condition for the provable success of the Birkhoff relaxation. It also indicates a phase transition for standard deviations that decay slower. A brief numerical study indicates that the success of the relaxation might go beyond the provable guarantee and that post-processing rounding schemes seem to yield strong results even in the case where the result  of the relaxation itself is provably well-separated from the true permutation.", "questions": "Please consider improving the readability of the manuscript for a broader audience. In particular, please address the explicit suggestions for an improved clarity listed under \"Strength and Weaknesses\".\n\nIn the checklist, the authors state that \"Our code is a simple Python script to solve convex optimization problems using cvxpy. Such an approach is ubiquitous, so we decided not to make the code open-source. However, we are happy to make it open-source if the reviewers deem it to be essential.\"  Despite the simplicity of the experiments, I strongly recommend making the source code publically available. This allows other researchers to reproduce that paper's results exactly with minimal effort.", "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": "The paper addresses an interesting and important problem. To the best of my knowledge, it makes an important theoretical contribution, advancing the provable guarantees in the form of error estimates for the Birkhoff relaxation of the quadratic assignment problem under specific assumptions on the input matrices. Although the numerical results do not necesarily indicate that the error bounds (or conditions) are tight, I consider this work to be an important step towards a better understanding of the Birkhoff relaxation. \n\nIn terms of the presentation, the paper is not very easy to follow. This is partly due to the theoretical, mathematically challenging nature of the topic. Yet, moving some more techincal aspects into the appendix to generate space for a little more context to address a broader audience could be helpful (e.g. possibly introducing the Birkhoff polytope formaly). Some specific aspects that could improve the presentation:\n- I would have found it helpful if alternative relaxation methods were briefly introduced. For instance, I could imagine that \"simplex\" (reference [1]) is a weaker relaxation obtained by dropping the sum-to-one constraint along the columns (or rows), but currently understanding the relaxation requires looking at reference [1]. \n- The variable $J$ (equation after l. 110) is not defined but used many times throughout the manuscript. Its meaning can be deduced from the context but this is not friendly for a quick read. \n- In line 50, I think it should read $B= A+\\sigma Z$ (not $B^{\\pi*}$), and the definition of $B^{\\pi^*}$ follows from $B$ in the next line. \n- After reading in line 123 that the analysis in [1] is restricted to $\\sigma =0$, and that the work presented here allows $\\sigma>0$, I was surprised to read \"we consider a simpler optimization problem corresponding to $\\sigma=0$ in (2)\" in line 157. It subsequently becomes clear that this is just an intermediate step, but informing the reader about the big picture of the proof strategy would be beneficial. \n- The bound $\\sqrt{n}\\geq ||X||_F^2$ is a typo (but it is used correctly, without the square, in the proof). \n- I'd recommend to consider different colors for the middle plot of Fig. 1, or insert a title \"Birkhoff Relaxation for n=400\". As the left plot has the same colors and a legend that does not apply to the middle plot, this can be misleading when having a quick look only. \n- Typo in line 260, \"left plot\" should be \"right plot\".", "was_revised": true, "final_justification": "While I agree with my fellow reviewers that the practical impact could be stronger (including dedicated solvers for competitive runtimes), I think it is a nice theoretical contribution. Moreover, the authors promised to release their code. I will keep my initial rating.", "rebuttal": "**Comment:** Please consider improving the readability of the manuscript for a broader audience. In particular, please address the explicit suggestions for an improved clarity listed under \"Strength and Weaknesses\".\n\n**Response:** Thank you so much for carefully reading our manuscript, suggesting several expositional improvements, and catching some typos! We are grateful for your time and efforts. We will implement all the suggested changes in the manuscript.\n\n**Comment:** In the checklist, the authors state that \"Our code is a simple Python script to solve convex optimization problems using cvxpy. Such an approach is ubiquitous, so we decided not to make the code open-source. However, we are happy to make it open-source if the reviewers deem it to be essential.\" Despite the simplicity of the experiments, I strongly recommend making the source code publically available. This allows other researchers to reproduce that paper's results exactly with minimal effort.\n\n**Response:** Thank you so much for this comment. We will make the code open source and include it with the paper."}]

Author rebuttal:

Meta-review: All reviewers found that the paper contains solid theoretical contribution that advances our understanding of the Birkhoff relaxation of the graph alignment problem. As the authors revise their paper, they are urged to give a more thorough discussion of the practical significance of their work, as well as a detailed comparison of the results obtained in this work with those in the literature.
Decision: Accept (poster)