A Survey on Graph Kernels

Abstract

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.

References in corpus (12)

• Efficient Estimation of Word Representations in Vector Space
• Semi-Supervised Classification with Graph Convolutional Networks
• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• Convolutional Networks on Graphs for Learning Molecular Fingerprints
• Subgraph Matching Kernels for Attributed Graphs
• On Valid Optimal Assignment Kernels and Applications to Graph Classification
• The Multiscale Laplacian Graph Kernel
• The optimal assignment kernel is not positive definite
• RetGK: Graph Kernels based on Return Probabilities of Random Walks
• A Unifying View of Explicit and Implicit Feature Maps of Graph Kernels
• Deep Weisfeiler-Lehman Assignment Kernels via Multiple Kernel Learning

Cited by in corpus (69)

• A Comprehensive Survey on Deep Graph Representation Learning
• TUDataset: A collection of benchmark datasets for learning with graphs
• Spatio-temporal graph neural networks for multi-site PV power forecasting
• Metrics for Graph Comparison: A Practitioner's Guide
• Adversarial Graph Augmentation to Improve Graph Contrastive Learning
• Graph Kernels: A Survey
• Graph Kernels: State-of-the-Art and Future Challenges
• Generalization and Representational Limits of Graph Neural Networks
• Graph-based Modeling of Online Communities for Fake News Detection
• Quantum Feature Maps for Graph Machine Learning on a Neutral Atom Quantum Processor
• KGNN: Harnessing Kernel-based Networks for Semi-supervised Graph Classification
• Transfer Learning of Graph Neural Networks with Ego-graph Information Maximization
• SUGAR: Subgraph Neural Network with Reinforcement Pooling and Self-Supervised Mutual Information Mechanism
• Convolutional Kernel Networks for Graph-Structured Data
• GraphCrop: Subgraph Cropping for Graph Classification
• Provably Powerful Graph Networks
• Interpretable Neural Architecture Search via Bayesian Optimisation with Weisfeiler-Lehman Kernels
• Understanding Isomorphism Bias in Graph Data Sets
• Network mutual information measures for graph similarity
• Graph Kernel Neural Networks
• Evolutionary Architecture Search for Graph Neural Networks
• Graph Coarsening with Neural Networks
• Modeling Multiple Views via Implicitly Preserving Global Consistency and Local Complementarity
• On Local Distributions in Graph Signal Processing
• Global Attention Improves Graph Networks Generalization
• GNN-LoFI: a Novel Graph Neural Network through Localized Feature-based Histogram Intersection
• Size-Invariant Graph Representations for Graph Classification Extrapolations
• Multiple Kernel Representation Learning on Networks
• Hyperparameter-free and Explainable Whole Graph Embedding
• A contribution to Optimal Transport on incomparable spaces
• LCS Graph Kernel Based on Wasserstein Distance in Longest Common Subsequence Metric Space
• Comparing Temporal Graphs Using Dynamic Time Warping
• Graph Homomorphism Convolution
• A Novel Higher-order Weisfeiler-Lehman Graph Convolution
• Hypergraph Dissimilarity Measures
• Wasserstein Embedding for Graph Learning
• Hybrid localized graph kernel for machine learning energy-related properties of molecules and solids
• Walk Extraction Strategies for Node Embeddings with RDF2Vec in Knowledge Graphs
• HODLR$d$D: A new Black-box fast algorithm for $N$-body problems in $d$-dimensions with guaranteed error bounds
• Whole-Graph Representation Learning For the Classification of Signed Networks
• Parameter Prediction for Unseen Deep Architectures
• Sample efficient graph classification using binary Gaussian boson sampling
• Quantum evolution kernel : Machine learning on graphs with programmable arrays of qubits
• Modeling Edge Features with Deep Bayesian Graph Networks
• Realizable cycle structures in digraphs
• EmbAssi: Embedding Assignment Costs for Similarity Search in Large Graph Databases
• Matérn Gaussian Processes on Graphs
• Quadratic GCN for Graph Classification
• Stochastic encoding of graphs in deep learning allows for complex analysis of gender classification in resting-state and task functional brain networks from the UK Biobank
• Cross-view kernel transfer
• On the Weisfeiler-Leman Dimension of Fractional Packing
• A Stein Goodness of fit Test for Exponential Random Graph Models
• A Gaze into the Internal Logic of Graph Neural Networks, with Logic
• Benchmark of the Full and Reduced Effective Resistance Kernel for Molecular Classification
• Topological Graph Neural Networks
• Provenance Graph Kernel
• A Weighted Quiver Kernel using Functor Homology
• A Structural Feature-Based Approach for Comprehensive Graph Classification
• Pattern-Based Graph Classification: Comparison of Quality Measures and Importance of Preprocessing
• Representing Higher-Order Networks with Spectral Moments
• LSP : Acceleration and Regularization of Graph Neural Networks via Locality Sensitive Pruning of Graphs
• One Node at a Time: Node-Level Network Classification
• REFORM: Fast and Adaptive Solution for Subteam Replacement
• Graph embedding using multi-layer adjacent point merging model
• Density of States Graph Kernels
• The Analysis from Nonlinear Distance Metric to Kernel-based Drug Prescription Prediction System
• Autism Spectrum Disorder Screening Using Discriminative Brain Sub-Networks: An Entropic Approach
• Scaling up graph homomorphism for classification via sampling
• Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size