- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper presents a unified framework for matching problems whose objectives can be written as a difference of convex functions. It connects these problems to implicit registration and develops a dual formulation. For quadratic matching, the authors introduce an alternating optimization algorithm with convergence guarantees under stated assumptions. The framework supports balanced, unbalanced, and fused Gromov–Wasserstein problems. Experiments cover graph matching, word embedding alignment, partial shape matching, point cloud matching, and fracture matching.
Critical strengths
First, the framework provides a common formulation for several matching problems and allows different regularized optimal transport solvers to be used within the same algorithm. This modular design could reduce the effort needed to implement new matching objectives. Second, the analysis explicitly considers inexact inner updates, which are important in practical implementations. The appendix also gives concrete examples where the standard EGW solver oscillates while the proposed method converges. These examples provide useful evidence for the motivation behind the new solver.
Critical weaknesses
1. The additional contribution beyond existing matching-to-registration and dual GW methods is not sufficiently supported by targeted experiments.
The connection between GW matching and registration in a lifted feature space has already been studied. A particularly relevant work is “Gromov-Wasserstein at Scale, Beyond Squared Norms,” by Guillaume Houry, Jean Feydy, and François-Xavier Vialard, published at ICML 2026. It already develops a lifted-space alignment formulation and a scalable GW solver with theoretical guarantees.
The current submission cites this work, so the issue is not a missing reference. The important question is what the broader DC formulation and the additional optimization variables provide beyond that earlier approach. The generalization may be mathematically useful, but its practical importance needs clearer evidence.
The appendix includes small examples with oscillating EGW updates and a nonstandard cost. These examples support the need for a more reliable optimization method. However, they do not establish how often the problem occurs in realistic applications or how much the broader formulation improves matching quality, runtime, or robustness.
A direct comparison with the 2026 method on problems supported by both approaches is missing. For problems outside the earlier method’s scope, the paper should show that the additional generality leads to useful results at a reasonable computational cost. The current experiments demonstrate broad applicability, but do not sufficiently isolate the value of the new generalization.
2. The evaluation does not establish a strong advantage in matching quality or computational efficiency over current methods.
The graph experiment mainly compares against EGW from 2016 and a low-rank solver from 2022. The reported “accuracy” is an objective value rather than the accuracy of recovered node correspondences. Appendix A.2 states that the target graphs are generated by adding noisy edges to source graphs, so ground-truth correspondences are available. Reporting correspondence accuracy would provide a more direct test of whether the solver produces useful matches. The paper also notes that EGW remains competitive in runtime in this setting. For word embedding alignment, Table 1 reports 90 seconds for the proposed 300-dimensional solver and 2,220 seconds for the baseline. However, the table explicitly states that the baseline results are taken from the 2018 study. This does not establish the speed advantage under the same hardware, implementation, and stopping conditions. The translation results show some improvements over that baseline, but comparison with a single older method does not establish current SOTA performance.
The remaining applications are mainly evaluated through visual examples. Partial shape matching lacks a quantitative correspondence-error comparison. The large point cloud example takes about 30 minutes for inputs containing 100,000–200,000 points, but no matched runtime and accuracy comparison is provided. Fracture matching takes several hours and uses the best coarse result from 30 random initializations. This shows that the framework can handle the formulation, but leaves its reliability and practical efficiency unclear. Finally, the practical implementation uses dimension reduction, multiscale initialization, warm starts, and early stopping. These are reasonable choices, but their effects are not sufficiently separated. Controlled comparisons are needed to show how much of the practical improvement comes from the new dual method rather than these acceleration techniques.
Questions for authors
-
What are the main additional capabilities beyond Houry et al. (2026)? Can the authors provide direct comparisons on shared settings and quantitative results on realistic settings that require the broader DC formulation?
-
Can the graph experiments report ground-truth correspondence accuracy in addition to the objective value? How sensitive are the results to noise, initialization, and embedding dimension?
-
Can the word-alignment runtime comparison be repeated under the same hardware, implementation, and stopping conditions? Please also clarify which preprocessing and initialization costs are included.
-
Can the authors provide quantitative matching errors and runtime comparisons for the shape, point cloud, and fracture applications? For fracture matching, please report variation across initializations and the total computational cost.
4 comments
Official Comment by Reviewer LAaB
Theoretical concerns (Checked by GPT6.2)
- Appendix B.2 (lines 1078–1082) claims that applying an SVD to each feature matrix yields a block-separable factorization for any finite quadratic matching kernel. Under Definition 2, each block contributes a product of a source Gram kernel and a target Gram kernel. Any signed sum of such products is invariant under exchanging the two target indices. A finite kernel can violate this symmetry. For example, let on two source and two target points, and set . This rank-one positive semidefinite kernel satisfies and . Please revise the scope of the block-separability claim. The ordinary positive/negative spectral decomposition remains valid.
- Two steps in the continuous analysis need further justification. In Lemma 3 (lines 1709–1713), the proof concludes that the supremum is whenever it is unattained. In infinite dimensions, the supremum can be finite and unattained, so this argument does not establish the claimed domain of the conjugate. In Proposition 2 (lines 1849–1853), density of in alone does not establish equality of the two infima. The proof needs an approximation that preserves feasibility and recovers the objective value, including the regularizer .
- Lines 369–374 report empirical stability with one warm-started Sinkhorn update per dual-potential update. Theorems 5–6 require accuracy and stopping conditions for the inner solves. When using the single-update schedule, did the authors check whether those conditions were met? Reporting the observed inner-solver errors would clarify which guarantee applies in practice. Requested experiments
As a point-cloud registration researcher, I am particularly interested in fused unbalanced GW for outlier rejection under partial overlap. The geometric term in Figure 5 penalizes discrepancies between approximate within-cloud distances. Since rigid transformations preserve Euclidean distances, this gives the method a plausible way to identify geometrically inconsistent matches across scenes. I would consider the reported runtime of roughly 30 minutes reasonable if the method reliably registered scans at the reported scale of 100k–200k points. The 100 correspondences sampled for visualization do not establish that accuracy.
- Outlier rejection. On a benchmark such as 3DMatch and its low-overlap counterpart 3DLoMatch, please compare against Heng Yang et al.’s GNC-TLS on a common set of candidate correspondences. Explain how the GW coupling assigns a score to each candidate, whether it uses pairs outside the candidate set, and how inliers are selected. Report inlier precision and recall against the ground-truth pose. A comparison with a learned outlier-rejection method on a dataset outside its training domain would also test the potential generalization advantage.
- Rigid registration. Please compare the pose recovered from the GW coupling with a pipeline that generates tentative correspondences and passes them to TEASER++. Use the same sampled clouds and the same available feature information, and describe how each pipeline obtains its pose. Report rotation error, translation error, and registration recall across overlap levels, together with the point and correspondence counts.
- Unknown overlap. Appendix A.2 uses soft marginal KL penalties with , so the objective does not require a prescribed overlap fraction. How was selected? Was it fixed across scan pairs without access to ground-truth overlap? Showing how transported mass and registration recall vary with across overlap levels would clarify how the method performs when overlap is unknown.
I hope the authors will carefully examine the theoretical concerns raised above and correct any errors they find in the final version of the paper.
Official Comment by Reviewer LAaB
I appreciate the clarification that the intended novelty is a unified dual framework covering both balanced and unbalanced GW with general pairwise structure costs. I suggest narrowing the priority claim ("for the first time") accordingly. For finite, unregularized balanced GW, the objective is quadratic over a compact transport polytope, so standard nonconvex Frank–Wolfe theory already provides an approximate stationarity guarantee without requiring conditionally negative costs (Lacoste-Julien, 2016). Earlier work also studied convergence for a two-plan relaxation of unbalanced GW (Séjourné et al., 2021). It would help to specify which combination of objective, cost assumptions, and convergence guarantee is new here. I also suggest replacing “finds local solutions” with the precise conclusion of Theorems 5–6: under the stated inner-solver conditions, the algorithm terminates with a -critical plan.
We thank you for your valuable suggestions and remarks. We will modify our manuscript accordingly and correct the theoretical claims as needed. While we do not have time to implement the proposed experiments, we appreciate your interest in our method and we plan to apply it on specialized applications in a future work.
A last remark: Franke-Wolfe methods are indeed applicable for Gromov-Wasserstein (and have been used in several works), but they are not compatible with entropic regularization and the Sinkhorn algorithm cannot be used directly with Franke-Wolfe (as discussed in Houry and al. (2026)). We will explicit this point in the article.
We thank the reviewer for its relevant and exhaustive comments.
We realized that the core contribution of our method was not clearly explained. Existing algorithms, including the solver of Houry and al. (2026), are specific to the original Gromov-Wasserstein (GW) problem (in the balanced setting) and only apply to specific GW instances (squared norm or conditionally negative costs). Our initial goal was to solve GW with arbitrary costs, in both balanced and unbalanced settings, in a numerically stable way. Before our work, there was no solver tackling these instances for which convergence was guaranteed, and appendix A.1. shows that existing methods are indeed unstable on some inputs and may get stuck in infinite loops. Our method is specifically designed to fill this gap, providing an algorithm that finds local solutions of arbitrary-cost GW, balanced and unbalanced, which is guaranteed to terminate. We added a paragraph in our article to clarify this aspect of the contribution.
Besides these problems, our algorithm can also solve more general matching objectives: we applied this to fracture matching, where the function that we optimize has never been studied before and that does not admit any other existing solver.
2/4. Since our work aims to design a provably-convergent method for a new category of problems, we chose to keep experiments as qualitative as possible to show that it provides satisfying solutions on medium- to large-scale problems in a "reasonable" time, rather than focusing on quantitative evaluation and complex ablation studies. We could provide more metrics, but these would require to re-run all the experiments, and adding more quantitative evaluations would blur the motivation behind these experiments, which is to show the applicability of our solver on problem previously unaddressed by the literature.