# On a linear fused Gromov-Wasserstein distance for graph structured data

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 34 references that are in the map.
- First posted on arXiv 9 Mar 2022.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [Wasserstein Weisfeiler-Lehman Graph Kernels](https://mlsanity.com/paper/1906.01277/) (2019)
- [Wasserstein Embedding for Graph Learning](https://mlsanity.com/paper/2006.09430/) (2020)
- [Metrics for Graph Comparison: A Practitioner's Guide](https://mlsanity.com/paper/1904.07414/) (2019)
- [Faster Kernels for Graphs with Continuous Attributes via Hashing](https://mlsanity.com/paper/1610.00064/) (2016)
- [Gromov-Wasserstein Factorization Models for Graph Clustering](https://mlsanity.com/paper/1911.08530/) (2019)
- [On a linear Gromov-Wasserstein distance](https://mlsanity.com/paper/2112.11964/) (2021)
- [Learning subtree pattern importance for Weisfeiler-Lehmanbased graph kernels](https://mlsanity.com/paper/2106.04739/) (2021)
- [The Resistance Perturbation Distance: A Metric for the Analysis of Dynamic Networks](https://mlsanity.com/paper/1605.01091/) (2016)

## Built on by (most cited first, 9 of 9)

- [Graph Data Selection for Domain Adaptation: A Model-Free Approach](https://mlsanity.com/paper/2505.17293/) (2025)
- [Wasserstein Gradient Flow over Variational Parameter Space for Variational Inference](https://mlsanity.com/paper/2310.16705/) (2023)
- [Moreau-Yoshida Variational Transport: A General Framework For Solving Regularized Distributional Optimization Problems](https://mlsanity.com/paper/2307.16358/) (2023)
- [Multiple Wasserstein Gradient Descent Algorithm for Multi-Objective Distributional Optimization](https://mlsanity.com/paper/2505.18765/) (2025)
- [Generalized Wasserstein Flow Matching: Transport Plans, Everywhere, All at Once](https://mlsanity.com/paper/2605.08424/) (2026)
- [Transfer Learning on Edge Connecting Probability Estimation under Graphon Model](https://mlsanity.com/paper/2510.05527/) (2025)
- [Accelerated Multiple Wasserstein Gradient Flows for Multi-objective Distributional Optimization](https://mlsanity.com/paper/2601.19220/) (2026)
- [Fused Gromov-Wasserstein Variance Decomposition with Linear Optimal Transport](https://mlsanity.com/paper/2411.10204/) (2024)
- [A dictionary learning framework for graphs via filters and optimal transport](https://mlsanity.com/paper/2609.05919/) (2026)

## Abstract (arXiv)

We present a framework for embedding graph structured data into a vector space, taking into account node features and topology of a graph into the optimal transport (OT) problem. Then we propose a novel distance between two graphs, named linearFGW, defined as the Euclidean distance between their embeddings. The advantages of the proposed distance are twofold: 1) it can take into account node feature and structure of graphs for measuring the similarity between graphs in a kernel-based framework, 2) it can be much faster for computing kernel matrix than pairwise OT-based distances, particularly fused Gromov-Wasserstein, making it possible to deal with large-scale data sets. After discussing theoretical properties of linearFGW, we demonstrate experimental results on classification and clustering tasks, showing the effectiveness of the proposed linearFGW.