Aligning Embeddings and Geometric Random Graphs: Informational Results and Computational Approaches for the Procrustes-Wasserstein Problem

We thank the reviewer for the time spent reviewing and all the remarks and questions that will help clarify our paper. We make sure to address the concerns raised below.

The title seems misleading. Could the authors comment on the relation between the considered problems in line 29-39 with random graphs in the title? There is a strong connection between the PW (Procrustes-Wasserstein) problem and GGA (geometric graph alignment), as we argue in our paper.
In GGA, we observe two complete random graphs and try to recover an underlying node correspondence $P^*$. The randomness in this model comes from edge weights which are induced by a Gaussian model: The weights are scalar products between unobserved gaussian random vectors. Note that applying an orthogonal map $Q^*$ to all the vectors leaves the scalar products invariant.
In PW on the other hand, we directly observe the vectors and want to recover both $P^*$ and $Q^*$. As described in section 'Geometric graph alignment' of the introduction, the two problems (GGA and PW) are equivalent. This is formalized in Lemma 1, for which a proof is given in Appendix A.
To make it clearer, we propose to highlight Lemma 1 more in a revised version since it clarifies the title.

Could the authors elaborate why it is interesting to consider Procrustes-Wasserstein problem between a point cloud generated from Gaussian distribution and its noisy version under orthogonal transformation? This is a fundamental question which can be answered as follows. Many learning problems on real-world data can be phrased as optimization problems, which are often difficult in their worst case formulation, meaning the case where any instance of the problem is considered. A common approach to understanding a problem's hardness and deriving algorithmic guarantees is to consider the planted version of these problems, that is when data has more structure. This structure stems from a signal (here: an underlying alignement $P^*$ and an orthogonal transformation $Q^*$), and noise (here: Gaussian noise). The benefits of this approach is that we have a precise understanding of why the problem is easy or difficult based on the signal-to-noise ratio $\sigma$. For a broad introduction on planted problems, we refer to the survey on community detection by C. Moore, https://arxiv.org/pdf/1702.00467, page 5.

For the high dimensional regime, why do we need lower-bound on $\pi$, but upper bound on $Q$? How’s about the upper-bound on $\pi$, and lower-bound on $Q$ – do they have some roles in the considered problem setting? An upper bound on $\ell^2$ (for $Q$) and a lower bound on the overlap of $\pi$ point in the same direction: To show that recovery is possible, a larger overlap is better and a lower $\ell^2$-loss is better as well.

For the Algorithm 1, why is it possible to fix T, and K? Does the algorithm converge? Is it possible to have some reasonable stopping conditions? It is possible to fix $K,T$ arbitrarily, depending on the computation power available. Empirically, the algorithm converges after $O(1)$ iterations. The smaller the signal-to-noise ratio, the larger the number of required iteration.
We show in Proposition 1 that if $\sigma$ is small enough, $K,T=1$ is already sufficient.

Could the authors clarify why the algorithm 1 is superior to the algorithm in Grave et al. (2019)? It is better to deepen the analysis and illustrate with rigorous empirical evidence? E.g., with large number of data points (e.g., in Figure 1, it shows for n <= 200) Intuitively, our algorithm is better than that of Grave et al. (2019) since it is more ‘greedy' at each iteration. Empirically, Figure 1 shows that this is indeed the case for the whole considered range of parameters. The superiority is even stronger for small signal-to-noise ratios and large dimensions. We propose, as suggested by the reviewer, to extend our empirical analysis to larger number of data points ($n$ larger) and larger dimensions.

In line 104-108, the authors emphasize the difference with other related works. Additionally, as in Figure 1, the authors also consider the case where d=2 and d=5, it is not clear why these approaches are not considered as baselines (as claimed in line 102-103). Could the authors clarify it? In figure 1, we consider $d=2$ and $d=10$. These are no baselines; they are respectively meant to capture both the small dimension ($d << \log(n)$) and large dimension ($d>> \log(n)$) settings, as our paper shows that there is a dfference between these two regimes.

When Qstar = I, could the authors compare the presented results with those in Kunisky and Niles-Weed (2022)? This is the content Table 1: in particular, we show that for small dimensions, since we consider the $c^2$ transport cost, we are able to recover some signal even for $\sigma=\Omega(1)$, whereas Kunisky and Niles-Weed (2022) require much smaller signal-to-noise ratio ($\sigma<<n^{-1/d}$). We will make this comparison clearer in the paper.

The Procrustes-Wasserstein problem is a non-convex problem. It is better to consider its initialization problem as well. It is not clear about the importance of the one-step analysis for Ping-pong algorithm in the context of nonconvex optimization? Could the authors clarify it? Due to lack of space, we refer to our detailed answer in the rebuttal to Reviewer ERNU (first part).

It seems there is no discussion on the limitation. We propose to discuss the limitations of our work more clearly in a new separate paragraph, such as the problems left open, negative lower bounds and sharpness of our results, a deepened analysis of our algorithm and its initialization, the existence of computational-to-statistical gaps, and planted problems as tractable proxies for more complex problems.

We hope that our rebuttal answers the reviewer's main questions. We would greatly appreciate an adjusted review score if the concerns are lifted, and remain available for questions.

We appreciate the reviewer's feedback and questions, that will help improve the clarity of the paper. We answer the questions raised below.

Due to technical challenges, only guarantees for one step of the proposed algorithm is analyzed. This is indeed true, our analysis of the Ping-pong algorithm is indeed limited to a 1-step version. As acknowledged in the paper, we did not manage to analyze the Ping-pong algorithm in a more detailed way for two reasons: (i) the initialization is a hard problem to study (as we argue in the beginning of Section 3.2, there are no guarantees for the relaxed QAP) and (ii) the alternative minimization steps eluded our analysis so far due to the non-convexity of the minimization steps. However, it is to be noted that unlike previous results for relaxed QAP (such as for instance Valdivia and Tyagi, 2023), Proposition 1 offers recovery guarantees for non-null noise (even though the noise is required to be small enough). Deepening our understanding of the Ping-pong algorithm is a challenging work in progress.

The recovery guarantees [of the Ping-pong algorithm] are only provided in the overlap metric rather than the loss which is claimed to behave very differently when $d$ is small. For small dimensions, the overlap metric and the $c^2$ transport cost indeed behave very diffently: a guarantee in terms of $c^2$ cost cannot be translated into a guarantee in terms of overlap. However, even for small dimensions, guarantees in terms of overlap metric (as the one of Proposition 1) can be translated in terms of transport cost, since we always have $c^2(\pi,\pi') \leq \max_{i,j} \Vert x_i-x_j\Vert_2^2 \times (1-\text{overlap}(\pi,\pi'))$. For large dimensions, we have $\max_{i,j}\Vert x_i-x_j\Vert_2^2 =O(d)$ whp, while for small dimensions we have $\max_{i,j}\Vert x_i-x_j \Vert_2^2 =O(d\log(n))$ whp. We will add such a discussion in a revised version.

The dependency on the noise parameter in the statistical rates seems to be different from that of the ML estimators. This assertion is true: The ML estimator as in Wang et al., 2022 has guarantees that are expressed in terms of overlap metric, while our guarantees are expressed in terms of transport cost $c^2$, which leads to signal recovery even for noise $\sigma$ that does not tend to 0.

Are there any negative information-theoretic results, i.e., lower bounds on the costs, for the Procrustes-Wasserstein Problem of the planted model? and the tightness of the results in terms of $\sigma$ is unknown. The tightness of our results is still an open question we are working on. Hence, we thank you for your inquiry; this is indeed an interesting point. We think that the IT results in the paper are sharp, at least in small dimensions, and not far from being sharp in high dimensions. We believe that whatever the value of $d$, when $\sigma \not \to 0$, one should be able to show that the optimization problem has many solutions, and that some of them are far from the ground truth, in the $c^2$ as well as the $\ell^2$ sense.

How do the statistical guarantees for the proposed algorithm compare to the information-theoretic results? It would be nice if the authors could remark on this. The statistical guarantees for the Ping-pong algorithm (Section 3) are weaker than the information-theoretic results of Section 2. While in Section 2 we are able to recover some signal (in the $\ell^2$ and $c^2$ sense) as long as $\sigma \not \to 0$, Proposition 1 requires $\sigma\to 0$ at a polynomial rate in $n$ to recover any signal for the Ping-pong algorithm. However, experiments suggest that the Ping-pong algorithm still recovers some signal even for $\sigma=\Omega(1)$, suggesting that our analysis is suboptimal, leaving this question open for future works.

Can there possibly be computational-statistical gaps for the problem? This is a very interesting question, that we did not investigate yet. Comparing known computational results (Proposition 1 in our paper; the results from Gong and Li, 2024), there is still a gap between our informational results, and the cited computational results. However, we believe that this gap is mostly due to suboptimality of the analyses. There might be computational-statistical gaps, but investigating these would require using specific methods, for instance the low-degree methods (Hopkins, 2018, Statistical Inference and the Sum of Squares Method) that has proven to be efficient for planted recovery problems like the one we are interested in

We thank the reviewer for the thorough reading and reviewing, positive assessment, and very positive feedback which will help improve the quality of the paper in its second version. We answer the questions raised in the review below.

The analysis of the proposed ping-pong algorithm is quite limited. The one-step result provided in Proposition 1 is already an interesting step in the analysis, but it would be interesting to see a more refined analysis. Our analysis of the Ping-pong algorithm is indeed limited to a 1-step version. As acknowledged in the paper, we did not manage to analyze the Ping-pong algorithm in a more detailed way for two reasons: (i) the initialization is a hard problem to study (as we argue at the beginning of Section 3.2, there are no guarantees for the relaxed QAP) and (ii) the alternative minimization steps eluded our analysis so far due to the non-convexity of the minimization steps. However, it is to be noted that, unlike previous results for relaxed QAP (such as Valdivia and Tyagi, 2023), Proposition 1 offers recovery guarantees for non-null noise (even though the noise is required to be small enough). Deepening our understanding of the Ping-pong algorithm is a challenging work in progress.

Given the fact that the QAP problem is NP-hard it is clear that we cannot expect particularly strong results in general (e.g. convergence to global minimizer), but it may be possible to discern some properties of the matrices to which the algorithm converges or to provide a bound on the number of iterations required in certain cases. At the very least it would be useful to recall the per iteration complexity. We will recall the per iteration complexity of the Ping-pong algorithm in a revised version. For the initialization, each of the $T$ steps of Frank-Wolfe algorithm is a LAP that has complexity $O(n^3)$ (which can be reduced to $O(n)$ via entropic regularization at the cost of approximations). The SVD in the ‘Ping' step has complexity $O(d^3)$ while the LAP in the ‘Pong' step has complexity $O(n^3)$ (again, entropic regularization can reduce this to $O(n)$). The overall complexity of the algorithm is thus $O(Tn^3+ K(n^3+d^3))$ (or $O((K+T)n+ Kd^3)$ if we use entropic regularization).

We appreciate the reviewer's positive feedback and the valuable comments. We answer the question raised below.

Why is the conical alignment loss not used in practical experiments? Is it because it gives poor practical performances? The conical alignment loss is useful for informational results only, and is not used in practical experiments because its computational complexity is very high. The reason is that one has to optimize over an $\varepsilon-$net of asymptotic size $(\sqrt{d}/\varepsilon)^{d^2}$, and each evalutation on this $\varepsilon-$net has complexity $O(pn)$ where $p \geq \mathrm{polylog}(1/\sigma, d)$. This yields a total complexity which is superexponential in $d$.
In other words, the statistical performances of the conical alignment loss are strong, while its computation efficiency is not. We do however believe that the conical alignment loss could be a path towards more efficient algorithms for this problem, that could seek at approximately minimizing this loss.