Graph Kernels
Graph Kernels for Structured Data · Also known as: Structured Graph Kernels, Kernel Methods on Graphs, Graf Çekirdekleri, Graph Similarity Kernels
Graph kernels are positive semi-definite kernel functions that measure the similarity between two graphs by comparing their shared substructures — such as random walks, shortest paths, or subtree patterns. Introduced in a unified framework by Vishwanathan, Schraudolph, Kondor, and Borgwardt (2010), they bridge kernel methods and graph-structured data, enabling algorithms like SVMs to operate directly on graphs without requiring an explicit vectorization step.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Graph kernels are appropriate when input data are naturally represented as graphs — molecules, social networks, citation networks, parse trees, protein interaction networks — and a downstream supervised task (classification, regression) must be solved. They assume the graphs are of moderate size (hundreds to a few thousand nodes) and that substructure overlap is a meaningful proxy for task-relevant similarity. For very large graphs or when representation learning is preferred, graph neural networks are a more scalable alternative.
Strengths & limitations
- Theoretically principled: positive semi-definiteness guarantees valid kernel machines with convergence guarantees.
- No explicit feature engineering: structural features are extracted automatically from graph topology and labels.
- Flexible substructure choice: random-walk, Weisfeiler-Lehman, shortest-path, and graphlet variants address different domains.
- Interpretable similarity: the kernel value can be traced back to specific shared substructures, aiding domain experts.
- Quadratic memory and time in the number of training graphs for Gram matrix construction.
- Fixed substructure type may miss task-relevant patterns not captured by the chosen kernel variant.
- Cannot straightforwardly handle dynamic or heterogeneous graphs without custom extensions.
- Expressiveness is bounded by the Weisfeiler-Lehman hierarchy; certain non-isomorphic graphs may receive identical kernel values.
Frequently asked
What is the difference between a graph kernel and a graph neural network?
A graph kernel computes a fixed similarity measure between graph pairs using handcrafted substructures; it does not learn representations from data. A graph neural network learns node and graph embeddings end-to-end via gradient descent, adapting representations to the task. Graph kernels are more interpretable and data-efficient for small datasets, while GNNs scale better and can capture richer patterns.
Do graph kernels require node or edge labels?
No, but they can exploit them when available. Label-aware variants (e.g., labeled random walks, Weisfeiler-Lehman) incorporate node and edge attributes into substructure counting, substantially improving discrimination. Unlabeled variants rely solely on topological structure. Ignoring available labels usually degrades predictive performance in labeled datasets.
How do I choose among random-walk, shortest-path, and Weisfeiler-Lehman kernels?
The Weisfeiler-Lehman subtree kernel is generally the default choice: it is linear in the number of edges and achieves strong empirical performance across benchmarks. Shortest-path kernels are informative when global path structure matters. Random-walk kernels are theoretically elegant but computationally expensive due to their reliance on matrix inversion or Sylvester equation solving.
Sources
- Vishwanathan, S. V. N., Schraudolph, N. N., Kondor, R., & Borgwardt, K. M. (2010). Graph kernels. Journal of Machine Learning Research, 11, 1201–1242. link ↗
How to cite this page
ScholarGate. (2026, June 2). Graph Kernels for Structured Data. ScholarGate. https://scholargate.app/en/network-analysis/graph-kernels
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Graph Neural Network (Network Analysis)Network analysis↔ compare
- Knowledge Graph EmbeddingsNetwork analysis↔ compare