Fast Neighborhood Subgraph Pairwise Distance Kernel

By Fabrizio Costa, Kurt De Grave. 2010

303 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Pre-training Graph Neural Networks with Kernels (2018, positive): “Costa and De Grave [2010] extended the WL Subtree Kernel by computing exact matches between pairs of subgraphs with controlled size and distance.”
Contextual Weisfeiler-Lehman graph kernel for malware detection (2016, methodology): “ry, CWLK has the same efﬁciency as that of WLK and supports explicit feature vector representations of PRGs. Relation to other spatial contextual kernels. Two recently proposed graph kernels [13] and [14], consider incorporating the spatial context information to neighborhood subgraph features. They”
Link Prediction Based on Graph Neural Networks (2018, background): “Common of substructures include walks [54, 55], subgraphs [56, 57], paths [58], and subtrees [34, 59].”
Subgraph Matching Kernels for Attributed Graphs (2012, methodology): “As remarked before (Wale et al., 2008; Costa & De Grave, 2010) kernels using features of diﬀerent size are typically biased towards large features.”
A memory efficient graph kernel (2012, background): “Examples of such substructures are walks [1], paths [2], [3], or subtrees [4], [5].”
A survey on graph kernels (2019, background): “Costa and De Grave [39] introduced the neighborhood subgraph pairwise distance kernel which associates a string with every vertex representing its neighborhood up to a certain depth.”
A Tree-Based Kernel for Graphs (2012, methodology): “Costa and De Grave [5] extended the Fast Subtree Kernel by computing exact matches between pairs of subgraphs with controlled size and distance.”
Graph Invariant Kernels (2015, methodology): “The Gram matrices were normalized as proposed in [Costa and De Grave, 2010]: for each radius a different Gram matrix is extracted then normalized, we compute their sum and apply normalization again.”
Tree-Based Kernel for Graphs With Continuous Attributes (2015, background): “State-of-the-art kernels use explicit featu re mapping techniques [4], [6], [7], with computational complexi ties almost linear in the size of the graphs.”
Hunt For The Unique, Stable, Sparse And Fast Feature Learning On Graphs (2017, background): “kernel [9], Weisfeiler-Lehman kernel [31], deep graph kernels [34], graph invariant kernels [27] and multiscale Laplacian graph kernel [21].”
Ordered Decompositional DAG kernels enhancements (2015, methodology): “On these datasets, the baselines FS, NSPDK, ODDSTh kernels and the proposed ODDST+ kernel show very similar performances.”
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.”
Deep Graph Kernels (2015, methodology): “In a similar fashion, we can plug other graph kernels into our framework such as random-walk kernels [10], labeled version of graphlet kernel [28], subtree kernels [6, 24], cyclic pattern kernels [13] and p-step random-walk kernel [30].”
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting (2020, methodology): “In particular, subgraph patterns have been used to define Graph Kernels (GKs) [83], [84], [85], [86], [87], with the most prominent being the graphlet kernel [84].”
On Filter Size in Graph Convolutional Networks (2018, background): “We do not include other state-of-the-art graph kernels such as NSPDK [33] and ODD [26] because their performance is not much different from the considered ones, and it is above the scope of this paper to extensively compare the graph kernels in literature.”