# Graph Kernels: A Survey

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

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Apr 2019.

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

- [Topological Graph Neural Networks](https://mlsanity.com/paper/2102.07835/) (2021)
- [GAUCHE: A Library for Gaussian Processes in Chemistry](https://mlsanity.com/paper/2212.04450/) (2022)
- [Path Neural Networks: Expressive and Accurate Graph Neural Networks](https://mlsanity.com/paper/2306.05955/) (2023)
- [Nested Graph Pseudo-Label Refinement for Noisy Label Domain Adaptation Learning](https://mlsanity.com/paper/2508.00716/) (2025)
- [Graph Anomaly Detection with Unsupervised GNNs](https://mlsanity.com/paper/2210.09535/) (2022)
- [Micro and Macro Level Graph Modeling for Graph Variational Auto-Encoders](https://mlsanity.com/paper/2210.16844/) (2022)
- [Isotropic Gaussian Processes on Finite Spaces of Graphs](https://mlsanity.com/paper/2211.01689/) (2022)
- [Efficient Graph Field Integrators Meet Point Clouds](https://mlsanity.com/paper/2302.00942/) (2023)
- [Gaussian process regression with Sliced Wasserstein Weisfeiler-Lehman graph kernels](https://mlsanity.com/paper/2402.03838/) (2024)
- [Multiscale Graph Comparison via the Embedded Laplacian Discrepancy](https://mlsanity.com/paper/2201.12064/) (2022)
- [Generating Synthetic Mobility Networks with Generative Adversarial Networks](https://mlsanity.com/paper/2202.11028/) (2022)
- [Descriptive Kernel Convolution Network with Improved Random Walk Kernel](https://mlsanity.com/paper/2402.06087/) (2024)
- [Wasserstein Graph Distance Based on L1-Approximated Tree Edit Distance between Weisfeiler-Lehman Subtrees](https://mlsanity.com/paper/2207.04216/) (2022)
- [Graph Classification Gaussian Processes via Spectral Features](https://mlsanity.com/paper/2306.03770/) (2023)
- [Structural Node Embeddings with Homomorphism Counts](https://mlsanity.com/paper/2308.15283/) (2023)
- [Modeling Hierarchical Spaces: A Review and Unified Framework for Surrogate-Based Architecture Design](https://mlsanity.com/paper/2506.22621/) (2025)
- [HGCN(O): A Self-Tuning GCN HyperModel Toolkit for Outcome Prediction in Event-Sequence Data](https://mlsanity.com/paper/2507.22524/) (2025)
- [TREE-G: Decision Trees Contesting Graph Neural Networks](https://mlsanity.com/paper/2207.02760/) (2022)
- [Fast Tree-Field Integrators: From Low Displacement Rank to Topological Transformers](https://mlsanity.com/paper/2406.15881/) (2024)
- [Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs](https://mlsanity.com/paper/2410.10368/) (2024)
- [Global optimization of graph acquisition functions for neural architecture search](https://mlsanity.com/paper/2505.23640/) (2025)
- [Computationally-efficient Graph Modeling with Refined Graph Random Features](https://mlsanity.com/paper/2510.07716/) (2025)
- [Explaining the Power of Topological Data Analysis in Graph Machine Learning](https://mlsanity.com/paper/2401.04250/) (2024)
- [Graph Edits for Counterfactual Explanations: A comparative study](https://mlsanity.com/paper/2401.11609/) (2024)
- [Learning signals defined on graphs with optimal transport and Gaussian process regression](https://mlsanity.com/paper/2410.15721/) (2024)
- [Exploring Consistency in Graph Representations:from Graph Kernels to Graph Neural Networks](https://mlsanity.com/paper/2410.23748/) (2024)
- [Scalable Sobolev IPM for Probability Measures on a Graph](https://mlsanity.com/paper/2502.00737/) (2025)
- [Metric Graph Kernels via the Tropical Torelli Map](https://mlsanity.com/paper/2505.12129/) (2025)
- [Fast, Accurate and Interpretable Graph Classification with Topological Kernels](https://mlsanity.com/paper/2509.17693/) (2025)
- [Generating the Graph Gestalt: Kernel-Regularized Graph Representation Learning](https://mlsanity.com/paper/2106.15239/) (2021)

## Abstract (arXiv)

Graph kernels have attracted a lot of attention during the last decade, and have evolved into a rapidly developing branch of learning on structured data. During the past 20 years, the considerable research activity that occurred in the field resulted in the development of dozens of graph kernels, each focusing on specific structural properties of graphs. Graph kernels have proven successful in a wide range of domains, ranging from social networks to bioinformatics. The goal of this survey is to provide a unifying view of the literature on graph kernels. In particular, we present a comprehensive overview of a wide range of graph kernels. Furthermore, we perform an experimental evaluation of several of those kernels on publicly available datasets, and provide a comparative study. Finally, we discuss key applications of graph kernels, and outline some challenges that remain to be addressed.