CS Paper Radar

A Unified Dual Method for Matching Problems

Guillaume Houry, Ferdinand Genans, Jean Feydy, François-Xavier Vialard

cs.CG stat.ML ·submitted 2026-09-30 09:07 UTC · v1

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

Closest papers

Nearest neighbours by meaning across the whole index.

A new O(n log n) approach for the Euclidean maximum weight matching problem

cs.CG ·2026-09-07 ·Rostislav Staněk, Robert Arustamyan
similarity 0.61
Abstract

In a weighted graph $G = (V, E)$, the maximum weight matching problem (MWM) asks for a matching (i.e. pairing) of its vertices, such that each vertex is paired with at most one other vertex and the total sum of weights of all edges connecting paired vertices is maximised. If the vertices of the graph correspond to points in the Euclidean plane and the weights to their pairwise Euclidean distances, we get the Euclidean maximum weight matching problem (Euclidean MWM). The best optimum-solution algorithm for this problem runs in $O(n^{2.5})$. Furthermore, there exists an FPTAS guaranteeing a $(1 - ε)$-approximation ratio, which runs in $O(m ε^{-1} \log ε^{-1})$ time. Heuristics with a subquadratic running time (with respect to the number of vertices $|V|$) are known, but often yield solutions of a modest quality. In this paper, we present a novel algorithm for solving the Euclidean MWM running in $O(n \log n)$ time and providing excellent solution quality, especially for larger instances. In particular, in our computational tests, the algorithm yielded optimum or near-optimum solutions for all test instances; the worst observed optimality gap was less than $1.38\%$. This makes the algorithm highly attractive for practical applications, especially when exact methods become computationally prohibitive due to the size of the instance.

0.25

Discrete Gromov-Wasserstein Duality: Algorithms and Isomorphism Testing

cs.IT math.STmath.OCstat.ML ·2026-09-02 ·Gabriel Rioux, Joanna Marks, Riccardo Passeggeri, Ziv Goldfeld
similarity 0.60
Abstract · 72 pages, 6 figures, 1 table

The Gromov-Wasserstein (GW) distance provides a principled framework for aligning metric measure (mm) spaces based solely on their intrinsic structure. Its ability to identify isomorphic representations of distributions across spaces renders it valuable for comparing data where equality up to isomorphism occurs naturally such as in graphs or, more generally, distributions on graphs. Recently, a type of dual form for the GW distance between Euclidean distributions with the squared Euclidean or inner product costs was derived, spurring the development of new statistical and algorithmic results for this setting. This work furnishes a novel duality result for GW distances with and without entropic regularization that is applicable to all finitely supported mm spaces. Leveraging this result, we derive the sample complexity of empirical GW distances between finite mm spaces, as well as limit distributions under proper centering and scaling. Furthermore, we propose new algorithms for solving the regularized GW problem which are subject to formal convergence guarantees. These statistical and algorithmic advancements give rise to a principled and efficient framework for testing whether two distributions on the set of graphs with a fixed number of nodes are isomorphic based on samples.

0.36

Generalised Score Matching on Convex Domains

cs.LG stat.ML ·2026-09-10 ·Nishanth Shetty, Saisuchith Mahajan, Chandra Sekhar Seelamantula
similarity 0.60
Abstract

Score matching avoids computing the normalising constant that maximum-likelihood estimation requires. On constrained domains, its generalised variants weight the Fisher divergence so that boundary terms vanish. We derive generalised score matching on open convex subsets of $\mathbb{R}^{d}$ as the small-neighbourhood limit of minimum probability flow, in which the geometry of the neighbourhoods determines the weight. Every $C^{2}$ positive definite weight arises in this way, including those of classical score matching on $\mathbb{R}^{d}$ and of its variants for non-negative data on $\mathbb{R}_{+}^{d}$. For exponential families, we extend the standard convexity, consistency and asymptotic normality results to every such weight and show that the estimator converges to the true parameter under certain boundary conditions. For a truncated Gaussian on a polytope and a Dirichlet distribution on the simplex, proposed estimators attain the lowest median error of all methods compared, in at least 42 of 50 ground-truth configurations.

0.28

Averaged Mirror Descent and Dual Gradient Methods: Convergent Algorithms for Entropic Gromov-Wasserstein Problems

cs.LG math.OC ·2026-09-25 ·Joanna Marks, Gabriel Rioux, Riccardo Passeggeri
similarity 0.60
Abstract

The Gromov-Wasserstein (GW) distance measures the discrepancy between metric measure (mm) spaces and identifies optimal alignments between them based solely on their intrinsic structure. Since it identifies isomorphic mm spaces, it provides a natural notion of distance for heterogeneous datasets which may admit isomorphic representations. In order to accelerate computation of GW distances, many practitioners employ entropic regularization to obtain an Entropic GW (EGW) problem. The most popular EGW solver is the Mirror Descent (MD) algorithm, which reduces EGW computations to an iterative process where an entropic optimal transport (EOT) problem is solved at each iteration. Despite its widespread use, the convergence of MD for this problem has only been established for restricted classes of costs. On the other hand, a recently proposed dual gradient method is available for general costs, but requires a choice of step size which depends on the regularization parameter. To address these two issues, we introduce Averaged Mirror Descent (AMD), which averages consecutive MD steps, and prove its convergence for arbitrary costs. Then, we establish that the dual gradient method with a fixed step size also converges for arbitrary costs at the cost of a more complicated iteration. In both cases, we also account for inexact iterations which are inescapable in practice. We compare the empirical performance of these methods across various settings and, in particular, show that AMD and the dual gradient method both converge on an example where classical MD fails.

0.17

Rubix: Global Correspondence-Free Point Set Alignment through Assignment Geometry

cs.CV cs.CGcs.LGcs.RO+1 ·2026-10-07 ·Subhransu S. Bhattacharjee, Dylan Campbell, Rahul Shome
theory similarity 0.60
Abstract · 67 pages, 20 figures. Includes full proofs and experimental appendices

Procrustes-Wasserstein alignment jointly estimates a matching and rotation without supplied correspondences, but alternating minimization can stop at suboptimal solutions. Rubix solves the equally weighted planar problem globally under squared Euclidean loss. Each matching $σ$ of two centered $n$-point sets defines a complex correlation $z_σ=\sum_i\bar x_i y_{σ(i)}$. Their convex hull is the permutation polygon: supporting vertices give optimal matchings at fixed rotations, and the farthest vertex gives the global alignment. We prove the sharp bound of $n(n-1)$ vertices for $n\ge2$, answering Rote's rotation-assignment open problem. In exact arithmetic, assignment queries recover the polygon in $\mathcal O(n^5)$ operations. Assignment-based bounds extend the approach to three-dimensional rotations and partial matching at a supplied translation through branch-and-bound. On timed MPEG-7 shape pairs, Rubix attains every numerical reference value in 12 ms on average, 50 times faster than a rotation grid at the same accuracy. Its distances improve gravity-aligned matching of real 3D scans, shape retrieval and noisy crystal classification over alternating minimization.

0.25

Identifiable alignment of unpaired representations

cs.AI stat.MLcs.LGstat.ME ·2026-11-08 ·Stas Syrota, Albert Lopez I Serrano, Johanne Franck, Søren Hauberg
published similarity 0.59
Abstract · 40th Conference on Neural Information Processing Systems (NeurIPS 2026)

Aligning two models without paired data requires a distance that both share, yet existing methods use Euclidean or spherical geometry. This is either an arbitrary choice or imposed by their loss function. We show that, under a precise form of the manifold hypothesis, the pullback of the data metric gives such a distance for any two models of one data-generating process. This holds whether the models are encoders, decoders or both, and whatever their architecture, loss, prior or training data. The alignment map preserves this distance and the distribution of representations, and is identifiable if and only if the data distribution breaks every symmetry of the data manifold. We show that this symmetry breaking holds generically. Identifiability makes the alignment coupling the unique optimum of Gromov--Wasserstein and of its weighted combinations with a linear program. The linear program alone has the same optimum if almost every data point has a distinct distribution of distances. The coupling, and with it the alignment map, is recovered exactly from permuted samples, even without identifiability, and consistently from independent ones. Our method, Neural Gromov--Monge Alignment (NGMA), uses no pairs or labels and outperforms every unpaired and label-informed baseline. It relies on pullback distances to align image models with different priors and single-cell models trained on disjoint cells, where Euclidean distances fail.

0.48

Graph Matching Relaxations and Amortization for Supervised Graph Prediction

cs.LG stat.ML ·2026-09-14 ·Federico Méndez, Paul Krzakala, Gabriel Melo, Charlotte Laclau, Rémi Flamary +1 more
similarity 0.58
Abstract

End-to-end Supervised Graph Prediction (SGP) requires a permutation-invariant loss to compare predicted and target graphs with arbitrary node orderings. Such losses typically involve a costly graph-matching problem. We first study three Optimal Transport relaxations of this problem and show, theoretically and empirically, that the Gromov-Wasserstein (GW) objective is the most suitable for SGP. Then, to avoid solving the resulting inner optimization for every training example, we propose to amortize the graph matching (node alignment) problem. For each training sample, the loss function leverages a transport plan provided by a parametric matcher based on the differentiable Sinkhorn algorithm applied on empirical node distributions. The graph prediction module and the matcher are jointly learned. We showcase the efficiency of this approach on toy and real world SGP problems of increasing complexity including a novel Mass-spectra to Scaffold task that we introduce.

0.33

Matching with Multiple Bottlenecks: Parameterized Complexity and Approximation

cs.DS cs.CCcs.DM ·2026-10-05 ·Jonas Friemel, Tilo Hoitz, Phillip Keldenich, Arne Schmidt
similarity 0.58
Abstract

We consider a matching problem in which the cost of each edge is a vector with $k$ components. The cost of a matching is the sum of the bottlenecks over all components, and we ask whether there is a perfect matching of cost at most some value $Z$. This type of matching has applications in heavily synchronized job-shop scheduling problems and in reconfiguration problems, where movement is restricted to a single direction per step. In this paper, we analyze the problem from a parameterized complexity perspective and provide various results including FPT-membership for parameters $k$ and $Z$ combined, as well as W[P]-membership and W[SAT]-hardness for each of the two parameters individually. The reduction also implies para-NP-hardness parameterized by either maximum degree or treewidth. We further show hardness of approximation within a super-logarithmic factor for the optimization variant and provide a $k/d$-approximation algorithm for any constant $d \leq k$ as well as an efficient approximation scheme parameterized by $k$. With parameter $Z$, we show that no FPT-time $F(Z)$-approximation algorithm is possible for any computable function $F$, unless W[1] = FPT.

0.20