Random walk kernel
Count matching walks in product graph. Polynomial time. Weakness: 'tottering' — infinite short walks.
Advertisement
Shortest path kernel
Compare shortest-path length distributions. O(V⁴) per pair.
Advertisement
Weisfeiler-Leman kernel
Iterative label refinement + hash. Very effective, O(iterations · (V + E)).
Graph Neural Tangent Kernel
NTK of infinite-width GNN. Interpretable + often outperforms other kernels.