The Multiscale Laplacian Graph Kernel

Abstract

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 Nyström method, but for RKHS operators.

References in corpus (1)

• Discriminative Embeddings of Latent Variable Models for Structured Data

Cited by in corpus (40)

• A Survey on Graph Kernels
• TUDataset: A collection of benchmark datasets for learning with graphs
• InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization
• NetLSD: Hearing the Shape of a Graph
• Graph Capsule Convolutional Neural Networks
• Graph Kernels: A Survey
• Covariant Compositional Networks For Learning Graphs
• Learning molecular energies using localized graph kernels
• Graph Kernels: State-of-the-Art and Future Challenges
• Entropic Dynamic Time Warping Kernels for Co-evolving Financial Time Series Analysis
• InfoGCL: Information-Aware Graph Contrastive Learning
• Practical methods for graph two-sample testing
• Hierarchical stochastic graphlet embedding for graph-based pattern recognition
• Stochastic Graphlet Embedding
• Interpretable Neural Architecture Search via Bayesian Optimisation with Weisfeiler-Lehman Kernels
• MONK -- Outlier-Robust Mean Embedding Estimation by Median-of-Means
• Distance Metric Learning for Graph Structured Data
• Learning Universal Graph Neural Network Embeddings With Aid Of Transfer Learning
• Iterative Graph Self-Distillation
• Revisiting 2D Convolutional Neural Networks for Graph-based Applications
• Graph Convolutional Neural Networks via Motif-based Attention
• Graph2Seq: Scalable Learning Dynamics for Graphs
• Graph Autoencoders with Deconvolutional Networks
• Label Contrastive Coding based Graph Neural Network for Graph Classification
• Wasserstein Embedding for Graph Learning
• COPT: Coordinated Optimal Transport for Graph Sketching
• A Novel Higher-order Weisfeiler-Lehman Graph Convolution
• Measuring and utilizing temporal network dissimilarity
• Scalable Global Alignment Graph Kernel Using Random Features: From Node Embedding to Graph Embedding
• SGR: Self-Supervised Spectral Graph Representation Learning
• Message Passing Graph Kernels
• Global Weisfeiler-Lehman Graph Kernels
• Solving graph compression via optimal transport
• Ego-CNN: Distributed, Egocentric Representations of Graphs for Detecting Critical Structures
• Graphon based Clustering and Testing of Networks: Algorithms and Theory
• Learning Graphon Autoencoders for Generative Graph Modeling
• Emanuel Parzen: A Memorial, and a Model With the Two Kernels That He Championed
• A Quantum-inspired Similarity Measure for the Analysis of Complete Weighted Graphs
• Topology-Aware Hashing for Effective Control Flow Graph Similarity Analysis
• Graph Kernels based on High Order Graphlet Parsing and Hashing