acceptodds
Under review as a conference paper at ICLR 2027

A Unified Dual Method for Matching Problems

Abstract

Matching problems are ubiquitous in data science as they enable the alignment of structured objects and distributions. While existing solvers are often tailored to specific matching formulations, we unify a broad class of such problems within a common mathematical and optimization framework based on duality theory. Theoretically, we demonstrate that matching objectives decomposable as a difference of convex (DC) functions can be recast as implicit registration problems. This connection links matching to another well-studied class of objectives and yields a dual formulation amenable to natural optimization strategies. We then apply these findings to quadratic matching (QM) problems, which admit DC decompositions and for which we provide extensive convergence guarantees. Our framework applies to Gromov-Wasserstein (GW), as well as its unbalanced formulation and several variants, which are increasingly popular QM problems. Numerically, we implement our algorithms at scale for various data modalities such as graphs, point clouds, meshes, and word embeddings. Finally, our modular approach allows us to explore new formulations such as fracture matching, broadening the scope of problems that can be addressed within this framework.

Primary area:
optimization
Keywords:
Matching, Convex duality, Optimal transport, Gromov-Wasserstein

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_LAaBOpenReview ↗
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
  1. 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?

  2. 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?

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

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

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.

  1. For these reasons, our method is a generalization of Houry et al. (2026) rather than a competitor. In particular, in shared settings, our method is strictly equivalent to this baseline: this is why we did not add direct comparisons.

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.

  1. See the answer 2. to Reviewer N63d. Experimental details and setup are provided in Appendix A.2.
Reviewer_LAaBOpenReview ↗

Official Comment by Reviewer LAaB

Theoretical concerns (Checked by GPT6.2)

  1. 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 aij=1i=ja_{ij}=\mathbf{1}_{i=j} on two source and two target points, and set k((i,j),(i′,j′))=aijai′j′k((i,j),(i',j'))=a_{ij}a_{i'j'}. This rank-one positive semidefinite kernel satisfies k((1,1),(2,2))=1k((1,1),(2,2))=1 and k((1,2),(2,1))=0k((1,2),(2,1))=0. Please revise the scope of the block-separability claim. The ordinary positive/negative spectral decomposition remains valid.
  2. Two steps in the continuous analysis need further justification. In Lemma 3 (lines 1709–1713), the proof concludes that the supremum is +∞+\infty 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 L2L^2 in L1L^1 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 RR.
  3. 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 ρ=0.1\rho=0.1, so the objective does not require a prescribed overlap fraction. How was ρ\rho selected? Was it fixed across scan pairs without access to ground-truth overlap? Showing how transported mass and registration recall vary with ρ\rho 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.

Reviewer_LAaBOpenReview ↗

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 δ\delta-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.

Reviewer_oki4OpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes a unified matching framework based on duality theory. It reformulates matching objectives with a difference of convex (DC) structure as implicit registration problems and derives their corresponding dual formulations. Building on this, the authors develop an iterative algorithm for quadratic matching (QM) and establish guarantees for convergence and approximate criticality under specific assumptions. The framework encompasses Gromov–Wasserstein (GW) matching, unbalanced GW, and various regularized variants, while its modular design allows for the reuse of different optimal transport solvers. Experiments across diverse data modalities—including graphs, point clouds, meshes, and word embeddings—demonstrate the framework's broad applicability and scalability to large-scale computations. Furthermore, the authors explore the extensibility of this framework to customized matching objectives through the example of partial fragment matching.

Critical strengths

This paper provides a comprehensive mathematical derivation; Appendix E employs certifiable guarantees to link the precision of OT subproblems, inner-loop residuals, and the criticality of outer-loop approximations. This approach is more closely aligned with practical numerical computation than analyses restricted to exact alternating optimization. The proposed method offers strong potential for scalability. By leveraging block-separable embeddings and cross-correlation computations to represent matchings implicitly, the method avoids the explicit storage of large transport matrices. Examples spanning diverse data types underscore its potential value as a general-purpose solution framework.

Critical weaknesses
  1. The paper has poor readability; it is cluttered with an excessive number of formulas and lacks the necessary logical flow or process diagrams. It merely lists equations without clearly explaining how the proposed method achieves registration(matching).
  2. The contribution is weak. Methods for solving the Gromov-Wasserstein (GW) problem have already been extensively explored in existing literature. It remains unclear what the incremental contribution of this work is, or what the scope and limitations of the proposed baseline method are.
  3. There is a lack of necessary quantitative experiments and comparisons with other methods. The paper contains only one quantitative table (Table 1) and no comparative analysis; as it stands, the experimental evaluation is incomplete.
  4. The references are generally outdated; it is recommended to incorporate more recent related work.
Questions for authors

What method does this paper employ to address matching problems? Beyond the intricate mathematical derivations, what is the paper’s overall pipeline? Furthermore, what are the innovative aspects and the limitations (boundaries) of the proposed technical approach? Which recent SOTA methods are used for comparison? Please provide comprehensive quantitative comparative experiments and ablation studies to validate the effectiveness of the proposed method.

1 comment

We acknowledge the poor readability of our article, and we updated the article to clarify the core of our contribution.

Our article does not simply propose a new Gromov-Wasserstein (GW) solver, but generalizes the literature (mainly Houry et al. (2026)) to new problems that are not tackled by existing methods. Indeed, current provably-convergent GW solvers are specific to the balanced setting and only apply to specific GW instances (squared norm or conditionally negative costs). Our method is able to solve any GW problem, both in balanced and unbalanced settings, while having (quantitative) convergence guarantees: this is a fundamentally new result. Additionally, our same method can solve previously unstudied optimization objectives, such as in the fracture matching example.

The mathematical derivations of our article (sections 2 and 3) are central to our method, as the outcome (Theorem 3) corresponds to the equations we are effectively solving in our algorithm. This theorem recasts the original problem as a nested optimization involving 3 variables: Xi, Gamma and pi. Section 4 explain how to update each variable in an iterative solver, and guarantees that these updates converge (under mild hypotheses).

Since our goal is to provide an optimization method with formal guarantees for problems that do not admit ones yet, the critical part of our work is the mathematical side. Our experiments are here to show that, besides the mathematical guarantees, our method is applicable to real problems and can be actually used on inputs of fairly large size. Since our method is the only one to tackle the unbalanced GW and non-conditionally negative GW problems with convergence guarantees, there is no baseline to compare our work with, which is why we opted for qualitative experiments. Besides, we wanted to illustrate the genericity of our pipeline, which is why we preferred to showcase its applications on various settings rather than trying to maximize the performances on specific benchmarks.

The recent GW literature mainly focuses on heuristics or is restricted the specific setups mentioned above, which is not the target of our method. This is why we did not added comparisons with recent solvers, whose focus is intrinsically different from ours.

Finally, we would like to mention that convergence guarantees are not only a theoretical preoccupation, but also have important practical implications. Indeed, they ensure that the algorithm actually stops after a finite number of steps, whereas existing solvers may be eternally trapped in an endless loop (as illustrated in appendix A.1). Such loops are unacceptable when integrating the solver in practical pipelines, even if it happens only once in a while, as it can completely disrupt downstream applications. Therefore, our work marks a necessary steps towards reliable GW methods beyond the restrictive settings covered by the current literature.

Reviewer_N63dOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a unified dual framework for regularized quadratic matching (RQM), covering Gromov–Wasserstein and its entropic, unbalanced, fused, and semi-balanced variants. Using a difference-of-convex decomposition and a Toland-type duality, the authors eliminate the transport plan π\pi and obtain an equivalent problem over low-dimensional dual variables plus the dual potential of the regularizer R. Under factorizable- and block-separable-kernel assumptions, they give explicit dual formulations and block-separable embeddings for GW-type kernels, and develop an alternating algorithm that calls any off-the-shelf R-OT solver. The method is implemented in a modular, backend-agnostic fashion and evaluated on graph matching, word-embedding alignment, shape matching, 3D point-cloud matching, and fracture reconstruction.

Critical strengths
  • The paper offers a conceptually clean and genuinely unifying view of quadratic matching. By separating the non-convex part of the objective from the convex optimal-transport part, it decouples the choice of regularizer from the choice of kernel.
  • The convergence and complexity analysis, including the end-to-end guarantees for the entropic unbalanced case, fills a gap left by widely used methods that lack such guarantees.
  • The method is modular, scales to non-trivial problem sizes, and applies to several different matching regimes without redesign.
Critical weaknesses
  • The paper motivates a unified framework mainly by noting that GW variants are fragmented across separate solvers, but it gives no concrete instance of the problem this fragmentation causes. As a result, the “unified” framing reads more like a design preference than a demonstrated need. Pointing to a specific setting where the lack of a shared solver impedes comparison or reproduction would make the motivation much stronger.

  • Since the baseline times are taken from Alvarez-Melis & Jaakkola (2018) without specifying the hardware, while OURS is measured on an RTX6000, the “almost 20× faster” claim may partly reflect hardware differences rather than algorithmic improvements alone.

  • Convergence guarantees and algorithmic description are not aligned. The quantitative guarantees (Theorems 5, 12, 13 and Corollaries 1–2) are stated under specific conditions—entropic regularization, step size τ=1/L, boundedness of the dual iterates, and L-smoothness/strong concavity of hΓh_Γ—but Algorithm 1 accepts an arbitrary step size τ and the main text does not state when these conditions hold or how τ should be chosen.

Questions for authors

see the weaknesses

1 comment

We thank the reviewer for its feedback. Here are the answer to the mentioned weaknesses:

  1. Designing a shared solver for several problems has two main benefits:
  • It allows to easily transfer numerical techniques from one problem to another. In our case, since our computations are based on optimal transport (OT) resolutions, we can apply all the computational OT methods (multiscaling, sparsity techniques, memory-efficient backends...) to quadratic matching without additional effort.
  • We can tackle new optimizations objective without having to rewrite the whole solver: the fracture example (in the experiment part) illustrates this property, the function we minimize in this application being new and not solvable by any existing method.

Besides, our initial goal (which was not clearly stated in the initial version of our article) is to solve unbalanced GW and GW with arbitrary costs in a theoretically-grounded way, something that was not addressed by the literature. Our method allows to solve both, with convergence guarantees, using the same algorithm.

  1. About the result from Alvarez-Melis & Jaakkola (2018): after reimplementing their method on the same hardware, the running time of the baseline drops to 300s. Our method remains more competitive, although from a smaller margin. Also, we forgot to mention that our technique is significantly more memory-efficient: the baseline requires dozens of gigabytes of memory to run, preventing its usage on larger datasets or more modests GPUs. Our method is not subject to this limitation, its memory usage scaling linearly with the input size.

  2. Indeed, algorithm 1 can be applied in any setting, but convergence is only guaranteed under the conditions stated in our theorems. We presented things this way to keep the algorithm simple and to clearly indicate that the Xi updates follows a gradient descent. Under weaker conditions, other gradient descent schemes (e.g. adaptive step size) could be used to ensure convergence, although we did not explore this setting; over-detailing our algorithm would make the intuition behind this Xi-step less clear.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.