# A Survey on Graph Kernels

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

## Key facts

- Cited by 148 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Mar 2019.

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

- [Adversarial Graph Augmentation to Improve Graph Contrastive Learning](https://mlsanity.com/paper/2106.05819/) (2021)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Parameter Prediction for Unseen Deep Architectures](https://mlsanity.com/paper/2110.13100/) (2021)
- [Topological Graph Neural Networks](https://mlsanity.com/paper/2102.07835/) (2021)
- [Position: Graph Foundation Models are Already Here](https://mlsanity.com/paper/2402.02216/) (2024)
- [Size-Invariant Graph Representations for Graph Classification Extrapolations](https://mlsanity.com/paper/2103.05045/) (2021)
- [SUGAR: Subgraph Neural Network with Reinforcement Pooling and Self-Supervised Mutual Information Mechanism](https://mlsanity.com/paper/2101.08170/) (2021)
- [A Comprehensive Survey on Deep Graph Representation Learning](https://mlsanity.com/paper/2304.05055/) (2023)
- [CktGNN: Circuit Graph Neural Network for Electronic Design Automation](https://mlsanity.com/paper/2308.16406/) (2023)
- [Ordered Subgraph Aggregation Networks](https://mlsanity.com/paper/2206.11168/) (2022)
- [Graph Coarsening with Neural Networks](https://mlsanity.com/paper/2102.01350/) (2021)
- [KerGNNs: Interpretable Graph Neural Networks with Graph Kernels](https://mlsanity.com/paper/2201.00491/) (2022)
- [Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing](https://mlsanity.com/paper/2102.08786/) (2021)
- [Shortest Path Networks for Graph Property Prediction](https://mlsanity.com/paper/2206.01003/) (2022)
- [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)
- [Parallel and Distributed Graph Neural Networks: An In-Depth Concurrency Analysis](https://mlsanity.com/paper/2205.09702/) (2022)
- [GraphHD: Efficient graph classification using hyperdimensional computing](https://mlsanity.com/paper/2205.07826/) (2022)
- [Spatio-temporal graph neural networks for multi-site PV power forecasting](https://mlsanity.com/paper/2107.13875/) (2021)
- [Learning to Predict Graphs with Fused Gromov-Wasserstein Barycenters](https://mlsanity.com/paper/2202.03813/) (2022)
- [Semi-relaxed Gromov-Wasserstein divergence with applications on graphs](https://mlsanity.com/paper/2110.02753/) (2021)
- [Template based Graph Neural Network with Optimal Transport Distances](https://mlsanity.com/paper/2205.15733/) (2022)
- [The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs](https://mlsanity.com/paper/2105.05911/) (2021)
- [KGNN: Harnessing Kernel-based Networks for Semi-supervised Graph Classification](https://mlsanity.com/paper/2205.10550/) (2022)
- [JITServe: SLO-aware LLM Serving with Imprecise Request Information](https://mlsanity.com/paper/2504.20068/) (2025)
- [No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasets](https://mlsanity.com/paper/2502.02379/) (2025)
- [Return of the Latent Space COWBOYS: Re-thinking the use of VAEs for Bayesian Optimisation of Structured Spaces](https://mlsanity.com/paper/2507.03910/) (2025)
- [Graph Kernel Neural Networks](https://mlsanity.com/paper/2112.07436/) (2021)
- [Boosting Graph Structure Learning with Dummy Nodes](https://mlsanity.com/paper/2206.08561/) (2022)

## Abstract (arXiv)

Graph kernels have become an established and widely-used technique for solving classification tasks on graphs. This survey gives a comprehensive overview of techniques for kernel-based graph classification developed in the past 15 years. We describe and categorize graph kernels based on properties inherent to their design, such as the nature of their extracted graph features, their method of computation and their applicability to problems in practice. In an extensive experimental evaluation, we study the classification accuracy of a large suite of graph kernels on established benchmarks as well as new datasets. We compare the performance of popular kernels with several baseline methods and study the effect of applying a Gaussian RBF kernel to the metric induced by a graph kernel. In doing so, we find that simple baselines become competitive after this transformation on some datasets. Moreover, we study the extent to which existing graph kernels agree in their predictions (and prediction errors) and obtain a data-driven categorization of kernels as result. Finally, based on our experimental results, we derive a practitioner's guide to kernel-based graph classification.