mlsanityData to 7 Oct 2026

Semi-relaxed Gromov-Wasserstein divergence with applications on graphs

arXiv 2110.02753 ↗First posted 6 Oct 2021cs.LGcited by 21

Not on the map. Why?

Abstract (arXiv)

Comparing structured objects such as graphs is a fundamental operation involved in many learning tasks. To this end, the Gromov-Wasserstein (GW) distance, based on Optimal Transport (OT), has proven to be successful in handling the specific nature of the associated objects. More specifically, through the nodes connectivity relations, GW operates on graphs, seen as probability measures over specific spaces. At the core of OT is the idea of conservation of mass, which imposes a coupling between all the nodes from the two considered graphs. We argue in this paper that this property can be detrimental for tasks such as graph dictionary or partition learning, and we relax it by proposing a new semi-relaxed Gromov-Wasserstein divergence. Aside from immediate computational benefits, we discuss its properties, and show that it can lead to an efficient graph dictionary learning algorithm. We empirically demonstrate its relevance for complex tasks on graphs such as partitioning, clustering and completion.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). Builds on 32 of its 77 references that are in the map. First posted on arXiv 6 Oct 2021.

Builds on

32 of 77 references.

References · 32

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  3. 2013Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distancescited by 2,277
  4. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,131
  5. 2016Geometric deep learning: going beyond Euclidean datacited by 1,042
  6. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  7. 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 786
  8. 2018Computational Optimal Transportcited by 765
  9. 2019Graph U-Netscited by 489
  10. 2018Optimal Transport for structured data with application on graphscited by 170
  11. 2019A Survey on Graph Kernelscited by 148
  12. 2019Gromov-Wasserstein Learning for Graph Matching and Node Embeddingcited by 125
20 more
  1. 2019Wasserstein Weisfeiler-Lehman Graph Kernelscited by 104
  2. 2019Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matchingcited by 102
  3. 2018Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical propertiescited by 93
  4. 2019GOT: An Optimal Transport framework for Graph comparisoncited by 64
  5. 2016Convergence Rate of Frank-Wolfe for Non-Convex Objectivescited by 59
  6. 2020The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxationcited by 55
  7. 2017Distance Metric Learning using Graph Convolutional Networks: Application to Functional Brain Networkscited by 40
  8. 2020Generalized Spectral Clustering via Gromov-Wasserstein Learningcited by 37
  9. 2021Online Graph Dictionary Learningcited by 37
  10. 2020Learning Graphons via Structured Gromov-Wasserstein Barycenterscited by 36
  11. 2017Wasserstein Dictionary Learning: Optimal Transport-based unsupervised non-linear dictionary learningcited by 34
  12. 2018Bayesian Semi-supervised Learning with Graph Gaussian Processescited by 28
  13. 2015Adjusting for Chance Clustering Comparison Measurescited by 27
  14. 2019Gromov-Wasserstein Factorization Models for Graph Clusteringcited by 25
  15. 2017DS*: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problemscited by 20
  16. 2019GAP: Generalizable Approximate Graph Partitioning Frameworkcited by 18
  17. 2018Mean-field theory of graph neural networks in graph partitioningcited by 16
  18. 2016Optimal spectral transportation with application to music transcriptioncited by 11
  19. 2018(Probably) Concave Graph Matchingcited by 7
  20. 2020Partial Optimal Transport with Applications on Positive-Unlabeled Learningcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 5; 2023: 5; 2024: 4; 2025: 2; 2026: 5.

21 papers.

Sort:

  1. 2022Unbalanced Optimal Transport, from Theory to Numericscited by 45
  2. 2023A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarseningcited by 15
  3. 2023Fused Gromov-Wasserstein Graph Mixup for Graph-level Classificationscited by 15
  4. 2022Efficient Approximation of Gromov-Wasserstein Distance Using Importance Sparsificationcited by 11
  5. 2023A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein in Graph Datacited by 10
  6. 2024A New Robust Partial p-Wasserstein-Based Metric for Comparing Distributionscited by 7
  7. 2023Outlier-Robust Gromov-Wasserstein for Graph Datacited by 6
  8. 2024On Probabilistic Embeddings in Optimal Dimension Reductioncited by 5
  9. 2024Estimating Long-term Heterogeneous Dose-response Curve: Generalization Bound Leveraging Optimal Transport Weightscited by 4
  10. 2024Metric properties of partial and robust Gromov-Wasserstein distancescited by 2
  11. 2025Gradual Domain Adaptation for Graph Learningcited by 2
  12. 2022Fast and Provably Convergent Algorithms for Gromov-Wasserstein in Graph Datacited by 1
9 more
  1. 2022On the Convergence of Semi-Relaxed Sinkhorn with Marginal Constraint and OT Distance Gapscited by 1
  2. 2022Hybrid Gromov-Wasserstein Embedding for Capsule Learningcited by 1
  3. 2026Sliced Inner Product Gromov-Wasserstein Distancescited by 1
  4. 2023Interpolating between Clustering and Dimensionality Reduction with Gromov-Wassersteincited by 0
  5. 2025Towards Pre-trained Graph Condensation via Optimal Transportcited by 0
  6. 2026Supervised Distributional Reduction via Optimal Transport and Dependence Maximizationcited by 0
  7. 2026Bridging Maximum Likelihood and Optimal Transport for Efficient Inference and Model Selection in Stochastic Block Modelscited by 0
  8. 2026Network Learning with Semi-relaxed Gromov-Wassersteincited by 0
  9. 2026Unlocking Geodesic Gromov-Wasserstein Distances for 3D Modelingcited by 0