Diffusion enabled Optimal Transport distances for graph matching
Summary
Introduces Diffusion Semi-Relaxed Fused Gromov-Wasserstein (DsrFGW), a novel method that integrates node features and structural connectivity for graph comparison via optimal transport and diffusion processes, demonstrating improved robustness to noise and missing edges on synthetic tasks.
View Cached Full Text
Cached at: 07/09/26, 07:42 AM
# Diffusion enabled Optimal Transport distances for graph matching Source: [https://arxiv.org/abs/2607.06646](https://arxiv.org/abs/2607.06646) [View PDF](https://arxiv.org/pdf/2607.06646) > Abstract: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\. ## Submission history From: Iman Seyedi \[[view email](https://arxiv.org/show-email/6d2324db/2607.06646)\] **\[v1\]**Tue, 7 Jul 2026 15:55:34 UTC \(772 KB\)
Similar Articles
Multimarginal flow matching with optimal transport potentials
Proposes OTP-FM, a novel method for multimarginal flow matching that uses optimal transport potentials to softly steer flows through intermediate marginals, achieving state-of-the-art performance on single-cell RNA sequencing, oceanographic, and meteorological datasets.
The Geometry Behind Diffusion and Flow Matching: Gradient Flows and Geodesics in Wasserstein Space
This paper reveals that diffusion models and flow matching are two sides of the same Wasserstein geometry: diffusion follows a free-energy gradient flow (initial-value problem), while flow matching follows a Wasserstein geodesic (boundary-value problem), and they are unified through the JKO scheme.
Scalable Optimal Transport Algorithm for Network Alignment
FastAlign presents a scalable, sparsity-aware framework for optimal transport-based network alignment, achieving state-of-the-art accuracy while reducing runtime by up to 9.45x on CPU and 32.54x on GPU.
Geometry-Aware Tabular Diffusion
Introduces Geometry-Aware Tabular Diffusion (GATD), which augments tabular diffusion denoisers with explicit pairwise geometric features. Achieves state-of-the-art performance on ten benchmarks while using significantly fewer parameters.
Enhanced Graph Neural Networks using K-Hop Gaussian Diffusion
This paper proposes a K-Hop Gaussian (KHG) diffusion kernel as a preprocessing module for graph neural networks, balancing local and global information propagation to mitigate over-smoothing and information bottlenecks. Experiments show significant improvements over traditional message-passing GNNs and existing diffusion kernels, especially on noisy or structurally complex graphs.