Metraipolis › archive › dc_7501ac909396

Discrete Gromov-Wasserstein Duality: Algorithms and Isomorphism Testing — arXiv:2609.03094

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.03094
License (as archived): CC0-1.0
Archived: 2026-10-17T02:22:37.682Z
SHA-256 of the archived text: 1e96e49839efeca38ea0d11c253cc5c2bdb14ca396e3b03323021ae1ec151e55
Stable URL of this page: https://metraipolis.com/documento/dc_7501ac909396

How to cite

Discrete Gromov-Wasserstein Duality: Algorithms and Isomorphism Testing — arXiv:2609.03094 — arXiv (en), https://arxiv.org/abs/2609.03094 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7501ac909396 (Metraipolis archive dc_7501ac909396, sha256 1e96e49839efeca38ea0d11c253cc5c2bdb14ca396e3b03323021ae1ec151e55)

BibTeX

@misc{dc7501ac909396,
  title = {Discrete Gromov-Wasserstein Duality: Algorithms and Isomorphism Testing — arXiv:2609.03094},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.03094},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7501ac909396; sha256 1e96e49839efeca38ea0d11c253cc5c2bdb14ca396e3b03323021ae1ec151e55},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.03094. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-09-04 in stat.ML).
Categorie arXiv: Statistics Theory (math.ST) ; Information Theory (cs.IT); Optimization and Control (math.OC); Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2609.03094 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T02:04:11.998Z dalla pagina https://arxiv.org/catchup/stat.ML/2026-09-04?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).