# Graph Kernels: State-of-the-Art and Future Challenges

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

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Nov 2020.

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

- [GraphiT: Encoding Graph Structure in Transformers](https://mlsanity.com/paper/2106.05667/) (2021)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Topological Graph Neural Networks](https://mlsanity.com/paper/2102.07835/) (2021)
- [Ordered Subgraph Aggregation Networks](https://mlsanity.com/paper/2206.11168/) (2022)
- [Combining Latent Space and Structured Kernels for Bayesian Optimization over Combinatorial Spaces](https://mlsanity.com/paper/2111.01186/) (2021)
- [Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks](https://mlsanity.com/paper/2210.01906/) (2022)
- [Modular Design Patterns for Hybrid Learning and Reasoning Systems: a taxonomy, patterns and use cases](https://mlsanity.com/paper/2102.11965/) (2021)
- [Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions](https://mlsanity.com/paper/2106.01098/) (2021)
- [SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks](https://mlsanity.com/paper/2203.13913/) (2022)
- [Path Neural Networks: Expressive and Accurate Graph Neural Networks](https://mlsanity.com/paper/2306.05955/) (2023)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)
- [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)
- [SGAT: Simplicial Graph Attention Network](https://mlsanity.com/paper/2207.11761/) (2022)
- [No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasets](https://mlsanity.com/paper/2502.02379/) (2025)
- [Weisfeiler-Leman at the margin: When more expressivity matters](https://mlsanity.com/paper/2402.07568/) (2024)
- [Capturing Graphs with Hypo-Elliptic Diffusions](https://mlsanity.com/paper/2205.14092/) (2022)
- [The GeometricKernels Package: Heat and Mat'ern Kernels for Geometric Learning on Manifolds, Meshes, and Graphs](https://mlsanity.com/paper/2407.08086/) (2024)
- [Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited](https://mlsanity.com/paper/2205.10914/) (2022)
- [Graph Filtration Kernels](https://mlsanity.com/paper/2110.11862/) (2021)
- [Gaussian process regression with Sliced Wasserstein Weisfeiler-Lehman graph kernels](https://mlsanity.com/paper/2402.03838/) (2024)
- [Maximum Mean Discrepancy on Exponential Windows for Online Change Detection](https://mlsanity.com/paper/2205.12706/) (2022)
- [Diss-l-ECT: Dissecting Graph Data with Local Euler Characteristic Transforms](https://mlsanity.com/paper/2410.02622/) (2024)
- [Fast Topological Clustering with Wasserstein Distance](https://mlsanity.com/paper/2112.00101/) (2021)
- [Multiscale Graph Comparison via the Embedded Laplacian Discrepancy](https://mlsanity.com/paper/2201.12064/) (2022)
- [Gradual Weisfeiler-Leman: Slow and Steady Wins the Race](https://mlsanity.com/paper/2209.09048/) (2022)
- [Nystr"om M-Hilbert-Schmidt Independence Criterion](https://mlsanity.com/paper/2302.09930/) (2023)
- [Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernels](https://mlsanity.com/paper/2302.10128/) (2023)
- [Graph Classification Gaussian Processes via Spectral Features](https://mlsanity.com/paper/2306.03770/) (2023)
- [EGC2: Enhanced Graph Classification with Easy Graph Compression](https://mlsanity.com/paper/2107.07737/) (2021)

## Abstract (arXiv)

Graph-structured data are an integral part of many application domains, including chemoinformatics, computational biology, neuroimaging, and social network analysis. Over the last two decades, numerous graph kernels, i.e. kernel functions between graphs, have been proposed to solve the problem of assessing the similarity between graphs, thereby making it possible to perform predictions in both classification and regression settings. This manuscript provides a review of existing graph kernels, their applications, software plus data resources, and an empirical comparison of state-of-the-art graph kernels.