Expressivity versus efficiency of graph kernels

By J. Ramon, Thomas Gaertner. 2003

253 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…”
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…”
Propagation kernels: efficient graph kernels from propagated information (2014, background): “2009; Kriege and Mutzel 2012), kernels based on subtree patterns (Mahé and Vert 2009; Ramon and Gärtner 2003), and kernels based on structure propagation (Shervashidze et al.”
Fast subtree kernels on graphs (2009, background): “Definition The first subtree kernel on graphs was defined by [10].”
Glocalized Weisfeiler-Lehman Graph Kernels: Global-Local Feature Maps of Graphs (2017, methodology): “Kernels based on tree patterns were initially proposed by Ramon and Gärtner [24] and later refined by Mahé and Vert [25].”
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].”
A Structural Smoothing Framework For Robust Graph Comparison (2015, methodology): “In addition to the base kernels, we also compare our smoothed kernels with the random walk kernel [7], the Ramon-Gärtner subtree [18], and p-step random walk kernel [24].”
Graph Invariant Kernels (2015, background): “Examples include tree-structured patterns [Ramon and Gärtner, 2003; Mahé and Vert, 2009], paths [Kashima et al.”
A survey on graph kernels (2019, methodology): “Tree pattern kernels [28, 29] 2003”
Neural Network-based Graph Embedding for Cross-Platform Binary Code Similarity Detection (2017, methodology): “For example, [33] counts specific subtree patterns in a graph; [41] counts the appearance of subgraph with specific sizes; in [40], different structures will be counted in a process named Weisfeiler-Lehman algorithm.”
Acing the IOC Game: Toward Automatic Discovery and Analysis of Open-Source Cyber Threat Intelligence (2016, background): “rect product kernel [27] and subtree kernel [39].”
Efficient graphlet kernels for large graph comparison (2009, background): “Many different graph kernels have been defined, which focus on different types of substructures in graphs, such as random walks (Gärtner et al., 2003; Kashima et al., 2004), shortest paths (Borgwardt & Kriegel, 2005), subtrees (Ramon & Gärtner, 2003), and cycles (Horvath et al., 2004).”
Shortest-path kernels on graphs (2005, background): “Walks [8, 13], subtrees [17] and cyclic patterns [11] have been considered for this purpose.”
Efficient Graph Kernels by Randomization (2012, background): “The runtime complexity of this approach for N graphs is O(n2T 4) [16], where d is the maximum node degree in all graphs.”