# Template based Graph Neural Network with Optimal Transport Distances

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 77 references that are in the map.
- First posted on arXiv 31 May 2022.

## Builds on (most cited first, 30 of 39)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [Learning Convolutional Neural Networks for Graphs](https://mlsanity.com/paper/1605.05273/) (2016)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)
- [Understanding Attention and Generalization in Graph Neural Networks](https://mlsanity.com/paper/1905.02850/) (2019)
- [Machine Learning on Graphs: A Model and Comprehensive Taxonomy](https://mlsanity.com/paper/2005.03675/) (2020)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks](https://mlsanity.com/paper/2111.06283/) (2021)
- [Wasserstein Weisfeiler-Lehman Graph Kernels](https://mlsanity.com/paper/1906.01277/) (2019)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical properties](https://mlsanity.com/paper/1811.02834/) (2018)
- [Rethinking pooling in graph neural networks](https://mlsanity.com/paper/2010.11418/) (2020)
- [GOT: An Optimal Transport framework for Graph comparison](https://mlsanity.com/paper/1906.02085/) (2019)
- [Convergence Rate of Frank-Wolfe for Non-Convex Objectives](https://mlsanity.com/paper/1607.00345/) (2016)
- [Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs](https://mlsanity.com/paper/2106.01128/) (2021)

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

- [Optimizing OOD Detection in Molecular Graphs: A Novel Approach with Diffusion Models](https://mlsanity.com/paper/2404.15625/) (2024)
- [Rethinking Node-wise Propagation for Large-scale Graph Learning](https://mlsanity.com/paper/2402.06128/) (2024)
- [Fused Gromov-Wasserstein Graph Mixup for Graph-level Classifications](https://mlsanity.com/paper/2306.15963/) (2023)
- [Distributional Reduction: Unifying Dimensionality Reduction and Clustering with Gromov-Wasserstein](https://mlsanity.com/paper/2402.02239/) (2024)
- [Graph Classification via Reference Distribution Learning: Theory and Practice](https://mlsanity.com/paper/2408.11370/) (2024)
- [Semidefinite Relaxations of the Gromov-Wasserstein Distance](https://mlsanity.com/paper/2312.14572/) (2023)
- [Self-Attention Amortized Distributional Projection Optimization for Sliced Wasserstein Point-Cloud Reconstruction](https://mlsanity.com/paper/2301.04791/) (2023)
- [Structure-Aware E(3)-Invariant Molecular Conformer Aggregation Networks](https://mlsanity.com/paper/2402.01975/) (2024)
- [Differentiable Cluster Graph Neural Network](https://mlsanity.com/paper/2405.16185/) (2024)
- [Towards Data-centric Machine Learning on Directed Graphs: a Survey](https://mlsanity.com/paper/2412.01849/) (2024)
- [Gradual Domain Adaptation for Graph Learning](https://mlsanity.com/paper/2501.17443/) (2025)
- [Learning signals defined on graphs with optimal transport and Gaussian process regression](https://mlsanity.com/paper/2410.15721/) (2024)
- [Cross-View Topology-Aware Graph Representation Learning](https://mlsanity.com/paper/2512.02130/) (2025)
- [Structure-Sensitive Graph Dictionary Embedding for Graph Classification](https://mlsanity.com/paper/2306.10505/) (2023)
- [Interpolating between Clustering and Dimensionality Reduction with Gromov-Wasserstein](https://mlsanity.com/paper/2310.03398/) (2023)
- [Learning local and global prototypes with optimal transport for unsupervised anomaly detection and localization](https://mlsanity.com/paper/2508.12927/) (2025)
- [FnRGNN: Distribution-aware Fairness in Graph Neural Network](https://mlsanity.com/paper/2510.19257/) (2025)
- [Explainable Graph Representation Learning via Graph Pattern Analysis](https://mlsanity.com/paper/2512.04530/) (2025)
- [Bridging Maximum Likelihood and Optimal Transport for Efficient Inference and Model Selection in Stochastic Block Models](https://mlsanity.com/paper/2605.28488/) (2026)
- [Preserving Geometric Integrity in Graph Prompting via Measure-Constrained Optimal Transport](https://mlsanity.com/paper/2609.23547/) (2026)

## Abstract (arXiv)

Current Graph Neural Networks (GNN) architectures generally rely on two important components: node features embedding through message passing, and aggregation with a specialized form of pooling. The structural (or topological) information is implicitly taken into account in these two steps. We propose in this work a novel point of view, which places distances to some learnable graph templates at the core of the graph representation. This distance embedding is constructed thanks to an optimal transport distance: the Fused Gromov-Wasserstein (FGW) distance, which encodes simultaneously feature and structure dissimilarities by solving a soft graph-matching problem. We postulate that the vector of FGW distances to a set of template graphs has a strong discriminative power, which is then fed to a non-linear classifier for final predictions. Distance embedding can be seen as a new layer, and can leverage on existing message passing techniques to promote sensible feature representations. Interestingly enough, in our work the optimal set of template graphs is also learnt in an end-to-end fashion by differentiating through this layer. After describing the corresponding learning procedure, we empirically validate our claim on several synthetic and real life graph classification datasets, where our method is competitive or surpasses kernel and GNN state-of-the-art approaches. We complete our experiments by an ablation study and a sensitivity analysis to parameters.