PaperlayerView exact revision on arXiv

Source-linked AI summary

Discrete Gromov-Wasserstein Duality: Algorithms and Isomorphism Testing

Gabriel Rioux, Joanna Marks, Riccardo Passeggeri, Ziv Goldfeld

arXiv:2609.03094v1math.STcs.ITmath.ITmath.OCstat.MLstat.TH

TL;DR

GW compares metric-measure spaces through intrinsic structure, and an earlier dual form addressed Euclidean distributions. This work derives a dual representation for finite mm spaces, develops statistical and regularized optimization methods, and applies its testing framework to graph-distribution isomorphism, obtaining consistent tests.

  • Problem

    A dual form had been derived for GW between Euclidean distributions, while GW is used to compare heterogeneous datasets and identify isomorphic representations.

    Source: §1 · p. 1

  • Method

    The paper develops a dual representation for finitely supported mm spaces and uses it to establish statistical theory and algorithms for regularized GW.

    Source: §1 · p. 2

  • Results

    The framework yields consistent tests of whether two sampled graph sets come from the same distribution modulo a permutation of node labels.

    Source: §8 · p. 48

  • Takeaways & Limitations

    GW is a metric on compact mm spaces modulo isomorphism, making it a tool for comparing heterogeneous datasets and identifying isomorphic representations.

    Source: §1 · p. 1

    The duality result is established for finite metric-measure spaces; extending it to continuous spaces remains open, with a kernel-decomposition hurdle.

    Source: §8 · p. 48

Abstract

from arXiv · show

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.

1. Introduction

GW compares metric measure spaces through their intrinsic relational structure and can identify isomorphic representations. This paper extends duality beyond previously treated Euclidean settings and uses it to develop statistical and computational results for finite spaces.

1. Introduction

  • GW provides an optimal-transport framework for aligning distributions on distinct spaces and is a metric on compact metric measure spaces modulo isomorphism.It is an Lp relaxation of the Gromov–Hausdorff distance.Source: §1 · p. 1

1.1. Literature review.

  • A central open problem is duality for GW: its nonconvex quadratic formulation prevents standard convex-duality arguments.Earlier duality results covered Euclidean distributions with squared Euclidean or inner-product costs, and a formulation for finite-dimensional concave quadratic programs appeared in [28].Source: §1 · p. 2

1. Introduction

  • The paper develops a dual representation for all finitely discrete metric measure spaces, supporting statistical theory, regularized algorithms, and sample-based graph-distribution isomorphism testing.The stated applications include empirical convergence rates, limit laws, and tests for distributions on fixed-size graphs.Source: §1 · p. 2

1.1. Literature review.

  • Prior Euclidean GW duality enabled sample-complexity analyses, limit laws, and computational methods, while empirical GW inherits the curse of dimensionality known for empirical OT.With entropic regularization, a parametric rate was known under certain tail conditions.Source: §1.1 · pp. 2–3

2. Notation and Background

This section establishes notation and reviews OT, its entropic version, and GW. It represents finite GW problems as regularized quadratic programs over coupling constraints.

2. Notation and Background

  • The section fixes notation for finite sets, measures, pushforwards, distributions, and matrix norms used throughout.The Frobenius inner product is the entrywise matrix inner product, and the operator norm is also defined.Source: §2 · p. 3

2.1. Optimal Transport.

  • OT minimizes the cost integrated over couplings, and linear-programming duality gives a dual problem with OT plans and potentials as optimizers.OT potentials are not unique: adding a constant to one and subtracting it from the other gives an equivalent version.Source: §2.1 · p. 3

2.2. Entropic Optimal Transport.

  • Entropic OT regularizes OT using Kullback–Leibler divergence and has a dual formulation with potentials and a unique optimal plan.The section states that bounded versions of entropic OT potentials exist, with bounds depending on the cost.Source: §2.2 · p. 4

2.3. Gromov–Wasserstein Problems.

  • GW compares relational structure across incompatible spaces; its entropic version yields a finite regularized quadratic program in coupling variables.The feasible set is written as linear equality constraints and nonnegativity constraints, with entropy expressed using Shannon entropies.Source: §2.3 · pp. 4–5

3. The Variational Form

For finite GW problems, the paper replaces constrained quadratic minimization with an unconstrained min-max formulation involving an optimal linear-program value. The formulation applies with or without entropic regularization and connects GW to parameterized OT.

3. The Variational Form

  • For any ε ≥ 0, the variational formulation replaces constrained quadratic minimization with an unconstrained min-max problem whose objective includes an optimal linear-program value.The feasible coupling set is denoted K.Source: §3 · p. 5
  • Theorem 1 decomposes any symmetric cost matrix as a difference of two positive-semidefinite quadratic forms and gives an equivalent inf-sup problem with the same optimal value.Solutions map between formulations through the matrices B0 and B1; the theorem also gives a converse correspondence.Source: §3 · pp. 5–6
  • The formulation applies to arbitrary finitely discrete marginals without assumptions on the similarity measures or p > 0, at the cost of an additional maximization.Earlier formulations covered more restricted settings, including Euclidean distributions with squared Euclidean costs.Source: §3 · p. 6
  • The variational result connects entropic GW to a parameterized family of entropic OT problems, extending a connection used in earlier Euclidean GW statistical and computational work [38].The paper develops analogous theory for distributions supported on arbitrary finite metric spaces.Source: §3 · p. 6

4. Statistical Analysis

The section develops statistical results for empirical GW distances on finite spaces, including convergence rates, limit laws, and a sample-based framework for testing isomorphism. It also provides a conservative way to estimate null quantiles for that testing framework.

4.1. Sample Complexity.

  • Empirical EGW and GW distances have parametric convergence rates, with the EGW plug-in estimator converging in expectation at O(n^-1/2).Source: §4 · p. 7, §4.1 · p. 7

4.2. Directional Differentiability and Limit Distributions.

  • Empirical GW and EGW distances have limit theorems under the same √n scaling.Source: §4.2 · pp. 7–8

4.3. Hypothesis Testing.

  • Because the naive bootstrap may fail and the m-out-of-n bootstrap is computationally burdensome, the testing approach uses a simplified limit law under the null.Source: §4.3 · p. 9

4.3.1. Limit Laws Under the Null.

  • For dissimilarities with distinct profiles, GW_p(µ0, µ1) = 0 exactly when a bijection preserves κ and pushes µ0 to µ1.Source: §4.3.1 · p. 9
  • Under the null, the √n-scaled empirical GW distance has a simplified limit law indexed by structure-preserving maps and H_µ0.Source: §4.3.1 · p. 9, §4.3 · p. 9

4.3.2. Conservative Quantile Estimates.

  • The proposed null quantiles conservatively dominate the limiting-law quantiles, with equality when the measure-preserving structure-preserving map is unique.Source: §4.3.2 · p. 10

4.3.3. Computation and Consistency of Conservative Quantiles.

  • Conditional quantiles of the estimated null law consistently estimate those of L.Source: §4.3.3 · p. 11
  • The test has asymptotic level α and power 1 when GW_p(µ0, µ1) > 0.Its critical values use estimated null quantiles.Source: §4.3.3 · p. 11

5. Stability and Algorithms

This section studies stability of the entropic GW objective and develops and evaluates gradient-based algorithms, establishing convergence guarantees that account for inexact computations and analyzing computational and memory costs.

5.1. Objective Stability.

  • The objective ℓ is L-smooth, and its minimizers and the inner maximizers lie in explicit compact balls, enabling projected accelerated minimization.The gradient can be computed through an entropic optimal-transport problem, which the paper notes can be solved efficiently with Sinkhorn’s algorithm.Source: §5.1 · pp. 12–13, §5.2 · p. 13

5.2. Inexact Gradient Method.

  • Accelerated minimization of ℓ tolerates uniformly bounded gradient error and achieves O(J^-3) convergence when ℓ is convex or O(J^-1) when it is nonconvex, with an additional error term.The method is rate-adaptive to convexity; its rates comprise a term tracking algorithmic progress and a fixed term accounting for inexact gradient evaluations.Source: §5.2 · p. 14

5.3. An Inexact Gradient Oracle.

  • The proposed inexact gradient oracle meets any desired accuracy by combining approximate maximization of fu with sufficiently precise entropic optimal-transport solves.Theorem 6 bounds its uniform gradient error under conditions on the approximate maximizer and transport solution; Sinkhorn can supply transport approximations to the required precision.Source: §5.3 · pp. 15–16

5.4. An Unaccelerated Gradient Method.

  • The unaccelerated method lacks the accelerated algorithm’s adaptive rate, but its convergence analysis supports approximate stationary points when gradient error and iterate progress are small.The paper describes its nonconvex convergence rate as the best known for first-order methods on such problems.Source: §5.4 · pp. 16–17

5.5. Gradient Methods as Inexact Oracles.

  • For maximizing fu, the accelerated inexact gradient method has an optimization-error term that decreases at O(1/j^2), alongside a term accounting for gradient error.The section establishes distance-to-optimality bounds for the accelerated and unaccelerated methods used as inexact oracles.Source: §5.5 · pp. 17–18
  • Under a bounded approximate-gradient error, Proposition 12 gives Algorithm 6 a convergence guarantee for iterates targeting the unique maximizer of fu.The assumption bounds the gradient error by η for v with ∥v∥≤R1; the proposition applies to the minimum iterate, and the same rate is stated for an averaged iterate.Source: §5.5 · p. 18

5.6. Computational Complexity.

  • Factoring the Kronecker structure avoids explicitly forming B0 and B1, reducing storage from (r0+r1)N0N1 to (rK+0+rK−0)N0+(rK+1+rK−1)N1.For p=2, separately diagonalizing the two cost matrices gives decomposition cost O(max{N0^3,N1^3}) instead of diagonalizing the full matrix.Source: §5.6 · pp. 19–20
  • Given B0 and B1, J iterations of Algorithm 2 require O(JK(S+max{r0,r1})N0N1) operations when EOT problems use S Sinkhorn iterations.Each iteration solves an EOT problem in O(SN0N1) operations up to log factors; the gradient-oracle cost depends on the implementation.Source: §5.6 · pp. 20–21

5.7. Numerical Validation.

  • The numerical iterates were consistent with theoretical convergence rates, and the accelerated gradient method showed the staircase pattern typical of momentum-based methods.Source: Figure 2 · p. 22, §5.7 · p. 22
  • 2.4022×10^-8 and 6.0448×10^-11 were the maximum Frobenius-norm discrepancies between the algorithms’ final couplings and mirror descent’s in nonconvex and convex settings, respectively.Source: §5.7 · p. 23
  • Both proposed methods retained O(N^2) runtime scaling and had runtimes similar to mirror descent, slightly faster as N grew; in nonconvex cases, the accelerated method was slower.The reported scaling holds in both convex and nonconvex settings.Source: §5.7 · p. 23, Figure 3 · p. 24

6. Testing for Isomorphism of Graph Distributions

The section turns samples of graph distributions into a Gromov–Wasserstein test of equality up to vertex relabeling. Under stated support and node-count conditions, smoothing yields a consistent test, and simulations contrast its joint-edge sensitivity with an edge-marginal approach.

6. Testing for Isomorphism of Graph Distributions

  • Unlike the method in [38], the proposed approach applies to arbitrary graph distributions and compares joint edge distributions rather than only edge marginals.The earlier method is limited to distributions with independent edges.Source: §6 · p. 24
  • Before smoothing, zero GW characterizes label isomorphism when N ≠ 4 and both laws give positive mass to every single-edge graph.The kernel compatibility result links the GW criterion to permutation of vertex labels.Source: §6 · p. 25
  • Mixing each graph law with λU makes zero GW equivalent to label-permutation isomorphism for any two laws when N ≠ 4.U is the uniform measure on graphs with a single edge.Source: §6 · p. 25
  • Using smoothed empirical measures and conservative critical values scaled by (1−λ), the test has any given asymptotic level under isomorphism (GWp(˜µ0, ˜µ1)=0), while rejection probability converges to 1 otherwise (GWp(˜µ0, ˜µ1)>0).Source: §6 · p. 25
  • The N = 4 case can be handled by embedding four-node graphs into five-node graphs before applying the results.The paper proposes adding one node to the sampled graphs.Source: §6 · p. 26

6.1. Numerical Validation.

  • The proposed test’s type 2 error decays to 0 with sample size, while [38]’s remains essentially constant and can misidentify µ0 and µ2 as isomorphic.The simulation reports good finite-sample results despite Theorem 7 being asymptotic.Source: §6.1 · pp. 26–27

7. Proofs of Main Results

This section proves the paper’s main characterizations and analytic results, including optimizer and potential properties, GW derivatives, zero-distance structure-preserving bijections, convergence claims, bounds, and regularity results. It also transfers convergence guarantees under matched assumptions and establishes graph-isomorphism properties of the GW kernel, with the graph characterization requiring N ≠ 4.

7.1. Proof of Proposition 1.

  • Shifting the OT potentials yields bounds placing both normalized potentials between −3/2 and 1/2 times the sup norm of the cost.The proof chooses the shift so that the supremum of the first potential is 1/2 of the cost sup norm.Source: §7.1 · p. 28

7.2. Proof of Theorem 1.

  • The proof of Theorem 1 relates primal optimizers to the outer inf-sup problem: a primal optimizer induces an outer optimizer, and an outer optimizer yields a primal optimizer.The proof uses first-order optimality conditions and lemmas characterizing the relevant subdifferentials.Source: §7.2 · pp. 30–31

7.3. Proof of Proposition 3.

  • For the empirical and population marginals, the inf-sup solutions lie in the bounded sets B0B × B1B.The proof then invokes Corollary 1 to obtain the comparison stated in equation (24).Source: §7.4 · p. 32

7.5. Proof of Theorem 3.

  • The unregularized and entropically regularized GW objectives each have directional-derivative formulas for perturbations of both measures.The unregularized formula uses optimal GW plans and their OT potentials; the regularized formula uses optimal couplings and unique EOT potentials up to additive constants.Source: §7.5 · pp. 33–34

7.6. Proof of Proposition 4.

  • Under the stated conditions, every optimal coupling for GW is induced by a bijection preserving the space structure and mapping one measure to the other.Conversely, such a bijection induces a coupling with zero distortion, which is optimal because GW is nonnegative.Source: §7.6 · pp. 34–35, §7.7 · p. 35

7.7. Proof of Corollary 2.

  • The optimal-potential pairs for a coupling induced by S are characterized as (h, −h ◦ S−1), with h satisfying the stated feasibility condition.The proof uses complementary slackness and the structure-preserving property of S.Source: §7.7 · p. 35

7.8. Proof of Proposition 5.

  • Under the proof’s assumptions, L stochastically dominates L*, so P(L ≤ t) ≤ P(L* ≤ t) for every t.The passage also states that a distribution in the proposition coincides with that of L under the current assumptions.Source: §7.8 · p. 36
  • The set of structure-preserving bijections mapping µ0 to µ1 is a singleton exactly when the only measure-preserving structure-preserving self-map of the source is the identity.The proof establishes both directions by composing candidate bijections with a nonidentity self-map.Source: §7.8 · p. 36

7.9. Proof ofProposition 6.

  • The proof shows conditional convergence to the Gaussian-based limit and establishes continuity of its distribution function.It uses stability of the linear-program value under perturbations and verifies finiteness and Gaussian support conditions; the proof also records a geometric criterion for nonempty interior.Source: §7.9 · pp. 36–38

7.10. Proof of Theorem 4.

  • Under the alternative, the probability that the scaled empirical GW statistic falls below any fixed threshold tends to zero, and the proof extends this to the conditional critical value.The null-hypothesis claims follow from Propositions 5 and 6.Source: §7.10 · pp. 38–39

7.11. Proof of Proposition 7.

  • The proof establishes continuous differentiability of the optimizer and shows that the objective is convex under the stated condition on ε, with a globally Lipschitz gradient.The optimizer’s regularity follows from the implicit function theorem; the Hessian bounds yield convexity and a global gradient-Lipschitz bound.Source: §7.11 · pp. 40–42

7.12. Proof of Proposition 8.

  • The proof identifies the optimizer as the unique solution of a strictly convex problem and establishes 1-strong concavity of the objective.Source: §7.13 · p. 42

7.13. Proof of Proposition 9.

  • For Proposition 9, the proof applies the implicit function theorem to obtain a continuously differentiable optimizer map and bounds the Hessian to establish the gradient’s Lipschitz property.The argument adapts the regularity analysis used for Proposition 7 to the variable v.Source: §7.13 · p. 43
  • The proof of Proposition 9 applies the analysis of to minimizing a smooth objective over a closed ball using approximate gradients.The objective is decomposed into a smooth convex term and a smooth nonconvex term.Source: §7.14 · p. 43

7.14. Proof of Theorem 5.

  • Theorem 5 follows from Theorem 11 in by setting M = 2R0 and δ′ = 2R0η′.The proof identifies the current gradient oracle with the approximate-gradient setting of that theorem.Source: §7.14 · p. 44

7.15. Proof of Theorem 6.

  • Theorem 6’s proof uses uniform Hessian bounds to obtain strong convexity and combines minimizer stability with an approximation error bounded by τ.On the specified set, the objective has a strongly convex modulus; the argument then bounds the distance between approximate and target minimizers.Source: §7.15 · p. 44

7.16. Proof of Proposition 10.

  • Proposition 10’s convergence rate follows from after the proof shows that Algorithm 4’s projected updates coincide with those of Algorithm 1.The proof matches the approximate-gradient oracle and update rule to the conditions in.Source: §7.16 · p. 45

7.17. Proof of Proposition 11.

  • Proposition 11’s proof applies the guarantee in to the algorithm’s iterates and uses strong convexity to lower-bound the objective gap by half the squared distance to the optimizer.The approximate gradient satisfies the cited oracle condition.Source: §7.17 · pp. 45–46

7.18. Proof of Proposition 12.

  • For Proposition 12, the approximate gradient yields a (4R1η, (1 + ε^-1∥B1∥^2)op)-oracle, and a permuted pair of measures has GWp distance zero under the chosen kernel.The oracle construction uses the assumed Sinkhorn gradient accuracy and exact function evaluations.Source: §7.18 · p. 46, §7.19 · p. 46

7.19. Proof of Proposition 13.

  • For N ≠ 4, zero GWp distance under κ characterizes vertex-permutation equivalence of the graph distributions; the exceptional case arises because non-isomorphic triangle and claw graphs occur at N = 4.The proof first derives a kernel-preserving bijection between supports, then shows it is induced by a vertex permutation.Source: §7.19 · pp. 47–48, Figure 6 · p. 48

8. Concluding Remarks

The conclusion reports graph-distribution isomorphism tests and identifies extending the representation beyond finite metric measure spaces as a key open direction. Appendix A expresses coupling constraints as linear constraints and relates the entropic KL term to Shannon entropies.

8. Concluding Remarks

  • The variational forms connect finite-space GW, with or without entropic regularization, to parameterized OT problems and support statistical theory and first-order algorithms with nonasymptotic guarantees.The guarantees also cover inexact gradient evaluations, which arise because the required auxiliary optimization problems generally lack closed-form solutions.Source: §8 · p. 48
  • The hypothesis-testing framework yields consistent tests for whether sampled graphs come from the same distribution modulo label permutation.The adapted algorithms produced reasonable test-statistic results, although their convergence guarantees do not apply without regularization.Source: §8 · p. 48
  • Extending the representation beyond finite metric measure spaces remains open; the proof relies on decomposing symmetric matrices into differences of psd matrices.A corresponding difference-of-psd-kernels characterization for the continuous case is not straightforward to obtain in general.Source: §8 · p. 48

Appendix A. From Discrete GW to Quadratic Programming

  • The coupling set is represented by linear equality and nonnegativity constraints, Ax = b and x ≥ 0, so feasible vectors encode couplings.The passages also express KL(π∥µ0 ⊗ µ1) as −Hπ + Hµ0 + Hµ1.Source: Appendix A · p. 52

Appendix B. The Delta Method

The appendix applies a delta-method framework to derive limit laws for empirical GW costs. It states a continuity and positive-homogeneity property for the associated map under the proposition's assumptions.

Appendix B. The Delta Method

  • The appendix applies the delta-method approach of Proposition 1 and Remark 4 in to derive limit laws for empirical GW costs.The framework is adapted to pairs of probability vectors representing distributions on finite spaces.Source: Appendix B · pp. 52–53
  • The framework assumes a distributional limit for a pair of random vectors and regularity conditions on the empirical GW functional.The provided proposition passage states these as assumptions but does not fully specify their formulas.Source: Appendix B · p. 53
  • Under the proposition's assumptions, H(µ0,µ1) extends to a continuous, positively homogeneous map.The proposition is identified as Proposition 1 in.Source: Appendix B · p. 53

Appendix C. Implementation details for Algorithm 1

The implementation appendix addresses memory and constraint handling in Algorithm 1. It describes sparse storage for R, adjustments for estimated support sizes, and a bounded reformulation of an otherwise unbounded constraint set.

Appendix C. Implementation details for Algorithm 1

  • Sparse storage reduces the memory overhead of R, and vacuous constraints can be removed when their corresponding entries are zero.The passage notes that storing the full N0^2 × N0 matrix can require substantial memory when N0 is large.Source: Appendix C · p. 53
  • When support size is estimated from data, the estimated matrices and vectors can be padded to population dimensions with zeros for missing support points.The padded Gaussian sample has zero entries at those additional points, which do not contribute to the objective value.Source: Appendix C · pp. 53–54
  • Adding w1 ∈ [−δ, δ] bounds the constraint set without changing the optimal value, because the Gaussian sample is orthogonal to the all-ones vector under the stated assumption.The added constraint also accommodates numerical imprecision when generating the sample.Source: Appendix C · p. 54

Appendix D. Additional Experimental Details for Section 5.7

The appendix gives convergence and runtime experiment settings for the algorithms. In the convergence experiment, the reported outcomes abide by the derived convergence rates.

Appendix D. Additional Experimental Details for Section 5.7

  • The convergence experiment initializes gradient methods from the independent coupling and uses L = 1.5 for Algorithms 2 and 4 and L = 2 for Algorithm 6.The passages note that these step sizes need not match theoretical step sizes.Source: Appendix D · p. 54
  • The convergence experiments' results abide by the derived convergence rates, with the approximate-gradient tolerance met before the iteration limits.The tolerance was δ = 10^-10; the stated maxima were 1000 iterations for minimizing ℓ and 100 for the inexact gradient oracle.Source: Appendix D · pp. 54–55
  • The runtime experiment uses a maximum of 5000 iterations, a problem-dependent ε, and line-searched step sizes for the gradient methods.The approximate-gradient tolerance is δ = 10^-6; the passage says it was met before the iteration limit.Source: Appendix D · p. 55

Appendix E. Implementing the Graph Isomorphism Test

Appendix E describes a kernel-based implementation of the graph isomorphism test and a warm start for its GW computations. The following proofs establish stability of variational-form solutions and auxiliary optimization results.

Appendix E. Implementing the Graph Isomorphism Test

  • The graph-kernel construction yields a positive semidefinite matrix, allowing the 2-GW cost to be chosen negative semidefinite and B1=0; Algorithm 4 then uses an OT solver.The implementation sets ε=0 and uses the POT package for the resulting OT problem.Source: Appendix E · p. 55
  • A population-level optimal coupling induced by the true permutation initializes Algorithm 4; when the permutation is unknown, trying every possibility scales poorly as N increases.The warm start is motivated by cluster points of empirical variational-form solutions being solutions for the population problem under weak convergence of the marginals.Source: Appendix E · pp. 55–56

Appendix F. Convergence of Solutions for the Variational Form

  • Under weak convergence of the marginals, every cluster point of variational-form solution pairs solves the limiting variational problem.The accompanying lemma states that cluster points of minimizers of ℓ_n minimize ℓ, with ℓ_n(u_n) converging to inf_u ℓ(u).Source: Appendix F · p. 57

G.1. Proof of Lemma 2.

  • The proof of Lemma 2 uses strong concavity to identify the unique maximizer in v and Danskin’s theorem to derive subdifferentials.It combines these with a subdifferential sum rule for the variational objective.Source: §G.1 · p. 58

G.2. Proof of Lemma 3.

  • The proof of Lemma 3 invokes the convex subdifferential sum rule and an optimality condition for minimization over K.The cited results establish ∂(f + g) = ∂f + ∂g for the proper, lower semicontinuous convex functions in the proof.Source: §G.2 · p. 58

G.3. Proof of Lemma 4.

These auxiliary proofs use optimal-transport potentials and linear-programming duality to establish bounds and convergence-related results. They also address the lack of full support in one setting and construct nearby minimizers in another.

G.3. Proof of Lemma 4.

  • The proof of Lemma 4 handles marginals without full support by using the existence of OT potentials, since Proposition 1 does not directly apply.The passage notes that general OT results still provide potentials satisfying the stated infimum relations.Source: §G.4 · p. 60

G.4. Proof of Lemma 5.

  • The proof of Lemma 5 bounds both potentials using the supremum norm of the cost, with bounds between −3/2 and 1/2 times that norm.The displayed bounds apply to each potential across the spaces.Source: §G.4 · p. 60

G.5. Proof of Lemma 6.

  • The proof of Lemma 6 converts a linear program’s feasible pairs into OT potentials, establishing equality of the primal and dual optimal values.The argument uses strong duality and then takes an infimum over optimal GW plans to obtain the claimed bound.Source: §G.5 · pp. 62–63

G.6. Proof of Lemma 7.

  • In the proof of Lemma 7, nearby minimizers can be selected at distance O(t_n) as t_n decreases to zero.The argument also tightens a lower bound by taking a supremum over OT potentials.Source: §G.6 · pp. 63–64

G.7. Proof of Lemma 8.

The proof of Lemma 8 relates a linear program to entropic optimal-transport potentials and uses local perturbations of measures. Its argument relies on finite supports with positive masses.

G.7. Proof of Lemma 8.

  • For finite supports with positive masses, the entropic parameter bound is nonzero, and entropy terms remain well-defined for sufficiently small perturbations.The proof uses a first-order expansion for perturbed measures whose signed perturbation has total mass zero.Source: §G.7 · pp. 64–65
  • The proof identifies feasible pairs in the linear program with entropic OT potentials, whose objective values coincide by strong duality.The passage states that the potentials are unique up to additive constants.Source: §G.7 · p. 66
  • The resulting bound is tightened by taking the infimum over optimal entropic GW couplings.The proof concludes that this establishes the claimed result.Source: §G.7 · p. 66

G.8. Proof of Lemma 9.

The proof of Lemma 9 tracks minimizers and potentials as the marginals vary. It uses subsequence limits to connect solutions of the perturbed problems with the limiting variational form.

G.8. Proof of Lemma 9.

  • A convergent subsequence of perturbed minimizers has a limit that minimizes the limiting problem over K.The proof also relates the corresponding outer-minimization variables to the limiting variational form.Source: §G.8 · p. 67
  • The limiting pair (u0, v0) solves the variational inf-sup problem, with v0 identified as B1x0 by uniqueness.The proof obtains convergence of v along the subsequence using strong concavity.Source: §G.8 · p. 68
  • Limit points of the entropic OT potentials solve the limiting Schrödinger system and differ only by additive constants.This follows from continuity of the cost and uniqueness of the limiting potentials up to constants.Source: §G.8 · p. 68
  • The proof takes a lower bound over all optimal couplings for the limiting entropic GW problem, making the bound independent of the original sequence and subsequence.The cited passage links the limiting cost to the vector associated with x0.Source: §G.8 · p. 69

G.9. Proof of Lemma 10.

These proof steps establish conditions on Γη’s interior and show how κ-based graph comparisons support the subsequent isomorphism argument. They also characterize single-edge graphs and the behavior of maps preserving κ.

G.9. Proof of Lemma 10.

  • Coordinate bounds wi ∈ [−β/2, β/2] ensure Γη has nonempty interior, whereas identical κ0 profiles for two points force wi = wj throughout Γη and empty interior.The repeated-profile condition is stated for every x′ in spt(η).Source: §G.9 · p. 69

G.10. Proof of Lemma 13.

  • κ is invariant under vertex permutation, so coupling µ0 with its permuted version gives zero GW cost.Source: §G.10 · p. 70

G.11. Proof of Lemma 14.

  • κ(G, G) ≥ m + 4, with equality exactly when G has a single edge.Source: §G.11 · p. 70
  • If the support contains every single-edge graph, distinct graphs have distinct κ profiles against that support, for both µ0 and µ1.The proof distinguishes them using a single-edge graph whose edge is present in one graph but absent in the other.Source: §G.12 · p. 70

G.12. Proof of Lemma 15.

  • A κ-preserving bijection B maps the single-edge graphs bijectively onto themselves.The proof uses that κ(Gij, Gij) = 5 and that single-edge graphs are the only graphs with this value.Source: §G.13 · p. 70

G.13. Proof of Lemma 16.

The proof characterizes κ-preserving maps on single-edge graphs as vertex relabelings, then establishes convergence of empirical objectives and their minimizers.

G.13. Proof of Lemma 16.

  • Two single-edge graphs share a vertex exactly when their images under B do, preserving the incidence relation among edges.Source: §G.13 · p. 71
  • The incidence-preserving bijection B acts on single-edge graphs as a fixed permutation of vertices, including the cases N = 2 and N = 3.For N ≥ 5, the proof builds the common-vertex structure from images of edges incident to vertex 1.Source: §G.13 · p. 71

G.14. Proof of Lemma 17.

  • The empirical and population objectives can be optimized over the closed ball of radius R0 = ∥B0∥1,2, where both are 2R0-Lipschitz.Their minimizers lie in the respective feasible sets, whose elements have 1-norm one.Source: §G.14 · p. 71
  • Weak convergence of µ0,n and µ1,n yields uniform convergence of ℓn to ℓ on BR0, and cluster points of empirical minimizers minimize ℓ while optimal values converge.Source: §G.14 · p. 72

Related papers

Loading 2609.03094v1…