A survey on graph kernels

By Nils M. Kriege, Fredrik D. Johansson, Christopher Morris. 2019

491 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

Provably Powerful Graph Networks (2019, background): “As classical approaches often use hand-crafted graph features that are not necessarily suitable to all datasets and/or tasks (e.g., Kriege et al. (2019)), a signiﬁcant research effort in recent years is to develop deep models that are able to learn new graph representations from raw features (e.g.,…”
A Comprehensive Survey on Graph Neural Networks (2019, methodology): “For a further review of graph kernel methods, we refer the readers to [39].”
Graph Representation Learning (2020, background): “We point the interested reader to Kriege et al. [2020] and Vishwanathan et al. [2010] for detailed surveys of this area.”
TUDataset: A collection of benchmark datasets for learning with graphs (2020, background): “Graph kernels have been studied extensively in the past 15 years, see (Kriege et al., 2020) for a thorough overview.”
Machine Learning on Graphs: A Model and Comprehensive Taxonomy (2020, background): “known as graph kernels (GKs), see (Vishwanathan et al., 2010; Kriege et al., 2020) for reviews.”
Towards a practical k-dimensional Weisfeiler-Leman algorithm (2019, methodology): “We apply our algorithm to supervised graph classification [22] and show that our local algorithm is several magnitudes faster than the original algorithms, when performed for the same number of iterations, and prevents overfitting, and hence achieving higher accuracies for the graph classification p”
Evolutionary Architecture Search for Graph Neural Networks (2020, background): “As of today, many GNN structures with diverse learning mechanisms have been proposed for node relationship modeling [8], [9].”
Parameter Prediction for Unseen Deep Architectures (2021, methodology): “Alternative ways to compare graphs include running expensive graph edit distance (GED) algorithms, infeasible for graphs of our size, or designing task-specific graph kernels [78, 112, 77, 106].”
Adversarial Graph Augmentation to Improve Graph Contrastive Learning (2021, background): “Previous works [18,24] show that they generally outperform graph kernels [75–77] and network embedding methods [33,34,78,79].”
Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, methodology): “For a theoretical investigation of graph kernels, see (Kriege et al., 2018), for a thorough survey of graph kernels, see (Kriege et al., 2020).”
Generalization and Representational Limits of Graph Neural Networks (2020, background): “The inability of some graph kernels to distinguish graph properties such as planarity has also been established (Kriege et al., 2018, 2020).”
Mental State Classification Using Multi-Graph Features (2022, background): “Given the collection of graphs { 𝐴 ( 𝑘 ) } 𝑤 = 1 there are numerous kernels that map a graph to a real-valued vector space [19].”