On Graph Kernels: Hardness Results and Efficient Alternatives

By Thomas Gärtner, Peter A. Flach, Stefan Wrobel. 2003

1,062 citations recorded by the source corpus.

Subfields: Graph Learning, Statistical Learning Theory

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

In Statistical Learning Theory

Citations in the corpus

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…”
Position-aware Graph Neural Networks (2019, background): “Gärtner et al. (2003) and Kashima et al.”
Pre-training Graph Neural Networks with Kernels (2018, neutral): “Random walk kernels (MGK) [Gartner et al. , 2003] considers as features all the possible random walks in a graph.”
Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks (2018, background): “Important early work in this area includes random-walk based kernels (G¨artner, Flach, and Wrobel 2003; Kashima, Tsuda, and Inokuchi 2003)) and kernels based on shortest paths (Borgwardt and Kriegel 2005).”
Graph Kernels (2008, methodology): “The first such kernels were proposed by Gärtner et al. (2003) and later extended by Borgwardt et al. (2005).”
Propagation kernels: efficient graph kernels from propagated information (2014, background): “Most of the existing graph kernels (Shervashidze et al. 2009, 2011; Hido and Kashima 2009; Kashima et al. 2003; Gärtner et al. 2003) are designed for unlabeled graphs or graphs with a complete set of discrete node labels.”
TUDataset: A collection of benchmark datasets for learning with graphs (2020, background): “Important approaches include random-walk and shortest paths based kernels (Gärtner et al., 2003; Sugiyama & Borgwardt, 2015; Borgwardt & Kriegel, 2005; Kriege et al., 2019), as well as the Weisfeiler-Lehman subtree kernel (Shervashidze et al., 2011; Morris et al., 2017).”
InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization (2019, methodology): “For graph classification, we used 6 state-of-the-art graph kernels for comparison: Random Walk (RW) [14], Shortest Path Kernel (SP) [3], Graphlet Kernel (GK) [52], Weisfeiler-Lehman Sub-tree Kernel (WL) [51], Deep Graph Kernels (DGK) [63], and Multi-Scale Laplacian Kernel (MLG) [27].”
Shortest-path kernels on graphs (2005, background): “In [9] it is shown that computing kernels based on subgraphs is NP-hard.”
Graph Capsule Convolutional Neural Networks (2018, methodology): “Graph Kernel Baselines: We adopted 6 state-ofart graphs kernels for comparison namely: Random Walk (RW) (Gärtner et al., 2003), Shortest Path Kernel (SP) (Borgwardt & Kriegel, 2005), Graphlet Kernel (GK) (Shervashidze et al.”
Efficient Graph Kernels by Randomization (2012, background): “Unfortunately, existing graph kernels [4,6,10,18,19]”
Integrating structured biological data by Kernel Maximum Mean Discrepancy (2006, background): “However, as Gärtner et al. (2003) show, an injective φ(x) allows one to match graphs by computing φ(x) − φ(x ) 2 = k(x, x) + k(x , x ) − 2k(x, x ).”
Substructure Assembling Network for Graph Classification (2018, methodology): “Graph kernels vary based on graph features used for measuring similarity, ranging from random walks (Gärtner, Flach, and Wrobel 2003), shortest paths (Borgwardt and Kriegel 2005), to graph substructures (Shervashidze et al. 2009; Yanardag and Vishwanathan 2015).”
A survey of graph edit distance (2010, background): “9 Comparison of performance with increasing strength of distortion in [30] SVM), and random walks in graphs [55] (RW-SVM), respectively.”