Fast subtree kernels on graphs

By Nino Shervashidze, Karsten M. Borgwardt. 2009

268 citations recorded by the source corpus.

Subfields: Graph Learning, Algorithms & Complexity

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 Algorithms & Complexity

Citations in the corpus

Unsupervised Inductive Whole-Graph Embedding by Preserving Graph Proximity (2019, background): “Different graph kernels extract different types of substructures in a graph, e.g. graphlets (Shervashidze et al., 2009), subtree patterns (Shervashidze & Borgwardt, 2009), etc., and the resulting vector representation for each graph is typically called “feature vector” (Yanardag & Vishwanathan,…”
Graphite: Iterative Generative Modeling of Graphs (2018, background): “utation of feature maps. Extensive prior work has led to the development of graph kernels that are either hand designed based on graph properties such as subgraph patterns (Shervashidze et al., 2009; Shervashidze and Borgwardt, 2009) and shortest paths (Borgwardt and Kriegel, 2005), or explicitly le”
Deep Graph Kernels (2015, methodology): “Then, we discuss three major graph kernel families, namely, graph kernels based on limited-sized subgraphs [13, 28], graph kernels based on subtree patterns [24, 27], and graph kernels based on walks [14, 33] and paths [3].”
Modelling input texts: from Tree Kernels to Deep Learning (2015, unknown): “A highly efficient subtree kernel on graphs that exploits the idea from WeisfeilerLehman test of graph isomorphism is proposed in [145].”
Fast Neighborhood Subgraph Pairwise Distance Kernel (2010, methodology): “…Kernel (PMCSK) introduced in (Schietgat et al., 2009), the Neighborhood Subgraph Kernel (NSK) similar in spirit to the fast kernel presented in (Shervashidze & Borgwardt, 2009), and the Pairwise Distance Kernel (PDK), similar to the Equal Length Shortest-Path Kernel by (Borgwardt & Kriegel,…”
Halting in Random Walk Kernels (2015, background): “Over the last decade, graph kernels have become a popular approach to graph comparison [4, 5, 7, 9, 12, 13, 14], which is at the heart of many machine learning applications in bioinformatics, imaging, and social-network analysis.”
Learning with Similarity Functions on Graphs using Matchings of Geometric Embeddings (2015, background): “These kernels are the shortest-path kernel ( SP ) [4], the 4-graphlet kernel ( GL ) [37], the random walk kernel ( RW ) [15], the Lov´asz ϑ ( Lo-ϑ ) and svm-ϑ ( SVM-ϑ ) kernels [23], and the fast subtree kernel ( ST ) [35].”
A Structural Smoothing Framework For Robust Graph Comparison (2015, background): “While the DAG creation in Weisfeiler-Lehman kernel also adds a negligible overhead, the cost of smoothing becomes significant if the vocabulary size gets prohibitively large due to the exponential growing nature of the kernel w.r.t. to subtree parameter h. Finally, in our fourth experiment, we test ”
Fast Random Walk Graph Kernel (2012, background): “There are three major groups in graph kernels: kernels based on walks and paths [9, 20, 10, 3, 42, 43], kernels based on limited-size subgraphs [16, 36, 21], and kernels based on subtree patterns [25, 35, 15].”
Weisfeiler-Lehman Graph Kernels (2011, methodology): “In this section we present the Weisfeiler-Lehman subtree kernel (Shervashidze and Borgwardt, 2009), which is a natural instance of Definition 2.”
Ordered Decompositional DAG kernels enhancements (2015, methodology): “The Weisfeiler-Lehman Fast Subtree kernel (FS) counts the number of identical subtree patterns obtained by subtree-walks up to height h [24, 38].”
Power Iterated Color Refinement (2014, background): “1, and to the combinatorial CR implementation WL in Matlab of (Shervashidze and Borgwardt 2009; Shervashidze et al. 2011) used for fast Weisfeiler-Lehman graph kernels, see Tab.”
Discriminative Clustering by Regularized Information Maximization (2010, methodology): “We use the subtree kernel developed by [18] with subtree height of 1.”
A Tree-Based Kernel for Graphs (2012, methodology): “In addition, results from the following algorithms, when available, are provided from [18] and [20]: Gaston, Correlated Pattern Mining (CPM), MOLFEA, Marginalized Graph Kernel (MGK) and SVM with frequent pattern mining (freqSVM).”
Graph Representation Learning (2020, background): “The challenge with this approach is that counting these graphlets is a combinatorially difficult problem, though numerous approximations have been proposed [Shervashidze and Borgwardt, 2009].”
Deep Co-Investment Network Learning for Financial Assets (2018, methodology): “transform all the time series into the graphs, and we apply a graph kernel, Weisfeiler-Lehman kernel [20], to compare the similarities between the stocks.”
Tree-Based Kernel for Graphs With Continuous Attributes (2015, background): “For sake of comparison, the results of the Weisfeiler–Lehman kernel (WL) [7] and ODDST [4] kernels that can deal only with discrete attributes, are reported too.”
A memory efficient graph kernel (2012, background): “Examples of such substructures are walks [1], paths [2], [3], or subtrees [4], [5].”