Weisfeiler-Lehman Graph Kernels

Nino ShervashidzePascal SchweitzerErik Jan van LeeuwenKurt MehlhornKarsten M. Borgwardt

article2011JMLR2,456 citations

Introduces a fast graph kernel framework based on the Weisfeiler-Lehman graph isomorphism test that achieves linear runtime scaling in the number of edges while improving classification accuracy on large structured datasets.

Listen

Graph-structured data has become vital across fields like chemoinformatics, bioinformatics, and social network analysis, where tasks such as predicting the function or toxicity of molecules depend on measuring structural similarity. However, existing graph comparison methods suffer from severe computational bottlenecks. Exact matching is intractable, while traditional graph kernels—similarity functions that enable standard machine learning algorithms to process network data—scale poorly, typically requiring at least cubic runtime complexity relative to the number of nodes. This limitation has historically made it impractical to apply graph machine learning to large datasets containing graphs with hundreds or thousands of nodes.

The article develops and evaluates a family of efficient graph kernels tailored for large graphs with discrete node labels. Specifically, the authors set out to demonstrate that adapting the classic Weisfeiler-Lehman graph isomorphism test allows rapid feature extraction, yielding similarity measures that scale linearly with graph size while matching or exceeding the prediction accuracy of state-of-the-art methods.

To accomplish this, the authors designed a framework that iteratively augments node labels with the sorted labels of their neighboring nodes and compresses them into new, concise representations. By tracking these compressed labels across iterations, the method captures increasingly large neighborhood patterns (subtree patterns). The framework can also incorporate other base kernels, such as edge or shortest path comparisons. The authors tested these techniques through runtime simulations on synthetic graphs and benchmarked classification performance using support vector machines across five standard real-world datasets spanning chemoinformatics and protein structures (MUTAG, NCI1, NCI109, ENZYMES, and D&D), comparing them against leading walk-based, path-based, subgraph-based, and existing subtree kernels.

The findings show substantial improvements in both computational efficiency and classification accuracy. First, the Weisfeiler-Lehman subtree kernel achieved exceptional scalability, completing computations on the large D&D protein dataset in just 11 minutes, whereas competing methods required days or weeks, and some ran for over a month. Second, the Weisfeiler-Lehman framework achieved the highest classification accuracy on four of the five real-world benchmark datasets, improving predictive accuracy by over 8 percentage points on anti-cancer screening datasets (NCI1 and NCI109) compared to non-Weisfeiler-Lehman methods. Third, the Weisfeiler-Lehman shortest path and edge variations systematically enhanced classification performance over their base kernels on several benchmarks, although they incurred higher computational costs on very large graphs.

These results establish that organizations no longer need to sacrifice computational speed for predictive accuracy when analyzing graph-structured data. By reducing computation from polynomial to linear runtime per iteration, the method drastically lowers the computational cost and time required to process massive graph databases. This breakthrough makes high-throughput screening of chemical compounds and whole-protein structural analysis technically and economically viable on standard computing hardware.

Organizations handling network-structured data should adopt the global Weisfeiler-Lehman subtree kernel as a primary baseline for large-scale classification tasks due to its optimal balance of linear runtime and superior predictive accuracy. When analyzing smaller datasets where maximizing accuracy is the paramount goal and computing time is less constrained, practitioners should evaluate the Weisfeiler-Lehman shortest path or edge variants, which achieved top performance on complex benchmarks like the ENZYMES dataset.

The primary limitation of the proposed approach is that it is strictly designed for discrete or unlabeled nodes and edges; it does not natively support continuous or high-dimensional attributes. Additionally, while the subtree variant scales linearly, the edge and shortest path variants become computationally expensive on graphs with extensive label sets or large node counts. Further research is recommended to extend the Weisfeiler-Lehman kernel framework to accommodate continuous node features without losing linear scalability.

Machine Learning & Computational Biology Research Group Max Planck Institute for Informatics Max Planck Institutes Tübingen University of Bergen bipartite graphs classification computational biology Weisfeiler-Lehman graph kernels Weisfeiler-Lehman algorithm graphlet kernels

BorgwardtLab/graph-kernels Shervashidze et al (2011).pdf

Paper: Training linear SVMs in linear time, Thorsten Joachims (2006). Understanding linear-time support vector machine optimization provides essential context for the downstream SVM classification benchmarks used to evaluate the Weisfeiler-Lehman graph kernels.
Paper: Pegasos: primal estimated sub-gradient solver for SVM, Shai Shalev-Shwartz et al. (2007). Reading Pegasos clarifies scalable primal optimization for kernel-based and linear classifiers applied to the extracted graph feature vectors.
Paper: Random Features for Large-Scale Kernel Machines, Ali Rahimi et al. (2007). This paper establishes fundamental concepts for constructing explicit, scalable feature representations to bypass quadratic and cubic kernel matrix bottlenecks.

Paper: How Powerful are Graph Neural Networks?, Keyulu Xu et al. (2019). This foundational work builds directly on the Weisfeiler-Lehman graph isomorphism test to prove the theoretical upper bound on the representational power of message-passing graph neural networks.
Paper: Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks, Christopher Morris et al. (2019). This paper generalizes the Weisfeiler-Lehman framework by introducing higher-order graph neural networks that mirror multi-dimensional k-WL algorithms.
Paper: Learning Convolutional Neural Networks for Graphs, Mathias Niepert et al. (2016). PATCHY-SAN explicitly utilizes the Weisfeiler-Lehman algorithm to canonicalize and order local graph neighborhoods into receptive fields for convolutional architectures.
Paper: Convolutional Networks on Graphs for Learning Molecular Fingerprints, David Duvenaud et al. (2015). This work replaces classical discrete circular fingerprinting and graph kernels with end-to-end differentiable neural fingerprints on molecular graphs.
Paper: Hierarchical graph representation learning with differentiable pooling, Rex Ying et al. (2018). DiffPool advances graph classification beyond flat Weisfeiler-Lehman neighborhood aggregations by learning hierarchical, differentiable graph coarsening.
Paper: Representation Learning on Graphs: Methods and Applications, William L. Hamilton et al. (2017). This comprehensive review contrasts traditional heuristic- and kernel-based graph representations with modern representation learning paradigms.
Paper: Link Prediction Based on Graph Neural Networks, Muhan Zhang et al. (2018). SEAL adapts localized neighborhood representations into graph neural network architectures for link prediction, directly evaluating against Weisfeiler-Lehman graph kernel baselines.
Paper: MoleculeNet: a benchmark for molecular machine learning, Zhenqin Wu et al. (2017). MoleculeNet provides standardized benchmarks across chemical property datasets, evaluating modern learnable representations against classic graph kernel approaches.

Cover for Weisfeiler-Lehman Graph Kernels

Abstract

In this article, we propose a family of efficient kernels for large graphs with discrete node labels. Key to our method is a rapid feature extraction scheme based on the Weisfeiler-Lehman test of isomorphism on graphs. It maps the original graph to a sequence of graphs, whose node attributes capture topological and label information. A family of kernels can be defined based on this Weisfeiler-Lehman sequence of graphs, including a highly efficient kernel comparing subtree-like patterns. Its runtime scales only linearly in the number of edges of the graphs and the length of the Weisfeiler-Lehman graph sequence. In our experimental evaluation, our kernels outperform state-of-the-art graph kernels on several graph classification benchmark data sets in terms of accuracy and runtime. Our kernels open the door to large-scale applications of graph kernels in various disciplines such as computational biology and social network analysis.

Topics

bipartite graphs classification computational biology feature extraction network analysis social network analysis directed graphs weighted graph

Keywords

Weisfeiler-Lehman graph kernels Weisfeiler-Lehman algorithm graphlet kernels shortest path kernels subtree kernels random walk kernels optimal assignment kernels graph isomorphism graph similarity measures graph-structured data

1. Introduction
1.1 Review of Graph Kernels
2. The Weisfeiler-Lehman Test of Isomorphism
2.1 Complexity
2.2 Link with Subtree Patterns
3. The General Weisfeiler-Lehman Kernels
3.1 The Weisfeiler-Lehman Kernel Framework
3.1.1 NOTE ON COMPUTING WEISFEILER-LEHMAN KERNELS IN PRACTICE
3.2 The Weisfeiler-Lehman Subtree Kernel
3.2.1 COMPUTING THE WEISFEILER-LEHMAN SUBTREE KERNEL ON MANY GRAPHS
3.2.2 THE RAMON-G¨ ARTNER SUBTREE KERNEL
3.2.3 LINK TO THE WEISFEILER-LEHMAN SUBTREE KERNEL
3.3 The Weisfeiler-Lehman Edge Kernel
3.3.1 NOTE ON COMPUTATIONAL COMPLEXITY
3.4 The Weisfeiler-Lehman Shortest Path Kernel
3.4.1 NOTE ON COMPUTATIONAL COMPLEXITY
3.5 Other Weisfeiler-Lehman Kernels
4. Experiments
4.1 Runtime Behaviour of Weisfeiler-Lehman Subtree Kernel
4.1.1 METHODS
4.1.2 EXPERIMENTAL SETUP
4.1.3 RESULTS
4.2 Graph Classification
4.2.1 DATA SETS
4.2.2 EXPERIMENTAL SETUP
4.2.3 RESULTS
5. Conclusions
Acknowledgments
References

Knowls

Knowl 1 — General Weisfeiler-Lehman Graph Kernel Framework
model/method
Let $G = (V, E, ℓ)$ be an undirected graph with vertex set $V$ , edge set $E$ , and node labeling function $ℓ: V \to \Sigma$ , where $\Sigma$ is a discrete label alphabet. Let $r((V, E, l_i)) = (V, E, l_{i+1})$ denote one step of 1-dimensional Weisfeiler-Lehman node relabeling, where the new label $l_{i+1}(v)$ of each vertex $v \in V$ is obtained by sorting and compressing the multiset of labels of its neighbors $\mathcal{N}(v) = \{ u \in V \mid (v, u) \in E \}$ augmented with $l_i(v)$ .

The Weisfeiler-Lehman sequence of graphs up to height $h$ for $G$ is defined as: $\{G_0, G_1, \dots, G_h\} = \{(V, E, l_0), (V, E, l_1), \dots, (V, E, l_h)\}$ where $G_0 = G$ and $l_0 = \u2113$ .

Given any base graph kernel $k(G, G')$ and non-negative real weights $\alpha_0, \alpha_1, \dots, \alpha_h \ge 0$ , the general Weisfeiler-Lehman graph kernel with $h$ iterations is defined as: $k_{\text{WL}}^{(h)}(G, G') = \sum_{i=0}^h \alpha_i k(G_i, G'_i)$ where $\{G_0, \dots, G_h\}$ and $\{G'_0, \dots, G'_h\}$ are the Weisfeiler-Lehman sequences of $G$ and $G'$ up to height $h$ , respectively (standard weighting sets all $\alpha_i = 1$ ).

If the base kernel $k$ is positive semidefinite on graphs, the resulting Weisfeiler-Lehman kernel $k_{\text{WL}}^{(h)}$ is guaranteed to be positive semidefinite, because each component $k(G_i, G'_i) = k(r^i(G), r^i(G')) = \langle \phi(r^i(G)), \phi(r^i(G')) \rangle = \langle \psi(G), \psi(G') \rangle$ defines a valid positive semidefinite kernel on $(G, G')$ , and non-negative linear combinations of positive semidefinite kernels are positive semidefinite.
Knowl 2 — Weisfeiler-Lehman Subtree Kernel
model/method
The Weisfeiler-Lehman subtree kernel is an instance of the Weisfeiler-Lehman kernel framework where the base kernel counts pairs of identical node labels between two graphs $G = (V, E, \u2113)$ and $G' = (V', E', \u2113)$ : $k(G, G') = \sum_{v \in V} \sum_{v' \in V'} \delta(\u2113(v), \u2113(v'))$ where $\delta(a, b) = 1$ if $a = b$ and $0$ otherwise.

Let $\Sigma_i$ denote the set of all unique compressed labels that occur at iteration $i$ across graphs, with $\Sigma_0$ being the original label alphabet and all $\Sigma_i$ treated as disjoint. Let $c_i(G, \sigma)$ denote the number of occurrences of label $\sigma \in \Sigma_i$ in $G$ . The explicit feature vector of graph $G$ after $h$ iterations is given by the concatenation of label counts across all refinement levels $0, 1, \dots, h$ : $\phi_{\text{WLsubtree}}^{(h)}(G) = \left( c_0(G, \sigma_{01}), \dots, c_0(G, \sigma_{0|\Sigma_0|}), \dots, c_h(G, \sigma_{h1}), \dots, c_h(G, \sigma_{h|\Sigma_h|}) \right)$

The Weisfeiler-Lehman subtree kernel between graphs $G$ and $G'$ is the inner product of their feature vectors: $k_{\text{WLsubtree}}^{(h)}(G, G') = \langle \phi_{\text{WLsubtree}}^{(h)}(G), \phi_{\text{WLsubtree}}^{(h)}(G') \rangle = \sum_{i=0}^h \sum_{j=1}^{|\Sigma_i|} c_i(G, \sigma_{ij}) c_i(G', \sigma_{ij})$

This kernel exactly equals $k_{\text{WL}}^{(h)}(G, G') = \sum_{i=0}^h k(G_i, G'_i)$ instantiated with the Dirac node-matching base kernel. For a single pair of graphs with $m$ edges, the kernel can be evaluated in $O(hm)$ time.
Knowl 3 — Global Algorithm for Computing the Weisfeiler-Lehman Subtree Kernel on Multiple Graphs
algorithm
The global computation scheme computes the Weisfeiler-Lehman subtree kernel simultaneously across a dataset of $N$ graphs $\mathcal{G} = \{G_1, \dots, G_N\}$ , each having at most $n$ nodes and $m$ edges ( $m > n$ ), for a subtree height parameter $h$ .
Input: Set of $N$ labeled graphs $\mathcal{G} = \{G_1, \dots, G_N\}$ with label alphabet $\Sigma_0$ , number of iterations $h$
Output: Kernel matrix $K \in \mathbb{R}^{N \times N}$
Initialize feature vector $\phi(G) \leftarrow []$ for all $G \in \mathcal{G}$
for each graph $G \in \mathcal{G}$ do
    Count occurrences $c_0(G, \sigma)$ of each label $\sigma \in \Sigma_0$ in $G$
    Append counts $(c_0(G, \sigma_{01}), \dots, c_0(G, \sigma_{0|\Sigma_0|}))$ to $\phi(G)$
end for
for iteration $i = 1$ to $h$ do
    for each graph $G = (V, E) \in \mathcal{G}$ do
        for each node $v \in V$ do
            Assign multiset-label $M_i(v) \leftarrow \{ l_{i-1}(u) \mid u \in \mathcal{N}(v) \}$
            Sort elements of $M_i(v)$ in ascending order
            Prepend $l_{i-1}(v)$ to form string $s_i(v) \leftarrow (l_{i-1}(v), M_i(v))$
        end for
    end for
    Sort and map all strings $\{ s_i(v) \}_{v \in \bigcup V(G)}$ across all $N$ graphs to compressed integer labels $\Sigma_i$ using bucket sort or a hash function $f: \Sigma^* \to \Sigma$
    for each graph $G = (V, E) \in \mathcal{G}$ do
        for each node $v \in V$ do
             $l_i(v) \leftarrow f(s_i(v))$
        end for
        Count occurrences $c_i(G, \sigma)$ of each compressed label $\sigma \in \Sigma_i$ in $G$
        Append counts $(c_i(G, \sigma_{i1}), \dots, c_i(G, \sigma_{i|\Sigma_i|}))$ to $\phi(G)$
    end for
end for
Compute $K_{jk} \leftarrow \langle \phi(G_j), \phi(G_k) \rangle$ for all $1 \le j, k \le N$
return $K$
The total time complexity is $O(Nhm + N^2hn)$ . Feature extraction over all $N$ graphs requires $O(Nhm)$ time because multiset construction, bucket sorting, and compression take $O(Nm)$ per iteration. Since each graph has at most $hn$ non-zero entries in its feature vector, computing all $N^2$ inner products takes $O(N^2hn)$ time.
Knowl 4 — Recursive Formulation and Equivalence of the Weisfeiler-Lehman Subtree Kernel
theoretical result
The Weisfeiler-Lehman subtree kernel $k_{\text{WLsubtree}}^{(h)}(G, G')$ between two graphs $G = (V, E, \u2113)$ and $G' = (V', E', \u2113)$ is identically equal to the recursive kernel $k_{\text{rec}}^{(h)}(G, G')$ defined by: $k_{\text{rec}}^{(h)}(G, G') = \sum_{i=0}^h \sum_{v \in V} \sum_{v' \in V'} k_{\text{rec}, i}(v, v')$ where the base comparison at height $0$ is: $k_{\text{rec}, 0}(v, v') = \delta(\u2113(v), \u2113(v'))$ and for iterations $i > 0$ : $k_{\text{rec}, i}(v, v') = \begin{cases} k_{\text{rec}, i-1}(v, v') \max_{R \in \mathcal{M}(v, v')} \prod_{(w, w') \in R} k_{\text{rec}, i-1}(w, w') & \text{if } \mathcal{M}(v, v') \neq \emptyset \\ 0 & \text{if } \mathcal{M}(v, v') = \emptyset \end{cases}$ where $\delta$ is the Dirac indicator function (evaluating to $1$ when arguments are equal and $0$ otherwise), and $\mathcal{M}(v, v')$ is the set of exact full matchings between the neighborhoods of $v$ and $v'$ : $\mathcal{M}(v, v') = \left\{ R \subseteq \mathcal{N}(v) \times \mathcal{N}(v') \;\middle|\; |R| = |\mathcal{N}(v)| = |\mathcal{N}(v')| \wedge (\forall (u, u'), (w, w') \in R: u = w \iff u' = w') \wedge (\forall (u, u') \in R: \u2113(u) = \u2113(u')) \right\}$

Under this formulation, $k_{\text{rec}, i}(v, v')$ evaluates to $1$ if and only if the subtree patterns of height $i$ rooted at $v$ and $v'$ are isomorphic, and $0$ otherwise. This establishes that the Weisfeiler-Lehman subtree kernel tests for exact matching of full neighborhoods across all heights $0, \dots, h$ , in contrast to the Ramon-Gärtner subtree kernel which computes all subset matchings in neighborhoods (with worst-case cost exponential in the maximum node degree $d$ , scaling as $O(N^2 n^2 h 4^d)$ ).
Knowl 5 — 1-Dimensional Weisfeiler-Lehman Graph Relabeling Procedure
algorithm
The 1-dimensional Weisfeiler-Lehman graph relabeling algorithm (also known as naive vertex refinement) iteratively refines discrete node labels on a graph $G = (V, E, \u2113)$ or across a pair of graphs $G, G'$ . For unlabeled graphs, initial node labels $l_0(v)$ are initialized to node degrees $|\mathcal{N}(v)|$ .
Input: Graphs $G = (V, E, \u2113)$ and $G' = (V', E', \u2113)$ , iteration index $i \ge 1$ , prior labeling functions $l_{i-1}$
Output: Updated labelings $l_i$ for all vertices in $V \cup V'$
1. Multiset-label determination:
   for each node $v \in V \cup V'$ do
        $M_i(v) \leftarrow \{ l_{i-1}(u) \mid u \in \mathcal{N}(v) \}$
   end for
2. Multiset sorting and concatenation:
   for each node $v \in V \cup V'$ do
       Sort elements of $M_i(v)$ in ascending order into a sequence $(u_1, u_2, \dots)$
       Prepend prior label to construct string $s_i(v) \leftarrow (l_{i-1}(v), u_1, u_2, \dots)$
   end for
3. Label compression:
   Sort all strings $s_i(v)$ across all $v \in V \cup V'$ in ascending order
   Define injective map $f: \Sigma^* \to \Sigma$ assigning unique identifiers to distinct strings
4. Relabeling:
   for each node $v \in V \cup V'$ do
        $l_i(v) \leftarrow f(s_i(v))$
   end for
return $l_i$
For two graphs with $m$ total edges, step 1 takes $O(m)$ time. Step 2 sorts all multisets in $O(m)$ time total via counting (bucket) sort because labels at iteration $i-1$ range over at most $2n$ distinct values. Step 3 sorts the resulting strings in $O(m)$ time via radix sort. Compression and relabeling take $O(m)$ . Hence, one iteration requires $O(m)$ time, and $h$ iterations require $O(hm)$ total time.
Knowl 6 — Weisfeiler-Lehman Edge Kernel
model/method
The Weisfeiler-Lehman edge kernel is an instance of the Weisfeiler-Lehman kernel framework where the base kernel $k_E(G, G')$ compares edges with identically labeled endpoints between two graphs $G = (V, E, \u2113)$ and $G' = (V', E', \u2113)$ : $k_E(G, G') = \langle \phi_E(G), \phi_E(G') \rangle = \sum_{e=(u, v) \in E} \sum_{e'=(u', v') \in E'} \delta(a, a') \delta(b, b')$ where $(a, b)$ with $a \le b$ represents the ordered pair of endpoint labels $(\u2113(u), \u2113(v))$ for edge $e$ , $(a', b')$ represents ordered endpoint labels $(\u2113(u'), \u2113(v'))$ for edge $e'$ , and $\delta$ is the Dirac kernel. If edges have real-valued weights assigned by $w: E \to \mathbb{R}$ , the term is multiplied by an edge weight kernel $k_w(w(e), w(e'))$ .

The Weisfeiler-Lehman edge kernel with $h$ iterations is defined as: $k_{\text{WLedge}}^{(h)}(G, G') = \sum_{i=0}^h k_E(G_i, G'_i)$ where $G_i = (V, E, l_i)$ is the $i$ -th Weisfeiler-Lehman graph.

In each iteration $i$ , the number of possible unweighted edge features is $|\Sigma_i|(|\Sigma_i|+1)/2$ . Because $|\Sigma_i| \le |\Sigma_{i+1}|$ , computing explicit feature vectors becomes increasingly expensive as $i$ increases. When explicit feature representation is prohibitive or general edge-weight kernels are used, pairwise comparison between edges across all pairs of $N$ graphs takes $O(N^2 m^2)$ operations per iteration.
Knowl 7 — Weisfeiler-Lehman Shortest Path Kernel
model/method
The Weisfeiler-Lehman shortest path kernel is an instance of the Weisfeiler-Lehman kernel framework using a node-labeled shortest path kernel as the base kernel. For unweighted graphs, the base kernel $k_{\text{SP}}(G, G')$ counts matching triplets of the form $(a, b, p)$ : $k_{\text{SP}}(G, G') = \langle \phi_{\text{SP}}(G), \phi_{\text{SP}}(G') \rangle$ where $\phi_{\text{SP}}(G)$ is a vector recording occurrences of triplets $(a, b, p)$ such that $a, b \in \Sigma$ are ordered endpoint labels ( $a \le b$ ) of a shortest path in $G$ and $p \in \mathbb{N}_0$ is the geodesic shortest path length.

The Weisfeiler-Lehman shortest path kernel with $h$ iterations is defined as: $k_{\text{WL shortest path}}^{(h)}(G, G') = \sum_{i=0}^h k_{\text{SP}}(G_i, G'_i)$ where $G_i = (V, E, l_i)$ is the $i$ -th Weisfeiler-Lehman graph.

All-pairs shortest path lengths for all $N$ graphs can be precomputed once in $O(Nn^3)$ using the Floyd-Warshall algorithm because graph topology is invariant across the Weisfeiler-Lehman sequence. When using the Dirac kernel on integer shortest path lengths, the feature space dimension at iteration $i$ is bounded by $\frac{|\Sigma_i|(|\Sigma_i|+1)}{2} P$ , where $P$ is the number of distinct shortest path lengths. If explicit feature mapping is infeasible, pairwise comparison of all $O(n^2)$ shortest path pairs scales as $O(n^4)$ per graph pair and $O(N^2 n^4)$ across the dataset per iteration.

Knowl 8 — Graph Classification Accuracy of Weisfeiler-Lehman Kernels on Benchmark Datasets

data/table

The classification accuracy of the Weisfeiler-Lehman (WL) subtree, WL edge, and WL shortest path kernels was evaluated using 10-fold cross-validation repeated 10 times with a C-Support Vector Machine (LIBSVM) against baseline graph kernels: Ramon-Gärtner subtree (with parameter $\lambda = 1$ ), $p$ -random walk, geometric random walk, connected 3-node graphlet count, and node-labeled shortest path. Hyperparameters ( $h \in \{0, \dots, 10\}$ for WL subtree, $h \in \{0, 1, 2, 3\}$ for WL edge, $h \in \{0, 1, 2\}$ for WL shortest path and Ramon-Gärtner, $p \in \{1, \dots, 10\}$ for $p$ -random walk, and SVM parameter $C$ ) were selected strictly on training folds.

Method / Data Set	MUTAG	NCI1	NCI109	ENZYMES	DD
WL subtree	82.05 ( $\pm$ 0.36)	82.19 ( $\pm$ 0.18)	82.46 ( $\pm$ 0.24)	52.22 ( $\pm$ 1.26)	79.78 ( $\pm$ 0.36)
WL edge	81.06 ( $\pm$ 1.95)	84.37 ( $\pm$ 0.30)	84.49 ( $\pm$ 0.20)	53.17 ( $\pm$ 2.04)	77.95 ( $\pm$ 0.70)
WL shortest path	83.78 ( $\pm$ 1.46)	84.55 ( $\pm$ 0.36)	83.53 ( $\pm$ 0.30)	59.05 ( $\pm$ 1.05)	79.43 ( $\pm$ 0.55)
Ramon Gärtner	85.72 ( $\pm$ 0.49)	61.86 ( $\pm$ 0.27)	61.67 ( $\pm$ 0.21)	13.35 ( $\pm$ 0.87)	57.27 ( $\pm$ 0.07)
$p$ -random walk	79.19 ( $\pm$ 1.09)	58.66 ( $\pm$ 0.28)	58.36 ( $\pm$ 0.94)	27.67 ( $\pm$ 0.95)	66.64 ( $\pm$ 0.83)
Random walk	80.72 ( $\pm$ 0.38)	64.34 ( $\pm$ 0.27)	63.51 ( $\pm$ 0.18)	21.68 ( $\pm$ 0.94)	71.70 ( $\pm$ 0.47)
Graphlet count	75.61 ( $\pm$ 0.49)	66.00 ( $\pm$ 0.07)	66.59 ( $\pm$ 0.08)	32.70 ( $\pm$ 1.20)	78.59 ( $\pm$ 0.12)
Shortest path	87.28 ( $\pm$ 0.55)	73.47 ( $\pm$ 0.11)	73.07 ( $\pm$ 0.11)	41.68 ( $\pm$ 1.79)	78.45 ( $\pm$ 0.26)

On NCI1, NCI109, ENZYMES, and D&D, kernels from the Weisfeiler-Lehman framework achieve the highest prediction accuracy. On NCI1 and NCI109, the WL subtree kernel outperforms all non-WL methods by more than 8 percentage points. On ENZYMES, WL shortest path improves over the base shortest path kernel from 41.68% to 59.05%. Cross-validation systematically selected $h > 0$ (typically $h = 2$ or $3$ ) for WL edge and WL shortest path, demonstrating that multi-resolution node refinement consistently improves classification performance over the base graph kernels ( $h = 0$ ).

Knowl 9 — Computation Runtimes of Weisfeiler-Lehman and Baseline Graph Kernels on Benchmark Datasets

data/table

Kernel matrix computation times were measured across five graph classification benchmark datasets (MUTAG: 188 graphs, max 28 nodes; NCI1: 4110 graphs, max 111 nodes; NCI109: 4127 graphs, max 111 nodes; ENZYMES: 600 graphs, max 126 nodes; D&D: 1178 graphs, max 5748 nodes, average 284.32 nodes, 82 labels). Reported times represent the cumulative CPU computation time over all parameter values evaluated during cross-validation ( $h \in \{0, \dots, 10\}$ for WL subtree, $h \in \{0, 1, 2, 3\}$ for WL edge, $h \in \{0, 1, 2\}$ for WL shortest path and Ramon-Gärtner, $p \in \{1, \dots, 10\}$ for $p$ -random walk).

Data Set	MUTAG	NCI1	NCI109	ENZYMES	DD
Max # nodes	28	111	111	126	5748
Average # nodes	17.93	29.87	29.68	32.63	284.32
# labels	7	37	38	3	82
Number of graphs	188	4110	4127	600	1178
WL subtree	6”	7'20”	7'21”	20”	11'0”
WL edge	3”	1'5”	58”	11”	3 days
WL shortest path	2”	2'20”	2'23”	1'3”	484 days
Ramon Gärtner	40'6”	81 days	81 days	38 days	103 days
$p$ -random walk	4'42”	5 days	5 days	10'	4 days
Random walk	12”	9 days	9 days	12'19”	48 days
Graphlet count	3”	1'27”	1'27”	25”	30'21”
Shortest path	2”	4'38”	4'39”	5”	23h 17'2”

The global WL subtree kernel is fast and scalable across all datasets, computing 11 kernel matrices on the large D&D protein dataset in 11 minutes. In contrast, on D&D, shortest path takes over 23 hours, WL edge takes 3 days, random walk takes 48 days, Ramon-Gärtner takes 103 days, and WL shortest path takes 484 days. On NCI1 and NCI109 (over 4100 graphs), WL subtree finishes in under 8 minutes, whereas random walk requires 9 days and Ramon-Gärtner requires 81 days.

Knowl 10 — Runtime Scaling Characteristics of Pairwise versus Global Weisfeiler-Lehman Subtree Kernel Computation
empirical result
The computational runtime of the Weisfeiler-Lehman subtree kernel was empirically benchmarked on synthetic random graphs by varying four parameters independently around default settings ( $N = 10$ graphs, $n = 100$ nodes, subtree height $h = 4$ , and graph density $c = 0.4$ , where density defines the edge count $\lfloor c n(n-1)/2 \rfloor$ ):
1. Number of graphs $N \in \{10, 100, 1000\}$ : The pairwise computation scheme ( $O(N^2hm)$ ) scales quadratically with $N$ , reaching $\approx 10^5$ seconds at $N=1000$ . In contrast, the global computation scheme ( $O(Nhm + N^2hn)$ ) scales approximately linearly with $N$ up to $N = 1000$ (taking $\approx 10^1$ seconds), showing that feature extraction ( $Nhm$ ) dominates and the sparse $N^2hn$ inner-product multiplications remain negligible in this regime.
2. Graph size $n \in \{100, 200, \dots, 1000\}$ : Both schemes scale quadratically with $n$ (reflecting linear scaling with edge count $m = 0.4 n(n-1)/2$ ), but the global scheme is substantially faster across all graph sizes.
3. Subtree height $h \in \{2, 4, 8\}$ : Runtime increases strictly linearly with $h$ for both implementations, with the global scheme maintaining a lower slope.
4. Graph density $c \in \{0.1, 0.2, \dots, 0.9\}$ : Runtime increases linearly with density $c$ (and hence linearly with $m$ ). Across all parameter configurations, the global scheme consistently requires less runtime than the pairwise approach.

Coverage note — None was omitted; all key theoretical definitions, algorithms, complexity analyses, and empirical benchmark results were captured.

References

1.L. Babai and L. Kucera. Canonical labelling of graphs in linear average time. In Proceedings Symposium on Foundations of Computer Science, pages 39–46, 1979.
2.F. R. Bach. Graph kernels between point clouds. In Proceedings of the International Conference on Machine Learning, pages 25–32, 2008.
3.K. M. Borgwardt and H.-P. Kriegel. Shortest-path kernels on graphs. In Proceedings of the International Conference on Data Mining, pages 74–81, 2005.
4.K. M. Borgwardt, C. S. Ong, S. Schönauer, S. V. N. Vishwanathan, A. J. Smola, and H. P. Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(Suppl 1):i47–i56, Jun 2005.
5.H. Bunke and G. Allermann. Inexact graph matching for structural pattern recognition. Pattern Recognition Letters, 1:245–253, 1983.
6.J.-Y. Cai, M. Fürer, and N. Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389–410, 1992.
7.C.-C. Chang and C.-J. Lin. LIBSVM: A Library For Support Vector Machines, 2001. Software available at http://www.csie.ntu.edu.tw/∼cjlin/libsvm.
8.F. Costa and K. De Grave. Fast neighborhood subgraph pairwise distance kernel. In Proceedings of the International Conference on Machine Learning, pages 255–262, 2010.
9.A. K. Debnath, R. L. Lopez de Compadre, G. Debnath, A. J. Shusterman, and C. Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. J. Med. Chem., 34:786–797, 1991.
10.P. D. Dobson and A. J. Doig. Distinguishing enzyme structures from non-enzymes without alignments. J. Mol. Biol., 330(4):771–783, Jul 2003.
11.H. Fröhlich, J. Wegner, F. Sieker, and A. Zell. Optimal assignment kernels for attributed molecular graphs. In Proceedings of the International Conference on Machine Learning, pages 225–232, Bonn, Germany, 2005.
12.M. R. Garey and D. S. Johnson. Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, 1979.
13.T. Gärtner, P. A. Flach, and S. Wrobel. On graph kernels: Hardness results and efficient alternatives. In Proceedings of the Annual Conference on Computational Learning Theory, pages 129–143, 2003.
14.Z. Harchaoui and F. Bach. Image classification with segmentation graph kernels. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2007.
15.D. Haussler. Convolutional kernels on discrete structures. Technical Report UCSC-CRL-99 - 10, Computer Science Department, UC Santa Cruz, 1999.
16.S. Hido and H. Kashima. A linear-time graph kernel. In Proceedings of the International Conference on Data Mining, pages 179–188, 2009.
17.T. Hofmann, B. Schölkopf, and A. J. Smola. Kernel methods in machine learning. Annals of Statistics, 36(3):1171–1220, 2008.
18.T. Horváth, T. Gärtner, and S. Wrobel. Cyclic pattern kernels for predictive graph mining. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 158–167, 2004.
19.H. Kashima, K. Tsuda, and A. Inokuchi. Marginalized kernels between labeled graphs. In Proceedings of the International Conference on Machine Learning, Washington, DC, United States, 2003.
20.I. R. Kondor and K. M. Borgwardt. The skew spectrum of graphs. In Proceedings of the International Conference on Machine Learning, pages 496–503, 2008.
21.I. R. Kondor, N. Shervashidze, and K. M. Borgwardt. The graphlet spectrum. In Proceedings of the International Conference on Machine Learning, pages 529–536, 2009.
22.P. Mahé and J.-P. Vert. Graph kernels based on tree patterns for molecules. Machine Learning, 75 (1):3–35, 2009.
23.P. Mahé, N. Ueda, T. Akutsu, J. Perret, and J. Vert. Extensions of marginalized graph kernels. In Proceedings of the International Conference on Machine Learning, pages 552–559, Alberta, Canada, 2004.
24.K. Mehlhorn. Data Structures and Efficient Algorithms. Springer, 1984.
25.H. L. Morgan. The generation of unique machine description for chemical structures - a technique developed at chemical abstracts service. Journal of Chemical Documentation, 5(2):107–113, 1965.
26.M. Neuhaus and H. Bunke. Self-organizing maps for learning the edit costs in graph matching. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 35(3):503–514, 2005.
27.J. Ramon and T. Gärtner. Expressivity versus efficiency of graph kernels. Technical report, First International Workshop on Mining Graphs, Trees and Sequences (held with ECML/PKDD’03), 2003.
28.B. Schölkopf and A. J. Smola. Learning with Kernels. MIT Press, Cambridge, MA, 2002.
29.I. Schomburg, A. Chang, C. Ebeling, M. Gremse, C. Heldt, G. Huhn, and D. Schomburg. Brenda, the enzyme database: updates and major new developments. Nucleic Acids Research, 32D:431–433, 2004.
30.N. Shervashidze and K. M. Borgwardt. Fast subtree kernels on graphs. In Y. Bengio, D. Schuurmans, J. Lafferty, C. K. I. Williams, and A. Culotta, editors, Proceedings of the Conference on Advances in Neural Information Processing Systems, pages 1660–1668, 2009.
31.N. Shervashidze, S.V.N. Vishwanathan, T. Petri, K. Mehlhorn, and K.M. Borgwardt. Efficient graphlet kernels for large graph comparison. In David van Dyk and Max Welling, editors, Proceedings of the International Conference on Artificial Intelligence and Statistics, 2009.
32.F. Suard, V. Guigue, A. Rakotomamonjy, and A. Benshrair. Pedestrian detection using stereo-vision and graph kernels. In IEEE Symposium on Intelligent Vehicles, 2005.
33.J.-P. Vert. The optimal assignment kernel is not positive definite. CoRR, abs/0801.4061, 2008.
34.J.-P. Vert, T. Matsui, S. Satoh, and Y. Uchiyama. High-level feature extraction using svm with walk-based graph kernel. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, pages 1121–1124, 2009.
35.S. V. N. Vishwanathan, N. N. Schraudolph, I. R. Kondor, and K. M. Borgwardt. Graph kernels. Journal of Machine Learning Research, 11:1201–1242, 2010.
36.N. Wale and G. Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. In Proceedings of the International Conference on Data Mining, pages 678–689, Hong Kong, 2006.
37.B. Weisfeiler and A. A. Lehman. A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technicheskaya Informatsia, Ser. 2, 9, 1968.

Citation

MLA

Shervashidze, N., et al. “Weisfeiler-Lehman Graph Kernels”. Journal of Machine Learning Research, vol. 12, no. 77, 2011, pp. 2539–61, https://www.jmlr.org/papers/v12/shervashidze11a.html.

APA

Shervashidze, N., Schweitzer, P., Leeuwen, E. J. van ., Mehlhorn, K., & Borgwardt, K. M. (2011). Weisfeiler-Lehman Graph Kernels. Journal of Machine Learning Research, 12(77), 2539–2561. https://www.jmlr.org/papers/v12/shervashidze11a.html

Chicago

Shervashidze, N., P. Schweitzer, E. J. van . Leeuwen, K. Mehlhorn, and K. M. Borgwardt. 2011. “Weisfeiler-Lehman Graph Kernels”. Journal of Machine Learning Research 12 (77): 2539–61. https://www.jmlr.org/papers/v12/shervashidze11a.html.

Harvard

Shervashidze, N. et al. (2011) “Weisfeiler-Lehman Graph Kernels”, Journal of Machine Learning Research, 12(77), pp. 2539–2561. Available at: https://www.jmlr.org/papers/v12/shervashidze11a.html.

Vancouver

1. Shervashidze N, Schweitzer P, Leeuwen EJ van, Mehlhorn K, Borgwardt KM (2011) Weisfeiler-Lehman Graph Kernels. Journal of Machine Learning Research 12:2539–2561

BibTeX

@article{JMLR:v12:shervashidze11a,
  author  = {Nino Shervashidze and Pascal Schweitzer and Erik Jan van Leeuwen and Kurt Mehlhorn and Karsten M. Borgwardt},
  title   = {Weisfeiler-Lehman Graph Kernels},
  journal = {Journal of Machine Learning Research},
  year    = {2011},
  volume  = {12},
  number  = {77},
  pages   = {2539--2561},
  url     = {http://jmlr.org/papers/v12/shervashidze11a.html}
}

Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Weisfeiler-Lehman Graph Kernels

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — General Weisfeiler-Lehman Graph Kernel Framework

Knowl 2 — Weisfeiler-Lehman Subtree Kernel

Knowl 3 — Global Algorithm for Computing the Weisfeiler-Lehman Subtree Kernel on Multiple Graphs

Knowl 4 — Recursive Formulation and Equivalence of the Weisfeiler-Lehman Subtree Kernel

Knowl 5 — 1-Dimensional Weisfeiler-Lehman Graph Relabeling Procedure

Knowl 6 — Weisfeiler-Lehman Edge Kernel

Knowl 7 — Weisfeiler-Lehman Shortest Path Kernel