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.

Q1: how do the authors implement rounding

To 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.

Q2: it would be beneficial to see the 'permutationness'

Based 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.

Q3: why constrain ourselves to the orthogonal group

As 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.

Q4: I'm uncertain about the transformation of odd permutations

We 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.

Q5: permutation synchronization

The 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].

Q5: $\tau\to 0$ can cause numerical issues

Please refer to Q3 in the global rebuttal.

Q6: why is this approach preferable to entropy-regularized optimal transport

Our 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.

We 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.

References

[1] Minsu Cho, Karteek Alahari, and Jean Ponce. Learning graphs to match. ICCV, pages 25–32, 2013.

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

[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

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.

Q1: what's the role of the temperature parameter $\tau$?

Please refer to Q2 in the global rebuttal.

Q2: what's wrong if we just set it to 0 and we just want the closest permutations?

During 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.

Q3: the experiments show that smaller seem to be better

We 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$.

Q4: there would not be the problem of odd permutationsd

The 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.

Q5: the reader may be unclear about why special orthogonal group

The 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.

Q6: can authors provide results for the case "Known 0%"

We conducte experiments under the Known $0\%$ setting, and the results are as follows.

We 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.

Q7: the running time of the method is unclear

As 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.

While 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.

Q8: the scalability claim does not seem to be true

Although 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.

Q9: the optimization problem is not defined clearly

In 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.

Q10: is it possible to have an algorithm faster than cubic time

This 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.

Thank you once again for your time and effort. These valuable discussions will be incorporated into our paper to enhance its quality.

References

[1] Alexander Barvinok. Approximating orthogonal matrices by permutation matrices. arXiv preprint math/0510612, 2005.

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.

Q1: the experiments in the main text are both synthetic

We 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.

The 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.

As 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.

Q2: permutation synchronization is only tested on CMU house dataset

Following 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.

Q3: convex relaxation methods are known to be slow

The 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.

Q4: not sure how to read figure 4

Figure 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$.

Q5: the manifold $\mathcal{M}$ is an important mathematical object

Given 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$.

Q6: do you have any guidance on how to choose the hyperparameter $\tau$

The 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.

Q7: people usually have partial permutations instead of permutations

This 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.

We 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.

References

[1] Minsu Cho, Karteek Alahari, and Jean Ponce. Learning graphs to match. ICCV, pages 25–32, 2013.

[2] Ketan Date and Rakesh Nagi. Gpu-accelerated hungarian algorithms for the linear assignment problem. Parallel Computing, 57:52–72, 2016.

I thank the authors for the clarifications and additional experiments including comparisons with the baselines. I like to suggest one correction: I could find nothing in [3] regarding either the Birkhoff polytope or the permutation synchronization problem. Moreover, the Birkhoff polytope implementation in geoopt is due to Birdal & Simsekli CVPR'19, which addresses the permutation synchronization problem by optimizing over the Birkhoff polytope using its Riemannian characterization: https://github.com/geoopt/geoopt/blob/master/geoopt/manifolds/birkhoff_polytope.py.

Hence, I think the correct citation for RiemannBirk is: Birdal, Tolga, and Umut Simsekli. "Probabilistic permutation synchronization using the riemannian structure of the birkhoff polytope." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2019.

I will keep my initial recommendation of acceptance.