Subgraph Matching Kernels for Attributed Graphs

Abstract

We propose graph kernels based on subgraph matchings, i.e. structure-preserving bijections between subgraphs. While recently proposed kernels based on common subgraphs (Wale et al., 2008; Shervashidze et al., 2009) in general can not be applied to attributed graphs, our approach allows to rate mappings of subgraphs by a flexible scoring scheme comparing vertex and edge attributes by kernels. We show that subgraph matching kernels generalize several known kernels. To compute the kernel we propose a graph-theoretical algorithm inspired by a classical relation between common subgraphs of two graphs and cliques in their product graph observed by Levi (1973). Encouraging experimental results on a classification task of real-world graphs are presented.

Appears in Proceedings of the 29th International Conference on Machine Learning (ICML 2012)

Cited by in corpus (41)

• A Survey on Graph Kernels
• Contrastive Multi-View Representation Learning on Graphs
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
• Link Prediction Based on Graph Neural Networks
• A quantum hardware-induced graph kernel based on Gaussian Boson Sampling
• Graph Kernels: A Survey
• Learning Backtrackless Aligned-Spatial Graph Convolutional Networks for Graph Classification
• Graph Kernels: State-of-the-Art and Future Challenges
• Wasserstein Weisfeiler-Lehman Graph Kernels
• Dual Space Graph Contrastive Learning
• InfoGCL: Information-Aware Graph Contrastive Learning
• A tree-based kernel for graphs with continuous attributes
• Hierarchical stochastic graphlet embedding for graph-based pattern recognition
• Decimated Framelet System on Graphs and Fast G-Framelet Transforms
• Distance Metric Learning for Graph Structured Data
• edGNN: a Simple and Powerful GNN for Directed Labeled Graphs
• Partial Optimal Transport with Applications on Positive-Unlabeled Learning
• Learning Deep Graph Representations via Convolutional Neural Networks
• Redundancy-Free Computation Graphs for Graph Neural Networks
• Neighborhood Preserving Kernels for Attributed Graphs
• MathNet: Haar-Like Wavelet Multiresolution-Analysis for Graph Representation and Learning
• Mask-GVAE: Blind Denoising Graphs via Partition
• Deconvolutional Networks on Graph Data
• Graph Autoencoders with Deconvolutional Networks
• COPT: Coordinated Optimal Transport for Graph Sketching
• Global Weisfeiler-Lehman Graph Kernels
• Message Passing Graph Kernels
• Some New Layer Architectures for Graph CNN
• The All-Paths and Cycles Graph Kernel
• Solving graph compression via optimal transport
• Partition and Code: learning how to compress graphs
• Graph Kernels via Functional Embedding
• A Hierarchical Transitive-Aligned Graph Kernel for Un-attributed Graphs
• Towards Expressive Graph Representation
• Ordinal Pattern Kernel for Brain Connectivity Network Classification
• Transport based Graph Kernels
• Learning Graphon Autoencoders for Generative Graph Modeling
• A Structural Feature-Based Approach for Comprehensive Graph Classification
• Propagation Kernels
• Revisiting the Graph Isomorphism Problem with Semidefinite Programming
• Graph Space Embedding