OT4P: Unlocking Effective Orthogonal Group Path for Permutation Relaxation
Authors: Yaming Guo
Chen Zhu
Hengshu Zhu
Tieru Wu
Venue: NeurIPS 2024 poster (2024)
Keywords: permutation matrix
orthogonal group
differentiable transformation
stochastic optimization
Primary area: optimization
TL;DR: We present a novel differentiable transformation for relaxing permutation matrices onto the orthogonal group, which enables gradient-based (stochastic) optimization of problems involving permutation matrices.

Abstract: Optimization over permutations is typically an NP-hard problem that arises extensively in ranking, matching, tracking, etc. Birkhoff polytope-based relaxation methods have made significant advancements, particularly in penalty-free optimization and probabilistic inference. Relaxation onto the orthogonal group offers unique potential advantages such as a lower representation dimension and preservation of inner products; however, equally effective approaches remain unexplored. To bridge the gap, we present a temperature-controlled differentiable transformation that maps unconstrained vector space to the orthogonal group, where the temperature, in the limit, concentrates orthogonal matrices near permutation matrices. This transformation naturally implements a parameterization for the relaxation of permutation matrices, allowing for gradient-based optimization of problems involving permutations. Additionally, by deriving a re-parameterized gradient estimator, this transformation also provides efficient stochastic optimization over the latent permutations. Extensive experiments involving the optimization over permutation matrices validate the effectiveness of the proposed method.

OT4P: Unlocking Effective Orthogonal Group Path for Permutation Relaxation
Yaming Guo Chen Zhu"; Hengshu Zhu Tieru Wu!
School of Artificial Intelligence, Jilin University 2 School of Management, University of Science and Technology of China 3 Computer Network Information Center, Chinese Academy of Sciences "The Hong Kong University of Science and Technology (Guangzhou) [yamingguo98, 2c3930155 zhuhengshu) @gmail. com, wutr0jlu. edu cn
Abstract
Optimization over permutations is typically NP-hard problem that arises ex- tensively in ranking, matching, tracking, etc. Birkhoff polytope-based relaxation methods have made significant advancements, particularly in penalty-free optimiza- tion and probabilistic inference. Relaxation onto the orthogonal group offers unique potential advantages such as a lower representation dimension and preservation of inner products; however, equally effective approaches remain unexplored. To bridge the gap, we present temperature-conte controllee differentiable transformation that maps unconstrained vector space to the orthogonal group, where the temper- ature, in the limit, concentrates orthogonal matrices near permutation matrices. This transformation naturally implements a parameterization for the relaxation permutation matrices, allowing for gradient-based optimization of problems involving permutations. Additionally, by deriving re-parameterized gradient estimator, this transformation also provides efficient stochastic optimization over the latent permutations. Extensive experiments involving the optimization over permutation matrices validate the effectiveness the proposed method.
Introduction
Permutation refers to the reordering of elements within finite set, commonly encountered in problems involving bijections between two equally sized sets [17, 42, 15, 12). A permutation of elements can be denoted by an n x n permutation matrix, which is a square binary matrix that has exactly one entry in each row and each column, with other entries being O. We denote the set of all n-order permutation matrices as P.. := (P E 1)*xn | Prj 1, 1, Pij = (Vi, This work considers optimization over permutation matrices:
min f(P).
(1)
PEP,
Due the combinatorial nature of permutation matrices, the cardinality of the set P., grows factorially with the dimension n. typically rendering the problem NP-hard [26]. From theoretical perspective, one of the most renowned special cases of Equation (1) the quadratic assignment problem, which has attracted extensive research [37, 44J. In practical terms, Equation (1) also arises extensively in various machine learning tasks, including ranking [20, 75, 67, 68), matching [2], tracking [43], etc.
Previous studies have proposed relaxing permutation matrices into continuous spaces, including the convex hull of permutation matrices tetricess-thee Birkhoff polytope [15, 42]-and their embeddings in differentiable manifold-the orthogonal group [72, 27J. Recently, relaxation methods involving the Birkhoff polytope have made significant advancements, particularly in penalty-free optimization
"Coresponding authors
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Stepl I
Step II
%
n(n-1)
SO (n))
Mp
Figure 1: Illustration of OT4P with colored dots to help visualize the transformation. In the limit of temperature, the orthogonal matrices obtained from OT4P converge near the permutation matrices.
and probabilistic inference [59, 43, 49]. As notable example, Mena et al. [49] utilize the Sinkhorn operator [61] transform matrices into the Birkhoff polytope, bringing them closer to permutation matrices under temperature control. This approach avoids introducing penalty terms and supports variational inference.
However, providing equally good relaxation methods within the orthogonal group remains an unex- plored area. Indeed, relaxation onto the orthogonal group offers several unique potential advantages, such as: a lower representation dimension (2(n-1) leading to smaller search space; ii) the orthogonal matrix preserve the inner product of vectors, which is useful for tasks requiring the maintenance of geometric structures. In light the above advantages, this work aims develop effective method for relaxing the permutation matrices onto the orthogonal group, with a particular focus on:
2 compared to the Birkhoff polytope ((n 1)?),
Flexibility: can control the degree of approximation to permutation matrices.
Simplicity: does not rely on additional penalty terms.
Scalability: enables learning the latent variable model with permutations.
In this paper, present Orthogonal Group-based Transformation for Permutation Relaxation differentiable transformation. OT4P maps unconstrained vector
(OT4P), a comperature-contron space the orthogonal group, where the temperature, in the limit, concentrates orthogonal matrices near permutation matrices. As illustrated in Figure 1, OT4P involves two steps: I) map a vector to orthogonal matrix (o) utilizing the Lie exponential; II) move the orthogonal matrix (o) along the geodesic, controlled by temperature, to another orthogonal matrix (o), making it nearer to the closest permutation matrix (% or ( OT4P naturally implements parameterization for the relaxation of permutation matrices, allowing for pradient-based optmizatiion of problems involving permutations. In addition, 0T4P, combined with the re-parameterization trick, provides stochastic optimization over the latent permutations.
In summary, main contributions follows:
1. We present ОT4P, a differentiable transformation for relaxing permutation matrices onto the orthogonal group, characterized by its flexibility, simplicity, and scalability (Section 3.1).
2. We use OT4P to implement a parameterization for the relaxation of permutation matrices, which has the advantages of not altering the original problem, not complicating the original problem, and an efficient optimization process (Section 3.2).
3. We derive gradient estimator using OT4P and the re- parameterization trick, providing efficient tool for stochastic optimization over latent permutations (Section 3.3).
4. We validate the effectiveness of the proposed method through extensive experiments involv- ing the optimization of permutation matrices, including finding mode connectivity, inferring neuron identities, and solving permutation synchronization (Section 4).
2 Preliminaries
In this section, we give brief overview of the Riemannian geometry [38] and the Lie group theory [21] involved, with more comprchensive version available in Appendix B.

---

An n--imensionaal manifold M is space that can be locally approximated by Euclidean space I", where each point É M possesses a tangent space T,M as first-order local approximation of M around x. The Riemannian metric is collection := {m E M of inner products mz(::-)= T.M x T - R., which may define distances on the manifold. A geodesic is smooth curve that the tangent vector is parallel transported along the curve w.r.t. the Levi-Civita connection.
Lie group G is a differentiable manifold equipped with differentiable group operations, whose langent space at the identity e is the Lie algebra g. For each g E G, there exist diffeomorphisms (Definition 2) given by the left translation Lx(x) == gr (vz E G), which lead to vector space isomorphism (Definition 1) that relates the tangent space G to the Lie algebra i.e., (dLg)e g g G, Analogously, one can introduce the right translation: Ry(x) == xg (vg. x G). A Riemannian metric m on Lie group G is called left- invariant (ight-invvriant) if it renders each left (right) translation an isometry (Definition 3), allowing us associate neighborhoods of the identity with any point G using left (right) translation. If metric on the Lie group is both left and right invariant, it is termed the bi-invariant metric.
The Lie group we are interested in is the orthogonal group O(n), which consists of all n x n orthogonal matrices O satisfying OTO = 00T = I. We equip ((n) with the canonical metric, a bi- invariant metric defined as (A, B)r == trace( (A (AT)), where (:, )) the Frobenius inner product and trace(.) 1 is the trace of matrix. The subset of O(n) with determinant -1 forms subgroup known as the special orthogonal group, denoted by S0(n) := {O E R 1 = I, det O = +1}. The Lie algebra so (n) of the Lie group (O(n) comprises n x n stew-symmetric matrices, expressed so(n) == (A E R | A -A.. The Lie exponential expm(-): coinciding with the matrix exponential in the context of the matrix Lie group, maps elements in so(n) to SO(n), defined by
A
expm(A) = I+
2))
k!
The series in Equation (2) converges for all matrices A. The local inverse function of the matrix exponential is supposed to be the matrix logarithm, which is defined follows:
(11) (A - I)*
(A)
k
The series in Equation (3) converges whenever ||A- /|IF < 1, where ||A||E ((A, A)F represents the Frobenius norm induced by the Frobenius inner product.
3 Relaxing permutation on orthogonal group
In Section 3.1, we introduce the two steps of the proposed OT4P and analyze its key properties. Then, in Section 3.2, we demonstrate how to use OT4P to implement parameterization for the relaxation permutation matrices, emphasizing the advantages of such a parameterization. Finally, in Section 3.3, provide efficient stochastic optimization over the latent permutations using OT4P and the re- paraamttreiizaioon trick.
3.1
The proposed OT4P transformation
The proposed OT4P comprises two steps: 1) map a point in the vector space to an orthogonal matrix; II) move the orthogonal matrix along the geodesic under temperature control, bringing it nearer to the closest permutation matrix. We summarize the pseudo-code of 0T4P Algorithm 1.
Step I
Consider unconstrained vector space IR " For vector E R we can fill it into an upper triangular n x n matrix with zero in the diagonal. For example, in the case of n =
0
a1
02
[a1, 02 0z]
A
0
0
03
0
0
0
3

---

Algorithm OT4P
Input: Input matrix A E R hyperparameters (0, B (O(n)
1: Map A to an orthogonal matrix: O = ((A)
Defined in Equation (6)
2: Shift O to handle boundary issues: 0 BO
Details in Appendix C
3: Find the closest permutation matrix: P p(0) then
Defined Equation (7)
4: if det(P)
5: Set D = diag( (1,......,.11))
> Extension to odd permutations, see Appendix D
6: else
7: Set D -
8: end if
9: Move O toward along the geodesic controlled by r: Ô = (0) > Defined in Equation (11)
Output: The resulting orthogonal matrix Ô converge near the permutation matrix P
In the following, we employ matrices A E R=x" rather than vectors a to represent the elements in 1)n-1) A skew-symmetric matrix is uniquely determined by =(n-1) scalars, i.e., the entries above the main diagonal. Therefore, there exists isomorphism between the vector space R zin=1) and the Lie algebra so(n) formed by skew-symmetric matrices, given by
n(n-1)
I
- so(n)
(4)
A
As mentioned in Section 2, we can use the matrix exponential (Lie exponential) expm(.) to map the Lie algebra so(n) to the Lie group, i.c., special orthogonal group SO(n):
B so(n) SO(n)
(5)
A + expm(A).
to eia
Combining Equation (4) and Equation (5), we can map the unconstrained vector space the special orthogonal group SO(n), denoted
R min-1)
(O(n)
(6)
A+ expm(A -A)).
This mapping belongs to the classical category in Lie group theory and serves as an efficient solution for addressing orthogonal constraints in the field of machine learning [40, 53, 48). Similarly to Lezcano Casado [39], we present the important properties of the mapping <(-) below.
Theorem 1. The mapping Φ(-) is differentiable, surjective, and is injective on the domain U == {A
=(a=1) Im Au (A AT) E m), Vk} with X&(-) the eigenvalues. Additionally, the set SO(n) \ (lU) has a zero Lebesgue measure in SO(n).
The theorem indicates that each orthogonal matrix in SO(n) can represented by a vector in R m)n_1) with each representation being uniquely defined within set U, provided it exists there. However, permutation matrices may include -1 as one of their eigenvalues (see Figure 4), with their corresponding representations precisely lying the boundary of 2f. If the optimal solution to Equation (1) is permutation matrix with an eigenvalue of 11, may lead the optimization path to deviate from 4. To counter this, propose shifting the boundary of 2/ other eigenvalues by left-multiplying the result of Equation (6) with an orthogonal matrix B E SO(n). Theoretically. the left translation (n(O) == BO (vO SO(n)) creates diffeomorphism (Definition SO(n), where the representation of the permutation matrix in 24 changed from logm( (P) to logm( B P) We have empirically observed that the left translation LB effectively relocates the majority of permutation matrices' representations into the interior of 4. More discussion can be found in Appendix C.
Here, the term 'logm' refers to the generalized matrix logarithm, accommodating instances where the principal logarithm may not be defined.

---

Step II
Given an orthogonal matrix O E (n(,), we would like to move it toward the closest permutation matrix along the geodesic. To achieve this, we first need to find the permutation matrix P E Pn closest to O, which can be expressed as
(O) arg max (P.OFF PEP
where (A, B)r trace(A) (AT B) denotes the Frobenius inner product. Equation (7) is a linear assignment problem that can be solved in cubic time using the Hungarian algorithm [36], with further details available in the Appendix E.
Once found, can move O towards P Palong the geodesic OP. In the Lie group, utilizing the mapping logm(-). movement along the geodesic can be transformed into more manageable movement on the Lie algebra. However, since O or P may be far from the identity matrix the convergence speed of the series expansion of logm(-) may be slow or even fail to converge.
aLe
TiSD(n)
60(m)
dlp
expm
logm
Lg
S0(n)
P
We propose to carry out the above process in the tangent space T (nn)O()) rather than in the Lie algebra so(n). Due to the bi- invariant metric (-. 1) equipped on (O(n). the left translation (0))) PO (vO E SO(n)) establishes an isometry (Defini-
5
Lp
Figure 2: Illustration the mappings logm, and expmp. The left translation Lp establishes isometry between the neighborhoods of I and P. and its deriva- tive (dLp)e provides isomorphism between so (n) and TpSO(n).
tion 3) between the neighborhoods of T and P, and its derivative (dT.p). so -> (pOO(n) provides isomorphism (Def-
inition 1) between the Lie algebra so(n) and the tangent space (n). Hence, we first push O E SO(n) into the neighbor-
hood of I, then map it the Lie algebra so(n) using logm(-), and finally pull the result into the tangent space (n). this way, we define the logarithm map at P as
logmp SO(n) + TpS)(n)
(8)
+ P PP
Equation (8) maps O E (n) near P the tangent space TpSO(m). and its convergence domain also concentrates near P. Similarly, we can define its local inverse mapping:
expmp Sp)O SO(n)
(9)
A - P Pexpm( A).
Equation (9) maps A E (n)O(n) onto the special orthogonal group SO(n) located near P. With the aforementioned tools, we can easily move orthogonal matrix O toward its closest permutation matrix P by interpolation. Specifically, we map P and O to the tangent space TpSO(n) for lincar interpolation, and then map the interpolation result back to SO(n), given
Ō expmm(P
TP logm/ (P OTO) + (1 P)P logm P)])
= P Pexpm(22 PT
[ Poommmm (P)))
(10)
P expmm( logm(P O))
P(P POT.
The second equation stems from the fact that logm(!) 0. and the last equation follows from AT = expm(r (A)) when || - []]F < 1. The temperature parameter 7 (0, is used to control the degree to which the resulting orthogonal matrix Ô approaches P. It is clear that lim,~00 1 P|e 0.
5

---

Remark on odd permutations. The attentive reader may notice that Equation (10) presupposes P E SO(n), which works only for P corresponds to even permutations. However, we can readily extend it to cases where P corresponds to odd permutations. Firstly, we solve arg min pes((n) ||
P to identify an agent of P within SO(n), which admits an analytical solution p = PD with D diag( (1, ...,, 1, -1)). Then, by substituting P with P in Equation (10), O is moved toward P to obtain Ô Finally, we hight-multiph Ô by D to map it to the neighborhood of P. resulting in Ö ÖDT T Essentially, the neighborhoods of P and its agent P are linked through an isometry, specifically the right translation (O) :- OD (vO E O(n)). Consequently, when Ô is moved close enough to P, the resulting orthogonal matrix O will also be sufficiently close to P. Please refer Appendix D for more theoretical details.
Let Sp denote the set of orthogonal matrices in SO(n) whose closest permutation matrix is P. and let Spp represent its image obtained through Equation (10). Equation (10) actually transforms the submanifold Sp into new submanifold Sy, that is closer to the permutation matrix P. We define the manifold consisting of all images as MM := (S C O(n) P E Pa) Consequently, the special orthogonal group (O(n) is mapped to manifold MM that tightly wraps around the permutation matrices, which can more formally expressed as:
/ SO(n) Mp
(11)
0 - ((O) ([(O))] DT.
The aforementioned mapping covers all cases, where = diag((1, ((,...,, - 1}) for odd permutations and D = / for even permutations. In Figure 5, we provide visualization of the results of v, (-) as the temperature parameter T varies. The mapping (-()) is meaningless at points where p(-) w.r.t. Equation (7) is discontinuous. It is important to note that p(-) is piecewise constant function, changing only at points where multiple permutation matrices are equidistant. The following theorem presents key properties of the mapping (-).
Theorem 2.
The mapping thr (-) is differentiable, surjective, and injective on each submanifold Sp. Additionally, the set of meaningless points for (-(+) has a zero Lebesgue measure in SO(n).
The theorem shows that any point in the relaxation manifold Mp of permutation matrices can be uniquely identified by an orthogonal matrix in the special orthogonal group S0(n), where the set of meaningless elements (i.e., not mapped any point in .Mp) can be disregarded. Using the nin 1)
composite mapping bh o Φ. we create a one-to-one correspondence between := {A E R Im (A - A) E (- TT, Vk} and Mp, except for points associated with zero measure sets in SO(n) that are either not representable by (b-) or are meaningless for (-)(.). In other words, points in the manifold Mp, which tightly wraps around the permutation matrices, can almost be represented
one-to-one by points in U/ that lie in the unconstrained vector space.
3.2 Parameterization for gradient- optimization
This section demonstrates how to use OT4P implement a parameterization for the relaxation of permutation matrices, thereby allowing gradient-basee optimization for Equation (1). More importantly, we present three advantages of this parameterization, making a reasonable solution.
Recalling the manifold Mp obtained from Equation (11), which converges around the permutation matrices controlled by the temperature parameter We first relax Equation (1) into optimization problem on the manifold Mp:
min f(O). OEMp
(12)
Using the composite mapping vú, o o, we transform the constrained optimization problem on the manifold Mp into an unconstrained optimization problem in the vector space F "(n-1)
min
f(vr d(A)).
(13)
AER mln-1)
For the aforementioned optimization problem, we can employ standard optimization techniques, such as SGD and Adam algorithms [58], to approximate the solution. Below, we thoroughly discuss the three advantages brought about by the parameterization of OT4P.

---

The surjectivity does not alter the original problem. The surjectivity of the mapping V ø implies that every point in the manifold Mp has at least one corresponding pre-image the vector space R _ This guarantees that, during the optimization process, any point within the manifold Mp can be reached, thereby preventing the overlooking of any potential solutions to Equation (12). In particular, if we find a solution A while dealing with Equation (13), we can solve Equation (12) by mapping O = 10 o (A).
The injectivity does not complicate the original problem. If the optimization stays within u= {A " Im A - -A (-T,5), Akj, the mapping 3 o o map different elements in U to different elements on Mp. This means that each update in 2 results in a unique outcome in Mp, thereby reducing unnecessary redundant searches. Furthermore, the mapping th, & does not introduce spurious local minima, as each local minima in Mp creates single local minima in U.
The efficient optimization process. At first glance, the mapping v o involves matrix exponential and matrix power, which might demand substantial computational resources during the optimization process. Lezcano-Casado and Martunez-Rubio [40] has proposed a cheap method for computing matrix exponential expm(-) and its gradient, thanks to the efficient utilization of the scaling- squaring technique and Padé approximation [3]. Therefore, we will focus on how to handle the matrix power function efficiently.
scaling-squaring
Forward process. The orthogonal matrix O can be factorized, utilizing eigendecompo- sition, as O QXQ-1 where Q E Rnxx with each column representing an eigen- vector of O, and X diag(()1..... )n is diagonal matrix whose elements are the eigenvalues of O. In this case, the matrix power O" can be computed by applying the power function to the eigenvalues while keeping the eigenvectors unchanged [24], yielding Or Qdiag( (>i..... 1 It evident that calculating Or is not significantly more complex than computing scalar powers.
Backward process. Given an orthogonal matrix O, we assume that Ō (O) has been obtained through Equation (11). Then, there exists a unique orthogonal matrix W such that Ô W O due to the closure property of the Lie group. Therefore, in the forward pass, one can initially acquire Ô using Equation (11), followed by computing the equivalent transformation of the mapping , as W, ÔOT. In this way, the forward pass is streamlined into = W, thereby rendering the backward pass highly efficient, as only involves one linear transformation.
3.3 Re-parameterization provides stochastic optimization
In the previous section, we considered deterministic optimization over permutation matrices. However, in many scenarios, commonly build a probabilistic model to express the uncertainty inherent in the problem [7]. For such a task, it is crucial to have the ability to learn latent variable models associated with the latent nodes corresponding to permutations [20]. This section demonstrates how to perform stochastic optimization over the latent permutations using OT4P and the re-parameterization trick.
We restrict our attention to the scenario where the latent variable is permutation matrix. 2 = P. without loss of generality. Therefore, consider the probabilistic form of Equation (1) as follows
min E Ep P: (P).
(14)
The above equation deals with a distribution over permutation matrices rather than single permuta- tion matrix as in Equation (I). Evaluating and differentiating Equation (14) is challenging due to the expectation involving sum of nı terms. To remedy this, we employ the ce-parameterization trick [32, 56, 14]. In particular, we simulate (P; f) using the mappings p(-) w.r.t. Equation (7) and ((-) w.r.t Equation (11), expressed as
P ~ (P:6) - P= p(p(A - Bc)) with 0 {A, B E I m(n-1)
(15)
where ~ q(t) is random noise distribution. Equation (15) cleverly decouples the stochastic nature of the distribution q( P; 0), thereby obviating the dependence of the expectation on the parameters This enables us to draw multiple samples for the evaluation of Equation (14) with lower variance.
7

---

However. there exists not differentiable mapping p(-), which hinders gradient- gradient-based optimization
for 0. Recalling ОТ4P, we can approximate Equation (15) by relaxing the mapping p(.) +)- is evident that samples drawn from distribution 4/~ ( + Be)) converge almost surely to those from distribution ( A + Be)) owing to lim,-0 1007-004 4/ = p. To summarize, we can bring the gradient inside the expectation, as depicted below:
VE [ (++ (6(A+ BE))) Ee- Vf (W-(6(A+ Bc))),
(16)
which can now be computed using Monte Carlo [50].
Experiments
This section conducts experiments to evaluate the performance of DT4P optimization problems and probabilistic tasks. All experimental details not stated here, along with additional results, can be found in Appendix F. The core code for OT4P is available at https: //tp:/ggitttu cww/ wawaaagmmonn///TT1
4.1 Finding mode connectivity
In the first experiment, we consider an optimization problem inspired by the concept of linear mode connectivity. Recent studies have shown that neural networks trained with SGD belong to a set whose weights can be permuted so that we linearly connect those weights with no detriment to the loss [13, 57]. For demonstration purposes, we examine multi-laye perceptron (MLP) with L. layers and denote its weights as 0- {Wi]l E [L]] To find the optimal permutation between models 0 and 0B, Ainsworth et al. [2] propose the following data-free optimization problem:
min 7= (PiEP.)))
(W(4)
P. W. B 11 + ([W(A) PaW! (B)
(B) |W P, 12 (17)
The above problem is challenging because it does not admit a polynomial-ting constant-factor approximation scheme [2]. We can use OT4P to relax permutation matrices, as demonstrated in Section 3.2, enabling a gradient-based solution to Equation (17).
We explore a variety of network architectures, including MLP5 (5-layer MLP) [54], VGG11 [60], and R8 [22]. The weights for these networks derived from official pre-trained models in PyTorch [52]. with the exception of the MLP5, which is initialized randomly. For model 0p. we randomly sample permutation matrices from a uniform distribution and apply them permute the weights, yielding model A = 5 (00).. The Adam W [45] with an initial learning rate of 0.1 is employed to minimize the loss w.r.t. Equation (17), with a maximum of 500 iterations. To evaluate the results, we use the -DDistanc,, ||0, - x (8 lll,. to measure the difference from the target weights. Additionally, we flatten the permutation matrices and evaluate their alignment with the ground truth using Precision, Recall, and Hamming Distance.
We compare: 1) Weight Matching [2], which goes through each layer and greedily selects its best permutation matrix P:: 2) Sinkhorn [54], relaxing the permutation matrices to the vicinity of the Birkhoff polytope utilizing the Sinkhorn operator [61, 49]; and 3) 0T4P, our proposed method, which is evaluated with various temperature parameters. The results are reported in Tables and 4, with each experiment conducted five times. The findings indicate that Weight Matching occasionally fails to reach ground truth due to its sensitivity to random initialization. Additionally, Sinkhorn yields poor results in the VGG11 network architecture, which we attribute the relaxation on the Birkhoff polytope producing unreliable local minima. In contrast, OT4P finds the optimal permutation matrix most cases. Indeed, neural network can be conceptualized as geometric object whose vertices correspond to the rows of the weight matrices [35]. A reasonable relaxation of the matching task in Equation (17) involves rigid transformations represented by orthogonal matrices. The proposed 0T4P relaxes the permutation matrices into the orthogonal group, which is likely the primary reason for its powerful performance.
4.2 Inferring neuron identities
In the second experiment, we tackle probabilistic task motivated by the study of the neural dynamics in C. elegans [66]. This worm serves as model organism in neuroscience, with its complete neuronal connectivity known and represented by the adjacency matrix A {0, (0,1)axa However, matching
8

---

Table 1: 4 f-Disstnnce (converted by log(1 + z)) and Precision (%) of algorithms for finding mode connectivity across different network architectures.
MLP5
VGG11
ResNet18
Algorithm
log(1 1 + 41) (1)
Precision (1)
log(1 + 4) (L)
Precision (t)
log(1 + 4) (4)
Precision (t)
Weight Matching
0.000 20.00
100.0
0.000 20.00
100.0
1.215 #2.72
99.97 20.06
Sinkhorn
0.000 10.00
100.0 10000
11.61 10.07
63.08 13.14
9.830 10.181
95.56 10.s5
0T4P (r- = 0.3)
0,000 10.00
100.0 10.00
0,000 10.00
100.0 10.00
0,000 1:0.0
100.0 10.00
0T4P (r= = 0.5)
0.000 +0.00
100.0 #0.00
0.818
#1.83
99.99 #0.03
0.000 +:000
100.0 #0.00
0T4P (7 = 0.7)
0.000 +0.00
100.0 #0.00
0.000 +0.00
100.0 +0.00
0.000 +0.00
100.0 #0.00
traces from the observed neural dynamics Y E Rax1 to the neurons in the reference connectome A poses challenging task. Linderman al. [43] propose simulating neural activity using linear dynamical system Yú = P(A o W)P Y c, where c is Gaussian noise, W E RRn,, P E Pn, are latent variables, and @ is element-wise product. Our goal is to infer the latent permutation P to align the observed Y with the shared dynamics matrix W. We address this task by maximizing the marginal log-likelihood, i.e., max (P log ((|P)) using the techniques outlined Section 3.3.
+
Taking the methodology in Linderman et al. [43], we generate parameters A. W. and P with n 250 and randomly generate 1000 samples, where the noise follows Gaussian distribution . (N, 0.01). We formulate tasks of varying difficulty depending on the different proportions of known neurons [43]. Conceiving constraint matrix C E = where all elements are initialized to we ascertain that the reference neuron i corresponds to the observed neuron j. then set all elements to 0 in the i-th row and j-th column except for Cz, (see Equation (22) for an example). This constraint is enforced by zeroing corresponding entries before solving Equation (7). We conduct 500 iterations using the Adam optimizer [31] with an initial learning rate of 0.01. We report the marginal log- log-likelihood of the best model throughout the training, ranked first by Hamming Distance and then by the marginal log-likelihood (estimated with repeats). As done in Section 4.1, Precision, Recall, and Hamming Distance utilized to evaluate the permutation matrices obtained from the best model.
For comparison, we include: 1) Naive [43], which does not enforce that P is a permutation matrix and instead normalizes each row using the softmax function; 2) Gumbel-Sinkhorr [49], introducing Gumbel noise for re- p-parameterizationn before the Sinkhorn operator; and 3) 0T4P, our proposed method using the re- pe-paamtterization trick, with different temperature parameters. Each experiment conducted five times, and the results are presented in Tables 2 and 5. We observe that Naive fails to produce any meaningful solutions, and scenario (Known 5%). In contrast, OT4P consistently identifies the optimal permutation, except for 0T4P (r = 0.7), which achieves suboptimal results in the Known 5% setting. One possible reason why OT4P performs better is that the orthogonal group ( ("(n-1)) has lower dimension than the Birkhoff polytope ((n 1)²). This lower dimensionality makes the randomness simulated by the noise more effective in exploring latent permutations.
performs poorly in the more challenging
Table 2: Marginal
and Precision (%) of algorithms for inferring neuron identities
across different proportions of known neurons.
Known 5%
Known 10%
Known 20%
Algorithm
E Elogp(Y (t)
Precision (1)
E [lgg((PP)) (t)
Precision (1)
E log p(Y P) (1)
Precision (t)
Xaive
-340 +-4.4
8,900 #7.85
-2917 #226
29. #17.2
1100 #530
78. 40 #12.8
Gumbel Sinkhorn
-2256 =874
62.08 #160
-239.8 111
98.16 11.05
-14.88 #27.1
99.84 #0.358
OT&P 0.3)
-130.9 =10.9
100.0 20.00
-17.55 #10.1
100.0 #0.00
-22..7 #1100
100.0 20.00
0T4P (7 0.5)
161.0 236.8
100.0 20.00
1449. 435.0
100.0 40.00
-148.2 #27.6
100.0 20.00
0Т4Р (7 = 0.7)
-829.3 1:31
74.16 235.9
-183.1 106.2
100.0 13.00
-171.8 2.10.3
100.0 20.00
4.3 Solving permutation synchronization
In the third experiment, we aim to explore the effectiveness of our proposed 0T4P on large-scale problems. We specifically focus on the permutation synchronization problem [51, 47, 5], which tries to improve matching across multiple objects. Consider objects with n points each, and let the permutation matrix j(i E P,, to represent the correspondence between points in objects i and

---

Car
Duck
100.0
100.0
F-ccare (%)
90.0-
F-score (%)
99.0
Reg
OT4P(T 0.3)
OrthReg
0T4P(T=
80.0
RiemanBirk
OT4P(T 0.7)
Sinkhorn
70.0
70.0
30
30
Instance Size Face
Instance Size
Motorbike
Winehottle
100.0
100.0
F-score 1%))
F-score (%)
95.0
95.0
F-score
90.0
90.0
60.0
85.0
40.0
80.0
25
75 Instance Size
50
100
20
30
40
60
Instance Size
Instance Size
Figure 3: F-scores (%) for different algorithms on the WILLOW-OhjecCllas dataset, where the size of permutation synchronization problem instances varies along the horizontal axis.
Permutation synchronization seeks to identify the underlying permutations Pt(i [K]) such that P(i,5) - P.P.j for all i,j E [k]. which can be expressed as the following optimization problem:
min Σ - (P.EP,)
(18)
4
We select baselines: 1) Reg optimizes in Euclidean space with a regularization term E,(E,Puy-1) that encourages each column to sum 1. 2) OrthReg [72] optimizes over the special orthogonal group, using regularization term trace [P- P @ P)) (G is element-wise product) to force orthogonal matrices to converge permutation matrices. 3) RiemanBirk [6] optimizes on Birkhoff polytope utilizing Riemannian gradient descent. 4) Sinkhorn [49] optimizes in the vicinity of Birkhoff polytope, using the Sinkhorn operator to adjust positive matrices into approximate doubly stochastic matrices. All algorithms employ the Adam optimizer for 100 iterations, with Ri RiemanBirk utilizing Riemannian Adam [4, 34]. The initial learning rates are tuned within the set (0.1, 0.01, 0.001, 0.00013.
We the WILLOW-ObjecCCla, dataset [9] to generate problem instances (see Appendix F.4 for more details) and utilize the F-score to evaluate the alignment between the flattened permutation matrices and the ground truth. Each experiment is conducted five times, and the results are shown in Figure 3. Ri RiemanBrrk and Sinkhorn demonstrate poorer performance. A primary reason is that both methods are based on Birkhoff polytope to relax permutations, leading to unreliable local minima and preventing optimal solutions. Benefiting from the potential advantages offered by the orthogonal group, OrthReg generally produces competitive results. However, due to the instability of its regularization term, OrthReg sometimes underperforms, which may necessitate careful adjustment of the regularization coefficient for each class. In contrast, our proposed OT4P consistently outperforms other methods and demonstrates robustness to variations in the hyperparameter
5 Conclusion
In this paper, we present novel differentiable transformation, 0T4P, designed for relaxing permuta- tion matrices over the orthogonal group. This method is characterized by its flexibility, simplicity, and scalability. 0Т4P utilized to parametrize the relaxation of permutation matrices, with advantages of not altering the original problem, not complicating the original problem, and an efficient optimization process. By deriving gradient estimator, OT4P further provides an efficient tool for stochastic optimization over latent permutations. Extensive experiments show that OT4P achieves competitive results optimization problems and probabilistic tasks compared to relaxation methods on Birkhoff polytope. We believe our elementary work is a significant step toward relaxing permutations onto the orthogonal group. Please see Appendix A for further discussion, including related work, limitations, and broader impacts.
10

---

Acknowledgments and Disclosure of Funding
This work is supported by the National Key Research and Development Program of China (No. 2020YFA0714103).
References
[1] Ryan Prescott Adams and Richard S Zemel. Ranking via sinkhorn propagation. arXiv preprint 100iv: 1925, 2011.
[2] Samuel Ainsworth, Jonathan Hayase, and Siddhartha Srinivasa. Git re-basin: Merging models modulo permutation symmetries. The Eleventh International Conference on Learning Representations, 2023. URL https:// wtt. orumm wawrrrmmmddmdmmmmaa 1d=CQsmMYm1P5T..
[3] Awad Al-Mohy and Nicholas Higham. new scaling and squaring algorithm for the matrix exponential. SIAM Journal on Matrix Analysis and Applications, 31(3):970-99) 989,, 2010.
[4] Gary Becigneul and Octavian-Fugen Ganea. Riemannian adaptive optimization methods. In International Conference on Learning Representations, 2019. URL https://openreviee net/forum? 0997..
[5] Florian Bernard, Daniel Cremers, and Johan Thunberg. Sparse quadratic optimisation over the stiefel manifold with application to permutation synchronisation. Advances in Neural Information Processing Systems, 021222566222666 2021.
[6] Tolga Birdal and Umut Simsekli. Probabilistic permutation synchronization using the rie- mannian structure of the birkhoff polytope. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11105-11116, 2019.
[7] David M Blei, Alp Kucukelbir, and Jon McAuliffe. Variational inference: review for statisticians. Journal of the American statistical Association, 112(518):859-8777 2017.
[8] Rainer E Burkard, Stefan E Karisch, and Franz Rendl. Qaplib-a quadratic assignment problem library. Journal of Global optimization, 10:391 -039, 1997.
[9] Minsu Cho, Karteek Alahari, and Jean Ponce. Learning graphs match. In Proceedings of the IEEE International Conference on Computer Vision, pages 25-32, 2013.
[10] Jia Deng, Wei Dong. Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hicrarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages
leee, 2009.
[11] Zvi Drezner. The quadratic assignment problem. Location science, pages 345-363, 2015.
[12] Hannah Dröge, Zorah Lähner, Yuval Bahat, Onofre Martorell Nadal, Felix Heide, and Michael Möller. Kissing to find a match: Efficient low-rank permutation representation. Advances in Neural Information Processing Systems, 36, 2024.
[13] Rahim Entezari, Hanie Sedghi, Olga Saukh, and Behnam Neyshabur. The role of permutation invariance in linear mode connectivity of neural networks. In International Conference on Learning Representations, 2022. URL
d wiiiiiiiidigiiiii....i ggytemkL.
[14] Luca Falorsi, Pim de Haan, Tim R Davidson, and Patrick Forré. Reparameterizing distributions on lie groups. In The 22nd International Conference on Artificial Intelligence and Statistics, pages -3433.25.. PMLR, 2019.
[15] Marcelo Fiori, Pablo Sprechmann, Joshua Vogelstein, Pablo Musé, and Guillermo Sapiro. Robust multimodal graph matching: Sparse coding meets graph matching. Advances in neural information processing systems, 26, 2013.
[16] Matteo Fischetti, Michele Monaci, and Domenico Salvagnin. Three ideas for the quadratic assignment problem. Operations research, 60(4):954-964 2012.

---

[17] Fajwel Fogel, Rodolphe Jenatton, Francis Bach, and Alexandre d' Aspremont. Convex re- laxations for permutation problems. Advances in neural information processing systems, 26, 2013.
[18] Jean Gallier. Logarithms and square roots of real matrices existence, uniqueness and applications medical imaging. arXiv preprint arXiv:0805.0245 2011.
[19] Zheng Gong and Ying Sun. An energy-centric framework for category-free autoo--distribution node detection in graphs. In Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pages 908-919, 2024.
[20] Aditya Grover, Eric Wang. Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations. In International Conference on Learning Representations, 2019. URL https: http//pperrvvieeeeee eview www/ httt:/forommmidileeeeeee eSS3CcKX.
[21] Brian C Hall. Lie groups, Lie algebras. and representations. Springer, 2013.
[22] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and paltern recognition, pages 770-778, 2016.
[23] Nicholas J Higham. Functions of matrices: theory and computation. SIAM, 2008.
[24] Nicholas Higham and Lijing Lin. A schur-padé algorithm for fractional powers of matrix. SIAM Journal on Matrix Analysis and Applications, 32(3): 1056-1078, 2011.
[25] Einar Hille. On roots and logarithms of elements of a complex banach algebra. Mathematische Annalen, 136(1):46-55) 57, 1958.
[26] Bo Jiang, Ya-Feng Liu, and Zaiwen Wen. L_p-norm regularization algorithms for optimization over permutation matrices. SIAM Journal on Optimization, 26(4):2284 2313, 2016.
[27] Bo Jiang, Jin Tang, Chris Ding, and Bin Luo. Nonnegative orthogonal graph matching. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
[28] Ivan Karpukhin and Andrey Savchenko. Detpp: Leveraging object detection for robust long- horizon event prediction. arXiv preprint arXiv:2408.13112 13131, 2024.
[29] Ivan Karpukhin, Foma Shipilov, and Andrey Savchenko. Hotpp benchmark: Are good at the long horizon events forecasting? arXiv preprint arXiv:2406. 14341, 2024.
[30] Sunyoung Kim, Masakazu Kojima, and Kim-Chuan Toh. A lagrangian-dni relaxation: fast method for computing tight lower bounds for class of quadratic optimization problems. Mathematical Programming, 156(1):161-187 2016.
[31] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.69%0 12.6000, 2014.
[32] Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114, 2013.
[33] Virginia Klema and Alan Laub. The singular value decomposition: Its computation and some applications. IEEE Transactions on automatic control, 2642)1164-17,, 1980.
[34] Max Kochurov, Rasul Karimov, and Serge Kozlukov. Geoopt: Riemannian optimization in pytorch, 2020.
[35] Vignesh Kothapalli. Neural collapse: review on modelling principles and generalization. arXiv preprint arXiv:2206.04041, 2022.
[36] Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83-99) 1955.
[37] Eugene I. Lawler. The quadratic assignment problem. Management science, (4):586-559, 1963.
12

---

[38] John M Lee. Introduction to Riemannian manifolds, volume 2. Springer, 2018.
[39] Mario Lezcano Casado. Trivializations for gradient- optimization on manifolds. Advances in Neural Information Processing Systems, 32, 2019.
[40] Mario Lezcano-Casade and David MartueezRubbo. Cheap orthogonal constraints in neural networks: A simple parametrization of the orthogonal and unitary group. In International Conference Machine Learning, pages
PMLR, 2019.
[41] Innar Liiv. Seriation and matrix reordering methods: An historical overview. Statistical Analysis and Data Mining: The ASA Data Science Journal, 3(2):70-9) 91, 2010.
[42] Cong Han Lim and Stephen Wright. Beyond the birkhoff polytope: Convex relaxations for vector permutation problems. Advances in neural information processing systems, 27, 2014.
[43] Scott Linderman, Gonzalo Mena, Hal Cooper, Liam Paninski, and John Cunningham. Repa- rameterizing the birkhoff polytope for variational permutation inference. In International Conference Artificial Intelligence and Statistics, pages 1618-1627. PMLR, 2018.
[44] Eliane Maria Loiola, Nair Maria Maia De Abreu, Paulo Oswaldo Boaventura-Netto, Peter Hahn, and Tania Querido. A survey for the quadratic assignment problem. European journal of operational research, 176(2):657-690, 2007.
[45] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint 1rXiv:1711.051000 2017.
[46] Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. arXiv preprint arXiv: /6/ 1.07/ 2016.
[47] Elconora Maset, Federica Arrigoni, and Andrea Fusiello. Practical and efficient multi-view matching. In Proceedings of the IEEE International Conference Computer Vision, pages 1568-4576, 2017.
[48] Estelle Massart and Vinayak Abrol. Coordinate descent on the orthogonal group for recurrent neural network training. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7744-7751, 2022.
[49] Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning latent permuta- tions with gumbel-sinkhom networks. In International Conference on Learning Representations, 2018. URL https : /ttp///ppee//eeeeeee/ee/ee/eeeee wwt. net//oorurFdd=Byy330000
[50] Shakir Mohamed, Mihaela Rosca, Michael Figurnov, and Andriy Mnih. Monte carlo gradient estimation in machine learning. Journal of Machine Learning Research, 21(132):1-62, 2020.
[51] Deepti Pachauri, Risi Kondor, and Vikas Singh. Solving the multi-way matching problem by permutation synchronization. Advances in neural information processing systems, 26, 2013.
[52] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, ligh-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[53] Gao Peifeng, Qianqian Xu, Peisong Wen, Zhiyong Yang, Huiyang Shao, and Qingming Huang. Feature directions matter: I Long-tailed learning via rotated balanced representation. In Interna- tional Conference on Machine Learning, pages 27542-27563 PMLR, 2023.
[54] Fidel A Guerrero Peña, Heitor Rapela Medeiros, Thomas Dubail, Masih Aminbeidokhti, Eric Granger, and Marco Pedersoli. Re-basin via implicit sinkhorn differentiation. In Proceedings of the IEEE/VF Conference on Computer Vision and Pattern Recognition, pages 20237-20244 2023.
[55] Janez Povh. Semidefinite approximations for quadratic programs over orthogonal matrices. Journal of Global Optimization, 48(3):447-463, 2010.
13

---

[56] Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and upproximate inference deep generative models, In International conference on machine learning, pages 1278-1286. PMIR, 2014.
[57] Simone Rossi, Ankit Singh, and Thomas Hannagan. On permutation symmetries in bayesian neural network posteriors: a variational perspective. Advances in Neural Information Processing Systems, 36, 2024.
[58] Sebastian Ruder. An overview of gradient descent optimization algorithms. arXiv preprint (609.04/0004477 2016.
[59] Rodrigo Santa Cruz, Basura Fernando, Anoop Cherian, and Stephen Gould. Deeppermnet: Visual permutation learning. In Proceedings of the IEEE Conference on Computer Vision and Pattem Recognition, pages 3949-3957, 2017.
[60] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 1rXiv:1409.155, 2014.
[61] Richard Sinkhorn. A relationship between arbitrary positive matrices and doubly stochastic matrices. The annals of mathematical statistics, 35(2):876-879, 1964.
[62] Ying Sun, Hengshu Zhu, Chuan Qin, Fuzhen Zhuang, Qing Hc, and Hui Xiong. Discerning decision-making process of deep neural networks with hierarchical voting transformation. Advances in Neural Information Processing Systems, 34:17221-17234 2021.
[63] Ying Sun, Fuzhen Zhuang, Hengshu Zhu, Qing He, and Hui Xiong. Cost-effective and interpretable job skill recommendation with deep reinforcement learning. In Proceedings of the Web Conference 2021, pages 3827-3838, 2021.
[64] Ying Sun, Hengshu Zhu, Lu Wang, Le Zhang, and Hui Xiong. Large-scale online job search behaviors reveal labor market shifts amid covid-19. Nature Cities, 102):150-163, 2024.
[65] David M Tate and Alice E Smith. A genetic approach to the quadratic assignment problem. Computers Operations Research, (2(1):73-83, 1995.
[66] Lav R Varshney, Beth L Chen, Eric Paniagua, David Hall, and Dmitri B Chklovskii. Structural properties of the caenorhabditis elegans neuronal network. PLoS computational biology, 7(2): e1001066, 2011.
[67] Chao Wang, Hengshu Zhu, Chen Zhu, Chuan Qin, and Hui Xiong. Setrank: setwise bayesian approach for collaborative ranking from implicit feedback. In Proceedings of the aaai conference on artificial intelligence, volume 34, pages 6127-6136, 2020.
[68] Chao Wang, Hengshu Zhu, Chen Zhu, Chuan Qin, Enhong Chen, and Hui Xiong. Setrank: A setwise bayesian approach for collaborative ranking in recommender system. ACM Transactions on Information Systems, 42(2):1 2023.
[69] Runzhong Wang, Junchi Yan, and Xiaokang Yang. Neural graph matching network: Learn- ing lawler's 's quadratic assignment problem with extension to hypergraph and multiple-graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(9):5261-522 2021.
[70] Tianxin Wang, Fuzhen Zhuang, Ying Sun, Xiangliang Zhang, Leyu Lin, Feng Xia, Lei He, and Qing He. Adaptively sharing multi-levels of distributed representations in multi-task learning. Information Sciences, 591:226-234, 2022.
[71] Junchi Yan, Xu-Cheng Yin, Weiyao Lin, Cheng Deng, Hongyuan Zha, and Xiaokang Yang. short survey of recent advances in graph matching. Proceedings of the 2016 ACM on international conference multimedia retrieval, pages 167-174, 2016.
[72] Michael M Zavlanos and George Pappas. A dynamical systems approach to weighted graph matching. Automatica, 44(11)2211-28244 2008.
14

---

[73] He Zhang, Ying Sun, Weiyu Guo, Yafei Liu, Haonan Lu, Xiaodong Lin, and Hui Xiong. Inter- active interior design recommendation via coarse-to-fins multimodal reinforcement learning. In Proceedings of the 31st ACM International Conference Multimedia, pages 6472-6480, 2023.
[74] Yuting Zhang, Ying Sun, Fuzhen Zhuang, Yongchun Zhu, Zhulin An, and Yongjun Xu. Triple dual learning for opinion- based explainable recommendation, ACM Transactions on Information Systems, 42(3):1-22 2023.
[75] Hengshu Zhu, Hui Xiong, Yong Ge, and Enhong Chen. Discovery of ranking fraud for mobile apps. IEEE Transactions on knowledge and data engineering, 27(1):74-77, 2014.
15

---

A
Additional discussions
A.1 Related work
Optimization over permutations is commonly encountered in problems involving bijections between two sets of equal size [17, 42, 15, 12]. From theoretical perspective, well-known special case is the quadratic assignment problem, which has been drawing researchers' attention since its first formulation [37, 44]. In practical terms, optimization over permutations is also arises extensively in various machine learning tasks, including ranking [20, 75, 67, 68], matching [2]. tracking [43], recommendation [63, 74, 73], etc. Since our interest lies in addressing generie problems defined on permutation matrices, we will not discuss theoretical approaches for specific issues [11], such as exact methods [16]. lower bound methods [30], and vertex-based methods [65].
Previous studies have proposed relaxing the permutation matrices to continuous spaces, including the Birkhoff polytope [17, 15, 42] and orthogonal group [72, 55, 27]. The Birkhoff polytope is the convex hull of all permutation matrices, while the orthogonal group serves as a natural embedding of permutation matrices in a differentiable manifold. Such relaxation techniques have proven to be very powerful, with successful applications to various problems such as seriation [1, 17, 41] and graph matching [15, 69, 71]. Most of the methods mentioned above rely the explicit penalty term and are challenging to extend to probabilistic scenarios.
Recently, relaxation methods involving the Birkhoff polytope have made significant advancements, particularly penalty-free optimization and probabilistic inference. For instance, Linderman et al. [43] propose a rounding transformation regulated by temperature parameter, which rounds matrices towards the vertices of the Birkhoff polytope, i.c. permutation matrices. Similarly, Mena et al. [49] utilize the Sinkhorn operator [61] to transform matrices into the Birkhoff polytope, bringing them closer to permutation matrices under temperature control. Additionally, Grover et al. [20] suggest mapping vectors unimodal row stochastic matrices, a subset of the Birkhoff polytope that removes the requirement of every column sum being equal to 1. These works not only avoid introducing penalty terms but also provide probabilistic inference. However, providing equally effective relaxation methods within orthogonal groups remains an unexplored area. As mentioned in the main text, relaxation onto the orthogonal group possesses unique potential advantages. Therefore, our elementary work aims to address this gap.
A.2 Limitations
The first concerns the computational efficiency of OT4P when dealing with very large matrices (n > 1000), as the cost of eigendecomposition becomes prohibitive. This could benefit from efficient implementations of eigendecomposition on GPUs. The second limitation involves the noise distribution used for re- re-parameterization in 0T4P, which may not equally capture the latent permutation matrices. This can be improved by more carefully designing the noise distribution under the characteristics of the orthogonal group. The third challenge relates to the boundary issues in representing permutation matrices, hindering OT4P building block of deep neural networks. Indeed, such integration assumes all permutation matrices lie within 24. We believe that an ideal (analytical) solution can be devised to relocate all permutation matrices back into U, given that they constitute finite discrete set within the orthogonal group of order π.
A.3 Broader impacts
This work presents novel differentiable transformation for relaxing permutation matrices onto the orthogonal group, which enables gradient-based (stochastic) optimization of problems involving permutation matrices. Given the theoretical nature of our work, we have not identified any direct ethical concerns or negative socictal impacts related our research. Our study may have the broader impacts for a variety of areas of machine learning, such as deep learning [62], data mining [64]. Similar impacts were observed in multi-task learning [70] and graph learning [19].
B Riemannian Geometry and Lie Group
This section briefly summarizes the key concepts of Riemannian geometry and the Lie group theory involved. For a comprehensive understanding, recommend the standard textbooks Introduction to
16

---

Riemannian manifolds [38] and Lie groups, Lie algebras, and representations [21]. Additionally, the analysis of matrix functions can be found in Functions of matrices: theory and computation [23].
An n-dimensional manifold M is a topological space that can be locally approximated by the Euclidean space R At each point vector space, serving as a first-order local approximation of M around I. The Riemannian metric collection m := {m x 3 of inner products mz( (:>- T x T&M + R. induces a norm I1-1la T.M + R defined by ||yl|a := v mm (v. y). The length L(y) of a smooth curve y: [a, b] + MM is defined as L(>) = S ( dt. The distance d(z,, y) is set the infimum of the lengths of all smooth curves between x and y M. A geodesic is smooth curve y [a,b) bj - M that the tangent vector 7(!) parallel transported along the curve y w.r.t. the Levi-Civita connection, 0 for all t [a. b). With the basic concept of manifolds established, we present
M, there exists tangent space T.MM, an n-dimensional
i.., V (2' the definitions of isomorphism, diffeomorphism, and isometry.
Definition 1 (Vector space isomorphism). The vector spaces X' and Y' are called to be isomorphic if there exists a bijection a: X + y that preserves addition and scalar multiplication.
Definition (Diffccomorphism). Given two differentiable manifolds M and N, differentiable map M + N is diffcomorphism if it is bijection and its inverse a is differentiable as well.
Definition 3 (Isometry). Given two metric spaces (X, mx) and (),my)) map a X + y is called an isometry if mix m (#1, x2) my(a((z)) (x(22) for all points x1, E X.
Lie group G is a differentiable manifold equipped with differentiable group multiplication and inverse operations. The tangent space at the identity e is known as the Lie algebra of G. denoted as g := T.G. For all g E G. there exist diffeomorphisms given by the left translation Lg := gz (Vx E G) and the right translation (z)= ;= xy (Vz E G). The left and right translations lead to a vector space isomorphism that relates the tangent space to the Lie algebra. For left translation Ly the mapping (dLg)e == g + TgG maps elements of the Lie algebra into the tangent space T,G, with its inverse mapping (dLg-1), )g := TT g. Similarly, for right translation Ry. there is mapping (dRy)e := g + G.G and its inverse (dR,- := G,G + g. A Riemannian metric m the Lie group G is said to be left-invariant tright-invarint)) if it renders each left (right) translation an isometry. When adopting a left-invariant (right-invariant) metric the Lie group G. can associate neighborhoods of the identity e with neighborhoods of any point E G using left (right) translation, and vice versa. A metric on the Lie group that is both left and right invariant is termed bi-invariant metric. It is worth noting that compact Lie groups always possess the bi-invariant metric.
The Lie group we are interested in is the orthogonal group O(n), consisting of all n x orthogonal matrices O satisfying OTO = 00T T = I. We equip (nn) with the canonical metric, which is a bi-invariant metric inherited from Rexn and defined as (A, B)F == trace( B), where (:, )F is the Frobenius inner product and trace(-) is the trace of matrix. The orthogonal group O(n) is divided into two connected components depending on the value of the determinant, +1 or 1. The connected component with determinant +1 forms a subgroup known as the special orthogonal group SO(n) == {0 E R=*= O = I, det O = +1}. The Lie algebra (n of the Lie group SO(n) comprises n x n skew-symmetric matrices, expressed as so (n) == {A E Raxx | AT=
= AA}. It is noteworthy that so(n) is vector space with dimension n(n-1) The Lie exponential expm(-), coinciding with the matrix exponential in the context of the matrix Lie group, exactly maps elements in so(n) to elements in SO(n), defined by
06 A'
expm = 1+
hd
1=1
The series in the above equation converges for all matrices A.
In general, the matrix logarithm is expected to be the inverse function of the matrix exponential, meaning the logarithm of A is the solution B to the matrix equation expm B) A. Since the complex logarithm is a multi-
function, there may be an infinite number of matrices that satisfy expm B) = A. If A has no eigenvalues on R6 = (xr E IR < 0), then there exists unique logarithm called the principal logarithm, denoted as logm( All eigenvalues À of logm( A) satisfy - Im À < Assuming convergence of the series, the matrix logarithm logm(-) can be
17

---

defined by Taylor series expansion as follows:
Togm(A) = (-1)k+] (A-1)6
The series in the above equation converges whenever ||A /||F < where |||||= V A/r represents the Frobenius norm induced by the Frobenius inner product.
Define the V = {A R= Im (AA) (-T, x), vk} as the set of all matrices A E R for which all eigenvalues ÅS satisfies -π < Im 0 ग. Let W := {A E R=** \x<(A) & Bg Vk] denote the set all matrices [R*X" without non-positive real eigenvalues. Then, we can verify that (prove in Appendix G.I):
logmm (A)) = A, AA E V; expm(logm(( A)) A, AA W.
This indicates that the matrix logarithm is locally inverse function of the matrix exponential.
C Boundary issues in representation of permutation matrix
In this section, we provide an in-depth analysis of the potential adverse effects on optimization stemming from the direct application of mapping <(-) w.r.t. Equation (6). Subsequently, we show that left-multiplying the result of Equation (6) by an orthogonal matrix, as described in Step I, effectively alleviates this problem.
Since a permutation matrix must an orthogonal matrix, its eigenvalues A lie on the unit circle in the complex plane, i... A = 1. Additionally, any permutation be expressed as the product of cycles with disjoint supports. For a cycle length m, its corresponding m x m submatrix satisfies pm I, which implies that the eigenvalues of P admit the following form:
A = 2
k: 0,
m 1.
(19)
In Figure 4, visualize the eigenvalues corre- sponding to cycles of lengths 2, 3, 4, and 5. It clear that cycles of even length consistently possess an eigenvalue of -1. Notably, the eigen- values of permutation matrix are composed of those from the submatrices corresponding to its contained cycles. Therefore, many permutation matrices have 1 as one of their eigenvalues.
Cyce length
1.0
Cydle
Cycle lergth
Cyde lengt
0.5
Imaginary
0.0
As elucidated Lezcano-Casado and Martinez- Rubio [40], the representation in 4 == {A E AT) E (- T). Vk) of permutation matrices with an eigenvalue of -1 precisely lies on the boundary U. For prob- lems where these permutation matrices serve as the optimal solution, may cause the opti- mization path to deviate from U. A straight- forward method is to left-multiply the result of Equation (6) by random orthogonal matrix B (O(n), thereby shifting the boundary of 24 to other eigenvalues. Theoretically, this left translation (O) == BO (4O E SO(n)) cre- ates diffcommrphism (O(n) that transforms the representation of the permutation matrix P in U from logm( P) to logm(B3 P).
m(m=)) Im A
-0.-
-1.0
-1.0
-0.5
0.0 0.5
1.0
Real
Figure 4: Eigenvalues corresponding to cycles of different lengths, where eigenvalues from the same cycle are connected illustrate repeated values at -1.
To validate the efficacy of the aforementioned approach, we conducted simple empirical study. Given random orthogonal matrix B with determinant of 1, randomly generate 1000 permutation
18

---

matrices P, where odd permutations are projected to (O(n) as done in Appendix D. We then estimate the probability of the eigenvalue -1 1 occurring in P and B P, respectively. We examine permutation matrices ranging dimension n from 50, Each experiment is replicated five times and the results are presented in Table 3. The findings show that the left translation Lg effectively relocates the majority of permutation matrices' representations into the interior u4.
Table 3: Probability (%) of eigenvalue -1 occurring in matrices.
dimension n
3
5
10
20
50
P B
16.34 $0.89
32.14 #1.02
51.08
+1.36
64.78
#1.16
77.48
+0.80
15.92 +1.29
16.42 +1.18
8.36
+0.67
5.94
+0.29
8.66 #:112
Remark C.I. A high-level idea involves dynamically adjusting B to ensure that the permutation matrix near the current iteration point consistently remains within the interior of U. This a special case of dynamic trivialization proposed in Lezcano Casado [39].
D Theoretical details of the odd permutation
In this section, we provide the details of handling odd permutations and focus on elucidating the underlying theory.
To deal with the case where the permutation matrix P corresponds to an odd permutation, our core idea is to find an agent, P. of P within SO(n). In this way, we may move the orthogonal matrix O E (O(n) to the vicinity of P. and then restore the result to the neighborhood of P. This idea is formalized by the following method:
1. We seek an agent of P within (O(n), which is determined by solving the optimization problem:
arg min| P- PII PeSO(n)
(20)
The analytical solution to Equation (20) is given by P = PD. where = 1, 11]) is the identity matrix with the last column multiplied by -1.
2. Given that E SO(n), we can, by substituting P with P in Equation (10), move the orthogonal matrix O SO(n) to the vicinity of P, yielding Ô.
3. By right-multiplying by DT, we map Ô the neighborhood of P. resulting Ô ŌD
We now derive the analytical solution Equation (20). By the definition of the Frobenius norm, can express:
p - P1]
= tracee PTP) + trace(P" P) - 2 trrace(P] PT P)
2n - tracee p))
The last equation uses the fact that both P and P are orthogonal matrices, i.e., trace( P) trace( PT P) = n. Considering the singular value decomposition (SVD) [33], we have P T where U and V are orthogonal matrices, and is diagonal matrix with non-negative real singular values on the diagonal. Since the orthogonal matrix singular value is 1, there exists Σ = I. By leveraging the cyclic property of the trace, have:
trace( ST P) trace (TUIVT)
(21)
trace (V U) trace(
where Z = V PTU is orthogonal matrix with del Z = -1 Hence, all elements zijj of Z satisfy |æs,yl S and Z must have an odd number of -1 eigenvalues. Notice that the trace of matrix is the sum of its elements on the main diagonal, Equation (21) is maximized when
19

---

Z = diag [1, 1, ,, 1))) Thus, the analytical solution to Equation (20) is P = (DPT) PD, where diag( (1. -13) the identity matrix with the last column multiplied by -1
Since D an orthogonal matrix, right-multillying by D becomes a right translation (D(O)= = OD (AO E ((n))- Notably, O(n) is equipped with bi-invariant metric (;))r, which implies that Rd is an isometry, linking the the neighborhoods
and its agent P. Thus, we have (AD, BD)r = (A, B)r for any A, B E ( In other words, when is moved close enough to P. O will also be sufficiently close to P.
E More discussion on Step II
Visualization. In Figure 5, we visualize the results Equation (11) the temperature parameter
varies. The first row corresponds to the even permutation, while the second row corresponds to the odd permutation. The leftmost image (r 1.0) represents the original orthogonal matrices O from Step I, and the rightmost image (r = 0.0) is the permutation matrix P that is closest to O. The temperature parameter controls how closely the resulting orthogonal matrices Ô, obtained in Step approach P. As T - 0, the resulting orthogonal matrices Ô increasingly converge to
T 1.0
T 0.7
T 0.5
T 0.3
T= 0.0.0
cvcn
0.5
0
add
-0.5
Figure 5: Visualization of the results of Equation (11) as the parameter 7 varies. At T 1.0, the matrices original orthogonal matrices; 0.0, they are the permutation matrices closest to original orthogonal matrices.
Rounding to permutation matrix. Generally, the Hungarian algorithm requires cost matrix with- out negative values, which is unsuitable for orthogonal matrices that may contain negative elements. To implement the rounding w.r.. Equation (7) from the orthogonal matrix O, we first eliminate negative elements by subtracting the minimum element found within O, ie., O min(O). This approach is justified by the fact that arg max (P, O)F arg max, (P, min(O))F. Subsequent to this adjustment, we employ the Hungarian algorithm, available in existing libraries, to round (O) the closest permutation matrix.
Computational costs. The primary computational costs of the proposed DT4P arise from solving the linear assignment problem and performing eigendecomposition, both which typically scale with (n33). Numerous efforts have been made to accelerate these computations through parallel implementations on GPUs. We have employed existing implementations, specifically torch-linear- assignment [28, 29] and torch. linalliinalg.cig [52].
20

---

F Experimental details
E. Reproducibility and compute resources
To enhance the reproducibility, we provide a comprehensive overview of the experiments in Appen- dices F.2 to F,4, including but not limited to data generation, hyperparameters, evaluation procedures. For all experiments, we repeat the results using five different random seeds: 2021, 2022, 2023, 2024, and 2025. The core code has been released at https //g/tttttt/////// com wtt./coom/m////ee Yemingguu98/0044P
We conducted the experiments (Appendices F.2 and F.3) using a single NVIDIA A800, where the runtime environment was Python=3.10, CUDA=11.7, and PyTorch=2.01. The experiments in Section 4.1 took approximately 15 hours, while those Section 4.2 consumed another 15 hours. This estimate does not include the time spent on hyperparameter search or other experiments conducted during the research process.
E.2 Finding mode connectivity
Steup. We investigate various network architectures for Equation (17), including 5-layer MLP [54], VGG11 [60], and ResNet18 8 [22] For MLP5, both input and output are set 1, with each of the four hidden layers having dimension of 10, and the hyperbolic tangent serves the activation function. The model weights of MI.P5 are initialized randomly, while VGG11 and ResNet18 are derived from the official pre-trained models in Py Torch [52]. We minimize the loss corresponding to Equation (17) using A [45] with an initial learning rate of and a maximum of 500 iterations. Following Peña et al. [54], we adopt early stopping strategy upon finding the optimal permutation matrices.
Baseline. We take Weight Matching [2] and Sinkhorn [54] baselines. Weight Matching a method specifically designed for addressing Equation (17), which goes through each layer and greedily selects its best permutation matrix P.. We limit the maximum number traversal rounds to 10. Sinkhorn relaxes permutation matrices to the vicinity of the Birkhoff polytope utilizing the Sinkhorn operator [61, 49], solving Equation (17) in a differentiable fashion. The Sinkhorn operator undergoes 20 iterations, with the temperature parameter set to 0.5.
During the evaluation phase, we round the matrices obtained from Sinkhorn and OT4P to permutation matrices using Equation (7). We employ the f--Distance, |00 - π (0g)]l1. to measure the difference in weights with the target network. In addition, we flatten the permutation matrices and evaluate their alignment with the ground truth using Precision, Recall, and Hamming Distance.
Evaluation.
Table 4: Recall (%) and Hamming Distance of algorithms for finding mode connectivity across different network architectures.
MLP5
VGG11
ResNer18
Algorithm
Recall (t)
Hamming (1)
Recall (f)
Hamming (4)
Recall (t)
Hamming (4)
Weight Matching
100.0 20.00
0.000 +0.00
100.0 40.00
0.000 #0.00
99.97
#0.00
1.600 #3.58
Sinkhorn
100.0 20.00
0.000 +0.00
63.08 +3.14
2032 =173
95.56 #:
255.6 +50.8
OT4P (r 0.3)
100.0 20.00
0.000 1:000
100.0 40.00
0.000
20.00
100.0
+0.00
0.000 4:000
OT4P (r 0.5)
100.0 20.00
0.000
+:000
99.99 40.00
0.800
41.79
100.0
=0.00
0.000 #0.00
OT4P (F = 0.7)
100.0 20.00
0.000 +0.00
100.0 40.00
0.000 +0.00
100.0 =0.00
0.000 #0.00
F3 Inferring neuron identities
Setup. Following the methodology in Linderman et al. [43], we generate parameters A. W, and P with n = 250. Specifically, we randomly generate a binary upper triangular matrix A E (0, 1nxn and its symmetric version A A + A as the adjacency matrix. Parameter W is sampled from Gaussian distribution (00 1) according to the sparse sparsity defined by A. The permutation matrix P is randomly sampled from a uniform distribution. We generate 1000 samples according to Y, P(A @ W.PTY, Y,_1 where the noise follows Gaussian distribution (0, 0.01).
21

---

We formulate tasks of varying difficulty depending on the different proportions of known neurons [43]. Conceiving constraint matrix R=x* where all elements are initialized to I. If we ascertain that the reference neuron i corresponds to the observed neuron j. then set all elements to 0 in the i-th row and j-th except for Ct.j Equation (22) provides a simple example, where we know that the observed neuron 1 (or 3) corresponds to the reference neuron 2 (or 5).
1
1
0
0
0
0
1
0
1
1
1
1
1
1
1
0
know (1.2)
know (3.5)
1
1
1
1 1
1
0
0
0 1
(22)
1
1
1
1
1 1
1
0
1
1
1
1 1 1
1
0
This modeling decision significantly reduces the number of latent permutations that need to be inferred. The constraint matrix C' is enforced by zeroing corresponding entries, where for Naive it is before row normalization, for Gumbel-Sinkher Sinkhorn it is before the Sinkhorn operator, and for 0T4P is before solving Equation (7).
Baseline. We compare Naive [43] and -iibel-Sinnhon [49]. Naive does not enforce P be permutation matrix but instead normalizes each row using the softmax function. an extension of the Gumbel-Softmax [26, 46] method for permutations, introduces Gumbel noise for re- e-paaammttrizatiinn before the Sinkhorn operator. Both Naive and our OT4P use the stand Gaussian noise for re- re-parameterization. All methods estimate the gradient of the marginal log-likelihood (P-g((P:) log PY))P) with repeats.
Evaluation. We retain the best model throughout training, ranked first by Hamming Distance and then by the marginal log-likelihooo (estimated with 5 repeats). We report the marginal log- -ggliikl of the best model. As done Section 4.1, Precision, Recall, and Hamming Distance are utilized to evaluate the permutation matrices obtained from the best model without adding noise.
Table 5: Recall (%) and Hamming Distance of algorithms for inferring neuron identities across different proportions of known neurons.
Known 5%
Known 10%
Known 20%
Algorithm
Recall (t)
Hamming (4)
Recall (t)
Hamming (4)
Recall (t)
Hamming (4)
Naive
8.960 27.85
455.2 1:39.3
29.68
351.6 #66.0
78.40
1:2.8
108.0 0
Sinkhorn
62.08 #16.0
189.6 479.8
98.16
9.200 29.76
99.84 #0.358
0.800
OT4P (r = 0.3)
100.0 =0.00
0.000 1: 00
100.0 20.00
0.000 20.00
100.0 =0.00
0.000 ::0 00
OT4P (r = 0.5)
100.0 00.00
0,000 1:0 00
100.0 10.00
0.000 10.00
100.0 1:000
0.000 1:0 00
0T4P (T 0.7)
74.16 =35.9
129.2 1880
100.0 #0.00
0.000 +0.00
100.0 #0.00
0.000 +0.00
F.4 Solving permutation synchronization
Setup. We use the WILLOW- WILLOo-ObjecCClass dataset [9] to generate problem instances. The WILLOW-
ObjectClass dataset comprises images of five object classes, each containing 10 equal key points of at least 40 images. For each image, we extract interpolated features from the relu4 2 and relu5 / layers through pre-trained VGG16 [60] model on ImageNet [10]. The initial pairwise correspondences are established by applying the Hungarian algorithm [36] to the distance matrices of features. We increase the number of objectives, k, from 20 to the its largest value (multiples of 5) for each object class.
We also take the & -Distance to assess the 'permutationness' of the final matrix. Specifically, we round the matrix P. returned by the algorithms, its closest permutation matrix P. and then calculate the -iDisttncce between P and P. Table lists the results for the problem instances corresponding to the largest size (multiples of 5) in each object class. We observe that the relaxation extent of Sinkhorn unstable. Unlike them, OT4P consistently maintains smaller distances in almost all cases and exhibits positive correlation with changes in the hyperparameter
Permutationness.
22

---

Table 6: f fi-Distance between the matrix returned by the algorithms and its closest permutation matrix. In each object class, we select the largest problem instance size that is a multiple of five.
Dataset
Reg
OrthReg
RiemanBirk
Sinkhorn
DT4P
0.3)
0T4P 0.5)
DT4P 0.7)
Car
13.131005
3.20
10.9120.4
6.1010.08
2.301004
3.6710.16
4.68_0.09
Duck
12. 61.0..
3.26
10.85=a.m
5.65
2.05+0.02
3.1540.17
4.29-0.08
Face
40
3.0110.43
8.0010.45
0.0010.02
0.6110.01
0.9810.02
1.34_0001
Motorbike
15.17
3.37
13.30=0.11
10.86
3.10
4.76:1.29
5.90=0.18
Winchort
11.4420.41
3.17+0.31
9.12
2.62+0.07
1.53+0.02
2.36+t0.12
2.91=0.12
Impact of Optimizers. We compare the results of different optimizers in Table 7, selecting the largest instances (multiples of 5) for each object class. Methods based on the Birkhoff polytope show notable performance improvements on most datasets when using (Riemannian) SGD. For our proposed OT4P, the choice of optimizer appears to be less critical, as it consistently outperforms other methods regardless.
Table F-scores (%) for different algorithms with various optimizers on the WILLOW-OhjeaClass dataset. In each object class, we select the largest problem instance size that is multiple of five.
Dataset
Reg
DrthReg
RiemenBirk
Sinkhora
OT4P (r = 0.3)
0T4P (r 0.5)
OT4P (r 0.7)
Car
SGD
80. 10.98:1166
78.5 78.5221.20
79.27
81. 43..00
100.0::.00
100.000.00
100.0
Adam
77. 77.48:33.1
92.76a5.u 16
72.13+3.45
82. 22.9.1..22
100.0
98.61
99.8:0.40
SGD
00.84:0.35
91.5622.4
87.1414.c9
91.49
100.0::..00
98.93
99.63
Duck
Adam
75.52u0 sa
00.01 25/21
69.8943.54
79.3220.33
100.019.00
99.37
98.71
Face
SGD
Failed
100. 000.000.00
100 020.00
100 000.0.0.00
100. 000.0
100.0s0.00
100.0=a..0
Adam
99. 00.93=0.u 12
91.10s2.77
12:
100.0s0.00
100.0
100.0=0.00
100.0=a.00
Motorbike
SGD
50.00a1
62.062
29.7612.96
55. 78
98.51
98.01
98.999
Adam
45.57=2.06
02.52 42.52
43.72
57.08
97.22
07.20=2204
99.61
Winebottle
SGD
91 31
91.51 14
91 .8.4880000
91.4421.00
98.5321.05
U8.65 73
99.972.003
Adam
90.84
91.5622
87,1444.49
91.499a..0
100.0
98. 05.9332..5
99.63:a..0
Case study. This case study aims to explore the runtime and memory efficiency of our proposed OT4P on large-scala problems. We use the CMU House [5] image sequence to generate problem instances, comprising 111 frames of a video of toy house. A total of 111 x 111 pairwise matching. with each image having 30 hand labeled landmark points, are provided in Bernard et [5]. We increase the number of objectives, k. from 20 to 110 and utilize the proposed OT4P to approximately solve Equation (18) on the NVIDIA GeForce RTX 3090. For all instances, we conduct 100 iterations using AdamW [45] with an initial learning rate of 0.1.
F-score
Runtime
Memory usage
100.0
3.00
Mermory (MB)
GT4R(T = 0.3)
F-score (%)
300
OTHNT 0.5)
99.0
Time (5)
OT4R 0.7)
OT4P(T=
OT4P
200
98.0
0.5)
OT4R(T
1.00
OT4P(T
100
97.0
20
60
80
100
20
40
80
100
20
40
80
100
Instance Size
Instance Size
Instance Size
Figure 6: F-score, runtime, and memory usage of OT4P on the CMU House, where the size of permutation synchronization problem instances varies along the horizontal axis.
We flatten the permutation matrices and evaluate their alignment with the ground truth using F-score, while also assessing the runtime and the maximum GPU memory consumption during training. Each experiment is conducted five times, and the results are depicted in Figure 6, where the size of problem instances varies along the horizontal axis. The findings indicate that OT4P can find satisfactory solutions (with F-scores exceeding 97%) in less than 4 seconds, and the memory usage is manageable. Additionally, in Figure 7, we present the matching between the first and last images for = 110, where the obtained matchings are connected (correct:
incorrect: - Overall, the
23

---

31
(a) Input
(b) OT4P (T = 0.3)
(c) 0T4P (T 0.5)
(d) OT4P (T 0.7)
Figure 7: Matching between the first and last images of the CMU House for 110, where the obtained matchings are connected (green: correct, red: incorrect).
proposed OT4P demonstrates high efficiency in both runtime and memory usage when dealing with large-scale tasks amenable to parallel processing.
F55
Licenses
We will publicly release our code under the MIT license, in accordance with community standards. The licenses for the code, data, and models used in this study are provided below. Please refer to individual links for more details.
Py Torch: BSD-style
Torchvision: BSD 3-Clause
forch-linear-asiimment Apache
sinkhorn-rebasin: MIT
SparseStiefelOpt: GNU Affero General Public
geoopt: Apache
G
Proof
In this section, we first elucidate some key properties of the matrix exponential and the matrix logarithm. Based on these, we prove Theorems and 2 in Appendix G.2. Finally, we list some essential lemmas used in the proofs.
G.1 Properties of matrix exponential and logarithm
Theorem G.1. The matrix exponential map expm(() is injective over = {A E guxn Im (A)) E (-,, Vk).
Proof. For all A, B V. our goal is prove that A B if expm (A) = expm (B).
According to Lemma G. if expm (A) = expm (B), then and commute, i.e., AB BA. In fact, this commutativity implies that the equation expm (A + B) expm (A) expm (B) holds [23].

---

Thus, we can express
expin (A) expm (B)
expm (A) expm (-B) -expm (B) expm (-B) =
expm (A B) =
The above equation shows that all eigenvalues of expm (A B) are one. Since the eigenvalues of the exponential of matrix are the exponential of its eigenvalues, the eigenvalues of A B satisfy 2mri integers m Z. However, given that A, B E V. the range Im d (A - B) restricted to (-2x, 2x)) for all k, yielding a nilpotent matrix.
0. Thus, all eigenvalues of A B are zero, which means A - B is
Recalling Lemma G.2, we know that under the exponential map, the only nilpotent matrix mapped the identity matrix the null matrix. Therefore, we conclude that B 0, which implies A = B.
This confirms that the matrix exponential map is injective within the set V, thereby completing the proof.
Theorem G.2. The matrix logarithm map logm (-) is injective over W { 2 {x $ : Vk}, and (ogm(() V.
Proof. We first prove that if A E W. then B = logmn (A) E V.
Assume A E W with eigenvalues AE pxe where Pk > and 0g are real number. As shown in Gallier [18], the complex eigenvalues of B = logm (A) appear only for real Jordan blocks:
(log(ps) -0
log(pk)
where the eigenvalues are given by log(p:) ) + i0,. Since A has eigenvalues B it follows that 0g E (-T, T for all Thus, for any A E W, we have logm(4 A) E V, that is, [ogm(W) S V.
Recall that the matrix logarithm is defined with Theorem and noting that logmn(A) E V, then such a logarithm is unique. This proves that the matrix logarithm map is injective over V and completes the proof.
solution to the equation expm (B) A. Coupled
Corollary G.3. The image expm (V) V by the matrix exponential expm (+) is the set W and the mapping expm: V W a diffeomorphism.
Proof. By Theorem G.2, it is clear that W C expm (V). We now prove expm (V) S W.
For any matrix A V, the eigenvalues have the form ib, where and b are real number and -T < b π. Then, the eigenvalues of expm (A) take the form e = e eb Since e never lies on R- expm (A) has no non non-positive real eigenvalues, i.e., expm (A) E W. The arbitrariness of A leads to the conclusion of expm (V) C W.
The diffeomorphism results directly from Theorems G.I and G.2.
G.2 Proof of Theorems 1 and 2
Theorem 1s, The mapping s(-) is differentiable, surjective, and it is injective on the domain U (A E F min-1) Im A (A-AA (~R,T), T), wk} with Xx(-) the eigenvalues. Additionally, the ser 5O(n) \ ((U) has a zero Lebesgue measure in SO(n).
Proof. It trivial that 6(-) is differentiable.
We start by establishing that o(-) surjective. is worth mentioning that the conclusion of Lemma G.3 is applicable to SO(n) due to it being connected and compact. However, we pro- vide straightforward proof based on Theorem G.I. Indeed, any orthogonal matrix O E SO(n)
can be diagonalized into block-diag Mock-diagonal matrix with diagonal blocks consisting of 2 x rotation matrices:
cos sin 0 cos 0
sin 0
25

---

where O (-T,, π]] represents the rotation angle. For SO + 1). an extra block containing single 1 exists. Correspondigly, we have a skew-symmetrie matrix B sa(n) satisfying expm (B) O, which is also block-diagonal matrix with diagonal blocks of the form:
(-) 0)
There is an additional block with a single 0 on s2(2n + 1). As a result, for all orthogonal matrices O SO(n), we can surely find skew-symmetric matrix B E so(n) such that expm (B) = O. Given that sn(n) is isomorphism to the vector space IR باياي this confirms that Φ(-) is surjective. Regarding ((-) is injective on the domain 44 can be derived from Theorem G.1 because UI C V.
The above reasoning also indicates that @(4) S (O(n) S Φ(U) holds and that the boundary of LI has zero Lebesgue measure. Since the matrix exponential map expm (.) injective within the interior of U and the complex exponential function is single-valued, the set SO(n) ((l) has zero Lebesgue measure in (O()).
The mapping (-(()) differentiable, surjective, and injective on each submanifold Sp. Additionally, the set of meaningless points for +-(()) has a zero Lebesgue measure in SO(n).
Theorem 2*.
Proof. Since the right translation RD establishes an isometry between the neighborhoods of P and its agent P. we can, without loss of generality, restrict proof to the case where P - p(O) is an even permutation. In this case, we rewrite , as Φr (O) P Pexpm (r logm (PT O)). According to Corollary G.3, if PT O is within W, then submanifold Sp.
assert that x (-) is surjective and injective each
Assuming the eigenvalues of PT O are A the eigenvalues of PT 0-1 are 1,. An 1. Since the inverse mapping the left translation, Lpt (0) := O (VO E SO(n)), maps to neighborhood around we may assume ||PT O - I[
A well-known result is r(A) < |||||r
for any A E RRxx, where r(A) == max (A)) vk is the spectral radius. As a result, we have:
r(PTO I) max max(
4k) < ||PT 0 T|] < 1.
(23)
Equation (23) shows that the eigenvalues of PT are within unit circle centered in the complex plane. Therefore, p O has no eigenvalues on R7. meaning PO
0 E W.
Since p(-) w.r.t. Equation (7) is piecewise constant function, it follows that the set of points where dir (-) is meaningless has a zero Lebesgue measure. This completes the proof.
G.3 Lemmas used
Lemma G.1 (Theorem 4. in Hille [25]). Let A, B E Cax", If there no two eigenvalues in A such that their difference is of the form 2KT for and, ifexpm (A) = expm (B), we have that AB BA.
Let Nil(k) denote the set of (real or complex) nilpotent matrices, A, of any dimension n 2 such that A 0 and Uni(k) denote the set of unipotent matrices, B = I A. where A E Nil(k).
Lemma G.2 (Proposition 3.2. in Gallier [18]). The map expin Nil(k) + Uni(k) is homeomor- phism whose inverse is the matrix logarithm.
Lemma G.3 (Corollary 11.10. in Hall [21]). If G is connected, compact matrix Lie group, the exponential map for G is surjective.
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims accurately reflect the contribution and scope of the paper.
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
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations in Appendix A.
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 separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to 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 faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
27

---

Justification: In the Appendix G, we provide complete proofs for all theoretical results and list some essential lemmas used in the proofs.
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 in the main paper or the supplemental material, but if 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 or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: In Appendix F.I, we provide all the experimental details, the random seeds used and the runtime environment.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a 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 to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
28

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The core code has been released at /tt....ccc//amm/gggg/g///////
OT4P.
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/guides
wwwiibmisssooooooooooooooooooooo commoolion olicyy for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-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. ct/pcc/ppllc. ctc/public//ee Semnidde/Cooeeuui
cessoonoolccnn for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide comprehensive overview of the experiments in Appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, 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:
We report the experimental results using five different random seeds.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
29

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables 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: Appendix F.1 provides information on compute resources.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, 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 as 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 or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: / /nwuriprrsp.. cc httpppi//ttiisesuiiiiipppappppee
Answer: [Yes]
Justification:
We have reviewed the NeurIPS Code of Ethies.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations 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]
Justification:
We discuss the potential social impacts of this work in Appendix A.3
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., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
30

---

The conference expects that many papers will be foundational research and not tied 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, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or 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 monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
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)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Appendix F.5 have included the licenses for the assets used in the paper.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (c.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
31

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This does not apply research work.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is 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)?
Answer: [NA]
Justification:
This work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
32


Reviews:
[{"review_id": "aSLAlgAGeE", "reviewer": "Reviewer_3CCZ", "summary": "This paper proposes OT4P, a differentiable transformation that relaxes permutations to the orthogonal group. Based on OT4P, the authors propose novel frameworks for deterministic and stochastic optimization on permutation matrices. Numerical experiments demonstrate its efficiency and scalability in permutation matrix optimization tasks.", "questions": "- Do you have any guidance on how to choose the hyperparameter \\tau? It seems that \\tau=0.5 is optimal for all tasks in the experiment section. Should we just fix \\tau=0.5 for practical use?", "limitations": "Despite several limitations discussed in the appendix, other limitations of this work include: \n- In real world computer vision problems, people usually have partial permutations instead of permutations, since a keypoint may not be observed in some images. It would be more interesting if this work can be extended to optimization on partial permutations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is generally well written despite a few confusing sentences. The authors highlight the contributions and make a clear comparison with previously known results, and the main idea is interesting. Mathematical ideas are hard to clarify, but I find the paper easy to follow. The numerical experiment supports the claim that OT4P enjoys flexibility, simplicity and scalability on selected tasks.", "weaknesses": "Experiments are insufficient and do not fully convince me of the superiority of OT4P. It's hard to convince me that OT4P is valuable in real settings, therefore the impact of this work in practice is questionable. \n- The experiments in the main text are both synthetic. Why are they important? \n- Permutation synchronization is only tested on CMU house dataset, and it is only tested to demonstrate the runtime and memory efficiency. You can try more challenging multi-object matching datasets such as Willow[1]. It would be interesting to see if OT4P avoids unreliable local minima and achieves a better matching result, compared to Birkhoff polytope-based methods. \n\n- For permutation synchronization, convex relaxation methods are known to be slow, but you are using parallel computation to accelerate. A detailed explanation on this is necessary. \n\nThere are a few confusing sentences and some room of improvement in writing. \n- Line 223: 'is stay' should be 'stays'. \n- Not sure how to read figure 4. It would be nice to have some explanation. \n- The manifold \\mathcal{M} is an important mathematical object in the paper that relates directly to parameterization in optimization tasks. It is helpful to have more explanation on how it changes with the temperature parameter. \n\n[1] M. Cho, K. Alahari, and J. Ponce. Learning graphs to match. In Proceedings of the IEEE Interational Conference\non Computer Vision, 2013.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are deeply grateful to Reviewer 3CCZ for the detailed and constructive feedback on our work. We strongly recommend reviewing our global rebuttal first to clarify common concerns. We address your specific questions below.\n\n## **Q1: the experiments in the main text are both synthetic**\nWe recognize the importance of demonstrating the practical impact of the proposed OT4P method. Indeed, the experiments presented in the main text address new, practical problems involving permutation matrices in the field of machine learning, ranging from deterministic to stochastic optimization. Our OT4P showcases an effective way of tackling these real-world challenges.\n\nThe first reason for using synthetic data is the absence of a publicly available and widely used real-world dataset, as most are privately created in specific scenarios. The second reason is that the primary purpose of experiments is to test the theoretical properties of OT4P, including its ability to approximate permutation matrices and its effectiveness in gradient-based optimization. A controlled synthetic setting allows us to isolate the impact of our method from other potential confounding factors found in real-world environments. In conclusion, using synthetic data provides the most rigorous and efficient means of validating the proposed theory.\n\nAs you have noted, to further validate the practical applicability of our theory, we have included experiments with real-world datasets in the permutation synchronization task, which are detailed in the **Additional experiments** of the global rebuttal.\n\n## **Q2: permutation synchronization is only tested on CMU house dataset**\nFollowing your suggestion, we have conducted additional experiments on the WILLOW-ObjectClass dataset [1], incorporating four new baselines. Please see the **Additional experiments** in the global rebuttal for details.\n\n## **Q3: convex relaxation methods are known to be slow**\nThe primary computational costs of the proposed OT4P arise from solving the linear assignment problem and performing eigendecomposition, both of which typically scale with $\\mathcal{O}(n^3)$. Given the widespread application of these tools in machine learning, numerous studies have developed their parallel versions, especially optimized for GPUs that are well suited for dense matrix computations [2]. Benefiting from these advancements, OT4P can efficiently handle relaxation matrices at significantly accelerated speeds. We will provide further explanations in the paper.\n\n## **Q4: not sure how to read figure 4**\nFigure 4 illustrates the orthogonal matrices obtained in Step II of OT4P. The leftmost image ($\\tau=1$) represents the original orthogonal matrices $O$ from Step I, and the rightmost image ($\\tau=0$) is the permutation matrix $P$ that is closest to $O$. The temperature parameter $\\tau$ controls how closely the resulting orthogonal matrices $\\widetilde{O}$, obtained in Step II, approach $P$. As $\\tau\\to 0$, the resulting orthogonal matrices $\\widetilde{O}$ increasingly converge to $P$.\n\n## **Q5: the manifold $\\mathcal{M}$ is an important mathematical object**\nGiven the temperature parameter $\\tau$, the manifold $\\mathcal{M}:=\\\\{\\mathcal{S}\\_{P}^{\\prime}\\subset \\mathrm{O}(n)\\mid P\\in\\mathcal{P}\\_n \\\\}$ consists of submanifolds $\\mathcal{S}_{P}^{\\prime}$, where each $\\mathcal{S}\\_{P}^{\\prime}$ encompasses a permutation matrix $P$. As $\\tau$ approaches $0$, the $\\mathcal{S}\\_{P}^{\\prime}$ contract towards the permutation matrix $P$, culminating in the degeneration of $\\mathcal{S}\\_{P}^{\\prime}$ to a singleton set $\\{P\\}$ when $\\tau=0$.\n\n## **Q6: do you have any guidance on how to choose the hyperparameter $\\tau$**\nThe selection of the hyperparameter $\\tau$ involves balancing the relaxation of the solution and the difficulty of optimization. A large $\\tau$ may lead to overly relaxed solutions, while a small $\\tau$ might cause optimization challenges. Setting $\\tau=0.5$ is a practical and balanced choice, as this setting positions the resulting orthogonal matrix $\\widetilde{O}$ midway between the original orthogonal matrix $O$ and its closest permutation matrix $P$, in a certain sense.\n\n## **Q7: people usually have partial permutations instead of permutations**\nThis is indeed a valuable and interesting extension. One possible approach is to consider $n\\times k\\ (k<n)$ partial permutations as a projection of $n\\times n$ total permutations. In this way, we could use OT4P to relax the $n\\times n$ permutation matrices and then take the first $k$ columns of the resulting orthogonal matrix as the final output. Essentially, this method involves relaxing partial permutations onto the Stiefel manifold with dimension $n\\times k$. We plan to explore this idea more thoroughly in future work.\n\nWe will conduct a thorough review and correction of any typographical errors to avoid potential confusion. We once again thank the reviewers for their constructive feedback, which will significantly enhance the quality and clarity of our paper.\n\n## References\n[1] Minsu Cho, Karteek Alahari, and Jean Ponce. Learning graphs to match. ICCV, pages 25–32, 2013.\n\n[2] Ketan Date and Rakesh Nagi. Gpu-accelerated hungarian algorithms for the linear assignment problem. Parallel Computing, 57:52–72, 2016.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "n2lXOcvcTf", "reviewer": "Reviewer_FuEB", "summary": "The paper proposes a parameterization of $n\\times n$ permutation matrices by $n(n-1)/2$ unconstrained numbers. This parameterization eases the training of neural networks and is applicable to tasks involving optimization over permutations.", "questions": "Besides the above, one extra question:\n- Eq. 7 is a linear assignment problem. But since the data matrix is orthogonal, is it possible to have an algorithm faster than cubic time?", "limitations": "See the above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-written and easy to follow.\n- The initial idea is very simple: Replace the doubly stochastic relaxation with the orthogonal relaxation. Following this idea, the paper develops good intuition and solid theorems in terms of injective/surjectivity of the parametrization.\n- The experimental results look great, presenting the advantages of the proposed method in some aspects.", "weaknesses": "- Some design choices and technical development do not seem to be very motivated;\n   - What's the role of the temperature parameter $\\tau\\in(0,1]$? What's wrong if we just set it to $0$ and we just want the closest permutations? In fact, the experiments show that smaller $\\tau$ seem to be better (see Table 5). If $\\tau$ is not needed (and if I understand this correctly), then there would not be the problem of odd permutations and there would be no need to introduce $D$ and the remedy.  \n   The reader may be unclear about why special orthogonal groups are used for parameterization. Why not just use orthogonal groups? It would be nice to have this explained in the paper.\n\n- Can authors provide results for the case \"Known 0%\" in Table 2? This is important as it gives the reader a better understanding of the importance of having prior information. \n\n- The running time of the method is unclear and the scalability claim does not seem to be true. \n   - First, the two costly steps of the proposed method are eigenvalue decomposition and solving the linear assignment problem, and, in my experience, the latter is often much slower for various reasons, e.g., eigenvalue decomposition has high-quality implementations and is more amenable to parallel execution. Also, the method of Jonker & Volgenant (1987) [1] is much faster than the Hungarian algorithm. Both steps should be fast for matrices of size 1000x1000. Could the authors comment on why their implementation is slow for $n>1000$ (as mentioned in Appendix A.2)?  Furthermore, matrices of such sizes are not \"very large\"; hence, I think the claim that the proposed method is scalable is an overstatement.\n   - Could the authors compare the proposed method's running time (time complexity) with prior works?\n\n[1] A shortest augmenting path algorithm for dense and sparse linear assignment problems\n\n\n- Some typos or confusion:\n   - In the definition of the domain $U$ of Theorem 1, what is Im? Does it mean the imaginary part of the eigenvalues? It would be nice to define them.\n   - In Eq. 14, the optimization problem is not defined clearly. What are the optimization variables, and is $\\theta$ the parameter of $f$ as well?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We extend our heartfelt thanks to Reviewer FuEB for your thorough and thoughtful review of our manuscript. We strongly recommend reviewing our global rebuttal first to clarify common concerns. We have carefully considered your feedback and responded to it below.\n\n## **Q1: what's the role of the temperature parameter $\\tau$?**\nPlease refer to **Q2** in the global rebuttal.\n\n## **Q2: what's wrong if we just set it to 0 and we just want the closest permutations?**\nDuring the evaluation phase, we can set $\\tau=0$ to obtain the permutation matrix closest to the original orthogonal matrix. However, during the training phase, setting $\\tau=0$ impedes gradient-based optimization. For a detailed explanation, please see **Q3** in the global rebuttal.\n\n## **Q3: the experiments show that smaller seem to be better**\nWe would like to clarify that a smaller $\\tau$ indeed brings the relaxed problem closer to the original problem, potentially yielding more accurate solutions. However, this also tends to increase the difficulty of the optimization process, particularly when considering the extreme case of $\\tau=0$.\n\n## **Q4: there would not be the problem of odd permutationsd**\nThe issue with odd permutations arises because the special orthogonal group does not include permutation matrices $P$ with $\\det(P) =-1$. We address this problem using Lie group theory; for more details, please refer to **Q4** in the global response.\n\n## **Q5: the reader may be unclear about why special orthogonal group**\nThe full group of orthogonal matrices, $\\mathrm{O}(n)$, is not connected and consists of two connected components. When an initial point is set, Riemannian optimization typically cannot reach the other component. Consequently, most work prefers to utilize the special orthogonal group, $\\mathrm{SO}(n)$, which includes the identity matrix, for parameterization purposes.\n\n## **Q6: can authors provide results for the case \"Known 0%\"**\nWe conducte experiments under the Known $0\\%$ setting, and the results are as follows.\n|  Known $0\\%$   | Naive  |   Gumbel-Sinkhorn   | OT4P ($\\tau=0.3$) |  OT4P ($\\tau=0.5$)  | OT4P ($\\tau=0.7$)  |\n|  :--:  | :--: |  :--:  | :--: |  :--:  | :--:  |\n|  $\\log p(Y\\mid P)$  | <-3000  | <-3000  | <-3000  | <-3000 | <-3000 |\n|  Precision ($\\\\%$) | 2.08  | 1.76 | 1.36  | 1.60  | 1.60  |\n\nWe found that all methods failed. A possible reason is that prior information (constraint matrix) provides an initial point, which is crucial for gradient-based optimization. This experiment highlights the importance of prior information in accurately inferring neuron identities.\n\n## **Q7: the running time of the method is unclear**\nAs you correctly pointed out, the primary computational costs of OT4P lie in solving the linear assignment problem and performing eigendecomposition, both typically having a time complexity of $\\mathcal{O}(n^3)$. Numerous efforts have been made to accelerate these computations through parallel implementations on GPUs. We have employed existing implementations, specifically torch-linear-assignment and torch.linalg.eig, and found that eigendecomposition tends to be slower. These findings are replicated in the table below.\n|   size  | 50  |  100  |  500   | 1000 |  5000  |\n|  :--:  | :--:  |  :--:  | :--:  |  :--:  | :--:  |\n|  linear assignment problem (s)  | 0.001  | 0.002 |  0.011  | 0.051  | 2.384 |\n|  eigendecomposition (s) | 0.028  | 0.053 | 0.246  | 0.798 | 16.729 |\n\nWhile exploring more efficient methods for solving the linear assignment problem and performing eigendecomposition would be valuable, such investigations are beyond the scope of this paper. Nevertheless, we will include a time complexity analysis of OT4P in the manuscript and compare it with previous work.\n\n## **Q8: the scalability claim does not seem to be true**\nAlthough OT4P lacks scalability for matrices larger than 1000, we argue that this can be further improved by implementing a more efficient parallel version of eigendecomposition. Additionally, OT4P has demonstrated potential for stochastic optimization over latent permutations, as discussed in Section 3.2, representing an important extension for probabilistic tasks.\n\n## **Q9: the optimization problem is not defined clearly**\nIn Equation 14, the function $f(P)$ is defined with respect to the permutation matrix $P$, which is treated as a random variable drawn from the distribution $P\\sim q(P;\\theta)$ parameterized by $\\theta$. Here, $\\theta$ serves as the optimization variable. Evaluating and differentiating Equation 14 presents challenges because calculating the expectation involves a sum of $n!$ terms. We address this problem efficiently using OT4P combined with the re-parameterization technique.\n\n## **Q10: is it possible to have an algorithm faster than cubic time**\nThis is an insightful question. In the early stages of developing our idea, we experimented with randomized rounding, which derives permutations based on the action of the orthogonal matrix on random vectors [1]. We also tested a greedy strategy that sequentially sets the largest available element to $1$ in each column. However, preliminary experiments demonstrated the unreliability of these methods, prompting us to abandon them. In conclusion, OT4P would certainly benefit from a faster algorithm specifically designed to solve the linear assignment problem with an orthogonal matrix.\n\nThank you once again for your time and effort. These valuable discussions will be incorporated into our paper to enhance its quality.\n\n\n## References\n[1] Alexander Barvinok. Approximating orthogonal matrices by permutation matrices. arXiv preprint math/0510612, 2005.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4imAHwJwvi", "reviewer": "Reviewer_k6w2", "summary": "This paper proposes a new method for relaxing permutation matrices onto the group of orthogonal matrices. A temperature controlled differentiable transform maps the permutations onto O(n) and this allows for adjusting the strength of regularity vs the problem difficulty. With this relaxation, the paper employs continuous optimization methods to solve various problems including permutation synchronization, a notoriously challenging non-convex problem. The experiments demonstrate a consistent advantage over (Gumbel-) Sinkhorn.", "questions": "Please see the weaknesses section for most of my questions. In particular, I would be happy if the authors can address:\n- Distinguishing SO(n) from O(n) and stating the impact of the choice, especially in context of the proposed transformation.\n- Some evidence/evaluation/justification that the transformation does not pose a problem for geodesic distance computation.\n- Comparisons and discussions to [5] and the simple regularization baseline (see weaknesses).", "limitations": "The paper discusses the limitations in Appendix A. I would appreciate if some of those would be moved to the main paper. Especially the boundary issues can be discussed within the main text. An appropriate broader impact statement is added to the paper (appendix). I see no concerns with that.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "First of all, optimization over permutations is a very important problem, remaining yet to be solved. To this end, this paper introduces an awesome idea as well as a sensible, well-thought approach to implement it. I especially like the fact that, similar to entropic-OT, the temperature parameter allows for an interpretable control over being a generic orthogonal matrix vs. being a permutation. I also checked the code and it seems reasonable.", "weaknesses": "There are several clarifications and evidence needed to make the paper fully convincing:\n\n- Permutations are the only strictly positive orthogonal matrices. Therefore, all relaxed matrices in this paper will inherently include some negativity. While acceptable for optimization, this poses a challenge when rounding results back to permutations. This raises two questions:\n    1. How do the authors implement rounding, precisely? In the experimental results, it would be beneficial to see the 'permutationness' of the final matrix, possibly in comparison to accuracy or loss. This insight would inform practitioners about important design choices.\n    2. Why constrain ourselves to the orthogonal group and not introduce temperature directly in $\\mathbb{R}_{+}(n)$? What makes orthogonal matrices special? This point is only partially explained.\n  \n- I'm uncertain about the transformation of odd permutations. $O(n)$ has a disconnected topology, unless it's $SO(n)$ (considering reflections), and transforming to the interior of $\\mathcal{U}$ can distort and change geodesic distances, crucial for optimization. The paper appears to use $O(n)$ and $SO(n)$ interchangeably, which might not be good practice. The consideration of reflections is essential due to potential distortions caused by mapping some matrices into the interior of $\\mathcal{U}$. Are we assuming a connected topology? These points confuse me.\n  \n- Permutation synchronization, a new experiment mentioned only in the supplementary materials, deserves mention in the main text. Also note that, Birdal and Simsekli [5] use the Riemannian geometry of the doubly stochastic matrices to solve permutation synchronization. They also control the strength by analytically deriving the prior induced by the manifold-objective. This work should be discussed, and hopefully compared. \n  \n- The paper lacks another simple baseline: relax permutations onto orthogonal matrices (classical) and use a regularization term to enforce permutation-ness, controlled by coefficient $c$. As $c \\to 0$, optimization on $O(n)$ is naive, while as $c \\to \\infty$, strict permutation-ness makes the problem challenging. This approach could be included in comparisons.\n  \n- In the proposed approach, $T \\to 0$ can cause numerical issues. At what point does this become problematic and unfeasible? Intuitively, why is this approach preferable to entropy-regularized optimal transport, which seems similar in spirit? The paper should discuss or at least cite:\n*Cuturi, Marco. \"Sinkhorn distances: Lightspeed computation of optimal transport.\" Advances in neural information processing systems 26 (2013).*\n\n- Can we see results from different optimizers? Depending on their behavior, advantages might be amplified or diminished. For instance, [5] used Riemannian LBFGS. Note that Adam might not be the most suitable optimizer for such problems. \n  \nMinor issues:\n- Ln. 223: \"is stay\" -> \"stays\"\n- The link for CMU house seems to be broken. Where did authors obtain the dataset?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer k6w2 for your insightful and constructive comments. We strongly recommend reviewing our global rebuttal first to clarify common concerns. Following are our responses to each individual comment.\n\n## **Q1: how do the authors implement rounding**\nTo implement rounding from the orthogonal matrix $O$, we first eliminate negative elements by subtracting the minimum element found within $O$, i.e., $O−\\min(O)$. This approach is justified by the fact that $\\arg\\max_P ⟨P,O⟩=\\arg\\max_P⟨P,O−\\min(O)⟩$. Subsequent to this adjustment, we employ the Hungarian algorithm, available in existing libraries, to round $O−\\min(O)$ to the closest permutation matrix. We will provide additional details on this implementation in the paper.\n\n## **Q2: it would be beneficial to see the 'permutationness'**\nBased on your suggestion, in the newly added experiments, we have employed $\\ell_1$ Distance to measure the \"permutationness\" of the final matrix. For more details, please refer to the **Additional experiments** in the global rebuttal.\n\n## **Q3: why constrain ourselves to the orthogonal group**\nAs discussed in the paper, the orthogonal group possesses the advantages of offering lower-dimensional search space and preserving inner products. If Step II is replaced with linear interpolation, we would lose these potential benefits. Our experiments have also verified that remaining within the orthogonal group can lead to performance improvements in certain scenarios.\n\n## **Q4: I'm uncertain about the transformation of odd permutations**\nWe would like to clarify that the computation of geodesics is exclusively conducted within the simply connected $\\mathrm{SO}(n)$, without alternating between $\\mathrm{SO}(n)$ and $\\mathrm{O}(n)$. For a more comprehensive explanation, please refer to **Q4** in the global rebuttal. Importantly, we do not directly transfer orthogonal matrices near the odd permutation into the interior of $\\mathcal{U}$. Instead, we first map these matrices to $\\mathrm{SO}(n)$ using an isometry, and subsequently to $\\mathcal{U}$ through a differentiable homeomorphism, thus avoiding any potential distortions. \n\n## **Q5: permutation synchronization**\nThe global rebuttal presents additional experiments conducted on the WILLOW-ObjectClass dataset [1], incorporating the two baselines you mentioned. Furthermore, we provide results using various optimizers. Please note that the code in [5] is not publicly available, so we utilize Riemannian gradient descent at Birkhoff Polytope as an alternative [2].\n\n## **Q5: $\\tau\\to 0$ can cause numerical issues**\nPlease refer to **Q3** in the global rebuttal.\n\n## **Q6: why is this approach preferable to entropy-regularized optimal transport**\nOur approach is similar in spirit to methods based on Sinkhorn's algorithm, as both aim to relax and subsequently anneal solutions toward permutation matrices. However, unlike these works, we opt for relaxation over the orthogonal group, which offers potential advantages such as a lower-dimensional search space and the preservation of inner products. Practically, OT4P employs a single well-defined hyperparameter, whereas the Sinkhorn-based approaches typically involve two interdependent hyperparameters: the number of iterations and the regularization strength. These distinctions can make OT4P more straightforward to configure and potentially more robust in practice.\n\nWe will correct the typographical errors and cite the paper you mentioned. The CMU dataset can be found in the open-source project of [3]. Due to page constraints, discussions on permutation synchronization and boundary issues are currently placed in the appendix. We will consider relocating these sections to the main paper to improve clarity and structural coherence. Thank you once again for your insightful feedback, which provides valuable insights for further refinement of our work.\n\n## References\n[1] Minsu Cho, Karteek Alahari, and Jean Ponce. Learning graphs to match. ICCV, pages 25–32, 2013.\n\n[2] Gary Becigneul and Octavian-Eugen Ganea. Riemannian adaptive optimization methods. ICLR, 2019.\n\n[3] Florian Bernard, Daniel Cremers, and Johan Thunberg. Sparse quadratic optimisation over the stiefel manifold with application to permutation synchronisation. NeurIPS, 34:25256–25266, 2021. Project at https://github.com/fbernardpi/SparseStiefelOpt", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely appreciate the reviewers for dedicating their valuable time and effort to thoroughly reviewing our manuscript. Here, we address the common concerns raised and introduce the additional experiments conducted.

# Common concerns
## **Q1: What is the intuition behind Step II of the proposed OT4P?**
Given an orthogonal matrix $O$ obtained from Step I, Step II aims to move $O$ toward its closest permutation matrix $P$ to approach $P$. Analogous to transitioning a point $A$ towards another point $B$ along a straight line $AB$ in Euclidean space, OT4P moves $O$ towards $P$ along a geodesic $OP$—the generalization of straight lines to the manifold context.

## **Q2: What's the role of the temperature parameter $\tau$?**
The temperature parameter $\tau$ may be interpreted as the parameter of the geodesic (inversely), controlling how closely the resulting orthogonal matrix $\widetilde{O}$, obtained in Step II, approaches the permutation matrix $P$, with $\widetilde{O}\to P$ as $\tau\to0$. Specifically, when $\tau=1$, $\widetilde{O}$ remains equal to $O$, and when $\tau=0$, $\widetilde{O}$ becomes $P$.

## **Q3: What's wrong if we set $\tau = 0?$**
Setting $\tau=0$ is an impractical choice, as it would cause all orthogonal matrices near the permutation matrix $P$ to be mapped directly to $P$. In such a setting, gradient-based optimization becomes unfeasible because the mapping $\psi_{\tau}(\cdot)$ (corresponding to Step II) turns into a piecewise constant function, whose derivatives are almost everywhere zero.

## **Q4: How to deal with odd permutations?**
To deal with odd permutations, we identify an agent $\widehat{P}$ of the odd permutation $P$, and utilize Lie group theory to establish an isometry between the neighborhoods of $P$ and $\widehat{P}$. This approach allows us to move orthogonal matrices along geodesics within $\mathrm{SO}(n)$ towards $\widehat{P}$ , and then restore the results equivalently into the neighborhood of $P$ to approximate $P$. Importantly, all geodesics calculated in this process remain within $\mathrm{SO}(n)$, ensuring there is no distortion in the transformation.

# Additional experiments
Based on reviewers' feedback, we conducted permutation synchronization experiments on the more challenging WILLOW-ObjectClass dataset, incorporating four new baselines.

The WILLOW-ObjectClass dataset [1] comprises images of five object classes, each containing $10$ equal keypoints of at least $40$ images. For each image, we extract interpolated features from the relu4_2 and relu5_1 layers through a pre-trained VGG16 model on ImageNet. The initial pairwise correspondences are established by applying the Hungarian algorithm to the distance matrices of features.

We select the following algorithms as baselines:
1. Reg: Optimizes in Euclidean space with a regularization term $\sum_j (\sum_j P_{i,j} - 1)^2$ that encourages each column to sum to $1$.
2. OrthReg [2]: Optimizes over the (special) orthogonal group, using a regularization term $\frac{2}{3}\mathrm{trace}(P^{T}(P-P\circ P))$ ($\circ$ is element-wise product) to force the orthogonal matrix to converge to permutation matrices.
3. RiemanBirk [3]: Optimizes on Birkhoff polytope utilizing Riemannian gradient descent.
4. Sinkhorn [4]: Optimizes on the Birkhoff polytope, using the Sinkhorn operator to adjust positive matrices into doubly stochastic matrices.

Unless otherwise stated, all algorithms employ the Adam optimizer for $100$ iterations, with RiemanBirk utilizing Riemannian Adam. The initial learning rates are tuned within the set $\\{0.1, 0.01, 0.001, 0.0001\\}$.

We generate problem instances of varying sizes and report the average results from five runs in Figure 1 (see PDF). RiemanBirk and Sinkhorn demonstrate poorer performance. A primary reason is that both methods relax permutations in the Birkhoff polytope, leading to unreliable local minima and preventing optimal solutions. Benefiting from the potential advantages offered by the orthogonal group, OrthReg generally produces competitive results. However, due to the instability of its regularization term, OrthReg sometimes underperforms, which may necessitate careful adjustment of the regularization coefficient for each class. In contrast, our proposed OT4P consistently outperforms other methods and demonstrates robustness to variations in hyperparameters $\tau$.

We take the $\ell_1$ Distance to assess the "permutationness" of the final matrix. Specifically, we round the matrix $O$, returned by the algorithms, to its closest permutation matrix $P$, and then calculate the $\ell_1$ Distance between $O$ and $P$. Table 1 (see PDF) lists the results for the problem instances corresponding to the largest size (multiples of $5$) in each object class. We observe that the relaxation extent of Sinkhorn is unstable. Unlike them, ОТ4Р consistently maintains smaller distances in almost all cases and exhibits a positive correlation with changes in the hyperparameter $\tau$.

We compare the results of different optimizers in Table 2 (see PDF), selecting the largest problem instances (multiples of $5$) for each object class. Methods based on the Birkhoff polytope show notable performance improvements on most datasets when using (Riemannian) SGD. For our proposed OT4P, the choice of optimizer appears to be less critical, as it consistently outperforms other methods regardless.
## References
[1] Minsu Cho, Karteek Alahari, and Jean Ponce. Learning graphs to match. ICCV, pages 25–32, 2013.

[2] Michael M Zavlanos and George J Pappas. A dynamical systems approach to weighted graph matching. Automatica, 44(11):2817–2824, 2008.

[3] Gary Becigneul and Octavian-Eugen Ganea. Riemannian adaptive optimization methods. ICLR, 2019.

[4] Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning latent permutations with gumbel-sinkhorn networks. ICLR, 2018.

Meta-review: The paper introduces OT4P, an innovative approach that relaxes permutation matrices onto the orthogonal group, enabling continuous optimization for permutation-related tasks. Reviewers found the concept both novel and well-executed, offering a promising new direction in this challenging area. While some concerns were raised about the clarity of certain design choices and the need for more extensive experimental validation, the method's potential impact and the soundness of its theoretical foundation make it a valuable contribution. Therefore, I recommend accepting this paper.
Decision: Accept (poster)