The Multiscale Laplacian Graph Kernel

By Risi Kondor, Horace Pan. 2016

187 citations recorded by the source corpus.

Many real world graphs, such as the graphs of molecules, exhibit structure at multiple different scales, but most existing kernels between graphs are either purely local or purely global in character. In contrast, by building a hierarchy of nested subgraphs, the Multiscale Laplacian Graph kernels (MLG kernels) that we define in this paper can account for structure at a range of different scales. At the heart of the MLG construction is another new graph kernel, called the Feature Space Laplacian Graph kernel (FLG kernel), which has the property that it can lift a base kernel defined on the vertices of two graphs to a kernel between the graphs. The MLG kernel applies such FLG kernels to subgraphs recursively. To make the MLG kernel computationally feasible, we also introduce a randomized projection procedure, similar to the Nystro m method, but for RKHS operators.

Subfields: Artificial Intelligence, Geometry and Topology, Statistical and Nonlinear Physics, 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 Geometry and Topology

In Statistical and Nonlinear Physics

In Graph Learning

Citations in the corpus

An End-to-End Deep Learning Architecture for Graph Classification (2018, background): “Recent studies show comparing graphs more glob- ally can improve the performance (Kondor and Pan 2016; Morris, Kersting, and Mutzel 2017).”
Covariant Compositional Networks For Learning Graphs (2018, methodology): “For the graph kernels datasets, we compare against graph kernel results as reported in (Kondor & Pan, 2016) (which computed kernel matrices using the Weisfeiler–Lehman, Weisfeiler–edge, shortest paths, graphlets and multiscale Laplacian graph kernels and used a C-SVM on top), Neural graph…”
Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks (2018, background): “Recent works focus on assignment-based approaches (Kriege, Giscard, and Wilson 2016; Nikolentzos, Meladianos, and Vazirgiannis 2017; Johansson and Dubhashi 2015), spectral approaches (Kondor and Pan 2016), and graph decomposition approaches (Niko-lentzos et al. 2018).”
A simple yet effective baseline for non-attribute graph classification (2018, background): “[KP16], ˜ V is the number of sampled vertices and ˜ V V.”
Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, background): “Other recent works focus on assignment-based (Johansson & Dubhashi, 2015; Kriege et al., 2016; Nikolentzos et al., 2017), spectral (Kondor & Pan, 2016; Verma & Zhang, 2017), graph decomposition (Nikolentzos et al., 2018), randomized binning approaches (Heimann et al., 2019), and the extension of…”
Contrastive Multi-View Representation Learning on Graphs (2020, background): “…(SP) (Borgwardt & Kriegel, 2005), Graphlet kernel (GK) (Shervashidze et al., 2009), Weisfeiler-Lehman sub-tree kernel (WL) (Sher-vashidze et al., 2011), deep graph kernels (DGK) (Ya-nardag & Vishwana, 2015), and multi-scale Laplacian kernel (MLG) (Kondor & Pan, 2016) reported in (Sun et al., 2020).”
Hunt For The Unique, Stable, Sparse And Fast Feature Learning On Graphs (2017, methodology): “We compare our method with 6 state-of-art Graphs Kernels: Random Walk (RW) [13], Shortest Path Kernel (SP) [4], Graphlet Kernel (GK) [30], Weisfeiler-Lehman Kernel (WL) [31], Deep Graph Kernels (DGK) [34], Multiscale Laplacian Graph Kernels (MLK) [21].”
Graph Capsule Convolutional Neural Networks (2018, background): “…Shortest Path Kernel (SP) (Borgwardt & Kriegel, 2005), Graphlet Kernel (GK) (Shervashidze et al., 2009), Weisfeiler-Lehman Sub-tree Kernel (WL) (Shervashidze et al., 2011), Deep Graph Kernels (DGK) (Yanardag & Vishwanathan, 2015) and Multiscale Laplacian Graph Kernels (MLK) (Kondor & Pan, 2016).”
Glocalized Weisfeiler-Lehman Graph Kernels: Global-Local Feature Maps of Graphs (2017, background): “Moreover, Kondor and Pan [42] proposed a graph kernel based on the graph Laplacian.”
A Degeneracy Framework for Graph Similarity (2018, methodology): “Recently, the multiscale Lapla-Proceedings cian kernel was introduced to effectively compare structure at different scales [ Kondor and Pan, 2016 ] , while some neural network architectures were also designed to address the same problem [Dai et al. , 2016].”
TUDataset: A collection of benchmark datasets for learning with graphs (2020, background): “Further recent works focus on approaches based on assignments (Kriege et al., 2016; Nikolentzos et al., 2017), spectral properties (Kondor & Pan, 2016), graph decomposition (Nikolentzos et al., 2018), randomized binning (Heimann et al., 2019), and the extension of kernels based on the…”
Graph Classification using Structural Attention (2018, background): “This similarity can be measured by considering various structural properties like the shortest paths between nodes [4], the occurrence of certain graphlets or subgraphs [26], and even the structure of the graph at different scales [15].”
GroupINN: Grouping-based Interpretable Neural Network for Classification of Limited, Noisy Brain Data (2019, methodology): “Kernel methods usually compute the similarity between two networks based on substructures, such as walks [39], shortest paths [2], graphlets [30], or other subgraphs [15].”
A survey on graph kernels (2019, methodology): “In [49], a graph kernel is proposed which is able to capture the graph structure at multiple scales, i.”
InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization (2019, methodology): “We show results from six methods including three state-of-the-art graph kernel methods: WL [51], DGK [63], and MLG [27].”