Graph Kernels

By S. V. N. Vishwanathan, Karsten M. Borgwardt, Imre Kondor, N. Schraudolph. 2008

1,295 citations recorded by the source corpus.

We present a unified framework to study graph kernels, special cases of which include the random walk (Gartner et al., 2003; Borgwardt et al., 2005) and marginalized (Kashima et al., 2003, 2004; Mahet al., 2004) graph kernels. Through reduction to a Sylvester equation we improve the time complexity of kernel computation between unlabeled graphs with n vertices from O(n6) to O(n3). We find a spectral decomposition approach even more efficient when computing entire kernel matrices. For labeled graphs we develop conjugate gradient and fixed-point methods that take O(dn3) time per iteration, where d is the size of the label set. By extending the necessary linear algebra to Reproducing Kernel Hilbert Spaces (RKHS) we obtain the same result for d-dimensional edge kernels, and O(n4) in the infinite-dimensional case; on sparse graphs these algorithms only take O(n2) time per iteration in all cases. Experiments on graphs from bioinformatics and other application domains show that these techniques can speed up computation of the kernel by an order of magnitude or more. We also show that certain rational kernels (Cortes et al., 2002, 2003, 2004) when specialized to graphs reduce to our random walk graph kernel. Finally, we relate our framework to R-convolution kernels (Haussler, 1999) and provide a kernel that is close to the optimal assignment kernel of kernel of Frohlich et al. (2006) yet provably positive semi-definite.

Subfields: Graph Learning

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

Learning Convolutional Neural Networks for Graphs (2016, background): “Graph kernels allow kernel-based learning approaches such as SVMs to work directly on graphs (Vishwanathan et al., 2010).”
DeepWalk: online learning of social representations (2014, methodology): “Graph Kernels [42] have been proposed as a way to use relational data as part of the classification process, but are quite slow unless approximated [19].”
Discriminative Embeddings of Latent Variable Models for Structured Data (2016, neutral): “On graph benchmark datasets, we compare with subtree kernel (Ramon & Gärtner, 2003) (R&G, for short), random walk kernel(Gärtner et al., 2003; Vishwanathan et al., 2010), shortest path kernel (Borgwardt & Kriegel, 2005), graphlet kernel(Shervashidze et al., 2009) and the family of…”
Convolutional Neural Network Architectures for Matching Natural Language Sentences (2014, background): “Matching structured objects rarely goes beyond estimating the similarity of objects in the same domain [23, 24, 19], with few exceptions like [2, 18].”
The More You Know: Using Knowledge Graphs for Image Classification (2016, background): “There is also a substantial amount of work on various types of kernels defined 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].”
Pre-training Graph Neural Networks with Kernels (2018, neutral): “State-of-the-art machine learning techniques for classiﬁcation and regression on graphs are at the moment kernel machines equipped with speciﬁcally designed kernels for graphs (e.g, Shervashidze et al. [2009]; Vishwanathan et al. [2010]; Da San Martino et al. [2012a]).”
An End-to-End Deep Learning Architecture for Graph Classification (2018, methodology): “…and experimental setting We compare DGCNN with four 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.…”
Representation Learning on Graphs: Methods and Applications (2017, methodology): “Representation learning on subgraphs is closely related to the design of graph kernels, which deﬁne a distance measure between subgraphs [57].”
subgraph2vec: Learning Distributed Representations of Rooted Sub-graphs from Large Graphs (2016, background): “…3 Initialization: Sample Φ from U |SGV ocab|×δ 4 for e = 0 to e do 5 G = Shuffle (G) 6 for each Gi ∈ G do 7 for each v ∈ Vi do 8 for d = 0 to D do 9 sg (d) v := GetWLSubgraph(v,Gi, d) 10 RadialSkipGram (Φ, sg (d) v , Gi, D) 11 return Φ revealing that the learned word embeddings preserve semantics.”
Covariant Compositional Networks For Learning Graphs (2018, methodology): “…on random walks (G ¨ 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…”
Deriving Neural Architectures from Sequence and Graph Kernels (2017, background): “The derivation of the above neural module could be extended to other classes of graph kernels, such as subtree kernels (cf. (Ramon & G¨artner, 2003; Vishwanathan et al., 2010)).”
Graphite: Iterative Generative Modeling of Graphs (2018, methodology): “ubgraph patterns (Shervashidze et al., 2009; Shervashidze and Borgwardt, 2009) and shortest paths (Borgwardt and Kriegel, 2005), or explicitly learned from data (Yanardag and Vishwanathan, 2015). See Vishwanathan et al. (2010) for a detailed review. In fact, the WL algorithm discussed previously den”
Provably Powerful Graph Networks (2019, neutral): “4110 4127 5000 1000 1500 classes 2 2 2 2 2 3 2 3 avg node # 17.9 25.5 39.1 29.8 29.6 74.4 19.7 13 Results GK (Shervashidze et al., 2009) 81.39 1.7 55.65 0.5 71.39 0.3 62.49 0.3 62.35 0.3 NA NA NA RW (Vishwanathan et al., 2010) 79.17 2.1 55.91 0.3 59.57 0.1 > 3 days NA NA NA NA PK (Neumann et al.,”
Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks (2018, neutral): “In recent years, numerous approaches have been proposed for machine learning graphs—most notably, approaches based on graph kernels (Vishwanathan et al. 2010) or, alternatively, using graph neural network algorithms (Hamilton, Ying, and Leskovec 2017b).”
A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications (2017, background): “In the third type of graph kernels, a graph is decomposed into random walks or paths and represented as the counts of occurrence of random walks [137] or paths [138] in it.”
Text Categorization as a Graph Classification Problem (2015, background): “We refer to (Vishwanathan et al., 2010) for an in-depth review of the topic and in particular its limitations in terms of number of unique node labels, which make them unsuitable for our problem as tested in practice (limited to a few tens of unique labels compared to hundreds of thousands for us).”
Visual Causal Feature Learning (2014, background): “by an L 2 norm. Alternatives include other L p-induced metrics, distances in implicit feature spaces induced by image kernels (Harchaoui and Bach, 2007; Grauman and Darrell, 2007; Bosch et al., 2007; Vishwanathan, 2010) and distances in learned representation spaces (Bengio et al., 2013). Algorithm ”