Shortest-path kernels on graphs

By Karsten M. Borgwardt, Hans-Peter Kriegel. 2005

1,134 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Software, 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 Artificial Intelligence

In Computer Vision and Pattern Recognition

In Software

In Graph Learning

Citations in the corpus

Learning Convolutional Neural Networks for Graphs (2016, methodology): “…to (Yanardag & Vish-wanathan, 2015) and graph invariant kernels (Orsini et al., 2015) compare graphs based on the existence or count of small substructures such as shortest paths (Borgwardt & Kriegel, 2005), graphlets, subtrees, and other graph invariants (Haussler, 1999; Orsini et al., 2015).”
Discriminative Embeddings of Latent Variable Models for Structured Data (2016, neutral): “…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 Weisfeiler-Lehman kernels (WL kernel) (Shervashidze et…”
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].”
Position-aware Graph Neural Networks (2019, neutral): “Kernels based on shortest paths were ﬁrst proposed in (Borgwardt & Kriegel, 2005).”
Pre-training Graph Neural Networks with Kernels (2018, neutral): “The Shortest Path (SP) Kernel associates a feature to each pair of node labels at a certain (unbounded) shortest-path distance [Borgwardt and Kriegel, 2005].”
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.”
subgraph2vec: Learning Distributed Representations of Rooted Sub-graphs from Large Graphs (2016, background): “DOI: 10.1145/1235 lar and widely adopted approaches to measure similarities among graphs [3, 4, 6, 7, 14].”
Covariant Compositional Networks For Learning Graphs (2018, methodology): “Learning on graphs has a long history in the kernels literature, including approaches based 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…”
Graphite: Iterative Generative Modeling of Graphs (2018, background): “, 2009; Shervashidze and Borgwardt, 2009) and shortest paths (Borgwardt and Kriegel, 2005), or explicitly learned from data (Yanardag and Vishwanathan, 2015).”
Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks (2018, background): “…Networks (Li et al. 2016), GraphSAGE (Hamilton, Ying, and Leskovec 2017a), SplineCNN (Fey et al. 2018), and the spectral approaches proposed in (Bruna et al. 2014; Defferrard, X., and Vandergheynst 2016; Kipf and Welling 2017)—all of which descend from early work in (Merkwirth and Lengauer…”
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.”
A simple yet effective baseline for non-attribute graph classification (2018, neutral): “Shortest path kernel[BK05] is derived by comparing the paths between graphs.”
Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs (2017, neutral): “We consider four variants of providing additional degree labels L deg ( j ) and L deg ( i ) about a directed edge ( j, i ) : L deg Table 8 reveals that degree information can improve the results considerably, especially for datasets without given edge labels (by up to 5 percentage points for ENZYMES”
Graph Kernels (2008, neutral): “Other decompositions of graphs, which are well suited for particular application domains, include subtrees (Ramon and Gärtner, 2003), shortest paths (Borgwardt and Kriegel, 2005), molecular fingerprints based on various types of depth-first searches (Ralaivola et al., 2005), and structural…”
On Valid Optimal Assignment Kernels and Applications to Graph Classification (2016, methodology): “In addition we implemented a graphlet kernel (GL) and the shortest-path kernel (SP) [3].”
Propagation kernels: efficient graph kernels from propagated information (2014, background): “2011), the shortest path kernel (sp) (Borgwardt and Kriegel 2005), the graph hopper kernel (gh) (Feragen et al.”
The Multiscale Laplacian Graph Kernel (2016, methodology): “We compared the efﬁcacy of the MLG kernel with some of the top performing graph kernels from the literature: the Weisfeiler–Lehman Kernel, the Weisfeiler–Lehman Edge Kernel (Shervashidze et al., 2009), the Shortest Path Kernel (Borgwardt & Kriegel, 2005), the Graphlet Kernel (Shervashidze et al., 20”
Graph Representation Learning (2020, methodology): “[2003] involves running random walks over the graph and then counting the occurrence of different degree sequences,(3) while the shortest-path kernel of Borgwardt and Kriegel [2005] involves a similar idea but uses only the shortest-paths between nodes (rather 3Other node labels can also be used.”