mlsanityData to 13 Oct 2026

A Survey on Graph Kernels

arXiv 1903.11835 ↗First posted 28 Mar 2019cs.LG stat.MLcited by 148

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2021: 27; 2022: 32; 2023: 22; 2024: 25; 2025: 33; 2026: 9.

148 papers.

Sort:

By area:

  1. 2021Adversarial Graph Augmentation to Improve Graph Contrastive Learningcited by 200
  2. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  3. 2021Parameter Prediction for Unseen Deep Architecturescited by 89
  4. 2021Topological Graph Neural Networkscited by 86
  5. 2024Position: Graph Foundation Models are Already Herecited by 84
  6. 2021Size-Invariant Graph Representations for Graph Classification Extrapolationscited by 83
  7. 2021SUGAR: Subgraph Neural Network with Reinforcement Pooling and Self-Supervised Mutual Information Mechanismcited by 75
  8. 2023A Comprehensive Survey on Deep Graph Representation Learningcited by 72
  9. 2022Ordered Subgraph Aggregation Networkscited by 57
  10. 2023CktGNN: Circuit Graph Neural Network for Electronic Design Automationcited by 57
  11. 2021Graph Coarsening with Neural Networkscited by 55
  12. 2022KerGNNs: Interpretable Graph Neural Networks with Graph Kernelscited by 50
38 more
  1. 2021Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passingcited by 47
  2. 2022Shortest Path Networks for Graph Property Predictioncited by 46
  3. 2022SpeqNets: Sparsity-aware Permutation-equivariant Graph Networkscited by 37
  4. 2023Path Neural Networks: Expressive and Accurate Graph Neural Networkscited by 32
  5. 2023WL meet VCcited by 30
  6. 2022Parallel and Distributed Graph Neural Networks: An In-Depth Concurrency Analysiscited by 29
  7. 2022GraphHD: Efficient graph classification using hyperdimensional computingcited by 28
  8. 2021Spatio-temporal graph neural networks for multi-site PV power forecastingcited by 22
  9. 2022Learning to Predict Graphs with Fused Gromov-Wasserstein Barycenterscited by 22
  10. 2021Semi-relaxed Gromov-Wasserstein divergence with applications on graphscited by 21
  11. 2022Template based Graph Neural Network with Optimal Transport Distancescited by 20
  12. 2021The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphscited by 19
  13. 2022KGNN: Harnessing Kernel-based Networks for Semi-supervised Graph Classificationcited by 18
  14. 2025JITServe: SLO-aware LLM Serving with Imprecise Request Informationcited by 17
  15. 2025No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasetscited by 16
  16. 2021Graph Kernel Neural Networkscited by 13
  17. 2022Boosting Graph Structure Learning with Dummy Nodescited by 13
  18. 2022ToDD: Topological Compound Fingerprinting in Computer-Aided Drug Discoverycited by 13
  19. 2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
  20. 2025Return of the Latent Space COWBOYS: Re-thinking the use of VAEs for Bayesian Optimisation of Structured Spacescited by 13
  21. 2023Deep Orthogonal Hypersphere Compression for Anomaly Detectioncited by 12
  22. 2023A Survey of Graph Unlearningcited by 12
  23. 2022Taxonomy of Benchmarks in Graph Representation Learningcited by 11
  24. 2023Enhancing User Intent Capture in Session-Based Recommendation with Attribute Patternscited by 11
  25. 2024Non-convolutional Graph Neural Networkscited by 11
  26. 2023Expectation-Complete Graph Representations with Homomorphismscited by 10
  27. 2024The GeometricKernels Package: Heat and Mat'ern Kernels for Geometric Learning on Manifolds, Meshes, and Graphscited by 10
  28. 2021A Generalized Weisfeiler-Lehman Graph Kernelcited by 9
  29. 2021Graph Filtration Kernelscited by 8
  30. 2021D-HYPR: Harnessing Neighborhood Modeling and Asymmetry Preservation for Digraph Representation Learningcited by 8
  31. 2022Weisfeiler and Leman Go Walking: Random Walk Kernels Revisitedcited by 8
  32. 2022Mental State Classification Using Multi-graph Featurescited by 7
  33. 2022Isotropic Gaussian Processes on Finite Spaces of Graphscited by 7
  34. 2023Biological Sequence Kernels with Guaranteed Flexibilitycited by 7
  35. 2023Strengthening structural baselines for graph classification using Local Topological Profilecited by 7
  36. 2024Gaussian process regression with Sliced Wasserstein Weisfeiler-Lehman graph kernelscited by 7
  37. 2024Molecular Topological Profile (MOLTOP) -- Simple and Strong Baseline for Molecular Graph Classificationcited by 7
  38. 2022Bootstrapping Informative Graph Augmentation via A Meta Learning Approachcited by 6

50 most cited of 148 All 148 (JSON)