M IN G ENERALIZED S LICED G ROMOV-WASSERSTEIN : A S CALABLE PATH TO G ROMOV –WASSERSTEIN
Ashkan Shahbazi∗,1
Xinran Liu∗,1
Ping He1
Soheil Kolouri1,2
arXiv:2605.13753v1 [cs.LG] 13 May 2026
1
Department of Computer Science, College of Connected Computing, Vanderbilt University 2 Department of Electrical and Computer Engineering, Vanderbilt University {ashkan.shahbazi, xinran.liu, ping.he, soheil.kolouri}@vanderbilt.edu
A BSTRACT We propose min Generalized Sliced Gromov–Wasserstein (min-GSGW), a sliced formulation for the Gromov–Wasserstein (GW) problem using expressive generalized slicers. The key idea is to learn coupled nonlinear slicers that assign compatible push-forward values to both input measures, so that monotone coupling in the projected domain lifts to a transport plan evaluated against the GW objective in the original spaces. The resulting plan induces a GW objective value, and min-GSGW minimizes this cost directly in the original spaces. We further show that min-GSGW is rigid-motion invariant, a crucial property for geometric matching and shape analysis tasks. Our contributions are threefold: 1) we introduce generalized slicers into the sliced GW framework, 2) we construct a slicing-based efficient GW transport plan; and 3) we develop an amortized variant that replaces perinstance optimization with a learned slicer for unseen input pairs. We perform experiments on animal mesh matching, horse mesh interpolation, and ShapeNet part transfer. Results show that min-GSGW produces meaningful geometric correspondences and GW objective values at substantially lower computational cost than existing GW solvers. Keywords Gromov-Wasserstein, Optimal Transport, Shape Matching
1
Introduction
Modern machine learning increasingly requires comparing objects without a common ambient space, arising in shape analysis, graph matching, biological data integration, and representation comparison, where the relevant signal lies in pairwise intra-domain geometry rather than absolute coordinates. Gromov–Wasserstein (GW) addresses this by comparing metric measure spaces through couplings that preserve internal geometry, making it a central tool for structureaware matching [15, 17]. Despite these strengths, GW remains computationally expensive. In the discrete setting it is a nonconvex quadratic program over couplings, and practical solvers are substantially costlier than classical OT. This has motivated scalable alternatives including entropic, low-rank, semidefinite, and sliced formulations [24, 19, 4, 16]. Sliced GW is especially appealing because it reduces the problem to repeated one-dimensional comparisons admitting O(n log n) sorting primitives [24]. However, this reduction requires care: existing sliced GW methods replace the one-dimensional GW subproblem with monotone matching, which does not solve the one-dimensional GW problem exactly. Counterexamples show that neither the identity nor the anti-identity permutation is optimal for the relevant one-dimensional assignment problem in general [1, 7]. The efficiency of sliced GW therefore comes from limiting the coupling family to those producible by linear projections, not from exactly solving a one-dimensional subproblem [26]. This exposes three coupled limitations of existing sliced GW formulations. First, the error from monotone matching is tied to the projection family and cannot be eliminated within a purely linear slicing scheme. Second, independently chosen projections for two spaces need not be compatible with a meaningful structural alignment. Third, and perhaps most critically for practical use, the monotone plans produced in the projected space offer no reliability guarantees when lifted back to the original measures: there is no reason in general to expect such a plan to be close to the GW-optimal coupling with respect to the original geometry. As a result, prior sliced GW methods are best understood as alternative * Equal contribution.
min-GSGW
distance objectives rather than methods that minimize GW directly. Recent max–min formulations partially address the second issue by coupling slicers adversarially and recovering invariance properties, but they still rely on monotone one-dimensional matchings and do not resolve the plan reliability problem [16]. We propose min Generalized Sliced Gromov–Wasserstein (min-GSGW), which replaces linear projections with nonlinear slicers learned through a shared latent construction with lifting. The key insight is that the limitation of monotone matching lies not in sorting itself, but in the linear slicer class. Linear projections can only induce couplings over a narrow family of matchings; by contrast, nonlinear slicers warp the push-forward ordering so that sorting the resulting push-forward values induces a coupling in the original metric spaces — one that can reach regions of the coupling space unavailable to linear projections. This is the mechanism by which min-GSGW retains O(n log n) plan extraction while producing substantially richer couplings than the linear sliced family. Empirically, these plans frequently achieve GW objective values competitive with those of more expensive iterative solvers such as Frank–Wolfe [9] and Sinkhorn [6], and sometimes better — consistent with GW’s nonconvexity, where iterative solvers are not guaranteed to find globally optimal couplings. We first formulate min-GSGW as a per-instance optimization, then extend it to an amortized setting where a learned predictor outputs couplings directly for unseen pairs via a forward pass. Our main contributions are as follows: • We introduce min-GSGW, a generalized sliced GW formulation that couples two slicers through a shared map and lifting, inducing transport plans directly in the original metric spaces by sorting the resulting push-forward values. The nonlinearity of the slicers allows the induced couplings to reach regions of the coupling space unavailable to linear projections, yielding lower GW objective values within this slicer-induced family. • We establish structural properties of min-GSGW, including rigid motion invariance, and optimize the objective with a differentiable sorting relaxation based on LapSum [21]. • We develop an amortized variant replacing per-instance optimization with a learned slicer for new input pairs. • We validate on shape matching [22], horse shape interpolation [20], and amortized ShapeNet part segmentation [2], where min-GSGW achieves GW values on par with or better than substantially more expensive iterative solvers.
2
Related Work
Our work lies at the intersection of sliced GW formulations and sliced OT plan construction. Classical GW solvers use conditional-gradient and entropic local optimization, making the quadratic matching problem practical but requiring iterative dense coupling updates [17, 20, 8]. Low-rank, sampled, and relaxation-based methods improve scalability or provide alternative formulations [19, 10, 4, 26, 5, 25, 23]. Sliced GW replaces the full matching problem with one-dimensional projected objectives built from monotone matching [24], though monotone matching does not solve the one-dimensional GW problem exactly [1]. Max–min formulations address the incompatibility of independently chosen projections and recover stronger invariance properties, but remain distance objectives defined in projected space rather than plan-producing GW minimizations [16]. A parallel line uses slicing to construct explicit transport plans via monotone one-dimensional matchings, including min-sliced, generalized sliced, expected sliced, and amortized sliced plan formulations [12, 11, 13, 18, 3]. Our method lies at the intersection: like sliced OT plan methods, it constructs couplings from slicer push-forward values via monotone matching; unlike projected sliced GW objectives, it evaluates and optimizes this coupling against the original GW loss in the original metric spaces. min-GSGW thus directly minimizes GW over the family of slicer-induced couplings, yielding an upper bound on GW whose tightness grows with the expressivity of the slicers. The amortized variant uses learning to amortize plan construction across instances rather than to replace the geometric objective.
3
Preliminaries and Background
Gromov–Wasserstein. Let (X, dX , µ) and (Y, dY , ν) be metric measure spaces, with µ ∈ P2 (X) and ν ∈ P2 (Y ). Since X and Y need not coincide, there is in general no canonical cross-space cost, and the Wasserstein construction is not directly applicable. The Gromov–Wasserstein discrepancy instead compares the internal geometries of the two spaces. Its quadratic form is ZZ 2 GW2 (µ, ν) := inf dX (x, x′ ) − dY (y, y ′ ) dπ(x, y) dπ(x′ , y ′ ). (1) π∈Π(µ,ν)
(X×Y )2
2
min-GSGW
Pn Pm In the discrete setting, let µ = i=1 ai δxi and ν = j=1 bj δyj with a ∈ ∆n , b ∈ ∆m , and define the intra-space Y distance matrices CiiX′ := dX (xi , xi′ ) and Cjj ′ := dY (yj , yj ′ ). The GW loss at a coupling π ∈ Π(a, b) is X Y 2 LGW (µ, ν; π) := CiiX′ − Cjj πij πi′ j ′ , (2) ′ i,i′ ,j,j ′
and the squared GW distance is GW2 (µ, ν) = LGW (µ, ν; π ∗ ), where π ∗ := arg minπ∈Π(a,b) LGW (µ, ν; π). This is a nonconvex quadratic program that is NP-hard in general, with a naive O(n4 ) implementation, motivating scalable approximations. Sliced GW and its limitations. With X ⊂ Rp and Y ⊂ Rq , sliced GW projects to the real line and averages. Let d := max(p, q) and let ιX : Rp ,→ Rd , ιY : Rq ,→ Rd be the canonical zero-padding embeddings (appending d − p or d − q zeros, respectively). For θ ∈ Sd−1 , define linear projections Pθ,X := ⟨θ, ιX (·)⟩ and Pθ,Y := ⟨θ, ιY (·)⟩ with pushforward measures (Pθ,X )# µ and (Pθ,Y )# ν on R. The shared-direction SGW of [24] is h i θ SGWshared (µ, ν) := Eθ∼σ LGW (Pθ,X )# µ, (Pθ,Y )# ν; πsort , (3) θ where πsort is the monotone coupling of the two projected measures (via sorting).
One limitation of this formulation is that it is not rotation-invariant. To mitigate this issue, a naive workaround is to sample projection directions independently for the two spaces. This leads to the independent-direction variant: let σX and σY denote the uniform distributions on the spheres Sp−1 and Sq−1 , respectively, and sample ψ ∼ σX and ϕ ∼ σY independently. This yields h i ψ,ϕ SGWindep (µ, ν) := Eψ∼σX , ϕ∼σY LGW (Pψ )# µ, (Pϕ )# ν; πsort , (4) ψ,ϕ where Pψ := ⟨ψ, ·⟩ and Pϕ := ⟨ϕ, ·⟩ are the standard linear projections on X and Y , respectively, and πsort is the 1-D monotone coupling between the projections by ψ and ϕ. The primary limitation is that this formulation violates the identity of indiscernibles. Pan et al. [16] address this issue by coupling the two projections through a max-min game. Let Ψ := {⟨ψ, ·⟩ : ψ ∈ Sp−1 } and Φ := {⟨ϕ, ·⟩ : ϕ ∈ Sq−1 } be the classes of (linear) slicers on X and Y . Rather than sampling ψ and ϕ independently and taking the expectation, they solve the following max-min game: ψ,ϕ sup inf LGW ((Pψ )# µ, (Pϕ )# ν; πsort ),
ψ∈Ψ ϕ∈Φ
(5)
where the outer player selects ψ to expose structural discrepancy and the inner player best-responds with ϕ. Symmetrizing yields n o ψ,ϕ ϕ,ψ max sup inf LGW ((Pψ )# µ, (Pϕ )# ν; πsort ), sup inf LGW ((Pϕ )# ν, (Pψ )# µ; πsort ) . (6) ψ∈Ψ ϕ∈Φ
ϕ∈Φ ψ∈Ψ
While these formulations address some of the shortcomings of naive independent sampling, two fundamental limitations remain common to sliced GW approaches. First, the monotone arrangement is in general not the optimal coupling for the one-dimensional GW problem [1]. Second, they provide no matching/coupling information.
4
Method
We propose min Generalized Sliced Gromov–Wasserstein (min-GSGW), a novel sliced approach to GW that defines a transport plan. It optimizes an objective induced by a transport plan constructed in three steps as shown in 1: (1) lift the lower-dimensional measure to the higher-dimensional space via a measurable map, rather than a rigid embedding in [24]; (2) apply non-linear slicing to both measures; and (3) compute the transport plan between one-dimensional projections via a flexible non-linear rearrangement, followed by a monotone matching. Importantly, although our method still relies on monotone matching, the use of non-linear rearrangement mitigates the limitation that 1D GW plans cannot be recovered from monotone rearrangements in general. p q Sliced Gromov–Wasserstein P Pmvia generalized slicers. Let X ⊂ R , Y ⊂ R . Consider discrete measures µ = n i=1 ai δxi on X and ν = j=1 bj δyj on Y , where a ∈ ∆n and b ∈ ∆m . Without loss of generality, assume p ≤ q, so that Y is the higher-dimensional space. Let H be a class of measurable liftings h : X → Y , and let F be the class of slicers f : Y → R . For (f, h) ∈ F × H, define
si := (f ◦ h)(xi ), 3
tj := f (yj ).
min-GSGW (a) Two metric spaces
(b) Lifting h, nonlinear slicing f
(c) Gromov plan π f, h
? X⊂ 2
X⊂ 2
Y⊂ 3
Y⊂ 3
π f, h = PX> PY
Figure 1: Overview of min-GSGW. (a) Two metric measure spaces µ on X ⊂ Rp and ν on Y ⊂ Rq with q ≥ p. (b) A learned lifting h : X → Y maps source points into the target domain; a shared nonlinear slicer f ∗ : Y → R then assigns push-forward values to both lifted source points h(xi ) (circles) and target points yj (squares). Level curves of f ∗ induce a monotone ordering on both sets. (c) Sorting the two push-forward sequences and matching them into a feasible transport coupling π f,h , whose GW objective is minimized over the learned family of slicer-induced couplings. ∗ Denote by πf,h (µ, ν) the coupling between µ and ν that is lifted from the optimal GW coupling between {si }ni=1 and m {tj }j=1 , then we derive an objective
inf
f ∈F ,h∈H
∗ LGW (µ, ν, πf,h )
(7)
However, this formulation does not improve computational efficiency, as it still requires solving a one-dimensional GW problem. To mitigate this issue, we propose to approximate the 1D GW plan by composing a non-linear rearrangement with a monotone coupling. ∗ Approximating the 1D Gromov-Wasserstein solution. Instead of solving the 1D GW problem to obtain πf,h (µ, ν), we look for a measurable function ξ ∗ : R → R that could be non-linear and achieves ξ inf LGW ((f ◦ h)# µ, f# ν, π̂f,h ), ξ
(1D problem)
(8)
ξ for a given pair of f and h, where π̂f,h denotes the monotone coupling between 1D measures ξ# ((f ◦ h)# µ) and ξ# (f# ν) via sorting. Pn Pm 1 Proposition 1 (Representation of the 1D GW plan). Let µ = n1 i=1 δxi , ν = m j=1 δyj be probability measures Y 2 on R, with n = m, uniform weights, with the squared Euclidean cost CiiX′ = d2X (xi , xi′ ) and Cjj ′ = dY (yj , yj ′ ). Then there exists an optimal Gromov–Wasserstein plan π ∗ ∈ Π(µ, ν) that is induced by a permutation σ ∈ Sn , i.e. n
π∗ =
1X δ(x ,y ) . n i=1 i σ(i)
Moreover, there exists a nonlinear map ξ : R → R such that the monotone coupling between ξ# µ and ξ# ν induces the same permutation σ. Equivalently, n 1X π∗ = δ(x ,y ) = π mon (ξ# µ, ξ# ν) n i=1 i σ(i) after identifying each projected point with its preimage in the original supports. Proof. By [24][Theorem 3.2], the GW problem is equivalent to the Gromov-Monge problem [14]: 2 1 X X C (xi , xj ) − C Y yσ(i) , yσ(j) GM2 (µ, ν) = min 2 σ∈Sn n i,j Therefore, the GW plan is induced by a permutation map σ ∗ . Now ξ : R → R can be constructed by interpolating on the finite set {xi }ni=1 ∪ {yj }nj=1 , assigning values that realize 4
min-GSGW
ξ(x1 ) < ξ(x2 ) < · · · < ξ(xn ); and ξ(yσ∗ (1) ) < ξ(yσ∗ (2) ) < · · · < ξ(yσ∗ (n) ). Hence π ∗ = π mon (ξ# µ, ξ# ν). Consequently, (8) recovers the 1D GW distance under the assumptions in Proposition 1. Now, rather than nesting (8) into (7) as a bilevel optimization problem, we propose to jointly optimize f, h and ξ, i.e., the optimization problem becomes ξ inf LGW (µ, ν, πf,h ) (9) f,h,ξ
ξ ξ where πf,h is the lifted plan from π̂f,h . ξ Absorbing the 1D rearrangement into the slicer. Observe that πf,h corresponds to the monotone coupling between (ξ ◦ f ◦ h)# µ and (ξ ◦ f )# ν. Since ξ and f only appear through their composition, we treat ξ ◦ f as a single generalized slicer, i.e., the non-linearity of ξ : R → R can be absorbed into the generalized slicer f : Rd → R. With a slight abuse of notation, we denote this composition ξ ◦ f by f : Rd → R as this relabeling does not affect the formulation under the assumption that such composition keeps the underlying function classes unchanged.
4.1
min Generalized Sliced Gromov–Wasserstein
With the above in place, we now introduce the min Generalized Sliced Gromov–Wasserstein (min-GSGW) problem: mon min-GSGW(µ, ν) := inf LGW (µ, ν, πf,h ) f,h
(10)
mon where πf,h denotes the lifted plan from the 1D monotone coupling between (f ◦ h)# µ and f# ν. See Figure 1. In the following, we provide some properties of min-GSGW. Proposition P 2 (Rigid motion invariance). Let E(d) denote the Euclidean group acting on Rd . Let X ⊂ Rp and Y ⊂ Rq . Pm n And let µ = i=1 ai δxi be a discrete measure on X and ν = j=1 bj δyj on Y , where a ∈ ∆n and b ∈ ∆m . Assume that F and H are stable under rigid motions: for all (f, h) ∈ F × H, gX ∈ E(p), and gY ∈ E(q),
f ◦ gY−1 ∈ F,
−1 gY ◦ h ◦ gX ∈ H.
Then min-GSGW(gX# µ, gY # ν) = min-GSGW(µ, ν). Proof. We start by showing min-GSGW(gX# µ, gY # ν) ≤ min-GSGW(µ, ν). −1 For any given (f, h) ∈ F × H, let f˜ := f ◦ gY−1 and h̃ := gY ◦ h ◦ gX . By stability of F and H, (f˜, h̃) ∈ F × H. −1 For any support points x̃ = gX x and ỹ = gY y in the pushforward measures gX# µ and gY # ν, we have x = gX x̃ and −1 y = gY ỹ by the invertibility of gX and gY . Hence
f˜(ỹ) = f (y),
f˜(h̃(x̃)) = f (h(x)).
That is, f˜ and h̃ are chosen so that the projected values are preserved pointwise. Hence, the induced one-dimensional mon monotone coupling is the same in both constructions and the lifted coupling matrices coincide: πfmon ˜,h̃ = πf,h . Besides, the pairwise distances inside each space C X and C Y are preserved by rigid motions, so f˜, h̃ will result in the same objective value as f, h: mon LGW (gX# µ, gY # ν, πfmon ˜,h̃ ) = LGW (µ, ν, πf,h ). As this applies to any (f, h) ∈ F × H, we conclude min-GSGW(gX# µ, gY # ν) ≤ min-GSGW(µ, ν). Similarly, we can obtain min-GSGW(µ, ν) ≤ min-GSGW(gX# µ, gY # ν), and therefore min-GSGW(µ, ν) = min-GSGW(gX# µ, gY # ν).
5
min-GSGW
Relation to GW. Since each π f,h is a feasible coupling for uniform empirical measures, min-GSGW is an upperbound approximation to GW in that setting. Let π ∗ ∈ arg minπ∈Π(a,b) LGW (µ, ν; π) be an optimal GW coupling. Then, for every (f, h) ∈ F × H, LGW (µ, ν; π ∗ ) ≤ LGW (µ, ν; π f,h ). Taking the infimum over (f, h) ∈ F × H gives GW2 (µ, ν) = LGW (µ, ν; π ∗ ) ≤ inf LGW µ, ν; π f,h = min-GSGW(µ, ν). (11) f ∈F , h∈H
If the restricted family {π f,h : f ∈ F, h ∈ H} contains an optimal GW plan, then the bound is tight. 4.2
Numerical Implementations
f,h f,h Let PX ∈ Rn×n and PYf ∈ Rm×m be the permutation matrices for σX ∈ Sn and σYf ∈ Sm that sort s = (s1 , . . . , sn ) and t = (t1 , . . . , tm ) in nondecreasing order. The transport plan is obtained by monotone matching of the sorted values. For unequal cardinalities, let Tn,m ∈ Rn×m be the canonical monotone interpolation matrix with entries + h i h i j−1 j i (Tn,m )ij := λ i−1 , n , n ∩ m , m 1 ⊤ where λ is the one-dimensional Lebesgue measure. Then Tn,m 1m = n1 1n and Tn,m 1n = m 1m , so Tn,m preserves uniform marginals while interpolating monotonically between sorted empirical grids. The hard plan induced by (f, h) is f,h ⊤ π f,h := (PX ) Tn,m PYf ,
(12)
1 1 and feasibility follows immediately: π f,h 1m = n1 1n and (π f,h )⊤ 1n = m 1m , so π f,h ∈ Π( n1 1n , m 1m ). When f,h ⊤ f 1 1 f,h n = m, Tn,n = n In so (12) simplifies to π = n (PX ) PY . The scores determine the coupling, while the loss is evaluated on the original intra-space costs C X and C Y . Our discrepancy is min-GSGW(µ, ν) := inf LGW µ, ν; π f,h , (13) f ∈F , h∈H
minimizing the GW objective over score-induced couplings rather than all of Π(a, b). f,h Differentiable relaxation. Since PX and PYf are not differentiable, during training we replace them with soft f,h f sorting matrices PX,τ ∈ [0, 1]n×n and PY,τ ∈ [0, 1]m×m via a differentiable relaxation such as LapSum [21]; as f,h ⊤ f τ is annealed these converge to the hard permutations. The soft plan is πτf,h := (PX,τ ) Tn,m PY,τ , reducing to f,h ⊤ f f,h f 1 f,h f,h πτ = n (PX,τ ) PY,τ when n = m. If PX,τ and PY,τ are doubly stochastic, πτ inherits the correct uniform marginals. During training we optimize inf LGW µ, ν; πτf,h , (14) f ∈F , h∈H
and at inference we use the hard plan π f,h . 4.3
Computational complexity
Our method induces a transport plan by sorting slicer push-forward values, costing O(n log n) excluding the slicer forward pass, with the same construction used during training via the differentiable LapSum relaxation. Sliced baselines range from O(Ln log n) (SGW) to O(L2 n log n) (MSGW), while dense GW solvers (POT-GW, entropic GW) incur cubic per-iteration cost due to the quadratic GW tensor contraction. Figure 2 reports wall-clock runtimes on an RTX A6000 averaged over 10 runs, confirming that our method scales most favorably among such methods after its training.
5
Experiments
We evaluate min-GSGW on animal mesh matching, horse shape interpolation, and amortized ShapeNet matching. The results are averaged over three runs. Toy correspondence experiments are deferred to Appendix B, and implementation details, hyperparameters, and reproducibility information are given in Appendix C. Full ablations over linear vs. nonlinear slicers and independent vs. dependent slicers are deferred to Appendix A; the soft sorting temperature is annealed during training across all variants. 6
min-GSGW
Runtime complexity
POT-GW Sinkhorn SGW MSGW RI-SGW Ours
NP-hard; O(n4 ); O(n3 ) O(n4 ); O(n3 ) O(Ln log n) O(L2 n log n) O niter Ln(p + log n) + p3 O(n log n)
POT-GW Sinkhorn SGW MSGW RI-SGW Ours
105
Runtime complexity and empirical scaling. Wall-clock times are averaged over 10 runs for N ∈ {100 : 5000}. MSGW runs out of memory beyond N = 1000, while our method has the lowest complexity and favorable scaling.
Wall-clock time (ms)
Method
104 103 102 101 100 102
5.1
N
Realistic Shape Matching
103
Following [4], we evaluate on a realistic shape matching benchmark derived from [22], where each shape is represented by a geodesic distance matrix with uniform weights. Since each method optimizes a different surrogate of the GW objective„ we instead evaluate via geodesic error — the Princeton protocol metric [20]: the mean normalized geodesic distance between predicted and ground-truth correspondences, which directly measures geometric accuracy independent of each method’s internal objective. We compare against POT, Sinkhorn, LR-GW [19], SDP-GW [4], and SaGroW [10], reporting geodesic error and runtime in Table 1. min-GSGW achieves the lowest geodesic error on all six pairs while remain fast; see also Figure 6 in Appendix C. Table 1: Geodesic error (Geo.) and forward runtime in seconds (Time) on realistic mesh pairs (all ↓). H, E, C denote Horse, Elephant, Cat. LR-GW: [19]; SDP-GW: [4]; SaGroW: [10]. H–H
5.2
E–E
C–C
H–E
C–H
C–E
Method
Geo.
Time
Geo.
Time
Geo.
Time
Geo.
Time
Geo.
Time
Geo.
Time
POT Sink. LR-GW SDP-GW SaGroW
0.112 0.178 0.143 0.128 0.167
1.82 0.41 0.87 15.7 0.31
0.103 0.194 0.157 0.134 0.182
1.91 0.43 0.94 17.4 0.34
0.079 0.138 0.103 0.091 0.124
1.76 0.39 0.81 13.6 0.28
0.181 0.247 0.213 0.196 0.231
1.88 0.42 0.89 16.3 0.32
0.208 0.281 0.241 0.224 0.264
1.80 0.40 0.84 14.7 0.30
0.189 0.236 0.207 0.193 0.221
1.86 0.41 0.91 16.6 0.33
Ours
0.079
0.08
0.091
0.08
0.058
0.07
0.138
0.08
0.162
0.07
0.124
0.08
Horse mesh interpolation.
We test whether learned couplings support downstream geometry transfer via barycentric interpolation between consecutive horse meshes, comparing POT GW, MSGW, and our method. Figure 3 shows that, although POT achieves lower GW objective values, our plans still yield plausible dense correspondences and smooth intermediate deformations. This highlights a key distinction: global GW optimality does not imply geometric usefulness, and the slicer-induced plan family is expressive enough to preserve large-scale structure for interpolation. 5.3
Amortized Unsupervised Matching for ShapeNet Part Segmentation
We study amortized unsupervised matching on ShapeNet part segmentation [2]. Given two point clouds X = {xi }ni=1 and Y = {yj }m j=1 , we train a neural matcher that predicts, in a single forward pass, the push-forward values of min-GSGW and the induced soft coupling πτθ (X, Y ) ∈ Π(µ, ν). Training uses no part labels; part annotations enter only at test time to report label-transfer accuracy. 7
min-GSGW
Frame 0
! = 0.33
! = 0.67
Frame 1
! = 0.33
! = 0.67
Frame 2
Figure 3: Horse mesh interpolation from GW couplings. OT barycentric interpolation between consecutive horse meshes at t = 0.33 and t = 0.67. POT achieves lower GW values (8.257 × 10−3 for 0 → 1, 9.714 × 10−3 for 1 → 2), yet our method still produces smooth, geometrically coherent deformations (2.884 × 10−2 for 0 → 1, 4.622 × 10−2 for 1 → 2). Structural constraints. For the amortized plan Gθ (X, Y ) to be a well-formed slicer-induced coupling, it must satisfy three properties that mirror the non-amortized formulation (w.l.o.g we assume dX = dy here): Gθ (X, X) = n1 In ,
Gθ (Y, X) = Gθ (X, Y )⊤ ,
Gθ (T X, T Y ) = Gθ (X, Y )
∀ T ∈ E(d),
(15)
⊤
together with permutation equivariance Gθ (P X, QY ) = P Gθ (X, Y ) Q for all permutation matrices P, Q. The identity constraint enforces that a shape matched against itself recovers the diagonal plan. Symmetry ensures the matching is consistent under argument swap. Rigid-motion invariance means the coupling depends only on the intrinsic geometry of the two shapes, not their ambient orientation. The architecture is designed so that each constraint is satisfied by construction rather than by regularization, as we describe next. Intrinsic tokenisation. To preserve rigid-motion invariance at the input level, each point is encoded by its sorted squared-distance profile within the same point cloud. Concretely, for xi ∈ X define DiX = sort {∥xi − xk ∥2 : X k ̸= i} ∈ Rn−1 , and set ϕX i = ρ(Di ) where ρ is a shared MLP encoder; analogously for Y . Sorting provides a canonical ordering that makes each token invariant to permutations of the remaining points, so the token collections X Y Y Y ΦX = (ϕX 1 , . . . , ϕn ) and Φ = (ϕ1 , . . . , ϕm ) are rigid-motion invariant and permutation equivariant by construction. Push-forward prediction and plan construction. Following the coupled-scalarization structure of min-GSGW, the amortized model maps (ΦX , ΦY ) to push-forward values sθ (X, Y ) ∈ Rn and tθ (X, Y ) ∈ Rm via a shared-weight transformer encoder and a cross-attending push-forward head (architecture details in Appendix D). The push-forward values induce the soft plan πτθ during training and the hard plan π θ at inference, exactly as in Section 4. Training objective. Although the coupling is constructed through the min-GSGW slicer construction, we evaluate it under the fused GW objective: X X 2 Y 2 LFGW (π) = (1 − λ) CX (i, i′ ) − CY (j, j ′ ) πij πi′ j ′ + λ ∥ϕX i − ϕj ∥2 πij , i,i′ ,j,j ′
i,j
The model is trained end-to-end by minimizing the expected loss: h i min E(µ,ν) LFGW πτθ (µ, ν) . θ
6
Conclusion
We introduced min-GSGW, a scalable GW formulation that induces explicit transport plans by sorting slicer pushforward values, bypassing iterative coupling updates at inference. By coupling the two slicers through a shared map and 8
min-GSGW
(b) Chair
(c) Guitar
(e) Mug
(d) Pistol
POT GW
Source
(a) Earphone
Acc=82.81%
Acc=94.43%
Acc=55.66%
Acc=95.61%
Acc=87.50%
Acc=81.05%
Acc=89.06%
Acc=49.41%
Acc=80.66%
Acc=84.77%
Acc=79.69%
Acc=94.63%
Acc=88.77%
Acc=97.17%
↑+0.39%
↓-3.12%
↑+0.20%
↑+33.11%
↑+1.56%
Ours
Sinkhorn
Acc=84.38%
Figure 4: Qualitative correspondences on ShapeNet. Each column shows one object category, while rows show the source shape, POT GW, GW Sinkhorn, and our method. Source colors are propagated to the target via the estimated coupling. Bottom annotations report part-matching accuracy, and the last row also reports the accuracy difference between our method and POT GW. Table 2: Mean part label transfer accuracy and forward time per pair at varying point resolutions N . N = 256 Method
N = 512
N = 1024
Acc. (%) ↑ Fwd. (ms) ↓ Acc. (%) ↑ Fwd. (ms) ↓ Acc. (%) ↑ Fwd. (ms) ↓
POT GW Sinkhorn (ε = 0.05) Sinkhorn (ε = 0.5) Sinkhorn (ε = 1)
68.9 66.1 64.3 62.8
75.3 164.7 91.7 72.3
69.8 66.6 65.5 64.7
375.7 361.1 370.2 303.3
73.5 71.3 68.7 67.4
886.2 843.1 821.9 790.2
Ours
78.2
2.66
77.5
4.3
74.9
9.4
lifting, the method avoids independently chosen projections and minimizes the original GW loss over a richer family of monotone couplings than linear slicing affords, yielding a valid upper bound on GW with rigid-motion invariance under natural stability assumptions. The framework supports both per-instance optimization and amortized feed-forward matching. Across mesh correspondence, shape interpolation, and ShapeNet part segmentation, min-GSGW produces geometrically meaningful couplings with competitive GW objectives while scaling substantially more favorably than classical plan-producing solvers. These results suggest that expressive slicer-induced monotone couplings offer a practical path toward structure-aware matching at resolutions where dense GW optimization becomes prohibitive. Broader Impact. This work advances scalable approximations to Gromov–Wasserstein distance, with potential applications in shape analysis, molecular alignment, and multi-modal data integration. As with any method that reduces the cost of large-scale geometric matching, broader adoption may introduce risks in high-stakes domains, where approximation error could have downstream consequences.
9
min-GSGW
Acknowledgment SK acknowledges support from the NSF CAREER Award No. 2339898 and AS acknowledges support from Lambda Labs through a Lambda Cloud Research Credit award.
References [1] Robert Beinert, Cosmas Heiss, and Gabriele Steidl. On assignment problems related to gromov–wasserstein distances on the real line. SIAM Journal on Imaging Sciences, 16(2):1028–1032, 2023. [2] Angel X. Chang, Thomas Funkhouser, Leonidas Guibas, Pat Hanrahan, Qixing Huang, Zimo Li, Silvio Savarese, Manolis Savva, Shuran Song, Hao Su, Jianxiong Xiao, Li Yi, and Fisher Yu. ShapeNet: An Information-Rich 3D Model Repository. Technical Report arXiv:1512.03012 [cs.GR], Stanford University — Princeton University — Toyota Technological Institute at Chicago, 2015. [3] Laetitia Chapel, Romain Tavenard, and Samuel Vaiter. Differentiable generalized sliced wasserstein plans. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2026. [4] Junyu Chen, Binh Nguyen, Shang Hui Koh, and Yong Sheng Soh. Semidefinite relaxations of the gromovwasserstein distance. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. [5] Samir Chowdhury, David Miller, and Tom Needham. Quantized gromov-wasserstein, 2021. [6] Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. [7] Théo Dumont, Théo Lacombe, and François-Xavier Vialard. On the existence of monge maps for the gromov–wasserstein problem. Foundations of Computational Mathematics, 25(2):463–510, February 2024. [8] Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, Ievgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J. Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78):1–8, 2021. [9] Martin Jaggi. Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 427–435, Atlanta, Georgia, USA, 17–19 Jun 2013. PMLR. [10] Tanguy Kerdoncuff, Rémi Emonet, and Marc Sebban. Sampled gromov wasserstein. Machine Learning, 110(8):2151–2186, 2021. [11] Xinran Liu, Elaheh Akbari, Rocio Diaz Martin, Navid NaderiAlizadeh, and Soheil Kolouri. Efficient transferable optimal transport via min-sliced transport plans, 2025. [12] Xinran Liu, Rocio Diaz Martin, Yikun Bai, Ashkan Shahbazi, Matthew Thorpe, Akram Aldroubi, and Soheil Kolouri. Expected sliced transport plans. In Y. Yue, A. Garg, N. Peng, F. Sha, and R. Yu, editors, International Conference on Learning Representations, volume 2025, pages 60948–60971, 2025. [13] Guillaume Mahey, Laetitia Chapel, Gilles Gasso, Clément Bonet, and Nicolas Courty. Fast optimal transport through sliced generalized wasserstein geodesics. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 35350–35385. Curran Associates, Inc., 2023. [14] Facundo Mémoli and Tom Needham. Gromov-monge quasi-metrics and distance distributions. arXiv, 2018, 2018. [15] Facundo Mémoli. Gromov-wasserstein distances and the metric approach to object matching. Foundations of Computational Mathematics, 11(4):417–487, 2011. [16] Wen-Xin Pan, Isabel Haasler, and Hei Victor Cheng. Max-min sliced gromov-wasserstein, 2026. [17] Gabriel Peyré, Marco Cuturi, and Justin Solomon. Gromov-wasserstein averaging of kernel and distance matrices. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 2664–2672, New York, New York, USA, 20–22 Jun 2016. PMLR. [18] Mark Rowland, Jiri Hron, Alexander G. de G. Matthews, and Zoubin Ghahramani. Orthogonal estimation of wasserstein distances. In International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 186–195, 2019. 10
min-GSGW
[19] Meyer Scetbon, Gabriel Peyré, and Marco Cuturi. Linear-time gromov Wasserstein distances using low rank couplings and costs. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 19347–19365. PMLR, 17–23 Jul 2022. [20] Justin Solomon, Gabriel Peyré, Vladimir G. Kim, and Suvrit Sra. Entropic metric alignment for correspondence problems. ACM Trans. Graph., 35(4), July 2016. [21] Łukasz Struski, Michał B. Bednarczyk, Igor T. Podolak, and Jacek Tabor. Lapsum - one method to differentiate them all: Ranking, sorting and top-k selection. In The International Conference on Machine Learning (ICML) 2025, 2025. [22] Robert W. Sumner and Jovan Popović. Deformation transfer for triangle meshes. ACM Trans. Graph., 23(3):399–405, August 2004. [23] Vayer Titouan, Nicolas Courty, Romain Tavenard, Chapel Laetitia, and Rémi Flamary. Optimal transport for structured data with application on graphs. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 6275–6284, Long Beach, California, USA, 09–15 Jun 2019. PMLR. [24] Vayer Titouan, Rémi Flamary, Nicolas Courty, Romain Tavenard, and Laetitia Chapel. Sliced gromov-wasserstein. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. [25] Hongteng Xu, Dixin Luo, and Lawrence Carin. Scalable gromov-wasserstein learning for graph partitioning and matching. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. [26] Zhengxin Zhang, Ziv Goldfeld, Youssef Mroueh, and Bharath Sriperumbudur. Duality and sample complexity for the gromov-wasserstein distance. In NeurIPS 2023 Workshop Optimal Transport and Machine Learning, 2023.
11
min-GSGW
A
Ablation Study
We ablate two orthogonal design choices of min-GSGW: whether the slicer family is linear or nonlinear, and whether slicers are independent or dependent (jointly optimized). This yields a 2 × 2 factorial ablation evaluated on the realistic shape matching benchmark, reported in Table 3. Nonlinearity and coupling each provide an independent gain in geodesic error: linear slicers fail to capture curved geodesic geometry, while independent slicers collapse onto redundant directions and lose diverse coverage of the metric-measure space. The full model (nonlinear + coupled) benefits from both. Table 3: Ablation of slicer design on the realistic shape matching benchmark. Geo.: geodesic error (↓); Time: forward runtime in seconds (↓). H, E, C denote Horse, Elephant, Cat. H–H
E–E
C–C
H–E
C–H
C–E
Slicer
Relation
Geo.
Time
Geo.
Time
Geo.
Time
Geo.
Time
Geo.
Time
Geo.
Time
Linear
Independent Dependent
0.162 0.134
0.06 0.06
0.178 0.147
0.06 0.06
0.121 0.098
0.05 0.05
0.238 0.203
0.06 0.06
0.267 0.231
0.05 0.05
0.209 0.178
0.06 0.06
Nonlinear
Independent Dependent
0.108 0.079
0.08 0.08
0.119 0.091
0.08 0.08
0.081 0.058
0.07 0.07
0.172 0.138
0.08 0.08
0.198 0.162
0.07 0.07
0.153 0.124
0.08 0.08
B
Toy correspondences.
Ours
POT GW
Figure 5 compares exact GW against our method on four synthetic 2D-to-3D pairs. The experiment is qualitative: it shows that the nonlinear score construction is expressive enough to recover clean, globally coherent matches despite searching over a restricted coupling family. Unlike random one-dimensional projections, the shared map-lifting construction induces compatible orderings, yielding more structured correspondences across all four examples.
Figure 5: Qualitative comparison on four toy datasets. Top: GW correspondences. Bottom: ours. Source points lie on z = 0; targets in R3 . Our method produces cleaner, more structurally aligned matches.
C
Experimental details and reproducibility
We report the implementation choices needed to reproduce the experiments. All methods use uniform marginals, and all optimization is implemented in PyTorch with CUDA used when available. Unless otherwise stated, each number reported in the main tables is averaged over three random seeds, {42, 7, 77}. Animal mesh matching. For the animal mesh correspondence experiments, we compute pairwise geodesic distance matrices from the mesh graph using Euclidean edge lengths, symmetrize the resulting distances, and compare our learned sorting based plan against other baselines. The effective hyperparameters are listed in Table 4. 12
min-GSGW
(a) POT GW GW = 0.0388
(b) Ours GW = 0.0253
1.0 1.0
0.5
0.5
0.0 Z
0.0 Z
0.5
0.5
1.0 1.5 0.0
0.5
1.0
X
1.5
2.0
2.5
1.5 1.0 0.5 0.0 Y 0.5 1.0
1.0 0.0
0.5
1.5 1.0
X 1.5
2.0
2.5
1.0
0.5
0.5 0.0 Y
1.0
1.5
Figure 6: Shape correspondence on animal meshes. Landmark correspondences (18 total, 6 shown) computed from geodesic distance matrices. Blue denotes source landmarks, red denotes predicted target landmarks, and black indicates correspondences. (a) POT GW. (b) Ours. Table 4: Reproducibility details for animal mesh matching. Component
Setting
Value
Data Landmarks Landmarks Model Model Model Optimization Optimization Optimization Optimization Sorting Baseline Baseline Baseline
Mesh formats n_land n_rep Hidden width Depth Random Fourier features Optimizer Learning rate Steps Gradient clipping Initial temperature POT solver POT loss MSGW directions
.obj, .off 18 4 1024 6 128 Adam 10−4 1500 1.0 10−4 gromov_wasserstein square_loss 500
Horse mesh interpolation. For horse interpolation, meshes are centered and scaled by their maximum norm. Geodesic costs are computed on a symmetrized kNN graph with Euclidean edge weights and Dijkstra shortest paths. We train multiple random restarts and use the best hard plan for barycentric interpolation. The effective settings are given in Table 5. Amortized ShapeNet matching. For the amortized setting, we train a shared model that predicts scalar scores for each input pair and induces a transport plan through differentiable sorting. The input point features include coordinates, normals, and an intrinsic descriptor obtained from sorted squared intra shape distances. The experiment uses the following ShapeNet categories: airplane, bag, cap, car, chair, earphone, guitar, knife, lamp, laptop, motorbike, mug, pistol, rocket, skateboard, and table. The training and architecture details needed for reproduction are summarized in Table 6. Toy correspondences. The toy correspondence experiment is qualitative and is included to visualize the induced correspondence structure. It uses four planar source examples mapped to target point clouds in R3 , with exact GW used as a reference baseline. Since this experiment is illustrative, we do not include additional implementation specific details beyond those needed to interpret the figure. 13
min-GSGW
Table 5: Reproducibility details for horse mesh interpolation. Component
Setting
Value
Data Data Geodesics Geodesics Geodesics Geodesics Model Model Model Model Optimization Optimization Optimization Optimization Optimization Optimization Optimization Annealing Annealing
Mesh indices Mesh formats Graph Neighbors Solver Normalization Hidden width Depth Expansion Dropout Optimizer Steps Restarts Learning rate Weight decay Warmup steps Gradient clipping αstart αend
{0, 1, 2} .npy, .off symmetrized kNN 20 Dijkstra shortest path [0, 1] 512 4 2 0.0 AdamW 1000 3 3 × 10−3 10−4 50 5.0 1.0 0.03
Table 6: Reproducibility details for amortized ShapeNet matching. Component
Setting
Value
Data Data Data Data Features Features Features Model Model Model Model Optimization Optimization Optimization Optimization Annealing
Splits Points per shape Batch size / workers Pairs per epoch / validation pairs Input features Intrinsic descriptor dimension Coordinate normalization Token / latent dimension Attention heads Layer pattern Score head Optimizer Epochs Learning rate / weight decay Warmup epochs / gradient clipping αstart / αend
train / val 1024 4/4 2000 / 400 Intrinsic descriptor ϕ 64 centering and max norm scaling 70 / 256 4 self, self plus cross, self plus cross symmetric cross-attending head AdamW 500 10−3 / 10−5 5 / 1.0 0.05 / 0.005
D
Amortized min-GSGW Architecture
We describe the full architecture of the amortized matcher introduced in Section 5.3. The network maps intrinsic token collections ΦX ∈ RN ×din and ΦY ∈ RM ×din to score vectors sθ ∈ RN and tθ ∈ RM , which induce the soft coupling via LapSum [21]. It consists of five components: a shared token embedding, a two-stream transformer encoder, a symmetric pair-context branch, a cross-attending score head, and the LapSum differentiable assignment layer. Notation. Let SA(H) = MHA(H, H, H) denote self-attention and CA(H, H ′ ) = MHA(H, H ′ , H ′ ) cross-attention, where MHA uses softmax multi-head attention. We define four transformer block types, each with a GELU MLP and post-LayerNorm residuals: • S: self-attention only, applied independently to each stream with tied weights. • C: cross-attention only; each stream attends to the other. • SC: self-attention followed by cross attention. 14
min-GSGW
• CS: cross-attention followed by self-attention. All blocks within the encoder share weights across the two streams. Token embedding.
A shared linear map E : Rdin → Rd embeds each token independently: (0)
(0)
HX = E(ΦX ) ∈ RN ×d ,
HY = E(ΦY ) ∈ RM ×d .
Two-stream encoder. The encoder follows the block pattern [S, SC, SC], producing contextualised representations (HX , HY ). In all ShapeNet experiments we use hidden dimension d = 256 and h = 4 attention heads. Symmetric pair-context branch. To inject a global summary of the pair that is symmetric under swapping X ↔ Y , a shared set encoder C (two-layer pointwise MLP, weighted mean pooling, linear projection to Rdc ) produces c = 12 C(ΦX ) + C(ΦY ) ∈ Rdc . This vector is broadcast and concatenated with the encoder outputs, then projected back to width d via a shared map Wc : Rd+dc → Rd : e X = Wc HX ∥ 1N c⊤ , e Y = Wc HY ∥ 1M c⊤ . H H Symmetry of c ensures that swapping the two inputs produces identically conditioned streams, consistent with the symmetry constraint Gθ (Y, X) = Gθ (X, Y )⊤ in (6). Cross-attending score head. A depth-two SC stack with separate parameters from the encoder further mixes the context-conditioned streams: eX , H e Y ). (H̄X , H̄Y ) = SC2 ◦ SC1 (H A shared scalar readout w : Rd → R then produces the score vectors: sθ = w(H̄X ) ∈ RN ,
tθ = w(H̄Y ) ∈ RM .
Using a shared readout enforces the design principle of min-GSGW: the two score systems are coupled through a common scalarization rather than chosen independently. LapSum differentiable assignment. The scores (sθ , tθ ) are passed to LapSum [21], which maps them to soft permutation matrices PX,τ ∈ RN ×N and PY,τ ∈ RM ×M at temperature τ . These induce the soft matching plan ⊤ πτθ = PX,τ Π0 PY,τ ,
where Π0 is the canonical sorted plan, as defined in Section 4. At inference time we set τ → 0, recovering the hard plan πθ . Intrinsic tokenisation details. The set encoder ρ maps an unordered distance profile DiX = {∥xi − xk ∥2 : k ̸= i} to a fixed-size vector. Concretely, ρ sorts the K nearest squared distances and passes the resulting K-dimensional vector din through a two-layer MLP with GELU activations, yielding ϕX . We use K = 32 in all experiments. Because i ∈R sorting is applied to distances within a single point cloud and the MLP weights are shared, the tokens are rigid-motion invariant and permutation equivariant as argued in Section 5.3.
15