# Diffusion enabled Optimal Transport distances for graph matching

arXiv: https://arxiv.org/abs/2607.06646 · HTML: https://mlsanity.com/paper/2607.06646/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 34 references that are in the map.
- First posted on arXiv 7 Jul 2026.

## Builds on (most cited first, 8 of 8)

- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical properties](https://mlsanity.com/paper/1811.02834/) (2018)
- [Convergence Analysis for General Probability Flow ODEs of Diffusion Models in Wasserstein Distances](https://mlsanity.com/paper/2401.17958/) (2024)
- [A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening](https://mlsanity.com/paper/2306.08854/) (2023)
- [Hypergraph Co-Optimal Transport: Metric and Categorical Properties](https://mlsanity.com/paper/2112.03904/) (2021)
- [Optimal and Diffusion Transports in Machine Learning](https://mlsanity.com/paper/2512.06797/) (2025)
- [Gromov-Wasserstein Graph Coarsening](https://mlsanity.com/paper/2511.08733/) (2025)
- [Optimal Transport-Based Clustering of Attributed Graphs with an Application to Road Traffic Data](https://mlsanity.com/paper/2512.15570/) (2025)

## Abstract (arXiv)

This paper introduces Diffusion Semi-Relaxed Fused Gromov-Wasserstein (DsrFGW), a novel method for graph comparison that unifies node features and structural connectivity through optimal transport. While traditional Gromov-Wasserstein and semi-relaxed variants (srGW, srFGW) capture graph structure, they often struggle with sparse, noisy, or partially observed graphs. Inspired by Graph Diffusion Distance, which posits graphs are similar if they enable similar information transmission patterns, DsrFGW incorporates diffusion processes allowing information propagation across nodes, capturing local and global structural patterns while reducing sensitivity to noise or missing edges. An extensive evaluation on 36 synthetic pairwise graph matching tasks (easy, medium, hard) demonstrates consistent superiority over srFGW, achieving accuracy improvements of 0-20 percentage points and dramatic Adjusted Rand Index (ARI) gains: in medium-difficulty scenarios, srFGW often achieves negative ARI (worse than random) while DsrFGW offers better performance in terms of both internal and external clustering quality measures (i.e., Adjusted Rank Index and Accuracy with respect to the true underlying clusters, respectively). Even under severe noise, DsrFGW improves clustering quality in 92% of the synthetic tasks with optimal diffusion scales adapting to problem difficulty, establishing DsrFGW as a robust framework for graph comparison under structural uncertainty.