{"id":"6337b1da-2eb8-479a-81bd-bb3fc53d39a2","arxiv_id":"2504.14673","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A continuous version of the moment-SOS hierarchy for Gromov-Wasserstein distance is introduced, with proof of convergence, pseudo-metric structure, and sample-complexity bounds.","lead":"This paper extends the moment sum-of-squares hierarchy, a method for relaxing hard optimization problems, to the continuous Gromov-Wasserstein problem of matching distributions across different spaces. It proves that the relaxed problems converge to the exact Gromov-Wasserstein distance, define a pseudo-metric on metric measure spaces, and are statistically consistent under sampling.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5.2 defines a set function that is not a measure, so the gluing step backing Theorem 5.1 is invalid as written.","rationale":"The reader's conditional verdict was based partly on Lemma 4.4's false support assertion. That gap is real but repairable: P_{c,ε} is the pushforward of P under the cell-center map, and (PSD+) is preserved by measurable pushforwards, so the discretization step in Theorem 4.2 can be fixed. The more serious unaddressed flaw is the gluing construction in Lemma 5.2, which is needed for Theorem 5.1. The displayed set function is not a measure, so the proof of the pseudo-metric property does not currently go through. The flaw is concrete and testable, though likely fixable by writing the gluing as a disintegration and invoking the discrete gluing lemma with the correct summation over Y-cells. Since the convergence theorem (4.2) is not directly affected and the gluing gap is repairable, the conditional verdict remains appropriate.","tokens_in":25509,"tokens_out":28436,"duration_ms":254875,"concrete_test":"Take X=Z={0,1}, Y={0,1} with ν uniform, and A=C={(0,0)}. Let P disintegrate as P^0=δ_{(0,0)}, P^1=0, and Q as Q^0=0, Q^1=δ_{(0,0)}. Then the paper's formula gives S(A,{0},C)=0 and S(A,{1},C)=0, but S(A,{0,1},C)=1/4, violating additivity. This shows the displayed set function in Lemma 5.2 is not a measure.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 5.2 constructs S on rectangles by S(A×B×C)=P(A×B)Q(B×C)/ν^{2r}(B), with value 0 when the denominator is 0. This set function is not countably additive: for disjoint B1,B2 the denominator changes, so S(A,(B1∪B2),C) is not generally S(A,B1,C)+S(A,B2,C). Hence S does not extend to a probability measure on (X×Y×Z)^{2r}, and the definition of R=S|(X×Z)^{2r} is not meaningful. The later PSD+ verification inherits this problem: Step 2's formula for R_{c,1/s} also omits the summation over y-cells, so the reduction to the discrete gluing lemma [TNS25, Lemma 5.2] is not established. The correct construction is the disintegration S = ∫ P^y ⊗ Q^y dν^{2r}(y), with R the marginal on (X×Z)^{2r}; PSD+ of R can then be justified via partial traces / the discrete lemma after summing over y-cells. As written, Theorem 5.1's pseudo-metric claim is unproven.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes continuous extensions of the moment sum-of-squares hierarchy for the Gromov-Wasserstein problem. The authors define a relaxation (12) in which the decision variable is a probability measure on (X×Y)^{2r} satisfying symmetry, marginal, and a positive-semidefiniteness condition (PSD+). They claim three main results: Theorem 4.2 states that the optimal values of these relaxations converge to the GW distance; Theorem 5.1 states that each relaxation induces a pseudo-metric on metric measure spaces via a gluing lemma; Theorem 6.1 gives a sample-complexity bound for empirical versions of the hierarchy. The proofs proceed by reducing continuous problems to discrete ones and invoking the authors' previous unpublished results in [TNS25].","tokens_in":25615,"tokens_out":22698,"duration_ms":216578,"significance":"If the three main claims were established, the paper would make a valuable contribution: it would provide a tractable SDP-based hierarchy that approximates the (NP-hard) Gromov-Wasserstein problem, with convergence, metric structure, and statistical consistency. The PSD+ formulation is a natural continuous analogue of the finite-dimensional PSD condition, and the sample-complexity rate in Theorem 6.1 is of independent interest. The paper is clear and well motivated. However, several load-bearing proof steps are invalid as written: the claimed equivalence between the moment formulation and the measure formulation in Section 3 fails, the discretization Lemma 4.4 contains a false support assertion, and the gluing construction in Lemma 5.2 does not define a measure. These issues affect the central convergence and pseudo-metric claims. The results remain plausible and may be repairable, but the manuscript in its current form does not support its main theorems.","major_comments":[{"comment":"The claimed equivalence between (S-DGW-r2) and the measure formulation (9) is false as stated. In the reverse mapping, lower-degree moments are defined by ℓ(π^γ) := Σ_{τ: |τ+γ|=2r} ℓ(π^{τ+γ}), summing over multi-indices τ rather than over concrete coordinate sequences. This discards multinomial multiplicities. For example, take X=Y={x1,x2}, r=1, and P = 1/2 δ_{(x1,y1,x2,y2)} + 1/2 δ_{(x2,y2,x1,y1)}. Then the two atoms give the same monomial π_{11}π_{22}, but the formula (11) for γ=0 returns y0 = ℓ(π_{11}π_{22}) = 1/2, not 1. Thus a valid probability P is mapped to a moment sequence violating y0=1. Conversely, for m=n=1,r=1, the moment data y0=y11=1, y1111=2 satisfies the constraints of (S-DGW-r2), but the associated object P has total mass 2 and is not a probability measure. Hence the feasible sets are not in bijection, and the claimed exact correspondence between (9) and (S-DGW-r2) is not established. This invalidates the later statement that the continuous hierarchy exactly recovers the discrete hierarchy and undermines the use of [TNS25] in the proof of Theorem 4.2.","section":"Section 3, Eq. (11)"},{"comment":"The proof of Lemma 4.4 contains a false statement: it says that 'P is supported in the set {(x_i1, y_j1, ..., x_i2r, y_j2r)}', but P is a general probability measure on (X×Y)^{2r} and need not be supported on the finite grid. Consequently, the displayed equality between the integral over P_{c,ε} and the integral over P is not justified for arbitrary measurable f and g. The lemma may be repairable by proving PSD+ for P_{c,ε} through step functions or conditional expectations, but that argument is not supplied. Since Lemma 4.4 is used both for the bound (16) and for the reduction in Theorem 4.2, this is a load-bearing gap.","section":"Lemma 4.4"},{"comment":"The constructed set function S is not countably additive, so it does not extend to a probability measure on (X×Y×Z)^{2r}. For disjoint B1,B2 ⊂ Y^{2r}, the definition gives S(A×(B1∪B2)×C) = P(A×(B1∪B2))Q((B1∪B2)×C)/ν^{2r}(B1∪B2), which is not equal to S(A×B1×C)+S(A×B2×C) in general. A concrete finite example is obtained by taking ν(B1)=ν(B2)=1/2, P(A×B_i)=a_i, Q(B_i×C)=b_i; then the union value is 2(a1+a2)(b1+b2) while the sum is 2a1b1+2a2b2. Therefore R := S|_{(X×Z)^{2r}} is not well defined as a marginal of a measure, and the PSD+ verification for R in Step 2 is meaningless. The formula for R_{c,1/s} in Step 2 also omits the required summation over the intermediate y-cells. The appeal to [TNS25, Lemma 5.2] does not fix this, because the object to which that discrete lemma would be applied has not been constructed as a measure. Since Lemma 5.2 is the basis for the triangle inequality in Theorem 5.1 and for the sample-complexity argument in Section 6, both of those results are unsupported as written.","section":"Lemma 5.2"},{"comment":"The claimed density statement that the union over s of SF[t,s] is dense in B((X×Y)^t) with respect to the L∞ topology is false for arbitrary bounded measurable functions. Functions constant on a fixed finite metric partition cannot uniformly approximate a general measurable function that oscillates within partition cells. This affects the reduction of (PSD+) to step functions in Step 1, and a similar issue appears in the discretization arguments in Lemmas 4.4 and 4.6. A correct treatment would need a conditional-expectation or L2-martingale argument rather than uniform approximation. As written, the PSD+ verification for glued or discretized measures is not rigorous.","section":"Lemma 5.2, Step 1"},{"comment":"The proof of Proposition 6.2 is a heuristic accounting rather than a construction of a feasible transportation plan. It describes moving mass according to discrepancies at each dyadic level but does not specify how these moves are combined into a single coupling with the correct marginals, nor does it rigorously account for the cost of intermediate moves without double-counting. The final bound is plausible, but since Theorem 6.1 and the statistical consistency statement (20) depend on Proposition 6.2, the proof needs to be made precise.","section":"Section 6.2, Proposition 6.2"}],"minor_comments":[{"comment":"There are typos in the notation for the partitions: the target space is written as Y = ⨆_{j=1}^l Yi and later ν_{c,ε}(yi) = μ(Yi); these should be Y_j and ν(Y_j), respectively.","section":"Section 4, Eq. (13)"},{"comment":"The spaces B((X×Y)^n) and B+((X×Y)^n) are not given integrability or boundedness assumptions. Since (PSD+) integrates arbitrary measurable f, the integrals may fail to be finite; the definitions should specify bounded measurable functions or an equivalent integrability convention.","section":"Sections 4 and 5"},{"comment":"The notation for the pseudo-metric is inconsistent: the theorem states GW := GW^{(r)}_{p,q}, but the proof and surrounding text sometimes use GW without the superscript. This should be cleaned up.","section":"Section 5, Theorem 5.1"},{"comment":"The sentence about the product sigma-algebra should refer to B(X^{2r}) ⊗ B(Y^{2r}) ⊗ B(Z^{2r}) generating B((X×Y×Z)^{2r}); the current wording can be read as claiming a Cartesian-product generating property.","section":"Section 5, Lemma 5.2 proof"},{"comment":"The notation ∆ and ∆^{(r)} is used in the derivation of (20) before the definitions are explicitly stated. A short definition at the beginning of the section would improve readability.","section":"Section 6"},{"comment":"In the proof of Lemma 6.3, the equality after separation of sums is valid but should explicitly mention that the cross terms vanish because π has total mass on S; the current presentation is terse.","section":"Section 6.2, Lemma 6.3"}],"recommendation":"major_revision","confidential_remarks":"The paper relies heavily on [TNS25], an unpublished preprint by the same authors. If this companion work is not part of the review package, the editors should require the authors to include it or to give self-contained proofs of the discrete convergence and discrete gluing results, since those results are load-bearing here. The errors identified in Section 3 and Lemma 5.2 are substantial, but they appear to be repairable in a major revision rather than fatal to the overall research program."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. First, the core idea is real: they define a continuous moment-SOS relaxation for Gromov-Wasserstein via a positivity condition on probability measures, and they prove convergence, a pseudo-metric property, and a sample-complexity bound. Second, the proof of the gluing lemma (Lemma 5.2) is wrong as written. The set function S defined on rectangles by S(A×B×C)=P(A×B)Q(B×C)/ν^{2r}(B) is not countably additive, so it is not a measure. That means R=S|(X×Z)^{2r} is not well-defined and Theorem 5.1 is unproved. I checked the stress-test concern and it holds. The fix is standard—use the disintegration S = ∫ P^y ⊗ Q^y dν^{2r}(y)—and the paper even hints at the right ingredients, but the proof as it stands is invalid.\n\nNow the good parts. The continuous extension itself, with the PSD+ constraint, is a legitimate contribution. The convergence theorem (Theorem 4.2) is plausible and the concentration/extension strategy is sound in principle, modulo two caveats: Lemma 4.4 contains a false statement that P is supported on the finite atom set (the integral equality can still be recovered with step functions, so this is a minor fix), and the argument leans on the authors' unpublished [TNS25] for the discrete convergence result. The sample-complexity section is more solid: it adapts Niles-Weed–Bach cleanly, and the rates look right for the L^{p,q} cost.\n\nThe main soft spot, in proportion, is the gluing lemma. It is not a side remark—it underpins the pseudo-metric result that the paper advertises as a key novelty. But because the correct construction is known and short, I would guess the authors can repair it. The other caveats are minor or standard in this area.\n\nWho is this for? Researchers working on Gromov-Wasserstein relaxations and moment-SOS hierarchies. They will find the continuous extension and the sample-complexity result useful even if the pseudo-metric theorem needs tightening. It deserves a serious referee: the idea is good, the errors are identifiable and fixable, and the literature would benefit from a corrected version. My recommendation is to send it to peer review with a clear instruction to the authors that Lemma 5.2 must be rewritten before acceptance.","headline":"A genuinely interesting continuous extension of the moment-SOS hierarchy for Gromov-Wasserstein, but the proof of the gluing lemma is broken as written and needs repair before the pseudo-metric claim can be trusted.","tokens_in":26249,"tokens_out":2923,"would_cite":false,"duration_ms":27013,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C22","90C26","49Q22","60B05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper extends the moment-SOS hierarchy to continuous Gromov-Wasserstein settings and proves that the hierarchy converges to the exact distance, defines a pseudo-metric, and enjoys sample-consistency.","keywords":["Gromov-Wasserstein distance","moment-SOS hierarchy","semidefinite programming","optimal transport","metric measure spaces","pseudo-metric","sample complexity","positive semidefinite constraint"],"falsifier":"Take $X=Y=[0,1]$ with uniform measures and a smooth cost, choose a feasible $P$ in (12) given by a density that spreads mass across several partition cells, and check whether its $\\varepsilon$-concentration $P_{c,\\varepsilon}$ satisfies (PSD+) for all step functions $f$ and $g$; a single violation would show Lemma 4.4's construction fails, and comparing the resulting values with the claimed $8C\\varepsilon$ bound would settle whether Theorem 4.2 needs a different discretization argument.","tokens_in":25210,"feed_emoji":"📐","tokens_out":6527,"duration_ms":52933,"temperature":0.7,"pith_summary":"The paper establishes a continuous version of the moment-SOS hierarchy for the Gromov-Wasserstein problem: instead of discretizing the source and target distributions, it works directly with probability measures and replaces the finite-dimensional positive-semidefiniteness constraint by a function-space condition. Its main theorem says the optimal values of these relaxations increase to the true Gromov-Wasserstein distance as the hierarchy level grows, so the distance is the limit of semidefinite programs even in the continuous setting. It also shows each level of the hierarchy induces a pseudo-metric on metric measure spaces and proves a sample-consistency result: empirical versions computed from i.i.d. samples converge to the continuous value, with an explicit rate governed by an intrinsic dimension. A sympathetic reader would care because Gromov-Wasserstein itself is NP-hard, while the proposed relaxations are tractable SDPs that preserve the geometric and statistical structure of the original problem.","feed_headline":"Moment-SOS relaxations converge to exact Gromov-Wasserstein distance","feed_subtitle":"Each hierarchy level is a tractable semidefinite program and estimates the distance from samples consistently.","key_machinery":"The load-bearing object is the constraint (PSD+): for every $t\\le r$, every measurable $f$ on $(X\\times Y)^{2t}$, and every nonnegative measurable $g$ on $(X\\times Y)^{2r-2t}$, the integral of $f(x_1,y_1,\\dots,x_t,y_t) f(x_{t+1},y_{t+1},\\dots,x_{2t},y_{2t}) g(x_{2t+1},\\dots,x_{2r},y_{2r})$ against the candidate measure $P$ must be nonnegative. This is the continuous analogue of requiring all principal moment and localizing matrices to be positive semidefinite; it is what makes the relaxation simultaneously tractable and strong. The convergence proof is carried by $\\varepsilon$-concentration and $\\varepsilon$-extension maps that move a continuous feasible measure to a discrete one and back, introducing only an additive error of at most $8C\\varepsilon$, after which the known convergence theorem for the discrete hierarchy applies.","core_discovery":"The central discovery is a well-defined sequence of relaxations $\\mathrm{gw}^{(r)}(\\mu,\\nu)$ of the continuous Gromov-Wasserstein problem, stated over probability measures on $(X\\times Y)^{2r}$ with symmetry, marginal, and a positive-semidefinite-type constraint (PSD+). The paper proves three structural facts about this sequence. First, the values converge: $\\mathrm{gw}^{(r)}(\\mu,\\nu) \\to \\mathrm{gw}(\\mu,\\nu)$ as $r\\to\\infty$ for compact Polish metric measure spaces with diameter one and Lipschitz cost. Second, for the $L_{p,q}$ cost, each level defines a pseudo-metric over metric measure spaces, satisfying symmetry, non-negativity, vanishing on diagonals, and the triangle inequality via a gluing lemma that respects (PSD+). Third, the empirical analogue computed from samples is statistically consistent: under an intrinsic-dimension condition, $\\mathbb{E}[\\mathrm{gw}(\\mu, \\hat{\\mu}_n)]$ is bounded by terms of order $n^{-pq/s}$, $n^{-p/s}$, and $n^{-1/2}$, so the GW distance can be estimated from data. The paper also shows that discrete instances of these relaxations coincide exactly with the earlier moment-SOS hierarchy, so the continuous construction is an extension rather than a new unrelated object.","pith_inferences":["A likely testable extension is to replace the product form $f\\otimes f\\otimes g$ in (PSD+) with other positive kernels; each kernel choice would give a different continuous hierarchy, and only some of them may converge for non-Lipschitz costs.","The rate $n^{-1/s}$ suggests that for heavy-tailed or fractal measures the hierarchy's sample complexity degrades exactly as the covering dimension grows; measuring this on synthetic uniform versus fractal data would be a direct check.","If the convergence of the hierarchy in $r$ can be quantified, the pseudo-metrics could be used as a certificate of closeness between large metric measure spaces without computing an optimal transport plan."],"forward_implications":["If the convergence theorem is correct, the Gromov-Wasserstein distance is the limit of a sequence of semidefinite programs, so the NP-hard continuous problem is approached by tractable lower bounds that are guaranteed to tighten.","Each hierarchy level defines its own pseudo-metric on metric measure spaces, giving a family of computable distances interleaving with the exact Gromov-Wasserstein distance.","Empirical Gromov-Wasserstein values computed from samples converge in expectation to the true distance at a rate that depends on an intrinsic dimension of the underlying measure, not on the ambient dimension.","The discrete analogue is exactly the earlier moment-SOS hierarchy, so numerical implementations for the discrete case carry over without changing the formulation.","The same template, replacing finite PSD matrices by an integral condition on measures, may apply to other optimization problems whose objective and constraints are polynomial in a distribution."],"supporting_citations":[{"why":"Supplies the discrete moment-SOS hierarchy and its convergence result that Theorem 4.2 invokes after $\\varepsilon$-concentration.","marker":"[TNS25]"},{"why":"Defines the Gromov-Wasserstein distance that this paper relaxes.","marker":"[Mém11]"},{"why":"Provides the dyadic partition and empirical-measure bounds reused in the sample-complexity proof.","marker":"[NWB19]"},{"why":"Gives the p=q=2 statistical-consistency result that Section 6 extends to general $L_{p,q}$ distortion distances.","marker":"[ZGMS24]"},{"why":"Supplies the Positivstellensatz background justifying convergence of moment relaxations.","marker":"[Sch17]"}],"fun_headline_variants":["Moment-SOS hierarchy converges to exact Gromov-Wasserstein","Continuous SOS relaxations give exact GW distance, provably","Moment-SOS meets Gromov-Wasserstein: exact limits from samples","Semidefinite hierarchy nails Gromov-Wasserstein exactly","GW distance from SOS relaxations: convergent and sample-consistent"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The convergence proof assumes that shrinking a continuous measure onto finitely many representative points keeps the positive-semidefinite constraint intact, but the argument as written presumes the measure is already supported on those points, and it also leans on the not-yet-published discrete convergence theorem of the same authors.","fun_headline_variants_meta":{"raw":{"variants":["Moment-SOS hierarchy converges to exact Gromov-Wasserstein","Continuous SOS relaxations give exact GW distance, provably","Moment-SOS meets Gromov-Wasserstein: exact limits from samples","Semidefinite hierarchy nails Gromov-Wasserstein exactly","GW distance from SOS relaxations: convergent and sample-consistent"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000675,"raw_usage":{"total_tokens":3150,"prompt_tokens":1102,"completion_tokens":2048,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":718,"completion_tokens_details":{"reasoning_tokens":1957}},"tokens_in":718,"tokens_out":2048,"duration_ms":12182,"temperature":1.0,"reasoning_tokens":1957,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:43:18.014684+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $X=Y=[0,1]$ with uniform measures and a smooth cost, choose a feasible $P$ in (12) given by a density that spreads mass across several partition cells, and check whether its $\\varepsilon$-concentration $P_{c,\\varepsilon}$ satisfies (PSD+) for all step functions $f$ and $g$; a single violation would show Lemma 4.4's construction fails, and comparing the resulting values with the claimed $8C\\varepsilon$ bound would settle whether Theorem 4.2 needs a different discretization argument.","supporting_citations":[],"review_version":1}