Reproduce “Semi-relaxed Gromov-Wasserstein divergence with applications on graphs” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Cédric Vincent-Cuaz, Rémi Flamary, Marco Corneli, Titouan Vayer, Nicolas Courty

A semi-relaxed Gromov-Wasserstein (srGW) divergence is introduced, extending the Gromov-Wasserstein distance by relaxing mass conservation on one distribution for flexible graph comparison. This approach allows for partial graph matching and adaptive node reweighting, demonstrating superior or competitive performance across graph partitioning, clustering, and completion tasks with significantly reduced computational costs.

Key insights

  • srGW is asymmetric and can learn sparse target distributions, naturally accommodating partial graph matching or focusing on relevant subgraphs.
  • Relaxing a marginal constraint simplifies the optimization subproblem, leading to significant computational efficiency gains (e.g., 2-3 orders of magnitude faster embedding computation).
  • Learning the optimal node importance for one graph during comparison provides more flexible and potentially accurate results than relying on predefined distributions.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.