Weisfeiler-Lehman Graph Kernels

By Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, Karsten M. Borgwardt. 2011

2,430 citations recorded by the source corpus.

How researchers see this paper

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

In Graph Learning

Citations in the corpus

Inductive Representation Learning on Large Graphs (2017, methodology): “This includes a wide variety of kernel-based approaches, where feature vectors for graphs are derived from various graph kernels (see [30] and references therein).”
Learning Convolutional Neural Networks for Graphs (2016, methodology): “More-over, while all graph kernels have a training complexity at least quadratic in the number of graphs (Shervashidze et al., 2011), which is prohibitive for large-scale problems, P ATCHY - SAN scales linearly with the number of graphs.”
Gated Graph Sequence Neural Networks (2015, methodology): “Standard approaches to the problem include engineering custom features of an input graph, graph kernels (Kashima et al., 2003; Shervashidze et al., 2011), and methods that deﬁne graph features in terms of random walks on graphs (Perozzi et al., 2014).”
Discriminative Embeddings of Latent Variable Models for Structured Data (2016, neutral): “, 2009) and the family of Weisfeiler-Lehman kernels (WL kernel) (Shervashidze et al., 2011).”
Relational inductive biases, deep learning, and graph networks (2018, background): “2 Limitations of graph networks One limitation of GNs’ and MPNNs’ form of learned message-passing (Shervashidze et al., 2011) is that it cannot be guaranteed to solve some classes of problems, such as discriminating between certain non-isomorphic graphs.”
The More You Know: Using Knowledge Graphs for Image Classification (2016, background): “ogram veriﬁcation. There is also a substantial amount of work on various types of kernels deﬁned for graphs [36] such as diffusion kernels [14], graphlet kernels [33], Weisfeiler-Lehman graph kernels [32], deep graph kernels [27], graph invariant kernels [26] and shortest-path kernels [1]. The metho”
Unsupervised Inductive Whole-Graph Embedding by Preserving Graph Proximity (2019, background): “In contrast, although GRAPH KERNELS can be considered as inductive (Shervashidze et al., 2011), graph kernels have to perform the subgraph extraction for every graph, which can be slow and cannot adapt to different graph proximity metrics.”
Pre-training Graph Neural Networks with Kernels (2018, neutral): “…the performance of four state-of-the-art graph kernels: the graphlet kernel (GK) [Shervashidze et al. , 2009], the random walk kernel (RW) [Vishwanathan et al. , 2010], the propagation kernel (PK) [Neumann et al. , 2012], and the Weisfeiler-Lehman subtree kernel (WL) [Shervashidze et al. , 2011a].”
How Powerful are Graph Neural Networks? (2018, methodology): “We compare the GNNs above with a number of state-of-the-art baselines for graph classiﬁcation: (1) The WL subtree kernel (Shervashidze et al., 2011), where C -SVM (Chang & Lin, 2011) was used as a classiﬁer.”
Hierarchical Graph Representation Learning with Differentiable Pooling (2018, methodology): “We use the GRAPHLET [34], the SHORTESTPATH [2], WEISFEILER-LEHMAN kernel (WL) [33], and WEISFEILERLEHMAN OPTIMAL ASSIGNMENT KERNEL (WL-OA) [22] as kernel baselines.”
Representation Learning on Graphs with Jumping Knowledge Networks (2018, background): “Such schemes have been shown to generalize the Weisfeiler-Lehman graph isomorphism test (Weisfeiler & Lehman, 1968) enabling to simultaneously learn the topology as well as the distribution of node features in the neighborhood (Shervashidze et al., 2011; Kipf & Welling, 2017; Hamilton et al., 2017).”
An End-to-End Deep Learning Architecture for Graph Classification (2018, methodology): “We set the decay parameter λ of RW to the largest power of 10 that is smaller than the reciprocal of the squared maximum node degree as suggested in (Shervashidze et al. 2011).”
subgraph2vec: Learning Distributed Representations of Rooted Sub-graphs from Large Graphs (2016, methodology): “Subsequently, following the language model training process with the subgraphs and their contexts, subgraph2vec learns the intended subgraph embeddings.”
Covariant Compositional Networks For Learning Graphs (2018, background): “…artner, 2002; Borgwardt & Kriegel, 2005; Feragen et al., 2013), counting subgraphs (Shervashidze et al., 2009), spectral ideas (Vishwanathan et al., 2010), label propagation schemes with hashing (Shervashidze et al., 2011; Neumann et al., 2016), and even algebraic ideas (Kondor & Borgwardt, 2008).”
Deriving Neural Architectures from Sequence and Graph Kernels (2017, methodology): “This parameter tying mechanism allows our model to embed Weisfeiler-Lehman kernel (Shervashidze et al., 2011).”
Graphite: Iterative Generative Modeling of Graphs (2018, background): “Empirically, the test has been shown to fail on some regular graphs but gives excellent performance on real-world graphs [41].”
Provably Powerful Graph Networks (2019, methodology): “The WL tests have found many applications in machine learning: in addition to Xu et al. (2019); Morris et al. (2018), This idea was used in Shervashidze et al. (2011) to construct a graph kernel method, which was further generalized to higher order WL tests in Morris et al. (2017).”
Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks (2018, methodology): “2009), and, most notably, the Weisfeiler-Lehman subtree kernel (Shervashidze et al. 2011) as well as its higher-order variants (Morris, Kersting, and Mutzel 2017).”
A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications (2017, methodology): “for calculating graph similarities [49], [55], [95].”