Discrete Gromov-Wasserstein Duality: Algorithms and Isomorphism Testing

What the math gives to ML

The paper supplies a discrete Gromov–Wasserstein objective together with a useful quadratic representation for graph collections: for squared costs, the interaction matrix can be written as a negative Kronecker product of positive-semidefinite kernel matrices. This exposes a low-rank factorization that can replace explicit pair-of-pairs computations in a neural graph-alignment module. The paper also gives convergence bounds for optimization with uniformly inexact gradient oracles, which is directly relevant when the GW gradient is approximated by truncated low-rank products or minibatches. The most promising transfer is a structure-aware cross-attention layer whose transport matrix is optimized under graph-intrinsic costs rather than learned from node features alone.