# Wasserstein Weisfeiler-Lehman Graph Kernels

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

## Key facts

- Cited by 104 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2019.

## Built on by (most cited first, 30 of 104)

- [GraphPrompt: Unifying Pre-Training and Downstream Tasks for Graph Neural Networks](https://mlsanity.com/paper/2302.08043/) (2023)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants](https://mlsanity.com/paper/2201.07083/) (2022)
- [Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks](https://mlsanity.com/paper/2210.01906/) (2022)
- [Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions](https://mlsanity.com/paper/2106.01098/) (2021)
- [Generalized Graph Prompt: Toward a Unification of Pre-Training and Downstream Tasks on Graphs](https://mlsanity.com/paper/2311.15317/) (2023)
- [Online Graph Dictionary Learning](https://mlsanity.com/paper/2102.06555/) (2021)
- [SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks](https://mlsanity.com/paper/2203.13913/) (2022)
- [SBERT studies Meaning Representations: Decomposing Sentence Embeddings into Explainable Semantic Features](https://mlsanity.com/paper/2206.07023/) (2022)
- [Topological Relational Learning on Graphs](https://mlsanity.com/paper/2110.15529/) (2021)
- [Semi-relaxed Gromov-Wasserstein divergence with applications on graphs](https://mlsanity.com/paper/2110.02753/) (2021)
- [SMATCH++: Standardized and Extended Evaluation of Semantic Graphs](https://mlsanity.com/paper/2305.06993/) (2023)
- [Template based Graph Neural Network with Optimal Transport Distances](https://mlsanity.com/paper/2205.15733/) (2022)
- [Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernels](https://mlsanity.com/paper/2104.02995/) (2021)
- [The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs](https://mlsanity.com/paper/2105.05911/) (2021)
- [Curvature Filtrations for Graph Generative Model Evaluation](https://mlsanity.com/paper/2301.12906/) (2023)
- [HAQJSK: Hierarchical-Aligned Quantum Jensen-Shannon Kernels for Graph Classification](https://mlsanity.com/paper/2211.02904/) (2022)
- [Weisfeiler-Leman in the BAMBOO: Novel AMR Graph Metrics and a Benchmark for AMR Graph Similarity](https://mlsanity.com/paper/2108.11949/) (2021)
- [Weisfeiler-Lehman meets Gromov-Wasserstein](https://mlsanity.com/paper/2202.02495/) (2022)
- [Graph Classification via Reference Distribution Learning: Theory and Practice](https://mlsanity.com/paper/2408.11370/) (2024)
- [A Generalized Weisfeiler-Lehman Graph Kernel](https://mlsanity.com/paper/2101.08104/) (2021)
- [SLOSH: Set LOcality Sensitive Hashing via Sliced-Wasserstein Embeddings](https://mlsanity.com/paper/2112.05872/) (2021)
- [On a linear fused Gromov-Wasserstein distance for graph structured data](https://mlsanity.com/paper/2203.04711/) (2022)
- [Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited](https://mlsanity.com/paper/2205.10914/) (2022)
- [Hilbert Curve Projection Distance for Distribution Comparison](https://mlsanity.com/paper/2205.15059/) (2022)
- [Better Smatch = Better Parser? AMR evaluation is not so simple anymore](https://mlsanity.com/paper/2210.06461/) (2022)
- [Improving the Expressiveness of K-hop Message-Passing GNNs by Injecting Contextualized Substructure Information](https://mlsanity.com/paper/2406.19244/) (2024)
- [Learning subtree pattern importance for Weisfeiler-Lehmanbased graph kernels](https://mlsanity.com/paper/2106.04739/) (2021)
- [Graph Filtration Kernels](https://mlsanity.com/paper/2110.11862/) (2021)
- [Graphon based Clustering and Testing of Networks: Algorithms and Theory](https://mlsanity.com/paper/2110.02722/) (2021)

## Abstract (arXiv)

Most graph kernels are an instance of the class of R-Convolution kernels, which measure the similarity of objects by comparing their substructures. Despite their empirical success, most graph kernels use a naive aggregation of the final set of substructures, usually a sum or average, thereby potentially discarding valuable information about the distribution of individual components. Furthermore, only a limited instance of these approaches can be extended to continuously attributed graphs. We propose a novel method that relies on the Wasserstein distance between the node feature vector distributions of two graphs, which allows to find subtler differences in data sets by considering graphs as high-dimensional objects, rather than simple means. We further propose a Weisfeiler-Lehman inspired embedding scheme for graphs with continuous node attributes and weighted edges, enhance it with the computed Wasserstein distance, and thus improve the state-of-the-art prediction performance on several graph classification tasks.