On Valid Optimal Assignment Kernels and Applications to Graph Classification

Abstract

The success of kernel methods has initiated the design of novel positive semidefinite functions, in particular for structured data. A leading design paradigm for this is the convolution kernel, which decomposes structured objects into their parts and sums over all pairs of parts. Assignment kernels, in contrast, are obtained from an optimal bijection between parts, which can provide a more valid notion of similarity. In general however, optimal assignments yield indefinite functions, which complicates their use in kernel methods. We characterize a class of base kernels used to compare parts that guarantees positive semidefinite optimal assignment kernels. These base kernels give rise to hierarchies from which the optimal assignment kernels are computed in linear time by histogram intersection. We apply these results by developing the Weisfeiler-Lehman optimal assignment kernel for graphs. It provides high classification accuracy on widely-used benchmark data sets improving over the original Weisfeiler-Lehman kernel.

9 pages, 4 figures, NIPS 2016

Cited by in corpus (33)

• A Survey on Graph Kernels
• InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization
• Graph Capsule Convolutional Neural Networks
• Graph Kernels: A Survey
• Structure-Feature based Graph Self-adaptive Pooling
• Graph Kernels: State-of-the-Art and Future Challenges
• Wasserstein Weisfeiler-Lehman Graph Kernels
• DDGK: Learning Graph Representations for Deep Divergence Graph Kernels
• Learning metrics for persistence-based summaries and applications for graph classification
• Entropic Dynamic Time Warping Kernels for Co-evolving Financial Time Series Analysis
• Indefinite Kernel Logistic Regression with Concave-inexact-convex Procedure
• Interpretable Neural Architecture Search via Bayesian Optimisation with Weisfeiler-Lehman Kernels
• Learning subtree pattern importance for Weisfeiler-Lehmanbased graph kernels
• Deep Graph Similarity Learning: A Survey
• iPool -- Information-based Pooling in Hierarchical Graph Neural Networks
• Memory-Based Graph Networks
• Learning Deep Graph Representations via Convolutional Neural Networks
• Neighborhood Preserving Kernels for Attributed Graphs
• Revisiting 2D Convolutional Neural Networks for Graph-based Applications
• Geometric Scattering for Graph Data Analysis
• LCS Graph Kernel Based on Wasserstein Distance in Longest Common Subsequence Metric Space
• Comparing Temporal Graphs Using Dynamic Time Warping
• Wasserstein Embedding for Graph Learning
• Tree-Sliced Variants of Wasserstein Distances
• Scalable Global Alignment Graph Kernel Using Random Features: From Node Embedding to Graph Embedding
• Graph Filtration Learning
• Provenance Graph Kernel
• Topological Graph Neural Networks
• Graph Self-Supervised Learning with Learnable Structural and Positional Encodings
• Learning-based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matching
• Learning Data-adaptive Nonparametric Kernels
• REFORM: Fast and Adaptive Solution for Subteam Replacement
• Density of States Graph Kernels